Rewrite the style sharing candidate cache.

The style candidate cache had regressed a few times (see #12534), and my
intuition is that being able to disable all style sharing with a single rule in
the page is really unfortunate.

This commit redesigns the style sharing cache in order to be a optimistic cache,
but then reject candidates if they match different sibling-affecting selectors
in the page, for example.

So far the numbers have improved, but not so much as I'd wanted (~10%/20% of
non-incremental restyling time in general). The current implementation is really
dumb though (we recompute and re-match a lot of stuff), so we should be able to
optimise it quite a bit.

I have different ideas for improving it (that may or may not work), apart of the
low-hanging fruit like don't re-matching candidates all the time but I have to
measure the real impact.

Also, I need to verify it against try.

23 files changed, 462 insertions, 231 deletions

diff --git a/components/layout/Cargo.toml b/components/layout/Cargo.toml
index 1bddb701764..5ecfc91cf2c 100644
--- a/components/layout/Cargo.toml
+++ b/components/layout/Cargo.toml
@@ -33,7 +33,7 @@ range = {path = "../range"}
 rustc-serialize = "0.3"
 script_layout_interface = {path = "../script_layout_interface"}
 script_traits = {path = "../script_traits"}
-selectors = {version = "0.8", features = ["heap_size"]}
+selectors = {version = "0.9", features = ["heap_size"]}
 serde_macros = "0.8"
 smallvec = "0.1"
 string_cache = {version = "0.2.23", features = ["heap_size"]}
diff --git a/components/layout/traversal.rs b/components/layout/traversal.rs
index a8c94c52715..8e652dde8e9 100644
--- a/components/layout/traversal.rs
+++ b/components/layout/traversal.rs
@@ -13,7 +13,7 @@ use gfx::display_list::OpaqueNode;
 use script_layout_interface::restyle_damage::{BUBBLE_ISIZES, REFLOW, REFLOW_OUT_OF_FLOW, REPAINT, RestyleDamage};
 use script_layout_interface::wrapper_traits::{LayoutNode, ThreadSafeLayoutNode};
 use std::mem;
-use style::context::SharedStyleContext;
+use style::context::{LocalStyleContext, SharedStyleContext, StyleContext};
 use style::dom::TNode;
 use style::selector_impl::ServoSelectorImpl;
 use style::traversal::RestyleResult;
@@ -81,6 +81,10 @@ impl<'lc, N> DomTraversalContext<N> for RecalcStyleAndConstructFlows<'lc>
     fn process_postorder(&self, node: N) {
         construct_flows_at(&self.context, self.root, node);
     }
+
+    fn local_context(&self) -> &LocalStyleContext {
+        self.context.local_context()
+    }
 }
 
 /// A bottom-up, parallelizable traversal.
diff --git a/components/script/Cargo.toml b/components/script/Cargo.toml
index 2799b9bc4a4..135ead85732 100644
--- a/components/script/Cargo.toml
+++ b/components/script/Cargo.toml
@@ -65,7 +65,7 @@ regex = "0.1.43"
 rustc-serialize = "0.3"
 script_layout_interface = {path = "../script_layout_interface"}
 script_traits = {path = "../script_traits"}
-selectors = {version = "0.8", features = ["heap_size"]}
+selectors = {version = "0.9", features = ["heap_size"]}
 serde = "0.8"
 smallvec = "0.1"
 string_cache = {version = "0.2.23", features = ["heap_size", "unstable"]}
diff --git a/components/script/layout_wrapper.rs b/components/script/layout_wrapper.rs
index 7668c9ff272..13fcdc41df9 100644
--- a/components/script/layout_wrapper.rs
+++ b/components/script/layout_wrapper.rs
@@ -444,6 +444,11 @@ impl<'le> TElement for ServoLayoutElement<'le> {
     }
 }
 
+impl<'le> PartialEq for ServoLayoutElement<'le> {
+    fn eq(&self, other: &Self) -> bool {
+        self.as_node() == other.as_node()
+    }
+}
 
 impl<'le> ServoLayoutElement<'le> {
     fn from_layout_js(el: LayoutJS<Element>) -> ServoLayoutElement<'le> {
diff --git a/components/script_layout_interface/Cargo.toml b/components/script_layout_interface/Cargo.toml
index 6fb2a27786b..b2ec16ab3e6 100644
--- a/components/script_layout_interface/Cargo.toml
+++ b/components/script_layout_interface/Cargo.toml
@@ -27,7 +27,7 @@ plugins = {path = "../plugins"}
 profile_traits = {path = "../profile_traits"}
 range = {path = "../range"}
 script_traits = {path = "../script_traits"}
-selectors = {version = "0.8", features = ["heap_size"]}
+selectors = {version = "0.9", features = ["heap_size"]}
 string_cache = {version = "0.2.23", features = ["heap_size"]}
 style = {path = "../style"}
 url = {version = "1.2", features = ["heap_size"]}
diff --git a/components/servo/Cargo.lock b/components/servo/Cargo.lock
index 5b9fc065574..0e13d7bb742 100644
--- a/components/servo/Cargo.lock
+++ b/components/servo/Cargo.lock
@@ -1162,7 +1162,7 @@ dependencies = [
  "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "script_layout_interface 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_macros 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1931,7 +1931,7 @@ dependencies = [
  "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "script_layout_interface 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1968,7 +1968,7 @@ dependencies = [
  "profile_traits 0.0.1",
  "range 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
  "style 0.0.1",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2017,7 +2017,7 @@ dependencies = [
 
 [[package]]
 name = "selectors"
-version = "0.8.2"
+version = "0.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2239,7 +2239,7 @@ dependencies = [
  "plugins 0.0.1",
  "rand 0.3.14 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_macros 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2259,7 +2259,7 @@ dependencies = [
  "cssparser 0.5.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "euclid 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
  "style 0.0.1",
  "style_traits 0.0.1",
diff --git a/components/style/Cargo.toml b/components/style/Cargo.toml
index 21fcc15ede0..91693e26069 100644
--- a/components/style/Cargo.toml
+++ b/components/style/Cargo.toml
@@ -38,7 +38,7 @@ num-traits = "0.1.32"
 ordered-float = "0.2.2"
 rand = "0.3"
 rustc-serialize = "0.3"
-selectors = "0.8.2"
+selectors = "0.9"
 serde = {version = "0.8", optional = true}
 serde_macros = {version = "0.8", optional = true}
 smallvec = "0.1"
diff --git a/components/style/context.rs b/components/style/context.rs
index f1c5ac3f307..b5aa009dd25 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -7,6 +7,7 @@
 use animation::Animation;
 use app_units::Au;
 use dom::OpaqueNode;
+use dom::TElement;
 use error_reporting::ParseErrorReporter;
 use euclid::Size2D;
 use matching::{ApplicableDeclarationsCache, StyleSharingCandidateCache};
diff --git a/components/style/dom.rs b/components/style/dom.rs
index b6494b74160..3402912168a 100644
--- a/components/style/dom.rs
+++ b/components/style/dom.rs
@@ -201,7 +201,7 @@ pub trait PresentationalHintsSynthetizer {
         where V: Push<DeclarationBlock<Vec<PropertyDeclaration>>>;
 }
 
-pub trait TElement : Sized + Copy + Clone + ElementExt + PresentationalHintsSynthetizer {
+pub trait TElement : PartialEq + Sized + Copy + Clone + ElementExt + PresentationalHintsSynthetizer {
     type ConcreteNode: TNode<ConcreteElement = Self, ConcreteDocument = Self::ConcreteDocument>;
     type ConcreteDocument: TDocument<ConcreteNode = Self::ConcreteNode, ConcreteElement = Self>;
 
diff --git a/components/style/matching.rs b/components/style/matching.rs
index f3bd443ee43..d8b014af623 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -12,17 +12,19 @@ use cache::{LRUCache, SimpleHashCache};
 use cascade_info::CascadeInfo;
 use context::{StyleContext, SharedStyleContext};
 use data::PrivateStyleData;
-use dom::{TElement, TNode, TRestyleDamage};
+use dom::{TElement, TNode, TRestyleDamage, UnsafeNode};
 use properties::longhands::display::computed_value as display;
 use properties::{ComputedValues, PropertyDeclaration, cascade};
 use selector_impl::{ElementExt, TheSelectorImpl, PseudoElement};
 use selector_matching::{DeclarationBlock, Stylist};
 use selectors::bloom::BloomFilter;
+use selectors::matching::{StyleRelations, AFFECTED_BY_PSEUDO_ELEMENTS};
 use selectors::{Element, MatchAttr};
 use sink::ForgetfulSink;
 use smallvec::SmallVec;
 use std::borrow::Borrow;
 use std::collections::HashMap;
+use std::fmt;
 use std::hash::{BuildHasherDefault, Hash, Hasher};
 use std::slice::Iter;
 use std::sync::Arc;
@@ -178,155 +180,119 @@ impl ApplicableDeclarationsCache {
     }
 }
 
-/// An LRU cache of the last few nodes seen, so that we can aggressively try to reuse their styles.
+/// An LRU cache of the last few nodes seen, so that we can aggressively try to
+/// reuse their styles.
+///
+/// Note that this cache is flushed every time we steal work from the queue, so
+/// storing nodes here temporarily is safe.
+///
+/// NB: We store UnsafeNode's, but this is not unsafe. It's a shame being
+/// generic over elements is unfeasible (you can make compile style without much
+/// difficulty, but good luck with layout and all the types with assoc.
+/// lifetimes).
 pub struct StyleSharingCandidateCache {
-    cache: LRUCache<StyleSharingCandidate, ()>,
+    cache: LRUCache<UnsafeNode, ()>,
 }
 
-#[derive(Clone)]
-pub struct StyleSharingCandidate {
-    pub style: Arc<ComputedValues>,
-    pub parent_style: Arc<ComputedValues>,
-    pub local_name: Atom,
-    pub classes: Vec<Atom>,
-    pub namespace: Namespace,
-    pub common_style_affecting_attributes: CommonStyleAffectingAttributes,
-    pub link: bool,
-}
-
-impl PartialEq for StyleSharingCandidate {
-    fn eq(&self, other: &Self) -> bool {
-        arc_ptr_eq(&self.style, &other.style) &&
-            arc_ptr_eq(&self.parent_style, &other.parent_style) &&
-            self.local_name == other.local_name &&
-            self.classes == other.classes &&
-            self.link == other.link &&
-            self.namespace == other.namespace &&
-            self.common_style_affecting_attributes == other.common_style_affecting_attributes
-    }
-}
-
-impl StyleSharingCandidate {
-    /// Attempts to create a style sharing candidate from this node. Returns
-    /// the style sharing candidate or `None` if this node is ineligible for
-    /// style sharing.
-    #[allow(unsafe_code)]
-    fn new<N: TNode>(element: &N::ConcreteElement) -> Option<Self> {
-        let parent_element = match element.parent_element() {
-            None => return None,
-            Some(parent_element) => parent_element,
-        };
-
-        let style = unsafe {
-            match element.as_node().borrow_data_unchecked() {
-                None => return None,
-                Some(data_ref) => {
-                    match (*data_ref).style {
-                        None => return None,
-                        Some(ref data) => (*data).clone(),
-                    }
-                }
-            }
-        };
-        let parent_style = unsafe {
-            match parent_element.as_node().borrow_data_unchecked() {
-                None => return None,
-                Some(parent_data_ref) => {
-                    match (*parent_data_ref).style {
-                        None => return None,
-                        Some(ref data) => (*data).clone(),
-                    }
-                }
-            }
-        };
+#[derive(Clone, Debug)]
+pub enum CacheMiss {
+    Parent,
+    LocalName,
+    Namespace,
+    Link,
+    State,
+    IdAttr,
+    StyleAttr,
+    Class,
+    CommonStyleAffectingAttributes,
+    PresHints,
+    SiblingRules,
+    NonCommonAttrRules,
+}
 
-        if element.style_attribute().is_some() {
-            return None
+fn element_matches_candidate<E: TElement>(element: &E,
+                                          candidate: &E,
+                                          shared_context: &SharedStyleContext)
+                                          -> Result<Arc<ComputedValues>, CacheMiss> {
+    macro_rules! miss {
+        ($miss: ident) => {
+            return Err(CacheMiss::$miss);
         }
+    }
 
-        let mut classes = Vec::new();
-        element.each_class(|c| classes.push(c.clone()));
-        Some(StyleSharingCandidate {
-            style: style,
-            parent_style: parent_style,
-            local_name: element.get_local_name().clone(),
-            classes: classes,
-            link: element.is_link(),
-            namespace: (*element.get_namespace()).clone(),
-            common_style_affecting_attributes:
-                   create_common_style_affecting_attributes_from_element::<N::ConcreteElement>(&element)
-        })
-    }
-
-    pub fn can_share_style_with<E: TElement>(&self, element: &E) -> bool {
-        if element.get_local_name() != self.local_name.borrow() {
-            return false
-        }
+    if element.parent_element() != candidate.parent_element() {
+        miss!(Parent)
+    }
 
-        let mut num_classes = 0;
-        let mut classes_match = true;
-        element.each_class(|c| {
-            num_classes += 1;
-            // Note that we could do this check more cheaply if we decided to
-            // only consider class lists as equal if the orders match, since
-            // we could then index by num_classes instead of using .contains().
-            if classes_match && !self.classes.contains(c) {
-                classes_match = false;
-            }
-        });
-        if !classes_match || num_classes != self.classes.len() {
-            return false;
-        }
+    if *element.get_local_name() != *candidate.get_local_name() {
+        miss!(LocalName)
+    }
 
-        if element.get_namespace() != self.namespace.borrow() {
-            return false
-        }
+    if *element.get_namespace() != *candidate.get_namespace() {
+        miss!(Namespace)
+    }
 
-        let mut matching_rules = ForgetfulSink::new();
-        element.synthesize_presentational_hints_for_legacy_attributes(&mut matching_rules);
-        if !matching_rules.is_empty() {
-            return false;
-        }
+    if element.is_link() != candidate.is_link() {
+        miss!(Link)
+    }
 
-        // FIXME(pcwalton): It's probably faster to iterate over all the element's attributes and
-        // use the {common, rare}-style-affecting-attributes tables as lookup tables.
+    if element.get_state() != candidate.get_state() {
+        miss!(State)
+    }
 
-        for attribute_info in &common_style_affecting_attributes() {
-            match attribute_info.mode {
-                CommonStyleAffectingAttributeMode::IsPresent(flag) => {
-                    if self.common_style_affecting_attributes.contains(flag) !=
-                            element.has_attr(&ns!(), &attribute_info.atom) {
-                        return false
-                    }
-                }
-                CommonStyleAffectingAttributeMode::IsEqual(ref target_value, flag) => {
-                    let contains = self.common_style_affecting_attributes.contains(flag);
-                    if element.has_attr(&ns!(), &attribute_info.atom) {
-                        if !contains || !element.attr_equals(&ns!(), &attribute_info.atom, target_value) {
-                            return false
-                        }
-                    } else if contains {
-                        return false
-                    }
-                }
-            }
-        }
+    if element.get_id().is_some() {
+        miss!(IdAttr)
+    }
 
-        for attribute_name in &rare_style_affecting_attributes() {
-            if element.has_attr(&ns!(), attribute_name) {
-                return false
-            }
-        }
+    if element.style_attribute().is_some() {
+        miss!(StyleAttr)
+    }
 
-        if element.is_link() != self.link {
-            return false
-        }
+    if !have_same_class(element, candidate) {
+        miss!(Class)
+    }
 
-        // TODO(pcwalton): We don't support visited links yet, but when we do there will need to
-        // be some logic here.
+    if !have_same_common_style_affecting_attributes(element, candidate) {
+        miss!(CommonStyleAffectingAttributes)
+    }
 
-        true
+    if !have_same_presentational_hints(element, candidate) {
+        miss!(PresHints)
     }
+
+    if !match_same_sibling_affecting_rules(element, candidate, shared_context) {
+        miss!(SiblingRules)
+    }
+
+    if !match_same_not_common_style_affecting_attributes_rules(element, candidate, shared_context) {
+        miss!(NonCommonAttrRules)
+    }
+
+    let candidate_node = candidate.as_node();
+    let candidate_style = candidate_node.borrow_data().unwrap().style.as_ref().unwrap().clone();
+
+    Ok(candidate_style)
+}
+
+fn have_same_common_style_affecting_attributes<E: TElement>(element: &E,
+                                                            candidate: &E) -> bool {
+    // XXX probably could do something smarter. Also, the cache should
+    // precompute this for the parent. Just experimenting now though.
+    create_common_style_affecting_attributes_from_element(element) ==
+        create_common_style_affecting_attributes_from_element(candidate)
+}
+
+fn have_same_presentational_hints<E: TElement>(element: &E, candidate: &E) -> bool {
+    let mut first = vec![];
+    element.synthesize_presentational_hints_for_legacy_attributes(&mut first);
+    if cfg!(debug_assertions) {
+        let mut second = vec![];
+        candidate.synthesize_presentational_hints_for_legacy_attributes(&mut second);
+        debug_assert!(second.is_empty(),
+                      "Should never have inserted an element with preshints in the cache!");
+    }
+
+    first.is_empty()
 }
 
 bitflags! {
@@ -384,7 +350,32 @@ pub fn rare_style_affecting_attributes() -> [Atom; 3] {
     [ atom!("bgcolor"), atom!("border"), atom!("colspan") ]
 }
 
-static STYLE_SHARING_CANDIDATE_CACHE_SIZE: usize = 40;
+fn have_same_class<E: TElement>(element: &E, candidate: &E) -> bool {
+    // XXX Efficiency here, I'm only validating ideas.
+    let mut first = vec![];
+    let mut second = vec![];
+
+    element.each_class(|c| first.push(c.clone()));
+    candidate.each_class(|c| second.push(c.clone()));
+
+    first == second
+}
+
+fn match_same_not_common_style_affecting_attributes_rules<E: TElement>(element: &E,
+                                                                       candidate: &E,
+                                                                       ctx: &SharedStyleContext) -> bool {
+    // XXX Same here, could store in the cache an index with the matched rules,
+    // for example.
+    ctx.stylist.match_same_not_common_style_affecting_attributes_rules(element, candidate)
+}
+
+fn match_same_sibling_affecting_rules<E: TElement>(element: &E,
+                                                   candidate: &E,
+                                                   ctx: &SharedStyleContext) -> bool {
+    ctx.stylist.match_same_sibling_affecting_rules(element, candidate)
+}
+
+static STYLE_SHARING_CANDIDATE_CACHE_SIZE: usize = 8;
 
 impl StyleSharingCandidateCache {
     pub fn new() -> Self {
@@ -393,20 +384,45 @@ impl StyleSharingCandidateCache {
         }
     }
 
-    pub fn iter(&self) -> Iter<(StyleSharingCandidate, ())> {
+    pub fn iter(&self) -> Iter<(UnsafeNode, ())> {
         self.cache.iter()
     }
 
-    pub fn insert_if_possible<N: TNode>(&mut self, element: &N::ConcreteElement) {
-        match StyleSharingCandidate::new::<N>(element) {
-            None => {}
-            Some(candidate) => self.cache.insert(candidate, ())
+    pub fn insert_if_possible<E: TElement>(&mut self,
+                                           element: &E,
+                                           relations: StyleRelations) {
+        use selectors::matching::*; // For flags
+        use traversal::relations_are_shareable;
+
+        let parent = match element.parent_element() {
+            Some(element) => element,
+            None => {
+                debug!("Failing to insert to the cache: no parent element");
+                return;
+            }
+        };
+
+        // These are things we don't check in the candidate match because they
+        // are either uncommon or expensive.
+        if !relations_are_shareable(&relations) {
+            debug!("Failing to insert to the cache: {:?}", relations);
+            return;
         }
+
+        // XXX check transitions/animations and reject!
+        debug!("Inserting into cache: {:?} with parent {:?}",
+               element.as_node().to_unsafe(), parent.as_node().to_unsafe());
+
+        self.cache.insert(element.as_node().to_unsafe(), ())
     }
 
     pub fn touch(&mut self, index: usize) {
         self.cache.touch(index);
     }
+
+    pub fn clear(&mut self) {
+        self.cache.evict_all()
+    }
 }
 
 /// The results of attempting to share a style.
@@ -562,31 +578,19 @@ impl<N: TNode> PrivateMatchMethods for N {}
 
 trait PrivateElementMatchMethods: TElement {
     fn share_style_with_candidate_if_possible(&self,
-                                              parent_node: Option<Self::ConcreteNode>,
-                                              candidate: &StyleSharingCandidate)
+                                              parent_node: Self::ConcreteNode,
+                                              shared_context: &SharedStyleContext,
+                                              candidate: &Self)
                                               -> Option<Arc<ComputedValues>> {
-        let parent_node = match parent_node {
-            Some(ref parent_node) if parent_node.as_element().is_some() => parent_node,
-            Some(_) | None => return None,
-        };
-
-        let parent_data: Option<&PrivateStyleData> = unsafe {
-            parent_node.borrow_data_unchecked().map(|d| &*d)
-        };
+        debug_assert!(parent_node.is_element());
 
-        if let Some(parent_data_ref) = parent_data {
-            // Check parent style.
-            let parent_style = (*parent_data_ref).style.as_ref().unwrap();
-            if !arc_ptr_eq(parent_style, &candidate.parent_style) {
-                return None
-            }
-            // Check tag names, classes, etc.
-            if !candidate.can_share_style_with(self) {
-                return None
+        match element_matches_candidate(self, candidate, shared_context) {
+            Ok(cv) => Some(cv),
+            Err(error) => {
+                debug!("Cache miss: {:?}", error);
+                None
             }
-            return Some(candidate.style.clone())
         }
-        None
     }
 }
 
@@ -597,15 +601,19 @@ pub trait ElementMatchMethods : TElement {
                      stylist: &Stylist,
                      parent_bf: Option<&BloomFilter>,
                      applicable_declarations: &mut ApplicableDeclarations)
-                     -> bool {
+                     -> StyleRelations {
+        use traversal::relations_are_shareable;
         let style_attribute = self.style_attribute().as_ref();
 
-        applicable_declarations.normal_shareable =
+        let mut relations =
             stylist.push_applicable_declarations(self,
                                                  parent_bf,
                                                  style_attribute,
                                                  None,
                                                  &mut applicable_declarations.normal);
+
+        applicable_declarations.normal_shareable = relations_are_shareable(&relations);
+
         TheSelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
             stylist.push_applicable_declarations(self,
                                                  parent_bf,
@@ -614,8 +622,14 @@ pub trait ElementMatchMethods : TElement {
                                                  applicable_declarations.per_pseudo.entry(pseudo).or_insert(vec![]));
         });
 
-        applicable_declarations.normal_shareable &&
-        applicable_declarations.per_pseudo.values().all(|v| v.is_empty())
+        let has_pseudos =
+            applicable_declarations.per_pseudo.values().any(|v| !v.is_empty());
+
+        if has_pseudos {
+            relations |= AFFECTED_BY_PSEUDO_ELEMENTS;
+        }
+
+        relations
     }
 
     /// Attempts to share a style with another node. This method is unsafe because it depends on
@@ -624,6 +638,7 @@ pub trait ElementMatchMethods : TElement {
     unsafe fn share_style_if_possible(&self,
                                       style_sharing_candidate_cache:
                                         &mut StyleSharingCandidateCache,
+                                      shared_context: &SharedStyleContext,
                                       parent: Option<Self::ConcreteNode>)
                                       -> StyleSharingResult<<Self::ConcreteNode as TNode>::ConcreteRestyleDamage> {
         if opts::get().disable_share_style_cache {
@@ -633,12 +648,24 @@ pub trait ElementMatchMethods : TElement {
         if self.style_attribute().is_some() {
             return StyleSharingResult::CannotShare
         }
+
         if self.has_attr(&ns!(), &atom!("id")) {
             return StyleSharingResult::CannotShare
         }
 
-        for (i, &(ref candidate, ())) in style_sharing_candidate_cache.iter().enumerate() {
-            if let Some(shared_style) = self.share_style_with_candidate_if_possible(parent.clone(), candidate) {
+        let parent = match parent {
+            Some(parent) if parent.is_element() => parent,
+            _ => return StyleSharingResult::CannotShare,
+        };
+
+        let iter = style_sharing_candidate_cache.iter().map(|&(unsafe_node, ())| {
+            Self::ConcreteNode::from_unsafe(&unsafe_node).as_element().unwrap()
+        });
+
+        for (i, candidate) in iter.enumerate() {
+            if let Some(shared_style) = self.share_style_with_candidate_if_possible(parent,
+                                                                                    shared_context,
+                                                                                    &candidate) {
                 // Yay, cache hit. Share the style.
                 let node = self.as_node();
 
diff --git a/components/style/parallel.rs b/components/style/parallel.rs
index 532bde8540a..ba904866710 100644
--- a/components/style/parallel.rs
+++ b/components/style/parallel.rs
@@ -12,6 +12,8 @@ use dom::{OpaqueNode, TNode, UnsafeNode};
 use std::mem;
 use std::sync::atomic::Ordering;
 use traversal::{RestyleResult, DomTraversalContext};
+use traversal::{STYLE_SHARING_CACHE_HITS, STYLE_SHARING_CACHE_MISSES};
+use util::opts;
 use workqueue::{WorkQueue, WorkUnit, WorkerProxy};
 
 #[allow(dead_code)]
@@ -42,13 +44,28 @@ pub fn run_queue_with_custom_work_data_type<To, F, SharedContext: Sync>(
 pub fn traverse_dom<N, C>(root: N,
                           queue_data: &C::SharedContext,
                           queue: &mut WorkQueue<C::SharedContext, WorkQueueData>)
-                          where N: TNode, C: DomTraversalContext<N> {
+    where N: TNode,
+          C: DomTraversalContext<N>
+{
+    if opts::get().style_sharing_stats {
+        STYLE_SHARING_CACHE_HITS.store(0, Ordering::SeqCst);
+        STYLE_SHARING_CACHE_MISSES.store(0, Ordering::SeqCst);
+    }
     run_queue_with_custom_work_data_type(queue, |queue| {
         queue.push(WorkUnit {
             fun: top_down_dom::<N, C>,
             data: (Box::new(vec![root.to_unsafe()]), root.opaque()),
         });
     }, queue_data);
+
+    if opts::get().style_sharing_stats {
+        let hits = STYLE_SHARING_CACHE_HITS.load(Ordering::SeqCst);
+        let misses = STYLE_SHARING_CACHE_MISSES.load(Ordering::SeqCst);
+
+        println!("Style sharing stats:");
+        println!(" * Hits: {}", hits);
+        println!(" * Misses: {}", misses);
+    }
 }
 
 /// A parallel top-down DOM traversal.
@@ -102,6 +119,10 @@ fn top_down_dom<N, C>(unsafe_nodes: UnsafeNodeList,
         }
     }
 
+    // NB: In parallel traversal mode we have to purge the LRU cache in order to
+    // be able to access it without races.
+    context.local_context().style_sharing_candidate_cache.borrow_mut().clear();
+
     for chunk in discovered_child_nodes.chunks(CHUNK_SIZE) {
         proxy.push(WorkUnit {
             fun:  top_down_dom::<N, C>,
diff --git a/components/style/restyle_hints.rs b/components/style/restyle_hints.rs
index 4f1467c4584..e0688567550 100644
--- a/components/style/restyle_hints.rs
+++ b/components/style/restyle_hints.rs
@@ -6,6 +6,7 @@
 
 use element_state::*;
 use selector_impl::{ElementExt, TheSelectorImpl, NonTSPseudoClass, AttrValue};
+use selectors::matching::StyleRelations;
 use selectors::matching::matches_compound_selector;
 use selectors::parser::{AttrSelector, Combinator, CompoundSelector, SimpleSelector, SelectorImpl};
 use selectors::{Element, MatchAttr};
@@ -348,7 +349,11 @@ impl DependencySet {
         DependencySet { deps: Vec::new() }
     }
 
-    pub fn note_selector(&mut self, selector: Arc<CompoundSelector<TheSelectorImpl>>) {
+    pub fn len(&self) -> usize {
+        self.deps.len()
+    }
+
+    pub fn note_selector(&mut self, selector: &Arc<CompoundSelector<TheSelectorImpl>>) {
         let mut cur = selector;
         let mut combinator: Option<Combinator> = None;
         loop {
@@ -370,7 +375,7 @@ impl DependencySet {
             cur = match cur.next {
                 Some((ref sel, comb)) => {
                     combinator = Some(comb);
-                    sel.clone()
+                    sel
                 }
                 None => break,
             }
@@ -389,14 +394,19 @@ impl DependencySet {
                            -> RestyleHint
     where E: ElementExt + Clone
     {
+        debug!("About to calculate restyle hint for element. Deps: {}",
+               self.deps.len());
+
         let state_changes = snapshot.state().map_or_else(ElementState::empty, |old_state| current_state ^ old_state);
         let attrs_changed = snapshot.has_attrs();
         let mut hint = RestyleHint::empty();
         for dep in &self.deps {
             if state_changes.intersects(dep.sensitivities.states) || (attrs_changed && dep.sensitivities.attrs) {
                 let old_el: ElementWrapper<E> = ElementWrapper::new_with_snapshot(el.clone(), snapshot);
-                let matched_then = matches_compound_selector(&*dep.selector, &old_el, None, &mut false);
-                let matches_now = matches_compound_selector(&*dep.selector, el, None, &mut false);
+                let matched_then =
+                    matches_compound_selector(&*dep.selector, &old_el, None, &mut StyleRelations::empty());
+                let matches_now =
+                    matches_compound_selector(&*dep.selector, el, None, &mut StyleRelations::empty());
                 if matched_then != matches_now {
                     hint.insert(combinator_to_restyle_hint(dep.combinator));
                     if hint.is_all() {
diff --git a/components/style/selector_matching.rs b/components/style/selector_matching.rs
index 2ae05ce1d6f..f6aa5a65445 100644
--- a/components/style/selector_matching.rs
+++ b/components/style/selector_matching.rs
@@ -15,7 +15,9 @@ use selector_impl::{ElementExt, TheSelectorImpl, PseudoElement};
 use selectors::Element;
 use selectors::bloom::BloomFilter;
 use selectors::matching::DeclarationBlock as GenericDeclarationBlock;
-use selectors::matching::{Rule, SelectorMap};
+use selectors::matching::{AFFECTED_BY_STYLE_ATTRIBUTE, AFFECTED_BY_PRESENTATIONAL_HINTS};
+use selectors::matching::{Rule, SelectorMap, StyleRelations};
+use selectors::parser::Selector;
 use sink::Push;
 use smallvec::VecLike;
 use std::collections::HashMap;
@@ -26,7 +28,6 @@ use style_traits::viewport::ViewportConstraints;
 use stylesheets::{CSSRule, CSSRuleIteratorExt, Origin, Stylesheet};
 use viewport::{MaybeNew, ViewportRuleCascade};
 
-
 pub type DeclarationBlock = GenericDeclarationBlock<Vec<PropertyDeclaration>>;
 
 /// This structure holds all the selectors and device characteristics
@@ -76,6 +77,13 @@ pub struct Stylist {
 
     /// Selector dependencies used to compute restyle hints.
     state_deps: DependencySet,
+
+    /// Selectors in the page affecting siblings
+    sibling_affecting_selectors: Vec<Selector<TheSelectorImpl>>,
+
+    /// Selectors in the page matching elements with non-common style-affecting
+    /// attributes.
+    non_common_style_affecting_attributes_selectors: Vec<Selector<TheSelectorImpl>>,
 }
 
 impl Stylist {
@@ -93,6 +101,10 @@ impl Stylist {
             precomputed_pseudo_element_decls: HashMap::with_hasher(Default::default()),
             rules_source_order: 0,
             state_deps: DependencySet::new(),
+
+            // XXX remember resetting them!
+            sibling_affecting_selectors: vec![],
+            non_common_style_affecting_attributes_selectors: vec![]
         };
 
         TheSelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
@@ -120,6 +132,9 @@ impl Stylist {
         self.rules_source_order = 0;
         self.state_deps.clear();
 
+        self.sibling_affecting_selectors.clear();
+        self.non_common_style_affecting_attributes_selectors.clear();
+
         for ref stylesheet in TheSelectorImpl::get_user_or_user_agent_stylesheets().iter() {
             self.add_stylesheet(&stylesheet);
         }
@@ -178,8 +193,16 @@ impl Stylist {
                     append!(style_rule, normal);
                     append!(style_rule, important);
                     rules_source_order += 1;
+
                     for selector in &style_rule.selectors {
-                        self.state_deps.note_selector(selector.compound_selectors.clone());
+                        self.state_deps.note_selector(&selector.compound_selectors);
+                        if selector.affects_siblings() {
+                            self.sibling_affecting_selectors.push(selector.clone());
+                        }
+
+                        if selector.matches_non_common_style_affecting_attribute() {
+                            self.non_common_style_affecting_attributes_selectors.push(selector.clone());
+                        }
                     }
 
                     self.rules_source_order = rules_source_order;
@@ -202,6 +225,14 @@ impl Stylist {
             }
         }
 
+        debug!("Stylist stats:");
+        debug!(" - Got {} sibling-affecting selectors",
+               self.sibling_affecting_selectors.len());
+        debug!(" - Got {} non-common-style-attribute-affecting selectors",
+               self.non_common_style_affecting_attributes_selectors.len());
+        debug!(" - Got {} deps for style-hint calculation",
+               self.state_deps.len());
+
         TheSelectorImpl::each_precomputed_pseudo_element(|pseudo| {
             // TODO: Consider not doing this and just getting the rules on the
             // fly. It should be a bit slower, but we'd take rid of the
@@ -310,11 +341,11 @@ impl Stylist {
                                         parent_bf: Option<&BloomFilter>,
                                         style_attribute: Option<&PropertyDeclarationBlock>,
                                         pseudo_element: Option<&PseudoElement>,
-                                        applicable_declarations: &mut V)
-                                        -> bool
-                                        where E: Element<Impl=TheSelectorImpl> +
-                                                 PresentationalHintsSynthetizer,
-                                              V: Push<DeclarationBlock> + VecLike<DeclarationBlock> {
+                                        applicable_declarations: &mut V) -> StyleRelations
+        where E: Element<Impl=TheSelectorImpl> +
+                 PresentationalHintsSynthetizer,
+              V: Push<DeclarationBlock> + VecLike<DeclarationBlock>
+    {
         assert!(!self.is_device_dirty);
         assert!(style_attribute.is_none() || pseudo_element.is_none(),
                 "Style attributes do not apply to pseudo-elements");
@@ -327,65 +358,82 @@ impl Stylist {
             None => &self.element_map,
         };
 
-        let mut shareable = true;
+        let mut relations = StyleRelations::empty();
 
+        debug!("Determining if style is shareable: pseudo: {}", pseudo_element.is_some());
         // Step 1: Normal user-agent rules.
         map.user_agent.normal.get_all_matching_rules(element,
                                                      parent_bf,
                                                      applicable_declarations,
-                                                     &mut shareable);
+                                                     &mut relations);
+        debug!("UA normal: {:?}", relations);
 
         // Step 2: Presentational hints.
         let length = applicable_declarations.len();
         element.synthesize_presentational_hints_for_legacy_attributes(applicable_declarations);
         if applicable_declarations.len() != length {
             // Never share style for elements with preshints
-            shareable = false;
+            relations |= AFFECTED_BY_PRESENTATIONAL_HINTS;
         }
+        debug!("preshints: {:?}", relations);
 
         // Step 3: User and author normal rules.
         map.user.normal.get_all_matching_rules(element,
                                                parent_bf,
                                                applicable_declarations,
-                                               &mut shareable);
+                                               &mut relations);
+        debug!("user normal: {:?}", relations);
         map.author.normal.get_all_matching_rules(element,
                                                  parent_bf,
                                                  applicable_declarations,
-                                                 &mut shareable);
+                                                 &mut relations);
+        debug!("author normal: {:?}", relations);
 
         // Step 4: Normal style attributes.
-        style_attribute.map(|sa| {
-            shareable = false;
+        if let Some(ref sa)  = style_attribute {
+            relations |= AFFECTED_BY_STYLE_ATTRIBUTE;
             Push::push(
                 applicable_declarations,
-                GenericDeclarationBlock::from_declarations(sa.normal.clone()))
-        });
+                GenericDeclarationBlock::from_declarations(sa.normal.clone()));
+        }
+
+        debug!("style attr: {:?}", relations);
 
         // Step 5: Author-supplied `!important` rules.
         map.author.important.get_all_matching_rules(element,
                                                     parent_bf,
                                                     applicable_declarations,
-                                                    &mut shareable);
+                                                    &mut relations);
+
+        debug!("author important: {:?}", relations);
 
         // Step 6: `!important` style attributes.
-        style_attribute.map(|sa| {
-            shareable = false;
+        if let Some(ref sa) = style_attribute {
             Push::push(
                 applicable_declarations,
-                GenericDeclarationBlock::from_declarations(sa.important.clone()))
-        });
+                GenericDeclarationBlock::from_declarations(sa.important.clone()));
+        }
+
+        debug!("style attr important: {:?}", relations);
 
         // Step 7: User and UA `!important` rules.
         map.user.important.get_all_matching_rules(element,
                                                   parent_bf,
                                                   applicable_declarations,
-                                                  &mut shareable);
+                                                  &mut relations);
+
+        debug!("user important: {:?}", relations);
+
         map.user_agent.important.get_all_matching_rules(element,
                                                         parent_bf,
                                                         applicable_declarations,
-                                                        &mut shareable);
+                                                        &mut relations);
+
+        debug!("UA important: {:?}", relations);
+
+        debug!("push_applicable_declarations: shareable: {:?}", relations);
 
-        shareable
+        relations
     }
 
     #[inline]
@@ -398,6 +446,67 @@ impl Stylist {
         &self.animations
     }
 
+    pub fn match_same_not_common_style_affecting_attributes_rules<E>(&self,
+                                                                     element: &E,
+                                                                     candidate: &E) -> bool
+    where E: ElementExt
+    {
+        use selectors::matching::StyleRelations;
+        use selectors::matching::matches_compound_selector;
+        // XXX we can probably do better, the candidate should already know what
+        // rules it matches.
+        //
+        // XXX Could the bloom filter help here? Should be available.
+        for ref selector in self.non_common_style_affecting_attributes_selectors.iter() {
+            let element_matches = matches_compound_selector(&selector.compound_selectors,
+                                                            element,
+                                                            None,
+                                                            &mut StyleRelations::empty());
+            let candidate_matches = matches_compound_selector(&selector.compound_selectors,
+                                                              candidate,
+                                                              None,
+                                                              &mut StyleRelations::empty());
+
+            if element_matches != candidate_matches {
+                return false;
+            }
+        }
+
+        true
+    }
+
+    pub fn match_same_sibling_affecting_rules<E>(&self,
+                                                 element: &E,
+                                                 candidate: &E) -> bool
+    where E: ElementExt
+    {
+        use selectors::matching::StyleRelations;
+        use selectors::matching::matches_compound_selector;
+        // XXX we can probably do better, the candidate should already know what
+        // rules it matches.
+        //
+        // XXX The bloom filter would help here, and should be available.
+        for ref selector in self.sibling_affecting_selectors.iter() {
+            let element_matches = matches_compound_selector(&selector.compound_selectors,
+                                                            element,
+                                                            None,
+                                                            &mut StyleRelations::empty());
+
+            let candidate_matches = matches_compound_selector(&selector.compound_selectors,
+                                                              candidate,
+                                                              None,
+                                                              &mut StyleRelations::empty());
+
+            if element_matches != candidate_matches {
+                debug!("match_same_sibling_affecting_rules: Failure due to {:?}",
+                       selector.compound_selectors);
+                return false;
+            }
+        }
+
+        true
+    }
+
     pub fn compute_restyle_hint<E>(&self, element: &E,
                                    snapshot: &E::Snapshot,
                                    // NB: We need to pass current_state as an argument because
diff --git a/components/style/sequential.rs b/components/style/sequential.rs
index 334eecc5959..d3db166b446 100644
--- a/components/style/sequential.rs
+++ b/components/style/sequential.rs
@@ -35,5 +35,6 @@ pub fn traverse_dom<N, C>(root: N,
     if context.should_process(root) {
         doit::<N, C>(&context, root);
     }
+    // Clear the local LRU cache since we store stateful elements inside.
+    context.local_context().style_sharing_candidate_cache.borrow_mut().clear();
 }
-
diff --git a/components/style/traversal.rs b/components/style/traversal.rs
index 0a5fdd2cfcd..506e9e018f3 100644
--- a/components/style/traversal.rs
+++ b/components/style/traversal.rs
@@ -5,11 +5,14 @@
 //! Traversing the DOM tree; the bloom filter.
 
 use animation;
-use context::{SharedStyleContext, StyleContext};
+use context::{LocalStyleContext, SharedStyleContext, StyleContext};
 use dom::{OpaqueNode, TElement, TNode, TRestyleDamage, UnsafeNode};
 use matching::{ApplicableDeclarations, ElementMatchMethods, MatchMethods, StyleSharingResult};
 use selectors::bloom::BloomFilter;
+use selectors::matching::StyleRelations;
 use std::cell::RefCell;
+use std::sync::Arc;
+use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
 use tid::tid;
 use util::opts;
 use values::HasViewportPercentage;
@@ -27,6 +30,10 @@ pub enum RestyleResult {
     Stop,
 }
 
+/// Style sharing candidate cache stats. These are only used when
+/// `-Z style-sharing-stats` is given.
+pub static STYLE_SHARING_CACHE_HITS: AtomicUsize = ATOMIC_USIZE_INIT;
+pub static STYLE_SHARING_CACHE_MISSES: AtomicUsize = ATOMIC_USIZE_INIT;
 
 /// A pair of the bloom filter used for css selector matching, and the node to
 /// which it applies. This is used to efficiently do `Descendant` selector
@@ -149,7 +156,7 @@ pub fn remove_from_bloom_filter<'a, N, C>(context: &C, root: OpaqueNode, node: N
     };
 }
 
-pub trait DomTraversalContext<N: TNode>  {
+pub trait DomTraversalContext<N: TNode> {
     type SharedContext: Sync + 'static;
 
     fn new<'a>(&'a Self::SharedContext, OpaqueNode) -> Self;
@@ -191,6 +198,19 @@ pub trait DomTraversalContext<N: TNode>  {
             }
         }
     }
+
+    fn local_context(&self) -> &LocalStyleContext;
+}
+
+/// Determines the amount of relations where we're going to share style.
+#[inline]
+pub fn relations_are_shareable(relations: &StyleRelations) -> bool {
+    use selectors::matching::*;
+    !relations.intersects(AFFECTED_BY_ID_SELECTOR |
+                          AFFECTED_BY_PSEUDO_ELEMENTS | AFFECTED_BY_STATE |
+                          AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR |
+                          AFFECTED_BY_STYLE_ATTRIBUTE |
+                          AFFECTED_BY_PRESENTATIONAL_HINTS)
 }
 
 pub fn ensure_node_styled<'a, N, C>(node: N,
@@ -301,6 +321,7 @@ pub fn recalc_style_at<'a, N, C>(context: &'a C,
             Some(element) => {
                 unsafe {
                     element.share_style_if_possible(style_sharing_candidate_cache,
+                                                    context.shared_context(),
                                                     parent_opt.clone())
                 }
             },
@@ -312,20 +333,30 @@ pub fn recalc_style_at<'a, N, C>(context: &'a C,
             StyleSharingResult::CannotShare => {
                 let mut applicable_declarations = ApplicableDeclarations::new();
 
+                let relations;
                 let shareable_element = match node.as_element() {
                     Some(element) => {
+                        if opts::get().style_sharing_stats {
+                            STYLE_SHARING_CACHE_MISSES.fetch_add(1, Ordering::Relaxed);
+                        }
+
                         // Perform the CSS selector matching.
                         let stylist = &context.shared_context().stylist;
 
-                        if element.match_element(&**stylist,
-                                                 Some(&*bf),
-                                                 &mut applicable_declarations) {
+                        relations = element.match_element(&**stylist,
+                                                          Some(&*bf),
+                                                          &mut applicable_declarations);
+
+                        debug!("Result of selector matching: {:?}", relations);
+
+                        if relations_are_shareable(&relations) {
                             Some(element)
                         } else {
                             None
                         }
                     },
                     None => {
+                        relations = StyleRelations::empty();
                         if node.has_changed() {
                             node.set_restyle_damage(N::ConcreteRestyleDamage::rebuild_and_reflow())
                         }
@@ -342,11 +373,14 @@ pub fn recalc_style_at<'a, N, C>(context: &'a C,
 
                 // Add ourselves to the LRU cache.
                 if let Some(element) = shareable_element {
-                    style_sharing_candidate_cache.insert_if_possible::<'ln, N>(&element);
+                    style_sharing_candidate_cache.insert_if_possible(&element, relations);
                 }
             }
-            StyleSharingResult::StyleWasShared(index, damage, restyle_result_cascade) => {
-                restyle_result = restyle_result_cascade;
+            StyleSharingResult::StyleWasShared(index, damage, cached_restyle_result) => {
+                restyle_result = cached_restyle_result;
+                if opts::get().style_sharing_stats {
+                    STYLE_SHARING_CACHE_HITS.fetch_add(1, Ordering::Relaxed);
+                }
                 style_sharing_candidate_cache.touch(index);
                 node.set_restyle_damage(damage);
             }
diff --git a/components/util/opts.rs b/components/util/opts.rs
index a74c2b21352..209fe4bb500 100644
--- a/components/util/opts.rs
+++ b/components/util/opts.rs
@@ -172,6 +172,9 @@ pub struct Opts {
     /// Whether Style Sharing Cache is used
     pub disable_share_style_cache: bool,
 
+    /// Whether to show in stdout style sharing cache stats after a restyle.
+    pub style_sharing_stats: bool,
+
     /// Translate mouse input into touch events.
     pub convert_mouse_to_touch: bool,
 
@@ -275,6 +278,9 @@ pub struct DebugOptions {
     /// Disable the style sharing cache.
     pub disable_share_style_cache: bool,
 
+    /// Whether to show in stdout style sharing cache stats after a restyle.
+    pub style_sharing_stats: bool,
+
     /// Translate mouse input into touch events.
     pub convert_mouse_to_touch: bool,
 
@@ -331,6 +337,7 @@ impl DebugOptions {
                 "paint-flashing" => debug_options.paint_flashing = true,
                 "trace-layout" => debug_options.trace_layout = true,
                 "disable-share-style-cache" => debug_options.disable_share_style_cache = true,
+                "style-sharing-stats" => debug_options.style_sharing_stats = true,
                 "convert-mouse-to-touch" => debug_options.convert_mouse_to_touch = true,
                 "replace-surrogates" => debug_options.replace_surrogates = true,
                 "gc-profile" => debug_options.gc_profile = true,
@@ -512,6 +519,7 @@ pub fn default_opts() -> Opts {
         profile_script_events: false,
         profile_heartbeats: false,
         disable_share_style_cache: false,
+        style_sharing_stats: false,
         convert_mouse_to_touch: false,
         exit_after_load: false,
         no_native_titlebar: false,
@@ -817,6 +825,7 @@ pub fn from_cmdline_args(args: &[String]) -> ArgumentParsingResult {
         dump_layer_tree: debug_options.dump_layer_tree,
         relayout_event: debug_options.relayout_event,
         disable_share_style_cache: debug_options.disable_share_style_cache,
+        style_sharing_stats: debug_options.style_sharing_stats,
         convert_mouse_to_touch: debug_options.convert_mouse_to_touch,
         exit_after_load: opt_match.opt_present("x"),
         no_native_titlebar: do_not_use_native_titlebar,
diff --git a/ports/cef/Cargo.lock b/ports/cef/Cargo.lock
index fdf8e83b369..265f9d40900 100644
--- a/ports/cef/Cargo.lock
+++ b/ports/cef/Cargo.lock
@@ -1070,7 +1070,7 @@ dependencies = [
  "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "script_layout_interface 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_macros 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1783,7 +1783,7 @@ dependencies = [
  "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "script_layout_interface 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1820,7 +1820,7 @@ dependencies = [
  "profile_traits 0.0.1",
  "range 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
  "style 0.0.1",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1859,7 +1859,7 @@ dependencies = [
 
 [[package]]
 name = "selectors"
-version = "0.8.2"
+version = "0.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2122,7 +2122,7 @@ dependencies = [
  "plugins 0.0.1",
  "rand 0.3.14 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_macros 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
diff --git a/ports/geckolib/Cargo.lock b/ports/geckolib/Cargo.lock
index 6fe7b41c55f..51fbc37f50b 100644
--- a/ports/geckolib/Cargo.lock
+++ b/ports/geckolib/Cargo.lock
@@ -11,7 +11,7 @@ dependencies = [
  "libc 0.2.13 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "num_cpus 0.2.13 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "style 0.0.1",
  "style_traits 0.0.1",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -170,7 +170,7 @@ dependencies = [
  "gecko_bindings 0.0.1",
  "heapsize 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "libc 0.2.13 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -311,7 +311,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "selectors"
-version = "0.8.2"
+version = "0.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -367,7 +367,7 @@ dependencies = [
  "ordered-float 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.3.14 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "style_traits 0.0.1",
  "time 0.1.35 (registry+https://github.com/rust-lang/crates.io-index)",
diff --git a/ports/geckolib/Cargo.toml b/ports/geckolib/Cargo.toml
index 472401147d7..603d5d466ea 100644
--- a/ports/geckolib/Cargo.toml
+++ b/ports/geckolib/Cargo.toml
@@ -19,7 +19,7 @@ lazy_static = "0.2"
 libc = "0.2"
 log = {version = "0.3.5", features = ["release_max_level_info"]}
 num_cpus = "0.2.2"
-selectors = "0.8"
+selectors = "0.9"
 style = {path = "../../components/style", features = ["gecko"]}
 style_traits = {path = "../../components/style_traits"}
 url = "1.2"
diff --git a/ports/geckolib/string_cache/Cargo.toml b/ports/geckolib/string_cache/Cargo.toml
index 070c9968148..4fd3daf6dfa 100644
--- a/ports/geckolib/string_cache/Cargo.toml
+++ b/ports/geckolib/string_cache/Cargo.toml
@@ -14,5 +14,5 @@ cfg-if = "0.1.0"
 gecko_bindings = {version = "0.0.1", path = "../gecko_bindings"}
 heapsize = "0.3.5"
 libc = "0.2"
-selectors = "0.8"
+selectors = "0.9"
 serde = "0.8"
diff --git a/ports/geckolib/traversal.rs b/ports/geckolib/traversal.rs
index 50aa40dbd79..118c4688c83 100644
--- a/ports/geckolib/traversal.rs
+++ b/ports/geckolib/traversal.rs
@@ -4,7 +4,7 @@
 
 use context::StandaloneStyleContext;
 use std::mem;
-use style::context::SharedStyleContext;
+use style::context::{LocalStyleContext, SharedStyleContext, StyleContext};
 use style::dom::OpaqueNode;
 use style::traversal::RestyleResult;
 use style::traversal::{DomTraversalContext, recalc_style_at};
@@ -42,4 +42,8 @@ impl<'lc, 'ln> DomTraversalContext<GeckoNode<'ln>> for RecalcStyleOnly<'lc> {
 
     /// We don't use the post-order traversal for anything.
     fn needs_postorder_traversal(&self) -> bool { false }
+
+    fn local_context(&self) -> &LocalStyleContext {
+        self.context.local_context()
+    }
 }
diff --git a/ports/geckolib/wrapper.rs b/ports/geckolib/wrapper.rs
index 78417d5fad8..62fc84a36fe 100644
--- a/ports/geckolib/wrapper.rs
+++ b/ports/geckolib/wrapper.rs
@@ -459,6 +459,12 @@ impl<'le> TElement for GeckoElement<'le> {
     }
 }
 
+impl<'le> PartialEq for GeckoElement<'le> {
+    fn eq(&self, other: &Self) -> bool {
+        self.element == other.element
+    }
+}
+
 impl<'le> PresentationalHintsSynthetizer for GeckoElement<'le> {
     fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, _hints: &mut V)
         where V: Push<DeclarationBlock<Vec<PropertyDeclaration>>>
diff --git a/tests/unit/style/Cargo.toml b/tests/unit/style/Cargo.toml
index 3d048e4f070..333ccc2574a 100644
--- a/tests/unit/style/Cargo.toml
+++ b/tests/unit/style/Cargo.toml
@@ -14,7 +14,7 @@ app_units = "0.3"
 cssparser = {version = "0.5.7", features = ["heap_size"]}
 euclid = "0.9"
 rustc-serialize = "0.3"
-selectors = {version = "0.8", features = ["heap_size"]}
+selectors = {version = "0.9", features = ["heap_size"]}
 string_cache = {version = "0.2.23", features = ["heap_size"]}
 style = {path = "../../../components/style"}
 style_traits = {path = "../../../components/style_traits"}