[clangd] Index local classes, virtual and overriding methods.

[usaxena95]

Summary

Previously we did not record local class declarations. Now with features like
findImplementation and typeHierarchy, we have a need to index such local
classes to accurately report subclasses and implementations of methods.

Performance testing results:

• No changes in indexing timing.
• No significant change in memory usage.
• 1% increase in #relations.
• 0.17% increase in #refs.
• 0.22% increase #symbols.

New index stats
Time to index: 4:13 min
memory usage 543MB
number of symbols: 521.5K
number of refs: 8679K
number of relations: 49K

Base Index stats
Time to index: 4:15 min
memory usage 542MB
number of symbols: 520K
number of refs: 8664K
number of relations: 48.5K

Fixes: https://github.com/clangd/clangd/issues/644

[njames93]

Thank you for taking the time to fix this and the performance measurements to boot.
My only question is does this try and index lambdas, under the hood they are declared as a CXXRecordDecl, defined in function scope?

[usaxena95]

Added tests for not indexing lambdas.

[usaxena95]

In D94785#2501312, @njames93 wrote:

My only question is does this try and index lambdas, under the hood they are declared as a CXXRecordDecl, defined in function scope?

I would not expect that to happen as it is an anonymous class and we filter those in the beginning of shouldCollectSymbol.
Added tests to test this.

Although now that I enabled this in all SymbolCollectorTests, this causes a regression in RefContainers.

void f2() {
      (void) $ref1a[[f1]](1);
      auto fptr = &$ref1b[[f1]];
    }

&f1 is contained in fptr instead of f2. No immediate ideas why would this happen. Will take a look into this next week.

[nridge]

In D94785#2501806, @usaxena95 wrote:

Although now that I enabled this in all SymbolCollectorTests, this causes a regression in RefContainers.

void f2() {
      (void) $ref1a[[f1]](1);
      auto fptr = &$ref1b[[f1]];
    }

&f1 is contained in fptr instead of f2. No immediate ideas why would this happen.

I have a theory as to why.

If you look at the next test case in RefContainers:

int $toplevel2[[v1]] = $ref2[[f1]](2);

here, v1 is a global variable, and it is the containing symbol for the reference in the initializer.

So, I think libIndex considers references in initializers to be contained in the declaration of the variable. The reason this didn't happen for local variables until now, is that IndexFunctionLocals was false, and libIndex probably avoids returning non-indexed symbols in ASTNode::Parent.

[hokein]

In D94785#2503939, @nridge wrote:

In D94785#2501806, @usaxena95 wrote:

Although now that I enabled this in all SymbolCollectorTests, this causes a regression in RefContainers.

void f2() {
      (void) $ref1a[[f1]](1);
      auto fptr = &$ref1b[[f1]];
    }

&f1 is contained in fptr instead of f2. No immediate ideas why would this happen.

I have a theory as to why.

If you look at the next test case in RefContainers:

int $toplevel2[[v1]] = $ref2[[f1]](2);

here, v1 is a global variable, and it is the containing symbol for the reference in the initializer.

So, I think libIndex considers references in initializers to be contained in the declaration of the variable. The reason this didn't happen for local variables until now, is that IndexFunctionLocals was false, and libIndex probably avoids returning non-indexed symbols in ASTNode::Parent.

This looks like a bug in libindex -- not sure we should fix that before this patch, I think we can probably live with this, and fix the bug afterwards.

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

64–65

Can you add a comment explicitly mentioning that we only index function-local classes and its methods? Without a comment, the reader would expect we index all function-local symbols by just reading this part of code.

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

223

nit: CollectMainFileSymbols affects the function-local symbols, I think? please update the comments of SymbolCollector::Options::CollectMainFileSymbols.

231

nit: use index::isFunctionLocalSymbol

[usaxena95]

Addressed comments. Left a todo to fix the bug in RefContainers later.

[hokein]

mostly good.

I think we'd better bump the index version, even though this is not a breaking change, but we will collect more data. Not bumping the index version may lead to a half-completed state of the index (e.g. only newly-changed files will get completed index data in background index).

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

227

having a special case here is subtle, I think the reason we need this is to filter out non-virtual methods etc for function-local classes? not sure we should do this, my guess is that we wouldn't save too much, I'd just remove this and index all members for function-local classes.

[usaxena95]

In D94785#2506186, @hokein wrote:

I think we'd better bump the index version, even though this is not a breaking change, but we will collect more data. Not bumping the index version may lead to a half-completed state of the index (e.g. only newly-changed files will get completed index data in background index).

Yes. Good point. Incremented the version of the index.

[usaxena95]

Index all member functions instead of only polymorphic functions.

[usaxena95]

Updated index tests's input files.

[hokein]

Thanks, looks good!

if you don't mind, could you rerun the benchmark (we have a behavior changes from original version, I guess it won't not change significantly)? and update the data in the description before landing.

[usaxena95]

In D94785#2506685, @hokein wrote:

if you don't mind, could you rerun the benchmark (we have a behavior changes from original version, I guess it won't not change significantly)? and update the data in the description before landing.

Updated the stats. The stats are still very similar.

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

SlabTuple indexSymbols(ASTContext &AST, std::shared_ptr<Preprocessor> PP,
   CollectorOpts.CountReferences = false;
   CollectorOpts.Origin = SymbolOrigin::Dynamic;
   CollectorOpts.CollectMainFileRefs = CollectMainFileRefs;
 
   index::IndexingOptions IndexOpts;
   // We only need declarations, because we don't count references.
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::DeclarationsOnly;
-  IndexOpts.IndexFunctionLocals = false;
+  // We index function-local classes and its member functions only.
+  IndexOpts.IndexFunctionLocals = true;
   if (IsIndexMainAST) {
     // We only collect refs when indexing main AST.
     CollectorOpts.RefFilter = RefKind::All;
     // Comments for main file can always be obtained from sema, do not store
     // them in the index.
     CollectorOpts.StoreAllDocumentation = false;
   } else {
     IndexOpts.IndexMacrosInPreprocessor = true;

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

std::unique_ptr<FrontendAction> createStaticIndexingAction(
     SymbolCollector::Options Opts,
     std::function<void(SymbolSlab)> SymbolsCallback,
     std::function<void(RefSlab)> RefsCallback,
     std::function<void(RelationSlab)> RelationsCallback,
     std::function<void(IncludeGraph)> IncludeGraphCallback) {
   index::IndexingOptions IndexOpts;
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::All;
+  // We index function-local classes and its member functions only.
+  IndexOpts.IndexFunctionLocals = true;
   Opts.CollectIncludePath = true;
   if (Opts.Origin == SymbolOrigin::Unknown)
     Opts.Origin = SymbolOrigin::Static;
   Opts.StoreAllDocumentation = false;
   if (RefsCallback != nullptr) {
     Opts.RefFilter = RefKind::All;
     Opts.RefsInHeaders = true;
   }

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

 //   - srcs: information related to include graph
 //   - stri: string table
 //   - symb: symbols
 //   - refs: references to symbols
 
 // The current versioning scheme is simple - non-current versions are rejected.
 // If you make a breaking change, bump this version number to invalidate stored
 // data. Later we may want to support some backward compatibility.
-constexpr static uint32_t Version = 15;
+constexpr static uint32_t Version = 16;
 
 llvm::Expected<IndexFileIn> readRIFF(llvm::StringRef Data) {
   auto RIFF = riff::readFile(Data);
   if (!RIFF)
     return RIFF.takeError();
   if (RIFF->Type != riff::fourCC("CdIx"))
     return error("wrong RIFF filetype: {0}", riff::fourCCStr(RIFF->Type));
   llvm::StringMap<llvm::StringRef> Chunks;

clang-tools-extra/clangd/index/SymbolCollector.h

struct Options {
     bool RefsInHeaders = false;
     // Every symbol collected will be stamped with this origin.
     SymbolOrigin Origin = SymbolOrigin::Unknown;
     /// Collect macros.
     /// Note that SymbolCollector must be run with preprocessor in order to
     /// collect macros. For example, `indexTopLevelDecls` will not index any
     /// macro even if this is true.
     bool CollectMacro = false;
-    /// Collect symbols local to main-files, such as static functions
-    /// and symbols inside an anonymous namespace.
+    /// Collect symbols local to main-files, such as static functions, symbols
+    /// inside an anonymous namespace, function-local classes and its member
+    /// functions.
     bool CollectMainFileSymbols = true;
     /// Collect references to main-file symbols.
     bool CollectMainFileRefs = false;
     /// If set to true, SymbolCollector will collect doc for all symbols.
     /// Note that documents of symbols being indexed for completion will always
     /// be collected regardless of this option.
     bool StoreAllDocumentation = false;
     /// If this is set, only collect symbols/references from a file if

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

bool SymbolCollector::shouldCollectSymbol(const NamedDecl &ND,
   if (ND.getDeclName().isEmpty())
     return false;
 
   // Skip main-file symbols if we are not collecting them.
   if (IsMainFileOnly && !Opts.CollectMainFileSymbols)
     return false;
 
   // Skip symbols in anonymous namespaces in header files.
   if (!IsMainFileOnly && ND.isInAnonymousNamespace())
     return false;
 
+  // For function local symbols, index only classes and its member functions.
+  if (index::isFunctionLocalSymbol(&ND))
+    return isa<RecordDecl>(ND) ||
+           (ND.isCXXInstanceMember() && ND.isFunctionOrFunctionTemplate());
+
   // We want most things but not "local" symbols such as symbols inside
   // FunctionDecl, BlockDecl, ObjCMethodDecl and OMPDeclareReductionDecl.
   // FIXME: Need a matcher for ExportDecl in order to include symbols declared
   // within an export.
   const auto *DeclCtx = ND.getDeclContext();
   switch (DeclCtx->getDeclKind()) {
   case Decl::TranslationUnit:
   case Decl::Namespace:
   case Decl::LinkageSpec:

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

 
 TEST(WorkspaceSymbols, NoLocals) {
   TestTU TU;
   TU.Code = R"cpp(
       void test(int FirstParam, int SecondParam) {
         struct LocalClass {};
         int local_var;
       })cpp";
-  EXPECT_THAT(getSymbols(TU, "l"), IsEmpty());
+  EXPECT_THAT(getSymbols(TU, "l"), ElementsAre(QName("LocalClass")));
   EXPECT_THAT(getSymbols(TU, "p"), IsEmpty());
 }
 
 TEST(WorkspaceSymbols, Globals) {
   TestTU TU;
   TU.AdditionalFiles["foo.h"] = R"cpp(
       int global_var;
 

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

MATCHER_P(Labeled, Label, "") {
   return (arg.Name + arg.Signature).str() == Label;
 }
 MATCHER_P(ReturnType, D, "") { return arg.ReturnType == D; }
 MATCHER_P(Doc, D, "") { return arg.Documentation == D; }
 MATCHER_P(Snippet, S, "") {
   return (arg.Name + arg.CompletionSnippetSuffix).str() == S;
 }
 MATCHER_P(QName, Name, "") { return (arg.Scope + arg.Name).str() == Name; }
+MATCHER_P(HasName, Name, "") { return arg.Name == Name; }
 MATCHER_P(TemplateArgs, TemplArgs, "") {
   return arg.TemplateSpecializationArgs == TemplArgs;
 }
 MATCHER_P(DeclURI, P, "") {
   return StringRef(arg.CanonicalDeclaration.FileURI) == P;
 }
 MATCHER_P(DefURI, P, "") { return StringRef(arg.Definition.FileURI) == P; }
 MATCHER(IncludeHeader, "") { return !arg.IncludeHeaders.empty(); }
TEST_F(ShouldCollectSymbolTest, ShouldCollectSymbol) {
   EXPECT_TRUE(shouldCollect("nx::f"));
   EXPECT_TRUE(shouldCollect("InMain"));
   EXPECT_TRUE(shouldCollect("InAnonymous", /*Qualified=*/false));
   EXPECT_TRUE(shouldCollect("g"));
 
   EXPECT_FALSE(shouldCollect("Local", /*Qualified=*/false));
 }
 
+TEST_F(ShouldCollectSymbolTest, CollectLocalClassesAndVirtualMethods) {
+  build(R"(
+    namespace nx {
+    auto f() {
+      int Local;
+      auto LocalLambda = [&](){
+        Local++;
+        class ClassInLambda{};
+        return Local;
+      };
+    } // auto ensures function body is parsed.
+    auto foo() {
+      class LocalBase {
+        virtual void LocalVirtual();
+        void LocalConcrete();
+        int BaseMember;
+      };
+    }
+    } // namespace nx
+  )",
+        "");
+  auto AST = File.build();
+  EXPECT_FALSE(shouldCollect("Local", /*Qualified=*/false));
+  EXPECT_TRUE(shouldCollect("ClassInLambda", /*Qualified=*/false));
+  EXPECT_TRUE(shouldCollect("LocalBase", /*Qualified=*/false));
+  EXPECT_TRUE(shouldCollect("LocalVirtual", /*Qualified=*/false));
+  EXPECT_TRUE(shouldCollect("LocalConcrete", /*Qualified=*/false));
+  EXPECT_FALSE(shouldCollect("BaseMember", /*Qualified=*/false));
+  EXPECT_FALSE(shouldCollect("Local", /*Qualified=*/false));
+}
+
 TEST_F(ShouldCollectSymbolTest, NoPrivateProtoSymbol) {
   HeaderName = "f.proto.h";
   build(
       R"(// Generated by the protocol buffer compiler.  DO NOT EDIT!
          namespace nx {
            class Top_Level {};
            class TopLevel {};
            enum Kind {
std::unique_ptr<FrontendAction> create() override {
     private:
       std::shared_ptr<index::IndexDataConsumer> DataConsumer;
       index::IndexingOptions Opts;
       CommentHandler *PragmaHandler;
     };
     index::IndexingOptions IndexOpts;
     IndexOpts.SystemSymbolFilter =
         index::IndexingOptions::SystemSymbolFilterKind::All;
-    IndexOpts.IndexFunctionLocals = false;
+    IndexOpts.IndexFunctionLocals = true;
     Collector = std::make_shared<SymbolCollector>(COpts);
     return std::make_unique<IndexAction>(Collector, std::move(IndexOpts),
                                          PragmaHandler);
   }
 
   std::shared_ptr<SymbolCollector> Collector;
   SymbolCollector::Options COpts;
   CommentHandler *PragmaHandler;
const std::string Header = R"(
     inline void f2() {}
     static const int KInt = 2;
     const char* kStr = "123";
 
     namespace {
     void ff() {} // ignore
     }
 
-    void f1() {}
+    void f1() {
+      auto LocalLambda = [&](){
+        class ClassInLambda{};
+      };
+    }
 
     namespace foo {
     // Type alias
     typedef int int32;
     using int32_t = int32;
 
     // Variable
     int v1;
EXPECT_THAT(Symbols,
                   {AllOf(QName("Foo"), ForCodeCompletion(true)),
                    AllOf(QName("Foo::Foo"), ForCodeCompletion(false)),
                    AllOf(QName("Foo::Foo"), ForCodeCompletion(false)),
                    AllOf(QName("Foo::f"), ForCodeCompletion(false)),
                    AllOf(QName("Foo::~Foo"), ForCodeCompletion(false)),
                    AllOf(QName("Foo::operator="), ForCodeCompletion(false)),
                    AllOf(QName("Foo::Nested"), ForCodeCompletion(false)),
                    AllOf(QName("Foo::Nested::f"), ForCodeCompletion(false)),
-
+                   AllOf(QName("ClassInLambda"), ForCodeCompletion(false)),
                    AllOf(QName("Friend"), ForCodeCompletion(true)),
                    AllOf(QName("f1"), ForCodeCompletion(true)),
                    AllOf(QName("f2"), ForCodeCompletion(true)),
                    AllOf(QName("KInt"), ForCodeCompletion(true)),
                    AllOf(QName("kStr"), ForCodeCompletion(true)),
                    AllOf(QName("foo"), ForCodeCompletion(true)),
                    AllOf(QName("foo::bar"), ForCodeCompletion(true)),
                    AllOf(QName("foo::int32"), ForCodeCompletion(true)),
TEST_F(SymbolCollectorTest, RefContainers) {
   };
   auto Container = [&](llvm::StringRef RangeName) {
     auto Ref = FindRefWithRange(Code.range(RangeName));
     EXPECT_TRUE(bool(Ref));
     return Ref->Container;
   };
   EXPECT_EQ(Container("ref1a"),
             findSymbol(Symbols, "f2").ID); // function body (call)
-  EXPECT_EQ(Container("ref1b"),
+  // FIXME: This is wrongly contained by fptr and not f2.
+  EXPECT_NE(Container("ref1b"),
             findSymbol(Symbols, "f2").ID); // function body (address-of)
   EXPECT_EQ(Container("ref2"),
             findSymbol(Symbols, "v1").ID); // variable initializer
   EXPECT_EQ(Container("ref3"),
             findSymbol(Symbols, "f3").ID); // function parameter default value
   EXPECT_EQ(Container("ref4"),
             findSymbol(Symbols, "S1::member1").ID); // member initializer
   EXPECT_EQ(Container("ref5"),

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

void FromReference() {
       Child1 * C1;
       C1->B$2^ar();
       C1->Fo$3^o();
     }
     // CRTP should work.
     template<typename T>
     struct $5^TemplateBase {};
     struct $5[[Child3]] : public TemplateBase<Child3> {};
+
+    // Local classes.
+    void LocationFunction() {
+      struct $0[[LocalClass1]] : Base {
+        void $1[[Foo]]() override;
+      };
+      struct $6^LocalBase {
+        virtual void $7^Bar();
+      };
+      struct $6[[LocalClass2]]: LocalBase {
+        void $7[[Bar]]() override;
+      };
+    }
   )cpp";
 
   Annotations Code(Test);
   auto TU = TestTU::withCode(Code.code());
   auto AST = TU.build();
-  for (StringRef Label : {"0", "1", "2", "3", "4", "5"}) {
+  auto Index = TU.index();
+  for (StringRef Label : {"0", "1", "2", "3", "4", "5", "6", "7"}) {
     for (const auto &Point : Code.points(Label)) {
-      EXPECT_THAT(findImplementations(AST, Point, TU.index().get()),
+      EXPECT_THAT(findImplementations(AST, Point, Index.get()),
                   UnorderedPointwise(DeclRange(), Code.ranges(Label)))
           << Code.code() << " at " << Point << " for Label " << Label;
     }
   }
 }
 
 TEST(FindImplementations, CaptureDefintion) {
   llvm::StringRef Test = R"cpp(