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