selectors/relative_selector/
filter.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5/// Bloom filter for relative selectors.
6use crate::FxHashMap;
7
8use crate::SelectorImpl;
9use crate::bloom::BloomFilter;
10use crate::context::QuirksMode;
11use crate::parser::{RelativeSelector, RelativeSelectorMatchHint, collect_selector_hashes};
12use crate::tree::{Element, OpaqueElement};
13
14enum Entry {
15    /// Filter lookup happened once. Construction of the filter is expensive,
16    /// so this is set when the element for subtree traversal is encountered.
17    Lookup,
18    /// Filter lookup happened more than once, and the filter for this element's
19    /// subtree traversal is constructed. Could use special handlings for pseudo-classes
20    /// such as `:hover` and `:focus`, see Bug 1845503.
21    HasFilter(Box<BloomFilter>),
22}
23
24#[derive(Clone, Copy, Hash, Eq, PartialEq)]
25enum TraversalKind {
26    Children,
27    Descendants,
28}
29
30fn add_to_filter<E: Element>(element: E, filter: &mut BloomFilter, kind: TraversalKind) -> bool {
31    let mut child = element.first_element_child();
32    while let Some(e) = child {
33        if !e.add_element_unique_hashes(filter) {
34            return false;
35        }
36        if kind == TraversalKind::Descendants && !add_to_filter(e, filter, kind) {
37            return false;
38        }
39        child = e.next_sibling_element();
40    }
41    true
42}
43
44#[derive(Clone, Copy, Hash, Eq, PartialEq)]
45struct Key(OpaqueElement, TraversalKind);
46
47/// Map of bloom filters for fast-rejecting relative selectors.
48#[derive(Default)]
49pub struct RelativeSelectorFilterMap {
50    map: FxHashMap<Key, Entry>,
51}
52
53fn fast_reject<Impl: SelectorImpl>(
54    selector: &RelativeSelector<Impl>,
55    quirks_mode: QuirksMode,
56    filter: &BloomFilter,
57) -> bool {
58    let mut hashes = [0u32; 4];
59    let mut len = 0;
60    // For inner selectors, we only collect from the single rightmost compound.
61    // This is because inner selectors can cause breakouts: e.g. `.anchor:has(:is(.a .b) .c)`
62    // can match when `.a` is the ancestor of `.anchor`. Including `.a` would possibly fast
63    // reject the subtree for not having `.a`, even if the selector would match.
64    // Technically, if the selector's traversal is non-sibling subtree, we can traverse
65    // inner selectors up to the point where a descendant/child combinator is encountered
66    // (e.g. In `.anchor:has(:is(.a ~ .b) .c)`, `.a` is guaranteed to be the a descendant
67    // of `.anchor`). While that can be separately handled, well, this is simpler.
68    collect_selector_hashes(
69        selector.selector.iter(),
70        quirks_mode,
71        &mut hashes,
72        &mut len,
73        |s| s.iter(),
74    );
75    for hash in &hashes[0..len] {
76        if !filter.might_contain_hash(*hash) {
77            // Definitely rejected.
78            return true;
79        }
80    }
81    false
82}
83
84impl RelativeSelectorFilterMap {
85    fn get_filter<E: Element>(&mut self, element: E, kind: TraversalKind) -> Option<&BloomFilter> {
86        // Insert flag to indicate that we looked up the filter once, and
87        // create the filter if and only if that flag is there.
88        let key = Key(element.opaque(), kind);
89        let entry = self
90            .map
91            .entry(key)
92            .and_modify(|entry| {
93                if !matches!(entry, Entry::Lookup) {
94                    return;
95                }
96                let mut filter = BloomFilter::new();
97                // Go through all children/descendants of this element and add their hashes.
98                if add_to_filter(element, &mut filter, kind) {
99                    *entry = Entry::HasFilter(Box::new(filter));
100                }
101            })
102            .or_insert(Entry::Lookup);
103        match *entry {
104            Entry::Lookup => None,
105            Entry::HasFilter(ref filter) => Some(filter.as_ref()),
106        }
107    }
108
109    /// Potentially reject the given selector for this element.
110    /// This may seem redundant in presence of the cache, but the cache keys into the
111    /// selector-element pair specifically, while this filter keys to the element
112    /// and the traversal kind, so it is useful for handling multiple selectors
113    /// that effectively end up looking at the same(-ish, for siblings) subtree.
114    pub fn fast_reject<Impl: SelectorImpl, E: Element>(
115        &mut self,
116        element: E,
117        selector: &RelativeSelector<Impl>,
118        quirks_mode: QuirksMode,
119    ) -> bool {
120        if matches!(
121            selector.match_hint,
122            RelativeSelectorMatchHint::InNextSibling
123        ) {
124            // Don't bother.
125            return false;
126        }
127        let is_sibling = matches!(
128            selector.match_hint,
129            RelativeSelectorMatchHint::InSibling
130                | RelativeSelectorMatchHint::InNextSiblingSubtree
131                | RelativeSelectorMatchHint::InSiblingSubtree
132        );
133        let is_subtree = matches!(
134            selector.match_hint,
135            RelativeSelectorMatchHint::InSubtree
136                | RelativeSelectorMatchHint::InNextSiblingSubtree
137                | RelativeSelectorMatchHint::InSiblingSubtree
138        );
139        let kind = if is_subtree {
140            TraversalKind::Descendants
141        } else {
142            TraversalKind::Children
143        };
144        if is_sibling {
145            // Contain the entirety of the parent's children/subtree in the filter, and use that.
146            // This is less likely to reject, especially for sibling subtree matches; however, it's less
147            // expensive memory-wise, compared to storing filters for each sibling.
148            element.parent_element().is_some_and(|parent| {
149                self.get_filter(parent, kind)
150                    .is_some_and(|filter| fast_reject(selector, quirks_mode, filter))
151            })
152        } else {
153            self.get_filter(element, kind)
154                .is_some_and(|filter| fast_reject(selector, quirks_mode, filter))
155        }
156    }
157}
selectors/relative_selector/filter.rs

selectors/relative_selector/
filter.rs
