{"version":3,"file":"base-index.cjs","sources":["../../../src/indexes/base-index.ts"],"sourcesContent":["import { compileSingleRowExpression } from '../query/compiler/evaluators.js'\nimport { comparisonFunctions } from '../query/builder/functions.js'\nimport { DEFAULT_COMPARE_OPTIONS, deepEquals } from '../utils.js'\nimport { makeCheckedComparator, makeComparator } from '../utils/comparison.js'\nimport type { CompiledSingleRowExpression } from '../query/compiler/evaluators.js'\nimport type { RangeQueryOptions } from './btree-index.js'\nimport type { CompareOptions } from '../query/builder/types.js'\nimport type { BasicExpression, OrderByDirection } from '../query/ir.js'\n\nfunction normalizeLocaleOptions(options: object | undefined): object {\n  return Object.fromEntries(\n    Object.entries(options ?? {}).filter(([, value]) => value !== undefined),\n  )\n}\n\nfunction canonicalizeLocale(locale: string | undefined): string | undefined {\n  return locale === undefined ? undefined : Intl.getCanonicalLocales(locale)[0]\n}\n\ntype LocaleCompareOptions = CompareOptions & {\n  stringSort: `locale`\n  locale?: string\n  localeOptions?: object\n}\n\nfunction resolveStringSort(\n  options: CompareOptions,\n): NonNullable<CompareOptions[`stringSort`]> {\n  return options.stringSort ?? DEFAULT_COMPARE_OPTIONS.stringSort!\n}\n\n/**\n * Operations that indexes can support, imported from available comparison functions\n */\nexport const IndexOperation = comparisonFunctions\n\nexport const builtInIndexResolverNames = new WeakMap<object, string>()\n\n/**\n * Type for index operation values\n */\nexport type IndexOperation = (typeof comparisonFunctions)[number]\n\n/** The read-side surface consumers use on a resolved (possibly reversed) index. */\nexport type IndexReader<TKey extends string | number = string | number> = Pick<\n  IndexInterface<TKey>,\n  | `lookup`\n  | `rangeQuery`\n  | `take`\n  | `takeFromStart`\n  | `keyCount`\n  | `supports`\n  | `supportsRangeOptimization`\n  | `canOptimizeRangeFor`\n>\n\nexport interface IndexInterface<\n  TKey extends string | number = string | number,\n> {\n  add: (key: TKey, item: any) => void\n  remove: (key: TKey, item: any) => void\n  update: (key: TKey, oldItem: any, newItem: any) => void\n\n  build: (entries: Iterable<[TKey, any]>) => void\n  clear: () => void\n\n  lookup: (operation: IndexOperation, value: any) => Set<TKey>\n\n  equalityLookup: (value: any) => Set<TKey>\n  inArrayLookup: (values: Array<any>) => Set<TKey>\n\n  rangeQuery: (options: RangeQueryOptions) => Set<TKey>\n  rangeQueryReversed: (options: RangeQueryOptions) => Set<TKey>\n\n  take: (\n    n: number,\n    from: unknown,\n    filterFn?: (key: TKey) => boolean,\n  ) => Array<TKey>\n  takeFromStart: (n: number, filterFn?: (key: TKey) => boolean) => Array<TKey>\n  takeReversed: (\n    n: number,\n    from: unknown,\n    filterFn?: (key: TKey) => boolean,\n  ) => Array<TKey>\n  takeReversedFromEnd: (\n    n: number,\n    filterFn?: (key: TKey) => boolean,\n  ) => Array<TKey>\n\n  get keyCount(): number\n  supports: (operation: IndexOperation) => boolean\n\n  /**\n   * Whether range lookups (gt/gte/lt/lte) on this index can be trusted to\n   * return every matching key. Range traversal relies on the index ordering, so\n   * it is unsafe when the index uses a custom comparator, whose order may not\n   * match the WHERE evaluator's relational operators. Callers must fall back to\n   * a full scan when this is `false`.\n   */\n  get supportsRangeOptimization(): boolean\n\n  /**\n   * Whether the live values in this index share the predicate operand's\n   * relational domain. Mixed domains can sort differently in the index and\n   * WHERE evaluator, which can make a range lookup omit matching rows.\n   */\n  canOptimizeRangeFor?: (value: unknown) => boolean\n\n  matchesField: (fieldPath: Array<string>) => boolean\n  matchesCompareOptions: (compareOptions: CompareOptions) => boolean\n  matchesDirection: (direction: OrderByDirection) => boolean\n}\n\n/**\n * Base abstract class that all index types extend\n */\nexport abstract class BaseIndex<\n  TKey extends string | number = string | number,\n> implements IndexInterface<TKey> {\n  public readonly id: number\n  public readonly name?: string\n  public readonly expression: BasicExpression\n  public abstract readonly supportedOperations: Set<IndexOperation>\n  protected readonly compareOptions: CompareOptions\n  /**\n   * Orders indexed values. Every result is checked, because a custom\n   * comparator or custom collation may be supplied by the user.\n   */\n  protected readonly compareFn: (a: any, b: any) => number\n  private compiledIndexEvaluator: CompiledSingleRowExpression | undefined\n  /**\n   * A user-supplied comparator's ordering may not match the WHERE evaluator's\n   * relational operators.\n   */\n  protected readonly hasCustomComparator: boolean\n  private rangeValueDomains = new Map<string, number>()\n\n  constructor(\n    id: number,\n    expression: BasicExpression,\n    name?: string,\n    options?: any,\n  ) {\n    this.id = id\n    this.expression = expression\n    this.compareOptions = options?.compareOptions ?? DEFAULT_COMPARE_OPTIONS\n    this.hasCustomComparator = options?.compareFn != null\n    this.compareFn = makeCheckedComparator(\n      options?.compareFn ?? makeComparator(this.compareOptions),\n    )\n    this.name = name\n    this.initialize(options)\n  }\n\n  // Abstract methods that each index type must implement\n  abstract add(key: TKey, item: any): void\n  abstract remove(key: TKey, item: any): void\n  abstract update(key: TKey, oldItem: any, newItem: any): void\n  abstract build(entries: Iterable<[TKey, any]>): void\n  abstract clear(): void\n  abstract lookup(operation: IndexOperation, value: any): Set<TKey>\n  abstract take(\n    n: number,\n    from: unknown,\n    filterFn?: (key: TKey) => boolean,\n  ): Array<TKey>\n  abstract takeFromStart(\n    n: number,\n    filterFn?: (key: TKey) => boolean,\n  ): Array<TKey>\n  abstract takeReversed(\n    n: number,\n    from: unknown,\n    filterFn?: (key: TKey) => boolean,\n  ): Array<TKey>\n  abstract takeReversedFromEnd(\n    n: number,\n    filterFn?: (key: TKey) => boolean,\n  ): Array<TKey>\n  abstract get keyCount(): number\n  abstract equalityLookup(value: any): Set<TKey>\n  abstract inArrayLookup(values: Array<any>): Set<TKey>\n  abstract rangeQuery(options: RangeQueryOptions): Set<TKey>\n\n  // Common methods\n  rangeQueryReversed(options: RangeQueryOptions = {}): Set<TKey> {\n    const { from, to, fromInclusive = true, toInclusive = true } = options\n    const reversed: RangeQueryOptions = {}\n    if (`to` in options) {\n      reversed.from = to\n      reversed.fromInclusive = toInclusive\n    }\n    if (`from` in options) {\n      reversed.to = from\n      reversed.toInclusive = fromInclusive\n    }\n    return this.rangeQuery(reversed)\n  }\n\n  supports(operation: IndexOperation): boolean {\n    return this.supportedOperations.has(operation)\n  }\n\n  get supportsRangeOptimization(): boolean {\n    return !this.hasCustomComparator\n  }\n\n  protected addRangeValue(value: unknown): void {\n    const domain = rangeValueDomain(value)\n    if (domain === undefined) return\n    this.rangeValueDomains.set(\n      domain,\n      (this.rangeValueDomains.get(domain) ?? 0) + 1,\n    )\n  }\n\n  protected removeRangeValue(value: unknown): void {\n    const domain = rangeValueDomain(value)\n    if (domain === undefined) return\n    const count = this.rangeValueDomains.get(domain)\n    if (count === undefined) return\n    if (count === 1) this.rangeValueDomains.delete(domain)\n    else this.rangeValueDomains.set(domain, count - 1)\n  }\n\n  protected clearRangeValues(): void {\n    this.rangeValueDomains.clear()\n  }\n\n  canOptimizeRangeFor(value: unknown): boolean {\n    const domain = rangeValueDomain(value)\n    if (domain === undefined) return true\n    if (!isNativeRangeDomain(domain)) return false\n    return (\n      this.rangeValueDomains.size === 0 ||\n      (this.rangeValueDomains.size === 1 && this.rangeValueDomains.has(domain))\n    )\n  }\n\n  matchesField(fieldPath: Array<string>): boolean {\n    return (\n      this.expression.type === `ref` &&\n      this.expression.path.length === fieldPath.length &&\n      this.expression.path.every((part, i) => part === fieldPath[i])\n    )\n  }\n\n  /**\n   * Checks if the compare options match the index's compare options.\n   * The direction is ignored because the index can be reversed if the direction is different.\n   */\n  matchesCompareOptions(compareOptions: CompareOptions): boolean {\n    const indexCompareOptions = this.compareOptions\n    const indexStringSort = resolveStringSort(indexCompareOptions)\n    const requestedStringSort = resolveStringSort(compareOptions)\n\n    if (\n      indexCompareOptions.nulls !== compareOptions.nulls ||\n      indexStringSort !== requestedStringSort\n    ) {\n      return false\n    }\n\n    if (indexStringSort === `custom` && requestedStringSort === `custom`) {\n      return (\n        indexCompareOptions.stringSort === `custom` &&\n        compareOptions.stringSort === `custom` &&\n        indexCompareOptions.compare === compareOptions.compare\n      )\n    }\n\n    if (indexStringSort !== `locale` || requestedStringSort !== `locale`) {\n      return true\n    }\n\n    const indexLocaleOptions = indexCompareOptions as LocaleCompareOptions\n    const requestedLocaleOptions = compareOptions as LocaleCompareOptions\n\n    return (\n      canonicalizeLocale(indexLocaleOptions.locale) ===\n        canonicalizeLocale(requestedLocaleOptions.locale) &&\n      deepEquals(\n        normalizeLocaleOptions(indexLocaleOptions.localeOptions),\n        normalizeLocaleOptions(requestedLocaleOptions.localeOptions),\n      )\n    )\n  }\n\n  /**\n   * Checks if the index matches the provided direction.\n   */\n  matchesDirection(direction: OrderByDirection): boolean {\n    return this.compareOptions.direction === direction\n  }\n\n  protected abstract initialize(options?: any): void\n\n  protected evaluateIndexExpression(item: any): any {\n    const evaluator = (this.compiledIndexEvaluator ??=\n      compileSingleRowExpression(this.expression))\n    return evaluator(item as Record<string, unknown>)\n  }\n}\n\nfunction rangeValueDomain(value: unknown): string | undefined {\n  if (value == null) return undefined\n  if (value instanceof Date) return `date`\n  return typeof value\n}\n\nfunction isNativeRangeDomain(domain: string): boolean {\n  return (\n    domain === `number` ||\n    domain === `bigint` ||\n    domain === `boolean` ||\n    domain === `string` ||\n    domain === `date`\n  )\n}\n\n/**\n * Type for index constructor\n */\nexport type IndexConstructor<TKey extends string | number = string | number> =\n  new (\n    id: number,\n    expression: BasicExpression,\n    name?: string,\n    options?: any,\n  ) => BaseIndex<TKey>\n"],"names":["DEFAULT_COMPARE_OPTIONS","makeCheckedComparator","makeComparator","deepEquals","compileSingleRowExpression"],"mappings":";;;;;AASA,SAAS,uBAAuB,SAAqC;AACnE,SAAO,OAAO;AAAA,IACZ,OAAO,QAAQ,WAAW,EAAE,EAAE,OAAO,CAAC,CAAA,EAAG,KAAK,MAAM,UAAU,MAAS;AAAA,EAAA;AAE3E;AAEA,SAAS,mBAAmB,QAAgD;AAC1E,SAAO,WAAW,SAAY,SAAY,KAAK,oBAAoB,MAAM,EAAE,CAAC;AAC9E;AAQA,SAAS,kBACP,SAC2C;AAC3C,SAAO,QAAQ,cAAcA,MAAAA,wBAAwB;AACvD;AAOO,MAAM,gDAAgC,QAAA;AAiFtC,MAAe,UAEY;AAAA,EAmBhC,YACE,IACA,YACA,MACA,SACA;AAPF,SAAQ,wCAAwB,IAAA;AAQ9B,SAAK,KAAK;AACV,SAAK,aAAa;AAClB,SAAK,iBAAiB,SAAS,kBAAkBA,MAAAA;AACjD,SAAK,sBAAsB,SAAS,aAAa;AACjD,SAAK,YAAYC,WAAAA;AAAAA,MACf,SAAS,aAAaC,0BAAe,KAAK,cAAc;AAAA,IAAA;AAE1D,SAAK,OAAO;AACZ,SAAK,WAAW,OAAO;AAAA,EACzB;AAAA;AAAA,EAiCA,mBAAmB,UAA6B,IAAe;AAC7D,UAAM,EAAE,MAAM,IAAI,gBAAgB,MAAM,cAAc,SAAS;AAC/D,UAAM,WAA8B,CAAA;AACpC,QAAI,QAAQ,SAAS;AACnB,eAAS,OAAO;AAChB,eAAS,gBAAgB;AAAA,IAC3B;AACA,QAAI,UAAU,SAAS;AACrB,eAAS,KAAK;AACd,eAAS,cAAc;AAAA,IACzB;AACA,WAAO,KAAK,WAAW,QAAQ;AAAA,EACjC;AAAA,EAEA,SAAS,WAAoC;AAC3C,WAAO,KAAK,oBAAoB,IAAI,SAAS;AAAA,EAC/C;AAAA,EAEA,IAAI,4BAAqC;AACvC,WAAO,CAAC,KAAK;AAAA,EACf;AAAA,EAEU,cAAc,OAAsB;AAC5C,UAAM,SAAS,iBAAiB,KAAK;AACrC,QAAI,WAAW,OAAW;AAC1B,SAAK,kBAAkB;AAAA,MACrB;AAAA,OACC,KAAK,kBAAkB,IAAI,MAAM,KAAK,KAAK;AAAA,IAAA;AAAA,EAEhD;AAAA,EAEU,iBAAiB,OAAsB;AAC/C,UAAM,SAAS,iBAAiB,KAAK;AACrC,QAAI,WAAW,OAAW;AAC1B,UAAM,QAAQ,KAAK,kBAAkB,IAAI,MAAM;AAC/C,QAAI,UAAU,OAAW;AACzB,QAAI,UAAU,EAAG,MAAK,kBAAkB,OAAO,MAAM;AAAA,QAChD,MAAK,kBAAkB,IAAI,QAAQ,QAAQ,CAAC;AAAA,EACnD;AAAA,EAEU,mBAAyB;AACjC,SAAK,kBAAkB,MAAA;AAAA,EACzB;AAAA,EAEA,oBAAoB,OAAyB;AAC3C,UAAM,SAAS,iBAAiB,KAAK;AACrC,QAAI,WAAW,OAAW,QAAO;AACjC,QAAI,CAAC,oBAAoB,MAAM,EAAG,QAAO;AACzC,WACE,KAAK,kBAAkB,SAAS,KAC/B,KAAK,kBAAkB,SAAS,KAAK,KAAK,kBAAkB,IAAI,MAAM;AAAA,EAE3E;AAAA,EAEA,aAAa,WAAmC;AAC9C,WACE,KAAK,WAAW,SAAS,SACzB,KAAK,WAAW,KAAK,WAAW,UAAU,UAC1C,KAAK,WAAW,KAAK,MAAM,CAAC,MAAM,MAAM,SAAS,UAAU,CAAC,CAAC;AAAA,EAEjE;AAAA;AAAA;AAAA;AAAA;AAAA,EAMA,sBAAsB,gBAAyC;AAC7D,UAAM,sBAAsB,KAAK;AACjC,UAAM,kBAAkB,kBAAkB,mBAAmB;AAC7D,UAAM,sBAAsB,kBAAkB,cAAc;AAE5D,QACE,oBAAoB,UAAU,eAAe,SAC7C,oBAAoB,qBACpB;AACA,aAAO;AAAA,IACT;AAEA,QAAI,oBAAoB,YAAY,wBAAwB,UAAU;AACpE,aACE,oBAAoB,eAAe,YACnC,eAAe,eAAe,YAC9B,oBAAoB,YAAY,eAAe;AAAA,IAEnD;AAEA,QAAI,oBAAoB,YAAY,wBAAwB,UAAU;AACpE,aAAO;AAAA,IACT;AAEA,UAAM,qBAAqB;AAC3B,UAAM,yBAAyB;AAE/B,WACE,mBAAmB,mBAAmB,MAAM,MAC1C,mBAAmB,uBAAuB,MAAM,KAClDC,MAAAA;AAAAA,MACE,uBAAuB,mBAAmB,aAAa;AAAA,MACvD,uBAAuB,uBAAuB,aAAa;AAAA,IAAA;AAAA,EAGjE;AAAA;AAAA;AAAA;AAAA,EAKA,iBAAiB,WAAsC;AACrD,WAAO,KAAK,eAAe,cAAc;AAAA,EAC3C;AAAA,EAIU,wBAAwB,MAAgB;AAChD,UAAM,YAAa,KAAK,2BACtBC,WAAAA,2BAA2B,KAAK,UAAU;AAC5C,WAAO,UAAU,IAA+B;AAAA,EAClD;AACF;AAEA,SAAS,iBAAiB,OAAoC;AAC5D,MAAI,SAAS,KAAM,QAAO;AAC1B,MAAI,iBAAiB,KAAM,QAAO;AAClC,SAAO,OAAO;AAChB;AAEA,SAAS,oBAAoB,QAAyB;AACpD,SACE,WAAW,YACX,WAAW,YACX,WAAW,aACX,WAAW,YACX,WAAW;AAEf;;;"}