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