[clangd] Boost fuzzy match score by 2x (so a maximum of 2) when the query is the full identifier name.

[sammccall]

Summary

Fix a couple of bugs in tests an in Quality to keep tests passing.

[sammccall]

More clearly explain scores >1.

[ioeric]

lg

[sammccall]

Explain WordN == PatN criterion for an exact match.

clangd/FuzzyMatch.h

 
 // A matcher capable of matching and scoring strings against a single pattern.
 // It's optimized for matching against many strings - match() does not allocate.
 class FuzzyMatcher {
 public:
   // Characters beyond MaxPat are ignored.
   FuzzyMatcher(llvm::StringRef Pattern);
 
-  // If Word matches the pattern, return a score in [0,1] (higher is better).
+  // If Word matches the pattern, return a score indicating the quality match.
+  // Scores usually fall in a [0,1] range, with 1 being a very good score.
+  // "Super" scores in (1,2] are possible if the pattern is the full word.
   // Characters beyond MaxWord are ignored.
   llvm::Optional<float> match(llvm::StringRef Word);
 
   llvm::StringRef pattern() const { return llvm::StringRef(Pat, PatN); }
   bool empty() const { return PatN == 0; }
 
   // Dump internal state from the last match() to the stream, for debugging.
   // Returns the pattern with [] around matched characters, e.g.

clangd/FuzzyMatch.cpp

if (!(WordContainsPattern = init(Word)))
     return None;
   if (!PatN)
     return 1;
   buildGraph();
   auto Best = std::max(Scores[PatN][WordN][Miss].Score,
                        Scores[PatN][WordN][Match].Score);
   if (isAwful(Best))
     return None;
-  return ScoreScale * std::min(PerfectBonus * PatN, std::max<int>(0, Best));
+  float Score =
+      ScoreScale * std::min(PerfectBonus * PatN, std::max<int>(0, Best));
+  // If the pattern is as long as the word, we have an exact string match,
+  // since every pattern character must match something.
+  if (WordN == PatN)
+    Score *= 2; // May not be perfect 2 if case differs in a significant way.
+  return Score;
 }
 
 // Segmentation of words and patterns.
 // A name like "fooBar_baz" consists of several parts foo, bar, baz.
 // Aligning segmentation of word and pattern improves the fuzzy-match.
 // For example: [lol] matches "LaughingOutLoud" better than "LionPopulation"
 //
 // First we classify each character into types (uppercase, lowercase, etc).

clangd/Quality.h

struct SymbolQualitySignals {
   // Condense these signals down to a single number, higher is better.
   float evaluate() const;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &,
                               const SymbolQualitySignals &);
 
 /// Attributes of a symbol-query pair that affect how much we like it.
 struct SymbolRelevanceSignals {
-  /// 0-1 fuzzy-match score for unqualified name. Must be explicitly assigned.
+  /// 0-1+ fuzzy-match score for unqualified name. Must be explicitly assigned.
   float NameMatch = 1;
   bool Forbidden = false; // Unavailable (e.g const) or inaccessible (private).
   /// Proximity between best declaration and the query. [0-1], 1 is closest.
   float ProximityScore = 0;
 
   // An approximate measure of where we expect the symbol to be used.
   enum AccessibleScope {
     FunctionScope,

clangd/Quality.cpp

float SymbolQualitySignals::evaluate() const {
 
   switch (Category) {
     case Type:
     case Function:
     case Variable:
       Score *= 1.1;
       break;
     case Namespace:
+      Score *= 0.8;
+      break;
     case Macro:
       Score *= 0.2;
       break;
     case Unknown:
       break;
   }
 
   return Score;

unittests/clangd/FindSymbolsTests.cpp

TEST_F(WorkspaceSymbolsTest, WithLimit) {
   addFile("foo.h", R"cpp(
       int foo;
       int foo2;
       )cpp");
   addFile("foo.cpp", R"cpp(
       #include "foo.h"
       )cpp");
   EXPECT_THAT(getSymbols("foo"),
-              ElementsAre(AllOf(Named("foo"), InContainer(""),
+              UnorderedElementsAre(AllOf(Named("foo"), InContainer(""),
                                          WithKind(SymbolKind::Variable)),
                                    AllOf(Named("foo2"), InContainer(""),
                                          WithKind(SymbolKind::Variable))));
 
   Limit = 1;
   EXPECT_THAT(getSymbols("foo"),
               ElementsAre(AnyOf((Named("foo"), InContainer("")),
                                 AllOf(Named("foo2"), InContainer("")))));
 }
 
 } // namespace clangd
 } // namespace clang

unittests/clangd/FuzzyMatchTests.cpp

struct ExpectedMatch {
   std::string Word;
 
 private:
   Optional<StringRef> Annotated;
 };
 
 struct MatchesMatcher : public testing::MatcherInterface<StringRef> {
   ExpectedMatch Candidate;
-  MatchesMatcher(ExpectedMatch Candidate) : Candidate(std::move(Candidate)) {}
+  Optional<float> Score;
+  MatchesMatcher(ExpectedMatch Candidate, Optional<float> Score)
+      : Candidate(std::move(Candidate)), Score(Score) {}
 
   void DescribeTo(::std::ostream *OS) const override {
     raw_os_ostream(*OS) << "Matches " << Candidate;
+    if (Score)
+      *OS << " with score " << *Score;
   }
 
   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 && Candidate.accepts(AnnotatedMatch);
+    return Result && Candidate.accepts(AnnotatedMatch) &&
+           (!Score || testing::Value(*Result, testing::FloatEq(*Score)));
   }
 };
 
-// Accepts patterns that match a given word.
+// Accepts patterns that match a given word, optionally requiring a score.
 // Dumps the debug tables on match failure.
-testing::Matcher<StringRef> matches(StringRef M) {
-  return testing::MakeMatcher<StringRef>(new MatchesMatcher(M));
+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("qp", Not(matches("unique_ptr")));
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("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]arse", "[p]osix", "[p]afdsa", "[p]ath", "[p]"));
+  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"));
 }
 
+// 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("[abs]l", 1.f));
+  EXPECT_THAT("abs", matches("[abs]", 2.f));
+  EXPECT_THAT("aBs", matches("[abs]", 2.f));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang