orinium_browser/engine/layouter/
match_cache.rs

1//! Epoch-scoped cache of CSS selector match results.
2//!
3//! Selector matching is the dominant per-element cost after the rule set has
4//! been built: every layout run walks the candidate rules of every element and
5//! runs `ComplexSelector::matches` again, even though the result only depends on
6//! the (immutable) DOM snapshot and the (immutable) rule set. Repeated layout
7//! runs over an unchanged document — scroll, resize, hover and animation frames
8//! — therefore repeat exactly the same matches.
9//!
10//! [`SelectorMatchCache`] memoizes `(selector, element)` pairs. The key is the
11//! identity of the [`ComplexSelector`] allocation ([`Arc::as_ptr`]) rather than
12//! the selector text: rules sharing a selector group share one `Arc`, so the
13//! pointer is stable for as long as the owning [`RuleSet`] is reused, and this
14//! avoids hashing selector trees on every lookup.
15//!
16//! ## Invalidation contract
17//!
18//! The cache is scoped to one DOM-snapshot/rule-set/interaction epoch.
19//! [`SelectorMatchCache::clear`] MUST be called whenever any input that can
20//! affect selector matching changes:
21//!
22//! - The rule set is rebuilt (new selector allocations).
23//! - The DOM snapshot changes (`dom_version` bumps): structural changes,
24//!   attribute changes, pseudo-class state changes (:checked, :focus, etc.).
25//! - Interaction state changes (`interaction_version` bumps): :hover, :active,
26//!   :focus-within, etc.
27//!
28//! Entries carry the epoch they were created in. [`SelectorMatchCache::get_or_insert`]
29//! returns a miss for entries from a previous epoch, so even if `clear` is
30//! accidentally skipped, stale entries are never reused. `clear` also drops the
31//! backing map to bound memory growth.
32//!
33//! [`SelectorMatchCache`] is single-threaded: it is owned by a layout worker
34//! and accessed only from that worker's thread.
35
36use std::collections::HashMap;
37use std::sync::Arc;
38
39use super::dom_snapshot::NodeId;
40use crate::engine::cache_stats::{CacheStats, CacheStatsSnapshot};
41use crate::engine::css::parser::ComplexSelector;
42
43/// Default number of memoized `(selector, element)` results.
44// Entries are a pointer, a node id, a boolean and an epoch, so this bounds
45// the cache at a few megabytes even for very large documents.
46pub const DEFAULT_CAPACITY: usize = 131_072;
47
48/// `(selector allocation, element)` identity of one cached match result.
49type MatchKey = (usize, NodeId);
50
51/// Memoizes selector match results for one DOM/rule-set epoch.
52// Uses an epoch-scoped `HashMap` with an admission cap rather than an LRU.
53// Once the cache reaches `capacity`, new entries are not inserted and the
54// lookup is recorded as a skip so we can distinguish capacity pressure from
55// cache misses that could be served by the map.
56// Each entry stores the epoch it was created in. [`clear`] bumps the epoch,
57// making all existing entries stale. [`get_or_insert`] treats entries from a
58// previous epoch as misses, so stale results are never reused even if
59// [`clear`] is inadvertently skipped. [`clear`] also empties the map to bound
60// memory growth from stale entries.
61pub struct SelectorMatchCache {
62    entries: HashMap<MatchKey, (bool, u64)>,
63    epoch: u64,
64    capacity: usize,
65    stats: CacheStats,
66}
67
68impl Default for SelectorMatchCache {
69    fn default() -> Self {
70        Self::new()
71    }
72}
73
74impl SelectorMatchCache {
75    pub fn new() -> Self {
76        Self::with_capacity(DEFAULT_CAPACITY)
77    }
78
79    pub fn with_capacity(capacity: usize) -> Self {
80        let capacity = capacity.max(1);
81        Self {
82            entries: HashMap::with_capacity(capacity.min(4096)),
83            epoch: 0,
84            capacity,
85            stats: CacheStats::new("selector_match"),
86        }
87    }
88
89    /// Returns the cached match result for `selector` against `node_id`,
90    /// computing and storing it with `compute` on a miss.
91    ///
92    /// Entries from a previous epoch are treated as misses: they are never
93    /// returned, even if they happen to still be in the map.
94    pub fn get_or_insert(
95        &mut self,
96        selector: &Arc<ComplexSelector>,
97        node_id: NodeId,
98        compute: impl FnOnce() -> bool,
99    ) -> bool {
100        let key = (Arc::as_ptr(selector) as usize, node_id);
101        if let Some(&(matched, entry_epoch)) = self.entries.get(&key)
102            && entry_epoch == self.epoch
103        {
104            self.stats.record_hit();
105            return matched;
106        }
107        // Stale entry from a previous epoch: fall through to recompute.
108
109        self.stats.record_miss();
110        let matched = compute();
111        if self.entries.len() < self.capacity {
112            self.entries.insert(key, (matched, self.epoch));
113        } else {
114            self.stats.record_skip();
115        }
116        matched
117    }
118
119    /// Drops every entry and bumps the epoch. Call when the DOM snapshot or
120    /// the rule set changes.
121    ///
122    /// After this call, all previously cached results are stale: [`get_or_insert`]
123    /// will treat them as misses because their epoch no longer matches.
124    pub fn clear(&mut self) {
125        self.entries.clear();
126        self.epoch = self.epoch.wrapping_add(1);
127        self.stats.reset();
128    }
129
130    pub fn len(&self) -> usize {
131        self.entries.len()
132    }
133
134    pub fn is_empty(&self) -> bool {
135        self.entries.is_empty()
136    }
137
138    pub fn capacity(&self) -> usize {
139        self.capacity
140    }
141
142    pub fn stats(&self) -> CacheStatsSnapshot {
143        self.stats.snapshot()
144    }
145}
146
147#[cfg(test)]
148mod tests {
149    use super::*;
150
151    fn selector() -> Arc<ComplexSelector> {
152        Arc::new(ComplexSelector { parts: Vec::new() })
153    }
154
155    #[test]
156    fn a_second_lookup_reuses_the_stored_result() {
157        let mut cache = SelectorMatchCache::new();
158        let selector = selector();
159        let mut computed = 0;
160
161        let first = cache.get_or_insert(&selector, 7, || {
162            computed += 1;
163            true
164        });
165        let second = cache.get_or_insert(&selector, 7, || {
166            computed += 1;
167            false
168        });
169
170        assert!(first);
171        assert!(second, "the cached result must win over the recomputation");
172        assert_eq!(computed, 1);
173        let stats = cache.stats();
174        assert_eq!(
175            (stats.hits, stats.misses, stats.evictions, stats.skips),
176            (1, 1, 0, 0)
177        );
178    }
179
180    #[test]
181    fn elements_and_selectors_are_distinct_keys() {
182        let mut cache = SelectorMatchCache::new();
183        let first_selector = selector();
184        let second_selector = selector();
185        let mut computed = 0;
186
187        cache.get_or_insert(&first_selector, 1, || {
188            computed += 1;
189            true
190        });
191        cache.get_or_insert(&first_selector, 2, || {
192            computed += 1;
193            false
194        });
195        cache.get_or_insert(&second_selector, 1, || {
196            computed += 1;
197            false
198        });
199
200        assert_eq!(computed, 3);
201        let stats = cache.stats();
202        assert_eq!(
203            (stats.hits, stats.misses, stats.evictions, stats.skips),
204            (0, 3, 0, 0)
205        );
206    }
207
208    #[test]
209    fn capacity_pressure_skips_without_eviction() {
210        let mut cache = SelectorMatchCache::with_capacity(1);
211        let first_selector = selector();
212        let second_selector = selector();
213
214        cache.get_or_insert(&first_selector, 1, || true);
215        cache.get_or_insert(&second_selector, 1, || true);
216
217        assert_eq!(cache.len(), 1);
218        let stats = cache.stats();
219        assert_eq!(stats.evictions, 0);
220        assert_eq!(stats.skips, 1);
221        assert_eq!(stats.hits, 0);
222
223        // Existing entries remain cached.
224        let mut computed = 0;
225        let matched = cache.get_or_insert(&first_selector, 1, || {
226            computed += 1;
227            false
228        });
229        assert!(matched);
230        assert_eq!(computed, 0);
231        assert_eq!(cache.stats().hits, 1);
232    }
233
234    #[test]
235    fn over_capacity_passes_hit_in_the_second_epoch_like_pass() {
236        let mut cache = SelectorMatchCache::with_capacity(4);
237        let selectors: Vec<Arc<ComplexSelector>> = (0..6)
238            .map(|_| Arc::new(ComplexSelector { parts: Vec::new() }))
239            .collect();
240        let mut computed = 0;
241
242        // First pass fills the cache and skips beyond capacity.
243        for sel in &selectors {
244            cache.get_or_insert(sel, 1, || {
245                computed += 1;
246                true
247            });
248        }
249        assert_eq!(cache.len(), 4);
250        let first = cache.stats();
251        assert_eq!(first.misses, 6);
252        assert_eq!(first.skips, 2);
253        assert_eq!(first.evictions, 0);
254        assert_eq!(computed, 6);
255
256        // Second pass over the same keys: entries inserted in pass 1 must hit.
257        // Keys beyond capacity were never stored, so they miss again.
258        for sel in &selectors {
259            cache.get_or_insert(sel, 1, || {
260                computed += 1;
261                false
262            });
263        }
264        let second = cache.stats();
265        assert_eq!(second.misses, 8);
266        assert_eq!(second.hits, 4);
267        assert_eq!(second.skips, 4);
268        assert_eq!(computed, 8);
269    }
270
271    #[test]
272    fn clear_drops_entries_and_resets_counters() {
273        let mut cache = SelectorMatchCache::new();
274        let selector = selector();
275        cache.get_or_insert(&selector, 1, || true);
276        cache.clear();
277
278        assert!(cache.is_empty());
279        let stats = cache.stats();
280        assert_eq!(stats.misses, 0);
281        assert_eq!(stats.hits, 0);
282        assert_eq!(stats.evictions, 0);
283        assert_eq!(stats.skips, 0);
284    }
285
286    #[test]
287    fn clear_bumps_epoch_so_stale_entries_are_not_reused() {
288        let mut cache = SelectorMatchCache::new();
289        let selector = selector();
290
291        // First epoch: cache stores `true`.
292        let first = cache.get_or_insert(&selector, 1, || true);
293        assert!(first);
294
295        // Bump the epoch without clearing the map (simulates a missed clear).
296        cache.epoch = cache.epoch.wrapping_add(1);
297
298        // The old entry is still in the map but must be treated as a miss.
299        let second = cache.get_or_insert(&selector, 1, || false);
300        assert!(!second, "stale epoch entry must not be reused");
301
302        // Stats should show two misses (both lookups were misses due to epoch mismatch).
303        let stats = cache.stats();
304        assert_eq!(stats.misses, 2);
305        assert_eq!(stats.hits, 0);
306    }
307
308    #[test]
309    fn epoch_rollover_does_not_break_cache() {
310        let mut cache = SelectorMatchCache::new();
311        let selector = selector();
312
313        // Bump epoch many times to test wraparound behavior.
314        for _ in 0..10_000 {
315            cache.epoch = cache.epoch.wrapping_add(1);
316            cache.get_or_insert(&selector, 1, || true);
317            cache.clear();
318        }
319
320        assert!(cache.is_empty());
321    }
322}
orinium_browser/engine/layouter/match_cache.rs

orinium_browser/engine/layouter/
match_cache.rs
