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