{"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 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 usesLocaleCollation(\n  options: CompareOptions,\n): options is LocaleCompareOptions {\n  return (options.stringSort ?? DEFAULT_COMPARE_OPTIONS.stringSort) === `locale`\n}\n\n/**\n * Operations that indexes can support, imported from available comparison functions\n */\nexport const IndexOperation = comparisonFunctions\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 compareOptions: CompareOptions\n  private compiledIndexEvaluator: CompiledSingleRowExpression | undefined\n  /**\n   * Set by subclasses when constructed with a user-supplied comparator, whose\n   * ordering may not match the WHERE evaluator's relational operators.\n   */\n  protected hasCustomComparator = false\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 = DEFAULT_COMPARE_OPTIONS\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 indexUsesLocale = usesLocaleCollation(indexCompareOptions)\n    const requestedUsesLocale = usesLocaleCollation(compareOptions)\n\n    if (\n      indexCompareOptions.nulls !== compareOptions.nulls ||\n      indexUsesLocale !== requestedUsesLocale\n    ) {\n      return false\n    }\n\n    if (!indexUsesLocale || !requestedUsesLocale) {\n      return true\n    }\n\n    return (\n      canonicalizeLocale(indexCompareOptions.locale) ===\n        canonicalizeLocale(compareOptions.locale) &&\n      deepEquals(\n        normalizeLocaleOptions(indexCompareOptions.localeOptions),\n        normalizeLocaleOptions(compareOptions.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","deepEquals","compileSingleRowExpression"],"mappings":";;;;AAQA,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,oBACP,SACiC;AACjC,UAAQ,QAAQ,cAAcA,MAAAA,wBAAwB,gBAAgB;AACxE;AAsFO,MAAe,UAEY;AAAA,EAchC,YACE,IACA,YACA,MACA,SACA;AARF,SAAU,sBAAsB;AAChC,SAAQ,wCAAwB,IAAA;AAQ9B,SAAK,KAAK;AACV,SAAK,aAAa;AAClB,SAAK,iBAAiBA,MAAAA;AACtB,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,oBAAoB,mBAAmB;AAC/D,UAAM,sBAAsB,oBAAoB,cAAc;AAE9D,QACE,oBAAoB,UAAU,eAAe,SAC7C,oBAAoB,qBACpB;AACA,aAAO;AAAA,IACT;AAEA,QAAI,CAAC,mBAAmB,CAAC,qBAAqB;AAC5C,aAAO;AAAA,IACT;AAEA,WACE,mBAAmB,oBAAoB,MAAM,MAC3C,mBAAmB,eAAe,MAAM,KAC1CC,MAAAA;AAAAA,MACE,uBAAuB,oBAAoB,aAAa;AAAA,MACxD,uBAAuB,eAAe,aAAa;AAAA,IAAA;AAAA,EAGzD;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;;"}