ProgramState.cpp source code [clang_source_code/lib/StaticAnalyzer/Core/ProgramState.cpp]

1	//= ProgramState.cpp - Path-Sensitive "State" for tracking values --- C++ ---=
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 implements ProgramState and ProgramStateManager.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
14	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
15	#include "clang/Analysis/CFG.h"
16	#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
17	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
18	#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
19	#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h"
20	#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
21	#include "llvm/Support/raw_ostream.h"
22
23	using namespace clang;
24	using namespace ento;
25
26	namespace clang { namespace ento {
27	/// Increments the number of times this state is referenced.
28
29	void ProgramStateRetain(const ProgramState *state) {
30	++const_cast<ProgramState*>(state)->refCount;
31	}
32
33	/// Decrement the number of times this state is referenced.
34	void ProgramStateRelease(const ProgramState *state) {
35	refCount > 0", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/ProgramState.cpp", 35, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(state->refCount > 0);
36	ProgramState s = const_cast<ProgramState>(state);
37	if (--s->refCount == 0) {
38	ProgramStateManager &Mgr = s->getStateManager();
39	Mgr.StateSet.RemoveNode(s);
40	s->~ProgramState();
41	Mgr.freeStates.push_back(s);
42	}
43	}
44	}}
45
46	ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env,
47	StoreRef st, GenericDataMap gdm)
48	: stateMgr(mgr),
49	Env(env),
50	store(st.getStore()),
51	GDM(gdm),
52	refCount(0) {
53	stateMgr->getStoreManager().incrementReferenceCount(store);
54	}
55
56	ProgramState::ProgramState(const ProgramState &RHS)
57	: llvm::FoldingSetNode(),
58	stateMgr(RHS.stateMgr),
59	Env(RHS.Env),
60	store(RHS.store),
61	GDM(RHS.GDM),
62	refCount(0) {
63	stateMgr->getStoreManager().incrementReferenceCount(store);
64	}
65
66	ProgramState::~ProgramState() {
67	if (store)
68	stateMgr->getStoreManager().decrementReferenceCount(store);
69	}
70
71	int64_t ProgramState::getID() const {
72	return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(this);
73	}
74
75	ProgramStateManager::ProgramStateManager(ASTContext &Ctx,
76	StoreManagerCreator CreateSMgr,
77	ConstraintManagerCreator CreateCMgr,
78	llvm::BumpPtrAllocator &alloc,
79	SubEngine *SubEng)
80	: Eng(SubEng), EnvMgr(alloc), GDMFactory(alloc),
81	svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)),
82	CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) {
83	StoreMgr = (CreateSMgr)(this);
84	ConstraintMgr = (CreateCMgr)(this, SubEng);
85	}
86
87
88	ProgramStateManager::~ProgramStateManager() {
89	for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
90	I!=E; ++I)
91	I->second.second(I->second.first);
92	}
93
94	ProgramStateRef
95	ProgramStateManager::removeDeadBindings(ProgramStateRef state,
96	const StackFrameContext *LCtx,
97	SymbolReaper& SymReaper) {
98
99	// This code essentially performs a "mark-and-sweep" of the VariableBindings.
100	// The roots are any Block-level exprs and Decls that our liveness algorithm
101	// tells us are live. We then see what Decls they may reference, and keep
102	// those around. This code more than likely can be made faster, and the
103	// frequency of which this method is called should be experimented with
104	// for optimum performance.
105	ProgramState NewState = *state;
106
107	NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);
108
109	// Clean up the store.
110	StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
111	SymReaper);
112	NewState.setStore(newStore);
113	SymReaper.setReapedStore(newStore);
114
115	ProgramStateRef Result = getPersistentState(NewState);
116	return ConstraintMgr->removeDeadBindings(Result, SymReaper);
117	}
118
119	ProgramStateRef ProgramState::bindLoc(Loc LV,
120	SVal V,
121	const LocationContext *LCtx,
122	bool notifyChanges) const {
123	ProgramStateManager &Mgr = getStateManager();
124	ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(),
125	LV, V));
126	const MemRegion *MR = LV.getAsRegion();
127	if (MR && notifyChanges)
128	return Mgr.getOwningEngine().processRegionChange(newState, MR, LCtx);
129
130	return newState;
131	}
132
133	ProgramStateRef
134	ProgramState::bindDefaultInitial(SVal loc, SVal V,
135	const LocationContext *LCtx) const {
136	ProgramStateManager &Mgr = getStateManager();
137	const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
138	const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V);
139	ProgramStateRef new_state = makeWithStore(newStore);
140	return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
141	}
142
143	ProgramStateRef
144	ProgramState::bindDefaultZero(SVal loc, const LocationContext *LCtx) const {
145	ProgramStateManager &Mgr = getStateManager();
146	const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
147	const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R);
148	ProgramStateRef new_state = makeWithStore(newStore);
149	return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
150	}
151
152	typedef ArrayRef<const MemRegion *> RegionList;
153	typedef ArrayRef<SVal> ValueList;
154
155	ProgramStateRef
156	ProgramState::invalidateRegions(RegionList Regions,
157	const Expr *E, unsigned Count,
158	const LocationContext *LCtx,
159	bool CausedByPointerEscape,
160	InvalidatedSymbols *IS,
161	const CallEvent *Call,
162	RegionAndSymbolInvalidationTraits *ITraits) const {
163	SmallVector<SVal, 8> Values;
164	for (RegionList::const_iterator I = Regions.begin(),
165	End = Regions.end(); I != End; ++I)
166	Values.push_back(loc::MemRegionVal(*I));
167
168	return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
169	IS, ITraits, Call);
170	}
171
172	ProgramStateRef
173	ProgramState::invalidateRegions(ValueList Values,
174	const Expr *E, unsigned Count,
175	const LocationContext *LCtx,
176	bool CausedByPointerEscape,
177	InvalidatedSymbols *IS,
178	const CallEvent *Call,
179	RegionAndSymbolInvalidationTraits *ITraits) const {
180
181	return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
182	IS, ITraits, Call);
183	}
184
185	ProgramStateRef
186	ProgramState::invalidateRegionsImpl(ValueList Values,
187	const Expr *E, unsigned Count,
188	const LocationContext *LCtx,
189	bool CausedByPointerEscape,
190	InvalidatedSymbols *IS,
191	RegionAndSymbolInvalidationTraits *ITraits,
192	const CallEvent *Call) const {
193	ProgramStateManager &Mgr = getStateManager();
194	SubEngine &Eng = Mgr.getOwningEngine();
195
196	InvalidatedSymbols InvalidatedSyms;
197	if (!IS)
198	IS = &InvalidatedSyms;
199
200	RegionAndSymbolInvalidationTraits ITraitsLocal;
201	if (!ITraits)
202	ITraits = &ITraitsLocal;
203
204	StoreManager::InvalidatedRegions TopLevelInvalidated;
205	StoreManager::InvalidatedRegions Invalidated;
206	const StoreRef &newStore
207	= Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call,
208	IS, ITraits, &TopLevelInvalidated,
209	&Invalidated);
210
211	ProgramStateRef newState = makeWithStore(newStore);
212
213	if (CausedByPointerEscape) {
214	newState = Eng.notifyCheckersOfPointerEscape(newState, IS,
215	TopLevelInvalidated,
216	Call,
217	*ITraits);
218	}
219
220	return Eng.processRegionChanges(newState, IS, TopLevelInvalidated,
221	Invalidated, LCtx, Call);
222	}
223
224	ProgramStateRef ProgramState::killBinding(Loc LV) const {
225	(0) . __assert_fail ("!LV.getAs() && \"Use invalidateRegion instead.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/ProgramState.cpp", 225, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead.");
226
227	Store OldStore = getStore();
228	const StoreRef &newStore =
229	getStateManager().StoreMgr->killBinding(OldStore, LV);
230
231	if (newStore.getStore() == OldStore)
232	return this;
233
234	return makeWithStore(newStore);
235	}
236
237	ProgramStateRef
238	ProgramState::enterStackFrame(const CallEvent &Call,
239	const StackFrameContext *CalleeCtx) const {
240	const StoreRef &NewStore =
241	getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx);
242	return makeWithStore(NewStore);
243	}
244
245	SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const {
246	// We only want to do fetches from regions that we can actually bind
247	// values. For example, SymbolicRegions of type 'id<...>' cannot
248	// have direct bindings (but their can be bindings on their subregions).
249	if (!R->isBoundable())
250	return UnknownVal();
251
252	if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
253	QualType T = TR->getValueType();
254	if (Loc::isLocType(T) \|\| T->isIntegralOrEnumerationType())
255	return getSVal(R);
256	}
257
258	return UnknownVal();
259	}
260
261	SVal ProgramState::getSVal(Loc location, QualType T) const {
262	SVal V = getRawSVal(location, T);
263
264	// If 'V' is a symbolic value that is perfectly constrained to
265	// be a constant value, use that value instead to lessen the burden
266	// on later analysis stages (so we have less symbolic values to reason
267	// about).
268	// We only go into this branch if we can convert the APSInt value we have
269	// to the type of T, which is not always the case (e.g. for void).
270	if (!T.isNull() && (T->isIntegralOrEnumerationType() \|\| Loc::isLocType(T))) {
271	if (SymbolRef sym = V.getAsSymbol()) {
272	if (const llvm::APSInt *Int = getStateManager()
273	.getConstraintManager()
274	.getSymVal(this, sym)) {
275	// FIXME: Because we don't correctly model (yet) sign-extension
276	// and truncation of symbolic values, we need to convert
277	// the integer value to the correct signedness and bitwidth.
278	//
279	// This shows up in the following:
280	//
281	// char foo();
282	// unsigned x = foo();
283	// if (x == 54)
284	// ...
285	//
286	// The symbolic value stored to 'x' is actually the conjured
287	// symbol for the call to foo(); the type of that symbol is 'char',
288	// not unsigned.
289	const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int);
290
291	if (V.getAs<Loc>())
292	return loc::ConcreteInt(NewV);
293	else
294	return nonloc::ConcreteInt(NewV);
295	}
296	}
297	}
298
299	return V;
300	}
301
302	ProgramStateRef ProgramState::BindExpr(const Stmt *S,
303	const LocationContext *LCtx,
304	SVal V, bool Invalidate) const{
305	Environment NewEnv =
306	getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V,
307	Invalidate);
308	if (NewEnv == Env)
309	return this;
310
311	ProgramState NewSt = *this;
312	NewSt.Env = NewEnv;
313	return getStateManager().getPersistentState(NewSt);
314	}
315
316	ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx,
317	DefinedOrUnknownSVal UpperBound,
318	bool Assumption,
319	QualType indexTy) const {
320	if (Idx.isUnknown() \|\| UpperBound.isUnknown())
321	return this;
322
323	// Build an expression for 0 <= Idx < UpperBound.
324	// This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
325	// FIXME: This should probably be part of SValBuilder.
326	ProgramStateManager &SM = getStateManager();
327	SValBuilder &svalBuilder = SM.getSValBuilder();
328	ASTContext &Ctx = svalBuilder.getContext();
329
330	// Get the offset: the minimum value of the array index type.
331	BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
332	if (indexTy.isNull())
333	indexTy = svalBuilder.getArrayIndexType();
334	nonloc::ConcreteInt Min(BVF.getMinValue(indexTy));
335
336	// Adjust the index.
337	SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add,
338	Idx.castAs<NonLoc>(), Min, indexTy);
339	if (newIdx.isUnknownOrUndef())
340	return this;
341
342	// Adjust the upper bound.
343	SVal newBound =
344	svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(),
345	Min, indexTy);
346
347	if (newBound.isUnknownOrUndef())
348	return this;
349
350	// Build the actual comparison.
351	SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(),
352	newBound.castAs<NonLoc>(), Ctx.IntTy);
353	if (inBound.isUnknownOrUndef())
354	return this;
355
356	// Finally, let the constraint manager take care of it.
357	ConstraintManager &CM = SM.getConstraintManager();
358	return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption);
359	}
360
361	ConditionTruthVal ProgramState::isNonNull(SVal V) const {
362	ConditionTruthVal IsNull = isNull(V);
363	if (IsNull.isUnderconstrained())
364	return IsNull;
365	return ConditionTruthVal(!IsNull.getValue());
366	}
367
368	ConditionTruthVal ProgramState::areEqual(SVal Lhs, SVal Rhs) const {
369	return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs);
370	}
371
372	ConditionTruthVal ProgramState::isNull(SVal V) const {
373	if (V.isZeroConstant())
374	return true;
375
376	if (V.isConstant())
377	return false;
378
379	SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true);
380	if (!Sym)
381	return ConditionTruthVal();
382
383	return getStateManager().ConstraintMgr->isNull(this, Sym);
384	}
385
386	ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) {
387	ProgramState State(this,
388	EnvMgr.getInitialEnvironment(),
389	StoreMgr->getInitialStore(InitLoc),
390	GDMFactory.getEmptyMap());
391
392	return getPersistentState(State);
393	}
394
395	ProgramStateRef ProgramStateManager::getPersistentStateWithGDM(
396	ProgramStateRef FromState,
397	ProgramStateRef GDMState) {
398	ProgramState NewState(*FromState);
399	NewState.GDM = GDMState->GDM;
400	return getPersistentState(NewState);
401	}
402
403	ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) {
404
405	llvm::FoldingSetNodeID ID;
406	State.Profile(ID);
407	void *InsertPos;
408
409	if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
410	return I;
411
412	ProgramState *newState = nullptr;
413	if (!freeStates.empty()) {
414	newState = freeStates.back();
415	freeStates.pop_back();
416	}
417	else {
418	newState = (ProgramState*) Alloc.Allocate<ProgramState>();
419	}
420	new (newState) ProgramState(State);
421	StateSet.InsertNode(newState, InsertPos);
422	return newState;
423	}
424
425	ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const {
426	ProgramState NewSt(*this);
427	NewSt.setStore(store);
428	return getStateManager().getPersistentState(NewSt);
429	}
430
431	void ProgramState::setStore(const StoreRef &newStore) {
432	Store newStoreStore = newStore.getStore();
433	if (newStoreStore)
434	stateMgr->getStoreManager().incrementReferenceCount(newStoreStore);
435	if (store)
436	stateMgr->getStoreManager().decrementReferenceCount(store);
437	store = newStoreStore;
438	}
439
440	//===----------------------------------------------------------------------===//
441	// State pretty-printing.
442	//===----------------------------------------------------------------------===//
443
444	void ProgramState::print(raw_ostream &Out,
445	const char NL, const char Sep,
446	const LocationContext *LC) const {
447	// Print the store.
448	ProgramStateManager &Mgr = getStateManager();
449	const ASTContext &Context = getStateManager().getContext();
450	Mgr.getStoreManager().print(getStore(), Out, NL);
451
452	// Print out the environment.
453	Env.print(Out, NL, Sep, Context, LC);
454
455	// Print out the constraints.
456	Mgr.getConstraintManager().print(this, Out, NL, Sep);
457
458	// Print out the tracked dynamic types.
459	printDynamicTypeInfo(this, Out, NL, Sep);
460
461	// Print out tainted symbols.
462	printTaint(Out, NL);
463
464	// Print checker-specific data.
465	Mgr.getOwningEngine().printState(Out, this, NL, Sep, LC);
466	}
467
468	void ProgramState::printDOT(raw_ostream &Out,
469	const LocationContext *LC) const {
470	print(Out, "\\l", "\\\|", LC);
471	}
472
473	LLVM_DUMP_METHOD void ProgramState::dump() const {
474	print(llvm::errs());
475	}
476
477	void ProgramState::printTaint(raw_ostream &Out,
478	const char *NL) const {
479	TaintMapImpl TM = get<TaintMap>();
480
481	if (!TM.isEmpty())
482	Out <<"Tainted symbols:" << NL;
483
484	for (TaintMapImpl::iterator I = TM.begin(), E = TM.end(); I != E; ++I) {
485	Out << I->first << " : " << I->second << NL;
486	}
487	}
488
489	void ProgramState::dumpTaint() const {
490	printTaint(llvm::errs());
491	}
492
493	AnalysisManager& ProgramState::getAnalysisManager() const {
494	return stateMgr->getOwningEngine().getAnalysisManager();
495	}
496
497	//===----------------------------------------------------------------------===//
498	// Generic Data Map.
499	//===----------------------------------------------------------------------===//
500
501	void const ProgramState::FindGDM(void *K) const {
502	return GDM.lookup(K);
503	}
504
505	void*
506	ProgramStateManager::FindGDMContext(void *K,
507	void (CreateContext)(llvm::BumpPtrAllocator&),
508	void (DeleteContext)(void)) {
509
510	std::pair<void, void ()(void*)>& p = GDMContexts[K];
511	if (!p.first) {
512	p.first = CreateContext(Alloc);
513	p.second = DeleteContext;
514	}
515
516	return p.first;
517	}
518
519	ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void Key, void Data){
520	ProgramState::GenericDataMap M1 = St->getGDM();
521	ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data);
522
523	if (M1 == M2)
524	return St;
525
526	ProgramState NewSt = *St;
527	NewSt.GDM = M2;
528	return getPersistentState(NewSt);
529	}
530
531	ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) {
532	ProgramState::GenericDataMap OldM = state->getGDM();
533	ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key);
534
535	if (NewM == OldM)
536	return state;
537
538	ProgramState NewState = *state;
539	NewState.GDM = NewM;
540	return getPersistentState(NewState);
541	}
542
543	bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
544	bool wasVisited = !visited.insert(val.getCVData()).second;
545	if (wasVisited)
546	return true;
547
548	StoreManager &StoreMgr = state->getStateManager().getStoreManager();
549	// FIXME: We don't really want to use getBaseRegion() here because pointer
550	// arithmetic doesn't apply, but scanReachableSymbols only accepts base
551	// regions right now.
552	const MemRegion *R = val.getRegion()->getBaseRegion();
553	return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
554	}
555
556	bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
557	for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I)
558	if (!scan(*I))
559	return false;
560
561	return true;
562	}
563
564	bool ScanReachableSymbols::scan(const SymExpr *sym) {
565	for (SymExpr::symbol_iterator SI = sym->symbol_begin(),
566	SE = sym->symbol_end();
567	SI != SE; ++SI) {
568	bool wasVisited = !visited.insert(*SI).second;
569	if (wasVisited)
570	continue;
571
572	if (!visitor.VisitSymbol(*SI))
573	return false;
574	}
575
576	return true;
577	}
578
579	bool ScanReachableSymbols::scan(SVal val) {
580	if (Optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>())
581	return scan(X->getRegion());
582
583	if (Optional<nonloc::LazyCompoundVal> X =
584	val.getAs<nonloc::LazyCompoundVal>())
585	return scan(*X);
586
587	if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
588	return scan(X->getLoc());
589
590	if (SymbolRef Sym = val.getAsSymbol())
591	return scan(Sym);
592
593	if (const SymExpr *Sym = val.getAsSymbolicExpression())
594	return scan(Sym);
595
596	if (Optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>())
597	return scan(*X);
598
599	return true;
600	}
601
602	bool ScanReachableSymbols::scan(const MemRegion *R) {
603	if (isa<MemSpaceRegion>(R))
604	return true;
605
606	bool wasVisited = !visited.insert(R).second;
607	if (wasVisited)
608	return true;
609
610	if (!visitor.VisitMemRegion(R))
611	return false;
612
613	// If this is a symbolic region, visit the symbol for the region.
614	if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
615	if (!visitor.VisitSymbol(SR->getSymbol()))
616	return false;
617
618	// If this is a subregion, also visit the parent regions.
619	if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
620	const MemRegion *Super = SR->getSuperRegion();
621	if (!scan(Super))
622	return false;
623
624	// When we reach the topmost region, scan all symbols in it.
625	if (isa<MemSpaceRegion>(Super)) {
626	StoreManager &StoreMgr = state->getStateManager().getStoreManager();
627	if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this))
628	return false;
629	}
630	}
631
632	// Regions captured by a block are also implicitly reachable.
633	if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
634	BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
635	E = BDR->referenced_vars_end();
636	for ( ; I != E; ++I) {
637	if (!scan(I.getCapturedRegion()))
638	return false;
639	}
640	}
641
642	return true;
643	}
644
645	bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
646	ScanReachableSymbols S(this, visitor);
647	return S.scan(val);
648	}
649
650	bool ProgramState::scanReachableSymbols(
651	llvm::iterator_range<region_iterator> Reachable,
652	SymbolVisitor &visitor) const {
653	ScanReachableSymbols S(this, visitor);
654	for (const MemRegion *R : Reachable) {
655	if (!S.scan(R))
656	return false;
657	}
658	return true;
659	}
660
661	ProgramStateRef ProgramState::addTaint(const Stmt *S,
662	const LocationContext *LCtx,
663	TaintTagType Kind) const {
664	if (const Expr *E = dyn_cast_or_null<Expr>(S))
665	S = E->IgnoreParens();
666
667	return addTaint(getSVal(S, LCtx), Kind);
668	}
669
670	ProgramStateRef ProgramState::addTaint(SVal V,
671	TaintTagType Kind) const {
672	SymbolRef Sym = V.getAsSymbol();
673	if (Sym)
674	return addTaint(Sym, Kind);
675
676	// If the SVal represents a structure, try to mass-taint all values within the
677	// structure. For now it only works efficiently on lazy compound values that
678	// were conjured during a conservative evaluation of a function - either as
679	// return values of functions that return structures or arrays by value, or as
680	// values of structures or arrays passed into the function by reference,
681	// directly or through pointer aliasing. Such lazy compound values are
682	// characterized by having exactly one binding in their captured store within
683	// their parent region, which is a conjured symbol default-bound to the base
684	// region of the parent region.
685	if (auto LCV = V.getAs<nonloc::LazyCompoundVal>()) {
686	if (Optional<SVal> binding = getStateManager().StoreMgr->getDefaultBinding(*LCV)) {
687	if (SymbolRef Sym = binding->getAsSymbol())
688	return addPartialTaint(Sym, LCV->getRegion(), Kind);
689	}
690	}
691
692	const MemRegion *R = V.getAsRegion();
693	return addTaint(R, Kind);
694	}
695
696	ProgramStateRef ProgramState::addTaint(const MemRegion *R,
697	TaintTagType Kind) const {
698	if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R))
699	return addTaint(SR->getSymbol(), Kind);
700	return this;
701	}
702
703	ProgramStateRef ProgramState::addTaint(SymbolRef Sym,
704	TaintTagType Kind) const {
705	// If this is a symbol cast, remove the cast before adding the taint. Taint
706	// is cast agnostic.
707	while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym))
708	Sym = SC->getOperand();
709
710	ProgramStateRef NewState = set<TaintMap>(Sym, Kind);
711	assert(NewState);
712	return NewState;
713	}
714
715	ProgramStateRef ProgramState::addPartialTaint(SymbolRef ParentSym,
716	const SubRegion *SubRegion,
717	TaintTagType Kind) const {
718	// Ignore partial taint if the entire parent symbol is already tainted.
719	if (contains<TaintMap>(ParentSym) && *get<TaintMap>(ParentSym) == Kind)
720	return this;
721
722	// Partial taint applies if only a portion of the symbol is tainted.
723	if (SubRegion == SubRegion->getBaseRegion())
724	return addTaint(ParentSym, Kind);
725
726	const TaintedSubRegions *SavedRegs = get<DerivedSymTaint>(ParentSym);
727	TaintedSubRegions Regs =
728	SavedRegs ? *SavedRegs : stateMgr->TSRFactory.getEmptyMap();
729
730	Regs = stateMgr->TSRFactory.add(Regs, SubRegion, Kind);
731	ProgramStateRef NewState = set<DerivedSymTaint>(ParentSym, Regs);
732	assert(NewState);
733	return NewState;
734	}
735
736	bool ProgramState::isTainted(const Stmt S, const LocationContext LCtx,
737	TaintTagType Kind) const {
738	if (const Expr *E = dyn_cast_or_null<Expr>(S))
739	S = E->IgnoreParens();
740
741	SVal val = getSVal(S, LCtx);
742	return isTainted(val, Kind);
743	}
744
745	bool ProgramState::isTainted(SVal V, TaintTagType Kind) const {
746	if (const SymExpr *Sym = V.getAsSymExpr())
747	return isTainted(Sym, Kind);
748	if (const MemRegion *Reg = V.getAsRegion())
749	return isTainted(Reg, Kind);
750	return false;
751	}
752
753	bool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const {
754	if (!Reg)
755	return false;
756
757	// Element region (array element) is tainted if either the base or the offset
758	// are tainted.
759	if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg))
760	return isTainted(ER->getSuperRegion(), K) \|\| isTainted(ER->getIndex(), K);
761
762	if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg))
763	return isTainted(SR->getSymbol(), K);
764
765	if (const SubRegion *ER = dyn_cast<SubRegion>(Reg))
766	return isTainted(ER->getSuperRegion(), K);
767
768	return false;
769	}
770
771	bool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const {
772	if (!Sym)
773	return false;
774
775	// Traverse all the symbols this symbol depends on to see if any are tainted.
776	for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end();
777	SI != SE; ++SI) {
778	if (!isa<SymbolData>(*SI))
779	continue;
780
781	if (const TaintTagType Tag = get<TaintMap>(SI)) {
782	if (*Tag == Kind)
783	return true;
784	}
785
786	if (const SymbolDerived SD = dyn_cast<SymbolDerived>(SI)) {
787	// If this is a SymbolDerived with a tainted parent, it's also tainted.
788	if (isTainted(SD->getParentSymbol(), Kind))
789	return true;
790
791	// If this is a SymbolDerived with the same parent symbol as another
792	// tainted SymbolDerived and a region that's a sub-region of that tainted
793	// symbol, it's also tainted.
794	if (const TaintedSubRegions *Regs =
795	get<DerivedSymTaint>(SD->getParentSymbol())) {
796	const TypedValueRegion *R = SD->getRegion();
797	for (auto I : *Regs) {
798	// FIXME: The logic to identify tainted regions could be more
799	// complete. For example, this would not currently identify
800	// overlapping fields in a union as tainted. To identify this we can
801	// check for overlapping/nested byte offsets.
802	if (Kind == I.second && R->isSubRegionOf(I.first))
803	return true;
804	}
805	}
806	}
807
808	// If memory region is tainted, data is also tainted.
809	if (const SymbolRegionValue SRV = dyn_cast<SymbolRegionValue>(SI)) {
810	if (isTainted(SRV->getRegion(), Kind))
811	return true;
812	}
813
814	// If this is a SymbolCast from a tainted value, it's also tainted.
815	if (const SymbolCast SC = dyn_cast<SymbolCast>(SI)) {
816	if (isTainted(SC->getOperand(), Kind))
817	return true;
818	}
819	}
820
821	return false;
822	}
823