--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -29,16 +29,17 @@ using namespace mozilla;
 using namespace mozilla::dom;
 
 ServoStyleSet::ServoStyleSet()
   : mPresContext(nullptr)
   , mBatching(0)
   , mUniqueIDCounter(0)
   , mAllowResolveStaleStyles(false)
   , mAuthorStyleDisabled(false)
+  , mStylistMayNeedRebuild(false)
 {
 }
 
 ServoStyleSet::~ServoStyleSet()
 {
 }
 
 void
@@ -171,16 +172,17 @@ nsresult
 ServoStyleSet::EndUpdate()
 {
   MOZ_ASSERT(mBatching > 0);
   if (--mBatching > 0) {
     return NS_OK;
   }
 
   Servo_StyleSet_FlushStyleSheets(mRawSet.get());
+  mStylistMayNeedRebuild = false;
   return NS_OK;
 }
 
 already_AddRefed<nsStyleContext>
 ServoStyleSet::ResolveStyleFor(Element* aElement,
                                nsStyleContext* aParentContext,
                                LazyComputeBehavior aMayCompute)
 {
@@ -245,16 +247,18 @@ ServoStyleSet::ResolveMappedAttrDeclarat
   }
 
   mPresContext->Document()->ResolveScheduledSVGPresAttrs();
 }
 
 void
 ServoStyleSet::PreTraverseSync()
 {
+  MaybeRebuildStylist();
+
   ResolveMappedAttrDeclarationBlocks();
 
   nsCSSRuleProcessor::InitSystemMetrics();
 
   // This is lazily computed and pseudo matching needs to access
   // it so force computation early.
   mPresContext->Document()->GetDocumentState();
 
@@ -290,16 +294,17 @@ ServoStyleSet::PrepareAndTraverseSubtree
                                          TraversalRestyleBehavior
                                            aRestyleBehavior)
 {
   // Get the Document's root element to ensure that the cache is valid before
   // calling into the (potentially-parallel) Servo traversal, where a cache hit
   // is necessary to avoid a data race when updating the cache.
   mozilla::Unused << aRoot->OwnerDoc()->GetRootElement();
 
+  MOZ_ASSERT(!mStylistMayNeedRebuild);
   AutoSetInServoTraversal guard(this);
 
   bool isInitial = !aRoot->HasServoData();
   bool forReconstruct =
     aRestyleBehavior == TraversalRestyleBehavior::ForReconstruct;
   bool postTraversalRequired =
     Servo_TraverseSubtree(aRoot, mRawSet.get(), aRootBehavior, aRestyleBehavior);
   MOZ_ASSERT_IF(isInitial || forReconstruct, !postTraversalRequired);
@@ -426,16 +431,18 @@ ServoStyleSet::ResolvePseudoElementStyle
                                          CSSPseudoElementType aType,
                                          nsStyleContext* aParentContext,
                                          Element* aPseudoElement)
 {
   if (aPseudoElement) {
     NS_WARNING("stylo: We don't support CSS_PSEUDO_ELEMENT_SUPPORTS_USER_ACTION_STATE yet");
   }
 
+  MaybeRebuildStylist();
+
   // NB: We ignore aParentContext, on the assumption that pseudo element styles
   // should just inherit from aOriginatingElement's primary style, which Servo
   // already knows.
   MOZ_ASSERT(aType < CSSPseudoElementType::Count);
   nsIAtom* pseudoTag = nsCSSPseudoElements::GetPseudoAtom(aType);
 
   RefPtr<ServoComputedValues> computedValues =
     Servo_ResolvePseudoStyle(aOriginatingElement, pseudoTag,
@@ -472,16 +479,18 @@ ServoStyleSet::ResolveTransientServoStyl
 
 already_AddRefed<nsStyleContext>
 ServoStyleSet::ResolveInheritingAnonymousBoxStyle(nsIAtom* aPseudoTag,
                                                   nsStyleContext* aParentContext)
 {
   MOZ_ASSERT(nsCSSAnonBoxes::IsAnonBox(aPseudoTag) &&
              !nsCSSAnonBoxes::IsNonInheritingAnonBox(aPseudoTag));
 
+  MaybeRebuildStylist();
+
   bool skipFixup =
     nsCSSAnonBoxes::AnonBoxSkipsParentDisplayBasedStyleFixup(aPseudoTag);
 
   const ServoComputedValues* parentStyle =
     aParentContext ? aParentContext->StyleSource().AsServoComputedValues()
                    : nullptr;
   RefPtr<ServoComputedValues> computedValues =
     Servo_ComputedValues_GetForAnonymousBox(parentStyle, aPseudoTag, skipFixup,
@@ -514,16 +523,18 @@ ServoStyleSet::ResolveNonInheritingAnony
   nsCSSAnonBoxes::NonInheriting type =
     nsCSSAnonBoxes::NonInheritingTypeForPseudoTag(aPseudoTag);
   RefPtr<nsStyleContext>& cache = mNonInheritingStyleContexts[type];
   if (cache) {
     RefPtr<nsStyleContext> retval = cache;
     return retval.forget();
   }
 
+  MaybeRebuildStylist();
+
   // We always want to skip parent-based display fixup here.  It never makes
   // sense for non-inheriting anonymous boxes.  (Static assertions in
   // nsCSSAnonBoxes.cpp ensure that all non-inheriting non-anonymous boxes
   // are indeed annotated as skipping this fixup.)
   MOZ_ASSERT(!nsCSSAnonBoxes::IsNonInheritingAnonBox(nsCSSAnonBoxes::viewport),
              "viewport needs fixup to handle blockifying it");
   RefPtr<ServoComputedValues> computedValues =
     Servo_ComputedValues_GetForAnonymousBox(nullptr, aPseudoTag, true,
@@ -562,16 +573,17 @@ ServoStyleSet::AppendStyleSheet(SheetTyp
   uint32_t newUniqueID = AppendSheetOfType(aType, aSheet, oldUniqueID);
 
   if (mRawSet) {
     // Maintain a mirrored list of sheets on the servo side.
     Servo_StyleSet_AppendStyleSheet(mRawSet.get(),
                                     aSheet->RawSheet(),
                                     newUniqueID,
                                     !mBatching);
+    mStylistMayNeedRebuild = true;
   }
 
   return NS_OK;
 }
 
 nsresult
 ServoStyleSet::PrependStyleSheet(SheetType aType,
                                  ServoStyleSheet* aSheet)
@@ -588,46 +600,50 @@ ServoStyleSet::PrependStyleSheet(SheetTy
   uint32_t newUniqueID = PrependSheetOfType(aType, aSheet, oldUniqueID);
 
   if (mRawSet) {
     // Maintain a mirrored list of sheets on the servo side.
     Servo_StyleSet_PrependStyleSheet(mRawSet.get(),
                                      aSheet->RawSheet(),
                                      newUniqueID,
                                      !mBatching);
+    mStylistMayNeedRebuild = true;
   }
 
   return NS_OK;
 }
 
 nsresult
 ServoStyleSet::RemoveStyleSheet(SheetType aType,
                                 ServoStyleSheet* aSheet)
 {
   MOZ_ASSERT(aSheet);
   MOZ_ASSERT(nsStyleSet::IsCSSSheetType(aType));
 
   uint32_t uniqueID = RemoveSheetOfType(aType, aSheet);
   if (mRawSet && uniqueID) {
     // Maintain a mirrored list of sheets on the servo side.
     Servo_StyleSet_RemoveStyleSheet(mRawSet.get(), uniqueID, !mBatching);
+    mStylistMayNeedRebuild = true;
   }
 
   return NS_OK;
 }
 
 nsresult
 ServoStyleSet::ReplaceSheets(SheetType aType,
                              const nsTArray<RefPtr<ServoStyleSheet>>& aNewSheets)
 {
   // Gecko uses a two-dimensional array keyed by sheet type, whereas Servo
   // stores a flattened list. This makes ReplaceSheets a pretty clunky thing
   // to express. If the need ever arises, we can easily make this more efficent,
   // probably by aligning the representations better between engines.
 
+  mStylistMayNeedRebuild = true;
+
   // Remove all the existing sheets first.
   if (mRawSet) {
     for (const Entry& entry : mEntries[aType]) {
       Servo_StyleSet_RemoveStyleSheet(mRawSet.get(), entry.uniqueID, false);
     }
   }
   mEntries[aType].Clear();
 
@@ -640,16 +656,17 @@ ServoStyleSet::ReplaceSheets(SheetType a
                                       sheet->RawSheet(),
                                       uniqueID,
                                       false);
     }
   }
 
   if (!mBatching) {
     Servo_StyleSet_FlushStyleSheets(mRawSet.get());
+    mStylistMayNeedRebuild = false;
   }
 
   return NS_OK;
 }
 
 nsresult
 ServoStyleSet::InsertStyleSheetBefore(SheetType aType,
                                       ServoStyleSheet* aNewSheet,
@@ -678,16 +695,17 @@ ServoStyleSet::InsertStyleSheetBefore(Sh
 
   if (mRawSet) {
     // Maintain a mirrored list of sheets on the servo side.
     Servo_StyleSet_InsertStyleSheetBefore(mRawSet.get(),
                                           aNewSheet->RawSheet(),
                                           newUniqueID,
                                           beforeUniqueID,
                                           !mBatching);
+    mStylistMayNeedRebuild = true;
   }
 
   return NS_OK;
 }
 
 int32_t
 ServoStyleSet::SheetCount(SheetType aType) const
 {
@@ -733,40 +751,44 @@ ServoStyleSet::AddDocStyleSheet(ServoSty
 
     if (mRawSet) {
       // Maintain a mirrored list of sheets on the servo side.
       Servo_StyleSet_InsertStyleSheetBefore(mRawSet.get(),
                                             aSheet->RawSheet(),
                                             newUniqueID,
                                             beforeUniqueID,
                                             !mBatching);
+      mStylistMayNeedRebuild = true;
     }
   } else {
     // This case is append.
     uint32_t newUniqueID = AppendSheetOfType(SheetType::Doc,
                                              aSheet,
                                              oldUniqueID);
 
     if (mRawSet) {
       // Maintain a mirrored list of sheets on the servo side.
       Servo_StyleSet_AppendStyleSheet(mRawSet.get(),
                                       aSheet->RawSheet(),
                                       newUniqueID,
                                       !mBatching);
+      mStylistMayNeedRebuild = true;
     }
   }
 
   return NS_OK;
 }
 
 already_AddRefed<nsStyleContext>
 ServoStyleSet::ProbePseudoElementStyle(Element* aOriginatingElement,
                                        CSSPseudoElementType aType,
                                        nsStyleContext* aParentContext)
 {
+  MaybeRebuildStylist();
+
   // NB: We ignore aParentContext, on the assumption that pseudo element styles
   // should just inherit from aOriginatingElement's primary style, which Servo
   // already knows.
   MOZ_ASSERT(aType < CSSPseudoElementType::Count);
   nsIAtom* pseudoTag = nsCSSPseudoElements::GetPseudoAtom(aType);
 
   RefPtr<ServoComputedValues> computedValues =
     Servo_ResolvePseudoStyle(aOriginatingElement, pseudoTag,
@@ -880,19 +902,21 @@ ServoStyleSet::StyleSubtreeForReconstruc
                               TraversalRootBehavior::Normal,
                               TraversalRestyleBehavior::ForReconstruct);
   MOZ_ASSERT(!postTraversalRequired);
 }
 
 void
 ServoStyleSet::NoteStyleSheetsChanged()
 {
+  mStylistMayNeedRebuild = true;
   Servo_StyleSet_NoteStyleSheetsChanged(mRawSet.get(), mAuthorStyleDisabled);
   if (!mBatching) {
     Servo_StyleSet_FlushStyleSheets(mRawSet.get());
+    mStylistMayNeedRebuild = false;
   }
 }
 
 #ifdef DEBUG
 void
 ServoStyleSet::AssertTreeIsClean()
 {
   DocumentStyleRootIterator iter(mPresContext->Document());
@@ -903,16 +927,18 @@ ServoStyleSet::AssertTreeIsClean()
 #endif
 
 bool
 ServoStyleSet::FillKeyframesForName(const nsString& aName,
                                     const nsTimingFunction& aTimingFunction,
                                     const ServoComputedValues* aComputedValues,
                                     nsTArray<Keyframe>& aKeyframes)
 {
+  MaybeRebuildStylist();
+
   NS_ConvertUTF16toUTF8 name(aName);
   return Servo_StyleSet_FillKeyframesForName(mRawSet.get(),
                                              &name,
                                              &aTimingFunction,
                                              aComputedValues,
                                              &aKeyframes);
 }
 
@@ -960,32 +986,34 @@ ServoStyleSet::RebuildData()
 {
   ClearNonInheritingStyleContexts();
   Servo_StyleSet_RebuildData(mRawSet.get());
 }
 
 already_AddRefed<ServoComputedValues>
 ServoStyleSet::ResolveServoStyle(Element* aElement)
 {
+  MaybeRebuildStylist();
   return Servo_ResolveStyle(aElement, mRawSet.get(),
                             mAllowResolveStaleStyles).Consume();
 }
 
 void
 ServoStyleSet::ClearNonInheritingStyleContexts()
 {
   for (RefPtr<nsStyleContext>& ptr : mNonInheritingStyleContexts) {
     ptr = nullptr;
   }
 }
 
 already_AddRefed<ServoComputedValues>
 ServoStyleSet::ResolveStyleLazily(Element* aElement, nsIAtom* aPseudoTag)
 {
   mPresContext->EffectCompositor()->PreTraverse(aElement, aPseudoTag);
+  MOZ_ASSERT(!mStylistMayNeedRebuild);
 
   AutoSetInServoTraversal guard(this);
 
   /**
    * NB: This is needed because we process animations and transitions on the
    * pseudo-elements themselves, not on the parent's EagerPseudoStyles.
    *
    * That means that that style doesn't account for animations, and we can't do
@@ -1022,30 +1050,40 @@ ServoStyleSet::ResolveStyleLazily(Elemen
   }
 
   return computedValues.forget();
 }
 
 bool
 ServoStyleSet::AppendFontFaceRules(nsTArray<nsFontFaceRuleContainer>& aArray)
 {
+  MaybeRebuildStylist();
   Servo_StyleSet_GetFontFaceRules(mRawSet.get(), &aArray);
   return true;
 }
 
 already_AddRefed<ServoComputedValues>
 ServoStyleSet::ResolveForDeclarations(
   ServoComputedValuesBorrowedOrNull aParentOrNull,
   RawServoDeclarationBlockBorrowed aDeclarations)
 {
+  MaybeRebuildStylist();
   return Servo_StyleSet_ResolveForDeclarations(mRawSet.get(),
                                                aParentOrNull,
                                                aDeclarations).Consume();
 }
 
+void
+ServoStyleSet::RebuildStylist()
+{
+  MOZ_ASSERT(mStylistMayNeedRebuild);
+  Servo_StyleSet_FlushStyleSheets(mRawSet.get());
+  mStylistMayNeedRebuild = false;
+}
+
 uint32_t
 ServoStyleSet::FindSheetOfType(SheetType aType,
                                ServoStyleSheet* aSheet)
 {
   for (const auto& entry : mEntries[aType]) {
     if (entry.sheet == aSheet) {
       return entry.uniqueID;
     }

--- a/layout/style/ServoStyleSet.h
+++ b/layout/style/ServoStyleSet.h
@@ -392,16 +392,33 @@ private:
    *
    * When aRoot is null, the entire document is pre-traversed.  Otherwise,
    * only the subtree rooted at aRoot is pre-traversed.
    */
   void PreTraverse(dom::Element* aRoot = nullptr);
   // Subset of the pre-traverse steps that involve syncing up data
   void PreTraverseSync();
 
+  /**
+   * Rebuild the stylist.  This should only be called if mStylistMayNeedRebuild
+   * is true.
+   */
+  void RebuildStylist();
+
+  /**
+   * Helper for correctly calling RebuildStylist without paying the cost of an
+   * extra function call in the common no-rebuild-needed case.
+   */
+  void MaybeRebuildStylist()
+  {
+    if (mStylistMayNeedRebuild) {
+      RebuildStylist();
+    }
+  }
+
   already_AddRefed<ServoComputedValues> ResolveStyleLazily(dom::Element* aElement,
                                                            nsIAtom* aPseudoTag);
 
   void RunPostTraversalTasks();
 
   uint32_t FindSheetOfType(SheetType aType,
                            ServoStyleSheet* aSheet);
 
@@ -433,16 +450,17 @@ private:
   nsPresContext* mPresContext;
   UniquePtr<RawServoStyleSet> mRawSet;
   EnumeratedArray<SheetType, SheetType::Count,
                   nsTArray<Entry>> mEntries;
   int32_t mBatching;
   uint32_t mUniqueIDCounter;
   bool mAllowResolveStaleStyles;
   bool mAuthorStyleDisabled;
+  bool mStylistMayNeedRebuild;
 
   // Stores pointers to our cached style contexts for non-inheriting anonymous
   // boxes.
   EnumeratedArray<nsCSSAnonBoxes::NonInheriting,
                   nsCSSAnonBoxes::NonInheriting::_Count,
                   RefPtr<nsStyleContext>> mNonInheritingStyleContexts;
 
   // Tasks to perform after a traversal, back on the main thread.