Index: clang-tools-extra/trunk/clangd/CodeComplete.cpp =================================================================== --- clang-tools-extra/trunk/clangd/CodeComplete.cpp +++ clang-tools-extra/trunk/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: clang-tools-extra/trunk/clangd/FuzzyMatch.h =================================================================== --- clang-tools-extra/trunk/clangd/FuzzyMatch.h +++ clang-tools-extra/trunk/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: clang-tools-extra/trunk/clangd/Protocol.h =================================================================== --- clang-tools-extra/trunk/clangd/Protocol.h +++ clang-tools-extra/trunk/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: clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp +++ clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp @@ -380,6 +380,30 @@ 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; @@ -599,22 +623,6 @@ 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