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
31namespace clang::include_cleaner {
32namespace {
33using DeclCallback =
34 llvm::function_ref<void(SourceLocation, NamedDecl &, RefType)>;
35
36class 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: Base->getPointeeType());
55 // Unwrap the sugar ElaboratedType.
56 if (const auto *ElTy = dyn_cast<ElaboratedType>(Val&: Base))
57 return getMemberProvider(Base: ElTy->getNamedType());
58
59 if (const auto *TT = dyn_cast<TypedefType>(Val&: Base))
60 return TT->getDecl();
61 if (const auto *UT = dyn_cast<UsingType>(Val&: 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>(Val&: Base))
71 return resolveTemplateName(TN: 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(TN: 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
102public:
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(Loc: S->getOperatorLoc(), ND: getMemberProvider(Base: S->getArg(0)->getType()),
117 RT: RefType::Implicit);
118 } else {
119 report(Loc: S->getOperatorLoc(), ND: llvm::dyn_cast<NamedDecl>(CD),
120 RT: 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>(Val: 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>(Val: FD)) {
141 report(Loc: DRE->getLocation(), ND: 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>(Val: FD)) {
151 if (!DRE->getQualifier() || DRE->getQualifier()->getAsNamespace())
152 report(Loc: DRE->getLocation(), ND: 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(Loc: E->getMemberLoc(), ND: getMemberProvider(Base: Type), RT: RefType::Implicit);
165 return true;
166 }
167 bool VisitCXXDependentScopeMemberExpr(CXXDependentScopeMemberExpr *E) {
168 report(Loc: E->getMemberLoc(), ND: getMemberProvider(Base: E->getBaseType()),
169 RT: 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(Loc: E->getLocation(), ND: getMemberProvider(Base: E->getType()),
179 RT: 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(Loc: E->getNameLoc(), ND: D, RT: 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, ND: Spec, RT: RefType::Ambiguous);
199 llvm::SmallVector<ParitialDeclType *> PartialSpecializations;
200 TD->getPartialSpecializations(PartialSpecializations);
201 for (auto *PartialSpec : PartialSpecializations)
202 report(Loc, ND: PartialSpec, RT: 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(Loc: FD->getLocation(), ND: FD);
231 // Explicit specializaiton/instantiations of a function template requires
232 // primary template.
233 if (clang::isTemplateExplicitInstantiationOrSpecialization(
234 Kind: FD->getTemplateSpecializationKind()))
235 report(Loc: FD->getLocation(), ND: 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>(Val: VD))
242 return true;
243 // Mark declaration from definition as it needs type-checking.
244 if (VD->isThisDeclarationADefinition())
245 report(Loc: VD->getLocation(), ND: 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(Loc: D->getLocation(), ND: 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(Loc: D->getLocation(), ND: FD);
262 return true;
263 }
264
265 bool VisitConceptReference(const ConceptReference *CR) {
266 report(Loc: CR->getConceptNameLoc(), ND: CR->getFoundDecl());
267 return true;
268 }
269
270 // Report a reference from explicit specializations to the specialized
271 // template. Implicit ones are filtered out by RAV and explicit instantiations
272 // are already traversed through typelocs.
273 bool
274 VisitClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *CTSD) {
275 if (CTSD->isExplicitSpecialization())
276 report(Loc: CTSD->getLocation(),
277 ND: CTSD->getSpecializedTemplate()->getTemplatedDecl());
278 return true;
279 }
280 bool VisitVarTemplateSpecializationDecl(VarTemplateSpecializationDecl *VTSD) {
281 if (VTSD->isExplicitSpecialization())
282 report(Loc: VTSD->getLocation(),
283 ND: VTSD->getSpecializedTemplate()->getTemplatedDecl());
284 return true;
285 }
286
287 // TypeLoc visitors.
288 void reportType(SourceLocation RefLoc, NamedDecl *ND) {
289 // Reporting explicit references to types nested inside classes can cause
290 // issues, e.g. a type accessed through a derived class shouldn't require
291 // inclusion of the base.
292 // Hence we report all such references as implicit. The code must spell the
293 // outer type-location somewhere, which will trigger an explicit reference
294 // and per IWYS, it's that spelling's responsibility to bring in necessary
295 // declarations.
296 RefType RT = llvm::isa<RecordDecl>(ND->getDeclContext())
297 ? RefType::Implicit
298 : RefType::Explicit;
299 return report(Loc: RefLoc, ND, RT);
300 }
301
302 bool VisitUsingTypeLoc(UsingTypeLoc TL) {
303 reportType(RefLoc: TL.getNameLoc(), ND: TL.getFoundDecl());
304 return true;
305 }
306
307 bool VisitTagTypeLoc(TagTypeLoc TTL) {
308 reportType(RefLoc: TTL.getNameLoc(), ND: TTL.getDecl());
309 return true;
310 }
311
312 bool VisitTypedefTypeLoc(TypedefTypeLoc TTL) {
313 reportType(RefLoc: TTL.getNameLoc(), ND: TTL.getTypedefNameDecl());
314 return true;
315 }
316
317 bool VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc TL) {
318 reportType(RefLoc: TL.getTemplateNameLoc(),
319 ND: getMostRelevantTemplatePattern(TL.getTypePtr()));
320 return true;
321 }
322
323 bool VisitDeducedTemplateSpecializationTypeLoc(
324 DeducedTemplateSpecializationTypeLoc TL) {
325 reportType(RefLoc: TL.getTemplateNameLoc(),
326 ND: getMostRelevantTemplatePattern(TL.getTypePtr()));
327 return true;
328 }
329
330 bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &TL) {
331 auto &Arg = TL.getArgument();
332 // Template-template parameters require special attention, as there's no
333 // TemplateNameLoc.
334 if (Arg.getKind() == TemplateArgument::Template ||
335 Arg.getKind() == TemplateArgument::TemplateExpansion) {
336 report(Loc: TL.getLocation(),
337 ND: resolveTemplateName(TN: Arg.getAsTemplateOrTemplatePattern()));
338 return true;
339 }
340 return RecursiveASTVisitor::TraverseTemplateArgumentLoc(ArgLoc: TL);
341 }
342
343 bool VisitCXXStdInitializerListExpr(CXXStdInitializerListExpr *E) {
344 // Reliance on initializer_lists requires std::initializer_list to be
345 // visible per standard. So report a reference to it, otherwise include of
346 // `<initializer_list>` might not receive any use.
347 report(Loc: E->getExprLoc(),
348 ND: const_cast<CXXRecordDecl *>(E->getBestDynamicClassType()),
349 RT: RefType::Implicit);
350 return true;
351 }
352};
353
354} // namespace
355
356void walkAST(Decl &Root, DeclCallback Callback) {
357 ASTWalker(Callback).TraverseDecl(D: &Root);
358}
359
360} // namespace clang::include_cleaner
361

source code of clang-tools-extra/include-cleaner/lib/WalkAST.cpp