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

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__ = "6.2.2" 

16 

17import collections 

18import collections.abc 

19import functools 

20import heapq 

21import random 

22import time 

23 

24from . import keys 

25 

26 

27class _DefaultSize: 

28 __slots__ = () 

29 

30 def __getitem__(self, _key): 

31 return 1 

32 

33 def __setitem__(self, _key, _value): 

34 pass 

35 

36 def pop(self, _key): 

37 return 1 

38 

39 

40class Cache(collections.abc.MutableMapping): 

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

42 

43 __marker = object() 

44 

45 __size = _DefaultSize() 

46 

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

48 if getsizeof: 

49 self.getsizeof = getsizeof 

50 if self.getsizeof is not Cache.getsizeof: 

51 self.__size = dict() 

52 self.__data = dict() 

53 self.__currsize = 0 

54 self.__maxsize = maxsize 

55 

56 def __repr__(self): 

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

58 type(self).__name__, 

59 repr(self.__data), 

60 self.__maxsize, 

61 self.__currsize, 

62 ) 

63 

64 def __getitem__(self, key): 

65 try: 

66 return self.__data[key] 

67 except KeyError: 

68 return self.__missing__(key) 

69 

70 def __setitem__(self, key, value): 

71 maxsize = self.__maxsize 

72 size = self.getsizeof(value) 

73 if size > maxsize: 

74 raise ValueError("value too large") 

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

76 while self.__currsize + size > maxsize: 

77 self.popitem() 

78 if key in self.__data: 

79 diffsize = size - self.__size[key] 

80 else: 

81 diffsize = size 

82 self.__data[key] = value 

83 self.__size[key] = size 

84 self.__currsize += diffsize 

85 

86 def __delitem__(self, key): 

87 size = self.__size.pop(key) 

88 del self.__data[key] 

89 self.__currsize -= size 

90 

91 def __contains__(self, key): 

92 return key in self.__data 

93 

94 def __missing__(self, key): 

95 raise KeyError(key) 

96 

97 def __iter__(self): 

98 return iter(self.__data) 

99 

100 def __len__(self): 

101 return len(self.__data) 

102 

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

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

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

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

107 # somewhat less elegant versions. 

108 

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

110 if key in self: 

111 return self[key] 

112 else: 

113 return default 

114 

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

116 if key in self: 

117 value = self[key] 

118 del self[key] 

119 elif default is self.__marker: 

120 raise KeyError(key) 

121 else: 

122 value = default 

123 return value 

124 

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

126 if key in self: 

127 value = self[key] 

128 else: 

129 self[key] = value = default 

130 return value 

131 

132 @property 

133 def maxsize(self): 

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

135 return self.__maxsize 

136 

137 @property 

138 def currsize(self): 

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

140 return self.__currsize 

141 

142 @staticmethod 

143 def getsizeof(value): 

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

145 return 1 

146 

147 

148class FIFOCache(Cache): 

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

150 

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

152 Cache.__init__(self, maxsize, getsizeof) 

153 self.__order = collections.OrderedDict() 

154 

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

156 cache_setitem(self, key, value) 

157 try: 

158 self.__order.move_to_end(key) 

159 except KeyError: 

160 self.__order[key] = None 

161 

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

163 cache_delitem(self, key) 

164 del self.__order[key] 

165 

166 def popitem(self): 

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

168 try: 

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

170 except StopIteration: 

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

172 else: 

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

174 

175 

176class LFUCache(Cache): 

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

178 

179 class _Link: 

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

181 

182 def __init__(self, count): 

183 self.count = count 

184 self.keys = set() 

185 

186 def unlink(self): 

187 next = self.next 

188 prev = self.prev 

189 prev.next = next 

190 next.prev = prev 

191 

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

193 Cache.__init__(self, maxsize, getsizeof) 

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

195 root.prev = root.next = root 

196 self.__links = {} 

197 

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

199 value = cache_getitem(self, key) 

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

201 self.__touch(key) 

202 return value 

203 

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

205 cache_setitem(self, key, value) 

206 if key in self.__links: 

207 return self.__touch(key) 

208 root = self.__root 

209 link = root.next 

210 if link.count != 1: 

211 link = LFUCache._Link(1) 

212 link.next = root.next 

213 root.next = link.next.prev = link 

214 link.prev = root 

215 link.keys.add(key) 

216 self.__links[key] = link 

217 

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

219 cache_delitem(self, key) 

220 link = self.__links.pop(key) 

221 link.keys.remove(key) 

222 if not link.keys: 

223 link.unlink() 

224 

225 def popitem(self): 

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

227 root = self.__root 

228 curr = root.next 

229 if curr is root: 

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

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

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

233 

234 def __touch(self, key): 

235 """Increment use count""" 

236 link = self.__links[key] 

237 curr = link.next 

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

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

240 link.count += 1 

241 return 

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

243 curr.next = link.next 

244 link.next = curr.next.prev = curr 

245 curr.prev = link 

246 curr.keys.add(key) 

247 link.keys.remove(key) 

248 if not link.keys: 

249 link.unlink() 

250 self.__links[key] = curr 

251 

252 

253class LRUCache(Cache): 

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

255 

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

257 Cache.__init__(self, maxsize, getsizeof) 

258 self.__order = collections.OrderedDict() 

259 

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

261 value = cache_getitem(self, key) 

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

263 self.__touch(key) 

264 return value 

265 

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

267 cache_setitem(self, key, value) 

268 self.__touch(key) 

269 

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

271 cache_delitem(self, key) 

272 del self.__order[key] 

273 

274 def popitem(self): 

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

276 try: 

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

278 except StopIteration: 

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

280 else: 

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

282 

283 def __touch(self, key): 

284 """Mark as recently used""" 

285 try: 

286 self.__order.move_to_end(key) 

287 except KeyError: 

288 self.__order[key] = None 

289 

290 

291class RRCache(Cache): 

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

293 

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

295 Cache.__init__(self, maxsize, getsizeof) 

296 self.__choice = choice 

297 self.__index = {} 

298 self.__keys = [] 

299 

300 @property 

301 def choice(self): 

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

303 return self.__choice 

304 

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

306 cache_setitem(self, key, value) 

307 if key not in self.__index: 

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

309 self.__keys.append(key) 

310 

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

312 cache_delitem(self, key) 

313 index = self.__index.pop(key) 

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

315 last = self.__keys[-1] 

316 self.__keys[index] = last 

317 self.__index[last] = index 

318 self.__keys.pop() 

319 

320 def popitem(self): 

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

322 try: 

323 key = self.__choice(self.__keys) 

324 except IndexError: 

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

326 else: 

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

328 

329 

330class _TimedCache(Cache): 

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

332 

333 class _Timer: 

334 def __init__(self, timer): 

335 self.__timer = timer 

336 self.__nesting = 0 

337 

338 def __call__(self): 

339 if self.__nesting == 0: 

340 return self.__timer() 

341 else: 

342 return self.__time 

343 

344 def __enter__(self): 

345 if self.__nesting == 0: 

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

347 else: 

348 time = self.__time 

349 self.__nesting += 1 

350 return time 

351 

352 def __exit__(self, *exc): 

353 self.__nesting -= 1 

354 

355 def __reduce__(self): 

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

357 

358 def __getattr__(self, name): 

359 return getattr(self.__timer, name) 

360 

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

362 Cache.__init__(self, maxsize, getsizeof) 

363 self.__timer = _TimedCache._Timer(timer) 

364 

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

366 with self.__timer as time: 

367 self.expire(time) 

368 return cache_repr(self) 

369 

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

371 with self.__timer as time: 

372 self.expire(time) 

373 return cache_len(self) 

374 

375 @property 

376 def currsize(self): 

377 with self.__timer as time: 

378 self.expire(time) 

379 return super().currsize 

380 

381 @property 

382 def timer(self): 

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

384 return self.__timer 

385 

386 def clear(self): 

387 with self.__timer as time: 

388 self.expire(time) 

389 Cache.clear(self) 

390 

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

392 with self.__timer: 

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

394 

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

396 with self.__timer: 

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

398 

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

400 with self.__timer: 

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

402 

403 

404class TTLCache(_TimedCache): 

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

406 

407 class _Link: 

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

409 

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

411 self.key = key 

412 self.expires = expires 

413 

414 def __reduce__(self): 

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

416 

417 def unlink(self): 

418 next = self.next 

419 prev = self.prev 

420 prev.next = next 

421 next.prev = prev 

422 

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

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

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

426 root.prev = root.next = root 

427 self.__links = collections.OrderedDict() 

428 self.__ttl = ttl 

429 

430 def __contains__(self, key): 

431 try: 

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

433 except KeyError: 

434 return False 

435 else: 

436 return self.timer() < link.expires 

437 

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

439 try: 

440 link = self.__getlink(key) 

441 except KeyError: 

442 expired = False 

443 else: 

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

445 if expired: 

446 return self.__missing__(key) 

447 else: 

448 return cache_getitem(self, key) 

449 

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

451 with self.timer as time: 

452 self.expire(time) 

453 cache_setitem(self, key, value) 

454 try: 

455 link = self.__getlink(key) 

456 except KeyError: 

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

458 else: 

459 link.unlink() 

460 link.expires = time + self.__ttl 

461 link.next = root = self.__root 

462 link.prev = prev = root.prev 

463 prev.next = root.prev = link 

464 

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

466 cache_delitem(self, key) 

467 link = self.__links.pop(key) 

468 link.unlink() 

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

470 raise KeyError(key) 

471 

472 def __iter__(self): 

473 root = self.__root 

474 curr = root.next 

475 while curr is not root: 

476 # "freeze" time for iterator access 

477 with self.timer as time: 

478 if time < curr.expires: 

479 yield curr.key 

480 curr = curr.next 

481 

482 def __setstate__(self, state): 

483 self.__dict__.update(state) 

484 root = self.__root 

485 root.prev = root.next = root 

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

487 link.next = root 

488 link.prev = prev = root.prev 

489 prev.next = root.prev = link 

490 self.expire(self.timer()) 

491 

492 @property 

493 def ttl(self): 

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

495 return self.__ttl 

496 

497 def expire(self, time=None): 

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

499 expired `(key, value)` pairs. 

500 

501 """ 

502 if time is None: 

503 time = self.timer() 

504 root = self.__root 

505 curr = root.next 

506 links = self.__links 

507 expired = [] 

508 cache_delitem = Cache.__delitem__ 

509 cache_getitem = Cache.__getitem__ 

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

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

512 cache_delitem(self, curr.key) 

513 del links[curr.key] 

514 next = curr.next 

515 curr.unlink() 

516 curr = next 

517 return expired 

518 

519 def popitem(self): 

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

521 has not already expired. 

522 

523 """ 

524 with self.timer as time: 

525 self.expire(time) 

526 try: 

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

528 except StopIteration: 

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

530 else: 

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

532 

533 def __getlink(self, key): 

534 value = self.__links[key] 

535 self.__links.move_to_end(key) 

536 return value 

537 

538 

539class TLRUCache(_TimedCache): 

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

541 

542 @functools.total_ordering 

543 class _Item: 

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

545 

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

547 self.key = key 

548 self.expires = expires 

549 self.removed = False 

550 

551 def __lt__(self, other): 

552 return self.expires < other.expires 

553 

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

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

556 self.__items = collections.OrderedDict() 

557 self.__order = [] 

558 self.__ttu = ttu 

559 

560 def __contains__(self, key): 

561 try: 

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

563 except KeyError: 

564 return False 

565 else: 

566 return self.timer() < item.expires 

567 

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

569 try: 

570 item = self.__getitem(key) 

571 except KeyError: 

572 expired = False 

573 else: 

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

575 if expired: 

576 return self.__missing__(key) 

577 else: 

578 return cache_getitem(self, key) 

579 

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

581 with self.timer as time: 

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

583 if not (time < expires): 

584 return # skip expired items 

585 self.expire(time) 

586 cache_setitem(self, key, value) 

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

588 # only mark it as removed for now 

589 try: 

590 self.__getitem(key).removed = True 

591 except KeyError: 

592 pass 

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

594 heapq.heappush(self.__order, item) 

595 

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

597 with self.timer as time: 

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

599 cache_delitem(self, key) 

600 item = self.__items.pop(key) 

601 item.removed = True 

602 if not (time < item.expires): 

603 raise KeyError(key) 

604 

605 def __iter__(self): 

606 for curr in self.__order: 

607 # "freeze" time for iterator access 

608 with self.timer as time: 

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

610 yield curr.key 

611 

612 @property 

613 def ttu(self): 

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

615 return self.__ttu 

616 

617 def expire(self, time=None): 

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

619 expired `(key, value)` pairs. 

620 

621 """ 

622 if time is None: 

623 time = self.timer() 

624 items = self.__items 

625 order = self.__order 

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

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

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

629 heapq.heapify(order) 

630 expired = [] 

631 cache_delitem = Cache.__delitem__ 

632 cache_getitem = Cache.__getitem__ 

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

634 item = heapq.heappop(order) 

635 if not item.removed: 

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

637 cache_delitem(self, item.key) 

638 del items[item.key] 

639 return expired 

640 

641 def popitem(self): 

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

643 has not already expired. 

644 

645 """ 

646 with self.timer as time: 

647 self.expire(time) 

648 try: 

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

650 except StopIteration: 

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

652 else: 

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

654 

655 def __getitem(self, key): 

656 value = self.__items[key] 

657 self.__items.move_to_end(key) 

658 return value 

659 

660 

661_CacheInfo = collections.namedtuple( 

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

663) 

664 

665 

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

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

668 results in a cache. 

669 

670 """ 

671 from ._cached import _wrapper 

672 

673 if isinstance(condition, bool): 

674 from warnings import warn 

675 

676 warn( 

677 "passing `info` as positional parameter is deprecated", 

678 DeprecationWarning, 

679 stacklevel=2, 

680 ) 

681 info = condition 

682 condition = None 

683 

684 def decorator(func): 

685 if info: 

686 if isinstance(cache, Cache): 

687 

688 def make_info(hits, misses): 

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

690 

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

692 

693 def make_info(hits, misses): 

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

695 

696 else: 

697 

698 def make_info(hits, misses): 

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

700 

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

702 else: 

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

704 

705 return decorator 

706 

707 

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

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

710 callable that saves results in a cache. 

711 

712 """ 

713 from ._cachedmethod import _wrapper 

714 

715 def decorator(method): 

716 return _wrapper(method, cache, key, lock, condition) 

717 

718 return decorator