1export type RankedSearchResult<T> = {
2 item: T;
3 score: number;
4 tieBreaker: string;
5};
6
7export function normalizeSearchQuery(
8 input: string,
9 options?: {
10 trimLeadingPattern?: RegExp;
11 },
12): string {
13 const trimmed = input.trim();
14 if (!trimmed) {
15 return "";
16 }
17 return options?.trimLeadingPattern
18 ? trimmed.replace(options.trimLeadingPattern, "").toLowerCase()
19 : trimmed.toLowerCase();
20}
21
22export function scoreSubsequenceMatch(value: string, query: string): number | null {
23 if (!query) return 0;
24
25 let queryIndex = 0;
26 let firstMatchIndex = -1;
27 let previousMatchIndex = -1;
28 let gapPenalty = 0;
29
30 for (let valueIndex = 0; valueIndex < value.length; valueIndex += 1) {
31 if (value[valueIndex] !== query[queryIndex]) {
32 continue;
33 }
34
35 if (firstMatchIndex === -1) {
36 firstMatchIndex = valueIndex;
37 }
38 if (previousMatchIndex !== -1) {
39 gapPenalty += valueIndex - previousMatchIndex - 1;
40 }
41
42 previousMatchIndex = valueIndex;
43 queryIndex += 1;
44 if (queryIndex === query.length) {
45 const spanPenalty = valueIndex - firstMatchIndex + 1 - query.length;
46 const lengthPenalty = Math.min(64, value.length - query.length);
47 return firstMatchIndex * 2 + gapPenalty * 3 + spanPenalty + lengthPenalty;
48 }
49 }
50
51 return null;
52}
53
54function lengthPenalty(value: string, query: string): number {
55 return Math.min(64, Math.max(0, value.length - query.length));
56}
57
58function findBoundaryMatchIndex(
59 value: string,
60 query: string,
61 boundaryMarkers: readonly string[],
62): number | null {
63 let bestIndex: number | null = null;
64
65 for (const marker of boundaryMarkers) {
66 const index = value.indexOf(`${marker}${query}`);
67 if (index === -1) {
68 continue;
69 }
70
71 const matchIndex = index + marker.length;
72 if (bestIndex === null || matchIndex < bestIndex) {
73 bestIndex = matchIndex;
74 }
75 }
76
77 return bestIndex;
78}
79
80/**
81 * Scores how well `value` matches `query` using tiered match strategies.
82 *
83 * **Expects pre-normalized inputs**: both `value` and `query` must already be
84 * trimmed and lowercased (e.g. via {@link normalizeSearchQuery}).
85 */
86export function scoreQueryMatch(input: {
87 value: string;
88 query: string;
89 exactBase: number;
90 prefixBase?: number;
91 boundaryBase?: number;
92 includesBase?: number;
93 fuzzyBase?: number;
94 boundaryMarkers?: readonly string[];
95}): number | null {
96 const { value, query } = input;
97
98 if (!value || !query) {
99 return null;
100 }
101
102 if (value === query) {
103 return input.exactBase;
104 }
105
106 if (input.prefixBase !== undefined && value.startsWith(query)) {
107 return input.prefixBase + lengthPenalty(value, query);
108 }
109
110 if (input.boundaryBase !== undefined) {
111 const boundaryIndex = findBoundaryMatchIndex(
112 value,
113 query,
114 input.boundaryMarkers ?? [" ", "-", "_", "/"],
115 );
116 if (boundaryIndex !== null) {
117 return input.boundaryBase + boundaryIndex * 2 + lengthPenalty(value, query);
118 }
119 }
120
121 if (input.includesBase !== undefined) {
122 const includesIndex = value.indexOf(query);
123 if (includesIndex !== -1) {
124 return input.includesBase + includesIndex * 2 + lengthPenalty(value, query);
125 }
126 }
127
128 if (input.fuzzyBase !== undefined) {
129 const fuzzyScore = scoreSubsequenceMatch(value, query);
130 if (fuzzyScore !== null) {
131 return input.fuzzyBase + fuzzyScore;
132 }
133 }
134
135 return null;
136}
137
138function compareRankedSearchResults<T>(
139 left: RankedSearchResult<T>,
140 right: RankedSearchResult<T>,
141): number {
142 const scoreDelta = left.score - right.score;
143 if (scoreDelta !== 0) return scoreDelta;
144 return left.tieBreaker.localeCompare(right.tieBreaker);
145}
146
147function findInsertionIndex<T>(
148 rankedEntries: RankedSearchResult<T>[],
149 candidate: RankedSearchResult<T>,
150): number {
151 let low = 0;
152 let high = rankedEntries.length;
153
154 while (low < high) {
155 const middle = low + Math.floor((high - low) / 2);
156 const current = rankedEntries[middle];
157 if (!current) {
158 break;
159 }
160
161 if (compareRankedSearchResults(candidate, current) < 0) {
162 high = middle;
163 } else {
164 low = middle + 1;
165 }
166 }
167
168 return low;
169}
170
171export function insertRankedSearchResult<T>(
172 rankedEntries: RankedSearchResult<T>[],
173 candidate: RankedSearchResult<T>,
174 limit: number,
175): void {
176 if (limit <= 0) {
177 return;
178 }
179
180 const insertionIndex = findInsertionIndex(rankedEntries, candidate);
181 if (rankedEntries.length < limit) {
182 rankedEntries.splice(insertionIndex, 0, candidate);
183 return;
184 }
185
186 if (insertionIndex >= limit) {
187 return;
188 }
189
190 rankedEntries.splice(insertionIndex, 0, candidate);
191 rankedEntries.pop();
192}