ExprEngine.cpp revision 3070e13dca5bbefa32acb80ce4a7b217a6220983 
1//=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines 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.
13//
14//===----------------------------------------------------------------------===//
15
16#include "clang/StaticAnalyzer/Core/CheckerManager.h"
17#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
20#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h"
21#include "clang/AST/CharUnits.h"
22#include "clang/AST/ParentMap.h"
23#include "clang/AST/StmtObjC.h"
24#include "clang/AST/DeclCXX.h"
25#include "clang/Basic/Builtins.h"
26#include "clang/Basic/SourceManager.h"
27#include "clang/Basic/PrettyStackTrace.h"
28#include "llvm/Support/raw_ostream.h"
29#include "llvm/ADT/ImmutableList.h"
30
31#ifndef NDEBUG
32#include "llvm/Support/GraphWriter.h"
33#endif
34
35using namespace clang;
36using namespace ento;
37using llvm::APSInt;
38
39//===----------------------------------------------------------------------===//
40// Utility functions.
41//===----------------------------------------------------------------------===//
42
43static inline Selector GetNullarySelector(const char* name, ASTContext &Ctx) {
44  IdentifierInfo* II = &Ctx.Idents.get(name);
45  return Ctx.Selectors.getSelector(0, &II);
46}
47
48//===----------------------------------------------------------------------===//
49// Engine construction and deletion.
50//===----------------------------------------------------------------------===//
51
52ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled)
53  : AMgr(mgr),
54    AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
55    Engine(*this),
56    G(Engine.getGraph()),
57    StateMgr(getContext(), mgr.getStoreManagerCreator(),
58             mgr.getConstraintManagerCreator(), G.getAllocator(),
59             *this),
60    SymMgr(StateMgr.getSymbolManager()),
61    svalBuilder(StateMgr.getSValBuilder()),
62    EntryNode(NULL),
63    currentStmt(NULL), currentStmtIdx(0), currentBuilderContext(0),
64    NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL),
65    RaiseSel(GetNullarySelector("raise", getContext())),
66    ObjCGCEnabled(gcEnabled), BR(mgr, *this) {
67
68  if (mgr.shouldEagerlyTrimExplodedGraph()) {
69    // Enable eager node reclaimation when constructing the ExplodedGraph.
70    G.enableNodeReclamation();
71  }
72}
73
74ExprEngine::~ExprEngine() {
75  BR.FlushReports();
76  delete [] NSExceptionInstanceRaiseSelectors;
77}
78
79//===----------------------------------------------------------------------===//
80// Utility methods.
81//===----------------------------------------------------------------------===//
82
83const ProgramState *ExprEngine::getInitialState(const LocationContext *InitLoc) {
84  const ProgramState *state = StateMgr.getInitialState(InitLoc);
85  const Decl *D = InitLoc->getDecl();
86
87  // Preconditions.
88  // FIXME: It would be nice if we had a more general mechanism to add
89  // such preconditions.  Some day.
90  do {
91
92    if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
93      // Precondition: the first argument of 'main' is an integer guaranteed
94      //  to be > 0.
95      const IdentifierInfo *II = FD->getIdentifier();
96      if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
97        break;
98
99      const ParmVarDecl *PD = FD->getParamDecl(0);
100      QualType T = PD->getType();
101      if (!T->isIntegerType())
102        break;
103
104      const MemRegion *R = state->getRegion(PD, InitLoc);
105      if (!R)
106        break;
107
108      SVal V = state->getSVal(loc::MemRegionVal(R));
109      SVal Constraint_untested = evalBinOp(state, BO_GT, V,
110                                           svalBuilder.makeZeroVal(T),
111                                           getContext().IntTy);
112
113      DefinedOrUnknownSVal *Constraint =
114        dyn_cast<DefinedOrUnknownSVal>(&Constraint_untested);
115
116      if (!Constraint)
117        break;
118
119      if (const ProgramState *newState = state->assume(*Constraint, true))
120        state = newState;
121    }
122    break;
123  }
124  while (0);
125
126  if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
127    // Precondition: 'self' is always non-null upon entry to an Objective-C
128    // method.
129    const ImplicitParamDecl *SelfD = MD->getSelfDecl();
130    const MemRegion *R = state->getRegion(SelfD, InitLoc);
131    SVal V = state->getSVal(loc::MemRegionVal(R));
132
133    if (const Loc *LV = dyn_cast<Loc>(&V)) {
134      // Assume that the pointer value in 'self' is non-null.
135      state = state->assume(*LV, true);
136      assert(state && "'self' cannot be null");
137    }
138  }
139
140  if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
141    if (!MD->isStatic()) {
142      // Precondition: 'this' is always non-null upon entry to the
143      // top-level function.  This is our starting assumption for
144      // analyzing an "open" program.
145      const StackFrameContext *SFC = InitLoc->getCurrentStackFrame();
146      if (SFC->getParent() == 0) {
147        loc::MemRegionVal L(getCXXThisRegion(MD, SFC));
148        SVal V = state->getSVal(L);
149        if (const Loc *LV = dyn_cast<Loc>(&V)) {
150          state = state->assume(*LV, true);
151          assert(state && "'this' cannot be null");
152        }
153      }
154    }
155  }
156
157  return state;
158}
159
160//===----------------------------------------------------------------------===//
161// Top-level transfer function logic (Dispatcher).
162//===----------------------------------------------------------------------===//
163
164/// evalAssume - Called by ConstraintManager. Used to call checker-specific
165///  logic for handling assumptions on symbolic values.
166const ProgramState *ExprEngine::processAssume(const ProgramState *state,
167                                              SVal cond, bool assumption) {
168  return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
169}
170
171bool ExprEngine::wantsRegionChangeUpdate(const ProgramState *state) {
172  return getCheckerManager().wantsRegionChangeUpdate(state);
173}
174
175const ProgramState *
176ExprEngine::processRegionChanges(const ProgramState *state,
177                            const StoreManager::InvalidatedSymbols *invalidated,
178                                 ArrayRef<const MemRegion *> Explicits,
179                                 ArrayRef<const MemRegion *> Regions) {
180  return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
181                                                         Explicits, Regions);
182}
183
184void ExprEngine::printState(raw_ostream &Out, const ProgramState *State,
185                            const char *NL, const char *Sep) {
186  getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep);
187}
188
189void ExprEngine::processEndWorklist(bool hasWorkRemaining) {
190  getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
191}
192
193void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
194                                   unsigned StmtIdx, NodeBuilderContext *Ctx) {
195  currentStmtIdx = StmtIdx;
196  currentBuilderContext = Ctx;
197
198  switch (E.getKind()) {
199    case CFGElement::Invalid:
200      llvm_unreachable("Unexpected CFGElement kind.");
201    case CFGElement::Statement:
202      ProcessStmt(const_cast<Stmt*>(E.getAs<CFGStmt>()->getStmt()), Pred);
203      return;
204    case CFGElement::Initializer:
205      ProcessInitializer(E.getAs<CFGInitializer>()->getInitializer(), Pred);
206      return;
207    case CFGElement::AutomaticObjectDtor:
208    case CFGElement::BaseDtor:
209    case CFGElement::MemberDtor:
210    case CFGElement::TemporaryDtor:
211      ProcessImplicitDtor(*E.getAs<CFGImplicitDtor>(), Pred);
212      return;
213  }
214  currentStmtIdx = 0;
215  currentBuilderContext = 0;
216}
217
218static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
219                                     const CFGStmt S,
220                                     const ExplodedNode *Pred,
221                                     const LocationContext *LC) {
222
223  // Are we never purging state values?
224  if (AMgr.getPurgeMode() == PurgeNone)
225    return false;
226
227  // Is this the beginning of a basic block?
228  if (isa<BlockEntrance>(Pred->getLocation()))
229    return true;
230
231  // Is this on a non-expression?
232  if (!isa<Expr>(S.getStmt()))
233    return true;
234
235  // Is this an expression that is consumed by another expression?  If so,
236  // postpone cleaning out the state.
237  ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
238  return !PM.isConsumedExpr(cast<Expr>(S.getStmt()));
239}
240
241void ExprEngine::ProcessStmt(const CFGStmt S,
242                             ExplodedNode *Pred) {
243  // TODO: Use RAII to remove the unnecessary, tagged nodes.
244  //RegisterCreatedNodes registerCreatedNodes(getGraph());
245
246  // Reclaim any unnecessary nodes in the ExplodedGraph.
247  G.reclaimRecentlyAllocatedNodes();
248  // Recycle any unused states in the ProgramStateManager.
249  StateMgr.recycleUnusedStates();
250
251  currentStmt = S.getStmt();
252  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
253                                currentStmt->getLocStart(),
254                                "Error evaluating statement");
255
256  EntryNode = Pred;
257
258  const ProgramState *EntryState = EntryNode->getState();
259  CleanedState = EntryState;
260
261  // Create the cleaned state.
262  const LocationContext *LC = EntryNode->getLocationContext();
263  SymbolReaper SymReaper(LC, currentStmt, SymMgr, getStoreManager());
264
265  if (shouldRemoveDeadBindings(AMgr, S, Pred, LC)) {
266    getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
267
268    const StackFrameContext *SFC = LC->getCurrentStackFrame();
269
270    // Create a state in which dead bindings are removed from the environment
271    // and the store. TODO: The function should just return new env and store,
272    // not a new state.
273    CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
274  }
275
276  // Process any special transfer function for dead symbols.
277  ExplodedNodeSet Tmp;
278  // A tag to track convenience transitions, which can be removed at cleanup.
279  static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node");
280
281  if (!SymReaper.hasDeadSymbols()) {
282    // Generate a CleanedNode that has the environment and store cleaned
283    // up. Since no symbols are dead, we can optimize and not clean out
284    // the constraint manager.
285    StmtNodeBuilder Bldr(Pred, Tmp, *currentBuilderContext);
286    Bldr.generateNode(currentStmt, EntryNode, CleanedState, false, &cleanupTag);
287
288  } else {
289    // Call checkers with the non-cleaned state so that they could query the
290    // values of the soon to be dead symbols.
291    ExplodedNodeSet CheckedSet;
292    getCheckerManager().runCheckersForDeadSymbols(CheckedSet, EntryNode,
293                                                 SymReaper, currentStmt, *this);
294
295    // For each node in CheckedSet, generate CleanedNodes that have the
296    // environment, the store, and the constraints cleaned up but have the
297    // user-supplied states as the predecessors.
298    StmtNodeBuilder Bldr(CheckedSet, Tmp, *currentBuilderContext);
299    for (ExplodedNodeSet::const_iterator
300          I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) {
301      const ProgramState *CheckerState = (*I)->getState();
302
303      // The constraint manager has not been cleaned up yet, so clean up now.
304      CheckerState = getConstraintManager().removeDeadBindings(CheckerState,
305                                                               SymReaper);
306
307      assert(StateMgr.haveEqualEnvironments(CheckerState, EntryState) &&
308        "Checkers are not allowed to modify the Environment as a part of "
309        "checkDeadSymbols processing.");
310      assert(StateMgr.haveEqualStores(CheckerState, EntryState) &&
311        "Checkers are not allowed to modify the Store as a part of "
312        "checkDeadSymbols processing.");
313
314      // Create a state based on CleanedState with CheckerState GDM and
315      // generate a transition to that state.
316      const ProgramState *CleanedCheckerSt =
317        StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
318      Bldr.generateNode(currentStmt, *I, CleanedCheckerSt, false, &cleanupTag,
319                        ProgramPoint::PostPurgeDeadSymbolsKind);
320    }
321  }
322
323  ExplodedNodeSet Dst;
324  for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) {
325    ExplodedNodeSet DstI;
326    // Visit the statement.
327    Visit(currentStmt, *I, DstI);
328    Dst.insert(DstI);
329  }
330
331  // Enqueue the new nodes onto the work list.
332  Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx);
333
334  // NULL out these variables to cleanup.
335  CleanedState = NULL;
336  EntryNode = NULL;
337  currentStmt = 0;
338}
339
340void ExprEngine::ProcessInitializer(const CFGInitializer Init,
341                                    ExplodedNode *Pred) {
342  ExplodedNodeSet Dst;
343
344  // We don't set EntryNode and currentStmt. And we don't clean up state.
345  const CXXCtorInitializer *BMI = Init.getInitializer();
346  const StackFrameContext *stackFrame =
347                           cast<StackFrameContext>(Pred->getLocationContext());
348  const CXXConstructorDecl *decl =
349                           cast<CXXConstructorDecl>(stackFrame->getDecl());
350  const CXXThisRegion *thisReg = getCXXThisRegion(decl, stackFrame);
351
352  SVal thisVal = Pred->getState()->getSVal(thisReg);
353
354  if (BMI->isAnyMemberInitializer()) {
355    ExplodedNodeSet AfterEval;
356
357    // Evaluate the initializer.
358    Visit(BMI->getInit(), Pred, AfterEval);
359
360    StmtNodeBuilder Bldr(AfterEval, Dst, *currentBuilderContext);
361    for (ExplodedNodeSet::iterator I = AfterEval.begin(),
362                                   E = AfterEval.end(); I != E; ++I){
363      ExplodedNode *P = *I;
364      const ProgramState *state = P->getState();
365
366      const FieldDecl *FD = BMI->getAnyMember();
367
368      SVal FieldLoc = state->getLValue(FD, thisVal);
369      SVal InitVal = state->getSVal(BMI->getInit(), Pred->getLocationContext());
370      state = state->bindLoc(FieldLoc, InitVal);
371
372      // Use a custom node building process.
373      PostInitializer PP(BMI, stackFrame);
374      // Builder automatically add the generated node to the deferred set,
375      // which are processed in the builder's dtor.
376      Bldr.generateNode(PP, P, state);
377    }
378  } else {
379    assert(BMI->isBaseInitializer());
380
381    // Get the base class declaration.
382    const CXXConstructExpr *ctorExpr = cast<CXXConstructExpr>(BMI->getInit());
383
384    // Create the base object region.
385    SVal baseVal =
386        getStoreManager().evalDerivedToBase(thisVal, ctorExpr->getType());
387    const MemRegion *baseReg = baseVal.getAsRegion();
388    assert(baseReg);
389
390    VisitCXXConstructExpr(ctorExpr, baseReg, Pred, Dst);
391  }
392
393  // Enqueue the new nodes onto the work list.
394  Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx);
395}
396
397void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
398                                     ExplodedNode *Pred) {
399  ExplodedNodeSet Dst;
400  switch (D.getKind()) {
401  case CFGElement::AutomaticObjectDtor:
402    ProcessAutomaticObjDtor(cast<CFGAutomaticObjDtor>(D), Pred, Dst);
403    break;
404  case CFGElement::BaseDtor:
405    ProcessBaseDtor(cast<CFGBaseDtor>(D), Pred, Dst);
406    break;
407  case CFGElement::MemberDtor:
408    ProcessMemberDtor(cast<CFGMemberDtor>(D), Pred, Dst);
409    break;
410  case CFGElement::TemporaryDtor:
411    ProcessTemporaryDtor(cast<CFGTemporaryDtor>(D), Pred, Dst);
412    break;
413  default:
414    llvm_unreachable("Unexpected dtor kind.");
415  }
416
417  // Enqueue the new nodes onto the work list.
418  Engine.enqueue(Dst, currentBuilderContext->getBlock(), currentStmtIdx);
419}
420
421void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
422                                         ExplodedNode *Pred,
423                                         ExplodedNodeSet &Dst) {
424  const ProgramState *state = Pred->getState();
425  const VarDecl *varDecl = Dtor.getVarDecl();
426
427  QualType varType = varDecl->getType();
428
429  if (const ReferenceType *refType = varType->getAs<ReferenceType>())
430    varType = refType->getPointeeType();
431
432  const CXXRecordDecl *recordDecl = varType->getAsCXXRecordDecl();
433  assert(recordDecl && "get CXXRecordDecl fail");
434  const CXXDestructorDecl *dtorDecl = recordDecl->getDestructor();
435
436  Loc dest = state->getLValue(varDecl, Pred->getLocationContext());
437
438  VisitCXXDestructor(dtorDecl, cast<loc::MemRegionVal>(dest).getRegion(),
439                     Dtor.getTriggerStmt(), Pred, Dst);
440}
441
442void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
443                                 ExplodedNode *Pred, ExplodedNodeSet &Dst) {}
444
445void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
446                                   ExplodedNode *Pred, ExplodedNodeSet &Dst) {}
447
448void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
449                                      ExplodedNode *Pred,
450                                      ExplodedNodeSet &Dst) {}
451
452void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
453                       ExplodedNodeSet &DstTop) {
454  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
455                                S->getLocStart(),
456                                "Error evaluating statement");
457  ExplodedNodeSet Dst;
458  StmtNodeBuilder Bldr(Pred, DstTop, *currentBuilderContext);
459
460  // Expressions to ignore.
461  if (const Expr *Ex = dyn_cast<Expr>(S))
462    S = Ex->IgnoreParens();
463
464  // FIXME: add metadata to the CFG so that we can disable
465  //  this check when we KNOW that there is no block-level subexpression.
466  //  The motivation is that this check requires a hashtable lookup.
467
468  if (S != currentStmt && Pred->getLocationContext()->getCFG()->isBlkExpr(S))
469    return;
470
471  switch (S->getStmtClass()) {
472    // C++ and ARC stuff we don't support yet.
473    case Expr::ObjCIndirectCopyRestoreExprClass:
474    case Stmt::CXXBindTemporaryExprClass:
475    case Stmt::CXXCatchStmtClass:
476    case Stmt::CXXDependentScopeMemberExprClass:
477    case Stmt::CXXPseudoDestructorExprClass:
478    case Stmt::CXXThrowExprClass:
479    case Stmt::CXXTryStmtClass:
480    case Stmt::CXXTypeidExprClass:
481    case Stmt::CXXUuidofExprClass:
482    case Stmt::CXXUnresolvedConstructExprClass:
483    case Stmt::CXXScalarValueInitExprClass:
484    case Stmt::DependentScopeDeclRefExprClass:
485    case Stmt::UnaryTypeTraitExprClass:
486    case Stmt::BinaryTypeTraitExprClass:
487    case Stmt::ArrayTypeTraitExprClass:
488    case Stmt::ExpressionTraitExprClass:
489    case Stmt::UnresolvedLookupExprClass:
490    case Stmt::UnresolvedMemberExprClass:
491    case Stmt::CXXNoexceptExprClass:
492    case Stmt::PackExpansionExprClass:
493    case Stmt::SubstNonTypeTemplateParmPackExprClass:
494    case Stmt::SEHTryStmtClass:
495    case Stmt::SEHExceptStmtClass:
496    case Stmt::SEHFinallyStmtClass: {
497      const ExplodedNode *node = Bldr.generateNode(S, Pred, Pred->getState());
498      Engine.addAbortedBlock(node, currentBuilderContext->getBlock());
499      break;
500    }
501
502    // We don't handle default arguments either yet, but we can fake it
503    // for now by just skipping them.
504    case Stmt::SubstNonTypeTemplateParmExprClass:
505    case Stmt::CXXDefaultArgExprClass:
506      break;
507
508    case Stmt::ParenExprClass:
509      llvm_unreachable("ParenExprs already handled.");
510    case Stmt::GenericSelectionExprClass:
511      llvm_unreachable("GenericSelectionExprs already handled.");
512    // Cases that should never be evaluated simply because they shouldn't
513    // appear in the CFG.
514    case Stmt::BreakStmtClass:
515    case Stmt::CaseStmtClass:
516    case Stmt::CompoundStmtClass:
517    case Stmt::ContinueStmtClass:
518    case Stmt::CXXForRangeStmtClass:
519    case Stmt::DefaultStmtClass:
520    case Stmt::DoStmtClass:
521    case Stmt::ForStmtClass:
522    case Stmt::GotoStmtClass:
523    case Stmt::IfStmtClass:
524    case Stmt::IndirectGotoStmtClass:
525    case Stmt::LabelStmtClass:
526    case Stmt::NoStmtClass:
527    case Stmt::NullStmtClass:
528    case Stmt::SwitchStmtClass:
529    case Stmt::WhileStmtClass:
530    case Expr::MSDependentExistsStmtClass:
531      llvm_unreachable("Stmt should not be in analyzer evaluation loop");
532      break;
533
534    case Stmt::GNUNullExprClass: {
535      // GNU __null is a pointer-width integer, not an actual pointer.
536      const ProgramState *state = Pred->getState();
537      state = state->BindExpr(S, Pred->getLocationContext(),
538                              svalBuilder.makeIntValWithPtrWidth(0, false));
539      Bldr.generateNode(S, Pred, state);
540      break;
541    }
542
543    case Stmt::ObjCAtSynchronizedStmtClass:
544      Bldr.takeNodes(Pred);
545      VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
546      Bldr.addNodes(Dst);
547      break;
548
549    case Stmt::ObjCPropertyRefExprClass:
550      // Implicitly handled by Environment::getSVal().
551      break;
552
553    case Stmt::ImplicitValueInitExprClass: {
554      const ProgramState *state = Pred->getState();
555      QualType ty = cast<ImplicitValueInitExpr>(S)->getType();
556      SVal val = svalBuilder.makeZeroVal(ty);
557      Bldr.generateNode(S, Pred, state->BindExpr(S, Pred->getLocationContext(),
558                                                 val));
559      break;
560    }
561
562    case Stmt::ExprWithCleanupsClass:
563      Bldr.takeNodes(Pred);
564      Visit(cast<ExprWithCleanups>(S)->getSubExpr(), Pred, Dst);
565      Bldr.addNodes(Dst);
566      break;
567
568    // Cases not handled yet; but will handle some day.
569    case Stmt::DesignatedInitExprClass:
570    case Stmt::ExtVectorElementExprClass:
571    case Stmt::ImaginaryLiteralClass:
572    case Stmt::ObjCAtCatchStmtClass:
573    case Stmt::ObjCAtFinallyStmtClass:
574    case Stmt::ObjCAtTryStmtClass:
575    case Stmt::ObjCAutoreleasePoolStmtClass:
576    case Stmt::ObjCEncodeExprClass:
577    case Stmt::ObjCIsaExprClass:
578    case Stmt::ObjCProtocolExprClass:
579    case Stmt::ObjCSelectorExprClass:
580    case Stmt::ObjCStringLiteralClass:
581    case Stmt::ParenListExprClass:
582    case Stmt::PredefinedExprClass:
583    case Stmt::ShuffleVectorExprClass:
584    case Stmt::VAArgExprClass:
585    case Stmt::CUDAKernelCallExprClass:
586    case Stmt::OpaqueValueExprClass:
587    case Stmt::AsTypeExprClass:
588    case Stmt::AtomicExprClass:
589        // Fall through.
590
591    // Cases we intentionally don't evaluate, since they don't need
592    // to be explicitly evaluated.
593    case Stmt::AddrLabelExprClass:
594    case Stmt::IntegerLiteralClass:
595    case Stmt::CharacterLiteralClass:
596    case Stmt::CXXBoolLiteralExprClass:
597    case Stmt::FloatingLiteralClass:
598    case Stmt::SizeOfPackExprClass:
599    case Stmt::CXXNullPtrLiteralExprClass:
600      // No-op. Simply propagate the current state unchanged.
601      break;
602
603    case Stmt::ArraySubscriptExprClass:
604      Bldr.takeNodes(Pred);
605      VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
606      Bldr.addNodes(Dst);
607      break;
608
609    case Stmt::AsmStmtClass:
610      Bldr.takeNodes(Pred);
611      VisitAsmStmt(cast<AsmStmt>(S), Pred, Dst);
612      Bldr.addNodes(Dst);
613      break;
614
615    case Stmt::BlockDeclRefExprClass: {
616      Bldr.takeNodes(Pred);
617      const BlockDeclRefExpr *BE = cast<BlockDeclRefExpr>(S);
618      VisitCommonDeclRefExpr(BE, BE->getDecl(), Pred, Dst);
619      Bldr.addNodes(Dst);
620      break;
621    }
622
623    case Stmt::BlockExprClass:
624      Bldr.takeNodes(Pred);
625      VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
626      Bldr.addNodes(Dst);
627      break;
628
629    case Stmt::BinaryOperatorClass: {
630      const BinaryOperator* B = cast<BinaryOperator>(S);
631      if (B->isLogicalOp()) {
632        Bldr.takeNodes(Pred);
633        VisitLogicalExpr(B, Pred, Dst);
634        Bldr.addNodes(Dst);
635        break;
636      }
637      else if (B->getOpcode() == BO_Comma) {
638        const ProgramState *state = Pred->getState();
639        Bldr.generateNode(B, Pred,
640                          state->BindExpr(B, Pred->getLocationContext(),
641                                          state->getSVal(B->getRHS(),
642                                                  Pred->getLocationContext())));
643        break;
644      }
645
646      Bldr.takeNodes(Pred);
647
648      if (AMgr.shouldEagerlyAssume() &&
649          (B->isRelationalOp() || B->isEqualityOp())) {
650        ExplodedNodeSet Tmp;
651        VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
652        evalEagerlyAssume(Dst, Tmp, cast<Expr>(S));
653      }
654      else
655        VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
656
657      Bldr.addNodes(Dst);
658      break;
659    }
660
661    case Stmt::CallExprClass:
662    case Stmt::CXXOperatorCallExprClass:
663    case Stmt::CXXMemberCallExprClass: {
664      Bldr.takeNodes(Pred);
665      VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
666      Bldr.addNodes(Dst);
667      break;
668    }
669
670    case Stmt::CXXTemporaryObjectExprClass:
671    case Stmt::CXXConstructExprClass: {
672      const CXXConstructExpr *C = cast<CXXConstructExpr>(S);
673      // For block-level CXXConstructExpr, we don't have a destination region.
674      // Let VisitCXXConstructExpr() create one.
675      Bldr.takeNodes(Pred);
676      VisitCXXConstructExpr(C, 0, Pred, Dst);
677      Bldr.addNodes(Dst);
678      break;
679    }
680
681    case Stmt::CXXNewExprClass: {
682      Bldr.takeNodes(Pred);
683      const CXXNewExpr *NE = cast<CXXNewExpr>(S);
684      VisitCXXNewExpr(NE, Pred, Dst);
685      Bldr.addNodes(Dst);
686      break;
687    }
688
689    case Stmt::CXXDeleteExprClass: {
690      Bldr.takeNodes(Pred);
691      const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S);
692      VisitCXXDeleteExpr(CDE, Pred, Dst);
693      Bldr.addNodes(Dst);
694      break;
695    }
696      // FIXME: ChooseExpr is really a constant.  We need to fix
697      //        the CFG do not model them as explicit control-flow.
698
699    case Stmt::ChooseExprClass: { // __builtin_choose_expr
700      Bldr.takeNodes(Pred);
701      const ChooseExpr *C = cast<ChooseExpr>(S);
702      VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
703      Bldr.addNodes(Dst);
704      break;
705    }
706
707    case Stmt::CompoundAssignOperatorClass:
708      Bldr.takeNodes(Pred);
709      VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
710      Bldr.addNodes(Dst);
711      break;
712
713    case Stmt::CompoundLiteralExprClass:
714      Bldr.takeNodes(Pred);
715      VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
716      Bldr.addNodes(Dst);
717      break;
718
719    case Stmt::BinaryConditionalOperatorClass:
720    case Stmt::ConditionalOperatorClass: { // '?' operator
721      Bldr.takeNodes(Pred);
722      const AbstractConditionalOperator *C
723        = cast<AbstractConditionalOperator>(S);
724      VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
725      Bldr.addNodes(Dst);
726      break;
727    }
728
729    case Stmt::CXXThisExprClass:
730      Bldr.takeNodes(Pred);
731      VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
732      Bldr.addNodes(Dst);
733      break;
734
735    case Stmt::DeclRefExprClass: {
736      Bldr.takeNodes(Pred);
737      const DeclRefExpr *DE = cast<DeclRefExpr>(S);
738      VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
739      Bldr.addNodes(Dst);
740      break;
741    }
742
743    case Stmt::DeclStmtClass:
744      Bldr.takeNodes(Pred);
745      VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
746      Bldr.addNodes(Dst);
747      break;
748
749    case Stmt::ImplicitCastExprClass:
750    case Stmt::CStyleCastExprClass:
751    case Stmt::CXXStaticCastExprClass:
752    case Stmt::CXXDynamicCastExprClass:
753    case Stmt::CXXReinterpretCastExprClass:
754    case Stmt::CXXConstCastExprClass:
755    case Stmt::CXXFunctionalCastExprClass:
756    case Stmt::ObjCBridgedCastExprClass: {
757      Bldr.takeNodes(Pred);
758      const CastExpr *C = cast<CastExpr>(S);
759      // Handle the previsit checks.
760      ExplodedNodeSet dstPrevisit;
761      getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this);
762
763      // Handle the expression itself.
764      ExplodedNodeSet dstExpr;
765      for (ExplodedNodeSet::iterator i = dstPrevisit.begin(),
766                                     e = dstPrevisit.end(); i != e ; ++i) {
767        VisitCast(C, C->getSubExpr(), *i, dstExpr);
768      }
769
770      // Handle the postvisit checks.
771      getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
772      Bldr.addNodes(Dst);
773      break;
774    }
775
776    case Expr::MaterializeTemporaryExprClass: {
777      Bldr.takeNodes(Pred);
778      const MaterializeTemporaryExpr *Materialize
779                                            = cast<MaterializeTemporaryExpr>(S);
780      if (!Materialize->getType()->isRecordType())
781        CreateCXXTemporaryObject(Materialize, Pred, Dst);
782      else
783        Visit(Materialize->GetTemporaryExpr(), Pred, Dst);
784      Bldr.addNodes(Dst);
785      break;
786    }
787
788    case Stmt::InitListExprClass:
789      Bldr.takeNodes(Pred);
790      VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
791      Bldr.addNodes(Dst);
792      break;
793
794    case Stmt::MemberExprClass:
795      Bldr.takeNodes(Pred);
796      VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
797      Bldr.addNodes(Dst);
798      break;
799
800    case Stmt::ObjCIvarRefExprClass:
801      Bldr.takeNodes(Pred);
802      VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
803      Bldr.addNodes(Dst);
804      break;
805
806    case Stmt::ObjCForCollectionStmtClass:
807      Bldr.takeNodes(Pred);
808      VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
809      Bldr.addNodes(Dst);
810      break;
811
812    case Stmt::ObjCMessageExprClass:
813      Bldr.takeNodes(Pred);
814      VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
815      Bldr.addNodes(Dst);
816      break;
817
818    case Stmt::ObjCAtThrowStmtClass: {
819      // FIXME: This is not complete.  We basically treat @throw as
820      // an abort.
821      Bldr.generateNode(S, Pred, Pred->getState());
822      break;
823    }
824
825    case Stmt::ReturnStmtClass:
826      Bldr.takeNodes(Pred);
827      VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
828      Bldr.addNodes(Dst);
829      break;
830
831    case Stmt::OffsetOfExprClass:
832      Bldr.takeNodes(Pred);
833      VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst);
834      Bldr.addNodes(Dst);
835      break;
836
837    case Stmt::UnaryExprOrTypeTraitExprClass:
838      Bldr.takeNodes(Pred);
839      VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
840                                    Pred, Dst);
841      Bldr.addNodes(Dst);
842      break;
843
844    case Stmt::StmtExprClass: {
845      const StmtExpr *SE = cast<StmtExpr>(S);
846
847      if (SE->getSubStmt()->body_empty()) {
848        // Empty statement expression.
849        assert(SE->getType() == getContext().VoidTy
850               && "Empty statement expression must have void type.");
851        break;
852      }
853
854      if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
855        const ProgramState *state = Pred->getState();
856        Bldr.generateNode(SE, Pred,
857                          state->BindExpr(SE, Pred->getLocationContext(),
858                                          state->getSVal(LastExpr,
859                                                  Pred->getLocationContext())));
860      }
861      break;
862    }
863
864    case Stmt::StringLiteralClass: {
865      const ProgramState *state = Pred->getState();
866      SVal V = state->getLValue(cast<StringLiteral>(S));
867      Bldr.generateNode(S, Pred, state->BindExpr(S, Pred->getLocationContext(),
868                                                 V));
869      return;
870    }
871
872    case Stmt::UnaryOperatorClass: {
873      Bldr.takeNodes(Pred);
874      const UnaryOperator *U = cast<UnaryOperator>(S);
875      if (AMgr.shouldEagerlyAssume() && (U->getOpcode() == UO_LNot)) {
876        ExplodedNodeSet Tmp;
877        VisitUnaryOperator(U, Pred, Tmp);
878        evalEagerlyAssume(Dst, Tmp, U);
879      }
880      else
881        VisitUnaryOperator(U, Pred, Dst);
882      Bldr.addNodes(Dst);
883      break;
884    }
885
886    case Stmt::PseudoObjectExprClass: {
887      Bldr.takeNodes(Pred);
888      const ProgramState *state = Pred->getState();
889      const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S);
890      if (const Expr *Result = PE->getResultExpr()) {
891        SVal V = state->getSVal(Result, Pred->getLocationContext());
892        Bldr.generateNode(S, Pred,
893                          state->BindExpr(S, Pred->getLocationContext(), V));
894      }
895      else
896        Bldr.generateNode(S, Pred,
897                          state->BindExpr(S, Pred->getLocationContext(),
898                                                   UnknownVal()));
899
900      Bldr.addNodes(Dst);
901      break;
902    }
903  }
904}
905
906/// Block entrance.  (Update counters).
907void ExprEngine::processCFGBlockEntrance(NodeBuilderWithSinks &nodeBuilder) {
908
909  // FIXME: Refactor this into a checker.
910  ExplodedNode *pred = nodeBuilder.getContext().getPred();
911
912  if (nodeBuilder.getContext().getCurrentBlockCount() >= AMgr.getMaxVisit()) {
913    static SimpleProgramPointTag tag("ExprEngine : Block count exceeded");
914    nodeBuilder.generateNode(pred->getState(), pred, &tag, true);
915  }
916}
917
918//===----------------------------------------------------------------------===//
919// Branch processing.
920//===----------------------------------------------------------------------===//
921
922const ProgramState *ExprEngine::MarkBranch(const ProgramState *state,
923                                           const Stmt *Terminator,
924                                           const LocationContext *LCtx,
925                                           bool branchTaken) {
926
927  switch (Terminator->getStmtClass()) {
928    default:
929      return state;
930
931    case Stmt::BinaryOperatorClass: { // '&&' and '||'
932
933      const BinaryOperator* B = cast<BinaryOperator>(Terminator);
934      BinaryOperator::Opcode Op = B->getOpcode();
935
936      assert (Op == BO_LAnd || Op == BO_LOr);
937
938      // For &&, if we take the true branch, then the value of the whole
939      // expression is that of the RHS expression.
940      //
941      // For ||, if we take the false branch, then the value of the whole
942      // expression is that of the RHS expression.
943
944      const Expr *Ex = (Op == BO_LAnd && branchTaken) ||
945                       (Op == BO_LOr && !branchTaken)
946                       ? B->getRHS() : B->getLHS();
947
948      return state->BindExpr(B, LCtx, UndefinedVal(Ex));
949    }
950
951    case Stmt::BinaryConditionalOperatorClass:
952    case Stmt::ConditionalOperatorClass: { // ?:
953      const AbstractConditionalOperator* C
954        = cast<AbstractConditionalOperator>(Terminator);
955
956      // For ?, if branchTaken == true then the value is either the LHS or
957      // the condition itself. (GNU extension).
958
959      const Expr *Ex;
960
961      if (branchTaken)
962        Ex = C->getTrueExpr();
963      else
964        Ex = C->getFalseExpr();
965
966      return state->BindExpr(C, LCtx, UndefinedVal(Ex));
967    }
968
969    case Stmt::ChooseExprClass: { // ?:
970
971      const ChooseExpr *C = cast<ChooseExpr>(Terminator);
972
973      const Expr *Ex = branchTaken ? C->getLHS() : C->getRHS();
974      return state->BindExpr(C, LCtx, UndefinedVal(Ex));
975    }
976  }
977}
978
979/// RecoverCastedSymbol - A helper function for ProcessBranch that is used
980/// to try to recover some path-sensitivity for casts of symbolic
981/// integers that promote their values (which are currently not tracked well).
982/// This function returns the SVal bound to Condition->IgnoreCasts if all the
983//  cast(s) did was sign-extend the original value.
984static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr,
985                                const ProgramState *state,
986                                const Stmt *Condition,
987                                const LocationContext *LCtx,
988                                ASTContext &Ctx) {
989
990  const Expr *Ex = dyn_cast<Expr>(Condition);
991  if (!Ex)
992    return UnknownVal();
993
994  uint64_t bits = 0;
995  bool bitsInit = false;
996
997  while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
998    QualType T = CE->getType();
999
1000    if (!T->isIntegerType())
1001      return UnknownVal();
1002
1003    uint64_t newBits = Ctx.getTypeSize(T);
1004    if (!bitsInit || newBits < bits) {
1005      bitsInit = true;
1006      bits = newBits;
1007    }
1008
1009    Ex = CE->getSubExpr();
1010  }
1011
1012  // We reached a non-cast.  Is it a symbolic value?
1013  QualType T = Ex->getType();
1014
1015  if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits)
1016    return UnknownVal();
1017
1018  return state->getSVal(Ex, LCtx);
1019}
1020
1021void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
1022                               NodeBuilderContext& BldCtx,
1023                               ExplodedNode *Pred,
1024                               ExplodedNodeSet &Dst,
1025                               const CFGBlock *DstT,
1026                               const CFGBlock *DstF) {
1027  currentBuilderContext = &BldCtx;
1028
1029  // Check for NULL conditions; e.g. "for(;;)"
1030  if (!Condition) {
1031    BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
1032    NullCondBldr.markInfeasible(false);
1033    NullCondBldr.generateNode(Pred->getState(), true, Pred);
1034    return;
1035  }
1036
1037  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1038                                Condition->getLocStart(),
1039                                "Error evaluating branch");
1040
1041  ExplodedNodeSet CheckersOutSet;
1042  getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
1043                                                    Pred, *this);
1044  // We generated only sinks.
1045  if (CheckersOutSet.empty())
1046    return;
1047
1048  BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
1049  for (NodeBuilder::iterator I = CheckersOutSet.begin(),
1050                             E = CheckersOutSet.end(); E != I; ++I) {
1051    ExplodedNode *PredI = *I;
1052
1053    if (PredI->isSink())
1054      continue;
1055
1056    const ProgramState *PrevState = Pred->getState();
1057    SVal X = PrevState->getSVal(Condition, Pred->getLocationContext());
1058
1059    if (X.isUnknownOrUndef()) {
1060      // Give it a chance to recover from unknown.
1061      if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1062        if (Ex->getType()->isIntegerType()) {
1063          // Try to recover some path-sensitivity.  Right now casts of symbolic
1064          // integers that promote their values are currently not tracked well.
1065          // If 'Condition' is such an expression, try and recover the
1066          // underlying value and use that instead.
1067          SVal recovered = RecoverCastedSymbol(getStateManager(),
1068                                               PrevState, Condition,
1069                                               Pred->getLocationContext(),
1070                                               getContext());
1071
1072          if (!recovered.isUnknown()) {
1073            X = recovered;
1074          }
1075        }
1076      }
1077    }
1078
1079    const LocationContext *LCtx = PredI->getLocationContext();
1080
1081    // If the condition is still unknown, give up.
1082    if (X.isUnknownOrUndef()) {
1083      builder.generateNode(MarkBranch(PrevState, Term, LCtx, true),
1084                           true, PredI);
1085      builder.generateNode(MarkBranch(PrevState, Term, LCtx, false),
1086                           false, PredI);
1087      continue;
1088    }
1089
1090    DefinedSVal V = cast<DefinedSVal>(X);
1091
1092    // Process the true branch.
1093    if (builder.isFeasible(true)) {
1094      if (const ProgramState *state = PrevState->assume(V, true))
1095        builder.generateNode(MarkBranch(state, Term, LCtx, true),
1096                             true, PredI);
1097      else
1098        builder.markInfeasible(true);
1099    }
1100
1101    // Process the false branch.
1102    if (builder.isFeasible(false)) {
1103      if (const ProgramState *state = PrevState->assume(V, false))
1104        builder.generateNode(MarkBranch(state, Term, LCtx, false),
1105                             false, PredI);
1106      else
1107        builder.markInfeasible(false);
1108    }
1109  }
1110  currentBuilderContext = 0;
1111}
1112
1113/// processIndirectGoto - Called by CoreEngine.  Used to generate successor
1114///  nodes by processing the 'effects' of a computed goto jump.
1115void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
1116
1117  const ProgramState *state = builder.getState();
1118  SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
1119
1120  // Three possibilities:
1121  //
1122  //   (1) We know the computed label.
1123  //   (2) The label is NULL (or some other constant), or Undefined.
1124  //   (3) We have no clue about the label.  Dispatch to all targets.
1125  //
1126
1127  typedef IndirectGotoNodeBuilder::iterator iterator;
1128
1129  if (isa<loc::GotoLabel>(V)) {
1130    const LabelDecl *L = cast<loc::GotoLabel>(V).getLabel();
1131
1132    for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
1133      if (I.getLabel() == L) {
1134        builder.generateNode(I, state);
1135        return;
1136      }
1137    }
1138
1139    llvm_unreachable("No block with label.");
1140  }
1141
1142  if (isa<loc::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
1143    // Dispatch to the first target and mark it as a sink.
1144    //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1145    // FIXME: add checker visit.
1146    //    UndefBranches.insert(N);
1147    return;
1148  }
1149
1150  // This is really a catch-all.  We don't support symbolics yet.
1151  // FIXME: Implement dispatch for symbolic pointers.
1152
1153  for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
1154    builder.generateNode(I, state);
1155}
1156
1157/// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
1158///  nodes when the control reaches the end of a function.
1159void ExprEngine::processEndOfFunction(NodeBuilderContext& BC) {
1160  StateMgr.EndPath(BC.Pred->getState());
1161  ExplodedNodeSet Dst;
1162  getCheckerManager().runCheckersForEndPath(BC, Dst, *this);
1163  Engine.enqueueEndOfFunction(Dst);
1164}
1165
1166/// ProcessSwitch - Called by CoreEngine.  Used to generate successor
1167///  nodes by processing the 'effects' of a switch statement.
1168void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
1169  typedef SwitchNodeBuilder::iterator iterator;
1170  const ProgramState *state = builder.getState();
1171  const Expr *CondE = builder.getCondition();
1172  SVal  CondV_untested = state->getSVal(CondE, builder.getLocationContext());
1173
1174  if (CondV_untested.isUndef()) {
1175    //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1176    // FIXME: add checker
1177    //UndefBranches.insert(N);
1178
1179    return;
1180  }
1181  DefinedOrUnknownSVal CondV = cast<DefinedOrUnknownSVal>(CondV_untested);
1182
1183  const ProgramState *DefaultSt = state;
1184
1185  iterator I = builder.begin(), EI = builder.end();
1186  bool defaultIsFeasible = I == EI;
1187
1188  for ( ; I != EI; ++I) {
1189    // Successor may be pruned out during CFG construction.
1190    if (!I.getBlock())
1191      continue;
1192
1193    const CaseStmt *Case = I.getCase();
1194
1195    // Evaluate the LHS of the case value.
1196    llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
1197    assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType()));
1198
1199    // Get the RHS of the case, if it exists.
1200    llvm::APSInt V2;
1201    if (const Expr *E = Case->getRHS())
1202      V2 = E->EvaluateKnownConstInt(getContext());
1203    else
1204      V2 = V1;
1205
1206    // FIXME: Eventually we should replace the logic below with a range
1207    //  comparison, rather than concretize the values within the range.
1208    //  This should be easy once we have "ranges" for NonLVals.
1209
1210    do {
1211      nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1));
1212      DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
1213                                               CondV, CaseVal);
1214
1215      // Now "assume" that the case matches.
1216      if (const ProgramState *stateNew = state->assume(Res, true)) {
1217        builder.generateCaseStmtNode(I, stateNew);
1218
1219        // If CondV evaluates to a constant, then we know that this
1220        // is the *only* case that we can take, so stop evaluating the
1221        // others.
1222        if (isa<nonloc::ConcreteInt>(CondV))
1223          return;
1224      }
1225
1226      // Now "assume" that the case doesn't match.  Add this state
1227      // to the default state (if it is feasible).
1228      if (DefaultSt) {
1229        if (const ProgramState *stateNew = DefaultSt->assume(Res, false)) {
1230          defaultIsFeasible = true;
1231          DefaultSt = stateNew;
1232        }
1233        else {
1234          defaultIsFeasible = false;
1235          DefaultSt = NULL;
1236        }
1237      }
1238
1239      // Concretize the next value in the range.
1240      if (V1 == V2)
1241        break;
1242
1243      ++V1;
1244      assert (V1 <= V2);
1245
1246    } while (true);
1247  }
1248
1249  if (!defaultIsFeasible)
1250    return;
1251
1252  // If we have switch(enum value), the default branch is not
1253  // feasible if all of the enum constants not covered by 'case:' statements
1254  // are not feasible values for the switch condition.
1255  //
1256  // Note that this isn't as accurate as it could be.  Even if there isn't
1257  // a case for a particular enum value as long as that enum value isn't
1258  // feasible then it shouldn't be considered for making 'default:' reachable.
1259  const SwitchStmt *SS = builder.getSwitch();
1260  const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1261  if (CondExpr->getType()->getAs<EnumType>()) {
1262    if (SS->isAllEnumCasesCovered())
1263      return;
1264  }
1265
1266  builder.generateDefaultCaseNode(DefaultSt);
1267}
1268
1269//===----------------------------------------------------------------------===//
1270// Transfer functions: Loads and stores.
1271//===----------------------------------------------------------------------===//
1272
1273void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
1274                                        ExplodedNode *Pred,
1275                                        ExplodedNodeSet &Dst) {
1276  StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext);
1277
1278  const ProgramState *state = Pred->getState();
1279  const LocationContext *LCtx = Pred->getLocationContext();
1280
1281  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1282    assert(Ex->isLValue());
1283    SVal V = state->getLValue(VD, Pred->getLocationContext());
1284
1285    // For references, the 'lvalue' is the pointer address stored in the
1286    // reference region.
1287    if (VD->getType()->isReferenceType()) {
1288      if (const MemRegion *R = V.getAsRegion())
1289        V = state->getSVal(R);
1290      else
1291        V = UnknownVal();
1292    }
1293
1294    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0,
1295                      ProgramPoint::PostLValueKind);
1296    return;
1297  }
1298  if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) {
1299    assert(!Ex->isLValue());
1300    SVal V = svalBuilder.makeIntVal(ED->getInitVal());
1301    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
1302    return;
1303  }
1304  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
1305    SVal V = svalBuilder.getFunctionPointer(FD);
1306    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), false, 0,
1307                      ProgramPoint::PostLValueKind);
1308    return;
1309  }
1310  assert (false &&
1311          "ValueDecl support for this ValueDecl not implemented.");
1312}
1313
1314/// VisitArraySubscriptExpr - Transfer function for array accesses
1315void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A,
1316                                             ExplodedNode *Pred,
1317                                             ExplodedNodeSet &Dst){
1318
1319  const Expr *Base = A->getBase()->IgnoreParens();
1320  const Expr *Idx  = A->getIdx()->IgnoreParens();
1321
1322
1323  ExplodedNodeSet checkerPreStmt;
1324  getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this);
1325
1326  StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currentBuilderContext);
1327
1328  for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(),
1329                                 ei = checkerPreStmt.end(); it != ei; ++it) {
1330    const LocationContext *LCtx = (*it)->getLocationContext();
1331    const ProgramState *state = (*it)->getState();
1332    SVal V = state->getLValue(A->getType(),
1333                              state->getSVal(Idx, LCtx),
1334                              state->getSVal(Base, LCtx));
1335    assert(A->isLValue());
1336    Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V),
1337                      false, 0, ProgramPoint::PostLValueKind);
1338  }
1339}
1340
1341/// VisitMemberExpr - Transfer function for member expressions.
1342void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
1343                                 ExplodedNodeSet &TopDst) {
1344
1345  StmtNodeBuilder Bldr(Pred, TopDst, *currentBuilderContext);
1346  ExplodedNodeSet Dst;
1347  Decl *member = M->getMemberDecl();
1348  if (VarDecl *VD = dyn_cast<VarDecl>(member)) {
1349    assert(M->isLValue());
1350    Bldr.takeNodes(Pred);
1351    VisitCommonDeclRefExpr(M, VD, Pred, Dst);
1352    Bldr.addNodes(Dst);
1353    return;
1354  }
1355
1356  FieldDecl *field = dyn_cast<FieldDecl>(member);
1357  if (!field) // FIXME: skipping member expressions for non-fields
1358    return;
1359
1360  Expr *baseExpr = M->getBase()->IgnoreParens();
1361  const ProgramState *state = Pred->getState();
1362  const LocationContext *LCtx = Pred->getLocationContext();
1363  SVal baseExprVal = state->getSVal(baseExpr, Pred->getLocationContext());
1364  if (isa<nonloc::LazyCompoundVal>(baseExprVal) ||
1365      isa<nonloc::CompoundVal>(baseExprVal) ||
1366      // FIXME: This can originate by conjuring a symbol for an unknown
1367      // temporary struct object, see test/Analysis/fields.c:
1368      // (p = getit()).x
1369      isa<nonloc::SymbolVal>(baseExprVal)) {
1370    Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, UnknownVal()));
1371    return;
1372  }
1373
1374  // FIXME: Should we insert some assumption logic in here to determine
1375  // if "Base" is a valid piece of memory?  Before we put this assumption
1376  // later when using FieldOffset lvals (which we no longer have).
1377
1378  // For all other cases, compute an lvalue.
1379  SVal L = state->getLValue(field, baseExprVal);
1380  if (M->isLValue())
1381    Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), false, 0,
1382                      ProgramPoint::PostLValueKind);
1383  else {
1384    Bldr.takeNodes(Pred);
1385    evalLoad(Dst, M, Pred, state, L);
1386    Bldr.addNodes(Dst);
1387  }
1388}
1389
1390/// evalBind - Handle the semantics of binding a value to a specific location.
1391///  This method is used by evalStore and (soon) VisitDeclStmt, and others.
1392void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
1393                          ExplodedNode *Pred,
1394                          SVal location, SVal Val, bool atDeclInit,
1395                          ProgramPoint::Kind PointKind) {
1396
1397  // Do a previsit of the bind.
1398  ExplodedNodeSet CheckedSet;
1399  getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
1400                                         StoreE, *this, PointKind);
1401
1402  // TODO:AZ Remove TmpDst after NB refactoring is done.
1403  ExplodedNodeSet TmpDst;
1404  StmtNodeBuilder Bldr(CheckedSet, TmpDst, *currentBuilderContext);
1405
1406  for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1407       I!=E; ++I) {
1408    const ProgramState *state = (*I)->getState();
1409
1410    if (atDeclInit) {
1411      const VarRegion *VR =
1412        cast<VarRegion>(cast<loc::MemRegionVal>(location).getRegion());
1413
1414      state = state->bindDecl(VR, Val);
1415    } else {
1416      state = state->bindLoc(location, Val);
1417    }
1418
1419    Bldr.generateNode(StoreE, *I, state, false, 0, PointKind);
1420  }
1421
1422  Dst.insert(TmpDst);
1423}
1424
1425/// evalStore - Handle the semantics of a store via an assignment.
1426///  @param Dst The node set to store generated state nodes
1427///  @param AssignE The assignment expression if the store happens in an
1428///         assignment.
1429///  @param LocatioinE The location expression that is stored to.
1430///  @param state The current simulation state
1431///  @param location The location to store the value
1432///  @param Val The value to be stored
1433void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
1434                             const Expr *LocationE,
1435                             ExplodedNode *Pred,
1436                             const ProgramState *state, SVal location, SVal Val,
1437                             const ProgramPointTag *tag) {
1438  // Proceed with the store.  We use AssignE as the anchor for the PostStore
1439  // ProgramPoint if it is non-NULL, and LocationE otherwise.
1440  const Expr *StoreE = AssignE ? AssignE : LocationE;
1441
1442  if (isa<loc::ObjCPropRef>(location)) {
1443    loc::ObjCPropRef prop = cast<loc::ObjCPropRef>(location);
1444    return VisitObjCMessage(ObjCPropertySetter(prop.getPropRefExpr(),
1445                                               StoreE, Val), Pred, Dst);
1446  }
1447
1448  // Evaluate the location (checks for bad dereferences).
1449  ExplodedNodeSet Tmp;
1450  evalLocation(Tmp, LocationE, Pred, state, location, tag, false);
1451
1452  if (Tmp.empty())
1453    return;
1454
1455  if (location.isUndef())
1456    return;
1457
1458  for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
1459    evalBind(Dst, StoreE, *NI, location, Val, false,
1460             ProgramPoint::PostStoreKind);
1461}
1462
1463void ExprEngine::evalLoad(ExplodedNodeSet &Dst, const Expr *Ex,
1464                            ExplodedNode *Pred,
1465                            const ProgramState *state, SVal location,
1466                            const ProgramPointTag *tag, QualType LoadTy) {
1467  assert(!isa<NonLoc>(location) && "location cannot be a NonLoc.");
1468
1469  if (isa<loc::ObjCPropRef>(location)) {
1470    loc::ObjCPropRef prop = cast<loc::ObjCPropRef>(location);
1471    return VisitObjCMessage(ObjCPropertyGetter(prop.getPropRefExpr(), Ex),
1472                            Pred, Dst);
1473  }
1474
1475  // Are we loading from a region?  This actually results in two loads; one
1476  // to fetch the address of the referenced value and one to fetch the
1477  // referenced value.
1478  if (const TypedValueRegion *TR =
1479        dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) {
1480
1481    QualType ValTy = TR->getValueType();
1482    if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
1483      static SimpleProgramPointTag
1484             loadReferenceTag("ExprEngine : Load Reference");
1485      ExplodedNodeSet Tmp;
1486      evalLoadCommon(Tmp, Ex, Pred, state, location, &loadReferenceTag,
1487                     getContext().getPointerType(RT->getPointeeType()));
1488
1489      // Perform the load from the referenced value.
1490      for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
1491        state = (*I)->getState();
1492        location = state->getSVal(Ex, (*I)->getLocationContext());
1493        evalLoadCommon(Dst, Ex, *I, state, location, tag, LoadTy);
1494      }
1495      return;
1496    }
1497  }
1498
1499  evalLoadCommon(Dst, Ex, Pred, state, location, tag, LoadTy);
1500}
1501
1502void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst, const Expr *Ex,
1503                                  ExplodedNode *Pred,
1504                                  const ProgramState *state, SVal location,
1505                                  const ProgramPointTag *tag, QualType LoadTy) {
1506
1507  // Evaluate the location (checks for bad dereferences).
1508  ExplodedNodeSet Tmp;
1509  evalLocation(Tmp, Ex, Pred, state, location, tag, true);
1510  if (Tmp.empty())
1511    return;
1512
1513  StmtNodeBuilder Bldr(Tmp, Dst, *currentBuilderContext);
1514  if (location.isUndef())
1515    return;
1516
1517  // Proceed with the load.
1518  for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
1519    state = (*NI)->getState();
1520    const LocationContext *LCtx = (*NI)->getLocationContext();
1521
1522    if (location.isUnknown()) {
1523      // This is important.  We must nuke the old binding.
1524      Bldr.generateNode(Ex, *NI, state->BindExpr(Ex, LCtx, UnknownVal()),
1525                        false, tag, ProgramPoint::PostLoadKind);
1526    }
1527    else {
1528      if (LoadTy.isNull())
1529        LoadTy = Ex->getType();
1530      SVal V = state->getSVal(cast<Loc>(location), LoadTy);
1531      Bldr.generateNode(Ex, *NI, state->bindExprAndLocation(Ex, LCtx,
1532                                                            location, V),
1533                        false, tag, ProgramPoint::PostLoadKind);
1534    }
1535  }
1536}
1537
1538void ExprEngine::evalLocation(ExplodedNodeSet &Dst, const Stmt *S,
1539                                ExplodedNode *Pred,
1540                                const ProgramState *state, SVal location,
1541                                const ProgramPointTag *tag, bool isLoad) {
1542  StmtNodeBuilder BldrTop(Pred, Dst, *currentBuilderContext);
1543  // Early checks for performance reason.
1544  if (location.isUnknown()) {
1545    return;
1546  }
1547
1548  ExplodedNodeSet Src;
1549  BldrTop.takeNodes(Pred);
1550  StmtNodeBuilder Bldr(Pred, Src, *currentBuilderContext);
1551  if (Pred->getState() != state) {
1552    // Associate this new state with an ExplodedNode.
1553    // FIXME: If I pass null tag, the graph is incorrect, e.g for
1554    //   int *p;
1555    //   p = 0;
1556    //   *p = 0xDEADBEEF;
1557    // "p = 0" is not noted as "Null pointer value stored to 'p'" but
1558    // instead "int *p" is noted as
1559    // "Variable 'p' initialized to a null pointer value"
1560
1561    // FIXME: why is 'tag' not used instead of etag?
1562    static SimpleProgramPointTag etag("ExprEngine: Location");
1563
1564    Bldr.generateNode(S, Pred, state, false, &etag);
1565  }
1566  ExplodedNodeSet Tmp;
1567  getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad, S,
1568                                             *this);
1569  BldrTop.addNodes(Tmp);
1570}
1571
1572bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE,
1573                              ExplodedNode *Pred) {
1574  return false;
1575
1576  // Inlining isn't correct right now because we:
1577  // (a) don't generate CallExit nodes.
1578  // (b) we need a way to postpone doing post-visits of CallExprs until
1579  // the CallExit.  This means we need CallExits for the non-inline
1580  // cases as well.
1581
1582#if 0
1583  const ProgramState *state = Pred->getState();
1584  const Expr *Callee = CE->getCallee();
1585  SVal L = state->getSVal(Callee);
1586
1587  const FunctionDecl *FD = L.getAsFunctionDecl();
1588  if (!FD)
1589    return false;
1590
1591  // Specially handle CXXMethods.
1592  const CXXMethodDecl *methodDecl = 0;
1593
1594  switch (CE->getStmtClass()) {
1595    default: break;
1596    case Stmt::CXXOperatorCallExprClass: {
1597      const CXXOperatorCallExpr *opCall = cast<CXXOperatorCallExpr>(CE);
1598      methodDecl =
1599        dyn_cast_or_null<CXXMethodDecl>(opCall->getCalleeDecl());
1600      break;
1601    }
1602    case Stmt::CXXMemberCallExprClass: {
1603      const CXXMemberCallExpr *memberCall = cast<CXXMemberCallExpr>(CE);
1604      const MemberExpr *memberExpr =
1605        cast<MemberExpr>(memberCall->getCallee()->IgnoreParens());
1606      methodDecl = cast<CXXMethodDecl>(memberExpr->getMemberDecl());
1607      break;
1608    }
1609  }
1610
1611
1612
1613
1614  // Check if the function definition is in the same translation unit.
1615  if (FD->hasBody(FD)) {
1616    const StackFrameContext *stackFrame =
1617      AMgr.getStackFrame(AMgr.getAnalysisDeclContext(FD),
1618                         Pred->getLocationContext(),
1619                         CE, currentBuilderContext->getBlock(),
1620                         currentStmtIdx);
1621    // Now we have the definition of the callee, create a CallEnter node.
1622    CallEnter Loc(CE, stackFrame, Pred->getLocationContext());
1623
1624    ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
1625    Dst.Add(N);
1626    return true;
1627  }
1628
1629  // Check if we can find the function definition in other translation units.
1630  if (AMgr.hasIndexer()) {
1631    AnalysisDeclContext *C = AMgr.getAnalysisDeclContextInAnotherTU(FD);
1632    if (C == 0)
1633      return false;
1634    const StackFrameContext *stackFrame =
1635      AMgr.getStackFrame(C, Pred->getLocationContext(),
1636                         CE, currentBuilderContext->getBlock(), currentStmtIdx);
1637    CallEnter Loc(CE, stackFrame, Pred->getLocationContext());
1638    ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
1639    Dst.Add(N);
1640    return true;
1641  }
1642
1643  // Generate the CallExit node.
1644
1645  return false;
1646#endif
1647}
1648
1649std::pair<const ProgramPointTag *, const ProgramPointTag*>
1650ExprEngine::getEagerlyAssumeTags() {
1651  static SimpleProgramPointTag
1652         EagerlyAssumeTrue("ExprEngine : Eagerly Assume True"),
1653         EagerlyAssumeFalse("ExprEngine : Eagerly Assume False");
1654  return std::make_pair(&EagerlyAssumeTrue, &EagerlyAssumeFalse);
1655}
1656
1657void ExprEngine::evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
1658                                   const Expr *Ex) {
1659  StmtNodeBuilder Bldr(Src, Dst, *currentBuilderContext);
1660
1661  for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
1662    ExplodedNode *Pred = *I;
1663    // Test if the previous node was as the same expression.  This can happen
1664    // when the expression fails to evaluate to anything meaningful and
1665    // (as an optimization) we don't generate a node.
1666    ProgramPoint P = Pred->getLocation();
1667    if (!isa<PostStmt>(P) || cast<PostStmt>(P).getStmt() != Ex) {
1668      continue;
1669    }
1670
1671    const ProgramState *state = Pred->getState();
1672    SVal V = state->getSVal(Ex, Pred->getLocationContext());
1673    nonloc::SymbolVal *SEV = dyn_cast<nonloc::SymbolVal>(&V);
1674    if (SEV && SEV->isExpression()) {
1675      const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
1676        getEagerlyAssumeTags();
1677
1678      // First assume that the condition is true.
1679      if (const ProgramState *StateTrue = state->assume(*SEV, true)) {
1680        SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
1681        StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
1682        Bldr.generateNode(Ex, Pred, StateTrue, false, tags.first);
1683      }
1684
1685      // Next, assume that the condition is false.
1686      if (const ProgramState *StateFalse = state->assume(*SEV, false)) {
1687        SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
1688        StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
1689        Bldr.generateNode(Ex, Pred, StateFalse, false, tags.second);
1690      }
1691    }
1692  }
1693}
1694
1695void ExprEngine::VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred,
1696                                ExplodedNodeSet &Dst) {
1697  VisitAsmStmtHelperOutputs(A, A->begin_outputs(), A->end_outputs(), Pred, Dst);
1698}
1699
1700void ExprEngine::VisitAsmStmtHelperOutputs(const AsmStmt *A,
1701                                             AsmStmt::const_outputs_iterator I,
1702                                             AsmStmt::const_outputs_iterator E,
1703                                     ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1704  if (I == E) {
1705    VisitAsmStmtHelperInputs(A, A->begin_inputs(), A->end_inputs(), Pred, Dst);
1706    return;
1707  }
1708
1709  ExplodedNodeSet Tmp;
1710  Visit(*I, Pred, Tmp);
1711  ++I;
1712
1713  for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end();NI != NE;++NI)
1714    VisitAsmStmtHelperOutputs(A, I, E, *NI, Dst);
1715}
1716
1717void ExprEngine::VisitAsmStmtHelperInputs(const AsmStmt *A,
1718                                            AsmStmt::const_inputs_iterator I,
1719                                            AsmStmt::const_inputs_iterator E,
1720                                            ExplodedNode *Pred,
1721                                            ExplodedNodeSet &Dst) {
1722  if (I == E) {
1723    StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext);
1724    // We have processed both the inputs and the outputs.  All of the outputs
1725    // should evaluate to Locs.  Nuke all of their values.
1726
1727    // FIXME: Some day in the future it would be nice to allow a "plug-in"
1728    // which interprets the inline asm and stores proper results in the
1729    // outputs.
1730
1731    const ProgramState *state = Pred->getState();
1732
1733    for (AsmStmt::const_outputs_iterator OI = A->begin_outputs(),
1734                                   OE = A->end_outputs(); OI != OE; ++OI) {
1735
1736      SVal X = state->getSVal(*OI, Pred->getLocationContext());
1737      assert (!isa<NonLoc>(X));  // Should be an Lval, or unknown, undef.
1738
1739      if (isa<Loc>(X))
1740        state = state->bindLoc(cast<Loc>(X), UnknownVal());
1741    }
1742
1743    Bldr.generateNode(A, Pred, state);
1744    return;
1745  }
1746
1747  ExplodedNodeSet Tmp;
1748  Visit(*I, Pred, Tmp);
1749
1750  ++I;
1751
1752  for (ExplodedNodeSet::iterator NI = Tmp.begin(), NE = Tmp.end(); NI!=NE; ++NI)
1753    VisitAsmStmtHelperInputs(A, I, E, *NI, Dst);
1754}
1755
1756
1757//===----------------------------------------------------------------------===//
1758// Visualization.
1759//===----------------------------------------------------------------------===//
1760
1761#ifndef NDEBUG
1762static ExprEngine* GraphPrintCheckerState;
1763static SourceManager* GraphPrintSourceManager;
1764
1765namespace llvm {
1766template<>
1767struct DOTGraphTraits<ExplodedNode*> :
1768  public DefaultDOTGraphTraits {
1769
1770  DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
1771
1772  // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
1773  // work.
1774  static std::string getNodeAttributes(const ExplodedNode *N, void*) {
1775
1776#if 0
1777      // FIXME: Replace with a general scheme to tell if the node is
1778      // an error node.
1779    if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
1780        GraphPrintCheckerState->isExplicitNullDeref(N) ||
1781        GraphPrintCheckerState->isUndefDeref(N) ||
1782        GraphPrintCheckerState->isUndefStore(N) ||
1783        GraphPrintCheckerState->isUndefControlFlow(N) ||
1784        GraphPrintCheckerState->isUndefResult(N) ||
1785        GraphPrintCheckerState->isBadCall(N) ||
1786        GraphPrintCheckerState->isUndefArg(N))
1787      return "color=\"red\",style=\"filled\"";
1788
1789    if (GraphPrintCheckerState->isNoReturnCall(N))
1790      return "color=\"blue\",style=\"filled\"";
1791#endif
1792    return "";
1793  }
1794
1795  static std::string getNodeLabel(const ExplodedNode *N, void*){
1796
1797    std::string sbuf;
1798    llvm::raw_string_ostream Out(sbuf);
1799
1800    // Program Location.
1801    ProgramPoint Loc = N->getLocation();
1802
1803    switch (Loc.getKind()) {
1804      case ProgramPoint::BlockEntranceKind:
1805        Out << "Block Entrance: B"
1806            << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
1807        break;
1808
1809      case ProgramPoint::BlockExitKind:
1810        assert (false);
1811        break;
1812
1813      case ProgramPoint::CallEnterKind:
1814        Out << "CallEnter";
1815        break;
1816
1817      case ProgramPoint::CallExitKind:
1818        Out << "CallExit";
1819        break;
1820
1821      default: {
1822        if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) {
1823          const Stmt *S = L->getStmt();
1824          SourceLocation SLoc = S->getLocStart();
1825
1826          Out << S->getStmtClassName() << ' ' << (void*) S << ' ';
1827          LangOptions LO; // FIXME.
1828          S->printPretty(Out, 0, PrintingPolicy(LO));
1829
1830          if (SLoc.isFileID()) {
1831            Out << "\\lline="
1832              << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
1833              << " col="
1834              << GraphPrintSourceManager->getExpansionColumnNumber(SLoc)
1835              << "\\l";
1836          }
1837
1838          if (isa<PreStmt>(Loc))
1839            Out << "\\lPreStmt\\l;";
1840          else if (isa<PostLoad>(Loc))
1841            Out << "\\lPostLoad\\l;";
1842          else if (isa<PostStore>(Loc))
1843            Out << "\\lPostStore\\l";
1844          else if (isa<PostLValue>(Loc))
1845            Out << "\\lPostLValue\\l";
1846
1847#if 0
1848            // FIXME: Replace with a general scheme to determine
1849            // the name of the check.
1850          if (GraphPrintCheckerState->isImplicitNullDeref(N))
1851            Out << "\\|Implicit-Null Dereference.\\l";
1852          else if (GraphPrintCheckerState->isExplicitNullDeref(N))
1853            Out << "\\|Explicit-Null Dereference.\\l";
1854          else if (GraphPrintCheckerState->isUndefDeref(N))
1855            Out << "\\|Dereference of undefialied value.\\l";
1856          else if (GraphPrintCheckerState->isUndefStore(N))
1857            Out << "\\|Store to Undefined Loc.";
1858          else if (GraphPrintCheckerState->isUndefResult(N))
1859            Out << "\\|Result of operation is undefined.";
1860          else if (GraphPrintCheckerState->isNoReturnCall(N))
1861            Out << "\\|Call to function marked \"noreturn\".";
1862          else if (GraphPrintCheckerState->isBadCall(N))
1863            Out << "\\|Call to NULL/Undefined.";
1864          else if (GraphPrintCheckerState->isUndefArg(N))
1865            Out << "\\|Argument in call is undefined";
1866#endif
1867
1868          break;
1869        }
1870
1871        const BlockEdge &E = cast<BlockEdge>(Loc);
1872        Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
1873            << E.getDst()->getBlockID()  << ')';
1874
1875        if (const Stmt *T = E.getSrc()->getTerminator()) {
1876
1877          SourceLocation SLoc = T->getLocStart();
1878
1879          Out << "\\|Terminator: ";
1880          LangOptions LO; // FIXME.
1881          E.getSrc()->printTerminator(Out, LO);
1882
1883          if (SLoc.isFileID()) {
1884            Out << "\\lline="
1885              << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
1886              << " col="
1887              << GraphPrintSourceManager->getExpansionColumnNumber(SLoc);
1888          }
1889
1890          if (isa<SwitchStmt>(T)) {
1891            const Stmt *Label = E.getDst()->getLabel();
1892
1893            if (Label) {
1894              if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
1895                Out << "\\lcase ";
1896                LangOptions LO; // FIXME.
1897                C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
1898
1899                if (const Stmt *RHS = C->getRHS()) {
1900                  Out << " .. ";
1901                  RHS->printPretty(Out, 0, PrintingPolicy(LO));
1902                }
1903
1904                Out << ":";
1905              }
1906              else {
1907                assert (isa<DefaultStmt>(Label));
1908                Out << "\\ldefault:";
1909              }
1910            }
1911            else
1912              Out << "\\l(implicit) default:";
1913          }
1914          else if (isa<IndirectGotoStmt>(T)) {
1915            // FIXME
1916          }
1917          else {
1918            Out << "\\lCondition: ";
1919            if (*E.getSrc()->succ_begin() == E.getDst())
1920              Out << "true";
1921            else
1922              Out << "false";
1923          }
1924
1925          Out << "\\l";
1926        }
1927
1928#if 0
1929          // FIXME: Replace with a general scheme to determine
1930          // the name of the check.
1931        if (GraphPrintCheckerState->isUndefControlFlow(N)) {
1932          Out << "\\|Control-flow based on\\lUndefined value.\\l";
1933        }
1934#endif
1935      }
1936    }
1937
1938    const ProgramState *state = N->getState();
1939    Out << "\\|StateID: " << (void*) state
1940        << " NodeID: " << (void*) N << "\\|";
1941    state->printDOT(Out);
1942
1943    Out << "\\l";
1944
1945    if (const ProgramPointTag *tag = Loc.getTag()) {
1946      Out << "\\|Tag: " << tag->getTagDescription();
1947      Out << "\\l";
1948    }
1949    return Out.str();
1950  }
1951};
1952} // end llvm namespace
1953#endif
1954
1955#ifndef NDEBUG
1956template <typename ITERATOR>
1957ExplodedNode *GetGraphNode(ITERATOR I) { return *I; }
1958
1959template <> ExplodedNode*
1960GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
1961  (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
1962  return I->first;
1963}
1964#endif
1965
1966void ExprEngine::ViewGraph(bool trim) {
1967#ifndef NDEBUG
1968  if (trim) {
1969    std::vector<ExplodedNode*> Src;
1970
1971    // Flush any outstanding reports to make sure we cover all the nodes.
1972    // This does not cause them to get displayed.
1973    for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
1974      const_cast<BugType*>(*I)->FlushReports(BR);
1975
1976    // Iterate through the reports and get their nodes.
1977    for (BugReporter::EQClasses_iterator
1978           EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
1979      BugReportEquivClass& EQ = *EI;
1980      const BugReport &R = **EQ.begin();
1981      ExplodedNode *N = const_cast<ExplodedNode*>(R.getErrorNode());
1982      if (N) Src.push_back(N);
1983    }
1984
1985    ViewGraph(&Src[0], &Src[0]+Src.size());
1986  }
1987  else {
1988    GraphPrintCheckerState = this;
1989    GraphPrintSourceManager = &getContext().getSourceManager();
1990
1991    llvm::ViewGraph(*G.roots_begin(), "ExprEngine");
1992
1993    GraphPrintCheckerState = NULL;
1994    GraphPrintSourceManager = NULL;
1995  }
1996#endif
1997}
1998
1999void ExprEngine::ViewGraph(ExplodedNode** Beg, ExplodedNode** End) {
2000#ifndef NDEBUG
2001  GraphPrintCheckerState = this;
2002  GraphPrintSourceManager = &getContext().getSourceManager();
2003
2004  std::auto_ptr<ExplodedGraph> TrimmedG(G.Trim(Beg, End).first);
2005
2006  if (!TrimmedG.get())
2007    llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
2008  else
2009    llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine");
2010
2011  GraphPrintCheckerState = NULL;
2012  GraphPrintSourceManager = NULL;
2013#endif
2014}
2015