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