Bug 1382925 - style: Invert storage of selector maps to key off origin first. draft
authorCameron McCormack <cam@mcc.id.au>
Mon, 07 Aug 2017 13:52:15 +0800
changeset 641542 8a9069a5df3ac6b899b0f18c023ba47675f0b26c
parent 641444 bb8de16ce00cb57b587a14c210ecc7505f366328
child 641543 ba5cdda896e4d347a01c20f2de3e6c9da821cb0c
push id72572
push userbmo:cam@mcc.id.au
push dateMon, 07 Aug 2017 08:22:57 +0000
bugs1382925
milestone57.0a1
Bug 1382925 - style: Invert storage of selector maps to key off origin first. MozReview-Commit-ID: 3VxiQZshsu0
servo/components/style/stylist.rs
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -46,19 +46,18 @@ use stylesheets::{StylesheetInDocument, 
 use stylesheets::keyframes_rule::KeyframesAnimation;
 use stylesheets::viewport_rule::{self, MaybeNew, ViewportRule};
 use thread_state;
 
 pub use ::fnv::FnvHashMap;
 
 /// This structure holds all the selectors and device characteristics
 /// for a given document. The selectors are converted into `Rule`s
-/// (defined in rust-selectors), and introduced in a `SelectorMap`
-/// depending on the pseudo-element (see `PerPseudoElementSelectorMap`),
-/// and stylesheet origin (see the fields of `PerPseudoElementSelectorMap`).
+/// (defined in rust-selectors), and sorted into `SelectorMap`s keyed
+/// off stylesheet origin and pseudo-element (see `CascadeData`).
 ///
 /// This structure is effectively created once per pipeline, in the
 /// LayoutThread corresponding to that pipeline.
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 pub struct Stylist {
     /// Device that the stylist is currently evaluating against.
     ///
     /// This field deserves a bigger comment due to the different use that Gecko
@@ -85,27 +84,24 @@ pub struct Stylist {
 
     /// If true, the device has changed, and the stylist needs to be updated.
     is_device_dirty: bool,
 
     /// If true, the stylist is in a cleared state (e.g. just-constructed, or
     /// had clear() called on it with no following rebuild()).
     is_cleared: bool,
 
-    /// The current selector maps, after evaluating media
-    /// rules against the current device.
-    element_map: PerPseudoElementSelectorMap,
+    /// Selector maps for all of the style sheets in the stylist, after
+    /// evalutaing media rules agains the current device, split out per
+    /// cascade level.
+    cascade_data: CascadeData,
 
     /// The rule tree, that stores the results of selector matching.
     rule_tree: RuleTree,
 
-    /// The selector maps corresponding to a given pseudo-element
-    /// (depending on the implementation)
-    pseudos_map: FnvHashMap<PseudoElement, PerPseudoElementSelectorMap>,
-
     /// A map with all the animations indexed by name.
     animations: FnvHashMap<Atom, KeyframesAnimation>,
 
     /// 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!
@@ -229,48 +225,41 @@ impl From<StyleRuleInclusion> for RuleIn
 }
 
 impl Stylist {
     /// Construct a new `Stylist`, using given `Device` and `QuirksMode`.
     /// If more members are added here, think about whether they should
     /// be reset in clear().
     #[inline]
     pub fn new(device: Device, quirks_mode: QuirksMode) -> Self {
-        let mut stylist = Stylist {
+        Stylist {
             viewport_constraints: None,
             device: device,
             is_device_dirty: true,
             is_cleared: true,
             quirks_mode: quirks_mode,
             effective_media_query_results: EffectiveMediaQueryResults::new(),
 
-            element_map: PerPseudoElementSelectorMap::new(),
-            pseudos_map: Default::default(),
+            cascade_data: CascadeData::new(),
             animations: Default::default(),
             precomputed_pseudo_element_decls: Default::default(),
             rules_source_order: 0,
             rule_tree: RuleTree::new(),
             invalidation_map: InvalidationMap::new(),
             attribute_dependencies: BloomFilter::new(),
             style_attribute_dependency: false,
             state_dependencies: ElementState::empty(),
             mapped_ids: BloomFilter::new(),
             selectors_for_cache_revalidation: SelectorMap::new(),
             num_selectors: 0,
             num_declarations: 0,
             num_rebuilds: 0,
-        };
-
-        SelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
-            stylist.pseudos_map.insert(pseudo, PerPseudoElementSelectorMap::new());
-        });
+        }
 
         // FIXME: Add iso-8859-9.css when the document’s encoding is ISO-8859-8.
-
-        stylist
     }
 
     /// Returns the number of selectors.
     pub fn num_selectors(&self) -> usize {
         self.num_selectors
     }
 
     /// Returns the number of declarations.
@@ -312,18 +301,17 @@ impl Stylist {
 
         self.is_cleared = true;
 
         self.effective_media_query_results.clear();
         self.viewport_constraints = None;
         // preserve current device
         self.is_device_dirty = true;
         // preserve current quirks_mode value
-        self.element_map = PerPseudoElementSelectorMap::new();
-        self.pseudos_map = Default::default();
+        self.cascade_data.clear();
         self.animations.clear(); // Or set to Default::default()?
         self.precomputed_pseudo_element_decls = Default::default();
         self.rules_source_order = 0;
         // We want to keep rule_tree around across stylist rebuilds.
         self.invalidation_map.clear();
         self.attribute_dependencies.clear();
         self.style_attribute_dependency = false;
         self.state_dependencies = ElementState::empty();
@@ -388,20 +376,16 @@ impl Stylist {
                                                &cascaded_rule,
                                                self.quirks_mode)
         }
 
         if let Some(ref constraints) = self.viewport_constraints {
             self.device.account_for_viewport_rule(constraints);
         }
 
-        SelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
-            self.pseudos_map.insert(pseudo, PerPseudoElementSelectorMap::new());
-        });
-
         extra_data.clear();
 
         if let Some(ua_stylesheets) = ua_stylesheets {
             for stylesheet in &ua_stylesheets.user_or_user_agent_stylesheets {
                 self.add_stylesheet(stylesheet, guards.ua_or_user, extra_data);
             }
 
             if self.quirks_mode != QuirksMode::NoQuirks {
@@ -415,18 +399,18 @@ impl Stylist {
             !author_style_disabled || s.origin(guards.author) != Origin::Author
         });
 
         for stylesheet in sheets_to_add {
             self.add_stylesheet(stylesheet, guards.author, extra_data);
         }
 
         SelectorImpl::each_precomputed_pseudo_element(|pseudo| {
-            if let Some(map) = self.pseudos_map.remove(&pseudo) {
-                let declarations = map.user_agent.get_universal_rules(CascadeLevel::UANormal);
+            if let Some(map) = self.cascade_data.user_agent.pseudos_map.remove(&pseudo) {
+                let declarations = map.get_universal_rules(CascadeLevel::UANormal);
                 self.precomputed_pseudo_element_decls.insert(pseudo, declarations);
             }
         });
 
         self.is_device_dirty = false;
         true
     }
 
@@ -477,34 +461,28 @@ impl Stylist {
         for rule in stylesheet.effective_rules(&self.device, guard) {
             match *rule {
                 CssRule::Style(ref locked) => {
                     let style_rule = locked.read_with(&guard);
                     self.num_declarations += style_rule.block.read_with(&guard).len();
                     for selector in &style_rule.selectors.0 {
                         self.num_selectors += 1;
 
-                        let map = if let Some(pseudo) = selector.pseudo_element() {
-                            self.pseudos_map
-                                .entry(pseudo.canonical())
-                                .or_insert_with(PerPseudoElementSelectorMap::new)
-                                .borrow_for_origin(&origin)
-                        } else {
-                            self.element_map.borrow_for_origin(&origin)
-                        };
-
                         let hashes =
                             AncestorHashes::new(&selector, self.quirks_mode);
 
-                        map.insert(
-                            Rule::new(selector.clone(),
-                                      hashes.clone(),
-                                      locked.clone(),
-                                      self.rules_source_order),
-                            self.quirks_mode);
+                        self.cascade_data
+                            .borrow_mut_for_origin(&origin)
+                            .borrow_mut_for_pseudo_or_insert(selector.pseudo_element())
+                            .insert(
+                                Rule::new(selector.clone(),
+                                          hashes.clone(),
+                                          locked.clone(),
+                                          self.rules_source_order),
+                                self.quirks_mode);
 
                         self.invalidation_map.note_selector(selector, self.quirks_mode);
                         let mut visitor = StylistSelectorVisitor {
                             needs_revalidation: false,
                             passed_rightmost_selector: false,
                             attribute_dependencies: &mut self.attribute_dependencies,
                             style_attribute_dependency: &mut self.style_attribute_dependency,
                             state_dependencies: &mut self.state_dependencies,
@@ -852,17 +830,18 @@ impl Stylist {
                                 pseudo: &PseudoElement,
                                 is_probe: bool,
                                 rule_inclusion: RuleInclusion)
                                 -> CascadeInputs
         where E: TElement
     {
         let pseudo = pseudo.canonical();
         debug_assert!(pseudo.is_lazy());
-        if self.pseudos_map.get(&pseudo).is_none() {
+
+        if !self.cascade_data.has_rules_for_pseudo(&pseudo) {
             return CascadeInputs::default()
         }
 
         // Apply the selector flags. We should be in sequential mode
         // already, so we can directly apply the parent flags.
         let mut set_selector_flags = |element: &E, flags: ElementSelectorFlags| {
             if cfg!(feature = "servo") {
                 // Servo calls this function from the worker, but only for internal
@@ -1112,55 +1091,42 @@ impl Stylist {
         // during multiple layout passes, but this is totally bogus, in the
         // sense that it's updated asynchronously.
         //
         // This should probably be an argument to `update`, and use the quirks
         // mode info in the `SharedLayoutContext`.
         self.quirks_mode = quirks_mode;
     }
 
-    /// Returns the correspond PerPseudoElementSelectorMap given PseudoElement.
-    fn get_map(&self,
-               pseudo_element: Option<&PseudoElement>) -> Option<&PerPseudoElementSelectorMap>
-    {
-        match pseudo_element {
-            Some(pseudo) => self.pseudos_map.get(pseudo),
-            None => Some(&self.element_map),
-        }
-    }
-
-
     /// Returns the applicable CSS declarations for the given element by
     /// treating us as an XBL stylesheet-only stylist.
     pub fn push_applicable_declarations_as_xbl_only_stylist<E, V>(&self,
                                                                   element: &E,
                                                                   pseudo_element: Option<&PseudoElement>,
                                                                   applicable_declarations: &mut V)
         where E: TElement,
               V: Push<ApplicableDeclarationBlock> + VecLike<ApplicableDeclarationBlock>,
     {
         let mut matching_context =
             MatchingContext::new(MatchingMode::Normal, None, self.quirks_mode);
         let mut dummy_flag_setter = |_: &E, _: ElementSelectorFlags| {};
 
-        let map = match self.get_map(pseudo_element) {
-            Some(map) => map,
-            None => return,
-        };
         let rule_hash_target = element.rule_hash_target();
 
         // nsXBLPrototypeResources::LoadResources() loads Chrome XBL style
         // sheets under eAuthorSheetFeatures level.
-        map.author.get_all_matching_rules(element,
-                                          &rule_hash_target,
-                                          applicable_declarations,
-                                          &mut matching_context,
-                                          self.quirks_mode,
-                                          &mut dummy_flag_setter,
-                                          CascadeLevel::XBL);
+        if let Some(map) = self.cascade_data.author.borrow_for_pseudo(pseudo_element) {
+            map.get_all_matching_rules(element,
+                                       &rule_hash_target,
+                                       applicable_declarations,
+                                       &mut matching_context,
+                                       self.quirks_mode,
+                                       &mut dummy_flag_setter,
+                                       CascadeLevel::XBL);
+        }
     }
 
     /// Returns the applicable CSS declarations for the given element.
     ///
     /// This corresponds to `ElementRuleCollector` in WebKit.
     ///
     /// The `StyleRelations` recorded in `MatchingContext` indicate hints about
     /// which kind of rules have matched.
@@ -1182,35 +1148,33 @@ impl Stylist {
         debug_assert!(!self.is_device_dirty);
         // Gecko definitely has pseudo-elements with style attributes, like
         // ::-moz-color-swatch.
         debug_assert!(cfg!(feature = "gecko") ||
                       style_attribute.is_none() || pseudo_element.is_none(),
                       "Style attributes do not apply to pseudo-elements");
         debug_assert!(pseudo_element.map_or(true, |p| !p.is_precomputed()));
 
-        let map = match self.get_map(pseudo_element) {
-            Some(map) => map,
-            None => return,
-        };
         let rule_hash_target = element.rule_hash_target();
 
         debug!("Determining if style is shareable: pseudo: {}",
                pseudo_element.is_some());
 
         let only_default_rules = rule_inclusion == RuleInclusion::DefaultOnly;
 
         // Step 1: Normal user-agent rules.
-        map.user_agent.get_all_matching_rules(element,
-                                              &rule_hash_target,
-                                              applicable_declarations,
-                                              context,
-                                              self.quirks_mode,
-                                              flags_setter,
-                                              CascadeLevel::UANormal);
+        if let Some(map) = self.cascade_data.user_agent.borrow_for_pseudo(pseudo_element) {
+            map.get_all_matching_rules(element,
+                                       &rule_hash_target,
+                                       applicable_declarations,
+                                       context,
+                                       self.quirks_mode,
+                                       flags_setter,
+                                       CascadeLevel::UANormal);
+        }
 
         if pseudo_element.is_none() && !only_default_rules {
             // Step 2: Presentational hints.
             let length_before_preshints = applicable_declarations.len();
             element.synthesize_presentational_hints_for_legacy_attributes(
                 context.visited_handling,
                 applicable_declarations
             );
@@ -1228,44 +1192,48 @@ impl Stylist {
         //
         //     element.matches_user_and_author_rules() ||
         //     (is_implemented_pseudo &&
         //      rule_hash_target.matches_user_and_author_rules())
         //
         // Which may be more what you would probably expect.
         if rule_hash_target.matches_user_and_author_rules() {
             // Step 3a: User normal rules.
-            map.user.get_all_matching_rules(element,
-                                            &rule_hash_target,
-                                            applicable_declarations,
-                                            context,
-                                            self.quirks_mode,
-                                            flags_setter,
-                                            CascadeLevel::UserNormal);
+            if let Some(map) = self.cascade_data.user.borrow_for_pseudo(pseudo_element) {
+                map.get_all_matching_rules(element,
+                                           &rule_hash_target,
+                                           applicable_declarations,
+                                           context,
+                                           self.quirks_mode,
+                                           flags_setter,
+                                           CascadeLevel::UserNormal);
+            }
         } else {
             debug!("skipping user rules");
         }
 
         // Step 3b: XBL rules.
         let cut_off_inheritance =
             element.get_declarations_from_xbl_bindings(pseudo_element,
                                                        applicable_declarations);
 
         if rule_hash_target.matches_user_and_author_rules() && !only_default_rules {
             // Gecko skips author normal rules if cutting off inheritance.
             // See nsStyleSet::FileRules().
             if !cut_off_inheritance {
                 // Step 3c: Author normal rules.
-                map.author.get_all_matching_rules(element,
-                                                  &rule_hash_target,
-                                                  applicable_declarations,
-                                                  context,
-                                                  self.quirks_mode,
-                                                  flags_setter,
-                                                  CascadeLevel::AuthorNormal);
+                if let Some(map) = self.cascade_data.author.borrow_for_pseudo(pseudo_element) {
+                    map.get_all_matching_rules(element,
+                                               &rule_hash_target,
+                                               applicable_declarations,
+                                               context,
+                                               self.quirks_mode,
+                                               flags_setter,
+                                               CascadeLevel::AuthorNormal);
+                }
             } else {
                 debug!("skipping author normal rules due to cut off inheritance");
             }
         } else {
             debug!("skipping author normal rules");
         }
 
         if !only_default_rules {
@@ -1587,47 +1555,141 @@ impl<'a> SelectorVisitor for StylistSele
             }
             _ => {},
         }
 
         true
     }
 }
 
-/// Map that contains the CSS rules for a specific PseudoElement
-/// (or lack of PseudoElement).
+/// Data resulting from performing the CSS cascade.
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 #[derive(Debug)]
-struct PerPseudoElementSelectorMap {
+struct CascadeData {
     /// Rules from user agent stylesheets
-    user_agent: SelectorMap<Rule>,
+    user_agent: PerOriginCascadeData,
     /// Rules from author stylesheets
-    author: SelectorMap<Rule>,
+    author: PerOriginCascadeData,
     /// Rules from user stylesheets
-    user: SelectorMap<Rule>,
+    user: PerOriginCascadeData,
 }
 
-impl PerPseudoElementSelectorMap {
-    #[inline]
+impl CascadeData {
     fn new() -> Self {
-        PerPseudoElementSelectorMap {
-            user_agent: SelectorMap::new(),
-            author: SelectorMap::new(),
-            user: SelectorMap::new(),
+        CascadeData {
+            user_agent: PerOriginCascadeData::new(),
+            author: PerOriginCascadeData::new(),
+            user: PerOriginCascadeData::new(),
         }
     }
 
     #[inline]
-    fn borrow_for_origin(&mut self, origin: &Origin) -> &mut SelectorMap<Rule> {
+    fn borrow_mut_for_origin(&mut self, origin: &Origin) -> &mut PerOriginCascadeData {
         match *origin {
             Origin::UserAgent => &mut self.user_agent,
             Origin::Author => &mut self.author,
             Origin::User => &mut self.user,
         }
     }
+
+    fn clear(&mut self) {
+        self.user_agent.clear();
+        self.author.clear();
+        self.user.clear();
+    }
+
+    fn has_rules_for_pseudo(&self, pseudo: &PseudoElement) -> bool {
+        self.iter_origins().any(|d| d.has_rules_for_pseudo(pseudo))
+    }
+
+    fn iter_origins(&self) -> CascadeDataIter {
+        CascadeDataIter {
+            cascade_data: &self,
+            cur: 0,
+        }
+    }
+}
+
+struct CascadeDataIter<'a> {
+    cascade_data: &'a CascadeData,
+    cur: usize,
+}
+
+impl<'a> Iterator for CascadeDataIter<'a> {
+
+    type Item = &'a PerOriginCascadeData;
+
+    fn next(&mut self) -> Option<&'a PerOriginCascadeData> {
+        let result = match self.cur {
+            0 => &self.cascade_data.user_agent,
+            1 => &self.cascade_data.author,
+            2 => &self.cascade_data.user,
+            _ => return None,
+        };
+        self.cur += 1;
+        Some(result)
+    }
+}
+
+/// Data resulting from performing the CSS cascade that is specific to a given
+/// origin.
+#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
+#[derive(Debug)]
+struct PerOriginCascadeData {
+    /// Rules from stylesheets at this `CascadeData`'s origin.
+    element_map: SelectorMap<Rule>,
+
+    /// Rules from stylesheets at this `CascadeData`'s origin that correspond
+    /// to a given pseudo-element.
+    pseudos_map: FnvHashMap<PseudoElement, SelectorMap<Rule>>,
+}
+
+impl PerOriginCascadeData {
+    fn new() -> Self {
+        let mut data = PerOriginCascadeData {
+            element_map: SelectorMap::new(),
+            pseudos_map: Default::default(),
+        };
+        SelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
+            data.pseudos_map.insert(pseudo, SelectorMap::new());
+        });
+        data
+    }
+
+    #[inline]
+    fn borrow_for_pseudo(&self, pseudo: Option<&PseudoElement>) -> Option<&SelectorMap<Rule>> {
+        match pseudo {
+            Some(pseudo) => self.pseudos_map.get(&pseudo.canonical()),
+            None => Some(&self.element_map),
+        }
+    }
+
+    #[inline]
+    fn borrow_mut_for_pseudo_or_insert(&mut self, pseudo: Option<&PseudoElement>) -> &mut SelectorMap<Rule> {
+        match pseudo {
+            Some(pseudo) => {
+                self.pseudos_map
+                    .entry(pseudo.canonical())
+                    .or_insert_with(SelectorMap::new)
+            }
+            None => &mut self.element_map,
+        }
+    }
+
+    fn clear(&mut self) {
+        self.element_map = SelectorMap::new();
+        self.pseudos_map = Default::default();
+        SelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
+            self.pseudos_map.insert(pseudo, SelectorMap::new());
+        });
+    }
+
+    fn has_rules_for_pseudo(&self, pseudo: &PseudoElement) -> bool {
+        self.pseudos_map.contains_key(pseudo)
+    }
 }
 
 /// A rule, that wraps a style rule, but represents a single selector of the
 /// rule.
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 #[derive(Clone, Debug)]
 pub struct Rule {
     /// The selector this struct represents. We store this and the