sammccall created this revision.
Herald added subscribers: cfe-commits, klimek.
The scoring function is fuzzy-match-quality * existing quality score.
Repository:
rCTE Clang Tools Extra
https://reviews.llvm.org/D40780
Files:
clangd/ClangdUnit.cpp
clangd/FuzzyMatch.h
clangd/Protocol.h
test/clangd/completion-fuzzy.test
Index: test/clangd/completion-fuzzy.test
===================================================================
--- /dev/null
+++ test/clangd/completion-fuzzy.test
@@ -0,0 +1,38 @@
+# 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"}
Index: clangd/Protocol.h
===================================================================
--- clangd/Protocol.h
+++ clangd/Protocol.h
@@ -438,6 +438,17 @@
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.
@@ -458,6 +469,9 @@
/// 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;
Index: clangd/FuzzyMatch.h
===================================================================
--- clangd/FuzzyMatch.h
+++ clangd/FuzzyMatch.h
@@ -35,6 +35,8 @@
// 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"
Index: clangd/ClangdUnit.cpp
===================================================================
--- clangd/ClangdUnit.cpp
+++ clangd/ClangdUnit.cpp
@@ -11,6 +11,7 @@
#include "Logger.h"
#include "Trace.h"
+#include "FuzzyMatch.h"
#include "clang/Frontend/CompilerInstance.h"
#include "clang/Frontend/CompilerInvocation.h"
#include "clang/Frontend/FrontendActions.h"
@@ -371,11 +372,14 @@
/// 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 {
@@ -396,6 +400,14 @@
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.
@@ -446,17 +458,18 @@
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;
@@ -479,37 +492,26 @@
CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
private:
- bool fuzzyMatch(Sema &S, const CodeCompletionContext &CCCtx, StringRef Filter,
- CodeCompletionResult Result) {
+ 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
@@ -523,6 +525,7 @@
Item.documentation = getDocumentation(CCS);
Item.sortText = Candidate.sortText();
+ Item.scoreInfo = Candidate.scores();
// Fill in the label, detail, insertText and filterText fields of the
// CompletionItem.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
