llvm-project

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
364