aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--components/layout_thread/dom_wrapper.rs9
-rw-r--r--components/script/dom/element.rs4
-rw-r--r--components/selectors/context.rs9
-rw-r--r--components/selectors/lib.rs4
-rw-r--r--components/selectors/matching.rs81
-rw-r--r--components/selectors/nth_index_cache.rs56
-rw-r--r--components/selectors/tree.rs18
-rw-r--r--components/style/context.rs2
-rw-r--r--components/style/gecko/wrapper.rs6
-rw-r--r--components/style/invalidation/element/element_wrapper.rs6
-rw-r--r--components/style/sharing/checks.rs2
-rw-r--r--components/style/sharing/mod.rs2
-rw-r--r--components/style/stylist.rs3
13 files changed, 163 insertions, 39 deletions
diff --git a/components/layout_thread/dom_wrapper.rs b/components/layout_thread/dom_wrapper.rs
index a9596f099a2..962fe09a726 100644
--- a/components/layout_thread/dom_wrapper.rs
+++ b/components/layout_thread/dom_wrapper.rs
@@ -630,6 +630,10 @@ fn as_element<'le>(node: LayoutJS<Node>) -> Option<ServoLayoutElement<'le>> {
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)
@@ -1168,6 +1172,11 @@ impl<'le> ThreadSafeLayoutElement for ServoThreadSafeLayoutElement<'le> {
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
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index 76990dc9aa6..cad8c87900a 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -2500,6 +2500,10 @@ impl VirtualMethods for Element {
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()
}
diff --git a/components/selectors/context.rs b/components/selectors/context.rs
index 46991d349ce..f0da3b14ef6 100644
--- a/components/selectors/context.rs
+++ b/components/selectors/context.rs
@@ -4,6 +4,7 @@
use attr::CaseSensitivity;
use bloom::BloomFilter;
+use nth_index_cache::NthIndexCache;
/// What kind of selector matching mode we should use.
///
@@ -69,12 +70,6 @@ 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.
@@ -84,7 +79,7 @@ pub struct MatchingContext<'a> {
/// 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
diff --git a/components/selectors/lib.rs b/components/selectors/lib.rs
index 2184dfc64e7..0805a53041f 100644
--- a/components/selectors/lib.rs
+++ b/components/selectors/lib.rs
@@ -24,6 +24,7 @@ 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;
@@ -31,5 +32,6 @@ 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};
diff --git a/components/selectors/matching.rs b/components/selectors/matching.rs
index afff6cd1e92..ff0dd40b484 100644
--- a/components/selectors/matching.rs
+++ b/components/selectors/matching.rs
@@ -4,6 +4,7 @@
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;
@@ -787,7 +788,20 @@ fn matches_generic_nth_child<E, F>(element: &E,
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) {
@@ -800,40 +814,59 @@ fn matches_generic_nth_child<E, F>(element: &E,
}
#[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
diff --git a/components/selectors/nth_index_cache.rs b/components/selectors/nth_index_cache.rs
new file mode 100644
index 00000000000..ebae7a6033a
--- /dev/null
+++ b/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()
+ }
+}
diff --git a/components/selectors/tree.rs b/components/selectors/tree.rs
index 23238237b2f..958311ad0d8 100644
--- a/components/selectors/tree.rs
+++ b/components/selectors/tree.rs
@@ -8,11 +8,27 @@
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
diff --git a/components/style/context.rs b/components/style/context.rs
index ff2551c0b54..dadd80d343b 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -23,7 +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::NthIndexCache;
use selectors::matching::ElementSelectorFlags;
use servo_arc::Arc;
#[cfg(feature = "servo")] use servo_atoms::Atom;
diff --git a/components/style/gecko/wrapper.rs b/components/style/gecko/wrapper.rs
index 641aafbb31a..655b6759ca0 100644
--- a/components/style/gecko/wrapper.rs
+++ b/components/style/gecko/wrapper.rs
@@ -76,7 +76,7 @@ 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};
@@ -1682,6 +1682,10 @@ impl<'le> PresentationalHintsSynthesizer for GeckoElement<'le> {
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.
diff --git a/components/style/invalidation/element/element_wrapper.rs b/components/style/invalidation/element/element_wrapper.rs
index 2bb2c3857dc..705da44840c 100644
--- a/components/style/invalidation/element/element_wrapper.rs
+++ b/components/style/invalidation/element/element_wrapper.rs
@@ -9,7 +9,7 @@ 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;
@@ -258,6 +258,10 @@ impl<'a, E> Element for ElementWrapper<'a, E>
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))
diff --git a/components/style/sharing/checks.rs b/components/style/sharing/checks.rs
index 2120bbc6f8c..20020b9497b 100644
--- a/components/style/sharing/checks.rs
+++ b/components/style/sharing/checks.rs
@@ -10,7 +10,7 @@ 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.
diff --git a/components/style/sharing/mod.rs b/components/style/sharing/mod.rs
index 8e2c9763b1d..e99da60f4b9 100644
--- a/components/style/sharing/mod.rs
+++ b/components/style/sharing/mod.rs
@@ -75,7 +75,7 @@ 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;
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index b398ff851bc..5962117fbad 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -28,9 +28,10 @@ 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};
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-01 15:08:09 +0000