// Composite-search query tree.
//
// The tree is the user's full search expression: a root GroupNode (AND by
// default) containing LeafNodes (single search terms) and nested GroupNodes
// (sub-expressions). The eval engine in `searchEval.ts` walks this tree and
// returns the matching slug set + per-leaf hits.
//
// Serialization here is the source of truth for both the URL (`qt=` param)
// and IndexedDB-backed layer cache keys. Keep field names short — they end
// up in URLs.

// Which corpus the legacy single-input search targets. "posts" is the social
// corpus (lib/posts.ts); the composite query tree can mix all of them freely,
// this only decides what a bare `?q=` URL means.
//
// Defined here rather than in `components/urlState.ts` (which re-exports it)
// because `buildSearchRoot` below turns one into a query tree — the model owns
// the vocabulary it interprets.
export type SearchMode = "transcripts" | "subs" | "posts";

export type LayerScope =
  | "transcripts"
  | "chat"
  // The social-post corpus (common/lib/posts.ts). A parallel content layer, so
  // it composes into the SAME boolean tree as transcripts — which is what makes
  // `(transcripts:"foo" OR posts:"foo")` a single unified search.
  | "posts"
  | "metadata"
  | "description"
  | "tags";

export type GroupOp = "AND" | "OR";

export type LeafNode = {
  kind: "leaf";
  id: string;
  query: string;
  scope: LayerScope;
  useRegex: boolean;
  contributeHits: boolean;
  negate: boolean;
};

export type GroupNode = {
  kind: "group";
  id: string;
  op: GroupOp;
  negate: boolean;
  children: QueryNode[];
};

export type QueryNode = LeafNode | GroupNode;

let _idCounter = 0;
// IDs intentionally exclude Date.now() / Math.random() so that the same
// `emptyRoot()` call on the server and client produces matching IDs — Next's
// hydration warning fires loudly on any data-* attribute mismatch.
function nextId(prefix: string): string {
  _idCounter = (_idCounter + 1) | 0;
  return `${prefix}${_idCounter.toString(36)}`;
}

export function newLeaf(partial: Partial<LeafNode> = {}): LeafNode {
  return {
    kind: "leaf",
    id: partial.id ?? nextId("l"),
    query: partial.query ?? "",
    scope: partial.scope ?? "transcripts",
    useRegex: partial.useRegex ?? false,
    contributeHits: partial.contributeHits ?? true,
    negate: partial.negate ?? false,
  };
}

export function newGroup(partial: Partial<GroupNode> = {}): GroupNode {
  return {
    kind: "group",
    id: partial.id ?? nextId("g"),
    op: partial.op ?? "AND",
    negate: partial.negate ?? false,
    children: partial.children ?? [],
  };
}

export function emptyRoot(): GroupNode {
  return newGroup({ children: [newLeaf({ scope: "transcripts" })] });
}

export function isLeaf(n: QueryNode): n is LeafNode {
  return n.kind === "leaf";
}

export function isGroup(n: QueryNode): n is GroupNode {
  return n.kind === "group";
}

// A leaf is "active" (has any effect on evaluation) only when it has a
// non-empty query. Empty leaves are skipped at eval time rather than treated
// as a wildcard match — see searchEval.ts.
export function isLeafActive(leaf: LeafNode): boolean {
  return leaf.query.trim().length > 0;
}

// Recursively determine whether a node contributes anything to evaluation.
// Used to short-circuit empty subtrees so a freshly added blank leaf doesn't
// nuke an AND result down to zero.
export function isNodeActive(n: QueryNode): boolean {
  if (isLeaf(n)) return isLeafActive(n);
  return n.children.some(isNodeActive);
}

// ─── Canonical hash ───
// Stable hash over content (not IDs). Used as the prefix of the layer-cache
// key so semantically equivalent trees collide in cache regardless of the
// random IDs assigned to their nodes. Children of OR groups are sorted by
// their own hash; AND children stay ordered for evaluation purposes but the
// cache only consumes the final hash so order doesn't matter for hits.

function fnv1a(str: string): string {
  // 32-bit FNV-1a. Sufficient for cache keys (collision risk negligible at
  // the cardinalities this UI produces) and avoids pulling in a crypto dep.
  let h = 0x811c9dc5;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return (h >>> 0).toString(36);
}

export function canonicalHash(n: QueryNode): string {
  return fnv1a(canonicalString(n));
}

function canonicalString(n: QueryNode): string {
  if (isLeaf(n)) {
    const q = n.useRegex ? n.query : n.query.toLowerCase();
    // contributeHits MUST be in the hash: the cached payload's hit map is
    // empty when contributeHits=false, so a collision lets a hits-off run
    // poison the cache for a later hits-on run with the same query/scope.
    return `L|${n.scope}|${n.useRegex ? "r" : "p"}|${n.negate ? "n" : "y"}|${n.contributeHits ? "h" : "H"}|${q}`;
  }
  const childStrs = n.children.filter(isNodeActive).map(canonicalString);
  if (n.op === "OR") childStrs.sort();
  return `G|${n.op}|${n.negate ? "n" : "y"}|${childStrs.join("
")}`;
}

export function hashSlugs(slugs: ReadonlyArray<string> | ReadonlySet<string>): string {
  const arr = Array.isArray(slugs) ? slugs.slice() : Array.from(slugs);
  arr.sort();
  return fnv1a(arr.join("|"));
}

// ─── Serialization (URL/storage) ───
// Compact JSON shape: { o, c, n } for groups, { k:"l", q, s, r, h, n, i } for
// leaves. IDs are preserved so React keys stay stable across reloads.

type SerializedLeaf = {
  k: "l";
  i?: string;
  q: string;
  s: LayerScope;
  r?: 1;
  h?: 0;
  n?: 1;
};
type SerializedGroup = {
  k: "g";
  i?: string;
  o: GroupOp;
  n?: 1;
  c: Serialized[];
};
type Serialized = SerializedLeaf | SerializedGroup;

function serialize(n: QueryNode): Serialized {
  // IDs are intentionally NOT serialized — they're session-scoped (used as
  // React keys + for the swatch colour hash). Persisting them would just
  // produce noisy URLs without enabling anything useful, and leaving them
  // out keeps the URL stable across sessions for the same logical query.
  if (isLeaf(n)) {
    const out: SerializedLeaf = { k: "l", q: n.query, s: n.scope };
    if (n.useRegex) out.r = 1;
    if (!n.contributeHits) out.h = 0;
    if (n.negate) out.n = 1;
    return out;
  }
  const out: SerializedGroup = {
    k: "g",
    o: n.op,
    c: n.children.map(serialize),
  };
  if (n.negate) out.n = 1;
  return out;
}

function deserialize(raw: unknown): QueryNode | null {
  if (!raw || typeof raw !== "object") return null;
  const r = raw as Record<string, unknown>;
  if (r.k === "l") {
    const scope = r.s;
    // Explicit whitelist: an unrecognized scope drops the leaf rather than
    // silently evaluating it as something else. New scopes MUST be added here
    // or a `qt=` URL carrying them loses the leaf.
    if (
      scope !== "transcripts" &&
      scope !== "chat" &&
      scope !== "posts" &&
      scope !== "metadata" &&
      scope !== "description" &&
      scope !== "tags"
    ) {
      return null;
    }
    return {
      kind: "leaf",
      id: typeof r.i === "string" && r.i ? r.i : nextId("l"),
      query: typeof r.q === "string" ? r.q : "",
      scope,
      useRegex: r.r === 1,
      contributeHits: r.h !== 0,
      negate: r.n === 1,
    };
  }
  if (r.k === "g") {
    const op = r.o;
    if (op !== "AND" && op !== "OR") return null;
    const rawChildren = Array.isArray(r.c) ? r.c : [];
    const children: QueryNode[] = [];
    for (const c of rawChildren) {
      const child = deserialize(c);
      if (child) children.push(child);
    }
    return {
      kind: "group",
      id: typeof r.i === "string" && r.i ? r.i : nextId("g"),
      op,
      negate: r.n === 1,
      children,
    };
  }
  return null;
}

export function stringifyRoot(root: GroupNode): string {
  return JSON.stringify(serialize(root));
}

export function parseRoot(s: string): GroupNode | null {
  let raw: unknown;
  try {
    raw = JSON.parse(s);
  } catch {
    return null;
  }
  const node = deserialize(raw);
  if (!node || !isGroup(node)) return null;
  return node;
}

// Build a root from the legacy single-input search (`?q=` / `?m=` / `?re=`).
// Returns a one-leaf root targeted at the appropriate scope. Used when a URL
// has `q=` but no `qt=`, so old share links keep working.
export function rootFromLegacy(
  q: string,
  mode: SearchMode,
  useRegex: boolean,
): GroupNode {
  return newGroup({
    children: [
      newLeaf({
        query: q,
        scope:
          mode === "subs" ? "chat" : mode === "posts" ? "posts" : "transcripts",
        useRegex,
        contributeHits: true,
      }),
    ],
  });
}

// ─── Tree mutation helpers ───
// All mutations are immutable: each helper returns a new root with the
// changed subtree replaced. Easier reasoning for React and matches the
// "edit-only-the-leaf" cache-reuse story (sibling subtrees keep identity).

export function replaceNode(
  root: GroupNode,
  id: string,
  next: QueryNode,
): GroupNode {
  const out = replaceInNode(root, id, next);
  if (!out || !isGroup(out)) return root;
  return out;
}

function replaceInNode(
  node: QueryNode,
  id: string,
  next: QueryNode,
): QueryNode | null {
  if (node.id === id) return next;
  if (!isGroup(node)) return null;
  let changed = false;
  const newChildren: QueryNode[] = node.children.map((c) => {
    const r = replaceInNode(c, id, next);
    if (r) {
      changed = true;
      return r;
    }
    return c;
  });
  if (!changed) return null;
  return { ...node, children: newChildren };
}

export function removeNode(root: GroupNode, id: string): GroupNode {
  const out = removeFromNode(root, id);
  if (!out || !isGroup(out)) return root;
  return out;
}

// True when the tree renders in QueryBuilder's "compact" single-input mode:
// a non-negated AND root with exactly one non-negated leaf child.
export function isCompactRoot(root: GroupNode): boolean {
  if (root.negate || root.op !== "AND" || root.children.length !== 1) {
    return false;
  }
  const only = root.children[0];
  return isLeaf(only) && !only.negate;
}

// Compact mode hides per-leaf options that have no other control to toggle
// them (currently "Show hits in results"). When a tree collapses to compact
// form those hidden options would otherwise stay stuck in whatever state they
// had with 2+ layers, so reset them to their leaf defaults. No-op for any
// non-compact tree.
export function normalizeRoot(root: GroupNode): GroupNode {
  if (!isCompactRoot(root)) return root;
  const only = root.children[0] as LeafNode;
  if (only.contributeHits) return root;
  return { ...root, children: [{ ...only, contributeHits: true }] };
}

function removeFromNode(node: QueryNode, id: string): QueryNode | null {
  if (!isGroup(node)) return null;
  let changed = false;
  const newChildren: QueryNode[] = [];
  for (const c of node.children) {
    if (c.id === id) {
      changed = true;
      continue;
    }
    const r = removeFromNode(c, id);
    if (r) {
      changed = true;
      newChildren.push(r);
    } else {
      newChildren.push(c);
    }
  }
  if (!changed) return null;
  return { ...node, children: newChildren };
}

export function insertChild(
  root: GroupNode,
  groupId: string,
  child: QueryNode,
  position: "start" | "end" = "end",
): GroupNode {
  const out = insertInNode(root, groupId, child, position);
  if (!out || !isGroup(out)) return root;
  return out;
}

function insertInNode(
  node: QueryNode,
  groupId: string,
  child: QueryNode,
  position: "start" | "end",
): QueryNode | null {
  if (!isGroup(node)) return null;
  if (node.id === groupId) {
    const newChildren =
      position === "start"
        ? [child, ...node.children]
        : [...node.children, child];
    return { ...node, children: newChildren };
  }
  let changed = false;
  const newChildren: QueryNode[] = node.children.map((c) => {
    const r = insertInNode(c, groupId, child, position);
    if (r) {
      changed = true;
      return r;
    }
    return c;
  });
  if (!changed) return null;
  return { ...node, children: newChildren };
}

// "Wrap leaf in a group": replace the leaf with a fresh AND group containing
// it. Used by the "Add OR sibling" UX so users don't have to manually create
// a group + drag the leaf into it.
export function wrapInGroup(
  root: GroupNode,
  id: string,
  op: GroupOp = "AND",
): GroupNode {
  let target: QueryNode | null = null;
  function find(n: QueryNode): void {
    if (n.id === id) {
      target = n;
      return;
    }
    if (isGroup(n)) for (const c of n.children) find(c);
  }
  find(root);
  if (!target) return root;
  return replaceNode(root, id, newGroup({ op, children: [target] }));
}

// Inverse of `wrapInGroup`: replace a group with its children spliced into
// the parent at the same position. If the group is negated, flip each
// promoted child's `negate` so the meaning of the subtree is preserved
// locally (De Morgan applied per-child). Root is left alone since the tree
// invariant requires a GroupNode at the top.
export function unwrapGroup(root: GroupNode, id: string): GroupNode {
  if (root.id === id) return root;
  const out = unwrapInNode(root, id);
  if (!out || !isGroup(out)) return root;
  return out;
}

function unwrapInNode(node: QueryNode, id: string): QueryNode | null {
  if (!isGroup(node)) return null;
  let changed = false;
  const newChildren: QueryNode[] = [];
  for (const c of node.children) {
    if (isGroup(c) && c.id === id) {
      changed = true;
      const promoted = c.negate ? c.children.map(flipNegate) : c.children;
      newChildren.push(...promoted);
      continue;
    }
    const r = unwrapInNode(c, id);
    if (r) {
      changed = true;
      newChildren.push(r);
    } else {
      newChildren.push(c);
    }
  }
  if (!changed) return null;
  return { ...node, children: newChildren };
}

function flipNegate(n: QueryNode): QueryNode {
  return { ...n, negate: !n.negate };
}

// Walk every leaf in the tree, depth-first. Used by the UI to compute live
// counts, colour swatches, and the "contributing leaves" list.
export function forEachLeaf(
  root: QueryNode,
  fn: (leaf: LeafNode) => void,
): void {
  if (isLeaf(root)) {
    fn(root);
    return;
  }
  for (const c of root.children) forEachLeaf(c, fn);
}

// ─── "Search in" ───
// The Filters panel's "Search in" row says what the DEFAULT leaf reads: a leaf
// whose scope is "transcripts" (what `emptyRoot` and every plain query make)
// reads the transcript cues, the posts corpus and the live-chat track, each
// when its box is ticked. A leaf asked for BY NAME in the builder ("Live chat",
// "Posts", "Title / channel", …) is not the row's business and is left as it
// is. The row is not part of the tree: the tree the visitor built, the `qt=`
// it writes and the canonical hash stay what they were, and this rewrite is
// applied to the committed tree just before it runs.
//
// `posts` and `chat` are what the row ticks AND the site ships — the caller
// folds "Posts is ticked but this site has no posts" to false, so a rewrite
// never asks for a corpus that is not there.
export type SearchIn = { transcripts: boolean; posts: boolean; chat: boolean };

// Transcripts and posts on, live chat off: the ruling's default.
export const SEARCH_IN_DEFAULT: Readonly<SearchIn> = {
  transcripts: true,
  posts: true,
  chat: false,
};

export function searchInReadsNothing(s: SearchIn): boolean {
  return !s.transcripts && !s.posts && !s.chat;
}

// Under a curated-tag filter no post can match — a post carries no curated
// tags — so a posts copy would read an empty scope and cost a posts-manifest
// load for nothing. It is left out, unless posts are all the row reads: then
// it stays (and reads nothing, which is the answer) so that the leaf does not
// fall back to reading its transcripts.
export function searchInUnderTags(s: SearchIn, tagFilterOn: boolean): SearchIn {
  if (!tagFilterOn || !s.posts || (!s.transcripts && !s.chat)) return s;
  return { ...s, posts: false };
}

export type SearchInTree = {
  root: GroupNode;
  // A per-kind copy's leaf id → the id of the "transcripts" leaf it stands
  // for. The result fold (`lib/search/searchIn.ts`) reads it to file the
  // copies' hits and counts back under the leaf the visitor sees.
  origin: ReadonlyMap<string, string>;
  // The "transcripts" leaf's id → the OR group over its copies, whose group
  // state is the union the leaf's count should read. Only for a leaf that
  // reads two or three kinds (one kind is the same leaf with another scope).
  unionOf: ReadonlyMap<string, string>;
};

// The kinds in the order their copies are made. The order is cosmetic (an OR's
// children run in parallel and its hash sorts them); fixed so a test can name it.
const SEARCH_IN_KINDS = ["transcripts", "posts", "chat"] as const;

// Rewrite every ACTIVE "transcripts" leaf to read what the row ticks:
//   transcripts only     → the leaf, unchanged (the same object)
//   one other kind only  → the leaf with that scope; same id, same negate
//   two or three kinds   → an OR group over one copy per kind, each copy with
//                          the leaf's `contributeHits`. A negated leaf is NOT
//                          of the union: the OR goes inside a negated
//                          one-child AND, so the OR's own state is always the
//                          union (the count the leaf shows) whatever `negate`.
//   nothing              → the leaf, unchanged. The UI never commits it (the
//                          Search button, Enter, Apply and the profile saves
//                          all refuse); a tree that arrives with nothing ticked
//                          some other way reads its transcripts rather than
//                          silently matching nothing.
// Copies get derived ids (`<id>~posts`, `<id>~in`, …) because every leaf in a
// run keys its own results by id. An unchanged subtree keeps its identity, so
// the default row returns the very root it was given.
export function applySearchIn(root: GroupNode, s: SearchIn): SearchInTree {
  const origin = new Map<string, string>();
  const unionOf = new Map<string, string>();
  const kinds = SEARCH_IN_KINDS.filter((k) => s[k]);
  if (kinds.length === 0 || (kinds.length === 1 && kinds[0] === "transcripts")) {
    return { root, origin, unionOf };
  }
  const out = rewriteSearchIn(root, kinds, origin, unionOf);
  return { root: out as GroupNode, origin, unionOf };
}

function rewriteSearchIn(
  node: QueryNode,
  kinds: ReadonlyArray<LayerScope>,
  origin: Map<string, string>,
  unionOf: Map<string, string>,
): QueryNode {
  if (isLeaf(node)) {
    if (node.scope !== "transcripts" || !isLeafActive(node)) return node;
    if (kinds.length === 1) return { ...node, scope: kinds[0] };
    const union: GroupNode = {
      kind: "group",
      id: `${node.id}~in`,
      op: "OR",
      negate: false,
      children: kinds.map((scope) => {
        const id = `${node.id}~${scope}`;
        origin.set(id, node.id);
        return { ...node, id, scope, negate: false };
      }),
    };
    unionOf.set(node.id, union.id);
    if (!node.negate) return union;
    return {
      kind: "group",
      id: `${node.id}~not`,
      op: "AND",
      negate: true,
      children: [union],
    };
  }
  let changed = false;
  const children = node.children.map((c) => {
    const r = rewriteSearchIn(c, kinds, origin, unionOf);
    if (r !== c) changed = true;
    return r;
  });
  return changed ? { ...node, children } : node;
}