Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/cachetools/__init__.py: 78%

1"""Extensible memoizing collections and decorators.""" 

2 

3__all__ = ( 

4 "Cache", 

5 "FIFOCache", 

6 "LFUCache", 

7 "LRUCache", 

8 "RRCache", 

9 "TLRUCache", 

10 "TTLCache", 

11 "cached", 

12 "cachedmethod", 

13) 

14 

15__version__ = "7.1.1" 

16 

17import collections 

18import collections.abc 

19import functools 

20import heapq 

21import random 

22import time 

23 

24from . import keys 

25 

26# Typing stubs for this package are provided by typeshed: 

27# https://github.com/python/typeshed/tree/main/stubs/cachetools 

28 

29 

30class _DefaultSize: 

31 """A minimal "fake" dict that returns a constant size 1 for any key.""" 

32 

33 __slots__ = () 

34 

35 def __getitem__(self, _key): 

36 return 1 

37 

38 def __setitem__(self, _key, _value): 

39 pass 

40 

41 def pop(self, _key): 

42 return 1 

43 

44 def clear(self): 

45 pass 

46 

47 

48class Cache(collections.abc.MutableMapping): 

49 """Mutable mapping to serve as a simple cache or cache base class.""" 

50 

51 __marker = object() 

52 

53 __size = _DefaultSize() 

54 

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 

63 

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 ) 

71 

72 def __getitem__(self, key): 

73 try: 

74 return self.__data[key] 

75 except KeyError: 

76 return self.__missing__(key) 

77 

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 

93 

94 def __delitem__(self, key): 

95 size = self.__size.pop(key) 

96 del self.__data[key] 

97 self.__currsize -= size 

98 

99 def __contains__(self, key): 

100 return key in self.__data 

101 

102 def __missing__(self, key): 

103 raise KeyError(key) 

104 

105 def __iter__(self): 

106 return iter(self.__data) 

107 

108 def __len__(self): 

109 return len(self.__data) 

110 

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. 

116 

117 def get(self, key, default=None): 

118 if key in self: 

119 return self[key] 

120 else: 

121 return default 

122 

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 

132 

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 

139 

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. 

145 

146 def clear(self): 

147 self.__data.clear() 

148 self.__size.clear() 

149 self.__currsize = 0 

150 

151 @property 

152 def maxsize(self): 

153 """The maximum size of the cache.""" 

154 return self.__maxsize 

155 

156 @property 

157 def currsize(self): 

158 """The current size of the cache.""" 

159 return self.__currsize 

160 

161 @staticmethod 

162 def getsizeof(value): 

163 """Return the size of a cache element's value.""" 

164 return 1 

165 

166 

167class FIFOCache(Cache): 

168 """First In First Out (FIFO) cache implementation.""" 

169 

170 def __init__(self, maxsize, getsizeof=None): 

171 Cache.__init__(self, maxsize, getsizeof) 

172 self.__order = collections.OrderedDict() 

173 

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 

180 

181 def __delitem__(self, key, cache_delitem=Cache.__delitem__): 

182 cache_delitem(self, key) 

183 del self.__order[key] 

184 

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)) 

193 

194 def clear(self): 

195 Cache.clear(self) 

196 self.__order.clear() 

197 

198 

199class LFUCache(Cache): 

200 """Least Frequently Used (LFU) cache implementation.""" 

201 

202 class _Link: 

203 __slots__ = ("count", "keys", "next", "prev") 

204 

205 def __init__(self, count): 

206 self.count = count 

207 self.keys = set() 

208 

209 def unlink(self): 

210 next = self.next 

211 prev = self.prev 

212 prev.next = next 

213 next.prev = prev 

214 

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 = {} 

220 

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 

226 

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 

241 

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() 

248 

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)) 

257 

258 def clear(self): 

259 Cache.clear(self) 

260 root = self.__root 

261 root.prev = root.next = root 

262 self.__links.clear() 

263 

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 

281 

282 

283class LRUCache(Cache): 

284 """Least Recently Used (LRU) cache implementation.""" 

285 

286 def __init__(self, maxsize, getsizeof=None): 

287 Cache.__init__(self, maxsize, getsizeof) 

288 self.__order = collections.OrderedDict() 

289 

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 

295 

296 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__): 

297 cache_setitem(self, key, value) 

298 self.__touch(key) 

299 

300 def __delitem__(self, key, cache_delitem=Cache.__delitem__): 

301 cache_delitem(self, key) 

302 del self.__order[key] 

303 

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)) 

312 

313 def clear(self): 

314 Cache.clear(self) 

315 self.__order.clear() 

316 

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 

323 

324 

325class RRCache(Cache): 

326 """Random Replacement (RR) cache implementation.""" 

327 

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 = [] 

333 

334 @property 

335 def choice(self): 

336 """The `choice` function used by the cache.""" 

337 return self.__choice 

338 

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) 

344 

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() 

353 

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)) 

362 

363 def clear(self): 

364 Cache.clear(self) 

365 self.__index.clear() 

366 del self.__keys[:] 

367 

368 

369class _TimedCache(Cache): 

370 """Base class for time aware cache implementations.""" 

371 

372 class _Timer: 

373 def __init__(self, timer): 

374 self.__timer = timer 

375 self.__nesting = 0 

376 

377 def __call__(self): 

378 if self.__nesting == 0: 

379 return self.__timer() 

380 else: 

381 return self.__time 

382 

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 

390 

391 def __exit__(self, *exc): 

392 self.__nesting -= 1 

393 

394 def __reduce__(self): 

395 return _TimedCache._Timer, (self.__timer,) 

396 

397 def __getattr__(self, name): 

398 return getattr(self.__timer, name) 

399 

400 def __init__(self, maxsize, timer, getsizeof=None): 

401 Cache.__init__(self, maxsize, getsizeof) 

402 self.__timer = _TimedCache._Timer(timer) 

403 

404 def __repr__(self, cache_repr=Cache.__repr__): 

405 with self.__timer as time: 

406 self.expire(time) 

407 return cache_repr(self) 

408 

409 def __len__(self, cache_len=Cache.__len__): 

410 with self.__timer as time: 

411 self.expire(time) 

412 return cache_len(self) 

413 

414 @property 

415 def currsize(self): 

416 with self.__timer as time: 

417 self.expire(time) 

418 return super().currsize 

419 

420 @property 

421 def timer(self): 

422 """The timer function used by the cache.""" 

423 return self.__timer 

424 

425 def get(self, *args, **kwargs): 

426 with self.__timer: 

427 return Cache.get(self, *args, **kwargs) 

428 

429 def pop(self, *args, **kwargs): 

430 with self.__timer: 

431 return Cache.pop(self, *args, **kwargs) 

432 

433 def setdefault(self, *args, **kwargs): 

434 with self.__timer: 

435 return Cache.setdefault(self, *args, **kwargs) 

436 

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) 

442 

443 def expire(self, time=None): # pragma: no cover 

444 raise NotImplementedError 

445 

446 

447class TTLCache(_TimedCache): 

448 """LRU Cache implementation with per-item time-to-live (TTL) value.""" 

449 

450 class _Link: 

451 __slots__ = ("key", "expires", "next", "prev") 

452 

453 def __init__(self, key=None, expires=None): 

454 self.key = key 

455 self.expires = expires 

456 

457 def __reduce__(self): 

458 return TTLCache._Link, (self.key, self.expires) 

459 

460 def unlink(self): 

461 next = self.next 

462 prev = self.prev 

463 prev.next = next 

464 next.prev = prev 

465 

466 def __init__(self, maxsize, ttl, timer=time.monotonic, getsizeof=None): 

467 _TimedCache.__init__(self, maxsize, timer, getsizeof) 

468 self.__root = root = TTLCache._Link() 

469 root.prev = root.next = root 

470 self.__links = collections.OrderedDict() 

471 self.__ttl = ttl 

472 

473 def __contains__(self, key): 

474 try: 

475 link = self.__links[key] # no reordering 

476 except KeyError: 

477 return False 

478 else: 

479 return self.timer() < link.expires 

480 

481 def __getitem__(self, key, cache_getitem=Cache.__getitem__): 

482 try: 

483 link = self.__getlink(key) 

484 except KeyError: 

485 expired = False 

486 else: 

487 expired = not (self.timer() < link.expires) 

488 if expired: 

489 return self.__missing__(key) 

490 else: 

491 return cache_getitem(self, key) 

492 

493 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__): 

494 with self.timer as time: 

495 self.expire(time) 

496 cache_setitem(self, key, value) 

497 try: 

498 link = self.__getlink(key) 

499 except KeyError: 

500 self.__links[key] = link = TTLCache._Link(key) 

501 else: 

502 link.unlink() 

503 link.expires = time + self.__ttl 

504 link.next = root = self.__root 

505 link.prev = prev = root.prev 

506 prev.next = root.prev = link 

507 

508 def __delitem__(self, key, cache_delitem=Cache.__delitem__): 

509 cache_delitem(self, key) 

510 link = self.__links.pop(key) 

511 link.unlink() 

512 if not (self.timer() < link.expires): 

513 raise KeyError(key) 

514 

515 def __iter__(self): 

516 root = self.__root 

517 curr = root.next 

518 while curr is not root: 

519 # "freeze" time for iterator access 

520 with self.timer as time: 

521 if time < curr.expires: 

522 yield curr.key 

523 curr = curr.next 

524 

525 def __setstate__(self, state): 

526 self.__dict__.update(state) 

527 root = self.__root 

528 root.prev = root.next = root 

529 for link in sorted(self.__links.values(), key=lambda obj: obj.expires): 

530 link.next = root 

531 link.prev = prev = root.prev 

532 prev.next = root.prev = link 

533 self.expire(self.timer()) 

534 

535 @property 

536 def ttl(self): 

537 """The time-to-live value of the cache's items.""" 

538 return self.__ttl 

539 

540 def expire(self, time=None): 

541 """Remove expired items from the cache and return an iterable of the 

542 expired `(key, value)` pairs. 

543 

544 """ 

545 if time is None: 

546 time = self.timer() 

547 root = self.__root 

548 curr = root.next 

549 links = self.__links 

550 expired = [] 

551 cache_delitem = Cache.__delitem__ 

552 cache_getitem = Cache.__getitem__ 

553 while curr is not root and not (time < curr.expires): 

554 expired.append((curr.key, cache_getitem(self, curr.key))) 

555 cache_delitem(self, curr.key) 

556 del links[curr.key] 

557 next = curr.next 

558 curr.unlink() 

559 curr = next 

560 return expired 

561 

562 def popitem(self): 

563 """Remove and return the `(key, value)` pair least recently used that 

564 has not already expired. 

565 

566 """ 

567 with self.timer as time: 

568 self.expire(time) 

569 try: 

570 key = next(iter(self.__links)) 

571 except StopIteration: 

572 raise KeyError("%s is empty" % type(self).__name__) from None 

573 else: 

574 return (key, self.pop(key)) 

575 

576 def clear(self): 

577 _TimedCache.clear(self) 

578 root = self.__root 

579 root.prev = root.next = root 

580 self.__links.clear() 

581 

582 def __getlink(self, key): 

583 value = self.__links[key] 

584 self.__links.move_to_end(key) 

585 return value 

586 

587 

588class TLRUCache(_TimedCache): 

589 """Time aware Least Recently Used (TLRU) cache implementation.""" 

590 

591 __HEAP_CLEANUP_FACTOR = 2 # clean up the heap if size > N * len(items) 

592 

593 @functools.total_ordering 

594 class _Item: 

595 __slots__ = ("key", "expires", "removed") 

596 

597 def __init__(self, key=None, expires=None): 

598 self.key = key 

599 self.expires = expires 

600 self.removed = False 

601 

602 def __lt__(self, other): 

603 return self.expires < other.expires 

604 

605 def __init__(self, maxsize, ttu, timer=time.monotonic, getsizeof=None): 

606 _TimedCache.__init__(self, maxsize, timer, getsizeof) 

607 self.__items = collections.OrderedDict() 

608 self.__order = [] 

609 self.__ttu = ttu 

610 

611 def __contains__(self, key): 

612 try: 

613 item = self.__items[key] # no reordering 

614 except KeyError: 

615 return False 

616 else: 

617 return self.timer() < item.expires 

618 

619 def __getitem__(self, key, cache_getitem=Cache.__getitem__): 

620 try: 

621 item = self.__getitem(key) 

622 except KeyError: 

623 expired = False 

624 else: 

625 expired = not (self.timer() < item.expires) 

626 if expired: 

627 return self.__missing__(key) 

628 else: 

629 return cache_getitem(self, key) 

630 

631 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__): 

632 with self.timer as time: 

633 expires = self.__ttu(key, value, time) 

634 if not (time < expires): 

635 return # skip expired items 

636 self.expire(time) 

637 cache_setitem(self, key, value) 

638 # removing an existing item would break the heap structure, so 

639 # only mark it as removed for now 

640 try: 

641 self.__getitem(key).removed = True 

642 except KeyError: 

643 pass 

644 self.__items[key] = item = TLRUCache._Item(key, expires) 

645 heapq.heappush(self.__order, item) 

646 

647 def __delitem__(self, key, cache_delitem=Cache.__delitem__): 

648 with self.timer as time: 

649 # no self.expire() for performance reasons, e.g. self.clear() [#67] 

650 cache_delitem(self, key) 

651 item = self.__items.pop(key) 

652 item.removed = True 

653 if not (time < item.expires): 

654 raise KeyError(key) 

655 

656 def __iter__(self): 

657 for curr in self.__order: 

658 # "freeze" time for iterator access 

659 with self.timer as time: 

660 if time < curr.expires and not curr.removed: 

661 yield curr.key 

662 

663 @property 

664 def ttu(self): 

665 """The local time-to-use function used by the cache.""" 

666 return self.__ttu 

667 

668 def expire(self, time=None): 

669 """Remove expired items from the cache and return an iterable of the 

670 expired `(key, value)` pairs. 

671 

672 """ 

673 if time is None: 

674 time = self.timer() 

675 items = self.__items 

676 order = self.__order 

677 # clean up the heap if too many items are marked as removed 

678 if len(order) > len(items) * self.__HEAP_CLEANUP_FACTOR: 

679 self.__order = order = [item for item in order if not item.removed] 

680 heapq.heapify(order) 

681 expired = [] 

682 cache_delitem = Cache.__delitem__ 

683 cache_getitem = Cache.__getitem__ 

684 while order and (order[0].removed or not (time < order[0].expires)): 

685 item = heapq.heappop(order) 

686 if not item.removed: 

687 expired.append((item.key, cache_getitem(self, item.key))) 

688 cache_delitem(self, item.key) 

689 del items[item.key] 

690 return expired 

691 

692 def popitem(self): 

693 """Remove and return the `(key, value)` pair least recently used that 

694 has not already expired. 

695 

696 """ 

697 with self.timer as time: 

698 self.expire(time) 

699 try: 

700 key = next(iter(self.__items)) 

701 except StopIteration: 

702 raise KeyError("%s is empty" % type(self).__name__) from None 

703 else: 

704 return (key, self.pop(key)) 

705 

706 def clear(self): 

707 _TimedCache.clear(self) 

708 self.__items.clear() 

709 del self.__order[:] 

710 

711 def __getitem(self, key): 

712 value = self.__items[key] 

713 self.__items.move_to_end(key) 

714 return value 

715 

716 

717# note that the runtime __name__ is "CacheInfo", as in stdlib: 

718# https://github.com/python/cpython/blob/3.14/Lib/functools.py#L520 

719_CacheInfo = collections.namedtuple( 

720 "CacheInfo", ["hits", "misses", "maxsize", "currsize"] 

721) 

722 

723 

724def cached(cache, key=keys.hashkey, lock=None, condition=None, info=False): 

725 """Decorator to wrap a function with a memoizing callable that saves 

726 results in a cache. 

727 

728 """ 

729 from ._cached import _wrapper 

730 

731 def decorator(func): 

732 if info: 

733 if isinstance(cache, Cache): 

734 

735 def make_info(hits, misses): 

736 return _CacheInfo(hits, misses, cache.maxsize, cache.currsize) 

737 

738 elif isinstance(cache, collections.abc.Mapping): 

739 

740 def make_info(hits, misses): 

741 return _CacheInfo(hits, misses, None, len(cache)) 

742 

743 else: 

744 

745 def make_info(hits, misses): 

746 return _CacheInfo(hits, misses, 0, 0) 

747 

748 return _wrapper(func, cache, key, lock, condition, info=make_info) 

749 else: 

750 return _wrapper(func, cache, key, lock, condition) 

751 

752 return decorator 

753 

754 

755def cachedmethod(cache, key=keys.methodkey, lock=None, condition=None, info=False): 

756 """Decorator to wrap a method with a memoizing callable that saves 

757 results in a cache. 

758 

759 """ 

760 from ._cachedmethod import _wrapper 

761 

762 def decorator(method): 

763 if info: 

764 

765 def make_info(cache, hits, misses): 

766 if isinstance(cache, Cache): 

767 return _CacheInfo(hits, misses, cache.maxsize, cache.currsize) 

768 elif isinstance(cache, collections.abc.Mapping): 

769 return _CacheInfo(hits, misses, None, len(cache)) 

770 else: 

771 raise TypeError("cache(self) must return a mutable mapping") 

772 

773 return _wrapper(method, cache, key, lock, condition, info=make_info) 

774 else: 

775 return _wrapper(method, cache, key, lock, condition) 

776 

777 return decorator