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

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

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

383 

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

385 self.key = key 

386 self.expires = expires 

387 

388 def __reduce__(self): 

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

390 

391 def unlink(self): 

392 next = self.next 

393 prev = self.prev 

394 prev.next = next 

395 next.prev = prev 

396 

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

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

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

400 root.prev = root.next = root 

401 self.__links = collections.OrderedDict() 

402 self.__ttl = ttl 

403 

404 def __contains__(self, key): 

405 try: 

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

407 except KeyError: 

408 return False 

409 else: 

410 return self.timer() < link.expires 

411 

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

413 try: 

414 link = self.__getlink(key) 

415 except KeyError: 

416 expired = False 

417 else: 

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

419 if expired: 

420 return self.__missing__(key) 

421 else: 

422 return cache_getitem(self, key) 

423 

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

425 with self.timer as time: 

426 self.expire(time) 

427 cache_setitem(self, key, value) 

428 try: 

429 link = self.__getlink(key) 

430 except KeyError: 

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

432 else: 

433 link.unlink() 

434 link.expires = time + self.__ttl 

435 link.next = root = self.__root 

436 link.prev = prev = root.prev 

437 prev.next = root.prev = link 

438 

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

440 cache_delitem(self, key) 

441 link = self.__links.pop(key) 

442 link.unlink() 

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

444 raise KeyError(key) 

445 

446 def __iter__(self): 

447 root = self.__root 

448 curr = root.next 

449 while curr is not root: 

450 # "freeze" time for iterator access 

451 with self.timer as time: 

452 if time < curr.expires: 

453 yield curr.key 

454 curr = curr.next 

455 

456 def __setstate__(self, state): 

457 self.__dict__.update(state) 

458 root = self.__root 

459 root.prev = root.next = root 

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

461 link.next = root 

462 link.prev = prev = root.prev 

463 prev.next = root.prev = link 

464 self.expire(self.timer()) 

465 

466 @property 

467 def ttl(self): 

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

469 return self.__ttl 

470 

471 def expire(self, time=None): 

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

473 if time is None: 

474 time = self.timer() 

475 root = self.__root 

476 curr = root.next 

477 links = self.__links 

478 cache_delitem = Cache.__delitem__ 

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

480 cache_delitem(self, curr.key) 

481 del links[curr.key] 

482 next = curr.next 

483 curr.unlink() 

484 curr = next 

485 

486 def popitem(self): 

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

488 has not already expired. 

489 

490 """ 

491 with self.timer as time: 

492 self.expire(time) 

493 try: 

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

495 except StopIteration: 

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

497 else: 

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

499 

500 def __getlink(self, key): 

501 value = self.__links[key] 

502 self.__links.move_to_end(key) 

503 return value 

504 

505 

506class TLRUCache(_TimedCache): 

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

508 

509 @functools.total_ordering 

510 class _Item: 

511 

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

513 

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

515 self.key = key 

516 self.expires = expires 

517 self.removed = False 

518 

519 def __lt__(self, other): 

520 return self.expires < other.expires 

521 

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

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

524 self.__items = collections.OrderedDict() 

525 self.__order = [] 

526 self.__ttu = ttu 

527 

528 def __contains__(self, key): 

529 try: 

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

531 except KeyError: 

532 return False 

533 else: 

534 return self.timer() < item.expires 

535 

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

537 try: 

538 item = self.__getitem(key) 

539 except KeyError: 

540 expired = False 

541 else: 

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

543 if expired: 

544 return self.__missing__(key) 

545 else: 

546 return cache_getitem(self, key) 

547 

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

549 with self.timer as time: 

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

551 if not (time < expires): 

552 return # skip expired items 

553 self.expire(time) 

554 cache_setitem(self, key, value) 

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

556 # only mark it as removed for now 

557 try: 

558 self.__getitem(key).removed = True 

559 except KeyError: 

560 pass 

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

562 heapq.heappush(self.__order, item) 

563 

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

565 with self.timer as time: 

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

567 cache_delitem(self, key) 

568 item = self.__items.pop(key) 

569 item.removed = True 

570 if not (time < item.expires): 

571 raise KeyError(key) 

572 

573 def __iter__(self): 

574 for curr in self.__order: 

575 # "freeze" time for iterator access 

576 with self.timer as time: 

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

578 yield curr.key 

579 

580 @property 

581 def ttu(self): 

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

583 return self.__ttu 

584 

585 def expire(self, time=None): 

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

587 if time is None: 

588 time = self.timer() 

589 items = self.__items 

590 order = self.__order 

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

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

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

594 heapq.heapify(order) 

595 cache_delitem = Cache.__delitem__ 

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

597 item = heapq.heappop(order) 

598 if not item.removed: 

599 cache_delitem(self, item.key) 

600 del items[item.key] 

601 

602 def popitem(self): 

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

604 has not already expired. 

605 

606 """ 

607 with self.timer as time: 

608 self.expire(time) 

609 try: 

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

611 except StopIteration: 

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

613 else: 

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

615 

616 def __getitem(self, key): 

617 value = self.__items[key] 

618 self.__items.move_to_end(key) 

619 return value 

620 

621 

622_CacheInfo = collections.namedtuple( 

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

624) 

625 

626 

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

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

629 results in a cache. 

630 

631 """ 

632 

633 def decorator(func): 

634 if info: 

635 hits = misses = 0 

636 

637 if isinstance(cache, Cache): 

638 

639 def getinfo(): 

640 nonlocal hits, misses 

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

642 

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

644 

645 def getinfo(): 

646 nonlocal hits, misses 

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

648 

649 else: 

650 

651 def getinfo(): 

652 nonlocal hits, misses 

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

654 

655 if cache is None: 

656 

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

658 nonlocal misses 

659 misses += 1 

660 return func(*args, **kwargs) 

661 

662 def cache_clear(): 

663 nonlocal hits, misses 

664 hits = misses = 0 

665 

666 cache_info = getinfo 

667 

668 elif lock is None: 

669 

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

671 nonlocal hits, misses 

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

673 try: 

674 result = cache[k] 

675 hits += 1 

676 return result 

677 except KeyError: 

678 misses += 1 

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

680 try: 

681 cache[k] = v 

682 except ValueError: 

683 pass # value too large 

684 return v 

685 

686 def cache_clear(): 

687 nonlocal hits, misses 

688 cache.clear() 

689 hits = misses = 0 

690 

691 cache_info = getinfo 

692 

693 else: 

694 

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

696 nonlocal hits, misses 

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

698 try: 

699 with lock: 

700 result = cache[k] 

701 hits += 1 

702 return result 

703 except KeyError: 

704 with lock: 

705 misses += 1 

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

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

708 try: 

709 with lock: 

710 return cache.setdefault(k, v) 

711 except ValueError: 

712 return v # value too large 

713 

714 def cache_clear(): 

715 nonlocal hits, misses 

716 with lock: 

717 cache.clear() 

718 hits = misses = 0 

719 

720 def cache_info(): 

721 with lock: 

722 return getinfo() 

723 

724 else: 

725 if cache is None: 

726 

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

728 return func(*args, **kwargs) 

729 

730 def cache_clear(): 

731 pass 

732 

733 elif lock is None: 

734 

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

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

737 try: 

738 return cache[k] 

739 except KeyError: 

740 pass # key not found 

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

742 try: 

743 cache[k] = v 

744 except ValueError: 

745 pass # value too large 

746 return v 

747 

748 def cache_clear(): 

749 cache.clear() 

750 

751 else: 

752 

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

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

755 try: 

756 with lock: 

757 return cache[k] 

758 except KeyError: 

759 pass # key not found 

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

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

762 try: 

763 with lock: 

764 return cache.setdefault(k, v) 

765 except ValueError: 

766 return v # value too large 

767 

768 def cache_clear(): 

769 with lock: 

770 cache.clear() 

771 

772 cache_info = None 

773 

774 wrapper.cache = cache 

775 wrapper.cache_key = key 

776 wrapper.cache_lock = lock 

777 wrapper.cache_clear = cache_clear 

778 wrapper.cache_info = cache_info 

779 

780 return functools.update_wrapper(wrapper, func) 

781 

782 return decorator 

783 

784 

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

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

787 callable that saves results in a cache. 

788 

789 """ 

790 

791 def decorator(method): 

792 if lock is None: 

793 

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

795 c = cache(self) 

796 if c is None: 

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

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

799 try: 

800 return c[k] 

801 except KeyError: 

802 pass # key not found 

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

804 try: 

805 c[k] = v 

806 except ValueError: