--- a/layout/style/ServoBindingList.h
+++ b/layout/style/ServoBindingList.h
@@ -49,17 +49,18 @@ SERVO_BINDING_FUNC(Servo_StyleSheet_HasR
 SERVO_BINDING_FUNC(Servo_StyleSheet_GetRules, ServoCssRulesStrong,
                    RawServoStyleSheetBorrowed sheet)
 SERVO_BINDING_FUNC(Servo_StyleSheet_Clone, RawServoStyleSheetStrong,
                    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)
+                   RawServoStyleSetBorrowed set,
+                   RawGeckoElementBorrowedOrNull doc_elem)
 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,
                    RawServoStyleSetBorrowed set,
                    RawServoStyleSheetBorrowed sheet,
@@ -67,17 +68,18 @@ SERVO_BINDING_FUNC(Servo_StyleSet_Prepen
 SERVO_BINDING_FUNC(Servo_StyleSet_RemoveStyleSheet, void,
                    RawServoStyleSetBorrowed set,
                    uint64_t unique_id)
 SERVO_BINDING_FUNC(Servo_StyleSet_InsertStyleSheetBefore, void,
                    RawServoStyleSetBorrowed set,
                    RawServoStyleSheetBorrowed sheet,
                    uint64_t unique_id,
                    uint64_t before_unique_id)
-SERVO_BINDING_FUNC(Servo_StyleSet_FlushStyleSheets, void, RawServoStyleSetBorrowed set)
+SERVO_BINDING_FUNC(Servo_StyleSet_FlushStyleSheets, void, RawServoStyleSetBorrowed set,
+                   RawGeckoElementBorrowedOrNull doc_elem)
 SERVO_BINDING_FUNC(Servo_StyleSet_NoteStyleSheetsChanged, void,
                    RawServoStyleSetBorrowed set, bool author_style_disabled)
 SERVO_BINDING_FUNC(Servo_StyleSet_GetKeyframesForName, bool,
                    RawServoStyleSetBorrowed set,
                    const nsACString* property,
                    nsTimingFunctionBorrowed timing_function,
                    ServoComputedValuesBorrowed computed_values,
                    RawGeckoKeyframeListBorrowedMut keyframe_list)

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -125,20 +125,24 @@ ServoStyleSet::Shutdown()
   // starts going away.
   ClearNonInheritingStyleContexts();
   mRawSet = nullptr;
 }
 
 void
 ServoStyleSet::InvalidateStyleForCSSRuleChanges()
 {
-  if (Element* root = mPresContext->Document()->GetRootElement()) {
+  MOZ_ASSERT(StylistNeedsUpdate());
+  if (Element* root = mPresContext->Document()->GetDocumentElement()) {
+    // FIXME(emilio): Add a nicer API for this.
     mPresContext->RestyleManager()->PostRestyleEventForCSSRuleChanges(
-        root, eRestyle_Subtree, nsChangeHint(0));
+      root, nsRestyleHint(0), nsChangeHint(0));
   }
+  // Do nothing, we've recorded the invalidation, and we'll invalidate stuff
+  // async when styling something.
 }
 
 size_t
 ServoStyleSet::SizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
 {
   size_t n = aMallocSizeOf(this);
 
   // Measurement of the following members may be added later if DMD finds it is
@@ -162,27 +166,17 @@ ServoStyleSet::GetAuthorStyleDisabled() 
 nsresult
 ServoStyleSet::SetAuthorStyleDisabled(bool aStyleDisabled)
 {
   if (mAuthorStyleDisabled == aStyleDisabled) {
     return NS_OK;
   }
 
   mAuthorStyleDisabled = aStyleDisabled;
-
-  // If we've just disabled, we have to note the stylesheets have changed and
-  // call flush directly, since the PresShell won't.
-  if (mAuthorStyleDisabled) {
-    NoteStyleSheetsChanged();
-  }
-  // If we've just enabled, then PresShell will trigger the notification and
-  // later flush when the stylesheet objects are enabled in JS.
-  //
-  // TODO(emilio): Users can have JS disabled, can't they? Will that affect that
-  // notification on content documents?
+  ForceAllStyleDirty();
 
   return NS_OK;
 }
 
 void
 ServoStyleSet::BeginUpdate()
 {
 }
@@ -970,22 +964,43 @@ ServoStyleSet::StyleSubtreeForReconstruc
   DebugOnly<bool> postTraversalRequired =
     PrepareAndTraverseSubtree(aRoot,
                               TraversalRootBehavior::Normal,
                               TraversalRestyleBehavior::ForReconstruct);
   MOZ_ASSERT(!postTraversalRequired);
 }
 
 void
-ServoStyleSet::NoteStyleSheetsChanged()
+ServoStyleSet::ForceAllStyleDirty()
 {
   SetStylistStyleSheetsDirty();
   Servo_StyleSet_NoteStyleSheetsChanged(mRawSet.get(), mAuthorStyleDisabled);
 }
 
+void
+ServoStyleSet::RecordStyleSheetChange(
+    ServoStyleSheet* aSheet,
+    StyleSheet::ChangeType aChangeType)
+{
+  SetStylistStyleSheetsDirty();
+  switch (aChangeType) {
+    case StyleSheet::ChangeType::RuleAdded:
+    case StyleSheet::ChangeType::RuleRemoved:
+    case StyleSheet::ChangeType::RuleChanged:
+    case StyleSheet::ChangeType::ApplicableStateChanged:
+      // FIXME(emilio): We can presumably do better in a bunch of these.
+      return ForceAllStyleDirty();
+    case StyleSheet::ChangeType::Added:
+    case StyleSheet::ChangeType::Removed:
+      // Do nothing, we've already recorded the change in the AppendFoo methods,
+      // etc, and will act consequently.
+      return;
+  }
+}
+
 #ifdef DEBUG
 void
 ServoStyleSet::AssertTreeIsClean()
 {
   DocumentStyleRootIterator iter(mPresContext->Document());
   while (Element* root = iter.GetNextStyleRoot()) {
     Servo_AssertTreeIsClean(root);
   }
@@ -1078,17 +1093,18 @@ ServoStyleSet::EnsureUniqueInnerOnCSSShe
   mNeedsRestyleAfterEnsureUniqueInner = false;
   return res;
 }
 
 void
 ServoStyleSet::RebuildData()
 {
   ClearNonInheritingStyleContexts();
-  Servo_StyleSet_RebuildData(mRawSet.get());
+  Element* root = mPresContext->Document()->GetDocumentElement();
+  Servo_StyleSet_RebuildData(mRawSet.get(), root);
   mStylistState = StylistState::NotDirty;
 }
 
 void
 ServoStyleSet::ClearDataAndMarkDeviceDirty()
 {
   ClearNonInheritingStyleContexts();
   Servo_StyleSet_Clear(mRawSet.get());
@@ -1192,17 +1208,18 @@ ServoStyleSet::ResolveForDeclarations(
 
 void
 ServoStyleSet::UpdateStylist()
 {
   MOZ_ASSERT(StylistNeedsUpdate());
   if (mStylistState == StylistState::FullyDirty) {
     RebuildData();
   } else {
-    Servo_StyleSet_FlushStyleSheets(mRawSet.get());
+    Element* root = mPresContext->Document()->GetDocumentElement();
+    Servo_StyleSet_FlushStyleSheets(mRawSet.get(), root);
   }
   mStylistState = StylistState::NotDirty;
 }
 
 void
 ServoStyleSet::PrependSheetOfType(SheetType aType,
                                   ServoStyleSheet* aSheet)
 {

--- a/layout/style/ServoStyleSet.h
+++ b/layout/style/ServoStyleSet.h
@@ -100,28 +100,22 @@ public:
 
   ServoStyleSet();
   ~ServoStyleSet();
 
   void Init(nsPresContext* aPresContext);
   void BeginShutdown();
   void Shutdown();
 
-  void RecordStyleSheetChange(mozilla::ServoStyleSheet*, StyleSheet::ChangeType)
-  {
-    // TODO(emilio): Record which kind of changes have we handled, and act
-    // properly in InvalidateStyleForCSSRuleChanges instead of invalidating the
-    // whole document.
-    NoteStyleSheetsChanged();
-  }
+  void RecordStyleSheetChange(mozilla::ServoStyleSheet*, StyleSheet::ChangeType);
 
   void RecordShadowStyleChange(mozilla::dom::ShadowRoot* aShadowRoot) {
     // FIXME(emilio): When we properly support shadow dom we'll need to do
     // better.
-    NoteStyleSheetsChanged();
+    ForceAllStyleDirty();
   }
 
   bool StyleSheetsHaveChanged() const
   {
     return StylistNeedsUpdate();
   }
 
   void InvalidateStyleForCSSRuleChanges();
@@ -298,17 +292,17 @@ public:
    */
   void StyleSubtreeForReconstruct(dom::Element* aRoot);
 
   /**
    * Records that the contents of style sheets have changed since the last
    * restyle.  Calling this will ensure that the Stylist rebuilds its
    * selector maps.
    */
-  void NoteStyleSheetsChanged();
+  void ForceAllStyleDirty();
 
   /**
    * Helper for correctly calling RebuildStylist without paying the cost of an
    * extra function call in the common no-rebuild-needed case.
    */
   void UpdateStylistIfNeeded()
   {
     if (StylistNeedsUpdate()) {