[clangd] Speculative code completion index request before Sema is run.

[ioeric]

Summary

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.

Trace with speculative index request:

[ioeric]

I just realized that CodeCompleteFlow would be blocked by the speculative index request even when index request is not needed (e.g. member access), because it owns the future object. This can make some completion requests slower. We may need to move the async index query into the ClangdServer::codeComplete so that completion callback can be invoked as soon as results are ready, without having to wait for speculative index results.

[ioeric]

• Make sure completion result callback can be called even if the unused speculative request has not finished.

[kadircet]

unittests/clangd/CodeCompleteTests.cpp

1710

Maybe an EXPECT for this one as well?

[ioeric]

• Improve tests.

unittests/clangd/CodeCompleteTests.cpp

1710

Nice catch!

[ioeric]

• minor cleanup.

[ilya-biryukov]

Really excited about this one, this should give us decent latency improvements when using the static index.
My main suggestion would be to put almost all of the speculating code into CodeComplete.cpp.

We could merely return the request that should be used for speculation to ClangdServer, that would in turn stash it in the map.
This should keep the code more localized in code completion and keep changes to other parts trivial. WDYT?

clangd/ClangdServer.cpp

159

NIT: maybe invert condition to reduce nesting?

160

Maybe move this logic into code completion, keeping only the storage for the old requests?
The code is domain-specific to code completion and we should aim to keep as little of domain logic in ClangdServer.

clangd/CodeComplete.cpp

1053

Maybe return the new callback from completion instead of passing a callback to update here?

1388

This looks incorrect in case of the identifiers starting at offset 0. A corner case, but still.

clangd/index/Index.cpp

147

I think we should just have a generic 'std::async'-like helper that does the same things, properly piping our context to the new threads.
Async requests to the index and other code potentially doing network requests are good candidates to use use it.

Maybe include it in this change? It shouldn't be more than a few lines, but would already make the code cleaner.

clangd/index/Index.h

404

Could this be an implementation detail of code completion if we move the spawning of the task into codeComplete function?

409

Can this be a simple struct with two fields std::future<SymbolSlab> and the original FuzzyFindRequest?
And having a function that fires the async request instead of doing that in constructor should be more straight-forward

clangd/tool/ClangdMain.cpp

179

Maybe remove this option?
Doing a speculative request seems like the right thing to do in all cases. It never hurts completion latency. Any reasons to avoid it?

unittests/clangd/CodeCompleteTests.cpp

926

Why do we want to change this? To avoid tests getting requests from the previous tests?

[ioeric]

• Moved most logic into CodeComplete.cc

[ioeric]

• minor cleanup

[ioeric]

• another minior cleanup

[ioeric]

clangd/ClangdServer.cpp

159

It would become something like:

if (!SpecFuzzyReq)
  return SpecFuzzyReq;
.... // some work
return SpecFuzzyReq;

Having to return the same thing twice seems a bit worse IMO.

clangd/CodeComplete.cpp

1388

Offset == 0 is handled above.

clangd/tool/ClangdMain.cpp

179

Sure, was trying to be conservative :)

Removed the command-line option but still keeping the code completion option. As async call has some overhead, I think we should only enable it when static index is provided.

unittests/clangd/CodeCompleteTests.cpp

926

Yes.

[ioeric]

• fix typos..

[ilya-biryukov]

clangd/ClangdServer.cpp

159

I think it's better. Besides, you could replace return llvm::None in the first statement (would be even more straightforward from my point of view).
There's a secion in LLVM Style Guide on this.

clangd/CodeComplete.cpp

1388

Didn't notice. LG, thanks

clangd/CodeComplete.h

185

Maybe a short comment describing on why we have this parameter?

195

NewReq is an implementation detail only needed in CodeComplete.cpp, right? Maybe remove from this struct and only set in .cpp file?

196

Maybe remove description of the value in the result?
We don't want anyone to use, so a simple comment that the future is only there to wait until the async calls complete should be enough.

197

SpecFuzzyFind is partially an out parameter, maybe put it at the end of the parameter list?

clangd/tool/ClangdMain.cpp

179

Enabling only when static index is there LG. OTOH, it should always take less than code completion in case there's no static index, so it would've probably been fine either way

unittests/clangd/CodeCompleteTests.cpp

928

Calling any methods on moved-from objects is a red flag.
It probably works on vectors, but maybe reassign Requests = {} or use a swap-with-empty-vector trick instead to avoid that?

[ioeric]

• Merge remote-tracking branch 'origin/master' into speculate-index
• address comments.

[ilya-biryukov]

clangd/CodeComplete.h

186

s/can be before/can be send
(or similar?)

[ilya-biryukov]

clangd/CodeComplete.h

186

or rather 'can be sent'

[ioeric]

• fix doc

[ioeric]

• moved SpecReq into CodeComplete.cpp

[ilya-biryukov]

LG, thanks. And two small NITs.

clangd/CodeComplete.h

183

Is it exposed only for tests?
Maybe add a comment that it's a private API that should be avoided and put it to the end of the file?

200

A comment does not mention the destructor will wait for the async call to finish.
Maybe add that, it looks like an important detail?

[ioeric]

• add doc

clangd/ClangdServer.h

 #include "ClangdUnit.h"
 #include "CodeComplete.h"
 #include "FSProvider.h"
 #include "Function.h"
 #include "GlobalCompilationDatabase.h"
 #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"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include <functional>
 #include <future>
 #include <string>
private:
 
   typedef uint64_t DocVersion;
 
   void consumeDiagnostics(PathRef File, DocVersion Version,
                           std::vector<Diag> Diags);
 
   tooling::CompileCommand getCompileCommand(PathRef File);
 
+  llvm::Optional<FuzzyFindRequest> speculativeFuzzyFindRequestForCompletion(
+      PathRef File, llvm::StringRef Content, Position Pos);
+
   GlobalCompilationDatabase &CDB;
   DiagnosticsConsumer &DiagConsumer;
   FileSystemProvider &FSProvider;
 
   /// Used to synchronize diagnostic responses for added and removed files.
   llvm::StringMap<DocVersion> InternalVersion;
 
   Path ResourceDir;
   // The index used to look up symbols. This could be:
   //   - null (all index functionality is optional)
   //   - the dynamic index owned by ClangdServer (FileIdx)
   //   - the static index passed to the constructor
   //   - a merged view of a static and dynamic index (MergedIndex)
   SymbolIndex *Index;
   // If present, an up-to-date of symbols in open files. Read via Index.
   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;
   /// Used to serialize diagnostic callbacks.
   /// FIXME(ibiryukov): get rid of an extra map and put all version counters
   /// into CppFile.
   std::mutex DiagnosticsMutex;
   /// Maps from a filename to the latest version of reported diagnostics.

clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "ClangdServer.h"
 #include "CodeComplete.h"
 #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"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #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"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
 #include <future>
+#include <mutex>
 
 using namespace clang;
 using namespace clang::clangd;
 
 namespace {
 
 void ignoreError(llvm::Error Err) {
   handleAllErrors(std::move(Err), [](const llvm::ErrorInfoBase &) {});
WorkScheduler.update(File, std::move(Inputs), WantDiags,
                        });
 }
 
 void ClangdServer::removeDocument(PathRef File) {
   ++InternalVersion[File];
   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<FuzzyFindRequest>
+ClangdServer::speculativeFuzzyFindRequestForCompletion(PathRef File,
+                                                       StringRef Content,
+                                                       Position Pos) {
+  llvm::Optional<FuzzyFindRequest> SpecFuzzyReq;
+  {
+    std::lock_guard<std::mutex> 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<CodeCompleteResult> CB) {
   // Copy completion options for passing them to async task handler.
   auto CodeCompleteOpts = Opts;
   if (!CodeCompleteOpts.Index) // Respect overridden index.
     CodeCompleteOpts.Index = Index;
 
   // 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,
     if (!IP)
       return CB(IP.takeError());
 
     auto PreambleData = IP->Preamble;
 
+    std::function<void(FuzzyFindRequest)> UpdateFuzzyFindReq =
+        [File, this](FuzzyFindRequest Req) {
+          std::lock_guard<std::mutex> Lock(
+              CachedCompletionFuzzyFindRequestMutex);
+          CachedCompletionFuzzyFindRequestByFile[File] = Req;
+        };
+    llvm::Optional<AsyncFuzzyFind> 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<FuzzyFindRequest> 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);
+        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,
                                 Bind(Task, File.str(), std::move(CB)));
 }
 
 void ClangdServer::signatureHelp(PathRef File, Position Pos,
                                  Callback<SignatureHelp> CB) {

clangd/CodeComplete.h

 #include "Logger.h"
 #include "Path.h"
 #include "Protocol.h"
 #include "index/Index.h"
 #include "clang/Frontend/PrecompiledPreamble.h"
 #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;
 class PCHContainerOperations;
 namespace clangd {
 
 struct CodeCompleteOptions {
   /// Returns options that can be passed to clang's completion engine.
struct CodeCompleteOptions {
   struct IncludeInsertionIndicator {
     std::string Insert = "•";
     std::string NoInsert = " ";
   } IncludeIndicator;
 
   /// 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.
   /// FIXME(ioeric): we might want a better way to pass the index around inside
   /// clangd.
   const SymbolIndex *Index = nullptr;
 
   /// Include completions that require small corrections, e.g. change '.' to

 raw_ostream &operator<<(raw_ostream &, const CodeCompletion &);
 struct CodeCompleteResult {
   std::vector<CodeCompletion> Completions;
   bool HasMore = false;
   CodeCompletionContext::Kind Context = CodeCompletionContext::CCC_Other;
 };
 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);
+/// \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,
+             const IncludeStructure &PreambleInclusions, StringRef Contents,
+             Position Pos, IntrusiveRefCntPtr<vfs::FileSystem> VFS,
+             std::function<void(FuzzyFindRequest)> UpdateCachedFuzzyFindReq,
+             AsyncFuzzyFind *SpeculativeFuzzyFind, CodeCompleteOptions Opts);
 
 /// Get signature help at a specified \p Pos in \p FileName.
 SignatureHelp
 signatureHelp(PathRef FileName, const tooling::CompileCommand &Command,
               PrecompiledPreamble const *Preamble, StringRef Contents,
               Position Pos, IntrusiveRefCntPtr<vfs::FileSystem> VFS,
               std::shared_ptr<PCHContainerOperations> PCHs, SymbolIndex *Index);
 
 // For index-based completion, we only consider:
 //   * symbols in namespaces or translation unit scopes (e.g. no class
 //     members, no locals)
 //   * enum constants in unscoped enum decl (e.g. "red" in "enum {red};")
 //   * primary templates (no specializations)

clangd/CodeComplete.cpp

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Index/USRGeneration.h"
 #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 <queue>
 
 // We log detailed candidate here if you run with -debug-only=codecomplete.
 #define DEBUG_TYPE "CodeComplete"
 
 namespace clang {
 namespace clangd {

 //     Symbol (Index), or both. It computes the result quality score.
 //     CompletionCandidate also does conversion to CompletionItem (at the end).
 //   - FuzzyMatcher scores how the candidate matches the partial identifier.
 //     This score is combined with the result quality score for the final score.
 //   - TopN determines the results with the best score.
 class CodeCompleteFlow {
   PathRef FileName;
   IncludeStructure Includes; // Complete once the compiler runs.
+  std::function<void(FuzzyFindRequest)> 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.
   bool Incomplete = false; // Would more be available with a higher limit?
   llvm::Optional<FuzzyMatcher> Filter;       // Initialized once Sema runs.
   std::vector<std::string> QueryScopes;      // Initialized once Sema runs.
   // Include-insertion and proximity scoring rely on the include structure.
   // This is available after Sema has run.
   llvm::Optional<IncludeInserter> Inserter;  // Available during runWithSema.
   llvm::Optional<URIDistance> FileProximity; // Initialized once Sema runs.
 
 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<void(FuzzyFindRequest)> 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");
 
     // 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.
     CodeCompleteResult Output;
auto RecorderOwner = llvm::make_unique<CompletionRecorder>(Opts, [&]() {
       SPAN_ATTACH(Tracer, "sema_completion_kind",
                   getCompletionKindString(Recorder->CCContext.getKind()));
       log("Code complete: sema context {0}, query scopes [{1}]",
           getCompletionKindString(Recorder->CCContext.getKind()),
           llvm::join(QueryScopes.begin(), QueryScopes.end(), ","));
     });
 
     Recorder = RecorderOwner.get();
+
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, &Includes);
 
     SPAN_ATTACH(Tracer, "sema_results", NSema);
     SPAN_ATTACH(Tracer, "index_results", NIndex);
     SPAN_ATTACH(Tracer, "merged_results", NBoth);
     SPAN_ATTACH(Tracer, "returned_results", int64_t(Output.Completions.size()));
     SPAN_ATTACH(Tracer, "incomplete", Output.HasMore);
CodeCompleteResult runWithSema() {
     //        explicitly request symbols corresponding to Sema results.
     //        We can use their signals even if the index can't suggest them.
     // We must copy index results to preserve them, but there are at most Limit.
     auto IndexResults = (Opts.Index && allowIndex(Recorder->CCContext))
                             ? queryIndex()
                             : 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) {
       Output.Completions.push_back(toCodeCompletion(C.first));
       Output.Completions.back().Score = C.second;
       Output.Completions.back().CompletionTokenRange = TextEditRange;
     }
     Output.HasMore = Incomplete;
     Output.Context = Recorder->CCContext.getKind();
     return Output;
   }
 
   SymbolSlab queryIndex() {
     trace::Span Tracer("Query index");
     SPAN_ATTACH(Tracer, "limit", int64_t(Opts.Limit));
 
-    SymbolSlab::Builder ResultsBuilder;
     // Build the query.
     FuzzyFindRequest Req;
     if (Opts.Limit)
       Req.MaxCandidateCount = Opts.Limit;
     Req.Query = Filter->pattern();
     Req.RestrictForCodeCompletion = true;
     Req.Scopes = QueryScopes;
     // FIXME: we should send multiple weighted paths here.
     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;
     return std::move(ResultsBuilder).build();
   }
 
   // Merges Sema and Index results where possible, to form CompletionCandidates.
   // Groups overloads if desired, to form CompletionCandidate::Bundles.
for (const auto &Item : Bundle) {
                         *Inserter, FileName, Opts);
       else
         Builder->add(Item, SemaCCS);
     }
     return Builder->build();
   }
 };
 
-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,
+             const IncludeStructure &PreambleInclusions, StringRef Contents,
+             Position Pos, IntrusiveRefCntPtr<vfs::FileSystem> VFS,
+             std::function<void(FuzzyFindRequest)> UpdateCachedFuzzyFindReq,
+             AsyncFuzzyFind *SpeculativeFuzzyFind, CodeCompleteOptions Opts) {
+  return CodeCompleteFlow(FileName, PreambleInclusions,
+                          std::move(UpdateCachedFuzzyFindReq),
+                          SpeculativeFuzzyFind, Opts)
       .run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs});
 }
 
 SignatureHelp signatureHelp(PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,

clangd/index/Index.h

 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/StringSaver.h"
 #include <array>
+#include <functional>
+#include <future>
 #include <string>
+#include <tuple>
 
 namespace clang {
 namespace clangd {
 
 struct SymbolLocation {
   // Specify a position (Line, Column) of symbol. Using Line/Column allows us to
   // build LSP responses without reading the file content.
   struct Position {
struct FuzzyFindRequest {
   /// \brief The number of top candidates to return. The index may choose to
   /// return more than this, e.g. if it doesn't know which candidates are best.
   size_t MaxCandidateCount = UINT_MAX;
   /// If set to true, only symbols for completion support will be considered.
   bool RestrictForCodeCompletion = false;
   /// 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);
+  }
+  bool operator!=(const FuzzyFindRequest &Req) const { return !(*this == Req); }
 };
 
 struct LookupRequest {
   llvm::DenseSet<SymbolID> IDs;
 };
 
 struct OccurrencesRequest {
   llvm::DenseSet<SymbolID> IDs;
public:
   /// Resutls are returned in arbitrary order.
   ///
   /// The returned result must be deep-copied if it's used outside Callback.
   virtual void findOccurrences(
       const OccurrencesRequest &Req,
       llvm::function_ref<void(const SymbolOccurrence &)> 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<SymbolSlab> Result;
+};
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

clangd/index/Index.cpp

 //===--- Index.cpp -----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #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 {
 using namespace llvm;
 
 raw_ostream &operator<<(raw_ostream &OS, const SymbolLocation &L) {
   if (!L)
     return OS << "(none)";
SymbolSlab SymbolSlab::Builder::build() && {
   // We may have unused strings from overwritten symbols. Build a new arena.
   BumpPtrAllocator NewArena;
   llvm::UniqueStringSaver Strings(NewArena);
   for (auto &S : Symbols)
     own(S, Strings, NewArena);
   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

clangd/tool/ClangdMain.cpp

 
 static llvm::cl::opt<bool> HeaderInsertionDecorators(
     "header-insertion-decorators",
     llvm::cl::desc("Prepend a circular dot or space before the completion "
                    "label, depending on whether "
                    "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(
         "YAML-format global symbol file to build the static index. Clangd will "
         "use the static index for global code completion.\n"
         "WARNING: This option is experimental only, and will be removed "
         "eventually. Don't rely on it."),
     llvm::cl::init(""), llvm::cl::Hidden);
int main(int argc, char *argv[]) {
   CCOpts.IncludeIneligibleResults = IncludeIneligibleResults;
   CCOpts.Limit = LimitResults;
   CCOpts.BundleOverloads = CompletionStyle != Detailed;
   CCOpts.ShowOrigins = ShowOrigins;
   if (!HeaderInsertionDecorators) {
     CCOpts.IncludeIndicator.Insert.clear();
     CCOpts.IncludeIndicator.NoInsert.clear();
   }
+  CCOpts.SpeculativeIndexRequest =
+      SpeculateCompletionIndexRequest && Opts.StaticIndex;
 
   // Initialize and run ClangdLSPServer.
   ClangdLSPServer LSPServer(
       Out, CCOpts, CompileCommandsDirPath,
       /*ShouldUseInMemoryCDB=*/CompileArgsFrom == LSPCompileArgs, Opts);
   constexpr int NoShutdownRequestErrorCode = 1;
   llvm::set_thread_name("clangd.main");
   // Change stdin to binary to not lose \r\n on windows.
   llvm::sys::ChangeStdinToBinary();
   return LSPServer.run(stdin, InputStyle) ? 0 : NoShutdownRequestErrorCode;
 }

unittests/clangd/CodeCompleteTests.cpp

public:
 
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override {}
 
   void findOccurrences(const OccurrencesRequest &Req,
                        llvm::function_ref<void(const SymbolOccurrence &)>
                            Callback) const override {}
 
-  const std::vector<FuzzyFindRequest> allRequests() const { return Requests; }
+  const std::vector<FuzzyFindRequest> consumeRequests() const {
+    auto Reqs = std::move(Requests);
+    Requests.clear();
+    return Reqs;
+  }
 
 private:
   mutable std::vector<FuzzyFindRequest> Requests;
 };
 
 std::vector<FuzzyFindRequest> captureIndexRequests(llvm::StringRef Code) {
   clangd::CodeCompleteOptions Opts;
   IndexRequestCollector Requests;
   Opts.Index = &Requests;
   completions(Code, {}, Opts);
-  return Requests.allRequests();
+  return Requests.consumeRequests();
 }
 
 TEST(CompletionTest, UnqualifiedIdQuery) {
   auto Requests = captureIndexRequests(R"cpp(
       namespace std {}
       using namespace std;
       namespace ns {
       void f() {
Opts.EnableFunctionArgSnippets = false;
     C.Kind = CompletionItemKind::Function;
 
     auto R = C.render(Opts);
     EXPECT_EQ(R.textEdit->newText, "Foo::x(${0})");
     EXPECT_EQ(R.insertTextFormat, InsertTextFormat::Snippet);
   }
 }
 
+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

unittests/clangd/IndexTests.cpp

TEST(MergeTest, PreferSymbolWithDefn) {
 
   R.Definition.FileURI = "file:/right.cpp"; // Now right will be favored.
   M = mergeSymbol(L, R, &Scratch);
   EXPECT_EQ(M.CanonicalDeclaration.FileURI, "file:/right.h");
   EXPECT_EQ(M.Definition.FileURI, "file:/right.cpp");
   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