[clangd] Incorporate fuzzy-match into result rankings.

[sammccall]

Summary

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

[ioeric]

clangd/ClangdUnit.cpp

377

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

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

Described this sensitivity.

380

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

2

nit: any reason not using unittest CodeCompleteTests here?

[sammccall]

Unit test instead of lit test.

test/clangd/completion-fuzzy.test

2

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

clangd/ClangdUnit.cpp

 //===--- ClangdUnit.cpp -----------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 
 #include "ClangdUnit.h"
 
 #include "Logger.h"
 #include "Trace.h"
+#include "FuzzyMatch.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Frontend/Utils.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/MacroInfo.h"
if (CCS.getBriefComment() != nullptr) {
     Result += CCS.getBriefComment();
   }
   return Result;
 }
 
 /// A scored code completion result.
 /// It may be promoted to a CompletionItem if it's among the top-ranked results.
 struct CompletionCandidate {
-  CompletionCandidate(CodeCompletionResult &Result)
-      : Result(&Result), Score(score(Result)) {}
+  CompletionCandidate(CodeCompletionResult &Result, float FilterScore)
+      : Result(&Result), SymbolScore(score(Result)), FilterScore(FilterScore),
+        Score(FilterScore * SymbolScore) {}
 
   CodeCompletionResult *Result;
-  float Score; // 0 to 1, higher is better.
+  float SymbolScore; // higher is better
+  float FilterScore; // 0 to 1, higher is better.
+  float Score;       // higher is better
 
   // Comparison reflects rank: better candidates are smaller.
   bool operator<(const CompletionCandidate &C) const {
     if (Score != C.Score)
       return Score > C.Score;
     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));
     OS << Result->getOrderedName(NameStorage);
     return OS.str();
   }
 
+  CompletionItemScores scores() const {
+    CompletionItemScores R;
+    R.finalScore = Score;
+    R.symbolScore = SymbolScore;
+    R.filterScore = FilterScore;
+    return R;
+  }
+
 private:
   static float score(const CodeCompletionResult &Result) {
     // Priority 80 is a really bad score.
     float Score = 1 - std::min<float>(80, Result.Priority) / 80;
 
     switch (static_cast<CXAvailabilityKind>(Result.Availability)) {
     case CXAvailability_Available:
       // No penalty.
CompletionItemsCollector(const clangd::CodeCompleteOptions &CodeCompleteOpts,
                              /*OutputIsBinary=*/false),
         ClangdOpts(CodeCompleteOpts), Items(Items),
         Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
         CCTUInfo(Allocator) {}
 
   void ProcessCodeCompleteResults(Sema &S, CodeCompletionContext Context,
                                   CodeCompletionResult *Results,
                                   unsigned NumResults) override final {
-    StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
+    FuzzyMatcher Filter(S.getPreprocessor().getCodeCompletionFilter());
     std::priority_queue<CompletionCandidate> Candidates;
     for (unsigned I = 0; I < NumResults; ++I) {
       auto &Result = Results[I];
       if (!ClangdOpts.IncludeIneligibleResults &&
           (Result.Availability == CXAvailability_NotAvailable ||
            Result.Availability == CXAvailability_NotAccessible))
         continue;
-      if (!Filter.empty() && !fuzzyMatch(S, Context, 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) {
+    if (Filter.empty())
+      return 1;
     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.insertTextFormat = InsertTextFormat::PlainText;
 
     Item.documentation = getDocumentation(CCS);
     Item.sortText = Candidate.sortText();
+    Item.scoreInfo = Candidate.scores();
 
     // Fill in the label, detail, insertText and filterText fields of the
     // CompletionItem.
     ProcessChunks(CCS, Item);
 
     // Fill in the kind field of the CompletionItem.
     Item.kind = getKind(Candidate.Result->Kind, Candidate.Result->CursorKind);
 

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;

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;
 

test/clangd/completion-fuzzy.test

+# RUN: clangd -pretty -run-synchronously < %s | FileCheck %s
+# It is absolutely vital that this file has CRLF line endings.
+#
+Content-Length: 125
+
+{"jsonrpc":"2.0","id":0,"method":"initialize","params":{"processId":123,"rootPath":"clangd","capabilities":{},"trace":"off"}}
+
+Content-Length: 224
+
+{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"file:///main.cpp","languageId":"cpp","version":1,"text":"struct fake { int BigBang, Babble, Ball; };\nint main() {\n  fake f;\n  f.bb\n}\n"}}}
+
+# Complete right after the dot (no identifier)
+Content-Length: 148
+
+{"jsonrpc":"2.0","id":1,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"position":{"line":3,"character":5}}}
+#      CHECK:  "id": 1
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:  "result": {
+#      CHECK:      "label": "Babble"
+#      CHECK:      "label": "Ball"
+#      CHECK:      "label": "BigBang"
+
+# Complete after .bb.
+# BigBang is a better match than Babble, Ball doesn't match at all.
+Content-Length: 148
+
+{"jsonrpc":"2.0","id":2,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"position":{"line":3,"character":6}}}
+#      CHECK:  "id": 2
+# CHECK-NEXT:  "jsonrpc": "2.0",
+# CHECK-NEXT:  "result": {
+#  CHECK-NOT:      "label": "Ball"
+#      CHECK:      "label": "BigBang"
+#  CHECK-NOT:      "label": "Ball"
+#      CHECK:      "label": "Babble"
+#  CHECK-NOT:      "label": "Ball"
+Content-Length: 44
+
+{"jsonrpc":"2.0","id":4,"method":"shutdown"}