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.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 self.__index = {} 

292 self.__keys = [] 

293 

294 @property 

295 def choice(self): 

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

297 return self.__choice 

298 

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

300 cache_setitem(self, key, value) 

301 if key not in self.__index: 

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

303 self.__keys.append(key) 

304 

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

306 cache_delitem(self, key) 

307 index = self.__index.pop(key) 

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

309 last = self.__keys[-1] 

310 self.__keys[index] = last 

311 self.__index[last] = index 

312 self.__keys.pop() 

313 

314 def popitem(self): 

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

316 try: 

317 key = self.__choice(self.__keys) 

318 except IndexError: 

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

320 else: 

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

322 

323 

324class _TimedCache(Cache): 

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

326 

327 class _Timer: 

328 def __init__(self, timer): 

329 self.__timer = timer 

330 self.__nesting = 0 

331 

332 def __call__(self): 

333 if self.__nesting == 0: 

334 return self.__timer() 

335 else: 

336 return self.__time 

337 

338 def __enter__(self): 

339 if self.__nesting == 0: 

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

341 else: 

342 time = self.__time 

343 self.__nesting += 1 

344 return time 

345 

346 def __exit__(self, *exc): 

347 self.__nesting -= 1 

348 

349 def __reduce__(self): 

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

351 

352 def __getattr__(self, name): 

353 return getattr(self.__timer, name) 

354 

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

356 Cache.__init__(self, maxsize, getsizeof) 

357 self.__timer = _TimedCache._Timer(timer) 

358 

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

360 with self.__timer as time: 

361 self.expire(time) 

362 return cache_repr(self) 

363 

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

365 with self.__timer as time: 

366 self.expire(time) 

367 return cache_len(self) 

368 

369 @property 

370 def currsize(self): 

371 with self.__timer as time: 

372 self.expire(time) 

373 return super().currsize 

374 

375 @property 

376 def timer(self): 

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

378 return self.__timer 

379 

380 def clear(self): 

381 with self.__timer as time: 

382 self.expire(time) 

383 Cache.clear(self) 

384 

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

386 with self.__timer: 

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

388 

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

390 with self.__timer: 

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

392 

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

394 with self.__timer: 

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

396 

397 

398class TTLCache(_TimedCache): 

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

400 

401 class _Link: 

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

403 

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

405 self.key = key 

406 self.expires = expires 

407 

408 def __reduce__(self): 

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

410 

411 def unlink(self): 

412 next = self.next 

413 prev = self.prev 

414 prev.next = next 

415 next.prev = prev 

416 

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

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

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

420 root.prev = root.next = root 

421 self.__links = collections.OrderedDict() 

422 self.__ttl = ttl 

423 

424 def __contains__(self, key): 

425 try: 

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

427 except KeyError: 

428 return False 

429 else: 

430 return self.timer() < link.expires 

431 

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

433 try: 

434 link = self.__getlink(key) 

435 except KeyError: 

436 expired = False 

437 else: 

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

439 if expired: 

440 return self.__missing__(key) 

441 else: 

442 return cache_getitem(self, key) 

443 

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

445 with self.timer as time: 

446 self.expire(time) 

447 cache_setitem(self, key, value) 

448 try: 

449 link = self.__getlink(key) 

450 except KeyError: 

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

452 else: 

453 link.unlink() 

454 link.expires = time + self.__ttl 

455 link.next = root = self.__root 

456 link.prev = prev = root.prev 

457 prev.next = root.prev = link 

458 

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

460 cache_delitem(self, key) 

461 link = self.__links.pop(key) 

462 link.unlink() 

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

464 raise KeyError(key) 

465 

466 def __iter__(self): 

467 root = self.__root 

468 curr = root.next 

469 while curr is not root: 

470 # "freeze" time for iterator access 

471 with self.timer as time: 

472 if time < curr.expires: 

473 yield curr.key 

474 curr = curr.next 

475 

476 def __setstate__(self, state): 

477 self.__dict__.update(state) 

478 root = self.__root 

479 root.prev = root.next = root 

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

481 link.next = root 

482 link.prev = prev = root.prev 

483 prev.next = root.prev = link 

484 self.expire(self.timer()) 

485 

486 @property 

487 def ttl(self): 

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

489 return self.__ttl 

490 

491 def expire(self, time=None): 

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

493 expired `(key, value)` pairs. 

494 

495 """ 

496 if time is None: 

497 time = self.timer() 

498 root = self.__root 

499 curr = root.next 

500 links = self.__links 

501 expired = [] 

502 cache_delitem = Cache.__delitem__ 

503 cache_getitem = Cache.__getitem__ 

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

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

506 cache_delitem(self, curr.key) 

507 del links[curr.key] 

508 next = curr.next 

509 curr.unlink() 

510 curr = next 

511 return expired 

512 

513 def popitem(self): 

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

515 has not already expired. 

516 

517 """ 

518 with self.timer as time: 

519 self.expire(time) 

520 try: 

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

522 except StopIteration: 

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

524 else: 

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

526 

527 def __getlink(self, key): 

528 value = self.__links[key] 

529 self.__links.move_to_end(key) 

530 return value 

531 

532 

533class TLRUCache(_TimedCache): 

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

535 

536 @functools.total_ordering 

537 class _Item: 

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

539 

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

541 self.key = key 

542 self.expires = expires 

543 self.removed = False 

544 

545 def __lt__(self, other): 

546 return self.expires < other.expires 

547 

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

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

550 self.__items = collections.OrderedDict() 

551 self.__order = [] 

552 self.__ttu = ttu 

553 

554 def __contains__(self, key): 

555 try: 

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

557 except KeyError: 

558 return False 

559 else: 

560 return self.timer() < item.expires 

561 

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

563 try: 

564 item = self.__getitem(key) 

565 except KeyError: 

566 expired = False 

567 else: 

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

569 if expired: 

570 return self.__missing__(key) 

571 else: 

572 return cache_getitem(self, key) 

573 

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

575 with self.timer as time: 

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

577 if not (time < expires): 

578 return # skip expired items 

579 self.expire(time) 

580 cache_setitem(self, key, value) 

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

582 # only mark it as removed for now 

583 try: 

584 self.__getitem(key).removed = True 

585 except KeyError: 

586 pass 

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

588 heapq.heappush(self.__order, item) 

589 

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

591 with self.timer as time: 

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

593 cache_delitem(self, key) 

594 item = self.__items.pop(key) 

595 item.removed = True 

596 if not (time < item.expires): 

597 raise KeyError(key) 

598 

599 def __iter__(self): 

600 for curr in self.__order: 

601 # "freeze" time for iterator access 

602 with self.timer as time: 

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

604 yield curr.key 

605 

606 @property 

607 def ttu(self): 

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

609 return self.__ttu 

610 

611 def expire(self, time=None): 

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

613 expired `(key, value)` pairs. 

614 

615 """ 

616 if time is None: 

617 time = self.timer() 

618 items = self.__items 

619 order = self.__order 

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

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

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

623 heapq.heapify(order) 

624 expired = [] 

625 cache_delitem = Cache.__delitem__ 

626 cache_getitem = Cache.__getitem__ 

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

628 item = heapq.heappop(order) 

629 if not item.removed: 

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

631 cache_delitem(self, item.key) 

632 del items[item.key] 

633 return expired 

634 

635 def popitem(self): 

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

637 has not already expired. 

638 

639 """ 

640 with self.timer as time: 

641 self.expire(time) 

642 try: 

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

644 except StopIteration: 

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

646 else: 

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

648 

649 def __getitem(self, key): 

650 value = self.__items[key] 

651 self.__items.move_to_end(key) 

652 return value 

653 

654 

655_CacheInfo = collections.namedtuple( 

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

657) 

658 

659 

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

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

662 results in a cache. 

663 

664 """ 

665 from ._cached import _wrapper 

666 

667 if isinstance(condition, bool): 

668 from warnings import warn 

669 

670 warn( 

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

672 DeprecationWarning, 

673 stacklevel=2, 

674 ) 

675 info = condition 

676 condition = None 

677 

678 def decorator(func): 

679 if info: 

680 if isinstance(cache, Cache): 

681 

682 def make_info(hits, misses): 

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

684 

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

686 

687 def make_info(hits, misses): 

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

689 

690 else: 

691 

692 def make_info(hits, misses): 

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

694 

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

696 else: 

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

698 

699 return decorator 

700 

701 

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

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

704 callable that saves results in a cache. 

705 

706 """ 

707 from ._cachedmethod import _wrapper 

708 

709 def decorator(method): 

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

711 

712 return decorator