[clangd] Support dependent bases in type hierarchy

Patch by Nathan Ridge!

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.

Differential Revision: https://reviews.llvm.org/D59756

git-svn-id: https://llvm.org/svn/llvm-project/clang-tools-extra/trunk@358866 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 69 insertions, 47 deletions

diff --git a/clangd/XRefs.cpp b/clangd/XRefs.cpp
index 6ca65bea..6f47618f 100644
--- a/clangd/XRefs.cpp
+++ b/clangd/XRefs.cpp
@@ -876,21 +876,40 @@ declToTypeHierarchyItem(ASTContext &Ctx, const NamedDecl &ND) {
   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;
 }
 
@@ -933,10 +952,17 @@ std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) {
       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);
@@ -952,10 +978,13 @@ getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
   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;
 }
 
diff --git a/unittests/clangd/TypeHierarchyTests.cpp b/unittests/clangd/TypeHierarchyTests.cpp
index 81a9ab43..79307e28 100644
--- a/unittests/clangd/TypeHierarchyTests.cpp
+++ b/unittests/clangd/TypeHierarchyTests.cpp
@@ -291,9 +291,7 @@ struct Child<int> : Parent {};
   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 {};
@@ -383,10 +381,10 @@ int main() {
   }
 }
 
-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");
@@ -399,62 +397,57 @@ TEST(TypeHierarchy, RecursiveHierarchy1) {
   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(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()));
+  EXPECT_THAT(
+      *Result,
+      AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+            Parents(AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+                          SelectionRangeIs(Source.range("SDef")), Parents()))));
 }
 
 } // namespace