--- a/dom/xbl/nsBindingManager.cpp
+++ b/dom/xbl/nsBindingManager.cpp
@@ -1139,25 +1139,8 @@ nsBindingManager::FindNestedSingleInsert
     if (newParent == parent) {
       break;
     }
     parent = newParent;
   }
 
   return parent;
 }
-
-bool
-nsBindingManager::AnyBindingHasDocumentStateDependency(EventStates aStateMask)
-{
-  MOZ_ASSERT(mDocument->IsStyledByServo());
-
-  bool result = false;
-  EnumerateBoundContentBindings([&](nsXBLBinding* aBinding) {
-    ServoStyleSet* styleSet = aBinding->PrototypeBinding()->GetServoStyleSet();
-    if (styleSet && styleSet->HasDocumentStateDependency(aStateMask)) {
-      result = true;
-      return false;
-    }
-    return true;
-  });
-  return result;
-}

--- a/dom/xbl/nsBindingManager.h
+++ b/dom/xbl/nsBindingManager.h
@@ -168,17 +168,21 @@ public:
   // points and their insertion parents.
   void ClearInsertionPointsRecursively(nsIContent* aContent);
 
   // Called when the document is going away
   void DropDocumentReference();
 
   nsIContent* FindNestedSingleInsertionPoint(nsIContent* aContainer, bool* aMulti);
 
-  bool AnyBindingHasDocumentStateDependency(mozilla::EventStates aStateMask);
+  // Enumerate each bound content's bindings (including its base bindings)
+  // in mBoundContentSet. Return false from the callback to stop enumeration.
+  using BoundContentBindingCallback = std::function<bool (nsXBLBinding*)>;
+  bool EnumerateBoundContentBindings(
+    const BoundContentBindingCallback& aCallback) const;
 
 protected:
   nsIXPConnectWrappedJS* GetWrappedJS(nsIContent* aContent);
   nsresult SetWrappedJS(nsIContent* aContent, nsIXPConnectWrappedJS* aResult);
 
   // Called by ContentAppended and ContentInserted to handle a single child
   // insertion.  aChild must not be null.  aContainer may be null.
   // aAppend is true if this child is being appended, not inserted.
@@ -190,24 +194,17 @@ protected:
   void DoProcessAttachedQueue();
 
   // Post an event to process the attached queue.
   void PostProcessAttachedQueueEvent();
 
   // Call PostProcessAttachedQueueEvent() on a timer.
   static void PostPAQEventCallback(nsITimer* aTimer, void* aClosure);
 
-  // Enumerate each bound content's bindings (including its base bindings)
-  // in mBoundContentSet. Return false from the callback to stop enumeration.
-  using BoundContentBindingCallback = std::function<bool (nsXBLBinding*)>;
-  bool EnumerateBoundContentBindings(
-    const BoundContentBindingCallback& aCallback) const;
-
 // MEMBER VARIABLES
-protected:
   // A set of nsIContent that currently have a binding installed.
   nsAutoPtr<nsTHashtable<nsRefPtrHashKey<nsIContent> > > mBoundContentSet;
 
   // A mapping from nsIContent* to nsIXPWrappedJS* (an XPConnect
   // wrapper for JS objects).  For XBL bindings that implement XPIDL
   // interfaces, and that get referred to from C++, this table caches
   // the XPConnect wrapper for the binding.  By caching it, I control
   // its lifetime, and I prevent a re-wrap of the same script object

--- a/layout/base/PresShell.cpp
+++ b/layout/base/PresShell.cpp
@@ -4333,45 +4333,40 @@ PresShell::ContentStateChanged(nsIDocume
   if (mDidInitialize) {
     nsAutoCauseReflowNotifier crNotifier(this);
     mPresContext->RestyleManager()->ContentStateChanged(aContent, aStateMask);
     VERIFY_STYLE_TREE;
   }
 }
 
 void
-PresShell::DocumentStatesChanged(nsIDocument* aDocument,
-                                 EventStates aStateMask)
+PresShell::DocumentStatesChanged(nsIDocument* aDocument, EventStates aStateMask)
 {
   NS_PRECONDITION(!mIsDocumentGone, "Unexpected DocumentStatesChanged");
   NS_PRECONDITION(aDocument == mDocument, "Unexpected aDocument");
+  MOZ_ASSERT(!aStateMask.IsEmpty());
 
   if (mDidInitialize) {
-    Element* rootElement = aDocument->GetRootElement();
-    bool needRestyle = false;
     if (mStyleSet->IsServo()) {
-      needRestyle = rootElement &&
-        (mStyleSet->AsServo()->HasDocumentStateDependency(aStateMask) ||
-         aDocument->BindingManager()->
-           AnyBindingHasDocumentStateDependency(aStateMask));
-    } else {
-      needRestyle = mStyleSet->AsGecko()->
-        HasDocumentStateDependentStyle(rootElement, aStateMask);
-    }
-    if (needRestyle) {
-      mPresContext->RestyleManager()->PostRestyleEvent(rootElement,
-                                                       eRestyle_Subtree,
-                                                       nsChangeHint(0));
-      VERIFY_STYLE_TREE;
+      mStyleSet->AsServo()->InvalidateStyleForDocumentStateChanges(aStateMask);
+    } else if (Element* rootElement = aDocument->GetRootElement()) {
+      const bool needRestyle =
+        mStyleSet->AsGecko()->HasDocumentStateDependentStyle(
+          rootElement, aStateMask);
+      if (needRestyle) {
+        mPresContext->RestyleManager()->PostRestyleEvent(rootElement,
+                                                         eRestyle_Subtree,
+                                                         nsChangeHint(0));
+        VERIFY_STYLE_TREE;
+      }
     }
   }
 
   if (aStateMask.HasState(NS_DOCUMENT_STATE_WINDOW_INACTIVE)) {
-    nsIFrame* root = mFrameConstructor->GetRootFrame();
-    if (root) {
+    if (nsIFrame* root = mFrameConstructor->GetRootFrame()) {
       root->SchedulePaint();
     }
   }
 }
 
 void
 PresShell::AttributeWillChange(nsIDocument* aDocument,
                                Element*     aElement,

--- a/layout/style/ServoBindingList.h
+++ b/layout/style/ServoBindingList.h
@@ -35,16 +35,21 @@ SERVO_BINDING_FUNC(Servo_Element_GetPseu
                    ServoStyleContextStrong,
                    RawGeckoElementBorrowed node, size_t index)
 SERVO_BINDING_FUNC(Servo_Element_IsDisplayNone,
                    bool,
                    RawGeckoElementBorrowed element)
 SERVO_BINDING_FUNC(Servo_Element_IsPrimaryStyleReusedViaRuleNode,
                    bool,
                    RawGeckoElementBorrowed element)
+SERVO_BINDING_FUNC(Servo_InvalidateStyleForDocStateChanges,
+                   void,
+                   RawGeckoElementBorrowed root,
+                   const nsTArray<RawServoStyleSetBorrowed>* sets,
+                   uint64_t aStatesChanged)
 
 // Styleset and Stylesheet management
 SERVO_BINDING_FUNC(Servo_StyleSheet_FromUTF8Bytes,
                    RawServoStyleSheetContentsStrong,
                    mozilla::css::Loader* loader,
                    mozilla::ServoStyleSheet* gecko_stylesheet,
                    const uint8_t* data,
                    size_t data_len,

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -28,16 +28,17 @@
 #include "nsHTMLStyleSheet.h"
 #include "nsIAnonymousContentCreator.h"
 #include "nsIDocumentInlines.h"
 #include "nsMediaFeatures.h"
 #include "nsPrintfCString.h"
 #include "nsSMILAnimationController.h"
 #include "nsStyleContext.h"
 #include "nsStyleSet.h"
+#include "nsXBLPrototypeBinding.h"
 #include "gfxUserFontSet.h"
 
 using namespace mozilla;
 using namespace mozilla::dom;
 
 ServoStyleSet* ServoStyleSet::sInServoTraversal = nullptr;
 
 #ifdef DEBUG
@@ -219,16 +220,52 @@ ServoStyleSet::SetPresContext(nsPresCont
   if (rulesChanged != OriginFlags(0)) {
     MarkOriginsDirty(rulesChanged);
     return true;
   }
 
   return false;
 }
 
+void
+ServoStyleSet::InvalidateStyleForDocumentStateChanges(EventStates aStatesChanged)
+{
+  MOZ_ASSERT(IsMaster());
+  MOZ_ASSERT(mDocument);
+  MOZ_ASSERT(!aStatesChanged.IsEmpty());
+
+  nsPresContext* pc = GetPresContext();
+  if (!pc) {
+    return;
+  }
+
+  Element* root = mDocument->GetRootElement();
+  if (!root) {
+    return;
+  }
+
+  // TODO(emilio): It may be nicer to just invalidate stuff in a given subtree
+  // for XBL sheets / shadow DOM. Consider just enumerating bound content
+  // instead and run invalidation individually, passing mRawSet for the UA /
+  // User sheets.
+  AutoTArray<RawServoStyleSetBorrowed, 20> styleSets;
+  styleSets.AppendElement(mRawSet.get());
+  // FIXME(emilio): When bug 1425759 is fixed we need to enumerate ShadowRoots
+  // too.
+  mDocument->BindingManager()->EnumerateBoundContentBindings([&](nsXBLBinding* aBinding) {
+    if (ServoStyleSet* set = aBinding->PrototypeBinding()->GetServoStyleSet()) {
+      styleSets.AppendElement(set->RawSet());
+    }
+    return true;
+  });
+
+  Servo_InvalidateStyleForDocStateChanges(
+    root, &styleSets, aStatesChanged.ServoValue());
+}
+
 nsRestyleHint
 ServoStyleSet::MediumFeaturesChanged(bool aViewportChanged)
 {
   bool viewportUnitsUsed = false;
   bool rulesChanged = MediumFeaturesChangedRules(&viewportUnitsUsed);
 
   if (nsPresContext* pc = GetPresContext()) {
     if (mDocument->BindingManager()->MediumFeaturesChanged(pc)) {

--- a/layout/style/ServoStyleSet.h
+++ b/layout/style/ServoStyleSet.h
@@ -141,16 +141,19 @@ public:
   void RuleAdded(ServoStyleSheet&, css::Rule&);
   void RuleRemoved(ServoStyleSheet&, css::Rule&);
   void RuleChanged(ServoStyleSheet& aSheet, css::Rule* aRule);
 
   // All the relevant changes are handled in RuleAdded / RuleRemoved / etc, and
   // the relevant AppendSheet / RemoveSheet...
   void RecordStyleSheetChange(ServoStyleSheet*, StyleSheet::ChangeType) {}
 
+  // Runs style invalidation due to document state changes.
+  void InvalidateStyleForDocumentStateChanges(EventStates aStatesChanged);
+
   void RecordShadowStyleChange(dom::ShadowRoot* aShadowRoot) {
     // FIXME(emilio): When we properly support shadow dom we'll need to do
     // better.
     MarkOriginsDirty(OriginFlags::All);
   }
 
   bool StyleSheetsHaveChanged() const
   {

--- a/servo/components/style/invalidation/element/document_state.rs
+++ b/servo/components/style/invalidation/element/document_state.rs
@@ -25,30 +25,30 @@ impl Default for InvalidationMatchingDat
         Self {
             document_state: DocumentState::empty(),
         }
     }
 }
 
 /// An invalidation processor for style changes due to state and attribute
 /// changes.
-pub struct DocumentStateInvalidationProcessor<'a, E: TElement> {
+pub struct DocumentStateInvalidationProcessor<'a, E: TElement, I> {
     // TODO(emilio): We might want to just run everything for every possible
     // binding along with the document data, or just apply the XBL stuff to the
     // bound subtrees.
-    rules: &'a CascadeData,
+    rules: I,
     matching_context: MatchingContext<'a, E::Impl>,
     document_states_changed: DocumentState,
 }
 
-impl<'a, E: TElement> DocumentStateInvalidationProcessor<'a, E> {
+impl<'a, E: TElement, I> DocumentStateInvalidationProcessor<'a, E, I> {
     /// Creates a new DocumentStateInvalidationProcessor.
     #[inline]
     pub fn new(
-        rules: &'a CascadeData,
+        rules: I,
         document_states_changed: DocumentState,
         quirks_mode: QuirksMode,
     ) -> Self {
         let mut matching_context = MatchingContext::new_for_visited(
             MatchingMode::Normal,
             None,
             None,
             VisitedHandlingMode::AllLinksVisitedAndUnvisited,
@@ -58,32 +58,37 @@ impl<'a, E: TElement> DocumentStateInval
         matching_context.extra_data = InvalidationMatchingData {
             document_state: document_states_changed,
         };
 
         Self { rules, document_states_changed, matching_context }
     }
 }
 
-impl<'a, E: TElement> InvalidationProcessor<'a, E> for DocumentStateInvalidationProcessor<'a, E> {
+impl<'a, E, I> InvalidationProcessor<'a, E> for DocumentStateInvalidationProcessor<'a, E, I>
+where
+    E: TElement,
+    I: Iterator<Item = &'a CascadeData>,
+{
     fn collect_invalidations(
         &mut self,
         _element: E,
         self_invalidations: &mut InvalidationVector<'a>,
         _descendant_invalidations: &mut DescendantInvalidationLists<'a>,
         _sibling_invalidations: &mut InvalidationVector<'a>,
     ) -> bool {
-        let map = self.rules.invalidation_map();
+        for cascade_data in &mut self.rules {
+            let map = cascade_data.invalidation_map();
+            for dependency in &map.document_state_selectors {
+                if !dependency.state.intersects(self.document_states_changed) {
+                    continue;
+                }
 
-        for dependency in &map.document_state_selectors {
-            if !dependency.state.intersects(self.document_states_changed) {
-                continue;
+                self_invalidations.push(Invalidation::new(&dependency.selector, 0));
             }
-
-            self_invalidations.push(Invalidation::new(&dependency.selector, 0));
         }
 
         false
     }
 
     fn matching_context(&mut self) -> &mut MatchingContext<'a, E::Impl> {
         &mut self.matching_context
     }

--- a/servo/components/style/invalidation/element/invalidator.rs
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -529,16 +529,30 @@ where
 
         if self.processor.light_tree_only() {
             let node = self.element.as_node();
             return self.invalidate_dom_descendants_of(node, invalidations);
         }
 
         let mut any_descendant = false;
 
+        // NOTE(emilio): This should not not be needed for Shadow DOM for normal
+        // element state / attribute invalidations (it's needed for XBL though,
+        // due to the weird way the anon content there works (it doesn't block
+        // combinators).
+        //
+        // However, it's needed as of right now for document state invalidation,
+        // were we rely on iterating every element that ends up in the composed
+        // doc.
+        //
+        // Also, we could avoid having that special-case for document state
+        // invalidations if we invalidate for document state changes per
+        // subtree, though that's kind of annoying because we need to invalidate
+        // the shadow host subtree (to handle :host and ::slotted), and the
+        // actual shadow tree (to handle all other rules in the ShadowRoot).
         if let Some(anon_content) = self.element.xbl_binding_anonymous_content() {
             any_descendant |=
                 self.invalidate_dom_descendants_of(anon_content, invalidations);
         }
 
         if let Some(before) = self.element.before_pseudo_element() {
             any_descendant |=
                 self.invalidate_pseudo_element_or_nac(before, invalidations);

--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -4,16 +4,17 @@
 
 use cssparser::{ParseErrorKind, Parser, ParserInput};
 use cssparser::ToCss as ParserToCss;
 use env_logger::LogBuilder;
 use malloc_size_of::MallocSizeOfOps;
 use selectors::{Element, NthIndexCache};
 use selectors::matching::{MatchingContext, MatchingMode, matches_selector};
 use servo_arc::{Arc, ArcBorrow, RawOffsetArc};
+use smallvec::SmallVec;
 use std::cell::RefCell;
 use std::env;
 use std::fmt::Write;
 use std::iter;
 use std::mem;
 use std::ptr;
 use style::applicable_declarations::ApplicableDeclarationBlock;
 use style::context::{CascadeInputs, QuirksMode, SharedStyleContext, StyleContext};
@@ -1769,17 +1770,16 @@ pub unsafe extern "C" fn Servo_SelectorL
 
 #[no_mangle]
 pub unsafe extern "C" fn Servo_SelectorList_QueryAll(
     node: RawGeckoNodeBorrowed,
     selectors: RawServoSelectorListBorrowed,
     content_list: *mut structs::nsSimpleContentList,
     may_use_invalidation: bool,
 ) {
-    use smallvec::SmallVec;
     use std::borrow::Borrow;
     use style::dom_apis::{self, MayUseInvalidation, QueryAll};
 
     let node = GeckoNode(node);
     let selectors = ::selectors::SelectorList::from_ffi(selectors).borrow();
     let mut result = SmallVec::new();
 
     let may_use_invalidation =
@@ -2388,17 +2388,16 @@ pub extern "C" fn Servo_ComputedValues_E
     second: ServoComputedDataBorrowed
 ) -> bool {
     first.custom_properties == second.custom_properties
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_ComputedValues_GetStyleRuleList(values: ServoStyleContextBorrowed,
                                                         rules: RawGeckoServoStyleRuleListBorrowedMut) {
-    use smallvec::SmallVec;
 
     let rule_node = match values.rules {
         Some(ref r) => r,
         None => return,
     };
 
     let mut result = SmallVec::<[_; 10]>::new();
     for node in rule_node.self_and_ancestors() {
@@ -4926,16 +4925,50 @@ pub extern "C" fn Servo_ParseCounterStyl
     let mut parser = Parser::new(&mut input);
     match parser.parse_entirely(counter_style::parse_counter_style_name_definition) {
         Ok(name) => name.0.into_addrefed(),
         Err(_) => ptr::null_mut(),
     }
 }
 
 #[no_mangle]
+pub unsafe extern "C" fn Servo_InvalidateStyleForDocStateChanges(
+    root: RawGeckoElementBorrowed,
+    raw_style_sets: *const nsTArray<RawServoStyleSetBorrowed>,
+    states_changed: u64,
+) {
+    use style::invalidation::element::document_state::DocumentStateInvalidationProcessor;
+    use style::invalidation::element::invalidator::TreeStyleInvalidator;
+
+    let mut borrows = SmallVec::<[_; 20]>::with_capacity((*raw_style_sets).len());
+    for style_set in &**raw_style_sets {
+        borrows.push(PerDocumentStyleData::from_ffi(*style_set).borrow());
+    }
+    let root = GeckoElement(root);
+    let mut processor = DocumentStateInvalidationProcessor::new(
+        borrows.iter().flat_map(|b| b.stylist.iter_origins().map(|(data, _origin)| data)),
+        DocumentState::from_bits_truncate(states_changed),
+        root.as_node().owner_doc().quirks_mode(),
+    );
+
+    let result = TreeStyleInvalidator::new(
+        root,
+        /* stack_limit_checker = */ None,
+        &mut processor,
+    ).invalidate();
+
+    debug_assert!(!result.has_invalidated_siblings(), "How in the world?");
+    if result.has_invalidated_descendants() {
+        bindings::Gecko_NoteDirtySubtreeForInvalidation(root.0);
+    } else if result.has_invalidated_self() {
+        bindings::Gecko_NoteDirtyElement(root.0);
+    }
+}
+
+#[no_mangle]
 pub extern "C" fn Servo_ParseCounterStyleDescriptor(
     descriptor: nsCSSCounterDesc,
     value: *const nsACString,
     raw_extra_data: *mut URLExtraData,
     result: *mut nsCSSValue,
 ) -> bool {
     let value = unsafe { value.as_ref().unwrap().as_str_unchecked() };
     let url_data = unsafe {