[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

1690

Maybe an EXPECT for this one as well?

[ioeric]

• Improve tests.

unittests/clangd/CodeCompleteTests.cpp

1690

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

188

NIT: maybe invert condition to reduce nesting?

189

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

1163

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

1519

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

clangd/index/Index.cpp

146

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

402

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

407

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

188

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–930

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

188

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

1519

Offset == 0 is handled above.

clangd/tool/ClangdMain.cpp

188

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–930

Yes.

[ioeric]

• fix typos..

[ilya-biryukov]

clangd/ClangdServer.cpp

188

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

1519

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.

216

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

clangd/tool/ClangdMain.cpp

188

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/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:
   //   - 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<DynamicIndex> DynamicIdx;
   // If present, a merged view of DynamicIdx 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/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 &) {});
void ClangdServer::codeComplete(PathRef File, Position Pos,
   // 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;
 
+    llvm::Optional<SpeculativeFuzzyFind> SpecFuzzyFind;
+    if (CodeCompleteOpts.Index && CodeCompleteOpts.SpeculativeIndexRequest) {
+      SpecFuzzyFind.emplace();
+      {
+        std::lock_guard<std::mutex> 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);
+        IP->Contents, Pos, FS, PCHs,
+        SpecFuzzyFind ? SpecFuzzyFind.getPointer() : nullptr, CodeCompleteOpts);
+    {
+      clang::clangd::trace::Span Tracer("Completion results callback");
       CB(std::move(Result));
+    }
+    if (SpecFuzzyFind && SpecFuzzyFind->NewReq.hasValue()) {
+      std::lock_guard<std::mutex> 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,
                                 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);
+
+struct SpeculativeFuzzyFind {
+  /// A cached request from past code completions.
+  /// Set by caller of codeComplete()
+  llvm::Optional<FuzzyFindRequest> CachedReq;
+  /// Speculative request based on the cached request and the filter text before
+  /// the cursor.
+  /// Set by `codeComplete()`.
+  llvm::Optional<FuzzyFindRequest> SpecReq;
+  /// The actual request used by `codeComplete()`.
+  /// Set by `codeComplete()`.
+  llvm::Optional<FuzzyFindRequest> NewReq;
+  /// Result from the speculative/asynchonous call. This is only valid if
+  /// `SpecReq` is set.
+  /// The result is consumed by `codeComplete()` if speculation succeeded.
+  /// NOTE that the structure can only be destroyed after the async call
+  /// finishes.
+  std::future<SymbolSlab> Result;
+};
+
 /// 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);
+/// 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,
+             const IncludeStructure &PreambleInclusions, StringRef Contents,
+             Position Pos, IntrusiveRefCntPtr<vfs::FileSystem> VFS,
+             SpeculativeFuzzyFind *SpecFuzzyFind, 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);
 

clangd/CodeComplete.cpp

 #include "Compiler.h"
 #include "Diagnostics.h"
 #include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Headers.h"
 #include "Logger.h"
 #include "Quality.h"
 #include "SourceCode.h"
+#include "TUScheduler.h"
 #include "Trace.h"
 #include "URI.h"
 #include "index/Index.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Basic/LangOptions.h"
 #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/ScopedPrinter.h"
 #include <queue>
 
 // We log detailed candidate here if you run with -debug-only=codecomplete.
 #define DEBUG_TYPE "CodeComplete"
 
bool allowIndex(CodeCompletionContext &CC) {
   case NestedNameSpecifier::TypeSpecWithTemplate:
   // Unresolved inside a template.
   case NestedNameSpecifier::Identifier:
     return false;
   }
   llvm_unreachable("invalid NestedNameSpecifier kind");
 }
 
+std::future<SymbolSlab> startAsyncFuzzyFind(const SymbolIndex &Index,
+                                            const FuzzyFindRequest &Req) {
+  return runAsync<SymbolSlab>([&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<FuzzyFindRequest> 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 {
   clang::CodeCompleteOptions Result;
   Result.IncludeCodePatterns = EnableSnippets && IncludeCodePatterns;
   Result.IncludeMacros = IncludeMacros;
   Result.IncludeGlobals = true;
   // We choose to include full comments and not do doxygen parsing in

 //     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.
+  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.
   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,
+                   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 ((SpecFuzzyFind->SpecReq = speculativeFuzzyFindRequestForCompletion(
+               *SpecFuzzyFind->CachedReq, SemaCCInput.FileName,
+               SemaCCInput.Contents, SemaCCInput.Pos)))
+        SpecFuzzyFind->Result =
+            startAsyncFuzzyFind(*Opts.Index, *SpecFuzzyFind->SpecReq);
+    }
 
     // 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, [&]() {
       assert(Recorder && "Recorder is not set");
       auto Style =
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() {
     // Sema provides the needed context to query the index.
     // FIXME: in addition to querying for extra/overlapping symbols, we should
     //        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();
+    trace::Span Tracer("Populate CodeCompleteResult");
     // Merge Sema, Index and Override results, score them, and pick the
     // winners.
     const auto Overrides = getNonOverridenMethodCompletionResults(
         Recorder->CCSema->CurContext, Recorder->CCSema);
     auto Top = mergeResults(Recorder->Results, IndexResults, Overrides);
     CodeCompleteResult Output;
 
     // Convert the results to final form, assembling the expensive strings.
     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 (SpecFuzzyFind)
+      SpecFuzzyFind->NewReq = Req;
+    if (SpecFuzzyFind && SpecFuzzyFind->Result.valid() &&
+        (*SpecFuzzyFind->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;
     return std::move(ResultsBuilder).build();
   }
 
   // Merges Sema, Index and Override results where possible, to form
   // CompletionCandidates. Groups overloads if desired, to form
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,
+             SpeculativeFuzzyFind *SpecFuzzyFind, CodeCompleteOptions Opts) {
+  return CodeCompleteFlow(FileName, PreambleInclusions, SpecFuzzyFind, 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/TUScheduler.h

 //===--- TUScheduler.h -------------------------------------------*-C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_TUSCHEDULER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_TUSCHEDULER_H
 
 #include "ClangdUnit.h"
 #include "Function.h"
 #include "Threading.h"
 #include "llvm/ADT/StringMap.h"
+#include <future>
 
 namespace clang {
 namespace clangd {
 
 /// Returns a number of a default async threads to use for TUScheduler.
 /// Returned value is always >= 1 (i.e. will not cause requests to be processed
 /// synchronously).
 unsigned getDefaultAsyncThreadsCount();
private:
   std::unique_ptr<ASTCache> IdleASTs;
   // None when running tasks synchronously and non-None when running tasks
   // asynchronously.
   llvm::Optional<AsyncTaskRunner> PreambleTasks;
   llvm::Optional<AsyncTaskRunner> WorkerThreads;
   std::chrono::steady_clock::duration UpdateDebounce;
 };
 
+/// Runs \p Action asynchronously with a new std::thread. The context will be
+/// propogated.
+template <typename T>
+std::future<T> runAsync(llvm::unique_function<T()> Action) {
+  return std::async(std::launch::async,
+                    [](llvm::unique_function<T()> &&Action, Context Ctx) {
+                      WithContext WithCtx(std::move(Ctx));
+                      return Action();
+                    },
+                    std::move(Action), Contex::current().clone());
+}
+
 } // namespace clangd
 } // namespace clang
 
 #endif

clangd/index/Index.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 <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:
   virtual void findOccurrences(
       const OccurrencesRequest &Req,
       llvm::function_ref<void(const SymbolOccurrence &)> Callback) const = 0;
 };
 
 } // 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"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
SymbolSlab SymbolSlab::Builder::build() && {
   BumpPtrAllocator NewArena;
   llvm::UniqueStringSaver Strings(NewArena);
   for (auto &S : Symbols)
     own(S, Strings, NewArena);
   return SymbolSlab(std::move(NewArena), std::move(Symbols));
 }
 
 } // namespace clangd
 } // namespace clang

clangd/tool/ClangdMain.cpp

llvm::cl::desc(
         "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);
 
 enum CompileArgsFrom { LSPCompileArgs, FilesystemCompileArgs };
 
 static llvm::cl::opt<CompileArgsFrom> CompileArgsFrom(
     "compile_args_from", llvm::cl::desc("The source of compile commands"),
     llvm::cl::values(clEnumValN(LSPCompileArgs, "lsp",
                                 "All compile commands come from LSP and "
                                 "'compile_commands.json' files are ignored"),
                      clEnumValN(FilesystemCompileArgs, "filesystem",
                                 "All compile commands come from the "
                                 "'compile_commands.json' files")),
     llvm::cl::init(FilesystemCompileArgs), 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 = 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() {
EXPECT_THAT(
         Results.Completions,
         UnorderedElementsAre(AllOf(Named("xfoo"), SnippetSuffix("($0)"))));
   }
 }
 
 TEST(CompletionTest, SuggestOverrides) {
   constexpr const char *const Text(R"cpp(
   class A {
    public:
     virtual void vfunc(bool param);
     virtual void vfunc(bool param, int p);
     void func(bool param);
   };
   class B : public A {
   virtual void ttt(bool param) const;
   void vfunc(bool param, int p) override;
   };
   class C : public B {
    public:
     void vfunc(bool param) override;
     ^
   };
   )cpp");
   const auto Results = completions(Text);
   EXPECT_THAT(Results.Completions,
               AllOf(Contains(Labeled("void vfunc(bool param, int p) override")),
                     Contains(Labeled("void ttt(bool param) const override")),
                     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