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,10 @@ tooling::CompileCommand getCompileCommand(PathRef File); + CachedFuzzyFindRequest + cachedFuzzyFindRequestForCompletion(PathRef File, llvm::StringRef Content, + Position Pos); + GlobalCompilationDatabase &CDB; DiagnosticsConsumer &DiagConsumer; FileSystemProvider &FSProvider; @@ -225,6 +231,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" @@ -29,6 +31,7 @@ #include "llvm/Support/Path.h" #include "llvm/Support/raw_ostream.h" #include +#include using namespace clang; using namespace clang::clangd; @@ -140,6 +143,34 @@ WorkScheduler.remove(File); } +// Creates a `CachedFuzzyFindRequest` based on the cached index request from the +// last completion, if any, and the speculated completion filter text in the +// source code. +CachedFuzzyFindRequest ClangdServer::cachedFuzzyFindRequestForCompletion( + PathRef File, StringRef Content, Position Pos) { + llvm::Optional CachedFuzzyReqCopy; + { + std::lock_guard Lock(CachedCompletionFuzzyFindRequestMutex); + CachedFuzzyReqCopy = CachedCompletionFuzzyFindRequestByFile[File]; + } + if (CachedFuzzyReqCopy) { + if (auto Filter = speculateCompletionFilter(Content, Pos)) { + CachedFuzzyReqCopy->Query = *Filter; + } else { + elog("Failed to speculate filter text for code completion at Pos " + "{0}:{1}: {2}", + Pos.line, Pos.character, Filter.takeError()); + CachedFuzzyReqCopy.reset(); + } + } + + return CachedFuzzyFindRequest( + CachedFuzzyReqCopy, [File, this](FuzzyFindRequest Req) { + std::lock_guard Lock(CachedCompletionFuzzyFindRequestMutex); + CachedCompletionFuzzyFindRequestByFile[File] = Req; + }); +} + void ClangdServer::codeComplete(PathRef File, Position Pos, const clangd::CodeCompleteOptions &Opts, Callback CB) { @@ -151,21 +182,31 @@ // 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 CachedIndexReq; + if (CodeCompleteOpts.Index && CodeCompleteOpts.SpeculativeIndexRequest) + CachedIndexReq = + cachedFuzzyFindRequestForCompletion(File, IP->Contents, Pos); + // 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, std::move(CachedIndexReq), + 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,8 @@ #include "clang/Sema/CodeCompleteConsumer.h" #include "clang/Sema/CodeCompleteOptions.h" #include "clang/Tooling/CompilationDatabase.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Error.h" namespace clang { class NamedDecl; @@ -72,6 +74,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. @@ -161,15 +173,19 @@ }; 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); +CodeCompleteResult +codeComplete(PathRef FileName, const tooling::CompileCommand &Command, + PrecompiledPreamble const *Preamble, + const IncludeStructure &PreambleInclusions, StringRef Contents, + Position Pos, IntrusiveRefCntPtr VFS, + std::shared_ptr PCHs, + llvm::Optional CachedIndexReq, + CodeCompleteOptions Opts); /// Get signature help at a specified \p Pos in \p FileName. SignatureHelp signatureHelp(PathRef FileName, Index: clangd/CodeComplete.cpp =================================================================== --- clangd/CodeComplete.cpp +++ clangd/CodeComplete.cpp @@ -42,6 +42,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" @@ -953,6 +955,21 @@ llvm_unreachable("invalid NestedNameSpecifier kind"); } +std::future asyncFuzzyFind(const SymbolIndex &Index, + const FuzzyFindRequest &Req) { + auto QueryIndex = [&Index, &Req](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. + return std::async(std::launch::async, QueryIndex, Context::current().clone()); +} + } // namespace clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const { @@ -1007,6 +1024,7 @@ class CodeCompleteFlow { PathRef FileName; IncludeStructure Includes; // Complete once the compiler runs. + llvm::Optional CachedIndexReq; const CodeCompleteOptions &Opts; // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup. CompletionRecorder *Recorder = nullptr; @@ -1019,15 +1037,26 @@ llvm::Optional Inserter; // Available during runWithSema. llvm::Optional FileProximity; // Initialized once Sema runs. + // Result from the async fuzzyFind request. Initialized *before* Sema runs, if + // applicable. + std::future SpeculativeFuzzyFindResult; + public: // A CodeCompleteFlow object is only useful for calling run() exactly once. CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes, + llvm::Optional CachedIndexReq, const CodeCompleteOptions &Opts) - : FileName(FileName), Includes(Includes), Opts(Opts) {} + : FileName(FileName), Includes(Includes), CachedIndexReq(CachedIndexReq), + Opts(Opts) {} CodeCompleteResult run(const SemaCompleteInput &SemaCCInput) && { trace::Span Tracer("CodeCompleteFlow"); + if (Opts.SpeculativeIndexRequest && Opts.Index && CachedIndexReq && + CachedIndexReq->getCachedReq()) + SpeculativeFuzzyFindResult = + asyncFuzzyFind(*Opts.Index, *CachedIndexReq->getCachedReq()); + // We run Sema code completion first. It builds an AST and calculates: // - completion results based on the AST. // - partial identifier and context. We need these for the index query. @@ -1081,6 +1110,7 @@ }); Recorder = RecorderOwner.get(); + semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(), SemaCCInput, &Includes); @@ -1134,6 +1164,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) { @@ -1150,7 +1182,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) @@ -1162,7 +1193,26 @@ Req.ProximityPaths.push_back(FileName); vlog("Code complete: fuzzyFind(\"{0}\", scopes=[{1}])", Req.Query, llvm::join(Req.Scopes.begin(), Req.Scopes.end(), ",")); + + llvm::Optional CachedReq; + if (CachedIndexReq) + CachedReq = CachedIndexReq->getCachedReq(); + if (CachedReq && (*CachedReq == Req) && + SpeculativeFuzzyFindResult.valid()) { + 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 SpeculativeFuzzyFindResult.get(); + } + + SPAN_ATTACH(Tracer, "Speculative results", false); + if (CachedIndexReq) + CachedIndexReq->setCachedRequest(Req); + // Run the query against the index. + SymbolSlab::Builder ResultsBuilder; if (Opts.Index->fuzzyFind( Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); })) Incomplete = true; @@ -1297,15 +1347,41 @@ } }; -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, + llvm::Optional CachedIndexReq, + CodeCompleteOptions Opts) { + return CodeCompleteFlow(FileName, PreambleInclusions, + std::move(CachedIndexReq), Opts) .run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs}); } Index: clangd/index/Index.h =================================================================== --- clangd/index/Index.h +++ clangd/index/Index.h @@ -18,7 +18,10 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/StringExtras.h" #include +#include +#include #include +#include namespace clang { namespace clangd { @@ -340,6 +343,13 @@ /// 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); + } }; struct LookupRequest { @@ -384,6 +394,27 @@ llvm::function_ref Callback) const = 0; }; +/// Maintains a cached fuzzy find request and provides an interface to update +/// the new fuzzy request in cache. +class CachedFuzzyFindRequest { +public: + /// \p UpdateCache An updater provided by the cache owner to update the new + /// request. + CachedFuzzyFindRequest(llvm::Optional CachedReq, + std::function UpdateCache) + : CachedReq(std::move(CachedReq)), UpdateCache(std::move(UpdateCache)) {} + + const llvm::Optional &getCachedReq() const { + return CachedReq; + } + + void setCachedRequest(FuzzyFindRequest Req) { UpdateCache(std::move(Req)); } + +private: + llvm::Optional CachedReq; + std::function UpdateCache; +}; + } // 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 { 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 @@ -1594,6 +1594,66 @@ ElementsAre(Sig("foo(T, U) -> void", {"T", "U"}))); } +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("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()); + + FS.Files[testPath("bar.h")] = + R"cpp(namespace ns { struct preamble { int member; }; })cpp"; + auto File = testPath("foo.cpp"); + Annotations Test(R"cpp( + #include "bar.h" + namespace ns1 { int local1; } + namespace ns2 { int local2; } + void f() { ns1::^; } + void f() { ns2::$2^; } + )cpp"); + runAddDocument(Server, File, Test.code()); + clangd::CodeCompleteOptions Opts = {}; + + auto I = memIndex({var("ns1::index1"), var("ns2::index2")}); + Opts.Index = I.get(); + Opts.SpeculativeIndexRequest = true; + + auto First = cantFail(runCodeComplete(Server, File, Test.point(), Opts)); + EXPECT_THAT(First.Completions, + UnorderedElementsAre(Named("local1"), Named("index1"))); + + auto Second = cantFail(runCodeComplete(Server, File, Test.point(), Opts)); + EXPECT_THAT(Second.Completions, + UnorderedElementsAre(Named("local1"), Named("index1"))); + + auto CacheMiss = + cantFail(runCodeComplete(Server, File, Test.point("2"), Opts)); + EXPECT_THAT(CacheMiss.Completions, + UnorderedElementsAre(Named("local2"), Named("index2"))); +} + } // namespace } // namespace clangd } // namespace clang