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