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

17 

18import collections 

19import collections.abc 

20import functools 

21import heapq 

22import random 

23import time 

24 

25from . import keys 

26 

27 

28class _DefaultSize: 

29 __slots__ = () 

30 

31 def __getitem__(self, _): 

32 return 1 

33 

34 def __setitem__(self, _, value): 

35 assert value == 1 

36 

37 def pop(self, _): 

38 return 1 

39 

40 

41class Cache(collections.abc.MutableMapping): 

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

43 

44 __marker = object() 

45 

46 __size = _DefaultSize() 

47 

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

49 if getsizeof: 

50 self.getsizeof = getsizeof 

51 if self.getsizeof is not Cache.getsizeof: 

52 self.__size = dict() 

53 self.__data = dict() 

54 self.__currsize = 0 

55 self.__maxsize = maxsize 

56 

57 def __repr__(self): 

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

59 self.__class__.__name__, 

60 repr(self.__data), 

61 self.__maxsize, 

62 self.__currsize, 

63 ) 

64 

65 def __getitem__(self, key): 

66 try: 

67 return self.__data[key] 

68 except KeyError: 

69 return self.__missing__(key) 

70 

71 def __setitem__(self, key, value): 

72 maxsize = self.__maxsize 

73 size = self.getsizeof(value) 

74 if size > maxsize: 

75 raise ValueError("value too large") 

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

77 while self.__currsize + size > maxsize: 

78 self.popitem() 

79 if key in self.__data: 

80 diffsize = size - self.__size[key] 

81 else: 

82 diffsize = size 

83 self.__data[key] = value 

84 self.__size[key] = size 

85 self.__currsize += diffsize 

86 

87 def __delitem__(self, key): 

88 size = self.__size.pop(key) 

89 del self.__data[key] 

90 self.__currsize -= size 

91 

92 def __contains__(self, key): 

93 return key in self.__data 

94 

95 def __missing__(self, key): 

96 raise KeyError(key) 

97 

98 def __iter__(self): 

99 return iter(self.__data) 

100 

101 def __len__(self): 

102 return len(self.__data) 

103 

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

105 if key in self: 

106 return self[key] 

107 else: 

108 return default 

109 

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

111 if key in self: 

112 value = self[key] 

113 del self[key] 

114 elif default is self.__marker: 

115 raise KeyError(key) 

116 else: 

117 value = default 

118 return value 

119 

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

121 if key in self: 

122 value = self[key] 

123 else: 

124 self[key] = value = default 

125 return value 

126 

127 @property 

128 def maxsize(self): 

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

130 return self.__maxsize 

131 

132 @property 

133 def currsize(self): 

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

135 return self.__currsize 

136 

137 @staticmethod 

138 def getsizeof(value): 

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

140 return 1 

141 

142 

143class FIFOCache(Cache): 

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

145 

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

147 Cache.__init__(self, maxsize, getsizeof) 

148 self.__order = collections.OrderedDict() 

149 

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

151 cache_setitem(self, key, value) 

152 try: 

153 self.__order.move_to_end(key) 

154 except KeyError: 

155 self.__order[key] = None 

156 

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

158 cache_delitem(self, key) 

159 del self.__order[key] 

160 

161 def popitem(self): 

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

163 try: 

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

165 except StopIteration: 

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

167 else: 

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

169 

170 

171class LFUCache(Cache): 

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

173 

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

175 Cache.__init__(self, maxsize, getsizeof) 

176 self.__counter = collections.Counter() 

177 

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

179 value = cache_getitem(self, key) 

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

181 self.__counter[key] -= 1 

182 return value 

183 

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

185 cache_setitem(self, key, value) 

186 self.__counter[key] -= 1 

187 

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

189 cache_delitem(self, key) 

190 del self.__counter[key] 

191 

192 def popitem(self): 

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

194 try: 

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

196 except ValueError: 

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

198 else: 

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

200 

201 

202class LRUCache(Cache): 

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

204 

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

206 Cache.__init__(self, maxsize, getsizeof) 

207 self.__order = collections.OrderedDict() 

208 

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

210 value = cache_getitem(self, key) 

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

212 self.__update(key) 

213 return value 

214 

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

216 cache_setitem(self, key, value) 

217 self.__update(key) 

218 

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

220 cache_delitem(self, key) 

221 del self.__order[key] 

222 

223 def popitem(self): 

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

225 try: 

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

227 except StopIteration: 

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

229 else: 

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

231 

232 def __update(self, key): 

233 try: 

234 self.__order.move_to_end(key) 

235 except KeyError: 

236 self.__order[key] = None 

237 

238 

239class MRUCache(Cache): 

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

241 

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

243 from warnings import warn 

244 

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

246 

247 Cache.__init__(self, maxsize, getsizeof) 

248 self.__order = collections.OrderedDict() 

249 

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

251 value = cache_getitem(self, key) 

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

253 self.__update(key) 

254 return value 

255 

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

257 cache_setitem(self, key, value) 

258 self.__update(key) 

259 

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

261 cache_delitem(self, key) 

262 del self.__order[key] 

263 

264 def popitem(self): 

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

266 try: 

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

268 except StopIteration: 

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

270 else: 

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

272 

273 def __update(self, key): 

274 try: 

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

276 except KeyError: 

277 self.__order[key] = None 

278 

279 

280class RRCache(Cache): 

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

282 

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

284 Cache.__init__(self, maxsize, getsizeof) 

285 self.__choice = choice 

286 

287 @property 

288 def choice(self): 

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

290 return self.__choice 

291 

292 def popitem(self): 

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

294 try: 

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

296 except IndexError: 

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

298 else: 

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

300 

301 

302class _TimedCache(Cache): 

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

304 

305 class _Timer: 

306 def __init__(self, timer): 

307 self.__timer = timer 

308 self.__nesting = 0 

309 

310 def __call__(self): 

311 if self.__nesting == 0: 

312 return self.__timer() 

313 else: 

314 return self.__time 

315 

316 def __enter__(self): 

317 if self.__nesting == 0: 

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

319 else: 

320 time = self.__time 

321 self.__nesting += 1 

322 return time 

323 

324 def __exit__(self, *exc): 

325 self.__nesting -= 1 

326 

327 def __reduce__(self): 

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

329 

330 def __getattr__(self, name): 

331 return getattr(self.__timer, name) 

332 

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

334 Cache.__init__(self, maxsize, getsizeof) 

335 self.__timer = _TimedCache._Timer(timer) 

336 

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

338 with self.__timer as time: 

339 self.expire(time) 

340 return cache_repr(self) 

341 

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

343 with self.__timer as time: 

344 self.expire(time) 

345 return cache_len(self) 

346 

347 @property 

348 def currsize(self): 

349 with self.__timer as time: 

350 self.expire(time) 

351 return super().currsize 

352 

353 @property 

354 def timer(self): 

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

356 return self.__timer 

357 

358 def clear(self): 

359 with self.__timer as time: 

360 self.expire(time) 

361 Cache.clear(self) 

362 

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

364 with self.__timer: 

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

366 

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

368 with self.__timer: 

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

370 

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

372 with self.__timer: 

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

374 

375 

376class TTLCache(_TimedCache): 

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

378 

379 class _Link: 

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

381 

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

383 self.key = key 

384 self.expires = expires 

385 

386 def __reduce__(self): 

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

388 

389 def unlink(self): 

390 next = self.next 

391 prev = self.prev 

392 prev.next = next 

393 next.prev = prev 

394 

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

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

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

398 root.prev = root.next = root 

399 self.__links = collections.OrderedDict() 

400 self.__ttl = ttl 

401 

402 def __contains__(self, key): 

403 try: 

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

405 except KeyError: 

406 return False 

407 else: 

408 return self.timer() < link.expires 

409 

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

411 try: 

412 link = self.__getlink(key) 

413 except KeyError: 

414 expired = False 

415 else: 

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

417 if expired: 

418 return self.__missing__(key) 

419 else: 

420 return cache_getitem(self, key) 

421 

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

423 with self.timer as time: 

424 self.expire(time) 

425 cache_setitem(self, key, value) 

426 try: 

427 link = self.__getlink(key) 

428 except KeyError: 

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

430 else: 

431 link.unlink() 

432 link.expires = time + self.__ttl 

433 link.next = root = self.__root 

434 link.prev = prev = root.prev 

435 prev.next = root.prev = link 

436 

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

438 cache_delitem(self, key) 

439 link = self.__links.pop(key) 

440 link.unlink() 

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

442 raise KeyError(key) 

443 

444 def __iter__(self): 

445 root = self.__root 

446 curr = root.next 

447 while curr is not root: 

448 # "freeze" time for iterator access 

449 with self.timer as time: 

450 if time < curr.expires: 

451 yield curr.key 

452 curr = curr.next 

453 

454 def __setstate__(self, state): 

455 self.__dict__.update(state) 

456 root = self.__root 

457 root.prev = root.next = root 

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

459 link.next = root 

460 link.prev = prev = root.prev 

461 prev.next = root.prev = link 

462 self.expire(self.timer()) 

463 

464 @property 

465 def ttl(self): 

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

467 return self.__ttl 

468 

469 def expire(self, time=None): 

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

471 expired `(key, value)` pairs. 

472 

473 """ 

474 if time is None: 

475 time = self.timer() 

476 root = self.__root 

477 curr = root.next 

478 links = self.__links 

479 expired = [] 

480 cache_delitem = Cache.__delitem__ 

481 cache_getitem = Cache.__getitem__ 

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

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

484 cache_delitem(self, curr.key) 

485 del links[curr.key] 

486 next = curr.next 

487 curr.unlink() 

488 curr = next 

489 return expired 

490 

491 def popitem(self): 

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

493 has not already expired. 

494 

495 """ 

496 with self.timer as time: 

497 self.expire(time) 

498 try: 

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

500 except StopIteration: 

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

502 else: 

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

504 

505 def __getlink(self, key): 

506 value = self.__links[key] 

507 self.__links.move_to_end(key) 

508 return value 

509 

510 

511class TLRUCache(_TimedCache): 

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

513 

514 @functools.total_ordering 

515 class _Item: 

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

517 

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

519 self.key = key 

520 self.expires = expires 

521 self.removed = False 

522 

523 def __lt__(self, other): 

524 return self.expires < other.expires 

525 

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

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

528 self.__items = collections.OrderedDict() 

529 self.__order = [] 

530 self.__ttu = ttu 

531 

532 def __contains__(self, key): 

533 try: 

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

535 except KeyError: 

536 return False 

537 else: 

538 return self.timer() < item.expires 

539 

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

541 try: 

542 item = self.__getitem(key) 

543 except KeyError: 

544 expired = False 

545 else: 

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

547 if expired: 

548 return self.__missing__(key) 

549 else: 

550 return cache_getitem(self, key) 

551 

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

553 with self.timer as time: 

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

555 if not (time < expires): 

556 return # skip expired items 

557 self.expire(time) 

558 cache_setitem(self, key, value) 

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

560 # only mark it as removed for now 

561 try: 

562 self.__getitem(key).removed = True 

563 except KeyError: 

564 pass 

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

566 heapq.heappush(self.__order, item) 

567 

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

569 with self.timer as time: 

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

571 cache_delitem(self, key) 

572 item = self.__items.pop(key) 

573 item.removed = True 

574 if not (time < item.expires): 

575 raise KeyError(key) 

576 

577 def __iter__(self): 

578 for curr in self.__order: 

579 # "freeze" time for iterator access 

580 with self.timer as time: 

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

582 yield curr.key 

583 

584 @property 

585 def ttu(self): 

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

587 return self.__ttu 

588 

589 def expire(self, time=None): 

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

591 expired `(key, value)` pairs. 

592 

593 """ 

594 if time is None: 

595 time = self.timer() 

596 items = self.__items 

597 order = self.__order 

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

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

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

601 heapq.heapify(order) 

602 expired = [] 

603 cache_delitem = Cache.__delitem__ 

604 cache_getitem = Cache.__getitem__ 

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

606 item = heapq.heappop(order) 

607 if not item.removed: 

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

609 cache_delitem(self, item.key) 

610 del items[item.key] 

611 return expired 

612 

613 def popitem(self): 

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

615 has not already expired. 

616 

617 """ 

618 with self.timer as time: 

619 self.expire(time) 

620 try: 

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

622 except StopIteration: 

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

624 else: 

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

626 

627 def __getitem(self, key): 

628 value = self.__items[key] 

629 self.__items.move_to_end(key) 

630 return value 

631 

632 

633_CacheInfo = collections.namedtuple( 

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

635) 

636 

637 

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

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

640 results in a cache. 

641 

642 """ 

643 

644 def decorator(func): 

645 if info: 

646 hits = misses = 0 

647 

648 if isinstance(cache, Cache): 

649 

650 def getinfo(): 

651 nonlocal hits, misses 

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

653 

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

655 

656 def getinfo(): 

657 nonlocal hits, misses 

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

659 

660 else: 

661 

662 def getinfo(): 

663 nonlocal hits, misses 

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

665 

666 if cache is None: 

667 

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

669 nonlocal misses 

670 misses += 1 

671 return func(*args, **kwargs) 

672 

673 def cache_clear(): 

674 nonlocal hits, misses 

675 hits = misses = 0 

676 

677 cache_info = getinfo 

678 

679 elif lock is None: 

680 

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

682 nonlocal hits, misses 

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

684 try: 

685 result = cache[k] 

686 hits += 1 

687 return result 

688 except KeyError: 

689 misses += 1 

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

691 try: 

692 cache[k] = v 

693 except ValueError: 

694 pass # value too large 

695 return v 

696 

697 def cache_clear(): 

698 nonlocal hits, misses 

699 cache.clear() 

700 hits = misses = 0 

701 

702 cache_info = getinfo 

703 

704 else: 

705 

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

707 nonlocal hits, misses 

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

709 try: 

710 with lock: 

711 result = cache[k] 

712 hits += 1 

713 return result 

714 except KeyError: 

715 with lock: 

716 misses += 1 

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

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

719 try: 

720 with lock: 

721 return cache.setdefault(k, v) 

722 except ValueError: 

723 return v # value too large 

724 

725 def cache_clear(): 

726 nonlocal hits, misses 

727 with lock: 

728 cache.clear() 

729 hits = misses = 0 

730 

731 def cache_info(): 

732 with lock: 

733 return getinfo() 

734 

735 else: 

736 if cache is None: 

737 

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

739 return func(*args, **kwargs) 

740 

741 def cache_clear(): 

742 pass 

743 

744 elif lock is None: 

745 

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

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

748 try: 

749 return cache[k] 

750 except KeyError: 

751 pass # key not found 

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

753 try: 

754 cache[k] = v 

755 except ValueError: 

756 pass # value too large 

757 return v 

758 

759 def cache_clear(): 

760 cache.clear() 

761 

762 else: 

763 

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

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

766 try: 

767 with lock: 

768 return cache[k] 

769 except KeyError: 

770 pass # key not found 

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

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

773 try: 

774 with lock: 

775 return cache.setdefault(k, v) 

776 except ValueError: 

777 return v # value too large 

778 

779 def cache_clear(): 

780 with lock: 

781 cache.clear() 

782 

783 cache_info = None 

784 

785 wrapper.cache = cache 

786 wrapper.cache_key = key 

787 wrapper.cache_lock = lock 

788 wrapper.cache_clear = cache_clear 

789 wrapper.cache_info = cache_info 

790 

791 return functools.update_wrapper(wrapper, func) 

792 

793 return decorator 

794 

795 

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

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

798 callable that saves results in a cache. 

799 

800 """ 

801 

802 def decorator(method): 

803 if lock is None: 

804 

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

806 c = cache(self)