Bug 1334730 - servo: Implement an nth-index cache (from bholley:nth_index_cache). r=emilio, a=sledru
authorBobby Holley <bobbyholley@gmail.com>
Thu, 21 Sep 2017 18:10:05 -0500
changeset 431812 61d057b77852143069240c8a7e9de24577b74831
parent 431811 1ac500d40e49104486b2339988d4581bd150e046
child 431813 df77a4c1b59103eef619fda4ca1e75404e17a95d
push id7819
push userryanvm@gmail.com
push dateMon, 25 Sep 2017 13:25:08 +0000
treeherdermozilla-beta@078e47662790 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersemilio, sledru
bugs1334730
milestone57.0
Bug 1334730 - servo: Implement an nth-index cache (from bholley:nth_index_cache). r=emilio, a=sledru Source-Repo: https://github.com/servo/servo Source-Revision: be9c8ec07a0ca745adf1b412d32b3b32adec122c
servo/components/layout_thread/dom_wrapper.rs
servo/components/script/dom/element.rs
servo/components/selectors/context.rs
servo/components/selectors/lib.rs
servo/components/selectors/matching.rs
servo/components/selectors/nth_index_cache.rs
servo/components/selectors/tree.rs
servo/components/style/context.rs
servo/components/style/gecko/wrapper.rs
servo/components/style/invalidation/element/element_wrapper.rs
servo/components/style/sharing/checks.rs
servo/components/style/sharing/mod.rs
servo/components/style/stylist.rs
--- a/servo/components/layout_thread/dom_wrapper.rs
+++ b/servo/components/layout_thread/dom_wrapper.rs
@@ -625,16 +625,20 @@ impl<'le> ServoLayoutElement<'le> {
 
 fn as_element<'le>(node: LayoutJS<Node>) -> Option<ServoLayoutElement<'le>> {
     node.downcast().map(ServoLayoutElement::from_layout_js)
 }
 
 impl<'le> ::selectors::Element for ServoLayoutElement<'le> {
     type Impl = SelectorImpl;
 
+    fn opaque(&self) -> ::selectors::OpaqueElement {
+        ::selectors::OpaqueElement::new(self.as_node().opaque().0 as *const ())
+    }
+
     fn parent_element(&self) -> Option<ServoLayoutElement<'le>> {
         unsafe {
             self.element.upcast().parent_node_ref().and_then(as_element)
         }
     }
 
     fn first_child_element(&self) -> Option<ServoLayoutElement<'le>> {
         self.as_node().children().filter_map(|n| n.as_element()).next()
@@ -1163,16 +1167,21 @@ impl<'le> ThreadSafeLayoutElement for Se
 /// Probably a few more of this functions can be implemented (like `has_class`, etc.),
 /// but they have no use right now.
 ///
 /// Note that the element implementation is needed only for selector matching,
 /// not for inheritance (styles are inherited appropiately).
 impl<'le> ::selectors::Element for ServoThreadSafeLayoutElement<'le> {
     type Impl = SelectorImpl;
 
+    fn opaque(&self) -> ::selectors::OpaqueElement {
+        ::selectors::OpaqueElement::new(self.as_node().opaque().0 as *const ())
+    }
+
+
     fn parent_element(&self) -> Option<Self> {
         warn!("ServoThreadSafeLayoutElement::parent_element called");
         None
     }
 
     fn first_child_element(&self) -> Option<Self> {
         warn!("ServoThreadSafeLayoutElement::first_child_element called");
         None
--- a/servo/components/script/dom/element.rs
+++ b/servo/components/script/dom/element.rs
@@ -2495,16 +2495,20 @@ impl VirtualMethods for Element {
             self.tag_name.clear();
         }
     }
 }
 
 impl<'a> ::selectors::Element for Root<Element> {
     type Impl = SelectorImpl;
 
+    fn opaque(&self) -> ::selectors::OpaqueElement {
+        ::selectors::OpaqueElement::new(self.reflector().get_jsobject().get())
+    }
+
     fn parent_element(&self) -> Option<Root<Element>> {
         self.upcast::<Node>().GetParentElement()
     }
 
     fn match_pseudo_element(&self,
                             _pseudo: &PseudoElement,
                             _context: &mut MatchingContext)
                             -> bool
--- a/servo/components/selectors/context.rs
+++ b/servo/components/selectors/context.rs
@@ -1,14 +1,15 @@
 /* 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/. */
 
 use attr::CaseSensitivity;
 use bloom::BloomFilter;
+use nth_index_cache::NthIndexCache;
 
 /// What kind of selector matching mode we should use.
 ///
 /// There are two modes of selector matching. The difference is only noticeable
 /// in presence of pseudo-elements.
 #[derive(Clone, Copy, Debug, PartialEq)]
 pub enum MatchingMode {
     /// Don't ignore any pseudo-element selectors.
@@ -64,32 +65,26 @@ impl QuirksMode {
         match self {
             QuirksMode::NoQuirks |
             QuirksMode::LimitedQuirks => CaseSensitivity::CaseSensitive,
             QuirksMode::Quirks => CaseSensitivity::AsciiCaseInsensitive,
         }
     }
 }
 
-/// 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.
 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>,
+    pub 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
     /// matching _any_ selector for this element. (This differs from
     /// `RelevantLinkStatus` which tracks the status for the _current_ selector
     /// only.)
     pub relevant_link_found: bool,
 
--- a/servo/components/selectors/lib.rs
+++ b/servo/components/selectors/lib.rs
@@ -19,17 +19,19 @@ extern crate precomputed_hash;
 extern crate servo_arc;
 extern crate smallvec;
 
 pub mod attr;
 pub mod bloom;
 mod builder;
 pub mod context;
 pub mod matching;
+mod nth_index_cache;
 pub mod parser;
 #[cfg(test)] mod size_of_tests;
 #[cfg(any(test, feature = "gecko_like_types"))] pub mod gecko_like_types;
 pub mod sink;
 mod tree;
 pub mod visitor;
 
+pub use nth_index_cache::NthIndexCache;
 pub use parser::{SelectorImpl, Parser, SelectorList};
-pub use tree::Element;
+pub use tree::{Element, OpaqueElement};
--- a/servo/components/selectors/matching.rs
+++ b/servo/components/selectors/matching.rs
@@ -1,14 +1,15 @@
 /* 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/. */
 
 use attr::{ParsedAttrSelectorOperation, AttrSelectorOperation, NamespaceConstraint};
 use bloom::{BLOOM_HASH_MASK, BloomFilter};
+use nth_index_cache::NthIndexCacheInner;
 use parser::{AncestorHashes, Combinator, Component, LocalName};
 use parser::{Selector, SelectorImpl, SelectorIter, SelectorList};
 use std::borrow::Borrow;
 use tree::Element;
 
 pub use context::*;
 
 // The bloom filter for descendant CSS selectors will have a <1% false
@@ -782,63 +783,95 @@ fn matches_generic_nth_child<E, F>(eleme
     }
 
     flags_setter(element, if is_from_end {
         HAS_SLOW_SELECTOR
     } else {
         HAS_SLOW_SELECTOR_LATER_SIBLINGS
     });
 
-    let index = nth_child_index(element, is_of_type, is_from_end);
+    // Grab a reference to the appropriate cache.
+    let mut cache = context.shared.nth_index_cache.as_mut().map(|c| {
+        c.get(is_of_type, is_from_end)
+    });
+
+    // Lookup or compute the index.
+    let index = if let Some(i) = cache.as_mut().and_then(|c| c.lookup(element.opaque())) {
+        i
+    } else {
+        let i = nth_child_index(element, is_of_type, is_from_end, cache.as_mut().map(|s| &mut **s));
+        cache.as_mut().map(|c| c.insert(element.opaque(), i));
+        i
+    };
+    debug_assert_eq!(index, nth_child_index(element, is_of_type, is_from_end, None), "invalid cache");
 
     // Is there a non-negative integer n such that An+B=index?
     match index.checked_sub(b) {
         None => false,
         Some(an) => match an.checked_div(a) {
             Some(n) => n >= 0 && a * n == an,
             None /* a == 0 */ => an == 0,
         },
     }
 }
 
 #[inline]
+fn same_type<E: Element>(a: &E, b: &E) -> bool {
+    a.get_local_name() == b.get_local_name() &&
+    a.get_namespace() == b.get_namespace()
+}
+
+#[inline]
 fn nth_child_index<E>(
     element: &E,
     is_of_type: bool,
     is_from_end: bool,
+    mut cache: Option<&mut NthIndexCacheInner>,
 ) -> i32
 where
     E: Element,
 {
-    let mut index: i32 = 1;
-    let mut next_sibling = if is_from_end {
-        element.next_sibling_element()
-    } else {
-        element.prev_sibling_element()
-    };
-
-    loop {
-        let sibling = match next_sibling {
-            None => break,
-            Some(next_sibling) => next_sibling
-        };
+    // The traversal mostly processes siblings left to right. So when we walk
+    // siblings to the right when computing NthLast/NthLastOfType we're unlikely
+    // to get cache hits along the way. As such, we take the hit of walking the
+    // siblings to the left checking the cache in the is_from_end case (this
+    // matches what Gecko does). The indices-from-the-left is handled during the
+    // regular look further below.
+    if let Some(ref mut c) = cache {
+        if is_from_end && !c.is_empty() {
+            let mut index: i32 = 1;
+            let mut curr = element.clone();
+            while let Some(e) = curr.prev_sibling_element() {
+                curr = e;
+                if !is_of_type || same_type(element, &curr) {
+                    if let Some(i) = c.lookup(curr.opaque()) {
+                        return i - index;
+                    }
+                    index += 1;
+                }
+            }
+        }
+    }
 
-        if is_of_type {
-            if element.get_local_name() == sibling.get_local_name() &&
-                element.get_namespace() == sibling.get_namespace() {
-                index += 1;
+    let mut index: i32 = 1;
+    let mut curr = element.clone();
+    let next = |e: E| if is_from_end { e.next_sibling_element() } else { e.prev_sibling_element() };
+    while let Some(e) = next(curr) {
+        curr = e;
+        if !is_of_type || same_type(element, &curr) {
+            // If we're computing indices from the left, check each element in the
+            // cache. We handle the indices-from-the-right case at the top of this
+            // function.
+            if !is_from_end {
+                if let Some(i) = cache.as_mut().and_then(|c| c.lookup(curr.opaque())) {
+                    return i + index
+                }
             }
-        } else {
-          index += 1;
+            index += 1;
         }
-        next_sibling = if is_from_end {
-            sibling.next_sibling_element()
-        } else {
-            sibling.prev_sibling_element()
-        };
     }
 
     index
 }
 
 #[inline]
 fn matches_first_child<E, F>(element: &E, flags_setter: &mut F) -> bool
     where E: Element,
new file mode 100644
--- /dev/null
+++ b/servo/components/selectors/nth_index_cache.rs
@@ -0,0 +1,56 @@
+/* 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/. */
+
+use fnv::FnvHashMap;
+use tree::OpaqueElement;
+
+/// A cache to speed up matching of nth-index-like selectors.
+///
+/// See [1] for some discussion around the design tradeoffs.
+///
+/// [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1401855#c3
+#[derive(Default)]
+pub struct NthIndexCache {
+    nth: NthIndexCacheInner,
+    nth_last: NthIndexCacheInner,
+    nth_of_type: NthIndexCacheInner,
+    nth_last_of_type: NthIndexCacheInner,
+}
+
+impl NthIndexCache {
+    /// Gets the appropriate cache for the given parameters.
+    pub fn get(
+        &mut self,
+        is_of_type: bool,
+        is_from_end: bool
+    ) -> &mut NthIndexCacheInner {
+        match (is_of_type, is_from_end) {
+            (false, false) => &mut self.nth,
+            (false, true) => &mut self.nth_last,
+            (true, false) => &mut self.nth_of_type,
+            (true, true) => &mut self.nth_last_of_type,
+        }
+    }
+}
+
+/// The concrete per-pseudo-class cache.
+#[derive(Default)]
+pub struct NthIndexCacheInner(FnvHashMap<OpaqueElement, i32>);
+
+impl NthIndexCacheInner {
+    /// Does a lookup for a given element in the cache.
+    pub fn lookup(&mut self, el: OpaqueElement) -> Option<i32> {
+        self.0.get(&el).map(|x| *x)
+    }
+
+    /// Inserts an entry into the cache.
+    pub fn insert(&mut self, element: OpaqueElement, index: i32) {
+        self.0.insert(element, index);
+    }
+
+    /// Returns whether the cache is empty.
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+}
--- a/servo/components/selectors/tree.rs
+++ b/servo/components/selectors/tree.rs
@@ -3,21 +3,37 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 //! Traits that nodes must implement. Breaks the otherwise-cyclic dependency
 //! between layout and style.
 
 use attr::{AttrSelectorOperation, NamespaceConstraint, CaseSensitivity};
 use matching::{ElementSelectorFlags, LocalMatchingContext, MatchingContext, RelevantLinkStatus};
 use parser::SelectorImpl;
+use servo_arc::NonZeroPtrMut;
 use std::fmt::Debug;
 
-pub trait Element: Sized + Debug {
+/// Opaque representation of an Element, for identity comparisons. We use
+/// NonZeroPtrMut to get the NonZero optimization.
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct OpaqueElement(pub NonZeroPtrMut<()>);
+
+impl OpaqueElement {
+    /// Creates a new OpaqueElement from an arbitrarily-typed pointer.
+    pub fn new<T>(ptr: *const T) -> Self {
+        OpaqueElement(NonZeroPtrMut::new(ptr as *const () as *mut ()))
+    }
+}
+
+pub trait Element: Sized + Clone + Debug {
     type Impl: SelectorImpl;
 
+    /// Converts self into an opaque representation.
+    fn opaque(&self) -> OpaqueElement;
+
     fn parent_element(&self) -> Option<Self>;
 
     /// The parent of a given pseudo-element, after matching a pseudo-element
     /// selector.
     ///
     /// This is guaranteed to be called in a pseudo-element.
     fn pseudo_element_originating_element(&self) -> Option<Self> {
         self.parent_element()
--- a/servo/components/style/context.rs
+++ b/servo/components/style/context.rs
@@ -18,17 +18,17 @@ use lru_cache::{Entry, LRUCache};
 #[cfg(feature = "gecko")] use gecko_bindings::structs;
 use parallel::{STACK_SAFETY_MARGIN_KB, STYLE_THREAD_STACK_SIZE_KB};
 #[cfg(feature = "servo")] use parking_lot::RwLock;
 use properties::ComputedValues;
 #[cfg(feature = "servo")] use properties::PropertyId;
 use rule_cache::RuleCache;
 use rule_tree::StrongRuleNode;
 use selector_parser::{EAGER_PSEUDO_COUNT, SnapshotMap};
-use selectors::context::NthIndexCache;
+use selectors::NthIndexCache;
 use selectors::matching::ElementSelectorFlags;
 use servo_arc::Arc;
 #[cfg(feature = "servo")] use servo_atoms::Atom;
 use shared_lock::StylesheetGuards;
 use sharing::StyleSharingCache;
 use std::fmt;
 use std::ops;
 #[cfg(feature = "servo")] use std::sync::Mutex;
--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -71,17 +71,17 @@ use logical_geometry::WritingMode;
 use media_queries::Device;
 use properties::{ComputedValues, parse_style_attribute};
 use properties::{Importance, PropertyDeclaration, PropertyDeclarationBlock};
 use properties::animated_properties::{AnimatableLonghand, AnimationValue, AnimationValueMap};
 use properties::animated_properties::TransitionProperty;
 use properties::style_structs::Font;
 use rule_tree::CascadeLevel as ServoCascadeLevel;
 use selector_parser::{AttrValue, ElementExt, PseudoClassStringArg};
-use selectors::Element;
+use selectors::{Element, OpaqueElement};
 use selectors::attr::{AttrSelectorOperation, AttrSelectorOperator, CaseSensitivity, NamespaceConstraint};
 use selectors::matching::{ElementSelectorFlags, LocalMatchingContext, MatchingContext};
 use selectors::matching::{RelevantLinkStatus, VisitedHandlingMode};
 use selectors::sink::Push;
 use servo_arc::{Arc, ArcBorrow, RawOffsetArc};
 use shared_lock::Locked;
 use std::cell::RefCell;
 use std::fmt;
@@ -1677,16 +1677,20 @@ impl<'le> PresentationalHintsSynthesizer
             }
         }
     }
 }
 
 impl<'le> ::selectors::Element for GeckoElement<'le> {
     type Impl = SelectorImpl;
 
+    fn opaque(&self) -> OpaqueElement {
+        OpaqueElement::new(self.0)
+    }
+
     fn parent_element(&self) -> Option<Self> {
         // FIXME(emilio): This will need to jump across if the parent node is a
         // shadow root to get the shadow host.
         let parent_node = self.as_node().parent_node();
         parent_node.and_then(|n| n.as_element())
     }
 
     fn pseudo_element_originating_element(&self) -> Option<Self> {
--- a/servo/components/style/invalidation/element/element_wrapper.rs
+++ b/servo/components/style/invalidation/element/element_wrapper.rs
@@ -4,17 +4,17 @@
 
 //! A wrapper over an element and a snapshot, that allows us to selector-match
 //! against a past state of the element.
 
 use {Atom, CaseSensitivityExt, LocalName, Namespace};
 use dom::TElement;
 use element_state::ElementState;
 use selector_parser::{NonTSPseudoClass, PseudoElement, SelectorImpl, Snapshot, SnapshotMap, AttrValue};
-use selectors::Element;
+use selectors::{Element, OpaqueElement};
 use selectors::attr::{AttrSelectorOperation, CaseSensitivity, NamespaceConstraint};
 use selectors::matching::{ElementSelectorFlags, LocalMatchingContext, MatchingContext};
 use selectors::matching::RelevantLinkStatus;
 use std::cell::Cell;
 use std::fmt;
 
 /// In order to compute restyle hints, we perform a selector match against a
 /// list of partial selectors whose rightmost simple selector may be sensitive
@@ -253,16 +253,20 @@ impl<'a, E> Element for ElementWrapper<'
     {
         self.element.match_pseudo_element(pseudo_element, context)
     }
 
     fn is_link(&self) -> bool {
         self.element.is_link()
     }
 
+    fn opaque(&self) -> OpaqueElement {
+        self.element.opaque()
+    }
+
     fn parent_element(&self) -> Option<Self> {
         self.element.parent_element()
             .map(|e| ElementWrapper::new(e, self.snapshot_map))
     }
 
     fn first_child_element(&self) -> Option<Self> {
         self.element.first_child_element()
             .map(|e| ElementWrapper::new(e, self.snapshot_map))
--- a/servo/components/style/sharing/checks.rs
+++ b/servo/components/style/sharing/checks.rs
@@ -5,17 +5,17 @@
 //! Different checks done during the style sharing process in order to determine
 //! quickly whether it's worth to share style, and whether two different
 //! elements can indeed share the same style.
 
 use Atom;
 use bloom::StyleBloom;
 use context::{SelectorFlagsMap, SharedStyleContext};
 use dom::TElement;
-use selectors::context::NthIndexCache;
+use selectors::NthIndexCache;
 use sharing::{StyleSharingCandidate, StyleSharingTarget};
 
 /// Determines whether a target and a candidate have compatible parents for sharing.
 pub fn parents_allow_sharing<E>(
     target: &mut StyleSharingTarget<E>,
     candidate: &mut StyleSharingCandidate<E>
 ) -> bool
     where E: TElement,
--- a/servo/components/style/sharing/mod.rs
+++ b/servo/components/style/sharing/mod.rs
@@ -70,17 +70,17 @@ use atomic_refcell::{AtomicRefCell, Atom
 use bloom::StyleBloom;
 use context::{SelectorFlagsMap, SharedStyleContext, StyleContext};
 use dom::{TElement, SendElement};
 use lru_cache::{LRUCache, Entry};
 use matching::MatchMethods;
 use owning_ref::OwningHandle;
 use properties::ComputedValues;
 use rule_tree::StrongRuleNode;
-use selectors::context::NthIndexCache;
+use selectors::NthIndexCache;
 use selectors::matching::{ElementSelectorFlags, VisitedHandlingMode};
 use servo_arc::{Arc, NonZeroPtrMut};
 use smallbitvec::SmallBitVec;
 use smallvec::SmallVec;
 use std::marker::PhantomData;
 use std::mem;
 use std::ops::Deref;
 use style_resolver::{PrimaryStyle, ResolvedElementStyles};
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -23,19 +23,20 @@ use media_queries::Device;
 use properties::{self, CascadeFlags, ComputedValues};
 use properties::{AnimationRules, PropertyDeclarationBlock};
 #[cfg(feature = "servo")]
 use properties::INHERIT_ALL;
 use properties::IS_LINK;
 use rule_tree::{CascadeLevel, RuleTree, StrongRuleNode, StyleSource};
 use selector_map::{PrecomputedHashMap, SelectorMap, SelectorMapEntry};
 use selector_parser::{SelectorImpl, PerPseudoElementMap, PseudoElement};
+use selectors::NthIndexCache;
 use selectors::attr::NamespaceConstraint;
 use selectors::bloom::{BloomFilter, NonCountingBloomFilter};
-use selectors::matching::{ElementSelectorFlags, matches_selector, MatchingContext, MatchingMode, NthIndexCache};
+use selectors::matching::{ElementSelectorFlags, matches_selector, MatchingContext, MatchingMode};
 use selectors::matching::VisitedHandlingMode;
 use selectors::parser::{AncestorHashes, Combinator, Component, Selector};
 use selectors::parser::{SelectorIter, SelectorMethods};
 use selectors::sink::Push;
 use selectors::visitor::SelectorVisitor;
 use servo_arc::{Arc, ArcBorrow};
 use shared_lock::{Locked, SharedRwLockReadGuard, StylesheetGuards};
 use smallbitvec::SmallBitVec;