termivar_scanner/
cache.rs

1//! Bounded in-memory cache.
2//!
3//! ## Runtime scope
4//!
5//! - **Build:** opt-in via `platform-models`.
6//! - **Execution:** host/library only; no repository runtime caller.
7//! - **Default `termivar scan`:** no.
8//! - **Support:** experimental/scaffold.
9//!
10//! See `docs/internals/runtime-map.md`.
11//!
12//! [`LruCache`] provides process-local TTL storage with true access-recency
13//! eviction. TTL uses a monotonic clock; recency uses a sequence allocated
14//! while the cache lock is held. This module does
15//! not cache HTTP responses because a URL alone cannot identify authorization,
16//! cookies, headers, request body, or other response-varying context safely.
17
18use std::collections::HashMap;
19use std::hash::Hash;
20use std::sync::atomic::{AtomicU64, Ordering};
21use std::sync::{Arc, Mutex, PoisonError};
22use std::time::{Duration, Instant};
23
24trait Clock: Send + Sync {
25    fn now(&self) -> Duration;
26}
27
28struct SystemClock {
29    origin: Instant,
30}
31
32impl SystemClock {
33    fn new() -> Self {
34        Self {
35            origin: Instant::now(),
36        }
37    }
38}
39
40impl Clock for SystemClock {
41    fn now(&self) -> Duration {
42        self.origin.elapsed()
43    }
44}
45
46struct CacheEntry<T> {
47    value: T,
48    created_at: Duration,
49    last_access_sequence: u128,
50    ttl: Duration,
51}
52
53impl<T> CacheEntry<T> {
54    fn new(value: T, ttl: Duration, now: Duration, access_sequence: u128) -> Self {
55        Self {
56            value,
57            created_at: now,
58            last_access_sequence: access_sequence,
59            ttl,
60        }
61    }
62
63    fn is_expired_at(&self, now: Duration) -> bool {
64        now.saturating_sub(self.created_at) >= self.ttl
65    }
66}
67
68struct CacheState<K, V> {
69    entries: HashMap<K, CacheEntry<V>>,
70    next_access_sequence: u128,
71}
72
73impl<K, V> Default for CacheState<K, V> {
74    fn default() -> Self {
75        Self {
76            entries: HashMap::new(),
77            next_access_sequence: 0,
78        }
79    }
80}
81
82impl<K, V> CacheState<K, V> {
83    fn allocate_access_sequence(&mut self) -> u128 {
84        if self.next_access_sequence == u128::MAX {
85            let mut entries: Vec<_> = self.entries.values_mut().collect();
86            entries.sort_by_key(|entry| entry.last_access_sequence);
87            for (sequence, entry) in entries.into_iter().enumerate() {
88                entry.last_access_sequence = sequence as u128;
89            }
90            self.next_access_sequence = self.entries.len() as u128;
91        }
92        let sequence = self.next_access_sequence;
93        self.next_access_sequence += 1;
94        sequence
95    }
96}
97
98/// A process-local, bounded least-recently-used cache with TTL expiration.
99pub struct LruCache<K, V> {
100    cache: Mutex<CacheState<K, V>>,
101    max_size: usize,
102    hits: AtomicU64,
103    misses: AtomicU64,
104    clock: Arc<dyn Clock>,
105}
106
107impl<K: Eq + Hash + Clone, V: Clone> LruCache<K, V> {
108    /// Creates an empty cache using a monotonic process clock.
109    #[must_use]
110    pub fn new(max_size: usize) -> Self {
111        Self::with_clock(max_size, Arc::new(SystemClock::new()))
112    }
113
114    fn with_clock(max_size: usize, clock: Arc<dyn Clock>) -> Self {
115        Self {
116            cache: Mutex::new(CacheState::default()),
117            max_size,
118            hits: AtomicU64::new(0),
119            misses: AtomicU64::new(0),
120            clock,
121        }
122    }
123
124    /// Inserts or replaces a value with a TTL measured from this call.
125    pub fn insert(&self, key: K, value: V, ttl_secs: u64) {
126        if self.max_size == 0 {
127            return;
128        }
129
130        let mut state = self.cache.lock().unwrap_or_else(PoisonError::into_inner);
131        let now = self.clock.now();
132        if !state.entries.contains_key(&key) && state.entries.len() >= self.max_size {
133            let eviction_key = state
134                .entries
135                .iter()
136                .min_by_key(|(_, entry)| entry.last_access_sequence)
137                .map(|(key, _)| key.clone());
138            if let Some(eviction_key) = eviction_key {
139                state.entries.remove(&eviction_key);
140            }
141        }
142
143        let access_sequence = state.allocate_access_sequence();
144        state.entries.insert(
145            key,
146            CacheEntry::new(value, Duration::from_secs(ttl_secs), now, access_sequence),
147        );
148    }
149
150    /// Returns an unexpired value and records this lookup as the latest access.
151    pub fn get(&self, key: &K) -> Option<V> {
152        let mut state = self.cache.lock().unwrap_or_else(PoisonError::into_inner);
153        let now = self.clock.now();
154
155        let expired = state
156            .entries
157            .get(key)
158            .is_some_and(|entry| entry.is_expired_at(now));
159        if expired {
160            state.entries.remove(key);
161            increment(&self.misses);
162            return None;
163        }
164
165        if let Some(value) = state.entries.get(key).map(|entry| entry.value.clone()) {
166            let access_sequence = state.allocate_access_sequence();
167            if let Some(entry) = state.entries.get_mut(key) {
168                entry.last_access_sequence = access_sequence;
169            }
170            increment(&self.hits);
171            Some(value)
172        } else {
173            increment(&self.misses);
174            None
175        }
176    }
177
178    /// Removes a key.
179    pub fn remove(&self, key: &K) -> bool {
180        self.cache
181            .lock()
182            .unwrap_or_else(PoisonError::into_inner)
183            .entries
184            .remove(key)
185            .is_some()
186    }
187
188    /// Clears all entries without changing accumulated statistics.
189    pub fn clear(&self) {
190        self.cache
191            .lock()
192            .unwrap_or_else(PoisonError::into_inner)
193            .entries
194            .clear();
195    }
196
197    /// Returns a point-in-time statistics snapshot.
198    #[must_use]
199    pub fn stats(&self) -> CacheStats {
200        let hits = self.hits.load(Ordering::Relaxed);
201        let misses = self.misses.load(Ordering::Relaxed);
202        let total = hits.saturating_add(misses);
203        let size = self
204            .cache
205            .lock()
206            .unwrap_or_else(PoisonError::into_inner)
207            .entries
208            .len();
209
210        CacheStats {
211            hits,
212            misses,
213            hit_rate: if total == 0 {
214                0.0
215            } else {
216                (hits as f64 / total as f64) * 100.0
217            },
218            size,
219            max_size: self.max_size,
220        }
221    }
222}
223
224fn increment(counter: &AtomicU64) {
225    // Preserve the successful RMW even when saturation leaves the value unchanged.
226    let mut current = counter.load(Ordering::Relaxed);
227    loop {
228        match counter.compare_exchange_weak(
229            current,
230            current.saturating_add(1),
231            Ordering::Relaxed,
232            Ordering::Relaxed,
233        ) {
234            Ok(_) => return,
235            Err(observed) => current = observed,
236        }
237    }
238}
239
240/// Cache statistics snapshot.
241#[derive(Debug, Clone, PartialEq)]
242pub struct CacheStats {
243    pub hits: u64,
244    pub misses: u64,
245    pub hit_rate: f64,
246    pub size: usize,
247    pub max_size: usize,
248}
249
250#[cfg(test)]
251mod tests {
252    use super::*;
253
254    #[test]
255    fn atomic_saturating_cache_increment_preserves_zero_max_and_concurrent_updates() {
256        let counter = AtomicU64::new(0);
257        increment(&counter);
258        assert_eq!(counter.load(Ordering::Relaxed), 1);
259        counter.store(u64::MAX - 1, Ordering::Relaxed);
260        increment(&counter);
261        increment(&counter);
262        assert_eq!(counter.load(Ordering::Relaxed), u64::MAX);
263
264        counter.store(0, Ordering::Relaxed);
265        std::thread::scope(|scope| {
266            for _ in 0..4 {
267                scope.spawn(|| {
268                    for _ in 0..1000 {
269                        increment(&counter);
270                    }
271                });
272            }
273        });
274        assert_eq!(counter.load(Ordering::Relaxed), 4000);
275    }
276
277    #[derive(Default)]
278    struct TestClock {
279        seconds: AtomicU64,
280    }
281
282    impl TestClock {
283        fn set(&self, seconds: u64) {
284            self.seconds.store(seconds, Ordering::Relaxed);
285        }
286
287        fn advance(&self, seconds: u64) {
288            self.seconds.fetch_add(seconds, Ordering::Relaxed);
289        }
290    }
291
292    impl Clock for TestClock {
293        fn now(&self) -> Duration {
294            Duration::from_secs(self.seconds.load(Ordering::Relaxed))
295        }
296    }
297
298    fn cache_with_clock<K: Eq + Hash + Clone, V: Clone>(
299        max_size: usize,
300        clock: Arc<TestClock>,
301    ) -> LruCache<K, V> {
302        LruCache::with_clock(max_size, clock)
303    }
304
305    #[test]
306    fn ttl_expiration_uses_the_injected_monotonic_clock() {
307        let clock = Arc::new(TestClock::default());
308        let cache = cache_with_clock(1, Arc::clone(&clock));
309        cache.insert("key", "value", 10);
310
311        clock.advance(9);
312        assert_eq!(cache.get(&"key"), Some("value"));
313        clock.advance(1);
314        assert_eq!(cache.get(&"key"), None);
315    }
316
317    #[test]
318    fn backward_clock_values_do_not_underflow_or_expire_entries() {
319        let clock = Arc::new(TestClock::default());
320        clock.set(10);
321        let cache = cache_with_clock(1, Arc::clone(&clock));
322        cache.insert("key", "value", 5);
323
324        clock.set(1);
325        assert_eq!(cache.get(&"key"), Some("value"));
326    }
327
328    #[test]
329    fn successful_get_refreshes_lru_recency() {
330        let clock = Arc::new(TestClock::default());
331        let cache = cache_with_clock(2, Arc::clone(&clock));
332        cache.insert("first", "one", 100);
333        clock.advance(1);
334        cache.insert("second", "two", 100);
335        clock.advance(1);
336        assert_eq!(cache.get(&"first"), Some("one"));
337        clock.advance(1);
338        cache.insert("third", "three", 100);
339
340        assert_eq!(cache.get(&"second"), None);
341        assert_eq!(cache.get(&"first"), Some("one"));
342        assert_eq!(cache.get(&"third"), Some("three"));
343    }
344
345    #[test]
346    fn equal_clock_values_still_evict_by_serialized_access_order() {
347        let clock = Arc::new(TestClock::default());
348        let cache = cache_with_clock(2, clock);
349        cache.insert("first", "one", 100);
350        cache.insert("second", "two", 100);
351        assert_eq!(cache.get(&"first"), Some("one"));
352        cache.insert("third", "three", 100);
353
354        assert_eq!(cache.get(&"second"), None);
355        assert_eq!(cache.get(&"first"), Some("one"));
356        assert_eq!(cache.get(&"third"), Some("three"));
357    }
358
359    #[test]
360    fn replacing_an_existing_key_does_not_evict_another_entry() {
361        let clock = Arc::new(TestClock::default());
362        let cache = cache_with_clock(2, Arc::clone(&clock));
363        cache.insert("first", "one", 100);
364        clock.advance(1);
365        cache.insert("second", "two", 100);
366        clock.advance(1);
367        cache.insert("first", "updated", 100);
368
369        assert_eq!(cache.stats().size, 2);
370        assert_eq!(cache.get(&"first"), Some("updated"));
371        assert_eq!(cache.get(&"second"), Some("two"));
372    }
373
374    #[test]
375    fn zero_size_cache_stores_nothing_and_counts_a_miss() {
376        let cache = LruCache::new(0);
377        cache.insert(1, "value", 100);
378
379        assert_eq!(cache.get(&1), None);
380        assert_eq!(
381            cache.stats(),
382            CacheStats {
383                hits: 0,
384                misses: 1,
385                hit_rate: 0.0,
386                size: 0,
387                max_size: 0,
388            }
389        );
390    }
391
392    #[test]
393    fn remove_clear_and_stats_report_real_operations() {
394        let cache = LruCache::new(2);
395        cache.insert("first", "one", 100);
396        cache.insert("second", "two", 100);
397        assert_eq!(cache.get(&"first"), Some("one"));
398        assert!(cache.remove(&"second"));
399        assert!(!cache.remove(&"missing"));
400        cache.clear();
401
402        let stats = cache.stats();
403        assert_eq!(stats.hits, 1);
404        assert_eq!(stats.misses, 0);
405        assert_eq!(stats.hit_rate, 100.0);
406        assert_eq!(stats.size, 0);
407    }
408}
termivar_scanner/cache.rs

termivar_scanner/
cache.rs
