[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 ↗

(On Diff #168847)

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 ↗

(On Diff #168847)

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 ↗

(On Diff #168847)

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 ↗

(On Diff #168847)

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

52

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

15

Also add a test for enqueueAll with multiple TUs ?

[sammccall]

unittests/clangd/BackgroundIndexTests.cpp

15

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

15

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

15

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

15

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

15

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

15

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 ↗

(On Diff #169694)

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/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/FileIndex.h"
+#include "index/Index.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;
+  unsigned NumActiveTasks = 0; // Only idle when queue is empty *and* no tasks.
+  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 "ClangdUnit.h"
+#include "Compiler.h"
+#include "Logger.h"
+#include "Trace.h"
+#include "index/IndexAction.h"
+#include "index/MemIndex.h"
+#include "index/Serialization.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);
+      QueueCV.wait(Lock, [&] { return ShouldStop || !Queue.empty(); });
+      if (ShouldStop) {
+        Queue.clear();
+        QueueCV.notify_all();
+        return;
+      }
+      ++NumActiveTasks;
+      Task = std::move(Queue.front());
+      Queue.pop_front();
+    }
+    (*Task)();
+    {
+      std::unique_lock<std::mutex> Lock(QueueMu);
+      assert(NumActiveTasks > 0 && "before decrementing");
+      --NumActiveTasks;
+    }
+    QueueCV.notify_all();
+  }
+}
+
+void BackgroundIndex::blockUntilIdleForTest() {
+  std::unique_lock<std::mutex> Lock(QueueMu);
+  QueueCV.wait(Lock, [&] { return Queue.empty() && NumActiveTasks == 0; });
+}
+
+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

unittests/clangd/BackgroundIndexTests.cpp

+#include "SyncAPI.h"
+#include "TestFS.h"
+#include "index/Background.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using testing::UnorderedElementsAre;
+
+namespace clang {
+namespace clangd {
+
+MATCHER_P(Named, N, "") { return arg.Name == N; }
+
+TEST(BackgroundIndexTest, IndexTwoFiles) {
+  MockFSProvider FS;
+  // a.h yields different symbols when included by A.cc vs B.cc.
+  // Currently we store symbols for each TU, so we get both.
+  FS.Files[testPath("root/A.h")] = "void a_h(); void NAME(){}";
+  FS.Files[testPath("root/A.cc")] = "#include \"A.h\"";
+  FS.Files[testPath("root/B.cc")] = "#define NAME bar\n#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"), Cmd);
+  Cmd.CommandLine.back() = Cmd.Filename = testPath("root/B.cc");
+  Idx.enqueue(testPath("root"), Cmd);
+
+  Idx.blockUntilIdleForTest();
+  EXPECT_THAT(runFuzzyFind(Idx, ""),
+              UnorderedElementsAre(Named("a_h"), Named("foo"), Named("bar")));
+}
+
+} // 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