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