tessera_codegraph/
bloom.rs

1use std::hash::{Hash, Hasher};
2
3use bit_vec::BitVec;
4
5/// A small, allocation-free Bloom filter. We use it to short-circuit the
6/// hallucination validator: if a symbol isn't in the bloom it's *definitely*
7/// not in the graph, so we can return early without an SQL round-trip.
8#[derive(Debug, Clone)]
9pub struct BloomFilter {
10    bits: BitVec,
11    k: u32,
12    m: u64,
13}
14
15impl BloomFilter {
16    pub fn for_expected(items: usize, false_positive: f64) -> Self {
17        let items = items.max(1) as f64;
18        let p = false_positive.clamp(1e-6, 0.5);
19        let ln2 = std::f64::consts::LN_2;
20        let m = (-(items * p.ln()) / (ln2 * ln2)).ceil() as u64;
21        let m = m.max(64);
22        let k = ((m as f64 / items) * ln2).ceil() as u32;
23        let k = k.clamp(2, 16);
24        Self {
25            bits: BitVec::from_elem(m as usize, false),
26            k,
27            m,
28        }
29    }
30
31    pub fn insert(&mut self, item: &str) {
32        let (h1, h2) = double_hash(item);
33        for i in 0..self.k {
34            let combined = h1.wrapping_add((i as u64).wrapping_mul(h2));
35            let index = (combined % self.m) as usize;
36            self.bits.set(index, true);
37        }
38    }
39
40    pub fn contains(&self, item: &str) -> bool {
41        let (h1, h2) = double_hash(item);
42        (0..self.k).all(|i| {
43            let combined = h1.wrapping_add((i as u64).wrapping_mul(h2));
44            let index = (combined % self.m) as usize;
45            self.bits.get(index).unwrap_or(false)
46        })
47    }
48
49    pub fn to_bytes(&self) -> Vec<u8> {
50        let bytes = self.bits.to_bytes();
51        let mut out = Vec::with_capacity(bytes.len() + 16);
52        out.extend_from_slice(&self.k.to_le_bytes());
53        out.extend_from_slice(&self.m.to_le_bytes());
54        let bit_len = self.bits.len() as u64;
55        out.extend_from_slice(&bit_len.to_le_bytes());
56        out.extend_from_slice(&bytes);
57        out
58    }
59
60    pub fn from_bytes(bytes: &[u8]) -> Option<Self> {
61        if bytes.len() < 4 + 8 + 8 {
62            return None;
63        }
64        let k = u32::from_le_bytes(bytes[0..4].try_into().ok()?);
65        let m = u64::from_le_bytes(bytes[4..12].try_into().ok()?);
66        let bit_len = u64::from_le_bytes(bytes[12..20].try_into().ok()?) as usize;
67        let raw = &bytes[20..];
68        let mut bits = BitVec::from_bytes(raw);
69        bits.truncate(bit_len);
70        Some(Self { bits, k, m })
71    }
72}
73
74fn double_hash(item: &str) -> (u64, u64) {
75    let mut h1 = std::collections::hash_map::DefaultHasher::new();
76    item.hash(&mut h1);
77    let h1 = h1.finish();
78
79    let mut h2 = std::collections::hash_map::DefaultHasher::new();
80    (item, "tessera").hash(&mut h2);
81    let h2 = h2.finish() | 1;
82    (h1, h2)
83}
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn round_trip() {
91        let mut bloom = BloomFilter::for_expected(100, 0.01);
92        bloom.insert("findById");
93        bloom.insert("loadUser");
94        assert!(bloom.contains("findById"));
95        assert!(bloom.contains("loadUser"));
96        // Probabilistic; "nonexistent_unique_xyz_123" should almost certainly miss.
97        assert!(!bloom.contains("nonexistent_unique_xyz_123_!@#"));
98    }
99
100    #[test]
101    fn serialization() {
102        let mut bloom = BloomFilter::for_expected(50, 0.01);
103        bloom.insert("alpha");
104        bloom.insert("beta");
105        let bytes = bloom.to_bytes();
106        let restored = BloomFilter::from_bytes(&bytes).expect("decode bloom");
107        assert!(restored.contains("alpha"));
108        assert!(restored.contains("beta"));
109    }
110}
tessera_codegraph/bloom.rs

tessera_codegraph/
bloom.rs
