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