| 1 |
//===--- FuzzyMatch.h - Approximate identifier matching ---------*- C++-*-===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// To check for a match between a Pattern ('u_p') and a Word ('unique_ptr'), |
| 10 |
// we consider the possible partial match states: |
| 11 |
// |
| 12 |
// u n i q u e _ p t r |
| 13 |
// +--------------------- |
| 14 |
// |A . . . . . . . . . . |
| 15 |
// u| |
| 16 |
// |. . . . . . . . . . . |
| 17 |
// _| |
| 18 |
// |. . . . . . . O . . . |
| 19 |
// p| |
| 20 |
// |. . . . . . . . . . B |
| 21 |
// |
| 22 |
// Each dot represents some prefix of the pattern being matched against some |
| 23 |
// prefix of the word. |
| 24 |
// - A is the initial state: '' matched against '' |
| 25 |
// - O is an intermediate state: 'u_' matched against 'unique_' |
| 26 |
// - B is the target state: 'u_p' matched against 'unique_ptr' |
| 27 |
// |
| 28 |
// We aim to find the best path from A->B. |
| 29 |
// - Moving right (consuming a word character) |
| 30 |
// Always legal: not all word characters must match. |
| 31 |
// - Moving diagonally (consuming both a word and pattern character) |
| 32 |
// Legal if the characters match. |
| 33 |
// - Moving down (consuming a pattern character) is never legal. |
| 34 |
// Never legal: all pattern characters must match something. |
| 35 |
// Characters are matched case-insensitively. |
| 36 |
// The first pattern character may only match the start of a word segment. |
| 37 |
// |
| 38 |
// The scoring is based on heuristics: |
| 39 |
// - when matching a character, apply a bonus or penalty depending on the |
| 40 |
// match quality (does case match, do word segments align, etc) |
| 41 |
// - when skipping a character, apply a penalty if it hurts the match |
| 42 |
// (it starts a word segment, or splits the matched region, etc) |
| 43 |
// |
| 44 |
// These heuristics require the ability to "look backward" one character, to |
| 45 |
// see whether it was matched or not. Therefore the dynamic-programming matrix |
| 46 |
// has an extra dimension (last character matched). |
| 47 |
// Each entry also has an additional flag indicating whether the last-but-one |
| 48 |
// character matched, which is needed to trace back through the scoring table |
| 49 |
// and reconstruct the match. |
| 50 |
// |
| 51 |
// We treat strings as byte-sequences, so only ASCII has first-class support. |
| 52 |
// |
| 53 |
// This algorithm was inspired by VS code's client-side filtering, and aims |
| 54 |
// to be mostly-compatible. |
| 55 |
// |
| 56 |
//===----------------------------------------------------------------------===// |
| 57 |
|
| 58 |
#include "FuzzyMatch.h" |
| 59 |
#include "llvm/Support/Format.h" |
| 60 |
#include <optional> |
| 61 |
|
| 62 |
namespace clang { |
| 63 |
namespace clangd { |
| 64 |
|
| 65 |
constexpr int FuzzyMatcher::MaxPat; |
| 66 |
constexpr int FuzzyMatcher::MaxWord; |
| 67 |
|
| 68 |
static char lower(char C) { return C >= 'A' && C <= 'Z' ? C + ('a' - 'A') : C; } |
| 69 |
// A "negative infinity" score that won't overflow. |
| 70 |
// We use this to mark unreachable states and forbidden solutions. |
| 71 |
// Score field is 15 bits wide, min value is -2^14, we use half of that. |
| 72 |
static constexpr int AwfulScore = -(1 << 13); |
| 73 |
static bool isAwful(int S) { return S < AwfulScore / 2; } |
| 74 |
static constexpr int PerfectBonus = 4; // Perfect per-pattern-char score. |
| 75 |
|
| 76 |
FuzzyMatcher::FuzzyMatcher(llvm::StringRef Pattern) |
| 77 |
: PatN(std::min<int>(MaxPat, Pattern.size())), |
| 78 |
ScoreScale(PatN ? float{1} / (PerfectBonus * PatN) : 0), WordN(0) { |
| 79 |
std::copy(Pattern.begin(), Pattern.begin() + PatN, Pat); |
| 80 |
for (int I = 0; I < PatN; ++I) |
| 81 |
LowPat[I] = lower(Pat[I]); |
| 82 |
Scores[0][0][Miss] = {0, Miss}; |
| 83 |
Scores[0][0][Match] = {AwfulScore, Miss}; |
| 84 |
for (int P = 0; P <= PatN; ++P) |
| 85 |
for (int W = 0; W < P; ++W) |
| 86 |
for (Action A : {Miss, Match}) |
| 87 |
Scores[P][W][A] = {AwfulScore, Miss}; |
| 88 |
PatTypeSet = calculateRoles(llvm::StringRef(Pat, PatN), |
| 89 |
llvm::MutableArrayRef(PatRole, PatN)); |
| 90 |
} |
| 91 |
|
| 92 |
std::optional<float> FuzzyMatcher::match(llvm::StringRef Word) { |
| 93 |
if (!(WordContainsPattern = init(Word))) |
| 94 |
return std::nullopt; |
| 95 |
if (!PatN) |
| 96 |
return 1; |
| 97 |
buildGraph(); |
| 98 |
auto Best = std::max(Scores[PatN][WordN][Miss].Score, |
| 99 |
Scores[PatN][WordN][Match].Score); |
| 100 |
if (isAwful(Best)) |
| 101 |
return std::nullopt; |
| 102 |
float Score = |
| 103 |
ScoreScale * std::min(PerfectBonus * PatN, std::max<int>(0, Best)); |
| 104 |
// If the pattern is as long as the word, we have an exact string match, |
| 105 |
// since every pattern character must match something. |
| 106 |
if (WordN == PatN) |
| 107 |
Score *= 2; // May not be perfect 2 if case differs in a significant way. |
| 108 |
return Score; |
| 109 |
} |
| 110 |
|
| 111 |
// We get CharTypes from a lookup table. Each is 2 bits, 4 fit in each byte. |
| 112 |
// The top 6 bits of the char select the byte, the bottom 2 select the offset. |
| 113 |
// e.g. 'q' = 010100 01 = byte 28 (55), bits 3-2 (01) -> Lower. |
| 114 |
constexpr static uint8_t CharTypes[] = { |
| 115 |
0x00, 0x00, 0x00, 0x00, // Control characters |
| 116 |
0x00, 0x00, 0x00, 0x00, // Control characters |
| 117 |
0xff, 0xff, 0xff, 0xff, // Punctuation |
| 118 |
0x55, 0x55, 0xf5, 0xff, // Numbers->Lower, more Punctuation. |
| 119 |
0xab, 0xaa, 0xaa, 0xaa, // @ and A-O |
| 120 |
0xaa, 0xaa, 0xea, 0xff, // P-Z, more Punctuation. |
| 121 |
0x57, 0x55, 0x55, 0x55, // ` and a-o |
| 122 |
0x55, 0x55, 0xd5, 0x3f, // p-z, Punctuation, DEL. |
| 123 |
0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, // Bytes over 127 -> Lower. |
| 124 |
0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, // (probably UTF-8). |
| 125 |
0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, |
| 126 |
0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, |
| 127 |
}; |
| 128 |
|
| 129 |
// The Role can be determined from the Type of a character and its neighbors: |
| 130 |
// |
| 131 |
// Example | Chars | Type | Role |
| 132 |
// ---------+--------------+----- |
| 133 |
// F(o)oBar | Foo | Ull | Tail |
| 134 |
// Foo(B)ar | oBa | lUl | Head |
| 135 |
// (f)oo | ^fo | Ell | Head |
| 136 |
// H(T)TP | HTT | UUU | Tail |
| 137 |
// |
| 138 |
// Our lookup table maps a 6 bit key (Prev, Curr, Next) to a 2-bit Role. |
| 139 |
// A byte packs 4 Roles. (Prev, Curr) selects a byte, Next selects the offset. |
| 140 |
// e.g. Lower, Upper, Lower -> 01 10 01 -> byte 6 (aa), bits 3-2 (10) -> Head. |
| 141 |
constexpr static uint8_t CharRoles[] = { |
| 142 |
// clang-format off |
| 143 |
// Curr= Empty Lower Upper Separ |
| 144 |
/* Prev=Empty */ 0x00, 0xaa, 0xaa, 0xff, // At start, Lower|Upper->Head |
| 145 |
/* Prev=Lower */ 0x00, 0x55, 0xaa, 0xff, // In word, Upper->Head;Lower->Tail |
| 146 |
/* Prev=Upper */ 0x00, 0x55, 0x59, 0xff, // Ditto, but U(U)U->Tail |
| 147 |
/* Prev=Separ */ 0x00, 0xaa, 0xaa, 0xff, // After separator, like at start |
| 148 |
// clang-format on |
| 149 |
}; |
| 150 |
|
| 151 |
template <typename T> static T packedLookup(const uint8_t *Data, int I) { |
| 152 |
return static_cast<T>((Data[I >> 2] >> ((I & 3) * 2)) & 3); |
| 153 |
} |
| 154 |
CharTypeSet calculateRoles(llvm::StringRef Text, |
| 155 |
llvm::MutableArrayRef<CharRole> Roles) { |
| 156 |
assert(Text.size() == Roles.size()); |
| 157 |
if (Text.size() == 0) |
| 158 |
return 0; |
| 159 |
CharType Type = packedLookup<CharType>(CharTypes, Text[0]); |
| 160 |
CharTypeSet TypeSet = 1 << Type; |
| 161 |
// Types holds a sliding window of (Prev, Curr, Next) types. |
| 162 |
// Initial value is (Empty, Empty, type of Text[0]). |
| 163 |
int Types = Type; |
| 164 |
// Rotate slides in the type of the next character. |
| 165 |
auto Rotate = [&](CharType T) { Types = ((Types << 2) | T) & 0x3f; }; |
| 166 |
for (unsigned I = 0; I < Text.size() - 1; ++I) { |
| 167 |
// For each character, rotate in the next, and look up the role. |
| 168 |
Type = packedLookup<CharType>(CharTypes, Text[I + 1]); |
| 169 |
TypeSet |= 1 << Type; |
| 170 |
Rotate(Type); |
| 171 |
Roles[I] = packedLookup<CharRole>(CharRoles, Types); |
| 172 |
} |
| 173 |
// For the last character, the "next character" is Empty. |
| 174 |
Rotate(Empty); |
| 175 |
Roles[Text.size() - 1] = packedLookup<CharRole>(CharRoles, Types); |
| 176 |
return TypeSet; |
| 177 |
} |
| 178 |
|
| 179 |
// Sets up the data structures matching Word. |
| 180 |
// Returns false if we can cheaply determine that no match is possible. |
| 181 |
bool FuzzyMatcher::init(llvm::StringRef NewWord) { |
| 182 |
WordN = std::min<int>(MaxWord, NewWord.size()); |
| 183 |
if (PatN > WordN) |
| 184 |
return false; |
| 185 |
std::copy(NewWord.begin(), NewWord.begin() + WordN, Word); |
| 186 |
if (PatN == 0) |
| 187 |
return true; |
| 188 |
for (int I = 0; I < WordN; ++I) |
| 189 |
LowWord[I] = lower(Word[I]); |
| 190 |
|
| 191 |
// Cheap subsequence check. |
| 192 |
for (int W = 0, P = 0; P != PatN; ++W) { |
| 193 |
if (W == WordN) |
| 194 |
return false; |
| 195 |
if (LowWord[W] == LowPat[P]) |
| 196 |
++P; |
| 197 |
} |
| 198 |
|
| 199 |
// FIXME: some words are hard to tokenize algorithmically. |
| 200 |
// e.g. vsprintf is V S Print F, and should match [pri] but not [int]. |
| 201 |
// We could add a tokenization dictionary for common stdlib names. |
| 202 |
WordTypeSet = calculateRoles(llvm::StringRef(Word, WordN), |
| 203 |
llvm::MutableArrayRef(WordRole, WordN)); |
| 204 |
return true; |
| 205 |
} |
| 206 |
|
| 207 |
// The forwards pass finds the mappings of Pattern onto Word. |
| 208 |
// Score = best score achieved matching Word[..W] against Pat[..P]. |
| 209 |
// Unlike other tables, indices range from 0 to N *inclusive* |
| 210 |
// Matched = whether we chose to match Word[W] with Pat[P] or not. |
| 211 |
// |
| 212 |
// Points are mostly assigned to matched characters, with 1 being a good score |
| 213 |
// and 3 being a great one. So we treat the score range as [0, 3 * PatN]. |
| 214 |
// This range is not strict: we can apply larger bonuses/penalties, or penalize |
| 215 |
// non-matched characters. |
| 216 |
void FuzzyMatcher::buildGraph() { |
| 217 |
for (int W = 0; W < WordN; ++W) { |
| 218 |
Scores[0][W + 1][Miss] = {Scores[0][W][Miss].Score - skipPenalty(W, Miss), |
| 219 |
Miss}; |
| 220 |
Scores[0][W + 1][Match] = {AwfulScore, Miss}; |
| 221 |
} |
| 222 |
for (int P = 0; P < PatN; ++P) { |
| 223 |
for (int W = P; W < WordN; ++W) { |
| 224 |
auto &Score = Scores[P + 1][W + 1], &PreMiss = Scores[P + 1][W]; |
| 225 |
|
| 226 |
auto MatchMissScore = PreMiss[Match].Score; |
| 227 |
auto MissMissScore = PreMiss[Miss].Score; |
| 228 |
if (P < PatN - 1) { // Skipping trailing characters is always free. |
| 229 |
MatchMissScore -= skipPenalty(W, Match); |
| 230 |
MissMissScore -= skipPenalty(W, Miss); |
| 231 |
} |
| 232 |
Score[Miss] = (MatchMissScore > MissMissScore) |
| 233 |
? ScoreInfo{MatchMissScore, Match} |
| 234 |
: ScoreInfo{MissMissScore, Miss}; |
| 235 |
|
| 236 |
auto &PreMatch = Scores[P][W]; |
| 237 |
auto MatchMatchScore = |
| 238 |
allowMatch(P, W, Match) |
| 239 |
? PreMatch[Match].Score + matchBonus(P, W, Match) |
| 240 |
: AwfulScore; |
| 241 |
auto MissMatchScore = allowMatch(P, W, Miss) |
| 242 |
? PreMatch[Miss].Score + matchBonus(P, W, Miss) |
| 243 |
: AwfulScore; |
| 244 |
Score[Match] = (MatchMatchScore > MissMatchScore) |
| 245 |
? ScoreInfo{MatchMatchScore, Match} |
| 246 |
: ScoreInfo{MissMatchScore, Miss}; |
| 247 |
} |
| 248 |
} |
| 249 |
} |
| 250 |
|
| 251 |
bool FuzzyMatcher::allowMatch(int P, int W, Action Last) const { |
| 252 |
if (LowPat[P] != LowWord[W]) |
| 253 |
return false; |
| 254 |
// We require a "strong" match: |
| 255 |
// - for the first pattern character. [foo] !~ "barefoot" |
| 256 |
// - after a gap. [pat] !~ "patnther" |
| 257 |
if (Last == Miss) { |
| 258 |
// We're banning matches outright, so conservatively accept some other cases |
| 259 |
// where our segmentation might be wrong: |
| 260 |
// - allow matching B in ABCDef (but not in NDEBUG) |
| 261 |
// - we'd like to accept print in sprintf, but too many false positives |
| 262 |
if (WordRole[W] == Tail && |
| 263 |
(Word[W] == LowWord[W] || !(WordTypeSet & 1 << Lower))) |
| 264 |
return false; |
| 265 |
} |
| 266 |
return true; |
| 267 |
} |
| 268 |
|
| 269 |
int FuzzyMatcher::skipPenalty(int W, Action Last) const { |
| 270 |
if (W == 0) // Skipping the first character. |
| 271 |
return 3; |
| 272 |
if (WordRole[W] == Head) // Skipping a segment. |
| 273 |
return 1; // We want to keep this lower than a consecutive match bonus. |
| 274 |
// Instead of penalizing non-consecutive matches, we give a bonus to a |
| 275 |
// consecutive match in matchBonus. This produces a better score distribution |
| 276 |
// than penalties in case of small patterns, e.g. 'up' for 'unique_ptr'. |
| 277 |
return 0; |
| 278 |
} |
| 279 |
|
| 280 |
int FuzzyMatcher::matchBonus(int P, int W, Action Last) const { |
| 281 |
assert(LowPat[P] == LowWord[W]); |
| 282 |
int S = 1; |
| 283 |
bool IsPatSingleCase = |
| 284 |
(PatTypeSet == 1 << Lower) || (PatTypeSet == 1 << Upper); |
| 285 |
// Bonus: case matches, or a Head in the pattern aligns with one in the word. |
| 286 |
// Single-case patterns lack segmentation signals and we assume any character |
| 287 |
// can be a head of a segment. |
| 288 |
if (Pat[P] == Word[W] || |
| 289 |
(WordRole[W] == Head && (IsPatSingleCase || PatRole[P] == Head))) |
| 290 |
++S; |
| 291 |
// Bonus: a consecutive match. First character match also gets a bonus to |
| 292 |
// ensure prefix final match score normalizes to 1.0. |
| 293 |
if (W == 0 || Last == Match) |
| 294 |
S += 2; |
| 295 |
// Penalty: matching inside a segment (and previous char wasn't matched). |
| 296 |
if (WordRole[W] == Tail && P && Last == Miss) |
| 297 |
S -= 3; |
| 298 |
// Penalty: a Head in the pattern matches in the middle of a word segment. |
| 299 |
if (PatRole[P] == Head && WordRole[W] == Tail) |
| 300 |
--S; |
| 301 |
// Penalty: matching the first pattern character in the middle of a segment. |
| 302 |
if (P == 0 && WordRole[W] == Tail) |
| 303 |
S -= 4; |
| 304 |
assert(S <= PerfectBonus); |
| 305 |
return S; |
| 306 |
} |
| 307 |
|
| 308 |
llvm::SmallString<256> FuzzyMatcher::dumpLast(llvm::raw_ostream &OS) const { |
| 309 |
llvm::SmallString<256> Result; |
| 310 |
OS << "=== Match \"" << llvm::StringRef(Word, WordN) << "\" against [" |
| 311 |
<< llvm::StringRef(Pat, PatN) << "] ===\n"; |
| 312 |
if (PatN == 0) { |
| 313 |
OS << "Pattern is empty: perfect match.\n"; |
| 314 |
return Result = llvm::StringRef(Word, WordN); |
| 315 |
} |
| 316 |
if (WordN == 0) { |
| 317 |
OS << "Word is empty: no match.\n"; |
| 318 |
return Result; |
| 319 |
} |
| 320 |
if (!WordContainsPattern) { |
| 321 |
OS << "Substring check failed.\n"; |
| 322 |
return Result; |
| 323 |
} |
| 324 |
if (isAwful(std::max(Scores[PatN][WordN][Match].Score, |
| 325 |
Scores[PatN][WordN][Miss].Score))) { |
| 326 |
OS << "Substring check passed, but all matches are forbidden\n"; |
| 327 |
} |
| 328 |
if (!(PatTypeSet & 1 << Upper)) |
| 329 |
OS << "Lowercase query, so scoring ignores case\n"; |
| 330 |
|
| 331 |
// Traverse Matched table backwards to reconstruct the Pattern/Word mapping. |
| 332 |
// The Score table has cumulative scores, subtracting along this path gives |
| 333 |
// us the per-letter scores. |
| 334 |
Action Last = |
| 335 |
(Scores[PatN][WordN][Match].Score > Scores[PatN][WordN][Miss].Score) |
| 336 |
? Match |
| 337 |
: Miss; |
| 338 |
int S[MaxWord]; |
| 339 |
Action A[MaxWord]; |
| 340 |
for (int W = WordN - 1, P = PatN - 1; W >= 0; --W) { |
| 341 |
A[W] = Last; |
| 342 |
const auto &Cell = Scores[P + 1][W + 1][Last]; |
| 343 |
if (Last == Match) |
| 344 |
--P; |
| 345 |
const auto &Prev = Scores[P + 1][W][Cell.Prev]; |
| 346 |
S[W] = Cell.Score - Prev.Score; |
| 347 |
Last = Cell.Prev; |
| 348 |
} |
| 349 |
for (int I = 0; I < WordN; ++I) { |
| 350 |
if (A[I] == Match && (I == 0 || A[I - 1] == Miss)) |
| 351 |
Result.push_back('['); |
| 352 |
if (A[I] == Miss && I > 0 && A[I - 1] == Match) |
| 353 |
Result.push_back(']'); |
| 354 |
Result.push_back(Word[I]); |
| 355 |
} |
| 356 |
if (A[WordN - 1] == Match) |
| 357 |
Result.push_back(']'); |
| 358 |
|
| 359 |
for (char C : llvm::StringRef(Word, WordN)) |
| 360 |
OS << " " << C << " "; |
| 361 |
OS << "\n"; |
| 362 |
for (int I = 0, J = 0; I < WordN; I++) |
| 363 |
OS << " " << (A[I] == Match ? Pat[J++] : ' ') << " "; |
| 364 |
OS << "\n"; |
| 365 |
for (int I = 0; I < WordN; I++) |
| 366 |
OS << llvm::format("%2d ", S[I]); |
| 367 |
OS << "\n"; |
| 368 |
|
| 369 |
OS << "\nSegmentation:"; |
| 370 |
OS << "\n'" << llvm::StringRef(Word, WordN) << "'\n "; |
| 371 |
for (int I = 0; I < WordN; ++I) |
| 372 |
OS << "?-+ "[static_cast<int>(WordRole[I])]; |
| 373 |
OS << "\n[" << llvm::StringRef(Pat, PatN) << "]\n "; |
| 374 |
for (int I = 0; I < PatN; ++I) |
| 375 |
OS << "?-+ "[static_cast<int>(PatRole[I])]; |
| 376 |
OS << "\n"; |
| 377 |
|
| 378 |
OS << "\nScoring table (last-Miss, last-Match):\n"; |
| 379 |
OS << " | "; |
| 380 |
for (char C : llvm::StringRef(Word, WordN)) |
| 381 |
OS << " " << C << " "; |
| 382 |
OS << "\n"; |
| 383 |
OS << "-+----" << std::string(WordN * 4, '-') << "\n"; |
| 384 |
for (int I = 0; I <= PatN; ++I) { |
| 385 |
for (Action A : {Miss, Match}) { |
| 386 |
OS << ((I && A == Miss) ? Pat[I - 1] : ' ') << "|"; |
| 387 |
for (int J = 0; J <= WordN; ++J) { |
| 388 |
if (!isAwful(Scores[I][J][A].Score)) |
| 389 |
OS << llvm::format("%3d%c", Scores[I][J][A].Score, |
| 390 |
Scores[I][J][A].Prev == Match ? '*' : ' '); |
| 391 |
else |
| 392 |
OS << " "; |
| 393 |
} |
| 394 |
OS << "\n"; |
| 395 |
} |
| 396 |
} |
| 397 |
|
| 398 |
return Result; |
| 399 |
} |
| 400 |
|
| 401 |
} // namespace clangd |
| 402 |
} // namespace clang |