[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

why do we want to process these relations for references?

426

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

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

434

maybe call it Object ?

436

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

nit: invert the condition to reduce nesting

453

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

453

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

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

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

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

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

298

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

could you add a comment explaining the situation ?

431

nit: no need for braces

436

nit: braces

453

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/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/clangd/index/SymbolCollector.cpp

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;
+
+  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::setIncludeLocation(const Symbol &S,
-                                         SourceLocation Loc) {
+void SymbolCollector::processRelations(
+    const NamedDecl &ND, const SymbolID &ID,
+    ArrayRef<index::SymbolRelation> Relations) {
+  // Store subtype relations.
+  const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(&ND);
+  if (!RD)
+    return;
+
+  for (const auto &R : Relations) {
+    if (!(R.Roles & static_cast<unsigned>(index::SymbolRole::RelationBaseOf))) {
+      continue;
+    }
+    const Decl *Parent = R.RelatedSymbol;
+
+    if (const auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(Parent)) {
+      if (!CTSD->isExplicitSpecialization()) {
+        Parent = CTSD->getSpecializedTemplate();
+      }
+    }
+    if (auto ParentID = getSymbolID(Parent)) {
+      // We are a subtype to each of our parents.
+      // TODO: There may be cases where the parent type is not indexed for some
+      // reason (e.g. currently we don't index explicit class template
+      // specializations). Those cases should probably be removed in due course,
+      // but for now there are two possible ways to handle it:
+      //   (A) Avoid storing the relationship 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, *ParentID});
+    }
+  }
+}
+
+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;
 }
 
static bool isIf(llvm::StringRef Line) {
   return Line.startswith("if");
 }
 // Is Line an #error directive mentioning includes?
 static bool isErrorAboutInclude(llvm::StringRef Line) {
   Line = Line.ltrim();
   if (!Line.consume_front("#"))
     return false;
   Line = Line.ltrim();
-  if (! Line.startswith("error"))
+  if (!Line.startswith("error"))
     return false;
   return Line.contains_lower("includ"); // Matches "include" or "including".
 }
 
 bool SymbolCollector::isDontIncludeMeHeader(llvm::StringRef Content) {
   llvm::StringRef Line;
   // Only sniff up to 100 lines or 10KB.
-  Content = Content.take_front(100*100);
+  Content = Content.take_front(100 * 100);
   for (unsigned I = 0; I < 100 && !Content.empty(); ++I) {
     std::tie(Line, Content) = Content.split('\n');
     if (isIf(Line) && isErrorAboutInclude(Content.split('\n').first))
       return true;
   }
   return false;
 }
 
 } // namespace clangd
 } // namespace clang