1/** Shared ranking keeps command palettes and MCP thread search consistent across surfaces. */
2
3import type { OrchestrationV2ThreadOpens } from "@t3tools/contracts";
4
5import { WORKTREE_BRANCH_PREFIX } from "./git.ts";
6
7const ALPHANUMERIC = /[\p{L}\p{N}]/u;
8const LOWERCASE = /\p{Ll}/u;
9const UPPERCASE = /\p{Lu}/u;
10const DIGIT = /\p{N}/u;
11const LETTER = /\p{L}/u;
12const COMBINING_MARKS = /\p{M}/gu;
13// Emoji and other symbols can be searched for, so they start words too.
14const SYMBOL = /\p{So}/u;
15const APOSTROPHE = /['’]/;
16const CURLY_APOSTROPHES = /[\u2018\u2019]/g;
17
18interface SearchField {
19 /** Case- and accent-folded text, one UTF-16 unit per source unit. */
20 readonly text: string;
21 /** 1 where a word starts in `text`. */
22 readonly wordStarts: Uint8Array;
23}
24
25export interface SearchRange {
26 readonly start: number;
27 readonly end: number;
28}
29
30// Thread titles, branches, and project names repeat across keystrokes; folding
31// them once keeps a keystroke to plain string scans. Each keystroke reads every
32// field, so the limit must hold all of them or the cache clears every time; a
33// field is a few bytes per character.
34const fieldCache = new Map<string, SearchField>();
35const FIELD_CACHE_LIMIT = 100_000;
36
37function foldCharacter(character: string): string {
38 // A typed straight apostrophe finds a curly one: iOS keyboards type "’".
39 return character
40 .normalize("NFKD")
41 .replace(COMBINING_MARKS, "")
42 .toLowerCase()
43 .replace("ς", "σ")
44 .replace(/[‘’]/, "'");
45}
46
47/**
48 * `text` with case and accents folded one UTF-16 unit at a time, so offsets
49 * and word starts still read from `text` and highlights need no mapping. A
50 * letter that folds to more or less than one unit ("ß", "fi") stays as it is.
51 */
52function foldInPlace(text: string): string {
53 return text
54 .replace(/[\u0080-\uffff]/g, (character) => {
55 const folded = foldCharacter(character);
56 return folded.length === 1 ? folded : character;
57 })
58 .toLowerCase();
59}
60
61// Chinese and Japanese text has no spaces, so each ideograph or kana starts a word.
62function isCjk(character: string): boolean {
63 const code = character.codePointAt(0)!;
64 return (
65 (code >= 0x3040 && code <= 0x30ff) ||
66 (code >= 0x3400 && code <= 0x4dbf) ||
67 (code >= 0x4e00 && code <= 0x9fff) ||
68 (code >= 0xf900 && code <= 0xfaff)
69 );
70}
71
72// Two Chinese, Japanese, or Korean characters already make a common word.
73function hasCjkWord(token: string): boolean {
74 return Array.from(token).some((character) => {
75 const code = character.codePointAt(0)!;
76 return isCjk(character) || (code >= 0xac00 && code <= 0xd7af);
77 });
78}
79
80/**
81 * Whether `character` starts a word after `previous` and `beforePrevious`
82 * ("" at the start): after a non-letter, at a camelCase or digit boundary, or
83 * at any Chinese or Japanese character. The one rule for titles and messages.
84 */
85function isWordStart(
86 beforePrevious: string,
87 previous: string,
88 character: string,
89 next: string,
90): boolean {
91 // "Julius’s": a possessive or contraction does not start a word.
92 const afterApostrophe = APOSTROPHE.test(previous) && ALPHANUMERIC.test(beforePrevious);
93 return (
94 (ALPHANUMERIC.test(character) || SYMBOL.test(character)) &&
95 !afterApostrophe &&
96 (previous === "" ||
97 !ALPHANUMERIC.test(previous) ||
98 (LOWERCASE.test(previous) && UPPERCASE.test(character)) ||
99 // The last capital of an acronym starts the next word: "JSONSchema".
100 (UPPERCASE.test(previous) && UPPERCASE.test(character) && LOWERCASE.test(next)) ||
101 DIGIT.test(previous) !== DIGIT.test(character) ||
102 isCjk(character))
103 );
104}
105
106function foldSearchField(source: string): SearchField {
107 const wordStarts = new Uint8Array(source.length);
108 const characters = Array.from(source);
109 let index = 0;
110 for (const [position, character] of characters.entries()) {
111 const previous = characters[position - 1] ?? "";
112 const next = characters[position + 1] ?? "";
113 if (isWordStart(characters[position - 2] ?? "", previous, character, next)) {
114 wordStarts[index] = 1;
115 }
116 index += character.length;
117 }
118 return { text: foldInPlace(source), wordStarts };
119}
120
121function prepareSearchField(source: string): SearchField {
122 const cached = fieldCache.get(source);
123 if (cached) return cached;
124 // Oldest first out. A read does not re-insert: that would cost more than the
125 // fold it saves, and the limit holds far more fields than a keystroke reads.
126 if (fieldCache.size >= FIELD_CACHE_LIMIT) {
127 fieldCache.delete(fieldCache.keys().next().value!);
128 }
129 const field = foldSearchField(source);
130 fieldCache.set(source, field);
131 return field;
132}
133
134// Quotes around a pasted query: "fix sidebar".
135const WRAPPING_QUOTES = /^\s*["'`“”‘’]+|["'`“”‘’]+\s*$/g;
136
137/** Folded, whitespace-collapsed query; empty when there is nothing to match. */
138export function foldSearchQuery(query: string): string {
139 return foldInPlace(query.replace(WRAPPING_QUOTES, "").normalize("NFC"))
140 .split(/\s+/)
141 .filter((token) => token.length > 0)
142 .join(" ");
143}
144
145function wordEnd(field: SearchField, index: number): number {
146 let end = index + 1;
147 while (end < field.text.length && !field.wordStarts[end] && ALPHANUMERIC.test(field.text[end]!)) {
148 end++;
149 }
150 return end;
151}
152
153// One substitution, insertion, deletion, or swap of neighbours; with
154// `swapOnly`, only a swap.
155function withinOneEdit(left: string, right: string, swapOnly: boolean): boolean {
156 if (Math.abs(left.length - right.length) > (swapOnly ? 0 : 1)) return false;
157 let index = 0;
158 while (index < left.length && index < right.length && left[index] === right[index]) index++;
159 const restLeft = left.slice(index);
160 const restRight = right.slice(index);
161 const swapped =
162 restLeft.length > 1 &&
163 restLeft[0] === restRight[1] &&
164 restLeft[1] === restRight[0] &&
165 restLeft.slice(2) === restRight.slice(2);
166 if (swapOnly) return swapped;
167 return (
168 swapped ||
169 restLeft === restRight ||
170 restLeft.slice(1) === restRight.slice(1) ||
171 restLeft.slice(1) === restRight ||
172 restLeft === restRight.slice(1)
173 );
174}
175
176const WHOLE_WORD = 1;
177// The bonus for a field equal to the whole query lifts a whole word to this.
178const WHOLE_NAME = 1.5;
179const MID_WORD = 0.3;
180const TYPO = 0.45;
181// Whole words typed together are exact, so they rank with typos and above
182// mid-word hits, though below a match at a word start.
183const JOINED_WORDS = 0.6;
184
185interface TokenMatch extends SearchRange {
186 readonly score: number;
187 /** Separate ranges, for words typed together. */
188 readonly letters?: ReadonlyArray<SearchRange>;
189}
190
191/**
192 * Mid-word hits need four or more characters and `midWord`, so "del" does not find "model".
193 * Typos preserve the first letter except for swaps; short tokens allow fewer edits to limit noise.
194 * Numbers never match with a typo because different pull request numbers must stay distinct.
195 */
196function matchToken(
197 field: SearchField,
198 token: string,
199 typos: boolean,
200 isPrimary: boolean,
201 midWord: boolean,
202): TokenMatch | null {
203 if (token.length === 0) return null;
204 let best: TokenMatch | null = null;
205 let ownBoundary: boolean | undefined;
206 for (
207 let index = field.text.indexOf(token);
208 index !== -1;
209 index = field.text.indexOf(token, index + 1)
210 ) {
211 // A token that opens with punctuation (".ts") brings its own boundary, as in messages.
212 if (
213 field.wordStarts[index] ||
214 (ownBoundary ??= !ALPHANUMERIC.test(token[0]!) && !SYMBOL.test(token[0]!))
215 ) {
216 // Whole when the match ends where a word ends: "t3c" is a prefix of
217 // "t3code", ".ts" whole in "index.ts" but a prefix in "parser.tsx".
218 const end = index + token.length;
219 const whole =
220 end >= field.text.length ||
221 field.wordStarts[end] === 1 ||
222 !ALPHANUMERIC.test(field.text[end]!);
223 let runEnd = end;
224 while (runEnd < field.text.length && ALPHANUMERIC.test(field.text[runEnd]!)) runEnd++;
225 const score = whole ? WHOLE_WORD : 0.7 + (0.2 * token.length) / (runEnd - index);
226 if (best === null || score > best.score) {
227 best = { score, start: index, end: index + token.length };
228 }
229 if (score === WHOLE_WORD) return best;
230 } else if (midWord && token.length >= 4 && best === null) {
231 best = { score: MID_WORD, start: index, end: index + token.length };
232 }
233 }
234 // Joined words are exact, so they count without the typo pass: a strong
235 // match elsewhere must not hide "VS Code" for "vscode".
236 if ((best === null || best.score <= MID_WORD) && isPrimary) {
237 const joined = matchJoinedWords(field, token);
238 if (joined) return joined;
239 }
240 if ((best !== null && best.score > MID_WORD) || !typos || token.length < 3) return best;
241 // Numbers skip typos to keep pull requests distinct. Words with digits ("t3code") do not.
242 if (LETTER.test(token)) {
243 for (let index = 0; index < field.text.length; index++) {
244 if (!field.wordStarts[index]) continue;
245 // People rarely mistype the first letter, so a typo keeps it, unless it
246 // swaps the first two of a longer word ("ing" is not "nig…").
247 const first = field.text[index];
248 const firstLetterKept =
249 first === token[0] ||
250 (token.length > 3 && first === token[1] && field.text[index + 1] === token[0]);
251 if (!firstLetterKept) continue;
252 // The whole run, across camelCase joins: "githbu" is "GitHub".
253 let runEnd = index + 1;
254 while (runEnd < field.text.length && ALPHANUMERIC.test(field.text[runEnd]!)) runEnd++;
255 const word = field.text.slice(index, runEnd);
256 // Short tokens forgive a swapped pair or one missing letter ("srv" for
257 // "serv…"); any other edit of a three- or four-letter word matches too
258 // much ("cron" would find every "con…").
259 const short = token.length <= 4;
260 // The same length first, so "githbu" highlights all of "GitHub".
261 const lengths = short
262 ? [token.length, token.length + 1]
263 : [token.length, token.length - 1, token.length + 1];
264 for (const length of lengths) {
265 if (length > word.length) continue;
266 const prefix = word.slice(0, length);
267 if (withinOneEdit(token, prefix, short && length === token.length)) {
268 return { score: TYPO, start: index, end: index + length };
269 }
270 }
271 }
272 }
273 return best;
274}
275
276/**
277 * Short words followed by a short prefix are noise inside a title ("inth" in "in thread").
278 * Allow them at its start ("t3co"), before three letters ("gomod"), or a whole word ("vscode").
279 */
280function matchJoinedWords(field: SearchField, token: string): TokenMatch | null {
281 for (
282 let start = field.text.indexOf(token[0]!);
283 start !== -1;
284 start = field.text.indexOf(token[0]!, start + 1)
285 ) {
286 if (!field.wordStarts[start]) continue;
287 const runs: SearchRange[] = [];
288 let at = start;
289 let rest = token;
290 while (rest.length > 0 && at < field.text.length) {
291 const end = wordEnd(field, at);
292 if (rest.length <= end - at && field.text.startsWith(rest, at)) {
293 runs.push({ start: at, end: at + rest.length });
294 rest = "";
295 } else if (rest.startsWith(field.text.slice(at, end))) {
296 runs.push({ start: at, end });
297 rest = rest.slice(end - at);
298 at = end;
299 while (at < field.text.length && !field.wordStarts[at]) at++;
300 } else {
301 break;
302 }
303 }
304 const last = runs.at(-1);
305 if (rest.length > 0 || last === undefined || runs.length < 2) continue;
306 if (
307 last.end === wordEnd(field, last.start) ||
308 last.end - last.start >= 3 ||
309 start === field.wordStarts.indexOf(1) ||
310 runs.slice(0, -1).every((run) => run.end - run.start >= 3)
311 ) {
312 return { score: JOINED_WORDS, start, end: last.end, letters: runs };
313 }
314 }
315 return null;
316}
317
318interface WeightedSearchField {
319 readonly value: string;
320 /** `value` folded; set on first use, so fields kept across keystrokes fold once. */
321 prepared?: SearchField;
322 readonly weight: number;
323 /** Only a whole-word match counts, as for a short query against keywords. */
324 readonly wholeWords?: boolean;
325 /**
326 * Only a match at a word start counts, without typos: hidden keywords that
327 * matched loosely would list results the user cannot see why for.
328 */
329 readonly keyword?: boolean;
330 /**
331 * Where the thread lives (project, environment): it helps a match, but a
332 * word start there does not make the match strong, so it never turns off
333 * joined words or typos for the titles.
334 */
335 readonly context?: boolean;
336 /**
337 * A token of four or more letters may match inside a word here. Only thread
338 * titles allow it: inside a command name or a branch it reads as junk
339 * ("arch" in "Search").
340 */
341 readonly midWord?: boolean;
342}
343
344interface SearchFieldsMatch {
345 /** Roughly 0.3 (inside a word) to 1.5 (exact title). */
346 readonly quality: number;
347 /**
348 * Every non-filler token has three or more characters and matched a whole word at full
349 * weight, before phrase bonuses. Optional filler words don't count either way.
350 */
351 readonly wholeWords: boolean;
352 /** Every token matched at a word start, without a typo. */
353 readonly strong: boolean;
354 /** Source ranges matched in the first field, for highlighting. */
355 readonly primaryRanges: ReadonlyArray<SearchRange>;
356}
357
358function preparedField(weighted: WeightedSearchField): SearchField {
359 return (weighted.prepared ??= prepareSearchField(weighted.value));
360}
361
362const FILLER_WORDS = new Set(["a", "an", "and", "for", "in", "of", "on", "the", "to", "with"]);
363
364// Sorted, with overlapping ranges joined.
365function mergeRanges(ranges: ReadonlyArray<SearchRange>): SearchRange[] {
366 const merged: SearchRange[] = [];
367 for (const range of [...ranges].sort((left, right) => left.start - right.start)) {
368 const last = merged.at(-1);
369 if (last && range.start <= last.end) {
370 merged[merged.length - 1] = { start: last.start, end: Math.max(last.end, range.end) };
371 } else {
372 merged.push({ start: range.start, end: range.end });
373 }
374 }
375 return merged;
376}
377
378// A keystroke scores every thread for one query, so its tokens are split once.
379let lastQuery:
380 | { readonly query: string; readonly tokens: string[]; readonly fillerOptional: boolean }
381 | undefined;
382
383function queryTokens(normalizedQuery: string) {
384 if (lastQuery?.query !== normalizedQuery) {
385 const tokens = normalizedQuery.split(" ").filter((token) => token.length > 0);
386 // A phrase-style query ("fix the sidebar") carries filler words a name may
387 // leave out; they count where they match but are not required.
388 lastQuery = {
389 query: normalizedQuery,
390 tokens,
391 fillerOptional: tokens.some((token) => !FILLER_WORDS.has(token)),
392 };
393 }
394 return lastQuery;
395}
396
397/**
398 * Every query token must match some field. Quality is the mean of each token's
399 * best weighted match, plus a bonus when the first field holds the whole query
400 * as a phrase or equals it.
401 */
402function matchSearchFields(
403 normalizedQuery: string,
404 fields: ReadonlyArray<WeightedSearchField>,
405 options?: { readonly typos?: boolean },
406): SearchFieldsMatch | null {
407 if (normalizedQuery.length === 0) return null;
408 const primary = fields[0]?.value ? preparedField(fields[0]) : undefined;
409 // An empty token would match everywhere, and loop forever in `matchToken`.
410 const { tokens, fillerOptional } = queryTokens(normalizedQuery);
411 if (tokens.length === 0) return null;
412 const primaryRanges: SearchRange[] = [];
413 let total = 0;
414 let counted = 0;
415 let notWhole = false;
416 let strong = true;
417 for (const token of tokens) {
418 let best = 0;
419 let bestPrimary: TokenMatch | null = null;
420 let atWordStart = false;
421 for (const weighted of fields) {
422 if (weighted.value.length === 0) continue;
423 const { weight, wholeWords, keyword, context, midWord } = weighted;
424 const field = preparedField(weighted);
425 if (best >= weight && field !== primary && atWordStart) continue;
426 const typos = (options?.typos ?? false) && !keyword;
427 // Joined words only count in the name.
428 const match = matchToken(field, token, typos, field === primary, midWord ?? false);
429 if (match === null || match.score < (wholeWords ? WHOLE_WORD : keyword ? 0.7 : 0)) continue;
430 if (field === primary) bestPrimary = match;
431 if (match.score >= 0.7 && !context) atWordStart = true;
432 if (match.score * weight > best) best = match.score * weight;
433 }
434 if (best === 0) {
435 if (fillerOptional && FILLER_WORDS.has(token)) continue;
436 return null;
437 }
438 strong &&= atWordStart;
439 if (bestPrimary) primaryRanges.push(...(bestPrimary.letters ?? [bestPrimary]));
440 total += best;
441 counted += 1;
442 // Optional filler never decides the whole-word tier; a query of only filler never earns it.
443 if (FILLER_WORDS.has(token)) notWhole ||= !fillerOptional;
444 else notWhole ||= token.length < PICK_PREFIX_MIN_LENGTH || best < WHOLE_WORD;
445 }
446 let quality = total / counted;
447 if (primary) {
448 if (primary.text === normalizedQuery) quality += WHOLE_NAME - WHOLE_WORD;
449 else if (tokens.length > 1 && primary.text.includes(normalizedQuery)) quality += 0.25;
450 }
451 return {
452 quality,
453 wholeWords: !notWhole,
454 strong,
455 primaryRanges: mergeRanges(primaryRanges),
456 };
457}
458
459// A two-letter Latin substring of a message is noise rather than a match.
460const MESSAGE_TOKEN_MIN_LENGTH = 3;
461
462/**
463 * Keep accents: the server index folds Latin accents, and stripping marks breaks Korean/Japanese.
464 * Every `long` token must match; `short` tokens only narrow hits. No long tokens means no search.
465 * Two CJK characters count as long.
466 */
467export function messageSearchTokens(query: string): {
468 readonly long: ReadonlyArray<string>;
469 readonly short: ReadonlyArray<string>;
470 /** Every token, in the order typed. */
471 readonly words: ReadonlyArray<string>;
472} {
473 const tokens = query
474 .replace(WRAPPING_QUOTES, "")
475 // The index stores apostrophes straight, as `indexedMessageText` writes them.
476 .replace(CURLY_APOSTROPHES, "'")
477 .normalize("NFC")
478 .toLowerCase()
479 .split(/\s+/)
480 .filter((token) => token.length > 0);
481 const searchable = (token: string) => {
482 const length = Array.from(token).length;
483 return length >= MESSAGE_TOKEN_MIN_LENGTH || (length === 2 && hasCjkWord(token));
484 };
485 return {
486 long: tokens.filter(searchable),
487 short: tokens.filter((token) => !searchable(token)),
488 words: tokens,
489 };
490}
491
492/**
493 * Matches the query's words side by side as whole words, as typed, whatever
494 * whitespace is between them and ignoring case; null for a single word.
495 */
496export function messagePhrase(query: string): RegExp | null {
497 const { words } = messageSearchTokens(query);
498 return words.length > 1
499 ? new RegExp(
500 `(?<![\\p{L}\\p{N}])${words
501 .map((word) => word.replace(/[.*+?^${}()|[\]\\]/g, "\\$&"))
502 .join("\\s+")}(?![\\p{L}\\p{N}])`,
503 "iu",
504 )
505 : null;
506}
507
508// Words written together, as typed, rank above the same words apart, as in
509// titles; words near each other rank above words far apart.
510const MESSAGE_PHRASE_BONUS = 0.25;
511const MESSAGE_NEAR_BONUS = 0.1;
512// About what a result row shows.
513const MESSAGE_NEAR_SPAN = 60;
514
515const NON_ASCII = /[\u0080-\uffff]/;
516// A message token shorter than this must start a word: "fts" is not in "drafts".
517const MESSAGE_WORD_START_LENGTH = 4;
518const MESSAGE_PREFIX = 0.8;
519
520function startsWordAt(text: string, index: number): boolean {
521 const character = text[index]!;
522 // A token that opens with punctuation (such as ".ts") brings its own boundary.
523 if (!ALPHANUMERIC.test(character) && !SYMBOL.test(character)) return true;
524 return isWordStart(
525 text[index - 2] ?? "",
526 text[index - 1] ?? "",
527 character,
528 text[index + 1] ?? "",
529 );
530}
531
532// Whether a word ends right before `end` in `text`.
533function endsWordAt(text: string, end: number): boolean {
534 return end >= text.length || !ALPHANUMERIC.test(text[end]!) || startsWordAt(text, end);
535}
536
537// A commit SHA or UUID part: seven or more hex characters with a digit.
538const HEX_ID = /^(?=[a-f]*\d)[0-9a-f]{7,}$/i;
539
540// Where `token` best sits in `folded`, a fold of `text`: every place it is a
541// whole word, else a word start, else inside a word. Hits past the start of a
542// hex ID do not count ("cafe" in "7cafe52bb8"), though a pasted SHA prefix
543// does.
544function findMessageToken(
545 text: string,
546 folded: string,
547 token: string,
548 firstOnly: boolean,
549): { readonly at: ReadonlyArray<number>; readonly quality: number } | null {
550 let quality = 0;
551 let at: number[] = [];
552 // The letters-and-digits run around the hit, kept for later hits in the
553 // same run: rescanning it per hit is quadratic in a long run ("0000" in a
554 // hex dump).
555 let run = { start: 0, end: -1, hex: false };
556 for (let index = folded.indexOf(token); index !== -1; index = folded.indexOf(token, index + 1)) {
557 if (index + token.length > run.end) {
558 let start = index;
559 while (start > 0 && ALPHANUMERIC.test(text[start - 1]!)) start--;
560 let end = index + token.length;
561 while (end < text.length && ALPHANUMERIC.test(text[end]!)) end++;
562 run = { start, end, hex: HEX_ID.test(text.slice(start, end)) };
563 }
564 if (run.hex && run.start < index) continue;
565 const found = !startsWordAt(text, index)
566 ? MID_WORD
567 : endsWordAt(text, index + token.length)
568 ? 1
569 : MESSAGE_PREFIX;
570 if (found > quality) {
571 quality = found;
572 at = [index];
573 if (firstOnly && quality === 1) return { at, quality };
574 } else if (!firstOnly && found === quality) {
575 at.push(index);
576 }
577 }
578 return at.length === 0 ? null : { at, quality };
579}
580
581export interface MessageMatch {
582 /**
583 * 1 when every searched word is a whole word, MESSAGE_PREFIX when one only
584 * starts a word ("mode" in "model"), MID_WORD when one only appears inside
585 * words, plus MESSAGE_PHRASE_BONUS when the words are written together as
586 * typed, else MESSAGE_NEAR_BONUS when they sit within a row's width.
587 */
588 readonly quality: number;
589 /** Where a snippet should start to show the match. */
590 readonly offset: number;
591}
592
593/**
594 * Grades messages against a query, so message hits rank like titles: null
595 * when a token is missing or a short one never starts a word ("fts" in
596 * "drafts"). Case and accents are ignored, as in the server's index. The
597 * query is prepared once, since the server grades thousands of hits for it.
598 */
599export function messageMatcher(query: string): (text: string) => MessageMatch | null {
600 const { long, short, words } = messageSearchTokens(query);
601 const tokens = [...long, ...short].map((token) => ({
602 token,
603 // Marks go from the folded token: lowercasing "İ" adds one.
604 folded: foldInPlace(token).replace(COMBINING_MARKS, ""),
605 nonAscii: NON_ASCII.test(token),
606 mustStartWord: Array.from(token).length < MESSAGE_WORD_START_LENGTH,
607 // Too short to search, so it only narrows: grading by it would reorder
608 // results on each keystroke while the next word is typed ("nvme s").
609 grades: long.includes(token),
610 }));
611 const phrase = messagePhrase(query);
612 // Accents typed or left out still read as written together: "cafe open"
613 // in "Café open".
614 const foldedPhrase = messagePhrase(
615 words.map((word) => foldInPlace(word).replace(COMBINING_MARKS, "")).join(" "),
616 );
617 const queryNonAscii = NON_ASCII.test(query);
618 return (text) => {
619 const lower = text.toLowerCase();
620 // "İ" lowercases to two units, which would shift every offset after it.
621 const plain = lower.length === text.length ? lower : foldInPlace(text);
622 let folded: string | null = null;
623 let quality = 1;
624 const positions: Array<ReadonlyArray<number>> = [];
625 for (const { token, folded: foldedToken, nonAscii, mustStartWord, grades } of tokens) {
626 let found = findMessageToken(text, plain, token, tokens.length === 1);
627 // Accents typed or left out: "cafe" finds "Café", also after "cafeteria".
628 if (found?.quality !== 1 && foldedToken.length > 0 && (nonAscii || NON_ASCII.test(text))) {
629 found = findMessageToken(
630 text,
631 (folded ??= foldInPlace(text)),
632 foldedToken,
633 tokens.length === 1,
634 );
635 }
636 if (found === null) return null;
637 if (found.quality === MID_WORD && mustStartWord) return null;
638 if (grades) quality = Math.min(quality, found.quality);
639 positions.push(found.at);
640 }
641 // Written together as typed: the snippet starts there. Apostrophes are
642 // straight in the query, and straightening keeps offsets.
643 const straight = (value: string) => value.replace(CURLY_APOSTROPHES, "'");
644 const together =
645 phrase?.exec(straight(plain)) ??
646 (queryNonAscii || NON_ASCII.test(text)
647 ? foldedPhrase?.exec(straight((folded ??= foldInPlace(text))))
648 : null);
649 if (together) return { quality: quality + MESSAGE_PHRASE_BONUS, offset: together.index };
650 // Else the shortest stretch that holds every word: the snippet starts
651 // there, so it shows them all, and words close together rank above words
652 // far apart ("lakebed perf").
653 const near = shortestSpan(positions);
654 return {
655 quality:
656 long.length > 1 && near.length <= MESSAGE_NEAR_SPAN
657 ? quality + MESSAGE_NEAR_BONUS
658 : quality,
659 offset: near.start,
660 };
661 };
662}
663
664// The shortest stretch of text holding one place of each word, from each
665// word's places in order.
666function shortestSpan(places: ReadonlyArray<ReadonlyArray<number>>): {
667 readonly start: number;
668 readonly length: number;
669} {
670 const hits = places
671 .flatMap((at, word) => at.map((index) => ({ index, word })))
672 .sort((left, right) => left.index - right.index);
673 const counts = places.map(() => 0);
674 let covered = 0;
675 let best = { start: hits[0]?.index ?? 0, length: Number.POSITIVE_INFINITY };
676 let left = 0;
677 for (const hit of hits) {
678 counts[hit.word] = (counts[hit.word] ?? 0) + 1;
679 if (counts[hit.word] === 1) covered++;
680 while (covered === places.length) {
681 const first = hits[left]!;
682 if (hit.index - first.index < best.length) {
683 best = { start: first.index, length: hit.index - first.index };
684 }
685 counts[first.word] = (counts[first.word] ?? 1) - 1;
686 if (counts[first.word] === 0) covered--;
687 left++;
688 }
689 }
690 return best;
691}
692
693/**
694 * Ranges of `text` that contain a long message search token, for message
695 * snippets, ignoring case and accents. Shorter tokens would light up half the
696 * snippet, and a short long token only counts where it starts a word.
697 * Snippets vary per query, so they skip the field cache.
698 */
699export function findSearchTokenRanges(text: string, query: string): SearchRange[] {
700 const tokens = new Map(
701 messageSearchTokens(query)
702 .long.map(
703 (token) =>
704 [foldSearchQuery(token), Array.from(token).length < MESSAGE_WORD_START_LENGTH] as const,
705 )
706 // Some tokens fold to nothing ("´´´"), which would match everywhere.
707 .filter(([token]) => token.length > 0),
708 );
709 if (tokens.size === 0) return [];
710 const field = foldSearchField(text);
711 const ranges: SearchRange[] = [];
712 for (const [token, needsWordStart] of tokens) {
713 // A token that opens with punctuation brings its own boundary, as in scoring.
714 const ownBoundary = !ALPHANUMERIC.test(token[0]!) && !SYMBOL.test(token[0]!);
715 for (let index = field.text.indexOf(token); index !== -1;) {
716 if (needsWordStart && !ownBoundary && !field.wordStarts[index]) {
717 index = field.text.indexOf(token, index + 1);
718 continue;
719 }
720 ranges.push({ start: index, end: index + token.length });
721 index = field.text.indexOf(token, index + token.length);
722 }
723 }
724 return mergeRanges(ranges);
725}
726
727export interface SearchTextPart {
728 readonly text: string;
729 readonly highlighted: boolean;
730 readonly start: number;
731}
732
733/** `text` cut into plain and highlighted parts at sorted, non-overlapping `ranges`. */
734export function splitSearchText(
735 text: string,
736 ranges: ReadonlyArray<SearchRange>,
737): SearchTextPart[] {
738 const parts: SearchTextPart[] = [];
739 let cursor = 0;
740 for (const range of ranges) {
741 if (range.start > cursor) {
742 parts.push({ text: text.slice(cursor, range.start), highlighted: false, start: cursor });
743 }
744 parts.push({ text: text.slice(range.start, range.end), highlighted: true, start: range.start });
745 cursor = range.end;
746 }
747 if (cursor < text.length || parts.length === 0) {
748 parts.push({ text: text.slice(cursor), highlighted: false, start: cursor });
749 }
750 return parts;
751}
752
753const DAY_MS = 24 * 60 * 60 * 1000;
754/** Both activity recency and open counts halve every two weeks. */
755export const SEARCH_RECENCY_HALF_LIFE_MS = 14 * DAY_MS;
756/**
757 * Opens closer together than this count once, so flipping between threads is
758 * not frequency. Clients skip sending them.
759 */
760export const THREAD_OPEN_DEDUPE_MS = 10 * 60 * 1000;
761const THREAD_SEARCH_PICK_LIMIT = 3;
762/** Picked queries are stored this long; clients send no more. */
763const THREAD_SEARCH_PICK_MAX_LENGTH = 32;
764
765/**
766 * `query` as a pick is stored and compared: folded, then cut to the stored
767 * length without splitting an emoji in two. Clients and the server both use
768 * it, so a long pick matches its query again.
769 */
770export function pickedQuery(query: string): string {
771 const cut = foldSearchQuery(query).slice(0, THREAD_SEARCH_PICK_MAX_LENGTH);
772 return (/[\ud800-\udbff]$/.test(cut) ? cut.slice(0, -1) : cut).trim();
773}
774
775function decay(ageMs: number): number {
776 return 2 ** (-Math.max(0, ageMs) / SEARCH_RECENCY_HALF_LIFE_MS);
777}
778
779/** Server-stored open history; see `OrchestrationV2ThreadOpens`. */
780export type ThreadOpenStats = OrchestrationV2ThreadOpens;
781
782/**
783 * Next open stats after an open at `at`. `query` is the palette query that
784 * picked the thread, when it was opened from search.
785 */
786export function recordThreadOpen(
787 previous: ThreadOpenStats | null,
788 at: number,
789 query: string | undefined,
790): ThreadOpenStats {
791 const pick = pickedQuery(query ?? "");
792 // Picks that no longer count are not kept or synced.
793 const earlier = (previous?.picks ?? []).filter((entry) => at - entry.at <= PICK_WINDOW_MS);
794 const picks = pick
795 ? [{ query: pick, at }, ...earlier.filter((entry) => entry.query !== pick)].slice(
796 0,
797 THREAD_SEARCH_PICK_LIMIT,
798 )
799 : earlier;
800 if (previous !== null && at - previous.openedAt < THREAD_OPEN_DEDUPE_MS) {
801 return { ...previous, picks };
802 }
803 const score = previous === null ? 1 : previous.score * decay(at - previous.openedAt) + 1;
804 return { openedAt: at, score, picks };
805}
806
807export interface ThreadSearchSubject {
808 /** Matched only by the whole query, like references. */
809 readonly id?: string;
810 readonly title: string;
811 readonly branch?: string | null;
812 readonly projectTitle?: string | null;
813 /** Only set with two or more environments; it tells same-named threads apart. */
814 readonly environmentLabel?: string | null;
815 readonly pullRequests?: ReadonlyArray<{
816 readonly number: number;
817 readonly title?: string | null;
818 /** Values such as URLs, matched only by the whole query. */
819 readonly references?: ReadonlyArray<string>;
820 }>;
821 /** Latest user activity, in epoch ms. */
822 readonly activityAt: number | null;
823 readonly opens?: ThreadOpenStats | null;
824}
825
826// Use reorders matches of about the same quality but never turns a mid-word
827// hit on a busy thread into a better result than a whole word on a quiet one.
828const USE_BOOST_LIMIT = 2.5;
829
830/**
831 * How much use lifts a thread: 1 for a stale, never-opened thread, about 2 for
832 * one active today, and up to 2.5 for threads opened often.
833 */
834function threadUsageBoost(thread: ThreadSearchSubject, now: number): number {
835 const recency = thread.activityAt === null ? 0 : decay(now - thread.activityAt);
836 const opens = thread.opens ? thread.opens.score * decay(now - thread.opens.openedAt) : 0;
837 return Math.min(USE_BOOST_LIMIT, 1 + recency + 0.5 * Math.log2(1 + opens));
838}
839
840const REFERENCE_PREFIX_MIN = 8;
841
842// A number is never cut short: ".../pull/2288" is not pull request 22889.
843const notCut = (text: string, end: number) => !DIGIT.test(text[end] ?? "");
844
845// IDs and URLs have many word starts, so field matching would let short queries hit every thread.
846// Require a long prefix, or any long part containing a digit. Both are ASCII; lowercasing suffices.
847function matchReference(
848 normalizedQuery: string,
849 thread: ThreadSearchSubject,
850): SearchFieldsMatch | null {
851 if (normalizedQuery.length < REFERENCE_PREFIX_MIN) return null;
852 const anywhere = DIGIT.test(normalizedQuery);
853 const matches = (reference: string) => {
854 const folded = reference.toLowerCase();
855 const at = folded.indexOf(normalizedQuery);
856 // A pasted link may go on past the reference: ".../pull/22889/files".
857 return anywhere
858 ? (at !== -1 && notCut(folded, at + normalizedQuery.length)) ||
859 (normalizedQuery.startsWith(folded) && notCut(normalizedQuery, folded.length))
860 : at === 0;
861 };
862 return (thread.id && matches(thread.id)) ||
863 thread.pullRequests?.some((pullRequest) => pullRequest.references?.some(matches))
864 ? { quality: 0.6, wholeWords: false, strong: true, primaryRanges: [] }
865 : null;
866}
867
868// Picks expire from the pick time; opening a thread another way must not extend their priority.
869// They reorder word matches within a group, never the groups themselves.
870const PICK_WINDOW_MS = 21 * DAY_MS;
871// The start of a picked query counts from three letters: "n" is too little to
872// go on.
873const PICK_PREFIX_MIN_LENGTH = 3;
874
875/** The latest pick of the thread for this query, while it lasts. */
876function activePick(
877 thread: ThreadSearchSubject,
878 normalizedQuery: string,
879 now: number,
880): ThreadOpenStats["picks"][number] | undefined {
881 // Stored picks are cut to a length, so compare the query cut the same way.
882 const query = pickedQuery(normalizedQuery);
883 const prefix = query.length >= PICK_PREFIX_MIN_LENGTH;
884 // The latest exact pick, else the latest pick the query starts.
885 let exact: ThreadOpenStats["picks"][number] | undefined;
886 let latest: ThreadOpenStats["picks"][number] | undefined;
887 for (const pick of thread.opens?.picks ?? []) {
888 if (now - pick.at > PICK_WINDOW_MS) continue;
889 if (pick.query === query && (exact === undefined || pick.at > exact.at)) exact = pick;
890 const matches = pick.query === query || (prefix && pick.query.startsWith(query));
891 if (matches && (latest === undefined || pick.at > latest.at)) latest = pick;
892 }
893 return exact ?? latest;
894}
895
896export interface ThreadSearchMatch {
897 /** Match quality times use; what results sort by. */
898 readonly score: number;
899 /** Match quality alone; see `rankSearchGroups`. */
900 readonly quality: number;
901 readonly wholeWords: boolean;
902 /** Every token matched at a word start; see `rankSearchGroups`. */
903 readonly strong: boolean;
904 /** Matched ranges in the title. */
905 readonly ranges: ReadonlyArray<SearchRange>;
906 /**
907 * Why the thread matched when its title shows no match, for the result row.
908 * Built on demand, so only the rows shown pay for it.
909 */
910 readonly explain?: () => SearchMatchHint | undefined;
911 /** When the thread was picked for this query, while that pick lasts; see `rankSearchGroups`. */
912 readonly pickedAt?: number;
913 /** Picked for exactly this query, before newer picks for longer ones; see `rankSearchGroups`. */
914 readonly pickedExactly?: boolean;
915 /** Below the whole-name class; see `scoreThreadSearch`. */
916 readonly groupQuality: number;
917}
918
919export interface SearchMatchHint {
920 readonly label: string;
921 readonly text: string;
922 readonly ranges: ReadonlyArray<SearchRange>;
923}
924
925// Most threads' branches start with the app's own worktree prefix ("t3/", and
926// "t3code/" before it, "t3-<hex>" when a "t3" branch blocks nested refs), so
927// "t3 connect" would match nearly every thread.
928// Only before more text, so typing "t3/" does not empty the list for a keystroke.
929const WORKTREE_BRANCH_PREFIX_PATTERN = new RegExp(
930 `^(?:(?:${WORKTREE_BRANCH_PREFIX}|t3code)/(?=\\S)|${WORKTREE_BRANCH_PREFIX}-(?=[0-9a-f]{8}$))`,
931);
932
933// The flat prefix anywhere in a query, while its hex is still being typed, so
934// "t3-abcd" and "connect t3-abcd1234" still reach the stripped branch field.
935const FLAT_BRANCH_QUERY_PREFIX_PATTERN = new RegExp(
936 `(^| )${WORKTREE_BRANCH_PREFIX}-(?=[0-9a-f]{1,8}(?: |$))`,
937 "g",
938);
939
940function searchableBranch(branch: string | null | undefined): string | null {
941 return branch ? branch.replace(WORKTREE_BRANCH_PREFIX_PATTERN, "") : null;
942}
943
944/**
945 * The field that explains a match whose title shows none: the first that holds
946 * the whole query, else, past the words the project or environment holds, the
947 * first that holds the rest ("lakebed perf" in project "lakebed" with the PR
948 * title "perf: …").
949 */
950function matchHint(
951 normalizedQuery: string,
952 thread: ThreadSearchSubject,
953 typos: boolean,
954): SearchMatchHint | undefined {
955 const candidates: Array<{ readonly label: string; readonly text: string | null | undefined }> = [
956 ...(thread.pullRequests ?? []).map((pullRequest) => ({
957 label: "PR",
958 text: `#${pullRequest.number}${pullRequest.title ? ` ${pullRequest.title}` : ""}`,
959 })),
960 { label: "Branch", text: searchableBranch(thread.branch) },
961 { label: "Project", text: thread.projectTitle },
962 { label: "Environment", text: thread.environmentLabel },
963 ];
964 const holds = (text: string, query: string) =>
965 matchSearchFields(query, [{ value: text, weight: 1 }], { typos })?.primaryRanges;
966 const hintFor = (query: string) => {
967 for (const { label, text } of candidates) {
968 const ranges = text ? holds(text, query) : undefined;
969 if (text && ranges) return { label, text, ranges };
970 }
971 return undefined;
972 };
973 const whole = hintFor(normalizedQuery);
974 if (whole) return whole;
975 const contexts = [thread.projectTitle, thread.environmentLabel].filter(
976 (text): text is string => !!text,
977 );
978 const rest = normalizedQuery
979 .split(" ")
980 .filter((token) => !contexts.some((text) => holds(text, token)))
981 .join(" ");
982 return rest && rest !== normalizedQuery ? hintFor(rest) : undefined;
983}
984
985// A keystroke scores each thread's fields again, so they are listed once per subject.
986const threadFieldsCache = new WeakMap<ThreadSearchSubject, ReadonlyArray<WeightedSearchField>>();
987
988function threadSearchFields(thread: ThreadSearchSubject): ReadonlyArray<WeightedSearchField> {
989 const cached = threadFieldsCache.get(thread);
990 if (cached) return cached;
991 const fields: WeightedSearchField[] = [{ value: thread.title, weight: 1, midWord: true }];
992 for (const pullRequest of thread.pullRequests ?? []) {
993 fields.push({ value: `#${pullRequest.number}`, weight: 1 });
994 if (pullRequest.title) fields.push({ value: pullRequest.title, weight: 0.5 });
995 }
996 const branch = searchableBranch(thread.branch);
997 if (branch) fields.push({ value: branch, weight: 0.6 });
998 if (thread.projectTitle) {
999 fields.push({ value: thread.projectTitle, weight: 0.25, context: true });
1000 }
1001 if (thread.environmentLabel) {
1002 fields.push({ value: thread.environmentLabel, weight: 0.25, context: true });
1003 }
1004 threadFieldsCache.set(thread, fields);
1005 return fields;
1006}
1007
1008let lastFieldQuery: { readonly query: string; readonly fieldQuery: string } | undefined;
1009
1010// Strip pull request prefixes and the worktree prefix so queries match the stored fields.
1011function threadFieldQuery(normalizedQuery: string): string {
1012 if (lastFieldQuery?.query !== normalizedQuery) {
1013 lastFieldQuery = {
1014 query: normalizedQuery,
1015 fieldQuery: normalizedQuery
1016 .replace(/^(?:pr|pull request|pull)\s*(?=#?\d)/, "")
1017 .replace(/^#\s*/, "")
1018 .replace(WORKTREE_BRANCH_PREFIX_PATTERN, "")
1019 .replace(FLAT_BRANCH_QUERY_PREFIX_PATTERN, "$1"),
1020 };
1021 }
1022 return lastFieldQuery.fieldQuery;
1023}
1024
1025/**
1026 * Scores a thread for a normalized query, or null when it does not match.
1027 * Titles and pull request numbers count fully, pull request titles and
1028 * branches less, project and environment names least.
1029 */
1030export function scoreThreadSearch(
1031 normalizedQuery: string,
1032 thread: ThreadSearchSubject,
1033 now: number,
1034 options?: {
1035 readonly typos?: boolean;
1036 /**
1037 * Palette picks; off where a pick would show up unexplained, such as a
1038 * sidebar filter or an agent's search.
1039 */
1040 readonly picks?: boolean;
1041 },
1042): ThreadSearchMatch | null {
1043 const fields = threadSearchFields(thread);
1044 const fieldQuery = threadFieldQuery(normalizedQuery);
1045 const fieldMatch = matchSearchFields(fieldQuery, fields, options);
1046 const referenceMatch = fieldMatch ? null : matchReference(normalizedQuery, thread);
1047 const match = fieldMatch ?? referenceMatch;
1048 if (match === null) return null;
1049 // A row whose title shows no match must say why. With several words, one
1050 // that cannot (its words spread over unrelated fields) is a coincidence and
1051 // is left out; a single word always sits in the field that matched it, so
1052 // its hint waits until the row is shown.
1053 const typos = options?.typos ?? false;
1054 const titleShowsMatch = match.primaryRanges.length > 0;
1055 const checkHint = !titleShowsMatch && referenceMatch === null && fieldQuery.includes(" ");
1056 const checkedHint = checkHint ? matchHint(fieldQuery, thread, typos) : undefined;
1057 if (checkHint && checkedHint === undefined) return null;
1058 const explain = titleShowsMatch
1059 ? undefined
1060 : (): SearchMatchHint | undefined =>
1061 referenceMatch
1062 ? { label: "ID or link", text: normalizedQuery, ranges: [] }
1063 : (checkedHint ?? matchHint(fieldQuery, thread, typos));
1064 const pick = options?.picks === false ? undefined : activePick(thread, normalizedQuery, now);
1065 return {
1066 score: match.quality * threadUsageBoost(thread, now),
1067 quality: match.quality,
1068 wholeWords: match.wholeWords,
1069 // A thread's whole title never lifts its group over a command or project
1070 // of that name: every new thread is titled "New thread" for a while.
1071 groupQuality: Math.min(match.quality, WHOLE_NAME - 0.01),
1072 strong: match.strong,
1073 ranges: match.primaryRanges,
1074 ...(explain ? { explain } : {}),
1075 ...(pick ? { pickedAt: pick.at } : {}),
1076 ...(pick?.query === pickedQuery(normalizedQuery) ? { pickedExactly: true } : {}),
1077 };
1078}
1079
1080/** When the user last used a thread: their last message or their last open. */
1081export function threadRecentUse(thread: ThreadSearchSubject): number {
1082 return Math.max(thread.activityAt ?? 0, thread.opens?.openedAt ?? 0);
1083}
1084
1085/**
1086 * How strongly a thread's messages match among matches of one quality: a
1087 * thread that keeps using the word outweighs a recent passing mention, as
1088 * hits count for more than recency or use (21 hits about 5.5, one hit 2).
1089 */
1090function messageMatchWeight(hits: number): number {
1091 return 1 + Math.log2(1 + hits);
1092}
1093
1094/** `withoutTitleMatches` reserves message rows for threads the palette has not already listed. */
1095export function rankMessageMatches<
1096 T extends {
1097 readonly quality?: number;
1098 readonly hits?: number;
1099 readonly messageCreatedAt?: string | null;
1100 },
1101>(
1102 matches: ReadonlyArray<T>,
1103 subjectOf: (match: T) => ThreadSearchSubject | undefined,
1104 normalizedQuery: string,
1105 now: number,
1106 options?: { readonly picks?: boolean; readonly withoutTitleMatches?: boolean },
1107): T[] {
1108 return matches
1109 .flatMap((match) => {
1110 const subject = subjectOf(match);
1111 if (!subject) return [];
1112 if (
1113 options?.withoutTitleMatches &&
1114 scoreThreadSearch(normalizedQuery, subject, now, { picks: false }) !== null
1115 ) {
1116 return [];
1117 }
1118 // Older servers send no quality; their matches count as words.
1119 const quality = match.quality ?? 1;
1120 return [
1121 {
1122 match,
1123 quality,
1124 pickedAt:
1125 options?.picks === false ? 0 : (activePick(subject, normalizedQuery, now)?.at ?? 0),
1126 score: messageMatchWeight(match.hits ?? 1) * threadUsageBoost(subject, now),
1127 },
1128 ];
1129 })
1130 .sort(
1131 (left, right) =>
1132 // Word matches first; among them a pick, then the closer match.
1133 Number(right.quality >= MESSAGE_PREFIX) - Number(left.quality >= MESSAGE_PREFIX) ||
1134 right.pickedAt - left.pickedAt ||
1135 right.quality - left.quality ||
1136 right.score - left.score ||
1137 (right.match.messageCreatedAt ?? "").localeCompare(left.match.messageCreatedAt ?? ""),
1138 )
1139 .map(({ match }) => match);
1140}
1141
1142/** Palette limits shared by web and mobile. */
1143export const PALETTE_THREAD_LIMIT = 20;
1144export const PALETTE_MESSAGE_LIMIT = 10;
1145/** Next to matching threads, other groups show only their best few rows. */
1146export const PALETTE_SECONDARY_LIMIT = 3;
1147
1148// Whole words and prefixes share a class so "Compact" does not lift settings over "Compaction".
1149function matchClass(quality: number): number {
1150 return quality >= WHOLE_NAME ? 3 : quality >= 0.7 ? 2 : quality >= 0.4 ? 1 : 0;
1151}
1152
1153export interface RankedSearchItem<T, M> {
1154 readonly item: T;
1155 readonly match: M;
1156}
1157
1158/**
1159 * Rank groups by match class to keep typing stable and thread use from outweighing equal commands.
1160 * Try typos only without word-start matches: they add noise beside real matches and cost per key.
1161 */
1162export function rankSearchGroups<
1163 G,
1164 T,
1165 M extends {
1166 readonly score: number;
1167 readonly quality: number;
1168 readonly strong: boolean;
1169 readonly pickedAt?: number;
1170 readonly pickedExactly?: boolean;
1171 readonly groupQuality?: number;
1172 readonly wholeWords?: boolean;
1173 },
1174>(
1175 groups: ReadonlyArray<{ readonly group: G; readonly items: ReadonlyArray<T> }>,
1176 score: (item: T, options: { readonly typos: boolean }, group: G) => M | null,
1177): Array<{ readonly group: G; readonly ranked: ReadonlyArray<RankedSearchItem<T, M>> }> {
1178 const rank = (typos: boolean) =>
1179 groups.map(({ group, items }) => {
1180 const options = { typos };
1181 const ranked: Array<RankedSearchItem<T, M>> = [];
1182 for (const item of items) {
1183 const match = score(item, options, group);
1184 if (match !== null) ranked.push({ item, match });
1185 }
1186 return { group, ranked };
1187 });
1188 let ranked = rank(false);
1189 if (!ranked.some((entry) => entry.ranked.some(({ match }) => match.strong))) {
1190 ranked = rank(true);
1191 }
1192 return ranked
1193 .flatMap(({ group, ranked: items }, order) => {
1194 if (items.length === 0) return [];
1195 // Use cannot lift a project-only match above a title match or cross match classes.
1196 // Picks reorder word matches, keeping typos and mid-word hits below them.
1197 // A longer-query pick must not pass a whole-name match for the current query.
1198 const wordMatch = (match: M) => Math.min(matchClass(match.quality), 2);
1199 const exactPickAt = (match: M) => (match.pickedExactly ? (match.pickedAt ?? 0) : 0);
1200 // Use reorders whole words or prefixes among themselves, never a prefix above a whole word.
1201 const wholeWord = (match: M) => Number(match.wholeWords ?? match.quality >= WHOLE_WORD);
1202 const sorted = [...items].sort(
1203 (left, right) =>
1204 wordMatch(right.match) - wordMatch(left.match) ||
1205 exactPickAt(right.match) - exactPickAt(left.match) ||
1206 matchClass(right.match.quality) - matchClass(left.match.quality) ||
1207 (right.match.pickedAt ?? 0) - (left.match.pickedAt ?? 0) ||
1208 wholeWord(right.match) - wholeWord(left.match) ||
1209 right.match.score - left.match.score,
1210 );
1211 const best = Math.max(
1212 ...items.map(({ match }) => matchClass(match.groupQuality ?? match.quality)),
1213 );
1214 return [{ group, ranked: sorted, best, order }];
1215 })
1216 .sort((left, right) => right.best - left.best || left.order - right.order)
1217 .map(({ group, ranked: items }) => ({ group, ranked: items }));
1218}
1219
1220/** `rankSearchGroups` for a single list. */
1221export function rankSearchItems<
1222 T,
1223 M extends { readonly score: number; readonly quality: number; readonly strong: boolean },
1224>(
1225 items: ReadonlyArray<T>,
1226 score: (item: T, options: { readonly typos: boolean }) => M | null,
1227): ReadonlyArray<RankedSearchItem<T, M>> {
1228 return rankSearchGroups([{ group: null, items }], score)[0]?.ranked ?? [];
1229}
1230
1231export interface SearchTermsMatch {
1232 readonly score: number;
1233 readonly quality: number;
1234 /** The quality its group ranks by, when lower; see `scoreSearchTerms`. */
1235 readonly groupQuality?: number;
1236 readonly strong: boolean;
1237 readonly ranges: ReadonlyArray<SearchRange>;
1238}
1239
1240const KEYWORD_QUALITY = 0.65;
1241// Below this, keyword prefixes match too much: "co" or "pro" would list most
1242// settings. A short query still matches a keyword it equals ("pr").
1243const KEYWORD_QUERY_MIN_LENGTH = 4;
1244
1245/**
1246 * Keywords count less so hidden terms cannot lift a group above a matching name.
1247 * Short queries need whole keywords to avoid listing most settings for common prefixes.
1248 */
1249export function scoreSearchTerms(
1250 normalizedQuery: string,
1251 terms: ReadonlyArray<string>,
1252 options?: { readonly typos?: boolean },
1253): SearchTermsMatch | null {
1254 // Filler words ("the ci") do not make a short query long.
1255 const meaningful = normalizedQuery
1256 .split(" ")
1257 .filter((token) => !FILLER_WORDS.has(token))
1258 .join(" ");
1259 const short = (meaningful || normalizedQuery).length < KEYWORD_QUERY_MIN_LENGTH;
1260 const match = matchSearchFields(
1261 normalizedQuery,
1262 terms.map((value, index) =>
1263 index === 0
1264 ? { value, weight: 1 }
1265 : // An alias typed in full ("pr") is deliberate, above a mere name prefix.
1266 { value, weight: short ? 0.8 : 0.6, wholeWords: short, keyword: true },
1267 ),
1268 options,
1269 );
1270 return (
1271 match && {
1272 score: match.quality,
1273 quality: match.quality,
1274 // Below the word-start class: a match only in hidden keywords must not put
1275 // its group above a result whose name matches. Inside the group an exact
1276 // alias still beats a name prefix ("pr" lists "Open pull requests" first).
1277 ...(match.primaryRanges.length > 0
1278 ? {}
1279 : { groupQuality: Math.min(match.quality, KEYWORD_QUALITY) }),
1280 strong: match.strong,
1281 ranges: match.primaryRanges,
1282 }
1283 );
1284}