oxirs_tdb/
triple_cache.rs

1//! Triple pattern cache: memoize repeated triple pattern lookups using LRU eviction.
2//!
3//! This module caches the results of triple pattern queries (where any component
4//! may be a wildcard) using an LRU cache keyed by the pattern.  It also supports
5//! cache invalidation when a specific triple is written so that stale results
6//! are not served.
7
8use std::collections::HashMap;
9
10// ---------------------------------------------------------------------------
11// Data types
12// ---------------------------------------------------------------------------
13
14/// A triple pattern where `None` represents a wildcard.
15#[derive(Debug, Clone, PartialEq, Eq, Hash)]
16pub struct TriplePattern {
17    /// Subject IRI or blank node — `None` = match any.
18    pub subject: Option<String>,
19    /// Predicate IRI — `None` = match any.
20    pub predicate: Option<String>,
21    /// Object value — `None` = match any.
22    pub object: Option<String>,
23}
24
25impl TriplePattern {
26    /// Create a new triple pattern.
27    pub fn new(subject: Option<String>, predicate: Option<String>, object: Option<String>) -> Self {
28        Self {
29            subject,
30            predicate,
31            object,
32        }
33    }
34
35    /// Create a fully-bound pattern (no wildcards).
36    pub fn bound(s: &str, p: &str, o: &str) -> Self {
37        Self {
38            subject: Some(s.to_string()),
39            predicate: Some(p.to_string()),
40            object: Some(o.to_string()),
41        }
42    }
43
44    /// Create a subject-bound pattern (S ? ?).
45    pub fn for_subject(s: &str) -> Self {
46        Self {
47            subject: Some(s.to_string()),
48            predicate: None,
49            object: None,
50        }
51    }
52
53    /// Create a fully wildcard pattern (? ? ?).
54    pub fn wildcard() -> Self {
55        Self {
56            subject: None,
57            predicate: None,
58            object: None,
59        }
60    }
61
62    /// Return `true` if this pattern could match the given concrete triple.
63    ///
64    /// A pattern component matches when it is `None` (wildcard) or equals the
65    /// corresponding triple component.
66    pub fn matches(&self, s: &str, p: &str, o: &str) -> bool {
67        self.subject.as_deref().map_or(true, |ps| ps == s)
68            && self.predicate.as_deref().map_or(true, |pp| pp == p)
69            && self.object.as_deref().map_or(true, |po| po == o)
70    }
71}
72
73/// A cache key derived from a `TriplePattern` (same structure, implements Hash+Eq
74/// through the derived `TriplePattern` impls).
75pub type CacheKey = TriplePattern;
76
77// ---------------------------------------------------------------------------
78// CacheEntry
79// ---------------------------------------------------------------------------
80
81/// One entry in the triple cache.
82#[derive(Debug, Clone)]
83pub struct CacheEntry {
84    /// The cached query results: (subject, predicate, object) triples.
85    pub results: Vec<(String, String, String)>,
86    /// How many times this entry has been retrieved.
87    pub hit_count: usize,
88    /// Monotonic timestamp of last access (supplied by the caller).
89    pub last_accessed: u64,
90}
91
92// ---------------------------------------------------------------------------
93// CacheStats
94// ---------------------------------------------------------------------------
95
96/// Aggregate cache statistics.
97#[derive(Debug, Clone, Default)]
98pub struct CacheStats {
99    /// Number of cache hits.
100    pub hits: u64,
101    /// Number of cache misses.
102    pub misses: u64,
103    /// Number of entries evicted (LRU).
104    pub evictions: u64,
105    /// Current number of entries in the cache.
106    pub size: usize,
107}
108
109// ---------------------------------------------------------------------------
110// TripleCache
111// ---------------------------------------------------------------------------
112
113/// An LRU cache for triple pattern query results.
114pub struct TripleCache {
115    store: HashMap<CacheKey, CacheEntry>,
116    capacity: usize,
117    stats: CacheStats,
118}
119
120impl TripleCache {
121    /// Create a new cache with the given maximum capacity (number of entries).
122    pub fn new(capacity: usize) -> Self {
123        Self {
124            store: HashMap::new(),
125            capacity,
126            stats: CacheStats::default(),
127        }
128    }
129
130    // -----------------------------------------------------------------------
131    // Core operations
132    // -----------------------------------------------------------------------
133
134    /// Look up a cached result for `pattern`.
135    ///
136    /// Returns a reference to the result list on a hit, or `None` on a miss.
137    /// Updates `hit_count`, `last_accessed`, and cache statistics.
138    pub fn get(
139        &mut self,
140        pattern: &TriplePattern,
141        now: u64,
142    ) -> Option<&Vec<(String, String, String)>> {
143        if let Some(entry) = self.store.get_mut(pattern) {
144            entry.hit_count += 1;
145            entry.last_accessed = now;
146            self.stats.hits += 1;
147            // Re-borrow immutably to return the reference.
148            return Some(&self.store[pattern].results);
149        }
150        self.stats.misses += 1;
151        None
152    }
153
154    /// Store a result for `pattern`.
155    ///
156    /// If the cache is at capacity, the LRU entry (smallest `last_accessed`)
157    /// is evicted before inserting the new entry.
158    pub fn put(
159        &mut self,
160        pattern: TriplePattern,
161        results: Vec<(String, String, String)>,
162        now: u64,
163    ) {
164        // Evict if at capacity (and the pattern is not already present).
165        if !self.store.contains_key(&pattern) && self.store.len() >= self.capacity {
166            self.evict_lru();
167        }
168
169        let entry = CacheEntry {
170            results,
171            hit_count: 0,
172            last_accessed: now,
173        };
174        self.store.insert(pattern, entry);
175        self.stats.size = self.store.len();
176    }
177
178    /// Invalidate all cached entries whose pattern *could* match the concrete
179    /// triple (s, p, o).
180    ///
181    /// A cached pattern must be removed if querying it again after the
182    /// insertion of (s,p,o) might yield a different result set.
183    pub fn invalidate_matching(&mut self, s: &str, p: &str, o: &str) {
184        self.store.retain(|pattern, _| !pattern.matches(s, p, o));
185        self.stats.size = self.store.len();
186    }
187
188    // -----------------------------------------------------------------------
189    // Accessors
190    // -----------------------------------------------------------------------
191
192    /// Return a reference to the current cache statistics.
193    pub fn stats(&self) -> &CacheStats {
194        &self.stats
195    }
196
197    /// Return the current number of cached entries.
198    pub fn len(&self) -> usize {
199        self.store.len()
200    }
201
202    /// Return `true` when the cache contains no entries.
203    pub fn is_empty(&self) -> bool {
204        self.store.is_empty()
205    }
206
207    /// Remove all entries from the cache.
208    pub fn clear(&mut self) {
209        self.store.clear();
210        self.stats.size = 0;
211    }
212
213    // -----------------------------------------------------------------------
214    // Internal helpers
215    // -----------------------------------------------------------------------
216
217    fn evict_lru(&mut self) {
218        if self.store.is_empty() {
219            return;
220        }
221        // Find the key with the smallest `last_accessed` timestamp.
222        let lru_key = self
223            .store
224            .iter()
225            .min_by_key(|(_, entry)| entry.last_accessed)
226            .map(|(k, _)| k.clone());
227
228        if let Some(key) = lru_key {
229            self.store.remove(&key);
230            self.stats.evictions += 1;
231        }
232    }
233}
234
235// ---------------------------------------------------------------------------
236// Tests
237// ---------------------------------------------------------------------------
238
239#[cfg(test)]
240mod tests {
241    use super::*;
242
243    fn triple(s: &str, p: &str, o: &str) -> (String, String, String) {
244        (s.to_string(), p.to_string(), o.to_string())
245    }
246
247    fn pattern_sp(s: &str, p: &str) -> TriplePattern {
248        TriplePattern::new(Some(s.to_string()), Some(p.to_string()), None)
249    }
250
251    // -----------------------------------------------------------------------
252    // TriplePattern::matches
253    // -----------------------------------------------------------------------
254
255    #[test]
256    fn test_pattern_matches_wildcard() {
257        let p = TriplePattern::wildcard();
258        assert!(p.matches("s", "p", "o"));
259    }
260
261    #[test]
262    fn test_pattern_matches_bound_exact() {
263        let p = TriplePattern::bound("s", "p", "o");
264        assert!(p.matches("s", "p", "o"));
265        assert!(!p.matches("s2", "p", "o"));
266    }
267
268    #[test]
269    fn test_pattern_matches_subject_bound() {
270        let p = TriplePattern::for_subject("Alice");
271        assert!(p.matches("Alice", "knows", "Bob"));
272        assert!(!p.matches("Bob", "knows", "Alice"));
273    }
274
275    #[test]
276    fn test_pattern_matches_partial_wildcard() {
277        let p = pattern_sp(":Alice", ":knows");
278        assert!(p.matches(":Alice", ":knows", ":Bob"));
279        assert!(p.matches(":Alice", ":knows", ":Carol"));
280        assert!(!p.matches(":Alice", ":likes", ":Bob"));
281    }
282
283    // -----------------------------------------------------------------------
284    // Basic get/put
285    // -----------------------------------------------------------------------
286
287    #[test]
288    fn test_cache_miss() {
289        let mut cache = TripleCache::new(10);
290        let p = TriplePattern::wildcard();
291        assert!(cache.get(&p, 1).is_none());
292        assert_eq!(cache.stats().misses, 1);
293    }
294
295    #[test]
296    fn test_cache_hit_after_put() {
297        let mut cache = TripleCache::new(10);
298        let p = TriplePattern::for_subject("Alice");
299        let results = vec![triple(":Alice", ":knows", ":Bob")];
300        cache.put(p.clone(), results.clone(), 1);
301        let got = cache.get(&p, 2);
302        assert!(got.is_some());
303        assert_eq!(got.unwrap(), &results);
304        assert_eq!(cache.stats().hits, 1);
305    }
306
307    #[test]
308    fn test_cache_size_after_put() {
309        let mut cache = TripleCache::new(10);
310        assert_eq!(cache.len(), 0);
311        cache.put(TriplePattern::wildcard(), vec![], 1);
312        assert_eq!(cache.len(), 1);
313    }
314
315    #[test]
316    fn test_cache_is_empty() {
317        let cache = TripleCache::new(5);
318        assert!(cache.is_empty());
319    }
320
321    #[test]
322    fn test_cache_put_updates_existing() {
323        let mut cache = TripleCache::new(5);
324        let p = TriplePattern::for_subject("X");
325        cache.put(p.clone(), vec![triple("X", "p", "o1")], 1);
326        cache.put(p.clone(), vec![triple("X", "p", "o2")], 2);
327        let got = cache.get(&p, 3).unwrap();
328        assert_eq!(got.len(), 1);
329        // Second put overwrites
330        assert_eq!(got[0].2, "o2");
331        // Only 1 distinct key
332        assert_eq!(cache.len(), 1);
333    }
334
335    // -----------------------------------------------------------------------
336    // LRU eviction
337    // -----------------------------------------------------------------------
338
339    #[test]
340    fn test_lru_eviction_on_capacity() {
341        let mut cache = TripleCache::new(3);
342        let p1 = TriplePattern::for_subject("A");
343        let p2 = TriplePattern::for_subject("B");
344        let p3 = TriplePattern::for_subject("C");
345        let p4 = TriplePattern::for_subject("D");
346
347        cache.put(p1.clone(), vec![], 1);
348        cache.put(p2.clone(), vec![], 2);
349        cache.put(p3.clone(), vec![], 3);
350        // p1 has the smallest timestamp → should be evicted
351        cache.put(p4.clone(), vec![], 4);
352
353        assert_eq!(cache.len(), 3);
354        assert_eq!(cache.stats().evictions, 1);
355        // p1 should be gone
356        assert!(cache.get(&p1, 5).is_none());
357        // p4 should be present
358        assert!(cache.get(&p4, 6).is_some());
359    }
360
361    #[test]
362    fn test_lru_eviction_respects_access_time() {
363        let mut cache = TripleCache::new(2);
364        let p1 = TriplePattern::for_subject("A");
365        let p2 = TriplePattern::for_subject("B");
366        let p3 = TriplePattern::for_subject("C");
367
368        cache.put(p1.clone(), vec![], 1);
369        cache.put(p2.clone(), vec![], 2);
370        // Access p1 to refresh its timestamp
371        cache.get(&p1, 10);
372        // Now insert p3 — p2 (last_accessed=2) should be evicted, not p1 (last_accessed=10)
373        cache.put(p3.clone(), vec![], 3);
374
375        assert!(cache.get(&p1, 11).is_some());
376        assert!(cache.get(&p3, 12).is_some());
377        // p2 was the LRU
378        assert!(cache.get(&p2, 13).is_none());
379    }
380
381    // -----------------------------------------------------------------------
382    // Invalidation
383    // -----------------------------------------------------------------------
384
385    #[test]
386    fn test_invalidate_bound_pattern() {
387        let mut cache = TripleCache::new(10);
388        let p = TriplePattern::bound(":Alice", ":knows", ":Bob");
389        cache.put(p.clone(), vec![triple(":Alice", ":knows", ":Bob")], 1);
390        cache.invalidate_matching(":Alice", ":knows", ":Bob");
391        assert!(cache.get(&p, 2).is_none());
392    }
393
394    #[test]
395    fn test_invalidate_wildcard_pattern_removes_all() {
396        let mut cache = TripleCache::new(10);
397        cache.put(TriplePattern::for_subject("A"), vec![], 1);
398        cache.put(TriplePattern::for_subject("B"), vec![], 2);
399        cache.put(TriplePattern::wildcard(), vec![], 3);
400        // Wildcard pattern matches any triple → removed on any invalidation
401        cache.invalidate_matching("A", "p", "o");
402        // wildcard should be gone; "B" may remain (only if pattern doesn't match)
403        assert!(cache.get(&TriplePattern::wildcard(), 4).is_none());
404    }
405
406    #[test]
407    fn test_invalidate_non_matching_pattern_not_removed() {
408        let mut cache = TripleCache::new(10);
409        let p = TriplePattern::for_subject("Bob");
410        cache.put(p.clone(), vec![triple("Bob", "age", "30")], 1);
411        // Invalidate a triple about Alice — should not affect Bob's pattern
412        cache.invalidate_matching("Alice", "knows", "Carol");
413        assert!(cache.get(&p, 2).is_some());
414    }
415
416    #[test]
417    fn test_invalidate_updates_stats_size() {
418        let mut cache = TripleCache::new(10);
419        cache.put(TriplePattern::bound("s", "p", "o"), vec![], 1);
420        assert_eq!(cache.stats().size, 1);
421        cache.invalidate_matching("s", "p", "o");
422        assert_eq!(cache.stats().size, 0);
423    }
424
425    // -----------------------------------------------------------------------
426    // Statistics
427    // -----------------------------------------------------------------------
428
429    #[test]
430    fn test_stats_hits_and_misses() {
431        let mut cache = TripleCache::new(10);
432        let p = TriplePattern::wildcard();
433        cache.get(&p, 1); // miss
434        cache.put(p.clone(), vec![], 2);
435        cache.get(&p, 3); // hit
436        cache.get(&p, 4); // hit
437        assert_eq!(cache.stats().misses, 1);
438        assert_eq!(cache.stats().hits, 2);
439    }
440
441    #[test]
442    fn test_stats_eviction_count() {
443        let mut cache = TripleCache::new(2);
444        cache.put(TriplePattern::for_subject("A"), vec![], 1);
445        cache.put(TriplePattern::for_subject("B"), vec![], 2);
446        cache.put(TriplePattern::for_subject("C"), vec![], 3); // evict A
447        cache.put(TriplePattern::for_subject("D"), vec![], 4); // evict B
448        assert_eq!(cache.stats().evictions, 2);
449    }
450
451    // -----------------------------------------------------------------------
452    // Clear
453    // -----------------------------------------------------------------------
454
455    #[test]
456    fn test_clear_empties_cache() {
457        let mut cache = TripleCache::new(10);
458        cache.put(TriplePattern::wildcard(), vec![], 1);
459        cache.put(TriplePattern::for_subject("X"), vec![], 2);
460        cache.clear();
461        assert!(cache.is_empty());
462        assert_eq!(cache.stats().size, 0);
463    }
464
465    #[test]
466    fn test_clear_then_reuse() {
467        let mut cache = TripleCache::new(5);
468        cache.put(TriplePattern::for_subject("A"), vec![], 1);
469        cache.clear();
470        let p = TriplePattern::for_subject("B");
471        cache.put(p.clone(), vec![triple("B", "p", "o")], 2);
472        assert!(cache.get(&p, 3).is_some());
473    }
474
475    // -----------------------------------------------------------------------
476    // Edge cases
477    // -----------------------------------------------------------------------
478
479    #[test]
480    fn test_capacity_one() {
481        let mut cache = TripleCache::new(1);
482        let p1 = TriplePattern::for_subject("A");
483        let p2 = TriplePattern::for_subject("B");
484        cache.put(p1.clone(), vec![], 1);
485        cache.put(p2.clone(), vec![], 2); // evicts p1
486        assert!(cache.get(&p1, 3).is_none());
487        assert!(cache.get(&p2, 4).is_some());
488    }
489
490    #[test]
491    fn test_empty_results_cached() {
492        let mut cache = TripleCache::new(5);
493        let p = TriplePattern::wildcard();
494        cache.put(p.clone(), vec![], 1);
495        let got = cache.get(&p, 2);
496        assert!(got.is_some());
497        assert!(got.unwrap().is_empty());
498    }
499}
oxirs_tdb/triple_cache.rs

oxirs_tdb/
triple_cache.rs
