Index: clangd/ClangdServer.h =================================================================== --- clangd/ClangdServer.h +++ clangd/ClangdServer.h @@ -18,6 +18,8 @@ #include "Protocol.h" #include "TUScheduler.h" #include "index/FileIndex.h" +#include "index/Index.h" +#include "clang/Basic/VirtualFileSystem.h" #include "clang/Tooling/CompilationDatabase.h" #include "clang/Tooling/Core/Replacement.h" #include "llvm/ADT/IntrusiveRefCntPtr.h" @@ -207,6 +209,9 @@ tooling::CompileCommand getCompileCommand(PathRef File); + llvm::Optional speculativeFuzzyFindRequestForCompletion( + PathRef File, llvm::StringRef Content, Position Pos); + GlobalCompilationDatabase &CDB; DiagnosticsConsumer &DiagConsumer; FileSystemProvider &FSProvider; @@ -225,6 +230,12 @@ std::unique_ptr FileIdx; // If present, a merged view of FileIdx and an external index. Read via Index. std::unique_ptr MergedIndex; + + // GUARDED_BY(CachedCompletionFuzzyFindRequestMutex) + llvm::StringMap> + CachedCompletionFuzzyFindRequestByFile; + mutable std::mutex CachedCompletionFuzzyFindRequestMutex; + // If set, this represents the workspace path. llvm::Optional RootPath; std::shared_ptr PCHs; Index: clangd/ClangdServer.cpp =================================================================== --- clangd/ClangdServer.cpp +++ clangd/ClangdServer.cpp @@ -12,7 +12,9 @@ #include "FindSymbols.h" #include "Headers.h" #include "SourceCode.h" +#include "Trace.h" #include "XRefs.h" +#include "index/Index.h" #include "index/Merge.h" #include "clang/Format/Format.h" #include "clang/Frontend/CompilerInstance.h" @@ -22,6 +24,7 @@ #include "clang/Tooling/Refactoring/RefactoringResultConsumer.h" #include "clang/Tooling/Refactoring/Rename/RenamingAction.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/Optional.h" #include "llvm/ADT/ScopeExit.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/Errc.h" @@ -29,6 +32,7 @@ #include "llvm/Support/Path.h" #include "llvm/Support/raw_ostream.h" #include +#include using namespace clang; using namespace clang::clangd; @@ -140,6 +144,32 @@ WorkScheduler.remove(File); } +// Creates a `FuzzyFindRequest` based on the cached index request from the +// last completion, if any, and the speculated completion filter text in the +// source code. +llvm::Optional +ClangdServer::speculativeFuzzyFindRequestForCompletion(PathRef File, + StringRef Content, + Position Pos) { + llvm::Optional SpecFuzzyReq; + { + std::lock_guard Lock(CachedCompletionFuzzyFindRequestMutex); + SpecFuzzyReq = CachedCompletionFuzzyFindRequestByFile[File]; + } + if (SpecFuzzyReq) { + if (auto Filter = speculateCompletionFilter(Content, Pos)) { + SpecFuzzyReq->Query = *Filter; + } else { + elog("Failed to speculate filter text for code completion at Pos " + "{0}:{1}: {2}", + Pos.line, Pos.character, Filter.takeError()); + SpecFuzzyReq.reset(); + } + } + + return SpecFuzzyReq; +} + void ClangdServer::codeComplete(PathRef File, Position Pos, const clangd::CodeCompleteOptions &Opts, Callback CB) { @@ -151,21 +181,47 @@ // Copy PCHs to avoid accessing this->PCHs concurrently std::shared_ptr PCHs = this->PCHs; auto FS = FSProvider.getFileSystem(); - auto Task = [PCHs, Pos, FS, - CodeCompleteOpts](Path File, Callback CB, - llvm::Expected IP) { + + auto Task = [PCHs, Pos, FS, CodeCompleteOpts, + this](Path File, Callback CB, + llvm::Expected IP) { if (!IP) return CB(IP.takeError()); auto PreambleData = IP->Preamble; + std::function UpdateFuzzyFindReq = + [File, this](FuzzyFindRequest Req) { + std::lock_guard Lock( + CachedCompletionFuzzyFindRequestMutex); + CachedCompletionFuzzyFindRequestByFile[File] = Req; + }; + llvm::Optional SpeculativeFuzzyFind; + if (CodeCompleteOpts.Index && CodeCompleteOpts.SpeculativeIndexRequest) { + // Start the speculative fuzzyFind here so that it can outlive + // `codeComplete`. If the speculative result is not used (speculation + // fails or index is not used), `codeComplete` can finish before the + // request finishes. As we want to invoke `CB` as early as possible, we + // avoid starting the async call inside `codeComplete` as it (the + // underlying std::future) can block `codeComplete`. + if (llvm::Optional SpecReq = + speculativeFuzzyFindRequestForCompletion(File, IP->Contents, Pos)) + SpeculativeFuzzyFind.emplace(*CodeCompleteOpts.Index, + std::move(*SpecReq)); + } + // FIXME(ibiryukov): even if Preamble is non-null, we may want to check // both the old and the new version in case only one of them matches. CodeCompleteResult Result = clangd::codeComplete( File, IP->Command, PreambleData ? &PreambleData->Preamble : nullptr, PreambleData ? PreambleData->Includes : IncludeStructure(), - IP->Contents, Pos, FS, PCHs, CodeCompleteOpts); - CB(std::move(Result)); + IP->Contents, Pos, FS, PCHs, UpdateFuzzyFindReq, + SpeculativeFuzzyFind ? SpeculativeFuzzyFind.getPointer() : nullptr, + CodeCompleteOpts); + { + clang::clangd::trace::Span Tracer("Completion results callback"); + CB(std::move(Result)); + } }; WorkScheduler.runWithPreamble("CodeComplete", File, Index: clangd/CodeComplete.h =================================================================== --- clangd/CodeComplete.h +++ clangd/CodeComplete.h @@ -25,6 +25,9 @@ #include "clang/Sema/CodeCompleteConsumer.h" #include "clang/Sema/CodeCompleteOptions.h" #include "clang/Tooling/CompilationDatabase.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Error.h" namespace clang { class NamedDecl; @@ -72,6 +75,16 @@ /// Expose origins of completion items in the label (for debugging). bool ShowOrigins = false; + /// If set to true, this will send an asynchronous speculative index request, + /// based on the index request for the last code completion on the same file + /// and the filter text typed before the cursor, before sema code completion + /// is invoked. This can reduce the code completion latency (by roughly + /// latency of sema code completion) if the speculative request is the same as + /// the one generated for the ongoing code completion from sema. As a sequence + /// of code completions often have the same scopes and proximity paths etc, + /// this should be effective for a number of code completions. + bool SpeculativeIndexRequest = false; + // Populated internally by clangd, do not set. /// If `Index` is set, it is used to augment the code completion /// results. @@ -165,15 +178,21 @@ }; raw_ostream &operator<<(raw_ostream &, const CodeCompleteResult &); +/// Retrives a speculative code completion filter text before the cursor. +llvm::Expected +speculateCompletionFilter(llvm::StringRef Content, Position Pos); + /// Get code completions at a specified \p Pos in \p FileName. -CodeCompleteResult codeComplete(PathRef FileName, - const tooling::CompileCommand &Command, - PrecompiledPreamble const *Preamble, - const IncludeStructure &PreambleInclusions, - StringRef Contents, Position Pos, - IntrusiveRefCntPtr VFS, - std::shared_ptr PCHs, - CodeCompleteOptions Opts); +/// \p SpeculativeFuzzyFind can be nullptr. If set, it maintains an ongoing +/// asychronous speculative fuzzy find for the code completion. +CodeCompleteResult +codeComplete(PathRef FileName, const tooling::CompileCommand &Command, + PrecompiledPreamble const *Preamble, + const IncludeStructure &PreambleInclusions, StringRef Contents, + Position Pos, IntrusiveRefCntPtr VFS, + std::shared_ptr PCHs, + std::function UpdateCachedFuzzyFindReq, + AsyncFuzzyFind *SpeculativeFuzzyFind, CodeCompleteOptions Opts); /// Get signature help at a specified \p Pos in \p FileName. SignatureHelp Index: clangd/CodeComplete.cpp =================================================================== --- clangd/CodeComplete.cpp +++ clangd/CodeComplete.cpp @@ -42,8 +42,11 @@ #include "clang/Sema/CodeCompleteConsumer.h" #include "clang/Sema/Sema.h" #include "clang/Tooling/Core/Replacement.h" +#include "llvm/ADT/Optional.h" +#include "llvm/Support/Error.h" #include "llvm/Support/Format.h" #include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/GenericDomTree.h" #include "llvm/Support/ScopedPrinter.h" #include @@ -1047,7 +1050,10 @@ class CodeCompleteFlow { PathRef FileName; IncludeStructure Includes; // Complete once the compiler runs. + std::function UpdateCachedFuzzyFindReq; + AsyncFuzzyFind *SpeculativeFuzzyFind; // Can be nullptr. const CodeCompleteOptions &Opts; + // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup. CompletionRecorder *Recorder = nullptr; int NSema = 0, NIndex = 0, NBoth = 0; // Counters for logging. @@ -1061,9 +1067,13 @@ public: // A CodeCompleteFlow object is only useful for calling run() exactly once. - CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes, - const CodeCompleteOptions &Opts) - : FileName(FileName), Includes(Includes), Opts(Opts) {} + CodeCompleteFlow( + PathRef FileName, const IncludeStructure &Includes, + std::function UpdateCachedFuzzyFindReq, + AsyncFuzzyFind *SpeculativeFuzzyFind, const CodeCompleteOptions &Opts) + : FileName(FileName), Includes(Includes), + UpdateCachedFuzzyFindReq(UpdateCachedFuzzyFindReq), + SpeculativeFuzzyFind(SpeculativeFuzzyFind), Opts(Opts) {} CodeCompleteResult run(const SemaCompleteInput &SemaCCInput) && { trace::Span Tracer("CodeCompleteFlow"); @@ -1121,6 +1131,7 @@ }); Recorder = RecorderOwner.get(); + semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(), SemaCCInput, &Includes); @@ -1174,6 +1185,8 @@ : SymbolSlab(); // Merge Sema and Index results, score them, and pick the winners. auto Top = mergeResults(Recorder->Results, IndexResults); + + trace::Span Tracer("Populate CodeCompleteResult"); // Convert the results to final form, assembling the expensive strings. CodeCompleteResult Output; for (auto &C : Top) { @@ -1190,7 +1203,6 @@ trace::Span Tracer("Query index"); SPAN_ATTACH(Tracer, "limit", int64_t(Opts.Limit)); - SymbolSlab::Builder ResultsBuilder; // Build the query. FuzzyFindRequest Req; if (Opts.Limit) @@ -1202,7 +1214,22 @@ Req.ProximityPaths.push_back(FileName); vlog("Code complete: fuzzyFind(\"{0}\", scopes=[{1}])", Req.Query, llvm::join(Req.Scopes.begin(), Req.Scopes.end(), ",")); + + if (SpeculativeFuzzyFind && (SpeculativeFuzzyFind->getRequest() == Req)) { + vlog("Code complete: speculative fuzzy request matches the actual index " + "request. Waiting for the speculative index results."); + SPAN_ATTACH(Tracer, "Speculative results", true); + + trace::Span WaitSpec("Wait speculative results"); + return SpeculativeFuzzyFind->getResult(); + } + + SPAN_ATTACH(Tracer, "Speculative results", false); + if (UpdateCachedFuzzyFindReq) + UpdateCachedFuzzyFindReq(Req); + // Run the query against the index. + SymbolSlab::Builder ResultsBuilder; if (Opts.Index->fuzzyFind( Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); })) Incomplete = true; @@ -1337,15 +1364,42 @@ } }; -CodeCompleteResult codeComplete(PathRef FileName, - const tooling::CompileCommand &Command, - PrecompiledPreamble const *Preamble, - const IncludeStructure &PreambleInclusions, - StringRef Contents, Position Pos, - IntrusiveRefCntPtr VFS, - std::shared_ptr PCHs, - CodeCompleteOptions Opts) { - return CodeCompleteFlow(FileName, PreambleInclusions, Opts) +llvm::Expected +speculateCompletionFilter(llvm::StringRef Content, Position Pos) { + auto Offset = positionToOffset(Content, Pos); + if (!Offset) + return llvm::make_error( + "Failed to convert position to offset in content.", + llvm::inconvertibleErrorCode()); + if (*Offset == 0) + return ""; + + // Start from the character before the cursor. + int St = *Offset - 1; + // FIXME(ioeric): consider UTF characters? + auto IsValidIdentifierChar = [](char c) { + return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || + (c >= '0' && c <= '9') || (c == '_')); + }; + size_t Len = 0; + for (; (St >= 0) && IsValidIdentifierChar(Content[St]); --St, ++Len) { + } + if (Len > 0) + St++; // Shift to the first valid character. + return Content.substr(St, Len); +} + +CodeCompleteResult +codeComplete(PathRef FileName, const tooling::CompileCommand &Command, + PrecompiledPreamble const *Preamble, + const IncludeStructure &PreambleInclusions, StringRef Contents, + Position Pos, IntrusiveRefCntPtr VFS, + std::shared_ptr PCHs, + std::function UpdateCachedFuzzyFindReq, + AsyncFuzzyFind *SpeculativeFuzzyFind, CodeCompleteOptions Opts) { + return CodeCompleteFlow(FileName, PreambleInclusions, + std::move(UpdateCachedFuzzyFindReq), + SpeculativeFuzzyFind, Opts) .run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs}); } Index: clangd/index/Index.h =================================================================== --- clangd/index/Index.h +++ clangd/index/Index.h @@ -19,7 +19,10 @@ #include "llvm/ADT/StringExtras.h" #include "llvm/Support/StringSaver.h" #include +#include +#include #include +#include namespace clang { namespace clangd { @@ -343,6 +346,14 @@ /// Contextually relevant files (e.g. the file we're code-completing in). /// Paths should be absolute. std::vector ProximityPaths; + + bool operator==(const FuzzyFindRequest &Req) const { + return std::tie(Query, Scopes, MaxCandidateCount, RestrictForCodeCompletion, + ProximityPaths) == + std::tie(Req.Query, Req.Scopes, Req.MaxCandidateCount, + Req.RestrictForCodeCompletion, Req.ProximityPaths); + } + bool operator!=(const FuzzyFindRequest &Req) const { return !(*this == Req); } }; struct LookupRequest { @@ -387,6 +398,28 @@ llvm::function_ref Callback) const = 0; }; +/// Maintains an asynchronous fuzzyFind index query. +/// The class will only be destroyed after the ongoing fuzzy find request, if +/// any, finishes. +class AsyncFuzzyFind { +public: + /// Starts an asynchronous fuzzy find query. + AsyncFuzzyFind(const SymbolIndex &Index, FuzzyFindRequest Req); + + const FuzzyFindRequest &getRequest() const { return Req; } + + // Returns true if the result of the async call can still be consumed. + bool valid() { return Result.valid(); } + + // Waits for the asynchronous call to finish and returns the result. + // REQUIRES: `valid() == true`. + SymbolSlab getResult(); + +private: + FuzzyFindRequest Req; + std::future Result; +}; + } // namespace clangd } // namespace clang Index: clangd/index/Index.cpp =================================================================== --- clangd/index/Index.cpp +++ clangd/index/Index.cpp @@ -8,9 +8,13 @@ //===----------------------------------------------------------------------===// #include "Index.h" +#include "../Context.h" +#include "../Logger.h" +#include "../Trace.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/SHA1.h" #include "llvm/Support/raw_ostream.h" +#include namespace clang { namespace clangd { @@ -128,5 +132,26 @@ return SymbolSlab(std::move(NewArena), std::move(Symbols)); } +AsyncFuzzyFind::AsyncFuzzyFind(const SymbolIndex &Index, + FuzzyFindRequest AsyncReq) + : Req(std::move(AsyncReq)) { + auto QueryIndex = [&Index, this](Context Ctx) { + WithContext WithCtx(std::move(Ctx)); + trace::Span Tracer("Async fuzzyFind"); + SymbolSlab::Builder Syms; + Index.fuzzyFind(Req, [&Syms](const Symbol &Sym) { Syms.insert(Sym); }); + return std::move(Syms).build(); + }; + // FIXME(ioeric): we might want to use threads in work scheduler. + Result = + std::async(std::launch::async, QueryIndex, Context::current().clone()); +} + +SymbolSlab AsyncFuzzyFind::getResult() { + assert(Result.valid()); + auto Slab = Result.get(); + return Slab; +} + } // namespace clangd } // namespace clang Index: clangd/tool/ClangdMain.cpp =================================================================== --- clangd/tool/ClangdMain.cpp +++ clangd/tool/ClangdMain.cpp @@ -164,6 +164,20 @@ "an include line will be inserted or not."), llvm::cl::init(true)); +static llvm::cl::opt SpeculateCompletionIndexRequest( + "speculative-completion-index-request", + llvm::cl::desc( + R"(If set to true and static index is enabled, this will send an + asynchronous speculative index request, based on the index request for + the last code completion on the same file and the filter text typed + before the cursor, before sema code completion is invoked. This can + reduce the code completion latency (by roughly latency of sema code + completion) if the speculative request is the same as the one generated + for the ongoing code completion from sema. As a sequence of code + completions often have the same scopes and proximity paths etc, this + should be effective for a number of code completions.)"), + llvm::cl::init(true)); + static llvm::cl::opt YamlSymbolFile( "yaml-symbol-file", llvm::cl::desc( @@ -299,6 +313,8 @@ CCOpts.IncludeIndicator.Insert.clear(); CCOpts.IncludeIndicator.NoInsert.clear(); } + CCOpts.SpeculativeIndexRequest = + SpeculateCompletionIndexRequest && Opts.StaticIndex; // Initialize and run ClangdLSPServer. ClangdLSPServer LSPServer( Index: unittests/clangd/CodeCompleteTests.cpp =================================================================== --- unittests/clangd/CodeCompleteTests.cpp +++ unittests/clangd/CodeCompleteTests.cpp @@ -923,7 +923,11 @@ llvm::function_ref Callback) const override {} - const std::vector allRequests() const { return Requests; } + const std::vector consumeRequests() const { + auto Reqs = std::move(Requests); + Requests.clear(); + return Reqs; + } private: mutable std::vector Requests; @@ -934,7 +938,7 @@ IndexRequestCollector Requests; Opts.Index = &Requests; completions(Code, {}, Opts); - return Requests.allRequests(); + return Requests.consumeRequests(); } TEST(CompletionTest, UnqualifiedIdQuery) { @@ -1700,6 +1704,75 @@ } } +TEST(SpeculateCompletionFilter, Filters) { + Annotations F(R"cpp($bof^ + $bol^ + ab$ab^ + x.ab$dot^ + x.$dotempty^ + x::ab$scoped^ + x::$scopedempty^ + + )cpp"); + auto speculate = [&](StringRef PointName) { + auto Filter = speculateCompletionFilter(F.code(), F.point(PointName)); + assert(Filter); + return *Filter; + }; + EXPECT_EQ(speculate("bof"), ""); + EXPECT_EQ(speculate("bol"), ""); + EXPECT_EQ(speculate("ab"), "ab"); + EXPECT_EQ(speculate("dot"), "ab"); + EXPECT_EQ(speculate("dotempty"), ""); + EXPECT_EQ(speculate("scoped"), "ab"); + EXPECT_EQ(speculate("scopedempty"), ""); +} + +TEST(CompletionTest, EnableSpeculativeIndexRequest) { + MockFSProvider FS; + MockCompilationDatabase CDB; + IgnoreDiagnostics DiagConsumer; + ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest()); + + auto File = testPath("foo.cpp"); + Annotations Test(R"cpp( + namespace ns1 { int abc; } + namespace ns2 { int abc; } + void f() { ns1::ab$1^; ns1::ab$2^; } + void f() { ns2::ab$3^; } + )cpp"); + runAddDocument(Server, File, Test.code()); + clangd::CodeCompleteOptions Opts = {}; + + IndexRequestCollector Requests; + Opts.Index = &Requests; + Opts.SpeculativeIndexRequest = true; + + auto CompleteAtPoint = [&](StringRef P) { + cantFail(runCodeComplete(Server, File, Test.point(P), Opts)); + // Sleep for a while to make sure asynchronous call (if applicable) is also + // triggered before callback is invoked. + std::this_thread::sleep_for(std::chrono::milliseconds(100)); + }; + + CompleteAtPoint("1"); + auto Reqs1 = Requests.consumeRequests(); + ASSERT_EQ(Reqs1.size(), 1u); + EXPECT_THAT(Reqs1[0].Scopes, UnorderedElementsAre("ns1::")); + + CompleteAtPoint("2"); + auto Reqs2 = Requests.consumeRequests(); + // Speculation succeeded. Used speculative index result. + ASSERT_EQ(Reqs2.size(), 1u); + EXPECT_EQ(Reqs2[0], Reqs1[0]); + + CompleteAtPoint("3"); + // Speculation failed. Sent speculative index request and the new index + // request after sema. + auto Reqs3 = Requests.consumeRequests(); + ASSERT_EQ(Reqs3.size(), 2u); +} + } // namespace } // namespace clangd } // namespace clang Index: unittests/clangd/IndexTests.cpp =================================================================== --- unittests/clangd/IndexTests.cpp +++ unittests/clangd/IndexTests.cpp @@ -321,6 +321,21 @@ EXPECT_EQ(M.Name, "right"); } +TEST(AsyncFuzzyFind, Simple) { + MemIndex Idx; + Idx.build(generateSymbols({"ns::abc", "ns::xyz"})); + + FuzzyFindRequest Req; + Req.Query = ""; + Req.Scopes = {"ns::"}; + + AsyncFuzzyFind Async(Idx, Req); + + EXPECT_EQ(Async.getRequest(), Req); + EXPECT_THAT(Async.getResult(), + UnorderedElementsAre(Named("abc"), Named("xyz"))); +} + } // namespace } // namespace clangd } // namespace clang