blob: 41a89e7b39d9119892f82925e5d0c6017ea36ed5 [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//===----------------------------------------------------------------------===//
Zhongxing Xu668399b2009-11-24 08:24:26 +000015#include "GRExprEngineInternalChecks.h"
Benjamin Kramer5e2d2c22010-03-27 21:19:47 +000016#include "clang/Checker/BugReporter/BugType.h"
17#include "clang/Checker/PathSensitive/AnalysisManager.h"
Ted Kremenek1309f9a2010-01-25 04:41:41 +000018#include "clang/Checker/PathSensitive/GRExprEngine.h"
19#include "clang/Checker/PathSensitive/GRExprEngineBuilders.h"
20#include "clang/Checker/PathSensitive/Checker.h"
Ken Dyck199c3d62010-01-11 17:06:35 +000021#include "clang/AST/CharUnits.h"
Chris Lattner16f00492009-04-26 01:32:48 +000022#include "clang/AST/ParentMap.h"
23#include "clang/AST/StmtObjC.h"
Zhongxing Xuc5063572010-03-16 13:14:16 +000024#include "clang/AST/DeclCXX.h"
Chris Lattner1b63e4f2009-06-14 01:54:56 +000025#include "clang/Basic/Builtins.h"
Chris Lattner16f00492009-04-26 01:32:48 +000026#include "clang/Basic/SourceManager.h"
Ted Kremeneke97ca062008-03-07 20:57:30 +000027#include "clang/Basic/SourceManager.h"
Ted Kremenek0bed8a12009-03-11 02:41:36 +000028#include "clang/Basic/PrettyStackTrace.h"
Ted Kremeneka95d3752008-09-13 05:16:45 +000029#include "llvm/Support/raw_ostream.h"
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +000030#include "llvm/ADT/ImmutableList.h"
Ted Kremenek4323a572008-07-10 22:03:41 +000031
Ted Kremenek0f5f0592008-02-27 06:07:00 +000032#ifndef NDEBUG
33#include "llvm/Support/GraphWriter.h"
Ted Kremenek0f5f0592008-02-27 06:07:00 +000034#endif
35
Ted Kremenekb387a3f2008-02-14 22:16:04 +000036using namespace clang;
37using llvm::dyn_cast;
Ted Kremenek852274d2009-12-16 03:18:58 +000038using llvm::dyn_cast_or_null;
Ted Kremenekb387a3f2008-02-14 22:16:04 +000039using llvm::cast;
40using llvm::APSInt;
Ted Kremenekab2b8c52008-01-23 19:59:44 +000041
Zhongxing Xu6190ec22010-02-26 15:43:34 +000042namespace {
43 // Trait class for recording returned expression in the state.
44 struct ReturnExpr {
45 static int TagInt;
46 typedef const Stmt *data_type;
47 };
48 int ReturnExpr::TagInt;
49}
50
Ted Kremeneke695e1c2008-04-15 23:06:53 +000051//===----------------------------------------------------------------------===//
Ted Kremenek32c49952009-11-25 21:51:20 +000052// Utility functions.
53//===----------------------------------------------------------------------===//
54
55static inline Selector GetNullarySelector(const char* name, ASTContext& Ctx) {
56 IdentifierInfo* II = &Ctx.Idents.get(name);
57 return Ctx.Selectors.getSelector(0, &II);
58}
59
60//===----------------------------------------------------------------------===//
Ted Kremenek5a5d98b2009-07-22 21:43:51 +000061// Checker worklist routines.
62//===----------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +000063
Zhongxing Xu03509ae2010-07-20 06:22:24 +000064void GRExprEngine::CheckerVisit(const Stmt *S, ExplodedNodeSet &Dst,
Jordy Rose72905cf2010-08-04 07:10:57 +000065 ExplodedNodeSet &Src, CallbackKind Kind) {
Mike Stump1eb44332009-09-09 15:08:12 +000066
Ted Kremenek9e9595b2010-06-25 20:59:31 +000067 // Determine if we already have a cached 'CheckersOrdered' vector
Jordy Rose72905cf2010-08-04 07:10:57 +000068 // specifically tailored for the provided <CallbackKind, Stmt kind>. This
Ted Kremenek9e9595b2010-06-25 20:59:31 +000069 // can reduce the number of checkers actually called.
70 CheckersOrdered *CO = &Checkers;
71 llvm::OwningPtr<CheckersOrdered> NewCO;
Jordy Rose72905cf2010-08-04 07:10:57 +000072
73 // The cache key is made up of the and the callback kind (pre- or post-visit)
74 // and the statement kind.
75 CallbackTag K = GetCallbackTag(Kind, S->getStmtClass());
Ted Kremenek9e9595b2010-06-25 20:59:31 +000076
77 CheckersOrdered *& CO_Ref = COCache[K];
78
79 if (!CO_Ref) {
80 // If we have no previously cached CheckersOrdered vector for this
81 // statement kind, then create one.
82 NewCO.reset(new CheckersOrdered);
83 }
84 else {
85 // Use the already cached set.
86 CO = CO_Ref;
87 }
88
89 if (CO->empty()) {
90 // If there are no checkers, return early without doing any
91 // more work.
Ted Kremenek17f4da82009-12-09 02:45:41 +000092 Dst.insert(Src);
Zhongxing Xua46e4d92009-12-02 05:49:12 +000093 return;
Ted Kremenek5a5d98b2009-07-22 21:43:51 +000094 }
Mike Stump1eb44332009-09-09 15:08:12 +000095
Zhongxing Xu031ccc02009-08-06 12:48:26 +000096 ExplodedNodeSet Tmp;
97 ExplodedNodeSet *PrevSet = &Src;
Ted Kremenek9e9595b2010-06-25 20:59:31 +000098 unsigned checkersEvaluated = 0;
Mike Stump1eb44332009-09-09 15:08:12 +000099
Zhongxing Xu68df7302010-08-06 04:20:59 +0000100 for (CheckersOrdered::iterator I=CO->begin(), E=CO->end(); I!=E; ++I) {
101 // If all nodes are sunk, bail out early.
102 if (PrevSet->empty())
103 break;
Ted Kremenek17f4da82009-12-09 02:45:41 +0000104 ExplodedNodeSet *CurrSet = 0;
105 if (I+1 == E)
106 CurrSet = &Dst;
107 else {
108 CurrSet = (PrevSet == &Tmp) ? &Src : &Tmp;
109 CurrSet->clear();
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000110 }
Zhongxing Xuec9227f2009-10-29 02:09:30 +0000111 void *tag = I->first;
112 Checker *checker = I->second;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000113 bool respondsToCallback = true;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000114
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000115 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000116 NI != NE; ++NI) {
117
Jordy Rose72905cf2010-08-04 07:10:57 +0000118 checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag,
119 Kind == PreVisitStmtCallback, respondsToCallback);
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000120
121 }
122
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000123 PrevSet = CurrSet;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000124
125 if (NewCO.get()) {
126 ++checkersEvaluated;
127 if (respondsToCallback)
128 NewCO->push_back(*I);
129 }
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000130 }
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000131
132 // If we built NewCO, check if we called all the checkers. This is important
133 // so that we know that we accurately determined the entire set of checkers
Ted Kremenek9b44eaf2010-08-05 15:03:30 +0000134 // that responds to this callback. Note that 'checkersEvaluated' might
135 // not be the same as Checkers.size() if one of the Checkers generates
136 // a sink node.
137 if (NewCO.get() && checkersEvaluated == Checkers.size())
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000138 CO_Ref = NewCO.take();
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000139
140 // Don't autotransition. The CheckerContext objects should do this
141 // automatically.
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000142}
143
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000144void GRExprEngine::CheckerEvalNilReceiver(const ObjCMessageExpr *ME,
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000145 ExplodedNodeSet &Dst,
146 const GRState *state,
147 ExplodedNode *Pred) {
Ted Kremenek9c149532010-12-01 21:57:22 +0000148 bool evaluated = false;
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000149 ExplodedNodeSet DstTmp;
150
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000151 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
152 void *tag = I->first;
153 Checker *checker = I->second;
154
Ted Kremenek9c149532010-12-01 21:57:22 +0000155 if (checker->GR_evalNilReceiver(DstTmp, *Builder, *this, ME, Pred, state,
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000156 tag)) {
Ted Kremenek9c149532010-12-01 21:57:22 +0000157 evaluated = true;
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000158 break;
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000159 } else
160 // The checker didn't evaluate the expr. Restore the Dst.
161 DstTmp.clear();
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000162 }
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000163
Ted Kremenek9c149532010-12-01 21:57:22 +0000164 if (evaluated)
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000165 Dst.insert(DstTmp);
166 else
167 Dst.insert(Pred);
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000168}
169
Zhongxing Xu935ef902009-12-07 09:17:35 +0000170// CheckerEvalCall returns true if one of the checkers processed the node.
171// This may return void when all call evaluation logic goes to some checker
172// in the future.
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000173bool GRExprEngine::CheckerEvalCall(const CallExpr *CE,
174 ExplodedNodeSet &Dst,
Zhongxing Xu935ef902009-12-07 09:17:35 +0000175 ExplodedNode *Pred) {
Ted Kremenek9c149532010-12-01 21:57:22 +0000176 bool evaluated = false;
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000177 ExplodedNodeSet DstTmp;
Zhongxing Xu935ef902009-12-07 09:17:35 +0000178
179 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
180 void *tag = I->first;
181 Checker *checker = I->second;
182
Ted Kremenek9c149532010-12-01 21:57:22 +0000183 if (checker->GR_evalCallExpr(DstTmp, *Builder, *this, CE, Pred, tag)) {
184 evaluated = true;
Zhongxing Xu935ef902009-12-07 09:17:35 +0000185 break;
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000186 } else
187 // The checker didn't evaluate the expr. Restore the DstTmp set.
188 DstTmp.clear();
Zhongxing Xu935ef902009-12-07 09:17:35 +0000189 }
190
Ted Kremenek9c149532010-12-01 21:57:22 +0000191 if (evaluated)
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000192 Dst.insert(DstTmp);
193 else
194 Dst.insert(Pred);
195
Ted Kremenek9c149532010-12-01 21:57:22 +0000196 return evaluated;
Zhongxing Xu935ef902009-12-07 09:17:35 +0000197}
198
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000199// FIXME: This is largely copy-paste from CheckerVisit(). Need to
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000200// unify.
Ted Kremenek79d73042010-09-02 00:56:20 +0000201void GRExprEngine::CheckerVisitBind(const Stmt *StoreE, ExplodedNodeSet &Dst,
202 ExplodedNodeSet &Src, SVal location,
203 SVal val, bool isPrevisit) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000204
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000205 if (Checkers.empty()) {
Ted Kremenek17f4da82009-12-09 02:45:41 +0000206 Dst.insert(Src);
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000207 return;
208 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000209
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000210 ExplodedNodeSet Tmp;
211 ExplodedNodeSet *PrevSet = &Src;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000212
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000213 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E; ++I)
214 {
Ted Kremenek17f4da82009-12-09 02:45:41 +0000215 ExplodedNodeSet *CurrSet = 0;
216 if (I+1 == E)
217 CurrSet = &Dst;
218 else {
219 CurrSet = (PrevSet == &Tmp) ? &Src : &Tmp;
220 CurrSet->clear();
221 }
Ted Kremenek53287512009-12-18 20:13:39 +0000222
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000223 void *tag = I->first;
224 Checker *checker = I->second;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000225
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000226 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
227 NI != NE; ++NI)
Ted Kremenek79d73042010-09-02 00:56:20 +0000228 checker->GR_VisitBind(*CurrSet, *Builder, *this, StoreE,
Ted Kremenek50ecd152009-11-05 00:42:23 +0000229 *NI, tag, location, val, isPrevisit);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000230
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000231 // Update which NodeSet is the current one.
232 PrevSet = CurrSet;
233 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000234
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000235 // Don't autotransition. The CheckerContext objects should do this
236 // automatically.
237}
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000238//===----------------------------------------------------------------------===//
Ted Kremenekbdb435d2008-07-11 18:37:32 +0000239// Engine construction and deletion.
240//===----------------------------------------------------------------------===//
241
Ted Kremenek32c49952009-11-25 21:51:20 +0000242static void RegisterInternalChecks(GRExprEngine &Eng) {
243 // Register internal "built-in" BugTypes with the BugReporter. These BugTypes
244 // are different than what probably many checks will do since they don't
245 // create BugReports on-the-fly but instead wait until GRExprEngine finishes
246 // analyzing a function. Generation of BugReport objects is done via a call
247 // to 'FlushReports' from BugReporter.
248 // The following checks do not need to have their associated BugTypes
249 // explicitly registered with the BugReporter. If they issue any BugReports,
250 // their associated BugType will get registered with the BugReporter
251 // automatically. Note that the check itself is owned by the GRExprEngine
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000252 // object.
Ted Kremenek40c37e12010-02-04 00:47:48 +0000253 RegisterAdjustedReturnValueChecker(Eng);
Zhongxing Xu5126c602010-06-16 05:45:09 +0000254 // CallAndMessageChecker should be registered before AttrNonNullChecker,
255 // where we assume arguments are not undefined.
Ted Kremenek32c49952009-11-25 21:51:20 +0000256 RegisterCallAndMessageChecker(Eng);
Zhongxing Xu5126c602010-06-16 05:45:09 +0000257 RegisterAttrNonNullChecker(Eng);
Ted Kremenek32c49952009-11-25 21:51:20 +0000258 RegisterDereferenceChecker(Eng);
259 RegisterVLASizeChecker(Eng);
260 RegisterDivZeroChecker(Eng);
Ted Kremenek32c49952009-11-25 21:51:20 +0000261 RegisterReturnUndefChecker(Eng);
262 RegisterUndefinedArraySubscriptChecker(Eng);
263 RegisterUndefinedAssignmentChecker(Eng);
264 RegisterUndefBranchChecker(Eng);
Ted Kremenek94fd0b82010-02-16 08:33:59 +0000265 RegisterUndefCapturedBlockVarChecker(Eng);
Ted Kremenek32c49952009-11-25 21:51:20 +0000266 RegisterUndefResultChecker(Eng);
Zhongxing Xu9b146832010-06-09 06:08:24 +0000267 RegisterStackAddrLeakChecker(Eng);
Ted Kremenek4f6aa772010-09-10 03:05:40 +0000268 RegisterObjCAtSyncChecker(Eng);
Zhongxing Xu935ef902009-12-07 09:17:35 +0000269
270 // This is not a checker yet.
271 RegisterNoReturnFunctionChecker(Eng);
Zhongxing Xu7c9624b2009-12-08 09:07:59 +0000272 RegisterBuiltinFunctionChecker(Eng);
Zhongxing Xu1ec4e972009-12-09 12:23:28 +0000273 RegisterOSAtomicChecker(Eng);
Ted Kremenek381d1bf2010-02-25 00:20:35 +0000274 RegisterUnixAPIChecker(Eng);
Ted Kremenekdf61b582010-02-25 05:44:09 +0000275 RegisterMacOSXAPIChecker(Eng);
Ted Kremeneke448ab42008-05-01 18:33:28 +0000276}
277
Ted Kremenek32a58082010-01-05 00:15:18 +0000278GRExprEngine::GRExprEngine(AnalysisManager &mgr, GRTransferFuncs *tf)
Zhongxing Xu25e695b2009-08-15 03:17:38 +0000279 : AMgr(mgr),
Zhongxing Xuc77a5512010-07-01 07:10:59 +0000280 CoreEngine(*this),
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000281 G(CoreEngine.getGraph()),
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000282 Builder(NULL),
Zhongxing Xuc77a5512010-07-01 07:10:59 +0000283 StateMgr(getContext(), mgr.getStoreManagerCreator(),
Ted Kremenek32a58082010-01-05 00:15:18 +0000284 mgr.getConstraintManagerCreator(), G.getAllocator(),
285 *this),
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000286 SymMgr(StateMgr.getSymbolManager()),
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000287 svalBuilder(StateMgr.getSValBuilder()),
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000288 EntryNode(NULL), currentStmt(NULL),
Zhongxing Xua5a41662008-12-22 08:30:52 +0000289 NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL),
Zhongxing Xuc77a5512010-07-01 07:10:59 +0000290 RaiseSel(GetNullarySelector("raise", getContext())),
Ted Kremenek32a58082010-01-05 00:15:18 +0000291 BR(mgr, *this), TF(tf) {
Ted Kremenekc80135b2009-11-25 21:45:48 +0000292 // Register internal checks.
Ted Kremenek32c49952009-11-25 21:51:20 +0000293 RegisterInternalChecks(*this);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000294
Ted Kremenek32a58082010-01-05 00:15:18 +0000295 // FIXME: Eventually remove the TF object entirely.
296 TF->RegisterChecks(*this);
297 TF->RegisterPrinters(getStateManager().Printers);
Ted Kremenekc80135b2009-11-25 21:45:48 +0000298}
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000299
Mike Stump1eb44332009-09-09 15:08:12 +0000300GRExprEngine::~GRExprEngine() {
Ted Kremenekcf118d42009-02-04 23:49:09 +0000301 BR.FlushReports();
Ted Kremeneke448ab42008-05-01 18:33:28 +0000302 delete [] NSExceptionInstanceRaiseSelectors;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000303
304 // Delete the set of checkers.
Ted Kremenek094bef52009-10-30 17:47:32 +0000305 for (CheckersOrdered::iterator I=Checkers.begin(), E=Checkers.end(); I!=E;++I)
Zhongxing Xuec9227f2009-10-29 02:09:30 +0000306 delete I->second;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000307
308 for (CheckersOrderedCache::iterator I=COCache.begin(), E=COCache.end();
309 I!=E;++I)
310 delete I->second;
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000311}
312
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000313//===----------------------------------------------------------------------===//
314// Utility methods.
315//===----------------------------------------------------------------------===//
316
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000317const GRState* GRExprEngine::getInitialState(const LocationContext *InitLoc) {
318 const GRState *state = StateMgr.getInitialState(InitLoc);
Mike Stump1eb44332009-09-09 15:08:12 +0000319
Ted Kremenekcfcd7fd2009-09-09 20:36:12 +0000320 // Preconditions.
321
Ted Kremenek52e56022009-04-10 00:59:50 +0000322 // FIXME: It would be nice if we had a more general mechanism to add
323 // such preconditions. Some day.
Ted Kremenek5974ec52009-12-17 19:17:27 +0000324 do {
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000325 const Decl *D = InitLoc->getDecl();
Ted Kremenek5974ec52009-12-17 19:17:27 +0000326 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
327 // Precondition: the first argument of 'main' is an integer guaranteed
328 // to be > 0.
329 const IdentifierInfo *II = FD->getIdentifier();
330 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
331 break;
Ted Kremeneka591bc02009-06-18 22:57:13 +0000332
Ted Kremenek5974ec52009-12-17 19:17:27 +0000333 const ParmVarDecl *PD = FD->getParamDecl(0);
334 QualType T = PD->getType();
335 if (!T->isIntegerType())
336 break;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000337
Ted Kremenek5974ec52009-12-17 19:17:27 +0000338 const MemRegion *R = state->getRegion(PD, InitLoc);
339 if (!R)
340 break;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000341
Ted Kremenek13976632010-02-08 16:18:51 +0000342 SVal V = state->getSVal(loc::MemRegionVal(R));
Ted Kremenek9c149532010-12-01 21:57:22 +0000343 SVal Constraint_untested = evalBinOp(state, BO_GT, V,
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000344 svalBuilder.makeZeroVal(T),
Ted Kremenek5974ec52009-12-17 19:17:27 +0000345 getContext().IntTy);
346
347 DefinedOrUnknownSVal *Constraint =
348 dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000349
Ted Kremenek5974ec52009-12-17 19:17:27 +0000350 if (!Constraint)
351 break;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000352
Ted Kremenek28f47b92010-12-01 22:16:56 +0000353 if (const GRState *newState = state->assume(*Constraint, true))
Ted Kremenek5974ec52009-12-17 19:17:27 +0000354 state = newState;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000355
Ted Kremenek5974ec52009-12-17 19:17:27 +0000356 break;
357 }
358
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000359 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
Ted Kremenek5974ec52009-12-17 19:17:27 +0000360 // Precondition: 'self' is always non-null upon entry to an Objective-C
361 // method.
362 const ImplicitParamDecl *SelfD = MD->getSelfDecl();
363 const MemRegion *R = state->getRegion(SelfD, InitLoc);
Ted Kremenek13976632010-02-08 16:18:51 +0000364 SVal V = state->getSVal(loc::MemRegionVal(R));
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000365
Ted Kremenek5974ec52009-12-17 19:17:27 +0000366 if (const Loc *LV = dyn_cast<Loc>(&V)) {
367 // Assume that the pointer value in 'self' is non-null.
Ted Kremenek28f47b92010-12-01 22:16:56 +0000368 state = state->assume(*LV, true);
Ted Kremenek5974ec52009-12-17 19:17:27 +0000369 assert(state && "'self' cannot be null");
Ted Kremenek5f75f922009-12-17 01:20:43 +0000370 }
Ted Kremenek52e56022009-04-10 00:59:50 +0000371 }
Ted Kremenek5974ec52009-12-17 19:17:27 +0000372 } while (0);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000373
Ted Kremenek52e56022009-04-10 00:59:50 +0000374 return state;
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000375}
376
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000377//===----------------------------------------------------------------------===//
378// Top-level transfer function logic (Dispatcher).
379//===----------------------------------------------------------------------===//
380
Ted Kremenek9c149532010-12-01 21:57:22 +0000381/// evalAssume - Called by ConstraintManager. Used to call checker-specific
Ted Kremenek32a58082010-01-05 00:15:18 +0000382/// logic for handling assumptions on symbolic values.
383const GRState *GRExprEngine::ProcessAssume(const GRState *state, SVal cond,
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000384 bool assumption) {
Jordy Rose72905cf2010-08-04 07:10:57 +0000385 // Determine if we already have a cached 'CheckersOrdered' vector
386 // specifically tailored for processing assumptions. This
387 // can reduce the number of checkers actually called.
388 CheckersOrdered *CO = &Checkers;
389 llvm::OwningPtr<CheckersOrdered> NewCO;
Ted Kremenek32a58082010-01-05 00:15:18 +0000390
Jordy Rose72905cf2010-08-04 07:10:57 +0000391 CallbackTag K = GetCallbackTag(ProcessAssumeCallback);
392 CheckersOrdered *& CO_Ref = COCache[K];
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000393
Jordy Rose72905cf2010-08-04 07:10:57 +0000394 if (!CO_Ref) {
395 // If we have no previously cached CheckersOrdered vector for this
396 // statement kind, then create one.
397 NewCO.reset(new CheckersOrdered);
398 }
399 else {
400 // Use the already cached set.
401 CO = CO_Ref;
Ted Kremenek32a58082010-01-05 00:15:18 +0000402 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000403
Jordy Rose72905cf2010-08-04 07:10:57 +0000404 if (!CO->empty()) {
405 // Let the checkers have a crack at the assume before the transfer functions
406 // get their turn.
Jordy Rosea2050612010-08-12 04:05:07 +0000407 for (CheckersOrdered::iterator I = CO->begin(), E = CO->end(); I!=E; ++I) {
Jordy Rose72905cf2010-08-04 07:10:57 +0000408
409 // If any checker declares the state infeasible (or if it starts that
410 // way), bail out.
411 if (!state)
412 return NULL;
413
414 Checker *C = I->second;
415 bool respondsToCallback = true;
416
Ted Kremenek9c149532010-12-01 21:57:22 +0000417 state = C->evalAssume(state, cond, assumption, &respondsToCallback);
Jordy Rose72905cf2010-08-04 07:10:57 +0000418
Ted Kremenek28f47b92010-12-01 22:16:56 +0000419 // Check if we're building the cache of checkers that care about
420 // assumptions.
Jordy Rose72905cf2010-08-04 07:10:57 +0000421 if (NewCO.get() && respondsToCallback)
422 NewCO->push_back(*I);
423 }
424
425 // If we got through all the checkers, and we built a list of those that
Ted Kremenek28f47b92010-12-01 22:16:56 +0000426 // care about assumptions, save it.
Jordy Rose72905cf2010-08-04 07:10:57 +0000427 if (NewCO.get())
428 CO_Ref = NewCO.take();
429 }
430
431 // If the state is infeasible at this point, bail out.
Ted Kremenek32a58082010-01-05 00:15:18 +0000432 if (!state)
433 return NULL;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000434
Ted Kremenek9c149532010-12-01 21:57:22 +0000435 return TF->evalAssume(state, cond, assumption);
Ted Kremenek32a58082010-01-05 00:15:18 +0000436}
437
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000438bool GRExprEngine::WantsRegionChangeUpdate(const GRState* state) {
439 CallbackTag K = GetCallbackTag(EvalRegionChangesCallback);
440 CheckersOrdered *CO = COCache[K];
441
442 if (!CO)
443 CO = &Checkers;
444
445 for (CheckersOrdered::iterator I = CO->begin(), E = CO->end(); I != E; ++I) {
446 Checker *C = I->second;
447 if (C->WantsRegionChangeUpdate(state))
448 return true;
449 }
450
451 return false;
452}
453
454const GRState *
455GRExprEngine::ProcessRegionChanges(const GRState *state,
456 const MemRegion * const *Begin,
457 const MemRegion * const *End) {
458 // FIXME: Most of this method is copy-pasted from ProcessAssume.
459
460 // Determine if we already have a cached 'CheckersOrdered' vector
461 // specifically tailored for processing region changes. This
462 // can reduce the number of checkers actually called.
463 CheckersOrdered *CO = &Checkers;
464 llvm::OwningPtr<CheckersOrdered> NewCO;
465
466 CallbackTag K = GetCallbackTag(EvalRegionChangesCallback);
467 CheckersOrdered *& CO_Ref = COCache[K];
468
469 if (!CO_Ref) {
470 // If we have no previously cached CheckersOrdered vector for this
471 // callback, then create one.
472 NewCO.reset(new CheckersOrdered);
473 }
474 else {
475 // Use the already cached set.
476 CO = CO_Ref;
477 }
478
479 // If there are no checkers, just return the state as is.
480 if (CO->empty())
481 return state;
482
483 for (CheckersOrdered::iterator I = CO->begin(), E = CO->end(); I != E; ++I) {
484 // If any checker declares the state infeasible (or if it starts that way),
485 // bail out.
486 if (!state)
487 return NULL;
488
489 Checker *C = I->second;
490 bool respondsToCallback = true;
491
492 state = C->EvalRegionChanges(state, Begin, End, &respondsToCallback);
493
494 // See if we're building a cache of checkers that care about region changes.
495 if (NewCO.get() && respondsToCallback)
496 NewCO->push_back(*I);
497 }
498
499 // If we got through all the checkers, and we built a list of those that
500 // care about region changes, save it.
501 if (NewCO.get())
502 CO_Ref = NewCO.take();
503
504 return state;
505}
506
Ted Kremenekccc263b2010-06-23 22:08:00 +0000507void GRExprEngine::ProcessEndWorklist(bool hasWorkRemaining) {
508 for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
509 I != E; ++I) {
Tom Carebc42c532010-08-03 01:55:07 +0000510 I->second->VisitEndAnalysis(G, BR, *this);
Ted Kremenekccc263b2010-06-23 22:08:00 +0000511 }
512}
513
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000514void GRExprEngine::ProcessElement(const CFGElement E,
515 GRStmtNodeBuilder& builder) {
516 switch (E.getKind()) {
517 case CFGElement::Statement:
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000518 ProcessStmt(E.getAs<CFGStmt>(), builder);
519 break;
520 case CFGElement::Initializer:
521 ProcessInitializer(E.getAs<CFGInitializer>(), builder);
522 break;
523 case CFGElement::ImplicitDtor:
524 ProcessImplicitDtor(E.getAs<CFGImplicitDtor>(), builder);
525 break;
526 default:
527 // Suppress compiler warning.
528 llvm_unreachable("Unexpected CFGElement kind.");
529 }
530}
531
532void GRExprEngine::ProcessStmt(const CFGStmt S, GRStmtNodeBuilder& builder) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000533 currentStmt = S.getStmt();
Ted Kremenek0bed8a12009-03-11 02:41:36 +0000534 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000535 currentStmt->getLocStart(),
Ted Kremenek0bed8a12009-03-11 02:41:36 +0000536 "Error evaluating statement");
Mike Stump1eb44332009-09-09 15:08:12 +0000537
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000538 Builder = &builder;
Zhongxing Xu25108a52010-02-26 02:38:09 +0000539 EntryNode = builder.getBasePredecessor();
Mike Stump1eb44332009-09-09 15:08:12 +0000540
Mike Stump1eb44332009-09-09 15:08:12 +0000541 // Create the cleaned state.
Jordy Rosebd533aa2010-08-14 20:18:45 +0000542 const LocationContext *LC = EntryNode->getLocationContext();
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000543 SymbolReaper SymReaper(LC, currentStmt, SymMgr);
Zhongxing Xuc179a7f2010-03-05 04:45:36 +0000544
Jordy Rosebd533aa2010-08-14 20:18:45 +0000545 if (AMgr.shouldPurgeDead()) {
546 const GRState *St = EntryNode->getState();
Zhongxing Xuc179a7f2010-03-05 04:45:36 +0000547
Jordy Rosebd533aa2010-08-14 20:18:45 +0000548 for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
549 I != E; ++I) {
550 Checker *checker = I->second;
551 checker->MarkLiveSymbols(St, SymReaper);
552 }
553
554 const StackFrameContext *SFC = LC->getCurrentStackFrame();
555 CleanedState = StateMgr.RemoveDeadBindings(St, SFC, SymReaper);
556 } else {
557 CleanedState = EntryNode->getState();
558 }
Ted Kremenek241677a2009-01-21 22:26:05 +0000559
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000560 // Process any special transfer function for dead symbols.
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000561 ExplodedNodeSet Tmp;
Mike Stump1eb44332009-09-09 15:08:12 +0000562
Ted Kremenek241677a2009-01-21 22:26:05 +0000563 if (!SymReaper.hasDeadSymbols())
Ted Kremenek846d4e92008-04-24 23:35:58 +0000564 Tmp.Add(EntryNode);
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000565 else {
566 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000567 SaveOr OldHasGen(Builder->HasGeneratedNode);
568
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000569 SaveAndRestore<bool> OldPurgeDeadSymbols(Builder->PurgingDeadSymbols);
570 Builder->PurgingDeadSymbols = true;
Mike Stump1eb44332009-09-09 15:08:12 +0000571
Zhongxing Xu94006132009-11-13 06:53:04 +0000572 // FIXME: This should soon be removed.
573 ExplodedNodeSet Tmp2;
Ted Kremenek9c149532010-12-01 21:57:22 +0000574 getTF().evalDeadSymbols(Tmp2, *this, *Builder, EntryNode,
Ted Kremenek241677a2009-01-21 22:26:05 +0000575 CleanedState, SymReaper);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000576
Zhongxing Xu94006132009-11-13 06:53:04 +0000577 if (Checkers.empty())
Zhongxing Xu7fbb1ba2009-12-14 02:13:39 +0000578 Tmp.insert(Tmp2);
Zhongxing Xu94006132009-11-13 06:53:04 +0000579 else {
580 ExplodedNodeSet Tmp3;
581 ExplodedNodeSet *SrcSet = &Tmp2;
582 for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
583 I != E; ++I) {
Ted Kremenek17f4da82009-12-09 02:45:41 +0000584 ExplodedNodeSet *DstSet = 0;
585 if (I+1 == E)
586 DstSet = &Tmp;
587 else {
588 DstSet = (SrcSet == &Tmp2) ? &Tmp3 : &Tmp2;
589 DstSet->clear();
590 }
591
Zhongxing Xu94006132009-11-13 06:53:04 +0000592 void *tag = I->first;
593 Checker *checker = I->second;
594 for (ExplodedNodeSet::iterator NI = SrcSet->begin(), NE = SrcSet->end();
595 NI != NE; ++NI)
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000596 checker->GR_evalDeadSymbols(*DstSet, *Builder, *this, currentStmt,
Ted Kremenek852274d2009-12-16 03:18:58 +0000597 *NI, SymReaper, tag);
Zhongxing Xu94006132009-11-13 06:53:04 +0000598 SrcSet = DstSet;
599 }
600 }
601
Ted Kremenek846d4e92008-04-24 23:35:58 +0000602 if (!Builder->BuildSinks && !Builder->HasGeneratedNode)
603 Tmp.Add(EntryNode);
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000604 }
Mike Stump1eb44332009-09-09 15:08:12 +0000605
Ted Kremenek846d4e92008-04-24 23:35:58 +0000606 bool HasAutoGenerated = false;
607
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000608 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000609 ExplodedNodeSet Dst;
Mike Stump1eb44332009-09-09 15:08:12 +0000610
611 // Set the cleaned state.
Ted Kremenek846d4e92008-04-24 23:35:58 +0000612 Builder->SetCleanedState(*I == EntryNode ? CleanedState : GetState(*I));
Mike Stump1eb44332009-09-09 15:08:12 +0000613
614 // Visit the statement.
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000615 Visit(currentStmt, *I, Dst);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000616
617 // Do we need to auto-generate a node? We only need to do this to generate
618 // a node with a "cleaned" state; GRCoreEngine will actually handle
Mike Stump1eb44332009-09-09 15:08:12 +0000619 // auto-transitions for other cases.
Ted Kremenek846d4e92008-04-24 23:35:58 +0000620 if (Dst.size() == 1 && *Dst.begin() == EntryNode
621 && !Builder->HasGeneratedNode && !HasAutoGenerated) {
622 HasAutoGenerated = true;
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000623 builder.generateNode(currentStmt, GetState(EntryNode), *I);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000624 }
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000625 }
Mike Stump1eb44332009-09-09 15:08:12 +0000626
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000627 // NULL out these variables to cleanup.
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000628 CleanedState = NULL;
Ted Kremenek846d4e92008-04-24 23:35:58 +0000629 EntryNode = NULL;
Ted Kremenekdf7533b2008-07-17 21:27:31 +0000630
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000631 currentStmt = 0;
Mike Stump1eb44332009-09-09 15:08:12 +0000632
Ted Kremenek846d4e92008-04-24 23:35:58 +0000633 Builder = NULL;
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000634}
635
Zhongxing Xu9dc84c92010-11-16 07:52:17 +0000636void GRExprEngine::ProcessInitializer(const CFGInitializer Init,
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000637 GRStmtNodeBuilder &builder) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000638 // We don't set EntryNode and currentStmt. And we don't clean up state.
Zhongxing Xu9dc84c92010-11-16 07:52:17 +0000639 const CXXBaseOrMemberInitializer *BMI = Init.getInitializer();
640
641 ExplodedNode *Pred = builder.getBasePredecessor();
642 const LocationContext *LC = Pred->getLocationContext();
643
Francois Pichet00eb3f92010-12-04 09:14:42 +0000644 if (BMI->isAnyMemberInitializer()) {
Zhongxing Xu9dc84c92010-11-16 07:52:17 +0000645 ExplodedNodeSet Dst;
646
647 // Evaluate the initializer.
648 Visit(BMI->getInit(), Pred, Dst);
649
650 for (ExplodedNodeSet::iterator I = Dst.begin(), E = Dst.end(); I != E; ++I){
651 ExplodedNode *Pred = *I;
652 const GRState *state = Pred->getState();
653
Francois Pichet00eb3f92010-12-04 09:14:42 +0000654 const FieldDecl *FD = BMI->getAnyMember();
Zhongxing Xu9dc84c92010-11-16 07:52:17 +0000655 const RecordDecl *RD = FD->getParent();
656 const CXXThisRegion *ThisR = getCXXThisRegion(cast<CXXRecordDecl>(RD),
657 cast<StackFrameContext>(LC));
658
659 SVal ThisV = state->getSVal(ThisR);
660 SVal FieldLoc = state->getLValue(FD, ThisV);
661 SVal InitVal = state->getSVal(BMI->getInit());
662 state = state->bindLoc(FieldLoc, InitVal);
663
664 // Use a custom node building process.
665 PostInitializer PP(BMI, LC);
666 // Builder automatically add the generated node to the deferred set,
667 // which are processed in the builder's dtor.
668 builder.generateNode(PP, state, Pred);
669 }
670 }
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000671}
672
673void GRExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
674 GRStmtNodeBuilder &builder) {
Zhongxing Xub13453b2010-11-20 06:53:12 +0000675 Builder = &builder;
676
Zhongxing Xu4ffcb992010-11-17 09:16:19 +0000677 switch (D.getDtorKind()) {
678 case CFGElement::AutomaticObjectDtor:
679 ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), builder);
680 break;
681 case CFGElement::BaseDtor:
682 ProcessBaseDtor(cast<CFGBaseDtor>(D), builder);
683 break;
684 case CFGElement::MemberDtor:
685 ProcessMemberDtor(cast<CFGMemberDtor>(D), builder);
686 break;
687 case CFGElement::TemporaryDtor:
688 ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), builder);
689 break;
690 default:
691 llvm_unreachable("Unexpected dtor kind.");
692 }
693}
694
Zhongxing Xu22104902010-11-25 06:35:14 +0000695void GRExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor dtor,
Zhongxing Xu4ffcb992010-11-17 09:16:19 +0000696 GRStmtNodeBuilder &builder) {
Zhongxing Xu22104902010-11-25 06:35:14 +0000697 ExplodedNode *pred = builder.getBasePredecessor();
698 const GRState *state = pred->getState();
699 const VarDecl *varDecl = dtor.getVarDecl();
Zhongxing Xub13453b2010-11-20 06:53:12 +0000700
Zhongxing Xu22104902010-11-25 06:35:14 +0000701 QualType varType = varDecl->getType();
Zhongxing Xub13453b2010-11-20 06:53:12 +0000702
Zhongxing Xu22104902010-11-25 06:35:14 +0000703 if (const ReferenceType *refType = varType->getAs<ReferenceType>())
704 varType = refType->getPointeeType();
705
706 const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl();
707 assert(recordDecl && "get CXXRecordDecl fail");
708 const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor();
709
710 Loc dest = state->getLValue(varDecl, pred->getLocationContext());
711
712 ExplodedNodeSet dstSet;
713 VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(),
714 dtor.getTriggerStmt(), pred, dstSet);
Zhongxing Xu4ffcb992010-11-17 09:16:19 +0000715}
716
717void GRExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
718 GRStmtNodeBuilder &builder) {
719}
720
721void GRExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
722 GRStmtNodeBuilder &builder) {
723}
724
725void GRExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
726 GRStmtNodeBuilder &builder) {
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000727}
728
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000729void GRExprEngine::Visit(const Stmt* S, ExplodedNode* Pred,
730 ExplodedNodeSet& Dst) {
Ted Kremenek0bed8a12009-03-11 02:41:36 +0000731 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
732 S->getLocStart(),
733 "Error evaluating statement");
734
John McCallf6a16482010-12-04 03:47:34 +0000735 // Expressions to ignore.
736 if (const Expr *Ex = dyn_cast<Expr>(S))
Ted Kremenek892697d2010-12-16 07:46:53 +0000737 S = Ex->IgnoreParens();
John McCallf6a16482010-12-04 03:47:34 +0000738
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000739 // FIXME: add metadata to the CFG so that we can disable
740 // this check when we KNOW that there is no block-level subexpression.
741 // The motivation is that this check requires a hashtable lookup.
Mike Stump1eb44332009-09-09 15:08:12 +0000742
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000743 if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) {
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000744 Dst.Add(Pred);
745 return;
746 }
Mike Stump1eb44332009-09-09 15:08:12 +0000747
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000748 switch (S->getStmtClass()) {
Ted Kremenekc768a0c2009-12-15 01:38:04 +0000749 // C++ stuff we don't support yet.
Ted Kremenekc768a0c2009-12-15 01:38:04 +0000750 case Stmt::CXXBindTemporaryExprClass:
Ted Kremenekc768a0c2009-12-15 01:38:04 +0000751 case Stmt::CXXCatchStmtClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000752 case Stmt::CXXDefaultArgExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000753 case Stmt::CXXDependentScopeMemberExprClass:
John McCall4765fa02010-12-06 08:20:24 +0000754 case Stmt::ExprWithCleanupsClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000755 case Stmt::CXXNullPtrLiteralExprClass:
756 case Stmt::CXXPseudoDestructorExprClass:
757 case Stmt::CXXTemporaryObjectExprClass:
758 case Stmt::CXXThrowExprClass:
759 case Stmt::CXXTryStmtClass:
760 case Stmt::CXXTypeidExprClass:
Francois Pichet9be88402010-09-08 23:47:05 +0000761 case Stmt::CXXUuidofExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000762 case Stmt::CXXUnresolvedConstructExprClass:
Douglas Gregored8abf12010-07-08 06:14:04 +0000763 case Stmt::CXXScalarValueInitExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000764 case Stmt::DependentScopeDeclRefExprClass:
765 case Stmt::UnaryTypeTraitExprClass:
Francois Pichet6ad6f282010-12-07 00:08:36 +0000766 case Stmt::BinaryTypeTraitExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000767 case Stmt::UnresolvedLookupExprClass:
768 case Stmt::UnresolvedMemberExprClass:
Sebastian Redl6b219d02010-09-10 20:55:54 +0000769 case Stmt::CXXNoexceptExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000770 {
Ted Kremenekc768a0c2009-12-15 01:38:04 +0000771 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
772 Builder->BuildSinks = true;
773 MakeNode(Dst, S, Pred, GetState(Pred));
774 break;
775 }
John McCallf6a16482010-12-04 03:47:34 +0000776
777 case Stmt::ParenExprClass:
778 llvm_unreachable("ParenExprs already handled.");
Ted Kremenek1b49d762010-04-15 17:33:31 +0000779 // Cases that should never be evaluated simply because they shouldn't
780 // appear in the CFG.
781 case Stmt::BreakStmtClass:
782 case Stmt::CaseStmtClass:
783 case Stmt::CompoundStmtClass:
784 case Stmt::ContinueStmtClass:
785 case Stmt::DefaultStmtClass:
786 case Stmt::DoStmtClass:
787 case Stmt::GotoStmtClass:
788 case Stmt::IndirectGotoStmtClass:
789 case Stmt::LabelStmtClass:
790 case Stmt::NoStmtClass:
791 case Stmt::NullStmtClass:
792 case Stmt::SwitchCaseClass:
John McCall7cd7d1a2010-11-15 23:31:06 +0000793 case Stmt::OpaqueValueExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000794 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
795 break;
796
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +0000797 case Stmt::GNUNullExprClass: {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000798 MakeNode(Dst, S, Pred, GetState(Pred)->BindExpr(S, svalBuilder.makeNull()));
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +0000799 break;
800 }
801
Ted Kremenek4beaa9f2010-09-10 03:05:33 +0000802 case Stmt::ObjCAtSynchronizedStmtClass:
803 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
804 break;
805
Ted Kremenek1b49d762010-04-15 17:33:31 +0000806 // Cases not handled yet; but will handle some day.
807 case Stmt::DesignatedInitExprClass:
808 case Stmt::ExtVectorElementExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000809 case Stmt::ImaginaryLiteralClass:
810 case Stmt::ImplicitValueInitExprClass:
811 case Stmt::ObjCAtCatchStmtClass:
812 case Stmt::ObjCAtFinallyStmtClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000813 case Stmt::ObjCAtTryStmtClass:
814 case Stmt::ObjCEncodeExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000815 case Stmt::ObjCIsaExprClass:
816 case Stmt::ObjCPropertyRefExprClass:
817 case Stmt::ObjCProtocolExprClass:
818 case Stmt::ObjCSelectorExprClass:
819 case Stmt::ObjCStringLiteralClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000820 case Stmt::ParenListExprClass:
821 case Stmt::PredefinedExprClass:
822 case Stmt::ShuffleVectorExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000823 case Stmt::VAArgExprClass:
824 // Fall through.
825
826 // Cases we intentionally don't evaluate, since they don't need
827 // to be explicitly evaluated.
Zhongxing Xubc9ad742010-04-13 13:15:19 +0000828 case Stmt::AddrLabelExprClass:
829 case Stmt::IntegerLiteralClass:
830 case Stmt::CharacterLiteralClass:
Zhongxing Xu477323d2010-04-14 06:29:29 +0000831 case Stmt::CXXBoolLiteralExprClass:
Zhongxing Xubc9ad742010-04-13 13:15:19 +0000832 case Stmt::FloatingLiteralClass:
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000833 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
834 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000835
Ted Kremenek540cbe22008-04-22 04:56:29 +0000836 case Stmt::ArraySubscriptExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000837 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
Ted Kremenek540cbe22008-04-22 04:56:29 +0000838 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000839
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000840 case Stmt::AsmStmtClass:
841 VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst);
842 break;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000843
Ted Kremenek892697d2010-12-16 07:46:53 +0000844 case Stmt::BlockDeclRefExprClass: {
845 const BlockDeclRefExpr *BE = cast<BlockDeclRefExpr>(S);
846 VisitCommonDeclRefExpr(BE, BE->getDecl(), Pred, Dst);
Ted Kremenek67d12872009-12-07 22:05:27 +0000847 break;
Ted Kremenek892697d2010-12-16 07:46:53 +0000848 }
Mike Stump1eb44332009-09-09 15:08:12 +0000849
Ted Kremenekc95ad9f2009-11-25 01:33:13 +0000850 case Stmt::BlockExprClass:
851 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
852 break;
853
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000854 case Stmt::BinaryOperatorClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000855 const BinaryOperator* B = cast<BinaryOperator>(S);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000856 if (B->isLogicalOp()) {
857 VisitLogicalExpr(B, Pred, Dst);
858 break;
859 }
John McCall2de56d12010-08-25 11:45:40 +0000860 else if (B->getOpcode() == BO_Comma) {
Ted Kremeneka8538d92009-02-13 01:45:31 +0000861 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +0000862 MakeNode(Dst, B, Pred, state->BindExpr(B, state->getSVal(B->getRHS())));
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000863 break;
864 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000865
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000866 if (AMgr.shouldEagerlyAssume() &&
Zhongxing Xubb141212009-12-16 11:27:52 +0000867 (B->isRelationalOp() || B->isEqualityOp())) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000868 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +0000869 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
Ted Kremenek9c149532010-12-01 21:57:22 +0000870 evalEagerlyAssume(Dst, Tmp, cast<Expr>(S));
Ted Kremenek48af2a92009-02-25 22:32:02 +0000871 }
872 else
Ted Kremenek892697d2010-12-16 07:46:53 +0000873 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
Ted Kremenek48af2a92009-02-25 22:32:02 +0000874
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000875 break;
876 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000877
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000878 case Stmt::CallExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000879 const CallExpr* C = cast<CallExpr>(S);
Ted Kremenek892697d2010-12-16 07:46:53 +0000880 VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst);
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000881 break;
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000882 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000883
Zhongxing Xu7ce351d2010-11-01 09:09:44 +0000884 case Stmt::CXXConstructExprClass: {
885 const CXXConstructExpr *C = cast<CXXConstructExpr>(S);
886 // For block-level CXXConstructExpr, we don't have a destination region.
887 // Let VisitCXXConstructExpr() create one.
Ted Kremenek892697d2010-12-16 07:46:53 +0000888 VisitCXXConstructExpr(C, 0, Pred, Dst);
Zhongxing Xu7ce351d2010-11-01 09:09:44 +0000889 break;
890 }
891
Zhongxing Xu950db872010-04-01 07:58:50 +0000892 case Stmt::CXXMemberCallExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000893 const CXXMemberCallExpr *MCE = cast<CXXMemberCallExpr>(S);
Zhongxing Xu950db872010-04-01 07:58:50 +0000894 VisitCXXMemberCallExpr(MCE, Pred, Dst);
895 break;
896 }
897
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000898 case Stmt::CXXOperatorCallExprClass: {
899 const CXXOperatorCallExpr *C = cast<CXXOperatorCallExpr>(S);
900 VisitCXXOperatorCallExpr(C, Pred, Dst);
901 break;
902 }
903
Zhongxing Xu856c6bc2010-04-19 11:47:28 +0000904 case Stmt::CXXNewExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000905 const CXXNewExpr *NE = cast<CXXNewExpr>(S);
Zhongxing Xu856c6bc2010-04-19 11:47:28 +0000906 VisitCXXNewExpr(NE, Pred, Dst);
907 break;
908 }
909
Zhongxing Xu6b851382010-04-21 02:17:31 +0000910 case Stmt::CXXDeleteExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000911 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S);
Zhongxing Xu6b851382010-04-21 02:17:31 +0000912 VisitCXXDeleteExpr(CDE, Pred, Dst);
913 break;
914 }
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000915 // FIXME: ChooseExpr is really a constant. We need to fix
916 // the CFG do not model them as explicit control-flow.
Mike Stump1eb44332009-09-09 15:08:12 +0000917
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000918 case Stmt::ChooseExprClass: { // __builtin_choose_expr
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000919 const ChooseExpr* C = cast<ChooseExpr>(S);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000920 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
921 break;
922 }
Mike Stump1eb44332009-09-09 15:08:12 +0000923
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000924 case Stmt::CompoundAssignOperatorClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000925 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000926 break;
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000927
928 case Stmt::CompoundLiteralExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000929 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000930 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000931
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000932 case Stmt::ConditionalOperatorClass: { // '?' operator
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000933 const ConditionalOperator* C = cast<ConditionalOperator>(S);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000934 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
935 break;
936 }
Mike Stump1eb44332009-09-09 15:08:12 +0000937
Zhongxing Xubb141212009-12-16 11:27:52 +0000938 case Stmt::CXXThisExprClass:
939 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
940 break;
941
Ted Kremenek892697d2010-12-16 07:46:53 +0000942 case Stmt::DeclRefExprClass: {
943 const DeclRefExpr *DE = cast<DeclRefExpr>(S);
944 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000945 break;
Ted Kremenek892697d2010-12-16 07:46:53 +0000946 }
Mike Stump1eb44332009-09-09 15:08:12 +0000947
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000948 case Stmt::DeclStmtClass:
949 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
950 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000951
Ted Kremenek919f0662009-12-24 01:49:25 +0000952 case Stmt::ForStmtClass:
953 // This case isn't for branch processing, but for handling the
954 // initialization of a condition variable.
955 VisitCondInit(cast<ForStmt>(S)->getConditionVariable(), S, Pred, Dst);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000956 break;
Ted Kremenek919f0662009-12-24 01:49:25 +0000957
Argyrios Kyrtzidis0835a3c2008-08-18 23:01:59 +0000958 case Stmt::ImplicitCastExprClass:
Zhongxing Xu0d9d7362010-04-13 12:38:32 +0000959 case Stmt::CStyleCastExprClass:
960 case Stmt::CXXStaticCastExprClass:
961 case Stmt::CXXDynamicCastExprClass:
962 case Stmt::CXXReinterpretCastExprClass:
963 case Stmt::CXXConstCastExprClass:
964 case Stmt::CXXFunctionalCastExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000965 const CastExpr* C = cast<CastExpr>(S);
Ted Kremenek892697d2010-12-16 07:46:53 +0000966 VisitCast(C, C->getSubExpr(), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000967 break;
968 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000969
Ted Kremenek61dfbec2009-12-23 04:49:01 +0000970 case Stmt::IfStmtClass:
971 // This case isn't for branch processing, but for handling the
972 // initialization of a condition variable.
Ted Kremenekfcfb5032009-12-24 00:40:03 +0000973 VisitCondInit(cast<IfStmt>(S)->getConditionVariable(), S, Pred, Dst);
Ted Kremenek61dfbec2009-12-23 04:49:01 +0000974 break;
Zhongxing Xuc4f87062008-10-30 05:02:23 +0000975
976 case Stmt::InitListExprClass:
977 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
978 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000979
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000980 case Stmt::MemberExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000981 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
Ted Kremenek469ecbd2008-04-21 23:43:38 +0000982 break;
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000983 case Stmt::ObjCIvarRefExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000984 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000985 break;
Ted Kremenekaf337412008-11-12 19:24:17 +0000986
987 case Stmt::ObjCForCollectionStmtClass:
988 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
989 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000990
Ted Kremenek38ac4f52009-12-22 22:13:46 +0000991 case Stmt::ObjCMessageExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000992 VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000993 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000994
Ted Kremenekbbfd07a2008-12-09 20:18:58 +0000995 case Stmt::ObjCAtThrowStmtClass: {
996 // FIXME: This is not complete. We basically treat @throw as
997 // an abort.
998 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
999 Builder->BuildSinks = true;
1000 MakeNode(Dst, S, Pred, GetState(Pred));
1001 break;
1002 }
Mike Stump1eb44332009-09-09 15:08:12 +00001003
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001004 case Stmt::ReturnStmtClass:
1005 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
1006 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001007
Douglas Gregor8ecdb652010-04-28 22:16:22 +00001008 case Stmt::OffsetOfExprClass:
1009 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst);
1010 break;
1011
Sebastian Redl05189992008-11-11 17:56:53 +00001012 case Stmt::SizeOfAlignOfExprClass:
1013 VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001014 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001015
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001016 case Stmt::StmtExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001017 const StmtExpr* SE = cast<StmtExpr>(S);
Ted Kremeneka3d1eb82009-02-14 05:55:08 +00001018
1019 if (SE->getSubStmt()->body_empty()) {
1020 // Empty statement expression.
1021 assert(SE->getType() == getContext().VoidTy
1022 && "Empty statement expression must have void type.");
1023 Dst.Add(Pred);
1024 break;
1025 }
Mike Stump1eb44332009-09-09 15:08:12 +00001026
Ted Kremeneka3d1eb82009-02-14 05:55:08 +00001027 if (Expr* LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1028 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +00001029 MakeNode(Dst, SE, Pred, state->BindExpr(SE, state->getSVal(LastExpr)));
Ted Kremeneka3d1eb82009-02-14 05:55:08 +00001030 }
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001031 else
1032 Dst.Add(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00001033
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001034 break;
1035 }
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001036
Ted Kremenek892697d2010-12-16 07:46:53 +00001037 case Stmt::StringLiteralClass: {
1038 const GRState* state = GetState(Pred);
1039 SVal V = state->getLValue(cast<StringLiteral>(S));
1040 MakeNode(Dst, S, Pred, state->BindExpr(S, V));
1041 return;
1042 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001043
Ted Kremenekfcfb5032009-12-24 00:40:03 +00001044 case Stmt::SwitchStmtClass:
1045 // This case isn't for branch processing, but for handling the
1046 // initialization of a condition variable.
1047 VisitCondInit(cast<SwitchStmt>(S)->getConditionVariable(), S, Pred, Dst);
1048 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001049
Ted Kremenek72374592009-03-18 23:49:26 +00001050 case Stmt::UnaryOperatorClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001051 const UnaryOperator *U = cast<UnaryOperator>(S);
John McCall2de56d12010-08-25 11:45:40 +00001052 if (AMgr.shouldEagerlyAssume()&&(U->getOpcode() == UO_LNot)) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001053 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00001054 VisitUnaryOperator(U, Pred, Tmp);
Ted Kremenek9c149532010-12-01 21:57:22 +00001055 evalEagerlyAssume(Dst, Tmp, U);
Ted Kremenek72374592009-03-18 23:49:26 +00001056 }
1057 else
Ted Kremenek892697d2010-12-16 07:46:53 +00001058 VisitUnaryOperator(U, Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001059 break;
Ted Kremenek72374592009-03-18 23:49:26 +00001060 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001061
Ted Kremenek4c508a12009-12-24 00:54:56 +00001062 case Stmt::WhileStmtClass:
1063 // This case isn't for branch processing, but for handling the
1064 // initialization of a condition variable.
1065 VisitCondInit(cast<WhileStmt>(S)->getConditionVariable(), S, Pred, Dst);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001066 break;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001067 }
1068}
1069
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001070//===----------------------------------------------------------------------===//
1071// Block entrance. (Update counters).
1072//===----------------------------------------------------------------------===//
1073
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001074bool GRExprEngine::ProcessBlockEntrance(const CFGBlock* B,
1075 const ExplodedNode *Pred,
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001076 GRBlockCounter BC) {
Zhongxing Xud9e0c0f2010-03-23 05:05:02 +00001077 return BC.getNumVisited(Pred->getLocationContext()->getCurrentStackFrame(),
Tom Care68625cf2010-09-14 21:35:27 +00001078 B->getBlockID()) < AMgr.getMaxVisit();
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001079}
1080
1081//===----------------------------------------------------------------------===//
Ted Kremenek1670e402009-04-11 00:11:10 +00001082// Generic node creation.
1083//===----------------------------------------------------------------------===//
1084
Zhongxing Xu3992a502010-07-20 02:41:28 +00001085ExplodedNode* GRExprEngine::MakeNode(ExplodedNodeSet& Dst, const Stmt* S,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001086 ExplodedNode* Pred, const GRState* St,
1087 ProgramPoint::Kind K, const void *tag) {
Ted Kremenek1670e402009-04-11 00:11:10 +00001088 assert (Builder && "GRStmtNodeBuilder not present.");
1089 SaveAndRestore<const void*> OldTag(Builder->Tag);
1090 Builder->Tag = tag;
1091 return Builder->MakeNode(Dst, S, Pred, St, K);
1092}
1093
1094//===----------------------------------------------------------------------===//
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001095// Branch processing.
1096//===----------------------------------------------------------------------===//
1097
Ted Kremeneka8538d92009-02-13 01:45:31 +00001098const GRState* GRExprEngine::MarkBranch(const GRState* state,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001099 const Stmt* Terminator,
1100 bool branchTaken) {
Mike Stump1eb44332009-09-09 15:08:12 +00001101
Ted Kremenek05a23782008-02-26 19:05:15 +00001102 switch (Terminator->getStmtClass()) {
1103 default:
Ted Kremeneka8538d92009-02-13 01:45:31 +00001104 return state;
Mike Stump1eb44332009-09-09 15:08:12 +00001105
Ted Kremenek05a23782008-02-26 19:05:15 +00001106 case Stmt::BinaryOperatorClass: { // '&&' and '||'
Mike Stump1eb44332009-09-09 15:08:12 +00001107
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001108 const BinaryOperator* B = cast<BinaryOperator>(Terminator);
Ted Kremenek05a23782008-02-26 19:05:15 +00001109 BinaryOperator::Opcode Op = B->getOpcode();
Mike Stump1eb44332009-09-09 15:08:12 +00001110
John McCall2de56d12010-08-25 11:45:40 +00001111 assert (Op == BO_LAnd || Op == BO_LOr);
Mike Stump1eb44332009-09-09 15:08:12 +00001112
Ted Kremenek05a23782008-02-26 19:05:15 +00001113 // For &&, if we take the true branch, then the value of the whole
1114 // expression is that of the RHS expression.
1115 //
1116 // For ||, if we take the false branch, then the value of the whole
1117 // expression is that of the RHS expression.
Mike Stump1eb44332009-09-09 15:08:12 +00001118
John McCall2de56d12010-08-25 11:45:40 +00001119 const Expr* Ex = (Op == BO_LAnd && branchTaken) ||
1120 (Op == BO_LOr && !branchTaken)
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001121 ? B->getRHS() : B->getLHS();
Mike Stump1eb44332009-09-09 15:08:12 +00001122
Ted Kremenek8e029342009-08-27 22:17:37 +00001123 return state->BindExpr(B, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +00001124 }
Mike Stump1eb44332009-09-09 15:08:12 +00001125
Ted Kremenek05a23782008-02-26 19:05:15 +00001126 case Stmt::ConditionalOperatorClass: { // ?:
Mike Stump1eb44332009-09-09 15:08:12 +00001127
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001128 const ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
Mike Stump1eb44332009-09-09 15:08:12 +00001129
Ted Kremenek05a23782008-02-26 19:05:15 +00001130 // For ?, if branchTaken == true then the value is either the LHS or
1131 // the condition itself. (GNU extension).
Mike Stump1eb44332009-09-09 15:08:12 +00001132
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001133 const Expr* Ex;
Mike Stump1eb44332009-09-09 15:08:12 +00001134
Ted Kremenek05a23782008-02-26 19:05:15 +00001135 if (branchTaken)
Mike Stump1eb44332009-09-09 15:08:12 +00001136 Ex = C->getLHS() ? C->getLHS() : C->getCond();
Ted Kremenek05a23782008-02-26 19:05:15 +00001137 else
1138 Ex = C->getRHS();
Mike Stump1eb44332009-09-09 15:08:12 +00001139
Ted Kremenek8e029342009-08-27 22:17:37 +00001140 return state->BindExpr(C, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +00001141 }
Mike Stump1eb44332009-09-09 15:08:12 +00001142
Ted Kremenek05a23782008-02-26 19:05:15 +00001143 case Stmt::ChooseExprClass: { // ?:
Mike Stump1eb44332009-09-09 15:08:12 +00001144
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001145 const ChooseExpr* C = cast<ChooseExpr>(Terminator);
Mike Stump1eb44332009-09-09 15:08:12 +00001146
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001147 const Expr* Ex = branchTaken ? C->getLHS() : C->getRHS();
Ted Kremenek8e029342009-08-27 22:17:37 +00001148 return state->BindExpr(C, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +00001149 }
1150 }
1151}
1152
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001153/// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1154/// to try to recover some path-sensitivity for casts of symbolic
1155/// integers that promote their values (which are currently not tracked well).
1156/// This function returns the SVal bound to Condition->IgnoreCasts if all the
1157// cast(s) did was sign-extend the original value.
1158static SVal RecoverCastedSymbol(GRStateManager& StateMgr, const GRState* state,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001159 const Stmt* Condition, ASTContext& Ctx) {
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001160
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001161 const Expr *Ex = dyn_cast<Expr>(Condition);
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001162 if (!Ex)
1163 return UnknownVal();
1164
1165 uint64_t bits = 0;
1166 bool bitsInit = false;
Mike Stump1eb44332009-09-09 15:08:12 +00001167
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001168 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001169 QualType T = CE->getType();
1170
1171 if (!T->isIntegerType())
1172 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001173
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001174 uint64_t newBits = Ctx.getTypeSize(T);
1175 if (!bitsInit || newBits < bits) {
1176 bitsInit = true;
1177 bits = newBits;
1178 }
Mike Stump1eb44332009-09-09 15:08:12 +00001179
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001180 Ex = CE->getSubExpr();
1181 }
1182
1183 // We reached a non-cast. Is it a symbolic value?
1184 QualType T = Ex->getType();
1185
1186 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits)
1187 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001188
Ted Kremenek13976632010-02-08 16:18:51 +00001189 return state->getSVal(Ex);
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001190}
1191
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001192void GRExprEngine::ProcessBranch(const Stmt* Condition, const Stmt* Term,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001193 GRBranchNodeBuilder& builder) {
Mike Stump1eb44332009-09-09 15:08:12 +00001194
Ted Kremenekb2331832008-02-15 22:29:00 +00001195 // Check for NULL conditions; e.g. "for(;;)"
Mike Stump1eb44332009-09-09 15:08:12 +00001196 if (!Condition) {
Ted Kremenekb2331832008-02-15 22:29:00 +00001197 builder.markInfeasible(false);
Ted Kremenekb2331832008-02-15 22:29:00 +00001198 return;
1199 }
Mike Stump1eb44332009-09-09 15:08:12 +00001200
Ted Kremenek21028dd2009-03-11 03:54:24 +00001201 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1202 Condition->getLocStart(),
1203 "Error evaluating branch");
Ted Kremenek0fb0bc42009-08-27 01:39:13 +00001204
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001205 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
1206 void *tag = I->first;
1207 Checker *checker = I->second;
1208 checker->VisitBranchCondition(builder, *this, Condition, tag);
1209 }
1210
1211 // If the branch condition is undefined, return;
1212 if (!builder.isFeasible(true) && !builder.isFeasible(false))
1213 return;
1214
Mike Stump1eb44332009-09-09 15:08:12 +00001215 const GRState* PrevState = builder.getState();
Ted Kremenek13976632010-02-08 16:18:51 +00001216 SVal X = PrevState->getSVal(Condition);
Mike Stump1eb44332009-09-09 15:08:12 +00001217
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001218 if (X.isUnknown()) {
1219 // Give it a chance to recover from unknown.
1220 if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1221 if (Ex->getType()->isIntegerType()) {
1222 // Try to recover some path-sensitivity. Right now casts of symbolic
1223 // integers that promote their values are currently not tracked well.
1224 // If 'Condition' is such an expression, try and recover the
1225 // underlying value and use that instead.
1226 SVal recovered = RecoverCastedSymbol(getStateManager(),
1227 builder.getState(), Condition,
1228 getContext());
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001229
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001230 if (!recovered.isUnknown()) {
1231 X = recovered;
1232 }
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001233 }
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001234 }
1235 // If the condition is still unknown, give up.
1236 if (X.isUnknown()) {
1237 builder.generateNode(MarkBranch(PrevState, Term, true), true);
1238 builder.generateNode(MarkBranch(PrevState, Term, false), false);
Ted Kremenekb38911f2008-01-30 23:03:39 +00001239 return;
Mike Stump1eb44332009-09-09 15:08:12 +00001240 }
Ted Kremenekb38911f2008-01-30 23:03:39 +00001241 }
Mike Stump1eb44332009-09-09 15:08:12 +00001242
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001243 DefinedSVal V = cast<DefinedSVal>(X);
1244
Ted Kremenek6a6719a2008-02-29 20:27:50 +00001245 // Process the true branch.
Ted Kremenek52003542009-07-20 18:44:36 +00001246 if (builder.isFeasible(true)) {
Ted Kremenek28f47b92010-12-01 22:16:56 +00001247 if (const GRState *state = PrevState->assume(V, true))
Ted Kremenek52003542009-07-20 18:44:36 +00001248 builder.generateNode(MarkBranch(state, Term, true), true);
1249 else
1250 builder.markInfeasible(true);
1251 }
Mike Stump1eb44332009-09-09 15:08:12 +00001252
1253 // Process the false branch.
Ted Kremenek52003542009-07-20 18:44:36 +00001254 if (builder.isFeasible(false)) {
Ted Kremenek28f47b92010-12-01 22:16:56 +00001255 if (const GRState *state = PrevState->assume(V, false))
Ted Kremenek52003542009-07-20 18:44:36 +00001256 builder.generateNode(MarkBranch(state, Term, false), false);
1257 else
1258 builder.markInfeasible(false);
1259 }
Ted Kremenek71c29bd2008-01-29 23:32:35 +00001260}
1261
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001262/// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor
Ted Kremenek754607e2008-02-13 00:24:44 +00001263/// nodes by processing the 'effects' of a computed goto jump.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001264void GRExprEngine::ProcessIndirectGoto(GRIndirectGotoNodeBuilder& builder) {
Ted Kremenek754607e2008-02-13 00:24:44 +00001265
Mike Stump1eb44332009-09-09 15:08:12 +00001266 const GRState *state = builder.getState();
Ted Kremenek13976632010-02-08 16:18:51 +00001267 SVal V = state->getSVal(builder.getTarget());
Mike Stump1eb44332009-09-09 15:08:12 +00001268
Ted Kremenek754607e2008-02-13 00:24:44 +00001269 // Three possibilities:
1270 //
1271 // (1) We know the computed label.
Ted Kremenek4a4e5242008-02-28 09:25:22 +00001272 // (2) The label is NULL (or some other constant), or Undefined.
Ted Kremenek754607e2008-02-13 00:24:44 +00001273 // (3) We have no clue about the label. Dispatch to all targets.
1274 //
Mike Stump1eb44332009-09-09 15:08:12 +00001275
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001276 typedef GRIndirectGotoNodeBuilder::iterator iterator;
Ted Kremenek754607e2008-02-13 00:24:44 +00001277
Zhongxing Xu1c96b242008-10-17 05:57:07 +00001278 if (isa<loc::GotoLabel>(V)) {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001279 const LabelStmt* L = cast<loc::GotoLabel>(V).getLabel();
Mike Stump1eb44332009-09-09 15:08:12 +00001280
Ted Kremenek754607e2008-02-13 00:24:44 +00001281 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) {
Ted Kremenek24f1a962008-02-13 17:27:37 +00001282 if (I.getLabel() == L) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001283 builder.generateNode(I, state);
Ted Kremenek754607e2008-02-13 00:24:44 +00001284 return;
1285 }
1286 }
Mike Stump1eb44332009-09-09 15:08:12 +00001287
Ted Kremenek754607e2008-02-13 00:24:44 +00001288 assert (false && "No block with label.");
1289 return;
1290 }
1291
Zhongxing Xu1c96b242008-10-17 05:57:07 +00001292 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
Ted Kremenek754607e2008-02-13 00:24:44 +00001293 // Dispatch to the first target and mark it as a sink.
Zhongxing Xu2055eff2009-11-24 07:06:39 +00001294 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1295 // FIXME: add checker visit.
1296 // UndefBranches.insert(N);
Ted Kremenek754607e2008-02-13 00:24:44 +00001297 return;
1298 }
Mike Stump1eb44332009-09-09 15:08:12 +00001299
Ted Kremenek754607e2008-02-13 00:24:44 +00001300 // This is really a catch-all. We don't support symbolics yet.
Ted Kremenekb3cfd582009-04-23 17:49:43 +00001301 // FIXME: Implement dispatch for symbolic pointers.
Mike Stump1eb44332009-09-09 15:08:12 +00001302
Ted Kremenek754607e2008-02-13 00:24:44 +00001303 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
Ted Kremeneka8538d92009-02-13 01:45:31 +00001304 builder.generateNode(I, state);
Ted Kremenek754607e2008-02-13 00:24:44 +00001305}
Ted Kremenekf233d482008-02-05 00:26:40 +00001306
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001307
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001308void GRExprEngine::VisitGuardedExpr(const Expr* Ex, const Expr* L,
1309 const Expr* R,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001310 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001311
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001312 assert(Ex == currentStmt &&
Zhongxing Xubb141212009-12-16 11:27:52 +00001313 Pred->getLocationContext()->getCFG()->isBlkExpr(Ex));
Mike Stump1eb44332009-09-09 15:08:12 +00001314
Ted Kremeneka8538d92009-02-13 01:45:31 +00001315 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +00001316 SVal X = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00001317
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001318 assert (X.isUndef());
Mike Stump1eb44332009-09-09 15:08:12 +00001319
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001320 const Expr *SE = (Expr*) cast<UndefinedVal>(X).getData();
Mike Stump1eb44332009-09-09 15:08:12 +00001321 assert(SE);
Ted Kremenek13976632010-02-08 16:18:51 +00001322 X = state->getSVal(SE);
Mike Stump1eb44332009-09-09 15:08:12 +00001323
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001324 // Make sure that we invalidate the previous binding.
Ted Kremenek8e029342009-08-27 22:17:37 +00001325 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, X, true));
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001326}
1327
Ted Kremenek73099bf2009-11-14 01:05:20 +00001328/// ProcessEndPath - Called by GRCoreEngine. Used to generate end-of-path
1329/// nodes when the control reaches the end of a function.
1330void GRExprEngine::ProcessEndPath(GREndPathNodeBuilder& builder) {
Ted Kremenek9c149532010-12-01 21:57:22 +00001331 getTF().evalEndPath(*this, builder);
Ted Kremenek73099bf2009-11-14 01:05:20 +00001332 StateMgr.EndPath(builder.getState());
Zhongxing Xu243fde92009-11-17 07:54:15 +00001333 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E;++I){
1334 void *tag = I->first;
1335 Checker *checker = I->second;
Ted Kremenek9c149532010-12-01 21:57:22 +00001336 checker->evalEndPath(builder, tag, *this);
Zhongxing Xu243fde92009-11-17 07:54:15 +00001337 }
Ted Kremenek73099bf2009-11-14 01:05:20 +00001338}
1339
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001340/// ProcessSwitch - Called by GRCoreEngine. Used to generate successor
1341/// nodes by processing the 'effects' of a switch statement.
Mike Stump1eb44332009-09-09 15:08:12 +00001342void GRExprEngine::ProcessSwitch(GRSwitchNodeBuilder& builder) {
1343 typedef GRSwitchNodeBuilder::iterator iterator;
1344 const GRState* state = builder.getState();
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001345 const Expr* CondE = builder.getCondition();
Ted Kremenek13976632010-02-08 16:18:51 +00001346 SVal CondV_untested = state->getSVal(CondE);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001347
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001348 if (CondV_untested.isUndef()) {
Zhongxing Xu2055eff2009-11-24 07:06:39 +00001349 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001350 // FIXME: add checker
Zhongxing Xu2055eff2009-11-24 07:06:39 +00001351 //UndefBranches.insert(N);
1352
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001353 return;
1354 }
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001355 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested);
Ted Kremenek692416c2008-02-18 22:57:02 +00001356
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001357 const GRState *DefaultSt = state;
Ted Kremenek34feff62010-08-26 22:19:33 +00001358
1359 iterator I = builder.begin(), EI = builder.end();
1360 bool defaultIsFeasible = I == EI;
Mike Stump1eb44332009-09-09 15:08:12 +00001361
Ted Kremenek34feff62010-08-26 22:19:33 +00001362 for ( ; I != EI; ++I) {
Ted Kremenek41271172010-08-26 22:04:01 +00001363 const CaseStmt* Case = I.getCase();
Ted Kremenek72afb372009-01-17 01:54:16 +00001364
1365 // Evaluate the LHS of the case value.
1366 Expr::EvalResult V1;
Mike Stump1eb44332009-09-09 15:08:12 +00001367 bool b = Case->getLHS()->Evaluate(V1, getContext());
1368
Ted Kremenek72afb372009-01-17 01:54:16 +00001369 // Sanity checks. These go away in Release builds.
Mike Stump1eb44332009-09-09 15:08:12 +00001370 assert(b && V1.Val.isInt() && !V1.HasSideEffects
Ted Kremenek72afb372009-01-17 01:54:16 +00001371 && "Case condition must evaluate to an integer constant.");
Mike Stump1eb44332009-09-09 15:08:12 +00001372 b = b; // silence unused variable warning
1373 assert(V1.Val.getInt().getBitWidth() ==
Ted Kremenek72afb372009-01-17 01:54:16 +00001374 getContext().getTypeSize(CondE->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00001375
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001376 // Get the RHS of the case, if it exists.
Ted Kremenek72afb372009-01-17 01:54:16 +00001377 Expr::EvalResult V2;
Mike Stump1eb44332009-09-09 15:08:12 +00001378
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001379 if (const Expr* E = Case->getRHS()) {
Ted Kremenek72afb372009-01-17 01:54:16 +00001380 b = E->Evaluate(V2, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +00001381 assert(b && V2.Val.isInt() && !V2.HasSideEffects
Ted Kremenek72afb372009-01-17 01:54:16 +00001382 && "Case condition must evaluate to an integer constant.");
1383 b = b; // silence unused variable warning
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001384 }
Ted Kremenek14a11402008-03-17 22:17:56 +00001385 else
1386 V2 = V1;
Mike Stump1eb44332009-09-09 15:08:12 +00001387
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001388 // FIXME: Eventually we should replace the logic below with a range
1389 // comparison, rather than concretize the values within the range.
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001390 // This should be easy once we have "ranges" for NonLVals.
Mike Stump1eb44332009-09-09 15:08:12 +00001391
Ted Kremenek14a11402008-03-17 22:17:56 +00001392 do {
Mike Stump1eb44332009-09-09 15:08:12 +00001393 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1.Val.getInt()));
Ted Kremenek9c149532010-12-01 21:57:22 +00001394 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
Ted Kremenek48569f92010-01-08 18:54:04 +00001395 CondV, CaseVal);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001396
Mike Stump1eb44332009-09-09 15:08:12 +00001397 // Now "assume" that the case matches.
Ted Kremenek28f47b92010-12-01 22:16:56 +00001398 if (const GRState* stateNew = state->assume(Res, true)) {
Ted Kremeneka591bc02009-06-18 22:57:13 +00001399 builder.generateCaseStmtNode(I, stateNew);
Mike Stump1eb44332009-09-09 15:08:12 +00001400
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001401 // If CondV evaluates to a constant, then we know that this
1402 // is the *only* case that we can take, so stop evaluating the
1403 // others.
Zhongxing Xu1c96b242008-10-17 05:57:07 +00001404 if (isa<nonloc::ConcreteInt>(CondV))
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001405 return;
1406 }
Mike Stump1eb44332009-09-09 15:08:12 +00001407
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001408 // Now "assume" that the case doesn't match. Add this state
1409 // to the default state (if it is feasible).
Ted Kremenek48569f92010-01-08 18:54:04 +00001410 if (DefaultSt) {
Ted Kremenek28f47b92010-12-01 22:16:56 +00001411 if (const GRState *stateNew = DefaultSt->assume(Res, false)) {
Ted Kremenek48569f92010-01-08 18:54:04 +00001412 defaultIsFeasible = true;
1413 DefaultSt = stateNew;
1414 }
1415 else {
1416 defaultIsFeasible = false;
1417 DefaultSt = NULL;
1418 }
Ted Kremenek5014ab12008-04-23 05:03:18 +00001419 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001420
Ted Kremenek14a11402008-03-17 22:17:56 +00001421 // Concretize the next value in the range.
Ted Kremenek72afb372009-01-17 01:54:16 +00001422 if (V1.Val.getInt() == V2.Val.getInt())
Ted Kremenek14a11402008-03-17 22:17:56 +00001423 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001424
Ted Kremenek72afb372009-01-17 01:54:16 +00001425 ++V1.Val.getInt();
1426 assert (V1.Val.getInt() <= V2.Val.getInt());
Mike Stump1eb44332009-09-09 15:08:12 +00001427
Ted Kremenek14a11402008-03-17 22:17:56 +00001428 } while (true);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001429 }
Mike Stump1eb44332009-09-09 15:08:12 +00001430
Ted Kremenek4d3175c2010-09-09 00:40:40 +00001431 if (!defaultIsFeasible)
1432 return;
1433
1434 // If we have switch(enum value), the default branch is not
1435 // feasible if all of the enum constants not covered by 'case:' statements
1436 // are not feasible values for the switch condition.
1437 //
1438 // Note that this isn't as accurate as it could be. Even if there isn't
1439 // a case for a particular enum value as long as that enum value isn't
1440 // feasible then it shouldn't be considered for making 'default:' reachable.
1441 const SwitchStmt *SS = builder.getSwitch();
1442 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1443 if (CondExpr->getType()->getAs<EnumType>()) {
1444 if (SS->isAllEnumCasesCovered())
1445 return;
1446 }
1447
1448 builder.generateDefaultCaseNode(DefaultSt);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001449}
1450
Douglas Gregor102acd52010-02-25 19:01:53 +00001451void GRExprEngine::ProcessCallEnter(GRCallEnterNodeBuilder &B) {
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001452 const GRState *state = B.getState()->EnterStackFrame(B.getCalleeContext());
Ted Kremenekd048c6e2010-12-20 21:19:09 +00001453 B.generateNode(state);
Douglas Gregor102acd52010-02-25 19:01:53 +00001454}
1455
1456void GRExprEngine::ProcessCallExit(GRCallExitNodeBuilder &B) {
1457 const GRState *state = B.getState();
1458 const ExplodedNode *Pred = B.getPredecessor();
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001459 const StackFrameContext *calleeCtx =
Douglas Gregor102acd52010-02-25 19:01:53 +00001460 cast<StackFrameContext>(Pred->getLocationContext());
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001461 const Stmt *CE = calleeCtx->getCallSite();
Douglas Gregor102acd52010-02-25 19:01:53 +00001462
Zhongxing Xu6190ec22010-02-26 15:43:34 +00001463 // If the callee returns an expression, bind its value to CallExpr.
1464 const Stmt *ReturnedExpr = state->get<ReturnExpr>();
1465 if (ReturnedExpr) {
1466 SVal RetVal = state->getSVal(ReturnedExpr);
1467 state = state->BindExpr(CE, RetVal);
Zhongxing Xubd2b2082010-03-23 08:09:29 +00001468 // Clear the return expr GDM.
Zhongxing Xu0541d102010-03-25 01:39:39 +00001469 state = state->remove<ReturnExpr>();
Zhongxing Xu6190ec22010-02-26 15:43:34 +00001470 }
1471
Zhongxing Xu8e18c1b2010-03-23 09:13:17 +00001472 // Bind the constructed object value to CXXConstructExpr.
1473 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
Zhongxing Xu9dc84c92010-11-16 07:52:17 +00001474 const CXXThisRegion *ThisR =
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001475 getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx);
Zhongxing Xud7064342010-11-24 13:08:51 +00001476
Zhongxing Xu8e18c1b2010-03-23 09:13:17 +00001477 SVal ThisV = state->getSVal(ThisR);
Zhongxing Xu05e53912010-12-22 07:20:27 +00001478 // Always bind the region to the CXXConstructExpr.
1479 state = state->BindExpr(CCE, ThisV);
Zhongxing Xu8e18c1b2010-03-23 09:13:17 +00001480 }
1481
Ted Kremenekd048c6e2010-12-20 21:19:09 +00001482 B.generateNode(state);
Douglas Gregor102acd52010-02-25 19:01:53 +00001483}
1484
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001485//===----------------------------------------------------------------------===//
1486// Transfer functions: logical operations ('&&', '||').
1487//===----------------------------------------------------------------------===//
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001488
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001489void GRExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode* Pred,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001490 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001491
John McCall2de56d12010-08-25 11:45:40 +00001492 assert(B->getOpcode() == BO_LAnd ||
1493 B->getOpcode() == BO_LOr);
Mike Stump1eb44332009-09-09 15:08:12 +00001494
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001495 assert(B==currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(B));
Mike Stump1eb44332009-09-09 15:08:12 +00001496
Ted Kremeneka8538d92009-02-13 01:45:31 +00001497 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +00001498 SVal X = state->getSVal(B);
Ted Kremenek3ff12592009-06-19 17:10:32 +00001499 assert(X.isUndef());
Mike Stump1eb44332009-09-09 15:08:12 +00001500
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001501 const Expr *Ex = (const Expr*) cast<UndefinedVal>(X).getData();
Ted Kremenek3ff12592009-06-19 17:10:32 +00001502 assert(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00001503
Ted Kremenek05a23782008-02-26 19:05:15 +00001504 if (Ex == B->getRHS()) {
Ted Kremenek13976632010-02-08 16:18:51 +00001505 X = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00001506
Ted Kremenek4a4e5242008-02-28 09:25:22 +00001507 // Handle undefined values.
Ted Kremenek4a4e5242008-02-28 09:25:22 +00001508 if (X.isUndef()) {
Ted Kremenek8e029342009-08-27 22:17:37 +00001509 MakeNode(Dst, B, Pred, state->BindExpr(B, X));
Ted Kremenek58b33212008-02-26 19:40:44 +00001510 return;
1511 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001512
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001513 DefinedOrUnknownSVal XD = cast<DefinedOrUnknownSVal>(X);
Mike Stump1eb44332009-09-09 15:08:12 +00001514
Ted Kremenek05a23782008-02-26 19:05:15 +00001515 // We took the RHS. Because the value of the '&&' or '||' expression must
1516 // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
1517 // or 1. Alternatively, we could take a lazy approach, and calculate this
1518 // value later when necessary. We don't have the machinery in place for
1519 // this right now, and since most logical expressions are used for branches,
Mike Stump1eb44332009-09-09 15:08:12 +00001520 // the payoff is not likely to be large. Instead, we do eager evaluation.
Ted Kremenek28f47b92010-12-01 22:16:56 +00001521 if (const GRState *newState = state->assume(XD, true))
Mike Stump1eb44332009-09-09 15:08:12 +00001522 MakeNode(Dst, B, Pred,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001523 newState->BindExpr(B, svalBuilder.makeIntVal(1U, B->getType())));
Mike Stump1eb44332009-09-09 15:08:12 +00001524
Ted Kremenek28f47b92010-12-01 22:16:56 +00001525 if (const GRState *newState = state->assume(XD, false))
Mike Stump1eb44332009-09-09 15:08:12 +00001526 MakeNode(Dst, B, Pred,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001527 newState->BindExpr(B, svalBuilder.makeIntVal(0U, B->getType())));
Ted Kremenekf233d482008-02-05 00:26:40 +00001528 }
1529 else {
Ted Kremenek05a23782008-02-26 19:05:15 +00001530 // We took the LHS expression. Depending on whether we are '&&' or
1531 // '||' we know what the value of the expression is via properties of
1532 // the short-circuiting.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001533 X = svalBuilder.makeIntVal(B->getOpcode() == BO_LAnd ? 0U : 1U,
Zhongxing Xud91ee272009-06-23 09:02:15 +00001534 B->getType());
Ted Kremenek8e029342009-08-27 22:17:37 +00001535 MakeNode(Dst, B, Pred, state->BindExpr(B, X));
Ted Kremenekf233d482008-02-05 00:26:40 +00001536 }
Ted Kremenekf233d482008-02-05 00:26:40 +00001537}
Mike Stump1eb44332009-09-09 15:08:12 +00001538
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001539//===----------------------------------------------------------------------===//
Ted Kremenekec96a2d2008-04-16 18:39:06 +00001540// Transfer functions: Loads and stores.
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001541//===----------------------------------------------------------------------===//
Ted Kremenekd27f8162008-01-15 23:55:06 +00001542
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001543void GRExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001544 ExplodedNodeSet &Dst) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001545
Ted Kremenek66078612009-11-25 22:23:25 +00001546 ExplodedNodeSet Tmp;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001547
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001548 CanQualType T = getContext().getCanonicalType(BE->getType());
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001549 SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T,
Ted Kremenek0a8112a2009-11-25 23:53:07 +00001550 Pred->getLocationContext());
1551
Ted Kremenek66078612009-11-25 22:23:25 +00001552 MakeNode(Tmp, BE, Pred, GetState(Pred)->BindExpr(BE, V),
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001553 ProgramPoint::PostLValueKind);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001554
Ted Kremenek66078612009-11-25 22:23:25 +00001555 // Post-visit the BlockExpr.
Jordy Rose72905cf2010-08-04 07:10:57 +00001556 CheckerVisit(BE, Dst, Tmp, PostVisitStmtCallback);
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001557}
1558
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001559void GRExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
Ted Kremenek67d12872009-12-07 22:05:27 +00001560 ExplodedNode *Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00001561 ExplodedNodeSet &Dst) {
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001562 const GRState *state = GetState(Pred);
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001563
1564 if (const VarDecl* VD = dyn_cast<VarDecl>(D)) {
Ted Kremenek892697d2010-12-16 07:46:53 +00001565 assert(Ex->isLValue());
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001566 SVal V = state->getLValue(VD, Pred->getLocationContext());
Zhongxing Xua7581732008-10-17 02:20:14 +00001567
Ted Kremenek892697d2010-12-16 07:46:53 +00001568 // For references, the 'lvalue' is the pointer address stored in the
1569 // reference region.
1570 if (VD->getType()->isReferenceType()) {
1571 if (const MemRegion *R = V.getAsRegion())
1572 V = state->getSVal(R);
1573 else
1574 V = UnknownVal();
Ted Kremenek852274d2009-12-16 03:18:58 +00001575 }
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001576
Ted Kremenek892697d2010-12-16 07:46:53 +00001577 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V),
1578 ProgramPoint::PostLValueKind);
Ted Kremenek852274d2009-12-16 03:18:58 +00001579 return;
Ted Kremenek892697d2010-12-16 07:46:53 +00001580 }
1581 if (const EnumConstantDecl* ED = dyn_cast<EnumConstantDecl>(D)) {
1582 assert(!Ex->isLValue());
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001583 SVal V = svalBuilder.makeIntVal(ED->getInitVal());
Ted Kremenek8e029342009-08-27 22:17:37 +00001584 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V));
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001585 return;
Ted Kremenek892697d2010-12-16 07:46:53 +00001586 }
1587 if (const FunctionDecl* FD = dyn_cast<FunctionDecl>(D)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001588 SVal V = svalBuilder.getFunctionPointer(FD);
Ted Kremenek8e029342009-08-27 22:17:37 +00001589 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V),
Ted Kremenek7090d542009-05-07 18:27:16 +00001590 ProgramPoint::PostLValueKind);
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001591 return;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001592 }
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001593 assert (false &&
1594 "ValueDecl support for this ValueDecl not implemented.");
Ted Kremenek3271f8d2008-02-07 04:16:04 +00001595}
1596
Ted Kremenek540cbe22008-04-22 04:56:29 +00001597/// VisitArraySubscriptExpr - Transfer function for array accesses
Ted Kremenek892697d2010-12-16 07:46:53 +00001598void GRExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr* A,
1599 ExplodedNode* Pred,
1600 ExplodedNodeSet& Dst){
Mike Stump1eb44332009-09-09 15:08:12 +00001601
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001602 const Expr* Base = A->getBase()->IgnoreParens();
1603 const Expr* Idx = A->getIdx()->IgnoreParens();
Ted Kremenek892697d2010-12-16 07:46:53 +00001604
1605 // Evaluate the base.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001606 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00001607 Visit(Base, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00001608
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001609 for (ExplodedNodeSet::iterator I1=Tmp.begin(), E1=Tmp.end(); I1!=E1; ++I1) {
1610 ExplodedNodeSet Tmp2;
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001611 Visit(Idx, *I1, Tmp2); // Evaluate the index.
Zhongxing Xud6944852009-11-11 13:42:54 +00001612 ExplodedNodeSet Tmp3;
Jordy Rose72905cf2010-08-04 07:10:57 +00001613 CheckerVisit(A, Tmp3, Tmp2, PreVisitStmtCallback);
Zhongxing Xud6944852009-11-11 13:42:54 +00001614
1615 for (ExplodedNodeSet::iterator I2=Tmp3.begin(),E2=Tmp3.end();I2!=E2; ++I2) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001616 const GRState* state = GetState(*I2);
Ted Kremenek13976632010-02-08 16:18:51 +00001617 SVal V = state->getLValue(A->getType(), state->getSVal(Idx),
1618 state->getSVal(Base));
Ted Kremenek892697d2010-12-16 07:46:53 +00001619 assert(A->isLValue());
1620 MakeNode(Dst, A, *I2, state->BindExpr(A, V), ProgramPoint::PostLValueKind);
Ted Kremenek4d0348b2008-04-29 23:24:44 +00001621 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001622 }
Ted Kremenek540cbe22008-04-22 04:56:29 +00001623}
1624
Ted Kremenek469ecbd2008-04-21 23:43:38 +00001625/// VisitMemberExpr - Transfer function for member expressions.
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001626void GRExprEngine::VisitMemberExpr(const MemberExpr* M, ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00001627 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001628
Ted Kremenek892697d2010-12-16 07:46:53 +00001629 Expr *baseExpr = M->getBase()->IgnoreParens();
1630 ExplodedNodeSet dstBase;
1631 Visit(baseExpr, Pred, dstBase);
Mike Stump1eb44332009-09-09 15:08:12 +00001632
Ted Kremenek892697d2010-12-16 07:46:53 +00001633 FieldDecl *field = dyn_cast<FieldDecl>(M->getMemberDecl());
1634 if (!field) // FIXME: skipping member expressions for non-fields
Douglas Gregor86f19402008-12-20 23:49:58 +00001635 return;
1636
Ted Kremenek892697d2010-12-16 07:46:53 +00001637 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end();
1638 I != E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001639 const GRState* state = GetState(*I);
Ted Kremenek892697d2010-12-16 07:46:53 +00001640 SVal baseExprVal = state->getSVal(baseExpr);
1641 if (isa<nonloc::LazyCompoundVal>(baseExprVal) ||
1642 isa<nonloc::CompoundVal>(baseExprVal)) {
1643 MakeNode(Dst, M, *I, state->BindExpr(M, UnknownVal()));
1644 continue;
1645 }
1646
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001647 // FIXME: Should we insert some assumption logic in here to determine
1648 // if "Base" is a valid piece of memory? Before we put this assumption
Douglas Gregor86f19402008-12-20 23:49:58 +00001649 // later when using FieldOffset lvals (which we no longer have).
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001650
Ted Kremenek892697d2010-12-16 07:46:53 +00001651 // For all other cases, compute an lvalue.
1652 SVal L = state->getLValue(field, baseExprVal);
1653 if (M->isLValue())
Zhongxing Xu662174ca2009-10-30 07:19:39 +00001654 MakeNode(Dst, M, *I, state->BindExpr(M, L), ProgramPoint::PostLValueKind);
1655 else
Ted Kremenek9c149532010-12-01 21:57:22 +00001656 evalLoad(Dst, M, *I, state, L);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001657 }
Ted Kremenek469ecbd2008-04-21 23:43:38 +00001658}
1659
Ted Kremenek9c149532010-12-01 21:57:22 +00001660/// evalBind - Handle the semantics of binding a value to a specific location.
1661/// This method is used by evalStore and (soon) VisitDeclStmt, and others.
1662void GRExprEngine::evalBind(ExplodedNodeSet& Dst, const Stmt* StoreE,
Ted Kremenek79d73042010-09-02 00:56:20 +00001663 ExplodedNode* Pred, const GRState* state,
1664 SVal location, SVal Val, bool atDeclInit) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001665
1666
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001667 // Do a previsit of the bind.
1668 ExplodedNodeSet CheckedSet, Src;
1669 Src.Add(Pred);
Ted Kremenek79d73042010-09-02 00:56:20 +00001670 CheckerVisitBind(StoreE, CheckedSet, Src, location, Val, true);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001671
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001672 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1673 I!=E; ++I) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001674
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001675 if (Pred != *I)
1676 state = GetState(*I);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001677
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001678 const GRState* newState = 0;
Ted Kremeneka8538d92009-02-13 01:45:31 +00001679
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001680 if (atDeclInit) {
1681 const VarRegion *VR =
1682 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001683
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001684 newState = state->bindDecl(VR, Val);
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001685 }
1686 else {
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001687 if (location.isUnknown()) {
1688 // We know that the new state will be the same as the old state since
1689 // the location of the binding is "unknown". Consequently, there
1690 // is no reason to just create a new node.
1691 newState = state;
1692 }
1693 else {
1694 // We are binding to a value other than 'unknown'. Perform the binding
1695 // using the StoreManager.
1696 newState = state->bindLoc(cast<Loc>(location), Val);
1697 }
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001698 }
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001699
1700 // The next thing to do is check if the GRTransferFuncs object wants to
1701 // update the state based on the new binding. If the GRTransferFunc object
1702 // doesn't do anything, just auto-propagate the current state.
Ted Kremenek79d73042010-09-02 00:56:20 +00001703
1704 // NOTE: We use 'AssignE' for the location of the PostStore if 'AssignE'
1705 // is non-NULL. Checkers typically care about
1706
Ted Kremenek50ecd152009-11-05 00:42:23 +00001707 GRStmtNodeBuilderRef BuilderRef(Dst, *Builder, *this, *I, newState, StoreE,
Ted Kremenek96ebad62010-09-09 07:13:00 +00001708 true);
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001709
Ted Kremenek9c149532010-12-01 21:57:22 +00001710 getTF().evalBind(BuilderRef, location, Val);
Ted Kremenek41573eb2009-02-14 01:43:44 +00001711 }
Ted Kremeneka8538d92009-02-13 01:45:31 +00001712}
1713
Ted Kremenek9c149532010-12-01 21:57:22 +00001714/// evalStore - Handle the semantics of a store via an assignment.
Ted Kremeneka8538d92009-02-13 01:45:31 +00001715/// @param Dst The node set to store generated state nodes
Zhongxing Xue8a4d7d2010-09-02 01:56:39 +00001716/// @param AssignE The assignment expression if the store happens in an
1717/// assignment.
1718/// @param LocatioinE The location expression that is stored to.
Ted Kremeneka8538d92009-02-13 01:45:31 +00001719/// @param state The current simulation state
1720/// @param location The location to store the value
1721/// @param Val The value to be stored
Ted Kremenek9c149532010-12-01 21:57:22 +00001722void GRExprEngine::evalStore(ExplodedNodeSet& Dst, const Expr *AssignE,
Ted Kremenek79d73042010-09-02 00:56:20 +00001723 const Expr* LocationE,
Ted Kremenek50ecd152009-11-05 00:42:23 +00001724 ExplodedNode* Pred,
Ted Kremenek1670e402009-04-11 00:11:10 +00001725 const GRState* state, SVal location, SVal Val,
1726 const void *tag) {
Mike Stump1eb44332009-09-09 15:08:12 +00001727
Ted Kremenek50ecd152009-11-05 00:42:23 +00001728 assert(Builder && "GRStmtNodeBuilder must be defined.");
Mike Stump1eb44332009-09-09 15:08:12 +00001729
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001730 // Evaluate the location (checks for bad dereferences).
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001731 ExplodedNodeSet Tmp;
Ted Kremenek9c149532010-12-01 21:57:22 +00001732 evalLocation(Tmp, LocationE, Pred, state, location, tag, false);
Mike Stump1eb44332009-09-09 15:08:12 +00001733
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001734 if (Tmp.empty())
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001735 return;
Ted Kremenekb0533962008-04-18 20:35:30 +00001736
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001737 assert(!location.isUndef());
Ted Kremeneka8538d92009-02-13 01:45:31 +00001738
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001739 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind,
1740 ProgramPoint::PostStoreKind);
1741 SaveAndRestore<const void*> OldTag(Builder->Tag, tag);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001742
Ted Kremenek79d73042010-09-02 00:56:20 +00001743 // Proceed with the store. We use AssignE as the anchor for the PostStore
1744 // ProgramPoint if it is non-NULL, and LocationE otherwise.
1745 const Expr *StoreE = AssignE ? AssignE : LocationE;
1746
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001747 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
Ted Kremenek9c149532010-12-01 21:57:22 +00001748 evalBind(Dst, StoreE, *NI, GetState(*NI), location, Val);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001749}
1750
Ted Kremenek9c149532010-12-01 21:57:22 +00001751void GRExprEngine::evalLoad(ExplodedNodeSet& Dst, const Expr *Ex,
Zhongxing Xu3992a502010-07-20 02:41:28 +00001752 ExplodedNode* Pred,
Ted Kremenek1670e402009-04-11 00:11:10 +00001753 const GRState* state, SVal location,
Zhongxing Xu652be342009-11-16 04:49:44 +00001754 const void *tag, QualType LoadTy) {
Zhanyong Wancca8ab12010-11-24 01:47:11 +00001755 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001756
Ted Kremenek852274d2009-12-16 03:18:58 +00001757 // Are we loading from a region? This actually results in two loads; one
1758 // to fetch the address of the referenced value and one to fetch the
1759 // referenced value.
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001760 if (const TypedRegion *TR =
Ted Kremenek852274d2009-12-16 03:18:58 +00001761 dyn_cast_or_null<TypedRegion>(location.getAsRegion())) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001762
Zhongxing Xu018220c2010-08-11 06:10:55 +00001763 QualType ValTy = TR->getValueType();
Ted Kremenek852274d2009-12-16 03:18:58 +00001764 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001765 static int loadReferenceTag = 0;
Ted Kremenek852274d2009-12-16 03:18:58 +00001766 ExplodedNodeSet Tmp;
Ted Kremenek9c149532010-12-01 21:57:22 +00001767 evalLoadCommon(Tmp, Ex, Pred, state, location, &loadReferenceTag,
Ted Kremenek852274d2009-12-16 03:18:58 +00001768 getContext().getPointerType(RT->getPointeeType()));
1769
1770 // Perform the load from the referenced value.
1771 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
1772 state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00001773 location = state->getSVal(Ex);
Ted Kremenek9c149532010-12-01 21:57:22 +00001774 evalLoadCommon(Dst, Ex, *I, state, location, tag, LoadTy);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001775 }
Ted Kremenek852274d2009-12-16 03:18:58 +00001776 return;
1777 }
1778 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001779
Ted Kremenek9c149532010-12-01 21:57:22 +00001780 evalLoadCommon(Dst, Ex, Pred, state, location, tag, LoadTy);
Ted Kremenek852274d2009-12-16 03:18:58 +00001781}
1782
Ted Kremenek9c149532010-12-01 21:57:22 +00001783void GRExprEngine::evalLoadCommon(ExplodedNodeSet& Dst, const Expr *Ex,
Ted Kremenek852274d2009-12-16 03:18:58 +00001784 ExplodedNode* Pred,
1785 const GRState* state, SVal location,
1786 const void *tag, QualType LoadTy) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001787
Mike Stump1eb44332009-09-09 15:08:12 +00001788 // Evaluate the location (checks for bad dereferences).
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001789 ExplodedNodeSet Tmp;
Ted Kremenek9c149532010-12-01 21:57:22 +00001790 evalLocation(Tmp, Ex, Pred, state, location, tag, true);
Mike Stump1eb44332009-09-09 15:08:12 +00001791
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001792 if (Tmp.empty())
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001793 return;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001794
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001795 assert(!location.isUndef());
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001796
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001797 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind);
1798 SaveAndRestore<const void*> OldTag(Builder->Tag);
Mike Stump1eb44332009-09-09 15:08:12 +00001799
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001800 // Proceed with the load.
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001801 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1802 state = GetState(*NI);
Ted Kremenek96ebad62010-09-09 07:13:00 +00001803
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001804 if (location.isUnknown()) {
1805 // This is important. We must nuke the old binding.
1806 MakeNode(Dst, Ex, *NI, state->BindExpr(Ex, UnknownVal()),
1807 ProgramPoint::PostLoadKind, tag);
1808 }
1809 else {
Ted Kremenek96ebad62010-09-09 07:13:00 +00001810 if (LoadTy.isNull())
1811 LoadTy = Ex->getType();
1812 SVal V = state->getSVal(cast<Loc>(location), LoadTy);
1813 MakeNode(Dst, Ex, *NI, state->bindExprAndLocation(Ex, location, V),
1814 ProgramPoint::PostLoadKind, tag);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001815 }
Zhongxing Xud5b499d2008-11-28 08:34:30 +00001816 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001817}
1818
Ted Kremenek9c149532010-12-01 21:57:22 +00001819void GRExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *S,
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001820 ExplodedNode* Pred,
1821 const GRState* state, SVal location,
1822 const void *tag, bool isLoad) {
Zhongxing Xu00b1ad22009-11-20 03:50:46 +00001823 // Early checks for performance reason.
1824 if (location.isUnknown() || Checkers.empty()) {
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001825 Dst.Add(Pred);
1826 return;
Ted Kremenek0296c222009-11-02 23:19:29 +00001827 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001828
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001829 ExplodedNodeSet Src, Tmp;
1830 Src.Add(Pred);
1831 ExplodedNodeSet *PrevSet = &Src;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001832
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001833 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E; ++I)
1834 {
Ted Kremenek17f4da82009-12-09 02:45:41 +00001835 ExplodedNodeSet *CurrSet = 0;
1836 if (I+1 == E)
1837 CurrSet = &Dst;
1838 else {
1839 CurrSet = (PrevSet == &Tmp) ? &Src : &Tmp;
1840 CurrSet->clear();
1841 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001842
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001843 void *tag = I->first;
1844 Checker *checker = I->second;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001845
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001846 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
Ted Kremenek19d67b52009-11-23 22:22:01 +00001847 NI != NE; ++NI) {
1848 // Use the 'state' argument only when the predecessor node is the
1849 // same as Pred. This allows us to catch updates to the state.
Ted Kremenek342e9072010-12-20 21:22:47 +00001850 checker->GR_visitLocation(*CurrSet, *Builder, *this, S, *NI,
Ted Kremenek19d67b52009-11-23 22:22:01 +00001851 *NI == Pred ? state : GetState(*NI),
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001852 location, tag, isLoad);
Ted Kremenek19d67b52009-11-23 22:22:01 +00001853 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001854
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001855 // Update which NodeSet is the current one.
1856 PrevSet = CurrSet;
1857 }
Ted Kremenekec96a2d2008-04-16 18:39:06 +00001858}
1859
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001860bool GRExprEngine::InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE,
1861 ExplodedNode *Pred) {
1862 const GRState *state = GetState(Pred);
1863 const Expr *Callee = CE->getCallee();
1864 SVal L = state->getSVal(Callee);
1865
1866 const FunctionDecl *FD = L.getAsFunctionDecl();
1867 if (!FD)
1868 return false;
1869
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001870 // Check if the function definition is in the same translation unit.
1871 if (FD->hasBody(FD)) {
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001872 const StackFrameContext *stackFrame =
1873 AMgr.getStackFrame(AMgr.getAnalysisContext(FD),
1874 Pred->getLocationContext(),
Ted Kremenek892697d2010-12-16 07:46:53 +00001875 CE, Builder->getBlock(), Builder->getIndex());
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001876 // Now we have the definition of the callee, create a CallEnter node.
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001877 CallEnter Loc(CE, stackFrame, Pred->getLocationContext());
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001878
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001879 ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001880 Dst.Add(N);
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001881 return true;
1882 }
1883
1884 // Check if we can find the function definition in other translation units.
1885 if (AMgr.hasIndexer()) {
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001886 AnalysisContext *C = AMgr.getAnalysisContextInAnotherTU(FD);
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001887 if (C == 0)
1888 return false;
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001889 const StackFrameContext *stackFrame =
1890 AMgr.getStackFrame(C, Pred->getLocationContext(),
Ted Kremenek892697d2010-12-16 07:46:53 +00001891 CE, Builder->getBlock(), Builder->getIndex());
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001892 CallEnter Loc(CE, stackFrame, Pred->getLocationContext());
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001893 ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
1894 Dst.Add(N);
1895 return true;
1896 }
1897
1898 return false;
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001899}
1900
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001901void GRExprEngine::VisitCall(const CallExpr* CE, ExplodedNode* Pred,
1902 CallExpr::const_arg_iterator AI,
1903 CallExpr::const_arg_iterator AE,
Ted Kremenek892697d2010-12-16 07:46:53 +00001904 ExplodedNodeSet& Dst) {
Ted Kremenek3cead902009-12-17 20:06:29 +00001905
Douglas Gregor9d293df2008-10-28 00:22:11 +00001906 // Determine the type of function we're calling (if available).
Douglas Gregor72564e72009-02-26 23:50:07 +00001907 const FunctionProtoType *Proto = NULL;
Douglas Gregor9d293df2008-10-28 00:22:11 +00001908 QualType FnType = CE->getCallee()->IgnoreParens()->getType();
Ted Kremenek6217b802009-07-29 21:53:49 +00001909 if (const PointerType *FnTypePtr = FnType->getAs<PointerType>())
John McCall183700f2009-09-21 23:43:11 +00001910 Proto = FnTypePtr->getPointeeType()->getAs<FunctionProtoType>();
Douglas Gregor9d293df2008-10-28 00:22:11 +00001911
Ted Kremenekc69c4382010-09-23 05:14:51 +00001912 // Evaluate the arguments.
Ted Kremenek3cead902009-12-17 20:06:29 +00001913 ExplodedNodeSet ArgsEvaluated;
Ted Kremenek9c149532010-12-01 21:57:22 +00001914 evalArguments(CE->arg_begin(), CE->arg_end(), Proto, Pred, ArgsEvaluated);
Ted Kremenekde434242008-02-19 01:44:53 +00001915
Ted Kremenek7f14e6f2009-12-17 20:10:17 +00001916 // Now process the call itself.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001917 ExplodedNodeSet DstTmp;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001918 const Expr* Callee = CE->getCallee()->IgnoreParens();
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001919
Ted Kremenek3cead902009-12-17 20:06:29 +00001920 for (ExplodedNodeSet::iterator NI=ArgsEvaluated.begin(),
Ted Kremenek7f14e6f2009-12-17 20:10:17 +00001921 NE=ArgsEvaluated.end(); NI != NE; ++NI) {
1922 // Evaluate the callee.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001923 ExplodedNodeSet DstTmp2;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001924 Visit(Callee, *NI, DstTmp2);
Ted Kremenek5a5d98b2009-07-22 21:43:51 +00001925 // Perform the previsit of the CallExpr, storing the results in DstTmp.
Jordy Rose72905cf2010-08-04 07:10:57 +00001926 CheckerVisit(CE, DstTmp, DstTmp2, PreVisitStmtCallback);
Ted Kremenek5a5d98b2009-07-22 21:43:51 +00001927 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001928
Ted Kremenek3cead902009-12-17 20:06:29 +00001929 // Finally, evaluate the function call. We try each of the checkers
1930 // to see if the can evaluate the function call.
Ted Kremenek17f4da82009-12-09 02:45:41 +00001931 ExplodedNodeSet DstTmp3;
Ted Kremenek53287512009-12-18 20:13:39 +00001932
Mike Stump1eb44332009-09-09 15:08:12 +00001933 for (ExplodedNodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end();
Zhongxing Xu248072a2009-09-05 05:00:57 +00001934 DI != DE; ++DI) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001935
Ted Kremeneka8538d92009-02-13 01:45:31 +00001936 const GRState* state = GetState(*DI);
Ted Kremenek13976632010-02-08 16:18:51 +00001937 SVal L = state->getSVal(Callee);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001938
Ted Kremeneka1354a52008-03-03 16:47:31 +00001939 // FIXME: Add support for symbolic function calls (calls involving
1940 // function pointer values that are symbolic).
Ted Kremenek4bf38da2008-03-05 21:15:02 +00001941 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
Ted Kremenek17f4da82009-12-09 02:45:41 +00001942 ExplodedNodeSet DstChecker;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001943
Zhongxing Xu935ef902009-12-07 09:17:35 +00001944 // If the callee is processed by a checker, skip the rest logic.
1945 if (CheckerEvalCall(CE, DstChecker, *DI))
Zhongxing Xu9f68ea22009-12-09 05:48:53 +00001946 DstTmp3.insert(DstChecker);
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001947 else if (AMgr.shouldInlineCall() && InlineCall(Dst, CE, *DI)) {
1948 // Callee is inlined. We shouldn't do post call checking.
1949 return;
1950 }
Zhongxing Xu935ef902009-12-07 09:17:35 +00001951 else {
Ted Kremenek17f4da82009-12-09 02:45:41 +00001952 for (ExplodedNodeSet::iterator DI_Checker = DstChecker.begin(),
Ted Kremenek3cead902009-12-17 20:06:29 +00001953 DE_Checker = DstChecker.end();
1954 DI_Checker != DE_Checker; ++DI_Checker) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001955
Ted Kremenek3cead902009-12-17 20:06:29 +00001956 // Dispatch to the plug-in transfer function.
Ted Kremenek9c149532010-12-01 21:57:22 +00001957 unsigned oldSize = DstTmp3.size();
Ted Kremenek17f4da82009-12-09 02:45:41 +00001958 SaveOr OldHasGen(Builder->HasGeneratedNode);
1959 Pred = *DI_Checker;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001960
Ted Kremenek17f4da82009-12-09 02:45:41 +00001961 // Dispatch to transfer function logic to handle the call itself.
1962 // FIXME: Allow us to chain together transfer functions.
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001963 assert(Builder && "GRStmtNodeBuilder must be defined.");
Ted Kremenek9c149532010-12-01 21:57:22 +00001964 getTF().evalCall(DstTmp3, *this, *Builder, CE, L, Pred);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001965
Ted Kremenek17f4da82009-12-09 02:45:41 +00001966 // Handle the case where no nodes where generated. Auto-generate that
1967 // contains the updated state if we aren't generating sinks.
Ted Kremenek9c149532010-12-01 21:57:22 +00001968 if (!Builder->BuildSinks && DstTmp3.size() == oldSize &&
Ted Kremenek17f4da82009-12-09 02:45:41 +00001969 !Builder->HasGeneratedNode)
1970 MakeNode(DstTmp3, CE, Pred, state);
1971 }
Zhongxing Xu935ef902009-12-07 09:17:35 +00001972 }
Ted Kremenekde434242008-02-19 01:44:53 +00001973 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001974
Ted Kremenek3cead902009-12-17 20:06:29 +00001975 // Finally, perform the post-condition check of the CallExpr and store
1976 // the created nodes in 'Dst'.
Ted Kremenek892697d2010-12-16 07:46:53 +00001977 CheckerVisit(CE, Dst, DstTmp3, PostVisitStmtCallback);
Ted Kremenekde434242008-02-19 01:44:53 +00001978}
1979
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001980//===----------------------------------------------------------------------===//
Ted Kremenek97ed4f62008-10-17 00:03:18 +00001981// Transfer function: Objective-C ivar references.
1982//===----------------------------------------------------------------------===//
1983
Ted Kremenekf5cae632009-02-28 20:50:43 +00001984static std::pair<const void*,const void*> EagerlyAssumeTag
Douglas Gregora5fdd9c2010-05-11 06:18:17 +00001985 = std::pair<const void*,const void*>(&EagerlyAssumeTag,static_cast<void*>(0));
Ted Kremenekf5cae632009-02-28 20:50:43 +00001986
Ted Kremenek9c149532010-12-01 21:57:22 +00001987void GRExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001988 const Expr *Ex) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001989 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
1990 ExplodedNode *Pred = *I;
Mike Stump1eb44332009-09-09 15:08:12 +00001991
Ted Kremenekb2939022009-02-25 23:32:10 +00001992 // Test if the previous node was as the same expression. This can happen
1993 // when the expression fails to evaluate to anything meaningful and
1994 // (as an optimization) we don't generate a node.
Mike Stump1eb44332009-09-09 15:08:12 +00001995 ProgramPoint P = Pred->getLocation();
Ted Kremenekb2939022009-02-25 23:32:10 +00001996 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) {
Mike Stump1eb44332009-09-09 15:08:12 +00001997 Dst.Add(Pred);
Ted Kremenekb2939022009-02-25 23:32:10 +00001998 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001999 }
Ted Kremenekb2939022009-02-25 23:32:10 +00002000
Zhongxing Xu59fea602010-04-20 04:53:09 +00002001 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +00002002 SVal V = state->getSVal(Ex);
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002003 if (nonloc::SymExprVal *SEV = dyn_cast<nonloc::SymExprVal>(&V)) {
Ted Kremenek48af2a92009-02-25 22:32:02 +00002004 // First assume that the condition is true.
Ted Kremenek28f47b92010-12-01 22:16:56 +00002005 if (const GRState *stateTrue = state->assume(*SEV, true)) {
Mike Stump1eb44332009-09-09 15:08:12 +00002006 stateTrue = stateTrue->BindExpr(Ex,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002007 svalBuilder.makeIntVal(1U, Ex->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00002008 Dst.Add(Builder->generateNode(PostStmtCustom(Ex,
Zhongxing Xu25e695b2009-08-15 03:17:38 +00002009 &EagerlyAssumeTag, Pred->getLocationContext()),
Ted Kremenek48af2a92009-02-25 22:32:02 +00002010 stateTrue, Pred));
2011 }
Mike Stump1eb44332009-09-09 15:08:12 +00002012
Ted Kremenek48af2a92009-02-25 22:32:02 +00002013 // Next, assume that the condition is false.
Ted Kremenek28f47b92010-12-01 22:16:56 +00002014 if (const GRState *stateFalse = state->assume(*SEV, false)) {
Mike Stump1eb44332009-09-09 15:08:12 +00002015 stateFalse = stateFalse->BindExpr(Ex,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002016 svalBuilder.makeIntVal(0U, Ex->getType()));
Zhongxing Xu25e695b2009-08-15 03:17:38 +00002017 Dst.Add(Builder->generateNode(PostStmtCustom(Ex, &EagerlyAssumeTag,
2018 Pred->getLocationContext()),
Ted Kremenek48af2a92009-02-25 22:32:02 +00002019 stateFalse, Pred));
2020 }
2021 }
2022 else
2023 Dst.Add(Pred);
2024 }
2025}
2026
2027//===----------------------------------------------------------------------===//
Ted Kremenek4beaa9f2010-09-10 03:05:33 +00002028// Transfer function: Objective-C @synchronized.
2029//===----------------------------------------------------------------------===//
2030
2031void GRExprEngine::VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
2032 ExplodedNode *Pred,
2033 ExplodedNodeSet &Dst) {
2034
2035 // The mutex expression is a CFGElement, so we don't need to explicitly
2036 // visit it since it will already be processed.
2037
2038 // Pre-visit the ObjCAtSynchronizedStmt.
2039 ExplodedNodeSet Tmp;
2040 Tmp.Add(Pred);
2041 CheckerVisit(S, Dst, Tmp, PreVisitStmtCallback);
2042}
2043
2044//===----------------------------------------------------------------------===//
Ted Kremenek48af2a92009-02-25 22:32:02 +00002045// Transfer function: Objective-C ivar references.
2046//===----------------------------------------------------------------------===//
2047
Ted Kremenek892697d2010-12-16 07:46:53 +00002048void GRExprEngine::VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr* Ex,
2049 ExplodedNode* Pred,
2050 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00002051
Ted Kremenek892697d2010-12-16 07:46:53 +00002052 // Visit the base expression, which is needed for computing the lvalue
2053 // of the ivar.
2054 ExplodedNodeSet dstBase;
2055 const Expr *baseExpr = Ex->getBase();
2056 Visit(baseExpr, Pred, dstBase);
Mike Stump1eb44332009-09-09 15:08:12 +00002057
Ted Kremenek892697d2010-12-16 07:46:53 +00002058 // Using the base, compute the lvalue of the instance variable.
2059 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end();
2060 I!=E; ++I) {
2061 ExplodedNode *nodeBase = *I;
2062 const GRState *state = GetState(nodeBase);
2063 SVal baseVal = state->getSVal(baseExpr);
2064 SVal location = state->getLValue(Ex->getDecl(), baseVal);
2065 MakeNode(Dst, Ex, *I, state->BindExpr(Ex, location));
Ted Kremenek97ed4f62008-10-17 00:03:18 +00002066 }
2067}
2068
2069//===----------------------------------------------------------------------===//
Ted Kremenekaf337412008-11-12 19:24:17 +00002070// Transfer function: Objective-C fast enumeration 'for' statements.
2071//===----------------------------------------------------------------------===//
2072
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002073void GRExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt* S,
Zhongxing Xub317f8f2009-09-10 05:44:00 +00002074 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00002075
Ted Kremenekaf337412008-11-12 19:24:17 +00002076 // ObjCForCollectionStmts are processed in two places. This method
2077 // handles the case where an ObjCForCollectionStmt* occurs as one of the
2078 // statements within a basic block. This transfer function does two things:
2079 //
2080 // (1) binds the next container value to 'element'. This creates a new
2081 // node in the ExplodedGraph.
2082 //
2083 // (2) binds the value 0/1 to the ObjCForCollectionStmt* itself, indicating
2084 // whether or not the container has any more elements. This value
2085 // will be tested in ProcessBranch. We need to explicitly bind
2086 // this value because a container can contain nil elements.
Mike Stump1eb44332009-09-09 15:08:12 +00002087 //
Ted Kremenekaf337412008-11-12 19:24:17 +00002088 // FIXME: Eventually this logic should actually do dispatches to
2089 // 'countByEnumeratingWithState:objects:count:' (NSFastEnumeration).
2090 // This will require simulating a temporary NSFastEnumerationState, either
2091 // through an SVal or through the use of MemRegions. This value can
2092 // be affixed to the ObjCForCollectionStmt* instead of 0/1; when the loop
2093 // terminates we reclaim the temporary (it goes out of scope) and we
2094 // we can test if the SVal is 0 or if the MemRegion is null (depending
2095 // on what approach we take).
2096 //
2097 // For now: simulate (1) by assigning either a symbol or nil if the
2098 // container is empty. Thus this transfer function will by default
2099 // result in state splitting.
Mike Stump1eb44332009-09-09 15:08:12 +00002100
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002101 const Stmt* elem = S->getElement();
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002102 SVal ElementV;
Mike Stump1eb44332009-09-09 15:08:12 +00002103
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002104 if (const DeclStmt* DS = dyn_cast<DeclStmt>(elem)) {
2105 const VarDecl* ElemD = cast<VarDecl>(DS->getSingleDecl());
Ted Kremenekaf337412008-11-12 19:24:17 +00002106 assert (ElemD->getInit() == 0);
Ted Kremenekd17da2b2009-08-21 22:28:32 +00002107 ElementV = GetState(Pred)->getLValue(ElemD, Pred->getLocationContext());
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002108 VisitObjCForCollectionStmtAux(S, Pred, Dst, ElementV);
2109 return;
Ted Kremenekaf337412008-11-12 19:24:17 +00002110 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002111
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002112 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00002113 Visit(cast<Expr>(elem), Pred, Tmp);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002114 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) {
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002115 const GRState* state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002116 VisitObjCForCollectionStmtAux(S, *I, Dst, state->getSVal(elem));
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002117 }
2118}
2119
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002120void GRExprEngine::VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt* S,
Zhongxing Xub317f8f2009-09-10 05:44:00 +00002121 ExplodedNode* Pred, ExplodedNodeSet& Dst,
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002122 SVal ElementV) {
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002123
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002124 // Check if the location we are writing back to is a null pointer.
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002125 const Stmt* elem = S->getElement();
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002126 ExplodedNodeSet Tmp;
Ted Kremenek9c149532010-12-01 21:57:22 +00002127 evalLocation(Tmp, elem, Pred, GetState(Pred), ElementV, NULL, false);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002128
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002129 if (Tmp.empty())
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002130 return;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002131
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002132 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
2133 Pred = *NI;
2134 const GRState *state = GetState(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00002135
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002136 // Handle the case where the container still has elements.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002137 SVal TrueV = svalBuilder.makeTruthVal(1);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002138 const GRState *hasElems = state->BindExpr(S, TrueV);
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002139
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002140 // Handle the case where the container has no elements.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002141 SVal FalseV = svalBuilder.makeTruthVal(0);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002142 const GRState *noElems = state->BindExpr(S, FalseV);
Mike Stump1eb44332009-09-09 15:08:12 +00002143
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002144 if (loc::MemRegionVal* MV = dyn_cast<loc::MemRegionVal>(&ElementV))
2145 if (const TypedRegion* R = dyn_cast<TypedRegion>(MV->getRegion())) {
2146 // FIXME: The proper thing to do is to really iterate over the
2147 // container. We will do this with dispatch logic to the store.
2148 // For now, just 'conjure' up a symbolic value.
Zhongxing Xu018220c2010-08-11 06:10:55 +00002149 QualType T = R->getValueType();
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002150 assert(Loc::IsLocType(T));
2151 unsigned Count = Builder->getCurrentBlockCount();
2152 SymbolRef Sym = SymMgr.getConjuredSymbol(elem, T, Count);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002153 SVal V = svalBuilder.makeLoc(Sym);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002154 hasElems = hasElems->bindLoc(ElementV, V);
Mike Stump1eb44332009-09-09 15:08:12 +00002155
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002156 // Bind the location to 'nil' on the false branch.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002157 SVal nilV = svalBuilder.makeIntVal(0, T);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002158 noElems = noElems->bindLoc(ElementV, nilV);
2159 }
Ted Kremenek116ed0a2008-11-12 21:12:46 +00002160
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002161 // Create the new nodes.
2162 MakeNode(Dst, S, Pred, hasElems);
2163 MakeNode(Dst, S, Pred, noElems);
2164 }
Ted Kremenekaf337412008-11-12 19:24:17 +00002165}
2166
2167//===----------------------------------------------------------------------===//
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002168// Transfer function: Objective-C message expressions.
2169//===----------------------------------------------------------------------===//
2170
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002171namespace {
2172class ObjCMsgWLItem {
2173public:
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002174 ObjCMessageExpr::const_arg_iterator I;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002175 ExplodedNode *N;
2176
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002177 ObjCMsgWLItem(const ObjCMessageExpr::const_arg_iterator &i, ExplodedNode *n)
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002178 : I(i), N(n) {}
2179};
2180} // end anonymous namespace
2181
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002182void GRExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr* ME,
2183 ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00002184 ExplodedNodeSet& Dst){
Mike Stump1eb44332009-09-09 15:08:12 +00002185
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002186 // Create a worklist to process both the arguments.
2187 llvm::SmallVector<ObjCMsgWLItem, 20> WL;
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002188
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002189 // But first evaluate the receiver (if any).
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002190 ObjCMessageExpr::const_arg_iterator AI = ME->arg_begin(), AE = ME->arg_end();
2191 if (const Expr *Receiver = ME->getInstanceReceiver()) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002192 ExplodedNodeSet Tmp;
2193 Visit(Receiver, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002194
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002195 if (Tmp.empty())
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002196 return;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002197
2198 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I)
2199 WL.push_back(ObjCMsgWLItem(AI, *I));
2200 }
2201 else
2202 WL.push_back(ObjCMsgWLItem(AI, Pred));
2203
2204 // Evaluate the arguments.
2205 ExplodedNodeSet ArgsEvaluated;
2206 while (!WL.empty()) {
2207 ObjCMsgWLItem Item = WL.back();
2208 WL.pop_back();
2209
2210 if (Item.I == AE) {
2211 ArgsEvaluated.insert(Item.N);
2212 continue;
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002213 }
Mike Stump1eb44332009-09-09 15:08:12 +00002214
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002215 // Evaluate the subexpression.
2216 ExplodedNodeSet Tmp;
2217
2218 // FIXME: [Objective-C++] handle arguments that are references
2219 Visit(*Item.I, Item.N, Tmp);
2220
2221 // Enqueue evaluating the next argument on the worklist.
2222 ++(Item.I);
2223 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
2224 WL.push_back(ObjCMsgWLItem(Item.I, *NI));
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002225 }
Mike Stump1eb44332009-09-09 15:08:12 +00002226
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002227 // Now that the arguments are processed, handle the previsits checks.
2228 ExplodedNodeSet DstPrevisit;
Jordy Rose72905cf2010-08-04 07:10:57 +00002229 CheckerVisit(ME, DstPrevisit, ArgsEvaluated, PreVisitStmtCallback);
Mike Stump1eb44332009-09-09 15:08:12 +00002230
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002231 // Proceed with evaluate the message expression.
Ted Kremenek9c149532010-12-01 21:57:22 +00002232 ExplodedNodeSet dstEval;
Mike Stump1eb44332009-09-09 15:08:12 +00002233
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002234 for (ExplodedNodeSet::iterator DI = DstPrevisit.begin(),
2235 DE = DstPrevisit.end(); DI != DE; ++DI) {
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002236
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002237 Pred = *DI;
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002238 bool RaisesException = false;
Ted Kremenek9c149532010-12-01 21:57:22 +00002239 unsigned oldSize = dstEval.size();
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002240 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002241 SaveOr OldHasGen(Builder->HasGeneratedNode);
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002242
Douglas Gregor04badcf2010-04-21 00:45:42 +00002243 if (const Expr *Receiver = ME->getInstanceReceiver()) {
Zhongxing Xu59fea602010-04-20 04:53:09 +00002244 const GRState *state = GetState(Pred);
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002245
2246 // Bifurcate the state into nil and non-nil ones.
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002247 DefinedOrUnknownSVal receiverVal =
Ted Kremenek13976632010-02-08 16:18:51 +00002248 cast<DefinedOrUnknownSVal>(state->getSVal(Receiver));
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002249
2250 const GRState *notNilState, *nilState;
Ted Kremenek28f47b92010-12-01 22:16:56 +00002251 llvm::tie(notNilState, nilState) = state->assume(receiverVal);
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002252
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002253 // There are three cases: can be nil or non-nil, must be nil, must be
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002254 // non-nil. We handle must be nil, and merge the rest two into non-nil.
2255 if (nilState && !notNilState) {
Ted Kremenek9c149532010-12-01 21:57:22 +00002256 CheckerEvalNilReceiver(ME, dstEval, nilState, Pred);
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002257 continue;
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002258 }
2259
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002260 // Check if the "raise" message was sent.
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002261 assert(notNilState);
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002262 if (ME->getSelector() == RaiseSel)
2263 RaisesException = true;
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002264
2265 // Check if we raise an exception. For now treat these as sinks.
2266 // Eventually we will want to handle exceptions properly.
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002267 if (RaisesException)
2268 Builder->BuildSinks = true;
2269
2270 // Dispatch to plug-in transfer function.
Ted Kremenek9c149532010-12-01 21:57:22 +00002271 evalObjCMessageExpr(dstEval, ME, Pred, notNilState);
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002272 }
Douglas Gregor04badcf2010-04-21 00:45:42 +00002273 else if (ObjCInterfaceDecl *Iface = ME->getReceiverInterface()) {
2274 IdentifierInfo* ClsName = Iface->getIdentifier();
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002275 Selector S = ME->getSelector();
2276
2277 // Check for special instance methods.
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002278 if (!NSExceptionII) {
2279 ASTContext& Ctx = getContext();
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002280 NSExceptionII = &Ctx.Idents.get("NSException");
2281 }
2282
2283 if (ClsName == NSExceptionII) {
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002284 enum { NUM_RAISE_SELECTORS = 2 };
2285
2286 // Lazily create a cache of the selectors.
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002287 if (!NSExceptionInstanceRaiseSelectors) {
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002288 ASTContext& Ctx = getContext();
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002289 NSExceptionInstanceRaiseSelectors =
2290 new Selector[NUM_RAISE_SELECTORS];
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002291 llvm::SmallVector<IdentifierInfo*, NUM_RAISE_SELECTORS> II;
2292 unsigned idx = 0;
2293
2294 // raise:format:
2295 II.push_back(&Ctx.Idents.get("raise"));
2296 II.push_back(&Ctx.Idents.get("format"));
2297 NSExceptionInstanceRaiseSelectors[idx++] =
2298 Ctx.Selectors.getSelector(II.size(), &II[0]);
2299
2300 // raise:format::arguments:
2301 II.push_back(&Ctx.Idents.get("arguments"));
2302 NSExceptionInstanceRaiseSelectors[idx++] =
2303 Ctx.Selectors.getSelector(II.size(), &II[0]);
2304 }
2305
2306 for (unsigned i = 0; i < NUM_RAISE_SELECTORS; ++i)
2307 if (S == NSExceptionInstanceRaiseSelectors[i]) {
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002308 RaisesException = true;
2309 break;
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002310 }
2311 }
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002312
2313 // Check if we raise an exception. For now treat these as sinks.
2314 // Eventually we will want to handle exceptions properly.
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002315 if (RaisesException)
2316 Builder->BuildSinks = true;
2317
2318 // Dispatch to plug-in transfer function.
Ted Kremenek9c149532010-12-01 21:57:22 +00002319 evalObjCMessageExpr(dstEval, ME, Pred, Builder->GetState(Pred));
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002320 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002321
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002322 // Handle the case where no nodes where generated. Auto-generate that
2323 // contains the updated state if we aren't generating sinks.
Ted Kremenek9c149532010-12-01 21:57:22 +00002324 if (!Builder->BuildSinks && dstEval.size() == oldSize &&
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002325 !Builder->HasGeneratedNode)
Ted Kremenek9c149532010-12-01 21:57:22 +00002326 MakeNode(dstEval, ME, Pred, GetState(Pred));
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002327 }
Mike Stump1eb44332009-09-09 15:08:12 +00002328
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002329 // Finally, perform the post-condition check of the ObjCMessageExpr and store
2330 // the created nodes in 'Dst'.
Ted Kremenek892697d2010-12-16 07:46:53 +00002331 CheckerVisit(ME, Dst, dstEval, PostVisitStmtCallback);
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002332}
2333
2334//===----------------------------------------------------------------------===//
2335// Transfer functions: Miscellaneous statements.
2336//===----------------------------------------------------------------------===//
2337
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002338void GRExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,
Ted Kremenek892697d2010-12-16 07:46:53 +00002339 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
2340
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002341 ExplodedNodeSet S1;
Ted Kremenek892697d2010-12-16 07:46:53 +00002342 Visit(Ex, Pred, S1);
2343 ExplodedNodeSet S2;
2344 CheckerVisit(CastE, S2, S1, PreVisitStmtCallback);
2345
2346 if (CastE->getCastKind() == CK_LValueToRValue) {
2347 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I!=E; ++I) {
2348 ExplodedNode *subExprNode = *I;
2349 const GRState *state = GetState(subExprNode);
2350 evalLoad(Dst, CastE, subExprNode, state, state->getSVal(Ex));
2351 }
2352 return;
2353 }
2354
2355 // All other casts.
Ted Kremenek5d3003a2008-02-19 18:52:54 +00002356 QualType T = CastE->getType();
Zhongxing Xu933c3e12008-10-21 06:54:23 +00002357 QualType ExTy = Ex->getType();
Zhongxing Xued340f72008-10-22 08:02:16 +00002358
Zhongxing Xud3118bd2008-10-31 07:26:14 +00002359 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE))
Douglas Gregor49badde2008-10-27 19:41:14 +00002360 T = ExCast->getTypeAsWritten();
Ted Kremenek892697d2010-12-16 07:46:53 +00002361
2362#if 0
Ted Kremenek949bdb42009-12-23 00:26:16 +00002363 // If we are evaluating the cast in an lvalue context, we implicitly want
2364 // the cast to evaluate to a location.
2365 if (asLValue) {
2366 ASTContext &Ctx = getContext();
2367 T = Ctx.getPointerType(Ctx.getCanonicalType(T));
Ted Kremenek077a40d2009-12-23 01:19:20 +00002368 ExTy = Ctx.getPointerType(Ctx.getCanonicalType(ExTy));
Ted Kremenek949bdb42009-12-23 00:26:16 +00002369 }
Ted Kremenek892697d2010-12-16 07:46:53 +00002370#endif
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002371
Zhongxing Xub79b1172010-01-22 04:30:00 +00002372 switch (CastE->getCastKind()) {
John McCall2de56d12010-08-25 11:45:40 +00002373 case CK_ToVoid:
Zhongxing Xub79b1172010-01-22 04:30:00 +00002374 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I)
2375 Dst.Add(*I);
2376 return;
2377
John McCall0ae287a2010-12-01 04:43:34 +00002378 case CK_LValueToRValue:
John McCall2de56d12010-08-25 11:45:40 +00002379 case CK_NoOp:
2380 case CK_FunctionToPointerDecay:
Zhongxing Xub79b1172010-01-22 04:30:00 +00002381 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {
2382 // Copy the SVal of Ex to CastE.
2383 ExplodedNode *N = *I;
2384 const GRState *state = GetState(N);
Ted Kremenek13976632010-02-08 16:18:51 +00002385 SVal V = state->getSVal(Ex);
Zhongxing Xub79b1172010-01-22 04:30:00 +00002386 state = state->BindExpr(CastE, V);
2387 MakeNode(Dst, CastE, N, state);
2388 }
2389 return;
2390
John McCallf6a16482010-12-04 03:47:34 +00002391 case CK_GetObjCProperty:
John McCalldaa8e4e2010-11-15 09:13:47 +00002392 case CK_Dependent:
John McCall2de56d12010-08-25 11:45:40 +00002393 case CK_ArrayToPointerDecay:
2394 case CK_BitCast:
2395 case CK_LValueBitCast:
2396 case CK_IntegralCast:
John McCall404cd162010-11-13 01:35:44 +00002397 case CK_NullToPointer:
John McCall2de56d12010-08-25 11:45:40 +00002398 case CK_IntegralToPointer:
2399 case CK_PointerToIntegral:
John McCalldaa8e4e2010-11-15 09:13:47 +00002400 case CK_PointerToBoolean:
2401 case CK_IntegralToBoolean:
John McCall2de56d12010-08-25 11:45:40 +00002402 case CK_IntegralToFloating:
2403 case CK_FloatingToIntegral:
John McCalldaa8e4e2010-11-15 09:13:47 +00002404 case CK_FloatingToBoolean:
John McCall2de56d12010-08-25 11:45:40 +00002405 case CK_FloatingCast:
John McCall2bb5d002010-11-13 09:02:35 +00002406 case CK_FloatingRealToComplex:
John McCallf3ea8cf2010-11-14 08:17:51 +00002407 case CK_FloatingComplexToReal:
2408 case CK_FloatingComplexToBoolean:
John McCall2bb5d002010-11-13 09:02:35 +00002409 case CK_FloatingComplexCast:
John McCallf3ea8cf2010-11-14 08:17:51 +00002410 case CK_FloatingComplexToIntegralComplex:
John McCall2bb5d002010-11-13 09:02:35 +00002411 case CK_IntegralRealToComplex:
John McCallf3ea8cf2010-11-14 08:17:51 +00002412 case CK_IntegralComplexToReal:
2413 case CK_IntegralComplexToBoolean:
John McCall2bb5d002010-11-13 09:02:35 +00002414 case CK_IntegralComplexCast:
John McCallf3ea8cf2010-11-14 08:17:51 +00002415 case CK_IntegralComplexToFloatingComplex:
John McCall2de56d12010-08-25 11:45:40 +00002416 case CK_AnyPointerToObjCPointerCast:
2417 case CK_AnyPointerToBlockPointerCast:
Zhongxing Xu4fd56812010-11-26 08:21:53 +00002418
John McCall2de56d12010-08-25 11:45:40 +00002419 case CK_ObjCObjectLValueCast: {
Ted Kremenek846eabd2010-12-01 21:28:31 +00002420 // Delegate to SValBuilder to process.
Zhongxing Xub79b1172010-01-22 04:30:00 +00002421 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {
2422 ExplodedNode* N = *I;
2423 const GRState* state = GetState(N);
Ted Kremenek13976632010-02-08 16:18:51 +00002424 SVal V = state->getSVal(Ex);
Ted Kremenek9c149532010-12-01 21:57:22 +00002425 V = svalBuilder.evalCast(V, T, ExTy);
Zhongxing Xu814e6b92010-02-04 04:56:43 +00002426 state = state->BindExpr(CastE, V);
Zhongxing Xub79b1172010-01-22 04:30:00 +00002427 MakeNode(Dst, CastE, N, state);
2428 }
2429 return;
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +00002430 }
Zhongxing Xu4fd56812010-11-26 08:21:53 +00002431
2432 case CK_DerivedToBase:
2433 case CK_UncheckedDerivedToBase:
2434 // For DerivedToBase cast, delegate to the store manager.
2435 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {
2436 ExplodedNode *node = *I;
2437 const GRState *state = GetState(node);
2438 SVal val = state->getSVal(Ex);
2439 val = getStoreManager().evalDerivedToBase(val, T);
2440 state = state->BindExpr(CastE, val);
2441 MakeNode(Dst, CastE, node, state);
2442 }
2443 return;
2444
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +00002445 // Various C++ casts that are not handled yet.
John McCall2de56d12010-08-25 11:45:40 +00002446 case CK_Dynamic:
2447 case CK_ToUnion:
2448 case CK_BaseToDerived:
2449 case CK_NullToMemberPointer:
2450 case CK_BaseToDerivedMemberPointer:
2451 case CK_DerivedToBaseMemberPointer:
2452 case CK_UserDefinedConversion:
2453 case CK_ConstructorConversion:
2454 case CK_VectorSplat:
2455 case CK_MemberPointerToBoolean: {
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +00002456 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
2457 Builder->BuildSinks = true;
2458 MakeNode(Dst, CastE, Pred, GetState(Pred));
2459 return;
2460 }
Ted Kremenek874d63f2008-01-24 02:02:54 +00002461 }
Ted Kremenek9de04c42008-01-24 20:55:43 +00002462}
2463
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002464void GRExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr* CL,
Mike Stump1eb44332009-09-09 15:08:12 +00002465 ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00002466 ExplodedNodeSet& Dst) {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002467 const InitListExpr* ILE
2468 = cast<InitListExpr>(CL->getInitializer()->IgnoreParens());
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002469 ExplodedNodeSet Tmp;
Ted Kremenek4f090272008-10-27 21:54:31 +00002470 Visit(ILE, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002471
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002472 for (ExplodedNodeSet::iterator I = Tmp.begin(), EI = Tmp.end(); I!=EI; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002473 const GRState* state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002474 SVal ILV = state->getSVal(ILE);
Ted Kremenek67d12872009-12-07 22:05:27 +00002475 const LocationContext *LC = (*I)->getLocationContext();
2476 state = state->bindCompoundLiteral(CL, LC, ILV);
Ted Kremenek4f090272008-10-27 21:54:31 +00002477
Ted Kremenek892697d2010-12-16 07:46:53 +00002478 if (CL->isLValue()) {
Ted Kremenek67d12872009-12-07 22:05:27 +00002479 MakeNode(Dst, CL, *I, state->BindExpr(CL, state->getLValue(CL, LC)));
2480 }
Zhongxing Xuf22679e2008-11-07 10:38:33 +00002481 else
Ted Kremenek8e029342009-08-27 22:17:37 +00002482 MakeNode(Dst, CL, *I, state->BindExpr(CL, ILV));
Ted Kremenek4f090272008-10-27 21:54:31 +00002483 }
2484}
2485
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002486void GRExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
Mike Stump1eb44332009-09-09 15:08:12 +00002487 ExplodedNodeSet& Dst) {
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002488
Mike Stump1eb44332009-09-09 15:08:12 +00002489 // The CFG has one DeclStmt per Decl.
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002490 const Decl* D = *DS->decl_begin();
Mike Stump1eb44332009-09-09 15:08:12 +00002491
Ted Kremeneke6c62e32008-08-28 18:34:26 +00002492 if (!D || !isa<VarDecl>(D))
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002493 return;
Mike Stump1eb44332009-09-09 15:08:12 +00002494
2495 const VarDecl* VD = dyn_cast<VarDecl>(D);
Zhongxing Xu1f191242010-07-23 02:54:53 +00002496 const Expr* InitEx = VD->getInit();
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002497
2498 // FIXME: static variables may have an initializer, but the second
2499 // time a function is called those values may not be current.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002500 ExplodedNodeSet Tmp;
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002501
Zhongxing Xuf45fbad2010-12-19 02:26:37 +00002502 if (InitEx) {
2503 if (VD->getType()->isReferenceType() && !InitEx->isLValue()) {
Zhongxing Xu05e53912010-12-22 07:20:27 +00002504 // If the initializer is C++ record type, it should already has a
2505 // temp object.
2506 if (!InitEx->getType()->isRecordType())
2507 CreateCXXTemporaryObject(InitEx, Pred, Tmp);
2508 else
2509 Tmp.Add(Pred);
Zhongxing Xuf45fbad2010-12-19 02:26:37 +00002510 } else
2511 Visit(InitEx, Pred, Tmp);
2512 } else
Ted Kremeneke6c62e32008-08-28 18:34:26 +00002513 Tmp.Add(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00002514
Ted Kremenekae162332009-11-07 03:56:57 +00002515 ExplodedNodeSet Tmp2;
Jordy Rose72905cf2010-08-04 07:10:57 +00002516 CheckerVisit(DS, Tmp2, Tmp, PreVisitStmtCallback);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002517
Ted Kremenekae162332009-11-07 03:56:57 +00002518 for (ExplodedNodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) {
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002519 ExplodedNode *N = *I;
Ted Kremenekae162332009-11-07 03:56:57 +00002520 const GRState *state = GetState(N);
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002521
Zhongxing Xu4193eca2008-12-20 06:32:12 +00002522 // Decls without InitExpr are not initialized explicitly.
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002523 const LocationContext *LC = N->getLocationContext();
Ted Kremenekd17da2b2009-08-21 22:28:32 +00002524
Ted Kremenekaf337412008-11-12 19:24:17 +00002525 if (InitEx) {
Ted Kremenek13976632010-02-08 16:18:51 +00002526 SVal InitVal = state->getSVal(InitEx);
Mike Stump1eb44332009-09-09 15:08:12 +00002527
Zhongxing Xu05e53912010-12-22 07:20:27 +00002528 // We bound the temp obj region to the CXXConstructExpr. Now recover
2529 // the lazy compound value when the variable is not a reference.
2530 if (AMgr.getLangOptions().CPlusPlus && VD->getType()->isRecordType() &&
2531 !VD->getType()->isReferenceType() && isa<loc::MemRegionVal>(InitVal)){
2532 InitVal = state->getSVal(cast<loc::MemRegionVal>(InitVal).getRegion());
2533 assert(isa<nonloc::LazyCompoundVal>(InitVal));
2534 }
2535
Ted Kremenekaf337412008-11-12 19:24:17 +00002536 // Recover some path-sensitivity if a scalar value evaluated to
2537 // UnknownVal.
Ted Kremeneka804a682010-03-02 21:43:52 +00002538 if ((InitVal.isUnknown() ||
2539 !getConstraintManager().canReasonAbout(InitVal)) &&
2540 !VD->getType()->isReferenceType()) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002541 InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx,
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002542 Builder->getCurrentBlockCount());
Mike Stump1eb44332009-09-09 15:08:12 +00002543 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002544
Ted Kremenek9c149532010-12-01 21:57:22 +00002545 evalBind(Dst, DS, *I, state,
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002546 loc::MemRegionVal(state->getRegion(VD, LC)), InitVal, true);
Mike Stump1eb44332009-09-09 15:08:12 +00002547 }
Ted Kremenek5b8d9012009-02-14 01:54:57 +00002548 else {
Ted Kremenekf6f56d42009-11-04 00:09:15 +00002549 state = state->bindDeclWithNoInit(state->getRegion(VD, LC));
Ted Kremenek5b8d9012009-02-14 01:54:57 +00002550 MakeNode(Dst, DS, *I, state);
Ted Kremenekefd59942008-12-08 22:47:34 +00002551 }
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002552 }
Ted Kremenek9de04c42008-01-24 20:55:43 +00002553}
Ted Kremenek874d63f2008-01-24 02:02:54 +00002554
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002555void GRExprEngine::VisitCondInit(const VarDecl *VD, const Stmt *S,
Ted Kremenekfcfb5032009-12-24 00:40:03 +00002556 ExplodedNode *Pred, ExplodedNodeSet& Dst) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002557
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002558 const Expr* InitEx = VD->getInit();
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002559 ExplodedNodeSet Tmp;
2560 Visit(InitEx, Pred, Tmp);
2561
2562 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2563 ExplodedNode *N = *I;
2564 const GRState *state = GetState(N);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002565
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002566 const LocationContext *LC = N->getLocationContext();
Ted Kremenek13976632010-02-08 16:18:51 +00002567 SVal InitVal = state->getSVal(InitEx);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002568
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002569 // Recover some path-sensitivity if a scalar value evaluated to
2570 // UnknownVal.
2571 if (InitVal.isUnknown() ||
2572 !getConstraintManager().canReasonAbout(InitVal)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002573 InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx,
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002574 Builder->getCurrentBlockCount());
2575 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002576
Ted Kremenek9c149532010-12-01 21:57:22 +00002577 evalBind(Dst, S, N, state,
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002578 loc::MemRegionVal(state->getRegion(VD, LC)), InitVal, true);
2579 }
2580}
2581
Ted Kremenekf75b1862008-10-30 17:47:32 +00002582namespace {
2583 // This class is used by VisitInitListExpr as an item in a worklist
2584 // for processing the values contained in an InitListExpr.
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +00002585class InitListWLItem {
Ted Kremenekf75b1862008-10-30 17:47:32 +00002586public:
2587 llvm::ImmutableList<SVal> Vals;
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002588 ExplodedNode* N;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002589 InitListExpr::const_reverse_iterator Itr;
Mike Stump1eb44332009-09-09 15:08:12 +00002590
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002591 InitListWLItem(ExplodedNode* n, llvm::ImmutableList<SVal> vals,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002592 InitListExpr::const_reverse_iterator itr)
Ted Kremenekf75b1862008-10-30 17:47:32 +00002593 : Vals(vals), N(n), Itr(itr) {}
2594};
2595}
2596
2597
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002598void GRExprEngine::VisitInitListExpr(const InitListExpr* E, ExplodedNode* Pred,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002599 ExplodedNodeSet& Dst) {
Ted Kremeneka49e3672008-10-30 23:14:36 +00002600
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002601 const GRState* state = GetState(Pred);
Ted Kremenek76dba7b2008-11-13 05:05:34 +00002602 QualType T = getContext().getCanonicalType(E->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00002603 unsigned NumInitElements = E->getNumInits();
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002604
Douglas Gregorfb87b892010-04-26 21:31:17 +00002605 if (T->isArrayType() || T->isRecordType() || T->isVectorType()) {
Ted Kremeneka49e3672008-10-30 23:14:36 +00002606 llvm::ImmutableList<SVal> StartVals = getBasicVals().getEmptySValList();
Mike Stump1eb44332009-09-09 15:08:12 +00002607
Ted Kremeneka49e3672008-10-30 23:14:36 +00002608 // Handle base case where the initializer has no elements.
2609 // e.g: static int* myArray[] = {};
2610 if (NumInitElements == 0) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002611 SVal V = svalBuilder.makeCompoundVal(T, StartVals);
Ted Kremenek8e029342009-08-27 22:17:37 +00002612 MakeNode(Dst, E, Pred, state->BindExpr(E, V));
Ted Kremeneka49e3672008-10-30 23:14:36 +00002613 return;
Mike Stump1eb44332009-09-09 15:08:12 +00002614 }
2615
Ted Kremeneka49e3672008-10-30 23:14:36 +00002616 // Create a worklist to process the initializers.
2617 llvm::SmallVector<InitListWLItem, 10> WorkList;
Mike Stump1eb44332009-09-09 15:08:12 +00002618 WorkList.reserve(NumInitElements);
2619 WorkList.push_back(InitListWLItem(Pred, StartVals, E->rbegin()));
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002620 InitListExpr::const_reverse_iterator ItrEnd = E->rend();
Ted Kremenekcf549592009-09-22 21:19:14 +00002621 assert(!(E->rbegin() == E->rend()));
Mike Stump1eb44332009-09-09 15:08:12 +00002622
Ted Kremeneka49e3672008-10-30 23:14:36 +00002623 // Process the worklist until it is empty.
Ted Kremenekf75b1862008-10-30 17:47:32 +00002624 while (!WorkList.empty()) {
2625 InitListWLItem X = WorkList.back();
2626 WorkList.pop_back();
Mike Stump1eb44332009-09-09 15:08:12 +00002627
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002628 ExplodedNodeSet Tmp;
Ted Kremenekf75b1862008-10-30 17:47:32 +00002629 Visit(*X.Itr, X.N, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002630
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002631 InitListExpr::const_reverse_iterator NewItr = X.Itr + 1;
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002632
Zhongxing Xubb141212009-12-16 11:27:52 +00002633 for (ExplodedNodeSet::iterator NI=Tmp.begin(),NE=Tmp.end();NI!=NE;++NI) {
Ted Kremenekf75b1862008-10-30 17:47:32 +00002634 // Get the last initializer value.
2635 state = GetState(*NI);
Ted Kremenek13976632010-02-08 16:18:51 +00002636 SVal InitV = state->getSVal(cast<Expr>(*X.Itr));
Mike Stump1eb44332009-09-09 15:08:12 +00002637
Ted Kremenekf75b1862008-10-30 17:47:32 +00002638 // Construct the new list of values by prepending the new value to
2639 // the already constructed list.
2640 llvm::ImmutableList<SVal> NewVals =
2641 getBasicVals().consVals(InitV, X.Vals);
Mike Stump1eb44332009-09-09 15:08:12 +00002642
Ted Kremenekf75b1862008-10-30 17:47:32 +00002643 if (NewItr == ItrEnd) {
Zhongxing Xua189dca2008-10-31 03:01:26 +00002644 // Now we have a list holding all init values. Make CompoundValData.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002645 SVal V = svalBuilder.makeCompoundVal(T, NewVals);
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002646
Ted Kremenekf75b1862008-10-30 17:47:32 +00002647 // Make final state and node.
Ted Kremenek8e029342009-08-27 22:17:37 +00002648 MakeNode(Dst, E, *NI, state->BindExpr(E, V));
Ted Kremenekf75b1862008-10-30 17:47:32 +00002649 }
2650 else {
2651 // Still some initializer values to go. Push them onto the worklist.
2652 WorkList.push_back(InitListWLItem(*NI, NewVals, NewItr));
2653 }
2654 }
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002655 }
Mike Stump1eb44332009-09-09 15:08:12 +00002656
Ted Kremenek87903072008-10-30 18:34:31 +00002657 return;
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002658 }
2659
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002660 if (Loc::IsLocType(T) || T->isIntegerType()) {
2661 assert (E->getNumInits() == 1);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002662 ExplodedNodeSet Tmp;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002663 const Expr* Init = E->getInit(0);
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002664 Visit(Init, Pred, Tmp);
Zhongxing Xubb141212009-12-16 11:27:52 +00002665 for (ExplodedNodeSet::iterator I=Tmp.begin(), EI=Tmp.end(); I != EI; ++I) {
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002666 state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002667 MakeNode(Dst, E, *I, state->BindExpr(E, state->getSVal(Init)));
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002668 }
2669 return;
2670 }
2671
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002672 assert(0 && "unprocessed InitListExpr type");
2673}
Ted Kremenekf233d482008-02-05 00:26:40 +00002674
Sebastian Redl05189992008-11-11 17:56:53 +00002675/// VisitSizeOfAlignOfExpr - Transfer function for sizeof(type).
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002676void GRExprEngine::VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr* Ex,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002677 ExplodedNode* Pred,
2678 ExplodedNodeSet& Dst) {
Sebastian Redl05189992008-11-11 17:56:53 +00002679 QualType T = Ex->getTypeOfArgument();
Ken Dyck199c3d62010-01-11 17:06:35 +00002680 CharUnits amt;
Mike Stump1eb44332009-09-09 15:08:12 +00002681
Ted Kremenek87e80342008-03-15 03:13:20 +00002682 if (Ex->isSizeOf()) {
Mike Stump1eb44332009-09-09 15:08:12 +00002683 if (T == getContext().VoidTy) {
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002684 // sizeof(void) == 1 byte.
Ken Dyck199c3d62010-01-11 17:06:35 +00002685 amt = CharUnits::One();
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002686 }
Jordy Roseb7e3aab2010-07-05 04:42:43 +00002687 else if (!T->isConstantSizeType()) {
2688 assert(T->isVariableArrayType() && "Unknown non-constant-sized type.");
2689
2690 // FIXME: Add support for VLA type arguments, not just VLA expressions.
2691 // When that happens, we should probably refactor VLASizeChecker's code.
2692 if (Ex->isArgumentType()) {
2693 Dst.Add(Pred);
2694 return;
2695 }
2696
2697 // Get the size by getting the extent of the sub-expression.
2698 // First, visit the sub-expression to find its region.
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002699 const Expr *Arg = Ex->getArgumentExpr();
Jordy Roseb7e3aab2010-07-05 04:42:43 +00002700 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00002701 Visit(Arg, Pred, Tmp);
Jordy Roseb7e3aab2010-07-05 04:42:43 +00002702
2703 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2704 const GRState* state = GetState(*I);
2705 const MemRegion *MR = state->getSVal(Arg).getAsRegion();
2706
2707 // If the subexpression can't be resolved to a region, we don't know
2708 // anything about its size. Just leave the state as is and continue.
2709 if (!MR) {
2710 Dst.Add(*I);
2711 continue;
2712 }
2713
2714 // The result is the extent of the VLA.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002715 SVal Extent = cast<SubRegion>(MR)->getExtent(svalBuilder);
Jordy Roseb7e3aab2010-07-05 04:42:43 +00002716 MakeNode(Dst, Ex, *I, state->BindExpr(Ex, Extent));
2717 }
2718
Ted Kremenek87e80342008-03-15 03:13:20 +00002719 return;
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002720 }
John McCallc12c5bb2010-05-15 11:32:37 +00002721 else if (T->getAs<ObjCObjectType>()) {
2722 // Some code tries to take the sizeof an ObjCObjectType, relying that
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002723 // the compiler has laid out its representation. Just report Unknown
Mike Stump1eb44332009-09-09 15:08:12 +00002724 // for these.
Ted Kremenek61e8e1b2010-02-02 02:01:51 +00002725 Dst.Add(Pred);
Ted Kremenekf342d182008-04-30 21:31:12 +00002726 return;
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002727 }
2728 else {
2729 // All other cases.
Ken Dyck199c3d62010-01-11 17:06:35 +00002730 amt = getContext().getTypeSizeInChars(T);
Mike Stump1eb44332009-09-09 15:08:12 +00002731 }
Ted Kremenek87e80342008-03-15 03:13:20 +00002732 }
2733 else // Get alignment of the type.
Ken Dyckda8e5852010-01-27 12:54:25 +00002734 amt = getContext().getTypeAlignInChars(T);
Mike Stump1eb44332009-09-09 15:08:12 +00002735
Ted Kremenek0e561a32008-03-21 21:30:14 +00002736 MakeNode(Dst, Ex, Pred,
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002737 GetState(Pred)->BindExpr(Ex,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002738 svalBuilder.makeIntVal(amt.getQuantity(), Ex->getType())));
Ted Kremenekd9435bf2008-02-12 19:49:57 +00002739}
2740
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002741void GRExprEngine::VisitOffsetOfExpr(const OffsetOfExpr* OOE,
2742 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Douglas Gregor8ecdb652010-04-28 22:16:22 +00002743 Expr::EvalResult Res;
2744 if (OOE->Evaluate(Res, getContext()) && Res.Val.isInt()) {
2745 const APSInt &IV = Res.Val.getInt();
2746 assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType()));
2747 assert(OOE->getType()->isIntegerType());
2748 assert(IV.isSigned() == OOE->getType()->isSignedIntegerType());
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002749 SVal X = svalBuilder.makeIntVal(IV);
Douglas Gregor8ecdb652010-04-28 22:16:22 +00002750 MakeNode(Dst, OOE, Pred, GetState(Pred)->BindExpr(OOE, X));
2751 return;
2752 }
2753 // FIXME: Handle the case where __builtin_offsetof is not a constant.
2754 Dst.Add(Pred);
2755}
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002756
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002757void GRExprEngine::VisitUnaryOperator(const UnaryOperator* U,
2758 ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00002759 ExplodedNodeSet& Dst) {
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002760
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002761 switch (U->getOpcode()) {
Mike Stump1eb44332009-09-09 15:08:12 +00002762
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002763 default:
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002764 break;
Mike Stump1eb44332009-09-09 15:08:12 +00002765
John McCall2de56d12010-08-25 11:45:40 +00002766 case UO_Real: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002767 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002768 ExplodedNodeSet Tmp;
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002769 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002770
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002771 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +00002772
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002773 // FIXME: We don't have complex SValues yet.
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002774 if (Ex->getType()->isAnyComplexType()) {
2775 // Just report "Unknown."
2776 Dst.Add(*I);
2777 continue;
2778 }
Mike Stump1eb44332009-09-09 15:08:12 +00002779
John McCall2de56d12010-08-25 11:45:40 +00002780 // For all other types, UO_Real is an identity operation.
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002781 assert (U->getType() == Ex->getType());
Ted Kremeneka8538d92009-02-13 01:45:31 +00002782 const GRState* state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002783 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex)));
Mike Stump1eb44332009-09-09 15:08:12 +00002784 }
2785
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002786 return;
2787 }
Mike Stump1eb44332009-09-09 15:08:12 +00002788
John McCall2de56d12010-08-25 11:45:40 +00002789 case UO_Imag: {
Mike Stump1eb44332009-09-09 15:08:12 +00002790
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002791 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002792 ExplodedNodeSet Tmp;
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002793 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002794
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002795 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002796 // FIXME: We don't have complex SValues yet.
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002797 if (Ex->getType()->isAnyComplexType()) {
2798 // Just report "Unknown."
2799 Dst.Add(*I);
2800 continue;
2801 }
Mike Stump1eb44332009-09-09 15:08:12 +00002802
John McCall2de56d12010-08-25 11:45:40 +00002803 // For all other types, UO_Imag returns 0.
Ted Kremeneka8538d92009-02-13 01:45:31 +00002804 const GRState* state = GetState(*I);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002805 SVal X = svalBuilder.makeZeroVal(Ex->getType());
Ted Kremenek8e029342009-08-27 22:17:37 +00002806 MakeNode(Dst, U, *I, state->BindExpr(U, X));
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002807 }
Mike Stump1eb44332009-09-09 15:08:12 +00002808
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002809 return;
2810 }
Douglas Gregor8ecdb652010-04-28 22:16:22 +00002811
Ted Kremenek892697d2010-12-16 07:46:53 +00002812 case UO_Plus:
2813 assert(!U->isLValue());
2814 // FALL-THROUGH.
2815 case UO_Deref:
Zhongxing Xu9c2bac02010-12-18 05:16:43 +00002816 case UO_AddrOf:
John McCall2de56d12010-08-25 11:45:40 +00002817 case UO_Extension: {
Mike Stump1eb44332009-09-09 15:08:12 +00002818
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002819 // Unary "+" is a no-op, similar to a parentheses. We still have places
2820 // where it may be a block-level expression, so we need to
2821 // generate an extra node that just propagates the value of the
2822 // subexpression.
2823
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002824 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002825 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00002826 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002827
2828 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002829 const GRState* state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002830 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex)));
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002831 }
Mike Stump1eb44332009-09-09 15:08:12 +00002832
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002833 return;
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002834 }
Mike Stump1eb44332009-09-09 15:08:12 +00002835
John McCall2de56d12010-08-25 11:45:40 +00002836 case UO_LNot:
2837 case UO_Minus:
2838 case UO_Not: {
Ted Kremenek892697d2010-12-16 07:46:53 +00002839 assert (!U->isLValue());
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002840 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002841 ExplodedNodeSet Tmp;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002842 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002843
2844 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002845 const GRState* state = GetState(*I);
Mike Stump1eb44332009-09-09 15:08:12 +00002846
Ted Kremenek855cd902008-09-30 05:32:44 +00002847 // Get the value of the subexpression.
Ted Kremenek13976632010-02-08 16:18:51 +00002848 SVal V = state->getSVal(Ex);
Ted Kremenek855cd902008-09-30 05:32:44 +00002849
Ted Kremeneke04a5cb2008-11-15 00:20:05 +00002850 if (V.isUnknownOrUndef()) {
Ted Kremenek8e029342009-08-27 22:17:37 +00002851 MakeNode(Dst, U, *I, state->BindExpr(U, V));
Ted Kremeneke04a5cb2008-11-15 00:20:05 +00002852 continue;
2853 }
Mike Stump1eb44332009-09-09 15:08:12 +00002854
Ted Kremenek60595da2008-11-15 04:01:56 +00002855// QualType DstT = getContext().getCanonicalType(U->getType());
2856// QualType SrcT = getContext().getCanonicalType(Ex->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00002857//
Ted Kremenek60595da2008-11-15 04:01:56 +00002858// if (DstT != SrcT) // Perform promotions.
Ted Kremenek9c149532010-12-01 21:57:22 +00002859// V = evalCast(V, DstT);
Mike Stump1eb44332009-09-09 15:08:12 +00002860//
Ted Kremenek60595da2008-11-15 04:01:56 +00002861// if (V.isUnknownOrUndef()) {
2862// MakeNode(Dst, U, *I, BindExpr(St, U, V));
2863// continue;
2864// }
Mike Stump1eb44332009-09-09 15:08:12 +00002865
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002866 switch (U->getOpcode()) {
2867 default:
2868 assert(false && "Invalid Opcode.");
2869 break;
Mike Stump1eb44332009-09-09 15:08:12 +00002870
John McCall2de56d12010-08-25 11:45:40 +00002871 case UO_Not:
Ted Kremenek60a6e0c2008-10-01 00:21:14 +00002872 // FIXME: Do we need to handle promotions?
Ted Kremenek9c149532010-12-01 21:57:22 +00002873 state = state->BindExpr(U, evalComplement(cast<NonLoc>(V)));
Mike Stump1eb44332009-09-09 15:08:12 +00002874 break;
2875
John McCall2de56d12010-08-25 11:45:40 +00002876 case UO_Minus:
Ted Kremenek60a6e0c2008-10-01 00:21:14 +00002877 // FIXME: Do we need to handle promotions?
Ted Kremenek9c149532010-12-01 21:57:22 +00002878 state = state->BindExpr(U, evalMinus(cast<NonLoc>(V)));
Mike Stump1eb44332009-09-09 15:08:12 +00002879 break;
2880
John McCall2de56d12010-08-25 11:45:40 +00002881 case UO_LNot:
Mike Stump1eb44332009-09-09 15:08:12 +00002882
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002883 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
2884 //
2885 // Note: technically we do "E == 0", but this is the same in the
2886 // transfer functions as "0 == E".
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002887 SVal Result;
Mike Stump1eb44332009-09-09 15:08:12 +00002888
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002889 if (isa<Loc>(V)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002890 Loc X = svalBuilder.makeNull();
Ted Kremenek9c149532010-12-01 21:57:22 +00002891 Result = evalBinOp(state, BO_EQ, cast<Loc>(V), X,
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002892 U->getType());
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002893 }
2894 else {
Ted Kremenek60595da2008-11-15 04:01:56 +00002895 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType()));
Ted Kremenek9c149532010-12-01 21:57:22 +00002896 Result = evalBinOp(state, BO_EQ, cast<NonLoc>(V), X,
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002897 U->getType());
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002898 }
Mike Stump1eb44332009-09-09 15:08:12 +00002899
Ted Kremenek8e029342009-08-27 22:17:37 +00002900 state = state->BindExpr(U, Result);
Mike Stump1eb44332009-09-09 15:08:12 +00002901
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002902 break;
2903 }
Mike Stump1eb44332009-09-09 15:08:12 +00002904
Ted Kremeneka8538d92009-02-13 01:45:31 +00002905 MakeNode(Dst, U, *I, state);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002906 }
Mike Stump1eb44332009-09-09 15:08:12 +00002907
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002908 return;
2909 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002910 }
2911
2912 // Handle ++ and -- (both pre- and post-increment).
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002913 assert (U->isIncrementDecrementOp());
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002914 ExplodedNodeSet Tmp;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002915 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Ted Kremenek892697d2010-12-16 07:46:53 +00002916 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002917
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002918 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +00002919
Ted Kremeneka8538d92009-02-13 01:45:31 +00002920 const GRState* state = GetState(*I);
Zhongxing Xu250704b2010-12-22 08:38:13 +00002921 SVal loc = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00002922
2923 // Perform a load.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002924 ExplodedNodeSet Tmp2;
Zhongxing Xu250704b2010-12-22 08:38:13 +00002925 evalLoad(Tmp2, Ex, *I, state, loc);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002926
Zhongxing Xubb141212009-12-16 11:27:52 +00002927 for (ExplodedNodeSet::iterator I2=Tmp2.begin(), E2=Tmp2.end();I2!=E2;++I2) {
Mike Stump1eb44332009-09-09 15:08:12 +00002928
Ted Kremeneka8538d92009-02-13 01:45:31 +00002929 state = GetState(*I2);
Ted Kremenek13976632010-02-08 16:18:51 +00002930 SVal V2_untested = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00002931
2932 // Propagate unknown and undefined values.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002933 if (V2_untested.isUnknownOrUndef()) {
2934 MakeNode(Dst, U, *I2, state->BindExpr(U, V2_untested));
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002935 continue;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002936 }
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002937 DefinedSVal V2 = cast<DefinedSVal>(V2_untested);
Mike Stump1eb44332009-09-09 15:08:12 +00002938
2939 // Handle all other values.
John McCall2de56d12010-08-25 11:45:40 +00002940 BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add
2941 : BO_Sub;
Ted Kremenek21028dd2009-03-11 03:54:24 +00002942
Zhongxing Xua52ad4e2009-08-05 02:51:59 +00002943 // If the UnaryOperator has non-location type, use its type to create the
2944 // constant value. If the UnaryOperator has location type, create the
2945 // constant with int type and pointer width.
2946 SVal RHS;
2947
2948 if (U->getType()->isAnyPointerType())
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002949 RHS = svalBuilder.makeIntValWithPtrWidth(1, false);
Zhongxing Xua52ad4e2009-08-05 02:51:59 +00002950 else
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002951 RHS = svalBuilder.makeIntVal(1, U->getType());
Zhongxing Xua52ad4e2009-08-05 02:51:59 +00002952
Ted Kremenek9c149532010-12-01 21:57:22 +00002953 SVal Result = evalBinOp(state, Op, V2, RHS, U->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00002954
Ted Kremenekbb9b2712009-03-20 20:10:45 +00002955 // Conjure a new symbol if necessary to recover precision.
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002956 if (Result.isUnknown() || !getConstraintManager().canReasonAbout(Result)){
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002957 DefinedOrUnknownSVal SymVal =
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002958 svalBuilder.getConjuredSymbolVal(NULL, Ex,
Ted Kremenek87806792009-09-27 20:45:21 +00002959 Builder->getCurrentBlockCount());
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002960 Result = SymVal;
Mike Stump1eb44332009-09-09 15:08:12 +00002961
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002962 // If the value is a location, ++/-- should always preserve
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002963 // non-nullness. Check if the original value was non-null, and if so
Mike Stump1eb44332009-09-09 15:08:12 +00002964 // propagate that constraint.
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002965 if (Loc::IsLocType(U->getType())) {
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002966 DefinedOrUnknownSVal Constraint =
Zhongxing Xu250704b2010-12-22 08:38:13 +00002967 svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00002968
Ted Kremenek28f47b92010-12-01 22:16:56 +00002969 if (!state->assume(Constraint, true)) {
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002970 // It isn't feasible for the original value to be null.
2971 // Propagate this constraint.
Ted Kremenek9c149532010-12-01 21:57:22 +00002972 Constraint = svalBuilder.evalEQ(state, SymVal,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002973 svalBuilder.makeZeroVal(U->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00002974
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002975
Ted Kremenek28f47b92010-12-01 22:16:56 +00002976 state = state->assume(Constraint, false);
Ted Kremeneka591bc02009-06-18 22:57:13 +00002977 assert(state);
Mike Stump1eb44332009-09-09 15:08:12 +00002978 }
2979 }
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002980 }
Mike Stump1eb44332009-09-09 15:08:12 +00002981
Zhongxing Xu250704b2010-12-22 08:38:13 +00002982 // Since the lvalue-to-rvalue conversion is explicit in the AST,
2983 // we bind an l-value if the operator is prefix and an lvalue (in C++).
2984 if (U->isPrefix() && U->isLValue())
2985 state = state->BindExpr(U, loc);
2986 else
2987 state = state->BindExpr(U, V2);
Ted Kremenekcf78b6a2008-02-06 22:50:25 +00002988
Mike Stump1eb44332009-09-09 15:08:12 +00002989 // Perform the store.
Zhongxing Xu250704b2010-12-22 08:38:13 +00002990 evalStore(Dst, NULL, U, *I2, state, loc, Result);
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00002991 }
Ted Kremenek469ecbd2008-04-21 23:43:38 +00002992 }
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00002993}
2994
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002995void GRExprEngine::VisitAsmStmt(const AsmStmt* A, ExplodedNode* Pred,
Zhongxing Xubb141212009-12-16 11:27:52 +00002996 ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002997 VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst);
Mike Stump1eb44332009-09-09 15:08:12 +00002998}
Ted Kremenekef44bfb2008-03-17 21:11:24 +00002999
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003000void GRExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt* A,
3001 AsmStmt::const_outputs_iterator I,
3002 AsmStmt::const_outputs_iterator E,
Zhongxing Xubb141212009-12-16 11:27:52 +00003003 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003004 if (I == E) {
3005 VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst);
3006 return;
3007 }
Mike Stump1eb44332009-09-09 15:08:12 +00003008
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003009 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00003010 Visit(*I, Pred, Tmp);
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003011 ++I;
Mike Stump1eb44332009-09-09 15:08:12 +00003012
Zhongxing Xubb141212009-12-16 11:27:52 +00003013 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI)
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003014 VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst);
3015}
3016
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003017void GRExprEngine::VisitAsmStmtHelperInputs(const AsmStmt* A,
3018 AsmStmt::const_inputs_iterator I,
3019 AsmStmt::const_inputs_iterator E,
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003020 ExplodedNode* Pred,
Zhongxing Xubb141212009-12-16 11:27:52 +00003021 ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003022 if (I == E) {
Mike Stump1eb44332009-09-09 15:08:12 +00003023
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003024 // We have processed both the inputs and the outputs. All of the outputs
Zhongxing Xu1c96b242008-10-17 05:57:07 +00003025 // should evaluate to Locs. Nuke all of their values.
Mike Stump1eb44332009-09-09 15:08:12 +00003026
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003027 // FIXME: Some day in the future it would be nice to allow a "plug-in"
3028 // which interprets the inline asm and stores proper results in the
3029 // outputs.
Mike Stump1eb44332009-09-09 15:08:12 +00003030
Ted Kremeneka8538d92009-02-13 01:45:31 +00003031 const GRState* state = GetState(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00003032
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003033 for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(),
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003034 OE = A->end_outputs(); OI != OE; ++OI) {
Mike Stump1eb44332009-09-09 15:08:12 +00003035
Ted Kremenek13976632010-02-08 16:18:51 +00003036 SVal X = state->getSVal(*OI);
Zhongxing Xu1c96b242008-10-17 05:57:07 +00003037 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.
Mike Stump1eb44332009-09-09 15:08:12 +00003038
Zhongxing Xu1c96b242008-10-17 05:57:07 +00003039 if (isa<Loc>(X))
Ted Kremenek3ff12592009-06-19 17:10:32 +00003040 state = state->bindLoc(cast<Loc>(X), UnknownVal());
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003041 }
Mike Stump1eb44332009-09-09 15:08:12 +00003042
Ted Kremeneka8538d92009-02-13 01:45:31 +00003043 MakeNode(Dst, A, Pred, state);
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003044 return;
3045 }
Mike Stump1eb44332009-09-09 15:08:12 +00003046
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003047 ExplodedNodeSet Tmp;
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003048 Visit(*I, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00003049
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003050 ++I;
Mike Stump1eb44332009-09-09 15:08:12 +00003051
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00003052 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI)
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003053 VisitAsmStmtHelperInputs(A, I, E, *NI, Dst);
3054}
3055
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003056void GRExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
Ted Kremenek1053d242009-11-06 02:24:13 +00003057 ExplodedNodeSet &Dst) {
Ted Kremenek1053d242009-11-06 02:24:13 +00003058 ExplodedNodeSet Src;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003059 if (const Expr *RetE = RS->getRetValue()) {
Zhongxing Xubd2b2082010-03-23 08:09:29 +00003060 // Record the returned expression in the state. It will be used in
3061 // ProcessCallExit to bind the return value to the call expr.
Zhongxing Xu6190ec22010-02-26 15:43:34 +00003062 {
Ted Kremeneka804a682010-03-02 21:43:52 +00003063 static int Tag = 0;
3064 SaveAndRestore<const void *> OldTag(Builder->Tag, &Tag);
Zhongxing Xu6190ec22010-02-26 15:43:34 +00003065 const GRState *state = GetState(Pred);
3066 state = state->set<ReturnExpr>(RetE);
3067 Pred = Builder->generateNode(RetE, state, Pred);
3068 }
3069 // We may get a NULL Pred because we generated a cached node.
3070 if (Pred)
3071 Visit(RetE, Pred, Src);
Ted Kremenek02737ed2008-03-31 15:02:58 +00003072 }
Ted Kremenek1053d242009-11-06 02:24:13 +00003073 else {
3074 Src.Add(Pred);
3075 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003076
Ted Kremenek1053d242009-11-06 02:24:13 +00003077 ExplodedNodeSet CheckedSet;
Jordy Rose72905cf2010-08-04 07:10:57 +00003078 CheckerVisit(RS, CheckedSet, Src, PreVisitStmtCallback);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003079
Ted Kremenek1053d242009-11-06 02:24:13 +00003080 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
3081 I != E; ++I) {
Ted Kremenek6b31e8e2008-04-16 23:05:51 +00003082
Ted Kremenek1053d242009-11-06 02:24:13 +00003083 assert(Builder && "GRStmtNodeBuilder must be defined.");
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003084
Ted Kremenek1053d242009-11-06 02:24:13 +00003085 Pred = *I;
3086 unsigned size = Dst.size();
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003087
Ted Kremenek1053d242009-11-06 02:24:13 +00003088 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
3089 SaveOr OldHasGen(Builder->HasGeneratedNode);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003090
Ted Kremenek9c149532010-12-01 21:57:22 +00003091 getTF().evalReturn(Dst, *this, *Builder, RS, Pred);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003092
3093 // Handle the case where no nodes where generated.
3094 if (!Builder->BuildSinks && Dst.size() == size &&
Ted Kremenek1053d242009-11-06 02:24:13 +00003095 !Builder->HasGeneratedNode)
3096 MakeNode(Dst, RS, Pred, GetState(Pred));
Ted Kremenek5917d782008-11-21 00:27:44 +00003097 }
Ted Kremenek02737ed2008-03-31 15:02:58 +00003098}
Ted Kremenek55deb972008-03-25 00:34:37 +00003099
Ted Kremeneke695e1c2008-04-15 23:06:53 +00003100//===----------------------------------------------------------------------===//
3101// Transfer functions: Binary operators.
3102//===----------------------------------------------------------------------===//
3103
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003104void GRExprEngine::VisitBinaryOperator(const BinaryOperator* B,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003105 ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00003106 ExplodedNodeSet& Dst) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003107 ExplodedNodeSet Tmp1;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003108 Expr* LHS = B->getLHS()->IgnoreParens();
3109 Expr* RHS = B->getRHS()->IgnoreParens();
Mike Stump1eb44332009-09-09 15:08:12 +00003110
Ted Kremenek892697d2010-12-16 07:46:53 +00003111 Visit(LHS, Pred, Tmp1);
Zhongxing Xu668399b2009-11-24 08:24:26 +00003112 ExplodedNodeSet Tmp3;
3113
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00003114 for (ExplodedNodeSet::iterator I1=Tmp1.begin(), E1=Tmp1.end(); I1!=E1; ++I1) {
Zhongxing Xu59fea602010-04-20 04:53:09 +00003115 SVal LeftV = GetState(*I1)->getSVal(LHS);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003116 ExplodedNodeSet Tmp2;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003117 Visit(RHS, *I1, Tmp2);
Zhongxing Xu6403b572009-09-02 13:26:26 +00003118
3119 ExplodedNodeSet CheckedSet;
Jordy Rose72905cf2010-08-04 07:10:57 +00003120 CheckerVisit(B, CheckedSet, Tmp2, PreVisitStmtCallback);
Mike Stump1eb44332009-09-09 15:08:12 +00003121
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003122 // With both the LHS and RHS evaluated, process the operation itself.
Mike Stump1eb44332009-09-09 15:08:12 +00003123
3124 for (ExplodedNodeSet::iterator I2=CheckedSet.begin(), E2=CheckedSet.end();
Zhongxing Xu6403b572009-09-02 13:26:26 +00003125 I2 != E2; ++I2) {
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00003126
Ted Kremenek5b9bd212009-09-11 22:07:28 +00003127 const GRState *state = GetState(*I2);
Ted Kremenek13976632010-02-08 16:18:51 +00003128 SVal RightV = state->getSVal(RHS);
Ted Kremenek5b9bd212009-09-11 22:07:28 +00003129
Ted Kremenekcf78b6a2008-02-06 22:50:25 +00003130 BinaryOperator::Opcode Op = B->getOpcode();
Mike Stump1eb44332009-09-09 15:08:12 +00003131
John McCall2de56d12010-08-25 11:45:40 +00003132 if (Op == BO_Assign) {
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003133 // EXPERIMENTAL: "Conjured" symbols.
3134 // FIXME: Handle structs.
3135 QualType T = RHS->getType();
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003136
Ted Kremenek0e82a932010-07-29 00:28:33 +00003137 if (RightV.isUnknown() ||!getConstraintManager().canReasonAbout(RightV))
3138 {
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003139 unsigned Count = Builder->getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +00003140 RightV = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), Count);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003141 }
Zhongxing Xu662174ca2009-10-30 07:19:39 +00003142
Ted Kremenek892697d2010-12-16 07:46:53 +00003143 SVal ExprVal = B->isLValue() ? LeftV : RightV;
Zhongxing Xu662174ca2009-10-30 07:19:39 +00003144
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003145 // Simulate the effects of a "store": bind the value of the RHS
3146 // to the L-Value represented by the LHS.
Ted Kremenek9c149532010-12-01 21:57:22 +00003147 evalStore(Tmp3, B, LHS, *I2, state->BindExpr(B, ExprVal), LeftV,RightV);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003148 continue;
3149 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003150
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003151 if (!B->isAssignmentOp()) {
3152 // Process non-assignments except commas or short-circuited
3153 // logical expressions (LAnd and LOr).
Ted Kremenek9c149532010-12-01 21:57:22 +00003154 SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType());
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003155
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003156 if (Result.isUnknown()) {
Ted Kremenek96ebad62010-09-09 07:13:00 +00003157 MakeNode(Tmp3, B, *I2, state);
Ted Kremeneke38718e2008-04-16 18:21:25 +00003158 continue;
Ted Kremenekab2b8c52008-01-23 19:59:44 +00003159 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003160
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003161 state = state->BindExpr(B, Result);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003162
Zhongxing Xu668399b2009-11-24 08:24:26 +00003163 MakeNode(Tmp3, B, *I2, state);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003164 continue;
Ted Kremenekab2b8c52008-01-23 19:59:44 +00003165 }
Mike Stump1eb44332009-09-09 15:08:12 +00003166
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003167 assert (B->isCompoundAssignmentOp());
3168
Ted Kremenekcad29962009-02-07 00:52:24 +00003169 switch (Op) {
3170 default:
3171 assert(0 && "Invalid opcode for compound assignment.");
John McCall2de56d12010-08-25 11:45:40 +00003172 case BO_MulAssign: Op = BO_Mul; break;
3173 case BO_DivAssign: Op = BO_Div; break;
3174 case BO_RemAssign: Op = BO_Rem; break;
3175 case BO_AddAssign: Op = BO_Add; break;
3176 case BO_SubAssign: Op = BO_Sub; break;
3177 case BO_ShlAssign: Op = BO_Shl; break;
3178 case BO_ShrAssign: Op = BO_Shr; break;
3179 case BO_AndAssign: Op = BO_And; break;
3180 case BO_XorAssign: Op = BO_Xor; break;
3181 case BO_OrAssign: Op = BO_Or; break;
Ted Kremenek934e3e92008-10-27 23:02:39 +00003182 }
Mike Stump1eb44332009-09-09 15:08:12 +00003183
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003184 // Perform a load (the LHS). This performs the checks for
3185 // null dereferences, and so on.
Zhongxing Xuc39b2bd2010-01-19 09:25:53 +00003186 ExplodedNodeSet Tmp4;
Ted Kremenek13976632010-02-08 16:18:51 +00003187 SVal location = state->getSVal(LHS);
Ted Kremenek9c149532010-12-01 21:57:22 +00003188 evalLoad(Tmp4, LHS, *I2, state, location);
Mike Stump1eb44332009-09-09 15:08:12 +00003189
Zhongxing Xuc39b2bd2010-01-19 09:25:53 +00003190 for (ExplodedNodeSet::iterator I4=Tmp4.begin(), E4=Tmp4.end(); I4!=E4;
3191 ++I4) {
3192 state = GetState(*I4);
Ted Kremenek13976632010-02-08 16:18:51 +00003193 SVal V = state->getSVal(LHS);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003194
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003195 // Get the computation type.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00003196 QualType CTy =
3197 cast<CompoundAssignOperator>(B)->getComputationResultType();
Ted Kremenek60595da2008-11-15 04:01:56 +00003198 CTy = getContext().getCanonicalType(CTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00003199
Ted Kremenek32c3fa42009-07-21 21:03:30 +00003200 QualType CLHSTy =
3201 cast<CompoundAssignOperator>(B)->getComputationLHSType();
3202 CLHSTy = getContext().getCanonicalType(CLHSTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00003203
Ted Kremenek60595da2008-11-15 04:01:56 +00003204 QualType LTy = getContext().getCanonicalType(LHS->getType());
3205 QualType RTy = getContext().getCanonicalType(RHS->getType());
Eli Friedmanab3a8522009-03-28 01:22:36 +00003206
3207 // Promote LHS.
Ted Kremenek9c149532010-12-01 21:57:22 +00003208 V = svalBuilder.evalCast(V, CLHSTy, LTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00003209
Mike Stump1eb44332009-09-09 15:08:12 +00003210 // Compute the result of the operation.
Ted Kremenek9c149532010-12-01 21:57:22 +00003211 SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy),
Zhongxing Xu814e6b92010-02-04 04:56:43 +00003212 B->getType(), CTy);
Mike Stump1eb44332009-09-09 15:08:12 +00003213
Ted Kremenek9ff267d2008-10-20 23:13:25 +00003214 // EXPERIMENTAL: "Conjured" symbols.
3215 // FIXME: Handle structs.
Mike Stump1eb44332009-09-09 15:08:12 +00003216
Ted Kremenek60595da2008-11-15 04:01:56 +00003217 SVal LHSVal;
Mike Stump1eb44332009-09-09 15:08:12 +00003218
Ted Kremenek0e82a932010-07-29 00:28:33 +00003219 if (Result.isUnknown() ||
3220 !getConstraintManager().canReasonAbout(Result)) {
Mike Stump1eb44332009-09-09 15:08:12 +00003221
Ted Kremenek9ff267d2008-10-20 23:13:25 +00003222 unsigned Count = Builder->getCurrentBlockCount();
Mike Stump1eb44332009-09-09 15:08:12 +00003223
Ted Kremenek60595da2008-11-15 04:01:56 +00003224 // The symbolic value is actually for the type of the left-hand side
3225 // expression, not the computation type, as this is the value the
3226 // LValue on the LHS will bind to.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00003227 LHSVal = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LTy, Count);
Mike Stump1eb44332009-09-09 15:08:12 +00003228
Zhongxing Xu1c0c2332008-11-23 05:52:28 +00003229 // However, we need to convert the symbol to the computation type.
Ted Kremenek9c149532010-12-01 21:57:22 +00003230 Result = svalBuilder.evalCast(LHSVal, CTy, LTy);
Ted Kremenek9ff267d2008-10-20 23:13:25 +00003231 }
Ted Kremenek60595da2008-11-15 04:01:56 +00003232 else {
3233 // The left-hand side may bind to a different value then the
3234 // computation type.
Ted Kremenek9c149532010-12-01 21:57:22 +00003235 LHSVal = svalBuilder.evalCast(Result, LTy, CTy);
Ted Kremenek60595da2008-11-15 04:01:56 +00003236 }
Mike Stump1eb44332009-09-09 15:08:12 +00003237
Ted Kremenek9c149532010-12-01 21:57:22 +00003238 evalStore(Tmp3, B, LHS, *I4, state->BindExpr(B, Result),
Zhongxing Xu5032ffe2009-08-25 06:51:30 +00003239 location, LHSVal);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003240 }
Ted Kremenekcb448ca2008-01-16 00:53:15 +00003241 }
Ted Kremenekd27f8162008-01-15 23:55:06 +00003242 }
Zhongxing Xu668399b2009-11-24 08:24:26 +00003243
Jordy Rose72905cf2010-08-04 07:10:57 +00003244 CheckerVisit(B, Dst, Tmp3, PostVisitStmtCallback);
Ted Kremenekd27f8162008-01-15 23:55:06 +00003245}
Ted Kremenekee985462008-01-16 18:18:48 +00003246
3247//===----------------------------------------------------------------------===//
Ted Kremenek094bef52009-10-30 17:47:32 +00003248// Checker registration/lookup.
3249//===----------------------------------------------------------------------===//
3250
3251Checker *GRExprEngine::lookupChecker(void *tag) const {
Jeffrey Yasskin3958b502009-11-10 01:17:45 +00003252 CheckerMap::const_iterator I = CheckerM.find(tag);
Ted Kremenek094bef52009-10-30 17:47:32 +00003253 return (I == CheckerM.end()) ? NULL : Checkers[I->second].second;
3254}
3255
3256//===----------------------------------------------------------------------===//
Ted Kremeneke01c9872008-02-14 22:36:46 +00003257// Visualization.
Ted Kremenekee985462008-01-16 18:18:48 +00003258//===----------------------------------------------------------------------===//
3259
Ted Kremenekaa66a322008-01-16 21:46:15 +00003260#ifndef NDEBUG
Ted Kremenek4d4dd852008-02-13 17:41:41 +00003261static GRExprEngine* GraphPrintCheckerState;
Ted Kremeneke97ca062008-03-07 20:57:30 +00003262static SourceManager* GraphPrintSourceManager;
Ted Kremenek3b4f6702008-01-30 23:24:39 +00003263
Ted Kremenekaa66a322008-01-16 21:46:15 +00003264namespace llvm {
3265template<>
Douglas Gregor47491f82009-11-30 16:08:24 +00003266struct DOTGraphTraits<ExplodedNode*> :
Ted Kremenekaa66a322008-01-16 21:46:15 +00003267 public DefaultDOTGraphTraits {
Tobias Grosser006b0eb2009-11-30 14:16:05 +00003268
3269 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
3270
Zhongxing Xuec9227f2009-10-29 02:09:30 +00003271 // FIXME: Since we do not cache error nodes in GRExprEngine now, this does not
3272 // work.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003273 static std::string getNodeAttributes(const ExplodedNode* N, void*) {
Mike Stump1eb44332009-09-09 15:08:12 +00003274
Ted Kremenek10f51e82009-11-11 20:16:36 +00003275#if 0
3276 // FIXME: Replace with a general scheme to tell if the node is
3277 // an error node.
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00003278 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
Ted Kremenek9dca0622008-02-19 00:22:37 +00003279 GraphPrintCheckerState->isExplicitNullDeref(N) ||
Ted Kremenek4a4e5242008-02-28 09:25:22 +00003280 GraphPrintCheckerState->isUndefDeref(N) ||
3281 GraphPrintCheckerState->isUndefStore(N) ||
3282 GraphPrintCheckerState->isUndefControlFlow(N) ||
Ted Kremenek5e03fcb2008-02-29 23:14:48 +00003283 GraphPrintCheckerState->isUndefResult(N) ||
Ted Kremenek2ded35a2008-02-29 23:53:11 +00003284 GraphPrintCheckerState->isBadCall(N) ||
3285 GraphPrintCheckerState->isUndefArg(N))
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00003286 return "color=\"red\",style=\"filled\"";
Mike Stump1eb44332009-09-09 15:08:12 +00003287
Ted Kremenek8cc13ea2008-02-28 20:32:03 +00003288 if (GraphPrintCheckerState->isNoReturnCall(N))
3289 return "color=\"blue\",style=\"filled\"";
Zhongxing Xu2055eff2009-11-24 07:06:39 +00003290#endif
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00003291 return "";
3292 }
Mike Stump1eb44332009-09-09 15:08:12 +00003293
Tobias Grosser006b0eb2009-11-30 14:16:05 +00003294 static std::string getNodeLabel(const ExplodedNode* N, void*){
Mike Stump1eb44332009-09-09 15:08:12 +00003295
Ted Kremenek53ba0b62009-06-24 23:06:47 +00003296 std::string sbuf;
3297 llvm::raw_string_ostream Out(sbuf);
Ted Kremenek803c9ed2008-01-23 22:30:44 +00003298
3299 // Program Location.
Ted Kremenekaa66a322008-01-16 21:46:15 +00003300 ProgramPoint Loc = N->getLocation();
Mike Stump1eb44332009-09-09 15:08:12 +00003301
Ted Kremenekaa66a322008-01-16 21:46:15 +00003302 switch (Loc.getKind()) {
3303 case ProgramPoint::BlockEntranceKind:
Mike Stump1eb44332009-09-09 15:08:12 +00003304 Out << "Block Entrance: B"
Ted Kremenekaa66a322008-01-16 21:46:15 +00003305 << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
3306 break;
Mike Stump1eb44332009-09-09 15:08:12 +00003307
Ted Kremenekaa66a322008-01-16 21:46:15 +00003308 case ProgramPoint::BlockExitKind:
3309 assert (false);
3310 break;
Mike Stump1eb44332009-09-09 15:08:12 +00003311
Douglas Gregor102acd52010-02-25 19:01:53 +00003312 case ProgramPoint::CallEnterKind:
3313 Out << "CallEnter";
3314 break;
3315
3316 case ProgramPoint::CallExitKind:
3317 Out << "CallExit";
3318 break;
3319
Ted Kremenekaa66a322008-01-16 21:46:15 +00003320 default: {
Ted Kremenek5f85e172009-07-22 22:35:28 +00003321 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) {
3322 const Stmt* S = L->getStmt();
Ted Kremenek8c354752008-12-16 22:02:27 +00003323 SourceLocation SLoc = S->getLocStart();
3324
Mike Stump1eb44332009-09-09 15:08:12 +00003325 Out << S->getStmtClassName() << ' ' << (void*) S << ' ';
Chris Lattnere4f21422009-06-30 01:26:17 +00003326 LangOptions LO; // FIXME.
3327 S->printPretty(Out, 0, PrintingPolicy(LO));
Mike Stump1eb44332009-09-09 15:08:12 +00003328
3329 if (SLoc.isFileID()) {
Ted Kremenek8c354752008-12-16 22:02:27 +00003330 Out << "\\lline="
Chris Lattner7da5aea2009-02-04 00:55:58 +00003331 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc)
3332 << " col="
3333 << GraphPrintSourceManager->getInstantiationColumnNumber(SLoc)
3334 << "\\l";
Ted Kremenek8c354752008-12-16 22:02:27 +00003335 }
Mike Stump1eb44332009-09-09 15:08:12 +00003336
Ted Kremenek5f85e172009-07-22 22:35:28 +00003337 if (isa<PreStmt>(Loc))
Mike Stump1eb44332009-09-09 15:08:12 +00003338 Out << "\\lPreStmt\\l;";
Ted Kremenek5f85e172009-07-22 22:35:28 +00003339 else if (isa<PostLoad>(Loc))
Ted Kremenek7090d542009-05-07 18:27:16 +00003340 Out << "\\lPostLoad\\l;";
3341 else if (isa<PostStore>(Loc))
3342 Out << "\\lPostStore\\l";
3343 else if (isa<PostLValue>(Loc))
3344 Out << "\\lPostLValue\\l";
Mike Stump1eb44332009-09-09 15:08:12 +00003345
Ted Kremenek10f51e82009-11-11 20:16:36 +00003346#if 0
3347 // FIXME: Replace with a general scheme to determine
3348 // the name of the check.
Ted Kremenek8c354752008-12-16 22:02:27 +00003349 if (GraphPrintCheckerState->isImplicitNullDeref(N))
3350 Out << "\\|Implicit-Null Dereference.\\l";
3351 else if (GraphPrintCheckerState->isExplicitNullDeref(N))
3352 Out << "\\|Explicit-Null Dereference.\\l";
3353 else if (GraphPrintCheckerState->isUndefDeref(N))
3354 Out << "\\|Dereference of undefialied value.\\l";
3355 else if (GraphPrintCheckerState->isUndefStore(N))
3356 Out << "\\|Store to Undefined Loc.";
Ted Kremenek8c354752008-12-16 22:02:27 +00003357 else if (GraphPrintCheckerState->isUndefResult(N))
3358 Out << "\\|Result of operation is undefined.";
3359 else if (GraphPrintCheckerState->isNoReturnCall(N))
3360 Out << "\\|Call to function marked \"noreturn\".";
3361 else if (GraphPrintCheckerState->isBadCall(N))
3362 Out << "\\|Call to NULL/Undefined.";
3363 else if (GraphPrintCheckerState->isUndefArg(N))
3364 Out << "\\|Argument in call is undefined";
Ted Kremenek10f51e82009-11-11 20:16:36 +00003365#endif
Mike Stump1eb44332009-09-09 15:08:12 +00003366
Ted Kremenek8c354752008-12-16 22:02:27 +00003367 break;
3368 }
3369
Ted Kremenekaa66a322008-01-16 21:46:15 +00003370 const BlockEdge& E = cast<BlockEdge>(Loc);
3371 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
3372 << E.getDst()->getBlockID() << ')';
Mike Stump1eb44332009-09-09 15:08:12 +00003373
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003374 if (const Stmt* T = E.getSrc()->getTerminator()) {
Mike Stump1eb44332009-09-09 15:08:12 +00003375
Ted Kremeneke97ca062008-03-07 20:57:30 +00003376 SourceLocation SLoc = T->getLocStart();
Mike Stump1eb44332009-09-09 15:08:12 +00003377
Ted Kremenekb38911f2008-01-30 23:03:39 +00003378 Out << "\\|Terminator: ";
Chris Lattnere4f21422009-06-30 01:26:17 +00003379 LangOptions LO; // FIXME.
3380 E.getSrc()->printTerminator(Out, LO);
Mike Stump1eb44332009-09-09 15:08:12 +00003381
Ted Kremenek9b5551d2008-03-09 03:30:59 +00003382 if (SLoc.isFileID()) {
3383 Out << "\\lline="
Chris Lattner7da5aea2009-02-04 00:55:58 +00003384 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc)
3385 << " col="
3386 << GraphPrintSourceManager->getInstantiationColumnNumber(SLoc);
Ted Kremenek9b5551d2008-03-09 03:30:59 +00003387 }
Mike Stump1eb44332009-09-09 15:08:12 +00003388
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003389 if (isa<SwitchStmt>(T)) {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003390 const Stmt* Label = E.getDst()->getLabel();
Mike Stump1eb44332009-09-09 15:08:12 +00003391
3392 if (Label) {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003393 if (const CaseStmt* C = dyn_cast<CaseStmt>(Label)) {
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003394 Out << "\\lcase ";
Chris Lattnere4f21422009-06-30 01:26:17 +00003395 LangOptions LO; // FIXME.
3396 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
Mike Stump1eb44332009-09-09 15:08:12 +00003397
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003398 if (const Stmt* RHS = C->getRHS()) {
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003399 Out << " .. ";
Chris Lattnere4f21422009-06-30 01:26:17 +00003400 RHS->printPretty(Out, 0, PrintingPolicy(LO));
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003401 }
Mike Stump1eb44332009-09-09 15:08:12 +00003402
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003403 Out << ":";
3404 }
3405 else {
3406 assert (isa<DefaultStmt>(Label));
3407 Out << "\\ldefault:";
3408 }
3409 }
Mike Stump1eb44332009-09-09 15:08:12 +00003410 else
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003411 Out << "\\l(implicit) default:";
3412 }
3413 else if (isa<IndirectGotoStmt>(T)) {
Ted Kremenekb38911f2008-01-30 23:03:39 +00003414 // FIXME
3415 }
3416 else {
3417 Out << "\\lCondition: ";
3418 if (*E.getSrc()->succ_begin() == E.getDst())
3419 Out << "true";
3420 else
Mike Stump1eb44332009-09-09 15:08:12 +00003421 Out << "false";
Ted Kremenekb38911f2008-01-30 23:03:39 +00003422 }
Mike Stump1eb44332009-09-09 15:08:12 +00003423
Ted Kremenekb38911f2008-01-30 23:03:39 +00003424 Out << "\\l";
3425 }
Mike Stump1eb44332009-09-09 15:08:12 +00003426
Ted Kremenek10f51e82009-11-11 20:16:36 +00003427#if 0
3428 // FIXME: Replace with a general scheme to determine
3429 // the name of the check.
Ted Kremenek4a4e5242008-02-28 09:25:22 +00003430 if (GraphPrintCheckerState->isUndefControlFlow(N)) {
3431 Out << "\\|Control-flow based on\\lUndefined value.\\l";
Ted Kremenek3b4f6702008-01-30 23:24:39 +00003432 }
Ted Kremenek10f51e82009-11-11 20:16:36 +00003433#endif
Ted Kremenekaa66a322008-01-16 21:46:15 +00003434 }
3435 }
Mike Stump1eb44332009-09-09 15:08:12 +00003436
Ted Kremenekb65be702009-06-18 01:23:53 +00003437 const GRState *state = N->getState();
Ted Kremenek8673a682010-12-03 06:52:26 +00003438 Out << "\\|StateID: " << (void*) state
3439 << " NodeID: " << (void*) N << "\\|";
Zhongxing Xuc179a7f2010-03-05 04:45:36 +00003440 state->printDOT(Out, *N->getLocationContext()->getCFG());
Ted Kremenek803c9ed2008-01-23 22:30:44 +00003441 Out << "\\l";
Ted Kremenekaa66a322008-01-16 21:46:15 +00003442 return Out.str();
3443 }
3444};
Mike Stump1eb44332009-09-09 15:08:12 +00003445} // end llvm namespace
Ted Kremenekaa66a322008-01-16 21:46:15 +00003446#endif
3447
Ted Kremenekffe0f432008-03-07 22:58:01 +00003448#ifndef NDEBUG
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003449template <typename ITERATOR>
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003450ExplodedNode* GetGraphNode(ITERATOR I) { return *I; }
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003451
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003452template <> ExplodedNode*
3453GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
3454 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003455 return I->first;
3456}
Ted Kremenekffe0f432008-03-07 22:58:01 +00003457#endif
3458
3459void GRExprEngine::ViewGraph(bool trim) {
Mike Stump1eb44332009-09-09 15:08:12 +00003460#ifndef NDEBUG
Ted Kremenekffe0f432008-03-07 22:58:01 +00003461 if (trim) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003462 std::vector<ExplodedNode*> Src;
Ted Kremenek940abcc2009-03-11 01:41:22 +00003463
3464 // Flush any outstanding reports to make sure we cover all the nodes.
3465 // This does not cause them to get displayed.
3466 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
3467 const_cast<BugType*>(*I)->FlushReports(BR);
3468
3469 // Iterate through the reports and get their nodes.
3470 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) {
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00003471 for (BugType::const_iterator I2=(*I)->begin(), E2=(*I)->end();
Mike Stump1eb44332009-09-09 15:08:12 +00003472 I2!=E2; ++I2) {
Ted Kremenek940abcc2009-03-11 01:41:22 +00003473 const BugReportEquivClass& EQ = *I2;
3474 const BugReport &R = **EQ.begin();
Tom Care212f6d32010-09-16 03:50:38 +00003475 ExplodedNode *N = const_cast<ExplodedNode*>(R.getErrorNode());
Ted Kremenek940abcc2009-03-11 01:41:22 +00003476 if (N) Src.push_back(N);
3477 }
3478 }
Mike Stump1eb44332009-09-09 15:08:12 +00003479
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003480 ViewGraph(&Src[0], &Src[0]+Src.size());
Ted Kremenekffe0f432008-03-07 22:58:01 +00003481 }
Ted Kremenek493d7a22008-03-11 18:25:33 +00003482 else {
3483 GraphPrintCheckerState = this;
3484 GraphPrintSourceManager = &getContext().getSourceManager();
Ted Kremenekae6814e2008-08-13 21:24:49 +00003485
Ted Kremenekffe0f432008-03-07 22:58:01 +00003486 llvm::ViewGraph(*G.roots_begin(), "GRExprEngine");
Mike Stump1eb44332009-09-09 15:08:12 +00003487
Ted Kremenek493d7a22008-03-11 18:25:33 +00003488 GraphPrintCheckerState = NULL;
3489 GraphPrintSourceManager = NULL;
3490 }
3491#endif
3492}
3493
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003494void GRExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) {
Ted Kremenek493d7a22008-03-11 18:25:33 +00003495#ifndef NDEBUG
3496 GraphPrintCheckerState = this;
3497 GraphPrintSourceManager = &getContext().getSourceManager();
Mike Stump1eb44332009-09-09 15:08:12 +00003498
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003499 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first);
Ted Kremenek493d7a22008-03-11 18:25:33 +00003500
Ted Kremenekcf118d42009-02-04 23:49:09 +00003501 if (!TrimmedG.get())
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +00003502 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
Ted Kremenekcf118d42009-02-04 23:49:09 +00003503 else
Mike Stump1eb44332009-09-09 15:08:12 +00003504 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedGRExprEngine");
3505
Ted Kremenek3b4f6702008-01-30 23:24:39 +00003506 GraphPrintCheckerState = NULL;
Ted Kremeneke97ca062008-03-07 20:57:30 +00003507 GraphPrintSourceManager = NULL;
Ted Kremeneke01c9872008-02-14 22:36:46 +00003508#endif
Ted Kremenekee985462008-01-16 18:18:48 +00003509}