{"version":3,"sources":["../../../../src/client/components/segment-cache-impl/tuple-map.ts"],"sourcesContent":["// Utility type. Prefix<[A, B, C, D]> matches [A], [A, B], [A, B, C] etc.\nexport type Prefix<T extends any[]> = T extends [infer First, ...infer Rest]\n  ? [] | [First] | [First, ...Prefix<Rest>]\n  : []\n\nexport type TupleMap<Keypath extends Array<any>, V> = {\n  set(keys: Prefix<Keypath>, value: V): void\n  get(keys: Prefix<Keypath>): V | null\n  delete(keys: Prefix<Keypath>): void\n}\n\n/**\n * Creates a map whose keys are tuples. Tuples are compared per-element. This\n * is useful when a key has multiple parts, but you don't want to concatenate\n * them into a single string value.\n *\n * In the Segment Cache, we use this to store cache entries by both their href\n * and their Next-URL.\n *\n * Example:\n *   map.set(['https://localhost', 'foo/bar/baz'], 'yay');\n *   map.get(['https://localhost', 'foo/bar/baz']); // returns 'yay'\n */\nexport function createTupleMap<Keypath extends Array<any>, V>(): TupleMap<\n  Keypath,\n  V\n> {\n  type MapEntryShared = {\n    parent: MapEntry | null\n    key: any\n    map: Map<any, MapEntry> | null\n  }\n\n  type EmptyMapEntry = MapEntryShared & {\n    value: null\n    hasValue: false\n  }\n\n  type FullMapEntry = MapEntryShared & {\n    value: V\n    hasValue: true\n  }\n\n  type MapEntry = EmptyMapEntry | FullMapEntry\n\n  let rootEntry: MapEntry = {\n    parent: null,\n    key: null,\n    hasValue: false,\n    value: null,\n    map: null,\n  }\n\n  // To optimize successive lookups, we cache the last accessed keypath.\n  // Although it's not encoded in the type, these are both null or\n  // both non-null. It uses object equality, so to take advantage of this\n  // optimization, you must pass the same array instance to each successive\n  // method call, and you must also not mutate the array between calls.\n  let lastAccessedEntry: MapEntry | null = null\n  let lastAccessedKeys: Prefix<Keypath> | null = null\n\n  function getOrCreateEntry(keys: Prefix<Keypath>): MapEntry {\n    if (lastAccessedKeys === keys) {\n      return lastAccessedEntry!\n    }\n\n    // Go through each level of keys until we find the entry that matches,\n    // or create a new one if it doesn't already exist.\n    let entry = rootEntry\n    for (let i = 0; i < keys.length; i++) {\n      const key = keys[i]\n      let map = entry.map\n      if (map !== null) {\n        const existingEntry = map.get(key)\n        if (existingEntry !== undefined) {\n          // Found a match. Keep going.\n          entry = existingEntry\n          continue\n        }\n      } else {\n        map = new Map()\n        entry.map = map\n      }\n      // No entry exists yet at this level. Create a new one.\n      const newEntry: MapEntry = {\n        parent: entry,\n        key,\n        value: null,\n        hasValue: false,\n        map: null,\n      }\n      map.set(key, newEntry)\n      entry = newEntry\n    }\n\n    lastAccessedKeys = keys\n    lastAccessedEntry = entry\n\n    return entry\n  }\n\n  function getEntryIfExists(keys: Prefix<Keypath>): MapEntry | null {\n    if (lastAccessedKeys === keys) {\n      return lastAccessedEntry\n    }\n\n    // Go through each level of keys until we find the entry that matches, or\n    // return null if no match exists.\n    let entry = rootEntry\n    for (let i = 0; i < keys.length; i++) {\n      const key = keys[i]\n      let map = entry.map\n      if (map !== null) {\n        const existingEntry = map.get(key)\n        if (existingEntry !== undefined) {\n          // Found a match. Keep going.\n          entry = existingEntry\n          continue\n        }\n      }\n      // No entry exists at this level.\n      return null\n    }\n\n    lastAccessedKeys = keys\n    lastAccessedEntry = entry\n\n    return entry\n  }\n\n  function set(keys: Prefix<Keypath>, value: V): void {\n    const entry = getOrCreateEntry(keys)\n    entry.hasValue = true\n    entry.value = value\n  }\n\n  function get(keys: Prefix<Keypath>): V | null {\n    const entry = getEntryIfExists(keys)\n    if (entry === null || !entry.hasValue) {\n      return null\n    }\n    return entry.value\n  }\n\n  function deleteEntry(keys: Prefix<Keypath>): void {\n    const entry = getEntryIfExists(keys)\n    if (entry === null || !entry.hasValue) {\n      return\n    }\n\n    // Found a match. Delete it from the cache.\n    const deletedEntry: EmptyMapEntry = entry as any\n    deletedEntry.hasValue = false\n    deletedEntry.value = null\n\n    // Check if we can garbage collect the entry.\n    if (deletedEntry.map === null) {\n      // Since this entry has no value, and also no child entries, we can\n      // garbage collect it. Remove it from its parent, and keep garbage\n      // collecting the parents until we reach a non-empty entry.\n\n      // Unlike a `set` operation, these are no longer valid because the entry\n      // itself is being modified, not just the value it contains.\n      lastAccessedEntry = null\n      lastAccessedKeys = null\n\n      let parent = deletedEntry.parent\n      let key = deletedEntry.key\n      while (parent !== null) {\n        const parentMap = parent.map\n        if (parentMap !== null) {\n          parentMap.delete(key)\n          if (parentMap.size === 0) {\n            // We just removed the last entry in the parent map.\n            parent.map = null\n            if (parent.value === null) {\n              // The parent node has no child entries, nor does it have a value\n              // on itself. It can be garbage collected. Keep going.\n              key = parent.key\n              parent = parent.parent\n              continue\n            }\n          }\n        }\n        // The parent is not empty. Stop garbage collecting.\n        break\n      }\n    }\n  }\n\n  return {\n    set,\n    get,\n    delete: deleteEntry,\n  }\n}\n"],"names":["createTupleMap","rootEntry","parent","key","hasValue","value","map","lastAccessedEntry","lastAccessedKeys","getOrCreateEntry","keys","entry","i","length","existingEntry","get","undefined","Map","newEntry","set","getEntryIfExists","deleteEntry","deletedEntry","parentMap","delete","size"],"mappings":"AAAA,yEAAyE;;;;;+BAuBzDA;;;eAAAA;;;AAAT,SAASA;IAsBd,IAAIC,YAAsB;QACxBC,QAAQ;QACRC,KAAK;QACLC,UAAU;QACVC,OAAO;QACPC,KAAK;IACP;IAEA,sEAAsE;IACtE,gEAAgE;IAChE,uEAAuE;IACvE,yEAAyE;IACzE,qEAAqE;IACrE,IAAIC,oBAAqC;IACzC,IAAIC,mBAA2C;IAE/C,SAASC,iBAAiBC,IAAqB;QAC7C,IAAIF,qBAAqBE,MAAM;YAC7B,OAAOH;QACT;QAEA,sEAAsE;QACtE,mDAAmD;QACnD,IAAII,QAAQV;QACZ,IAAK,IAAIW,IAAI,GAAGA,IAAIF,KAAKG,MAAM,EAAED,IAAK;YACpC,MAAMT,MAAMO,IAAI,CAACE,EAAE;YACnB,IAAIN,MAAMK,MAAML,GAAG;YACnB,IAAIA,QAAQ,MAAM;gBAChB,MAAMQ,gBAAgBR,IAAIS,GAAG,CAACZ;gBAC9B,IAAIW,kBAAkBE,WAAW;oBAC/B,6BAA6B;oBAC7BL,QAAQG;oBACR;gBACF;YACF,OAAO;gBACLR,MAAM,IAAIW;gBACVN,MAAML,GAAG,GAAGA;YACd;YACA,uDAAuD;YACvD,MAAMY,WAAqB;gBACzBhB,QAAQS;gBACRR;gBACAE,OAAO;gBACPD,UAAU;gBACVE,KAAK;YACP;YACAA,IAAIa,GAAG,CAAChB,KAAKe;YACbP,QAAQO;QACV;QAEAV,mBAAmBE;QACnBH,oBAAoBI;QAEpB,OAAOA;IACT;IAEA,SAASS,iBAAiBV,IAAqB;QAC7C,IAAIF,qBAAqBE,MAAM;YAC7B,OAAOH;QACT;QAEA,yEAAyE;QACzE,kCAAkC;QAClC,IAAII,QAAQV;QACZ,IAAK,IAAIW,IAAI,GAAGA,IAAIF,KAAKG,MAAM,EAAED,IAAK;YACpC,MAAMT,MAAMO,IAAI,CAACE,EAAE;YACnB,IAAIN,MAAMK,MAAML,GAAG;YACnB,IAAIA,QAAQ,MAAM;gBAChB,MAAMQ,gBAAgBR,IAAIS,GAAG,CAACZ;gBAC9B,IAAIW,kBAAkBE,WAAW;oBAC/B,6BAA6B;oBAC7BL,QAAQG;oBACR;gBACF;YACF;YACA,iCAAiC;YACjC,OAAO;QACT;QAEAN,mBAAmBE;QACnBH,oBAAoBI;QAEpB,OAAOA;IACT;IAEA,SAASQ,IAAIT,IAAqB,EAAEL,KAAQ;QAC1C,MAAMM,QAAQF,iBAAiBC;QAC/BC,MAAMP,QAAQ,GAAG;QACjBO,MAAMN,KAAK,GAAGA;IAChB;IAEA,SAASU,IAAIL,IAAqB;QAChC,MAAMC,QAAQS,iBAAiBV;QAC/B,IAAIC,UAAU,QAAQ,CAACA,MAAMP,QAAQ,EAAE;YACrC,OAAO;QACT;QACA,OAAOO,MAAMN,KAAK;IACpB;IAEA,SAASgB,YAAYX,IAAqB;QACxC,MAAMC,QAAQS,iBAAiBV;QAC/B,IAAIC,UAAU,QAAQ,CAACA,MAAMP,QAAQ,EAAE;YACrC;QACF;QAEA,2CAA2C;QAC3C,MAAMkB,eAA8BX;QACpCW,aAAalB,QAAQ,GAAG;QACxBkB,aAAajB,KAAK,GAAG;QAErB,6CAA6C;QAC7C,IAAIiB,aAAahB,GAAG,KAAK,MAAM;YAC7B,mEAAmE;YACnE,kEAAkE;YAClE,2DAA2D;YAE3D,wEAAwE;YACxE,4DAA4D;YAC5DC,oBAAoB;YACpBC,mBAAmB;YAEnB,IAAIN,SAASoB,aAAapB,MAAM;YAChC,IAAIC,MAAMmB,aAAanB,GAAG;YAC1B,MAAOD,WAAW,KAAM;gBACtB,MAAMqB,YAAYrB,OAAOI,GAAG;gBAC5B,IAAIiB,cAAc,MAAM;oBACtBA,UAAUC,MAAM,CAACrB;oBACjB,IAAIoB,UAAUE,IAAI,KAAK,GAAG;wBACxB,oDAAoD;wBACpDvB,OAAOI,GAAG,GAAG;wBACb,IAAIJ,OAAOG,KAAK,KAAK,MAAM;4BACzB,iEAAiE;4BACjE,sDAAsD;4BACtDF,MAAMD,OAAOC,GAAG;4BAChBD,SAASA,OAAOA,MAAM;4BACtB;wBACF;oBACF;gBACF;gBAEA;YACF;QACF;IACF;IAEA,OAAO;QACLiB;QACAJ;QACAS,QAAQH;IACV;AACF"}