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

nautilus_common/cache/
fifo.rs
