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