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

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.7" 

16 

17import collections 

18import collections.abc 

19import functools 

20import heapq 

21import random 

22import time 

23 

24from . import keys 

25 

26 

27class _DefaultSize: 

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

29 

30 __slots__ = () 

31 

32 def __getitem__(self, _key): 

33 return 1 

34 

35 def __setitem__(self, _key, _value): 

36 pass 

37 

38 def pop(self, _key): 

39 return 1 

40 

41 def clear(self): 

42 pass 

43 

44 

45class Cache(collections.abc.MutableMapping): 

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

47 

48 __marker = object() 

49 

50 __size = _DefaultSize() 

51 

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

57 self.__data = {} 

58 self.__currsize = 0 

59 self.__maxsize = maxsize 

60 

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 ) 

68 

69 def __getitem__(self, key): 

70 try: 

71 return self.__data[key] 

72 except KeyError: 

73 return self.__missing__(key) 

74 

75 def __setitem__(self, key, value): 

76 maxsize = self.__maxsize 

77 size = self.getsizeof(value) 

78 if size < 0: 

79 raise ValueError("value size must be non-negative") 

80 if size > maxsize: 

81 raise ValueError("value too large") 

82 if key not in self.__data: 

83 diffsize = size 

84 while self.__currsize + diffsize > maxsize: 

85 self.popitem() 

86 else: 

87 diffsize = size - self.__size[key] 

88 while self.__currsize + diffsize > maxsize: 

89 self.popitem() 

90 if key not in self.__data: 

91 diffsize = size 

92 self.__data[key] = value 

93 self.__size[key] = size 

94 self.__currsize += diffsize 

95 

96 def __delitem__(self, key): 

97 size = self.__size.pop(key) 

98 del self.__data[key] 

99 self.__currsize -= size 

100 

101 def __contains__(self, key): 

102 return key in self.__data 

103 

104 def __missing__(self, key): 

105 raise KeyError(key) 

106 

107 def __iter__(self): 

108 return iter(self.__data) 

109 

110 def __len__(self): 

111 return len(self.__data) 

112 

113 # Note that we cannot simply inherit get(), pop() and setdefault() 

114 # from MutableMapping, since these rely on __getitem__ throwing a 

115 # KeyError on cache miss. This is not the case if __missing__ is 

116 # implemented for a Cache subclass, so we have to roll our own, 

117 # somewhat less elegant versions. 

118 

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

120 if key in self: 

121 return self[key] 

122 else: 

123 return default 

124 

125 def pop(self, key, default=__marker): 

126 if key in self: 

127 value = self[key] 

128 del self[key] 

129 elif default is self.__marker: 

130 raise KeyError(key) 

131 else: 

132 value = default 

133 return value 

134 

135 def setdefault(self, key, default=None): 

136 if key in self: 

137 value = self[key] 

138 else: 

139 self[key] = value = default 

140 return value 

141 

142 # Although the MutableMapping.clear() default implementation works 

143 # perfectly well, it calls popitem() in a loop until the cache is 

144 # empty, resulting in O(n) complexity. For large caches, this 

145 # becomes a significant performance bottleneck, so we provide an 

146 # optimized version for each Cache subclass. 

147 

148 def clear(self): 

149 self.__data.clear() 

150 self.__size.clear() 

151 self.__currsize = 0 

152 

153 @property 

154 def maxsize(self): 

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

156 return self.__maxsize 

157 

158 @property 

159 def currsize(self): 

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

161 return self.__currsize 

162 

163 @staticmethod 

164 def getsizeof(value): 

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

166 return 1 

167 

168 

169class FIFOCache(Cache): 

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

171 

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

173 Cache.__init__(self, maxsize, getsizeof) 

174 self.__order = collections.OrderedDict() 

175 

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

177 cache_setitem(self, key, value) 

178 if key in self.__order: 

179 self.__order.move_to_end(key) 

180 else: 

181 self.__order[key] = None 

182 

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

184 cache_delitem(self, key) 

185 del self.__order[key] 

186 

187 def popitem(self): 

188 """Remove and return the `(key, value)` pair first inserted.""" 

189 try: 

190 key = next(iter(self.__order)) 

191 except StopIteration: 

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

193 else: 

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

195 

196 def clear(self): 

197 Cache.clear(self) 

198 self.__order.clear() 

199 

200 

201class LFUCache(Cache): 

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

203 

204 class _Link: 

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

206 

207 def __init__(self, count): 

208 self.count = count 

209 self.keys = set() 

210 

211 def unlink(self): 

212 next = self.next 

213 prev = self.prev 

214 prev.next = next 

215 next.prev = prev 

216 

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

218 Cache.__init__(self, maxsize, getsizeof) 

219 self.__root = root = LFUCache._Link(0) # sentinel 

220 root.prev = root.next = root 

221 self.__links = {} 

222 

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

224 value = cache_getitem(self, key) 

225 if key in self: # __missing__ may not store item 

226 self.__touch(key) 

227 return value 

228 

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

230 cache_setitem(self, key, value) 

231 if key in self.__links: 

232 self.__touch(key) 

233 return 

234 root = self.__root 

235 link = root.next 

236 if link.count != 1: 

237 link = LFUCache._Link(1) 

238 link.next = root.next 

239 root.next = link.next.prev = link 

240 link.prev = root 

241 link.keys.add(key) 

242 self.__links[key] = link 

243 

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

245 cache_delitem(self, key) 

246 link = self.__links.pop(key) 

247 link.keys.remove(key) 

248 if not link.keys: 

249 link.unlink() 

250 

251 def popitem(self): 

252 """Remove and return the `(key, value)` pair least frequently used.""" 

253 root = self.__root 

254 curr = root.next 

255 if curr is root: 

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

257 key = next(iter(curr.keys)) # remove an arbitrary element 

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

259 

260 def clear(self): 

261 Cache.clear(self) 

262 root = self.__root 

263 root.prev = root.next = root 

264 self.__links.clear() 

265 

266 def __touch(self, key): 

267 """Increment use count""" 

268 link = self.__links[key] 

269 curr = link.next 

270 if curr.count != link.count + 1: 

271 if len(link.keys) == 1: 

272 link.count += 1 

273 return 

274 curr = LFUCache._Link(link.count + 1) 

275 curr.next = link.next 

276 link.next = curr.next.prev = curr 

277 curr.prev = link 

278 curr.keys.add(key) 

279 link.keys.remove(key) 

280 if not link.keys: 

281 link.unlink() 

282 self.__links[key] = curr 

283 

284 

285class LRUCache(Cache): 

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

287 

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

289 Cache.__init__(self, maxsize, getsizeof) 

290 self.__order = collections.OrderedDict() 

291 

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

293 value = cache_getitem(self, key) 

294 if key in self: # __missing__ may not store item 

295 self.__touch(key) 

296 return value 

297 

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

299 cache_setitem(self, key, value) 

300 self.__touch(key) 

301 

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

303 cache_delitem(self, key) 

304 del self.__order[key] 

305 

306 def popitem(self): 

307 """Remove and return the `(key, value)` pair least recently used.""" 

308 try: 

309 key = next(iter(self.__order)) 

310 except StopIteration: 

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

312 else: 

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

314 

315 def clear(self): 

316 Cache.clear(self) 

317 self.__order.clear() 

318 

319 def __touch(self, key): 

320 """Mark as recently used""" 

321 try: 

322 self.__order.move_to_end(key) 

323 except KeyError: 

324 self.__order[key] = None 

325 

326 

327class RRCache(Cache): 

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

329 

330 def __init__(self, maxsize, choice=random.choice, getsizeof=None): 

331 Cache.__init__(self, maxsize, getsizeof) 

332 self.__choice = choice 

333 self.__index = {} 

334 self.__keys = [] 

335 

336 @property 

337 def choice(self): 

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

339 return self.__choice 

340 

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

342 cache_setitem(self, key, value) 

343 if key not in self.__index: 

344 self.__index[key] = len(self.__keys) 

345 self.__keys.append(key) 

346 

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

348 cache_delitem(self, key) 

349 index = self.__index.pop(key) 

350 if index != len(self.__keys) - 1: 

351 last = self.__keys[-1] 

352 self.__keys[index] = last 

353 self.__index[last] = index 

354 self.__keys.pop() 

355 

356 def popitem(self): 

357 """Remove and return a random `(key, value)` pair.""" 

358 try: 

359 key = self.__choice(self.__keys) 

360 except IndexError: 

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

362 else: 

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

364 

365 def clear(self): 

366 Cache.clear(self) 

367 self.__index.clear() 

368 del self.__keys[:] 

369 

370 

371class _TimedCache(Cache): 

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

373 

374 class _Timer: 

375 def __init__(self, timer): 

376 self.__timer = timer 

377 self.__nesting = 0 

378 

379 def __call__(self): 

380 if self.__nesting == 0: 

381 return self.__timer() 

382 else: 

383 return self.__time 

384 

385 def __enter__(self): 

386 if self.__nesting == 0: 

387 self.__time = time = self.__timer() 

388 else: 

389 time = self.__time 

390 self.__nesting += 1 

391 return time 

392 

393 def __exit__(self, *exc): 

394 self.__nesting -= 1 

395 

396 def __reduce__(self): 

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

398 

399 def __getattr__(self, name): 

400 return getattr(self.__timer, name) 

401 

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

403 Cache.__init__(self, maxsize, getsizeof) 

404 self.__timer = _TimedCache._Timer(timer) 

405 

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

407 with self.__timer as time: 

408 self.expire(time) 

409 return cache_repr(self) 

410 

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

412 with self.__timer as time: 

413 self.expire(time) 

414 return cache_len(self) 

415 

416 @property 

417 def currsize(self): 

418 with self.__timer as time: 

419 self.expire(time) 

420 return super().currsize 

421 

422 @property 

423 def timer(self): 

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

425 return self.__timer 

426 

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

428 with self.__timer: 

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

430 

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

432 with self.__timer: 

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

434 

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

436 with self.__timer: 

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

438 

439 def clear(self): 

440 # Subclasses must override to also reset their own time-tracking 

441 # structures; we do not call expire() here since clear() should 

442 # be O(1) regardless of cache contents. 

443 Cache.clear(self) 

444 

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

446 raise NotImplementedError 

447 

448 

449class TTLCache(_TimedCache): 

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

451 

452 class _Link: 

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

454 

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

456 self.key = key 

457 self.expires = expires 

458 

459 def __reduce__(self): 

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

461 

462 def unlink(self): 

463 next = self.next 

464 prev = self.prev 

465 prev.next = next 

466 next.prev = prev 

467 

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

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

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

471 root.prev = root.next = root 

472 self.__links = collections.OrderedDict() 

473 self.__ttl = ttl 

474 

475 def __contains__(self, key): 

476 try: 

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

478 except KeyError: 

479 return False 

480 else: 

481 return self.timer() < link.expires 

482 

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

484 try: 

485 link = self.__getlink(key) 

486 except KeyError: 

487 expired = False 

488 else: 

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

490 if expired: 

491 return self.__missing__(key) 

492 else: 

493 return cache_getitem(self, key) 

494 

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

496 with self.timer as time: 

497 self.expire(time) 

498 cache_setitem(self, key, value) 

499 try: 

500 link = self.__getlink(key) 

501 except KeyError: 

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

503 else: 

504 link.unlink() 

505 link.expires = time + self.__ttl 

506 link.next = root = self.__root 

507 link.prev = prev = root.prev 

508 prev.next = root.prev = link 

509 

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

511 cache_delitem(self, key) 

512 link = self.__links.pop(key) 

513 link.unlink() 

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

515 raise KeyError(key) 

516 

517 def __iter__(self): 

518 root = self.__root 

519 curr = root.next 

520 while curr is not root: 

521 # "freeze" time for iterator access 

522 with self.timer as time: 

523 if time < curr.expires: 

524 yield curr.key 

525 curr = curr.next 

526 

527 def __setstate__(self, state): 

528 self.__dict__.update(state) 

529 root = self.__root 

530 root.prev = root.next = root 

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

532 link.next = root 

533 link.prev = prev = root.prev 

534 prev.next = root.prev = link 

535 self.expire(self.timer()) 

536 

537 @property 

538 def ttl(self): 

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

540 return self.__ttl 

541 

542 def expire(self, time=None): 

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

544 expired `(key, value)` pairs. 

545 

546 """ 

547 if time is None: 

548 time = self.timer() 

549 root = self.__root 

550 curr = root.next 

551 links = self.__links 

552 expired = [] 

553 cache_delitem = Cache.__delitem__ 

554 cache_getitem = Cache.__getitem__ 

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

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

557 cache_delitem(self, curr.key) 

558 del links[curr.key] 

559 next = curr.next 

560 curr.unlink() 

561 curr = next 

562 return expired 

563 

564 def popitem(self): 

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

566 has not already expired. 

567 

568 """ 

569 with self.timer as time: 

570 self.expire(time) 

571 try: 

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

573 except StopIteration: 

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

575 else: 

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

577 

578 def clear(self): 

579 _TimedCache.clear(self) 

580 root = self.__root 

581 root.prev = root.next = root 

582 self.__links.clear() 

583 

584 def __getlink(self, key): 

585 value = self.__links[key] 

586 self.__links.move_to_end(key) 

587 return value 

588 

589 

590class TLRUCache(_TimedCache): 

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

592 

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

594 

595 @functools.total_ordering 

596 class _Item: 

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

598 

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

600 self.key = key 

601 self.expires = expires 

602 self.removed = False 

603 

604 def __lt__(self, other): 

605 return self.expires < other.expires 

606 

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

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

609 self.__items = collections.OrderedDict() 

610 self.__order = [] 

611 self.__ttu = ttu 

612 

613 def __contains__(self, key): 

614 try: 

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

616 except KeyError: 

617 return False 

618 else: 

619 return self.timer() < item.expires 

620 

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

622 try: 

623 item = self.__getitem(key) 

624 except KeyError: 

625 expired = False 

626 else: 

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

628 if expired: 

629 return self.__missing__(key) 

630 else: 

631 return cache_getitem(self, key) 

632 

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

634 with self.timer as time: 

635 self.expire(time) 

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

637 if not (time < expires): 

638 # updating an existing item with an already expired 

639 # one should remove the existing item 

640 return self.__delitem(key) 

641 cache_setitem(self, key, value) 

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

643 # only mark it as removed for now 

644 try: 

645 self.__getitem(key).removed = True 

646 except KeyError: 

647 pass 

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

649 heapq.heappush(self.__order, item) 

650 

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

652 with self.timer as time: 

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

654 cache_delitem(self, key) 

655 item = self.__items.pop(key) 

656 item.removed = True 

657 if not (time < item.expires): 

658 raise KeyError(key) 

659 

660 def __iter__(self): 

661 for curr in self.__order: 

662 # "freeze" time for iterator access 

663 with self.timer as time: 

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

665 yield curr.key 

666 

667 @property 

668 def ttu(self): 

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

670 return self.__ttu 

671 

672 def expire(self, time=None): 

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

674 expired `(key, value)` pairs. 

675 

676 """ 

677 if time is None: 

678 time = self.timer() 

679 items = self.__items 

680 order = self.__order 

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

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

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

684 heapq.heapify(order) 

685 expired = [] 

686 cache_delitem = Cache.__delitem__ 

687 cache_getitem = Cache.__getitem__ 

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

689 item = heapq.heappop(order) 

690 if not item.removed: 

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

692 cache_delitem(self, item.key) 

693 del items[item.key] 

694 return expired 

695 

696 def popitem(self): 

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

698 has not already expired. 

699 

700 """ 

701 with self.timer as time: 

702 self.expire(time) 

703 try: 

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

705 except StopIteration: 

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

707 else: 

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

709 

710 def clear(self): 

711 _TimedCache.clear(self) 

712 self.__items.clear() 

713 del self.__order[:] 

714 

715 def __getitem(self, key): 

716 value = self.__items[key] 

717 self.__items.move_to_end(key) 

718 return value 

719 

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

721 try: 

722 self.__items.pop(key).removed = True 

723 except KeyError: 

724 pass 

725 else: 

726 cache_delitem(self, key) 

727 

728 

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

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

731_CacheInfo = collections.namedtuple( 

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

733) 

734 

735 

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

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

738 results in a cache. 

739 

740 """ 

741 from ._cached import _wrapper 

742 

743 def decorator(func): 

744 if info: 

745 if isinstance(cache, Cache): 

746 

747 def make_info(hits, misses): 

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

749 

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

751 

752 def make_info(hits, misses): 

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

754 

755 else: 

756 

757 def make_info(hits, misses): 

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

759 

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

761 else: 

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

763 

764 return decorator 

765 

766 

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

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

769 results in a cache. 

770 

771 """ 

772 from ._cachedmethod import _wrapper 

773 

774 def decorator(method): 

775 if info: 

776 

777 def make_info(cache, hits, misses): 

778 if isinstance(cache, Cache): 

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

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

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

782 else: 

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

784 

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