1 //===-- ASTOps.cc -------------------------------*- C++ -*-===//
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 // Operations on AST nodes that are used in flow-sensitive analysis.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "clang/Analysis/FlowSensitive/ASTOps.h"
14 #include "clang/AST/ASTLambda.h"
15 #include "clang/AST/ComputeDependence.h"
16 #include "clang/AST/Decl.h"
17 #include "clang/AST/DeclBase.h"
18 #include "clang/AST/DeclCXX.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/AST/ExprCXX.h"
21 #include "clang/AST/Stmt.h"
22 #include "clang/AST/Type.h"
23 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
24 #include "clang/Basic/LLVM.h"
25 #include "llvm/ADT/DenseSet.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include <cassert>
28 #include <iterator>
29 #include <vector>
30
31 #define DEBUG_TYPE "dataflow"
32
33 namespace clang::dataflow {
34
ignoreCFGOmittedNodes(const Expr & E)35 const Expr &ignoreCFGOmittedNodes(const Expr &E) {
36 const Expr *Current = &E;
37 const Expr *Last = nullptr;
38 while (Current != Last) {
39 Last = Current;
40 if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {
41 Current = EWC->getSubExpr();
42 assert(Current != nullptr);
43 }
44 if (auto *CE = dyn_cast<ConstantExpr>(Current)) {
45 Current = CE->getSubExpr();
46 assert(Current != nullptr);
47 }
48 Current = Current->IgnoreParens();
49 assert(Current != nullptr);
50 }
51 return *Current;
52 }
53
ignoreCFGOmittedNodes(const Stmt & S)54 const Stmt &ignoreCFGOmittedNodes(const Stmt &S) {
55 if (auto *E = dyn_cast<Expr>(&S))
56 return ignoreCFGOmittedNodes(*E);
57 return S;
58 }
59
60 // FIXME: Does not precisely handle non-virtual diamond inheritance. A single
61 // field decl will be modeled for all instances of the inherited field.
getFieldsFromClassHierarchy(QualType Type,FieldSet & Fields)62 static void getFieldsFromClassHierarchy(QualType Type, FieldSet &Fields) {
63 if (Type->isIncompleteType() || Type->isDependentType() ||
64 !Type->isRecordType())
65 return;
66
67 Fields.insert_range(Type->getAsRecordDecl()->fields());
68 if (auto *CXXRecord = Type->getAsCXXRecordDecl())
69 for (const CXXBaseSpecifier &Base : CXXRecord->bases())
70 getFieldsFromClassHierarchy(Base.getType(), Fields);
71 }
72
73 /// Gets the set of all fields in the type.
getObjectFields(QualType Type)74 FieldSet getObjectFields(QualType Type) {
75 FieldSet Fields;
76 getFieldsFromClassHierarchy(Type, Fields);
77 return Fields;
78 }
79
containsSameFields(const FieldSet & Fields,const RecordStorageLocation::FieldToLoc & FieldLocs)80 bool containsSameFields(const FieldSet &Fields,
81 const RecordStorageLocation::FieldToLoc &FieldLocs) {
82 if (Fields.size() != FieldLocs.size())
83 return false;
84 for ([[maybe_unused]] auto [Field, Loc] : FieldLocs)
85 if (!Fields.contains(cast_or_null<FieldDecl>(Field)))
86 return false;
87 return true;
88 }
89
90 /// Returns the fields of a `RecordDecl` that are initialized by an
91 /// `InitListExpr` or `CXXParenListInitExpr`, in the order in which they appear
92 /// in `InitListExpr::inits()` / `CXXParenListInitExpr::getInitExprs()`.
93 /// `InitList->getType()` must be a record type.
94 template <class InitListT>
95 static std::vector<const FieldDecl *>
getFieldsForInitListExpr(const InitListT * InitList)96 getFieldsForInitListExpr(const InitListT *InitList) {
97 const RecordDecl *RD = InitList->getType()->getAsRecordDecl();
98 assert(RD != nullptr);
99
100 std::vector<const FieldDecl *> Fields;
101
102 if (InitList->getType()->isUnionType()) {
103 if (const FieldDecl *Field = InitList->getInitializedFieldInUnion())
104 Fields.push_back(Field);
105 return Fields;
106 }
107
108 // Unnamed bitfields are only used for padding and do not appear in
109 // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s
110 // field list, and we thus need to remove them before mapping inits to
111 // fields to avoid mapping inits to the wrongs fields.
112 llvm::copy_if(
113 RD->fields(), std::back_inserter(Fields),
114 [](const FieldDecl *Field) { return !Field->isUnnamedBitField(); });
115 return Fields;
116 }
117
RecordInitListHelper(const InitListExpr * InitList)118 RecordInitListHelper::RecordInitListHelper(const InitListExpr *InitList)
119 : RecordInitListHelper(InitList->getType(),
120 getFieldsForInitListExpr(InitList),
121 InitList->inits()) {}
122
RecordInitListHelper(const CXXParenListInitExpr * ParenInitList)123 RecordInitListHelper::RecordInitListHelper(
124 const CXXParenListInitExpr *ParenInitList)
125 : RecordInitListHelper(ParenInitList->getType(),
126 getFieldsForInitListExpr(ParenInitList),
127 ParenInitList->getInitExprs()) {}
128
RecordInitListHelper(QualType Ty,std::vector<const FieldDecl * > Fields,ArrayRef<Expr * > Inits)129 RecordInitListHelper::RecordInitListHelper(
130 QualType Ty, std::vector<const FieldDecl *> Fields,
131 ArrayRef<Expr *> Inits) {
132 auto *RD = Ty->getAsCXXRecordDecl();
133 assert(RD != nullptr);
134
135 // Unions initialized with an empty initializer list need special treatment.
136 // For structs/classes initialized with an empty initializer list, Clang
137 // puts `ImplicitValueInitExpr`s in `InitListExpr::inits()`, but for unions,
138 // it doesn't do this -- so we create an `ImplicitValueInitExpr` ourselves.
139 SmallVector<Expr *> InitsForUnion;
140 if (Ty->isUnionType() && Inits.empty()) {
141 assert(Fields.size() <= 1);
142 if (!Fields.empty()) {
143 ImplicitValueInitForUnion.emplace(Fields.front()->getType());
144 InitsForUnion.push_back(&*ImplicitValueInitForUnion);
145 }
146 Inits = InitsForUnion;
147 }
148
149 size_t InitIdx = 0;
150
151 assert(Fields.size() + RD->getNumBases() == Inits.size());
152 for (const CXXBaseSpecifier &Base : RD->bases()) {
153 assert(InitIdx < Inits.size());
154 Expr *Init = Inits[InitIdx++];
155 BaseInits.emplace_back(&Base, Init);
156 }
157
158 assert(Fields.size() == Inits.size() - InitIdx);
159 for (const FieldDecl *Field : Fields) {
160 assert(InitIdx < Inits.size());
161 Expr *Init = Inits[InitIdx++];
162 FieldInits.emplace_back(Field, Init);
163 }
164 }
165
insertIfGlobal(const Decl & D,llvm::DenseSet<const VarDecl * > & Globals)166 static void insertIfGlobal(const Decl &D,
167 llvm::DenseSet<const VarDecl *> &Globals) {
168 if (auto *V = dyn_cast<VarDecl>(&D))
169 if (V->hasGlobalStorage())
170 Globals.insert(V);
171 }
172
insertIfLocal(const Decl & D,llvm::DenseSet<const VarDecl * > & Locals)173 static void insertIfLocal(const Decl &D,
174 llvm::DenseSet<const VarDecl *> &Locals) {
175 if (auto *V = dyn_cast<VarDecl>(&D))
176 if (V->hasLocalStorage() && !isa<ParmVarDecl>(V))
177 Locals.insert(V);
178 }
179
insertIfFunction(const Decl & D,llvm::DenseSet<const FunctionDecl * > & Funcs)180 static void insertIfFunction(const Decl &D,
181 llvm::DenseSet<const FunctionDecl *> &Funcs) {
182 if (auto *FD = dyn_cast<FunctionDecl>(&D))
183 Funcs.insert(FD);
184 }
185
getMemberForAccessor(const CXXMemberCallExpr & C)186 static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) {
187 // Use getCalleeDecl instead of getMethodDecl in order to handle
188 // pointer-to-member calls.
189 const auto *MethodDecl = dyn_cast_or_null<CXXMethodDecl>(C.getCalleeDecl());
190 if (!MethodDecl)
191 return nullptr;
192 auto *Body = dyn_cast_or_null<CompoundStmt>(MethodDecl->getBody());
193 if (!Body || Body->size() != 1)
194 return nullptr;
195 if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin()))
196 if (auto *Return = RS->getRetValue())
197 return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts());
198 return nullptr;
199 }
200
201 class ReferencedDeclsVisitor : public AnalysisASTVisitor {
202 public:
ReferencedDeclsVisitor(ReferencedDecls & Referenced)203 ReferencedDeclsVisitor(ReferencedDecls &Referenced)
204 : Referenced(Referenced) {}
205
traverseConstructorInits(const CXXConstructorDecl * Ctor)206 void traverseConstructorInits(const CXXConstructorDecl *Ctor) {
207 for (const CXXCtorInitializer *Init : Ctor->inits()) {
208 if (Init->isMemberInitializer()) {
209 Referenced.Fields.insert(Init->getMember());
210 } else if (Init->isIndirectMemberInitializer()) {
211 for (const auto *I : Init->getIndirectMember()->chain())
212 Referenced.Fields.insert(cast<FieldDecl>(I));
213 }
214
215 Expr *InitExpr = Init->getInit();
216
217 // Also collect declarations referenced in `InitExpr`.
218 TraverseStmt(InitExpr);
219
220 // If this is a `CXXDefaultInitExpr`, also collect declarations referenced
221 // within the default expression.
222 if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(InitExpr))
223 TraverseStmt(DefaultInit->getExpr());
224 }
225 }
226
VisitDecl(Decl * D)227 bool VisitDecl(Decl *D) override {
228 insertIfGlobal(*D, Referenced.Globals);
229 insertIfLocal(*D, Referenced.Locals);
230 insertIfFunction(*D, Referenced.Functions);
231 return true;
232 }
233
VisitDeclRefExpr(DeclRefExpr * E)234 bool VisitDeclRefExpr(DeclRefExpr *E) override {
235 insertIfGlobal(*E->getDecl(), Referenced.Globals);
236 insertIfLocal(*E->getDecl(), Referenced.Locals);
237 insertIfFunction(*E->getDecl(), Referenced.Functions);
238 return true;
239 }
240
VisitCXXMemberCallExpr(CXXMemberCallExpr * C)241 bool VisitCXXMemberCallExpr(CXXMemberCallExpr *C) override {
242 // If this is a method that returns a member variable but does nothing else,
243 // model the field of the return value.
244 if (MemberExpr *E = getMemberForAccessor(*C))
245 if (const auto *FD = dyn_cast<FieldDecl>(E->getMemberDecl()))
246 Referenced.Fields.insert(FD);
247 return true;
248 }
249
VisitMemberExpr(MemberExpr * E)250 bool VisitMemberExpr(MemberExpr *E) override {
251 // FIXME: should we be using `E->getFoundDecl()`?
252 const ValueDecl *VD = E->getMemberDecl();
253 insertIfGlobal(*VD, Referenced.Globals);
254 insertIfFunction(*VD, Referenced.Functions);
255 if (const auto *FD = dyn_cast<FieldDecl>(VD))
256 Referenced.Fields.insert(FD);
257 return true;
258 }
259
VisitInitListExpr(InitListExpr * InitList)260 bool VisitInitListExpr(InitListExpr *InitList) override {
261 if (InitList->getType()->isRecordType())
262 Referenced.Fields.insert_range(getFieldsForInitListExpr(InitList));
263 return true;
264 }
265
VisitCXXParenListInitExpr(CXXParenListInitExpr * ParenInitList)266 bool VisitCXXParenListInitExpr(CXXParenListInitExpr *ParenInitList) override {
267 if (ParenInitList->getType()->isRecordType())
268 Referenced.Fields.insert_range(getFieldsForInitListExpr(ParenInitList));
269 return true;
270 }
271
272 private:
273 ReferencedDecls &Referenced;
274 };
275
getReferencedDecls(const FunctionDecl & FD)276 ReferencedDecls getReferencedDecls(const FunctionDecl &FD) {
277 ReferencedDecls Result;
278 ReferencedDeclsVisitor Visitor(Result);
279 Visitor.TraverseStmt(FD.getBody());
280 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(&FD))
281 Visitor.traverseConstructorInits(CtorDecl);
282
283 // If analyzing a lambda call operator, collect all captures of parameters (of
284 // the surrounding function). This collects them even if they are not
285 // referenced in the body of the lambda call operator. Non-parameter local
286 // variables that are captured are already collected into
287 // `ReferencedDecls.Locals` when traversing the call operator body, but we
288 // collect parameters here to avoid needing to check at each referencing node
289 // whether the parameter is a lambda capture from a surrounding function or is
290 // a parameter of the current function. If it becomes necessary to limit this
291 // set to the parameters actually referenced in the body, alternative
292 // optimizations can be implemented to minimize duplicative work.
293 if (const auto *Method = dyn_cast<CXXMethodDecl>(&FD);
294 Method && isLambdaCallOperator(Method)) {
295 for (const auto &Capture : Method->getParent()->captures()) {
296 if (Capture.capturesVariable()) {
297 if (const auto *Param =
298 dyn_cast<ParmVarDecl>(Capture.getCapturedVar())) {
299 Result.LambdaCapturedParams.insert(Param);
300 }
301 }
302 }
303 }
304
305 return Result;
306 }
307
getReferencedDecls(const Stmt & S)308 ReferencedDecls getReferencedDecls(const Stmt &S) {
309 ReferencedDecls Result;
310 ReferencedDeclsVisitor Visitor(Result);
311 Visitor.TraverseStmt(const_cast<Stmt *>(&S));
312 return Result;
313 }
314
315 } // namespace clang::dataflow
316