servo: Merge #18703 - style: Allow passing an nth-index-cache to the invalidation code (from emilio:nth-index-cache-invalidate); r=bholley
authorEmilio Cobos Álvarez <emilio@crisal.io>
Tue, 03 Oct 2017 00:40:03 -0500
changeset 426824 03ac8608515f88f5604e2299ad3f3380d8aeaa8c
parent 426746 14841c4d8a9783ad55a0c560ec9312ba16200ac1
child 426825 08b8284f7cb78035aebdb52803c5e189e24e1077
push id97
push userfmarier@mozilla.com
push dateSat, 14 Oct 2017 01:12:59 +0000
reviewersbholley
milestone58.0a1
servo: Merge #18703 - style: Allow passing an nth-index-cache to the invalidation code (from emilio:nth-index-cache-invalidate); r=bholley style: Allow passing an nth-index-cache to the invalidation code. Source-Repo: https://github.com/servo/servo Source-Revision: 2a5121357a76e2b558ecd0dae7689d709b6a2b41
servo/components/style/data.rs
servo/components/style/invalidation/element/invalidator.rs
servo/components/style/traversal.rs
servo/ports/geckolib/glue.rs
--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -9,16 +9,17 @@ use dom::TElement;
 use invalidation::element::invalidator::InvalidationResult;
 use invalidation::element::restyle_hints::RestyleHint;
 #[cfg(feature = "gecko")]
 use malloc_size_of::MallocSizeOfOps;
 use properties::ComputedValues;
 use properties::longhands::display::computed_value as display;
 use rule_tree::StrongRuleNode;
 use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, RestyleDamage};
+use selectors::NthIndexCache;
 use servo_arc::Arc;
 use shared_lock::StylesheetGuards;
 use std::fmt;
 use std::mem;
 use std::ops::{Deref, DerefMut};
 use style_resolver::{PrimaryStyle, ResolvedElementStyles, ResolvedStyle};
 
 bitflags! {
@@ -231,16 +232,17 @@ impl ElementData {
     /// Invalidates style for this element, its descendants, and later siblings,
     /// based on the snapshot of the element that we took when attributes or
     /// state changed.
     pub fn invalidate_style_if_needed<'a, E: TElement>(
         &mut self,
         element: E,
         shared_context: &SharedStyleContext,
         stack_limit_checker: Option<&StackLimitChecker>,
+        nth_index_cache: Option<&mut NthIndexCache>,
     ) -> InvalidationResult {
         // In animation-only restyle we shouldn't touch snapshot at all.
         if shared_context.traversal_flags.for_animation_only() {
             return InvalidationResult::empty();
         }
 
         use invalidation::element::invalidator::TreeStyleInvalidator;
 
@@ -256,17 +258,19 @@ impl ElementData {
             return InvalidationResult::empty();
         }
 
         let invalidator = TreeStyleInvalidator::new(
             element,
             Some(self),
             shared_context,
             stack_limit_checker,
+            nth_index_cache,
         );
+
         let result = invalidator.invalidate();
         unsafe { element.set_handled_snapshot() }
         debug_assert!(element.handled_snapshot());
         result
     }
 
     /// Returns true if this element has styles.
     #[inline]
--- a/servo/components/style/invalidation/element/invalidator.rs
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -10,16 +10,17 @@ use context::{SharedStyleContext, StackL
 use data::ElementData;
 use dom::{TElement, TNode};
 use element_state::{ElementState, IN_VISITED_OR_UNVISITED_STATE};
 use invalidation::element::element_wrapper::{ElementSnapshot, ElementWrapper};
 use invalidation::element::invalidation_map::*;
 use invalidation::element::restyle_hints::*;
 use selector_map::SelectorMap;
 use selector_parser::{SelectorImpl, Snapshot};
+use selectors::NthIndexCache;
 use selectors::attr::CaseSensitivity;
 use selectors::matching::{MatchingContext, MatchingMode, VisitedHandlingMode};
 use selectors::matching::{matches_selector, matches_compound_selector};
 use selectors::matching::CompoundSelectorMatchingResult;
 use selectors::parser::{Combinator, Component, Selector};
 use smallvec::SmallVec;
 use std::fmt;
 
@@ -42,16 +43,17 @@ pub struct TreeStyleInvalidator<'a, 'b: 
     // inserted in the tree and still has no data (though I _think_ the slow
     // selector bits save us, it'd be nice not to depend on them).
     //
     // Seems like we could at least avoid running invalidation for the
     // descendants if an element has no data, though.
     data: Option<&'a mut ElementData>,
     shared_context: &'a SharedStyleContext<'b>,
     stack_limit_checker: Option<&'a StackLimitChecker>,
+    nth_index_cache: Option<&'a mut NthIndexCache>,
 }
 
 type InvalidationVector = SmallVec<[Invalidation; 10]>;
 
 /// The kind of invalidation we're processing.
 ///
 /// We can use this to avoid pushing invalidations of the same kind to our
 /// descendants or siblings.
@@ -169,22 +171,24 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
     where E: TElement,
 {
     /// Trivially constructs a new `TreeStyleInvalidator`.
     pub fn new(
         element: E,
         data: Option<&'a mut ElementData>,
         shared_context: &'a SharedStyleContext<'b>,
         stack_limit_checker: Option<&'a StackLimitChecker>,
+        nth_index_cache: Option<&'a mut NthIndexCache>,
     ) -> Self {
         Self {
             element,
             data,
             shared_context,
             stack_limit_checker,
+            nth_index_cache,
         }
     }
 
     /// Perform the invalidation pass.
     pub fn invalidate(mut self) -> InvalidationResult {
         debug!("StyleTreeInvalidator::invalidate({:?})", self.element);
         debug_assert!(self.element.has_snapshot(), "Why bothering?");
         debug_assert!(self.data.is_some(), "How exactly?");
@@ -247,26 +251,27 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
             } else {
                 self.element
             };
 
         let mut descendant_invalidations = InvalidationVector::new();
         let mut sibling_invalidations = InvalidationVector::new();
         let invalidated_self = {
             let mut collector = InvalidationCollector {
-                wrapper: wrapper,
+                wrapper,
+                lookup_element,
+                nth_index_cache: self.nth_index_cache.as_mut().map(|c| &mut **c),
+                state_changes,
                 element: self.element,
                 snapshot: &snapshot,
                 shared_context: self.shared_context,
-                lookup_element: lookup_element,
                 removed_id: id_removed.as_ref(),
                 added_id: id_added.as_ref(),
                 classes_removed: &classes_removed,
                 classes_added: &classes_added,
-                state_changes: state_changes,
                 descendant_invalidations: &mut descendant_invalidations,
                 sibling_invalidations: &mut sibling_invalidations,
                 invalidates_self: false,
             };
 
             shared_context.stylist.each_invalidation_map(|invalidation_map| {
                 collector.collect_dependencies_in_invalidation_map(invalidation_map);
             });
@@ -320,16 +325,17 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
             let mut sibling_data = sibling.mutate_data();
             let sibling_data = sibling_data.as_mut().map(|d| &mut **d);
 
             let mut sibling_invalidator = TreeStyleInvalidator::new(
                 sibling,
                 sibling_data,
                 self.shared_context,
                 self.stack_limit_checker,
+                self.nth_index_cache.as_mut().map(|c| &mut **c),
             );
 
             let mut invalidations_for_descendants = InvalidationVector::new();
             any_invalidated |=
                 sibling_invalidator.process_sibling_invalidations(
                     &mut invalidations_for_descendants,
                     sibling_invalidations,
                 );
@@ -383,16 +389,17 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
         let mut child_data = child.mutate_data();
         let child_data = child_data.as_mut().map(|d| &mut **d);
 
         let mut child_invalidator = TreeStyleInvalidator::new(
             child,
             child_data,
             self.shared_context,
             self.stack_limit_checker,
+            self.nth_index_cache.as_mut().map(|c| &mut **c),
         );
 
         let mut invalidations_for_descendants = InvalidationVector::new();
         let mut invalidated_child = false;
 
         invalidated_child |=
             child_invalidator.process_sibling_invalidations(
                 &mut invalidations_for_descendants,
@@ -628,32 +635,32 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
         invalidation: &Invalidation,
         descendant_invalidations: &mut InvalidationVector,
         sibling_invalidations: &mut InvalidationVector,
         invalidation_kind: InvalidationKind,
     ) -> SingleInvalidationResult {
         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(
+        let matching_result = {
+            let mut context = MatchingContext::new_for_visited(
                 MatchingMode::Normal,
                 None,
-                None,
+                self.nth_index_cache.as_mut().map(|c| &mut **c),
                 VisitedHandlingMode::AllLinksVisitedAndUnvisited,
                 self.shared_context.quirks_mode(),
             );
 
-        let matching_result = matches_compound_selector(
-            &invalidation.selector,
-            invalidation.offset,
-            &mut context,
-            &self.element
-        );
+            matches_compound_selector(
+                &invalidation.selector,
+                invalidation.offset,
+                &mut context,
+                &self.element
+            )
+        };
 
         let mut invalidated_self = false;
         let mut matched = false;
         match matching_result {
             CompoundSelectorMatchingResult::Matched { next_combinator_offset: 0 } => {
                 debug!(" > Invalidation matched completely");
                 matched = true;
                 invalidated_self = true;
@@ -809,16 +816,17 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
     }
 }
 
 struct InvalidationCollector<'a, 'b: 'a, E>
     where E: TElement,
 {
     element: E,
     wrapper: ElementWrapper<'b, E>,
+    nth_index_cache: Option<&'a mut NthIndexCache>,
     snapshot: &'a Snapshot,
     shared_context: &'a SharedStyleContext<'b>,
     lookup_element: E,
     removed_id: Option<&'a Atom>,
     added_id: Option<&'a Atom>,
     classes_removed: &'a SmallVec<[Atom; 8]>,
     classes_added: &'a SmallVec<[Atom; 8]>,
     state_changes: ElementState,
@@ -918,71 +926,97 @@ impl<'a, 'b: 'a, E> InvalidationCollecto
                         VisitedDependent::No
                     };
                 self.scan_dependency(&dependency.dep, visited_dependent);
                 true
             },
         );
     }
 
+    /// Check whether a dependency should be taken into account, using a given
+    /// visited handling mode.
+    fn check_dependency(
+        &mut self,
+        visited_handling_mode: VisitedHandlingMode,
+        dependency: &Dependency,
+        relevant_link_found: &mut bool,
+    ) -> bool {
+        let (matches_now, relevant_link_found_now) = {
+            let mut context = MatchingContext::new_for_visited(
+                MatchingMode::Normal,
+                None,
+                self.nth_index_cache.as_mut().map(|c| &mut **c),
+                visited_handling_mode,
+                self.shared_context.quirks_mode(),
+            );
+
+            let matches_now = matches_selector(
+                &dependency.selector,
+                dependency.selector_offset,
+                None,
+                &self.element,
+                &mut context,
+                &mut |_, _| {},
+            );
+
+            (matches_now, context.relevant_link_found)
+        };
+
+        let (matched_then, relevant_link_found_then) = {
+            let mut context = MatchingContext::new_for_visited(
+                MatchingMode::Normal,
+                None,
+                self.nth_index_cache.as_mut().map(|c| &mut **c),
+                visited_handling_mode,
+                self.shared_context.quirks_mode(),
+            );
+
+            let matched_then = matches_selector(
+                &dependency.selector,
+                dependency.selector_offset,
+                None,
+                &self.wrapper,
+                &mut context,
+                &mut |_, _| {},
+            );
+
+            (matched_then, context.relevant_link_found)
+        };
+
+        *relevant_link_found = relevant_link_found_now;
+
+        // Check for mismatches in both the match result and also the status
+        // of whether a relevant link was found.
+        matched_then != matches_now ||
+            relevant_link_found_now != relevant_link_found_then
+    }
+
     fn scan_dependency(
         &mut self,
         dependency: &Dependency,
         is_visited_dependent: VisitedDependent,
     ) {
         debug!("TreeStyleInvalidator::scan_dependency({:?}, {:?}, {:?})",
                self.element,
                dependency,
                is_visited_dependent);
 
         if !self.dependency_may_be_relevant(dependency) {
             return;
         }
 
-        // TODO(emilio): Add a bloom filter here?
-        //
-        // If we decide to do so, we can't use the bloom filter for snapshots,
-        // given that arbitrary elements in the parent chain may have mutated
-        // their id's/classes, which means that they won't be in the filter, and
-        // as such we may fast-reject selectors incorrectly.
-        //
-        // We may be able to improve this if we record as we go down the tree
-        // 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, None,
-                                             VisitedHandlingMode::AllLinksUnvisited,
-                                             self.shared_context.quirks_mode());
-        let mut then_context =
-            MatchingContext::new_for_visited(MatchingMode::Normal, None, None,
-                                             VisitedHandlingMode::AllLinksUnvisited,
-                                             self.shared_context.quirks_mode());
+        let mut relevant_link_found = false;
 
-        let matched_then =
-            matches_selector(&dependency.selector,
-                             dependency.selector_offset,
-                             None,
-                             &self.wrapper,
-                             &mut then_context,
-                             &mut |_, _| {});
-        let matches_now =
-            matches_selector(&dependency.selector,
-                             dependency.selector_offset,
-                             None,
-                             &self.element,
-                             &mut now_context,
-                             &mut |_, _| {});
+        let should_account_for_dependency = self.check_dependency(
+            VisitedHandlingMode::AllLinksUnvisited,
+            dependency,
+            &mut relevant_link_found,
+        );
 
-        // Check for mismatches in both the match result and also the status
-        // of whether a relevant link was found.
-        if matched_then != matches_now ||
-           then_context.relevant_link_found != now_context.relevant_link_found {
+        if should_account_for_dependency {
             return self.note_dependency(dependency);
         }
 
         // If there is a relevant link, then we also matched in visited
         // mode.
         //
         // Match again in this mode to ensure this also matches.
         //
@@ -992,35 +1026,24 @@ impl<'a, 'b: 'a, E> InvalidationCollecto
         // The matching process only considers the relevant link state and
         // visited handling mode when deciding if visited matches.  Instead, we
         // are rematching here in case there is some :visited selector whose
         // matching result changed for some other state or attribute change of
         // this element (for example, for things like [foo]:visited).
         //
         // NOTE: This thing is actually untested because testing it is flaky,
         // see the tests that were added and then backed out in bug 1328509.
-        if is_visited_dependent == VisitedDependent::Yes && now_context.relevant_link_found {
-            then_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
-            let matched_then =
-                matches_selector(&dependency.selector,
-                                 dependency.selector_offset,
-                                 None,
-                                 &self.wrapper,
-                                 &mut then_context,
-                                 &mut |_, _| {});
+        if is_visited_dependent == VisitedDependent::Yes && relevant_link_found {
+            let should_account_for_dependency = self.check_dependency(
+                VisitedHandlingMode::RelevantLinkVisited,
+                dependency,
+                &mut false,
+            );
 
-            now_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
-            let matches_now =
-                matches_selector(&dependency.selector,
-                                 dependency.selector_offset,
-                                 None,
-                                 &self.element,
-                                 &mut now_context,
-                                 &mut |_, _| {});
-            if matched_then != matches_now {
+            if should_account_for_dependency {
                 return self.note_dependency(dependency);
             }
         }
     }
 
     fn note_dependency(&mut self, dependency: &Dependency) {
         if dependency.affects_self() {
             self.invalidates_self = true;
--- a/servo/components/style/traversal.rs
+++ b/servo/components/style/traversal.rs
@@ -164,18 +164,21 @@ pub trait DomTraversal<E: TElement> : Sy
             //
             // From the perspective of this traversal, the root cannot have
             // reconstructed ancestors.
             data.set_reconstructed_ancestor(false);
 
             if !traversal_flags.for_animation_only() {
                 // Invalidate our style, and that of our siblings and
                 // descendants as needed.
+                //
+                // FIXME(emilio): an nth-index cache could be worth here, even
+                // if temporary?
                 let invalidation_result =
-                    data.invalidate_style_if_needed(root, shared_context, None);
+                    data.invalidate_style_if_needed(root, shared_context, None, None);
 
                 if invalidation_result.has_invalidated_siblings() {
                     let actual_root =
                         parent.expect("How in the world can you invalidate \
                                        siblings without a parent?");
                     unsafe { actual_root.set_dirty_descendants() }
                     return PreTraverseToken(Some(actual_root));
                 }
@@ -890,17 +893,18 @@ where
 
             // Handle element snapshots and invalidation of descendants and siblings
             // as needed.
             //
             // NB: This will be a no-op if there's no snapshot.
             child_data.invalidate_style_if_needed(
                 child,
                 &context.shared,
-                Some(&context.thread_local.stack_limit_checker)
+                Some(&context.thread_local.stack_limit_checker),
+                Some(&mut context.thread_local.nth_index_cache)
             );
         }
 
         if D::element_needs_traversal(child, flags, child_data.map(|d| &*d), Some(data)) {
             note_child(child_node);
 
             // Set the dirty descendants bit on the parent as needed, so that we
             // can find elements during the post-traversal.
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -4053,17 +4053,27 @@ pub extern "C" fn Servo_ProcessInvalidat
     let shared_style_context = create_shared_context(&global_style_data,
                                                      &guard,
                                                      &per_doc_data,
                                                      TraversalFlags::empty(),
                                                      unsafe { &*snapshots });
     let mut data = data.as_mut().map(|d| &mut **d);
 
     if let Some(ref mut data) = data {
-        let result = data.invalidate_style_if_needed(element, &shared_style_context, None);
+        // FIXME(emilio): an nth-index cache could be worth here, even
+        // if temporary?
+        //
+        // Also, ideally we could share them across all the elements?
+        let result = data.invalidate_style_if_needed(
+            element,
+            &shared_style_context,
+            None,
+            None,
+        );
+
         if result.has_invalidated_siblings() {
             let parent = element.traversal_parent().expect("How could we invalidate siblings without a common parent?");
             unsafe {
                 parent.set_dirty_descendants();
                 bindings::Gecko_NoteDirtySubtreeForInvalidation(parent.0);
             }
         } else if result.has_invalidated_descendants() {
             unsafe { bindings::Gecko_NoteDirtySubtreeForInvalidation(element.0) };