Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/cachetools/__init__.py: 78%
Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Extensible memoizing collections and decorators."""
3__all__ = (
4 "Cache",
5 "FIFOCache",
6 "LFUCache",
7 "LRUCache",
8 "RRCache",
9 "TLRUCache",
10 "TTLCache",
11 "cached",
12 "cachedmethod",
13)
15__version__ = "7.1.4"
17import collections
18import collections.abc
19import functools
20import heapq
21import random
22import time
24from . import keys
27class _DefaultSize:
28 """A minimal "fake" dict that returns a constant size 1 for any key."""
30 __slots__ = ()
32 def __getitem__(self, _key):
33 return 1
35 def __setitem__(self, _key, _value):
36 pass
38 def pop(self, _key):
39 return 1
41 def clear(self):
42 pass
45class Cache(collections.abc.MutableMapping):
46 """Mutable mapping to serve as a simple cache or cache base class."""
48 __marker = object()
50 __size = _DefaultSize()
52 def __init__(self, maxsize, getsizeof=None):
53 if getsizeof:
54 self.getsizeof = getsizeof
55 if self.getsizeof is not Cache.getsizeof:
56 self.__size = dict()
57 self.__data = dict()
58 self.__currsize = 0
59 self.__maxsize = maxsize
61 def __repr__(self):
62 return "%s(%s, maxsize=%r, currsize=%r)" % (
63 type(self).__name__,
64 repr(self.__data),
65 self.__maxsize,
66 self.__currsize,
67 )
69 def __getitem__(self, key):
70 try:
71 return self.__data[key]
72 except KeyError:
73 return self.__missing__(key)
75 def __setitem__(self, key, value):
76 maxsize = self.__maxsize
77 size = self.getsizeof(value)
78 if size > maxsize:
79 raise ValueError("value too large")
80 if key not in self.__data or self.__size[key] < size:
81 while self.__currsize + size > maxsize:
82 self.popitem()
83 if key in self.__data:
84 diffsize = size - self.__size[key]
85 else:
86 diffsize = size
87 self.__data[key] = value
88 self.__size[key] = size
89 self.__currsize += diffsize
91 def __delitem__(self, key):
92 size = self.__size.pop(key)
93 del self.__data[key]
94 self.__currsize -= size
96 def __contains__(self, key):
97 return key in self.__data
99 def __missing__(self, key):
100 raise KeyError(key)
102 def __iter__(self):
103 return iter(self.__data)
105 def __len__(self):
106 return len(self.__data)
108 # Note that we cannot simply inherit get(), pop() and setdefault()
109 # from MutableMapping, since these rely on __getitem__ throwing a
110 # KeyError on cache miss. This is not the case if __missing__ is
111 # implemented for a Cache subclass, so we have to roll our own,
112 # somewhat less elegant versions.
114 def get(self, key, default=None):
115 if key in self:
116 return self[key]
117 else:
118 return default
120 def pop(self, key, default=__marker):
121 if key in self:
122 value = self[key]
123 del self[key]
124 elif default is self.__marker:
125 raise KeyError(key)
126 else:
127 value = default
128 return value
130 def setdefault(self, key, default=None):
131 if key in self:
132 value = self[key]
133 else:
134 self[key] = value = default
135 return value
137 # Although the MutableMapping.clear() default implementation works
138 # perfectly well, it calls popitem() in a loop until the cache is
139 # empty, resulting in O(n) complexity. For large caches, this
140 # becomes a significant performance bottleneck, so we provide an
141 # optimized version for each Cache subclass.
143 def clear(self):
144 self.__data.clear()
145 self.__size.clear()
146 self.__currsize = 0
148 @property
149 def maxsize(self):
150 """The maximum size of the cache."""
151 return self.__maxsize
153 @property
154 def currsize(self):
155 """The current size of the cache."""
156 return self.__currsize
158 @staticmethod
159 def getsizeof(value):
160 """Return the size of a cache element's value."""
161 return 1
164class FIFOCache(Cache):
165 """First In First Out (FIFO) cache implementation."""
167 def __init__(self, maxsize, getsizeof=None):
168 Cache.__init__(self, maxsize, getsizeof)
169 self.__order = collections.OrderedDict()
171 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
172 cache_setitem(self, key, value)
173 if key in self.__order:
174 self.__order.move_to_end(key)
175 else:
176 self.__order[key] = None
178 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
179 cache_delitem(self, key)
180 del self.__order[key]
182 def popitem(self):
183 """Remove and return the `(key, value)` pair first inserted."""
184 try:
185 key = next(iter(self.__order))
186 except StopIteration:
187 raise KeyError("%s is empty" % type(self).__name__) from None
188 else:
189 return (key, self.pop(key))
191 def clear(self):
192 Cache.clear(self)
193 self.__order.clear()
196class LFUCache(Cache):
197 """Least Frequently Used (LFU) cache implementation."""
199 class _Link:
200 __slots__ = ("count", "keys", "next", "prev")
202 def __init__(self, count):
203 self.count = count
204 self.keys = set()
206 def unlink(self):
207 next = self.next
208 prev = self.prev
209 prev.next = next
210 next.prev = prev
212 def __init__(self, maxsize, getsizeof=None):
213 Cache.__init__(self, maxsize, getsizeof)
214 self.__root = root = LFUCache._Link(0) # sentinel
215 root.prev = root.next = root
216 self.__links = {}
218 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
219 value = cache_getitem(self, key)
220 if key in self: # __missing__ may not store item
221 self.__touch(key)
222 return value
224 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
225 cache_setitem(self, key, value)
226 if key in self.__links:
227 self.__touch(key)
228 return
229 root = self.__root
230 link = root.next
231 if link.count != 1:
232 link = LFUCache._Link(1)
233 link.next = root.next
234 root.next = link.next.prev = link
235 link.prev = root
236 link.keys.add(key)
237 self.__links[key] = link
239 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
240 cache_delitem(self, key)
241 link = self.__links.pop(key)
242 link.keys.remove(key)
243 if not link.keys:
244 link.unlink()
246 def popitem(self):
247 """Remove and return the `(key, value)` pair least frequently used."""
248 root = self.__root
249 curr = root.next
250 if curr is root:
251 raise KeyError("%s is empty" % type(self).__name__) from None
252 key = next(iter(curr.keys)) # remove an arbitrary element
253 return (key, self.pop(key))
255 def clear(self):
256 Cache.clear(self)
257 root = self.__root
258 root.prev = root.next = root
259 self.__links.clear()
261 def __touch(self, key):
262 """Increment use count"""
263 link = self.__links[key]
264 curr = link.next
265 if curr.count != link.count + 1:
266 if len(link.keys) == 1:
267 link.count += 1
268 return
269 curr = LFUCache._Link(link.count + 1)
270 curr.next = link.next
271 link.next = curr.next.prev = curr
272 curr.prev = link
273 curr.keys.add(key)
274 link.keys.remove(key)
275 if not link.keys:
276 link.unlink()
277 self.__links[key] = curr
280class LRUCache(Cache):
281 """Least Recently Used (LRU) cache implementation."""
283 def __init__(self, maxsize, getsizeof=None):
284 Cache.__init__(self, maxsize, getsizeof)
285 self.__order = collections.OrderedDict()
287 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
288 value = cache_getitem(self, key)
289 if key in self: # __missing__ may not store item
290 self.__touch(key)
291 return value
293 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
294 cache_setitem(self, key, value)
295 self.__touch(key)
297 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
298 cache_delitem(self, key)
299 del self.__order[key]
301 def popitem(self):
302 """Remove and return the `(key, value)` pair least recently used."""
303 try:
304 key = next(iter(self.__order))
305 except StopIteration:
306 raise KeyError("%s is empty" % type(self).__name__) from None
307 else:
308 return (key, self.pop(key))
310 def clear(self):
311 Cache.clear(self)
312 self.__order.clear()
314 def __touch(self, key):
315 """Mark as recently used"""
316 try:
317 self.__order.move_to_end(key)
318 except KeyError:
319 self.__order[key] = None
322class RRCache(Cache):
323 """Random Replacement (RR) cache implementation."""
325 def __init__(self, maxsize, choice=random.choice, getsizeof=None):
326 Cache.__init__(self, maxsize, getsizeof)
327 self.__choice = choice
328 self.__index = {}
329 self.__keys = []
331 @property
332 def choice(self):
333 """The `choice` function used by the cache."""
334 return self.__choice
336 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
337 cache_setitem(self, key, value)
338 if key not in self.__index:
339 self.__index[key] = len(self.__keys)
340 self.__keys.append(key)
342 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
343 cache_delitem(self, key)
344 index = self.__index.pop(key)
345 if index != len(self.__keys) - 1:
346 last = self.__keys[-1]
347 self.__keys[index] = last
348 self.__index[last] = index
349 self.__keys.pop()
351 def popitem(self):
352 """Remove and return a random `(key, value)` pair."""
353 try:
354 key = self.__choice(self.__keys)
355 except IndexError:
356 raise KeyError("%s is empty" % type(self).__name__) from None
357 else:
358 return (key, self.pop(key))
360 def clear(self):
361 Cache.clear(self)
362 self.__index.clear()
363 del self.__keys[:]
366class _TimedCache(Cache):
367 """Base class for time aware cache implementations."""
369 class _Timer:
370 def __init__(self, timer):
371 self.__timer = timer
372 self.__nesting = 0
374 def __call__(self):
375 if self.__nesting == 0:
376 return self.__timer()
377 else:
378 return self.__time
380 def __enter__(self):
381 if self.__nesting == 0:
382 self.__time = time = self.__timer()
383 else:
384 time = self.__time
385 self.__nesting += 1
386 return time
388 def __exit__(self, *exc):
389 self.__nesting -= 1
391 def __reduce__(self):
392 return _TimedCache._Timer, (self.__timer,)
394 def __getattr__(self, name):
395 return getattr(self.__timer, name)
397 def __init__(self, maxsize, timer, getsizeof=None):
398 Cache.__init__(self, maxsize, getsizeof)
399 self.__timer = _TimedCache._Timer(timer)
401 def __repr__(self, cache_repr=Cache.__repr__):
402 with self.__timer as time:
403 self.expire(time)
404 return cache_repr(self)
406 def __len__(self, cache_len=Cache.__len__):
407 with self.__timer as time:
408 self.expire(time)
409 return cache_len(self)
411 @property
412 def currsize(self):
413 with self.__timer as time:
414 self.expire(time)
415 return super().currsize
417 @property
418 def timer(self):
419 """The timer function used by the cache."""
420 return self.__timer
422 def get(self, *args, **kwargs):
423 with self.__timer:
424 return Cache.get(self, *args, **kwargs)
426 def pop(self, *args, **kwargs):
427 with self.__timer:
428 return Cache.pop(self, *args, **kwargs)
430 def setdefault(self, *args, **kwargs):
431 with self.__timer:
432 return Cache.setdefault(self, *args, **kwargs)
434 def clear(self):
435 # Subclasses must override to also reset their own time-tracking
436 # structures; we do not call expire() here since clear() should
437 # be O(1) regardless of cache contents.
438 Cache.clear(self)
440 def expire(self, time=None): # pragma: no cover
441 raise NotImplementedError
444class TTLCache(_TimedCache):
445 """LRU Cache implementation with per-item time-to-live (TTL) value."""
447 class _Link:
448 __slots__ = ("key", "expires", "next", "prev")
450 def __init__(self, key=None, expires=None):
451 self.key = key
452 self.expires = expires
454 def __reduce__(self):
455 return TTLCache._Link, (self.key, self.expires)
457 def unlink(self):
458 next = self.next
459 prev = self.prev
460 prev.next = next
461 next.prev = prev
463 def __init__(self, maxsize, ttl, timer=time.monotonic, getsizeof=None):
464 _TimedCache.__init__(self, maxsize, timer, getsizeof)
465 self.__root = root = TTLCache._Link()
466 root.prev = root.next = root
467 self.__links = collections.OrderedDict()
468 self.__ttl = ttl
470 def __contains__(self, key):
471 try:
472 link = self.__links[key] # no reordering
473 except KeyError:
474 return False
475 else:
476 return self.timer() < link.expires
478 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
479 try:
480 link = self.__getlink(key)
481 except KeyError:
482 expired = False
483 else:
484 expired = not (self.timer() < link.expires)
485 if expired:
486 return self.__missing__(key)
487 else:
488 return cache_getitem(self, key)
490 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
491 with self.timer as time:
492 self.expire(time)
493 cache_setitem(self, key, value)
494 try:
495 link = self.__getlink(key)
496 except KeyError:
497 self.__links[key] = link = TTLCache._Link(key)
498 else:
499 link.unlink()
500 link.expires = time + self.__ttl
501 link.next = root = self.__root
502 link.prev = prev = root.prev
503 prev.next = root.prev = link
505 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
506 cache_delitem(self, key)
507 link = self.__links.pop(key)
508 link.unlink()
509 if not (self.timer() < link.expires):
510 raise KeyError(key)
512 def __iter__(self):
513 root = self.__root
514 curr = root.next
515 while curr is not root:
516 # "freeze" time for iterator access
517 with self.timer as time:
518 if time < curr.expires:
519 yield curr.key
520 curr = curr.next
522 def __setstate__(self, state):
523 self.__dict__.update(state)
524 root = self.__root
525 root.prev = root.next = root
526 for link in sorted(self.__links.values(), key=lambda obj: obj.expires):
527 link.next = root
528 link.prev = prev = root.prev
529 prev.next = root.prev = link
530 self.expire(self.timer())
532 @property
533 def ttl(self):
534 """The time-to-live value of the cache's items."""
535 return self.__ttl
537 def expire(self, time=None):
538 """Remove expired items from the cache and return an iterable of the
539 expired `(key, value)` pairs.
541 """
542 if time is None:
543 time = self.timer()
544 root = self.__root
545 curr = root.next
546 links = self.__links
547 expired = []
548 cache_delitem = Cache.__delitem__
549 cache_getitem = Cache.__getitem__
550 while curr is not root and not (time < curr.expires):
551 expired.append((curr.key, cache_getitem(self, curr.key)))
552 cache_delitem(self, curr.key)
553 del links[curr.key]
554 next = curr.next
555 curr.unlink()
556 curr = next
557 return expired
559 def popitem(self):
560 """Remove and return the `(key, value)` pair least recently used that
561 has not already expired.
563 """
564 with self.timer as time:
565 self.expire(time)
566 try:
567 key = next(iter(self.__links))
568 except StopIteration:
569 raise KeyError("%s is empty" % type(self).__name__) from None
570 else:
571 return (key, self.pop(key))
573 def clear(self):
574 _TimedCache.clear(self)
575 root = self.__root
576 root.prev = root.next = root
577 self.__links.clear()
579 def __getlink(self, key):
580 value = self.__links[key]
581 self.__links.move_to_end(key)
582 return value
585class TLRUCache(_TimedCache):
586 """Time aware Least Recently Used (TLRU) cache implementation."""
588 __HEAP_CLEANUP_FACTOR = 2 # clean up the heap if size > N * len(items)
590 @functools.total_ordering
591 class _Item:
592 __slots__ = ("key", "expires", "removed")
594 def __init__(self, key=None, expires=None):
595 self.key = key
596 self.expires = expires
597 self.removed = False
599 def __lt__(self, other):
600 return self.expires < other.expires
602 def __init__(self, maxsize, ttu, timer=time.monotonic, getsizeof=None):
603 _TimedCache.__init__(self, maxsize, timer, getsizeof)
604 self.__items = collections.OrderedDict()
605 self.__order = []
606 self.__ttu = ttu
608 def __contains__(self, key):
609 try:
610 item = self.__items[key] # no reordering
611 except KeyError:
612 return False
613 else:
614 return self.timer() < item.expires
616 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
617 try:
618 item = self.__getitem(key)
619 except KeyError:
620 expired = False
621 else:
622 expired = not (self.timer() < item.expires)
623 if expired:
624 return self.__missing__(key)
625 else:
626 return cache_getitem(self, key)
628 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
629 with self.timer as time:
630 expires = self.__ttu(key, value, time)
631 if not (time < expires):
632 return # skip expired items
633 self.expire(time)
634 cache_setitem(self, key, value)
635 # removing an existing item would break the heap structure, so
636 # only mark it as removed for now
637 try:
638 self.__getitem(key).removed = True
639 except KeyError:
640 pass
641 self.__items[key] = item = TLRUCache._Item(key, expires)
642 heapq.heappush(self.__order, item)
644 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
645 with self.timer as time:
646 # no self.expire() for performance reasons, e.g. self.clear() [#67]
647 cache_delitem(self, key)
648 item = self.__items.pop(key)
649 item.removed = True
650 if not (time < item.expires):
651 raise KeyError(key)
653 def __iter__(self):
654 for curr in self.__order:
655 # "freeze" time for iterator access
656 with self.timer as time:
657 if time < curr.expires and not curr.removed:
658 yield curr.key
660 @property
661 def ttu(self):
662 """The local time-to-use function used by the cache."""
663 return self.__ttu
665 def expire(self, time=None):
666 """Remove expired items from the cache and return an iterable of the
667 expired `(key, value)` pairs.
669 """
670 if time is None:
671 time = self.timer()
672 items = self.__items
673 order = self.__order
674 # clean up the heap if too many items are marked as removed
675 if len(order) > len(items) * self.__HEAP_CLEANUP_FACTOR:
676 self.__order = order = [item for item in order if not item.removed]
677 heapq.heapify(order)
678 expired = []
679 cache_delitem = Cache.__delitem__
680 cache_getitem = Cache.__getitem__
681 while order and (order[0].removed or not (time < order[0].expires)):
682 item = heapq.heappop(order)
683 if not item.removed:
684 expired.append((item.key, cache_getitem(self, item.key)))
685 cache_delitem(self, item.key)
686 del items[item.key]
687 return expired
689 def popitem(self):
690 """Remove and return the `(key, value)` pair least recently used that
691 has not already expired.
693 """
694 with self.timer as time:
695 self.expire(time)
696 try:
697 key = next(iter(self.__items))
698 except StopIteration:
699 raise KeyError("%s is empty" % type(self).__name__) from None
700 else:
701 return (key, self.pop(key))
703 def clear(self):
704 _TimedCache.clear(self)
705 self.__items.clear()
706 del self.__order[:]
708 def __getitem(self, key):
709 value = self.__items[key]
710 self.__items.move_to_end(key)
711 return value
714# note that the runtime __name__ is "CacheInfo", as in stdlib:
715# https://github.com/python/cpython/blob/3.14/Lib/functools.py#L520
716_CacheInfo = collections.namedtuple(
717 "CacheInfo", ["hits", "misses", "maxsize", "currsize"]
718)
721def cached(cache, key=keys.hashkey, lock=None, condition=None, info=False):
722 """Decorator to wrap a function with a memoizing callable that saves
723 results in a cache.
725 """
726 from ._cached import _wrapper
728 def decorator(func):
729 if info:
730 if isinstance(cache, Cache):
732 def make_info(hits, misses):
733 return _CacheInfo(hits, misses, cache.maxsize, cache.currsize)
735 elif isinstance(cache, collections.abc.Mapping):
737 def make_info(hits, misses):
738 return _CacheInfo(hits, misses, None, len(cache))
740 else:
742 def make_info(hits, misses):
743 return _CacheInfo(hits, misses, 0, 0)
745 return _wrapper(func, cache, key, lock, condition, info=make_info)
746 else:
747 return _wrapper(func, cache, key, lock, condition)
749 return decorator
752def cachedmethod(cache, key=keys.methodkey, lock=None, condition=None, info=False):
753 """Decorator to wrap a method with a memoizing callable that saves
754 results in a cache.
756 """
757 from ._cachedmethod import _wrapper
759 def decorator(method):
760 if info:
762 def make_info(cache, hits, misses):
763 if isinstance(cache, Cache):
764 return _CacheInfo(hits, misses, cache.maxsize, cache.currsize)
765 elif isinstance(cache, collections.abc.Mapping):
766 return _CacheInfo(hits, misses, None, len(cache))
767 else:
768 raise TypeError("cache(self) must return a mutable mapping")
770 return _wrapper(method, cache, key, lock, condition, info=make_info)
771 else:
772 return _wrapper(method, cache, key, lock, condition)
774 return decorator