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

selectors/relative_selector/
filter.rs
