[clangd] Dont index deeply nested symbols

[kadircet]

Summary

This is fix for some timeouts and OOM problems faced while indexing an
auto-generated file with thousands of nested lambdas.

[kadircet]

• Revert unrelated changes in tests

[sammccall]

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

143

I'd consider pulling the logic out into isDeeplyNested(unsigned MaxDepth=10) in AST.h, to keep this readable & policy-oriented and as we may well want to apply this in other places where we use SymbolCollector (or other traversals)

[kadircet]

• Move depth check into a helper and add tests for it.

clang-tools-extra/clangd/AST.h

 /// x has type `undeduced auto`, and external linkage.
 /// If we compute linkage at this point, the external linkage will be cached.
 ///
 /// After code completion the initializer is attached, and x has a lambda type.
 /// This means x has "unique external" linkage. If we computed linkage above,
 /// the cached value is incorrect. (clang catches this with an assertion).
 bool hasUnstableLinkage(const Decl *D);
 
+/// Checks whether \p D is more than \p MaxDepth away from translation unit
+/// scope.
+/// This is useful for limiting traversals to keep operation latencies
+/// reasonable.
+bool isDeeplyNested(const Decl *D, unsigned MaxDepth = 10);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_AST_H_

clang-tools-extra/clangd/AST.cpp

 
 bool hasUnstableLinkage(const Decl *D) {
   // Linkage of a ValueDecl depends on the type.
   // If that's not deduced yet, deducing it may change the linkage.
   auto *VD = llvm::dyn_cast_or_null<ValueDecl>(D);
   return VD && !VD->getType().isNull() && VD->getType()->isUndeducedType();
 }
 
+bool isDeeplyNested(const Decl *D, unsigned MaxDepth) {
+  size_t ContextDepth = 0;
+  for (auto *Ctx = D->getDeclContext(); Ctx && !Ctx->isTranslationUnit();
+       Ctx = Ctx->getParent()) {
+    if (++ContextDepth == MaxDepth)
+      return true;
+  }
+  return false;
+}
 } // namespace clangd
 } // namespace clang

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

 //===--- IndexAction.cpp -----------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "IndexAction.h"
+#include "AST.h"
 #include "Headers.h"
 #include "index/Relation.h"
 #include "index/SymbolOrigin.h"
 #include "support/Logger.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/MultiplexConsumer.h"
 #include "clang/Index/IndexingAction.h"
 #include "clang/Index/IndexingOptions.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/STLExtras.h"
+#include <cstddef>
 #include <functional>
 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace clangd {
 namespace {
 
IndexAction(std::shared_ptr<SymbolCollector> C,
               std::function<void(RelationSlab)> RelationsCallback,
               std::function<void(IncludeGraph)> IncludeGraphCallback)
       : SymbolsCallback(SymbolsCallback), RefsCallback(RefsCallback),
         RelationsCallback(RelationsCallback),
         IncludeGraphCallback(IncludeGraphCallback), Collector(C),
         Includes(std::move(Includes)), Opts(Opts),
         PragmaHandler(collectIWYUHeaderMaps(this->Includes.get())) {
     this->Opts.ShouldTraverseDecl = [this](const Decl *D) {
+      // Many operations performed during indexing is linear in terms of depth
+      // of the decl (USR generation, name lookups, figuring out role of a
+      // reference are some examples). Since we index all the decls nested
+      // inside, it becomes quadratic. So we give up on nested symbols.
+      if (isDeeplyNested(D))
+        return false;
       auto &SM = D->getASTContext().getSourceManager();
       auto FID = SM.getFileID(SM.getExpansionLoc(D->getLocation()));
       if (!FID.isValid())
         return true;
       return Collector->shouldIndexFile(FID);
     };
   }
 

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

for (const auto &Case : Cases) {
     ASSERT_EQ(InsertionPoints.size(), Case.Types.size());
     for (size_t I = 0, E = InsertionPoints.size(); I != E; ++I) {
       const auto *DC = InsertionPoints[I];
       EXPECT_EQ(printType(AST.getASTContext().getTypeDeclType(TargetDecl), *DC),
                 Case.Types[I]);
     }
   }
 }
+
+TEST(ClangdAST, IsDeeplyNested) {
+  Annotations Test(
+      R"cpp(
+        namespace ns {
+        class Foo {
+          void bar() {
+            class Bar {};
+          }
+        };
+        })cpp");
+  TestTU TU = TestTU::withCode(Test.code());
+  ParsedAST AST = TU.build();
+
+  EXPECT_TRUE(isDeeplyNested(&findUnqualifiedDecl(AST, "Foo"), /*MaxDepth=*/1));
+  EXPECT_FALSE(
+      isDeeplyNested(&findUnqualifiedDecl(AST, "Foo"), /*MaxDepth=*/2));
+
+  EXPECT_TRUE(isDeeplyNested(&findUnqualifiedDecl(AST, "bar"), /*MaxDepth=*/2));
+  EXPECT_FALSE(
+      isDeeplyNested(&findUnqualifiedDecl(AST, "bar"), /*MaxDepth=*/3));
+
+  EXPECT_TRUE(isDeeplyNested(&findUnqualifiedDecl(AST, "Bar"), /*MaxDepth=*/3));
+  EXPECT_FALSE(
+      isDeeplyNested(&findUnqualifiedDecl(AST, "Bar"), /*MaxDepth=*/4));
+}
 } // namespace
 } // namespace clangd
 } // namespace clang

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

TEST_F(IndexActionTest, SkipFiles) {
   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"));
 }
 
+TEST_F(IndexActionTest, SkipNestedSymbols) {
+  std::string MainFilePath = testPath("main.cpp");
+  addFile(MainFilePath, R"cpp(
+  namespace ns1 {
+  namespace ns2 {
+  namespace ns3 {
+  namespace ns4 {
+  namespace ns5 {
+  namespace ns6 {
+  namespace ns7 {
+  namespace ns8 {
+  namespace ns9 {
+  class Bar {};
+  void foo() {
+    class Baz {};
+  }
+  }
+  }
+  }
+  }
+  }
+  }
+  }
+  }
+  })cpp");
+  IndexFileIn IndexFile = runIndexingAction(MainFilePath, {"-std=c++14"});
+  EXPECT_THAT(*IndexFile.Symbols, testing::Contains(HasName("foo")));
+  EXPECT_THAT(*IndexFile.Symbols, testing::Contains(HasName("Bar")));
+  EXPECT_THAT(*IndexFile.Symbols, Not(testing::Contains(HasName("Baz"))));
+}
 } // namespace
 } // namespace clangd
 } // namespace clang