[clangd] Don't traverse the AST within uninteresting files during indexing

[sammccall]

Summary

We already skip function bodies from these files while parsing, and drop symbols
found in them. However, traversing their ASTs still takes a substantial amount
of time.

Non-scientific benchmark on my machine:

background-indexing llvm-project (llvm+clang+clang-tools-extra), wall time
before: 7:46
after: 5:13
change: -33%

Indexer.cpp libclang should be updated too, I'm less familiar with that code,
and it's doing tricky things with the ShouldSkipFunctionBody callback, so it
needs to be done separately.

[sammccall]

@adamcz I think this is relevant to your interests maybe? :-)

[kadircet]

clang-tools-extra/clangd/unittests/IndexActionTests.cpp

22

nit using ::testing::EndsWith

was this add using tweak ?

261

maybe give the member a different name to distinguish it from the local var in function ?

clang/include/clang/Index/IndexingOptions.h

40

s/references that/references to that

clang/lib/Index/IndexingAction.cpp

142

are we happy with the copy here ?

I am a little uneasy, as these functions can preserve state. Currently the one used in here and the one used in IndexingContext::indexTopLevelDecl are different copies.

Maybe rather progate a null function into the IndexASTConsumer and create this default lambda in there, making use of the function inside IndexingContext::IndexOpts without a copy?

[adamcz]

Correct me if I'm wrong, but this might lead to a file never being updated in the index, even after edit, right?
Let's say you have file a.cpp that includes a.h. a.h has
namespace foo {

#define EXPAND(foo) whatever
#include "b.h"

}
all nodes from b.h will be inside the namespace node in a.h. If a.h did not change, b.h will never be indexed.

It's a corner case, of course, so may the speed gain is worth the cost, but don't we have inline #includes like this even in clang codebase?

[sammccall]

In D80296#2053189, @adamcz wrote:

Correct me if I'm wrong, but this might lead to a file never being updated in the index, even after edit, right?
Let's say you have file a.cpp that includes a.h. a.h has
namespace foo {

#define EXPAND(foo) whatever
#include "b.h"

}
all nodes from b.h will be inside the namespace node in a.h. If a.h did not change, b.h will never be indexed.

Yes, there's some potential regression here. It exists if:

• the including file is unmodified, the included is modified
• the including file defines the top-level decl (e.g. enclosing namespaces), otherwise change has no effect
• the symbols are considered part of the included file for sharding purposes, otherwise this already didn't work. (I think they are in most cases)

I think I'm comfortable throwing this in the "clangd is designed for well-structured codebases" bucket, along with non-self-contained files in other contexts (b.h is necessarily not self-contained here). I'm also comfortable saying tablegen isn't a well-structured part of LLVM :-)
And for preamble index, (which doesn't yet have this optimization) I think that's the end of the story.
However, this being persistently sticky *forever* with the background index does seem pretty horrible. I can't see an elegant fix though, and a 33% speedup for background index is an important win (it's a top clangd complaint).

Any bright ideas? If not, maybe we land this and try to fix it somehow later, or just accept it as one of our speed/accuracy tradeoffs.

clang-tools-extra/clangd/unittests/IndexActionTests.cpp

22

Yes, it was.
I feel a bit silly as I'm well aware of the behaviour here and have argued it's the right thing, and wrote testing::EndsWith inline, extracted it, and didn't check the output (as it was offscreen).

@adamcz FYI
If we see this a lot maybe we should consider something like "if all existing usings in the block are globally qualified...". Current behavior is definitely defensible though.

clang/lib/Index/IndexingAction.cpp

142

are we happy with the copy here ?

Note that we already have a copy: we take IndexingOptions by const ref and createIndexingASTConsumer copies it, including the function. So anything that relies on the identity of the function passed in, or breaks semantics of copying, is busted already.

as for internal state (e.g. a cache)... I'd agree if this were a heavily used library function (find a way to capture by pointer/shared_ptr). But it's not, and neither of the in-tree callers work this way - I'm not sure it's worth spending API complexity on.

Maybe rather progate...

Hmm, I like the idea that these are clearly separate options at the lower internal layer, and that blurs the lines a bit.
(I'd like *more* making them completely the same, but halfway isn't a happy place to be I think)

[sammccall]

Tweak names, style, comments

[adamcz]

I have no objections to landing this as-is, even if it represents a regression for some evil codebases.

A possible solution is to iterate through all the includes in a given file (SourceManager knows that already) and if any of them are outside of preamble, do not use this optimization on that file. Should be easy and, hopefully, fast. Most files are well-behaved and have includes in preamble only, thus the optimization would still kick in most of the time.

clang-tools-extra/clangd/unittests/IndexActionTests.cpp

22

Agreed. I'm starting to think we should have some sort of config file that defines style for the codebase (beyond clang-format config, things like always-use-::-for-using or never-add-using-for-::std) and possibly guess the values, when missing, during background indexing. It could simplify code edits a lot.

[kadircet]

clang/lib/Index/IndexingAction.cpp

142

as for internal state (e.g. a cache)... I'd agree if this were a heavily used library function (find a way to capture by pointer/shared_ptr). But it's not, and neither of the in-tree callers work this way - I'm not sure it's worth spending API complexity on.

SG. I wasn't concerned about the copying but rather lambda invoked in ShouldSkipFunctionBody and ShouldTraverseDecl being different. I agree that preserving internal state is not that important for current in-tree uses, just wanted to make sure the discrepancy didn't go unnoticed :D

clang-tools-extra/clangd/index/IndexAction.cpp

 public:
   IndexAction(std::shared_ptr<SymbolCollector> C,
               std::unique_ptr<CanonicalIncludes> Includes,
               const index::IndexingOptions &Opts,
               std::function<void(SymbolSlab)> SymbolsCallback,
               std::function<void(RefSlab)> RefsCallback,
               std::function<void(RelationSlab)> RelationsCallback,
               std::function<void(IncludeGraph)> IncludeGraphCallback)
-      : SymbolsCallback(SymbolsCallback),
-        RefsCallback(RefsCallback), RelationsCallback(RelationsCallback),
+      : SymbolsCallback(SymbolsCallback), RefsCallback(RefsCallback),
+        RelationsCallback(RelationsCallback),
         IncludeGraphCallback(IncludeGraphCallback), Collector(C),
         Includes(std::move(Includes)), Opts(Opts),
-        PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {}
+        PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {
+    this->Opts.ShouldTraverseDecl = [this](const Decl *D) {
+      auto &SM = D->getASTContext().getSourceManager();
+      auto FID = SM.getFileID(SM.getExpansionLoc(D->getLocation()));
+      if (!FID.isValid())
+        return true;
+      return Collector->shouldIndexFile(FID);
+    };
+  }
 
   std::unique_ptr<ASTConsumer>
   CreateASTConsumer(CompilerInstance &CI, llvm::StringRef InFile) override {
     CI.getPreprocessor().addCommentHandler(PragmaHandler.get());
     Includes->addSystemHeadersMapping(CI.getLangOpts());
     if (IncludeGraphCallback != nullptr)
       CI.getPreprocessor().addPPCallbacks(
           std::make_unique<IncludeGraphCollector>(CI.getSourceManager(), IG));
 
-    return index::createIndexingASTConsumer(
-        Collector, Opts, CI.getPreprocessorPtr(),
-        /*ShouldSkipFunctionBody=*/[this](const Decl *D) {
-          auto &SM = D->getASTContext().getSourceManager();
-          auto FID = SM.getFileID(SM.getExpansionLoc(D->getLocation()));
-          if (!FID.isValid())
-            return false;
-          return !Collector->shouldIndexFile(FID);
-        });
+    return index::createIndexingASTConsumer(Collector, Opts,
+                                            CI.getPreprocessorPtr());
   }
 
   bool BeginInvocation(CompilerInstance &CI) override {
     // We want all comments, not just the doxygen ones.
     CI.getLangOpts().CommentOpts.ParseAllComments = true;
     CI.getLangOpts().RetainCommentsFromSystemHeaders = true;
     // Index the whole file even if there are warnings and -Werror is set.
     // Avoids some analyses too. Set in two places as we're late to the party.

clang-tools-extra/clangd/unittests/IndexActionTests.cpp

 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using ::testing::AllOf;
 using ::testing::ElementsAre;
+using testing::EndsWith;
 using ::testing::Not;
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 using ::testing::UnorderedPointwise;
 
 std::string toUri(llvm::StringRef Path) { return URI::create(Path).toString(); }
 
 MATCHER(IsTU, "") { return arg.Flags & IncludeGraphNode::SourceFlag::IsTU; }
public:
   IndexFileIn
   runIndexingAction(llvm::StringRef MainFilePath,
                     const std::vector<std::string> &ExtraArgs = {}) {
     IndexFileIn IndexFile;
     llvm::IntrusiveRefCntPtr<FileManager> Files(
         new FileManager(FileSystemOptions(), InMemoryFileSystem));
 
     auto Action = createStaticIndexingAction(
-        SymbolCollector::Options(),
-        [&](SymbolSlab S) { IndexFile.Symbols = std::move(S); },
+        Opts, [&](SymbolSlab S) { IndexFile.Symbols = std::move(S); },
         [&](RefSlab R) { IndexFile.Refs = std::move(R); },
         [&](RelationSlab R) { IndexFile.Relations = std::move(R); },
         [&](IncludeGraph IG) { IndexFile.Sources = std::move(IG); });
 
     std::vector<std::string> Args = {"index_action", "-fsyntax-only",
                                      "-xc++",        "-std=c++11",
                                      "-iquote",      testRoot()};
     Args.insert(Args.end(), ExtraArgs.begin(), ExtraArgs.end());
     Args.push_back(std::string(MainFilePath));
 
     tooling::ToolInvocation Invocation(
         Args, std::move(Action), Files.get(),
         std::make_shared<PCHContainerOperations>());
 
     Invocation.run();
 
     checkNodesAreInitialized(IndexFile, FilePaths);
     return IndexFile;
   }
 
   void addFile(llvm::StringRef Path, llvm::StringRef Content) {
     InMemoryFileSystem->addFile(Path, 0,
-                                llvm::MemoryBuffer::getMemBuffer(Content));
+                                llvm::MemoryBuffer::getMemBufferCopy(Content));
     FilePaths.push_back(std::string(Path));
   }
 
 protected:
+  SymbolCollector::Options Opts;
   std::vector<std::string> FilePaths;
   llvm::IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem;
 };
 
 TEST_F(IndexActionTest, CollectIncludeGraph) {
   std::string MainFilePath = testPath("main.cpp");
   std::string MainCode = "#include \"level1.h\"";
   std::string Level1HeaderPath = testPath("level1.h");
TEST_F(IndexActionTest, NoWarnings) {
   // This would cause indexing to stop (if warnings weren't disabled).
   IndexFileIn IndexFile = runIndexingAction(
       MainFilePath, {"-ferror-limit=1", "-Wparentheses", "-Werror"});
   ASSERT_TRUE(IndexFile.Sources);
   ASSERT_NE(0u, IndexFile.Sources->size());
   EXPECT_THAT(*IndexFile.Symbols, ElementsAre(HasName("foo"), HasName("bar")));
 }
 
+TEST_F(IndexActionTest, SkipFiles) {
+  std::string MainFilePath = testPath("main.cpp");
+  addFile(MainFilePath, R"cpp(
+    #include "bad.h"
+    #include "good.h"
+  )cpp");
+  addFile(testPath("good.h"), R"cpp(
+    struct S { int s; };
+    void f1() { S s; }
+    auto unskippable1() { return S(); }
+  )cpp");
+  addFile(testPath("bad.h"), R"cpp(
+    struct T { S s; };
+    void f2() { S s; }
+    auto unskippable2() { return S(); }
+  )cpp");
+  Opts.FileFilter = [](const SourceManager &SM, FileID F) {
+    return !SM.getFileEntryForID(F)->getName().endswith("bad.h");
+  };
+  IndexFileIn IndexFile = runIndexingAction(MainFilePath, {"-std=c++14"});
+  EXPECT_THAT(*IndexFile.Symbols,
+              UnorderedElementsAre(HasName("S"), HasName("s"), HasName("f1"),
+                                   HasName("unskippable1")));
+  for (const auto &Pair : *IndexFile.Refs)
+    for (const auto &Ref : Pair.second)
+      EXPECT_THAT(Ref.Location.FileURI, EndsWith("good.h"));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

clang/include/clang/Index/IndexingAction.h

namespace clang {
   class Decl;
   class FrontendAction;
 
 namespace serialization {
   class ModuleFile;
 }
 
 namespace index {
-  class IndexDataConsumer;
 
 /// Creates an ASTConsumer that indexes all symbols (macros and AST decls).
+std::unique_ptr<ASTConsumer>
+createIndexingASTConsumer(std::shared_ptr<IndexDataConsumer> DataConsumer,
+                          const IndexingOptions &Opts,
+                          std::shared_ptr<Preprocessor> PP);
+
 std::unique_ptr<ASTConsumer> createIndexingASTConsumer(
     std::shared_ptr<IndexDataConsumer> DataConsumer,
     const IndexingOptions &Opts, std::shared_ptr<Preprocessor> PP,
+    // Prefer to set Opts.ShouldTraverseDecl and use the above overload.
+    // This version is only needed if used to *track* function body parsing.
     std::function<bool(const Decl *)> ShouldSkipFunctionBody);
 
-inline std::unique_ptr<ASTConsumer> createIndexingASTConsumer(
-    std::shared_ptr<IndexDataConsumer> DataConsumer,
-    const IndexingOptions &Opts, std::shared_ptr<Preprocessor> PP) {
-  return createIndexingASTConsumer(
-      std::move(DataConsumer), Opts, std::move(PP),
-      /*ShouldSkipFunctionBody=*/[](const Decl *) { return false; });
-}
-
 /// Creates a frontend action that indexes all symbols (macros and AST decls).
 std::unique_ptr<FrontendAction>
 createIndexingAction(std::shared_ptr<IndexDataConsumer> DataConsumer,
                      const IndexingOptions &Opts);
 
 /// Recursively indexes all decls in the AST.
 void indexASTUnit(ASTUnit &Unit, IndexDataConsumer &DataConsumer,
                   IndexingOptions Opts);

clang/include/clang/Index/IndexingOptions.h

struct IndexingOptions {
   bool IndexImplicitInstantiation = false;
   // Whether to index macro definitions in the Preprocesor when preprocessor
   // callback is not available (e.g. after parsing has finished). Note that
   // macro references are not available in Proprocessor.
   bool IndexMacrosInPreprocessor = false;
   // Has no effect if IndexFunctionLocals are false.
   bool IndexParametersInDeclarations = false;
   bool IndexTemplateParameters = false;
+
+  // If set, skip indexing inside some declarations for performance.
+  // This prevents traversal, so skipping a struct means its declaration an
+  // members won't be indexed, but references that struct elsewhere will be.
+  // Currently this is only checked for top-level declarations.
+  std::function<bool(const Decl *)> ShouldTraverseDecl;
 };
 
 } // namespace index
 } // namespace clang
 
 #endif // LLVM_CLANG_INDEX_INDEXINGOPTIONS_H

clang/lib/Index/IndexDecl.cpp

 
 bool IndexingContext::indexTopLevelDecl(const Decl *D) {
   if (D->getLocation().isInvalid())
     return true;
 
   if (isa<ObjCMethodDecl>(D))
     return true; // Wait for the objc container.
 
+  if (IndexOpts.ShouldTraverseDecl && !IndexOpts.ShouldTraverseDecl(D))
+    return true; // skip
+
   return indexDecl(D);
 }
 
 bool IndexingContext::indexDeclGroupRef(DeclGroupRef DG) {
   for (DeclGroupRef::iterator I = DG.begin(), E = DG.end(); I != E; ++I)
     if (!indexTopLevelDecl(*I))
       return false;
   return true;
 }

clang/lib/Index/IndexingAction.cpp

 std::unique_ptr<ASTConsumer> index::createIndexingASTConsumer(
     std::shared_ptr<IndexDataConsumer> DataConsumer,
     const IndexingOptions &Opts, std::shared_ptr<Preprocessor> PP,
     std::function<bool(const Decl *)> ShouldSkipFunctionBody) {
   return std::make_unique<IndexASTConsumer>(DataConsumer, Opts, PP,
                                             ShouldSkipFunctionBody);
 }
 
+std::unique_ptr<ASTConsumer> clang::index::createIndexingASTConsumer(
+    std::shared_ptr<IndexDataConsumer> DataConsumer,
+    const IndexingOptions &Opts, std::shared_ptr<Preprocessor> PP) {
+  std::function<bool(const Decl *)> ShouldSkipFunctionBody = [](const Decl *) {
+    return false;
+  };
+  if (Opts.ShouldTraverseDecl)
+    ShouldSkipFunctionBody =
+        [ShouldTraverseDecl(Opts.ShouldTraverseDecl)](const Decl *D) {
+          return !ShouldTraverseDecl(D);
+        };
+  return createIndexingASTConsumer(std::move(DataConsumer), Opts, std::move(PP),
+                                   std::move(ShouldSkipFunctionBody));
+}
+
 std::unique_ptr<FrontendAction>
 index::createIndexingAction(std::shared_ptr<IndexDataConsumer> DataConsumer,
                             const IndexingOptions &Opts) {
   assert(DataConsumer != nullptr);
   return std::make_unique<IndexAction>(std::move(DataConsumer), Opts);
 }
 
 static bool topLevelDeclVisitor(void *context, const Decl *D) {