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

1	//== RegionStore.cpp - Field-sensitive store model --------------- 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 defines a basic region store model. In this model, we do have field
10	// sensitivity. But we assume nothing about the heap shape. So recursive data
11	// structures are largely ignored. Basically we do 1-limiting analysis.
12	// Parameter pointers are assumed with no aliasing. Pointee objects of
13	// parameters are created lazily.
14	//
15	//===----------------------------------------------------------------------===//
16
17	#include "clang/AST/Attr.h"
18	#include "clang/AST/CharUnits.h"
19	#include "clang/ASTMatchers/ASTMatchFinder.h"
20	#include "clang/Analysis/Analyses/LiveVariables.h"
21	#include "clang/Analysis/AnalysisDeclContext.h"
22	#include "clang/Basic/TargetInfo.h"
23	#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
24	#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
25	#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
26	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
27	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
28	#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
29	#include "llvm/ADT/ImmutableMap.h"
30	#include "llvm/ADT/Optional.h"
31	#include "llvm/Support/raw_ostream.h"
32	#include <utility>
33
34	using namespace clang;
35	using namespace ento;
36
37	//===----------------------------------------------------------------------===//
38	// Representation of binding keys.
39	//===----------------------------------------------------------------------===//
40
41	namespace {
42	class BindingKey {
43	public:
44	enum Kind { Default = 0x0, Direct = 0x1 };
45	private:
46	enum { Symbolic = 0x2 };
47
48	llvm::PointerIntPair<const MemRegion *, 2> P;
49	uint64_t Data;
50
51	/// Create a key for a binding to region \p r, which has a symbolic offset
52	/// from region \p Base.
53	explicit BindingKey(const SubRegion r, const SubRegion Base, Kind k)
54	: P(r, k \| Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) {
55	(0) . __assert_fail ("r && Base && \"Must have known regions.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 55, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(r && Base && "Must have known regions.");
56	(0) . __assert_fail ("getConcreteOffsetRegion() == Base && \"Failed to store base region\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 56, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(getConcreteOffsetRegion() == Base && "Failed to store base region");
57	}
58
59	/// Create a key for a binding at \p offset from base region \p r.
60	explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k)
61	: P(r, k), Data(offset) {
62	(0) . __assert_fail ("r && \"Must have known regions.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 62, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(r && "Must have known regions.");
63	(0) . __assert_fail ("getOffset() == offset && \"Failed to store offset\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 63, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(getOffset() == offset && "Failed to store offset");
64	(0) . __assert_fail ("(r == r->getBaseRegion() \|\| isa(r) \|\| isa (r)) && \"Not a base\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 66, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert((r == r->getBaseRegion() \|\| isa<ObjCIvarRegion>(r) \|\|
65	(0) . __assert_fail ("(r == r->getBaseRegion() \|\| isa(r) \|\| isa (r)) && \"Not a base\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 66, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> isa <CXXDerivedObjectRegion>(r)) &&
66	(0) . __assert_fail ("(r == r->getBaseRegion() \|\| isa(r) \|\| isa (r)) && \"Not a base\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 66, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Not a base");
67	}
68	public:
69
70	bool isDirect() const { return P.getInt() & Direct; }
71	bool hasSymbolicOffset() const { return P.getInt() & Symbolic; }
72
73	const MemRegion *getRegion() const { return P.getPointer(); }
74	uint64_t getOffset() const {
75	assert(!hasSymbolicOffset());
76	return Data;
77	}
78
79	const SubRegion *getConcreteOffsetRegion() const {
80	assert(hasSymbolicOffset());
81	return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data));
82	}
83
84	const MemRegion *getBaseRegion() const {
85	if (hasSymbolicOffset())
86	return getConcreteOffsetRegion()->getBaseRegion();
87	return getRegion()->getBaseRegion();
88	}
89
90	void Profile(llvm::FoldingSetNodeID& ID) const {
91	ID.AddPointer(P.getOpaqueValue());
92	ID.AddInteger(Data);
93	}
94
95	static BindingKey Make(const MemRegion *R, Kind k);
96
97	bool operator<(const BindingKey &X) const {
98	if (P.getOpaqueValue() < X.P.getOpaqueValue())
99	return true;
100	if (P.getOpaqueValue() > X.P.getOpaqueValue())
101	return false;
102	return Data < X.Data;
103	}
104
105	bool operator==(const BindingKey &X) const {
106	return P.getOpaqueValue() == X.P.getOpaqueValue() &&
107	Data == X.Data;
108	}
109
110	void dump() const;
111	};
112	} // end anonymous namespace
113
114	BindingKey BindingKey::Make(const MemRegion *R, Kind k) {
115	const RegionOffset &RO = R->getAsOffset();
116	if (RO.hasSymbolicOffset())
117	return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k);
118
119	return BindingKey(RO.getRegion(), RO.getOffset(), k);
120	}
121
122	namespace llvm {
123	static inline
124	raw_ostream &operator<<(raw_ostream &os, BindingKey K) {
125	os << '(' << K.getRegion();
126	if (!K.hasSymbolicOffset())
127	os << ',' << K.getOffset();
128	os << ',' << (K.isDirect() ? "direct" : "default")
129	<< ')';
130	return os;
131	}
132
133	} // end llvm namespace
134
135	#ifndef NDEBUG
136	LLVM_DUMP_METHOD void BindingKey::dump() const { llvm::errs() << *this; }
137	#endif
138
139	//===----------------------------------------------------------------------===//
140	// Actual Store type.
141	//===----------------------------------------------------------------------===//
142
143	typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings;
144	typedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef;
145	typedef std::pair<BindingKey, SVal> BindingPair;
146
147	typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings>
148	RegionBindings;
149
150	namespace {
151	class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *,
152	ClusterBindings> {
153	ClusterBindings::Factory *CBFactory;
154
155	public:
156	typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>
157	ParentTy;
158
159	RegionBindingsRef(ClusterBindings::Factory &CBFactory,
160	const RegionBindings::TreeTy *T,
161	RegionBindings::TreeTy::Factory *F)
162	: llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(T, F),
163	CBFactory(&CBFactory) {}
164
165	RegionBindingsRef(const ParentTy &P, ClusterBindings::Factory &CBFactory)
166	: llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>(P),
167	CBFactory(&CBFactory) {}
168
169	RegionBindingsRef add(key_type_ref K, data_type_ref D) const {
170	return RegionBindingsRef(static_cast<const ParentTy *>(this)->add(K, D),
171	*CBFactory);
172	}
173
174	RegionBindingsRef remove(key_type_ref K) const {
175	return RegionBindingsRef(static_cast<const ParentTy *>(this)->remove(K),
176	*CBFactory);
177	}
178
179	RegionBindingsRef addBinding(BindingKey K, SVal V) const;
180
181	RegionBindingsRef addBinding(const MemRegion *R,
182	BindingKey::Kind k, SVal V) const;
183
184	const SVal *lookup(BindingKey K) const;
185	const SVal lookup(const MemRegion R, BindingKey::Kind k) const;
186	using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup;
187
188	RegionBindingsRef removeBinding(BindingKey K);
189
190	RegionBindingsRef removeBinding(const MemRegion *R,
191	BindingKey::Kind k);
192
193	RegionBindingsRef removeBinding(const MemRegion *R) {
194	return removeBinding(R, BindingKey::Direct).
195	removeBinding(R, BindingKey::Default);
196	}
197
198	Optional<SVal> getDirectBinding(const MemRegion *R) const;
199
200	/// getDefaultBinding - Returns an SVal* representing an optional default
201	/// binding associated with a region and its subregions.
202	Optional<SVal> getDefaultBinding(const MemRegion *R) const;
203
204	/// Return the internal tree as a Store.
205	Store asStore() const {
206	return asImmutableMap().getRootWithoutRetain();
207	}
208
209	void dump(raw_ostream &OS, const char *nl) const {
210	for (iterator I = begin(), E = end(); I != E; ++I) {
211	const ClusterBindings &Cluster = I.getData();
212	for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
213	CI != CE; ++CI) {
214	OS << ' ' << CI.getKey() << " : " << CI.getData() << nl;
215	}
216	OS << nl;
217	}
218	}
219
220	LLVM_DUMP_METHOD void dump() const { dump(llvm::errs(), "\n"); }
221	};
222	} // end anonymous namespace
223
224	typedef const RegionBindingsRef& RegionBindingsConstRef;
225
226	Optional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const {
227	return Optional<SVal>::create(lookup(R, BindingKey::Direct));
228	}
229
230	Optional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const {
231	return Optional<SVal>::create(lookup(R, BindingKey::Default));
232	}
233
234	RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const {
235	const MemRegion *Base = K.getBaseRegion();
236
237	const ClusterBindings *ExistingCluster = lookup(Base);
238	ClusterBindings Cluster =
239	(ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap());
240
241	ClusterBindings NewCluster = CBFactory->add(Cluster, K, V);
242	return add(Base, NewCluster);
243	}
244
245
246	RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R,
247	BindingKey::Kind k,
248	SVal V) const {
249	return addBinding(BindingKey::Make(R, k), V);
250	}
251
252	const SVal *RegionBindingsRef::lookup(BindingKey K) const {
253	const ClusterBindings *Cluster = lookup(K.getBaseRegion());
254	if (!Cluster)
255	return nullptr;
256	return Cluster->lookup(K);
257	}
258
259	const SVal RegionBindingsRef::lookup(const MemRegion R,
260	BindingKey::Kind k) const {
261	return lookup(BindingKey::Make(R, k));
262	}
263
264	RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) {
265	const MemRegion *Base = K.getBaseRegion();
266	const ClusterBindings *Cluster = lookup(Base);
267	if (!Cluster)
268	return *this;
269
270	ClusterBindings NewCluster = CBFactory->remove(*Cluster, K);
271	if (NewCluster.isEmpty())
272	return remove(Base);
273	return add(Base, NewCluster);
274	}
275
276	RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R,
277	BindingKey::Kind k){
278	return removeBinding(BindingKey::Make(R, k));
279	}
280
281	//===----------------------------------------------------------------------===//
282	// Fine-grained control of RegionStoreManager.
283	//===----------------------------------------------------------------------===//
284
285	namespace {
286	struct minimal_features_tag {};
287	struct maximal_features_tag {};
288
289	class RegionStoreFeatures {
290	bool SupportsFields;
291	public:
292	RegionStoreFeatures(minimal_features_tag) :
293	SupportsFields(false) {}
294
295	RegionStoreFeatures(maximal_features_tag) :
296	SupportsFields(true) {}
297
298	void enableFields(bool t) { SupportsFields = t; }
299
300	bool supportsFields() const { return SupportsFields; }
301	};
302	}
303
304	//===----------------------------------------------------------------------===//
305	// Main RegionStore logic.
306	//===----------------------------------------------------------------------===//
307
308	namespace {
309	class InvalidateRegionsWorker;
310
311	class RegionStoreManager : public StoreManager {
312	public:
313	const RegionStoreFeatures Features;
314
315	RegionBindings::Factory RBFactory;
316	mutable ClusterBindings::Factory CBFactory;
317
318	typedef std::vector<SVal> SValListTy;
319	private:
320	typedef llvm::DenseMap<const LazyCompoundValData *,
321	SValListTy> LazyBindingsMapTy;
322	LazyBindingsMapTy LazyBindingsMap;
323
324	/// The largest number of fields a struct can have and still be
325	/// considered "small".
326	///
327	/// This is currently used to decide whether or not it is worth "forcing" a
328	/// LazyCompoundVal on bind.
329	///
330	/// This is controlled by 'region-store-small-struct-limit' option.
331	/// To disable all small-struct-dependent behavior, set the option to "0".
332	unsigned SmallStructLimit;
333
334	/// A helper used to populate the work list with the given set of
335	/// regions.
336	void populateWorkList(InvalidateRegionsWorker &W,
337	ArrayRef<SVal> Values,
338	InvalidatedRegions *TopLevelRegions);
339
340	public:
341	RegionStoreManager(ProgramStateManager& mgr, const RegionStoreFeatures &f)
342	: StoreManager(mgr), Features(f),
343	RBFactory(mgr.getAllocator()), CBFactory(mgr.getAllocator()),
344	SmallStructLimit(0) {
345	SubEngine &Eng = StateMgr.getOwningEngine();
346	AnalyzerOptions &Options = Eng.getAnalysisManager().options;
347	SmallStructLimit = Options.RegionStoreSmallStructLimit;
348	}
349
350
351	/// setImplicitDefaultValue - Set the default binding for the provided
352	/// MemRegion to the value implicitly defined for compound literals when
353	/// the value is not specified.
354	RegionBindingsRef setImplicitDefaultValue(RegionBindingsConstRef B,
355	const MemRegion *R, QualType T);
356
357	/// ArrayToPointer - Emulates the "decay" of an array to a pointer
358	/// type. 'Array' represents the lvalue of the array being decayed
359	/// to a pointer, and the returned SVal represents the decayed
360	/// version of that lvalue (i.e., a pointer to the first element of
361	/// the array). This is called by ExprEngine when evaluating
362	/// casts from arrays to pointers.
363	SVal ArrayToPointer(Loc Array, QualType ElementTy) override;
364
365	StoreRef getInitialStore(const LocationContext *InitLoc) override {
366	return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this);
367	}
368
369	//===-------------------------------------------------------------------===//
370	// Binding values to regions.
371	//===-------------------------------------------------------------------===//
372	RegionBindingsRef invalidateGlobalRegion(MemRegion::Kind K,
373	const Expr *Ex,
374	unsigned Count,
375	const LocationContext *LCtx,
376	RegionBindingsRef B,
377	InvalidatedRegions *Invalidated);
378
379	StoreRef invalidateRegions(Store store,
380	ArrayRef<SVal> Values,
381	const Expr *E, unsigned Count,
382	const LocationContext *LCtx,
383	const CallEvent *Call,
384	InvalidatedSymbols &IS,
385	RegionAndSymbolInvalidationTraits &ITraits,
386	InvalidatedRegions *Invalidated,
387	InvalidatedRegions *InvalidatedTopLevel) override;
388
389	bool scanReachableSymbols(Store S, const MemRegion *R,
390	ScanReachableSymbols &Callbacks) override;
391
392	RegionBindingsRef removeSubRegionBindings(RegionBindingsConstRef B,
393	const SubRegion *R);
394
395	public: // Part of public interface to class.
396
397	StoreRef Bind(Store store, Loc LV, SVal V) override {
398	return StoreRef(bind(getRegionBindings(store), LV, V).asStore(), *this);
399	}
400
401	RegionBindingsRef bind(RegionBindingsConstRef B, Loc LV, SVal V);
402
403	// BindDefaultInitial is only used to initialize a region with
404	// a default value.
405	StoreRef BindDefaultInitial(Store store, const MemRegion *R,
406	SVal V) override {
407	RegionBindingsRef B = getRegionBindings(store);
408	// Use other APIs when you have to wipe the region that was initialized
409	// earlier.
410	(0) . __assert_fail ("!(B.getDefaultBinding(R) \|\| B.getDirectBinding(R)) && \"Double initialization!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 411, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!(B.getDefaultBinding(R) \|\| B.getDirectBinding(R)) &&
411	(0) . __assert_fail ("!(B.getDefaultBinding(R) \|\| B.getDirectBinding(R)) && \"Double initialization!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 411, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Double initialization!");
412	B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V);
413	return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this);
414	}
415
416	// BindDefaultZero is used for zeroing constructors that may accidentally
417	// overwrite existing bindings.
418	StoreRef BindDefaultZero(Store store, const MemRegion *R) override {
419	// FIXME: The offsets of empty bases can be tricky because of
420	// of the so called "empty base class optimization".
421	// If a base class has been optimized out
422	// we should not try to create a binding, otherwise we should.
423	// Unfortunately, at the moment ASTRecordLayout doesn't expose
424	// the actual sizes of the empty bases
425	// and trying to infer them from offsets/alignments
426	// seems to be error-prone and non-trivial because of the trailing padding.
427	// As a temporary mitigation we don't create bindings for empty bases.
428	if (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R))
429	if (BR->getDecl()->isEmpty())
430	return StoreRef(store, *this);
431
432	RegionBindingsRef B = getRegionBindings(store);
433	SVal V = svalBuilder.makeZeroVal(Ctx.CharTy);
434	B = removeSubRegionBindings(B, cast<SubRegion>(R));
435	B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V);
436	return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this);
437	}
438
439	/// Attempt to extract the fields of \p LCV and bind them to the struct region
440	/// \p R.
441	///
442	/// This path is used when it seems advantageous to "force" loading the values
443	/// within a LazyCompoundVal to bind memberwise to the struct region, rather
444	/// than using a Default binding at the base of the entire region. This is a
445	/// heuristic attempting to avoid building long chains of LazyCompoundVals.
446	///
447	/// \returns The updated store bindings, or \c None if binding non-lazily
448	/// would be too expensive.
449	Optional<RegionBindingsRef> tryBindSmallStruct(RegionBindingsConstRef B,
450	const TypedValueRegion *R,
451	const RecordDecl *RD,
452	nonloc::LazyCompoundVal LCV);
453
454	/// BindStruct - Bind a compound value to a structure.
455	RegionBindingsRef bindStruct(RegionBindingsConstRef B,
456	const TypedValueRegion* R, SVal V);
457
458	/// BindVector - Bind a compound value to a vector.
459	RegionBindingsRef bindVector(RegionBindingsConstRef B,
460	const TypedValueRegion* R, SVal V);
461
462	RegionBindingsRef bindArray(RegionBindingsConstRef B,
463	const TypedValueRegion* R,
464	SVal V);
465
466	/// Clears out all bindings in the given region and assigns a new value
467	/// as a Default binding.
468	RegionBindingsRef bindAggregate(RegionBindingsConstRef B,
469	const TypedRegion *R,
470	SVal DefaultVal);
471
472	/// Create a new store with the specified binding removed.
473	/// \param ST the original store, that is the basis for the new store.
474	/// \param L the location whose binding should be removed.
475	StoreRef killBinding(Store ST, Loc L) override;
476
477	void incrementReferenceCount(Store store) override {
478	getRegionBindings(store).manualRetain();
479	}
480
481	/// If the StoreManager supports it, decrement the reference count of
482	/// the specified Store object. If the reference count hits 0, the memory
483	/// associated with the object is recycled.
484	void decrementReferenceCount(Store store) override {
485	getRegionBindings(store).manualRelease();
486	}
487
488	bool includedInBindings(Store store, const MemRegion *region) const override;
489
490	/// Return the value bound to specified location in a given state.
491	///
492	/// The high level logic for this method is this:
493	/// getBinding (L)
494	/// if L has binding
495	/// return L's binding
496	/// else if L is in killset
497	/// return unknown
498	/// else
499	/// if L is on stack or heap
500	/// return undefined
501	/// else
502	/// return symbolic
503	SVal getBinding(Store S, Loc L, QualType T) override {
504	return getBinding(getRegionBindings(S), L, T);
505	}
506
507	Optional<SVal> getDefaultBinding(Store S, const MemRegion *R) override {
508	RegionBindingsRef B = getRegionBindings(S);
509	// Default bindings are always applied over a base region so look up the
510	// base region's default binding, otherwise the lookup will fail when R
511	// is at an offset from R->getBaseRegion().
512	return B.getDefaultBinding(R->getBaseRegion());
513	}
514
515	SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType());
516
517	SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R);
518
519	SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R);
520
521	SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R);
522
523	SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R);
524
525	SVal getBindingForLazySymbol(const TypedValueRegion *R);
526
527	SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
528	const TypedValueRegion *R,
529	QualType Ty);
530
531	SVal getLazyBinding(const SubRegion *LazyBindingRegion,
532	RegionBindingsRef LazyBinding);
533
534	/// Get bindings for the values in a struct and return a CompoundVal, used
535	/// when doing struct copy:
536	/// struct s x, y;
537	/// x = y;
538	/// y's value is retrieved by this method.
539	SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R);
540	SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R);
541	NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R);
542
543	/// Used to lazily generate derived symbols for bindings that are defined
544	/// implicitly by default bindings in a super region.
545	///
546	/// Note that callers may need to specially handle LazyCompoundVals, which
547	/// are returned as is in case the caller needs to treat them differently.
548	Optional<SVal> getBindingForDerivedDefaultValue(RegionBindingsConstRef B,
549	const MemRegion *superR,
550	const TypedValueRegion *R,
551	QualType Ty);
552
553	/// Get the state and region whose binding this region \p R corresponds to.
554	///
555	/// If there is no lazy binding for \p R, the returned value will have a null
556	/// \c second. Note that a null pointer can represents a valid Store.
557	std::pair<Store, const SubRegion *>
558	findLazyBinding(RegionBindingsConstRef B, const SubRegion *R,
559	const SubRegion *originalRegion);
560
561	/// Returns the cached set of interesting SVals contained within a lazy
562	/// binding.
563	///
564	/// The precise value of "interesting" is determined for the purposes of
565	/// RegionStore's internal analysis. It must always contain all regions and
566	/// symbols, but may omit constants and other kinds of SVal.
567	const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV);
568
569	//===------------------------------------------------------------------===//
570	// State pruning.
571	//===------------------------------------------------------------------===//
572
573	/// removeDeadBindings - Scans the RegionStore of 'state' for dead values.
574	/// It returns a new Store with these values removed.
575	StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
576	SymbolReaper& SymReaper) override;
577
578	//===------------------------------------------------------------------===//
579	// Region "extents".
580	//===------------------------------------------------------------------===//
581
582	// FIXME: This method will soon be eliminated; see the note in Store.h.
583	DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state,
584	const MemRegion* R,
585	QualType EleTy) override;
586
587	//===------------------------------------------------------------------===//
588	// Utility methods.
589	//===------------------------------------------------------------------===//
590
591	RegionBindingsRef getRegionBindings(Store store) const {
592	return RegionBindingsRef(CBFactory,
593	static_cast<const RegionBindings::TreeTy*>(store),
594	RBFactory.getTreeFactory());
595	}
596
597	void print(Store store, raw_ostream &Out, const char* nl) override;
598
599	void iterBindings(Store store, BindingsHandler& f) override {
600	RegionBindingsRef B = getRegionBindings(store);
601	for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) {
602	const ClusterBindings &Cluster = I.getData();
603	for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
604	CI != CE; ++CI) {
605	const BindingKey &K = CI.getKey();
606	if (!K.isDirect())
607	continue;
608	if (const SubRegion *R = dyn_cast<SubRegion>(K.getRegion())) {
609	// FIXME: Possibly incorporate the offset?
610	if (!f.HandleBinding(*this, store, R, CI.getData()))
611	return;
612	}
613	}
614	}
615	}
616	};
617
618	} // end anonymous namespace
619
620	//===----------------------------------------------------------------------===//
621	// RegionStore creation.
622	//===----------------------------------------------------------------------===//
623
624	std::unique_ptr<StoreManager>
625	ento::CreateRegionStoreManager(ProgramStateManager &StMgr) {
626	RegionStoreFeatures F = maximal_features_tag();
627	return llvm::make_unique<RegionStoreManager>(StMgr, F);
628	}
629
630	std::unique_ptr<StoreManager>
631	ento::CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr) {
632	RegionStoreFeatures F = minimal_features_tag();
633	F.enableFields(true);
634	return llvm::make_unique<RegionStoreManager>(StMgr, F);
635	}
636
637
638	//===----------------------------------------------------------------------===//
639	// Region Cluster analysis.
640	//===----------------------------------------------------------------------===//
641
642	namespace {
643	/// Used to determine which global regions are automatically included in the
644	/// initial worklist of a ClusterAnalysis.
645	enum GlobalsFilterKind {
646	/// Don't include any global regions.
647	GFK_None,
648	/// Only include system globals.
649	GFK_SystemOnly,
650	/// Include all global regions.
651	GFK_All
652	};
653
654	template <typename DERIVED>
655	class ClusterAnalysis {
656	protected:
657	typedef llvm::DenseMap<const MemRegion , const ClusterBindings > ClusterMap;
658	typedef const MemRegion * WorkListElement;
659	typedef SmallVector<WorkListElement, 10> WorkList;
660
661	llvm::SmallPtrSet<const ClusterBindings *, 16> Visited;
662
663	WorkList WL;
664
665	RegionStoreManager &RM;
666	ASTContext &Ctx;
667	SValBuilder &svalBuilder;
668
669	RegionBindingsRef B;
670
671
672	protected:
673	const ClusterBindings getCluster(const MemRegion R) {
674	return B.lookup(R);
675	}
676
677	/// Returns true if all clusters in the given memspace should be initially
678	/// included in the cluster analysis. Subclasses may provide their
679	/// own implementation.
680	bool includeEntireMemorySpace(const MemRegion *Base) {
681	return false;
682	}
683
684	public:
685	ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
686	RegionBindingsRef b)
687	: RM(rm), Ctx(StateMgr.getContext()),
688	svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {}
689
690	RegionBindingsRef getRegionBindings() const { return B; }
691
692	bool isVisited(const MemRegion *R) {
693	return Visited.count(getCluster(R));
694	}
695
696	void GenerateClusters() {
697	// Scan the entire set of bindings and record the region clusters.
698	for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end();
699	RI != RE; ++RI){
700	const MemRegion *Base = RI.getKey();
701
702	const ClusterBindings &Cluster = RI.getData();
703	(0) . __assert_fail ("!Cluster.isEmpty() && \"Empty clusters should be removed\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 703, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!Cluster.isEmpty() && "Empty clusters should be removed");
704	static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster);
705
706	// If the base's memspace should be entirely invalidated, add the cluster
707	// to the workspace up front.
708	if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base))
709	AddToWorkList(WorkListElement(Base), &Cluster);
710	}
711	}
712
713	bool AddToWorkList(WorkListElement E, const ClusterBindings *C) {
714	if (C && !Visited.insert(C).second)
715	return false;
716	WL.push_back(E);
717	return true;
718	}
719
720	bool AddToWorkList(const MemRegion *R) {
721	return static_cast<DERIVED*>(this)->AddToWorkList(R);
722	}
723
724	void RunWorkList() {
725	while (!WL.empty()) {
726	WorkListElement E = WL.pop_back_val();
727	const MemRegion *BaseR = E;
728
729	static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR));
730	}
731	}
732
733	void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {}
734	void VisitCluster(const MemRegion baseR, const ClusterBindings C) {}
735
736	void VisitCluster(const MemRegion BaseR, const ClusterBindings C,
737	bool Flag) {
738	static_cast<DERIVED*>(this)->VisitCluster(BaseR, C);
739	}
740	};
741	}
742
743	//===----------------------------------------------------------------------===//
744	// Binding invalidation.
745	//===----------------------------------------------------------------------===//
746
747	bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R,
748	ScanReachableSymbols &Callbacks) {
749	(0) . __assert_fail ("R == R->getBaseRegion() && \"Should only be called for base regions\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 749, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(R == R->getBaseRegion() && "Should only be called for base regions");
750	RegionBindingsRef B = getRegionBindings(S);
751	const ClusterBindings *Cluster = B.lookup(R);
752
753	if (!Cluster)
754	return true;
755
756	for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end();
757	RI != RE; ++RI) {
758	if (!Callbacks.scan(RI.getData()))
759	return false;
760	}
761
762	return true;
763	}
764
765	static inline bool isUnionField(const FieldRegion *FR) {
766	return FR->getDecl()->getParent()->isUnion();
767	}
768
769	typedef SmallVector<const FieldDecl *, 8> FieldVector;
770
771	static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) {
772	(0) . __assert_fail ("K.hasSymbolicOffset() && \"Not implemented for concrete offset keys\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 772, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");
773
774	const MemRegion *Base = K.getConcreteOffsetRegion();
775	const MemRegion *R = K.getRegion();
776
777	while (R != Base) {
778	if (const FieldRegion *FR = dyn_cast<FieldRegion>(R))
779	if (!isUnionField(FR))
780	Fields.push_back(FR->getDecl());
781
782	R = cast<SubRegion>(R)->getSuperRegion();
783	}
784	}
785
786	static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) {
787	(0) . __assert_fail ("K.hasSymbolicOffset() && \"Not implemented for concrete offset keys\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 787, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");
788
789	if (Fields.empty())
790	return true;
791
792	FieldVector FieldsInBindingKey;
793	getSymbolicOffsetFields(K, FieldsInBindingKey);
794
795	ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size();
796	if (Delta >= 0)
797	return std::equal(FieldsInBindingKey.begin() + Delta,
798	FieldsInBindingKey.end(),
799	Fields.begin());
800	else
801	return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(),
802	Fields.begin() - Delta);
803	}
804
805	/// Collects all bindings in \p Cluster that may refer to bindings within
806	/// \p Top.
807	///
808	/// Each binding is a pair whose \c first is the key (a BindingKey) and whose
809	/// \c second is the value (an SVal).
810	///
811	/// The \p IncludeAllDefaultBindings parameter specifies whether to include
812	/// default bindings that may extend beyond \p Top itself, e.g. if \p Top is
813	/// an aggregate within a larger aggregate with a default binding.
814	static void
815	collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings,
816	SValBuilder &SVB, const ClusterBindings &Cluster,
817	const SubRegion *Top, BindingKey TopKey,
818	bool IncludeAllDefaultBindings) {
819	FieldVector FieldsInSymbolicSubregions;
820	if (TopKey.hasSymbolicOffset()) {
821	getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions);
822	Top = TopKey.getConcreteOffsetRegion();
823	TopKey = BindingKey::Make(Top, BindingKey::Default);
824	}
825
826	// Find the length (in bits) of the region being invalidated.
827	uint64_t Length = UINT64_MAX;
828	SVal Extent = Top->getExtent(SVB);
829	if (Optional<nonloc::ConcreteInt> ExtentCI =
830	Extent.getAs<nonloc::ConcreteInt>()) {
831	const llvm::APSInt &ExtentInt = ExtentCI->getValue();
832	assert(ExtentInt.isNonNegative() \|\| ExtentInt.isUnsigned());
833	// Extents are in bytes but region offsets are in bits. Be careful!
834	Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth();
835	} else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) {
836	if (FR->getDecl()->isBitField())
837	Length = FR->getDecl()->getBitWidthValue(SVB.getContext());
838	}
839
840	for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end();
841	I != E; ++I) {
842	BindingKey NextKey = I.getKey();
843	if (NextKey.getRegion() == TopKey.getRegion()) {
844	// FIXME: This doesn't catch the case where we're really invalidating a
845	// region with a symbolic offset. Example:
846	// R: points[i].y
847	// Next: points[0].x
848
849	if (NextKey.getOffset() > TopKey.getOffset() &&
850	NextKey.getOffset() - TopKey.getOffset() < Length) {
851	// Case 1: The next binding is inside the region we're invalidating.
852	// Include it.
853	Bindings.push_back(*I);
854
855	} else if (NextKey.getOffset() == TopKey.getOffset()) {
856	// Case 2: The next binding is at the same offset as the region we're
857	// invalidating. In this case, we need to leave default bindings alone,
858	// since they may be providing a default value for a regions beyond what
859	// we're invalidating.
860	// FIXME: This is probably incorrect; consider invalidating an outer
861	// struct whose first field is bound to a LazyCompoundVal.
862	if (IncludeAllDefaultBindings \|\| NextKey.isDirect())
863	Bindings.push_back(*I);
864	}
865
866	} else if (NextKey.hasSymbolicOffset()) {
867	const MemRegion *Base = NextKey.getConcreteOffsetRegion();
868	if (Top->isSubRegionOf(Base) && Top != Base) {
869	// Case 3: The next key is symbolic and we just changed something within
870	// its concrete region. We don't know if the binding is still valid, so
871	// we'll be conservative and include it.
872	if (IncludeAllDefaultBindings \|\| NextKey.isDirect())
873	if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
874	Bindings.push_back(*I);
875	} else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) {
876	// Case 4: The next key is symbolic, but we changed a known
877	// super-region. In this case the binding is certainly included.
878	if (BaseSR->isSubRegionOf(Top))
879	if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
880	Bindings.push_back(*I);
881	}
882	}
883	}
884	}
885
886	static void
887	collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings,
888	SValBuilder &SVB, const ClusterBindings &Cluster,
889	const SubRegion *Top, bool IncludeAllDefaultBindings) {
890	collectSubRegionBindings(Bindings, SVB, Cluster, Top,
891	BindingKey::Make(Top, BindingKey::Default),
892	IncludeAllDefaultBindings);
893	}
894
895	RegionBindingsRef
896	RegionStoreManager::removeSubRegionBindings(RegionBindingsConstRef B,
897	const SubRegion *Top) {
898	BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default);
899	const MemRegion *ClusterHead = TopKey.getBaseRegion();
900
901	if (Top == ClusterHead) {
902	// We can remove an entire cluster's bindings all in one go.
903	return B.remove(Top);
904	}
905
906	const ClusterBindings *Cluster = B.lookup(ClusterHead);
907	if (!Cluster) {
908	// If we're invalidating a region with a symbolic offset, we need to make
909	// sure we don't treat the base region as uninitialized anymore.
910	if (TopKey.hasSymbolicOffset()) {
911	const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
912	return B.addBinding(Concrete, BindingKey::Default, UnknownVal());
913	}
914	return B;
915	}
916
917	SmallVector<BindingPair, 32> Bindings;
918	collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey,
919	/IncludeAllDefaultBindings=/false);
920
921	ClusterBindingsRef Result(*Cluster, CBFactory);
922	for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(),
923	E = Bindings.end();
924	I != E; ++I)
925	Result = Result.remove(I->first);
926
927	// If we're invalidating a region with a symbolic offset, we need to make sure
928	// we don't treat the base region as uninitialized anymore.
929	// FIXME: This isn't very precise; see the example in
930	// collectSubRegionBindings.
931	if (TopKey.hasSymbolicOffset()) {
932	const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
933	Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default),
934	UnknownVal());
935	}
936
937	if (Result.isEmpty())
938	return B.remove(ClusterHead);
939	return B.add(ClusterHead, Result.asImmutableMap());
940	}
941
942	namespace {
943	class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker>
944	{
945	const Expr *Ex;
946	unsigned Count;
947	const LocationContext *LCtx;
948	InvalidatedSymbols &IS;
949	RegionAndSymbolInvalidationTraits &ITraits;
950	StoreManager::InvalidatedRegions *Regions;
951	GlobalsFilterKind GlobalsFilter;
952	public:
953	InvalidateRegionsWorker(RegionStoreManager &rm,
954	ProgramStateManager &stateMgr,
955	RegionBindingsRef b,
956	const Expr *ex, unsigned count,
957	const LocationContext *lctx,
958	InvalidatedSymbols &is,
959	RegionAndSymbolInvalidationTraits &ITraitsIn,
960	StoreManager::InvalidatedRegions *r,
961	GlobalsFilterKind GFK)
962	: ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b),
963	Ex(ex), Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r),
964	GlobalsFilter(GFK) {}
965
966	void VisitCluster(const MemRegion baseR, const ClusterBindings C);
967	void VisitBinding(SVal V);
968
969	using ClusterAnalysis::AddToWorkList;
970
971	bool AddToWorkList(const MemRegion *R);
972
973	/// Returns true if all clusters in the memory space for \p Base should be
974	/// be invalidated.
975	bool includeEntireMemorySpace(const MemRegion *Base);
976
977	/// Returns true if the memory space of the given region is one of the global
978	/// regions specially included at the start of invalidation.
979	bool isInitiallyIncludedGlobalRegion(const MemRegion *R);
980	};
981	}
982
983	bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) {
984	bool doNotInvalidateSuperRegion = ITraits.hasTrait(
985	R, RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);
986	const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion();
987	return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
988	}
989
990	void InvalidateRegionsWorker::VisitBinding(SVal V) {
991	// A symbol? Mark it touched by the invalidation.
992	if (SymbolRef Sym = V.getAsSymbol())
993	IS.insert(Sym);
994
995	if (const MemRegion *R = V.getAsRegion()) {
996	AddToWorkList(R);
997	return;
998	}
999
1000	// Is it a LazyCompoundVal? All references get invalidated as well.
1001	if (Optional<nonloc::LazyCompoundVal> LCS =
1002	V.getAs<nonloc::LazyCompoundVal>()) {
1003
1004	const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS);
1005
1006	for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(),
1007	E = Vals.end();
1008	I != E; ++I)
1009	VisitBinding(*I);
1010
1011	return;
1012	}
1013	}
1014
1015	void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
1016	const ClusterBindings *C) {
1017
1018	bool PreserveRegionsContents =
1019	ITraits.hasTrait(baseR,
1020	RegionAndSymbolInvalidationTraits::TK_PreserveContents);
1021
1022	if (C) {
1023	for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
1024	VisitBinding(I.getData());
1025
1026	// Invalidate regions contents.
1027	if (!PreserveRegionsContents)
1028	B = B.remove(baseR);
1029	}
1030
1031	if (const auto *TO = dyn_cast<TypedValueRegion>(baseR)) {
1032	if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) {
1033
1034	// Lambdas can affect all static local variables without explicitly
1035	// capturing those.
1036	// We invalidate all static locals referenced inside the lambda body.
1037	if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) {
1038	using namespace ast_matchers;
1039
1040	const char *DeclBind = "DeclBind";
1041	StatementMatcher RefToStatic = stmt(hasDescendant(declRefExpr(
1042	to(varDecl(hasStaticStorageDuration()).bind(DeclBind)))));
1043	auto Matches =
1044	match(RefToStatic, *RD->getLambdaCallOperator()->getBody(),
1045	RD->getASTContext());
1046
1047	for (BoundNodes &Match : Matches) {
1048	auto *VD = Match.getNodeAs<VarDecl>(DeclBind);
1049	const VarRegion *ToInvalidate =
1050	RM.getRegionManager().getVarRegion(VD, LCtx);
1051	AddToWorkList(ToInvalidate);
1052	}
1053	}
1054	}
1055	}
1056
1057	// BlockDataRegion? If so, invalidate captured variables that are passed
1058	// by reference.
1059	if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
1060	for (BlockDataRegion::referenced_vars_iterator
1061	BI = BR->referenced_vars_begin(), BE = BR->referenced_vars_end() ;
1062	BI != BE; ++BI) {
1063	const VarRegion *VR = BI.getCapturedRegion();
1064	const VarDecl *VD = VR->getDecl();
1065	if (VD->hasAttr<BlocksAttr>() \|\| !VD->hasLocalStorage()) {
1066	AddToWorkList(VR);
1067	}
1068	else if (Loc::isLocType(VR->getValueType())) {
1069	// Map the current bindings to a Store to retrieve the value
1070	// of the binding. If that binding itself is a region, we should
1071	// invalidate that region. This is because a block may capture
1072	// a pointer value, but the thing pointed by that pointer may
1073	// get invalidated.
1074	SVal V = RM.getBinding(B, loc::MemRegionVal(VR));
1075	if (Optional<Loc> L = V.getAs<Loc>()) {
1076	if (const MemRegion *LR = L->getAsRegion())
1077	AddToWorkList(LR);
1078	}
1079	}
1080	}
1081	return;
1082	}
1083
1084	// Symbolic region?
1085	if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
1086	IS.insert(SR->getSymbol());
1087
1088	// Nothing else should be done in the case when we preserve regions context.
1089	if (PreserveRegionsContents)
1090	return;
1091
1092	// Otherwise, we have a normal data region. Record that we touched the region.
1093	if (Regions)
1094	Regions->push_back(baseR);
1095
1096	if (isa<AllocaRegion>(baseR) \|\| isa<SymbolicRegion>(baseR)) {
1097	// Invalidate the region by setting its default value to
1098	// conjured symbol. The type of the symbol is irrelevant.
1099	DefinedOrUnknownSVal V =
1100	svalBuilder.conjureSymbolVal(baseR, Ex, LCtx, Ctx.IntTy, Count);
1101	B = B.addBinding(baseR, BindingKey::Default, V);
1102	return;
1103	}
1104
1105	if (!baseR->isBoundable())
1106	return;
1107
1108	const TypedValueRegion *TR = cast<TypedValueRegion>(baseR);
1109	QualType T = TR->getValueType();
1110
1111	if (isInitiallyIncludedGlobalRegion(baseR)) {
1112	// If the region is a global and we are invalidating all globals,
1113	// erasing the entry is good enough. This causes all globals to be lazily
1114	// symbolicated from the same base symbol.
1115	return;
1116	}
1117
1118	if (T->isRecordType()) {
1119	// Invalidate the region by setting its default value to
1120	// conjured symbol. The type of the symbol is irrelevant.
1121	DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
1122	Ctx.IntTy, Count);
1123	B = B.addBinding(baseR, BindingKey::Default, V);
1124	return;
1125	}
1126
1127	if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
1128	bool doNotInvalidateSuperRegion = ITraits.hasTrait(
1129	baseR,
1130	RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);
1131
1132	if (doNotInvalidateSuperRegion) {
1133	// We are not doing blank invalidation of the whole array region so we
1134	// have to manually invalidate each elements.
1135	Optional<uint64_t> NumElements;
1136
1137	// Compute lower and upper offsets for region within array.
1138	if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT))
1139	NumElements = CAT->getSize().getZExtValue();
1140	if (!NumElements) // We are not dealing with a constant size array
1141	goto conjure_default;
1142	QualType ElementTy = AT->getElementType();
1143	uint64_t ElemSize = Ctx.getTypeSize(ElementTy);
1144	const RegionOffset &RO = baseR->getAsOffset();
1145	const MemRegion *SuperR = baseR->getBaseRegion();
1146	if (RO.hasSymbolicOffset()) {
1147	// If base region has a symbolic offset,
1148	// we revert to invalidating the super region.
1149	if (SuperR)
1150	AddToWorkList(SuperR);
1151	goto conjure_default;
1152	}
1153
1154	uint64_t LowerOffset = RO.getOffset();
1155	uint64_t UpperOffset = LowerOffset + NumElements ElemSize;
1156	bool UpperOverflow = UpperOffset < LowerOffset;
1157
1158	// Invalidate regions which are within array boundaries,
1159	// or have a symbolic offset.
1160	if (!SuperR)
1161	goto conjure_default;
1162
1163	const ClusterBindings *C = B.lookup(SuperR);
1164	if (!C)
1165	goto conjure_default;
1166
1167	for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E;
1168	++I) {
1169	const BindingKey &BK = I.getKey();
1170	Optional<uint64_t> ROffset =
1171	BK.hasSymbolicOffset() ? Optional<uint64_t>() : BK.getOffset();
1172
1173	// Check offset is not symbolic and within array's boundaries.
1174	// Handles arrays of 0 elements and of 0-sized elements as well.
1175	if (!ROffset \|\|
1176	((ROffset >= LowerOffset && ROffset < UpperOffset) \|\|
1177	(UpperOverflow &&
1178	(ROffset >= LowerOffset \|\| ROffset < UpperOffset)) \|\|
1179	(LowerOffset == UpperOffset && *ROffset == LowerOffset))) {
1180	B = B.removeBinding(I.getKey());
1181	// Bound symbolic regions need to be invalidated for dead symbol
1182	// detection.
1183	SVal V = I.getData();
1184	const MemRegion *R = V.getAsRegion();
1185	if (R && isa<SymbolicRegion>(R))
1186	VisitBinding(V);
1187	}
1188	}
1189	}
1190	conjure_default:
1191	// Set the default value of the array to conjured symbol.
1192	DefinedOrUnknownSVal V =
1193	svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
1194	AT->getElementType(), Count);
1195	B = B.addBinding(baseR, BindingKey::Default, V);
1196	return;
1197	}
1198
1199	DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(baseR, Ex, LCtx,
1200	T,Count);
1201	assert(SymbolManager::canSymbolicate(T) \|\| V.isUnknown());
1202	B = B.addBinding(baseR, BindingKey::Direct, V);
1203	}
1204
1205	bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion(
1206	const MemRegion *R) {
1207	switch (GlobalsFilter) {
1208	case GFK_None:
1209	return false;
1210	case GFK_SystemOnly:
1211	return isa<GlobalSystemSpaceRegion>(R->getMemorySpace());
1212	case GFK_All:
1213	return isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace());
1214	}
1215
1216	llvm_unreachable("unknown globals filter");
1217	}
1218
1219	bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) {
1220	if (isInitiallyIncludedGlobalRegion(Base))
1221	return true;
1222
1223	const MemSpaceRegion *MemSpace = Base->getMemorySpace();
1224	return ITraits.hasTrait(MemSpace,
1225	RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
1226	}
1227
1228	RegionBindingsRef
1229	RegionStoreManager::invalidateGlobalRegion(MemRegion::Kind K,
1230	const Expr *Ex,
1231	unsigned Count,
1232	const LocationContext *LCtx,
1233	RegionBindingsRef B,
1234	InvalidatedRegions *Invalidated) {
1235	// Bind the globals memory space to a new symbol that we will use to derive
1236	// the bindings for all globals.
1237	const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K);
1238	SVal V = svalBuilder.conjureSymbolVal(/* SymbolTag = / (const void) GS, Ex, LCtx,
1239	/* type does not matter */ Ctx.IntTy,
1240	Count);
1241
1242	B = B.removeBinding(GS)
1243	.addBinding(BindingKey::Make(GS, BindingKey::Default), V);
1244
1245	// Even if there are no bindings in the global scope, we still need to
1246	// record that we touched it.
1247	if (Invalidated)
1248	Invalidated->push_back(GS);
1249
1250	return B;
1251	}
1252
1253	void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,
1254	ArrayRef<SVal> Values,
1255	InvalidatedRegions *TopLevelRegions) {
1256	for (ArrayRef<SVal>::iterator I = Values.begin(),
1257	E = Values.end(); I != E; ++I) {
1258	SVal V = *I;
1259	if (Optional<nonloc::LazyCompoundVal> LCS =
1260	V.getAs<nonloc::LazyCompoundVal>()) {
1261
1262	const SValListTy &Vals = getInterestingValues(*LCS);
1263
1264	for (SValListTy::const_iterator I = Vals.begin(),
1265	E = Vals.end(); I != E; ++I) {
1266	// Note: the last argument is false here because these are
1267	// non-top-level regions.
1268	if (const MemRegion R = (I).getAsRegion())
1269	W.AddToWorkList(R);
1270	}
1271	continue;
1272	}
1273
1274	if (const MemRegion *R = V.getAsRegion()) {
1275	if (TopLevelRegions)
1276	TopLevelRegions->push_back(R);
1277	W.AddToWorkList(R);
1278	continue;
1279	}
1280	}
1281	}
1282
1283	StoreRef
1284	RegionStoreManager::invalidateRegions(Store store,
1285	ArrayRef<SVal> Values,
1286	const Expr *Ex, unsigned Count,
1287	const LocationContext *LCtx,
1288	const CallEvent *Call,
1289	InvalidatedSymbols &IS,
1290	RegionAndSymbolInvalidationTraits &ITraits,
1291	InvalidatedRegions *TopLevelRegions,
1292	InvalidatedRegions *Invalidated) {
1293	GlobalsFilterKind GlobalsFilter;
1294	if (Call) {
1295	if (Call->isInSystemHeader())
1296	GlobalsFilter = GFK_SystemOnly;
1297	else
1298	GlobalsFilter = GFK_All;
1299	} else {
1300	GlobalsFilter = GFK_None;
1301	}
1302
1303	RegionBindingsRef B = getRegionBindings(store);
1304	InvalidateRegionsWorker W(*this, StateMgr, B, Ex, Count, LCtx, IS, ITraits,
1305	Invalidated, GlobalsFilter);
1306
1307	// Scan the bindings and generate the clusters.
1308	W.GenerateClusters();
1309
1310	// Add the regions to the worklist.
1311	populateWorkList(W, Values, TopLevelRegions);
1312
1313	W.RunWorkList();
1314
1315	// Return the new bindings.
1316	B = W.getRegionBindings();
1317
1318	// For calls, determine which global regions should be invalidated and
1319	// invalidate them. (Note that function-static and immutable globals are never
1320	// invalidated by this.)
1321	// TODO: This could possibly be more precise with modules.
1322	switch (GlobalsFilter) {
1323	case GFK_All:
1324	B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind,
1325	Ex, Count, LCtx, B, Invalidated);
1326	LLVM_FALLTHROUGH;
1327	case GFK_SystemOnly:
1328	B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind,
1329	Ex, Count, LCtx, B, Invalidated);
1330	LLVM_FALLTHROUGH;
1331	case GFK_None:
1332	break;
1333	}
1334
1335	return StoreRef(B.asStore(), *this);
1336	}
1337
1338	//===----------------------------------------------------------------------===//
1339	// Extents for regions.
1340	//===----------------------------------------------------------------------===//
1341
1342	DefinedOrUnknownSVal
1343	RegionStoreManager::getSizeInElements(ProgramStateRef state,
1344	const MemRegion *R,
1345	QualType EleTy) {
1346	SVal Size = cast<SubRegion>(R)->getExtent(svalBuilder);
1347	const llvm::APSInt *SizeInt = svalBuilder.getKnownValue(state, Size);
1348	if (!SizeInt)
1349	return UnknownVal();
1350
1351	CharUnits RegionSize = CharUnits::fromQuantity(SizeInt->getSExtValue());
1352
1353	if (Ctx.getAsVariableArrayType(EleTy)) {
1354	// FIXME: We need to track extra state to properly record the size
1355	// of VLAs. Returning UnknownVal here, however, is a stop-gap so that
1356	// we don't have a divide-by-zero below.
1357	return UnknownVal();
1358	}
1359
1360	CharUnits EleSize = Ctx.getTypeSizeInChars(EleTy);
1361
1362	// If a variable is reinterpreted as a type that doesn't fit into a larger
1363	// type evenly, round it down.
1364	// This is a signed value, since it's used in arithmetic with signed indices.
1365	return svalBuilder.makeIntVal(RegionSize / EleSize,
1366	svalBuilder.getArrayIndexType());
1367	}
1368
1369	//===----------------------------------------------------------------------===//
1370	// Location and region casting.
1371	//===----------------------------------------------------------------------===//
1372
1373	/// ArrayToPointer - Emulates the "decay" of an array to a pointer
1374	/// type. 'Array' represents the lvalue of the array being decayed
1375	/// to a pointer, and the returned SVal represents the decayed
1376	/// version of that lvalue (i.e., a pointer to the first element of
1377	/// the array). This is called by ExprEngine when evaluating casts
1378	/// from arrays to pointers.
1379	SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) {
1380	if (Array.getAs<loc::ConcreteInt>())
1381	return Array;
1382
1383	if (!Array.getAs<loc::MemRegionVal>())
1384	return UnknownVal();
1385
1386	const SubRegion *R =
1387	cast<SubRegion>(Array.castAs<loc::MemRegionVal>().getRegion());
1388	NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
1389	return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx));
1390	}
1391
1392	//===----------------------------------------------------------------------===//
1393	// Loading values from regions.
1394	//===----------------------------------------------------------------------===//
1395
1396	SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) {
1397	(0) . __assert_fail ("!L.getAs() && \"location unknown\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 1397, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!L.getAs<UnknownVal>() && "location unknown");
1398	(0) . __assert_fail ("!L.getAs() && \"location undefined\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 1398, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!L.getAs<UndefinedVal>() && "location undefined");
1399
1400	// For access to concrete addresses, return UnknownVal. Checks
1401	// for null dereferences (and similar errors) are done by checkers, not
1402	// the Store.
1403	// FIXME: We can consider lazily symbolicating such memory, but we really
1404	// should defer this when we can reason easily about symbolicating arrays
1405	// of bytes.
1406	if (L.getAs<loc::ConcreteInt>()) {
1407	return UnknownVal();
1408	}
1409	if (!L.getAs<loc::MemRegionVal>()) {
1410	return UnknownVal();
1411	}
1412
1413	const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion();
1414
1415	if (isa<BlockDataRegion>(MR)) {
1416	return UnknownVal();
1417	}
1418
1419	if (!isa<TypedValueRegion>(MR)) {
1420	if (T.isNull()) {
1421	if (const TypedRegion *TR = dyn_cast<TypedRegion>(MR))
1422	T = TR->getLocationType()->getPointeeType();
1423	else if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
1424	T = SR->getSymbol()->getType()->getPointeeType();
1425	}
1426	(0) . __assert_fail ("!T.isNull() && \"Unable to auto-detect binding type!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 1426, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!T.isNull() && "Unable to auto-detect binding type!");
1427	(0) . __assert_fail ("!T->isVoidType() && \"Attempting to dereference a void pointer!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 1427, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!T->isVoidType() && "Attempting to dereference a void pointer!");
1428	MR = GetElementZeroRegion(cast<SubRegion>(MR), T);
1429	} else {
1430	T = cast<TypedValueRegion>(MR)->getValueType();
1431	}
1432
1433	// FIXME: Perhaps this method should just take a 'const MemRegion*' argument
1434	// instead of 'Loc', and have the other Loc cases handled at a higher level.
1435	const TypedValueRegion *R = cast<TypedValueRegion>(MR);
1436	QualType RTy = R->getValueType();
1437
1438	// FIXME: we do not yet model the parts of a complex type, so treat the
1439	// whole thing as "unknown".
1440	if (RTy->isAnyComplexType())
1441	return UnknownVal();
1442
1443	// FIXME: We should eventually handle funny addressing. e.g.:
1444	//
1445	// int x = ...;
1446	// int *p = &x;
1447	// char q = (char) p;
1448	// char c = *q; // returns the first byte of 'x'.
1449	//
1450	// Such funny addressing will occur due to layering of regions.
1451	if (RTy->isStructureOrClassType())
1452	return getBindingForStruct(B, R);
1453
1454	// FIXME: Handle unions.
1455	if (RTy->isUnionType())
1456	return createLazyBinding(B, R);
1457
1458	if (RTy->isArrayType()) {
1459	if (RTy->isConstantArrayType())
1460	return getBindingForArray(B, R);
1461	else
1462	return UnknownVal();
1463	}
1464
1465	// FIXME: handle Vector types.
1466	if (RTy->isVectorType())
1467	return UnknownVal();
1468
1469	if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
1470	return CastRetrievedVal(getBindingForField(B, FR), FR, T);
1471
1472	if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
1473	// FIXME: Here we actually perform an implicit conversion from the loaded
1474	// value to the element type. Eventually we want to compose these values
1475	// more intelligently. For example, an 'element' can encompass multiple
1476	// bound regions (e.g., several bound bytes), or could be a subset of
1477	// a larger value.
1478	return CastRetrievedVal(getBindingForElement(B, ER), ER, T);
1479	}
1480
1481	if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1482	// FIXME: Here we actually perform an implicit conversion from the loaded
1483	// value to the ivar type. What we should model is stores to ivars
1484	// that blow past the extent of the ivar. If the address of the ivar is
1485	// reinterpretted, it is possible we stored a different value that could
1486	// fit within the ivar. Either we need to cast these when storing them
1487	// or reinterpret them lazily (as we do here).
1488	return CastRetrievedVal(getBindingForObjCIvar(B, IVR), IVR, T);
1489	}
1490
1491	if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1492	// FIXME: Here we actually perform an implicit conversion from the loaded
1493	// value to the variable type. What we should model is stores to variables
1494	// that blow past the extent of the variable. If the address of the
1495	// variable is reinterpretted, it is possible we stored a different value
1496	// that could fit within the variable. Either we need to cast these when
1497	// storing them or reinterpret them lazily (as we do here).
1498	return CastRetrievedVal(getBindingForVar(B, VR), VR, T);
1499	}
1500
1501	const SVal *V = B.lookup(R, BindingKey::Direct);
1502
1503	// Check if the region has a binding.
1504	if (V)
1505	return *V;
1506
1507	// The location does not have a bound value. This means that it has
1508	// the value it had upon its creation and/or entry to the analyzed
1509	// function/method. These are either symbolic values or 'undefined'.
1510	if (R->hasStackNonParametersStorage()) {
1511	// All stack variables are considered to have undefined values
1512	// upon creation. All heap allocated blocks are considered to
1513	// have undefined values as well unless they are explicitly bound
1514	// to specific values.
1515	return UndefinedVal();
1516	}
1517
1518	// All other values are symbolic.
1519	return svalBuilder.getRegionValueSymbolVal(R);
1520	}
1521
1522	static QualType getUnderlyingType(const SubRegion *R) {
1523	QualType RegionTy;
1524	if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R))
1525	RegionTy = TVR->getValueType();
1526
1527	if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
1528	RegionTy = SR->getSymbol()->getType();
1529
1530	return RegionTy;
1531	}
1532
1533	/// Checks to see if store \p B has a lazy binding for region \p R.
1534	///
1535	/// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected
1536	/// if there are additional bindings within \p R.
1537	///
1538	/// Note that unlike RegionStoreManager::findLazyBinding, this will not search
1539	/// for lazy bindings for super-regions of \p R.
1540	static Optional<nonloc::LazyCompoundVal>
1541	getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B,
1542	const SubRegion *R, bool AllowSubregionBindings) {
1543	Optional<SVal> V = B.getDefaultBinding(R);
1544	if (!V)
1545	return None;
1546
1547	Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>();
1548	if (!LCV)
1549	return None;
1550
1551	// If the LCV is for a subregion, the types might not match, and we shouldn't
1552	// reuse the binding.
1553	QualType RegionTy = getUnderlyingType(R);
1554	if (!RegionTy.isNull() &&
1555	!RegionTy->isVoidPointerType()) {
1556	QualType SourceRegionTy = LCV->getRegion()->getValueType();
1557	if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy))
1558	return None;
1559	}
1560
1561	if (!AllowSubregionBindings) {
1562	// If there are any other bindings within this region, we shouldn't reuse
1563	// the top-level binding.
1564	SmallVector<BindingPair, 16> Bindings;
1565	collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R,
1566	/IncludeAllDefaultBindings=/true);
1567	if (Bindings.size() > 1)
1568	return None;
1569	}
1570
1571	return *LCV;
1572	}
1573
1574
1575	std::pair<Store, const SubRegion *>
1576	RegionStoreManager::findLazyBinding(RegionBindingsConstRef B,
1577	const SubRegion *R,
1578	const SubRegion *originalRegion) {
1579	if (originalRegion != R) {
1580	if (Optional<nonloc::LazyCompoundVal> V =
1581	getExistingLazyBinding(svalBuilder, B, R, true))
1582	return std::make_pair(V->getStore(), V->getRegion());
1583	}
1584
1585	typedef std::pair<Store, const SubRegion *> StoreRegionPair;
1586	StoreRegionPair Result = StoreRegionPair();
1587
1588	if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1589	Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()),
1590	originalRegion);
1591
1592	if (Result.second)
1593	Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second);
1594
1595	} else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1596	Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()),
1597	originalRegion);
1598
1599	if (Result.second)
1600	Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second);
1601
1602	} else if (const CXXBaseObjectRegion *BaseReg =
1603	dyn_cast<CXXBaseObjectRegion>(R)) {
1604	// C++ base object region is another kind of region that we should blast
1605	// through to look for lazy compound value. It is like a field region.
1606	Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()),
1607	originalRegion);
1608
1609	if (Result.second)
1610	Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,
1611	Result.second);
1612	}
1613
1614	return Result;
1615	}
1616
1617	SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
1618	const ElementRegion* R) {
1619	// We do not currently model bindings of the CompoundLiteralregion.
1620	if (isa<CompoundLiteralRegion>(R->getBaseRegion()))
1621	return UnknownVal();
1622
1623	// Check if the region has a binding.
1624	if (const Optional<SVal> &V = B.getDirectBinding(R))
1625	return *V;
1626
1627	const MemRegion* superR = R->getSuperRegion();
1628
1629	// Check if the region is an element region of a string literal.
1630	if (const StringRegion *StrR = dyn_cast<StringRegion>(superR)) {
1631	// FIXME: Handle loads from strings where the literal is treated as
1632	// an integer, e.g., ((unsigned int)"hello")
1633	QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();
1634	if (!Ctx.hasSameUnqualifiedType(T, R->getElementType()))
1635	return UnknownVal();
1636
1637	const StringLiteral *Str = StrR->getStringLiteral();
1638	SVal Idx = R->getIndex();
1639	if (Optional<nonloc::ConcreteInt> CI = Idx.getAs<nonloc::ConcreteInt>()) {
1640	int64_t i = CI->getValue().getSExtValue();
1641	// Abort on string underrun. This can be possible by arbitrary
1642	// clients of getBindingForElement().
1643	if (i < 0)
1644	return UndefinedVal();
1645	int64_t length = Str->getLength();
1646	// Technically, only i == length is guaranteed to be null.
1647	// However, such overflows should be caught before reaching this point;
1648	// the only time such an access would be made is if a string literal was
1649	// used to initialize a larger array.
1650	char c = (i >= length) ? '\0' : Str->getCodeUnit(i);
1651	return svalBuilder.makeIntVal(c, T);
1652	}
1653	} else if (const VarRegion *VR = dyn_cast<VarRegion>(superR)) {
1654	// Check if the containing array is const and has an initialized value.
1655	const VarDecl *VD = VR->getDecl();
1656	// Either the array or the array element has to be const.
1657	if (VD->getType().isConstQualified() \|\| R->getElementType().isConstQualified()) {
1658	if (const Expr *Init = VD->getInit()) {
1659	if (const auto *InitList = dyn_cast<InitListExpr>(Init)) {
1660	// The array index has to be known.
1661	if (auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) {
1662	int64_t i = CI->getValue().getSExtValue();
1663	// If it is known that the index is out of bounds, we can return
1664	// an undefined value.
1665	if (i < 0)
1666	return UndefinedVal();
1667
1668	if (auto CAT = Ctx.getAsConstantArrayType(VD->getType()))
1669	if (CAT->getSize().sle(i))
1670	return UndefinedVal();
1671
1672	// If there is a list, but no init, it must be zero.
1673	if (i >= InitList->getNumInits())
1674	return svalBuilder.makeZeroVal(R->getElementType());
1675
1676	if (const Expr *ElemInit = InitList->getInit(i))
1677	if (Optional<SVal> V = svalBuilder.getConstantVal(ElemInit))
1678	return *V;
1679	}
1680	}
1681	}
1682	}
1683	}
1684
1685	// Check for loads from a code text region. For such loads, just give up.
1686	if (isa<CodeTextRegion>(superR))
1687	return UnknownVal();
1688
1689	// Handle the case where we are indexing into a larger scalar object.
1690	// For example, this handles:
1691	// int x = ...
1692	// char *y = &x;
1693	// return *y;
1694	// FIXME: This is a hack, and doesn't do anything really intelligent yet.
1695	const RegionRawOffset &O = R->getAsArrayOffset();
1696
1697	// If we cannot reason about the offset, return an unknown value.
1698	if (!O.getRegion())
1699	return UnknownVal();
1700
1701	if (const TypedValueRegion *baseR =
1702	dyn_cast_or_null<TypedValueRegion>(O.getRegion())) {
1703	QualType baseT = baseR->getValueType();
1704	if (baseT->isScalarType()) {
1705	QualType elemT = R->getElementType();
1706	if (elemT->isScalarType()) {
1707	if (Ctx.getTypeSizeInChars(baseT) >= Ctx.getTypeSizeInChars(elemT)) {
1708	if (const Optional<SVal> &V = B.getDirectBinding(superR)) {
1709	if (SymbolRef parentSym = V->getAsSymbol())
1710	return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1711
1712	if (V->isUnknownOrUndef())
1713	return *V;
1714	// Other cases: give up. We are indexing into a larger object
1715	// that has some value, but we don't know how to handle that yet.
1716	return UnknownVal();
1717	}
1718	}
1719	}
1720	}
1721	}
1722	return getBindingForFieldOrElementCommon(B, R, R->getElementType());
1723	}
1724
1725	SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B,
1726	const FieldRegion* R) {
1727
1728	// Check if the region has a binding.
1729	if (const Optional<SVal> &V = B.getDirectBinding(R))
1730	return *V;
1731
1732	// Is the field declared constant and has an in-class initializer?
1733	const FieldDecl *FD = R->getDecl();
1734	QualType Ty = FD->getType();
1735	if (Ty.isConstQualified())
1736	if (const Expr *Init = FD->getInClassInitializer())
1737	if (Optional<SVal> V = svalBuilder.getConstantVal(Init))
1738	return *V;
1739
1740	// If the containing record was initialized, try to get its constant value.
1741	const MemRegion* superR = R->getSuperRegion();
1742	if (const auto *VR = dyn_cast<VarRegion>(superR)) {
1743	const VarDecl *VD = VR->getDecl();
1744	QualType RecordVarTy = VD->getType();
1745	unsigned Index = FD->getFieldIndex();
1746	// Either the record variable or the field has to be const qualified.
1747	if (RecordVarTy.isConstQualified() \|\| Ty.isConstQualified())
1748	if (const Expr *Init = VD->getInit())
1749	if (const auto *InitList = dyn_cast<InitListExpr>(Init)) {
1750	if (Index < InitList->getNumInits()) {
1751	if (const Expr *FieldInit = InitList->getInit(Index))
1752	if (Optional<SVal> V = svalBuilder.getConstantVal(FieldInit))
1753	return *V;
1754	} else {
1755	return svalBuilder.makeZeroVal(Ty);
1756	}
1757	}
1758	}
1759
1760	return getBindingForFieldOrElementCommon(B, R, Ty);
1761	}
1762
1763	Optional<SVal>
1764	RegionStoreManager::getBindingForDerivedDefaultValue(RegionBindingsConstRef B,
1765	const MemRegion *superR,
1766	const TypedValueRegion *R,
1767	QualType Ty) {
1768
1769	if (const Optional<SVal> &D = B.getDefaultBinding(superR)) {
1770	const SVal &val = D.getValue();
1771	if (SymbolRef parentSym = val.getAsSymbol())
1772	return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1773
1774	if (val.isZeroConstant())
1775	return svalBuilder.makeZeroVal(Ty);
1776
1777	if (val.isUnknownOrUndef())
1778	return val;
1779
1780	// Lazy bindings are usually handled through getExistingLazyBinding().
1781	// We should unify these two code paths at some point.
1782	if (val.getAs<nonloc::LazyCompoundVal>() \|\|
1783	val.getAs<nonloc::CompoundVal>())
1784	return val;
1785
1786	llvm_unreachable("Unknown default value");
1787	}
1788
1789	return None;
1790	}
1791
1792	SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion,
1793	RegionBindingsRef LazyBinding) {
1794	SVal Result;
1795	if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion))
1796	Result = getBindingForElement(LazyBinding, ER);
1797	else
1798	Result = getBindingForField(LazyBinding,
1799	cast<FieldRegion>(LazyBindingRegion));
1800
1801	// FIXME: This is a hack to deal with RegionStore's inability to distinguish a
1802	// default value for /part/ of an aggregate from a default value for the
1803	// /entire/ aggregate. The most common case of this is when struct Outer
1804	// has as its first member a struct Inner, which is copied in from a stack
1805	// variable. In this case, even if the Outer's default value is symbolic, 0,
1806	// or unknown, it gets overridden by the Inner's default value of undefined.
1807	//
1808	// This is a general problem -- if the Inner is zero-initialized, the Outer
1809	// will now look zero-initialized. The proper way to solve this is with a
1810	// new version of RegionStore that tracks the extent of a binding as well
1811	// as the offset.
1812	//
1813	// This hack only takes care of the undefined case because that can very
1814	// quickly result in a warning.
1815	if (Result.isUndef())
1816	Result = UnknownVal();
1817
1818	return Result;
1819	}
1820
1821	SVal
1822	RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
1823	const TypedValueRegion *R,
1824	QualType Ty) {
1825
1826	// At this point we have already checked in either getBindingForElement or
1827	// getBindingForField if 'R' has a direct binding.
1828
1829	// Lazy binding?
1830	Store lazyBindingStore = nullptr;
1831	const SubRegion *lazyBindingRegion = nullptr;
1832	std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R);
1833	if (lazyBindingRegion)
1834	return getLazyBinding(lazyBindingRegion,
1835	getRegionBindings(lazyBindingStore));
1836
1837	// Record whether or not we see a symbolic index. That can completely
1838	// be out of scope of our lookup.
1839	bool hasSymbolicIndex = false;
1840
1841	// FIXME: This is a hack to deal with RegionStore's inability to distinguish a
1842	// default value for /part/ of an aggregate from a default value for the
1843	// /entire/ aggregate. The most common case of this is when struct Outer
1844	// has as its first member a struct Inner, which is copied in from a stack
1845	// variable. In this case, even if the Outer's default value is symbolic, 0,
1846	// or unknown, it gets overridden by the Inner's default value of undefined.
1847	//
1848	// This is a general problem -- if the Inner is zero-initialized, the Outer
1849	// will now look zero-initialized. The proper way to solve this is with a
1850	// new version of RegionStore that tracks the extent of a binding as well
1851	// as the offset.
1852	//
1853	// This hack only takes care of the undefined case because that can very
1854	// quickly result in a warning.
1855	bool hasPartialLazyBinding = false;
1856
1857	const SubRegion *SR = R;
1858	while (SR) {
1859	const MemRegion *Base = SR->getSuperRegion();
1860	if (Optional<SVal> D = getBindingForDerivedDefaultValue(B, Base, R, Ty)) {
1861	if (D->getAs<nonloc::LazyCompoundVal>()) {
1862	hasPartialLazyBinding = true;
1863	break;
1864	}
1865
1866	return *D;
1867	}
1868
1869	if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) {
1870	NonLoc index = ER->getIndex();
1871	if (!index.isConstant())
1872	hasSymbolicIndex = true;
1873	}
1874
1875	// If our super region is a field or element itself, walk up the region
1876	// hierarchy to see if there is a default value installed in an ancestor.
1877	SR = dyn_cast<SubRegion>(Base);
1878	}
1879
1880	if (R->hasStackNonParametersStorage()) {
1881	if (isa<ElementRegion>(R)) {
1882	// Currently we don't reason specially about Clang-style vectors. Check
1883	// if superR is a vector and if so return Unknown.
1884	if (const TypedValueRegion *typedSuperR =
1885	dyn_cast<TypedValueRegion>(R->getSuperRegion())) {
1886	if (typedSuperR->getValueType()->isVectorType())
1887	return UnknownVal();
1888	}
1889	}
1890
1891	// FIXME: We also need to take ElementRegions with symbolic indexes into
1892	// account. This case handles both directly accessing an ElementRegion
1893	// with a symbolic offset, but also fields within an element with
1894	// a symbolic offset.
1895	if (hasSymbolicIndex)
1896	return UnknownVal();
1897
1898	if (!hasPartialLazyBinding)
1899	return UndefinedVal();
1900	}
1901
1902	// All other values are symbolic.
1903	return svalBuilder.getRegionValueSymbolVal(R);
1904	}
1905
1906	SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B,
1907	const ObjCIvarRegion* R) {
1908	// Check if the region has a binding.
1909	if (const Optional<SVal> &V = B.getDirectBinding(R))
1910	return *V;
1911
1912	const MemRegion *superR = R->getSuperRegion();
1913
1914	// Check if the super region has a default binding.
1915	if (const Optional<SVal> &V = B.getDefaultBinding(superR)) {
1916	if (SymbolRef parentSym = V->getAsSymbol())
1917	return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
1918
1919	// Other cases: give up.
1920	return UnknownVal();
1921	}
1922
1923	return getBindingForLazySymbol(R);
1924	}
1925
1926	SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B,
1927	const VarRegion *R) {
1928
1929	// Check if the region has a binding.
1930	if (const Optional<SVal> &V = B.getDirectBinding(R))
1931	return *V;
1932
1933	// Lazily derive a value for the VarRegion.
1934	const VarDecl *VD = R->getDecl();
1935	const MemSpaceRegion *MS = R->getMemorySpace();
1936
1937	// Arguments are always symbolic.
1938	if (isa<StackArgumentsSpaceRegion>(MS))
1939	return svalBuilder.getRegionValueSymbolVal(R);
1940
1941	// Is 'VD' declared constant? If so, retrieve the constant value.
1942	if (VD->getType().isConstQualified()) {
1943	if (const Expr *Init = VD->getInit()) {
1944	if (Optional<SVal> V = svalBuilder.getConstantVal(Init))
1945	return *V;
1946
1947	// If the variable is const qualified and has an initializer but
1948	// we couldn't evaluate initializer to a value, treat the value as
1949	// unknown.
1950	return UnknownVal();
1951	}
1952	}
1953
1954	// This must come after the check for constants because closure-captured
1955	// constant variables may appear in UnknownSpaceRegion.
1956	if (isa<UnknownSpaceRegion>(MS))
1957	return svalBuilder.getRegionValueSymbolVal(R);
1958
1959	if (isa<GlobalsSpaceRegion>(MS)) {
1960	QualType T = VD->getType();
1961
1962	// Function-scoped static variables are default-initialized to 0; if they
1963	// have an initializer, it would have been processed by now.
1964	// FIXME: This is only true when we're starting analysis from main().
1965	// We're losing a lot of coverage here.
1966	if (isa<StaticGlobalSpaceRegion>(MS))
1967	return svalBuilder.makeZeroVal(T);
1968
1969	if (Optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) {
1970	getAs()", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 1970, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!V->getAs<nonloc::LazyCompoundVal>());
1971	return V.getValue();
1972	}
1973
1974	return svalBuilder.getRegionValueSymbolVal(R);
1975	}
1976
1977	return UndefinedVal();
1978	}
1979
1980	SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) {
1981	// All other values are symbolic.
1982	return svalBuilder.getRegionValueSymbolVal(R);
1983	}
1984
1985	const RegionStoreManager::SValListTy &
1986	RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) {
1987	// First, check the cache.
1988	LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData());
1989	if (I != LazyBindingsMap.end())
1990	return I->second;
1991
1992	// If we don't have a list of values cached, start constructing it.
1993	SValListTy List;
1994
1995	const SubRegion *LazyR = LCV.getRegion();
1996	RegionBindingsRef B = getRegionBindings(LCV.getStore());
1997
1998	// If this region had /no/ bindings at the time, there are no interesting
1999	// values to return.
2000	const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion());
2001	if (!Cluster)
2002	return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
2003
2004	SmallVector<BindingPair, 32> Bindings;
2005	collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR,
2006	/IncludeAllDefaultBindings=/true);
2007	for (SmallVectorImpl<BindingPair>::const_iterator I = Bindings.begin(),
2008	E = Bindings.end();
2009	I != E; ++I) {
2010	SVal V = I->second;
2011	if (V.isUnknownOrUndef() \|\| V.isConstant())
2012	continue;
2013
2014	if (Optional<nonloc::LazyCompoundVal> InnerLCV =
2015	V.getAs<nonloc::LazyCompoundVal>()) {
2016	const SValListTy &InnerList = getInterestingValues(*InnerLCV);
2017	List.insert(List.end(), InnerList.begin(), InnerList.end());
2018	continue;
2019	}
2020
2021	List.push_back(V);
2022	}
2023
2024	return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
2025	}
2026
2027	NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B,
2028	const TypedValueRegion *R) {
2029	if (Optional<nonloc::LazyCompoundVal> V =
2030	getExistingLazyBinding(svalBuilder, B, R, false))
2031	return *V;
2032
2033	return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R);
2034	}
2035
2036	static bool isRecordEmpty(const RecordDecl *RD) {
2037	if (!RD->field_empty())
2038	return false;
2039	if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(RD))
2040	return CRD->getNumBases() == 0;
2041	return true;
2042	}
2043
2044	SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B,
2045	const TypedValueRegion *R) {
2046	const RecordDecl *RD = R->getValueType()->castAs<RecordType>()->getDecl();
2047	if (!RD->getDefinition() \|\| isRecordEmpty(RD))
2048	return UnknownVal();
2049
2050	return createLazyBinding(B, R);
2051	}
2052
2053	SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B,
2054	const TypedValueRegion *R) {
2055	(0) . __assert_fail ("Ctx.getAsConstantArrayType(R->getValueType()) && \"Only constant array types can have compound bindings.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2056, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Ctx.getAsConstantArrayType(R->getValueType()) &&
2056	(0) . __assert_fail ("Ctx.getAsConstantArrayType(R->getValueType()) && \"Only constant array types can have compound bindings.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2056, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Only constant array types can have compound bindings.");
2057
2058	return createLazyBinding(B, R);
2059	}
2060
2061	bool RegionStoreManager::includedInBindings(Store store,
2062	const MemRegion *region) const {
2063	RegionBindingsRef B = getRegionBindings(store);
2064	region = region->getBaseRegion();
2065
2066	// Quick path: if the base is the head of a cluster, the region is live.
2067	if (B.lookup(region))
2068	return true;
2069
2070	// Slow path: if the region is the VALUE of any binding, it is live.
2071	for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {
2072	const ClusterBindings &Cluster = RI.getData();
2073	for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
2074	CI != CE; ++CI) {
2075	const SVal &D = CI.getData();
2076	if (const MemRegion *R = D.getAsRegion())
2077	if (R->getBaseRegion() == region)
2078	return true;
2079	}
2080	}
2081
2082	return false;
2083	}
2084
2085	//===----------------------------------------------------------------------===//
2086	// Binding values to regions.
2087	//===----------------------------------------------------------------------===//
2088
2089	StoreRef RegionStoreManager::killBinding(Store ST, Loc L) {
2090	if (Optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>())
2091	if (const MemRegion* R = LV->getRegion())
2092	return StoreRef(getRegionBindings(ST).removeBinding(R)
2093	.asImmutableMap()
2094	.getRootWithoutRetain(),
2095	*this);
2096
2097	return StoreRef(ST, *this);
2098	}
2099
2100	RegionBindingsRef
2101	RegionStoreManager::bind(RegionBindingsConstRef B, Loc L, SVal V) {
2102	if (L.getAs<loc::ConcreteInt>())
2103	return B;
2104
2105	// If we get here, the location should be a region.
2106	const MemRegion *R = L.castAs<loc::MemRegionVal>().getRegion();
2107
2108	// Check if the region is a struct region.
2109	if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) {
2110	QualType Ty = TR->getValueType();
2111	if (Ty->isArrayType())
2112	return bindArray(B, TR, V);
2113	if (Ty->isStructureOrClassType())
2114	return bindStruct(B, TR, V);
2115	if (Ty->isVectorType())
2116	return bindVector(B, TR, V);
2117	if (Ty->isUnionType())
2118	return bindAggregate(B, TR, V);
2119	}
2120
2121	if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
2122	// Binding directly to a symbolic region should be treated as binding
2123	// to element 0.
2124	QualType T = SR->getSymbol()->getType();
2125	if (T->isAnyPointerType() \|\| T->isReferenceType())
2126	T = T->getPointeeType();
2127
2128	R = GetElementZeroRegion(SR, T);
2129	}
2130
2131	(0) . __assert_fail ("(!isa(R) \|\| !B.lookup(R)) && \"'this' pointer is not an l-value and is not assignable\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2132, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert((!isa<CXXThisRegion>(R) \|\| !B.lookup(R)) &&
2132	(0) . __assert_fail ("(!isa(R) \|\| !B.lookup(R)) && \"'this' pointer is not an l-value and is not assignable\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2132, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "'this' pointer is not an l-value and is not assignable");
2133
2134	// Clear out bindings that may overlap with this binding.
2135	RegionBindingsRef NewB = removeSubRegionBindings(B, cast<SubRegion>(R));
2136	return NewB.addBinding(BindingKey::Make(R, BindingKey::Direct), V);
2137	}
2138
2139	RegionBindingsRef
2140	RegionStoreManager::setImplicitDefaultValue(RegionBindingsConstRef B,
2141	const MemRegion *R,
2142	QualType T) {
2143	SVal V;
2144
2145	if (Loc::isLocType(T))
2146	V = svalBuilder.makeNull();
2147	else if (T->isIntegralOrEnumerationType())
2148	V = svalBuilder.makeZeroVal(T);
2149	else if (T->isStructureOrClassType() \|\| T->isArrayType()) {
2150	// Set the default value to a zero constant when it is a structure
2151	// or array. The type doesn't really matter.
2152	V = svalBuilder.makeZeroVal(Ctx.IntTy);
2153	}
2154	else {
2155	// We can't represent values of this type, but we still need to set a value
2156	// to record that the region has been initialized.
2157	// If this assertion ever fires, a new case should be added above -- we
2158	// should know how to default-initialize any value we can symbolicate.
2159	(0) . __assert_fail ("!SymbolManager..canSymbolicate(T) && \"This type is representable\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2159, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!SymbolManager::canSymbolicate(T) && "This type is representable");
2160	V = UnknownVal();
2161	}
2162
2163	return B.addBinding(R, BindingKey::Default, V);
2164	}
2165
2166	RegionBindingsRef
2167	RegionStoreManager::bindArray(RegionBindingsConstRef B,
2168	const TypedValueRegion* R,
2169	SVal Init) {
2170
2171	const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
2172	QualType ElementTy = AT->getElementType();
2173	Optional<uint64_t> Size;
2174
2175	if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
2176	Size = CAT->getSize().getZExtValue();
2177
2178	// Check if the init expr is a literal. If so, bind the rvalue instead.
2179	// FIXME: It's not responsibility of the Store to transform this lvalue
2180	// to rvalue. ExprEngine or maybe even CFG should do this before binding.
2181	if (Optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) {
2182	SVal V = getBinding(B.asStore(), *MRV, R->getValueType());
2183	return bindAggregate(B, R, V);
2184	}
2185
2186	// Handle lazy compound values.
2187	if (Init.getAs<nonloc::LazyCompoundVal>())
2188	return bindAggregate(B, R, Init);
2189
2190	if (Init.isUnknown())
2191	return bindAggregate(B, R, UnknownVal());
2192
2193	// Remaining case: explicit compound values.
2194	const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>();
2195	nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
2196	uint64_t i = 0;
2197
2198	RegionBindingsRef NewB(B);
2199
2200	for (; Size.hasValue() ? i < Size.getValue() : true ; ++i, ++VI) {
2201	// The init list might be shorter than the array length.
2202	if (VI == VE)
2203	break;
2204
2205	const NonLoc &Idx = svalBuilder.makeArrayIndex(i);
2206	const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
2207
2208	if (ElementTy->isStructureOrClassType())
2209	NewB = bindStruct(NewB, ER, *VI);
2210	else if (ElementTy->isArrayType())
2211	NewB = bindArray(NewB, ER, *VI);
2212	else
2213	NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2214	}
2215
2216	// If the init list is shorter than the array length (or the array has
2217	// variable length), set the array default value. Values that are already set
2218	// are not overwritten.
2219	if (!Size.hasValue() \|\| i < Size.getValue())
2220	NewB = setImplicitDefaultValue(NewB, R, ElementTy);
2221
2222	return NewB;
2223	}
2224
2225	RegionBindingsRef RegionStoreManager::bindVector(RegionBindingsConstRef B,
2226	const TypedValueRegion* R,
2227	SVal V) {
2228	QualType T = R->getValueType();
2229	isVectorType()", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2229, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(T->isVectorType());
2230	const VectorType *VT = T->getAs<VectorType>(); // Use getAs for typedefs.
2231
2232	// Handle lazy compound values and symbolic values.
2233	if (V.getAs<nonloc::LazyCompoundVal>() \|\| V.getAs<nonloc::SymbolVal>())
2234	return bindAggregate(B, R, V);
2235
2236	// We may get non-CompoundVal accidentally due to imprecise cast logic or
2237	// that we are binding symbolic struct value. Kill the field values, and if
2238	// the value is symbolic go and bind it as a "default" binding.
2239	if (!V.getAs<nonloc::CompoundVal>()) {
2240	return bindAggregate(B, R, UnknownVal());
2241	}
2242
2243	QualType ElemType = VT->getElementType();
2244	nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>();
2245	nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
2246	unsigned index = 0, numElements = VT->getNumElements();
2247	RegionBindingsRef NewB(B);
2248
2249	for ( ; index != numElements ; ++index) {
2250	if (VI == VE)
2251	break;
2252
2253	NonLoc Idx = svalBuilder.makeArrayIndex(index);
2254	const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);
2255
2256	if (ElemType->isArrayType())
2257	NewB = bindArray(NewB, ER, *VI);
2258	else if (ElemType->isStructureOrClassType())
2259	NewB = bindStruct(NewB, ER, *VI);
2260	else
2261	NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2262	}
2263	return NewB;
2264	}
2265
2266	Optional<RegionBindingsRef>
2267	RegionStoreManager::tryBindSmallStruct(RegionBindingsConstRef B,
2268	const TypedValueRegion *R,
2269	const RecordDecl *RD,
2270	nonloc::LazyCompoundVal LCV) {
2271	FieldVector Fields;
2272
2273	if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD))
2274	if (Class->getNumBases() != 0 \|\| Class->getNumVBases() != 0)
2275	return None;
2276
2277	for (const auto *FD : RD->fields()) {
2278	if (FD->isUnnamedBitfield())
2279	continue;
2280
2281	// If there are too many fields, or if any of the fields are aggregates,
2282	// just use the LCV as a default binding.
2283	if (Fields.size() == SmallStructLimit)
2284	return None;
2285
2286	QualType Ty = FD->getType();
2287	if (!(Ty->isScalarType() \|\| Ty->isReferenceType()))
2288	return None;
2289
2290	Fields.push_back(FD);
2291	}
2292
2293	RegionBindingsRef NewB = B;
2294
2295	for (FieldVector::iterator I = Fields.begin(), E = Fields.end(); I != E; ++I){
2296	const FieldRegion SourceFR = MRMgr.getFieldRegion(I, LCV.getRegion());
2297	SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR);
2298
2299	const FieldRegion DestFR = MRMgr.getFieldRegion(I, R);
2300	NewB = bind(NewB, loc::MemRegionVal(DestFR), V);
2301	}
2302
2303	return NewB;
2304	}
2305
2306	RegionBindingsRef RegionStoreManager::bindStruct(RegionBindingsConstRef B,
2307	const TypedValueRegion* R,
2308	SVal V) {
2309	if (!Features.supportsFields())
2310	return B;
2311
2312	QualType T = R->getValueType();
2313	isStructureOrClassType()", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2313, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(T->isStructureOrClassType());
2314
2315	const RecordType* RT = T->getAs<RecordType>();
2316	const RecordDecl *RD = RT->getDecl();
2317
2318	if (!RD->isCompleteDefinition())
2319	return B;
2320
2321	// Handle lazy compound values and symbolic values.
2322	if (Optional<nonloc::LazyCompoundVal> LCV =
2323	V.getAs<nonloc::LazyCompoundVal>()) {
2324	if (Optional<RegionBindingsRef> NewB = tryBindSmallStruct(B, R, RD, *LCV))
2325	return *NewB;
2326	return bindAggregate(B, R, V);
2327	}
2328	if (V.getAs<nonloc::SymbolVal>())
2329	return bindAggregate(B, R, V);
2330
2331	// We may get non-CompoundVal accidentally due to imprecise cast logic or
2332	// that we are binding symbolic struct value. Kill the field values, and if
2333	// the value is symbolic go and bind it as a "default" binding.
2334	if (V.isUnknown() \|\| !V.getAs<nonloc::CompoundVal>())
2335	return bindAggregate(B, R, UnknownVal());
2336
2337	// The raw CompoundVal is essentially a symbolic InitListExpr: an (immutable)
2338	// list of other values. It appears pretty much only when there's an actual
2339	// initializer list expression in the program, and the analyzer tries to
2340	// unwrap it as soon as possible.
2341	// This code is where such unwrap happens: when the compound value is put into
2342	// the object that it was supposed to initialize (it's an initializer list,
2343	// after all), instead of binding the whole value to the whole object, we bind
2344	// sub-values to sub-objects. Sub-values may themselves be compound values,
2345	// and in this case the procedure becomes recursive.
2346	// FIXME: The annoying part about compound values is that they don't carry
2347	// any sort of information about which value corresponds to which sub-object.
2348	// It's simply a list of values in the middle of nowhere; we expect to match
2349	// them to sub-objects, essentially, "by index": first value binds to
2350	// the first field, second value binds to the second field, etc.
2351	// It would have been much safer to organize non-lazy compound values as
2352	// a mapping from fields/bases to values.
2353	const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>();
2354	nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
2355
2356	RegionBindingsRef NewB(B);
2357
2358	// In C++17 aggregates may have base classes, handle those as well.
2359	// They appear before fields in the initializer list / compound value.
2360	if (const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) {
2361	(0) . __assert_fail ("CRD->isAggregate() && \"Non-aggregates are constructed with a constructor!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2362, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(CRD->isAggregate() &&
2362	(0) . __assert_fail ("CRD->isAggregate() && \"Non-aggregates are constructed with a constructor!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2362, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Non-aggregates are constructed with a constructor!");
2363
2364	for (const auto &B : CRD->bases()) {
2365	// (Multiple inheritance is fine though.)
2366	(0) . __assert_fail ("!B.isVirtual() && \"Aggregates cannot have virtual base classes!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2366, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!B.isVirtual() && "Aggregates cannot have virtual base classes!");
2367
2368	if (VI == VE)
2369	break;
2370
2371	QualType BTy = B.getType();
2372	(0) . __assert_fail ("BTy->isStructureOrClassType() && \"Base classes must be classes!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2372, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(BTy->isStructureOrClassType() && "Base classes must be classes!");
2373
2374	const CXXRecordDecl *BRD = BTy->getAsCXXRecordDecl();
2375	(0) . __assert_fail ("BRD && \"Base classes must be C++ classes!\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/RegionStore.cpp", 2375, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(BRD && "Base classes must be C++ classes!");
2376
2377	const CXXBaseObjectRegion *BR =
2378	MRMgr.getCXXBaseObjectRegion(BRD, R, /IsVirtual=/false);
2379
2380	NewB = bindStruct(NewB, BR, *VI);
2381
2382	++VI;
2383	}
2384	}
2385
2386	RecordDecl::field_iterator FI, FE;
2387
2388	for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) {
2389
2390	if (VI == VE)
2391	break;
2392
2393	// Skip any unnamed bitfields to stay in sync with the initializers.
2394	if (FI->isUnnamedBitfield())
2395	continue;
2396
2397	QualType FTy = FI->getType();
2398	const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
2399
2400	if (FTy->isArrayType())
2401	NewB = bindArray(NewB, FR, *VI);
2402	else if (FTy->isStructureOrClassType())
2403	NewB = bindStruct(NewB, FR, *VI);
2404	else
2405	NewB = bind(NewB, loc::MemRegionVal(FR), *VI);
2406	++VI;
2407	}
2408
2409	// There may be fewer values in the initialize list than the fields of struct.
2410	if (FI != FE) {
2411	NewB = NewB.addBinding(R, BindingKey::Default,
2412	svalBuilder.makeIntVal(0, false));
2413	}
2414
2415	return NewB;
2416	}
2417
2418	RegionBindingsRef
2419	RegionStoreManager::bindAggregate(RegionBindingsConstRef B,
2420	const TypedRegion *R,
2421	SVal Val) {
2422	// Remove the old bindings, using 'R' as the root of all regions
2423	// we will invalidate. Then add the new binding.
2424	return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val);
2425	}
2426
2427	//===----------------------------------------------------------------------===//
2428	// State pruning.
2429	//===----------------------------------------------------------------------===//
2430
2431	namespace {
2432	class RemoveDeadBindingsWorker
2433	: public ClusterAnalysis<RemoveDeadBindingsWorker> {
2434	SmallVector<const SymbolicRegion *, 12> Postponed;
2435	SymbolReaper &SymReaper;
2436	const StackFrameContext *CurrentLCtx;
2437
2438	public:
2439	RemoveDeadBindingsWorker(RegionStoreManager &rm,
2440	ProgramStateManager &stateMgr,
2441	RegionBindingsRef b, SymbolReaper &symReaper,
2442	const StackFrameContext *LCtx)
2443	: ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b),
2444	SymReaper(symReaper), CurrentLCtx(LCtx) {}
2445
2446	// Called by ClusterAnalysis.
2447	void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C);
2448	void VisitCluster(const MemRegion baseR, const ClusterBindings C);
2449	using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster;
2450
2451	using ClusterAnalysis::AddToWorkList;
2452
2453	bool AddToWorkList(const MemRegion *R);
2454
2455	bool UpdatePostponed();
2456	void VisitBinding(SVal V);
2457	};
2458	}
2459
2460	bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) {
2461	const MemRegion *BaseR = R->getBaseRegion();
2462	return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
2463	}
2464
2465	void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
2466	const ClusterBindings &C) {
2467
2468	if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
2469	if (SymReaper.isLive(VR))
2470	AddToWorkList(baseR, &C);
2471
2472	return;
2473	}
2474
2475	if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
2476	if (SymReaper.isLive(SR->getSymbol()))
2477	AddToWorkList(SR, &C);
2478	else
2479	Postponed.push_back(SR);
2480
2481	return;
2482	}
2483
2484	if (isa<NonStaticGlobalSpaceRegion>(baseR)) {
2485	AddToWorkList(baseR, &C);
2486	return;
2487	}
2488
2489	// CXXThisRegion in the current or parent location context is live.
2490	if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
2491	const auto *StackReg =
2492	cast<StackArgumentsSpaceRegion>(TR->getSuperRegion());
2493	const StackFrameContext *RegCtx = StackReg->getStackFrame();
2494	if (CurrentLCtx &&
2495	(RegCtx == CurrentLCtx \|\| RegCtx->isParentOf(CurrentLCtx)))
2496	AddToWorkList(TR, &C);
2497	}
2498	}
2499
2500	void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
2501	const ClusterBindings *C) {
2502	if (!C)
2503	return;
2504
2505	// Mark the symbol for any SymbolicRegion with live bindings as live itself.
2506	// This means we should continue to track that symbol.
2507	if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
2508	SymReaper.markLive(SymR->getSymbol());
2509
2510	for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
2511	// Element index of a binding key is live.
2512	SymReaper.markElementIndicesLive(I.getKey().getRegion());
2513
2514	VisitBinding(I.getData());
2515	}
2516	}
2517
2518	void RemoveDeadBindingsWorker::VisitBinding(SVal V) {
2519	// Is it a LazyCompoundVal? All referenced regions are live as well.
2520	if (Optional<nonloc::LazyCompoundVal> LCS =
2521	V.getAs<nonloc::LazyCompoundVal>()) {
2522
2523	const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS);
2524
2525	for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(),
2526	E = Vals.end();
2527	I != E; ++I)
2528	VisitBinding(*I);
2529
2530	return;
2531	}
2532
2533	// If V is a region, then add it to the worklist.
2534	if (const MemRegion *R = V.getAsRegion()) {
2535	AddToWorkList(R);
2536	SymReaper.markLive(R);
2537
2538	// All regions captured by a block are also live.
2539	if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
2540	BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(),
2541	E = BR->referenced_vars_end();
2542	for ( ; I != E; ++I)
2543	AddToWorkList(I.getCapturedRegion());
2544	}
2545	}
2546
2547
2548	// Update the set of live symbols.
2549	for (auto SI = V.symbol_begin(), SE = V.symbol_end(); SI!=SE; ++SI)
2550	SymReaper.markLive(*SI);
2551	}
2552
2553	bool RemoveDeadBindingsWorker::UpdatePostponed() {
2554	// See if any postponed SymbolicRegions are actually live now, after
2555	// having done a scan.
2556	bool Changed = false;
2557
2558	for (auto I = Postponed.begin(), E = Postponed.end(); I != E; ++I) {
2559	if (const SymbolicRegion SR = I) {
2560	if (SymReaper.isLive(SR->getSymbol())) {
2561	Changed \|= AddToWorkList(SR);
2562	*I = nullptr;
2563	}
2564	}
2565	}
2566
2567	return Changed;
2568	}
2569
2570	StoreRef RegionStoreManager::removeDeadBindings(Store store,
2571	const StackFrameContext *LCtx,
2572	SymbolReaper& SymReaper) {
2573	RegionBindingsRef B = getRegionBindings(store);
2574	RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);
2575	W.GenerateClusters();
2576
2577	// Enqueue the region roots onto the worklist.
2578	for (SymbolReaper::region_iterator I = SymReaper.region_begin(),
2579	E = SymReaper.region_end(); I != E; ++I) {
2580	W.AddToWorkList(*I);
2581	}
2582
2583	do W.RunWorkList(); while (W.UpdatePostponed());
2584
2585	// We have now scanned the store, marking reachable regions and symbols
2586	// as live. We now remove all the regions that are dead from the store
2587	// as well as update DSymbols with the set symbols that are now dead.
2588	for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) {
2589	const MemRegion *Base = I.getKey();
2590
2591	// If the cluster has been visited, we know the region has been marked.
2592	// Otherwise, remove the dead entry.
2593	if (!W.isVisited(Base))
2594	B = B.remove(Base);
2595	}
2596
2597	return StoreRef(B.asStore(), *this);
2598	}
2599
2600	//===----------------------------------------------------------------------===//
2601	// Utility methods.
2602	//===----------------------------------------------------------------------===//
2603
2604	void RegionStoreManager::print(Store store, raw_ostream &OS,
2605	const char* nl) {
2606	RegionBindingsRef B = getRegionBindings(store);
2607	OS << "Store (direct and default bindings), "
2608	<< B.asStore()
2609	<< " :" << nl;
2610	B.dump(OS, nl);
2611	}
2612

Clang Project