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