blob: 0e2ac04efbf6b5ca55ca5492ceed0251683570f6 [file] [log] [blame]
Zhongxing Xucb7464a2010-04-19 12:51:02 +00001//===- GRCXXExprEngine.cpp - C++ expr evaluation engine ---------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the C++ expression evaluation engine.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Checker/PathSensitive/AnalysisManager.h"
15#include "clang/Checker/PathSensitive/GRExprEngine.h"
16#include "clang/AST/DeclCXX.h"
17
18using namespace clang;
19
Ted Kremenekc69c4382010-09-23 05:14:51 +000020namespace {
21class CallExprWLItem {
22public:
23 CallExpr::const_arg_iterator I;
24 ExplodedNode *N;
25
26 CallExprWLItem(const CallExpr::const_arg_iterator &i, ExplodedNode *n)
27 : I(i), N(n) {}
28};
29}
30
Ted Kremenek9c149532010-12-01 21:57:22 +000031void GRExprEngine::evalArguments(ConstExprIterator AI, ConstExprIterator AE,
Zhongxing Xub17b1b32010-04-20 03:37:34 +000032 const FunctionProtoType *FnType,
Marcin Swiderski82c63bf2010-11-17 21:27:36 +000033 ExplodedNode *Pred, ExplodedNodeSet &Dst,
34 bool FstArgAsLValue) {
Ted Kremenekc69c4382010-09-23 05:14:51 +000035
36
Zhongxing Xub17b1b32010-04-20 03:37:34 +000037 llvm::SmallVector<CallExprWLItem, 20> WorkList;
38 WorkList.reserve(AE - AI);
39 WorkList.push_back(CallExprWLItem(AI, Pred));
40
41 while (!WorkList.empty()) {
42 CallExprWLItem Item = WorkList.back();
43 WorkList.pop_back();
44
45 if (Item.I == AE) {
46 Dst.insert(Item.N);
47 continue;
48 }
49
Ted Kremenekc69c4382010-09-23 05:14:51 +000050 // Evaluate the argument.
Zhongxing Xub17b1b32010-04-20 03:37:34 +000051 ExplodedNodeSet Tmp;
Marcin Swiderski82c63bf2010-11-17 21:27:36 +000052 bool VisitAsLvalue = FstArgAsLValue;
53 if (FstArgAsLValue) {
54 FstArgAsLValue = false;
55 } else {
56 const unsigned ParamIdx = Item.I - AI;
57 VisitAsLvalue = FnType && ParamIdx < FnType->getNumArgs()
58 ? FnType->getArgType(ParamIdx)->isReferenceType()
59 : false;
60 }
Ted Kremenekc69c4382010-09-23 05:14:51 +000061
Ted Kremenek892697d2010-12-16 07:46:53 +000062 Visit(*Item.I, Item.N, Tmp);
Zhongxing Xub17b1b32010-04-20 03:37:34 +000063 ++(Item.I);
64 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI != NE; ++NI)
65 WorkList.push_back(CallExprWLItem(Item.I, *NI));
66 }
67}
68
Zhongxing Xu9dc84c92010-11-16 07:52:17 +000069const CXXThisRegion *GRExprEngine::getCXXThisRegion(const CXXRecordDecl *D,
Zhongxing Xucb7464a2010-04-19 12:51:02 +000070 const StackFrameContext *SFC) {
John McCallb168cbf2010-11-16 09:18:38 +000071 Type *T = D->getTypeForDecl();
72 QualType PT = getContext().getPointerType(QualType(T, 0));
Ted Kremenekc8413fd2010-12-02 07:49:45 +000073 return svalBuilder.getRegionManager().getCXXThisRegion(PT, SFC);
Zhongxing Xucb7464a2010-04-19 12:51:02 +000074}
75
Zhongxing Xu32303022010-11-24 13:48:50 +000076const CXXThisRegion *GRExprEngine::getCXXThisRegion(const CXXMethodDecl *decl,
77 const StackFrameContext *frameCtx) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +000078 return svalBuilder.getRegionManager().
Zhongxing Xu32303022010-11-24 13:48:50 +000079 getCXXThisRegion(decl->getThisType(getContext()), frameCtx);
80}
81
Zhongxing Xu03509ae2010-07-20 06:22:24 +000082void GRExprEngine::CreateCXXTemporaryObject(const Expr *Ex, ExplodedNode *Pred,
Zhongxing Xucb7464a2010-04-19 12:51:02 +000083 ExplodedNodeSet &Dst) {
84 ExplodedNodeSet Tmp;
85 Visit(Ex, Pred, Tmp);
86 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) {
87 const GRState *state = GetState(*I);
88
89 // Bind the temporary object to the value of the expression. Then bind
90 // the expression to the location of the object.
91 SVal V = state->getSVal(Ex);
92
93 const MemRegion *R =
Ted Kremenekc8413fd2010-12-02 07:49:45 +000094 svalBuilder.getRegionManager().getCXXTempObjectRegion(Ex,
Zhongxing Xucb7464a2010-04-19 12:51:02 +000095 Pred->getLocationContext());
96
97 state = state->bindLoc(loc::MemRegionVal(R), V);
98 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, loc::MemRegionVal(R)));
99 }
100}
101
Zhongxing Xu7ce351d2010-11-01 09:09:44 +0000102void GRExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *E,
103 const MemRegion *Dest,
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000104 ExplodedNode *Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +0000105 ExplodedNodeSet &Dst) {
Zhongxing Xu7ce351d2010-11-01 09:09:44 +0000106 if (!Dest)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000107 Dest = svalBuilder.getRegionManager().getCXXTempObjectRegion(E,
Zhongxing Xu7ce351d2010-11-01 09:09:44 +0000108 Pred->getLocationContext());
109
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000110 if (E->isElidable()) {
111 VisitAggExpr(E->getArg(0), Dest, Pred, Dst);
112 return;
113 }
114
115 const CXXConstructorDecl *CD = E->getConstructor();
116 assert(CD);
117
Zhongxing Xu7b99d122010-05-06 02:59:29 +0000118 if (!(CD->isThisDeclarationADefinition() && AMgr.shouldInlineCall()))
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000119 // FIXME: invalidate the object.
120 return;
121
122
123 // Evaluate other arguments.
Ted Kremenek9c149532010-12-01 21:57:22 +0000124 ExplodedNodeSet argsEvaluated;
Zhongxing Xu107ccd12010-04-20 05:40:40 +0000125 const FunctionProtoType *FnType = CD->getType()->getAs<FunctionProtoType>();
Ted Kremenek9c149532010-12-01 21:57:22 +0000126 evalArguments(E->arg_begin(), E->arg_end(), FnType, Pred, argsEvaluated);
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000127 // The callee stack frame context used to create the 'this' parameter region.
128 const StackFrameContext *SFC = AMgr.getStackFrame(CD,
129 Pred->getLocationContext(),
Ted Kremenek892697d2010-12-16 07:46:53 +0000130 E, Builder->getBlock(),
131 Builder->getIndex());
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000132
Zhongxing Xu9dc84c92010-11-16 07:52:17 +0000133 const CXXThisRegion *ThisR =getCXXThisRegion(E->getConstructor()->getParent(),
134 SFC);
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000135
Zhongxing Xu19b78d92010-11-24 08:53:20 +0000136 CallEnter Loc(E, SFC, Pred->getLocationContext());
Ted Kremenek9c149532010-12-01 21:57:22 +0000137 for (ExplodedNodeSet::iterator NI = argsEvaluated.begin(),
138 NE = argsEvaluated.end(); NI != NE; ++NI) {
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000139 const GRState *state = GetState(*NI);
Zhongxing Xu3bf185b2010-08-24 04:26:55 +0000140 // Setup 'this' region, so that the ctor is evaluated on the object pointed
141 // by 'Dest'.
Zhongxing Xu7ce351d2010-11-01 09:09:44 +0000142 state = state->bindLoc(loc::MemRegionVal(ThisR), loc::MemRegionVal(Dest));
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000143 ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
144 if (N)
145 Dst.Add(N);
146 }
147}
148
Zhongxing Xub13453b2010-11-20 06:53:12 +0000149void GRExprEngine::VisitCXXDestructor(const CXXDestructorDecl *DD,
150 const MemRegion *Dest,
151 const Stmt *S,
152 ExplodedNode *Pred,
153 ExplodedNodeSet &Dst) {
154 if (!(DD->isThisDeclarationADefinition() && AMgr.shouldInlineCall()))
155 return;
156 // Create the context for 'this' region.
157 const StackFrameContext *SFC = AMgr.getStackFrame(DD,
158 Pred->getLocationContext(),
Ted Kremenek892697d2010-12-16 07:46:53 +0000159 S, Builder->getBlock(),
Zhongxing Xub13453b2010-11-20 06:53:12 +0000160 Builder->getIndex());
161
162 const CXXThisRegion *ThisR = getCXXThisRegion(DD->getParent(), SFC);
163
Zhongxing Xu19b78d92010-11-24 08:53:20 +0000164 CallEnter PP(S, SFC, Pred->getLocationContext());
Zhongxing Xub13453b2010-11-20 06:53:12 +0000165
166 const GRState *state = Pred->getState();
167 state = state->bindLoc(loc::MemRegionVal(ThisR), loc::MemRegionVal(Dest));
168 ExplodedNode *N = Builder->generateNode(PP, state, Pred);
169 if (N)
170 Dst.Add(N);
171}
172
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000173void GRExprEngine::VisitCXXMemberCallExpr(const CXXMemberCallExpr *MCE,
174 ExplodedNode *Pred,
175 ExplodedNodeSet &Dst) {
176 // Get the method type.
177 const FunctionProtoType *FnType =
178 MCE->getCallee()->getType()->getAs<FunctionProtoType>();
179 assert(FnType && "Method type not available");
180
181 // Evaluate explicit arguments with a worklist.
Ted Kremenek9c149532010-12-01 21:57:22 +0000182 ExplodedNodeSet argsEvaluated;
183 evalArguments(MCE->arg_begin(), MCE->arg_end(), FnType, Pred, argsEvaluated);
Zhongxing Xu107ccd12010-04-20 05:40:40 +0000184
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000185 // Evaluate the implicit object argument.
Ted Kremenek9c149532010-12-01 21:57:22 +0000186 ExplodedNodeSet AllargsEvaluated;
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000187 const MemberExpr *ME = dyn_cast<MemberExpr>(MCE->getCallee()->IgnoreParens());
188 if (!ME)
189 return;
190 Expr *ObjArgExpr = ME->getBase();
Ted Kremenek9c149532010-12-01 21:57:22 +0000191 for (ExplodedNodeSet::iterator I = argsEvaluated.begin(),
192 E = argsEvaluated.end(); I != E; ++I) {
Ted Kremenek9c149532010-12-01 21:57:22 +0000193 Visit(ObjArgExpr, *I, AllargsEvaluated);
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000194 }
195
Ted Kremeneka54e8242010-09-30 01:06:29 +0000196 // Now evaluate the call itself.
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000197 const CXXMethodDecl *MD = cast<CXXMethodDecl>(ME->getMemberDecl());
198 assert(MD && "not a CXXMethodDecl?");
Ted Kremenek9c149532010-12-01 21:57:22 +0000199 evalMethodCall(MCE, MD, ObjArgExpr, Pred, AllargsEvaluated, Dst);
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000200}
201
202void GRExprEngine::VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *C,
203 ExplodedNode *Pred,
204 ExplodedNodeSet &Dst) {
205 const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(C->getCalleeDecl());
206 if (!MD) {
207 // If the operator doesn't represent a method call treat as regural call.
Ted Kremenek892697d2010-12-16 07:46:53 +0000208 VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst);
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000209 return;
210 }
211
212 // Determine the type of function we're calling (if available).
213 const FunctionProtoType *Proto = NULL;
214 QualType FnType = C->getCallee()->IgnoreParens()->getType();
215 if (const PointerType *FnTypePtr = FnType->getAs<PointerType>())
216 Proto = FnTypePtr->getPointeeType()->getAs<FunctionProtoType>();
217
218 // Evaluate arguments treating the first one (object method is called on)
219 // as alvalue.
Ted Kremenek9c149532010-12-01 21:57:22 +0000220 ExplodedNodeSet argsEvaluated;
221 evalArguments(C->arg_begin(), C->arg_end(), Proto, Pred, argsEvaluated, true);
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000222
223 // Now evaluate the call itself.
Ted Kremenek9c149532010-12-01 21:57:22 +0000224 evalMethodCall(C, MD, C->getArg(0), Pred, argsEvaluated, Dst);
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000225}
226
Ted Kremenek9c149532010-12-01 21:57:22 +0000227void GRExprEngine::evalMethodCall(const CallExpr *MCE, const CXXMethodDecl *MD,
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000228 const Expr *ThisExpr, ExplodedNode *Pred,
229 ExplodedNodeSet &Src, ExplodedNodeSet &Dst) {
230 // Allow checkers to pre-visit the member call.
231 ExplodedNodeSet PreVisitChecks;
232 CheckerVisit(MCE, PreVisitChecks, Src, PreVisitStmtCallback);
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000233
Ted Kremeneka54e8242010-09-30 01:06:29 +0000234 if (!(MD->isThisDeclarationADefinition() && AMgr.shouldInlineCall())) {
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000235 // FIXME: conservative method call evaluation.
Ted Kremeneka54e8242010-09-30 01:06:29 +0000236 CheckerVisit(MCE, Dst, PreVisitChecks, PostVisitStmtCallback);
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000237 return;
Ted Kremeneka54e8242010-09-30 01:06:29 +0000238 }
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000239
240 const StackFrameContext *SFC = AMgr.getStackFrame(MD,
241 Pred->getLocationContext(),
Ted Kremenek892697d2010-12-16 07:46:53 +0000242 MCE,
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000243 Builder->getBlock(),
244 Builder->getIndex());
Zhongxing Xu32303022010-11-24 13:48:50 +0000245 const CXXThisRegion *ThisR = getCXXThisRegion(MD, SFC);
Zhongxing Xu19b78d92010-11-24 08:53:20 +0000246 CallEnter Loc(MCE, SFC, Pred->getLocationContext());
Ted Kremeneka54e8242010-09-30 01:06:29 +0000247 for (ExplodedNodeSet::iterator I = PreVisitChecks.begin(),
248 E = PreVisitChecks.end(); I != E; ++I) {
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000249 // Set up 'this' region.
250 const GRState *state = GetState(*I);
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000251 state = state->bindLoc(loc::MemRegionVal(ThisR), state->getSVal(ThisExpr));
252 Dst.Add(Builder->generateNode(Loc, state, *I));
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000253 }
254}
255
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000256void GRExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000257 ExplodedNodeSet &Dst) {
258 if (CNE->isArray()) {
259 // FIXME: allocating an array has not been handled.
260 return;
261 }
262
263 unsigned Count = Builder->getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000264 DefinedOrUnknownSVal symVal =
265 svalBuilder.getConjuredSymbolVal(NULL, CNE, CNE->getType(), Count);
266 const MemRegion *NewReg = cast<loc::MemRegionVal>(symVal).getRegion();
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000267
268 QualType ObjTy = CNE->getType()->getAs<PointerType>()->getPointeeType();
269
270 const ElementRegion *EleReg =
271 getStoreManager().GetElementZeroRegion(NewReg, ObjTy);
272
Zhongxing Xub17b1b32010-04-20 03:37:34 +0000273 // Evaluate constructor arguments.
274 const FunctionProtoType *FnType = NULL;
275 const CXXConstructorDecl *CD = CNE->getConstructor();
276 if (CD)
277 FnType = CD->getType()->getAs<FunctionProtoType>();
Ted Kremenek9c149532010-12-01 21:57:22 +0000278 ExplodedNodeSet argsEvaluated;
279 evalArguments(CNE->constructor_arg_begin(), CNE->constructor_arg_end(),
280 FnType, Pred, argsEvaluated);
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000281
Zhongxing Xub17b1b32010-04-20 03:37:34 +0000282 // Initialize the object region and bind the 'new' expression.
Ted Kremenek9c149532010-12-01 21:57:22 +0000283 for (ExplodedNodeSet::iterator I = argsEvaluated.begin(),
284 E = argsEvaluated.end(); I != E; ++I) {
Zhongxing Xub17b1b32010-04-20 03:37:34 +0000285 const GRState *state = GetState(*I);
286
287 if (ObjTy->isRecordType()) {
Jordy Roseff59efd2010-08-03 20:44:35 +0000288 state = state->InvalidateRegion(EleReg, CNE, Count);
Zhongxing Xub17b1b32010-04-20 03:37:34 +0000289 } else {
290 if (CNE->hasInitializer()) {
291 SVal V = state->getSVal(*CNE->constructor_arg_begin());
292 state = state->bindLoc(loc::MemRegionVal(EleReg), V);
293 } else {
294 // Explicitly set to undefined, because currently we retrieve symbolic
295 // value from symbolic region.
296 state = state->bindLoc(loc::MemRegionVal(EleReg), UndefinedVal());
297 }
298 }
299 state = state->BindExpr(CNE, loc::MemRegionVal(EleReg));
Zhongxing Xu978b9352010-04-21 02:20:10 +0000300 MakeNode(Dst, CNE, *I, state);
Zhongxing Xub17b1b32010-04-20 03:37:34 +0000301 }
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000302}
303
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000304void GRExprEngine::VisitCXXDeleteExpr(const CXXDeleteExpr *CDE,
305 ExplodedNode *Pred,ExplodedNodeSet &Dst) {
Zhongxing Xu6b851382010-04-21 02:17:31 +0000306 // Should do more checking.
Ted Kremenek9c149532010-12-01 21:57:22 +0000307 ExplodedNodeSet Argevaluated;
308 Visit(CDE->getArgument(), Pred, Argevaluated);
309 for (ExplodedNodeSet::iterator I = Argevaluated.begin(),
310 E = Argevaluated.end(); I != E; ++I) {
Zhongxing Xu6b851382010-04-21 02:17:31 +0000311 const GRState *state = GetState(*I);
312 MakeNode(Dst, CDE, *I, state);
313 }
314}
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000315
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000316void GRExprEngine::VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
Zhongxing Xu6b851382010-04-21 02:17:31 +0000317 ExplodedNodeSet &Dst) {
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000318 // Get the this object region from StoreManager.
319 const MemRegion *R =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000320 svalBuilder.getRegionManager().getCXXThisRegion(
Zhongxing Xucb7464a2010-04-19 12:51:02 +0000321 getContext().getCanonicalType(TE->getType()),
322 Pred->getLocationContext());
323
324 const GRState *state = GetState(Pred);
325 SVal V = state->getSVal(loc::MemRegionVal(R));
326 MakeNode(Dst, TE, Pred, state->BindExpr(TE, V));
327}