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