[clangd] Enable auto-index behind a flag.

[sammccall]

Summary

Ownership and configuration:
The auto-index (background index) is maintained by ClangdServer, like Dynamic.
(This means ClangdServer will be able to enqueue preamble indexing in future).
For now it's enabled by a simple boolean flag in ClangdServer::Options, but
we probably want to eventually allow injecting the storage strategy.

New 'sync' command:
In order to meaningfully test the integration (not just unit-test components)
we need a way for tests to ensure the asynchronous index reads/writes occur
before a certain point.
Because these tests and assertions are few, I think exposing an explicit "sync"
command for use in tests is simpler than allowing threading to be completely
disabled in the background index (as we do for TUScheduler).

Bugs:
I fixed a couple of trivial bugs I found while testing, but there's one I can't.
JSONCompilationDatabase::getAllFiles() may return relative paths, and currently
we trigger an assertion that assumes they are absolute.
There's no efficient way to resolve them (you have to retrieve the corresponding
command and then resolve against its directory property). In general I think
this behavior is broken and we should fix it in JSONCompilationDatabase and
require CompilationDatabase::getAllFiles() to be absolute.

[ioeric]

lgtm (will let @kadircet stamp )

test/clangd/background-index.test

20

Maybe make this a FIXME?

[kadircet]

Sorry for the bugs, thanks for the fixes :D

clangd/ClangdServer.cpp

515

Should we change BackgroundIndexs signature to indicate success failure? Not sure it can block but just in case something weird happens.

test/clangd/background-index.test

14

shouldn't this one be running ?

17

and this

[kadircet]

test/clangd/background-index.test

17

also I suppose we might wanna delete this file after test ends(if the temp directory is not already deleted at exit)

[kadircet]

test/clangd/background-index.test

14

Argh, sorry somehow I got confused and thought these were commented-out.. NVM

[sammccall]

Make blockUntilIdleForTest() accept a timeout, update comment.

[sammccall]

test/clangd/background-index.test

17

Convention is that tests are responsible for cleaning up the temp directory *before* they run, but not after.

clangd/ClangdLSPServer.h

 private:
   // Implement DiagnosticsConsumer.
   void onDiagnosticsReady(PathRef File, std::vector<Diag> Diagnostics) override;
 
   // LSP methods. Notifications have signature void(const Params&).
   // Calls have signature void(const Params&, Callback<Response>).
   void onInitialize(const InitializeParams &, Callback<llvm::json::Value>);
   void onShutdown(const ShutdownParams &, Callback<std::nullptr_t>);
+  void onSync(const NoParams &, Callback<std::nullptr_t>);
   void onDocumentDidOpen(const DidOpenTextDocumentParams &);
   void onDocumentDidChange(const DidChangeTextDocumentParams &);
   void onDocumentDidClose(const DidCloseTextDocumentParams &);
   void onDocumentOnTypeFormatting(const DocumentOnTypeFormattingParams &,
                                   Callback<std::vector<TextEdit>>);
   void onDocumentRangeFormatting(const DocumentRangeFormattingParams &,
                                  Callback<std::vector<TextEdit>>);
   void onDocumentFormatting(const DocumentFormattingParams &,

clangd/ClangdLSPServer.cpp

 
 void ClangdLSPServer::onShutdown(const ShutdownParams &Params,
                                  Callback<std::nullptr_t> Reply) {
   // Do essentially nothing, just say we're ready to exit.
   ShutdownRequestReceived = true;
   Reply(nullptr);
 }
 
+// sync is a clangd extension: it blocks until all background work completes.
+// It blocks the calling thread, so no messages are processed until it returns!
+void ClangdLSPServer::onSync(const NoParams &Params,
+                             Callback<std::nullptr_t> Reply) {
+  if (Server->blockUntilIdleForTest(/*TimeoutSeconds=*/60))
+    Reply(nullptr);
+  else
+    Reply(createStringError(llvm::inconvertibleErrorCode(),
+                            "Not idle after a minute"));
+}
+
 void ClangdLSPServer::onDocumentDidOpen(
     const DidOpenTextDocumentParams &Params) {
   PathRef File = Params.textDocument.uri.file();
 
   const std::string &Contents = Params.textDocument.text;
 
   DraftMgr.addDraft(File, Contents);
   Server->addDocument(File, Contents, WantDiagnostics::Yes);
: Transp(Transp), MsgHandler(new MessageHandler(*this)), CCOpts(CCOpts),
       SupportedSymbolKinds(defaultSymbolKinds()),
       SupportedCompletionItemKinds(defaultCompletionItemKinds()),
       UseDirBasedCDB(UseDirBasedCDB),
       CompileCommandsDir(std::move(CompileCommandsDir)),
       ClangdServerOpts(Opts) {
   // clang-format off
   MsgHandler->bind("initialize", &ClangdLSPServer::onInitialize);
   MsgHandler->bind("shutdown", &ClangdLSPServer::onShutdown);
+  MsgHandler->bind("sync", &ClangdLSPServer::onSync);
   MsgHandler->bind("textDocument/rangeFormatting", &ClangdLSPServer::onDocumentRangeFormatting);
   MsgHandler->bind("textDocument/onTypeFormatting", &ClangdLSPServer::onDocumentOnTypeFormatting);
   MsgHandler->bind("textDocument/formatting", &ClangdLSPServer::onDocumentFormatting);
   MsgHandler->bind("textDocument/codeAction", &ClangdLSPServer::onCodeAction);
   MsgHandler->bind("textDocument/completion", &ClangdLSPServer::onCompletion);
   MsgHandler->bind("textDocument/signatureHelp", &ClangdLSPServer::onSignatureHelp);
   MsgHandler->bind("textDocument/definition", &ClangdLSPServer::onGoToDefinition);
   MsgHandler->bind("textDocument/references", &ClangdLSPServer::onReference);

clangd/ClangdServer.h

 #include "Cancellation.h"
 #include "ClangdUnit.h"
 #include "CodeComplete.h"
 #include "FSProvider.h"
 #include "Function.h"
 #include "GlobalCompilationDatabase.h"
 #include "Protocol.h"
 #include "TUScheduler.h"
+#include "index/Background.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>
struct Options {
     bool StorePreamblesInMemory = true;
 
     /// If true, ClangdServer builds a dynamic in-memory index for symbols in
     /// opened files and uses the index to augment code completion results.
     bool BuildDynamicSymbolIndex = false;
     /// Use a heavier and faster in-memory index implementation.
     /// FIXME: we should make this true if it isn't too slow to build!.
     bool HeavyweightDynamicSymbolIndex = false;
+    /// If true, ClangdServer automatically indexes files in the current project
+    /// on background threads. The index is stored in the project root.
+    bool BackgroundIndex = false;
 
     /// If set, use this index to augment code completion results.
     SymbolIndex *StaticIndex = nullptr;
 
     /// Clangd's workspace root. Relevant for "workspace" operations not bound
     /// to a particular file.
     /// FIXME: If not set, should use the current working directory.
     llvm::Optional<std::string> WorkspaceRoot;
private:
   const FileSystemProvider &FSProvider;
 
   Path ResourceDir;
   // The index used to look up symbols. This could be:
   //   - null (all index functionality is optional)
   //   - the dynamic index owned by ClangdServer (DynamicIdx)
   //   - the static index passed to the constructor
   //   - a merged view of a static and dynamic index (MergedIndex)
-  const SymbolIndex *Index;
+  const SymbolIndex *Index = nullptr;
   // If present, an index of symbols in open files. Read via *Index.
   std::unique_ptr<FileIndex> DynamicIdx;
-  // If present, storage for the merged static/dynamic index. Read via *Index.
-  std::unique_ptr<SymbolIndex> MergedIdx;
+  // If present, the new "auto-index" maintained in background threads.
+  std::unique_ptr<BackgroundIndex> BackgroundIdx;
+  // Storage for merged views of the various indexes.
+  std::vector<std::unique_ptr<SymbolIndex>> MergedIdx;
 
   // GUARDED_BY(CachedCompletionFuzzyFindRequestMutex)
   llvm::StringMap<llvm::Optional<FuzzyFindRequest>>
       CachedCompletionFuzzyFindRequestByFile;
   mutable std::mutex CachedCompletionFuzzyFindRequestMutex;
 
   llvm::Optional<std::string> WorkspaceRoot;
   std::shared_ptr<PCHContainerOperations> PCHs;

clangd/ClangdServer.cpp

: CDB(CDB), FSProvider(FSProvider),
       // parsed file and rebuild the file index synchronously each time an AST
       // is parsed.
       // FIXME(ioeric): this can be slow and we may be able to index on less
       // critical paths.
       WorkScheduler(Opts.AsyncThreadsCount, Opts.StorePreamblesInMemory,
                     llvm::make_unique<UpdateIndexCallbacks>(DynamicIdx.get(),
                                                             DiagConsumer),
                     Opts.UpdateDebounce, Opts.RetentionPolicy) {
-  if (DynamicIdx && Opts.StaticIndex) {
-    MergedIdx =
-        llvm::make_unique<MergedIndex>(DynamicIdx.get(), Opts.StaticIndex);
-    Index = MergedIdx.get();
-  } else if (DynamicIdx)
-    Index = DynamicIdx.get();
-  else if (Opts.StaticIndex)
-    Index = Opts.StaticIndex;
-  else
-    Index = nullptr;
+  // Adds an index to the stack, at higher priority than existing indexes.
+  auto AddIndex = [&](SymbolIndex *Idx) {
+    if (this->Index != nullptr) {
+      MergedIdx.push_back(llvm::make_unique<MergedIndex>(Idx, this->Index));
+      this->Index = MergedIdx.back().get();
+    } else {
+      this->Index = Idx;
+    }
+  };
+  if (Opts.StaticIndex)
+    AddIndex(Opts.StaticIndex);
+  if (Opts.BackgroundIndex) {
+    BackgroundIdx = llvm::make_unique<BackgroundIndex>(
+        Context::current().clone(), ResourceDir, FSProvider, CDB,
+        BackgroundIndexStorage::createDiskBackedStorageFactory());
+    AddIndex(BackgroundIdx.get());
+  }
+  if (DynamicIdx)
+    AddIndex(DynamicIdx.get());
 }
 
 void ClangdServer::addDocument(PathRef File, StringRef Contents,
                                WantDiagnostics WantDiags) {
   WorkScheduler.update(File,
                        ParseInputs{getCompileCommand(File),
                                    FSProvider.getFileSystem(), Contents.str()},
                        WantDiags);

 
 std::vector<std::pair<Path, std::size_t>>
 ClangdServer::getUsedBytesPerFile() const {
   return WorkScheduler.getUsedBytesPerFile();
 }
 
 LLVM_NODISCARD bool
 ClangdServer::blockUntilIdleForTest(Optional<double> TimeoutSeconds) {
-  return WorkScheduler.blockUntilIdle(timeoutSeconds(TimeoutSeconds));
+  return WorkScheduler.blockUntilIdle(timeoutSeconds(TimeoutSeconds)) &&
+         (!BackgroundIdx ||
+          BackgroundIdx->blockUntilIdleForTest(TimeoutSeconds));
 }
 
 } // namespace clangd
 } // namespace clang

clangd/GlobalCompilationDatabase.cpp

DirectoryBasedGlobalCompilationDatabase::getCDBForFile(
   } else {
     for (auto Path = path::parent_path(File); !CDB && !Path.empty();
          Path = path::parent_path(Path)) {
       std::tie(CDB, Cached) = getCDBInDirLocked(Path);
       if (Project && CDB)
         Project->SourceRoot = Path;
     }
   }
+  // FIXME: getAllFiles() may return relative paths, we need absolute paths.
+  // Hopefully the fix is to change JSONCompilationDatabase and the interface.
   if (CDB && !Cached)
     OnCommandChanged.broadcast(CDB->getAllFiles());
   return CDB;
 }
 
 OverlayCDB::OverlayCDB(const GlobalCompilationDatabase *Base,
                        std::vector<std::string> FallbackFlags)
     : Base(Base), FallbackFlags(std::move(FallbackFlags)) {
OverlayCDB::getCompileCommand(PathRef File, ProjectInfo *Project) const {
     std::lock_guard<std::mutex> Lock(Mutex);
     auto It = Commands.find(File);
     if (It != Commands.end()) {
       if (Project)
         Project->SourceRoot = "";
       return It->second;
     }
   }
-  return Base ? Base->getCompileCommand(File) : None;
+  return Base ? Base->getCompileCommand(File, Project) : None;
 }
 
 tooling::CompileCommand OverlayCDB::getFallbackCommand(PathRef File) const {
   auto Cmd = Base ? Base->getFallbackCommand(File)
                   : GlobalCompilationDatabase::getFallbackCommand(File);
   std::lock_guard<std::mutex> Lock(Mutex);
   Cmd.CommandLine.insert(Cmd.CommandLine.end(), FallbackFlags.begin(),
                          FallbackFlags.end());

clangd/index/Background.h

public:
   void enqueue(const std::vector<std::string> &ChangedFiles);
   void enqueue(const std::string &File);
 
   // Cause background threads to stop after ther current task, any remaining
   // tasks will be discarded.
   void stop();
 
   // Wait until the queue is empty, to allow deterministic testing.
-  void blockUntilIdleForTest();
+  LLVM_NODISCARD bool
+  blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds = 10);
 
   using FileDigest = decltype(llvm::SHA1::hash({}));
 
 private:
   /// Given index results from a TU, only update files in \p FilesToUpdate.
   void update(llvm::StringRef MainFile, SymbolSlab Symbols, RefSlab Refs,
               const llvm::StringMap<FileDigest> &FilesToUpdate,
               BackgroundIndexStorage *IndexStorage);

clangd/index/Background.cpp

(*Task)();
       std::unique_lock<std::mutex> Lock(QueueMu);
       assert(NumActiveTasks > 0 && "before decrementing");
       --NumActiveTasks;
     }
     QueueCV.notify_all();
   }
 }
 
-void BackgroundIndex::blockUntilIdleForTest() {
+bool BackgroundIndex::blockUntilIdleForTest(
+    llvm::Optional<double> TimeoutSeconds) {
   std::unique_lock<std::mutex> Lock(QueueMu);
-  QueueCV.wait(Lock, [&] { return Queue.empty() && NumActiveTasks == 0; });
+  return wait(Lock, QueueCV, timeoutSeconds(TimeoutSeconds),
+              [&] { return Queue.empty() && NumActiveTasks == 0; });
 }
 
 void BackgroundIndex::enqueue(const std::vector<std::string> &ChangedFiles) {
   enqueueTask([this, ChangedFiles] {
     trace::Span Tracer("BackgroundIndexEnqueue");
     // We're doing this asynchronously, because we'll read shards here too.
     // FIXME: read shards here too.
 

clangd/index/BackgroundIndexStorage.cpp

 }
 
 std::string getShardPathFromFilePath(llvm::StringRef ShardRoot,
                                      llvm::StringRef FilePath) {
   llvm::SmallString<128> ShardRootSS(ShardRoot);
   llvm::sys::path::append(ShardRootSS, llvm::sys::path::filename(FilePath) +
                                            "." + llvm::toHex(digest(FilePath)) +
                                            ".idx");
-  return ShardRoot.str();
+  return ShardRootSS.str();
 }
 
 // Uses disk as a storage for index shards. Creates a directory called
 // ".clangd-index/" under the path provided during construction.
 class DiskBackedIndexStorage : public BackgroundIndexStorage {
   std::string DiskShardRoot;
 
 public:
vlog("Couldn't find project for {0}, indexing in-memory only",
          ShardIdentifier);
     return llvm::Error::success();
   }
 };
 
 // Creates and owns IndexStorages for multiple CDBs.
 class DiskBackedIndexStorageManager {
 public:
+  DiskBackedIndexStorageManager()
+      : IndexStorageMapMu(llvm::make_unique<std::mutex>()) {}
+
   // Creates or fetches to storage from cache for the specified CDB.
   BackgroundIndexStorage *operator()(llvm::StringRef CDBDirectory) {
     std::lock_guard<std::mutex> Lock(*IndexStorageMapMu);
     auto &IndexStorage = IndexStorageMap[CDBDirectory];
     if (!IndexStorage)
       IndexStorage = create(CDBDirectory);
     return IndexStorage.get();
   }

clangd/tool/ClangdMain.cpp

static cl::opt<Path> IndexFile(
     "index-file",
     cl::desc(
         "Index file to build the static index. The file must have been created "
         "by a compatible clangd-index.\n"
         "WARNING: This option is experimental only, and will be removed "
         "eventually. Don't rely on it."),
     cl::init(""), cl::Hidden);
 
+static cl::opt<bool> EnableBackgroundIndex(
+    "background-index",
+    cl::desc("Index project code in the background and persist index on disk. "
+             "Experimental"),
+    cl::init(false), cl::Hidden);
+
 enum CompileArgsFrom { LSPCompileArgs, FilesystemCompileArgs };
 static cl::opt<CompileArgsFrom> CompileArgsFrom(
     "compile_args_from", cl::desc("The source of compile commands"),
     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 "
int main(int argc, char *argv[]) {
   case PCHStorageFlag::Disk:
     Opts.StorePreamblesInMemory = false;
     break;
   }
   if (!ResourceDir.empty())
     Opts.ResourceDir = ResourceDir;
   Opts.BuildDynamicSymbolIndex = EnableIndex;
   Opts.HeavyweightDynamicSymbolIndex = UseDex;
+  Opts.BackgroundIndex = EnableBackgroundIndex;
   std::unique_ptr<SymbolIndex> StaticIdx;
   std::future<void> AsyncIndexLoad; // Block exit while loading the index.
   if (EnableIndex && !IndexFile.empty()) {
     // Load the index asynchronously. Meanwhile SwapIndex returns no results.
     SwapIndex *Placeholder;
     StaticIdx.reset(Placeholder = new SwapIndex(llvm::make_unique<MemIndex>()));
     AsyncIndexLoad = runAsync<void>([Placeholder] {
       if (auto Idx = loadIndex(IndexFile, /*UseDex=*/true))

test/clangd/Inputs/background-index/compile_commands.json

+[{
+  "directory": "DIRECTORY",
+  "command": "clang foo.cpp",
+  "file": "DIRECTORY/foo.cpp"
+}]

test/clangd/Inputs/background-index/definition.jsonrpc

+{
+  "jsonrpc": "2.0",
+  "id": 0,
+  "method": "initialize",
+  "params": {
+    "processId": 123,
+    "rootPath": "clangd",
+    "capabilities": {},
+    "trace": "off"
+  }
+}
+---
+{
+  "jsonrpc": "2.0",
+  "method": "textDocument/didOpen",
+  "params": {
+    "textDocument": {
+      "uri": "file://DIRECTORY/bar.cpp",
+      "languageId": "cpp",
+      "version": 1,
+      "text": "#include \"foo.h\"\nint main(){\nreturn foo();\n}"
+    }
+  }
+}
+---
+{
+  "jsonrpc": "2.0",
+  "id": 1,
+  "method": "sync",
+  "params": null
+}
+---
+{
+  "jsonrpc": "2.0",
+  "id": 2,
+  "method": "textDocument/definition",
+  "params": {
+    "textDocument": {
+      "uri": "file://DIRECTORY/bar.cpp"
+    },
+    "position": {
+      "line": 2,
+      "character": 8
+    }
+  }
+}
+# CHECK: "uri": "file://DIRECTORY/foo.cpp"
+---
+{"jsonrpc":"2.0","id":3,"method":"shutdown"}
+---
+{"jsonrpc":"2.0","method":"exit"}

test/clangd/Inputs/background-index/foo.h

+#ifndef FOO_H
+#define FOO_H
+int foo();
+#endif

test/clangd/Inputs/background-index/foo.cpp

+#include "foo.h"
+int foo() { return 42; }

test/clangd/background-index.test

+# We need to splice paths into file:// URIs for this test.
+# UNSUPPORTED: win32
+
+# Use a copy of inputs, as we'll mutate it (as will the background index).
+# RUN: rm -rf %t
+# RUN: cp -r %S/Inputs/background-index %t
+# Need to embed the correct temp path in the actual JSON-RPC requests.
+# RUN: sed -i -e "s|DIRECTORY|%t|" %t/*
+
+# We're editing bar.cpp, which includes foo.h.
+# foo() is declared in foo.h and defined in foo.cpp.
+# The background index should allow us to go-to-definition on foo().
+# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | FileCheck %t/definition.jsonrpc
+
+# Test that the index is writing files in the expected location.
+# RUN: ls %t/.clangd-index/foo.cpp.*.idx
+
+# Test the index is read from disk: delete code and restart clangd.
+# FIXME: This test currently fails as we don't read the index yet.
+# RUN: rm %t/foo.cpp
+# RUN: clangd -background-index -lit-test < %t/definition.jsonrpc | not FileCheck %t/definition.jsonrpc

unittests/clangd/BackgroundIndexTests.cpp

BackgroundIndex Idx(Context::empty(), "", FS, CDB,
                       [&](llvm::StringRef) { return &MSS; });
 
   tooling::CompileCommand Cmd;
   Cmd.Filename = testPath("root/A.cc");
   Cmd.Directory = testPath("root");
   Cmd.CommandLine = {"clang++", "-DA=1", testPath("root/A.cc")};
   CDB.setCompileCommand(testPath("root"), Cmd);
 
-  Idx.blockUntilIdleForTest();
+  ASSERT_TRUE(Idx.blockUntilIdleForTest());
   EXPECT_THAT(
       runFuzzyFind(Idx, ""),
       UnorderedElementsAre(Named("common"), Named("A_CC"),
                            AllOf(Named("f_b"), Declared(), Not(Defined()))));
 
   Cmd.Filename = testPath("root/B.cc");
   Cmd.CommandLine = {"clang++", Cmd.Filename};
   CDB.setCompileCommand(testPath("root"), Cmd);
 
-  Idx.blockUntilIdleForTest();
+  ASSERT_TRUE(Idx.blockUntilIdleForTest());
   // B_CC is dropped as we don't collect symbols from A.h in this compilation.
   EXPECT_THAT(runFuzzyFind(Idx, ""),
               UnorderedElementsAre(Named("common"), Named("A_CC"),
                                    AllOf(Named("f_b"), Declared(), Defined())));
 
   auto Syms = runFuzzyFind(Idx, "common");
   EXPECT_THAT(Syms, UnorderedElementsAre(Named("common")));
   auto Common = *Syms.begin();
TEST(BackgroundIndexTest, ShardStorageWriteTest) {
   Cmd.Directory = testPath("root");
   Cmd.CommandLine = {"clang++", testPath("root/A.cc")};
   // Check nothing is loaded from Storage, but A.cc and A.h has been stored.
   {
     OverlayCDB CDB(/*Base=*/nullptr);
     BackgroundIndex Idx(Context::empty(), "", FS, CDB,
                         [&](llvm::StringRef) { return &MSS; });
     CDB.setCompileCommand(testPath("root"), Cmd);
-    Idx.blockUntilIdleForTest();
+    ASSERT_TRUE(Idx.blockUntilIdleForTest());
   }
   EXPECT_EQ(CacheHits, 0U);
   EXPECT_EQ(Storage.size(), 2U);
 
   auto ShardHeader = MSS.loadShard(testPath("root/A.h"));
   EXPECT_NE(ShardHeader, nullptr);
   EXPECT_THAT(
       *ShardHeader->Symbols,