ioeric created this revision.
ioeric added reviewers: hokein, ilya-biryukov.
Herald added subscribers: cfe-commits, kadircet, arphaman, jkorous, MaskRay.
For index-based code completion, 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.
Repository:
rCTE Clang Tools Extra
https://reviews.llvm.org/D50962
Files:
clangd/ClangdServer.cpp
clangd/ClangdServer.h
clangd/CodeComplete.cpp
clangd/CodeComplete.h
clangd/index/Index.cpp
clangd/index/Index.h
clangd/tool/ClangdMain.cpp
unittests/clangd/CodeCompleteTests.cpp
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
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<bool> 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<Path> 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: 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 <array>
+#include <functional>
+#include <future>
#include <string>
+#include <tuple>
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<std::string> 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<void(const SymbolOccurrence &)> 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<FuzzyFindRequest> CachedReq,
+ std::function<void(FuzzyFindRequest Req)> UpdateCache)
+ : CachedReq(std::move(CachedReq)), UpdateCache(std::move(UpdateCache)) {}
+
+ const llvm::Optional<FuzzyFindRequest> &getCachedReq() const {
+ return CachedReq;
+ }
+
+ void setCachedRequest(FuzzyFindRequest Req) { UpdateCache(std::move(Req)); }
+
+private:
+ llvm::Optional<FuzzyFindRequest> CachedReq;
+ std::function<void(FuzzyFindRequest Req)> 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 <future>
namespace clang {
namespace clangd {
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<llvm::StringRef>
+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::FileSystem> VFS,
- std::shared_ptr<PCHContainerOperations> PCHs,
- CodeCompleteOptions Opts);
+CodeCompleteResult
+codeComplete(PathRef FileName, const tooling::CompileCommand &Command,
+ PrecompiledPreamble const *Preamble,
+ const IncludeStructure &PreambleInclusions, StringRef Contents,
+ Position Pos, IntrusiveRefCntPtr<vfs::FileSystem> VFS,
+ std::shared_ptr<PCHContainerOperations> PCHs,
+ llvm::Optional<CachedFuzzyFindRequest> 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<SymbolSlab> 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<CachedFuzzyFindRequest> CachedIndexReq;
const CodeCompleteOptions &Opts;
// Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
CompletionRecorder *Recorder = nullptr;
@@ -1019,15 +1037,26 @@
llvm::Optional<IncludeInserter> Inserter; // Available during runWithSema.
llvm::Optional<URIDistance> FileProximity; // Initialized once Sema runs.
+ // Result from the async fuzzyFind request. Initialized *before* Sema runs, if
+ // applicable.
+ std::future<SymbolSlab> SpeculativeFuzzyFindResult;
+
public:
// A CodeCompleteFlow object is only useful for calling run() exactly once.
CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes,
+ llvm::Optional<CachedFuzzyFindRequest> 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<FuzzyFindRequest> 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::FileSystem> VFS,
- std::shared_ptr<PCHContainerOperations> PCHs,
- CodeCompleteOptions Opts) {
- return CodeCompleteFlow(FileName, PreambleInclusions, Opts)
+llvm::Expected<llvm::StringRef>
+speculateCompletionFilter(llvm::StringRef Content, Position Pos) {
+ auto Offset = positionToOffset(Content, Pos);
+ if (!Offset)
+ return llvm::make_error<llvm::StringError>(
+ "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::FileSystem> VFS,
+ std::shared_ptr<PCHContainerOperations> PCHs,
+ llvm::Optional<CachedFuzzyFindRequest> CachedIndexReq,
+ CodeCompleteOptions Opts) {
+ return CodeCompleteFlow(FileName, PreambleInclusions,
+ std::move(CachedIndexReq), Opts)
.run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs});
}
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<FileIndex> FileIdx;
// If present, a merged view of FileIdx and an external index. Read via Index.
std::unique_ptr<SymbolIndex> MergedIndex;
+
+ // GUARDED_BY(CachedCompletionFuzzyFindRequestMutex)
+ llvm::StringMap<llvm::Optional<FuzzyFindRequest>>
+ CachedCompletionFuzzyFindRequestByFile;
+ mutable std::mutex CachedCompletionFuzzyFindRequestMutex;
+
// If set, this represents the workspace path.
llvm::Optional<std::string> RootPath;
std::shared_ptr<PCHContainerOperations> 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 <future>
+#include <mutex>
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<FuzzyFindRequest> CachedFuzzyReqCopy;
+ {
+ std::lock_guard<std::mutex> 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<std::mutex> Lock(CachedCompletionFuzzyFindRequestMutex);
+ CachedCompletionFuzzyFindRequestByFile[File] = Req;
+ });
+}
+
void ClangdServer::codeComplete(PathRef File, Position Pos,
const clangd::CodeCompleteOptions &Opts,
Callback<CodeCompleteResult> CB) {
@@ -151,21 +182,31 @@
// Copy PCHs to avoid accessing this->PCHs concurrently
std::shared_ptr<PCHContainerOperations> PCHs = this->PCHs;
auto FS = FSProvider.getFileSystem();
- auto Task = [PCHs, Pos, FS,
- CodeCompleteOpts](Path File, Callback<CodeCompleteResult> CB,
- llvm::Expected<InputsAndPreamble> IP) {
+
+ auto Task = [PCHs, Pos, FS, CodeCompleteOpts,
+ this](Path File, Callback<CodeCompleteResult> CB,
+ llvm::Expected<InputsAndPreamble> IP) {
if (!IP)
return CB(IP.takeError());
auto PreambleData = IP->Preamble;
+ llvm::Optional<CachedFuzzyFindRequest> 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,
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
