[clangd] Incorporate fuzzy-match into result rankings.

[sammccall]

Summary

The scoring function is fuzzy-match-quality * existing quality score.

[ioeric]

clangd/ClangdUnit.cpp

377 ↗

(On Diff #125311)

It might worth mentioning how well FilterScore * SymbolScore performs. I think it could be affected by the distribution of the filtering score and symbol scores. We might want to do some tweaks on the numbers depending on the distributions...

380 ↗

(On Diff #125311)

Any reason not to use CompletionItemScores here? Maybe copy over some comments?

[sammccall]

Tested in this file:

#include <memory>
#include <unordered_map>
#include <vector>
int main() { std::^ }

Before this change:

u -> __has_argument_type, __has_first_argument_type...
un -> __has_argument_type, __has_first_argument_type...
u_p -> __has_argument_type, __has_first_argument_type...
um -> uintmax_t, unordered_map, unordered_multimap...

After this change

u -> u16streampos, u16string, u32streampos...
un -> unary_function, unary_negate, uncaught_exception...
u_p -> unique_ptr, undeclare_no_pointers, __has_argument_type...
um -> unordered_map, unordered_multimap, __has_argument_type...

clangd/ClangdUnit.cpp

377 ↗

(On Diff #125311)

Described this sensitivity.

380 ↗

(On Diff #125311)

Done. My feeling was that CompletionItemScores was an API and we shouldn't couple our internal layout to it. But it's convenient now and may remain so, we can change it later.

[sammccall]

Rebase, and address comments.

[hokein]

LGTM.

test/clangd/completion-fuzzy.test

1 ↗

(On Diff #129622)

nit: any reason not using unittest CodeCompleteTests here?

[sammccall]

Unit test instead of lit test.

test/clangd/completion-fuzzy.test

1 ↗

(On Diff #129622)

Whoops, none at all! Done.
When I first wrote this, CodeCompletionTests didn't exist in a useful form.

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

 // Signature help works in a similar way as code completion, but it is simpler
 // as there are typically fewer candidates.
 //
 //===---------------------------------------------------------------------===//
 
 #include "CodeComplete.h"
 #include "CodeCompletionStrings.h"
 #include "Compiler.h"
+#include "FuzzyMatch.h"
 #include "Logger.h"
 #include "index/Index.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
 #include "llvm/Support/Format.h"
 #include <queue>
default:
       break;
     }
   }
   return Result;
 }
 
 /// A scored code completion result.
 /// It may be promoted to a CompletionItem if it's among the top-ranked results.
+///
+/// We score candidates by multiplying the symbolScore ("quality" of the result)
+/// with the filterScore (how well it matched the query).
+/// This is sensitive to the distribution of both component scores!
 struct CompletionCandidate {
-  CompletionCandidate(CodeCompletionResult &Result)
-      : Result(&Result), Score(score(Result)) {}
+  CompletionCandidate(CodeCompletionResult &Result, float FilterScore)
+      : Result(&Result) {
+    Scores.symbolScore = score(Result);  // Higher is better.
+    Scores.filterScore = FilterScore;    // 0-1, higher is better.
+    Scores.finalScore = Scores.symbolScore * Scores.filterScore;
+  }
 
   CodeCompletionResult *Result;
-  float Score; // 0 to 1, higher is better.
+  CompletionItemScores Scores;
 
   // Comparison reflects rank: better candidates are smaller.
   bool operator<(const CompletionCandidate &C) const {
-    if (Score != C.Score)
-      return Score > C.Score;
+    if (Scores.finalScore != C.Scores.finalScore)
+      return Scores.finalScore > C.Scores.finalScore;
     return *Result < *C.Result;
   }
 
   // Returns a string that sorts in the same order as operator<, for LSP.
   // Conceptually, this is [-Score, Name]. We convert -Score to an integer, and
   // hex-encode it for readability. Example: [0.5, "foo"] -> "41000000foo"
   std::string sortText() const {
     std::string S, NameStorage;
     llvm::raw_string_ostream OS(S);
-    write_hex(OS, encodeFloat(-Score), llvm::HexPrintStyle::Lower,
-              /*Width=*/2 * sizeof(Score));
+    write_hex(OS, encodeFloat(-Scores.finalScore), llvm::HexPrintStyle::Lower,
+              /*Width=*/2 * sizeof(Scores.finalScore));
     OS << Result->getOrderedName(NameStorage);
     return OS.str();
   }
 
 private:
   static float score(const CodeCompletionResult &Result) {
     // Priority 80 is a really bad score.
     float Score = 1 - std::min<float>(80, Result.Priority) / 80;
CompletionItemsCollector(const CodeCompleteOptions &CodeCompleteOpts,
         ClangdOpts(CodeCompleteOpts), Items(Items),
         Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
         CCTUInfo(Allocator), CompletedName(CompletedName),
         EnableSnippets(CodeCompleteOpts.EnableSnippets) {}
 
   void ProcessCodeCompleteResults(Sema &S, CodeCompletionContext Context,
                                   CodeCompletionResult *Results,
                                   unsigned NumResults) override final {
+    FuzzyMatcher Filter(S.getPreprocessor().getCodeCompletionFilter());
     if (auto SS = Context.getCXXScopeSpecifier())
       CompletedName.SSInfo = extraCompletionScope(S, **SS);
 
     CompletedName.Filter = S.getPreprocessor().getCodeCompletionFilter();
     std::priority_queue<CompletionCandidate> Candidates;
     for (unsigned I = 0; I < NumResults; ++I) {
       auto &Result = Results[I];
       // We drop hidden items, as they cannot be found by the lookup after
       // inserting the corresponding completion item and only produce noise and
       // duplicates in the completion list. However, there is one exception. If
       // Result has a Qualifier which is non-informative, we can refer to an
       // item by adding that qualifier, so we don't filter out this item.
       if (Result.Hidden && (!Result.Qualifier || Result.QualifierIsInformative))
         continue;
       if (!ClangdOpts.IncludeIneligibleResults &&
           (Result.Availability == CXAvailability_NotAvailable ||
            Result.Availability == CXAvailability_NotAccessible))
         continue;
-      if (!CompletedName.Filter.empty() &&
-          !fuzzyMatch(S, Context, CompletedName.Filter, Result))
+      auto FilterScore = fuzzyMatch(S, Context, Filter, Result);
+      if (!FilterScore)
         continue;
-      Candidates.emplace(Result);
+      Candidates.emplace(Result, *FilterScore);
       if (ClangdOpts.Limit && Candidates.size() > ClangdOpts.Limit) {
         Candidates.pop();
         Items.isIncomplete = true;
       }
     }
     while (!Candidates.empty()) {
       auto &Candidate = Candidates.top();
       const auto *CCS = Candidate.Result->CreateCodeCompletionString(
           S, Context, *Allocator, CCTUInfo,
           CodeCompleteOpts.IncludeBriefComments);
       assert(CCS && "Expected the CodeCompletionString to be non-null");
       Items.items.push_back(ProcessCodeCompleteResult(Candidate, *CCS));
       Candidates.pop();
     }
     std::reverse(Items.items.begin(), Items.items.end());
   }
 
   GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
 
   CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
 
 private:
-  bool fuzzyMatch(Sema &S, const CodeCompletionContext &CCCtx, StringRef Filter,
+  llvm::Optional<float> fuzzyMatch(Sema &S, const CodeCompletionContext &CCCtx,
+                                   FuzzyMatcher &Filter,
                                    CodeCompletionResult Result) {
     switch (Result.Kind) {
     case CodeCompletionResult::RK_Declaration:
       if (auto *ID = Result.Declaration->getIdentifier())
-        return fuzzyMatch(Filter, ID->getName());
+        return Filter.match(ID->getName());
       break;
     case CodeCompletionResult::RK_Keyword:
-      return fuzzyMatch(Filter, Result.Keyword);
+      return Filter.match(Result.Keyword);
     case CodeCompletionResult::RK_Macro:
-      return fuzzyMatch(Filter, Result.Macro->getName());
+      return Filter.match(Result.Macro->getName());
     case CodeCompletionResult::RK_Pattern:
-      return fuzzyMatch(Filter, Result.Pattern->getTypedText());
+      return Filter.match(Result.Pattern->getTypedText());
     }
     auto *CCS = Result.CreateCodeCompletionString(
         S, CCCtx, *Allocator, CCTUInfo, /*IncludeBriefComments=*/false);
-    return fuzzyMatch(Filter, CCS->getTypedText());
-  }
-
-  // Checks whether Target matches the Filter.
-  // Currently just requires a case-insensitive subsequence match.
-  // FIXME: make stricter and word-based: 'unique_ptr' should not match 'que'.
-  // FIXME: return a score to be incorporated into ranking.
-  static bool fuzzyMatch(StringRef Filter, StringRef Target) {
-    size_t TPos = 0;
-    for (char C : Filter) {
-      TPos = Target.find_lower(C, TPos);
-      if (TPos == StringRef::npos)
-        return false;
-    }
-    return true;
+    return Filter.match(CCS->getTypedText());
   }
 
   CompletionItem
   ProcessCodeCompleteResult(const CompletionCandidate &Candidate,
                             const CodeCompletionString &CCS) const {
 
     // Adjust this to InsertTextFormat::Snippet iff we encounter a
     // CK_Placeholder chunk in SnippetCompletionItemsCollector.
     CompletionItem Item;
 
     Item.documentation = getDocumentation(CCS);
     Item.sortText = Candidate.sortText();
+    Item.scoreInfo = Candidate.Scores;
 
     Item.detail = getDetail(CCS);
     Item.filterText = getFilterText(CCS);
     getLabelAndInsertText(CCS, &Item.label, &Item.insertText, EnableSnippets);
 
     Item.insertTextFormat = EnableSnippets ? InsertTextFormat::Snippet
                                            : InsertTextFormat::PlainText;
 

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

 public:
   // Characters beyond MaxPat are ignored.
   FuzzyMatcher(llvm::StringRef Pattern);
 
   // If Word matches the pattern, return a score in [0,1] (higher is better).
   // Characters beyond MaxWord are ignored.
   llvm::Optional<float> match(llvm::StringRef Word);
 
+  bool empty() { return PatN == 0; }
+
   // Dump internal state from the last match() to the stream, for debugging.
   // Returns the pattern with [] around matched characters, e.g.
   //   [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;

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

enum class InsertTextFormat {
   /// of the snippet. Placeholders with equal identifiers are linked, that is
   /// typing in one will update others too.
   ///
   /// See also:
   /// https//github.com/Microsoft/vscode/blob/master/src/vs/editor/contrib/snippet/common/snippet.md
   Snippet = 2,
 };
 
+/// Provides details for how a completion item was scored.
+/// This can be used for client-side filtering of completion items as the
+/// user keeps typing.
+/// This is a clangd extension.
+struct CompletionItemScores {
+  float finalScore;  /// The score that items are ranked by.
+                     /// This is filterScore * symbolScore.
+  float filterScore; /// How the partial identifier matched filterText. [0-1]
+  float symbolScore; /// How the symbol fits, ignoring the partial identifier.
+};
+
 struct CompletionItem {
   /// The label of this completion item. By default also the text that is
   /// inserted when selecting this completion.
   std::string label;
 
   /// The kind of this completion item. Based of the kind an icon is chosen by
   /// the editor.
   CompletionItemKind kind = CompletionItemKind::Missing;
 
   /// A human-readable string with additional information about this item, like
   /// type or symbol information.
   std::string detail;
 
   /// A human-readable string that represents a doc-comment.
   std::string documentation;
 
   /// A string that should be used when comparing this item with other items.
   /// When `falsy` the label is used.
   std::string sortText;
 
+  /// Details about the quality of this completion item. (clangd extension)
+  llvm::Optional<CompletionItemScores> scoreInfo;
+
   /// A string that should be used when filtering a set of completion items.
   /// When `falsy` the label is used.
   std::string filterText;
 
   /// A string that should be inserted to a document when selecting this
   /// completion. When `falsy` the label is used.
   std::string insertText;
 

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

TEST(CompletionTest, Kinds) {
 
   clangd::CodeCompleteOptions Opts;
   Opts.EnableSnippets = true; // Needed for code patterns.
 
   Results = completions("nam^");
   EXPECT_THAT(Results.items, Has("namespace", CompletionItemKind::Snippet));
 }
 
+TEST(CompletionTest, NoDuplicates) {
+  auto Items = completions(R"cpp(
+struct Adapter {
+  void method();
+};
+
+void Adapter::method() {
+  Adapter^
+}
+  )cpp")
+                   .items;
+
+  // Make sure there are no duplicate entries of 'Adapter'.
+  EXPECT_THAT(Items, ElementsAre(Named("Adapter"), Named("~Adapter")));
+}
+
+TEST(CompletionTest, FuzzyRanking) {
+  auto Items = completions(R"cpp(
+      struct fake { int BigBang, Babble, Ball; };
+      int main() { fake().bb^ }")cpp").items;
+  // BigBang is a better match than Babble. Ball doesn't match at all.
+  EXPECT_THAT(Items, ElementsAre(Named("BigBang"), Named("Babble")));
+}
+
 SignatureHelp signatures(StringRef Text) {
   MockFSProvider FS;
   MockCompilationDatabase CDB;
   IgnoreDiagnostics DiagConsumer;
   ClangdServer Server(CDB, DiagConsumer, FS, getDefaultAsyncThreadsCount(),
                       /*StorePreamblesInMemory=*/true);
   auto File = getVirtualTestFilePath("foo.cpp");
   Annotations Test(Text);
TEST(CompletionTest, ASTIndexMultiFile) {
   EXPECT_THAT(Results.items, Has("XYZ", CompletionItemKind::Class));
   EXPECT_THAT(Results.items, Has("foo", CompletionItemKind::Function));
   EXPECT_THAT(Results.items, Has("XXX", CompletionItemKind::Class));
   EXPECT_THAT(Results.items, Contains(AllOf(Named("fooooo"), Filter("fooooo"),
                                             Kind(CompletionItemKind::Function),
                                             Doc("Doooc"), Detail("void"))));
 }
 
-TEST(CompletionTest, NoDuplicates) {
-  auto Items = completions(R"cpp(
-struct Adapter {
-  void method();
-};
-
-void Adapter::method() {
-  Adapter^
-}
-  )cpp")
-                   .items;
-
-  // Make sure there are no duplicate entries of 'Adapter'.
-  EXPECT_THAT(Items, ElementsAre(Named("Adapter"), Named("~Adapter")));
-}
-
 } // namespace
 } // namespace clangd
 } // namespace clang