[clangd] Fix unintentionally loose fuzzy matching, and the tests masking it.

[sammccall]

Summary

The intent was that [ar] doesn't match "FooBar"; the first character must match
a Head character (hard requirement, not just a low score).
This matches VSCode, and was "tested" but the tests were defective.

The tests expected matches("FooBar") to fail for lack of a match. But instead
it fails because the string should be annotated - matches("FooB[ar]").
This patch makes matches("FooBar") ignore annotations, as was intended.

Fixing the code to reject weak matches for the first char causes problems:

• [bre] no longer matches "HTMLBRElement". We allow matching against an uppercase char even if we don't think it's head. Only do this if there's at least one lowercase, to avoid triggering on MACROS
• [print] no longer matches "sprintf". This is hard to fix without false positives (e.g. [int] vs "sprintf"]) This patch leaves this case broken. A future patch will add a dictionary providing custom segmentation to common names from the standard library.

Fixed a couple of index tests that indirectly relied on broken fuzzy matching.
Added const in a couple of missing places for consistency with new code.

[sammccall]

test tweaks

[ilya-biryukov]

LGTM, but note the unreachable code comment

unittests/clangd/FuzzyMatchTests.cpp

35

Maybe put operator before Word to keep fields grouped together?

37

This code is unreachable. Probably intended to remove return from the previous line?

clangd/FuzzyMatch.h

private:
   // Action should be an enum, but this causes bitfield problems:
   //   - for MSVC the enum type must be explicitly unsigned for correctness
   //   - GCC 4.8 complains not all values fit if the type is unsigned
   using Action = bool;
   constexpr static Action Miss = false, Match = true;
 
   bool init(llvm::StringRef Word);
   void buildGraph();
-  void calculateRoles(const char *Text, CharRole *Out, int N);
-  int skipPenalty(int W, Action Last);
-  int matchBonus(int P, int W, Action Last);
+  void calculateRoles(const char *Text, CharRole *Out, int &Types, int N);
+  bool allowMatch(int P, int W) const;
+  int skipPenalty(int W, Action Last) const;
+  int matchBonus(int P, int W, Action Last) const;
 
   // Pattern data is initialized by the constructor, then constant.
   char Pat[MaxPat];         // Pattern data
   int PatN;                 // Length
   char LowPat[MaxPat];      // Pattern in lowercase
   CharRole PatRole[MaxPat]; // Pattern segmentation info
-  bool CaseSensitive;       // Case-sensitive match if pattern has uppercase
+  int PatTypeSet;           // Bitmask of 1<<CharType
   float ScoreScale;         // Normalizes scores for the pattern length.
 
   // Word data is initialized on each call to match(), mostly by init().
   char Word[MaxWord];         // Word data
   int WordN;                  // Length
   char LowWord[MaxWord];      // Word in lowercase
   CharRole WordRole[MaxWord]; // Word segmentation info
+  int WordTypeSet;            // Bitmask of 1<<CharType
   bool WordContainsPattern;   // Simple substring check
 
   // Cumulative best-match score table.
   // Boundary conditions are filled in by the constructor.
   // The rest is repopulated for each match(), by buildGraph().
   struct ScoreInfo {
     signed int Score : 15;
     Action Prev : 1;
   };
   ScoreInfo Scores[MaxPat + 1][MaxWord + 1][/* Last Action */ 2];
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/FuzzyMatch.cpp

 //
 // We aim to find the best path from A->B.
 //  - Moving right (consuming a word character)
 //    Always legal: not all word characters must match.
 //  - Moving diagonally (consuming both a word and pattern character)
 //    Legal if the characters match.
 //  - Moving down (consuming a pattern character) is never legal.
 //    Never legal: all pattern characters must match something.
+// Characters are matched case-insensitively.
+// The first pattern character may only match the start of a word segment.
 //
 // The scoring is based on heuristics:
 //  - when matching a character, apply a bonus or penalty depending on the
 //    match quality (does case match, do word segments align, etc)
 //  - when skipping a character, apply a penalty if it hurts the match
 //    (it starts a word segment, or splits the matched region, etc)
 //
 // These heuristics require the ability to "look backward" one character, to

 // A "negative infinity" score that won't overflow.
 // We use this to mark unreachable states and forbidden solutions.
 // Score field is 15 bits wide, min value is -2^14, we use half of that.
 static constexpr int AwfulScore = -(1 << 13);
 static bool isAwful(int S) { return S < AwfulScore / 2; }
 static constexpr int PerfectBonus = 3; // Perfect per-pattern-char score.
 
 FuzzyMatcher::FuzzyMatcher(StringRef Pattern)
-    : PatN(std::min<int>(MaxPat, Pattern.size())), CaseSensitive(false),
+    : PatN(std::min<int>(MaxPat, Pattern.size())),
       ScoreScale(PatN ? float{1} / (PerfectBonus * PatN) : 0), WordN(0) {
   std::copy(Pattern.begin(), Pattern.begin() + PatN, Pat);
-  for (int I = 0; I < PatN; ++I) {
+  for (int I = 0; I < PatN; ++I)
     LowPat[I] = lower(Pat[I]);
-    CaseSensitive |= LowPat[I] != Pat[I];
-  }
   Scores[0][0][Miss] = {0, Miss};
   Scores[0][0][Match] = {AwfulScore, Miss};
   for (int P = 0; P <= PatN; ++P)
     for (int W = 0; W < P; ++W)
       for (Action A : {Miss, Match})
         Scores[P][W][A] = {AwfulScore, Miss};
   if (PatN > 0)
-    calculateRoles(Pat, PatRole, PatN);
+    calculateRoles(Pat, PatRole, PatTypeSet, PatN);
 }
 
 Optional<float> FuzzyMatcher::match(StringRef Word) {
   if (!(WordContainsPattern = init(Word)))
     return None;
   if (!PatN)
     return 1;
   buildGraph();
constexpr static uint8_t CharRoles[] = {
     /* Prev=Upper */ 0x00, 0x55, 0x59, 0xff, // Ditto, but U(U)U->Tail
     /* Prev=Separ */ 0x00, 0xaa, 0xaa, 0xff, // After separator, like at start
     // clang-format on
 };
 
 template <typename T> static T packedLookup(const uint8_t *Data, int I) {
   return static_cast<T>((Data[I >> 2] >> ((I & 3) * 2)) & 3);
 }
-void FuzzyMatcher::calculateRoles(const char *Text, CharRole *Out, int N) {
+void FuzzyMatcher::calculateRoles(const char *Text, CharRole *Out, int &TypeSet,
+                                  int N) {
   assert(N > 0);
+  CharType Type = packedLookup<CharType>(CharTypes, Text[0]);
+  TypeSet = 1 << Type;
   // Types holds a sliding window of (Prev, Curr, Next) types.
   // Initial value is (Empty, Empty, type of Text[0]).
-  int Types = packedLookup<CharType>(CharTypes, Text[0]);
+  int Types = Type;
   // Rotate slides in the type of the next character.
   auto Rotate = [&](CharType T) { Types = ((Types << 2) | T) & 0x3f; };
   for (int I = 0; I < N - 1; ++I) {
     // For each character, rotate in the next, and look up the role.
-    Rotate(packedLookup<CharType>(CharTypes, Text[I + 1]));
+    Type = packedLookup<CharType>(CharTypes, Text[I + 1]);
+    TypeSet |= 1 << Type;
+    Rotate(Type);
     *Out++ = packedLookup<CharRole>(CharRoles, Types);
   }
   // For the last character, the "next character" is Empty.
   Rotate(Empty);
   *Out++ = packedLookup<CharRole>(CharRoles, Types);
 }
 
 // Sets up the data structures matching Word.
bool FuzzyMatcher::init(StringRef NewWord) {
   // Cheap subsequence check.
   for (int W = 0, P = 0; P != PatN; ++W) {
     if (W == WordN)
       return false;
     if (LowWord[W] == LowPat[P])
       ++P;
   }
 
-  calculateRoles(Word, WordRole, WordN);
+  // FIXME: some words are hard to tokenize algorithmically.
+  // e.g. vsprintf is V S Print F, and should match [pri] but not [int].
+  // We could add a tokenization dictionary for common stdlib names.
+  calculateRoles(Word, WordRole, WordTypeSet, WordN);
   return true;
 }
 
 // The forwards pass finds the mappings of Pattern onto Word.
 // Score = best score achieved matching Word[..W] against Pat[..P].
 // Unlike other tables, indices range from 0 to N *inclusive*
 // Matched = whether we chose to match Word[W] with Pat[P] or not.
 //
for (int W = P; W < WordN; ++W) {
       if (P < PatN - 1) { // Skipping trailing characters is always free.
         MatchMissScore -= skipPenalty(W, Match);
         MissMissScore -= skipPenalty(W, Miss);
       }
       Score[Miss] = (MatchMissScore > MissMissScore)
                         ? ScoreInfo{MatchMissScore, Match}
                         : ScoreInfo{MissMissScore, Miss};
 
-      if (LowPat[P] != LowWord[W]) { // No match possible.
+      if (!allowMatch(P, W)) {
         Score[Match] = {AwfulScore, Miss};
       } else {
         auto &PreMatch = Scores[P][W];
         auto MatchMatchScore = PreMatch[Match].Score + matchBonus(P, W, Match);
         auto MissMatchScore = PreMatch[Miss].Score + matchBonus(P, W, Miss);
         Score[Match] = (MatchMatchScore > MissMatchScore)
                            ? ScoreInfo{MatchMatchScore, Match}
                            : ScoreInfo{MissMatchScore, Miss};
       }
     }
   }
 }
 
-int FuzzyMatcher::skipPenalty(int W, Action Last) {
+bool FuzzyMatcher::allowMatch(int P, int W) const {
+  if (LowPat[P] != LowWord[W])
+    return false;
+  // We require a "strong" match for the first pattern character only.
+  if (P > 0)
+    return true;
+  // Obvious "strong match" for first char: match against a word head.
+  // We're banning matches outright, so conservatively accept some other cases
+  // where our segmentation might be wrong:
+  //  - allow matching B in ABCDef (but not in NDEBUG)
+  //  - we'd like to accept print in sprintf, but too many false positives
+  return WordRole[W] != Tail ||
+         (Word[W] != LowWord[W] && WordTypeSet & 1 << Lower);
+}
+
+int FuzzyMatcher::skipPenalty(int W, Action Last) const {
   int S = 0;
   if (WordRole[W] == Head) // Skipping a segment.
     S += 1;
   if (Last == Match) // Non-consecutive match.
     S += 2;          // We'd rather skip a segment than split our match.
   return S;
 }
 
-int FuzzyMatcher::matchBonus(int P, int W, Action Last) {
+int FuzzyMatcher::matchBonus(int P, int W, Action Last) const {
   assert(LowPat[P] == LowWord[W]);
   int S = 1;
   // Bonus: pattern so far is a (case-insensitive) prefix of the word.
   if (P == W) // We can't skip pattern characters, so we must have matched all.
     ++S;
   // Bonus: case matches, or a Head in the pattern aligns with one in the word.
-  if ((Pat[P] == Word[W] && (CaseSensitive || P == W)) ||
+  if ((Pat[P] == Word[W] && ((PatTypeSet & 1 << Upper) || P == W)) ||
       (PatRole[P] == Head && WordRole[W] == Head))
     ++S;
   // Penalty: matching inside a segment (and previous char wasn't matched).
   if (WordRole[W] == Tail && P && Last == Miss)
     S -= 3;
   // Penalty: a Head in the pattern matches in the middle of a word segment.
   if (PatRole[P] == Head && WordRole[W] == Tail)
     --S;
llvm::SmallString<256> FuzzyMatcher::dumpLast(llvm::raw_ostream &OS) const {
   }
   if (!WordContainsPattern) {
     OS << "Substring check failed.\n";
     return Result;
   } else if (isAwful(std::max(Scores[PatN][WordN][Match].Score,
                               Scores[PatN][WordN][Miss].Score))) {
     OS << "Substring check passed, but all matches are forbidden\n";
   }
-  if (!CaseSensitive)
+  if (!(PatTypeSet & 1 << Upper))
     OS << "Lowercase query, so scoring ignores case\n";
 
   // Traverse Matched table backwards to reconstruct the Pattern/Word mapping.
   // The Score table has cumulative scores, subtracting along this path gives
   // us the per-letter scores.
   Action Last =
       (Scores[PatN][WordN][Match].Score > Scores[PatN][WordN][Miss].Score)
           ? Match

unittests/clangd/FuzzyMatchTests.cpp

 
 namespace clang {
 namespace clangd {
 namespace {
 using namespace llvm;
 using testing::Not;
 
 struct ExpectedMatch {
-  ExpectedMatch(StringRef Annotated) : Word(Annotated), Annotated(Annotated) {
+  // Annotations are optional, and will not be asserted if absent.
+  ExpectedMatch(StringRef Match) : Word(Match), Annotated(Match) {
     for (char C : "[]")
       Word.erase(std::remove(Word.begin(), Word.end(), C), Word.end());
+    if (Word.size() == Annotated->size())
+      Annotated = None;
+  }
+  bool accepts(StringRef ActualAnnotated) const {
+    return !Annotated || ActualAnnotated == *Annotated;
   }
   std::string Word;
-  StringRef Annotated;
-};
-raw_ostream &operator<<(raw_ostream &OS, const ExpectedMatch &M) {
-  return OS << "'" << M.Word << "' as " << M.Annotated;
+
+  friend raw_ostream &operator<<(raw_ostream &OS, const ExpectedMatch &M) {
+    return OS << "'" << M.Word;
+    if (M.Annotated)
+      OS << "' as " << *M.Annotated;
   }
 
+private:
+  Optional<StringRef> Annotated;
+};
+
 struct MatchesMatcher : public testing::MatcherInterface<StringRef> {
   ExpectedMatch Candidate;
   MatchesMatcher(ExpectedMatch Candidate) : Candidate(std::move(Candidate)) {}
 
   void DescribeTo(::std::ostream *OS) const override {
     raw_os_ostream(*OS) << "Matches " << Candidate;
   }
 
   bool MatchAndExplain(StringRef Pattern,
                        testing::MatchResultListener *L) const override {
     std::unique_ptr<raw_ostream> OS(
         L->stream() ? (raw_ostream *)(new raw_os_ostream(*L->stream()))
                     : new raw_null_ostream());
     FuzzyMatcher Matcher(Pattern);
     auto Result = Matcher.match(Candidate.Word);
     auto AnnotatedMatch = Matcher.dumpLast(*OS << "\n");
-    return Result && AnnotatedMatch == Candidate.Annotated;
+    return Result && Candidate.accepts(AnnotatedMatch);
   }
 };
 
 // Accepts patterns that match a given word.
 // Dumps the debug tables on match failure.
 testing::Matcher<StringRef> matches(StringRef M) {
   return testing::MakeMatcher<StringRef>(new MatchesMatcher(M));
 }
TEST(FuzzyMatch, Matches) {
   EXPECT_THAT("lowrd", matches("[low]Wo[rd]"));
   EXPECT_THAT("myvable", matches("[myva]ria[ble]"));
   EXPECT_THAT("no", Not(matches("")));
   EXPECT_THAT("no", Not(matches("match")));
   EXPECT_THAT("ob", Not(matches("foobar")));
   EXPECT_THAT("sl", matches("[S]Visual[L]oggerLogsList"));
   EXPECT_THAT("sllll", matches("[S]Visua[lL]ogger[L]ogs[L]ist"));
   EXPECT_THAT("Three", matches("H[T]ML[HRE]l[e]ment"));
+  EXPECT_THAT("b", Not(matches("NDEBUG")));
   EXPECT_THAT("Three", matches("[Three]"));
   EXPECT_THAT("fo", Not(matches("barfoo")));
   EXPECT_THAT("fo", matches("bar_[fo]o"));
   EXPECT_THAT("fo", matches("bar_[Fo]o"));
   EXPECT_THAT("fo", matches("bar [fo]o"));
   EXPECT_THAT("fo", matches("bar.[fo]o"));
   EXPECT_THAT("fo", matches("bar/[fo]o"));
   EXPECT_THAT("fo", matches("bar\\[fo]o"));
TEST(FuzzyMatch, Matches) {
   EXPECT_THAT("g g", Not(matches("  groupGroup")));
   EXPECT_THAT("g g", matches("  [g]roup[ G]roup"));
   EXPECT_THAT(" g g", matches("[ ] [g]roup[ G]roup"));
   EXPECT_THAT("zz", matches("[zz]Group"));
   EXPECT_THAT("zzg", matches("[zzG]roup"));
   EXPECT_THAT("g", matches("zz[G]roup"));
 
   EXPECT_THAT("aaaa", matches("_a_[aaaa]")); // Prefer consecutive.
-  EXPECT_THAT("printf", matches("s[printf]"));
-  EXPECT_THAT("str", matches("o[str]eam"));
+  // These would ideally match, but would need special segmentation rules.
+  EXPECT_THAT("printf", Not(matches("s[printf]")));
+  EXPECT_THAT("str", Not(matches("o[str]eam")));
 }
 
 struct RankMatcher : public testing::MatcherInterface<StringRef> {
   std::vector<ExpectedMatch> RankedStrings;
   RankMatcher(std::initializer_list<ExpectedMatch> RankedStrings)
       : RankedStrings(RankedStrings) {}
 
   void DescribeTo(::std::ostream *OS) const override {
for (const auto &Str : RankedStrings) {
         *OS << "\nDoesn't match '" << Str.Word << "'";
         Matcher.dumpLast(*OS << "\n");
         Ok = false;
       } else {
         std::string Buf;
         llvm::raw_string_ostream Info(Buf);
         auto AnnotatedMatch = Matcher.dumpLast(Info);
 
-        if (AnnotatedMatch != Str.Annotated) {
-          *OS << "\nMatched " << Str.Word << " as " << AnnotatedMatch
-              << " instead of " << Str.Annotated << "\n"
+        if (!Str.accepts(AnnotatedMatch)) {
+          *OS << "\nDoesn't match " << Str << ", but " << AnnotatedMatch << "\n"
               << Info.str();
           Ok = false;
         } else if (LastScore && *LastScore < *Score) {
           *OS << "\nRanks '" << Str.Word << "'=" << *Score << " above '"
               << LastMatch->Word << "'=" << *LastScore << "\n"
               << Info.str();
           Matcher.match(LastMatch->Word);
           Matcher.dumpLast(*OS << "\n");

unittests/clangd/IndexTests.cpp

TEST(MemIndexTest, MemIndexSymbolsRecycled) {
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("7"));
 
   EXPECT_FALSE(Symbols.expired());
   // Release old symbols.
   I.build(generateNumSymbols(0, 0));
   EXPECT_TRUE(Symbols.expired());
 }
 
-TEST(MemIndexTest, MemIndexMatchSubstring) {
-  MemIndex I;
-  I.build(generateNumSymbols(5, 25));
-  FuzzyFindRequest Req;
-  Req.Query = "5";
-  EXPECT_THAT(match(I, Req), UnorderedElementsAre("5", "15", "25"));
-}
-
 TEST(MemIndexTest, MemIndexDeduplicate) {
   auto Symbols = generateNumSymbols(0, 10);
 
   // Inject some duplicates and make sure we only match the same symbol once.
   auto Sym = symbol("7");
   Symbols->push_back(&Sym);
   Symbols->push_back(&Sym);
   Symbols->push_back(&Sym);
TEST(MemIndexTest, FuzzyMatch) {
   Req.Query = "lol";
   Req.MaxCandidateCount = 2;
   EXPECT_THAT(match(I, Req),
               UnorderedElementsAre("LaughingOutLoud", "LittleOldLady"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
   MemIndex I;
-  I.build(generateSymbols({"a::xyz", "b::yz", "yz"}));
+  I.build(generateSymbols({"a::y1", "b::y2", "y3"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "b::yz", "yz"));
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "b::y2", "y3"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
   MemIndex I;
-  I.build(generateSymbols({"a::xyz", "b::yz", "yz"}));
+  I.build(generateSymbols({"a::y1", "b::y2", "y3"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {""};
-  EXPECT_THAT(match(I, Req), UnorderedElementsAre("yz"));
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("y3"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
   MemIndex I;
-  I.build(generateSymbols({"a::xyz", "a::yy", "a::xz", "b::yz", "yz"}));
+  I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y2", "y3"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a"};
-  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy"));
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
   MemIndex I;
-  I.build(generateSymbols({"a::xyz", "a::yy", "a::xz", "b::yz", "yz"}));
+  I.build(generateSymbols({"a::y1", "a::y2", "a::x", "b::y3", "y3"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a", "b"};
-  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy", "b::yz"));
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1", "a::y2", "b::y3"));
 }
 
 TEST(MemIndexTest, NoMatchNestedScopes) {
   MemIndex I;
-  I.build(generateSymbols({"a::xyz", "a::b::yy"}));
+  I.build(generateSymbols({"a::y1", "a::b::y2"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
   Req.Scopes = {"a"};
-  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz"));
+  EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::y1"));
 }
 
 TEST(MemIndexTest, IgnoreCases) {
   MemIndex I;
   I.build(generateSymbols({"ns::ABC", "ns::abc"}));
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns"};