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

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:{F6997544}

Reviewers: hokein, ilya-biryukov

Reviewed By: ilya-biryukov

Subscribers: javed.absar, jfb, MaskRay, jkorous, arphaman, kadircet, cfe-commits

Differential Revision: https://reviews.llvm.org/D50962

llvm-svn: 340604

8 files changed, 274 insertions, 19 deletions

diff --git a/clang-tools-extra/clangd/ClangdServer.cpp b/clang-tools-extra/clangd/ClangdServer.cpp
index 0a3a26c82d6..788b58294bc 100644
--- a/clang-tools-extra/clangd/ClangdServer.cpp
+++ b/clang-tools-extra/clangd/ClangdServer.cpp
@@ -12,6 +12,7 @@
 #include "FindSymbols.h"
 #include "Headers.h"
 #include "SourceCode.h"
+#include "Trace.h"
 #include "XRefs.h"
 #include "index/Merge.h"
 #include "clang/Format/Format.h"
@@ -22,6 +23,7 @@
 #include "clang/Tooling/Refactoring/RefactoringResultConsumer.h"
 #include "clang/Tooling/Refactoring/Rename/RenamingAction.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
@@ -29,6 +31,7 @@
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
 #include <future>
+#include <mutex>
 
 using namespace clang;
 using namespace clang::clangd;
@@ -181,21 +184,44 @@ void ClangdServer::codeComplete(PathRef File, Position Pos,
   // 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<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);
-    CB(std::move(Result));
+        IP->Contents, Pos, FS, PCHs, CodeCompleteOpts,
+        SpecFuzzyFind ? SpecFuzzyFind.getPointer() : nullptr);
+    {
+      clang::clangd::trace::Span Tracer("Completion results callback");
+      CB(std::move(Result));
+    }
+    if (SpecFuzzyFind && SpecFuzzyFind->NewReq.hasValue()) {
+      std::lock_guard<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,
diff --git a/clang-tools-extra/clangd/ClangdServer.h b/clang-tools-extra/clangd/ClangdServer.h
index 5613553810a..8bb5fdd653c 100644
--- a/clang-tools-extra/clangd/ClangdServer.h
+++ b/clang-tools-extra/clangd/ClangdServer.h
@@ -18,6 +18,7 @@
 #include "Protocol.h"
 #include "TUScheduler.h"
 #include "index/FileIndex.h"
+#include "index/Index.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
@@ -228,6 +229,12 @@ private:
   // 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;
diff --git a/clang-tools-extra/clangd/CodeComplete.cpp b/clang-tools-extra/clangd/CodeComplete.cpp
index 254c22be3a9..65c415fbaca 100644
--- a/clang-tools-extra/clangd/CodeComplete.cpp
+++ b/clang-tools-extra/clangd/CodeComplete.cpp
@@ -29,6 +29,7 @@
 #include "Logger.h"
 #include "Quality.h"
 #include "SourceCode.h"
+#include "TUScheduler.h"
 #include "Trace.h"
 #include "URI.h"
 #include "index/Index.h"
@@ -42,6 +43,8 @@
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Tooling/Core/Replacement.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/Support/Error.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/ScopedPrinter.h"
@@ -1077,6 +1080,32 @@ bool allowIndex(CodeCompletionContext &CC) {
   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 {
@@ -1131,7 +1160,9 @@ clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const {
 class CodeCompleteFlow {
   PathRef FileName;
   IncludeStructure Includes; // Complete once the compiler runs.
+  SpeculativeFuzzyFind *SpecFuzzyFind; // Can be nullptr.
   const CodeCompleteOptions &Opts;
+
   // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
   CompletionRecorder *Recorder = nullptr;
   int NSema = 0, NIndex = 0, NBoth = 0; // Counters for logging.
@@ -1142,15 +1173,29 @@ class CodeCompleteFlow {
   // This is available after Sema has run.
   llvm::Optional<IncludeInserter> Inserter;  // Available during runWithSema.
   llvm::Optional<URIDistance> FileProximity; // Initialized once Sema runs.
+  /// Speculative request based on the cached request and the filter text before
+  /// the cursor.
+  /// Initialized right before sema run. This is only set if `SpecFuzzyFind` is
+  /// set and contains a cached request.
+  llvm::Optional<FuzzyFindRequest> SpecReq;
 
 public:
   // A CodeCompleteFlow object is only useful for calling run() exactly once.
   CodeCompleteFlow(PathRef FileName, const IncludeStructure &Includes,
+                   SpeculativeFuzzyFind *SpecFuzzyFind,
                    const CodeCompleteOptions &Opts)
-      : FileName(FileName), Includes(Includes), Opts(Opts) {}
+      : FileName(FileName), Includes(Includes), SpecFuzzyFind(SpecFuzzyFind),
+        Opts(Opts) {}
 
   CodeCompleteResult run(const SemaCompleteInput &SemaCCInput) && {
     trace::Span Tracer("CodeCompleteFlow");
+    if (Opts.Index && SpecFuzzyFind && SpecFuzzyFind->CachedReq.hasValue()) {
+      assert(!SpecFuzzyFind->Result.valid());
+      if ((SpecReq = speculativeFuzzyFindRequestForCompletion(
+               *SpecFuzzyFind->CachedReq, SemaCCInput.FileName,
+               SemaCCInput.Contents, SemaCCInput.Pos)))
+        SpecFuzzyFind->Result = startAsyncFuzzyFind(*Opts.Index, *SpecReq);
+    }
 
     // We run Sema code completion first. It builds an AST and calculates:
     //   - completion results based on the AST.
@@ -1205,6 +1250,7 @@ public:
     });
 
     Recorder = RecorderOwner.get();
+
     semaCodeComplete(std::move(RecorderOwner), Opts.getClangCompleteOpts(),
                      SemaCCInput, &Includes);
 
@@ -1256,6 +1302,7 @@ private:
     auto IndexResults = (Opts.Index && allowIndex(Recorder->CCContext))
                             ? queryIndex()
                             : SymbolSlab();
+    trace::Span Tracer("Populate CodeCompleteResult");
     // Merge Sema, Index and Override results, score them, and pick the
     // winners.
     const auto Overrides = getNonOverridenMethodCompletionResults(
@@ -1279,7 +1326,6 @@ private:
     trace::Span Tracer("Query index");
     SPAN_ATTACH(Tracer, "limit", int64_t(Opts.Limit));
 
-    SymbolSlab::Builder ResultsBuilder;
     // Build the query.
     FuzzyFindRequest Req;
     if (Opts.Limit)
@@ -1291,7 +1337,22 @@ private:
     Req.ProximityPaths.push_back(FileName);
     vlog("Code complete: fuzzyFind(\"{0}\", scopes=[{1}])", Req.Query,
          llvm::join(Req.Scopes.begin(), Req.Scopes.end(), ","));
+
+    if (SpecFuzzyFind)
+      SpecFuzzyFind->NewReq = Req;
+    if (SpecFuzzyFind && SpecFuzzyFind->Result.valid() && (*SpecReq == Req)) {
+      vlog("Code complete: speculative fuzzy request matches the actual index "
+           "request. Waiting for the speculative index results.");
+      SPAN_ATTACH(Tracer, "Speculative results", true);
+
+      trace::Span WaitSpec("Wait speculative results");
+      return SpecFuzzyFind->Result.get();
+    }
+
+    SPAN_ATTACH(Tracer, "Speculative results", false);
+
     // Run the query against the index.
+    SymbolSlab::Builder ResultsBuilder;
     if (Opts.Index->fuzzyFind(
             Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); }))
       Incomplete = true;
@@ -1437,15 +1498,39 @@ private:
   }
 };
 
-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,
+             CodeCompleteOptions Opts, SpeculativeFuzzyFind *SpecFuzzyFind) {
+  return CodeCompleteFlow(FileName, PreambleInclusions, SpecFuzzyFind, Opts)
       .run({FileName, Command, Preamble, Contents, Pos, VFS, PCHs});
 }
 
diff --git a/clang-tools-extra/clangd/CodeComplete.h b/clang-tools-extra/clangd/CodeComplete.h
index 1d85a66ec44..1785fb6a68e 100644
--- a/clang-tools-extra/clangd/CodeComplete.h
+++ b/clang-tools-extra/clangd/CodeComplete.h
@@ -25,6 +25,10 @@
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/CodeCompleteOptions.h"
 #include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
+#include <future>
 
 namespace clang {
 class NamedDecl;
@@ -72,6 +76,16 @@ struct CodeCompleteOptions {
   /// Expose origins of completion items in the label (for debugging).
   bool ShowOrigins = false;
 
+  /// If set to true, this will send an asynchronous speculative index request,
+  /// based on the index request for the last code completion on the same file
+  /// and the filter text typed before the cursor, before sema code completion
+  /// is invoked. This can reduce the code completion latency (by roughly
+  /// latency of sema code completion) if the speculative request is the same as
+  /// the one generated for the ongoing code completion from sema. As a sequence
+  /// of code completions often have the same scopes and proximity paths etc,
+  /// this should be effective for a number of code completions.
+  bool SpeculativeIndexRequest = false;
+
   // Populated internally by clangd, do not set.
   /// If `Index` is set, it is used to augment the code completion
   /// results.
@@ -165,7 +179,27 @@ struct CodeCompleteResult {
 };
 raw_ostream &operator<<(raw_ostream &, const CodeCompleteResult &);
 
+/// A speculative and asynchronous fuzzy find index request (based on cached
+/// request) that can be sent before parsing sema. This would reduce completion
+/// latency if the speculation succeeds.
+struct SpeculativeFuzzyFind {
+  /// A cached request from past code completions.
+  /// Set by caller of `codeComplete()`.
+  llvm::Optional<FuzzyFindRequest> CachedReq;
+  /// The actual request used by `codeComplete()`.
+  /// Set by `codeComplete()`. This can be used by callers to update cache.
+  llvm::Optional<FuzzyFindRequest> NewReq;
+  /// The result is consumed by `codeComplete()` if speculation succeeded.
+  /// NOTE: the destructor will wait for the async call to finish.
+  std::future<SymbolSlab> Result;
+};
+
 /// Get code completions at a specified \p Pos in \p FileName.
+/// If \p SpecFuzzyFind is set, a speculative and asynchronous fuzzy find index
+/// request (based on cached request) will be run before parsing sema. In case
+/// the speculative result is used by code completion (e.g. speculation failed),
+/// the speculative result is not consumed, and `SpecFuzzyFind` is only
+/// destroyed when the async request finishes.
 CodeCompleteResult codeComplete(PathRef FileName,
                                 const tooling::CompileCommand &Command,
                                 PrecompiledPreamble const *Preamble,
@@ -173,7 +207,8 @@ CodeCompleteResult codeComplete(PathRef FileName,
                                 StringRef Contents, Position Pos,
                                 IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                                 std::shared_ptr<PCHContainerOperations> PCHs,
-                                CodeCompleteOptions Opts);
+                                CodeCompleteOptions Opts,
+                                SpeculativeFuzzyFind *SpecFuzzyFind = nullptr);
 
 /// Get signature help at a specified \p Pos in \p FileName.
 SignatureHelp
@@ -193,6 +228,12 @@ signatureHelp(PathRef FileName, const tooling::CompileCommand &Command,
 // like workspace/symbols or textDocument/definition, but are not used for code
 // completion.
 bool isIndexedForCodeCompletion(const NamedDecl &ND, ASTContext &ASTCtx);
+
+/// Retrives a speculative code completion filter text before the cursor.
+/// Exposed for testing only.
+llvm::Expected<llvm::StringRef>
+speculateCompletionFilter(llvm::StringRef Content, Position Pos);
+
 } // namespace clangd
 } // namespace clang
 
diff --git a/clang-tools-extra/clangd/TUScheduler.h b/clang-tools-extra/clangd/TUScheduler.h
index 27542c66250..edb19ee196a 100644
--- a/clang-tools-extra/clangd/TUScheduler.h
+++ b/clang-tools-extra/clangd/TUScheduler.h
@@ -14,6 +14,7 @@
 #include "Function.h"
 #include "Threading.h"
 #include "llvm/ADT/StringMap.h"
+#include <future>
 
 namespace clang {
 namespace clangd {
@@ -167,6 +168,18 @@ private:
   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), Context::current().clone());
+}
+
 } // namespace clangd
 } // namespace clang
 
diff --git a/clang-tools-extra/clangd/index/Index.h b/clang-tools-extra/clangd/index/Index.h
index 95b081acec7..c813ab82911 100644
--- a/clang-tools-extra/clangd/index/Index.h
+++ b/clang-tools-extra/clangd/index/Index.h
@@ -20,6 +20,7 @@
 #include "llvm/Support/StringSaver.h"
 #include <array>
 #include <string>
+#include <tuple>
 
 namespace clang {
 namespace clangd {
@@ -343,6 +344,14 @@ struct FuzzyFindRequest {
   /// 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 {
diff --git a/clang-tools-extra/clangd/tool/ClangdMain.cpp b/clang-tools-extra/clangd/tool/ClangdMain.cpp
index 0149caec85b..39f2185359a 100644
--- a/clang-tools-extra/clangd/tool/ClangdMain.cpp
+++ b/clang-tools-extra/clangd/tool/ClangdMain.cpp
@@ -308,6 +308,7 @@ int main(int argc, char *argv[]) {
     CCOpts.IncludeIndicator.Insert.clear();
     CCOpts.IncludeIndicator.NoInsert.clear();
   }
+  CCOpts.SpeculativeIndexRequest = Opts.StaticIndex;
 
   // Initialize and run ClangdLSPServer.
   ClangdLSPServer LSPServer(
diff --git a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
index 3f855844aed..b92cf64a6f2 100644
--- a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
+++ b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
@@ -927,7 +927,11 @@ public:
   // isn't used in production code.
   size_t estimateMemoryUsage() const override { return 0; }
 
-  const std::vector<FuzzyFindRequest> allRequests() const { return Requests; }
+  const std::vector<FuzzyFindRequest> consumeRequests() const {
+    auto Reqs = std::move(Requests);
+    Requests = {};
+    return Reqs;
+  }
 
 private:
   mutable std::vector<FuzzyFindRequest> Requests;
@@ -938,7 +942,7 @@ std::vector<FuzzyFindRequest> captureIndexRequests(llvm::StringRef Code) {
   IndexRequestCollector Requests;
   Opts.Index = &Requests;
   completions(Code, {}, Opts);
-  return Requests.allRequests();
+  return Requests.consumeRequests();
 }
 
 TEST(CompletionTest, UnqualifiedIdQuery) {
@@ -1709,6 +1713,75 @@ TEST(CompletionTest, SuggestOverrides) {
                     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