xref: /freebsd-src/contrib/llvm-project/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp (revision a7dea1671b87c07d2d266f836bfa8b58efc7c134)
1 //===- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 //  This file defines a meta-engine for path-sensitive dataflow analysis that
10 //  is built on GREngine, but provides the boilerplate to execute transfer
11 //  functions and build the ExplodedGraph at the expression level.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
16 #include "PrettyStackTraceLocationContext.h"
17 #include "clang/AST/ASTContext.h"
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/DeclBase.h"
20 #include "clang/AST/DeclCXX.h"
21 #include "clang/AST/DeclObjC.h"
22 #include "clang/AST/Expr.h"
23 #include "clang/AST/ExprCXX.h"
24 #include "clang/AST/ExprObjC.h"
25 #include "clang/AST/ParentMap.h"
26 #include "clang/AST/PrettyPrinter.h"
27 #include "clang/AST/Stmt.h"
28 #include "clang/AST/StmtCXX.h"
29 #include "clang/AST/StmtObjC.h"
30 #include "clang/AST/Type.h"
31 #include "clang/Analysis/AnalysisDeclContext.h"
32 #include "clang/Analysis/CFG.h"
33 #include "clang/Analysis/ConstructionContext.h"
34 #include "clang/Analysis/ProgramPoint.h"
35 #include "clang/Basic/IdentifierTable.h"
36 #include "clang/Basic/JsonSupport.h"
37 #include "clang/Basic/LLVM.h"
38 #include "clang/Basic/LangOptions.h"
39 #include "clang/Basic/PrettyStackTrace.h"
40 #include "clang/Basic/SourceLocation.h"
41 #include "clang/Basic/SourceManager.h"
42 #include "clang/Basic/Specifiers.h"
43 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
44 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
45 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
46 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
47 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
48 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
49 #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
50 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
51 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
52 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
53 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
54 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
55 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
56 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
57 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
58 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
59 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
60 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
61 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
62 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
63 #include "llvm/ADT/APSInt.h"
64 #include "llvm/ADT/DenseMap.h"
65 #include "llvm/ADT/ImmutableMap.h"
66 #include "llvm/ADT/ImmutableSet.h"
67 #include "llvm/ADT/Optional.h"
68 #include "llvm/ADT/SmallVector.h"
69 #include "llvm/ADT/Statistic.h"
70 #include "llvm/Support/Casting.h"
71 #include "llvm/Support/Compiler.h"
72 #include "llvm/Support/DOTGraphTraits.h"
73 #include "llvm/Support/ErrorHandling.h"
74 #include "llvm/Support/GraphWriter.h"
75 #include "llvm/Support/SaveAndRestore.h"
76 #include "llvm/Support/raw_ostream.h"
77 #include <cassert>
78 #include <cstdint>
79 #include <memory>
80 #include <string>
81 #include <tuple>
82 #include <utility>
83 #include <vector>
84 
85 using namespace clang;
86 using namespace ento;
87 
88 #define DEBUG_TYPE "ExprEngine"
89 
90 STATISTIC(NumRemoveDeadBindings,
91             "The # of times RemoveDeadBindings is called");
92 STATISTIC(NumMaxBlockCountReached,
93             "The # of aborted paths due to reaching the maximum block count in "
94             "a top level function");
95 STATISTIC(NumMaxBlockCountReachedInInlined,
96             "The # of aborted paths due to reaching the maximum block count in "
97             "an inlined function");
98 STATISTIC(NumTimesRetriedWithoutInlining,
99             "The # of times we re-evaluated a call without inlining");
100 
101 //===----------------------------------------------------------------------===//
102 // Internal program state traits.
103 //===----------------------------------------------------------------------===//
104 
105 namespace {
106 
107 // When modeling a C++ constructor, for a variety of reasons we need to track
108 // the location of the object for the duration of its ConstructionContext.
109 // ObjectsUnderConstruction maps statements within the construction context
110 // to the object's location, so that on every such statement the location
111 // could have been retrieved.
112 
113 /// ConstructedObjectKey is used for being able to find the path-sensitive
114 /// memory region of a freshly constructed object while modeling the AST node
115 /// that syntactically represents the object that is being constructed.
116 /// Semantics of such nodes may sometimes require access to the region that's
117 /// not otherwise present in the program state, or to the very fact that
118 /// the construction context was present and contained references to these
119 /// AST nodes.
120 class ConstructedObjectKey {
121   typedef std::pair<ConstructionContextItem, const LocationContext *>
122       ConstructedObjectKeyImpl;
123 
124   const ConstructedObjectKeyImpl Impl;
125 
126   const void *getAnyASTNodePtr() const {
127     if (const Stmt *S = getItem().getStmtOrNull())
128       return S;
129     else
130       return getItem().getCXXCtorInitializer();
131   }
132 
133 public:
134   explicit ConstructedObjectKey(const ConstructionContextItem &Item,
135                        const LocationContext *LC)
136       : Impl(Item, LC) {}
137 
138   const ConstructionContextItem &getItem() const { return Impl.first; }
139   const LocationContext *getLocationContext() const { return Impl.second; }
140 
141   ASTContext &getASTContext() const {
142     return getLocationContext()->getDecl()->getASTContext();
143   }
144 
145   void printJson(llvm::raw_ostream &Out, PrinterHelper *Helper,
146                  PrintingPolicy &PP) const {
147     const Stmt *S = getItem().getStmtOrNull();
148     const CXXCtorInitializer *I = nullptr;
149     if (!S)
150       I = getItem().getCXXCtorInitializer();
151 
152     if (S)
153       Out << "\"stmt_id\": " << S->getID(getASTContext());
154     else
155       Out << "\"init_id\": " << I->getID(getASTContext());
156 
157     // Kind
158     Out << ", \"kind\": \"" << getItem().getKindAsString()
159         << "\", \"argument_index\": ";
160 
161     if (getItem().getKind() == ConstructionContextItem::ArgumentKind)
162       Out << getItem().getIndex();
163     else
164       Out << "null";
165 
166     // Pretty-print
167     Out << ", \"pretty\": ";
168 
169     if (S) {
170       S->printJson(Out, Helper, PP, /*AddQuotes=*/true);
171     } else {
172       Out << '\"' << I->getAnyMember()->getNameAsString() << '\"';
173     }
174   }
175 
176   void Profile(llvm::FoldingSetNodeID &ID) const {
177     ID.Add(Impl.first);
178     ID.AddPointer(Impl.second);
179   }
180 
181   bool operator==(const ConstructedObjectKey &RHS) const {
182     return Impl == RHS.Impl;
183   }
184 
185   bool operator<(const ConstructedObjectKey &RHS) const {
186     return Impl < RHS.Impl;
187   }
188 };
189 } // namespace
190 
191 typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>
192     ObjectsUnderConstructionMap;
193 REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction,
194                                  ObjectsUnderConstructionMap)
195 
196 //===----------------------------------------------------------------------===//
197 // Engine construction and deletion.
198 //===----------------------------------------------------------------------===//
199 
200 static const char* TagProviderName = "ExprEngine";
201 
202 ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU,
203                        AnalysisManager &mgr,
204                        SetOfConstDecls *VisitedCalleesIn,
205                        FunctionSummariesTy *FS,
206                        InliningModes HowToInlineIn)
207     : CTU(CTU), AMgr(mgr),
208       AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
209       Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()),
210       StateMgr(getContext(), mgr.getStoreManagerCreator(),
211                mgr.getConstraintManagerCreator(), G.getAllocator(),
212                this),
213       SymMgr(StateMgr.getSymbolManager()),
214       MRMgr(StateMgr.getRegionManager()),
215       svalBuilder(StateMgr.getSValBuilder()),
216       ObjCNoRet(mgr.getASTContext()),
217       BR(mgr, *this),
218       VisitedCallees(VisitedCalleesIn),
219       HowToInline(HowToInlineIn)
220   {
221   unsigned TrimInterval = mgr.options.GraphTrimInterval;
222   if (TrimInterval != 0) {
223     // Enable eager node reclamation when constructing the ExplodedGraph.
224     G.enableNodeReclamation(TrimInterval);
225   }
226 }
227 
228 //===----------------------------------------------------------------------===//
229 // Utility methods.
230 //===----------------------------------------------------------------------===//
231 
232 ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
233   ProgramStateRef state = StateMgr.getInitialState(InitLoc);
234   const Decl *D = InitLoc->getDecl();
235 
236   // Preconditions.
237   // FIXME: It would be nice if we had a more general mechanism to add
238   // such preconditions.  Some day.
239   do {
240     if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
241       // Precondition: the first argument of 'main' is an integer guaranteed
242       //  to be > 0.
243       const IdentifierInfo *II = FD->getIdentifier();
244       if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
245         break;
246 
247       const ParmVarDecl *PD = FD->getParamDecl(0);
248       QualType T = PD->getType();
249       const auto *BT = dyn_cast<BuiltinType>(T);
250       if (!BT || !BT->isInteger())
251         break;
252 
253       const MemRegion *R = state->getRegion(PD, InitLoc);
254       if (!R)
255         break;
256 
257       SVal V = state->getSVal(loc::MemRegionVal(R));
258       SVal Constraint_untested = evalBinOp(state, BO_GT, V,
259                                            svalBuilder.makeZeroVal(T),
260                                            svalBuilder.getConditionType());
261 
262       Optional<DefinedOrUnknownSVal> Constraint =
263           Constraint_untested.getAs<DefinedOrUnknownSVal>();
264 
265       if (!Constraint)
266         break;
267 
268       if (ProgramStateRef newState = state->assume(*Constraint, true))
269         state = newState;
270     }
271     break;
272   }
273   while (false);
274 
275   if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
276     // Precondition: 'self' is always non-null upon entry to an Objective-C
277     // method.
278     const ImplicitParamDecl *SelfD = MD->getSelfDecl();
279     const MemRegion *R = state->getRegion(SelfD, InitLoc);
280     SVal V = state->getSVal(loc::MemRegionVal(R));
281 
282     if (Optional<Loc> LV = V.getAs<Loc>()) {
283       // Assume that the pointer value in 'self' is non-null.
284       state = state->assume(*LV, true);
285       assert(state && "'self' cannot be null");
286     }
287   }
288 
289   if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {
290     if (!MD->isStatic()) {
291       // Precondition: 'this' is always non-null upon entry to the
292       // top-level function.  This is our starting assumption for
293       // analyzing an "open" program.
294       const StackFrameContext *SFC = InitLoc->getStackFrame();
295       if (SFC->getParent() == nullptr) {
296         loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC);
297         SVal V = state->getSVal(L);
298         if (Optional<Loc> LV = V.getAs<Loc>()) {
299           state = state->assume(*LV, true);
300           assert(state && "'this' cannot be null");
301         }
302       }
303     }
304   }
305 
306   return state;
307 }
308 
309 ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded(
310     ProgramStateRef State, const LocationContext *LC,
311     const Expr *InitWithAdjustments, const Expr *Result,
312     const SubRegion **OutRegionWithAdjustments) {
313   // FIXME: This function is a hack that works around the quirky AST
314   // we're often having with respect to C++ temporaries. If only we modelled
315   // the actual execution order of statements properly in the CFG,
316   // all the hassle with adjustments would not be necessary,
317   // and perhaps the whole function would be removed.
318   SVal InitValWithAdjustments = State->getSVal(InitWithAdjustments, LC);
319   if (!Result) {
320     // If we don't have an explicit result expression, we're in "if needed"
321     // mode. Only create a region if the current value is a NonLoc.
322     if (!InitValWithAdjustments.getAs<NonLoc>()) {
323       if (OutRegionWithAdjustments)
324         *OutRegionWithAdjustments = nullptr;
325       return State;
326     }
327     Result = InitWithAdjustments;
328   } else {
329     // We need to create a region no matter what. For sanity, make sure we don't
330     // try to stuff a Loc into a non-pointer temporary region.
331     assert(!InitValWithAdjustments.getAs<Loc>() ||
332            Loc::isLocType(Result->getType()) ||
333            Result->getType()->isMemberPointerType());
334   }
335 
336   ProgramStateManager &StateMgr = State->getStateManager();
337   MemRegionManager &MRMgr = StateMgr.getRegionManager();
338   StoreManager &StoreMgr = StateMgr.getStoreManager();
339 
340   // MaterializeTemporaryExpr may appear out of place, after a few field and
341   // base-class accesses have been made to the object, even though semantically
342   // it is the whole object that gets materialized and lifetime-extended.
343   //
344   // For example:
345   //
346   //   `-MaterializeTemporaryExpr
347   //     `-MemberExpr
348   //       `-CXXTemporaryObjectExpr
349   //
350   // instead of the more natural
351   //
352   //   `-MemberExpr
353   //     `-MaterializeTemporaryExpr
354   //       `-CXXTemporaryObjectExpr
355   //
356   // Use the usual methods for obtaining the expression of the base object,
357   // and record the adjustments that we need to make to obtain the sub-object
358   // that the whole expression 'Ex' refers to. This trick is usual,
359   // in the sense that CodeGen takes a similar route.
360 
361   SmallVector<const Expr *, 2> CommaLHSs;
362   SmallVector<SubobjectAdjustment, 2> Adjustments;
363 
364   const Expr *Init = InitWithAdjustments->skipRValueSubobjectAdjustments(
365       CommaLHSs, Adjustments);
366 
367   // Take the region for Init, i.e. for the whole object. If we do not remember
368   // the region in which the object originally was constructed, come up with
369   // a new temporary region out of thin air and copy the contents of the object
370   // (which are currently present in the Environment, because Init is an rvalue)
371   // into that region. This is not correct, but it is better than nothing.
372   const TypedValueRegion *TR = nullptr;
373   if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) {
374     if (Optional<SVal> V = getObjectUnderConstruction(State, MT, LC)) {
375       State = finishObjectConstruction(State, MT, LC);
376       State = State->BindExpr(Result, LC, *V);
377       return State;
378     } else {
379       StorageDuration SD = MT->getStorageDuration();
380       // If this object is bound to a reference with static storage duration, we
381       // put it in a different region to prevent "address leakage" warnings.
382       if (SD == SD_Static || SD == SD_Thread) {
383         TR = MRMgr.getCXXStaticTempObjectRegion(Init);
384       } else {
385         TR = MRMgr.getCXXTempObjectRegion(Init, LC);
386       }
387     }
388   } else {
389     TR = MRMgr.getCXXTempObjectRegion(Init, LC);
390   }
391 
392   SVal Reg = loc::MemRegionVal(TR);
393   SVal BaseReg = Reg;
394 
395   // Make the necessary adjustments to obtain the sub-object.
396   for (auto I = Adjustments.rbegin(), E = Adjustments.rend(); I != E; ++I) {
397     const SubobjectAdjustment &Adj = *I;
398     switch (Adj.Kind) {
399     case SubobjectAdjustment::DerivedToBaseAdjustment:
400       Reg = StoreMgr.evalDerivedToBase(Reg, Adj.DerivedToBase.BasePath);
401       break;
402     case SubobjectAdjustment::FieldAdjustment:
403       Reg = StoreMgr.getLValueField(Adj.Field, Reg);
404       break;
405     case SubobjectAdjustment::MemberPointerAdjustment:
406       // FIXME: Unimplemented.
407       State = State->invalidateRegions(Reg, InitWithAdjustments,
408                                        currBldrCtx->blockCount(), LC, true,
409                                        nullptr, nullptr, nullptr);
410       return State;
411     }
412   }
413 
414   // What remains is to copy the value of the object to the new region.
415   // FIXME: In other words, what we should always do is copy value of the
416   // Init expression (which corresponds to the bigger object) to the whole
417   // temporary region TR. However, this value is often no longer present
418   // in the Environment. If it has disappeared, we instead invalidate TR.
419   // Still, what we can do is assign the value of expression Ex (which
420   // corresponds to the sub-object) to the TR's sub-region Reg. At least,
421   // values inside Reg would be correct.
422   SVal InitVal = State->getSVal(Init, LC);
423   if (InitVal.isUnknown()) {
424     InitVal = getSValBuilder().conjureSymbolVal(Result, LC, Init->getType(),
425                                                 currBldrCtx->blockCount());
426     State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
427 
428     // Then we'd need to take the value that certainly exists and bind it
429     // over.
430     if (InitValWithAdjustments.isUnknown()) {
431       // Try to recover some path sensitivity in case we couldn't
432       // compute the value.
433       InitValWithAdjustments = getSValBuilder().conjureSymbolVal(
434           Result, LC, InitWithAdjustments->getType(),
435           currBldrCtx->blockCount());
436     }
437     State =
438         State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false);
439   } else {
440     State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
441   }
442 
443   // The result expression would now point to the correct sub-region of the
444   // newly created temporary region. Do this last in order to getSVal of Init
445   // correctly in case (Result == Init).
446   if (Result->isGLValue()) {
447     State = State->BindExpr(Result, LC, Reg);
448   } else {
449     State = State->BindExpr(Result, LC, InitValWithAdjustments);
450   }
451 
452   // Notify checkers once for two bindLoc()s.
453   State = processRegionChange(State, TR, LC);
454 
455   if (OutRegionWithAdjustments)
456     *OutRegionWithAdjustments = cast<SubRegion>(Reg.getAsRegion());
457   return State;
458 }
459 
460 ProgramStateRef
461 ExprEngine::addObjectUnderConstruction(ProgramStateRef State,
462                                        const ConstructionContextItem &Item,
463                                        const LocationContext *LC, SVal V) {
464   ConstructedObjectKey Key(Item, LC->getStackFrame());
465   // FIXME: Currently the state might already contain the marker due to
466   // incorrect handling of temporaries bound to default parameters.
467   assert(!State->get<ObjectsUnderConstruction>(Key) ||
468          Key.getItem().getKind() ==
469              ConstructionContextItem::TemporaryDestructorKind);
470   return State->set<ObjectsUnderConstruction>(Key, V);
471 }
472 
473 Optional<SVal>
474 ExprEngine::getObjectUnderConstruction(ProgramStateRef State,
475                                        const ConstructionContextItem &Item,
476                                        const LocationContext *LC) {
477   ConstructedObjectKey Key(Item, LC->getStackFrame());
478   return Optional<SVal>::create(State->get<ObjectsUnderConstruction>(Key));
479 }
480 
481 ProgramStateRef
482 ExprEngine::finishObjectConstruction(ProgramStateRef State,
483                                      const ConstructionContextItem &Item,
484                                      const LocationContext *LC) {
485   ConstructedObjectKey Key(Item, LC->getStackFrame());
486   assert(State->contains<ObjectsUnderConstruction>(Key));
487   return State->remove<ObjectsUnderConstruction>(Key);
488 }
489 
490 ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State,
491                                             const CXXBindTemporaryExpr *BTE,
492                                             const LocationContext *LC) {
493   ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
494   // FIXME: Currently the state might already contain the marker due to
495   // incorrect handling of temporaries bound to default parameters.
496   return State->set<ObjectsUnderConstruction>(Key, UnknownVal());
497 }
498 
499 ProgramStateRef
500 ExprEngine::cleanupElidedDestructor(ProgramStateRef State,
501                                     const CXXBindTemporaryExpr *BTE,
502                                     const LocationContext *LC) {
503   ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
504   assert(State->contains<ObjectsUnderConstruction>(Key));
505   return State->remove<ObjectsUnderConstruction>(Key);
506 }
507 
508 bool ExprEngine::isDestructorElided(ProgramStateRef State,
509                                     const CXXBindTemporaryExpr *BTE,
510                                     const LocationContext *LC) {
511   ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
512   return State->contains<ObjectsUnderConstruction>(Key);
513 }
514 
515 bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State,
516                                                const LocationContext *FromLC,
517                                                const LocationContext *ToLC) {
518   const LocationContext *LC = FromLC;
519   while (LC != ToLC) {
520     assert(LC && "ToLC must be a parent of FromLC!");
521     for (auto I : State->get<ObjectsUnderConstruction>())
522       if (I.first.getLocationContext() == LC)
523         return false;
524 
525     LC = LC->getParent();
526   }
527   return true;
528 }
529 
530 
531 //===----------------------------------------------------------------------===//
532 // Top-level transfer function logic (Dispatcher).
533 //===----------------------------------------------------------------------===//
534 
535 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
536 ///  logic for handling assumptions on symbolic values.
537 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
538                                               SVal cond, bool assumption) {
539   return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
540 }
541 
542 ProgramStateRef
543 ExprEngine::processRegionChanges(ProgramStateRef state,
544                                  const InvalidatedSymbols *invalidated,
545                                  ArrayRef<const MemRegion *> Explicits,
546                                  ArrayRef<const MemRegion *> Regions,
547                                  const LocationContext *LCtx,
548                                  const CallEvent *Call) {
549   return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
550                                                          Explicits, Regions,
551                                                          LCtx, Call);
552 }
553 
554 static void
555 printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State,
556                                   const char *NL, const LocationContext *LCtx,
557                                   unsigned int Space = 0, bool IsDot = false) {
558   PrintingPolicy PP =
559       LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy();
560 
561   ++Space;
562   bool HasItem = false;
563 
564   // Store the last key.
565   const ConstructedObjectKey *LastKey = nullptr;
566   for (const auto &I : State->get<ObjectsUnderConstruction>()) {
567     const ConstructedObjectKey &Key = I.first;
568     if (Key.getLocationContext() != LCtx)
569       continue;
570 
571     if (!HasItem) {
572       Out << "[" << NL;
573       HasItem = true;
574     }
575 
576     LastKey = &Key;
577   }
578 
579   for (const auto &I : State->get<ObjectsUnderConstruction>()) {
580     const ConstructedObjectKey &Key = I.first;
581     SVal Value = I.second;
582     if (Key.getLocationContext() != LCtx)
583       continue;
584 
585     Indent(Out, Space, IsDot) << "{ ";
586     Key.printJson(Out, nullptr, PP);
587     Out << ", \"value\": \"" << Value << "\" }";
588 
589     if (&Key != LastKey)
590       Out << ',';
591     Out << NL;
592   }
593 
594   if (HasItem)
595     Indent(Out, --Space, IsDot) << ']'; // End of "location_context".
596   else {
597     Out << "null ";
598   }
599 }
600 
601 void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State,
602                            const LocationContext *LCtx, const char *NL,
603                            unsigned int Space, bool IsDot) const {
604   Indent(Out, Space, IsDot) << "\"constructing_objects\": ";
605 
606   if (LCtx && !State->get<ObjectsUnderConstruction>().isEmpty()) {
607     ++Space;
608     Out << '[' << NL;
609     LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {
610       printObjectsUnderConstructionJson(Out, State, NL, LC, Space, IsDot);
611     });
612 
613     --Space;
614     Indent(Out, Space, IsDot) << "]," << NL; // End of "constructing_objects".
615   } else {
616     Out << "null," << NL;
617   }
618 
619   getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space,
620                                                    IsDot);
621 }
622 
623 void ExprEngine::processEndWorklist() {
624   getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
625 }
626 
627 void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
628                                    unsigned StmtIdx, NodeBuilderContext *Ctx) {
629   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
630   currStmtIdx = StmtIdx;
631   currBldrCtx = Ctx;
632 
633   switch (E.getKind()) {
634     case CFGElement::Statement:
635     case CFGElement::Constructor:
636     case CFGElement::CXXRecordTypedCall:
637       ProcessStmt(E.castAs<CFGStmt>().getStmt(), Pred);
638       return;
639     case CFGElement::Initializer:
640       ProcessInitializer(E.castAs<CFGInitializer>(), Pred);
641       return;
642     case CFGElement::NewAllocator:
643       ProcessNewAllocator(E.castAs<CFGNewAllocator>().getAllocatorExpr(),
644                           Pred);
645       return;
646     case CFGElement::AutomaticObjectDtor:
647     case CFGElement::DeleteDtor:
648     case CFGElement::BaseDtor:
649     case CFGElement::MemberDtor:
650     case CFGElement::TemporaryDtor:
651       ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
652       return;
653     case CFGElement::LoopExit:
654       ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred);
655       return;
656     case CFGElement::LifetimeEnds:
657     case CFGElement::ScopeBegin:
658     case CFGElement::ScopeEnd:
659       return;
660   }
661 }
662 
663 static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
664                                      const Stmt *S,
665                                      const ExplodedNode *Pred,
666                                      const LocationContext *LC) {
667   // Are we never purging state values?
668   if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
669     return false;
670 
671   // Is this the beginning of a basic block?
672   if (Pred->getLocation().getAs<BlockEntrance>())
673     return true;
674 
675   // Is this on a non-expression?
676   if (!isa<Expr>(S))
677     return true;
678 
679   // Run before processing a call.
680   if (CallEvent::isCallStmt(S))
681     return true;
682 
683   // Is this an expression that is consumed by another expression?  If so,
684   // postpone cleaning out the state.
685   ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
686   return !PM.isConsumedExpr(cast<Expr>(S));
687 }
688 
689 void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
690                             const Stmt *ReferenceStmt,
691                             const LocationContext *LC,
692                             const Stmt *DiagnosticStmt,
693                             ProgramPoint::Kind K) {
694   assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
695           ReferenceStmt == nullptr || isa<ReturnStmt>(ReferenceStmt))
696           && "PostStmt is not generally supported by the SymbolReaper yet");
697   assert(LC && "Must pass the current (or expiring) LocationContext");
698 
699   if (!DiagnosticStmt) {
700     DiagnosticStmt = ReferenceStmt;
701     assert(DiagnosticStmt && "Required for clearing a LocationContext");
702   }
703 
704   NumRemoveDeadBindings++;
705   ProgramStateRef CleanedState = Pred->getState();
706 
707   // LC is the location context being destroyed, but SymbolReaper wants a
708   // location context that is still live. (If this is the top-level stack
709   // frame, this will be null.)
710   if (!ReferenceStmt) {
711     assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
712            "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
713     LC = LC->getParent();
714   }
715 
716   const StackFrameContext *SFC = LC ? LC->getStackFrame() : nullptr;
717   SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
718 
719   for (auto I : CleanedState->get<ObjectsUnderConstruction>()) {
720     if (SymbolRef Sym = I.second.getAsSymbol())
721       SymReaper.markLive(Sym);
722     if (const MemRegion *MR = I.second.getAsRegion())
723       SymReaper.markLive(MR);
724   }
725 
726   getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
727 
728   // Create a state in which dead bindings are removed from the environment
729   // and the store. TODO: The function should just return new env and store,
730   // not a new state.
731   CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
732 
733   // Process any special transfer function for dead symbols.
734   // A tag to track convenience transitions, which can be removed at cleanup.
735   static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node");
736   // Call checkers with the non-cleaned state so that they could query the
737   // values of the soon to be dead symbols.
738   ExplodedNodeSet CheckedSet;
739   getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
740                                                 DiagnosticStmt, *this, K);
741 
742   // For each node in CheckedSet, generate CleanedNodes that have the
743   // environment, the store, and the constraints cleaned up but have the
744   // user-supplied states as the predecessors.
745   StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
746   for (const auto I : CheckedSet) {
747     ProgramStateRef CheckerState = I->getState();
748 
749     // The constraint manager has not been cleaned up yet, so clean up now.
750     CheckerState =
751         getConstraintManager().removeDeadBindings(CheckerState, SymReaper);
752 
753     assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
754            "Checkers are not allowed to modify the Environment as a part of "
755            "checkDeadSymbols processing.");
756     assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
757            "Checkers are not allowed to modify the Store as a part of "
758            "checkDeadSymbols processing.");
759 
760     // Create a state based on CleanedState with CheckerState GDM and
761     // generate a transition to that state.
762     ProgramStateRef CleanedCheckerSt =
763         StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
764     Bldr.generateNode(DiagnosticStmt, I, CleanedCheckerSt, &cleanupTag, K);
765   }
766 }
767 
768 void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) {
769   // Reclaim any unnecessary nodes in the ExplodedGraph.
770   G.reclaimRecentlyAllocatedNodes();
771 
772   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
773                                 currStmt->getBeginLoc(),
774                                 "Error evaluating statement");
775 
776   // Remove dead bindings and symbols.
777   ExplodedNodeSet CleanedStates;
778   if (shouldRemoveDeadBindings(AMgr, currStmt, Pred,
779                                Pred->getLocationContext())) {
780     removeDead(Pred, CleanedStates, currStmt,
781                                     Pred->getLocationContext());
782   } else
783     CleanedStates.Add(Pred);
784 
785   // Visit the statement.
786   ExplodedNodeSet Dst;
787   for (const auto I : CleanedStates) {
788     ExplodedNodeSet DstI;
789     // Visit the statement.
790     Visit(currStmt, I, DstI);
791     Dst.insert(DstI);
792   }
793 
794   // Enqueue the new nodes onto the work list.
795   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
796 }
797 
798 void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) {
799   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
800                                 S->getBeginLoc(),
801                                 "Error evaluating end of the loop");
802   ExplodedNodeSet Dst;
803   Dst.Add(Pred);
804   NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
805   ProgramStateRef NewState = Pred->getState();
806 
807   if(AMgr.options.ShouldUnrollLoops)
808     NewState = processLoopEnd(S, NewState);
809 
810   LoopExit PP(S, Pred->getLocationContext());
811   Bldr.generateNode(PP, NewState, Pred);
812   // Enqueue the new nodes onto the work list.
813   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
814 }
815 
816 void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit,
817                                     ExplodedNode *Pred) {
818   const CXXCtorInitializer *BMI = CFGInit.getInitializer();
819   const Expr *Init = BMI->getInit()->IgnoreImplicit();
820   const LocationContext *LC = Pred->getLocationContext();
821 
822   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
823                                 BMI->getSourceLocation(),
824                                 "Error evaluating initializer");
825 
826   // We don't clean up dead bindings here.
827   const auto *stackFrame = cast<StackFrameContext>(Pred->getLocationContext());
828   const auto *decl = cast<CXXConstructorDecl>(stackFrame->getDecl());
829 
830   ProgramStateRef State = Pred->getState();
831   SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));
832 
833   ExplodedNodeSet Tmp;
834   SVal FieldLoc;
835 
836   // Evaluate the initializer, if necessary
837   if (BMI->isAnyMemberInitializer()) {
838     // Constructors build the object directly in the field,
839     // but non-objects must be copied in from the initializer.
840     if (getObjectUnderConstruction(State, BMI, LC)) {
841       // The field was directly constructed, so there is no need to bind.
842       // But we still need to stop tracking the object under construction.
843       State = finishObjectConstruction(State, BMI, LC);
844       NodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
845       PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr);
846       Bldr.generateNode(PS, State, Pred);
847     } else {
848       const ValueDecl *Field;
849       if (BMI->isIndirectMemberInitializer()) {
850         Field = BMI->getIndirectMember();
851         FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);
852       } else {
853         Field = BMI->getMember();
854         FieldLoc = State->getLValue(BMI->getMember(), thisVal);
855       }
856 
857       SVal InitVal;
858       if (Init->getType()->isArrayType()) {
859         // Handle arrays of trivial type. We can represent this with a
860         // primitive load/copy from the base array region.
861         const ArraySubscriptExpr *ASE;
862         while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))
863           Init = ASE->getBase()->IgnoreImplicit();
864 
865         SVal LValue = State->getSVal(Init, stackFrame);
866         if (!Field->getType()->isReferenceType())
867           if (Optional<Loc> LValueLoc = LValue.getAs<Loc>())
868             InitVal = State->getSVal(*LValueLoc);
869 
870         // If we fail to get the value for some reason, use a symbolic value.
871         if (InitVal.isUnknownOrUndef()) {
872           SValBuilder &SVB = getSValBuilder();
873           InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame,
874                                          Field->getType(),
875                                          currBldrCtx->blockCount());
876         }
877       } else {
878         InitVal = State->getSVal(BMI->getInit(), stackFrame);
879       }
880 
881       PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
882       evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);
883     }
884   } else {
885     assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
886     Tmp.insert(Pred);
887     // We already did all the work when visiting the CXXConstructExpr.
888   }
889 
890   // Construct PostInitializer nodes whether the state changed or not,
891   // so that the diagnostics don't get confused.
892   PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
893   ExplodedNodeSet Dst;
894   NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
895   for (const auto I : Tmp) {
896     ProgramStateRef State = I->getState();
897     Bldr.generateNode(PP, State, I);
898   }
899 
900   // Enqueue the new nodes onto the work list.
901   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
902 }
903 
904 void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
905                                      ExplodedNode *Pred) {
906   ExplodedNodeSet Dst;
907   switch (D.getKind()) {
908   case CFGElement::AutomaticObjectDtor:
909     ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);
910     break;
911   case CFGElement::BaseDtor:
912     ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst);
913     break;
914   case CFGElement::MemberDtor:
915     ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst);
916     break;
917   case CFGElement::TemporaryDtor:
918     ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst);
919     break;
920   case CFGElement::DeleteDtor:
921     ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst);
922     break;
923   default:
924     llvm_unreachable("Unexpected dtor kind.");
925   }
926 
927   // Enqueue the new nodes onto the work list.
928   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
929 }
930 
931 void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE,
932                                      ExplodedNode *Pred) {
933   ExplodedNodeSet Dst;
934   AnalysisManager &AMgr = getAnalysisManager();
935   AnalyzerOptions &Opts = AMgr.options;
936   // TODO: We're not evaluating allocators for all cases just yet as
937   // we're not handling the return value correctly, which causes false
938   // positives when the alpha.cplusplus.NewDeleteLeaks check is on.
939   if (Opts.MayInlineCXXAllocator)
940     VisitCXXNewAllocatorCall(NE, Pred, Dst);
941   else {
942     NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
943     const LocationContext *LCtx = Pred->getLocationContext();
944     PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx);
945     Bldr.generateNode(PP, Pred->getState(), Pred);
946   }
947   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
948 }
949 
950 void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
951                                          ExplodedNode *Pred,
952                                          ExplodedNodeSet &Dst) {
953   const VarDecl *varDecl = Dtor.getVarDecl();
954   QualType varType = varDecl->getType();
955 
956   ProgramStateRef state = Pred->getState();
957   SVal dest = state->getLValue(varDecl, Pred->getLocationContext());
958   const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();
959 
960   if (varType->isReferenceType()) {
961     const MemRegion *ValueRegion = state->getSVal(Region).getAsRegion();
962     if (!ValueRegion) {
963       // FIXME: This should not happen. The language guarantees a presence
964       // of a valid initializer here, so the reference shall not be undefined.
965       // It seems that we're calling destructors over variables that
966       // were not initialized yet.
967       return;
968     }
969     Region = ValueRegion->getBaseRegion();
970     varType = cast<TypedValueRegion>(Region)->getValueType();
971   }
972 
973   // FIXME: We need to run the same destructor on every element of the array.
974   // This workaround will just run the first destructor (which will still
975   // invalidate the entire array).
976   EvalCallOptions CallOpts;
977   Region = makeZeroElementRegion(state, loc::MemRegionVal(Region), varType,
978                                  CallOpts.IsArrayCtorOrDtor).getAsRegion();
979 
980   VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(),
981                      /*IsBase=*/false, Pred, Dst, CallOpts);
982 }
983 
984 void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor,
985                                    ExplodedNode *Pred,
986                                    ExplodedNodeSet &Dst) {
987   ProgramStateRef State = Pred->getState();
988   const LocationContext *LCtx = Pred->getLocationContext();
989   const CXXDeleteExpr *DE = Dtor.getDeleteExpr();
990   const Stmt *Arg = DE->getArgument();
991   QualType DTy = DE->getDestroyedType();
992   SVal ArgVal = State->getSVal(Arg, LCtx);
993 
994   // If the argument to delete is known to be a null value,
995   // don't run destructor.
996   if (State->isNull(ArgVal).isConstrainedTrue()) {
997     QualType BTy = getContext().getBaseElementType(DTy);
998     const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl();
999     const CXXDestructorDecl *Dtor = RD->getDestructor();
1000 
1001     PostImplicitCall PP(Dtor, DE->getBeginLoc(), LCtx);
1002     NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1003     Bldr.generateNode(PP, Pred->getState(), Pred);
1004     return;
1005   }
1006 
1007   EvalCallOptions CallOpts;
1008   const MemRegion *ArgR = ArgVal.getAsRegion();
1009   if (DE->isArrayForm()) {
1010     // FIXME: We need to run the same destructor on every element of the array.
1011     // This workaround will just run the first destructor (which will still
1012     // invalidate the entire array).
1013     CallOpts.IsArrayCtorOrDtor = true;
1014     // Yes, it may even be a multi-dimensional array.
1015     while (const auto *AT = getContext().getAsArrayType(DTy))
1016       DTy = AT->getElementType();
1017     if (ArgR)
1018       ArgR = getStoreManager().GetElementZeroRegion(cast<SubRegion>(ArgR), DTy);
1019   }
1020 
1021   VisitCXXDestructor(DTy, ArgR, DE, /*IsBase=*/false, Pred, Dst, CallOpts);
1022 }
1023 
1024 void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
1025                                  ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1026   const LocationContext *LCtx = Pred->getLocationContext();
1027 
1028   const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
1029   Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,
1030                                             LCtx->getStackFrame());
1031   SVal ThisVal = Pred->getState()->getSVal(ThisPtr);
1032 
1033   // Create the base object region.
1034   const CXXBaseSpecifier *Base = D.getBaseSpecifier();
1035   QualType BaseTy = Base->getType();
1036   SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy,
1037                                                      Base->isVirtual());
1038 
1039   EvalCallOptions CallOpts;
1040   VisitCXXDestructor(BaseTy, BaseVal.getAsRegion(), CurDtor->getBody(),
1041                      /*IsBase=*/true, Pred, Dst, CallOpts);
1042 }
1043 
1044 void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
1045                                    ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1046   const FieldDecl *Member = D.getFieldDecl();
1047   QualType T = Member->getType();
1048   ProgramStateRef State = Pred->getState();
1049   const LocationContext *LCtx = Pred->getLocationContext();
1050 
1051   const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
1052   Loc ThisStorageLoc =
1053       getSValBuilder().getCXXThis(CurDtor, LCtx->getStackFrame());
1054   Loc ThisLoc = State->getSVal(ThisStorageLoc).castAs<Loc>();
1055   SVal FieldVal = State->getLValue(Member, ThisLoc);
1056 
1057   // FIXME: We need to run the same destructor on every element of the array.
1058   // This workaround will just run the first destructor (which will still
1059   // invalidate the entire array).
1060   EvalCallOptions CallOpts;
1061   FieldVal = makeZeroElementRegion(State, FieldVal, T,
1062                                    CallOpts.IsArrayCtorOrDtor);
1063 
1064   VisitCXXDestructor(T, FieldVal.getAsRegion(), CurDtor->getBody(),
1065                      /*IsBase=*/false, Pred, Dst, CallOpts);
1066 }
1067 
1068 void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
1069                                       ExplodedNode *Pred,
1070                                       ExplodedNodeSet &Dst) {
1071   const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr();
1072   ProgramStateRef State = Pred->getState();
1073   const LocationContext *LC = Pred->getLocationContext();
1074   const MemRegion *MR = nullptr;
1075 
1076   if (Optional<SVal> V =
1077           getObjectUnderConstruction(State, D.getBindTemporaryExpr(),
1078                                      Pred->getLocationContext())) {
1079     // FIXME: Currently we insert temporary destructors for default parameters,
1080     // but we don't insert the constructors, so the entry in
1081     // ObjectsUnderConstruction may be missing.
1082     State = finishObjectConstruction(State, D.getBindTemporaryExpr(),
1083                                      Pred->getLocationContext());
1084     MR = V->getAsRegion();
1085   }
1086 
1087   // If copy elision has occurred, and the constructor corresponding to the
1088   // destructor was elided, we need to skip the destructor as well.
1089   if (isDestructorElided(State, BTE, LC)) {
1090     State = cleanupElidedDestructor(State, BTE, LC);
1091     NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1092     PostImplicitCall PP(D.getDestructorDecl(getContext()),
1093                         D.getBindTemporaryExpr()->getBeginLoc(),
1094                         Pred->getLocationContext());
1095     Bldr.generateNode(PP, State, Pred);
1096     return;
1097   }
1098 
1099   ExplodedNodeSet CleanDtorState;
1100   StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx);
1101   StmtBldr.generateNode(D.getBindTemporaryExpr(), Pred, State);
1102 
1103   QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType();
1104   // FIXME: Currently CleanDtorState can be empty here due to temporaries being
1105   // bound to default parameters.
1106   assert(CleanDtorState.size() <= 1);
1107   ExplodedNode *CleanPred =
1108       CleanDtorState.empty() ? Pred : *CleanDtorState.begin();
1109 
1110   EvalCallOptions CallOpts;
1111   CallOpts.IsTemporaryCtorOrDtor = true;
1112   if (!MR) {
1113     // If we have no MR, we still need to unwrap the array to avoid destroying
1114     // the whole array at once. Regardless, we'd eventually need to model array
1115     // destructors properly, element-by-element.
1116     while (const ArrayType *AT = getContext().getAsArrayType(T)) {
1117       T = AT->getElementType();
1118       CallOpts.IsArrayCtorOrDtor = true;
1119     }
1120   } else {
1121     // We'd eventually need to makeZeroElementRegion() trick here,
1122     // but for now we don't have the respective construction contexts,
1123     // so MR would always be null in this case. Do nothing for now.
1124   }
1125   VisitCXXDestructor(T, MR, D.getBindTemporaryExpr(),
1126                      /*IsBase=*/false, CleanPred, Dst, CallOpts);
1127 }
1128 
1129 void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
1130                                                NodeBuilderContext &BldCtx,
1131                                                ExplodedNode *Pred,
1132                                                ExplodedNodeSet &Dst,
1133                                                const CFGBlock *DstT,
1134                                                const CFGBlock *DstF) {
1135   BranchNodeBuilder TempDtorBuilder(Pred, Dst, BldCtx, DstT, DstF);
1136   ProgramStateRef State = Pred->getState();
1137   const LocationContext *LC = Pred->getLocationContext();
1138   if (getObjectUnderConstruction(State, BTE, LC)) {
1139     TempDtorBuilder.markInfeasible(false);
1140     TempDtorBuilder.generateNode(State, true, Pred);
1141   } else {
1142     TempDtorBuilder.markInfeasible(true);
1143     TempDtorBuilder.generateNode(State, false, Pred);
1144   }
1145 }
1146 
1147 void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,
1148                                            ExplodedNodeSet &PreVisit,
1149                                            ExplodedNodeSet &Dst) {
1150   // This is a fallback solution in case we didn't have a construction
1151   // context when we were constructing the temporary. Otherwise the map should
1152   // have been populated there.
1153   if (!getAnalysisManager().options.ShouldIncludeTemporaryDtorsInCFG) {
1154     // In case we don't have temporary destructors in the CFG, do not mark
1155     // the initialization - we would otherwise never clean it up.
1156     Dst = PreVisit;
1157     return;
1158   }
1159   StmtNodeBuilder StmtBldr(PreVisit, Dst, *currBldrCtx);
1160   for (ExplodedNode *Node : PreVisit) {
1161     ProgramStateRef State = Node->getState();
1162     const LocationContext *LC = Node->getLocationContext();
1163     if (!getObjectUnderConstruction(State, BTE, LC)) {
1164       // FIXME: Currently the state might also already contain the marker due to
1165       // incorrect handling of temporaries bound to default parameters; for
1166       // those, we currently skip the CXXBindTemporaryExpr but rely on adding
1167       // temporary destructor nodes.
1168       State = addObjectUnderConstruction(State, BTE, LC, UnknownVal());
1169     }
1170     StmtBldr.generateNode(BTE, Node, State);
1171   }
1172 }
1173 
1174 ProgramStateRef ExprEngine::escapeValue(ProgramStateRef State, SVal V,
1175                                         PointerEscapeKind K) const {
1176   class CollectReachableSymbolsCallback final : public SymbolVisitor {
1177     InvalidatedSymbols Symbols;
1178 
1179   public:
1180     explicit CollectReachableSymbolsCallback(ProgramStateRef) {}
1181 
1182     const InvalidatedSymbols &getSymbols() const { return Symbols; }
1183 
1184     bool VisitSymbol(SymbolRef Sym) override {
1185       Symbols.insert(Sym);
1186       return true;
1187     }
1188   };
1189 
1190   const CollectReachableSymbolsCallback &Scanner =
1191       State->scanReachableSymbols<CollectReachableSymbolsCallback>(V);
1192   return getCheckerManager().runCheckersForPointerEscape(
1193       State, Scanner.getSymbols(), /*CallEvent*/ nullptr, K, nullptr);
1194 }
1195 
1196 void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
1197                        ExplodedNodeSet &DstTop) {
1198   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1199                                 S->getBeginLoc(), "Error evaluating statement");
1200   ExplodedNodeSet Dst;
1201   StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
1202 
1203   assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
1204 
1205   switch (S->getStmtClass()) {
1206     // C++, OpenMP and ARC stuff we don't support yet.
1207     case Expr::ObjCIndirectCopyRestoreExprClass:
1208     case Stmt::CXXDependentScopeMemberExprClass:
1209     case Stmt::CXXInheritedCtorInitExprClass:
1210     case Stmt::CXXTryStmtClass:
1211     case Stmt::CXXTypeidExprClass:
1212     case Stmt::CXXUuidofExprClass:
1213     case Stmt::CXXFoldExprClass:
1214     case Stmt::MSPropertyRefExprClass:
1215     case Stmt::MSPropertySubscriptExprClass:
1216     case Stmt::CXXUnresolvedConstructExprClass:
1217     case Stmt::DependentScopeDeclRefExprClass:
1218     case Stmt::ArrayTypeTraitExprClass:
1219     case Stmt::ExpressionTraitExprClass:
1220     case Stmt::UnresolvedLookupExprClass:
1221     case Stmt::UnresolvedMemberExprClass:
1222     case Stmt::TypoExprClass:
1223     case Stmt::CXXNoexceptExprClass:
1224     case Stmt::PackExpansionExprClass:
1225     case Stmt::SubstNonTypeTemplateParmPackExprClass:
1226     case Stmt::FunctionParmPackExprClass:
1227     case Stmt::CoroutineBodyStmtClass:
1228     case Stmt::CoawaitExprClass:
1229     case Stmt::DependentCoawaitExprClass:
1230     case Stmt::CoreturnStmtClass:
1231     case Stmt::CoyieldExprClass:
1232     case Stmt::SEHTryStmtClass:
1233     case Stmt::SEHExceptStmtClass:
1234     case Stmt::SEHLeaveStmtClass:
1235     case Stmt::SEHFinallyStmtClass:
1236     case Stmt::OMPParallelDirectiveClass:
1237     case Stmt::OMPSimdDirectiveClass:
1238     case Stmt::OMPForDirectiveClass:
1239     case Stmt::OMPForSimdDirectiveClass:
1240     case Stmt::OMPSectionsDirectiveClass:
1241     case Stmt::OMPSectionDirectiveClass:
1242     case Stmt::OMPSingleDirectiveClass:
1243     case Stmt::OMPMasterDirectiveClass:
1244     case Stmt::OMPCriticalDirectiveClass:
1245     case Stmt::OMPParallelForDirectiveClass:
1246     case Stmt::OMPParallelForSimdDirectiveClass:
1247     case Stmt::OMPParallelSectionsDirectiveClass:
1248     case Stmt::OMPTaskDirectiveClass:
1249     case Stmt::OMPTaskyieldDirectiveClass:
1250     case Stmt::OMPBarrierDirectiveClass:
1251     case Stmt::OMPTaskwaitDirectiveClass:
1252     case Stmt::OMPTaskgroupDirectiveClass:
1253     case Stmt::OMPFlushDirectiveClass:
1254     case Stmt::OMPOrderedDirectiveClass:
1255     case Stmt::OMPAtomicDirectiveClass:
1256     case Stmt::OMPTargetDirectiveClass:
1257     case Stmt::OMPTargetDataDirectiveClass:
1258     case Stmt::OMPTargetEnterDataDirectiveClass:
1259     case Stmt::OMPTargetExitDataDirectiveClass:
1260     case Stmt::OMPTargetParallelDirectiveClass:
1261     case Stmt::OMPTargetParallelForDirectiveClass:
1262     case Stmt::OMPTargetUpdateDirectiveClass:
1263     case Stmt::OMPTeamsDirectiveClass:
1264     case Stmt::OMPCancellationPointDirectiveClass:
1265     case Stmt::OMPCancelDirectiveClass:
1266     case Stmt::OMPTaskLoopDirectiveClass:
1267     case Stmt::OMPTaskLoopSimdDirectiveClass:
1268     case Stmt::OMPMasterTaskLoopDirectiveClass:
1269     case Stmt::OMPMasterTaskLoopSimdDirectiveClass:
1270     case Stmt::OMPParallelMasterTaskLoopDirectiveClass:
1271     case Stmt::OMPDistributeDirectiveClass:
1272     case Stmt::OMPDistributeParallelForDirectiveClass:
1273     case Stmt::OMPDistributeParallelForSimdDirectiveClass:
1274     case Stmt::OMPDistributeSimdDirectiveClass:
1275     case Stmt::OMPTargetParallelForSimdDirectiveClass:
1276     case Stmt::OMPTargetSimdDirectiveClass:
1277     case Stmt::OMPTeamsDistributeDirectiveClass:
1278     case Stmt::OMPTeamsDistributeSimdDirectiveClass:
1279     case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:
1280     case Stmt::OMPTeamsDistributeParallelForDirectiveClass:
1281     case Stmt::OMPTargetTeamsDirectiveClass:
1282     case Stmt::OMPTargetTeamsDistributeDirectiveClass:
1283     case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:
1284     case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:
1285     case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:
1286     case Stmt::CapturedStmtClass: {
1287       const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
1288       Engine.addAbortedBlock(node, currBldrCtx->getBlock());
1289       break;
1290     }
1291 
1292     case Stmt::ParenExprClass:
1293       llvm_unreachable("ParenExprs already handled.");
1294     case Stmt::GenericSelectionExprClass:
1295       llvm_unreachable("GenericSelectionExprs already handled.");
1296     // Cases that should never be evaluated simply because they shouldn't
1297     // appear in the CFG.
1298     case Stmt::BreakStmtClass:
1299     case Stmt::CaseStmtClass:
1300     case Stmt::CompoundStmtClass:
1301     case Stmt::ContinueStmtClass:
1302     case Stmt::CXXForRangeStmtClass:
1303     case Stmt::DefaultStmtClass:
1304     case Stmt::DoStmtClass:
1305     case Stmt::ForStmtClass:
1306     case Stmt::GotoStmtClass:
1307     case Stmt::IfStmtClass:
1308     case Stmt::IndirectGotoStmtClass:
1309     case Stmt::LabelStmtClass:
1310     case Stmt::NoStmtClass:
1311     case Stmt::NullStmtClass:
1312     case Stmt::SwitchStmtClass:
1313     case Stmt::WhileStmtClass:
1314     case Expr::MSDependentExistsStmtClass:
1315       llvm_unreachable("Stmt should not be in analyzer evaluation loop");
1316 
1317     case Stmt::ObjCSubscriptRefExprClass:
1318     case Stmt::ObjCPropertyRefExprClass:
1319       llvm_unreachable("These are handled by PseudoObjectExpr");
1320 
1321     case Stmt::GNUNullExprClass: {
1322       // GNU __null is a pointer-width integer, not an actual pointer.
1323       ProgramStateRef state = Pred->getState();
1324       state = state->BindExpr(S, Pred->getLocationContext(),
1325                               svalBuilder.makeIntValWithPtrWidth(0, false));
1326       Bldr.generateNode(S, Pred, state);
1327       break;
1328     }
1329 
1330     case Stmt::ObjCAtSynchronizedStmtClass:
1331       Bldr.takeNodes(Pred);
1332       VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
1333       Bldr.addNodes(Dst);
1334       break;
1335 
1336     case Expr::ConstantExprClass:
1337     case Stmt::ExprWithCleanupsClass:
1338       // Handled due to fully linearised CFG.
1339       break;
1340 
1341     case Stmt::CXXBindTemporaryExprClass: {
1342       Bldr.takeNodes(Pred);
1343       ExplodedNodeSet PreVisit;
1344       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1345       ExplodedNodeSet Next;
1346       VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), PreVisit, Next);
1347       getCheckerManager().runCheckersForPostStmt(Dst, Next, S, *this);
1348       Bldr.addNodes(Dst);
1349       break;
1350     }
1351 
1352     // Cases not handled yet; but will handle some day.
1353     case Stmt::DesignatedInitExprClass:
1354     case Stmt::DesignatedInitUpdateExprClass:
1355     case Stmt::ArrayInitLoopExprClass:
1356     case Stmt::ArrayInitIndexExprClass:
1357     case Stmt::ExtVectorElementExprClass:
1358     case Stmt::ImaginaryLiteralClass:
1359     case Stmt::ObjCAtCatchStmtClass:
1360     case Stmt::ObjCAtFinallyStmtClass:
1361     case Stmt::ObjCAtTryStmtClass:
1362     case Stmt::ObjCAutoreleasePoolStmtClass:
1363     case Stmt::ObjCEncodeExprClass:
1364     case Stmt::ObjCIsaExprClass:
1365     case Stmt::ObjCProtocolExprClass:
1366     case Stmt::ObjCSelectorExprClass:
1367     case Stmt::ParenListExprClass:
1368     case Stmt::ShuffleVectorExprClass:
1369     case Stmt::ConvertVectorExprClass:
1370     case Stmt::VAArgExprClass:
1371     case Stmt::CUDAKernelCallExprClass:
1372     case Stmt::OpaqueValueExprClass:
1373     case Stmt::AsTypeExprClass:
1374     case Stmt::ConceptSpecializationExprClass:
1375     case Stmt::CXXRewrittenBinaryOperatorClass:
1376       // Fall through.
1377 
1378     // Cases we intentionally don't evaluate, since they don't need
1379     // to be explicitly evaluated.
1380     case Stmt::PredefinedExprClass:
1381     case Stmt::AddrLabelExprClass:
1382     case Stmt::AttributedStmtClass:
1383     case Stmt::IntegerLiteralClass:
1384     case Stmt::FixedPointLiteralClass:
1385     case Stmt::CharacterLiteralClass:
1386     case Stmt::ImplicitValueInitExprClass:
1387     case Stmt::CXXScalarValueInitExprClass:
1388     case Stmt::CXXBoolLiteralExprClass:
1389     case Stmt::ObjCBoolLiteralExprClass:
1390     case Stmt::ObjCAvailabilityCheckExprClass:
1391     case Stmt::FloatingLiteralClass:
1392     case Stmt::NoInitExprClass:
1393     case Stmt::SizeOfPackExprClass:
1394     case Stmt::StringLiteralClass:
1395     case Stmt::SourceLocExprClass:
1396     case Stmt::ObjCStringLiteralClass:
1397     case Stmt::CXXPseudoDestructorExprClass:
1398     case Stmt::SubstNonTypeTemplateParmExprClass:
1399     case Stmt::CXXNullPtrLiteralExprClass:
1400     case Stmt::OMPArraySectionExprClass:
1401     case Stmt::TypeTraitExprClass: {
1402       Bldr.takeNodes(Pred);
1403       ExplodedNodeSet preVisit;
1404       getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
1405       getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
1406       Bldr.addNodes(Dst);
1407       break;
1408     }
1409 
1410     case Stmt::CXXDefaultArgExprClass:
1411     case Stmt::CXXDefaultInitExprClass: {
1412       Bldr.takeNodes(Pred);
1413       ExplodedNodeSet PreVisit;
1414       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1415 
1416       ExplodedNodeSet Tmp;
1417       StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
1418 
1419       const Expr *ArgE;
1420       if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S))
1421         ArgE = DefE->getExpr();
1422       else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S))
1423         ArgE = DefE->getExpr();
1424       else
1425         llvm_unreachable("unknown constant wrapper kind");
1426 
1427       bool IsTemporary = false;
1428       if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) {
1429         ArgE = MTE->GetTemporaryExpr();
1430         IsTemporary = true;
1431       }
1432 
1433       Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE);
1434       if (!ConstantVal)
1435         ConstantVal = UnknownVal();
1436 
1437       const LocationContext *LCtx = Pred->getLocationContext();
1438       for (const auto I : PreVisit) {
1439         ProgramStateRef State = I->getState();
1440         State = State->BindExpr(S, LCtx, *ConstantVal);
1441         if (IsTemporary)
1442           State = createTemporaryRegionIfNeeded(State, LCtx,
1443                                                 cast<Expr>(S),
1444                                                 cast<Expr>(S));
1445         Bldr2.generateNode(S, I, State);
1446       }
1447 
1448       getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
1449       Bldr.addNodes(Dst);
1450       break;
1451     }
1452 
1453     // Cases we evaluate as opaque expressions, conjuring a symbol.
1454     case Stmt::CXXStdInitializerListExprClass:
1455     case Expr::ObjCArrayLiteralClass:
1456     case Expr::ObjCDictionaryLiteralClass:
1457     case Expr::ObjCBoxedExprClass: {
1458       Bldr.takeNodes(Pred);
1459 
1460       ExplodedNodeSet preVisit;
1461       getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
1462 
1463       ExplodedNodeSet Tmp;
1464       StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
1465 
1466       const auto *Ex = cast<Expr>(S);
1467       QualType resultType = Ex->getType();
1468 
1469       for (const auto N : preVisit) {
1470         const LocationContext *LCtx = N->getLocationContext();
1471         SVal result = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx,
1472                                                    resultType,
1473                                                    currBldrCtx->blockCount());
1474         ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result);
1475 
1476         // Escape pointers passed into the list, unless it's an ObjC boxed
1477         // expression which is not a boxable C structure.
1478         if (!(isa<ObjCBoxedExpr>(Ex) &&
1479               !cast<ObjCBoxedExpr>(Ex)->getSubExpr()
1480                                       ->getType()->isRecordType()))
1481           for (auto Child : Ex->children()) {
1482             assert(Child);
1483             SVal Val = State->getSVal(Child, LCtx);
1484             State = escapeValue(State, Val, PSK_EscapeOther);
1485           }
1486 
1487         Bldr2.generateNode(S, N, State);
1488       }
1489 
1490       getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
1491       Bldr.addNodes(Dst);
1492       break;
1493     }
1494 
1495     case Stmt::ArraySubscriptExprClass:
1496       Bldr.takeNodes(Pred);
1497       VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
1498       Bldr.addNodes(Dst);
1499       break;
1500 
1501     case Stmt::GCCAsmStmtClass:
1502       Bldr.takeNodes(Pred);
1503       VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
1504       Bldr.addNodes(Dst);
1505       break;
1506 
1507     case Stmt::MSAsmStmtClass:
1508       Bldr.takeNodes(Pred);
1509       VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
1510       Bldr.addNodes(Dst);
1511       break;
1512 
1513     case Stmt::BlockExprClass:
1514       Bldr.takeNodes(Pred);
1515       VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
1516       Bldr.addNodes(Dst);
1517       break;
1518 
1519     case Stmt::LambdaExprClass:
1520       if (AMgr.options.ShouldInlineLambdas) {
1521         Bldr.takeNodes(Pred);
1522         VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst);
1523         Bldr.addNodes(Dst);
1524       } else {
1525         const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
1526         Engine.addAbortedBlock(node, currBldrCtx->getBlock());
1527       }
1528       break;
1529 
1530     case Stmt::BinaryOperatorClass: {
1531       const auto *B = cast<BinaryOperator>(S);
1532       if (B->isLogicalOp()) {
1533         Bldr.takeNodes(Pred);
1534         VisitLogicalExpr(B, Pred, Dst);
1535         Bldr.addNodes(Dst);
1536         break;
1537       }
1538       else if (B->getOpcode() == BO_Comma) {
1539         ProgramStateRef state = Pred->getState();
1540         Bldr.generateNode(B, Pred,
1541                           state->BindExpr(B, Pred->getLocationContext(),
1542                                           state->getSVal(B->getRHS(),
1543                                                   Pred->getLocationContext())));
1544         break;
1545       }
1546 
1547       Bldr.takeNodes(Pred);
1548 
1549       if (AMgr.options.ShouldEagerlyAssume &&
1550           (B->isRelationalOp() || B->isEqualityOp())) {
1551         ExplodedNodeSet Tmp;
1552         VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
1553         evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
1554       }
1555       else
1556         VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
1557 
1558       Bldr.addNodes(Dst);
1559       break;
1560     }
1561 
1562     case Stmt::CXXOperatorCallExprClass: {
1563       const auto *OCE = cast<CXXOperatorCallExpr>(S);
1564 
1565       // For instance method operators, make sure the 'this' argument has a
1566       // valid region.
1567       const Decl *Callee = OCE->getCalleeDecl();
1568       if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
1569         if (MD->isInstance()) {
1570           ProgramStateRef State = Pred->getState();
1571           const LocationContext *LCtx = Pred->getLocationContext();
1572           ProgramStateRef NewState =
1573             createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
1574           if (NewState != State) {
1575             Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr,
1576                                      ProgramPoint::PreStmtKind);
1577             // Did we cache out?
1578             if (!Pred)
1579               break;
1580           }
1581         }
1582       }
1583       // FALLTHROUGH
1584       LLVM_FALLTHROUGH;
1585     }
1586 
1587     case Stmt::CallExprClass:
1588     case Stmt::CXXMemberCallExprClass:
1589     case Stmt::UserDefinedLiteralClass:
1590       Bldr.takeNodes(Pred);
1591       VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
1592       Bldr.addNodes(Dst);
1593       break;
1594 
1595     case Stmt::CXXCatchStmtClass:
1596       Bldr.takeNodes(Pred);
1597       VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
1598       Bldr.addNodes(Dst);
1599       break;
1600 
1601     case Stmt::CXXTemporaryObjectExprClass:
1602     case Stmt::CXXConstructExprClass:
1603       Bldr.takeNodes(Pred);
1604       VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
1605       Bldr.addNodes(Dst);
1606       break;
1607 
1608     case Stmt::CXXNewExprClass: {
1609       Bldr.takeNodes(Pred);
1610 
1611       ExplodedNodeSet PreVisit;
1612       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1613 
1614       ExplodedNodeSet PostVisit;
1615       for (const auto i : PreVisit)
1616         VisitCXXNewExpr(cast<CXXNewExpr>(S), i, PostVisit);
1617 
1618       getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
1619       Bldr.addNodes(Dst);
1620       break;
1621     }
1622 
1623     case Stmt::CXXDeleteExprClass: {
1624       Bldr.takeNodes(Pred);
1625       ExplodedNodeSet PreVisit;
1626       const auto *CDE = cast<CXXDeleteExpr>(S);
1627       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1628 
1629       for (const auto i : PreVisit)
1630         VisitCXXDeleteExpr(CDE, i, Dst);
1631 
1632       Bldr.addNodes(Dst);
1633       break;
1634     }
1635       // FIXME: ChooseExpr is really a constant.  We need to fix
1636       //        the CFG do not model them as explicit control-flow.
1637 
1638     case Stmt::ChooseExprClass: { // __builtin_choose_expr
1639       Bldr.takeNodes(Pred);
1640       const auto *C = cast<ChooseExpr>(S);
1641       VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
1642       Bldr.addNodes(Dst);
1643       break;
1644     }
1645 
1646     case Stmt::CompoundAssignOperatorClass:
1647       Bldr.takeNodes(Pred);
1648       VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
1649       Bldr.addNodes(Dst);
1650       break;
1651 
1652     case Stmt::CompoundLiteralExprClass:
1653       Bldr.takeNodes(Pred);
1654       VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
1655       Bldr.addNodes(Dst);
1656       break;
1657 
1658     case Stmt::BinaryConditionalOperatorClass:
1659     case Stmt::ConditionalOperatorClass: { // '?' operator
1660       Bldr.takeNodes(Pred);
1661       const auto *C = cast<AbstractConditionalOperator>(S);
1662       VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
1663       Bldr.addNodes(Dst);
1664       break;
1665     }
1666 
1667     case Stmt::CXXThisExprClass:
1668       Bldr.takeNodes(Pred);
1669       VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
1670       Bldr.addNodes(Dst);
1671       break;
1672 
1673     case Stmt::DeclRefExprClass: {
1674       Bldr.takeNodes(Pred);
1675       const auto *DE = cast<DeclRefExpr>(S);
1676       VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
1677       Bldr.addNodes(Dst);
1678       break;
1679     }
1680 
1681     case Stmt::DeclStmtClass:
1682       Bldr.takeNodes(Pred);
1683       VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
1684       Bldr.addNodes(Dst);
1685       break;
1686 
1687     case Stmt::ImplicitCastExprClass:
1688     case Stmt::CStyleCastExprClass:
1689     case Stmt::CXXStaticCastExprClass:
1690     case Stmt::CXXDynamicCastExprClass:
1691     case Stmt::CXXReinterpretCastExprClass:
1692     case Stmt::CXXConstCastExprClass:
1693     case Stmt::CXXFunctionalCastExprClass:
1694     case Stmt::BuiltinBitCastExprClass:
1695     case Stmt::ObjCBridgedCastExprClass: {
1696       Bldr.takeNodes(Pred);
1697       const auto *C = cast<CastExpr>(S);
1698       ExplodedNodeSet dstExpr;
1699       VisitCast(C, C->getSubExpr(), Pred, dstExpr);
1700 
1701       // Handle the postvisit checks.
1702       getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
1703       Bldr.addNodes(Dst);
1704       break;
1705     }
1706 
1707     case Expr::MaterializeTemporaryExprClass: {
1708       Bldr.takeNodes(Pred);
1709       const auto *MTE = cast<MaterializeTemporaryExpr>(S);
1710       ExplodedNodeSet dstPrevisit;
1711       getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);
1712       ExplodedNodeSet dstExpr;
1713       for (const auto i : dstPrevisit)
1714         CreateCXXTemporaryObject(MTE, i, dstExpr);
1715       getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);
1716       Bldr.addNodes(Dst);
1717       break;
1718     }
1719 
1720     case Stmt::InitListExprClass:
1721       Bldr.takeNodes(Pred);
1722       VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
1723       Bldr.addNodes(Dst);
1724       break;
1725 
1726     case Stmt::MemberExprClass:
1727       Bldr.takeNodes(Pred);
1728       VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
1729       Bldr.addNodes(Dst);
1730       break;
1731 
1732     case Stmt::AtomicExprClass:
1733       Bldr.takeNodes(Pred);
1734       VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst);
1735       Bldr.addNodes(Dst);
1736       break;
1737 
1738     case Stmt::ObjCIvarRefExprClass:
1739       Bldr.takeNodes(Pred);
1740       VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
1741       Bldr.addNodes(Dst);
1742       break;
1743 
1744     case Stmt::ObjCForCollectionStmtClass:
1745       Bldr.takeNodes(Pred);
1746       VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
1747       Bldr.addNodes(Dst);
1748       break;
1749 
1750     case Stmt::ObjCMessageExprClass:
1751       Bldr.takeNodes(Pred);
1752       VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
1753       Bldr.addNodes(Dst);
1754       break;
1755 
1756     case Stmt::ObjCAtThrowStmtClass:
1757     case Stmt::CXXThrowExprClass:
1758       // FIXME: This is not complete.  We basically treat @throw as
1759       // an abort.
1760       Bldr.generateSink(S, Pred, Pred->getState());
1761       break;
1762 
1763     case Stmt::ReturnStmtClass:
1764       Bldr.takeNodes(Pred);
1765       VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
1766       Bldr.addNodes(Dst);
1767       break;
1768 
1769     case Stmt::OffsetOfExprClass: {
1770       Bldr.takeNodes(Pred);
1771       ExplodedNodeSet PreVisit;
1772       getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1773 
1774       ExplodedNodeSet PostVisit;
1775       for (const auto Node : PreVisit)
1776         VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Node, PostVisit);
1777 
1778       getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
1779       Bldr.addNodes(Dst);
1780       break;
1781     }
1782 
1783     case Stmt::UnaryExprOrTypeTraitExprClass:
1784       Bldr.takeNodes(Pred);
1785       VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
1786                                     Pred, Dst);
1787       Bldr.addNodes(Dst);
1788       break;
1789 
1790     case Stmt::StmtExprClass: {
1791       const auto *SE = cast<StmtExpr>(S);
1792 
1793       if (SE->getSubStmt()->body_empty()) {
1794         // Empty statement expression.
1795         assert(SE->getType() == getContext().VoidTy
1796                && "Empty statement expression must have void type.");
1797         break;
1798       }
1799 
1800       if (const auto *LastExpr =
1801               dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1802         ProgramStateRef state = Pred->getState();
1803         Bldr.generateNode(SE, Pred,
1804                           state->BindExpr(SE, Pred->getLocationContext(),
1805                                           state->getSVal(LastExpr,
1806                                                   Pred->getLocationContext())));
1807       }
1808       break;
1809     }
1810 
1811     case Stmt::UnaryOperatorClass: {
1812       Bldr.takeNodes(Pred);
1813       const auto *U = cast<UnaryOperator>(S);
1814       if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) {
1815         ExplodedNodeSet Tmp;
1816         VisitUnaryOperator(U, Pred, Tmp);
1817         evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
1818       }
1819       else
1820         VisitUnaryOperator(U, Pred, Dst);
1821       Bldr.addNodes(Dst);
1822       break;
1823     }
1824 
1825     case Stmt::PseudoObjectExprClass: {
1826       Bldr.takeNodes(Pred);
1827       ProgramStateRef state = Pred->getState();
1828       const auto *PE = cast<PseudoObjectExpr>(S);
1829       if (const Expr *Result = PE->getResultExpr()) {
1830         SVal V = state->getSVal(Result, Pred->getLocationContext());
1831         Bldr.generateNode(S, Pred,
1832                           state->BindExpr(S, Pred->getLocationContext(), V));
1833       }
1834       else
1835         Bldr.generateNode(S, Pred,
1836                           state->BindExpr(S, Pred->getLocationContext(),
1837                                                    UnknownVal()));
1838 
1839       Bldr.addNodes(Dst);
1840       break;
1841     }
1842   }
1843 }
1844 
1845 bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
1846                                        const LocationContext *CalleeLC) {
1847   const StackFrameContext *CalleeSF = CalleeLC->getStackFrame();
1848   const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame();
1849   assert(CalleeSF && CallerSF);
1850   ExplodedNode *BeforeProcessingCall = nullptr;
1851   const Stmt *CE = CalleeSF->getCallSite();
1852 
1853   // Find the first node before we started processing the call expression.
1854   while (N) {
1855     ProgramPoint L = N->getLocation();
1856     BeforeProcessingCall = N;
1857     N = N->pred_empty() ? nullptr : *(N->pred_begin());
1858 
1859     // Skip the nodes corresponding to the inlined code.
1860     if (L.getStackFrame() != CallerSF)
1861       continue;
1862     // We reached the caller. Find the node right before we started
1863     // processing the call.
1864     if (L.isPurgeKind())
1865       continue;
1866     if (L.getAs<PreImplicitCall>())
1867       continue;
1868     if (L.getAs<CallEnter>())
1869       continue;
1870     if (Optional<StmtPoint> SP = L.getAs<StmtPoint>())
1871       if (SP->getStmt() == CE)
1872         continue;
1873     break;
1874   }
1875 
1876   if (!BeforeProcessingCall)
1877     return false;
1878 
1879   // TODO: Clean up the unneeded nodes.
1880 
1881   // Build an Epsilon node from which we will restart the analyzes.
1882   // Note that CE is permitted to be NULL!
1883   ProgramPoint NewNodeLoc =
1884                EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
1885   // Add the special flag to GDM to signal retrying with no inlining.
1886   // Note, changing the state ensures that we are not going to cache out.
1887   ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
1888   NewNodeState =
1889     NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
1890 
1891   // Make the new node a successor of BeforeProcessingCall.
1892   bool IsNew = false;
1893   ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
1894   // We cached out at this point. Caching out is common due to us backtracking
1895   // from the inlined function, which might spawn several paths.
1896   if (!IsNew)
1897     return true;
1898 
1899   NewNode->addPredecessor(BeforeProcessingCall, G);
1900 
1901   // Add the new node to the work list.
1902   Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
1903                                   CalleeSF->getIndex());
1904   NumTimesRetriedWithoutInlining++;
1905   return true;
1906 }
1907 
1908 /// Block entrance.  (Update counters).
1909 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
1910                                          NodeBuilderWithSinks &nodeBuilder,
1911                                          ExplodedNode *Pred) {
1912   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
1913   // If we reach a loop which has a known bound (and meets
1914   // other constraints) then consider completely unrolling it.
1915   if(AMgr.options.ShouldUnrollLoops) {
1916     unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
1917     const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
1918     if (Term) {
1919       ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
1920                                                  Pred, maxBlockVisitOnPath);
1921       if (NewState != Pred->getState()) {
1922         ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred);
1923         if (!UpdatedNode)
1924           return;
1925         Pred = UpdatedNode;
1926       }
1927     }
1928     // Is we are inside an unrolled loop then no need the check the counters.
1929     if(isUnrolledState(Pred->getState()))
1930       return;
1931   }
1932 
1933   // If this block is terminated by a loop and it has already been visited the
1934   // maximum number of times, widen the loop.
1935   unsigned int BlockCount = nodeBuilder.getContext().blockCount();
1936   if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
1937       AMgr.options.ShouldWidenLoops) {
1938     const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
1939     if (!(Term &&
1940           (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term))))
1941       return;
1942     // Widen.
1943     const LocationContext *LCtx = Pred->getLocationContext();
1944     ProgramStateRef WidenedState =
1945         getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
1946     nodeBuilder.generateNode(WidenedState, Pred);
1947     return;
1948   }
1949 
1950   // FIXME: Refactor this into a checker.
1951   if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
1952     static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
1953     const ExplodedNode *Sink =
1954                    nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
1955 
1956     // Check if we stopped at the top level function or not.
1957     // Root node should have the location context of the top most function.
1958     const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
1959     const LocationContext *CalleeSF = CalleeLC->getStackFrame();
1960     const LocationContext *RootLC =
1961                         (*G.roots_begin())->getLocation().getLocationContext();
1962     if (RootLC->getStackFrame() != CalleeSF) {
1963       Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
1964 
1965       // Re-run the call evaluation without inlining it, by storing the
1966       // no-inlining policy in the state and enqueuing the new work item on
1967       // the list. Replay should almost never fail. Use the stats to catch it
1968       // if it does.
1969       if ((!AMgr.options.NoRetryExhausted &&
1970            replayWithoutInlining(Pred, CalleeLC)))
1971         return;
1972       NumMaxBlockCountReachedInInlined++;
1973     } else
1974       NumMaxBlockCountReached++;
1975 
1976     // Make sink nodes as exhausted(for stats) only if retry failed.
1977     Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
1978   }
1979 }
1980 
1981 //===----------------------------------------------------------------------===//
1982 // Branch processing.
1983 //===----------------------------------------------------------------------===//
1984 
1985 /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
1986 /// to try to recover some path-sensitivity for casts of symbolic
1987 /// integers that promote their values (which are currently not tracked well).
1988 /// This function returns the SVal bound to Condition->IgnoreCasts if all the
1989 //  cast(s) did was sign-extend the original value.
1990 static SVal RecoverCastedSymbol(ProgramStateRef state,
1991                                 const Stmt *Condition,
1992                                 const LocationContext *LCtx,
1993                                 ASTContext &Ctx) {
1994 
1995   const auto *Ex = dyn_cast<Expr>(Condition);
1996   if (!Ex)
1997     return UnknownVal();
1998 
1999   uint64_t bits = 0;
2000   bool bitsInit = false;
2001 
2002   while (const auto *CE = dyn_cast<CastExpr>(Ex)) {
2003     QualType T = CE->getType();
2004 
2005     if (!T->isIntegralOrEnumerationType())
2006       return UnknownVal();
2007 
2008     uint64_t newBits = Ctx.getTypeSize(T);
2009     if (!bitsInit || newBits < bits) {
2010       bitsInit = true;
2011       bits = newBits;
2012     }
2013 
2014     Ex = CE->getSubExpr();
2015   }
2016 
2017   // We reached a non-cast.  Is it a symbolic value?
2018   QualType T = Ex->getType();
2019 
2020   if (!bitsInit || !T->isIntegralOrEnumerationType() ||
2021       Ctx.getTypeSize(T) > bits)
2022     return UnknownVal();
2023 
2024   return state->getSVal(Ex, LCtx);
2025 }
2026 
2027 #ifndef NDEBUG
2028 static const Stmt *getRightmostLeaf(const Stmt *Condition) {
2029   while (Condition) {
2030     const auto *BO = dyn_cast<BinaryOperator>(Condition);
2031     if (!BO || !BO->isLogicalOp()) {
2032       return Condition;
2033     }
2034     Condition = BO->getRHS()->IgnoreParens();
2035   }
2036   return nullptr;
2037 }
2038 #endif
2039 
2040 // Returns the condition the branch at the end of 'B' depends on and whose value
2041 // has been evaluated within 'B'.
2042 // In most cases, the terminator condition of 'B' will be evaluated fully in
2043 // the last statement of 'B'; in those cases, the resolved condition is the
2044 // given 'Condition'.
2045 // If the condition of the branch is a logical binary operator tree, the CFG is
2046 // optimized: in that case, we know that the expression formed by all but the
2047 // rightmost leaf of the logical binary operator tree must be true, and thus
2048 // the branch condition is at this point equivalent to the truth value of that
2049 // rightmost leaf; the CFG block thus only evaluates this rightmost leaf
2050 // expression in its final statement. As the full condition in that case was
2051 // not evaluated, and is thus not in the SVal cache, we need to use that leaf
2052 // expression to evaluate the truth value of the condition in the current state
2053 // space.
2054 static const Stmt *ResolveCondition(const Stmt *Condition,
2055                                     const CFGBlock *B) {
2056   if (const auto *Ex = dyn_cast<Expr>(Condition))
2057     Condition = Ex->IgnoreParens();
2058 
2059   const auto *BO = dyn_cast<BinaryOperator>(Condition);
2060   if (!BO || !BO->isLogicalOp())
2061     return Condition;
2062 
2063   assert(B->getTerminator().isStmtBranch() &&
2064          "Other kinds of branches are handled separately!");
2065 
2066   // For logical operations, we still have the case where some branches
2067   // use the traditional "merge" approach and others sink the branch
2068   // directly into the basic blocks representing the logical operation.
2069   // We need to distinguish between those two cases here.
2070 
2071   // The invariants are still shifting, but it is possible that the
2072   // last element in a CFGBlock is not a CFGStmt.  Look for the last
2073   // CFGStmt as the value of the condition.
2074   CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
2075   for (; I != E; ++I) {
2076     CFGElement Elem = *I;
2077     Optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
2078     if (!CS)
2079       continue;
2080     const Stmt *LastStmt = CS->getStmt();
2081     assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition));
2082     return LastStmt;
2083   }
2084   llvm_unreachable("could not resolve condition");
2085 }
2086 
2087 void ExprEngine::processBranch(const Stmt *Condition,
2088                                NodeBuilderContext& BldCtx,
2089                                ExplodedNode *Pred,
2090                                ExplodedNodeSet &Dst,
2091                                const CFGBlock *DstT,
2092                                const CFGBlock *DstF) {
2093   assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) &&
2094          "CXXBindTemporaryExprs are handled by processBindTemporary.");
2095   const LocationContext *LCtx = Pred->getLocationContext();
2096   PrettyStackTraceLocationContext StackCrashInfo(LCtx);
2097   currBldrCtx = &BldCtx;
2098 
2099   // Check for NULL conditions; e.g. "for(;;)"
2100   if (!Condition) {
2101     BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
2102     NullCondBldr.markInfeasible(false);
2103     NullCondBldr.generateNode(Pred->getState(), true, Pred);
2104     return;
2105   }
2106 
2107   if (const auto *Ex = dyn_cast<Expr>(Condition))
2108     Condition = Ex->IgnoreParens();
2109 
2110   Condition = ResolveCondition(Condition, BldCtx.getBlock());
2111   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
2112                                 Condition->getBeginLoc(),
2113                                 "Error evaluating branch");
2114 
2115   ExplodedNodeSet CheckersOutSet;
2116   getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
2117                                                     Pred, *this);
2118   // We generated only sinks.
2119   if (CheckersOutSet.empty())
2120     return;
2121 
2122   BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
2123   for (const auto PredI : CheckersOutSet) {
2124     if (PredI->isSink())
2125       continue;
2126 
2127     ProgramStateRef PrevState = PredI->getState();
2128     SVal X = PrevState->getSVal(Condition, PredI->getLocationContext());
2129 
2130     if (X.isUnknownOrUndef()) {
2131       // Give it a chance to recover from unknown.
2132       if (const auto *Ex = dyn_cast<Expr>(Condition)) {
2133         if (Ex->getType()->isIntegralOrEnumerationType()) {
2134           // Try to recover some path-sensitivity.  Right now casts of symbolic
2135           // integers that promote their values are currently not tracked well.
2136           // If 'Condition' is such an expression, try and recover the
2137           // underlying value and use that instead.
2138           SVal recovered = RecoverCastedSymbol(PrevState, Condition,
2139                                                PredI->getLocationContext(),
2140                                                getContext());
2141 
2142           if (!recovered.isUnknown()) {
2143             X = recovered;
2144           }
2145         }
2146       }
2147     }
2148 
2149     // If the condition is still unknown, give up.
2150     if (X.isUnknownOrUndef()) {
2151       builder.generateNode(PrevState, true, PredI);
2152       builder.generateNode(PrevState, false, PredI);
2153       continue;
2154     }
2155 
2156     DefinedSVal V = X.castAs<DefinedSVal>();
2157 
2158     ProgramStateRef StTrue, StFalse;
2159     std::tie(StTrue, StFalse) = PrevState->assume(V);
2160 
2161     // Process the true branch.
2162     if (builder.isFeasible(true)) {
2163       if (StTrue)
2164         builder.generateNode(StTrue, true, PredI);
2165       else
2166         builder.markInfeasible(true);
2167     }
2168 
2169     // Process the false branch.
2170     if (builder.isFeasible(false)) {
2171       if (StFalse)
2172         builder.generateNode(StFalse, false, PredI);
2173       else
2174         builder.markInfeasible(false);
2175     }
2176   }
2177   currBldrCtx = nullptr;
2178 }
2179 
2180 /// The GDM component containing the set of global variables which have been
2181 /// previously initialized with explicit initializers.
2182 REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
2183                                  llvm::ImmutableSet<const VarDecl *>)
2184 
2185 void ExprEngine::processStaticInitializer(const DeclStmt *DS,
2186                                           NodeBuilderContext &BuilderCtx,
2187                                           ExplodedNode *Pred,
2188                                           ExplodedNodeSet &Dst,
2189                                           const CFGBlock *DstT,
2190                                           const CFGBlock *DstF) {
2191   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
2192   currBldrCtx = &BuilderCtx;
2193 
2194   const auto *VD = cast<VarDecl>(DS->getSingleDecl());
2195   ProgramStateRef state = Pred->getState();
2196   bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
2197   BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
2198 
2199   if (!initHasRun) {
2200     state = state->add<InitializedGlobalsSet>(VD);
2201   }
2202 
2203   builder.generateNode(state, initHasRun, Pred);
2204   builder.markInfeasible(!initHasRun);
2205 
2206   currBldrCtx = nullptr;
2207 }
2208 
2209 /// processIndirectGoto - Called by CoreEngine.  Used to generate successor
2210 ///  nodes by processing the 'effects' of a computed goto jump.
2211 void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
2212   ProgramStateRef state = builder.getState();
2213   SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
2214 
2215   // Three possibilities:
2216   //
2217   //   (1) We know the computed label.
2218   //   (2) The label is NULL (or some other constant), or Undefined.
2219   //   (3) We have no clue about the label.  Dispatch to all targets.
2220   //
2221 
2222   using iterator = IndirectGotoNodeBuilder::iterator;
2223 
2224   if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
2225     const LabelDecl *L = LV->getLabel();
2226 
2227     for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
2228       if (I.getLabel() == L) {
2229         builder.generateNode(I, state);
2230         return;
2231       }
2232     }
2233 
2234     llvm_unreachable("No block with label.");
2235   }
2236 
2237   if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) {
2238     // Dispatch to the first target and mark it as a sink.
2239     //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
2240     // FIXME: add checker visit.
2241     //    UndefBranches.insert(N);
2242     return;
2243   }
2244 
2245   // This is really a catch-all.  We don't support symbolics yet.
2246   // FIXME: Implement dispatch for symbolic pointers.
2247 
2248   for (iterator I = builder.begin(), E = builder.end(); I != E; ++I)
2249     builder.generateNode(I, state);
2250 }
2251 
2252 void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
2253                                         ExplodedNode *Pred,
2254                                         ExplodedNodeSet &Dst,
2255                                         const BlockEdge &L) {
2256   SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
2257   getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);
2258 }
2259 
2260 /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
2261 ///  nodes when the control reaches the end of a function.
2262 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
2263                                       ExplodedNode *Pred,
2264                                       const ReturnStmt *RS) {
2265   ProgramStateRef State = Pred->getState();
2266 
2267   if (!Pred->getStackFrame()->inTopFrame())
2268     State = finishArgumentConstruction(
2269         State, *getStateManager().getCallEventManager().getCaller(
2270                    Pred->getStackFrame(), Pred->getState()));
2271 
2272   // FIXME: We currently cannot assert that temporaries are clear, because
2273   // lifetime extended temporaries are not always modelled correctly. In some
2274   // cases when we materialize the temporary, we do
2275   // createTemporaryRegionIfNeeded(), and the region changes, and also the
2276   // respective destructor becomes automatic from temporary. So for now clean up
2277   // the state manually before asserting. Ideally, this braced block of code
2278   // should go away.
2279   {
2280     const LocationContext *FromLC = Pred->getLocationContext();
2281     const LocationContext *ToLC = FromLC->getStackFrame()->getParent();
2282     const LocationContext *LC = FromLC;
2283     while (LC != ToLC) {
2284       assert(LC && "ToLC must be a parent of FromLC!");
2285       for (auto I : State->get<ObjectsUnderConstruction>())
2286         if (I.first.getLocationContext() == LC) {
2287           // The comment above only pardons us for not cleaning up a
2288           // temporary destructor. If any other statements are found here,
2289           // it must be a separate problem.
2290           assert(I.first.getItem().getKind() ==
2291                      ConstructionContextItem::TemporaryDestructorKind ||
2292                  I.first.getItem().getKind() ==
2293                      ConstructionContextItem::ElidedDestructorKind);
2294           State = State->remove<ObjectsUnderConstruction>(I.first);
2295         }
2296       LC = LC->getParent();
2297     }
2298   }
2299 
2300   // Perform the transition with cleanups.
2301   if (State != Pred->getState()) {
2302     ExplodedNodeSet PostCleanup;
2303     NodeBuilder Bldr(Pred, PostCleanup, BC);
2304     Pred = Bldr.generateNode(Pred->getLocation(), State, Pred);
2305     if (!Pred) {
2306       // The node with clean temporaries already exists. We might have reached
2307       // it on a path on which we initialize different temporaries.
2308       return;
2309     }
2310   }
2311 
2312   assert(areAllObjectsFullyConstructed(Pred->getState(),
2313                                        Pred->getLocationContext(),
2314                                        Pred->getStackFrame()->getParent()));
2315 
2316   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
2317 
2318   ExplodedNodeSet Dst;
2319   if (Pred->getLocationContext()->inTopFrame()) {
2320     // Remove dead symbols.
2321     ExplodedNodeSet AfterRemovedDead;
2322     removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
2323 
2324     // Notify checkers.
2325     for (const auto I : AfterRemovedDead)
2326       getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS);
2327   } else {
2328     getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS);
2329   }
2330 
2331   Engine.enqueueEndOfFunction(Dst, RS);
2332 }
2333 
2334 /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
2335 ///  nodes by processing the 'effects' of a switch statement.
2336 void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
2337   using iterator = SwitchNodeBuilder::iterator;
2338 
2339   ProgramStateRef state = builder.getState();
2340   const Expr *CondE = builder.getCondition();
2341   SVal  CondV_untested = state->getSVal(CondE, builder.getLocationContext());
2342 
2343   if (CondV_untested.isUndef()) {
2344     //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
2345     // FIXME: add checker
2346     //UndefBranches.insert(N);
2347 
2348     return;
2349   }
2350   DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
2351 
2352   ProgramStateRef DefaultSt = state;
2353 
2354   iterator I = builder.begin(), EI = builder.end();
2355   bool defaultIsFeasible = I == EI;
2356 
2357   for ( ; I != EI; ++I) {
2358     // Successor may be pruned out during CFG construction.
2359     if (!I.getBlock())
2360       continue;
2361 
2362     const CaseStmt *Case = I.getCase();
2363 
2364     // Evaluate the LHS of the case value.
2365     llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
2366     assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType()));
2367 
2368     // Get the RHS of the case, if it exists.
2369     llvm::APSInt V2;
2370     if (const Expr *E = Case->getRHS())
2371       V2 = E->EvaluateKnownConstInt(getContext());
2372     else
2373       V2 = V1;
2374 
2375     ProgramStateRef StateCase;
2376     if (Optional<NonLoc> NL = CondV.getAs<NonLoc>())
2377       std::tie(StateCase, DefaultSt) =
2378           DefaultSt->assumeInclusiveRange(*NL, V1, V2);
2379     else // UnknownVal
2380       StateCase = DefaultSt;
2381 
2382     if (StateCase)
2383       builder.generateCaseStmtNode(I, StateCase);
2384 
2385     // Now "assume" that the case doesn't match.  Add this state
2386     // to the default state (if it is feasible).
2387     if (DefaultSt)
2388       defaultIsFeasible = true;
2389     else {
2390       defaultIsFeasible = false;
2391       break;
2392     }
2393   }
2394 
2395   if (!defaultIsFeasible)
2396     return;
2397 
2398   // If we have switch(enum value), the default branch is not
2399   // feasible if all of the enum constants not covered by 'case:' statements
2400   // are not feasible values for the switch condition.
2401   //
2402   // Note that this isn't as accurate as it could be.  Even if there isn't
2403   // a case for a particular enum value as long as that enum value isn't
2404   // feasible then it shouldn't be considered for making 'default:' reachable.
2405   const SwitchStmt *SS = builder.getSwitch();
2406   const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
2407   if (CondExpr->getType()->getAs<EnumType>()) {
2408     if (SS->isAllEnumCasesCovered())
2409       return;
2410   }
2411 
2412   builder.generateDefaultCaseNode(DefaultSt);
2413 }
2414 
2415 //===----------------------------------------------------------------------===//
2416 // Transfer functions: Loads and stores.
2417 //===----------------------------------------------------------------------===//
2418 
2419 void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
2420                                         ExplodedNode *Pred,
2421                                         ExplodedNodeSet &Dst) {
2422   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2423 
2424   ProgramStateRef state = Pred->getState();
2425   const LocationContext *LCtx = Pred->getLocationContext();
2426 
2427   if (const auto *VD = dyn_cast<VarDecl>(D)) {
2428     // C permits "extern void v", and if you cast the address to a valid type,
2429     // you can even do things with it. We simply pretend
2430     assert(Ex->isGLValue() || VD->getType()->isVoidType());
2431     const LocationContext *LocCtxt = Pred->getLocationContext();
2432     const Decl *D = LocCtxt->getDecl();
2433     const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D);
2434     const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex);
2435     Optional<std::pair<SVal, QualType>> VInfo;
2436 
2437     if (AMgr.options.ShouldInlineLambdas && DeclRefEx &&
2438         DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&
2439         MD->getParent()->isLambda()) {
2440       // Lookup the field of the lambda.
2441       const CXXRecordDecl *CXXRec = MD->getParent();
2442       llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
2443       FieldDecl *LambdaThisCaptureField;
2444       CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
2445 
2446       // Sema follows a sequence of complex rules to determine whether the
2447       // variable should be captured.
2448       if (const FieldDecl *FD = LambdaCaptureFields[VD]) {
2449         Loc CXXThis =
2450             svalBuilder.getCXXThis(MD, LocCtxt->getStackFrame());
2451         SVal CXXThisVal = state->getSVal(CXXThis);
2452         VInfo = std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType());
2453       }
2454     }
2455 
2456     if (!VInfo)
2457       VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType());
2458 
2459     SVal V = VInfo->first;
2460     bool IsReference = VInfo->second->isReferenceType();
2461 
2462     // For references, the 'lvalue' is the pointer address stored in the
2463     // reference region.
2464     if (IsReference) {
2465       if (const MemRegion *R = V.getAsRegion())
2466         V = state->getSVal(R);
2467       else
2468         V = UnknownVal();
2469     }
2470 
2471     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
2472                       ProgramPoint::PostLValueKind);
2473     return;
2474   }
2475   if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) {
2476     assert(!Ex->isGLValue());
2477     SVal V = svalBuilder.makeIntVal(ED->getInitVal());
2478     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
2479     return;
2480   }
2481   if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
2482     SVal V = svalBuilder.getFunctionPointer(FD);
2483     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
2484                       ProgramPoint::PostLValueKind);
2485     return;
2486   }
2487   if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D)) {
2488     // FIXME: Compute lvalue of field pointers-to-member.
2489     // Right now we just use a non-null void pointer, so that it gives proper
2490     // results in boolean contexts.
2491     // FIXME: Maybe delegate this to the surrounding operator&.
2492     // Note how this expression is lvalue, however pointer-to-member is NonLoc.
2493     SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy,
2494                                           currBldrCtx->blockCount());
2495     state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true);
2496     Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
2497                       ProgramPoint::PostLValueKind);
2498     return;
2499   }
2500   if (isa<BindingDecl>(D)) {
2501     // FIXME: proper support for bound declarations.
2502     // For now, let's just prevent crashing.
2503     return;
2504   }
2505 
2506   llvm_unreachable("Support for this Decl not implemented.");
2507 }
2508 
2509 /// VisitArraySubscriptExpr - Transfer function for array accesses
2510 void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A,
2511                                              ExplodedNode *Pred,
2512                                              ExplodedNodeSet &Dst){
2513   const Expr *Base = A->getBase()->IgnoreParens();
2514   const Expr *Idx  = A->getIdx()->IgnoreParens();
2515 
2516   ExplodedNodeSet CheckerPreStmt;
2517   getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this);
2518 
2519   ExplodedNodeSet EvalSet;
2520   StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
2521 
2522   bool IsVectorType = A->getBase()->getType()->isVectorType();
2523 
2524   // The "like" case is for situations where C standard prohibits the type to
2525   // be an lvalue, e.g. taking the address of a subscript of an expression of
2526   // type "void *".
2527   bool IsGLValueLike = A->isGLValue() ||
2528     (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus);
2529 
2530   for (auto *Node : CheckerPreStmt) {
2531     const LocationContext *LCtx = Node->getLocationContext();
2532     ProgramStateRef state = Node->getState();
2533 
2534     if (IsGLValueLike) {
2535       QualType T = A->getType();
2536 
2537       // One of the forbidden LValue types! We still need to have sensible
2538       // symbolic locations to represent this stuff. Note that arithmetic on
2539       // void pointers is a GCC extension.
2540       if (T->isVoidType())
2541         T = getContext().CharTy;
2542 
2543       SVal V = state->getLValue(T,
2544                                 state->getSVal(Idx, LCtx),
2545                                 state->getSVal(Base, LCtx));
2546       Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr,
2547           ProgramPoint::PostLValueKind);
2548     } else if (IsVectorType) {
2549       // FIXME: non-glvalue vector reads are not modelled.
2550       Bldr.generateNode(A, Node, state, nullptr);
2551     } else {
2552       llvm_unreachable("Array subscript should be an lValue when not \
2553 a vector and not a forbidden lvalue type");
2554     }
2555   }
2556 
2557   getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this);
2558 }
2559 
2560 /// VisitMemberExpr - Transfer function for member expressions.
2561 void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
2562                                  ExplodedNodeSet &Dst) {
2563   // FIXME: Prechecks eventually go in ::Visit().
2564   ExplodedNodeSet CheckedSet;
2565   getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this);
2566 
2567   ExplodedNodeSet EvalSet;
2568   ValueDecl *Member = M->getMemberDecl();
2569 
2570   // Handle static member variables and enum constants accessed via
2571   // member syntax.
2572   if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) {
2573     for (const auto I : CheckedSet)
2574       VisitCommonDeclRefExpr(M, Member, I, EvalSet);
2575   } else {
2576     StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
2577     ExplodedNodeSet Tmp;
2578 
2579     for (const auto I : CheckedSet) {
2580       ProgramStateRef state = I->getState();
2581       const LocationContext *LCtx = I->getLocationContext();
2582       Expr *BaseExpr = M->getBase();
2583 
2584       // Handle C++ method calls.
2585       if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) {
2586         if (MD->isInstance())
2587           state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
2588 
2589         SVal MDVal = svalBuilder.getFunctionPointer(MD);
2590         state = state->BindExpr(M, LCtx, MDVal);
2591 
2592         Bldr.generateNode(M, I, state);
2593         continue;
2594       }
2595 
2596       // Handle regular struct fields / member variables.
2597       const SubRegion *MR = nullptr;
2598       state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr,
2599                                             /*Result=*/nullptr,
2600                                             /*OutRegionWithAdjustments=*/&MR);
2601       SVal baseExprVal =
2602           MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx);
2603 
2604       const auto *field = cast<FieldDecl>(Member);
2605       SVal L = state->getLValue(field, baseExprVal);
2606 
2607       if (M->isGLValue() || M->getType()->isArrayType()) {
2608         // We special-case rvalues of array type because the analyzer cannot
2609         // reason about them, since we expect all regions to be wrapped in Locs.
2610         // We instead treat these as lvalues and assume that they will decay to
2611         // pointers as soon as they are used.
2612         if (!M->isGLValue()) {
2613           assert(M->getType()->isArrayType());
2614           const auto *PE =
2615             dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M));
2616           if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
2617             llvm_unreachable("should always be wrapped in ArrayToPointerDecay");
2618           }
2619         }
2620 
2621         if (field->getType()->isReferenceType()) {
2622           if (const MemRegion *R = L.getAsRegion())
2623             L = state->getSVal(R);
2624           else
2625             L = UnknownVal();
2626         }
2627 
2628         Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr,
2629                           ProgramPoint::PostLValueKind);
2630       } else {
2631         Bldr.takeNodes(I);
2632         evalLoad(Tmp, M, M, I, state, L);
2633         Bldr.addNodes(Tmp);
2634       }
2635     }
2636   }
2637 
2638   getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this);
2639 }
2640 
2641 void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,
2642                                  ExplodedNodeSet &Dst) {
2643   ExplodedNodeSet AfterPreSet;
2644   getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this);
2645 
2646   // For now, treat all the arguments to C11 atomics as escaping.
2647   // FIXME: Ideally we should model the behavior of the atomics precisely here.
2648 
2649   ExplodedNodeSet AfterInvalidateSet;
2650   StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);
2651 
2652   for (const auto I : AfterPreSet) {
2653     ProgramStateRef State = I->getState();
2654     const LocationContext *LCtx = I->getLocationContext();
2655 
2656     SmallVector<SVal, 8> ValuesToInvalidate;
2657     for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) {
2658       const Expr *SubExpr = AE->getSubExprs()[SI];
2659       SVal SubExprVal = State->getSVal(SubExpr, LCtx);
2660       ValuesToInvalidate.push_back(SubExprVal);
2661     }
2662 
2663     State = State->invalidateRegions(ValuesToInvalidate, AE,
2664                                     currBldrCtx->blockCount(),
2665                                     LCtx,
2666                                     /*CausedByPointerEscape*/true,
2667                                     /*Symbols=*/nullptr);
2668 
2669     SVal ResultVal = UnknownVal();
2670     State = State->BindExpr(AE, LCtx, ResultVal);
2671     Bldr.generateNode(AE, I, State, nullptr,
2672                       ProgramPoint::PostStmtKind);
2673   }
2674 
2675   getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);
2676 }
2677 
2678 // A value escapes in four possible cases:
2679 // (1) We are binding to something that is not a memory region.
2680 // (2) We are binding to a MemRegion that does not have stack storage.
2681 // (3) We are binding to a top-level parameter region with a non-trivial
2682 //     destructor. We won't see the destructor during analysis, but it's there.
2683 // (4) We are binding to a MemRegion with stack storage that the store
2684 //     does not understand.
2685 ProgramStateRef
2686 ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,
2687                                         SVal Val, const LocationContext *LCtx) {
2688 
2689   // Cases (1) and (2).
2690   const MemRegion *MR = Loc.getAsRegion();
2691   if (!MR || !MR->hasStackStorage())
2692     return escapeValue(State, Val, PSK_EscapeOnBind);
2693 
2694   // Case (3).
2695   if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion()))
2696     if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame())
2697       if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
2698         if (!RD->hasTrivialDestructor())
2699           return escapeValue(State, Val, PSK_EscapeOnBind);
2700 
2701   // Case (4): in order to test that, generate a new state with the binding
2702   // added. If it is the same state, then it escapes (since the store cannot
2703   // represent the binding).
2704   // Do this only if we know that the store is not supposed to generate the
2705   // same state.
2706   SVal StoredVal = State->getSVal(MR);
2707   if (StoredVal != Val)
2708     if (State == (State->bindLoc(loc::MemRegionVal(MR), Val, LCtx)))
2709       return escapeValue(State, Val, PSK_EscapeOnBind);
2710 
2711   return State;
2712 }
2713 
2714 ProgramStateRef
2715 ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
2716     const InvalidatedSymbols *Invalidated,
2717     ArrayRef<const MemRegion *> ExplicitRegions,
2718     const CallEvent *Call,
2719     RegionAndSymbolInvalidationTraits &ITraits) {
2720   if (!Invalidated || Invalidated->empty())
2721     return State;
2722 
2723   if (!Call)
2724     return getCheckerManager().runCheckersForPointerEscape(State,
2725                                                            *Invalidated,
2726                                                            nullptr,
2727                                                            PSK_EscapeOther,
2728                                                            &ITraits);
2729 
2730   // If the symbols were invalidated by a call, we want to find out which ones
2731   // were invalidated directly due to being arguments to the call.
2732   InvalidatedSymbols SymbolsDirectlyInvalidated;
2733   for (const auto I : ExplicitRegions) {
2734     if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>())
2735       SymbolsDirectlyInvalidated.insert(R->getSymbol());
2736   }
2737 
2738   InvalidatedSymbols SymbolsIndirectlyInvalidated;
2739   for (const auto &sym : *Invalidated) {
2740     if (SymbolsDirectlyInvalidated.count(sym))
2741       continue;
2742     SymbolsIndirectlyInvalidated.insert(sym);
2743   }
2744 
2745   if (!SymbolsDirectlyInvalidated.empty())
2746     State = getCheckerManager().runCheckersForPointerEscape(State,
2747         SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits);
2748 
2749   // Notify about the symbols that get indirectly invalidated by the call.
2750   if (!SymbolsIndirectlyInvalidated.empty())
2751     State = getCheckerManager().runCheckersForPointerEscape(State,
2752         SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits);
2753 
2754   return State;
2755 }
2756 
2757 /// evalBind - Handle the semantics of binding a value to a specific location.
2758 ///  This method is used by evalStore and (soon) VisitDeclStmt, and others.
2759 void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
2760                           ExplodedNode *Pred,
2761                           SVal location, SVal Val,
2762                           bool atDeclInit, const ProgramPoint *PP) {
2763   const LocationContext *LC = Pred->getLocationContext();
2764   PostStmt PS(StoreE, LC);
2765   if (!PP)
2766     PP = &PS;
2767 
2768   // Do a previsit of the bind.
2769   ExplodedNodeSet CheckedSet;
2770   getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
2771                                          StoreE, *this, *PP);
2772 
2773   StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
2774 
2775   // If the location is not a 'Loc', it will already be handled by
2776   // the checkers.  There is nothing left to do.
2777   if (!location.getAs<Loc>()) {
2778     const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr,
2779                                      /*tag*/nullptr);
2780     ProgramStateRef state = Pred->getState();
2781     state = processPointerEscapedOnBind(state, location, Val, LC);
2782     Bldr.generateNode(L, state, Pred);
2783     return;
2784   }
2785 
2786   for (const auto PredI : CheckedSet) {
2787     ProgramStateRef state = PredI->getState();
2788 
2789     state = processPointerEscapedOnBind(state, location, Val, LC);
2790 
2791     // When binding the value, pass on the hint that this is a initialization.
2792     // For initializations, we do not need to inform clients of region
2793     // changes.
2794     state = state->bindLoc(location.castAs<Loc>(),
2795                            Val, LC, /* notifyChanges = */ !atDeclInit);
2796 
2797     const MemRegion *LocReg = nullptr;
2798     if (Optional<loc::MemRegionVal> LocRegVal =
2799             location.getAs<loc::MemRegionVal>()) {
2800       LocReg = LocRegVal->getRegion();
2801     }
2802 
2803     const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr);
2804     Bldr.generateNode(L, state, PredI);
2805   }
2806 }
2807 
2808 /// evalStore - Handle the semantics of a store via an assignment.
2809 ///  @param Dst The node set to store generated state nodes
2810 ///  @param AssignE The assignment expression if the store happens in an
2811 ///         assignment.
2812 ///  @param LocationE The location expression that is stored to.
2813 ///  @param state The current simulation state
2814 ///  @param location The location to store the value
2815 ///  @param Val The value to be stored
2816 void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
2817                              const Expr *LocationE,
2818                              ExplodedNode *Pred,
2819                              ProgramStateRef state, SVal location, SVal Val,
2820                              const ProgramPointTag *tag) {
2821   // Proceed with the store.  We use AssignE as the anchor for the PostStore
2822   // ProgramPoint if it is non-NULL, and LocationE otherwise.
2823   const Expr *StoreE = AssignE ? AssignE : LocationE;
2824 
2825   // Evaluate the location (checks for bad dereferences).
2826   ExplodedNodeSet Tmp;
2827   evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false);
2828 
2829   if (Tmp.empty())
2830     return;
2831 
2832   if (location.isUndef())
2833     return;
2834 
2835   for (const auto I : Tmp)
2836     evalBind(Dst, StoreE, I, location, Val, false);
2837 }
2838 
2839 void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
2840                           const Expr *NodeEx,
2841                           const Expr *BoundEx,
2842                           ExplodedNode *Pred,
2843                           ProgramStateRef state,
2844                           SVal location,
2845                           const ProgramPointTag *tag,
2846                           QualType LoadTy) {
2847   assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
2848   assert(NodeEx);
2849   assert(BoundEx);
2850   // Evaluate the location (checks for bad dereferences).
2851   ExplodedNodeSet Tmp;
2852   evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true);
2853   if (Tmp.empty())
2854     return;
2855 
2856   StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
2857   if (location.isUndef())
2858     return;
2859 
2860   // Proceed with the load.
2861   for (const auto I : Tmp) {
2862     state = I->getState();
2863     const LocationContext *LCtx = I->getLocationContext();
2864 
2865     SVal V = UnknownVal();
2866     if (location.isValid()) {
2867       if (LoadTy.isNull())
2868         LoadTy = BoundEx->getType();
2869       V = state->getSVal(location.castAs<Loc>(), LoadTy);
2870     }
2871 
2872     Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag,
2873                       ProgramPoint::PostLoadKind);
2874   }
2875 }
2876 
2877 void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
2878                               const Stmt *NodeEx,
2879                               const Stmt *BoundEx,
2880                               ExplodedNode *Pred,
2881                               ProgramStateRef state,
2882                               SVal location,
2883                               bool isLoad) {
2884   StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
2885   // Early checks for performance reason.
2886   if (location.isUnknown()) {
2887     return;
2888   }
2889 
2890   ExplodedNodeSet Src;
2891   BldrTop.takeNodes(Pred);
2892   StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
2893   if (Pred->getState() != state) {
2894     // Associate this new state with an ExplodedNode.
2895     // FIXME: If I pass null tag, the graph is incorrect, e.g for
2896     //   int *p;
2897     //   p = 0;
2898     //   *p = 0xDEADBEEF;
2899     // "p = 0" is not noted as "Null pointer value stored to 'p'" but
2900     // instead "int *p" is noted as
2901     // "Variable 'p' initialized to a null pointer value"
2902 
2903     static SimpleProgramPointTag tag(TagProviderName, "Location");
2904     Bldr.generateNode(NodeEx, Pred, state, &tag);
2905   }
2906   ExplodedNodeSet Tmp;
2907   getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
2908                                              NodeEx, BoundEx, *this);
2909   BldrTop.addNodes(Tmp);
2910 }
2911 
2912 std::pair<const ProgramPointTag *, const ProgramPointTag*>
2913 ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
2914   static SimpleProgramPointTag
2915          eagerlyAssumeBinOpBifurcationTrue(TagProviderName,
2916                                            "Eagerly Assume True"),
2917          eagerlyAssumeBinOpBifurcationFalse(TagProviderName,
2918                                             "Eagerly Assume False");
2919   return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
2920                         &eagerlyAssumeBinOpBifurcationFalse);
2921 }
2922 
2923 void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
2924                                                    ExplodedNodeSet &Src,
2925                                                    const Expr *Ex) {
2926   StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
2927 
2928   for (const auto Pred : Src) {
2929     // Test if the previous node was as the same expression.  This can happen
2930     // when the expression fails to evaluate to anything meaningful and
2931     // (as an optimization) we don't generate a node.
2932     ProgramPoint P = Pred->getLocation();
2933     if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
2934       continue;
2935     }
2936 
2937     ProgramStateRef state = Pred->getState();
2938     SVal V = state->getSVal(Ex, Pred->getLocationContext());
2939     Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
2940     if (SEV && SEV->isExpression()) {
2941       const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
2942         geteagerlyAssumeBinOpBifurcationTags();
2943 
2944       ProgramStateRef StateTrue, StateFalse;
2945       std::tie(StateTrue, StateFalse) = state->assume(*SEV);
2946 
2947       // First assume that the condition is true.
2948       if (StateTrue) {
2949         SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
2950         StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
2951         Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
2952       }
2953 
2954       // Next, assume that the condition is false.
2955       if (StateFalse) {
2956         SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
2957         StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
2958         Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
2959       }
2960     }
2961   }
2962 }
2963 
2964 void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
2965                                  ExplodedNodeSet &Dst) {
2966   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2967   // We have processed both the inputs and the outputs.  All of the outputs
2968   // should evaluate to Locs.  Nuke all of their values.
2969 
2970   // FIXME: Some day in the future it would be nice to allow a "plug-in"
2971   // which interprets the inline asm and stores proper results in the
2972   // outputs.
2973 
2974   ProgramStateRef state = Pred->getState();
2975 
2976   for (const Expr *O : A->outputs()) {
2977     SVal X = state->getSVal(O, Pred->getLocationContext());
2978     assert(!X.getAs<NonLoc>());  // Should be an Lval, or unknown, undef.
2979 
2980     if (Optional<Loc> LV = X.getAs<Loc>())
2981       state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext());
2982   }
2983 
2984   Bldr.generateNode(A, Pred, state);
2985 }
2986 
2987 void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
2988                                 ExplodedNodeSet &Dst) {
2989   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2990   Bldr.generateNode(A, Pred, Pred->getState());
2991 }
2992 
2993 //===----------------------------------------------------------------------===//
2994 // Visualization.
2995 //===----------------------------------------------------------------------===//
2996 
2997 #ifndef NDEBUG
2998 namespace llvm {
2999 
3000 template<>
3001 struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits {
3002   DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
3003 
3004   static bool nodeHasBugReport(const ExplodedNode *N) {
3005     BugReporter &BR = static_cast<ExprEngine &>(
3006       N->getState()->getStateManager().getOwningEngine()).getBugReporter();
3007 
3008     const auto EQClasses =
3009         llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end());
3010 
3011     for (const auto &EQ : EQClasses) {
3012       for (const auto &I : EQ.getReports()) {
3013         const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get());
3014         if (!PR)
3015           continue;
3016         const ExplodedNode *EN = PR->getErrorNode();
3017         if (EN->getState() == N->getState() &&
3018             EN->getLocation() == N->getLocation())
3019           return true;
3020       }
3021     }
3022     return false;
3023   }
3024 
3025   /// \p PreCallback: callback before break.
3026   /// \p PostCallback: callback after break.
3027   /// \p Stop: stop iteration if returns {@code true}
3028   /// \return Whether {@code Stop} ever returned {@code true}.
3029   static bool traverseHiddenNodes(
3030       const ExplodedNode *N,
3031       llvm::function_ref<void(const ExplodedNode *)> PreCallback,
3032       llvm::function_ref<void(const ExplodedNode *)> PostCallback,
3033       llvm::function_ref<bool(const ExplodedNode *)> Stop) {
3034     while (true) {
3035       PreCallback(N);
3036       if (Stop(N))
3037         return true;
3038 
3039       if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc()))
3040         break;
3041       PostCallback(N);
3042 
3043       N = N->getFirstSucc();
3044     }
3045     return false;
3046   }
3047 
3048   static bool isNodeHidden(const ExplodedNode *N) {
3049     return N->isTrivial();
3050   }
3051 
3052   static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){
3053     std::string Buf;
3054     llvm::raw_string_ostream Out(Buf);
3055 
3056     const bool IsDot = true;
3057     const unsigned int Space = 1;
3058     ProgramStateRef State = N->getState();
3059 
3060     Out << "{ \"state_id\": " << State->getID()
3061         << ",\\l";
3062 
3063     Indent(Out, Space, IsDot) << "\"program_points\": [\\l";
3064 
3065     // Dump program point for all the previously skipped nodes.
3066     traverseHiddenNodes(
3067         N,
3068         [&](const ExplodedNode *OtherNode) {
3069           Indent(Out, Space + 1, IsDot) << "{ ";
3070           OtherNode->getLocation().printJson(Out, /*NL=*/"\\l");
3071           Out << ", \"tag\": ";
3072           if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())
3073             Out << '\"' << Tag->getTagDescription() << "\"";
3074           else
3075             Out << "null";
3076           Out << ", \"node_id\": " << OtherNode->getID() <<
3077                  ", \"is_sink\": " << OtherNode->isSink() <<
3078                  ", \"has_report\": " << nodeHasBugReport(OtherNode) << " }";
3079         },
3080         // Adds a comma and a new-line between each program point.
3081         [&](const ExplodedNode *) { Out << ",\\l"; },
3082         [&](const ExplodedNode *) { return false; });
3083 
3084     Out << "\\l"; // Adds a new-line to the last program point.
3085     Indent(Out, Space, IsDot) << "],\\l";
3086 
3087     State->printDOT(Out, N->getLocationContext(), Space);
3088 
3089     Out << "\\l}\\l";
3090     return Out.str();
3091   }
3092 };
3093 
3094 } // namespace llvm
3095 #endif
3096 
3097 void ExprEngine::ViewGraph(bool trim) {
3098 #ifndef NDEBUG
3099   std::string Filename = DumpGraph(trim);
3100   llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
3101 #endif
3102   llvm::errs() << "Warning: viewing graph requires assertions" << "\n";
3103 }
3104 
3105 
3106 void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) {
3107 #ifndef NDEBUG
3108   std::string Filename = DumpGraph(Nodes);
3109   llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
3110 #endif
3111   llvm::errs() << "Warning: viewing graph requires assertions" << "\n";
3112 }
3113 
3114 std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) {
3115 #ifndef NDEBUG
3116   if (trim) {
3117     std::vector<const ExplodedNode *> Src;
3118 
3119     // Iterate through the reports and get their nodes.
3120     for (BugReporter::EQClasses_iterator
3121            EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
3122       const auto *R =
3123           dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get());
3124       if (!R)
3125         continue;
3126       const auto *N = const_cast<ExplodedNode *>(R->getErrorNode());
3127       Src.push_back(N);
3128     }
3129     return DumpGraph(Src, Filename);
3130   } else {
3131     return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false,
3132                      /*Title=*/"Exploded Graph", /*Filename=*/Filename);
3133   }
3134 #endif
3135   llvm::errs() << "Warning: dumping graph requires assertions" << "\n";
3136   return "";
3137 }
3138 
3139 std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode*> Nodes,
3140                                   StringRef Filename) {
3141 #ifndef NDEBUG
3142   std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes));
3143 
3144   if (!TrimmedG.get()) {
3145     llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
3146   } else {
3147     return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine",
3148                             /*ShortNames=*/false,
3149                             /*Title=*/"Trimmed Exploded Graph",
3150                             /*Filename=*/Filename);
3151   }
3152 #endif
3153   llvm::errs() << "Warning: dumping graph requires assertions" << "\n";
3154   return "";
3155 }
3156 
3157 void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() {
3158   static int index = 0;
3159   return &index;
3160 }
3161