blob: ca960142ee35a5c1ff9a249dc4022961a8eff990 [file] [log] [blame]
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001//=-- ExprEngine.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//===----------------------------------------------------------------------===//
Argyrios Kyrtzidisa7af5ea2010-12-22 18:52:56 +000015
16// FIXME: Restructure checker registration.
Zhongxing Xu0742f182011-01-10 09:23:01 +000017#include "ExprEngineInternalChecks.h"
Argyrios Kyrtzidisa7af5ea2010-12-22 18:52:56 +000018
Ted Kremenek21142582010-12-23 19:38:26 +000019#include "clang/StaticAnalyzer/BugReporter/BugType.h"
20#include "clang/StaticAnalyzer/PathSensitive/AnalysisManager.h"
21#include "clang/StaticAnalyzer/PathSensitive/ExprEngine.h"
22#include "clang/StaticAnalyzer/PathSensitive/ExprEngineBuilders.h"
23#include "clang/StaticAnalyzer/PathSensitive/Checker.h"
Ken Dyck199c3d62010-01-11 17:06:35 +000024#include "clang/AST/CharUnits.h"
Chris Lattner16f00492009-04-26 01:32:48 +000025#include "clang/AST/ParentMap.h"
26#include "clang/AST/StmtObjC.h"
Zhongxing Xuc5063572010-03-16 13:14:16 +000027#include "clang/AST/DeclCXX.h"
Chris Lattner1b63e4f2009-06-14 01:54:56 +000028#include "clang/Basic/Builtins.h"
Chris Lattner16f00492009-04-26 01:32:48 +000029#include "clang/Basic/SourceManager.h"
Ted Kremeneke97ca062008-03-07 20:57:30 +000030#include "clang/Basic/SourceManager.h"
Ted Kremenek0bed8a12009-03-11 02:41:36 +000031#include "clang/Basic/PrettyStackTrace.h"
Ted Kremeneka95d3752008-09-13 05:16:45 +000032#include "llvm/Support/raw_ostream.h"
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +000033#include "llvm/ADT/ImmutableList.h"
Ted Kremenek4323a572008-07-10 22:03:41 +000034
Ted Kremenek0f5f0592008-02-27 06:07:00 +000035#ifndef NDEBUG
36#include "llvm/Support/GraphWriter.h"
Ted Kremenek0f5f0592008-02-27 06:07:00 +000037#endif
38
Ted Kremenekb387a3f2008-02-14 22:16:04 +000039using namespace clang;
Ted Kremenek9ef65372010-12-23 07:20:52 +000040using namespace ento;
Ted Kremenekb387a3f2008-02-14 22:16:04 +000041using llvm::dyn_cast;
Ted Kremenek852274d2009-12-16 03:18:58 +000042using llvm::dyn_cast_or_null;
Ted Kremenekb387a3f2008-02-14 22:16:04 +000043using llvm::cast;
44using llvm::APSInt;
Ted Kremenekab2b8c52008-01-23 19:59:44 +000045
Zhongxing Xu6190ec22010-02-26 15:43:34 +000046namespace {
47 // Trait class for recording returned expression in the state.
48 struct ReturnExpr {
49 static int TagInt;
50 typedef const Stmt *data_type;
51 };
52 int ReturnExpr::TagInt;
53}
54
Ted Kremeneke695e1c2008-04-15 23:06:53 +000055//===----------------------------------------------------------------------===//
Ted Kremenek32c49952009-11-25 21:51:20 +000056// Utility functions.
57//===----------------------------------------------------------------------===//
58
59static inline Selector GetNullarySelector(const char* name, ASTContext& Ctx) {
60 IdentifierInfo* II = &Ctx.Idents.get(name);
61 return Ctx.Selectors.getSelector(0, &II);
62}
63
64//===----------------------------------------------------------------------===//
Ted Kremenek5a5d98b2009-07-22 21:43:51 +000065// Checker worklist routines.
66//===----------------------------------------------------------------------===//
Mike Stump1eb44332009-09-09 15:08:12 +000067
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +000068void ExprEngine::CheckerVisit(const Stmt *S, ExplodedNodeSet &Dst,
Jordy Rose72905cf2010-08-04 07:10:57 +000069 ExplodedNodeSet &Src, CallbackKind Kind) {
Mike Stump1eb44332009-09-09 15:08:12 +000070
Ted Kremenek9e9595b2010-06-25 20:59:31 +000071 // Determine if we already have a cached 'CheckersOrdered' vector
Jordy Rose72905cf2010-08-04 07:10:57 +000072 // specifically tailored for the provided <CallbackKind, Stmt kind>. This
Ted Kremenek9e9595b2010-06-25 20:59:31 +000073 // can reduce the number of checkers actually called.
74 CheckersOrdered *CO = &Checkers;
75 llvm::OwningPtr<CheckersOrdered> NewCO;
Jordy Rose72905cf2010-08-04 07:10:57 +000076
77 // The cache key is made up of the and the callback kind (pre- or post-visit)
78 // and the statement kind.
79 CallbackTag K = GetCallbackTag(Kind, S->getStmtClass());
Ted Kremenek9e9595b2010-06-25 20:59:31 +000080
81 CheckersOrdered *& CO_Ref = COCache[K];
82
83 if (!CO_Ref) {
84 // If we have no previously cached CheckersOrdered vector for this
85 // statement kind, then create one.
86 NewCO.reset(new CheckersOrdered);
87 }
88 else {
89 // Use the already cached set.
90 CO = CO_Ref;
91 }
92
93 if (CO->empty()) {
94 // If there are no checkers, return early without doing any
95 // more work.
Ted Kremenek17f4da82009-12-09 02:45:41 +000096 Dst.insert(Src);
Zhongxing Xua46e4d92009-12-02 05:49:12 +000097 return;
Ted Kremenek5a5d98b2009-07-22 21:43:51 +000098 }
Mike Stump1eb44332009-09-09 15:08:12 +000099
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000100 ExplodedNodeSet Tmp;
101 ExplodedNodeSet *PrevSet = &Src;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000102 unsigned checkersEvaluated = 0;
Mike Stump1eb44332009-09-09 15:08:12 +0000103
Zhongxing Xu68df7302010-08-06 04:20:59 +0000104 for (CheckersOrdered::iterator I=CO->begin(), E=CO->end(); I!=E; ++I) {
105 // If all nodes are sunk, bail out early.
106 if (PrevSet->empty())
107 break;
Ted Kremenek17f4da82009-12-09 02:45:41 +0000108 ExplodedNodeSet *CurrSet = 0;
109 if (I+1 == E)
110 CurrSet = &Dst;
111 else {
112 CurrSet = (PrevSet == &Tmp) ? &Src : &Tmp;
113 CurrSet->clear();
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000114 }
Zhongxing Xuec9227f2009-10-29 02:09:30 +0000115 void *tag = I->first;
116 Checker *checker = I->second;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000117 bool respondsToCallback = true;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000118
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000119 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000120 NI != NE; ++NI) {
121
Jordy Rose72905cf2010-08-04 07:10:57 +0000122 checker->GR_Visit(*CurrSet, *Builder, *this, S, *NI, tag,
123 Kind == PreVisitStmtCallback, respondsToCallback);
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000124
125 }
126
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000127 PrevSet = CurrSet;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000128
129 if (NewCO.get()) {
130 ++checkersEvaluated;
131 if (respondsToCallback)
132 NewCO->push_back(*I);
133 }
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000134 }
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000135
136 // If we built NewCO, check if we called all the checkers. This is important
137 // so that we know that we accurately determined the entire set of checkers
Ted Kremenek9b44eaf2010-08-05 15:03:30 +0000138 // that responds to this callback. Note that 'checkersEvaluated' might
139 // not be the same as Checkers.size() if one of the Checkers generates
140 // a sink node.
141 if (NewCO.get() && checkersEvaluated == Checkers.size())
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000142 CO_Ref = NewCO.take();
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000143
144 // Don't autotransition. The CheckerContext objects should do this
145 // automatically.
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000146}
147
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000148void ExprEngine::CheckerEvalNilReceiver(const ObjCMessageExpr *ME,
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000149 ExplodedNodeSet &Dst,
150 const GRState *state,
151 ExplodedNode *Pred) {
Ted Kremenek9c149532010-12-01 21:57:22 +0000152 bool evaluated = false;
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000153 ExplodedNodeSet DstTmp;
154
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000155 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
156 void *tag = I->first;
157 Checker *checker = I->second;
158
Ted Kremenek9c149532010-12-01 21:57:22 +0000159 if (checker->GR_evalNilReceiver(DstTmp, *Builder, *this, ME, Pred, state,
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000160 tag)) {
Ted Kremenek9c149532010-12-01 21:57:22 +0000161 evaluated = true;
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000162 break;
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000163 } else
164 // The checker didn't evaluate the expr. Restore the Dst.
165 DstTmp.clear();
Zhongxing Xua46e4d92009-12-02 05:49:12 +0000166 }
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000167
Ted Kremenek9c149532010-12-01 21:57:22 +0000168 if (evaluated)
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000169 Dst.insert(DstTmp);
170 else
171 Dst.insert(Pred);
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000172}
173
Zhongxing Xu935ef902009-12-07 09:17:35 +0000174// CheckerEvalCall returns true if one of the checkers processed the node.
175// This may return void when all call evaluation logic goes to some checker
176// in the future.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000177bool ExprEngine::CheckerEvalCall(const CallExpr *CE,
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000178 ExplodedNodeSet &Dst,
Zhongxing Xu935ef902009-12-07 09:17:35 +0000179 ExplodedNode *Pred) {
Ted Kremenek9c149532010-12-01 21:57:22 +0000180 bool evaluated = false;
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000181 ExplodedNodeSet DstTmp;
Zhongxing Xu935ef902009-12-07 09:17:35 +0000182
183 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
184 void *tag = I->first;
185 Checker *checker = I->second;
186
Ted Kremenek9c149532010-12-01 21:57:22 +0000187 if (checker->GR_evalCallExpr(DstTmp, *Builder, *this, CE, Pred, tag)) {
188 evaluated = true;
Zhongxing Xu935ef902009-12-07 09:17:35 +0000189 break;
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000190 } else
191 // The checker didn't evaluate the expr. Restore the DstTmp set.
192 DstTmp.clear();
Zhongxing Xu935ef902009-12-07 09:17:35 +0000193 }
194
Ted Kremenek9c149532010-12-01 21:57:22 +0000195 if (evaluated)
Zhongxing Xu78c98fa2009-12-09 12:16:07 +0000196 Dst.insert(DstTmp);
197 else
198 Dst.insert(Pred);
199
Ted Kremenek9c149532010-12-01 21:57:22 +0000200 return evaluated;
Zhongxing Xu935ef902009-12-07 09:17:35 +0000201}
202
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000203// FIXME: This is largely copy-paste from CheckerVisit(). Need to
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000204// unify.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000205void ExprEngine::CheckerVisitBind(const Stmt *StoreE, ExplodedNodeSet &Dst,
Ted Kremenek79d73042010-09-02 00:56:20 +0000206 ExplodedNodeSet &Src, SVal location,
207 SVal val, bool isPrevisit) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000208
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000209 if (Checkers.empty()) {
Ted Kremenek17f4da82009-12-09 02:45:41 +0000210 Dst.insert(Src);
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000211 return;
212 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000213
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000214 ExplodedNodeSet Tmp;
215 ExplodedNodeSet *PrevSet = &Src;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000216
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000217 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E; ++I)
218 {
Ted Kremenek17f4da82009-12-09 02:45:41 +0000219 ExplodedNodeSet *CurrSet = 0;
220 if (I+1 == E)
221 CurrSet = &Dst;
222 else {
223 CurrSet = (PrevSet == &Tmp) ? &Src : &Tmp;
224 CurrSet->clear();
225 }
Ted Kremenek53287512009-12-18 20:13:39 +0000226
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000227 void *tag = I->first;
228 Checker *checker = I->second;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000229
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000230 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
231 NI != NE; ++NI)
Ted Kremenek79d73042010-09-02 00:56:20 +0000232 checker->GR_VisitBind(*CurrSet, *Builder, *this, StoreE,
Ted Kremenek50ecd152009-11-05 00:42:23 +0000233 *NI, tag, location, val, isPrevisit);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000234
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000235 // Update which NodeSet is the current one.
236 PrevSet = CurrSet;
237 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000238
Ted Kremenekb107c4b2009-11-04 04:24:16 +0000239 // Don't autotransition. The CheckerContext objects should do this
240 // automatically.
241}
Ted Kremenek5a5d98b2009-07-22 21:43:51 +0000242//===----------------------------------------------------------------------===//
Ted Kremenekbdb435d2008-07-11 18:37:32 +0000243// Engine construction and deletion.
244//===----------------------------------------------------------------------===//
245
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000246static void RegisterInternalChecks(ExprEngine &Eng) {
Ted Kremenek32c49952009-11-25 21:51:20 +0000247 // Register internal "built-in" BugTypes with the BugReporter. These BugTypes
248 // are different than what probably many checks will do since they don't
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000249 // create BugReports on-the-fly but instead wait until ExprEngine finishes
Ted Kremenek32c49952009-11-25 21:51:20 +0000250 // analyzing a function. Generation of BugReport objects is done via a call
251 // to 'FlushReports' from BugReporter.
252 // The following checks do not need to have their associated BugTypes
253 // explicitly registered with the BugReporter. If they issue any BugReports,
254 // their associated BugType will get registered with the BugReporter
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000255 // automatically. Note that the check itself is owned by the ExprEngine
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000256 // object.
Ted Kremenek40c37e12010-02-04 00:47:48 +0000257 RegisterAdjustedReturnValueChecker(Eng);
Zhongxing Xu5126c602010-06-16 05:45:09 +0000258 // CallAndMessageChecker should be registered before AttrNonNullChecker,
259 // where we assume arguments are not undefined.
Ted Kremenek32c49952009-11-25 21:51:20 +0000260 RegisterCallAndMessageChecker(Eng);
Zhongxing Xu5126c602010-06-16 05:45:09 +0000261 RegisterAttrNonNullChecker(Eng);
Ted Kremenek32c49952009-11-25 21:51:20 +0000262 RegisterDereferenceChecker(Eng);
263 RegisterVLASizeChecker(Eng);
264 RegisterDivZeroChecker(Eng);
Ted Kremenek32c49952009-11-25 21:51:20 +0000265 RegisterReturnUndefChecker(Eng);
266 RegisterUndefinedArraySubscriptChecker(Eng);
267 RegisterUndefinedAssignmentChecker(Eng);
268 RegisterUndefBranchChecker(Eng);
Ted Kremenek94fd0b82010-02-16 08:33:59 +0000269 RegisterUndefCapturedBlockVarChecker(Eng);
Ted Kremenek32c49952009-11-25 21:51:20 +0000270 RegisterUndefResultChecker(Eng);
Zhongxing Xu9b146832010-06-09 06:08:24 +0000271 RegisterStackAddrLeakChecker(Eng);
Ted Kremenek4f6aa772010-09-10 03:05:40 +0000272 RegisterObjCAtSyncChecker(Eng);
Zhongxing Xu935ef902009-12-07 09:17:35 +0000273
274 // This is not a checker yet.
275 RegisterNoReturnFunctionChecker(Eng);
Zhongxing Xu7c9624b2009-12-08 09:07:59 +0000276 RegisterBuiltinFunctionChecker(Eng);
Zhongxing Xu1ec4e972009-12-09 12:23:28 +0000277 RegisterOSAtomicChecker(Eng);
Ted Kremenek381d1bf2010-02-25 00:20:35 +0000278 RegisterUnixAPIChecker(Eng);
Ted Kremenekdf61b582010-02-25 05:44:09 +0000279 RegisterMacOSXAPIChecker(Eng);
Ted Kremeneke448ab42008-05-01 18:33:28 +0000280}
281
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000282ExprEngine::ExprEngine(AnalysisManager &mgr, TransferFuncs *tf)
Zhongxing Xu25e695b2009-08-15 03:17:38 +0000283 : AMgr(mgr),
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000284 Engine(*this),
285 G(Engine.getGraph()),
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000286 Builder(NULL),
Zhongxing Xuc77a5512010-07-01 07:10:59 +0000287 StateMgr(getContext(), mgr.getStoreManagerCreator(),
Ted Kremenek32a58082010-01-05 00:15:18 +0000288 mgr.getConstraintManagerCreator(), G.getAllocator(),
289 *this),
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000290 SymMgr(StateMgr.getSymbolManager()),
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000291 svalBuilder(StateMgr.getSValBuilder()),
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000292 EntryNode(NULL), currentStmt(NULL),
Zhongxing Xua5a41662008-12-22 08:30:52 +0000293 NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL),
Zhongxing Xuc77a5512010-07-01 07:10:59 +0000294 RaiseSel(GetNullarySelector("raise", getContext())),
Ted Kremenek32a58082010-01-05 00:15:18 +0000295 BR(mgr, *this), TF(tf) {
Ted Kremenekc80135b2009-11-25 21:45:48 +0000296 // Register internal checks.
Ted Kremenek32c49952009-11-25 21:51:20 +0000297 RegisterInternalChecks(*this);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000298
Ted Kremenek32a58082010-01-05 00:15:18 +0000299 // FIXME: Eventually remove the TF object entirely.
300 TF->RegisterChecks(*this);
301 TF->RegisterPrinters(getStateManager().Printers);
Ted Kremenekc80135b2009-11-25 21:45:48 +0000302}
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000303
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000304ExprEngine::~ExprEngine() {
Ted Kremenekcf118d42009-02-04 23:49:09 +0000305 BR.FlushReports();
Ted Kremeneke448ab42008-05-01 18:33:28 +0000306 delete [] NSExceptionInstanceRaiseSelectors;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000307
308 // Delete the set of checkers.
Ted Kremenek094bef52009-10-30 17:47:32 +0000309 for (CheckersOrdered::iterator I=Checkers.begin(), E=Checkers.end(); I!=E;++I)
Zhongxing Xuec9227f2009-10-29 02:09:30 +0000310 delete I->second;
Ted Kremenek9e9595b2010-06-25 20:59:31 +0000311
312 for (CheckersOrderedCache::iterator I=COCache.begin(), E=COCache.end();
313 I!=E;++I)
314 delete I->second;
Ted Kremenek50a6d0c2008-04-09 21:41:14 +0000315}
316
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000317//===----------------------------------------------------------------------===//
318// Utility methods.
319//===----------------------------------------------------------------------===//
320
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000321const GRState* ExprEngine::getInitialState(const LocationContext *InitLoc) {
Zhongxing Xu17fd8632009-08-17 06:19:58 +0000322 const GRState *state = StateMgr.getInitialState(InitLoc);
Mike Stump1eb44332009-09-09 15:08:12 +0000323
Ted Kremenekcfcd7fd2009-09-09 20:36:12 +0000324 // Preconditions.
325
Ted Kremenek52e56022009-04-10 00:59:50 +0000326 // FIXME: It would be nice if we had a more general mechanism to add
327 // such preconditions. Some day.
Ted Kremenek5974ec52009-12-17 19:17:27 +0000328 do {
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000329 const Decl *D = InitLoc->getDecl();
Ted Kremenek5974ec52009-12-17 19:17:27 +0000330 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
331 // Precondition: the first argument of 'main' is an integer guaranteed
332 // to be > 0.
333 const IdentifierInfo *II = FD->getIdentifier();
334 if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
335 break;
Ted Kremeneka591bc02009-06-18 22:57:13 +0000336
Ted Kremenek5974ec52009-12-17 19:17:27 +0000337 const ParmVarDecl *PD = FD->getParamDecl(0);
338 QualType T = PD->getType();
339 if (!T->isIntegerType())
340 break;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000341
Ted Kremenek5974ec52009-12-17 19:17:27 +0000342 const MemRegion *R = state->getRegion(PD, InitLoc);
343 if (!R)
344 break;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000345
Ted Kremenek13976632010-02-08 16:18:51 +0000346 SVal V = state->getSVal(loc::MemRegionVal(R));
Ted Kremenek9c149532010-12-01 21:57:22 +0000347 SVal Constraint_untested = evalBinOp(state, BO_GT, V,
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000348 svalBuilder.makeZeroVal(T),
Ted Kremenek5974ec52009-12-17 19:17:27 +0000349 getContext().IntTy);
350
351 DefinedOrUnknownSVal *Constraint =
352 dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000353
Ted Kremenek5974ec52009-12-17 19:17:27 +0000354 if (!Constraint)
355 break;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000356
Ted Kremenek28f47b92010-12-01 22:16:56 +0000357 if (const GRState *newState = state->assume(*Constraint, true))
Ted Kremenek5974ec52009-12-17 19:17:27 +0000358 state = newState;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000359
Ted Kremenek5974ec52009-12-17 19:17:27 +0000360 break;
361 }
362
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000363 if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
Ted Kremenek5974ec52009-12-17 19:17:27 +0000364 // Precondition: 'self' is always non-null upon entry to an Objective-C
365 // method.
366 const ImplicitParamDecl *SelfD = MD->getSelfDecl();
367 const MemRegion *R = state->getRegion(SelfD, InitLoc);
Ted Kremenek13976632010-02-08 16:18:51 +0000368 SVal V = state->getSVal(loc::MemRegionVal(R));
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000369
Ted Kremenek5974ec52009-12-17 19:17:27 +0000370 if (const Loc *LV = dyn_cast<Loc>(&V)) {
371 // Assume that the pointer value in 'self' is non-null.
Ted Kremenek28f47b92010-12-01 22:16:56 +0000372 state = state->assume(*LV, true);
Ted Kremenek5974ec52009-12-17 19:17:27 +0000373 assert(state && "'self' cannot be null");
Ted Kremenek5f75f922009-12-17 01:20:43 +0000374 }
Ted Kremenek52e56022009-04-10 00:59:50 +0000375 }
Ted Kremenek5974ec52009-12-17 19:17:27 +0000376 } while (0);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000377
Ted Kremenek52e56022009-04-10 00:59:50 +0000378 return state;
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000379}
380
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000381//===----------------------------------------------------------------------===//
382// Top-level transfer function logic (Dispatcher).
383//===----------------------------------------------------------------------===//
384
Ted Kremenek9c149532010-12-01 21:57:22 +0000385/// evalAssume - Called by ConstraintManager. Used to call checker-specific
Ted Kremenek32a58082010-01-05 00:15:18 +0000386/// logic for handling assumptions on symbolic values.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000387const GRState *ExprEngine::ProcessAssume(const GRState *state, SVal cond,
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000388 bool assumption) {
Jordy Rose72905cf2010-08-04 07:10:57 +0000389 // Determine if we already have a cached 'CheckersOrdered' vector
390 // specifically tailored for processing assumptions. This
391 // can reduce the number of checkers actually called.
392 CheckersOrdered *CO = &Checkers;
393 llvm::OwningPtr<CheckersOrdered> NewCO;
Ted Kremenek32a58082010-01-05 00:15:18 +0000394
Jordy Rose72905cf2010-08-04 07:10:57 +0000395 CallbackTag K = GetCallbackTag(ProcessAssumeCallback);
396 CheckersOrdered *& CO_Ref = COCache[K];
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000397
Jordy Rose72905cf2010-08-04 07:10:57 +0000398 if (!CO_Ref) {
399 // If we have no previously cached CheckersOrdered vector for this
400 // statement kind, then create one.
401 NewCO.reset(new CheckersOrdered);
402 }
403 else {
404 // Use the already cached set.
405 CO = CO_Ref;
Ted Kremenek32a58082010-01-05 00:15:18 +0000406 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000407
Jordy Rose72905cf2010-08-04 07:10:57 +0000408 if (!CO->empty()) {
409 // Let the checkers have a crack at the assume before the transfer functions
410 // get their turn.
Jordy Rosea2050612010-08-12 04:05:07 +0000411 for (CheckersOrdered::iterator I = CO->begin(), E = CO->end(); I!=E; ++I) {
Jordy Rose72905cf2010-08-04 07:10:57 +0000412
413 // If any checker declares the state infeasible (or if it starts that
414 // way), bail out.
415 if (!state)
416 return NULL;
417
418 Checker *C = I->second;
419 bool respondsToCallback = true;
420
Ted Kremenek9c149532010-12-01 21:57:22 +0000421 state = C->evalAssume(state, cond, assumption, &respondsToCallback);
Jordy Rose72905cf2010-08-04 07:10:57 +0000422
Ted Kremenek28f47b92010-12-01 22:16:56 +0000423 // Check if we're building the cache of checkers that care about
424 // assumptions.
Jordy Rose72905cf2010-08-04 07:10:57 +0000425 if (NewCO.get() && respondsToCallback)
426 NewCO->push_back(*I);
427 }
428
429 // If we got through all the checkers, and we built a list of those that
Ted Kremenek28f47b92010-12-01 22:16:56 +0000430 // care about assumptions, save it.
Jordy Rose72905cf2010-08-04 07:10:57 +0000431 if (NewCO.get())
432 CO_Ref = NewCO.take();
433 }
434
435 // If the state is infeasible at this point, bail out.
Ted Kremenek32a58082010-01-05 00:15:18 +0000436 if (!state)
437 return NULL;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000438
Ted Kremenek9c149532010-12-01 21:57:22 +0000439 return TF->evalAssume(state, cond, assumption);
Ted Kremenek32a58082010-01-05 00:15:18 +0000440}
441
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000442bool ExprEngine::WantsRegionChangeUpdate(const GRState* state) {
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000443 CallbackTag K = GetCallbackTag(EvalRegionChangesCallback);
444 CheckersOrdered *CO = COCache[K];
445
446 if (!CO)
447 CO = &Checkers;
448
449 for (CheckersOrdered::iterator I = CO->begin(), E = CO->end(); I != E; ++I) {
450 Checker *C = I->second;
451 if (C->WantsRegionChangeUpdate(state))
452 return true;
453 }
454
455 return false;
456}
457
458const GRState *
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000459ExprEngine::ProcessRegionChanges(const GRState *state,
Jordy Rosec2b7dfa2010-08-14 20:44:32 +0000460 const MemRegion * const *Begin,
461 const MemRegion * const *End) {
462 // FIXME: Most of this method is copy-pasted from ProcessAssume.
463
464 // Determine if we already have a cached 'CheckersOrdered' vector
465 // specifically tailored for processing region changes. This
466 // can reduce the number of checkers actually called.
467 CheckersOrdered *CO = &Checkers;
468 llvm::OwningPtr<CheckersOrdered> NewCO;
469
470 CallbackTag K = GetCallbackTag(EvalRegionChangesCallback);
471 CheckersOrdered *& CO_Ref = COCache[K];
472
473 if (!CO_Ref) {
474 // If we have no previously cached CheckersOrdered vector for this
475 // callback, then create one.
476 NewCO.reset(new CheckersOrdered);
477 }
478 else {
479 // Use the already cached set.
480 CO = CO_Ref;
481 }
482
483 // If there are no checkers, just return the state as is.
484 if (CO->empty())
485 return state;
486
487 for (CheckersOrdered::iterator I = CO->begin(), E = CO->end(); I != E; ++I) {
488 // If any checker declares the state infeasible (or if it starts that way),
489 // bail out.
490 if (!state)
491 return NULL;
492
493 Checker *C = I->second;
494 bool respondsToCallback = true;
495
496 state = C->EvalRegionChanges(state, Begin, End, &respondsToCallback);
497
498 // See if we're building a cache of checkers that care about region changes.
499 if (NewCO.get() && respondsToCallback)
500 NewCO->push_back(*I);
501 }
502
503 // If we got through all the checkers, and we built a list of those that
504 // care about region changes, save it.
505 if (NewCO.get())
506 CO_Ref = NewCO.take();
507
508 return state;
509}
510
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000511void ExprEngine::ProcessEndWorklist(bool hasWorkRemaining) {
Ted Kremenekccc263b2010-06-23 22:08:00 +0000512 for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
513 I != E; ++I) {
Tom Carebc42c532010-08-03 01:55:07 +0000514 I->second->VisitEndAnalysis(G, BR, *this);
Ted Kremenekccc263b2010-06-23 22:08:00 +0000515 }
516}
517
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000518void ExprEngine::ProcessElement(const CFGElement E,
519 StmtNodeBuilder& builder) {
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000520 switch (E.getKind()) {
521 case CFGElement::Statement:
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000522 ProcessStmt(E.getAs<CFGStmt>(), builder);
523 break;
524 case CFGElement::Initializer:
525 ProcessInitializer(E.getAs<CFGInitializer>(), builder);
526 break;
527 case CFGElement::ImplicitDtor:
528 ProcessImplicitDtor(E.getAs<CFGImplicitDtor>(), builder);
529 break;
530 default:
531 // Suppress compiler warning.
532 llvm_unreachable("Unexpected CFGElement kind.");
533 }
534}
535
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000536void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000537 currentStmt = S.getStmt();
Ted Kremenek0bed8a12009-03-11 02:41:36 +0000538 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000539 currentStmt->getLocStart(),
Ted Kremenek0bed8a12009-03-11 02:41:36 +0000540 "Error evaluating statement");
Mike Stump1eb44332009-09-09 15:08:12 +0000541
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000542 Builder = &builder;
Zhongxing Xu25108a52010-02-26 02:38:09 +0000543 EntryNode = builder.getBasePredecessor();
Mike Stump1eb44332009-09-09 15:08:12 +0000544
Mike Stump1eb44332009-09-09 15:08:12 +0000545 // Create the cleaned state.
Jordy Rosebd533aa2010-08-14 20:18:45 +0000546 const LocationContext *LC = EntryNode->getLocationContext();
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000547 SymbolReaper SymReaper(LC, currentStmt, SymMgr);
Zhongxing Xuc179a7f2010-03-05 04:45:36 +0000548
Jordy Rosebd533aa2010-08-14 20:18:45 +0000549 if (AMgr.shouldPurgeDead()) {
550 const GRState *St = EntryNode->getState();
Zhongxing Xuc179a7f2010-03-05 04:45:36 +0000551
Jordy Rosebd533aa2010-08-14 20:18:45 +0000552 for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
553 I != E; ++I) {
554 Checker *checker = I->second;
555 checker->MarkLiveSymbols(St, SymReaper);
556 }
557
558 const StackFrameContext *SFC = LC->getCurrentStackFrame();
559 CleanedState = StateMgr.RemoveDeadBindings(St, SFC, SymReaper);
560 } else {
561 CleanedState = EntryNode->getState();
562 }
Ted Kremenek241677a2009-01-21 22:26:05 +0000563
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000564 // Process any special transfer function for dead symbols.
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000565 ExplodedNodeSet Tmp;
Mike Stump1eb44332009-09-09 15:08:12 +0000566
Ted Kremenek241677a2009-01-21 22:26:05 +0000567 if (!SymReaper.hasDeadSymbols())
Ted Kremenek846d4e92008-04-24 23:35:58 +0000568 Tmp.Add(EntryNode);
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000569 else {
570 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000571 SaveOr OldHasGen(Builder->HasGeneratedNode);
572
Ted Kremenek331b0ac2008-06-18 05:34:07 +0000573 SaveAndRestore<bool> OldPurgeDeadSymbols(Builder->PurgingDeadSymbols);
574 Builder->PurgingDeadSymbols = true;
Mike Stump1eb44332009-09-09 15:08:12 +0000575
Zhongxing Xu94006132009-11-13 06:53:04 +0000576 // FIXME: This should soon be removed.
577 ExplodedNodeSet Tmp2;
Ted Kremenek9c149532010-12-01 21:57:22 +0000578 getTF().evalDeadSymbols(Tmp2, *this, *Builder, EntryNode,
Ted Kremenek241677a2009-01-21 22:26:05 +0000579 CleanedState, SymReaper);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000580
Zhongxing Xu94006132009-11-13 06:53:04 +0000581 if (Checkers.empty())
Zhongxing Xu7fbb1ba2009-12-14 02:13:39 +0000582 Tmp.insert(Tmp2);
Zhongxing Xu94006132009-11-13 06:53:04 +0000583 else {
584 ExplodedNodeSet Tmp3;
585 ExplodedNodeSet *SrcSet = &Tmp2;
586 for (CheckersOrdered::iterator I = Checkers.begin(), E = Checkers.end();
587 I != E; ++I) {
Ted Kremenek17f4da82009-12-09 02:45:41 +0000588 ExplodedNodeSet *DstSet = 0;
589 if (I+1 == E)
590 DstSet = &Tmp;
591 else {
592 DstSet = (SrcSet == &Tmp2) ? &Tmp3 : &Tmp2;
593 DstSet->clear();
594 }
595
Zhongxing Xu94006132009-11-13 06:53:04 +0000596 void *tag = I->first;
597 Checker *checker = I->second;
598 for (ExplodedNodeSet::iterator NI = SrcSet->begin(), NE = SrcSet->end();
599 NI != NE; ++NI)
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000600 checker->GR_evalDeadSymbols(*DstSet, *Builder, *this, currentStmt,
Ted Kremenek852274d2009-12-16 03:18:58 +0000601 *NI, SymReaper, tag);
Zhongxing Xu94006132009-11-13 06:53:04 +0000602 SrcSet = DstSet;
603 }
604 }
605
Ted Kremenek846d4e92008-04-24 23:35:58 +0000606 if (!Builder->BuildSinks && !Builder->HasGeneratedNode)
607 Tmp.Add(EntryNode);
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000608 }
Mike Stump1eb44332009-09-09 15:08:12 +0000609
Ted Kremenek846d4e92008-04-24 23:35:58 +0000610 bool HasAutoGenerated = false;
611
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000612 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000613 ExplodedNodeSet Dst;
Mike Stump1eb44332009-09-09 15:08:12 +0000614
615 // Set the cleaned state.
Ted Kremenek846d4e92008-04-24 23:35:58 +0000616 Builder->SetCleanedState(*I == EntryNode ? CleanedState : GetState(*I));
Mike Stump1eb44332009-09-09 15:08:12 +0000617
618 // Visit the statement.
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000619 Visit(currentStmt, *I, Dst);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000620
621 // Do we need to auto-generate a node? We only need to do this to generate
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000622 // a node with a "cleaned" state; CoreEngine will actually handle
Mike Stump1eb44332009-09-09 15:08:12 +0000623 // auto-transitions for other cases.
Ted Kremenek846d4e92008-04-24 23:35:58 +0000624 if (Dst.size() == 1 && *Dst.begin() == EntryNode
625 && !Builder->HasGeneratedNode && !HasAutoGenerated) {
626 HasAutoGenerated = true;
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000627 builder.generateNode(currentStmt, GetState(EntryNode), *I);
Ted Kremenek846d4e92008-04-24 23:35:58 +0000628 }
Ted Kremenek77d7ef82008-04-24 18:31:42 +0000629 }
Mike Stump1eb44332009-09-09 15:08:12 +0000630
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000631 // NULL out these variables to cleanup.
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000632 CleanedState = NULL;
Ted Kremenek846d4e92008-04-24 23:35:58 +0000633 EntryNode = NULL;
Ted Kremenekdf7533b2008-07-17 21:27:31 +0000634
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000635 currentStmt = 0;
Mike Stump1eb44332009-09-09 15:08:12 +0000636
Ted Kremenek846d4e92008-04-24 23:35:58 +0000637 Builder = NULL;
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000638}
639
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000640void ExprEngine::ProcessInitializer(const CFGInitializer Init,
641 StmtNodeBuilder &builder) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000642 // We don't set EntryNode and currentStmt. And we don't clean up state.
Sean Huntcbb67482011-01-08 20:30:50 +0000643 const CXXCtorInitializer *BMI = Init.getInitializer();
Zhongxing Xu9dc84c92010-11-16 07:52:17 +0000644
645 ExplodedNode *Pred = builder.getBasePredecessor();
646 const LocationContext *LC = Pred->getLocationContext();
647
Francois Pichet00eb3f92010-12-04 09:14:42 +0000648 if (BMI->isAnyMemberInitializer()) {
Zhongxing Xu9dc84c92010-11-16 07:52:17 +0000649 ExplodedNodeSet Dst;
650
651 // Evaluate the initializer.
652 Visit(BMI->getInit(), Pred, Dst);
653
654 for (ExplodedNodeSet::iterator I = Dst.begin(), E = Dst.end(); I != E; ++I){
655 ExplodedNode *Pred = *I;
656 const GRState *state = Pred->getState();
657
Francois Pichet00eb3f92010-12-04 09:14:42 +0000658 const FieldDecl *FD = BMI->getAnyMember();
Zhongxing Xu9dc84c92010-11-16 07:52:17 +0000659 const RecordDecl *RD = FD->getParent();
660 const CXXThisRegion *ThisR = getCXXThisRegion(cast<CXXRecordDecl>(RD),
661 cast<StackFrameContext>(LC));
662
663 SVal ThisV = state->getSVal(ThisR);
664 SVal FieldLoc = state->getLValue(FD, ThisV);
665 SVal InitVal = state->getSVal(BMI->getInit());
666 state = state->bindLoc(FieldLoc, InitVal);
667
668 // Use a custom node building process.
669 PostInitializer PP(BMI, LC);
670 // Builder automatically add the generated node to the deferred set,
671 // which are processed in the builder's dtor.
672 builder.generateNode(PP, state, Pred);
673 }
674 }
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000675}
676
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000677void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
678 StmtNodeBuilder &builder) {
Zhongxing Xub13453b2010-11-20 06:53:12 +0000679 Builder = &builder;
680
Zhongxing Xu4ffcb992010-11-17 09:16:19 +0000681 switch (D.getDtorKind()) {
682 case CFGElement::AutomaticObjectDtor:
683 ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), builder);
684 break;
685 case CFGElement::BaseDtor:
686 ProcessBaseDtor(cast<CFGBaseDtor>(D), builder);
687 break;
688 case CFGElement::MemberDtor:
689 ProcessMemberDtor(cast<CFGMemberDtor>(D), builder);
690 break;
691 case CFGElement::TemporaryDtor:
692 ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), builder);
693 break;
694 default:
695 llvm_unreachable("Unexpected dtor kind.");
696 }
697}
698
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000699void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor dtor,
700 StmtNodeBuilder &builder) {
Zhongxing Xu22104902010-11-25 06:35:14 +0000701 ExplodedNode *pred = builder.getBasePredecessor();
702 const GRState *state = pred->getState();
703 const VarDecl *varDecl = dtor.getVarDecl();
Zhongxing Xub13453b2010-11-20 06:53:12 +0000704
Zhongxing Xu22104902010-11-25 06:35:14 +0000705 QualType varType = varDecl->getType();
Zhongxing Xub13453b2010-11-20 06:53:12 +0000706
Zhongxing Xu22104902010-11-25 06:35:14 +0000707 if (const ReferenceType *refType = varType->getAs<ReferenceType>())
708 varType = refType->getPointeeType();
709
710 const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl();
711 assert(recordDecl && "get CXXRecordDecl fail");
712 const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor();
713
714 Loc dest = state->getLValue(varDecl, pred->getLocationContext());
715
716 ExplodedNodeSet dstSet;
717 VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(),
718 dtor.getTriggerStmt(), pred, dstSet);
Zhongxing Xu4ffcb992010-11-17 09:16:19 +0000719}
720
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000721void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
722 StmtNodeBuilder &builder) {
Zhongxing Xu4ffcb992010-11-17 09:16:19 +0000723}
724
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000725void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
726 StmtNodeBuilder &builder) {
Zhongxing Xu4ffcb992010-11-17 09:16:19 +0000727}
728
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000729void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
730 StmtNodeBuilder &builder) {
Zhongxing Xu9c6cd672010-11-15 08:48:43 +0000731}
732
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +0000733void ExprEngine::Visit(const Stmt* S, ExplodedNode* Pred,
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000734 ExplodedNodeSet& Dst) {
Ted Kremenek0bed8a12009-03-11 02:41:36 +0000735 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
736 S->getLocStart(),
737 "Error evaluating statement");
738
John McCallf6a16482010-12-04 03:47:34 +0000739 // Expressions to ignore.
740 if (const Expr *Ex = dyn_cast<Expr>(S))
Ted Kremenek892697d2010-12-16 07:46:53 +0000741 S = Ex->IgnoreParens();
John McCallf6a16482010-12-04 03:47:34 +0000742
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000743 // FIXME: add metadata to the CFG so that we can disable
744 // this check when we KNOW that there is no block-level subexpression.
745 // The motivation is that this check requires a hashtable lookup.
Mike Stump1eb44332009-09-09 15:08:12 +0000746
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000747 if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S)) {
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000748 Dst.Add(Pred);
749 return;
750 }
Mike Stump1eb44332009-09-09 15:08:12 +0000751
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000752 switch (S->getStmtClass()) {
Ted Kremenekc768a0c2009-12-15 01:38:04 +0000753 // C++ stuff we don't support yet.
Ted Kremenekc768a0c2009-12-15 01:38:04 +0000754 case Stmt::CXXBindTemporaryExprClass:
Ted Kremenekc768a0c2009-12-15 01:38:04 +0000755 case Stmt::CXXCatchStmtClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000756 case Stmt::CXXDefaultArgExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000757 case Stmt::CXXDependentScopeMemberExprClass:
John McCall4765fa02010-12-06 08:20:24 +0000758 case Stmt::ExprWithCleanupsClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000759 case Stmt::CXXNullPtrLiteralExprClass:
760 case Stmt::CXXPseudoDestructorExprClass:
761 case Stmt::CXXTemporaryObjectExprClass:
762 case Stmt::CXXThrowExprClass:
763 case Stmt::CXXTryStmtClass:
764 case Stmt::CXXTypeidExprClass:
Francois Pichet9be88402010-09-08 23:47:05 +0000765 case Stmt::CXXUuidofExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000766 case Stmt::CXXUnresolvedConstructExprClass:
Douglas Gregored8abf12010-07-08 06:14:04 +0000767 case Stmt::CXXScalarValueInitExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000768 case Stmt::DependentScopeDeclRefExprClass:
769 case Stmt::UnaryTypeTraitExprClass:
Francois Pichet6ad6f282010-12-07 00:08:36 +0000770 case Stmt::BinaryTypeTraitExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000771 case Stmt::UnresolvedLookupExprClass:
772 case Stmt::UnresolvedMemberExprClass:
Sebastian Redl6b219d02010-09-10 20:55:54 +0000773 case Stmt::CXXNoexceptExprClass:
Douglas Gregorbe230c32011-01-03 17:17:50 +0000774 case Stmt::PackExpansionExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000775 {
Ted Kremenekc768a0c2009-12-15 01:38:04 +0000776 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
777 Builder->BuildSinks = true;
778 MakeNode(Dst, S, Pred, GetState(Pred));
779 break;
780 }
John McCallf6a16482010-12-04 03:47:34 +0000781
782 case Stmt::ParenExprClass:
783 llvm_unreachable("ParenExprs already handled.");
Ted Kremenek1b49d762010-04-15 17:33:31 +0000784 // Cases that should never be evaluated simply because they shouldn't
785 // appear in the CFG.
786 case Stmt::BreakStmtClass:
787 case Stmt::CaseStmtClass:
788 case Stmt::CompoundStmtClass:
789 case Stmt::ContinueStmtClass:
790 case Stmt::DefaultStmtClass:
791 case Stmt::DoStmtClass:
792 case Stmt::GotoStmtClass:
793 case Stmt::IndirectGotoStmtClass:
794 case Stmt::LabelStmtClass:
795 case Stmt::NoStmtClass:
796 case Stmt::NullStmtClass:
797 case Stmt::SwitchCaseClass:
John McCall7cd7d1a2010-11-15 23:31:06 +0000798 case Stmt::OpaqueValueExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000799 llvm_unreachable("Stmt should not be in analyzer evaluation loop");
800 break;
801
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +0000802 case Stmt::GNUNullExprClass: {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000803 MakeNode(Dst, S, Pred, GetState(Pred)->BindExpr(S, svalBuilder.makeNull()));
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +0000804 break;
805 }
806
Ted Kremenek4beaa9f2010-09-10 03:05:33 +0000807 case Stmt::ObjCAtSynchronizedStmtClass:
808 VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
809 break;
810
Ted Kremenek1b49d762010-04-15 17:33:31 +0000811 // Cases not handled yet; but will handle some day.
812 case Stmt::DesignatedInitExprClass:
813 case Stmt::ExtVectorElementExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000814 case Stmt::ImaginaryLiteralClass:
815 case Stmt::ImplicitValueInitExprClass:
816 case Stmt::ObjCAtCatchStmtClass:
817 case Stmt::ObjCAtFinallyStmtClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000818 case Stmt::ObjCAtTryStmtClass:
819 case Stmt::ObjCEncodeExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000820 case Stmt::ObjCIsaExprClass:
821 case Stmt::ObjCPropertyRefExprClass:
822 case Stmt::ObjCProtocolExprClass:
823 case Stmt::ObjCSelectorExprClass:
824 case Stmt::ObjCStringLiteralClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000825 case Stmt::ParenListExprClass:
826 case Stmt::PredefinedExprClass:
827 case Stmt::ShuffleVectorExprClass:
Ted Kremenek1b49d762010-04-15 17:33:31 +0000828 case Stmt::VAArgExprClass:
829 // Fall through.
830
831 // Cases we intentionally don't evaluate, since they don't need
832 // to be explicitly evaluated.
Zhongxing Xubc9ad742010-04-13 13:15:19 +0000833 case Stmt::AddrLabelExprClass:
834 case Stmt::IntegerLiteralClass:
835 case Stmt::CharacterLiteralClass:
Zhongxing Xu477323d2010-04-14 06:29:29 +0000836 case Stmt::CXXBoolLiteralExprClass:
Zhongxing Xubc9ad742010-04-13 13:15:19 +0000837 case Stmt::FloatingLiteralClass:
Douglas Gregorf901a7d2011-01-04 18:46:34 +0000838 case Stmt::SizeOfPackExprClass:
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000839 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
840 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000841
Ted Kremenek540cbe22008-04-22 04:56:29 +0000842 case Stmt::ArraySubscriptExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000843 VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
Ted Kremenek540cbe22008-04-22 04:56:29 +0000844 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000845
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000846 case Stmt::AsmStmtClass:
847 VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst);
848 break;
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000849
Ted Kremenek892697d2010-12-16 07:46:53 +0000850 case Stmt::BlockDeclRefExprClass: {
851 const BlockDeclRefExpr *BE = cast<BlockDeclRefExpr>(S);
852 VisitCommonDeclRefExpr(BE, BE->getDecl(), Pred, Dst);
Ted Kremenek67d12872009-12-07 22:05:27 +0000853 break;
Ted Kremenek892697d2010-12-16 07:46:53 +0000854 }
Mike Stump1eb44332009-09-09 15:08:12 +0000855
Ted Kremenekc95ad9f2009-11-25 01:33:13 +0000856 case Stmt::BlockExprClass:
857 VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
858 break;
859
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000860 case Stmt::BinaryOperatorClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000861 const BinaryOperator* B = cast<BinaryOperator>(S);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000862 if (B->isLogicalOp()) {
863 VisitLogicalExpr(B, Pred, Dst);
864 break;
865 }
John McCall2de56d12010-08-25 11:45:40 +0000866 else if (B->getOpcode() == BO_Comma) {
Ted Kremeneka8538d92009-02-13 01:45:31 +0000867 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +0000868 MakeNode(Dst, B, Pred, state->BindExpr(B, state->getSVal(B->getRHS())));
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000869 break;
870 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000871
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000872 if (AMgr.shouldEagerlyAssume() &&
Zhongxing Xubb141212009-12-16 11:27:52 +0000873 (B->isRelationalOp() || B->isEqualityOp())) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +0000874 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +0000875 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
Ted Kremenek9c149532010-12-01 21:57:22 +0000876 evalEagerlyAssume(Dst, Tmp, cast<Expr>(S));
Ted Kremenek48af2a92009-02-25 22:32:02 +0000877 }
878 else
Ted Kremenek892697d2010-12-16 07:46:53 +0000879 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
Ted Kremenek48af2a92009-02-25 22:32:02 +0000880
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000881 break;
882 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000883
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000884 case Stmt::CallExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000885 const CallExpr* C = cast<CallExpr>(S);
Ted Kremenek892697d2010-12-16 07:46:53 +0000886 VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst);
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000887 break;
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000888 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +0000889
Zhongxing Xu7ce351d2010-11-01 09:09:44 +0000890 case Stmt::CXXConstructExprClass: {
891 const CXXConstructExpr *C = cast<CXXConstructExpr>(S);
892 // For block-level CXXConstructExpr, we don't have a destination region.
893 // Let VisitCXXConstructExpr() create one.
Ted Kremenek892697d2010-12-16 07:46:53 +0000894 VisitCXXConstructExpr(C, 0, Pred, Dst);
Zhongxing Xu7ce351d2010-11-01 09:09:44 +0000895 break;
896 }
897
Zhongxing Xu950db872010-04-01 07:58:50 +0000898 case Stmt::CXXMemberCallExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000899 const CXXMemberCallExpr *MCE = cast<CXXMemberCallExpr>(S);
Zhongxing Xu950db872010-04-01 07:58:50 +0000900 VisitCXXMemberCallExpr(MCE, Pred, Dst);
901 break;
902 }
903
Marcin Swiderski6a02b602010-11-18 06:29:23 +0000904 case Stmt::CXXOperatorCallExprClass: {
905 const CXXOperatorCallExpr *C = cast<CXXOperatorCallExpr>(S);
906 VisitCXXOperatorCallExpr(C, Pred, Dst);
907 break;
908 }
909
Zhongxing Xu856c6bc2010-04-19 11:47:28 +0000910 case Stmt::CXXNewExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000911 const CXXNewExpr *NE = cast<CXXNewExpr>(S);
Zhongxing Xu856c6bc2010-04-19 11:47:28 +0000912 VisitCXXNewExpr(NE, Pred, Dst);
913 break;
914 }
915
Zhongxing Xu6b851382010-04-21 02:17:31 +0000916 case Stmt::CXXDeleteExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000917 const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S);
Zhongxing Xu6b851382010-04-21 02:17:31 +0000918 VisitCXXDeleteExpr(CDE, Pred, Dst);
919 break;
920 }
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000921 // FIXME: ChooseExpr is really a constant. We need to fix
922 // the CFG do not model them as explicit control-flow.
Mike Stump1eb44332009-09-09 15:08:12 +0000923
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000924 case Stmt::ChooseExprClass: { // __builtin_choose_expr
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000925 const ChooseExpr* C = cast<ChooseExpr>(S);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000926 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
927 break;
928 }
Mike Stump1eb44332009-09-09 15:08:12 +0000929
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000930 case Stmt::CompoundAssignOperatorClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000931 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000932 break;
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000933
934 case Stmt::CompoundLiteralExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000935 VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000936 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000937
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000938 case Stmt::ConditionalOperatorClass: { // '?' operator
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000939 const ConditionalOperator* C = cast<ConditionalOperator>(S);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000940 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
941 break;
942 }
Mike Stump1eb44332009-09-09 15:08:12 +0000943
Zhongxing Xubb141212009-12-16 11:27:52 +0000944 case Stmt::CXXThisExprClass:
945 VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
946 break;
947
Ted Kremenek892697d2010-12-16 07:46:53 +0000948 case Stmt::DeclRefExprClass: {
949 const DeclRefExpr *DE = cast<DeclRefExpr>(S);
950 VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000951 break;
Ted Kremenek892697d2010-12-16 07:46:53 +0000952 }
Mike Stump1eb44332009-09-09 15:08:12 +0000953
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000954 case Stmt::DeclStmtClass:
955 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
956 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000957
Ted Kremenek919f0662009-12-24 01:49:25 +0000958 case Stmt::ForStmtClass:
959 // This case isn't for branch processing, but for handling the
960 // initialization of a condition variable.
961 VisitCondInit(cast<ForStmt>(S)->getConditionVariable(), S, Pred, Dst);
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000962 break;
Ted Kremenek919f0662009-12-24 01:49:25 +0000963
Argyrios Kyrtzidis0835a3c2008-08-18 23:01:59 +0000964 case Stmt::ImplicitCastExprClass:
Zhongxing Xu0d9d7362010-04-13 12:38:32 +0000965 case Stmt::CStyleCastExprClass:
966 case Stmt::CXXStaticCastExprClass:
967 case Stmt::CXXDynamicCastExprClass:
968 case Stmt::CXXReinterpretCastExprClass:
969 case Stmt::CXXConstCastExprClass:
970 case Stmt::CXXFunctionalCastExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +0000971 const CastExpr* C = cast<CastExpr>(S);
Ted Kremenek892697d2010-12-16 07:46:53 +0000972 VisitCast(C, C->getSubExpr(), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000973 break;
974 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +0000975
Ted Kremenek61dfbec2009-12-23 04:49:01 +0000976 case Stmt::IfStmtClass:
977 // This case isn't for branch processing, but for handling the
978 // initialization of a condition variable.
Ted Kremenekfcfb5032009-12-24 00:40:03 +0000979 VisitCondInit(cast<IfStmt>(S)->getConditionVariable(), S, Pred, Dst);
Ted Kremenek61dfbec2009-12-23 04:49:01 +0000980 break;
Zhongxing Xuc4f87062008-10-30 05:02:23 +0000981
982 case Stmt::InitListExprClass:
983 VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
984 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000985
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000986 case Stmt::MemberExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000987 VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
Ted Kremenek469ecbd2008-04-21 23:43:38 +0000988 break;
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000989 case Stmt::ObjCIvarRefExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000990 VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
Ted Kremenek97ed4f62008-10-17 00:03:18 +0000991 break;
Ted Kremenekaf337412008-11-12 19:24:17 +0000992
993 case Stmt::ObjCForCollectionStmtClass:
994 VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
995 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000996
Ted Kremenek38ac4f52009-12-22 22:13:46 +0000997 case Stmt::ObjCMessageExprClass:
Ted Kremenek892697d2010-12-16 07:46:53 +0000998 VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +0000999 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001000
Ted Kremenekbbfd07a2008-12-09 20:18:58 +00001001 case Stmt::ObjCAtThrowStmtClass: {
1002 // FIXME: This is not complete. We basically treat @throw as
1003 // an abort.
1004 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
1005 Builder->BuildSinks = true;
1006 MakeNode(Dst, S, Pred, GetState(Pred));
1007 break;
1008 }
Mike Stump1eb44332009-09-09 15:08:12 +00001009
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001010 case Stmt::ReturnStmtClass:
1011 VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
1012 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001013
Douglas Gregor8ecdb652010-04-28 22:16:22 +00001014 case Stmt::OffsetOfExprClass:
1015 VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst);
1016 break;
1017
Sebastian Redl05189992008-11-11 17:56:53 +00001018 case Stmt::SizeOfAlignOfExprClass:
1019 VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001020 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001021
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001022 case Stmt::StmtExprClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001023 const StmtExpr* SE = cast<StmtExpr>(S);
Ted Kremeneka3d1eb82009-02-14 05:55:08 +00001024
1025 if (SE->getSubStmt()->body_empty()) {
1026 // Empty statement expression.
1027 assert(SE->getType() == getContext().VoidTy
1028 && "Empty statement expression must have void type.");
1029 Dst.Add(Pred);
1030 break;
1031 }
Mike Stump1eb44332009-09-09 15:08:12 +00001032
Ted Kremeneka3d1eb82009-02-14 05:55:08 +00001033 if (Expr* LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1034 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +00001035 MakeNode(Dst, SE, Pred, state->BindExpr(SE, state->getSVal(LastExpr)));
Ted Kremeneka3d1eb82009-02-14 05:55:08 +00001036 }
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001037 else
1038 Dst.Add(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00001039
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001040 break;
1041 }
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001042
Ted Kremenek892697d2010-12-16 07:46:53 +00001043 case Stmt::StringLiteralClass: {
1044 const GRState* state = GetState(Pred);
1045 SVal V = state->getLValue(cast<StringLiteral>(S));
1046 MakeNode(Dst, S, Pred, state->BindExpr(S, V));
1047 return;
1048 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001049
Ted Kremenekfcfb5032009-12-24 00:40:03 +00001050 case Stmt::SwitchStmtClass:
1051 // This case isn't for branch processing, but for handling the
1052 // initialization of a condition variable.
1053 VisitCondInit(cast<SwitchStmt>(S)->getConditionVariable(), S, Pred, Dst);
1054 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001055
Ted Kremenek72374592009-03-18 23:49:26 +00001056 case Stmt::UnaryOperatorClass: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001057 const UnaryOperator *U = cast<UnaryOperator>(S);
John McCall2de56d12010-08-25 11:45:40 +00001058 if (AMgr.shouldEagerlyAssume()&&(U->getOpcode() == UO_LNot)) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001059 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00001060 VisitUnaryOperator(U, Pred, Tmp);
Ted Kremenek9c149532010-12-01 21:57:22 +00001061 evalEagerlyAssume(Dst, Tmp, U);
Ted Kremenek72374592009-03-18 23:49:26 +00001062 }
1063 else
Ted Kremenek892697d2010-12-16 07:46:53 +00001064 VisitUnaryOperator(U, Pred, Dst);
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001065 break;
Ted Kremenek72374592009-03-18 23:49:26 +00001066 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001067
Ted Kremenek4c508a12009-12-24 00:54:56 +00001068 case Stmt::WhileStmtClass:
1069 // This case isn't for branch processing, but for handling the
1070 // initialization of a condition variable.
1071 VisitCondInit(cast<WhileStmt>(S)->getConditionVariable(), S, Pred, Dst);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001072 break;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001073 }
1074}
1075
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001076//===----------------------------------------------------------------------===//
1077// Block entrance. (Update counters).
1078//===----------------------------------------------------------------------===//
1079
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001080bool ExprEngine::ProcessBlockEntrance(const CFGBlock* B,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001081 const ExplodedNode *Pred,
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001082 BlockCounter BC) {
Zhongxing Xud9e0c0f2010-03-23 05:05:02 +00001083 return BC.getNumVisited(Pred->getLocationContext()->getCurrentStackFrame(),
Tom Care68625cf2010-09-14 21:35:27 +00001084 B->getBlockID()) < AMgr.getMaxVisit();
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001085}
1086
1087//===----------------------------------------------------------------------===//
Ted Kremenek1670e402009-04-11 00:11:10 +00001088// Generic node creation.
1089//===----------------------------------------------------------------------===//
1090
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001091ExplodedNode* ExprEngine::MakeNode(ExplodedNodeSet& Dst, const Stmt* S,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001092 ExplodedNode* Pred, const GRState* St,
1093 ProgramPoint::Kind K, const void *tag) {
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001094 assert (Builder && "StmtNodeBuilder not present.");
Ted Kremenek1670e402009-04-11 00:11:10 +00001095 SaveAndRestore<const void*> OldTag(Builder->Tag);
1096 Builder->Tag = tag;
1097 return Builder->MakeNode(Dst, S, Pred, St, K);
1098}
1099
1100//===----------------------------------------------------------------------===//
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001101// Branch processing.
1102//===----------------------------------------------------------------------===//
1103
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001104const GRState* ExprEngine::MarkBranch(const GRState* state,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001105 const Stmt* Terminator,
1106 bool branchTaken) {
Mike Stump1eb44332009-09-09 15:08:12 +00001107
Ted Kremenek05a23782008-02-26 19:05:15 +00001108 switch (Terminator->getStmtClass()) {
1109 default:
Ted Kremeneka8538d92009-02-13 01:45:31 +00001110 return state;
Mike Stump1eb44332009-09-09 15:08:12 +00001111
Ted Kremenek05a23782008-02-26 19:05:15 +00001112 case Stmt::BinaryOperatorClass: { // '&&' and '||'
Mike Stump1eb44332009-09-09 15:08:12 +00001113
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001114 const BinaryOperator* B = cast<BinaryOperator>(Terminator);
Ted Kremenek05a23782008-02-26 19:05:15 +00001115 BinaryOperator::Opcode Op = B->getOpcode();
Mike Stump1eb44332009-09-09 15:08:12 +00001116
John McCall2de56d12010-08-25 11:45:40 +00001117 assert (Op == BO_LAnd || Op == BO_LOr);
Mike Stump1eb44332009-09-09 15:08:12 +00001118
Ted Kremenek05a23782008-02-26 19:05:15 +00001119 // For &&, if we take the true branch, then the value of the whole
1120 // expression is that of the RHS expression.
1121 //
1122 // For ||, if we take the false branch, then the value of the whole
1123 // expression is that of the RHS expression.
Mike Stump1eb44332009-09-09 15:08:12 +00001124
John McCall2de56d12010-08-25 11:45:40 +00001125 const Expr* Ex = (Op == BO_LAnd && branchTaken) ||
1126 (Op == BO_LOr && !branchTaken)
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001127 ? B->getRHS() : B->getLHS();
Mike Stump1eb44332009-09-09 15:08:12 +00001128
Ted Kremenek8e029342009-08-27 22:17:37 +00001129 return state->BindExpr(B, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +00001130 }
Mike Stump1eb44332009-09-09 15:08:12 +00001131
Ted Kremenek05a23782008-02-26 19:05:15 +00001132 case Stmt::ConditionalOperatorClass: { // ?:
Mike Stump1eb44332009-09-09 15:08:12 +00001133
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001134 const ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
Mike Stump1eb44332009-09-09 15:08:12 +00001135
Ted Kremenek05a23782008-02-26 19:05:15 +00001136 // For ?, if branchTaken == true then the value is either the LHS or
1137 // the condition itself. (GNU extension).
Mike Stump1eb44332009-09-09 15:08:12 +00001138
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001139 const Expr* Ex;
Mike Stump1eb44332009-09-09 15:08:12 +00001140
Ted Kremenek05a23782008-02-26 19:05:15 +00001141 if (branchTaken)
Mike Stump1eb44332009-09-09 15:08:12 +00001142 Ex = C->getLHS() ? C->getLHS() : C->getCond();
Ted Kremenek05a23782008-02-26 19:05:15 +00001143 else
1144 Ex = C->getRHS();
Mike Stump1eb44332009-09-09 15:08:12 +00001145
Ted Kremenek8e029342009-08-27 22:17:37 +00001146 return state->BindExpr(C, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +00001147 }
Mike Stump1eb44332009-09-09 15:08:12 +00001148
Ted Kremenek05a23782008-02-26 19:05:15 +00001149 case Stmt::ChooseExprClass: { // ?:
Mike Stump1eb44332009-09-09 15:08:12 +00001150
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001151 const ChooseExpr* C = cast<ChooseExpr>(Terminator);
Mike Stump1eb44332009-09-09 15:08:12 +00001152
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001153 const Expr* Ex = branchTaken ? C->getLHS() : C->getRHS();
Ted Kremenek8e029342009-08-27 22:17:37 +00001154 return state->BindExpr(C, UndefinedVal(Ex));
Ted Kremenek05a23782008-02-26 19:05:15 +00001155 }
1156 }
1157}
1158
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001159/// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1160/// to try to recover some path-sensitivity for casts of symbolic
1161/// integers that promote their values (which are currently not tracked well).
1162/// This function returns the SVal bound to Condition->IgnoreCasts if all the
1163// cast(s) did was sign-extend the original value.
1164static SVal RecoverCastedSymbol(GRStateManager& StateMgr, const GRState* state,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001165 const Stmt* Condition, ASTContext& Ctx) {
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001166
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001167 const Expr *Ex = dyn_cast<Expr>(Condition);
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001168 if (!Ex)
1169 return UnknownVal();
1170
1171 uint64_t bits = 0;
1172 bool bitsInit = false;
Mike Stump1eb44332009-09-09 15:08:12 +00001173
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001174 while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001175 QualType T = CE->getType();
1176
1177 if (!T->isIntegerType())
1178 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001179
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001180 uint64_t newBits = Ctx.getTypeSize(T);
1181 if (!bitsInit || newBits < bits) {
1182 bitsInit = true;
1183 bits = newBits;
1184 }
Mike Stump1eb44332009-09-09 15:08:12 +00001185
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001186 Ex = CE->getSubExpr();
1187 }
1188
1189 // We reached a non-cast. Is it a symbolic value?
1190 QualType T = Ex->getType();
1191
1192 if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits)
1193 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +00001194
Ted Kremenek13976632010-02-08 16:18:51 +00001195 return state->getSVal(Ex);
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001196}
1197
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001198void ExprEngine::ProcessBranch(const Stmt* Condition, const Stmt* Term,
1199 BranchNodeBuilder& builder) {
Mike Stump1eb44332009-09-09 15:08:12 +00001200
Ted Kremenekb2331832008-02-15 22:29:00 +00001201 // Check for NULL conditions; e.g. "for(;;)"
Mike Stump1eb44332009-09-09 15:08:12 +00001202 if (!Condition) {
Ted Kremenekb2331832008-02-15 22:29:00 +00001203 builder.markInfeasible(false);
Ted Kremenekb2331832008-02-15 22:29:00 +00001204 return;
1205 }
Mike Stump1eb44332009-09-09 15:08:12 +00001206
Ted Kremenek21028dd2009-03-11 03:54:24 +00001207 PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1208 Condition->getLocStart(),
1209 "Error evaluating branch");
Ted Kremenek0fb0bc42009-08-27 01:39:13 +00001210
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001211 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end();I!=E;++I) {
1212 void *tag = I->first;
1213 Checker *checker = I->second;
1214 checker->VisitBranchCondition(builder, *this, Condition, tag);
1215 }
1216
1217 // If the branch condition is undefined, return;
1218 if (!builder.isFeasible(true) && !builder.isFeasible(false))
1219 return;
1220
Mike Stump1eb44332009-09-09 15:08:12 +00001221 const GRState* PrevState = builder.getState();
Ted Kremenek13976632010-02-08 16:18:51 +00001222 SVal X = PrevState->getSVal(Condition);
Mike Stump1eb44332009-09-09 15:08:12 +00001223
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001224 if (X.isUnknown()) {
1225 // Give it a chance to recover from unknown.
1226 if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1227 if (Ex->getType()->isIntegerType()) {
1228 // Try to recover some path-sensitivity. Right now casts of symbolic
1229 // integers that promote their values are currently not tracked well.
1230 // If 'Condition' is such an expression, try and recover the
1231 // underlying value and use that instead.
1232 SVal recovered = RecoverCastedSymbol(getStateManager(),
1233 builder.getState(), Condition,
1234 getContext());
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001235
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001236 if (!recovered.isUnknown()) {
1237 X = recovered;
1238 }
Ted Kremenek6ae8a362009-03-13 16:32:54 +00001239 }
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001240 }
1241 // If the condition is still unknown, give up.
1242 if (X.isUnknown()) {
1243 builder.generateNode(MarkBranch(PrevState, Term, true), true);
1244 builder.generateNode(MarkBranch(PrevState, Term, false), false);
Ted Kremenekb38911f2008-01-30 23:03:39 +00001245 return;
Mike Stump1eb44332009-09-09 15:08:12 +00001246 }
Ted Kremenekb38911f2008-01-30 23:03:39 +00001247 }
Mike Stump1eb44332009-09-09 15:08:12 +00001248
Zhongxing Xu0835e4c2009-11-23 03:20:54 +00001249 DefinedSVal V = cast<DefinedSVal>(X);
1250
Ted Kremenek6a6719a2008-02-29 20:27:50 +00001251 // Process the true branch.
Ted Kremenek52003542009-07-20 18:44:36 +00001252 if (builder.isFeasible(true)) {
Ted Kremenek28f47b92010-12-01 22:16:56 +00001253 if (const GRState *state = PrevState->assume(V, true))
Ted Kremenek52003542009-07-20 18:44:36 +00001254 builder.generateNode(MarkBranch(state, Term, true), true);
1255 else
1256 builder.markInfeasible(true);
1257 }
Mike Stump1eb44332009-09-09 15:08:12 +00001258
1259 // Process the false branch.
Ted Kremenek52003542009-07-20 18:44:36 +00001260 if (builder.isFeasible(false)) {
Ted Kremenek28f47b92010-12-01 22:16:56 +00001261 if (const GRState *state = PrevState->assume(V, false))
Ted Kremenek52003542009-07-20 18:44:36 +00001262 builder.generateNode(MarkBranch(state, Term, false), false);
1263 else
1264 builder.markInfeasible(false);
1265 }
Ted Kremenek71c29bd2008-01-29 23:32:35 +00001266}
1267
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001268/// ProcessIndirectGoto - Called by CoreEngine. Used to generate successor
Ted Kremenek754607e2008-02-13 00:24:44 +00001269/// nodes by processing the 'effects' of a computed goto jump.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001270void ExprEngine::ProcessIndirectGoto(IndirectGotoNodeBuilder& builder) {
Ted Kremenek754607e2008-02-13 00:24:44 +00001271
Mike Stump1eb44332009-09-09 15:08:12 +00001272 const GRState *state = builder.getState();
Ted Kremenek13976632010-02-08 16:18:51 +00001273 SVal V = state->getSVal(builder.getTarget());
Mike Stump1eb44332009-09-09 15:08:12 +00001274
Ted Kremenek754607e2008-02-13 00:24:44 +00001275 // Three possibilities:
1276 //
1277 // (1) We know the computed label.
Ted Kremenek4a4e5242008-02-28 09:25:22 +00001278 // (2) The label is NULL (or some other constant), or Undefined.
Ted Kremenek754607e2008-02-13 00:24:44 +00001279 // (3) We have no clue about the label. Dispatch to all targets.
1280 //
Mike Stump1eb44332009-09-09 15:08:12 +00001281
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001282 typedef IndirectGotoNodeBuilder::iterator iterator;
Ted Kremenek754607e2008-02-13 00:24:44 +00001283
Zhongxing Xu1c96b242008-10-17 05:57:07 +00001284 if (isa<loc::GotoLabel>(V)) {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001285 const LabelStmt* L = cast<loc::GotoLabel>(V).getLabel();
Mike Stump1eb44332009-09-09 15:08:12 +00001286
Ted Kremenek754607e2008-02-13 00:24:44 +00001287 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) {
Ted Kremenek24f1a962008-02-13 17:27:37 +00001288 if (I.getLabel() == L) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001289 builder.generateNode(I, state);
Ted Kremenek754607e2008-02-13 00:24:44 +00001290 return;
1291 }
1292 }
Mike Stump1eb44332009-09-09 15:08:12 +00001293
Ted Kremenek754607e2008-02-13 00:24:44 +00001294 assert (false && "No block with label.");
1295 return;
1296 }
1297
Zhongxing Xu1c96b242008-10-17 05:57:07 +00001298 if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
Ted Kremenek754607e2008-02-13 00:24:44 +00001299 // Dispatch to the first target and mark it as a sink.
Zhongxing Xu2055eff2009-11-24 07:06:39 +00001300 //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1301 // FIXME: add checker visit.
1302 // UndefBranches.insert(N);
Ted Kremenek754607e2008-02-13 00:24:44 +00001303 return;
1304 }
Mike Stump1eb44332009-09-09 15:08:12 +00001305
Ted Kremenek754607e2008-02-13 00:24:44 +00001306 // This is really a catch-all. We don't support symbolics yet.
Ted Kremenekb3cfd582009-04-23 17:49:43 +00001307 // FIXME: Implement dispatch for symbolic pointers.
Mike Stump1eb44332009-09-09 15:08:12 +00001308
Ted Kremenek754607e2008-02-13 00:24:44 +00001309 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
Ted Kremeneka8538d92009-02-13 01:45:31 +00001310 builder.generateNode(I, state);
Ted Kremenek754607e2008-02-13 00:24:44 +00001311}
Ted Kremenekf233d482008-02-05 00:26:40 +00001312
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001313
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001314void ExprEngine::VisitGuardedExpr(const Expr* Ex, const Expr* L,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001315 const Expr* R,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001316 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001317
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001318 assert(Ex == currentStmt &&
Zhongxing Xubb141212009-12-16 11:27:52 +00001319 Pred->getLocationContext()->getCFG()->isBlkExpr(Ex));
Mike Stump1eb44332009-09-09 15:08:12 +00001320
Ted Kremeneka8538d92009-02-13 01:45:31 +00001321 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +00001322 SVal X = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00001323
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001324 assert (X.isUndef());
Mike Stump1eb44332009-09-09 15:08:12 +00001325
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001326 const Expr *SE = (Expr*) cast<UndefinedVal>(X).getData();
Mike Stump1eb44332009-09-09 15:08:12 +00001327 assert(SE);
Ted Kremenek13976632010-02-08 16:18:51 +00001328 X = state->getSVal(SE);
Mike Stump1eb44332009-09-09 15:08:12 +00001329
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001330 // Make sure that we invalidate the previous binding.
Ted Kremenek8e029342009-08-27 22:17:37 +00001331 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, X, true));
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001332}
1333
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001334/// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
Ted Kremenek73099bf2009-11-14 01:05:20 +00001335/// nodes when the control reaches the end of a function.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001336void ExprEngine::ProcessEndPath(EndPathNodeBuilder& builder) {
Ted Kremenek9c149532010-12-01 21:57:22 +00001337 getTF().evalEndPath(*this, builder);
Ted Kremenek73099bf2009-11-14 01:05:20 +00001338 StateMgr.EndPath(builder.getState());
Zhongxing Xu243fde92009-11-17 07:54:15 +00001339 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E;++I){
1340 void *tag = I->first;
1341 Checker *checker = I->second;
Ted Kremenek9c149532010-12-01 21:57:22 +00001342 checker->evalEndPath(builder, tag, *this);
Zhongxing Xu243fde92009-11-17 07:54:15 +00001343 }
Ted Kremenek73099bf2009-11-14 01:05:20 +00001344}
1345
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001346/// ProcessSwitch - Called by CoreEngine. Used to generate successor
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001347/// nodes by processing the 'effects' of a switch statement.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001348void ExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) {
1349 typedef SwitchNodeBuilder::iterator iterator;
Mike Stump1eb44332009-09-09 15:08:12 +00001350 const GRState* state = builder.getState();
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001351 const Expr* CondE = builder.getCondition();
Ted Kremenek13976632010-02-08 16:18:51 +00001352 SVal CondV_untested = state->getSVal(CondE);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001353
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001354 if (CondV_untested.isUndef()) {
Zhongxing Xu2055eff2009-11-24 07:06:39 +00001355 //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001356 // FIXME: add checker
Zhongxing Xu2055eff2009-11-24 07:06:39 +00001357 //UndefBranches.insert(N);
1358
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001359 return;
1360 }
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001361 DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested);
Ted Kremenek692416c2008-02-18 22:57:02 +00001362
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001363 const GRState *DefaultSt = state;
Ted Kremenek34feff62010-08-26 22:19:33 +00001364
1365 iterator I = builder.begin(), EI = builder.end();
1366 bool defaultIsFeasible = I == EI;
Mike Stump1eb44332009-09-09 15:08:12 +00001367
Ted Kremenek34feff62010-08-26 22:19:33 +00001368 for ( ; I != EI; ++I) {
Ted Kremenek41271172010-08-26 22:04:01 +00001369 const CaseStmt* Case = I.getCase();
Ted Kremenek72afb372009-01-17 01:54:16 +00001370
1371 // Evaluate the LHS of the case value.
1372 Expr::EvalResult V1;
Mike Stump1eb44332009-09-09 15:08:12 +00001373 bool b = Case->getLHS()->Evaluate(V1, getContext());
1374
Ted Kremenek72afb372009-01-17 01:54:16 +00001375 // Sanity checks. These go away in Release builds.
Mike Stump1eb44332009-09-09 15:08:12 +00001376 assert(b && V1.Val.isInt() && !V1.HasSideEffects
Ted Kremenek72afb372009-01-17 01:54:16 +00001377 && "Case condition must evaluate to an integer constant.");
Jeffrey Yasskinc6ed7292010-12-23 01:01:28 +00001378 (void)b; // silence unused variable warning
Mike Stump1eb44332009-09-09 15:08:12 +00001379 assert(V1.Val.getInt().getBitWidth() ==
Ted Kremenek72afb372009-01-17 01:54:16 +00001380 getContext().getTypeSize(CondE->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00001381
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001382 // Get the RHS of the case, if it exists.
Ted Kremenek72afb372009-01-17 01:54:16 +00001383 Expr::EvalResult V2;
Mike Stump1eb44332009-09-09 15:08:12 +00001384
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001385 if (const Expr* E = Case->getRHS()) {
Ted Kremenek72afb372009-01-17 01:54:16 +00001386 b = E->Evaluate(V2, getContext());
Mike Stump1eb44332009-09-09 15:08:12 +00001387 assert(b && V2.Val.isInt() && !V2.HasSideEffects
Ted Kremenek72afb372009-01-17 01:54:16 +00001388 && "Case condition must evaluate to an integer constant.");
Jeffrey Yasskinc6ed7292010-12-23 01:01:28 +00001389 (void)b; // silence unused variable warning
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001390 }
Ted Kremenek14a11402008-03-17 22:17:56 +00001391 else
1392 V2 = V1;
Mike Stump1eb44332009-09-09 15:08:12 +00001393
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001394 // FIXME: Eventually we should replace the logic below with a range
1395 // comparison, rather than concretize the values within the range.
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00001396 // This should be easy once we have "ranges" for NonLVals.
Mike Stump1eb44332009-09-09 15:08:12 +00001397
Ted Kremenek14a11402008-03-17 22:17:56 +00001398 do {
Mike Stump1eb44332009-09-09 15:08:12 +00001399 nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1.Val.getInt()));
Ted Kremenek9c149532010-12-01 21:57:22 +00001400 DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
Ted Kremenek48569f92010-01-08 18:54:04 +00001401 CondV, CaseVal);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001402
Mike Stump1eb44332009-09-09 15:08:12 +00001403 // Now "assume" that the case matches.
Ted Kremenek28f47b92010-12-01 22:16:56 +00001404 if (const GRState* stateNew = state->assume(Res, true)) {
Ted Kremeneka591bc02009-06-18 22:57:13 +00001405 builder.generateCaseStmtNode(I, stateNew);
Mike Stump1eb44332009-09-09 15:08:12 +00001406
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001407 // If CondV evaluates to a constant, then we know that this
1408 // is the *only* case that we can take, so stop evaluating the
1409 // others.
Zhongxing Xu1c96b242008-10-17 05:57:07 +00001410 if (isa<nonloc::ConcreteInt>(CondV))
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001411 return;
1412 }
Mike Stump1eb44332009-09-09 15:08:12 +00001413
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001414 // Now "assume" that the case doesn't match. Add this state
1415 // to the default state (if it is feasible).
Ted Kremenek48569f92010-01-08 18:54:04 +00001416 if (DefaultSt) {
Ted Kremenek28f47b92010-12-01 22:16:56 +00001417 if (const GRState *stateNew = DefaultSt->assume(Res, false)) {
Ted Kremenek48569f92010-01-08 18:54:04 +00001418 defaultIsFeasible = true;
1419 DefaultSt = stateNew;
1420 }
1421 else {
1422 defaultIsFeasible = false;
1423 DefaultSt = NULL;
1424 }
Ted Kremenek5014ab12008-04-23 05:03:18 +00001425 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001426
Ted Kremenek14a11402008-03-17 22:17:56 +00001427 // Concretize the next value in the range.
Ted Kremenek72afb372009-01-17 01:54:16 +00001428 if (V1.Val.getInt() == V2.Val.getInt())
Ted Kremenek14a11402008-03-17 22:17:56 +00001429 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001430
Ted Kremenek72afb372009-01-17 01:54:16 +00001431 ++V1.Val.getInt();
1432 assert (V1.Val.getInt() <= V2.Val.getInt());
Mike Stump1eb44332009-09-09 15:08:12 +00001433
Ted Kremenek14a11402008-03-17 22:17:56 +00001434 } while (true);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001435 }
Mike Stump1eb44332009-09-09 15:08:12 +00001436
Ted Kremenek4d3175c2010-09-09 00:40:40 +00001437 if (!defaultIsFeasible)
1438 return;
1439
1440 // If we have switch(enum value), the default branch is not
1441 // feasible if all of the enum constants not covered by 'case:' statements
1442 // are not feasible values for the switch condition.
1443 //
1444 // Note that this isn't as accurate as it could be. Even if there isn't
1445 // a case for a particular enum value as long as that enum value isn't
1446 // feasible then it shouldn't be considered for making 'default:' reachable.
1447 const SwitchStmt *SS = builder.getSwitch();
1448 const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1449 if (CondExpr->getType()->getAs<EnumType>()) {
1450 if (SS->isAllEnumCasesCovered())
1451 return;
1452 }
1453
1454 builder.generateDefaultCaseNode(DefaultSt);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001455}
1456
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001457void ExprEngine::ProcessCallEnter(CallEnterNodeBuilder &B) {
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001458 const GRState *state = B.getState()->EnterStackFrame(B.getCalleeContext());
Ted Kremenekd048c6e2010-12-20 21:19:09 +00001459 B.generateNode(state);
Douglas Gregor102acd52010-02-25 19:01:53 +00001460}
1461
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001462void ExprEngine::ProcessCallExit(CallExitNodeBuilder &B) {
Douglas Gregor102acd52010-02-25 19:01:53 +00001463 const GRState *state = B.getState();
1464 const ExplodedNode *Pred = B.getPredecessor();
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001465 const StackFrameContext *calleeCtx =
Douglas Gregor102acd52010-02-25 19:01:53 +00001466 cast<StackFrameContext>(Pred->getLocationContext());
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001467 const Stmt *CE = calleeCtx->getCallSite();
Douglas Gregor102acd52010-02-25 19:01:53 +00001468
Zhongxing Xu6190ec22010-02-26 15:43:34 +00001469 // If the callee returns an expression, bind its value to CallExpr.
1470 const Stmt *ReturnedExpr = state->get<ReturnExpr>();
1471 if (ReturnedExpr) {
1472 SVal RetVal = state->getSVal(ReturnedExpr);
1473 state = state->BindExpr(CE, RetVal);
Zhongxing Xubd2b2082010-03-23 08:09:29 +00001474 // Clear the return expr GDM.
Zhongxing Xu0541d102010-03-25 01:39:39 +00001475 state = state->remove<ReturnExpr>();
Zhongxing Xu6190ec22010-02-26 15:43:34 +00001476 }
1477
Zhongxing Xu8e18c1b2010-03-23 09:13:17 +00001478 // Bind the constructed object value to CXXConstructExpr.
1479 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
Zhongxing Xu9dc84c92010-11-16 07:52:17 +00001480 const CXXThisRegion *ThisR =
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001481 getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx);
Zhongxing Xud7064342010-11-24 13:08:51 +00001482
Zhongxing Xu8e18c1b2010-03-23 09:13:17 +00001483 SVal ThisV = state->getSVal(ThisR);
Zhongxing Xu05e53912010-12-22 07:20:27 +00001484 // Always bind the region to the CXXConstructExpr.
1485 state = state->BindExpr(CCE, ThisV);
Zhongxing Xu8e18c1b2010-03-23 09:13:17 +00001486 }
1487
Ted Kremenekd048c6e2010-12-20 21:19:09 +00001488 B.generateNode(state);
Douglas Gregor102acd52010-02-25 19:01:53 +00001489}
1490
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001491//===----------------------------------------------------------------------===//
1492// Transfer functions: logical operations ('&&', '||').
1493//===----------------------------------------------------------------------===//
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001494
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001495void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode* Pred,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001496 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001497
John McCall2de56d12010-08-25 11:45:40 +00001498 assert(B->getOpcode() == BO_LAnd ||
1499 B->getOpcode() == BO_LOr);
Mike Stump1eb44332009-09-09 15:08:12 +00001500
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001501 assert(B==currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(B));
Mike Stump1eb44332009-09-09 15:08:12 +00001502
Ted Kremeneka8538d92009-02-13 01:45:31 +00001503 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +00001504 SVal X = state->getSVal(B);
Ted Kremenek3ff12592009-06-19 17:10:32 +00001505 assert(X.isUndef());
Mike Stump1eb44332009-09-09 15:08:12 +00001506
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001507 const Expr *Ex = (const Expr*) cast<UndefinedVal>(X).getData();
Ted Kremenek3ff12592009-06-19 17:10:32 +00001508 assert(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00001509
Ted Kremenek05a23782008-02-26 19:05:15 +00001510 if (Ex == B->getRHS()) {
Ted Kremenek13976632010-02-08 16:18:51 +00001511 X = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00001512
Ted Kremenek4a4e5242008-02-28 09:25:22 +00001513 // Handle undefined values.
Ted Kremenek4a4e5242008-02-28 09:25:22 +00001514 if (X.isUndef()) {
Ted Kremenek8e029342009-08-27 22:17:37 +00001515 MakeNode(Dst, B, Pred, state->BindExpr(B, X));
Ted Kremenek58b33212008-02-26 19:40:44 +00001516 return;
1517 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001518
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001519 DefinedOrUnknownSVal XD = cast<DefinedOrUnknownSVal>(X);
Mike Stump1eb44332009-09-09 15:08:12 +00001520
Ted Kremenek05a23782008-02-26 19:05:15 +00001521 // We took the RHS. Because the value of the '&&' or '||' expression must
1522 // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
1523 // or 1. Alternatively, we could take a lazy approach, and calculate this
1524 // value later when necessary. We don't have the machinery in place for
1525 // this right now, and since most logical expressions are used for branches,
Mike Stump1eb44332009-09-09 15:08:12 +00001526 // the payoff is not likely to be large. Instead, we do eager evaluation.
Ted Kremenek28f47b92010-12-01 22:16:56 +00001527 if (const GRState *newState = state->assume(XD, true))
Mike Stump1eb44332009-09-09 15:08:12 +00001528 MakeNode(Dst, B, Pred,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001529 newState->BindExpr(B, svalBuilder.makeIntVal(1U, B->getType())));
Mike Stump1eb44332009-09-09 15:08:12 +00001530
Ted Kremenek28f47b92010-12-01 22:16:56 +00001531 if (const GRState *newState = state->assume(XD, false))
Mike Stump1eb44332009-09-09 15:08:12 +00001532 MakeNode(Dst, B, Pred,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001533 newState->BindExpr(B, svalBuilder.makeIntVal(0U, B->getType())));
Ted Kremenekf233d482008-02-05 00:26:40 +00001534 }
1535 else {
Ted Kremenek05a23782008-02-26 19:05:15 +00001536 // We took the LHS expression. Depending on whether we are '&&' or
1537 // '||' we know what the value of the expression is via properties of
1538 // the short-circuiting.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001539 X = svalBuilder.makeIntVal(B->getOpcode() == BO_LAnd ? 0U : 1U,
Zhongxing Xud91ee272009-06-23 09:02:15 +00001540 B->getType());
Ted Kremenek8e029342009-08-27 22:17:37 +00001541 MakeNode(Dst, B, Pred, state->BindExpr(B, X));
Ted Kremenekf233d482008-02-05 00:26:40 +00001542 }
Ted Kremenekf233d482008-02-05 00:26:40 +00001543}
Mike Stump1eb44332009-09-09 15:08:12 +00001544
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001545//===----------------------------------------------------------------------===//
Ted Kremenekec96a2d2008-04-16 18:39:06 +00001546// Transfer functions: Loads and stores.
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001547//===----------------------------------------------------------------------===//
Ted Kremenekd27f8162008-01-15 23:55:06 +00001548
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001549void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001550 ExplodedNodeSet &Dst) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001551
Ted Kremenek66078612009-11-25 22:23:25 +00001552 ExplodedNodeSet Tmp;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001553
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001554 CanQualType T = getContext().getCanonicalType(BE->getType());
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001555 SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T,
Ted Kremenek0a8112a2009-11-25 23:53:07 +00001556 Pred->getLocationContext());
1557
Ted Kremenek66078612009-11-25 22:23:25 +00001558 MakeNode(Tmp, BE, Pred, GetState(Pred)->BindExpr(BE, V),
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001559 ProgramPoint::PostLValueKind);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001560
Ted Kremenek66078612009-11-25 22:23:25 +00001561 // Post-visit the BlockExpr.
Jordy Rose72905cf2010-08-04 07:10:57 +00001562 CheckerVisit(BE, Dst, Tmp, PostVisitStmtCallback);
Ted Kremenekc95ad9f2009-11-25 01:33:13 +00001563}
1564
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001565void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
1566 ExplodedNode *Pred,
1567 ExplodedNodeSet &Dst) {
Ted Kremenek5b9bd212009-09-11 22:07:28 +00001568 const GRState *state = GetState(Pred);
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001569
1570 if (const VarDecl* VD = dyn_cast<VarDecl>(D)) {
Ted Kremenek892697d2010-12-16 07:46:53 +00001571 assert(Ex->isLValue());
Ted Kremenekd17da2b2009-08-21 22:28:32 +00001572 SVal V = state->getLValue(VD, Pred->getLocationContext());
Zhongxing Xua7581732008-10-17 02:20:14 +00001573
Ted Kremenek892697d2010-12-16 07:46:53 +00001574 // For references, the 'lvalue' is the pointer address stored in the
1575 // reference region.
1576 if (VD->getType()->isReferenceType()) {
1577 if (const MemRegion *R = V.getAsRegion())
1578 V = state->getSVal(R);
1579 else
1580 V = UnknownVal();
Ted Kremenek852274d2009-12-16 03:18:58 +00001581 }
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001582
Ted Kremenek892697d2010-12-16 07:46:53 +00001583 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V),
1584 ProgramPoint::PostLValueKind);
Ted Kremenek852274d2009-12-16 03:18:58 +00001585 return;
Ted Kremenek892697d2010-12-16 07:46:53 +00001586 }
1587 if (const EnumConstantDecl* ED = dyn_cast<EnumConstantDecl>(D)) {
1588 assert(!Ex->isLValue());
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001589 SVal V = svalBuilder.makeIntVal(ED->getInitVal());
Ted Kremenek8e029342009-08-27 22:17:37 +00001590 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V));
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001591 return;
Ted Kremenek892697d2010-12-16 07:46:53 +00001592 }
1593 if (const FunctionDecl* FD = dyn_cast<FunctionDecl>(D)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001594 SVal V = svalBuilder.getFunctionPointer(FD);
Ted Kremenek8e029342009-08-27 22:17:37 +00001595 MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, V),
Ted Kremenek7090d542009-05-07 18:27:16 +00001596 ProgramPoint::PostLValueKind);
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001597 return;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001598 }
Zhongxing Xu6d69b5d2008-10-16 06:09:51 +00001599 assert (false &&
1600 "ValueDecl support for this ValueDecl not implemented.");
Ted Kremenek3271f8d2008-02-07 04:16:04 +00001601}
1602
Ted Kremenek540cbe22008-04-22 04:56:29 +00001603/// VisitArraySubscriptExpr - Transfer function for array accesses
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001604void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr* A,
1605 ExplodedNode* Pred,
1606 ExplodedNodeSet& Dst){
Mike Stump1eb44332009-09-09 15:08:12 +00001607
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001608 const Expr* Base = A->getBase()->IgnoreParens();
1609 const Expr* Idx = A->getIdx()->IgnoreParens();
Ted Kremenek892697d2010-12-16 07:46:53 +00001610
1611 // Evaluate the base.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001612 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00001613 Visit(Base, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00001614
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001615 for (ExplodedNodeSet::iterator I1=Tmp.begin(), E1=Tmp.end(); I1!=E1; ++I1) {
1616 ExplodedNodeSet Tmp2;
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001617 Visit(Idx, *I1, Tmp2); // Evaluate the index.
Zhongxing Xud6944852009-11-11 13:42:54 +00001618 ExplodedNodeSet Tmp3;
Jordy Rose72905cf2010-08-04 07:10:57 +00001619 CheckerVisit(A, Tmp3, Tmp2, PreVisitStmtCallback);
Zhongxing Xud6944852009-11-11 13:42:54 +00001620
1621 for (ExplodedNodeSet::iterator I2=Tmp3.begin(),E2=Tmp3.end();I2!=E2; ++I2) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001622 const GRState* state = GetState(*I2);
Ted Kremenek13976632010-02-08 16:18:51 +00001623 SVal V = state->getLValue(A->getType(), state->getSVal(Idx),
1624 state->getSVal(Base));
Ted Kremenek892697d2010-12-16 07:46:53 +00001625 assert(A->isLValue());
1626 MakeNode(Dst, A, *I2, state->BindExpr(A, V), ProgramPoint::PostLValueKind);
Ted Kremenek4d0348b2008-04-29 23:24:44 +00001627 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001628 }
Ted Kremenek540cbe22008-04-22 04:56:29 +00001629}
1630
Ted Kremenek469ecbd2008-04-21 23:43:38 +00001631/// VisitMemberExpr - Transfer function for member expressions.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001632void ExprEngine::VisitMemberExpr(const MemberExpr* M, ExplodedNode* Pred,
1633 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00001634
Ted Kremenek892697d2010-12-16 07:46:53 +00001635 Expr *baseExpr = M->getBase()->IgnoreParens();
1636 ExplodedNodeSet dstBase;
1637 Visit(baseExpr, Pred, dstBase);
Mike Stump1eb44332009-09-09 15:08:12 +00001638
Ted Kremenek892697d2010-12-16 07:46:53 +00001639 FieldDecl *field = dyn_cast<FieldDecl>(M->getMemberDecl());
1640 if (!field) // FIXME: skipping member expressions for non-fields
Douglas Gregor86f19402008-12-20 23:49:58 +00001641 return;
1642
Ted Kremenek892697d2010-12-16 07:46:53 +00001643 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end();
1644 I != E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00001645 const GRState* state = GetState(*I);
Ted Kremenek892697d2010-12-16 07:46:53 +00001646 SVal baseExprVal = state->getSVal(baseExpr);
1647 if (isa<nonloc::LazyCompoundVal>(baseExprVal) ||
1648 isa<nonloc::CompoundVal>(baseExprVal)) {
1649 MakeNode(Dst, M, *I, state->BindExpr(M, UnknownVal()));
1650 continue;
1651 }
1652
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001653 // FIXME: Should we insert some assumption logic in here to determine
1654 // if "Base" is a valid piece of memory? Before we put this assumption
Douglas Gregor86f19402008-12-20 23:49:58 +00001655 // later when using FieldOffset lvals (which we no longer have).
Ted Kremenekd9bc33e2008-10-17 00:51:01 +00001656
Ted Kremenek892697d2010-12-16 07:46:53 +00001657 // For all other cases, compute an lvalue.
1658 SVal L = state->getLValue(field, baseExprVal);
1659 if (M->isLValue())
Zhongxing Xu662174ca2009-10-30 07:19:39 +00001660 MakeNode(Dst, M, *I, state->BindExpr(M, L), ProgramPoint::PostLValueKind);
1661 else
Ted Kremenek9c149532010-12-01 21:57:22 +00001662 evalLoad(Dst, M, *I, state, L);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001663 }
Ted Kremenek469ecbd2008-04-21 23:43:38 +00001664}
1665
Ted Kremenek9c149532010-12-01 21:57:22 +00001666/// evalBind - Handle the semantics of binding a value to a specific location.
1667/// This method is used by evalStore and (soon) VisitDeclStmt, and others.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001668void ExprEngine::evalBind(ExplodedNodeSet& Dst, const Stmt* StoreE,
Ted Kremenek79d73042010-09-02 00:56:20 +00001669 ExplodedNode* Pred, const GRState* state,
1670 SVal location, SVal Val, bool atDeclInit) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001671
1672
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001673 // Do a previsit of the bind.
1674 ExplodedNodeSet CheckedSet, Src;
1675 Src.Add(Pred);
Ted Kremenek79d73042010-09-02 00:56:20 +00001676 CheckerVisitBind(StoreE, CheckedSet, Src, location, Val, true);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001677
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001678 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1679 I!=E; ++I) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001680
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001681 if (Pred != *I)
1682 state = GetState(*I);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001683
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001684 const GRState* newState = 0;
Ted Kremeneka8538d92009-02-13 01:45:31 +00001685
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001686 if (atDeclInit) {
1687 const VarRegion *VR =
1688 cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion());
Mike Stump1eb44332009-09-09 15:08:12 +00001689
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001690 newState = state->bindDecl(VR, Val);
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001691 }
1692 else {
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001693 if (location.isUnknown()) {
1694 // We know that the new state will be the same as the old state since
1695 // the location of the binding is "unknown". Consequently, there
1696 // is no reason to just create a new node.
1697 newState = state;
1698 }
1699 else {
1700 // We are binding to a value other than 'unknown'. Perform the binding
1701 // using the StoreManager.
1702 newState = state->bindLoc(cast<Loc>(location), Val);
1703 }
Ted Kremenekf6f56d42009-11-04 00:09:15 +00001704 }
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001705
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001706 // The next thing to do is check if the TransferFuncs object wants to
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001707 // update the state based on the new binding. If the GRTransferFunc object
1708 // doesn't do anything, just auto-propagate the current state.
Ted Kremenek79d73042010-09-02 00:56:20 +00001709
1710 // NOTE: We use 'AssignE' for the location of the PostStore if 'AssignE'
1711 // is non-NULL. Checkers typically care about
1712
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001713 StmtNodeBuilderRef BuilderRef(Dst, *Builder, *this, *I, newState, StoreE,
Ted Kremenek96ebad62010-09-09 07:13:00 +00001714 true);
Ted Kremenekb107c4b2009-11-04 04:24:16 +00001715
Ted Kremenek9c149532010-12-01 21:57:22 +00001716 getTF().evalBind(BuilderRef, location, Val);
Ted Kremenek41573eb2009-02-14 01:43:44 +00001717 }
Ted Kremeneka8538d92009-02-13 01:45:31 +00001718}
1719
Ted Kremenek9c149532010-12-01 21:57:22 +00001720/// evalStore - Handle the semantics of a store via an assignment.
Ted Kremeneka8538d92009-02-13 01:45:31 +00001721/// @param Dst The node set to store generated state nodes
Zhongxing Xue8a4d7d2010-09-02 01:56:39 +00001722/// @param AssignE The assignment expression if the store happens in an
1723/// assignment.
1724/// @param LocatioinE The location expression that is stored to.
Ted Kremeneka8538d92009-02-13 01:45:31 +00001725/// @param state The current simulation state
1726/// @param location The location to store the value
1727/// @param Val The value to be stored
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001728void ExprEngine::evalStore(ExplodedNodeSet& Dst, const Expr *AssignE,
Ted Kremenek79d73042010-09-02 00:56:20 +00001729 const Expr* LocationE,
Ted Kremenek50ecd152009-11-05 00:42:23 +00001730 ExplodedNode* Pred,
Ted Kremenek1670e402009-04-11 00:11:10 +00001731 const GRState* state, SVal location, SVal Val,
1732 const void *tag) {
Mike Stump1eb44332009-09-09 15:08:12 +00001733
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001734 assert(Builder && "StmtNodeBuilder must be defined.");
Mike Stump1eb44332009-09-09 15:08:12 +00001735
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001736 // Evaluate the location (checks for bad dereferences).
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001737 ExplodedNodeSet Tmp;
Ted Kremenek9c149532010-12-01 21:57:22 +00001738 evalLocation(Tmp, LocationE, Pred, state, location, tag, false);
Mike Stump1eb44332009-09-09 15:08:12 +00001739
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001740 if (Tmp.empty())
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001741 return;
Ted Kremenekb0533962008-04-18 20:35:30 +00001742
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001743 assert(!location.isUndef());
Ted Kremeneka8538d92009-02-13 01:45:31 +00001744
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001745 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind,
1746 ProgramPoint::PostStoreKind);
1747 SaveAndRestore<const void*> OldTag(Builder->Tag, tag);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001748
Ted Kremenek79d73042010-09-02 00:56:20 +00001749 // Proceed with the store. We use AssignE as the anchor for the PostStore
1750 // ProgramPoint if it is non-NULL, and LocationE otherwise.
1751 const Expr *StoreE = AssignE ? AssignE : LocationE;
1752
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001753 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
Ted Kremenek9c149532010-12-01 21:57:22 +00001754 evalBind(Dst, StoreE, *NI, GetState(*NI), location, Val);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001755}
1756
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001757void ExprEngine::evalLoad(ExplodedNodeSet& Dst, const Expr *Ex,
Zhongxing Xu3992a502010-07-20 02:41:28 +00001758 ExplodedNode* Pred,
Ted Kremenek1670e402009-04-11 00:11:10 +00001759 const GRState* state, SVal location,
Zhongxing Xu652be342009-11-16 04:49:44 +00001760 const void *tag, QualType LoadTy) {
Zhanyong Wancca8ab12010-11-24 01:47:11 +00001761 assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001762
Ted Kremenek852274d2009-12-16 03:18:58 +00001763 // Are we loading from a region? This actually results in two loads; one
1764 // to fetch the address of the referenced value and one to fetch the
1765 // referenced value.
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001766 if (const TypedRegion *TR =
Ted Kremenek852274d2009-12-16 03:18:58 +00001767 dyn_cast_or_null<TypedRegion>(location.getAsRegion())) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001768
Zhongxing Xu018220c2010-08-11 06:10:55 +00001769 QualType ValTy = TR->getValueType();
Ted Kremenek852274d2009-12-16 03:18:58 +00001770 if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001771 static int loadReferenceTag = 0;
Ted Kremenek852274d2009-12-16 03:18:58 +00001772 ExplodedNodeSet Tmp;
Ted Kremenek9c149532010-12-01 21:57:22 +00001773 evalLoadCommon(Tmp, Ex, Pred, state, location, &loadReferenceTag,
Ted Kremenek852274d2009-12-16 03:18:58 +00001774 getContext().getPointerType(RT->getPointeeType()));
1775
1776 // Perform the load from the referenced value.
1777 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
1778 state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00001779 location = state->getSVal(Ex);
Ted Kremenek9c149532010-12-01 21:57:22 +00001780 evalLoadCommon(Dst, Ex, *I, state, location, tag, LoadTy);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001781 }
Ted Kremenek852274d2009-12-16 03:18:58 +00001782 return;
1783 }
1784 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001785
Ted Kremenek9c149532010-12-01 21:57:22 +00001786 evalLoadCommon(Dst, Ex, Pred, state, location, tag, LoadTy);
Ted Kremenek852274d2009-12-16 03:18:58 +00001787}
1788
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001789void ExprEngine::evalLoadCommon(ExplodedNodeSet& Dst, const Expr *Ex,
Ted Kremenek852274d2009-12-16 03:18:58 +00001790 ExplodedNode* Pred,
1791 const GRState* state, SVal location,
1792 const void *tag, QualType LoadTy) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001793
Mike Stump1eb44332009-09-09 15:08:12 +00001794 // Evaluate the location (checks for bad dereferences).
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001795 ExplodedNodeSet Tmp;
Ted Kremenek9c149532010-12-01 21:57:22 +00001796 evalLocation(Tmp, Ex, Pred, state, location, tag, true);
Mike Stump1eb44332009-09-09 15:08:12 +00001797
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001798 if (Tmp.empty())
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001799 return;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001800
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001801 assert(!location.isUndef());
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001802
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001803 SaveAndRestore<ProgramPoint::Kind> OldSPointKind(Builder->PointKind);
1804 SaveAndRestore<const void*> OldTag(Builder->Tag);
Mike Stump1eb44332009-09-09 15:08:12 +00001805
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001806 // Proceed with the load.
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001807 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1808 state = GetState(*NI);
Ted Kremenek96ebad62010-09-09 07:13:00 +00001809
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001810 if (location.isUnknown()) {
1811 // This is important. We must nuke the old binding.
1812 MakeNode(Dst, Ex, *NI, state->BindExpr(Ex, UnknownVal()),
1813 ProgramPoint::PostLoadKind, tag);
1814 }
1815 else {
Ted Kremenek96ebad62010-09-09 07:13:00 +00001816 if (LoadTy.isNull())
1817 LoadTy = Ex->getType();
1818 SVal V = state->getSVal(cast<Loc>(location), LoadTy);
1819 MakeNode(Dst, Ex, *NI, state->bindExprAndLocation(Ex, location, V),
1820 ProgramPoint::PostLoadKind, tag);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001821 }
Zhongxing Xud5b499d2008-11-28 08:34:30 +00001822 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00001823}
1824
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001825void ExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *S,
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001826 ExplodedNode* Pred,
1827 const GRState* state, SVal location,
1828 const void *tag, bool isLoad) {
Zhongxing Xu00b1ad22009-11-20 03:50:46 +00001829 // Early checks for performance reason.
1830 if (location.isUnknown() || Checkers.empty()) {
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001831 Dst.Add(Pred);
1832 return;
Ted Kremenek0296c222009-11-02 23:19:29 +00001833 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001834
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001835 ExplodedNodeSet Src, Tmp;
1836 Src.Add(Pred);
1837 ExplodedNodeSet *PrevSet = &Src;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001838
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001839 for (CheckersOrdered::iterator I=Checkers.begin(),E=Checkers.end(); I!=E; ++I)
1840 {
Ted Kremenek17f4da82009-12-09 02:45:41 +00001841 ExplodedNodeSet *CurrSet = 0;
1842 if (I+1 == E)
1843 CurrSet = &Dst;
1844 else {
1845 CurrSet = (PrevSet == &Tmp) ? &Src : &Tmp;
1846 CurrSet->clear();
1847 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001848
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001849 void *tag = I->first;
1850 Checker *checker = I->second;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001851
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001852 for (ExplodedNodeSet::iterator NI = PrevSet->begin(), NE = PrevSet->end();
Ted Kremenek19d67b52009-11-23 22:22:01 +00001853 NI != NE; ++NI) {
1854 // Use the 'state' argument only when the predecessor node is the
1855 // same as Pred. This allows us to catch updates to the state.
Ted Kremenek342e9072010-12-20 21:22:47 +00001856 checker->GR_visitLocation(*CurrSet, *Builder, *this, S, *NI,
Ted Kremenek19d67b52009-11-23 22:22:01 +00001857 *NI == Pred ? state : GetState(*NI),
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001858 location, tag, isLoad);
Ted Kremenek19d67b52009-11-23 22:22:01 +00001859 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001860
Ted Kremenekb4b817d2009-11-11 03:26:34 +00001861 // Update which NodeSet is the current one.
1862 PrevSet = CurrSet;
1863 }
Ted Kremenekec96a2d2008-04-16 18:39:06 +00001864}
1865
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001866bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE,
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001867 ExplodedNode *Pred) {
1868 const GRState *state = GetState(Pred);
1869 const Expr *Callee = CE->getCallee();
1870 SVal L = state->getSVal(Callee);
1871
1872 const FunctionDecl *FD = L.getAsFunctionDecl();
1873 if (!FD)
1874 return false;
1875
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001876 // Check if the function definition is in the same translation unit.
1877 if (FD->hasBody(FD)) {
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001878 const StackFrameContext *stackFrame =
1879 AMgr.getStackFrame(AMgr.getAnalysisContext(FD),
1880 Pred->getLocationContext(),
Ted Kremenek892697d2010-12-16 07:46:53 +00001881 CE, Builder->getBlock(), Builder->getIndex());
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001882 // Now we have the definition of the callee, create a CallEnter node.
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001883 CallEnter Loc(CE, stackFrame, Pred->getLocationContext());
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001884
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001885 ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001886 Dst.Add(N);
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001887 return true;
1888 }
1889
1890 // Check if we can find the function definition in other translation units.
1891 if (AMgr.hasIndexer()) {
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001892 AnalysisContext *C = AMgr.getAnalysisContextInAnotherTU(FD);
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001893 if (C == 0)
1894 return false;
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001895 const StackFrameContext *stackFrame =
1896 AMgr.getStackFrame(C, Pred->getLocationContext(),
Ted Kremenek892697d2010-12-16 07:46:53 +00001897 CE, Builder->getBlock(), Builder->getIndex());
Zhongxing Xu19b78d92010-11-24 08:53:20 +00001898 CallEnter Loc(CE, stackFrame, Pred->getLocationContext());
Zhongxing Xuc6238d22010-07-19 01:31:21 +00001899 ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
1900 Dst.Add(N);
1901 return true;
1902 }
1903
1904 return false;
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001905}
1906
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001907void ExprEngine::VisitCall(const CallExpr* CE, ExplodedNode* Pred,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001908 CallExpr::const_arg_iterator AI,
1909 CallExpr::const_arg_iterator AE,
Ted Kremenek892697d2010-12-16 07:46:53 +00001910 ExplodedNodeSet& Dst) {
Ted Kremenek3cead902009-12-17 20:06:29 +00001911
Douglas Gregor9d293df2008-10-28 00:22:11 +00001912 // Determine the type of function we're calling (if available).
Douglas Gregor72564e72009-02-26 23:50:07 +00001913 const FunctionProtoType *Proto = NULL;
Douglas Gregor9d293df2008-10-28 00:22:11 +00001914 QualType FnType = CE->getCallee()->IgnoreParens()->getType();
Ted Kremenek6217b802009-07-29 21:53:49 +00001915 if (const PointerType *FnTypePtr = FnType->getAs<PointerType>())
John McCall183700f2009-09-21 23:43:11 +00001916 Proto = FnTypePtr->getPointeeType()->getAs<FunctionProtoType>();
Douglas Gregor9d293df2008-10-28 00:22:11 +00001917
Ted Kremenekc69c4382010-09-23 05:14:51 +00001918 // Evaluate the arguments.
Ted Kremenek3cead902009-12-17 20:06:29 +00001919 ExplodedNodeSet ArgsEvaluated;
Ted Kremenek9c149532010-12-01 21:57:22 +00001920 evalArguments(CE->arg_begin(), CE->arg_end(), Proto, Pred, ArgsEvaluated);
Ted Kremenekde434242008-02-19 01:44:53 +00001921
Ted Kremenek7f14e6f2009-12-17 20:10:17 +00001922 // Now process the call itself.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001923 ExplodedNodeSet DstTmp;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001924 const Expr* Callee = CE->getCallee()->IgnoreParens();
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001925
Ted Kremenek3cead902009-12-17 20:06:29 +00001926 for (ExplodedNodeSet::iterator NI=ArgsEvaluated.begin(),
Ted Kremenek7f14e6f2009-12-17 20:10:17 +00001927 NE=ArgsEvaluated.end(); NI != NE; ++NI) {
1928 // Evaluate the callee.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001929 ExplodedNodeSet DstTmp2;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001930 Visit(Callee, *NI, DstTmp2);
Ted Kremenek5a5d98b2009-07-22 21:43:51 +00001931 // Perform the previsit of the CallExpr, storing the results in DstTmp.
Jordy Rose72905cf2010-08-04 07:10:57 +00001932 CheckerVisit(CE, DstTmp, DstTmp2, PreVisitStmtCallback);
Ted Kremenek5a5d98b2009-07-22 21:43:51 +00001933 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001934
Ted Kremenek3cead902009-12-17 20:06:29 +00001935 // Finally, evaluate the function call. We try each of the checkers
1936 // to see if the can evaluate the function call.
Ted Kremenek17f4da82009-12-09 02:45:41 +00001937 ExplodedNodeSet DstTmp3;
Ted Kremenek53287512009-12-18 20:13:39 +00001938
Mike Stump1eb44332009-09-09 15:08:12 +00001939 for (ExplodedNodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end();
Zhongxing Xu248072a2009-09-05 05:00:57 +00001940 DI != DE; ++DI) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001941
Ted Kremeneka8538d92009-02-13 01:45:31 +00001942 const GRState* state = GetState(*DI);
Ted Kremenek13976632010-02-08 16:18:51 +00001943 SVal L = state->getSVal(Callee);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001944
Ted Kremeneka1354a52008-03-03 16:47:31 +00001945 // FIXME: Add support for symbolic function calls (calls involving
1946 // function pointer values that are symbolic).
Ted Kremenek4bf38da2008-03-05 21:15:02 +00001947 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
Ted Kremenek17f4da82009-12-09 02:45:41 +00001948 ExplodedNodeSet DstChecker;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001949
Zhongxing Xu935ef902009-12-07 09:17:35 +00001950 // If the callee is processed by a checker, skip the rest logic.
1951 if (CheckerEvalCall(CE, DstChecker, *DI))
Zhongxing Xu9f68ea22009-12-09 05:48:53 +00001952 DstTmp3.insert(DstChecker);
Zhongxing Xu1c625f22010-05-06 03:38:27 +00001953 else if (AMgr.shouldInlineCall() && InlineCall(Dst, CE, *DI)) {
1954 // Callee is inlined. We shouldn't do post call checking.
1955 return;
1956 }
Zhongxing Xu935ef902009-12-07 09:17:35 +00001957 else {
Ted Kremenek17f4da82009-12-09 02:45:41 +00001958 for (ExplodedNodeSet::iterator DI_Checker = DstChecker.begin(),
Ted Kremenek3cead902009-12-17 20:06:29 +00001959 DE_Checker = DstChecker.end();
1960 DI_Checker != DE_Checker; ++DI_Checker) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001961
Ted Kremenek3cead902009-12-17 20:06:29 +00001962 // Dispatch to the plug-in transfer function.
Ted Kremenek9c149532010-12-01 21:57:22 +00001963 unsigned oldSize = DstTmp3.size();
Ted Kremenek17f4da82009-12-09 02:45:41 +00001964 SaveOr OldHasGen(Builder->HasGeneratedNode);
1965 Pred = *DI_Checker;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001966
Ted Kremenek17f4da82009-12-09 02:45:41 +00001967 // Dispatch to transfer function logic to handle the call itself.
1968 // FIXME: Allow us to chain together transfer functions.
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001969 assert(Builder && "StmtNodeBuilder must be defined.");
Ted Kremenek9c149532010-12-01 21:57:22 +00001970 getTF().evalCall(DstTmp3, *this, *Builder, CE, L, Pred);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001971
Ted Kremenek17f4da82009-12-09 02:45:41 +00001972 // Handle the case where no nodes where generated. Auto-generate that
1973 // contains the updated state if we aren't generating sinks.
Ted Kremenek9c149532010-12-01 21:57:22 +00001974 if (!Builder->BuildSinks && DstTmp3.size() == oldSize &&
Ted Kremenek17f4da82009-12-09 02:45:41 +00001975 !Builder->HasGeneratedNode)
1976 MakeNode(DstTmp3, CE, Pred, state);
1977 }
Zhongxing Xu935ef902009-12-07 09:17:35 +00001978 }
Ted Kremenekde434242008-02-19 01:44:53 +00001979 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00001980
Ted Kremenek3cead902009-12-17 20:06:29 +00001981 // Finally, perform the post-condition check of the CallExpr and store
1982 // the created nodes in 'Dst'.
Ted Kremenek892697d2010-12-16 07:46:53 +00001983 CheckerVisit(CE, Dst, DstTmp3, PostVisitStmtCallback);
Ted Kremenekde434242008-02-19 01:44:53 +00001984}
1985
Ted Kremeneke695e1c2008-04-15 23:06:53 +00001986//===----------------------------------------------------------------------===//
Ted Kremenek97ed4f62008-10-17 00:03:18 +00001987// Transfer function: Objective-C ivar references.
1988//===----------------------------------------------------------------------===//
1989
Ted Kremenekf5cae632009-02-28 20:50:43 +00001990static std::pair<const void*,const void*> EagerlyAssumeTag
Douglas Gregora5fdd9c2010-05-11 06:18:17 +00001991 = std::pair<const void*,const void*>(&EagerlyAssumeTag,static_cast<void*>(0));
Ted Kremenekf5cae632009-02-28 20:50:43 +00001992
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00001993void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00001994 const Expr *Ex) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00001995 for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
1996 ExplodedNode *Pred = *I;
Mike Stump1eb44332009-09-09 15:08:12 +00001997
Ted Kremenekb2939022009-02-25 23:32:10 +00001998 // Test if the previous node was as the same expression. This can happen
1999 // when the expression fails to evaluate to anything meaningful and
2000 // (as an optimization) we don't generate a node.
Mike Stump1eb44332009-09-09 15:08:12 +00002001 ProgramPoint P = Pred->getLocation();
Ted Kremenekb2939022009-02-25 23:32:10 +00002002 if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) {
Mike Stump1eb44332009-09-09 15:08:12 +00002003 Dst.Add(Pred);
Ted Kremenekb2939022009-02-25 23:32:10 +00002004 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00002005 }
Ted Kremenekb2939022009-02-25 23:32:10 +00002006
Zhongxing Xu59fea602010-04-20 04:53:09 +00002007 const GRState* state = GetState(Pred);
Ted Kremenek13976632010-02-08 16:18:51 +00002008 SVal V = state->getSVal(Ex);
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002009 if (nonloc::SymExprVal *SEV = dyn_cast<nonloc::SymExprVal>(&V)) {
Ted Kremenek48af2a92009-02-25 22:32:02 +00002010 // First assume that the condition is true.
Ted Kremenek28f47b92010-12-01 22:16:56 +00002011 if (const GRState *stateTrue = state->assume(*SEV, true)) {
Mike Stump1eb44332009-09-09 15:08:12 +00002012 stateTrue = stateTrue->BindExpr(Ex,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002013 svalBuilder.makeIntVal(1U, Ex->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00002014 Dst.Add(Builder->generateNode(PostStmtCustom(Ex,
Zhongxing Xu25e695b2009-08-15 03:17:38 +00002015 &EagerlyAssumeTag, Pred->getLocationContext()),
Ted Kremenek48af2a92009-02-25 22:32:02 +00002016 stateTrue, Pred));
2017 }
Mike Stump1eb44332009-09-09 15:08:12 +00002018
Ted Kremenek48af2a92009-02-25 22:32:02 +00002019 // Next, assume that the condition is false.
Ted Kremenek28f47b92010-12-01 22:16:56 +00002020 if (const GRState *stateFalse = state->assume(*SEV, false)) {
Mike Stump1eb44332009-09-09 15:08:12 +00002021 stateFalse = stateFalse->BindExpr(Ex,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002022 svalBuilder.makeIntVal(0U, Ex->getType()));
Zhongxing Xu25e695b2009-08-15 03:17:38 +00002023 Dst.Add(Builder->generateNode(PostStmtCustom(Ex, &EagerlyAssumeTag,
2024 Pred->getLocationContext()),
Ted Kremenek48af2a92009-02-25 22:32:02 +00002025 stateFalse, Pred));
2026 }
2027 }
2028 else
2029 Dst.Add(Pred);
2030 }
2031}
2032
2033//===----------------------------------------------------------------------===//
Ted Kremenek4beaa9f2010-09-10 03:05:33 +00002034// Transfer function: Objective-C @synchronized.
2035//===----------------------------------------------------------------------===//
2036
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002037void ExprEngine::VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
Ted Kremenek4beaa9f2010-09-10 03:05:33 +00002038 ExplodedNode *Pred,
2039 ExplodedNodeSet &Dst) {
2040
2041 // The mutex expression is a CFGElement, so we don't need to explicitly
2042 // visit it since it will already be processed.
2043
2044 // Pre-visit the ObjCAtSynchronizedStmt.
2045 ExplodedNodeSet Tmp;
2046 Tmp.Add(Pred);
2047 CheckerVisit(S, Dst, Tmp, PreVisitStmtCallback);
2048}
2049
2050//===----------------------------------------------------------------------===//
Ted Kremenek48af2a92009-02-25 22:32:02 +00002051// Transfer function: Objective-C ivar references.
2052//===----------------------------------------------------------------------===//
2053
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002054void ExprEngine::VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr* Ex,
2055 ExplodedNode* Pred,
2056 ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00002057
Ted Kremenek892697d2010-12-16 07:46:53 +00002058 // Visit the base expression, which is needed for computing the lvalue
2059 // of the ivar.
2060 ExplodedNodeSet dstBase;
2061 const Expr *baseExpr = Ex->getBase();
2062 Visit(baseExpr, Pred, dstBase);
Mike Stump1eb44332009-09-09 15:08:12 +00002063
Ted Kremenek892697d2010-12-16 07:46:53 +00002064 // Using the base, compute the lvalue of the instance variable.
2065 for (ExplodedNodeSet::iterator I = dstBase.begin(), E = dstBase.end();
2066 I!=E; ++I) {
2067 ExplodedNode *nodeBase = *I;
2068 const GRState *state = GetState(nodeBase);
2069 SVal baseVal = state->getSVal(baseExpr);
2070 SVal location = state->getLValue(Ex->getDecl(), baseVal);
2071 MakeNode(Dst, Ex, *I, state->BindExpr(Ex, location));
Ted Kremenek97ed4f62008-10-17 00:03:18 +00002072 }
2073}
2074
2075//===----------------------------------------------------------------------===//
Ted Kremenekaf337412008-11-12 19:24:17 +00002076// Transfer function: Objective-C fast enumeration 'for' statements.
2077//===----------------------------------------------------------------------===//
2078
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002079void ExprEngine::VisitObjCForCollectionStmt(const ObjCForCollectionStmt* S,
Zhongxing Xub317f8f2009-09-10 05:44:00 +00002080 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Mike Stump1eb44332009-09-09 15:08:12 +00002081
Ted Kremenekaf337412008-11-12 19:24:17 +00002082 // ObjCForCollectionStmts are processed in two places. This method
2083 // handles the case where an ObjCForCollectionStmt* occurs as one of the
2084 // statements within a basic block. This transfer function does two things:
2085 //
2086 // (1) binds the next container value to 'element'. This creates a new
2087 // node in the ExplodedGraph.
2088 //
2089 // (2) binds the value 0/1 to the ObjCForCollectionStmt* itself, indicating
2090 // whether or not the container has any more elements. This value
2091 // will be tested in ProcessBranch. We need to explicitly bind
2092 // this value because a container can contain nil elements.
Mike Stump1eb44332009-09-09 15:08:12 +00002093 //
Ted Kremenekaf337412008-11-12 19:24:17 +00002094 // FIXME: Eventually this logic should actually do dispatches to
2095 // 'countByEnumeratingWithState:objects:count:' (NSFastEnumeration).
2096 // This will require simulating a temporary NSFastEnumerationState, either
2097 // through an SVal or through the use of MemRegions. This value can
2098 // be affixed to the ObjCForCollectionStmt* instead of 0/1; when the loop
2099 // terminates we reclaim the temporary (it goes out of scope) and we
2100 // we can test if the SVal is 0 or if the MemRegion is null (depending
2101 // on what approach we take).
2102 //
2103 // For now: simulate (1) by assigning either a symbol or nil if the
2104 // container is empty. Thus this transfer function will by default
2105 // result in state splitting.
Mike Stump1eb44332009-09-09 15:08:12 +00002106
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002107 const Stmt* elem = S->getElement();
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002108 SVal ElementV;
Mike Stump1eb44332009-09-09 15:08:12 +00002109
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002110 if (const DeclStmt* DS = dyn_cast<DeclStmt>(elem)) {
2111 const VarDecl* ElemD = cast<VarDecl>(DS->getSingleDecl());
Ted Kremenekaf337412008-11-12 19:24:17 +00002112 assert (ElemD->getInit() == 0);
Ted Kremenekd17da2b2009-08-21 22:28:32 +00002113 ElementV = GetState(Pred)->getLValue(ElemD, Pred->getLocationContext());
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002114 VisitObjCForCollectionStmtAux(S, Pred, Dst, ElementV);
2115 return;
Ted Kremenekaf337412008-11-12 19:24:17 +00002116 }
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002117
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002118 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00002119 Visit(cast<Expr>(elem), Pred, Tmp);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002120 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) {
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002121 const GRState* state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002122 VisitObjCForCollectionStmtAux(S, *I, Dst, state->getSVal(elem));
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002123 }
2124}
2125
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002126void ExprEngine::VisitObjCForCollectionStmtAux(const ObjCForCollectionStmt* S,
Zhongxing Xub317f8f2009-09-10 05:44:00 +00002127 ExplodedNode* Pred, ExplodedNodeSet& Dst,
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002128 SVal ElementV) {
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002129
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002130 // Check if the location we are writing back to is a null pointer.
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002131 const Stmt* elem = S->getElement();
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002132 ExplodedNodeSet Tmp;
Ted Kremenek9c149532010-12-01 21:57:22 +00002133 evalLocation(Tmp, elem, Pred, GetState(Pred), ElementV, NULL, false);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002134
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002135 if (Tmp.empty())
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002136 return;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002137
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002138 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
2139 Pred = *NI;
2140 const GRState *state = GetState(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00002141
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002142 // Handle the case where the container still has elements.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002143 SVal TrueV = svalBuilder.makeTruthVal(1);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002144 const GRState *hasElems = state->BindExpr(S, TrueV);
Ted Kremenek06fb99f2008-11-14 19:47:18 +00002145
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002146 // Handle the case where the container has no elements.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002147 SVal FalseV = svalBuilder.makeTruthVal(0);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002148 const GRState *noElems = state->BindExpr(S, FalseV);
Mike Stump1eb44332009-09-09 15:08:12 +00002149
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002150 if (loc::MemRegionVal* MV = dyn_cast<loc::MemRegionVal>(&ElementV))
2151 if (const TypedRegion* R = dyn_cast<TypedRegion>(MV->getRegion())) {
2152 // FIXME: The proper thing to do is to really iterate over the
2153 // container. We will do this with dispatch logic to the store.
2154 // For now, just 'conjure' up a symbolic value.
Zhongxing Xu018220c2010-08-11 06:10:55 +00002155 QualType T = R->getValueType();
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002156 assert(Loc::IsLocType(T));
2157 unsigned Count = Builder->getCurrentBlockCount();
2158 SymbolRef Sym = SymMgr.getConjuredSymbol(elem, T, Count);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002159 SVal V = svalBuilder.makeLoc(Sym);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002160 hasElems = hasElems->bindLoc(ElementV, V);
Mike Stump1eb44332009-09-09 15:08:12 +00002161
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002162 // Bind the location to 'nil' on the false branch.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002163 SVal nilV = svalBuilder.makeIntVal(0, T);
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002164 noElems = noElems->bindLoc(ElementV, nilV);
2165 }
Ted Kremenek116ed0a2008-11-12 21:12:46 +00002166
Ted Kremenekb4b817d2009-11-11 03:26:34 +00002167 // Create the new nodes.
2168 MakeNode(Dst, S, Pred, hasElems);
2169 MakeNode(Dst, S, Pred, noElems);
2170 }
Ted Kremenekaf337412008-11-12 19:24:17 +00002171}
2172
2173//===----------------------------------------------------------------------===//
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002174// Transfer function: Objective-C message expressions.
2175//===----------------------------------------------------------------------===//
2176
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002177namespace {
2178class ObjCMsgWLItem {
2179public:
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002180 ObjCMessageExpr::const_arg_iterator I;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002181 ExplodedNode *N;
2182
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002183 ObjCMsgWLItem(const ObjCMessageExpr::const_arg_iterator &i, ExplodedNode *n)
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002184 : I(i), N(n) {}
2185};
2186} // end anonymous namespace
2187
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002188void ExprEngine::VisitObjCMessageExpr(const ObjCMessageExpr* ME,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002189 ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00002190 ExplodedNodeSet& Dst){
Mike Stump1eb44332009-09-09 15:08:12 +00002191
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002192 // Create a worklist to process both the arguments.
2193 llvm::SmallVector<ObjCMsgWLItem, 20> WL;
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002194
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002195 // But first evaluate the receiver (if any).
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002196 ObjCMessageExpr::const_arg_iterator AI = ME->arg_begin(), AE = ME->arg_end();
2197 if (const Expr *Receiver = ME->getInstanceReceiver()) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002198 ExplodedNodeSet Tmp;
2199 Visit(Receiver, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002200
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002201 if (Tmp.empty())
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002202 return;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002203
2204 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I)
2205 WL.push_back(ObjCMsgWLItem(AI, *I));
2206 }
2207 else
2208 WL.push_back(ObjCMsgWLItem(AI, Pred));
2209
2210 // Evaluate the arguments.
2211 ExplodedNodeSet ArgsEvaluated;
2212 while (!WL.empty()) {
2213 ObjCMsgWLItem Item = WL.back();
2214 WL.pop_back();
2215
2216 if (Item.I == AE) {
2217 ArgsEvaluated.insert(Item.N);
2218 continue;
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002219 }
Mike Stump1eb44332009-09-09 15:08:12 +00002220
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002221 // Evaluate the subexpression.
2222 ExplodedNodeSet Tmp;
2223
2224 // FIXME: [Objective-C++] handle arguments that are references
2225 Visit(*Item.I, Item.N, Tmp);
2226
2227 // Enqueue evaluating the next argument on the worklist.
2228 ++(Item.I);
2229 for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
2230 WL.push_back(ObjCMsgWLItem(Item.I, *NI));
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002231 }
Mike Stump1eb44332009-09-09 15:08:12 +00002232
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002233 // Now that the arguments are processed, handle the previsits checks.
2234 ExplodedNodeSet DstPrevisit;
Jordy Rose72905cf2010-08-04 07:10:57 +00002235 CheckerVisit(ME, DstPrevisit, ArgsEvaluated, PreVisitStmtCallback);
Mike Stump1eb44332009-09-09 15:08:12 +00002236
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002237 // Proceed with evaluate the message expression.
Ted Kremenek9c149532010-12-01 21:57:22 +00002238 ExplodedNodeSet dstEval;
Mike Stump1eb44332009-09-09 15:08:12 +00002239
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002240 for (ExplodedNodeSet::iterator DI = DstPrevisit.begin(),
2241 DE = DstPrevisit.end(); DI != DE; ++DI) {
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002242
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002243 Pred = *DI;
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002244 bool RaisesException = false;
Ted Kremenek9c149532010-12-01 21:57:22 +00002245 unsigned oldSize = dstEval.size();
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002246 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002247 SaveOr OldHasGen(Builder->HasGeneratedNode);
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002248
Douglas Gregor04badcf2010-04-21 00:45:42 +00002249 if (const Expr *Receiver = ME->getInstanceReceiver()) {
Zhongxing Xu59fea602010-04-20 04:53:09 +00002250 const GRState *state = GetState(Pred);
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002251
2252 // Bifurcate the state into nil and non-nil ones.
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002253 DefinedOrUnknownSVal receiverVal =
Ted Kremenek13976632010-02-08 16:18:51 +00002254 cast<DefinedOrUnknownSVal>(state->getSVal(Receiver));
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002255
2256 const GRState *notNilState, *nilState;
Ted Kremenek28f47b92010-12-01 22:16:56 +00002257 llvm::tie(notNilState, nilState) = state->assume(receiverVal);
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002258
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002259 // There are three cases: can be nil or non-nil, must be nil, must be
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002260 // non-nil. We handle must be nil, and merge the rest two into non-nil.
2261 if (nilState && !notNilState) {
Ted Kremenek9c149532010-12-01 21:57:22 +00002262 CheckerEvalNilReceiver(ME, dstEval, nilState, Pred);
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002263 continue;
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002264 }
2265
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002266 // Check if the "raise" message was sent.
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002267 assert(notNilState);
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002268 if (ME->getSelector() == RaiseSel)
2269 RaisesException = true;
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002270
2271 // Check if we raise an exception. For now treat these as sinks.
2272 // Eventually we will want to handle exceptions properly.
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002273 if (RaisesException)
2274 Builder->BuildSinks = true;
2275
2276 // Dispatch to plug-in transfer function.
Ted Kremenek9c149532010-12-01 21:57:22 +00002277 evalObjCMessageExpr(dstEval, ME, Pred, notNilState);
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002278 }
Douglas Gregor04badcf2010-04-21 00:45:42 +00002279 else if (ObjCInterfaceDecl *Iface = ME->getReceiverInterface()) {
2280 IdentifierInfo* ClsName = Iface->getIdentifier();
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002281 Selector S = ME->getSelector();
2282
2283 // Check for special instance methods.
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002284 if (!NSExceptionII) {
2285 ASTContext& Ctx = getContext();
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002286 NSExceptionII = &Ctx.Idents.get("NSException");
2287 }
2288
2289 if (ClsName == NSExceptionII) {
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002290 enum { NUM_RAISE_SELECTORS = 2 };
2291
2292 // Lazily create a cache of the selectors.
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002293 if (!NSExceptionInstanceRaiseSelectors) {
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002294 ASTContext& Ctx = getContext();
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002295 NSExceptionInstanceRaiseSelectors =
2296 new Selector[NUM_RAISE_SELECTORS];
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002297 llvm::SmallVector<IdentifierInfo*, NUM_RAISE_SELECTORS> II;
2298 unsigned idx = 0;
2299
2300 // raise:format:
2301 II.push_back(&Ctx.Idents.get("raise"));
2302 II.push_back(&Ctx.Idents.get("format"));
2303 NSExceptionInstanceRaiseSelectors[idx++] =
2304 Ctx.Selectors.getSelector(II.size(), &II[0]);
2305
2306 // raise:format::arguments:
2307 II.push_back(&Ctx.Idents.get("arguments"));
2308 NSExceptionInstanceRaiseSelectors[idx++] =
2309 Ctx.Selectors.getSelector(II.size(), &II[0]);
2310 }
2311
2312 for (unsigned i = 0; i < NUM_RAISE_SELECTORS; ++i)
2313 if (S == NSExceptionInstanceRaiseSelectors[i]) {
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002314 RaisesException = true;
2315 break;
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002316 }
2317 }
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002318
2319 // Check if we raise an exception. For now treat these as sinks.
2320 // Eventually we will want to handle exceptions properly.
Zhongxing Xua46e4d92009-12-02 05:49:12 +00002321 if (RaisesException)
2322 Builder->BuildSinks = true;
2323
2324 // Dispatch to plug-in transfer function.
Ted Kremenek9c149532010-12-01 21:57:22 +00002325 evalObjCMessageExpr(dstEval, ME, Pred, Builder->GetState(Pred));
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002326 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002327
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002328 // Handle the case where no nodes where generated. Auto-generate that
2329 // contains the updated state if we aren't generating sinks.
Ted Kremenek9c149532010-12-01 21:57:22 +00002330 if (!Builder->BuildSinks && dstEval.size() == oldSize &&
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002331 !Builder->HasGeneratedNode)
Ted Kremenek9c149532010-12-01 21:57:22 +00002332 MakeNode(dstEval, ME, Pred, GetState(Pred));
Ted Kremenekc79d7d42009-11-21 01:25:37 +00002333 }
Mike Stump1eb44332009-09-09 15:08:12 +00002334
Ted Kremenek38ac4f52009-12-22 22:13:46 +00002335 // Finally, perform the post-condition check of the ObjCMessageExpr and store
2336 // the created nodes in 'Dst'.
Ted Kremenek892697d2010-12-16 07:46:53 +00002337 CheckerVisit(ME, Dst, dstEval, PostVisitStmtCallback);
Ted Kremeneke695e1c2008-04-15 23:06:53 +00002338}
2339
2340//===----------------------------------------------------------------------===//
2341// Transfer functions: Miscellaneous statements.
2342//===----------------------------------------------------------------------===//
2343
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002344void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,
2345 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
Ted Kremenek892697d2010-12-16 07:46:53 +00002346
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002347 ExplodedNodeSet S1;
Ted Kremenek892697d2010-12-16 07:46:53 +00002348 Visit(Ex, Pred, S1);
2349 ExplodedNodeSet S2;
2350 CheckerVisit(CastE, S2, S1, PreVisitStmtCallback);
2351
2352 if (CastE->getCastKind() == CK_LValueToRValue) {
2353 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I!=E; ++I) {
2354 ExplodedNode *subExprNode = *I;
2355 const GRState *state = GetState(subExprNode);
2356 evalLoad(Dst, CastE, subExprNode, state, state->getSVal(Ex));
2357 }
2358 return;
2359 }
2360
2361 // All other casts.
Ted Kremenek5d3003a2008-02-19 18:52:54 +00002362 QualType T = CastE->getType();
Zhongxing Xu933c3e12008-10-21 06:54:23 +00002363 QualType ExTy = Ex->getType();
Zhongxing Xued340f72008-10-22 08:02:16 +00002364
Zhongxing Xud3118bd2008-10-31 07:26:14 +00002365 if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE))
Douglas Gregor49badde2008-10-27 19:41:14 +00002366 T = ExCast->getTypeAsWritten();
Ted Kremenek892697d2010-12-16 07:46:53 +00002367
2368#if 0
Ted Kremenek949bdb42009-12-23 00:26:16 +00002369 // If we are evaluating the cast in an lvalue context, we implicitly want
2370 // the cast to evaluate to a location.
2371 if (asLValue) {
2372 ASTContext &Ctx = getContext();
2373 T = Ctx.getPointerType(Ctx.getCanonicalType(T));
Ted Kremenek077a40d2009-12-23 01:19:20 +00002374 ExTy = Ctx.getPointerType(Ctx.getCanonicalType(ExTy));
Ted Kremenek949bdb42009-12-23 00:26:16 +00002375 }
Ted Kremenek892697d2010-12-16 07:46:53 +00002376#endif
Ted Kremenek32c3fa42009-07-21 21:03:30 +00002377
Zhongxing Xub79b1172010-01-22 04:30:00 +00002378 switch (CastE->getCastKind()) {
John McCall2de56d12010-08-25 11:45:40 +00002379 case CK_ToVoid:
Zhongxing Xub79b1172010-01-22 04:30:00 +00002380 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I)
2381 Dst.Add(*I);
2382 return;
2383
John McCall0ae287a2010-12-01 04:43:34 +00002384 case CK_LValueToRValue:
John McCall2de56d12010-08-25 11:45:40 +00002385 case CK_NoOp:
2386 case CK_FunctionToPointerDecay:
Zhongxing Xub79b1172010-01-22 04:30:00 +00002387 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {
2388 // Copy the SVal of Ex to CastE.
2389 ExplodedNode *N = *I;
2390 const GRState *state = GetState(N);
Ted Kremenek13976632010-02-08 16:18:51 +00002391 SVal V = state->getSVal(Ex);
Zhongxing Xub79b1172010-01-22 04:30:00 +00002392 state = state->BindExpr(CastE, V);
2393 MakeNode(Dst, CastE, N, state);
2394 }
2395 return;
2396
John McCallf6a16482010-12-04 03:47:34 +00002397 case CK_GetObjCProperty:
John McCalldaa8e4e2010-11-15 09:13:47 +00002398 case CK_Dependent:
John McCall2de56d12010-08-25 11:45:40 +00002399 case CK_ArrayToPointerDecay:
2400 case CK_BitCast:
2401 case CK_LValueBitCast:
2402 case CK_IntegralCast:
John McCall404cd162010-11-13 01:35:44 +00002403 case CK_NullToPointer:
John McCall2de56d12010-08-25 11:45:40 +00002404 case CK_IntegralToPointer:
2405 case CK_PointerToIntegral:
John McCalldaa8e4e2010-11-15 09:13:47 +00002406 case CK_PointerToBoolean:
2407 case CK_IntegralToBoolean:
John McCall2de56d12010-08-25 11:45:40 +00002408 case CK_IntegralToFloating:
2409 case CK_FloatingToIntegral:
John McCalldaa8e4e2010-11-15 09:13:47 +00002410 case CK_FloatingToBoolean:
John McCall2de56d12010-08-25 11:45:40 +00002411 case CK_FloatingCast:
John McCall2bb5d002010-11-13 09:02:35 +00002412 case CK_FloatingRealToComplex:
John McCallf3ea8cf2010-11-14 08:17:51 +00002413 case CK_FloatingComplexToReal:
2414 case CK_FloatingComplexToBoolean:
John McCall2bb5d002010-11-13 09:02:35 +00002415 case CK_FloatingComplexCast:
John McCallf3ea8cf2010-11-14 08:17:51 +00002416 case CK_FloatingComplexToIntegralComplex:
John McCall2bb5d002010-11-13 09:02:35 +00002417 case CK_IntegralRealToComplex:
John McCallf3ea8cf2010-11-14 08:17:51 +00002418 case CK_IntegralComplexToReal:
2419 case CK_IntegralComplexToBoolean:
John McCall2bb5d002010-11-13 09:02:35 +00002420 case CK_IntegralComplexCast:
John McCallf3ea8cf2010-11-14 08:17:51 +00002421 case CK_IntegralComplexToFloatingComplex:
John McCall2de56d12010-08-25 11:45:40 +00002422 case CK_AnyPointerToObjCPointerCast:
2423 case CK_AnyPointerToBlockPointerCast:
Zhongxing Xu4fd56812010-11-26 08:21:53 +00002424
John McCall2de56d12010-08-25 11:45:40 +00002425 case CK_ObjCObjectLValueCast: {
Ted Kremenek846eabd2010-12-01 21:28:31 +00002426 // Delegate to SValBuilder to process.
Zhongxing Xub79b1172010-01-22 04:30:00 +00002427 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {
2428 ExplodedNode* N = *I;
2429 const GRState* state = GetState(N);
Ted Kremenek13976632010-02-08 16:18:51 +00002430 SVal V = state->getSVal(Ex);
Ted Kremenek9c149532010-12-01 21:57:22 +00002431 V = svalBuilder.evalCast(V, T, ExTy);
Zhongxing Xu814e6b92010-02-04 04:56:43 +00002432 state = state->BindExpr(CastE, V);
Zhongxing Xub79b1172010-01-22 04:30:00 +00002433 MakeNode(Dst, CastE, N, state);
2434 }
2435 return;
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +00002436 }
Zhongxing Xu4fd56812010-11-26 08:21:53 +00002437
2438 case CK_DerivedToBase:
2439 case CK_UncheckedDerivedToBase:
2440 // For DerivedToBase cast, delegate to the store manager.
2441 for (ExplodedNodeSet::iterator I = S2.begin(), E = S2.end(); I != E; ++I) {
2442 ExplodedNode *node = *I;
2443 const GRState *state = GetState(node);
2444 SVal val = state->getSVal(Ex);
2445 val = getStoreManager().evalDerivedToBase(val, T);
2446 state = state->BindExpr(CastE, val);
2447 MakeNode(Dst, CastE, node, state);
2448 }
2449 return;
2450
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +00002451 // Various C++ casts that are not handled yet.
John McCall2de56d12010-08-25 11:45:40 +00002452 case CK_Dynamic:
2453 case CK_ToUnion:
2454 case CK_BaseToDerived:
2455 case CK_NullToMemberPointer:
2456 case CK_BaseToDerivedMemberPointer:
2457 case CK_DerivedToBaseMemberPointer:
2458 case CK_UserDefinedConversion:
2459 case CK_ConstructorConversion:
2460 case CK_VectorSplat:
2461 case CK_MemberPointerToBoolean: {
Ted Kremenek8ad9cbc2010-06-22 19:05:10 +00002462 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
2463 Builder->BuildSinks = true;
2464 MakeNode(Dst, CastE, Pred, GetState(Pred));
2465 return;
2466 }
Ted Kremenek874d63f2008-01-24 02:02:54 +00002467 }
Ted Kremenek9de04c42008-01-24 20:55:43 +00002468}
2469
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002470void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr* CL,
Mike Stump1eb44332009-09-09 15:08:12 +00002471 ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00002472 ExplodedNodeSet& Dst) {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002473 const InitListExpr* ILE
2474 = cast<InitListExpr>(CL->getInitializer()->IgnoreParens());
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002475 ExplodedNodeSet Tmp;
Ted Kremenek4f090272008-10-27 21:54:31 +00002476 Visit(ILE, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002477
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002478 for (ExplodedNodeSet::iterator I = Tmp.begin(), EI = Tmp.end(); I!=EI; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002479 const GRState* state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002480 SVal ILV = state->getSVal(ILE);
Ted Kremenek67d12872009-12-07 22:05:27 +00002481 const LocationContext *LC = (*I)->getLocationContext();
2482 state = state->bindCompoundLiteral(CL, LC, ILV);
Ted Kremenek4f090272008-10-27 21:54:31 +00002483
Ted Kremenek892697d2010-12-16 07:46:53 +00002484 if (CL->isLValue()) {
Ted Kremenek67d12872009-12-07 22:05:27 +00002485 MakeNode(Dst, CL, *I, state->BindExpr(CL, state->getLValue(CL, LC)));
2486 }
Zhongxing Xuf22679e2008-11-07 10:38:33 +00002487 else
Ted Kremenek8e029342009-08-27 22:17:37 +00002488 MakeNode(Dst, CL, *I, state->BindExpr(CL, ILV));
Ted Kremenek4f090272008-10-27 21:54:31 +00002489 }
2490}
2491
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002492void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
Mike Stump1eb44332009-09-09 15:08:12 +00002493 ExplodedNodeSet& Dst) {
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002494
Mike Stump1eb44332009-09-09 15:08:12 +00002495 // The CFG has one DeclStmt per Decl.
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002496 const Decl* D = *DS->decl_begin();
Mike Stump1eb44332009-09-09 15:08:12 +00002497
Ted Kremeneke6c62e32008-08-28 18:34:26 +00002498 if (!D || !isa<VarDecl>(D))
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002499 return;
Mike Stump1eb44332009-09-09 15:08:12 +00002500
2501 const VarDecl* VD = dyn_cast<VarDecl>(D);
Zhongxing Xu1f191242010-07-23 02:54:53 +00002502 const Expr* InitEx = VD->getInit();
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002503
2504 // FIXME: static variables may have an initializer, but the second
2505 // time a function is called those values may not be current.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002506 ExplodedNodeSet Tmp;
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002507
Zhongxing Xuf45fbad2010-12-19 02:26:37 +00002508 if (InitEx) {
2509 if (VD->getType()->isReferenceType() && !InitEx->isLValue()) {
Zhongxing Xu05e53912010-12-22 07:20:27 +00002510 // If the initializer is C++ record type, it should already has a
2511 // temp object.
2512 if (!InitEx->getType()->isRecordType())
2513 CreateCXXTemporaryObject(InitEx, Pred, Tmp);
2514 else
2515 Tmp.Add(Pred);
Zhongxing Xuf45fbad2010-12-19 02:26:37 +00002516 } else
2517 Visit(InitEx, Pred, Tmp);
2518 } else
Ted Kremeneke6c62e32008-08-28 18:34:26 +00002519 Tmp.Add(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00002520
Ted Kremenekae162332009-11-07 03:56:57 +00002521 ExplodedNodeSet Tmp2;
Jordy Rose72905cf2010-08-04 07:10:57 +00002522 CheckerVisit(DS, Tmp2, Tmp, PreVisitStmtCallback);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002523
Ted Kremenekae162332009-11-07 03:56:57 +00002524 for (ExplodedNodeSet::iterator I=Tmp2.begin(), E=Tmp2.end(); I!=E; ++I) {
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002525 ExplodedNode *N = *I;
Ted Kremenekae162332009-11-07 03:56:57 +00002526 const GRState *state = GetState(N);
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002527
Zhongxing Xu4193eca2008-12-20 06:32:12 +00002528 // Decls without InitExpr are not initialized explicitly.
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002529 const LocationContext *LC = N->getLocationContext();
Ted Kremenekd17da2b2009-08-21 22:28:32 +00002530
Ted Kremenekaf337412008-11-12 19:24:17 +00002531 if (InitEx) {
Ted Kremenek13976632010-02-08 16:18:51 +00002532 SVal InitVal = state->getSVal(InitEx);
Mike Stump1eb44332009-09-09 15:08:12 +00002533
Zhongxing Xu05e53912010-12-22 07:20:27 +00002534 // We bound the temp obj region to the CXXConstructExpr. Now recover
2535 // the lazy compound value when the variable is not a reference.
2536 if (AMgr.getLangOptions().CPlusPlus && VD->getType()->isRecordType() &&
2537 !VD->getType()->isReferenceType() && isa<loc::MemRegionVal>(InitVal)){
2538 InitVal = state->getSVal(cast<loc::MemRegionVal>(InitVal).getRegion());
2539 assert(isa<nonloc::LazyCompoundVal>(InitVal));
2540 }
2541
Ted Kremenekaf337412008-11-12 19:24:17 +00002542 // Recover some path-sensitivity if a scalar value evaluated to
2543 // UnknownVal.
Ted Kremeneka804a682010-03-02 21:43:52 +00002544 if ((InitVal.isUnknown() ||
2545 !getConstraintManager().canReasonAbout(InitVal)) &&
2546 !VD->getType()->isReferenceType()) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002547 InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx,
Zhongxing Xu5206f0b2009-11-03 12:13:38 +00002548 Builder->getCurrentBlockCount());
Mike Stump1eb44332009-09-09 15:08:12 +00002549 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002550
Ted Kremenek9c149532010-12-01 21:57:22 +00002551 evalBind(Dst, DS, *I, state,
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002552 loc::MemRegionVal(state->getRegion(VD, LC)), InitVal, true);
Mike Stump1eb44332009-09-09 15:08:12 +00002553 }
Ted Kremenek5b8d9012009-02-14 01:54:57 +00002554 else {
Ted Kremenekf6f56d42009-11-04 00:09:15 +00002555 state = state->bindDeclWithNoInit(state->getRegion(VD, LC));
Ted Kremenek5b8d9012009-02-14 01:54:57 +00002556 MakeNode(Dst, DS, *I, state);
Ted Kremenekefd59942008-12-08 22:47:34 +00002557 }
Ted Kremenek5b7dcce2008-04-22 22:25:27 +00002558 }
Ted Kremenek9de04c42008-01-24 20:55:43 +00002559}
Ted Kremenek874d63f2008-01-24 02:02:54 +00002560
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002561void ExprEngine::VisitCondInit(const VarDecl *VD, const Stmt *S,
Ted Kremenekfcfb5032009-12-24 00:40:03 +00002562 ExplodedNode *Pred, ExplodedNodeSet& Dst) {
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002563
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002564 const Expr* InitEx = VD->getInit();
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002565 ExplodedNodeSet Tmp;
2566 Visit(InitEx, Pred, Tmp);
2567
2568 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2569 ExplodedNode *N = *I;
2570 const GRState *state = GetState(N);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002571
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002572 const LocationContext *LC = N->getLocationContext();
Ted Kremenek13976632010-02-08 16:18:51 +00002573 SVal InitVal = state->getSVal(InitEx);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002574
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002575 // Recover some path-sensitivity if a scalar value evaluated to
2576 // UnknownVal.
2577 if (InitVal.isUnknown() ||
2578 !getConstraintManager().canReasonAbout(InitVal)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002579 InitVal = svalBuilder.getConjuredSymbolVal(NULL, InitEx,
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002580 Builder->getCurrentBlockCount());
2581 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002582
Ted Kremenek9c149532010-12-01 21:57:22 +00002583 evalBind(Dst, S, N, state,
Ted Kremenek61dfbec2009-12-23 04:49:01 +00002584 loc::MemRegionVal(state->getRegion(VD, LC)), InitVal, true);
2585 }
2586}
2587
Ted Kremenekf75b1862008-10-30 17:47:32 +00002588namespace {
2589 // This class is used by VisitInitListExpr as an item in a worklist
2590 // for processing the values contained in an InitListExpr.
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +00002591class InitListWLItem {
Ted Kremenekf75b1862008-10-30 17:47:32 +00002592public:
2593 llvm::ImmutableList<SVal> Vals;
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002594 ExplodedNode* N;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002595 InitListExpr::const_reverse_iterator Itr;
Mike Stump1eb44332009-09-09 15:08:12 +00002596
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002597 InitListWLItem(ExplodedNode* n, llvm::ImmutableList<SVal> vals,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002598 InitListExpr::const_reverse_iterator itr)
Ted Kremenekf75b1862008-10-30 17:47:32 +00002599 : Vals(vals), N(n), Itr(itr) {}
2600};
2601}
2602
2603
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002604void ExprEngine::VisitInitListExpr(const InitListExpr* E, ExplodedNode* Pred,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002605 ExplodedNodeSet& Dst) {
Ted Kremeneka49e3672008-10-30 23:14:36 +00002606
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002607 const GRState* state = GetState(Pred);
Ted Kremenek76dba7b2008-11-13 05:05:34 +00002608 QualType T = getContext().getCanonicalType(E->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00002609 unsigned NumInitElements = E->getNumInits();
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002610
Douglas Gregorfb87b892010-04-26 21:31:17 +00002611 if (T->isArrayType() || T->isRecordType() || T->isVectorType()) {
Ted Kremeneka49e3672008-10-30 23:14:36 +00002612 llvm::ImmutableList<SVal> StartVals = getBasicVals().getEmptySValList();
Mike Stump1eb44332009-09-09 15:08:12 +00002613
Ted Kremeneka49e3672008-10-30 23:14:36 +00002614 // Handle base case where the initializer has no elements.
2615 // e.g: static int* myArray[] = {};
2616 if (NumInitElements == 0) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002617 SVal V = svalBuilder.makeCompoundVal(T, StartVals);
Ted Kremenek8e029342009-08-27 22:17:37 +00002618 MakeNode(Dst, E, Pred, state->BindExpr(E, V));
Ted Kremeneka49e3672008-10-30 23:14:36 +00002619 return;
Mike Stump1eb44332009-09-09 15:08:12 +00002620 }
2621
Ted Kremeneka49e3672008-10-30 23:14:36 +00002622 // Create a worklist to process the initializers.
2623 llvm::SmallVector<InitListWLItem, 10> WorkList;
Mike Stump1eb44332009-09-09 15:08:12 +00002624 WorkList.reserve(NumInitElements);
2625 WorkList.push_back(InitListWLItem(Pred, StartVals, E->rbegin()));
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002626 InitListExpr::const_reverse_iterator ItrEnd = E->rend();
Ted Kremenekcf549592009-09-22 21:19:14 +00002627 assert(!(E->rbegin() == E->rend()));
Mike Stump1eb44332009-09-09 15:08:12 +00002628
Ted Kremeneka49e3672008-10-30 23:14:36 +00002629 // Process the worklist until it is empty.
Ted Kremenekf75b1862008-10-30 17:47:32 +00002630 while (!WorkList.empty()) {
2631 InitListWLItem X = WorkList.back();
2632 WorkList.pop_back();
Mike Stump1eb44332009-09-09 15:08:12 +00002633
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002634 ExplodedNodeSet Tmp;
Ted Kremenekf75b1862008-10-30 17:47:32 +00002635 Visit(*X.Itr, X.N, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002636
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002637 InitListExpr::const_reverse_iterator NewItr = X.Itr + 1;
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002638
Zhongxing Xubb141212009-12-16 11:27:52 +00002639 for (ExplodedNodeSet::iterator NI=Tmp.begin(),NE=Tmp.end();NI!=NE;++NI) {
Ted Kremenekf75b1862008-10-30 17:47:32 +00002640 // Get the last initializer value.
2641 state = GetState(*NI);
Ted Kremenek13976632010-02-08 16:18:51 +00002642 SVal InitV = state->getSVal(cast<Expr>(*X.Itr));
Mike Stump1eb44332009-09-09 15:08:12 +00002643
Ted Kremenekf75b1862008-10-30 17:47:32 +00002644 // Construct the new list of values by prepending the new value to
2645 // the already constructed list.
2646 llvm::ImmutableList<SVal> NewVals =
2647 getBasicVals().consVals(InitV, X.Vals);
Mike Stump1eb44332009-09-09 15:08:12 +00002648
Ted Kremenekf75b1862008-10-30 17:47:32 +00002649 if (NewItr == ItrEnd) {
Zhongxing Xua189dca2008-10-31 03:01:26 +00002650 // Now we have a list holding all init values. Make CompoundValData.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002651 SVal V = svalBuilder.makeCompoundVal(T, NewVals);
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002652
Ted Kremenekf75b1862008-10-30 17:47:32 +00002653 // Make final state and node.
Ted Kremenek8e029342009-08-27 22:17:37 +00002654 MakeNode(Dst, E, *NI, state->BindExpr(E, V));
Ted Kremenekf75b1862008-10-30 17:47:32 +00002655 }
2656 else {
2657 // Still some initializer values to go. Push them onto the worklist.
2658 WorkList.push_back(InitListWLItem(*NI, NewVals, NewItr));
2659 }
2660 }
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002661 }
Mike Stump1eb44332009-09-09 15:08:12 +00002662
Ted Kremenek87903072008-10-30 18:34:31 +00002663 return;
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002664 }
2665
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002666 if (Loc::IsLocType(T) || T->isIntegerType()) {
2667 assert (E->getNumInits() == 1);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002668 ExplodedNodeSet Tmp;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002669 const Expr* Init = E->getInit(0);
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002670 Visit(Init, Pred, Tmp);
Zhongxing Xubb141212009-12-16 11:27:52 +00002671 for (ExplodedNodeSet::iterator I=Tmp.begin(), EI=Tmp.end(); I != EI; ++I) {
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002672 state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002673 MakeNode(Dst, E, *I, state->BindExpr(E, state->getSVal(Init)));
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002674 }
2675 return;
2676 }
2677
Zhongxing Xuc4f87062008-10-30 05:02:23 +00002678 assert(0 && "unprocessed InitListExpr type");
2679}
Ted Kremenekf233d482008-02-05 00:26:40 +00002680
Sebastian Redl05189992008-11-11 17:56:53 +00002681/// VisitSizeOfAlignOfExpr - Transfer function for sizeof(type).
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002682void ExprEngine::VisitSizeOfAlignOfExpr(const SizeOfAlignOfExpr* Ex,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002683 ExplodedNode* Pred,
2684 ExplodedNodeSet& Dst) {
Sebastian Redl05189992008-11-11 17:56:53 +00002685 QualType T = Ex->getTypeOfArgument();
Ken Dyck199c3d62010-01-11 17:06:35 +00002686 CharUnits amt;
Mike Stump1eb44332009-09-09 15:08:12 +00002687
Ted Kremenek87e80342008-03-15 03:13:20 +00002688 if (Ex->isSizeOf()) {
Mike Stump1eb44332009-09-09 15:08:12 +00002689 if (T == getContext().VoidTy) {
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002690 // sizeof(void) == 1 byte.
Ken Dyck199c3d62010-01-11 17:06:35 +00002691 amt = CharUnits::One();
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002692 }
Jordy Roseb7e3aab2010-07-05 04:42:43 +00002693 else if (!T->isConstantSizeType()) {
2694 assert(T->isVariableArrayType() && "Unknown non-constant-sized type.");
2695
2696 // FIXME: Add support for VLA type arguments, not just VLA expressions.
2697 // When that happens, we should probably refactor VLASizeChecker's code.
2698 if (Ex->isArgumentType()) {
2699 Dst.Add(Pred);
2700 return;
2701 }
2702
2703 // Get the size by getting the extent of the sub-expression.
2704 // First, visit the sub-expression to find its region.
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002705 const Expr *Arg = Ex->getArgumentExpr();
Jordy Roseb7e3aab2010-07-05 04:42:43 +00002706 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00002707 Visit(Arg, Pred, Tmp);
Jordy Roseb7e3aab2010-07-05 04:42:43 +00002708
2709 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
2710 const GRState* state = GetState(*I);
2711 const MemRegion *MR = state->getSVal(Arg).getAsRegion();
2712
2713 // If the subexpression can't be resolved to a region, we don't know
2714 // anything about its size. Just leave the state as is and continue.
2715 if (!MR) {
2716 Dst.Add(*I);
2717 continue;
2718 }
2719
2720 // The result is the extent of the VLA.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002721 SVal Extent = cast<SubRegion>(MR)->getExtent(svalBuilder);
Jordy Roseb7e3aab2010-07-05 04:42:43 +00002722 MakeNode(Dst, Ex, *I, state->BindExpr(Ex, Extent));
2723 }
2724
Ted Kremenek87e80342008-03-15 03:13:20 +00002725 return;
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002726 }
John McCallc12c5bb2010-05-15 11:32:37 +00002727 else if (T->getAs<ObjCObjectType>()) {
2728 // Some code tries to take the sizeof an ObjCObjectType, relying that
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002729 // the compiler has laid out its representation. Just report Unknown
Mike Stump1eb44332009-09-09 15:08:12 +00002730 // for these.
Ted Kremenek61e8e1b2010-02-02 02:01:51 +00002731 Dst.Add(Pred);
Ted Kremenekf342d182008-04-30 21:31:12 +00002732 return;
Ted Kremenek55f7bcb2008-12-15 18:51:00 +00002733 }
2734 else {
2735 // All other cases.
Ken Dyck199c3d62010-01-11 17:06:35 +00002736 amt = getContext().getTypeSizeInChars(T);
Mike Stump1eb44332009-09-09 15:08:12 +00002737 }
Ted Kremenek87e80342008-03-15 03:13:20 +00002738 }
2739 else // Get alignment of the type.
Ken Dyckda8e5852010-01-27 12:54:25 +00002740 amt = getContext().getTypeAlignInChars(T);
Mike Stump1eb44332009-09-09 15:08:12 +00002741
Ted Kremenek0e561a32008-03-21 21:30:14 +00002742 MakeNode(Dst, Ex, Pred,
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002743 GetState(Pred)->BindExpr(Ex,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002744 svalBuilder.makeIntVal(amt.getQuantity(), Ex->getType())));
Ted Kremenekd9435bf2008-02-12 19:49:57 +00002745}
2746
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002747void ExprEngine::VisitOffsetOfExpr(const OffsetOfExpr* OOE,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002748 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Douglas Gregor8ecdb652010-04-28 22:16:22 +00002749 Expr::EvalResult Res;
2750 if (OOE->Evaluate(Res, getContext()) && Res.Val.isInt()) {
2751 const APSInt &IV = Res.Val.getInt();
2752 assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType()));
2753 assert(OOE->getType()->isIntegerType());
2754 assert(IV.isSigned() == OOE->getType()->isSignedIntegerType());
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002755 SVal X = svalBuilder.makeIntVal(IV);
Douglas Gregor8ecdb652010-04-28 22:16:22 +00002756 MakeNode(Dst, OOE, Pred, GetState(Pred)->BindExpr(OOE, X));
2757 return;
2758 }
2759 // FIXME: Handle the case where __builtin_offsetof is not a constant.
2760 Dst.Add(Pred);
2761}
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002762
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00002763void ExprEngine::VisitUnaryOperator(const UnaryOperator* U,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002764 ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00002765 ExplodedNodeSet& Dst) {
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002766
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002767 switch (U->getOpcode()) {
Mike Stump1eb44332009-09-09 15:08:12 +00002768
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002769 default:
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00002770 break;
Mike Stump1eb44332009-09-09 15:08:12 +00002771
John McCall2de56d12010-08-25 11:45:40 +00002772 case UO_Real: {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002773 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002774 ExplodedNodeSet Tmp;
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002775 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002776
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002777 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +00002778
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002779 // FIXME: We don't have complex SValues yet.
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002780 if (Ex->getType()->isAnyComplexType()) {
2781 // Just report "Unknown."
2782 Dst.Add(*I);
2783 continue;
2784 }
Mike Stump1eb44332009-09-09 15:08:12 +00002785
John McCall2de56d12010-08-25 11:45:40 +00002786 // For all other types, UO_Real is an identity operation.
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002787 assert (U->getType() == Ex->getType());
Ted Kremeneka8538d92009-02-13 01:45:31 +00002788 const GRState* state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002789 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex)));
Mike Stump1eb44332009-09-09 15:08:12 +00002790 }
2791
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002792 return;
2793 }
Mike Stump1eb44332009-09-09 15:08:12 +00002794
John McCall2de56d12010-08-25 11:45:40 +00002795 case UO_Imag: {
Mike Stump1eb44332009-09-09 15:08:12 +00002796
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002797 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002798 ExplodedNodeSet Tmp;
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002799 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002800
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002801 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002802 // FIXME: We don't have complex SValues yet.
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002803 if (Ex->getType()->isAnyComplexType()) {
2804 // Just report "Unknown."
2805 Dst.Add(*I);
2806 continue;
2807 }
Mike Stump1eb44332009-09-09 15:08:12 +00002808
John McCall2de56d12010-08-25 11:45:40 +00002809 // For all other types, UO_Imag returns 0.
Ted Kremeneka8538d92009-02-13 01:45:31 +00002810 const GRState* state = GetState(*I);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002811 SVal X = svalBuilder.makeZeroVal(Ex->getType());
Ted Kremenek8e029342009-08-27 22:17:37 +00002812 MakeNode(Dst, U, *I, state->BindExpr(U, X));
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002813 }
Mike Stump1eb44332009-09-09 15:08:12 +00002814
Ted Kremenekb8e26e62008-06-19 17:55:38 +00002815 return;
2816 }
Douglas Gregor8ecdb652010-04-28 22:16:22 +00002817
Ted Kremenek892697d2010-12-16 07:46:53 +00002818 case UO_Plus:
2819 assert(!U->isLValue());
2820 // FALL-THROUGH.
2821 case UO_Deref:
Zhongxing Xu9c2bac02010-12-18 05:16:43 +00002822 case UO_AddrOf:
John McCall2de56d12010-08-25 11:45:40 +00002823 case UO_Extension: {
Mike Stump1eb44332009-09-09 15:08:12 +00002824
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002825 // Unary "+" is a no-op, similar to a parentheses. We still have places
2826 // where it may be a block-level expression, so we need to
2827 // generate an extra node that just propagates the value of the
2828 // subexpression.
2829
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002830 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002831 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00002832 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002833
2834 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002835 const GRState* state = GetState(*I);
Ted Kremenek13976632010-02-08 16:18:51 +00002836 MakeNode(Dst, U, *I, state->BindExpr(U, state->getSVal(Ex)));
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002837 }
Mike Stump1eb44332009-09-09 15:08:12 +00002838
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002839 return;
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002840 }
Mike Stump1eb44332009-09-09 15:08:12 +00002841
John McCall2de56d12010-08-25 11:45:40 +00002842 case UO_LNot:
2843 case UO_Minus:
2844 case UO_Not: {
Ted Kremenek892697d2010-12-16 07:46:53 +00002845 assert (!U->isLValue());
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002846 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002847 ExplodedNodeSet Tmp;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002848 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002849
2850 for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
Ted Kremeneka8538d92009-02-13 01:45:31 +00002851 const GRState* state = GetState(*I);
Mike Stump1eb44332009-09-09 15:08:12 +00002852
Ted Kremenek855cd902008-09-30 05:32:44 +00002853 // Get the value of the subexpression.
Ted Kremenek13976632010-02-08 16:18:51 +00002854 SVal V = state->getSVal(Ex);
Ted Kremenek855cd902008-09-30 05:32:44 +00002855
Ted Kremeneke04a5cb2008-11-15 00:20:05 +00002856 if (V.isUnknownOrUndef()) {
Ted Kremenek8e029342009-08-27 22:17:37 +00002857 MakeNode(Dst, U, *I, state->BindExpr(U, V));
Ted Kremeneke04a5cb2008-11-15 00:20:05 +00002858 continue;
2859 }
Mike Stump1eb44332009-09-09 15:08:12 +00002860
Ted Kremenek60595da2008-11-15 04:01:56 +00002861// QualType DstT = getContext().getCanonicalType(U->getType());
2862// QualType SrcT = getContext().getCanonicalType(Ex->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00002863//
Ted Kremenek60595da2008-11-15 04:01:56 +00002864// if (DstT != SrcT) // Perform promotions.
Ted Kremenek9c149532010-12-01 21:57:22 +00002865// V = evalCast(V, DstT);
Mike Stump1eb44332009-09-09 15:08:12 +00002866//
Ted Kremenek60595da2008-11-15 04:01:56 +00002867// if (V.isUnknownOrUndef()) {
2868// MakeNode(Dst, U, *I, BindExpr(St, U, V));
2869// continue;
2870// }
Mike Stump1eb44332009-09-09 15:08:12 +00002871
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002872 switch (U->getOpcode()) {
2873 default:
2874 assert(false && "Invalid Opcode.");
2875 break;
Mike Stump1eb44332009-09-09 15:08:12 +00002876
John McCall2de56d12010-08-25 11:45:40 +00002877 case UO_Not:
Ted Kremenek60a6e0c2008-10-01 00:21:14 +00002878 // FIXME: Do we need to handle promotions?
Ted Kremenek9c149532010-12-01 21:57:22 +00002879 state = state->BindExpr(U, evalComplement(cast<NonLoc>(V)));
Mike Stump1eb44332009-09-09 15:08:12 +00002880 break;
2881
John McCall2de56d12010-08-25 11:45:40 +00002882 case UO_Minus:
Ted Kremenek60a6e0c2008-10-01 00:21:14 +00002883 // FIXME: Do we need to handle promotions?
Ted Kremenek9c149532010-12-01 21:57:22 +00002884 state = state->BindExpr(U, evalMinus(cast<NonLoc>(V)));
Mike Stump1eb44332009-09-09 15:08:12 +00002885 break;
2886
John McCall2de56d12010-08-25 11:45:40 +00002887 case UO_LNot:
Mike Stump1eb44332009-09-09 15:08:12 +00002888
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002889 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
2890 //
2891 // Note: technically we do "E == 0", but this is the same in the
2892 // transfer functions as "0 == E".
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002893 SVal Result;
Mike Stump1eb44332009-09-09 15:08:12 +00002894
Zhongxing Xu1c96b242008-10-17 05:57:07 +00002895 if (isa<Loc>(V)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002896 Loc X = svalBuilder.makeNull();
Ted Kremenek9c149532010-12-01 21:57:22 +00002897 Result = evalBinOp(state, BO_EQ, cast<Loc>(V), X,
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002898 U->getType());
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002899 }
2900 else {
Ted Kremenek60595da2008-11-15 04:01:56 +00002901 nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType()));
Ted Kremenek9c149532010-12-01 21:57:22 +00002902 Result = evalBinOp(state, BO_EQ, cast<NonLoc>(V), X,
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002903 U->getType());
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002904 }
Mike Stump1eb44332009-09-09 15:08:12 +00002905
Ted Kremenek8e029342009-08-27 22:17:37 +00002906 state = state->BindExpr(U, Result);
Mike Stump1eb44332009-09-09 15:08:12 +00002907
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002908 break;
2909 }
Mike Stump1eb44332009-09-09 15:08:12 +00002910
Ted Kremeneka8538d92009-02-13 01:45:31 +00002911 MakeNode(Dst, U, *I, state);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002912 }
Mike Stump1eb44332009-09-09 15:08:12 +00002913
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002914 return;
2915 }
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002916 }
2917
2918 // Handle ++ and -- (both pre- and post-increment).
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002919 assert (U->isIncrementDecrementOp());
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002920 ExplodedNodeSet Tmp;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00002921 const Expr* Ex = U->getSubExpr()->IgnoreParens();
Ted Kremenek892697d2010-12-16 07:46:53 +00002922 Visit(Ex, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00002923
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002924 for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) {
Mike Stump1eb44332009-09-09 15:08:12 +00002925
Ted Kremeneka8538d92009-02-13 01:45:31 +00002926 const GRState* state = GetState(*I);
Zhongxing Xu250704b2010-12-22 08:38:13 +00002927 SVal loc = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00002928
2929 // Perform a load.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00002930 ExplodedNodeSet Tmp2;
Zhongxing Xu250704b2010-12-22 08:38:13 +00002931 evalLoad(Tmp2, Ex, *I, state, loc);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00002932
Zhongxing Xubb141212009-12-16 11:27:52 +00002933 for (ExplodedNodeSet::iterator I2=Tmp2.begin(), E2=Tmp2.end();I2!=E2;++I2) {
Mike Stump1eb44332009-09-09 15:08:12 +00002934
Ted Kremeneka8538d92009-02-13 01:45:31 +00002935 state = GetState(*I2);
Ted Kremenek13976632010-02-08 16:18:51 +00002936 SVal V2_untested = state->getSVal(Ex);
Mike Stump1eb44332009-09-09 15:08:12 +00002937
2938 // Propagate unknown and undefined values.
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002939 if (V2_untested.isUnknownOrUndef()) {
2940 MakeNode(Dst, U, *I2, state->BindExpr(U, V2_untested));
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00002941 continue;
Ted Kremenekb9bbd592010-02-15 23:02:46 +00002942 }
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002943 DefinedSVal V2 = cast<DefinedSVal>(V2_untested);
Mike Stump1eb44332009-09-09 15:08:12 +00002944
2945 // Handle all other values.
John McCall2de56d12010-08-25 11:45:40 +00002946 BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add
2947 : BO_Sub;
Ted Kremenek21028dd2009-03-11 03:54:24 +00002948
Zhongxing Xua52ad4e2009-08-05 02:51:59 +00002949 // If the UnaryOperator has non-location type, use its type to create the
2950 // constant value. If the UnaryOperator has location type, create the
2951 // constant with int type and pointer width.
2952 SVal RHS;
2953
2954 if (U->getType()->isAnyPointerType())
Ted Kremeneka6b0b962010-12-24 08:39:33 +00002955 RHS = svalBuilder.makeArrayIndex(1);
Zhongxing Xua52ad4e2009-08-05 02:51:59 +00002956 else
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002957 RHS = svalBuilder.makeIntVal(1, U->getType());
Zhongxing Xua52ad4e2009-08-05 02:51:59 +00002958
Ted Kremenek9c149532010-12-01 21:57:22 +00002959 SVal Result = evalBinOp(state, Op, V2, RHS, U->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00002960
Ted Kremenekbb9b2712009-03-20 20:10:45 +00002961 // Conjure a new symbol if necessary to recover precision.
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002962 if (Result.isUnknown() || !getConstraintManager().canReasonAbout(Result)){
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002963 DefinedOrUnknownSVal SymVal =
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002964 svalBuilder.getConjuredSymbolVal(NULL, Ex,
Ted Kremenek87806792009-09-27 20:45:21 +00002965 Builder->getCurrentBlockCount());
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002966 Result = SymVal;
Mike Stump1eb44332009-09-09 15:08:12 +00002967
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002968 // If the value is a location, ++/-- should always preserve
Ted Kremenek6c07bdb2009-06-26 00:05:51 +00002969 // non-nullness. Check if the original value was non-null, and if so
Mike Stump1eb44332009-09-09 15:08:12 +00002970 // propagate that constraint.
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002971 if (Loc::IsLocType(U->getType())) {
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002972 DefinedOrUnknownSVal Constraint =
Zhongxing Xu250704b2010-12-22 08:38:13 +00002973 svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00002974
Ted Kremenek28f47b92010-12-01 22:16:56 +00002975 if (!state->assume(Constraint, true)) {
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002976 // It isn't feasible for the original value to be null.
2977 // Propagate this constraint.
Ted Kremenek9c149532010-12-01 21:57:22 +00002978 Constraint = svalBuilder.evalEQ(state, SymVal,
Ted Kremenekc8413fd2010-12-02 07:49:45 +00002979 svalBuilder.makeZeroVal(U->getType()));
Mike Stump1eb44332009-09-09 15:08:12 +00002980
Ted Kremenek5b9bd212009-09-11 22:07:28 +00002981
Ted Kremenek28f47b92010-12-01 22:16:56 +00002982 state = state->assume(Constraint, false);
Ted Kremeneka591bc02009-06-18 22:57:13 +00002983 assert(state);
Mike Stump1eb44332009-09-09 15:08:12 +00002984 }
2985 }
Ted Kremenekaf48fdd2009-04-21 22:38:05 +00002986 }
Mike Stump1eb44332009-09-09 15:08:12 +00002987
Zhongxing Xu250704b2010-12-22 08:38:13 +00002988 // Since the lvalue-to-rvalue conversion is explicit in the AST,
2989 // we bind an l-value if the operator is prefix and an lvalue (in C++).
Zhongxing Xub0862442011-01-10 03:22:57 +00002990 if (U->isLValue())
Zhongxing Xu250704b2010-12-22 08:38:13 +00002991 state = state->BindExpr(U, loc);
2992 else
2993 state = state->BindExpr(U, V2);
Ted Kremenekcf78b6a2008-02-06 22:50:25 +00002994
Mike Stump1eb44332009-09-09 15:08:12 +00002995 // Perform the store.
Zhongxing Xu250704b2010-12-22 08:38:13 +00002996 evalStore(Dst, NULL, U, *I2, state, loc, Result);
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00002997 }
Ted Kremenek469ecbd2008-04-21 23:43:38 +00002998 }
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00002999}
3000
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003001void ExprEngine::VisitAsmStmt(const AsmStmt* A, ExplodedNode* Pred,
Zhongxing Xubb141212009-12-16 11:27:52 +00003002 ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003003 VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst);
Mike Stump1eb44332009-09-09 15:08:12 +00003004}
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003005
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003006void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt* A,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003007 AsmStmt::const_outputs_iterator I,
3008 AsmStmt::const_outputs_iterator E,
Zhongxing Xubb141212009-12-16 11:27:52 +00003009 ExplodedNode* Pred, ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003010 if (I == E) {
3011 VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst);
3012 return;
3013 }
Mike Stump1eb44332009-09-09 15:08:12 +00003014
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003015 ExplodedNodeSet Tmp;
Ted Kremenek892697d2010-12-16 07:46:53 +00003016 Visit(*I, Pred, Tmp);
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003017 ++I;
Mike Stump1eb44332009-09-09 15:08:12 +00003018
Zhongxing Xubb141212009-12-16 11:27:52 +00003019 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI)
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003020 VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst);
3021}
3022
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003023void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt* A,
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003024 AsmStmt::const_inputs_iterator I,
3025 AsmStmt::const_inputs_iterator E,
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003026 ExplodedNode* Pred,
Zhongxing Xubb141212009-12-16 11:27:52 +00003027 ExplodedNodeSet& Dst) {
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003028 if (I == E) {
Mike Stump1eb44332009-09-09 15:08:12 +00003029
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003030 // We have processed both the inputs and the outputs. All of the outputs
Zhongxing Xu1c96b242008-10-17 05:57:07 +00003031 // should evaluate to Locs. Nuke all of their values.
Mike Stump1eb44332009-09-09 15:08:12 +00003032
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003033 // FIXME: Some day in the future it would be nice to allow a "plug-in"
3034 // which interprets the inline asm and stores proper results in the
3035 // outputs.
Mike Stump1eb44332009-09-09 15:08:12 +00003036
Ted Kremeneka8538d92009-02-13 01:45:31 +00003037 const GRState* state = GetState(Pred);
Mike Stump1eb44332009-09-09 15:08:12 +00003038
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003039 for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(),
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003040 OE = A->end_outputs(); OI != OE; ++OI) {
Mike Stump1eb44332009-09-09 15:08:12 +00003041
Ted Kremenek13976632010-02-08 16:18:51 +00003042 SVal X = state->getSVal(*OI);
Zhongxing Xu1c96b242008-10-17 05:57:07 +00003043 assert (!isa<NonLoc>(X)); // Should be an Lval, or unknown, undef.
Mike Stump1eb44332009-09-09 15:08:12 +00003044
Zhongxing Xu1c96b242008-10-17 05:57:07 +00003045 if (isa<Loc>(X))
Ted Kremenek3ff12592009-06-19 17:10:32 +00003046 state = state->bindLoc(cast<Loc>(X), UnknownVal());
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003047 }
Mike Stump1eb44332009-09-09 15:08:12 +00003048
Ted Kremeneka8538d92009-02-13 01:45:31 +00003049 MakeNode(Dst, A, Pred, state);
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003050 return;
3051 }
Mike Stump1eb44332009-09-09 15:08:12 +00003052
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003053 ExplodedNodeSet Tmp;
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003054 Visit(*I, Pred, Tmp);
Mike Stump1eb44332009-09-09 15:08:12 +00003055
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003056 ++I;
Mike Stump1eb44332009-09-09 15:08:12 +00003057
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00003058 for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI)
Ted Kremenekef44bfb2008-03-17 21:11:24 +00003059 VisitAsmStmtHelperInputs(A, I, E, *NI, Dst);
3060}
3061
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003062void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
Ted Kremenek1053d242009-11-06 02:24:13 +00003063 ExplodedNodeSet &Dst) {
Ted Kremenek1053d242009-11-06 02:24:13 +00003064 ExplodedNodeSet Src;
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003065 if (const Expr *RetE = RS->getRetValue()) {
Zhongxing Xubd2b2082010-03-23 08:09:29 +00003066 // Record the returned expression in the state. It will be used in
3067 // ProcessCallExit to bind the return value to the call expr.
Zhongxing Xu6190ec22010-02-26 15:43:34 +00003068 {
Ted Kremeneka804a682010-03-02 21:43:52 +00003069 static int Tag = 0;
3070 SaveAndRestore<const void *> OldTag(Builder->Tag, &Tag);
Zhongxing Xu6190ec22010-02-26 15:43:34 +00003071 const GRState *state = GetState(Pred);
3072 state = state->set<ReturnExpr>(RetE);
3073 Pred = Builder->generateNode(RetE, state, Pred);
3074 }
3075 // We may get a NULL Pred because we generated a cached node.
3076 if (Pred)
3077 Visit(RetE, Pred, Src);
Ted Kremenek02737ed2008-03-31 15:02:58 +00003078 }
Ted Kremenek1053d242009-11-06 02:24:13 +00003079 else {
3080 Src.Add(Pred);
3081 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003082
Ted Kremenek1053d242009-11-06 02:24:13 +00003083 ExplodedNodeSet CheckedSet;
Jordy Rose72905cf2010-08-04 07:10:57 +00003084 CheckerVisit(RS, CheckedSet, Src, PreVisitStmtCallback);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003085
Ted Kremenek1053d242009-11-06 02:24:13 +00003086 for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
3087 I != E; ++I) {
Ted Kremenek6b31e8e2008-04-16 23:05:51 +00003088
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003089 assert(Builder && "StmtNodeBuilder must be defined.");
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003090
Ted Kremenek1053d242009-11-06 02:24:13 +00003091 Pred = *I;
3092 unsigned size = Dst.size();
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003093
Ted Kremenek1053d242009-11-06 02:24:13 +00003094 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
3095 SaveOr OldHasGen(Builder->HasGeneratedNode);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003096
Ted Kremenek9c149532010-12-01 21:57:22 +00003097 getTF().evalReturn(Dst, *this, *Builder, RS, Pred);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003098
3099 // Handle the case where no nodes where generated.
3100 if (!Builder->BuildSinks && Dst.size() == size &&
Ted Kremenek1053d242009-11-06 02:24:13 +00003101 !Builder->HasGeneratedNode)
3102 MakeNode(Dst, RS, Pred, GetState(Pred));
Ted Kremenek5917d782008-11-21 00:27:44 +00003103 }
Ted Kremenek02737ed2008-03-31 15:02:58 +00003104}
Ted Kremenek55deb972008-03-25 00:34:37 +00003105
Ted Kremeneke695e1c2008-04-15 23:06:53 +00003106//===----------------------------------------------------------------------===//
3107// Transfer functions: Binary operators.
3108//===----------------------------------------------------------------------===//
3109
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003110void ExprEngine::VisitBinaryOperator(const BinaryOperator* B,
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003111 ExplodedNode* Pred,
Ted Kremenek892697d2010-12-16 07:46:53 +00003112 ExplodedNodeSet& Dst) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003113 ExplodedNodeSet Tmp1;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003114 Expr* LHS = B->getLHS()->IgnoreParens();
3115 Expr* RHS = B->getRHS()->IgnoreParens();
Mike Stump1eb44332009-09-09 15:08:12 +00003116
Ted Kremenek892697d2010-12-16 07:46:53 +00003117 Visit(LHS, Pred, Tmp1);
Zhongxing Xu668399b2009-11-24 08:24:26 +00003118 ExplodedNodeSet Tmp3;
3119
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00003120 for (ExplodedNodeSet::iterator I1=Tmp1.begin(), E1=Tmp1.end(); I1!=E1; ++I1) {
Zhongxing Xu59fea602010-04-20 04:53:09 +00003121 SVal LeftV = GetState(*I1)->getSVal(LHS);
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003122 ExplodedNodeSet Tmp2;
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003123 Visit(RHS, *I1, Tmp2);
Zhongxing Xu6403b572009-09-02 13:26:26 +00003124
3125 ExplodedNodeSet CheckedSet;
Jordy Rose72905cf2010-08-04 07:10:57 +00003126 CheckerVisit(B, CheckedSet, Tmp2, PreVisitStmtCallback);
Mike Stump1eb44332009-09-09 15:08:12 +00003127
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003128 // With both the LHS and RHS evaluated, process the operation itself.
Mike Stump1eb44332009-09-09 15:08:12 +00003129
3130 for (ExplodedNodeSet::iterator I2=CheckedSet.begin(), E2=CheckedSet.end();
Zhongxing Xu6403b572009-09-02 13:26:26 +00003131 I2 != E2; ++I2) {
Ted Kremenekaa1c4e52008-02-21 18:02:17 +00003132
Ted Kremenek5b9bd212009-09-11 22:07:28 +00003133 const GRState *state = GetState(*I2);
Ted Kremenek13976632010-02-08 16:18:51 +00003134 SVal RightV = state->getSVal(RHS);
Ted Kremenek5b9bd212009-09-11 22:07:28 +00003135
Ted Kremenekcf78b6a2008-02-06 22:50:25 +00003136 BinaryOperator::Opcode Op = B->getOpcode();
Mike Stump1eb44332009-09-09 15:08:12 +00003137
John McCall2de56d12010-08-25 11:45:40 +00003138 if (Op == BO_Assign) {
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003139 // EXPERIMENTAL: "Conjured" symbols.
3140 // FIXME: Handle structs.
3141 QualType T = RHS->getType();
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003142
Ted Kremenek0e82a932010-07-29 00:28:33 +00003143 if (RightV.isUnknown() ||!getConstraintManager().canReasonAbout(RightV))
3144 {
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003145 unsigned Count = Builder->getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +00003146 RightV = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), Count);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003147 }
Zhongxing Xu662174ca2009-10-30 07:19:39 +00003148
Ted Kremenek892697d2010-12-16 07:46:53 +00003149 SVal ExprVal = B->isLValue() ? LeftV : RightV;
Zhongxing Xu662174ca2009-10-30 07:19:39 +00003150
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003151 // Simulate the effects of a "store": bind the value of the RHS
3152 // to the L-Value represented by the LHS.
Ted Kremenek9c149532010-12-01 21:57:22 +00003153 evalStore(Tmp3, B, LHS, *I2, state->BindExpr(B, ExprVal), LeftV,RightV);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003154 continue;
3155 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003156
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003157 if (!B->isAssignmentOp()) {
3158 // Process non-assignments except commas or short-circuited
3159 // logical expressions (LAnd and LOr).
Ted Kremenek9c149532010-12-01 21:57:22 +00003160 SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType());
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003161
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003162 if (Result.isUnknown()) {
Ted Kremenek96ebad62010-09-09 07:13:00 +00003163 MakeNode(Tmp3, B, *I2, state);
Ted Kremeneke38718e2008-04-16 18:21:25 +00003164 continue;
Ted Kremenekab2b8c52008-01-23 19:59:44 +00003165 }
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003166
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003167 state = state->BindExpr(B, Result);
Ted Kremenekb9bbd592010-02-15 23:02:46 +00003168
Zhongxing Xu668399b2009-11-24 08:24:26 +00003169 MakeNode(Tmp3, B, *I2, state);
Zhongxing Xu73af2d52009-10-21 11:42:22 +00003170 continue;
Ted Kremenekab2b8c52008-01-23 19:59:44 +00003171 }
Mike Stump1eb44332009-09-09 15:08:12 +00003172
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003173 assert (B->isCompoundAssignmentOp());
3174
Ted Kremenekcad29962009-02-07 00:52:24 +00003175 switch (Op) {
3176 default:
3177 assert(0 && "Invalid opcode for compound assignment.");
John McCall2de56d12010-08-25 11:45:40 +00003178 case BO_MulAssign: Op = BO_Mul; break;
3179 case BO_DivAssign: Op = BO_Div; break;
3180 case BO_RemAssign: Op = BO_Rem; break;
3181 case BO_AddAssign: Op = BO_Add; break;
3182 case BO_SubAssign: Op = BO_Sub; break;
3183 case BO_ShlAssign: Op = BO_Shl; break;
3184 case BO_ShrAssign: Op = BO_Shr; break;
3185 case BO_AndAssign: Op = BO_And; break;
3186 case BO_XorAssign: Op = BO_Xor; break;
3187 case BO_OrAssign: Op = BO_Or; break;
Ted Kremenek934e3e92008-10-27 23:02:39 +00003188 }
Mike Stump1eb44332009-09-09 15:08:12 +00003189
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003190 // Perform a load (the LHS). This performs the checks for
3191 // null dereferences, and so on.
Zhongxing Xuc39b2bd2010-01-19 09:25:53 +00003192 ExplodedNodeSet Tmp4;
Ted Kremenek13976632010-02-08 16:18:51 +00003193 SVal location = state->getSVal(LHS);
Ted Kremenek9c149532010-12-01 21:57:22 +00003194 evalLoad(Tmp4, LHS, *I2, state, location);
Mike Stump1eb44332009-09-09 15:08:12 +00003195
Zhongxing Xuc39b2bd2010-01-19 09:25:53 +00003196 for (ExplodedNodeSet::iterator I4=Tmp4.begin(), E4=Tmp4.end(); I4!=E4;
3197 ++I4) {
3198 state = GetState(*I4);
Ted Kremenek13976632010-02-08 16:18:51 +00003199 SVal V = state->getSVal(LHS);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003200
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003201 // Get the computation type.
Ted Kremenek32c3fa42009-07-21 21:03:30 +00003202 QualType CTy =
3203 cast<CompoundAssignOperator>(B)->getComputationResultType();
Ted Kremenek60595da2008-11-15 04:01:56 +00003204 CTy = getContext().getCanonicalType(CTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00003205
Ted Kremenek32c3fa42009-07-21 21:03:30 +00003206 QualType CLHSTy =
3207 cast<CompoundAssignOperator>(B)->getComputationLHSType();
3208 CLHSTy = getContext().getCanonicalType(CLHSTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00003209
Ted Kremenek60595da2008-11-15 04:01:56 +00003210 QualType LTy = getContext().getCanonicalType(LHS->getType());
3211 QualType RTy = getContext().getCanonicalType(RHS->getType());
Eli Friedmanab3a8522009-03-28 01:22:36 +00003212
3213 // Promote LHS.
Ted Kremenek9c149532010-12-01 21:57:22 +00003214 V = svalBuilder.evalCast(V, CLHSTy, LTy);
Eli Friedmanab3a8522009-03-28 01:22:36 +00003215
Mike Stump1eb44332009-09-09 15:08:12 +00003216 // Compute the result of the operation.
Ted Kremenek9c149532010-12-01 21:57:22 +00003217 SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy),
Zhongxing Xu814e6b92010-02-04 04:56:43 +00003218 B->getType(), CTy);
Mike Stump1eb44332009-09-09 15:08:12 +00003219
Ted Kremenek9ff267d2008-10-20 23:13:25 +00003220 // EXPERIMENTAL: "Conjured" symbols.
3221 // FIXME: Handle structs.
Mike Stump1eb44332009-09-09 15:08:12 +00003222
Ted Kremenek60595da2008-11-15 04:01:56 +00003223 SVal LHSVal;
Mike Stump1eb44332009-09-09 15:08:12 +00003224
Ted Kremenek0e82a932010-07-29 00:28:33 +00003225 if (Result.isUnknown() ||
3226 !getConstraintManager().canReasonAbout(Result)) {
Mike Stump1eb44332009-09-09 15:08:12 +00003227
Ted Kremenek9ff267d2008-10-20 23:13:25 +00003228 unsigned Count = Builder->getCurrentBlockCount();
Mike Stump1eb44332009-09-09 15:08:12 +00003229
Ted Kremenek60595da2008-11-15 04:01:56 +00003230 // The symbolic value is actually for the type of the left-hand side
3231 // expression, not the computation type, as this is the value the
3232 // LValue on the LHS will bind to.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00003233 LHSVal = svalBuilder.getConjuredSymbolVal(NULL, B->getRHS(), LTy, Count);
Mike Stump1eb44332009-09-09 15:08:12 +00003234
Zhongxing Xu1c0c2332008-11-23 05:52:28 +00003235 // However, we need to convert the symbol to the computation type.
Ted Kremenek9c149532010-12-01 21:57:22 +00003236 Result = svalBuilder.evalCast(LHSVal, CTy, LTy);
Ted Kremenek9ff267d2008-10-20 23:13:25 +00003237 }
Ted Kremenek60595da2008-11-15 04:01:56 +00003238 else {
3239 // The left-hand side may bind to a different value then the
3240 // computation type.
Ted Kremenek9c149532010-12-01 21:57:22 +00003241 LHSVal = svalBuilder.evalCast(Result, LTy, CTy);
Ted Kremenek60595da2008-11-15 04:01:56 +00003242 }
Mike Stump1eb44332009-09-09 15:08:12 +00003243
Zhongxing Xuf9d3cbb2011-01-10 03:54:19 +00003244 // In C++, assignment and compound assignment operators return an
3245 // lvalue.
3246 if (B->isLValue())
3247 state = state->BindExpr(B, location);
3248 else
3249 state = state->BindExpr(B, Result);
3250
3251 evalStore(Tmp3, B, LHS, *I4, state, location, LHSVal);
Ted Kremenek1b8bd4d2008-04-29 21:04:26 +00003252 }
Ted Kremenekcb448ca2008-01-16 00:53:15 +00003253 }
Ted Kremenekd27f8162008-01-15 23:55:06 +00003254 }
Zhongxing Xu668399b2009-11-24 08:24:26 +00003255
Jordy Rose72905cf2010-08-04 07:10:57 +00003256 CheckerVisit(B, Dst, Tmp3, PostVisitStmtCallback);
Ted Kremenekd27f8162008-01-15 23:55:06 +00003257}
Ted Kremenekee985462008-01-16 18:18:48 +00003258
3259//===----------------------------------------------------------------------===//
Ted Kremenek094bef52009-10-30 17:47:32 +00003260// Checker registration/lookup.
3261//===----------------------------------------------------------------------===//
3262
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003263Checker *ExprEngine::lookupChecker(void *tag) const {
Jeffrey Yasskin3958b502009-11-10 01:17:45 +00003264 CheckerMap::const_iterator I = CheckerM.find(tag);
Ted Kremenek094bef52009-10-30 17:47:32 +00003265 return (I == CheckerM.end()) ? NULL : Checkers[I->second].second;
3266}
3267
3268//===----------------------------------------------------------------------===//
Ted Kremeneke01c9872008-02-14 22:36:46 +00003269// Visualization.
Ted Kremenekee985462008-01-16 18:18:48 +00003270//===----------------------------------------------------------------------===//
3271
Ted Kremenekaa66a322008-01-16 21:46:15 +00003272#ifndef NDEBUG
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003273static ExprEngine* GraphPrintCheckerState;
Ted Kremeneke97ca062008-03-07 20:57:30 +00003274static SourceManager* GraphPrintSourceManager;
Ted Kremenek3b4f6702008-01-30 23:24:39 +00003275
Ted Kremenekaa66a322008-01-16 21:46:15 +00003276namespace llvm {
3277template<>
Douglas Gregor47491f82009-11-30 16:08:24 +00003278struct DOTGraphTraits<ExplodedNode*> :
Ted Kremenekaa66a322008-01-16 21:46:15 +00003279 public DefaultDOTGraphTraits {
Tobias Grosser006b0eb2009-11-30 14:16:05 +00003280
3281 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
3282
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003283 // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
Zhongxing Xuec9227f2009-10-29 02:09:30 +00003284 // work.
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003285 static std::string getNodeAttributes(const ExplodedNode* N, void*) {
Mike Stump1eb44332009-09-09 15:08:12 +00003286
Ted Kremenek10f51e82009-11-11 20:16:36 +00003287#if 0
3288 // FIXME: Replace with a general scheme to tell if the node is
3289 // an error node.
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00003290 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
Ted Kremenek9dca0622008-02-19 00:22:37 +00003291 GraphPrintCheckerState->isExplicitNullDeref(N) ||
Ted Kremenek4a4e5242008-02-28 09:25:22 +00003292 GraphPrintCheckerState->isUndefDeref(N) ||
3293 GraphPrintCheckerState->isUndefStore(N) ||
3294 GraphPrintCheckerState->isUndefControlFlow(N) ||
Ted Kremenek5e03fcb2008-02-29 23:14:48 +00003295 GraphPrintCheckerState->isUndefResult(N) ||
Ted Kremenek2ded35a2008-02-29 23:53:11 +00003296 GraphPrintCheckerState->isBadCall(N) ||
3297 GraphPrintCheckerState->isUndefArg(N))
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00003298 return "color=\"red\",style=\"filled\"";
Mike Stump1eb44332009-09-09 15:08:12 +00003299
Ted Kremenek8cc13ea2008-02-28 20:32:03 +00003300 if (GraphPrintCheckerState->isNoReturnCall(N))
3301 return "color=\"blue\",style=\"filled\"";
Zhongxing Xu2055eff2009-11-24 07:06:39 +00003302#endif
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00003303 return "";
3304 }
Mike Stump1eb44332009-09-09 15:08:12 +00003305
Tobias Grosser006b0eb2009-11-30 14:16:05 +00003306 static std::string getNodeLabel(const ExplodedNode* N, void*){
Mike Stump1eb44332009-09-09 15:08:12 +00003307
Ted Kremenek53ba0b62009-06-24 23:06:47 +00003308 std::string sbuf;
3309 llvm::raw_string_ostream Out(sbuf);
Ted Kremenek803c9ed2008-01-23 22:30:44 +00003310
3311 // Program Location.
Ted Kremenekaa66a322008-01-16 21:46:15 +00003312 ProgramPoint Loc = N->getLocation();
Mike Stump1eb44332009-09-09 15:08:12 +00003313
Ted Kremenekaa66a322008-01-16 21:46:15 +00003314 switch (Loc.getKind()) {
3315 case ProgramPoint::BlockEntranceKind:
Mike Stump1eb44332009-09-09 15:08:12 +00003316 Out << "Block Entrance: B"
Ted Kremenekaa66a322008-01-16 21:46:15 +00003317 << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
3318 break;
Mike Stump1eb44332009-09-09 15:08:12 +00003319
Ted Kremenekaa66a322008-01-16 21:46:15 +00003320 case ProgramPoint::BlockExitKind:
3321 assert (false);
3322 break;
Mike Stump1eb44332009-09-09 15:08:12 +00003323
Douglas Gregor102acd52010-02-25 19:01:53 +00003324 case ProgramPoint::CallEnterKind:
3325 Out << "CallEnter";
3326 break;
3327
3328 case ProgramPoint::CallExitKind:
3329 Out << "CallExit";
3330 break;
3331
Ted Kremenekaa66a322008-01-16 21:46:15 +00003332 default: {
Ted Kremenek5f85e172009-07-22 22:35:28 +00003333 if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) {
3334 const Stmt* S = L->getStmt();
Ted Kremenek8c354752008-12-16 22:02:27 +00003335 SourceLocation SLoc = S->getLocStart();
3336
Mike Stump1eb44332009-09-09 15:08:12 +00003337 Out << S->getStmtClassName() << ' ' << (void*) S << ' ';
Chris Lattnere4f21422009-06-30 01:26:17 +00003338 LangOptions LO; // FIXME.
3339 S->printPretty(Out, 0, PrintingPolicy(LO));
Mike Stump1eb44332009-09-09 15:08:12 +00003340
3341 if (SLoc.isFileID()) {
Ted Kremenek8c354752008-12-16 22:02:27 +00003342 Out << "\\lline="
Chris Lattner7da5aea2009-02-04 00:55:58 +00003343 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc)
3344 << " col="
3345 << GraphPrintSourceManager->getInstantiationColumnNumber(SLoc)
3346 << "\\l";
Ted Kremenek8c354752008-12-16 22:02:27 +00003347 }
Mike Stump1eb44332009-09-09 15:08:12 +00003348
Ted Kremenek5f85e172009-07-22 22:35:28 +00003349 if (isa<PreStmt>(Loc))
Mike Stump1eb44332009-09-09 15:08:12 +00003350 Out << "\\lPreStmt\\l;";
Ted Kremenek5f85e172009-07-22 22:35:28 +00003351 else if (isa<PostLoad>(Loc))
Ted Kremenek7090d542009-05-07 18:27:16 +00003352 Out << "\\lPostLoad\\l;";
3353 else if (isa<PostStore>(Loc))
3354 Out << "\\lPostStore\\l";
3355 else if (isa<PostLValue>(Loc))
3356 Out << "\\lPostLValue\\l";
Mike Stump1eb44332009-09-09 15:08:12 +00003357
Ted Kremenek10f51e82009-11-11 20:16:36 +00003358#if 0
3359 // FIXME: Replace with a general scheme to determine
3360 // the name of the check.
Ted Kremenek8c354752008-12-16 22:02:27 +00003361 if (GraphPrintCheckerState->isImplicitNullDeref(N))
3362 Out << "\\|Implicit-Null Dereference.\\l";
3363 else if (GraphPrintCheckerState->isExplicitNullDeref(N))
3364 Out << "\\|Explicit-Null Dereference.\\l";
3365 else if (GraphPrintCheckerState->isUndefDeref(N))
3366 Out << "\\|Dereference of undefialied value.\\l";
3367 else if (GraphPrintCheckerState->isUndefStore(N))
3368 Out << "\\|Store to Undefined Loc.";
Ted Kremenek8c354752008-12-16 22:02:27 +00003369 else if (GraphPrintCheckerState->isUndefResult(N))
3370 Out << "\\|Result of operation is undefined.";
3371 else if (GraphPrintCheckerState->isNoReturnCall(N))
3372 Out << "\\|Call to function marked \"noreturn\".";
3373 else if (GraphPrintCheckerState->isBadCall(N))
3374 Out << "\\|Call to NULL/Undefined.";
3375 else if (GraphPrintCheckerState->isUndefArg(N))
3376 Out << "\\|Argument in call is undefined";
Ted Kremenek10f51e82009-11-11 20:16:36 +00003377#endif
Mike Stump1eb44332009-09-09 15:08:12 +00003378
Ted Kremenek8c354752008-12-16 22:02:27 +00003379 break;
3380 }
3381
Ted Kremenekaa66a322008-01-16 21:46:15 +00003382 const BlockEdge& E = cast<BlockEdge>(Loc);
3383 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
3384 << E.getDst()->getBlockID() << ')';
Mike Stump1eb44332009-09-09 15:08:12 +00003385
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003386 if (const Stmt* T = E.getSrc()->getTerminator()) {
Mike Stump1eb44332009-09-09 15:08:12 +00003387
Ted Kremeneke97ca062008-03-07 20:57:30 +00003388 SourceLocation SLoc = T->getLocStart();
Mike Stump1eb44332009-09-09 15:08:12 +00003389
Ted Kremenekb38911f2008-01-30 23:03:39 +00003390 Out << "\\|Terminator: ";
Chris Lattnere4f21422009-06-30 01:26:17 +00003391 LangOptions LO; // FIXME.
3392 E.getSrc()->printTerminator(Out, LO);
Mike Stump1eb44332009-09-09 15:08:12 +00003393
Ted Kremenek9b5551d2008-03-09 03:30:59 +00003394 if (SLoc.isFileID()) {
3395 Out << "\\lline="
Chris Lattner7da5aea2009-02-04 00:55:58 +00003396 << GraphPrintSourceManager->getInstantiationLineNumber(SLoc)
3397 << " col="
3398 << GraphPrintSourceManager->getInstantiationColumnNumber(SLoc);
Ted Kremenek9b5551d2008-03-09 03:30:59 +00003399 }
Mike Stump1eb44332009-09-09 15:08:12 +00003400
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003401 if (isa<SwitchStmt>(T)) {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003402 const Stmt* Label = E.getDst()->getLabel();
Mike Stump1eb44332009-09-09 15:08:12 +00003403
3404 if (Label) {
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003405 if (const CaseStmt* C = dyn_cast<CaseStmt>(Label)) {
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003406 Out << "\\lcase ";
Chris Lattnere4f21422009-06-30 01:26:17 +00003407 LangOptions LO; // FIXME.
3408 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
Mike Stump1eb44332009-09-09 15:08:12 +00003409
Zhongxing Xu03509ae2010-07-20 06:22:24 +00003410 if (const Stmt* RHS = C->getRHS()) {
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003411 Out << " .. ";
Chris Lattnere4f21422009-06-30 01:26:17 +00003412 RHS->printPretty(Out, 0, PrintingPolicy(LO));
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003413 }
Mike Stump1eb44332009-09-09 15:08:12 +00003414
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003415 Out << ":";
3416 }
3417 else {
3418 assert (isa<DefaultStmt>(Label));
3419 Out << "\\ldefault:";
3420 }
3421 }
Mike Stump1eb44332009-09-09 15:08:12 +00003422 else
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00003423 Out << "\\l(implicit) default:";
3424 }
3425 else if (isa<IndirectGotoStmt>(T)) {
Ted Kremenekb38911f2008-01-30 23:03:39 +00003426 // FIXME
3427 }
3428 else {
3429 Out << "\\lCondition: ";
3430 if (*E.getSrc()->succ_begin() == E.getDst())
3431 Out << "true";
3432 else
Mike Stump1eb44332009-09-09 15:08:12 +00003433 Out << "false";
Ted Kremenekb38911f2008-01-30 23:03:39 +00003434 }
Mike Stump1eb44332009-09-09 15:08:12 +00003435
Ted Kremenekb38911f2008-01-30 23:03:39 +00003436 Out << "\\l";
3437 }
Mike Stump1eb44332009-09-09 15:08:12 +00003438
Ted Kremenek10f51e82009-11-11 20:16:36 +00003439#if 0
3440 // FIXME: Replace with a general scheme to determine
3441 // the name of the check.
Ted Kremenek4a4e5242008-02-28 09:25:22 +00003442 if (GraphPrintCheckerState->isUndefControlFlow(N)) {
3443 Out << "\\|Control-flow based on\\lUndefined value.\\l";
Ted Kremenek3b4f6702008-01-30 23:24:39 +00003444 }
Ted Kremenek10f51e82009-11-11 20:16:36 +00003445#endif
Ted Kremenekaa66a322008-01-16 21:46:15 +00003446 }
3447 }
Mike Stump1eb44332009-09-09 15:08:12 +00003448
Ted Kremenekb65be702009-06-18 01:23:53 +00003449 const GRState *state = N->getState();
Ted Kremenek8673a682010-12-03 06:52:26 +00003450 Out << "\\|StateID: " << (void*) state
3451 << " NodeID: " << (void*) N << "\\|";
Zhongxing Xuc179a7f2010-03-05 04:45:36 +00003452 state->printDOT(Out, *N->getLocationContext()->getCFG());
Ted Kremenek803c9ed2008-01-23 22:30:44 +00003453 Out << "\\l";
Ted Kremenekaa66a322008-01-16 21:46:15 +00003454 return Out.str();
3455 }
3456};
Mike Stump1eb44332009-09-09 15:08:12 +00003457} // end llvm namespace
Ted Kremenekaa66a322008-01-16 21:46:15 +00003458#endif
3459
Ted Kremenekffe0f432008-03-07 22:58:01 +00003460#ifndef NDEBUG
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003461template <typename ITERATOR>
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003462ExplodedNode* GetGraphNode(ITERATOR I) { return *I; }
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003463
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003464template <> ExplodedNode*
3465GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
3466 (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003467 return I->first;
3468}
Ted Kremenekffe0f432008-03-07 22:58:01 +00003469#endif
3470
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003471void ExprEngine::ViewGraph(bool trim) {
Mike Stump1eb44332009-09-09 15:08:12 +00003472#ifndef NDEBUG
Ted Kremenekffe0f432008-03-07 22:58:01 +00003473 if (trim) {
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003474 std::vector<ExplodedNode*> Src;
Ted Kremenek940abcc2009-03-11 01:41:22 +00003475
3476 // Flush any outstanding reports to make sure we cover all the nodes.
3477 // This does not cause them to get displayed.
3478 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
3479 const_cast<BugType*>(*I)->FlushReports(BR);
3480
3481 // Iterate through the reports and get their nodes.
3482 for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I) {
Ted Kremeneke1ccccf2009-09-03 03:02:58 +00003483 for (BugType::const_iterator I2=(*I)->begin(), E2=(*I)->end();
Mike Stump1eb44332009-09-09 15:08:12 +00003484 I2!=E2; ++I2) {
Ted Kremenek940abcc2009-03-11 01:41:22 +00003485 const BugReportEquivClass& EQ = *I2;
3486 const BugReport &R = **EQ.begin();
Tom Care212f6d32010-09-16 03:50:38 +00003487 ExplodedNode *N = const_cast<ExplodedNode*>(R.getErrorNode());
Ted Kremenek940abcc2009-03-11 01:41:22 +00003488 if (N) Src.push_back(N);
3489 }
3490 }
Mike Stump1eb44332009-09-09 15:08:12 +00003491
Ted Kremenek7ec07fd2008-03-12 17:18:20 +00003492 ViewGraph(&Src[0], &Src[0]+Src.size());
Ted Kremenekffe0f432008-03-07 22:58:01 +00003493 }
Ted Kremenek493d7a22008-03-11 18:25:33 +00003494 else {
3495 GraphPrintCheckerState = this;
3496 GraphPrintSourceManager = &getContext().getSourceManager();
Ted Kremenekae6814e2008-08-13 21:24:49 +00003497
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003498 llvm::ViewGraph(*G.roots_begin(), "ExprEngine");
Mike Stump1eb44332009-09-09 15:08:12 +00003499
Ted Kremenek493d7a22008-03-11 18:25:33 +00003500 GraphPrintCheckerState = NULL;
3501 GraphPrintSourceManager = NULL;
3502 }
3503#endif
3504}
3505
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003506void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) {
Ted Kremenek493d7a22008-03-11 18:25:33 +00003507#ifndef NDEBUG
3508 GraphPrintCheckerState = this;
3509 GraphPrintSourceManager = &getContext().getSourceManager();
Mike Stump1eb44332009-09-09 15:08:12 +00003510
Zhongxing Xu031ccc02009-08-06 12:48:26 +00003511 std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first);
Ted Kremenek493d7a22008-03-11 18:25:33 +00003512
Ted Kremenekcf118d42009-02-04 23:49:09 +00003513 if (!TrimmedG.get())
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +00003514 llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
Ted Kremenekcf118d42009-02-04 23:49:09 +00003515 else
Argyrios Kyrtzidisd2592a32010-12-22 18:53:44 +00003516 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine");
Mike Stump1eb44332009-09-09 15:08:12 +00003517
Ted Kremenek3b4f6702008-01-30 23:24:39 +00003518 GraphPrintCheckerState = NULL;
Ted Kremeneke97ca062008-03-07 20:57:30 +00003519 GraphPrintSourceManager = NULL;
Ted Kremeneke01c9872008-02-14 22:36:46 +00003520#endif
Ted Kremenekee985462008-01-16 18:18:48 +00003521}