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

   1 //===--- WalkAST.cpp - Find declaration references in the AST -------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "AnalysisInternal.h"
  10 #include "clang-include-cleaner/Types.h"
  11 #include "clang/AST/ASTFwd.h"
  12 #include "clang/AST/Decl.h"
  13 #include "clang/AST/DeclCXX.h"
  14 #include "clang/AST/DeclTemplate.h"
  15 #include "clang/AST/Expr.h"
  16 #include "clang/AST/ExprCXX.h"
  17 #include "clang/AST/RecursiveASTVisitor.h"
  18 #include "clang/AST/TemplateBase.h"
  19 #include "clang/AST/TemplateName.h"
  20 #include "clang/AST/Type.h"
  21 #include "clang/AST/TypeLoc.h"
  22 #include "clang/Basic/IdentifierTable.h"
  23 #include "clang/Basic/SourceLocation.h"
  24 #include "clang/Basic/Specifiers.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/STLFunctionalExtras.h"
  27 #include "llvm/ADT/SmallVector.h"
  28 #include "llvm/Support/Casting.h"
  29
  30 namespace clang::include_cleaner {
  31 namespace {
  32 using DeclCallback =
  33     llvm::function_ref<void(SourceLocation, NamedDecl &, RefType)>;
  34
  35 class ASTWalker : public RecursiveASTVisitor<ASTWalker> {
  36   DeclCallback Callback;
  37
  38   void report(SourceLocation Loc, NamedDecl *ND,
  39               RefType RT = RefType::Explicit) {
  40     if (!ND || Loc.isInvalid())
  41       return;
  42     Callback(Loc, *cast<NamedDecl>(ND->getCanonicalDecl()), RT);
  43   }
  44
  45   NamedDecl *resolveTemplateName(TemplateName TN) {
  46     // For using-templates, only mark the alias.
  47     if (auto *USD = TN.getAsUsingShadowDecl())
  48       return USD;
  49     return TN.getAsTemplateDecl();
  50   }
  51   NamedDecl *getMemberProvider(QualType Base) {
  52     if (Base->isPointerType())
  53       return getMemberProvider(Base->getPointeeType());
  54     // Unwrap the sugar ElaboratedType.
  55     if (const auto *ElTy = dyn_cast<ElaboratedType>(Base))
  56       return getMemberProvider(ElTy->getNamedType());
  57
  58     if (const auto *TT = dyn_cast<TypedefType>(Base))
  59       return TT->getDecl();
  60     if (const auto *UT = dyn_cast<UsingType>(Base))
  61       return UT->getFoundDecl();
  62     // A heuristic: to resolve a template type to **only** its template name.
  63     // We're only using this method for the base type of MemberExpr, in general
  64     // the template provides the member, and the critical case `unique_ptr<Foo>`
  65     // is supported (the base type is a Foo*).
  66     //
  67     // There are some exceptions that this heuristic could fail (dependent base,
  68     // dependent typealias), but we believe these are rare.
  69     if (const auto *TST = dyn_cast<TemplateSpecializationType>(Base))
  70       return resolveTemplateName(TST->getTemplateName());
  71     return Base->getAsRecordDecl();
  72   }
  73   // Templated as TemplateSpecializationType and
  74   // DeducedTemplateSpecializationType doesn't share a common base.
  75   template <typename T>
  76   // Picks the most specific specialization for a
  77   // (Deduced)TemplateSpecializationType, while prioritizing using-decls.
  78   NamedDecl *getMostRelevantTemplatePattern(const T *TST) {
  79     // In case of exported template names always prefer the using-decl. This
  80     // implies we'll point at the using-decl even when there's an explicit
  81     // specializaiton using the exported name, but that's rare.
  82     auto *ND = resolveTemplateName(TST->getTemplateName());
  83     if (llvm::isa_and_present<UsingShadowDecl, TypeAliasTemplateDecl>(ND))
  84       return ND;
  85     // This is the underlying decl used by TemplateSpecializationType, can be
  86     // null when type is dependent or not resolved to a pattern yet.
  87     // If so, fallback to primary template.
  88     CXXRecordDecl *TD = TST->getAsCXXRecordDecl();
  89     if (!TD || TD->getTemplateSpecializationKind() == TSK_Undeclared)
  90       return ND;
  91     // We ignore explicit instantiations. This might imply marking the wrong
  92     // declaration as used in specific cases, but seems like the right trade-off
  93     // in general (e.g. we don't want to include a custom library that has an
  94     // explicit specialization of a common type).
  95     if (auto *Pat = TD->getTemplateInstantiationPattern())
  96       return Pat;
  97     // For explicit specializations, use the specialized decl directly.
  98     return TD;
  99   }
 100
 101 public:
 102   ASTWalker(DeclCallback Callback) : Callback(Callback) {}
 103
 104   // Operators are almost always ADL extension points and by design references
 105   // to them doesn't count as uses (generally the type should provide them, so
 106   // ignore them).
 107   // Unless we're using an operator defined as a member, in such cases treat
 108   // these as regular member references.
 109   bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *S) {
 110     if (!WalkUpFromCXXOperatorCallExpr(S))
 111       return false;
 112     if (auto *CD = S->getCalleeDecl()) {
 113       if (llvm::isa<CXXMethodDecl>(CD)) {
 114         // Treat this as a regular member reference.
 115         report(S->getOperatorLoc(), getMemberProvider(S->getArg(0)->getType()),
 116                RefType::Implicit);
 117       } else {
 118         report(S->getOperatorLoc(), llvm::dyn_cast<NamedDecl>(CD),
 119                RefType::Implicit);
 120       }
 121     }
 122     for (auto *Arg : S->arguments())
 123       if (!TraverseStmt(Arg))
 124         return false;
 125     return true;
 126   }
 127
 128   bool VisitDeclRefExpr(DeclRefExpr *DRE) {
 129     // Static class members are handled here, as they don't produce MemberExprs.
 130     if (DRE->getFoundDecl()->isCXXClassMember()) {
 131       if (auto *Qual = DRE->getQualifier())
 132         report(DRE->getLocation(), Qual->getAsRecordDecl(), RefType::Implicit);
 133     } else {
 134       report(DRE->getLocation(), DRE->getFoundDecl());
 135     }
 136     return true;
 137   }
 138
 139   bool VisitMemberExpr(MemberExpr *E) {
 140     // Reporting a usage of the member decl would cause issues (e.g. force
 141     // including the base class for inherited members). Instead, we report a
 142     // usage of the base type of the MemberExpr, so that e.g. code
 143     // `returnFoo().bar` can keep #include "foo.h" (rather than inserting
 144     // "bar.h" for the underlying base type `Bar`).
 145     QualType Type = E->getBase()->IgnoreImpCasts()->getType();
 146     report(E->getMemberLoc(), getMemberProvider(Type), RefType::Implicit);
 147     return true;
 148   }
 149   bool VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
 150     report(E->getMemberLoc(), getMemberProvider(E->getBaseType()),
 151            RefType::Implicit);
 152     return true;
 153   }
 154
 155   bool VisitCXXConstructExpr(CXXConstructExpr *E) {
 156     // Always treat consturctor calls as implicit. We'll have an explicit
 157     // reference for the constructor calls that mention the type-name (through
 158     // TypeLocs). This reference only matters for cases where there's no
 159     // explicit syntax at all or there're only braces.
 160     report(E->getLocation(), getMemberProvider(E->getType()),
 161            RefType::Implicit);
 162     return true;
 163   }
 164
 165   bool VisitOverloadExpr(OverloadExpr *E) {
 166     // Since we can't prove which overloads are used, report all of them.
 167     llvm::for_each(E->decls(), [this, E](NamedDecl *D) {
 168       report(E->getNameLoc(), D, RefType::Ambiguous);
 169     });
 170     return true;
 171   }
 172
 173   // Report all (partial) specializations of a class/var template decl.
 174   template <typename TemplateDeclType, typename ParitialDeclType>
 175   void reportSpecializations(SourceLocation Loc, NamedDecl *ND) {
 176     const auto *TD = llvm::dyn_cast<TemplateDeclType>(ND);
 177     if (!TD)
 178       return;
 179
 180     for (auto *Spec : TD->specializations())
 181       report(Loc, Spec, RefType::Ambiguous);
 182     llvm::SmallVector<ParitialDeclType *> PartialSpecializations;
 183     TD->getPartialSpecializations(PartialSpecializations);
 184     for (auto *PartialSpec : PartialSpecializations)
 185       report(Loc, PartialSpec, RefType::Ambiguous);
 186   }
 187   bool VisitUsingDecl(UsingDecl *UD) {
 188     for (const auto *Shadow : UD->shadows()) {
 189       auto *TD = Shadow->getTargetDecl();
 190       auto IsUsed = TD->isUsed() || TD->isReferenced();
 191       report(UD->getLocation(), TD,
 192              IsUsed ? RefType::Explicit : RefType::Ambiguous);
 193
 194       // All (partial) template specializations are visible via a using-decl,
 195       // However a using-decl only refers to the primary template (per C++ name
 196       // lookup). Thus, we need to manually report all specializations.
 197       reportSpecializations<ClassTemplateDecl,
 198                             ClassTemplatePartialSpecializationDecl>(
 199           UD->getLocation(), TD);
 200       reportSpecializations<VarTemplateDecl,
 201                             VarTemplatePartialSpecializationDecl>(
 202           UD->getLocation(), TD);
 203       if (const auto *FTD = llvm::dyn_cast<FunctionTemplateDecl>(TD))
 204         for (auto *Spec : FTD->specializations())
 205           report(UD->getLocation(), Spec, RefType::Ambiguous);
 206     }
 207     return true;
 208   }
 209
 210   bool VisitFunctionDecl(FunctionDecl *FD) {
 211     // Mark declaration from definition as it needs type-checking.
 212     if (FD->isThisDeclarationADefinition())
 213       report(FD->getLocation(), FD);
 214     return true;
 215   }
 216   bool VisitVarDecl(VarDecl *VD) {
 217     // Ignore the parameter decl itself (its children were handled elsewhere),
 218     // as they don't contribute to the main-file #include.
 219     if (llvm::isa<ParmVarDecl>(VD))
 220       return true;
 221     // Mark declaration from definition as it needs type-checking.
 222     if (VD->isThisDeclarationADefinition())
 223       report(VD->getLocation(), VD);
 224     return true;
 225   }
 226
 227   bool VisitEnumDecl(EnumDecl *D) {
 228     // Definition of an enum with an underlying type references declaration for
 229     // type-checking purposes.
 230     if (D->isThisDeclarationADefinition() && D->getIntegerTypeSourceInfo())
 231       report(D->getLocation(), D);
 232     return true;
 233   }
 234
 235   // Report a reference from explicit specializations to the specialized
 236   // template. Implicit ones are filtered out by RAV and explicit instantiations
 237   // are already traversed through typelocs.
 238   bool
 239   VisitClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *CTSD) {
 240     if (CTSD->isExplicitSpecialization())
 241       report(CTSD->getLocation(),
 242              CTSD->getSpecializedTemplate()->getTemplatedDecl());
 243     return true;
 244   }
 245   bool VisitVarTemplateSpecializationDecl(VarTemplateSpecializationDecl *VTSD) {
 246     if (VTSD->isExplicitSpecialization())
 247       report(VTSD->getLocation(),
 248              VTSD->getSpecializedTemplate()->getTemplatedDecl());
 249     return true;
 250   }
 251
 252   // TypeLoc visitors.
 253   void reportType(SourceLocation RefLoc, NamedDecl *ND) {
 254     // Reporting explicit references to types nested inside classes can cause
 255     // issues, e.g. a type accessed through a derived class shouldn't require
 256     // inclusion of the base.
 257     // Hence we report all such references as implicit. The code must spell the
 258     // outer type-location somewhere, which will trigger an explicit reference
 259     // and per IWYS, it's that spelling's responsibility to bring in necessary
 260     // declarations.
 261     RefType RT = llvm::isa<RecordDecl>(ND->getDeclContext())
 262                      ? RefType::Implicit
 263                      : RefType::Explicit;
 264     return report(RefLoc, ND, RT);
 265   }
 266
 267   bool VisitUsingTypeLoc(UsingTypeLoc TL) {
 268     reportType(TL.getNameLoc(), TL.getFoundDecl());
 269     return true;
 270   }
 271
 272   bool VisitTagTypeLoc(TagTypeLoc TTL) {
 273     reportType(TTL.getNameLoc(), TTL.getDecl());
 274     return true;
 275   }
 276
 277   bool VisitTypedefTypeLoc(TypedefTypeLoc TTL) {
 278     reportType(TTL.getNameLoc(), TTL.getTypedefNameDecl());
 279     return true;
 280   }
 281
 282   bool VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc TL) {
 283     reportType(TL.getTemplateNameLoc(),
 284                getMostRelevantTemplatePattern(TL.getTypePtr()));
 285     return true;
 286   }
 287
 288   bool VisitDeducedTemplateSpecializationTypeLoc(
 289       DeducedTemplateSpecializationTypeLoc TL) {
 290     reportType(TL.getTemplateNameLoc(),
 291                getMostRelevantTemplatePattern(TL.getTypePtr()));
 292     return true;
 293   }
 294
 295   bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &TL) {
 296     auto &Arg = TL.getArgument();
 297     // Template-template parameters require special attention, as there's no
 298     // TemplateNameLoc.
 299     if (Arg.getKind() == TemplateArgument::Template ||
 300         Arg.getKind() == TemplateArgument::TemplateExpansion) {
 301       report(TL.getLocation(),
 302              resolveTemplateName(Arg.getAsTemplateOrTemplatePattern()));
 303       return true;
 304     }
 305     return RecursiveASTVisitor::TraverseTemplateArgumentLoc(TL);
 306   }
 307 };
 308
 309 } // namespace
 310
 311 void walkAST(Decl &Root, DeclCallback Callback) {
 312   ASTWalker(Callback).TraverseDecl(&Root);
 313 }
 314
 315 } // namespace clang::include_cleaner