Merge commit 'refs/upstream/master' into gecko-backout

34 files changed, 1127 insertions, 715 deletions

diff --git a/components/canvas/Cargo.toml b/components/canvas/Cargo.toml
index 5fb7776fefc..42e8b853e53 100644
--- a/components/canvas/Cargo.toml
+++ b/components/canvas/Cargo.toml
@@ -12,7 +12,7 @@ path = "lib.rs"
 [dependencies]
 azure = {git = "https://github.com/servo/rust-azure"}
 canvas_traits = {path = "../canvas_traits"}
-cssparser = "0.16"
+cssparser = "0.16.1"
 euclid = "0.15"
 gleam = "0.4"
 ipc-channel = "0.8"
diff --git a/components/canvas_traits/Cargo.toml b/components/canvas_traits/Cargo.toml
index 94465e16809..1c6ca6bb1a4 100644
--- a/components/canvas_traits/Cargo.toml
+++ b/components/canvas_traits/Cargo.toml
@@ -10,7 +10,7 @@ name = "canvas_traits"
 path = "lib.rs"
 
 [dependencies]
-cssparser = "0.16"
+cssparser = "0.16.1"
 euclid = "0.15"
 heapsize = "0.4"
 heapsize_derive = "0.1"
diff --git a/components/layout_thread/lib.rs b/components/layout_thread/lib.rs
index ce3a7e28b7d..96eac55cc5b 100644
--- a/components/layout_thread/lib.rs
+++ b/components/layout_thread/lib.rs
@@ -793,6 +793,10 @@ impl LayoutThread {
     /// Shuts down the layout thread now. If there are any DOM nodes left, layout will now (safely)
     /// crash.
     fn exit_now(&mut self) {
+        // Drop the root flow explicitly to avoid holding style data, such as
+        // rule nodes.  The `Stylist` checks when it is dropped that all rule
+        // nodes have been GCed, so we want drop anyone who holds them first.
+        self.root_flow.borrow_mut().take();
         // Drop the rayon threadpool if present.
         let _ = self.parallel_traversal.take();
     }
diff --git a/components/script/Cargo.toml b/components/script/Cargo.toml
index b9d8a0b1304..12f84eeaf12 100644
--- a/components/script/Cargo.toml
+++ b/components/script/Cargo.toml
@@ -35,7 +35,7 @@ byteorder = "1.0"
 canvas_traits = {path = "../canvas_traits"}
 caseless = "0.1.0"
 cookie = "0.6"
-cssparser = "0.16"
+cssparser = "0.16.1"
 deny_public_fields = {path = "../deny_public_fields"}
 devtools_traits = {path = "../devtools_traits"}
 dom_struct = {path = "../dom_struct"}
diff --git a/components/script/dom/globalscope.rs b/components/script/dom/globalscope.rs
index ce81958a2cb..3a47298c53b 100644
--- a/components/script/dom/globalscope.rs
+++ b/components/script/dom/globalscope.rs
@@ -543,12 +543,16 @@ impl GlobalScope {
     ///
     /// ["current"]: https://html.spec.whatwg.org/multipage/#current
     #[allow(unsafe_code)]
-    pub fn current() -> Root<Self> {
+    pub fn current() -> Option<Root<Self>> {
         unsafe {
             let cx = Runtime::get();
             assert!(!cx.is_null());
             let global = CurrentGlobalOrNull(cx);
-            global_scope_from_global(global)
+            if global.is_null() {
+                None
+            } else {
+                Some(global_scope_from_global(global))
+            }
         }
     }
 
diff --git a/components/script/dom/htmliframeelement.rs b/components/script/dom/htmliframeelement.rs
index 23feab87329..bde40d11a2b 100644
--- a/components/script/dom/htmliframeelement.rs
+++ b/components/script/dom/htmliframeelement.rs
@@ -590,7 +590,7 @@ impl HTMLIFrameElementMethods for HTMLIFrameElement {
             Some(document) => document,
         };
         // Step 4.
-        let current = GlobalScope::current().as_window().Document();
+        let current = GlobalScope::current().expect("No current global object").as_window().Document();
         if !current.origin().same_origin_domain(document.origin()) {
             return None;
         }
diff --git a/components/script/dom/permissions.rs b/components/script/dom/permissions.rs
index b5cab2ace90..3368782d06e 100644
--- a/components/script/dom/permissions.rs
+++ b/components/script/dom/permissions.rs
@@ -241,7 +241,7 @@ impl PermissionAlgorithm for Permissions {
                 let state =
                     prompt_user(&format!("{} {} ?", REQUEST_DIALOG_MESSAGE, perm_name.clone()));
 
-                let globalscope = GlobalScope::current();
+                let globalscope = GlobalScope::current().expect("No current global object");
                 globalscope.as_window()
                            .permission_state_invocation_results()
                            .borrow_mut()
@@ -266,7 +266,7 @@ pub fn get_descriptor_permission_state(permission_name: PermissionName,
     // Step 1.
     let settings = match env_settings_obj {
         Some(env_settings_obj) => Root::from_ref(env_settings_obj),
-        None => GlobalScope::current(),
+        None => GlobalScope::current().expect("No current global object"),
     };
 
     // Step 2.
diff --git a/components/script/dom/servoparser/async_html.rs b/components/script/dom/servoparser/async_html.rs
index e13f8169faa..e1632ffaf3c 100644
--- a/components/script/dom/servoparser/async_html.rs
+++ b/components/script/dom/servoparser/async_html.rs
@@ -138,8 +138,6 @@ pub struct ParseNode {
 
 #[derive(JSTraceable, HeapSizeOf)]
 struct ParseNodeData {
-    target: Option<String>,
-    data: Option<String>,
     contents: Option<ParseNode>,
     is_integration_point: bool,
 }
@@ -147,8 +145,6 @@ struct ParseNodeData {
 impl Default for ParseNodeData {
     fn default() -> ParseNodeData {
         ParseNodeData {
-            target: None,
-            data: None,
             contents: None,
             is_integration_point: false,
         }
@@ -169,7 +165,7 @@ enum ParseOperation {
     MarkScriptAlreadyStarted(ParseNodeID),
     ReparentChildren(ParseNodeID, ParseNodeID),
     AssociateWithForm(ParseNodeID, ParseNodeID),
-    CreatePI(ParseNodeID),
+    CreatePI(ParseNodeID, StrTendril, StrTendril),
     Pop(ParseNodeID),
 }
 
@@ -329,15 +325,11 @@ impl Sink {
             ParseOperation::Pop(node) => {
                 vtable_for(self.get_node(&node)).pop();
             }
-            ParseOperation::CreatePI(node) => {
-                let pi;
-                {
-                    let data = self.get_parse_node_data(&node);
-                    pi = ProcessingInstruction::new(
-                        DOMString::from(data.target.clone().unwrap()),
-                        DOMString::from(data.data.clone().unwrap()),
+            ParseOperation::CreatePI(node, target, data) => {
+                let pi = ProcessingInstruction::new(
+                        DOMString::from(String::from(target)),
+                        DOMString::from(String::from(data)),
                         document);
-                }
                 self.insert_node(node, JS::from_ref(pi.upcast()));
             }
         }
@@ -411,12 +403,7 @@ impl TreeSink for Sink {
 
     fn create_pi(&mut self, target: StrTendril, data: StrTendril) -> ParseNode {
         let node = self.new_parse_node();
-        {
-            let mut node_data = self.get_parse_node_data_mut(&node.id);
-            node_data.target = Some(String::from(target));
-            node_data.data = Some(String::from(data));
-        }
-        self.process_operation(ParseOperation::CreatePI(node.id));
+        self.process_operation(ParseOperation::CreatePI(node.id, target, data));
         node
     }
 
diff --git a/components/script/dom/window.rs b/components/script/dom/window.rs
index 0d4dca7d845..d560c71b3ad 100644
--- a/components/script/dom/window.rs
+++ b/components/script/dom/window.rs
@@ -586,7 +586,7 @@ impl WindowMethods for Window {
         };
         // Step 6.
         let container_doc = document_from_node(container);
-        let current_doc = GlobalScope::current().as_window().Document();
+        let current_doc = GlobalScope::current().expect("No current global object").as_window().Document();
         if !current_doc.origin().same_origin_domain(container_doc.origin()) {
             return None;
         }
diff --git a/components/script/layout_wrapper.rs b/components/script/layout_wrapper.rs
index d26493589c2..0875d437598 100644
--- a/components/script/layout_wrapper.rs
+++ b/components/script/layout_wrapper.rs
@@ -902,7 +902,7 @@ impl<'ln> ThreadSafeLayoutNode for ServoThreadSafeLayoutNode<'ln> {
     fn parent_style(&self) -> Arc<ComputedValues> {
         let parent = self.node.parent_node().unwrap().as_element().unwrap();
         let parent_data = parent.get_data().unwrap().borrow();
-        parent_data.styles().primary.values().clone()
+        parent_data.styles.primary().clone()
     }
 
     fn debug_id(self) -> usize {
diff --git a/components/script_layout_interface/Cargo.toml b/components/script_layout_interface/Cargo.toml
index fa861a91e6b..73d1f506636 100644
--- a/components/script_layout_interface/Cargo.toml
+++ b/components/script_layout_interface/Cargo.toml
@@ -13,7 +13,7 @@ path = "lib.rs"
 app_units = "0.5"
 atomic_refcell = "0.1"
 canvas_traits = {path = "../canvas_traits"}
-cssparser = "0.16"
+cssparser = "0.16.1"
 euclid = "0.15"
 gfx_traits = {path = "../gfx_traits"}
 heapsize = "0.4"
diff --git a/components/script_layout_interface/lib.rs b/components/script_layout_interface/lib.rs
index e3d791b7774..3e0a258aa7d 100644
--- a/components/script_layout_interface/lib.rs
+++ b/components/script_layout_interface/lib.rs
@@ -65,7 +65,7 @@ pub struct StyleData {
 impl StyleData {
     pub fn new() -> Self {
         Self {
-            element_data: AtomicRefCell::new(ElementData::new(None)),
+            element_data: AtomicRefCell::new(ElementData::default()),
             parallel: DomParallelInfo::new(),
         }
     }
diff --git a/components/script_layout_interface/wrapper_traits.rs b/components/script_layout_interface/wrapper_traits.rs
index c5574dc2a8f..cac426156da 100644
--- a/components/script_layout_interface/wrapper_traits.rs
+++ b/components/script_layout_interface/wrapper_traits.rs
@@ -346,7 +346,7 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
 
     #[inline]
     fn get_before_pseudo(&self) -> Option<Self> {
-        if self.style_data().styles().pseudos.has(&PseudoElement::Before) {
+        if self.style_data().styles.pseudos.has(&PseudoElement::Before) {
             Some(self.with_pseudo(PseudoElementType::Before(None)))
         } else {
             None
@@ -355,7 +355,7 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
 
     #[inline]
     fn get_after_pseudo(&self) -> Option<Self> {
-        if self.style_data().styles().pseudos.has(&PseudoElement::After) {
+        if self.style_data().styles.pseudos.has(&PseudoElement::After) {
             Some(self.with_pseudo(PseudoElementType::After(None)))
         } else {
             None
@@ -396,7 +396,7 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
         let data = self.style_data();
         match self.get_pseudo_element_type() {
             PseudoElementType::Normal => {
-                data.styles().primary.values().clone()
+                data.styles.primary().clone()
             },
             other => {
                 // Precompute non-eagerly-cascaded pseudo-element styles if not
@@ -406,17 +406,17 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
                     // Already computed during the cascade.
                     PseudoElementCascadeType::Eager => {
                         self.style_data()
-                            .styles().pseudos.get(&style_pseudo)
-                            .unwrap().values().clone()
+                            .styles.pseudos.get(&style_pseudo)
+                            .unwrap().clone()
                     },
                     PseudoElementCascadeType::Precomputed => {
                         context.stylist.precomputed_values_for_pseudo(
                             &context.guards,
                             &style_pseudo,
-                            Some(data.styles().primary.values()),
+                            Some(data.styles.primary()),
                             CascadeFlags::empty(),
                             &ServoMetricsProvider)
-                            .values().clone()
+                            .clone()
                     }
                     PseudoElementCascadeType::Lazy => {
                         context.stylist
@@ -425,10 +425,10 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
                                    unsafe { &self.unsafe_get() },
                                    &style_pseudo,
                                    RuleInclusion::All,
-                                   data.styles().primary.values(),
+                                   data.styles.primary(),
                                    &ServoMetricsProvider)
                                .unwrap()
-                               .values().clone()
+                               .clone()
                     }
                 }
             }
@@ -438,10 +438,10 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
     #[inline]
     fn selected_style(&self) -> Arc<ServoComputedValues> {
         let data = self.style_data();
-        data.styles().pseudos
+        data.styles.pseudos
             .get(&PseudoElement::Selection).map(|s| s)
-            .unwrap_or(&data.styles().primary)
-            .values().clone()
+            .unwrap_or(data.styles.primary())
+            .clone()
     }
 
     /// Returns the already resolved style of the node.
@@ -456,10 +456,10 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
         let data = self.style_data();
         match self.get_pseudo_element_type() {
             PseudoElementType::Normal
-                => data.styles().primary.values().clone(),
+                => data.styles.primary().clone(),
             other
-                => data.styles().pseudos
-                       .get(&other.style_pseudo_element()).unwrap().values().clone(),
+                => data.styles.pseudos
+                       .get(&other.style_pseudo_element()).unwrap().clone(),
         }
     }
 }
diff --git a/components/selectors/Cargo.toml b/components/selectors/Cargo.toml
index 3894e3e21ad..4a1ad7dd894 100644
--- a/components/selectors/Cargo.toml
+++ b/components/selectors/Cargo.toml
@@ -20,11 +20,12 @@ doctest = false
 
 [features]
 gecko_like_types = []
+unstable = []
 
 [dependencies]
 bitflags = "0.7"
 matches = "0.1"
-cssparser = "0.16"
+cssparser = "0.16.1"
 log = "0.3"
 fnv = "1.0"
 phf = "0.7.18"
diff --git a/components/selectors/bloom.rs b/components/selectors/bloom.rs
index 0f6fabbaa10..8caab9935cb 100644
--- a/components/selectors/bloom.rs
+++ b/components/selectors/bloom.rs
@@ -108,6 +108,18 @@ impl BloomFilter {
         self.counters = [0; ARRAY_SIZE]
     }
 
+    // Slow linear accessor to make sure the bloom filter is zeroed. This should
+    // never be used in release builds.
+    #[cfg(debug_assertions)]
+    pub fn is_zeroed(&self) -> bool {
+        self.counters.iter().all(|x| *x == 0)
+    }
+
+    #[cfg(not(debug_assertions))]
+    pub fn is_zeroed(&self) -> bool {
+        unreachable!()
+    }
+
     #[inline]
     pub fn insert_hash(&mut self, hash: u32) {
         {
@@ -229,85 +241,75 @@ fn create_and_insert_some_stuff() {
 #[cfg(test)]
 mod bench {
     extern crate test;
-
-    use std::hash::{Hash, Hasher, SipHasher};
     use super::BloomFilter;
 
+    #[derive(Default)]
+    struct HashGenerator(u32);
+
+    impl HashGenerator {
+        fn next(&mut self) -> u32 {
+            // Each hash is split into two twelve-bit segments, which are used
+            // as an index into an array. We increment each by 64 so that we
+            // hit the next cache line, and then another 1 so that our wrapping
+            // behavior leads us to different entries each time.
+            //
+            // Trying to simulate cold caches is rather difficult with the cargo
+            // benchmarking setup, so it may all be moot depending on the number
+            // of iterations that end up being run. But we might as well.
+            self.0 += (65) + (65 << super::KEY_SIZE);
+            self.0
+        }
+    }
+
     #[bench]
     fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) {
         b.iter(|| {
+            let mut gen1 = HashGenerator::default();
+            let mut gen2 = HashGenerator::default();
             let mut bf = BloomFilter::new();
-            for i in 0_usize .. 1000 {
-                bf.insert(&i);
+            for _ in 0_usize .. 1000 {
+                bf.insert_hash(gen1.next());
             }
-            for i in 0_usize .. 100 {
-                bf.remove(&i);
+            for _ in 0_usize .. 100 {
+                bf.remove_hash(gen2.next());
             }
-            for i in 100_usize .. 200 {
-                test::black_box(bf.might_contain(&i));
+            for _ in 100_usize .. 200 {
+                test::black_box(bf.might_contain_hash(gen2.next()));
             }
         });
     }
 
     #[bench]
-    fn might_contain(b: &mut test::Bencher) {
-        let mut bf = BloomFilter::new();
-
-        for i in 0_usize .. 1000 {
-            bf.insert(&i);
-        }
-
-        let mut i = 0_usize;
-
-        b.bench_n(1000, |b| {
-            b.iter(|| {
-                test::black_box(bf.might_contain(&i));
-                i += 1;
-            });
+    fn might_contain_10(b: &mut test::Bencher) {
+        let bf = BloomFilter::new();
+        let mut gen = HashGenerator::default();
+        b.iter(|| for _ in 0..10 {
+            test::black_box(bf.might_contain_hash(gen.next()));
         });
     }
 
     #[bench]
-    fn insert(b: &mut test::Bencher) {
-        let mut bf = BloomFilter::new();
-
-        b.bench_n(1000, |b| {
-            let mut i = 0_usize;
-
-            b.iter(|| {
-                test::black_box(bf.insert(&i));
-                i += 1;
-            });
-        });
+    fn clear(b: &mut test::Bencher) {
+        let mut bf = Box::new(BloomFilter::new());
+        b.iter(|| test::black_box(&mut bf).clear());
     }
 
     #[bench]
-    fn remove(b: &mut test::Bencher) {
+    fn insert_10(b: &mut test::Bencher) {
         let mut bf = BloomFilter::new();
-        for i in 0_usize .. 1000 {
-            bf.insert(&i);
-        }
-
-        b.bench_n(1000, |b| {
-            let mut i = 0_usize;
-
-            b.iter(|| {
-                bf.remove(&i);
-                i += 1;
-            });
+        let mut gen = HashGenerator::default();
+        b.iter(|| for _ in 0..10 {
+            test::black_box(bf.insert_hash(gen.next()));
         });
-
-        test::black_box(bf.might_contain(&0_usize));
     }
 
     #[bench]
-    fn hash_a_uint(b: &mut test::Bencher) {
-        let mut i = 0_usize;
-        b.iter(|| {
-            let mut hasher = SipHasher::default();
-            i.hash(&mut hasher);
-            test::black_box(hasher.finish());
-            i += 1;
-        })
+    fn remove_10(b: &mut test::Bencher) {
+        let mut bf = BloomFilter::new();
+        let mut gen = HashGenerator::default();
+        // Note: this will underflow, and that's ok.
+        b.iter(|| for _ in 0..10 {
+            bf.remove_hash(gen.next())
+        });
     }
 }
diff --git a/components/selectors/lib.rs b/components/selectors/lib.rs
index 568e1aaba70..c2ad24ee73e 100644
--- a/components/selectors/lib.rs
+++ b/components/selectors/lib.rs
@@ -2,6 +2,9 @@
  * 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/. */
 
+// Make |cargo bench| work.
+#![cfg_attr(feature = "unstable", feature(test))]
+
 #[macro_use] extern crate bitflags;
 #[macro_use] extern crate cssparser;
 #[macro_use] extern crate log;
diff --git a/components/style/Cargo.toml b/components/style/Cargo.toml
index 7a365f7bb93..29a77455833 100644
--- a/components/style/Cargo.toml
+++ b/components/style/Cargo.toml
@@ -38,7 +38,7 @@ bitflags = "0.7"
 bit-vec = "0.4.3"
 byteorder = "1.0"
 cfg-if = "0.1.0"
-cssparser = "0.16"
+cssparser = "0.16.1"
 encoding = {version = "0.2", optional = true}
 euclid = "0.15"
 fnv = "1.0"
diff --git a/components/style/animation.rs b/components/style/animation.rs
index 50735801c2a..ae96078c38c 100644
--- a/components/style/animation.rs
+++ b/components/style/animation.rs
@@ -502,6 +502,7 @@ fn compute_style_for_animation_step(context: &SharedStyleContext,
             // as existing browsers don't appear to animate visited styles.
             let computed =
                 properties::apply_declarations(context.stylist.device(),
+                                               previous_style.rules(),
                                                iter,
                                                previous_style,
                                                previous_style,
diff --git a/components/style/bloom.rs b/components/style/bloom.rs
index c63cf88a76e..34b6b608962 100644
--- a/components/style/bloom.rs
+++ b/components/style/bloom.rs
@@ -46,8 +46,39 @@ pub struct StyleBloom<E: TElement> {
     /// The bloom filter per se.
     filter: Box<BloomFilter>,
 
-    /// The stack of elements that this bloom filter contains.
-    elements: Vec<SendElement<E>>,
+    /// The stack of elements that this bloom filter contains, along with the
+    /// number of hashes pushed for each element.
+    elements: SmallVec<[PushedElement<E>; 16]>,
+
+    /// Stack of hashes that have been pushed onto this filter.
+    pushed_hashes: SmallVec<[u32; 64]>,
+}
+
+/// The very rough benchmarks in the selectors crate show clear()
+/// costing about 25 times more than remove_hash(). We use this to implement
+/// clear() more efficiently when only a small number of hashes have been
+/// pushed.
+///
+/// One subtly to note is that remove_hash() will not touch the value
+/// if the filter overflowed. However, overflow can only occur if we
+/// get 255 collisions on the same hash value, and 25 < 255.
+const MEMSET_CLEAR_THRESHOLD: usize = 25;
+
+struct PushedElement<E: TElement> {
+    /// The element that was pushed.
+    element: SendElement<E>,
+
+    /// The number of hashes pushed for the element.
+    num_hashes: usize,
+}
+
+impl<E: TElement> PushedElement<E> {
+    fn new(el: E, num_hashes: usize) -> Self {
+        PushedElement {
+            element: unsafe { SendElement::new(el) },
+            num_hashes: num_hashes,
+        }
+    }
 }
 
 fn each_relevant_element_hash<E, F>(element: E, mut f: F)
@@ -75,7 +106,8 @@ impl<E: TElement> StyleBloom<E> {
     pub fn new() -> Self {
         StyleBloom {
             filter: Box::new(BloomFilter::new()),
-            elements: vec![],
+            elements: Default::default(),
+            pushed_hashes: Default::default(),
         }
     }
 
@@ -98,23 +130,36 @@ impl<E: TElement> StyleBloom<E> {
     /// Same as `push`, but without asserting, in order to use it from
     /// `rebuild`.
     fn push_internal(&mut self, element: E) {
+        let mut count = 0;
         each_relevant_element_hash(element, |hash| {
+            count += 1;
             self.filter.insert_hash(hash);
+            self.pushed_hashes.push(hash);
         });
-        self.elements.push(unsafe { SendElement::new(element) });
+        self.elements.push(PushedElement::new(element, count));
     }
 
     /// Pop the last element in the bloom filter and return it.
+    #[inline]
     fn pop(&mut self) -> Option<E> {
-        let popped = self.elements.pop().map(|el| *el);
+        let (popped_element, num_hashes)  = match self.elements.pop() {
+            None => return None,
+            Some(x) => (*x.element, x.num_hashes),
+        };
 
-        if let Some(popped) = popped {
-            each_relevant_element_hash(popped, |hash| {
-                self.filter.remove_hash(hash);
-            })
+        // Verify that the pushed hashes match the ones we'd get from the element.
+        let mut expected_hashes = vec![];
+        if cfg!(debug_assertions) {
+            each_relevant_element_hash(popped_element, |hash| expected_hashes.push(hash));
         }
 
-        popped
+        for _ in 0..num_hashes {
+            let hash = self.pushed_hashes.pop().unwrap();
+            debug_assert_eq!(expected_hashes.pop().unwrap(), hash);
+            self.filter.remove_hash(hash);
+        }
+
+        Some(popped_element)
     }
 
     /// Returns true if the bloom filter is empty.
@@ -131,21 +176,32 @@ impl<E: TElement> StyleBloom<E> {
 
     /// Clears the bloom filter.
     pub fn clear(&mut self) {
-        self.filter.clear();
         self.elements.clear();
+
+        if self.pushed_hashes.len() > MEMSET_CLEAR_THRESHOLD {
+            self.filter.clear();
+            self.pushed_hashes.clear();
+        } else {
+            for hash in self.pushed_hashes.drain() {
+                self.filter.remove_hash(hash);
+            }
+            debug_assert!(self.filter.is_zeroed());
+        }
     }
 
     /// Rebuilds the bloom filter up to the parent of the given element.
     pub fn rebuild(&mut self, mut element: E) {
         self.clear();
 
+        let mut parents_to_insert = SmallVec::<[E; 16]>::new();
         while let Some(parent) = element.traversal_parent() {
-            self.push_internal(parent);
+            parents_to_insert.push(parent);
             element = parent;
         }
 
-        // Put them in the order we expect, from root to `element`'s parent.
-        self.elements.reverse();
+        for parent in parents_to_insert.drain().rev() {
+            self.push(parent);
+        }
     }
 
     /// In debug builds, asserts that all the parents of `element` are in the
@@ -156,7 +212,7 @@ impl<E: TElement> StyleBloom<E> {
         if cfg!(debug_assertions) {
             let mut checked = 0;
             while let Some(parent) = element.traversal_parent() {
-                assert_eq!(parent, *self.elements[self.elements.len() - 1 - checked]);
+                assert_eq!(parent, *(self.elements[self.elements.len() - 1 - checked].element));
                 element = parent;
                 checked += 1;
             }
@@ -169,7 +225,7 @@ impl<E: TElement> StyleBloom<E> {
     /// (if any) and its ancestors.
     #[inline]
     pub fn current_parent(&self) -> Option<E> {
-        self.elements.last().map(|el| **el)
+        self.elements.last().map(|ref el| *el.element)
     }
 
     /// Insert the parents of an element in the bloom filter, trying to recover
@@ -238,7 +294,7 @@ impl<E: TElement> StyleBloom<E> {
 
         // Let's collect the parents we are going to need to insert once we've
         // found the common one.
-        let mut parents_to_insert = SmallVec::<[E; 8]>::new();
+        let mut parents_to_insert = SmallVec::<[E; 16]>::new();
 
         // If the bloom filter still doesn't have enough elements, the common
         // parent is up in the dom.
@@ -266,7 +322,7 @@ impl<E: TElement> StyleBloom<E> {
         //
         // Thus it's possible with Gecko that we do not find any common
         // ancestor.
-        while **self.elements.last().unwrap() != common_parent {
+        while *(self.elements.last().unwrap().element) != common_parent {
             parents_to_insert.push(common_parent);
             self.pop().unwrap();
             common_parent = match common_parent.traversal_parent() {
@@ -284,7 +340,7 @@ impl<E: TElement> StyleBloom<E> {
 
         // Now the parents match, so insert the stack of elements we have been
         // collecting so far.
-        for parent in parents_to_insert.into_iter().rev() {
+        for parent in parents_to_insert.drain().rev() {
             self.push(parent);
         }
 
diff --git a/components/style/context.rs b/components/style/context.rs
index 96b84ad2ed3..33ff5d61697 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -7,9 +7,10 @@
 #[cfg(feature = "servo")] use animation::Animation;
 use animation::PropertyAnimation;
 use app_units::Au;
+use arrayvec::ArrayVec;
 use bloom::StyleBloom;
 use cache::LRUCache;
-use data::ElementData;
+use data::{EagerPseudoStyles, ElementData};
 use dom::{OpaqueNode, TNode, TElement, SendElement};
 use error_reporting::ParseErrorReporter;
 use euclid::Size2D;
@@ -17,9 +18,10 @@ use fnv::FnvHashMap;
 use font_metrics::FontMetricsProvider;
 #[cfg(feature = "gecko")] use gecko_bindings::structs;
 #[cfg(feature = "servo")] use parking_lot::RwLock;
-#[cfg(feature = "gecko")] use properties::ComputedValues;
-use selector_parser::SnapshotMap;
-use selectors::matching::ElementSelectorFlags;
+use properties::ComputedValues;
+use rule_tree::StrongRuleNode;
+use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, SnapshotMap};
+use selectors::matching::{ElementSelectorFlags, VisitedHandlingMode};
 use shared_lock::StylesheetGuards;
 use sharing::{ValidationData, StyleSharingCandidateCache};
 use std::fmt;
@@ -141,6 +143,423 @@ impl<'a> SharedStyleContext<'a> {
     }
 }
 
+/// The structure holds various intermediate inputs that are eventually used by
+/// by the cascade.
+///
+/// The matching and cascading process stores them in this format temporarily
+/// within the `CurrentElementInfo`. At the end of the cascade, they are folded
+/// down into the main `ComputedValues` to reduce memory usage per element while
+/// still remaining accessible.
+#[derive(Clone)]
+pub struct CascadeInputs {
+    /// The rule node representing the ordered list of rules matched for this
+    /// node.
+    rules: Option<StrongRuleNode>,
+
+    /// The rule node representing the ordered list of rules matched for this
+    /// node if visited, only computed if there's a relevant link for this
+    /// element. A element's "relevant link" is the element being matched if it
+    /// is a link or the nearest ancestor link.
+    visited_rules: Option<StrongRuleNode>,
+
+    /// The element's computed values if visited, only computed if there's a
+    /// relevant link for this element. A element's "relevant link" is the
+    /// element being matched if it is a link or the nearest ancestor link.
+    ///
+    /// We also store a reference to this inside the regular ComputedValues to
+    /// avoid refactoring all APIs to become aware of multiple ComputedValues
+    /// objects.
+    visited_values: Option<Arc<ComputedValues>>,
+}
+
+impl Default for CascadeInputs {
+    fn default() -> Self {
+        CascadeInputs {
+            rules: None,
+            visited_rules: None,
+            visited_values: None,
+        }
+    }
+}
+
+impl CascadeInputs {
+    /// Construct inputs from previous cascade results, if any.
+    fn new_from_style(style: &Arc<ComputedValues>) -> Self {
+        CascadeInputs {
+            rules: style.rules.clone(),
+            visited_rules: style.get_visited_style().and_then(|v| v.rules.clone()),
+            // Values will be re-cascaded if necessary, so this can be None.
+            visited_values: None,
+        }
+    }
+
+    /// Whether there are any rules.  Rules will be present after unvisited
+    /// matching or pulled from a previous cascade if no matching is expected.
+    pub fn has_rules(&self) -> bool {
+        self.rules.is_some()
+    }
+
+    /// Gets a mutable reference to the rule node, if any.
+    pub fn get_rules_mut(&mut self) -> Option<&mut StrongRuleNode> {
+        self.rules.as_mut()
+    }
+
+    /// Gets a reference to the rule node. Panic if the element does not have
+    /// rule node.
+    pub fn rules(&self) -> &StrongRuleNode {
+        self.rules.as_ref().unwrap()
+    }
+
+    /// Sets the rule node depending on visited mode.
+    /// Returns whether the rules changed.
+    pub fn set_rules(&mut self,
+                     visited_handling: VisitedHandlingMode,
+                     rules: StrongRuleNode)
+                     -> bool {
+        match visited_handling {
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
+                unreachable!("We should never try to selector match with \
+                             AllLinksVisitedAndUnvisited");
+            },
+            VisitedHandlingMode::AllLinksUnvisited => self.set_unvisited_rules(rules),
+            VisitedHandlingMode::RelevantLinkVisited => self.set_visited_rules(rules),
+        }
+    }
+
+    /// Sets the unvisited rule node, and returns whether it changed.
+    fn set_unvisited_rules(&mut self, rules: StrongRuleNode) -> bool {
+        if let Some(ref old_rules) = self.rules {
+            if *old_rules == rules {
+                return false
+            }
+        }
+        self.rules = Some(rules);
+        true
+    }
+
+    /// Whether there are any visited rules.  Visited rules will be present
+    /// after visited matching or pulled from a previous cascade (assuming there
+    /// was a relevant link at the time) if no matching is expected.
+    pub fn has_visited_rules(&self) -> bool {
+        self.visited_rules.is_some()
+    }
+
+    /// Gets a reference to the visited rule node, if any.
+    pub fn get_visited_rules(&self) -> Option<&StrongRuleNode> {
+        self.visited_rules.as_ref()
+    }
+
+    /// Gets a mutable reference to the visited rule node, if any.
+    pub fn get_visited_rules_mut(&mut self) -> Option<&mut StrongRuleNode> {
+        self.visited_rules.as_mut()
+    }
+
+    /// Gets a reference to the visited rule node. Panic if the element does not
+    /// have visited rule node.
+    pub fn visited_rules(&self) -> &StrongRuleNode {
+        self.visited_rules.as_ref().unwrap()
+    }
+
+    /// Sets the visited rule node, and returns whether it changed.
+    fn set_visited_rules(&mut self, rules: StrongRuleNode) -> bool {
+        if let Some(ref old_rules) = self.visited_rules {
+            if *old_rules == rules {
+                return false
+            }
+        }
+        self.visited_rules = Some(rules);
+        true
+    }
+
+    /// Takes the visited rule node.
+    pub fn take_visited_rules(&mut self) -> Option<StrongRuleNode> {
+        self.visited_rules.take()
+    }
+
+    /// Gets a reference to the visited computed values. Panic if the element
+    /// does not have visited computed values.
+    pub fn visited_values(&self) -> &Arc<ComputedValues> {
+        self.visited_values.as_ref().unwrap()
+    }
+
+    /// Sets the visited computed values.
+    pub fn set_visited_values(&mut self, values: Arc<ComputedValues>) {
+        self.visited_values = Some(values);
+    }
+
+    /// Take the visited computed values.
+    pub fn take_visited_values(&mut self) -> Option<Arc<ComputedValues>> {
+        self.visited_values.take()
+    }
+
+    /// Clone the visited computed values Arc.  Used to store a reference to the
+    /// visited values inside the regular values.
+    pub fn clone_visited_values(&self) -> Option<Arc<ComputedValues>> {
+        self.visited_values.clone()
+    }
+}
+
+// We manually implement Debug for CascadeInputs so that we can avoid the
+// verbose stringification of ComputedValues for normal logging.
+impl fmt::Debug for CascadeInputs {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "CascadeInputs {{ rules: {:?}, visited_rules: {:?}, .. }}",
+               self.rules, self.visited_rules)
+    }
+}
+
+/// A list of cascade inputs for eagerly-cascaded pseudo-elements.
+/// The list is stored inline.
+#[derive(Debug)]
+pub struct EagerPseudoCascadeInputs(Option<[Option<CascadeInputs>; EAGER_PSEUDO_COUNT]>);
+
+// Manually implement `Clone` here because the derived impl of `Clone` for
+// array types assumes the value inside is `Copy`.
+impl Clone for EagerPseudoCascadeInputs {
+    fn clone(&self) -> Self {
+        if self.0.is_none() {
+            return EagerPseudoCascadeInputs(None)
+        }
+        let self_inputs = self.0.as_ref().unwrap();
+        let mut inputs: [Option<CascadeInputs>; EAGER_PSEUDO_COUNT] = Default::default();
+        for i in 0..EAGER_PSEUDO_COUNT {
+            inputs[i] = self_inputs[i].clone();
+        }
+        EagerPseudoCascadeInputs(Some(inputs))
+    }
+}
+
+impl EagerPseudoCascadeInputs {
+    /// Construct inputs from previous cascade results, if any.
+    fn new_from_style(styles: &EagerPseudoStyles) -> Self {
+        EagerPseudoCascadeInputs(styles.0.as_ref().map(|styles| {
+            let mut inputs: [Option<CascadeInputs>; EAGER_PSEUDO_COUNT] = Default::default();
+            for i in 0..EAGER_PSEUDO_COUNT {
+                inputs[i] = styles[i].as_ref().map(|s| CascadeInputs::new_from_style(s));
+            }
+            inputs
+        }))
+    }
+
+    /// Returns whether there are any pseudo inputs.
+    pub fn is_empty(&self) -> bool {
+        self.0.is_none()
+    }
+
+    /// Returns a reference to the inputs for a given eager pseudo, if they exist.
+    pub fn get(&self, pseudo: &PseudoElement) -> Option<&CascadeInputs> {
+        debug_assert!(pseudo.is_eager());
+        self.0.as_ref().and_then(|p| p[pseudo.eager_index()].as_ref())
+    }
+
+    /// Returns a mutable reference to the inputs for a given eager pseudo, if they exist.
+    pub fn get_mut(&mut self, pseudo: &PseudoElement) -> Option<&mut CascadeInputs> {
+        debug_assert!(pseudo.is_eager());
+        self.0.as_mut().and_then(|p| p[pseudo.eager_index()].as_mut())
+    }
+
+    /// Returns true if the EagerPseudoCascadeInputs has a inputs for |pseudo|.
+    pub fn has(&self, pseudo: &PseudoElement) -> bool {
+        self.get(pseudo).is_some()
+    }
+
+    /// Inserts a pseudo-element. The pseudo-element must not already exist.
+    pub fn insert(&mut self, pseudo: &PseudoElement, inputs: CascadeInputs) {
+        debug_assert!(!self.has(pseudo));
+        if self.0.is_none() {
+            self.0 = Some(Default::default());
+        }
+        self.0.as_mut().unwrap()[pseudo.eager_index()] = Some(inputs);
+    }
+
+    /// Removes a pseudo-element inputs if they exist, and returns it.
+    pub fn take(&mut self, pseudo: &PseudoElement) -> Option<CascadeInputs> {
+        let result = match self.0.as_mut() {
+            None => return None,
+            Some(arr) => arr[pseudo.eager_index()].take(),
+        };
+        let empty = self.0.as_ref().unwrap().iter().all(|x| x.is_none());
+        if empty {
+            self.0 = None;
+        }
+        result
+    }
+
+    /// Returns a list of the pseudo-elements.
+    pub fn keys(&self) -> ArrayVec<[PseudoElement; EAGER_PSEUDO_COUNT]> {
+        let mut v = ArrayVec::new();
+        if let Some(ref arr) = self.0 {
+            for i in 0..EAGER_PSEUDO_COUNT {
+                if arr[i].is_some() {
+                    v.push(PseudoElement::from_eager_index(i));
+                }
+            }
+        }
+        v
+    }
+
+    /// Adds the unvisited rule node for a given pseudo-element, which may or
+    /// may not exist.
+    ///
+    /// Returns true if the pseudo-element is new.
+    fn add_unvisited_rules(&mut self,
+                           pseudo: &PseudoElement,
+                           rules: StrongRuleNode)
+                           -> bool {
+        if let Some(mut inputs) = self.get_mut(pseudo) {
+            inputs.set_unvisited_rules(rules);
+            return false
+        }
+        let mut inputs = CascadeInputs::default();
+        inputs.set_unvisited_rules(rules);
+        self.insert(pseudo, inputs);
+        true
+    }
+
+    /// Remove the unvisited rule node for a given pseudo-element, which may or
+    /// may not exist. Since removing the rule node implies we don't need any
+    /// other data for the pseudo, take the entire pseudo if found.
+    ///
+    /// Returns true if the pseudo-element was removed.
+    fn remove_unvisited_rules(&mut self, pseudo: &PseudoElement) -> bool {
+        self.take(pseudo).is_some()
+    }
+
+    /// Adds the visited rule node for a given pseudo-element.  It is assumed to
+    /// already exist because unvisited inputs should have been added first.
+    ///
+    /// Returns true if the pseudo-element is new.  (Always false, but returns a
+    /// bool for parity with `add_unvisited_rules`.)
+    fn add_visited_rules(&mut self,
+                         pseudo: &PseudoElement,
+                         rules: StrongRuleNode)
+                         -> bool {
+        debug_assert!(self.has(pseudo));
+        let mut inputs = self.get_mut(pseudo).unwrap();
+        inputs.set_visited_rules(rules);
+        false
+    }
+
+    /// Remove the visited rule node for a given pseudo-element, which may or
+    /// may not exist.
+    ///
+    /// Returns true if the psuedo-element was removed. (Always false, but
+    /// returns a bool for parity with `remove_unvisited_rules`.)
+    fn remove_visited_rules(&mut self, pseudo: &PseudoElement) -> bool {
+        if let Some(mut inputs) = self.get_mut(pseudo) {
+            inputs.take_visited_rules();
+        }
+        false
+    }
+
+    /// Adds a rule node for a given pseudo-element, which may or may not exist.
+    /// The type of rule node depends on the visited mode.
+    ///
+    /// Returns true if the pseudo-element is new.
+    pub fn add_rules(&mut self,
+                     pseudo: &PseudoElement,
+                     visited_handling: VisitedHandlingMode,
+                     rules: StrongRuleNode)
+                     -> bool {
+        match visited_handling {
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
+                unreachable!("We should never try to selector match with \
+                             AllLinksVisitedAndUnvisited");
+            },
+            VisitedHandlingMode::AllLinksUnvisited => {
+                self.add_unvisited_rules(&pseudo, rules)
+            },
+            VisitedHandlingMode::RelevantLinkVisited => {
+                self.add_visited_rules(&pseudo, rules)
+            },
+        }
+    }
+
+    /// Removes a rule node for a given pseudo-element, which may or may not
+    /// exist. The type of rule node depends on the visited mode.
+    ///
+    /// Returns true if the psuedo-element was removed.
+    pub fn remove_rules(&mut self,
+                        pseudo: &PseudoElement,
+                        visited_handling: VisitedHandlingMode)
+                        -> bool {
+        match visited_handling {
+            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
+                unreachable!("We should never try to selector match with \
+                             AllLinksVisitedAndUnvisited");
+            },
+            VisitedHandlingMode::AllLinksUnvisited => {
+                self.remove_unvisited_rules(&pseudo)
+            },
+            VisitedHandlingMode::RelevantLinkVisited => {
+                self.remove_visited_rules(&pseudo)
+            },
+        }
+    }
+}
+
+/// The cascade inputs associated with a node, including those for any
+/// pseudo-elements.
+///
+/// The matching and cascading process stores them in this format temporarily
+/// within the `CurrentElementInfo`. At the end of the cascade, they are folded
+/// down into the main `ComputedValues` to reduce memory usage per element while
+/// still remaining accessible.
+#[derive(Clone, Debug)]
+pub struct ElementCascadeInputs {
+    /// The element's cascade inputs.
+    pub primary: Option<CascadeInputs>,
+    /// A list of the inputs for the element's eagerly-cascaded pseudo-elements.
+    pub pseudos: EagerPseudoCascadeInputs,
+}
+
+impl Default for ElementCascadeInputs {
+    /// Construct an empty `ElementCascadeInputs`.
+    fn default() -> Self {
+        ElementCascadeInputs {
+            primary: None,
+            pseudos: EagerPseudoCascadeInputs(None),
+        }
+    }
+}
+
+impl ElementCascadeInputs {
+    /// Construct inputs from previous cascade results, if any.
+    pub fn new_from_element_data(data: &ElementData) -> Self {
+        if !data.has_styles() {
+            return ElementCascadeInputs::default()
+        }
+        ElementCascadeInputs {
+            primary: Some(CascadeInputs::new_from_style(data.styles.primary())),
+            pseudos: EagerPseudoCascadeInputs::new_from_style(&data.styles.pseudos),
+        }
+    }
+
+    /// Returns whether we have primary inputs.
+    pub fn has_primary(&self) -> bool {
+        self.primary.is_some()
+    }
+
+    /// Gets the primary inputs. Panic if unavailable.
+    pub fn primary(&self) -> &CascadeInputs {
+        self.primary.as_ref().unwrap()
+    }
+
+    /// Gets the mutable primary inputs. Panic if unavailable.
+    pub fn primary_mut(&mut self) -> &mut CascadeInputs {
+        self.primary.as_mut().unwrap()
+    }
+
+    /// Ensure primary inputs exist and create them if they do not.
+    /// Returns a mutable reference to the primary inputs.
+    pub fn ensure_primary(&mut self) -> &mut CascadeInputs {
+        if self.primary.is_none() {
+            self.primary = Some(CascadeInputs::default());
+        }
+        self.primary.as_mut().unwrap()
+    }
+}
+
 /// Information about the current element being processed. We group this
 /// together into a single struct within ThreadLocalStyleContext so that we can
 /// instantiate and destroy it easily at the beginning and end of element
@@ -157,6 +576,11 @@ pub struct CurrentElementInfo {
     /// A Vec of possibly expired animations. Used only by Servo.
     #[allow(dead_code)]
     pub possibly_expired_animations: Vec<PropertyAnimation>,
+    /// Temporary storage for various intermediate inputs that are eventually
+    /// used by by the cascade. At the end of the cascade, they are folded down
+    /// into the main `ComputedValues` to reduce memory usage per element while
+    /// still remaining accessible.
+    pub cascade_inputs: ElementCascadeInputs,
 }
 
 /// Statistics gathered during the traversal. We gather statistics on each
@@ -454,6 +878,7 @@ impl<E: TElement> ThreadLocalStyleContext<E> {
             is_initial_style: !data.has_styles(),
             validation_data: ValidationData::default(),
             possibly_expired_animations: Vec::new(),
+            cascade_inputs: ElementCascadeInputs::default(),
         });
     }
 
@@ -498,6 +923,24 @@ pub struct StyleContext<'a, E: TElement + 'a> {
     pub thread_local: &'a mut ThreadLocalStyleContext<E>,
 }
 
+impl<'a, E: TElement + 'a> StyleContext<'a, E> {
+    /// Returns a reference to the cascade inputs.  Panics if there is no
+    /// `CurrentElementInfo`.
+    pub fn cascade_inputs(&self) -> &ElementCascadeInputs {
+        &self.thread_local.current_element_info
+             .as_ref().unwrap()
+             .cascade_inputs
+    }
+
+    /// Returns a mutable reference to the cascade inputs.  Panics if there is
+    /// no `CurrentElementInfo`.
+    pub fn cascade_inputs_mut(&mut self) -> &mut ElementCascadeInputs {
+        &mut self.thread_local.current_element_info
+                 .as_mut().unwrap()
+                 .cascade_inputs
+    }
+}
+
 /// Why we're doing reflow.
 #[derive(PartialEq, Copy, Clone, Debug)]
 pub enum ReflowGoal {
diff --git a/components/style/data.rs b/components/style/data.rs
index 0363d397d74..b50b2170191 100644
--- a/components/style/data.rs
+++ b/components/style/data.rs
@@ -12,141 +12,113 @@ use properties::{AnimationRules, ComputedValues, PropertyDeclarationBlock};
 use properties::longhands::display::computed_value as display;
 use rule_tree::StrongRuleNode;
 use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, RestyleDamage};
-use selectors::matching::VisitedHandlingMode;
 use shared_lock::{Locked, StylesheetGuards};
-use std::fmt;
 use stylearc::Arc;
 
-/// The structure that represents the result of style computation. This is
-/// effectively a tuple of rules and computed values, that is, the rule node,
-/// and the result of computing that rule node's rules, the `ComputedValues`.
-#[derive(Clone)]
-pub struct ComputedStyle {
-    /// The rule node representing the ordered list of rules matched for this
-    /// node.
-    pub rules: StrongRuleNode,
-
-    /// The computed values for each property obtained by cascading the
-    /// matched rules. This can only be none during a transient interval of
-    /// the styling algorithm, and callers can safely unwrap it.
-    pub values: Option<Arc<ComputedValues>>,
-
-    /// The rule node representing the ordered list of rules matched for this
-    /// node if visited, only computed if there's a relevant link for this
-    /// element. A element's "relevant link" is the element being matched if it
-    /// is a link or the nearest ancestor link.
-    visited_rules: Option<StrongRuleNode>,
-
-    /// The element's computed values if visited, only computed if there's a
-    /// relevant link for this element. A element's "relevant link" is the
-    /// element being matched if it is a link or the nearest ancestor link.
-    ///
-    /// We also store a reference to this inside the regular ComputedValues to
-    /// avoid refactoring all APIs to become aware of multiple ComputedValues
-    /// objects.
-    visited_values: Option<Arc<ComputedValues>>,
-}
-
-impl ComputedStyle {
-    /// Trivially construct a new `ComputedStyle`.
-    pub fn new(rules: StrongRuleNode, values: Arc<ComputedValues>) -> Self {
-        ComputedStyle {
-            rules: rules,
-            values: Some(values),
-            visited_rules: None,
-            visited_values: None,
-        }
+bitflags! {
+    flags RestyleFlags: u8 {
+        /// Whether the styles changed for this restyle.
+        const WAS_RESTYLED = 1 << 0,
+        /// Whether we reframed/reconstructed any ancestor or self.
+        const ANCESTOR_WAS_RECONSTRUCTED = 1 << 1,
     }
+}
 
-    /// Constructs a partial ComputedStyle, whose ComputedVaues will be filled
-    /// in later.
-    pub fn new_partial(rules: StrongRuleNode) -> Self {
-        ComputedStyle {
-            rules: rules,
-            values: None,
-            visited_rules: None,
-            visited_values: None,
-        }
-    }
+/// Transient data used by the restyle algorithm. This structure is instantiated
+/// either before or during restyle traversal, and is cleared at the end of node
+/// processing.
+#[derive(Debug)]
+pub struct RestyleData {
+    /// The restyle hint, which indicates whether selectors need to be rematched
+    /// for this element, its children, and its descendants.
+    pub hint: RestyleHint,
 
-    /// Returns a reference to the ComputedValues. The values can only be null during
-    /// the styling algorithm, so this is safe to call elsewhere.
-    pub fn values(&self) -> &Arc<ComputedValues> {
-        self.values.as_ref().unwrap()
-    }
+    /// A few flags to have in mind.
+    flags: RestyleFlags,
 
-    /// Whether there are any visited rules.
-    pub fn has_visited_rules(&self) -> bool {
-        self.visited_rules.is_some()
-    }
+    /// The restyle damage, indicating what kind of layout changes are required
+    /// afte restyling.
+    pub damage: RestyleDamage,
+}
 
-    /// Gets a reference to the visited rule node, if any.
-    pub fn get_visited_rules(&self) -> Option<&StrongRuleNode> {
-        self.visited_rules.as_ref()
+impl Default for RestyleData {
+    fn default() -> Self {
+        Self::new()
     }
+}
 
-    /// Gets a mutable reference to the visited rule node, if any.
-    pub fn get_visited_rules_mut(&mut self) -> Option<&mut StrongRuleNode> {
-        self.visited_rules.as_mut()
+impl RestyleData {
+    fn new() -> Self {
+        Self {
+            hint: RestyleHint::empty(),
+            flags: RestyleFlags::empty(),
+            damage: RestyleDamage::empty(),
+        }
     }
 
-    /// Gets a reference to the visited rule node. Panic if the element does not
-    /// have visited rule node.
-    pub fn visited_rules(&self) -> &StrongRuleNode {
-        self.get_visited_rules().unwrap()
+    /// Clear all the restyle state associated with this element.
+    fn clear(&mut self) {
+        *self = Self::new();
     }
 
-    /// Sets the visited rule node, and returns whether it changed.
-    pub fn set_visited_rules(&mut self, rules: StrongRuleNode) -> bool {
-        if let Some(ref old_rules) = self.visited_rules {
-            if *old_rules == rules {
-                return false
-            }
-        }
-        self.visited_rules = Some(rules);
-        true
+    /// Returns whether this element or any ancestor is going to be
+    /// reconstructed.
+    pub fn reconstructed_self_or_ancestor(&self) -> bool {
+        self.reconstructed_ancestor() ||
+        self.damage.contains(RestyleDamage::reconstruct())
     }
 
-    /// Takes the visited rule node.
-    pub fn take_visited_rules(&mut self) -> Option<StrongRuleNode> {
-        self.visited_rules.take()
+    /// Returns whether any ancestor of this element was restyled.
+    fn reconstructed_ancestor(&self) -> bool {
+        self.flags.contains(ANCESTOR_WAS_RECONSTRUCTED)
     }
 
-    /// Gets a reference to the visited computed values. Panic if the element
-    /// does not have visited computed values.
-    pub fn visited_values(&self) -> &Arc<ComputedValues> {
-        self.visited_values.as_ref().unwrap()
+    /// Sets the flag that tells us whether we've reconstructed an ancestor.
+    pub fn set_reconstructed_ancestor(&mut self) {
+        // If it weren't for animation-only traversals, we could assert
+        // `!self.reconstructed_ancestor()` here.
+        self.flags.insert(ANCESTOR_WAS_RECONSTRUCTED);
     }
 
-    /// Sets the visited computed values.
-    pub fn set_visited_values(&mut self, values: Arc<ComputedValues>) {
-        self.visited_values = Some(values);
+    /// Mark this element as restyled, which is useful to know whether we need
+    /// to do a post-traversal.
+    pub fn set_restyled(&mut self) {
+        self.flags.insert(WAS_RESTYLED);
     }
 
-    /// Take the visited computed values.
-    pub fn take_visited_values(&mut self) -> Option<Arc<ComputedValues>> {
-        self.visited_values.take()
+    /// Mark this element as restyled, which is useful to know whether we need
+    /// to do a post-traversal.
+    pub fn is_restyle(&self) -> bool {
+        self.flags.contains(WAS_RESTYLED)
     }
 
-    /// Clone the visited computed values Arc.  Used to store a reference to the
-    /// visited values inside the regular values.
-    pub fn clone_visited_values(&self) -> Option<Arc<ComputedValues>> {
-        self.visited_values.clone()
+    /// Returns whether this element has been part of a restyle.
+    pub fn contains_restyle_data(&self) -> bool {
+        self.is_restyle() || !self.hint.is_empty() || !self.damage.is_empty()
     }
 }
 
-// We manually implement Debug for ComputedStyle so that we can avoid the
-// verbose stringification of ComputedValues for normal logging.
-impl fmt::Debug for ComputedStyle {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "ComputedStyle {{ rules: {:?}, values: {{..}} }}", self.rules)
+/// A list of styles for eagerly-cascaded pseudo-elements.
+/// Lazily-allocated.
+#[derive(Debug)]
+pub struct EagerPseudoStyles(pub Option<Box<[Option<Arc<ComputedValues>>; EAGER_PSEUDO_COUNT]>>);
+
+// Manually implement `Clone` here because the derived impl of `Clone` for
+// array types assumes the value inside is `Copy`.
+impl Clone for EagerPseudoStyles {
+    fn clone(&self) -> Self {
+        if self.0.is_none() {
+            return EagerPseudoStyles(None)
+        }
+        let self_values = self.0.as_ref().unwrap();
+        let mut values: [Option<Arc<ComputedValues>>; EAGER_PSEUDO_COUNT] = Default::default();
+        for i in 0..EAGER_PSEUDO_COUNT {
+            values[i] = self_values[i].clone();
+        }
+        EagerPseudoStyles(Some(Box::new(values)))
     }
 }
 
-/// A list of styles for eagerly-cascaded pseudo-elements. Lazily-allocated.
-#[derive(Clone, Debug)]
-pub struct EagerPseudoStyles(Option<Box<[Option<ComputedStyle>]>>);
-
 impl EagerPseudoStyles {
     /// Returns whether there are any pseudo styles.
     pub fn is_empty(&self) -> bool {
@@ -154,33 +126,38 @@ impl EagerPseudoStyles {
     }
 
     /// Returns a reference to the style for a given eager pseudo, if it exists.
-    pub fn get(&self, pseudo: &PseudoElement) -> Option<&ComputedStyle> {
+    pub fn get(&self, pseudo: &PseudoElement) -> Option<&Arc<ComputedValues>> {
         debug_assert!(pseudo.is_eager());
         self.0.as_ref().and_then(|p| p[pseudo.eager_index()].as_ref())
     }
 
     /// Returns a mutable reference to the style for a given eager pseudo, if it exists.
-    pub fn get_mut(&mut self, pseudo: &PseudoElement) -> Option<&mut ComputedStyle> {
+    pub fn get_mut(&mut self, pseudo: &PseudoElement) -> Option<&mut Arc<ComputedValues>> {
         debug_assert!(pseudo.is_eager());
         self.0.as_mut().and_then(|p| p[pseudo.eager_index()].as_mut())
     }
 
-    /// Returns true if the EagerPseudoStyles has a ComputedStyle for |pseudo|.
+    /// Returns true if the EagerPseudoStyles has the style for |pseudo|.
     pub fn has(&self, pseudo: &PseudoElement) -> bool {
         self.get(pseudo).is_some()
     }
 
-    /// Inserts a pseudo-element. The pseudo-element must not already exist.
-    pub fn insert(&mut self, pseudo: &PseudoElement, style: ComputedStyle) {
-        debug_assert!(!self.has(pseudo));
+    /// Sets the style for the eager pseudo.
+    pub fn set(&mut self, pseudo: &PseudoElement, value: Arc<ComputedValues>) {
         if self.0.is_none() {
-            self.0 = Some(vec![None; EAGER_PSEUDO_COUNT].into_boxed_slice());
+            self.0 = Some(Box::new(Default::default()));
         }
-        self.0.as_mut().unwrap()[pseudo.eager_index()] = Some(style);
+        self.0.as_mut().unwrap()[pseudo.eager_index()] = Some(value);
+    }
+
+    /// Inserts a pseudo-element. The pseudo-element must not already exist.
+    pub fn insert(&mut self, pseudo: &PseudoElement, value: Arc<ComputedValues>) {
+        debug_assert!(!self.has(pseudo));
+        self.set(pseudo, value);
     }
 
     /// Removes a pseudo-element style if it exists, and returns it.
-    fn take(&mut self, pseudo: &PseudoElement) -> Option<ComputedStyle> {
+    pub fn take(&mut self, pseudo: &PseudoElement) -> Option<Arc<ComputedValues>> {
         let result = match self.0.as_mut() {
             None => return None,
             Some(arr) => arr[pseudo.eager_index()].take(),
@@ -205,106 +182,8 @@ impl EagerPseudoStyles {
         v
     }
 
-    /// Adds the unvisited rule node for a given pseudo-element, which may or
-    /// may not exist.
-    ///
-    /// Returns true if the pseudo-element is new.
-    fn add_unvisited_rules(&mut self,
-                           pseudo: &PseudoElement,
-                           rules: StrongRuleNode)
-                           -> bool {
-        if let Some(mut style) = self.get_mut(pseudo) {
-            style.rules = rules;
-            return false
-        }
-        self.insert(pseudo, ComputedStyle::new_partial(rules));
-        true
-    }
-
-    /// Remove the unvisited rule node for a given pseudo-element, which may or
-    /// may not exist. Since removing the rule node implies we don't need any
-    /// other data for the pseudo, take the entire pseudo if found.
-    ///
-    /// Returns true if the pseudo-element was removed.
-    fn remove_unvisited_rules(&mut self, pseudo: &PseudoElement) -> bool {
-        self.take(pseudo).is_some()
-    }
-
-    /// Adds the visited rule node for a given pseudo-element.  It is assumed to
-    /// already exist because unvisited styles should have been added first.
-    ///
-    /// Returns true if the pseudo-element is new.  (Always false, but returns a
-    /// bool for parity with `add_unvisited_rules`.)
-    fn add_visited_rules(&mut self,
-                         pseudo: &PseudoElement,
-                         rules: StrongRuleNode)
-                         -> bool {
-        debug_assert!(self.has(pseudo));
-        let mut style = self.get_mut(pseudo).unwrap();
-        style.set_visited_rules(rules);
-        false
-    }
-
-    /// Remove the visited rule node for a given pseudo-element, which may or
-    /// may not exist.
-    ///
-    /// Returns true if the psuedo-element was removed. (Always false, but
-    /// returns a bool for parity with `remove_unvisited_rules`.)
-    fn remove_visited_rules(&mut self, pseudo: &PseudoElement) -> bool {
-        if let Some(mut style) = self.get_mut(pseudo) {
-            style.take_visited_rules();
-        }
-        false
-    }
-
-    /// Adds a rule node for a given pseudo-element, which may or may not exist.
-    /// The type of rule node depends on the visited mode.
-    ///
-    /// Returns true if the pseudo-element is new.
-    pub fn add_rules(&mut self,
-                     pseudo: &PseudoElement,
-                     visited_handling: VisitedHandlingMode,
-                     rules: StrongRuleNode)
-                     -> bool {
-        match visited_handling {
-            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
-                unreachable!("We should never try to selector match with \
-                             AllLinksVisitedAndUnvisited");
-            },
-            VisitedHandlingMode::AllLinksUnvisited => {
-                self.add_unvisited_rules(&pseudo, rules)
-            },
-            VisitedHandlingMode::RelevantLinkVisited => {
-                self.add_visited_rules(&pseudo, rules)
-            },
-        }
-    }
-
-    /// Removes a rule node for a given pseudo-element, which may or may not
-    /// exist. The type of rule node depends on the visited mode.
-    ///
-    /// Returns true if the psuedo-element was removed.
-    pub fn remove_rules(&mut self,
-                        pseudo: &PseudoElement,
-                        visited_handling: VisitedHandlingMode)
-                        -> bool {
-        match visited_handling {
-            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
-                unreachable!("We should never try to selector match with \
-                             AllLinksVisitedAndUnvisited");
-            },
-            VisitedHandlingMode::AllLinksUnvisited => {
-                self.remove_unvisited_rules(&pseudo)
-            },
-            VisitedHandlingMode::RelevantLinkVisited => {
-                self.remove_visited_rules(&pseudo)
-            },
-        }
-    }
-
-    /// Returns whether this EagerPseudoStyles has the same set of
-    /// pseudos as the given one.
-    pub fn has_same_pseudos_as(&self, other: &EagerPseudoStyles) -> bool {
+    /// Returns whether this map has the same set of pseudos as the given one.
+    pub fn has_same_pseudos_as(&self, other: &Self) -> bool {
         // We could probably just compare self.keys() to other.keys(), but that
         // seems like it'll involve a bunch more moving stuff around and
         // whatnot.
@@ -328,100 +207,40 @@ impl EagerPseudoStyles {
 #[derive(Clone, Debug)]
 pub struct ElementStyles {
     /// The element's style.
-    pub primary: ComputedStyle,
+    pub primary: Option<Arc<ComputedValues>>,
     /// A list of the styles for the element's eagerly-cascaded pseudo-elements.
     pub pseudos: EagerPseudoStyles,
 }
 
-impl ElementStyles {
-    /// Trivially construct a new `ElementStyles`.
-    pub fn new(primary: ComputedStyle) -> Self {
+impl Default for ElementStyles {
+    /// Construct an empty `ElementStyles`.
+    fn default() -> Self {
         ElementStyles {
-            primary: primary,
+            primary: None,
             pseudos: EagerPseudoStyles(None),
         }
     }
-
-    /// Whether this element `display` value is `none`.
-    pub fn is_display_none(&self) -> bool {
-        self.primary.values().get_box().clone_display() == display::T::none
-    }
-}
-
-bitflags! {
-    flags RestyleFlags: u8 {
-        /// Whether the styles changed for this restyle.
-        const WAS_RESTYLED = 1 << 0,
-        /// Whether we reframed/reconstructed any ancestor or self.
-        const ANCESTOR_WAS_RECONSTRUCTED = 1 << 1,
-    }
-}
-
-/// Transient data used by the restyle algorithm. This structure is instantiated
-/// either before or during restyle traversal, and is cleared at the end of node
-/// processing.
-#[derive(Debug)]
-pub struct RestyleData {
-    /// The restyle hint, which indicates whether selectors need to be rematched
-    /// for this element, its children, and its descendants.
-    pub hint: RestyleHint,
-
-    /// A few flags to have in mind.
-    flags: RestyleFlags,
-
-    /// The restyle damage, indicating what kind of layout changes are required
-    /// afte restyling.
-    pub damage: RestyleDamage,
 }
 
-impl RestyleData {
-    fn new() -> Self {
-        Self {
-            hint: RestyleHint::empty(),
-            flags: RestyleFlags::empty(),
-            damage: RestyleDamage::empty(),
-        }
-    }
-
-    /// Clear all the restyle state associated with this element.
-    fn clear(&mut self) {
-        *self = Self::new();
-    }
-
-    /// Returns whether this element or any ancestor is going to be
-    /// reconstructed.
-    pub fn reconstructed_self_or_ancestor(&self) -> bool {
-        self.reconstructed_ancestor() ||
-        self.damage.contains(RestyleDamage::reconstruct())
-    }
-
-    /// Returns whether any ancestor of this element was restyled.
-    fn reconstructed_ancestor(&self) -> bool {
-        self.flags.contains(ANCESTOR_WAS_RECONSTRUCTED)
-    }
-
-    /// Sets the flag that tells us whether we've reconstructed an ancestor.
-    pub fn set_reconstructed_ancestor(&mut self) {
-        // If it weren't for animation-only traversals, we could assert
-        // `!self.reconstructed_ancestor()` here.
-        self.flags.insert(ANCESTOR_WAS_RECONSTRUCTED);
+impl ElementStyles {
+    /// Returns the primary style.
+    pub fn get_primary(&self) -> Option<&Arc<ComputedValues>> {
+        self.primary.as_ref()
     }
 
-    /// Mark this element as restyled, which is useful to know whether we need
-    /// to do a post-traversal.
-    pub fn set_restyled(&mut self) {
-        self.flags.insert(WAS_RESTYLED);
+    /// Returns the mutable primary style.
+    pub fn get_primary_mut(&mut self) -> Option<&mut Arc<ComputedValues>> {
+        self.primary.as_mut()
     }
 
-    /// Mark this element as restyled, which is useful to know whether we need
-    /// to do a post-traversal.
-    pub fn is_restyle(&self) -> bool {
-        self.flags.contains(WAS_RESTYLED)
+    /// Returns the primary style.  Panic if no style available.
+    pub fn primary(&self) -> &Arc<ComputedValues> {
+        self.primary.as_ref().unwrap()
     }
 
-    /// Returns whether this element has been part of a restyle.
-    pub fn contains_restyle_data(&self) -> bool {
-        self.is_restyle() || !self.hint.is_empty() || !self.damage.is_empty()
+    /// Whether this element `display` value is `none`.
+    pub fn is_display_none(&self) -> bool {
+        self.primary().get_box().clone_display() == display::T::none
     }
 }
 
@@ -430,10 +249,10 @@ impl RestyleData {
 /// In Gecko, this hangs directly off the Element. Servo, this is embedded
 /// inside of layout data, which itself hangs directly off the Element. In
 /// both cases, it is wrapped inside an AtomicRefCell to ensure thread safety.
-#[derive(Debug)]
+#[derive(Debug, Default)]
 pub struct ElementData {
-    /// The computed styles for the element and its pseudo-elements.
-    styles: Option<ElementStyles>,
+    /// The styles for the element and its pseudo-elements.
+    pub styles: ElementStyles,
 
     /// Restyle state.
     pub restyle: RestyleData,
@@ -458,7 +277,7 @@ impl ElementData {
     pub fn styles_and_restyle_mut(
         &mut self
     ) -> (&mut ElementStyles, &mut RestyleData) {
-        (self.styles.as_mut().unwrap(),
+        (&mut self.styles,
          &mut self.restyle)
     }
 
@@ -492,18 +311,9 @@ impl ElementData {
         }
     }
 
-
-    /// Trivially construct an ElementData.
-    pub fn new(existing: Option<ElementStyles>) -> Self {
-        ElementData {
-            styles: existing,
-            restyle: RestyleData::new(),
-        }
-    }
-
-    /// Returns true if this element has a computed style.
+    /// Returns true if this element has styles.
     pub fn has_styles(&self) -> bool {
-        self.styles.is_some()
+        self.styles.primary.is_some()
     }
 
     /// Returns whether we have any outstanding style invalidation.
@@ -550,47 +360,6 @@ impl ElementData {
         return RestyleKind::CascadeOnly;
     }
 
-    /// Gets the element styles, if any.
-    pub fn get_styles(&self) -> Option<&ElementStyles> {
-        self.styles.as_ref()
-    }
-
-    /// Gets the element styles. Panic if the element has never been styled.
-    pub fn styles(&self) -> &ElementStyles {
-        self.styles.as_ref().expect("Calling styles() on unstyled ElementData")
-    }
-
-    /// Gets a mutable reference to the element styles, if any.
-    pub fn get_styles_mut(&mut self) -> Option<&mut ElementStyles> {
-        self.styles.as_mut()
-    }
-
-    /// Gets a mutable reference to the element styles. Panic if the element has
-    /// never been styled.
-    pub fn styles_mut(&mut self) -> &mut ElementStyles {
-        self.styles.as_mut().expect("Calling styles_mut() on unstyled ElementData")
-    }
-
-    /// Sets the computed element styles.
-    pub fn set_styles(&mut self, styles: ElementStyles) {
-        self.styles = Some(styles);
-    }
-
-    /// Sets the computed element rules, and returns whether the rules changed.
-    pub fn set_primary_rules(&mut self, rules: StrongRuleNode) -> bool {
-        if !self.has_styles() {
-            self.set_styles(ElementStyles::new(ComputedStyle::new_partial(rules)));
-            return true;
-        }
-
-        if self.styles().primary.rules == rules {
-            return false;
-        }
-
-        self.styles_mut().primary.rules = rules;
-        true
-    }
-
     /// Return true if important rules are different.
     /// We use this to make sure the cascade of off-main thread animations is correct.
     /// Note: Ignore custom properties for now because we only support opacity and transform
@@ -604,7 +373,7 @@ impl ElementData {
                                          guards: &StylesheetGuards) -> bool {
         debug_assert!(self.has_styles());
         let (important_rules, _custom) =
-            self.styles().primary.rules.get_properties_overriding_animations(&guards);
+            self.styles.primary().rules().get_properties_overriding_animations(&guards);
         let (other_important_rules, _custom) = rules.get_properties_overriding_animations(&guards);
         important_rules != other_important_rules
     }
@@ -621,8 +390,8 @@ impl ElementData {
             return None;
         }
 
-        match self.get_styles() {
-            Some(s) => s.primary.rules.get_smil_animation_rule(),
+        match self.styles.get_primary() {
+            Some(v) => v.rules().get_smil_animation_rule(),
             None => None,
         }
     }
@@ -633,8 +402,8 @@ impl ElementData {
             return AnimationRules(None, None)
         }
 
-        match self.get_styles() {
-            Some(s) => s.primary.rules.get_animation_rules(),
+        match self.styles.get_primary() {
+            Some(v) => v.rules().get_animation_rules(),
             None => AnimationRules(None, None),
         }
     }
diff --git a/components/style/dom.rs b/components/style/dom.rs
index 98ea2153f35..de736e291c6 100644
--- a/components/style/dom.rs
+++ b/components/style/dom.rs
@@ -218,8 +218,7 @@ fn fmt_with_data_and_primary_values<N: TNode>(f: &mut fmt::Formatter, n: N) -> f
     if let Some(el) = n.as_element() {
         let dd = el.has_dirty_descendants();
         let data = el.borrow_data();
-        let styles = data.as_ref().and_then(|d| d.get_styles());
-        let values = styles.map(|s| s.primary.values());
+        let values = data.as_ref().and_then(|d| d.styles.get_primary());
         write!(f, "{:?} dd={} data={:?} values={:?}", el, dd, &data, values)
     } else {
         write!(f, "{:?}", n)
@@ -603,6 +602,21 @@ pub trait TElement : Eq + PartialEq + Debug + Hash + Sized + Copy + Clone +
         None
     }
 
+    /// Returns the rule hash target given an element.
+    fn rule_hash_target(&self) -> Self {
+        let is_implemented_pseudo =
+            self.implemented_pseudo_element().is_some();
+
+        // NB: This causes use to rule has pseudo selectors based on the
+        // properties of the originating element (which is fine, given the
+        // find_first_from_right usage).
+        if is_implemented_pseudo {
+            self.closest_non_native_anonymous_ancestor().unwrap()
+        } else {
+            *self
+        }
+    }
+
     /// Gets declarations from XBL bindings from the element. Only gecko element could have this.
     fn get_declarations_from_xbl_bindings<V>(&self,
                                              _pseudo_element: Option<&PseudoElement>,
diff --git a/components/style/gecko/wrapper.rs b/components/style/gecko/wrapper.rs
index 203c2fbacdd..9f2169028ca 100644
--- a/components/style/gecko/wrapper.rs
+++ b/components/style/gecko/wrapper.rs
@@ -515,7 +515,7 @@ impl<'le> GeckoElement<'le> {
             Some(x) => x,
             None => {
                 debug!("Creating ElementData for {:?}", self);
-                let ptr = Box::into_raw(Box::new(AtomicRefCell::new(ElementData::new(None))));
+                let ptr = Box::into_raw(Box::new(AtomicRefCell::new(ElementData::default())));
                 self.0.mServoData.set(ptr);
                 unsafe { &* ptr }
             },
@@ -532,7 +532,7 @@ impl<'le> GeckoElement<'le> {
                 Some(mem::replace(old.borrow_mut().deref_mut(), replace_data))
             }
             (Some(old), None) => {
-                let old_data = mem::replace(old.borrow_mut().deref_mut(), ElementData::new(None));
+                let old_data = mem::replace(old.borrow_mut().deref_mut(), ElementData::default());
                 self.0.mServoData.set(ptr::null_mut());
                 Some(old_data)
             }
@@ -985,7 +985,7 @@ impl<'le> TElement for GeckoElement<'le> {
         // should destroy all CSS animations in display:none subtree.
         let computed_data = self.borrow_data();
         let computed_values =
-            computed_data.as_ref().map(|d| d.styles().primary.values());
+            computed_data.as_ref().map(|d| d.styles.primary());
         let computed_values_opt =
             computed_values.map(|v| *HasArcFFI::arc_as_borrowed(v));
         let before_change_values =
@@ -1019,7 +1019,9 @@ impl<'le> TElement for GeckoElement<'le> {
         where V: Push<ApplicableDeclarationBlock> + VecLike<ApplicableDeclarationBlock> {
         // Walk the binding scope chain, starting with the binding attached to our content, up
         // till we run out of scopes or we get cut off.
-        let mut current = Some(*self);
+
+        // If we are NAC, we want to get rules from our rule_hash_target.
+        let mut current = Some(self.rule_hash_target());
 
         while let Some(element) = current {
             if let Some(binding) = element.get_xbl_binding() {
diff --git a/components/style/matching.rs b/components/style/matching.rs
index 6640e5e33de..ab51de215c4 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -9,8 +9,8 @@
 
 use applicable_declarations::ApplicableDeclarationList;
 use cascade_info::CascadeInfo;
-use context::{SelectorFlagsMap, SharedStyleContext, StyleContext};
-use data::{ComputedStyle, ElementData, RestyleData};
+use context::{CascadeInputs, SelectorFlagsMap, SharedStyleContext, StyleContext};
+use data::{ElementData, ElementStyles, RestyleData};
 use dom::{TElement, TNode};
 use font_metrics::FontMetricsProvider;
 use invalidation::element::restyle_hints::{RESTYLE_CSS_ANIMATIONS, RESTYLE_CSS_TRANSITIONS};
@@ -146,55 +146,98 @@ pub enum CascadeVisitedMode {
 /// depending on the current cascade mode.
 impl CascadeVisitedMode {
     /// Returns whether there is a rule node based on the cascade mode.
-    fn has_rules(&self, style: &ComputedStyle) -> bool {
+    /// Rules will be present after matching or pulled from a previous cascade
+    /// if no matching is expected.  For visited, this means rules exist only
+    /// if a revelant link existed when matching was last done.
+    fn has_rules(&self, inputs: &CascadeInputs) -> bool {
         match *self {
-            CascadeVisitedMode::Unvisited => true,
-            CascadeVisitedMode::Visited => style.has_visited_rules(),
+            CascadeVisitedMode::Unvisited => inputs.has_rules(),
+            CascadeVisitedMode::Visited => inputs.has_visited_rules(),
         }
     }
 
     /// Returns the rule node based on the cascade mode.
-    fn rules<'a>(&self, style: &'a ComputedStyle) -> &'a StrongRuleNode {
+    fn rules<'a>(&self, inputs: &'a CascadeInputs) -> &'a StrongRuleNode {
         match *self {
-            CascadeVisitedMode::Unvisited => &style.rules,
-            CascadeVisitedMode::Visited => style.visited_rules(),
+            CascadeVisitedMode::Unvisited => inputs.rules(),
+            CascadeVisitedMode::Visited => inputs.visited_rules(),
         }
     }
 
     /// Returns a mutable rules node based on the cascade mode, if any.
-    fn get_rules_mut<'a>(&self, style: &'a mut ComputedStyle) -> Option<&'a mut StrongRuleNode> {
+    fn get_rules_mut<'a>(&self, inputs: &'a mut CascadeInputs) -> Option<&'a mut StrongRuleNode> {
         match *self {
-            CascadeVisitedMode::Unvisited => Some(&mut style.rules),
-            CascadeVisitedMode::Visited => style.get_visited_rules_mut(),
+            CascadeVisitedMode::Unvisited => inputs.get_rules_mut(),
+            CascadeVisitedMode::Visited => inputs.get_visited_rules_mut(),
         }
     }
 
     /// Returns the computed values based on the cascade mode.  In visited mode,
     /// visited values are only returned if they already exist.  If they don't,
     /// we fallback to the regular, unvisited styles.
-    fn values<'a>(&self, style: &'a ComputedStyle) -> &'a Arc<ComputedValues> {
-        let mut values = style.values();
-
+    fn values<'a>(&self, values: &'a Arc<ComputedValues>) -> &'a Arc<ComputedValues> {
         if *self == CascadeVisitedMode::Visited && values.get_visited_style().is_some() {
-            values = values.visited_style();
+            return values.visited_style();
         }
 
         values
     }
 
-    /// Set the computed values based on the cascade mode.
-    fn set_values(&self, style: &mut ComputedStyle, values: Arc<ComputedValues>) {
+    /// Set the primary computed values based on the cascade mode.
+    fn set_primary_values(&self,
+                          styles: &mut ElementStyles,
+                          inputs: &mut CascadeInputs,
+                          values: Arc<ComputedValues>) {
+        // Unvisited values are stored in permanent storage on `ElementData`.
+        // Visited values are stored temporarily in `CascadeInputs` and then
+        // folded into the unvisited values when they cascade.
+        match *self {
+            CascadeVisitedMode::Unvisited => styles.primary = Some(values),
+            CascadeVisitedMode::Visited => inputs.set_visited_values(values),
+        }
+    }
+
+    /// Set the primary computed values based on the cascade mode.
+    fn set_pseudo_values(&self,
+                         styles: &mut ElementStyles,
+                         inputs: &mut CascadeInputs,
+                         pseudo: &PseudoElement,
+                         values: Arc<ComputedValues>) {
+        // Unvisited values are stored in permanent storage on `ElementData`.
+        // Visited values are stored temporarily in `CascadeInputs` and then
+        // folded into the unvisited values when they cascade.
         match *self {
-            CascadeVisitedMode::Unvisited => style.values = Some(values),
-            CascadeVisitedMode::Visited => style.set_visited_values(values),
+            CascadeVisitedMode::Unvisited => styles.pseudos.set(pseudo, values),
+            CascadeVisitedMode::Visited => inputs.set_visited_values(values),
         }
     }
 
-    /// Take the computed values based on the cascade mode.
-    fn take_values(&self, style: &mut ComputedStyle) -> Option<Arc<ComputedValues>> {
+    /// Take the primary computed values based on the cascade mode.
+    fn take_primary_values(&self,
+                           styles: &mut ElementStyles,
+                           inputs: &mut CascadeInputs)
+                           -> Option<Arc<ComputedValues>> {
+        // Unvisited values are stored in permanent storage on `ElementData`.
+        // Visited values are stored temporarily in `CascadeInputs` and then
+        // folded into the unvisited values when they cascade.
         match *self {
-            CascadeVisitedMode::Unvisited => style.values.take(),
-            CascadeVisitedMode::Visited => style.take_visited_values(),
+            CascadeVisitedMode::Unvisited => styles.primary.take(),
+            CascadeVisitedMode::Visited => inputs.take_visited_values(),
+        }
+    }
+
+    /// Take the pseudo computed values based on the cascade mode.
+    fn take_pseudo_values(&self,
+                          styles: &mut ElementStyles,
+                          inputs: &mut CascadeInputs,
+                          pseudo: &PseudoElement)
+                          -> Option<Arc<ComputedValues>> {
+        // Unvisited values are stored in permanent storage on `ElementData`.
+        // Visited values are stored temporarily in `CascadeInputs` and then
+        // folded into the unvisited values when they cascade.
+        match *self {
+            CascadeVisitedMode::Unvisited => styles.pseudos.take(pseudo),
+            CascadeVisitedMode::Visited => inputs.take_visited_values(),
         }
     }
 
@@ -246,7 +289,7 @@ trait PrivateMatchMethods: TElement {
             };
 
             let is_display_contents =
-                current.borrow_data().unwrap().styles().primary.values().is_display_contents();
+                current.borrow_data().unwrap().styles.primary().is_display_contents();
 
             if !is_display_contents {
                 return current;
@@ -254,11 +297,15 @@ trait PrivateMatchMethods: TElement {
         }
     }
 
+    /// A common path for the cascade used by both primary elements and eager
+    /// pseudo-elements after collecting the appropriate rules to use.
+    ///
+    /// `primary_style` is expected to be Some for eager pseudo-elements.
     fn cascade_with_rules(&self,
                           shared_context: &SharedStyleContext,
                           font_metrics_provider: &FontMetricsProvider,
                           rule_node: &StrongRuleNode,
-                          primary_style: &ComputedStyle,
+                          primary_style: Option<&Arc<ComputedValues>>,
                           cascade_target: CascadeTarget,
                           cascade_visited: CascadeVisitedMode,
                           visited_values_to_insert: Option<Arc<ComputedValues>>)
@@ -294,13 +341,13 @@ trait PrivateMatchMethods: TElement {
                     // but not wanting to flush all of layout).
                     debug_assert!(cfg!(feature = "gecko") ||
                                   parent_el.unwrap().has_current_styles(d));
-                    &d.styles().primary
+                    d.styles.primary()
                 });
                 parent_style.map(|s| cascade_visited.values(s))
             }
             CascadeTarget::EagerPseudo => {
                 parent_el = Some(self.clone());
-                Some(cascade_visited.values(primary_style))
+                Some(cascade_visited.values(primary_style.unwrap()))
             }
         };
 
@@ -310,7 +357,7 @@ trait PrivateMatchMethods: TElement {
         if style_to_inherit_from.map_or(false, |s| s.is_display_contents()) {
             layout_parent_el = Some(layout_parent_el.unwrap().layout_parent());
             layout_parent_data = layout_parent_el.as_ref().unwrap().borrow_data().unwrap();
-            layout_parent_style = Some(cascade_visited.values(&layout_parent_data.styles().primary));
+            layout_parent_style = Some(cascade_visited.values(layout_parent_data.styles.primary()));
         }
 
         let style_to_inherit_from = style_to_inherit_from.map(|x| &**x);
@@ -349,14 +396,19 @@ trait PrivateMatchMethods: TElement {
         values
     }
 
+    /// A common path for the cascade used by both primary elements and eager
+    /// pseudo-elements.
+    ///
+    /// `primary_style` is expected to be Some for eager pseudo-elements.
     fn cascade_internal(&self,
                         context: &StyleContext<Self>,
-                        primary_style: &ComputedStyle,
-                        eager_pseudo_style: Option<&ComputedStyle>,
+                        primary_style: Option<&Arc<ComputedValues>>,
+                        primary_inputs: &CascadeInputs,
+                        eager_pseudo_inputs: Option<&CascadeInputs>,
                         cascade_visited: CascadeVisitedMode)
                         -> Arc<ComputedValues> {
         if let Some(pseudo) = self.implemented_pseudo_element() {
-            debug_assert!(eager_pseudo_style.is_none());
+            debug_assert!(eager_pseudo_inputs.is_none());
 
             // This is an element-backed pseudo, just grab the styles from the
             // parent if it's eager, and recascade otherwise.
@@ -377,10 +429,10 @@ trait PrivateMatchMethods: TElement {
                 debug_assert!(pseudo.is_before_or_after());
                 let parent = self.parent_element().unwrap();
                 if !parent.may_have_animations() ||
-                   primary_style.rules.get_animation_rules().is_empty() {
+                   primary_inputs.rules().get_animation_rules().is_empty() {
                     let parent_data = parent.borrow_data().unwrap();
                     let pseudo_style =
-                        parent_data.styles().pseudos.get(&pseudo).unwrap();
+                        parent_data.styles.pseudos.get(&pseudo).unwrap();
                     let values = cascade_visited.values(pseudo_style);
                     return values.clone()
                 }
@@ -390,18 +442,21 @@ trait PrivateMatchMethods: TElement {
         // Find possible visited computed styles to insert within the regular
         // computed values we are about to create.
         let visited_values_to_insert = if cascade_visited.visited_values_for_insertion() {
-            match eager_pseudo_style {
+            match eager_pseudo_inputs {
                 Some(ref s) => s.clone_visited_values(),
-                None => primary_style.clone_visited_values(),
+                None => primary_inputs.clone_visited_values(),
             }
         } else {
             None
         };
 
         // Grab the rule node.
-        let style = eager_pseudo_style.unwrap_or(primary_style);
-        let rule_node = cascade_visited.rules(style);
-        let cascade_target = if eager_pseudo_style.is_some() {
+        let inputs = eager_pseudo_inputs.unwrap_or(primary_inputs);
+        // We'd really like to take the rules here to avoid refcount traffic,
+        // but animation's usage of `apply_declarations` make this tricky.
+        // See bug 1375525.
+        let rule_node = cascade_visited.rules(inputs);
+        let cascade_target = if eager_pseudo_inputs.is_some() {
             CascadeTarget::EagerPseudo
         } else {
             CascadeTarget::Normal
@@ -426,23 +481,30 @@ trait PrivateMatchMethods: TElement {
                        -> ChildCascadeRequirement {
         debug!("Cascade primary for {:?}, visited: {:?}", self, cascade_visited);
 
-        // Collect some values.
-        let (mut styles, restyle) = data.styles_and_restyle_mut();
-        let mut primary_style = &mut styles.primary;
-        // If there was no relevant link, we won't have any visited rules, so
-        // there may not be anything do for the visited case.  This early return
-        // is especially important for the `cascade_primary_and_pseudos` path
-        // since we rely on the state of some previous matching run.
-        if !cascade_visited.has_rules(primary_style) {
-            return ChildCascadeRequirement::CanSkipCascade
-        }
-        let mut old_values = cascade_visited.take_values(primary_style);
+        let mut old_values = cascade_visited.take_primary_values(
+            &mut data.styles,
+            context.cascade_inputs_mut().primary_mut()
+        );
+
+        let mut new_values = {
+            let primary_inputs = context.cascade_inputs().primary();
 
-        // Compute the new values.
-        let mut new_values = self.cascade_internal(context,
-                                                   primary_style,
-                                                   None,
-                                                   cascade_visited);
+            // If there was no relevant link at the time of matching, we won't
+            // have any visited rules, so there may not be anything do for the
+            // visited case. This early return is especially important for the
+            // `cascade_primary_and_pseudos` path since we rely on the state of
+            // some previous matching run.
+            if !cascade_visited.has_rules(primary_inputs) {
+                return ChildCascadeRequirement::CanSkipCascade
+            }
+
+            // Compute the new values.
+            self.cascade_internal(context,
+                                  None,
+                                  primary_inputs,
+                                  None,
+                                  cascade_visited)
+        };
 
         // NB: Animations for pseudo-elements in Gecko are handled while
         // traversing the pseudo-elements themselves.
@@ -451,7 +513,6 @@ trait PrivateMatchMethods: TElement {
             self.process_animations(context,
                                     &mut old_values,
                                     &mut new_values,
-                                    primary_style,
                                     important_rules_changed);
         }
 
@@ -460,7 +521,7 @@ trait PrivateMatchMethods: TElement {
         if cascade_visited.should_accumulate_damage() {
             child_cascade_requirement =
                 self.accumulate_damage(&context.shared,
-                                       restyle,
+                                       &mut data.restyle,
                                        old_values.as_ref().map(|v| v.as_ref()),
                                        &new_values,
                                        None);
@@ -483,7 +544,10 @@ trait PrivateMatchMethods: TElement {
         }
 
         // Set the new computed values.
-        cascade_visited.set_values(primary_style, new_values);
+        let primary_inputs = context.cascade_inputs_mut().primary_mut();
+        cascade_visited.set_primary_values(&mut data.styles,
+                                           primary_inputs,
+                                           new_values);
 
         // Return whether the damage indicates we must cascade new inherited
         // values into children.
@@ -498,31 +562,52 @@ trait PrivateMatchMethods: TElement {
                             pseudo: &PseudoElement,
                             cascade_visited: CascadeVisitedMode) {
         debug_assert!(pseudo.is_eager());
-        let (mut styles, restyle) = data.styles_and_restyle_mut();
-        let mut pseudo_style = styles.pseudos.get_mut(pseudo).unwrap();
-        // If there was no relevant link, we won't have any visited rules, so
-        // there may not be anything do for the visited case.  This early return
-        // is especially important for the `cascade_primary_and_pseudos` path
-        // since we rely on the state of some previous matching run.
-        if !cascade_visited.has_rules(pseudo_style) {
-            return
-        }
-        let old_values = cascade_visited.take_values(pseudo_style);
 
-        let new_values = self.cascade_internal(context,
-                                               &styles.primary,
-                                               Some(pseudo_style),
-                                               cascade_visited);
+        let old_values = cascade_visited.take_pseudo_values(
+            &mut data.styles,
+            context.cascade_inputs_mut().pseudos.get_mut(pseudo).unwrap(),
+            pseudo
+        );
+
+        let new_values = {
+            let pseudo_inputs = context.cascade_inputs().pseudos
+                                       .get(pseudo).unwrap();
+
+            // If there was no relevant link at the time of matching, we won't
+            // have any visited rules, so there may not be anything do for the
+            // visited case. This early return is especially important for the
+            // `cascade_primary_and_pseudos` path since we rely on the state of
+            // some previous matching run.
+            if !cascade_visited.has_rules(pseudo_inputs) {
+                return
+            }
+
+            // Primary inputs should already have rules populated since it's
+            // always processed before eager pseudos.
+            let primary_inputs = context.cascade_inputs().primary();
+            debug_assert!(cascade_visited.has_rules(primary_inputs));
+
+            self.cascade_internal(context,
+                                  data.styles.get_primary(),
+                                  primary_inputs,
+                                  Some(pseudo_inputs),
+                                  cascade_visited)
+        };
 
         if cascade_visited.should_accumulate_damage() {
             self.accumulate_damage(&context.shared,
-                                   restyle,
-                                   old_values.as_ref().map(|v| &**v),
+                                   &mut data.restyle,
+                                   old_values.as_ref().map(|v| v.as_ref()),
                                    &new_values,
                                    Some(pseudo));
         }
 
-        cascade_visited.set_values(pseudo_style, new_values);
+        let pseudo_inputs = context.cascade_inputs_mut().pseudos
+                                   .get_mut(pseudo).unwrap();
+        cascade_visited.set_pseudo_values(&mut data.styles,
+                                          pseudo_inputs,
+                                          pseudo,
+                                          new_values);
     }
 
     /// get_after_change_style removes the transition rules from the ComputedValues.
@@ -530,9 +615,9 @@ trait PrivateMatchMethods: TElement {
     #[cfg(feature = "gecko")]
     fn get_after_change_style(&self,
                               context: &mut StyleContext<Self>,
-                              primary_style: &ComputedStyle)
+                              primary_style: &Arc<ComputedValues>)
                               -> Option<Arc<ComputedValues>> {
-        let rule_node = &primary_style.rules;
+        let rule_node = primary_style.rules();
         let without_transition_rules =
             context.shared.stylist.rule_tree().remove_transition_rule_if_applicable(rule_node);
         if without_transition_rules == *rule_node {
@@ -546,7 +631,7 @@ trait PrivateMatchMethods: TElement {
         Some(self.cascade_with_rules(context.shared,
                                      &context.thread_local.font_metrics_provider,
                                      &without_transition_rules,
-                                     primary_style,
+                                     Some(primary_style),
                                      CascadeTarget::Normal,
                                      CascadeVisitedMode::Unvisited,
                                      None))
@@ -586,7 +671,6 @@ trait PrivateMatchMethods: TElement {
                           context: &mut StyleContext<Self>,
                           old_values: &mut Option<Arc<ComputedValues>>,
                           new_values: &mut Arc<ComputedValues>,
-                          primary_style: &ComputedStyle,
                           important_rules_changed: bool) {
         use context::{CASCADE_RESULTS, CSS_ANIMATIONS, CSS_TRANSITIONS, EFFECT_PROPERTIES};
         use context::UpdateAnimationsTasks;
@@ -599,7 +683,7 @@ trait PrivateMatchMethods: TElement {
         let before_change_style = if self.might_need_transitions_update(old_values.as_ref().map(|s| &**s),
                                                                         new_values) {
             let after_change_style = if self.has_css_transitions() {
-                self.get_after_change_style(context, primary_style)
+                self.get_after_change_style(context, new_values)
             } else {
                 None
             };
@@ -652,7 +736,6 @@ trait PrivateMatchMethods: TElement {
                           context: &mut StyleContext<Self>,
                           old_values: &mut Option<Arc<ComputedValues>>,
                           new_values: &mut Arc<ComputedValues>,
-                          _primary_style: &ComputedStyle,
                           _important_rules_changed: bool) {
         use animation;
 
@@ -857,7 +940,7 @@ pub trait MatchMethods : TElement {
                                  CascadeVisitedMode::Unvisited);
 
         // Match and cascade eager pseudo-elements.
-        if !data.styles().is_display_none() {
+        if !data.styles.is_display_none() {
             self.match_pseudos(context, data, VisitedHandlingMode::AllLinksUnvisited);
 
             // If there's a relevant link involved, match and cascade eager
@@ -876,7 +959,7 @@ pub trait MatchMethods : TElement {
         }
 
         // If we have any pseudo elements, indicate so in the primary StyleRelations.
-        if !data.styles().pseudos.is_empty() {
+        if !data.styles.pseudos.is_empty() {
             primary_results.relations |= AFFECTED_BY_PSEUDO_ELEMENTS;
         }
 
@@ -899,7 +982,7 @@ pub trait MatchMethods : TElement {
             context.thread_local
                    .style_sharing_candidate_cache
                    .insert_if_possible(self,
-                                       data.styles().primary.values(),
+                                       data.styles.primary(),
                                        primary_results.relations,
                                        validation_data,
                                        dom_depth);
@@ -943,6 +1026,10 @@ pub trait MatchMethods : TElement {
     {
         debug!("Match primary for {:?}, visited: {:?}", self, visited_handling);
 
+        let mut primary_inputs = context.thread_local.current_element_info
+                                        .as_mut().unwrap()
+                                        .cascade_inputs.ensure_primary();
+
         let only_default_rules = context.shared.traversal_flags.for_default_styles();
         let implemented_pseudo = self.implemented_pseudo_element();
         if let Some(ref pseudo) = implemented_pseudo {
@@ -964,8 +1051,8 @@ pub trait MatchMethods : TElement {
                 let parent = self.parent_element().unwrap();
                 let parent_data = parent.borrow_data().unwrap();
                 let pseudo_style =
-                    parent_data.styles().pseudos.get(&pseudo).unwrap();
-                let mut rules = pseudo_style.rules.clone();
+                    parent_data.styles.pseudos.get(&pseudo).unwrap();
+                let mut rules = pseudo_style.rules().clone();
                 if parent.may_have_animations() {
                     let animation_rules = data.get_animation_rules();
 
@@ -998,20 +1085,9 @@ pub trait MatchMethods : TElement {
                     self.has_animations() &&
                     data.has_styles() &&
                     data.important_rules_are_different(&rules,
-                                                   &context.shared.guards);
-
-                let rules_changed = match visited_handling {
-                    VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
-                        unreachable!("We should never try to selector match with \
-                                     AllLinksVisitedAndUnvisited");
-                    },
-                    VisitedHandlingMode::AllLinksUnvisited => {
-                        data.set_primary_rules(rules)
-                    },
-                    VisitedHandlingMode::RelevantLinkVisited => {
-                        data.styles_mut().primary.set_visited_rules(rules)
-                    },
-                };
+                                                       &context.shared.guards);
+
+                let rules_changed = primary_inputs.set_rules(visited_handling, rules);
 
                 return MatchingResults::new(rules_changed, important_rules_changed)
             }
@@ -1084,18 +1160,7 @@ pub trait MatchMethods : TElement {
                 &context.shared.guards
             );
 
-        let rules_changed = match visited_handling {
-            VisitedHandlingMode::AllLinksVisitedAndUnvisited => {
-                unreachable!("We should never try to selector match with \
-                             AllLinksVisitedAndUnvisited");
-            },
-            VisitedHandlingMode::AllLinksUnvisited => {
-                data.set_primary_rules(primary_rule_node)
-            },
-            VisitedHandlingMode::RelevantLinkVisited => {
-                data.styles_mut().primary.set_visited_rules(primary_rule_node)
-            },
-        };
+        let rules_changed = primary_inputs.set_rules(visited_handling, primary_rule_node);
 
         MatchingResults::new_from_context(rules_changed,
                                           important_rules_changed,
@@ -1118,11 +1183,6 @@ pub trait MatchMethods : TElement {
 
         let mut applicable_declarations = ApplicableDeclarationList::new();
 
-        let map = &mut context.thread_local.selector_flags;
-        let mut set_selector_flags = |element: &Self, flags: ElementSelectorFlags| {
-            self.apply_selector_flags(map, element, flags);
-        };
-
         // Borrow the stuff we need here so the borrow checker doesn't get mad
         // at us later in the closure.
         let stylist = &context.shared.stylist;
@@ -1134,57 +1194,69 @@ pub trait MatchMethods : TElement {
             RuleInclusion::All
         };
 
-        let bloom_filter = context.thread_local.bloom_filter.filter();
-
-        let mut matching_context =
-            MatchingContext::new_for_visited(MatchingMode::ForStatelessPseudoElement,
-                                             Some(bloom_filter),
-                                             visited_handling,
-                                             context.shared.quirks_mode);
-
         // Compute rule nodes for eagerly-cascaded pseudo-elements.
         let mut matches_different_pseudos = false;
         SelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
+            let bloom_filter = context.thread_local.bloom_filter.filter();
+
+            let mut matching_context =
+                MatchingContext::new_for_visited(MatchingMode::ForStatelessPseudoElement,
+                                                 Some(bloom_filter),
+                                                 visited_handling,
+                                                 context.shared.quirks_mode);
+
             // For pseudo-elements, we only try to match visited rules if there
             // are also unvisited rules.  (This matches Gecko's behavior.)
             if visited_handling == VisitedHandlingMode::RelevantLinkVisited &&
-               !data.styles().pseudos.has(&pseudo) {
+               !context.cascade_inputs().pseudos.has(&pseudo) {
                 return
             }
 
-            if !self.may_generate_pseudo(&pseudo, data.styles().primary.values()) {
+            if !self.may_generate_pseudo(&pseudo, data.styles.primary()) {
                 return;
             }
 
-            debug_assert!(applicable_declarations.is_empty());
-            // NB: We handle animation rules for ::before and ::after when
-            // traversing them.
-            stylist.push_applicable_declarations(self,
-                                                 Some(&pseudo),
-                                                 None,
-                                                 None,
-                                                 AnimationRules(None, None),
-                                                 rule_inclusion,
-                                                 &mut applicable_declarations,
-                                                 &mut matching_context,
-                                                 &mut set_selector_flags);
+            {
+                let map = &mut context.thread_local.selector_flags;
+                let mut set_selector_flags = |element: &Self, flags: ElementSelectorFlags| {
+                    self.apply_selector_flags(map, element, flags);
+                };
+
+                debug_assert!(applicable_declarations.is_empty());
+                // NB: We handle animation rules for ::before and ::after when
+                // traversing them.
+                stylist.push_applicable_declarations(self,
+                                                     Some(&pseudo),
+                                                     None,
+                                                     None,
+                                                     AnimationRules(None, None),
+                                                     rule_inclusion,
+                                                     &mut applicable_declarations,
+                                                     &mut matching_context,
+                                                     &mut set_selector_flags);
+            }
 
-            let pseudos = &mut data.styles_mut().pseudos;
+            let pseudos = &mut context.thread_local.current_element_info
+                                      .as_mut().unwrap()
+                                      .cascade_inputs.pseudos;
             if !applicable_declarations.is_empty() {
                 let rules = stylist.rule_tree().compute_rule_node(
                     &mut applicable_declarations,
                     &guards
                 );
-                matches_different_pseudos |= pseudos.add_rules(
+                matches_different_pseudos |= !data.styles.pseudos.has(&pseudo);
+                pseudos.add_rules(
                     &pseudo,
                     visited_handling,
                     rules
                 );
             } else {
-                matches_different_pseudos |= pseudos.remove_rules(
+                matches_different_pseudos |= data.styles.pseudos.has(&pseudo);
+                pseudos.remove_rules(
                     &pseudo,
                     visited_handling
                 );
+                data.styles.pseudos.take(&pseudo);
             }
         });
 
@@ -1292,14 +1364,13 @@ pub trait MatchMethods : TElement {
     fn replace_rules(
         &self,
         replacements: RestyleHint,
-        context: &StyleContext<Self>,
-        data: &mut ElementData
+        context: &mut StyleContext<Self>,
     ) -> bool {
         let mut result = false;
-        result |= self.replace_rules_internal(replacements, context, data,
+        result |= self.replace_rules_internal(replacements, context,
                                               CascadeVisitedMode::Unvisited);
         if !context.shared.traversal_flags.for_animation_only() {
-            result |= self.replace_rules_internal(replacements, context, data,
+            result |= self.replace_rules_internal(replacements, context,
                                                   CascadeVisitedMode::Visited);
         }
         result
@@ -1312,8 +1383,7 @@ pub trait MatchMethods : TElement {
     fn replace_rules_internal(
         &self,
         replacements: RestyleHint,
-        context: &StyleContext<Self>,
-        data: &mut ElementData,
+        context: &mut StyleContext<Self>,
         cascade_visited: CascadeVisitedMode
     ) -> bool {
         use properties::PropertyDeclarationBlock;
@@ -1322,8 +1392,11 @@ pub trait MatchMethods : TElement {
         debug_assert!(replacements.intersects(RestyleHint::replacements()) &&
                       (replacements & !RestyleHint::replacements()).is_empty());
 
-        let element_styles = &mut data.styles_mut();
-        let primary_rules = match cascade_visited.get_rules_mut(&mut element_styles.primary) {
+        let stylist = &context.shared.stylist;
+        let guards = &context.shared.guards;
+
+        let mut primary_inputs = context.cascade_inputs_mut().primary_mut();
+        let primary_rules = match cascade_visited.get_rules_mut(primary_inputs) {
             Some(r) => r,
             None => return false,
         };
@@ -1331,8 +1404,8 @@ pub trait MatchMethods : TElement {
         let replace_rule_node = |level: CascadeLevel,
                                  pdb: Option<&Arc<Locked<PropertyDeclarationBlock>>>,
                                  path: &mut StrongRuleNode| -> bool {
-            let new_node = context.shared.stylist.rule_tree()
-                .update_rule_at_level(level, pdb, path, &context.shared.guards);
+            let new_node = stylist.rule_tree()
+                                  .update_rule_at_level(level, pdb, path, guards);
             match new_node {
                 Some(n) => {
                     *path = n;
@@ -1455,8 +1528,9 @@ pub trait MatchMethods : TElement {
         // which pseudos match), so now we can just iterate what we have. This
         // does mean collecting owned pseudos, so that the borrow checker will
         // let us pass the mutable |data| to the cascade function.
-        let matched_pseudos = data.styles().pseudos.keys();
+        let matched_pseudos = context.cascade_inputs().pseudos.keys();
         for pseudo in matched_pseudos {
+            debug!("Cascade pseudo for {:?} {:?}", self, pseudo);
             self.cascade_eager_pseudo(context, data, &pseudo, cascade_visited);
         }
     }
@@ -1465,17 +1539,17 @@ pub trait MatchMethods : TElement {
     fn get_base_style(&self,
                       shared_context: &SharedStyleContext,
                       font_metrics_provider: &FontMetricsProvider,
-                      primary_style: &ComputedStyle,
-                      pseudo_style: Option<&ComputedStyle>)
+                      primary_style: &Arc<ComputedValues>,
+                      pseudo_style: Option<&Arc<ComputedValues>>)
                       -> Arc<ComputedValues> {
         let relevant_style = pseudo_style.unwrap_or(primary_style);
-        let rule_node = &relevant_style.rules;
+        let rule_node = relevant_style.rules();
         let without_animation_rules =
             shared_context.stylist.rule_tree().remove_animation_rules(rule_node);
         if without_animation_rules == *rule_node {
             // Note that unwrapping here is fine, because the style is
             // only incomplete during the styling process.
-            return relevant_style.values.as_ref().unwrap().clone();
+            return relevant_style.clone();
         }
 
         // This currently ignores visited styles, which seems acceptable,
@@ -1483,7 +1557,7 @@ pub trait MatchMethods : TElement {
         self.cascade_with_rules(shared_context,
                                 font_metrics_provider,
                                 &without_animation_rules,
-                                primary_style,
+                                Some(primary_style),
                                 CascadeTarget::Normal,
                                 CascadeVisitedMode::Unvisited,
                                 None)
diff --git a/components/style/properties/gecko.mako.rs b/components/style/properties/gecko.mako.rs
index c75ba4d3e68..4ff4ca4d06a 100644
--- a/components/style/properties/gecko.mako.rs
+++ b/components/style/properties/gecko.mako.rs
@@ -58,6 +58,7 @@ use properties::longhands;
 use properties:: FontComputationData;
 use properties::{Importance, LonghandId};
 use properties::{PropertyDeclaration, PropertyDeclarationBlock, PropertyDeclarationId};
+use rule_tree::StrongRuleNode;
 use std::fmt::{self, Debug};
 use std::mem::{forget, transmute, zeroed};
 use std::ptr;
@@ -75,7 +76,7 @@ pub mod style_structs {
 }
 
 
-#[derive(Clone, Debug)]
+#[derive(Clone)]
 pub struct ComputedValues {
     % for style_struct in data.style_structs:
     ${style_struct.ident}: Arc<style_structs::${style_struct.name}>,
@@ -85,6 +86,10 @@ pub struct ComputedValues {
     pub writing_mode: WritingMode,
     pub font_computation_data: FontComputationData,
 
+    /// The rule node representing the ordered list of rules matched for this
+    /// node.  Can be None for default values and text nodes.  This is
+    /// essentially an optimization to avoid referencing the root rule node.
+    pub rules: Option<StrongRuleNode>,
     /// The element's computed values if visited, only computed if there's a
     /// relevant link for this element. A element's "relevant link" is the
     /// element being matched if it is a link or the nearest ancestor link.
@@ -95,6 +100,7 @@ impl ComputedValues {
     pub fn new(custom_properties: Option<Arc<ComputedValuesMap>>,
                writing_mode: WritingMode,
                font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
+               rules: Option<StrongRuleNode>,
                visited_style: Option<Arc<ComputedValues>>,
                % for style_struct in data.style_structs:
                ${style_struct.ident}: Arc<style_structs::${style_struct.name}>,
@@ -104,6 +110,7 @@ impl ComputedValues {
             custom_properties: custom_properties,
             writing_mode: writing_mode,
             font_computation_data: FontComputationData::new(font_size_keyword),
+            rules: rules,
             visited_style: visited_style,
             % for style_struct in data.style_structs:
             ${style_struct.ident}: ${style_struct.ident},
@@ -116,6 +123,7 @@ impl ComputedValues {
             custom_properties: None,
             writing_mode: WritingMode::empty(), // FIXME(bz): This seems dubious
             font_computation_data: FontComputationData::default_values(),
+            rules: None,
             visited_style: None,
             % for style_struct in data.style_structs:
                 ${style_struct.ident}: style_structs::${style_struct.name}::default(pres_context),
@@ -123,7 +131,6 @@ impl ComputedValues {
         })
     }
 
-
     #[inline]
     pub fn is_display_contents(&self) -> bool {
         self.get_box().clone_display() == longhands::display::computed_value::T::contents
@@ -156,19 +163,23 @@ impl ComputedValues {
     }
     % endfor
 
-    /// Gets a reference to the visited computed values, if any.
+    /// Gets a reference to the rule node. Panic if no rule node exists.
+    pub fn rules(&self) -> &StrongRuleNode {
+        self.rules.as_ref().unwrap()
+    }
+
+    /// Gets a reference to the visited style, if any.
     pub fn get_visited_style(&self) -> Option<<&Arc<ComputedValues>> {
         self.visited_style.as_ref()
     }
 
-    /// Gets a reference to the visited computed values. Panic if the element
-    /// does not have visited computed values.
+    /// Gets a reference to the visited style. Panic if no visited style exists.
     pub fn visited_style(&self) -> &Arc<ComputedValues> {
         self.get_visited_style().unwrap()
     }
 
-    /// Clone the visited computed values Arc.  Used for inheriting parent styles
-    /// in StyleBuilder::for_inheritance.
+    /// Clone the visited style.  Used for inheriting parent styles in
+    /// StyleBuilder::for_inheritance.
     pub fn clone_visited_style(&self) -> Option<Arc<ComputedValues>> {
         self.visited_style.clone()
     }
diff --git a/components/style/properties/helpers/animated_properties.mako.rs b/components/style/properties/helpers/animated_properties.mako.rs
index a78af95120b..3874f972a25 100644
--- a/components/style/properties/helpers/animated_properties.mako.rs
+++ b/components/style/properties/helpers/animated_properties.mako.rs
@@ -2765,7 +2765,7 @@ impl Animatable for IntermediateRGBA {
 
     #[inline]
     fn get_zero_value(&self) -> Option<Self> {
-        Some(IntermediateRGBA::new(0., 0., 0., 1.))
+        Some(IntermediateRGBA::transparent())
     }
 
     #[inline]
@@ -2982,6 +2982,14 @@ impl Animatable for IntermediateSVGPaint {
         Ok(self.kind.compute_squared_distance(&other.kind)? +
             self.fallback.compute_squared_distance(&other.fallback)?)
     }
+
+    #[inline]
+    fn get_zero_value(&self) -> Option<Self> {
+        Some(IntermediateSVGPaint {
+            kind: option_try!(self.kind.get_zero_value()),
+            fallback: self.fallback.and_then(|v| v.get_zero_value()),
+        })
+    }
 }
 
 impl Animatable for IntermediateSVGPaintKind {
@@ -3012,6 +3020,18 @@ impl Animatable for IntermediateSVGPaintKind {
             _ => Err(())
         }
     }
+
+    #[inline]
+    fn get_zero_value(&self) -> Option<Self> {
+        match self {
+            &SVGPaintKind::Color(ref color) => color.get_zero_value()
+                                                    .map(SVGPaintKind::Color),
+            &SVGPaintKind::None |
+            &SVGPaintKind::ContextFill |
+            &SVGPaintKind::ContextStroke =>  Some(self.clone()),
+            _ => None,
+        }
+    }
 }
 
 #[derive(Copy, Clone, Debug, PartialEq)]
diff --git a/components/style/properties/properties.mako.rs b/components/style/properties/properties.mako.rs
index 03f9802e019..390ad3d3c27 100644
--- a/components/style/properties/properties.mako.rs
+++ b/components/style/properties/properties.mako.rs
@@ -1810,7 +1810,7 @@ pub type ServoComputedValues = ComputedValues;
 ///
 /// When needed, the structs may be copied in order to get mutated.
 #[cfg(feature = "servo")]
-#[cfg_attr(feature = "servo", derive(Clone, Debug))]
+#[cfg_attr(feature = "servo", derive(Clone))]
 pub struct ComputedValues {
     % for style_struct in data.active_style_structs():
         ${style_struct.ident}: Arc<style_structs::${style_struct.name}>,
@@ -1821,6 +1821,10 @@ pub struct ComputedValues {
     /// The keyword behind the current font-size property, if any
     pub font_computation_data: FontComputationData,
 
+    /// The rule node representing the ordered list of rules matched for this
+    /// node.  Can be None for default values and text nodes.  This is
+    /// essentially an optimization to avoid referencing the root rule node.
+    pub rules: Option<StrongRuleNode>,
     /// The element's computed values if visited, only computed if there's a
     /// relevant link for this element. A element's "relevant link" is the
     /// element being matched if it is a link or the nearest ancestor link.
@@ -1833,6 +1837,7 @@ impl ComputedValues {
     pub fn new(custom_properties: Option<Arc<::custom_properties::ComputedValuesMap>>,
                writing_mode: WritingMode,
                font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
+               rules: Option<StrongRuleNode>,
                visited_style: Option<Arc<ComputedValues>>,
             % for style_struct in data.active_style_structs():
                ${style_struct.ident}: Arc<style_structs::${style_struct.name}>,
@@ -1842,6 +1847,7 @@ impl ComputedValues {
             custom_properties: custom_properties,
             writing_mode: writing_mode,
             font_computation_data: FontComputationData::new(font_size_keyword),
+            rules: rules,
             visited_style: visited_style,
         % for style_struct in data.active_style_structs():
             ${style_struct.ident}: ${style_struct.ident},
@@ -1878,19 +1884,23 @@ impl ComputedValues {
         }
     % endfor
 
-    /// Gets a reference to the visited computed values, if any.
+    /// Gets a reference to the rule node. Panic if no rule node exists.
+    pub fn rules(&self) -> &StrongRuleNode {
+        self.rules.as_ref().unwrap()
+    }
+
+    /// Gets a reference to the visited style, if any.
     pub fn get_visited_style(&self) -> Option<<&Arc<ComputedValues>> {
         self.visited_style.as_ref()
     }
 
-    /// Gets a reference to the visited computed values. Panic if the element
-    /// does not have visited computed values.
+    /// Gets a reference to the visited style. Panic if no visited style exists.
     pub fn visited_style(&self) -> &Arc<ComputedValues> {
         self.get_visited_style().unwrap()
     }
 
-    /// Clone the visited computed values Arc.  Used for inheriting parent styles
-    /// in StyleBuilder::for_inheritance.
+    /// Clone the visited style.  Used for inheriting parent styles in
+    /// StyleBuilder::for_inheritance.
     pub fn clone_visited_style(&self) -> Option<Arc<ComputedValues>> {
         self.visited_style.clone()
     }
@@ -2138,6 +2148,14 @@ impl ComputedValues {
     }
 }
 
+// We manually implement Debug for ComputedValues so that we can avoid the
+// verbose stringification of every property and instead focus on a few values.
+impl fmt::Debug for ComputedValues {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "ComputedValues {{ rules: {:?}, .. }}", self.rules)
+    }
+}
+
 /// Return a WritingMode bitflags from the relevant CSS properties.
 pub fn get_writing_mode(inheritedbox_style: &style_structs::InheritedBox) -> WritingMode {
     use logical_geometry;
@@ -2277,6 +2295,9 @@ impl<'a, T: 'a> Deref for StyleStructRef<'a, T> {
 /// actually cloning them, until we either build the style, or mutate the
 /// inherited value.
 pub struct StyleBuilder<'a> {
+    /// The rule node representing the ordered list of rules matched for this
+    /// node.
+    rules: Option<StrongRuleNode>,
     custom_properties: Option<Arc<::custom_properties::ComputedValuesMap>>,
     /// The writing mode flags.
     ///
@@ -2296,6 +2317,7 @@ pub struct StyleBuilder<'a> {
 impl<'a> StyleBuilder<'a> {
     /// Trivially construct a `StyleBuilder`.
     pub fn new(
+        rules: Option<StrongRuleNode>,
         custom_properties: Option<Arc<::custom_properties::ComputedValuesMap>>,
         writing_mode: WritingMode,
         font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
@@ -2305,6 +2327,7 @@ impl<'a> StyleBuilder<'a> {
         % endfor
     ) -> Self {
         StyleBuilder {
+            rules: rules,
             custom_properties: custom_properties,
             writing_mode: writing_mode,
             font_size_keyword: font_size_keyword,
@@ -2324,7 +2347,8 @@ impl<'a> StyleBuilder<'a> {
     /// Inherits style from the parent element, accounting for the default
     /// computed values that need to be provided as well.
     pub fn for_inheritance(parent: &'a ComputedValues, default: &'a ComputedValues) -> Self {
-        Self::new(parent.custom_properties(),
+        Self::new(/* rules = */ None,
+                  parent.custom_properties(),
                   parent.writing_mode,
                   parent.font_computation_data.font_size_keyword,
                   parent.clone_visited_style(),
@@ -2400,6 +2424,7 @@ impl<'a> StyleBuilder<'a> {
         ComputedValues::new(self.custom_properties,
                             self.writing_mode,
                             self.font_size_keyword,
+                            self.rules,
                             self.visited_style,
                             % for style_struct in data.active_style_structs():
                             self.${style_struct.ident}.build(),
@@ -2443,6 +2468,7 @@ mod lazy_static_module {
             custom_properties: None,
             writing_mode: WritingMode::empty(),
             font_computation_data: FontComputationData::default_values(),
+            rules: None,
             visited_style: None,
         };
     }
@@ -2560,6 +2586,7 @@ pub fn cascade(device: &Device,
         })
     };
     apply_declarations(device,
+                       rule_node,
                        iter_declarations,
                        inherited_style,
                        layout_parent_style,
@@ -2575,6 +2602,7 @@ pub fn cascade(device: &Device,
 /// first.
 #[allow(unused_mut)] // conditionally compiled code for "position"
 pub fn apply_declarations<'a, F, I>(device: &Device,
+                                    rules: &StrongRuleNode,
                                     iter_declarations: F,
                                     inherited_style: &ComputedValues,
                                     layout_parent_style: &ComputedValues,
@@ -2604,8 +2632,12 @@ pub fn apply_declarations<'a, F, I>(device: &Device,
         ::custom_properties::finish_cascade(
             custom_properties, &inherited_custom_properties);
 
+    // We'd really like to own the rules here to avoid refcount traffic, but
+    // animation's usage of `apply_declarations` make this tricky. See bug
+    // 1375525.
     let builder = if !flags.contains(INHERIT_ALL) {
-        StyleBuilder::new(custom_properties,
+        StyleBuilder::new(Some(rules.clone()),
+                          custom_properties,
                           WritingMode::empty(),
                           inherited_style.font_computation_data.font_size_keyword,
                           visited_style,
@@ -2618,7 +2650,8 @@ pub fn apply_declarations<'a, F, I>(device: &Device,
                           % endfor
                           )
     } else {
-        StyleBuilder::new(custom_properties,
+        StyleBuilder::new(Some(rules.clone()),
+                          custom_properties,
                           WritingMode::empty(),
                           inherited_style.font_computation_data.font_size_keyword,
                           visited_style,
diff --git a/components/style/rule_tree/mod.rs b/components/style/rule_tree/mod.rs
index 40031e971ed..f4fe5da37be 100644
--- a/components/style/rule_tree/mod.rs
+++ b/components/style/rule_tree/mod.rs
@@ -1169,7 +1169,7 @@ impl StrongRuleNode {
             };
 
             let parent_data = element.mutate_data().unwrap();
-            let parent_rule_node = parent_data.styles().primary.rules.clone();
+            let parent_rule_node = parent_data.styles.primary().rules().clone();
             element_rule_node = Cow::Owned(parent_rule_node);
 
             properties = inherited_properties;
diff --git a/components/style/sharing/checks.rs b/components/style/sharing/checks.rs
index b380ca467f1..17875cb061a 100644
--- a/components/style/sharing/checks.rs
+++ b/components/style/sharing/checks.rs
@@ -28,8 +28,8 @@ pub fn same_computed_values<E>(first: Option<E>, second: Option<E>) -> bool
         _ => return false,
     };
 
-    let eq = Arc::ptr_eq(a.borrow_data().unwrap().styles().primary.values(),
-                         b.borrow_data().unwrap().styles().primary.values());
+    let eq = Arc::ptr_eq(a.borrow_data().unwrap().styles.primary(),
+                         b.borrow_data().unwrap().styles.primary());
     eq
 }
 
diff --git a/components/style/sharing/mod.rs b/components/style/sharing/mod.rs
index a1cedbd4b73..39ddd2faf89 100644
--- a/components/style/sharing/mod.rs
+++ b/components/style/sharing/mod.rs
@@ -362,7 +362,7 @@ impl<E: TElement> StyleSharingTarget<E> {
 
     fn accumulate_damage_when_sharing(&self,
                                       shared_context: &SharedStyleContext,
-                                      shared_style: &ElementStyles,
+                                      shared_styles: &ElementStyles,
                                       data: &mut ElementData) -> ChildCascadeRequirement {
         // Accumulate restyle damage for the case when our sharing
         // target managed to share style.  This can come from several
@@ -379,7 +379,7 @@ impl<E: TElement> StyleSharingTarget<E> {
             // pseudos being restyled.
             let (styles, mut restyle_data) = data.styles_and_restyle_mut();
             let old_pseudos = &styles.pseudos;
-            let new_pseudos = &shared_style.pseudos;
+            let new_pseudos = &shared_styles.pseudos;
 
             if !old_pseudos.has_same_pseudos_as(new_pseudos) {
                 restyle_data.damage |= RestyleDamage::reconstruct();
@@ -389,9 +389,9 @@ impl<E: TElement> StyleSharingTarget<E> {
                 // here....
                 for pseudo in old_pseudos.keys() {
                     let old_values =
-                        old_pseudos.get(&pseudo).unwrap().values.as_ref().map(|v| &**v);
+                        old_pseudos.get(&pseudo).map(|v| &**v);
                     let new_values =
-                        new_pseudos.get(&pseudo).unwrap().values();
+                        new_pseudos.get(&pseudo).unwrap();
                     self.element.accumulate_damage(
                         &shared_context,
                         restyle_data,
@@ -403,14 +403,12 @@ impl<E: TElement> StyleSharingTarget<E> {
             }
         }
 
-        let old_values =
-            data.get_styles_mut().and_then(|s| s.primary.values.take());
-
+        let old_values = data.styles.primary.take();
         self.element.accumulate_damage(
             &shared_context,
             &mut data.restyle,
             old_values.as_ref().map(|v| &**v),
-            shared_style.primary.values(),
+            shared_styles.primary(),
             None
         )
     }
@@ -595,13 +593,13 @@ impl<E: TElement> StyleSharingCandidateCache<E> {
                 );
 
             match sharing_result {
-                Ok(shared_style) => {
+                Ok(shared_styles) => {
                     // Yay, cache hit. Share the style.
                     let child_cascade_requirement =
                         target.accumulate_damage_when_sharing(shared_context,
-                                                              &shared_style,
+                                                              &shared_styles,
                                                               data);
-                    data.set_styles(shared_style);
+                    data.styles = shared_styles;
 
                     return StyleSharingResult::StyleWasShared(i, child_cascade_requirement)
                 }
@@ -708,6 +706,6 @@ impl<E: TElement> StyleSharingCandidateCache<E> {
 
         debug!("Sharing style between {:?} and {:?}",
                target.element, candidate.element);
-        Ok(data.styles().clone())
+        Ok(data.styles.clone())
     }
 }
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index 5a849a0ab7f..2825e6c1088 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -8,7 +8,6 @@ use {Atom, LocalName, Namespace};
 use applicable_declarations::{ApplicableDeclarationBlock, ApplicableDeclarationList};
 use bit_vec::BitVec;
 use context::QuirksMode;
-use data::ComputedStyle;
 use dom::TElement;
 use element_state::ElementState;
 use error_reporting::create_error_reporter;
@@ -588,7 +587,7 @@ impl Stylist {
                                          parent: Option<&Arc<ComputedValues>>,
                                          cascade_flags: CascadeFlags,
                                          font_metrics: &FontMetricsProvider)
-                                         -> ComputedStyle {
+                                         -> Arc<ComputedValues> {
         debug_assert!(pseudo.is_precomputed());
 
         let rule_node = match self.precomputed_pseudo_element_decls.get(pseudo) {
@@ -628,7 +627,7 @@ impl Stylist {
                                 font_metrics,
                                 cascade_flags,
                                 self.quirks_mode);
-        ComputedStyle::new(rule_node, Arc::new(computed))
+        Arc::new(computed)
     }
 
     /// Returns the style for an anonymous box of the given type.
@@ -666,7 +665,6 @@ impl Stylist {
         }
         self.precomputed_values_for_pseudo(guards, &pseudo, Some(parent_style), cascade_flags,
                                            &ServoMetricsProvider)
-            .values.unwrap()
     }
 
     /// Computes a pseudo-element style lazily during layout.
@@ -683,7 +681,7 @@ impl Stylist {
                                                   rule_inclusion: RuleInclusion,
                                                   parent_style: &ComputedValues,
                                                   font_metrics: &FontMetricsProvider)
-                                                  -> Option<ComputedStyle>
+                                                  -> Option<Arc<ComputedValues>>
         where E: TElement,
     {
         let rule_node =
@@ -710,7 +708,7 @@ impl Stylist {
                                 CascadeFlags::empty(),
                                 self.quirks_mode);
 
-        Some(ComputedStyle::new(rule_node, Arc::new(computed)))
+        Some(Arc::new(computed))
     }
 
     /// Computes the rule node for a lazily-cascaded pseudo-element.
@@ -959,22 +957,6 @@ impl Stylist {
         }
     }
 
-    /// Returns the rule hash target given an element.
-    fn rule_hash_target<E>(&self, element: E) -> E
-        where E: TElement
-    {
-        let is_implemented_pseudo =
-            element.implemented_pseudo_element().is_some();
-
-        // NB: This causes use to rule has pseudo selectors based on the
-        // properties of the originating element (which is fine, given the
-        // find_first_from_right usage).
-        if is_implemented_pseudo {
-            element.closest_non_native_anonymous_ancestor().unwrap()
-        } else {
-            element
-        }
-    }
 
     /// Returns the applicable CSS declarations for the given element by
     /// treating us as an XBL stylesheet-only stylist.
@@ -993,7 +975,7 @@ impl Stylist {
             Some(map) => map,
             None => return,
         };
-        let rule_hash_target = self.rule_hash_target(*element);
+        let rule_hash_target = element.rule_hash_target();
 
         // nsXBLPrototypeResources::ComputeServoStyleSet() added XBL stylesheets under author
         // (doc) level.
@@ -1039,7 +1021,7 @@ impl Stylist {
             Some(map) => map,
             None => return,
         };
-        let rule_hash_target = self.rule_hash_target(*element);
+        let rule_hash_target = element.rule_hash_target();
 
         debug!("Determining if style is shareable: pseudo: {}",
                pseudo_element.is_some());
@@ -1101,8 +1083,8 @@ impl Stylist {
 
         // Step 3b: XBL rules.
         let cut_off_inheritance =
-            rule_hash_target.get_declarations_from_xbl_bindings(pseudo_element,
-                                                                applicable_declarations);
+            element.get_declarations_from_xbl_bindings(pseudo_element,
+                                                       applicable_declarations);
         debug!("XBL: {:?}", context.relations);
 
         if rule_hash_target.matches_user_and_author_rules() && !only_default_rules {
diff --git a/components/style/traversal.rs b/components/style/traversal.rs
index a265f49ba2c..c181f3162a9 100644
--- a/components/style/traversal.rs
+++ b/components/style/traversal.rs
@@ -5,7 +5,7 @@
 //! Traversing the DOM tree; the bloom filter.
 
 use atomic_refcell::AtomicRefCell;
-use context::{SharedStyleContext, StyleContext, ThreadLocalStyleContext};
+use context::{ElementCascadeInputs, StyleContext, SharedStyleContext, ThreadLocalStyleContext};
 use data::{ElementData, ElementStyles};
 use dom::{DirtyDescendants, NodeInfo, OpaqueNode, TElement, TNode};
 use invalidation::element::restyle_hints::{RECASCADE_SELF, RECASCADE_DESCENDANTS, RestyleHint};
@@ -228,7 +228,7 @@ pub trait DomTraversal<E: TElement> : Sync {
                       "must not specify FOR_RECONSTRUCT in combination with UNSTYLED_CHILDREN_ONLY");
 
         if traversal_flags.for_unstyled_children_only() {
-            if root.borrow_data().map_or(true, |d| d.has_styles() && d.styles().is_display_none()) {
+            if root.borrow_data().map_or(true, |d| d.has_styles() && d.styles.is_display_none()) {
                 return PreTraverseToken {
                     traverse: false,
                     unstyled_children_only: false,
@@ -303,7 +303,7 @@ pub trait DomTraversal<E: TElement> : Sync {
                     if pseudo.is_before_or_after() {
                         is_before_or_after_pseudo = true;
                         let still_match =
-                            parent_data.styles().pseudos.get(&pseudo).is_some();
+                            parent_data.styles.pseudos.get(&pseudo).is_some();
 
                         if !still_match {
                             debug_assert!(going_to_reframe,
@@ -404,7 +404,7 @@ pub trait DomTraversal<E: TElement> : Sync {
         debug_assert!(cfg!(feature = "gecko") || parent.has_current_styles(parent_data));
 
         // If the parent computed display:none, we don't style the subtree.
-        if parent_data.styles().is_display_none() {
+        if parent_data.styles.is_display_none() {
             if log.allow() { debug!("Parent {:?} is display:none, culling traversal", parent); }
             return false;
         }
@@ -431,7 +431,7 @@ pub trait DomTraversal<E: TElement> : Sync {
         // recursively drops Servo ElementData when the XBL insertion parent of
         // an Element is changed.
         if cfg!(feature = "gecko") && thread_local.is_initial_style() &&
-           parent_data.styles().primary.values().has_moz_binding() {
+           parent_data.styles.primary().has_moz_binding() {
             if log.allow() { debug!("Parent {:?} has XBL binding, deferring traversal", parent); }
             return false;
         }
@@ -515,7 +515,7 @@ fn resolve_style_internal<E, F>(context: &mut StyleContext<E>,
     let mut display_none_root = None;
 
     // If the Element isn't styled, we need to compute its style.
-    if data.get_styles().is_none() {
+    if !data.has_styles() {
         // Compute the parent style if necessary.
         let parent = element.traversal_parent();
         if let Some(p) = parent {
@@ -549,7 +549,7 @@ fn resolve_style_internal<E, F>(context: &mut StyleContext<E>,
 
     // If we're display:none and none of our ancestors are, we're the root
     // of a display:none subtree.
-    if display_none_root.is_none() && data.styles().is_display_none() {
+    if display_none_root.is_none() && data.styles.is_display_none() {
         display_none_root = Some(element);
     }
 
@@ -576,7 +576,7 @@ pub fn resolve_style<E, F, G, H>(context: &mut StyleContext<E>, element: E,
     // Make them available for the scope of the callback. The callee may use the
     // argument, or perform any other processing that requires the styles to exist
     // on the Element.
-    callback(element.borrow_data().unwrap().styles());
+    callback(&element.borrow_data().unwrap().styles);
 
     // Clear any styles in display:none subtrees or subtrees not in the document,
     // to leave the tree in a valid state.  For display:none subtrees, we leave
@@ -635,7 +635,7 @@ pub fn resolve_default_style<E, F, G, H>(context: &mut StyleContext<E>,
     // Make them available for the scope of the callback. The callee may use the
     // argument, or perform any other processing that requires the styles to exist
     // on the Element.
-    callback(element.borrow_data().unwrap().styles());
+    callback(&element.borrow_data().unwrap().styles);
 
     // Swap the old element data back into the element and its ancestors.
     for entry in old_data {
@@ -685,7 +685,7 @@ pub fn recalc_style_at<E, D>(traversal: &D,
 
         // If we're restyling this element to display:none, throw away all style
         // data in the subtree, notify the caller to early-return.
-        if data.styles().is_display_none() {
+        if data.styles.is_display_none() {
             debug!("{:?} style is display:none - clearing data from descendants.",
                    element);
             clear_descendant_data(element, &|e| unsafe { D::clear_element_data(&e) });
@@ -709,7 +709,7 @@ pub fn recalc_style_at<E, D>(traversal: &D,
     trace!("propagated_hint={:?} \
             is_display_none={:?}, implementing_pseudo={:?}",
            propagated_hint,
-           data.styles().is_display_none(),
+           data.styles.is_display_none(),
            element.implemented_pseudo_element());
     debug_assert!(element.has_current_styles(data) ||
                   context.shared.traversal_flags.for_animation_only(),
@@ -769,7 +769,7 @@ pub fn recalc_style_at<E, D>(traversal: &D,
     // The second case is when we are in a restyle for reconstruction,
     // where we won't need to perform a post-traversal to pick up any
     // change hints.
-    if data.styles().is_display_none() ||
+    if data.styles.is_display_none() ||
        context.shared.traversal_flags.for_reconstruct() {
         unsafe { element.unset_dirty_descendants(); }
     }
@@ -829,7 +829,11 @@ fn compute_style<E, D>(_traversal: &D,
             )
         }
         CascadeWithReplacements(flags) => {
-            let important_rules_changed = element.replace_rules(flags, context, data);
+            // Skipping full matching, load cascade inputs from previous values.
+            context.thread_local.current_element_info
+                   .as_mut().unwrap()
+                   .cascade_inputs = ElementCascadeInputs::new_from_element_data(data);
+            let important_rules_changed = element.replace_rules(flags, context);
             element.cascade_primary_and_pseudos(
                 context,
                 data,
@@ -837,6 +841,10 @@ fn compute_style<E, D>(_traversal: &D,
             )
         }
         CascadeOnly => {
+            // Skipping full matching, load cascade inputs from previous values.
+            context.thread_local.current_element_info
+                   .as_mut().unwrap()
+                   .cascade_inputs = ElementCascadeInputs::new_from_element_data(data);
             element.cascade_primary_and_pseudos(
                 context,
                 data,
diff --git a/components/style/values/specified/color.rs b/components/style/values/specified/color.rs
index b19543c535f..f4aa6cda1c9 100644
--- a/components/style/values/specified/color.rs
+++ b/components/style/values/specified/color.rs
@@ -276,7 +276,7 @@ impl ToComputedValue for Color {
                     let wrap = GeckoElement(body);
                     let borrow = wrap.borrow_data();
                     ComputedColor::rgba(borrow.as_ref().unwrap()
-                                              .styles().primary.values()
+                                              .styles.primary()
                                               .get_color()
                                               .clone_color())
                 } else {
diff --git a/components/style_traits/Cargo.toml b/components/style_traits/Cargo.toml
index 3be76bbfdbb..feeeb7c786a 100644
--- a/components/style_traits/Cargo.toml
+++ b/components/style_traits/Cargo.toml
@@ -16,7 +16,7 @@ gecko = []
 [dependencies]
 app_units = "0.5"
 bitflags = "0.7"
-cssparser = "0.16"
+cssparser = "0.16.1"
 euclid = "0.15"
 heapsize = {version = "0.4", optional = true}
 heapsize_derive = {version = "0.1", optional = true}