[clangd] Show template arguments in type hierarchy when possible

[nridge]

Summary

Fixes https://github.com/clangd/clangd/issues/31

[kadircet]

I think this requires changes in other places too, for example when querying index for the children we rather want to query using the symbolid of template pattern, not the instantiation.

clang-tools-extra/clangd/XRefs.cpp

674–675

instead of doing the traversal twice, can we just sent both pattern and instantiation here, and then prefer the specializationdecl instead of just selecting decls[0] below ?

[nridge]

Address review comments

[nridge]

In D71533#1785376, @kadircet wrote:

I think this requires changes in other places too, for example when querying index for the children we rather want to query using the symbolid of template pattern, not the instantiation.

Good catch! I added a couple of additional test cases to exercise this.

[kadircet]

clang-tools-extra/clangd/XRefs.cpp

690

maybe just

const Decl *D = Decls.front()
for(const auto *C : Decls) {
  if(isa<ClassTempl...>(C)) {
    D = C;
    break;
  }
}

775

nit: no need for braces

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

421

what about making use of template pattern in case of invalid instantiations?

as type hierarchy tries to provide information regarding bases and children, I think it is more important to show those instead of template instantiation arguments.

472

can you also add a case for deriving from explicit (partial) specialization and type hierarchy on instantiation of a different pattern?
e.g.

template <typename T> class X {};
template <typename T> class X<T*> {};

struct Child : X<int*> {};

X<int> fo^o;

[kadircet]

clang-tools-extra/clangd/XRefs.cpp

690

now you can use explicitReferenceTargets instead, with only DeclRelation::Underlying set in the mask.

[nridge]

Address most review comments

[nridge]

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

421

Is there a way to query a ClassTemplateSpecializationDecl for whether instantiating its base specifier failed?

Or, should we fall back on the template pattern any time bases() is empty?

[kadircet]

clang-tools-extra/clangd/XRefs.cpp

141

this will result in changes in behavior for other functionality (it is unfortunate if no tests regressed), for example findReferences did work on template patterns rather than instantiations now it won't receive pattern results when triggered on instantiations. whether we want that or not is up for debate, but definitely not part of this patch.

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

421

you can check for CTSD->isInvalidDecl() and fallback to pattern in such cases.

[nridge]

Address review comments

[merge_guards_bot]

Unit tests: pass. 61304 tests passed, 0 failed and 736 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[kadircet]

clang-tools-extra/clangd/XRefs.cpp

680

instead of creating a new function, could you rather inline that ? it is the only call site and almost the same with getDeclAtPosition.
the comment above (with little modifications) should suffice to explain why getDeclAtPosition is not used here.

[nridge]

Address latest review comment

[merge_guards_bot]

Unit tests: pass. 61729 tests passed, 0 failed and 779 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[kadircet]

Thanks, LGTM!

clang-tools-extra/clangd/XRefs.cpp

715

nit: redundant braces

[nridge]

Address nit

[merge_guards_bot]

Unit tests: pass. 61774 tests passed, 0 failed and 780 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

clang-tools-extra/clangd/XRefs.cpp

std::vector<const NamedDecl *> getDeclAtPosition(ParsedAST &AST,
                                                  SourceLocation Pos,
                                                  DeclRelationSet Relations) {
   FileID FID;
   unsigned Offset;
   std::tie(FID, Offset) = AST.getSourceManager().getDecomposedSpellingLoc(Pos);
   SelectionTree Selection(AST.getASTContext(), AST.getTokens(), Offset);
   std::vector<const NamedDecl *> Result;
   if (const SelectionTree::Node *N = Selection.commonAncestor()) {
     auto Decls = targetDecl(N->ASTNode, Relations);
     Result.assign(Decls.begin(), Decls.end());
   }
   return Result;
 }
 
 llvm::Optional<Location> makeLocation(ASTContext &AST, SourceLocation TokLoc,
                                       llvm::StringRef TUPath) {
   const SourceManager &SourceMgr = AST.getSourceManager();
static void fillSuperTypes(const CXXRecordDecl &CXXRD, ASTContext &ASTCtx,
   if (Pattern) {
     RPSet.erase(Pattern);
   }
 }
 
 const CXXRecordDecl *findRecordTypeAt(ParsedAST &AST, Position Pos) {
   const SourceManager &SM = AST.getSourceManager();
   SourceLocation SourceLocationBeg = SM.getMacroArgExpandedLocation(
       getBeginningOfIdentifier(Pos, SM, AST.getLangOpts()));
-  DeclRelationSet Relations =
-      DeclRelation::TemplatePattern | DeclRelation::Underlying;
-  auto Decls = getDeclAtPosition(AST, SourceLocationBeg, Relations);
+  unsigned Offset =
+      AST.getSourceManager().getDecomposedSpellingLoc(SourceLocationBeg).second;
+  SelectionTree Selection(AST.getASTContext(), AST.getTokens(), Offset);
+  const SelectionTree::Node *N = Selection.commonAncestor();
+  if (!N)
+    return nullptr;
+
+  // Note: explicitReferenceTargets() will search for both template
+  // instantiations and template patterns, and prefer the former if available
+  // (generally, one will be available for non-dependent specializations of a
+  // class template).
+  auto Decls = explicitReferenceTargets(N->ASTNode, DeclRelation::Underlying);
   if (Decls.empty())
     return nullptr;
 
   const NamedDecl *D = Decls[0];
 
   if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
     // If this is a variable, use the type of the variable.
     return VD->getType().getTypePtr()->getAsCXXRecordDecl();
   }
 
   if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
     // If this is a method, use the type of the class.
     return Method->getParent();
   }
 
   // We don't handle FieldDecl because it's not clear what behaviour
   // the user would expect: the enclosing class type (as with a
   // method), or the field's type (as with a variable).
 
   return dyn_cast<CXXRecordDecl>(D);
 }
 
 std::vector<const CXXRecordDecl *> typeParents(const CXXRecordDecl *CXXRD) {
   std::vector<const CXXRecordDecl *> Result;
 
+  // If this is an invalid instantiation, instantiation of the bases
+  // may not have succeeded, so fall back to the template pattern.
+  if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD)) {
+    if (CTSD->isInvalidDecl())
+      CXXRD = CTSD->getSpecializedTemplate()->getTemplatedDecl();
+  }
+
   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();
     }
 
getTypeHierarchy(ParsedAST &AST, Position Pos, int ResolveLevels,
   }
 
   if ((Direction == TypeHierarchyDirection::Children ||
        Direction == TypeHierarchyDirection::Both) &&
       ResolveLevels > 0) {
     Result->children.emplace();
 
     if (Index) {
+      // The index does not store relationships between implicit
+      // specializations, so if we have one, use the template pattern instead.
+      if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(CXXRD))
+        CXXRD = CTSD->getTemplateInstantiationPattern();
+
       if (Optional<SymbolID> ID = getSymbolID(CXXRD))
         fillSubTypes(*ID, *Result->children, Index, ResolveLevels, TUPath);
     }
   }
 
   return Result;
 }
 

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

TEST(TypeHierarchy, RecursiveHierarchyUnbounded) {
   TU.ExtraArgs.push_back("-ftemplate-depth=10");
   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").
+  // The parent is reported as "S" because "S<0>" is an invalid instantiation.
+  // We then iterate once more and find "S" again before detecting the
+  // recursion.
   llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
       AST, Source.points()[0], 0, TypeHierarchyDirection::Parents);
   ASSERT_TRUE(bool(Result));
   EXPECT_THAT(
       *Result,
+      AllOf(WithName("S<0>"), WithKind(SymbolKind::Struct),
+            Parents(
                 AllOf(WithName("S"), WithKind(SymbolKind::Struct),
+                      SelectionRangeIs(Source.range("SDef")),
                       Parents(AllOf(WithName("S"), WithKind(SymbolKind::Struct),
-                          SelectionRangeIs(Source.range("SDef")), Parents()))));
+                                    SelectionRangeIs(Source.range("SDef")),
+                                    Parents()))))));
 }
 
 TEST(TypeHierarchy, RecursiveHierarchyBounded) {
   Annotations Source(R"cpp(
   template <int N>
   struct $SDef[[S]] : S<N - 1> {};
 
   template <>
TEST(TypeHierarchy, RecursiveHierarchyBounded) {
 
   // 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.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()))));
+      AllOf(WithName("S<2>"), WithKind(SymbolKind::Struct),
+            Parents(AllOf(
+                WithName("S<1>"), WithKind(SymbolKind::Struct),
+                SelectionRangeIs(Source.range("SDef")),
+                Parents(AllOf(WithName("S<0>"), WithKind(SymbolKind::Struct),
+                              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()))));
 }
 
+TEST(TypeHierarchy, DeriveFromImplicitSpec) {
+  Annotations Source(R"cpp(
+  template <typename T>
+  struct Parent {};
+
+  struct Child : Parent<int> {};
+
+  Parent<int> Fo^o;
+  )cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+  auto Index = TU.index();
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
+      AST, Source.points()[0], 2, TypeHierarchyDirection::Children, Index.get(),
+      testPath(TU.Filename));
+  ASSERT_TRUE(bool(Result));
+  EXPECT_THAT(*Result,
+              AllOf(WithName("Parent<int>"), WithKind(SymbolKind::Struct),
+                    Children(AllOf(WithName("Child"),
+                                   WithKind(SymbolKind::Struct), Children()))));
+}
+
+TEST(TypeHierarchy, DeriveFromPartialSpec) {
+  Annotations Source(R"cpp(
+  template <typename T> struct Parent {};
+  template <typename T> struct Parent<T*> {};
+
+  struct Child : Parent<int*> {};
+
+  Parent<int> Fo^o;
+  )cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+  auto Index = TU.index();
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
+      AST, Source.points()[0], 2, TypeHierarchyDirection::Children, Index.get(),
+      testPath(TU.Filename));
+  ASSERT_TRUE(bool(Result));
+  EXPECT_THAT(*Result, AllOf(WithName("Parent<int>"),
+                             WithKind(SymbolKind::Struct), Children()));
+}
+
+TEST(TypeHierarchy, DeriveFromTemplate) {
+  Annotations Source(R"cpp(
+  template <typename T>
+  struct Parent {};
+
+  template <typename T>
+  struct Child : Parent<T> {};
+
+  Parent<int> Fo^o;
+  )cpp");
+
+  TestTU TU = TestTU::withCode(Source.code());
+  auto AST = TU.build();
+  auto Index = TU.index();
+  ASSERT_TRUE(AST.getDiagnostics().empty());
+
+  // FIXME: We'd like this to return the implicit specialization Child<int>,
+  //        but currently libIndex does not expose relationships between
+  //        implicit specializations.
+  llvm::Optional<TypeHierarchyItem> Result = getTypeHierarchy(
+      AST, Source.points()[0], 2, TypeHierarchyDirection::Children, Index.get(),
+      testPath(TU.Filename));
+  ASSERT_TRUE(bool(Result));
+  EXPECT_THAT(*Result,
+              AllOf(WithName("Parent<int>"), WithKind(SymbolKind::Struct),
+                    Children(AllOf(WithName("Child"),
+                                   WithKind(SymbolKind::Struct), Children()))));
+}
+
 SymbolID findSymbolIDByName(SymbolIndex *Index, llvm::StringRef Name,
                             llvm::StringRef TemplateArgs = "") {
   SymbolID Result;
   FuzzyFindRequest Request;
   Request.Query = Name;
   Request.AnyScope = true;
   bool GotResult = false;
   Index->fuzzyFind(Request, [&](const Symbol &S) {