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.

1 files changed, 60 insertions, 60 deletions

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)
 }