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