selectors/subtree_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//! Hashes for the DOM-maintained filter of local names, classes and
6//! null-namespace attribute names in an element's DOM subtree, including itself.
7//! Shadow-tree contents are not included. This is separate from the ancestor
8//! bloom and the wider, lazily constructed `RelativeSelectorFilterMap`.
9//!
10//! Required hashes can be OR'd together: `(filter & hashes) == hashes` means
11//! that a match remains possible. Zero never rejects. Removed names may leave
12//! stale bits, so a hit cannot prove that a selector matches.
13
14// Bit 0 is the DOM's inline-filter tag. Match AttrArray::HashForBloomFilter.
15#[cfg(target_pointer_width = "32")]
16const BLOOM_BITS: u32 = 31;
17
18#[cfg(target_pointer_width = "64")]
19const BLOOM_BITS: u32 = 63;
20
21/// Turn a 32-bit atom hash into the bits it occupies in the subtree filter
22/// (k = 2 hash functions).
23///
24/// This must match `AttrArray::HashForBloomFilter` exactly, or lookups will
25/// reject subtrees that do contain the name we're looking for.
26#[inline]
27pub fn hash_for_subtree_filter(hash: u32) -> u64 {
28 let mut filter = 1u64;
29 filter |= 1u64 << (1 + (hash % BLOOM_BITS));
30 filter |= 1u64 << (1 + ((hash >> 6) % BLOOM_BITS));
31 filter
32}