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
33namespace clang::dataflow {
34
35const 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>(Val: Current)) {
41 Current = EWC->getSubExpr();
42 assert(Current != nullptr);
43 }
44 if (auto *CE = dyn_cast<ConstantExpr>(Val: Current)) {
45 Current = CE->getSubExpr();
46 assert(Current != nullptr);
47 }
48 Current = Current->IgnoreParens();
49 assert(Current != nullptr);
50 }
51 return *Current;
52}
53
54const Stmt &ignoreCFGOmittedNodes(const Stmt &S) {
55 if (auto *E = dyn_cast<Expr>(Val: &S))
56 return ignoreCFGOmittedNodes(E: *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.
62static void getFieldsFromClassHierarchy(QualType Type, FieldSet &Fields) {
63 if (Type->isIncompleteType() || Type->isDependentType() ||
64 !Type->isRecordType())
65 return;
66
67 Fields.insert_range(R: Type->getAsRecordDecl()->fields());
68 if (auto *CXXRecord = Type->getAsCXXRecordDecl())
69 for (const CXXBaseSpecifier &Base : CXXRecord->bases())
70 getFieldsFromClassHierarchy(Type: Base.getType(), Fields);
71}
72
73/// Gets the set of all fields in the type.
74FieldSet getObjectFields(QualType Type) {
75 FieldSet Fields;
76 getFieldsFromClassHierarchy(Type, Fields);
77 return Fields;
78}
79
80bool 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(key: cast_or_null<FieldDecl>(Val: 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.
94template <class InitListT>
95static std::vector<const FieldDecl *>
96getFieldsForInitListExpr(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(x: 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(x&: Fields),
114 [](const FieldDecl *Field) { return !Field->isUnnamedBitField(); });
115 return Fields;
116}
117
118RecordInitListHelper::RecordInitListHelper(const InitListExpr *InitList)
119 : RecordInitListHelper(InitList->getType(),
120 getFieldsForInitListExpr(InitList),
121 InitList->inits()) {}
122
123RecordInitListHelper::RecordInitListHelper(
124 const CXXParenListInitExpr *ParenInitList)
125 : RecordInitListHelper(ParenInitList->getType(),
126 getFieldsForInitListExpr(InitList: ParenInitList),
127 ParenInitList->getInitExprs()) {}
128
129RecordInitListHelper::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(args: Fields.front()->getType());
144 InitsForUnion.push_back(Elt: &*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(Args: &Base, Args&: 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(Args&: Field, Args&: Init);
163 }
164}
165
166static void insertIfGlobal(const Decl &D,
167 llvm::DenseSet<const VarDecl *> &Globals) {
168 if (auto *V = dyn_cast<VarDecl>(Val: &D))
169 if (V->hasGlobalStorage())
170 Globals.insert(V);
171}
172
173static void insertIfLocal(const Decl &D,
174 llvm::DenseSet<const VarDecl *> &Locals) {
175 if (auto *V = dyn_cast<VarDecl>(Val: &D))
176 if (V->hasLocalStorage() && !isa<ParmVarDecl>(Val: V))
177 Locals.insert(V);
178}
179
180static void insertIfFunction(const Decl &D,
181 llvm::DenseSet<const FunctionDecl *> &Funcs) {
182 if (auto *FD = dyn_cast<FunctionDecl>(Val: &D))
183 Funcs.insert(V: FD);
184}
185
186static 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>(Val: C.getCalleeDecl());
190 if (!MethodDecl)
191 return nullptr;
192 auto *Body = dyn_cast_or_null<CompoundStmt>(Val: MethodDecl->getBody());
193 if (!Body || Body->size() != 1)
194 return nullptr;
195 if (auto *RS = dyn_cast<ReturnStmt>(Val: *Body->body_begin()))
196 if (auto *Return = RS->getRetValue())
197 return dyn_cast<MemberExpr>(Val: Return->IgnoreParenImpCasts());
198 return nullptr;
199}
200
201class ReferencedDeclsVisitor : public AnalysisASTVisitor {
202public:
203 ReferencedDeclsVisitor(ReferencedDecls &Referenced)
204 : Referenced(Referenced) {}
205
206 void traverseConstructorInits(const CXXConstructorDecl *Ctor) {
207 for (const CXXCtorInitializer *Init : Ctor->inits()) {
208 if (Init->isMemberInitializer()) {
209 Referenced.Fields.insert(X: Init->getMember());
210 } else if (Init->isIndirectMemberInitializer()) {
211 for (const auto *I : Init->getIndirectMember()->chain())
212 Referenced.Fields.insert(X: cast<FieldDecl>(Val: I));
213 }
214
215 Expr *InitExpr = Init->getInit();
216
217 // Also collect declarations referenced in `InitExpr`.
218 TraverseStmt(S: InitExpr);
219
220 // If this is a `CXXDefaultInitExpr`, also collect declarations referenced
221 // within the default expression.
222 if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(Val: InitExpr))
223 TraverseStmt(S: DefaultInit->getExpr());
224 }
225 }
226
227 bool VisitDecl(Decl *D) override {
228 insertIfGlobal(D: *D, Globals&: Referenced.Globals);
229 insertIfLocal(D: *D, Locals&: Referenced.Locals);
230 insertIfFunction(D: *D, Funcs&: Referenced.Functions);
231 return true;
232 }
233
234 bool VisitDeclRefExpr(DeclRefExpr *E) override {
235 insertIfGlobal(D: *E->getDecl(), Globals&: Referenced.Globals);
236 insertIfLocal(D: *E->getDecl(), Locals&: Referenced.Locals);
237 insertIfFunction(D: *E->getDecl(), Funcs&: Referenced.Functions);
238 return true;
239 }
240
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: *C))
245 if (const auto *FD = dyn_cast<FieldDecl>(Val: E->getMemberDecl()))
246 Referenced.Fields.insert(X: FD);
247 return true;
248 }
249
250 bool VisitMemberExpr(MemberExpr *E) override {
251 // FIXME: should we be using `E->getFoundDecl()`?
252 const ValueDecl *VD = E->getMemberDecl();
253 insertIfGlobal(D: *VD, Globals&: Referenced.Globals);
254 insertIfFunction(D: *VD, Funcs&: Referenced.Functions);
255 if (const auto *FD = dyn_cast<FieldDecl>(Val: VD))
256 Referenced.Fields.insert(X: FD);
257 return true;
258 }
259
260 bool VisitInitListExpr(InitListExpr *InitList) override {
261 if (InitList->getType()->isRecordType())
262 Referenced.Fields.insert_range(R: getFieldsForInitListExpr(InitList));
263 return true;
264 }
265
266 bool VisitCXXParenListInitExpr(CXXParenListInitExpr *ParenInitList) override {
267 if (ParenInitList->getType()->isRecordType())
268 Referenced.Fields.insert_range(R: getFieldsForInitListExpr(InitList: ParenInitList));
269 return true;
270 }
271
272private:
273 ReferencedDecls &Referenced;
274};
275
276ReferencedDecls getReferencedDecls(const FunctionDecl &FD) {
277 ReferencedDecls Result;
278 ReferencedDeclsVisitor Visitor(Result);
279 Visitor.TraverseStmt(S: FD.getBody());
280 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(Val: &FD))
281 Visitor.traverseConstructorInits(Ctor: 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>(Val: &FD);
294 Method && isLambdaCallOperator(MD: Method)) {
295 for (const auto &Capture : Method->getParent()->captures()) {
296 if (Capture.capturesVariable()) {
297 if (const auto *Param =
298 dyn_cast<ParmVarDecl>(Val: Capture.getCapturedVar())) {
299 Result.LambdaCapturedParams.insert(V: Param);
300 }
301 }
302 }
303 }
304
305 return Result;
306}
307
308ReferencedDecls getReferencedDecls(const Stmt &S) {
309 ReferencedDecls Result;
310 ReferencedDeclsVisitor Visitor(Result);
311 Visitor.TraverseStmt(S: const_cast<Stmt *>(&S));
312 return Result;
313}
314
315} // namespace clang::dataflow
316