name = "lru"
description = "An LRU cache implementation — ETNA workload."
language = "rust"
strategies = ["proptest", "quickcheck", "crabcheck", "hegel"]
crate = "lru"
base_commit = "dac07e3edc896f6caec5180ac179b89044399c59"

[[tasks]]
mutations = ["clone_unbounded_no_panic_3ec42b6_1"]

[tasks.source]
repo = "https://github.com/jeromefroe/lru-rs"
commits = ["3ec42b6369082c00da2836fe033db20cb52a36fc"]
commit_subjects = ["Fix clone implementation for unbounded cache"]
prs = [219]
summary = "`<LruCache as Clone>::clone` forwarded `self.cap()` (which is `usize::MAX` for an unbounded cache) into `HashMap::with_capacity_and_hasher`, panicking with 'Hash table capacity overflow' the first time anyone cloned an unbounded cache. The fix special-cases `is_unbounded()` and uses `self.len()` for the new map's initial capacity instead."

[tasks.injection]
kind = "patch"
patch = "patches/clone_unbounded_no_panic_3ec42b6_1.patch"
files = ["src/lib.rs"]
locations = [{ file = "src/lib.rs", symbol = "LruCache::clone" }]

[tasks.bug]
short_name = "clone_unbounded_no_panic"
invariant = "`LruCache::unbounded().clone()` must not panic regardless of how many entries the cache currently holds, and the clone must contain the same key/value pairs as the original."
how_triggered = "The buggy clone allocates the new internal `HashMap` with capacity `self.cap().get()`. When the cache is unbounded `self.cap()` is `NonZeroUsize::MAX`, so `HashMap::with_capacity_and_hasher` is asked to reserve `usize::MAX` slots and hashbrown panics with 'Hash table capacity overflow' before a single entry is copied."

[[tasks.tasks]]
property = "CloneUnboundedNoPanic"
witnesses = [
  { test_fn = "witness_clone_unbounded_no_panic_case_three_entries" },
  { test_fn = "witness_clone_unbounded_no_panic_case_one_entry" },
  { test_fn = "witness_clone_unbounded_no_panic_case_empty" },
]

[[tasks]]
mutations = ["pop_iter_consistent_5f4a46a_1"]

[tasks.source]
repo = "https://github.com/jeromefroe/lru-rs"
commits = ["5f4a46a522b4e325cc4d56c1b737e44915921cca"]
commit_subjects = ["Fix bug in LruCache::pop()."]
prs = [29]
summary = "`LruCache::pop` removed the entry from the underlying hashmap but never detached the corresponding node from the linked list. Subsequent operations (iter, pop_lru, evict-on-put) walked through the orphaned node, leading to memory unsafety and observable wrong-key-in-iter behaviour."

[tasks.injection]
kind = "patch"
patch = "patches/pop_iter_consistent_5f4a46a_1.patch"
files = ["src/lib.rs"]
locations = [{ file = "src/lib.rs", symbol = "LruCache::pop" }]

[tasks.bug]
short_name = "pop_iter_consistent"
invariant = "After `pop(k)` removes a key, the cache's linked-list view (iter, pop_lru, evict-on-put) must agree with the map view. In particular, the popped key must not appear in `iter()` and must not be returned by any subsequent `pop_lru`."
how_triggered = "The buggy `pop` removes the entry from the hashmap and frees its `Box<LruEntry>` but skips `self.detach(node)`, so the linked list still threads through the freed slot. iter() then visits the orphan (still holding the popped key), and pop_lru's `self.map.remove(&old_key).unwrap()` panics when it tries to remove a key the map no longer contains."

[[tasks.tasks]]
property = "PopIterConsistent"
witnesses = [
  { test_fn = "witness_pop_iter_consistent_case_pop_middle" },
  { test_fn = "witness_pop_iter_consistent_case_pop_first" },
  { test_fn = "witness_pop_iter_consistent_case_pop_last" },
]

[[tasks]]
mutations = ["drop_impl_drops_all_37dbda0_1"]

[tasks.source]
repo = "https://github.com/jeromefroe/lru-rs"
commits = ["37dbda01eb6820b86292c1f9d497d01d35287ad8"]
commit_subjects = ["Use as_mut_ptr method to fix memory leak"]
prs = [79]
summary = "The cache's `Drop` impl ran `ptr::drop_in_place(&mut e.key as *mut _)`. Type inference picked `*mut MaybeUninit<K>`, so the drop targeted the MaybeUninit wrapper (a no-op) rather than the inner `K`/`V`, leaking every entry's key and value when the cache itself was dropped. The fix uses `e.key.as_mut_ptr()` to obtain a `*mut K` so the inner destructor actually runs."

[tasks.injection]
kind = "patch"
patch = "patches/drop_impl_drops_all_37dbda0_1.patch"
files = ["src/lib.rs"]
locations = [{ file = "src/lib.rs", symbol = "<LruCache as Drop>::drop" }]

[tasks.bug]
short_name = "drop_impl_drops_all"
invariant = "Dropping an `LruCache` containing N entries must run `Drop` once for every key and once for every value (so 2*N destructor calls when both K and V track drops)."
how_triggered = "The buggy `Drop` impl casts `&mut node.key` (whose type is `&mut MaybeUninit<K>`) to `*mut _`, picking up `*mut MaybeUninit<K>` from inference. `ptr::drop_in_place` on a `*mut MaybeUninit<K>` is a no-op (MaybeUninit has no Drop), so the inner `K` is leaked; same for `V`. Dropping the cache therefore observes zero K/V destructor calls instead of the expected 2*N."

[[tasks.tasks]]
property = "DropImplDropsAll"
witnesses = [
  { test_fn = "witness_drop_impl_drops_all_case_many" },
  { test_fn = "witness_drop_impl_drops_all_case_one" },
]

[[tasks]]
mutations = ["clear_resize_drops_all_4460158_1"]

[tasks.source]
repo = "https://github.com/jeromefroe/lru-rs"
commits = ["4460158fab9808001d8fad509615a4a8c2769e11"]
commit_subjects = ["Fix memory leak when using clear and resize"]
prs = [101]
summary = "Both `clear()` and `resize()` invoked the private `remove_last()` helper, which detaches a node from the linked list and frees its `Box<LruEntry>` shell but leaves the inner `MaybeUninit<K>` / `MaybeUninit<V>` undropped. Every entry the cache evicted via clear or resize was leaked. The fix routes both methods through `pop_lru()`, which `assume_init()`s the K/V out of the slot so they get destructed when the returned tuple is dropped."

[tasks.injection]
kind = "patch"
files = ["src/lib.rs"]
locations = [
  { file = "src/lib.rs", symbol = "LruCache::clear" },
  { file = "src/lib.rs", symbol = "LruCache::resize" },
]
patch = "patches/clear_resize_drops_all_4460158_1.patch"

[tasks.bug]
short_name = "clear_resize_drops_all"
invariant = "Both `LruCache::clear()` and `LruCache::resize(small)` must drop every entry they remove from the cache; for N tracked entries cleared, the K/V destructor count must equal 2*N."
how_triggered = "The buggy `clear` and `resize` discard the result of `self.remove_last()`. `remove_last` only frees the `Box<LruEntry>` heap allocation; the inner `MaybeUninit<K>` and `MaybeUninit<V>` are never dropped because `MaybeUninit` does not run its inner `T`'s destructor on drop. Every cleared / resized-out entry leaks both its key and value."

[[tasks.tasks]]
property = "ClearResizeDropsAll"
witnesses = [
  { test_fn = "witness_clear_resize_drops_all_case_clear" },
  { test_fn = "witness_clear_resize_drops_all_case_resize" },
  { test_fn = "witness_clear_resize_drops_all_case_clear_one" },
]

[[tasks]]
mutations = ["pop_drops_key_ea64c8f_1"]

[tasks.source]
repo = "https://github.com/jeromefroe/lru-rs"
commits = ["ea64c8f932a45434cbc71d3843d28af7c1819864"]
commit_subjects = ["Fix memory leak when using pop"]
prs = [104]
summary = "`LruCache::pop` removed an entry from the hashmap and returned its value but never dropped the entry's key. The key sat in the freed slot's `MaybeUninit<K>` and was leaked, so any K with a non-trivial destructor (Box, Rc, custom Drop) leaked once per `pop` call. The fix adds an explicit `ptr::drop_in_place(old_node.key.as_mut_ptr())` before the slot is reused."

[tasks.injection]
kind = "patch"
patch = "patches/pop_drops_key_ea64c8f_1.patch"
files = ["src/lib.rs"]
locations = [{ file = "src/lib.rs", symbol = "LruCache::pop" }]

[tasks.bug]
short_name = "pop_drops_key"
invariant = "`LruCache::pop(&q)` must drop the popped entry's key. After popping N tracked keys, the key destructor count must equal N."
how_triggered = "The buggy `pop` extracts the entry's `V` via `assume_init` and returns it but never drops the entry's `K`. Because `K` lives inside a `MaybeUninit<K>` slot, dropping the surrounding `LruEntry` is a no-op for the inner key — every `pop` call therefore leaks one K."

[[tasks.tasks]]
property = "PopDropsKey"
witnesses = [
  { test_fn = "witness_pop_drops_key_case_many" },
  { test_fn = "witness_pop_drops_key_case_one" },
]
