Introduce an NthIndexCache type and pipe it from ThreadLocalStyleContext to MatchingContext.

Some future refactoring here to pass fewer things as parameters would be nice.

11 files changed, 84 insertions, 25 deletions

diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index 195884bebab..76990dc9aa6 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -2188,7 +2188,8 @@ impl ElementMethods for Element {
             Err(_) => Err(Error::Syntax),
             Ok(selectors) => {
                 let quirks_mode = document_from_node(self).quirks_mode();
-                let mut ctx = MatchingContext::new(MatchingMode::Normal, None,
+                // FIXME(bholley): Consider an nth-index cache here.
+                let mut ctx = MatchingContext::new(MatchingMode::Normal, None, None,
                                                    quirks_mode);
                 Ok(matches_selector_list(&selectors, &Root::from_ref(self), &mut ctx))
             }
@@ -2209,7 +2210,8 @@ impl ElementMethods for Element {
                 for element in root.inclusive_ancestors() {
                     if let Some(element) = Root::downcast::<Element>(element) {
                         let quirks_mode = document_from_node(self).quirks_mode();
-                        let mut ctx = MatchingContext::new(MatchingMode::Normal, None,
+                        // FIXME(bholley): Consider an nth-index cache here.
+                        let mut ctx = MatchingContext::new(MatchingMode::Normal, None, None,
                                                            quirks_mode);
                         if matches_selector_list(&selectors, &element, &mut ctx) {
                             return Ok(Some(element));
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index b83cdcbd37e..6b16cc242db 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -363,7 +363,9 @@ impl<'a> Iterator for QuerySelectorIterator {
         self.iterator.by_ref().filter_map(|node| {
             // TODO(cgaebel): Is it worth it to build a bloom filter here
             // (instead of passing `None`)? Probably.
-            let mut ctx = MatchingContext::new(MatchingMode::Normal, None,
+            //
+            // FIXME(bholley): Consider an nth-index cache here.
+            let mut ctx = MatchingContext::new(MatchingMode::Normal, None, None,
                 node.owner_doc().quirks_mode());
             if let Some(element) = Root::downcast(node) {
                 if matches_selector_list(selectors, &element, &mut ctx) {
@@ -754,7 +756,8 @@ impl Node {
             Err(_) => Err(Error::Syntax),
             // Step 3.
             Ok(selectors) => {
-                let mut ctx = MatchingContext::new(MatchingMode::Normal, None,
+                // FIXME(bholley): Consider an nth-index cache here.
+                let mut ctx = MatchingContext::new(MatchingMode::Normal, None, None,
                                                    self.owner_doc().quirks_mode());
                 Ok(self.traverse_preorder().filter_map(Root::downcast).find(|element| {
                     matches_selector_list(&selectors, element, &mut ctx)
diff --git a/components/selectors/context.rs b/components/selectors/context.rs
index 31ce04b37a1..46991d349ce 100644
--- a/components/selectors/context.rs
+++ b/components/selectors/context.rs
@@ -69,15 +69,22 @@ impl QuirksMode {
     }
 }
 
+/// A cache to speed up matching of nth-index-like selectors.
+///
+/// NB: This is just a dummy type right now, it will be fleshed out in later patches.
+#[derive(Default)]
+pub struct NthIndexCache(usize);
+
 /// Data associated with the matching process for a element.  This context is
 /// used across many selectors for an element, so it's not appropriate for
 /// transient data that applies to only a single selector.
-#[derive(Clone)]
 pub struct MatchingContext<'a> {
     /// Input with the matching mode we should use when matching selectors.
     pub matching_mode: MatchingMode,
     /// Input with the bloom filter used to fast-reject selectors.
     pub bloom_filter: Option<&'a BloomFilter>,
+    /// An optional cache to speed up nth-index-like selectors.
+    nth_index_cache: Option<&'a mut NthIndexCache>,
     /// Input that controls how matching for links is handled.
     pub visited_handling: VisitedHandlingMode,
     /// Output that records whether we encountered a "relevant link" while
@@ -94,12 +101,14 @@ impl<'a> MatchingContext<'a> {
     /// Constructs a new `MatchingContext`.
     pub fn new(matching_mode: MatchingMode,
                bloom_filter: Option<&'a BloomFilter>,
+               nth_index_cache: Option<&'a mut NthIndexCache>,
                quirks_mode: QuirksMode)
                -> Self
     {
         Self {
             matching_mode: matching_mode,
             bloom_filter: bloom_filter,
+            nth_index_cache: nth_index_cache,
             visited_handling: VisitedHandlingMode::AllLinksUnvisited,
             relevant_link_found: false,
             quirks_mode: quirks_mode,
@@ -110,6 +119,7 @@ impl<'a> MatchingContext<'a> {
     /// Constructs a new `MatchingContext` for use in visited matching.
     pub fn new_for_visited(matching_mode: MatchingMode,
                            bloom_filter: Option<&'a BloomFilter>,
+                           nth_index_cache: Option<&'a mut NthIndexCache>,
                            visited_handling: VisitedHandlingMode,
                            quirks_mode: QuirksMode)
                            -> Self
@@ -119,6 +129,7 @@ impl<'a> MatchingContext<'a> {
             bloom_filter: bloom_filter,
             visited_handling: visited_handling,
             relevant_link_found: false,
+            nth_index_cache: nth_index_cache,
             quirks_mode: quirks_mode,
             classes_and_ids_case_sensitivity: quirks_mode.classes_and_ids_case_sensitivity(),
         }
diff --git a/components/selectors/matching.rs b/components/selectors/matching.rs
index b9b2da857d8..fad3ce181ae 100644
--- a/components/selectors/matching.rs
+++ b/components/selectors/matching.rs
@@ -724,26 +724,26 @@ fn matches_simple_selector<E, F>(
             element.is_empty()
         }
         Component::NthChild(a, b) => {
-            matches_generic_nth_child(element, a, b, false, false, flags_setter)
+            matches_generic_nth_child(element, context, a, b, false, false, flags_setter)
         }
         Component::NthLastChild(a, b) => {
-            matches_generic_nth_child(element, a, b, false, true, flags_setter)
+            matches_generic_nth_child(element, context, a, b, false, true, flags_setter)
         }
         Component::NthOfType(a, b) => {
-            matches_generic_nth_child(element, a, b, true, false, flags_setter)
+            matches_generic_nth_child(element, context, a, b, true, false, flags_setter)
         }
         Component::NthLastOfType(a, b) => {
-            matches_generic_nth_child(element, a, b, true, true, flags_setter)
+            matches_generic_nth_child(element, context, a, b, true, true, flags_setter)
         }
         Component::FirstOfType => {
-            matches_generic_nth_child(element, 0, 1, true, false, flags_setter)
+            matches_generic_nth_child(element, context, 0, 1, true, false, flags_setter)
         }
         Component::LastOfType => {
-            matches_generic_nth_child(element, 0, 1, true, true, flags_setter)
+            matches_generic_nth_child(element, context, 0, 1, true, true, flags_setter)
         }
         Component::OnlyOfType => {
-            matches_generic_nth_child(element, 0, 1, true, false, flags_setter) &&
-            matches_generic_nth_child(element, 0, 1, true, true, flags_setter)
+            matches_generic_nth_child(element, context, 0, 1, true, false, flags_setter) &&
+            matches_generic_nth_child(element, context, 0, 1, true, true, flags_setter)
         }
         Component::Negation(ref negated) => {
             context.nesting_level += 1;
@@ -767,6 +767,7 @@ fn select_name<'a, T>(is_html: bool, local_name: &'a T, local_name_lower: &'a T)
 
 #[inline]
 fn matches_generic_nth_child<E, F>(element: &E,
+                                   context: &mut LocalMatchingContext<E::Impl>,
                                    a: i32,
                                    b: i32,
                                    is_of_type: bool,
diff --git a/components/style/context.rs b/components/style/context.rs
index 8b26754e0cb..ff2551c0b54 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -23,6 +23,7 @@ use properties::ComputedValues;
 use rule_cache::RuleCache;
 use rule_tree::StrongRuleNode;
 use selector_parser::{EAGER_PSEUDO_COUNT, SnapshotMap};
+use selectors::context::NthIndexCache;
 use selectors::matching::ElementSelectorFlags;
 use servo_arc::Arc;
 #[cfg(feature = "servo")] use servo_atoms::Atom;
@@ -719,6 +720,8 @@ pub struct ThreadLocalStyleContext<E: TElement> {
     /// A checker used to ensure that parallel.rs does not recurse indefinitely
     /// even on arbitrarily deep trees.  See Gecko bug 1376883.
     pub stack_limit_checker: StackLimitChecker,
+    /// A cache for nth-index-like selectors.
+    pub nth_index_cache: NthIndexCache,
 }
 
 impl<E: TElement> ThreadLocalStyleContext<E> {
@@ -737,6 +740,7 @@ impl<E: TElement> ThreadLocalStyleContext<E> {
             font_metrics_provider: E::FontMetricsProvider::create_from(shared),
             stack_limit_checker: StackLimitChecker::new(
                 (STYLE_THREAD_STACK_SIZE_KB - STACK_SAFETY_MARGIN_KB) * 1024),
+            nth_index_cache: NthIndexCache::default(),
         }
     }
 
@@ -754,6 +758,7 @@ impl<E: TElement> ThreadLocalStyleContext<E> {
             font_metrics_provider: E::FontMetricsProvider::create_from(shared),
             stack_limit_checker: StackLimitChecker::new(
                 (STYLE_THREAD_STACK_SIZE_KB - STACK_SAFETY_MARGIN_KB) * 1024),
+            nth_index_cache: NthIndexCache::default(),
         }
     }
 
diff --git a/components/style/invalidation/element/invalidator.rs b/components/style/invalidation/element/invalidator.rs
index 5338bf22e3a..2080ba7676e 100644
--- a/components/style/invalidation/element/invalidator.rs
+++ b/components/style/invalidation/element/invalidator.rs
@@ -633,10 +633,12 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator<'a, 'b, E>
         debug!("TreeStyleInvalidator::process_invalidation({:?}, {:?}, {:?})",
                self.element, invalidation, invalidation_kind);
 
+        // FIXME(bholley): Consider passing an nth-index cache here.
         let mut context =
             MatchingContext::new_for_visited(
                 MatchingMode::Normal,
                 None,
+                None,
                 VisitedHandlingMode::AllLinksVisitedAndUnvisited,
                 self.shared_context.quirks_mode(),
             );
@@ -946,12 +948,14 @@ impl<'a, 'b: 'a, E> InvalidationCollector<'a, 'b, E>
         // whether any parent had a snapshot, and whether those snapshots were
         // taken due to an element class/id change, but it's not clear it'd be
         // worth it.
+        //
+        // FIXME(bholley): Consider passing an nth-index cache here.
         let mut now_context =
-            MatchingContext::new_for_visited(MatchingMode::Normal, None,
+            MatchingContext::new_for_visited(MatchingMode::Normal, None, None,
                                              VisitedHandlingMode::AllLinksUnvisited,
                                              self.shared_context.quirks_mode());
         let mut then_context =
-            MatchingContext::new_for_visited(MatchingMode::Normal, None,
+            MatchingContext::new_for_visited(MatchingMode::Normal, None, None,
                                              VisitedHandlingMode::AllLinksUnvisited,
                                              self.shared_context.quirks_mode());
 
diff --git a/components/style/sharing/checks.rs b/components/style/sharing/checks.rs
index d5607590cd3..2120bbc6f8c 100644
--- a/components/style/sharing/checks.rs
+++ b/components/style/sharing/checks.rs
@@ -10,6 +10,7 @@ use Atom;
 use bloom::StyleBloom;
 use context::{SelectorFlagsMap, SharedStyleContext};
 use dom::TElement;
+use selectors::context::NthIndexCache;
 use sharing::{StyleSharingCandidate, StyleSharingTarget};
 
 /// Determines whether a target and a candidate have compatible parents for sharing.
@@ -99,16 +100,25 @@ pub fn revalidate<E>(target: &mut StyleSharingTarget<E>,
                      candidate: &mut StyleSharingCandidate<E>,
                      shared_context: &SharedStyleContext,
                      bloom: &StyleBloom<E>,
+                     nth_index_cache: &mut NthIndexCache,
                      selector_flags_map: &mut SelectorFlagsMap<E>)
                      -> bool
     where E: TElement,
 {
     let stylist = &shared_context.stylist;
 
-    let for_element =
-        target.revalidation_match_results(stylist, bloom, selector_flags_map);
-
-    let for_candidate = candidate.revalidation_match_results(stylist, bloom);
+    let for_element = target.revalidation_match_results(
+        stylist,
+        bloom,
+        nth_index_cache,
+        selector_flags_map,
+    );
+
+    let for_candidate = candidate.revalidation_match_results(
+        stylist,
+        bloom,
+        nth_index_cache,
+    );
 
     // This assert "ensures", to some extent, that the two candidates have
     // matched the same rulehash buckets, and as such, that the bits we're
diff --git a/components/style/sharing/mod.rs b/components/style/sharing/mod.rs
index c1b843993a7..8e2c9763b1d 100644
--- a/components/style/sharing/mod.rs
+++ b/components/style/sharing/mod.rs
@@ -75,6 +75,7 @@ use matching::MatchMethods;
 use owning_ref::OwningHandle;
 use properties::ComputedValues;
 use rule_tree::StrongRuleNode;
+use selectors::context::NthIndexCache;
 use selectors::matching::{ElementSelectorFlags, VisitedHandlingMode};
 use servo_arc::{Arc, NonZeroPtrMut};
 use smallbitvec::SmallBitVec;
@@ -203,6 +204,7 @@ impl ValidationData {
         element: E,
         stylist: &Stylist,
         bloom: &StyleBloom<E>,
+        nth_index_cache: &mut NthIndexCache,
         bloom_known_valid: bool,
         flags_setter: &mut F
     ) -> &SmallBitVec
@@ -230,6 +232,7 @@ impl ValidationData {
             self.revalidation_match_results =
                 Some(stylist.match_revalidation_selectors(&element,
                                                           bloom_to_use,
+                                                          nth_index_cache,
                                                           flags_setter));
         }
 
@@ -289,11 +292,13 @@ impl<E: TElement> StyleSharingCandidate<E> {
         &mut self,
         stylist: &Stylist,
         bloom: &StyleBloom<E>,
+        nth_index_cache: &mut NthIndexCache,
     ) -> &SmallBitVec {
         self.validation_data.revalidation_match_results(
             self.element,
             stylist,
             bloom,
+            nth_index_cache,
             /* bloom_known_valid = */ false,
             &mut |_, _| {})
     }
@@ -346,6 +351,7 @@ impl<E: TElement> StyleSharingTarget<E> {
         &mut self,
         stylist: &Stylist,
         bloom: &StyleBloom<E>,
+        nth_index_cache: &mut NthIndexCache,
         selector_flags_map: &mut SelectorFlagsMap<E>
     ) -> &SmallBitVec {
         // It's important to set the selector flags. Otherwise, if we succeed in
@@ -372,6 +378,7 @@ impl<E: TElement> StyleSharingTarget<E> {
             self.element,
             stylist,
             bloom,
+            nth_index_cache,
             /* bloom_known_valid = */ true,
             &mut set_selector_flags)
     }
@@ -385,6 +392,7 @@ impl<E: TElement> StyleSharingTarget<E> {
         let shared_context = &context.shared;
         let selector_flags_map = &mut context.thread_local.selector_flags;
         let bloom_filter = &context.thread_local.bloom_filter;
+        let nth_index_cache = &mut context.thread_local.nth_index_cache;
 
         if cache.dom_depth != bloom_filter.matching_depth() {
             debug!("Can't share style, because DOM depth changed from {:?} to {:?}, element: {:?}",
@@ -398,6 +406,7 @@ impl<E: TElement> StyleSharingTarget<E> {
             shared_context,
             selector_flags_map,
             bloom_filter,
+            nth_index_cache,
             self
         )
     }
@@ -596,6 +605,7 @@ impl<E: TElement> StyleSharingCache<E> {
         shared_context: &SharedStyleContext,
         selector_flags_map: &mut SelectorFlagsMap<E>,
         bloom_filter: &StyleBloom<E>,
+        nth_index_cache: &mut NthIndexCache,
         target: &mut StyleSharingTarget<E>,
     ) -> Option<ResolvedElementStyles> {
         if shared_context.options.disable_style_sharing_cache {
@@ -621,6 +631,7 @@ impl<E: TElement> StyleSharingCache<E> {
                 candidate,
                 &shared_context,
                 bloom_filter,
+                nth_index_cache,
                 selector_flags_map
             )
         })
@@ -631,6 +642,7 @@ impl<E: TElement> StyleSharingCache<E> {
         candidate: &mut StyleSharingCandidate<E>,
         shared: &SharedStyleContext,
         bloom: &StyleBloom<E>,
+        nth_index_cache: &mut NthIndexCache,
         selector_flags_map: &mut SelectorFlagsMap<E>
     ) -> Option<ResolvedElementStyles> {
         // Check that we have the same parent, or at least that the parents
@@ -705,7 +717,7 @@ impl<E: TElement> StyleSharingCache<E> {
         }
 
         if !checks::revalidate(target, candidate, shared, bloom,
-                               selector_flags_map) {
+                               nth_index_cache, selector_flags_map) {
             trace!("Miss: Revalidation");
             return None;
         }
diff --git a/components/style/style_resolver.rs b/components/style/style_resolver.rs
index ee66b56a1d9..8c026a28d83 100644
--- a/components/style/style_resolver.rs
+++ b/components/style/style_resolver.rs
@@ -413,10 +413,12 @@ where
 
         let map = &mut self.context.thread_local.selector_flags;
         let bloom_filter = self.context.thread_local.bloom_filter.filter();
+        let nth_index_cache = &mut self.context.thread_local.nth_index_cache;
         let mut matching_context =
             MatchingContext::new_for_visited(
                 MatchingMode::Normal,
                 Some(bloom_filter),
+                Some(nth_index_cache),
                 visited_handling,
                 self.context.shared.quirks_mode(),
             );
@@ -486,11 +488,13 @@ where
         }
 
         let bloom_filter = self.context.thread_local.bloom_filter.filter();
+        let nth_index_cache = &mut self.context.thread_local.nth_index_cache;
 
         let mut matching_context =
             MatchingContext::new_for_visited(
                 MatchingMode::ForStatelessPseudoElement,
                 Some(bloom_filter),
+                Some(nth_index_cache),
                 visited_handling,
                 self.context.shared.quirks_mode(),
             );
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index 60b3d1b520d..b398ff851bc 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -30,7 +30,7 @@ use selector_map::{PrecomputedHashMap, SelectorMap, SelectorMapEntry};
 use selector_parser::{SelectorImpl, PerPseudoElementMap, PseudoElement};
 use selectors::attr::NamespaceConstraint;
 use selectors::bloom::{BloomFilter, NonCountingBloomFilter};
-use selectors::matching::{ElementSelectorFlags, matches_selector, MatchingContext, MatchingMode};
+use selectors::matching::{ElementSelectorFlags, matches_selector, MatchingContext, MatchingMode, NthIndexCache};
 use selectors::matching::VisitedHandlingMode;
 use selectors::parser::{AncestorHashes, Combinator, Component, Selector};
 use selectors::parser::{SelectorIter, SelectorMethods};
@@ -1028,6 +1028,7 @@ impl Stylist {
         let mut matching_context =
             MatchingContext::new(MatchingMode::ForStatelessPseudoElement,
                                  None,
+                                 None,
                                  self.quirks_mode);
 
         self.push_applicable_declarations(
@@ -1061,6 +1062,7 @@ impl Stylist {
                 MatchingContext::new_for_visited(
                     MatchingMode::ForStatelessPseudoElement,
                     None,
+                    None,
                     VisitedHandlingMode::RelevantLinkVisited,
                     self.quirks_mode,
                 );
@@ -1203,7 +1205,7 @@ impl Stylist {
         V: Push<ApplicableDeclarationBlock> + VecLike<ApplicableDeclarationBlock>,
     {
         let mut matching_context =
-            MatchingContext::new(MatchingMode::Normal, None, self.quirks_mode);
+            MatchingContext::new(MatchingMode::Normal, None, None, self.quirks_mode);
         let mut dummy_flag_setter = |_: &E, _: ElementSelectorFlags| {};
 
         let rule_hash_target = element.rule_hash_target();
@@ -1427,6 +1429,7 @@ impl Stylist {
         &self,
         element: &E,
         bloom: Option<&BloomFilter>,
+        nth_index_cache: &mut NthIndexCache,
         flags_setter: &mut F
     ) -> SmallBitVec
     where
@@ -1435,8 +1438,12 @@ impl Stylist {
     {
         // NB: `MatchingMode` doesn't really matter, given we don't share style
         // between pseudos.
-        let mut matching_context =
-            MatchingContext::new(MatchingMode::Normal, bloom, self.quirks_mode);
+        let mut matching_context = MatchingContext::new(
+            MatchingMode::Normal,
+            bloom,
+            Some(nth_index_cache),
+            self.quirks_mode
+        );
 
         // Note that, by the time we're revalidating, we're guaranteed that the
         // candidate and the entry have the same id, classes, and local name.
diff --git a/ports/geckolib/glue.rs b/ports/geckolib/glue.rs
index eccfc810cfe..0409ead88f5 100644
--- a/ports/geckolib/glue.rs
+++ b/ports/geckolib/glue.rs
@@ -1503,7 +1503,7 @@ pub extern "C" fn Servo_StyleRule_SelectorMatchesElement(rule: RawServoStyleRule
         };
 
         let element = GeckoElement(element);
-        let mut ctx = MatchingContext::new(matching_mode, None, element.owner_document_quirks_mode());
+        let mut ctx = MatchingContext::new(matching_mode, None, None, element.owner_document_quirks_mode());
         matches_selector(selector, 0, None, &element, &mut ctx, &mut |_, _| {})
     })
 }