rust_browser/crates/selectors/src/bloom.rs

//! Counting bloom filter for ancestor attribute checks.
//!
//! Used during style computation to quickly determine whether a required
//! ancestor tag, class, or ID is definitely absent from the ancestor chain.
//! False positives are acceptable (we'll just do the full ancestor walk);
//! false negatives must never occur.

/// Number of entries in the counting bloom filter.
/// 256 entries gives a reasonable false positive rate for typical DOM depths (10-30).
const FILTER_SIZE: usize = 256;

/// A counting bloom filter that tracks ancestor attributes (tag names, classes, IDs).
///
/// Supports insert/remove for incremental maintenance during DFS traversal.
/// Uses two hash functions to reduce false positive rate.
pub struct AncestorFilter {
    counters: [u8; FILTER_SIZE],
}

impl AncestorFilter {
    pub fn new() -> Self {
        Self {
            counters: [0; FILTER_SIZE],
        }
    }

    /// Insert an attribute key into the filter.
    pub fn insert(&mut self, key: &str) {
        let (h1, h2) = Self::hashes(key);
        self.counters[h1] = self.counters[h1].saturating_add(1);
        self.counters[h2] = self.counters[h2].saturating_add(1);
    }

    /// Remove an attribute key from the filter.
    pub fn remove(&mut self, key: &str) {
        let (h1, h2) = Self::hashes(key);
        self.counters[h1] = self.counters[h1].saturating_sub(1);
        self.counters[h2] = self.counters[h2].saturating_sub(1);
    }

    /// Check if the filter might contain the given key.
    /// Returns `false` if definitely absent, `true` if possibly present.
    pub fn might_contain(&self, key: &str) -> bool {
        let (h1, h2) = Self::hashes(key);
        self.counters[h1] > 0 && self.counters[h2] > 0
    }

    /// Two independent hash functions for the bloom filter.
    fn hashes(key: &str) -> (usize, usize) {
        // FNV-1a inspired hashes with different seeds
        let mut h1: u32 = 0x811c_9dc5;
        let mut h2: u32 = 0x01000193;
        for byte in key.as_bytes() {
            h1 ^= *byte as u32;
            h1 = h1.wrapping_mul(0x0100_0193);
            h2 = h2.wrapping_mul(0x811c_9dc5);
            h2 ^= *byte as u32;
        }
        ((h1 as usize) % FILTER_SIZE, (h2 as usize) % FILTER_SIZE)
    }
}

impl Default for AncestorFilter {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_empty_filter_contains_nothing() {
        let filter = AncestorFilter::new();
        assert!(!filter.might_contain("div"));
        assert!(!filter.might_contain("container"));
    }

    #[test]
    fn test_insert_and_query() {
        let mut filter = AncestorFilter::new();
        filter.insert("div");
        assert!(filter.might_contain("div"));
    }

    #[test]
    fn test_remove_reverts_insert() {
        let mut filter = AncestorFilter::new();
        filter.insert("div");
        assert!(filter.might_contain("div"));
        filter.remove("div");
        assert!(!filter.might_contain("div"));
    }

    #[test]
    fn test_multiple_inserts() {
        let mut filter = AncestorFilter::new();
        filter.insert("div");
        filter.insert("div");
        filter.remove("div");
        // Still present (count = 1)
        assert!(filter.might_contain("div"));
        filter.remove("div");
        // Now gone (count = 0)
        assert!(!filter.might_contain("div"));
    }

    #[test]
    fn test_different_keys() {
        let mut filter = AncestorFilter::new();
        filter.insert("div");
        filter.insert("container");
        assert!(filter.might_contain("div"));
        assert!(filter.might_contain("container"));
        filter.remove("div");
        assert!(!filter.might_contain("div"));
        assert!(filter.might_contain("container"));
    }
}