[include-cleaner] Improve handling for templates

[kadircet]

Summary

Principal here is:

• Making sure each template instantiation implies use of the most specialized template. As explicit instantiations/specializations are not redeclarations of the primary template.
• Introducing a use from explicit instantions/specializaitons to the primary template, as they're required but not traversed as part of the RAV.

[kadircet]

• Use template instantion pattern helper instead of dealing with partial specializations

[sammccall]

clang-tools-extra/include-cleaner/lib/WalkAST.cpp

91

We could consider the other order:

if (auto *Pattern = TD->getTemplateInstantiationPattern())
  return Pattern;
return TD;

To me this feels a bit more like there's an obvious principle and less like case bashing.

Concretely I think the difference is that we now report the pattern rather than the specialization for explicit template instantiations. As discussed offline, I'm not very familiar with the patterns where explicit instantiations are used. But it seems at least ambiguous whether a visible explicit instantiation is semantically significant, whereas it's clear that the pattern is important. So I think preferring the pattern here would be slightly better too, up to you.

196

maybe add to the comment that implicit ones are never visited?
(It should have been obvious to me, but it's easy to fall into the trap of "what are all the things a CTSD can be again?")

clang-tools-extra/include-cleaner/unittests/WalkASTTest.cpp

111

this seems a little ad-hoc (is class name always enough info, why are we sorting/uniquing here)

Consider returning vector<NamedDecl*> and using a matcher to verify the things you care about (kind(Decl::ClassTemplate) or so?)

[kadircet]

clang-tools-extra/include-cleaner/unittests/WalkASTTest.cpp

111

sorry was planning to drop this actually, analysistest covers the "we're picking the right declaration at a certain location" logic. but since i forgot, i might as well change it to keep decls around :P

[kadircet]

• Ignore explicit instantiations
• Update tests to use decls

[dyung]

@kadircet, your change is causing 3 test failures on Windows bots, can you take a look and revert if you need time to investigate?

https://lab.llvm.org/buildbot/#/builders/216/builds/19740
https://lab.llvm.org/buildbot/#/builders/123/builds/18332

[kadircet]

figured out the issue, preparing a fix

[kadircet]

caea93cc4478cca28321cba4fa2871d5e6090299 should fix the issue

clang-tools-extra/include-cleaner/lib/WalkAST.cpp

 //===--- WalkAST.cpp - Find declaration references in the AST -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "AnalysisInternal.h"
 #include "clang-include-cleaner/Types.h"
+#include "clang/AST/ASTFwd.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
+#include "clang/AST/DeclTemplate.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/TemplateBase.h"
 #include "clang/AST/TemplateName.h"
 #include "clang/AST/Type.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/Basic/IdentifierTable.h"
NamedDecl *getMemberProvider(QualType Base) {
     return Base->getAsRecordDecl();
   }
   // Templated as TemplateSpecializationType and
   // DeducedTemplateSpecializationType doesn't share a common base.
   template <typename T>
   // Picks the most specific specialization for a
   // (Deduced)TemplateSpecializationType, while prioritizing using-decls.
   NamedDecl *getMostRelevantTemplatePattern(const T *TST) {
-    // This is the underlying decl used by TemplateSpecializationType, can be
-    // null when type is dependent.
-    auto *RD = TST->getAsTagDecl();
-    auto *ND = resolveTemplateName(TST->getTemplateName());
     // In case of exported template names always prefer the using-decl. This
     // implies we'll point at the using-decl even when there's an explicit
     // specializaiton using the exported name, but that's rare.
+    auto *ND = resolveTemplateName(TST->getTemplateName());
     if (llvm::isa_and_present<UsingShadowDecl, TypeAliasTemplateDecl>(ND))
       return ND;
-    // Fallback to primary template for dependent instantiations.
-    return RD ? RD : ND;
+    // This is the underlying decl used by TemplateSpecializationType, can be
+    // null when type is dependent if so fallback to primary template.
+    CXXRecordDecl *TD = TST->getAsCXXRecordDecl();
+    if (!TD)
+      return ND;
+    // We ignore explicit instantiations. This might imply marking the wrong
+    // declaration as used in specific cases, but seems like the right trade-off
+    // in general (e.g. we don't want to include a custom library that has an
+    // explicit specialization of a common type).
+    if (auto *Pat = TD->getTemplateInstantiationPattern())
+      return Pat;
+    // For explicit specializations, use the specialized decl directly.
+    return TD;
   }
 
 public:
   ASTWalker(DeclCallback Callback) : Callback(Callback) {}
 
   // Operators are almost always ADL extension points and by design references
   // to them doesn't count as uses (generally the type should provide them, so
   // ignore them).
public:
   bool VisitEnumDecl(EnumDecl *D) {
     // Definition of an enum with an underlying type references declaration for
     // type-checking purposes.
     if (D->isThisDeclarationADefinition() && D->getIntegerTypeSourceInfo())
       report(D->getLocation(), D);
     return true;
   }
 
+  // Report a reference from explicit specializations to the specialized
+  // template. Implicit ones are filtered out by RAV and explicit instantiations
+  // are already traversed through typelocs.
+  bool
+  VisitClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *CTSD) {
+    if (CTSD->isExplicitSpecialization())
+      report(CTSD->getLocation(),
+             CTSD->getSpecializedTemplate()->getTemplatedDecl());
+    return true;
+  }
+  bool VisitVarTemplateSpecializationDecl(VarTemplateSpecializationDecl *VTSD) {
+    if (VTSD->isExplicitSpecialization())
+      report(VTSD->getLocation(),
+             VTSD->getSpecializedTemplate()->getTemplatedDecl());
+    return true;
+  }
+
   // TypeLoc visitors.
   bool VisitUsingTypeLoc(UsingTypeLoc TL) {
     report(TL.getNameLoc(), TL.getFoundDecl());
     return true;
   }
 
   bool VisitTagTypeLoc(TagTypeLoc TTL) {
     report(TTL.getNameLoc(), TTL.getDecl());

clang-tools-extra/include-cleaner/unittests/AnalysisTest.cpp

 #include "TypesInternal.h"
 #include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
+#include "clang/Format/Format.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Testing/TestAST.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Testing/Annotations/Annotations.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cstddef>
+#include <map>
 #include <memory>
 #include <string>
 #include <vector>
 
 namespace clang::include_cleaner {
 namespace {
 using testing::AllOf;
 using testing::Contains;
EXPECT_THAT(
                                          Answer1, RefType::Explicit},
                          SymbolReference{SM.getComposedLoc(SM.getMainFileID(),
                                                            Code.point("2")),
                                          Answer2, RefType::Explicit}}),
       UnorderedElementsAre(
           Pair(Code.point("1"), UnorderedElementsAre(HdrFile)),
           Pair(Code.point("2"), UnorderedElementsAre(HdrFile)),
           Pair(Code.point("3"), UnorderedElementsAre(MainFile)),
-          Pair(Code.point("4"), UnorderedElementsAre(MainFile))
-              ));
+          Pair(Code.point("4"), UnorderedElementsAre(MainFile))));
 }
 
 class AnalyzeTest : public testing::Test {
 protected:
   TestInputs Inputs;
   PragmaIncludes PI;
   RecordedPP PP;
   AnalyzeTest() {
TEST(Hints, Ordering) {
   };
   EXPECT_LT(Hinted(Hints::None), Hinted(Hints::CompleteSymbol));
   EXPECT_LT(Hinted(Hints::CompleteSymbol), Hinted(Hints::PublicHeader));
   EXPECT_LT(Hinted(Hints::PublicHeader), Hinted(Hints::PreferredHeader));
   EXPECT_LT(Hinted(Hints::CompleteSymbol | Hints::PublicHeader),
             Hinted(Hints::PreferredHeader));
 }
 
+// Test ast traversal & redecl selection end-to-end for templates, as explicit
+// instantiations/specializations are not redecls of the primary template. We
+// need to make sure we're selecting the right ones.
+TEST_F(WalkUsedTest, TemplateDecls) {
+  llvm::Annotations Code(R"cpp(
+    #include "fwd.h"
+    #include "def.h"
+    #include "partial.h"
+    template <> struct $exp_spec^Foo<char> {};
+    template struct $exp^Foo<int>;
+    $full^Foo<int> x;
+    $implicit^Foo<bool> y;
+    $partial^Foo<int*> z;
+  )cpp");
+  Inputs.Code = Code.code();
+  Inputs.ExtraFiles["fwd.h"] = guard("template<typename> struct Foo;");
+  Inputs.ExtraFiles["def.h"] = guard("template<typename> struct Foo {};");
+  Inputs.ExtraFiles["partial.h"] =
+      guard("template<typename T> struct Foo<T*> {};");
+  TestAST AST(Inputs);
+  auto &SM = AST.sourceManager();
+  const auto *Fwd = SM.getFileManager().getFile("fwd.h").get();
+  const auto *Def = SM.getFileManager().getFile("def.h").get();
+  const auto *Partial = SM.getFileManager().getFile("partial.h").get();
+
+  EXPECT_THAT(
+      offsetToProviders(AST, SM),
+      AllOf(Contains(
+                Pair(Code.point("exp_spec"), UnorderedElementsAre(Fwd, Def))),
+            Contains(Pair(Code.point("exp"), UnorderedElementsAre(Fwd, Def))),
+            Contains(Pair(Code.point("full"), UnorderedElementsAre(Fwd, Def))),
+            Contains(
+                Pair(Code.point("implicit"), UnorderedElementsAre(Fwd, Def))),
+            Contains(
+                Pair(Code.point("partial"), UnorderedElementsAre(Partial)))));
+}
+
 } // namespace
 } // namespace clang::include_cleaner

clang-tools-extra/include-cleaner/unittests/WalkASTTest.cpp

 //===--- WalkASTTest.cpp ------------------------------------------- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "AnalysisInternal.h"
+#include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Frontend/TextDiagnostic.h"
 #include "clang/Testing/TestAST.h"
-#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/GenericUniformityImpl.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/raw_ostream.h"
 #include "llvm/Testing/Annotations/Annotations.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cstddef>
+#include <string>
 #include <unordered_map>
 #include <utility>
 #include <vector>
 
 namespace clang::include_cleaner {
 namespace {
+using testing::ElementsAre;
 
 // Specifies a test of which symbols are referenced by a piece of code.
 // Target should contain points annotated with the reference kind.
 // Example:
 //   Target:      int $explicit^foo();
 //   Referencing: int x = ^foo();
 // There must be exactly one referencing location marked.
-void testWalk(llvm::StringRef TargetCode, llvm::StringRef ReferencingCode) {
+// Returns target decls.
+std::vector<NamedDecl *> testWalk(llvm::StringRef TargetCode,
+                                  llvm::StringRef ReferencingCode) {
   llvm::Annotations Target(TargetCode);
   llvm::Annotations Referencing(ReferencingCode);
 
   TestInputs Inputs(Referencing.code());
   Inputs.ExtraFiles["target.h"] = Target.code().str();
   Inputs.ExtraArgs.push_back("-include");
   Inputs.ExtraArgs.push_back("target.h");
   Inputs.ExtraArgs.push_back("-std=c++17");
   TestAST AST(Inputs);
   const auto &SM = AST.sourceManager();
 
   // We're only going to record references from the nominated point,
   // to the target file.
   FileID ReferencingFile = SM.getMainFileID();
   SourceLocation ReferencingLoc =
       SM.getComposedLoc(ReferencingFile, Referencing.point());
   FileID TargetFile = SM.translateFile(
       llvm::cantFail(AST.fileManager().getFileRef("target.h")));
 
+  std::vector<NamedDecl *> TargetDecls;
   // Perform the walk, and capture the offsets of the referenced targets.
   std::unordered_map<RefType, std::vector<size_t>> ReferencedOffsets;
   for (Decl *D : AST.context().getTranslationUnitDecl()->decls()) {
     if (ReferencingFile != SM.getDecomposedExpansionLoc(D->getLocation()).first)
       continue;
     walkAST(*D, [&](SourceLocation Loc, NamedDecl &ND, RefType RT) {
       if (SM.getFileLoc(Loc) != ReferencingLoc)
         return;
       auto NDLoc = SM.getDecomposedLoc(SM.getFileLoc(ND.getLocation()));
       if (NDLoc.first != TargetFile)
         return;
       ReferencedOffsets[RT].push_back(NDLoc.second);
+      TargetDecls.push_back(&ND);
     });
   }
   for (auto &Entry : ReferencedOffsets)
     llvm::sort(Entry.second);
 
   // Compare results to the expected points.
   // For each difference, show the target point in context, like a diagnostic.
   std::string DiagBuf;
for (auto RT : {RefType::Explicit, RefType::Implicit, RefType::Ambiguous}) {
     for (auto Actual : ReferencedOffsets[RT])
       if (!llvm::is_contained(Target.points(RTStr), Actual))
         DiagnosePoint("location unexpectedly used with type " + RTStr, Actual);
   }
 
   // If there were any differences, we print the entire referencing code once.
   if (!DiagBuf.empty())
     ADD_FAILURE() << DiagBuf << "\nfrom code:\n" << ReferencingCode;
+  return TargetDecls;
 }
 
 TEST(WalkAST, DeclRef) {
   testWalk("int $explicit^x;", "int y = ^x;");
   testWalk("int $explicit^foo();", "int y = ^foo();");
   testWalk("namespace ns { int $explicit^x; }", "int y = ns::^x;");
   testWalk("struct S { static int $explicit^x; };", "int y = S::^x;");
   // Canonical declaration only.
   testWalk("extern int $explicit^x; int x;", "int y = ^x;");
   // Return type of `foo` isn't used.
   testWalk("struct S{}; S $explicit^foo();", "auto bar() { return ^foo(); }");
 }
 
 TEST(WalkAST, TagType) {
   testWalk("struct $explicit^S {};", "^S *y;");
   testWalk("enum $explicit^E {};", "^E *y;");
   testWalk("struct $explicit^S { static int x; };", "int y = ^S::x;");
   // One explicit call from the TypeLoc in constructor spelling, another
   // implicit reference through the constructor call.
   testWalk("struct $explicit^$implicit^S { static int x; };", "auto y = ^S();");
-  testWalk("template<typename> struct $explicit^Foo {};", "^Foo<int> x;");
-  testWalk(R"cpp(
+}
+
+MATCHER_P(HasKind, Kind, "") {
+  if (arg->getKind() == Kind)
+    return true;
+  *result_listener << "Got kind: " << arg->getDeclKindName();
+  return false;
+}
+
+TEST(WalkAST, ClassTemplates) {
+  // Explicit instantiation and (partial) specialization references primary
+  // template.
+  EXPECT_THAT(testWalk("template<typename> struct $explicit^Foo{};",
+                       "template struct ^Foo<int>;"),
+              ElementsAre(HasKind(Decl::CXXRecord)));
+  EXPECT_THAT(testWalk("template<typename> struct $explicit^Foo{};",
+                       "template<> struct ^Foo<int> {};"),
+              ElementsAre(HasKind(Decl::CXXRecord)));
+  EXPECT_THAT(testWalk("template<typename> struct $explicit^Foo{};",
+                       "template<typename T> struct ^Foo<T*> {};"),
+              ElementsAre(HasKind(Decl::CXXRecord)));
+
+  // Implicit instantiations references most relevant template.
+  EXPECT_THAT(
+      testWalk("template<typename> struct $explicit^Foo {};", "^Foo<int> x;"),
+      ElementsAre(HasKind(Decl::CXXRecord)));
+  EXPECT_THAT(testWalk(R"cpp(
     template<typename> struct Foo {};
     template<> struct $explicit^Foo<int> {};)cpp",
-           "^Foo<int> x;");
-  testWalk(R"cpp(
+                       "^Foo<int> x;"),
+              ElementsAre(HasKind(Decl::ClassTemplateSpecialization)));
+  EXPECT_THAT(testWalk(R"cpp(
     template<typename> struct Foo {};
     template<typename T> struct $explicit^Foo<T*> { void x(); };)cpp",
-           "^Foo<int *> x;");
-  testWalk(R"cpp(
-    template<typename> struct Foo {};
-    template struct $explicit^Foo<int>;)cpp",
-           "^Foo<int> x;");
+                       "^Foo<int *> x;"),
+              ElementsAre(HasKind(Decl::ClassTemplatePartialSpecialization)));
+  EXPECT_THAT(testWalk(R"cpp(
+    template<typename> struct $explicit^Foo {};
+    template struct Foo<int>;)cpp",
+                       "^Foo<int> x;"),
+              ElementsAre(HasKind(Decl::CXXRecord)));
   // FIXME: This is broken due to
   // https://github.com/llvm/llvm-project/issues/42259.
-  testWalk(R"cpp(
+  EXPECT_THAT(testWalk(R"cpp(
     template<typename T> struct $explicit^Foo { Foo(T); };
-    template<> struct Foo<int> { void get(); Foo(int); };)cpp",
-           "^Foo x(3);");
+    template<> struct Foo<int> { Foo(int); };)cpp",
+                       "^Foo x(3);"),
+              ElementsAre(HasKind(Decl::ClassTemplate)));
+}
+TEST(WalkAST, VarTemplates) {
+  // Explicit instantiation and (partial) specialization references primary
+  // template.
+  // FIXME: Explicit instantiations has wrong source location, they point at the
+  // primary template location (hence we drop the reference).
+  EXPECT_THAT(
+      testWalk("template<typename T> T Foo = 0;", "template int ^Foo<int>;"),
+      ElementsAre());
+  EXPECT_THAT(testWalk("template<typename T> T $explicit^Foo = 0;",
+                       "template<> int ^Foo<int> = 2;"),
+              ElementsAre(HasKind(Decl::Var)));
+  EXPECT_THAT(testWalk("template<typename T> T $explicit^Foo = 0;",
+                       "template<typename T> T* ^Foo<T*> = 1;"),
+              ElementsAre(HasKind(Decl::Var)));
+
+  // Implicit instantiations references most relevant template.
+  // FIXME: This points at implicit specialization, instead we should point to
+  // pattern.
+  EXPECT_THAT(testWalk(R"cpp(
+    template <typename T> T $explicit^Foo = 0;)cpp",
+                       "int z = ^Foo<int>;"),
+              ElementsAre(HasKind(Decl::VarTemplateSpecialization)));
+  EXPECT_THAT(testWalk(R"cpp(
+    template<typename T> T Foo = 0;
+    template<> int $explicit^Foo<int> = 1;)cpp",
+                       "int x = ^Foo<int>;"),
+              ElementsAre(HasKind(Decl::VarTemplateSpecialization)));
+  // FIXME: This points at implicit specialization, instead we should point to
+  // explicit partial specializaiton pattern.
+  EXPECT_THAT(testWalk(R"cpp(
+    template<typename T> T Foo = 0;
+    template<typename T> T* $explicit^Foo<T*> = nullptr;)cpp",
+                       "int *x = ^Foo<int *>;"),
+              ElementsAre(HasKind(Decl::VarTemplateSpecialization)));
+  EXPECT_THAT(testWalk(R"cpp(
+    template<typename T> T $explicit^Foo = 0;
+    template int Foo<int>;)cpp",
+                       "int x = ^Foo<int>;"),
+              ElementsAre(HasKind(Decl::VarTemplateSpecialization)));
+}
+TEST(WalkAST, FunctionTemplates) {
+  // Explicit instantiation and (partial) specialization references primary
+  // template.
+  // FIXME: Explicit instantiations has wrong source location, they point at the
+  // primary template location (hence we drop the reference).
+  EXPECT_THAT(testWalk("template<typename T> void foo(T) {}",
+                       "template void ^foo<int>(int);"),
+              ElementsAre());
+  // FIXME: Report specialized template as used from explicit specializations.
+  EXPECT_THAT(testWalk("template<typename T> void foo(T);",
+                       "template<> void ^foo<int>(int);"),
+              ElementsAre());
+  EXPECT_THAT(testWalk("template<typename T> void foo(T) {}",
+                       "template<typename T> void ^foo(T*) {}"),
+              ElementsAre());
+
+  // Implicit instantiations references most relevant template.
+  EXPECT_THAT(testWalk(R"cpp(
+    template <typename T> void $explicit^foo() {})cpp",
+                       "auto x = []{ ^foo<int>(); };"),
+              ElementsAre(HasKind(Decl::FunctionTemplate)));
+  // FIXME: DeclRefExpr points at primary template, not the specialization.
+  EXPECT_THAT(testWalk(R"cpp(
+    template<typename T> void $explicit^foo() {}
+    template<> void foo<int>(){})cpp",
+                       "auto x = []{ ^foo<int>(); };"),
+              ElementsAre(HasKind(Decl::FunctionTemplate)));
+  EXPECT_THAT(testWalk(R"cpp(
+    template<typename T> void $explicit^foo() {};
+    template void foo<int>();)cpp",
+                       "auto x = [] { ^foo<int>(); };"),
+              ElementsAre(HasKind(Decl::FunctionTemplate)));
 }
 
 TEST(WalkAST, Alias) {
   testWalk(R"cpp(
     namespace ns { int x; }
     using ns::$explicit^x;
   )cpp",
            "int y = ^x;");
testWalk(R"cpp(
       using ns::$explicit^S;)cpp",
            "^S<int> x;");
   testWalk(R"cpp(
       namespace ns {
         template <typename T> struct S { S(T);};
         template <typename T> S(T t) -> S<T>;
       }
       using ns::$explicit^S;)cpp",
            "^S x(123);");
   testWalk("template<typename> struct $explicit^S {};",
            R"cpp(
       template <template <typename> typename> struct X {};
       X<^S> x;)cpp");
   testWalk("template<typename T> struct $explicit^S { S(T); };", "^S s(42);");
 }
 
 TEST(WalkAST, MemberExprs) {