[IncludeCleaner] Handle more C++ constructs

[kadircet]

Summary

This brings IncludeCleaner's reference discovery from AST to the parity
with current implementation in clangd. Some highlights:

• Handling of MemberExprs, only the member declaration is marked as referenced and not the container, unlike clangd.
• Constructor calls, only the constructor and not the container, unlike clangd.
• All the possible candidates for unresolved overloads, same as clangd.
• All the shadow decls for using-decls, same as clangd.
• Declarations for definitions of enums with an underlying type and functions, same as clangd.
• Using typelocs, using templatenames and typedefs only reference the found decl, same as clangd.
• Template specializations only reference the primary template, not the explicit specializations, to be fixed.
• Expr types aren't marked as used, unlike clangd.

Going forward, we can consider having signals to indicate type of a
reference (e.g. implicit signal for type of an expr) so that the
applications can perform a filtering based on their needs.
At the moment the biggest discrepancy is around type of exprs, i.e. not
marking containers for member/constructor accesses. I believe this is
the right model since the declaration of the member and the container
should be available in a single file (modulo macros).

[sammccall]

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

54

nit: inline?

54

should this be the founddecl instead of the memberdecl?

65

I think we need a policy knob for this, to decide whether to over or underestimate.
This would be the wrong behavior for missing-includes analysis.

65

comment echoes the code, say why instead

71

I wonder if this is correct enough.

This brings a set of overloads into scope, the intention may be to bring a particular overload with others as harmless side effects: consider using std::swap.
In this case, inserting includes for all the overloads that happened to be visible would be too much.

Possible behaviors:

• what we do here
• only do this if overestimate=true
• if overestimate=false, only include those USDs marked as referenced (not sure if they actually get marked appropriately, the bit exists)

78

comment echoes the code, say why instead

111

nit: *explicit* specializations?

[kadircet]

• Adress comments

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

54

right, forgot about these. also added a test.

65

i agree that this needs a knob. it's just unclear at which level currently, i am putting together a doc to have a better decision here (mostly to post vs pre filter).

i'd rather move forward with this version, to prepare grounds for the tidy check and clangd usage based on this library, and address these issues in a new iteration.

71

i agree, basically the same things as I mentioned above, we should definitely have a way to filter these.

[sammccall]

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

65

OK, add a FIXME?

71

ack, again let's mark this as incomplete somehow (esp because this one is subtle)

[kadircet]

• Rebase
• Add FIXMEs

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/AST/Decl.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
 #include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/TemplateName.h"
+#include "clang/AST/Type.h"
+#include "clang/AST/TypeLoc.h"
+#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Casting.h"
 
 namespace clang::include_cleaner {
 namespace {
 using DeclCallback = llvm::function_ref<void(SourceLocation, NamedDecl &)>;
 
 class ASTWalker : public RecursiveASTVisitor<ASTWalker> {
   DeclCallback Callback;
 
+  bool handleTemplateName(SourceLocation Loc, TemplateName TN) {
+    // For using-templates, only mark the alias.
+    if (auto *USD = TN.getAsUsingShadowDecl()) {
+      report(Loc, USD);
+      return true;
+    }
+    report(Loc, TN.getAsTemplateDecl());
+    return true;
+  }
+
   void report(SourceLocation Loc, NamedDecl *ND) {
     if (!ND || Loc.isInvalid())
       return;
     Callback(Loc, *cast<NamedDecl>(ND->getCanonicalDecl()));
   }
 
 public:
   ASTWalker(DeclCallback Callback) : Callback(Callback) {}
 
+  bool VisitDeclRefExpr(DeclRefExpr *DRE) {
+    report(DRE->getLocation(), DRE->getFoundDecl());
+    return true;
+  }
+
+  bool VisitMemberExpr(MemberExpr *E) {
+    report(E->getMemberLoc(), E->getFoundDecl().getDecl());
+    return true;
+  }
+
+  bool VisitCXXConstructExpr(CXXConstructExpr *E) {
+    report(E->getLocation(), E->getConstructor());
+    return true;
+  }
+
+  bool VisitOverloadExpr(OverloadExpr *E) {
+    // Since we can't prove which overloads are used, report all of them.
+    // FIXME: Provide caller with the ability to make a decision for such uses.
+    llvm::for_each(E->decls(),
+                   [this, E](NamedDecl *D) { report(E->getNameLoc(), D); });
+    return true;
+  }
+
+  bool VisitUsingDecl(UsingDecl *UD) {
+    // FIXME: Provide caller with the ability to tell apart used/non-used
+    // targets.
+    for (const auto *Shadow : UD->shadows())
+      report(UD->getLocation(), Shadow->getTargetDecl());
+    return true;
+  }
+
+  bool VisitFunctionDecl(FunctionDecl *FD) {
+    // Mark declaration from definition as it needs type-checking.
+    if (FD->isThisDeclarationADefinition())
+      report(FD->getLocation(), FD);
+    return true;
+  }
+
+  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;
+  }
+
+  // TypeLoc visitors.
+  bool VisitUsingTypeLoc(UsingTypeLoc TL) {
+    report(TL.getNameLoc(), TL.getFoundDecl());
+    return true;
+  }
+
   bool VisitTagTypeLoc(TagTypeLoc TTL) {
     report(TTL.getNameLoc(), TTL.getDecl());
     return true;
   }
 
-  bool VisitDeclRefExpr(DeclRefExpr *DRE) {
-    report(DRE->getLocation(), DRE->getFoundDecl());
+  bool VisitTypedefTypeLoc(TypedefTypeLoc TTL) {
+    report(TTL.getNameLoc(), TTL.getTypedefNameDecl());
     return true;
   }
+
+  bool VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc TL) {
+    // FIXME: Handle explicit specializations.
+    return handleTemplateName(TL.getTemplateNameLoc(),
+                              TL.getTypePtr()->getTemplateName());
+  }
+
+  bool VisitDeducedTemplateSpecializationTypeLoc(
+      DeducedTemplateSpecializationTypeLoc TL) {
+    // FIXME: Handle specializations.
+    return handleTemplateName(TL.getTemplateNameLoc(),
+                              TL.getTypePtr()->getTemplateName());
+  }
+
+  bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &TL) {
+    auto &Arg = TL.getArgument();
+    // Template-template parameters require special attention, as there's no
+    // TemplateNameLoc.
+    if (Arg.getKind() == TemplateArgument::Template ||
+        Arg.getKind() == TemplateArgument::TemplateExpansion)
+      return handleTemplateName(TL.getLocation(),
+                                Arg.getAsTemplateOrTemplatePattern());
+    return RecursiveASTVisitor::TraverseTemplateArgumentLoc(TL);
+  }
 };
 
 } // namespace
 
 void walkAST(Decl &Root, DeclCallback Callback) {
   ASTWalker(Callback).TraverseDecl(&Root);
 }
 
 } // namespace clang::include_cleaner

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

 using testing::UnorderedElementsAre;
 
 TEST(WalkUsed, Basic) {
   // FIXME: Have a fixture for setting up tests.
   llvm::Annotations HeaderCode(R"cpp(
   void foo();
   namespace std { class vector {}; })cpp");
   llvm::Annotations Code(R"cpp(
-  void bar() {
+  void $bar^bar() {
     $foo^foo();
-    std::$vector^vector v;
+    std::$vector^vector $vconstructor^v;
   }
   )cpp");
   TestInputs Inputs(Code.code());
   Inputs.ExtraFiles["header.h"] = HeaderCode.code().str();
   Inputs.ExtraArgs.push_back("-include");
   Inputs.ExtraArgs.push_back("header.h");
   TestAST AST(Inputs);
 
   llvm::SmallVector<Decl *> TopLevelDecls;
   for (Decl *D : AST.context().getTranslationUnitDecl()->decls()) {
     TopLevelDecls.emplace_back(D);
   }
 
   auto &SM = AST.sourceManager();
   llvm::DenseMap<size_t, std::vector<Header>> OffsetToProviders;
   walkUsed(TopLevelDecls, [&](SourceLocation RefLoc, Symbol S,
                               llvm::ArrayRef<Header> Providers) {
     auto [FID, Offset] = SM.getDecomposedLoc(RefLoc);
     EXPECT_EQ(FID, SM.getMainFileID());
     OffsetToProviders.try_emplace(Offset, Providers.vec());
   });
-  auto HeaderFile = AST.fileManager().getFile("header.h").get();
+  auto HeaderFile = Header(AST.fileManager().getFile("header.h").get());
+  auto MainFile = Header(SM.getFileEntryForID(SM.getMainFileID()));
+  auto VectorSTL = Header(tooling::stdlib::Header::named("<vector>").value());
   EXPECT_THAT(
       OffsetToProviders,
       UnorderedElementsAre(
-          Pair(Code.point("foo"), UnorderedElementsAre(Header(HeaderFile))),
-          Pair(Code.point("vector"),
-               UnorderedElementsAre(Header(
-                   tooling::stdlib::Header::named("<vector>").value())))));
+          Pair(Code.point("bar"), UnorderedElementsAre(MainFile)),
+          Pair(Code.point("foo"), UnorderedElementsAre(HeaderFile)),
+          Pair(Code.point("vector"), UnorderedElementsAre(VectorSTL)),
+          Pair(Code.point("vconstructor"), UnorderedElementsAre(VectorSTL))));
 }
 
 } // namespace
 } // namespace clang::include_cleaner

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

 void 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());

 
 TEST(WalkAST, DeclRef) {
   testWalk("int ^x;", "int y = ^x;");
   testWalk("int ^foo();", "int y = ^foo();");
   testWalk("namespace ns { int ^x; }", "int y = ns::^x;");
   testWalk("struct S { static int ^x; };", "int y = S::^x;");
   // Canonical declaration only.
   testWalk("extern int ^x; int x;", "int y = ^x;");
+  // Return type of `foo` isn't used.
+  testWalk("struct S{}; S ^foo();", "auto bar() { return ^foo(); }");
 }
 
 TEST(WalkAST, TagType) {
   testWalk("struct ^S {};", "^S *y;");
   testWalk("enum ^E {};", "^E *y;");
   testWalk("struct ^S { static int x; };", "int y = ^S::x;");
 }
 
 TEST(WalkAST, Alias) {
   testWalk(R"cpp(
     namespace ns { int x; }
     using ns::^x;
   )cpp",
            "int y = ^x;");
+  testWalk("using ^foo = int;", "^foo x;");
+  testWalk("struct S {}; using ^foo = S;", "^foo x;");
+}
+
+TEST(WalkAST, Using) {
+  testWalk("namespace ns { void ^x(); void ^x(int); }", "using ns::^x;");
+  testWalk("namespace ns { struct S; } using ns::^S;", "^S *s;");
+}
+
+TEST(WalkAST, Namespaces) {
+  testWalk("namespace ns { void x(); }", "using namespace ^ns;");
+}
+
+TEST(WalkAST, TemplateNames) {
+  testWalk("template<typename> struct ^S {};", "^S<int> s;");
+  // FIXME: Template decl has the wrong primary location for type-alias template
+  // decls.
   testWalk(R"cpp(
-    namespace ns { struct S; } // Not used
-    using ns::S; // FIXME: S should be used
-  )cpp",
-           "^S *x;");
+      template <typename> struct S {};
+      template <typename T> ^using foo = S<T>;)cpp",
+           "^foo<int> x;");
+  testWalk(R"cpp(
+      namespace ns {template <typename> struct S {}; }
+      using ns::^S;)cpp",
+           "^S<int> x;");
+  testWalk("template<typename> struct ^S {};",
+           R"cpp(
+      template <template <typename> typename> struct X {};
+      X<^S> x;)cpp");
+  testWalk("template<typename T> struct ^S { S(T); };", "^S s(42);");
+  // Should we mark the specialization instead?
+  testWalk("template<typename> struct ^S {}; template <> struct S<int> {};",
+           "^S<int> s;");
+}
+
+TEST(WalkAST, MemberExprs) {
+  testWalk("struct S { void ^foo(); };", "void foo() { S{}.^foo(); }");
+  testWalk("struct S { void foo(); }; struct X : S { using S::^foo; };",
+           "void foo() { X{}.^foo(); }");
+}
+
+TEST(WalkAST, ConstructExprs) {
+  testWalk("struct ^S {};", "S ^t;");
+  testWalk("struct S { ^S(int); };", "S ^t(42);");
+}
+
+TEST(WalkAST, Functions) {
+  // Definition uses declaration, not the other way around.
+  testWalk("void ^foo();", "void ^foo() {}");
+  testWalk("void foo() {}", "void ^foo();");
+
+  // Unresolved calls marks all the overloads.
+  testWalk("void ^foo(int); void ^foo(char);",
+           "template <typename T> void bar() { ^foo(T{}); }");
+}
+
+TEST(WalkAST, Enums) {
+  testWalk("enum E { ^A = 42, B = 43 };", "int e = ^A;");
+  testWalk("enum class ^E : int;", "enum class ^E : int {};");
+  testWalk("enum class E : int {};", "enum class ^E : int ;");
 }
 
 } // namespace
 } // namespace clang::include_cleaner