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/ComputeDependence.h"
15#include "clang/AST/Decl.h"
16#include "clang/AST/DeclBase.h"
17#include "clang/AST/DeclCXX.h"
18#include "clang/AST/Expr.h"
19#include "clang/AST/ExprCXX.h"
20#include "clang/AST/Stmt.h"
21#include "clang/AST/Type.h"
22#include "clang/Analysis/FlowSensitive/StorageLocation.h"
23#include "clang/Basic/LLVM.h"
24#include "llvm/ADT/DenseSet.h"
25#include "llvm/ADT/STLExtras.h"
26#include <cassert>
27#include <iterator>
28#include <vector>
29
30#define DEBUG_TYPE "dataflow"
31
32namespace clang::dataflow {
33
34const Expr &ignoreCFGOmittedNodes(const Expr &E) {
35 const Expr *Current = &E;
36 if (auto *EWC = dyn_cast<ExprWithCleanups>(Val: Current)) {
37 Current = EWC->getSubExpr();
38 assert(Current != nullptr);
39 }
40 Current = Current->IgnoreParens();
41 assert(Current != nullptr);
42 return *Current;
43}
44
45const Stmt &ignoreCFGOmittedNodes(const Stmt &S) {
46 if (auto *E = dyn_cast<Expr>(Val: &S))
47 return ignoreCFGOmittedNodes(E: *E);
48 return S;
49}
50
51// FIXME: Does not precisely handle non-virtual diamond inheritance. A single
52// field decl will be modeled for all instances of the inherited field.
53static void getFieldsFromClassHierarchy(QualType Type, FieldSet &Fields) {
54 if (Type->isIncompleteType() || Type->isDependentType() ||
55 !Type->isRecordType())
56 return;
57
58 for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
59 Fields.insert(X: Field);
60 if (auto *CXXRecord = Type->getAsCXXRecordDecl())
61 for (const CXXBaseSpecifier &Base : CXXRecord->bases())
62 getFieldsFromClassHierarchy(Type: Base.getType(), Fields);
63}
64
65/// Gets the set of all fields in the type.
66FieldSet getObjectFields(QualType Type) {
67 FieldSet Fields;
68 getFieldsFromClassHierarchy(Type, Fields);
69 return Fields;
70}
71
72bool containsSameFields(const FieldSet &Fields,
73 const RecordStorageLocation::FieldToLoc &FieldLocs) {
74 if (Fields.size() != FieldLocs.size())
75 return false;
76 for ([[maybe_unused]] auto [Field, Loc] : FieldLocs)
77 if (!Fields.contains(key: cast_or_null<FieldDecl>(Val: Field)))
78 return false;
79 return true;
80}
81
82/// Returns the fields of a `RecordDecl` that are initialized by an
83/// `InitListExpr` or `CXXParenListInitExpr`, in the order in which they appear
84/// in `InitListExpr::inits()` / `CXXParenListInitExpr::getInitExprs()`.
85/// `InitList->getType()` must be a record type.
86template <class InitListT>
87static std::vector<const FieldDecl *>
88getFieldsForInitListExpr(const InitListT *InitList) {
89 const RecordDecl *RD = InitList->getType()->getAsRecordDecl();
90 assert(RD != nullptr);
91
92 std::vector<const FieldDecl *> Fields;
93
94 if (InitList->getType()->isUnionType()) {
95 Fields.push_back(InitList->getInitializedFieldInUnion());
96 return Fields;
97 }
98
99 // Unnamed bitfields are only used for padding and do not appear in
100 // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s
101 // field list, and we thus need to remove them before mapping inits to
102 // fields to avoid mapping inits to the wrongs fields.
103 llvm::copy_if(
104 RD->fields(), std::back_inserter(x&: Fields),
105 [](const FieldDecl *Field) { return !Field->isUnnamedBitField(); });
106 return Fields;
107}
108
109RecordInitListHelper::RecordInitListHelper(const InitListExpr *InitList)
110 : RecordInitListHelper(InitList->getType(),
111 getFieldsForInitListExpr(InitList),
112 InitList->inits()) {}
113
114RecordInitListHelper::RecordInitListHelper(
115 const CXXParenListInitExpr *ParenInitList)
116 : RecordInitListHelper(ParenInitList->getType(),
117 getFieldsForInitListExpr(InitList: ParenInitList),
118 ParenInitList->getInitExprs()) {}
119
120RecordInitListHelper::RecordInitListHelper(
121 QualType Ty, std::vector<const FieldDecl *> Fields,
122 ArrayRef<Expr *> Inits) {
123 auto *RD = Ty->getAsCXXRecordDecl();
124 assert(RD != nullptr);
125
126 // Unions initialized with an empty initializer list need special treatment.
127 // For structs/classes initialized with an empty initializer list, Clang
128 // puts `ImplicitValueInitExpr`s in `InitListExpr::inits()`, but for unions,
129 // it doesn't do this -- so we create an `ImplicitValueInitExpr` ourselves.
130 SmallVector<Expr *> InitsForUnion;
131 if (Ty->isUnionType() && Inits.empty()) {
132 assert(Fields.size() == 1);
133 ImplicitValueInitForUnion.emplace(Fields.front()->getType());
134 InitsForUnion.push_back(&*ImplicitValueInitForUnion);
135 Inits = InitsForUnion;
136 }
137
138 size_t InitIdx = 0;
139
140 assert(Fields.size() + RD->getNumBases() == Inits.size());
141 for (const CXXBaseSpecifier &Base : RD->bases()) {
142 assert(InitIdx < Inits.size());
143 Expr *Init = Inits[InitIdx++];
144 BaseInits.emplace_back(Args: &Base, Args&: Init);
145 }
146
147 assert(Fields.size() == Inits.size() - InitIdx);
148 for (const FieldDecl *Field : Fields) {
149 assert(InitIdx < Inits.size());
150 Expr *Init = Inits[InitIdx++];
151 FieldInits.emplace_back(Args&: Field, Args&: Init);
152 }
153}
154
155static void insertIfGlobal(const Decl &D,
156 llvm::DenseSet<const VarDecl *> &Globals) {
157 if (auto *V = dyn_cast<VarDecl>(Val: &D))
158 if (V->hasGlobalStorage())
159 Globals.insert(V);
160}
161
162static void insertIfFunction(const Decl &D,
163 llvm::DenseSet<const FunctionDecl *> &Funcs) {
164 if (auto *FD = dyn_cast<FunctionDecl>(Val: &D))
165 Funcs.insert(V: FD);
166}
167
168static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) {
169 // Use getCalleeDecl instead of getMethodDecl in order to handle
170 // pointer-to-member calls.
171 const auto *MethodDecl = dyn_cast_or_null<CXXMethodDecl>(C.getCalleeDecl());
172 if (!MethodDecl)
173 return nullptr;
174 auto *Body = dyn_cast_or_null<CompoundStmt>(MethodDecl->getBody());
175 if (!Body || Body->size() != 1)
176 return nullptr;
177 if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin()))
178 if (auto *Return = RS->getRetValue())
179 return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts());
180 return nullptr;
181}
182
183static void getReferencedDecls(const Decl &D, ReferencedDecls &Referenced) {
184 insertIfGlobal(D, Globals&: Referenced.Globals);
185 insertIfFunction(D, Funcs&: Referenced.Functions);
186 if (const auto *Decomp = dyn_cast<DecompositionDecl>(Val: &D))
187 for (const auto *B : Decomp->bindings())
188 if (auto *ME = dyn_cast_or_null<MemberExpr>(Val: B->getBinding()))
189 // FIXME: should we be using `E->getFoundDecl()`?
190 if (const auto *FD = dyn_cast<FieldDecl>(Val: ME->getMemberDecl()))
191 Referenced.Fields.insert(X: FD);
192}
193
194/// Traverses `S` and inserts into `Referenced` any declarations that are
195/// declared in or referenced from sub-statements.
196static void getReferencedDecls(const Stmt &S, ReferencedDecls &Referenced) {
197 for (auto *Child : S.children())
198 if (Child != nullptr)
199 getReferencedDecls(S: *Child, Referenced);
200 if (const auto *DefaultArg = dyn_cast<CXXDefaultArgExpr>(Val: &S))
201 getReferencedDecls(*DefaultArg->getExpr(), Referenced);
202 if (const auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(Val: &S))
203 getReferencedDecls(*DefaultInit->getExpr(), Referenced);
204
205 if (auto *DS = dyn_cast<DeclStmt>(Val: &S)) {
206 if (DS->isSingleDecl())
207 getReferencedDecls(D: *DS->getSingleDecl(), Referenced);
208 else
209 for (auto *D : DS->getDeclGroup())
210 getReferencedDecls(D: *D, Referenced);
211 } else if (auto *E = dyn_cast<DeclRefExpr>(Val: &S)) {
212 insertIfGlobal(*E->getDecl(), Referenced.Globals);
213 insertIfFunction(*E->getDecl(), Referenced.Functions);
214 } else if (const auto *C = dyn_cast<CXXMemberCallExpr>(Val: &S)) {
215 // If this is a method that returns a member variable but does nothing else,
216 // model the field of the return value.
217 if (MemberExpr *E = getMemberForAccessor(C: *C))
218 if (const auto *FD = dyn_cast<FieldDecl>(Val: E->getMemberDecl()))
219 Referenced.Fields.insert(X: FD);
220 } else if (auto *E = dyn_cast<MemberExpr>(Val: &S)) {
221 // FIXME: should we be using `E->getFoundDecl()`?
222 const ValueDecl *VD = E->getMemberDecl();
223 insertIfGlobal(*VD, Referenced.Globals);
224 insertIfFunction(*VD, Referenced.Functions);
225 if (const auto *FD = dyn_cast<FieldDecl>(Val: VD))
226 Referenced.Fields.insert(X: FD);
227 } else if (auto *InitList = dyn_cast<InitListExpr>(Val: &S)) {
228 if (InitList->getType()->isRecordType())
229 for (const auto *FD : getFieldsForInitListExpr(InitList))
230 Referenced.Fields.insert(X: FD);
231 } else if (auto *ParenInitList = dyn_cast<CXXParenListInitExpr>(Val: &S)) {
232 if (ParenInitList->getType()->isRecordType())
233 for (const auto *FD : getFieldsForInitListExpr(InitList: ParenInitList))
234 Referenced.Fields.insert(X: FD);
235 }
236}
237
238ReferencedDecls getReferencedDecls(const FunctionDecl &FD) {
239 ReferencedDecls Result;
240 // Look for global variable and field references in the
241 // constructor-initializers.
242 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(Val: &FD)) {
243 for (const auto *Init : CtorDecl->inits()) {
244 if (Init->isMemberInitializer()) {
245 Result.Fields.insert(X: Init->getMember());
246 } else if (Init->isIndirectMemberInitializer()) {
247 for (const auto *I : Init->getIndirectMember()->chain())
248 Result.Fields.insert(X: cast<FieldDecl>(Val: I));
249 }
250 const Expr *E = Init->getInit();
251 assert(E != nullptr);
252 getReferencedDecls(*E, Result);
253 }
254 // Add all fields mentioned in default member initializers.
255 for (const FieldDecl *F : CtorDecl->getParent()->fields())
256 if (const auto *I = F->getInClassInitializer())
257 getReferencedDecls(*I, Result);
258 }
259 getReferencedDecls(S: *FD.getBody(), Referenced&: Result);
260
261 return Result;
262}
263
264ReferencedDecls getReferencedDecls(const Stmt &S) {
265 ReferencedDecls Result;
266 getReferencedDecls(S, Referenced&: Result);
267 return Result;
268}
269
270} // namespace clang::dataflow
271

source code of clang/lib/Analysis/FlowSensitive/ASTOps.cpp