nautilus_common/cache/
fifo.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16//! Bounded FIFO caches for tracking IDs and key-value pairs with O(1) lookups.
17
18use std::{fmt::Debug, hash::Hash};
19
20use ahash::{AHashMap, AHashSet};
21use arraydeque::ArrayDeque;
22
23/// A bounded cache that maintains a set of IDs with O(1) lookups.
24///
25/// Uses an `ArrayDeque` for FIFO ordering and an `AHashSet` for fast membership checks.
26/// When capacity is exceeded, the oldest entry is automatically evicted.
27///
28/// # Examples
29///
30/// ```
31/// use nautilus_common::cache::fifo::FifoCache;
32///
33/// let mut cache: FifoCache<u32, 3> = FifoCache::new();
34/// cache.add(1);
35/// cache.add(2);
36/// cache.add(3);
37/// assert!(cache.contains(&1));
38///
39/// // Adding beyond capacity evicts the oldest
40/// cache.add(4);
41/// assert!(!cache.contains(&1));
42/// assert!(cache.contains(&4));
43/// ```
44///
45/// Zero capacity is a compile-time error:
46///
47/// ```compile_fail
48/// use nautilus_common::cache::fifo::FifoCache;
49///
50/// // This fails to compile: capacity must be > 0
51/// let cache: FifoCache<u32, 0> = FifoCache::new();
52/// ```
53///
54/// Default also enforces non-zero capacity:
55///
56/// ```compile_fail
57/// use nautilus_common::cache::fifo::FifoCache;
58///
59/// // This also fails to compile
60/// let cache: FifoCache<u32, 0> = FifoCache::default();
61/// ```
62#[derive(Debug)]
63pub struct FifoCache<T, const N: usize>
64where
65    T: Clone + Debug + Eq + Hash,
66{
67    order: ArrayDeque<T, N>,
68    index: AHashSet<T>,
69}
70
71impl<T, const N: usize> FifoCache<T, N>
72where
73    T: Clone + Debug + Eq + Hash,
74{
75    /// Creates a new empty [`FifoCache`] with capacity `N`.
76    ///
77    /// # Panics
78    ///
79    /// Compile-time panic if `N == 0`.
80    #[must_use]
81    pub fn new() -> Self {
82        const { assert!(N > 0, "FifoCache capacity must be greater than zero") };
83
84        Self {
85            order: ArrayDeque::new(),
86            index: AHashSet::with_capacity(N),
87        }
88    }
89
90    /// Returns the capacity of the cache.
91    #[must_use]
92    pub const fn capacity(&self) -> usize {
93        N
94    }
95
96    /// Returns the number of IDs in the cache.
97    #[must_use]
98    pub fn len(&self) -> usize {
99        self.index.len()
100    }
101
102    /// Returns whether the cache is empty.
103    #[must_use]
104    pub fn is_empty(&self) -> bool {
105        self.index.is_empty()
106    }
107
108    /// Returns whether the cache contains the given ID (O(1) lookup).
109    #[must_use]
110    pub fn contains(&self, id: &T) -> bool {
111        self.index.contains(id)
112    }
113
114    /// Adds an ID to the cache.
115    ///
116    /// If the ID already exists, this is a no-op.
117    /// If the cache is at capacity, the oldest entry is evicted.
118    pub fn add(&mut self, id: T) {
119        if self.index.contains(&id) {
120            return;
121        }
122
123        if self.order.is_full()
124            && let Some(evicted) = self.order.pop_back()
125        {
126            self.index.remove(&evicted);
127        }
128
129        if self.order.push_front(id.clone()).is_ok() {
130            self.index.insert(id);
131        }
132    }
133
134    /// Removes an ID from the cache.
135    pub fn remove(&mut self, id: &T) {
136        if self.index.remove(id) {
137            self.order.retain(|x| x != id);
138        }
139    }
140
141    /// Clears all entries from the cache.
142    pub fn clear(&mut self) {
143        self.order.clear();
144        self.index.clear();
145    }
146}
147
148impl<T, const N: usize> Default for FifoCache<T, N>
149where
150    T: Clone + Debug + Eq + Hash,
151{
152    fn default() -> Self {
153        Self::new()
154    }
155}
156
157/// A bounded cache that maintains key-value pairs with O(1) lookups.
158///
159/// Uses an `ArrayDeque` for FIFO ordering and an `AHashMap` for fast key-value access.
160/// When capacity is exceeded, the oldest entry is automatically evicted.
161///
162/// # Examples
163///
164/// ```
165/// use nautilus_common::cache::fifo::FifoCacheMap;
166///
167/// let mut cache: FifoCacheMap<u32, String, 3> = FifoCacheMap::new();
168/// cache.insert(1, "one".to_string());
169/// cache.insert(2, "two".to_string());
170/// cache.insert(3, "three".to_string());
171/// assert_eq!(cache.get(&1), Some(&"one".to_string()));
172///
173/// // Adding beyond capacity evicts the oldest
174/// cache.insert(4, "four".to_string());
175/// assert_eq!(cache.get(&1), None);
176/// assert_eq!(cache.get(&4), Some(&"four".to_string()));
177/// ```
178///
179/// Zero capacity is a compile-time error:
180///
181/// ```compile_fail
182/// use nautilus_common::cache::fifo::FifoCacheMap;
183///
184/// // This fails to compile: capacity must be > 0
185/// let cache: FifoCacheMap<u32, String, 0> = FifoCacheMap::new();
186/// ```
187#[derive(Debug)]
188pub struct FifoCacheMap<K, V, const N: usize>
189where
190    K: Clone + Debug + Eq + Hash,
191{
192    order: ArrayDeque<K, N>,
193    index: AHashMap<K, V>,
194}
195
196impl<K, V, const N: usize> FifoCacheMap<K, V, N>
197where
198    K: Clone + Debug + Eq + Hash,
199{
200    /// Creates a new empty [`FifoCacheMap`] with capacity `N`.
201    ///
202    /// # Panics
203    ///
204    /// Compile-time panic if `N == 0`.
205    #[must_use]
206    pub fn new() -> Self {
207        const { assert!(N > 0, "FifoCacheMap capacity must be greater than zero") };
208
209        Self {
210            order: ArrayDeque::new(),
211            index: AHashMap::with_capacity(N),
212        }
213    }
214
215    /// Returns the capacity of the cache.
216    #[must_use]
217    pub const fn capacity(&self) -> usize {
218        N
219    }
220
221    /// Returns the number of entries in the cache.
222    #[must_use]
223    pub fn len(&self) -> usize {
224        self.index.len()
225    }
226
227    /// Returns whether the cache is empty.
228    #[must_use]
229    pub fn is_empty(&self) -> bool {
230        self.index.is_empty()
231    }
232
233    /// Returns whether the cache contains the given key (O(1) lookup).
234    #[must_use]
235    pub fn contains_key(&self, key: &K) -> bool {
236        self.index.contains_key(key)
237    }
238
239    /// Returns a reference to the value for the given key (O(1) lookup).
240    #[must_use]
241    pub fn get(&self, key: &K) -> Option<&V> {
242        self.index.get(key)
243    }
244
245    /// Returns a mutable reference to the value for the given key (O(1) lookup).
246    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
247        self.index.get_mut(key)
248    }
249
250    /// Inserts a key-value pair into the cache.
251    ///
252    /// If the key already exists, the value is updated (no eviction occurs).
253    /// If the cache is at capacity and the key is new, the oldest entry is evicted.
254    pub fn insert(&mut self, key: K, value: V) {
255        if self.index.contains_key(&key) {
256            self.index.insert(key, value);
257            return;
258        }
259
260        if self.order.is_full()
261            && let Some(evicted) = self.order.pop_back()
262        {
263            self.index.remove(&evicted);
264        }
265
266        if self.order.push_front(key.clone()).is_ok() {
267            self.index.insert(key, value);
268        }
269    }
270
271    /// Removes a key from the cache, returning the value if present.
272    pub fn remove(&mut self, key: &K) -> Option<V> {
273        if let Some(value) = self.index.remove(key) {
274            self.order.retain(|x| x != key);
275            Some(value)
276        } else {
277            None
278        }
279    }
280
281    /// Clears all entries from the cache.
282    pub fn clear(&mut self) {
283        self.order.clear();
284        self.index.clear();
285    }
286}
287
288impl<K, V, const N: usize> Default for FifoCacheMap<K, V, N>
289where
290    K: Clone + Debug + Eq + Hash,
291{
292    fn default() -> Self {
293        Self::new()
294    }
295}
296
297#[cfg(test)]
298mod tests {
299    use rstest::rstest;
300
301    use super::*;
302
303    #[rstest]
304    fn test_add_and_contains() {
305        let mut cache: FifoCache<u32, 4> = FifoCache::new();
306        cache.add(1);
307        cache.add(2);
308        cache.add(3);
309
310        assert!(cache.contains(&1));
311        assert!(cache.contains(&2));
312        assert!(cache.contains(&3));
313        assert!(!cache.contains(&4));
314        assert_eq!(cache.len(), 3);
315    }
316
317    #[rstest]
318    fn test_eviction_at_capacity() {
319        let mut cache: FifoCache<u32, 3> = FifoCache::new();
320        cache.add(1);
321        cache.add(2);
322        cache.add(3);
323        assert_eq!(cache.len(), 3);
324
325        // Adding a 4th should evict the oldest (1)
326        cache.add(4);
327        assert_eq!(cache.len(), 3);
328        assert!(!cache.contains(&1));
329        assert!(cache.contains(&2));
330        assert!(cache.contains(&3));
331        assert!(cache.contains(&4));
332    }
333
334    #[rstest]
335    fn test_duplicate_add_is_noop() {
336        let mut cache: FifoCache<u32, 3> = FifoCache::new();
337        cache.add(1);
338        cache.add(2);
339        cache.add(1); // duplicate
340
341        assert_eq!(cache.len(), 2);
342        assert!(cache.contains(&1));
343        assert!(cache.contains(&2));
344    }
345
346    #[rstest]
347    fn test_remove() {
348        let mut cache: FifoCache<u32, 4> = FifoCache::new();
349        cache.add(1);
350        cache.add(2);
351        cache.add(3);
352
353        cache.remove(&2);
354        assert_eq!(cache.len(), 2);
355        assert!(cache.contains(&1));
356        assert!(!cache.contains(&2));
357        assert!(cache.contains(&3));
358    }
359
360    #[rstest]
361    fn test_remove_nonexistent_is_noop() {
362        let mut cache: FifoCache<u32, 4> = FifoCache::new();
363        cache.add(1);
364        cache.remove(&99);
365        assert_eq!(cache.len(), 1);
366    }
367
368    #[rstest]
369    fn test_capacity() {
370        let cache: FifoCache<u32, 10> = FifoCache::new();
371        assert_eq!(cache.capacity(), 10);
372    }
373
374    #[rstest]
375    fn test_is_empty() {
376        let mut cache: FifoCache<u32, 4> = FifoCache::new();
377        assert!(cache.is_empty());
378        cache.add(1);
379        assert!(!cache.is_empty());
380    }
381
382    #[rstest]
383    fn test_capacity_one_evicts_immediately() {
384        let mut cache: FifoCache<u32, 1> = FifoCache::new();
385        cache.add(1);
386        assert!(cache.contains(&1));
387        assert_eq!(cache.len(), 1);
388
389        cache.add(2);
390        assert!(!cache.contains(&1));
391        assert!(cache.contains(&2));
392        assert_eq!(cache.len(), 1);
393    }
394
395    #[rstest]
396    fn test_sequential_eviction_order() {
397        let mut cache: FifoCache<u32, 3> = FifoCache::new();
398
399        // Fill: [3, 2, 1] (front to back)
400        cache.add(1);
401        cache.add(2);
402        cache.add(3);
403
404        // Add 4: evicts 1 -> [4, 3, 2]
405        cache.add(4);
406        assert!(!cache.contains(&1));
407        assert!(cache.contains(&2));
408
409        // Add 5: evicts 2 -> [5, 4, 3]
410        cache.add(5);
411        assert!(!cache.contains(&2));
412        assert!(cache.contains(&3));
413
414        // Add 6: evicts 3 -> [6, 5, 4]
415        cache.add(6);
416        assert!(!cache.contains(&3));
417        assert!(cache.contains(&4));
418        assert!(cache.contains(&5));
419        assert!(cache.contains(&6));
420    }
421
422    #[rstest]
423    fn test_remove_then_readd() {
424        let mut cache: FifoCache<u32, 3> = FifoCache::new();
425        cache.add(1);
426        cache.add(2);
427        cache.remove(&1);
428        assert!(!cache.contains(&1));
429        assert_eq!(cache.len(), 1);
430
431        cache.add(1);
432        assert!(cache.contains(&1));
433        assert_eq!(cache.len(), 2);
434    }
435
436    #[rstest]
437    fn test_remove_frees_slot_for_new_element() {
438        let mut cache: FifoCache<u32, 3> = FifoCache::new();
439
440        cache.add(1);
441        cache.add(2);
442        cache.add(3);
443        cache.remove(&2);
444        assert_eq!(cache.len(), 2);
445
446        // Add new element - should not evict anyone
447        cache.add(4);
448        assert_eq!(cache.len(), 3);
449        assert!(cache.contains(&1));
450        assert!(cache.contains(&3));
451        assert!(cache.contains(&4));
452    }
453
454    #[rstest]
455    fn test_duplicate_add_does_not_refresh_position() {
456        let mut cache: FifoCache<u32, 3> = FifoCache::new();
457
458        // Add 1, 2, 3 (1 is oldest)
459        cache.add(1);
460        cache.add(2);
461        cache.add(3);
462
463        // Re-add 1 (should be no-op, 1 stays oldest)
464        cache.add(1);
465
466        // Add 4: should evict 1 (still oldest), not 2
467        cache.add(4);
468        assert!(!cache.contains(&1));
469        assert!(cache.contains(&2));
470        assert!(cache.contains(&3));
471        assert!(cache.contains(&4));
472    }
473
474    #[rstest]
475    fn test_interleaved_add_remove() {
476        let mut cache: FifoCache<u32, 4> = FifoCache::new();
477
478        cache.add(1);
479        cache.add(2);
480        cache.remove(&1);
481        cache.add(3);
482        cache.add(4);
483        cache.remove(&3);
484        cache.add(5);
485
486        assert!(!cache.contains(&1));
487        assert!(cache.contains(&2));
488        assert!(!cache.contains(&3));
489        assert!(cache.contains(&4));
490        assert!(cache.contains(&5));
491        assert_eq!(cache.len(), 3);
492    }
493
494    #[rstest]
495    fn test_remove_all_elements() {
496        let mut cache: FifoCache<u32, 3> = FifoCache::new();
497        cache.add(1);
498        cache.add(2);
499        cache.add(3);
500
501        cache.remove(&1);
502        cache.remove(&2);
503        cache.remove(&3);
504
505        assert!(cache.is_empty());
506        assert_eq!(cache.len(), 0);
507    }
508
509    #[rstest]
510    fn test_string_type() {
511        let mut cache: FifoCache<String, 2> = FifoCache::new();
512        cache.add("hello".to_string());
513        cache.add("world".to_string());
514
515        assert!(cache.contains(&"hello".to_string()));
516        assert!(cache.contains(&"world".to_string()));
517
518        cache.add("foo".to_string());
519        assert!(!cache.contains(&"hello".to_string()));
520    }
521
522    #[rstest]
523    fn test_map_insert_and_get() {
524        let mut cache: FifoCacheMap<u32, String, 4> = FifoCacheMap::new();
525        cache.insert(1, "one".to_string());
526        cache.insert(2, "two".to_string());
527        cache.insert(3, "three".to_string());
528
529        assert_eq!(cache.get(&1), Some(&"one".to_string()));
530        assert_eq!(cache.get(&2), Some(&"two".to_string()));
531        assert_eq!(cache.get(&3), Some(&"three".to_string()));
532        assert_eq!(cache.get(&4), None);
533        assert_eq!(cache.len(), 3);
534    }
535
536    #[rstest]
537    fn test_map_eviction_at_capacity() {
538        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
539        cache.insert(1, "one");
540        cache.insert(2, "two");
541        cache.insert(3, "three");
542        assert_eq!(cache.len(), 3);
543
544        // Adding a 4th should evict the oldest (1)
545        cache.insert(4, "four");
546        assert_eq!(cache.len(), 3);
547        assert_eq!(cache.get(&1), None);
548        assert_eq!(cache.get(&2), Some(&"two"));
549        assert_eq!(cache.get(&3), Some(&"three"));
550        assert_eq!(cache.get(&4), Some(&"four"));
551    }
552
553    #[rstest]
554    fn test_map_update_existing_key() {
555        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
556        cache.insert(1, "one");
557        cache.insert(2, "two");
558        cache.insert(3, "three");
559
560        // Update existing key - should not evict
561        cache.insert(1, "ONE");
562        assert_eq!(cache.len(), 3);
563        assert_eq!(cache.get(&1), Some(&"ONE"));
564        assert_eq!(cache.get(&2), Some(&"two"));
565        assert_eq!(cache.get(&3), Some(&"three"));
566    }
567
568    #[rstest]
569    fn test_map_remove() {
570        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
571        cache.insert(1, "one");
572        cache.insert(2, "two");
573        cache.insert(3, "three");
574
575        let removed = cache.remove(&2);
576        assert_eq!(removed, Some("two"));
577        assert_eq!(cache.len(), 2);
578        assert!(cache.contains_key(&1));
579        assert!(!cache.contains_key(&2));
580        assert!(cache.contains_key(&3));
581    }
582
583    #[rstest]
584    fn test_map_remove_nonexistent() {
585        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
586        cache.insert(1, "one");
587        let removed = cache.remove(&99);
588        assert_eq!(removed, None);
589        assert_eq!(cache.len(), 1);
590    }
591
592    #[rstest]
593    fn test_map_get_mut() {
594        let mut cache: FifoCacheMap<u32, String, 4> = FifoCacheMap::new();
595        cache.insert(1, "one".to_string());
596
597        if let Some(value) = cache.get_mut(&1) {
598            value.push_str("_modified");
599        }
600
601        assert_eq!(cache.get(&1), Some(&"one_modified".to_string()));
602    }
603
604    #[rstest]
605    fn test_map_capacity() {
606        let cache: FifoCacheMap<u32, &str, 10> = FifoCacheMap::new();
607        assert_eq!(cache.capacity(), 10);
608    }
609
610    #[rstest]
611    fn test_map_is_empty() {
612        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
613        assert!(cache.is_empty());
614        cache.insert(1, "one");
615        assert!(!cache.is_empty());
616    }
617
618    #[rstest]
619    fn test_map_capacity_one() {
620        let mut cache: FifoCacheMap<u32, &str, 1> = FifoCacheMap::new();
621        cache.insert(1, "one");
622        assert_eq!(cache.get(&1), Some(&"one"));
623
624        cache.insert(2, "two");
625        assert_eq!(cache.get(&1), None);
626        assert_eq!(cache.get(&2), Some(&"two"));
627        assert_eq!(cache.len(), 1);
628    }
629
630    #[rstest]
631    fn test_map_sequential_eviction() {
632        let mut cache: FifoCacheMap<u32, u32, 3> = FifoCacheMap::new();
633
634        cache.insert(1, 10);
635        cache.insert(2, 20);
636        cache.insert(3, 30);
637
638        // Add 4: evicts 1
639        cache.insert(4, 40);
640        assert!(!cache.contains_key(&1));
641        assert!(cache.contains_key(&2));
642
643        // Add 5: evicts 2
644        cache.insert(5, 50);
645        assert!(!cache.contains_key(&2));
646        assert!(cache.contains_key(&3));
647    }
648
649    #[rstest]
650    fn test_map_update_does_not_change_eviction_order() {
651        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
652
653        cache.insert(1, "one");
654        cache.insert(2, "two");
655        cache.insert(3, "three");
656
657        // Update key 1 - should NOT move it to front
658        cache.insert(1, "ONE");
659
660        // Add new key - should still evict 1 (oldest by insertion order)
661        cache.insert(4, "four");
662        assert!(!cache.contains_key(&1));
663        assert!(cache.contains_key(&2));
664        assert!(cache.contains_key(&3));
665        assert!(cache.contains_key(&4));
666    }
667
668    #[rstest]
669    fn test_map_remove_frees_slot() {
670        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
671
672        cache.insert(1, "one");
673        cache.insert(2, "two");
674        cache.insert(3, "three");
675
676        cache.remove(&2);
677        assert_eq!(cache.len(), 2);
678
679        // Add new element - should not evict anyone
680        cache.insert(4, "four");
681        assert_eq!(cache.len(), 3);
682        assert!(cache.contains_key(&1));
683        assert!(cache.contains_key(&3));
684        assert!(cache.contains_key(&4));
685    }
686
687    use proptest::prelude::*;
688
689    /// Operations that can be performed on a FifoCache
690    #[derive(Clone, Debug)]
691    enum Op {
692        Add(u8),
693        Remove(u8),
694    }
695
696    fn op_strategy() -> impl Strategy<Value = Op> {
697        prop_oneof![(0..50u8).prop_map(Op::Add), (0..50u8).prop_map(Op::Remove),]
698    }
699
700    fn ops_strategy() -> impl Strategy<Value = Vec<Op>> {
701        proptest::collection::vec(op_strategy(), 0..100)
702    }
703
704    /// Apply operations and return final cache state
705    fn apply_ops<const N: usize>(ops: &[Op]) -> FifoCache<u8, N> {
706        let mut cache = FifoCache::<u8, N>::new();
707        for op in ops {
708            match op {
709                Op::Add(id) => cache.add(*id),
710                Op::Remove(id) => cache.remove(id),
711            }
712        }
713        cache
714    }
715
716    proptest! {
717        /// Invariant: len() never exceeds capacity
718        #[rstest]
719        fn prop_len_never_exceeds_capacity(ops in ops_strategy()) {
720            let cache = apply_ops::<8>(&ops);
721            prop_assert!(cache.len() <= cache.capacity());
722        }
723
724        /// Invariant: is_empty() iff len() == 0
725        #[rstest]
726        fn prop_is_empty_consistent_with_len(ops in ops_strategy()) {
727            let cache = apply_ops::<8>(&ops);
728            if cache.is_empty() {
729                prop_assert_eq!(cache.len(), 0);
730            } else {
731                prop_assert!(!cache.is_empty());
732            }
733        }
734
735        /// Invariant: Adding a duplicate does not change len
736        #[rstest]
737        fn prop_add_duplicate_is_idempotent(
738            ops in ops_strategy(),
739            id in 0..50u8
740        ) {
741            let mut cache = apply_ops::<8>(&ops);
742            cache.add(id);
743            let len_after_first = cache.len();
744            let contained_after_first = cache.contains(&id);
745
746            cache.add(id);
747            prop_assert_eq!(cache.len(), len_after_first);
748            prop_assert_eq!(cache.contains(&id), contained_after_first);
749        }
750
751        /// Invariant: After remove(x), contains(x) is false
752        #[rstest]
753        fn prop_remove_ensures_not_contained(
754            ops in ops_strategy(),
755            id in 0..50u8
756        ) {
757            let mut cache = apply_ops::<8>(&ops);
758            cache.remove(&id);
759            prop_assert!(!cache.contains(&id));
760        }
761
762        /// Invariant: After add(x), contains(x) is true (unless immediately evicted)
763        #[rstest]
764        fn prop_add_ensures_contained_if_capacity(id in 0..50u8) {
765            let mut cache: FifoCache<u8, 8> = FifoCache::new();
766            cache.add(id);
767            prop_assert!(cache.contains(&id));
768        }
769
770        /// Invariant: FIFO eviction order - oldest element evicted first
771        #[rstest]
772        fn prop_fifo_eviction_order(extra in 0..20u8) {
773            let mut cache: FifoCache<u8, 4> = FifoCache::new();
774
775            // Fill cache with 0, 1, 2, 3
776            for i in 0..4u8 {
777                cache.add(i);
778            }
779            prop_assert_eq!(cache.len(), 4);
780
781            // Add more elements, should evict in FIFO order
782            for i in 0..extra {
783                let new_id = 100 + i;
784                cache.add(new_id);
785
786                // The element that should have been evicted
787                let evicted = i;
788                if evicted < 4 {
789                    prop_assert!(!cache.contains(&evicted),
790                        "Element {} should have been evicted", evicted);
791                }
792            }
793        }
794
795        /// Invariant: Remove on empty cache is safe no-op
796        #[rstest]
797        fn prop_remove_on_empty_is_noop(id in 0..50u8) {
798            let mut cache: FifoCache<u8, 8> = FifoCache::new();
799            cache.remove(&id);
800            prop_assert!(cache.is_empty());
801            prop_assert_eq!(cache.len(), 0);
802        }
803
804        /// Invariant: len() decreases by 1 when removing existing element
805        #[rstest]
806        fn prop_remove_decreases_len(
807            ops in ops_strategy(),
808            id in 0..50u8
809        ) {
810            let mut cache = apply_ops::<8>(&ops);
811            cache.add(id); // Ensure it exists
812            let len_before = cache.len();
813
814            cache.remove(&id);
815
816            if cache.contains(&id) {
817                prop_assert!(false, "Element still contained after remove");
818            }
819            prop_assert!(cache.len() < len_before || len_before == 0);
820        }
821
822        /// Invariant: At capacity, adding new element keeps len same
823        #[rstest]
824        fn prop_add_at_capacity_maintains_len(new_id in 50..100u8) {
825            let mut cache: FifoCache<u8, 4> = FifoCache::new();
826
827            // Fill to capacity with distinct values
828            for i in 0..4u8 {
829                cache.add(i);
830            }
831            prop_assert_eq!(cache.len(), 4);
832
833            // Add new element (guaranteed not in cache)
834            cache.add(new_id);
835            prop_assert_eq!(cache.len(), 4);
836        }
837
838        /// Invariant: All added elements are contained until evicted or removed
839        #[rstest]
840        fn prop_recent_adds_are_contained(recent in proptest::collection::vec(0..50u8, 1..5)) {
841            let mut cache: FifoCache<u8, 8> = FifoCache::new();
842
843            for &id in &recent {
844                cache.add(id);
845            }
846
847            // Deduplicate to get expected unique count
848            let mut unique: Vec<u8> = recent;
849            unique.sort_unstable();
850            unique.dedup();
851            let expected_len = unique.len().min(8);
852
853            prop_assert_eq!(cache.len(), expected_len);
854
855            // All unique recent adds should be contained (capacity is 8, we add at most 5)
856            for id in unique {
857                prop_assert!(cache.contains(&id), "Recently added {} not contained", id);
858            }
859        }
860
861        /// Invariant: len() never exceeds capacity for map
862        #[rstest]
863        fn prop_map_len_never_exceeds_capacity(
864            keys in proptest::collection::vec(0..50u8, 0..100)
865        ) {
866            let mut cache: FifoCacheMap<u8, u8, 8> = FifoCacheMap::new();
867            for key in keys {
868                cache.insert(key, key);
869            }
870            prop_assert!(cache.len() <= cache.capacity());
871        }
872
873        /// Invariant: is_empty() iff len() == 0 for map
874        #[rstest]
875        fn prop_map_is_empty_consistent_with_len(
876            keys in proptest::collection::vec(0..50u8, 0..20)
877        ) {
878            let mut cache: FifoCacheMap<u8, u8, 8> = FifoCacheMap::new();
879            for key in keys {
880                cache.insert(key, key);
881            }
882            if cache.is_empty() {
883                prop_assert_eq!(cache.len(), 0);
884            } else {
885                prop_assert!(!cache.is_empty());
886            }
887        }
888
889        /// Invariant: Updating existing key does not change len
890        #[rstest]
891        fn prop_map_update_is_idempotent_for_len(
892            keys in proptest::collection::vec(0..50u8, 1..10),
893            key in 0..50u8
894        ) {
895            let mut cache: FifoCacheMap<u8, u8, 8> = FifoCacheMap::new();
896            for k in keys {
897                cache.insert(k, k);
898            }
899            cache.insert(key, 100);
900            let len_after_first = cache.len();
901
902            cache.insert(key, 200);
903            prop_assert_eq!(cache.len(), len_after_first);
904        }
905
906        /// Invariant: After remove(k), get(k) is None
907        #[rstest]
908        fn prop_map_remove_ensures_not_contained(
909            keys in proptest::collection::vec(0..50u8, 0..20),
910            key in 0..50u8
911        ) {
912            let mut cache: FifoCacheMap<u8, u8, 8> = FifoCacheMap::new();
913            for k in keys {
914                cache.insert(k, k);
915            }
916            cache.remove(&key);
917            prop_assert!(cache.get(&key).is_none());
918        }
919
920        /// Invariant: After insert(k, v), get(k) returns Some(&v)
921        #[rstest]
922        fn prop_map_insert_ensures_get(key in 0..50u8, value in 0..100u8) {
923            let mut cache: FifoCacheMap<u8, u8, 8> = FifoCacheMap::new();
924            cache.insert(key, value);
925            prop_assert_eq!(cache.get(&key), Some(&value));
926        }
927
928        /// Invariant: At capacity, inserting new key keeps len same
929        #[rstest]
930        fn prop_map_insert_at_capacity_maintains_len(new_key in 50..100u8) {
931            let mut cache: FifoCacheMap<u8, u8, 4> = FifoCacheMap::new();
932
933            for i in 0..4u8 {
934                cache.insert(i, i * 10);
935            }
936            prop_assert_eq!(cache.len(), 4);
937
938            cache.insert(new_key, 99);
939            prop_assert_eq!(cache.len(), 4);
940        }
941
942        /// Invariant: FIFO eviction for map
943        #[rstest]
944        fn prop_map_fifo_eviction(extra in 0..20u8) {
945            let mut cache: FifoCacheMap<u8, u8, 4> = FifoCacheMap::new();
946
947            for i in 0..4u8 {
948                cache.insert(i, i * 10);
949            }
950
951            for i in 0..extra {
952                let new_key = 100 + i;
953                cache.insert(new_key, new_key);
954
955                let evicted = i;
956                if evicted < 4 {
957                    prop_assert!(cache.get(&evicted).is_none(),
958                        "Key {} should have been evicted", evicted);
959                }
960            }
961        }
962    }
963}
nautilus_common/cache/fifo.rs

nautilus_common/cache/
fifo.rs
