Index: clangd/ClangdServer.h =================================================================== --- clangd/ClangdServer.h +++ clangd/ClangdServer.h @@ -18,6 +18,7 @@ #include "Protocol.h" #include "TUScheduler.h" #include "index/FileIndex.h" +#include "index/Index.h" #include "clang/Tooling/CompilationDatabase.h" #include "clang/Tooling/Core/Replacement.h" #include "llvm/ADT/IntrusiveRefCntPtr.h" @@ -228,6 +229,12 @@ // If present, a merged view of DynamicIdx 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,6 +12,7 @@ #include "FindSymbols.h" #include "Headers.h" #include "SourceCode.h" +#include "Trace.h" #include "XRefs.h" #include "index/Merge.h" #include "clang/Format/Format.h" @@ -22,6 +23,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 +31,7 @@ #include "llvm/Support/Path.h" #include "llvm/Support/raw_ostream.h" #include +#include using namespace clang; using namespace clang::clangd; @@ -181,21 +184,44 @@ // 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; + llvm::Optional SpecFuzzyFind; + if (CodeCompleteOpts.Index && CodeCompleteOpts.SpeculativeIndexRequest) { + SpecFuzzyFind.emplace(); + { + std::lock_guard Lock(CachedCompletionFuzzyFindRequestMutex); + SpecFuzzyFind->CachedReq = CachedCompletionFuzzyFindRequestByFile[File]; + } + } + // 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, CodeCompleteOpts, + SpecFuzzyFind ? SpecFuzzyFind.getPointer() : nullptr); + { + clang::clangd::trace::Span Tracer("Completion results callback"); + CB(std::move(Result)); + } + if (SpecFuzzyFind && SpecFuzzyFind->NewReq.hasValue()) { + std::lock_guard Lock(CachedCompletionFuzzyFindRequestMutex); + CachedCompletionFuzzyFindRequestByFile[File] = + SpecFuzzyFind->NewReq.getValue(); + } + // SpecFuzzyFind is only destroyed after speculative fuzzy find finishes. + // We don't want `codeComplete` to wait for the async call if it doesn't use + // the result (e.g. non-index completion, speculation fails), so that `CB` + // is called as soon as results are available. }; WorkScheduler.runWithPreamble("CodeComplete", File, Index: clangd/CodeComplete.h =================================================================== --- clangd/CodeComplete.h +++ clangd/CodeComplete.h @@ -25,6 +25,10 @@ #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" +#include namespace clang { class NamedDecl; @@ -72,6 +76,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,7 +179,27 @@ }; raw_ostream &operator<<(raw_ostream &, const CodeCompleteResult &); +/// A speculative and asynchronous fuzzy find index request (based on cached +/// request) that can be sent before parsing sema. This would reduce completion +/// latency if the speculation succeeds. +struct SpeculativeFuzzyFind { + /// A cached request from past code completions. + /// Set by caller of `codeComplete()`. + llvm::Optional CachedReq; + /// The actual request used by `codeComplete()`. + /// Set by `codeComplete()`. This can be used by callers to update cache. + llvm::Optional NewReq; + /// The result is consumed by `codeComplete()` if speculation succeeded. + /// NOTE: the destructor will wait for the async call to finish. + std::future Result; +}; + /// Get code completions at a specified \p Pos in \p FileName. +/// If \p SpecFuzzyFind is set, a speculative and asynchronous fuzzy find index +/// request (based on cached request) will be run before parsing sema. In case +/// the speculative result is used by code completion (e.g. speculation failed), +/// the speculative result is not consumed, and `SpecFuzzyFind` is only +/// destroyed when the async request finishes. CodeCompleteResult codeComplete(PathRef FileName, const tooling::CompileCommand &Command, PrecompiledPreamble const *Preamble, @@ -173,7 +207,8 @@ StringRef Contents, Position Pos, IntrusiveRefCntPtr VFS, std::shared_ptr PCHs, - CodeCompleteOptions Opts); + CodeCompleteOptions Opts, + SpeculativeFuzzyFind *SpecFuzzyFind = nullptr); /// Get signature help at a specified \p Pos in \p FileName. SignatureHelp @@ -193,6 +228,12 @@ // like workspace/symbols or textDocument/definition, but are not used for code // completion. bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx); + +/// Retrives a speculative code completion filter text before the cursor. +/// Exposed for testing only. +llvm::Expected +speculateCompletionFilter(llvm::StringRef Content, Position Pos); + } // namespace clangd } // namespace clang Index: clangd/CodeComplete.cpp =================================================================== --- clangd/CodeComplete.cpp +++ clangd/CodeComplete.cpp @@ -29,6 +29,7 @@ #include "Logger.h" #include "Quality.h" #include "SourceCode.h" +#include "TUScheduler.h" #include "Trace.h" #include "URI.h" #include "index/Index.h" @@ -42,6 +43,8 @@ #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/ScopedPrinter.h" @@ -1077,6 +1080,32 @@ llvm_unreachable("invalid NestedNameSpecifier kind"); } +std::future startAsyncFuzzyFind(const SymbolIndex &Index, + const FuzzyFindRequest &Req) { + return runAsync([&Index, Req]() { + trace::Span Tracer("Async fuzzyFind"); + SymbolSlab::Builder Syms; + Index.fuzzyFind(Req, [&Syms](const Symbol &Sym) { Syms.insert(Sym); }); + return std::move(Syms).build(); + }); +} + +// 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 speculativeFuzzyFindRequestForCompletion( + FuzzyFindRequest CachedReq, PathRef File, StringRef Content, Position Pos) { + auto Filter = speculateCompletionFilter(Content, Pos); + if (!Filter) { + elog("Failed to speculate filter text for code completion at Pos " + "{0}:{1}: {2}", + Pos.line, Pos.character, Filter.takeError()); + return llvm::None; + } + CachedReq.Query = *Filter; + return CachedReq; +} + } // namespace clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const { @@ -1131,7 +1160,9 @@ class CodeCompleteFlow { PathRef FileName; IncludeStructure Includes; // Complete once the compiler runs. + SpeculativeFuzzyFind *SpecFuzzyFind; // 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. @@ -1142,15 +1173,29 @@ // This is available after Sema has run. llvm::Optional Inserter; // Available during runWithSema. llvm::Optional FileProximity; // Initialized once Sema runs. + /// Speculative request based on the cached request and the filter text before + /// the cursor. + /// Initialized right before sema run. This is only set if `SpecFuzzyFind` is + /// set and contains a cached request. + llvm::Optional SpecReq; public: // A CodeCompleteFlow object is only useful for calling run() exactly once. CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes, + SpeculativeFuzzyFind *SpecFuzzyFind, const CodeCompleteOptions &Opts) - : FileName(FileName), Includes(Includes), Opts(Opts) {} + : FileName(FileName), Includes(Includes), SpecFuzzyFind(SpecFuzzyFind), + Opts(Opts) {} CodeCompleteResult run(const SemaCompleteInput &SemaCCInput) && { trace::Span Tracer("CodeCompleteFlow"); + if (Opts.Index && SpecFuzzyFind && SpecFuzzyFind->CachedReq.hasValue()) { + assert(!SpecFuzzyFind->Result.valid()); + if ((SpecReq = speculativeFuzzyFindRequestForCompletion( + *SpecFuzzyFind->CachedReq, SemaCCInput.FileName, + SemaCCInput.Contents, SemaCCInput.Pos))) + SpecFuzzyFind->Result = startAsyncFuzzyFind(*Opts.Index, *SpecReq); + } // We run Sema code completion first. It builds an AST and calculates: // - completion results based on the AST. @@ -1205,6 +1250,7 @@ }); Recorder = RecorderOwner.get(); + semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(), SemaCCInput, &Includes); @@ -1256,6 +1302,7 @@ auto IndexResults = (Opts.Index && allowIndex(Recorder->CCContext)) ? queryIndex() : SymbolSlab(); + trace::Span Tracer("Populate CodeCompleteResult"); // Merge Sema, Index and Override results, score them, and pick the // winners. const auto Overrides = getNonOverridenMethodCompletionResults( @@ -1279,7 +1326,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) @@ -1291,7 +1337,22 @@ Req.ProximityPaths.push_back(FileName); vlog("Code complete: fuzzyFind(\"{0}\", scopes=[{1}])", Req.Query, llvm::join(Req.Scopes.begin(), Req.Scopes.end(), ",")); + + if (SpecFuzzyFind) + SpecFuzzyFind->NewReq = Req; + if (SpecFuzzyFind && SpecFuzzyFind->Result.valid() && (*SpecReq == 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 SpecFuzzyFind->Result.get(); + } + + SPAN_ATTACH(Tracer, "Speculative results", false); + // Run the query against the index. + SymbolSlab::Builder ResultsBuilder; if (Opts.Index->fuzzyFind( Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); })) Incomplete = true; @@ -1437,15 +1498,39 @@ } }; -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, + CodeCompleteOptions Opts, SpeculativeFuzzyFind *SpecFuzzyFind) { + return CodeCompleteFlow(FileName, PreambleInclusions, SpecFuzzyFind, Opts) .run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs}); } Index: clangd/TUScheduler.h =================================================================== --- clangd/TUScheduler.h +++ clangd/TUScheduler.h @@ -14,6 +14,7 @@ #include "Function.h" #include "Threading.h" #include "llvm/ADT/StringMap.h" +#include namespace clang { namespace clangd { @@ -167,6 +168,18 @@ std::chrono::steady_clock::duration UpdateDebounce; }; +/// Runs \p Action asynchronously with a new std::thread. The context will be +/// propogated. +template +std::future runAsync(llvm::unique_function Action) { + return std::async(std::launch::async, + [](llvm::unique_function &&Action, Context Ctx) { + WithContext WithCtx(std::move(Ctx)); + return Action(); + }, + std::move(Action), Context::current().clone()); +} + } // namespace clangd } // namespace clang Index: clangd/index/Index.h =================================================================== --- clangd/index/Index.h +++ clangd/index/Index.h @@ -20,6 +20,7 @@ #include "llvm/Support/StringSaver.h" #include #include +#include namespace clang { namespace clangd { @@ -343,6 +344,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 { Index: clangd/tool/ClangdMain.cpp =================================================================== --- clangd/tool/ClangdMain.cpp +++ clangd/tool/ClangdMain.cpp @@ -308,6 +308,7 @@ CCOpts.IncludeIndicator.Insert.clear(); CCOpts.IncludeIndicator.NoInsert.clear(); } + CCOpts.SpeculativeIndexRequest = Opts.StaticIndex; // Initialize and run ClangdLSPServer. ClangdLSPServer LSPServer( Index: unittests/clangd/CodeCompleteTests.cpp =================================================================== --- unittests/clangd/CodeCompleteTests.cpp +++ unittests/clangd/CodeCompleteTests.cpp @@ -927,7 +927,11 @@ // isn't used in production code. size_t estimateMemoryUsage() const override { return 0; } - const std::vector allRequests() const { return Requests; } + const std::vector consumeRequests() const { + auto Reqs = std::move(Requests); + Requests = {}; + return Reqs; + } private: mutable std::vector Requests; @@ -938,7 +942,7 @@ IndexRequestCollector Requests; Opts.Index = &Requests; completions(Code, {}, Opts); - return Requests.allRequests(); + return Requests.consumeRequests(); } TEST(CompletionTest, UnqualifiedIdQuery) { @@ -1709,6 +1713,75 @@ Not(Contains(Labeled("void vfunc(bool param) override"))))); } +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