sailfork / t3code-github / packages/ shared/ src/ paletteSearch.ts
/** 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, "\\Loading Sailfork
amp;"))
.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,
}
);
}