--- a/servo/components/layout_thread/dom_wrapper.rs
+++ b/servo/components/layout_thread/dom_wrapper.rs
@@ -146,20 +146,20 @@ impl<'ln> NodeInfo for ServoLayoutNode<'
         }
     }
 
     fn is_text_node(&self) -> bool {
         self.script_type_id() == NodeTypeId::CharacterData(CharacterDataTypeId::Text)
     }
 }
 
-#[derive(Clone, Copy)]
+#[derive(Clone, Copy, PartialEq)]
 enum Impossible { }
 
-#[derive(Clone, Copy)]
+#[derive(Clone, Copy, PartialEq)]
 pub struct ShadowRoot<'lr>(Impossible, PhantomData<&'lr ()>);
 
 impl<'lr> TShadowRoot for ShadowRoot<'lr> {
     type ConcreteNode = ServoLayoutNode<'lr>;
 
     fn as_node(&self) -> Self::ConcreteNode {
         match self.0 { }
     }

--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -316,17 +316,17 @@ fn fmt_subtree<F, N: TNode>(f: &mut fmt:
             fmt_subtree(f, stringify, kid, indent + 1)?;
         }
     }
 
     Ok(())
 }
 
 /// The ShadowRoot trait.
-pub trait TShadowRoot : Sized + Copy + Clone {
+pub trait TShadowRoot : Sized + Copy + Clone + PartialEq {
     /// The concrete node type.
     type ConcreteNode: TNode<ConcreteShadowRoot = Self>;
 
     /// Get this ShadowRoot as a node.
     fn as_node(&self) -> Self::ConcreteNode;
 
     /// Get the shadow host that hosts this ShadowRoot.
     fn host(&self) -> <Self::ConcreteNode as TNode>::ConcreteElement;
@@ -385,25 +385,16 @@ pub trait TElement
         while let Some(parent) = curr.traversal_parent() {
             depth += 1;
             curr = parent;
         }
 
         depth
     }
 
-    /// The style scope of this element is a node that represents which rules
-    /// apply to the element.
-    ///
-    /// In Servo, where we don't know about Shadow DOM or XBL, the style scope
-    /// is always the document.
-    fn style_scope(&self) -> Self::ConcreteNode {
-        self.as_node().owner_doc().as_node()
-    }
-
     /// Get this node's parent element from the perspective of a restyle
     /// traversal.
     fn traversal_parent(&self) -> Option<Self> {
         self.as_node().traversal_parent()
     }
 
     /// Get this node's children from the perspective of a restyle traversal.
     fn traversal_children(&self) -> LayoutIterator<Self::TraversalChildrenIterator>;
@@ -743,16 +734,19 @@ pub trait TElement
     }
 
     /// The shadow root this element is a host of.
     fn shadow_root(&self) -> Option<<Self::ConcreteNode as TNode>::ConcreteShadowRoot>;
 
     /// The shadow root which roots the subtree this element is contained in.
     fn containing_shadow(&self) -> Option<<Self::ConcreteNode as TNode>::ConcreteShadowRoot>;
 
+    /// XBL hack for style sharing. :(
+    fn has_same_xbl_proto_binding_as(&self, _other: Self) -> bool { true }
+
     /// Return the element which we can use to look up rules in the selector
     /// maps.
     ///
     /// This is always the element itself, except in the case where we are an
     /// element-backed pseudo-element, in which case we return the originating
     /// element.
     fn rule_hash_target(&self) -> Self {
         if self.implemented_pseudo_element().is_some() {

--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -130,16 +130,23 @@ impl<'ld> TDocument for GeckoDocument<'l
         }
     }
 }
 
 /// A simple wrapper over `ShadowRoot`.
 #[derive(Clone, Copy)]
 pub struct GeckoShadowRoot<'lr>(pub &'lr structs::ShadowRoot);
 
+impl<'lr> PartialEq for GeckoShadowRoot<'lr> {
+    #[inline]
+    fn eq(&self, other: &Self) -> bool {
+        self.0 as *const _ == other.0 as *const _
+    }
+}
+
 impl<'lr> TShadowRoot for GeckoShadowRoot<'lr> {
     type ConcreteNode = GeckoNode<'lr>;
 
     #[inline]
     fn as_node(&self) -> Self::ConcreteNode {
         GeckoNode(&self.0._base._base._base._base)
     }
 
@@ -1035,39 +1042,16 @@ impl<'le> TElement for GeckoElement<'le>
     fn before_pseudo_element(&self) -> Option<Self> {
         self.before_or_after_pseudo(/* is_before = */ true)
     }
 
     fn after_pseudo_element(&self) -> Option<Self> {
         self.before_or_after_pseudo(/* is_before = */ false)
     }
 
-    /// Ensure this accurately represents the rules that an element may ever
-    /// match, even in the native anonymous content case.
-    fn style_scope(&self) -> Self::ConcreteNode {
-        if self.implemented_pseudo_element().is_some() {
-            return self.closest_non_native_anonymous_ancestor().unwrap().style_scope();
-        }
-
-        if self.is_in_native_anonymous_subtree() {
-            return self.as_node().owner_doc().as_node();
-        }
-
-        if self.xbl_binding().is_some() || self.shadow_root().is_some() {
-            return self.as_node();
-        }
-
-        if let Some(parent) = self.xbl_binding_parent() {
-            return parent.as_node();
-        }
-
-        self.as_node().owner_doc().as_node()
-    }
-
-
     #[inline]
     fn is_html_element(&self) -> bool {
         self.namespace_id() == (structs::root::kNameSpaceID_XHTML as i32)
     }
 
     /// Return the list of slotted nodes of this node.
     #[inline]
     fn slotted_nodes(&self) -> &[Self::ConcreteNode] {
@@ -1103,18 +1087,26 @@ impl<'le> TElement for GeckoElement<'le>
     }
 
     #[inline]
     fn containing_shadow(&self) -> Option<GeckoShadowRoot<'le>> {
         let slots = self.extended_slots()?;
         unsafe { slots._base.mContainingShadow.mRawPtr.as_ref().map(GeckoShadowRoot) }
     }
 
-    /// Execute `f` for each anonymous content child element (apart from
-    /// ::before and ::after) whose originating element is `self`.
+    fn has_same_xbl_proto_binding_as(&self, other: Self) -> bool {
+        match (self.xbl_binding(), other.xbl_binding()) {
+            (None, None) => true,
+            (Some(a), Some(b)) => {
+                a.0.mPrototypeBinding == b.0.mPrototypeBinding
+            }
+            _ => false,
+        }
+    }
+
     fn each_anonymous_content_child<F>(&self, mut f: F)
     where
         F: FnMut(Self),
     {
         let array: *mut structs::nsTArray<*mut nsIContent> =
             unsafe { bindings::Gecko_GetAnonymousContentForElement(self.0) };
 
         if array.is_null() {

--- a/servo/components/style/sharing/mod.rs
+++ b/servo/components/style/sharing/mod.rs
@@ -674,33 +674,51 @@ impl<E: TElement> StyleSharingCache<E> {
             return None;
         }
 
         if target.is_link() != candidate.element.is_link() {
             trace!("Miss: Link");
             return None;
         }
 
-        // Note that in the XBL case, we should be able to assert that the
-        // scopes are different, since two elements with different XBL bindings
-        // need to necessarily have different style (and thus children of them
-        // would never pass the parent check).
-        if target.element.style_scope() != candidate.element.style_scope() {
-            trace!("Miss: Different style scopes");
+        // If two elements belong to different shadow trees, different rules may
+        // apply to them, from the respective trees.
+        if target.element.containing_shadow() != candidate.element.containing_shadow() {
+            trace!("Miss: Different containing shadow roots");
+            return None;
+        }
+
+        // Note that in theory we shouldn't need this XBL check. However, XBL is
+        // absolutely broken in all sorts of ways.
+        //
+        // A style change that changes which XBL binding applies to an element
+        // arrives there, with the element still having the old prototype
+        // binding attached. And thus we try to match revalidation selectors
+        // with the old XBL binding, because we can't look at the new ones of
+        // course. And that causes us to revalidate with the wrong selectors and
+        // hit assertions.
+        //
+        // Other than this, we don't need anything else like the containing XBL
+        // binding parent or what not, since two elements with different XBL
+        // bindings will necessarily end up with different style.
+        if !target.element.has_same_xbl_proto_binding_as(candidate.element) {
+            trace!("Miss: Different proto bindings");
             return None;
         }
 
         // If the elements are not assigned to the same slot they could match
         // different ::slotted() rules in the slot scope.
         //
         // If two elements are assigned to different slots, even within the same
         // shadow root, they could match different rules, due to the slot being
         // assigned to yet another slot in another shadow root.
         if target.element.assigned_slot() != candidate.element.assigned_slot() {
-            trace!("Miss: Different style scopes");
+            // TODO(emilio): We could have a look at whether the shadow roots
+            // actually have slotted rules and such.
+            trace!("Miss: Different assigned slots");
             return None;
         }
 
         if target.matches_user_and_author_rules() !=
             candidate.element.matches_user_and_author_rules() {
             trace!("Miss: User and Author Rules");
             return None;
         }