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,7 +458,7 @@ 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 Candidates; for (unsigned I = 0; I < NumResults; ++I) { auto &Result = Results[I]; @@ -454,9 +466,10 @@ (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 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. Index: clangd/FuzzyMatch.h =================================================================== --- clangd/FuzzyMatch.h +++ clangd/FuzzyMatch.h @@ -35,6 +35,8 @@ // Characters beyond MaxWord are ignored. llvm::Optional 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/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 scoreInfo; + /// A string that should be used when filtering a set of completion items. /// When `falsy` the label is used. std::string filterText; 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"}