The best way to control Claude Code, Codex and more from any computer or phone
| 1 | /** Shared ranking keeps command palettes and MCP thread search consistent across surfaces. */ |
| 2 | |
| 3 | import type { OrchestrationV2ThreadOpens } from "@t3tools/contracts"; |
| 4 | |
| 5 | import { WORKTREE_BRANCH_PREFIX } from "./git.ts"; |
| 6 | |
| 7 | const ALPHANUMERIC = /[\p{L}\p{N}]/u; |
| 8 | const LOWERCASE = /\p{Ll}/u; |
| 9 | const UPPERCASE = /\p{Lu}/u; |
| 10 | const DIGIT = /\p{N}/u; |
| 11 | const LETTER = /\p{L}/u; |
| 12 | const COMBINING_MARKS = /\p{M}/gu; |
| 13 | // Emoji and other symbols can be searched for, so they start words too. |
| 14 | const SYMBOL = /\p{So}/u; |
| 15 | const APOSTROPHE = /['’]/; |
| 16 | const CURLY_APOSTROPHES = /[\u2018\u2019]/g; |
| 17 | |
| 18 | interface 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 | |
| 25 | export 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. |
| 34 | const fieldCache = new Map<string, SearchField>(); |
| 35 | const FIELD_CACHE_LIMIT = 100_000; |
| 36 | |
| 37 | function 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 | */ |
| 52 | function 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. |
| 62 | function 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. |
| 73 | function 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 | */ |
| 85 | function 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 | |
| 106 | function 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 | |
| 121 | function 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". |
| 135 | const WRAPPING_QUOTES = /^\s*["'`“”‘’]+|["'`“”‘’]+\s*$/g; |
| 136 | |
| 137 | /** Folded, whitespace-collapsed query; empty when there is nothing to match. */ |
| 138 | export 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 | |
| 145 | function 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. |
| 155 | function 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 | |
| 176 | const WHOLE_WORD = 1; |
| 177 | // The bonus for a field equal to the whole query lifts a whole word to this. |
| 178 | const WHOLE_NAME = 1.5; |
| 179 | const MID_WORD = 0.3; |
| 180 | const 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. |
| 183 | const JOINED_WORDS = 0.6; |
| 184 | |
| 185 | interface 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 | */ |
| 196 | function 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 | */ |
| 280 | function 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 | |
| 318 | interface 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 | |
| 344 | interface 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 | |
| 358 | function preparedField(weighted: WeightedSearchField): SearchField { |
| 359 | return (weighted.prepared ??= prepareSearchField(weighted.value)); |
| 360 | } |
| 361 | |
| 362 | const FILLER_WORDS = new Set(["a", "an", "and", "for", "in", "of", "on", "the", "to", "with"]); |
| 363 | |
| 364 | // Sorted, with overlapping ranges joined. |
| 365 | function 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. |
| 379 | let lastQuery: |
| 380 | | { readonly query: string; readonly tokens: string[]; readonly fillerOptional: boolean } |
| 381 | | undefined; |
| 382 | |
| 383 | function 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 | */ |
| 402 | function 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. |
| 460 | const 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 | */ |
| 467 | export 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 | */ |
| 496 | export 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. |
| 510 | const MESSAGE_PHRASE_BONUS = 0.25; |
| 511 | const MESSAGE_NEAR_BONUS = 0.1; |
| 512 | // About what a result row shows. |
| 513 | const MESSAGE_NEAR_SPAN = 60; |
| 514 | |
| 515 | const NON_ASCII = /[\u0080-\uffff]/; |
| 516 | // A message token shorter than this must start a word: "fts" is not in "drafts". |
| 517 | const MESSAGE_WORD_START_LENGTH = 4; |
| 518 | const MESSAGE_PREFIX = 0.8; |
| 519 | |
| 520 | function 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`. |
| 533 | function 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. |
| 538 | const 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. |
| 544 | function 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 | |
| 581 | export 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 | */ |
| 599 | export 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. |
| 666 | function 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 | */ |
| 699 | export 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 | |
| 727 | export 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`. */ |
| 734 | export 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 | |
| 753 | const DAY_MS = 24 * 60 * 60 * 1000; |
| 754 | /** Both activity recency and open counts halve every two weeks. */ |
| 755 | export 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 | */ |
| 760 | export const THREAD_OPEN_DEDUPE_MS = 10 * 60 * 1000; |
| 761 | const THREAD_SEARCH_PICK_LIMIT = 3; |
| 762 | /** Picked queries are stored this long; clients send no more. */ |
| 763 | const 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 | */ |
| 770 | export 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 | |
| 775 | function 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`. */ |
| 780 | export 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 | */ |
| 786 | export 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 | |
| 807 | export 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. |
| 828 | const 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 | */ |
| 834 | function 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 | |
| 840 | const REFERENCE_PREFIX_MIN = 8; |
| 841 | |
| 842 | // A number is never cut short: ".../pull/2288" is not pull request 22889. |
| 843 | const 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. |
| 847 | function 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. |
| 870 | const 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. |
| 873 | const PICK_PREFIX_MIN_LENGTH = 3; |
| 874 | |
| 875 | /** The latest pick of the thread for this query, while it lasts. */ |
| 876 | function 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 | |
| 896 | export 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 | |
| 919 | export type SearchMatchHintField = |
| 920 | | "pull-request" |
| 921 | | "branch" |
| 922 | | "project" |
| 923 | | "environment" |
| 924 | | "reference"; |
| 925 | |
| 926 | export interface SearchMatchHint { |
| 927 | readonly field: SearchMatchHintField; |
| 928 | readonly label: string; |
| 929 | readonly text: string; |
| 930 | readonly ranges: ReadonlyArray<SearchRange>; |
| 931 | } |
| 932 | |
| 933 | // Most threads' branches start with the app's own worktree prefix ("t3/", and |
| 934 | // "t3code/" before it, "t3-<hex>" when a "t3" branch blocks nested refs), so |
| 935 | // "t3 connect" would match nearly every thread. |
| 936 | // Only before more text, so typing "t3/" does not empty the list for a keystroke. |
| 937 | const WORKTREE_BRANCH_PREFIX_PATTERN = new RegExp( |
| 938 | `^(?:(?:${WORKTREE_BRANCH_PREFIX}|t3code)/(?=\\S)|${WORKTREE_BRANCH_PREFIX}-(?=[0-9a-f]{8}$))`, |
| 939 | ); |
| 940 | |
| 941 | // The flat prefix anywhere in a query, while its hex is still being typed, so |
| 942 | // "t3-abcd" and "connect t3-abcd1234" still reach the stripped branch field. |
| 943 | const FLAT_BRANCH_QUERY_PREFIX_PATTERN = new RegExp( |
| 944 | `(^| )${WORKTREE_BRANCH_PREFIX}-(?=[0-9a-f]{1,8}(?: |$))`, |
| 945 | "g", |
| 946 | ); |
| 947 | |
| 948 | function searchableBranch(branch: string | null | undefined): string | null { |
| 949 | return branch ? branch.replace(WORKTREE_BRANCH_PREFIX_PATTERN, "") : null; |
| 950 | } |
| 951 | |
| 952 | /** |
| 953 | * The field that explains a match whose title shows none: the first that holds |
| 954 | * the whole query, else, past the words the project or environment holds, the |
| 955 | * first that holds the rest ("lakebed perf" in project "lakebed" with the PR |
| 956 | * title "perf: …"). |
| 957 | */ |
| 958 | function matchHint( |
| 959 | normalizedQuery: string, |
| 960 | thread: ThreadSearchSubject, |
| 961 | typos: boolean, |
| 962 | ): SearchMatchHint | undefined { |
| 963 | const candidates: Array<{ |
| 964 | readonly field: SearchMatchHintField; |
| 965 | readonly label: string; |
| 966 | readonly text: string | null | undefined; |
| 967 | }> = [ |
| 968 | ...(thread.pullRequests ?? []).map((pullRequest) => ({ |
| 969 | field: "pull-request" as const, |
| 970 | label: "PR", |
| 971 | text: `#${pullRequest.number}${pullRequest.title ? ` ${pullRequest.title}` : ""}`, |
| 972 | })), |
| 973 | { field: "branch", label: "Branch", text: searchableBranch(thread.branch) }, |
| 974 | { field: "project", label: "Project", text: thread.projectTitle }, |
| 975 | { field: "environment", label: "Environment", text: thread.environmentLabel }, |
| 976 | ]; |
| 977 | const holds = (text: string, query: string) => |
| 978 | matchSearchFields(query, [{ value: text, weight: 1 }], { typos })?.primaryRanges; |
| 979 | const hintFor = (query: string) => { |
| 980 | for (const { field, label, text } of candidates) { |
| 981 | const ranges = text ? holds(text, query) : undefined; |
| 982 | if (text && ranges) return { field, label, text, ranges }; |
| 983 | } |
| 984 | return undefined; |
| 985 | }; |
| 986 | const whole = hintFor(normalizedQuery); |
| 987 | if (whole) return whole; |
| 988 | const contexts = [thread.projectTitle, thread.environmentLabel].filter( |
| 989 | (text): text is string => !!text, |
| 990 | ); |
| 991 | const rest = normalizedQuery |
| 992 | .split(" ") |
| 993 | .filter((token) => !contexts.some((text) => holds(text, token))) |
| 994 | .join(" "); |
| 995 | return rest && rest !== normalizedQuery ? hintFor(rest) : undefined; |
| 996 | } |
| 997 | |
| 998 | // A keystroke scores each thread's fields again, so they are listed once per subject. |
| 999 | const threadFieldsCache = new WeakMap<ThreadSearchSubject, ReadonlyArray<WeightedSearchField>>(); |
| 1000 | |
| 1001 | function threadSearchFields(thread: ThreadSearchSubject): ReadonlyArray<WeightedSearchField> { |
| 1002 | const cached = threadFieldsCache.get(thread); |
| 1003 | if (cached) return cached; |
| 1004 | const fields: WeightedSearchField[] = [{ value: thread.title, weight: 1, midWord: true }]; |
| 1005 | for (const pullRequest of thread.pullRequests ?? []) { |
| 1006 | fields.push({ value: `#${pullRequest.number}`, weight: 1 }); |
| 1007 | if (pullRequest.title) fields.push({ value: pullRequest.title, weight: 0.5 }); |
| 1008 | } |
| 1009 | const branch = searchableBranch(thread.branch); |
| 1010 | if (branch) fields.push({ value: branch, weight: 0.6 }); |
| 1011 | if (thread.projectTitle) { |
| 1012 | fields.push({ value: thread.projectTitle, weight: 0.25, context: true }); |
| 1013 | } |
| 1014 | if (thread.environmentLabel) { |
| 1015 | fields.push({ value: thread.environmentLabel, weight: 0.25, context: true }); |
| 1016 | } |
| 1017 | threadFieldsCache.set(thread, fields); |
| 1018 | return fields; |
| 1019 | } |
| 1020 | |
| 1021 | let lastFieldQuery: { readonly query: string; readonly fieldQuery: string } | undefined; |
| 1022 | |
| 1023 | // Strip pull request prefixes and the worktree prefix so queries match the stored fields. |
| 1024 | function threadFieldQuery(normalizedQuery: string): string { |
| 1025 | if (lastFieldQuery?.query !== normalizedQuery) { |
| 1026 | lastFieldQuery = { |
| 1027 | query: normalizedQuery, |
| 1028 | fieldQuery: normalizedQuery |
| 1029 | .replace(/^(?:pr|pull request|pull)\s*(?=#?\d)/, "") |
| 1030 | .replace(/^#\s*/, "") |
| 1031 | .replace(WORKTREE_BRANCH_PREFIX_PATTERN, "") |
| 1032 | .replace(FLAT_BRANCH_QUERY_PREFIX_PATTERN, "$1"), |
| 1033 | }; |
| 1034 | } |
| 1035 | return lastFieldQuery.fieldQuery; |
| 1036 | } |
| 1037 | |
| 1038 | /** |
| 1039 | * Scores a thread for a normalized query, or null when it does not match. |
| 1040 | * Titles and pull request numbers count fully, pull request titles and |
| 1041 | * branches less, project and environment names least. |
| 1042 | */ |
| 1043 | export function scoreThreadSearch( |
| 1044 | normalizedQuery: string, |
| 1045 | thread: ThreadSearchSubject, |
| 1046 | now: number, |
| 1047 | options?: { |
| 1048 | readonly typos?: boolean; |
| 1049 | /** |
| 1050 | * Palette picks; off where a pick would show up unexplained, such as a |
| 1051 | * sidebar filter or an agent's search. |
| 1052 | */ |
| 1053 | readonly picks?: boolean; |
| 1054 | }, |
| 1055 | ): ThreadSearchMatch | null { |
| 1056 | const fields = threadSearchFields(thread); |
| 1057 | const fieldQuery = threadFieldQuery(normalizedQuery); |
| 1058 | const fieldMatch = matchSearchFields(fieldQuery, fields, options); |
| 1059 | const referenceMatch = fieldMatch ? null : matchReference(normalizedQuery, thread); |
| 1060 | const match = fieldMatch ?? referenceMatch; |
| 1061 | if (match === null) return null; |
| 1062 | // A row whose title shows no match must say why. With several words, one |
| 1063 | // that cannot (its words spread over unrelated fields) is a coincidence and |
| 1064 | // is left out; a single word always sits in the field that matched it, so |
| 1065 | // its hint waits until the row is shown. |
| 1066 | const typos = options?.typos ?? false; |
| 1067 | const titleShowsMatch = match.primaryRanges.length > 0; |
| 1068 | const checkHint = !titleShowsMatch && referenceMatch === null && fieldQuery.includes(" "); |
| 1069 | const checkedHint = checkHint ? matchHint(fieldQuery, thread, typos) : undefined; |
| 1070 | if (checkHint && checkedHint === undefined) return null; |
| 1071 | const explain = titleShowsMatch |
| 1072 | ? undefined |
| 1073 | : (): SearchMatchHint | undefined => |
| 1074 | referenceMatch |
| 1075 | ? { field: "reference", label: "ID or link", text: normalizedQuery, ranges: [] } |
| 1076 | : (checkedHint ?? matchHint(fieldQuery, thread, typos)); |
| 1077 | const pick = options?.picks === false ? undefined : activePick(thread, normalizedQuery, now); |
| 1078 | return { |
| 1079 | score: match.quality * threadUsageBoost(thread, now), |
| 1080 | quality: match.quality, |
| 1081 | wholeWords: match.wholeWords, |
| 1082 | // A thread's whole title never lifts its group over a command or project |
| 1083 | // of that name: every new thread is titled "New thread" for a while. |
| 1084 | groupQuality: Math.min(match.quality, WHOLE_NAME - 0.01), |
| 1085 | strong: match.strong, |
| 1086 | ranges: match.primaryRanges, |
| 1087 | ...(explain ? { explain } : {}), |
| 1088 | ...(pick ? { pickedAt: pick.at } : {}), |
| 1089 | ...(pick?.query === pickedQuery(normalizedQuery) ? { pickedExactly: true } : {}), |
| 1090 | }; |
| 1091 | } |
| 1092 | |
| 1093 | /** When the user last used a thread: their last message or their last open. */ |
| 1094 | export function threadRecentUse(thread: ThreadSearchSubject): number { |
| 1095 | return Math.max(thread.activityAt ?? 0, thread.opens?.openedAt ?? 0); |
| 1096 | } |
| 1097 | |
| 1098 | /** |
| 1099 | * How strongly a thread's messages match among matches of one quality: a |
| 1100 | * thread that keeps using the word outweighs a recent passing mention, as |
| 1101 | * hits count for more than recency or use (21 hits about 5.5, one hit 2). |
| 1102 | */ |
| 1103 | function messageMatchWeight(hits: number): number { |
| 1104 | return 1 + Math.log2(1 + hits); |
| 1105 | } |
| 1106 | |
| 1107 | /** `withoutTitleMatches` reserves message rows for threads the palette has not already listed. */ |
| 1108 | export function rankMessageMatches< |
| 1109 | T extends { |
| 1110 | readonly quality?: number; |
| 1111 | readonly hits?: number; |
| 1112 | readonly messageCreatedAt?: string | null; |
| 1113 | }, |
| 1114 | >( |
| 1115 | matches: ReadonlyArray<T>, |
| 1116 | subjectOf: (match: T) => ThreadSearchSubject | undefined, |
| 1117 | normalizedQuery: string, |
| 1118 | now: number, |
| 1119 | options?: { readonly picks?: boolean; readonly withoutTitleMatches?: boolean }, |
| 1120 | ): T[] { |
| 1121 | return matches |
| 1122 | .flatMap((match) => { |
| 1123 | const subject = subjectOf(match); |
| 1124 | if (!subject) return []; |
| 1125 | if ( |
| 1126 | options?.withoutTitleMatches && |
| 1127 | scoreThreadSearch(normalizedQuery, subject, now, { picks: false }) !== null |
| 1128 | ) { |
| 1129 | return []; |
| 1130 | } |
| 1131 | // Older servers send no quality; their matches count as words. |
| 1132 | const quality = match.quality ?? 1; |
| 1133 | return [ |
| 1134 | { |
| 1135 | match, |
| 1136 | quality, |
| 1137 | pickedAt: |
| 1138 | options?.picks === false ? 0 : (activePick(subject, normalizedQuery, now)?.at ?? 0), |
| 1139 | score: messageMatchWeight(match.hits ?? 1) * threadUsageBoost(subject, now), |
| 1140 | }, |
| 1141 | ]; |
| 1142 | }) |
| 1143 | .sort( |
| 1144 | (left, right) => |
| 1145 | // Word matches first; among them a pick, then the closer match. |
| 1146 | Number(right.quality >= MESSAGE_PREFIX) - Number(left.quality >= MESSAGE_PREFIX) || |
| 1147 | right.pickedAt - left.pickedAt || |
| 1148 | right.quality - left.quality || |
| 1149 | right.score - left.score || |
| 1150 | (right.match.messageCreatedAt ?? "").localeCompare(left.match.messageCreatedAt ?? ""), |
| 1151 | ) |
| 1152 | .map(({ match }) => match); |
| 1153 | } |
| 1154 | |
| 1155 | /** Palette limits shared by web and mobile. */ |
| 1156 | export const PALETTE_THREAD_LIMIT = 20; |
| 1157 | export const PALETTE_MESSAGE_LIMIT = 10; |
| 1158 | /** Next to matching threads, other groups show only their best few rows. */ |
| 1159 | export const PALETTE_SECONDARY_LIMIT = 3; |
| 1160 | |
| 1161 | // Whole words and prefixes share a class so "Compact" does not lift settings over "Compaction". |
| 1162 | function matchClass(quality: number): number { |
| 1163 | return quality >= WHOLE_NAME ? 3 : quality >= 0.7 ? 2 : quality >= 0.4 ? 1 : 0; |
| 1164 | } |
| 1165 | |
| 1166 | export interface RankedSearchItem<T, M> { |
| 1167 | readonly item: T; |
| 1168 | readonly match: M; |
| 1169 | } |
| 1170 | |
| 1171 | /** |
| 1172 | * Rank groups by match class to keep typing stable and thread use from outweighing equal commands. |
| 1173 | * Try typos only without word-start matches: they add noise beside real matches and cost per key. |
| 1174 | */ |
| 1175 | export function rankSearchGroups< |
| 1176 | G, |
| 1177 | T, |
| 1178 | M extends { |
| 1179 | readonly score: number; |
| 1180 | readonly quality: number; |
| 1181 | readonly strong: boolean; |
| 1182 | readonly pickedAt?: number; |
| 1183 | readonly pickedExactly?: boolean; |
| 1184 | readonly groupQuality?: number; |
| 1185 | readonly wholeWords?: boolean; |
| 1186 | }, |
| 1187 | >( |
| 1188 | groups: ReadonlyArray<{ readonly group: G; readonly items: ReadonlyArray<T> }>, |
| 1189 | score: (item: T, options: { readonly typos: boolean }, group: G) => M | null, |
| 1190 | ): Array<{ readonly group: G; readonly ranked: ReadonlyArray<RankedSearchItem<T, M>> }> { |
| 1191 | const rank = (typos: boolean) => |
| 1192 | groups.map(({ group, items }) => { |
| 1193 | const options = { typos }; |
| 1194 | const ranked: Array<RankedSearchItem<T, M>> = []; |
| 1195 | for (const item of items) { |
| 1196 | const match = score(item, options, group); |
| 1197 | if (match !== null) ranked.push({ item, match }); |
| 1198 | } |
| 1199 | return { group, ranked }; |
| 1200 | }); |
| 1201 | let ranked = rank(false); |
| 1202 | if (!ranked.some((entry) => entry.ranked.some(({ match }) => match.strong))) { |
| 1203 | ranked = rank(true); |
| 1204 | } |
| 1205 | return ranked |
| 1206 | .flatMap(({ group, ranked: items }, order) => { |
| 1207 | if (items.length === 0) return []; |
| 1208 | // Use cannot lift a project-only match above a title match or cross match classes. |
| 1209 | // Picks reorder word matches, keeping typos and mid-word hits below them. |
| 1210 | // A longer-query pick must not pass a whole-name match for the current query. |
| 1211 | const wordMatch = (match: M) => Math.min(matchClass(match.quality), 2); |
| 1212 | const exactPickAt = (match: M) => (match.pickedExactly ? (match.pickedAt ?? 0) : 0); |
| 1213 | // Use reorders whole words or prefixes among themselves, never a prefix above a whole word. |
| 1214 | const wholeWord = (match: M) => Number(match.wholeWords ?? match.quality >= WHOLE_WORD); |
| 1215 | const sorted = [...items].sort( |
| 1216 | (left, right) => |
| 1217 | wordMatch(right.match) - wordMatch(left.match) || |
| 1218 | exactPickAt(right.match) - exactPickAt(left.match) || |
| 1219 | matchClass(right.match.quality) - matchClass(left.match.quality) || |
| 1220 | (right.match.pickedAt ?? 0) - (left.match.pickedAt ?? 0) || |
| 1221 | wholeWord(right.match) - wholeWord(left.match) || |
| 1222 | right.match.score - left.match.score, |
| 1223 | ); |
| 1224 | const best = Math.max( |
| 1225 | ...items.map(({ match }) => matchClass(match.groupQuality ?? match.quality)), |
| 1226 | ); |
| 1227 | return [{ group, ranked: sorted, best, order }]; |
| 1228 | }) |
| 1229 | .sort((left, right) => right.best - left.best || left.order - right.order) |
| 1230 | .map(({ group, ranked: items }) => ({ group, ranked: items })); |
| 1231 | } |
| 1232 | |
| 1233 | /** `rankSearchGroups` for a single list. */ |
| 1234 | export function rankSearchItems< |
| 1235 | T, |
| 1236 | M extends { readonly score: number; readonly quality: number; readonly strong: boolean }, |
| 1237 | >( |
| 1238 | items: ReadonlyArray<T>, |
| 1239 | score: (item: T, options: { readonly typos: boolean }) => M | null, |
| 1240 | ): ReadonlyArray<RankedSearchItem<T, M>> { |
| 1241 | return rankSearchGroups([{ group: null, items }], score)[0]?.ranked ?? []; |
| 1242 | } |
| 1243 | |
| 1244 | export interface SearchTermsMatch { |
| 1245 | readonly score: number; |
| 1246 | readonly quality: number; |
| 1247 | /** The quality its group ranks by, when lower; see `scoreSearchTerms`. */ |
| 1248 | readonly groupQuality?: number; |
| 1249 | readonly strong: boolean; |
| 1250 | readonly ranges: ReadonlyArray<SearchRange>; |
| 1251 | } |
| 1252 | |
| 1253 | const KEYWORD_QUALITY = 0.65; |
| 1254 | // Below this, keyword prefixes match too much: "co" or "pro" would list most |
| 1255 | // settings. A short query still matches a keyword it equals ("pr"). |
| 1256 | const KEYWORD_QUERY_MIN_LENGTH = 4; |
| 1257 | |
| 1258 | /** |
| 1259 | * Keywords count less so hidden terms cannot lift a group above a matching name. |
| 1260 | * Short queries need whole keywords to avoid listing most settings for common prefixes. |
| 1261 | */ |
| 1262 | export function scoreSearchTerms( |
| 1263 | normalizedQuery: string, |
| 1264 | terms: ReadonlyArray<string>, |
| 1265 | options?: { readonly typos?: boolean }, |
| 1266 | ): SearchTermsMatch | null { |
| 1267 | // Filler words ("the ci") do not make a short query long. |
| 1268 | const meaningful = normalizedQuery |
| 1269 | .split(" ") |
| 1270 | .filter((token) => !FILLER_WORDS.has(token)) |
| 1271 | .join(" "); |
| 1272 | const short = (meaningful || normalizedQuery).length < KEYWORD_QUERY_MIN_LENGTH; |
| 1273 | const match = matchSearchFields( |
| 1274 | normalizedQuery, |
| 1275 | terms.map((value, index) => |
| 1276 | index === 0 |
| 1277 | ? { value, weight: 1 } |
| 1278 | : // An alias typed in full ("pr") is deliberate, above a mere name prefix. |
| 1279 | { value, weight: short ? 0.8 : 0.6, wholeWords: short, keyword: true }, |
| 1280 | ), |
| 1281 | options, |
| 1282 | ); |
| 1283 | return ( |
| 1284 | match && { |
| 1285 | score: match.quality, |
| 1286 | quality: match.quality, |
| 1287 | // Below the word-start class: a match only in hidden keywords must not put |
| 1288 | // its group above a result whose name matches. Inside the group an exact |
| 1289 | // alias still beats a name prefix ("pr" lists "Open pull requests" first). |
| 1290 | ...(match.primaryRanges.length > 0 |
| 1291 | ? {} |
| 1292 | : { groupQuality: Math.min(match.quality, KEYWORD_QUALITY) }), |
| 1293 | strong: match.strong, |
| 1294 | ranges: match.primaryRanges, |
| 1295 | } |
| 1296 | ); |
| 1297 | } |