[clangd] Store preamble macros in dynamic index.

[ioeric]

Summary

Pros:
o Loading macros from preamble for every completion is slow (see profile).
o Calculating macro USR is also slow (see profile).
o Sema can provide a lot of macro completion results (e.g. when filter is empty,
60k for some large TUs!).

Cons:
o Slight memory increase in dynamic index (~1%).
o Some extra work during preamble build (should be fine as preamble build and
indexAST is way slower).

Before:

After:

[ioeric]

• minor cleanup

[ilya-biryukov]

~1% increase in memory usage seems totally fine. Actually surprised it's that small.
Overall LG, just a single comment about extra copying. Thanks for the change, looks like a great improvement!

clangd/index/FileIndex.cpp

84

Why make an extra copy of the symbols? Why not add macros to the same builder used in collector?

[ioeric]

clangd/index/FileIndex.cpp

84

index::indexTopLevelDecls will re-initialize the collector. This is safe with the current implementation, but I can imagine it goes wrong when we do more cleanup in the initialization.

[ilya-biryukov]

clangd/index/FileIndex.cpp

84

Sorry, missed the comment about it.
And if we do this after indexTopLevelDecls, than we'll be calling after the finish call. Sigh...

Doing an extra copy of the symbols here is wasteful and makes the code more complicated than it should be.

We have alternatives that could fix this:

1. Move IndexMacro logic into index::indexTopLevelDecls
2. Move macro collection to SymbolCollector::finish()
3. Extract a function that creates a symbol for macro definition, so we don't need to call handleMacroOccurence and add can add extra macro symbols after SymbolCollector finishes.

(1) seems to be the cleanest option, WDYT?

[ioeric]

• Move macro collection to indexTopLevelDecls.

[ioeric]

In D52078#1234667, @ilya-biryukov wrote:

~1% increase in memory usage seems totally fine. Actually surprised it's that small.

Tested on a larger file: it's ~5% for ClangdServer.cpp. I think it's still worth it for the speedup.

clangd/index/FileIndex.cpp

84

(1) sounds good. D52098

[sammccall]

This is definitely the right thing to do, thanks for finding it!
I've got a long comment about how everything used to be simpler in the good old days :-) I'm itching to refactor a bit, but land this first.

clangd/index/FileIndex.cpp

34

I don't understand this change. Don't we also want this only if IndexMacros is true?
(It's possible it doesn't make a difference due to implementation details but it seems worth being clear here)

clangd/index/FileIndex.h

93–94

I'm concerned about the proliferation of parameters here. (Not new with this patch, it's been a continuous process - the first version had one input and one output!)
It's heading in the direction of being a catch-all "collect some data from an AST" function, at which point each caller has to think hard about every option and we're going to end up with bugs.
(For example: TestTU::index() passes "false" for IndexMacros. It seems to me maybe it should be "true". But it's really hard to tell.)
That's also pretty similar to the mission of SymbolCollector itself, so we're going to get some confusion there.

As far as I can tell, there's now two types of indexing that we do:

• preamble indexing: we look at all decls, and only index those outside the main file. We index macros. We don't collect references. Inputs are ASTContext and PP.
• mainfile-style indexing: we look only at top-level decls in the main file. We don't index macros. We collect references from the main file. Inputs are ParsedAST.

This really looks like it should be 2 functions with 2 and 1 parameters, rather than 1 function with 4.
Then callers will have two styles of indexing (with names!) to choose between, rather than being required to design their own. And we can get rid of the "is this a main-file index?" hacks in the implementation.

Sorry for jumping on you here, this change isn't any worse than the three previous patches that added knobs to this function.
This doesn't need to be addressed in this patch - could be before or after, and I'm happy to take this on myself. But I think we shouldn't kick this can down the road too much further, eventually we end up with APIs like clang :-)

[ioeric]

clangd/index/FileIndex.h

93–94

I'm definitely on board with this and happy to do the refactoring before landing this patch, to break API just once ;) Just to clarify my understanding before doing that, do we also want to split FileIndex::update into updatePreamble and updateMain? And the new indexAST will be indexMain and indexPreamble?

[ioeric]

• merge with origin/master

[sammccall]

Something not listed in cons: because macros aren't namespaced and we don't have lots of signals, they can be really spammy.
Potentially, offering macros that aren't in the TU could be a loss even if it's a win for other types of signals.

We could always e.g. postfilter index macro results using the include structure of the preamble, so no concern for this patch, just something to think about for the followup.

We also need to make sure that we're not indexing/serving header guards as code completions (e.g. if SemaCodeComplete is currently taking care of this)

clangd/index/FileIndex.cpp

58

nit: please clang-format

[ioeric]

In D52078#1238301, @sammccall wrote:

Something not listed in cons: because macros aren't namespaced and we don't have lots of signals, they can be really spammy.
Potentially, offering macros that aren't in the TU could be a loss even if it's a win for other types of signals.

Aren't they already spammy from Sema? Sema can provide thousands of macros in the TU.

We penalize quality of macro symbols in the global index. Maybe we can do the same thing for dynamic index?

We could always e.g. postfilter index macro results using the include structure of the preamble, so no concern for this patch, just something to think about for the followup.

Sounds good.

We also need to make sure that we're not indexing/serving header guards as code completions (e.g. if SemaCodeComplete is currently taking care of this)

These symbols are already filtered out in SymbolCollector.

[cfe-commits]

• msg-7222-125.txt159 BDownload

clangd/ClangdServer.cpp

public:
   // Index() presents a merged view of the supplied main-file and preamble ASTs.
   std::unique_ptr<ParsingCallbacks> makeUpdateCallbacks() {
     struct CB : public ParsingCallbacks {
       CB(ClangdServer::DynamicIndex *This) : This(This) {}
       DynamicIndex *This;
 
       void onPreambleAST(PathRef Path, ASTContext &Ctx,
                          std::shared_ptr<clang::Preprocessor> PP) override {
-        This->PreambleIdx.update(Path, &Ctx, std::move(PP));
+        This->PreambleIdx.update(Path, &Ctx, std::move(PP),
+                                 /*IndexMacros=*/true);
       }
 
       void onMainAST(PathRef Path, ParsedAST &AST) override {
-        This->MainFileIdx.update(Path, &AST.getASTContext(),
-                                 AST.getPreprocessorPtr(),
-                                 AST.getLocalTopLevelDecls());
+        This->MainFileIdx.update(
+            Path, &AST.getASTContext(), AST.getPreprocessorPtr(),
+            /*IndexMacros=*/false, AST.getLocalTopLevelDecls());
       }
     };
     return llvm::make_unique<CB>(this);
   };
 
 private:
   // Contains information from each file's preamble only.
   // These are large, but update fairly infrequently (preambles are stable).

clangd/index/FileIndex.h

public:
   /// If URISchemes is empty, the default schemes in SymbolCollector will be
   /// used.
   FileIndex(std::vector<std::string> URISchemes = {});
 
   /// Update symbols in \p Path with symbols in \p AST. If \p AST is
   /// nullptr, this removes all symbols in the file.
   /// If \p AST is not null, \p PP cannot be null and it should be the
   /// preprocessor that was used to build \p AST.
+  /// If \p IndexMacros is true, also collect macro definitions in \p PP.
   /// If \p TopLevelDecls is set, only these decls are indexed. Otherwise, all
   /// top level decls obtained from \p AST are indexed.
   void
   update(PathRef Path, ASTContext *AST, std::shared_ptr<Preprocessor> PP,
+         bool IndexMacros = false,
          llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls = llvm::None);
 
 private:
   // Only update() should swap the index.
   using SwapIndex::reset;
 
   FileSymbols FSymbols;
   std::vector<std::string> URISchemes;
 };
 
 /// Retrieves symbols and refs in \p AST.
 /// Exposed to assist in unit tests.
 /// If URISchemes is empty, the default schemes in SymbolCollector will be used.
 /// If \p TopLevelDecls is set, only these decls are indexed. Otherwise, all top
 /// level decls obtained from \p AST are indexed.
+/// If \p IndexMacros is true, also collect macro definitions in \p PP.
 std::pair<SymbolSlab, RefSlab>
 indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
+         bool IndexMacros = false,
          llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls = llvm::None,
          llvm::ArrayRef<std::string> URISchemes = {});
 
 } // 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 "Logger.h"
 #include "SymbolCollector.h"
+#include "index/Index.h"
+#include "clang/Index/IndexSymbol.h"
 #include "clang/Index/IndexingAction.h"
+#include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/Preprocessor.h"
 
 namespace clang {
 namespace clangd {
 
 std::pair<SymbolSlab, RefSlab>
-indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
+indexAST(ASTContext &AST, std::shared_ptr<Preprocessor> PP, bool IndexMacros,
          llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls,
          llvm::ArrayRef<std::string> URISchemes) {
   SymbolCollector::Options CollectorOpts;
   // FIXME(ioeric): we might also want to collect include headers. We would need
   // to make sure all includes are canonicalized (with CanonicalIncludes), which
   // is not trivial given the current way of collecting symbols: we only have
   // AST at this point, but we also need preprocessor callbacks (e.g.
   // CommentHandler for IWYU pragma) to canonicalize includes.
   CollectorOpts.CollectIncludePath = false;
   CollectorOpts.CountReferences = false;
+  CollectorOpts.CollectMacro = true;
   if (!URISchemes.empty())
     CollectorOpts.URISchemes = URISchemes;
   CollectorOpts.Origin = SymbolOrigin::Dynamic;
 
   index::IndexingOptions IndexOpts;
   // We only need declarations, because we don't count references.
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::DeclarationsOnly;
   IndexOpts.IndexFunctionLocals = false;
 
   std::vector<Decl *> DeclsToIndex;
   if (TopLevelDecls)
     DeclsToIndex.assign(TopLevelDecls->begin(), TopLevelDecls->end());
   else
     DeclsToIndex.assign(AST.getTranslationUnitDecl()->decls().begin(),
                         AST.getTranslationUnitDecl()->decls().end());
 
   // We only collect refs when indexing main AST.
   // FIXME: this is a hacky way to detect whether we are indexing preamble AST
   // or main AST, we should make it explicitly.
   bool IsIndexMainAST = TopLevelDecls.hasValue();
   if (IsIndexMainAST)
     CollectorOpts.RefFilter = RefKind::All;
 
   SymbolCollector Collector(std::move(CollectorOpts));
   Collector.setPreprocessor(PP);
+  Collector.initialize(AST);
+
+  SymbolSlab Macros;
+  if (IndexMacros) {
+    // FIXME: also collect macro references?
+    for (const auto &M : PP->macros())
+      if (MacroDirective *MD = M.second.getLatest())
+        Collector.handleMacroOccurence(
+            M.first, MD->getMacroInfo(),
+            static_cast<unsigned>(index::SymbolRole::Definition),
+            MD->getLocation());
+    Macros = Collector.takeSymbols();
+  }
+  // Collector will be re-initialized.
   index::indexTopLevelDecls(AST, DeclsToIndex, Collector, IndexOpts);
 
   const auto &SM = AST.getSourceManager();
   const auto *MainFileEntry = SM.getFileEntryForID(SM.getMainFileID());
   std::string FileName = MainFileEntry ? MainFileEntry->getName() : "";
 
-  auto Syms = Collector.takeSymbols();
+  SymbolSlab::Builder Merged;
+  for (const auto &Macro : Macros)
+    Merged.insert(Macro);
+  for (const auto &Sym : Collector.takeSymbols())
+    Merged.insert(Sym);
+  auto Syms = std::move(Merged).build();
+
   auto Refs = Collector.takeRefs();
   vlog("index {0}AST for {1}: \n"
        "  symbol slab: {2} symbols, {3} bytes\n"
        "  ref slab: {4} symbols, {5} bytes",
        IsIndexMainAST ? "Main" : "Preamble", FileName, Syms.size(),
        Syms.bytes(), Refs.size(), Refs.bytes());
   return {std::move(Syms), std::move(Refs)};
 }
std::unique_ptr<SymbolIndex> FileSymbols::buildMemIndex() {
   return llvm::make_unique<MemIndex>(
       llvm::make_pointee_range(AllSymbols), std::move(AllRefs),
       std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs),
                       std::move(RefsStorage)),
       StorageSize);
 }
 
 void FileIndex::update(PathRef Path, ASTContext *AST,
-                       std::shared_ptr<Preprocessor> PP,
+                       std::shared_ptr<Preprocessor> PP, bool IndexMacros,
                        llvm::Optional<llvm::ArrayRef<Decl *>> TopLevelDecls) {
   if (!AST) {
     FSymbols.update(Path, nullptr, nullptr);
   } else {
     assert(PP);
-    auto Contents = indexAST(*AST, PP, TopLevelDecls, URISchemes);
+    auto Contents = indexAST(*AST, PP, IndexMacros, TopLevelDecls, URISchemes);
     FSymbols.update(Path,
                     llvm::make_unique<SymbolSlab>(std::move(Contents.first)),
                     llvm::make_unique<RefSlab>(std::move(Contents.second)));
   }
   reset(FSymbols.buildMemIndex());
 }
 
 } // namespace clangd
 } // namespace clang

unittests/clangd/CodeCompleteTests.cpp

TEST(CompletionTest, Filter) {
   // Macros require  prefix match.
   EXPECT_THAT(completions(Body + "int main() { C^ }").Completions,
               AllOf(Has("Car"), Not(Has("MotorCar"))));
 }
 
 void TestAfterDotCompletion(clangd::CodeCompleteOptions Opts) {
   auto Results = completions(
       R"cpp(
-      #define MACRO X
-
       int global_var;
 
       int global_func();
 
+      // Make sure this is not in preamble.
+      #define MACRO X
+
       struct GlobalClass {};
 
       struct ClassWithMembers {
         /// Doc for method.
         int method();
 
         int field;
       private:
void TestAfterDotCompletion(clangd::CodeCompleteOptions Opts) {
   // Check documentation.
   EXPECT_IFF(Opts.IncludeComments, Results.Completions,
              Contains(IsDocumented()));
 }
 
 void TestGlobalScopeCompletion(clangd::CodeCompleteOptions Opts) {
   auto Results = completions(
       R"cpp(
-      #define MACRO X
-
       int global_var;
       int global_func();
 
+      // Make sure this is not in preamble.
+      #define MACRO X
+
       struct GlobalClass {};
 
       struct ClassWithMembers {
         /// Doc for method.
         int method();
       };
 
       int test() {
EXPECT_THAT(
       Results.Completions,
       HasSubsequence(Named("a"),
                      SnippetSuffix("(${1:int i}, ${2:const float f})")));
 }
 
 TEST(CompletionTest, Kinds) {
   auto Results = completions(
       R"cpp(
-          #define MACRO X
           int variable;
           struct Struct {};
           int function();
+          // make sure MACRO is not included in preamble.
+          #define MACRO 10
           int X = ^
       )cpp",
       {func("indexFunction"), var("indexVariable"), cls("indexClass")});
   EXPECT_THAT(Results.Completions,
               AllOf(Has("function", CompletionItemKind::Function),
                     Has("variable", CompletionItemKind::Variable),
                     Has("int", CompletionItemKind::Keyword),
                     Has("Struct", CompletionItemKind::Class),
TEST(CompletionTest, MergeMacrosFromIndexAndSema) {
   Sym.ID = SymbolID("c:foo.cpp@8@macro@Clangd_Macro_Test");
   Sym.SymInfo.Kind = index::SymbolKind::Macro;
   Sym.Flags |= Symbol::IndexedForCodeCompletion;
   EXPECT_THAT(completions("#define Clangd_Macro_Test\nClangd_Macro_T^", {Sym})
                   .Completions,
               UnorderedElementsAre(Named("Clangd_Macro_Test")));
 }
 
+TEST(CompletionTest, NoMacroFromPreambleIfIndexIsSet) {
+  auto Results = completions(
+      R"cpp(
+          #define CLANGD_PREAMBLE x
+          int x = 0;
+          #define CLANGD_MAIN x
+          void f() { CLANGD_^ }
+      )cpp",
+      {func("CLANGD_INDEX")});
+  // Index is overriden in code completion options, so the preamble symbol is
+  // not seen.
+  EXPECT_THAT(Results.Completions, UnorderedElementsAre(Named("CLANGD_MAIN"),
+                                                        Named("CLANGD_INDEX")));
+}
+
 TEST(CompletionTest, DeprecatedResults) {
   std::string Body = R"cpp(
     void TestClangd();
     void TestClangc() __attribute__((deprecated("", "")));
   )cpp";
 
   EXPECT_THAT(
       completions(Body + "int main() { TestClang^ }").Completions,

unittests/clangd/FileIndexTests.cpp

 #include "Annotations.h"
 #include "ClangdUnit.h"
 #include "TestFS.h"
 #include "TestTU.h"
 #include "gmock/gmock.h"
 #include "index/FileIndex.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PCHContainerOperations.h"
+#include "clang/Index/IndexSymbol.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "gtest/gtest.h"
 
 using testing::_;
 using testing::AllOf;
 using testing::ElementsAre;
 using testing::Pair;

 
 // Adds Basename.cpp, which includes Basename.h, which contains Code.
 void update(FileIndex &M, llvm::StringRef Basename, llvm::StringRef Code) {
   TestTU File;
   File.Filename = (Basename + ".cpp").str();
   File.HeaderFilename = (Basename + ".h").str();
   File.HeaderCode = Code;
   auto AST = File.build();
-  M.update(File.Filename, &AST.getASTContext(), AST.getPreprocessorPtr());
+  M.update(File.Filename, &AST.getASTContext(), AST.getPreprocessorPtr(),
+           /*IndexMacros=*/true);
 }
 
 TEST(FileIndexTest, CustomizedURIScheme) {
   FileIndex M({"unittest"});
   update(M, "f", "class string {};");
 
   FuzzyFindRequest Req;
   Req.Query = "";
TEST(FileIndexTest, Refs) {
   FileIndex Index(/*URISchemes*/ {"unittest"});
   // Add test.cc
   TestTU Test;
   Test.HeaderCode = HeaderCode;
   Test.Code = MainCode.code();
   Test.Filename = "test.cc";
   auto AST = Test.build();
   Index.update(Test.Filename, &AST.getASTContext(), AST.getPreprocessorPtr(),
-               AST.getLocalTopLevelDecls());
+               /*IndexMacros=*/false, AST.getLocalTopLevelDecls());
   // Add test2.cc
   TestTU Test2;
   Test2.HeaderCode = HeaderCode;
   Test2.Code = MainCode.code();
   Test2.Filename = "test2.cc";
   AST = Test2.build();
   Index.update(Test2.Filename, &AST.getASTContext(), AST.getPreprocessorPtr(),
-               AST.getLocalTopLevelDecls());
+               /*IndexMacros=*/false, AST.getLocalTopLevelDecls());
 
   EXPECT_THAT(getRefs(Index, Foo.ID),
               RefsAre({AllOf(RefRange(MainCode.range("foo")),
                              FileURI("unittest:///test.cc")),
                        AllOf(RefRange(MainCode.range("foo")),
                              FileURI("unittest:///test2.cc"))}));
 }
 
+TEST(FileIndexTest, CollectMacros) {
+  FileIndex M;
+  update(M, "f", "#define CLANGD 1");
+
+  FuzzyFindRequest Req;
+  Req.Query = "";
+  bool SeenSymbol = false;
+  M.fuzzyFind(Req, [&](const Symbol &Sym) {
+    EXPECT_EQ(Sym.Name, "CLANGD");
+    EXPECT_EQ(Sym.SymInfo.Kind, index::SymbolKind::Macro);
+    SeenSymbol = true;
+  });
+  EXPECT_TRUE(SeenSymbol);
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

unittests/clangd/IndexTests.cpp

TEST(MergeIndexTest, Refs) {
   // Build dynamic index for test.cc.
   Annotations Test1Code(R"(class $Foo[[Foo]];)");
   TestTU Test;
   Test.HeaderCode = HeaderCode;
   Test.Code = Test1Code.code();
   Test.Filename = "test.cc";
   auto AST = Test.build();
   Dyn.update(Test.Filename, &AST.getASTContext(), AST.getPreprocessorPtr(),
-             AST.getLocalTopLevelDecls());
+             /*IndexMacros=*/false, AST.getLocalTopLevelDecls());
 
   // Build static index for test.cc.
   Test.HeaderCode = HeaderCode;
   Test.Code = "// static\nclass Foo {};";
   Test.Filename = "test.cc";
   auto StaticAST = Test.build();
   // Add stale refs for test.cc.
   StaticIndex.update(Test.Filename, &StaticAST.getASTContext(),
                      StaticAST.getPreprocessorPtr(),
-                     StaticAST.getLocalTopLevelDecls());
+                     /*IndexMacros=*/false, StaticAST.getLocalTopLevelDecls());
 
   // Add refs for test2.cc
   Annotations Test2Code(R"(class $Foo[[Foo]] {};)");
   TestTU Test2;
   Test2.HeaderCode = HeaderCode;
   Test2.Code = Test2Code.code();
   Test2.Filename = "test2.cc";
   StaticAST = Test2.build();
   StaticIndex.update(Test2.Filename, &StaticAST.getASTContext(),
                      StaticAST.getPreprocessorPtr(),
-                     StaticAST.getLocalTopLevelDecls());
+                     /*IndexMacros=*/false, StaticAST.getLocalTopLevelDecls());
 
   RefsRequest Request;
   Request.IDs = {Foo.ID};
   RefSlab::Builder Results;
   MergedIndex->refs(Request, [&](const Ref &O) { Results.insert(Foo.ID, O); });
 
   EXPECT_THAT(
       std::move(Results).build(),

unittests/clangd/TestTU.cpp

 SymbolSlab TestTU::headerSymbols() const {
   auto AST = build();
   return indexAST(AST.getASTContext(), AST.getPreprocessorPtr()).first;
 }
 
 std::unique_ptr<SymbolIndex> TestTU::index() const {
   auto AST = build();
   auto Content = indexAST(AST.getASTContext(), AST.getPreprocessorPtr(),
-                          AST.getLocalTopLevelDecls());
+                          /*IndexMacros=*/false, AST.getLocalTopLevelDecls());
   return MemIndex::build(std::move(Content.first), std::move(Content.second));
 }
 
 const Symbol &findSymbol(const SymbolSlab &Slab, llvm::StringRef QName) {
   const Symbol *Result = nullptr;
   for (const Symbol &S : Slab) {
     if (QName != (S.Scope + S.Name).str())
       continue;