blob: c9c419beaa0bad1059c516415a0a94658abe0b37 [file] [log] [blame]
Ted Kremenek77349cb2008-02-14 22:13:12 +00001//=-- GRExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
Ted Kremenek64924852008-01-31 02:35:41 +00002//
Ted Kremenek4af84312008-01-31 06:49:09 +00003// The LLVM Compiler Infrastructure
Ted Kremenekd27f8162008-01-15 23:55:06 +00004//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
Ted Kremenek77349cb2008-02-14 22:13:12 +000010// This file defines a meta-engine for path-sensitive dataflow analysis that
11// is built on GREngine, but provides the boilerplate to execute transfer
12// functions and build the ExplodedGraph at the expression level.
Ted Kremenekd27f8162008-01-15 23:55:06 +000013//
14//===----------------------------------------------------------------------===//
15
Zhongxing Xu668399b2009-11-24 08:24:26 +000016#include "GRExprEngineInternalChecks.h"
Ted Kremenek77349cb2008-02-14 22:13:12 +000017#include "clang/Analysis/PathSensitive/GRExprEngine.h"
Ted Kremenek41573eb2009-02-14 01:43:44 +000018#include "clang/Analysis/PathSensitive/GRExprEngineBuilders.h"
Ted Kremenek5a5d98b2009-07-22 21:43:51 +000019#include "clang/Analysis/PathSensitive/Checker.h"
Chris Lattner16f00492009-04-26 01:32:48 +000020#include "clang/AST/ParentMap.h"
21#include "clang/AST/StmtObjC.h"
Chris Lattner1b63e4f2009-06-14 01:54:56 +000022#include "clang/Basic/Builtins.h"
Chris Lattner16f00492009-04-26 01:32:48 +000023#include "clang/Basic/SourceManager.h"
Ted Kremeneke97ca062008-03-07 20:57:30 +000024#include "clang/Basic/SourceManager.h"
Ted Kremenek0bed8a12009-03-11 02:41:36 +000025#include "clang/Basic/PrettyStackTrace.h"
Ted Kremeneka95d3752008-09-13 05:16:45 +000026#include "llvm/Support/raw_ostream.h"
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +000027#include "llvm/ADT/ImmutableList.h"
Douglas Gregor55d3f7a2009-10-29 00:41:01 +000028#include "llvm/ADT/StringSwitch.h"
Ted Kremenek4323a572008-07-10 22:03:41 +000029
Ted Kremenek0f5f0592008-02-27 06:07:00 +000030#ifndef NDEBUG
31#include "llvm/Support/GraphWriter.h"
Ted Kremenek0f5f0592008-02-27 06:07:00 +000032#endif
33
Ted Kremenekb387a3f2008-02-14 22:16:04 +000034using namespace clang;
35using llvm::dyn_cast;
36using llvm::cast;
37using llvm::APSInt;
Ted Kremenekab2b8c52008-01-23 19:59:44 +000038
Ted Kremeneke695e1c2008-04-15 23:06:53 +000039//===----------------------------------------------------------------------===//
Ted Kremenek32c49952009-11-25 21:51:20 +000040// Utility functions.
41//===----------------------------------------------------------------------===//
42
43static inline Selector GetNullarySelector(const char* name, ASTContext& Ctx) {
44 IdentifierInfo* II = &Ctx.Idents.get(name);
45 return Ctx.Selectors.getSelector(0, &II);
46}
47
48//===----------------------------------------------------------------------===//
Ted Kremenek5a5d98b2009-07-22 21:43:51 +000049// Batch auditor. DEPRECATED.
Ted Kremeneke695e1c2008-04-15 23:06:53 +000050//===----------------------------------------------------------------------===//
51
Ted Kremenekbdb435d2008-07-11 18:37:32 +000052namespace {
53
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000054class MappedBatchAuditor : public GRSimpleAPICheck {
Ted Kremenekbdb435d2008-07-11 18:37:32 +000055 typedef llvm::ImmutableList<GRSimpleAPICheck*> Checks;
56 typedef llvm::DenseMap<void*,Checks> MapTy;
Mike Stump1eb44332009-09-09 15:08:12 +000057
Ted Kremenekbdb435d2008-07-11 18:37:32 +000058 MapTy M;
59 Checks::Factory F;
Ted Kremenek536aa022009-03-30 17:53:05 +000060 Checks AllStmts;
Ted Kremenekbdb435d2008-07-11 18:37:32 +000061
62public:
Ted Kremenek536aa022009-03-30 17:53:05 +000063 MappedBatchAuditor(llvm::BumpPtrAllocator& Alloc) :
64 F(Alloc), AllStmts(F.GetEmptyList()) {}
Mike Stump1eb44332009-09-09 15:08:12 +000065
Ted Kremenekbdb435d2008-07-11 18:37:32 +000066 virtual ~MappedBatchAuditor() {
67 llvm::DenseSet<GRSimpleAPICheck*> AlreadyVisited;
Mike Stump1eb44332009-09-09 15:08:12 +000068
Ted Kremenekbdb435d2008-07-11 18:37:32 +000069 for (MapTy::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI)
70 for (Checks::iterator I=MI->second.begin(), E=MI->second.end(); I!=E;++I){
71
72 GRSimpleAPICheck* check = *I;
Mike Stump1eb44332009-09-09 15:08:12 +000073
Ted Kremenekbdb435d2008-07-11 18:37:32 +000074 if (AlreadyVisited.count(check))
75 continue;
Mike Stump1eb44332009-09-09 15:08:12 +000076
Ted Kremenekbdb435d2008-07-11 18:37:32 +000077 AlreadyVisited.insert(check);
78 delete check;
79 }
80 }
81
Ted Kremenek536aa022009-03-30 17:53:05 +000082 void AddCheck(GRSimpleAPICheck *A, Stmt::StmtClass C) {
Ted Kremenekbdb435d2008-07-11 18:37:32 +000083 assert (A && "Check cannot be null.");
84 void* key = reinterpret_cast<void*>((uintptr_t) C);
85 MapTy::iterator I = M.find(key);
86 M[key] = F.Concat(A, I == M.end() ? F.GetEmptyList() : I->second);
87 }
Mike Stump1eb44332009-09-09 15:08:12 +000088
Ted Kremenek536aa022009-03-30 17:53:05 +000089 void AddCheck(GRSimpleAPICheck *A) {
90 assert (A && "Check cannot be null.");
Mike Stump1eb44332009-09-09 15:08:12 +000091 AllStmts = F.Concat(A, AllStmts);
Ted Kremenek536aa022009-03-30 17:53:05 +000092 }
Ted Kremenekcf118d42009-02-04 23:49:09 +000093
Zhongxing Xu031ccc02009-08-06 12:48:26 +000094 virtual bool Audit(ExplodedNode* N, GRStateManager& VMgr) {
Ted Kremenek536aa022009-03-30 17:53:05 +000095 // First handle the auditors that accept all statements.
96 bool isSink = false;
97 for (Checks::iterator I = AllStmts.begin(), E = AllStmts.end(); I!=E; ++I)
98 isSink |= (*I)->Audit(N, VMgr);
Mike Stump1eb44332009-09-09 15:08:12 +000099
Ted Kremenek536aa022009-03-30 17:53:05 +0000100 // Next handle the auditors that accept only specific statements.
Ted Kremenek5f85e172009-07-22 22:35:28 +0000101 const Stmt* S = cast<PostStmt>(N->getLocation()).getStmt();
Ted Kremenekbdb435d2008-07-11 18:37:32 +0000102 void* key = reinterpret_cast<void*>((uintptr_t) S->getStmtClass());
103 MapTy::iterator MI = M.find(key);
Mike Stump1eb44332009-09-09 15:08:12 +0000104 if (MI != M.end()) {
Ted Kremenek536aa022009-03-30 17:53:05 +0000105 for (Checks::iterator I=MI->second.begin(), E=MI->second.end(); I!=E; ++I)
106 isSink |= (*I)->Audit(N, VMgr);
107 }
Mike Stump1eb44332009-09-09 15:08:12 +0000108
109 return isSink;
Ted Kremenekbdb435d2008-07-11 18:37:32 +0000110 }
111};
112
113} // end anonymous namespace
114
115//===----------------------------------------------------------------------===//
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000116// Checker worklist routines.
117//===----------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +0000118
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000119void GRExprEngine::CheckerVisit(Stmt *S, ExplodedNodeSet &Dst,
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000120 ExplodedNodeSet &Src, bool isPrevisit) {
Mike Stump1eb44332009-09-09 15:08:12 +0000121
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000122 if (Checkers.empty()) {
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000123 Dst = Src;
124 return;
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000125 }
Mike Stump1eb44332009-09-09 15:08:12 +0000126
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000127 ExplodedNodeSet Tmp;
128 ExplodedNodeSet *PrevSet = &Src;
Mike Stump1eb44332009-09-09 15:08:12 +0000129
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000130 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E;++I){
Ted Kremenek094bef52009-10-30 17:47:32 +0000131 ExplodedNodeSet *CurrSet = (I+1 == E) ? &Dst
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000132 : (PrevSet == &Tmp) ? &Src : &Tmp;
Ted Kremenek094bef52009-10-30 17:47:32 +0000133
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000134 CurrSet->clear();
Zhongxing Xuec9227f2009-10-29 02:09:30 +0000135 void *tag = I->first;
136 Checker *checker = I->second;
Ted Kremenekb801b732009-11-25 21:40:22 +0000137
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000138 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000139 NI != NE; ++NI)
140 checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag, isPrevisit);
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000141 PrevSet = CurrSet;
142 }
143
144 // Don't autotransition. The CheckerContext objects should do this
145 // automatically.
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000146}
147
148void GRExprEngine::CheckerEvalNilReceiver(const ObjCMessageExpr *ME,
149 ExplodedNodeSet &Dst,
150 const GRState *state,
151 ExplodedNode *Pred) {
152 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
153 void *tag = I->first;
154 Checker *checker = I->second;
155
156 if (checker->GR_EvalNilReceiver(Dst, *Builder, *this, ME, Pred, state, tag))
157 break;
158 }
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000159}
160
Zhongxing Xu935ef902009-12-07 09:17:35 +0000161// CheckerEvalCall returns true if one of the checkers processed the node.
162// This may return void when all call evaluation logic goes to some checker
163// in the future.
164bool GRExprEngine::CheckerEvalCall(const CallExpr *CE,
165 ExplodedNodeSet &Dst,
166 ExplodedNode *Pred) {
167 bool Evaluated = false;
168
169 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
170 void *tag = I->first;
171 Checker *checker = I->second;
172
173 if (checker->GR_EvalCallExpr(Dst, *Builder, *this, CE, Pred, tag)) {
174 Evaluated = true;
175 break;
176 }
177 }
178
179 return Evaluated;
180}
181
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000182// FIXME: This is largely copy-paste from CheckerVisit(). Need to
183// unify.
Ted Kremenek50ecd152009-11-05 00:42:23 +0000184void GRExprEngine::CheckerVisitBind(const Stmt *AssignE, const Stmt *StoreE,
185 ExplodedNodeSet &Dst,
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000186 ExplodedNodeSet &Src,
187 SVal location, SVal val, bool isPrevisit) {
188
189 if (Checkers.empty()) {
190 Dst = Src;
191 return;
192 }
193
194 ExplodedNodeSet Tmp;
195 ExplodedNodeSet *PrevSet = &Src;
196
197 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E; ++I)
198 {
199 ExplodedNodeSet *CurrSet = (I+1 == E) ? &Dst
200 : (PrevSet == &Tmp) ? &Src : &Tmp;
201
202 CurrSet->clear();
203 void *tag = I->first;
204 Checker *checker = I->second;
205
206 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
207 NI != NE; ++NI)
Ted Kremenek50ecd152009-11-05 00:42:23 +0000208 checker->GR_VisitBind(*CurrSet, *Builder, *this, AssignE, StoreE,
209 *NI, tag, location, val, isPrevisit);
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000210
211 // Update which NodeSet is the current one.
212 PrevSet = CurrSet;
213 }
214
215 // Don't autotransition. The CheckerContext objects should do this
216 // automatically.
217}
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000218//===----------------------------------------------------------------------===//
Ted Kremenekbdb435d2008-07-11 18:37:32 +0000219// Engine construction and deletion.
220//===----------------------------------------------------------------------===//
221
Ted Kremenek32c49952009-11-25 21:51:20 +0000222static void RegisterInternalChecks(GRExprEngine &Eng) {
223 // Register internal "built-in" BugTypes with the BugReporter. These BugTypes
224 // are different than what probably many checks will do since they don't
225 // create BugReports on-the-fly but instead wait until GRExprEngine finishes
226 // analyzing a function. Generation of BugReport objects is done via a call
227 // to 'FlushReports' from BugReporter.
228 // The following checks do not need to have their associated BugTypes
229 // explicitly registered with the BugReporter. If they issue any BugReports,
230 // their associated BugType will get registered with the BugReporter
231 // automatically. Note that the check itself is owned by the GRExprEngine
232 // object.
233 RegisterAttrNonNullChecker(Eng);
234 RegisterCallAndMessageChecker(Eng);
235 RegisterDereferenceChecker(Eng);
236 RegisterVLASizeChecker(Eng);
237 RegisterDivZeroChecker(Eng);
238 RegisterReturnStackAddressChecker(Eng);
239 RegisterReturnUndefChecker(Eng);
240 RegisterUndefinedArraySubscriptChecker(Eng);
241 RegisterUndefinedAssignmentChecker(Eng);
242 RegisterUndefBranchChecker(Eng);
243 RegisterUndefResultChecker(Eng);
Zhongxing Xu935ef902009-12-07 09:17:35 +0000244
245 // This is not a checker yet.
246 RegisterNoReturnFunctionChecker(Eng);
Zhongxing Xu7c9624b2009-12-08 09:07:59 +0000247 RegisterBuiltinFunctionChecker(Eng);
Ted Kremeneke448ab42008-05-01 18:33:28 +0000248}
249
Zhongxing Xu5032ffe2009-08-25 06:51:30 +0000250GRExprEngine::GRExprEngine(AnalysisManager &mgr)
Zhongxing Xu25e695b2009-08-15 03:17:38 +0000251 : AMgr(mgr),
Mike Stump1eb44332009-09-09 15:08:12 +0000252 CoreEngine(mgr.getASTContext(), *this),
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000253 G(CoreEngine.getGraph()),
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000254 Builder(NULL),
Mike Stump1eb44332009-09-09 15:08:12 +0000255 StateMgr(G.getContext(), mgr.getStoreManagerCreator(),
Zhongxing Xu5032ffe2009-08-25 06:51:30 +0000256 mgr.getConstraintManagerCreator(), G.getAllocator()),
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000257 SymMgr(StateMgr.getSymbolManager()),
Ted Kremenek8e5fb282009-04-09 16:46:55 +0000258 ValMgr(StateMgr.getValueManager()),
Ted Kremenek06669c82009-07-16 01:32:00 +0000259 SVator(ValMgr.getSValuator()),
Ted Kremeneke448ab42008-05-01 18:33:28 +0000260 CurrentStmt(NULL),
Zhongxing Xua5a41662008-12-22 08:30:52 +0000261 NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL),
Mike Stump1eb44332009-09-09 15:08:12 +0000262 RaiseSel(GetNullarySelector("raise", G.getContext())),
Ted Kremenekc80135b2009-11-25 21:45:48 +0000263 BR(mgr, *this)
264{
265 // Register internal checks.
Ted Kremenek32c49952009-11-25 21:51:20 +0000266 RegisterInternalChecks(*this);
Ted Kremenekc80135b2009-11-25 21:45:48 +0000267}
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000268
Mike Stump1eb44332009-09-09 15:08:12 +0000269GRExprEngine::~GRExprEngine() {
Ted Kremenekcf118d42009-02-04 23:49:09 +0000270 BR.FlushReports();
Ted Kremeneke448ab42008-05-01 18:33:28 +0000271 delete [] NSExceptionInstanceRaiseSelectors;
Ted Kremenek094bef52009-10-30 17:47:32 +0000272 for (CheckersOrdered::iterator I=Checkers.begin(), E=Checkers.end(); I!=E;++I)
Zhongxing Xuec9227f2009-10-29 02:09:30 +0000273 delete I->second;
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000274}
275
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000276//===----------------------------------------------------------------------===//
277// Utility methods.
278//===----------------------------------------------------------------------===//
279
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000280void GRExprEngine::setTransferFunctions(GRTransferFuncs* tf) {
Ted Kremenek729a9a22008-07-17 23:15:45 +0000281 StateMgr.TF = tf;
Ted Kremenek1fb7d0c2009-11-03 23:30:34 +0000282 tf->RegisterChecks(*this);
Ted Kremenek1c72ef02008-08-16 00:49:49 +0000283 tf->RegisterPrinters(getStateManager().Printers);
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000284}
285
Ted Kremenekbdb435d2008-07-11 18:37:32 +0000286void GRExprEngine::AddCheck(GRSimpleAPICheck* A, Stmt::StmtClass C) {
287 if (!BatchAuditor)
288 BatchAuditor.reset(new MappedBatchAuditor(getGraph().getAllocator()));
Mike Stump1eb44332009-09-09 15:08:12 +0000289
Ted Kremenekbdb435d2008-07-11 18:37:32 +0000290 ((MappedBatchAuditor*) BatchAuditor.get())->AddCheck(A, C);
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000291}
292
Ted Kremenek536aa022009-03-30 17:53:05 +0000293void GRExprEngine::AddCheck(GRSimpleAPICheck *A) {
294 if (!BatchAuditor)
295 BatchAuditor.reset(new MappedBatchAuditor(getGraph().getAllocator()));
296
297 ((MappedBatchAuditor*) BatchAuditor.get())->AddCheck(A);
298}
299
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000300const GRState* GRExprEngine::getInitialState(const LocationContext *InitLoc) {
301 const GRState *state = StateMgr.getInitialState(InitLoc);
Mike Stump1eb44332009-09-09 15:08:12 +0000302
Ted Kremenekcfcd7fd2009-09-09 20:36:12 +0000303 // Preconditions.
304
Ted Kremenek52e56022009-04-10 00:59:50 +0000305 // FIXME: It would be nice if we had a more general mechanism to add
306 // such preconditions. Some day.
Ted Kremenekcfcd7fd2009-09-09 20:36:12 +0000307 const Decl *D = InitLoc->getDecl();
308
309 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
310 // Precondition: the first argument of 'main' is an integer guaranteed
311 // to be > 0.
Daniel Dunbar01eb9b92009-10-18 21:17:35 +0000312 if (FD->getIdentifier()->getName() == "main" &&
Ted Kremenek52e56022009-04-10 00:59:50 +0000313 FD->getNumParams() > 0) {
314 const ParmVarDecl *PD = FD->getParamDecl(0);
315 QualType T = PD->getType();
316 if (T->isIntegerType())
Ted Kremenekd17da2b2009-08-21 22:28:32 +0000317 if (const MemRegion *R = state->getRegion(PD, InitLoc)) {
Ted Kremenek3ff12592009-06-19 17:10:32 +0000318 SVal V = state->getSVal(loc::MemRegionVal(R));
Ted Kremenek5b9bd212009-09-11 22:07:28 +0000319 SVal Constraint_untested = EvalBinOp(state, BinaryOperator::GT, V,
320 ValMgr.makeZeroVal(T),
321 getContext().IntTy);
Ted Kremeneka591bc02009-06-18 22:57:13 +0000322
Ted Kremenek5b9bd212009-09-11 22:07:28 +0000323 if (DefinedOrUnknownSVal *Constraint =
324 dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested)) {
325 if (const GRState *newState = state->Assume(*Constraint, true))
326 state = newState;
327 }
Ted Kremenek52e56022009-04-10 00:59:50 +0000328 }
329 }
Ted Kremenekcfcd7fd2009-09-09 20:36:12 +0000330 }
331 else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
332 // Precondition: 'self' is always non-null upon entry to an Objective-C
333 // method.
334 const ImplicitParamDecl *SelfD = MD->getSelfDecl();
335 const MemRegion *R = state->getRegion(SelfD, InitLoc);
336 SVal V = state->getSVal(loc::MemRegionVal(R));
337
338 if (const Loc *LV = dyn_cast<Loc>(&V)) {
339 // Assume that the pointer value in 'self' is non-null.
Ted Kremenek5b9bd212009-09-11 22:07:28 +0000340 state = state->Assume(*LV, true);
Ted Kremenekcfcd7fd2009-09-09 20:36:12 +0000341 assert(state && "'self' cannot be null");
342 }
343 }
344
Ted Kremenek52e56022009-04-10 00:59:50 +0000345 return state;
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000346}
347
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000348//===----------------------------------------------------------------------===//
349// Top-level transfer function logic (Dispatcher).
350//===----------------------------------------------------------------------===//
351
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000352void GRExprEngine::ProcessStmt(Stmt* S, GRStmtNodeBuilder& builder) {
Mike Stump1eb44332009-09-09 15:08:12 +0000353
Ted Kremenek0bed8a12009-03-11 02:41:36 +0000354 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
355 S->getLocStart(),
356 "Error evaluating statement");
Mike Stump1eb44332009-09-09 15:08:12 +0000357
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000358 Builder = &builder;
Ted Kremenek846d4e92008-04-24 23:35:58 +0000359 EntryNode = builder.getLastNode();
Mike Stump1eb44332009-09-09 15:08:12 +0000360
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000361 CurrentStmt = S;
Mike Stump1eb44332009-09-09 15:08:12 +0000362
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000363 // Set up our simple checks.
Ted Kremenekbdb435d2008-07-11 18:37:32 +0000364 if (BatchAuditor)
365 Builder->setAuditor(BatchAuditor.get());
Mike Stump1eb44332009-09-09 15:08:12 +0000366
367 // Create the cleaned state.
Zhongxing Xub317f8f2009-09-10 05:44:00 +0000368 SymbolReaper SymReaper(Builder->getBasePredecessor()->getLiveVariables(),
369 SymMgr);
Zhongxing Xuc9994962009-08-27 06:55:26 +0000370 CleanedState = AMgr.shouldPurgeDead()
371 ? StateMgr.RemoveDeadBindings(EntryNode->getState(), CurrentStmt, SymReaper)
372 : EntryNode->getState();
Ted Kremenek241677a2009-01-21 22:26:05 +0000373
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000374 // Process any special transfer function for dead symbols.
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000375 ExplodedNodeSet Tmp;
Mike Stump1eb44332009-09-09 15:08:12 +0000376
Ted Kremenek241677a2009-01-21 22:26:05 +0000377 if (!SymReaper.hasDeadSymbols())
Ted Kremenek846d4e92008-04-24 23:35:58 +0000378 Tmp.Add(EntryNode);
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000379 else {
380 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000381 SaveOr OldHasGen(Builder->HasGeneratedNode);
382
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000383 SaveAndRestore<bool> OldPurgeDeadSymbols(Builder->PurgingDeadSymbols);
384 Builder->PurgingDeadSymbols = true;
Mike Stump1eb44332009-09-09 15:08:12 +0000385
Zhongxing Xu94006132009-11-13 06:53:04 +0000386 // FIXME: This should soon be removed.
387 ExplodedNodeSet Tmp2;
388 getTF().EvalDeadSymbols(Tmp2, *this, *Builder, EntryNode, S,
Ted Kremenek241677a2009-01-21 22:26:05 +0000389 CleanedState, SymReaper);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000390
Zhongxing Xu94006132009-11-13 06:53:04 +0000391 if (Checkers.empty())
392 Tmp = Tmp2;
393 else {
394 ExplodedNodeSet Tmp3;
395 ExplodedNodeSet *SrcSet = &Tmp2;
396 for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
397 I != E; ++I) {
398 ExplodedNodeSet *DstSet = (I+1 == E) ? &Tmp
399 : (SrcSet == &Tmp2) ? &Tmp3
400 : &Tmp2;
Zhongxing Xuc5419cc2009-11-17 07:19:51 +0000401 DstSet->clear();
Zhongxing Xu94006132009-11-13 06:53:04 +0000402 void *tag = I->first;
403 Checker *checker = I->second;
404 for (ExplodedNodeSet::iterator NI = SrcSet->begin(), NE = SrcSet->end();
405 NI != NE; ++NI)
406 checker->GR_EvalDeadSymbols(*DstSet, *Builder, *this, S, *NI,
407 SymReaper, tag);
408 SrcSet = DstSet;
409 }
410 }
411
Ted Kremenek846d4e92008-04-24 23:35:58 +0000412 if (!Builder->BuildSinks && !Builder->HasGeneratedNode)
413 Tmp.Add(EntryNode);
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000414 }
Mike Stump1eb44332009-09-09 15:08:12 +0000415
Ted Kremenek846d4e92008-04-24 23:35:58 +0000416 bool HasAutoGenerated = false;
417
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000418 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremenek846d4e92008-04-24 23:35:58 +0000419
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000420 ExplodedNodeSet Dst;
Mike Stump1eb44332009-09-09 15:08:12 +0000421
422 // Set the cleaned state.
Ted Kremenek846d4e92008-04-24 23:35:58 +0000423 Builder->SetCleanedState(*I == EntryNode ? CleanedState : GetState(*I));
Mike Stump1eb44332009-09-09 15:08:12 +0000424
425 // Visit the statement.
Ted Kremenek846d4e92008-04-24 23:35:58 +0000426 Visit(S, *I, Dst);
427
428 // Do we need to auto-generate a node? We only need to do this to generate
429 // a node with a "cleaned" state; GRCoreEngine will actually handle
Mike Stump1eb44332009-09-09 15:08:12 +0000430 // auto-transitions for other cases.
Ted Kremenek846d4e92008-04-24 23:35:58 +0000431 if (Dst.size() == 1 && *Dst.begin() == EntryNode
432 && !Builder->HasGeneratedNode && !HasAutoGenerated) {
433 HasAutoGenerated = true;
434 builder.generateNode(S, GetState(EntryNode), *I);
435 }
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000436 }
Mike Stump1eb44332009-09-09 15:08:12 +0000437
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000438 // NULL out these variables to cleanup.
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000439 CleanedState = NULL;
Ted Kremenek846d4e92008-04-24 23:35:58 +0000440 EntryNode = NULL;
Ted Kremenekdf7533b2008-07-17 21:27:31 +0000441
Ted Kremenekdf7533b2008-07-17 21:27:31 +0000442 CurrentStmt = 0;
Mike Stump1eb44332009-09-09 15:08:12 +0000443
Ted Kremenek846d4e92008-04-24 23:35:58 +0000444 Builder = NULL;
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000445}
446
Mike Stump1eb44332009-09-09 15:08:12 +0000447void GRExprEngine::Visit(Stmt* S, ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Ted Kremenek0bed8a12009-03-11 02:41:36 +0000448 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
449 S->getLocStart(),
450 "Error evaluating statement");
451
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000452 // FIXME: add metadata to the CFG so that we can disable
453 // this check when we KNOW that there is no block-level subexpression.
454 // The motivation is that this check requires a hashtable lookup.
Mike Stump1eb44332009-09-09 15:08:12 +0000455
Zhongxing Xucc025532009-08-25 03:33:41 +0000456 if (S != CurrentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) {
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000457 Dst.Add(Pred);
458 return;
459 }
Mike Stump1eb44332009-09-09 15:08:12 +0000460
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000461 switch (S->getStmtClass()) {
Mike Stump1eb44332009-09-09 15:08:12 +0000462
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000463 default:
464 // Cases we intentionally have "default" handle:
465 // AddrLabelExpr, IntegerLiteral, CharacterLiteral
Mike Stump1eb44332009-09-09 15:08:12 +0000466
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000467 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
468 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000469
Ted Kremenek540cbe22008-04-22 04:56:29 +0000470 case Stmt::ArraySubscriptExprClass:
471 VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst, false);
472 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000473
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000474 case Stmt::AsmStmtClass:
475 VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst);
476 break;
Ted Kremenek67d12872009-12-07 22:05:27 +0000477
478 case Stmt::BlockDeclRefExprClass:
479 VisitBlockDeclRefExpr(cast<BlockDeclRefExpr>(S), Pred, Dst, false);
480 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000481
Ted Kremenekc95ad9f2009-11-25 01:33:13 +0000482 case Stmt::BlockExprClass:
483 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
484 break;
485
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000486 case Stmt::BinaryOperatorClass: {
487 BinaryOperator* B = cast<BinaryOperator>(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000488
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000489 if (B->isLogicalOp()) {
490 VisitLogicalExpr(B, Pred, Dst);
491 break;
492 }
493 else if (B->getOpcode() == BinaryOperator::Comma) {
Ted Kremeneka8538d92009-02-13 01:45:31 +0000494 const GRState* state = GetState(Pred);
Ted Kremenek8e029342009-08-27 22:17:37 +0000495 MakeNode(Dst, B, Pred, state->BindExpr(B, state->getSVal(B->getRHS())));
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000496 break;
497 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000498
Zhongxing Xu5032ffe2009-08-25 06:51:30 +0000499 if (AMgr.shouldEagerlyAssume() && (B->isRelationalOp() || B->isEqualityOp())) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000500 ExplodedNodeSet Tmp;
Zhongxing Xu662174ca2009-10-30 07:19:39 +0000501 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp, false);
Mike Stump1eb44332009-09-09 15:08:12 +0000502 EvalEagerlyAssume(Dst, Tmp, cast<Expr>(S));
Ted Kremenek48af2a92009-02-25 22:32:02 +0000503 }
504 else
Zhongxing Xu662174ca2009-10-30 07:19:39 +0000505 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst, false);
Ted Kremenek48af2a92009-02-25 22:32:02 +0000506
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000507 break;
508 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000509
Douglas Gregorb4609802008-11-14 16:09:21 +0000510 case Stmt::CallExprClass:
511 case Stmt::CXXOperatorCallExprClass: {
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000512 CallExpr* C = cast<CallExpr>(S);
513 VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst);
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000514 break;
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000515 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000516
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000517 // FIXME: ChooseExpr is really a constant. We need to fix
518 // the CFG do not model them as explicit control-flow.
Mike Stump1eb44332009-09-09 15:08:12 +0000519
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000520 case Stmt::ChooseExprClass: { // __builtin_choose_expr
521 ChooseExpr* C = cast<ChooseExpr>(S);
522 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
523 break;
524 }
Mike Stump1eb44332009-09-09 15:08:12 +0000525
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000526 case Stmt::CompoundAssignOperatorClass:
Zhongxing Xu662174ca2009-10-30 07:19:39 +0000527 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst, false);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000528 break;
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000529
530 case Stmt::CompoundLiteralExprClass:
531 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst, false);
532 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000533
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000534 case Stmt::ConditionalOperatorClass: { // '?' operator
535 ConditionalOperator* C = cast<ConditionalOperator>(S);
536 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
537 break;
538 }
Mike Stump1eb44332009-09-09 15:08:12 +0000539
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000540 case Stmt::DeclRefExprClass:
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000541 VisitDeclRefExpr(cast<DeclRefExpr>(S), Pred, Dst, false);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000542 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000543
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000544 case Stmt::DeclStmtClass:
545 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
546 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000547
Argyrios Kyrtzidis0835a3c2008-08-18 23:01:59 +0000548 case Stmt::ImplicitCastExprClass:
Douglas Gregor6eec8e82008-10-28 15:36:24 +0000549 case Stmt::CStyleCastExprClass: {
Argyrios Kyrtzidis0835a3c2008-08-18 23:01:59 +0000550 CastExpr* C = cast<CastExpr>(S);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000551 VisitCast(C, C->getSubExpr(), Pred, Dst);
552 break;
553 }
Zhongxing Xuc4f87062008-10-30 05:02:23 +0000554
555 case Stmt::InitListExprClass:
556 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
557 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000558
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000559 case Stmt::MemberExprClass:
Ted Kremenek469ecbd2008-04-21 23:43:38 +0000560 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst, false);
561 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000562
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000563 case Stmt::ObjCIvarRefExprClass:
564 VisitObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst, false);
565 break;
Ted Kremenekaf337412008-11-12 19:24:17 +0000566
567 case Stmt::ObjCForCollectionStmtClass:
568 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
569 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000570
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000571 case Stmt::ObjCMessageExprClass: {
572 VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), Pred, Dst);
573 break;
574 }
Mike Stump1eb44332009-09-09 15:08:12 +0000575
Ted Kremenekbbfd07a2008-12-09 20:18:58 +0000576 case Stmt::ObjCAtThrowStmtClass: {
577 // FIXME: This is not complete. We basically treat @throw as
578 // an abort.
579 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
580 Builder->BuildSinks = true;
581 MakeNode(Dst, S, Pred, GetState(Pred));
582 break;
583 }
Mike Stump1eb44332009-09-09 15:08:12 +0000584
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000585 case Stmt::ParenExprClass:
Ted Kremenek540cbe22008-04-22 04:56:29 +0000586 Visit(cast<ParenExpr>(S)->getSubExpr()->IgnoreParens(), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000587 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000588
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000589 case Stmt::ReturnStmtClass:
590 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
591 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000592
Sebastian Redl05189992008-11-11 17:56:53 +0000593 case Stmt::SizeOfAlignOfExprClass:
594 VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000595 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000596
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000597 case Stmt::StmtExprClass: {
598 StmtExpr* SE = cast<StmtExpr>(S);
Ted Kremeneka3d1eb82009-02-14 05:55:08 +0000599
600 if (SE->getSubStmt()->body_empty()) {
601 // Empty statement expression.
602 assert(SE->getType() == getContext().VoidTy
603 && "Empty statement expression must have void type.");
604 Dst.Add(Pred);
605 break;
606 }
Mike Stump1eb44332009-09-09 15:08:12 +0000607
Ted Kremeneka3d1eb82009-02-14 05:55:08 +0000608 if (Expr* LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
609 const GRState* state = GetState(Pred);
Ted Kremenek8e029342009-08-27 22:17:37 +0000610 MakeNode(Dst, SE, Pred, state->BindExpr(SE, state->getSVal(LastExpr)));
Ted Kremeneka3d1eb82009-02-14 05:55:08 +0000611 }
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000612 else
613 Dst.Add(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +0000614
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000615 break;
616 }
Zhongxing Xu6987c7b2008-11-30 05:49:49 +0000617
618 case Stmt::StringLiteralClass:
619 VisitLValue(cast<StringLiteral>(S), Pred, Dst);
620 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000621
Ted Kremenek72374592009-03-18 23:49:26 +0000622 case Stmt::UnaryOperatorClass: {
623 UnaryOperator *U = cast<UnaryOperator>(S);
Zhongxing Xu5032ffe2009-08-25 06:51:30 +0000624 if (AMgr.shouldEagerlyAssume() && (U->getOpcode() == UnaryOperator::LNot)) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000625 ExplodedNodeSet Tmp;
Ted Kremenek72374592009-03-18 23:49:26 +0000626 VisitUnaryOperator(U, Pred, Tmp, false);
627 EvalEagerlyAssume(Dst, Tmp, U);
628 }
629 else
630 VisitUnaryOperator(U, Pred, Dst, false);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000631 break;
Ted Kremenek72374592009-03-18 23:49:26 +0000632 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000633 }
634}
635
Mike Stump1eb44332009-09-09 15:08:12 +0000636void GRExprEngine::VisitLValue(Expr* Ex, ExplodedNode* Pred,
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000637 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +0000638
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000639 Ex = Ex->IgnoreParens();
Mike Stump1eb44332009-09-09 15:08:12 +0000640
Zhongxing Xucc025532009-08-25 03:33:41 +0000641 if (Ex != CurrentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(Ex)) {
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000642 Dst.Add(Pred);
643 return;
644 }
Mike Stump1eb44332009-09-09 15:08:12 +0000645
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000646 switch (Ex->getStmtClass()) {
Mike Stump1eb44332009-09-09 15:08:12 +0000647
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000648 case Stmt::ArraySubscriptExprClass:
649 VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(Ex), Pred, Dst, true);
650 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000651
Ted Kremenek67d12872009-12-07 22:05:27 +0000652 case Stmt::BlockDeclRefExprClass:
653 VisitBlockDeclRefExpr(cast<BlockDeclRefExpr>(Ex), Pred, Dst, true);
654 return;
655
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000656 case Stmt::DeclRefExprClass:
657 VisitDeclRefExpr(cast<DeclRefExpr>(Ex), Pred, Dst, true);
658 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000659
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000660 case Stmt::ObjCIvarRefExprClass:
661 VisitObjCIvarRefExpr(cast<ObjCIvarRefExpr>(Ex), Pred, Dst, true);
662 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000663
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000664 case Stmt::UnaryOperatorClass:
665 VisitUnaryOperator(cast<UnaryOperator>(Ex), Pred, Dst, true);
666 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000667
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +0000668 case Stmt::MemberExprClass:
669 VisitMemberExpr(cast<MemberExpr>(Ex), Pred, Dst, true);
670 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000671
Ted Kremenek4f090272008-10-27 21:54:31 +0000672 case Stmt::CompoundLiteralExprClass:
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000673 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(Ex), Pred, Dst, true);
Ted Kremenek4f090272008-10-27 21:54:31 +0000674 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000675
Ted Kremenekb6b81d12008-10-17 17:24:14 +0000676 case Stmt::ObjCPropertyRefExprClass:
Fariborz Jahanian09105f52009-08-20 17:02:02 +0000677 case Stmt::ObjCImplicitSetterGetterRefExprClass:
Ted Kremenekb6b81d12008-10-17 17:24:14 +0000678 // FIXME: Property assignments are lvalues, but not really "locations".
679 // e.g.: self.x = something;
680 // Here the "self.x" really can translate to a method call (setter) when
681 // the assignment is made. Moreover, the entire assignment expression
682 // evaluate to whatever "something" is, not calling the "getter" for
683 // the property (which would make sense since it can have side effects).
684 // We'll probably treat this as a location, but not one that we can
685 // take the address of. Perhaps we need a new SVal class for cases
686 // like thsis?
687 // Note that we have a similar problem for bitfields, since they don't
688 // have "locations" in the sense that we can take their address.
689 Dst.Add(Pred);
Ted Kremenekc7df6d22008-10-18 04:08:49 +0000690 return;
Zhongxing Xu143bf822008-10-25 14:18:57 +0000691
692 case Stmt::StringLiteralClass: {
Ted Kremeneka8538d92009-02-13 01:45:31 +0000693 const GRState* state = GetState(Pred);
Ted Kremenek3ff12592009-06-19 17:10:32 +0000694 SVal V = state->getLValue(cast<StringLiteral>(Ex));
Ted Kremenek8e029342009-08-27 22:17:37 +0000695 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V));
Zhongxing Xu143bf822008-10-25 14:18:57 +0000696 return;
697 }
Mike Stump1eb44332009-09-09 15:08:12 +0000698
Zhongxing Xu662174ca2009-10-30 07:19:39 +0000699 case Stmt::BinaryOperatorClass:
700 case Stmt::CompoundAssignOperatorClass:
701 VisitBinaryOperator(cast<BinaryOperator>(Ex), Pred, Dst, true);
702 return;
703
Ted Kremenekf8cd1b22008-10-18 04:15:35 +0000704 default:
705 // Arbitrary subexpressions can return aggregate temporaries that
706 // can be used in a lvalue context. We need to enhance our support
707 // of such temporaries in both the environment and the store, so right
708 // now we just do a regular visit.
Douglas Gregord7eb8462009-01-30 17:31:00 +0000709 assert ((Ex->getType()->isAggregateType()) &&
Ted Kremenek5b2316a2008-10-25 20:09:21 +0000710 "Other kinds of expressions with non-aggregate/union types do"
711 " not have lvalues.");
Mike Stump1eb44332009-09-09 15:08:12 +0000712
Ted Kremenekf8cd1b22008-10-18 04:15:35 +0000713 Visit(Ex, Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000714 }
715}
716
717//===----------------------------------------------------------------------===//
718// Block entrance. (Update counters).
719//===----------------------------------------------------------------------===//
720
Ted Kremenek4adc81e2008-08-13 04:27:00 +0000721bool GRExprEngine::ProcessBlockEntrance(CFGBlock* B, const GRState*,
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000722 GRBlockCounter BC) {
Mike Stump1eb44332009-09-09 15:08:12 +0000723
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000724 return BC.getNumVisited(B->getBlockID()) < 3;
725}
726
727//===----------------------------------------------------------------------===//
Ted Kremenek1670e402009-04-11 00:11:10 +0000728// Generic node creation.
729//===----------------------------------------------------------------------===//
730
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000731ExplodedNode* GRExprEngine::MakeNode(ExplodedNodeSet& Dst, Stmt* S,
732 ExplodedNode* Pred, const GRState* St,
733 ProgramPoint::Kind K, const void *tag) {
Ted Kremenek1670e402009-04-11 00:11:10 +0000734 assert (Builder && "GRStmtNodeBuilder not present.");
735 SaveAndRestore<const void*> OldTag(Builder->Tag);
736 Builder->Tag = tag;
737 return Builder->MakeNode(Dst, S, Pred, St, K);
738}
739
740//===----------------------------------------------------------------------===//
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000741// Branch processing.
742//===----------------------------------------------------------------------===//
743
Ted Kremeneka8538d92009-02-13 01:45:31 +0000744const GRState* GRExprEngine::MarkBranch(const GRState* state,
Ted Kremenek4323a572008-07-10 22:03:41 +0000745 Stmt* Terminator,
746 bool branchTaken) {
Mike Stump1eb44332009-09-09 15:08:12 +0000747
Ted Kremenek05a23782008-02-26 19:05:15 +0000748 switch (Terminator->getStmtClass()) {
749 default:
Ted Kremeneka8538d92009-02-13 01:45:31 +0000750 return state;
Mike Stump1eb44332009-09-09 15:08:12 +0000751
Ted Kremenek05a23782008-02-26 19:05:15 +0000752 case Stmt::BinaryOperatorClass: { // '&&' and '||'
Mike Stump1eb44332009-09-09 15:08:12 +0000753
Ted Kremenek05a23782008-02-26 19:05:15 +0000754 BinaryOperator* B = cast<BinaryOperator>(Terminator);
755 BinaryOperator::Opcode Op = B->getOpcode();
Mike Stump1eb44332009-09-09 15:08:12 +0000756
Ted Kremenek05a23782008-02-26 19:05:15 +0000757 assert (Op == BinaryOperator::LAnd || Op == BinaryOperator::LOr);
Mike Stump1eb44332009-09-09 15:08:12 +0000758
Ted Kremenek05a23782008-02-26 19:05:15 +0000759 // For &&, if we take the true branch, then the value of the whole
760 // expression is that of the RHS expression.
761 //
762 // For ||, if we take the false branch, then the value of the whole
763 // expression is that of the RHS expression.
Mike Stump1eb44332009-09-09 15:08:12 +0000764
Ted Kremenek05a23782008-02-26 19:05:15 +0000765 Expr* Ex = (Op == BinaryOperator::LAnd && branchTaken) ||
Mike Stump1eb44332009-09-09 15:08:12 +0000766 (Op == BinaryOperator::LOr && !branchTaken)
Ted Kremenek05a23782008-02-26 19:05:15 +0000767 ? B->getRHS() : B->getLHS();
Mike Stump1eb44332009-09-09 15:08:12 +0000768
Ted Kremenek8e029342009-08-27 22:17:37 +0000769 return state->BindExpr(B, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +0000770 }
Mike Stump1eb44332009-09-09 15:08:12 +0000771
Ted Kremenek05a23782008-02-26 19:05:15 +0000772 case Stmt::ConditionalOperatorClass: { // ?:
Mike Stump1eb44332009-09-09 15:08:12 +0000773
Ted Kremenek05a23782008-02-26 19:05:15 +0000774 ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
Mike Stump1eb44332009-09-09 15:08:12 +0000775
Ted Kremenek05a23782008-02-26 19:05:15 +0000776 // For ?, if branchTaken == true then the value is either the LHS or
777 // the condition itself. (GNU extension).
Mike Stump1eb44332009-09-09 15:08:12 +0000778
779 Expr* Ex;
780
Ted Kremenek05a23782008-02-26 19:05:15 +0000781 if (branchTaken)
Mike Stump1eb44332009-09-09 15:08:12 +0000782 Ex = C->getLHS() ? C->getLHS() : C->getCond();
Ted Kremenek05a23782008-02-26 19:05:15 +0000783 else
784 Ex = C->getRHS();
Mike Stump1eb44332009-09-09 15:08:12 +0000785
Ted Kremenek8e029342009-08-27 22:17:37 +0000786 return state->BindExpr(C, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +0000787 }
Mike Stump1eb44332009-09-09 15:08:12 +0000788
Ted Kremenek05a23782008-02-26 19:05:15 +0000789 case Stmt::ChooseExprClass: { // ?:
Mike Stump1eb44332009-09-09 15:08:12 +0000790
Ted Kremenek05a23782008-02-26 19:05:15 +0000791 ChooseExpr* C = cast<ChooseExpr>(Terminator);
Mike Stump1eb44332009-09-09 15:08:12 +0000792
793 Expr* Ex = branchTaken ? C->getLHS() : C->getRHS();
Ted Kremenek8e029342009-08-27 22:17:37 +0000794 return state->BindExpr(C, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +0000795 }
796 }
797}
798
Ted Kremenek6ae8a362009-03-13 16:32:54 +0000799/// RecoverCastedSymbol - A helper function for ProcessBranch that is used
800/// to try to recover some path-sensitivity for casts of symbolic
801/// integers that promote their values (which are currently not tracked well).
802/// This function returns the SVal bound to Condition->IgnoreCasts if all the
803// cast(s) did was sign-extend the original value.
804static SVal RecoverCastedSymbol(GRStateManager& StateMgr, const GRState* state,
805 Stmt* Condition, ASTContext& Ctx) {
806
807 Expr *Ex = dyn_cast<Expr>(Condition);
808 if (!Ex)
809 return UnknownVal();
810
811 uint64_t bits = 0;
812 bool bitsInit = false;
Mike Stump1eb44332009-09-09 15:08:12 +0000813
Ted Kremenek6ae8a362009-03-13 16:32:54 +0000814 while (CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
815 QualType T = CE->getType();
816
817 if (!T->isIntegerType())
818 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000819
Ted Kremenek6ae8a362009-03-13 16:32:54 +0000820 uint64_t newBits = Ctx.getTypeSize(T);
821 if (!bitsInit || newBits < bits) {
822 bitsInit = true;
823 bits = newBits;
824 }
Mike Stump1eb44332009-09-09 15:08:12 +0000825
Ted Kremenek6ae8a362009-03-13 16:32:54 +0000826 Ex = CE->getSubExpr();
827 }
828
829 // We reached a non-cast. Is it a symbolic value?
830 QualType T = Ex->getType();
831
832 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits)
833 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000834
Ted Kremenek23ec48c2009-06-18 23:58:37 +0000835 return state->getSVal(Ex);
Ted Kremenek6ae8a362009-03-13 16:32:54 +0000836}
837
Ted Kremenekaf337412008-11-12 19:24:17 +0000838void GRExprEngine::ProcessBranch(Stmt* Condition, Stmt* Term,
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000839 GRBranchNodeBuilder& builder) {
Mike Stump1eb44332009-09-09 15:08:12 +0000840
Ted Kremenekb2331832008-02-15 22:29:00 +0000841 // Check for NULL conditions; e.g. "for(;;)"
Mike Stump1eb44332009-09-09 15:08:12 +0000842 if (!Condition) {
Ted Kremenekb2331832008-02-15 22:29:00 +0000843 builder.markInfeasible(false);
Ted Kremenekb2331832008-02-15 22:29:00 +0000844 return;
845 }
Mike Stump1eb44332009-09-09 15:08:12 +0000846
Ted Kremenek21028dd2009-03-11 03:54:24 +0000847 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
848 Condition->getLocStart(),
849 "Error evaluating branch");
Ted Kremenek0fb0bc42009-08-27 01:39:13 +0000850
Zhongxing Xu0835e4c2009-11-23 03:20:54 +0000851 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
852 void *tag = I->first;
853 Checker *checker = I->second;
854 checker->VisitBranchCondition(builder, *this, Condition, tag);
855 }
856
857 // If the branch condition is undefined, return;
858 if (!builder.isFeasible(true) && !builder.isFeasible(false))
859 return;
860
Mike Stump1eb44332009-09-09 15:08:12 +0000861 const GRState* PrevState = builder.getState();
Ted Kremenek5b9bd212009-09-11 22:07:28 +0000862 SVal X = PrevState->getSVal(Condition);
Mike Stump1eb44332009-09-09 15:08:12 +0000863
Zhongxing Xu0835e4c2009-11-23 03:20:54 +0000864 if (X.isUnknown()) {
865 // Give it a chance to recover from unknown.
866 if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
867 if (Ex->getType()->isIntegerType()) {
868 // Try to recover some path-sensitivity. Right now casts of symbolic
869 // integers that promote their values are currently not tracked well.
870 // If 'Condition' is such an expression, try and recover the
871 // underlying value and use that instead.
872 SVal recovered = RecoverCastedSymbol(getStateManager(),
873 builder.getState(), Condition,
874 getContext());
875
876 if (!recovered.isUnknown()) {
877 X = recovered;
878 }
Ted Kremenek6ae8a362009-03-13 16:32:54 +0000879 }
Zhongxing Xu0835e4c2009-11-23 03:20:54 +0000880 }
881 // If the condition is still unknown, give up.
882 if (X.isUnknown()) {
883 builder.generateNode(MarkBranch(PrevState, Term, true), true);
884 builder.generateNode(MarkBranch(PrevState, Term, false), false);
Ted Kremenekb38911f2008-01-30 23:03:39 +0000885 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000886 }
Ted Kremenekb38911f2008-01-30 23:03:39 +0000887 }
Mike Stump1eb44332009-09-09 15:08:12 +0000888
Zhongxing Xu0835e4c2009-11-23 03:20:54 +0000889 DefinedSVal V = cast<DefinedSVal>(X);
890
Ted Kremenek6a6719a2008-02-29 20:27:50 +0000891 // Process the true branch.
Ted Kremenek52003542009-07-20 18:44:36 +0000892 if (builder.isFeasible(true)) {
Zhongxing Xu0835e4c2009-11-23 03:20:54 +0000893 if (const GRState *state = PrevState->Assume(V, true))
Ted Kremenek52003542009-07-20 18:44:36 +0000894 builder.generateNode(MarkBranch(state, Term, true), true);
895 else
896 builder.markInfeasible(true);
897 }
Mike Stump1eb44332009-09-09 15:08:12 +0000898
899 // Process the false branch.
Ted Kremenek52003542009-07-20 18:44:36 +0000900 if (builder.isFeasible(false)) {
Zhongxing Xu0835e4c2009-11-23 03:20:54 +0000901 if (const GRState *state = PrevState->Assume(V, false))
Ted Kremenek52003542009-07-20 18:44:36 +0000902 builder.generateNode(MarkBranch(state, Term, false), false);
903 else
904 builder.markInfeasible(false);
905 }
Ted Kremenek71c29bd2008-01-29 23:32:35 +0000906}
907
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000908/// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor
Ted Kremenek754607e2008-02-13 00:24:44 +0000909/// nodes by processing the 'effects' of a computed goto jump.
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000910void GRExprEngine::ProcessIndirectGoto(GRIndirectGotoNodeBuilder& builder) {
Ted Kremenek754607e2008-02-13 00:24:44 +0000911
Mike Stump1eb44332009-09-09 15:08:12 +0000912 const GRState *state = builder.getState();
Ted Kremenek3ff12592009-06-19 17:10:32 +0000913 SVal V = state->getSVal(builder.getTarget());
Mike Stump1eb44332009-09-09 15:08:12 +0000914
Ted Kremenek754607e2008-02-13 00:24:44 +0000915 // Three possibilities:
916 //
917 // (1) We know the computed label.
Ted Kremenek4a4e5242008-02-28 09:25:22 +0000918 // (2) The label is NULL (or some other constant), or Undefined.
Ted Kremenek754607e2008-02-13 00:24:44 +0000919 // (3) We have no clue about the label. Dispatch to all targets.
920 //
Mike Stump1eb44332009-09-09 15:08:12 +0000921
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000922 typedef GRIndirectGotoNodeBuilder::iterator iterator;
Ted Kremenek754607e2008-02-13 00:24:44 +0000923
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000924 if (isa<loc::GotoLabel>(V)) {
925 LabelStmt* L = cast<loc::GotoLabel>(V).getLabel();
Mike Stump1eb44332009-09-09 15:08:12 +0000926
Ted Kremenek754607e2008-02-13 00:24:44 +0000927 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) {
Ted Kremenek24f1a962008-02-13 17:27:37 +0000928 if (I.getLabel() == L) {
Ted Kremeneka8538d92009-02-13 01:45:31 +0000929 builder.generateNode(I, state);
Ted Kremenek754607e2008-02-13 00:24:44 +0000930 return;
931 }
932 }
Mike Stump1eb44332009-09-09 15:08:12 +0000933
Ted Kremenek754607e2008-02-13 00:24:44 +0000934 assert (false && "No block with label.");
935 return;
936 }
937
Zhongxing Xu1c96b242008-10-17 05:57:07 +0000938 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
Ted Kremenek754607e2008-02-13 00:24:44 +0000939 // Dispatch to the first target and mark it as a sink.
Zhongxing Xu2055eff2009-11-24 07:06:39 +0000940 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
941 // FIXME: add checker visit.
942 // UndefBranches.insert(N);
Ted Kremenek754607e2008-02-13 00:24:44 +0000943 return;
944 }
Mike Stump1eb44332009-09-09 15:08:12 +0000945
Ted Kremenek754607e2008-02-13 00:24:44 +0000946 // This is really a catch-all. We don't support symbolics yet.
Ted Kremenekb3cfd582009-04-23 17:49:43 +0000947 // FIXME: Implement dispatch for symbolic pointers.
Mike Stump1eb44332009-09-09 15:08:12 +0000948
Ted Kremenek754607e2008-02-13 00:24:44 +0000949 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
Ted Kremeneka8538d92009-02-13 01:45:31 +0000950 builder.generateNode(I, state);
Ted Kremenek754607e2008-02-13 00:24:44 +0000951}
Ted Kremenekf233d482008-02-05 00:26:40 +0000952
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000953
954void GRExprEngine::VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R,
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000955 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +0000956
Zhongxing Xucc025532009-08-25 03:33:41 +0000957 assert (Ex == CurrentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(Ex));
Mike Stump1eb44332009-09-09 15:08:12 +0000958
Ted Kremeneka8538d92009-02-13 01:45:31 +0000959 const GRState* state = GetState(Pred);
Ted Kremenek0fb0bc42009-08-27 01:39:13 +0000960 SVal X = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +0000961
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000962 assert (X.isUndef());
Mike Stump1eb44332009-09-09 15:08:12 +0000963
Ted Kremenek3ff12592009-06-19 17:10:32 +0000964 Expr *SE = (Expr*) cast<UndefinedVal>(X).getData();
Mike Stump1eb44332009-09-09 15:08:12 +0000965 assert(SE);
Ted Kremenek0fb0bc42009-08-27 01:39:13 +0000966 X = state->getSVal(SE);
Mike Stump1eb44332009-09-09 15:08:12 +0000967
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000968 // Make sure that we invalidate the previous binding.
Ted Kremenek8e029342009-08-27 22:17:37 +0000969 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, X, true));
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000970}
971
Ted Kremenek73099bf2009-11-14 01:05:20 +0000972/// ProcessEndPath - Called by GRCoreEngine. Used to generate end-of-path
973/// nodes when the control reaches the end of a function.
974void GRExprEngine::ProcessEndPath(GREndPathNodeBuilder& builder) {
975 getTF().EvalEndPath(*this, builder);
976 StateMgr.EndPath(builder.getState());
Zhongxing Xu243fde92009-11-17 07:54:15 +0000977 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E;++I){
978 void *tag = I->first;
979 Checker *checker = I->second;
980 checker->EvalEndPath(builder, tag, *this);
981 }
Ted Kremenek73099bf2009-11-14 01:05:20 +0000982}
983
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000984/// ProcessSwitch - Called by GRCoreEngine. Used to generate successor
985/// nodes by processing the 'effects' of a switch statement.
Mike Stump1eb44332009-09-09 15:08:12 +0000986void GRExprEngine::ProcessSwitch(GRSwitchNodeBuilder& builder) {
987 typedef GRSwitchNodeBuilder::iterator iterator;
988 const GRState* state = builder.getState();
Ted Kremenek692416c2008-02-18 22:57:02 +0000989 Expr* CondE = builder.getCondition();
Ted Kremenek5b9bd212009-09-11 22:07:28 +0000990 SVal CondV_untested = state->getSVal(CondE);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000991
Ted Kremenek5b9bd212009-09-11 22:07:28 +0000992 if (CondV_untested.isUndef()) {
Zhongxing Xu2055eff2009-11-24 07:06:39 +0000993 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
994 // FIXME: add checker
995 //UndefBranches.insert(N);
996
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000997 return;
998 }
Ted Kremenek5b9bd212009-09-11 22:07:28 +0000999 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested);
Ted Kremenek692416c2008-02-18 22:57:02 +00001000
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001001 const GRState *DefaultSt = state;
Ted Kremeneka591bc02009-06-18 22:57:13 +00001002 bool defaultIsFeasible = false;
Mike Stump1eb44332009-09-09 15:08:12 +00001003
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001004 for (iterator I = builder.begin(), EI = builder.end(); I != EI; ++I) {
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001005 CaseStmt* Case = cast<CaseStmt>(I.getCase());
Ted Kremenek72afb372009-01-17 01:54:16 +00001006
1007 // Evaluate the LHS of the case value.
1008 Expr::EvalResult V1;
Mike Stump1eb44332009-09-09 15:08:12 +00001009 bool b = Case->getLHS()->Evaluate(V1, getContext());
1010
Ted Kremenek72afb372009-01-17 01:54:16 +00001011 // Sanity checks. These go away in Release builds.
Mike Stump1eb44332009-09-09 15:08:12 +00001012 assert(b && V1.Val.isInt() && !V1.HasSideEffects
Ted Kremenek72afb372009-01-17 01:54:16 +00001013 && "Case condition must evaluate to an integer constant.");
Mike Stump1eb44332009-09-09 15:08:12 +00001014 b = b; // silence unused variable warning
1015 assert(V1.Val.getInt().getBitWidth() ==
Ted Kremenek72afb372009-01-17 01:54:16 +00001016 getContext().getTypeSize(CondE->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00001017
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001018 // Get the RHS of the case, if it exists.
Ted Kremenek72afb372009-01-17 01:54:16 +00001019 Expr::EvalResult V2;
Mike Stump1eb44332009-09-09 15:08:12 +00001020
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001021 if (Expr* E = Case->getRHS()) {
Ted Kremenek72afb372009-01-17 01:54:16 +00001022 b = E->Evaluate(V2, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +00001023 assert(b && V2.Val.isInt() && !V2.HasSideEffects
Ted Kremenek72afb372009-01-17 01:54:16 +00001024 && "Case condition must evaluate to an integer constant.");
1025 b = b; // silence unused variable warning
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001026 }
Ted Kremenek14a11402008-03-17 22:17:56 +00001027 else
1028 V2 = V1;
Mike Stump1eb44332009-09-09 15:08:12 +00001029
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001030 // FIXME: Eventually we should replace the logic below with a range
1031 // comparison, rather than concretize the values within the range.
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001032 // This should be easy once we have "ranges" for NonLVals.
Mike Stump1eb44332009-09-09 15:08:12 +00001033
Ted Kremenek14a11402008-03-17 22:17:56 +00001034 do {
Mike Stump1eb44332009-09-09 15:08:12 +00001035 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1.Val.getInt()));
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001036 DefinedOrUnknownSVal Res = SVator.EvalEQ(DefaultSt, CondV, CaseVal);
1037
Mike Stump1eb44332009-09-09 15:08:12 +00001038 // Now "assume" that the case matches.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001039 if (const GRState* stateNew = state->Assume(Res, true)) {
Ted Kremeneka591bc02009-06-18 22:57:13 +00001040 builder.generateCaseStmtNode(I, stateNew);
Mike Stump1eb44332009-09-09 15:08:12 +00001041
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001042 // If CondV evaluates to a constant, then we know that this
1043 // is the *only* case that we can take, so stop evaluating the
1044 // others.
Zhongxing Xu1c96b242008-10-17 05:57:07 +00001045 if (isa<nonloc::ConcreteInt>(CondV))
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001046 return;
1047 }
Mike Stump1eb44332009-09-09 15:08:12 +00001048
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001049 // Now "assume" that the case doesn't match. Add this state
1050 // to the default state (if it is feasible).
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001051 if (const GRState *stateNew = DefaultSt->Assume(Res, false)) {
Ted Kremeneka591bc02009-06-18 22:57:13 +00001052 defaultIsFeasible = true;
1053 DefaultSt = stateNew;
Ted Kremenek5014ab12008-04-23 05:03:18 +00001054 }
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001055
Ted Kremenek14a11402008-03-17 22:17:56 +00001056 // Concretize the next value in the range.
Ted Kremenek72afb372009-01-17 01:54:16 +00001057 if (V1.Val.getInt() == V2.Val.getInt())
Ted Kremenek14a11402008-03-17 22:17:56 +00001058 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001059
Ted Kremenek72afb372009-01-17 01:54:16 +00001060 ++V1.Val.getInt();
1061 assert (V1.Val.getInt() <= V2.Val.getInt());
Mike Stump1eb44332009-09-09 15:08:12 +00001062
Ted Kremenek14a11402008-03-17 22:17:56 +00001063 } while (true);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001064 }
Mike Stump1eb44332009-09-09 15:08:12 +00001065
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001066 // If we reach here, than we know that the default branch is
Mike Stump1eb44332009-09-09 15:08:12 +00001067 // possible.
Ted Kremeneka591bc02009-06-18 22:57:13 +00001068 if (defaultIsFeasible) builder.generateDefaultCaseNode(DefaultSt);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001069}
1070
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001071//===----------------------------------------------------------------------===//
1072// Transfer functions: logical operations ('&&', '||').
1073//===----------------------------------------------------------------------===//
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001074
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001075void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, ExplodedNode* Pred,
1076 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001077
Ted Kremenek3ff12592009-06-19 17:10:32 +00001078 assert(B->getOpcode() == BinaryOperator::LAnd ||
1079 B->getOpcode() == BinaryOperator::LOr);
Mike Stump1eb44332009-09-09 15:08:12 +00001080
Zhongxing Xucc025532009-08-25 03:33:41 +00001081 assert(B == CurrentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(B));
Mike Stump1eb44332009-09-09 15:08:12 +00001082
Ted Kremeneka8538d92009-02-13 01:45:31 +00001083 const GRState* state = GetState(Pred);
Ted Kremenek0fb0bc42009-08-27 01:39:13 +00001084 SVal X = state->getSVal(B);
Ted Kremenek3ff12592009-06-19 17:10:32 +00001085 assert(X.isUndef());
Mike Stump1eb44332009-09-09 15:08:12 +00001086
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001087 const Expr *Ex = (const Expr*) cast<UndefinedVal>(X).getData();
Ted Kremenek3ff12592009-06-19 17:10:32 +00001088 assert(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00001089
Ted Kremenek05a23782008-02-26 19:05:15 +00001090 if (Ex == B->getRHS()) {
Ted Kremenek0fb0bc42009-08-27 01:39:13 +00001091 X = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00001092
Ted Kremenek4a4e5242008-02-28 09:25:22 +00001093 // Handle undefined values.
Ted Kremenek4a4e5242008-02-28 09:25:22 +00001094 if (X.isUndef()) {
Ted Kremenek8e029342009-08-27 22:17:37 +00001095 MakeNode(Dst, B, Pred, state->BindExpr(B, X));
Ted Kremenek58b33212008-02-26 19:40:44 +00001096 return;
1097 }
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001098
1099 DefinedOrUnknownSVal XD = cast<DefinedOrUnknownSVal>(X);
Mike Stump1eb44332009-09-09 15:08:12 +00001100
Ted Kremenek05a23782008-02-26 19:05:15 +00001101 // We took the RHS. Because the value of the '&&' or '||' expression must
1102 // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
1103 // or 1. Alternatively, we could take a lazy approach, and calculate this
1104 // value later when necessary. We don't have the machinery in place for
1105 // this right now, and since most logical expressions are used for branches,
Mike Stump1eb44332009-09-09 15:08:12 +00001106 // the payoff is not likely to be large. Instead, we do eager evaluation.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001107 if (const GRState *newState = state->Assume(XD, true))
Mike Stump1eb44332009-09-09 15:08:12 +00001108 MakeNode(Dst, B, Pred,
Ted Kremenek8e029342009-08-27 22:17:37 +00001109 newState->BindExpr(B, ValMgr.makeIntVal(1U, B->getType())));
Mike Stump1eb44332009-09-09 15:08:12 +00001110
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001111 if (const GRState *newState = state->Assume(XD, false))
Mike Stump1eb44332009-09-09 15:08:12 +00001112 MakeNode(Dst, B, Pred,
Ted Kremenek8e029342009-08-27 22:17:37 +00001113 newState->BindExpr(B, ValMgr.makeIntVal(0U, B->getType())));
Ted Kremenekf233d482008-02-05 00:26:40 +00001114 }
1115 else {
Ted Kremenek05a23782008-02-26 19:05:15 +00001116 // We took the LHS expression. Depending on whether we are '&&' or
1117 // '||' we know what the value of the expression is via properties of
1118 // the short-circuiting.
Mike Stump1eb44332009-09-09 15:08:12 +00001119 X = ValMgr.makeIntVal(B->getOpcode() == BinaryOperator::LAnd ? 0U : 1U,
Zhongxing Xud91ee272009-06-23 09:02:15 +00001120 B->getType());
Ted Kremenek8e029342009-08-27 22:17:37 +00001121 MakeNode(Dst, B, Pred, state->BindExpr(B, X));
Ted Kremenekf233d482008-02-05 00:26:40 +00001122 }
Ted Kremenekf233d482008-02-05 00:26:40 +00001123}
Mike Stump1eb44332009-09-09 15:08:12 +00001124
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001125//===----------------------------------------------------------------------===//
Ted Kremenekec96a2d2008-04-16 18:39:06 +00001126// Transfer functions: Loads and stores.
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001127//===----------------------------------------------------------------------===//
Ted Kremenekd27f8162008-01-15 23:55:06 +00001128
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001129void GRExprEngine::VisitBlockExpr(BlockExpr *BE, ExplodedNode *Pred,
1130 ExplodedNodeSet &Dst) {
Ted Kremenek66078612009-11-25 22:23:25 +00001131
1132 ExplodedNodeSet Tmp;
1133
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001134 CanQualType T = getContext().getCanonicalType(BE->getType());
Ted Kremenek0a8112a2009-11-25 23:53:07 +00001135 SVal V = ValMgr.getBlockPointer(BE->getBlockDecl(), T,
1136 Pred->getLocationContext());
1137
Ted Kremenek66078612009-11-25 22:23:25 +00001138 MakeNode(Tmp, BE, Pred, GetState(Pred)->BindExpr(BE, V),
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001139 ProgramPoint::PostLValueKind);
Ted Kremenek66078612009-11-25 22:23:25 +00001140
1141 // Post-visit the BlockExpr.
1142 CheckerVisit(BE, Dst, Tmp, false);
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001143}
1144
Mike Stump1eb44332009-09-09 15:08:12 +00001145void GRExprEngine::VisitDeclRefExpr(DeclRefExpr *Ex, ExplodedNode *Pred,
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001146 ExplodedNodeSet &Dst, bool asLValue) {
Ted Kremenek67d12872009-12-07 22:05:27 +00001147 VisitCommonDeclRefExpr(Ex, Ex->getDecl(), Pred, Dst, asLValue);
1148}
1149
1150void GRExprEngine::VisitBlockDeclRefExpr(BlockDeclRefExpr *Ex,
1151 ExplodedNode *Pred,
1152 ExplodedNodeSet &Dst, bool asLValue) {
1153 VisitCommonDeclRefExpr(Ex, Ex->getDecl(), Pred, Dst, asLValue);
1154}
1155
1156void GRExprEngine::VisitCommonDeclRefExpr(Expr *Ex, const NamedDecl *D,
1157 ExplodedNode *Pred,
1158 ExplodedNodeSet &Dst, bool asLValue) {
Mike Stump1eb44332009-09-09 15:08:12 +00001159
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001160 const GRState *state = GetState(Pred);
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001161
1162 if (const VarDecl* VD = dyn_cast<VarDecl>(D)) {
1163
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001164 SVal V = state->getLValue(VD, Pred->getLocationContext());
Zhongxing Xua7581732008-10-17 02:20:14 +00001165
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001166 if (asLValue)
Ted Kremenek8e029342009-08-27 22:17:37 +00001167 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V),
Ted Kremenek7090d542009-05-07 18:27:16 +00001168 ProgramPoint::PostLValueKind);
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001169 else
Ted Kremeneka8538d92009-02-13 01:45:31 +00001170 EvalLoad(Dst, Ex, Pred, state, V);
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001171 return;
1172
1173 } else if (const EnumConstantDecl* ED = dyn_cast<EnumConstantDecl>(D)) {
1174 assert(!asLValue && "EnumConstantDecl does not have lvalue.");
1175
Zhongxing Xu3038c5a2009-06-23 06:13:19 +00001176 SVal V = ValMgr.makeIntVal(ED->getInitVal());
Ted Kremenek8e029342009-08-27 22:17:37 +00001177 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V));
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001178 return;
1179
1180 } else if (const FunctionDecl* FD = dyn_cast<FunctionDecl>(D)) {
Ted Kremenek657406d2009-09-23 01:30:01 +00001181 // This code is valid regardless of the value of 'isLValue'.
Zhongxing Xu369f4472009-04-20 05:24:46 +00001182 SVal V = ValMgr.getFunctionPointer(FD);
Ted Kremenek8e029342009-08-27 22:17:37 +00001183 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V),
Ted Kremenek7090d542009-05-07 18:27:16 +00001184 ProgramPoint::PostLValueKind);
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001185 return;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001186 }
Mike Stump1eb44332009-09-09 15:08:12 +00001187
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001188 assert (false &&
1189 "ValueDecl support for this ValueDecl not implemented.");
Ted Kremenek3271f8d2008-02-07 04:16:04 +00001190}
1191
Ted Kremenek540cbe22008-04-22 04:56:29 +00001192/// VisitArraySubscriptExpr - Transfer function for array accesses
Mike Stump1eb44332009-09-09 15:08:12 +00001193void GRExprEngine::VisitArraySubscriptExpr(ArraySubscriptExpr* A,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001194 ExplodedNode* Pred,
1195 ExplodedNodeSet& Dst, bool asLValue){
Mike Stump1eb44332009-09-09 15:08:12 +00001196
Ted Kremenek540cbe22008-04-22 04:56:29 +00001197 Expr* Base = A->getBase()->IgnoreParens();
Ted Kremenek4d0348b2008-04-29 23:24:44 +00001198 Expr* Idx = A->getIdx()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001199 ExplodedNodeSet Tmp;
Mike Stump1eb44332009-09-09 15:08:12 +00001200
Ted Kremenek265a3052009-02-24 02:23:11 +00001201 if (Base->getType()->isVectorType()) {
1202 // For vector types get its lvalue.
1203 // FIXME: This may not be correct. Is the rvalue of a vector its location?
1204 // In fact, I think this is just a hack. We need to get the right
1205 // semantics.
1206 VisitLValue(Base, Pred, Tmp);
1207 }
Mike Stump1eb44332009-09-09 15:08:12 +00001208 else
Ted Kremenek265a3052009-02-24 02:23:11 +00001209 Visit(Base, Pred, Tmp); // Get Base's rvalue, which should be an LocVal.
Mike Stump1eb44332009-09-09 15:08:12 +00001210
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001211 for (ExplodedNodeSet::iterator I1=Tmp.begin(), E1=Tmp.end(); I1!=E1; ++I1) {
1212 ExplodedNodeSet Tmp2;
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001213 Visit(Idx, *I1, Tmp2); // Evaluate the index.
Mike Stump1eb44332009-09-09 15:08:12 +00001214
Zhongxing Xud6944852009-11-11 13:42:54 +00001215 ExplodedNodeSet Tmp3;
1216 CheckerVisit(A, Tmp3, Tmp2, true);
1217
1218 for (ExplodedNodeSet::iterator I2=Tmp3.begin(),E2=Tmp3.end();I2!=E2; ++I2) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001219 const GRState* state = GetState(*I2);
Zhongxing Xud0f8bb12009-10-14 03:33:08 +00001220 SVal V = state->getLValue(A->getType(), state->getSVal(Idx),
1221 state->getSVal(Base));
Ted Kremenek4d0348b2008-04-29 23:24:44 +00001222
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001223 if (asLValue)
Ted Kremenek8e029342009-08-27 22:17:37 +00001224 MakeNode(Dst, A, *I2, state->BindExpr(A, V),
Ted Kremenek7090d542009-05-07 18:27:16 +00001225 ProgramPoint::PostLValueKind);
Ted Kremenek4d0348b2008-04-29 23:24:44 +00001226 else
Ted Kremeneka8538d92009-02-13 01:45:31 +00001227 EvalLoad(Dst, A, *I2, state, V);
Ted Kremenek4d0348b2008-04-29 23:24:44 +00001228 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001229 }
Ted Kremenek540cbe22008-04-22 04:56:29 +00001230}
1231
Ted Kremenek469ecbd2008-04-21 23:43:38 +00001232/// VisitMemberExpr - Transfer function for member expressions.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001233void GRExprEngine::VisitMemberExpr(MemberExpr* M, ExplodedNode* Pred,
1234 ExplodedNodeSet& Dst, bool asLValue) {
Mike Stump1eb44332009-09-09 15:08:12 +00001235
Ted Kremenek469ecbd2008-04-21 23:43:38 +00001236 Expr* Base = M->getBase()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001237 ExplodedNodeSet Tmp;
Mike Stump1eb44332009-09-09 15:08:12 +00001238
1239 if (M->isArrow())
Ted Kremenek5c456fe2008-10-18 03:28:48 +00001240 Visit(Base, Pred, Tmp); // p->f = ... or ... = p->f
1241 else
1242 VisitLValue(Base, Pred, Tmp); // x.f = ... or ... = x.f
Mike Stump1eb44332009-09-09 15:08:12 +00001243
Douglas Gregor86f19402008-12-20 23:49:58 +00001244 FieldDecl *Field = dyn_cast<FieldDecl>(M->getMemberDecl());
1245 if (!Field) // FIXME: skipping member expressions for non-fields
1246 return;
1247
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001248 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001249 const GRState* state = GetState(*I);
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001250 // FIXME: Should we insert some assumption logic in here to determine
1251 // if "Base" is a valid piece of memory? Before we put this assumption
Douglas Gregor86f19402008-12-20 23:49:58 +00001252 // later when using FieldOffset lvals (which we no longer have).
Zhongxing Xu662174ca2009-10-30 07:19:39 +00001253 SVal L = state->getLValue(Field, state->getSVal(Base));
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001254
Zhongxing Xu662174ca2009-10-30 07:19:39 +00001255 if (asLValue)
1256 MakeNode(Dst, M, *I, state->BindExpr(M, L), ProgramPoint::PostLValueKind);
1257 else
1258 EvalLoad(Dst, M, *I, state, L);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001259 }
Ted Kremenek469ecbd2008-04-21 23:43:38 +00001260}
1261
Ted Kremeneka8538d92009-02-13 01:45:31 +00001262/// EvalBind - Handle the semantics of binding a value to a specific location.
1263/// This method is used by EvalStore and (soon) VisitDeclStmt, and others.
Ted Kremenek50ecd152009-11-05 00:42:23 +00001264void GRExprEngine::EvalBind(ExplodedNodeSet& Dst, Stmt *AssignE,
1265 Stmt* StoreE, ExplodedNode* Pred,
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001266 const GRState* state, SVal location, SVal Val,
1267 bool atDeclInit) {
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001268
1269
1270 // Do a previsit of the bind.
1271 ExplodedNodeSet CheckedSet, Src;
1272 Src.Add(Pred);
Ted Kremenek50ecd152009-11-05 00:42:23 +00001273 CheckerVisitBind(AssignE, StoreE, CheckedSet, Src, location, Val, true);
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001274
1275 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1276 I!=E; ++I) {
1277
1278 if (Pred != *I)
1279 state = GetState(*I);
1280
1281 const GRState* newState = 0;
Ted Kremeneka8538d92009-02-13 01:45:31 +00001282
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001283 if (atDeclInit) {
1284 const VarRegion *VR =
1285 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001286
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001287 newState = state->bindDecl(VR, Val);
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001288 }
1289 else {
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001290 if (location.isUnknown()) {
1291 // We know that the new state will be the same as the old state since
1292 // the location of the binding is "unknown". Consequently, there
1293 // is no reason to just create a new node.
1294 newState = state;
1295 }
1296 else {
1297 // We are binding to a value other than 'unknown'. Perform the binding
1298 // using the StoreManager.
1299 newState = state->bindLoc(cast<Loc>(location), Val);
1300 }
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001301 }
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001302
1303 // The next thing to do is check if the GRTransferFuncs object wants to
1304 // update the state based on the new binding. If the GRTransferFunc object
1305 // doesn't do anything, just auto-propagate the current state.
Ted Kremenek50ecd152009-11-05 00:42:23 +00001306 GRStmtNodeBuilderRef BuilderRef(Dst, *Builder, *this, *I, newState, StoreE,
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001307 newState != state);
1308
1309 getTF().EvalBind(BuilderRef, location, Val);
Ted Kremenek41573eb2009-02-14 01:43:44 +00001310 }
Ted Kremeneka8538d92009-02-13 01:45:31 +00001311}
1312
1313/// EvalStore - Handle the semantics of a store via an assignment.
1314/// @param Dst The node set to store generated state nodes
1315/// @param Ex The expression representing the location of the store
1316/// @param state The current simulation state
1317/// @param location The location to store the value
1318/// @param Val The value to be stored
Ted Kremenek50ecd152009-11-05 00:42:23 +00001319void GRExprEngine::EvalStore(ExplodedNodeSet& Dst, Expr *AssignE,
1320 Expr* StoreE,
1321 ExplodedNode* Pred,
Ted Kremenek1670e402009-04-11 00:11:10 +00001322 const GRState* state, SVal location, SVal Val,
1323 const void *tag) {
Mike Stump1eb44332009-09-09 15:08:12 +00001324
Ted Kremenek50ecd152009-11-05 00:42:23 +00001325 assert(Builder && "GRStmtNodeBuilder must be defined.");
Mike Stump1eb44332009-09-09 15:08:12 +00001326
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001327 // Evaluate the location (checks for bad dereferences).
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001328 ExplodedNodeSet Tmp;
1329 EvalLocation(Tmp, StoreE, Pred, state, location, tag, false);
Mike Stump1eb44332009-09-09 15:08:12 +00001330
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001331 if (Tmp.empty())
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001332 return;
Ted Kremenekb0533962008-04-18 20:35:30 +00001333
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001334 assert(!location.isUndef());
Ted Kremeneka8538d92009-02-13 01:45:31 +00001335
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001336 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind,
1337 ProgramPoint::PostStoreKind);
1338 SaveAndRestore<const void*> OldTag(Builder->Tag, tag);
1339
Mike Stump1eb44332009-09-09 15:08:12 +00001340 // Proceed with the store.
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001341 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
1342 EvalBind(Dst, AssignE, StoreE, *NI, GetState(*NI), location, Val);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001343}
1344
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001345void GRExprEngine::EvalLoad(ExplodedNodeSet& Dst, Expr *Ex, ExplodedNode* Pred,
Ted Kremenek1670e402009-04-11 00:11:10 +00001346 const GRState* state, SVal location,
Zhongxing Xu652be342009-11-16 04:49:44 +00001347 const void *tag, QualType LoadTy) {
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001348
Mike Stump1eb44332009-09-09 15:08:12 +00001349 // Evaluate the location (checks for bad dereferences).
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001350 ExplodedNodeSet Tmp;
1351 EvalLocation(Tmp, Ex, Pred, state, location, tag, true);
Mike Stump1eb44332009-09-09 15:08:12 +00001352
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001353 if (Tmp.empty())
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001354 return;
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001355
1356 assert(!location.isUndef());
1357
1358 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind);
1359 SaveAndRestore<const void*> OldTag(Builder->Tag);
Mike Stump1eb44332009-09-09 15:08:12 +00001360
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001361 // Proceed with the load.
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001362 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1363 state = GetState(*NI);
1364 if (location.isUnknown()) {
1365 // This is important. We must nuke the old binding.
1366 MakeNode(Dst, Ex, *NI, state->BindExpr(Ex, UnknownVal()),
1367 ProgramPoint::PostLoadKind, tag);
1368 }
1369 else {
Zhongxing Xu652be342009-11-16 04:49:44 +00001370 SVal V = state->getSVal(cast<Loc>(location), LoadTy.isNull() ?
1371 Ex->getType() : LoadTy);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001372 MakeNode(Dst, Ex, *NI, state->BindExpr(Ex, V), ProgramPoint::PostLoadKind,
1373 tag);
1374 }
Zhongxing Xud5b499d2008-11-28 08:34:30 +00001375 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001376}
1377
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001378void GRExprEngine::EvalLocation(ExplodedNodeSet &Dst, Stmt *S,
1379 ExplodedNode* Pred,
1380 const GRState* state, SVal location,
1381 const void *tag, bool isLoad) {
Zhongxing Xu00b1ad22009-11-20 03:50:46 +00001382 // Early checks for performance reason.
1383 if (location.isUnknown() || Checkers.empty()) {
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001384 Dst.Add(Pred);
1385 return;
Ted Kremenek0296c222009-11-02 23:19:29 +00001386 }
1387
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001388 ExplodedNodeSet Src, Tmp;
1389 Src.Add(Pred);
1390 ExplodedNodeSet *PrevSet = &Src;
1391
1392 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E; ++I)
1393 {
1394 ExplodedNodeSet *CurrSet = (I+1 == E) ? &Dst
1395 : (PrevSet == &Tmp) ? &Src : &Tmp;
1396
1397 CurrSet->clear();
1398 void *tag = I->first;
1399 Checker *checker = I->second;
1400
1401 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
Ted Kremenek19d67b52009-11-23 22:22:01 +00001402 NI != NE; ++NI) {
1403 // Use the 'state' argument only when the predecessor node is the
1404 // same as Pred. This allows us to catch updates to the state.
1405 checker->GR_VisitLocation(*CurrSet, *Builder, *this, S, *NI,
1406 *NI == Pred ? state : GetState(*NI),
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001407 location, tag, isLoad);
Ted Kremenek19d67b52009-11-23 22:22:01 +00001408 }
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001409
1410 // Update which NodeSet is the current one.
1411 PrevSet = CurrSet;
1412 }
Ted Kremenekec96a2d2008-04-16 18:39:06 +00001413}
1414
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001415//===----------------------------------------------------------------------===//
Ted Kremenek1670e402009-04-11 00:11:10 +00001416// Transfer function: OSAtomics.
1417//
1418// FIXME: Eventually refactor into a more "plugin" infrastructure.
1419//===----------------------------------------------------------------------===//
1420
1421// Mac OS X:
1422// http://developer.apple.com/documentation/Darwin/Reference/Manpages/man3
1423// atomic.3.html
1424//
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001425static bool EvalOSAtomicCompareAndSwap(ExplodedNodeSet& Dst,
Ted Kremenek1670e402009-04-11 00:11:10 +00001426 GRExprEngine& Engine,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001427 GRStmtNodeBuilder& Builder,
Zhongxing Xu1eacb722009-11-16 02:52:18 +00001428 CallExpr* CE, ExplodedNode* Pred) {
Ted Kremenek1670e402009-04-11 00:11:10 +00001429
1430 // Not enough arguments to match OSAtomicCompareAndSwap?
1431 if (CE->getNumArgs() != 3)
1432 return false;
Mike Stump1eb44332009-09-09 15:08:12 +00001433
Ted Kremenek1670e402009-04-11 00:11:10 +00001434 ASTContext &C = Engine.getContext();
1435 Expr *oldValueExpr = CE->getArg(0);
1436 QualType oldValueType = C.getCanonicalType(oldValueExpr->getType());
1437
1438 Expr *newValueExpr = CE->getArg(1);
1439 QualType newValueType = C.getCanonicalType(newValueExpr->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00001440
Ted Kremenek1670e402009-04-11 00:11:10 +00001441 // Do the types of 'oldValue' and 'newValue' match?
1442 if (oldValueType != newValueType)
1443 return false;
Mike Stump1eb44332009-09-09 15:08:12 +00001444
Ted Kremenek1670e402009-04-11 00:11:10 +00001445 Expr *theValueExpr = CE->getArg(2);
Ted Kremenek39abcdf2009-08-01 05:59:39 +00001446 const PointerType *theValueType =
1447 theValueExpr->getType()->getAs<PointerType>();
Mike Stump1eb44332009-09-09 15:08:12 +00001448
Ted Kremenek1670e402009-04-11 00:11:10 +00001449 // theValueType not a pointer?
1450 if (!theValueType)
1451 return false;
Mike Stump1eb44332009-09-09 15:08:12 +00001452
Ted Kremenek1670e402009-04-11 00:11:10 +00001453 QualType theValueTypePointee =
1454 C.getCanonicalType(theValueType->getPointeeType()).getUnqualifiedType();
Mike Stump1eb44332009-09-09 15:08:12 +00001455
Ted Kremenek1670e402009-04-11 00:11:10 +00001456 // The pointee must match newValueType and oldValueType.
1457 if (theValueTypePointee != newValueType)
1458 return false;
Mike Stump1eb44332009-09-09 15:08:12 +00001459
Ted Kremenek1670e402009-04-11 00:11:10 +00001460 static unsigned magic_load = 0;
1461 static unsigned magic_store = 0;
1462
1463 const void *OSAtomicLoadTag = &magic_load;
1464 const void *OSAtomicStoreTag = &magic_store;
Mike Stump1eb44332009-09-09 15:08:12 +00001465
Ted Kremenek1670e402009-04-11 00:11:10 +00001466 // Load 'theValue'.
Ted Kremenek1670e402009-04-11 00:11:10 +00001467 const GRState *state = Pred->getState();
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001468 ExplodedNodeSet Tmp;
Ted Kremenek23ec48c2009-06-18 23:58:37 +00001469 SVal location = state->getSVal(theValueExpr);
Zhongxing Xu652be342009-11-16 04:49:44 +00001470 // Here we should use the value type of the region as the load type.
1471 const MemRegion *R = location.getAsRegion();
1472 QualType LoadTy;
1473 if (R)
1474 LoadTy = cast<TypedRegion>(R)->getValueType(C);
1475 Engine.EvalLoad(Tmp, theValueExpr, Pred, state, location, OSAtomicLoadTag,
1476 LoadTy);
Ted Kremenek1670e402009-04-11 00:11:10 +00001477
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001478 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end();
Ted Kremenek1670e402009-04-11 00:11:10 +00001479 I != E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +00001480
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001481 ExplodedNode *N = *I;
Ted Kremenek1670e402009-04-11 00:11:10 +00001482 const GRState *stateLoad = N->getState();
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001483 SVal theValueVal_untested = stateLoad->getSVal(theValueExpr);
1484 SVal oldValueVal_untested = stateLoad->getSVal(oldValueExpr);
Mike Stump1eb44332009-09-09 15:08:12 +00001485
Ted Kremenek1ff83392009-07-20 20:38:59 +00001486 // FIXME: Issue an error.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001487 if (theValueVal_untested.isUndef() || oldValueVal_untested.isUndef()) {
Mike Stump1eb44332009-09-09 15:08:12 +00001488 return false;
Ted Kremenek1ff83392009-07-20 20:38:59 +00001489 }
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001490
1491 DefinedOrUnknownSVal theValueVal =
1492 cast<DefinedOrUnknownSVal>(theValueVal_untested);
1493 DefinedOrUnknownSVal oldValueVal =
1494 cast<DefinedOrUnknownSVal>(oldValueVal_untested);
Mike Stump1eb44332009-09-09 15:08:12 +00001495
Ted Kremenekff4264d2009-08-25 18:44:25 +00001496 SValuator &SVator = Engine.getSValuator();
Mike Stump1eb44332009-09-09 15:08:12 +00001497
Ted Kremenek1670e402009-04-11 00:11:10 +00001498 // Perform the comparison.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001499 DefinedOrUnknownSVal Cmp = SVator.EvalEQ(stateLoad, theValueVal,
1500 oldValueVal);
Ted Kremeneka591bc02009-06-18 22:57:13 +00001501
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001502 const GRState *stateEqual = stateLoad->Assume(Cmp, true);
Mike Stump1eb44332009-09-09 15:08:12 +00001503
Ted Kremenek1670e402009-04-11 00:11:10 +00001504 // Were they equal?
Ted Kremeneka591bc02009-06-18 22:57:13 +00001505 if (stateEqual) {
Ted Kremenek1670e402009-04-11 00:11:10 +00001506 // Perform the store.
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001507 ExplodedNodeSet TmpStore;
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001508 SVal val = stateEqual->getSVal(newValueExpr);
Mike Stump1eb44332009-09-09 15:08:12 +00001509
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001510 // Handle implicit value casts.
1511 if (const TypedRegion *R =
1512 dyn_cast_or_null<TypedRegion>(location.getAsRegion())) {
Ted Kremenekff4264d2009-08-25 18:44:25 +00001513 llvm::tie(state, val) = SVator.EvalCast(val, state, R->getValueType(C),
1514 newValueExpr->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00001515 }
1516
Ted Kremenek50ecd152009-11-05 00:42:23 +00001517 Engine.EvalStore(TmpStore, NULL, theValueExpr, N, stateEqual, location,
Ted Kremenek32c3fa42009-07-21 21:03:30 +00001518 val, OSAtomicStoreTag);
Mike Stump1eb44332009-09-09 15:08:12 +00001519
Ted Kremenek1670e402009-04-11 00:11:10 +00001520 // Now bind the result of the comparison.
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001521 for (ExplodedNodeSet::iterator I2 = TmpStore.begin(),
Ted Kremenek1670e402009-04-11 00:11:10 +00001522 E2 = TmpStore.end(); I2 != E2; ++I2) {
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001523 ExplodedNode *predNew = *I2;
Ted Kremenek1670e402009-04-11 00:11:10 +00001524 const GRState *stateNew = predNew->getState();
1525 SVal Res = Engine.getValueManager().makeTruthVal(true, CE->getType());
Ted Kremenek8e029342009-08-27 22:17:37 +00001526 Engine.MakeNode(Dst, CE, predNew, stateNew->BindExpr(CE, Res));
Ted Kremenek1670e402009-04-11 00:11:10 +00001527 }
1528 }
Mike Stump1eb44332009-09-09 15:08:12 +00001529
Ted Kremenek1670e402009-04-11 00:11:10 +00001530 // Were they not equal?
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001531 if (const GRState *stateNotEqual = stateLoad->Assume(Cmp, false)) {
Ted Kremenek1670e402009-04-11 00:11:10 +00001532 SVal Res = Engine.getValueManager().makeTruthVal(false, CE->getType());
Ted Kremenek8e029342009-08-27 22:17:37 +00001533 Engine.MakeNode(Dst, CE, N, stateNotEqual->BindExpr(CE, Res));
Ted Kremenek1670e402009-04-11 00:11:10 +00001534 }
1535 }
Mike Stump1eb44332009-09-09 15:08:12 +00001536
Ted Kremenek1670e402009-04-11 00:11:10 +00001537 return true;
1538}
1539
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001540static bool EvalOSAtomic(ExplodedNodeSet& Dst,
Ted Kremenek1670e402009-04-11 00:11:10 +00001541 GRExprEngine& Engine,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001542 GRStmtNodeBuilder& Builder,
Ted Kremenek1670e402009-04-11 00:11:10 +00001543 CallExpr* CE, SVal L,
Zhongxing Xuc5619d92009-08-06 01:32:16 +00001544 ExplodedNode* Pred) {
Zhongxing Xu369f4472009-04-20 05:24:46 +00001545 const FunctionDecl* FD = L.getAsFunctionDecl();
1546 if (!FD)
Ted Kremenek1670e402009-04-11 00:11:10 +00001547 return false;
Zhongxing Xu369f4472009-04-20 05:24:46 +00001548
Ted Kremenek1670e402009-04-11 00:11:10 +00001549 const char *FName = FD->getNameAsCString();
Mike Stump1eb44332009-09-09 15:08:12 +00001550
Ted Kremenek1670e402009-04-11 00:11:10 +00001551 // Check for compare and swap.
Ted Kremenekb3bf76f2009-04-11 00:54:13 +00001552 if (strncmp(FName, "OSAtomicCompareAndSwap", 22) == 0 ||
1553 strncmp(FName, "objc_atomicCompareAndSwap", 25) == 0)
Zhongxing Xu1eacb722009-11-16 02:52:18 +00001554 return EvalOSAtomicCompareAndSwap(Dst, Engine, Builder, CE, Pred);
Ted Kremenekb3bf76f2009-04-11 00:54:13 +00001555
Ted Kremenek1670e402009-04-11 00:11:10 +00001556 // FIXME: Other atomics.
1557 return false;
1558}
1559
1560//===----------------------------------------------------------------------===//
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001561// Transfer function: Function calls.
1562//===----------------------------------------------------------------------===//
Ted Kremenek1670e402009-04-11 00:11:10 +00001563
Zhongxing Xu248072a2009-09-05 05:00:57 +00001564bool GRExprEngine::EvalBuiltinFunction(const FunctionDecl *FD, CallExpr *CE,
1565 ExplodedNode *Pred,
1566 ExplodedNodeSet &Dst) {
1567 if (!FD)
1568 return false;
Mike Stump1eb44332009-09-09 15:08:12 +00001569
Douglas Gregor7814e6d2009-09-12 00:22:50 +00001570 unsigned id = FD->getBuiltinID();
Zhongxing Xu248072a2009-09-05 05:00:57 +00001571 if (!id)
1572 return false;
1573
1574 const GRState *state = Pred->getState();
1575
1576 switch (id) {
1577 case Builtin::BI__builtin_expect: {
1578 // For __builtin_expect, just return the value of the subexpression.
Mike Stump1eb44332009-09-09 15:08:12 +00001579 assert (CE->arg_begin() != CE->arg_end());
Zhongxing Xu248072a2009-09-05 05:00:57 +00001580 SVal X = state->getSVal(*(CE->arg_begin()));
1581 MakeNode(Dst, CE, Pred, state->BindExpr(CE, X));
1582 return true;
1583 }
Mike Stump1eb44332009-09-09 15:08:12 +00001584
Zhongxing Xu248072a2009-09-05 05:00:57 +00001585 case Builtin::BI__builtin_alloca: {
1586 // FIXME: Refactor into StoreManager itself?
1587 MemRegionManager& RM = getStateManager().getRegionManager();
1588 const MemRegion* R =
Ted Kremenek67d12872009-12-07 22:05:27 +00001589 RM.getAllocaRegion(CE, Builder->getCurrentBlockCount(),
1590 Pred->getLocationContext());
Mike Stump1eb44332009-09-09 15:08:12 +00001591
Zhongxing Xu248072a2009-09-05 05:00:57 +00001592 // Set the extent of the region in bytes. This enables us to use the
1593 // SVal of the argument directly. If we save the extent in bits, we
1594 // cannot represent values like symbol*8.
1595 SVal Extent = state->getSVal(*(CE->arg_begin()));
1596 state = getStoreManager().setExtent(state, R, Extent);
1597 MakeNode(Dst, CE, Pred, state->BindExpr(CE, loc::MemRegionVal(R)));
1598 return true;
1599 }
1600 }
1601
1602 return false;
1603}
1604
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001605void GRExprEngine::VisitCall(CallExpr* CE, ExplodedNode* Pred,
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001606 CallExpr::arg_iterator AI,
1607 CallExpr::arg_iterator AE,
Mike Stump1eb44332009-09-09 15:08:12 +00001608 ExplodedNodeSet& Dst) {
Douglas Gregor9d293df2008-10-28 00:22:11 +00001609 // Determine the type of function we're calling (if available).
Douglas Gregor72564e72009-02-26 23:50:07 +00001610 const FunctionProtoType *Proto = NULL;
Douglas Gregor9d293df2008-10-28 00:22:11 +00001611 QualType FnType = CE->getCallee()->IgnoreParens()->getType();
Ted Kremenek6217b802009-07-29 21:53:49 +00001612 if (const PointerType *FnTypePtr = FnType->getAs<PointerType>())
John McCall183700f2009-09-21 23:43:11 +00001613 Proto = FnTypePtr->getPointeeType()->getAs<FunctionProtoType>();
Douglas Gregor9d293df2008-10-28 00:22:11 +00001614
1615 VisitCallRec(CE, Pred, AI, AE, Dst, Proto, /*ParamIdx=*/0);
1616}
1617
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001618void GRExprEngine::VisitCallRec(CallExpr* CE, ExplodedNode* Pred,
Douglas Gregor9d293df2008-10-28 00:22:11 +00001619 CallExpr::arg_iterator AI,
1620 CallExpr::arg_iterator AE,
Mike Stump1eb44332009-09-09 15:08:12 +00001621 ExplodedNodeSet& Dst,
1622 const FunctionProtoType *Proto,
Douglas Gregor9d293df2008-10-28 00:22:11 +00001623 unsigned ParamIdx) {
Mike Stump1eb44332009-09-09 15:08:12 +00001624
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001625 // Process the arguments.
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001626 if (AI != AE) {
Douglas Gregor9d293df2008-10-28 00:22:11 +00001627 // If the call argument is being bound to a reference parameter,
1628 // visit it as an lvalue, not an rvalue.
1629 bool VisitAsLvalue = false;
1630 if (Proto && ParamIdx < Proto->getNumArgs())
1631 VisitAsLvalue = Proto->getArgType(ParamIdx)->isReferenceType();
1632
Mike Stump1eb44332009-09-09 15:08:12 +00001633 ExplodedNodeSet DstTmp;
Douglas Gregor9d293df2008-10-28 00:22:11 +00001634 if (VisitAsLvalue)
Mike Stump1eb44332009-09-09 15:08:12 +00001635 VisitLValue(*AI, Pred, DstTmp);
Douglas Gregor9d293df2008-10-28 00:22:11 +00001636 else
Mike Stump1eb44332009-09-09 15:08:12 +00001637 Visit(*AI, Pred, DstTmp);
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001638 ++AI;
Mike Stump1eb44332009-09-09 15:08:12 +00001639
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001640 for (ExplodedNodeSet::iterator DI=DstTmp.begin(), DE=DstTmp.end(); DI != DE;
1641 ++DI)
Douglas Gregor9d293df2008-10-28 00:22:11 +00001642 VisitCallRec(CE, *DI, AI, AE, Dst, Proto, ParamIdx + 1);
Mike Stump1eb44332009-09-09 15:08:12 +00001643
Ted Kremenekde434242008-02-19 01:44:53 +00001644 return;
1645 }
1646
1647 // If we reach here we have processed all of the arguments. Evaluate
1648 // the callee expression.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001649 ExplodedNodeSet DstTmp;
Ted Kremenek186350f2008-04-23 20:12:28 +00001650 Expr* Callee = CE->getCallee()->IgnoreParens();
Mike Stump1eb44332009-09-09 15:08:12 +00001651
Ted Kremenek5a5d98b2009-07-22 21:43:51 +00001652 { // Enter new scope to make the lifetime of 'DstTmp2' bounded.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001653 ExplodedNodeSet DstTmp2;
Ted Kremenek5a5d98b2009-07-22 21:43:51 +00001654 Visit(Callee, Pred, DstTmp2);
Mike Stump1eb44332009-09-09 15:08:12 +00001655
Ted Kremenek5a5d98b2009-07-22 21:43:51 +00001656 // Perform the previsit of the CallExpr, storing the results in DstTmp.
1657 CheckerVisit(CE, DstTmp, DstTmp2, true);
1658 }
Mike Stump1eb44332009-09-09 15:08:12 +00001659
Ted Kremenekde434242008-02-19 01:44:53 +00001660 // Finally, evaluate the function call.
Mike Stump1eb44332009-09-09 15:08:12 +00001661 for (ExplodedNodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end();
Zhongxing Xu248072a2009-09-05 05:00:57 +00001662 DI != DE; ++DI) {
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001663
Ted Kremeneka8538d92009-02-13 01:45:31 +00001664 const GRState* state = GetState(*DI);
Ted Kremenek3ff12592009-06-19 17:10:32 +00001665 SVal L = state->getSVal(Callee);
Ted Kremenekde434242008-02-19 01:44:53 +00001666
Ted Kremeneka1354a52008-03-03 16:47:31 +00001667 // FIXME: Add support for symbolic function calls (calls involving
1668 // function pointer values that are symbolic).
Zhongxing Xud99f3612009-09-02 08:10:35 +00001669
Ted Kremenek4bf38da2008-03-05 21:15:02 +00001670 // Check for the "noreturn" attribute.
Mike Stump1eb44332009-09-09 15:08:12 +00001671
Ted Kremenek4bf38da2008-03-05 21:15:02 +00001672 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
Zhongxing Xu4e71ddb2009-09-04 02:17:35 +00001673
Zhongxing Xu935ef902009-12-07 09:17:35 +00001674 ExplodedNodeSet DstTmp3, DstChecker, DstOther;
Mike Stump1eb44332009-09-09 15:08:12 +00001675
Zhongxing Xu935ef902009-12-07 09:17:35 +00001676 // If the callee is processed by a checker, skip the rest logic.
1677 if (CheckerEvalCall(CE, DstChecker, *DI))
1678 DstTmp3 = DstChecker;
1679 else {
Zhongxing Xu935ef902009-12-07 09:17:35 +00001680 // Dispatch to the plug-in transfer function.
1681 SaveOr OldHasGen(Builder->HasGeneratedNode);
1682 Pred = *DI;
1683
1684 // Dispatch to transfer function logic to handle the call itself.
1685 // FIXME: Allow us to chain together transfer functions.
1686 assert(Builder && "GRStmtNodeBuilder must be defined.");
Ted Kremenek31a241a2009-11-12 04:35:08 +00001687
Zhongxing Xu935ef902009-12-07 09:17:35 +00001688 if (!EvalOSAtomic(DstOther, *this, *Builder, CE, L, Pred))
1689 getTF().EvalCall(DstOther, *this, *Builder, CE, L, Pred);
1690
1691 // Handle the case where no nodes where generated. Auto-generate that
1692 // contains the updated state if we aren't generating sinks.
1693 if (!Builder->BuildSinks && DstTmp3.empty() &&
1694 !Builder->HasGeneratedNode)
1695 MakeNode(DstOther, CE, Pred, state);
1696
1697 DstTmp3 = DstOther;
1698 }
1699
Ted Kremenek31a241a2009-11-12 04:35:08 +00001700 // Perform the post-condition check of the CallExpr.
Zhongxing Xu935ef902009-12-07 09:17:35 +00001701 CheckerVisit(CE, Dst, DstTmp3, false);
Ted Kremenekde434242008-02-19 01:44:53 +00001702 }
1703}
1704
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001705//===----------------------------------------------------------------------===//
Ted Kremenek97ed4f62008-10-17 00:03:18 +00001706// Transfer function: Objective-C ivar references.
1707//===----------------------------------------------------------------------===//
1708
Ted Kremenekf5cae632009-02-28 20:50:43 +00001709static std::pair<const void*,const void*> EagerlyAssumeTag
1710 = std::pair<const void*,const void*>(&EagerlyAssumeTag,0);
1711
Zhongxing Xub317f8f2009-09-10 05:44:00 +00001712void GRExprEngine::EvalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
1713 Expr *Ex) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001714 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
1715 ExplodedNode *Pred = *I;
Mike Stump1eb44332009-09-09 15:08:12 +00001716
Ted Kremenekb2939022009-02-25 23:32:10 +00001717 // Test if the previous node was as the same expression. This can happen
1718 // when the expression fails to evaluate to anything meaningful and
1719 // (as an optimization) we don't generate a node.
Mike Stump1eb44332009-09-09 15:08:12 +00001720 ProgramPoint P = Pred->getLocation();
Ted Kremenekb2939022009-02-25 23:32:10 +00001721 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) {
Mike Stump1eb44332009-09-09 15:08:12 +00001722 Dst.Add(Pred);
Ted Kremenekb2939022009-02-25 23:32:10 +00001723 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001724 }
Ted Kremenekb2939022009-02-25 23:32:10 +00001725
Mike Stump1eb44332009-09-09 15:08:12 +00001726 const GRState* state = Pred->getState();
1727 SVal V = state->getSVal(Ex);
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001728 if (nonloc::SymExprVal *SEV = dyn_cast<nonloc::SymExprVal>(&V)) {
Ted Kremenek48af2a92009-02-25 22:32:02 +00001729 // First assume that the condition is true.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001730 if (const GRState *stateTrue = state->Assume(*SEV, true)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001731 stateTrue = stateTrue->BindExpr(Ex,
Ted Kremenek0fb0bc42009-08-27 01:39:13 +00001732 ValMgr.makeIntVal(1U, Ex->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00001733 Dst.Add(Builder->generateNode(PostStmtCustom(Ex,
Zhongxing Xu25e695b2009-08-15 03:17:38 +00001734 &EagerlyAssumeTag, Pred->getLocationContext()),
Ted Kremenek48af2a92009-02-25 22:32:02 +00001735 stateTrue, Pred));
1736 }
Mike Stump1eb44332009-09-09 15:08:12 +00001737
Ted Kremenek48af2a92009-02-25 22:32:02 +00001738 // Next, assume that the condition is false.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001739 if (const GRState *stateFalse = state->Assume(*SEV, false)) {
Mike Stump1eb44332009-09-09 15:08:12 +00001740 stateFalse = stateFalse->BindExpr(Ex,
Ted Kremenek0fb0bc42009-08-27 01:39:13 +00001741 ValMgr.makeIntVal(0U, Ex->getType()));
Zhongxing Xu25e695b2009-08-15 03:17:38 +00001742 Dst.Add(Builder->generateNode(PostStmtCustom(Ex, &EagerlyAssumeTag,
1743 Pred->getLocationContext()),
Ted Kremenek48af2a92009-02-25 22:32:02 +00001744 stateFalse, Pred));
1745 }
1746 }
1747 else
1748 Dst.Add(Pred);
1749 }
1750}
1751
1752//===----------------------------------------------------------------------===//
1753// Transfer function: Objective-C ivar references.
1754//===----------------------------------------------------------------------===//
1755
Zhongxing Xub317f8f2009-09-10 05:44:00 +00001756void GRExprEngine::VisitObjCIvarRefExpr(ObjCIvarRefExpr* Ex, ExplodedNode* Pred,
1757 ExplodedNodeSet& Dst, bool asLValue) {
Mike Stump1eb44332009-09-09 15:08:12 +00001758
Ted Kremenek97ed4f62008-10-17 00:03:18 +00001759 Expr* Base = cast<Expr>(Ex->getBase());
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001760 ExplodedNodeSet Tmp;
Ted Kremenek97ed4f62008-10-17 00:03:18 +00001761 Visit(Base, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00001762
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001763 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001764 const GRState* state = GetState(*I);
Ted Kremenek3ff12592009-06-19 17:10:32 +00001765 SVal BaseVal = state->getSVal(Base);
1766 SVal location = state->getLValue(Ex->getDecl(), BaseVal);
Mike Stump1eb44332009-09-09 15:08:12 +00001767
Ted Kremenek97ed4f62008-10-17 00:03:18 +00001768 if (asLValue)
Ted Kremenek8e029342009-08-27 22:17:37 +00001769 MakeNode(Dst, Ex, *I, state->BindExpr(Ex, location));
Ted Kremenek97ed4f62008-10-17 00:03:18 +00001770 else
Ted Kremeneka8538d92009-02-13 01:45:31 +00001771 EvalLoad(Dst, Ex, *I, state, location);
Ted Kremenek97ed4f62008-10-17 00:03:18 +00001772 }
1773}
1774
1775//===----------------------------------------------------------------------===//
Ted Kremenekaf337412008-11-12 19:24:17 +00001776// Transfer function: Objective-C fast enumeration 'for' statements.
1777//===----------------------------------------------------------------------===//
1778
1779void GRExprEngine::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S,
Zhongxing Xub317f8f2009-09-10 05:44:00 +00001780 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001781
Ted Kremenekaf337412008-11-12 19:24:17 +00001782 // ObjCForCollectionStmts are processed in two places. This method
1783 // handles the case where an ObjCForCollectionStmt* occurs as one of the
1784 // statements within a basic block. This transfer function does two things:
1785 //
1786 // (1) binds the next container value to 'element'. This creates a new
1787 // node in the ExplodedGraph.
1788 //
1789 // (2) binds the value 0/1 to the ObjCForCollectionStmt* itself, indicating
1790 // whether or not the container has any more elements. This value
1791 // will be tested in ProcessBranch. We need to explicitly bind
1792 // this value because a container can contain nil elements.
Mike Stump1eb44332009-09-09 15:08:12 +00001793 //
Ted Kremenekaf337412008-11-12 19:24:17 +00001794 // FIXME: Eventually this logic should actually do dispatches to
1795 // 'countByEnumeratingWithState:objects:count:' (NSFastEnumeration).
1796 // This will require simulating a temporary NSFastEnumerationState, either
1797 // through an SVal or through the use of MemRegions. This value can
1798 // be affixed to the ObjCForCollectionStmt* instead of 0/1; when the loop
1799 // terminates we reclaim the temporary (it goes out of scope) and we
1800 // we can test if the SVal is 0 or if the MemRegion is null (depending
1801 // on what approach we take).
1802 //
1803 // For now: simulate (1) by assigning either a symbol or nil if the
1804 // container is empty. Thus this transfer function will by default
1805 // result in state splitting.
Mike Stump1eb44332009-09-09 15:08:12 +00001806
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001807 Stmt* elem = S->getElement();
1808 SVal ElementV;
Mike Stump1eb44332009-09-09 15:08:12 +00001809
Ted Kremenekaf337412008-11-12 19:24:17 +00001810 if (DeclStmt* DS = dyn_cast<DeclStmt>(elem)) {
Chris Lattner7e24e822009-03-28 06:33:19 +00001811 VarDecl* ElemD = cast<VarDecl>(DS->getSingleDecl());
Ted Kremenekaf337412008-11-12 19:24:17 +00001812 assert (ElemD->getInit() == 0);
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001813 ElementV = GetState(Pred)->getLValue(ElemD, Pred->getLocationContext());
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001814 VisitObjCForCollectionStmtAux(S, Pred, Dst, ElementV);
1815 return;
Ted Kremenekaf337412008-11-12 19:24:17 +00001816 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001817
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001818 ExplodedNodeSet Tmp;
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001819 VisitLValue(cast<Expr>(elem), Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00001820
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001821 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) {
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001822 const GRState* state = GetState(*I);
Ted Kremenek3ff12592009-06-19 17:10:32 +00001823 VisitObjCForCollectionStmtAux(S, *I, Dst, state->getSVal(elem));
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001824 }
1825}
1826
1827void GRExprEngine::VisitObjCForCollectionStmtAux(ObjCForCollectionStmt* S,
Zhongxing Xub317f8f2009-09-10 05:44:00 +00001828 ExplodedNode* Pred, ExplodedNodeSet& Dst,
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001829 SVal ElementV) {
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001830
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001831 // Check if the location we are writing back to is a null pointer.
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001832 Stmt* elem = S->getElement();
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001833 ExplodedNodeSet Tmp;
1834 EvalLocation(Tmp, elem, Pred, GetState(Pred), ElementV, NULL, false);
1835
1836 if (Tmp.empty())
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001837 return;
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001838
1839 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1840 Pred = *NI;
1841 const GRState *state = GetState(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00001842
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001843 // Handle the case where the container still has elements.
1844 SVal TrueV = ValMgr.makeTruthVal(1);
1845 const GRState *hasElems = state->BindExpr(S, TrueV);
Ted Kremenek06fb99f2008-11-14 19:47:18 +00001846
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001847 // Handle the case where the container has no elements.
1848 SVal FalseV = ValMgr.makeTruthVal(0);
1849 const GRState *noElems = state->BindExpr(S, FalseV);
Mike Stump1eb44332009-09-09 15:08:12 +00001850
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001851 if (loc::MemRegionVal* MV = dyn_cast<loc::MemRegionVal>(&ElementV))
1852 if (const TypedRegion* R = dyn_cast<TypedRegion>(MV->getRegion())) {
1853 // FIXME: The proper thing to do is to really iterate over the
1854 // container. We will do this with dispatch logic to the store.
1855 // For now, just 'conjure' up a symbolic value.
1856 QualType T = R->getValueType(getContext());
1857 assert(Loc::IsLocType(T));
1858 unsigned Count = Builder->getCurrentBlockCount();
1859 SymbolRef Sym = SymMgr.getConjuredSymbol(elem, T, Count);
1860 SVal V = ValMgr.makeLoc(Sym);
1861 hasElems = hasElems->bindLoc(ElementV, V);
Mike Stump1eb44332009-09-09 15:08:12 +00001862
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001863 // Bind the location to 'nil' on the false branch.
1864 SVal nilV = ValMgr.makeIntVal(0, T);
1865 noElems = noElems->bindLoc(ElementV, nilV);
1866 }
Ted Kremenek116ed0a2008-11-12 21:12:46 +00001867
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001868 // Create the new nodes.
1869 MakeNode(Dst, S, Pred, hasElems);
1870 MakeNode(Dst, S, Pred, noElems);
1871 }
Ted Kremenekaf337412008-11-12 19:24:17 +00001872}
1873
1874//===----------------------------------------------------------------------===//
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001875// Transfer function: Objective-C message expressions.
1876//===----------------------------------------------------------------------===//
1877
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001878void GRExprEngine::VisitObjCMessageExpr(ObjCMessageExpr* ME, ExplodedNode* Pred,
1879 ExplodedNodeSet& Dst){
Mike Stump1eb44332009-09-09 15:08:12 +00001880
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001881 VisitObjCMessageExprArgHelper(ME, ME->arg_begin(), ME->arg_end(),
1882 Pred, Dst);
Mike Stump1eb44332009-09-09 15:08:12 +00001883}
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001884
1885void GRExprEngine::VisitObjCMessageExprArgHelper(ObjCMessageExpr* ME,
Zhongxing Xud3118bd2008-10-31 07:26:14 +00001886 ObjCMessageExpr::arg_iterator AI,
1887 ObjCMessageExpr::arg_iterator AE,
Zhongxing Xub317f8f2009-09-10 05:44:00 +00001888 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001889 if (AI == AE) {
Mike Stump1eb44332009-09-09 15:08:12 +00001890
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001891 // Process the receiver.
Mike Stump1eb44332009-09-09 15:08:12 +00001892
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001893 if (Expr* Receiver = ME->getReceiver()) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001894 ExplodedNodeSet Tmp;
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001895 Visit(Receiver, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00001896
Zhongxing Xub317f8f2009-09-10 05:44:00 +00001897 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI != NE;
1898 ++NI)
Daniel Dunbar36292552009-07-23 04:41:06 +00001899 VisitObjCMessageExprDispatchHelper(ME, *NI, Dst);
Mike Stump1eb44332009-09-09 15:08:12 +00001900
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001901 return;
1902 }
Mike Stump1eb44332009-09-09 15:08:12 +00001903
Daniel Dunbar36292552009-07-23 04:41:06 +00001904 VisitObjCMessageExprDispatchHelper(ME, Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001905 return;
1906 }
Mike Stump1eb44332009-09-09 15:08:12 +00001907
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001908 ExplodedNodeSet Tmp;
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001909 Visit(*AI, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00001910
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001911 ++AI;
Mike Stump1eb44332009-09-09 15:08:12 +00001912
Zhongxing Xub317f8f2009-09-10 05:44:00 +00001913 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI)
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001914 VisitObjCMessageExprArgHelper(ME, AI, AE, *NI, Dst);
1915}
1916
1917void GRExprEngine::VisitObjCMessageExprDispatchHelper(ObjCMessageExpr* ME,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001918 ExplodedNode* Pred,
1919 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001920
Ted Kremenek54cb7cc2009-11-03 08:03:59 +00001921 // Handle previsits checks.
1922 ExplodedNodeSet Src, DstTmp;
Ted Kremenekfee96e02009-11-24 21:41:28 +00001923 Src.Add(Pred);
1924
Zhongxing Xua46e4d92009-12-02 05:49:12 +00001925 CheckerVisit(ME, DstTmp, Src, true);
Ted Kremenek54cb7cc2009-11-03 08:03:59 +00001926
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001927 unsigned size = Dst.size();
Ted Kremenekc79d7d42009-11-21 01:25:37 +00001928
Ted Kremenek54cb7cc2009-11-03 08:03:59 +00001929 for (ExplodedNodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end();
Ted Kremenekc79d7d42009-11-21 01:25:37 +00001930 DI!=DE; ++DI) {
1931 Pred = *DI;
Ted Kremenekc79d7d42009-11-21 01:25:37 +00001932 bool RaisesException = false;
1933
Zhongxing Xua46e4d92009-12-02 05:49:12 +00001934 if (const Expr *Receiver = ME->getReceiver()) {
1935 const GRState *state = Pred->getState();
1936
1937 // Bifurcate the state into nil and non-nil ones.
1938 DefinedOrUnknownSVal receiverVal =
1939 cast<DefinedOrUnknownSVal>(state->getSVal(Receiver));
1940
1941 const GRState *notNilState, *nilState;
1942 llvm::tie(notNilState, nilState) = state->Assume(receiverVal);
1943
1944 // There are three cases: can be nil or non-nil, must be nil, must be
1945 // non-nil. We handle must be nil, and merge the rest two into non-nil.
1946 if (nilState && !notNilState) {
1947 CheckerEvalNilReceiver(ME, Dst, nilState, Pred);
1948 return;
1949 }
1950
1951 assert(notNilState);
1952
Ted Kremenekc79d7d42009-11-21 01:25:37 +00001953 // Check if the "raise" message was sent.
1954 if (ME->getSelector() == RaiseSel)
1955 RaisesException = true;
Zhongxing Xua46e4d92009-12-02 05:49:12 +00001956
1957 // Check if we raise an exception. For now treat these as sinks.
1958 // Eventually we will want to handle exceptions properly.
1959 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
1960 if (RaisesException)
1961 Builder->BuildSinks = true;
1962
1963 // Dispatch to plug-in transfer function.
1964 SaveOr OldHasGen(Builder->HasGeneratedNode);
1965 EvalObjCMessageExpr(Dst, ME, Pred, notNilState);
Ted Kremenekc79d7d42009-11-21 01:25:37 +00001966 }
1967 else {
1968
1969 IdentifierInfo* ClsName = ME->getClassName();
1970 Selector S = ME->getSelector();
1971
1972 // Check for special instance methods.
1973
1974 if (!NSExceptionII) {
1975 ASTContext& Ctx = getContext();
1976
1977 NSExceptionII = &Ctx.Idents.get("NSException");
1978 }
1979
1980 if (ClsName == NSExceptionII) {
1981
1982 enum { NUM_RAISE_SELECTORS = 2 };
1983
1984 // Lazily create a cache of the selectors.
1985
1986 if (!NSExceptionInstanceRaiseSelectors) {
1987
1988 ASTContext& Ctx = getContext();
1989
1990 NSExceptionInstanceRaiseSelectors = new Selector[NUM_RAISE_SELECTORS];
1991
1992 llvm::SmallVector<IdentifierInfo*, NUM_RAISE_SELECTORS> II;
1993 unsigned idx = 0;
1994
1995 // raise:format:
1996 II.push_back(&Ctx.Idents.get("raise"));
1997 II.push_back(&Ctx.Idents.get("format"));
1998 NSExceptionInstanceRaiseSelectors[idx++] =
1999 Ctx.Selectors.getSelector(II.size(), &II[0]);
2000
2001 // raise:format::arguments:
2002 II.push_back(&Ctx.Idents.get("arguments"));
2003 NSExceptionInstanceRaiseSelectors[idx++] =
2004 Ctx.Selectors.getSelector(II.size(), &II[0]);
2005 }
2006
2007 for (unsigned i = 0; i < NUM_RAISE_SELECTORS; ++i)
2008 if (S == NSExceptionInstanceRaiseSelectors[i]) {
2009 RaisesException = true; break;
2010 }
2011 }
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002012
2013 // Check if we raise an exception. For now treat these as sinks.
2014 // Eventually we will want to handle exceptions properly.
2015 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
2016 if (RaisesException)
2017 Builder->BuildSinks = true;
2018
2019 // Dispatch to plug-in transfer function.
2020 SaveOr OldHasGen(Builder->HasGeneratedNode);
2021 EvalObjCMessageExpr(Dst, ME, Pred, Builder->GetState(Pred));
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002022 }
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002023 }
Mike Stump1eb44332009-09-09 15:08:12 +00002024
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002025 // Handle the case where no nodes where generated. Auto-generate that
2026 // contains the updated state if we aren't generating sinks.
Ted Kremenekb0533962008-04-18 20:35:30 +00002027 if (!Builder->BuildSinks && Dst.size() == size && !Builder->HasGeneratedNode)
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002028 MakeNode(Dst, ME, Pred, GetState(Pred));
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002029}
2030
2031//===----------------------------------------------------------------------===//
2032// Transfer functions: Miscellaneous statements.
2033//===----------------------------------------------------------------------===//
2034
Zhongxing Xu4f3dc692009-11-09 08:07:38 +00002035void GRExprEngine::VisitCast(Expr* CastE, Expr* Ex, ExplodedNode* Pred,
2036 ExplodedNodeSet& Dst){
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002037 ExplodedNodeSet S1;
Ted Kremenek5d3003a2008-02-19 18:52:54 +00002038 QualType T = CastE->getType();
Zhongxing Xu933c3e12008-10-21 06:54:23 +00002039 QualType ExTy = Ex->getType();
Zhongxing Xued340f72008-10-22 08:02:16 +00002040
Zhongxing Xud3118bd2008-10-31 07:26:14 +00002041 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE))
Douglas Gregor49badde2008-10-27 19:41:14 +00002042 T = ExCast->getTypeAsWritten();
2043
Zhongxing Xued340f72008-10-22 08:02:16 +00002044 if (ExTy->isArrayType() || ExTy->isFunctionType() || T->isReferenceType())
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002045 VisitLValue(Ex, Pred, S1);
Ted Kremenek65cfb732008-03-04 22:16:08 +00002046 else
2047 Visit(Ex, Pred, S1);
Mike Stump1eb44332009-09-09 15:08:12 +00002048
Zhongxing Xu4f3dc692009-11-09 08:07:38 +00002049 ExplodedNodeSet S2;
2050 CheckerVisit(CastE, S2, S1, true);
2051
Ted Kremenek0fe33bc2008-04-22 21:10:18 +00002052 // Check for casting to "void".
Mike Stump1eb44332009-09-09 15:08:12 +00002053 if (T->isVoidType()) {
Zhongxing Xu4f3dc692009-11-09 08:07:38 +00002054 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I)
2055 Dst.Add(*I);
Ted Kremenek874d63f2008-01-24 02:02:54 +00002056 return;
2057 }
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002058
Zhongxing Xu4f3dc692009-11-09 08:07:38 +00002059 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {
2060 ExplodedNode* N = *I;
Ted Kremeneka8538d92009-02-13 01:45:31 +00002061 const GRState* state = GetState(N);
Ted Kremenek3ff12592009-06-19 17:10:32 +00002062 SVal V = state->getSVal(Ex);
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002063 const SValuator::CastResult &Res = SVator.EvalCast(V, state, T, ExTy);
Ted Kremenek8e029342009-08-27 22:17:37 +00002064 state = Res.getState()->BindExpr(CastE, Res.getSVal());
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002065 MakeNode(Dst, CastE, N, state);
Ted Kremenek874d63f2008-01-24 02:02:54 +00002066 }
Ted Kremenek9de04c42008-01-24 20:55:43 +00002067}
2068
Ted Kremenek4f090272008-10-27 21:54:31 +00002069void GRExprEngine::VisitCompoundLiteralExpr(CompoundLiteralExpr* CL,
Mike Stump1eb44332009-09-09 15:08:12 +00002070 ExplodedNode* Pred,
2071 ExplodedNodeSet& Dst,
Zhongxing Xuf22679e2008-11-07 10:38:33 +00002072 bool asLValue) {
Ted Kremenek4f090272008-10-27 21:54:31 +00002073 InitListExpr* ILE = cast<InitListExpr>(CL->getInitializer()->IgnoreParens());
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002074 ExplodedNodeSet Tmp;
Ted Kremenek4f090272008-10-27 21:54:31 +00002075 Visit(ILE, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002076
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002077 for (ExplodedNodeSet::iterator I = Tmp.begin(), EI = Tmp.end(); I!=EI; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002078 const GRState* state = GetState(*I);
Ted Kremenek3ff12592009-06-19 17:10:32 +00002079 SVal ILV = state->getSVal(ILE);
Ted Kremenek67d12872009-12-07 22:05:27 +00002080 const LocationContext *LC = (*I)->getLocationContext();
2081 state = state->bindCompoundLiteral(CL, LC, ILV);
Ted Kremenek4f090272008-10-27 21:54:31 +00002082
Ted Kremenek67d12872009-12-07 22:05:27 +00002083 if (asLValue) {
2084 MakeNode(Dst, CL, *I, state->BindExpr(CL, state->getLValue(CL, LC)));
2085 }
Zhongxing Xuf22679e2008-11-07 10:38:33 +00002086 else
Ted Kremenek8e029342009-08-27 22:17:37 +00002087 MakeNode(Dst, CL, *I, state->BindExpr(CL, ILV));
Ted Kremenek4f090272008-10-27 21:54:31 +00002088 }
2089}
2090
Ted Kremenekd17da2b2009-08-21 22:28:32 +00002091void GRExprEngine::VisitDeclStmt(DeclStmt *DS, ExplodedNode *Pred,
Mike Stump1eb44332009-09-09 15:08:12 +00002092 ExplodedNodeSet& Dst) {
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002093
Mike Stump1eb44332009-09-09 15:08:12 +00002094 // The CFG has one DeclStmt per Decl.
Douglas Gregor4afa39d2009-01-20 01:17:11 +00002095 Decl* D = *DS->decl_begin();
Mike Stump1eb44332009-09-09 15:08:12 +00002096
Ted Kremeneke6c62e32008-08-28 18:34:26 +00002097 if (!D || !isa<VarDecl>(D))
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002098 return;
Mike Stump1eb44332009-09-09 15:08:12 +00002099
2100 const VarDecl* VD = dyn_cast<VarDecl>(D);
Ted Kremenekaf337412008-11-12 19:24:17 +00002101 Expr* InitEx = const_cast<Expr*>(VD->getInit());
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002102
2103 // FIXME: static variables may have an initializer, but the second
2104 // time a function is called those values may not be current.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002105 ExplodedNodeSet Tmp;
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002106
Ted Kremenekaf337412008-11-12 19:24:17 +00002107 if (InitEx)
2108 Visit(InitEx, Pred, Tmp);
Ted Kremenek1152fc02009-07-17 23:48:26 +00002109 else
Ted Kremeneke6c62e32008-08-28 18:34:26 +00002110 Tmp.Add(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00002111
Ted Kremenekae162332009-11-07 03:56:57 +00002112 ExplodedNodeSet Tmp2;
2113 CheckerVisit(DS, Tmp2, Tmp, true);
2114
2115 for (ExplodedNodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) {
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002116 ExplodedNode *N = *I;
Ted Kremenekae162332009-11-07 03:56:57 +00002117 const GRState *state = GetState(N);
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002118
Zhongxing Xu4193eca2008-12-20 06:32:12 +00002119 // Decls without InitExpr are not initialized explicitly.
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002120 const LocationContext *LC = N->getLocationContext();
Ted Kremenekd17da2b2009-08-21 22:28:32 +00002121
Ted Kremenekaf337412008-11-12 19:24:17 +00002122 if (InitEx) {
Ted Kremenek3ff12592009-06-19 17:10:32 +00002123 SVal InitVal = state->getSVal(InitEx);
Ted Kremenekaf337412008-11-12 19:24:17 +00002124 QualType T = VD->getType();
Mike Stump1eb44332009-09-09 15:08:12 +00002125
Ted Kremenekaf337412008-11-12 19:24:17 +00002126 // Recover some path-sensitivity if a scalar value evaluated to
2127 // UnknownVal.
Mike Stump1eb44332009-09-09 15:08:12 +00002128 if (InitVal.isUnknown() ||
Ted Kremenek276c6ac2009-03-11 02:24:48 +00002129 !getConstraintManager().canReasonAbout(InitVal)) {
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002130 InitVal = ValMgr.getConjuredSymbolVal(NULL, InitEx,
2131 Builder->getCurrentBlockCount());
Mike Stump1eb44332009-09-09 15:08:12 +00002132 }
Ted Kremenekf6f56d42009-11-04 00:09:15 +00002133
Ted Kremenek50ecd152009-11-05 00:42:23 +00002134 EvalBind(Dst, DS, DS, *I, state,
2135 loc::MemRegionVal(state->getRegion(VD, LC)), InitVal, true);
Mike Stump1eb44332009-09-09 15:08:12 +00002136 }
Ted Kremenek5b8d9012009-02-14 01:54:57 +00002137 else {
Ted Kremenekf6f56d42009-11-04 00:09:15 +00002138 state = state->bindDeclWithNoInit(state->getRegion(VD, LC));
Ted Kremenek5b8d9012009-02-14 01:54:57 +00002139 MakeNode(Dst, DS, *I, state);
Ted Kremenekefd59942008-12-08 22:47:34 +00002140 }
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002141 }
Ted Kremenek9de04c42008-01-24 20:55:43 +00002142}
Ted Kremenek874d63f2008-01-24 02:02:54 +00002143
Ted Kremenekf75b1862008-10-30 17:47:32 +00002144namespace {
2145 // This class is used by VisitInitListExpr as an item in a worklist
2146 // for processing the values contained in an InitListExpr.
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +00002147class InitListWLItem {
Ted Kremenekf75b1862008-10-30 17:47:32 +00002148public:
2149 llvm::ImmutableList<SVal> Vals;
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002150 ExplodedNode* N;
Ted Kremenekf75b1862008-10-30 17:47:32 +00002151 InitListExpr::reverse_iterator Itr;
Mike Stump1eb44332009-09-09 15:08:12 +00002152
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002153 InitListWLItem(ExplodedNode* n, llvm::ImmutableList<SVal> vals,
2154 InitListExpr::reverse_iterator itr)
Ted Kremenekf75b1862008-10-30 17:47:32 +00002155 : Vals(vals), N(n), Itr(itr) {}
2156};
2157}
2158
2159
Mike Stump1eb44332009-09-09 15:08:12 +00002160void GRExprEngine::VisitInitListExpr(InitListExpr* E, ExplodedNode* Pred,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002161 ExplodedNodeSet& Dst) {
Ted Kremeneka49e3672008-10-30 23:14:36 +00002162
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002163 const GRState* state = GetState(Pred);
Ted Kremenek76dba7b2008-11-13 05:05:34 +00002164 QualType T = getContext().getCanonicalType(E->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00002165 unsigned NumInitElements = E->getNumInits();
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002166
Ted Kremenekf3bfa212009-07-28 20:46:55 +00002167 if (T->isArrayType() || T->isStructureType() ||
2168 T->isUnionType() || T->isVectorType()) {
Ted Kremenekf75b1862008-10-30 17:47:32 +00002169
Ted Kremeneka49e3672008-10-30 23:14:36 +00002170 llvm::ImmutableList<SVal> StartVals = getBasicVals().getEmptySValList();
Mike Stump1eb44332009-09-09 15:08:12 +00002171
Ted Kremeneka49e3672008-10-30 23:14:36 +00002172 // Handle base case where the initializer has no elements.
2173 // e.g: static int* myArray[] = {};
2174 if (NumInitElements == 0) {
Zhongxing Xud91ee272009-06-23 09:02:15 +00002175 SVal V = ValMgr.makeCompoundVal(T, StartVals);
Ted Kremenek8e029342009-08-27 22:17:37 +00002176 MakeNode(Dst, E, Pred, state->BindExpr(E, V));
Ted Kremeneka49e3672008-10-30 23:14:36 +00002177 return;
Mike Stump1eb44332009-09-09 15:08:12 +00002178 }
2179
Ted Kremeneka49e3672008-10-30 23:14:36 +00002180 // Create a worklist to process the initializers.
2181 llvm::SmallVector<InitListWLItem, 10> WorkList;
Mike Stump1eb44332009-09-09 15:08:12 +00002182 WorkList.reserve(NumInitElements);
2183 WorkList.push_back(InitListWLItem(Pred, StartVals, E->rbegin()));
Ted Kremenekf75b1862008-10-30 17:47:32 +00002184 InitListExpr::reverse_iterator ItrEnd = E->rend();
Ted Kremenekcf549592009-09-22 21:19:14 +00002185 assert(!(E->rbegin() == E->rend()));
Mike Stump1eb44332009-09-09 15:08:12 +00002186
Ted Kremeneka49e3672008-10-30 23:14:36 +00002187 // Process the worklist until it is empty.
Ted Kremenekf75b1862008-10-30 17:47:32 +00002188 while (!WorkList.empty()) {
2189 InitListWLItem X = WorkList.back();
2190 WorkList.pop_back();
Mike Stump1eb44332009-09-09 15:08:12 +00002191
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002192 ExplodedNodeSet Tmp;
Ted Kremenekf75b1862008-10-30 17:47:32 +00002193 Visit(*X.Itr, X.N, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002194
Ted Kremenekf75b1862008-10-30 17:47:32 +00002195 InitListExpr::reverse_iterator NewItr = X.Itr + 1;
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002196
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002197 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
Ted Kremenekf75b1862008-10-30 17:47:32 +00002198 // Get the last initializer value.
2199 state = GetState(*NI);
Ted Kremenek3ff12592009-06-19 17:10:32 +00002200 SVal InitV = state->getSVal(cast<Expr>(*X.Itr));
Mike Stump1eb44332009-09-09 15:08:12 +00002201
Ted Kremenekf75b1862008-10-30 17:47:32 +00002202 // Construct the new list of values by prepending the new value to
2203 // the already constructed list.
2204 llvm::ImmutableList<SVal> NewVals =
2205 getBasicVals().consVals(InitV, X.Vals);
Mike Stump1eb44332009-09-09 15:08:12 +00002206
Ted Kremenekf75b1862008-10-30 17:47:32 +00002207 if (NewItr == ItrEnd) {
Zhongxing Xua189dca2008-10-31 03:01:26 +00002208 // Now we have a list holding all init values. Make CompoundValData.
Zhongxing Xud91ee272009-06-23 09:02:15 +00002209 SVal V = ValMgr.makeCompoundVal(T, NewVals);
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002210
Ted Kremenekf75b1862008-10-30 17:47:32 +00002211 // Make final state and node.
Ted Kremenek8e029342009-08-27 22:17:37 +00002212 MakeNode(Dst, E, *NI, state->BindExpr(E, V));
Ted Kremenekf75b1862008-10-30 17:47:32 +00002213 }
2214 else {
2215 // Still some initializer values to go. Push them onto the worklist.
2216 WorkList.push_back(InitListWLItem(*NI, NewVals, NewItr));
2217 }
2218 }
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002219 }
Mike Stump1eb44332009-09-09 15:08:12 +00002220
Ted Kremenek87903072008-10-30 18:34:31 +00002221 return;
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002222 }
2223
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002224 if (Loc::IsLocType(T) || T->isIntegerType()) {
2225 assert (E->getNumInits() == 1);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002226 ExplodedNodeSet Tmp;
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002227 Expr* Init = E->getInit(0);
2228 Visit(Init, Pred, Tmp);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002229 for (ExplodedNodeSet::iterator I = Tmp.begin(), EI = Tmp.end(); I != EI; ++I) {
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002230 state = GetState(*I);
Ted Kremenek8e029342009-08-27 22:17:37 +00002231 MakeNode(Dst, E, *I, state->BindExpr(E, state->getSVal(Init)));
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002232 }
2233 return;
2234 }
2235
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002236 assert(0 && "unprocessed InitListExpr type");
2237}
Ted Kremenekf233d482008-02-05 00:26:40 +00002238
Sebastian Redl05189992008-11-11 17:56:53 +00002239/// VisitSizeOfAlignOfExpr - Transfer function for sizeof(type).
2240void GRExprEngine::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr* Ex,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002241 ExplodedNode* Pred,
2242 ExplodedNodeSet& Dst) {
Sebastian Redl05189992008-11-11 17:56:53 +00002243 QualType T = Ex->getTypeOfArgument();
Mike Stump1eb44332009-09-09 15:08:12 +00002244 uint64_t amt;
2245
Ted Kremenek87e80342008-03-15 03:13:20 +00002246 if (Ex->isSizeOf()) {
Mike Stump1eb44332009-09-09 15:08:12 +00002247 if (T == getContext().VoidTy) {
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002248 // sizeof(void) == 1 byte.
2249 amt = 1;
2250 }
2251 else if (!T.getTypePtr()->isConstantSizeType()) {
2252 // FIXME: Add support for VLAs.
Ted Kremenek87e80342008-03-15 03:13:20 +00002253 return;
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002254 }
2255 else if (T->isObjCInterfaceType()) {
2256 // Some code tries to take the sizeof an ObjCInterfaceType, relying that
2257 // the compiler has laid out its representation. Just report Unknown
Mike Stump1eb44332009-09-09 15:08:12 +00002258 // for these.
Ted Kremenekf342d182008-04-30 21:31:12 +00002259 return;
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002260 }
2261 else {
2262 // All other cases.
Ted Kremenek87e80342008-03-15 03:13:20 +00002263 amt = getContext().getTypeSize(T) / 8;
Mike Stump1eb44332009-09-09 15:08:12 +00002264 }
Ted Kremenek87e80342008-03-15 03:13:20 +00002265 }
2266 else // Get alignment of the type.
Ted Kremenek897781a2008-03-15 03:13:55 +00002267 amt = getContext().getTypeAlign(T) / 8;
Mike Stump1eb44332009-09-09 15:08:12 +00002268
Ted Kremenek0e561a32008-03-21 21:30:14 +00002269 MakeNode(Dst, Ex, Pred,
Ted Kremenek8e029342009-08-27 22:17:37 +00002270 GetState(Pred)->BindExpr(Ex, ValMgr.makeIntVal(amt, Ex->getType())));
Ted Kremenekd9435bf2008-02-12 19:49:57 +00002271}
2272
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002273
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002274void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, ExplodedNode* Pred,
2275 ExplodedNodeSet& Dst, bool asLValue) {
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002276
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002277 switch (U->getOpcode()) {
Mike Stump1eb44332009-09-09 15:08:12 +00002278
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002279 default:
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002280 break;
Mike Stump1eb44332009-09-09 15:08:12 +00002281
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002282 case UnaryOperator::Deref: {
Mike Stump1eb44332009-09-09 15:08:12 +00002283
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002284 Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002285 ExplodedNodeSet Tmp;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002286 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002287
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002288 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +00002289
Ted Kremeneka8538d92009-02-13 01:45:31 +00002290 const GRState* state = GetState(*I);
Ted Kremenek3ff12592009-06-19 17:10:32 +00002291 SVal location = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00002292
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002293 if (asLValue)
Ted Kremenek8e029342009-08-27 22:17:37 +00002294 MakeNode(Dst, U, *I, state->BindExpr(U, location),
Ted Kremenek7090d542009-05-07 18:27:16 +00002295 ProgramPoint::PostLValueKind);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002296 else
Ted Kremeneka8538d92009-02-13 01:45:31 +00002297 EvalLoad(Dst, U, *I, state, location);
Mike Stump1eb44332009-09-09 15:08:12 +00002298 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002299
2300 return;
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002301 }
Mike Stump1eb44332009-09-09 15:08:12 +00002302
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002303 case UnaryOperator::Real: {
Mike Stump1eb44332009-09-09 15:08:12 +00002304
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002305 Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002306 ExplodedNodeSet Tmp;
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002307 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002308
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002309 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +00002310
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002311 // FIXME: We don't have complex SValues yet.
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002312 if (Ex->getType()->isAnyComplexType()) {
2313 // Just report "Unknown."
2314 Dst.Add(*I);
2315 continue;
2316 }
Mike Stump1eb44332009-09-09 15:08:12 +00002317
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002318 // For all other types, UnaryOperator::Real is an identity operation.
2319 assert (U->getType() == Ex->getType());
Ted Kremeneka8538d92009-02-13 01:45:31 +00002320 const GRState* state = GetState(*I);
Ted Kremenek8e029342009-08-27 22:17:37 +00002321 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex)));
Mike Stump1eb44332009-09-09 15:08:12 +00002322 }
2323
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002324 return;
2325 }
Mike Stump1eb44332009-09-09 15:08:12 +00002326
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002327 case UnaryOperator::Imag: {
Mike Stump1eb44332009-09-09 15:08:12 +00002328
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002329 Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002330 ExplodedNodeSet Tmp;
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002331 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002332
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002333 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002334 // FIXME: We don't have complex SValues yet.
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002335 if (Ex->getType()->isAnyComplexType()) {
2336 // Just report "Unknown."
2337 Dst.Add(*I);
2338 continue;
2339 }
Mike Stump1eb44332009-09-09 15:08:12 +00002340
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002341 // For all other types, UnaryOperator::Float returns 0.
2342 assert (Ex->getType()->isIntegerType());
Ted Kremeneka8538d92009-02-13 01:45:31 +00002343 const GRState* state = GetState(*I);
Zhongxing Xud91ee272009-06-23 09:02:15 +00002344 SVal X = ValMgr.makeZeroVal(Ex->getType());
Ted Kremenek8e029342009-08-27 22:17:37 +00002345 MakeNode(Dst, U, *I, state->BindExpr(U, X));
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002346 }
Mike Stump1eb44332009-09-09 15:08:12 +00002347
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002348 return;
2349 }
Mike Stump1eb44332009-09-09 15:08:12 +00002350
Ted Kremeneke2b57442009-09-15 00:40:32 +00002351 case UnaryOperator::OffsetOf: {
Ted Kremenekaab7efe2009-09-15 04:19:09 +00002352 Expr::EvalResult Res;
2353 if (U->Evaluate(Res, getContext()) && Res.Val.isInt()) {
2354 const APSInt &IV = Res.Val.getInt();
2355 assert(IV.getBitWidth() == getContext().getTypeSize(U->getType()));
2356 assert(U->getType()->isIntegerType());
2357 assert(IV.isSigned() == U->getType()->isSignedIntegerType());
2358 SVal X = ValMgr.makeIntVal(IV);
2359 MakeNode(Dst, U, Pred, GetState(Pred)->BindExpr(U, X));
2360 return;
2361 }
2362 // FIXME: Handle the case where __builtin_offsetof is not a constant.
2363 Dst.Add(Pred);
Ted Kremeneka084bb62008-04-30 21:45:55 +00002364 return;
Ted Kremeneke2b57442009-09-15 00:40:32 +00002365 }
Mike Stump1eb44332009-09-09 15:08:12 +00002366
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002367 case UnaryOperator::Plus: assert (!asLValue); // FALL-THROUGH.
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002368 case UnaryOperator::Extension: {
Mike Stump1eb44332009-09-09 15:08:12 +00002369
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002370 // Unary "+" is a no-op, similar to a parentheses. We still have places
2371 // where it may be a block-level expression, so we need to
2372 // generate an extra node that just propagates the value of the
2373 // subexpression.
2374
2375 Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002376 ExplodedNodeSet Tmp;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002377 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002378
2379 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002380 const GRState* state = GetState(*I);
Ted Kremenek8e029342009-08-27 22:17:37 +00002381 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex)));
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002382 }
Mike Stump1eb44332009-09-09 15:08:12 +00002383
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002384 return;
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002385 }
Mike Stump1eb44332009-09-09 15:08:12 +00002386
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002387 case UnaryOperator::AddrOf: {
Mike Stump1eb44332009-09-09 15:08:12 +00002388
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002389 assert(!asLValue);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002390 Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002391 ExplodedNodeSet Tmp;
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002392 VisitLValue(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002393
2394 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002395 const GRState* state = GetState(*I);
Ted Kremenek3ff12592009-06-19 17:10:32 +00002396 SVal V = state->getSVal(Ex);
Ted Kremenek8e029342009-08-27 22:17:37 +00002397 state = state->BindExpr(U, V);
Ted Kremeneka8538d92009-02-13 01:45:31 +00002398 MakeNode(Dst, U, *I, state);
Ted Kremenek89063af2008-02-21 19:15:37 +00002399 }
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002400
Mike Stump1eb44332009-09-09 15:08:12 +00002401 return;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002402 }
Mike Stump1eb44332009-09-09 15:08:12 +00002403
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002404 case UnaryOperator::LNot:
2405 case UnaryOperator::Minus:
2406 case UnaryOperator::Not: {
Mike Stump1eb44332009-09-09 15:08:12 +00002407
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002408 assert (!asLValue);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002409 Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002410 ExplodedNodeSet Tmp;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002411 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002412
2413 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002414 const GRState* state = GetState(*I);
Mike Stump1eb44332009-09-09 15:08:12 +00002415
Ted Kremenek855cd902008-09-30 05:32:44 +00002416 // Get the value of the subexpression.
Ted Kremenek3ff12592009-06-19 17:10:32 +00002417 SVal V = state->getSVal(Ex);
Ted Kremenek855cd902008-09-30 05:32:44 +00002418
Ted Kremeneke04a5cb2008-11-15 00:20:05 +00002419 if (V.isUnknownOrUndef()) {
Ted Kremenek8e029342009-08-27 22:17:37 +00002420 MakeNode(Dst, U, *I, state->BindExpr(U, V));
Ted Kremeneke04a5cb2008-11-15 00:20:05 +00002421 continue;
2422 }
Mike Stump1eb44332009-09-09 15:08:12 +00002423
Ted Kremenek60595da2008-11-15 04:01:56 +00002424// QualType DstT = getContext().getCanonicalType(U->getType());
2425// QualType SrcT = getContext().getCanonicalType(Ex->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00002426//
Ted Kremenek60595da2008-11-15 04:01:56 +00002427// if (DstT != SrcT) // Perform promotions.
Mike Stump1eb44332009-09-09 15:08:12 +00002428// V = EvalCast(V, DstT);
2429//
Ted Kremenek60595da2008-11-15 04:01:56 +00002430// if (V.isUnknownOrUndef()) {
2431// MakeNode(Dst, U, *I, BindExpr(St, U, V));
2432// continue;
2433// }
Mike Stump1eb44332009-09-09 15:08:12 +00002434
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002435 switch (U->getOpcode()) {
2436 default:
2437 assert(false && "Invalid Opcode.");
2438 break;
Mike Stump1eb44332009-09-09 15:08:12 +00002439
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002440 case UnaryOperator::Not:
Ted Kremenek60a6e0c2008-10-01 00:21:14 +00002441 // FIXME: Do we need to handle promotions?
Ted Kremenek8e029342009-08-27 22:17:37 +00002442 state = state->BindExpr(U, EvalComplement(cast<NonLoc>(V)));
Mike Stump1eb44332009-09-09 15:08:12 +00002443 break;
2444
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002445 case UnaryOperator::Minus:
Ted Kremenek60a6e0c2008-10-01 00:21:14 +00002446 // FIXME: Do we need to handle promotions?
Ted Kremenek8e029342009-08-27 22:17:37 +00002447 state = state->BindExpr(U, EvalMinus(cast<NonLoc>(V)));
Mike Stump1eb44332009-09-09 15:08:12 +00002448 break;
2449
2450 case UnaryOperator::LNot:
2451
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002452 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
2453 //
2454 // Note: technically we do "E == 0", but this is the same in the
2455 // transfer functions as "0 == E".
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002456 SVal Result;
Mike Stump1eb44332009-09-09 15:08:12 +00002457
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002458 if (isa<Loc>(V)) {
Zhongxing Xud91ee272009-06-23 09:02:15 +00002459 Loc X = ValMgr.makeNull();
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002460 Result = EvalBinOp(state, BinaryOperator::EQ, cast<Loc>(V), X,
2461 U->getType());
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002462 }
2463 else {
Ted Kremenek60595da2008-11-15 04:01:56 +00002464 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType()));
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +00002465 Result = EvalBinOp(state, BinaryOperator::EQ, cast<NonLoc>(V), X,
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002466 U->getType());
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002467 }
Mike Stump1eb44332009-09-09 15:08:12 +00002468
Ted Kremenek8e029342009-08-27 22:17:37 +00002469 state = state->BindExpr(U, Result);
Mike Stump1eb44332009-09-09 15:08:12 +00002470
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002471 break;
2472 }
Mike Stump1eb44332009-09-09 15:08:12 +00002473
Ted Kremeneka8538d92009-02-13 01:45:31 +00002474 MakeNode(Dst, U, *I, state);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002475 }
Mike Stump1eb44332009-09-09 15:08:12 +00002476
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002477 return;
2478 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002479 }
2480
2481 // Handle ++ and -- (both pre- and post-increment).
2482
2483 assert (U->isIncrementDecrementOp());
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002484 ExplodedNodeSet Tmp;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002485 Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002486 VisitLValue(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002487
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002488 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +00002489
Ted Kremeneka8538d92009-02-13 01:45:31 +00002490 const GRState* state = GetState(*I);
Ted Kremenek3ff12592009-06-19 17:10:32 +00002491 SVal V1 = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00002492
2493 // Perform a load.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002494 ExplodedNodeSet Tmp2;
Ted Kremeneka8538d92009-02-13 01:45:31 +00002495 EvalLoad(Tmp2, Ex, *I, state, V1);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002496
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002497 for (ExplodedNodeSet::iterator I2 = Tmp2.begin(), E2 = Tmp2.end(); I2!=E2; ++I2) {
Mike Stump1eb44332009-09-09 15:08:12 +00002498
Ted Kremeneka8538d92009-02-13 01:45:31 +00002499 state = GetState(*I2);
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002500 SVal V2_untested = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00002501
2502 // Propagate unknown and undefined values.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002503 if (V2_untested.isUnknownOrUndef()) {
2504 MakeNode(Dst, U, *I2, state->BindExpr(U, V2_untested));
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002505 continue;
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002506 }
2507 DefinedSVal V2 = cast<DefinedSVal>(V2_untested);
Mike Stump1eb44332009-09-09 15:08:12 +00002508
2509 // Handle all other values.
Ted Kremenek50d0ac22008-02-15 22:09:30 +00002510 BinaryOperator::Opcode Op = U->isIncrementOp() ? BinaryOperator::Add
2511 : BinaryOperator::Sub;
Ted Kremenek21028dd2009-03-11 03:54:24 +00002512
Zhongxing Xua52ad4e2009-08-05 02:51:59 +00002513 // If the UnaryOperator has non-location type, use its type to create the
2514 // constant value. If the UnaryOperator has location type, create the
2515 // constant with int type and pointer width.
2516 SVal RHS;
2517
2518 if (U->getType()->isAnyPointerType())
2519 RHS = ValMgr.makeIntValWithPtrWidth(1, false);
2520 else
2521 RHS = ValMgr.makeIntVal(1, U->getType());
2522
Mike Stump1eb44332009-09-09 15:08:12 +00002523 SVal Result = EvalBinOp(state, Op, V2, RHS, U->getType());
2524
Ted Kremenekbb9b2712009-03-20 20:10:45 +00002525 // Conjure a new symbol if necessary to recover precision.
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002526 if (Result.isUnknown() || !getConstraintManager().canReasonAbout(Result)){
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002527 DefinedOrUnknownSVal SymVal =
Ted Kremenek87806792009-09-27 20:45:21 +00002528 ValMgr.getConjuredSymbolVal(NULL, Ex,
2529 Builder->getCurrentBlockCount());
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002530 Result = SymVal;
Mike Stump1eb44332009-09-09 15:08:12 +00002531
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002532 // If the value is a location, ++/-- should always preserve
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002533 // non-nullness. Check if the original value was non-null, and if so
Mike Stump1eb44332009-09-09 15:08:12 +00002534 // propagate that constraint.
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002535 if (Loc::IsLocType(U->getType())) {
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002536 DefinedOrUnknownSVal Constraint =
2537 SVator.EvalEQ(state, V2, ValMgr.makeZeroVal(U->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00002538
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002539 if (!state->Assume(Constraint, true)) {
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002540 // It isn't feasible for the original value to be null.
2541 // Propagate this constraint.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002542 Constraint = SVator.EvalEQ(state, SymVal,
2543 ValMgr.makeZeroVal(U->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00002544
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002545
2546 state = state->Assume(Constraint, false);
Ted Kremeneka591bc02009-06-18 22:57:13 +00002547 assert(state);
Mike Stump1eb44332009-09-09 15:08:12 +00002548 }
2549 }
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002550 }
Mike Stump1eb44332009-09-09 15:08:12 +00002551
Ted Kremenek8e029342009-08-27 22:17:37 +00002552 state = state->BindExpr(U, U->isPostfix() ? V2 : Result);
Ted Kremenekcf78b6a2008-02-06 22:50:25 +00002553
Mike Stump1eb44332009-09-09 15:08:12 +00002554 // Perform the store.
Ted Kremenek50ecd152009-11-05 00:42:23 +00002555 EvalStore(Dst, NULL, U, *I2, state, V1, Result);
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00002556 }
Ted Kremenek469ecbd2008-04-21 23:43:38 +00002557 }
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00002558}
2559
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002560void GRExprEngine::VisitAsmStmt(AsmStmt* A, ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002561 VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst);
Mike Stump1eb44332009-09-09 15:08:12 +00002562}
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002563
2564void GRExprEngine::VisitAsmStmtHelperOutputs(AsmStmt* A,
2565 AsmStmt::outputs_iterator I,
2566 AsmStmt::outputs_iterator E,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002567 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002568 if (I == E) {
2569 VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst);
2570 return;
2571 }
Mike Stump1eb44332009-09-09 15:08:12 +00002572
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002573 ExplodedNodeSet Tmp;
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002574 VisitLValue(*I, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002575
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002576 ++I;
Mike Stump1eb44332009-09-09 15:08:12 +00002577
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002578 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI != NE; ++NI)
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002579 VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst);
2580}
2581
2582void GRExprEngine::VisitAsmStmtHelperInputs(AsmStmt* A,
2583 AsmStmt::inputs_iterator I,
2584 AsmStmt::inputs_iterator E,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002585 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002586 if (I == E) {
Mike Stump1eb44332009-09-09 15:08:12 +00002587
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002588 // We have processed both the inputs and the outputs. All of the outputs
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002589 // should evaluate to Locs. Nuke all of their values.
Mike Stump1eb44332009-09-09 15:08:12 +00002590
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002591 // FIXME: Some day in the future it would be nice to allow a "plug-in"
2592 // which interprets the inline asm and stores proper results in the
2593 // outputs.
Mike Stump1eb44332009-09-09 15:08:12 +00002594
Ted Kremeneka8538d92009-02-13 01:45:31 +00002595 const GRState* state = GetState(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00002596
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002597 for (AsmStmt::outputs_iterator OI = A->begin_outputs(),
2598 OE = A->end_outputs(); OI != OE; ++OI) {
Mike Stump1eb44332009-09-09 15:08:12 +00002599
2600 SVal X = state->getSVal(*OI);
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002601 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.
Mike Stump1eb44332009-09-09 15:08:12 +00002602
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002603 if (isa<Loc>(X))
Ted Kremenek3ff12592009-06-19 17:10:32 +00002604 state = state->bindLoc(cast<Loc>(X), UnknownVal());
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002605 }
Mike Stump1eb44332009-09-09 15:08:12 +00002606
Ted Kremeneka8538d92009-02-13 01:45:31 +00002607 MakeNode(Dst, A, Pred, state);
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002608 return;
2609 }
Mike Stump1eb44332009-09-09 15:08:12 +00002610
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002611 ExplodedNodeSet Tmp;
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002612 Visit(*I, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002613
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002614 ++I;
Mike Stump1eb44332009-09-09 15:08:12 +00002615
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00002616 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI)
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002617 VisitAsmStmtHelperInputs(A, I, E, *NI, Dst);
2618}
2619
Ted Kremenek1053d242009-11-06 02:24:13 +00002620void GRExprEngine::VisitReturnStmt(ReturnStmt *RS, ExplodedNode *Pred,
2621 ExplodedNodeSet &Dst) {
2622
2623 ExplodedNodeSet Src;
2624 if (Expr *RetE = RS->getRetValue()) {
2625 Visit(RetE, Pred, Src);
Ted Kremenek02737ed2008-03-31 15:02:58 +00002626 }
Ted Kremenek1053d242009-11-06 02:24:13 +00002627 else {
2628 Src.Add(Pred);
2629 }
2630
2631 ExplodedNodeSet CheckedSet;
2632 CheckerVisit(RS, CheckedSet, Src, true);
2633
2634 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
2635 I != E; ++I) {
Ted Kremenek6b31e8e2008-04-16 23:05:51 +00002636
Ted Kremenek1053d242009-11-06 02:24:13 +00002637 assert(Builder && "GRStmtNodeBuilder must be defined.");
2638
2639 Pred = *I;
2640 unsigned size = Dst.size();
2641
2642 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
2643 SaveOr OldHasGen(Builder->HasGeneratedNode);
2644
2645 getTF().EvalReturn(Dst, *this, *Builder, RS, Pred);
2646
2647 // Handle the case where no nodes where generated.
2648 if (!Builder->BuildSinks && Dst.size() == size &&
2649 !Builder->HasGeneratedNode)
2650 MakeNode(Dst, RS, Pred, GetState(Pred));
Ted Kremenek5917d782008-11-21 00:27:44 +00002651 }
Ted Kremenek02737ed2008-03-31 15:02:58 +00002652}
Ted Kremenek55deb972008-03-25 00:34:37 +00002653
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002654//===----------------------------------------------------------------------===//
2655// Transfer functions: Binary operators.
2656//===----------------------------------------------------------------------===//
2657
Ted Kremenek4d4dd852008-02-13 17:41:41 +00002658void GRExprEngine::VisitBinaryOperator(BinaryOperator* B,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002659 ExplodedNode* Pred,
Zhongxing Xu662174ca2009-10-30 07:19:39 +00002660 ExplodedNodeSet& Dst, bool asLValue) {
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002661
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002662 ExplodedNodeSet Tmp1;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002663 Expr* LHS = B->getLHS()->IgnoreParens();
2664 Expr* RHS = B->getRHS()->IgnoreParens();
Mike Stump1eb44332009-09-09 15:08:12 +00002665
Fariborz Jahanian09105f52009-08-20 17:02:02 +00002666 // FIXME: Add proper support for ObjCImplicitSetterGetterRefExpr.
2667 if (isa<ObjCImplicitSetterGetterRefExpr>(LHS)) {
Mike Stump1eb44332009-09-09 15:08:12 +00002668 Visit(RHS, Pred, Dst);
Ted Kremenek759623e2008-12-06 02:39:30 +00002669 return;
2670 }
Mike Stump1eb44332009-09-09 15:08:12 +00002671
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00002672 if (B->isAssignmentOp())
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00002673 VisitLValue(LHS, Pred, Tmp1);
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00002674 else
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002675 Visit(LHS, Pred, Tmp1);
Ted Kremenekcb448ca2008-01-16 00:53:15 +00002676
Zhongxing Xu668399b2009-11-24 08:24:26 +00002677 ExplodedNodeSet Tmp3;
2678
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00002679 for (ExplodedNodeSet::iterator I1=Tmp1.begin(), E1=Tmp1.end(); I1!=E1; ++I1) {
Ted Kremenek3ff12592009-06-19 17:10:32 +00002680 SVal LeftV = (*I1)->getState()->getSVal(LHS);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002681 ExplodedNodeSet Tmp2;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002682 Visit(RHS, *I1, Tmp2);
Zhongxing Xu6403b572009-09-02 13:26:26 +00002683
2684 ExplodedNodeSet CheckedSet;
2685 CheckerVisit(B, CheckedSet, Tmp2, true);
Mike Stump1eb44332009-09-09 15:08:12 +00002686
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002687 // With both the LHS and RHS evaluated, process the operation itself.
Mike Stump1eb44332009-09-09 15:08:12 +00002688
2689 for (ExplodedNodeSet::iterator I2=CheckedSet.begin(), E2=CheckedSet.end();
Zhongxing Xu6403b572009-09-02 13:26:26 +00002690 I2 != E2; ++I2) {
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002691
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002692 const GRState *state = GetState(*I2);
2693 const GRState *OldSt = state;
Ted Kremenek3ff12592009-06-19 17:10:32 +00002694 SVal RightV = state->getSVal(RHS);
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002695
Ted Kremenekcf78b6a2008-02-06 22:50:25 +00002696 BinaryOperator::Opcode Op = B->getOpcode();
Mike Stump1eb44332009-09-09 15:08:12 +00002697
Zhongxing Xu73af2d52009-10-21 11:42:22 +00002698 if (Op == BinaryOperator::Assign) {
2699 // EXPERIMENTAL: "Conjured" symbols.
2700 // FIXME: Handle structs.
2701 QualType T = RHS->getType();
2702
2703 if ((RightV.isUnknown()||!getConstraintManager().canReasonAbout(RightV))
2704 && (Loc::IsLocType(T) || (T->isScalarType()&&T->isIntegerType()))) {
2705 unsigned Count = Builder->getCurrentBlockCount();
2706 RightV = ValMgr.getConjuredSymbolVal(NULL, B->getRHS(), Count);
2707 }
Zhongxing Xu662174ca2009-10-30 07:19:39 +00002708
Ted Kremenek12e6f032009-10-30 22:01:29 +00002709 SVal ExprVal = asLValue ? LeftV : RightV;
Zhongxing Xu662174ca2009-10-30 07:19:39 +00002710
Zhongxing Xu73af2d52009-10-21 11:42:22 +00002711 // Simulate the effects of a "store": bind the value of the RHS
2712 // to the L-Value represented by the LHS.
Zhongxing Xu668399b2009-11-24 08:24:26 +00002713 EvalStore(Tmp3, B, LHS, *I2, state->BindExpr(B, ExprVal), LeftV, RightV);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00002714 continue;
2715 }
2716
2717 if (!B->isAssignmentOp()) {
2718 // Process non-assignments except commas or short-circuited
2719 // logical expressions (LAnd and LOr).
2720 SVal Result = EvalBinOp(state, Op, LeftV, RightV, B->getType());
2721
2722 if (Result.isUnknown()) {
2723 if (OldSt != state) {
2724 // Generate a new node if we have already created a new state.
Zhongxing Xu668399b2009-11-24 08:24:26 +00002725 MakeNode(Tmp3, B, *I2, state);
Ted Kremenek361fa8e2008-03-12 21:45:47 +00002726 }
Zhongxing Xu73af2d52009-10-21 11:42:22 +00002727 else
Zhongxing Xu668399b2009-11-24 08:24:26 +00002728 Tmp3.Add(*I2);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00002729
Ted Kremeneke38718e2008-04-16 18:21:25 +00002730 continue;
Ted Kremenekab2b8c52008-01-23 19:59:44 +00002731 }
Zhongxing Xu73af2d52009-10-21 11:42:22 +00002732
2733 state = state->BindExpr(B, Result);
2734
Zhongxing Xu668399b2009-11-24 08:24:26 +00002735 MakeNode(Tmp3, B, *I2, state);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00002736 continue;
Ted Kremenekab2b8c52008-01-23 19:59:44 +00002737 }
Mike Stump1eb44332009-09-09 15:08:12 +00002738
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002739 assert (B->isCompoundAssignmentOp());
2740
Ted Kremenekcad29962009-02-07 00:52:24 +00002741 switch (Op) {
2742 default:
2743 assert(0 && "Invalid opcode for compound assignment.");
2744 case BinaryOperator::MulAssign: Op = BinaryOperator::Mul; break;
2745 case BinaryOperator::DivAssign: Op = BinaryOperator::Div; break;
2746 case BinaryOperator::RemAssign: Op = BinaryOperator::Rem; break;
2747 case BinaryOperator::AddAssign: Op = BinaryOperator::Add; break;
2748 case BinaryOperator::SubAssign: Op = BinaryOperator::Sub; break;
2749 case BinaryOperator::ShlAssign: Op = BinaryOperator::Shl; break;
2750 case BinaryOperator::ShrAssign: Op = BinaryOperator::Shr; break;
2751 case BinaryOperator::AndAssign: Op = BinaryOperator::And; break;
2752 case BinaryOperator::XorAssign: Op = BinaryOperator::Xor; break;
2753 case BinaryOperator::OrAssign: Op = BinaryOperator::Or; break;
Ted Kremenek934e3e92008-10-27 23:02:39 +00002754 }
Mike Stump1eb44332009-09-09 15:08:12 +00002755
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002756 // Perform a load (the LHS). This performs the checks for
2757 // null dereferences, and so on.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002758 ExplodedNodeSet Tmp3;
Ted Kremenek3ff12592009-06-19 17:10:32 +00002759 SVal location = state->getSVal(LHS);
Ted Kremeneka8538d92009-02-13 01:45:31 +00002760 EvalLoad(Tmp3, LHS, *I2, state, location);
Mike Stump1eb44332009-09-09 15:08:12 +00002761
2762 for (ExplodedNodeSet::iterator I3=Tmp3.begin(), E3=Tmp3.end(); I3!=E3;
Zhongxing Xu6403b572009-09-02 13:26:26 +00002763 ++I3) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002764 state = GetState(*I3);
Ted Kremenek3ff12592009-06-19 17:10:32 +00002765 SVal V = state->getSVal(LHS);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002766
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002767 // Get the computation type.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002768 QualType CTy =
2769 cast<CompoundAssignOperator>(B)->getComputationResultType();
Ted Kremenek60595da2008-11-15 04:01:56 +00002770 CTy = getContext().getCanonicalType(CTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00002771
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002772 QualType CLHSTy =
2773 cast<CompoundAssignOperator>(B)->getComputationLHSType();
2774 CLHSTy = getContext().getCanonicalType(CLHSTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00002775
Ted Kremenek60595da2008-11-15 04:01:56 +00002776 QualType LTy = getContext().getCanonicalType(LHS->getType());
2777 QualType RTy = getContext().getCanonicalType(RHS->getType());
Eli Friedmanab3a8522009-03-28 01:22:36 +00002778
2779 // Promote LHS.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002780 llvm::tie(state, V) = SVator.EvalCast(V, state, CLHSTy, LTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00002781
Mike Stump1eb44332009-09-09 15:08:12 +00002782 // Compute the result of the operation.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002783 SVal Result;
2784 llvm::tie(state, Result) = SVator.EvalCast(EvalBinOp(state, Op, V,
2785 RightV, CTy),
2786 state, B->getType(), CTy);
Mike Stump1eb44332009-09-09 15:08:12 +00002787
Ted Kremenek9ff267d2008-10-20 23:13:25 +00002788 // EXPERIMENTAL: "Conjured" symbols.
2789 // FIXME: Handle structs.
Mike Stump1eb44332009-09-09 15:08:12 +00002790
Ted Kremenek60595da2008-11-15 04:01:56 +00002791 SVal LHSVal;
Mike Stump1eb44332009-09-09 15:08:12 +00002792
2793 if ((Result.isUnknown() ||
Ted Kremenek276c6ac2009-03-11 02:24:48 +00002794 !getConstraintManager().canReasonAbout(Result))
Mike Stump1eb44332009-09-09 15:08:12 +00002795 && (Loc::IsLocType(CTy)
Ted Kremenek276c6ac2009-03-11 02:24:48 +00002796 || (CTy->isScalarType() && CTy->isIntegerType()))) {
Mike Stump1eb44332009-09-09 15:08:12 +00002797
Ted Kremenek9ff267d2008-10-20 23:13:25 +00002798 unsigned Count = Builder->getCurrentBlockCount();
Mike Stump1eb44332009-09-09 15:08:12 +00002799
Ted Kremenek60595da2008-11-15 04:01:56 +00002800 // The symbolic value is actually for the type of the left-hand side
2801 // expression, not the computation type, as this is the value the
2802 // LValue on the LHS will bind to.
Ted Kremenek87806792009-09-27 20:45:21 +00002803 LHSVal = ValMgr.getConjuredSymbolVal(NULL, B->getRHS(), LTy, Count);
Mike Stump1eb44332009-09-09 15:08:12 +00002804
Zhongxing Xu1c0c2332008-11-23 05:52:28 +00002805 // However, we need to convert the symbol to the computation type.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002806 llvm::tie(state, Result) = SVator.EvalCast(LHSVal, state, CTy, LTy);
Ted Kremenek9ff267d2008-10-20 23:13:25 +00002807 }
Ted Kremenek60595da2008-11-15 04:01:56 +00002808 else {
2809 // The left-hand side may bind to a different value then the
2810 // computation type.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002811 llvm::tie(state, LHSVal) = SVator.EvalCast(Result, state, LTy, CTy);
Ted Kremenek60595da2008-11-15 04:01:56 +00002812 }
Mike Stump1eb44332009-09-09 15:08:12 +00002813
Zhongxing Xu668399b2009-11-24 08:24:26 +00002814 EvalStore(Tmp3, B, LHS, *I3, state->BindExpr(B, Result),
Zhongxing Xu5032ffe2009-08-25 06:51:30 +00002815 location, LHSVal);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002816 }
Ted Kremenekcb448ca2008-01-16 00:53:15 +00002817 }
Ted Kremenekd27f8162008-01-15 23:55:06 +00002818 }
Zhongxing Xu668399b2009-11-24 08:24:26 +00002819
2820 CheckerVisit(B, Dst, Tmp3, false);
Ted Kremenekd27f8162008-01-15 23:55:06 +00002821}
Ted Kremenekee985462008-01-16 18:18:48 +00002822
2823//===----------------------------------------------------------------------===//
Ted Kremenek094bef52009-10-30 17:47:32 +00002824// Checker registration/lookup.
2825//===----------------------------------------------------------------------===//
2826
2827Checker *GRExprEngine::lookupChecker(void *tag) const {
Jeffrey Yasskin3958b502009-11-10 01:17:45 +00002828 CheckerMap::const_iterator I = CheckerM.find(tag);
Ted Kremenek094bef52009-10-30 17:47:32 +00002829 return (I == CheckerM.end()) ? NULL : Checkers[I->second].second;
2830}
2831
2832//===----------------------------------------------------------------------===//
Ted Kremeneke01c9872008-02-14 22:36:46 +00002833// Visualization.
Ted Kremenekee985462008-01-16 18:18:48 +00002834//===----------------------------------------------------------------------===//
2835
Ted Kremenekaa66a322008-01-16 21:46:15 +00002836#ifndef NDEBUG
Ted Kremenek4d4dd852008-02-13 17:41:41 +00002837static GRExprEngine* GraphPrintCheckerState;
Ted Kremeneke97ca062008-03-07 20:57:30 +00002838static SourceManager* GraphPrintSourceManager;
Ted Kremenek3b4f6702008-01-30 23:24:39 +00002839
Ted Kremenekaa66a322008-01-16 21:46:15 +00002840namespace llvm {
2841template<>
Douglas Gregor47491f82009-11-30 16:08:24 +00002842struct DOTGraphTraits<ExplodedNode*> :
Ted Kremenekaa66a322008-01-16 21:46:15 +00002843 public DefaultDOTGraphTraits {
Tobias Grosser006b0eb2009-11-30 14:16:05 +00002844
2845 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
2846
Zhongxing Xuec9227f2009-10-29 02:09:30 +00002847 // FIXME: Since we do not cache error nodes in GRExprEngine now, this does not
2848 // work.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002849 static std::string getNodeAttributes(const ExplodedNode* N, void*) {
Mike Stump1eb44332009-09-09 15:08:12 +00002850
Ted Kremenek10f51e82009-11-11 20:16:36 +00002851#if 0
2852 // FIXME: Replace with a general scheme to tell if the node is
2853 // an error node.
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00002854 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
Ted Kremenek9dca0622008-02-19 00:22:37 +00002855 GraphPrintCheckerState->isExplicitNullDeref(N) ||
Ted Kremenek4a4e5242008-02-28 09:25:22 +00002856 GraphPrintCheckerState->isUndefDeref(N) ||
2857 GraphPrintCheckerState->isUndefStore(N) ||
2858 GraphPrintCheckerState->isUndefControlFlow(N) ||
Ted Kremenek5e03fcb2008-02-29 23:14:48 +00002859 GraphPrintCheckerState->isUndefResult(N) ||
Ted Kremenek2ded35a2008-02-29 23:53:11 +00002860 GraphPrintCheckerState->isBadCall(N) ||
2861 GraphPrintCheckerState->isUndefArg(N))
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00002862 return "color=\"red\",style=\"filled\"";
Mike Stump1eb44332009-09-09 15:08:12 +00002863
Ted Kremenek8cc13ea2008-02-28 20:32:03 +00002864 if (GraphPrintCheckerState->isNoReturnCall(N))
2865 return "color=\"blue\",style=\"filled\"";
Zhongxing Xu2055eff2009-11-24 07:06:39 +00002866#endif
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00002867 return "";
2868 }
Mike Stump1eb44332009-09-09 15:08:12 +00002869
Tobias Grosser006b0eb2009-11-30 14:16:05 +00002870 static std::string getNodeLabel(const ExplodedNode* N, void*){
Mike Stump1eb44332009-09-09 15:08:12 +00002871
Ted Kremenek53ba0b62009-06-24 23:06:47 +00002872 std::string sbuf;
2873 llvm::raw_string_ostream Out(sbuf);
Ted Kremenek803c9ed2008-01-23 22:30:44 +00002874
2875 // Program Location.
Ted Kremenekaa66a322008-01-16 21:46:15 +00002876 ProgramPoint Loc = N->getLocation();
Mike Stump1eb44332009-09-09 15:08:12 +00002877
Ted Kremenekaa66a322008-01-16 21:46:15 +00002878 switch (Loc.getKind()) {
2879 case ProgramPoint::BlockEntranceKind:
Mike Stump1eb44332009-09-09 15:08:12 +00002880 Out << "Block Entrance: B"
Ted Kremenekaa66a322008-01-16 21:46:15 +00002881 << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
2882 break;
Mike Stump1eb44332009-09-09 15:08:12 +00002883
Ted Kremenekaa66a322008-01-16 21:46:15 +00002884 case ProgramPoint::BlockExitKind:
2885 assert (false);
2886 break;
Mike Stump1eb44332009-09-09 15:08:12 +00002887
Ted Kremenekaa66a322008-01-16 21:46:15 +00002888 default: {
Ted Kremenek5f85e172009-07-22 22:35:28 +00002889 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) {
2890 const Stmt* S = L->getStmt();
Ted Kremenek8c354752008-12-16 22:02:27 +00002891 SourceLocation SLoc = S->getLocStart();
2892
Mike Stump1eb44332009-09-09 15:08:12 +00002893 Out << S->getStmtClassName() << ' ' << (void*) S << ' ';
Chris Lattnere4f21422009-06-30 01:26:17 +00002894 LangOptions LO; // FIXME.
2895 S->printPretty(Out, 0, PrintingPolicy(LO));
Mike Stump1eb44332009-09-09 15:08:12 +00002896
2897 if (SLoc.isFileID()) {
Ted Kremenek8c354752008-12-16 22:02:27 +00002898 Out << "\\lline="
Chris Lattner7da5aea2009-02-04 00:55:58 +00002899 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc)
2900 << " col="
2901 << GraphPrintSourceManager->getInstantiationColumnNumber(SLoc)
2902 << "\\l";
Ted Kremenek8c354752008-12-16 22:02:27 +00002903 }
Mike Stump1eb44332009-09-09 15:08:12 +00002904
Ted Kremenek5f85e172009-07-22 22:35:28 +00002905 if (isa<PreStmt>(Loc))
Mike Stump1eb44332009-09-09 15:08:12 +00002906 Out << "\\lPreStmt\\l;";
Ted Kremenek5f85e172009-07-22 22:35:28 +00002907 else if (isa<PostLoad>(Loc))
Ted Kremenek7090d542009-05-07 18:27:16 +00002908 Out << "\\lPostLoad\\l;";
2909 else if (isa<PostStore>(Loc))
2910 Out << "\\lPostStore\\l";
2911 else if (isa<PostLValue>(Loc))
2912 Out << "\\lPostLValue\\l";
Mike Stump1eb44332009-09-09 15:08:12 +00002913
Ted Kremenek10f51e82009-11-11 20:16:36 +00002914#if 0
2915 // FIXME: Replace with a general scheme to determine
2916 // the name of the check.
Ted Kremenek8c354752008-12-16 22:02:27 +00002917 if (GraphPrintCheckerState->isImplicitNullDeref(N))
2918 Out << "\\|Implicit-Null Dereference.\\l";
2919 else if (GraphPrintCheckerState->isExplicitNullDeref(N))
2920 Out << "\\|Explicit-Null Dereference.\\l";
2921 else if (GraphPrintCheckerState->isUndefDeref(N))
2922 Out << "\\|Dereference of undefialied value.\\l";
2923 else if (GraphPrintCheckerState->isUndefStore(N))
2924 Out << "\\|Store to Undefined Loc.";
Ted Kremenek8c354752008-12-16 22:02:27 +00002925 else if (GraphPrintCheckerState->isUndefResult(N))
2926 Out << "\\|Result of operation is undefined.";
2927 else if (GraphPrintCheckerState->isNoReturnCall(N))
2928 Out << "\\|Call to function marked \"noreturn\".";
2929 else if (GraphPrintCheckerState->isBadCall(N))
2930 Out << "\\|Call to NULL/Undefined.";
2931 else if (GraphPrintCheckerState->isUndefArg(N))
2932 Out << "\\|Argument in call is undefined";
Ted Kremenek10f51e82009-11-11 20:16:36 +00002933#endif
Mike Stump1eb44332009-09-09 15:08:12 +00002934
Ted Kremenek8c354752008-12-16 22:02:27 +00002935 break;
2936 }
2937
Ted Kremenekaa66a322008-01-16 21:46:15 +00002938 const BlockEdge& E = cast<BlockEdge>(Loc);
2939 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
2940 << E.getDst()->getBlockID() << ')';
Mike Stump1eb44332009-09-09 15:08:12 +00002941
Ted Kremenekb38911f2008-01-30 23:03:39 +00002942 if (Stmt* T = E.getSrc()->getTerminator()) {
Mike Stump1eb44332009-09-09 15:08:12 +00002943
Ted Kremeneke97ca062008-03-07 20:57:30 +00002944 SourceLocation SLoc = T->getLocStart();
Mike Stump1eb44332009-09-09 15:08:12 +00002945
Ted Kremenekb38911f2008-01-30 23:03:39 +00002946 Out << "\\|Terminator: ";
Chris Lattnere4f21422009-06-30 01:26:17 +00002947 LangOptions LO; // FIXME.
2948 E.getSrc()->printTerminator(Out, LO);
Mike Stump1eb44332009-09-09 15:08:12 +00002949
Ted Kremenek9b5551d2008-03-09 03:30:59 +00002950 if (SLoc.isFileID()) {
2951 Out << "\\lline="
Chris Lattner7da5aea2009-02-04 00:55:58 +00002952 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc)
2953 << " col="
2954 << GraphPrintSourceManager->getInstantiationColumnNumber(SLoc);
Ted Kremenek9b5551d2008-03-09 03:30:59 +00002955 }
Mike Stump1eb44332009-09-09 15:08:12 +00002956
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00002957 if (isa<SwitchStmt>(T)) {
2958 Stmt* Label = E.getDst()->getLabel();
Mike Stump1eb44332009-09-09 15:08:12 +00002959
2960 if (Label) {
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00002961 if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) {
2962 Out << "\\lcase ";
Chris Lattnere4f21422009-06-30 01:26:17 +00002963 LangOptions LO; // FIXME.
2964 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
Mike Stump1eb44332009-09-09 15:08:12 +00002965
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00002966 if (Stmt* RHS = C->getRHS()) {
2967 Out << " .. ";
Chris Lattnere4f21422009-06-30 01:26:17 +00002968 RHS->printPretty(Out, 0, PrintingPolicy(LO));
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00002969 }
Mike Stump1eb44332009-09-09 15:08:12 +00002970
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00002971 Out << ":";
2972 }
2973 else {
2974 assert (isa<DefaultStmt>(Label));
2975 Out << "\\ldefault:";
2976 }
2977 }
Mike Stump1eb44332009-09-09 15:08:12 +00002978 else
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00002979 Out << "\\l(implicit) default:";
2980 }
2981 else if (isa<IndirectGotoStmt>(T)) {
Ted Kremenekb38911f2008-01-30 23:03:39 +00002982 // FIXME
2983 }
2984 else {
2985 Out << "\\lCondition: ";
2986 if (*E.getSrc()->succ_begin() == E.getDst())
2987 Out << "true";
2988 else
Mike Stump1eb44332009-09-09 15:08:12 +00002989 Out << "false";
Ted Kremenekb38911f2008-01-30 23:03:39 +00002990 }
Mike Stump1eb44332009-09-09 15:08:12 +00002991
Ted Kremenekb38911f2008-01-30 23:03:39 +00002992 Out << "\\l";
2993 }
Mike Stump1eb44332009-09-09 15:08:12 +00002994
Ted Kremenek10f51e82009-11-11 20:16:36 +00002995#if 0
2996 // FIXME: Replace with a general scheme to determine
2997 // the name of the check.
Ted Kremenek4a4e5242008-02-28 09:25:22 +00002998 if (GraphPrintCheckerState->isUndefControlFlow(N)) {
2999 Out << "\\|Control-flow based on\\lUndefined value.\\l";
Ted Kremenek3b4f6702008-01-30 23:24:39 +00003000 }
Ted Kremenek10f51e82009-11-11 20:16:36 +00003001#endif
Ted Kremenekaa66a322008-01-16 21:46:15 +00003002 }
3003 }
Mike Stump1eb44332009-09-09 15:08:12 +00003004
Ted Kremenekaed9b6a2008-02-28 10:21:43 +00003005 Out << "\\|StateID: " << (void*) N->getState() << "\\|";
Ted Kremenek016f52f2008-02-08 21:10:02 +00003006
Ted Kremenekb65be702009-06-18 01:23:53 +00003007 const GRState *state = N->getState();
3008 state->printDOT(Out);
Mike Stump1eb44332009-09-09 15:08:12 +00003009
Ted Kremenek803c9ed2008-01-23 22:30:44 +00003010 Out << "\\l";
Ted Kremenekaa66a322008-01-16 21:46:15 +00003011 return Out.str();
3012 }
3013};
Mike Stump1eb44332009-09-09 15:08:12 +00003014} // end llvm namespace
Ted Kremenekaa66a322008-01-16 21:46:15 +00003015#endif
3016
Ted Kremenekffe0f432008-03-07 22:58:01 +00003017#ifndef NDEBUG
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003018template <typename ITERATOR>
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003019ExplodedNode* GetGraphNode(ITERATOR I) { return *I; }
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003020
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003021template <> ExplodedNode*
3022GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
3023 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003024 return I->first;
3025}
Ted Kremenekffe0f432008-03-07 22:58:01 +00003026#endif
3027
3028void GRExprEngine::ViewGraph(bool trim) {
Mike Stump1eb44332009-09-09 15:08:12 +00003029#ifndef NDEBUG
Ted Kremenekffe0f432008-03-07 22:58:01 +00003030 if (trim) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003031 std::vector<ExplodedNode*> Src;
Ted Kremenek940abcc2009-03-11 01:41:22 +00003032
3033 // Flush any outstanding reports to make sure we cover all the nodes.
3034 // This does not cause them to get displayed.
3035 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
3036 const_cast<BugType*>(*I)->FlushReports(BR);
3037
3038 // Iterate through the reports and get their nodes.
3039 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) {
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00003040 for (BugType::const_iterator I2=(*I)->begin(), E2=(*I)->end();
Mike Stump1eb44332009-09-09 15:08:12 +00003041 I2!=E2; ++I2) {
Ted Kremenek940abcc2009-03-11 01:41:22 +00003042 const BugReportEquivClass& EQ = *I2;
3043 const BugReport &R = **EQ.begin();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003044 ExplodedNode *N = const_cast<ExplodedNode*>(R.getEndNode());
Ted Kremenek940abcc2009-03-11 01:41:22 +00003045 if (N) Src.push_back(N);
3046 }
3047 }
Mike Stump1eb44332009-09-09 15:08:12 +00003048
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003049 ViewGraph(&Src[0], &Src[0]+Src.size());
Ted Kremenekffe0f432008-03-07 22:58:01 +00003050 }
Ted Kremenek493d7a22008-03-11 18:25:33 +00003051 else {
3052 GraphPrintCheckerState = this;
3053 GraphPrintSourceManager = &getContext().getSourceManager();
Ted Kremenekae6814e2008-08-13 21:24:49 +00003054
Ted Kremenekffe0f432008-03-07 22:58:01 +00003055 llvm::ViewGraph(*G.roots_begin(), "GRExprEngine");
Mike Stump1eb44332009-09-09 15:08:12 +00003056
Ted Kremenek493d7a22008-03-11 18:25:33 +00003057 GraphPrintCheckerState = NULL;
3058 GraphPrintSourceManager = NULL;
3059 }
3060#endif
3061}
3062
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003063void GRExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) {
Ted Kremenek493d7a22008-03-11 18:25:33 +00003064#ifndef NDEBUG
3065 GraphPrintCheckerState = this;
3066 GraphPrintSourceManager = &getContext().getSourceManager();
Mike Stump1eb44332009-09-09 15:08:12 +00003067
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003068 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first);
Ted Kremenek493d7a22008-03-11 18:25:33 +00003069
Ted Kremenekcf118d42009-02-04 23:49:09 +00003070 if (!TrimmedG.get())
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +00003071 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
Ted Kremenekcf118d42009-02-04 23:49:09 +00003072 else
Mike Stump1eb44332009-09-09 15:08:12 +00003073 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedGRExprEngine");
3074
Ted Kremenek3b4f6702008-01-30 23:24:39 +00003075 GraphPrintCheckerState = NULL;
Ted Kremeneke97ca062008-03-07 20:57:30 +00003076 GraphPrintSourceManager = NULL;
Ted Kremeneke01c9872008-02-14 22:36:46 +00003077#endif
Ted Kremenekee985462008-01-16 18:18:48 +00003078}