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

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