Buggy behavior on ARC

[stevefan1999-personal]

caches-rs/src/lru/adaptive.rs

Line 384 in ab7fd3c

let mut ent = self.recent_evict.map.remove(&key_ref).unwrap();

Seems to be buggy.

running 1 test
thread 'limited_cache::test::test_get_or_insert_default_and_edit_evicts_old_items_to_meet_capacity' panicked at C:\Users\steve\scoop\persist\rustup\.cargo\git\checkouts\caches-rs-f5b438d840965066\ff4eb24\src\lru\adaptive.rs:384:66:
called `Option::unwrap()` on a `None` value
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/58eefc33adf769a1abe12ad94b3e6811185b4ce5/library\std\src\panicking.rs:617
   1: core::panicking::panic_fmt
             at /rustc/58eefc33adf769a1abe12ad94b3e6811185b4ce5/library\core\src\panicking.rs:67
   2: core::panicking::panic
             at /rustc/58eefc33adf769a1abe12ad94b3e6811185b4ce5/library\core\src\panicking.rs:117
   3: enum2$<core::option::Option<alloc::boxed::Box<caches::lru::raw::EntryNode<alloc::string::String,usize>,alloc::alloc::Global> > >::unwrap<alloc::boxed::Box<caches::lru::raw::EntryNode<alloc::string::String,usize>,alloc::alloc::Global> >
             at /rustc/58eefc33adf769a1abe12ad94b3e6811185b4ce5\library\core\src\option.rs:935
   4: caches::lru::adaptive::impl$4::put<alloc::string::String,usize,ahash::random_state::RandomState,ahash::random_state::RandomState,ahash::random_state::RandomState,ahash::random_state::RandomState>
             at C:\Users\steve\scoop\persist\rustup\.cargo\git\checkouts\caches-rs-f5b438d840965066\ff4eb24\src\lru\adaptive.rs:384
   5: rustls::limited_cache::LimitedCache<alloc::string::String,usize>::get_or_insert_default_and_edit<alloc::string::String,usize,rustls::limited_cache::test::test_get_or_insert_default_and_edit_evicts_old_items_to_meet_capacity::closure_env$4>
             at .\src\limited_cache.rs:38
   6: rustls::limited_cache::test::test_get_or_insert_default_and_edit_evicts_old_items_to_meet_capacity
             at .\src\limited_cache.rs:180
   7: rustls::limited_cache::test::test_get_or_insert_default_and_edit_evicts_old_items_to_meet_capacity::closure$0
             at .\src\limited_cache.rs:165
   8: core::ops::function::FnOnce::call_once<rustls::limited_cache::test::test_get_or_insert_default_and_edit_evicts_old_items_to_meet_capacity::closure_env$0,tuple$<> >
             at /rustc/58eefc33adf769a1abe12ad94b3e6811185b4ce5\library\core\src\ops\function.rs:250
   9: core::ops::function::FnOnce::call_once
             at /rustc/58eefc33adf769a1abe12ad94b3e6811185b4ce5/library\core\src\ops\function.rs:250
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
test limited_cache::test::test_get_or_insert_default_and_edit_evicts_old_items_to_meet_capacity ... FAILED

failures:

failures:
    limited_cache::test::test_get_or_insert_default_and_edit_evicts_old_items_to_meet_capacity

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 189 filtered out; finished in 0.07s

    #[test]
    fn test_get_or_insert_default_and_edit_evicts_old_items_to_meet_capacity() {
        let mut t = Test::new(3);

        t.get_or_insert_default_and_edit("abc".into(), |v| *v += 1);
        t.get_or_insert_default_and_edit("def".into(), |v| *v += 2);

        // evicts "abc"
        t.get_or_insert_default_and_edit("ghi".into(), |v| *v += 3);
        assert_eq!(t.get("abc"), None);

        // evicts "def"
        t.get_or_insert_default_and_edit("jkl".into(), |v| *v += 4);
        assert_eq!(t.get("def"), None);

        // evicts "ghi"
        t.get_or_insert_default_and_edit("abc".into(), |v| *v += 5);
        assert_eq!(t.get("ghi"), None);

        // evicts "jkl"
        t.get_or_insert_default_and_edit("def".into(), |v| *v += 6);

        assert_eq!(t.get("abc"), Some(&5));
        assert_eq!(t.get("def"), Some(&6));
        assert_eq!(t.get("ghi"), None);
        assert_eq!(t.get("jkl"), None);
    }

pub(crate) struct LimitedCache<K: Clone + Hash + Eq, V> {
    map: AdaptiveCache<K, V>,
}

impl<K, V> LimitedCache<K, V>
where
    K: Eq + Hash + Clone + core::fmt::Debug,
    V: Default,
{
    /// Create a new LimitedCache with the given rough capacity.
    pub(crate) fn new(capacity_order_of_magnitude: usize) -> Self {
        Self {
            map: AdaptiveCache::new(capacity_order_of_magnitude - 1).unwrap(),
        }
    }

    pub(crate) fn get_or_insert_default_and_edit(&mut self, k: K, edit: impl FnOnce(&mut V)) {
        if self.map.contains(&k) {
            edit(self.map.get_mut(&k).unwrap());
        } else {
            let mut val = V::default();
            edit(&mut val);

            // TODO: there seems to have a bug on caches-rs where if the key was recently removed
            self.map.remove(&k);
            self.map.put(k, val);
        }
    }

    pub(crate) fn insert(&mut self, k: K, v: V) {
        self.map.put(k, v);
    }

    pub(crate) fn get<'a, Q: ?Sized>(&'a mut self, k: &'a Q) -> Option<&V>
    where
        K: Borrow<Q>,
        KeyRef<K>: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.map.get(k)
    }

    pub(crate) fn get_mut<'a, Q: ?Sized>(&'a mut self, k: &'a Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        KeyRef<K>: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.map.get_mut(k)
    }

    pub(crate) fn remove<'a, Q: ?Sized>(&'a mut self, k: &'a Q) -> Option<V>
    where
        K: Borrow<Q>,
        KeyRef<K>: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.map.remove(k)
    }
}

[al8n]

Hi, thanks for reporting. I found that this is not a bug. In your test case, you set the size to 3, which means both the recent_cache and the frequent_cache have a size 3. If you change the size to 2, then your test case will work.

Anyway, the design of the API misleads. I will polish the APIs in the next release.