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

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

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, _): 

31 return 1 

32 

33 def __setitem__(self, _, value): 

34 assert value == 1 

35 

36 def pop(self, _): 

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 self.__class__.__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 def get(self, key, default=None): 

104 if key in self: 

105 return self[key] 

106 else: 

107 return default 

108 

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

110 if key in self: 

111 value = self[key] 

112 del self[key] 

113 elif default is self.__marker: 

114 raise KeyError(key) 

115 else: 

116 value = default 

117 return value 

118 

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

120 if key in self: 

121 value = self[key] 

122 else: 

123 self[key] = value = default 

124 return value 

125 

126 @property 

127 def maxsize(self): 

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

129 return self.__maxsize 

130 

131 @property 

132 def currsize(self): 

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

134 return self.__currsize 

135 

136 @staticmethod 

137 def getsizeof(value): 

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

139 return 1 

140 

141 

142class FIFOCache(Cache): 

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

144 

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

146 Cache.__init__(self, maxsize, getsizeof) 

147 self.__order = collections.OrderedDict() 

148 

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

150 cache_setitem(self, key, value) 

151 try: 

152 self.__order.move_to_end(key) 

153 except KeyError: 

154 self.__order[key] = None 

155 

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

157 cache_delitem(self, key) 

158 del self.__order[key] 

159 

160 def popitem(self): 

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

162 try: 

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

164 except StopIteration: 

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

166 else: 

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

168 

169 

170class LFUCache(Cache): 

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

172 

173 class _Link: 

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

175 

176 def __init__(self, count): 

177 self.count = count 

178 self.keys = set() 

179 

180 def unlink(self): 

181 next = self.next 

182 prev = self.prev 

183 prev.next = next 

184 next.prev = prev 

185 

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

187 Cache.__init__(self, maxsize, getsizeof) 

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

189 root.prev = root.next = root 

190 self.__links = {} 

191 

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

193 value = cache_getitem(self, key) 

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

195 self.__touch(key) 

196 return value 

197 

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

199 cache_setitem(self, key, value) 

200 if key in self.__links: 

201 return self.__touch(key) 

202 root = self.__root 

203 link = root.next 

204 if link.count != 1: 

205 link = LFUCache._Link(1) 

206 link.next = root.next 

207 root.next = link.next.prev = link 

208 link.prev = root 

209 link.keys.add(key) 

210 self.__links[key] = link 

211 

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

213 cache_delitem(self, key) 

214 link = self.__links.pop(key) 

215 link.keys.remove(key) 

216 if not link.keys: 

217 link.unlink() 

218 

219 def popitem(self): 

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

221 root = self.__root 

222 curr = root.next 

223 if curr is root: 

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

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

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

227 

228 def __touch(self, key): 

229 """Increment use count""" 

230 link = self.__links[key] 

231 curr = link.next 

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

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

234 link.count += 1 

235 return 

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

237 curr.next = link.next 

238 link.next = curr.next.prev = curr 

239 curr.prev = link 

240 curr.keys.add(key) 

241 link.keys.remove(key) 

242 if not link.keys: 

243 link.unlink() 

244 self.__links[key] = curr 

245 

246 

247class LRUCache(Cache): 

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

249 

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

251 Cache.__init__(self, maxsize, getsizeof) 

252 self.__order = collections.OrderedDict() 

253 

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

255 value = cache_getitem(self, key) 

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

257 self.__touch(key) 

258 return value 

259 

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

261 cache_setitem(self, key, value) 

262 self.__touch(key) 

263 

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

265 cache_delitem(self, key) 

266 del self.__order[key] 

267 

268 def popitem(self): 

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

270 try: 

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

272 except StopIteration: 

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

274 else: 

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

276 

277 def __touch(self, key): 

278 """Mark as recently used""" 

279 try: 

280 self.__order.move_to_end(key) 

281 except KeyError: 

282 self.__order[key] = None 

283 

284 

285class RRCache(Cache): 

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

287 

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

289 Cache.__init__(self, maxsize, getsizeof) 

290 self.__choice = choice 

291 

292 @property 

293 def choice(self): 

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

295 return self.__choice 

296 

297 def popitem(self): 

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

299 try: 

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

301 except IndexError: 

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

303 else: 

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

305 

306 

307class _TimedCache(Cache): 

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

309 

310 class _Timer: 

311 def __init__(self, timer): 

312 self.__timer = timer 

313 self.__nesting = 0 

314 

315 def __call__(self): 

316 if self.__nesting == 0: 

317 return self.__timer() 

318 else: 

319 return self.__time 

320 

321 def __enter__(self): 

322 if self.__nesting == 0: 

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

324 else: 

325 time = self.__time 

326 self.__nesting += 1 

327 return time 

328 

329 def __exit__(self, *exc): 

330 self.__nesting -= 1 

331 

332 def __reduce__(self): 

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

334 

335 def __getattr__(self, name): 

336 return getattr(self.__timer, name) 

337 

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

339 Cache.__init__(self, maxsize, getsizeof) 

340 self.__timer = _TimedCache._Timer(timer) 

341 

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

343 with self.__timer as time: 

344 self.expire(time) 

345 return cache_repr(self) 

346 

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

348 with self.__timer as time: 

349 self.expire(time) 

350 return cache_len(self) 

351 

352 @property 

353 def currsize(self): 

354 with self.__timer as time: 

355 self.expire(time) 

356 return super().currsize 

357 

358 @property 

359 def timer(self): 

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

361 return self.__timer 

362 

363 def clear(self): 

364 with self.__timer as time: 

365 self.expire(time) 

366 Cache.clear(self) 

367 

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

369 with self.__timer: 

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

371 

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

373 with self.__timer: 

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

375 

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

377 with self.__timer: 

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

379 

380 

381class TTLCache(_TimedCache): 

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

383 

384 class _Link: 

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

386 

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

388 self.key = key 

389 self.expires = expires 

390 

391 def __reduce__(self): 

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

393 

394 def unlink(self): 

395 next = self.next 

396 prev = self.prev 

397 prev.next = next 

398 next.prev = prev 

399 

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

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

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

403 root.prev = root.next = root 

404 self.__links = collections.OrderedDict() 

405 self.__ttl = ttl 

406 

407 def __contains__(self, key): 

408 try: 

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

410 except KeyError: 

411 return False 

412 else: 

413 return self.timer() < link.expires 

414 

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

416 try: 

417 link = self.__getlink(key) 

418 except KeyError: 

419 expired = False 

420 else: 

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

422 if expired: 

423 return self.__missing__(key) 

424 else: 

425 return cache_getitem(self, key) 

426 

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

428 with self.timer as time: 

429 self.expire(time) 

430 cache_setitem(self, key, value) 

431 try: 

432 link = self.__getlink(key) 

433 except KeyError: 

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

435 else: 

436 link.unlink() 

437 link.expires = time + self.__ttl 

438 link.next = root = self.__root 

439 link.prev = prev = root.prev 

440 prev.next = root.prev = link 

441 

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

443 cache_delitem(self, key) 

444 link = self.__links.pop(key) 

445 link.unlink() 

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

447 raise KeyError(key) 

448 

449 def __iter__(self): 

450 root = self.__root 

451 curr = root.next 

452 while curr is not root: 

453 # "freeze" time for iterator access 

454 with self.timer as time: 

455 if time < curr.expires: 

456 yield curr.key 

457 curr = curr.next 

458 

459 def __setstate__(self, state): 

460 self.__dict__.update(state) 

461 root = self.__root 

462 root.prev = root.next = root 

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

464 link.next = root 

465 link.prev = prev = root.prev 

466 prev.next = root.prev = link 

467 self.expire(self.timer()) 

468 

469 @property 

470 def ttl(self): 

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

472 return self.__ttl 

473 

474 def expire(self, time=None): 

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

476 expired `(key, value)` pairs. 

477 

478 """ 

479 if time is None: 

480 time = self.timer() 

481 root = self.__root 

482 curr = root.next 

483 links = self.__links 

484 expired = [] 

485 cache_delitem = Cache.__delitem__ 

486 cache_getitem = Cache.__getitem__ 

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

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

489 cache_delitem(self, curr.key) 

490 del links[curr.key] 

491 next = curr.next 

492 curr.unlink() 

493 curr = next 

494 return expired 

495 

496 def popitem(self): 

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

498 has not already expired. 

499 

500 """ 

501 with self.timer as time: 

502 self.expire(time) 

503 try: 

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

505 except StopIteration: 

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

507 else: 

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

509 

510 def __getlink(self, key): 

511 value = self.__links[key] 

512 self.__links.move_to_end(key) 

513 return value 

514 

515 

516class TLRUCache(_TimedCache): 

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

518 

519 @functools.total_ordering 

520 class _Item: 

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

522 

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

524 self.key = key 

525 self.expires = expires 

526 self.removed = False 

527 

528 def __lt__(self, other): 

529 return self.expires < other.expires 

530 

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

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

533 self.__items = collections.OrderedDict() 

534 self.__order = [] 

535 self.__ttu = ttu 

536 

537 def __contains__(self, key): 

538 try: 

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

540 except KeyError: 

541 return False 

542 else: 

543 return self.timer() < item.expires 

544 

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

546 try: 

547 item = self.__getitem(key) 

548 except KeyError: 

549 expired = False 

550 else: 

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

552 if expired: 

553 return self.__missing__(key) 

554 else: 

555 return cache_getitem(self, key) 

556 

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

558 with self.timer as time: 

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

560 if not (time < expires): 

561 return # skip expired items 

562 self.expire(time) 

563 cache_setitem(self, key, value) 

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

565 # only mark it as removed for now 

566 try: 

567 self.__getitem(key).removed = True 

568 except KeyError: 

569 pass 

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

571 heapq.heappush(self.__order, item) 

572 

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

574 with self.timer as time: 

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

576 cache_delitem(self, key) 

577 item = self.__items.pop(key) 

578 item.removed = True 

579 if not (time < item.expires): 

580 raise KeyError(key) 

581 

582 def __iter__(self): 

583 for curr in self.__order: 

584 # "freeze" time for iterator access 

585 with self.timer as time: 

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

587 yield curr.key 

588 

589 @property 

590 def ttu(self): 

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

592 return self.__ttu 

593 

594 def expire(self, time=None): 

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

596 expired `(key, value)` pairs. 

597 

598 """ 

599 if time is None: 

600 time = self.timer() 

601 items = self.__items 

602 order = self.__order 

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

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

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

606 heapq.heapify(order) 

607 expired = [] 

608 cache_delitem = Cache.__delitem__ 

609 cache_getitem = Cache.__getitem__ 

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

611 item = heapq.heappop(order) 

612 if not item.removed: 

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

614 cache_delitem(self, item.key) 

615 del items[item.key] 

616 return expired 

617 

618 def popitem(self): 

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

620 has not already expired. 

621 

622 """ 

623 with self.timer as time: 

624 self.expire(time) 

625 try: 

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

627 except StopIteration: 

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

629 else: 

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

631 

632 def __getitem(self, key): 

633 value = self.__items[key] 

634 self.__items.move_to_end(key) 

635 return value 

636 

637 

638_CacheInfo = collections.namedtuple( 

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

640) 

641 

642 

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

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

645 results in a cache. 

646 

647 """ 

648 from ._cached import _wrapper 

649 

650 if isinstance(condition, bool): 

651 from warnings import warn 

652 

653 warn( 

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

655 DeprecationWarning, 

656 stacklevel=2, 

657 ) 

658 info = condition 

659 condition = None 

660 

661 def decorator(func): 

662 if info: 

663 if isinstance(cache, Cache): 

664 

665 def make_info(hits, misses): 

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

667 

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

669 

670 def make_info(hits, misses): 

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

672 

673 else: 

674 

675 def make_info(hits, misses): 

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

677 

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

679 else: 

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

681 

682 return decorator 

683 

684 

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

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

687 callable that saves results in a cache. 

688 

689 """ 

690 from ._cachedmethod import _wrapper 

691 

692 def decorator(method): 

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

694 

695 return decorator