1// Copyright (C) 2023 The Android Open Source Project 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15import {byLengthAsc, Fzf} from 'fzf'; 16import {SyncOptionsTuple} from 'fzf/dist/types/finders'; 17 18export interface FuzzySegment { 19 matching: boolean; 20 value: string; 21} 22 23export interface FuzzyResult<T> { 24 item: T; 25 segments: FuzzySegment[]; 26} 27 28export type KeyLookup<T> = (x: T) => string; 29 30// Finds approx matching in arbitrary lists of items. 31export class FuzzyFinder<T> { 32 private readonly fzf: Fzf<ReadonlyArray<T>>; 33 // Because we operate on arbitrary lists, a key lookup function is required to 34 // so we know which part of the list is to be be searched. It should return 35 // the relevant search string for each item. 36 constructor( 37 items: ReadonlyArray<T>, 38 private readonly keyLookup: KeyLookup<T>, 39 ) { 40 // NOTE(stevegolton): This type assertion because FZF appears to be very 41 // fussy about its input types. 42 const options = [ 43 {selector: keyLookup, tiebreakers: [byLengthAsc]}, 44 ] as SyncOptionsTuple<T>; 45 this.fzf = new Fzf<ReadonlyArray<T>>(items, ...options); 46 } 47 48 // Return a list of items that match any of the search terms. 49 find(searchTerm: string): FuzzyResult<T>[] { 50 return this.fzf.find(searchTerm).map((m) => { 51 const normalisedTerm = this.keyLookup(m.item); 52 return { 53 item: m.item, 54 segments: indiciesToSegments( 55 Array.from(m.positions).sort((a, b) => a - b), 56 normalisedTerm, 57 ), 58 }; 59 }); 60 } 61} 62 63// Given a list of indicies of matching chars, and the original value, produce 64// a list of match/nomatch segments. 65function indiciesToSegments(indicies: number[], text: string): FuzzySegment[] { 66 const segments: FuzzySegment[] = []; 67 let nextIndex = 0; 68 let match = ''; 69 for (const i of indicies) { 70 if (nextIndex < i) { 71 // If we had a match segment from before, add it now. 72 if (match !== '') { 73 segments.push({matching: true, value: match}); 74 match = ''; 75 } 76 // Missed some indicies - wrap them up into a nomatch segment. 77 segments.push({matching: false, value: text.slice(nextIndex, i)}); 78 } 79 80 // Append this matching char to the previous match. 81 match += text[i]; 82 nextIndex = i + 1; 83 } 84 85 // Add any lingering match segment. 86 if (match !== '') { 87 segments.push({matching: true, value: match}); 88 } 89 90 // Add final nomatch segment if there is anything left. 91 if (nextIndex < text.length) { 92 segments.push({matching: false, value: text.slice(nextIndex)}); 93 } 94 95 return segments; 96} 97 98// Evaluate whether |searchTerm| is found in |text|. 99// |indicies| is an array of numbers the same length as |searchTerm|, into which 100// we place the indicies of the matching chars in |text|. 101function match(searchTerm: string, text: string, indicies: number[]): boolean { 102 let j = 0; // index into the searchTerm. 103 let success: boolean = true; 104 105 // For each char of the searchTerm... 106 for (let i = 0; i < searchTerm.length; ++i) { 107 const char = searchTerm[i].toLowerCase(); 108 // ...advance the text index until we find the char. 109 for (; j < text.length; ++j) { 110 // If we find it add it to the segment and move on. 111 if (text[j].toLowerCase() === char) { 112 indicies[i] = j; 113 break; 114 } 115 } 116 117 // Failed to find searchTerm[i] in text: give up. 118 if (j === text.length) { 119 success = false; 120 break; 121 } 122 123 ++j; 124 } 125 126 return success; 127} 128 129export interface FuzzyMatch { 130 matches: boolean; 131 segments: FuzzySegment[]; 132} 133 134// Fuzzy match a single piece of text against several search terms. 135// If any of the terms match, the result of the match is true. 136export function fuzzyMatch( 137 text: string, 138 ...searchTerms: ReadonlyArray<string> 139): FuzzyMatch { 140 for (const searchTerm of searchTerms) { 141 const indicies: number[] = new Array(searchTerm.length); 142 if (match(searchTerm, text, indicies)) { 143 const segments = indiciesToSegments(indicies, text); 144 return { 145 matches: true, 146 segments, 147 }; 148 } 149 } 150 151 return { 152 matches: false, 153 segments: [], 154 }; 155} 156