[clangd] Minimal implementation of automatic static index, behind a flag.

[sammccall]

Summary

See tinyurl.com/clangd-automatic-index for design and goals.

Lots of limitations to keep this patch smallish, TODOs everywhere:

• no serialization to disk
• no changes to dynamic index, which now has a much simpler job
• no partitioning of symbols by file to avoid duplication of header symbols
• no reindexing of edited files
• only a single worker thread
• compilation database is slurped synchronously (doesn't scale)
• uses memindex, rebuilds after every file (should be dex, periodically)

Still needs tests, but should be ready for review of the basic shape.

[ioeric]

Looks good in general.

clangd/ClangdLSPServer.h

117

please document what the callback is for and how often it's called.

clangd/index/Background.cpp

64

Maybe add a trace?

99

Why is this needed?

164

Add a FIXME to use Dex?

clangd/index/Background.h

2

Is it possible to add test for this?

29

s/TODO/FIXME/?

40

Maybe add a FIXME for files not in CDB e.g. headers?

clangd/tool/ClangdMain.cpp

170

Should we ignore index-file/auto-index if one is set?

[sammccall]

clangd/index/Background.cpp

99

Removed. I copied it from the related code in JSONCompilationDatabase, but I'm not sure what the right behavior is, as JSONCompilationDatabase doesn't specify the format of paths.

164

Added it to the existing TODO. They're coupled: dex is expensive to build, so rebuilding it after every file wouldnt' make sense.

clangd/index/Background.h

2

Added a test that indexes a file, waits for the queue to be empty, and queries.

That's pretty basic, do you have suggestions for things you'd like to see tested?

40

There's nothing missing for headers at this point.
Headers will already be indexed (as part of any TU that includes them).
Later, we'll partition the outputs by file, but these headers will still be indexed.
When it comes time to watch files on disk for changes, then we'll need to consider headers specially.

Indexing headers that are not included by any file is out of scope (it's not clear this is a good idea, e.g. consider files under test/ in llvm).

clangd/tool/ClangdMain.cpp

170

Since this is hidden/experimental, I think it's not worth adding explicit code so they interact nicely, I just documented the behavior instead instead.

[sammccall]

Address comments, add tests.
Some changes (enqueue(), blockUntilIdleForTest()) to support testing.

[sammccall]

clangd/ClangdLSPServer.h

117

Documented at the callsite and in GlobalCompilationDatabase.h.
This class here is really just plumbing (it shouldn't be in the header at all)

[sammccall]

Oops, forgot one comment.

[ioeric]

clangd/index/Background.cpp

51

Maybe generalize this to NumActiveTasks? Currently, this is single-threaded and safe, but it could be missed when we add more threads.

unittests/clangd/BackgroundIndexTests.cpp

14

Also add a test for enqueueAll with multiple TUs ?

[sammccall]

unittests/clangd/BackgroundIndexTests.cpp

14

Is it important to call enqueueAll specifically vs enqueue multiple times?

We don't have a good test fixture for a compilation database, and enqueueAll is trivial...

[ioeric]

unittests/clangd/BackgroundIndexTests.cpp

14

I think the randomization code worths a test.

How about adding a test in ClangdServer with the auto index enabled? I think we'd also want coverage in ClangdServer anyway.

[sammccall]

unittests/clangd/BackgroundIndexTests.cpp

14

How would you suggest testing the randomization :-)

The problem with a ClangdServer test is that it doesn't know anything about autoindex.
AutoIndex lives in ClangdLSPServer, because that's where the compilation database lives (because people keep cramming LSP extensions in to manipulate it, and I haven't been able to remove them).
Nobody has worked out how to test ClangdLSPServer yet. It's a worthy project, but...

[ioeric]

unittests/clangd/BackgroundIndexTests.cpp

14

How would you suggest testing the randomization :-)

Not suggesting testing the behavior; just test that it works really. I guess a single file would also do it.

The problem with a ClangdServer test is that it doesn't know anything about autoindex.

Ah, I see. That's a bit unfortunate. ClangdServer seems to be a better place for the auto index. I wonder if we could move AutoIndex into ClangdServer? I'm not very familiar with CDB APIs, but intuitively this seems doable if we tweak the interface of CDB a bit e.g. inject the callback into GlobalCompilationDatabase without going through CompilationDB? Not sure if how well this would play with the CDB design though.

[sammccall]

unittests/clangd/BackgroundIndexTests.cpp

14

ClangdServer seems to be a better place for the auto index

I fully agree.

I wonder if we could move AutoIndex into ClangdServer? I'm not very familiar with CDB APIs...

Currently the global CDB is trying to be all things to all people:

• by default, it follows Tooling conventions and looks for compile_commands above the source files
• google's hosted option wants it to be completely opaque, no indexing
• apple wants it to be an in-memory store mutated over LSP
• ericsson wants it to be a fixed directory set by the user

And we've implemented these in ad-hoc ways, not behind any real abstraction. I don't think adding more functionality to the interface without addressing this is a great idea, and I don't really know how to untangle all this without asking people to rethink their use cases. But I'll think about this some more.

[sammccall]

Address comments, strip out of clangdlspserver for now.

[sammccall]

unittests/clangd/BackgroundIndexTests.cpp

14

After thinking about this, decided to just check in the library with unit tests for now while we sort out the layering.
I've ripped out all the ClangdMain and ClangdLSPServer changes.

[ioeric]

still lgtm

clangd/Compiler.cpp

83

Maybe also revert this change?

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   RIFF.cpp
   SourceCode.cpp
   Threading.cpp
   Trace.cpp
   TUScheduler.cpp
   URI.cpp
   XRefs.cpp
 
+  index/Background.cpp
   index/CanonicalIncludes.cpp
   index/FileIndex.cpp
   index/Index.cpp
   index/IndexAction.cpp
   index/MemIndex.cpp
   index/Merge.cpp
   index/Serialization.cpp
   index/SymbolCollector.cpp

clangd/ClangdLSPServer.h

 
 #include "ClangdServer.h"
 #include "DraftStore.h"
 #include "FindSymbols.h"
 #include "GlobalCompilationDatabase.h"
 #include "Path.h"
 #include "Protocol.h"
 #include "ProtocolHandlers.h"
+#include "index/Background.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "llvm/ADT/Optional.h"
 #include <memory>
 
 namespace clang {
 namespace clangd {
 
 class JSONOutput;
 class SymbolIndex;
 
 /// This class exposes ClangdServer's capabilities via Language Server Protocol.
 ///
 /// JSONRPCDispatcher binds the implemented ProtocolCallbacks methods
 /// (e.g. onInitialize) to corresponding JSON-RPC methods ("initialize").
 /// The server also supports $/cancelRequest (JSONRPCDispatcher provides this).
 class ClangdLSPServer : private DiagnosticsConsumer, private ProtocolCallbacks {
 public:
   /// If \p CompileCommandsDir has a value, compile_commands.json will be
   /// loaded only from \p CompileCommandsDir. Otherwise, clangd will look
   /// for compile_commands.json in all parent directories of each file.
   ClangdLSPServer(JSONOutput &Out, const clangd::CodeCompleteOptions &CCOpts,
                   llvm::Optional<Path> CompileCommandsDir,
-                  bool ShouldUseInMemoryCDB, const ClangdServer::Options &Opts);
+                  bool ShouldUseInMemoryCDB, bool AutoIndex,
+                  const ClangdServer::Options &Opts);
 
   /// Run LSP server loop, receiving input for it from \p In. \p In must be
   /// opened in binary mode. Output will be written using Out variable passed to
   /// class constructor. This method must not be executed more than once for
   /// each instance of ClangdLSPServer.
   ///
   /// \return Whether we received a 'shutdown' request before an 'exit' request.
   bool run(std::FILE *In,
private:
   /// Caches FixIts per file and diagnostics
   llvm::StringMap<DiagnosticToReplacementMap> FixItsMap;
 
   /// Encapsulates the directory-based or the in-memory compilation database
   /// that's used by the LSP server.
   class CompilationDB {
   public:
     static CompilationDB makeInMemory();
-    static CompilationDB
-    makeDirectoryBased(llvm::Optional<Path> CompileCommandsDir);
+    static CompilationDB makeDirectoryBased(
+        llvm::Optional<Path> CompileCommandsDir,
+        std::function<void(llvm::StringRef,
+                           const tooling::CompilationDatabase &)> OnNewCDB);
 
     void invalidate(PathRef File);
 
     /// Sets the compilation command for a particular file.
     /// Only valid for in-memory CDB, no-op and error log on DirectoryBasedCDB.
     ///
     /// \returns True if the File had no compilation command before.
     bool
private:
   clangd::CodeCompleteOptions CCOpts;
   /// Options used for diagnostics.
   ClangdDiagnosticOptions DiagOpts;
   /// The supported kinds of the client.
   SymbolKindBitset SupportedSymbolKinds;
   /// The supported completion item kinds of the client.
   CompletionItemKindBitset SupportedCompletionItemKinds;
 
+  llvm::Optional<BackgroundIndex> BackgroundIdx;
+
   // Store of the current versions of the open documents.
   DraftStore DraftMgr;
 
   // Server must be the last member of the class to allow its destructor to exit
   // the worker thread that may otherwise run an async callback on partially
   // destructed instance of ClangdLSPServer.
   // Set in construtor and destroyed when run() finishes. To ensure all worker
   // threads exit before run() returns.
   std::unique_ptr<ClangdServer> Server;
 };
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_CLANGDLSPSERVER_H

clangd/ClangdLSPServer.cpp

 //===--- ClangdLSPServer.cpp - LSP server ------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangdLSPServer.h"
+#include "Compiler.h"
 #include "Diagnostics.h"
 #include "JSONRPCDispatcher.h"
 #include "SourceCode.h"
 #include "URI.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
reply(json::Object{
                  {"commands", {ExecuteCommandParams::CLANGD_APPLY_FIX_COMMAND}},
              }},
         }}}});
 }
 
 void ClangdLSPServer::onShutdown(ShutdownParams &Params) {
   // Do essentially nothing, just say we're ready to exit.
   ShutdownRequestReceived = true;
+  if (BackgroundIdx)
+    BackgroundIdx->stop();
   reply(nullptr);
 }
 
 void ClangdLSPServer::onExit(ExitParams &Params) { IsDone = true; }
 
 void ClangdLSPServer::onDocumentDidOpen(DidOpenTextDocumentParams &Params) {
   PathRef File = Params.textDocument.uri.file();
   if (Params.metadata && !Params.metadata->extraFlags.empty())
Server->findReferences(Params.textDocument.uri.file(), Params.position,
                                  llvm::toString(Locations.takeError()));
                            reply(llvm::json::Array(*Locations));
                          });
 }
 
 ClangdLSPServer::ClangdLSPServer(JSONOutput &Out,
                                  const clangd::CodeCompleteOptions &CCOpts,
                                  llvm::Optional<Path> CompileCommandsDir,
-                                 bool ShouldUseInMemoryCDB,
+                                 bool ShouldUseInMemoryCDB, bool AutoIndex,
                                  const ClangdServer::Options &Opts)
-    : Out(Out), CDB(ShouldUseInMemoryCDB ? CompilationDB::makeInMemory()
-                                         : CompilationDB::makeDirectoryBased(
-                                               std::move(CompileCommandsDir))),
+    : Out(Out), CDB(ShouldUseInMemoryCDB
+                        ? CompilationDB::makeInMemory()
+                              std::move(CompileCommandsDir),
+                              [&](StringRef Dir,
+                                  const tooling::CompilationDatabase &CDB) {
+                                // We found a new compilation DB.
+                                if (BackgroundIdx)
+                                  BackgroundIdx->enqueueAll(Dir, CDB);
+                              })),
       CCOpts(CCOpts), SupportedSymbolKinds(defaultSymbolKinds()),
-      SupportedCompletionItemKinds(defaultCompletionItemKinds()),
-      Server(new ClangdServer(CDB.getCDB(), FSProvider, /*DiagConsumer=*/*this,
-                              Opts)) {}
+      SupportedCompletionItemKinds(defaultCompletionItemKinds()) {
+  ClangdServer::Options SOpts = Opts;
+  if (AutoIndex) {
+    log("Static index will be built in the background from compilation DB.");
+    BackgroundIdx.emplace(Context::empty(),
+                          Opts.ResourceDir
+                              ? *Opts.ResourceDir
+                              : StringRef(getStandardResourceDir()),
+                          FSProvider);
+    SOpts.StaticIndex = BackgroundIdx.getPointer();
+  }
+  Server.reset(new ClangdServer(CDB.getCDB(), FSProvider,
+                                /*DiagConsumer=*/*this, SOpts));
+}
 
 bool ClangdLSPServer::run(std::FILE *In, JSONStreamStyle InputStyle) {
   assert(!IsDone && "Run was called before");
   assert(Server);
 
   // Set up JSONRPCDispatcher.
   JSONRPCDispatcher Dispatcher([](const json::Value &Params) {
     replyError(ErrorCode::MethodNotFound, "method not found");

 
 ClangdLSPServer::CompilationDB ClangdLSPServer::CompilationDB::makeInMemory() {
   return CompilationDB(llvm::make_unique<InMemoryCompilationDb>(), nullptr,
                        /*IsDirectoryBased=*/false);
 }
 
 ClangdLSPServer::CompilationDB
 ClangdLSPServer::CompilationDB::makeDirectoryBased(
-    llvm::Optional<Path> CompileCommandsDir) {
+    llvm::Optional<Path> CompileCommandsDir,
+    std::function<void(StringRef, const tooling::CompilationDatabase &)>
+        OnNewCDB) {
   auto CDB = llvm::make_unique<DirectoryBasedGlobalCompilationDatabase>(
-      std::move(CompileCommandsDir));
+      std::move(CompileCommandsDir), std::move(OnNewCDB));
   auto CachingCDB = llvm::make_unique<CachingCompilationDb>(*CDB);
   return CompilationDB(std::move(CDB), std::move(CachingCDB),
                        /*IsDirectoryBased=*/true);
 }
 
 void ClangdLSPServer::CompilationDB::invalidate(PathRef File) {
   if (!IsDirectoryBased)
     static_cast<InMemoryCompilationDb *>(CDB.get())->invalidate(File);

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 "Compiler.h"
 #include "FindSymbols.h"
 #include "Headers.h"
 #include "SourceCode.h"
 #include "Trace.h"
 #include "XRefs.h"
 #include "index/FileIndex.h"
 #include "index/Merge.h"
 #include "clang/Format/Format.h"

 using namespace clang::clangd;
 
 namespace {
 
 void ignoreError(llvm::Error Err) {
   handleAllErrors(std::move(Err), [](const llvm::ErrorInfoBase &) {});
 }
 
-std::string getStandardResourceDir() {
-  static int Dummy; // Just an address in this process.
-  return CompilerInvocation::GetResourcesPath("clangd", (void *)&Dummy);
-}
-
 class RefactoringResultCollector final
     : public tooling::RefactoringResultConsumer {
 public:
   void handleError(llvm::Error Err) override {
     assert(!Result.hasValue());
     // FIXME: figure out a way to return better message for DiagnosticError.
     // clangd uses llvm::toString to convert the Err to string, however, for
     // DiagnosticError, only "clang diagnostic" will be generated.

clangd/Compiler.h

 /// be consumed by FrontendAction::BeginSourceFile to properly destroy \p
 /// MainFile.
 std::unique_ptr<CompilerInstance> prepareCompilerInstance(
     std::unique_ptr<clang::CompilerInvocation>, const PrecompiledPreamble *,
     std::unique_ptr<llvm::MemoryBuffer> MainFile,
     std::shared_ptr<PCHContainerOperations>,
     IntrusiveRefCntPtr<llvm::vfs::FileSystem>, DiagnosticConsumer &);
 
+std::string getStandardResourceDir();
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_COMPILER_H

clangd/Compiler.cpp

if (!Clang->hasTarget())
     return nullptr;
 
   // RemappedFileBuffers will handle the lifetime of the Buffer pointer,
   // release it.
   Buffer.release();
   return Clang;
 }
 
+std::string getStandardResourceDir() {
+  static int Dummy; // Just an address in this process.
+  return CompilerInvocation::GetResourcesPath("clangd", (void *)&Dummy);
+}
+
 } // namespace clangd
 } // namespace clang

clangd/GlobalCompilationDatabase.h

public:
   /// existing targets.
 };
 
 /// Gets compile args from tooling::CompilationDatabases built for parent
 /// directories.
 class DirectoryBasedGlobalCompilationDatabase
     : public GlobalCompilationDatabase {
 public:
+  // OnNewCDB is called after each compilation database is first loaded.
   DirectoryBasedGlobalCompilationDatabase(
-      llvm::Optional<Path> CompileCommandsDir);
+      llvm::Optional<Path> CompileCommandsDir,
+      std::function<void(llvm::StringRef,
+                         const clang::tooling::CompilationDatabase &)>
+          OnNewCDB = nullptr);
   ~DirectoryBasedGlobalCompilationDatabase() override;
 
   /// Scans File's parents looking for compilation databases.
   /// Any extra flags will be added.
   llvm::Optional<tooling::CompileCommand>
   getCompileCommand(PathRef File) const override;
 
   /// Uses the default fallback command, adding any extra flags.
private:
   mutable llvm::StringMap<std::unique_ptr<clang::tooling::CompilationDatabase>>
       CompilationDatabases;
 
   /// Stores extra flags per file.
   llvm::StringMap<std::vector<std::string>> ExtraFlagsForFile;
   /// Used for command argument pointing to folder where compile_commands.json
   /// is located.
   llvm::Optional<Path> CompileCommandsDir;
+  std::function<void(llvm::StringRef, const tooling::CompilationDatabase &)>
+      OnNewCDB;
 };
 
 /// A wrapper around GlobalCompilationDatabase that caches the compile commands.
 /// Note that only results of getCompileCommand are cached.
 class CachingCompilationDb : public GlobalCompilationDatabase {
 public:
   explicit CachingCompilationDb(const GlobalCompilationDatabase &InnerCDB);
 

clangd/GlobalCompilationDatabase.cpp

GlobalCompilationDatabase::getFallbackCommand(PathRef File) const {
   return tooling::CompileCommand(llvm::sys::path::parent_path(File),
                                  llvm::sys::path::filename(File),
                                  std::move(Argv),
                                  /*Output=*/"");
 }
 
 DirectoryBasedGlobalCompilationDatabase::
     DirectoryBasedGlobalCompilationDatabase(
-        llvm::Optional<Path> CompileCommandsDir)
-    : CompileCommandsDir(std::move(CompileCommandsDir)) {}
+        llvm::Optional<Path> CompileCommandsDir,
+        std::function<void(llvm::StringRef,
+                           const tooling::CompilationDatabase &)>
+            OnNewCDB)
+    : CompileCommandsDir(std::move(CompileCommandsDir)),
+      OnNewCDB(std::move(OnNewCDB)) {}
 
 DirectoryBasedGlobalCompilationDatabase::
     ~DirectoryBasedGlobalCompilationDatabase() = default;
 
 llvm::Optional<tooling::CompileCommand>
 DirectoryBasedGlobalCompilationDatabase::getCompileCommand(PathRef File) const {
   if (auto CDB = getCDBForFile(File)) {
     auto Candidates = CDB->getCompileCommands(File);
DirectoryBasedGlobalCompilationDatabase::getCDBInDirLocked(PathRef Dir) const {
   // FIXME(ibiryukov): Invalidate cached compilation databases on changes
   auto CachedIt = CompilationDatabases.find(Dir);
   if (CachedIt != CompilationDatabases.end())
     return CachedIt->second.get();
   std::string Error = "";
   auto CDB = tooling::CompilationDatabase::loadFromDirectory(Dir, Error);
   auto Result = CDB.get();
   CompilationDatabases.insert(std::make_pair(Dir, std::move(CDB)));
+  if (Result && OnNewCDB) {
+    Mutex.unlock();
+    OnNewCDB(Dir, *Result);
+    Mutex.lock();
+  }
   return Result;
 }
 
 tooling::CompilationDatabase *
 DirectoryBasedGlobalCompilationDatabase::getCDBForFile(PathRef File) const {
   namespace path = llvm::sys::path;
   assert((path::is_absolute(File, path::Style::posix) ||
           path::is_absolute(File, path::Style::windows)) &&

clangd/index/Background.h

+//===--- Background.h - Build an index in a background thread ----*- 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_INDEX_BACKGROUND_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
+
+#include "Context.h"
+#include "FSProvider.h"
+#include "index/Index.h"
+#include "index/FileIndex.h"
+#include "clang/Tooling/CompilationDatabase.h"
+#include "llvm/Support/SHA1.h"
+#include <condition_variable>
+#include <deque>
+#include <thread>
+
+namespace clang {
+namespace clangd {
+
+// Builds an in-memory index by by running the static indexer action over
+// all commands in a compilation database. Indexing happens in the background.
+// FIXME: it should also persist its state on disk for fast start.
+// FIXME: it should watch for changes to files on disk.
+class BackgroundIndex : public SwapIndex {
+public:
+  // FIXME: resource-dir injection should be hoisted somewhere common.
+  BackgroundIndex(Context BackgroundContext,
+                  StringRef ResourceDir, const FileSystemProvider &);
+  ~BackgroundIndex(); // Blocks while the current task finishes.
+
+  // Enqueue a translation unit for indexing.
+  // The indexing happens in a background thread, so the symbols will be
+  // available sometime later.
+  void enqueue(llvm::StringRef Directory, tooling::CompileCommand);
+  // Index all TUs described in the compilation database.
+  void enqueueAll(llvm::StringRef Directory,
+                  const tooling::CompilationDatabase &);
+
+  // 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();
+
+private:
+  // configuration
+  std::string ResourceDir;
+  const FileSystemProvider &FSProvider;
+  Context BackgroundContext;
+
+  // index state
+  llvm::Error index(tooling::CompileCommand);
+  FileSymbols IndexedSymbols; // Index contents.
+  using Hash = decltype(llvm::SHA1::hash({}));
+  llvm::StringMap<Hash> FileHash; // Digest of indexed file.
+
+  // queue management
+  using Task = std::function<void()>; // FIXME: use multiple worker threads.
+  void run(); // Main loop executed by Thread. Runs tasks from Queue.
+  void enqueueLocked(tooling::CompileCommand Cmd);
+  std::thread Thread;
+  std::mutex QueueMu;
+  bool HasActiveTask = false;
+  std::condition_variable QueueCV;
+  bool ShouldStop = false;
+  std::deque<Task> Queue;
+};
+
+} // namespace clangd
+} // namespace clang
+
+#endif

clangd/index/Background.cpp

+//===-- Background.cpp - Build an index in a background thread ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "index/Background.h"
+#include "index/MemIndex.h"
+#include "index/Serialization.h"
+#include "index/IndexAction.h"
+#include "Compiler.h"
+#include "ClangdUnit.h"
+#include "Logger.h"
+#include "Trace.h"
+#include "llvm/Support/SHA1.h"
+#include <random>
+
+using namespace llvm;
+namespace clang {
+namespace clangd {
+
+BackgroundIndex::BackgroundIndex(Context BackgroundContext,
+                                 StringRef ResourceDir,
+                                 const FileSystemProvider &FSProvider)
+    : SwapIndex(llvm::make_unique<MemIndex>()), ResourceDir(ResourceDir),
+      FSProvider(FSProvider), BackgroundContext(std::move(BackgroundContext)),
+      Thread([this] { run(); }) {}
+
+BackgroundIndex::~BackgroundIndex() {
+  stop();
+  Thread.join();
+}
+
+void BackgroundIndex::stop() {
+  {
+    std::lock_guard<std::mutex> Lock(QueueMu);
+    ShouldStop = true;
+  }
+  QueueCV.notify_all();
+}
+
+void BackgroundIndex::run() {
+  WithContext Background(std::move(BackgroundContext));
+  while(true) {
+    llvm::Optional<Task> Task;
+    {
+      std::unique_lock<std::mutex> Lock(QueueMu);
+      assert(!HasActiveTask);
+      QueueCV.wait(Lock, [&] { return ShouldStop || !Queue.empty(); });
+      if (ShouldStop) {
+        Queue.clear();
+        QueueCV.notify_all();
+        return;
+      }
+      HasActiveTask = true;
+      Task = std::move(Queue.front());
+      Queue.pop_front();
+    }
+    (*Task)();
+    {
+      std::unique_lock<std::mutex> Lock(QueueMu);
+      HasActiveTask = false;
+    }
+    QueueCV.notify_all();
+  }
+}
+
+void BackgroundIndex::blockUntilIdleForTest() {
+  std::unique_lock<std::mutex> Lock(QueueMu);
+  QueueCV.wait(Lock, [&] { return Queue.empty() && !HasActiveTask; });
+}
+
+void BackgroundIndex::enqueue(StringRef Directory,
+                              tooling::CompileCommand Cmd) {
+  std::lock_guard<std::mutex> Lock(QueueMu);
+  enqueueLocked(std::move(Cmd));
+}
+
+void BackgroundIndex::enqueueAll(StringRef Directory,
+                                 const tooling::CompilationDatabase &CDB) {
+  trace::Span Tracer("BackgroundIndexEnqueueCDB");
+  // FIXME: this function may be slow. Perhaps enqueue a task to re-read the CDB
+  // from disk and enqueue the commands asynchronously?
+  auto Cmds = CDB.getAllCompileCommands();
+  SPAN_ATTACH(Tracer, "commands", int64_t(Cmds.size()));
+  std::mt19937 Generator(std::random_device{}());
+  std::shuffle(Cmds.begin(), Cmds.end(), Generator);
+  log("Enqueueing {0} commands for indexing from {1}", Cmds.size(), Directory);
+  {
+    std::lock_guard<std::mutex> Lock(QueueMu);
+    for (auto &Cmd : Cmds)
+      enqueueLocked(std::move(Cmd));
+  }
+  QueueCV.notify_all();
+}
+
+void BackgroundIndex::enqueueLocked(tooling::CompileCommand Cmd) {
+  Queue.push_back(Bind(
+      [this](tooling::CompileCommand Cmd) {
+        std::string Filename = Cmd.Filename;
+        Cmd.CommandLine.push_back("-resource-dir=" + ResourceDir);
+        if (auto Error = index(std::move(Cmd)))
+          log("Indexing {0} failed: {1}", Filename, std::move(Error));
+      },
+      std::move(Cmd)));
+}
+
+llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd) {
+  trace::Span Tracer("BackgroundIndex");
+  SPAN_ATTACH(Tracer, "file", Cmd.Filename);
+  SmallString<128> AbsolutePath;
+  if (llvm::sys::path::is_absolute(Cmd.Filename)) {
+    AbsolutePath = Cmd.Filename;
+  } else {
+    AbsolutePath = Cmd.Directory;
+    llvm::sys::path::append(AbsolutePath, Cmd.Filename);
+  }
+
+  auto FS = FSProvider.getFileSystem();
+  auto Buf = FS->getBufferForFile(AbsolutePath);
+  if (!Buf)
+    return errorCodeToError(Buf.getError());
+  StringRef Contents = Buf->get()->getBuffer();
+  auto Hash = SHA1::hash({(const uint8_t *)Contents.data(), Contents.size()});
+
+  if (FileHash.lookup(AbsolutePath) == Hash) {
+    vlog("No need to index {0}, already up to date", AbsolutePath);
+    return Error::success();
+  }
+
+  log("Indexing {0}", Cmd.Filename, toHex(Hash));
+  ParseInputs Inputs;
+  Inputs.FS = std::move(FS);
+  Inputs.FS->setCurrentWorkingDirectory(Cmd.Directory);
+  Inputs.CompileCommand = std::move(Cmd);
+  auto CI = buildCompilerInvocation(Inputs);
+  if (!CI)
+    return createStringError(llvm::inconvertibleErrorCode(),
+                             "Couldn't build compiler invocation");
+  IgnoreDiagnostics IgnoreDiags;
+  auto Clang = prepareCompilerInstance(
+      std::move(CI), /*Preamble=*/nullptr, std::move(*Buf),
+      std::make_shared<PCHContainerOperations>(), Inputs.FS, IgnoreDiags);
+  if (!Clang)
+    return createStringError(llvm::inconvertibleErrorCode(),
+                             "Couldn't build compiler instance");
+
+  SymbolCollector::Options IndexOpts;
+  SymbolSlab Symbols;
+  RefSlab Refs;
+  IndexFileIn IndexData;
+  auto Action = createStaticIndexingAction(
+      IndexOpts, [&](SymbolSlab S) { Symbols = std::move(S); },
+      [&](RefSlab R) { Refs = std::move(R); });
+
+  // We're going to run clang here, and it could potentially crash.
+  // We could use CrashRecoveryContext to try to make indexing crashes nonfatal,
+  // but the leaky "recovery" is pretty scary too in a long-running process.
+  // If crashes are a real problem, maybe we should fork a child process.
+
+  const FrontendInputFile &Input = Clang->getFrontendOpts().Inputs.front();
+  if (!Action->BeginSourceFile(*Clang, Input))
+    return createStringError(llvm::inconvertibleErrorCode(),
+                             "BeginSourceFile() failed");
+  if (!Action->Execute())
+    return createStringError(llvm::inconvertibleErrorCode(),
+                             "Execute() failed");
+  Action->EndSourceFile();
+
+  log("Indexed {0} ({1} symbols, {2} refs)", Inputs.CompileCommand.Filename,
+      Symbols.size(), Refs.size());
+  SPAN_ATTACH(Tracer, "symbols", int(Symbols.size()));
+  SPAN_ATTACH(Tracer, "refs", int(Refs.size()));
+  // FIXME: partition the symbols by file rather than TU, to avoid duplication.
+  IndexedSymbols.update(AbsolutePath,
+                        llvm::make_unique<SymbolSlab>(std::move(Symbols)),
+                        llvm::make_unique<RefSlab>(std::move(Refs)));
+  FileHash[AbsolutePath] = Hash;
+
+  // FIXME: this should rebuild once-in-a-while, not after every file.
+  //       At that point we should use Dex, too.
+  vlog("Rebuilding automatic index");
+  reset(IndexedSymbols.buildMemIndex());
+  return Error::success();
+}
+
+} // namespace clangd
+} // namespace clang

clangd/tool/ClangdMain.cpp

static llvm::cl::opt<Path> IndexFile(
     "index-file",
     llvm::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."),
     llvm::cl::init(""), llvm::cl::Hidden);
 
+static llvm::cl::opt<bool> AutoIndex(
+    "auto-index",
+    llvm::cl::desc(
+        "Build a full index for the codebase containing edited files. "
+        "Indexing will occur in the background. "
+        "This option is still experimental, as the indexing is inefficient."
+        "Takes precedence over -index-file."),
+    llvm::cl::init(false), 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 "
if (!HeaderInsertionDecorators) {
     CCOpts.IncludeIndicator.Insert.clear();
     CCOpts.IncludeIndicator.NoInsert.clear();
   }
   CCOpts.SpeculativeIndexRequest = Opts.StaticIndex;
   CCOpts.EnableFunctionArgSnippets = EnableFunctionArgSnippets;
   CCOpts.AllScopes = AllScopesCompletion;
 
   // Initialize and run ClangdLSPServer.
-  ClangdLSPServer LSPServer(
-      Out, CCOpts, CompileCommandsDirPath,
-      /*ShouldUseInMemoryCDB=*/CompileArgsFrom == LSPCompileArgs, Opts);
+  ClangdLSPServer LSPServer(Out, CCOpts, CompileCommandsDirPath,
+                            /*ShouldUseInMemoryCDB=*/CompileArgsFrom ==
+                                LSPCompileArgs,
+                            AutoIndex, 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/BackgroundIndexTests.cpp

+#include "index/Background.h"
+#include "SyncAPI.h"
+#include "TestFS.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using testing::ElementsAre;
+
+namespace clang {
+namespace clangd {
+
+MATCHER_P(Named, N, "") { return arg.Name == N; }
+
+TEST(BackgroundIndexTest, IndexesOneFile) {
+  MockFSProvider FS;
+  FS.Files[testPath("root/A.h")] = "void NAME(){}";
+  FS.Files[testPath("root/A.cc")] = "#include \"A.h\"";
+  BackgroundIndex Idx(Context::empty(), "", FS);
+  tooling::CompileCommand Cmd;
+  Cmd.Filename = testPath("root/A.cc");
+  Cmd.Directory = testPath("root");
+  Cmd.CommandLine = {"clang++", "-DNAME=foo", testPath("root/A.cc")};
+  Idx.enqueue(testPath("root"), std::move(Cmd));
+
+  Idx.blockUntilIdleForTest();
+  EXPECT_THAT(runFuzzyFind(Idx, "f"), ElementsAre(Named("foo")));
+}
+
+} // namespace clangd
+} // namespace clang

unittests/clangd/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   support
   )
 
 get_filename_component(CLANGD_SOURCE_DIR
   ${CMAKE_CURRENT_SOURCE_DIR}/../../clangd REALPATH)
 include_directories(
   ${CLANGD_SOURCE_DIR}
   )
 
 add_extra_unittest(ClangdTests
   Annotations.cpp
+  BackgroundIndexTests.cpp
   CancellationTests.cpp
   ClangdTests.cpp
   ClangdUnitTests.cpp
   CodeCompleteTests.cpp
   CodeCompletionStringsTests.cpp
   ContextTests.cpp
   DexTests.cpp
   DraftStoreTests.cpp

unittests/clangd/SyncAPI.h

 // async versions in clangd code.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_SYNCAPI_H
 #define LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_SYNCAPI_H
 
 #include "ClangdServer.h"
-#include <future>
+#include "index/Index.h"
 
 namespace clang {
 namespace clangd {
 
 // Calls addDocument and then blockUntilIdleForTest.
 void runAddDocument(ClangdServer &Server, PathRef File, StringRef Contents,
                     WantDiagnostics WantDiags = WantDiagnostics::Auto);
 

 std::string runDumpAST(ClangdServer &Server, PathRef File);
 
 llvm::Expected<std::vector<SymbolInformation>>
 runWorkspaceSymbols(ClangdServer &Server, StringRef Query, int Limit);
 
 llvm::Expected<std::vector<SymbolInformation>>
 runDocumentSymbols(ClangdServer &Server, PathRef File);
 
+SymbolSlab runFuzzyFind(const SymbolIndex &Index, StringRef Query);
+SymbolSlab runFuzzyFind(const SymbolIndex &Index, const FuzzyFindRequest &Req);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_UNITTESTS_CLANGD_SYNCAPI_H

unittests/clangd/SyncAPI.cpp

 
 llvm::Expected<std::vector<SymbolInformation>>
 runDocumentSymbols(ClangdServer &Server, PathRef File) {
   llvm::Optional<llvm::Expected<std::vector<SymbolInformation>>> Result;
   Server.documentSymbols(File, capture(Result));
   return std::move(*Result);
 }
 
+SymbolSlab runFuzzyFind(const SymbolIndex &Index, StringRef Query) {
+  FuzzyFindRequest Req;
+  Req.Query = Query;
+  return runFuzzyFind(Index, Req);
+}
+
+SymbolSlab runFuzzyFind(const SymbolIndex &Index, const FuzzyFindRequest &Req) {
+  SymbolSlab::Builder Builder;
+  Index.fuzzyFind(Req, [&](const Symbol& Sym) {
+    Builder.insert(Sym);
+  });
+  return std::move(Builder).build();
+}
+
 } // namespace clangd
 } // namespace clang