--- a/layout/base/ServoRestyleManager.cpp
+++ b/layout/base/ServoRestyleManager.cpp
@@ -90,19 +90,21 @@ ServoRestyleManager::RebuildAllStyleData
   // non-inheriting anon boxes. It's not clear if we want to support that, but
   // if we do, we need to re-selector-match them here.
 }
 
 void
 ServoRestyleManager::PostRebuildAllStyleDataEvent(nsChangeHint aExtraHint,
                                                   nsRestyleHint aRestyleHint)
 {
-  // TODO(emilio): We should do the stylesheet flushing + device reset async
-  // here.
-  RebuildAllStyleData(aExtraHint, aRestyleHint);
+  StyleSet()->ClearDataAndMarkDeviceDirty();
+
+  if (Element* root = mPresContext->Document()->GetRootElement()) {
+    PostRestyleEvent(root, aRestyleHint, aExtraHint);
+  }
 }
 
 /* static */ void
 ServoRestyleManager::ClearServoDataFromSubtree(Element* aElement)
 {
   if (!aElement->HasServoData()) {
     MOZ_ASSERT(!aElement->HasDirtyDescendantsForServo());
     return;

--- a/layout/style/ServoBindingList.h
+++ b/layout/style/ServoBindingList.h
@@ -44,16 +44,18 @@ SERVO_BINDING_FUNC(Servo_StyleSheet_Clea
                    const nsACString* data,
                    RawGeckoURLExtraData* extra_data,
                    uint32_t line_number_offset)
 SERVO_BINDING_FUNC(Servo_StyleSheet_HasRules, bool,
                    RawServoStyleSheetBorrowed sheet)
 SERVO_BINDING_FUNC(Servo_StyleSheet_GetRules, ServoCssRulesStrong,
                    RawServoStyleSheetBorrowed sheet)
 SERVO_BINDING_FUNC(Servo_StyleSet_Init, RawServoStyleSetOwned, RawGeckoPresContextOwned pres_context)
+SERVO_BINDING_FUNC(Servo_StyleSet_Clear, void,
+                   RawServoStyleSetBorrowed set)
 SERVO_BINDING_FUNC(Servo_StyleSet_RebuildData, void,
                    RawServoStyleSetBorrowed set)
 SERVO_BINDING_FUNC(Servo_StyleSet_Drop, void, RawServoStyleSetOwned set)
 SERVO_BINDING_FUNC(Servo_StyleSet_AppendStyleSheet, void,
                    RawServoStyleSetBorrowed set,
                    RawServoStyleSheetBorrowed sheet,
                    uint64_t unique_id)
 SERVO_BINDING_FUNC(Servo_StyleSet_PrependStyleSheet, void,

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -37,17 +37,17 @@ static inline uint64_t UniqueIDForSheet(
   // we use the sheet address as a unique ID.
   return reinterpret_cast<uint64_t>(aSheet);
 }
 
 ServoStyleSet::ServoStyleSet()
   : mPresContext(nullptr)
   , mAllowResolveStaleStyles(false)
   , mAuthorStyleDisabled(false)
-  , mStylistMayNeedRebuild(false)
+  , mStylistState(StylistState::NotDirty)
 {
 }
 
 ServoStyleSet::~ServoStyleSet()
 {
 }
 
 void
@@ -250,28 +250,28 @@ 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();
 
   // Ensure that the @font-face data is not stale
   mPresContext->Document()->GetUserFontSet();
+
+  UpdateStylistIfNeeded();
 }
 
 void
 ServoStyleSet::PreTraverse(Element* aRoot)
 {
   PreTraverseSync();
 
   // Process animation stuff that we should avoid doing during the parallel
@@ -297,17 +297,17 @@ ServoStyleSet::PrepareAndTraverseSubtree
   TraversalRootBehavior aRootBehavior,
   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);
+  MOZ_ASSERT(!StylistNeedsUpdate());
   AutoSetInServoTraversal guard(this);
 
   const SnapshotTable& snapshots = Snapshots();
 
   bool isInitial = !aRoot->HasServoData();
   bool forReconstruct =
     aRestyleBehavior == TraversalRestyleBehavior::ForReconstruct;
   bool postTraversalRequired = Servo_TraverseSubtree(
@@ -432,17 +432,17 @@ ServoStyleSet::ResolveStyleForPlaceholde
 }
 
 already_AddRefed<nsStyleContext>
 ServoStyleSet::ResolvePseudoElementStyle(Element* aOriginatingElement,
                                          CSSPseudoElementType aType,
                                          nsStyleContext* aParentContext,
                                          Element* aPseudoElement)
 {
-  MaybeRebuildStylist();
+  UpdateStylistIfNeeded();
 
   // 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);
 
   RefPtr<ServoComputedValues> computedValues;
   if (aPseudoElement) {
@@ -491,17 +491,17 @@ ServoStyleSet::ResolveTransientServoStyl
 
 already_AddRefed<nsStyleContext>
 ServoStyleSet::ResolveInheritingAnonymousBoxStyle(nsIAtom* aPseudoTag,
                                                   nsStyleContext* aParentContext)
 {
   MOZ_ASSERT(nsCSSAnonBoxes::IsAnonBox(aPseudoTag) &&
              !nsCSSAnonBoxes::IsNonInheritingAnonBox(aPseudoTag));
 
-  MaybeRebuildStylist();
+  UpdateStylistIfNeeded();
 
   bool skipFixup =
     nsCSSAnonBoxes::AnonBoxSkipsParentDisplayBasedStyleFixup(aPseudoTag);
 
   const ServoComputedValues* parentStyle =
     aParentContext ? aParentContext->StyleSource().AsServoComputedValues()
                    : nullptr;
   RefPtr<ServoComputedValues> computedValues =
@@ -535,17 +535,17 @@ ServoStyleSet::ResolveNonInheritingAnony
   nsCSSAnonBoxes::NonInheriting type =
     nsCSSAnonBoxes::NonInheritingTypeForPseudoTag(aPseudoTag);
   RefPtr<nsStyleContext>& cache = mNonInheritingStyleContexts[type];
   if (cache) {
     RefPtr<nsStyleContext> retval = cache;
     return retval.forget();
   }
 
-  MaybeRebuildStylist();
+  UpdateStylistIfNeeded();
 
   // 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 =
@@ -583,17 +583,17 @@ ServoStyleSet::AppendStyleSheet(SheetTyp
 
   if (mRawSet) {
     // Maintain a mirrored list of sheets on the servo side.
     // Servo will remove aSheet from its original position as part of the call
     // to Servo_StyleSet_AppendStyleSheet.
     Servo_StyleSet_AppendStyleSheet(mRawSet.get(),
                                     aSheet->RawSheet(),
                                     UniqueIDForSheet(aSheet));
-    mStylistMayNeedRebuild = true;
+    SetStylistStyleSheetsDirty();
   }
 
   return NS_OK;
 }
 
 nsresult
 ServoStyleSet::PrependStyleSheet(SheetType aType,
                                  ServoStyleSheet* aSheet)
@@ -608,49 +608,49 @@ ServoStyleSet::PrependStyleSheet(SheetTy
 
   if (mRawSet) {
     // Maintain a mirrored list of sheets on the servo side.
     // Servo will remove aSheet from its original position as part of the call
     // to Servo_StyleSet_PrependStyleSheet.
     Servo_StyleSet_PrependStyleSheet(mRawSet.get(),
                                      aSheet->RawSheet(),
                                      UniqueIDForSheet(aSheet));
-    mStylistMayNeedRebuild = true;
+    SetStylistStyleSheetsDirty();
   }
 
   return NS_OK;
 }
 
 nsresult
 ServoStyleSet::RemoveStyleSheet(SheetType aType,
                                 ServoStyleSheet* aSheet)
 {
   MOZ_ASSERT(aSheet);
   MOZ_ASSERT(nsStyleSet::IsCSSSheetType(aType));
 
   RemoveSheetOfType(aType, aSheet);
   if (mRawSet) {
     // Maintain a mirrored list of sheets on the servo side.
     Servo_StyleSet_RemoveStyleSheet(mRawSet.get(), UniqueIDForSheet(aSheet));
-    mStylistMayNeedRebuild = true;
+    SetStylistStyleSheetsDirty();
   }
 
   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;
+  SetStylistStyleSheetsDirty();
 
   // Remove all the existing sheets first.
   if (mRawSet) {
     for (const auto& sheet : mSheets[aType]) {
       Servo_StyleSet_RemoveStyleSheet(mRawSet.get(), UniqueIDForSheet(sheet));
     }
   }
   mSheets[aType].Clear();
@@ -687,17 +687,17 @@ ServoStyleSet::InsertStyleSheetBefore(Sh
   InsertSheetOfType(aType, aNewSheet, aReferenceSheet);
 
   if (mRawSet) {
     // Maintain a mirrored list of sheets on the servo side.
     Servo_StyleSet_InsertStyleSheetBefore(mRawSet.get(),
                                           aNewSheet->RawSheet(),
                                           UniqueIDForSheet(aNewSheet),
                                           UniqueIDForSheet(aReferenceSheet));
-    mStylistMayNeedRebuild = true;
+    SetStylistStyleSheetsDirty();
   }
 
   return NS_OK;
 }
 
 int32_t
 ServoStyleSet::SheetCount(SheetType aType) const
 {
@@ -739,40 +739,40 @@ ServoStyleSet::AddDocStyleSheet(ServoSty
     InsertSheetOfType(SheetType::Doc, aSheet, beforeSheet);
 
     if (mRawSet) {
       // Maintain a mirrored list of sheets on the servo side.
       Servo_StyleSet_InsertStyleSheetBefore(mRawSet.get(),
                                             aSheet->RawSheet(),
                                             UniqueIDForSheet(aSheet),
                                             UniqueIDForSheet(beforeSheet));
-      mStylistMayNeedRebuild = true;
+      SetStylistStyleSheetsDirty();
     }
   } else {
     // This case is append.
     AppendSheetOfType(SheetType::Doc, aSheet);
 
     if (mRawSet) {
       // Maintain a mirrored list of sheets on the servo side.
       Servo_StyleSet_AppendStyleSheet(mRawSet.get(),
                                       aSheet->RawSheet(),
                                       UniqueIDForSheet(aSheet));
-      mStylistMayNeedRebuild = true;
+      SetStylistStyleSheetsDirty();
     }
   }
 
   return NS_OK;
 }
 
 already_AddRefed<nsStyleContext>
 ServoStyleSet::ProbePseudoElementStyle(Element* aOriginatingElement,
                                        CSSPseudoElementType aType,
                                        nsStyleContext* aParentContext)
 {
-  MaybeRebuildStylist();
+  UpdateStylistIfNeeded();
 
   // 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);
 
   RefPtr<ServoComputedValues> computedValues =
     Servo_ResolvePseudoStyle(aOriginatingElement, aType,
@@ -887,17 +887,17 @@ ServoStyleSet::StyleSubtreeForReconstruc
                               TraversalRootBehavior::Normal,
                               TraversalRestyleBehavior::ForReconstruct);
   MOZ_ASSERT(!postTraversalRequired);
 }
 
 void
 ServoStyleSet::NoteStyleSheetsChanged()
 {
-  mStylistMayNeedRebuild = true;
+  SetStylistStyleSheetsDirty();
   Servo_StyleSet_NoteStyleSheetsChanged(mRawSet.get(), mAuthorStyleDisabled);
 }
 
 #ifdef DEBUG
 void
 ServoStyleSet::AssertTreeIsClean()
 {
   DocumentStyleRootIterator iter(mPresContext->Document());
@@ -908,17 +908,17 @@ ServoStyleSet::AssertTreeIsClean()
 #endif
 
 bool
 ServoStyleSet::GetKeyframesForName(const nsString& aName,
                                    const nsTimingFunction& aTimingFunction,
                                    const ServoComputedValues* aComputedValues,
                                    nsTArray<Keyframe>& aKeyframes)
 {
-  MaybeRebuildStylist();
+  UpdateStylistIfNeeded();
 
   NS_ConvertUTF16toUTF8 name(aName);
   return Servo_StyleSet_GetKeyframesForName(mRawSet.get(),
                                             &name,
                                             &aTimingFunction,
                                             aComputedValues,
                                             &aKeyframes);
 }
@@ -963,22 +963,31 @@ ServoStyleSet::ComputeAnimationValue(
                                       mRawSet.get()).Consume();
 }
 
 void
 ServoStyleSet::RebuildData()
 {
   ClearNonInheritingStyleContexts();
   Servo_StyleSet_RebuildData(mRawSet.get());
+  mStylistState = StylistState::NotDirty;
+}
+
+void
+ServoStyleSet::ClearDataAndMarkDeviceDirty()
+{
+  ClearNonInheritingStyleContexts();
+  Servo_StyleSet_Clear(mRawSet.get());
+  mStylistState = StylistState::FullyDirty;
 }
 
 already_AddRefed<ServoComputedValues>
 ServoStyleSet::ResolveServoStyle(Element* aElement)
 {
-  MaybeRebuildStylist();
+  UpdateStylistIfNeeded();
   return Servo_ResolveStyle(aElement, mRawSet.get(),
                             mAllowResolveStaleStyles).Consume();
 }
 
 void
 ServoStyleSet::ClearNonInheritingStyleContexts()
 {
   for (RefPtr<nsStyleContext>& ptr : mNonInheritingStyleContexts) {
@@ -986,17 +995,17 @@ ServoStyleSet::ClearNonInheritingStyleCo
   }
 }
 
 already_AddRefed<ServoComputedValues>
 ServoStyleSet::ResolveStyleLazily(Element* aElement,
                                   CSSPseudoElementType aPseudoType)
 {
   mPresContext->EffectCompositor()->PreTraverse(aElement, aPseudoType);
-  MOZ_ASSERT(!mStylistMayNeedRebuild);
+  MOZ_ASSERT(!StylistNeedsUpdate());
 
   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
@@ -1035,44 +1044,48 @@ ServoStyleSet::ResolveStyleLazily(Elemen
   }
 
   return computedValues.forget();
 }
 
 bool
 ServoStyleSet::AppendFontFaceRules(nsTArray<nsFontFaceRuleContainer>& aArray)
 {
-  MaybeRebuildStylist();
+  UpdateStylistIfNeeded();
   Servo_StyleSet_GetFontFaceRules(mRawSet.get(), &aArray);
   return true;
 }
 
 nsCSSCounterStyleRule*
 ServoStyleSet::CounterStyleRuleForName(nsIAtom* aName)
 {
   return Servo_StyleSet_GetCounterStyleRule(mRawSet.get(), aName);
 }
 
 already_AddRefed<ServoComputedValues>
 ServoStyleSet::ResolveForDeclarations(
   ServoComputedValuesBorrowedOrNull aParentOrNull,
   RawServoDeclarationBlockBorrowed aDeclarations)
 {
-  MaybeRebuildStylist();
+  UpdateStylistIfNeeded();
   return Servo_StyleSet_ResolveForDeclarations(mRawSet.get(),
                                                aParentOrNull,
                                                aDeclarations).Consume();
 }
 
 void
-ServoStyleSet::RebuildStylist()
+ServoStyleSet::UpdateStylist()
 {
-  MOZ_ASSERT(mStylistMayNeedRebuild);
-  Servo_StyleSet_FlushStyleSheets(mRawSet.get());
-  mStylistMayNeedRebuild = false;
+  MOZ_ASSERT(StylistNeedsUpdate());
+  if (mStylistState == StylistState::FullyDirty) {
+    RebuildData();
+  } else {
+    Servo_StyleSet_FlushStyleSheets(mRawSet.get());
+  }
+  mStylistState = StylistState::NotDirty;
 }
 
 void
 ServoStyleSet::PrependSheetOfType(SheetType aType,
                                   ServoStyleSheet* aSheet)
 {
   mSheets[aType].InsertElementAt(0, aSheet);
 }

--- a/layout/style/ServoStyleSet.h
+++ b/layout/style/ServoStyleSet.h
@@ -285,16 +285,23 @@ public:
 
   /**
    * Rebuild the style data. This will force a stylesheet flush, and also
    * recompute the default computed styles.
    */
   void RebuildData();
 
   /**
+   * Clears the style data, both style sheet data and cached non-inheriting
+   * style contexts, and marks the stylist as needing an unconditional full
+   * rebuild, including a device reset.
+   */
+  void ClearDataAndMarkDeviceDirty();
+
+  /**
    * Resolve style for the given element, and return it as a
    * ServoComputedValues, not an nsStyleContext.
    */
   already_AddRefed<ServoComputedValues> ResolveServoStyle(dom::Element* aElement);
 
   bool GetKeyframesForName(const nsString& aName,
                            const nsTimingFunction& aTimingFunction,
                            const ServoComputedValues* aComputedValues,
@@ -415,29 +422,61 @@ 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.
+   * A tri-state used to track which kind of stylist state we may need to
+   * update.
+   */
+  enum class StylistState : uint8_t {
+    /** The stylist is not dirty, we should do nothing */
+    NotDirty,
+    /** The style sheets have changed, so we need to update the style data. */
+    StyleSheetsDirty,
+    /**
+     * All style data is dirty and both style sheet data and default computed
+     * values need to be recomputed.
+     */
+    FullyDirty,
+  };
+
+  /**
+   * Note that the stylist needs a style flush due to style sheet changes.
    */
-  void RebuildStylist();
+  void SetStylistStyleSheetsDirty()
+  {
+    if (mStylistState == StylistState::NotDirty) {
+      mStylistState = StylistState::StyleSheetsDirty;
+    }
+  }
+
+  bool StylistNeedsUpdate() const
+  {
+    return mStylistState != StylistState::NotDirty;
+  }
+
+  /**
+   * Update the stylist as needed to ensure style data is up-to-date.
+   *
+   * This should only be called if StylistNeedsUpdate returns true.
+   */
+  void UpdateStylist();
 
   /**
    * Helper for correctly calling RebuildStylist without paying the cost of an
    * extra function call in the common no-rebuild-needed case.
    */
-  void MaybeRebuildStylist()
+  void UpdateStylistIfNeeded()
   {
-    if (mStylistMayNeedRebuild) {
-      RebuildStylist();
+    if (StylistNeedsUpdate()) {
+      UpdateStylist();
     }
   }
 
   already_AddRefed<ServoComputedValues>
     ResolveStyleLazily(dom::Element* aElement, CSSPseudoElementType aPseudoType);
 
   void RunPostTraversalTasks();
 
@@ -455,17 +494,17 @@ private:
                          ServoStyleSheet* aSheet);
 
   nsPresContext* mPresContext;
   UniquePtr<RawServoStyleSet> mRawSet;
   EnumeratedArray<SheetType, SheetType::Count,
                   nsTArray<RefPtr<ServoStyleSheet>>> mSheets;
   bool mAllowResolveStaleStyles;
   bool mAuthorStyleDisabled;
-  bool mStylistMayNeedRebuild;
+  StylistState mStylistState;
 
   // 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.