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.0.5"
17import collections
18import collections.abc
19import functools
20import heapq
21import random
22import time
24from . import keys
26# Typing stubs for this package are provided by typeshed:
27# https://github.com/python/typeshed/tree/main/stubs/cachetools
30class _DefaultSize:
31 """A minimal "fake" dict that returns a constant size 1 for any key."""
33 __slots__ = ()
35 def __getitem__(self, _key):
36 return 1
38 def __setitem__(self, _key, _value):
39 pass
41 def pop(self, _key):
42 return 1
44 def clear(self):
45 pass
48class Cache(collections.abc.MutableMapping):
49 """Mutable mapping to serve as a simple cache or cache base class."""
51 __marker = object()
53 __size = _DefaultSize()
55 def __init__(self, maxsize, getsizeof=None):
56 if getsizeof:
57 self.getsizeof = getsizeof
58 if self.getsizeof is not Cache.getsizeof:
59 self.__size = dict()
60 self.__data = dict()
61 self.__currsize = 0
62 self.__maxsize = maxsize
64 def __repr__(self):
65 return "%s(%s, maxsize=%r, currsize=%r)" % (
66 type(self).__name__,
67 repr(self.__data),
68 self.__maxsize,
69 self.__currsize,
70 )
72 def __getitem__(self, key):
73 try:
74 return self.__data[key]
75 except KeyError:
76 return self.__missing__(key)
78 def __setitem__(self, key, value):
79 maxsize = self.__maxsize
80 size = self.getsizeof(value)
81 if size > maxsize:
82 raise ValueError("value too large")
83 if key not in self.__data or self.__size[key] < size:
84 while self.__currsize + size > maxsize:
85 self.popitem()
86 if key in self.__data:
87 diffsize = size - self.__size[key]
88 else:
89 diffsize = size
90 self.__data[key] = value
91 self.__size[key] = size
92 self.__currsize += diffsize
94 def __delitem__(self, key):
95 size = self.__size.pop(key)
96 del self.__data[key]
97 self.__currsize -= size
99 def __contains__(self, key):
100 return key in self.__data
102 def __missing__(self, key):
103 raise KeyError(key)
105 def __iter__(self):
106 return iter(self.__data)
108 def __len__(self):
109 return len(self.__data)
111 # Note that we cannot simply inherit get(), pop() and setdefault()
112 # from MutableMapping, since these rely on __getitem__ throwing a
113 # KeyError on cache miss. This is not the case if __missing__ is
114 # implemented for a Cache subclass, so we have to roll our own,
115 # somewhat less elegant versions.
117 def get(self, key, default=None):
118 if key in self:
119 return self[key]
120 else:
121 return default
123 def pop(self, key, default=__marker):
124 if key in self:
125 value = self[key]
126 del self[key]
127 elif default is self.__marker:
128 raise KeyError(key)
129 else:
130 value = default
131 return value
133 def setdefault(self, key, default=None):
134 if key in self:
135 value = self[key]
136 else:
137 self[key] = value = default
138 return value
140 # Although the MutableMapping.clear() default implementation works
141 # perfectly well, it calls popitem() in a loop until the cache is
142 # empty, resulting in O(n) complexity. For large caches, this
143 # becomes a significant performance bottleneck, so we provide an
144 # optimized version for each Cache subclass.
146 def clear(self):
147 self.__data.clear()
148 self.__size.clear()
149 self.__currsize = 0
151 @property
152 def maxsize(self):
153 """The maximum size of the cache."""
154 return self.__maxsize
156 @property
157 def currsize(self):
158 """The current size of the cache."""
159 return self.__currsize
161 @staticmethod
162 def getsizeof(value):
163 """Return the size of a cache element's value."""
164 return 1
167class FIFOCache(Cache):
168 """First In First Out (FIFO) cache implementation."""
170 def __init__(self, maxsize, getsizeof=None):
171 Cache.__init__(self, maxsize, getsizeof)
172 self.__order = collections.OrderedDict()
174 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
175 cache_setitem(self, key, value)
176 if key in self.__order:
177 self.__order.move_to_end(key)
178 else:
179 self.__order[key] = None
181 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
182 cache_delitem(self, key)
183 del self.__order[key]
185 def popitem(self):
186 """Remove and return the `(key, value)` pair first inserted."""
187 try:
188 key = next(iter(self.__order))
189 except StopIteration:
190 raise KeyError("%s is empty" % type(self).__name__) from None
191 else:
192 return (key, self.pop(key))
194 def clear(self):
195 Cache.clear(self)
196 self.__order.clear()
199class LFUCache(Cache):
200 """Least Frequently Used (LFU) cache implementation."""
202 class _Link:
203 __slots__ = ("count", "keys", "next", "prev")
205 def __init__(self, count):
206 self.count = count
207 self.keys = set()
209 def unlink(self):
210 next = self.next
211 prev = self.prev
212 prev.next = next
213 next.prev = prev
215 def __init__(self, maxsize, getsizeof=None):
216 Cache.__init__(self, maxsize, getsizeof)
217 self.__root = root = LFUCache._Link(0) # sentinel
218 root.prev = root.next = root
219 self.__links = {}
221 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
222 value = cache_getitem(self, key)
223 if key in self: # __missing__ may not store item
224 self.__touch(key)
225 return value
227 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
228 cache_setitem(self, key, value)
229 if key in self.__links:
230 self.__touch(key)
231 return
232 root = self.__root
233 link = root.next
234 if link.count != 1:
235 link = LFUCache._Link(1)
236 link.next = root.next
237 root.next = link.next.prev = link
238 link.prev = root
239 link.keys.add(key)
240 self.__links[key] = link
242 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
243 cache_delitem(self, key)
244 link = self.__links.pop(key)
245 link.keys.remove(key)
246 if not link.keys:
247 link.unlink()
249 def popitem(self):
250 """Remove and return the `(key, value)` pair least frequently used."""
251 root = self.__root
252 curr = root.next
253 if curr is root:
254 raise KeyError("%s is empty" % type(self).__name__) from None
255 key = next(iter(curr.keys)) # remove an arbitrary element
256 return (key, self.pop(key))
258 def clear(self):
259 Cache.clear(self)
260 root = self.__root
261 root.prev = root.next = root
262 self.__links.clear()
264 def __touch(self, key):
265 """Increment use count"""
266 link = self.__links[key]
267 curr = link.next
268 if curr.count != link.count + 1:
269 if len(link.keys) == 1:
270 link.count += 1
271 return
272 curr = LFUCache._Link(link.count + 1)
273 curr.next = link.next
274 link.next = curr.next.prev = curr
275 curr.prev = link
276 curr.keys.add(key)
277 link.keys.remove(key)
278 if not link.keys:
279 link.unlink()
280 self.__links[key] = curr
283class LRUCache(Cache):
284 """Least Recently Used (LRU) cache implementation."""
286 def __init__(self, maxsize, getsizeof=None):
287 Cache.__init__(self, maxsize, getsizeof)
288 self.__order = collections.OrderedDict()
290 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
291 value = cache_getitem(self, key)
292 if key in self: # __missing__ may not store item
293 self.__touch(key)
294 return value
296 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
297 cache_setitem(self, key, value)
298 self.__touch(key)
300 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
301 cache_delitem(self, key)
302 del self.__order[key]
304 def popitem(self):
305 """Remove and return the `(key, value)` pair least recently used."""
306 try:
307 key = next(iter(self.__order))
308 except StopIteration:
309 raise KeyError("%s is empty" % type(self).__name__) from None
310 else:
311 return (key, self.pop(key))
313 def clear(self):
314 Cache.clear(self)
315 self.__order.clear()
317 def __touch(self, key):
318 """Mark as recently used"""
319 try:
320 self.__order.move_to_end(key)
321 except KeyError:
322 self.__order[key] = None
325class RRCache(Cache):
326 """Random Replacement (RR) cache implementation."""
328 def __init__(self, maxsize, choice=random.choice, getsizeof=None):
329 Cache.__init__(self, maxsize, getsizeof)
330 self.__choice = choice
331 self.__index = {}
332 self.__keys = []
334 @property
335 def choice(self):
336 """The `choice` function used by the cache."""
337 return self.__choice
339 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
340 cache_setitem(self, key, value)
341 if key not in self.__index:
342 self.__index[key] = len(self.__keys)
343 self.__keys.append(key)
345 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
346 cache_delitem(self, key)
347 index = self.__index.pop(key)
348 if index != len(self.__keys) - 1:
349 last = self.__keys[-1]
350 self.__keys[index] = last
351 self.__index[last] = index
352 self.__keys.pop()
354 def popitem(self):
355 """Remove and return a random `(key, value)` pair."""
356 try:
357 key = self.__choice(self.__keys)
358 except IndexError:
359 raise KeyError("%s is empty" % type(self).__name__) from None
360 else:
361 return (key, self.pop(key))
363 def clear(self):
364 Cache.clear(self)
365 self.__index.clear()
366 del self.__keys[:]
369class _TimedCache(Cache):
370 """Base class for time aware cache implementations."""
372 class _Timer:
373 def __init__(self, timer):
374 self.__timer = timer
375 self.__nesting = 0
377 def __call__(self):
378 if self.__nesting == 0:
379 return self.__timer()
380 else:
381 return self.__time
383 def __enter__(self):
384 if self.__nesting == 0:
385 self.__time = time = self.__timer()
386 else:
387 time = self.__time
388 self.__nesting += 1
389 return time
391 def __exit__(self, *exc):
392 self.__nesting -= 1
394 def __reduce__(self):
395 return _TimedCache._Timer, (self.__timer,)
397 def __getattr__(self, name):
398 return getattr(self.__timer, name)
400 def __init__(self, maxsize, timer=time.monotonic, getsizeof=None):
401 Cache.__init__(self, maxsize, getsizeof)
402 self.__timer = _TimedCache._Timer(timer)
404 def __repr__(self, cache_repr=Cache.__repr__):
405 with self.__timer as time:
406 self.expire(time)
407 return cache_repr(self)
409 def __len__(self, cache_len=Cache.__len__):
410 with self.__timer as time:
411 self.expire(time)
412 return cache_len(self)
414 @property
415 def currsize(self):
416 with self.__timer as time:
417 self.expire(time)
418 return super().currsize
420 @property
421 def timer(self):
422 """The timer function used by the cache."""
423 return self.__timer
425 def get(self, *args, **kwargs):
426 with self.__timer:
427 return Cache.get(self, *args, **kwargs)
429 def pop(self, *args, **kwargs):
430 with self.__timer:
431 return Cache.pop(self, *args, **kwargs)
433 def setdefault(self, *args, **kwargs):
434 with self.__timer:
435 return Cache.setdefault(self, *args, **kwargs)
437 def clear(self):
438 # Subclasses must override to also reset their own time-tracking
439 # structures; we do not call expire() here since clear() should
440 # be O(1) regardless of cache contents.
441 Cache.clear(self)
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_CacheInfo = collections.namedtuple(
715 "CacheInfo", ["hits", "misses", "maxsize", "currsize"]
716)
719def cached(cache, key=keys.hashkey, lock=None, condition=None, info=False):
720 """Decorator to wrap a function with a memoizing callable that saves
721 results in a cache.
723 """
724 from ._cached import _wrapper
726 def decorator(func):
727 if info:
728 if isinstance(cache, Cache):
730 def make_info(hits, misses):
731 return _CacheInfo(hits, misses, cache.maxsize, cache.currsize)
733 elif isinstance(cache, collections.abc.Mapping):
735 def make_info(hits, misses):
736 return _CacheInfo(hits, misses, None, len(cache))
738 else:
740 def make_info(hits, misses):
741 return _CacheInfo(hits, misses, 0, 0)
743 return _wrapper(func, cache, key, lock, condition, info=make_info)
744 else:
745 return _wrapper(func, cache, key, lock, condition)
747 return decorator
750def cachedmethod(cache, key=keys.methodkey, lock=None, condition=None, info=False):
751 """Decorator to wrap a method with a memoizing callable that saves
752 results in a cache.
754 """
755 from ._cachedmethod import _wrapper
757 def decorator(method):
758 if info:
760 def make_info(cache, hits, misses):
761 if isinstance(cache, Cache):
762 return _CacheInfo(hits, misses, cache.maxsize, cache.currsize)
763 elif isinstance(cache, collections.abc.Mapping):
764 return _CacheInfo(hits, misses, None, len(cache))
765 else:
766 raise TypeError("cache(self) must return a mutable mapping")
768 return _wrapper(method, cache, key, lock, condition, info=make_info)
769 else:
770 return _wrapper(method, cache, key, lock, condition)
772 return decorator