Brunobkr/llama.cpp_AlgMor24_github

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

Showing the first 1,200 of 1726 lines. Download the file for the rest.