[include-cleaner] Traverse implicit template instantations if the templates are inside the main file.

[hokein]

Summary

This patch tweaks the WalkAST to traverse imlicit template
instantations, presumably this is a big behavior change.

when traversing impplicit instantations, all reported references are
implicit as they are not spelled in the source code, thus they are not
contributed to the #include insertions.

This would fix some unused-include false positives where we report an
#include is unused despite the used references is in an instantiated
body.

[ilya-biryukov]

Though I'm not a reviewer, I was looking through the emails and found this change interesting. This is not intended to block the review in any way, just trying to get a picture of the direction include-cleaner is taking.

Is this a digression from the initial idea of include-what-you-spell?
I thought that the whole point was in trying to make the analysis more "local" and avoid relying on implicit instantiations.

What is our strategy on balancing the number of false-positive removals we produce with the number of false-negatives where we don't remove something that's actually unused?

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

 #include "clang/AST/TemplateName.h"
 #include "clang/AST/Type.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/Specifiers.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
+#include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Casting.h"
 
 namespace clang::include_cleaner {
 namespace {
 using DeclCallback =
     llvm::function_ref<void(SourceLocation, NamedDecl &, RefType)>;
 
 class ASTWalker : public RecursiveASTVisitor<ASTWalker> {
   DeclCallback Callback;
+  // A flag indicating whether we are in the visiting-implicit-instantiations
+  // mode, controlling the RAV behavior.
+  bool VisitTemplateIntantiations = false;
 
   void report(SourceLocation Loc, NamedDecl *ND,
               RefType RT = RefType::Explicit) {
     if (!ND || Loc.isInvalid())
       return;
+    // If we're traversing implicit instantiations, all reported references are
+    // implicit regardlessly.
+    if (VisitTemplateIntantiations)
+      RT = RefType::Implicit;
     Callback(Loc, *cast<NamedDecl>(ND->getCanonicalDecl()), RT);
   }
 
   NamedDecl *resolveTemplateName(TemplateName TN) {
     // For using-templates, only mark the alias.
     if (auto *USD = TN.getAsUsingShadowDecl())
       return USD;
     return TN.getAsTemplateDecl();
if (auto *Pat = TD->getTemplateInstantiationPattern())
       return Pat;
     // For explicit specializations, use the specialized decl directly.
     return TD;
   }
 
 public:
   ASTWalker(DeclCallback Callback) : Callback(Callback) {}
 
+  bool shouldVisitTemplateInstantiations() const {
+    return VisitTemplateIntantiations;
+  }
+  // We traverse the implicit template instantiations if they are inside of the
+  // main file. References from template instantiations are always implicit, 
+  // as they are not spelled in the source code.
+  template <typename T, typename T2>
+  bool traverseImplicitInstantiations(const T *TemplateDecl,
+                                      T2 GetSpecializationKind) {
+    auto &SM = TemplateDecl->getASTContext().getSourceManager();
+    for (auto *Spec : TemplateDecl->specializations()) {
+      for (auto *RD : Spec->redecls()) {
+        if (!SM.isWrittenInMainFile(SM.getExpansionLoc(RD->getLocation())))
+          continue;
+        auto SpecKind = GetSpecializationKind(RD);
+        if (SpecKind != TSK_Undeclared && SpecKind != TSK_ImplicitInstantiation)
+          continue;
+        auto Restore = llvm::make_scope_exit(
+            [this]() { VisitTemplateIntantiations = false; });
+        VisitTemplateIntantiations = true;
+        if (!TraverseDecl(Spec))
+          return false;
+      }
+    }
+    return false;
+  }
+  bool TraverseClassTemplateDecl(ClassTemplateDecl *D) {
+    if (!RecursiveASTVisitor::TraverseClassTemplateDecl(D))
+      return false;
+    return traverseImplicitInstantiations(D, [](Decl *D) {
+      return llvm::cast<ClassTemplateSpecializationDecl>(D)
+          ->getSpecializationKind();
+    });
+  }
+  bool TraverseVarTemplateDecl(VarTemplateDecl *D) {
+    if (!RecursiveASTVisitor::TraverseVarTemplateDecl(D))
+      return false;
+    return traverseImplicitInstantiations(D, [](Decl *D) {
+      return llvm::cast<VarTemplateSpecializationDecl>(D)
+          ->getSpecializationKind();
+    });
+  }
+  bool TraverseFunctionTemplateDecl(FunctionTemplateDecl *D) {
+    if (!RecursiveASTVisitor::TraverseFunctionTemplateDecl(D))
+      return false;
+    return traverseImplicitInstantiations(D, [](FunctionDecl *FD) {
+      return FD->getTemplateSpecializationKind();
+    });
+  }
+
+  bool TraverseLambdaExpr(LambdaExpr *LE) {
+    if (!RecursiveASTVisitor::TraverseLambdaExpr(LE))
+      return false;
+    // By default, lambda class decl is not traversed by default (unless
+    // shouldVisitImplicitCode is true), here we traverse the operator call
+    // operator instantiations manually.
+    if (const FunctionTemplateDecl *CallOperatorMember =
+            LE->getLambdaClass()->getDependentLambdaCallOperator()) {
+      return traverseImplicitInstantiations(
+          CallOperatorMember,
+          [](FunctionDecl *FD) { return FD->getTemplateSpecializationKind(); });
+    }
+    return true;
+  }
+
   // 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).
   // Unless we're using an operator defined as a member, in such cases treat
   // these as regular member references.
   bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *S) {
     if (!WalkUpFromCXXOperatorCallExpr(S))
       return false;

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

 }
 
 TEST(WalkAST, Enums) {
   testWalk("enum E { $explicit^A = 42, B = 43 };", "int e = ^A;");
   testWalk("enum class $explicit^E : int;", "enum class ^E : int {};");
   testWalk("enum class E : int {};", "enum class ^E : int ;");
 }
 
+TEST(WalkAST, ImplicitInstantiations) {
+  // Class template instantations.
+  testWalk(R"cpp(
+      struct $implicit^Foo {int a;};
+      const Foo& getFoo();)cpp",
+           R"cpp(
+      template<class T>
+      struct Bar {
+         Bar(const T& t) { t.^a;};
+      };
+      void test() {
+        auto k = Bar(getFoo());
+      })cpp");
+  // Function template instantations.
+  testWalk(R"cpp(
+      struct $implicit^Foo {int a;};
+      const Foo& getFoo();)cpp",
+           R"cpp(
+      template<class T>
+      int getT(const T& t) {
+        return t.^a;
+      }
+
+      void test() {
+        auto k = getT(getFoo());
+      })cpp");
+  // Var template instantations.
+  testWalk(R"cpp(
+      struct $implicit^Foo {int a;};
+      const Foo getFoo();)cpp",
+           R"cpp(
+      template<class T>
+      int foo = T().^a;
+
+      void test() {
+        foo<decltype(getFoo())>;
+      })cpp");
+
+  // Generic lambdas, verified the implicit instantiations of the operator call
+  // method are traversed.
+  testWalk(R"cpp(
+      struct $implicit^Foo {int a;};
+      struct $implicit^Bar {int a;};
+      const Foo& getFoo();
+      const Bar& getBar();)cpp",
+           R"cpp(
+      void test() {
+        auto Generic = [](auto x) { x.^a; };
+        Generic(getFoo());
+        Generic(getBar());
+      })cpp");
+}
+
 } // namespace
 } // namespace clang::include_cleaner