[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

NIT: maybe split into two declarations?

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

clangd/FuzzyMatch.h

56

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

79

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.

clangd/FuzzyMatch.h

 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:
   //   - 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 &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
   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

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,
+           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;
+  // Don't allow the t in "Pat" to match "[Pa]n[t]her".
+  if (PatRole[P] == Tail && WordRole[W] == Tail && Last == Miss &&
+      Word[W] == LowWord[W] /* upper case "tail" is ambiguous */)
+    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

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", 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")));
 }
 
 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]x[B]yZ[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