/** Shared ranking keeps command palettes and MCP thread search consistent across surfaces. */

import type { OrchestrationV2ThreadOpens } from "@t3tools/contracts";

import { WORKTREE_BRANCH_PREFIX } from "./git.ts";

const ALPHANUMERIC = /[\p{L}\p{N}]/u;
const LOWERCASE = /\p{Ll}/u;
const UPPERCASE = /\p{Lu}/u;
const DIGIT = /\p{N}/u;
const LETTER = /\p{L}/u;
const COMBINING_MARKS = /\p{M}/gu;
// Emoji and other symbols can be searched for, so they start words too.
const SYMBOL = /\p{So}/u;
const APOSTROPHE = /['’]/;
const CURLY_APOSTROPHES = /[\u2018\u2019]/g;

interface SearchField {
  /** Case- and accent-folded text, one UTF-16 unit per source unit. */
  readonly text: string;
  /** 1 where a word starts in `text`. */
  readonly wordStarts: Uint8Array;
}

export interface SearchRange {
  readonly start: number;
  readonly end: number;
}

// Thread titles, branches, and project names repeat across keystrokes; folding
// them once keeps a keystroke to plain string scans. Each keystroke reads every
// field, so the limit must hold all of them or the cache clears every time; a
// field is a few bytes per character.
const fieldCache = new Map<string, SearchField>();
const FIELD_CACHE_LIMIT = 100_000;

function foldCharacter(character: string): string {
  // A typed straight apostrophe finds a curly one: iOS keyboards type "’".
  return character
    .normalize("NFKD")
    .replace(COMBINING_MARKS, "")
    .toLowerCase()
    .replace("ς", "σ")
    .replace(/[‘’]/, "'");
}

/**
 * `text` with case and accents folded one UTF-16 unit at a time, so offsets
 * and word starts still read from `text` and highlights need no mapping. A
 * letter that folds to more or less than one unit ("ß", "fi") stays as it is.
 */
function foldInPlace(text: string): string {
  return text
    .replace(/[\u0080-\uffff]/g, (character) => {
      const folded = foldCharacter(character);
      return folded.length === 1 ? folded : character;
    })
    .toLowerCase();
}

// Chinese and Japanese text has no spaces, so each ideograph or kana starts a word.
function isCjk(character: string): boolean {
  const code = character.codePointAt(0)!;
  return (
    (code >= 0x3040 && code <= 0x30ff) ||
    (code >= 0x3400 && code <= 0x4dbf) ||
    (code >= 0x4e00 && code <= 0x9fff) ||
    (code >= 0xf900 && code <= 0xfaff)
  );
}

// Two Chinese, Japanese, or Korean characters already make a common word.
function hasCjkWord(token: string): boolean {
  return Array.from(token).some((character) => {
    const code = character.codePointAt(0)!;
    return isCjk(character) || (code >= 0xac00 && code <= 0xd7af);
  });
}

/**
 * Whether `character` starts a word after `previous` and `beforePrevious`
 * ("" at the start): after a non-letter, at a camelCase or digit boundary, or
 * at any Chinese or Japanese character. The one rule for titles and messages.
 */
function isWordStart(
  beforePrevious: string,
  previous: string,
  character: string,
  next: string,
): boolean {
  // "Julius’s": a possessive or contraction does not start a word.
  const afterApostrophe = APOSTROPHE.test(previous) && ALPHANUMERIC.test(beforePrevious);
  return (
    (ALPHANUMERIC.test(character) || SYMBOL.test(character)) &&
    !afterApostrophe &&
    (previous === "" ||
      !ALPHANUMERIC.test(previous) ||
      (LOWERCASE.test(previous) && UPPERCASE.test(character)) ||
      // The last capital of an acronym starts the next word: "JSONSchema".
      (UPPERCASE.test(previous) && UPPERCASE.test(character) && LOWERCASE.test(next)) ||
      DIGIT.test(previous) !== DIGIT.test(character) ||
      isCjk(character))
  );
}

function foldSearchField(source: string): SearchField {
  const wordStarts = new Uint8Array(source.length);
  const characters = Array.from(source);
  let index = 0;
  for (const [position, character] of characters.entries()) {
    const previous = characters[position - 1] ?? "";
    const next = characters[position + 1] ?? "";
    if (isWordStart(characters[position - 2] ?? "", previous, character, next)) {
      wordStarts[index] = 1;
    }
    index += character.length;
  }
  return { text: foldInPlace(source), wordStarts };
}

function prepareSearchField(source: string): SearchField {
  const cached = fieldCache.get(source);
  if (cached) return cached;
  // Oldest first out. A read does not re-insert: that would cost more than the
  // fold it saves, and the limit holds far more fields than a keystroke reads.
  if (fieldCache.size >= FIELD_CACHE_LIMIT) {
    fieldCache.delete(fieldCache.keys().next().value!);
  }
  const field = foldSearchField(source);
  fieldCache.set(source, field);
  return field;
}

// Quotes around a pasted query: "fix sidebar".
const WRAPPING_QUOTES = /^\s*["'`“”‘’]+|["'`“”‘’]+\s*$/g;

/** Folded, whitespace-collapsed query; empty when there is nothing to match. */
export function foldSearchQuery(query: string): string {
  return foldInPlace(query.replace(WRAPPING_QUOTES, "").normalize("NFC"))
    .split(/\s+/)
    .filter((token) => token.length > 0)
    .join(" ");
}

function wordEnd(field: SearchField, index: number): number {
  let end = index + 1;
  while (end < field.text.length && !field.wordStarts[end] && ALPHANUMERIC.test(field.text[end]!)) {
    end++;
  }
  return end;
}

// One substitution, insertion, deletion, or swap of neighbours; with
// `swapOnly`, only a swap.
function withinOneEdit(left: string, right: string, swapOnly: boolean): boolean {
  if (Math.abs(left.length - right.length) > (swapOnly ? 0 : 1)) return false;
  let index = 0;
  while (index < left.length && index < right.length && left[index] === right[index]) index++;
  const restLeft = left.slice(index);
  const restRight = right.slice(index);
  const swapped =
    restLeft.length > 1 &&
    restLeft[0] === restRight[1] &&
    restLeft[1] === restRight[0] &&
    restLeft.slice(2) === restRight.slice(2);
  if (swapOnly) return swapped;
  return (
    swapped ||
    restLeft === restRight ||
    restLeft.slice(1) === restRight.slice(1) ||
    restLeft.slice(1) === restRight ||
    restLeft === restRight.slice(1)
  );
}

const WHOLE_WORD = 1;
// The bonus for a field equal to the whole query lifts a whole word to this.
const WHOLE_NAME = 1.5;
const MID_WORD = 0.3;
const TYPO = 0.45;
// Whole words typed together are exact, so they rank with typos and above
// mid-word hits, though below a match at a word start.
const JOINED_WORDS = 0.6;

interface TokenMatch extends SearchRange {
  readonly score: number;
  /** Separate ranges, for words typed together. */
  readonly letters?: ReadonlyArray<SearchRange>;
}

/**
 * Mid-word hits need four or more characters and `midWord`, so "del" does not find "model".
 * Typos preserve the first letter except for swaps; short tokens allow fewer edits to limit noise.
 * Numbers never match with a typo because different pull request numbers must stay distinct.
 */
function matchToken(
  field: SearchField,
  token: string,
  typos: boolean,
  isPrimary: boolean,
  midWord: boolean,
): TokenMatch | null {
  if (token.length === 0) return null;
  let best: TokenMatch | null = null;
  let ownBoundary: boolean | undefined;
  for (
    let index = field.text.indexOf(token);
    index !== -1;
    index = field.text.indexOf(token, index + 1)
  ) {
    // A token that opens with punctuation (".ts") brings its own boundary, as in messages.
    if (
      field.wordStarts[index] ||
      (ownBoundary ??= !ALPHANUMERIC.test(token[0]!) && !SYMBOL.test(token[0]!))
    ) {
      // Whole when the match ends where a word ends: "t3c" is a prefix of
      // "t3code", ".ts" whole in "index.ts" but a prefix in "parser.tsx".
      const end = index + token.length;
      const whole =
        end >= field.text.length ||
        field.wordStarts[end] === 1 ||
        !ALPHANUMERIC.test(field.text[end]!);
      let runEnd = end;
      while (runEnd < field.text.length && ALPHANUMERIC.test(field.text[runEnd]!)) runEnd++;
      const score = whole ? WHOLE_WORD : 0.7 + (0.2 * token.length) / (runEnd - index);
      if (best === null || score > best.score) {
        best = { score, start: index, end: index + token.length };
      }
      if (score === WHOLE_WORD) return best;
    } else if (midWord && token.length >= 4 && best === null) {
      best = { score: MID_WORD, start: index, end: index + token.length };
    }
  }
  // Joined words are exact, so they count without the typo pass: a strong
  // match elsewhere must not hide "VS Code" for "vscode".
  if ((best === null || best.score <= MID_WORD) && isPrimary) {
    const joined = matchJoinedWords(field, token);
    if (joined) return joined;
  }
  if ((best !== null && best.score > MID_WORD) || !typos || token.length < 3) return best;
  // Numbers skip typos to keep pull requests distinct. Words with digits ("t3code") do not.
  if (LETTER.test(token)) {
    for (let index = 0; index < field.text.length; index++) {
      if (!field.wordStarts[index]) continue;
      // People rarely mistype the first letter, so a typo keeps it, unless it
      // swaps the first two of a longer word ("ing" is not "nig…").
      const first = field.text[index];
      const firstLetterKept =
        first === token[0] ||
        (token.length > 3 && first === token[1] && field.text[index + 1] === token[0]);
      if (!firstLetterKept) continue;
      // The whole run, across camelCase joins: "githbu" is "GitHub".
      let runEnd = index + 1;
      while (runEnd < field.text.length && ALPHANUMERIC.test(field.text[runEnd]!)) runEnd++;
      const word = field.text.slice(index, runEnd);
      // Short tokens forgive a swapped pair or one missing letter ("srv" for
      // "serv…"); any other edit of a three- or four-letter word matches too
      // much ("cron" would find every "con…").
      const short = token.length <= 4;
      // The same length first, so "githbu" highlights all of "GitHub".
      const lengths = short
        ? [token.length, token.length + 1]
        : [token.length, token.length - 1, token.length + 1];
      for (const length of lengths) {
        if (length > word.length) continue;
        const prefix = word.slice(0, length);
        if (withinOneEdit(token, prefix, short && length === token.length)) {
          return { score: TYPO, start: index, end: index + length };
        }
      }
    }
  }
  return best;
}

/**
 * Short words followed by a short prefix are noise inside a title ("inth" in "in thread").
 * Allow them at its start ("t3co"), before three letters ("gomod"), or a whole word ("vscode").
 */
function matchJoinedWords(field: SearchField, token: string): TokenMatch | null {
  for (
    let start = field.text.indexOf(token[0]!);
    start !== -1;
    start = field.text.indexOf(token[0]!, start + 1)
  ) {
    if (!field.wordStarts[start]) continue;
    const runs: SearchRange[] = [];
    let at = start;
    let rest = token;
    while (rest.length > 0 && at < field.text.length) {
      const end = wordEnd(field, at);
      if (rest.length <= end - at && field.text.startsWith(rest, at)) {
        runs.push({ start: at, end: at + rest.length });
        rest = "";
      } else if (rest.startsWith(field.text.slice(at, end))) {
        runs.push({ start: at, end });
        rest = rest.slice(end - at);
        at = end;
        while (at < field.text.length && !field.wordStarts[at]) at++;
      } else {
        break;
      }
    }
    const last = runs.at(-1);
    if (rest.length > 0 || last === undefined || runs.length < 2) continue;
    if (
      last.end === wordEnd(field, last.start) ||
      last.end - last.start >= 3 ||
      start === field.wordStarts.indexOf(1) ||
      runs.slice(0, -1).every((run) => run.end - run.start >= 3)
    ) {
      return { score: JOINED_WORDS, start, end: last.end, letters: runs };
    }
  }
  return null;
}

interface WeightedSearchField {
  readonly value: string;
  /** `value` folded; set on first use, so fields kept across keystrokes fold once. */
  prepared?: SearchField;
  readonly weight: number;
  /** Only a whole-word match counts, as for a short query against keywords. */
  readonly wholeWords?: boolean;
  /**
   * Only a match at a word start counts, without typos: hidden keywords that
   * matched loosely would list results the user cannot see why for.
   */
  readonly keyword?: boolean;
  /**
   * Where the thread lives (project, environment): it helps a match, but a
   * word start there does not make the match strong, so it never turns off
   * joined words or typos for the titles.
   */
  readonly context?: boolean;
  /**
   * A token of four or more letters may match inside a word here. Only thread
   * titles allow it: inside a command name or a branch it reads as junk
   * ("arch" in "Search").
   */
  readonly midWord?: boolean;
}

interface SearchFieldsMatch {
  /** Roughly 0.3 (inside a word) to 1.5 (exact title). */
  readonly quality: number;
  /** Every token matched at a word start, without a typo. */
  readonly strong: boolean;
  /** Source ranges matched in the first field, for highlighting. */
  readonly primaryRanges: ReadonlyArray<SearchRange>;
}

function preparedField(weighted: WeightedSearchField): SearchField {
  return (weighted.prepared ??= prepareSearchField(weighted.value));
}

const FILLER_WORDS = new Set(["a", "an", "and", "for", "in", "of", "on", "the", "to", "with"]);

// Sorted, with overlapping ranges joined.
function mergeRanges(ranges: ReadonlyArray<SearchRange>): SearchRange[] {
  const merged: SearchRange[] = [];
  for (const range of [...ranges].sort((left, right) => left.start - right.start)) {
    const last = merged.at(-1);
    if (last && range.start <= last.end) {
      merged[merged.length - 1] = { start: last.start, end: Math.max(last.end, range.end) };
    } else {
      merged.push({ start: range.start, end: range.end });
    }
  }
  return merged;
}

// A keystroke scores every thread for one query, so its tokens are split once.
let lastQuery:
  | { readonly query: string; readonly tokens: string[]; readonly fillerOptional: boolean }
  | undefined;

function queryTokens(normalizedQuery: string) {
  if (lastQuery?.query !== normalizedQuery) {
    const tokens = normalizedQuery.split(" ").filter((token) => token.length > 0);
    // A phrase-style query ("fix the sidebar") carries filler words a name may
    // leave out; they count where they match but are not required.
    lastQuery = {
      query: normalizedQuery,
      tokens,
      fillerOptional: tokens.some((token) => !FILLER_WORDS.has(token)),
    };
  }
  return lastQuery;
}

/**
 * Every query token must match some field. Quality is the mean of each token's
 * best weighted match, plus a bonus when the first field holds the whole query
 * as a phrase or equals it.
 */
function matchSearchFields(
  normalizedQuery: string,
  fields: ReadonlyArray<WeightedSearchField>,
  options?: { readonly typos?: boolean },
): SearchFieldsMatch | null {
  if (normalizedQuery.length === 0) return null;
  const primary = fields[0]?.value ? preparedField(fields[0]) : undefined;
  // An empty token would match everywhere, and loop forever in `matchToken`.
  const { tokens, fillerOptional } = queryTokens(normalizedQuery);
  if (tokens.length === 0) return null;
  const primaryRanges: SearchRange[] = [];
  let total = 0;
  let counted = 0;
  let strong = true;
  for (const token of tokens) {
    let best = 0;
    let bestPrimary: TokenMatch | null = null;
    let atWordStart = false;
    for (const weighted of fields) {
      if (weighted.value.length === 0) continue;
      const { weight, wholeWords, keyword, context, midWord } = weighted;
      const field = preparedField(weighted);
      if (best >= weight && field !== primary && atWordStart) continue;
      const typos = (options?.typos ?? false) && !keyword;
      // Joined words only count in the name.
      const match = matchToken(field, token, typos, field === primary, midWord ?? false);
      if (match === null || match.score < (wholeWords ? WHOLE_WORD : keyword ? 0.7 : 0)) continue;
      if (field === primary) bestPrimary = match;
      if (match.score >= 0.7 && !context) atWordStart = true;
      if (match.score * weight > best) best = match.score * weight;
    }
    if (best === 0) {
      if (fillerOptional && FILLER_WORDS.has(token)) continue;
      return null;
    }
    strong &&= atWordStart;
    if (bestPrimary) primaryRanges.push(...(bestPrimary.letters ?? [bestPrimary]));
    total += best;
    counted += 1;
  }
  let quality = total / counted;
  if (primary) {
    if (primary.text === normalizedQuery) quality += WHOLE_NAME - WHOLE_WORD;
    else if (tokens.length > 1 && primary.text.includes(normalizedQuery)) quality += 0.25;
  }
  return {
    quality,
    strong,
    primaryRanges: mergeRanges(primaryRanges),
  };
}

// A two-letter Latin substring of a message is noise rather than a match.
const MESSAGE_TOKEN_MIN_LENGTH = 3;

/**
 * Keep accents: the server index folds Latin accents, and stripping marks breaks Korean/Japanese.
 * Every `long` token must match; `short` tokens only narrow hits. No long tokens means no search.
 * Two CJK characters count as long.
 */
export function messageSearchTokens(query: string): {
  readonly long: ReadonlyArray<string>;
  readonly short: ReadonlyArray<string>;
  /** Every token, in the order typed. */
  readonly words: ReadonlyArray<string>;
} {
  const tokens = query
    .replace(WRAPPING_QUOTES, "")
    // The index stores apostrophes straight, as `indexedMessageText` writes them.
    .replace(CURLY_APOSTROPHES, "'")
    .normalize("NFC")
    .toLowerCase()
    .split(/\s+/)
    .filter((token) => token.length > 0);
  const searchable = (token: string) => {
    const length = Array.from(token).length;
    return length >= MESSAGE_TOKEN_MIN_LENGTH || (length === 2 && hasCjkWord(token));
  };
  return {
    long: tokens.filter(searchable),
    short: tokens.filter((token) => !searchable(token)),
    words: tokens,
  };
}

/**
 * Matches the query's words side by side as whole words, as typed, whatever
 * whitespace is between them and ignoring case; null for a single word.
 */
export function messagePhrase(query: string): RegExp | null {
  const { words } = messageSearchTokens(query);
  return words.length > 1
    ? new RegExp(
        `(?<![\\p{L}\\p{N}])${words
          .map((word) => word.replace(/[.*+?^${}()|[\]\\]/g, "\\$&"))
          .join("\\s+")}(?![\\p{L}\\p{N}])`,
        "iu",
      )
    : null;
}

// Words written together, as typed, rank above the same words apart, as in
// titles; words near each other rank above words far apart.
const MESSAGE_PHRASE_BONUS = 0.25;
const MESSAGE_NEAR_BONUS = 0.1;
// About what a result row shows.
const MESSAGE_NEAR_SPAN = 60;

const NON_ASCII = /[\u0080-\uffff]/;
// A message token shorter than this must start a word: "fts" is not in "drafts".
const MESSAGE_WORD_START_LENGTH = 4;
const MESSAGE_PREFIX = 0.8;

function startsWordAt(text: string, index: number): boolean {
  const character = text[index]!;
  // A token that opens with punctuation (such as ".ts") brings its own boundary.
  if (!ALPHANUMERIC.test(character) && !SYMBOL.test(character)) return true;
  return isWordStart(
    text[index - 2] ?? "",
    text[index - 1] ?? "",
    character,
    text[index + 1] ?? "",
  );
}

// Whether a word ends right before `end` in `text`.
function endsWordAt(text: string, end: number): boolean {
  return end >= text.length || !ALPHANUMERIC.test(text[end]!) || startsWordAt(text, end);
}

// A commit SHA or UUID part: seven or more hex characters with a digit.
const HEX_ID = /^(?=[a-f]*\d)[0-9a-f]{7,}$/i;

// Where `token` best sits in `folded`, a fold of `text`: every place it is a
// whole word, else a word start, else inside a word. Hits past the start of a
// hex ID do not count ("cafe" in "7cafe52bb8"), though a pasted SHA prefix
// does.
function findMessageToken(
  text: string,
  folded: string,
  token: string,
  firstOnly: boolean,
): { readonly at: ReadonlyArray<number>; readonly quality: number } | null {
  let quality = 0;
  let at: number[] = [];
  // The letters-and-digits run around the hit, kept for later hits in the
  // same run: rescanning it per hit is quadratic in a long run ("0000" in a
  // hex dump).
  let run = { start: 0, end: -1, hex: false };
  for (let index = folded.indexOf(token); index !== -1; index = folded.indexOf(token, index + 1)) {
    if (index + token.length > run.end) {
      let start = index;
      while (start > 0 && ALPHANUMERIC.test(text[start - 1]!)) start--;
      let end = index + token.length;
      while (end < text.length && ALPHANUMERIC.test(text[end]!)) end++;
      run = { start, end, hex: HEX_ID.test(text.slice(start, end)) };
    }
    if (run.hex && run.start < index) continue;
    const found = !startsWordAt(text, index)
      ? MID_WORD
      : endsWordAt(text, index + token.length)
        ? 1
        : MESSAGE_PREFIX;
    if (found > quality) {
      quality = found;
      at = [index];
      if (firstOnly && quality === 1) return { at, quality };
    } else if (!firstOnly && found === quality) {
      at.push(index);
    }
  }
  return at.length === 0 ? null : { at, quality };
}

export interface MessageMatch {
  /**
   * 1 when every searched word is a whole word, MESSAGE_PREFIX when one only
   * starts a word ("mode" in "model"), MID_WORD when one only appears inside
   * words, plus MESSAGE_PHRASE_BONUS when the words are written together as
   * typed, else MESSAGE_NEAR_BONUS when they sit within a row's width.
   */
  readonly quality: number;
  /** Where a snippet should start to show the match. */
  readonly offset: number;
}

/**
 * Grades messages against a query, so message hits rank like titles: null
 * when a token is missing or a short one never starts a word ("fts" in
 * "drafts"). Case and accents are ignored, as in the server's index. The
 * query is prepared once, since the server grades thousands of hits for it.
 */
export function messageMatcher(query: string): (text: string) => MessageMatch | null {
  const { long, short, words } = messageSearchTokens(query);
  const tokens = [...long, ...short].map((token) => ({
    token,
    // Marks go from the folded token: lowercasing "İ" adds one.
    folded: foldInPlace(token).replace(COMBINING_MARKS, ""),
    nonAscii: NON_ASCII.test(token),
    mustStartWord: Array.from(token).length < MESSAGE_WORD_START_LENGTH,
    // Too short to search, so it only narrows: grading by it would reorder
    // results on each keystroke while the next word is typed ("nvme s").
    grades: long.includes(token),
  }));
  const phrase = messagePhrase(query);
  // Accents typed or left out still read as written together: "cafe open"
  // in "Café open".
  const foldedPhrase = messagePhrase(
    words.map((word) => foldInPlace(word).replace(COMBINING_MARKS, "")).join(" "),
  );
  const queryNonAscii = NON_ASCII.test(query);
  return (text) => {
    const lower = text.toLowerCase();
    // "İ" lowercases to two units, which would shift every offset after it.
    const plain = lower.length === text.length ? lower : foldInPlace(text);
    let folded: string | null = null;
    let quality = 1;
    const positions: Array<ReadonlyArray<number>> = [];
    for (const { token, folded: foldedToken, nonAscii, mustStartWord, grades } of tokens) {
      let found = findMessageToken(text, plain, token, tokens.length === 1);
      // Accents typed or left out: "cafe" finds "Café", also after "cafeteria".
      if (found?.quality !== 1 && foldedToken.length > 0 && (nonAscii || NON_ASCII.test(text))) {
        found = findMessageToken(
          text,
          (folded ??= foldInPlace(text)),
          foldedToken,
          tokens.length === 1,
        );
      }
      if (found === null) return null;
      if (found.quality === MID_WORD && mustStartWord) return null;
      if (grades) quality = Math.min(quality, found.quality);
      positions.push(found.at);
    }
    // Written together as typed: the snippet starts there. Apostrophes are
    // straight in the query, and straightening keeps offsets.
    const straight = (value: string) => value.replace(CURLY_APOSTROPHES, "'");
    const together =
      phrase?.exec(straight(plain)) ??
      (queryNonAscii || NON_ASCII.test(text)
        ? foldedPhrase?.exec(straight((folded ??= foldInPlace(text))))
        : null);
    if (together) return { quality: quality + MESSAGE_PHRASE_BONUS, offset: together.index };
    // Else the shortest stretch that holds every word: the snippet starts
    // there, so it shows them all, and words close together rank above words
    // far apart ("lakebed perf").
    const near = shortestSpan(positions);
    return {
      quality:
        long.length > 1 && near.length <= MESSAGE_NEAR_SPAN
          ? quality + MESSAGE_NEAR_BONUS
          : quality,
      offset: near.start,
    };
  };
}

// The shortest stretch of text holding one place of each word, from each
// word's places in order.
function shortestSpan(places: ReadonlyArray<ReadonlyArray<number>>): {
  readonly start: number;
  readonly length: number;
} {
  const hits = places
    .flatMap((at, word) => at.map((index) => ({ index, word })))
    .sort((left, right) => left.index - right.index);
  const counts = places.map(() => 0);
  let covered = 0;
  let best = { start: hits[0]?.index ?? 0, length: Number.POSITIVE_INFINITY };
  let left = 0;
  for (const hit of hits) {
    counts[hit.word] = (counts[hit.word] ?? 0) + 1;
    if (counts[hit.word] === 1) covered++;
    while (covered === places.length) {
      const first = hits[left]!;
      if (hit.index - first.index < best.length) {
        best = { start: first.index, length: hit.index - first.index };
      }
      counts[first.word] = (counts[first.word] ?? 1) - 1;
      if (counts[first.word] === 0) covered--;
      left++;
    }
  }
  return best;
}

/**
 * Ranges of `text` that contain a long message search token, for message
 * snippets, ignoring case and accents. Shorter tokens would light up half the
 * snippet, and a short long token only counts where it starts a word.
 * Snippets vary per query, so they skip the field cache.
 */
export function findSearchTokenRanges(text: string, query: string): SearchRange[] {
  const tokens = new Map(
    messageSearchTokens(query)
      .long.map(
        (token) =>
          [foldSearchQuery(token), Array.from(token).length < MESSAGE_WORD_START_LENGTH] as const,
      )
      // Some tokens fold to nothing ("´´´"), which would match everywhere.
      .filter(([token]) => token.length > 0),
  );
  if (tokens.size === 0) return [];
  const field = foldSearchField(text);
  const ranges: SearchRange[] = [];
  for (const [token, needsWordStart] of tokens) {
    // A token that opens with punctuation brings its own boundary, as in scoring.
    const ownBoundary = !ALPHANUMERIC.test(token[0]!) && !SYMBOL.test(token[0]!);
    for (let index = field.text.indexOf(token); index !== -1;) {
      if (needsWordStart && !ownBoundary && !field.wordStarts[index]) {
        index = field.text.indexOf(token, index + 1);
        continue;
      }
      ranges.push({ start: index, end: index + token.length });
      index = field.text.indexOf(token, index + token.length);
    }
  }
  return mergeRanges(ranges);
}

export interface SearchTextPart {
  readonly text: string;
  readonly highlighted: boolean;
  readonly start: number;
}

/** `text` cut into plain and highlighted parts at sorted, non-overlapping `ranges`. */
export function splitSearchText(
  text: string,
  ranges: ReadonlyArray<SearchRange>,
): SearchTextPart[] {
  const parts: SearchTextPart[] = [];
  let cursor = 0;
  for (const range of ranges) {
    if (range.start > cursor) {
      parts.push({ text: text.slice(cursor, range.start), highlighted: false, start: cursor });
    }
    parts.push({ text: text.slice(range.start, range.end), highlighted: true, start: range.start });
    cursor = range.end;
  }
  if (cursor < text.length || parts.length === 0) {
    parts.push({ text: text.slice(cursor), highlighted: false, start: cursor });
  }
  return parts;
}

const DAY_MS = 24 * 60 * 60 * 1000;
/** Both activity recency and open counts halve every two weeks. */
export const SEARCH_RECENCY_HALF_LIFE_MS = 14 * DAY_MS;
/**
 * Opens closer together than this count once, so flipping between threads is
 * not frequency. Clients skip sending them.
 */
export const THREAD_OPEN_DEDUPE_MS = 10 * 60 * 1000;
const THREAD_SEARCH_PICK_LIMIT = 3;
/** Picked queries are stored this long; clients send no more. */
const THREAD_SEARCH_PICK_MAX_LENGTH = 32;

/**
 * `query` as a pick is stored and compared: folded, then cut to the stored
 * length without splitting an emoji in two. Clients and the server both use
 * it, so a long pick matches its query again.
 */
export function pickedQuery(query: string): string {
  const cut = foldSearchQuery(query).slice(0, THREAD_SEARCH_PICK_MAX_LENGTH);
  return (/[\ud800-\udbff]$/.test(cut) ? cut.slice(0, -1) : cut).trim();
}

function decay(ageMs: number): number {
  return 2 ** (-Math.max(0, ageMs) / SEARCH_RECENCY_HALF_LIFE_MS);
}

/** Server-stored open history; see `OrchestrationV2ThreadOpens`. */
export type ThreadOpenStats = OrchestrationV2ThreadOpens;

/**
 * Next open stats after an open at `at`. `query` is the palette query that
 * picked the thread, when it was opened from search.
 */
export function recordThreadOpen(
  previous: ThreadOpenStats | null,
  at: number,
  query: string | undefined,
): ThreadOpenStats {
  const pick = pickedQuery(query ?? "");
  // Picks that no longer count are not kept or synced.
  const earlier = (previous?.picks ?? []).filter((entry) => at - entry.at <= PICK_WINDOW_MS);
  const picks = pick
    ? [{ query: pick, at }, ...earlier.filter((entry) => entry.query !== pick)].slice(
        0,
        THREAD_SEARCH_PICK_LIMIT,
      )
    : earlier;
  if (previous !== null && at - previous.openedAt < THREAD_OPEN_DEDUPE_MS) {
    return { ...previous, picks };
  }
  const score = previous === null ? 1 : previous.score * decay(at - previous.openedAt) + 1;
  return { openedAt: at, score, picks };
}

export interface ThreadSearchSubject {
  /** Matched only by the whole query, like references. */
  readonly id?: string;
  readonly title: string;
  readonly branch?: string | null;
  readonly projectTitle?: string | null;
  /** Only set with two or more environments; it tells same-named threads apart. */
  readonly environmentLabel?: string | null;
  readonly pullRequests?: ReadonlyArray<{
    readonly number: number;
    readonly title?: string | null;
    /** Values such as URLs, matched only by the whole query. */
    readonly references?: ReadonlyArray<string>;
  }>;
  /** Latest user activity, in epoch ms. */
  readonly activityAt: number | null;
  readonly opens?: ThreadOpenStats | null;
}

// Use reorders matches of about the same quality but never turns a mid-word
// hit on a busy thread into a better result than a whole word on a quiet one.
const USE_BOOST_LIMIT = 2.5;

/**
 * How much use lifts a thread: 1 for a stale, never-opened thread, about 2 for
 * one active today, and up to 2.5 for threads opened often.
 */
function threadUsageBoost(thread: ThreadSearchSubject, now: number): number {
  const recency = thread.activityAt === null ? 0 : decay(now - thread.activityAt);
  const opens = thread.opens ? thread.opens.score * decay(now - thread.opens.openedAt) : 0;
  return Math.min(USE_BOOST_LIMIT, 1 + recency + 0.5 * Math.log2(1 + opens));
}

const REFERENCE_PREFIX_MIN = 8;

// A number is never cut short: ".../pull/2288" is not pull request 22889.
const notCut = (text: string, end: number) => !DIGIT.test(text[end] ?? "");

// IDs and URLs have many word starts, so field matching would let short queries hit every thread.
// Require a long prefix, or any long part containing a digit. Both are ASCII; lowercasing suffices.
function matchReference(
  normalizedQuery: string,
  thread: ThreadSearchSubject,
): SearchFieldsMatch | null {
  if (normalizedQuery.length < REFERENCE_PREFIX_MIN) return null;
  const anywhere = DIGIT.test(normalizedQuery);
  const matches = (reference: string) => {
    const folded = reference.toLowerCase();
    const at = folded.indexOf(normalizedQuery);
    // A pasted link may go on past the reference: ".../pull/22889/files".
    return anywhere
      ? (at !== -1 && notCut(folded, at + normalizedQuery.length)) ||
          (normalizedQuery.startsWith(folded) && notCut(normalizedQuery, folded.length))
      : at === 0;
  };
  return (thread.id && matches(thread.id)) ||
    thread.pullRequests?.some((pullRequest) => pullRequest.references?.some(matches))
    ? { quality: 0.6, strong: true, primaryRanges: [] }
    : null;
}

// Picks expire from the pick time; opening a thread another way must not extend their priority.
// They reorder word matches within a group, never the groups themselves.
const PICK_WINDOW_MS = 21 * DAY_MS;
// The start of a picked query counts from three letters: "n" is too little to
// go on.
const PICK_PREFIX_MIN_LENGTH = 3;

/** The latest pick of the thread for this query, while it lasts. */
function activePick(
  thread: ThreadSearchSubject,
  normalizedQuery: string,
  now: number,
): ThreadOpenStats["picks"][number] | undefined {
  // Stored picks are cut to a length, so compare the query cut the same way.
  const query = pickedQuery(normalizedQuery);
  const prefix = query.length >= PICK_PREFIX_MIN_LENGTH;
  // The latest exact pick, else the latest pick the query starts.
  let exact: ThreadOpenStats["picks"][number] | undefined;
  let latest: ThreadOpenStats["picks"][number] | undefined;
  for (const pick of thread.opens?.picks ?? []) {
    if (now - pick.at > PICK_WINDOW_MS) continue;
    if (pick.query === query && (exact === undefined || pick.at > exact.at)) exact = pick;
    const matches = pick.query === query || (prefix && pick.query.startsWith(query));
    if (matches && (latest === undefined || pick.at > latest.at)) latest = pick;
  }
  return exact ?? latest;
}

export interface ThreadSearchMatch {
  /** Match quality times use; what results sort by. */
  readonly score: number;
  /** Match quality alone; see `rankSearchGroups`. */
  readonly quality: number;
  /** Every token matched at a word start; see `rankSearchGroups`. */
  readonly strong: boolean;
  /** Matched ranges in the title. */
  readonly ranges: ReadonlyArray<SearchRange>;
  /**
   * Why the thread matched when its title shows no match, for the result row.
   * Built on demand, so only the rows shown pay for it.
   */
  readonly explain?: () => SearchMatchHint | undefined;
  /** When the thread was picked for this query, while that pick lasts; see `rankSearchGroups`. */
  readonly pickedAt?: number;
  /** Picked for exactly this query, before newer picks for longer ones; see `rankSearchGroups`. */
  readonly pickedExactly?: boolean;
  /** Below the whole-name class; see `scoreThreadSearch`. */
  readonly groupQuality: number;
}

export interface SearchMatchHint {
  readonly label: string;
  readonly text: string;
  readonly ranges: ReadonlyArray<SearchRange>;
}

// Most threads' branches start with the app's own worktree prefix ("t3/", and
// "t3code/" before it), so "t3 connect" would match nearly every thread.
// Only before more text, so typing "t3/" does not empty the list for a keystroke.
const WORKTREE_BRANCH_PREFIX_PATTERN = new RegExp(`^(?:${WORKTREE_BRANCH_PREFIX}|t3code)/(?=\\S)`);

function searchableBranch(branch: string | null | undefined): string | null {
  return branch ? branch.replace(WORKTREE_BRANCH_PREFIX_PATTERN, "") : null;
}

/**
 * The field that explains a match whose title shows none: the first that holds
 * the whole query, else, past the words the project or environment holds, the
 * first that holds the rest ("lakebed perf" in project "lakebed" with the PR
 * title "perf: …").
 */
function matchHint(
  normalizedQuery: string,
  thread: ThreadSearchSubject,
  typos: boolean,
): SearchMatchHint | undefined {
  const candidates: Array<{ readonly label: string; readonly text: string | null | undefined }> = [
    ...(thread.pullRequests ?? []).map((pullRequest) => ({
      label: "PR",
      text: `#${pullRequest.number}${pullRequest.title ? ` ${pullRequest.title}` : ""}`,
    })),
    { label: "Branch", text: searchableBranch(thread.branch) },
    { label: "Project", text: thread.projectTitle },
    { label: "Environment", text: thread.environmentLabel },
  ];
  const holds = (text: string, query: string) =>
    matchSearchFields(query, [{ value: text, weight: 1 }], { typos })?.primaryRanges;
  const hintFor = (query: string) => {
    for (const { label, text } of candidates) {
      const ranges = text ? holds(text, query) : undefined;
      if (text && ranges) return { label, text, ranges };
    }
    return undefined;
  };
  const whole = hintFor(normalizedQuery);
  if (whole) return whole;
  const contexts = [thread.projectTitle, thread.environmentLabel].filter(
    (text): text is string => !!text,
  );
  const rest = normalizedQuery
    .split(" ")
    .filter((token) => !contexts.some((text) => holds(text, token)))
    .join(" ");
  return rest && rest !== normalizedQuery ? hintFor(rest) : undefined;
}

// A keystroke scores each thread's fields again, so they are listed once per subject.
const threadFieldsCache = new WeakMap<ThreadSearchSubject, ReadonlyArray<WeightedSearchField>>();

function threadSearchFields(thread: ThreadSearchSubject): ReadonlyArray<WeightedSearchField> {
  const cached = threadFieldsCache.get(thread);
  if (cached) return cached;
  const fields: WeightedSearchField[] = [{ value: thread.title, weight: 1, midWord: true }];
  for (const pullRequest of thread.pullRequests ?? []) {
    fields.push({ value: `#${pullRequest.number}`, weight: 1 });
    if (pullRequest.title) fields.push({ value: pullRequest.title, weight: 0.5 });
  }
  const branch = searchableBranch(thread.branch);
  if (branch) fields.push({ value: branch, weight: 0.6 });
  if (thread.projectTitle) {
    fields.push({ value: thread.projectTitle, weight: 0.25, context: true });
  }
  if (thread.environmentLabel) {
    fields.push({ value: thread.environmentLabel, weight: 0.25, context: true });
  }
  threadFieldsCache.set(thread, fields);
  return fields;
}

let lastFieldQuery: { readonly query: string; readonly fieldQuery: string } | undefined;

// Strip pull request prefixes and the worktree prefix so queries match the stored fields.
function threadFieldQuery(normalizedQuery: string): string {
  if (lastFieldQuery?.query !== normalizedQuery) {
    lastFieldQuery = {
      query: normalizedQuery,
      fieldQuery: normalizedQuery
        .replace(/^(?:pr|pull request|pull)\s*(?=#?\d)/, "")
        .replace(/^#\s*/, "")
        .replace(WORKTREE_BRANCH_PREFIX_PATTERN, ""),
    };
  }
  return lastFieldQuery.fieldQuery;
}

/**
 * Scores a thread for a normalized query, or null when it does not match.
 * Titles and pull request numbers count fully, pull request titles and
 * branches less, project and environment names least.
 */
export function scoreThreadSearch(
  normalizedQuery: string,
  thread: ThreadSearchSubject,
  now: number,
  options?: {
    readonly typos?: boolean;
    /**
     * Palette picks; off where a pick would show up unexplained, such as a
     * sidebar filter or an agent's search.
     */
    readonly picks?: boolean;
  },
): ThreadSearchMatch | null {
  const fields = threadSearchFields(thread);
  const fieldQuery = threadFieldQuery(normalizedQuery);
  const fieldMatch = matchSearchFields(fieldQuery, fields, options);
  const referenceMatch = fieldMatch ? null : matchReference(normalizedQuery, thread);
  const match = fieldMatch ?? referenceMatch;
  if (match === null) return null;
  // A row whose title shows no match must say why. With several words, one
  // that cannot (its words spread over unrelated fields) is a coincidence and
  // is left out; a single word always sits in the field that matched it, so
  // its hint waits until the row is shown.
  const typos = options?.typos ?? false;
  const titleShowsMatch = match.primaryRanges.length > 0;
  const checkHint = !titleShowsMatch && referenceMatch === null && fieldQuery.includes(" ");
  const checkedHint = checkHint ? matchHint(fieldQuery, thread, typos) : undefined;
  if (checkHint && checkedHint === undefined) return null;
  const explain = titleShowsMatch
    ? undefined
    : (): SearchMatchHint | undefined =>
        referenceMatch
          ? { label: "ID or link", text: normalizedQuery, ranges: [] }
          : (checkedHint ?? matchHint(fieldQuery, thread, typos));
  const pick = options?.picks === false ? undefined : activePick(thread, normalizedQuery, now);
  return {
    score: match.quality * threadUsageBoost(thread, now),
    quality: match.quality,
    // A thread's whole title never lifts its group over a command or project
    // of that name: every new thread is titled "New thread" for a while.
    groupQuality: Math.min(match.quality, WHOLE_NAME - 0.01),
    strong: match.strong,
    ranges: match.primaryRanges,
    ...(explain ? { explain } : {}),
    ...(pick ? { pickedAt: pick.at } : {}),
    ...(pick?.query === pickedQuery(normalizedQuery) ? { pickedExactly: true } : {}),
  };
}

/** When the user last used a thread: their last message or their last open. */
export function threadRecentUse(thread: ThreadSearchSubject): number {
  return Math.max(thread.activityAt ?? 0, thread.opens?.openedAt ?? 0);
}

/**
 * How strongly a thread's messages match among matches of one quality: a
 * thread that keeps using the word outweighs a recent passing mention, as
 * hits count for more than recency or use (21 hits about 5.5, one hit 2).
 */
function messageMatchWeight(hits: number): number {
  return 1 + Math.log2(1 + hits);
}

/** `withoutTitleMatches` reserves message rows for threads the palette has not already listed. */
export function rankMessageMatches<
  T extends {
    readonly quality?: number;
    readonly hits?: number;
    readonly messageCreatedAt?: string | null;
  },
>(
  matches: ReadonlyArray<T>,
  subjectOf: (match: T) => ThreadSearchSubject | undefined,
  normalizedQuery: string,
  now: number,
  options?: { readonly picks?: boolean; readonly withoutTitleMatches?: boolean },
): T[] {
  return matches
    .flatMap((match) => {
      const subject = subjectOf(match);
      if (!subject) return [];
      if (
        options?.withoutTitleMatches &&
        scoreThreadSearch(normalizedQuery, subject, now, { picks: false }) !== null
      ) {
        return [];
      }
      // Older servers send no quality; their matches count as words.
      const quality = match.quality ?? 1;
      return [
        {
          match,
          quality,
          pickedAt:
            options?.picks === false ? 0 : (activePick(subject, normalizedQuery, now)?.at ?? 0),
          score: messageMatchWeight(match.hits ?? 1) * threadUsageBoost(subject, now),
        },
      ];
    })
    .sort(
      (left, right) =>
        // Word matches first; among them a pick, then the closer match.
        Number(right.quality >= MESSAGE_PREFIX) - Number(left.quality >= MESSAGE_PREFIX) ||
        right.pickedAt - left.pickedAt ||
        right.quality - left.quality ||
        right.score - left.score ||
        (right.match.messageCreatedAt ?? "").localeCompare(left.match.messageCreatedAt ?? ""),
    )
    .map(({ match }) => match);
}

/** Palette limits shared by web and mobile. */
export const PALETTE_THREAD_LIMIT = 20;
export const PALETTE_MESSAGE_LIMIT = 10;
/** Next to matching threads, other groups show only their best few rows. */
export const PALETTE_SECONDARY_LIMIT = 3;

// Whole words and prefixes share a class so "Compact" does not lift settings over "Compaction".
function matchClass(quality: number): number {
  return quality >= WHOLE_NAME ? 3 : quality >= 0.7 ? 2 : quality >= 0.4 ? 1 : 0;
}

export interface RankedSearchItem<T, M> {
  readonly item: T;
  readonly match: M;
}

/**
 * Rank groups by match class to keep typing stable and thread use from outweighing equal commands.
 * Try typos only without word-start matches: they add noise beside real matches and cost per key.
 */
export function rankSearchGroups<
  G,
  T,
  M extends {
    readonly score: number;
    readonly quality: number;
    readonly strong: boolean;
    readonly pickedAt?: number;
    readonly pickedExactly?: boolean;
    readonly groupQuality?: number;
  },
>(
  groups: ReadonlyArray<{ readonly group: G; readonly items: ReadonlyArray<T> }>,
  score: (item: T, options: { readonly typos: boolean }, group: G) => M | null,
): Array<{ readonly group: G; readonly ranked: ReadonlyArray<RankedSearchItem<T, M>> }> {
  const rank = (typos: boolean) =>
    groups.map(({ group, items }) => {
      const options = { typos };
      const ranked: Array<RankedSearchItem<T, M>> = [];
      for (const item of items) {
        const match = score(item, options, group);
        if (match !== null) ranked.push({ item, match });
      }
      return { group, ranked };
    });
  let ranked = rank(false);
  if (!ranked.some((entry) => entry.ranked.some(({ match }) => match.strong))) {
    ranked = rank(true);
  }
  return ranked
    .flatMap(({ group, ranked: items }, order) => {
      if (items.length === 0) return [];
      // Use cannot lift a project-only match above a title match or cross match classes.
      // Picks reorder word matches, keeping typos and mid-word hits below them.
      // A longer-query pick must not pass a whole-name match for the current query.
      const wordMatch = (match: M) => Math.min(matchClass(match.quality), 2);
      const exactPickAt = (match: M) => (match.pickedExactly ? (match.pickedAt ?? 0) : 0);
      const sorted = [...items].sort(
        (left, right) =>
          wordMatch(right.match) - wordMatch(left.match) ||
          exactPickAt(right.match) - exactPickAt(left.match) ||
          matchClass(right.match.quality) - matchClass(left.match.quality) ||
          (right.match.pickedAt ?? 0) - (left.match.pickedAt ?? 0) ||
          right.match.score - left.match.score,
      );
      const best = Math.max(
        ...items.map(({ match }) => matchClass(match.groupQuality ?? match.quality)),
      );
      return [{ group, ranked: sorted, best, order }];
    })
    .sort((left, right) => right.best - left.best || left.order - right.order)
    .map(({ group, ranked: items }) => ({ group, ranked: items }));
}

/** `rankSearchGroups` for a single list. */
export function rankSearchItems<
  T,
  M extends { readonly score: number; readonly quality: number; readonly strong: boolean },
>(
  items: ReadonlyArray<T>,
  score: (item: T, options: { readonly typos: boolean }) => M | null,
): ReadonlyArray<RankedSearchItem<T, M>> {
  return rankSearchGroups([{ group: null, items }], score)[0]?.ranked ?? [];
}

export interface SearchTermsMatch {
  readonly score: number;
  readonly quality: number;
  /** The quality its group ranks by, when lower; see `scoreSearchTerms`. */
  readonly groupQuality?: number;
  readonly strong: boolean;
  readonly ranges: ReadonlyArray<SearchRange>;
}

const KEYWORD_QUALITY = 0.65;
// Below this, keyword prefixes match too much: "co" or "pro" would list most
// settings. A short query still matches a keyword it equals ("pr").
const KEYWORD_QUERY_MIN_LENGTH = 4;

/**
 * Keywords count less so hidden terms cannot lift a group above a matching name.
 * Short queries need whole keywords to avoid listing most settings for common prefixes.
 */
export function scoreSearchTerms(
  normalizedQuery: string,
  terms: ReadonlyArray<string>,
  options?: { readonly typos?: boolean },
): SearchTermsMatch | null {
  // Filler words ("the ci") do not make a short query long.
  const meaningful = normalizedQuery
    .split(" ")
    .filter((token) => !FILLER_WORDS.has(token))
    .join(" ");
  const short = (meaningful || normalizedQuery).length < KEYWORD_QUERY_MIN_LENGTH;
  const match = matchSearchFields(
    normalizedQuery,
    terms.map((value, index) =>
      index === 0
        ? { value, weight: 1 }
        : // An alias typed in full ("pr") is deliberate, above a mere name prefix.
          { value, weight: short ? 0.8 : 0.6, wholeWords: short, keyword: true },
    ),
    options,
  );
  return (
    match && {
      score: match.quality,
      quality: match.quality,
      // Below the word-start class: a match only in hidden keywords must not put
      // its group above a result whose name matches. Inside the group an exact
      // alias still beats a name prefix ("pr" lists "Open pull requests" first).
      ...(match.primaryRanges.length > 0
        ? {}
        : { groupQuality: Math.min(match.quality, KEYWORD_QUALITY) }),
      strong: match.strong,
      ranges: match.primaryRanges,
    }
  );
}