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

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 if key in self.__order: 

158 self.__order.move_to_end(key) 

159 else: 

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 self.__touch(key) 

208 return 

209 root = self.__root 

210 link = root.next 

211 if link.count != 1: 

212 link = LFUCache._Link(1) 

213 link.next = root.next 

214 root.next = link.next.prev = link 

215 link.prev = root 

216 link.keys.add(key) 

217 self.__links[key] = link 

218 

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

220 cache_delitem(self, key) 

221 link = self.__links.pop(key) 

222 link.keys.remove(key) 

223 if not link.keys: 

224 link.unlink() 

225 

226 def popitem(self): 

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

228 root = self.__root 

229 curr = root.next 

230 if curr is root: 

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

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

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

234 

235 def __touch(self, key): 

236 """Increment use count""" 

237 link = self.__links[key] 

238 curr = link.next 

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

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

241 link.count += 1 

242 return 

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

244 curr.next = link.next 

245 link.next = curr.next.prev = curr 

246 curr.prev = link 

247 curr.keys.add(key) 

248 link.keys.remove(key) 

249 if not link.keys: 

250 link.unlink() 

251 self.__links[key] = curr 

252 

253 

254class LRUCache(Cache): 

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

256 

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

258 Cache.__init__(self, maxsize, getsizeof) 

259 self.__order = collections.OrderedDict() 

260 

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

262 value = cache_getitem(self, key) 

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

264 self.__touch(key) 

265 return value 

266 

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

268 cache_setitem(self, key, value) 

269 self.__touch(key) 

270 

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

272 cache_delitem(self, key) 

273 del self.__order[key] 

274 

275 def popitem(self): 

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

277 try: 

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

279 except StopIteration: 

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

281 else: 

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

283 

284 def __touch(self, key): 

285 """Mark as recently used""" 

286 try: 

287 self.__order.move_to_end(key) 

288 except KeyError: 

289 self.__order[key] = None 

290 

291 

292class RRCache(Cache): 

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

294 

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

296 Cache.__init__(self, maxsize, getsizeof) 

297 self.__choice = choice 

298 self.__index = {} 

299 self.__keys = [] 

300 

301 @property 

302 def choice(self): 

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

304 return self.__choice 

305 

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

307 cache_setitem(self, key, value) 

308 if key not in self.__index: 

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

310 self.__keys.append(key) 

311 

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

313 cache_delitem(self, key) 

314 index = self.__index.pop(key) 

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

316 last = self.__keys[-1] 

317 self.__keys[index] = last 

318 self.__index[last] = index 

319 self.__keys.pop() 

320 

321 def popitem(self): 

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

323 try: 

324 key = self.__choice(self.__keys) 

325 except IndexError: 

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

327 else: 

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

329 

330 

331class _TimedCache(Cache): 

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

333 

334 class _Timer: 

335 def __init__(self, timer): 

336 self.__timer = timer 

337 self.__nesting = 0 

338 

339 def __call__(self): 

340 if self.__nesting == 0: 

341 return self.__timer() 

342 else: 

343 return self.__time 

344 

345 def __enter__(self): 

346 if self.__nesting == 0: 

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

348 else: 

349 time = self.__time 

350 self.__nesting += 1 

351 return time 

352 

353 def __exit__(self, *exc): 

354 self.__nesting -= 1 

355 

356 def __reduce__(self): 

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

358 

359 def __getattr__(self, name): 

360 return getattr(self.__timer, name) 

361 

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

363 Cache.__init__(self, maxsize, getsizeof) 

364 self.__timer = _TimedCache._Timer(timer) 

365 

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

367 with self.__timer as time: 

368 self.expire(time) 

369 return cache_repr(self) 

370 

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

372 with self.__timer as time: 

373 self.expire(time) 

374 return cache_len(self) 

375 

376 @property 

377 def currsize(self): 

378 with self.__timer as time: 

379 self.expire(time) 

380 return super().currsize 

381 

382 @property 

383 def timer(self): 

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

385 return self.__timer 

386 

387 def clear(self): 

388 with self.__timer as time: 

389 self.expire(time) 

390 Cache.clear(self) 

391 

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

393 with self.__timer: 

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

395 

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

397 with self.__timer: 

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

399 

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

401 with self.__timer: 

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

403 

404 

405class TTLCache(_TimedCache): 

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

407 

408 class _Link: 

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

410 

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

412 self.key = key 

413 self.expires = expires 

414 

415 def __reduce__(self): 

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

417 

418 def unlink(self): 

419 next = self.next 

420 prev = self.prev 

421 prev.next = next 

422 next.prev = prev 

423 

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

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

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

427 root.prev = root.next = root 

428 self.__links = collections.OrderedDict() 

429 self.__ttl = ttl 

430 

431 def __contains__(self, key): 

432 try: 

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

434 except KeyError: 

435 return False 

436 else: 

437 return self.timer() < link.expires 

438 

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

440 try: 

441 link = self.__getlink(key) 

442 except KeyError: 

443 expired = False 

444 else: 

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

446 if expired: 

447 return self.__missing__(key) 

448 else: 

449 return cache_getitem(self, key) 

450 

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

452 with self.timer as time: 

453 self.expire(time) 

454 cache_setitem(self, key, value) 

455 try: 

456 link = self.__getlink(key) 

457 except KeyError: 

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

459 else: 

460 link.unlink() 

461 link.expires = time + self.__ttl 

462 link.next = root = self.__root 

463 link.prev = prev = root.prev 

464 prev.next = root.prev = link 

465 

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

467 cache_delitem(self, key) 

468 link = self.__links.pop(key) 

469 link.unlink() 

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

471 raise KeyError(key) 

472 

473 def __iter__(self): 

474 root = self.__root 

475 curr = root.next 

476 while curr is not root: 

477 # "freeze" time for iterator access 

478 with self.timer as time: 

479 if time < curr.expires: 

480 yield curr.key 

481 curr = curr.next 

482 

483 def __setstate__(self, state): 

484 self.__dict__.update(state) 

485 root = self.__root 

486 root.prev = root.next = root 

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

488 link.next = root 

489 link.prev = prev = root.prev 

490 prev.next = root.prev = link 

491 self.expire(self.timer()) 

492 

493 @property 

494 def ttl(self): 

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

496 return self.__ttl 

497 

498 def expire(self, time=None): 

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

500 expired `(key, value)` pairs. 

501 

502 """ 

503 if time is None: 

504 time = self.timer() 

505 root = self.__root 

506 curr = root.next 

507 links = self.__links 

508 expired = [] 

509 cache_delitem = Cache.__delitem__ 

510 cache_getitem = Cache.__getitem__ 

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

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

513 cache_delitem(self, curr.key) 

514 del links[curr.key] 

515 next = curr.next 

516 curr.unlink() 

517 curr = next 

518 return expired 

519 

520 def popitem(self): 

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

522 has not already expired. 

523 

524 """ 

525 with self.timer as time: 

526 self.expire(time) 

527 try: 

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

529 except StopIteration: 

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

531 else: 

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

533 

534 def __getlink(self, key): 

535 value = self.__links[key] 

536 self.__links.move_to_end(key) 

537 return value 

538 

539 

540class TLRUCache(_TimedCache): 

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

542 

543 @functools.total_ordering 

544 class _Item: 

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

546 

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

548 self.key = key 

549 self.expires = expires 

550 self.removed = False 

551 

552 def __lt__(self, other): 

553 return self.expires < other.expires 

554 

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

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

557 self.__items = collections.OrderedDict() 

558 self.__order = [] 

559 self.__ttu = ttu 

560 

561 def __contains__(self, key): 

562 try: 

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

564 except KeyError: 

565 return False 

566 else: 

567 return self.timer() < item.expires 

568 

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

570 try: 

571 item = self.__getitem(key) 

572 except KeyError: 

573 expired = False 

574 else: 

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

576 if expired: 

577 return self.__missing__(key) 

578 else: 

579 return cache_getitem(self, key) 

580 

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

582 with self.timer as time: 

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

584 if not (time < expires): 

585 return # skip expired items 

586 self.expire(time) 

587 cache_setitem(self, key, value) 

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

589 # only mark it as removed for now 

590 try: 

591 self.__getitem(key).removed = True 

592 except KeyError: 

593 pass 

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

595 heapq.heappush(self.__order, item) 

596 

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

598 with self.timer as time: 

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

600 cache_delitem(self, key) 

601 item = self.__items.pop(key) 

602 item.removed = True 

603 if not (time < item.expires): 

604 raise KeyError(key) 

605 

606 def __iter__(self): 

607 for curr in self.__order: 

608 # "freeze" time for iterator access 

609 with self.timer as time: 

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

611 yield curr.key 

612 

613 @property 

614 def ttu(self): 

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

616 return self.__ttu 

617 

618 def expire(self, time=None): 

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

620 expired `(key, value)` pairs. 

621 

622 """ 

623 if time is None: 

624 time = self.timer() 

625 items = self.__items 

626 order = self.__order 

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

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

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

630 heapq.heapify(order) 

631 expired = [] 

632 cache_delitem = Cache.__delitem__ 

633 cache_getitem = Cache.__getitem__ 

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

635 item = heapq.heappop(order) 

636 if not item.removed: 

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

638 cache_delitem(self, item.key) 

639 del items[item.key] 

640 return expired 

641 

642 def popitem(self): 

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

644 has not already expired. 

645 

646 """ 

647 with self.timer as time: 

648 self.expire(time) 

649 try: 

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

651 except StopIteration: 

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

653 else: 

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

655 

656 def __getitem(self, key): 

657 value = self.__items[key] 

658 self.__items.move_to_end(key) 

659 return value 

660 

661 

662_CacheInfo = collections.namedtuple( 

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

664) 

665 

666 

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

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

669 results in a cache. 

670 

671 """ 

672 from ._cached import _wrapper 

673 

674 if isinstance(condition, bool): 

675 from warnings import warn 

676 

677 warn( 

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

679 DeprecationWarning, 

680 stacklevel=2, 

681 ) 

682 info = condition 

683 condition = None 

684 

685 def decorator(func): 

686 if info: 

687 if isinstance(cache, Cache): 

688 

689 def make_info(hits, misses): 

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

691 

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

693 

694 def make_info(hits, misses): 

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

696 

697 else: 

698 

699 def make_info(hits, misses): 

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

701 

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

703 else: 

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

705 

706 return decorator 

707 

708 

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

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

711 callable that saves results in a cache. 

712 

713 """ 

714 from ._cachedmethod import _wrapper 

715 

716 def decorator(method): 

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

718 

719 return decorator