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