Author: sammccall Date: Fri Dec 1 08:35:50 2017 New Revision: 319552 URL: http://llvm.org/viewvc/llvm-project?rev=319552&view=rev Log: [clangd] Filter completion results by fuzzy-matching identifiers.
Summary: This allows us to limit the number of results we return and still allow them to be surfaced by refining a query (D39852). The initial algorithm is very conservative - it accepts a completion if the filter is any case-insensitive sub-sequence. It does not attempt to rank items based on match quality. Reviewers: ilya-biryukov Subscribers: cfe-commits Differential Revision: https://reviews.llvm.org/D39882 Modified: clang-tools-extra/trunk/clangd/ClangdUnit.cpp clang-tools-extra/trunk/test/clangd/completion-items-kinds.test clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp Modified: clang-tools-extra/trunk/clangd/ClangdUnit.cpp URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/ClangdUnit.cpp?rev=319552&r1=319551&r2=319552&view=diff ============================================================================== --- clang-tools-extra/trunk/clangd/ClangdUnit.cpp (original) +++ clang-tools-extra/trunk/clangd/ClangdUnit.cpp Fri Dec 1 08:35:50 2017 @@ -446,6 +446,7 @@ public: void ProcessCodeCompleteResults(Sema &S, CodeCompletionContext Context, CodeCompletionResult *Results, unsigned NumResults) override final { + StringRef Filter = S.getPreprocessor().getCodeCompletionFilter(); std::priority_queue<CompletionCandidate> Candidates; for (unsigned I = 0; I < NumResults; ++I) { auto &Result = Results[I]; @@ -453,6 +454,8 @@ public: (Result.Availability == CXAvailability_NotAvailable || Result.Availability == CXAvailability_NotAccessible)) continue; + if (!Filter.empty() && !fuzzyMatch(S, Context, Filter, Result)) + continue; Candidates.emplace(Result); if (ClangdOpts.Limit && Candidates.size() > ClangdOpts.Limit) { Candidates.pop(); @@ -476,6 +479,39 @@ public: CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; } private: + bool fuzzyMatch(Sema &S, const CodeCompletionContext &CCCtx, StringRef Filter, + CodeCompletionResult Result) { + switch (Result.Kind) { + case CodeCompletionResult::RK_Declaration: + if (auto *ID = Result.Declaration->getIdentifier()) + return fuzzyMatch(Filter, ID->getName()); + break; + case CodeCompletionResult::RK_Keyword: + return fuzzyMatch(Filter, Result.Keyword); + case CodeCompletionResult::RK_Macro: + return fuzzyMatch(Filter, Result.Macro->getName()); + case CodeCompletionResult::RK_Pattern: + return fuzzyMatch(Filter, 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; + } + CompletionItem ProcessCodeCompleteResult(const CompletionCandidate &Candidate, const CodeCompletionString &CCS) const { Modified: clang-tools-extra/trunk/test/clangd/completion-items-kinds.test URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/test/clangd/completion-items-kinds.test?rev=319552&r1=319551&r2=319552&view=diff ============================================================================== --- clang-tools-extra/trunk/test/clangd/completion-items-kinds.test (original) +++ clang-tools-extra/trunk/test/clangd/completion-items-kinds.test Fri Dec 1 08:35:50 2017 @@ -30,7 +30,7 @@ Content-Length: 148 # CHECK-SAME: ]}} Content-Length: 146 -{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"file:///main.cpp","languageId":"cpp","version":1,"text":"whi"}}} +{"jsonrpc":"2.0","method":"textDocument/didOpen","params":{"textDocument":{"uri":"file:///main.cpp","languageId":"cpp","version":1,"text":"nam"}}} Content-Length: 148 {"jsonrpc":"2.0","id":2,"method":"textDocument/completion","params":{"textDocument":{"uri":"file:///main.cpp"},"position":{"line":1,"character":3}}} Modified: clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp?rev=319552&r1=319551&r2=319552&view=diff ============================================================================== --- clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp (original) +++ clang-tools-extra/trunk/unittests/clangd/ClangdTests.cpp Fri Dec 1 08:35:50 2017 @@ -742,6 +742,61 @@ int main() { ClassWithMembers().{complet EXPECT_FALSE(ContainsItem(Results, "CCC")); } +TEST_F(ClangdCompletionTest, Filter) { + MockFSProvider FS; + MockCompilationDatabase CDB(/*AddFreestandingFlag=*/true); + CDB.ExtraClangFlags.push_back("-xc++"); + ErrorCheckingDiagConsumer DiagConsumer; + clangd::CodeCompleteOptions Opts; + ClangdServer Server(CDB, DiagConsumer, FS, getDefaultAsyncThreadsCount(), + /*StorePreamblesInMemory=*/true, Opts, + EmptyLogger::getInstance()); + + auto FooCpp = getVirtualTestFilePath("foo.cpp"); + FS.Files[FooCpp] = ""; + FS.ExpectedFile = FooCpp; + const char *Body = R"cpp( + int Abracadabra; + int Alakazam; + struct S { + int FooBar; + int FooBaz; + int Qux; + }; + )cpp"; + auto Complete = [&](StringRef Query) { + StringWithPos Completion = parseTextMarker( + formatv("{0} int main() { {1}{{complete}} }", Body, Query).str(), + "complete"); + Server.addDocument(FooCpp, Completion.Text); + return Server + .codeComplete(FooCpp, Completion.MarkerPos, StringRef(Completion.Text)) + .get() + .Value; + }; + + auto Foba = Complete("S().Foba"); + EXPECT_TRUE(ContainsItem(Foba, "FooBar")); + EXPECT_TRUE(ContainsItem(Foba, "FooBaz")); + EXPECT_FALSE(ContainsItem(Foba, "Qux")); + + auto FR = Complete("S().FR"); + EXPECT_TRUE(ContainsItem(FR, "FooBar")); + EXPECT_FALSE(ContainsItem(FR, "FooBaz")); + EXPECT_FALSE(ContainsItem(FR, "Qux")); + + auto Op = Complete("S().opr"); + EXPECT_TRUE(ContainsItem(Op, "operator=")); + + auto Aaa = Complete("aaa"); + EXPECT_TRUE(ContainsItem(Aaa, "Abracadabra")); + EXPECT_TRUE(ContainsItem(Aaa, "Alakazam")); + + auto UA = Complete("_a"); + EXPECT_TRUE(ContainsItem(UA, "static_cast")); + EXPECT_FALSE(ContainsItem(UA, "Abracadabra")); +} + TEST_F(ClangdCompletionTest, CompletionOptions) { MockFSProvider FS; ErrorCheckingDiagConsumer DiagConsumer; _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
