[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 ↗

(On Diff #192053)

can we give this a more descriptive name like RecursiveHierarchyUnbounded?

405 ↗

(On Diff #192053)

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 ↗

(On Diff #192053)

RecursiveHierarchyBounded

447 ↗

(On Diff #192053)

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

463 ↗

(On Diff #192053)

(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 ↗

(On Diff #192053)

this patch doesn't seem to be against HEAD

[nridge]

Address review comments

[nridge]

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

405 ↗

(On Diff #192053)

(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 ↗

(On Diff #192053)

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 ↗

(On Diff #192053)

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/trunk/clangd/XRefs.cpp

declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
   auto TUPath = getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
   if (!FilePath || !TUPath)
     return llvm::None; // Not useful without a uri.
   THI.uri = URIForFile::canonicalize(*FilePath, *TUPath);
 
   return THI;
 }
 
-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 CXXRecordDecl *CXXRD = findRecordTypeAt(AST, Pos);
   if (!CXXRD)
     return llvm::None;
 
+  RecursionProtectionSet RPSet;
   Optional<TypeHierarchyItem> Result =
-      getTypeAncestors(*CXXRD, AST.getASTContext());
+      getTypeAncestors(*CXXRD, AST.getASTContext(), RPSet);
+
   // FIXME(nridge): Resolve type descendants if direction is Children or Both,
   // and ResolveLevels > 0.
+
   return Result;
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/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) {
+TEST(TypeHierarchy, RecursiveHierarchyUnbounded) {
   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.
+  // FIXME(nridge): It would be preferable if the type hierarchy gave us type
+  // names (e.g. "S<0>" for the child and "S<1>" for the parent) rather than
+  // template names (e.g. "S").
   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) {
+TEST(TypeHierarchy, RecursiveHierarchyBounded) {
   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()));
-}
-
-TEST(TypeHierarchy, RecursiveHierarchy3) {
-  Annotations Source(R"cpp(
-  template <int N>
-  struct S : S<N - 1> {};
-
-  template <>
-  struct S<0>{};
+  S$SRefConcrete^<2> s;
 
   template <int N>
   struct Foo {
-    S^<N> s;
-  };
-  )cpp");
+    S$SRefDependent^<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.
+  // Make sure getTypeHierarchy() doesn't get into an infinite recursion
+  // for either a concrete starting point or a dependent starting point.
   llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
-      AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
+      AST, Source.point("SRefConcrete"), 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()))));
+  Result = getTypeHierarchy(AST, Source.point("SRefDependent"), 0,
+                            TypeHierarchyDirection::Parents);
+  ASSERT_TRUE(bool(Result));
+  EXPECT_THAT(
+      *Result,
+      AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+            Parents(AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+                          SelectionRangeIs(Source.range("SDef")), Parents()))));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang