-
Notifications
You must be signed in to change notification settings - Fork 578
Open
Description
class LRUCache(....):
def set(self, key: K, value: V):
if self.cache.get(key):
self.cache[key] = value
self.cache.move_to_end(key, last=True)
else:
self.cache[key] = value
# Check, if the cache is full and we have to remove old items
# If the queue is of unlimited size, self.capacity is NaN and
# x > NaN is always False in Python and the cache won't be cleared.
if self.capacity is not None and self.length > self.capacity:
self.cache.popitem(last=False)
The condition if self.cache.get(key): checks if the value is truthy, not if the key exists. This causes problems when Falsy values (0, False, "", [], None, etc.) are stored for a key.
When updating an existing key with a falsy value, it's treated as a new key (goes to else) and breaks LRU ordering.
A test case to demonstrate this bug. This test fails
def test_lru_cache_set_item():
cache = LRUCache(capacity=3)
cache["a"] = 0 # Falsy value!
cache["b"] = 1
cache["c"] = 2
assert sorted(cache.lru) == ["a", "b", "c"]
cache.set("a", 3) # This should update "a" and move it to end
cache.set("d", 4) # This should evict "b"
assert sorted(cache.lru) == ["a", "c", "d"] # "b" should be gone but "a" is evicted in the current implementation
On the other end, the following test case passes -
def test_lru_cache_set_item():
cache = LRUCache(capacity=3)
cache["a"] = 3
cache["b"] = 1
cache["c"] = 2
assert sorted(cache.lru) == ["a", "b", "c"]
cache.set("a", 0)
cache.set("d", 4)
assert sorted(cache.lru) == ["a", "c", "d"]
Metadata
Metadata
Assignees
Labels
No labels