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

Reviewers: sammccall

Reviewed By: sammccall

Subscribers: klimek, mgorny, ilya-biryukov, cfe-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/clang-tools-extra/trunk@320807 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 260 insertions, 102 deletions

diff --git a/clangd/CMakeLists.txt b/clangd/CMakeLists.txt
index 6fe77c11..98a468ff 100644
--- a/clangd/CMakeLists.txt
+++ b/clangd/CMakeLists.txt
@@ -19,7 +19,7 @@ add_clang_library(clangDaemon
   Protocol.cpp
   ProtocolHandlers.cpp
   Trace.cpp
-  index/FileSymbols.cpp
+  index/FileIndex.cpp
   index/Index.cpp
   index/MemIndex.cpp
   index/SymbolCollector.cpp
diff --git a/clangd/index/FileSymbols.cpp b/clangd/index/FileIndex.cpp
index aad56dd7..1e0016a2 100644
--- a/clangd/index/FileSymbols.cpp
+++ b/clangd/index/FileIndex.cpp
@@ -1,4 +1,4 @@
-//===--- FileSymbols.cpp - Symbols from files. ------------------*- C++-*-===//
+//===--- FileIndex.cpp - Indexes for files. ------------------------ C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,11 +7,30 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "FileSymbols.h"
+#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);
@@ -44,5 +63,21 @@ std::shared_ptr<std::vector<const Symbol *>> FileSymbols::allSymbols() {
   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
diff --git a/clangd/index/FileSymbols.h b/clangd/index/FileIndex.h
index 5c3adc72..e904b8d1 100644
--- a/clangd/index/FileSymbols.h
+++ b/clangd/index/FileIndex.h
@@ -1,4 +1,4 @@
-//===--- FileSymbols.h - Symbols from files. ---------------------*- C++-*-===//
+//===--- FileIndex.h - Index for files. ---------------------------- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -6,14 +6,20 @@
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
+// FileIndex implements SymbolIndex for symbols from a set of files. Symbols are
+// maintained at source-file granuality (e.g. with ASTs), and files can be
+// updated dynamically.
+//
+//===---------------------------------------------------------------------===//
 
-#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILESYMBOLS_H
-#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILESYMBOLS_H
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
 
-#include "../Path.h"
+#include "../ClangdUnit.h"
+#include "../Context.h"
 #include "Index.h"
-#include "llvm/ADT/StringMap.h"
-#include <mutex>
+#include "MemIndex.h"
 
 namespace clang {
 namespace clangd {
@@ -47,7 +53,22 @@ private:
   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 in the file
+  void update(Context &Ctx, PathRef Path, ParsedAST *AST);
+
+  bool fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
+                 std::function<void(const Symbol &)> Callback) const override;
+
+private:
+  FileSymbols FSymbols;
+  MemIndex Index;
+};
+
 } // namespace clangd
 } // namespace clang
 
-#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILESYMBOLS_H
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H
diff --git a/unittests/clangd/CMakeLists.txt b/unittests/clangd/CMakeLists.txt
index 718b7ade..2c514e96 100644
--- a/unittests/clangd/CMakeLists.txt
+++ b/unittests/clangd/CMakeLists.txt
@@ -12,7 +12,7 @@ add_extra_unittest(ClangdTests
   ClangdTests.cpp
   CodeCompleteTests.cpp
   ContextTests.cpp
-  FileSymbolsTests.cpp
+  FileIndexTests.cpp
   FuzzyMatchTests.cpp
   IndexTests.cpp
   JSONExprTests.cpp
diff --git a/unittests/clangd/FileIndexTests.cpp b/unittests/clangd/FileIndexTests.cpp
new file mode 100644
index 00000000..c79de441
--- /dev/null
+++ b/unittests/clangd/FileIndexTests.cpp
@@ -0,0 +1,193 @@
+//===-- 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
diff --git a/unittests/clangd/FileSymbolsTests.cpp b/unittests/clangd/FileSymbolsTests.cpp
deleted file mode 100644
index f559b0f7..00000000
--- a/unittests/clangd/FileSymbolsTests.cpp
+++ /dev/null
@@ -1,91 +0,0 @@
-//===-- 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
-