--- a/layout/style/ServoBindings.cpp
+++ b/layout/style/ServoBindings.cpp
@@ -267,26 +267,25 @@ Gecko_MaybeCreateStyleChildrenIterator(R
 
 void
 Gecko_DropStyleChildrenIterator(StyleChildrenIteratorOwned aIterator)
 {
   MOZ_ASSERT(aIterator);
   delete aIterator;
 }
 
-bool
-Gecko_ElementHasBindingWithAnonymousContent(RawGeckoElementBorrowed aElement)
+nsIContent*
+Gecko_ElementBindingAnonymousContent(RawGeckoElementBorrowed aElement)
 {
-  if (!aElement->HasFlag(NODE_MAY_BE_IN_BINDING_MNGR)) {
-    return false;
+  MOZ_ASSERT(aElement->HasFlag(NODE_MAY_BE_IN_BINDING_MNGR));
+  nsBindingManager* manager = aElement->OwnerDoc()->BindingManager();
+  if (nsXBLBinding* binding = manager->GetBindingWithContent(aElement)) {
+    return binding->GetAnonymousContent();
   }
-
-  nsBindingManager* manager = aElement->OwnerDoc()->BindingManager();
-  nsXBLBinding* binding = manager->GetBindingWithContent(aElement);
-  return binding && binding->GetAnonymousContent();
+  return nullptr;
 }
 
 RawGeckoNodeBorrowed
 Gecko_GetNextStyleChild(StyleChildrenIteratorBorrowedMut aIterator)
 {
   MOZ_ASSERT(aIterator);
   return aIterator->GetNextChild();
 }

--- a/layout/style/ServoBindings.h
+++ b/layout/style/ServoBindings.h
@@ -153,17 +153,17 @@ void Gecko_LoadStyleSheet(mozilla::css::
 // first child. This generally works, but misses anonymous children, which we
 // want to traverse during styling. To support these cases, we create an
 // optional heap-allocated iterator for nodes that need it. If the creation
 // method returns null, Servo falls back to the aforementioned simpler (and
 // faster) sibling traversal.
 StyleChildrenIteratorOwnedOrNull Gecko_MaybeCreateStyleChildrenIterator(RawGeckoNodeBorrowed node);
 void Gecko_DropStyleChildrenIterator(StyleChildrenIteratorOwned it);
 RawGeckoNodeBorrowedOrNull Gecko_GetNextStyleChild(StyleChildrenIteratorBorrowedMut it);
-bool Gecko_ElementHasBindingWithAnonymousContent(RawGeckoElementBorrowed element);
+nsIContent* Gecko_ElementBindingAnonymousContent(RawGeckoElementBorrowed element);
 
 // Selector Matching.
 uint64_t Gecko_ElementState(RawGeckoElementBorrowed element);
 bool Gecko_IsTextNode(RawGeckoNodeBorrowed node);
 bool Gecko_IsRootElement(RawGeckoElementBorrowed element);
 bool Gecko_MatchesElement(mozilla::CSSPseudoClassType type, RawGeckoElementBorrowed element);
 nsIAtom* Gecko_LocalName(RawGeckoElementBorrowed element);
 nsIAtom* Gecko_Namespace(RawGeckoElementBorrowed element);

--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -582,16 +582,22 @@ pub trait TElement : Eq + PartialEq + De
     fn has_animation_restyle_hints(&self) -> bool {
         let data = match self.borrow_data() {
             Some(d) => d,
             None => return false,
         };
         return data.restyle.hint.has_animation_hint()
     }
 
+    /// Returns the anonymous content for the current element's XBL binding,
+    /// given if any.
+    ///
+    /// This is used in Gecko for XBL and shadow DOM.
+    fn xbl_binding_anonymous_content(&self) -> Option<Self::ConcreteNode>;
+
     /// Gets declarations from XBL bindings from the element. Only gecko element could have this.
     fn get_declarations_from_xbl_bindings<V>(&self,
                                              _pseudo_element: Option<&PseudoElement>,
                                              _applicable_declarations: &mut V)
                                              -> bool
         where V: Push<ApplicableDeclarationBlock> + VecLike<ApplicableDeclarationBlock> {
         false
     }

--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -31,17 +31,16 @@ use gecko::selector_parser::{SelectorImp
 use gecko::snapshot_helpers;
 use gecko_bindings::bindings;
 use gecko_bindings::bindings::{Gecko_DropStyleChildrenIterator, Gecko_MaybeCreateStyleChildrenIterator};
 use gecko_bindings::bindings::{Gecko_ElementState, Gecko_GetLastChild, Gecko_GetNextStyleChild};
 use gecko_bindings::bindings::{Gecko_IsRootElement, Gecko_MatchesElement, Gecko_Namespace};
 use gecko_bindings::bindings::{Gecko_SetNodeFlags, Gecko_UnsetNodeFlags};
 use gecko_bindings::bindings::Gecko_ClassOrClassList;
 use gecko_bindings::bindings::Gecko_ElementHasAnimations;
-use gecko_bindings::bindings::Gecko_ElementHasBindingWithAnonymousContent;
 use gecko_bindings::bindings::Gecko_ElementHasCSSAnimations;
 use gecko_bindings::bindings::Gecko_ElementHasCSSTransitions;
 use gecko_bindings::bindings::Gecko_GetActiveLinkAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetAnimationRule;
 use gecko_bindings::bindings::Gecko_GetExtraContentStyleDeclarations;
 use gecko_bindings::bindings::Gecko_GetHTMLPresentationAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetSMILOverrideDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetStyleAttrDeclarationBlock;
@@ -270,17 +269,20 @@ impl<'ln> TNode for GeckoNode<'ln> {
         if let Some(iter) = maybe_iter.into_owned_opt() {
             LayoutIterator(GeckoChildrenIterator::GeckoIterator(iter))
         } else {
             LayoutIterator(self.dom_children())
         }
     }
 
     fn children_and_traversal_children_might_differ(&self) -> bool {
-        self.as_element().map_or(false, |e| unsafe { Gecko_ElementHasBindingWithAnonymousContent(e.0) })
+        match self.as_element() {
+            Some(e) => e.xbl_binding_anonymous_content().is_some(),
+            None => false,
+        }
     }
 
     fn opaque(&self) -> OpaqueNode {
         let ptr: usize = self.0 as *const _ as usize;
         OpaqueNode(ptr)
     }
 
     fn debug_id(self) -> usize {
@@ -371,16 +373,20 @@ impl<'a> Iterator for GeckoChildrenItera
 /// A Simple wrapper over a non-null Gecko `nsXBLBinding` pointer.
 pub struct GeckoXBLBinding<'lb>(pub &'lb RawGeckoXBLBinding);
 
 impl<'lb> GeckoXBLBinding<'lb> {
     fn base_binding(&self) -> Option<GeckoXBLBinding> {
         unsafe { self.0.mNextBinding.mRawPtr.as_ref().map(GeckoXBLBinding) }
     }
 
+    fn anon_content(&self) -> *const nsIContent {
+        unsafe { self.0.mContent.raw::<nsIContent>() }
+    }
+
     fn inherits_style(&self) -> bool {
         unsafe { bindings::Gecko_XBLBinding_InheritsStyle(self.0) }
     }
 
     // Implements Gecko's nsXBLBinding::WalkRules().
     fn get_declarations_for<E, V>(&self,
                                   element: &E,
                                   pseudo_element: Option<&PseudoElement>,
@@ -1034,16 +1040,29 @@ impl<'le> TElement for GeckoElement<'le>
             current = element.get_xbl_binding_parent();
         }
 
         // If current has something, this means we cut off inheritance at some point in the
         // loop.
         current.is_some()
     }
 
+    fn xbl_binding_anonymous_content(&self) -> Option<GeckoNode<'le>> {
+        if self.flags() & (structs::NODE_MAY_BE_IN_BINDING_MNGR as u32) == 0 {
+            return None;
+        }
+
+        let anon_content = match self.get_xbl_binding() {
+            Some(binding) => binding.anon_content(),
+            None => return None,
+        };
+
+        unsafe { anon_content.as_ref().map(GeckoNode::from_content) }
+    }
+
     fn get_css_transitions_info(&self)
                                 -> HashMap<TransitionProperty, Arc<AnimationValue>> {
         use gecko_bindings::bindings::Gecko_ElementTransitions_EndValueAt;
         use gecko_bindings::bindings::Gecko_ElementTransitions_Length;
         use gecko_bindings::bindings::Gecko_ElementTransitions_PropertyAt;
 
         let collection_length =
             unsafe { Gecko_ElementTransitions_Length(self.0) };
@@ -1375,16 +1394,18 @@ impl<'le> PresentationalHintsSynthesizer
         }
     }
 }
 
 impl<'le> ::selectors::Element for GeckoElement<'le> {
     type Impl = SelectorImpl;
 
     fn parent_element(&self) -> Option<Self> {
+        // FIXME(emilio): This will need to jump across if the parent node is a
+        // shadow root to get the shadow host.
         let parent_node = self.as_node().parent_node();
         parent_node.and_then(|n| n.as_element())
     }
 
     fn pseudo_element_originating_element(&self) -> Option<Self> {
         debug_assert!(self.implemented_pseudo_element().is_some());
         self.closest_non_native_anonymous_ancestor()
     }

--- a/servo/components/style/invalidation/element/invalidator.rs
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -270,89 +270,141 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
         any_invalidated
     }
 
     fn invalidate_pseudo_element_or_nac(
         &mut self,
         child: E,
         invalidations: &InvalidationVector
     ) -> bool {
+        let mut sibling_invalidations = InvalidationVector::new();
+
+        let result = self.invalidate_child(
+            child,
+            invalidations,
+            &mut sibling_invalidations
+        );
+
+        // Roots of NAC subtrees can indeed generate sibling invalidations, but
+        // they can be just ignored, since they have no siblings.
+        debug_assert!(child.implemented_pseudo_element().is_none() ||
+                      sibling_invalidations.is_empty(),
+                      "pseudos can't generate sibling invalidations, since \
+                      using them in other position that isn't the \
+                      rightmost part of the selector is invalid \
+                      (for now at least)");
+
+        result
+    }
+
+    /// Invalidate a child and recurse down invalidating its descendants if
+    /// needed.
+    fn invalidate_child(
+        &mut self,
+        child: E,
+        invalidations: &InvalidationVector,
+        sibling_invalidations: &mut InvalidationVector,
+    ) -> bool {
         let mut child_data = child.mutate_data();
         let child_data = child_data.as_mut().map(|d| &mut **d);
 
         let mut child_invalidator = TreeStyleInvalidator::new(
             child,
             child_data,
             self.shared_context
         );
 
         let mut invalidations_for_descendants = InvalidationVector::new();
-        let mut sibling_invalidations = InvalidationVector::new();
+        let mut invalidated_child = false;
+
+        invalidated_child |=
+            child_invalidator.process_sibling_invalidations(
+                &mut invalidations_for_descendants,
+                sibling_invalidations,
+            );
+
+        invalidated_child |=
+            child_invalidator.process_descendant_invalidations(
+                invalidations,
+                &mut invalidations_for_descendants,
+                sibling_invalidations,
+            );
 
-        let invalidated = child_invalidator.process_descendant_invalidations(
-            invalidations,
-            &mut invalidations_for_descendants,
-            &mut sibling_invalidations,
+        // The child may not be a flattened tree child of the current element,
+        // but may be arbitrarily deep.
+        //
+        // Since we keep the traversal flags in terms of the flattened tree,
+        // we need to propagate it as appropriate.
+        if invalidated_child && child.parent_element() != Some(self.element) {
+            let mut current = child.traversal_parent();
+            while let Some(parent) = current.take() {
+                if parent == self.element {
+                    break;
+                }
+
+                unsafe { parent.set_dirty_descendants() };
+                current = parent.traversal_parent();
+            }
+        }
+
+        let invalidated_descendants = child_invalidator.invalidate_descendants(
+            &invalidations_for_descendants
         );
 
-        debug_assert!(child.implemented_pseudo_element().is_none() ||
-                      sibling_invalidations.is_empty(),
-                      "pseudos can't generate sibling invalidations, since \
-                      using them in other position that isn't the \
-                      rightmost part of the selector is invalid \
-                      (for now at least)");
-
-        // For NAC roots, we can ignore sibling invalidations, since they don't
-        // have any siblings.
-
-        let invalidated_children =
-            child_invalidator.invalidate_descendants(
-                &invalidations_for_descendants
-            );
-
-        invalidated || invalidated_children
+        invalidated_child || invalidated_descendants
     }
 
-    fn invalidate_pseudo_elements_and_nac(
+    fn invalidate_nac(
         &mut self,
-        invalidations: &InvalidationVector
+        invalidations: &InvalidationVector,
     ) -> bool {
-        let mut any_pseudo = false;
-
-        if let Some(before) = self.element.before_pseudo_element() {
-            any_pseudo |=
-                self.invalidate_pseudo_element_or_nac(before, invalidations);
-        }
-
-        if let Some(after) = self.element.after_pseudo_element() {
-            any_pseudo |=
-                self.invalidate_pseudo_element_or_nac(after, invalidations);
-        }
+        let mut any_nac_root = false;
 
         let element = self.element;
-        element.each_anonymous_content_child(|pseudo| {
-            let invalidated =
-                self.invalidate_pseudo_element_or_nac(pseudo, invalidations);
-
-            if invalidated {
-                let mut current = pseudo.traversal_parent();
-                while let Some(parent) = current.take() {
-                    if parent == self.element {
-                        break;
-                    }
-
-                    unsafe { parent.set_dirty_descendants() };
-                    current = parent.traversal_parent();
-                }
-            }
-
-            any_pseudo |= invalidated;
+        element.each_anonymous_content_child(|nac| {
+            any_nac_root |=
+                self.invalidate_pseudo_element_or_nac(nac, invalidations);
         });
 
-        any_pseudo
+        any_nac_root
+    }
+
+    // NB: It's important that this operates on DOM children, which is what
+    // selector-matching operates on.
+    fn invalidate_dom_descendants_of(
+        &mut self,
+        parent: E::ConcreteNode,
+        invalidations: &InvalidationVector,
+    ) -> bool {
+        let mut any_descendant = false;
+
+        let mut sibling_invalidations = InvalidationVector::new();
+        for child in parent.children() {
+            // TODO(emilio): We handle <xbl:children> fine, because they appear
+            // in selector-matching (note bug 1374247, though).
+            //
+            // This probably needs a shadow root check on `child` here, and
+            // recursing if that's the case.
+            //
+            // Also, what's the deal with HTML <content>? We don't need to
+            // support that for now, though we probably need to recurse into the
+            // distributed children too.
+            let child = match child.as_element() {
+                Some(e) => e,
+                None => continue,
+            };
+
+            any_descendant |= self.invalidate_child(
+                child,
+                invalidations,
+                &mut sibling_invalidations,
+            );
+        }
+
+        any_descendant
     }
 
     /// Given a descendant invalidation list, go through the current element's
     /// descendants, and invalidate style on them.
     fn invalidate_descendants(
         &mut self,
         invalidations: &InvalidationVector,
     ) -> bool {
@@ -368,82 +420,46 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
             None => return false,
             Some(ref data) => {
                 if data.restyle.hint.contains_subtree() {
                     return false;
                 }
             }
         }
 
-        let mut sibling_invalidations = InvalidationVector::new();
-
-        let mut any_children = false;
-
-        // NB: DOM children!
-        for child in self.element.as_node().children() {
-            let child = match child.as_element() {
-                Some(e) => e,
-                None => continue,
-            };
-
-            let mut child_data = child.get_data().map(|d| d.borrow_mut());
-            let child_data = child_data.as_mut().map(|d| &mut **d);
-
-            let mut child_invalidator = TreeStyleInvalidator::new(
-                child,
-                child_data,
-                self.shared_context
-            );
-
-            let mut invalidations_for_descendants = InvalidationVector::new();
-            let mut invalidated_child = false;
-
-            invalidated_child |=
-                child_invalidator.process_sibling_invalidations(
-                    &mut invalidations_for_descendants,
-                    &mut sibling_invalidations,
-                );
+        let mut any_descendant = false;
 
-            invalidated_child |=
-                child_invalidator.process_descendant_invalidations(
-                    invalidations,
-                    &mut invalidations_for_descendants,
-                    &mut sibling_invalidations,
-                );
-
-            // The child may not be a flattened tree child of the current
-            // element, but may be arbitrarily deep.
-            //
-            // Since we keep the traversal flags in terms of the flattened tree,
-            // we need to propagate it as appropriate.
-            if invalidated_child {
-                let mut current = child.traversal_parent();
-                while let Some(parent) = current.take() {
-                    if parent == self.element {
-                        break;
-                    }
-
-                    unsafe { parent.set_dirty_descendants() };
-                    current = parent.traversal_parent();
-                }
-            }
-
-            any_children |= invalidated_child;
-            any_children |= child_invalidator.invalidate_descendants(
-                &invalidations_for_descendants
-            );
+        if let Some(anon_content) = self.element.xbl_binding_anonymous_content() {
+            any_descendant |=
+                self.invalidate_dom_descendants_of(anon_content, invalidations);
         }
 
-        any_children |= self.invalidate_pseudo_elements_and_nac(invalidations);
+        // TODO(emilio): Having a list of invalidations just for pseudo-elements
+        // may save some work here and there.
+        if let Some(before) = self.element.before_pseudo_element() {
+            any_descendant |=
+                self.invalidate_pseudo_element_or_nac(before, invalidations);
+        }
 
-        if any_children {
+        let node = self.element.as_node();
+        any_descendant |=
+            self.invalidate_dom_descendants_of(node, invalidations);
+
+        if let Some(after) = self.element.after_pseudo_element() {
+            any_descendant |=
+                self.invalidate_pseudo_element_or_nac(after, invalidations);
+        }
+
+        any_descendant |= self.invalidate_nac(invalidations);
+
+        if any_descendant {
             unsafe { self.element.set_dirty_descendants() };
         }
 
-        any_children
+        any_descendant
     }
 
     /// Process the given sibling invalidations coming from our previous
     /// sibling.
     ///
     /// The sibling invalidations are somewhat special because they can be
     /// modified on the fly. New invalidations may be added and removed.
     ///