[clangd] SymbolCollector support for relations

[nridge]

Summary

The only relation currently collected is RelationBaseOf, because this is
all we need for type hierarchy subtypes. Additional relations can be
collected in the future as the need arises.

This patch builds on D59407 and D62459.

[kadircet]

Can you also add some tests ?

we have some tests in unittests/SymbolCollectorTests.cpp

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

298 ↗

(On Diff #201473)

why do we want to process these relations for references?

426 ↗

(On Diff #201473)

maybe rather check TagDecl to be as generic as possible.

also the check can be inlined since you are not using RD afterwards, i.e

if(!dyn_cast<TagDecl>(&ND))
  return;

431 ↗

(On Diff #201473)

this might get complicated, maybe isolate it to a bool shouldIndexRelation(const Relation&)

434 ↗

(On Diff #201473)

maybe call it Object ?

436 ↗

(On Diff #201473)

why? I believe we have those in the index since rL356125.

even if we don't I believe this part should also be isolated to somehow get canonical version of a given symbol.

441 ↗

(On Diff #201473)

nit: invert the condition to reduce nesting

453 ↗

(On Diff #201473)

I believe subject is ParentID and object is ID in a baseof relation so these should be replaced ?

453 ↗

(On Diff #201473)

also we should generalize this with something like index::applyForEachSymbolRole, which should also get rid of the check at top(shouldIndexRelation)

[nridge]

Addressed most review comments

[nridge]

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

298 ↗

(On Diff #201473)

The RelationBaseOf is not present in the Relations parameter of the handleDeclOccurrence() call for the base class's declaration. It's only present for the specific reference that's in the base-specifier.

436 ↗

(On Diff #201473)

I removed this logic as it no longer seems to be necessary now that we use libIndex's relations support to compute our relations.

453 ↗

(On Diff #201473)

I believe subject is ParentID and object is ID in a baseof relation so these should be replaced ?

The code was functionally correct, but the name ParentID was wrong -- the RelatedSymbol for a BaseOf relation is the child.

Anyways, I'm now calling it ObjectID.

453 ↗

(On Diff #201473)

also we should generalize this with something like index::applyForEachSymbolRole, which should also get rid of the check at top(shouldIndexRelation)

I don't fully understand this suggestion; could you elaborate?

Are you thinking ahead to a future where we want to index additional kinds of relations? Can we refactor things at that time?

[kadircet]

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

441 ↗

(On Diff #202371)

nit: braces

298 ↗

(On Diff #201473)

yeah just checked the indexing code, that's unfortunate :/.

could you add a comment explaining the situation ?

431 ↗

(On Diff #201473)

nit: no need for braces

453 ↗

(On Diff #201473)

yes I was thinking ahead. just wanted to make sure we can add other relation types without changing the logic inside processrelations.

but it is not that important, let's keep it that way, we can refactor it later on.

[nridge]

Address remaining review comments

[kadircet]

LGTM, thanks!

I suppose there are only two patches left now?

• Exposing relations in SymbolIndex.
• Implementing children resolution using that information.

[nridge]

In D62471#1527085, @kadircet wrote:

LGTM, thanks!

Thanks for the reviews so far!

I suppose there are only two patches left now?

• Exposing relations in SymbolIndex.
• Implementing children resolution using that information.

Yup. Coming up in the near future :)

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

handleDeclOccurence(const Decl *D, index::SymbolRoleSet Roles,
                       index::IndexDataConsumer::ASTNodeInfo ASTNode) override;
 
   bool handleMacroOccurence(const IdentifierInfo *Name, const MacroInfo *MI,
                             index::SymbolRoleSet Roles,
                             SourceLocation Loc) override;
 
   SymbolSlab takeSymbols() { return std::move(Symbols).build(); }
   RefSlab takeRefs() { return std::move(Refs).build(); }
+  RelationSlab takeRelations() { return std::move(Relations).build(); }
 
   void finish() override;
 
 private:
   const Symbol *addDeclaration(const NamedDecl &, SymbolID,
                                bool IsMainFileSymbol);
   void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
+  void processRelations(const NamedDecl &ND, const SymbolID &ID,
+                        ArrayRef<index::SymbolRelation> Relations);
 
   llvm::Optional<std::string> getIncludeHeader(llvm::StringRef QName, FileID);
   bool isSelfContainedHeader(FileID);
   // Heuristically headers that only want to be included via an umbrella.
   static bool isDontIncludeMeHeader(llvm::StringRef);
 
   // All Symbols collected from the AST.
   SymbolSlab::Builder Symbols;
   // File IDs for Symbol.IncludeHeaders.
   // The final spelling is calculated in finish().
   llvm::DenseMap<SymbolID, FileID> IncludeFiles;
   void setIncludeLocation(const Symbol &S, SourceLocation);
   // Indexed macros, to be erased if they turned out to be include guards.
   llvm::DenseSet<const IdentifierInfo *> IndexedMacros;
   // All refs collected from the AST.
   // Only symbols declared in preamble (from #include) and referenced from the
   // main file will be included.
   RefSlab::Builder Refs;
+  // All relations collected from the AST.
+  RelationSlab::Builder Relations;
   ASTContext *ASTCtx;
   std::shared_ptr<Preprocessor> PP;
   std::shared_ptr<GlobalCodeCompletionAllocator> CompletionAllocator;
   std::unique_ptr<CodeCompletionTUInfo> CompletionTUInfo;
   Options Opts;
   using DeclRef = std::pair<SourceLocation, index::SymbolRoleSet>;
   // Symbols referenced from the current TU, flushed on finish().
   llvm::DenseSet<const NamedDecl *> ReferencedDecls;

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

return (Roles & static_cast<unsigned>(index::SymbolRole::Definition)) &&
          isa<TagDecl>(&ND) &&
          !SM.isWrittenInMainFile(SM.getExpansionLoc(ND.getLocation()));
 }
 
 RefKind toRefKind(index::SymbolRoleSet Roles) {
   return static_cast<RefKind>(static_cast<unsigned>(RefKind::All) & Roles);
 }
 
+bool shouldIndexRelation(const index::SymbolRelation &R) {
+  // We currently only index BaseOf relations, for type hierarchy subtypes.
+  return R.Roles & static_cast<unsigned>(index::SymbolRole::RelationBaseOf);
+}
+
 } // namespace
 
 SymbolCollector::SymbolCollector(Options Opts) : Opts(std::move(Opts)) {}
 
 void SymbolCollector::initialize(ASTContext &Ctx) {
   ASTCtx = &Ctx;
   CompletionAllocator = std::make_shared<GlobalCodeCompletionAllocator>();
   CompletionTUInfo =
bool SymbolCollector::handleDeclOccurence(
   // D may not be an interesting symbol, but it's cheaper to check at the end.
   auto &SM = ASTCtx->getSourceManager();
   auto SpellingLoc = SM.getSpellingLoc(Loc);
   if (Opts.CountReferences &&
       (Roles & static_cast<unsigned>(index::SymbolRole::Reference)) &&
       SM.getFileID(SpellingLoc) == SM.getMainFileID())
     ReferencedDecls.insert(ND);
 
+  auto ID = getSymbolID(ND);
+  if (!ID)
+    return true;
+
+  // Note: we need to process relations for all decl occurrences, including
+  // refs, because the indexing code only populates relations for specific
+  // occurrences. For example, RelationBaseOf is only populated for the
+  // occurrence inside the base-specifier.
+  processRelations(*ND, *ID, Relations);
+
   bool CollectRef = static_cast<unsigned>(Opts.RefFilter) & Roles;
   bool IsOnlyRef =
       !(Roles & (static_cast<unsigned>(index::SymbolRole::Declaration) |
                  static_cast<unsigned>(index::SymbolRole::Definition)));
 
   if (IsOnlyRef && !CollectRef)
     return true;
 
   // ND is the canonical (i.e. first) declaration. If it's in the main file,
   // then no public declaration was visible, so assume it's main-file only.
   bool IsMainFileOnly =
       SM.isWrittenInMainFile(SM.getExpansionLoc(ND->getBeginLoc()));
   // In C, printf is a redecl of an implicit builtin! So check OrigD instead.
   if (ASTNode.OrigD->isImplicit() ||
       !shouldCollectSymbol(*ND, *ASTCtx, Opts, IsMainFileOnly))
     return true;
   // Do not store references to main-file symbols.
   if (CollectRef && !IsMainFileOnly && !isa<NamespaceDecl>(ND) &&
       (Opts.RefsInHeaders || SM.getFileID(SpellingLoc) == SM.getMainFileID()))
     DeclRefs[ND].emplace_back(SpellingLoc, Roles);
   // Don't continue indexing if this is a mere reference.
   if (IsOnlyRef)
     return true;
 
-  auto ID = getSymbolID(ND);
-  if (!ID)
-    return true;
-
   // FIXME: ObjCPropertyDecl are not properly indexed here:
   // - ObjCPropertyDecl may have an OrigD of ObjCPropertyImplDecl, which is
   // not a NamedDecl.
   auto *OriginalDecl = dyn_cast<NamedDecl>(ASTNode.OrigD);
   if (!OriginalDecl)
     return true;
 
   const Symbol *BasicSymbol = Symbols.find(*ID);
   if (!BasicSymbol) // Regardless of role, ND is the canonical declaration.
     BasicSymbol = addDeclaration(*ND, std::move(*ID), IsMainFileOnly);
   else if (isPreferredDeclaration(*OriginalDecl, Roles))
     // If OriginalDecl is preferred, replace the existing canonical
     // declaration (e.g. a class forward declaration). There should be at most
     // one duplicate as we expect to see only one preferred declaration per
     // TU, because in practice they are definitions.
     BasicSymbol = addDeclaration(*OriginalDecl, std::move(*ID), IsMainFileOnly);
 
   if (Roles & static_cast<unsigned>(index::SymbolRole::Definition))
     addDefinition(*OriginalDecl, *BasicSymbol);
+
   return true;
 }
 
 bool SymbolCollector::handleMacroOccurence(const IdentifierInfo *Name,
                                            const MacroInfo *MI,
                                            index::SymbolRoleSet Roles,
                                            SourceLocation Loc) {
   if (!Opts.CollectMacro)
bool SymbolCollector::handleMacroOccurence(const IdentifierInfo *Name,
   S.CompletionSnippetSuffix = SnippetSuffix;
 
   IndexedMacros.insert(Name);
   setIncludeLocation(S, DefLoc);
   Symbols.insert(S);
   return true;
 }
 
+void SymbolCollector::processRelations(
+    const NamedDecl &ND, const SymbolID &ID,
+    ArrayRef<index::SymbolRelation> Relations) {
+  // Store subtype relations.
+  if (!dyn_cast<TagDecl>(&ND))
+    return;
+
+  for (const auto &R : Relations) {
+    if (!shouldIndexRelation(R))
+      continue;
+
+    const Decl *Object = R.RelatedSymbol;
+
+    auto ObjectID = getSymbolID(Object);
+    if (!ObjectID)
+      continue;
+
+    // Record the relation.
+    // TODO: There may be cases where the object decl is not indexed for some
+    // reason. Those cases should probably be removed in due course, but for
+    // now there are two possible ways to handle it:
+    //   (A) Avoid storing the relation in such cases.
+    //   (B) Store it anyways. Clients will likely lookup() the SymbolID
+    //       in the index and find nothing, but that's a situation they
+    //       probably need to handle for other reasons anyways.
+    // We currently do (B) because it's simpler.
+    this->Relations.insert(
+        Relation{ID, index::SymbolRole::RelationBaseOf, *ObjectID});
+  }
+}
+
 void SymbolCollector::setIncludeLocation(const Symbol &S, SourceLocation Loc) {
   if (Opts.CollectIncludePath)
     if (shouldCollectIncludePath(S.SymInfo.Kind))
       // Use the expansion location to get the #include header since this is
       // where the symbol is exposed.
       IncludeFiles[S.ID] =
           PP->getSourceManager().getDecomposedExpansionLoc(Loc).first;
 }

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

void build(llvm::StringRef HeaderCode, llvm::StringRef Code = "") {
     AST = File.build();
   }
 
   // build() must have been called.
   bool shouldCollect(llvm::StringRef Name, bool Qualified = true) {
     assert(AST.hasValue());
     const NamedDecl &ND =
         Qualified ? findDecl(*AST, Name) : findUnqualifiedDecl(*AST, Name);
-    const SourceManager& SM = AST->getSourceManager();
-    bool MainFile = SM.isWrittenInMainFile(SM.getExpansionLoc(ND.getBeginLoc()));
+    const SourceManager &SM = AST->getSourceManager();
+    bool MainFile =
+        SM.isWrittenInMainFile(SM.getExpansionLoc(ND.getBeginLoc()));
     return SymbolCollector::shouldCollectSymbol(
         ND, AST->getASTContext(), SymbolCollector::Options(), MainFile);
   }
 
 protected:
   std::string HeaderName = "f.h";
   std::string FileName = "f.cpp";
   TestTU File;
bool runSymbolCollector(llvm::StringRef HeaderCode, llvm::StringRef MainCode,
     // This allows to override the "-xc++" with something else, i.e.
     // -xobjective-c++.
     Args.push_back(TestFileName);
 
     tooling::ToolInvocation Invocation(
         Args, Factory->create(), Files.get(),
         std::make_shared<PCHContainerOperations>());
 
-    InMemoryFileSystem->addFile(
-        TestHeaderName, 0, llvm::MemoryBuffer::getMemBuffer(HeaderCode));
+    InMemoryFileSystem->addFile(TestHeaderName, 0,
+                                llvm::MemoryBuffer::getMemBuffer(HeaderCode));
     InMemoryFileSystem->addFile(TestFileName, 0,
                                 llvm::MemoryBuffer::getMemBuffer(MainCode));
     Invocation.run();
     Symbols = Factory->Collector->takeSymbols();
     Refs = Factory->Collector->takeRefs();
+    Relations = Factory->Collector->takeRelations();
     return true;
   }
 
 protected:
   llvm::IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> InMemoryFileSystem;
   std::string TestHeaderName;
   std::string TestHeaderURI;
   std::string TestFileName;
   std::string TestFileURI;
   SymbolSlab Symbols;
   RefSlab Refs;
+  RelationSlab Relations;
   SymbolCollector::Options CollectorOpts;
   std::unique_ptr<CommentHandler> PragmaHandler;
 };
 
 TEST_F(SymbolCollectorTest, CollectSymbols) {
   const std::string Header = R"(
     class Foo {
       Foo() {}
TEST_F(SymbolCollectorTest, RefsInHeaders) {
   Annotations Header(R"(
   class [[Foo]] {};
   )");
   runSymbolCollector(Header.code(), "");
   EXPECT_THAT(Refs, Contains(Pair(findSymbol(Symbols, "Foo").ID,
                                   HaveRanges(Header.ranges()))));
 }
 
+TEST_F(SymbolCollectorTest, Relations) {
+  std::string Header = R"(
+  class Base {};
+  class Derived : public Base {};
+  )";
+  runSymbolCollector(Header, /*Main=*/"");
+  const Symbol &Base = findSymbol(Symbols, "Base");
+  const Symbol &Derived = findSymbol(Symbols, "Derived");
+  EXPECT_THAT(Relations,
+              Contains(Relation{Base.ID, index::SymbolRole::RelationBaseOf,
+                                Derived.ID}));
+}
+
 TEST_F(SymbolCollectorTest, References) {
   const std::string Header = R"(
     class W;
     class X {};
     class Y;
     class Z {}; // not used anywhere
     Y* y = nullptr;  // used in header doesn't count
     #define GLOBAL_Z(name) Z name;
const std::string Main = R"(
     namespace {
     class Bar {};
     }
     }
     void main_f() {}
     void f1() {}
   )";
   runSymbolCollector(/*Header=*/"", Main);
-  EXPECT_THAT(Symbols,
-              UnorderedElementsAre(QName("Foo"), QName("f1"), QName("f2"),
-                                   QName("ff"), QName("foo"), QName("foo::Bar"),
-                                   QName("main_f")));
+  EXPECT_THAT(Symbols, UnorderedElementsAre(
+                           QName("Foo"), QName("f1"), QName("f2"), QName("ff"),
+                           QName("foo"), QName("foo::Bar"), QName("main_f")));
 }
 
 TEST_F(SymbolCollectorTest, Documentation) {
   const std::string Header = R"(
     // Doc Foo
     class Foo {
       // Doc f
       int f();