[clangd] Support dependent bases in type hierarchy

[nridge]

Summary

Dependent bases are handled heuristically, by replacing them with the class
template that they are a specialization of, where possible. Care is taken
to avoid infinite recursion.

[nridge]

This patch aims to implement the more proper solution suggested here.

I couldn't actually use CXXRecordDecl->getTemplateInstantiationPattern() as suggested, because the base-specifiers resolve to types, not declarations, but I believe what I did here implements the same intention (please let me know if I misunderstood).

[sammccall]

LG, though I think your patch might be based on top of some uncommitted changes.

I noticed template names rather than type names are shown (not new in this patch) - we should fix that I think.

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

384

can we give this a more descriptive name like RecursiveHierarchyUnbounded?

405

Sorry, I realize this isn't related to this patch, but I didn't see the final form of the previous one.

This should be WithName("S<0>"), ... Parents(AllOf(WithName("S<1>")), ...). S is the name of the template, not the name of the type.

Can you add a fixme?

410

RecursiveHierarchyBounded

447

this can be merged with the previous test case, using two named points.

463

(in this case the printed name for the parent might end up looking odd - printing the spelled S<N - 1> is probably ideal but I don't really mind what we end up with, this is an edge case. Not for this patch, in any case)

609

this patch doesn't seem to be against HEAD

[nridge]

Address review comments

[nridge]

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

405

(I looked into what it would take to fix this, and it seems like we need D59639, so I'm going to wait for that.)

[sammccall]

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

405

AFAICS D59639 is something subtly different - it prints the args of *specializations* as written in the source code, not instantiations. i.e. if you try to use this for vector<int>, it won't work as there's no specialization, you'll get vector<T> instead.

[nridge]

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

405

I had another look, and you're right; I didn't appreciate that distinction.

I filed an issue to track implementing your suggestion. I plan to work on it.

In the meantime, could we get this patch committed?

[nridge]

Ping - could this be committed please?

[nridge]

Thanks!

clang-tools-extra/clangd/XRefs.cpp

Index->relations(ID, index::SymbolRole::RelationBaseOf,
                          fillSubTypes(Sub, *ChildSym->children, Index,
                                       Levels - 1);
                        }
                        SubTypes.emplace_back(std::move(*ChildSym));
                      }
                    });
 }
 
-static Optional<TypeHierarchyItem> getTypeAncestors(const CXXRecordDecl &CXXRD,
-                                                    ASTContext &ASTCtx) {
+using RecursionProtectionSet = llvm::SmallSet<const CXXRecordDecl *, 4>;
+
+static Optional<TypeHierarchyItem>
+getTypeAncestors(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx,
+                 RecursionProtectionSet &RPSet) {
   Optional<TypeHierarchyItem> Result = declToTypeHierarchyItem(ASTCtx, CXXRD);
   if (!Result)
     return Result;
 
   Result->parents.emplace();
 
+  // typeParents() will replace dependent template specializations
+  // with their class template, so to avoid infinite recursion for
+  // certain types of hierarchies, keep the templates encountered
+  // along the parent chain in a set, and stop the recursion if one
+  // starts to repeat.
+  auto *Pattern = CXXRD.getDescribedTemplate() ? &CXXRD : nullptr;
+  if (Pattern) {
+    if (!RPSet.insert(Pattern).second) {
+      return Result;
+    }
+  }
+
   for (const CXXRecordDecl *ParentDecl : typeParents(&CXXRD)) {
     if (Optional<TypeHierarchyItem> ParentSym =
-            getTypeAncestors(*ParentDecl, ASTCtx)) {
+            getTypeAncestors(*ParentDecl, ASTCtx, RPSet)) {
       Result->parents->emplace_back(std::move(*ParentSym));
     }
   }
+
+  if (Pattern) {
+    RPSet.erase(Pattern);
+  }
+
   return Result;
 }
 
 const CXXRecordDecl *findRecordTypeAt(ParsedAST &AST, Position Pos) {
   ASTContext &ASTCtx = AST.getASTContext();
   const SourceManager &SourceMgr = ASTCtx.getSourceManager();
   SourceLocation SourceLocationBeg =
       getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) {
   for (auto Base : CXXRD->bases()) {
     const CXXRecordDecl *ParentDecl = nullptr;
 
     const Type *Type = Base.getType().getTypePtr();
     if (const RecordType *RT = Type->getAs<RecordType>()) {
       ParentDecl = RT->getAsCXXRecordDecl();
     }
 
-    // For now, do not handle dependent bases such as "Base<T>".
-    // We would like to handle them by heuristically choosing the
-    // primary template declaration, but we need to take care to
-    // avoid infinite recursion.
+    if (!ParentDecl) {
+      // Handle a dependent base such as "Base<T>" by using the primary
+      // template.
+      if (const TemplateSpecializationType *TS =
+              Type->getAs<TemplateSpecializationType>()) {
+        TemplateName TN = TS->getTemplateName();
+        if (TemplateDecl *TD = TN.getAsTemplateDecl()) {
+          ParentDecl = dyn_cast<CXXRecordDecl>(TD->getTemplatedDecl());
+        }
+      }
+    }
 
     if (ParentDecl)
       Result.push_back(ParentDecl);
   }
 
   return Result;
 }
 
 llvm::Optional<TypeHierarchyItem>
 getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
                  TypeHierarchyDirection Direction, const SymbolIndex *Index) {
   const CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
   if (!CXXRD)
     return llvm::None;
 
+  RecursionProtectionSet RPSet;
   Optional<TypeHierarchyItem> Result =
-      getTypeAncestors(*CXXRD, AST.getASTContext());
+      getTypeAncestors(*CXXRD, AST.getASTContext(), RPSet);
 
   if ((Direction == TypeHierarchyDirection::Children ||
        Direction == TypeHierarchyDirection::Both) &&
       ResolveLevels > 0) {
     Result->children.emplace();
 
     if (Index) {
       if (Optional<SymbolID> ID = getSymbolID(CXXRD)) {

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

const CXXRecordDecl *Child =
       dyn_cast<ClassTemplateDecl>(&findDecl(AST, "Child"))->getTemplatedDecl();
   const CXXRecordDecl *ChildSpec =
       dyn_cast<CXXRecordDecl>(&findDeclWithTemplateArgs(AST, "Child<int>"));
 
   EXPECT_THAT(typeParents(Child), ElementsAre());
   EXPECT_THAT(typeParents(ChildSpec), ElementsAre(Parent));
 }
 
-// This is disabled for now, because support for dependent bases
-// requires additional measures to avoid infinite recursion.
-TEST(DISABLED_TypeParents, DependentBase) {
+TEST(TypeParents, DependentBase) {
   Annotations Source(R"cpp(
 template <typename T>
 struct Parent {};
 
 template <typename T>
 struct Child1 : Parent<T> {};
 
 template <typename T>
EXPECT_THAT(
                           SelectionRangeIs(Source.range("Parent3Def")),
                           Parents(AllOf(
                               WithName("Parent2"), WithKind(SymbolKind::Struct),
                               SelectionRangeIs(Source.range("Parent2Def")),
                               Parents()))))));
   }
 }
 
 TEST(TypeHierarchy, RecursiveHierarchy1) {
   Annotations Source(R"cpp(
   template <int N>
-  struct S : S<N + 1> {};
+  struct $SDef[[S]] : S<N + 1> {};
 
   S^<0> s;
   )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
 
   // The compiler should produce a diagnostic for hitting the
   // template instantiation depth.
   ASSERT_TRUE(!AST.getDiagnostics().empty());
 
   // Make sure getTypeHierarchy() doesn't get into an infinite recursion.
   llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
       AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
   ASSERT_TRUE(bool(Result));
-  EXPECT_THAT(*Result,
-              AllOf(WithName("S"), WithKind(SymbolKind::Struct), Parents()));
+  EXPECT_THAT(
+      *Result,
+      AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+            Parents(AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+                          SelectionRangeIs(Source.range("SDef")), Parents()))));
 }
 
 TEST(TypeHierarchy, RecursiveHierarchy2) {
   Annotations Source(R"cpp(
   template <int N>
-  struct S : S<N - 1> {};
+  struct $SDef[[S]] : S<N - 1> {};
 
   template <>
   struct S<0>{};
 
   S^<2> s;
   )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
 
   ASSERT_TRUE(AST.getDiagnostics().empty());
 
   // Make sure getTypeHierarchy() doesn't get into an infinite recursion.
   llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
       AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
   ASSERT_TRUE(bool(Result));
-  EXPECT_THAT(*Result,
-              AllOf(WithName("S"), WithKind(SymbolKind::Struct), Parents()));
+  EXPECT_THAT(
+      *Result,
+      AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+            Parents(AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+                          SelectionRangeIs(Source.range("SDef")), Parents()))));
 }
 
 TEST(TypeHierarchy, RecursiveHierarchy3) {
   Annotations Source(R"cpp(
   template <int N>
-  struct S : S<N - 1> {};
+  struct $SDef[[S]] : S<N - 1> {};
 
   template <>
   struct S<0>{};
 
   template <int N>
   struct Foo {
     S^<N> s;
   };
   )cpp");
 
   TestTU TU = TestTU::withCode(Source.code());
   auto AST = TU.build();
 
   ASSERT_TRUE(AST.getDiagnostics().empty());
 
   // Make sure getTypeHierarchy() doesn't get into an infinite recursion.
   llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
       AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
   ASSERT_TRUE(bool(Result));
-  EXPECT_THAT(*Result,
-              AllOf(WithName("S"), WithKind(SymbolKind::Struct), Parents()));
+  EXPECT_THAT(
+      *Result,
+      AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+            Parents(AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+                          SelectionRangeIs(Source.range("SDef")), Parents()))));
 }
 
 SymbolID findSymbolIDByName(llvm::StringRef Name, SymbolIndex *Index) {
   SymbolID Result;
   FuzzyFindRequest Request;
   Request.Query = Name;
   Request.AnyScope = true;
   Request.Limit = 1;
)cpp");
   auto Index = TU.index();
 
   SymbolID Parent = findSymbolIDByName("Parent", Index.get());
   SymbolID ChildSpec = findSymbolIDByName("Child<int>", Index.get());
 
   EXPECT_THAT(collectSubtypes(Parent, Index.get()), ElementsAre(ChildSpec));
 }
 
-// Disabled for the same reason as TypeParents.DependentBase.
-TEST(DISABLED_Subtypes, DependentBase) {
+TEST(Subtypes, DependentBase) {
   Annotations Source(R"cpp(
 template <typename T>
 struct Parent {};
 
 template <typename T>
 struct Child : Parent<T> {};
 )cpp");