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

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

17 

18import collections 

19import collections.abc 

20import functools 

21import heapq 

22import random 

23import time 

24 

25from . import keys 

26 

27 

28class _DefaultSize: 

29 

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 Cache.__init__(self, maxsize, getsizeof) 

245 self.__order = collections.OrderedDict() 

246 

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

248 value = cache_getitem(self, key) 

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

250 self.__update(key) 

251 return value 

252 

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

254 cache_setitem(self, key, value) 

255 self.__update(key) 

256 

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

258 cache_delitem(self, key) 

259 del self.__order[key] 

260 

261 def popitem(self): 

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

263 try: 

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

265 except StopIteration: 

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

267 else: 

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

269 

270 def __update(self, key): 

271 try: 

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

273 except KeyError: 

274 self.__order[key] = None 

275 

276 

277class RRCache(Cache): 

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

279 

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

281 Cache.__init__(self, maxsize, getsizeof) 

282 self.__choice = choice 

283 

284 @property 

285 def choice(self): 

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

287 return self.__choice 

288 

289 def popitem(self): 

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

291 try: 

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

293 except IndexError: 

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

295 else: 

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

297 

298 

299class _TimedCache(Cache): 

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

301 

302 class _Timer: 

303 def __init__(self, timer): 

304 self.__timer = timer 

305 self.__nesting = 0 

306 

307 def __call__(self): 

308 if self.__nesting == 0: 

309 return self.__timer() 

310 else: 

311 return self.__time 

312 

313 def __enter__(self): 

314 if self.__nesting == 0: 

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

316 else: 

317 time = self.__time 

318 self.__nesting += 1 

319 return time 

320 

321 def __exit__(self, *exc): 

322 self.__nesting -= 1 

323 

324 def __reduce__(self): 

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

326 

327 def __getattr__(self, name): 

328 return getattr(self.__timer, name) 

329 

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

331 Cache.__init__(self, maxsize, getsizeof) 

332 self.__timer = _TimedCache._Timer(timer) 

333 

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

335 with self.__timer as time: 

336 self.expire(time) 

337 return cache_repr(self) 

338 

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

340 with self.__timer as time: 

341 self.expire(time) 

342 return cache_len(self) 

343 

344 @property 

345 def currsize(self): 

346 with self.__timer as time: 

347 self.expire(time) 

348 return super().currsize 

349 

350 @property 

351 def timer(self): 

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

353 return self.__timer 

354 

355 def clear(self): 

356 with self.__timer as time: 

357 self.expire(time) 

358 Cache.clear(self) 

359 

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

361 with self.__timer: 

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

363 

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

365 with self.__timer: 

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

367 

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

369 with self.__timer: 

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

371 

372 

373class TTLCache(_TimedCache): 

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

375 

376 class _Link: 

377 

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

379 

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

381 self.key = key 

382 self.expires = expires 

383 

384 def __reduce__(self): 

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

386 

387 def unlink(self): 

388 next = self.next 

389 prev = self.prev 

390 prev.next = next 

391 next.prev = prev 

392 

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

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

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

396 root.prev = root.next = root 

397 self.__links = collections.OrderedDict() 

398 self.__ttl = ttl 

399 

400 def __contains__(self, key): 

401 try: 

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

403 except KeyError: 

404 return False 

405 else: 

406 return self.timer() < link.expires 

407 

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

409 try: 

410 link = self.__getlink(key) 

411 except KeyError: 

412 expired = False 

413 else: 

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

415 if expired: 

416 return self.__missing__(key) 

417 else: 

418 return cache_getitem(self, key) 

419 

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

421 with self.timer as time: 

422 self.expire(time) 

423 cache_setitem(self, key, value) 

424 try: 

425 link = self.__getlink(key) 

426 except KeyError: 

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

428 else: 

429 link.unlink() 

430 link.expires = time + self.__ttl 

431 link.next = root = self.__root 

432 link.prev = prev = root.prev 

433 prev.next = root.prev = link 

434 

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

436 cache_delitem(self, key) 

437 link = self.__links.pop(key) 

438 link.unlink() 

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

440 raise KeyError(key) 

441 

442 def __iter__(self): 

443 root = self.__root 

444 curr = root.next 

445 while curr is not root: 

446 # "freeze" time for iterator access 

447 with self.timer as time: 

448 if time < curr.expires: 

449 yield curr.key 

450 curr = curr.next 

451 

452 def __setstate__(self, state): 

453 self.__dict__.update(state) 

454 root = self.__root 

455 root.prev = root.next = root 

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

457 link.next = root 

458 link.prev = prev = root.prev 

459 prev.next = root.prev = link 

460 self.expire(self.timer()) 

461 

462 @property 

463 def ttl(self): 

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

465 return self.__ttl 

466 

467 def expire(self, time=None): 

468 """Remove expired items from the cache.""" 

469 if time is None: 

470 time = self.timer() 

471 root = self.__root 

472 curr = root.next 

473 links = self.__links 

474 cache_delitem = Cache.__delitem__ 

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

476 cache_delitem(self, curr.key) 

477 del links[curr.key] 

478 next = curr.next 

479 curr.unlink() 

480 curr = next 

481 

482 def popitem(self): 

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

484 has not already expired. 

485 

486 """ 

487 with self.timer as time: 

488 self.expire(time) 

489 try: 

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

491 except StopIteration: 

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

493 else: 

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

495 

496 def __getlink(self, key): 

497 value = self.__links[key] 

498 self.__links.move_to_end(key) 

499 return value 

500 

501 

502class TLRUCache(_TimedCache): 

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

504 

505 @functools.total_ordering 

506 class _Item: 

507 

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

509 

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

511 self.key = key 

512 self.expires = expires 

513 self.removed = False 

514 

515 def __lt__(self, other): 

516 return self.expires < other.expires 

517 

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

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

520 self.__items = collections.OrderedDict() 

521 self.__order = [] 

522 self.__ttu = ttu 

523 

524 def __contains__(self, key): 

525 try: 

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

527 except KeyError: 

528 return False 

529 else: 

530 return self.timer() < item.expires 

531 

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

533 try: 

534 item = self.__getitem(key) 

535 except KeyError: 

536 expired = False 

537 else: 

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

539 if expired: 

540 return self.__missing__(key) 

541 else: 

542 return cache_getitem(self, key) 

543 

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

545 with self.timer as time: 

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

547 if not (time < expires): 

548 return # skip expired items 

549 self.expire(time) 

550 cache_setitem(self, key, value) 

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

552 # only mark it as removed for now 

553 try: 

554 self.__getitem(key).removed = True 

555 except KeyError: 

556 pass 

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

558 heapq.heappush(self.__order, item) 

559 

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

561 with self.timer as time: 

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

563 cache_delitem(self, key) 

564 item = self.__items.pop(key) 

565 item.removed = True 

566 if not (time < item.expires): 

567 raise KeyError(key) 

568 

569 def __iter__(self): 

570 for curr in self.__order: 

571 # "freeze" time for iterator access 

572 with self.timer as time: 

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

574 yield curr.key 

575 

576 @property 

577 def ttu(self): 

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

579 return self.__ttu 

580 

581 def expire(self, time=None): 

582 """Remove expired items from the cache.""" 

583 if time is None: 

584 time = self.timer() 

585 items = self.__items 

586 order = self.__order 

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

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

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

590 heapq.heapify(order) 

591 cache_delitem = Cache.__delitem__ 

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

593 item = heapq.heappop(order) 

594 if not item.removed: 

595 cache_delitem(self, item.key) 

596 del items[item.key] 

597 

598 def popitem(self): 

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

600 has not already expired. 

601 

602 """ 

603 with self.timer as time: 

604 self.expire(time) 

605 try: 

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

607 except StopIteration: 

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

609 else: 

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

611 

612 def __getitem(self, key): 

613 value = self.__items[key] 

614 self.__items.move_to_end(key) 

615 return value 

616 

617 

618_CacheInfo = collections.namedtuple( 

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

620) 

621 

622 

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

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

625 results in a cache. 

626 

627 """ 

628 

629 def decorator(func): 

630 if info: 

631 hits = misses = 0 

632 

633 if isinstance(cache, Cache): 

634 

635 def getinfo(): 

636 nonlocal hits, misses 

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

638 

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

640 

641 def getinfo(): 

642 nonlocal hits, misses 

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

644 

645 else: 

646 

647 def getinfo(): 

648 nonlocal hits, misses 

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

650 

651 if cache is None: 

652 

653 def wrapper(*args, **kwargs): 

654 nonlocal misses 

655 misses += 1 

656 return func(*args, **kwargs) 

657 

658 def cache_clear(): 

659 nonlocal hits, misses 

660 hits = misses = 0 

661 

662 cache_info = getinfo 

663 

664 elif lock is None: 

665 

666 def wrapper(*args, **kwargs): 

667 nonlocal hits, misses 

668 k = key(*args, **kwargs) 

669 try: 

670 result = cache[k] 

671 hits += 1 

672 return result 

673 except KeyError: 

674 misses += 1 

675 v = func(*args, **kwargs) 

676 try: 

677 cache[k] = v 

678 except ValueError: 

679 pass # value too large 

680 return v 

681 

682 def cache_clear(): 

683 nonlocal hits, misses 

684 cache.clear() 

685 hits = misses = 0 

686 

687 cache_info = getinfo 

688 

689 else: 

690 

691 def wrapper(*args, **kwargs): 

692 nonlocal hits, misses 

693 k = key(*args, **kwargs) 

694 try: 

695 with lock: 

696 result = cache[k] 

697 hits += 1 

698 return result 

699 except KeyError: 

700 with lock: 

701 misses += 1 

702 v = func(*args, **kwargs) 

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

704 try: 

705 with lock: 

706 return cache.setdefault(k, v) 

707 except ValueError: 

708 return v # value too large 

709 

710 def cache_clear(): 

711 nonlocal hits, misses 

712 with lock: 

713 cache.clear() 

714 hits = misses = 0 

715 

716 def cache_info(): 

717 with lock: 

718 return getinfo() 

719 

720 else: 

721 if cache is None: 

722 

723 def wrapper(*args, **kwargs): 

724 return func(*args, **kwargs) 

725 

726 def cache_clear(): 

727 pass 

728 

729 elif lock is None: 

730 

731 def wrapper(*args, **kwargs): 

732 k = key(*args, **kwargs) 

733 try: 

734 return cache[k] 

735 except KeyError: 

736 pass # key not found 

737 v = func(*args, **kwargs) 

738 try: 

739 cache[k] = v 

740 except ValueError: 

741 pass # value too large 

742 return v 

743 

744 def cache_clear(): 

745 cache.clear() 

746 

747 else: 

748 

749 def wrapper(*args, **kwargs): 

750 k = key(*args, **kwargs) 

751 try: 

752 with lock: 

753 return cache[k] 

754 except KeyError: 

755 pass # key not found 

756 v = func(*args, **kwargs) 

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

758 try: 

759 with lock: 

760 return cache.setdefault(k, v) 

761 except ValueError: 

762 return v # value too large 

763 

764 def cache_clear(): 

765 with lock: 

766 cache.clear() 

767 

768 cache_info = None 

769 

770 wrapper.cache = cache 

771 wrapper.cache_key = key 

772 wrapper.cache_lock = lock 

773 wrapper.cache_clear = cache_clear 

774 wrapper.cache_info = cache_info 

775 

776 return functools.update_wrapper(wrapper, func) 

777 

778 return decorator 

779 

780 

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

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

783 callable that saves results in a cache. 

784 

785 """ 

786 

787 def decorator(method): 

788 if lock is None: 

789 

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

791 c = cache(self) 

792 if c is None: 

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

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

795 try: 

796 return c[k] 

797 except KeyError: 

798 pass # key not found 

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

800 try: 

801 c[k] = v 

802 except ValueError: 

803 pass # value too large 

804 return v 

805 

806 def clear(self): 

807 c = cache(self)