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