ExprEngine.cpp revision 6a556a42d48cc098fb8dcb5d4ecdd0e03e32c0ec 
1//=-- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines a meta-engine for path-sensitive dataflow analysis that
11//  is built on GREngine, but provides the boilerplate to execute transfer
12//  functions and build the ExplodedGraph at the expression level.
13//
14//===----------------------------------------------------------------------===//
15
16#define DEBUG_TYPE "ExprEngine"
17
18#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
19#include "PrettyStackTraceLocationContext.h"
20#include "clang/AST/CharUnits.h"
21#include "clang/AST/ParentMap.h"
22#include "clang/AST/StmtCXX.h"
23#include "clang/AST/StmtObjC.h"
24#include "clang/Basic/Builtins.h"
25#include "clang/Basic/PrettyStackTrace.h"
26#include "clang/Basic/SourceManager.h"
27#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
28#include "clang/StaticAnalyzer/Core/CheckerManager.h"
29#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
30#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
31#include "llvm/ADT/ImmutableList.h"
32#include "llvm/ADT/Statistic.h"
33#include "llvm/Support/raw_ostream.h"
34
35#ifndef NDEBUG
36#include "llvm/Support/GraphWriter.h"
37#endif
38
39using namespace clang;
40using namespace ento;
41using llvm::APSInt;
42
43STATISTIC(NumRemoveDeadBindings,
44            "The # of times RemoveDeadBindings is called");
45STATISTIC(NumMaxBlockCountReached,
46            "The # of aborted paths due to reaching the maximum block count in "
47            "a top level function");
48STATISTIC(NumMaxBlockCountReachedInInlined,
49            "The # of aborted paths due to reaching the maximum block count in "
50            "an inlined function");
51STATISTIC(NumTimesRetriedWithoutInlining,
52            "The # of times we re-evaluated a call without inlining");
53
54//===----------------------------------------------------------------------===//
55// Engine construction and deletion.
56//===----------------------------------------------------------------------===//
57
58ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled,
59                       SetOfConstDecls *VisitedCalleesIn,
60                       FunctionSummariesTy *FS,
61                       InliningModes HowToInlineIn)
62  : AMgr(mgr),
63    AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
64    Engine(*this, FS),
65    G(Engine.getGraph()),
66    StateMgr(getContext(), mgr.getStoreManagerCreator(),
67             mgr.getConstraintManagerCreator(), G.getAllocator(),
68             this),
69    SymMgr(StateMgr.getSymbolManager()),
70    svalBuilder(StateMgr.getSValBuilder()),
71    currStmtIdx(0), currBldrCtx(0),
72    ObjCNoRet(mgr.getASTContext()),
73    ObjCGCEnabled(gcEnabled), BR(mgr, *this),
74    VisitedCallees(VisitedCalleesIn),
75    HowToInline(HowToInlineIn)
76{
77  unsigned TrimInterval = mgr.options.getGraphTrimInterval();
78  if (TrimInterval != 0) {
79    // Enable eager node reclaimation when constructing the ExplodedGraph.
80    G.enableNodeReclamation(TrimInterval);
81  }
82}
83
84ExprEngine::~ExprEngine() {
85  BR.FlushReports();
86}
87
88//===----------------------------------------------------------------------===//
89// Utility methods.
90//===----------------------------------------------------------------------===//
91
92ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
93  ProgramStateRef state = StateMgr.getInitialState(InitLoc);
94  const Decl *D = InitLoc->getDecl();
95
96  // Preconditions.
97  // FIXME: It would be nice if we had a more general mechanism to add
98  // such preconditions.  Some day.
99  do {
100
101    if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
102      // Precondition: the first argument of 'main' is an integer guaranteed
103      //  to be > 0.
104      const IdentifierInfo *II = FD->getIdentifier();
105      if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
106        break;
107
108      const ParmVarDecl *PD = FD->getParamDecl(0);
109      QualType T = PD->getType();
110      const BuiltinType *BT = dyn_cast<BuiltinType>(T);
111      if (!BT || !BT->isInteger())
112        break;
113
114      const MemRegion *R = state->getRegion(PD, InitLoc);
115      if (!R)
116        break;
117
118      SVal V = state->getSVal(loc::MemRegionVal(R));
119      SVal Constraint_untested = evalBinOp(state, BO_GT, V,
120                                           svalBuilder.makeZeroVal(T),
121                                           getContext().IntTy);
122
123      Optional<DefinedOrUnknownSVal> Constraint =
124          Constraint_untested.getAs<DefinedOrUnknownSVal>();
125
126      if (!Constraint)
127        break;
128
129      if (ProgramStateRef newState = state->assume(*Constraint, true))
130        state = newState;
131    }
132    break;
133  }
134  while (0);
135
136  if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) {
137    // Precondition: 'self' is always non-null upon entry to an Objective-C
138    // method.
139    const ImplicitParamDecl *SelfD = MD->getSelfDecl();
140    const MemRegion *R = state->getRegion(SelfD, InitLoc);
141    SVal V = state->getSVal(loc::MemRegionVal(R));
142
143    if (Optional<Loc> LV = V.getAs<Loc>()) {
144      // Assume that the pointer value in 'self' is non-null.
145      state = state->assume(*LV, true);
146      assert(state && "'self' cannot be null");
147    }
148  }
149
150  if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(D)) {
151    if (!MD->isStatic()) {
152      // Precondition: 'this' is always non-null upon entry to the
153      // top-level function.  This is our starting assumption for
154      // analyzing an "open" program.
155      const StackFrameContext *SFC = InitLoc->getCurrentStackFrame();
156      if (SFC->getParent() == 0) {
157        loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC);
158        SVal V = state->getSVal(L);
159        if (Optional<Loc> LV = V.getAs<Loc>()) {
160          state = state->assume(*LV, true);
161          assert(state && "'this' cannot be null");
162        }
163      }
164    }
165  }
166
167  return state;
168}
169
170ProgramStateRef
171ExprEngine::createTemporaryRegionIfNeeded(ProgramStateRef State,
172                                          const LocationContext *LC,
173                                          const Expr *Ex,
174                                          const Expr *Result) {
175  SVal V = State->getSVal(Ex, LC);
176  if (!Result) {
177    // If we don't have an explicit result expression, we're in "if needed"
178    // mode. Only create a region if the current value is a NonLoc.
179    if (!V.getAs<NonLoc>())
180      return State;
181    Result = Ex;
182  } else {
183    // We need to create a region no matter what. For sanity, make sure we don't
184    // try to stuff a Loc into a non-pointer temporary region.
185    assert(!V.getAs<Loc>() || Loc::isLocType(Result->getType()) ||
186           Result->getType()->isMemberPointerType());
187  }
188
189  ProgramStateManager &StateMgr = State->getStateManager();
190  MemRegionManager &MRMgr = StateMgr.getRegionManager();
191  StoreManager &StoreMgr = StateMgr.getStoreManager();
192
193  // We need to be careful about treating a derived type's value as
194  // bindings for a base type. Unless we're creating a temporary pointer region,
195  // start by stripping and recording base casts.
196  SmallVector<const CastExpr *, 4> Casts;
197  const Expr *Inner = Ex->IgnoreParens();
198  if (!Loc::isLocType(Result->getType())) {
199    while (const CastExpr *CE = dyn_cast<CastExpr>(Inner)) {
200      if (CE->getCastKind() == CK_DerivedToBase ||
201          CE->getCastKind() == CK_UncheckedDerivedToBase)
202        Casts.push_back(CE);
203      else if (CE->getCastKind() != CK_NoOp)
204        break;
205
206      Inner = CE->getSubExpr()->IgnoreParens();
207    }
208  }
209
210  // Create a temporary object region for the inner expression (which may have
211  // a more derived type) and bind the value into it.
212  const TypedValueRegion *TR = NULL;
213  if (const MaterializeTemporaryExpr *MT =
214          dyn_cast<MaterializeTemporaryExpr>(Result)) {
215    StorageDuration SD = MT->getStorageDuration();
216    // If this object is bound to a reference with static storage duration, we
217    // put it in a different region to prevent "address leakage" warnings.
218    if (SD == SD_Static || SD == SD_Thread)
219        TR = MRMgr.getCXXStaticTempObjectRegion(Inner);
220  }
221  if (!TR)
222    TR = MRMgr.getCXXTempObjectRegion(Inner, LC);
223
224  SVal Reg = loc::MemRegionVal(TR);
225
226  if (V.isUnknown())
227    V = getSValBuilder().conjureSymbolVal(Result, LC, TR->getValueType(),
228                                          currBldrCtx->blockCount());
229  State = State->bindLoc(Reg, V);
230
231  // Re-apply the casts (from innermost to outermost) for type sanity.
232  for (SmallVectorImpl<const CastExpr *>::reverse_iterator I = Casts.rbegin(),
233                                                           E = Casts.rend();
234       I != E; ++I) {
235    Reg = StoreMgr.evalDerivedToBase(Reg, *I);
236  }
237
238  State = State->BindExpr(Result, LC, Reg);
239  return State;
240}
241
242//===----------------------------------------------------------------------===//
243// Top-level transfer function logic (Dispatcher).
244//===----------------------------------------------------------------------===//
245
246/// evalAssume - Called by ConstraintManager. Used to call checker-specific
247///  logic for handling assumptions on symbolic values.
248ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
249                                              SVal cond, bool assumption) {
250  return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
251}
252
253bool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) {
254  return getCheckerManager().wantsRegionChangeUpdate(state);
255}
256
257ProgramStateRef
258ExprEngine::processRegionChanges(ProgramStateRef state,
259                                 const InvalidatedSymbols *invalidated,
260                                 ArrayRef<const MemRegion *> Explicits,
261                                 ArrayRef<const MemRegion *> Regions,
262                                 const CallEvent *Call) {
263  return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
264                                                      Explicits, Regions, Call);
265}
266
267void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State,
268                            const char *NL, const char *Sep) {
269  getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep);
270}
271
272void ExprEngine::processEndWorklist(bool hasWorkRemaining) {
273  getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
274}
275
276void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
277                                   unsigned StmtIdx, NodeBuilderContext *Ctx) {
278  PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
279  currStmtIdx = StmtIdx;
280  currBldrCtx = Ctx;
281
282  switch (E.getKind()) {
283    case CFGElement::Statement:
284      ProcessStmt(const_cast<Stmt*>(E.castAs<CFGStmt>().getStmt()), Pred);
285      return;
286    case CFGElement::Initializer:
287      ProcessInitializer(E.castAs<CFGInitializer>().getInitializer(), Pred);
288      return;
289    case CFGElement::AutomaticObjectDtor:
290    case CFGElement::BaseDtor:
291    case CFGElement::MemberDtor:
292    case CFGElement::TemporaryDtor:
293      ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
294      return;
295  }
296}
297
298static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
299                                     const CFGStmt S,
300                                     const ExplodedNode *Pred,
301                                     const LocationContext *LC) {
302
303  // Are we never purging state values?
304  if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
305    return false;
306
307  // Is this the beginning of a basic block?
308  if (Pred->getLocation().getAs<BlockEntrance>())
309    return true;
310
311  // Is this on a non-expression?
312  if (!isa<Expr>(S.getStmt()))
313    return true;
314
315  // Run before processing a call.
316  if (CallEvent::isCallStmt(S.getStmt()))
317    return true;
318
319  // Is this an expression that is consumed by another expression?  If so,
320  // postpone cleaning out the state.
321  ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
322  return !PM.isConsumedExpr(cast<Expr>(S.getStmt()));
323}
324
325void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
326                            const Stmt *ReferenceStmt,
327                            const LocationContext *LC,
328                            const Stmt *DiagnosticStmt,
329                            ProgramPoint::Kind K) {
330  assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
331          ReferenceStmt == 0 || isa<ReturnStmt>(ReferenceStmt))
332          && "PostStmt is not generally supported by the SymbolReaper yet");
333  assert(LC && "Must pass the current (or expiring) LocationContext");
334
335  if (!DiagnosticStmt) {
336    DiagnosticStmt = ReferenceStmt;
337    assert(DiagnosticStmt && "Required for clearing a LocationContext");
338  }
339
340  NumRemoveDeadBindings++;
341  ProgramStateRef CleanedState = Pred->getState();
342
343  // LC is the location context being destroyed, but SymbolReaper wants a
344  // location context that is still live. (If this is the top-level stack
345  // frame, this will be null.)
346  if (!ReferenceStmt) {
347    assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
348           "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
349    LC = LC->getParent();
350  }
351
352  const StackFrameContext *SFC = LC ? LC->getCurrentStackFrame() : 0;
353  SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
354
355  getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
356
357  // Create a state in which dead bindings are removed from the environment
358  // and the store. TODO: The function should just return new env and store,
359  // not a new state.
360  CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
361
362  // Process any special transfer function for dead symbols.
363  // A tag to track convenience transitions, which can be removed at cleanup.
364  static SimpleProgramPointTag cleanupTag("ExprEngine : Clean Node");
365  if (!SymReaper.hasDeadSymbols()) {
366    // Generate a CleanedNode that has the environment and store cleaned
367    // up. Since no symbols are dead, we can optimize and not clean out
368    // the constraint manager.
369    StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx);
370    Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K);
371
372  } else {
373    // Call checkers with the non-cleaned state so that they could query the
374    // values of the soon to be dead symbols.
375    ExplodedNodeSet CheckedSet;
376    getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
377                                                  DiagnosticStmt, *this, K);
378
379    // For each node in CheckedSet, generate CleanedNodes that have the
380    // environment, the store, and the constraints cleaned up but have the
381    // user-supplied states as the predecessors.
382    StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
383    for (ExplodedNodeSet::const_iterator
384          I = CheckedSet.begin(), E = CheckedSet.end(); I != E; ++I) {
385      ProgramStateRef CheckerState = (*I)->getState();
386
387      // The constraint manager has not been cleaned up yet, so clean up now.
388      CheckerState = getConstraintManager().removeDeadBindings(CheckerState,
389                                                               SymReaper);
390
391      assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
392        "Checkers are not allowed to modify the Environment as a part of "
393        "checkDeadSymbols processing.");
394      assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
395        "Checkers are not allowed to modify the Store as a part of "
396        "checkDeadSymbols processing.");
397
398      // Create a state based on CleanedState with CheckerState GDM and
399      // generate a transition to that state.
400      ProgramStateRef CleanedCheckerSt =
401        StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
402      Bldr.generateNode(DiagnosticStmt, *I, CleanedCheckerSt, &cleanupTag, K);
403    }
404  }
405}
406
407void ExprEngine::ProcessStmt(const CFGStmt S,
408                             ExplodedNode *Pred) {
409  // Reclaim any unnecessary nodes in the ExplodedGraph.
410  G.reclaimRecentlyAllocatedNodes();
411
412  const Stmt *currStmt = S.getStmt();
413  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
414                                currStmt->getLocStart(),
415                                "Error evaluating statement");
416
417  // Remove dead bindings and symbols.
418  ExplodedNodeSet CleanedStates;
419  if (shouldRemoveDeadBindings(AMgr, S, Pred, Pred->getLocationContext())){
420    removeDead(Pred, CleanedStates, currStmt, Pred->getLocationContext());
421  } else
422    CleanedStates.Add(Pred);
423
424  // Visit the statement.
425  ExplodedNodeSet Dst;
426  for (ExplodedNodeSet::iterator I = CleanedStates.begin(),
427                                 E = CleanedStates.end(); I != E; ++I) {
428    ExplodedNodeSet DstI;
429    // Visit the statement.
430    Visit(currStmt, *I, DstI);
431    Dst.insert(DstI);
432  }
433
434  // Enqueue the new nodes onto the work list.
435  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
436}
437
438void ExprEngine::ProcessInitializer(const CFGInitializer Init,
439                                    ExplodedNode *Pred) {
440  const CXXCtorInitializer *BMI = Init.getInitializer();
441
442  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
443                                BMI->getSourceLocation(),
444                                "Error evaluating initializer");
445
446  // We don't clean up dead bindings here.
447  const StackFrameContext *stackFrame =
448                           cast<StackFrameContext>(Pred->getLocationContext());
449  const CXXConstructorDecl *decl =
450                           cast<CXXConstructorDecl>(stackFrame->getDecl());
451
452  ProgramStateRef State = Pred->getState();
453  SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));
454
455  ExplodedNodeSet Tmp(Pred);
456  SVal FieldLoc;
457
458  // Evaluate the initializer, if necessary
459  if (BMI->isAnyMemberInitializer()) {
460    // Constructors build the object directly in the field,
461    // but non-objects must be copied in from the initializer.
462    const Expr *Init = BMI->getInit()->IgnoreImplicit();
463    if (!isa<CXXConstructExpr>(Init)) {
464      const ValueDecl *Field;
465      if (BMI->isIndirectMemberInitializer()) {
466        Field = BMI->getIndirectMember();
467        FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);
468      } else {
469        Field = BMI->getMember();
470        FieldLoc = State->getLValue(BMI->getMember(), thisVal);
471      }
472
473      SVal InitVal;
474      if (BMI->getNumArrayIndices() > 0) {
475        // Handle arrays of trivial type. We can represent this with a
476        // primitive load/copy from the base array region.
477        const ArraySubscriptExpr *ASE;
478        while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))
479          Init = ASE->getBase()->IgnoreImplicit();
480
481        SVal LValue = State->getSVal(Init, stackFrame);
482        if (Optional<Loc> LValueLoc = LValue.getAs<Loc>())
483          InitVal = State->getSVal(*LValueLoc);
484
485        // If we fail to get the value for some reason, use a symbolic value.
486        if (InitVal.isUnknownOrUndef()) {
487          SValBuilder &SVB = getSValBuilder();
488          InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame,
489                                         Field->getType(),
490                                         currBldrCtx->blockCount());
491        }
492      } else {
493        InitVal = State->getSVal(BMI->getInit(), stackFrame);
494      }
495
496      assert(Tmp.size() == 1 && "have not generated any new nodes yet");
497      assert(*Tmp.begin() == Pred && "have not generated any new nodes yet");
498      Tmp.clear();
499
500      PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
501      evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);
502    }
503  } else {
504    assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
505    // We already did all the work when visiting the CXXConstructExpr.
506  }
507
508  // Construct PostInitializer nodes whether the state changed or not,
509  // so that the diagnostics don't get confused.
510  PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
511  ExplodedNodeSet Dst;
512  NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
513  for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) {
514    ExplodedNode *N = *I;
515    Bldr.generateNode(PP, N->getState(), N);
516  }
517
518  // Enqueue the new nodes onto the work list.
519  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
520}
521
522void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
523                                     ExplodedNode *Pred) {
524  ExplodedNodeSet Dst;
525  switch (D.getKind()) {
526  case CFGElement::AutomaticObjectDtor:
527    ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);
528    break;
529  case CFGElement::BaseDtor:
530    ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst);
531    break;
532  case CFGElement::MemberDtor:
533    ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst);
534    break;
535  case CFGElement::TemporaryDtor:
536    ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst);
537    break;
538  default:
539    llvm_unreachable("Unexpected dtor kind.");
540  }
541
542  // Enqueue the new nodes onto the work list.
543  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
544}
545
546void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
547                                         ExplodedNode *Pred,
548                                         ExplodedNodeSet &Dst) {
549  const VarDecl *varDecl = Dtor.getVarDecl();
550  QualType varType = varDecl->getType();
551
552  ProgramStateRef state = Pred->getState();
553  SVal dest = state->getLValue(varDecl, Pred->getLocationContext());
554  const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();
555
556  if (const ReferenceType *refType = varType->getAs<ReferenceType>()) {
557    varType = refType->getPointeeType();
558    Region = state->getSVal(Region).getAsRegion();
559  }
560
561  VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(), /*IsBase=*/ false,
562                     Pred, Dst);
563}
564
565void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
566                                 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
567  const LocationContext *LCtx = Pred->getLocationContext();
568  ProgramStateRef State = Pred->getState();
569
570  const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
571  Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,
572                                            LCtx->getCurrentStackFrame());
573  SVal ThisVal = Pred->getState()->getSVal(ThisPtr);
574
575  // Create the base object region.
576  const CXXBaseSpecifier *Base = D.getBaseSpecifier();
577  QualType BaseTy = Base->getType();
578  SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy,
579                                                     Base->isVirtual());
580
581  VisitCXXDestructor(BaseTy, BaseVal.castAs<loc::MemRegionVal>().getRegion(),
582                     CurDtor->getBody(), /*IsBase=*/ true, Pred, Dst);
583}
584
585void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
586                                   ExplodedNode *Pred, ExplodedNodeSet &Dst) {
587  const FieldDecl *Member = D.getFieldDecl();
588  ProgramStateRef State = Pred->getState();
589  const LocationContext *LCtx = Pred->getLocationContext();
590
591  const CXXDestructorDecl *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
592  Loc ThisVal = getSValBuilder().getCXXThis(CurDtor,
593                                            LCtx->getCurrentStackFrame());
594  SVal FieldVal =
595      State->getLValue(Member, State->getSVal(ThisVal).castAs<Loc>());
596
597  VisitCXXDestructor(Member->getType(),
598                     FieldVal.castAs<loc::MemRegionVal>().getRegion(),
599                     CurDtor->getBody(), /*IsBase=*/false, Pred, Dst);
600}
601
602void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
603                                      ExplodedNode *Pred,
604                                      ExplodedNodeSet &Dst) {}
605
606void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
607                       ExplodedNodeSet &DstTop) {
608  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
609                                S->getLocStart(),
610                                "Error evaluating statement");
611  ExplodedNodeSet Dst;
612  StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
613
614  assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
615
616  switch (S->getStmtClass()) {
617    // C++ and ARC stuff we don't support yet.
618    case Expr::ObjCIndirectCopyRestoreExprClass:
619    case Stmt::CXXDependentScopeMemberExprClass:
620    case Stmt::CXXTryStmtClass:
621    case Stmt::CXXTypeidExprClass:
622    case Stmt::CXXUuidofExprClass:
623    case Stmt::MSPropertyRefExprClass:
624    case Stmt::CXXUnresolvedConstructExprClass:
625    case Stmt::DependentScopeDeclRefExprClass:
626    case Stmt::UnaryTypeTraitExprClass:
627    case Stmt::BinaryTypeTraitExprClass:
628    case Stmt::TypeTraitExprClass:
629    case Stmt::ArrayTypeTraitExprClass:
630    case Stmt::ExpressionTraitExprClass:
631    case Stmt::UnresolvedLookupExprClass:
632    case Stmt::UnresolvedMemberExprClass:
633    case Stmt::CXXNoexceptExprClass:
634    case Stmt::PackExpansionExprClass:
635    case Stmt::SubstNonTypeTemplateParmPackExprClass:
636    case Stmt::FunctionParmPackExprClass:
637    case Stmt::SEHTryStmtClass:
638    case Stmt::SEHExceptStmtClass:
639    case Stmt::LambdaExprClass:
640    case Stmt::SEHFinallyStmtClass: {
641      const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
642      Engine.addAbortedBlock(node, currBldrCtx->getBlock());
643      break;
644    }
645
646    case Stmt::ParenExprClass:
647      llvm_unreachable("ParenExprs already handled.");
648    case Stmt::GenericSelectionExprClass:
649      llvm_unreachable("GenericSelectionExprs already handled.");
650    // Cases that should never be evaluated simply because they shouldn't
651    // appear in the CFG.
652    case Stmt::BreakStmtClass:
653    case Stmt::CaseStmtClass:
654    case Stmt::CompoundStmtClass:
655    case Stmt::ContinueStmtClass:
656    case Stmt::CXXForRangeStmtClass:
657    case Stmt::DefaultStmtClass:
658    case Stmt::DoStmtClass:
659    case Stmt::ForStmtClass:
660    case Stmt::GotoStmtClass:
661    case Stmt::IfStmtClass:
662    case Stmt::IndirectGotoStmtClass:
663    case Stmt::LabelStmtClass:
664    case Stmt::NoStmtClass:
665    case Stmt::NullStmtClass:
666    case Stmt::SwitchStmtClass:
667    case Stmt::WhileStmtClass:
668    case Expr::MSDependentExistsStmtClass:
669    case Stmt::CapturedStmtClass:
670    case Stmt::OMPParallelDirectiveClass:
671      llvm_unreachable("Stmt should not be in analyzer evaluation loop");
672
673    case Stmt::ObjCSubscriptRefExprClass:
674    case Stmt::ObjCPropertyRefExprClass:
675      llvm_unreachable("These are handled by PseudoObjectExpr");
676
677    case Stmt::GNUNullExprClass: {
678      // GNU __null is a pointer-width integer, not an actual pointer.
679      ProgramStateRef state = Pred->getState();
680      state = state->BindExpr(S, Pred->getLocationContext(),
681                              svalBuilder.makeIntValWithPtrWidth(0, false));
682      Bldr.generateNode(S, Pred, state);
683      break;
684    }
685
686    case Stmt::ObjCAtSynchronizedStmtClass:
687      Bldr.takeNodes(Pred);
688      VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
689      Bldr.addNodes(Dst);
690      break;
691
692    case Stmt::ExprWithCleanupsClass:
693      // Handled due to fully linearised CFG.
694      break;
695
696    // Cases not handled yet; but will handle some day.
697    case Stmt::DesignatedInitExprClass:
698    case Stmt::ExtVectorElementExprClass:
699    case Stmt::ImaginaryLiteralClass:
700    case Stmt::ObjCAtCatchStmtClass:
701    case Stmt::ObjCAtFinallyStmtClass:
702    case Stmt::ObjCAtTryStmtClass:
703    case Stmt::ObjCAutoreleasePoolStmtClass:
704    case Stmt::ObjCEncodeExprClass:
705    case Stmt::ObjCIsaExprClass:
706    case Stmt::ObjCProtocolExprClass:
707    case Stmt::ObjCSelectorExprClass:
708    case Stmt::ParenListExprClass:
709    case Stmt::PredefinedExprClass:
710    case Stmt::ShuffleVectorExprClass:
711    case Stmt::VAArgExprClass:
712    case Stmt::CUDAKernelCallExprClass:
713    case Stmt::OpaqueValueExprClass:
714    case Stmt::AsTypeExprClass:
715    case Stmt::AtomicExprClass:
716      // Fall through.
717
718    // Cases we intentionally don't evaluate, since they don't need
719    // to be explicitly evaluated.
720    case Stmt::AddrLabelExprClass:
721    case Stmt::AttributedStmtClass:
722    case Stmt::IntegerLiteralClass:
723    case Stmt::CharacterLiteralClass:
724    case Stmt::ImplicitValueInitExprClass:
725    case Stmt::CXXScalarValueInitExprClass:
726    case Stmt::CXXBoolLiteralExprClass:
727    case Stmt::ObjCBoolLiteralExprClass:
728    case Stmt::FloatingLiteralClass:
729    case Stmt::SizeOfPackExprClass:
730    case Stmt::StringLiteralClass:
731    case Stmt::ObjCStringLiteralClass:
732    case Stmt::CXXBindTemporaryExprClass:
733    case Stmt::CXXPseudoDestructorExprClass:
734    case Stmt::SubstNonTypeTemplateParmExprClass:
735    case Stmt::CXXNullPtrLiteralExprClass: {
736      Bldr.takeNodes(Pred);
737      ExplodedNodeSet preVisit;
738      getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
739      getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
740      Bldr.addNodes(Dst);
741      break;
742    }
743
744    case Stmt::CXXDefaultArgExprClass:
745    case Stmt::CXXDefaultInitExprClass: {
746      Bldr.takeNodes(Pred);
747      ExplodedNodeSet PreVisit;
748      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
749
750      ExplodedNodeSet Tmp;
751      StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
752
753      const Expr *ArgE;
754      if (const CXXDefaultArgExpr *DefE = dyn_cast<CXXDefaultArgExpr>(S))
755        ArgE = DefE->getExpr();
756      else if (const CXXDefaultInitExpr *DefE = dyn_cast<CXXDefaultInitExpr>(S))
757        ArgE = DefE->getExpr();
758      else
759        llvm_unreachable("unknown constant wrapper kind");
760
761      bool IsTemporary = false;
762      if (const MaterializeTemporaryExpr *MTE =
763            dyn_cast<MaterializeTemporaryExpr>(ArgE)) {
764        ArgE = MTE->GetTemporaryExpr();
765        IsTemporary = true;
766      }
767
768      Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE);
769      if (!ConstantVal)
770        ConstantVal = UnknownVal();
771
772      const LocationContext *LCtx = Pred->getLocationContext();
773      for (ExplodedNodeSet::iterator I = PreVisit.begin(), E = PreVisit.end();
774           I != E; ++I) {
775        ProgramStateRef State = (*I)->getState();
776        State = State->BindExpr(S, LCtx, *ConstantVal);
777        if (IsTemporary)
778          State = createTemporaryRegionIfNeeded(State, LCtx,
779                                                cast<Expr>(S),
780                                                cast<Expr>(S));
781        Bldr2.generateNode(S, *I, State);
782      }
783
784      getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
785      Bldr.addNodes(Dst);
786      break;
787    }
788
789    // Cases we evaluate as opaque expressions, conjuring a symbol.
790    case Stmt::CXXStdInitializerListExprClass:
791    case Expr::ObjCArrayLiteralClass:
792    case Expr::ObjCDictionaryLiteralClass:
793    case Expr::ObjCBoxedExprClass: {
794      Bldr.takeNodes(Pred);
795
796      ExplodedNodeSet preVisit;
797      getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
798
799      ExplodedNodeSet Tmp;
800      StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
801
802      const Expr *Ex = cast<Expr>(S);
803      QualType resultType = Ex->getType();
804
805      for (ExplodedNodeSet::iterator it = preVisit.begin(), et = preVisit.end();
806           it != et; ++it) {
807        ExplodedNode *N = *it;
808        const LocationContext *LCtx = N->getLocationContext();
809        SVal result = svalBuilder.conjureSymbolVal(0, Ex, LCtx, resultType,
810                                                   currBldrCtx->blockCount());
811        ProgramStateRef state = N->getState()->BindExpr(Ex, LCtx, result);
812        Bldr2.generateNode(S, N, state);
813      }
814
815      getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
816      Bldr.addNodes(Dst);
817      break;
818    }
819
820    case Stmt::ArraySubscriptExprClass:
821      Bldr.takeNodes(Pred);
822      VisitLvalArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
823      Bldr.addNodes(Dst);
824      break;
825
826    case Stmt::GCCAsmStmtClass:
827      Bldr.takeNodes(Pred);
828      VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
829      Bldr.addNodes(Dst);
830      break;
831
832    case Stmt::MSAsmStmtClass:
833      Bldr.takeNodes(Pred);
834      VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
835      Bldr.addNodes(Dst);
836      break;
837
838    case Stmt::BlockExprClass:
839      Bldr.takeNodes(Pred);
840      VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
841      Bldr.addNodes(Dst);
842      break;
843
844    case Stmt::BinaryOperatorClass: {
845      const BinaryOperator* B = cast<BinaryOperator>(S);
846      if (B->isLogicalOp()) {
847        Bldr.takeNodes(Pred);
848        VisitLogicalExpr(B, Pred, Dst);
849        Bldr.addNodes(Dst);
850        break;
851      }
852      else if (B->getOpcode() == BO_Comma) {
853        ProgramStateRef state = Pred->getState();
854        Bldr.generateNode(B, Pred,
855                          state->BindExpr(B, Pred->getLocationContext(),
856                                          state->getSVal(B->getRHS(),
857                                                  Pred->getLocationContext())));
858        break;
859      }
860
861      Bldr.takeNodes(Pred);
862
863      if (AMgr.options.eagerlyAssumeBinOpBifurcation &&
864          (B->isRelationalOp() || B->isEqualityOp())) {
865        ExplodedNodeSet Tmp;
866        VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
867        evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
868      }
869      else
870        VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
871
872      Bldr.addNodes(Dst);
873      break;
874    }
875
876    case Stmt::CXXOperatorCallExprClass: {
877      const CXXOperatorCallExpr *OCE = cast<CXXOperatorCallExpr>(S);
878
879      // For instance method operators, make sure the 'this' argument has a
880      // valid region.
881      const Decl *Callee = OCE->getCalleeDecl();
882      if (const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
883        if (MD->isInstance()) {
884          ProgramStateRef State = Pred->getState();
885          const LocationContext *LCtx = Pred->getLocationContext();
886          ProgramStateRef NewState =
887            createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
888          if (NewState != State) {
889            Pred = Bldr.generateNode(OCE, Pred, NewState, /*Tag=*/0,
890                                     ProgramPoint::PreStmtKind);
891            // Did we cache out?
892            if (!Pred)
893              break;
894          }
895        }
896      }
897      // FALLTHROUGH
898    }
899    case Stmt::CallExprClass:
900    case Stmt::CXXMemberCallExprClass:
901    case Stmt::UserDefinedLiteralClass: {
902      Bldr.takeNodes(Pred);
903      VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
904      Bldr.addNodes(Dst);
905      break;
906    }
907
908    case Stmt::CXXCatchStmtClass: {
909      Bldr.takeNodes(Pred);
910      VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
911      Bldr.addNodes(Dst);
912      break;
913    }
914
915    case Stmt::CXXTemporaryObjectExprClass:
916    case Stmt::CXXConstructExprClass: {
917      Bldr.takeNodes(Pred);
918      VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
919      Bldr.addNodes(Dst);
920      break;
921    }
922
923    case Stmt::CXXNewExprClass: {
924      Bldr.takeNodes(Pred);
925      ExplodedNodeSet PostVisit;
926      VisitCXXNewExpr(cast<CXXNewExpr>(S), Pred, PostVisit);
927      getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
928      Bldr.addNodes(Dst);
929      break;
930    }
931
932    case Stmt::CXXDeleteExprClass: {
933      Bldr.takeNodes(Pred);
934      ExplodedNodeSet PreVisit;
935      const CXXDeleteExpr *CDE = cast<CXXDeleteExpr>(S);
936      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
937
938      for (ExplodedNodeSet::iterator i = PreVisit.begin(),
939                                     e = PreVisit.end(); i != e ; ++i)
940        VisitCXXDeleteExpr(CDE, *i, Dst);
941
942      Bldr.addNodes(Dst);
943      break;
944    }
945      // FIXME: ChooseExpr is really a constant.  We need to fix
946      //        the CFG do not model them as explicit control-flow.
947
948    case Stmt::ChooseExprClass: { // __builtin_choose_expr
949      Bldr.takeNodes(Pred);
950      const ChooseExpr *C = cast<ChooseExpr>(S);
951      VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
952      Bldr.addNodes(Dst);
953      break;
954    }
955
956    case Stmt::CompoundAssignOperatorClass:
957      Bldr.takeNodes(Pred);
958      VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
959      Bldr.addNodes(Dst);
960      break;
961
962    case Stmt::CompoundLiteralExprClass:
963      Bldr.takeNodes(Pred);
964      VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
965      Bldr.addNodes(Dst);
966      break;
967
968    case Stmt::BinaryConditionalOperatorClass:
969    case Stmt::ConditionalOperatorClass: { // '?' operator
970      Bldr.takeNodes(Pred);
971      const AbstractConditionalOperator *C
972        = cast<AbstractConditionalOperator>(S);
973      VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
974      Bldr.addNodes(Dst);
975      break;
976    }
977
978    case Stmt::CXXThisExprClass:
979      Bldr.takeNodes(Pred);
980      VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
981      Bldr.addNodes(Dst);
982      break;
983
984    case Stmt::DeclRefExprClass: {
985      Bldr.takeNodes(Pred);
986      const DeclRefExpr *DE = cast<DeclRefExpr>(S);
987      VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
988      Bldr.addNodes(Dst);
989      break;
990    }
991
992    case Stmt::DeclStmtClass:
993      Bldr.takeNodes(Pred);
994      VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
995      Bldr.addNodes(Dst);
996      break;
997
998    case Stmt::ImplicitCastExprClass:
999    case Stmt::CStyleCastExprClass:
1000    case Stmt::CXXStaticCastExprClass:
1001    case Stmt::CXXDynamicCastExprClass:
1002    case Stmt::CXXReinterpretCastExprClass:
1003    case Stmt::CXXConstCastExprClass:
1004    case Stmt::CXXFunctionalCastExprClass:
1005    case Stmt::ObjCBridgedCastExprClass: {
1006      Bldr.takeNodes(Pred);
1007      const CastExpr *C = cast<CastExpr>(S);
1008      // Handle the previsit checks.
1009      ExplodedNodeSet dstPrevisit;
1010      getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, C, *this);
1011
1012      // Handle the expression itself.
1013      ExplodedNodeSet dstExpr;
1014      for (ExplodedNodeSet::iterator i = dstPrevisit.begin(),
1015                                     e = dstPrevisit.end(); i != e ; ++i) {
1016        VisitCast(C, C->getSubExpr(), *i, dstExpr);
1017      }
1018
1019      // Handle the postvisit checks.
1020      getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
1021      Bldr.addNodes(Dst);
1022      break;
1023    }
1024
1025    case Expr::MaterializeTemporaryExprClass: {
1026      Bldr.takeNodes(Pred);
1027      const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S);
1028      CreateCXXTemporaryObject(MTE, Pred, Dst);
1029      Bldr.addNodes(Dst);
1030      break;
1031    }
1032
1033    case Stmt::InitListExprClass:
1034      Bldr.takeNodes(Pred);
1035      VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
1036      Bldr.addNodes(Dst);
1037      break;
1038
1039    case Stmt::MemberExprClass:
1040      Bldr.takeNodes(Pred);
1041      VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
1042      Bldr.addNodes(Dst);
1043      break;
1044
1045    case Stmt::ObjCIvarRefExprClass:
1046      Bldr.takeNodes(Pred);
1047      VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
1048      Bldr.addNodes(Dst);
1049      break;
1050
1051    case Stmt::ObjCForCollectionStmtClass:
1052      Bldr.takeNodes(Pred);
1053      VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
1054      Bldr.addNodes(Dst);
1055      break;
1056
1057    case Stmt::ObjCMessageExprClass:
1058      Bldr.takeNodes(Pred);
1059      VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
1060      Bldr.addNodes(Dst);
1061      break;
1062
1063    case Stmt::ObjCAtThrowStmtClass:
1064    case Stmt::CXXThrowExprClass:
1065      // FIXME: This is not complete.  We basically treat @throw as
1066      // an abort.
1067      Bldr.generateSink(S, Pred, Pred->getState());
1068      break;
1069
1070    case Stmt::ReturnStmtClass:
1071      Bldr.takeNodes(Pred);
1072      VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
1073      Bldr.addNodes(Dst);
1074      break;
1075
1076    case Stmt::OffsetOfExprClass:
1077      Bldr.takeNodes(Pred);
1078      VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Pred, Dst);
1079      Bldr.addNodes(Dst);
1080      break;
1081
1082    case Stmt::UnaryExprOrTypeTraitExprClass:
1083      Bldr.takeNodes(Pred);
1084      VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
1085                                    Pred, Dst);
1086      Bldr.addNodes(Dst);
1087      break;
1088
1089    case Stmt::StmtExprClass: {
1090      const StmtExpr *SE = cast<StmtExpr>(S);
1091
1092      if (SE->getSubStmt()->body_empty()) {
1093        // Empty statement expression.
1094        assert(SE->getType() == getContext().VoidTy
1095               && "Empty statement expression must have void type.");
1096        break;
1097      }
1098
1099      if (Expr *LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1100        ProgramStateRef state = Pred->getState();
1101        Bldr.generateNode(SE, Pred,
1102                          state->BindExpr(SE, Pred->getLocationContext(),
1103                                          state->getSVal(LastExpr,
1104                                                  Pred->getLocationContext())));
1105      }
1106      break;
1107    }
1108
1109    case Stmt::UnaryOperatorClass: {
1110      Bldr.takeNodes(Pred);
1111      const UnaryOperator *U = cast<UnaryOperator>(S);
1112      if (AMgr.options.eagerlyAssumeBinOpBifurcation && (U->getOpcode() == UO_LNot)) {
1113        ExplodedNodeSet Tmp;
1114        VisitUnaryOperator(U, Pred, Tmp);
1115        evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
1116      }
1117      else
1118        VisitUnaryOperator(U, Pred, Dst);
1119      Bldr.addNodes(Dst);
1120      break;
1121    }
1122
1123    case Stmt::PseudoObjectExprClass: {
1124      Bldr.takeNodes(Pred);
1125      ProgramStateRef state = Pred->getState();
1126      const PseudoObjectExpr *PE = cast<PseudoObjectExpr>(S);
1127      if (const Expr *Result = PE->getResultExpr()) {
1128        SVal V = state->getSVal(Result, Pred->getLocationContext());
1129        Bldr.generateNode(S, Pred,
1130                          state->BindExpr(S, Pred->getLocationContext(), V));
1131      }
1132      else
1133        Bldr.generateNode(S, Pred,
1134                          state->BindExpr(S, Pred->getLocationContext(),
1135                                                   UnknownVal()));
1136
1137      Bldr.addNodes(Dst);
1138      break;
1139    }
1140  }
1141}
1142
1143bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
1144                                       const LocationContext *CalleeLC) {
1145  const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame();
1146  const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame();
1147  assert(CalleeSF && CallerSF);
1148  ExplodedNode *BeforeProcessingCall = 0;
1149  const Stmt *CE = CalleeSF->getCallSite();
1150
1151  // Find the first node before we started processing the call expression.
1152  while (N) {
1153    ProgramPoint L = N->getLocation();
1154    BeforeProcessingCall = N;
1155    N = N->pred_empty() ? NULL : *(N->pred_begin());
1156
1157    // Skip the nodes corresponding to the inlined code.
1158    if (L.getLocationContext()->getCurrentStackFrame() != CallerSF)
1159      continue;
1160    // We reached the caller. Find the node right before we started
1161    // processing the call.
1162    if (L.isPurgeKind())
1163      continue;
1164    if (L.getAs<PreImplicitCall>())
1165      continue;
1166    if (L.getAs<CallEnter>())
1167      continue;
1168    if (Optional<StmtPoint> SP = L.getAs<StmtPoint>())
1169      if (SP->getStmt() == CE)
1170        continue;
1171    break;
1172  }
1173
1174  if (!BeforeProcessingCall)
1175    return false;
1176
1177  // TODO: Clean up the unneeded nodes.
1178
1179  // Build an Epsilon node from which we will restart the analyzes.
1180  // Note that CE is permitted to be NULL!
1181  ProgramPoint NewNodeLoc =
1182               EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
1183  // Add the special flag to GDM to signal retrying with no inlining.
1184  // Note, changing the state ensures that we are not going to cache out.
1185  ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
1186  NewNodeState =
1187    NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
1188
1189  // Make the new node a successor of BeforeProcessingCall.
1190  bool IsNew = false;
1191  ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
1192  // We cached out at this point. Caching out is common due to us backtracking
1193  // from the inlined function, which might spawn several paths.
1194  if (!IsNew)
1195    return true;
1196
1197  NewNode->addPredecessor(BeforeProcessingCall, G);
1198
1199  // Add the new node to the work list.
1200  Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
1201                                  CalleeSF->getIndex());
1202  NumTimesRetriedWithoutInlining++;
1203  return true;
1204}
1205
1206/// Block entrance.  (Update counters).
1207void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
1208                                         NodeBuilderWithSinks &nodeBuilder,
1209                                         ExplodedNode *Pred) {
1210  PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
1211
1212  // FIXME: Refactor this into a checker.
1213  if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) {
1214    static SimpleProgramPointTag tag("ExprEngine : Block count exceeded");
1215    const ExplodedNode *Sink =
1216                   nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
1217
1218    // Check if we stopped at the top level function or not.
1219    // Root node should have the location context of the top most function.
1220    const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
1221    const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame();
1222    const LocationContext *RootLC =
1223                        (*G.roots_begin())->getLocation().getLocationContext();
1224    if (RootLC->getCurrentStackFrame() != CalleeSF) {
1225      Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
1226
1227      // Re-run the call evaluation without inlining it, by storing the
1228      // no-inlining policy in the state and enqueuing the new work item on
1229      // the list. Replay should almost never fail. Use the stats to catch it
1230      // if it does.
1231      if ((!AMgr.options.NoRetryExhausted &&
1232           replayWithoutInlining(Pred, CalleeLC)))
1233        return;
1234      NumMaxBlockCountReachedInInlined++;
1235    } else
1236      NumMaxBlockCountReached++;
1237
1238    // Make sink nodes as exhausted(for stats) only if retry failed.
1239    Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
1240  }
1241}
1242
1243//===----------------------------------------------------------------------===//
1244// Branch processing.
1245//===----------------------------------------------------------------------===//
1246
1247/// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1248/// to try to recover some path-sensitivity for casts of symbolic
1249/// integers that promote their values (which are currently not tracked well).
1250/// This function returns the SVal bound to Condition->IgnoreCasts if all the
1251//  cast(s) did was sign-extend the original value.
1252static SVal RecoverCastedSymbol(ProgramStateManager& StateMgr,
1253                                ProgramStateRef state,
1254                                const Stmt *Condition,
1255                                const LocationContext *LCtx,
1256                                ASTContext &Ctx) {
1257
1258  const Expr *Ex = dyn_cast<Expr>(Condition);
1259  if (!Ex)
1260    return UnknownVal();
1261
1262  uint64_t bits = 0;
1263  bool bitsInit = false;
1264
1265  while (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
1266    QualType T = CE->getType();
1267
1268    if (!T->isIntegralOrEnumerationType())
1269      return UnknownVal();
1270
1271    uint64_t newBits = Ctx.getTypeSize(T);
1272    if (!bitsInit || newBits < bits) {
1273      bitsInit = true;
1274      bits = newBits;
1275    }
1276
1277    Ex = CE->getSubExpr();
1278  }
1279
1280  // We reached a non-cast.  Is it a symbolic value?
1281  QualType T = Ex->getType();
1282
1283  if (!bitsInit || !T->isIntegralOrEnumerationType() ||
1284      Ctx.getTypeSize(T) > bits)
1285    return UnknownVal();
1286
1287  return state->getSVal(Ex, LCtx);
1288}
1289
1290static const Stmt *ResolveCondition(const Stmt *Condition,
1291                                    const CFGBlock *B) {
1292  if (const Expr *Ex = dyn_cast<Expr>(Condition))
1293    Condition = Ex->IgnoreParens();
1294
1295  const BinaryOperator *BO = dyn_cast<BinaryOperator>(Condition);
1296  if (!BO || !BO->isLogicalOp())
1297    return Condition;
1298
1299  // For logical operations, we still have the case where some branches
1300  // use the traditional "merge" approach and others sink the branch
1301  // directly into the basic blocks representing the logical operation.
1302  // We need to distinguish between those two cases here.
1303
1304  // The invariants are still shifting, but it is possible that the
1305  // last element in a CFGBlock is not a CFGStmt.  Look for the last
1306  // CFGStmt as the value of the condition.
1307  CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
1308  for (; I != E; ++I) {
1309    CFGElement Elem = *I;
1310    Optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
1311    if (!CS)
1312      continue;
1313    if (CS->getStmt() != Condition)
1314      break;
1315    return Condition;
1316  }
1317
1318  assert(I != E);
1319
1320  while (Condition) {
1321    BO = dyn_cast<BinaryOperator>(Condition);
1322    if (!BO || !BO->isLogicalOp())
1323      return Condition;
1324    Condition = BO->getRHS()->IgnoreParens();
1325  }
1326  llvm_unreachable("could not resolve condition");
1327}
1328
1329void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
1330                               NodeBuilderContext& BldCtx,
1331                               ExplodedNode *Pred,
1332                               ExplodedNodeSet &Dst,
1333                               const CFGBlock *DstT,
1334                               const CFGBlock *DstF) {
1335  PrettyStackTraceLocationContext StackCrashInfo(Pred->getLocationContext());
1336  currBldrCtx = &BldCtx;
1337
1338  // Check for NULL conditions; e.g. "for(;;)"
1339  if (!Condition) {
1340    BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
1341    NullCondBldr.markInfeasible(false);
1342    NullCondBldr.generateNode(Pred->getState(), true, Pred);
1343    return;
1344  }
1345
1346  SValBuilder &SVB = Pred->getState()->getStateManager().getSValBuilder();
1347  SVal TrueVal = SVB.makeTruthVal(true);
1348  SVal FalseVal = SVB.makeTruthVal(false);
1349
1350  // Resolve the condition in the precense of nested '||' and '&&'.
1351  if (const Expr *Ex = dyn_cast<Expr>(Condition))
1352    Condition = Ex->IgnoreParens();
1353  Condition = ResolveCondition(Condition, BldCtx.getBlock());
1354
1355  // Cast truth values to the correct type.
1356  if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1357    TrueVal = SVB.evalCast(TrueVal, Ex->getType(),
1358                           getContext().getLogicalOperationType());
1359    FalseVal = SVB.evalCast(FalseVal, Ex->getType(),
1360                            getContext().getLogicalOperationType());
1361  }
1362
1363
1364  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1365                                Condition->getLocStart(),
1366                                "Error evaluating branch");
1367
1368  ExplodedNodeSet CheckersOutSet;
1369  getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
1370                                                    Pred, *this);
1371  // We generated only sinks.
1372  if (CheckersOutSet.empty())
1373    return;
1374
1375  BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
1376  for (NodeBuilder::iterator I = CheckersOutSet.begin(),
1377                             E = CheckersOutSet.end(); E != I; ++I) {
1378    ExplodedNode *PredI = *I;
1379
1380    if (PredI->isSink())
1381      continue;
1382
1383    ProgramStateRef PrevState = PredI->getState();
1384    SVal X = PrevState->getSVal(Condition, PredI->getLocationContext());
1385
1386    if (X.isUnknownOrUndef()) {
1387      // Give it a chance to recover from unknown.
1388      if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1389        if (Ex->getType()->isIntegralOrEnumerationType()) {
1390          // Try to recover some path-sensitivity.  Right now casts of symbolic
1391          // integers that promote their values are currently not tracked well.
1392          // If 'Condition' is such an expression, try and recover the
1393          // underlying value and use that instead.
1394          SVal recovered = RecoverCastedSymbol(getStateManager(),
1395                                               PrevState, Condition,
1396                                               PredI->getLocationContext(),
1397                                               getContext());
1398
1399          if (!recovered.isUnknown()) {
1400            X = recovered;
1401          }
1402        }
1403      }
1404    }
1405
1406    ProgramStateRef StTrue, StFalse;
1407
1408    // If the condition is still unknown, give up.
1409    if (X.isUnknownOrUndef()) {
1410
1411      StTrue = PrevState->BindExpr(Condition, BldCtx.LC, TrueVal);
1412      StFalse = PrevState->BindExpr(Condition, BldCtx.LC, FalseVal);
1413
1414      builder.generateNode(StTrue, true, PredI);
1415      builder.generateNode(StFalse, false, PredI);
1416      continue;
1417    }
1418
1419    DefinedSVal V = X.castAs<DefinedSVal>();
1420    tie(StTrue, StFalse) = PrevState->assume(V);
1421
1422    // Process the true branch.
1423    if (builder.isFeasible(true)) {
1424      if (StTrue) {
1425        StTrue = StTrue->BindExpr(Condition, BldCtx.LC, TrueVal);
1426        builder.generateNode(StTrue, true, PredI);
1427      } else
1428        builder.markInfeasible(true);
1429    }
1430
1431    // Process the false branch.
1432    if (builder.isFeasible(false)) {
1433      if (StFalse) {
1434        StFalse = StFalse->BindExpr(Condition, BldCtx.LC, FalseVal);
1435        builder.generateNode(StFalse, false, PredI);
1436      } else
1437        builder.markInfeasible(false);
1438    }
1439  }
1440  currBldrCtx = 0;
1441}
1442
1443/// The GDM component containing the set of global variables which have been
1444/// previously initialized with explicit initializers.
1445REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
1446                                 llvm::ImmutableSet<const VarDecl *>)
1447
1448void ExprEngine::processStaticInitializer(const DeclStmt *DS,
1449                                          NodeBuilderContext &BuilderCtx,
1450                                          ExplodedNode *Pred,
1451                                          clang::ento::ExplodedNodeSet &Dst,
1452                                          const CFGBlock *DstT,
1453                                          const CFGBlock *DstF) {
1454  PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
1455  currBldrCtx = &BuilderCtx;
1456
1457  const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
1458  ProgramStateRef state = Pred->getState();
1459  bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
1460  BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
1461
1462  if (!initHasRun) {
1463    state = state->add<InitializedGlobalsSet>(VD);
1464  }
1465
1466  builder.generateNode(state, initHasRun, Pred);
1467  builder.markInfeasible(!initHasRun);
1468
1469  currBldrCtx = 0;
1470}
1471
1472/// processIndirectGoto - Called by CoreEngine.  Used to generate successor
1473///  nodes by processing the 'effects' of a computed goto jump.
1474void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
1475
1476  ProgramStateRef state = builder.getState();
1477  SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
1478
1479  // Three possibilities:
1480  //
1481  //   (1) We know the computed label.
1482  //   (2) The label is NULL (or some other constant), or Undefined.
1483  //   (3) We have no clue about the label.  Dispatch to all targets.
1484  //
1485
1486  typedef IndirectGotoNodeBuilder::iterator iterator;
1487
1488  if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
1489    const LabelDecl *L = LV->getLabel();
1490
1491    for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
1492      if (I.getLabel() == L) {
1493        builder.generateNode(I, state);
1494        return;
1495      }
1496    }
1497
1498    llvm_unreachable("No block with label.");
1499  }
1500
1501  if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) {
1502    // Dispatch to the first target and mark it as a sink.
1503    //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1504    // FIXME: add checker visit.
1505    //    UndefBranches.insert(N);
1506    return;
1507  }
1508
1509  // This is really a catch-all.  We don't support symbolics yet.
1510  // FIXME: Implement dispatch for symbolic pointers.
1511
1512  for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
1513    builder.generateNode(I, state);
1514}
1515
1516/// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
1517///  nodes when the control reaches the end of a function.
1518void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
1519                                      ExplodedNode *Pred) {
1520  PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
1521  StateMgr.EndPath(Pred->getState());
1522
1523  ExplodedNodeSet Dst;
1524  if (Pred->getLocationContext()->inTopFrame()) {
1525    // Remove dead symbols.
1526    ExplodedNodeSet AfterRemovedDead;
1527    removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
1528
1529    // Notify checkers.
1530    for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(),
1531        E = AfterRemovedDead.end(); I != E; ++I) {
1532      getCheckerManager().runCheckersForEndFunction(BC, Dst, *I, *this);
1533    }
1534  } else {
1535    getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this);
1536  }
1537
1538  Engine.enqueueEndOfFunction(Dst);
1539}
1540
1541/// ProcessSwitch - Called by CoreEngine.  Used to generate successor
1542///  nodes by processing the 'effects' of a switch statement.
1543void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
1544  typedef SwitchNodeBuilder::iterator iterator;
1545  ProgramStateRef state = builder.getState();
1546  const Expr *CondE = builder.getCondition();
1547  SVal  CondV_untested = state->getSVal(CondE, builder.getLocationContext());
1548
1549  if (CondV_untested.isUndef()) {
1550    //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1551    // FIXME: add checker
1552    //UndefBranches.insert(N);
1553
1554    return;
1555  }
1556  DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
1557
1558  ProgramStateRef DefaultSt = state;
1559
1560  iterator I = builder.begin(), EI = builder.end();
1561  bool defaultIsFeasible = I == EI;
1562
1563  for ( ; I != EI; ++I) {
1564    // Successor may be pruned out during CFG construction.
1565    if (!I.getBlock())
1566      continue;
1567
1568    const CaseStmt *Case = I.getCase();
1569
1570    // Evaluate the LHS of the case value.
1571    llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
1572    assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType()));
1573
1574    // Get the RHS of the case, if it exists.
1575    llvm::APSInt V2;
1576    if (const Expr *E = Case->getRHS())
1577      V2 = E->EvaluateKnownConstInt(getContext());
1578    else
1579      V2 = V1;
1580
1581    // FIXME: Eventually we should replace the logic below with a range
1582    //  comparison, rather than concretize the values within the range.
1583    //  This should be easy once we have "ranges" for NonLVals.
1584
1585    do {
1586      nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1));
1587      DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
1588                                               CondV, CaseVal);
1589
1590      // Now "assume" that the case matches.
1591      if (ProgramStateRef stateNew = state->assume(Res, true)) {
1592        builder.generateCaseStmtNode(I, stateNew);
1593
1594        // If CondV evaluates to a constant, then we know that this
1595        // is the *only* case that we can take, so stop evaluating the
1596        // others.
1597        if (CondV.getAs<nonloc::ConcreteInt>())
1598          return;
1599      }
1600
1601      // Now "assume" that the case doesn't match.  Add this state
1602      // to the default state (if it is feasible).
1603      if (DefaultSt) {
1604        if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) {
1605          defaultIsFeasible = true;
1606          DefaultSt = stateNew;
1607        }
1608        else {
1609          defaultIsFeasible = false;
1610          DefaultSt = NULL;
1611        }
1612      }
1613
1614      // Concretize the next value in the range.
1615      if (V1 == V2)
1616        break;
1617
1618      ++V1;
1619      assert (V1 <= V2);
1620
1621    } while (true);
1622  }
1623
1624  if (!defaultIsFeasible)
1625    return;
1626
1627  // If we have switch(enum value), the default branch is not
1628  // feasible if all of the enum constants not covered by 'case:' statements
1629  // are not feasible values for the switch condition.
1630  //
1631  // Note that this isn't as accurate as it could be.  Even if there isn't
1632  // a case for a particular enum value as long as that enum value isn't
1633  // feasible then it shouldn't be considered for making 'default:' reachable.
1634  const SwitchStmt *SS = builder.getSwitch();
1635  const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1636  if (CondExpr->getType()->getAs<EnumType>()) {
1637    if (SS->isAllEnumCasesCovered())
1638      return;
1639  }
1640
1641  builder.generateDefaultCaseNode(DefaultSt);
1642}
1643
1644//===----------------------------------------------------------------------===//
1645// Transfer functions: Loads and stores.
1646//===----------------------------------------------------------------------===//
1647
1648void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
1649                                        ExplodedNode *Pred,
1650                                        ExplodedNodeSet &Dst) {
1651  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1652
1653  ProgramStateRef state = Pred->getState();
1654  const LocationContext *LCtx = Pred->getLocationContext();
1655
1656  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1657    // C permits "extern void v", and if you cast the address to a valid type,
1658    // you can even do things with it. We simply pretend
1659    assert(Ex->isGLValue() || VD->getType()->isVoidType());
1660    SVal V = state->getLValue(VD, Pred->getLocationContext());
1661
1662    // For references, the 'lvalue' is the pointer address stored in the
1663    // reference region.
1664    if (VD->getType()->isReferenceType()) {
1665      if (const MemRegion *R = V.getAsRegion())
1666        V = state->getSVal(R);
1667      else
1668        V = UnknownVal();
1669    }
1670
1671    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1672                      ProgramPoint::PostLValueKind);
1673    return;
1674  }
1675  if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) {
1676    assert(!Ex->isGLValue());
1677    SVal V = svalBuilder.makeIntVal(ED->getInitVal());
1678    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
1679    return;
1680  }
1681  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
1682    SVal V = svalBuilder.getFunctionPointer(FD);
1683    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1684                      ProgramPoint::PostLValueKind);
1685    return;
1686  }
1687  if (isa<FieldDecl>(D)) {
1688    // FIXME: Compute lvalue of field pointers-to-member.
1689    // Right now we just use a non-null void pointer, so that it gives proper
1690    // results in boolean contexts.
1691    SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy,
1692                                          currBldrCtx->blockCount());
1693    state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true);
1694    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1695		      ProgramPoint::PostLValueKind);
1696    return;
1697  }
1698
1699  llvm_unreachable("Support for this Decl not implemented.");
1700}
1701
1702/// VisitArraySubscriptExpr - Transfer function for array accesses
1703void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A,
1704                                             ExplodedNode *Pred,
1705                                             ExplodedNodeSet &Dst){
1706
1707  const Expr *Base = A->getBase()->IgnoreParens();
1708  const Expr *Idx  = A->getIdx()->IgnoreParens();
1709
1710
1711  ExplodedNodeSet checkerPreStmt;
1712  getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this);
1713
1714  StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx);
1715
1716  for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(),
1717                                 ei = checkerPreStmt.end(); it != ei; ++it) {
1718    const LocationContext *LCtx = (*it)->getLocationContext();
1719    ProgramStateRef state = (*it)->getState();
1720    SVal V = state->getLValue(A->getType(),
1721                              state->getSVal(Idx, LCtx),
1722                              state->getSVal(Base, LCtx));
1723    assert(A->isGLValue());
1724    Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0,
1725                      ProgramPoint::PostLValueKind);
1726  }
1727}
1728
1729/// VisitMemberExpr - Transfer function for member expressions.
1730void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
1731                                 ExplodedNodeSet &TopDst) {
1732
1733  StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx);
1734  ExplodedNodeSet Dst;
1735  ValueDecl *Member = M->getMemberDecl();
1736
1737  // Handle static member variables and enum constants accessed via
1738  // member syntax.
1739  if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) {
1740    Bldr.takeNodes(Pred);
1741    VisitCommonDeclRefExpr(M, Member, Pred, Dst);
1742    Bldr.addNodes(Dst);
1743    return;
1744  }
1745
1746  ProgramStateRef state = Pred->getState();
1747  const LocationContext *LCtx = Pred->getLocationContext();
1748  Expr *BaseExpr = M->getBase();
1749
1750  // Handle C++ method calls.
1751  if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) {
1752    if (MD->isInstance())
1753      state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1754
1755    SVal MDVal = svalBuilder.getFunctionPointer(MD);
1756    state = state->BindExpr(M, LCtx, MDVal);
1757
1758    Bldr.generateNode(M, Pred, state);
1759    return;
1760  }
1761
1762  // Handle regular struct fields / member variables.
1763  state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1764  SVal baseExprVal = state->getSVal(BaseExpr, LCtx);
1765
1766  FieldDecl *field = cast<FieldDecl>(Member);
1767  SVal L = state->getLValue(field, baseExprVal);
1768
1769  if (M->isGLValue() || M->getType()->isArrayType()) {
1770
1771    // We special case rvalue of array type because the analyzer cannot reason
1772    // about it, since we expect all regions to be wrapped in Locs. So we will
1773    // treat these as lvalues assuming that they will decay to pointers as soon
1774    // as they are used.
1775    if (!M->isGLValue()) {
1776      assert(M->getType()->isArrayType());
1777      const ImplicitCastExpr *PE =
1778        dyn_cast<ImplicitCastExpr>(Pred->getParentMap().getParent(M));
1779      if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
1780        assert(false &&
1781               "We assume that array is always wrapped in ArrayToPointerDecay");
1782        L = UnknownVal();
1783      }
1784    }
1785
1786    if (field->getType()->isReferenceType()) {
1787      if (const MemRegion *R = L.getAsRegion())
1788        L = state->getSVal(R);
1789      else
1790        L = UnknownVal();
1791    }
1792
1793    Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0,
1794                      ProgramPoint::PostLValueKind);
1795  } else {
1796    Bldr.takeNodes(Pred);
1797    evalLoad(Dst, M, M, Pred, state, L);
1798    Bldr.addNodes(Dst);
1799  }
1800}
1801
1802namespace {
1803class CollectReachableSymbolsCallback : public SymbolVisitor {
1804  InvalidatedSymbols Symbols;
1805public:
1806  CollectReachableSymbolsCallback(ProgramStateRef State) {}
1807  const InvalidatedSymbols &getSymbols() const { return Symbols; }
1808
1809  bool VisitSymbol(SymbolRef Sym) {
1810    Symbols.insert(Sym);
1811    return true;
1812  }
1813};
1814} // end anonymous namespace
1815
1816// A value escapes in three possible cases:
1817// (1) We are binding to something that is not a memory region.
1818// (2) We are binding to a MemrRegion that does not have stack storage.
1819// (3) We are binding to a MemRegion with stack storage that the store
1820//     does not understand.
1821ProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State,
1822                                                        SVal Loc, SVal Val) {
1823  // Are we storing to something that causes the value to "escape"?
1824  bool escapes = true;
1825
1826  // TODO: Move to StoreManager.
1827  if (Optional<loc::MemRegionVal> regionLoc = Loc.getAs<loc::MemRegionVal>()) {
1828    escapes = !regionLoc->getRegion()->hasStackStorage();
1829
1830    if (!escapes) {
1831      // To test (3), generate a new state with the binding added.  If it is
1832      // the same state, then it escapes (since the store cannot represent
1833      // the binding).
1834      // Do this only if we know that the store is not supposed to generate the
1835      // same state.
1836      SVal StoredVal = State->getSVal(regionLoc->getRegion());
1837      if (StoredVal != Val)
1838        escapes = (State == (State->bindLoc(*regionLoc, Val)));
1839    }
1840  }
1841
1842  // If our store can represent the binding and we aren't storing to something
1843  // that doesn't have local storage then just return and have the simulation
1844  // state continue as is.
1845  if (!escapes)
1846    return State;
1847
1848  // Otherwise, find all symbols referenced by 'val' that we are tracking
1849  // and stop tracking them.
1850  CollectReachableSymbolsCallback Scanner =
1851      State->scanReachableSymbols<CollectReachableSymbolsCallback>(Val);
1852  const InvalidatedSymbols &EscapedSymbols = Scanner.getSymbols();
1853  State = getCheckerManager().runCheckersForPointerEscape(State,
1854                                                          EscapedSymbols,
1855                                                          /*CallEvent*/ 0,
1856                                                          PSK_EscapeOnBind);
1857
1858  return State;
1859}
1860
1861ProgramStateRef
1862ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
1863    const InvalidatedSymbols *Invalidated,
1864    ArrayRef<const MemRegion *> ExplicitRegions,
1865    ArrayRef<const MemRegion *> Regions,
1866    const CallEvent *Call,
1867    bool IsConst) {
1868
1869  if (!Invalidated || Invalidated->empty())
1870    return State;
1871
1872  if (!Call)
1873    return getCheckerManager().runCheckersForPointerEscape(State,
1874                                                           *Invalidated,
1875                                                           0,
1876                                                           PSK_EscapeOther,
1877                                                           IsConst);
1878
1879  // Note: Due to current limitations of RegionStore, we only process the top
1880  // level const pointers correctly. The lower level const pointers are
1881  // currently treated as non-const.
1882  if (IsConst)
1883    return getCheckerManager().runCheckersForPointerEscape(State,
1884                                                        *Invalidated,
1885                                                        Call,
1886                                                        PSK_DirectEscapeOnCall,
1887                                                        true);
1888
1889  // If the symbols were invalidated by a call, we want to find out which ones
1890  // were invalidated directly due to being arguments to the call.
1891  InvalidatedSymbols SymbolsDirectlyInvalidated;
1892  for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
1893      E = ExplicitRegions.end(); I != E; ++I) {
1894    if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>())
1895      SymbolsDirectlyInvalidated.insert(R->getSymbol());
1896  }
1897
1898  InvalidatedSymbols SymbolsIndirectlyInvalidated;
1899  for (InvalidatedSymbols::const_iterator I=Invalidated->begin(),
1900      E = Invalidated->end(); I!=E; ++I) {
1901    SymbolRef sym = *I;
1902    if (SymbolsDirectlyInvalidated.count(sym))
1903      continue;
1904    SymbolsIndirectlyInvalidated.insert(sym);
1905  }
1906
1907  if (!SymbolsDirectlyInvalidated.empty())
1908    State = getCheckerManager().runCheckersForPointerEscape(State,
1909        SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall);
1910
1911  // Notify about the symbols that get indirectly invalidated by the call.
1912  if (!SymbolsIndirectlyInvalidated.empty())
1913    State = getCheckerManager().runCheckersForPointerEscape(State,
1914        SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall);
1915
1916  return State;
1917}
1918
1919/// evalBind - Handle the semantics of binding a value to a specific location.
1920///  This method is used by evalStore and (soon) VisitDeclStmt, and others.
1921void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
1922                          ExplodedNode *Pred,
1923                          SVal location, SVal Val,
1924                          bool atDeclInit, const ProgramPoint *PP) {
1925
1926  const LocationContext *LC = Pred->getLocationContext();
1927  PostStmt PS(StoreE, LC);
1928  if (!PP)
1929    PP = &PS;
1930
1931  // Do a previsit of the bind.
1932  ExplodedNodeSet CheckedSet;
1933  getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
1934                                         StoreE, *this, *PP);
1935
1936
1937  StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
1938
1939  // If the location is not a 'Loc', it will already be handled by
1940  // the checkers.  There is nothing left to do.
1941  if (!location.getAs<Loc>()) {
1942    const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/0, /*tag*/0);
1943    ProgramStateRef state = Pred->getState();
1944    state = processPointerEscapedOnBind(state, location, Val);
1945    Bldr.generateNode(L, state, Pred);
1946    return;
1947  }
1948
1949
1950  for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1951       I!=E; ++I) {
1952    ExplodedNode *PredI = *I;
1953    ProgramStateRef state = PredI->getState();
1954
1955    state = processPointerEscapedOnBind(state, location, Val);
1956
1957    // When binding the value, pass on the hint that this is a initialization.
1958    // For initializations, we do not need to inform clients of region
1959    // changes.
1960    state = state->bindLoc(location.castAs<Loc>(),
1961                           Val, /* notifyChanges = */ !atDeclInit);
1962
1963    const MemRegion *LocReg = 0;
1964    if (Optional<loc::MemRegionVal> LocRegVal =
1965            location.getAs<loc::MemRegionVal>()) {
1966      LocReg = LocRegVal->getRegion();
1967    }
1968
1969    const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0);
1970    Bldr.generateNode(L, state, PredI);
1971  }
1972}
1973
1974/// evalStore - Handle the semantics of a store via an assignment.
1975///  @param Dst The node set to store generated state nodes
1976///  @param AssignE The assignment expression if the store happens in an
1977///         assignment.
1978///  @param LocationE The location expression that is stored to.
1979///  @param state The current simulation state
1980///  @param location The location to store the value
1981///  @param Val The value to be stored
1982void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
1983                             const Expr *LocationE,
1984                             ExplodedNode *Pred,
1985                             ProgramStateRef state, SVal location, SVal Val,
1986                             const ProgramPointTag *tag) {
1987  // Proceed with the store.  We use AssignE as the anchor for the PostStore
1988  // ProgramPoint if it is non-NULL, and LocationE otherwise.
1989  const Expr *StoreE = AssignE ? AssignE : LocationE;
1990
1991  // Evaluate the location (checks for bad dereferences).
1992  ExplodedNodeSet Tmp;
1993  evalLocation(Tmp, AssignE, LocationE, Pred, state, location, tag, false);
1994
1995  if (Tmp.empty())
1996    return;
1997
1998  if (location.isUndef())
1999    return;
2000
2001  for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
2002    evalBind(Dst, StoreE, *NI, location, Val, false);
2003}
2004
2005void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
2006                          const Expr *NodeEx,
2007                          const Expr *BoundEx,
2008                          ExplodedNode *Pred,
2009                          ProgramStateRef state,
2010                          SVal location,
2011                          const ProgramPointTag *tag,
2012                          QualType LoadTy)
2013{
2014  assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
2015
2016  // Are we loading from a region?  This actually results in two loads; one
2017  // to fetch the address of the referenced value and one to fetch the
2018  // referenced value.
2019  if (const TypedValueRegion *TR =
2020        dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) {
2021
2022    QualType ValTy = TR->getValueType();
2023    if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
2024      static SimpleProgramPointTag
2025             loadReferenceTag("ExprEngine : Load Reference");
2026      ExplodedNodeSet Tmp;
2027      evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state,
2028                     location, &loadReferenceTag,
2029                     getContext().getPointerType(RT->getPointeeType()));
2030
2031      // Perform the load from the referenced value.
2032      for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
2033        state = (*I)->getState();
2034        location = state->getSVal(BoundEx, (*I)->getLocationContext());
2035        evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy);
2036      }
2037      return;
2038    }
2039  }
2040
2041  evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy);
2042}
2043
2044void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst,
2045                                const Expr *NodeEx,
2046                                const Expr *BoundEx,
2047                                ExplodedNode *Pred,
2048                                ProgramStateRef state,
2049                                SVal location,
2050                                const ProgramPointTag *tag,
2051                                QualType LoadTy) {
2052  assert(NodeEx);
2053  assert(BoundEx);
2054  // Evaluate the location (checks for bad dereferences).
2055  ExplodedNodeSet Tmp;
2056  evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true);
2057  if (Tmp.empty())
2058    return;
2059
2060  StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
2061  if (location.isUndef())
2062    return;
2063
2064  // Proceed with the load.
2065  for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
2066    state = (*NI)->getState();
2067    const LocationContext *LCtx = (*NI)->getLocationContext();
2068
2069    SVal V = UnknownVal();
2070    if (location.isValid()) {
2071      if (LoadTy.isNull())
2072        LoadTy = BoundEx->getType();
2073      V = state->getSVal(location.castAs<Loc>(), LoadTy);
2074    }
2075
2076    Bldr.generateNode(NodeEx, *NI, state->BindExpr(BoundEx, LCtx, V), tag,
2077                      ProgramPoint::PostLoadKind);
2078  }
2079}
2080
2081void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
2082                              const Stmt *NodeEx,
2083                              const Stmt *BoundEx,
2084                              ExplodedNode *Pred,
2085                              ProgramStateRef state,
2086                              SVal location,
2087                              const ProgramPointTag *tag,
2088                              bool isLoad) {
2089  StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
2090  // Early checks for performance reason.
2091  if (location.isUnknown()) {
2092    return;
2093  }
2094
2095  ExplodedNodeSet Src;
2096  BldrTop.takeNodes(Pred);
2097  StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
2098  if (Pred->getState() != state) {
2099    // Associate this new state with an ExplodedNode.
2100    // FIXME: If I pass null tag, the graph is incorrect, e.g for
2101    //   int *p;
2102    //   p = 0;
2103    //   *p = 0xDEADBEEF;
2104    // "p = 0" is not noted as "Null pointer value stored to 'p'" but
2105    // instead "int *p" is noted as
2106    // "Variable 'p' initialized to a null pointer value"
2107
2108    static SimpleProgramPointTag tag("ExprEngine: Location");
2109    Bldr.generateNode(NodeEx, Pred, state, &tag);
2110  }
2111  ExplodedNodeSet Tmp;
2112  getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
2113                                             NodeEx, BoundEx, *this);
2114  BldrTop.addNodes(Tmp);
2115}
2116
2117std::pair<const ProgramPointTag *, const ProgramPointTag*>
2118ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
2119  static SimpleProgramPointTag
2120         eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"),
2121         eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False");
2122  return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
2123                        &eagerlyAssumeBinOpBifurcationFalse);
2124}
2125
2126void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
2127                                                   ExplodedNodeSet &Src,
2128                                                   const Expr *Ex) {
2129  StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
2130
2131  for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
2132    ExplodedNode *Pred = *I;
2133    // Test if the previous node was as the same expression.  This can happen
2134    // when the expression fails to evaluate to anything meaningful and
2135    // (as an optimization) we don't generate a node.
2136    ProgramPoint P = Pred->getLocation();
2137    if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
2138      continue;
2139    }
2140
2141    ProgramStateRef state = Pred->getState();
2142    SVal V = state->getSVal(Ex, Pred->getLocationContext());
2143    Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
2144    if (SEV && SEV->isExpression()) {
2145      const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
2146        geteagerlyAssumeBinOpBifurcationTags();
2147
2148      ProgramStateRef StateTrue, StateFalse;
2149      tie(StateTrue, StateFalse) = state->assume(*SEV);
2150
2151      // First assume that the condition is true.
2152      if (StateTrue) {
2153        SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
2154        StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
2155        Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
2156      }
2157
2158      // Next, assume that the condition is false.
2159      if (StateFalse) {
2160        SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
2161        StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
2162        Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
2163      }
2164    }
2165  }
2166}
2167
2168void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
2169                                 ExplodedNodeSet &Dst) {
2170  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2171  // We have processed both the inputs and the outputs.  All of the outputs
2172  // should evaluate to Locs.  Nuke all of their values.
2173
2174  // FIXME: Some day in the future it would be nice to allow a "plug-in"
2175  // which interprets the inline asm and stores proper results in the
2176  // outputs.
2177
2178  ProgramStateRef state = Pred->getState();
2179
2180  for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(),
2181       OE = A->end_outputs(); OI != OE; ++OI) {
2182    SVal X = state->getSVal(*OI, Pred->getLocationContext());
2183    assert (!X.getAs<NonLoc>());  // Should be an Lval, or unknown, undef.
2184
2185    if (Optional<Loc> LV = X.getAs<Loc>())
2186      state = state->bindLoc(*LV, UnknownVal());
2187  }
2188
2189  Bldr.generateNode(A, Pred, state);
2190}
2191
2192void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
2193                                ExplodedNodeSet &Dst) {
2194  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2195  Bldr.generateNode(A, Pred, Pred->getState());
2196}
2197
2198//===----------------------------------------------------------------------===//
2199// Visualization.
2200//===----------------------------------------------------------------------===//
2201
2202#ifndef NDEBUG
2203static ExprEngine* GraphPrintCheckerState;
2204static SourceManager* GraphPrintSourceManager;
2205
2206namespace llvm {
2207template<>
2208struct DOTGraphTraits<ExplodedNode*> :
2209  public DefaultDOTGraphTraits {
2210
2211  DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
2212
2213  // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
2214  // work.
2215  static std::string getNodeAttributes(const ExplodedNode *N, void*) {
2216
2217#if 0
2218      // FIXME: Replace with a general scheme to tell if the node is
2219      // an error node.
2220    if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
2221        GraphPrintCheckerState->isExplicitNullDeref(N) ||
2222        GraphPrintCheckerState->isUndefDeref(N) ||
2223        GraphPrintCheckerState->isUndefStore(N) ||
2224        GraphPrintCheckerState->isUndefControlFlow(N) ||
2225        GraphPrintCheckerState->isUndefResult(N) ||
2226        GraphPrintCheckerState->isBadCall(N) ||
2227        GraphPrintCheckerState->isUndefArg(N))
2228      return "color=\"red\",style=\"filled\"";
2229
2230    if (GraphPrintCheckerState->isNoReturnCall(N))
2231      return "color=\"blue\",style=\"filled\"";
2232#endif
2233    return "";
2234  }
2235
2236  static void printLocation(raw_ostream &Out, SourceLocation SLoc) {
2237    if (SLoc.isFileID()) {
2238      Out << "\\lline="
2239        << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2240        << " col="
2241        << GraphPrintSourceManager->getExpansionColumnNumber(SLoc)
2242        << "\\l";
2243    }
2244  }
2245
2246  static std::string getNodeLabel(const ExplodedNode *N, void*){
2247
2248    std::string sbuf;
2249    llvm::raw_string_ostream Out(sbuf);
2250
2251    // Program Location.
2252    ProgramPoint Loc = N->getLocation();
2253
2254    switch (Loc.getKind()) {
2255      case ProgramPoint::BlockEntranceKind: {
2256        Out << "Block Entrance: B"
2257            << Loc.castAs<BlockEntrance>().getBlock()->getBlockID();
2258        if (const NamedDecl *ND =
2259                    dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) {
2260          Out << " (";
2261          ND->printName(Out);
2262          Out << ")";
2263        }
2264        break;
2265      }
2266
2267      case ProgramPoint::BlockExitKind:
2268        assert (false);
2269        break;
2270
2271      case ProgramPoint::CallEnterKind:
2272        Out << "CallEnter";
2273        break;
2274
2275      case ProgramPoint::CallExitBeginKind:
2276        Out << "CallExitBegin";
2277        break;
2278
2279      case ProgramPoint::CallExitEndKind:
2280        Out << "CallExitEnd";
2281        break;
2282
2283      case ProgramPoint::PostStmtPurgeDeadSymbolsKind:
2284        Out << "PostStmtPurgeDeadSymbols";
2285        break;
2286
2287      case ProgramPoint::PreStmtPurgeDeadSymbolsKind:
2288        Out << "PreStmtPurgeDeadSymbols";
2289        break;
2290
2291      case ProgramPoint::EpsilonKind:
2292        Out << "Epsilon Point";
2293        break;
2294
2295      case ProgramPoint::PreImplicitCallKind: {
2296        ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
2297        Out << "PreCall: ";
2298
2299        // FIXME: Get proper printing options.
2300        PC.getDecl()->print(Out, LangOptions());
2301        printLocation(Out, PC.getLocation());
2302        break;
2303      }
2304
2305      case ProgramPoint::PostImplicitCallKind: {
2306        ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
2307        Out << "PostCall: ";
2308
2309        // FIXME: Get proper printing options.
2310        PC.getDecl()->print(Out, LangOptions());
2311        printLocation(Out, PC.getLocation());
2312        break;
2313      }
2314
2315      case ProgramPoint::PostInitializerKind: {
2316        Out << "PostInitializer: ";
2317        const CXXCtorInitializer *Init =
2318          Loc.castAs<PostInitializer>().getInitializer();
2319        if (const FieldDecl *FD = Init->getAnyMember())
2320          Out << *FD;
2321        else {
2322          QualType Ty = Init->getTypeSourceInfo()->getType();
2323          Ty = Ty.getLocalUnqualifiedType();
2324          LangOptions LO; // FIXME.
2325          Ty.print(Out, LO);
2326        }
2327        break;
2328      }
2329
2330      case ProgramPoint::BlockEdgeKind: {
2331        const BlockEdge &E = Loc.castAs<BlockEdge>();
2332        Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
2333            << E.getDst()->getBlockID()  << ')';
2334
2335        if (const Stmt *T = E.getSrc()->getTerminator()) {
2336          SourceLocation SLoc = T->getLocStart();
2337
2338          Out << "\\|Terminator: ";
2339          LangOptions LO; // FIXME.
2340          E.getSrc()->printTerminator(Out, LO);
2341
2342          if (SLoc.isFileID()) {
2343            Out << "\\lline="
2344              << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2345              << " col="
2346              << GraphPrintSourceManager->getExpansionColumnNumber(SLoc);
2347          }
2348
2349          if (isa<SwitchStmt>(T)) {
2350            const Stmt *Label = E.getDst()->getLabel();
2351
2352            if (Label) {
2353              if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
2354                Out << "\\lcase ";
2355                LangOptions LO; // FIXME.
2356                C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
2357
2358                if (const Stmt *RHS = C->getRHS()) {
2359                  Out << " .. ";
2360                  RHS->printPretty(Out, 0, PrintingPolicy(LO));
2361                }
2362
2363                Out << ":";
2364              }
2365              else {
2366                assert (isa<DefaultStmt>(Label));
2367                Out << "\\ldefault:";
2368              }
2369            }
2370            else
2371              Out << "\\l(implicit) default:";
2372          }
2373          else if (isa<IndirectGotoStmt>(T)) {
2374            // FIXME
2375          }
2376          else {
2377            Out << "\\lCondition: ";
2378            if (*E.getSrc()->succ_begin() == E.getDst())
2379              Out << "true";
2380            else
2381              Out << "false";
2382          }
2383
2384          Out << "\\l";
2385        }
2386
2387#if 0
2388          // FIXME: Replace with a general scheme to determine
2389          // the name of the check.
2390        if (GraphPrintCheckerState->isUndefControlFlow(N)) {
2391          Out << "\\|Control-flow based on\\lUndefined value.\\l";
2392        }
2393#endif
2394        break;
2395      }
2396
2397      default: {
2398        const Stmt *S = Loc.castAs<StmtPoint>().getStmt();
2399
2400        Out << S->getStmtClassName() << ' ' << (const void*) S << ' ';
2401        LangOptions LO; // FIXME.
2402        S->printPretty(Out, 0, PrintingPolicy(LO));
2403        printLocation(Out, S->getLocStart());
2404
2405        if (Loc.getAs<PreStmt>())
2406          Out << "\\lPreStmt\\l;";
2407        else if (Loc.getAs<PostLoad>())
2408          Out << "\\lPostLoad\\l;";
2409        else if (Loc.getAs<PostStore>())
2410          Out << "\\lPostStore\\l";
2411        else if (Loc.getAs<PostLValue>())
2412          Out << "\\lPostLValue\\l";
2413
2414#if 0
2415          // FIXME: Replace with a general scheme to determine
2416          // the name of the check.
2417        if (GraphPrintCheckerState->isImplicitNullDeref(N))
2418          Out << "\\|Implicit-Null Dereference.\\l";
2419        else if (GraphPrintCheckerState->isExplicitNullDeref(N))
2420          Out << "\\|Explicit-Null Dereference.\\l";
2421        else if (GraphPrintCheckerState->isUndefDeref(N))
2422          Out << "\\|Dereference of undefialied value.\\l";
2423        else if (GraphPrintCheckerState->isUndefStore(N))
2424          Out << "\\|Store to Undefined Loc.";
2425        else if (GraphPrintCheckerState->isUndefResult(N))
2426          Out << "\\|Result of operation is undefined.";
2427        else if (GraphPrintCheckerState->isNoReturnCall(N))
2428          Out << "\\|Call to function marked \"noreturn\".";
2429        else if (GraphPrintCheckerState->isBadCall(N))
2430          Out << "\\|Call to NULL/Undefined.";
2431        else if (GraphPrintCheckerState->isUndefArg(N))
2432          Out << "\\|Argument in call is undefined";
2433#endif
2434
2435        break;
2436      }
2437    }
2438
2439    ProgramStateRef state = N->getState();
2440    Out << "\\|StateID: " << (const void*) state.getPtr()
2441        << " NodeID: " << (const void*) N << "\\|";
2442    state->printDOT(Out);
2443
2444    Out << "\\l";
2445
2446    if (const ProgramPointTag *tag = Loc.getTag()) {
2447      Out << "\\|Tag: " << tag->getTagDescription();
2448      Out << "\\l";
2449    }
2450    return Out.str();
2451  }
2452};
2453} // end llvm namespace
2454#endif
2455
2456#ifndef NDEBUG
2457template <typename ITERATOR>
2458ExplodedNode *GetGraphNode(ITERATOR I) { return *I; }
2459
2460template <> ExplodedNode*
2461GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
2462  (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
2463  return I->first;
2464}
2465#endif
2466
2467void ExprEngine::ViewGraph(bool trim) {
2468#ifndef NDEBUG
2469  if (trim) {
2470    std::vector<const ExplodedNode*> Src;
2471
2472    // Flush any outstanding reports to make sure we cover all the nodes.
2473    // This does not cause them to get displayed.
2474    for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
2475      const_cast<BugType*>(*I)->FlushReports(BR);
2476
2477    // Iterate through the reports and get their nodes.
2478    for (BugReporter::EQClasses_iterator
2479           EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
2480      ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode());
2481      if (N) Src.push_back(N);
2482    }
2483
2484    ViewGraph(Src);
2485  }
2486  else {
2487    GraphPrintCheckerState = this;
2488    GraphPrintSourceManager = &getContext().getSourceManager();
2489
2490    llvm::ViewGraph(*G.roots_begin(), "ExprEngine");
2491
2492    GraphPrintCheckerState = NULL;
2493    GraphPrintSourceManager = NULL;
2494  }
2495#endif
2496}
2497
2498void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) {
2499#ifndef NDEBUG
2500  GraphPrintCheckerState = this;
2501  GraphPrintSourceManager = &getContext().getSourceManager();
2502
2503  OwningPtr<ExplodedGraph> TrimmedG(G.trim(Nodes));
2504
2505  if (!TrimmedG.get())
2506    llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
2507  else
2508    llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine");
2509
2510  GraphPrintCheckerState = NULL;
2511  GraphPrintSourceManager = NULL;
2512#endif
2513}
2514