Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/cachetools/__init__.py: 81%
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.1"
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
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 @property
138 def maxsize(self):
139 """The maximum size of the cache."""
140 return self.__maxsize
142 @property
143 def currsize(self):
144 """The current size of the cache."""
145 return self.__currsize
147 @staticmethod
148 def getsizeof(value):
149 """Return the size of a cache element's value."""
150 return 1
153class FIFOCache(Cache):
154 """First In First Out (FIFO) cache implementation."""
156 def __init__(self, maxsize, getsizeof=None):
157 Cache.__init__(self, maxsize, getsizeof)
158 self.__order = collections.OrderedDict()
160 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
161 cache_setitem(self, key, value)
162 if key in self.__order:
163 self.__order.move_to_end(key)
164 else:
165 self.__order[key] = None
167 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
168 cache_delitem(self, key)
169 del self.__order[key]
171 def popitem(self):
172 """Remove and return the `(key, value)` pair first inserted."""
173 try:
174 key = next(iter(self.__order))
175 except StopIteration:
176 raise KeyError("%s is empty" % type(self).__name__) from None
177 else:
178 return (key, self.pop(key))
181class LFUCache(Cache):
182 """Least Frequently Used (LFU) cache implementation."""
184 class _Link:
185 __slots__ = ("count", "keys", "next", "prev")
187 def __init__(self, count):
188 self.count = count
189 self.keys = set()
191 def unlink(self):
192 next = self.next
193 prev = self.prev
194 prev.next = next
195 next.prev = prev
197 def __init__(self, maxsize, getsizeof=None):
198 Cache.__init__(self, maxsize, getsizeof)
199 self.__root = root = LFUCache._Link(0) # sentinel
200 root.prev = root.next = root
201 self.__links = {}
203 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
204 value = cache_getitem(self, key)
205 if key in self: # __missing__ may not store item
206 self.__touch(key)
207 return value
209 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
210 cache_setitem(self, key, value)
211 if key in self.__links:
212 self.__touch(key)
213 return
214 root = self.__root
215 link = root.next
216 if link.count != 1:
217 link = LFUCache._Link(1)
218 link.next = root.next
219 root.next = link.next.prev = link
220 link.prev = root
221 link.keys.add(key)
222 self.__links[key] = link
224 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
225 cache_delitem(self, key)
226 link = self.__links.pop(key)
227 link.keys.remove(key)
228 if not link.keys:
229 link.unlink()
231 def popitem(self):
232 """Remove and return the `(key, value)` pair least frequently used."""
233 root = self.__root
234 curr = root.next
235 if curr is root:
236 raise KeyError("%s is empty" % type(self).__name__) from None
237 key = next(iter(curr.keys)) # remove an arbitrary element
238 return (key, self.pop(key))
240 def __touch(self, key):
241 """Increment use count"""
242 link = self.__links[key]
243 curr = link.next
244 if curr.count != link.count + 1:
245 if len(link.keys) == 1:
246 link.count += 1
247 return
248 curr = LFUCache._Link(link.count + 1)
249 curr.next = link.next
250 link.next = curr.next.prev = curr
251 curr.prev = link
252 curr.keys.add(key)
253 link.keys.remove(key)
254 if not link.keys:
255 link.unlink()
256 self.__links[key] = curr
259class LRUCache(Cache):
260 """Least Recently Used (LRU) cache implementation."""
262 def __init__(self, maxsize, getsizeof=None):
263 Cache.__init__(self, maxsize, getsizeof)
264 self.__order = collections.OrderedDict()
266 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
267 value = cache_getitem(self, key)
268 if key in self: # __missing__ may not store item
269 self.__touch(key)
270 return value
272 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
273 cache_setitem(self, key, value)
274 self.__touch(key)
276 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
277 cache_delitem(self, key)
278 del self.__order[key]
280 def popitem(self):
281 """Remove and return the `(key, value)` pair least recently used."""
282 try:
283 key = next(iter(self.__order))
284 except StopIteration:
285 raise KeyError("%s is empty" % type(self).__name__) from None
286 else:
287 return (key, self.pop(key))
289 def __touch(self, key):
290 """Mark as recently used"""
291 try:
292 self.__order.move_to_end(key)
293 except KeyError:
294 self.__order[key] = None
297class RRCache(Cache):
298 """Random Replacement (RR) cache implementation."""
300 def __init__(self, maxsize, choice=random.choice, getsizeof=None):
301 Cache.__init__(self, maxsize, getsizeof)
302 self.__choice = choice
303 self.__index = {}
304 self.__keys = []
306 @property
307 def choice(self):
308 """The `choice` function used by the cache."""
309 return self.__choice
311 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
312 cache_setitem(self, key, value)
313 if key not in self.__index:
314 self.__index[key] = len(self.__keys)
315 self.__keys.append(key)
317 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
318 cache_delitem(self, key)
319 index = self.__index.pop(key)
320 if index != len(self.__keys) - 1:
321 last = self.__keys[-1]
322 self.__keys[index] = last
323 self.__index[last] = index
324 self.__keys.pop()
326 def popitem(self):
327 """Remove and return a random `(key, value)` pair."""
328 try:
329 key = self.__choice(self.__keys)
330 except IndexError:
331 raise KeyError("%s is empty" % type(self).__name__) from None
332 else:
333 return (key, self.pop(key))
336class _TimedCache(Cache):
337 """Base class for time aware cache implementations."""
339 class _Timer:
340 def __init__(self, timer):
341 self.__timer = timer
342 self.__nesting = 0
344 def __call__(self):
345 if self.__nesting == 0:
346 return self.__timer()
347 else:
348 return self.__time
350 def __enter__(self):
351 if self.__nesting == 0:
352 self.__time = time = self.__timer()
353 else:
354 time = self.__time
355 self.__nesting += 1
356 return time
358 def __exit__(self, *exc):
359 self.__nesting -= 1
361 def __reduce__(self):
362 return _TimedCache._Timer, (self.__timer,)
364 def __getattr__(self, name):
365 return getattr(self.__timer, name)
367 def __init__(self, maxsize, timer=time.monotonic, getsizeof=None):
368 Cache.__init__(self, maxsize, getsizeof)
369 self.__timer = _TimedCache._Timer(timer)
371 def __repr__(self, cache_repr=Cache.__repr__):
372 with self.__timer as time:
373 self.expire(time)
374 return cache_repr(self)
376 def __len__(self, cache_len=Cache.__len__):
377 with self.__timer as time:
378 self.expire(time)
379 return cache_len(self)
381 @property
382 def currsize(self):
383 with self.__timer as time:
384 self.expire(time)
385 return super().currsize
387 @property
388 def timer(self):
389 """The timer function used by the cache."""
390 return self.__timer
392 def clear(self):
393 with self.__timer as time:
394 self.expire(time)
395 Cache.clear(self)
397 def get(self, *args, **kwargs):
398 with self.__timer:
399 return Cache.get(self, *args, **kwargs)
401 def pop(self, *args, **kwargs):
402 with self.__timer:
403 return Cache.pop(self, *args, **kwargs)
405 def setdefault(self, *args, **kwargs):
406 with self.__timer:
407 return Cache.setdefault(self, *args, **kwargs)
410class TTLCache(_TimedCache):
411 """LRU Cache implementation with per-item time-to-live (TTL) value."""
413 class _Link:
414 __slots__ = ("key", "expires", "next", "prev")
416 def __init__(self, key=None, expires=None):
417 self.key = key
418 self.expires = expires
420 def __reduce__(self):
421 return TTLCache._Link, (self.key, self.expires)
423 def unlink(self):
424 next = self.next
425 prev = self.prev
426 prev.next = next
427 next.prev = prev
429 def __init__(self, maxsize, ttl, timer=time.monotonic, getsizeof=None):
430 _TimedCache.__init__(self, maxsize, timer, getsizeof)
431 self.__root = root = TTLCache._Link()
432 root.prev = root.next = root
433 self.__links = collections.OrderedDict()
434 self.__ttl = ttl
436 def __contains__(self, key):
437 try:
438 link = self.__links[key] # no reordering
439 except KeyError:
440 return False
441 else:
442 return self.timer() < link.expires
444 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
445 try:
446 link = self.__getlink(key)
447 except KeyError:
448 expired = False
449 else:
450 expired = not (self.timer() < link.expires)
451 if expired:
452 return self.__missing__(key)
453 else:
454 return cache_getitem(self, key)
456 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
457 with self.timer as time:
458 self.expire(time)
459 cache_setitem(self, key, value)
460 try:
461 link = self.__getlink(key)
462 except KeyError:
463 self.__links[key] = link = TTLCache._Link(key)
464 else:
465 link.unlink()
466 link.expires = time + self.__ttl
467 link.next = root = self.__root
468 link.prev = prev = root.prev
469 prev.next = root.prev = link
471 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
472 cache_delitem(self, key)
473 link = self.__links.pop(key)
474 link.unlink()
475 if not (self.timer() < link.expires):
476 raise KeyError(key)
478 def __iter__(self):
479 root = self.__root
480 curr = root.next
481 while curr is not root:
482 # "freeze" time for iterator access
483 with self.timer as time:
484 if time < curr.expires:
485 yield curr.key
486 curr = curr.next
488 def __setstate__(self, state):
489 self.__dict__.update(state)
490 root = self.__root
491 root.prev = root.next = root
492 for link in sorted(self.__links.values(), key=lambda obj: obj.expires):
493 link.next = root
494 link.prev = prev = root.prev
495 prev.next = root.prev = link
496 self.expire(self.timer())
498 @property
499 def ttl(self):
500 """The time-to-live value of the cache's items."""
501 return self.__ttl
503 def expire(self, time=None):
504 """Remove expired items from the cache and return an iterable of the
505 expired `(key, value)` pairs.
507 """
508 if time is None:
509 time = self.timer()
510 root = self.__root
511 curr = root.next
512 links = self.__links
513 expired = []
514 cache_delitem = Cache.__delitem__
515 cache_getitem = Cache.__getitem__
516 while curr is not root and not (time < curr.expires):
517 expired.append((curr.key, cache_getitem(self, curr.key)))
518 cache_delitem(self, curr.key)
519 del links[curr.key]
520 next = curr.next
521 curr.unlink()
522 curr = next
523 return expired
525 def popitem(self):
526 """Remove and return the `(key, value)` pair least recently used that
527 has not already expired.
529 """
530 with self.timer as time:
531 self.expire(time)
532 try:
533 key = next(iter(self.__links))
534 except StopIteration:
535 raise KeyError("%s is empty" % type(self).__name__) from None
536 else:
537 return (key, self.pop(key))
539 def __getlink(self, key):
540 value = self.__links[key]
541 self.__links.move_to_end(key)
542 return value
545class TLRUCache(_TimedCache):
546 """Time aware Least Recently Used (TLRU) cache implementation."""
548 __HEAP_CLEANUP_FACTOR = 2 # clean up the heap if size > N * len(items)
550 @functools.total_ordering
551 class _Item:
552 __slots__ = ("key", "expires", "removed")
554 def __init__(self, key=None, expires=None):
555 self.key = key
556 self.expires = expires
557 self.removed = False
559 def __lt__(self, other):
560 return self.expires < other.expires
562 def __init__(self, maxsize, ttu, timer=time.monotonic, getsizeof=None):
563 _TimedCache.__init__(self, maxsize, timer, getsizeof)
564 self.__items = collections.OrderedDict()
565 self.__order = []
566 self.__ttu = ttu
568 def __contains__(self, key):
569 try:
570 item = self.__items[key] # no reordering
571 except KeyError:
572 return False
573 else:
574 return self.timer() < item.expires
576 def __getitem__(self, key, cache_getitem=Cache.__getitem__):
577 try:
578 item = self.__getitem(key)
579 except KeyError:
580 expired = False
581 else:
582 expired = not (self.timer() < item.expires)
583 if expired:
584 return self.__missing__(key)
585 else:
586 return cache_getitem(self, key)
588 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
589 with self.timer as time:
590 expires = self.__ttu(key, value, time)
591 if not (time < expires):
592 return # skip expired items
593 self.expire(time)
594 cache_setitem(self, key, value)
595 # removing an existing item would break the heap structure, so
596 # only mark it as removed for now
597 try:
598 self.__getitem(key).removed = True
599 except KeyError:
600 pass
601 self.__items[key] = item = TLRUCache._Item(key, expires)
602 heapq.heappush(self.__order, item)
604 def __delitem__(self, key, cache_delitem=Cache.__delitem__):
605 with self.timer as time:
606 # no self.expire() for performance reasons, e.g. self.clear() [#67]
607 cache_delitem(self, key)
608 item = self.__items.pop(key)
609 item.removed = True
610 if not (time < item.expires):
611 raise KeyError(key)
613 def __iter__(self):
614 for curr in self.__order:
615 # "freeze" time for iterator access
616 with self.timer as time:
617 if time < curr.expires and not curr.removed:
618 yield curr.key
620 @property
621 def ttu(self):
622 """The local time-to-use function used by the cache."""
623 return self.__ttu
625 def expire(self, time=None):
626 """Remove expired items from the cache and return an iterable of the
627 expired `(key, value)` pairs.
629 """
630 if time is None:
631 time = self.timer()
632 items = self.__items
633 order = self.__order
634 # clean up the heap if too many items are marked as removed
635 if len(order) > len(items) * self.__HEAP_CLEANUP_FACTOR:
636 self.__order = order = [item for item in order if not item.removed]
637 heapq.heapify(order)
638 expired = []
639 cache_delitem = Cache.__delitem__
640 cache_getitem = Cache.__getitem__
641 while order and (order[0].removed or not (time < order[0].expires)):
642 item = heapq.heappop(order)
643 if not item.removed:
644 expired.append((item.key, cache_getitem(self, item.key)))
645 cache_delitem(self, item.key)
646 del items[item.key]
647 return expired
649 def popitem(self):
650 """Remove and return the `(key, value)` pair least recently used that
651 has not already expired.
653 """
654 with self.timer as time:
655 self.expire(time)
656 try:
657 key = next(iter(self.__items))
658 except StopIteration:
659 raise KeyError("%s is empty" % type(self).__name__) from None
660 else:
661 return (key, self.pop(key))
663 def __getitem(self, key):
664 value = self.__items[key]
665 self.__items.move_to_end(key)
666 return value
669_CacheInfo = collections.namedtuple(
670 "CacheInfo", ["hits", "misses", "maxsize", "currsize"]
671)
674def cached(cache, key=keys.hashkey, lock=None, condition=None, info=False):
675 """Decorator to wrap a function with a memoizing callable that saves
676 results in a cache.
678 """
679 from ._cached import _wrapper
681 def decorator(func):
682 if info:
683 if isinstance(cache, Cache):
685 def make_info(hits, misses):
686 return _CacheInfo(hits, misses, cache.maxsize, cache.currsize)
688 elif isinstance(cache, collections.abc.Mapping):
690 def make_info(hits, misses):
691 return _CacheInfo(hits, misses, None, len(cache))
693 else:
695 def make_info(hits, misses):
696 return _CacheInfo(hits, misses, 0, 0)
698 return _wrapper(func, cache, key, lock, condition, info=make_info)
699 else:
700 return _wrapper(func, cache, key, lock, condition)
702 return decorator
705def cachedmethod(cache, key=keys.methodkey, lock=None, condition=None, info=False):
706 """Decorator to wrap a class or instance method with a memoizing
707 callable that saves results in a cache.
709 """
710 from ._cachedmethod import _wrapper
712 def decorator(method):
713 if info:
715 def make_info(cache, hits, misses):
716 if isinstance(cache, Cache):
717 return _CacheInfo(hits, misses, cache.maxsize, cache.currsize)
718 elif isinstance(cache, collections.abc.Mapping):
719 return _CacheInfo(hits, misses, None, len(cache))
720 else:
721 raise TypeError("cache(self) must return a mutable mapping")
723 return _wrapper(method, cache, key, lock, condition, info=make_info)
724 else:
725 return _wrapper(method, cache, key, lock, condition)
727 return decorator