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