Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/cachetools/__init__.py: 73%
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 "CacheInfo",
6 "FIFOCache",
7 "LFUCache",
8 "LRUCache",
9 "RRCache",
10 "TLRUCache",
11 "TTLCache",
12 "cached",
13 "cachedmethod",
14)
16__version__ = "8.0.0"
18import collections
19import collections.abc
20import functools
21import heapq
22import random
23import time
25from . import keys
28class Cache(collections.abc.MutableMapping):
29 """Mutable mapping to serve as a simple cache or cache base class."""
31 __marker = object()
33 __size = None
35 def __init__(self, maxsize, getsizeof=None):
36 if maxsize < 0:
37 raise ValueError("maxsize must be non-negative")
38 if getsizeof is not None:
39 self.getsizeof = getsizeof
40 if self.getsizeof is not Cache.getsizeof:
41 self.__size = {}
42 self.__data = {}
43 self.__currsize = 0
44 self.__maxsize = maxsize
46 def __repr__(self):
47 return "%s(%s, maxsize=%r, currsize=%r)" % (
48 type(self).__name__,
49 repr(self.__data),
50 self.__maxsize,
51 self.__currsize,
52 )
54 def __getitem__(self, key):
55 try:
56 return self.__data[key]
57 except KeyError:
58 return self.__missing__(key)
60 def __setitem__(self, key, value):
61 data = self.__data
62 size = self.__size
63 maxsize = self.__maxsize
64 if size is None:
65 if maxsize < 1:
66 raise ValueError("value too large")
67 elif key in data:
68 data[key] = value
69 else:
70 while self.__currsize + 1 > maxsize:
71 self.popitem()
72 data[key] = value
73 self.__currsize += 1
74 else:
75 itemsize = self.getsizeof(value)
76 if itemsize > maxsize:
77 raise ValueError("value too large")
78 if itemsize < 0:
79 raise ValueError("value size must be non-negative")
80 if key not in data:
81 diffsize = itemsize
82 while self.__currsize + diffsize > maxsize:
83 self.popitem()
84 else:
85 diffsize = itemsize - size[key]
86 while self.__currsize + diffsize > maxsize:
87 self.popitem()
88 if key not in data:
89 diffsize = itemsize
90 data[key] = value
91 size[key] = itemsize
92 self.__currsize += diffsize
94 def __delitem__(self, key):
95 size = self.__size
96 if size is None:
97 del self.__data[key]
98 self.__currsize -= 1
99 else:
100 itemsize = size.pop(key)
101 del self.__data[key]
102 self.__currsize -= itemsize
104 def __contains__(self, key):
105 return key in self.__data
107 def __missing__(self, key):
108 raise KeyError(key)
110 def __iter__(self):
111 return iter(self.__data)
113 def __len__(self):
114 return len(self.__data)
116 # Note that we cannot simply inherit get(), pop() and setdefault()
117 # from MutableMapping, since these rely on __getitem__ throwing a
118 # KeyError on cache miss. This is not the case if __missing__ is
119 # implemented for a Cache subclass, so we have to roll our own,
120 # somewhat less elegant versions.
122 def get(self, key, default=None):
123 if key in self:
124 return self[key]
125 else:
126 return default
128 def pop(self, key, default=__marker):
129 if key in self:
130 value = self[key]
131 del self[key]
132 elif default is self.__marker:
133 raise KeyError(key)
134 else:
135 value = default
136 return value
138 def setdefault(self, key, default=None):
139 if key in self:
140 value = self[key]
141 else:
142 self[key] = value = default
143 return value
145 # Although the MutableMapping.clear() default implementation works
146 # perfectly well, it calls popitem() in a loop until the cache is
147 # empty, resulting in O(n) complexity. For large caches, this
148 # becomes a significant performance bottleneck, so we provide an
149 # optimized version for each Cache subclass.
151 def clear(self):
152 size = self.__size
153 if size is not None:
154 size.clear()
155 self.__data.clear()
156 self.__currsize = 0
158 @property
159 def maxsize(self):
160 """The maximum size of the cache."""
161 return self.__maxsize
163 @property
164 def currsize(self):
165 """The current size of the cache."""
166 return self.__currsize
168 @staticmethod
169 def getsizeof(value):
170 """Return the size of a cache element's value."""
171 return 1
174class FIFOCache(Cache):
175 """First In First Out (FIFO) cache implementation."""
177 def __init__(self, maxsize, getsizeof=None):
178 Cache.__init__(self, maxsize, getsizeof)
179 self.__order = collections.OrderedDict()
181 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
182 cache_setitem(self, key, value)
183 if key in self.__order:
184 self.__order.move_to_end(key)
185 else:
186 self.__order[key] = None
188 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
189 cache_delitem(self, key)
190 del self.__order[key]
192 def popitem(self):
193 """Remove and return the `(key, value)` pair first inserted."""
194 try:
195 key = next(iter(self.__order))
196 except StopIteration:
197 raise KeyError("%s is empty" % type(self).__name__) from None
198 else:
199 value = Cache.__getitem__(self, key)
200 del self[key]
201 return (key, value)
203 def clear(self):
204 Cache.clear(self)
205 self.__order.clear()
208class LFUCache(Cache):
209 """Least Frequently Used (LFU) cache implementation."""
211 class _Link:
212 __slots__ = ("count", "keys", "next", "prev")
214 def __init__(self, count):
215 self.count = count
216 self.keys = collections.OrderedDict()
218 def unlink(self):
219 next = self.next
220 prev = self.prev
221 prev.next = next
222 next.prev = prev
224 def __init__(self, maxsize, getsizeof=None):
225 Cache.__init__(self, maxsize, getsizeof)
226 self.__root = root = LFUCache._Link(0) # sentinel
227 root.prev = root.next = root
228 self.__links = {}
230 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
231 value = cache_getitem(self, key)
232 if key in self.__links: # __missing__ may not store item
233 self.__touch(key)
234 return value
236 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
237 cache_setitem(self, key, value)
238 if key in self.__links:
239 self.__touch(key)
240 return
241 root = self.__root
242 link = root.next
243 if link.count != 1:
244 link = LFUCache._Link(1)
245 link.next = root.next
246 root.next = link.next.prev = link
247 link.prev = root
248 link.keys[key] = None
249 self.__links[key] = link
251 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
252 cache_delitem(self, key)
253 link = self.__links.pop(key)
254 del link.keys[key]
255 if not link.keys:
256 link.unlink()
258 def popitem(self):
259 """Remove and return the `(key, value)` pair least frequently used."""
260 root = self.__root
261 curr = root.next
262 if curr is root:
263 raise KeyError("%s is empty" % type(self).__name__) from None
264 key = next(iter(curr.keys)) # remove the "oldest" element
265 value = Cache.__getitem__(self, key)
266 del self[key]
267 return (key, value)
269 def clear(self):
270 Cache.clear(self)
271 root = self.__root
272 root.prev = root.next = root
273 self.__links.clear()
275 def __touch(self, key):
276 """Increment use count."""
277 link = self.__links[key]
278 curr = link.next
279 if curr.count != link.count + 1:
280 if len(link.keys) == 1:
281 link.count += 1
282 return
283 curr = LFUCache._Link(link.count + 1)
284 curr.next = link.next
285 link.next = curr.next.prev = curr
286 curr.prev = link
287 curr.keys[key] = None
288 del link.keys[key]
289 if not link.keys:
290 link.unlink()
291 self.__links[key] = curr
294class LRUCache(Cache):
295 """Least Recently Used (LRU) cache implementation."""
297 def __init__(self, maxsize, getsizeof=None):
298 Cache.__init__(self, maxsize, getsizeof)
299 self.__order = collections.OrderedDict()
301 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
302 value = cache_getitem(self, key)
303 try:
304 self.__order.move_to_end(key)
305 except KeyError: # __missing__ may not store item
306 pass
307 return value
309 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
310 cache_setitem(self, key, value)
311 self.__touch(key)
313 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
314 cache_delitem(self, key)
315 del self.__order[key]
317 def popitem(self):
318 """Remove and return the `(key, value)` pair least recently used."""
319 try:
320 key = next(iter(self.__order))
321 except StopIteration:
322 raise KeyError("%s is empty" % type(self).__name__) from None
323 else:
324 value = Cache.__getitem__(self, key)
325 del self[key]
326 return (key, value)
328 def clear(self):
329 Cache.clear(self)
330 self.__order.clear()
332 def __touch(self, key):
333 """Mark as recently used."""
334 try:
335 self.__order.move_to_end(key)
336 except KeyError:
337 self.__order[key] = None
340class RRCache(Cache):
341 """Random Replacement (RR) cache implementation."""
343 def __init__(self, maxsize, choice=random.choice, getsizeof=None):
344 Cache.__init__(self, maxsize, getsizeof)
345 self.__choice = choice
346 self.__index = {}
347 self.__keys = []
349 @property
350 def choice(self):
351 """The `choice` function used by the cache."""
352 return self.__choice
354 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
355 cache_setitem(self, key, value)
356 if key not in self.__index:
357 self.__index[key] = len(self.__keys)
358 self.__keys.append(key)
360 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
361 cache_delitem(self, key)
362 index = self.__index.pop(key)
363 if index != len(self.__keys) - 1:
364 last = self.__keys[-1]
365 self.__keys[index] = last
366 self.__index[last] = index
367 self.__keys.pop()
369 def popitem(self):
370 """Remove and return a random `(key, value)` pair."""
371 keys = self.__keys
372 if not keys:
373 raise KeyError("%s is empty" % type(self).__name__) from None
374 key = self.__choice(keys)
375 value = Cache.__getitem__(self, key)
376 del self[key]
377 return (key, value)
379 def clear(self):
380 Cache.clear(self)
381 self.__index.clear()
382 del self.__keys[:]
385class _TimedCache(Cache):
386 """Base class for time-aware cache implementations."""
388 class _Timer:
389 def __init__(self, timer):
390 self.__timer = timer
391 self.__nesting = 0
393 def __call__(self):
394 if self.__nesting == 0:
395 return self.__timer()
396 else:
397 return self.__time
399 def __enter__(self):
400 if self.__nesting == 0:
401 self.__time = time = self.__timer()
402 else:
403 time = self.__time
404 self.__nesting += 1
405 return time
407 def __exit__(self, *exc):
408 self.__nesting -= 1
410 def __reduce__(self):
411 return _TimedCache._Timer, (self.__timer,)
413 def __getattr__(self, name):
414 return getattr(self.__timer, name)
416 def __init__(self, maxsize, timer, getsizeof=None):
417 Cache.__init__(self, maxsize, getsizeof)
418 self.__timer = _TimedCache._Timer(timer)
420 def __repr__(self, cache_repr=Cache.__repr__):
421 with self.__timer as time:
422 self.expire(time)
423 return cache_repr(self)
425 def __len__(self, cache_len=Cache.__len__):
426 with self.__timer as time:
427 self.expire(time)
428 return cache_len(self)
430 @property
431 def currsize(self):
432 with self.__timer as time:
433 self.expire(time)
434 return super().currsize
436 @property
437 def timer(self):
438 """The timer function used by the cache."""
439 return self.__timer
441 def get(self, *args, **kwargs):
442 with self.__timer:
443 return Cache.get(self, *args, **kwargs)
445 def pop(self, *args, **kwargs):
446 with self.__timer:
447 return Cache.pop(self, *args, **kwargs)
449 def setdefault(self, *args, **kwargs):
450 with self.__timer:
451 return Cache.setdefault(self, *args, **kwargs)
453 def clear(self):
454 # Subclasses must override to also reset their own time-tracking
455 # structures; we do not call expire() here since clear() should
456 # be O(1) regardless of cache contents.
457 Cache.clear(self)
459 def expire(self, time=None): # pragma: no cover
460 raise NotImplementedError
463class TTLCache(_TimedCache):
464 """LRU Cache implementation with per-item time-to-live (TTL) value."""
466 class _Link:
467 __slots__ = ("expires", "key", "next", "prev")
469 def __init__(self, key=None, expires=None):
470 self.key = key
471 self.expires = expires
473 def __reduce__(self):
474 return TTLCache._Link, (self.key, self.expires)
476 def unlink(self):
477 next = self.next
478 prev = self.prev
479 prev.next = next
480 next.prev = prev
482 def __init__(self, maxsize, ttl, timer=time.monotonic, getsizeof=None):
483 _TimedCache.__init__(self, maxsize, timer, getsizeof)
484 self.__root = root = TTLCache._Link()
485 root.prev = root.next = root
486 self.__links = collections.OrderedDict()
487 self.__ttl = ttl
489 def __contains__(self, key):
490 try:
491 link = self.__links[key] # no reordering
492 except KeyError:
493 return False
494 else:
495 return self.timer() < link.expires
497 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
498 links = self.__links
499 try:
500 link = links[key]
501 except KeyError:
502 return cache_getitem(self, key)
503 links.move_to_end(key)
504 if self.timer() < link.expires:
505 return cache_getitem(self, key)
506 else:
507 return self.__missing__(key)
509 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
510 with self.timer as time:
511 expires = time + self.__ttl
512 self.expire(time)
513 cache_setitem(self, key, value)
514 links = self.__links
515 link = links.get(key)
516 if link is None:
517 links[key] = link = TTLCache._Link(key)
518 else:
519 links.move_to_end(key)
520 link.unlink()
521 link.expires = expires
522 link.next = root = self.__root
523 link.prev = prev = root.prev
524 prev.next = root.prev = link
526 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
527 cache_delitem(self, key)
528 link = self.__links.pop(key)
529 link.unlink()
530 if not (self.timer() < link.expires):
531 raise KeyError(key)
533 def __iter__(self):
534 root = self.__root
535 curr = root.next
536 while curr is not root:
537 # "freeze" time for iterator access
538 with self.timer as time:
539 if time < curr.expires:
540 yield curr.key
541 curr = curr.next
543 def __setstate__(self, state):
544 self.__dict__.update(state)
545 root = self.__root
546 root.prev = root.next = root
547 for link in sorted(self.__links.values(), key=lambda obj: obj.expires):
548 link.next = root
549 link.prev = prev = root.prev
550 prev.next = root.prev = link
551 self.expire(self.timer())
553 @property
554 def ttl(self):
555 """The time-to-live value of the cache's items."""
556 return self.__ttl
558 def expire(self, time=None):
559 """Remove expired items from the cache and return an iterable of the
560 expired `(key, value)` pairs.
562 """
563 if time is None:
564 time = self.timer()
565 root = self.__root
566 curr = root.next
567 if curr is root or time < curr.expires:
568 return [] # fast path: nothing has expired
569 links = self.__links
570 expired = []
571 cache_delitem = Cache.__delitem__
572 cache_getitem = Cache.__getitem__
573 while curr is not root and not (time < curr.expires):
574 expired.append((curr.key, cache_getitem(self, curr.key)))
575 cache_delitem(self, curr.key)
576 del links[curr.key]
577 next = curr.next
578 curr.unlink()
579 curr = next
580 return expired
582 def popitem(self):
583 """Remove and return the `(key, value)` pair least recently used that
584 has not already expired.
586 """
587 with self.timer as time:
588 self.expire(time)
589 try:
590 key = next(iter(self.__links))
591 except StopIteration:
592 raise KeyError("%s is empty" % type(self).__name__) from None
593 else:
594 value = Cache.__getitem__(self, key)
595 del self[key]
596 return (key, value)
598 def clear(self):
599 _TimedCache.clear(self)
600 root = self.__root
601 root.prev = root.next = root
602 self.__links.clear()
605class TLRUCache(_TimedCache):
606 """Time-aware Least Recently Used (TLRU) cache implementation."""
608 __HEAP_CLEANUP_FACTOR = 2 # clean up the heap if size > N * len(items)
610 @functools.total_ordering
611 class _Item:
612 __slots__ = ("expires", "key", "removed")
614 def __init__(self, key=None, expires=None):
615 self.key = key
616 self.expires = expires
617 self.removed = False
619 def __lt__(self, other):
620 return self.expires < other.expires
622 def __init__(self, maxsize, ttu, timer=time.monotonic, getsizeof=None):
623 _TimedCache.__init__(self, maxsize, timer, getsizeof)
624 self.__items = collections.OrderedDict()
625 self.__order = []
626 self.__ttu = ttu
628 def __contains__(self, key):
629 try:
630 item = self.__items[key] # no reordering
631 except KeyError:
632 return False
633 else:
634 return self.timer() < item.expires
636 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
637 items = self.__items
638 try:
639 item = items[key]
640 except KeyError:
641 return cache_getitem(self, key)
642 items.move_to_end(key)
643 if self.timer() < item.expires:
644 return cache_getitem(self, key)
645 else:
646 return self.__missing__(key)
648 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
649 with self.timer as time:
650 self.expire(time)
651 expires = self.__ttu(key, value, time)
652 if not (time < expires):
653 # updating an existing item with an already expired
654 # one should remove the existing item
655 return self.__delitem(key)
656 cache_setitem(self, key, value)
657 # removing an existing item would break the heap structure, so
658 # only mark it as removed for now
659 items = self.__items
660 item = items.get(key)
661 if item is not None:
662 item.removed = True
663 items.move_to_end(key)
664 items[key] = item = TLRUCache._Item(key, expires)
665 heapq.heappush(self.__order, item)
667 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
668 with self.timer as time:
669 # no self.expire() for performance reasons, e.g. self.clear() [#67]
670 cache_delitem(self, key)
671 item = self.__items.pop(key)
672 item.removed = True
673 if not (time < item.expires):
674 raise KeyError(key)
676 def __iter__(self):
677 for curr in self.__order:
678 # "freeze" time for iterator access
679 with self.timer as time:
680 if time < curr.expires and not curr.removed:
681 yield curr.key
683 @property
684 def ttu(self):
685 """The time-to-use function used by the cache."""
686 return self.__ttu
688 def expire(self, time=None):
689 """Remove expired items from the cache and return an iterable of the
690 expired `(key, value)` pairs.
692 """
693 if time is None:
694 time = self.timer()
695 items = self.__items
696 order = self.__order
697 # clean up the heap if too many items are marked as removed
698 if len(order) > len(items) * self.__HEAP_CLEANUP_FACTOR:
699 self.__order = order = [item for item in order if not item.removed]
700 heapq.heapify(order)
701 if not order or (not order[0].removed and time < order[0].expires):
702 return [] # fast path: nothing has expired
703 expired = []
704 cache_delitem = Cache.__delitem__
705 cache_getitem = Cache.__getitem__
706 while order and (order[0].removed or not (time < order[0].expires)):
707 item = heapq.heappop(order)
708 if not item.removed:
709 expired.append((item.key, cache_getitem(self, item.key)))
710 cache_delitem(self, item.key)
711 del items[item.key]
712 return expired
714 def popitem(self):
715 """Remove and return the `(key, value)` pair least recently used that
716 has not already expired.
718 """
719 with self.timer as time:
720 self.expire(time)
721 try:
722 key = next(iter(self.__items))
723 except StopIteration:
724 raise KeyError("%s is empty" % type(self).__name__) from None
725 else:
726 value = Cache.__getitem__(self, key)
727 del self[key]
728 return (key, value)
730 def clear(self):
731 _TimedCache.clear(self)
732 self.__items.clear()
733 del self.__order[:]
735 def __delitem(self, key, cache_delitem=Cache.__delitem__):
736 try:
737 self.__items.pop(key).removed = True
738 except KeyError:
739 pass
740 else:
741 cache_delitem(self, key)
744class CacheInfo(collections.namedtuple("CacheInfo", "hits misses maxsize currsize")):
745 """Named tuple holding cache statistics."""
747 __slots__ = ()
749 @classmethod
750 def _make_info(cls, cache, hits, misses):
751 if isinstance(cache, Cache):
752 return cls(hits, misses, cache.maxsize, cache.currsize)
753 else:
754 return cls(hits, misses, None, len(cache))
757def cached(cache, key=keys.hashkey, lock=None, condition=None, info=False):
758 """Decorator to wrap a function with a memoizing callable that saves
759 results in a cache.
761 """
762 from ._cached import _wrapper
764 if cache is None: # no longer supported since v8.0.0
765 raise TypeError("cache must not be None")
767 def decorator(func):
768 make_info = CacheInfo._make_info if info else None
769 return _wrapper(func, cache, key, lock, condition, make_info)
771 return decorator
774def cachedmethod(cache, key=keys.methodkey, lock=None, condition=None, info=False):
775 """Decorator to wrap a method with a memoizing callable that saves
776 results in a cache.
778 """
779 from ._cachedmethod import _wrapper
781 def decorator(method):
782 make_info = CacheInfo._make_info if info else None
783 return _wrapper(method, cache, key, lock, condition, make_info)
785 return decorator