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 const Expr *Last = nullptr;
37 while (Current != Last) {
38 Last = Current;
39 if (auto *EWC = dyn_cast<ExprWithCleanups>(Val: Current)) {
40 Current = EWC->getSubExpr();
41 assert(Current != nullptr);
42 }
43 if (auto *CE = dyn_cast<ConstantExpr>(Val: Current)) {
44 Current = CE->getSubExpr();
45 assert(Current != nullptr);
46 }
47 Current = Current->IgnoreParens();
48 assert(Current != nullptr);
49 }
50 return *Current;
51}
52
53const Stmt &ignoreCFGOmittedNodes(const Stmt &S) {
54 if (auto *E = dyn_cast<Expr>(Val: &S))
55 return ignoreCFGOmittedNodes(E: *E);
56 return S;
57}
58
59// FIXME: Does not precisely handle non-virtual diamond inheritance. A single
60// field decl will be modeled for all instances of the inherited field.
61static void getFieldsFromClassHierarchy(QualType Type, FieldSet &Fields) {
62 if (Type->isIncompleteType() || Type->isDependentType() ||
63 !Type->isRecordType())
64 return;
65
66 for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
67 Fields.insert(X: Field);
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 insertIfFunction(const Decl &D,
174 llvm::DenseSet<const FunctionDecl *> &Funcs) {
175 if (auto *FD = dyn_cast<FunctionDecl>(Val: &D))
176 Funcs.insert(V: FD);
177}
178
179static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) {
180 // Use getCalleeDecl instead of getMethodDecl in order to handle
181 // pointer-to-member calls.
182 const auto *MethodDecl = dyn_cast_or_null<CXXMethodDecl>(Val: C.getCalleeDecl());
183 if (!MethodDecl)
184 return nullptr;
185 auto *Body = dyn_cast_or_null<CompoundStmt>(Val: MethodDecl->getBody());
186 if (!Body || Body->size() != 1)
187 return nullptr;
188 if (auto *RS = dyn_cast<ReturnStmt>(Val: *Body->body_begin()))
189 if (auto *Return = RS->getRetValue())
190 return dyn_cast<MemberExpr>(Val: Return->IgnoreParenImpCasts());
191 return nullptr;
192}
193
194class ReferencedDeclsVisitor
195 : public AnalysisASTVisitor<ReferencedDeclsVisitor> {
196public:
197 ReferencedDeclsVisitor(ReferencedDecls &Referenced)
198 : Referenced(Referenced) {}
199
200 void TraverseConstructorInits(const CXXConstructorDecl *Ctor) {
201 for (const CXXCtorInitializer *Init : Ctor->inits()) {
202 if (Init->isMemberInitializer()) {
203 Referenced.Fields.insert(X: Init->getMember());
204 } else if (Init->isIndirectMemberInitializer()) {
205 for (const auto *I : Init->getIndirectMember()->chain())
206 Referenced.Fields.insert(X: cast<FieldDecl>(Val: I));
207 }
208
209 Expr *InitExpr = Init->getInit();
210
211 // Also collect declarations referenced in `InitExpr`.
212 TraverseStmt(S: InitExpr);
213
214 // If this is a `CXXDefaultInitExpr`, also collect declarations referenced
215 // within the default expression.
216 if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(Val: InitExpr))
217 TraverseStmt(S: DefaultInit->getExpr());
218 }
219 }
220
221 bool VisitDecl(Decl *D) {
222 insertIfGlobal(D: *D, Globals&: Referenced.Globals);
223 insertIfFunction(D: *D, Funcs&: Referenced.Functions);
224 return true;
225 }
226
227 bool VisitDeclRefExpr(DeclRefExpr *E) {
228 insertIfGlobal(D: *E->getDecl(), Globals&: Referenced.Globals);
229 insertIfFunction(D: *E->getDecl(), Funcs&: Referenced.Functions);
230 return true;
231 }
232
233 bool VisitCXXMemberCallExpr(CXXMemberCallExpr *C) {
234 // If this is a method that returns a member variable but does nothing else,
235 // model the field of the return value.
236 if (MemberExpr *E = getMemberForAccessor(C: *C))
237 if (const auto *FD = dyn_cast<FieldDecl>(Val: E->getMemberDecl()))
238 Referenced.Fields.insert(X: FD);
239 return true;
240 }
241
242 bool VisitMemberExpr(MemberExpr *E) {
243 // FIXME: should we be using `E->getFoundDecl()`?
244 const ValueDecl *VD = E->getMemberDecl();
245 insertIfGlobal(D: *VD, Globals&: Referenced.Globals);
246 insertIfFunction(D: *VD, Funcs&: Referenced.Functions);
247 if (const auto *FD = dyn_cast<FieldDecl>(Val: VD))
248 Referenced.Fields.insert(X: FD);
249 return true;
250 }
251
252 bool VisitInitListExpr(InitListExpr *InitList) {
253 if (InitList->getType()->isRecordType())
254 for (const auto *FD : getFieldsForInitListExpr(InitList))
255 Referenced.Fields.insert(X: FD);
256 return true;
257 }
258
259 bool VisitCXXParenListInitExpr(CXXParenListInitExpr *ParenInitList) {
260 if (ParenInitList->getType()->isRecordType())
261 for (const auto *FD : getFieldsForInitListExpr(InitList: ParenInitList))
262 Referenced.Fields.insert(X: FD);
263 return true;
264 }
265
266private:
267 ReferencedDecls &Referenced;
268};
269
270ReferencedDecls getReferencedDecls(const FunctionDecl &FD) {
271 ReferencedDecls Result;
272 ReferencedDeclsVisitor Visitor(Result);
273 Visitor.TraverseStmt(S: FD.getBody());
274 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(Val: &FD))
275 Visitor.TraverseConstructorInits(Ctor: CtorDecl);
276
277 return Result;
278}
279
280ReferencedDecls getReferencedDecls(const Stmt &S) {
281 ReferencedDecls Result;
282 ReferencedDeclsVisitor Visitor(Result);
283 Visitor.TraverseStmt(S: const_cast<Stmt *>(&S));
284 return Result;
285}
286
287} // namespace clang::dataflow
288