query.ts

/**
 * Utilities for querying/filtering entries from a {@linkcode Deno.Kv} instance.
 *
 * @module
 */

import {
  keyPartToJSON,
  keyToJSON,
  type KvKeyJSON,
  type KvKeyPartJSON,
  type KvValueJSON,
  toKey,
  toKeyPart,
  toValue,
  valueToJSON,
} from "@deno/kv-utils/json";
import { equal } from "@std/assert/equal";
import { assert } from "@std/assert/assert";
import { timingSafeEqual } from "@std/crypto/timing-safe-equal";

import { type BlobMeta, list } from "./blob.ts";
import { keys, type KeyTree, tree, unique, uniqueCount, type UniqueCountElement } from "./keys.ts";

/**
 * Options which can be used when calling {@linkcode query}.
 */
export interface QueryOptions extends Deno.KvListOptions {
  /**
   * If `true`, only blob entries will be returned as a {@linkcode ReadableStream} of {@linkcode Uint8Array} chunks.
   */
  stream?: boolean;
  /**
   * If `true`, only blob entries will be returned as a {@linkcode Blob} or {@linkcode File}.
   */
  blob?: boolean;
  /**
   * If `true`, only blob entries will be returned as a {@linkcode Uint8Array}.
   */
  bytes?: boolean;
  /**
   * If `true`, only blob entries will be returned as a {@linkcode BlobMeta} object.
   */
  meta?: boolean;
}

/**
 * The supported operations for filtering entries.
 *
 * The following operations are supported:
 *
 * - `"<"` - less than
 * - `"<="` - less than or equal
 * - `"=="` - equal
 * - `">="` - greater than or equal
 * - `">"` - greater than
 * - `"!="` - not equal
 * - `"array-contains"` - array contains the value
 * - `"array-contains-any"` - array contains any of the values
 * - `"in"` - value is in the array of supplied values
 * - `"not-in"` - value is not in the array of supplied values
 * - `"matches"` - value matches the regular expression
 * - `"kind-of"` - value is of the specified kind
 */
export type Operation =
  | "<"
  | "<="
  | "=="
  | ">="
  | ">"
  | "!="
  | "array-contains"
  | "array-contains-any"
  | "in"
  | "not-in"
  | "matches"
  | "kind-of";

type Mappable = Record<string, unknown> | Map<string, unknown>;

/**
 * The different kinds of values that can be stored in a {@linkcode Deno.Kv}.
 */
export type Kinds = KvValueJSON["type"];

export interface QueryLike<T = unknown> {
  readonly selector: Deno.KvListSelector;
  get(): Deno.KvListIterator<T>;
}

/**
 * A representation of a {@linkcode Deno.KvListSelector} as a JSON object.
 */
export type KvListSelectorJSON =
  | { prefix: KvKeyJSON }
  | { prefix: KvKeyJSON; start: KvKeyJSON }
  | { prefix: KvKeyJSON; end: KvKeyJSON }
  | { start: KvKeyJSON; end: KvKeyJSON };

/**
 * A representation of an _and_ filter as a JSON object.
 */
export interface KvFilterAndJSON {
  kind: "and";
  filters: KvFilterJSON[];
}

/**
 * A representation of an _or_ filter as a JSON object.
 */
export interface KvFilterOrJSON {
  kind: "or";
  filters: KvFilterJSON[];
}

/**
 * A representation of a _where_ filter as a JSON object.
 */
export interface KvFilterWhereJSON {
  kind: "where";
  property: string | string[];
  operation: Operation;
  value: KvValueJSON;
}

/**
 * A representation of a _value_ filter as a JSON object.
 */
export interface KvFilterValueJSON {
  kind: "value";
  operation: Operation;
  value: KvValueJSON;
}

/**
 * A representation of a filter as a JSON object.
 */
export type KvFilterJSON =
  | KvFilterAndJSON
  | KvFilterOrJSON
  | KvFilterWhereJSON
  | KvFilterValueJSON;

/**
 * A representation of a query as a JSON object.
 */
export interface KvQueryJSON {
  selector: KvListSelectorJSON;
  options?: Deno.KvListOptions;
  filters: KvFilterJSON[];
  keyFilters?: KvKeyFilterJSON[];
}

/**
 * A sentinel value representing a wildcard position in a {@linkcode KeyGlob}.
 * Matches any single key part at a given position during key glob matching.
 *
 * @example
 *
 * ```ts
 * import { query, wildcard } from "@kitsonk/kv-toolbox/query";
 *
 * const db = await Deno.openKv();
 * const result = query(db, { prefix: [] })
 *   .keyGlob(["users", wildcard, "logs"])
 *   .get();
 * for await (const entry of result) {
 *   console.log(entry.key);
 * }
 * db.close();
 * ```
 */
export const wildcard: unique symbol = Symbol("kv-toolbox.key-wildcard");

/**
 * The type of the {@linkcode wildcard} sentinel.
 */
export type KeyWildcard = typeof wildcard;

/**
 * A single position in a {@linkcode KeyGlob}. Either a concrete
 * {@linkcode Deno.KvKeyPart} or the {@linkcode wildcard} sentinel.
 */
export type KeyGlobPart = Deno.KvKeyPart | KeyWildcard;

/**
 * A glob pattern for matching {@linkcode Deno.KvKey}s. An array of
 * {@linkcode KeyGlobPart} values where {@linkcode wildcard} matches any single
 * key part at that position. The glob must have exactly the same length as the
 * key it is matched against.
 *
 * @example
 *
 * ```ts
 * import { type KeyGlob, wildcard } from "@kitsonk/kv-toolbox/query";
 *
 * const pattern: KeyGlob = ["users", wildcard, "logs"];
 * ```
 */
export type KeyGlob = KeyGlobPart[];

/**
 * A JSON representation of a wildcard position in a key glob pattern.
 */
export interface KvKeyGlobWildcardJSON {
  type: "wildcard";
}

/**
 * A JSON representation of a single position in a {@linkcode KeyGlob}.
 */
export type KvKeyGlobPartJSON = KvKeyPartJSON | KvKeyGlobWildcardJSON;

/**
 * A JSON representation of a key glob filter.
 */
export interface KvKeyFilterGlobJSON {
  kind: "glob";
  pattern: KvKeyGlobPartJSON[];
}

/**
 * A JSON representation of a key includes filter.
 */
export interface KvKeyFilterIncludesJSON {
  kind: "includes";
  value: KvKeyPartJSON;
}

/**
 * A JSON representation of a {@linkcode KeyFilter}.
 */
export type KvKeyFilterJSON = KvKeyFilterGlobJSON | KvKeyFilterIncludesJSON;

function partEqualsKeyPart(a: Deno.KvKeyPart, b: Deno.KvKeyPart): boolean {
  if (ArrayBuffer.isView(a)) {
    if (!ArrayBuffer.isView(b)) return false;
    return timingSafeEqual(a as Uint8Array, b as Uint8Array);
  }
  return a === b;
}

function matchesKeyGlob(key: Deno.KvKey, pattern: KeyGlob): boolean {
  if (key.length !== pattern.length) return false;
  for (let i = 0; i < pattern.length; i++) {
    const part = pattern[i];
    if (part === wildcard) continue;
    if (!partEqualsKeyPart(key[i], part as Deno.KvKeyPart)) return false;
  }
  return true;
}

function getKind(value: unknown): Kinds {
  const type = typeof value;
  switch (type) {
    case "bigint":
    case "boolean":
    case "number":
    case "string":
    case "undefined":
      return type;
    case "object":
      if (Array.isArray(value)) {
        return "Array";
      }
      if (value instanceof DataView) {
        return "DataView";
      }
      if (ArrayBuffer.isView(value)) {
        if (value instanceof Int8Array) {
          return "Int8Array";
        }
        if (value instanceof Uint8Array) {
          return "Uint8Array";
        }
        if (value instanceof Uint8ClampedArray) {
          return "Uint8ClampedArray";
        }
        if (value instanceof Int16Array) {
          return "Int16Array";
        }
        if (value instanceof Uint16Array) {
          return "Uint16Array";
        }
        if (value instanceof Int32Array) {
          return "Int32Array";
        }
        if (value instanceof Uint32Array) {
          return "Uint32Array";
        }
        if (value instanceof Float32Array) {
          return "Float32Array";
        }
        if (value instanceof Float64Array) {
          return "Float64Array";
        }
        if (value instanceof BigInt64Array) {
          return "BigInt64Array";
        }
        if (value instanceof BigUint64Array) {
          return "BigUint64Array";
        }
      }
      if (value instanceof ArrayBuffer) {
        return "ArrayBuffer";
      }
      if (value instanceof Date) {
        return "Date";
      }
      if ("Deno" in globalThis && value instanceof Deno.KvU64) {
        return "KvU64";
      }
      if (value instanceof Error) {
        if (value instanceof EvalError) {
          return "EvalError";
        }
        if (value instanceof RangeError) {
          return "RangeError";
        }
        if (value instanceof ReferenceError) {
          return "ReferenceError";
        }
        if (value instanceof SyntaxError) {
          return "SyntaxError";
        }
        if (value instanceof TypeError) {
          return "TypeError";
        }
        if (value instanceof URIError) {
          return "URIError";
        }
        return "Error";
      }
      if (value instanceof Map) {
        return "Map";
      }
      if (value === null) {
        return "null";
      }
      if (value instanceof RegExp) {
        return "RegExp";
      }
      if (value instanceof Set) {
        return "Set";
      }
      return "object";
    default:
      return "undefined";
  }
}

function getValue(obj: Mappable, key: string): unknown {
  if (obj instanceof Map) {
    return obj.get(key);
  }
  return obj[key];
}

function hasProperty(obj: Mappable, key: string): boolean {
  if (obj instanceof Map) {
    return obj.has(key);
  }
  return key in obj;
}

function isOptionBlob(options: QueryOptions): boolean {
  return options.blob || options.stream || options.bytes || options.meta ||
    false;
}

function isMappable(value: unknown): value is Mappable {
  return typeof value === "object" && value !== null;
}

function selectorToJSON(selector: Deno.KvListSelector): KvListSelectorJSON {
  if ("prefix" in selector) {
    if ("start" in selector) {
      return {
        prefix: keyToJSON(selector.prefix),
        start: keyToJSON(selector.start),
      };
    }
    if ("end" in selector) {
      return {
        prefix: keyToJSON(selector.prefix),
        end: keyToJSON(selector.end),
      };
    }
    return { prefix: keyToJSON(selector.prefix) };
  }
  return { start: keyToJSON(selector.start), end: keyToJSON(selector.end) };
}

function toSelector(json: KvListSelectorJSON): Deno.KvListSelector {
  if ("prefix" in json) {
    if ("start" in json) {
      return {
        prefix: toKey(json.prefix),
        start: toKey(json.start),
      };
    }
    if ("end" in json) {
      return {
        prefix: toKey(json.prefix),
        end: toKey(json.end),
      };
    }
    return { prefix: toKey(json.prefix) };
  }
  return { start: toKey(json.start), end: toKey(json.end) };
}

/**
 * A representation of a property path to a value in an object. This is used to
 * be able to query/filter entries based on nested properties.
 *
 * @example
 *
 * ```ts
 * import { PropertyPath } from "@kitsonk/kv-toolbox/query";
 * import { assert } from "@std/assert/assert";
 *
 * const path = new PropertyPath("a", "b", "c");
 * assert(path.exists({ a: { b: { c: 1 } } }));
 * assert(!path.exists({ a: { b: { d: 1 } } }));
 * assert(path.value({ a: { b: { c: 1 } } }) === 1);
 * ```
 */
export class PropertyPath {
  #parts: string[];

  constructor(...parts: string[]) {
    this.#parts = parts;
  }

  /**
   * Returns `true` if the property path exists in the object.
   */
  exists(other: unknown): other is Mappable {
    let current = other;
    for (const part of this.#parts) {
      if (!isMappable(current)) {
        return false;
      }
      if (!hasProperty(current, part)) {
        return false;
      }
      current = getValue(current, part);
    }
    return true;
  }

  /**
   * Returns the value of the property represented by the path. If the property
   * does not exist, an error is thrown.
   */
  value(other: Mappable): unknown {
    // deno-lint-ignore no-explicit-any
    let current: any = other;
    for (const part of this.#parts) {
      if (!isMappable(current)) {
        throw new TypeError("Value is not mappable");
      }
      if (!hasProperty(current, part)) {
        throw new Error("Property does not exist");
      }
      current = getValue(current, part);
    }
    return current;
  }

  /**
   * Convert the property path to a JSON array.
   */
  toJSON(): string[] {
    return this.#parts;
  }

  /**
   * Create a property path from an array of parts.
   */
  static from(parts: string[]): PropertyPath {
    return new PropertyPath(...parts);
  }
}

// deno-lint-ignore no-explicit-any
function exec(other: any, operation: Operation, value: any | any[]): boolean {
  switch (operation) {
    case "<":
      return other < value;
    case "<=":
      return other <= value;
    case "!=":
      return !equal(other, value);
    case "==":
      return equal(other, value);
    case ">":
      return other > value;
    case ">=":
      return other >= value;
    case "array-contains":
      if (Array.isArray(other)) {
        return other.some((v) => equal(v, value));
      }
      return false;
    case "array-contains-any":
      if (Array.isArray(other) && Array.isArray(value)) {
        return other.some((v) => value.some((w) => equal(v, w)));
      }
      return false;
    case "in":
      if (Array.isArray(value)) {
        return value.some((v) => equal(other, v));
      }
      return false;
    case "not-in":
      if (Array.isArray(value)) {
        return !value.some((v) => equal(other, v));
      }
      break;
    case "matches":
      if (typeof other === "string" && value instanceof RegExp) {
        return value.test(other);
      }
      break;
    case "kind-of":
      return getKind(other) === value;
  }
  return false;
}

/**
 * A filter instance which can be used to filter entries based on a set of
 * conditions. Users should use the static methods to create instances of this
 * class.
 *
 * @example Creating a filter based on a property value
 *
 * ```ts
 * import { Filter } from "@kitsonk/kv-toolbox/query";
 * import { assert } from "@std/assert/assert";
 *
 * const filter = Filter.where("age", "<=", 10);
 * assert(filter.test({ age: 10 }));
 * assert(!filter.test({ age: 11 }));
 * ```
 *
 * @example Creating a filter based on a property value using a `PropertyPath`
 *
 * ```ts
 * import { Filter, PropertyPath } from "@kitsonk/kv-toolbox/query";
 * import { assert } from "@std/assert/assert";
 *
 * const filter = Filter.where(new PropertyPath("a", "b", "c"), "==", 1);
 * assert(filter.test({ a: { b: { c: 1 } } }));
 * assert(!filter.test({ a: { b: { c: 2 } } }));
 * assert(!filter.test({ a: { b: { d: 1 } } }));
 * ```
 *
 * @example Creating a filter based on an _or_ condition
 *
 * ```ts
 * import { Filter } from "@kitsonk/kv-toolbox/query";
 * import { assert } from "@std/assert/assert";
 *
 * const filter = Filter.or(
 *   Filter.where("age", "<", 10),
 *   Filter.where("age", ">", 20),
 * );
 * assert(filter.test({ age: 5 }));
 * assert(filter.test({ age: 25 }));
 * assert(!filter.test({ age: 15 }));
 * ```
 *
 * @example Creating a filter based on an _and_ condition
 *
 * ```ts
 * import { Filter } from "@kitsonk/kv-toolbox/query";
 * import { assert } from "@std/assert/assert";
 *
 * const filter = Filter.and(
 *  Filter.where("age", ">", 10),
 *  Filter.where("age", "<", 20),
 * );
 * assert(filter.test({ age: 15 }));
 * assert(!filter.test({ age: 10 }));
 * assert(!filter.test({ age: 20 }));
 * ```
 */
export class Filter {
  #kind: "and" | "or" | "value" | "where";
  #property?: string | PropertyPath;
  #filters: Filter[];
  #operation?: Operation;
  #value?: unknown | unknown[];

  private constructor(kind: "and" | "or", filters: Filter[]);
  private constructor(
    kind: "where",
    filters: undefined,
    property: string | PropertyPath,
    operation: Operation,
    value: unknown | unknown[],
  );
  private constructor(
    kind: "value",
    filters: undefined,
    property: undefined,
    operation: Operation,
    value: unknown | unknown[],
  );
  private constructor(
    kind: "and" | "or" | "value" | "where",
    filters: Filter[] = [],
    property?: string | PropertyPath,
    operation?: Operation,
    value?: unknown | unknown[],
  ) {
    this.#kind = kind;
    this.#filters = filters;
    this.#property = property;
    this.#operation = operation;
    this.#value = value;
  }

  /**
   * Test the value against the filter.
   */
  test(value: unknown): boolean {
    switch (this.#kind) {
      case "and":
        return this.#filters.every((f) => f.test(value));
      case "or":
        return this.#filters.some((f) => f.test(value));
      case "where":
        assert(this.#property);
        assert(this.#operation);
        if (this.#property instanceof PropertyPath) {
          if (this.#property.exists(value)) {
            const propValue = this.#property.value(value);
            return exec(propValue, this.#operation, this.#value);
          }
          return false;
        }
        if (isMappable(value)) {
          if (hasProperty(value, this.#property)) {
            const propValue = getValue(value, this.#property);
            return exec(propValue, this.#operation, this.#value);
          }
          return false;
        }
        return false;
      case "value":
        assert(this.#operation);
        return exec(value, this.#operation, this.#value);
    }
    throw new TypeError("Invalid filter kind");
  }

  /**
   * Convert the filter to a JSON object.
   */
  toJSON(): KvFilterJSON {
    switch (this.#kind) {
      case "and":
        return {
          kind: "and",
          filters: this.#filters.map((f) => f.toJSON()),
        };
      case "or":
        return {
          kind: "or",
          filters: this.#filters.map((f) => f.toJSON()),
        };
      case "where":
        assert(this.#property);
        assert(this.#operation);
        return {
          kind: "where",
          property: this.#property instanceof PropertyPath ? this.#property.toJSON() : this.#property,
          operation: this.#operation,
          value: valueToJSON(this.#value),
        };
      case "value":
        assert(this.#operation);
        return {
          kind: "value",
          operation: this.#operation,
          value: valueToJSON(this.#value),
        };
    }
  }

  /**
   * Create a filter which will return `true` if all the filters return `true`.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.and(
   *   Filter.where("age", ">", 10),
   *   Filter.where("age", "<", 20),
   * );
   * assert(filter.test({ age: 15 }));
   * assert(!filter.test({ age: 10 }));
   * assert(!filter.test({ age: 20 }));
   * ```
   */
  static and(...filters: Filter[]): Filter {
    return new Filter("and", filters);
  }

  /**
   * Create a filter which will return `true` if any of the filters return
   * `true`.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.or(
   *   Filter.where("age", "<", 10),
   *   Filter.where("age", ">", 20),
   * );
   * assert(filter.test({ age: 5 }));
   * assert(filter.test({ age: 25 }));
   * assert(!filter.test({ age: 15 }));
   * ```
   */
  static or(...filters: Filter[]): Filter {
    return new Filter("or", filters);
  }

  /**
   * Create a filter which will return `true` if the value matches the
   * operation and value.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.value("==", 10);
   * assert(filter.test(10));
   * assert(!filter.test(11));
   * ```
   */
  static value(operation: "kind-of", value: Kinds): Filter;
  /**
   * Create a filter which will return `true` if the value matches the
   * operation and value.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.value("==", 10);
   * assert(filter.test(10));
   * assert(!filter.test(11));
   * ```
   */
  static value(operation: "matches", value: RegExp): Filter;
  /**
   * Create a filter which will return `true` if the value matches the
   * operation and value.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.value("==", 10);
   * assert(filter.test(10));
   * assert(!filter.test(11));
   * ```
   */
  static value(
    operation: "in" | "not-in" | "array-contains-any",
    value: unknown[],
  ): Filter;
  /**
   * Create a filter which will return `true` if the value matches the
   * operation and value.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.value("==", 10);
   * assert(filter.test(10));
   * assert(!filter.test(11));
   * ```
   */
  static value(operation: Operation, value: unknown): Filter;
  static value(operation: Operation, value: unknown | unknown[]): Filter {
    return new Filter("value", undefined, undefined, operation, value);
  }

  /**
   * Create a filter which will return `true` if the value of the property
   * matches the operation and value.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.where("age", "<=", 10);
   * assert(filter.test({ age: 10 }));
   * assert(!filter.test({ age: 11 }));
   * ```
   */
  static where(
    property: string | PropertyPath,
    operation: "kind-of",
    value: Kinds,
  ): Filter;
  /**
   * Create a filter which will return `true` if the value of the property
   * matches the operation and value.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.where("age", "<=", 10);
   * assert(filter.test({ age: 10 }));
   * assert(!filter.test({ age: 11 }));
   * ```
   */
  static where(
    property: string | PropertyPath,
    operation: "matches",
    value: RegExp,
  ): Filter;
  /**
   * Create a filter which will return `true` if the value of the property
   * matches the operation and value.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.where("age", "<=", 10);
   * assert(filter.test({ age: 10 }));
   * assert(!filter.test({ age: 11 }));
   * ```
   */
  static where(
    property: string | PropertyPath,
    operation: "in" | "not-in" | "array-contains-any",
    value: unknown[],
  ): Filter;
  /**
   * Create a filter which will return `true` if the value of the property
   * matches the operation and value.
   *
   * @example
   *
   * ```ts
   * import { Filter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = Filter.where("age", "<=", 10);
   * assert(filter.test({ age: 10 }));
   * assert(!filter.test({ age: 11 }));
   * ```
   */
  static where(
    property: string | PropertyPath,
    operation: Operation,
    value: unknown,
  ): Filter;
  static where(
    property: string | PropertyPath,
    operation: Operation,
    value: unknown | unknown[],
  ): Filter {
    return new Filter("where", undefined, property, operation, value);
  }

  /**
   * Parse a filter from a JSON object.
   */
  static parse(json: KvFilterJSON): Filter {
    switch (json.kind) {
      case "and":
        return Filter.and(...json.filters.map(Filter.parse));
      case "or":
        return Filter.or(...json.filters.map(Filter.parse));
      case "where":
        return Filter.where(
          Array.isArray(json.property) ? PropertyPath.from(json.property) : json.property,
          json.operation,
          toValue(json.value),
        );
      case "value":
        return Filter.value(json.operation, toValue(json.value));
    }
  }
}

/**
 * A filter instance which tests a {@linkcode Deno.KvKey} rather than an entry
 * value. Parallel to {@linkcode Filter} but operates on `entry.key`.
 *
 * @example Matching keys by glob pattern
 *
 * ```ts
 * import { KeyFilter, wildcard } from "@kitsonk/kv-toolbox/query";
 * import { assert } from "@std/assert/assert";
 *
 * const filter = KeyFilter.glob(["users", wildcard, "logs"]);
 * assert(filter.test(["users", "alice", "logs"]));
 * assert(!filter.test(["users", "alice", "sessions"]));
 * assert(!filter.test(["users", "logs"]));
 * ```
 *
 * @example Matching keys that include a specific part
 *
 * ```ts
 * import { KeyFilter } from "@kitsonk/kv-toolbox/query";
 * import { assert } from "@std/assert/assert";
 *
 * const filter = KeyFilter.includes("logs");
 * assert(filter.test(["users", "alice", "logs"]));
 * assert(filter.test(["logs"]));
 * assert(!filter.test(["users", "alice", "sessions"]));
 * ```
 */
export class KeyFilter {
  #kind: "glob" | "includes";
  #pattern?: KeyGlob;
  #value?: Deno.KvKeyPart;

  private constructor(kind: "glob", pattern: KeyGlob);
  private constructor(kind: "includes", value: Deno.KvKeyPart);
  private constructor(kind: "glob" | "includes", patternOrValue?: KeyGlob | Deno.KvKeyPart) {
    this.#kind = kind;
    if (kind === "glob") {
      this.#pattern = patternOrValue as KeyGlob;
    } else {
      this.#value = patternOrValue as Deno.KvKeyPart;
    }
  }

  /**
   * Test the key against this filter.
   */
  test(key: Deno.KvKey): boolean {
    switch (this.#kind) {
      case "glob":
        return matchesKeyGlob(key, this.#pattern!);
      case "includes":
        return key.some((part) => partEqualsKeyPart(part, this.#value!));
    }
  }

  /**
   * Convert the filter to a JSON object.
   */
  toJSON(): KvKeyFilterJSON {
    switch (this.#kind) {
      case "glob":
        return {
          kind: "glob",
          pattern: this.#pattern!.map((part): KvKeyGlobPartJSON =>
            part === wildcard ? { type: "wildcard" } : keyPartToJSON(part as Deno.KvKeyPart)
          ),
        };
      case "includes":
        return {
          kind: "includes",
          value: keyPartToJSON(this.#value!),
        };
    }
  }

  /**
   * Create a key filter that matches keys whose structure matches the given
   * glob pattern. Use {@linkcode wildcard} at any position to match any key
   * part there. The pattern length must equal the key length to match.
   *
   * @example
   *
   * ```ts
   * import { KeyFilter, wildcard } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = KeyFilter.glob(["users", wildcard, "logs"]);
   * assert(filter.test(["users", "alice", "logs"]));
   * assert(!filter.test(["users", "alice", "sessions"]));
   * ```
   */
  static glob(pattern: KeyGlob): KeyFilter {
    return new KeyFilter("glob", pattern);
  }

  /**
   * Create a key filter that matches keys containing the given key part at any
   * position.
   *
   * @example
   *
   * ```ts
   * import { KeyFilter } from "@kitsonk/kv-toolbox/query";
   * import { assert } from "@std/assert/assert";
   *
   * const filter = KeyFilter.includes("logs");
   * assert(filter.test(["users", "alice", "logs"]));
   * assert(!filter.test(["users", "alice", "sessions"]));
   * ```
   */
  static includes(value: Deno.KvKeyPart): KeyFilter {
    return new KeyFilter("includes", value);
  }

  /**
   * Parse a key filter from its JSON representation.
   */
  static parse(json: KvKeyFilterJSON): KeyFilter {
    switch (json.kind) {
      case "glob":
        return KeyFilter.glob(
          json.pattern.map((part) =>
            "type" in part && part.type === "wildcard" ? wildcard : toKeyPart(part as KvKeyPartJSON)
          ),
        );
      case "includes":
        return KeyFilter.includes(toKeyPart(json.value));
    }
  }
}

const AsyncIterator = Object.getPrototypeOf(async function* () {}).constructor;

class QueryListIterator<T = unknown> extends AsyncIterator implements Deno.KvListIterator<T> {
  #iterator: Deno.KvListIterator<T>;
  #count = 0;
  #cursor?: string;
  #limit?: number;
  #query: Filter[];
  #keyQuery: KeyFilter[];

  get cursor(): string {
    if (!this.#cursor) {
      throw new Error("Cannot get cursor before first iteration");
    }
    return this.#cursor;
  }

  constructor(
    iterator: Deno.KvListIterator<T>,
    query: Filter[],
    limit?: number,
    keyFilters: KeyFilter[] = [],
  ) {
    super();
    this.#iterator = iterator;
    this.#query = query;
    this.#limit = limit;
    this.#keyQuery = keyFilters;
  }

  async next(): Promise<IteratorResult<Deno.KvEntry<T>, undefined>> {
    for await (const entry of this.#iterator) {
      if (!this.#keyQuery.every((f) => f.test(entry.key))) continue;
      if (this.#query.every((f) => f.test(entry.value))) {
        this.#count++;
        if (this.#limit && this.#count > this.#limit) {
          return { value: undefined, done: true };
        }
        this.#cursor = this.#iterator.cursor;
        return { value: entry, done: false };
      }
    }
    return { value: undefined, done: true };
  }

  [Symbol.asyncIterator](): AsyncIterableIterator<Deno.KvEntry<T>> {
    return this;
  }
}

/**
 * Query instance for filtering entries from a {@linkcode Deno.Kv} instance.
 */
export class Query<T = unknown> implements QueryLike<T> {
  #kv: Deno.Kv;
  #limit?: number;
  #selector: Deno.KvListSelector;
  #options: QueryOptions;
  #query: Filter[] = [];
  #keyQuery: KeyFilter[] = [];

  /**
   * The selector that is used to query the entries.
   */
  get selector(): Deno.KvListSelector {
    return { ...this.#selector };
  }

  constructor(
    kv: Deno.Kv,
    selector: Deno.KvListSelector,
    options: QueryOptions = {},
  ) {
    this.#kv = kv;
    this.#selector = selector;
    const { limit, ...rest } = options;
    this.#limit = limit;
    this.#options = rest;
  }

  /**
   * Resolves with an array of unique sub keys/prefixes for the provided prefix
   * along with the number of sub keys that match that prefix. The `count`
   * represents the number of sub keys, a value of `0` indicates that only the
   * exact key exists with no sub keys.
   *
   * This is useful when storing keys and values in a hierarchical/tree view,
   * where you are retrieving a list including counts and you want to know all
   * the unique _descendants_ of a key in order to be able to enumerate them.
   *
   * @example
   *
   * If you had the following keys stored in a datastore and the query matched
   * the keys:
   *
   * ```
   * ["a", "b"]
   * ["a", "b", "c"]
   * ["a", "d", "e"]
   * ["a", "d", "f"]
   * ```
   *
   * And you would get the following results when using `.counts()`:
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const kv = await Deno.openKv();
   * console.log(await query(kv, { prefix: ["a"] }).counts());
   * // { key: ["a", "b"], count: 1 }
   * // { key: ["a", "d"], count: 2 }
   * await kv.close();
   * ```
   */
  counts(): Promise<UniqueCountElement[]> {
    return uniqueCount(this);
  }

  /**
   * Get the entries that match the query conditions.
   */
  get(): Deno.KvListIterator<T> {
    const iterator =
      (isOptionBlob(this.#options)
        ? list(this.#kv, this.#selector, this.#options)
        : this.#kv.list<T>(this.#selector, this.#options)) as Deno.KvListIterator<T>;
    return new QueryListIterator<T>(iterator, this.#query, this.#limit, this.#keyQuery);
  }

  /**
   * Add a key glob filter to the query. Only entries whose keys match the given
   * glob pattern will be returned. Multiple calls are ANDed together.
   *
   * Use {@linkcode wildcard} at any position to match any key part there. The
   * pattern length must match the key length exactly.
   *
   * @example
   *
   * ```ts
   * import { query, wildcard } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * // Returns all entries where key is ["users", <any>, "logs"]
   * const result = query(db, { prefix: [] })
   *   .keyGlob(["users", wildcard, "logs"])
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry.key);
   * }
   * db.close();
   * ```
   */
  keyGlob(pattern: KeyGlob): this {
    this.#keyQuery.push(KeyFilter.glob(pattern));
    return this;
  }

  /**
   * Add a key includes filter to the query. Only entries whose keys contain the
   * given key part at any position will be returned. Multiple calls are ANDed.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * // Returns all entries whose key contains "logs" at any position
   * const result = query(db, { prefix: [] })
   *   .keyIncludes("logs")
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry.key);
   * }
   * db.close();
   * ```
   */
  keyIncludes(value: Deno.KvKeyPart): this {
    this.#keyQuery.push(KeyFilter.includes(value));
    return this;
  }

  /**
   * Set the limit of the number of entries to return.
   *
   * This will override any limit that may have been set in the options.
   */
  limit(limit: number): this {
    this.#limit = limit;
    return this;
  }

  /**
   * Return an array of keys that match the query.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const kv = await Deno.openKv();
   * console.log(await query(kv, { prefix: ["hello"] }).keys());
   * await kv.close();
   * ```
   */
  keys(): Promise<Deno.KvKey[]> {
    return keys(this);
  }

  /**
   * Query a Deno KV store for keys and resolve with any matching keys
   * organized into a tree structure.
   *
   * Each child node indicates if it also has a value and any children of that
   * node.
   *
   * @example
   *
   * If you had the following keys stored in a datastore and the query matched
   * the values of all the entries:
   *
   * ```
   * ["a", "b"]
   * ["a", "b", "c"]
   * ["a", "d", "e"]
   * ["a", "d", "f"]
   * ```
   *
   * And you would get the following results when using `.tree()`:
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const kv = await Deno.openKv();
   * console.log(await query(kv, { prefix: ["a"] }).tree());
   * // {
   * //   prefix: ["a"],
   * //   children: [
   * //     {
   * //       part: "b",
   * //       hasValue: true,
   * //       children: [{ part: "c", hasValue: true }]
   * //     }, {
   * //       part: "d",
   * //       children: [
   * //         { part: "e", hasValue: true },
   * //         { part: "f", hasValue: true }
   * //       ]
   * //     }
   * //   ]
   * // }
   * await kv.close();
   * ```
   */
  tree(): Promise<KeyTree> {
    return tree(this);
  }

  /**
   * Resolves with an array of unique sub keys/prefixes for the matched query.
   *
   * This is useful when storing keys and values in a hierarchical/tree view,
   * where you are retrieving a list and you want to know all the unique
   * _descendants_ of a key in order to be able to enumerate them.
   *
   * @example
   *
   * The following keys stored in a datastore that matched the query:
   *
   * ```
   * ["a", "b"]
   * ["a", "b", "c"]
   * ["a", "d", "e"]
   * ["a", "d", "f"]
   * ```
   *
   * The following results when using `.unique()`:
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const kv = await Deno.openKv();
   * console.log(await query(kv, { prefix: ["a"] }).unique());
   * // ["a", "b"]
   * // ["a", "d"]
   * await kv.close();
   * ```
   */
  unique(): Promise<Deno.KvKey[]> {
    return unique(this);
  }

  /**
   * Add a filter to the query where the value of the entry matches the
   * operation and value.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .value("==", { age: 10 })
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  value(operation: "kind-of", value: Kinds): this;
  /**
   * Add a filter to the query where the value of the entry matches the
   * operation and value.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .value("==", { age: 10 })
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  value(operation: "matches", value: RegExp): this;
  /**
   * Add a filter to the query where the value of the entry matches the
   * operation and value.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .value("==", { age: 10 })
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  value(
    operation: "in" | "not-in" | "array-contains-any",
    value: unknown[],
  ): this;
  /**
   * Add a filter to the query where the value of the entry matches the
   * operation and value.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .value("==", { age: 10 })
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  value(operation: Operation, value: unknown): this;
  value(operation: Operation, value: unknown | unknown[]): this {
    this.#query.push(Filter.value(operation, value));
    return this;
  }

  /**
   * Add a filter to the query. Only entries which values match all the filters
   * will be returned.
   *
   * @example
   *
   * ```ts
   * import { query, Filter } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .where(Filter.and(
   *      Filter.where("age", ">", 10),
   *      Filter.where("age", "<", 20),
   *   ))
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  where(filter: Filter): this;
  /**
   * Add a property filter to the query. Only entries which values match the
   * filter will be returned.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .where("age", "<=", 10)
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  where(
    property: string | PropertyPath,
    operation: "kind-of",
    value: Kinds,
  ): this;
  /**
   * Add a property filter to the query. Only entries which values match the
   * filter will be returned.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .where("age", "<=", 10)
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  where(
    property: string | PropertyPath,
    operation: "matches",
    value: RegExp,
  ): this;
  /**
   * Add a property filter to the query. Only entries which values match the
   * filter will be returned.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .where("age", "<=", 10)
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  where(
    property: string | PropertyPath,
    operation: "in" | "not-in" | "array-contains-any",
    value: unknown[],
  ): this;
  /**
   * Add a property filter to the query. Only entries which values match the
   * filter will be returned.
   *
   * @example
   *
   * ```ts
   * import { query } from "@kitsonk/kv-toolbox/query";
   *
   * const db = await Deno.openKv();
   * const result = query(db, { prefix: [] })
   *   .where("age", "<=", 10)
   *   .get();
   * for await (const entry of result) {
   *   console.log(entry);
   * }
   * db.close();
   * ```
   */
  where(
    property: string | PropertyPath,
    operation: Operation,
    value: unknown,
  ): this;
  where(
    propertyOrFilter: Filter | string | PropertyPath,
    operation?: Operation,
    value?: unknown | unknown[],
  ): this {
    if (propertyOrFilter instanceof Filter) {
      this.#query.push(propertyOrFilter);
    } else {
      assert(operation, "Operation is required");
      this.#query.push(Filter.where(propertyOrFilter, operation, value));
    }
    return this;
  }

  /**
   * Convert the query to a JSON object.
   */
  toJSON(): KvQueryJSON {
    const json: KvQueryJSON = {
      selector: selectorToJSON(this.#selector),
      options: this.#options,
      filters: this.#query.map((f) => f.toJSON()),
    };
    if (this.#keyQuery.length > 0) {
      json.keyFilters = this.#keyQuery.map((f) => f.toJSON());
    }
    return json;
  }

  /**
   * Parse a query from an instance of {@linkcode Deno.Kv} and a JSON object.
   */
  static parse<T = unknown>(kv: Deno.Kv, json: KvQueryJSON): Query<T> {
    const q = new Query<T>(kv, toSelector(json.selector), json.options);
    q.#query = json.filters.map(Filter.parse);
    q.#keyQuery = (json.keyFilters ?? []).map(KeyFilter.parse);
    return q;
  }
}

/**
 * Query/filter entries from a {@linkcode Deno.Kv} instance.
 *
 * The query instance can be used to filter entries based on a set of
 * conditions. Then the filtered entries can be retrieved using the `.get()`
 * method, which returns an async iterator that will yield the entries that
 * match the conditions.
 *
 * At a base level a query works like the `Deno.Kv.prototype.list()` method, but
 * with the added ability to filter entries based on the query conditions.
 *
 * @example Querying blob entries as `ReadableStream<Uint8Array>` values
 *
 * ```ts
 * import { query } from "@kitsonk/kv-toolbox/query";
 * const db = await Deno.openKv();
 * const result = query(db, { prefix: [] }, { stream: true })
 *   .get();
 * for await (const entry of result) {
 *   console.log(entry);
 * }
 * db.close();
 * ```
 *
 * @template T the type of the value stored in the {@linkcode Deno.Kv} instance
 * @param kv the target {@linkcode Deno.Kv} instance
 * @param selector the selector to use for selecting entries
 * @param options
 * @returns
 */
export function query(
  kv: Deno.Kv,
  selector: Deno.KvListSelector,
  options: QueryOptions & { stream: true },
): Query<ReadableStream<Uint8Array>>;
/**
 * Query/filter entries from a {@linkcode Deno.Kv} instance.
 *
 * The query instance can be used to filter entries based on a set of
 * conditions. Then the filtered entries can be retrieved using the `.get()`
 * method, which returns an async iterator that will yield the entries that
 * match the conditions.
 *
 * At a base level a query works like the `Deno.Kv.prototype.list()` method, but
 * with the added ability to filter entries based on the query conditions.
 *
 * @example Querying blob entries as `Blob` or `File` values
 *
 * ```ts
 * import { query } from "@kitsonk/kv-toolbox/query";
 * const db = await Deno.openKv();
 * const result = query(db, { prefix: [] }, { blob: true })
 *   .get();
 * for await (const entry of result) {
 *   console.log(entry);
 * }
 * db.close();
 * ```
 *
 * @template T the type of the value stored in the {@linkcode Deno.Kv} instance
 * @param kv the target {@linkcode Deno.Kv} instance
 * @param selector the selector to use for selecting entries
 * @param options
 * @returns
 */
export function query(
  kv: Deno.Kv,
  selector: Deno.KvListSelector,
  options: QueryOptions & { blob: true },
): Query<Blob | File>;
/**
 * Query/filter entries from a {@linkcode Deno.Kv} instance.
 *
 * The query instance can be used to filter entries based on a set of
 * conditions. Then the filtered entries can be retrieved using the `.get()`
 * method, which returns an async iterator that will yield the entries that
 * match the conditions.
 *
 * At a base level a query works like the `Deno.Kv.prototype.list()` method, but
 * with the added ability to filter entries based on the query conditions.
 *
 * @example Querying blob entries as `Uint8Array` values
 *
 * ```ts
 * import { query } from "@kitsonk/kv-toolbox/query";
 * const db = await Deno.openKv();
 * const result = query(db, { prefix: [] }, { bytes: true })
 *   .get();
 * for await (const entry of result) {
 *   console.log(entry);
 * }
 * db.close();
 * ```
 *
 * @template T the type of the value stored in the {@linkcode Deno.Kv} instance
 * @param kv the target {@linkcode Deno.Kv} instance
 * @param selector the selector to use for selecting entries
 * @param options
 * @returns
 */
export function query(
  kv: Deno.Kv,
  selector: Deno.KvListSelector,
  options: QueryOptions & { bytes: true },
): Query<Uint8Array>;
/**
 * Query/filter entries from a {@linkcode Deno.Kv} instance.
 *
 * The query instance can be used to filter entries based on a set of
 * conditions. Then the filtered entries can be retrieved using the `.get()`
 * method, which returns an async iterator that will yield the entries that
 * match the conditions.
 *
 * At a base level a query works like the `Deno.Kv.prototype.list()` method, but
 * with the added ability to filter entries based on the query conditions.
 *
 * @example Querying blob entries as `BlobMeta` values
 *
 * ```ts
 * import { query } from "@kitsonk/kv-toolbox/query";
 * const db = await Deno.openKv();
 * const result = query(db, { prefix: [] }, { meta: true })
 *   .get();
 * for await (const entry of result) {
 *   console.log(entry);
 * }
 * db.close();
 * ```
 *
 * @template T the type of the value stored in the {@linkcode Deno.Kv} instance
 * @param kv the target {@linkcode Deno.Kv} instance
 * @param selector the selector to use for selecting entries
 * @param options
 * @returns
 */
export function query(
  kv: Deno.Kv,
  selector: Deno.KvListSelector,
  options: QueryOptions & { meta: true },
): Query<BlobMeta>;
/**
 * Query/filter entries from a {@linkcode Deno.Kv} instance.
 *
 * The query instance can be used to filter entries based on a set of
 * conditions. Then the filtered entries can be retrieved using the `.get()`
 * method, which returns an async iterator that will yield the entries that
 * match the conditions.
 *
 * At a base level a query works like the `Deno.Kv.prototype.list()` method, but
 * with the added ability to filter entries based on the query conditions.
 *
 * @example Filtering entries based on a property value
 *
 * ```ts
 * import { query } from "@kitsonk/kv-toolbox/query";
 * const db = await Deno.openKv();
 * const result = query(db, { prefix: [] })
 *   .where("age", "<=", 10)
 *   .get();
 * for await (const entry of result) {
 *   console.log(entry);
 * }
 * db.close();
 * ```
 *
 * @example Filtering entries based on a property value using a `PropertyPath`
 *
 * ```ts
 * import { query, PropertyPath } from "@kitsonk/kv-toolbox/query";
 *
 * const db = await Deno.openKv();
 * const result = query(db, { prefix: [] })
 *   // matches { a: { b: { c: 1 } } }
 *   .where(new PropertyPath("a", "b", "c"), "==", 1)
 *   .get();
 * for await (const entry of result) {
 *   console.log(entry);
 * }
 * db.close();
 * ```
 *
 * @example Filtering entries based on an _or_ condition
 *
 * ```ts
 * import { query, Filter } from "@kitsonk/kv-toolbox/query";
 *
 * const db = await Deno.openKv();
 * const result = query(db, { prefix: [] })
 *   .where(Filter.or(
 *     Filter.where("age", "<", 10),
 *     Filter.where("age", ">", 20),
 *   ))
 *   .get();
 * for await (const entry of result) {
 *   console.log(entry);
 * }
 * db.close();
 * ```
 *
 * @template T the type of the value stored in the {@linkcode Deno.Kv} instance
 * @param kv the target {@linkcode Deno.Kv} instance
 * @param selector the selector to use for selecting entries
 * @param options
 * @returns
 */
export function query<T = unknown>(kv: Deno.Kv, selector: Deno.KvListSelector, options?: QueryOptions): Query<T>;
export function query<T = unknown>(kv: Deno.Kv, selector: Deno.KvListSelector, options: QueryOptions = {}): Query<T> {
  return new Query(kv, selector, options);
}