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