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