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