Source code
Revision control
Copy as Markdown
Other Tools
/* 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
/// Bloom filter for relative selectors.
use fxhash::FxHashMap;
use crate::bloom::BloomFilter;
use crate::context::QuirksMode;
use crate::parser::{collect_selector_hashes, RelativeSelector, RelativeSelectorMatchHint};
use crate::tree::{Element, OpaqueElement};
use crate::SelectorImpl;
enum Entry {
/// Filter lookup happened once. Construction of the filter is expensive,
/// so this is set when the element for subtree traversal is encountered.
Lookup,
/// Filter lookup happened more than once, and the filter for this element's
/// subtree traversal is constructed. Could use special handlings for pseudo-classes
HasFilter(Box<BloomFilter>),
}
#[derive(Clone, Copy, Hash, Eq, PartialEq)]
enum TraversalKind {
Children,
Descendants,
}
fn add_to_filter<E: Element>(element: &E, filter: &mut BloomFilter, kind: TraversalKind) -> bool {
let mut child = element.first_element_child();
while let Some(e) = child {
if !e.add_element_unique_hashes(filter) {
return false;
}
if kind == TraversalKind::Descendants {
if !add_to_filter(&e, filter, kind) {
return false;
}
}
child = e.next_sibling_element();
}
true
}
#[derive(Clone, Copy, Hash, Eq, PartialEq)]
struct Key(OpaqueElement, TraversalKind);
/// Map of bloom filters for fast-rejecting relative selectors.
#[derive(Default)]
pub struct RelativeSelectorFilterMap {
map: FxHashMap<Key, Entry>,
}
fn fast_reject<Impl: SelectorImpl>(
selector: &RelativeSelector<Impl>,
quirks_mode: QuirksMode,
filter: &BloomFilter,
) -> bool {
let mut hashes = [0u32; 4];
let mut len = 0;
// For inner selectors, we only collect from the single rightmost compound.
// This is because inner selectors can cause breakouts: e.g. `.anchor:has(:is(.a .b) .c)`
// can match when `.a` is the ancestor of `.anchor`. Including `.a` would possibly fast
// reject the subtree for not having `.a`, even if the selector would match.
// Technically, if the selector's traversal is non-sibling subtree, we can traverse
// inner selectors up to the point where a descendant/child combinator is encountered
// (e.g. In `.anchor:has(:is(.a ~ .b) .c)`, `.a` is guaranteed to be the a descendant
// of `.anchor`). While that can be separately handled, well, this is simpler.
collect_selector_hashes(
selector.selector.iter(),
quirks_mode,
&mut hashes,
&mut len,
|s| s.iter(),
);
for i in 0..len {
if !filter.might_contain_hash(hashes[i]) {
// Definitely rejected.
return true;
}
}
false
}
impl RelativeSelectorFilterMap {
fn get_filter<E: Element>(&mut self, element: &E, kind: TraversalKind) -> Option<&BloomFilter> {
// Insert flag to indicate that we looked up the filter once, and
// create the filter if and only if that flag is there.
let key = Key(element.opaque(), kind);
let entry = self
.map
.entry(key)
.and_modify(|entry| {
if !matches!(entry, Entry::Lookup) {
return;
}
let mut filter = BloomFilter::new();
// Go through all children/descendants of this element and add their hashes.
if add_to_filter(element, &mut filter, kind) {
*entry = Entry::HasFilter(Box::new(filter));
}
})
.or_insert(Entry::Lookup);
match entry {
Entry::Lookup => None,
Entry::HasFilter(ref filter) => Some(filter.as_ref()),
}
}
/// Potentially reject the given selector for this element.
/// This may seem redundant in presence of the cache, but the cache keys into the
/// selector-element pair specifically, while this filter keys to the element
/// and the traversal kind, so it is useful for handling multiple selectors
/// that effectively end up looking at the same(-ish, for siblings) subtree.
pub fn fast_reject<Impl: SelectorImpl, E: Element>(
&mut self,
element: &E,
selector: &RelativeSelector<Impl>,
quirks_mode: QuirksMode,
) -> bool {
if matches!(
selector.match_hint,
RelativeSelectorMatchHint::InNextSibling
) {
// Don't bother.
return false;
}
let is_sibling = matches!(
selector.match_hint,
RelativeSelectorMatchHint::InSibling |
RelativeSelectorMatchHint::InNextSiblingSubtree |
RelativeSelectorMatchHint::InSiblingSubtree
);
let is_subtree = matches!(
selector.match_hint,
RelativeSelectorMatchHint::InSubtree |
RelativeSelectorMatchHint::InNextSiblingSubtree |
RelativeSelectorMatchHint::InSiblingSubtree
);
let kind = if is_subtree {
TraversalKind::Descendants
} else {
TraversalKind::Children
};
if is_sibling {
// Contain the entirety of the parent's children/subtree in the filter, and use that.
// This is less likely to reject, especially for sibling subtree matches; however, it's less
// expensive memory-wise, compared to storing filters for each sibling.
element.parent_element().map_or(false, |parent| {
self.get_filter(&parent, kind)
.map_or(false, |filter| fast_reject(selector, quirks_mode, filter))
})
} else {
self.get_filter(element, kind)
.map_or(false, |filter| fast_reject(selector, quirks_mode, filter))
}
}
}