servo: Merge #12668 - Rewrite the style sharing candidate cache (from emilio:style-cache); r=SimonSapin,pcwalton
authorEmilio Cobos Álvarez <ecoal95@gmail.com>
Wed, 17 Aug 2016 16:34:30 -0500
changeset 339514 53148dde6135ef48a1035b82c1b5dfbcbc77f79f
parent 339513 1cf3070fd052a90eb21bbe986f2aaccec8047887
child 339515 3967a95755b1b7917a6cd3d7d61ffb71274e957c
push id31307
push usergszorc@mozilla.com
push dateSat, 04 Feb 2017 00:59:06 +0000
treeherdermozilla-central@94079d43835f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersSimonSapin, pcwalton
servo: Merge #12668 - Rewrite the style sharing candidate cache (from emilio:style-cache); r=SimonSapin,pcwalton <!-- Please describe your changes on the following line: --> See the first commit's description for a bit of background. I'm making the PR in this state just to verify against try I've handled all cases of possibly incorrect sharing and, if not, fix it. --- <!-- Thank you for contributing to Servo! Please replace each `[ ]` by `[X]` when the step is complete, and replace `__` with appropriate data: --> - [x] `./mach build -d` does not report any errors - [x] `./mach test-tidy` does not report any errors - [x] These changes fix #12534 <!-- Either: --> - [x] There are tests for these changes OR <!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. --> Source-Repo: https://github.com/servo/servo Source-Revision: ec7efff14bf775d400ae768d8cb4ba1dac88ab59
servo/components/layout/Cargo.toml
servo/components/layout/traversal.rs
servo/components/script/Cargo.toml
servo/components/script/layout_wrapper.rs
servo/components/script_layout_interface/Cargo.toml
servo/components/servo/Cargo.lock
servo/components/style/Cargo.toml
servo/components/style/cache.rs
servo/components/style/dom.rs
servo/components/style/matching.rs
servo/components/style/parallel.rs
servo/components/style/restyle_hints.rs
servo/components/style/selector_matching.rs
servo/components/style/sequential.rs
servo/components/style/traversal.rs
servo/components/util/opts.rs
servo/ports/cef/Cargo.lock
servo/ports/geckolib/Cargo.lock
servo/ports/geckolib/Cargo.toml
servo/ports/geckolib/string_cache/Cargo.toml
servo/ports/geckolib/traversal.rs
servo/ports/geckolib/wrapper.rs
servo/tests/unit/style/Cargo.toml
--- a/servo/components/layout/Cargo.toml
+++ b/servo/components/layout/Cargo.toml
@@ -28,17 +28,17 @@ msg = {path = "../msg"}
 net_traits = {path = "../net_traits"}
 ordered-float = "0.2.2"
 plugins = {path = "../plugins"}
 profile_traits = {path = "../profile_traits"}
 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"]}
 style = {path = "../style"}
 style_traits = {path = "../style_traits"}
 unicode-bidi = "0.2"
 unicode-script = {version = "0.1", features = ["harfbuzz"]}
 url = {version = "1.2", features = ["heap_size"]}
--- a/servo/components/layout/traversal.rs
+++ b/servo/components/layout/traversal.rs
@@ -8,17 +8,17 @@ use construct::FlowConstructor;
 use context::{LayoutContext, SharedLayoutContext};
 use display_list_builder::DisplayListBuildState;
 use flow::{CAN_BE_FRAGMENTED, Flow, ImmutableFlowUtils, PostorderFlowTraversal};
 use flow::{PreorderFlowTraversal, self};
 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;
 use style::traversal::{DomTraversalContext, remove_from_bloom_filter, recalc_style_at};
 use util::opts;
 use wrapper::{LayoutNodeLayoutData, ThreadSafeLayoutNodeHelpers};
 
 pub struct RecalcStyleAndConstructFlows<'lc> {
@@ -76,16 +76,20 @@ impl<'lc, N> DomTraversalContext<N> for 
         node.initialize_data();
 
         recalc_style_at(&self.context, self.root, node)
     }
 
     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.
 pub trait PostorderNodeMutTraversal<ConcreteThreadSafeLayoutNode: ThreadSafeLayoutNode> {
     /// The operation to perform. Return true to continue or false to stop.
     fn process(&mut self, node: &ConcreteThreadSafeLayoutNode);
 }
 
--- a/servo/components/script/Cargo.toml
+++ b/servo/components/script/Cargo.toml
@@ -60,17 +60,17 @@ profile_traits = {path = "../profile_tra
 rand = "0.3"
 range = {path = "../range"}
 ref_filter_map = "1.0"
 ref_slice = "1.0"
 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"]}
 style = {path = "../style"}
 time = "0.1.12"
 url = {version = "1.2", features = ["heap_size", "query_encoding"]}
 util = {path = "../util"}
 uuid = {version = "0.3", features = ["v4"]}
--- a/servo/components/script/layout_wrapper.rs
+++ b/servo/components/script/layout_wrapper.rs
@@ -439,16 +439,21 @@ impl<'le> TElement for ServoLayoutElemen
     }
 
     #[inline]
     fn attr_equals(&self, namespace: &Namespace, attr: &Atom, val: &Atom) -> bool {
         self.get_attr(namespace, attr).map_or(false, |x| x == val)
     }
 }
 
+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> {
         ServoLayoutElement {
             element: el,
             chain: PhantomData,
         }
     }
--- a/servo/components/script_layout_interface/Cargo.toml
+++ b/servo/components/script_layout_interface/Cargo.toml
@@ -22,13 +22,13 @@ ipc-channel = "0.5"
 libc = "0.2"
 log = "0.3.5"
 msg = {path = "../msg"}
 net_traits = {path = "../net_traits"}
 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"]}
 util = {path = "../util"}
--- a/servo/components/servo/Cargo.lock
+++ b/servo/components/servo/Cargo.lock
@@ -1157,17 +1157,17 @@ dependencies = [
  "net_traits 0.0.1",
  "ordered-float 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "plugins 0.0.1",
  "profile_traits 0.0.1",
  "range 0.0.1",
  "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)",
  "style 0.0.1",
  "style_traits 0.0.1",
  "unicode-bidi 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "unicode-script 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1926,17 +1926,17 @@ dependencies = [
  "rand 0.3.14 (registry+https://github.com/rust-lang/crates.io-index)",
  "range 0.0.1",
  "ref_filter_map 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "ref_slice 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 0.1.71 (registry+https://github.com/rust-lang/crates.io-index)",
  "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)",
  "style 0.0.1",
  "time 0.1.35 (registry+https://github.com/rust-lang/crates.io-index)",
  "tinyfiledialogs 0.1.0 (git+https://github.com/jdm/tinyfiledialogs)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "util 0.0.1",
@@ -1963,17 +1963,17 @@ 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)",
  "msg 0.0.1",
  "net_traits 0.0.1",
  "plugins 0.0.1",
  "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)",
  "util 0.0.1",
 ]
 
 [[package]]
 name = "script_tests"
@@ -2012,17 +2012,17 @@ dependencies = [
  "style_traits 0.0.1",
  "time 0.1.35 (registry+https://github.com/rust-lang/crates.io-index)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "util 0.0.1",
 ]
 
 [[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)",
  "cssparser 0.5.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "fnv 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "heapsize 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "heapsize_plugin 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "matches 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2234,17 +2234,17 @@ 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)",
  "matches 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.1.32 (registry+https://github.com/rust-lang/crates.io-index)",
  "ordered-float 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "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)",
  "string_cache 0.2.23 (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)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "util 0.0.1",
@@ -2254,17 +2254,17 @@ dependencies = [
 [[package]]
 name = "style_tests"
 version = "0.0.1"
 dependencies = [
  "app_units 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "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",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "util 0.0.1",
 ]
 
 [[package]]
--- a/servo/components/style/Cargo.toml
+++ b/servo/components/style/Cargo.toml
@@ -33,17 +33,17 @@ heapsize = {version = "0.3.0", optional 
 heapsize_plugin = {version = "0.1.2", optional = true}
 lazy_static = "0.2"
 log = "0.3.5"
 matches = "0.1"
 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"
 string_cache = {version = "0.2.23", features = ["heap_size"], optional = true}
 style_traits = {path = "../style_traits"}
 time = "0.1"
 url = "1.2"
 util = {path = "../util"}
--- a/servo/components/style/cache.rs
+++ b/servo/components/style/cache.rs
@@ -2,27 +2,27 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Two simple cache data structures.
 
 use rand;
 use rand::Rng;
 use std::hash::{Hash, Hasher, SipHasher};
-use std::slice::Iter;
+use std::slice::{Iter, IterMut};
 
 pub struct LRUCache<K, V> {
     entries: Vec<(K, V)>,
     cache_size: usize,
 }
 
 impl<K: PartialEq, V: Clone> LRUCache<K, V> {
     pub fn new(size: usize) -> LRUCache<K, V> {
         LRUCache {
-          entries: vec!(),
+          entries: vec![],
           cache_size: size,
         }
     }
 
     #[inline]
     pub fn touch(&mut self, pos: usize) -> &V {
         let last_index = self.entries.len() - 1;
         if pos != last_index {
@@ -31,16 +31,20 @@ impl<K: PartialEq, V: Clone> LRUCache<K,
         }
         &self.entries[last_index].1
     }
 
     pub fn iter(&self) -> Iter<(K, V)> {
         self.entries.iter()
     }
 
+    pub fn iter_mut(&mut self) -> IterMut<(K, V)> {
+        self.entries.iter_mut()
+    }
+
     pub fn insert(&mut self, key: K, val: V) {
         if self.entries.len() == self.cache_size {
             self.entries.remove(0);
         }
         self.entries.push((key, val));
     }
 
     pub fn find(&mut self, key: &K) -> Option<V> {
--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -196,17 +196,17 @@ pub trait TDocument : Sized + Copy + Clo
                                               <Self::ConcreteElement as ElementExt>::Snapshot)>;
 }
 
 pub trait PresentationalHintsSynthetizer {
     fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, hints: &mut V)
         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>;
 
     fn as_node(&self) -> Self::ConcreteNode;
 
     fn style_attribute(&self) -> &Option<PropertyDeclarationBlock>;
 
     fn get_state(&self) -> ElementState;
@@ -231,16 +231,17 @@ pub trait TElement : Sized + Copy + Clon
             curr = parent;
         }
 
         // Process hints.
         if hint.contains(RESTYLE_SELF) {
             unsafe { node.set_dirty(true); }
         // XXX(emilio): For now, dirty implies dirty descendants if found.
         } else if hint.contains(RESTYLE_DESCENDANTS) {
+            unsafe { node.set_dirty_descendants(true); }
             let mut current = node.first_child();
             while let Some(node) = current {
                 unsafe { node.set_dirty(true); }
                 current = node.next_sibling();
             }
         }
 
         if hint.contains(RESTYLE_LATER_SIBLINGS) {
--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -7,31 +7,31 @@
 #![allow(unsafe_code)]
 
 use animation;
 use arc_ptr_eq;
 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_impl::{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::hash::{BuildHasherDefault, Hash, Hasher};
-use std::slice::Iter;
+use std::slice::IterMut;
 use std::sync::Arc;
-use string_cache::{Atom, Namespace};
+use string_cache::Atom;
 use traversal::RestyleResult;
 use util::opts;
 
 fn create_common_style_affecting_attributes_from_element<E: TElement>(element: &E)
                                                          -> CommonStyleAffectingAttributes {
     let mut flags = CommonStyleAffectingAttributes::empty();
     for attribute_info in &common_style_affecting_attributes() {
         match attribute_info.mode {
@@ -173,165 +173,157 @@ impl ApplicableDeclarationsCache {
         self.cache.insert(ApplicableDeclarationsCacheEntry::new(declarations), style)
     }
 
     pub fn evict_all(&mut self) {
         self.cache.evict_all();
     }
 }
 
-/// An LRU cache of the last few nodes seen, so that we can aggressively try to reuse their styles.
-pub struct StyleSharingCandidateCache {
-    cache: LRUCache<StyleSharingCandidate, ()>,
+/// Information regarding a candidate.
+///
+/// TODO: We can stick a lot more info here.
+#[derive(Debug)]
+struct StyleSharingCandidate {
+    /// The node, guaranteed to be an element.
+    node: UnsafeNode,
+    /// The cached computed style, here for convenience.
+    style: Arc<ComputedValues>,
+    /// The cached common style affecting attribute info.
+    common_style_affecting_attributes: Option<CommonStyleAffectingAttributes>,
 }
 
-#[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 {
+impl PartialEq<StyleSharingCandidate> 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.node == other.node &&
+            arc_ptr_eq(&self.style, &other.style) &&
             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,
-        };
+/// 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, ()>,
+}
 
-        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: &mut StyleSharingCandidate,
+                                          candidate_element: &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)
-        })
+    if element.parent_element() != candidate_element.parent_element() {
+        miss!(Parent)
+    }
+
+    if *element.get_local_name() != *candidate_element.get_local_name() {
+        miss!(LocalName)
+    }
+
+    if *element.get_namespace() != *candidate_element.get_namespace() {
+        miss!(Namespace)
+    }
+
+    if element.is_link() != candidate_element.is_link() {
+        miss!(Link)
     }
 
-    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.get_state() != candidate_element.get_state() {
+        miss!(State)
+    }
+
+    if element.get_id().is_some() {
+        miss!(IdAttr)
+    }
+
+    if element.style_attribute().is_some() {
+        miss!(StyleAttr)
+    }
+
+    if !have_same_class(element, candidate_element) {
+        miss!(Class)
+    }
 
-        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 !have_same_common_style_affecting_attributes(element,
+                                                    candidate,
+                                                    candidate_element) {
+        miss!(CommonStyleAffectingAttributes)
+    }
 
-        if element.get_namespace() != self.namespace.borrow() {
-            return false
-        }
+    if !have_same_presentational_hints(element, candidate_element) {
+        miss!(PresHints)
+    }
 
-        let mut matching_rules = ForgetfulSink::new();
-        element.synthesize_presentational_hints_for_legacy_attributes(&mut matching_rules);
-        if !matching_rules.is_empty() {
-            return false;
-        }
-
-        // 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 !match_same_sibling_affecting_rules(element,
+                                           candidate_element,
+                                           shared_context) {
+        miss!(SiblingRules)
+    }
 
-        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 !match_same_not_common_style_affecting_attributes_rules(element,
+                                                               candidate_element,
+                                                               shared_context) {
+        miss!(NonCommonAttrRules)
+    }
+
+    Ok(candidate.style.clone())
+}
 
-        for attribute_name in &rare_style_affecting_attributes() {
-            if element.has_attr(&ns!(), attribute_name) {
-                return false
-            }
-        }
+fn have_same_common_style_affecting_attributes<E: TElement>(element: &E,
+                                                            candidate: &mut StyleSharingCandidate,
+                                                            candidate_element: &E) -> bool {
+    if candidate.common_style_affecting_attributes.is_none() {
+        candidate.common_style_affecting_attributes =
+            Some(create_common_style_affecting_attributes_from_element(candidate_element))
+    }
+    create_common_style_affecting_attributes_from_element(element) ==
+        candidate.common_style_affecting_attributes.unwrap()
+}
 
-        if element.is_link() != self.link {
-            return false
-        }
+fn have_same_presentational_hints<E: TElement>(element: &E, candidate: &E) -> bool {
+    let mut first = ForgetfulSink::new();
+    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!");
+    }
 
-        // TODO(pcwalton): We don't support visited links yet, but when we do there will need to
-        // be some logic here.
-
-        true
-    }
+    first.is_empty()
 }
 
 bitflags! {
     pub flags CommonStyleAffectingAttributes: u8 {
         const HIDDEN_ATTRIBUTE = 0x01,
         const NO_WRAP_ATTRIBUTE = 0x02,
         const ALIGN_LEFT_ATTRIBUTE = 0x04,
         const ALIGN_CENTER_ATTRIBUTE = 0x08,
@@ -379,39 +371,107 @@ pub fn common_style_affecting_attributes
 
 /// Attributes that, if present, disable style sharing. All legacy HTML attributes must be in
 /// either this list or `common_style_affecting_attributes`. See the comment in
 /// `synthesize_presentational_hints_for_legacy_attributes`.
 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
+}
+
+// TODO: These re-match the candidate every time, which is suboptimal.
+#[inline]
+fn match_same_not_common_style_affecting_attributes_rules<E: TElement>(element: &E,
+                                                                       candidate: &E,
+                                                                       ctx: &SharedStyleContext) -> bool {
+    ctx.stylist.match_same_not_common_style_affecting_attributes_rules(element, candidate)
+}
+
+#[inline]
+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 {
         StyleSharingCandidateCache {
             cache: LRUCache::new(STYLE_SHARING_CANDIDATE_CACHE_SIZE),
         }
     }
 
-    pub fn iter(&self) -> Iter<(StyleSharingCandidate, ())> {
-        self.cache.iter()
+    fn iter_mut(&mut self) -> IterMut<(StyleSharingCandidate, ())> {
+        self.cache.iter_mut()
     }
 
-    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 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;
         }
+
+        let node = element.as_node();
+        let data = node.borrow_data().unwrap();
+        let style = data.style.as_ref().unwrap();
+
+        let box_style = style.get_box();
+        if box_style.transition_property_count() > 0 {
+            debug!("Failing to insert to the cache: transitions");
+            return;
+        }
+
+        if box_style.animation_name_count() > 0 {
+            debug!("Failing to insert to the cache: animations");
+            return;
+        }
+
+        debug!("Inserting into cache: {:?} with parent {:?}",
+               element.as_node().to_unsafe(), parent.as_node().to_unsafe());
+
+        self.cache.insert(StyleSharingCandidate {
+            node: node.to_unsafe(),
+            style: style.clone(),
+            common_style_affecting_attributes: None,
+        }, ());
     }
 
     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.
 pub enum StyleSharingResult<ConcreteRestyleDamage: TRestyleDamage> {
     /// We didn't find anybody to share the style with.
     CannotShare,
     /// The node's style can be shared. The integer specifies the index in the
     /// LRU cache that was hit and the damage that was done, and the restyle
@@ -557,119 +617,146 @@ trait PrivateMatchMethods: TNode {
         had_animations_to_expire || had_running_animations
     }
 }
 
 impl<N: TNode> PrivateMatchMethods for N {}
 
 trait PrivateElementMatchMethods: TElement {
     fn share_style_with_candidate_if_possible(&self,
-                                              parent_node: Option<Self::ConcreteNode>,
-                                              candidate: &StyleSharingCandidate)
-                                              -> 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,
-        };
+                                              parent_node: Self::ConcreteNode,
+                                              shared_context: &SharedStyleContext,
+                                              candidate: &mut StyleSharingCandidate)
+                                              -> Result<Arc<ComputedValues>, CacheMiss> {
+        debug_assert!(parent_node.is_element());
 
-        let parent_data: Option<&PrivateStyleData> = unsafe {
-            parent_node.borrow_data_unchecked().map(|d| &*d)
+        let candidate_element = unsafe {
+            Self::ConcreteNode::from_unsafe(&candidate.node).as_element().unwrap()
         };
 
-        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
-            }
-            return Some(candidate.style.clone())
-        }
-        None
+        element_matches_candidate(self, candidate, &candidate_element,
+                                  shared_context)
     }
 }
 
 impl<E: TElement> PrivateElementMatchMethods for E {}
 
 pub trait ElementMatchMethods : TElement {
     fn match_element(&self,
                      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,
                                                  None,
                                                  Some(&pseudo.clone()),
                                                  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
     /// the `style_sharing_candidate_cache` having only live nodes in it, and we have no way to
     /// guarantee that at the type system level yet.
     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 {
             return StyleSharingResult::CannotShare
         }
 
         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) {
-                // Yay, cache hit. Share the style.
-                let node = self.as_node();
+        let parent = match parent {
+            Some(parent) if parent.is_element() => parent,
+            _ => return StyleSharingResult::CannotShare,
+        };
 
-                let style = &mut node.mutate_data().unwrap().style;
+        for (i, &mut (ref mut candidate, ())) in style_sharing_candidate_cache.iter_mut().enumerate() {
+            let sharing_result = self.share_style_with_candidate_if_possible(parent,
+                                                                             shared_context,
+                                                                             candidate);
+            match sharing_result {
+                Ok(shared_style) => {
+                    // Yay, cache hit. Share the style.
+                    let node = self.as_node();
+                    let style = &mut node.mutate_data().unwrap().style;
 
-                let damage =
-                    match node.existing_style_for_restyle_damage((*style).as_ref(), None) {
-                        Some(ref source) => {
-                            <<Self as TElement>::ConcreteNode as TNode>
-                            ::ConcreteRestyleDamage::compute(source, &shared_style)
-                        }
-                        None => {
-                            <<Self as TElement>::ConcreteNode as TNode>
-                            ::ConcreteRestyleDamage::rebuild_and_reflow()
-                        }
+                    // TODO: add the display: none optimisation here too! Even
+                    // better, factor it out/make it a bit more generic so Gecko
+                    // can decide more easily if it knows that it's a child of
+                    // replaced content, or similar stuff!
+                    let damage =
+                        match node.existing_style_for_restyle_damage((*style).as_ref(), None) {
+                            Some(ref source) => {
+                                <<Self as TElement>::ConcreteNode as TNode>
+                                ::ConcreteRestyleDamage::compute(source, &shared_style)
+                            }
+                            None => {
+                                <<Self as TElement>::ConcreteNode as TNode>
+                                ::ConcreteRestyleDamage::rebuild_and_reflow()
+                            }
+                        };
+
+                    let restyle_result = if shared_style.get_box().clone_display() == display::T::none {
+                        RestyleResult::Stop
+                    } else {
+                        RestyleResult::Continue
                     };
 
-                let restyle_result = if shared_style.get_box().clone_display() == display::T::none {
-                    RestyleResult::Stop
-                } else {
-                    RestyleResult::Continue
-                };
+                    *style = Some(shared_style);
+
+                    return StyleSharingResult::StyleWasShared(i, damage, restyle_result)
+                }
+                Err(miss) => {
+                    debug!("Cache miss: {:?}", miss);
 
-                *style = Some(shared_style);
-
-                return StyleSharingResult::StyleWasShared(i, damage, restyle_result)
+                    // Cache miss, let's see what kind of failure to decide
+                    // whether we keep trying or not.
+                    match miss {
+                        // Too expensive failure, give up, we don't want another
+                        // one of these.
+                        CacheMiss::CommonStyleAffectingAttributes |
+                        CacheMiss::PresHints |
+                        CacheMiss::SiblingRules |
+                        CacheMiss::NonCommonAttrRules => break,
+                        _ => {}
+                    }
+                }
             }
         }
 
         StyleSharingResult::CannotShare
     }
 }
 
 impl<E: TElement> ElementMatchMethods for E {}
--- a/servo/components/style/parallel.rs
+++ b/servo/components/style/parallel.rs
@@ -7,16 +7,18 @@
 //! This code is highly unsafe. Keep this file small and easy to audit.
 
 #![allow(unsafe_code)]
 
 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)]
 fn static_assertion(node: UnsafeNode) {
     unsafe {
         let _: UnsafeNodeList = mem::transmute(node);
     }
 }
@@ -37,23 +39,38 @@ pub fn run_queue_with_custom_work_data_t
     };
     callback(queue);
     queue.run(shared);
 }
 
 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.
 #[inline(always)]
 fn top_down_dom<N, C>(unsafe_nodes: UnsafeNodeList,
                       proxy: &mut WorkerProxy<C::SharedContext, UnsafeNodeList>)
                       where N: TNode, C: DomTraversalContext<N> {
     let context = C::new(proxy.user_data(), unsafe_nodes.1);
@@ -97,16 +114,20 @@ fn top_down_dom<N, C>(unsafe_nodes: Unsa
 
             // If there were no more children, start walking back up.
             if children_to_process == 0 {
                 bottom_up_dom::<N, C>(unsafe_nodes.1, unsafe_node, proxy)
             }
         }
     }
 
+    // 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>,
             data: (Box::new(chunk.iter().cloned().collect()), unsafe_nodes.1),
         });
     }
 }
 
--- a/servo/components/style/restyle_hints.rs
+++ b/servo/components/style/restyle_hints.rs
@@ -1,16 +1,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Restyle hints: an optimization to avoid unnecessarily matching selectors.
 
 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};
 use std::clone::Clone;
 use std::sync::Arc;
 use string_cache::Atom;
 
 /// When the ElementState of an element (like IN_HOVER_STATE) changes, certain
@@ -343,17 +344,21 @@ pub struct DependencySet {
     deps: Vec<Dependency>,
 }
 
 impl DependencySet {
     pub fn new() -> Self {
         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 {
             let mut sensitivities = Sensitivities::new();
             for s in &cur.simple_selectors {
                 sensitivities.states.insert(selector_to_state(s));
                 if !sensitivities.attrs {
                     sensitivities.attrs = is_attr_selector(s);
@@ -365,17 +370,17 @@ impl DependencySet {
                     combinator: combinator,
                     sensitivities: sensitivities,
                 });
             }
 
             cur = match cur.next {
                 Some((ref sel, comb)) => {
                     combinator = Some(comb);
-                    sel.clone()
+                    sel
                 }
                 None => break,
             }
         }
     }
 
     pub fn clear(&mut self) {
         self.deps.clear();
@@ -384,24 +389,29 @@ impl DependencySet {
 
 impl DependencySet {
     pub fn compute_hint<E>(&self, el: &E,
                            snapshot: &E::Snapshot,
                            current_state: ElementState)
                            -> 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() {
                         break
                     }
                 }
             }
         }
--- a/servo/components/style/selector_matching.rs
+++ b/servo/components/style/selector_matching.rs
@@ -10,28 +10,29 @@ use error_reporting::StdoutErrorReporter
 use keyframes::KeyframesAnimation;
 use media_queries::{Device, MediaType};
 use properties::{self, PropertyDeclaration, PropertyDeclarationBlock, ComputedValues};
 use restyle_hints::{RestyleHint, DependencySet};
 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;
 use std::hash::BuildHasherDefault;
 use std::sync::Arc;
 use string_cache::Atom;
 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
 /// for a given document. The selectors are converted into `Rule`s
 /// (defined in rust-selectors), and introduced in a `SelectorMap`
 /// depending on the pseudo-element (see `PerPseudoElementSelectorMap`),
 /// stylesheet origin (see `PerOriginSelectorMap`), and priority
 /// (see the `normal` and `important` fields in `PerOriginSelectorMap`).
@@ -71,16 +72,23 @@ pub struct Stylist {
     precomputed_pseudo_element_decls: HashMap<PseudoElement,
                                               Vec<DeclarationBlock>,
                                               BuildHasherDefault<::fnv::FnvHasher>>,
 
     rules_source_order: usize,
 
     /// 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 {
     #[inline]
     pub fn new(device: Device) -> Self {
         let mut stylist = Stylist {
             viewport_constraints: None,
             device: device,
@@ -88,16 +96,20 @@ impl Stylist {
             quirks_mode: false,
 
             element_map: PerPseudoElementSelectorMap::new(),
             pseudos_map: HashMap::with_hasher(Default::default()),
             animations: HashMap::with_hasher(Default::default()),
             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| {
             stylist.pseudos_map.insert(pseudo, PerPseudoElementSelectorMap::new());
         });
 
         // FIXME: Add iso-8859-9.css when the document’s encoding is ISO-8859-8.
 
@@ -115,16 +127,19 @@ impl Stylist {
         TheSelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
             self.pseudos_map.insert(pseudo, PerPseudoElementSelectorMap::new());
         });
 
         self.precomputed_pseudo_element_decls = HashMap::with_hasher(Default::default());
         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);
         }
 
         if self.quirks_mode {
             if let Some(s) = TheSelectorImpl::get_quirks_mode_stylesheet() {
                 self.add_stylesheet(s);
             }
@@ -173,18 +188,26 @@ impl Stylist {
         );
 
         for rule in stylesheet.effective_rules(&self.device) {
             match *rule {
                 CSSRule::Style(ref style_rule) => {
                     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;
                 }
                 CSSRule::Keyframes(ref keyframes_rule) => {
                     debug!("Found valid keyframes rule: {:?}", keyframes_rule);
                     if let Some(animation) = KeyframesAnimation::from_keyframes(&keyframes_rule.keyframes) {
                         debug!("Found valid keyframe animation: {:?}", animation);
@@ -197,16 +220,24 @@ impl Stylist {
                         self.animations.remove(&keyframes_rule.name);
                     }
                 }
                 // We don't care about any other rule.
                 _ => {}
             }
         }
 
+        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
             // extra field, and avoid this precomputation entirely.
             if let Some(map) = self.pseudos_map.remove(&pseudo) {
                 let mut declarations = vec![];
 
                 map.user_agent.normal.get_universal_rules(&mut declarations);
@@ -305,104 +336,182 @@ impl Stylist {
     /// matching logic to be reduced to the logic in
     /// `css::matching::PrivateMatchMethods::candidate_element_allows_for_style_sharing`.
     pub fn push_applicable_declarations<E, V>(
                                         &self,
                                         element: &E,
                                         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");
         debug_assert!(pseudo_element.is_none() ||
                       !TheSelectorImpl::pseudo_element_cascade_type(pseudo_element.as_ref().unwrap())
                         .is_precomputed());
 
         let map = match pseudo_element {
             Some(ref pseudo) => self.pseudos_map.get(pseudo).unwrap(),
             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);
 
-        shareable
+        debug!("push_applicable_declarations: shareable: {:?}", relations);
+
+        relations
     }
 
     #[inline]
     pub fn is_device_dirty(&self) -> bool {
         self.is_device_dirty
     }
 
     #[inline]
     pub fn animations(&self) -> &HashMap<Atom, KeyframesAnimation> {
         &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
                                    // selectors::Element doesn't provide access to ElementState
                                    // directly, and computing it from the ElementState would be
                                    // more expensive than getting it directly from the caller.
                                    current_state: ElementState)
                                    -> RestyleHint
--- a/servo/components/style/sequential.rs
+++ b/servo/components/style/sequential.rs
@@ -30,10 +30,11 @@ pub fn traverse_dom<N, C>(root: N,
             context.process_postorder(node);
         }
     }
 
     let context = C::new(shared, root.opaque());
     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();
 }
-
--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -1,20 +1,22 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! 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::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering};
 use tid::tid;
 use util::opts;
 use values::HasViewportPercentage;
 
 /// Every time we do another layout, the old bloom filters are invalid. This is
 /// detected by ticking a generation number every layout.
 pub type Generation = u32;
 
@@ -22,16 +24,20 @@ pub type Generation = u32;
 /// an element.
 ///
 /// So far this only happens where a display: none node is found.
 pub enum RestyleResult {
     Continue,
     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
 /// matches. Thanks to the bloom filter, we can avoid walking up the tree
 /// looking for ancestors that aren't there in the majority of cases.
 ///
 /// As we walk down the DOM tree a thread-local bloom filter is built of all the
 /// CSS `SimpleSelector`s which are part of a `Descendant` compound selector
@@ -144,17 +150,17 @@ pub fn remove_from_bloom_filter<'a, N, C
             // Otherwise, put it back, but remove this node.
             node.remove_from_bloom_filter(&mut *bf);
             let unsafe_parent = parent.to_unsafe();
             put_thread_local_bloom_filter(bf, &unsafe_parent, &context.shared_context());
         },
     };
 }
 
-pub trait DomTraversalContext<N: TNode>  {
+pub trait DomTraversalContext<N: TNode> {
     type SharedContext: Sync + 'static;
 
     fn new<'a>(&'a Self::SharedContext, OpaqueNode) -> Self;
 
     /// Process `node` on the way down, before its children have been processed.
     fn process_preorder(&self, node: N) -> RestyleResult;
 
     /// Process `node` on the way up, after its children have been processed.
@@ -186,16 +192,29 @@ pub trait DomTraversalContext<N: TNode> 
         // the child, since we have exclusive access to both of them.
         if parent.is_dirty() {
             unsafe {
                 kid.set_dirty(true);
                 parent.set_dirty_descendants(true);
             }
         }
     }
+
+    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,
                                     context: &'a C)
     where N: TNode,
           C: StyleContext<'a>
 {
     let mut display_none = false;
@@ -296,62 +315,76 @@ pub fn recalc_style_at<'a, N, C>(context
         // Check to see whether we can share a style with someone.
         let style_sharing_candidate_cache =
             &mut context.local_context().style_sharing_candidate_cache.borrow_mut();
 
         let sharing_result = match node.as_element() {
             Some(element) => {
                 unsafe {
                     element.share_style_if_possible(style_sharing_candidate_cache,
+                                                    context.shared_context(),
                                                     parent_opt.clone())
                 }
             },
             None => StyleSharingResult::CannotShare,
         };
 
         // Otherwise, match and cascade selectors.
         match sharing_result {
             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())
                         }
                         None
                     },
                 };
 
                 // Perform the CSS cascade.
                 unsafe {
                     restyle_result = node.cascade_node(context,
-                                                    parent_opt,
-                                                    &applicable_declarations);
+                                                       parent_opt,
+                                                       &applicable_declarations);
                 }
 
                 // 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);
             }
         }
     } else {
         // Finish any expired transitions.
         animation::complete_expired_transitions(
             node.opaque(),
--- a/servo/components/util/opts.rs
+++ b/servo/components/util/opts.rs
@@ -167,16 +167,19 @@ pub struct Opts {
     pub dump_layer_tree: bool,
 
     /// Emits notifications when there is a relayout.
     pub relayout_event: bool,
 
     /// 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,
 
     /// True to exit after the page load (`-x`).
     pub exit_after_load: bool,
 
     /// Do not use native titlebar
     pub no_native_titlebar: bool,
@@ -270,16 +273,19 @@ pub struct DebugOptions {
     pub paint_flashing: bool,
 
     /// Write layout trace to an external file for debugging.
     pub trace_layout: bool,
 
     /// 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,
 
     /// Replace unpaires surrogates in DOM strings with U+FFFD.
     /// See https://github.com/servo/servo/issues/6564
     pub replace_surrogates: bool,
 
     /// Log GC passes and their durations.
@@ -326,16 +332,17 @@ impl DebugOptions {
                 "profile-heartbeats" => debug_options.profile_heartbeats = true,
                 "show-compositor-borders" => debug_options.show_compositor_borders = true,
                 "show-fragment-borders" => debug_options.show_fragment_borders = true,
                 "show-parallel-paint" => debug_options.show_parallel_paint = true,
                 "show-parallel-layout" => debug_options.show_parallel_layout = true,
                 "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,
                 "load-webfonts-synchronously" => debug_options.load_webfonts_synchronously = true,
                 "disable-vsync" => debug_options.disable_vsync = true,
                 "wr-stats" => debug_options.webrender_stats = true,
                 "wr-debug" => debug_options.webrender_debug = true,
                 "msaa" => debug_options.use_msaa = true,
@@ -507,16 +514,17 @@ pub fn default_opts() -> Opts {
         dump_flow_tree: false,
         dump_display_list: false,
         dump_display_list_json: false,
         dump_layer_tree: false,
         relayout_event: false,
         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,
         enable_vsync: true,
         use_webrender: false,
         webrender_stats: false,
         use_msaa: false,
         render_api: DEFAULT_RENDER_API,
@@ -812,16 +820,17 @@ pub fn from_cmdline_args(args: &[String]
         enable_canvas_antialiasing: !debug_options.disable_canvas_aa,
         dump_style_tree: debug_options.dump_style_tree,
         dump_flow_tree: debug_options.dump_flow_tree,
         dump_display_list: debug_options.dump_display_list,
         dump_display_list_json: debug_options.dump_display_list_json,
         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,
         enable_vsync: !debug_options.disable_vsync,
         use_webrender: use_webrender,
         webrender_stats: debug_options.webrender_stats,
         use_msaa: debug_options.use_msaa,
         config_dir: opt_match.opt_str("config-dir"),
--- a/servo/ports/cef/Cargo.lock
+++ b/servo/ports/cef/Cargo.lock
@@ -1065,17 +1065,17 @@ dependencies = [
  "net_traits 0.0.1",
  "ordered-float 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "plugins 0.0.1",
  "profile_traits 0.0.1",
  "range 0.0.1",
  "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)",
  "style 0.0.1",
  "style_traits 0.0.1",
  "unicode-bidi 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "unicode-script 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1778,17 +1778,17 @@ dependencies = [
  "rand 0.3.14 (registry+https://github.com/rust-lang/crates.io-index)",
  "range 0.0.1",
  "ref_filter_map 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "ref_slice 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 0.1.71 (registry+https://github.com/rust-lang/crates.io-index)",
  "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)",
  "style 0.0.1",
  "time 0.1.35 (registry+https://github.com/rust-lang/crates.io-index)",
  "tinyfiledialogs 0.1.0 (git+https://github.com/jdm/tinyfiledialogs)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "util 0.0.1",
@@ -1815,17 +1815,17 @@ 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)",
  "msg 0.0.1",
  "net_traits 0.0.1",
  "plugins 0.0.1",
  "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)",
  "util 0.0.1",
 ]
 
 [[package]]
 name = "script_traits"
@@ -1854,17 +1854,17 @@ dependencies = [
  "style_traits 0.0.1",
  "time 0.1.35 (registry+https://github.com/rust-lang/crates.io-index)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "util 0.0.1",
 ]
 
 [[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)",
  "cssparser 0.5.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "fnv 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "heapsize 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "heapsize_plugin 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "matches 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2117,17 +2117,17 @@ 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)",
  "matches 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.1.32 (registry+https://github.com/rust-lang/crates.io-index)",
  "ordered-float 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "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)",
  "string_cache 0.2.23 (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)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "util 0.0.1",
--- a/servo/ports/geckolib/Cargo.lock
+++ b/servo/ports/geckolib/Cargo.lock
@@ -6,17 +6,17 @@ dependencies = [
  "env_logger 0.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "euclid 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "gecko_bindings 0.0.1",
  "gecko_string_cache 0.2.20",
  "lazy_static 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "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)",
  "util 0.0.1",
 ]
 
 [[package]]
 name = "aho-corasick"
@@ -165,17 +165,17 @@ dependencies = [
 [[package]]
 name = "gecko_string_cache"
 version = "0.2.20"
 dependencies = [
  "cfg-if 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "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)",
 ]
 
 [[package]]
 name = "getopts"
 version = "0.2.14"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
@@ -306,17 +306,17 @@ source = "registry+https://github.com/ru
 
 [[package]]
 name = "rustc-serialize"
 version = "0.3.19"
 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)",
  "cssparser 0.5.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "fnv 1.0.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "matches 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "quickersort 2.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -362,17 +362,17 @@ dependencies = [
  "lazy_static 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "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)",
  "matches 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.1.32 (registry+https://github.com/rust-lang/crates.io-index)",
  "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)",
  "url 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "util 0.0.1",
  "walkdir 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
--- a/servo/ports/geckolib/Cargo.toml
+++ b/servo/ports/geckolib/Cargo.toml
@@ -14,13 +14,13 @@ app_units = "0.3"
 env_logger = "0.3"
 euclid = "0.9"
 gecko_bindings = {version = "0.0.1", path = "gecko_bindings"}
 gecko_string_cache = {path = "string_cache"}
 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"
 util = {path = "../../components/util"}
--- a/servo/ports/geckolib/string_cache/Cargo.toml
+++ b/servo/ports/geckolib/string_cache/Cargo.toml
@@ -9,10 +9,10 @@ publish = false
 [lib]
 path = "lib.rs"
 
 [dependencies]
 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"
--- a/servo/ports/geckolib/traversal.rs
+++ b/servo/ports/geckolib/traversal.rs
@@ -1,15 +1,15 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 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};
 use wrapper::GeckoNode;
 
 pub struct RecalcStyleOnly<'lc> {
     context: StandaloneStyleContext<'lc>,
     root: OpaqueNode,
@@ -37,9 +37,13 @@ impl<'lc, 'ln> DomTraversalContext<Gecko
     }
 
     fn process_postorder(&self, _: GeckoNode<'ln>) {
         unreachable!();
     }
 
     /// 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()
+    }
 }
--- a/servo/ports/geckolib/wrapper.rs
+++ b/servo/ports/geckolib/wrapper.rs
@@ -454,16 +454,22 @@ impl<'le> TElement for GeckoElement<'le>
                                        namespace.0.as_ptr(),
                                        attr.as_ptr(),
                                        val.as_ptr(),
                                        /* ignoreCase = */ false)
         }
     }
 }
 
+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>>>
     {
         // FIXME(bholley) - Need to implement this.
     }
 }
 
--- a/servo/tests/unit/style/Cargo.toml
+++ b/servo/tests/unit/style/Cargo.toml
@@ -9,14 +9,14 @@ name = "style_tests"
 path = "lib.rs"
 doctest = false
 
 [dependencies]
 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"}
 url = {version = "1.2", features = ["heap_size"]}
 util = {path = "../../../components/util"}