{"version":3,"sources":["../../../../src/server/lib/lru-cache.ts"],"sourcesContent":["/**\n * Node in the doubly-linked list used for LRU tracking.\n * Each node represents a cache entry with bidirectional pointers.\n */\nclass LRUNode<T> {\n  public readonly key: string\n  public data: T\n  public size: number\n  public prev: LRUNode<T> | SentinelNode<T> | null = null\n  public next: LRUNode<T> | SentinelNode<T> | null = null\n\n  constructor(key: string, data: T, size: number) {\n    this.key = key\n    this.data = data\n    this.size = size\n  }\n}\n\n/**\n * Sentinel node used for head/tail boundaries.\n * These nodes don't contain actual cache data but simplify list operations.\n */\nclass SentinelNode<T> {\n  public prev: LRUNode<T> | SentinelNode<T> | null = null\n  public next: LRUNode<T> | SentinelNode<T> | null = null\n}\n\n/**\n * LRU (Least Recently Used) Cache implementation using a doubly-linked list\n * and hash map for O(1) operations.\n *\n * Algorithm:\n * - Uses a doubly-linked list to maintain access order (most recent at head)\n * - Hash map provides O(1) key-to-node lookup\n * - Sentinel head/tail nodes simplify edge case handling\n * - Size-based eviction supports custom size calculation functions\n *\n * Data Structure Layout:\n * HEAD <-> [most recent] <-> ... <-> [least recent] <-> TAIL\n *\n * Operations:\n * - get(): Move accessed node to head (mark as most recent)\n * - set(): Add new node at head, evict from tail if over capacity\n * - Eviction: Remove least recent node (tail.prev) when size exceeds limit\n */\nexport class LRUCache<T> {\n  private readonly cache: Map<string, LRUNode<T>> = new Map()\n  private readonly head: SentinelNode<T>\n  private readonly tail: SentinelNode<T>\n  private totalSize: number = 0\n  private readonly maxSize: number\n  private readonly calculateSize: ((value: T) => number) | undefined\n  private readonly onEvict: ((key: string, value: T) => void) | undefined\n\n  constructor(\n    maxSize: number,\n    calculateSize?: (value: T) => number,\n    onEvict?: (key: string, value: T) => void\n  ) {\n    this.maxSize = maxSize\n    this.calculateSize = calculateSize\n    this.onEvict = onEvict\n\n    // Create sentinel nodes to simplify doubly-linked list operations\n    // HEAD <-> TAIL (empty list)\n    this.head = new SentinelNode<T>()\n    this.tail = new SentinelNode<T>()\n    this.head.next = this.tail\n    this.tail.prev = this.head\n  }\n\n  /**\n   * Adds a node immediately after the head (marks as most recently used).\n   * Used when inserting new items or when an item is accessed.\n   * PRECONDITION: node must be disconnected (prev/next should be null)\n   */\n  private addToHead(node: LRUNode<T>): void {\n    node.prev = this.head\n    node.next = this.head.next\n    // head.next is always non-null (points to tail or another node)\n    this.head.next!.prev = node\n    this.head.next = node\n  }\n\n  /**\n   * Removes a node from its current position in the doubly-linked list.\n   * Updates the prev/next pointers of adjacent nodes to maintain list integrity.\n   * PRECONDITION: node must be connected (prev/next are non-null)\n   */\n  private removeNode(node: LRUNode<T>): void {\n    // Connected nodes always have non-null prev/next\n    node.prev!.next = node.next\n    node.next!.prev = node.prev\n  }\n\n  /**\n   * Moves an existing node to the head position (marks as most recently used).\n   * This is the core LRU operation - accessed items become most recent.\n   */\n  private moveToHead(node: LRUNode<T>): void {\n    this.removeNode(node)\n    this.addToHead(node)\n  }\n\n  /**\n   * Removes and returns the least recently used node (the one before tail).\n   * This is called during eviction when the cache exceeds capacity.\n   * PRECONDITION: cache is not empty (ensured by caller)\n   */\n  private removeTail(): LRUNode<T> {\n    const lastNode = this.tail.prev as LRUNode<T>\n    // tail.prev is always non-null and always LRUNode when cache is not empty\n    this.removeNode(lastNode)\n    return lastNode\n  }\n\n  /**\n   * Sets a key-value pair in the cache.\n   * If the key exists, updates the value and moves to head.\n   * If new, adds at head and evicts from tail if necessary.\n   *\n   * Time Complexity:\n   * - O(1) for uniform item sizes\n   * - O(k) where k is the number of items evicted (can be O(N) for variable sizes)\n   */\n  public set(key: string, value: T): boolean {\n    const size = this.calculateSize?.(value) ?? 1\n    if (size <= 0) {\n      throw new Error(\n        `LRUCache: calculateSize returned ${size}, but size must be > 0. ` +\n          `Items with size 0 would never be evicted, causing unbounded cache growth.`\n      )\n    }\n    if (size > this.maxSize) {\n      console.warn('Single item size exceeds maxSize')\n      return false\n    }\n\n    const existing = this.cache.get(key)\n    if (existing) {\n      // Update existing node: adjust size and move to head (most recent)\n      existing.data = value\n      this.totalSize = this.totalSize - existing.size + size\n      existing.size = size\n      this.moveToHead(existing)\n    } else {\n      // Add new node at head (most recent position)\n      const newNode = new LRUNode(key, value, size)\n      this.cache.set(key, newNode)\n      this.addToHead(newNode)\n      this.totalSize += size\n    }\n\n    // Evict least recently used items until under capacity\n    while (this.totalSize > this.maxSize && this.cache.size > 0) {\n      const tail = this.removeTail()\n      this.cache.delete(tail.key)\n      this.totalSize -= tail.size\n      this.onEvict?.(tail.key, tail.data)\n    }\n\n    return true\n  }\n\n  /**\n   * Checks if a key exists in the cache.\n   * This is a pure query operation - does NOT update LRU order.\n   *\n   * Time Complexity: O(1)\n   */\n  public has(key: string): boolean {\n    return this.cache.has(key)\n  }\n\n  /**\n   * Retrieves a value by key and marks it as most recently used.\n   * Moving to head maintains the LRU property for future evictions.\n   *\n   * Time Complexity: O(1)\n   */\n  public get(key: string): T | undefined {\n    const node = this.cache.get(key)\n    if (!node) return undefined\n\n    // Mark as most recently used by moving to head\n    this.moveToHead(node)\n\n    return node.data\n  }\n\n  /**\n   * Returns an iterator over the cache entries. The order is outputted in the\n   * order of most recently used to least recently used.\n   */\n  public *[Symbol.iterator](): IterableIterator<[string, T]> {\n    let current = this.head.next\n    while (current && current !== this.tail) {\n      // Between head and tail, current is always LRUNode\n      const node = current as LRUNode<T>\n      yield [node.key, node.data]\n      current = current.next\n    }\n  }\n\n  /**\n   * Removes a specific key from the cache.\n   * Updates both the hash map and doubly-linked list.\n   *\n   * Note: This is an explicit removal and does NOT trigger the `onEvict`\n   * callback. Use this for intentional deletions where eviction tracking\n   * is not needed.\n   *\n   * Time Complexity: O(1)\n   */\n  public remove(key: string): void {\n    const node = this.cache.get(key)\n    if (!node) return\n\n    this.removeNode(node)\n    this.cache.delete(key)\n    this.totalSize -= node.size\n  }\n\n  /**\n   * Returns the number of items in the cache.\n   */\n  public get size(): number {\n    return this.cache.size\n  }\n\n  /**\n   * Returns the current total size of all cached items.\n   * This uses the custom size calculation if provided.\n   */\n  public get currentSize(): number {\n    return this.totalSize\n  }\n}\n"],"names":["LRUNode","constructor","key","data","size","prev","next","SentinelNode","LRUCache","maxSize","calculateSize","onEvict","cache","Map","totalSize","head","tail","addToHead","node","removeNode","moveToHead","removeTail","lastNode","set","value","Error","console","warn","existing","get","newNode","delete","has","undefined","Symbol","iterator","current","remove","currentSize"],"mappings":"AAAA;;;CAGC,GACD,MAAMA;IAOJC,YAAYC,GAAW,EAAEC,IAAO,EAAEC,IAAY,CAAE;aAHzCC,OAA4C;aAC5CC,OAA4C;QAGjD,IAAI,CAACJ,GAAG,GAAGA;QACX,IAAI,CAACC,IAAI,GAAGA;QACZ,IAAI,CAACC,IAAI,GAAGA;IACd;AACF;AAEA;;;CAGC,GACD,MAAMG;;aACGF,OAA4C;aAC5CC,OAA4C;;AACrD;AAEA;;;;;;;;;;;;;;;;;CAiBC,GACD,OAAO,MAAME;IASXP,YACEQ,OAAe,EACfC,aAAoC,EACpCC,OAAyC,CACzC;aAZeC,QAAiC,IAAIC;aAG9CC,YAAoB;QAU1B,IAAI,CAACL,OAAO,GAAGA;QACf,IAAI,CAACC,aAAa,GAAGA;QACrB,IAAI,CAACC,OAAO,GAAGA;QAEf,kEAAkE;QAClE,6BAA6B;QAC7B,IAAI,CAACI,IAAI,GAAG,IAAIR;QAChB,IAAI,CAACS,IAAI,GAAG,IAAIT;QAChB,IAAI,CAACQ,IAAI,CAACT,IAAI,GAAG,IAAI,CAACU,IAAI;QAC1B,IAAI,CAACA,IAAI,CAACX,IAAI,GAAG,IAAI,CAACU,IAAI;IAC5B;IAEA;;;;GAIC,GACD,AAAQE,UAAUC,IAAgB,EAAQ;QACxCA,KAAKb,IAAI,GAAG,IAAI,CAACU,IAAI;QACrBG,KAAKZ,IAAI,GAAG,IAAI,CAACS,IAAI,CAACT,IAAI;QAC1B,gEAAgE;QAChE,IAAI,CAACS,IAAI,CAACT,IAAI,CAAED,IAAI,GAAGa;QACvB,IAAI,CAACH,IAAI,CAACT,IAAI,GAAGY;IACnB;IAEA;;;;GAIC,GACD,AAAQC,WAAWD,IAAgB,EAAQ;QACzC,iDAAiD;QACjDA,KAAKb,IAAI,CAAEC,IAAI,GAAGY,KAAKZ,IAAI;QAC3BY,KAAKZ,IAAI,CAAED,IAAI,GAAGa,KAAKb,IAAI;IAC7B;IAEA;;;GAGC,GACD,AAAQe,WAAWF,IAAgB,EAAQ;QACzC,IAAI,CAACC,UAAU,CAACD;QAChB,IAAI,CAACD,SAAS,CAACC;IACjB;IAEA;;;;GAIC,GACD,AAAQG,aAAyB;QAC/B,MAAMC,WAAW,IAAI,CAACN,IAAI,CAACX,IAAI;QAC/B,0EAA0E;QAC1E,IAAI,CAACc,UAAU,CAACG;QAChB,OAAOA;IACT;IAEA;;;;;;;;GAQC,GACD,AAAOC,IAAIrB,GAAW,EAAEsB,KAAQ,EAAW;QACzC,MAAMpB,OAAO,CAAA,IAAI,CAACM,aAAa,oBAAlB,IAAI,CAACA,aAAa,MAAlB,IAAI,EAAiBc,WAAU;QAC5C,IAAIpB,QAAQ,GAAG;YACb,MAAM,qBAGL,CAHK,IAAIqB,MACR,CAAC,iCAAiC,EAAErB,KAAK,wBAAwB,CAAC,GAChE,CAAC,yEAAyE,CAAC,GAFzE,qBAAA;uBAAA;4BAAA;8BAAA;YAGN;QACF;QACA,IAAIA,OAAO,IAAI,CAACK,OAAO,EAAE;YACvBiB,QAAQC,IAAI,CAAC;YACb,OAAO;QACT;QAEA,MAAMC,WAAW,IAAI,CAAChB,KAAK,CAACiB,GAAG,CAAC3B;QAChC,IAAI0B,UAAU;YACZ,mEAAmE;YACnEA,SAASzB,IAAI,GAAGqB;YAChB,IAAI,CAACV,SAAS,GAAG,IAAI,CAACA,SAAS,GAAGc,SAASxB,IAAI,GAAGA;YAClDwB,SAASxB,IAAI,GAAGA;YAChB,IAAI,CAACgB,UAAU,CAACQ;QAClB,OAAO;YACL,8CAA8C;YAC9C,MAAME,UAAU,IAAI9B,QAAQE,KAAKsB,OAAOpB;YACxC,IAAI,CAACQ,KAAK,CAACW,GAAG,CAACrB,KAAK4B;YACpB,IAAI,CAACb,SAAS,CAACa;YACf,IAAI,CAAChB,SAAS,IAAIV;QACpB;QAEA,uDAAuD;QACvD,MAAO,IAAI,CAACU,SAAS,GAAG,IAAI,CAACL,OAAO,IAAI,IAAI,CAACG,KAAK,CAACR,IAAI,GAAG,EAAG;YAC3D,MAAMY,OAAO,IAAI,CAACK,UAAU;YAC5B,IAAI,CAACT,KAAK,CAACmB,MAAM,CAACf,KAAKd,GAAG;YAC1B,IAAI,CAACY,SAAS,IAAIE,KAAKZ,IAAI;YAC3B,IAAI,CAACO,OAAO,oBAAZ,IAAI,CAACA,OAAO,MAAZ,IAAI,EAAWK,KAAKd,GAAG,EAAEc,KAAKb,IAAI;QACpC;QAEA,OAAO;IACT;IAEA;;;;;GAKC,GACD,AAAO6B,IAAI9B,GAAW,EAAW;QAC/B,OAAO,IAAI,CAACU,KAAK,CAACoB,GAAG,CAAC9B;IACxB;IAEA;;;;;GAKC,GACD,AAAO2B,IAAI3B,GAAW,EAAiB;QACrC,MAAMgB,OAAO,IAAI,CAACN,KAAK,CAACiB,GAAG,CAAC3B;QAC5B,IAAI,CAACgB,MAAM,OAAOe;QAElB,+CAA+C;QAC/C,IAAI,CAACb,UAAU,CAACF;QAEhB,OAAOA,KAAKf,IAAI;IAClB;IAEA;;;GAGC,GACD,CAAQ,CAAC+B,OAAOC,QAAQ,CAAC,GAAkC;QACzD,IAAIC,UAAU,IAAI,CAACrB,IAAI,CAACT,IAAI;QAC5B,MAAO8B,WAAWA,YAAY,IAAI,CAACpB,IAAI,CAAE;YACvC,mDAAmD;YACnD,MAAME,OAAOkB;YACb,MAAM;gBAAClB,KAAKhB,GAAG;gBAAEgB,KAAKf,IAAI;aAAC;YAC3BiC,UAAUA,QAAQ9B,IAAI;QACxB;IACF;IAEA;;;;;;;;;GASC,GACD,AAAO+B,OAAOnC,GAAW,EAAQ;QAC/B,MAAMgB,OAAO,IAAI,CAACN,KAAK,CAACiB,GAAG,CAAC3B;QAC5B,IAAI,CAACgB,MAAM;QAEX,IAAI,CAACC,UAAU,CAACD;QAChB,IAAI,CAACN,KAAK,CAACmB,MAAM,CAAC7B;QAClB,IAAI,CAACY,SAAS,IAAII,KAAKd,IAAI;IAC7B;IAEA;;GAEC,GACD,IAAWA,OAAe;QACxB,OAAO,IAAI,CAACQ,KAAK,CAACR,IAAI;IACxB;IAEA;;;GAGC,GACD,IAAWkC,cAAsB;QAC/B,OAAO,IAAI,CAACxB,SAAS;IACvB;AACF","ignoreList":[0]}