Debian Codegraph @

frontend/src/lib/fuzzy.ts

raw
1 /**
2 * Fuzzy match a pattern against a string.
3 *
4 * @param pattern The pattern to search for.
5 * @param text The string to search in.
6 *
7 * Returns a score greater than zero if all characters of `pattern` can be
8 * found in order in `string`. For lowercase characters in `pattern` match both
9 * lower and upper case, for uppercase only an exact match counts.
10 */
11 export function fuzzytest(pattern: string, text: string): number {
12 const casesensitive = pattern === pattern.toLowerCase();
13 const exact = casesensitive
14 ? text.toLowerCase().indexOf(pattern)
15 : text.indexOf(pattern);
16 if (exact > -1) {
17 return pattern.length ** 2;
18 }
19 let score = 0;
20 let localScore = 0;
21 let pindex = 0;
22 for (const char of text) {
23 const search = pattern[pindex];
24 if (char === search || char.toLowerCase() === search) {
25 pindex += 1;
26 localScore += +1;
27 } else {
28 localScore = 0;
29 }
30 score += localScore;
31 }
32 return pindex === pattern.length ? score : 0;
33 }
34
35 /**
36 * Filter a list of possible suggestions to only those that match the pattern
37 */
38 export function fuzzyfilter(
39 pattern: string,
40 suggestions: readonly string[],
41 ): readonly string[] {
42 if (!pattern) {
43 return suggestions;
44 }
45 return suggestions
46 .map((s): [string, number] => [s, fuzzytest(pattern, s)])
47 .filter(([, score]) => score > 0)
48 .sort((a, b) => b[1] - a[1])
49 .map(([s]) => s);
50 }
51
52 export type FuzzyWrappedText = ["text" | "match", string][];
53
54 /**
55 * Wrap fuzzy matched characters.
56 *
57 * Wrap all occurences of characters of `pattern` (in order) in `string` in
58 * tuples with a "match" marker (and the others as plain "text") to allow for
59 * the matches to be wrapped in markers to highlight them in the HTML.
60 */
61 export function fuzzywrap(pattern: string, text: string): FuzzyWrappedText {
62 if (!pattern) {
63 return [["text", text]];
64 }
65 const casesensitive = pattern === pattern.toLowerCase();
66 const exact = casesensitive
67 ? text.toLowerCase().indexOf(pattern)
68 : text.indexOf(pattern);
69 if (exact > -1) {
70 const before = text.slice(0, exact);
71 const match = text.slice(exact, exact + pattern.length);
72 const after = text.slice(exact + pattern.length);
73 const result: FuzzyWrappedText = [];
74 if (before) {
75 result.push(["text", before]);
76 }
77 result.push(["match", match]);
78 if (after) {
79 result.push(["text", after]);
80 }
81 return result;
82 }
83 // current index into the pattern
84 let pindex = 0;
85 // current unmatched string
86 let plain: string | null = null;
87 // current matched string
88 let match: string | null = null;
89 const result: FuzzyWrappedText = [];
90 for (const char of text) {
91 const search = pattern[pindex];
92 if (char === search || char.toLowerCase() === search) {
93 match = match != null ? match + char : char;
94 if (plain != null) {
95 result.push(["text", plain]);
96 plain = null;
97 }
98 pindex += 1;
99 } else {
100 plain = plain != null ? plain + char : char;
101 if (match != null) {
102 result.push(["match", match]);
103 match = null;
104 }
105 }
106 }
107 if (pindex < pattern.length) {
108 return [["text", text]];
109 }
110 if (plain != null) {
111 result.push(["text", plain]);
112 plain = null;
113 }
114 if (match != null) {
115 result.push(["match", match]);
116 match = null;
117 }
118 return result;
119 }