• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
39 using namespace clang;
40 using namespace ento;
41 using llvm::APSInt;
42 
43 STATISTIC(NumRemoveDeadBindings,
44             "The # of times RemoveDeadBindings is called");
45 STATISTIC(NumMaxBlockCountReached,
46             "The # of aborted paths due to reaching the maximum block count in "
47             "a top level function");
48 STATISTIC(NumMaxBlockCountReachedInInlined,
49             "The # of aborted paths due to reaching the maximum block count in "
50             "an inlined function");
51 STATISTIC(NumTimesRetriedWithoutInlining,
52             "The # of times we re-evaluated a call without inlining");
53 
54 //===----------------------------------------------------------------------===//
55 // Engine construction and deletion.
56 //===----------------------------------------------------------------------===//
57 
ExprEngine(AnalysisManager & mgr,bool gcEnabled,SetOfConstDecls * VisitedCalleesIn,FunctionSummariesTy * FS,InliningModes HowToInlineIn)58 ExprEngine::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 
~ExprEngine()84 ExprEngine::~ExprEngine() {
85   BR.FlushReports();
86 }
87 
88 //===----------------------------------------------------------------------===//
89 // Utility methods.
90 //===----------------------------------------------------------------------===//
91 
getInitialState(const LocationContext * InitLoc)92 ProgramStateRef 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 
170 ProgramStateRef
createTemporaryRegionIfNeeded(ProgramStateRef State,const LocationContext * LC,const Expr * Ex,const Expr * Result)171 ExprEngine::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.
processAssume(ProgramStateRef state,SVal cond,bool assumption)248 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
249                                               SVal cond, bool assumption) {
250   return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
251 }
252 
wantsRegionChangeUpdate(ProgramStateRef state)253 bool ExprEngine::wantsRegionChangeUpdate(ProgramStateRef state) {
254   return getCheckerManager().wantsRegionChangeUpdate(state);
255 }
256 
257 ProgramStateRef
processRegionChanges(ProgramStateRef state,const InvalidatedSymbols * invalidated,ArrayRef<const MemRegion * > Explicits,ArrayRef<const MemRegion * > Regions,const CallEvent * Call)258 ExprEngine::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 
printState(raw_ostream & Out,ProgramStateRef State,const char * NL,const char * Sep)267 void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State,
268                             const char *NL, const char *Sep) {
269   getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep);
270 }
271 
processEndWorklist(bool hasWorkRemaining)272 void ExprEngine::processEndWorklist(bool hasWorkRemaining) {
273   getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
274 }
275 
processCFGElement(const CFGElement E,ExplodedNode * Pred,unsigned StmtIdx,NodeBuilderContext * Ctx)276 void 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 
shouldRemoveDeadBindings(AnalysisManager & AMgr,const CFGStmt S,const ExplodedNode * Pred,const LocationContext * LC)298 static 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 
removeDead(ExplodedNode * Pred,ExplodedNodeSet & Out,const Stmt * ReferenceStmt,const LocationContext * LC,const Stmt * DiagnosticStmt,ProgramPoint::Kind K)325 void 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 
ProcessStmt(const CFGStmt S,ExplodedNode * Pred)407 void 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 
ProcessInitializer(const CFGInitializer Init,ExplodedNode * Pred)438 void 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 
ProcessImplicitDtor(const CFGImplicitDtor D,ExplodedNode * Pred)522 void 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 
ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,ExplodedNode * Pred,ExplodedNodeSet & Dst)546 void 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 
ProcessBaseDtor(const CFGBaseDtor D,ExplodedNode * Pred,ExplodedNodeSet & Dst)565 void 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 
ProcessMemberDtor(const CFGMemberDtor D,ExplodedNode * Pred,ExplodedNodeSet & Dst)585 void 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 
ProcessTemporaryDtor(const CFGTemporaryDtor D,ExplodedNode * Pred,ExplodedNodeSet & Dst)602 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
603                                       ExplodedNode *Pred,
604                                       ExplodedNodeSet &Dst) {}
605 
Visit(const Stmt * S,ExplodedNode * Pred,ExplodedNodeSet & DstTop)606 void 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 
replayWithoutInlining(ExplodedNode * N,const LocationContext * CalleeLC)1143 bool 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).
processCFGBlockEntrance(const BlockEdge & L,NodeBuilderWithSinks & nodeBuilder,ExplodedNode * Pred)1207 void 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.
RecoverCastedSymbol(ProgramStateManager & StateMgr,ProgramStateRef state,const Stmt * Condition,const LocationContext * LCtx,ASTContext & Ctx)1252 static 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 
ResolveCondition(const Stmt * Condition,const CFGBlock * B)1290 static 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 
processBranch(const Stmt * Condition,const Stmt * Term,NodeBuilderContext & BldCtx,ExplodedNode * Pred,ExplodedNodeSet & Dst,const CFGBlock * DstT,const CFGBlock * DstF)1329 void 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 
1347   // Resolve the condition in the precense of nested '||' and '&&'.
1348   if (const Expr *Ex = dyn_cast<Expr>(Condition))
1349     Condition = Ex->IgnoreParens();
1350 
1351   Condition = ResolveCondition(Condition, BldCtx.getBlock());
1352   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1353                                 Condition->getLocStart(),
1354                                 "Error evaluating branch");
1355 
1356   ExplodedNodeSet CheckersOutSet;
1357   getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
1358                                                     Pred, *this);
1359   // We generated only sinks.
1360   if (CheckersOutSet.empty())
1361     return;
1362 
1363   BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
1364   for (NodeBuilder::iterator I = CheckersOutSet.begin(),
1365                              E = CheckersOutSet.end(); E != I; ++I) {
1366     ExplodedNode *PredI = *I;
1367 
1368     if (PredI->isSink())
1369       continue;
1370 
1371     ProgramStateRef PrevState = PredI->getState();
1372     SVal X = PrevState->getSVal(Condition, PredI->getLocationContext());
1373 
1374     if (X.isUnknownOrUndef()) {
1375       // Give it a chance to recover from unknown.
1376       if (const Expr *Ex = dyn_cast<Expr>(Condition)) {
1377         if (Ex->getType()->isIntegralOrEnumerationType()) {
1378           // Try to recover some path-sensitivity.  Right now casts of symbolic
1379           // integers that promote their values are currently not tracked well.
1380           // If 'Condition' is such an expression, try and recover the
1381           // underlying value and use that instead.
1382           SVal recovered = RecoverCastedSymbol(getStateManager(),
1383                                                PrevState, Condition,
1384                                                PredI->getLocationContext(),
1385                                                getContext());
1386 
1387           if (!recovered.isUnknown()) {
1388             X = recovered;
1389           }
1390         }
1391       }
1392     }
1393 
1394     // If the condition is still unknown, give up.
1395     if (X.isUnknownOrUndef()) {
1396       builder.generateNode(PrevState, true, PredI);
1397       builder.generateNode(PrevState, false, PredI);
1398       continue;
1399     }
1400 
1401     DefinedSVal V = X.castAs<DefinedSVal>();
1402 
1403     ProgramStateRef StTrue, StFalse;
1404     tie(StTrue, StFalse) = PrevState->assume(V);
1405 
1406     // Process the true branch.
1407     if (builder.isFeasible(true)) {
1408       if (StTrue)
1409         builder.generateNode(StTrue, true, PredI);
1410       else
1411         builder.markInfeasible(true);
1412     }
1413 
1414     // Process the false branch.
1415     if (builder.isFeasible(false)) {
1416       if (StFalse)
1417         builder.generateNode(StFalse, false, PredI);
1418       else
1419         builder.markInfeasible(false);
1420     }
1421   }
1422   currBldrCtx = 0;
1423 }
1424 
1425 /// The GDM component containing the set of global variables which have been
1426 /// previously initialized with explicit initializers.
REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,llvm::ImmutableSet<const VarDecl * >)1427 REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
1428                                  llvm::ImmutableSet<const VarDecl *>)
1429 
1430 void ExprEngine::processStaticInitializer(const DeclStmt *DS,
1431                                           NodeBuilderContext &BuilderCtx,
1432                                           ExplodedNode *Pred,
1433                                           clang::ento::ExplodedNodeSet &Dst,
1434                                           const CFGBlock *DstT,
1435                                           const CFGBlock *DstF) {
1436   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
1437   currBldrCtx = &BuilderCtx;
1438 
1439   const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
1440   ProgramStateRef state = Pred->getState();
1441   bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
1442   BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
1443 
1444   if (!initHasRun) {
1445     state = state->add<InitializedGlobalsSet>(VD);
1446   }
1447 
1448   builder.generateNode(state, initHasRun, Pred);
1449   builder.markInfeasible(!initHasRun);
1450 
1451   currBldrCtx = 0;
1452 }
1453 
1454 /// processIndirectGoto - Called by CoreEngine.  Used to generate successor
1455 ///  nodes by processing the 'effects' of a computed goto jump.
processIndirectGoto(IndirectGotoNodeBuilder & builder)1456 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
1457 
1458   ProgramStateRef state = builder.getState();
1459   SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
1460 
1461   // Three possibilities:
1462   //
1463   //   (1) We know the computed label.
1464   //   (2) The label is NULL (or some other constant), or Undefined.
1465   //   (3) We have no clue about the label.  Dispatch to all targets.
1466   //
1467 
1468   typedef IndirectGotoNodeBuilder::iterator iterator;
1469 
1470   if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
1471     const LabelDecl *L = LV->getLabel();
1472 
1473     for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
1474       if (I.getLabel() == L) {
1475         builder.generateNode(I, state);
1476         return;
1477       }
1478     }
1479 
1480     llvm_unreachable("No block with label.");
1481   }
1482 
1483   if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) {
1484     // Dispatch to the first target and mark it as a sink.
1485     //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
1486     // FIXME: add checker visit.
1487     //    UndefBranches.insert(N);
1488     return;
1489   }
1490 
1491   // This is really a catch-all.  We don't support symbolics yet.
1492   // FIXME: Implement dispatch for symbolic pointers.
1493 
1494   for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
1495     builder.generateNode(I, state);
1496 }
1497 
1498 /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
1499 ///  nodes when the control reaches the end of a function.
processEndOfFunction(NodeBuilderContext & BC,ExplodedNode * Pred)1500 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
1501                                       ExplodedNode *Pred) {
1502   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
1503   StateMgr.EndPath(Pred->getState());
1504 
1505   ExplodedNodeSet Dst;
1506   if (Pred->getLocationContext()->inTopFrame()) {
1507     // Remove dead symbols.
1508     ExplodedNodeSet AfterRemovedDead;
1509     removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
1510 
1511     // Notify checkers.
1512     for (ExplodedNodeSet::iterator I = AfterRemovedDead.begin(),
1513         E = AfterRemovedDead.end(); I != E; ++I) {
1514       getCheckerManager().runCheckersForEndFunction(BC, Dst, *I, *this);
1515     }
1516   } else {
1517     getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this);
1518   }
1519 
1520   Engine.enqueueEndOfFunction(Dst);
1521 }
1522 
1523 /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
1524 ///  nodes by processing the 'effects' of a switch statement.
processSwitch(SwitchNodeBuilder & builder)1525 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
1526   typedef SwitchNodeBuilder::iterator iterator;
1527   ProgramStateRef state = builder.getState();
1528   const Expr *CondE = builder.getCondition();
1529   SVal  CondV_untested = state->getSVal(CondE, builder.getLocationContext());
1530 
1531   if (CondV_untested.isUndef()) {
1532     //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
1533     // FIXME: add checker
1534     //UndefBranches.insert(N);
1535 
1536     return;
1537   }
1538   DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
1539 
1540   ProgramStateRef DefaultSt = state;
1541 
1542   iterator I = builder.begin(), EI = builder.end();
1543   bool defaultIsFeasible = I == EI;
1544 
1545   for ( ; I != EI; ++I) {
1546     // Successor may be pruned out during CFG construction.
1547     if (!I.getBlock())
1548       continue;
1549 
1550     const CaseStmt *Case = I.getCase();
1551 
1552     // Evaluate the LHS of the case value.
1553     llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
1554     assert(V1.getBitWidth() == getContext().getTypeSize(CondE->getType()));
1555 
1556     // Get the RHS of the case, if it exists.
1557     llvm::APSInt V2;
1558     if (const Expr *E = Case->getRHS())
1559       V2 = E->EvaluateKnownConstInt(getContext());
1560     else
1561       V2 = V1;
1562 
1563     // FIXME: Eventually we should replace the logic below with a range
1564     //  comparison, rather than concretize the values within the range.
1565     //  This should be easy once we have "ranges" for NonLVals.
1566 
1567     do {
1568       nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1));
1569       DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
1570                                                CondV, CaseVal);
1571 
1572       // Now "assume" that the case matches.
1573       if (ProgramStateRef stateNew = state->assume(Res, true)) {
1574         builder.generateCaseStmtNode(I, stateNew);
1575 
1576         // If CondV evaluates to a constant, then we know that this
1577         // is the *only* case that we can take, so stop evaluating the
1578         // others.
1579         if (CondV.getAs<nonloc::ConcreteInt>())
1580           return;
1581       }
1582 
1583       // Now "assume" that the case doesn't match.  Add this state
1584       // to the default state (if it is feasible).
1585       if (DefaultSt) {
1586         if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) {
1587           defaultIsFeasible = true;
1588           DefaultSt = stateNew;
1589         }
1590         else {
1591           defaultIsFeasible = false;
1592           DefaultSt = NULL;
1593         }
1594       }
1595 
1596       // Concretize the next value in the range.
1597       if (V1 == V2)
1598         break;
1599 
1600       ++V1;
1601       assert (V1 <= V2);
1602 
1603     } while (true);
1604   }
1605 
1606   if (!defaultIsFeasible)
1607     return;
1608 
1609   // If we have switch(enum value), the default branch is not
1610   // feasible if all of the enum constants not covered by 'case:' statements
1611   // are not feasible values for the switch condition.
1612   //
1613   // Note that this isn't as accurate as it could be.  Even if there isn't
1614   // a case for a particular enum value as long as that enum value isn't
1615   // feasible then it shouldn't be considered for making 'default:' reachable.
1616   const SwitchStmt *SS = builder.getSwitch();
1617   const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
1618   if (CondExpr->getType()->getAs<EnumType>()) {
1619     if (SS->isAllEnumCasesCovered())
1620       return;
1621   }
1622 
1623   builder.generateDefaultCaseNode(DefaultSt);
1624 }
1625 
1626 //===----------------------------------------------------------------------===//
1627 // Transfer functions: Loads and stores.
1628 //===----------------------------------------------------------------------===//
1629 
VisitCommonDeclRefExpr(const Expr * Ex,const NamedDecl * D,ExplodedNode * Pred,ExplodedNodeSet & Dst)1630 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
1631                                         ExplodedNode *Pred,
1632                                         ExplodedNodeSet &Dst) {
1633   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1634 
1635   ProgramStateRef state = Pred->getState();
1636   const LocationContext *LCtx = Pred->getLocationContext();
1637 
1638   if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
1639     // C permits "extern void v", and if you cast the address to a valid type,
1640     // you can even do things with it. We simply pretend
1641     assert(Ex->isGLValue() || VD->getType()->isVoidType());
1642     SVal V = state->getLValue(VD, Pred->getLocationContext());
1643 
1644     // For references, the 'lvalue' is the pointer address stored in the
1645     // reference region.
1646     if (VD->getType()->isReferenceType()) {
1647       if (const MemRegion *R = V.getAsRegion())
1648         V = state->getSVal(R);
1649       else
1650         V = UnknownVal();
1651     }
1652 
1653     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1654                       ProgramPoint::PostLValueKind);
1655     return;
1656   }
1657   if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) {
1658     assert(!Ex->isGLValue());
1659     SVal V = svalBuilder.makeIntVal(ED->getInitVal());
1660     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
1661     return;
1662   }
1663   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
1664     SVal V = svalBuilder.getFunctionPointer(FD);
1665     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1666                       ProgramPoint::PostLValueKind);
1667     return;
1668   }
1669   if (isa<FieldDecl>(D)) {
1670     // FIXME: Compute lvalue of field pointers-to-member.
1671     // Right now we just use a non-null void pointer, so that it gives proper
1672     // results in boolean contexts.
1673     SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy,
1674                                           currBldrCtx->blockCount());
1675     state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true);
1676     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), 0,
1677 		      ProgramPoint::PostLValueKind);
1678     return;
1679   }
1680 
1681   llvm_unreachable("Support for this Decl not implemented.");
1682 }
1683 
1684 /// VisitArraySubscriptExpr - Transfer function for array accesses
VisitLvalArraySubscriptExpr(const ArraySubscriptExpr * A,ExplodedNode * Pred,ExplodedNodeSet & Dst)1685 void ExprEngine::VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *A,
1686                                              ExplodedNode *Pred,
1687                                              ExplodedNodeSet &Dst){
1688 
1689   const Expr *Base = A->getBase()->IgnoreParens();
1690   const Expr *Idx  = A->getIdx()->IgnoreParens();
1691 
1692 
1693   ExplodedNodeSet checkerPreStmt;
1694   getCheckerManager().runCheckersForPreStmt(checkerPreStmt, Pred, A, *this);
1695 
1696   StmtNodeBuilder Bldr(checkerPreStmt, Dst, *currBldrCtx);
1697 
1698   for (ExplodedNodeSet::iterator it = checkerPreStmt.begin(),
1699                                  ei = checkerPreStmt.end(); it != ei; ++it) {
1700     const LocationContext *LCtx = (*it)->getLocationContext();
1701     ProgramStateRef state = (*it)->getState();
1702     SVal V = state->getLValue(A->getType(),
1703                               state->getSVal(Idx, LCtx),
1704                               state->getSVal(Base, LCtx));
1705     assert(A->isGLValue());
1706     Bldr.generateNode(A, *it, state->BindExpr(A, LCtx, V), 0,
1707                       ProgramPoint::PostLValueKind);
1708   }
1709 }
1710 
1711 /// VisitMemberExpr - Transfer function for member expressions.
VisitMemberExpr(const MemberExpr * M,ExplodedNode * Pred,ExplodedNodeSet & TopDst)1712 void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
1713                                  ExplodedNodeSet &TopDst) {
1714 
1715   StmtNodeBuilder Bldr(Pred, TopDst, *currBldrCtx);
1716   ExplodedNodeSet Dst;
1717   ValueDecl *Member = M->getMemberDecl();
1718 
1719   // Handle static member variables and enum constants accessed via
1720   // member syntax.
1721   if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) {
1722     Bldr.takeNodes(Pred);
1723     VisitCommonDeclRefExpr(M, Member, Pred, Dst);
1724     Bldr.addNodes(Dst);
1725     return;
1726   }
1727 
1728   ProgramStateRef state = Pred->getState();
1729   const LocationContext *LCtx = Pred->getLocationContext();
1730   Expr *BaseExpr = M->getBase();
1731 
1732   // Handle C++ method calls.
1733   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(Member)) {
1734     if (MD->isInstance())
1735       state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1736 
1737     SVal MDVal = svalBuilder.getFunctionPointer(MD);
1738     state = state->BindExpr(M, LCtx, MDVal);
1739 
1740     Bldr.generateNode(M, Pred, state);
1741     return;
1742   }
1743 
1744   // Handle regular struct fields / member variables.
1745   state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
1746   SVal baseExprVal = state->getSVal(BaseExpr, LCtx);
1747 
1748   FieldDecl *field = cast<FieldDecl>(Member);
1749   SVal L = state->getLValue(field, baseExprVal);
1750 
1751   if (M->isGLValue() || M->getType()->isArrayType()) {
1752 
1753     // We special case rvalue of array type because the analyzer cannot reason
1754     // about it, since we expect all regions to be wrapped in Locs. So we will
1755     // treat these as lvalues assuming that they will decay to pointers as soon
1756     // as they are used.
1757     if (!M->isGLValue()) {
1758       assert(M->getType()->isArrayType());
1759       const ImplicitCastExpr *PE =
1760         dyn_cast<ImplicitCastExpr>(Pred->getParentMap().getParent(M));
1761       if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
1762         assert(false &&
1763                "We assume that array is always wrapped in ArrayToPointerDecay");
1764         L = UnknownVal();
1765       }
1766     }
1767 
1768     if (field->getType()->isReferenceType()) {
1769       if (const MemRegion *R = L.getAsRegion())
1770         L = state->getSVal(R);
1771       else
1772         L = UnknownVal();
1773     }
1774 
1775     Bldr.generateNode(M, Pred, state->BindExpr(M, LCtx, L), 0,
1776                       ProgramPoint::PostLValueKind);
1777   } else {
1778     Bldr.takeNodes(Pred);
1779     evalLoad(Dst, M, M, Pred, state, L);
1780     Bldr.addNodes(Dst);
1781   }
1782 }
1783 
1784 namespace {
1785 class CollectReachableSymbolsCallback : public SymbolVisitor {
1786   InvalidatedSymbols Symbols;
1787 public:
CollectReachableSymbolsCallback(ProgramStateRef State)1788   CollectReachableSymbolsCallback(ProgramStateRef State) {}
getSymbols() const1789   const InvalidatedSymbols &getSymbols() const { return Symbols; }
1790 
VisitSymbol(SymbolRef Sym)1791   bool VisitSymbol(SymbolRef Sym) {
1792     Symbols.insert(Sym);
1793     return true;
1794   }
1795 };
1796 } // end anonymous namespace
1797 
1798 // A value escapes in three possible cases:
1799 // (1) We are binding to something that is not a memory region.
1800 // (2) We are binding to a MemrRegion that does not have stack storage.
1801 // (3) We are binding to a MemRegion with stack storage that the store
1802 //     does not understand.
processPointerEscapedOnBind(ProgramStateRef State,SVal Loc,SVal Val)1803 ProgramStateRef ExprEngine::processPointerEscapedOnBind(ProgramStateRef State,
1804                                                         SVal Loc, SVal Val) {
1805   // Are we storing to something that causes the value to "escape"?
1806   bool escapes = true;
1807 
1808   // TODO: Move to StoreManager.
1809   if (Optional<loc::MemRegionVal> regionLoc = Loc.getAs<loc::MemRegionVal>()) {
1810     escapes = !regionLoc->getRegion()->hasStackStorage();
1811 
1812     if (!escapes) {
1813       // To test (3), generate a new state with the binding added.  If it is
1814       // the same state, then it escapes (since the store cannot represent
1815       // the binding).
1816       // Do this only if we know that the store is not supposed to generate the
1817       // same state.
1818       SVal StoredVal = State->getSVal(regionLoc->getRegion());
1819       if (StoredVal != Val)
1820         escapes = (State == (State->bindLoc(*regionLoc, Val)));
1821     }
1822   }
1823 
1824   // If our store can represent the binding and we aren't storing to something
1825   // that doesn't have local storage then just return and have the simulation
1826   // state continue as is.
1827   if (!escapes)
1828     return State;
1829 
1830   // Otherwise, find all symbols referenced by 'val' that we are tracking
1831   // and stop tracking them.
1832   CollectReachableSymbolsCallback Scanner =
1833       State->scanReachableSymbols<CollectReachableSymbolsCallback>(Val);
1834   const InvalidatedSymbols &EscapedSymbols = Scanner.getSymbols();
1835   State = getCheckerManager().runCheckersForPointerEscape(State,
1836                                                           EscapedSymbols,
1837                                                           /*CallEvent*/ 0,
1838                                                           PSK_EscapeOnBind);
1839 
1840   return State;
1841 }
1842 
1843 ProgramStateRef
notifyCheckersOfPointerEscape(ProgramStateRef State,const InvalidatedSymbols * Invalidated,ArrayRef<const MemRegion * > ExplicitRegions,ArrayRef<const MemRegion * > Regions,const CallEvent * Call,bool IsConst)1844 ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
1845     const InvalidatedSymbols *Invalidated,
1846     ArrayRef<const MemRegion *> ExplicitRegions,
1847     ArrayRef<const MemRegion *> Regions,
1848     const CallEvent *Call,
1849     bool IsConst) {
1850 
1851   if (!Invalidated || Invalidated->empty())
1852     return State;
1853 
1854   if (!Call)
1855     return getCheckerManager().runCheckersForPointerEscape(State,
1856                                                            *Invalidated,
1857                                                            0,
1858                                                            PSK_EscapeOther,
1859                                                            IsConst);
1860 
1861   // Note: Due to current limitations of RegionStore, we only process the top
1862   // level const pointers correctly. The lower level const pointers are
1863   // currently treated as non-const.
1864   if (IsConst)
1865     return getCheckerManager().runCheckersForPointerEscape(State,
1866                                                         *Invalidated,
1867                                                         Call,
1868                                                         PSK_DirectEscapeOnCall,
1869                                                         true);
1870 
1871   // If the symbols were invalidated by a call, we want to find out which ones
1872   // were invalidated directly due to being arguments to the call.
1873   InvalidatedSymbols SymbolsDirectlyInvalidated;
1874   for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(),
1875       E = ExplicitRegions.end(); I != E; ++I) {
1876     if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>())
1877       SymbolsDirectlyInvalidated.insert(R->getSymbol());
1878   }
1879 
1880   InvalidatedSymbols SymbolsIndirectlyInvalidated;
1881   for (InvalidatedSymbols::const_iterator I=Invalidated->begin(),
1882       E = Invalidated->end(); I!=E; ++I) {
1883     SymbolRef sym = *I;
1884     if (SymbolsDirectlyInvalidated.count(sym))
1885       continue;
1886     SymbolsIndirectlyInvalidated.insert(sym);
1887   }
1888 
1889   if (!SymbolsDirectlyInvalidated.empty())
1890     State = getCheckerManager().runCheckersForPointerEscape(State,
1891         SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall);
1892 
1893   // Notify about the symbols that get indirectly invalidated by the call.
1894   if (!SymbolsIndirectlyInvalidated.empty())
1895     State = getCheckerManager().runCheckersForPointerEscape(State,
1896         SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall);
1897 
1898   return State;
1899 }
1900 
1901 /// evalBind - Handle the semantics of binding a value to a specific location.
1902 ///  This method is used by evalStore and (soon) VisitDeclStmt, and others.
evalBind(ExplodedNodeSet & Dst,const Stmt * StoreE,ExplodedNode * Pred,SVal location,SVal Val,bool atDeclInit,const ProgramPoint * PP)1903 void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
1904                           ExplodedNode *Pred,
1905                           SVal location, SVal Val,
1906                           bool atDeclInit, const ProgramPoint *PP) {
1907 
1908   const LocationContext *LC = Pred->getLocationContext();
1909   PostStmt PS(StoreE, LC);
1910   if (!PP)
1911     PP = &PS;
1912 
1913   // Do a previsit of the bind.
1914   ExplodedNodeSet CheckedSet;
1915   getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
1916                                          StoreE, *this, *PP);
1917 
1918 
1919   StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
1920 
1921   // If the location is not a 'Loc', it will already be handled by
1922   // the checkers.  There is nothing left to do.
1923   if (!location.getAs<Loc>()) {
1924     const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/0, /*tag*/0);
1925     ProgramStateRef state = Pred->getState();
1926     state = processPointerEscapedOnBind(state, location, Val);
1927     Bldr.generateNode(L, state, Pred);
1928     return;
1929   }
1930 
1931 
1932   for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
1933        I!=E; ++I) {
1934     ExplodedNode *PredI = *I;
1935     ProgramStateRef state = PredI->getState();
1936 
1937     state = processPointerEscapedOnBind(state, location, Val);
1938 
1939     // When binding the value, pass on the hint that this is a initialization.
1940     // For initializations, we do not need to inform clients of region
1941     // changes.
1942     state = state->bindLoc(location.castAs<Loc>(),
1943                            Val, /* notifyChanges = */ !atDeclInit);
1944 
1945     const MemRegion *LocReg = 0;
1946     if (Optional<loc::MemRegionVal> LocRegVal =
1947             location.getAs<loc::MemRegionVal>()) {
1948       LocReg = LocRegVal->getRegion();
1949     }
1950 
1951     const ProgramPoint L = PostStore(StoreE, LC, LocReg, 0);
1952     Bldr.generateNode(L, state, PredI);
1953   }
1954 }
1955 
1956 /// evalStore - Handle the semantics of a store via an assignment.
1957 ///  @param Dst The node set to store generated state nodes
1958 ///  @param AssignE The assignment expression if the store happens in an
1959 ///         assignment.
1960 ///  @param LocationE The location expression that is stored to.
1961 ///  @param state The current simulation state
1962 ///  @param location The location to store the value
1963 ///  @param Val The value to be stored
evalStore(ExplodedNodeSet & Dst,const Expr * AssignE,const Expr * LocationE,ExplodedNode * Pred,ProgramStateRef state,SVal location,SVal Val,const ProgramPointTag * tag)1964 void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
1965                              const Expr *LocationE,
1966                              ExplodedNode *Pred,
1967                              ProgramStateRef state, SVal location, SVal Val,
1968                              const ProgramPointTag *tag) {
1969   // Proceed with the store.  We use AssignE as the anchor for the PostStore
1970   // ProgramPoint if it is non-NULL, and LocationE otherwise.
1971   const Expr *StoreE = AssignE ? AssignE : LocationE;
1972 
1973   // Evaluate the location (checks for bad dereferences).
1974   ExplodedNodeSet Tmp;
1975   evalLocation(Tmp, AssignE, LocationE, Pred, state, location, tag, false);
1976 
1977   if (Tmp.empty())
1978     return;
1979 
1980   if (location.isUndef())
1981     return;
1982 
1983   for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI)
1984     evalBind(Dst, StoreE, *NI, location, Val, false);
1985 }
1986 
evalLoad(ExplodedNodeSet & Dst,const Expr * NodeEx,const Expr * BoundEx,ExplodedNode * Pred,ProgramStateRef state,SVal location,const ProgramPointTag * tag,QualType LoadTy)1987 void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
1988                           const Expr *NodeEx,
1989                           const Expr *BoundEx,
1990                           ExplodedNode *Pred,
1991                           ProgramStateRef state,
1992                           SVal location,
1993                           const ProgramPointTag *tag,
1994                           QualType LoadTy)
1995 {
1996   assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
1997 
1998   // Are we loading from a region?  This actually results in two loads; one
1999   // to fetch the address of the referenced value and one to fetch the
2000   // referenced value.
2001   if (const TypedValueRegion *TR =
2002         dyn_cast_or_null<TypedValueRegion>(location.getAsRegion())) {
2003 
2004     QualType ValTy = TR->getValueType();
2005     if (const ReferenceType *RT = ValTy->getAs<ReferenceType>()) {
2006       static SimpleProgramPointTag
2007              loadReferenceTag("ExprEngine : Load Reference");
2008       ExplodedNodeSet Tmp;
2009       evalLoadCommon(Tmp, NodeEx, BoundEx, Pred, state,
2010                      location, &loadReferenceTag,
2011                      getContext().getPointerType(RT->getPointeeType()));
2012 
2013       // Perform the load from the referenced value.
2014       for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end() ; I!=E; ++I) {
2015         state = (*I)->getState();
2016         location = state->getSVal(BoundEx, (*I)->getLocationContext());
2017         evalLoadCommon(Dst, NodeEx, BoundEx, *I, state, location, tag, LoadTy);
2018       }
2019       return;
2020     }
2021   }
2022 
2023   evalLoadCommon(Dst, NodeEx, BoundEx, Pred, state, location, tag, LoadTy);
2024 }
2025 
evalLoadCommon(ExplodedNodeSet & Dst,const Expr * NodeEx,const Expr * BoundEx,ExplodedNode * Pred,ProgramStateRef state,SVal location,const ProgramPointTag * tag,QualType LoadTy)2026 void ExprEngine::evalLoadCommon(ExplodedNodeSet &Dst,
2027                                 const Expr *NodeEx,
2028                                 const Expr *BoundEx,
2029                                 ExplodedNode *Pred,
2030                                 ProgramStateRef state,
2031                                 SVal location,
2032                                 const ProgramPointTag *tag,
2033                                 QualType LoadTy) {
2034   assert(NodeEx);
2035   assert(BoundEx);
2036   // Evaluate the location (checks for bad dereferences).
2037   ExplodedNodeSet Tmp;
2038   evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, tag, true);
2039   if (Tmp.empty())
2040     return;
2041 
2042   StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
2043   if (location.isUndef())
2044     return;
2045 
2046   // Proceed with the load.
2047   for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI!=NE; ++NI) {
2048     state = (*NI)->getState();
2049     const LocationContext *LCtx = (*NI)->getLocationContext();
2050 
2051     SVal V = UnknownVal();
2052     if (location.isValid()) {
2053       if (LoadTy.isNull())
2054         LoadTy = BoundEx->getType();
2055       V = state->getSVal(location.castAs<Loc>(), LoadTy);
2056     }
2057 
2058     Bldr.generateNode(NodeEx, *NI, state->BindExpr(BoundEx, LCtx, V), tag,
2059                       ProgramPoint::PostLoadKind);
2060   }
2061 }
2062 
evalLocation(ExplodedNodeSet & Dst,const Stmt * NodeEx,const Stmt * BoundEx,ExplodedNode * Pred,ProgramStateRef state,SVal location,const ProgramPointTag * tag,bool isLoad)2063 void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
2064                               const Stmt *NodeEx,
2065                               const Stmt *BoundEx,
2066                               ExplodedNode *Pred,
2067                               ProgramStateRef state,
2068                               SVal location,
2069                               const ProgramPointTag *tag,
2070                               bool isLoad) {
2071   StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
2072   // Early checks for performance reason.
2073   if (location.isUnknown()) {
2074     return;
2075   }
2076 
2077   ExplodedNodeSet Src;
2078   BldrTop.takeNodes(Pred);
2079   StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
2080   if (Pred->getState() != state) {
2081     // Associate this new state with an ExplodedNode.
2082     // FIXME: If I pass null tag, the graph is incorrect, e.g for
2083     //   int *p;
2084     //   p = 0;
2085     //   *p = 0xDEADBEEF;
2086     // "p = 0" is not noted as "Null pointer value stored to 'p'" but
2087     // instead "int *p" is noted as
2088     // "Variable 'p' initialized to a null pointer value"
2089 
2090     static SimpleProgramPointTag tag("ExprEngine: Location");
2091     Bldr.generateNode(NodeEx, Pred, state, &tag);
2092   }
2093   ExplodedNodeSet Tmp;
2094   getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
2095                                              NodeEx, BoundEx, *this);
2096   BldrTop.addNodes(Tmp);
2097 }
2098 
2099 std::pair<const ProgramPointTag *, const ProgramPointTag*>
geteagerlyAssumeBinOpBifurcationTags()2100 ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
2101   static SimpleProgramPointTag
2102          eagerlyAssumeBinOpBifurcationTrue("ExprEngine : Eagerly Assume True"),
2103          eagerlyAssumeBinOpBifurcationFalse("ExprEngine : Eagerly Assume False");
2104   return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
2105                         &eagerlyAssumeBinOpBifurcationFalse);
2106 }
2107 
evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet & Dst,ExplodedNodeSet & Src,const Expr * Ex)2108 void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
2109                                                    ExplodedNodeSet &Src,
2110                                                    const Expr *Ex) {
2111   StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
2112 
2113   for (ExplodedNodeSet::iterator I=Src.begin(), E=Src.end(); I!=E; ++I) {
2114     ExplodedNode *Pred = *I;
2115     // Test if the previous node was as the same expression.  This can happen
2116     // when the expression fails to evaluate to anything meaningful and
2117     // (as an optimization) we don't generate a node.
2118     ProgramPoint P = Pred->getLocation();
2119     if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
2120       continue;
2121     }
2122 
2123     ProgramStateRef state = Pred->getState();
2124     SVal V = state->getSVal(Ex, Pred->getLocationContext());
2125     Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
2126     if (SEV && SEV->isExpression()) {
2127       const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
2128         geteagerlyAssumeBinOpBifurcationTags();
2129 
2130       ProgramStateRef StateTrue, StateFalse;
2131       tie(StateTrue, StateFalse) = state->assume(*SEV);
2132 
2133       // First assume that the condition is true.
2134       if (StateTrue) {
2135         SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
2136         StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
2137         Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
2138       }
2139 
2140       // Next, assume that the condition is false.
2141       if (StateFalse) {
2142         SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
2143         StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
2144         Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
2145       }
2146     }
2147   }
2148 }
2149 
VisitGCCAsmStmt(const GCCAsmStmt * A,ExplodedNode * Pred,ExplodedNodeSet & Dst)2150 void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
2151                                  ExplodedNodeSet &Dst) {
2152   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2153   // We have processed both the inputs and the outputs.  All of the outputs
2154   // should evaluate to Locs.  Nuke all of their values.
2155 
2156   // FIXME: Some day in the future it would be nice to allow a "plug-in"
2157   // which interprets the inline asm and stores proper results in the
2158   // outputs.
2159 
2160   ProgramStateRef state = Pred->getState();
2161 
2162   for (GCCAsmStmt::const_outputs_iterator OI = A->begin_outputs(),
2163        OE = A->end_outputs(); OI != OE; ++OI) {
2164     SVal X = state->getSVal(*OI, Pred->getLocationContext());
2165     assert (!X.getAs<NonLoc>());  // Should be an Lval, or unknown, undef.
2166 
2167     if (Optional<Loc> LV = X.getAs<Loc>())
2168       state = state->bindLoc(*LV, UnknownVal());
2169   }
2170 
2171   Bldr.generateNode(A, Pred, state);
2172 }
2173 
VisitMSAsmStmt(const MSAsmStmt * A,ExplodedNode * Pred,ExplodedNodeSet & Dst)2174 void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
2175                                 ExplodedNodeSet &Dst) {
2176   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2177   Bldr.generateNode(A, Pred, Pred->getState());
2178 }
2179 
2180 //===----------------------------------------------------------------------===//
2181 // Visualization.
2182 //===----------------------------------------------------------------------===//
2183 
2184 #ifndef NDEBUG
2185 static ExprEngine* GraphPrintCheckerState;
2186 static SourceManager* GraphPrintSourceManager;
2187 
2188 namespace llvm {
2189 template<>
2190 struct DOTGraphTraits<ExplodedNode*> :
2191   public DefaultDOTGraphTraits {
2192 
DOTGraphTraitsllvm::DOTGraphTraits2193   DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
2194 
2195   // FIXME: Since we do not cache error nodes in ExprEngine now, this does not
2196   // work.
getNodeAttributesllvm::DOTGraphTraits2197   static std::string getNodeAttributes(const ExplodedNode *N, void*) {
2198 
2199 #if 0
2200       // FIXME: Replace with a general scheme to tell if the node is
2201       // an error node.
2202     if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
2203         GraphPrintCheckerState->isExplicitNullDeref(N) ||
2204         GraphPrintCheckerState->isUndefDeref(N) ||
2205         GraphPrintCheckerState->isUndefStore(N) ||
2206         GraphPrintCheckerState->isUndefControlFlow(N) ||
2207         GraphPrintCheckerState->isUndefResult(N) ||
2208         GraphPrintCheckerState->isBadCall(N) ||
2209         GraphPrintCheckerState->isUndefArg(N))
2210       return "color=\"red\",style=\"filled\"";
2211 
2212     if (GraphPrintCheckerState->isNoReturnCall(N))
2213       return "color=\"blue\",style=\"filled\"";
2214 #endif
2215     return "";
2216   }
2217 
printLocationllvm::DOTGraphTraits2218   static void printLocation(raw_ostream &Out, SourceLocation SLoc) {
2219     if (SLoc.isFileID()) {
2220       Out << "\\lline="
2221         << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2222         << " col="
2223         << GraphPrintSourceManager->getExpansionColumnNumber(SLoc)
2224         << "\\l";
2225     }
2226   }
2227 
getNodeLabelllvm::DOTGraphTraits2228   static std::string getNodeLabel(const ExplodedNode *N, void*){
2229 
2230     std::string sbuf;
2231     llvm::raw_string_ostream Out(sbuf);
2232 
2233     // Program Location.
2234     ProgramPoint Loc = N->getLocation();
2235 
2236     switch (Loc.getKind()) {
2237       case ProgramPoint::BlockEntranceKind: {
2238         Out << "Block Entrance: B"
2239             << Loc.castAs<BlockEntrance>().getBlock()->getBlockID();
2240         if (const NamedDecl *ND =
2241                     dyn_cast<NamedDecl>(Loc.getLocationContext()->getDecl())) {
2242           Out << " (";
2243           ND->printName(Out);
2244           Out << ")";
2245         }
2246         break;
2247       }
2248 
2249       case ProgramPoint::BlockExitKind:
2250         assert (false);
2251         break;
2252 
2253       case ProgramPoint::CallEnterKind:
2254         Out << "CallEnter";
2255         break;
2256 
2257       case ProgramPoint::CallExitBeginKind:
2258         Out << "CallExitBegin";
2259         break;
2260 
2261       case ProgramPoint::CallExitEndKind:
2262         Out << "CallExitEnd";
2263         break;
2264 
2265       case ProgramPoint::PostStmtPurgeDeadSymbolsKind:
2266         Out << "PostStmtPurgeDeadSymbols";
2267         break;
2268 
2269       case ProgramPoint::PreStmtPurgeDeadSymbolsKind:
2270         Out << "PreStmtPurgeDeadSymbols";
2271         break;
2272 
2273       case ProgramPoint::EpsilonKind:
2274         Out << "Epsilon Point";
2275         break;
2276 
2277       case ProgramPoint::PreImplicitCallKind: {
2278         ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
2279         Out << "PreCall: ";
2280 
2281         // FIXME: Get proper printing options.
2282         PC.getDecl()->print(Out, LangOptions());
2283         printLocation(Out, PC.getLocation());
2284         break;
2285       }
2286 
2287       case ProgramPoint::PostImplicitCallKind: {
2288         ImplicitCallPoint PC = Loc.castAs<ImplicitCallPoint>();
2289         Out << "PostCall: ";
2290 
2291         // FIXME: Get proper printing options.
2292         PC.getDecl()->print(Out, LangOptions());
2293         printLocation(Out, PC.getLocation());
2294         break;
2295       }
2296 
2297       case ProgramPoint::PostInitializerKind: {
2298         Out << "PostInitializer: ";
2299         const CXXCtorInitializer *Init =
2300           Loc.castAs<PostInitializer>().getInitializer();
2301         if (const FieldDecl *FD = Init->getAnyMember())
2302           Out << *FD;
2303         else {
2304           QualType Ty = Init->getTypeSourceInfo()->getType();
2305           Ty = Ty.getLocalUnqualifiedType();
2306           LangOptions LO; // FIXME.
2307           Ty.print(Out, LO);
2308         }
2309         break;
2310       }
2311 
2312       case ProgramPoint::BlockEdgeKind: {
2313         const BlockEdge &E = Loc.castAs<BlockEdge>();
2314         Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
2315             << E.getDst()->getBlockID()  << ')';
2316 
2317         if (const Stmt *T = E.getSrc()->getTerminator()) {
2318           SourceLocation SLoc = T->getLocStart();
2319 
2320           Out << "\\|Terminator: ";
2321           LangOptions LO; // FIXME.
2322           E.getSrc()->printTerminator(Out, LO);
2323 
2324           if (SLoc.isFileID()) {
2325             Out << "\\lline="
2326               << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
2327               << " col="
2328               << GraphPrintSourceManager->getExpansionColumnNumber(SLoc);
2329           }
2330 
2331           if (isa<SwitchStmt>(T)) {
2332             const Stmt *Label = E.getDst()->getLabel();
2333 
2334             if (Label) {
2335               if (const CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
2336                 Out << "\\lcase ";
2337                 LangOptions LO; // FIXME.
2338                 C->getLHS()->printPretty(Out, 0, PrintingPolicy(LO));
2339 
2340                 if (const Stmt *RHS = C->getRHS()) {
2341                   Out << " .. ";
2342                   RHS->printPretty(Out, 0, PrintingPolicy(LO));
2343                 }
2344 
2345                 Out << ":";
2346               }
2347               else {
2348                 assert (isa<DefaultStmt>(Label));
2349                 Out << "\\ldefault:";
2350               }
2351             }
2352             else
2353               Out << "\\l(implicit) default:";
2354           }
2355           else if (isa<IndirectGotoStmt>(T)) {
2356             // FIXME
2357           }
2358           else {
2359             Out << "\\lCondition: ";
2360             if (*E.getSrc()->succ_begin() == E.getDst())
2361               Out << "true";
2362             else
2363               Out << "false";
2364           }
2365 
2366           Out << "\\l";
2367         }
2368 
2369 #if 0
2370           // FIXME: Replace with a general scheme to determine
2371           // the name of the check.
2372         if (GraphPrintCheckerState->isUndefControlFlow(N)) {
2373           Out << "\\|Control-flow based on\\lUndefined value.\\l";
2374         }
2375 #endif
2376         break;
2377       }
2378 
2379       default: {
2380         const Stmt *S = Loc.castAs<StmtPoint>().getStmt();
2381 
2382         Out << S->getStmtClassName() << ' ' << (const void*) S << ' ';
2383         LangOptions LO; // FIXME.
2384         S->printPretty(Out, 0, PrintingPolicy(LO));
2385         printLocation(Out, S->getLocStart());
2386 
2387         if (Loc.getAs<PreStmt>())
2388           Out << "\\lPreStmt\\l;";
2389         else if (Loc.getAs<PostLoad>())
2390           Out << "\\lPostLoad\\l;";
2391         else if (Loc.getAs<PostStore>())
2392           Out << "\\lPostStore\\l";
2393         else if (Loc.getAs<PostLValue>())
2394           Out << "\\lPostLValue\\l";
2395 
2396 #if 0
2397           // FIXME: Replace with a general scheme to determine
2398           // the name of the check.
2399         if (GraphPrintCheckerState->isImplicitNullDeref(N))
2400           Out << "\\|Implicit-Null Dereference.\\l";
2401         else if (GraphPrintCheckerState->isExplicitNullDeref(N))
2402           Out << "\\|Explicit-Null Dereference.\\l";
2403         else if (GraphPrintCheckerState->isUndefDeref(N))
2404           Out << "\\|Dereference of undefialied value.\\l";
2405         else if (GraphPrintCheckerState->isUndefStore(N))
2406           Out << "\\|Store to Undefined Loc.";
2407         else if (GraphPrintCheckerState->isUndefResult(N))
2408           Out << "\\|Result of operation is undefined.";
2409         else if (GraphPrintCheckerState->isNoReturnCall(N))
2410           Out << "\\|Call to function marked \"noreturn\".";
2411         else if (GraphPrintCheckerState->isBadCall(N))
2412           Out << "\\|Call to NULL/Undefined.";
2413         else if (GraphPrintCheckerState->isUndefArg(N))
2414           Out << "\\|Argument in call is undefined";
2415 #endif
2416 
2417         break;
2418       }
2419     }
2420 
2421     ProgramStateRef state = N->getState();
2422     Out << "\\|StateID: " << (const void*) state.getPtr()
2423         << " NodeID: " << (const void*) N << "\\|";
2424     state->printDOT(Out);
2425 
2426     Out << "\\l";
2427 
2428     if (const ProgramPointTag *tag = Loc.getTag()) {
2429       Out << "\\|Tag: " << tag->getTagDescription();
2430       Out << "\\l";
2431     }
2432     return Out.str();
2433   }
2434 };
2435 } // end llvm namespace
2436 #endif
2437 
2438 #ifndef NDEBUG
2439 template <typename ITERATOR>
GetGraphNode(ITERATOR I)2440 ExplodedNode *GetGraphNode(ITERATOR I) { return *I; }
2441 
2442 template <> ExplodedNode*
GetGraphNode(llvm::DenseMap<ExplodedNode *,Expr * >::iterator I)2443 GetGraphNode<llvm::DenseMap<ExplodedNode*, Expr*>::iterator>
2444   (llvm::DenseMap<ExplodedNode*, Expr*>::iterator I) {
2445   return I->first;
2446 }
2447 #endif
2448 
ViewGraph(bool trim)2449 void ExprEngine::ViewGraph(bool trim) {
2450 #ifndef NDEBUG
2451   if (trim) {
2452     std::vector<const ExplodedNode*> Src;
2453 
2454     // Flush any outstanding reports to make sure we cover all the nodes.
2455     // This does not cause them to get displayed.
2456     for (BugReporter::iterator I=BR.begin(), E=BR.end(); I!=E; ++I)
2457       const_cast<BugType*>(*I)->FlushReports(BR);
2458 
2459     // Iterate through the reports and get their nodes.
2460     for (BugReporter::EQClasses_iterator
2461            EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
2462       ExplodedNode *N = const_cast<ExplodedNode*>(EI->begin()->getErrorNode());
2463       if (N) Src.push_back(N);
2464     }
2465 
2466     ViewGraph(Src);
2467   }
2468   else {
2469     GraphPrintCheckerState = this;
2470     GraphPrintSourceManager = &getContext().getSourceManager();
2471 
2472     llvm::ViewGraph(*G.roots_begin(), "ExprEngine");
2473 
2474     GraphPrintCheckerState = NULL;
2475     GraphPrintSourceManager = NULL;
2476   }
2477 #endif
2478 }
2479 
ViewGraph(ArrayRef<const ExplodedNode * > Nodes)2480 void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) {
2481 #ifndef NDEBUG
2482   GraphPrintCheckerState = this;
2483   GraphPrintSourceManager = &getContext().getSourceManager();
2484 
2485   OwningPtr<ExplodedGraph> TrimmedG(G.trim(Nodes));
2486 
2487   if (!TrimmedG.get())
2488     llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
2489   else
2490     llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedExprEngine");
2491 
2492   GraphPrintCheckerState = NULL;
2493   GraphPrintSourceManager = NULL;
2494 #endif
2495 }
2496