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