FATAL: _evict() double-removes nodes — pop() already calls remove() (nulling node.prev/next), then _remove_node() calls remove() AGAIN -> AttributeError: 'NoneType' on first eviction. The cache cannot survive reaching capacity.
Test suite never executes: test_lfu_eviction crashes at the first eviction, so the 'All tests passed' message is unreachable and assertions are effectively unverified.
Background _eviction_loop materializes list(self.key_to_node.keys())[:50] every sweep — an O(N) linear scan, forbidden by the strict O(1) requirement.
_FreqList.pop() has no empty-guard — calling pop() on an empty list dereferences self.head.next (the dummy tail) and corrupts the DLL.
Transaction _apply_put applies the buffered value into the EXACT original_node captured at tx.put() time; if the global cache evicted/relocated that node between put and commit, you mutate a stale/dangling node (no MVCC/version check).
Commit is not atomic across exceptions: a crash mid-_apply loop leaves half-applied global state with no rollback.
Uses time.time() (system clock) throughout instead of time.monotonic() — NTP jumps corrupt TTL eviction.
▮ RECOMMENDED USE
Not recommended for systems code as-is. The 4-bit quant degrades logic sharply vs the 6-bit sibling (82->57) — usable only for boilerplate/scaffolding drafts that a human will heavily rewrite.
▮ REFACTORED PATCH
# FIX 1 (the crash): _evict double-removes. pop() already unlinks,
# so do NOT call _remove_node on a popped node. Either:
# (a) pop and then only delete the key_map entry + min_freq bookkeeping:
def _evict(self):
if not self.freq_to_list:
return
evict_list = self.freq_to_list[self.min_freq]
if evict_list.size == 0: # guard against empty
del self.freq_to_list[self.min_freq]
return
node = evict_list.pop() # pop() unlinks + nulls prev/next
del self.key_to_node[node.key] # DON'T call _remove_node again
if self.freq_to_list[self.min_freq].size == 0:
del self.freq_to_list[self.min_freq]
self.min_freq += 1
# FIX 2: _FreqList.pop empty-guard
def pop(self) -> _Node:
if self.size == 0:
raise IndexError('pop from empty _FreqList')
node = self.head.next
self.remove(node)
return node
# FIX 3: kill the O(N) scan in background sweep — maintain a separate
# set of keys that have a TTL, and iterate that set in batches:
async with self.lock:
batch = list(self._ttl_keys)[:50]
for k in batch:
node = self.key_to_node.get(k)
if node and 0 < node.expires_at <= time.monotonic():
self._remove_node(node)
# FIX 4: time.time() -> time.monotonic() everywhere.
# FIX 5: add node.version; in tx._apply_put, abort/refresh if
# cache.key_to_node[key] is a different node than original_node.