codekingpro/portable-devtools
114k
1"use strict";
2/**
3 * @module LRUCache
4 */
5Object.defineProperty(exports, "__esModule", { value: true });
6exports.LRUCache = void 0;
7const defaultPerf = (typeof performance === 'object' &&
8 performance &&
9 typeof performance.now === 'function') ?
10 performance
11 : Date;
12const warned = new Set();
13/* c8 ignore start */
14const PROCESS = (typeof process === 'object' && !!process ?
15 process
16 : {});
17/* c8 ignore start */
18const emitWarning = (msg, type, code, fn) => {
19 typeof PROCESS.emitWarning === 'function' ?
20 PROCESS.emitWarning(msg, type, code, fn)
21 : console.error(`[${code}] ${type}: ${msg}`);
22};
23let AC = globalThis.AbortController;
24let AS = globalThis.AbortSignal;
25/* c8 ignore start */
26if (typeof AC === 'undefined') {
27 //@ts-ignore
28 AS = class AbortSignal {
29 onabort;
30 _onabort = [];
31 reason;
32 aborted = false;
33 addEventListener(_, fn) {
34 this._onabort.push(fn);
35 }
36 };
37 //@ts-ignore
38 AC = class AbortController {
39 constructor() {
40 warnACPolyfill();
41 }
42 signal = new AS();
43 abort(reason) {
44 if (this.signal.aborted)
45 return;
46 //@ts-ignore
47 this.signal.reason = reason;
48 //@ts-ignore
49 this.signal.aborted = true;
50 //@ts-ignore
51 for (const fn of this.signal._onabort) {
52 fn(reason);
53 }
54 this.signal.onabort?.(reason);
55 }
56 };
57 let printACPolyfillWarning = PROCESS.env?.LRU_CACHE_IGNORE_AC_WARNING !== '1';
58 const warnACPolyfill = () => {
59 if (!printACPolyfillWarning)
60 return;
61 printACPolyfillWarning = false;
62 emitWarning('AbortController is not defined. If using lru-cache in ' +
63 'node 14, load an AbortController polyfill from the ' +
64 '`node-abort-controller` package. A minimal polyfill is ' +
65 'provided for use by LRUCache.fetch(), but it should not be ' +
66 'relied upon in other contexts (eg, passing it to other APIs that ' +
67 'use AbortController/AbortSignal might have undesirable effects). ' +
68 'You may disable this with LRU_CACHE_IGNORE_AC_WARNING=1 in the env.', 'NO_ABORT_CONTROLLER', 'ENOTSUP', warnACPolyfill);
69 };
70}
71/* c8 ignore stop */
72const shouldWarn = (code) => !warned.has(code);
73const TYPE = Symbol('type');
74const isPosInt = (n) => n && n === Math.floor(n) && n > 0 && isFinite(n);
75/* c8 ignore start */
76// This is a little bit ridiculous, tbh.
77// The maximum array length is 2^32-1 or thereabouts on most JS impls.
78// And well before that point, you're caching the entire world, I mean,
79// that's ~32GB of just integers for the next/prev links, plus whatever
80// else to hold that many keys and values. Just filling the memory with
81// zeroes at init time is brutal when you get that big.
82// But why not be complete?
83// Maybe in the future, these limits will have expanded.
84const getUintArray = (max) => !isPosInt(max) ? null
85 : max <= Math.pow(2, 8) ? Uint8Array
86 : max <= Math.pow(2, 16) ? Uint16Array
87 : max <= Math.pow(2, 32) ? Uint32Array
88 : max <= Number.MAX_SAFE_INTEGER ? ZeroArray
89 : null;
90/* c8 ignore stop */
91class ZeroArray extends Array {
92 constructor(size) {
93 super(size);
94 this.fill(0);
95 }
96}
97class Stack {
98 heap;
99 length;
100 // private constructor
101 static #constructing = false;
102 static create(max) {
103 const HeapCls = getUintArray(max);
104 if (!HeapCls)
105 return [];
106 Stack.#constructing = true;
107 const s = new Stack(max, HeapCls);
108 Stack.#constructing = false;
109 return s;
110 }
111 constructor(max, HeapCls) {
112 /* c8 ignore start */
113 if (!Stack.#constructing) {
114 throw new TypeError('instantiate Stack using Stack.create(n)');
115 }
116 /* c8 ignore stop */
117 this.heap = new HeapCls(max);
118 this.length = 0;
119 }
120 push(n) {
121 this.heap[this.length++] = n;
122 }
123 pop() {
124 return this.heap[--this.length];
125 }
126}
127/**
128 * Default export, the thing you're using this module to get.
129 *
130 * The `K` and `V` types define the key and value types, respectively. The
131 * optional `FC` type defines the type of the `context` object passed to
132 * `cache.fetch()` and `cache.memo()`.
133 *
134 * Keys and values **must not** be `null` or `undefined`.
135 *
136 * All properties from the options object (with the exception of `max`,
137 * `maxSize`, `fetchMethod`, `memoMethod`, `dispose` and `disposeAfter`) are
138 * added as normal public members. (The listed options are read-only getters.)
139 *
140 * Changing any of these will alter the defaults for subsequent method calls.
141 */
142class LRUCache {
143 // options that cannot be changed without disaster
144 #max;
145 #maxSize;
146 #dispose;
147 #onInsert;
148 #disposeAfter;
149 #fetchMethod;
150 #memoMethod;
151 #perf;
152 /**
153 * {@link LRUCache.OptionsBase.perf}
154 */
155 get perf() {
156 return this.#perf;
157 }
158 /**
159 * {@link LRUCache.OptionsBase.ttl}
160 */
161 ttl;
162 /**
163 * {@link LRUCache.OptionsBase.ttlResolution}
164 */
165 ttlResolution;
166 /**
167 * {@link LRUCache.OptionsBase.ttlAutopurge}
168 */
169 ttlAutopurge;
170 /**
171 * {@link LRUCache.OptionsBase.updateAgeOnGet}
172 */
173 updateAgeOnGet;
174 /**
175 * {@link LRUCache.OptionsBase.updateAgeOnHas}
176 */
177 updateAgeOnHas;
178 /**
179 * {@link LRUCache.OptionsBase.allowStale}
180 */
181 allowStale;
182 /**
183 * {@link LRUCache.OptionsBase.noDisposeOnSet}
184 */
185 noDisposeOnSet;
186 /**
187 * {@link LRUCache.OptionsBase.noUpdateTTL}
188 */
189 noUpdateTTL;
190 /**
191 * {@link LRUCache.OptionsBase.maxEntrySize}
192 */
193 maxEntrySize;
194 /**
195 * {@link LRUCache.OptionsBase.sizeCalculation}
196 */
197 sizeCalculation;
198 /**
199 * {@link LRUCache.OptionsBase.noDeleteOnFetchRejection}
200 */
201 noDeleteOnFetchRejection;
202 /**
203 * {@link LRUCache.OptionsBase.noDeleteOnStaleGet}
204 */
205 noDeleteOnStaleGet;
206 /**
207 * {@link LRUCache.OptionsBase.allowStaleOnFetchAbort}
208 */
209 allowStaleOnFetchAbort;
210 /**
211 * {@link LRUCache.OptionsBase.allowStaleOnFetchRejection}
212 */
213 allowStaleOnFetchRejection;
214 /**
215 * {@link LRUCache.OptionsBase.ignoreFetchAbort}
216 */
217 ignoreFetchAbort;
218 // computed properties
219 #size;
220 #calculatedSize;
221 #keyMap;
222 #keyList;
223 #valList;
224 #next;
225 #prev;
226 #head;
227 #tail;
228 #free;
229 #disposed;
230 #sizes;
231 #starts;
232 #ttls;
233 #autopurgeTimers;
234 #hasDispose;
235 #hasFetchMethod;
236 #hasDisposeAfter;
237 #hasOnInsert;
238 /**
239 * Do not call this method unless you need to inspect the
240 * inner workings of the cache. If anything returned by this
241 * object is modified in any way, strange breakage may occur.
242 *
243 * These fields are private for a reason!
244 *
245 * @internal
246 */
247 static unsafeExposeInternals(c) {
248 return {
249 // properties
250 starts: c.#starts,
251 ttls: c.#ttls,
252 autopurgeTimers: c.#autopurgeTimers,
253 sizes: c.#sizes,
254 keyMap: c.#keyMap,
255 keyList: c.#keyList,
256 valList: c.#valList,
257 next: c.#next,
258 prev: c.#prev,
259 get head() {
260 return c.#head;
261 },
262 get tail() {
263 return c.#tail;
264 },
265 free: c.#free,
266 // methods
267 isBackgroundFetch: (p) => c.#isBackgroundFetch(p),
268 backgroundFetch: (k, index, options, context) => c.#backgroundFetch(k, index, options, context),
269 moveToTail: (index) => c.#moveToTail(index),
270 indexes: (options) => c.#indexes(options),
271 rindexes: (options) => c.#rindexes(options),
272 isStale: (index) => c.#isStale(index),
273 };
274 }
275 // Protected read-only members
276 /**
277 * {@link LRUCache.OptionsBase.max} (read-only)
278 */
279 get max() {
280 return this.#max;
281 }
282 /**
283 * {@link LRUCache.OptionsBase.maxSize} (read-only)
284 */
285 get maxSize() {
286 return this.#maxSize;
287 }
288 /**
289 * The total computed size of items in the cache (read-only)
290 */
291 get calculatedSize() {
292 return this.#calculatedSize;
293 }
294 /**
295 * The number of items stored in the cache (read-only)
296 */
297 get size() {
298 return this.#size;
299 }
300 /**
301 * {@link LRUCache.OptionsBase.fetchMethod} (read-only)
302 */
303 get fetchMethod() {
304 return this.#fetchMethod;
305 }
306 get memoMethod() {
307 return this.#memoMethod;
308 }
309 /**
310 * {@link LRUCache.OptionsBase.dispose} (read-only)
311 */
312 get dispose() {
313 return this.#dispose;
314 }
315 /**
316 * {@link LRUCache.OptionsBase.onInsert} (read-only)
317 */
318 get onInsert() {
319 return this.#onInsert;
320 }
321 /**
322 * {@link LRUCache.OptionsBase.disposeAfter} (read-only)
323 */
324 get disposeAfter() {
325 return this.#disposeAfter;
326 }
327 constructor(options) {
328 const { max = 0, ttl, ttlResolution = 1, ttlAutopurge, updateAgeOnGet, updateAgeOnHas, allowStale, dispose, onInsert, disposeAfter, noDisposeOnSet, noUpdateTTL, maxSize = 0, maxEntrySize = 0, sizeCalculation, fetchMethod, memoMethod, noDeleteOnFetchRejection, noDeleteOnStaleGet, allowStaleOnFetchRejection, allowStaleOnFetchAbort, ignoreFetchAbort, perf, } = options;
329 if (perf !== undefined) {
330 if (typeof perf?.now !== 'function') {
331 throw new TypeError('perf option must have a now() method if specified');
332 }
333 }
334 this.#perf = perf ?? defaultPerf;
335 if (max !== 0 && !isPosInt(max)) {
336 throw new TypeError('max option must be a nonnegative integer');
337 }
338 const UintArray = max ? getUintArray(max) : Array;
339 if (!UintArray) {
340 throw new Error('invalid max value: ' + max);
341 }
342 this.#max = max;
343 this.#maxSize = maxSize;
344 this.maxEntrySize = maxEntrySize || this.#maxSize;
345 this.sizeCalculation = sizeCalculation;
346 if (this.sizeCalculation) {
347 if (!this.#maxSize && !this.maxEntrySize) {
348 throw new TypeError('cannot set sizeCalculation without setting maxSize or maxEntrySize');
349 }
350 if (typeof this.sizeCalculation !== 'function') {
351 throw new TypeError('sizeCalculation set to non-function');
352 }
353 }
354 if (memoMethod !== undefined && typeof memoMethod !== 'function') {
355 throw new TypeError('memoMethod must be a function if defined');
356 }
357 this.#memoMethod = memoMethod;
358 if (fetchMethod !== undefined && typeof fetchMethod !== 'function') {
359 throw new TypeError('fetchMethod must be a function if specified');
360 }
361 this.#fetchMethod = fetchMethod;
362 this.#hasFetchMethod = !!fetchMethod;
363 this.#keyMap = new Map();
364 this.#keyList = new Array(max).fill(undefined);
365 this.#valList = new Array(max).fill(undefined);
366 this.#next = new UintArray(max);
367 this.#prev = new UintArray(max);
368 this.#head = 0;
369 this.#tail = 0;
370 this.#free = Stack.create(max);
371 this.#size = 0;
372 this.#calculatedSize = 0;
373 if (typeof dispose === 'function') {
374 this.#dispose = dispose;
375 }
376 if (typeof onInsert === 'function') {
377 this.#onInsert = onInsert;
378 }
379 if (typeof disposeAfter === 'function') {
380 this.#disposeAfter = disposeAfter;
381 this.#disposed = [];
382 }
383 else {
384 this.#disposeAfter = undefined;
385 this.#disposed = undefined;
386 }
387 this.#hasDispose = !!this.#dispose;
388 this.#hasOnInsert = !!this.#onInsert;
389 this.#hasDisposeAfter = !!this.#disposeAfter;
390 this.noDisposeOnSet = !!noDisposeOnSet;
391 this.noUpdateTTL = !!noUpdateTTL;
392 this.noDeleteOnFetchRejection = !!noDeleteOnFetchRejection;
393 this.allowStaleOnFetchRejection = !!allowStaleOnFetchRejection;
394 this.allowStaleOnFetchAbort = !!allowStaleOnFetchAbort;
395 this.ignoreFetchAbort = !!ignoreFetchAbort;
396 // NB: maxEntrySize is set to maxSize if it's set
397 if (this.maxEntrySize !== 0) {
398 if (this.#maxSize !== 0) {
399 if (!isPosInt(this.#maxSize)) {
400 throw new TypeError('maxSize must be a positive integer if specified');
401 }
402 }
403 if (!isPosInt(this.maxEntrySize)) {
404 throw new TypeError('maxEntrySize must be a positive integer if specified');
405 }
406 this.#initializeSizeTracking();
407 }
408 this.allowStale = !!allowStale;
409 this.noDeleteOnStaleGet = !!noDeleteOnStaleGet;
410 this.updateAgeOnGet = !!updateAgeOnGet;
411 this.updateAgeOnHas = !!updateAgeOnHas;
412 this.ttlResolution =
413 isPosInt(ttlResolution) || ttlResolution === 0 ? ttlResolution : 1;
414 this.ttlAutopurge = !!ttlAutopurge;
415 this.ttl = ttl || 0;
416 if (this.ttl) {
417 if (!isPosInt(this.ttl)) {
418 throw new TypeError('ttl must be a positive integer if specified');
419 }
420 this.#initializeTTLTracking();
421 }
422 // do not allow completely unbounded caches
423 if (this.#max === 0 && this.ttl === 0 && this.#maxSize === 0) {
424 throw new TypeError('At least one of max, maxSize, or ttl is required');
425 }
426 if (!this.ttlAutopurge && !this.#max && !this.#maxSize) {
427 const code = 'LRU_CACHE_UNBOUNDED';
428 if (shouldWarn(code)) {
429 warned.add(code);
430 const msg = 'TTL caching without ttlAutopurge, max, or maxSize can ' +
431 'result in unbounded memory consumption.';
432 emitWarning(msg, 'UnboundedCacheWarning', code, LRUCache);
433 }
434 }
435 }
436 /**
437 * Return the number of ms left in the item's TTL. If item is not in cache,
438 * returns `0`. Returns `Infinity` if item is in cache without a defined TTL.
439 */
440 getRemainingTTL(key) {
441 return this.#keyMap.has(key) ? Infinity : 0;
442 }
443 #initializeTTLTracking() {
444 const ttls = new ZeroArray(this.#max);
445 const starts = new ZeroArray(this.#max);
446 this.#ttls = ttls;
447 this.#starts = starts;
448 const purgeTimers = this.ttlAutopurge ?
449 new Array(this.#max)
450 : undefined;
451 this.#autopurgeTimers = purgeTimers;
452 this.#setItemTTL = (index, ttl, start = this.#perf.now()) => {
453 starts[index] = ttl !== 0 ? start : 0;
454 ttls[index] = ttl;
455 setPurgetTimer(index, ttl);
456 };
457 this.#updateItemAge = index => {
458 starts[index] = ttls[index] !== 0 ? this.#perf.now() : 0;
459 setPurgetTimer(index, ttls[index]);
460 };
461 // clear out the purge timer if we're setting TTL to 0, and
462 // previously had a ttl purge timer running, so it doesn't
463 // fire unnecessarily. Don't need to do this if we're not doing
464 // autopurge.
465 const setPurgetTimer = !this.ttlAutopurge ?
466 () => { }
467 : (index, ttl) => {
468 if (purgeTimers?.[index]) {
469 clearTimeout(purgeTimers[index]);
470 purgeTimers[index] = undefined;
471 }
472 if (ttl && ttl !== 0 && purgeTimers) {
473 const t = setTimeout(() => {
474 if (this.#isStale(index)) {
475 this.#delete(this.#keyList[index], 'expire');
476 }
477 }, ttl + 1);
478 // unref() not supported on all platforms
479 /* c8 ignore start */
480 if (t.unref) {
481 t.unref();
482 }
483 /* c8 ignore stop */
484 purgeTimers[index] = t;
485 }
486 };
487 this.#statusTTL = (status, index) => {
488 if (ttls[index]) {
489 const ttl = ttls[index];
490 const start = starts[index];
491 /* c8 ignore next */
492 if (!ttl || !start)
493 return;
494 status.ttl = ttl;
495 status.start = start;
496 status.now = cachedNow || getNow();
497 const age = status.now - start;
498 status.remainingTTL = ttl - age;
499 }
500 };
501 // debounce calls to perf.now() to 1s so we're not hitting
502 // that costly call repeatedly.
503 let cachedNow = 0;
504 const getNow = () => {
505 const n = this.#perf.now();
506 if (this.ttlResolution > 0) {
507 cachedNow = n;
508 const t = setTimeout(() => (cachedNow = 0), this.ttlResolution);
509 // not available on all platforms
510 /* c8 ignore start */
511 if (t.unref) {
512 t.unref();
513 }
514 /* c8 ignore stop */
515 }
516 return n;
517 };
518 this.getRemainingTTL = key => {
519 const index = this.#keyMap.get(key);
520 if (index === undefined) {
521 return 0;
522 }
523 const ttl = ttls[index];
524 const start = starts[index];
525 if (!ttl || !start) {
526 return Infinity;
527 }
528 const age = (cachedNow || getNow()) - start;
529 return ttl - age;
530 };
531 this.#isStale = index => {
532 const s = starts[index];
533 const t = ttls[index];
534 return !!t && !!s && (cachedNow || getNow()) - s > t;
535 };
536 }
537 // conditionally set private methods related to TTL
538 #updateItemAge = () => { };
539 #statusTTL = () => { };
540 #setItemTTL = () => { };
541 /* c8 ignore stop */
542 #isStale = () => false;
543 #initializeSizeTracking() {
544 const sizes = new ZeroArray(this.#max);
545 this.#calculatedSize = 0;
546 this.#sizes = sizes;
547 this.#removeItemSize = index => {
548 this.#calculatedSize -= sizes[index];
549 sizes[index] = 0;
550 };
551 this.#requireSize = (k, v, size, sizeCalculation) => {
552 // provisionally accept background fetches.
553 // actual value size will be checked when they return.
554 if (this.#isBackgroundFetch(v)) {
555 return 0;
556 }
557 if (!isPosInt(size)) {
558 if (sizeCalculation) {
559 if (typeof sizeCalculation !== 'function') {
560 throw new TypeError('sizeCalculation must be a function');
561 }
562 size = sizeCalculation(v, k);
563 if (!isPosInt(size)) {
564 throw new TypeError('sizeCalculation return invalid (expect positive integer)');
565 }
566 }
567 else {
568 throw new TypeError('invalid size value (must be positive integer). ' +
569 'When maxSize or maxEntrySize is used, sizeCalculation ' +
570 'or size must be set.');
571 }
572 }
573 return size;
574 };
575 this.#addItemSize = (index, size, status) => {
576 sizes[index] = size;
577 if (this.#maxSize) {
578 const maxSize = this.#maxSize - sizes[index];
579 while (this.#calculatedSize > maxSize) {
580 this.#evict(true);
581 }
582 }
583 this.#calculatedSize += sizes[index];
584 if (status) {
585 status.entrySize = size;
586 status.totalCalculatedSize = this.#calculatedSize;
587 }
588 };
589 }
590 #removeItemSize = _i => { };
591 #addItemSize = (_i, _s, _st) => { };
592 #requireSize = (_k, _v, size, sizeCalculation) => {
593 if (size || sizeCalculation) {
594 throw new TypeError('cannot set size without setting maxSize or maxEntrySize on cache');
595 }
596 return 0;
597 };
598 *#indexes({ allowStale = this.allowStale } = {}) {
599 if (this.#size) {
600 for (let i = this.#tail; true;) {
601 if (!this.#isValidIndex(i)) {
602 break;
603 }
604 if (allowStale || !this.#isStale(i)) {
605 yield i;
606 }
607 if (i === this.#head) {
608 break;
609 }
610 else {
611 i = this.#prev[i];
612 }
613 }
614 }
615 }
616 *#rindexes({ allowStale = this.allowStale } = {}) {
617 if (this.#size) {
618 for (let i = this.#head; true;) {
619 if (!this.#isValidIndex(i)) {
620 break;
621 }
622 if (allowStale || !this.#isStale(i)) {
623 yield i;
624 }
625 if (i === this.#tail) {
626 break;
627 }
628 else {
629 i = this.#next[i];
630 }
631 }
632 }
633 }
634 #isValidIndex(index) {
635 return (index !== undefined &&
636 this.#keyMap.get(this.#keyList[index]) === index);
637 }
638 /**
639 * Return a generator yielding `[key, value]` pairs,
640 * in order from most recently used to least recently used.
641 */
642 *entries() {
643 for (const i of this.#indexes()) {
644 if (this.#valList[i] !== undefined &&
645 this.#keyList[i] !== undefined &&
646 !this.#isBackgroundFetch(this.#valList[i])) {
647 yield [this.#keyList[i], this.#valList[i]];
648 }
649 }
650 }
651 /**
652 * Inverse order version of {@link LRUCache.entries}
653 *
654 * Return a generator yielding `[key, value]` pairs,
655 * in order from least recently used to most recently used.
656 */
657 *rentries() {
658 for (const i of this.#rindexes()) {
659 if (this.#valList[i] !== undefined &&
660 this.#keyList[i] !== undefined &&
661 !this.#isBackgroundFetch(this.#valList[i])) {
662 yield [this.#keyList[i], this.#valList[i]];
663 }
664 }
665 }
666 /**
667 * Return a generator yielding the keys in the cache,
668 * in order from most recently used to least recently used.
669 */
670 *keys() {
671 for (const i of this.#indexes()) {
672 const k = this.#keyList[i];
673 if (k !== undefined && !this.#isBackgroundFetch(this.#valList[i])) {
674 yield k;
675 }
676 }
677 }
678 /**
679 * Inverse order version of {@link LRUCache.keys}
680 *
681 * Return a generator yielding the keys in the cache,
682 * in order from least recently used to most recently used.
683 */
684 *rkeys() {
685 for (const i of this.#rindexes()) {
686 const k = this.#keyList[i];
687 if (k !== undefined && !this.#isBackgroundFetch(this.#valList[i])) {
688 yield k;
689 }
690 }
691 }
692 /**
693 * Return a generator yielding the values in the cache,
694 * in order from most recently used to least recently used.
695 */
696 *values() {
697 for (const i of this.#indexes()) {
698 const v = this.#valList[i];
699 if (v !== undefined && !this.#isBackgroundFetch(this.#valList[i])) {
700 yield this.#valList[i];
701 }
702 }
703 }
704 /**
705 * Inverse order version of {@link LRUCache.values}
706 *
707 * Return a generator yielding the values in the cache,
708 * in order from least recently used to most recently used.
709 */
710 *rvalues() {
711 for (const i of this.#rindexes()) {
712 const v = this.#valList[i];
713 if (v !== undefined && !this.#isBackgroundFetch(this.#valList[i])) {
714 yield this.#valList[i];
715 }
716 }
717 }
718 /**
719 * Iterating over the cache itself yields the same results as
720 * {@link LRUCache.entries}
721 */
722 [Symbol.iterator]() {
723 return this.entries();
724 }
725 /**
726 * A String value that is used in the creation of the default string
727 * description of an object. Called by the built-in method
728 * `Object.prototype.toString`.
729 */
730 [Symbol.toStringTag] = 'LRUCache';
731 /**
732 * Find a value for which the supplied fn method returns a truthy value,
733 * similar to `Array.find()`. fn is called as `fn(value, key, cache)`.
734 */
735 find(fn, getOptions = {}) {
736 for (const i of this.#indexes()) {
737 const v = this.#valList[i];
738 const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
739 if (value === undefined)
740 continue;
741 if (fn(value, this.#keyList[i], this)) {
742 return this.get(this.#keyList[i], getOptions);
743 }
744 }
745 }
746 /**
747 * Call the supplied function on each item in the cache, in order from most
748 * recently used to least recently used.
749 *
750 * `fn` is called as `fn(value, key, cache)`.
751 *
752 * If `thisp` is provided, function will be called in the `this`-context of
753 * the provided object, or the cache if no `thisp` object is provided.
754 *
755 * Does not update age or recenty of use, or iterate over stale values.
756 */
757 forEach(fn, thisp = this) {
758 for (const i of this.#indexes()) {
759 const v = this.#valList[i];
760 const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
761 if (value === undefined)
762 continue;
763 fn.call(thisp, value, this.#keyList[i], this);
764 }
765 }
766 /**
767 * The same as {@link LRUCache.forEach} but items are iterated over in
768 * reverse order. (ie, less recently used items are iterated over first.)
769 */
770 rforEach(fn, thisp = this) {
771 for (const i of this.#rindexes()) {
772 const v = this.#valList[i];
773 const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
774 if (value === undefined)
775 continue;
776 fn.call(thisp, value, this.#keyList[i], this);
777 }
778 }
779 /**
780 * Delete any stale entries. Returns true if anything was removed,
781 * false otherwise.
782 */
783 purgeStale() {
784 let deleted = false;
785 for (const i of this.#rindexes({ allowStale: true })) {
786 if (this.#isStale(i)) {
787 this.#delete(this.#keyList[i], 'expire');
788 deleted = true;
789 }
790 }
791 return deleted;
792 }
793 /**
794 * Get the extended info about a given entry, to get its value, size, and
795 * TTL info simultaneously. Returns `undefined` if the key is not present.
796 *
797 * Unlike {@link LRUCache#dump}, which is designed to be portable and survive
798 * serialization, the `start` value is always the current timestamp, and the
799 * `ttl` is a calculated remaining time to live (negative if expired).
800 *
801 * Always returns stale values, if their info is found in the cache, so be
802 * sure to check for expirations (ie, a negative {@link LRUCache.Entry#ttl})
803 * if relevant.
804 */
805 info(key) {
806 const i = this.#keyMap.get(key);
807 if (i === undefined)
808 return undefined;
809 const v = this.#valList[i];
810 /* c8 ignore start - this isn't tested for the info function,
811 * but it's the same logic as found in other places. */
812 const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
813 if (value === undefined)
814 return undefined;
815 /* c8 ignore end */
816 const entry = { value };
817 if (this.#ttls && this.#starts) {
818 const ttl = this.#ttls[i];
819 const start = this.#starts[i];
820 if (ttl && start) {
821 const remain = ttl - (this.#perf.now() - start);
822 entry.ttl = remain;
823 entry.start = Date.now();
824 }
825 }
826 if (this.#sizes) {
827 entry.size = this.#sizes[i];
828 }
829 return entry;
830 }
831 /**
832 * Return an array of [key, {@link LRUCache.Entry}] tuples which can be
833 * passed to {@link LRUCache#load}.
834 *
835 * The `start` fields are calculated relative to a portable `Date.now()`
836 * timestamp, even if `performance.now()` is available.
837 *
838 * Stale entries are always included in the `dump`, even if
839 * {@link LRUCache.OptionsBase.allowStale} is false.
840 *
841 * Note: this returns an actual array, not a generator, so it can be more
842 * easily passed around.
843 */
844 dump() {
845 const arr = [];
846 for (const i of this.#indexes({ allowStale: true })) {
847 const key = this.#keyList[i];
848 const v = this.#valList[i];
849 const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
850 if (value === undefined || key === undefined)
851 continue;
852 const entry = { value };
853 if (this.#ttls && this.#starts) {
854 entry.ttl = this.#ttls[i];
855 // always dump the start relative to a portable timestamp
856 // it's ok for this to be a bit slow, it's a rare operation.
857 const age = this.#perf.now() - this.#starts[i];
858 entry.start = Math.floor(Date.now() - age);
859 }
860 if (this.#sizes) {
861 entry.size = this.#sizes[i];
862 }
863 arr.unshift([key, entry]);
864 }
865 return arr;
866 }
867 /**
868 * Reset the cache and load in the items in entries in the order listed.
869 *
870 * The shape of the resulting cache may be different if the same options are
871 * not used in both caches.
872 *
873 * The `start` fields are assumed to be calculated relative to a portable
874 * `Date.now()` timestamp, even if `performance.now()` is available.
875 */
876 load(arr) {
877 this.clear();
878 for (const [key, entry] of arr) {
879 if (entry.start) {
880 // entry.start is a portable timestamp, but we may be using
881 // node's performance.now(), so calculate the offset, so that
882 // we get the intended remaining TTL, no matter how long it's
883 // been on ice.
884 //
885 // it's ok for this to be a bit slow, it's a rare operation.
886 const age = Date.now() - entry.start;
887 entry.start = this.#perf.now() - age;
888 }
889 this.set(key, entry.value, entry);
890 }
891 }
892 /**
893 * Add a value to the cache.
894 *
895 * Note: if `undefined` is specified as a value, this is an alias for
896 * {@link LRUCache#delete}
897 *
898 * Fields on the {@link LRUCache.SetOptions} options param will override
899 * their corresponding values in the constructor options for the scope
900 * of this single `set()` operation.
901 *
902 * If `start` is provided, then that will set the effective start
903 * time for the TTL calculation. Note that this must be a previous
904 * value of `performance.now()` if supported, or a previous value of
905 * `Date.now()` if not.
906 *
907 * Options object may also include `size`, which will prevent
908 * calling the `sizeCalculation` function and just use the specified
909 * number if it is a positive integer, and `noDisposeOnSet` which
910 * will prevent calling a `dispose` function in the case of
911 * overwrites.
912 *
913 * If the `size` (or return value of `sizeCalculation`) for a given
914 * entry is greater than `maxEntrySize`, then the item will not be
915 * added to the cache.
916 *
917 * Will update the recency of the entry.
918 *
919 * If the value is `undefined`, then this is an alias for
920 * `cache.delete(key)`. `undefined` is never stored in the cache.
921 */
922 set(k, v, setOptions = {}) {
923 if (v === undefined) {
924 this.delete(k);
925 return this;
926 }
927 const { ttl = this.ttl, start, noDisposeOnSet = this.noDisposeOnSet, sizeCalculation = this.sizeCalculation, status, } = setOptions;
928 let { noUpdateTTL = this.noUpdateTTL } = setOptions;
929 const size = this.#requireSize(k, v, setOptions.size || 0, sizeCalculation);
930 // if the item doesn't fit, don't do anything
931 // NB: maxEntrySize set to maxSize by default
932 if (this.maxEntrySize && size > this.maxEntrySize) {
933 if (status) {
934 status.set = 'miss';
935 status.maxEntrySizeExceeded = true;
936 }
937 // have to delete, in case something is there already.
938 this.#delete(k, 'set');
939 return this;
940 }
941 let index = this.#size === 0 ? undefined : this.#keyMap.get(k);
942 if (index === undefined) {
943 // addition
944 index = (this.#size === 0 ? this.#tail
945 : this.#free.length !== 0 ? this.#free.pop()
946 : this.#size === this.#max ? this.#evict(false)
947 : this.#size);
948 this.#keyList[index] = k;
949 this.#valList[index] = v;
950 this.#keyMap.set(k, index);
951 this.#next[this.#tail] = index;
952 this.#prev[index] = this.#tail;
953 this.#tail = index;
954 this.#size++;
955 this.#addItemSize(index, size, status);
956 if (status)
957 status.set = 'add';
958 noUpdateTTL = false;
959 if (this.#hasOnInsert) {
960 this.#onInsert?.(v, k, 'add');
961 }
962 }
963 else {
964 // update
965 this.#moveToTail(index);
966 const oldVal = this.#valList[index];
967 if (v !== oldVal) {
968 if (this.#hasFetchMethod && this.#isBackgroundFetch(oldVal)) {
969 oldVal.__abortController.abort(new Error('replaced'));
970 const { __staleWhileFetching: s } = oldVal;
971 if (s !== undefined && !noDisposeOnSet) {
972 if (this.#hasDispose) {
973 this.#dispose?.(s, k, 'set');
974 }
975 if (this.#hasDisposeAfter) {
976 this.#disposed?.push([s, k, 'set']);
977 }
978 }
979 }
980 else if (!noDisposeOnSet) {
981 if (this.#hasDispose) {
982 this.#dispose?.(oldVal, k, 'set');
983 }
984 if (this.#hasDisposeAfter) {
985 this.#disposed?.push([oldVal, k, 'set']);
986 }
987 }
988 this.#removeItemSize(index);
989 this.#addItemSize(index, size, status);
990 this.#valList[index] = v;
991 if (status) {
992 status.set = 'replace';
993 const oldValue = oldVal && this.#isBackgroundFetch(oldVal) ?
994 oldVal.__staleWhileFetching
995 : oldVal;
996 if (oldValue !== undefined)
997 status.oldValue = oldValue;
998 }
999 }
1000 else if (status) {
1001 status.set = 'update';
1002 }
1003 if (this.#hasOnInsert) {
1004 this.onInsert?.(v, k, v === oldVal ? 'update' : 'replace');
1005 }
1006 }
1007 if (ttl !== 0 && !this.#ttls) {
1008 this.#initializeTTLTracking();
1009 }
1010 if (this.#ttls) {
1011 if (!noUpdateTTL) {
1012 this.#setItemTTL(index, ttl, start);
1013 }
1014 if (status)
1015 this.#statusTTL(status, index);
1016 }
1017 if (!noDisposeOnSet && this.#hasDisposeAfter && this.#disposed) {
1018 const dt = this.#disposed;
1019 let task;
1020 while ((task = dt?.shift())) {
1021 this.#disposeAfter?.(...task);
1022 }
1023 }
1024 return this;
1025 }
1026 /**
1027 * Evict the least recently used item, returning its value or
1028 * `undefined` if cache is empty.
1029 */
1030 pop() {
1031 try {
1032 while (this.#size) {
1033 const val = this.#valList[this.#head];
1034 this.#evict(true);
1035 if (this.#isBackgroundFetch(val)) {
1036 if (val.__staleWhileFetching) {
1037 return val.__staleWhileFetching;
1038 }
1039 }
1040 else if (val !== undefined) {
1041 return val;
1042 }
1043 }
1044 }
1045 finally {
1046 if (this.#hasDisposeAfter && this.#disposed) {
1047 const dt = this.#disposed;
1048 let task;
1049 while ((task = dt?.shift())) {
1050 this.#disposeAfter?.(...task);
1051 }
1052 }
1053 }
1054 }
1055 #evict(free) {
1056 const head = this.#head;
1057 const k = this.#keyList[head];
1058 const v = this.#valList[head];
1059 if (this.#hasFetchMethod && this.#isBackgroundFetch(v)) {
1060 v.__abortController.abort(new Error('evicted'));
1061 }
1062 else if (this.#hasDispose || this.#hasDisposeAfter) {
1063 if (this.#hasDispose) {
1064 this.#dispose?.(v, k, 'evict');
1065 }
1066 if (this.#hasDisposeAfter) {
1067 this.#disposed?.push([v, k, 'evict']);
1068 }
1069 }
1070 this.#removeItemSize(head);
1071 if (this.#autopurgeTimers?.[head]) {
1072 clearTimeout(this.#autopurgeTimers[head]);
1073 this.#autopurgeTimers[head] = undefined;
1074 }
1075 // if we aren't about to use the index, then null these out
1076 if (free) {
1077 this.#keyList[head] = undefined;
1078 this.#valList[head] = undefined;
1079 this.#free.push(head);
1080 }
1081 if (this.#size === 1) {
1082 this.#head = this.#tail = 0;
1083 this.#free.length = 0;
1084 }
1085 else {
1086 this.#head = this.#next[head];
1087 }
1088 this.#keyMap.delete(k);
1089 this.#size--;
1090 return head;
1091 }
1092 /**
1093 * Check if a key is in the cache, without updating the recency of use.
1094 * Will return false if the item is stale, even though it is technically
1095 * in the cache.
1096 *
1097 * Check if a key is in the cache, without updating the recency of
1098 * use. Age is updated if {@link LRUCache.OptionsBase.updateAgeOnHas} is set
1099 * to `true` in either the options or the constructor.
1100 *
1101 * Will return `false` if the item is stale, even though it is technically in
1102 * the cache. The difference can be determined (if it matters) by using a
1103 * `status` argument, and inspecting the `has` field.
1104 *
1105 * Will not update item age unless
1106 * {@link LRUCache.OptionsBase.updateAgeOnHas} is set.
1107 */
1108 has(k, hasOptions = {}) {
1109 const { updateAgeOnHas = this.updateAgeOnHas, status } = hasOptions;
1110 const index = this.#keyMap.get(k);
1111 if (index !== undefined) {
1112 const v = this.#valList[index];
1113 if (this.#isBackgroundFetch(v) &&
1114 v.__staleWhileFetching === undefined) {
1115 return false;
1116 }
1117 if (!this.#isStale(index)) {
1118 if (updateAgeOnHas) {
1119 this.#updateItemAge(index);
1120 }
1121 if (status) {
1122 status.has = 'hit';
1123 this.#statusTTL(status, index);
1124 }
1125 return true;
1126 }
1127 else if (status) {
1128 status.has = 'stale';
1129 this.#statusTTL(status, index);
1130 }
1131 }
1132 else if (status) {
1133 status.has = 'miss';
1134 }
1135 return false;
1136 }
1137 /**
1138 * Like {@link LRUCache#get} but doesn't update recency or delete stale
1139 * items.
1140 *
1141 * Returns `undefined` if the item is stale, unless
1142 * {@link LRUCache.OptionsBase.allowStale} is set.
1143 */
1144 peek(k, peekOptions = {}) {
1145 const { allowStale = this.allowStale } = peekOptions;
1146 const index = this.#keyMap.get(k);
1147 if (index === undefined || (!allowStale && this.#isStale(index))) {
1148 return;
1149 }
1150 const v = this.#valList[index];
1151 // either stale and allowed, or forcing a refresh of non-stale value
1152 return this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
1153 }
1154 #backgroundFetch(k, index, options, context) {
1155 const v = index === undefined ? undefined : this.#valList[index];
1156 if (this.#isBackgroundFetch(v)) {
1157 return v;
1158 }
1159 const ac = new AC();
1160 const { signal } = options;
1161 // when/if our AC signals, then stop listening to theirs.
1162 signal?.addEventListener('abort', () => ac.abort(signal.reason), {
1163 signal: ac.signal,
1164 });
1165 const fetchOpts = {
1166 signal: ac.signal,
1167 options,
1168 context,
1169 };
1170 const cb = (v, updateCache = false) => {
1171 const { aborted } = ac.signal;
1172 const ignoreAbort = options.ignoreFetchAbort && v !== undefined;
1173 const proceed = options.ignoreFetchAbort ||
1174 !!(options.allowStaleOnFetchAbort && v !== undefined);
1175 if (options.status) {
1176 if (aborted && !updateCache) {
1177 options.status.fetchAborted = true;
1178 options.status.fetchError = ac.signal.reason;
1179 if (ignoreAbort)
1180 options.status.fetchAbortIgnored = true;
1181 }
1182 else {
1183 options.status.fetchResolved = true;
1184 }
1185 }
1186 if (aborted && !ignoreAbort && !updateCache) {
1187 return fetchFail(ac.signal.reason, proceed);
1188 }
1189 // either we didn't abort, and are still here, or we did, and ignored
1190 const bf = p;
1191 // if nothing else has been written there but we're set to update the
1192 // cache and ignore the abort, or if it's still pending on this specific
1193 // background request, then write it to the cache.
1194 const vl = this.#valList[index];
1195 if (vl === p || (ignoreAbort && updateCache && vl === undefined)) {
1196 if (v === undefined) {
1197 if (bf.__staleWhileFetching !== undefined) {
1198 this.#valList[index] = bf.__staleWhileFetching;
1199 }
1200 else {