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