[clangd] Build in-memory index on symbols in files.

[sammccall]

clangd/index/FileMemIndexManager.h

23 ↗

(On Diff #127075)

Discussed offline a bit:

• FileIndex or PerFileIndex is a great name for this, if it implements Index. So I think it should (and forward to the MemIndex that it owns).
• FileSymbols is mostly useful to implement this, so we could put them in the same header FileIndexand add a comment to that effect.
• What this means for unittest organization - up to you

unittests/clangd/IndexTests.cpp

116

Can you make this build() returning a ParsedAST instead?

It adds a little duplication to the callsite:

M.update("f1", build("f1", "...code..."));

but it makes this a much more "pure" function, and a good candidate for pulling out into a helper for other tests.

[ioeric]

• Address review comments. Merge FileSymbols and tests into FileIndex.

[ioeric]

• Minor cleanup

[sammccall]

I don't see FileSymbols.{h,cpp} being deleted, but maybe I'm bad at reading diffs.

clangd/index/FileIndex.h

9

Add a file-comment about what this is and how it's going to be used?
At the moment almost all the comments are on FileSymbols and implementation-focused, while FileIndex is the interesting class.

58

override

[ioeric]

• Removed unused files and addressed comments.

[ioeric]

In D41276#956513, @sammccall wrote:

I don't see FileSymbols.{h,cpp} being deleted, but maybe I'm bad at reading diffs.

No, I'm bad at creating diffs...

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   JSONExpr.cpp
   JSONRPCDispatcher.cpp
   Logger.cpp
   Protocol.cpp
   ProtocolHandlers.cpp
   Trace.cpp
-  index/FileSymbols.cpp
+  index/FileIndex.cpp
   index/Index.cpp
   index/MemIndex.cpp
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp
 
   LINK_LIBS
   clangAST
   clangBasic

clangd/index/FileIndex.h

+//===--- FileIndex.h - Index for files. ---------------------------- 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_FILEINDEX_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
+
+#include "../ClangdUnit.h"
+#include "../Context.h"
+#include "Index.h"
+#include "MemIndex.h"
+
+namespace clang {
+namespace clangd {
+
+/// \brief A container of Symbols from several source files. It can be updated
+/// at source-file granularity, replacing all symbols from one file with a new
+/// set.
+///
+/// This implements a snapshot semantics for symbols in a file. Each update to a
+/// file will create a new snapshot for all symbols in the file. Snapshots are
+/// managed with shared pointers that are shared between this class and the
+/// users. For each file, this class only stores a pointer pointing to the
+/// newest snapshot, and an outdated snapshot is deleted by the last owner of
+/// the snapshot, either this class or the symbol index.
+///
+/// The snapshot semantics keeps critical sections minimal since we only need
+/// locking when we swap or obtain refereces to snapshots.
+class FileSymbols {
+public:
+  /// \brief Updates all symbols in a file. If \p Slab is nullptr, symbols for
+  /// \p Path will be removed.
+  void update(PathRef Path, std::unique_ptr<SymbolSlab> Slab);
+
+  // The shared_ptr keeps the symbols alive
+  std::shared_ptr<std::vector<const Symbol *>> allSymbols();
+
+private:
+  mutable std::mutex Mutex;
+
+  /// \brief Stores the latest snapshots for all active files.
+  llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSlabs;
+};
+
+/// \brief This manages symbls from files and an in-memory index on all symbols.
+class FileIndex : public SymbolIndex {
+public:
+  /// \brief Update symbols in \p Path with symbols in \p AST. If \p AST is
+  /// nullptr, this removes all symbols from \p Path.
+  void update(Context &Ctx, PathRef Path, ParsedAST *AST);
+
+  bool fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
+                 std::function<void(const Symbol &)> Callback) const;
+
+private:
+  FileSymbols FSymbols;
+  MemIndex Index;
+};
+
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H

clangd/index/FileIndex.cpp

+//===--- FileIndex.cpp - Indexes for files. ------------------------ C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "FileIndex.h"
+#include "SymbolCollector.h"
+#include "clang/Index/IndexingAction.h"
+
+namespace clang {
+namespace clangd {
+namespace {
+
+/// Retrieves namespace and class level symbols in \p Decls.
+std::unique_ptr<SymbolSlab> indexAST(ASTContext &Ctx,
+                                     llvm::ArrayRef<const Decl *> Decls) {
+  auto Collector = std::make_shared<SymbolCollector>();
+  index::IndexingOptions IndexOpts;
+  IndexOpts.SystemSymbolFilter =
+      index::IndexingOptions::SystemSymbolFilterKind::All;
+  IndexOpts.IndexFunctionLocals = false;
+
+  index::indexTopLevelDecls(Ctx, Decls, Collector, IndexOpts);
+  auto Symbols = llvm::make_unique<SymbolSlab>();
+  *Symbols = Collector->takeSymbols();
+  return Symbols;
+}
+
+} // namespace
+
+void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Slab) {
+  std::lock_guard<std::mutex> Lock(Mutex);
+  if (!Slab)
+    FileToSlabs.erase(Path);
+  else
+    FileToSlabs[Path] = std::shared_ptr<SymbolSlab>(Slab.release());
+}
+
+std::shared_ptr<std::vector<const Symbol *>> FileSymbols::allSymbols() {
+  // The snapshot manages life time of symbol slabs and provides pointers of all
+  // symbols in all slabs.
+  struct Snapshot {
+    std::vector<const Symbol *> Pointers;
+    std::vector<std::shared_ptr<SymbolSlab>> KeepAlive;
+  };
+  auto Snap = std::make_shared<Snapshot>();
+  {
+    std::lock_guard<std::mutex> Lock(Mutex);
+
+    for (const auto &FileAndSlab : FileToSlabs) {
+      Snap->KeepAlive.push_back(FileAndSlab.second);
+      for (const auto &Iter : *FileAndSlab.second)
+        Snap->Pointers.push_back(&Iter.second);
+    }
+  }
+  auto *Pointers = &Snap->Pointers;
+  // Use aliasing constructor to keep the snapshot alive along with the
+  // pointers.
+  return {std::move(Snap), Pointers};
+}
+
+void FileIndex::update(Context &Ctx, PathRef Path, ParsedAST *AST) {
+  if (!AST) {
+    FSymbols.update(Path, nullptr);
+  } else {
+    auto Slab = indexAST(AST->getASTContext(), AST->getTopLevelDecls());
+    FSymbols.update(Path, std::move(Slab));
+  }
+  auto Symbols = FSymbols.allSymbols();
+  Index.build(std::move(Symbols));
+}
+
+bool FileIndex::fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
+                          std::function<void(const Symbol &)> Callback) const {
+  return Index.fuzzyFind(Ctx, Req, std::move(Callback));
+}
+
+} // 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
   ClangdTests.cpp
   CodeCompleteTests.cpp
   ContextTests.cpp
-  FileSymbolsTests.cpp
+  FileIndexTests.cpp
   FuzzyMatchTests.cpp
   IndexTests.cpp
   JSONExprTests.cpp
   TestFS.cpp
   TraceTests.cpp
   SymbolCollectorTests.cpp
   )
 

unittests/clangd/FileIndexTests.cpp

+//===-- FileIndexTests.cpp  ---------------------------*- C++ -*-----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "index/FileIndex.h"
+#include "clang/Frontend/CompilerInvocation.h"
+#include "clang/Frontend/PCHContainerOperations.h"
+#include "clang/Frontend/Utils.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using testing::UnorderedElementsAre;
+
+namespace clang {
+namespace clangd {
+
+namespace {
+
+Symbol symbol(llvm::StringRef ID) {
+  Symbol Sym;
+  Sym.ID = SymbolID(ID);
+  Sym.QualifiedName = ID;
+  return Sym;
+}
+
+void addNumSymbolsToSlab(int Begin, int End, SymbolSlab *Slab) {
+  for (int i = Begin; i <= End; i++)
+    Slab->insert(symbol(std::to_string(i)));
+}
+
+std::vector<std::string>
+getSymbolNames(const std::vector<const Symbol *> &Symbols) {
+  std::vector<std::string> Names;
+  for (const Symbol *Sym : Symbols)
+    Names.push_back(Sym->QualifiedName);
+  return Names;
+}
+
+TEST(FileSymbolsTest, UpdateAndGet) {
+  FileSymbols FS;
+  EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
+
+  auto Slab = llvm::make_unique<SymbolSlab>();
+  addNumSymbolsToSlab(1, 3, Slab.get());
+
+  FS.update("f1", std::move(Slab));
+
+  EXPECT_THAT(getSymbolNames(*FS.allSymbols()),
+              UnorderedElementsAre("1", "2", "3"));
+}
+
+TEST(FileSymbolsTest, Overlap) {
+  FileSymbols FS;
+
+  auto Slab = llvm::make_unique<SymbolSlab>();
+  addNumSymbolsToSlab(1, 3, Slab.get());
+
+  FS.update("f1", std::move(Slab));
+
+  Slab = llvm::make_unique<SymbolSlab>();
+  addNumSymbolsToSlab(3, 5, Slab.get());
+
+  FS.update("f2", std::move(Slab));
+
+  EXPECT_THAT(getSymbolNames(*FS.allSymbols()),
+              UnorderedElementsAre("1", "2", "3", "3", "4", "5"));
+}
+
+TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
+  FileSymbols FS;
+
+  auto Slab = llvm::make_unique<SymbolSlab>();
+  addNumSymbolsToSlab(1, 3, Slab.get());
+
+  FS.update("f1", std::move(Slab));
+
+  auto Symbols = FS.allSymbols();
+  EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
+
+  FS.update("f1", nullptr);
+  EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
+
+  EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
+}
+
+std::vector<std::string> match(const SymbolIndex &I,
+                               const FuzzyFindRequest &Req) {
+  std::vector<std::string> Matches;
+  auto Ctx = Context::empty();
+  I.fuzzyFind(Ctx, Req,
+              [&](const Symbol &Sym) { Matches.push_back(Sym.QualifiedName); });
+  return Matches;
+}
+
+/// Create an ParsedAST for \p Code. Returns None if \p Code is empty.
+llvm::Optional<ParsedAST> build(std::string Path, llvm::StringRef Code) {
+  Context Ctx = Context::empty();
+  if (Code.empty())
+    return llvm::None;
+  const char *Args[] = {"clang", "-xc++", Path.c_str()};
+
+  auto CI = createInvocationFromCommandLine(Args);
+
+  auto Buf = llvm::MemoryBuffer::getMemBuffer(Code);
+  auto AST = ParsedAST::Build(Ctx, std::move(CI), nullptr, std::move(Buf),
+                              std::make_shared<PCHContainerOperations>(),
+                              vfs::getRealFileSystem());
+  assert(AST.hasValue());
+  return std::move(*AST);
+}
+
+TEST(FileIndexTest, IndexAST) {
+  FileIndex M;
+  auto Ctx = Context::empty();
+  M.update(
+      Ctx, "f1",
+      build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
+
+  FuzzyFindRequest Req;
+  Req.Query = "ns::";
+  EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::f", "ns::X"));
+}
+
+TEST(FileIndexTest, NoLocal) {
+  FileIndex M;
+  auto Ctx = Context::empty();
+  M.update(
+      Ctx, "f1",
+      build("f1", "namespace ns { void f() { int local = 0; } class X {}; }")
+          .getPointer());
+
+  FuzzyFindRequest Req;
+  Req.Query = "";
+  EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns", "ns::f", "ns::X"));
+}
+
+TEST(FileIndexTest, IndexMultiASTAndDeduplicate) {
+  FileIndex M;
+  auto Ctx = Context::empty();
+  M.update(
+      Ctx, "f1",
+      build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
+  M.update(
+      Ctx, "f2",
+      build("f2", "namespace ns { void ff() {} class X {}; }").getPointer());
+
+  FuzzyFindRequest Req;
+  Req.Query = "ns::";
+  EXPECT_THAT(match(M, Req),
+              UnorderedElementsAre("ns::f", "ns::X", "ns::ff"));
+}
+
+TEST(FileIndexTest, RemoveAST) {
+  FileIndex M;
+  auto Ctx = Context::empty();
+  M.update(
+      Ctx, "f1",
+      build("f1", "namespace ns { void f() {} class X {}; }").getPointer());
+
+  FuzzyFindRequest Req;
+  Req.Query = "ns::";
+  EXPECT_THAT(match(M, Req), UnorderedElementsAre("ns::f", "ns::X"));
+
+  M.update(Ctx, "f1", nullptr);
+  EXPECT_THAT(match(M, Req), UnorderedElementsAre());
+}
+
+TEST(FileIndexTest, RemoveNonExisting) {
+  FileIndex M;
+  auto Ctx = Context::empty();
+  M.update(Ctx, "no", nullptr);
+  EXPECT_THAT(match(M, FuzzyFindRequest()), UnorderedElementsAre());
+}
+
+TEST(FileIndexTest, ClassMembers) {
+  FileIndex M;
+  auto Ctx = Context::empty();
+  M.update(Ctx, "f1",
+           build("f1", "class X { static int m1; int m2;};").getPointer());
+
+  FuzzyFindRequest Req;
+  Req.Query = "";
+  EXPECT_THAT(match(M, Req), UnorderedElementsAre("X", "X::m1", "X::m2"));
+}
+
+} // namespace
+} // namespace clangd
+} // namespace clang
+

unittests/clangd/FileSymbolsTests.cpp

-//===-- FileSymbolsTests.cpp  -------------------------*- C++ -*-----------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "index/FileSymbols.h"
-#include "gmock/gmock.h"
-#include "gtest/gtest.h"
-
-using testing::UnorderedElementsAre;
-
-namespace clang {
-namespace clangd {
-
-namespace {
-
-Symbol symbol(llvm::StringRef ID) {
-  Symbol Sym;
-  Sym.ID = SymbolID(ID);
-  Sym.QualifiedName = ID;
-  return Sym;
-}
-
-void addNumSymbolsToSlab(int Begin, int End, SymbolSlab *Slab) {
-  for (int i = Begin; i <= End; i++)
-    Slab->insert(symbol(std::to_string(i)));
-}
-
-std::vector<std::string>
-getSymbolNames(const std::vector<const Symbol *> &Symbols) {
-  std::vector<std::string> Names;
-  for (const Symbol *Sym : Symbols)
-    Names.push_back(Sym->QualifiedName);
-  return Names;
-}
-
-TEST(FileSymbolsTest, UpdateAndGet) {
-  FileSymbols FS;
-  EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
-
-  auto Slab = llvm::make_unique<SymbolSlab>();
-  addNumSymbolsToSlab(1, 3, Slab.get());
-
-  FS.update("f1", std::move(Slab));
-
-  EXPECT_THAT(getSymbolNames(*FS.allSymbols()),
-              UnorderedElementsAre("1", "2", "3"));
-}
-
-TEST(FileSymbolsTest, Overlap) {
-  FileSymbols FS;
-
-  auto Slab = llvm::make_unique<SymbolSlab>();
-  addNumSymbolsToSlab(1, 3, Slab.get());
-
-  FS.update("f1", std::move(Slab));
-
-  Slab = llvm::make_unique<SymbolSlab>();
-  addNumSymbolsToSlab(3, 5, Slab.get());
-
-  FS.update("f2", std::move(Slab));
-
-  EXPECT_THAT(getSymbolNames(*FS.allSymbols()),
-              UnorderedElementsAre("1", "2", "3", "3", "4", "5"));
-}
-
-TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
-  FileSymbols FS;
-
-  auto Slab = llvm::make_unique<SymbolSlab>();
-  addNumSymbolsToSlab(1, 3, Slab.get());
-
-  FS.update("f1", std::move(Slab));
-
-  auto Symbols = FS.allSymbols();
-  EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
-
-  FS.update("f1", nullptr);
-  EXPECT_THAT(getSymbolNames(*FS.allSymbols()), UnorderedElementsAre());
-
-  EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
-}
-
-} // namespace
-} // namespace clangd
-} // namespace clang
-

unittests/clangd/IndexTests.cpp

 //===-- IndexTests.cpp  -------------------------------*- C++ -*-----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "index/Index.h"
 #include "index/MemIndex.h"
+#include "llvm/ADT/Optional.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::UnorderedElementsAre;
 
 namespace clang {
 namespace clangd {
 
TEST(MemIndexTest, MemIndexLimitedNumMatches) {
   Req.Query = "5";
   Req.MaxCandidateCount = 3;
   auto Matches = match(I, Req);
   EXPECT_EQ(Matches.size(), Req.MaxCandidateCount);
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang