Concurrent rule tree, v1

This patch introduces infrastructure for the rule tree, and constructs it.

We don't use it yet, nor have good heuristics for GC'ing it, but this should not
happen anymore once we store the rule node reference in the node.

I haven't messed up with memory orders because I want to do a try run with it,
then mess with them.

Take down the ApplicableDeclarationsCache, use the rule tree for doing the cascade.

20 files changed, 1030 insertions, 526 deletions

diff --git a/components/layout/context.rs b/components/layout/context.rs
index 308295f4196..98e1ffe4092 100644
--- a/components/layout/context.rs
+++ b/components/layout/context.rs
@@ -53,9 +53,6 @@ fn create_or_get_local_context(shared_layout_context: &SharedLayoutContext)
     LOCAL_CONTEXT_KEY.with(|r| {
         let mut r = r.borrow_mut();
         if let Some(context) = r.clone() {
-            if shared_layout_context.style_context.screen_size_changed {
-                context.style_context.applicable_declarations_cache.borrow_mut().evict_all();
-            }
             context
         } else {
             let font_cache_thread = shared_layout_context.font_cache_thread.lock().unwrap().clone();
diff --git a/components/layout_thread/lib.rs b/components/layout_thread/lib.rs
index 537d5935596..60956b00150 100644
--- a/components/layout_thread/lib.rs
+++ b/components/layout_thread/lib.rs
@@ -1170,6 +1170,16 @@ impl LayoutThread {
             node.dump_style();
         }
 
+        if opts::get().dump_rule_tree {
+            shared_layout_context.style_context.stylist.rule_tree.dump_stdout();
+        }
+
+        // GC The rule tree.
+        //
+        // FIXME(emilio): The whole point of the free list is not always freeing
+        // the list, find a good heuristic here for that.
+        unsafe { shared_layout_context.style_context.stylist.rule_tree.gc() }
+
         // Perform post-style recalculation layout passes.
         self.perform_post_style_recalc_layout_passes(&data.reflow_info,
                                                      Some(&data.query_type),
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index 2217651f778..15a4ef816c8 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -328,10 +328,10 @@ impl LayoutElementHelpers for LayoutJS<Element> {
         where V: Push<ApplicableDeclarationBlock>
     {
         #[inline]
-        fn from_declaration(rule: PropertyDeclaration) -> ApplicableDeclarationBlock {
+        fn from_declaration(declaration: PropertyDeclaration) -> ApplicableDeclarationBlock {
             ApplicableDeclarationBlock::from_declarations(
                 Arc::new(RwLock::new(PropertyDeclarationBlock {
-                    declarations: vec![(rule, Importance::Normal)],
+                    declarations: vec![(declaration, Importance::Normal)],
                     important_count: 0,
                 })),
                 Importance::Normal)
@@ -814,10 +814,7 @@ impl Element {
         }
         None
     }
-}
-
 
-impl Element {
     pub fn is_focusable_area(&self) -> bool {
         if self.is_actually_disabled() {
             return false;
@@ -856,10 +853,7 @@ impl Element {
             _ => false,
         }
     }
-}
-
 
-impl Element {
     pub fn push_new_attribute(&self,
                               local_name: LocalName,
                               value: AttrValue,
diff --git a/components/script_layout_interface/wrapper_traits.rs b/components/script_layout_interface/wrapper_traits.rs
index a241ae12099..7bd91bdb0d0 100644
--- a/components/script_layout_interface/wrapper_traits.rs
+++ b/components/script_layout_interface/wrapper_traits.rs
@@ -375,13 +375,13 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
                                 .borrow()
                                 .current_styles().pseudos.contains_key(&style_pseudo) {
                             let mut data = self.get_style_data().unwrap().borrow_mut();
-                            let new_style =
+                            let new_style_and_rule_node =
                                 context.stylist.precomputed_values_for_pseudo(
                                     &style_pseudo,
                                     Some(&data.current_styles().primary),
                                     false);
                             data.current_pseudos_mut()
-                                .insert(style_pseudo.clone(), new_style.unwrap());
+                                .insert(style_pseudo.clone(), new_style_and_rule_node.unwrap());
                         }
                     }
                     PseudoElementCascadeType::Lazy => {
@@ -404,7 +404,7 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
 
                 self.get_style_data().unwrap().borrow()
                     .current_styles().pseudos.get(&style_pseudo)
-                    .unwrap().clone()
+                    .unwrap().0.clone()
             }
         }
     }
@@ -413,7 +413,7 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
     fn selected_style(&self) -> Arc<ServoComputedValues> {
         let data = self.get_style_data().unwrap().borrow();
         data.current_styles().pseudos
-            .get(&PseudoElement::Selection)
+            .get(&PseudoElement::Selection).map(|s| &s.0)
             .unwrap_or(&data.current_styles().primary)
             .clone()
     }
@@ -432,7 +432,8 @@ pub trait ThreadSafeLayoutElement: Clone + Copy + Sized + Debug +
             PseudoElementType::Normal
                 => data.current_styles().primary.clone(),
             other
-                => data.current_styles().pseudos.get(&other.style_pseudo_element()).unwrap().clone(),
+                => data.current_styles().pseudos
+                       .get(&other.style_pseudo_element()).unwrap().0.clone(),
         }
     }
 
diff --git a/components/style/animation.rs b/components/style/animation.rs
index b106db1812e..d681cb81a29 100644
--- a/components/style/animation.rs
+++ b/components/style/animation.rs
@@ -7,6 +7,7 @@
 use Atom;
 use bezier::Bezier;
 use context::SharedStyleContext;
+use declarations_iterators::RawDeclarationsIterator;
 use dom::{OpaqueNode, UnsafeNode};
 use euclid::point::Point2D;
 use keyframes::{KeyframesStep, KeyframesStepValue};
@@ -17,7 +18,6 @@ use properties::longhands::animation_iteration_count::computed_value::AnimationI
 use properties::longhands::animation_play_state::computed_value::AnimationPlayState;
 use properties::longhands::transition_timing_function::computed_value::StartEnd;
 use properties::longhands::transition_timing_function::computed_value::TransitionTimingFunction;
-use selector_matching::ApplicableDeclarationBlock;
 use std::sync::Arc;
 use std::sync::mpsc::Sender;
 use timer::Timer;
@@ -385,23 +385,24 @@ fn compute_style_for_animation_step(context: &SharedStyleContext,
                                     style_from_cascade: &ComputedValues)
                                     -> ComputedValues {
     match step.value {
-        // TODO: avoiding this spurious clone might involve having to create
-        // an Arc in the below (more common case).
         KeyframesStepValue::ComputedValues => style_from_cascade.clone(),
         KeyframesStepValue::Declarations { block: ref declarations } => {
-            let declaration_block = ApplicableDeclarationBlock {
-                mixed_declarations: declarations.clone(),
-                importance: Importance::Normal,
-                source_order: 0,
-                specificity: ::std::u32::MAX,
-            };
-            let (computed, _) = properties::cascade(context.viewport_size,
-                                                    &[declaration_block],
-                                                    Some(previous_style),
-                                                    None,
-                                                    None,
-                                                    context.error_reporter.clone(),
-                                                    CascadeFlags::empty());
+            let guard = declarations.read();
+
+            // No !important in keyframes.
+            debug_assert!(guard.declarations.iter()
+                            .all(|&(_, importance)| importance == Importance::Normal));
+
+            let iter = RawDeclarationsIterator::new(&guard.declarations);
+
+            let computed =
+                properties::apply_declarations(context.viewport_size,
+                                               /* is_root = */ false,
+                                               iter,
+                                               previous_style,
+                                               /* cascade_info = */ None,
+                                               context.error_reporter.clone(),
+                                               CascadeFlags::empty());
             computed
         }
     }
diff --git a/components/style/context.rs b/components/style/context.rs
index fc3724452a7..2707a799713 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -9,7 +9,7 @@ use app_units::Au;
 use dom::OpaqueNode;
 use error_reporting::ParseErrorReporter;
 use euclid::Size2D;
-use matching::{ApplicableDeclarationsCache, StyleSharingCandidateCache};
+use matching::StyleSharingCandidateCache;
 use parking_lot::RwLock;
 use selector_matching::Stylist;
 use std::cell::RefCell;
@@ -66,7 +66,6 @@ pub struct SharedStyleContext {
 }
 
 pub struct LocalStyleContext {
-    pub applicable_declarations_cache: RefCell<ApplicableDeclarationsCache>,
     pub style_sharing_candidate_cache: RefCell<StyleSharingCandidateCache>,
     /// A channel on which new animations that have been triggered by style
     /// recalculation can be sent.
@@ -76,7 +75,6 @@ pub struct LocalStyleContext {
 impl LocalStyleContext {
     pub fn new(local_context_creation_data: &LocalStyleContextCreationInfo) -> Self {
         LocalStyleContext {
-            applicable_declarations_cache: RefCell::new(ApplicableDeclarationsCache::new()),
             style_sharing_candidate_cache: RefCell::new(StyleSharingCandidateCache::new()),
             new_animations_sender: local_context_creation_data.new_animations_sender.clone(),
         }
diff --git a/components/style/data.rs b/components/style/data.rs
index f6011c81fcb..6f4a34e90ca 100644
--- a/components/style/data.rs
+++ b/components/style/data.rs
@@ -5,6 +5,7 @@
 //! Per-node data used in style calculation.
 
 use properties::ComputedValues;
+use rule_tree::StrongRuleNode;
 use selector_impl::PseudoElement;
 use std::collections::HashMap;
 use std::hash::BuildHasherDefault;
@@ -12,7 +13,7 @@ use std::mem;
 use std::ops::{Deref, DerefMut};
 use std::sync::Arc;
 
-type PseudoStylesInner = HashMap<PseudoElement, Arc<ComputedValues>,
+type PseudoStylesInner = HashMap<PseudoElement, (Arc<ComputedValues>, StrongRuleNode),
                                  BuildHasherDefault<::fnv::FnvHasher>>;
 #[derive(Clone, Debug)]
 pub struct PseudoStyles(PseudoStylesInner);
@@ -39,14 +40,18 @@ pub struct ElementStyles {
     /// The results of CSS styling for this node.
     pub primary: Arc<ComputedValues>,
 
+    /// The rule node representing the last rule matched for this node.
+    pub rule_node: StrongRuleNode,
+
     /// The results of CSS styling for each pseudo-element (if any).
     pub pseudos: PseudoStyles,
 }
 
 impl ElementStyles {
-    pub fn new(primary: Arc<ComputedValues>) -> Self {
+    pub fn new(primary: Arc<ComputedValues>, rule_node: StrongRuleNode) -> Self {
         ElementStyles {
             primary: primary,
+            rule_node: rule_node,
             pseudos: PseudoStyles::empty(),
         }
     }
@@ -185,11 +190,6 @@ impl ElementData {
         }
     }
 
-    pub fn style_text_node(&mut self, style: Arc<ComputedValues>) {
-        self.styles = ElementDataStyles::Current(ElementStyles::new(style));
-        self.restyle_data = None;
-    }
-
     pub fn finish_styling(&mut self, styles: ElementStyles) {
         debug_assert!(self.styles.is_previous());
         self.styles = ElementDataStyles::Current(styles);
diff --git a/components/style/declarations_iterators.rs b/components/style/declarations_iterators.rs
new file mode 100644
index 00000000000..27e37e59e71
--- /dev/null
+++ b/components/style/declarations_iterators.rs
@@ -0,0 +1,83 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! A set of simple iterators to be reused for doing the cascade.
+
+use properties::{Importance, PropertyDeclaration};
+
+
+/// An iterator that applies the declarations in a list that matches the given
+/// importance.
+#[derive(Clone)]
+pub struct SimpleDeclarationsIterator<'a> {
+    declarations: &'a [(PropertyDeclaration, Importance)],
+    importance: Importance,
+    index: usize,
+}
+
+impl<'a> SimpleDeclarationsIterator<'a> {
+    pub fn new(declarations: &'a [(PropertyDeclaration, Importance)],
+               importance: Importance) -> Self {
+        SimpleDeclarationsIterator {
+            declarations: declarations,
+            importance: importance,
+            index: 0,
+        }
+    }
+}
+
+impl<'a> Iterator for SimpleDeclarationsIterator<'a> {
+    type Item = &'a PropertyDeclaration;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        loop {
+            if self.index == self.declarations.len() {
+                return None;
+            }
+
+            let (ref decl, importance) =
+                self.declarations[self.declarations.len() - self.index - 1];
+
+            self.index += 1;
+
+            if importance == self.importance {
+                return Some(decl)
+            }
+        }
+    }
+}
+
+/// An iterator that applies the declarations in a list without checking any
+/// order.
+#[derive(Clone)]
+pub struct RawDeclarationsIterator<'a> {
+    declarations: &'a [(PropertyDeclaration, Importance)],
+    index: usize,
+}
+
+impl<'a> RawDeclarationsIterator<'a> {
+    pub fn new(declarations: &'a [(PropertyDeclaration, Importance)]) -> Self {
+        RawDeclarationsIterator {
+            declarations: declarations,
+            index: 0,
+        }
+    }
+}
+
+impl<'a> Iterator for RawDeclarationsIterator<'a> {
+    type Item = &'a PropertyDeclaration;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.index == self.declarations.len() {
+            return None;
+        }
+
+        let (ref decl, _) =
+            self.declarations[self.declarations.len() - self.index - 1];
+
+        self.index += 1;
+
+        return Some(decl)
+    }
+}
diff --git a/components/style/gecko/context.rs b/components/style/gecko/context.rs
index 068b81560d8..4cfb3152b16 100644
--- a/components/style/gecko/context.rs
+++ b/components/style/gecko/context.rs
@@ -13,9 +13,6 @@ fn create_or_get_local_context(shared: &SharedStyleContext) -> Rc<LocalStyleCont
     LOCAL_CONTEXT_KEY.with(|r| {
         let mut r = r.borrow_mut();
         if let Some(context) = r.clone() {
-            if shared.screen_size_changed {
-                context.applicable_declarations_cache.borrow_mut().evict_all();
-            }
             context
         } else {
             let context = Rc::new(LocalStyleContext::new(&shared.local_context_creation_data.lock().unwrap()));
diff --git a/components/style/gecko/wrapper.rs b/components/style/gecko/wrapper.rs
index d57d4ecd4a0..3723045bae7 100644
--- a/components/style/gecko/wrapper.rs
+++ b/components/style/gecko/wrapper.rs
@@ -334,7 +334,7 @@ impl<'le> GeckoElement<'le> {
 
     pub fn get_pseudo_style(&self, pseudo: &PseudoElement) -> Option<Arc<ComputedValues>> {
         self.borrow_data().and_then(|data| data.current_styles().pseudos
-                                               .get(pseudo).map(|c| c.clone()))
+                                               .get(pseudo).map(|c| c.0.clone()))
     }
 
     pub fn ensure_data(&self) -> &AtomicRefCell<ElementData> {
diff --git a/components/style/lib.rs b/components/style/lib.rs
index 687a54ca644..5b214485564 100644
--- a/components/style/lib.rs
+++ b/components/style/lib.rs
@@ -99,6 +99,7 @@ pub mod cascade_info;
 pub mod context;
 pub mod custom_properties;
 pub mod data;
+pub mod declarations_iterators;
 pub mod dom;
 pub mod element_state;
 pub mod error_reporting;
@@ -114,6 +115,7 @@ pub mod parallel;
 pub mod parser;
 pub mod refcell;
 pub mod restyle_hints;
+pub mod rule_tree;
 pub mod selector_impl;
 pub mod selector_matching;
 pub mod sequential;
diff --git a/components/style/matching.rs b/components/style/matching.rs
index 0887ebc823a..ac4bdb0b59a 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -8,26 +8,24 @@
 
 use {Atom, LocalName};
 use animation;
-use arc_ptr_eq;
 use atomic_refcell::AtomicRefMut;
-use cache::{LRUCache, SimpleHashCache};
+use cache::LRUCache;
 use cascade_info::CascadeInfo;
 use context::{SharedStyleContext, StyleContext};
 use data::{ElementData, ElementStyles, PseudoStyles};
 use dom::{TElement, TNode, TRestyleDamage, UnsafeNode};
 use properties::{CascadeFlags, ComputedValues, SHAREABLE, cascade};
 use properties::longhands::display::computed_value as display;
-use selector_impl::{PseudoElement, TheSelectorImpl};
+use rule_tree::StrongRuleNode;
+use selector_impl::{TheSelectorImpl, PseudoElement};
 use selector_matching::{ApplicableDeclarationBlock, Stylist};
 use selectors::MatchAttr;
 use selectors::bloom::BloomFilter;
 use selectors::matching::{AFFECTED_BY_PSEUDO_ELEMENTS, MatchingReason, StyleRelations};
 use sink::ForgetfulSink;
-use smallvec::SmallVec;
 use std::collections::HashMap;
-use std::hash::{BuildHasherDefault, Hash, Hasher};
+use std::hash::BuildHasherDefault;
 use std::mem;
-use std::ops::Deref;
 use std::slice::IterMut;
 use std::sync::Arc;
 use util::opts;
@@ -53,7 +51,7 @@ fn create_common_style_affecting_attributes_from_element<E: TElement>(element: &
 }
 
 pub struct ApplicableDeclarations {
-    pub normal: SmallVec<[ApplicableDeclarationBlock; 16]>,
+    pub normal: Vec<ApplicableDeclarationBlock>,
     pub per_pseudo: HashMap<PseudoElement,
                             Vec<ApplicableDeclarationBlock>,
                             BuildHasherDefault<::fnv::FnvHasher>>,
@@ -65,7 +63,7 @@ pub struct ApplicableDeclarations {
 impl ApplicableDeclarations {
     pub fn new() -> Self {
         let mut applicable_declarations = ApplicableDeclarations {
-            normal: SmallVec::new(),
+            normal: Vec::with_capacity(16),
             per_pseudo: HashMap::with_hasher(Default::default()),
             normal_shareable: false,
         };
@@ -78,105 +76,6 @@ impl ApplicableDeclarations {
     }
 }
 
-#[derive(Clone)]
-pub struct ApplicableDeclarationsCacheEntry {
-    pub declarations: Vec<ApplicableDeclarationBlock>,
-}
-
-impl ApplicableDeclarationsCacheEntry {
-    fn new(declarations: Vec<ApplicableDeclarationBlock>) -> ApplicableDeclarationsCacheEntry {
-        ApplicableDeclarationsCacheEntry {
-            declarations: declarations,
-        }
-    }
-}
-
-impl PartialEq for ApplicableDeclarationsCacheEntry {
-    fn eq(&self, other: &ApplicableDeclarationsCacheEntry) -> bool {
-        let this_as_query = ApplicableDeclarationsCacheQuery::new(&*self.declarations);
-        this_as_query.eq(other)
-    }
-}
-impl Eq for ApplicableDeclarationsCacheEntry {}
-
-impl Hash for ApplicableDeclarationsCacheEntry {
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        let tmp = ApplicableDeclarationsCacheQuery::new(&*self.declarations);
-        tmp.hash(state);
-    }
-}
-
-struct ApplicableDeclarationsCacheQuery<'a> {
-    declarations: &'a [ApplicableDeclarationBlock],
-}
-
-impl<'a> ApplicableDeclarationsCacheQuery<'a> {
-    fn new(declarations: &'a [ApplicableDeclarationBlock]) -> ApplicableDeclarationsCacheQuery<'a> {
-        ApplicableDeclarationsCacheQuery {
-            declarations: declarations,
-        }
-    }
-}
-
-impl<'a> PartialEq for ApplicableDeclarationsCacheQuery<'a> {
-    fn eq(&self, other: &ApplicableDeclarationsCacheQuery<'a>) -> bool {
-        self.declarations.len() == other.declarations.len() &&
-        self.declarations.iter().zip(other.declarations).all(|(this, other)| {
-            arc_ptr_eq(&this.mixed_declarations, &other.mixed_declarations) &&
-            this.importance == other.importance
-        })
-    }
-}
-impl<'a> Eq for ApplicableDeclarationsCacheQuery<'a> {}
-
-impl<'a> PartialEq<ApplicableDeclarationsCacheEntry> for ApplicableDeclarationsCacheQuery<'a> {
-    fn eq(&self, other: &ApplicableDeclarationsCacheEntry) -> bool {
-        let other_as_query = ApplicableDeclarationsCacheQuery::new(&other.declarations);
-        self.eq(&other_as_query)
-    }
-}
-
-impl<'a> Hash for ApplicableDeclarationsCacheQuery<'a> {
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        for declaration in self.declarations {
-            // Each declaration contians an Arc, which is a stable
-            // pointer; we use that for hashing and equality.
-            let ptr: *const _ = Arc::deref(&declaration.mixed_declarations);
-            ptr.hash(state);
-            declaration.importance.hash(state);
-        }
-    }
-}
-
-static APPLICABLE_DECLARATIONS_CACHE_SIZE: usize = 32;
-
-pub struct ApplicableDeclarationsCache {
-    cache: SimpleHashCache<ApplicableDeclarationsCacheEntry, Arc<ComputedValues>>,
-}
-
-impl ApplicableDeclarationsCache {
-    pub fn new() -> Self {
-        ApplicableDeclarationsCache {
-            cache: SimpleHashCache::new(APPLICABLE_DECLARATIONS_CACHE_SIZE),
-        }
-    }
-
-    pub fn find(&self, declarations: &[ApplicableDeclarationBlock]) -> Option<Arc<ComputedValues>> {
-        match self.cache.find(&ApplicableDeclarationsCacheQuery::new(declarations)) {
-            None => None,
-            Some(ref values) => Some((*values).clone()),
-        }
-    }
-
-    pub fn insert(&mut self, declarations: Vec<ApplicableDeclarationBlock>, style: Arc<ComputedValues>) {
-        self.cache.insert(ApplicableDeclarationsCacheEntry::new(declarations), style)
-    }
-
-    pub fn evict_all(&mut self) {
-        self.cache.evict_all();
-    }
-}
-
 /// Information regarding a candidate.
 ///
 /// TODO: We can stick a lot more info here.
@@ -184,8 +83,6 @@ impl ApplicableDeclarationsCache {
 struct StyleSharingCandidate {
     /// The node, guaranteed to be an element.
     node: UnsafeNode,
-    /// The cached computed style, here for convenience.
-    style: Arc<ComputedValues>,
     /// The cached common style affecting attribute info.
     common_style_affecting_attributes: Option<CommonStyleAffectingAttributes>,
     /// the cached class names.
@@ -195,7 +92,6 @@ struct StyleSharingCandidate {
 impl PartialEq<StyleSharingCandidate> for StyleSharingCandidate {
     fn eq(&self, other: &Self) -> bool {
         self.node == other.node &&
-            arc_ptr_eq(&self.style, &other.style) &&
             self.common_style_affecting_attributes == other.common_style_affecting_attributes
     }
 }
@@ -234,7 +130,7 @@ fn element_matches_candidate<E: TElement>(element: &E,
                                           candidate: &mut StyleSharingCandidate,
                                           candidate_element: &E,
                                           shared_context: &SharedStyleContext)
-                                          -> Result<Arc<ComputedValues>, CacheMiss> {
+                                          -> Result<(Arc<ComputedValues>, StrongRuleNode), CacheMiss> {
     macro_rules! miss {
         ($miss: ident) => {
             return Err(CacheMiss::$miss);
@@ -295,7 +191,11 @@ fn element_matches_candidate<E: TElement>(element: &E,
         miss!(NonCommonAttrRules)
     }
 
-    Ok(candidate.style.clone())
+    let data = candidate_element.borrow_data().unwrap();
+    let current_styles = data.get_current_styles().unwrap();
+
+    Ok((current_styles.primary.clone(),
+        current_styles.rule_node.clone()))
 }
 
 fn have_same_common_style_affecting_attributes<E: TElement>(element: &E,
@@ -458,7 +358,6 @@ impl StyleSharingCandidateCache {
 
         self.cache.insert(StyleSharingCandidate {
             node: element.as_node().to_unsafe(),
-            style: style.clone(),
             common_style_affecting_attributes: None,
             class_attributes: None,
         }, ());
@@ -490,7 +389,6 @@ pub enum StyleSharingResult<ConcreteRestyleDamage: TRestyleDamage> {
 // FIXME(pcwalton): Unify with `CascadeFlags`, perhaps?
 struct CascadeBooleans {
     shareable: bool,
-    cacheable: bool,
     animate: bool,
 }
 
@@ -503,23 +401,16 @@ trait PrivateMatchMethods: TElement {
                                             context: &Ctx,
                                             parent_style: Option<&Arc<ComputedValues>>,
                                             old_style: Option<&Arc<ComputedValues>>,
-                                            applicable_declarations: &[ApplicableDeclarationBlock],
-                                            applicable_declarations_cache:
-                                             &mut ApplicableDeclarationsCache,
+                                            applicable_declarations: &mut Vec<ApplicableDeclarationBlock>,
                                             booleans: CascadeBooleans)
-                                            -> Arc<ComputedValues>
+                                            -> (Arc<ComputedValues>, StrongRuleNode)
         where Ctx: StyleContext<'a>
     {
-        let mut cacheable = booleans.cacheable;
         let shared_context = context.shared_context();
-
-        // Don’t cache applicable declarations for elements with a style attribute.
-        // Since the style attribute contributes to that set, no other element would have the same set
-        // and the cache would not be effective anyway.
-        // This also works around the test failures at
-        // https://github.com/servo/servo/pull/13459#issuecomment-250717584
-        let has_style_attribute = self.style_attribute().is_some();
-        cacheable = cacheable && !has_style_attribute;
+        let rule_node =
+            shared_context.stylist.rule_tree
+                          .insert_ordered_rules(
+                              applicable_declarations.drain(..).map(|d| (d.source, d.importance)));
 
         let mut cascade_info = CascadeInfo::new();
         let mut cascade_flags = CascadeFlags::empty();
@@ -527,26 +418,18 @@ trait PrivateMatchMethods: TElement {
             cascade_flags.insert(SHAREABLE)
         }
 
-        let (this_style, is_cacheable) = match parent_style {
+        let this_style = match parent_style {
             Some(ref parent_style) => {
-                let cache_entry = applicable_declarations_cache.find(applicable_declarations);
-                let cached_computed_values = match cache_entry {
-                    Some(ref style) => Some(&**style),
-                    None => None,
-                };
-
                 cascade(shared_context.viewport_size,
-                        applicable_declarations,
+                        &rule_node,
                         Some(&***parent_style),
-                        cached_computed_values,
                         Some(&mut cascade_info),
                         shared_context.error_reporter.clone(),
                         cascade_flags)
             }
             None => {
                 cascade(shared_context.viewport_size,
-                        applicable_declarations,
-                        None,
+                        &rule_node,
                         None,
                         Some(&mut cascade_info),
                         shared_context.error_reporter.clone(),
@@ -555,43 +438,30 @@ trait PrivateMatchMethods: TElement {
         };
         cascade_info.finish(&self.as_node());
 
-        cacheable = cacheable && is_cacheable;
-
         let mut this_style = Arc::new(this_style);
 
         if booleans.animate {
             let new_animations_sender = &context.local_context().new_animations_sender;
             let this_opaque = self.as_node().opaque();
             // Trigger any present animations if necessary.
-            let mut animations_started = animation::maybe_start_animations(
-                &shared_context,
-                new_animations_sender,
-                this_opaque,
-                &this_style);
+            animation::maybe_start_animations(&shared_context,
+                                              new_animations_sender,
+                                              this_opaque, &this_style);
 
             // Trigger transitions if necessary. This will reset `this_style` back
             // to its old value if it did trigger a transition.
             if let Some(ref style) = old_style {
-                animations_started |=
-                    animation::start_transitions_if_applicable(
-                        new_animations_sender,
-                        this_opaque,
-                        self.as_node().to_unsafe(),
-                        &**style,
-                        &mut this_style,
-                        &shared_context.timer);
+                animation::start_transitions_if_applicable(
+                    new_animations_sender,
+                    this_opaque,
+                    self.as_node().to_unsafe(),
+                    &**style,
+                    &mut this_style,
+                    &shared_context.timer);
             }
-
-            cacheable = cacheable && !animations_started
-        }
-
-        // Cache the resolved style if it was cacheable.
-        if cacheable {
-            applicable_declarations_cache.insert(applicable_declarations.to_vec(),
-                                                 this_style.clone());
         }
 
-        this_style
+        (this_style, rule_node)
     }
 
     fn update_animations_for_cascade(&self,
@@ -636,7 +506,7 @@ trait PrivateMatchMethods: TElement {
     fn share_style_with_candidate_if_possible(&self,
                                               shared_context: &SharedStyleContext,
                                               candidate: &mut StyleSharingCandidate)
-                                              -> Result<Arc<ComputedValues>, CacheMiss> {
+                                              -> Result<(Arc<ComputedValues>, StrongRuleNode), CacheMiss> {
         let candidate_element = unsafe {
             Self::ConcreteNode::from_unsafe(&candidate.node).as_element().unwrap()
         };
@@ -652,9 +522,10 @@ pub trait MatchMethods : TElement {
     fn match_element(&self,
                      stylist: &Stylist,
                      parent_bf: Option<&BloomFilter>,
-                     applicable_declarations: &mut ApplicableDeclarations)
+                     mut applicable_declarations: &mut ApplicableDeclarations)
                      -> StyleRelations {
         use traversal::relations_are_shareable;
+
         let style_attribute = self.style_attribute();
 
         let mut relations =
@@ -711,7 +582,7 @@ pub trait MatchMethods : TElement {
         for (i, &mut (ref mut candidate, ())) in style_sharing_candidate_cache.iter_mut().enumerate() {
             let sharing_result = self.share_style_with_candidate_if_possible(shared_context, candidate);
             match sharing_result {
-                Ok(shared_style) => {
+                Ok((shared_style, rule_node)) => {
                     // Yay, cache hit. Share the style.
 
                     // TODO: add the display: none optimisation here too! Even
@@ -728,7 +599,7 @@ pub trait MatchMethods : TElement {
                             }
                         };
 
-                    data.finish_styling(ElementStyles::new(shared_style));
+                    data.finish_styling(ElementStyles::new(shared_style, rule_node));
 
                     return StyleSharingResult::StyleWasShared(i, damage)
                 }
@@ -848,7 +719,7 @@ pub trait MatchMethods : TElement {
                                     context: &Ctx,
                                     mut data: AtomicRefMut<ElementData>,
                                     parent: Option<Self>,
-                                    applicable_declarations: &ApplicableDeclarations)
+                                    mut applicable_declarations: ApplicableDeclarations)
         where Ctx: StyleContext<'a>
     {
         // Get our parent's style.
@@ -857,40 +728,39 @@ pub trait MatchMethods : TElement {
 
         let mut new_styles;
 
-        let mut applicable_declarations_cache =
-            context.local_context().applicable_declarations_cache.borrow_mut();
-
         let damage = {
-            // Update animations before the cascade. This may modify the value of the old primary
-            // style.
-            let cacheable = data.previous_styles_mut().map_or(true,
-                |x| !self.update_animations_for_cascade(context.shared_context(), &mut x.primary));
             let shareable = applicable_declarations.normal_shareable;
+
             let (old_primary, old_pseudos) = match data.previous_styles_mut() {
                 None => (None, None),
-                Some(x) => (Some(&x.primary), Some(&mut x.pseudos)),
+                Some(previous) => {
+                    // Update animations before the cascade. This may modify the
+                    // value of the old primary style.
+                    self.update_animations_for_cascade(context.shared_context(),
+                                                       &mut previous.primary);
+                    (Some(&previous.primary), Some(&mut previous.pseudos))
+                }
             };
 
-
-            new_styles = ElementStyles::new(
+            let (new_style, rule_node) =
                 self.cascade_node_pseudo_element(context,
-                                                 parent_style.clone(),
+                                                 parent_style,
                                                  old_primary,
-                                                 &applicable_declarations.normal,
-                                                 &mut applicable_declarations_cache,
+                                                 &mut applicable_declarations.normal,
                                                  CascadeBooleans {
                                                      shareable: shareable,
-                                                     cacheable: cacheable,
                                                      animate: true,
-                                                 }));
+                                                 });
+
+            new_styles = ElementStyles::new(new_style, rule_node);
 
             let damage =
                 self.compute_damage_and_cascade_pseudos(old_primary,
                                                         old_pseudos,
                                                         &new_styles.primary,
                                                         &mut new_styles.pseudos,
-                                                        context, applicable_declarations,
-                                                        &mut applicable_declarations_cache);
+                                                        context,
+                                                        &mut applicable_declarations);
 
             self.as_node().set_can_be_fragmented(parent.map_or(false, |p| {
                 p.as_node().can_be_fragmented() ||
@@ -912,8 +782,7 @@ pub trait MatchMethods : TElement {
                                                    new_primary: &Arc<ComputedValues>,
                                                    new_pseudos: &mut PseudoStyles,
                                                    context: &Ctx,
-                                                   applicable_declarations: &ApplicableDeclarations,
-                                                   mut applicable_declarations_cache: &mut ApplicableDeclarationsCache)
+                                                   applicable_declarations: &mut ApplicableDeclarations)
                                                    -> Self::ConcreteRestyleDamage
         where Ctx: StyleContext<'a>
     {
@@ -953,58 +822,55 @@ pub trait MatchMethods : TElement {
 
         let rebuild_and_reflow =
             Self::ConcreteRestyleDamage::rebuild_and_reflow();
-        let no_damage = Self::ConcreteRestyleDamage::empty();
 
         debug_assert!(new_pseudos.is_empty());
         <Self as MatchAttr>::Impl::each_eagerly_cascaded_pseudo_element(|pseudo| {
-            let applicable_declarations_for_this_pseudo =
-                applicable_declarations.per_pseudo.get(&pseudo).unwrap();
+            let mut applicable_declarations_for_this_pseudo =
+                applicable_declarations.per_pseudo.get_mut(&pseudo).unwrap();
 
             let has_declarations =
                 !applicable_declarations_for_this_pseudo.is_empty();
 
             // Grab the old pseudo style for analysis.
-            let mut old_pseudo_style = old_pseudos.as_mut().and_then(|x| x.remove(&pseudo));
+            let mut maybe_old_pseudo_style_and_rule_node =
+                old_pseudos.as_mut().and_then(|x| x.remove(&pseudo));
 
             if has_declarations {
                 // We have declarations, so we need to cascade. Compute parameters.
                 let animate = <Self as MatchAttr>::Impl::pseudo_is_before_or_after(&pseudo);
-                let cacheable = if animate && old_pseudo_style.is_some() {
-                    // Update animations before the cascade. This may modify
-                    // the value of old_pseudo_style.
-                    !self.update_animations_for_cascade(context.shared_context(),
-                                                        old_pseudo_style.as_mut().unwrap())
-                } else {
-                    true
-                };
-
-                let new_pseudo_style =
+                if animate {
+                    if let Some((ref mut old_pseudo_style, _)) = maybe_old_pseudo_style_and_rule_node {
+                        // Update animations before the cascade. This may modify
+                        // the value of old_pseudo_style.
+                        self.update_animations_for_cascade(context.shared_context(),
+                                                           old_pseudo_style);
+                    }
+                }
+
+                let (new_pseudo_style, new_rule_node) =
                     self.cascade_node_pseudo_element(context, Some(new_primary),
-                                                     old_pseudo_style.as_ref(),
-                                                     &*applicable_declarations_for_this_pseudo,
-                                                     &mut applicable_declarations_cache,
+                                                     maybe_old_pseudo_style_and_rule_node.as_ref().map(|s| &s.0),
+                                                     &mut applicable_declarations_for_this_pseudo,
                                                      CascadeBooleans {
                                                          shareable: false,
-                                                         cacheable: cacheable,
                                                          animate: animate,
                                                      });
 
                 // Compute restyle damage unless we've already maxed it out.
                 if damage != rebuild_and_reflow {
-                    damage = damage | match old_pseudo_style {
+                    damage = damage | match maybe_old_pseudo_style_and_rule_node {
                         None => rebuild_and_reflow,
-                        Some(ref old) => self.compute_restyle_damage(Some(old), &new_pseudo_style,
-                                                                     Some(&pseudo)),
+                        Some((ref old, _)) => self.compute_restyle_damage(Some(old), &new_pseudo_style,
+                                                                          Some(&pseudo)),
                     };
                 }
 
                 // Insert the new entry into the map.
-                let existing = new_pseudos.insert(pseudo, new_pseudo_style);
+                let existing = new_pseudos.insert(pseudo, (new_pseudo_style, new_rule_node));
                 debug_assert!(existing.is_none());
             } else {
-                damage = damage | match old_pseudo_style {
-                    Some(_) => rebuild_and_reflow,
-                    None => no_damage,
+                if maybe_old_pseudo_style_and_rule_node.is_some() {
+                    damage = rebuild_and_reflow;
                 }
             }
         });
diff --git a/components/style/parallel.rs b/components/style/parallel.rs
index 8c30868224d..6740c4f379c 100644
--- a/components/style/parallel.rs
+++ b/components/style/parallel.rs
@@ -33,7 +33,8 @@ pub fn run_queue_with_custom_work_data_type<To, F, SharedContext: Sync>(
         queue: &mut WorkQueue<SharedContext, WorkQueueData>,
         callback: F,
         shared: &SharedContext)
-        where To: 'static + Send, F: FnOnce(&mut WorkQueue<SharedContext, To>) {
+    where To: 'static + Send, F: FnOnce(&mut WorkQueue<SharedContext, To>)
+{
     let queue: &mut WorkQueue<SharedContext, To> = unsafe {
         mem::transmute(queue)
     };
@@ -73,7 +74,8 @@ pub fn traverse_dom<N, C>(root: N,
 #[inline(always)]
 fn top_down_dom<N, C>(unsafe_nodes: UnsafeNodeList,
                       proxy: &mut WorkerProxy<C::SharedContext, UnsafeNodeList>)
-                      where N: TNode, C: DomTraversalContext<N> {
+    where N: TNode, C: DomTraversalContext<N>
+{
     let context = C::new(proxy.user_data(), unsafe_nodes.1);
 
     let mut discovered_child_nodes = vec![];
diff --git a/components/style/properties/properties.mako.rs b/components/style/properties/properties.mako.rs
index c0543d7ab3f..f13d1289d60 100644
--- a/components/style/properties/properties.mako.rs
+++ b/components/style/properties/properties.mako.rs
@@ -28,12 +28,12 @@ use computed_values;
 #[cfg(feature = "servo")] use logical_geometry::{LogicalMargin, PhysicalSide};
 use logical_geometry::WritingMode;
 use parser::{ParserContext, ParserContextExtraData};
-use selector_matching::{ApplicableDeclarationBlock, ApplicableDeclarationBlockReadGuard};
 use stylesheets::Origin;
 #[cfg(feature = "servo")] use values::LocalToCss;
 use values::HasViewportPercentage;
-use values::computed::{self, ToComputedValue};
+use values::computed;
 use cascade_info::CascadeInfo;
+use rule_tree::StrongRuleNode;
 #[cfg(feature = "servo")] use values::specified::BorderStyle;
 
 use self::property_bit_field::PropertyBitField;
@@ -1382,120 +1382,6 @@ mod lazy_static_module {
     }
 }
 
-/// Fast path for the function below. Only computes new inherited styles.
-#[allow(unused_mut, unused_imports)]
-fn cascade_with_cached_declarations(
-        viewport_size: Size2D<Au>,
-        applicable_declarations: &[ApplicableDeclarationBlockReadGuard],
-        shareable: bool,
-        parent_style: &ComputedValues,
-        cached_style: &ComputedValues,
-        custom_properties: Option<Arc<::custom_properties::ComputedValuesMap>>,
-        mut cascade_info: Option<<&mut CascadeInfo>,
-        mut error_reporter: StdBox<ParseErrorReporter + Send>)
-        -> ComputedValues {
-    let mut context = computed::Context {
-        is_root_element: false,
-        viewport_size: viewport_size,
-        inherited_style: parent_style,
-        style: ComputedValues::new(
-            custom_properties,
-            shareable,
-            WritingMode::empty(),
-            parent_style.root_font_size(),
-            % for style_struct in data.active_style_structs():
-                % if style_struct.inherited:
-                    parent_style
-                % else:
-                    cached_style
-                % endif
-                    .clone_${style_struct.name_lower}(),
-            % endfor
-        ),
-    };
-    let mut seen = PropertyBitField::new();
-    // Declaration blocks are stored in increasing precedence order,
-    // we want them in decreasing order here.
-    for block in applicable_declarations.iter().rev() {
-        for declaration in block.iter().rev() {
-            match *declaration {
-                % for style_struct in data.active_style_structs():
-                    % for property in style_struct.longhands:
-                        % if not property.derived_from:
-                            PropertyDeclaration::${property.camel_case}(ref
-                                    ${'_' if not style_struct.inherited else ''}declared_value)
-                                    => {
-                                % if style_struct.inherited:
-                                    if seen.get_${property.ident}() {
-                                        continue
-                                    }
-                                    seen.set_${property.ident}();
-                                    let custom_props = context.style().custom_properties();
-                                    substitute_variables_${property.ident}(
-                                        declared_value, &custom_props,
-                                    |value| {
-                                        if let Some(ref mut cascade_info) = cascade_info {
-                                            cascade_info.on_cascade_property(&declaration,
-                                                                             &value);
-                                        }
-                                        match *value {
-                                            DeclaredValue::Value(ref specified_value)
-                                            => {
-                                                let computed = specified_value.to_computed_value(&context);
-                                                context.mutate_style().mutate_${style_struct.name_lower}()
-                                                       .set_${property.ident}(computed);
-                                            },
-                                            DeclaredValue::Initial
-                                            => {
-                                                // FIXME(bholley): We may want set_X_to_initial_value() here.
-                                                let initial = longhands::${property.ident}::get_initial_value();
-                                                context.mutate_style().mutate_${style_struct.name_lower}()
-                                                       .set_${property.ident}(initial);
-                                            },
-                                            DeclaredValue::Inherit => {
-                                                // This is a bit slow, but this is rare so it shouldn't
-                                                // matter.
-                                                //
-                                                // FIXME: is it still?
-                                                let inherited_struct = parent_style.get_${style_struct.ident}();
-                                                context.mutate_style().mutate_${style_struct.name_lower}()
-                                                       .copy_${property.ident}_from(inherited_struct);
-                                            }
-                                            DeclaredValue::WithVariables { .. } => unreachable!()
-                                        }
-                                    }, &mut error_reporter);
-                                % endif
-
-                                % if property.name in data.derived_longhands:
-                                    % for derived in data.derived_longhands[property.name]:
-                                            longhands::${derived.ident}
-                                                     ::derive_from_${property.ident}(&mut context);
-                                    % endfor
-                                % endif
-                            }
-                        % else:
-                            PropertyDeclaration::${property.camel_case}(_) => {
-                                // Do not allow stylesheets to set derived properties.
-                            }
-                        % endif
-                    % endfor
-                % endfor
-                PropertyDeclaration::Custom(..) => {}
-            }
-        }
-    }
-
-    if seen.get_font_style() || seen.get_font_weight() || seen.get_font_stretch() ||
-            seen.get_font_family() {
-        context.mutate_style().mutate_font().compute_font_hash();
-    }
-
-    let mode = get_writing_mode(context.style.get_inheritedbox());
-    context.style.set_writing_mode(mode);
-
-    context.style
-}
-
 pub type CascadePropertyFn =
     extern "Rust" fn(declaration: &PropertyDeclaration,
                      inherited_style: &ComputedValues,
@@ -1523,71 +1409,71 @@ bitflags! {
     }
 }
 
-/// Performs the CSS cascade, computing new styles for an element from its parent style and
-/// optionally a cached related style. The arguments are:
+/// Performs the CSS cascade, computing new styles for an element from its parent style.
+///
+/// The arguments are:
 ///
 ///   * `viewport_size`: The size of the initial viewport.
 ///
-///   * `applicable_declarations`: The list of CSS rules that matched.
+///   * `rule_node`: The rule node in the tree that represent the CSS rules that
+///   matched.
 ///
 ///   * `parent_style`: The parent style, if applicable; if `None`, this is the root node.
 ///
-///   * `cached_style`: If present, cascading is short-circuited for everything but inherited
-///     values and these values are used instead. Obviously, you must be careful when supplying
-///     this that it is safe to only provide inherited declarations. If `parent_style` is `None`,
-///     this is ignored.
-///
+/// Returns the computed values.
 ///   * `flags`: Various flags.
 ///
-/// Returns the computed values and a boolean indicating whether the result is cacheable.
 pub fn cascade(viewport_size: Size2D<Au>,
-               applicable_declarations: &[ApplicableDeclarationBlock],
+               rule_node: &StrongRuleNode,
                parent_style: Option<<&ComputedValues>,
-               cached_style: Option<<&ComputedValues>,
-               mut cascade_info: Option<<&mut CascadeInfo>,
-               mut error_reporter: StdBox<ParseErrorReporter + Send>,
+               cascade_info: Option<<&mut CascadeInfo>,
+               error_reporter: StdBox<ParseErrorReporter + Send>,
                flags: CascadeFlags)
-               -> (ComputedValues, bool) {
-    let initial_values = ComputedValues::initial_values();
+               -> ComputedValues {
     let (is_root_element, inherited_style) = match parent_style {
         Some(parent_style) => (false, parent_style),
-        None => (true, initial_values),
+        None => (true, ComputedValues::initial_values()),
     };
+    apply_declarations(viewport_size,
+                       is_root_element,
+                       rule_node.iter_declarations(),
+                       inherited_style,
+                       cascade_info,
+                       error_reporter,
+                       flags)
+}
 
-    // Aquire locks for at least the lifetime of `specified_custom_properties`.
-    let applicable_declarations = applicable_declarations.iter()
-        .map(|block| block.read())
-        .collect::<Vec<_>>();
-
+/// NOTE: This function expects the declaration with more priority to appear
+/// first.
+pub fn apply_declarations<'a, I>(viewport_size: Size2D<Au>,
+                                 is_root_element: bool,
+                                 declarations_iter: I,
+                                 inherited_style: &ComputedValues,
+                                 mut cascade_info: Option<<&mut CascadeInfo>,
+                                 mut error_reporter: StdBox<ParseErrorReporter + Send>,
+                                 flags: CascadeFlags)
+                                 -> ComputedValues
+    where I: Iterator<Item = &'a PropertyDeclaration> + Clone
+{
     let inherited_custom_properties = inherited_style.custom_properties();
-    let mut specified_custom_properties = None;
+    let mut custom_properties = None;
     let mut seen_custom = HashSet::new();
-    for block in applicable_declarations.iter().rev() {
-        for declaration in block.iter().rev() {
-            match *declaration {
-                PropertyDeclaration::Custom(ref name, ref value) => {
-                    ::custom_properties::cascade(
-                        &mut specified_custom_properties, &inherited_custom_properties,
-                        &mut seen_custom, name, value)
-                }
-                _ => {}
+    for declaration in declarations_iter.clone() {
+        match *declaration {
+            PropertyDeclaration::Custom(ref name, ref value) => {
+                ::custom_properties::cascade(
+                    &mut custom_properties, &inherited_custom_properties,
+                    &mut seen_custom, name, value)
             }
+            _ => {}
         }
     }
-    let custom_properties = ::custom_properties::finish_cascade(
-            specified_custom_properties, &inherited_custom_properties);
 
-    if let (Some(cached_style), Some(parent_style)) = (cached_style, parent_style) {
-        let style = cascade_with_cached_declarations(viewport_size,
-                                                     &applicable_declarations,
-                                                     flags.contains(SHAREABLE),
-                                                     parent_style,
-                                                     cached_style,
-                                                     custom_properties,
-                                                     cascade_info,
-                                                     error_reporter);
-        return (style, false)
-    }
+    let custom_properties =
+        ::custom_properties::finish_cascade(
+            custom_properties, &inherited_custom_properties);
+
+    let initial_values = ComputedValues::initial_values();
 
     let starting_style = if !flags.contains(INHERIT_ALL) {
         ComputedValues::new(custom_properties,
@@ -1620,54 +1506,66 @@ pub fn cascade(viewport_size: Size2D<Au>,
         style: starting_style,
     };
 
-    // Set computed values, overwriting earlier declarations for the same property.
+    // Set computed values, overwriting earlier declarations for the same
+    // property.
     let mut cacheable = true;
     let mut seen = PropertyBitField::new();
-    // Declaration blocks are stored in increasing precedence order, we want them in decreasing
-    // order here.
+
+    // Declaration blocks are stored in increasing precedence order, we want
+    // them in decreasing order here.
     //
-    // We could (and used to) use a pattern match here, but that bloats this function to over 100K
-    // of compiled code! To improve i-cache behavior, we outline the individual functions and use
+    // We could (and used to) use a pattern match here, but that bloats this
+    // function to over 100K of compiled code!
+    //
+    // To improve i-cache behavior, we outline the individual functions and use
     // virtual dispatch instead.
     ComputedValues::do_cascade_property(|cascade_property| {
         % for category_to_cascade_now in ["early", "other"]:
-            for block in applicable_declarations.iter().rev() {
-                for declaration in block.iter().rev() {
-                    if let PropertyDeclaration::Custom(..) = *declaration {
-                        continue
-                    }
-                    // The computed value of some properties depends on the (sometimes computed)
-                    // value of *other* properties.
-                    // So we classify properties into "early" and "other",
-                    // such that the only dependencies can be from "other" to "early".
-                    // We iterate applicable_declarations twice, first cascading "early" properties
-                    // then "other".
-                    // Unfortunately, it’s not easy to check that this classification is correct.
-                    let is_early_property = matches!(*declaration,
-                        PropertyDeclaration::FontSize(_) |
-                        PropertyDeclaration::Color(_) |
-                        PropertyDeclaration::Position(_) |
-                        PropertyDeclaration::Float(_) |
-                        PropertyDeclaration::TextDecoration${'' if product == 'servo' else 'Line'}(_) |
-                        PropertyDeclaration::WritingMode(_)
-                    );
-                    if
-                        % if category_to_cascade_now == "early":
-                            !
-                        % endif
-                        is_early_property
-                    {
-                        continue
-                    }
-                    let discriminant = declaration.discriminant_value();
-                    (cascade_property[discriminant])(declaration,
-                                                     inherited_style,
-                                                     &mut context,
-                                                     &mut seen,
-                                                     &mut cacheable,
-                                                     &mut cascade_info,
-                                                     &mut error_reporter);
+            % if category_to_cascade_now == "early":
+            for declaration in declarations_iter.clone() {
+            % else:
+            for declaration in declarations_iter {
+            % endif
+
+                if let PropertyDeclaration::Custom(..) = *declaration {
+                    continue
+                }
+                // The computed value of some properties depends on the
+                // (sometimes computed) value of *other* properties.
+                //
+                // So we classify properties into "early" and "other", such that
+                // the only dependencies can be from "other" to "early".
+                //
+                // We iterate applicable_declarations twice, first cascading
+                // "early" properties then "other".
+                //
+                // Unfortunately, it’s not easy to check that this
+                // classification is correct.
+                let is_early_property = matches!(*declaration,
+                    PropertyDeclaration::FontSize(_) |
+                    PropertyDeclaration::Color(_) |
+                    PropertyDeclaration::Position(_) |
+                    PropertyDeclaration::Float(_) |
+                    PropertyDeclaration::TextDecoration${'' if product == 'servo' else 'Line'}(_) |
+                    PropertyDeclaration::WritingMode(_)
+                );
+                if
+                    % if category_to_cascade_now == "early":
+                        !
+                    % endif
+                    is_early_property
+                {
+                    continue
                 }
+
+                let discriminant = declaration.discriminant_value();
+                (cascade_property[discriminant])(declaration,
+                                                 inherited_style,
+                                                 &mut context,
+                                                 &mut seen,
+                                                 &mut cacheable,
+                                                 &mut cascade_info,
+                                                 &mut error_reporter);
             }
         % endfor
     });
@@ -1753,6 +1651,7 @@ pub fn cascade(viewport_size: Size2D<Au>,
         }
     % endfor
 
+
     % if product == "gecko":
         style.mutate_background().fill_arrays();
         style.mutate_svg().fill_arrays();
@@ -1776,7 +1675,7 @@ pub fn cascade(viewport_size: Size2D<Au>,
 
     let mode = get_writing_mode(style.get_inheritedbox());
     style.set_writing_mode(mode);
-    (style, cacheable)
+    style
 }
 
 #[cfg(feature = "servo")]
@@ -1972,7 +1871,6 @@ pub fn modify_style_for_inline_absolute_hypothetical_fragment(style: &mut Arc<Co
     }
 }
 
-
 // FIXME: https://github.com/w3c/csswg-drafts/issues/580
 pub fn is_supported_property(property: &str) -> bool {
     match_ignore_ascii_case! { property,
diff --git a/components/style/rule_tree/mod.rs b/components/style/rule_tree/mod.rs
new file mode 100644
index 00000000000..02e539f8019
--- /dev/null
+++ b/components/style/rule_tree/mod.rs
@@ -0,0 +1,642 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#![allow(unsafe_code)]
+
+use arc_ptr_eq;
+#[cfg(feature = "servo")]
+use heapsize::HeapSizeOf;
+use owning_handle::OwningHandle;
+use owning_ref::{ArcRef, OwningRef};
+use parking_lot::{RwLock, RwLockReadGuard};
+use properties::{Importance, PropertyDeclaration, PropertyDeclarationBlock};
+use std::io::{self, Write};
+use std::ptr;
+use std::sync::Arc;
+use std::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
+use stylesheets::StyleRule;
+use thread_state;
+
+#[derive(Debug)]
+#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
+pub struct RuleTree {
+    root: StrongRuleNode,
+}
+
+#[derive(Debug, Clone)]
+pub enum StyleSource {
+    Style(Arc<RwLock<StyleRule>>),
+    Declarations(Arc<RwLock<PropertyDeclarationBlock>>),
+}
+
+// This is really nasty.
+type StyleSourceGuardHandle<'a> =
+    OwningHandle<
+        OwningHandle<
+            OwningRef<Arc<RwLock<StyleRule>>, RwLock<StyleRule>>,
+            RwLockReadGuard<'a, StyleRule>>,
+        RwLockReadGuard<'a, PropertyDeclarationBlock>>;
+
+pub enum StyleSourceGuard<'a> {
+    Style(StyleSourceGuardHandle<'a>),
+    Declarations(RwLockReadGuard<'a, PropertyDeclarationBlock>),
+}
+
+impl<'a> ::std::ops::Deref for StyleSourceGuard<'a> {
+    type Target = PropertyDeclarationBlock;
+
+    fn deref(&self) -> &Self::Target {
+        match *self {
+            StyleSourceGuard::Declarations(ref block) => &*block,
+            StyleSourceGuard::Style(ref handle) => &*handle,
+        }
+    }
+}
+
+impl StyleSource {
+    #[inline]
+    fn ptr_equals(&self, other: &Self) -> bool {
+        use self::StyleSource::*;
+        match (self, other) {
+            (&Style(ref one), &Style(ref other)) => arc_ptr_eq(one, other),
+            (&Declarations(ref one), &Declarations(ref other)) => arc_ptr_eq(one, other),
+            _ => false,
+        }
+    }
+
+    fn dump<W: Write>(&self, writer: &mut W) {
+        use self::StyleSource::*;
+
+        if let Style(ref rule) = *self {
+            let _ = write!(writer, "{:?}", rule.read().selectors);
+        }
+
+        let _ = write!(writer, "  -> {:?}", self.read().declarations);
+    }
+
+    #[inline]
+    pub fn read<'a>(&'a self) -> StyleSourceGuard<'a> {
+        use self::StyleSource::*;
+        match *self {
+            Style(ref rule) => {
+                let arc_ref = ArcRef::new(rule.clone());
+                let rule_owning_ref =
+                    OwningHandle::new(arc_ref, |r| unsafe { &*r }.read());
+                let block_owning_ref =
+                    OwningHandle::new(rule_owning_ref, |r| unsafe { &*r }.block.read());
+
+                StyleSourceGuard::Style(block_owning_ref)
+            }
+            Declarations(ref block) => StyleSourceGuard::Declarations(block.read()),
+        }
+    }
+}
+
+/// This value exists here so a node that pushes itself to the list can know
+/// that is in the free list by looking at is next pointer, and comparing it
+/// with null.
+const FREE_LIST_SENTINEL: *mut RuleNode = 0x01 as *mut RuleNode;
+
+impl RuleTree {
+    pub fn new() -> Self {
+        RuleTree {
+            root: StrongRuleNode::new(Box::new(RuleNode::root())),
+        }
+    }
+
+    pub fn root(&self) -> StrongRuleNode {
+        self.root.clone()
+    }
+
+    fn dump<W: Write>(&self, writer: &mut W) {
+        let _ = writeln!(writer, " + RuleTree");
+        self.root.get().dump(writer, 0);
+    }
+
+    pub fn dump_stdout(&self) {
+        let mut stdout = io::stdout();
+        self.dump(&mut stdout);
+    }
+
+    pub fn insert_ordered_rules<'a, I>(&self, iter: I) -> StrongRuleNode
+        where I: Iterator<Item=(StyleSource, Importance)>
+    {
+        let mut current = self.root.clone();
+        for (source, importance) in iter {
+            current = current.ensure_child(self.root.downgrade(), source, importance);
+        }
+        current
+    }
+
+    pub unsafe fn gc(&self) {
+        self.root.gc();
+    }
+}
+
+struct RuleNode {
+    /// The root node. Only the root has no root pointer, for obvious reasons.
+    root: Option<WeakRuleNode>,
+
+    /// The parent rule node. Only the root has no parent.
+    parent: Option<StrongRuleNode>,
+
+    /// The actual style source, either coming from a selector in a StyleRule,
+    /// or a raw property declaration block (like the style attribute).
+    source: Option<StyleSource>,
+
+    /// The importance of the declarations relevant in the style rule,
+    /// meaningless in the root node.
+    importance: Importance,
+
+    children: RuleChildrenList,
+    refcount: AtomicUsize,
+    next: AtomicPtr<RuleNode>,
+    prev: AtomicPtr<RuleNode>,
+
+    /// The next item in the rule tree free list, that starts on the root node.
+    next_free: AtomicPtr<RuleNode>,
+}
+
+unsafe impl Sync for RuleTree {}
+unsafe impl Send for RuleTree {}
+
+impl RuleNode {
+    fn new(root: WeakRuleNode,
+           parent: StrongRuleNode,
+           source: StyleSource,
+           importance: Importance) -> Self {
+        debug_assert!(root.upgrade().parent().is_none());
+        RuleNode {
+            root: Some(root),
+            parent: Some(parent),
+            source: Some(source),
+            importance: importance,
+            children: RuleChildrenList::new(),
+            refcount: AtomicUsize::new(1),
+            next: AtomicPtr::new(ptr::null_mut()),
+            prev: AtomicPtr::new(ptr::null_mut()),
+            next_free: AtomicPtr::new(ptr::null_mut()),
+        }
+    }
+
+    fn root() -> Self {
+        RuleNode {
+            root: None,
+            parent: None,
+            source: None,
+            importance: Importance::Normal,
+            children: RuleChildrenList::new(),
+            refcount: AtomicUsize::new(1),
+            next: AtomicPtr::new(ptr::null_mut()),
+            prev: AtomicPtr::new(ptr::null_mut()),
+            next_free: AtomicPtr::new(FREE_LIST_SENTINEL),
+        }
+    }
+
+    fn is_root(&self) -> bool {
+        self.parent.is_none()
+    }
+
+    /// Remove this rule node from the child list.
+    ///
+    /// This method doesn't use proper synchronization, and it's expected to be
+    /// called in a single-threaded fashion, thus the unsafety.
+    ///
+    /// This is expected to be called before freeing the node from the free
+    /// list.
+    unsafe fn remove_from_child_list(&self) {
+        debug!("Remove from child list: {:?}, parent: {:?}",
+               self as *const RuleNode, self.parent.as_ref().map(|p| p.ptr()));
+        let previous = self.prev.swap(ptr::null_mut(), Ordering::SeqCst);
+        let next = self.next.swap(ptr::null_mut(), Ordering::SeqCst);
+
+        if previous != ptr::null_mut() {
+            let really_previous = WeakRuleNode { ptr: previous };
+            really_previous.upgrade()
+                .get().next.store(next, Ordering::SeqCst);
+        } else {
+            self.parent.as_ref().unwrap()
+                .get().children.head.store(ptr::null_mut(), Ordering::SeqCst);
+        }
+
+        if next != ptr::null_mut() {
+            let really_next = WeakRuleNode { ptr: next };
+            really_next.upgrade().get().prev.store(previous, Ordering::SeqCst);
+        }
+    }
+
+    fn dump<W: Write>(&self, writer: &mut W, indent: usize) {
+        const INDENT_INCREMENT: usize = 4;
+
+        for _ in 0..indent {
+            let _ = write!(writer, " ");
+        }
+
+        let _ = writeln!(writer, " - {:?} (ref: {:?}, parent: {:?})",
+                         self as *const _, self.refcount.load(Ordering::SeqCst),
+                         self.parent.as_ref().map(|p| p.ptr()));
+
+        for _ in 0..indent {
+            let _ = write!(writer, " ");
+        }
+
+        match self.source {
+            Some(ref source) => {
+                source.dump(writer);
+            }
+            None => {
+                if indent != 0 {
+                    error!("How has this happened?");
+                }
+                let _ = write!(writer, "(root)");
+            }
+        }
+
+        let _ = write!(writer, "\n");
+        for child in self.children.iter() {
+            child.get().dump(writer, indent + INDENT_INCREMENT);
+        }
+    }
+}
+
+#[derive(Clone)]
+struct WeakRuleNode {
+    ptr: *mut RuleNode,
+}
+
+#[derive(Debug)]
+pub struct StrongRuleNode {
+    ptr: *mut RuleNode,
+}
+
+#[cfg(feature = "servo")]
+impl HeapSizeOf for StrongRuleNode {
+    fn heap_size_of_children(&self) -> usize { 0 }
+}
+
+
+impl StrongRuleNode {
+    fn new(n: Box<RuleNode>) -> Self {
+        debug_assert!(n.parent.is_none() == n.source.is_none());
+
+        let ptr = Box::into_raw(n);
+
+        debug!("Creating rule node: {:p}", ptr);
+
+        StrongRuleNode {
+            ptr: ptr,
+        }
+    }
+
+    fn downgrade(&self) -> WeakRuleNode {
+        WeakRuleNode {
+            ptr: self.ptr,
+        }
+    }
+
+    fn next(&self) -> Option<WeakRuleNode> {
+        // FIXME(emilio): Investigate what ordering can we achieve without
+        // messing things up.
+        let ptr = self.get().next.load(Ordering::SeqCst);
+        if ptr.is_null() {
+            None
+        } else {
+            Some(WeakRuleNode {
+                ptr: ptr
+            })
+        }
+    }
+
+    fn parent(&self) -> Option<&StrongRuleNode> {
+        self.get().parent.as_ref()
+    }
+
+    fn ensure_child(&self,
+                    root: WeakRuleNode,
+                    source: StyleSource,
+                    importance: Importance) -> StrongRuleNode {
+        let mut last = None;
+        for child in self.get().children.iter() {
+            if child .get().importance == importance &&
+                child.get().source.as_ref().unwrap().ptr_equals(&source) {
+                return child;
+            }
+            last = Some(child);
+        }
+
+        let node = Box::new(RuleNode::new(root.clone(),
+                                          self.clone(),
+                                          source.clone(),
+                                          importance));
+        let new_ptr = &*node as *const _ as *mut RuleNode;
+
+        loop {
+            let strong;
+
+            {
+                let next_ptr = match last {
+                    Some(ref l) => &l.get().next,
+                    None => &self.get().children.head,
+                };
+
+                let existing =
+                    next_ptr.compare_and_swap(ptr::null_mut(),
+                                              new_ptr,
+                                              Ordering::SeqCst);
+
+                if existing == ptr::null_mut() {
+                    // Now we know we're in the correct position in the child list,
+                    // we can set the back pointer, knowing that this will only be
+                    // accessed again in a single-threaded manner when we're
+                    // sweeping possibly dead nodes.
+                    if let Some(ref l) = last {
+                        node.prev.store(l.ptr(), Ordering::Relaxed);
+                    }
+
+                    return StrongRuleNode::new(node);
+                }
+
+                strong = WeakRuleNode { ptr: existing }.upgrade();
+
+                if strong.get().source.as_ref().unwrap().ptr_equals(&source) {
+                    // Some thread that was racing with as inserted the same rule
+                    // node than us, so give up and just use that.
+                    return strong;
+                }
+            }
+
+            last = Some(strong);
+        }
+    }
+
+    fn ptr(&self) -> *mut RuleNode {
+        self.ptr
+    }
+
+    fn get(&self) -> &RuleNode {
+        if cfg!(debug_assertions) {
+            let node = unsafe { &*self.ptr };
+            assert!(node.refcount.load(Ordering::SeqCst) > 0);
+        }
+        unsafe { &*self.ptr }
+    }
+
+    pub fn iter_declarations<'a>(&'a self) -> RuleTreeDeclarationsIterator<'a> {
+        RuleTreeDeclarationsIterator {
+            current: match self.get().source.as_ref() {
+                Some(ref source) => Some((self, source.read())),
+                None => None,
+            },
+            index: 0,
+        }
+    }
+
+    unsafe fn pop_from_free_list(&self) -> Option<WeakRuleNode> {
+        debug_assert!(thread_state::get().is_layout() &&
+                      !thread_state::get().is_worker());
+
+        let me = &*self.ptr;
+        debug_assert!(me.is_root());
+
+        let current = self.get().next_free.load(Ordering::SeqCst);
+        if current == FREE_LIST_SENTINEL {
+            return None;
+        }
+
+        let current = WeakRuleNode { ptr: current };
+
+        let node = &*current.ptr();
+        let next = node.next_free.swap(ptr::null_mut(), Ordering::SeqCst);
+        me.next_free.store(next, Ordering::SeqCst);
+
+        debug!("Popping from free list: cur: {:?}, next: {:?}", current.ptr(), next);
+
+        Some(current)
+    }
+
+    unsafe fn gc(&self) {
+        // NB: This can run from the root node destructor, so we can't use
+        // `get()`, since it asserts the refcount is bigger than zero.
+        let me = &*self.ptr;
+
+        debug_assert!(me.is_root(), "Can't call GC on a non-root node!");
+
+        while let Some(weak) = self.pop_from_free_list() {
+            let needs_drop = {
+                let node = &*weak.ptr();
+                if node.refcount.load(Ordering::SeqCst) == 0 {
+                    node.remove_from_child_list();
+                    true
+                } else {
+                    false
+                }
+            };
+
+            debug!("GC'ing {:?}: {}", weak.ptr(), needs_drop);
+            if needs_drop {
+                let _ = Box::from_raw(weak.ptr());
+            }
+        }
+
+        debug_assert!(me.next_free.load(Ordering::SeqCst) == FREE_LIST_SENTINEL);
+    }
+}
+
+pub struct RuleTreeDeclarationsIterator<'a> {
+    current: Option<(&'a StrongRuleNode, StyleSourceGuard<'a>)>,
+    index: usize,
+}
+
+impl<'a> Clone for RuleTreeDeclarationsIterator<'a> {
+    fn clone(&self) -> Self {
+        RuleTreeDeclarationsIterator {
+            current: self.current.as_ref().map(|&(node, _)| {
+                (&*node, node.get().source.as_ref().unwrap().read())
+            }),
+            index: self.index,
+        }
+    }
+}
+
+impl<'a> Iterator for RuleTreeDeclarationsIterator<'a> {
+    type Item = &'a PropertyDeclaration;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let (node, guard) = match self.current.take() {
+            Some(node_and_guard) => node_and_guard,
+            None => return None,
+        };
+
+        let declaration_count = guard.declarations.len();
+
+        if self.index == declaration_count {
+            let parent = node.parent().unwrap();
+            let guard = match parent.get().source {
+                Some(ref source) => source.read(),
+                None => {
+                    debug_assert!(parent.parent().is_none());
+                    self.current = None;
+                    return None;
+                }
+            };
+
+            self.current = Some((parent, guard));
+            self.index = 0;
+            // FIXME: Make this a loop and use continue, the borrow checker
+            // isn't too happy about it for some reason.
+            return self.next();
+        }
+
+        let (decl, importance) = {
+            let (ref decl, importance) =
+                guard.declarations[declaration_count - self.index - 1];
+
+            // FIXME: The borrow checker is not smart enough to see that the
+            // guard is moved below and that affects the lifetime of `decl`,
+            // plus `decl` has a stable address (because it's in an Arc), so we
+            // need to transmute here.
+            let decl: &'a PropertyDeclaration = unsafe { ::std::mem::transmute(decl) };
+
+            (decl, importance)
+        };
+
+        self.current = Some((node, guard));
+        self.index += 1;
+        if importance == node.get().importance {
+            return Some(decl);
+        }
+        // FIXME: Same as above, this is crap...
+        return self.next();
+    }
+}
+
+impl Clone for StrongRuleNode {
+    fn clone(&self) -> Self {
+        debug!("{:?}: {:?}+", self.ptr(), self.get().refcount.load(Ordering::SeqCst));
+        debug_assert!(self.get().refcount.load(Ordering::SeqCst) > 0);
+        self.get().refcount.fetch_add(1, Ordering::SeqCst);
+        StrongRuleNode {
+            ptr: self.ptr,
+        }
+    }
+}
+
+impl Drop for StrongRuleNode {
+    fn drop(&mut self) {
+        let node = unsafe { &*self.ptr };
+
+        debug!("{:?}: {:?}-", self.ptr(), node.refcount.load(Ordering::SeqCst));
+        debug!("Dropping node: {:?}, root: {:?}, parent: {:?}",
+               self.ptr,
+               node.root.as_ref().map(|r| r.ptr()),
+               node.parent.as_ref().map(|p| p.ptr()));
+        let should_drop = {
+            debug_assert!(node.refcount.load(Ordering::SeqCst) > 0);
+            node.refcount.fetch_sub(1, Ordering::SeqCst) == 1
+        };
+
+        if should_drop {
+            debug_assert_eq!(node.children.head.load(Ordering::SeqCst),
+                             ptr::null_mut());
+            if node.parent.is_none() {
+                debug!("Dropping root node!");
+                // NOTE: Calling this is fine, because the rule tree root
+                // destructor needs to happen from the layout thread, where the
+                // stylist, and hence, the rule tree, is held.
+                unsafe { self.gc() };
+                let _ = unsafe { Box::from_raw(self.ptr()) };
+                return;
+            }
+
+            // The node is already in the free list, so do nothing.
+            if node.next_free.load(Ordering::SeqCst) != ptr::null_mut() {
+                return;
+            }
+
+            let free_list =
+                &unsafe { &*node.root.as_ref().unwrap().ptr() }.next_free;
+            loop {
+                let next_free = free_list.load(Ordering::SeqCst);
+                debug_assert!(!next_free.is_null());
+
+                node.next_free.store(next_free, Ordering::SeqCst);
+
+                let existing =
+                    free_list.compare_and_swap(next_free,
+                                               self.ptr(),
+                                               Ordering::SeqCst);
+                if existing == next_free {
+                    // Successfully inserted, yay! Otherwise try again.
+                    break;
+                }
+            }
+        }
+    }
+}
+
+impl<'a> From<&'a StrongRuleNode> for WeakRuleNode {
+    fn from(node: &'a StrongRuleNode) -> Self {
+        WeakRuleNode {
+            ptr: node.ptr(),
+        }
+    }
+}
+
+impl WeakRuleNode {
+    fn upgrade(&self) -> StrongRuleNode {
+        debug!("Upgrading weak node: {:p}", self.ptr());
+
+        let node = unsafe { &*self.ptr };
+        node.refcount.fetch_add(1, Ordering::SeqCst);
+        StrongRuleNode {
+            ptr: self.ptr,
+        }
+    }
+
+    fn ptr(&self) -> *mut RuleNode {
+        self.ptr
+    }
+}
+
+struct RuleChildrenList {
+    head: AtomicPtr<RuleNode>,
+}
+
+impl RuleChildrenList {
+    fn new() -> Self {
+        RuleChildrenList {
+            head: AtomicPtr::new(ptr::null_mut())
+        }
+    }
+
+    fn iter(&self) -> RuleChildrenListIter {
+        // FIXME(emilio): Fiddle with memory orderings.
+        let head = self.head.load(Ordering::SeqCst);
+        RuleChildrenListIter {
+            current: if head.is_null() {
+                None
+            } else {
+                Some(WeakRuleNode {
+                    ptr: head,
+                })
+            },
+        }
+    }
+}
+
+struct RuleChildrenListIter {
+    current: Option<WeakRuleNode>,
+}
+
+impl Iterator for RuleChildrenListIter {
+    type Item = StrongRuleNode;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.current.take().map(|current| {
+            let current = current.upgrade();
+            self.current = current.next();
+            current
+        })
+    }
+}
diff --git a/components/style/selector_matching.rs b/components/style/selector_matching.rs
index b97fcf9bb68..1a0a07b32e4 100644
--- a/components/style/selector_matching.rs
+++ b/components/style/selector_matching.rs
@@ -10,11 +10,12 @@ use element_state::*;
 use error_reporting::StdoutErrorReporter;
 use keyframes::KeyframesAnimation;
 use media_queries::{Device, MediaType};
-use parking_lot::{RwLock, RwLockReadGuard};
+use parking_lot::RwLock;
 use properties::{self, CascadeFlags, ComputedValues, INHERIT_ALL, Importance};
 use properties::{PropertyDeclaration, PropertyDeclarationBlock};
 use quickersort::sort_by;
 use restyle_hints::{RestyleHint, DependencySet};
+use rule_tree::{RuleTree, StrongRuleNode, StyleSource};
 use selector_impl::{ElementExt, TheSelectorImpl, PseudoElement};
 use selectors::Element;
 use selectors::bloom::BloomFilter;
@@ -31,7 +32,7 @@ use std::hash::Hash;
 use std::slice;
 use std::sync::Arc;
 use style_traits::viewport::ViewportConstraints;
-use stylesheets::{CSSRule, Origin, Stylesheet, UserAgentStylesheets};
+use stylesheets::{CSSRule, Origin, StyleRule, Stylesheet, UserAgentStylesheets};
 use viewport::{self, MaybeNew, ViewportRule};
 
 pub type FnvHashMap<K, V> = HashMap<K, V, BuildHasherDefault<::fnv::FnvHasher>>;
@@ -62,6 +63,11 @@ pub struct Stylist {
     /// rules against the current device.
     element_map: PerPseudoElementSelectorMap,
 
+    /// The rule tree, that stores the results of selector matching.
+    ///
+    /// FIXME(emilio): Not `pub`!
+    pub rule_tree: RuleTree,
+
     /// The selector maps corresponding to a given pseudo-element
     /// (depending on the implementation)
     pseudos_map: FnvHashMap<PseudoElement, PerPseudoElementSelectorMap>,
@@ -72,6 +78,8 @@ pub struct Stylist {
     /// Applicable declarations for a given non-eagerly cascaded pseudo-element.
     /// These are eagerly computed once, and then used to resolve the new
     /// computed values on the fly on layout.
+    ///
+    /// FIXME(emilio): Use the rule tree!
     precomputed_pseudo_element_decls: FnvHashMap<PseudoElement, Vec<ApplicableDeclarationBlock>>,
 
     rules_source_order: usize,
@@ -103,6 +111,7 @@ impl Stylist {
             animations: Default::default(),
             precomputed_pseudo_element_decls: Default::default(),
             rules_source_order: 0,
+            rule_tree: RuleTree::new(),
             state_deps: DependencySet::new(),
 
             // XXX remember resetting them!
@@ -179,8 +188,8 @@ impl Stylist {
         stylesheet.effective_rules(&self.device, |rule| {
             match *rule {
                 CSSRule::Style(ref style_rule) => {
-                    let style_rule = style_rule.read();
-                    for selector in &style_rule.selectors {
+                    let guard = style_rule.read();
+                    for selector in &guard.selectors {
                         let map = if let Some(ref pseudo) = selector.pseudo_element {
                             pseudos_map
                                 .entry(pseudo.clone())
@@ -192,14 +201,14 @@ impl Stylist {
 
                         map.insert(Rule {
                             selector: selector.complex_selector.clone(),
-                            declarations: style_rule.block.clone(),
+                            style_rule: style_rule.clone(),
                             specificity: selector.specificity,
                             source_order: *rules_source_order,
                         });
                     }
                     *rules_source_order += 1;
 
-                    for selector in &style_rule.selectors {
+                    for selector in &guard.selectors {
                         state_deps.note_selector(&selector.complex_selector);
                         if selector.affects_siblings() {
                             sibling_affecting_selectors.push(selector.clone());
@@ -261,25 +270,30 @@ impl Stylist {
                                          pseudo: &PseudoElement,
                                          parent: Option<&Arc<ComputedValues>>,
                                          inherit_all: bool)
-                                         -> Option<Arc<ComputedValues>> {
+                                         -> Option<(Arc<ComputedValues>, StrongRuleNode)> {
         debug_assert!(TheSelectorImpl::pseudo_element_cascade_type(pseudo).is_precomputed());
         if let Some(declarations) = self.precomputed_pseudo_element_decls.get(pseudo) {
+            // FIXME(emilio): When we've taken rid of the cascade we can just
+            // use into_iter.
+            let rule_node =
+                self.rule_tree.insert_ordered_rules(
+                    declarations.iter().map(|a| (a.source.clone(), a.importance)));
+
             let mut flags = CascadeFlags::empty();
             if inherit_all {
                 flags.insert(INHERIT_ALL)
             }
 
-            let (computed, _) =
+            let computed =
                 properties::cascade(self.device.au_viewport_size(),
-                                    &declarations,
+                                    &rule_node,
                                     parent.map(|p| &**p),
                                     None,
-                                    None,
                                     Box::new(StdoutErrorReporter),
                                     flags);
-            Some(Arc::new(computed))
+            Some((Arc::new(computed), rule_node))
         } else {
-            parent.map(|p| p.clone())
+            parent.map(|p| (p.clone(), self.rule_tree.root()))
         }
     }
 
@@ -308,13 +322,14 @@ impl Stylist {
         };
         self.precomputed_values_for_pseudo(&pseudo, Some(parent_style), inherit_all)
             .expect("style_for_anonymous_box(): No precomputed values for that pseudo!")
+            .0
     }
 
     pub fn lazily_compute_pseudo_element_style<E>(&self,
                                                   element: &E,
                                                   pseudo: &PseudoElement,
                                                   parent: &Arc<ComputedValues>)
-                                                  -> Option<Arc<ComputedValues>>
+                                                  -> Option<(Arc<ComputedValues>, StrongRuleNode)>
         where E: Element<Impl=TheSelectorImpl> +
               fmt::Debug +
               PresentationalHintsSynthetizer
@@ -326,8 +341,6 @@ impl Stylist {
 
         let mut declarations = vec![];
 
-        // NB: This being cached could be worth it, maybe allow an optional
-        // ApplicableDeclarationsCache?.
         self.push_applicable_declarations(element,
                                           None,
                                           None,
@@ -335,16 +348,18 @@ impl Stylist {
                                           &mut declarations,
                                           MatchingReason::ForStyling);
 
-        let (computed, _) =
+        let rule_node =
+            self.rule_tree.insert_ordered_rules(declarations.into_iter().map(|a| (a.source.clone(), a.importance)));
+
+        let computed =
             properties::cascade(self.device.au_viewport_size(),
-                                &declarations,
+                                &rule_node,
                                 Some(&**parent),
                                 None,
-                                None,
                                 Box::new(StdoutErrorReporter),
                                 CascadeFlags::empty());
 
-        Some(Arc::new(computed))
+        Some((Arc::new(computed), rule_node))
     }
 
     pub fn set_device(&mut self, mut device: Device, stylesheets: &[Arc<Stylesheet>]) {
@@ -408,9 +423,9 @@ impl Stylist {
                  PresentationalHintsSynthetizer,
               V: Push<ApplicableDeclarationBlock> + VecLike<ApplicableDeclarationBlock>
     {
-        assert!(!self.is_device_dirty);
-        assert!(style_attribute.is_none() || pseudo_element.is_none(),
-                "Style attributes do not apply to pseudo-elements");
+        debug_assert!(!self.is_device_dirty);
+        debug_assert!(style_attribute.is_none() || pseudo_element.is_none(),
+                      "Style attributes do not apply to pseudo-elements");
         debug_assert!(pseudo_element.is_none() ||
                       !TheSelectorImpl::pseudo_element_cascade_type(pseudo_element.as_ref().unwrap())
                         .is_precomputed());
@@ -557,6 +572,11 @@ impl Stylist {
         true
     }
 
+    #[inline]
+    pub fn rule_tree_root(&self) -> StrongRuleNode {
+        self.rule_tree.root()
+    }
+
     pub fn match_same_sibling_affecting_rules<E>(&self,
                                                  element: &E,
                                                  candidate: &E) -> bool
@@ -754,7 +774,7 @@ impl SelectorMap {
 
         // Sort only the rules we just added.
         sort_by_key(&mut matching_rules_list[init_len..],
-                    |rule| (rule.specificity, rule.source_order));
+                    |block| (block.specificity, block.source_order));
     }
 
     /// Append to `rule_list` all universal Rules (rules with selector `*|*`) in
@@ -773,7 +793,8 @@ impl SelectorMap {
         for rule in self.other_rules.iter() {
             if rule.selector.compound_selector.is_empty() &&
                rule.selector.next.is_none() {
-                let block = rule.declarations.read();
+                let guard = rule.style_rule.read();
+                let block = guard.block.read();
                 if block.any_normal() {
                     matching_rules_list.push(
                         rule.to_applicable_declaration_block(Importance::Normal));
@@ -786,7 +807,7 @@ impl SelectorMap {
         }
 
         sort_by_key(&mut matching_rules_list[init_len..],
-                    |rule| (rule.specificity, rule.source_order));
+                    |block| (block.specificity, block.source_order));
     }
 
     fn get_matching_rules_from_hash<E, Str, BorrowedStr: ?Sized, Vector>(
@@ -827,7 +848,8 @@ impl SelectorMap {
               V: VecLike<ApplicableDeclarationBlock>
     {
         for rule in rules.iter() {
-            let block = rule.declarations.read();
+            let guard = rule.style_rule.read();
+            let block = guard.block.read();
             let any_declaration_for_importance = if importance.important() {
                 block.any_important()
             } else {
@@ -836,7 +858,8 @@ impl SelectorMap {
             if any_declaration_for_importance &&
                matches_complex_selector(&*rule.selector, element, parent_bf,
                                         relations, reason) {
-                matching_rules.push(rule.to_applicable_declaration_block(importance));
+                matching_rules.push(
+                    rule.to_applicable_declaration_block(importance));
             }
         }
     }
@@ -907,7 +930,7 @@ impl SelectorMap {
 }
 
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
-#[derive(Clone)]
+#[derive(Clone, Debug)]
 pub struct Rule {
     // This is an Arc because Rule will essentially be cloned for every element
     // that it matches. Selector contains an owned vector (through
@@ -915,16 +938,15 @@ pub struct Rule {
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
     pub selector: Arc<ComplexSelector<TheSelectorImpl>>,
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
-    pub declarations: Arc<RwLock<PropertyDeclarationBlock>>,
+    pub style_rule: Arc<RwLock<StyleRule>>,
     pub source_order: usize,
     pub specificity: u32,
 }
 
 impl Rule {
-    fn to_applicable_declaration_block(&self, importance: Importance)
-                                       -> ApplicableDeclarationBlock {
+    fn to_applicable_declaration_block(&self, importance: Importance) -> ApplicableDeclarationBlock {
         ApplicableDeclarationBlock {
-            mixed_declarations: self.declarations.clone(),
+            source: StyleSource::Style(self.style_rule.clone()),
             importance: importance,
             source_order: self.source_order,
             specificity: self.specificity,
@@ -937,10 +959,8 @@ impl Rule {
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 #[derive(Debug, Clone)]
 pub struct ApplicableDeclarationBlock {
-    /// Contains declarations of either importance, but only those of self.importance are relevant.
-    /// Use ApplicableDeclarationBlock::iter
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
-    pub mixed_declarations: Arc<RwLock<PropertyDeclarationBlock>>,
+    pub source: StyleSource,
     pub importance: Importance,
     pub source_order: usize,
     pub specificity: u32,
@@ -952,32 +972,10 @@ impl ApplicableDeclarationBlock {
                              importance: Importance)
                              -> Self {
         ApplicableDeclarationBlock {
-            mixed_declarations: declarations,
-            importance: importance,
+            source: StyleSource::Declarations(declarations),
             source_order: 0,
             specificity: 0,
-        }
-    }
-
-    pub fn read(&self) -> ApplicableDeclarationBlockReadGuard {
-        ApplicableDeclarationBlockReadGuard {
-            guard: self.mixed_declarations.read(),
-            importance: self.importance,
-        }
-    }
-
-}
-
-pub struct ApplicableDeclarationBlockReadGuard<'a> {
-    guard: RwLockReadGuard<'a, PropertyDeclarationBlock>,
-    importance: Importance,
-}
-
-impl<'a> ApplicableDeclarationBlockReadGuard<'a> {
-    pub fn iter(&self) -> ApplicableDeclarationBlockIter {
-        ApplicableDeclarationBlockIter {
-            iter: self.guard.declarations.iter(),
-            importance: self.importance,
+            importance: importance,
         }
     }
 }
@@ -1013,6 +1011,8 @@ impl<'a> DoubleEndedIterator for ApplicableDeclarationBlockIter<'a> {
     }
 }
 
-fn find_push<Str: Eq + Hash>(map: &mut FnvHashMap<Str, Vec<Rule>>, key: Str, value: Rule) {
+#[inline]
+fn find_push<Str: Eq + Hash>(map: &mut FnvHashMap<Str, Vec<Rule>>, key: Str,
+                             value: Rule) {
     map.entry(key).or_insert_with(Vec::new).push(value)
 }
diff --git a/components/style/thread_state.rs b/components/style/thread_state.rs
index 25e77ecbb45..12e52425f55 100644
--- a/components/style/thread_state.rs
+++ b/components/style/thread_state.rs
@@ -24,6 +24,10 @@ bitflags! {
 
 macro_rules! thread_types ( ( $( $fun:ident = $flag:ident ; )* ) => (
     impl ThreadState {
+        pub fn is_worker(self) -> bool {
+            self.contains(IN_WORKER)
+        }
+
         $(
             #[cfg(debug_assertions)]
             pub fn $fun(self) -> bool {
diff --git a/components/style/traversal.rs b/components/style/traversal.rs
index be69690f471..4dff1d0c967 100644
--- a/components/style/traversal.rs
+++ b/components/style/traversal.rs
@@ -294,7 +294,7 @@ fn ensure_element_styled_internal<'a, E, C>(element: E,
                           &mut applicable_declarations);
 
     unsafe {
-        element.cascade_node(context, data, parent, &applicable_declarations);
+        element.cascade_node(context, data, parent, applicable_declarations);
     }
 }
 
@@ -357,7 +357,7 @@ pub fn recalc_style_at<'a, E, C, D>(context: &'a C,
                 // Perform the CSS cascade.
                 unsafe {
                     element.cascade_node(context, data, element.parent_element(),
-                                         &applicable_declarations);
+                                         applicable_declarations);
                 }
 
                 // Add ourselves to the LRU cache.
diff --git a/components/style/values/specified/mod.rs b/components/style/values/specified/mod.rs
index aad327ca1d3..124acadad5a 100644
--- a/components/style/values/specified/mod.rs
+++ b/components/style/values/specified/mod.rs
@@ -215,8 +215,8 @@ impl ToCss for Length {
             Length::FontRelative(length) => length.to_css(dest),
             Length::ViewportPercentage(length) => length.to_css(dest),
             Length::Calc(ref calc, _) => calc.to_css(dest),
-            Length::ServoCharacterWidth(_)
-            => panic!("internal CSS values should never be serialized"),
+            /* This should only be reached from style dumping code */
+            Length::ServoCharacterWidth(CharacterWidth(i)) => write!(dest, "CharWidth({})", i),
         }
     }
 }
diff --git a/components/util/opts.rs b/components/util/opts.rs
index 242cd569bec..d82c9f5a5d7 100644
--- a/components/util/opts.rs
+++ b/components/util/opts.rs
@@ -159,6 +159,9 @@ pub struct Opts {
     /// Dumps the DOM after restyle.
     pub dump_style_tree: bool,
 
+    /// Dumps the rule tree.
+    pub dump_rule_tree: bool,
+
     /// Dumps the flow tree after a layout.
     pub dump_flow_tree: bool,
 
@@ -244,6 +247,9 @@ pub struct DebugOptions {
     /// Print the DOM after each restyle.
     pub dump_style_tree: bool,
 
+    /// Dumps the rule tree.
+    pub dump_rule_tree: bool,
+
     /// Print the flow tree after each layout.
     pub dump_flow_tree: bool,
 
@@ -339,6 +345,7 @@ impl DebugOptions {
                 "disable-text-aa" => debug_options.disable_text_aa = true,
                 "disable-canvas-aa" => debug_options.disable_text_aa = true,
                 "dump-style-tree" => debug_options.dump_style_tree = true,
+                "dump-rule-tree" => debug_options.dump_rule_tree = true,
                 "dump-flow-tree" => debug_options.dump_flow_tree = true,
                 "dump-display-list" => debug_options.dump_display_list = true,
                 "dump-display-list-json" => debug_options.dump_display_list_json = true,
@@ -521,6 +528,7 @@ pub fn default_opts() -> Opts {
         random_pipeline_closure_seed: None,
         sandbox: false,
         dump_style_tree: false,
+        dump_rule_tree: false,
         dump_flow_tree: false,
         dump_display_list: false,
         dump_display_list_json: false,
@@ -824,6 +832,7 @@ pub fn from_cmdline_args(args: &[String]) -> ArgumentParsingResult {
         enable_text_antialiasing: !debug_options.disable_text_aa,
         enable_canvas_antialiasing: !debug_options.disable_canvas_aa,
         dump_style_tree: debug_options.dump_style_tree,
+        dump_rule_tree: debug_options.dump_rule_tree,
         dump_flow_tree: debug_options.dump_flow_tree,
         dump_display_list: debug_options.dump_display_list,
         dump_display_list_json: debug_options.dump_display_list_json,