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

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

2 

3__all__ = ( 

4 "Cache", 

5 "FIFOCache", 

6 "LFUCache", 

7 "LRUCache", 

8 "MRUCache", 

9 "RRCache", 

10 "TLRUCache", 

11 "TTLCache", 

12 "cached", 

13 "cachedmethod", 

14) 

15 

16__version__ = "5.5.2" 

17 

18import collections 

19import collections.abc 

20import functools 

21import heapq 

22import random 

23import time 

24 

25from . import keys 

26from ._decorators import _cached_wrapper 

27 

28 

29class _DefaultSize: 

30 __slots__ = () 

31 

32 def __getitem__(self, _): 

33 return 1 

34 

35 def __setitem__(self, _, value): 

36 assert value == 1 

37 

38 def pop(self, _): 

39 return 1 

40 

41 

42class Cache(collections.abc.MutableMapping): 

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

44 

45 __marker = object() 

46 

47 __size = _DefaultSize() 

48 

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

50 if getsizeof: 

51 self.getsizeof = getsizeof 

52 if self.getsizeof is not Cache.getsizeof: 

53 self.__size = dict() 

54 self.__data = dict() 

55 self.__currsize = 0 

56 self.__maxsize = maxsize 

57 

58 def __repr__(self): 

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

60 self.__class__.__name__, 

61 repr(self.__data), 

62 self.__maxsize, 

63 self.__currsize, 

64 ) 

65 

66 def __getitem__(self, key): 

67 try: 

68 return self.__data[key] 

69 except KeyError: 

70 return self.__missing__(key) 

71 

72 def __setitem__(self, key, value): 

73 maxsize = self.__maxsize 

74 size = self.getsizeof(value) 

75 if size > maxsize: 

76 raise ValueError("value too large") 

77 if key not in self.__data or self.__size[key] < size: 

78 while self.__currsize + size > maxsize: 

79 self.popitem() 

80 if key in self.__data: 

81 diffsize = size - self.__size[key] 

82 else: 

83 diffsize = size 

84 self.__data[key] = value 

85 self.__size[key] = size 

86 self.__currsize += diffsize 

87 

88 def __delitem__(self, key): 

89 size = self.__size.pop(key) 

90 del self.__data[key] 

91 self.__currsize -= size 

92 

93 def __contains__(self, key): 

94 return key in self.__data 

95 

96 def __missing__(self, key): 

97 raise KeyError(key) 

98 

99 def __iter__(self): 

100 return iter(self.__data) 

101 

102 def __len__(self): 

103 return len(self.__data) 

104 

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

106 if key in self: 

107 return self[key] 

108 else: 

109 return default 

110 

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

112 if key in self: 

113 value = self[key] 

114 del self[key] 

115 elif default is self.__marker: 

116 raise KeyError(key) 

117 else: 

118 value = default 

119 return value 

120 

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

122 if key in self: 

123 value = self[key] 

124 else: 

125 self[key] = value = default 

126 return value 

127 

128 @property 

129 def maxsize(self): 

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

131 return self.__maxsize 

132 

133 @property 

134 def currsize(self): 

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

136 return self.__currsize 

137 

138 @staticmethod 

139 def getsizeof(value): 

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

141 return 1 

142 

143 

144class FIFOCache(Cache): 

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

146 

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

148 Cache.__init__(self, maxsize, getsizeof) 

149 self.__order = collections.OrderedDict() 

150 

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

152 cache_setitem(self, key, value) 

153 try: 

154 self.__order.move_to_end(key) 

155 except KeyError: 

156 self.__order[key] = None 

157 

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

159 cache_delitem(self, key) 

160 del self.__order[key] 

161 

162 def popitem(self): 

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

164 try: 

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

166 except StopIteration: 

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

168 else: 

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

170 

171 

172class LFUCache(Cache): 

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

174 

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

176 Cache.__init__(self, maxsize, getsizeof) 

177 self.__counter = collections.Counter() 

178 

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

180 value = cache_getitem(self, key) 

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

182 self.__counter[key] -= 1 

183 return value 

184 

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

186 cache_setitem(self, key, value) 

187 self.__counter[key] -= 1 

188 

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

190 cache_delitem(self, key) 

191 del self.__counter[key] 

192 

193 def popitem(self): 

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

195 try: 

196 ((key, _),) = self.__counter.most_common(1) 

197 except ValueError: 

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

199 else: 

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

201 

202 

203class LRUCache(Cache): 

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

205 

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

207 Cache.__init__(self, maxsize, getsizeof) 

208 self.__order = collections.OrderedDict() 

209 

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

211 value = cache_getitem(self, key) 

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

213 self.__update(key) 

214 return value 

215 

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

217 cache_setitem(self, key, value) 

218 self.__update(key) 

219 

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

221 cache_delitem(self, key) 

222 del self.__order[key] 

223 

224 def popitem(self): 

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

226 try: 

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

228 except StopIteration: 

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

230 else: 

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

232 

233 def __update(self, key): 

234 try: 

235 self.__order.move_to_end(key) 

236 except KeyError: 

237 self.__order[key] = None 

238 

239 

240class MRUCache(Cache): 

241 """Most Recently Used (MRU) cache implementation.""" 

242 

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

244 from warnings import warn 

245 

246 warn("MRUCache is deprecated", DeprecationWarning, stacklevel=2) 

247 

248 Cache.__init__(self, maxsize, getsizeof) 

249 self.__order = collections.OrderedDict() 

250 

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

252 value = cache_getitem(self, key) 

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

254 self.__update(key) 

255 return value 

256 

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

258 cache_setitem(self, key, value) 

259 self.__update(key) 

260 

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

262 cache_delitem(self, key) 

263 del self.__order[key] 

264 

265 def popitem(self): 

266 """Remove and return the `(key, value)` pair most recently used.""" 

267 try: 

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

269 except StopIteration: 

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

271 else: 

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

273 

274 def __update(self, key): 

275 try: 

276 self.__order.move_to_end(key, last=False) 

277 except KeyError: 

278 self.__order[key] = None 

279 

280 

281class RRCache(Cache): 

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

283 

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

285 Cache.__init__(self, maxsize, getsizeof) 

286 self.__choice = choice 

287 

288 @property 

289 def choice(self): 

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

291 return self.__choice 

292 

293 def popitem(self): 

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

295 try: 

296 key = self.__choice(list(self)) 

297 except IndexError: 

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

299 else: 

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

301 

302 

303class _TimedCache(Cache): 

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

305 

306 class _Timer: 

307 def __init__(self, timer): 

308 self.__timer = timer 

309 self.__nesting = 0 

310 

311 def __call__(self): 

312 if self.__nesting == 0: 

313 return self.__timer() 

314 else: 

315 return self.__time 

316 

317 def __enter__(self): 

318 if self.__nesting == 0: 

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

320 else: 

321 time = self.__time 

322 self.__nesting += 1 

323 return time 

324 

325 def __exit__(self, *exc): 

326 self.__nesting -= 1 

327 

328 def __reduce__(self): 

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

330 

331 def __getattr__(self, name): 

332 return getattr(self.__timer, name) 

333 

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

335 Cache.__init__(self, maxsize, getsizeof) 

336 self.__timer = _TimedCache._Timer(timer) 

337 

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

339 with self.__timer as time: 

340 self.expire(time) 

341 return cache_repr(self) 

342 

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

344 with self.__timer as time: 

345 self.expire(time) 

346 return cache_len(self) 

347 

348 @property 

349 def currsize(self): 

350 with self.__timer as time: 

351 self.expire(time) 

352 return super().currsize 

353 

354 @property 

355 def timer(self): 

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

357 return self.__timer 

358 

359 def clear(self): 

360 with self.__timer as time: 

361 self.expire(time) 

362 Cache.clear(self) 

363 

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

365 with self.__timer: 

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

367 

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

369 with self.__timer: 

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

371 

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

373 with self.__timer: 

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

375 

376 

377class TTLCache(_TimedCache): 

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

379 

380 class _Link: 

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

382 

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

384 self.key = key 

385 self.expires = expires 

386 

387 def __reduce__(self): 

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

389 

390 def unlink(self): 

391 next = self.next 

392 prev = self.prev 

393 prev.next = next 

394 next.prev = prev 

395 

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

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

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

399 root.prev = root.next = root 

400 self.__links = collections.OrderedDict() 

401 self.__ttl = ttl 

402 

403 def __contains__(self, key): 

404 try: 

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

406 except KeyError: 

407 return False 

408 else: 

409 return self.timer() < link.expires 

410 

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

412 try: 

413 link = self.__getlink(key) 

414 except KeyError: 

415 expired = False 

416 else: 

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

418 if expired: 

419 return self.__missing__(key) 

420 else: 

421 return cache_getitem(self, key) 

422 

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

424 with self.timer as time: 

425 self.expire(time) 

426 cache_setitem(self, key, value) 

427 try: 

428 link = self.__getlink(key) 

429 except KeyError: 

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

431 else: 

432 link.unlink() 

433 link.expires = time + self.__ttl 

434 link.next = root = self.__root 

435 link.prev = prev = root.prev 

436 prev.next = root.prev = link 

437 

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

439 cache_delitem(self, key) 

440 link = self.__links.pop(key) 

441 link.unlink() 

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

443 raise KeyError(key) 

444 

445 def __iter__(self): 

446 root = self.__root 

447 curr = root.next 

448 while curr is not root: 

449 # "freeze" time for iterator access 

450 with self.timer as time: 

451 if time < curr.expires: 

452 yield curr.key 

453 curr = curr.next 

454 

455 def __setstate__(self, state): 

456 self.__dict__.update(state) 

457 root = self.__root 

458 root.prev = root.next = root 

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

460 link.next = root 

461 link.prev = prev = root.prev 

462 prev.next = root.prev = link 

463 self.expire(self.timer()) 

464 

465 @property 

466 def ttl(self): 

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

468 return self.__ttl 

469 

470 def expire(self, time=None): 

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

472 expired `(key, value)` pairs. 

473 

474 """ 

475 if time is None: 

476 time = self.timer() 

477 root = self.__root 

478 curr = root.next 

479 links = self.__links 

480 expired = [] 

481 cache_delitem = Cache.__delitem__ 

482 cache_getitem = Cache.__getitem__ 

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

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

485 cache_delitem(self, curr.key) 

486 del links[curr.key] 

487 next = curr.next 

488 curr.unlink() 

489 curr = next 

490 return expired 

491 

492 def popitem(self): 

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

494 has not already expired. 

495 

496 """ 

497 with self.timer as time: 

498 self.expire(time) 

499 try: 

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

501 except StopIteration: 

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

503 else: 

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

505 

506 def __getlink(self, key): 

507 value = self.__links[key] 

508 self.__links.move_to_end(key) 

509 return value 

510 

511 

512class TLRUCache(_TimedCache): 

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

514 

515 @functools.total_ordering 

516 class _Item: 

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

518 

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

520 self.key = key 

521 self.expires = expires 

522 self.removed = False 

523 

524 def __lt__(self, other): 

525 return self.expires < other.expires 

526 

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

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

529 self.__items = collections.OrderedDict() 

530 self.__order = [] 

531 self.__ttu = ttu 

532 

533 def __contains__(self, key): 

534 try: 

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

536 except KeyError: 

537 return False 

538 else: 

539 return self.timer() < item.expires 

540 

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

542 try: 

543 item = self.__getitem(key) 

544 except KeyError: 

545 expired = False 

546 else: 

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

548 if expired: 

549 return self.__missing__(key) 

550 else: 

551 return cache_getitem(self, key) 

552 

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

554 with self.timer as time: 

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

556 if not (time < expires): 

557 return # skip expired items 

558 self.expire(time) 

559 cache_setitem(self, key, value) 

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

561 # only mark it as removed for now 

562 try: 

563 self.__getitem(key).removed = True 

564 except KeyError: 

565 pass 

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

567 heapq.heappush(self.__order, item) 

568 

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

570 with self.timer as time: 

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

572 cache_delitem(self, key) 

573 item = self.__items.pop(key) 

574 item.removed = True 

575 if not (time < item.expires): 

576 raise KeyError(key) 

577 

578 def __iter__(self): 

579 for curr in self.__order: 

580 # "freeze" time for iterator access 

581 with self.timer as time: 

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

583 yield curr.key 

584 

585 @property 

586 def ttu(self): 

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

588 return self.__ttu 

589 

590 def expire(self, time=None): 

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

592 expired `(key, value)` pairs. 

593 

594 """ 

595 if time is None: 

596 time = self.timer() 

597 items = self.__items 

598 order = self.__order 

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

600 if len(order) > len(items) * 2: 

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

602 heapq.heapify(order) 

603 expired = [] 

604 cache_delitem = Cache.__delitem__ 

605 cache_getitem = Cache.__getitem__ 

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

607 item = heapq.heappop(order) 

608 if not item.removed: 

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

610 cache_delitem(self, item.key) 

611 del items[item.key] 

612 return expired 

613 

614 def popitem(self): 

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

616 has not already expired. 

617 

618 """ 

619 with self.timer as time: 

620 self.expire(time) 

621 try: 

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

623 except StopIteration: 

624 raise KeyError("%s is empty" % self.__class__.__name__) from None 

625 else: 

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

627 

628 def __getitem(self, key): 

629 value = self.__items[key] 

630 self.__items.move_to_end(key) 

631 return value 

632 

633 

634_CacheInfo = collections.namedtuple( 

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

636) 

637 

638 

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

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

641 results in a cache. 

642 

643 """ 

644 

645 def decorator(func): 

646 if info: 

647 if isinstance(cache, Cache): 

648 

649 def make_info(hits, misses): 

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

651 

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

653 

654 def make_info(hits, misses): 

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

656 

657 else: 

658 

659 def make_info(hits, misses): 

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

661 

662 wrapper = _cached_wrapper(func, cache, key, lock, make_info) 

663 else: 

664 wrapper = _cached_wrapper(func, cache, key, lock, None) 

665 

666 wrapper.cache = cache 

667 wrapper.cache_key = key 

668 wrapper.cache_lock = lock 

669 

670 return functools.update_wrapper(wrapper, func) 

671 

672 return decorator 

673 

674 

675def cachedmethod(cache, key=keys.methodkey, lock=None): 

676 """Decorator to wrap a class or instance method with a memoizing 

677 callable that saves results in a cache. 

678 

679 """ 

680 

681 def decorator(method): 

682 if lock is None: 

683 

684 def wrapper(self, *args, **kwargs): 

685 c = cache(self) 

686 if c is None: 

687 return method(self, *args, **kwargs) 

688 k = key(self, *args, **kwargs) 

689 try: 

690 return c[k] 

691 except KeyError: 

692 pass # key not found 

693 v = method(self, *args, **kwargs) 

694 try: 

695 c[k] = v 

696 except ValueError: 

697 pass # value too large 

698 return v 

699 

700 def clear(self): 

701 c = cache(self) 

702 if c is not None: 

703 c.clear() 

704 

705 else: 

706 

707 def wrapper(self, *args, **kwargs): 

708 c = cache(self) 

709 if c is None: 

710 return method(self, *args, **kwargs) 

711 k = key(self, *args, **kwargs) 

712 try: 

713 with lock(self): 

714 return c[k] 

715 except KeyError: 

716 pass # key not found 

717 v = method(self, *args, **kwargs) 

718 # in case of a race, prefer the item already in the cache 

719 try: 

720 with lock(self): 

721 return c.setdefault(k, v) 

722 except ValueError: 

723 return v # value too large 

724 

725 def clear(self): 

726 c = cache(self) 

727 if c is not None: 

728 with lock(self): 

729 c.clear() 

730 

731 wrapper.cache = cache 

732 wrapper.cache_key = key 

733 wrapper.cache_lock = lock 

734 wrapper.cache_clear = clear 

735 

736 return functools.update_wrapper(wrapper, method) 

737 

738 return decorator