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

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 maxsize < 0: 

54 raise ValueError("maxsize must be non-negative") 

55 if getsizeof: 

56 self.getsizeof = getsizeof 

57 if self.getsizeof is not Cache.getsizeof: 

58 self.__size = {} 

59 self.__data = {} 

60 self.__currsize = 0 

61 self.__maxsize = maxsize 

62 

63 def __repr__(self): 

64 return "%s(%s, maxsize=%r, currsize=%r)" % ( 

65 type(self).__name__, 

66 repr(self.__data), 

67 self.__maxsize, 

68 self.__currsize, 

69 ) 

70 

71 def __getitem__(self, key): 

72 try: 

73 return self.__data[key] 

74 except KeyError: 

75 return self.__missing__(key) 

76 

77 def __setitem__(self, key, value): 

78 maxsize = self.__maxsize 

79 size = self.getsizeof(value) 

80 if size < 0: 

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

82 if size > maxsize: 

83 raise ValueError("value too large") 

84 if key not in self.__data: 

85 diffsize = size 

86 while self.__currsize + diffsize > maxsize: 

87 self.popitem() 

88 else: 

89 diffsize = size - self.__size[key] 

90 while self.__currsize + diffsize > maxsize: 

91 self.popitem() 

92 if key not in self.__data: 

93 diffsize = size 

94 self.__data[key] = value 

95 self.__size[key] = size 

96 self.__currsize += diffsize 

97 

98 def __delitem__(self, key): 

99 size = self.__size.pop(key) 

100 del self.__data[key] 

101 self.__currsize -= size 

102 

103 def __contains__(self, key): 

104 return key in self.__data 

105 

106 def __missing__(self, key): 

107 raise KeyError(key) 

108 

109 def __iter__(self): 

110 return iter(self.__data) 

111 

112 def __len__(self): 

113 return len(self.__data) 

114 

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

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

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

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

119 # somewhat less elegant versions. 

120 

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

122 if key in self: 

123 return self[key] 

124 else: 

125 return default 

126 

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

128 if key in self: 

129 value = self[key] 

130 del self[key] 

131 elif default is self.__marker: 

132 raise KeyError(key) 

133 else: 

134 value = default 

135 return value 

136 

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

138 if key in self: 

139 value = self[key] 

140 else: 

141 self[key] = value = default 

142 return value 

143 

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

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

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

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

148 # optimized version for each Cache subclass. 

149 

150 def clear(self): 

151 self.__data.clear() 

152 self.__size.clear() 

153 self.__currsize = 0 

154 

155 @property 

156 def maxsize(self): 

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

158 return self.__maxsize 

159 

160 @property 

161 def currsize(self): 

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

163 return self.__currsize 

164 

165 @staticmethod 

166 def getsizeof(value): 

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

168 return 1 

169 

170 

171class FIFOCache(Cache): 

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

173 

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

175 Cache.__init__(self, maxsize, getsizeof) 

176 self.__order = collections.OrderedDict() 

177 

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

179 cache_setitem(self, key, value) 

180 if key in self.__order: 

181 self.__order.move_to_end(key) 

182 else: 

183 self.__order[key] = None 

184 

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

186 cache_delitem(self, key) 

187 del self.__order[key] 

188 

189 def popitem(self): 

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

191 try: 

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

193 except StopIteration: 

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

195 else: 

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

197 

198 def clear(self): 

199 Cache.clear(self) 

200 self.__order.clear() 

201 

202 

203class LFUCache(Cache): 

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

205 

206 class _Link: 

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

208 

209 def __init__(self, count): 

210 self.count = count 

211 self.keys = set() 

212 

213 def unlink(self): 

214 next = self.next 

215 prev = self.prev 

216 prev.next = next 

217 next.prev = prev 

218 

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

220 Cache.__init__(self, maxsize, getsizeof) 

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

222 root.prev = root.next = root 

223 self.__links = {} 

224 

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

226 value = cache_getitem(self, key) 

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

228 self.__touch(key) 

229 return value 

230 

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

232 cache_setitem(self, key, value) 

233 if key in self.__links: 

234 self.__touch(key) 

235 return 

236 root = self.__root 

237 link = root.next 

238 if link.count != 1: 

239 link = LFUCache._Link(1) 

240 link.next = root.next 

241 root.next = link.next.prev = link 

242 link.prev = root 

243 link.keys.add(key) 

244 self.__links[key] = link 

245 

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

247 cache_delitem(self, key) 

248 link = self.__links.pop(key) 

249 link.keys.remove(key) 

250 if not link.keys: 

251 link.unlink() 

252 

253 def popitem(self): 

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

255 root = self.__root 

256 curr = root.next 

257 if curr is root: 

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

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

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

261 

262 def clear(self): 

263 Cache.clear(self) 

264 root = self.__root 

265 root.prev = root.next = root 

266 self.__links.clear() 

267 

268 def __touch(self, key): 

269 """Increment use count""" 

270 link = self.__links[key] 

271 curr = link.next 

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

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

274 link.count += 1 

275 return 

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

277 curr.next = link.next 

278 link.next = curr.next.prev = curr 

279 curr.prev = link 

280 curr.keys.add(key) 

281 link.keys.remove(key) 

282 if not link.keys: 

283 link.unlink() 

284 self.__links[key] = curr 

285 

286 

287class LRUCache(Cache): 

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

289 

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

291 Cache.__init__(self, maxsize, getsizeof) 

292 self.__order = collections.OrderedDict() 

293 

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

295 value = cache_getitem(self, key) 

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

297 self.__touch(key) 

298 return value 

299 

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

301 cache_setitem(self, key, value) 

302 self.__touch(key) 

303 

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

305 cache_delitem(self, key) 

306 del self.__order[key] 

307 

308 def popitem(self): 

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

310 try: 

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

312 except StopIteration: 

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

314 else: 

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

316 

317 def clear(self): 

318 Cache.clear(self) 

319 self.__order.clear() 

320 

321 def __touch(self, key): 

322 """Mark as recently used""" 

323 try: 

324 self.__order.move_to_end(key) 

325 except KeyError: 

326 self.__order[key] = None 

327 

328 

329class RRCache(Cache): 

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

331 

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

333 Cache.__init__(self, maxsize, getsizeof) 

334 self.__choice = choice 

335 self.__index = {} 

336 self.__keys = [] 

337 

338 @property 

339 def choice(self): 

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

341 return self.__choice 

342 

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

344 cache_setitem(self, key, value) 

345 if key not in self.__index: 

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

347 self.__keys.append(key) 

348 

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

350 cache_delitem(self, key) 

351 index = self.__index.pop(key) 

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

353 last = self.__keys[-1] 

354 self.__keys[index] = last 

355 self.__index[last] = index 

356 self.__keys.pop() 

357 

358 def popitem(self): 

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

360 try: 

361 key = self.__choice(self.__keys) 

362 except IndexError: 

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

364 else: 

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

366 

367 def clear(self): 

368 Cache.clear(self) 

369 self.__index.clear() 

370 del self.__keys[:] 

371 

372 

373class _TimedCache(Cache): 

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

375 

376 class _Timer: 

377 def __init__(self, timer): 

378 self.__timer = timer 

379 self.__nesting = 0 

380 

381 def __call__(self): 

382 if self.__nesting == 0: 

383 return self.__timer() 

384 else: 

385 return self.__time 

386 

387 def __enter__(self): 

388 if self.__nesting == 0: 

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

390 else: 

391 time = self.__time 

392 self.__nesting += 1 

393 return time 

394 

395 def __exit__(self, *exc): 

396 self.__nesting -= 1 

397 

398 def __reduce__(self): 

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

400 

401 def __getattr__(self, name): 

402 return getattr(self.__timer, name) 

403 

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

405 Cache.__init__(self, maxsize, getsizeof) 

406 self.__timer = _TimedCache._Timer(timer) 

407 

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

409 with self.__timer as time: 

410 self.expire(time) 

411 return cache_repr(self) 

412 

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

414 with self.__timer as time: 

415 self.expire(time) 

416 return cache_len(self) 

417 

418 @property 

419 def currsize(self): 

420 with self.__timer as time: 

421 self.expire(time) 

422 return super().currsize 

423 

424 @property 

425 def timer(self): 

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

427 return self.__timer 

428 

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

430 with self.__timer: 

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

432 

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

434 with self.__timer: 

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

436 

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

438 with self.__timer: 

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

440 

441 def clear(self): 

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

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

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

445 Cache.clear(self) 

446 

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

448 raise NotImplementedError 

449 

450 

451class TTLCache(_TimedCache): 

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

453 

454 class _Link: 

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

456 

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

458 self.key = key 

459 self.expires = expires 

460 

461 def __reduce__(self): 

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

463 

464 def unlink(self): 

465 next = self.next 

466 prev = self.prev 

467 prev.next = next 

468 next.prev = prev 

469 

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

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

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

473 root.prev = root.next = root 

474 self.__links = collections.OrderedDict() 

475 self.__ttl = ttl 

476 

477 def __contains__(self, key): 

478 try: 

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

480 except KeyError: 

481 return False 

482 else: 

483 return self.timer() < link.expires 

484 

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

486 try: 

487 link = self.__getlink(key) 

488 except KeyError: 

489 expired = False 

490 else: 

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

492 if expired: 

493 return self.__missing__(key) 

494 else: 

495 return cache_getitem(self, key) 

496 

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

498 with self.timer as time: 

499 self.expire(time) 

500 cache_setitem(self, key, value) 

501 try: 

502 link = self.__getlink(key) 

503 except KeyError: 

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

505 else: 

506 link.unlink() 

507 link.expires = time + self.__ttl 

508 link.next = root = self.__root 

509 link.prev = prev = root.prev 

510 prev.next = root.prev = link 

511 

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

513 cache_delitem(self, key) 

514 link = self.__links.pop(key) 

515 link.unlink() 

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

517 raise KeyError(key) 

518 

519 def __iter__(self): 

520 root = self.__root 

521 curr = root.next 

522 while curr is not root: 

523 # "freeze" time for iterator access 

524 with self.timer as time: 

525 if time < curr.expires: 

526 yield curr.key 

527 curr = curr.next 

528 

529 def __setstate__(self, state): 

530 self.__dict__.update(state) 

531 root = self.__root 

532 root.prev = root.next = root 

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

534 link.next = root 

535 link.prev = prev = root.prev 

536 prev.next = root.prev = link 

537 self.expire(self.timer()) 

538 

539 @property 

540 def ttl(self): 

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

542 return self.__ttl 

543 

544 def expire(self, time=None): 

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

546 expired `(key, value)` pairs. 

547 

548 """ 

549 if time is None: 

550 time = self.timer() 

551 root = self.__root 

552 curr = root.next 

553 links = self.__links 

554 expired = [] 

555 cache_delitem = Cache.__delitem__ 

556 cache_getitem = Cache.__getitem__ 

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

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

559 cache_delitem(self, curr.key) 

560 del links[curr.key] 

561 next = curr.next 

562 curr.unlink() 

563 curr = next 

564 return expired 

565 

566 def popitem(self): 

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

568 has not already expired. 

569 

570 """ 

571 with self.timer as time: 

572 self.expire(time) 

573 try: 

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

575 except StopIteration: 

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

577 else: 

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

579 

580 def clear(self): 

581 _TimedCache.clear(self) 

582 root = self.__root 

583 root.prev = root.next = root 

584 self.__links.clear() 

585 

586 def __getlink(self, key): 

587 value = self.__links[key] 

588 self.__links.move_to_end(key) 

589 return value 

590 

591 

592class TLRUCache(_TimedCache): 

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

594 

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

596 

597 @functools.total_ordering 

598 class _Item: 

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

600 

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

602 self.key = key 

603 self.expires = expires 

604 self.removed = False 

605 

606 def __lt__(self, other): 

607 return self.expires < other.expires 

608 

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

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

611 self.__items = collections.OrderedDict() 

612 self.__order = [] 

613 self.__ttu = ttu 

614 

615 def __contains__(self, key): 

616 try: 

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

618 except KeyError: 

619 return False 

620 else: 

621 return self.timer() < item.expires 

622 

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

624 try: 

625 item = self.__getitem(key) 

626 except KeyError: 

627 expired = False 

628 else: 

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

630 if expired: 

631 return self.__missing__(key) 

632 else: 

633 return cache_getitem(self, key) 

634 

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

636 with self.timer as time: 

637 self.expire(time) 

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

639 if not (time < expires): 

640 # updating an existing item with an already expired 

641 # one should remove the existing item 

642 return self.__delitem(key) 

643 cache_setitem(self, key, value) 

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

645 # only mark it as removed for now 

646 try: 

647 self.__getitem(key).removed = True 

648 except KeyError: 

649 pass 

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

651 heapq.heappush(self.__order, item) 

652 

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

654 with self.timer as time: 

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

656 cache_delitem(self, key) 

657 item = self.__items.pop(key) 

658 item.removed = True 

659 if not (time < item.expires): 

660 raise KeyError(key) 

661 

662 def __iter__(self): 

663 for curr in self.__order: 

664 # "freeze" time for iterator access 

665 with self.timer as time: 

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

667 yield curr.key 

668 

669 @property 

670 def ttu(self): 

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

672 return self.__ttu 

673 

674 def expire(self, time=None): 

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

676 expired `(key, value)` pairs. 

677 

678 """ 

679 if time is None: 

680 time = self.timer() 

681 items = self.__items 

682 order = self.__order 

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

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

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

686 heapq.heapify(order) 

687 expired = [] 

688 cache_delitem = Cache.__delitem__ 

689 cache_getitem = Cache.__getitem__ 

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

691 item = heapq.heappop(order) 

692 if not item.removed: 

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

694 cache_delitem(self, item.key) 

695 del items[item.key] 

696 return expired 

697 

698 def popitem(self): 

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

700 has not already expired. 

701 

702 """ 

703 with self.timer as time: 

704 self.expire(time) 

705 try: 

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

707 except StopIteration: 

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

709 else: 

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

711 

712 def clear(self): 

713 _TimedCache.clear(self) 

714 self.__items.clear() 

715 del self.__order[:] 

716 

717 def __getitem(self, key): 

718 value = self.__items[key] 

719 self.__items.move_to_end(key) 

720 return value 

721 

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

723 try: 

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

725 except KeyError: 

726 pass 

727 else: 

728 cache_delitem(self, key) 

729 

730 

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

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

733_CacheInfo = collections.namedtuple( 

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

735) 

736 

737 

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

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

740 results in a cache. 

741 

742 """ 

743 from ._cached import _wrapper 

744 

745 def decorator(func): 

746 if info: 

747 if isinstance(cache, Cache): 

748 

749 def make_info(hits, misses): 

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

751 

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

753 

754 def make_info(hits, misses): 

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

756 

757 else: 

758 

759 def make_info(hits, misses): 

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

761 

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

763 else: 

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

765 

766 return decorator 

767 

768 

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

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

771 results in a cache. 

772 

773 """ 

774 from ._cachedmethod import _wrapper 

775 

776 def decorator(method): 

777 if info: 

778 

779 def make_info(cache, hits, misses): 

780 if isinstance(cache, Cache): 

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

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

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

784 else: 

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

786 

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