[clangd] FuzzyMatch: forbid tail-tail matches after a miss: [pat] !~ "panther"

[sammccall]

Summary

This is a small code change but vastly reduces noise in code completion results.
The intent of allowing this was to let [sc] ~ "strncpy" and [strcpy] ~ "strncpy"
however the benefits for unsegmented names aren't IMO worth the costs.

Test cases should be representative of the changes here.

[sammccall]

Simplify logic/make more consistent. Couple of extra test cases.

[malaperle]

Very nice! I tried "std" and got much less (unimportant) results. I see something a bit weird with "getStandardResourceDir" but it might be VSCode. Here, I guess it's the "d" in Dir that matches but what's odd is that VS Code will highlight the first "d", i.e. in "standard". But it doesn't look like there is any way to control this in the LSP, is there?

[sammccall]

In D47950#1128370, @malaperle wrote:

Very nice! I tried "std" and got much less (unimportant) results. I see something a bit weird with "getStandardResourceDir" but it might be VSCode. Here, I guess it's the "d" in Dir that matches but what's odd is that VS Code will highlight the first "d", i.e. in "standard". But it doesn't look like there is any way to control this in the LSP, is there?

That's right. VSCode applies its fuzzymatch again client-side to determine which characters to highlight, and it chooses the wrong (IMO) "d" here. We wouldn't match [std] against "getStandardResourceZir".
(Worse, they use the same algorithm to rerank our results if client-side filtering applies...)

[malaperle]

In D47950#1128487, @sammccall wrote:

In D47950#1128370, @malaperle wrote:

Very nice! I tried "std" and got much less (unimportant) results. I see something a bit weird with "getStandardResourceDir" but it might be VSCode. Here, I guess it's the "d" in Dir that matches but what's odd is that VS Code will highlight the first "d", i.e. in "standard". But it doesn't look like there is any way to control this in the LSP, is there?

That's right. VSCode applies its fuzzymatch again client-side to determine which characters to highlight, and it chooses the wrong (IMO) "d" here. We wouldn't match [std] against "getStandardResourceZir".
(Worse, they use the same algorithm to rerank our results if client-side filtering applies...)

Thanks for the confirmation. In that case, I think the approach of this patch is quite good! Although it would be better is someone familiar with code completion could review the details :)

[sammccall]

Fix completion tests. (Simplify a bit - no need to re-test all the nuances of
fuzzy matching there).

[sammccall]

@ilya-biryukov ping. I'm excited about this change :-)

[ilya-biryukov]

LGTM with a few nits. And comment requests for things that were unclear when reading the code.

clangd/FuzzyMatch.cpp

269 ↗

(On Diff #151104)

NIT: maybe split into two declarations?

auto MatchMatchScore = ...;
auto MissMatchScore = ....;

clangd/FuzzyMatch.h

56 ↗

(On Diff #151104)

Maybe add a small doc comment for Action? Found myself figuring out what it is while reading this patch.

79 ↗

(On Diff #151104)

Maybe add a doc comment that this is the union of CharType of all chars in the word?
Seems obvious now, but was also a bit confusing when reading the code.

clang-tools-extra/trunk/clangd/FuzzyMatch.h

public:
   //   [u_p] + "unique_ptr" --> "[u]nique[_p]tr"
   llvm::SmallString<256> dumpLast(llvm::raw_ostream &) const;
 
 private:
   // We truncate the pattern and the word to bound the cost of matching.
   constexpr static int MaxPat = 63, MaxWord = 127;
   enum CharRole : unsigned char; // For segmentation.
   enum CharType : unsigned char; // For segmentation.
-  // Action should be an enum, but this causes bitfield problems:
+  // Action describes how a word character was matched to the pattern.
+  // It 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;
+  constexpr static Action Miss = false; // Word character was skipped.
+  constexpr static Action Match = true; // Matched against a pattern character.
 
   bool init(llvm::StringRef Word);
   void buildGraph();
   void calculateRoles(const char *Text, CharRole *Out, int &Types, int N);
-  bool allowMatch(int P, int W) const;
+  bool allowMatch(int P, int W, Action Last) 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
-  int PatTypeSet;           // Bitmask of 1<<CharType
+  int PatTypeSet;           // Bitmask of 1<<CharType for all Pattern characters
   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
+  int WordTypeSet;            // Bitmask of 1<<CharType for all Word characters
   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

clang-tools-extra/trunk/clangd/FuzzyMatch.cpp

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 (!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};
-      }
-    }
-  }
-}
+      auto MatchMatchScore =
+          allowMatch(P, W, Match)
+              ? PreMatch[Match].Score + matchBonus(P, W, Match)
+              : AwfulScore;
+      auto MissMatchScore = allowMatch(P, W, Miss)
+                                ? PreMatch[Miss].Score + matchBonus(P, W, Miss)
+                                : AwfulScore;
 
-bool FuzzyMatcher::allowMatch(int P, int W) const {
+bool FuzzyMatcher::allowMatch(int P, int W, Action Last) 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 require a "strong" match:
+  // - for the first pattern character.  [foo] !~ "barefoot"
+  // - after a gap.                      [pat] !~ "patnther"
+  if (Last == Miss) {
     // 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);
+    if (WordRole[W] == Tail &&
+        (Word[W] == LowWord[W] || !(WordTypeSet & 1 << Lower)))
+      return false;
+  }
+  return true;
 }
 
 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.

clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp

int main() { ClassWithMembers().^ }
                              /*IndexSymbols=*/{}, Opts);
 
   EXPECT_TRUE(Results.isIncomplete);
   EXPECT_THAT(Results.items, ElementsAre(Named("AAA"), Named("BBB")));
 }
 
 TEST(CompletionTest, Filter) {
   std::string Body = R"cpp(
-    #define FooBarMacro
-    int Abracadabra;
-    int Alakazam;
+    #define MotorCar
+    int Car;
     struct S {
       int FooBar;
       int FooBaz;
       int Qux;
     };
   )cpp";
-  EXPECT_THAT(completions(Body + "int main() { S().Foba^ }").items,
-              AllOf(Has("FooBar"), Has("FooBaz"), Not(Has("FooBarMacro")),
-                    Not(Has("Qux"))));
-
-  EXPECT_THAT(completions(Body + "int main() { S().FR^ }").items,
-              AllOf(Has("FooBar"), Not(Has("FooBaz")), Not(Has("Qux"))));
 
-  EXPECT_THAT(completions(Body + "int main() { aaa^ }").items,
-              AllOf(Has("Abracadabra"), Has("Alakazam")));
+  // Only items matching the fuzzy query are returned.
+  EXPECT_THAT(completions(Body + "int main() { S().Foba^ }").items,
+              AllOf(Has("FooBar"), Has("FooBaz"), Not(Has("Qux"))));
 
-  EXPECT_THAT(completions(Body + "int main() { _a^ }").items,
-              AllOf(Has("static_cast"), Not(Has("Abracadabra"))));
+  // Macros require  prefix match.
+  EXPECT_THAT(completions(Body + "int main() { C^ }").items,
+              AllOf(Has("Car"), Not(Has("MotorCar"))));
 }
 
 void TestAfterDotCompletion(clangd::CodeCompleteOptions Opts) {
   auto Results = completions(
       R"cpp(
       #define MACRO X
 
       int global_var;
TEST(CompletionTest, NoDuplicates) {
 
   // Make sure there are no duplicate entries of 'Adapter'.
   EXPECT_THAT(Results.items, ElementsAre(Named("Adapter")));
 }
 
 TEST(CompletionTest, ScopedNoIndex) {
   auto Results = completions(
       R"cpp(
-          namespace fake { int BigBang, Babble, Ball; };
-          int main() { fake::bb^ }
+          namespace fake { int BigBang, Babble, Box; };
+          int main() { fake::ba^ }
       ")cpp");
-  // BigBang is a better match than Babble. Ball doesn't match at all.
-  EXPECT_THAT(Results.items, ElementsAre(Named("BigBang"), Named("Babble")));
+  // Babble is a better match than BigBang. Box doesn't match at all.
+  EXPECT_THAT(Results.items, ElementsAre(Named("Babble"), Named("BigBang")));
 }
 
 TEST(CompletionTest, Scoped) {
   auto Results = completions(
       R"cpp(
-          namespace fake { int Babble, Ball; };
-          int main() { fake::bb^ }
+          namespace fake { int Babble, Box; };
+          int main() { fake::ba^ }
       ")cpp",
       {var("fake::BigBang")});
-  EXPECT_THAT(Results.items, ElementsAre(Named("BigBang"), Named("Babble")));
+  EXPECT_THAT(Results.items, ElementsAre(Named("Babble"), Named("BigBang")));
 }
 
 TEST(CompletionTest, ScopedWithFilter) {
   auto Results = completions(
       R"cpp(
           void f() { ns::x^ }
       )cpp",
       {cls("ns::XYZ"), func("ns::foo")});

clang-tools-extra/trunk/unittests/clangd/FuzzyMatchTests.cpp

 testing::Matcher<StringRef> matches(StringRef M, Optional<float> Score = {}) {
   return testing::MakeMatcher<StringRef>(new MatchesMatcher(M, Score));
 }
 
 TEST(FuzzyMatch, Matches) {
   EXPECT_THAT("", matches("unique_ptr"));
   EXPECT_THAT("u_p", matches("[u]nique[_p]tr"));
   EXPECT_THAT("up", matches("[u]nique_[p]tr"));
-  EXPECT_THAT("uq", matches("[u]ni[q]ue_ptr"));
+  EXPECT_THAT("uq", Not(matches("unique_ptr")));
   EXPECT_THAT("qp", Not(matches("unique_ptr")));
   EXPECT_THAT("log", Not(matches("SVGFEMorphologyElement")));
 
   EXPECT_THAT("tit", matches("win.[tit]"));
   EXPECT_THAT("title", matches("win.[title]"));
   EXPECT_THAT("WordCla", matches("[Word]Character[Cla]ssifier"));
   EXPECT_THAT("WordCCla", matches("[WordC]haracter[Cla]ssifier"));
 
   EXPECT_THAT("dete", Not(matches("editor.quickSuggestionsDelay")));
 
   EXPECT_THAT("highlight", matches("editorHover[Highlight]"));
   EXPECT_THAT("hhighlight", matches("editor[H]over[Highlight]"));
   EXPECT_THAT("dhhighlight", Not(matches("editorHoverHighlight")));
 
   EXPECT_THAT("-moz", matches("[-moz]-foo"));
   EXPECT_THAT("moz", matches("-[moz]-foo"));
   EXPECT_THAT("moza", matches("-[moz]-[a]nimation"));
 
   EXPECT_THAT("ab", matches("[ab]A"));
-  EXPECT_THAT("ccm", matches("[c]a[cm]elCase"));
+  EXPECT_THAT("ccm", Not(matches("cacmelCase")));
   EXPECT_THAT("bti", Not(matches("the_black_knight")));
   EXPECT_THAT("ccm", Not(matches("camelCase")));
   EXPECT_THAT("cmcm", Not(matches("camelCase")));
   EXPECT_THAT("BK", matches("the_[b]lack_[k]night"));
   EXPECT_THAT("KeyboardLayout=", Not(matches("KeyboardLayout")));
   EXPECT_THAT("LLL", matches("SVisual[L]ogger[L]ogs[L]ist"));
   EXPECT_THAT("LLLL", Not(matches("SVilLoLosLi")));
   EXPECT_THAT("LLLL", Not(matches("SVisualLoggerLogsList")));
   EXPECT_THAT("TEdit", matches("[T]ext[Edit]"));
   EXPECT_THAT("TEdit", matches("[T]ext[Edit]or"));
-  EXPECT_THAT("TEdit", matches("[Te]xte[dit]"));
+  EXPECT_THAT("TEdit", Not(matches("[T]ext[edit]")));
   EXPECT_THAT("TEdit", matches("[t]ext_[edit]"));
-  EXPECT_THAT("TEditDit", matches("[T]ext[Edit]or[D]ecorat[i]on[T]ype"));
+  EXPECT_THAT("TEditDt", matches("[T]ext[Edit]or[D]ecoration[T]ype"));
   EXPECT_THAT("TEdit", matches("[T]ext[Edit]orDecorationType"));
   EXPECT_THAT("Tedit", matches("[T]ext[Edit]"));
   EXPECT_THAT("ba", Not(matches("?AB?")));
   EXPECT_THAT("bkn", matches("the_[b]lack_[kn]ight"));
-  EXPECT_THAT("bt", matches("the_[b]lack_knigh[t]"));
-  EXPECT_THAT("ccm", matches("[c]amelCase[cm]"));
-  EXPECT_THAT("fdm", matches("[f]in[dM]odel"));
-  EXPECT_THAT("fob", matches("[fo]o[b]ar"));
+  EXPECT_THAT("bt", Not(matches("the_[b]lack_knigh[t]")));
+  EXPECT_THAT("ccm", Not(matches("[c]amelCase[cm]")));
+  EXPECT_THAT("fdm", Not(matches("[f]in[dM]odel")));
+  EXPECT_THAT("fob", Not(matches("[fo]o[b]ar")));
   EXPECT_THAT("fobz", Not(matches("foobar")));
   EXPECT_THAT("foobar", matches("[foobar]"));
   EXPECT_THAT("form", matches("editor.[form]atOnSave"));
   EXPECT_THAT("g p", matches("[G]it:[ P]ull"));
   EXPECT_THAT("g p", matches("[G]it:[ P]ull"));
   EXPECT_THAT("gip", matches("[Gi]t: [P]ull"));
   EXPECT_THAT("gip", matches("[Gi]t: [P]ull"));
   EXPECT_THAT("gp", matches("[G]it: [P]ull"));
   EXPECT_THAT("gp", matches("[G]it_Git_[P]ull"));
   EXPECT_THAT("is", matches("[I]mport[S]tatement"));
   EXPECT_THAT("is", matches("[is]Valid"));
-  EXPECT_THAT("lowrd", matches("[low]Wo[rd]"));
-  EXPECT_THAT("myvable", matches("[myva]ria[ble]"));
+  EXPECT_THAT("lowrd", Not(matches("[low]Wo[rd]")));
+  EXPECT_THAT("myvable", Not(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("sllll", matches("[S]Visua[L]ogger[Ll]ama[L]ist"));
+  EXPECT_THAT("THRE", matches("H[T]ML[HRE]lement"));
   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"));
TEST(FuzzyMatch, Matches) {
   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.
   // 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")));
+  EXPECT_THAT("strcpy", Not(matches("strncpy")));
+  EXPECT_THAT("std", Not(matches("PTHREAD_MUTEX_STALLED")));
+  EXPECT_THAT("std", Not(matches("pthread_condattr_setpshared")));
 }
 
 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 {

 // Accepts patterns that match all the strings and rank them in the given order.
 // Dumps the debug tables on match failure.
 template <typename... T> testing::Matcher<StringRef> ranks(T... RankedStrings) {
   return testing::MakeMatcher<StringRef>(
       new RankMatcher{ExpectedMatch(RankedStrings)...});
 }
 
 TEST(FuzzyMatch, Ranking) {
-  EXPECT_THAT("eb", ranks("[e]mplace_[b]ack", "[e]m[b]ed"));
   EXPECT_THAT("cons",
               ranks("[cons]ole", "[Cons]ole", "ArrayBuffer[Cons]tructor"));
   EXPECT_THAT("foo", ranks("[foo]", "[Foo]"));
-  EXPECT_THAT("onMess",
-              ranks("[onMess]age", "[onmess]age", "[on]This[M]ega[Es]cape[s]"));
+  EXPECT_THAT("onMes",
+              ranks("[onMes]sage", "[onmes]sage", "[on]This[M]ega[Es]capes"));
   EXPECT_THAT("CC", ranks("[C]amel[C]ase", "[c]amel[C]ase"));
   EXPECT_THAT("cC", ranks("[c]amel[C]ase", "[C]amel[C]ase"));
   EXPECT_THAT("p", ranks("[p]", "[p]arse", "[p]osix", "[p]afdsa", "[p]ath"));
   EXPECT_THAT("pa", ranks("[pa]rse", "[pa]th", "[pa]fdsa"));
   EXPECT_THAT("log", ranks("[log]", "Scroll[Log]icalPosition"));
   EXPECT_THAT("e", ranks("[e]lse", "Abstract[E]lement"));
   EXPECT_THAT("workbench.sideb",
               ranks("[workbench.sideB]ar.location",
                     "[workbench.]editor.default[SideB]ySideLayout"));
   EXPECT_THAT("editor.r", ranks("[editor.r]enderControlCharacter",
                                 "[editor.]overview[R]ulerlanes",
                                 "diff[Editor.r]enderSideBySide"));
   EXPECT_THAT("-mo", ranks("[-mo]z-columns", "[-]ms-ime-[mo]de"));
   EXPECT_THAT("convertModelPosition",
               ranks("[convertModelPosition]ToViewPosition",
                     "[convert]ViewTo[ModelPosition]"));
   EXPECT_THAT("is", ranks("[is]ValidViewletId", "[i]mport [s]tatement"));
-  EXPECT_THAT("title", ranks("window.[title]",
-                             "files.[t]r[i]m[T]rai[l]ingWhit[e]space"));
-  EXPECT_THAT("strcpy", ranks("[strcpy]", "[strcpy]_s", "[str]n[cpy]"));
-  EXPECT_THAT("close", ranks("workbench.quickOpen.[close]OnFocusOut",
-                             "[c]ss.[l]int.imp[o]rt[S]tat[e]ment",
-                             "[c]ss.co[lo]rDecorator[s].[e]nable"));
+  EXPECT_THAT("strcpy", ranks("[strcpy]", "[strcpy]_s"));
 }
 
 // Verify some bounds so we know scores fall in the right range.
 // Testing exact scores is fragile, so we prefer Ranking tests.
 TEST(FuzzyMatch, Scoring) {
-  EXPECT_THAT("abs", matches("[a]x[b]y[s]z", 0.f));
+  EXPECT_THAT("abs", matches("[a]w[B]xYz[S]", 0.f));
   EXPECT_THAT("abs", matches("[abs]l", 1.f));
   EXPECT_THAT("abs", matches("[abs]", 2.f));
   EXPECT_THAT("Abs", matches("[abs]", 2.f));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang