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