Index: clangd/CodeComplete.cpp =================================================================== --- clangd/CodeComplete.cpp +++ clangd/CodeComplete.cpp @@ -17,6 +17,7 @@ #include "CodeComplete.h" #include "CodeCompletionStrings.h" #include "Compiler.h" +#include "FuzzyMatch.h" #include "Logger.h" #include "index/Index.h" #include "clang/Frontend/CompilerInstance.h" @@ -186,17 +187,25 @@ /// 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; } @@ -206,8 +215,8 @@ 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(); } @@ -288,6 +297,7 @@ 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); @@ -306,10 +316,10 @@ (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; @@ -332,37 +342,24 @@ 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) { 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 @@ -375,6 +372,7 @@ Item.documentation = getDocumentation(CCS); Item.sortText = Candidate.sortText(); + Item.scoreInfo = Candidate.Scores; Item.detail = getDetail(CCS); Item.filterText = getFilterText(CCS); 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 @@ -446,6 +446,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. @@ -466,6 +477,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"}