index.js 56 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585
  1. /**
  2. * @module LRUCache
  3. */
  4. const defaultPerf = (typeof performance === 'object' &&
  5. performance &&
  6. typeof performance.now === 'function') ?
  7. performance
  8. : Date;
  9. const warned = new Set();
  10. /* c8 ignore start */
  11. const PROCESS = (typeof process === 'object' && !!process ?
  12. process
  13. : {});
  14. /* c8 ignore start */
  15. const emitWarning = (msg, type, code, fn) => {
  16. typeof PROCESS.emitWarning === 'function' ?
  17. PROCESS.emitWarning(msg, type, code, fn)
  18. : console.error(`[${code}] ${type}: ${msg}`);
  19. };
  20. let AC = globalThis.AbortController;
  21. let AS = globalThis.AbortSignal;
  22. /* c8 ignore start */
  23. if (typeof AC === 'undefined') {
  24. //@ts-ignore
  25. AS = class AbortSignal {
  26. onabort;
  27. _onabort = [];
  28. reason;
  29. aborted = false;
  30. addEventListener(_, fn) {
  31. this._onabort.push(fn);
  32. }
  33. };
  34. //@ts-ignore
  35. AC = class AbortController {
  36. constructor() {
  37. warnACPolyfill();
  38. }
  39. signal = new AS();
  40. abort(reason) {
  41. if (this.signal.aborted)
  42. return;
  43. //@ts-ignore
  44. this.signal.reason = reason;
  45. //@ts-ignore
  46. this.signal.aborted = true;
  47. //@ts-ignore
  48. for (const fn of this.signal._onabort) {
  49. fn(reason);
  50. }
  51. this.signal.onabort?.(reason);
  52. }
  53. };
  54. let printACPolyfillWarning = PROCESS.env?.LRU_CACHE_IGNORE_AC_WARNING !== '1';
  55. const warnACPolyfill = () => {
  56. if (!printACPolyfillWarning)
  57. return;
  58. printACPolyfillWarning = false;
  59. emitWarning('AbortController is not defined. If using lru-cache in ' +
  60. 'node 14, load an AbortController polyfill from the ' +
  61. '`node-abort-controller` package. A minimal polyfill is ' +
  62. 'provided for use by LRUCache.fetch(), but it should not be ' +
  63. 'relied upon in other contexts (eg, passing it to other APIs that ' +
  64. 'use AbortController/AbortSignal might have undesirable effects). ' +
  65. 'You may disable this with LRU_CACHE_IGNORE_AC_WARNING=1 in the env.', 'NO_ABORT_CONTROLLER', 'ENOTSUP', warnACPolyfill);
  66. };
  67. }
  68. /* c8 ignore stop */
  69. const shouldWarn = (code) => !warned.has(code);
  70. const TYPE = Symbol('type');
  71. const isPosInt = (n) => n && n === Math.floor(n) && n > 0 && isFinite(n);
  72. /* c8 ignore start */
  73. // This is a little bit ridiculous, tbh.
  74. // The maximum array length is 2^32-1 or thereabouts on most JS impls.
  75. // And well before that point, you're caching the entire world, I mean,
  76. // that's ~32GB of just integers for the next/prev links, plus whatever
  77. // else to hold that many keys and values. Just filling the memory with
  78. // zeroes at init time is brutal when you get that big.
  79. // But why not be complete?
  80. // Maybe in the future, these limits will have expanded.
  81. const getUintArray = (max) => !isPosInt(max) ? null
  82. : max <= Math.pow(2, 8) ? Uint8Array
  83. : max <= Math.pow(2, 16) ? Uint16Array
  84. : max <= Math.pow(2, 32) ? Uint32Array
  85. : max <= Number.MAX_SAFE_INTEGER ? ZeroArray
  86. : null;
  87. /* c8 ignore stop */
  88. class ZeroArray extends Array {
  89. constructor(size) {
  90. super(size);
  91. this.fill(0);
  92. }
  93. }
  94. class Stack {
  95. heap;
  96. length;
  97. // private constructor
  98. static #constructing = false;
  99. static create(max) {
  100. const HeapCls = getUintArray(max);
  101. if (!HeapCls)
  102. return [];
  103. Stack.#constructing = true;
  104. const s = new Stack(max, HeapCls);
  105. Stack.#constructing = false;
  106. return s;
  107. }
  108. constructor(max, HeapCls) {
  109. /* c8 ignore start */
  110. if (!Stack.#constructing) {
  111. throw new TypeError('instantiate Stack using Stack.create(n)');
  112. }
  113. /* c8 ignore stop */
  114. this.heap = new HeapCls(max);
  115. this.length = 0;
  116. }
  117. push(n) {
  118. this.heap[this.length++] = n;
  119. }
  120. pop() {
  121. return this.heap[--this.length];
  122. }
  123. }
  124. /**
  125. * Default export, the thing you're using this module to get.
  126. *
  127. * The `K` and `V` types define the key and value types, respectively. The
  128. * optional `FC` type defines the type of the `context` object passed to
  129. * `cache.fetch()` and `cache.memo()`.
  130. *
  131. * Keys and values **must not** be `null` or `undefined`.
  132. *
  133. * All properties from the options object (with the exception of `max`,
  134. * `maxSize`, `fetchMethod`, `memoMethod`, `dispose` and `disposeAfter`) are
  135. * added as normal public members. (The listed options are read-only getters.)
  136. *
  137. * Changing any of these will alter the defaults for subsequent method calls.
  138. */
  139. export class LRUCache {
  140. // options that cannot be changed without disaster
  141. #max;
  142. #maxSize;
  143. #dispose;
  144. #onInsert;
  145. #disposeAfter;
  146. #fetchMethod;
  147. #memoMethod;
  148. #perf;
  149. /**
  150. * {@link LRUCache.OptionsBase.perf}
  151. */
  152. get perf() {
  153. return this.#perf;
  154. }
  155. /**
  156. * {@link LRUCache.OptionsBase.ttl}
  157. */
  158. ttl;
  159. /**
  160. * {@link LRUCache.OptionsBase.ttlResolution}
  161. */
  162. ttlResolution;
  163. /**
  164. * {@link LRUCache.OptionsBase.ttlAutopurge}
  165. */
  166. ttlAutopurge;
  167. /**
  168. * {@link LRUCache.OptionsBase.updateAgeOnGet}
  169. */
  170. updateAgeOnGet;
  171. /**
  172. * {@link LRUCache.OptionsBase.updateAgeOnHas}
  173. */
  174. updateAgeOnHas;
  175. /**
  176. * {@link LRUCache.OptionsBase.allowStale}
  177. */
  178. allowStale;
  179. /**
  180. * {@link LRUCache.OptionsBase.noDisposeOnSet}
  181. */
  182. noDisposeOnSet;
  183. /**
  184. * {@link LRUCache.OptionsBase.noUpdateTTL}
  185. */
  186. noUpdateTTL;
  187. /**
  188. * {@link LRUCache.OptionsBase.maxEntrySize}
  189. */
  190. maxEntrySize;
  191. /**
  192. * {@link LRUCache.OptionsBase.sizeCalculation}
  193. */
  194. sizeCalculation;
  195. /**
  196. * {@link LRUCache.OptionsBase.noDeleteOnFetchRejection}
  197. */
  198. noDeleteOnFetchRejection;
  199. /**
  200. * {@link LRUCache.OptionsBase.noDeleteOnStaleGet}
  201. */
  202. noDeleteOnStaleGet;
  203. /**
  204. * {@link LRUCache.OptionsBase.allowStaleOnFetchAbort}
  205. */
  206. allowStaleOnFetchAbort;
  207. /**
  208. * {@link LRUCache.OptionsBase.allowStaleOnFetchRejection}
  209. */
  210. allowStaleOnFetchRejection;
  211. /**
  212. * {@link LRUCache.OptionsBase.ignoreFetchAbort}
  213. */
  214. ignoreFetchAbort;
  215. // computed properties
  216. #size;
  217. #calculatedSize;
  218. #keyMap;
  219. #keyList;
  220. #valList;
  221. #next;
  222. #prev;
  223. #head;
  224. #tail;
  225. #free;
  226. #disposed;
  227. #sizes;
  228. #starts;
  229. #ttls;
  230. #autopurgeTimers;
  231. #hasDispose;
  232. #hasFetchMethod;
  233. #hasDisposeAfter;
  234. #hasOnInsert;
  235. /**
  236. * Do not call this method unless you need to inspect the
  237. * inner workings of the cache. If anything returned by this
  238. * object is modified in any way, strange breakage may occur.
  239. *
  240. * These fields are private for a reason!
  241. *
  242. * @internal
  243. */
  244. static unsafeExposeInternals(c) {
  245. return {
  246. // properties
  247. starts: c.#starts,
  248. ttls: c.#ttls,
  249. autopurgeTimers: c.#autopurgeTimers,
  250. sizes: c.#sizes,
  251. keyMap: c.#keyMap,
  252. keyList: c.#keyList,
  253. valList: c.#valList,
  254. next: c.#next,
  255. prev: c.#prev,
  256. get head() {
  257. return c.#head;
  258. },
  259. get tail() {
  260. return c.#tail;
  261. },
  262. free: c.#free,
  263. // methods
  264. isBackgroundFetch: (p) => c.#isBackgroundFetch(p),
  265. backgroundFetch: (k, index, options, context) => c.#backgroundFetch(k, index, options, context),
  266. moveToTail: (index) => c.#moveToTail(index),
  267. indexes: (options) => c.#indexes(options),
  268. rindexes: (options) => c.#rindexes(options),
  269. isStale: (index) => c.#isStale(index),
  270. };
  271. }
  272. // Protected read-only members
  273. /**
  274. * {@link LRUCache.OptionsBase.max} (read-only)
  275. */
  276. get max() {
  277. return this.#max;
  278. }
  279. /**
  280. * {@link LRUCache.OptionsBase.maxSize} (read-only)
  281. */
  282. get maxSize() {
  283. return this.#maxSize;
  284. }
  285. /**
  286. * The total computed size of items in the cache (read-only)
  287. */
  288. get calculatedSize() {
  289. return this.#calculatedSize;
  290. }
  291. /**
  292. * The number of items stored in the cache (read-only)
  293. */
  294. get size() {
  295. return this.#size;
  296. }
  297. /**
  298. * {@link LRUCache.OptionsBase.fetchMethod} (read-only)
  299. */
  300. get fetchMethod() {
  301. return this.#fetchMethod;
  302. }
  303. get memoMethod() {
  304. return this.#memoMethod;
  305. }
  306. /**
  307. * {@link LRUCache.OptionsBase.dispose} (read-only)
  308. */
  309. get dispose() {
  310. return this.#dispose;
  311. }
  312. /**
  313. * {@link LRUCache.OptionsBase.onInsert} (read-only)
  314. */
  315. get onInsert() {
  316. return this.#onInsert;
  317. }
  318. /**
  319. * {@link LRUCache.OptionsBase.disposeAfter} (read-only)
  320. */
  321. get disposeAfter() {
  322. return this.#disposeAfter;
  323. }
  324. constructor(options) {
  325. const { max = 0, ttl, ttlResolution = 1, ttlAutopurge, updateAgeOnGet, updateAgeOnHas, allowStale, dispose, onInsert, disposeAfter, noDisposeOnSet, noUpdateTTL, maxSize = 0, maxEntrySize = 0, sizeCalculation, fetchMethod, memoMethod, noDeleteOnFetchRejection, noDeleteOnStaleGet, allowStaleOnFetchRejection, allowStaleOnFetchAbort, ignoreFetchAbort, perf, } = options;
  326. if (perf !== undefined) {
  327. if (typeof perf?.now !== 'function') {
  328. throw new TypeError('perf option must have a now() method if specified');
  329. }
  330. }
  331. this.#perf = perf ?? defaultPerf;
  332. if (max !== 0 && !isPosInt(max)) {
  333. throw new TypeError('max option must be a nonnegative integer');
  334. }
  335. const UintArray = max ? getUintArray(max) : Array;
  336. if (!UintArray) {
  337. throw new Error('invalid max value: ' + max);
  338. }
  339. this.#max = max;
  340. this.#maxSize = maxSize;
  341. this.maxEntrySize = maxEntrySize || this.#maxSize;
  342. this.sizeCalculation = sizeCalculation;
  343. if (this.sizeCalculation) {
  344. if (!this.#maxSize && !this.maxEntrySize) {
  345. throw new TypeError('cannot set sizeCalculation without setting maxSize or maxEntrySize');
  346. }
  347. if (typeof this.sizeCalculation !== 'function') {
  348. throw new TypeError('sizeCalculation set to non-function');
  349. }
  350. }
  351. if (memoMethod !== undefined && typeof memoMethod !== 'function') {
  352. throw new TypeError('memoMethod must be a function if defined');
  353. }
  354. this.#memoMethod = memoMethod;
  355. if (fetchMethod !== undefined && typeof fetchMethod !== 'function') {
  356. throw new TypeError('fetchMethod must be a function if specified');
  357. }
  358. this.#fetchMethod = fetchMethod;
  359. this.#hasFetchMethod = !!fetchMethod;
  360. this.#keyMap = new Map();
  361. this.#keyList = new Array(max).fill(undefined);
  362. this.#valList = new Array(max).fill(undefined);
  363. this.#next = new UintArray(max);
  364. this.#prev = new UintArray(max);
  365. this.#head = 0;
  366. this.#tail = 0;
  367. this.#free = Stack.create(max);
  368. this.#size = 0;
  369. this.#calculatedSize = 0;
  370. if (typeof dispose === 'function') {
  371. this.#dispose = dispose;
  372. }
  373. if (typeof onInsert === 'function') {
  374. this.#onInsert = onInsert;
  375. }
  376. if (typeof disposeAfter === 'function') {
  377. this.#disposeAfter = disposeAfter;
  378. this.#disposed = [];
  379. }
  380. else {
  381. this.#disposeAfter = undefined;
  382. this.#disposed = undefined;
  383. }
  384. this.#hasDispose = !!this.#dispose;
  385. this.#hasOnInsert = !!this.#onInsert;
  386. this.#hasDisposeAfter = !!this.#disposeAfter;
  387. this.noDisposeOnSet = !!noDisposeOnSet;
  388. this.noUpdateTTL = !!noUpdateTTL;
  389. this.noDeleteOnFetchRejection = !!noDeleteOnFetchRejection;
  390. this.allowStaleOnFetchRejection = !!allowStaleOnFetchRejection;
  391. this.allowStaleOnFetchAbort = !!allowStaleOnFetchAbort;
  392. this.ignoreFetchAbort = !!ignoreFetchAbort;
  393. // NB: maxEntrySize is set to maxSize if it's set
  394. if (this.maxEntrySize !== 0) {
  395. if (this.#maxSize !== 0) {
  396. if (!isPosInt(this.#maxSize)) {
  397. throw new TypeError('maxSize must be a positive integer if specified');
  398. }
  399. }
  400. if (!isPosInt(this.maxEntrySize)) {
  401. throw new TypeError('maxEntrySize must be a positive integer if specified');
  402. }
  403. this.#initializeSizeTracking();
  404. }
  405. this.allowStale = !!allowStale;
  406. this.noDeleteOnStaleGet = !!noDeleteOnStaleGet;
  407. this.updateAgeOnGet = !!updateAgeOnGet;
  408. this.updateAgeOnHas = !!updateAgeOnHas;
  409. this.ttlResolution =
  410. isPosInt(ttlResolution) || ttlResolution === 0 ? ttlResolution : 1;
  411. this.ttlAutopurge = !!ttlAutopurge;
  412. this.ttl = ttl || 0;
  413. if (this.ttl) {
  414. if (!isPosInt(this.ttl)) {
  415. throw new TypeError('ttl must be a positive integer if specified');
  416. }
  417. this.#initializeTTLTracking();
  418. }
  419. // do not allow completely unbounded caches
  420. if (this.#max === 0 && this.ttl === 0 && this.#maxSize === 0) {
  421. throw new TypeError('At least one of max, maxSize, or ttl is required');
  422. }
  423. if (!this.ttlAutopurge && !this.#max && !this.#maxSize) {
  424. const code = 'LRU_CACHE_UNBOUNDED';
  425. if (shouldWarn(code)) {
  426. warned.add(code);
  427. const msg = 'TTL caching without ttlAutopurge, max, or maxSize can ' +
  428. 'result in unbounded memory consumption.';
  429. emitWarning(msg, 'UnboundedCacheWarning', code, LRUCache);
  430. }
  431. }
  432. }
  433. /**
  434. * Return the number of ms left in the item's TTL. If item is not in cache,
  435. * returns `0`. Returns `Infinity` if item is in cache without a defined TTL.
  436. */
  437. getRemainingTTL(key) {
  438. return this.#keyMap.has(key) ? Infinity : 0;
  439. }
  440. #initializeTTLTracking() {
  441. const ttls = new ZeroArray(this.#max);
  442. const starts = new ZeroArray(this.#max);
  443. this.#ttls = ttls;
  444. this.#starts = starts;
  445. const purgeTimers = this.ttlAutopurge ?
  446. new Array(this.#max)
  447. : undefined;
  448. this.#autopurgeTimers = purgeTimers;
  449. this.#setItemTTL = (index, ttl, start = this.#perf.now()) => {
  450. starts[index] = ttl !== 0 ? start : 0;
  451. ttls[index] = ttl;
  452. // clear out the purge timer if we're setting TTL to 0, and
  453. // previously had a ttl purge timer running, so it doesn't
  454. // fire unnecessarily.
  455. if (purgeTimers?.[index]) {
  456. clearTimeout(purgeTimers[index]);
  457. purgeTimers[index] = undefined;
  458. }
  459. if (ttl !== 0 && purgeTimers) {
  460. const t = setTimeout(() => {
  461. if (this.#isStale(index)) {
  462. this.#delete(this.#keyList[index], 'expire');
  463. }
  464. }, ttl + 1);
  465. // unref() not supported on all platforms
  466. /* c8 ignore start */
  467. if (t.unref) {
  468. t.unref();
  469. }
  470. /* c8 ignore stop */
  471. purgeTimers[index] = t;
  472. }
  473. };
  474. this.#updateItemAge = index => {
  475. starts[index] = ttls[index] !== 0 ? this.#perf.now() : 0;
  476. };
  477. this.#statusTTL = (status, index) => {
  478. if (ttls[index]) {
  479. const ttl = ttls[index];
  480. const start = starts[index];
  481. /* c8 ignore next */
  482. if (!ttl || !start)
  483. return;
  484. status.ttl = ttl;
  485. status.start = start;
  486. status.now = cachedNow || getNow();
  487. const age = status.now - start;
  488. status.remainingTTL = ttl - age;
  489. }
  490. };
  491. // debounce calls to perf.now() to 1s so we're not hitting
  492. // that costly call repeatedly.
  493. let cachedNow = 0;
  494. const getNow = () => {
  495. const n = this.#perf.now();
  496. if (this.ttlResolution > 0) {
  497. cachedNow = n;
  498. const t = setTimeout(() => (cachedNow = 0), this.ttlResolution);
  499. // not available on all platforms
  500. /* c8 ignore start */
  501. if (t.unref) {
  502. t.unref();
  503. }
  504. /* c8 ignore stop */
  505. }
  506. return n;
  507. };
  508. this.getRemainingTTL = key => {
  509. const index = this.#keyMap.get(key);
  510. if (index === undefined) {
  511. return 0;
  512. }
  513. const ttl = ttls[index];
  514. const start = starts[index];
  515. if (!ttl || !start) {
  516. return Infinity;
  517. }
  518. const age = (cachedNow || getNow()) - start;
  519. return ttl - age;
  520. };
  521. this.#isStale = index => {
  522. const s = starts[index];
  523. const t = ttls[index];
  524. return !!t && !!s && (cachedNow || getNow()) - s > t;
  525. };
  526. }
  527. // conditionally set private methods related to TTL
  528. #updateItemAge = () => { };
  529. #statusTTL = () => { };
  530. #setItemTTL = () => { };
  531. /* c8 ignore stop */
  532. #isStale = () => false;
  533. #initializeSizeTracking() {
  534. const sizes = new ZeroArray(this.#max);
  535. this.#calculatedSize = 0;
  536. this.#sizes = sizes;
  537. this.#removeItemSize = index => {
  538. this.#calculatedSize -= sizes[index];
  539. sizes[index] = 0;
  540. };
  541. this.#requireSize = (k, v, size, sizeCalculation) => {
  542. // provisionally accept background fetches.
  543. // actual value size will be checked when they return.
  544. if (this.#isBackgroundFetch(v)) {
  545. return 0;
  546. }
  547. if (!isPosInt(size)) {
  548. if (sizeCalculation) {
  549. if (typeof sizeCalculation !== 'function') {
  550. throw new TypeError('sizeCalculation must be a function');
  551. }
  552. size = sizeCalculation(v, k);
  553. if (!isPosInt(size)) {
  554. throw new TypeError('sizeCalculation return invalid (expect positive integer)');
  555. }
  556. }
  557. else {
  558. throw new TypeError('invalid size value (must be positive integer). ' +
  559. 'When maxSize or maxEntrySize is used, sizeCalculation ' +
  560. 'or size must be set.');
  561. }
  562. }
  563. return size;
  564. };
  565. this.#addItemSize = (index, size, status) => {
  566. sizes[index] = size;
  567. if (this.#maxSize) {
  568. const maxSize = this.#maxSize - sizes[index];
  569. while (this.#calculatedSize > maxSize) {
  570. this.#evict(true);
  571. }
  572. }
  573. this.#calculatedSize += sizes[index];
  574. if (status) {
  575. status.entrySize = size;
  576. status.totalCalculatedSize = this.#calculatedSize;
  577. }
  578. };
  579. }
  580. #removeItemSize = _i => { };
  581. #addItemSize = (_i, _s, _st) => { };
  582. #requireSize = (_k, _v, size, sizeCalculation) => {
  583. if (size || sizeCalculation) {
  584. throw new TypeError('cannot set size without setting maxSize or maxEntrySize on cache');
  585. }
  586. return 0;
  587. };
  588. *#indexes({ allowStale = this.allowStale } = {}) {
  589. if (this.#size) {
  590. for (let i = this.#tail; true;) {
  591. if (!this.#isValidIndex(i)) {
  592. break;
  593. }
  594. if (allowStale || !this.#isStale(i)) {
  595. yield i;
  596. }
  597. if (i === this.#head) {
  598. break;
  599. }
  600. else {
  601. i = this.#prev[i];
  602. }
  603. }
  604. }
  605. }
  606. *#rindexes({ allowStale = this.allowStale } = {}) {
  607. if (this.#size) {
  608. for (let i = this.#head; true;) {
  609. if (!this.#isValidIndex(i)) {
  610. break;
  611. }
  612. if (allowStale || !this.#isStale(i)) {
  613. yield i;
  614. }
  615. if (i === this.#tail) {
  616. break;
  617. }
  618. else {
  619. i = this.#next[i];
  620. }
  621. }
  622. }
  623. }
  624. #isValidIndex(index) {
  625. return (index !== undefined &&
  626. this.#keyMap.get(this.#keyList[index]) === index);
  627. }
  628. /**
  629. * Return a generator yielding `[key, value]` pairs,
  630. * in order from most recently used to least recently used.
  631. */
  632. *entries() {
  633. for (const i of this.#indexes()) {
  634. if (this.#valList[i] !== undefined &&
  635. this.#keyList[i] !== undefined &&
  636. !this.#isBackgroundFetch(this.#valList[i])) {
  637. yield [this.#keyList[i], this.#valList[i]];
  638. }
  639. }
  640. }
  641. /**
  642. * Inverse order version of {@link LRUCache.entries}
  643. *
  644. * Return a generator yielding `[key, value]` pairs,
  645. * in order from least recently used to most recently used.
  646. */
  647. *rentries() {
  648. for (const i of this.#rindexes()) {
  649. if (this.#valList[i] !== undefined &&
  650. this.#keyList[i] !== undefined &&
  651. !this.#isBackgroundFetch(this.#valList[i])) {
  652. yield [this.#keyList[i], this.#valList[i]];
  653. }
  654. }
  655. }
  656. /**
  657. * Return a generator yielding the keys in the cache,
  658. * in order from most recently used to least recently used.
  659. */
  660. *keys() {
  661. for (const i of this.#indexes()) {
  662. const k = this.#keyList[i];
  663. if (k !== undefined && !this.#isBackgroundFetch(this.#valList[i])) {
  664. yield k;
  665. }
  666. }
  667. }
  668. /**
  669. * Inverse order version of {@link LRUCache.keys}
  670. *
  671. * Return a generator yielding the keys in the cache,
  672. * in order from least recently used to most recently used.
  673. */
  674. *rkeys() {
  675. for (const i of this.#rindexes()) {
  676. const k = this.#keyList[i];
  677. if (k !== undefined && !this.#isBackgroundFetch(this.#valList[i])) {
  678. yield k;
  679. }
  680. }
  681. }
  682. /**
  683. * Return a generator yielding the values in the cache,
  684. * in order from most recently used to least recently used.
  685. */
  686. *values() {
  687. for (const i of this.#indexes()) {
  688. const v = this.#valList[i];
  689. if (v !== undefined && !this.#isBackgroundFetch(this.#valList[i])) {
  690. yield this.#valList[i];
  691. }
  692. }
  693. }
  694. /**
  695. * Inverse order version of {@link LRUCache.values}
  696. *
  697. * Return a generator yielding the values in the cache,
  698. * in order from least recently used to most recently used.
  699. */
  700. *rvalues() {
  701. for (const i of this.#rindexes()) {
  702. const v = this.#valList[i];
  703. if (v !== undefined && !this.#isBackgroundFetch(this.#valList[i])) {
  704. yield this.#valList[i];
  705. }
  706. }
  707. }
  708. /**
  709. * Iterating over the cache itself yields the same results as
  710. * {@link LRUCache.entries}
  711. */
  712. [Symbol.iterator]() {
  713. return this.entries();
  714. }
  715. /**
  716. * A String value that is used in the creation of the default string
  717. * description of an object. Called by the built-in method
  718. * `Object.prototype.toString`.
  719. */
  720. [Symbol.toStringTag] = 'LRUCache';
  721. /**
  722. * Find a value for which the supplied fn method returns a truthy value,
  723. * similar to `Array.find()`. fn is called as `fn(value, key, cache)`.
  724. */
  725. find(fn, getOptions = {}) {
  726. for (const i of this.#indexes()) {
  727. const v = this.#valList[i];
  728. const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
  729. if (value === undefined)
  730. continue;
  731. if (fn(value, this.#keyList[i], this)) {
  732. return this.get(this.#keyList[i], getOptions);
  733. }
  734. }
  735. }
  736. /**
  737. * Call the supplied function on each item in the cache, in order from most
  738. * recently used to least recently used.
  739. *
  740. * `fn` is called as `fn(value, key, cache)`.
  741. *
  742. * If `thisp` is provided, function will be called in the `this`-context of
  743. * the provided object, or the cache if no `thisp` object is provided.
  744. *
  745. * Does not update age or recenty of use, or iterate over stale values.
  746. */
  747. forEach(fn, thisp = this) {
  748. for (const i of this.#indexes()) {
  749. const v = this.#valList[i];
  750. const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
  751. if (value === undefined)
  752. continue;
  753. fn.call(thisp, value, this.#keyList[i], this);
  754. }
  755. }
  756. /**
  757. * The same as {@link LRUCache.forEach} but items are iterated over in
  758. * reverse order. (ie, less recently used items are iterated over first.)
  759. */
  760. rforEach(fn, thisp = this) {
  761. for (const i of this.#rindexes()) {
  762. const v = this.#valList[i];
  763. const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
  764. if (value === undefined)
  765. continue;
  766. fn.call(thisp, value, this.#keyList[i], this);
  767. }
  768. }
  769. /**
  770. * Delete any stale entries. Returns true if anything was removed,
  771. * false otherwise.
  772. */
  773. purgeStale() {
  774. let deleted = false;
  775. for (const i of this.#rindexes({ allowStale: true })) {
  776. if (this.#isStale(i)) {
  777. this.#delete(this.#keyList[i], 'expire');
  778. deleted = true;
  779. }
  780. }
  781. return deleted;
  782. }
  783. /**
  784. * Get the extended info about a given entry, to get its value, size, and
  785. * TTL info simultaneously. Returns `undefined` if the key is not present.
  786. *
  787. * Unlike {@link LRUCache#dump}, which is designed to be portable and survive
  788. * serialization, the `start` value is always the current timestamp, and the
  789. * `ttl` is a calculated remaining time to live (negative if expired).
  790. *
  791. * Always returns stale values, if their info is found in the cache, so be
  792. * sure to check for expirations (ie, a negative {@link LRUCache.Entry#ttl})
  793. * if relevant.
  794. */
  795. info(key) {
  796. const i = this.#keyMap.get(key);
  797. if (i === undefined)
  798. return undefined;
  799. const v = this.#valList[i];
  800. /* c8 ignore start - this isn't tested for the info function,
  801. * but it's the same logic as found in other places. */
  802. const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
  803. if (value === undefined)
  804. return undefined;
  805. /* c8 ignore end */
  806. const entry = { value };
  807. if (this.#ttls && this.#starts) {
  808. const ttl = this.#ttls[i];
  809. const start = this.#starts[i];
  810. if (ttl && start) {
  811. const remain = ttl - (this.#perf.now() - start);
  812. entry.ttl = remain;
  813. entry.start = Date.now();
  814. }
  815. }
  816. if (this.#sizes) {
  817. entry.size = this.#sizes[i];
  818. }
  819. return entry;
  820. }
  821. /**
  822. * Return an array of [key, {@link LRUCache.Entry}] tuples which can be
  823. * passed to {@link LRUCache#load}.
  824. *
  825. * The `start` fields are calculated relative to a portable `Date.now()`
  826. * timestamp, even if `performance.now()` is available.
  827. *
  828. * Stale entries are always included in the `dump`, even if
  829. * {@link LRUCache.OptionsBase.allowStale} is false.
  830. *
  831. * Note: this returns an actual array, not a generator, so it can be more
  832. * easily passed around.
  833. */
  834. dump() {
  835. const arr = [];
  836. for (const i of this.#indexes({ allowStale: true })) {
  837. const key = this.#keyList[i];
  838. const v = this.#valList[i];
  839. const value = this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
  840. if (value === undefined || key === undefined)
  841. continue;
  842. const entry = { value };
  843. if (this.#ttls && this.#starts) {
  844. entry.ttl = this.#ttls[i];
  845. // always dump the start relative to a portable timestamp
  846. // it's ok for this to be a bit slow, it's a rare operation.
  847. const age = this.#perf.now() - this.#starts[i];
  848. entry.start = Math.floor(Date.now() - age);
  849. }
  850. if (this.#sizes) {
  851. entry.size = this.#sizes[i];
  852. }
  853. arr.unshift([key, entry]);
  854. }
  855. return arr;
  856. }
  857. /**
  858. * Reset the cache and load in the items in entries in the order listed.
  859. *
  860. * The shape of the resulting cache may be different if the same options are
  861. * not used in both caches.
  862. *
  863. * The `start` fields are assumed to be calculated relative to a portable
  864. * `Date.now()` timestamp, even if `performance.now()` is available.
  865. */
  866. load(arr) {
  867. this.clear();
  868. for (const [key, entry] of arr) {
  869. if (entry.start) {
  870. // entry.start is a portable timestamp, but we may be using
  871. // node's performance.now(), so calculate the offset, so that
  872. // we get the intended remaining TTL, no matter how long it's
  873. // been on ice.
  874. //
  875. // it's ok for this to be a bit slow, it's a rare operation.
  876. const age = Date.now() - entry.start;
  877. entry.start = this.#perf.now() - age;
  878. }
  879. this.set(key, entry.value, entry);
  880. }
  881. }
  882. /**
  883. * Add a value to the cache.
  884. *
  885. * Note: if `undefined` is specified as a value, this is an alias for
  886. * {@link LRUCache#delete}
  887. *
  888. * Fields on the {@link LRUCache.SetOptions} options param will override
  889. * their corresponding values in the constructor options for the scope
  890. * of this single `set()` operation.
  891. *
  892. * If `start` is provided, then that will set the effective start
  893. * time for the TTL calculation. Note that this must be a previous
  894. * value of `performance.now()` if supported, or a previous value of
  895. * `Date.now()` if not.
  896. *
  897. * Options object may also include `size`, which will prevent
  898. * calling the `sizeCalculation` function and just use the specified
  899. * number if it is a positive integer, and `noDisposeOnSet` which
  900. * will prevent calling a `dispose` function in the case of
  901. * overwrites.
  902. *
  903. * If the `size` (or return value of `sizeCalculation`) for a given
  904. * entry is greater than `maxEntrySize`, then the item will not be
  905. * added to the cache.
  906. *
  907. * Will update the recency of the entry.
  908. *
  909. * If the value is `undefined`, then this is an alias for
  910. * `cache.delete(key)`. `undefined` is never stored in the cache.
  911. */
  912. set(k, v, setOptions = {}) {
  913. if (v === undefined) {
  914. this.delete(k);
  915. return this;
  916. }
  917. const { ttl = this.ttl, start, noDisposeOnSet = this.noDisposeOnSet, sizeCalculation = this.sizeCalculation, status, } = setOptions;
  918. let { noUpdateTTL = this.noUpdateTTL } = setOptions;
  919. const size = this.#requireSize(k, v, setOptions.size || 0, sizeCalculation);
  920. // if the item doesn't fit, don't do anything
  921. // NB: maxEntrySize set to maxSize by default
  922. if (this.maxEntrySize && size > this.maxEntrySize) {
  923. if (status) {
  924. status.set = 'miss';
  925. status.maxEntrySizeExceeded = true;
  926. }
  927. // have to delete, in case something is there already.
  928. this.#delete(k, 'set');
  929. return this;
  930. }
  931. let index = this.#size === 0 ? undefined : this.#keyMap.get(k);
  932. if (index === undefined) {
  933. // addition
  934. index = (this.#size === 0 ? this.#tail
  935. : this.#free.length !== 0 ? this.#free.pop()
  936. : this.#size === this.#max ? this.#evict(false)
  937. : this.#size);
  938. this.#keyList[index] = k;
  939. this.#valList[index] = v;
  940. this.#keyMap.set(k, index);
  941. this.#next[this.#tail] = index;
  942. this.#prev[index] = this.#tail;
  943. this.#tail = index;
  944. this.#size++;
  945. this.#addItemSize(index, size, status);
  946. if (status)
  947. status.set = 'add';
  948. noUpdateTTL = false;
  949. if (this.#hasOnInsert) {
  950. this.#onInsert?.(v, k, 'add');
  951. }
  952. }
  953. else {
  954. // update
  955. this.#moveToTail(index);
  956. const oldVal = this.#valList[index];
  957. if (v !== oldVal) {
  958. if (this.#hasFetchMethod && this.#isBackgroundFetch(oldVal)) {
  959. oldVal.__abortController.abort(new Error('replaced'));
  960. const { __staleWhileFetching: s } = oldVal;
  961. if (s !== undefined && !noDisposeOnSet) {
  962. if (this.#hasDispose) {
  963. this.#dispose?.(s, k, 'set');
  964. }
  965. if (this.#hasDisposeAfter) {
  966. this.#disposed?.push([s, k, 'set']);
  967. }
  968. }
  969. }
  970. else if (!noDisposeOnSet) {
  971. if (this.#hasDispose) {
  972. this.#dispose?.(oldVal, k, 'set');
  973. }
  974. if (this.#hasDisposeAfter) {
  975. this.#disposed?.push([oldVal, k, 'set']);
  976. }
  977. }
  978. this.#removeItemSize(index);
  979. this.#addItemSize(index, size, status);
  980. this.#valList[index] = v;
  981. if (status) {
  982. status.set = 'replace';
  983. const oldValue = oldVal && this.#isBackgroundFetch(oldVal) ?
  984. oldVal.__staleWhileFetching
  985. : oldVal;
  986. if (oldValue !== undefined)
  987. status.oldValue = oldValue;
  988. }
  989. }
  990. else if (status) {
  991. status.set = 'update';
  992. }
  993. if (this.#hasOnInsert) {
  994. this.onInsert?.(v, k, v === oldVal ? 'update' : 'replace');
  995. }
  996. }
  997. if (ttl !== 0 && !this.#ttls) {
  998. this.#initializeTTLTracking();
  999. }
  1000. if (this.#ttls) {
  1001. if (!noUpdateTTL) {
  1002. this.#setItemTTL(index, ttl, start);
  1003. }
  1004. if (status)
  1005. this.#statusTTL(status, index);
  1006. }
  1007. if (!noDisposeOnSet && this.#hasDisposeAfter && this.#disposed) {
  1008. const dt = this.#disposed;
  1009. let task;
  1010. while ((task = dt?.shift())) {
  1011. this.#disposeAfter?.(...task);
  1012. }
  1013. }
  1014. return this;
  1015. }
  1016. /**
  1017. * Evict the least recently used item, returning its value or
  1018. * `undefined` if cache is empty.
  1019. */
  1020. pop() {
  1021. try {
  1022. while (this.#size) {
  1023. const val = this.#valList[this.#head];
  1024. this.#evict(true);
  1025. if (this.#isBackgroundFetch(val)) {
  1026. if (val.__staleWhileFetching) {
  1027. return val.__staleWhileFetching;
  1028. }
  1029. }
  1030. else if (val !== undefined) {
  1031. return val;
  1032. }
  1033. }
  1034. }
  1035. finally {
  1036. if (this.#hasDisposeAfter && this.#disposed) {
  1037. const dt = this.#disposed;
  1038. let task;
  1039. while ((task = dt?.shift())) {
  1040. this.#disposeAfter?.(...task);
  1041. }
  1042. }
  1043. }
  1044. }
  1045. #evict(free) {
  1046. const head = this.#head;
  1047. const k = this.#keyList[head];
  1048. const v = this.#valList[head];
  1049. if (this.#hasFetchMethod && this.#isBackgroundFetch(v)) {
  1050. v.__abortController.abort(new Error('evicted'));
  1051. }
  1052. else if (this.#hasDispose || this.#hasDisposeAfter) {
  1053. if (this.#hasDispose) {
  1054. this.#dispose?.(v, k, 'evict');
  1055. }
  1056. if (this.#hasDisposeAfter) {
  1057. this.#disposed?.push([v, k, 'evict']);
  1058. }
  1059. }
  1060. this.#removeItemSize(head);
  1061. if (this.#autopurgeTimers?.[head]) {
  1062. clearTimeout(this.#autopurgeTimers[head]);
  1063. this.#autopurgeTimers[head] = undefined;
  1064. }
  1065. // if we aren't about to use the index, then null these out
  1066. if (free) {
  1067. this.#keyList[head] = undefined;
  1068. this.#valList[head] = undefined;
  1069. this.#free.push(head);
  1070. }
  1071. if (this.#size === 1) {
  1072. this.#head = this.#tail = 0;
  1073. this.#free.length = 0;
  1074. }
  1075. else {
  1076. this.#head = this.#next[head];
  1077. }
  1078. this.#keyMap.delete(k);
  1079. this.#size--;
  1080. return head;
  1081. }
  1082. /**
  1083. * Check if a key is in the cache, without updating the recency of use.
  1084. * Will return false if the item is stale, even though it is technically
  1085. * in the cache.
  1086. *
  1087. * Check if a key is in the cache, without updating the recency of
  1088. * use. Age is updated if {@link LRUCache.OptionsBase.updateAgeOnHas} is set
  1089. * to `true` in either the options or the constructor.
  1090. *
  1091. * Will return `false` if the item is stale, even though it is technically in
  1092. * the cache. The difference can be determined (if it matters) by using a
  1093. * `status` argument, and inspecting the `has` field.
  1094. *
  1095. * Will not update item age unless
  1096. * {@link LRUCache.OptionsBase.updateAgeOnHas} is set.
  1097. */
  1098. has(k, hasOptions = {}) {
  1099. const { updateAgeOnHas = this.updateAgeOnHas, status } = hasOptions;
  1100. const index = this.#keyMap.get(k);
  1101. if (index !== undefined) {
  1102. const v = this.#valList[index];
  1103. if (this.#isBackgroundFetch(v) &&
  1104. v.__staleWhileFetching === undefined) {
  1105. return false;
  1106. }
  1107. if (!this.#isStale(index)) {
  1108. if (updateAgeOnHas) {
  1109. this.#updateItemAge(index);
  1110. }
  1111. if (status) {
  1112. status.has = 'hit';
  1113. this.#statusTTL(status, index);
  1114. }
  1115. return true;
  1116. }
  1117. else if (status) {
  1118. status.has = 'stale';
  1119. this.#statusTTL(status, index);
  1120. }
  1121. }
  1122. else if (status) {
  1123. status.has = 'miss';
  1124. }
  1125. return false;
  1126. }
  1127. /**
  1128. * Like {@link LRUCache#get} but doesn't update recency or delete stale
  1129. * items.
  1130. *
  1131. * Returns `undefined` if the item is stale, unless
  1132. * {@link LRUCache.OptionsBase.allowStale} is set.
  1133. */
  1134. peek(k, peekOptions = {}) {
  1135. const { allowStale = this.allowStale } = peekOptions;
  1136. const index = this.#keyMap.get(k);
  1137. if (index === undefined || (!allowStale && this.#isStale(index))) {
  1138. return;
  1139. }
  1140. const v = this.#valList[index];
  1141. // either stale and allowed, or forcing a refresh of non-stale value
  1142. return this.#isBackgroundFetch(v) ? v.__staleWhileFetching : v;
  1143. }
  1144. #backgroundFetch(k, index, options, context) {
  1145. const v = index === undefined ? undefined : this.#valList[index];
  1146. if (this.#isBackgroundFetch(v)) {
  1147. return v;
  1148. }
  1149. const ac = new AC();
  1150. const { signal } = options;
  1151. // when/if our AC signals, then stop listening to theirs.
  1152. signal?.addEventListener('abort', () => ac.abort(signal.reason), {
  1153. signal: ac.signal,
  1154. });
  1155. const fetchOpts = {
  1156. signal: ac.signal,
  1157. options,
  1158. context,
  1159. };
  1160. const cb = (v, updateCache = false) => {
  1161. const { aborted } = ac.signal;
  1162. const ignoreAbort = options.ignoreFetchAbort && v !== undefined;
  1163. const proceed = options.ignoreFetchAbort ||
  1164. !!(options.allowStaleOnFetchAbort && v !== undefined);
  1165. if (options.status) {
  1166. if (aborted && !updateCache) {
  1167. options.status.fetchAborted = true;
  1168. options.status.fetchError = ac.signal.reason;
  1169. if (ignoreAbort)
  1170. options.status.fetchAbortIgnored = true;
  1171. }
  1172. else {
  1173. options.status.fetchResolved = true;
  1174. }
  1175. }
  1176. if (aborted && !ignoreAbort && !updateCache) {
  1177. return fetchFail(ac.signal.reason, proceed);
  1178. }
  1179. // either we didn't abort, and are still here, or we did, and ignored
  1180. const bf = p;
  1181. // if nothing else has been written there but we're set to update the
  1182. // cache and ignore the abort, or if it's still pending on this specific
  1183. // background request, then write it to the cache.
  1184. const vl = this.#valList[index];
  1185. if (vl === p || (ignoreAbort && updateCache && vl === undefined)) {
  1186. if (v === undefined) {
  1187. if (bf.__staleWhileFetching !== undefined) {
  1188. this.#valList[index] = bf.__staleWhileFetching;
  1189. }
  1190. else {
  1191. this.#delete(k, 'fetch');
  1192. }
  1193. }
  1194. else {
  1195. if (options.status)
  1196. options.status.fetchUpdated = true;
  1197. this.set(k, v, fetchOpts.options);
  1198. }
  1199. }
  1200. return v;
  1201. };
  1202. const eb = (er) => {
  1203. if (options.status) {
  1204. options.status.fetchRejected = true;
  1205. options.status.fetchError = er;
  1206. }
  1207. // do not pass go, do not collect $200
  1208. return fetchFail(er, false);
  1209. };
  1210. const fetchFail = (er, proceed) => {
  1211. const { aborted } = ac.signal;
  1212. const allowStaleAborted = aborted && options.allowStaleOnFetchAbort;
  1213. const allowStale = allowStaleAborted || options.allowStaleOnFetchRejection;
  1214. const noDelete = allowStale || options.noDeleteOnFetchRejection;
  1215. const bf = p;
  1216. if (this.#valList[index] === p) {
  1217. // if we allow stale on fetch rejections, then we need to ensure that
  1218. // the stale value is not removed from the cache when the fetch fails.
  1219. const del = !noDelete ||
  1220. !proceed && bf.__staleWhileFetching === undefined;
  1221. if (del) {
  1222. this.#delete(k, 'fetch');
  1223. }
  1224. else if (!allowStaleAborted) {
  1225. // still replace the *promise* with the stale value,
  1226. // since we are done with the promise at this point.
  1227. // leave it untouched if we're still waiting for an
  1228. // aborted background fetch that hasn't yet returned.
  1229. this.#valList[index] = bf.__staleWhileFetching;
  1230. }
  1231. }
  1232. if (allowStale) {
  1233. if (options.status && bf.__staleWhileFetching !== undefined) {
  1234. options.status.returnedStale = true;
  1235. }
  1236. return bf.__staleWhileFetching;
  1237. }
  1238. else if (bf.__returned === bf) {
  1239. throw er;
  1240. }
  1241. };
  1242. const pcall = (res, rej) => {
  1243. const fmp = this.#fetchMethod?.(k, v, fetchOpts);
  1244. if (fmp && fmp instanceof Promise) {
  1245. fmp.then(v => res(v === undefined ? undefined : v), rej);
  1246. }
  1247. // ignored, we go until we finish, regardless.
  1248. // defer check until we are actually aborting,
  1249. // so fetchMethod can override.
  1250. ac.signal.addEventListener('abort', () => {
  1251. if (!options.ignoreFetchAbort || options.allowStaleOnFetchAbort) {
  1252. res(undefined);
  1253. // when it eventually resolves, update the cache.
  1254. if (options.allowStaleOnFetchAbort) {
  1255. res = v => cb(v, true);
  1256. }
  1257. }
  1258. });
  1259. };
  1260. if (options.status)
  1261. options.status.fetchDispatched = true;
  1262. const p = new Promise(pcall).then(cb, eb);
  1263. const bf = Object.assign(p, {
  1264. __abortController: ac,
  1265. __staleWhileFetching: v,
  1266. __returned: undefined,
  1267. });
  1268. if (index === undefined) {
  1269. // internal, don't expose status.
  1270. this.set(k, bf, { ...fetchOpts.options, status: undefined });
  1271. index = this.#keyMap.get(k);
  1272. }
  1273. else {
  1274. this.#valList[index] = bf;
  1275. }
  1276. return bf;
  1277. }
  1278. #isBackgroundFetch(p) {
  1279. if (!this.#hasFetchMethod)
  1280. return false;
  1281. const b = p;
  1282. return (!!b &&
  1283. b instanceof Promise &&
  1284. b.hasOwnProperty('__staleWhileFetching') &&
  1285. b.__abortController instanceof AC);
  1286. }
  1287. async fetch(k, fetchOptions = {}) {
  1288. const {
  1289. // get options
  1290. allowStale = this.allowStale, updateAgeOnGet = this.updateAgeOnGet, noDeleteOnStaleGet = this.noDeleteOnStaleGet,
  1291. // set options
  1292. ttl = this.ttl, noDisposeOnSet = this.noDisposeOnSet, size = 0, sizeCalculation = this.sizeCalculation, noUpdateTTL = this.noUpdateTTL,
  1293. // fetch exclusive options
  1294. noDeleteOnFetchRejection = this.noDeleteOnFetchRejection, allowStaleOnFetchRejection = this.allowStaleOnFetchRejection, ignoreFetchAbort = this.ignoreFetchAbort, allowStaleOnFetchAbort = this.allowStaleOnFetchAbort, context, forceRefresh = false, status, signal, } = fetchOptions;
  1295. if (!this.#hasFetchMethod) {
  1296. if (status)
  1297. status.fetch = 'get';
  1298. return this.get(k, {
  1299. allowStale,
  1300. updateAgeOnGet,
  1301. noDeleteOnStaleGet,
  1302. status,
  1303. });
  1304. }
  1305. const options = {
  1306. allowStale,
  1307. updateAgeOnGet,
  1308. noDeleteOnStaleGet,
  1309. ttl,
  1310. noDisposeOnSet,
  1311. size,
  1312. sizeCalculation,
  1313. noUpdateTTL,
  1314. noDeleteOnFetchRejection,
  1315. allowStaleOnFetchRejection,
  1316. allowStaleOnFetchAbort,
  1317. ignoreFetchAbort,
  1318. status,
  1319. signal,
  1320. };
  1321. let index = this.#keyMap.get(k);
  1322. if (index === undefined) {
  1323. if (status)
  1324. status.fetch = 'miss';
  1325. const p = this.#backgroundFetch(k, index, options, context);
  1326. return (p.__returned = p);
  1327. }
  1328. else {
  1329. // in cache, maybe already fetching
  1330. const v = this.#valList[index];
  1331. if (this.#isBackgroundFetch(v)) {
  1332. const stale = allowStale && v.__staleWhileFetching !== undefined;
  1333. if (status) {
  1334. status.fetch = 'inflight';
  1335. if (stale)
  1336. status.returnedStale = true;
  1337. }
  1338. return stale ? v.__staleWhileFetching : (v.__returned = v);
  1339. }
  1340. // if we force a refresh, that means do NOT serve the cached value,
  1341. // unless we are already in the process of refreshing the cache.
  1342. const isStale = this.#isStale(index);
  1343. if (!forceRefresh && !isStale) {
  1344. if (status)
  1345. status.fetch = 'hit';
  1346. this.#moveToTail(index);
  1347. if (updateAgeOnGet) {
  1348. this.#updateItemAge(index);
  1349. }
  1350. if (status)
  1351. this.#statusTTL(status, index);
  1352. return v;
  1353. }
  1354. // ok, it is stale or a forced refresh, and not already fetching.
  1355. // refresh the cache.
  1356. const p = this.#backgroundFetch(k, index, options, context);
  1357. const hasStale = p.__staleWhileFetching !== undefined;
  1358. const staleVal = hasStale && allowStale;
  1359. if (status) {
  1360. status.fetch = isStale ? 'stale' : 'refresh';
  1361. if (staleVal && isStale)
  1362. status.returnedStale = true;
  1363. }
  1364. return staleVal ? p.__staleWhileFetching : (p.__returned = p);
  1365. }
  1366. }
  1367. async forceFetch(k, fetchOptions = {}) {
  1368. const v = await this.fetch(k, fetchOptions);
  1369. if (v === undefined)
  1370. throw new Error('fetch() returned undefined');
  1371. return v;
  1372. }
  1373. memo(k, memoOptions = {}) {
  1374. const memoMethod = this.#memoMethod;
  1375. if (!memoMethod) {
  1376. throw new Error('no memoMethod provided to constructor');
  1377. }
  1378. const { context, forceRefresh, ...options } = memoOptions;
  1379. const v = this.get(k, options);
  1380. if (!forceRefresh && v !== undefined)
  1381. return v;
  1382. const vv = memoMethod(k, v, {
  1383. options,
  1384. context,
  1385. });
  1386. this.set(k, vv, options);
  1387. return vv;
  1388. }
  1389. /**
  1390. * Return a value from the cache. Will update the recency of the cache
  1391. * entry found.
  1392. *
  1393. * If the key is not found, get() will return `undefined`.
  1394. */
  1395. get(k, getOptions = {}) {
  1396. const { allowStale = this.allowStale, updateAgeOnGet = this.updateAgeOnGet, noDeleteOnStaleGet = this.noDeleteOnStaleGet, status, } = getOptions;
  1397. const index = this.#keyMap.get(k);
  1398. if (index !== undefined) {
  1399. const value = this.#valList[index];
  1400. const fetching = this.#isBackgroundFetch(value);
  1401. if (status)
  1402. this.#statusTTL(status, index);
  1403. if (this.#isStale(index)) {
  1404. if (status)
  1405. status.get = 'stale';
  1406. // delete only if not an in-flight background fetch
  1407. if (!fetching) {
  1408. if (!noDeleteOnStaleGet) {
  1409. this.#delete(k, 'expire');
  1410. }
  1411. if (status && allowStale)
  1412. status.returnedStale = true;
  1413. return allowStale ? value : undefined;
  1414. }
  1415. else {
  1416. if (status &&
  1417. allowStale &&
  1418. value.__staleWhileFetching !== undefined) {
  1419. status.returnedStale = true;
  1420. }
  1421. return allowStale ? value.__staleWhileFetching : undefined;
  1422. }
  1423. }
  1424. else {
  1425. if (status)
  1426. status.get = 'hit';
  1427. // if we're currently fetching it, we don't actually have it yet
  1428. // it's not stale, which means this isn't a staleWhileRefetching.
  1429. // If it's not stale, and fetching, AND has a __staleWhileFetching
  1430. // value, then that means the user fetched with {forceRefresh:true},
  1431. // so it's safe to return that value.
  1432. if (fetching) {
  1433. return value.__staleWhileFetching;
  1434. }
  1435. this.#moveToTail(index);
  1436. if (updateAgeOnGet) {
  1437. this.#updateItemAge(index);
  1438. }
  1439. return value;
  1440. }
  1441. }
  1442. else if (status) {
  1443. status.get = 'miss';
  1444. }
  1445. }
  1446. #connect(p, n) {
  1447. this.#prev[n] = p;
  1448. this.#next[p] = n;
  1449. }
  1450. #moveToTail(index) {
  1451. // if tail already, nothing to do
  1452. // if head, move head to next[index]
  1453. // else
  1454. // move next[prev[index]] to next[index] (head has no prev)
  1455. // move prev[next[index]] to prev[index]
  1456. // prev[index] = tail
  1457. // next[tail] = index
  1458. // tail = index
  1459. if (index !== this.#tail) {
  1460. if (index === this.#head) {
  1461. this.#head = this.#next[index];
  1462. }
  1463. else {
  1464. this.#connect(this.#prev[index], this.#next[index]);
  1465. }
  1466. this.#connect(this.#tail, index);
  1467. this.#tail = index;
  1468. }
  1469. }
  1470. /**
  1471. * Deletes a key out of the cache.
  1472. *
  1473. * Returns true if the key was deleted, false otherwise.
  1474. */
  1475. delete(k) {
  1476. return this.#delete(k, 'delete');
  1477. }
  1478. #delete(k, reason) {
  1479. let deleted = false;
  1480. if (this.#size !== 0) {
  1481. const index = this.#keyMap.get(k);
  1482. if (index !== undefined) {
  1483. if (this.#autopurgeTimers?.[index]) {
  1484. clearTimeout(this.#autopurgeTimers?.[index]);
  1485. this.#autopurgeTimers[index] = undefined;
  1486. }
  1487. deleted = true;
  1488. if (this.#size === 1) {
  1489. this.#clear(reason);
  1490. }
  1491. else {
  1492. this.#removeItemSize(index);
  1493. const v = this.#valList[index];
  1494. if (this.#isBackgroundFetch(v)) {
  1495. v.__abortController.abort(new Error('deleted'));
  1496. }
  1497. else if (this.#hasDispose || this.#hasDisposeAfter) {
  1498. if (this.#hasDispose) {
  1499. this.#dispose?.(v, k, reason);
  1500. }
  1501. if (this.#hasDisposeAfter) {
  1502. this.#disposed?.push([v, k, reason]);
  1503. }
  1504. }
  1505. this.#keyMap.delete(k);
  1506. this.#keyList[index] = undefined;
  1507. this.#valList[index] = undefined;
  1508. if (index === this.#tail) {
  1509. this.#tail = this.#prev[index];
  1510. }
  1511. else if (index === this.#head) {
  1512. this.#head = this.#next[index];
  1513. }
  1514. else {
  1515. const pi = this.#prev[index];
  1516. this.#next[pi] = this.#next[index];
  1517. const ni = this.#next[index];
  1518. this.#prev[ni] = this.#prev[index];
  1519. }
  1520. this.#size--;
  1521. this.#free.push(index);
  1522. }
  1523. }
  1524. }
  1525. if (this.#hasDisposeAfter && this.#disposed?.length) {
  1526. const dt = this.#disposed;
  1527. let task;
  1528. while ((task = dt?.shift())) {
  1529. this.#disposeAfter?.(...task);
  1530. }
  1531. }
  1532. return deleted;
  1533. }
  1534. /**
  1535. * Clear the cache entirely, throwing away all values.
  1536. */
  1537. clear() {
  1538. return this.#clear('delete');
  1539. }
  1540. #clear(reason) {
  1541. for (const index of this.#rindexes({ allowStale: true })) {
  1542. const v = this.#valList[index];
  1543. if (this.#isBackgroundFetch(v)) {
  1544. v.__abortController.abort(new Error('deleted'));
  1545. }
  1546. else {
  1547. const k = this.#keyList[index];
  1548. if (this.#hasDispose) {
  1549. this.#dispose?.(v, k, reason);
  1550. }
  1551. if (this.#hasDisposeAfter) {
  1552. this.#disposed?.push([v, k, reason]);
  1553. }
  1554. }
  1555. }
  1556. this.#keyMap.clear();
  1557. this.#valList.fill(undefined);
  1558. this.#keyList.fill(undefined);
  1559. if (this.#ttls && this.#starts) {
  1560. this.#ttls.fill(0);
  1561. this.#starts.fill(0);
  1562. for (const t of this.#autopurgeTimers ?? []) {
  1563. if (t !== undefined)
  1564. clearTimeout(t);
  1565. }
  1566. this.#autopurgeTimers?.fill(undefined);
  1567. }
  1568. if (this.#sizes) {
  1569. this.#sizes.fill(0);
  1570. }
  1571. this.#head = 0;
  1572. this.#tail = 0;
  1573. this.#free.length = 0;
  1574. this.#calculatedSize = 0;
  1575. this.#size = 0;
  1576. if (this.#hasDisposeAfter && this.#disposed) {
  1577. const dt = this.#disposed;
  1578. let task;
  1579. while ((task = dt?.shift())) {
  1580. this.#disposeAfter?.(...task);
  1581. }
  1582. }
  1583. }
  1584. }
  1585. //# sourceMappingURL=index.js.map