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

1	//===- SymbolManager.h - Management of Symbolic Values --------------------===//
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 SymbolManager, a class that manages symbolic values
10	// created for use by ExprEngine and related classes.
11	//
12	//===----------------------------------------------------------------------===//
13
14	#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
15	#include "clang/AST/ASTContext.h"
16	#include "clang/AST/Expr.h"
17	#include "clang/Analysis/Analyses/LiveVariables.h"
18	#include "clang/Analysis/AnalysisDeclContext.h"
19	#include "clang/Basic/LLVM.h"
20	#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
21	#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
22	#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
23	#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
24	#include "llvm/ADT/FoldingSet.h"
25	#include "llvm/ADT/STLExtras.h"
26	#include "llvm/Support/Casting.h"
27	#include "llvm/Support/Compiler.h"
28	#include "llvm/Support/ErrorHandling.h"
29	#include "llvm/Support/raw_ostream.h"
30	#include <cassert>
31
32	using namespace clang;
33	using namespace ento;
34
35	void SymExpr::anchor() {}
36
37	LLVM_DUMP_METHOD void SymExpr::dump() const {
38	dumpToStream(llvm::errs());
39	}
40
41	void SymIntExpr::dumpToStream(raw_ostream &os) const {
42	os << '(';
43	getLHS()->dumpToStream(os);
44	os << ") "
45	<< BinaryOperator::getOpcodeStr(getOpcode()) << ' ';
46	if (getRHS().isUnsigned())
47	os << getRHS().getZExtValue();
48	else
49	os << getRHS().getSExtValue();
50	if (getRHS().isUnsigned())
51	os << 'U';
52	}
53
54	void IntSymExpr::dumpToStream(raw_ostream &os) const {
55	if (getLHS().isUnsigned())
56	os << getLHS().getZExtValue();
57	else
58	os << getLHS().getSExtValue();
59	if (getLHS().isUnsigned())
60	os << 'U';
61	os << ' '
62	<< BinaryOperator::getOpcodeStr(getOpcode())
63	<< " (";
64	getRHS()->dumpToStream(os);
65	os << ')';
66	}
67
68	void SymSymExpr::dumpToStream(raw_ostream &os) const {
69	os << '(';
70	getLHS()->dumpToStream(os);
71	os << ") "
72	<< BinaryOperator::getOpcodeStr(getOpcode())
73	<< " (";
74	getRHS()->dumpToStream(os);
75	os << ')';
76	}
77
78	void SymbolCast::dumpToStream(raw_ostream &os) const {
79	os << '(' << ToTy.getAsString() << ") (";
80	Operand->dumpToStream(os);
81	os << ')';
82	}
83
84	void SymbolConjured::dumpToStream(raw_ostream &os) const {
85	os << "conj_$" << getSymbolID() << '{' << T.getAsString() << ", LC"
86	<< LCtx->getID();
87	if (S)
88	os << ", S" << S->getID(LCtx->getDecl()->getASTContext());
89	else
90	os << ", no stmt";
91	os << ", #" << Count << '}';
92	}
93
94	void SymbolDerived::dumpToStream(raw_ostream &os) const {
95	os << "derived_$" << getSymbolID() << '{'
96	<< getParentSymbol() << ',' << getRegion() << '}';
97	}
98
99	void SymbolExtent::dumpToStream(raw_ostream &os) const {
100	os << "extent_$" << getSymbolID() << '{' << getRegion() << '}';
101	}
102
103	void SymbolMetadata::dumpToStream(raw_ostream &os) const {
104	os << "meta_$" << getSymbolID() << '{'
105	<< getRegion() << ',' << T.getAsString() << '}';
106	}
107
108	void SymbolData::anchor() {}
109
110	void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
111	os << "reg_$" << getSymbolID()
112	<< '<' << getType().getAsString() << ' ' << R << '>';
113	}
114
115	bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
116	return itr == X.itr;
117	}
118
119	bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
120	return itr != X.itr;
121	}
122
123	SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
124	itr.push_back(SE);
125	}
126
127	SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
128	(0) . __assert_fail ("!itr.empty() && \"attempting to iterate on an 'end' iterator\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp", 128, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
129	expand();
130	return *this;
131	}
132
133	SymbolRef SymExpr::symbol_iterator::operator*() {
134	(0) . __assert_fail ("!itr.empty() && \"attempting to dereference an 'end' iterator\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp", 134, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!itr.empty() && "attempting to dereference an 'end' iterator");
135	return itr.back();
136	}
137
138	void SymExpr::symbol_iterator::expand() {
139	const SymExpr *SE = itr.pop_back_val();
140
141	switch (SE->getKind()) {
142	case SymExpr::SymbolRegionValueKind:
143	case SymExpr::SymbolConjuredKind:
144	case SymExpr::SymbolDerivedKind:
145	case SymExpr::SymbolExtentKind:
146	case SymExpr::SymbolMetadataKind:
147	return;
148	case SymExpr::SymbolCastKind:
149	itr.push_back(cast<SymbolCast>(SE)->getOperand());
150	return;
151	case SymExpr::SymIntExprKind:
152	itr.push_back(cast<SymIntExpr>(SE)->getLHS());
153	return;
154	case SymExpr::IntSymExprKind:
155	itr.push_back(cast<IntSymExpr>(SE)->getRHS());
156	return;
157	case SymExpr::SymSymExprKind: {
158	const auto *x = cast<SymSymExpr>(SE);
159	itr.push_back(x->getLHS());
160	itr.push_back(x->getRHS());
161	return;
162	}
163	}
164	llvm_unreachable("unhandled expansion case");
165	}
166
167	const SymbolRegionValue*
168	SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) {
169	llvm::FoldingSetNodeID profile;
170	SymbolRegionValue::Profile(profile, R);
171	void *InsertPos;
172	SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
173	if (!SD) {
174	SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>();
175	new (SD) SymbolRegionValue(SymbolCounter, R);
176	DataSet.InsertNode(SD, InsertPos);
177	++SymbolCounter;
178	}
179
180	return cast<SymbolRegionValue>(SD);
181	}
182
183	const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E,
184	const LocationContext *LCtx,
185	QualType T,
186	unsigned Count,
187	const void *SymbolTag) {
188	llvm::FoldingSetNodeID profile;
189	SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag);
190	void *InsertPos;
191	SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
192	if (!SD) {
193	SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>();
194	new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag);
195	DataSet.InsertNode(SD, InsertPos);
196	++SymbolCounter;
197	}
198
199	return cast<SymbolConjured>(SD);
200	}
201
202	const SymbolDerived*
203	SymbolManager::getDerivedSymbol(SymbolRef parentSymbol,
204	const TypedValueRegion *R) {
205	llvm::FoldingSetNodeID profile;
206	SymbolDerived::Profile(profile, parentSymbol, R);
207	void *InsertPos;
208	SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
209	if (!SD) {
210	SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>();
211	new (SD) SymbolDerived(SymbolCounter, parentSymbol, R);
212	DataSet.InsertNode(SD, InsertPos);
213	++SymbolCounter;
214	}
215
216	return cast<SymbolDerived>(SD);
217	}
218
219	const SymbolExtent*
220	SymbolManager::getExtentSymbol(const SubRegion *R) {
221	llvm::FoldingSetNodeID profile;
222	SymbolExtent::Profile(profile, R);
223	void *InsertPos;
224	SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
225	if (!SD) {
226	SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>();
227	new (SD) SymbolExtent(SymbolCounter, R);
228	DataSet.InsertNode(SD, InsertPos);
229	++SymbolCounter;
230	}
231
232	return cast<SymbolExtent>(SD);
233	}
234
235	const SymbolMetadata *
236	SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T,
237	const LocationContext *LCtx,
238	unsigned Count, const void *SymbolTag) {
239	llvm::FoldingSetNodeID profile;
240	SymbolMetadata::Profile(profile, R, S, T, LCtx, Count, SymbolTag);
241	void *InsertPos;
242	SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
243	if (!SD) {
244	SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>();
245	new (SD) SymbolMetadata(SymbolCounter, R, S, T, LCtx, Count, SymbolTag);
246	DataSet.InsertNode(SD, InsertPos);
247	++SymbolCounter;
248	}
249
250	return cast<SymbolMetadata>(SD);
251	}
252
253	const SymbolCast*
254	SymbolManager::getCastSymbol(const SymExpr *Op,
255	QualType From, QualType To) {
256	llvm::FoldingSetNodeID ID;
257	SymbolCast::Profile(ID, Op, From, To);
258	void *InsertPos;
259	SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
260	if (!data) {
261	data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>();
262	new (data) SymbolCast(Op, From, To);
263	DataSet.InsertNode(data, InsertPos);
264	}
265
266	return cast<SymbolCast>(data);
267	}
268
269	const SymIntExpr SymbolManager::getSymIntExpr(const SymExpr lhs,
270	BinaryOperator::Opcode op,
271	const llvm::APSInt& v,
272	QualType t) {
273	llvm::FoldingSetNodeID ID;
274	SymIntExpr::Profile(ID, lhs, op, v, t);
275	void *InsertPos;
276	SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
277
278	if (!data) {
279	data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>();
280	new (data) SymIntExpr(lhs, op, v, t);
281	DataSet.InsertNode(data, InsertPos);
282	}
283
284	return cast<SymIntExpr>(data);
285	}
286
287	const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs,
288	BinaryOperator::Opcode op,
289	const SymExpr *rhs,
290	QualType t) {
291	llvm::FoldingSetNodeID ID;
292	IntSymExpr::Profile(ID, lhs, op, rhs, t);
293	void *InsertPos;
294	SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
295
296	if (!data) {
297	data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>();
298	new (data) IntSymExpr(lhs, op, rhs, t);
299	DataSet.InsertNode(data, InsertPos);
300	}
301
302	return cast<IntSymExpr>(data);
303	}
304
305	const SymSymExpr SymbolManager::getSymSymExpr(const SymExpr lhs,
306	BinaryOperator::Opcode op,
307	const SymExpr *rhs,
308	QualType t) {
309	llvm::FoldingSetNodeID ID;
310	SymSymExpr::Profile(ID, lhs, op, rhs, t);
311	void *InsertPos;
312	SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
313
314	if (!data) {
315	data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>();
316	new (data) SymSymExpr(lhs, op, rhs, t);
317	DataSet.InsertNode(data, InsertPos);
318	}
319
320	return cast<SymSymExpr>(data);
321	}
322
323	QualType SymbolConjured::getType() const {
324	return T;
325	}
326
327	QualType SymbolDerived::getType() const {
328	return R->getValueType();
329	}
330
331	QualType SymbolExtent::getType() const {
332	ASTContext &Ctx = R->getMemRegionManager()->getContext();
333	return Ctx.getSizeType();
334	}
335
336	QualType SymbolMetadata::getType() const {
337	return T;
338	}
339
340	QualType SymbolRegionValue::getType() const {
341	return R->getValueType();
342	}
343
344	SymbolManager::~SymbolManager() {
345	llvm::DeleteContainerSeconds(SymbolDependencies);
346	}
347
348	bool SymbolManager::canSymbolicate(QualType T) {
349	T = T.getCanonicalType();
350
351	if (Loc::isLocType(T))
352	return true;
353
354	if (T->isIntegralOrEnumerationType())
355	return true;
356
357	if (T->isRecordType() && !T->isUnionType())
358	return true;
359
360	return false;
361	}
362
363	void SymbolManager::addSymbolDependency(const SymbolRef Primary,
364	const SymbolRef Dependent) {
365	SymbolDependTy::iterator I = SymbolDependencies.find(Primary);
366	SymbolRefSmallVectorTy *dependencies = nullptr;
367	if (I == SymbolDependencies.end()) {
368	dependencies = new SymbolRefSmallVectorTy();
369	SymbolDependencies[Primary] = dependencies;
370	} else {
371	dependencies = I->second;
372	}
373	dependencies->push_back(Dependent);
374	}
375
376	const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
377	const SymbolRef Primary) {
378	SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
379	if (I == SymbolDependencies.end())
380	return nullptr;
381	return I->second;
382	}
383
384	void SymbolReaper::markDependentsLive(SymbolRef sym) {
385	// Do not mark dependents more then once.
386	SymbolMapTy::iterator LI = TheLiving.find(sym);
387	(0) . __assert_fail ("LI != TheLiving.end() && \"The primary symbol is not live.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp", 387, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(LI != TheLiving.end() && "The primary symbol is not live.");
388	if (LI->second == HaveMarkedDependents)
389	return;
390	LI->second = HaveMarkedDependents;
391
392	if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
393	for (const auto I : *Deps) {
394	if (TheLiving.find(I) != TheLiving.end())
395	continue;
396	markLive(I);
397	}
398	}
399	}
400
401	void SymbolReaper::markLive(SymbolRef sym) {
402	TheLiving[sym] = NotProcessed;
403	markDependentsLive(sym);
404	}
405
406	void SymbolReaper::markLive(const MemRegion *region) {
407	RegionRoots.insert(region->getBaseRegion());
408	markElementIndicesLive(region);
409	}
410
411	void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
412	for (auto SR = dyn_cast<SubRegion>(region); SR;
413	SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {
414	if (const auto ER = dyn_cast<ElementRegion>(SR)) {
415	SVal Idx = ER->getIndex();
416	for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
417	markLive(*SI);
418	}
419	}
420	}
421
422	void SymbolReaper::markInUse(SymbolRef sym) {
423	if (isa<SymbolMetadata>(sym))
424	MetadataInUse.insert(sym);
425	}
426
427	bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
428	// TODO: For now, liveness of a memory region is equivalent to liveness of its
429	// base region. In fact we can do a bit better: say, if a particular FieldDecl
430	// is not used later in the path, we can diagnose a leak of a value within
431	// that field earlier than, say, the variable that contains the field dies.
432	MR = MR->getBaseRegion();
433
434	if (RegionRoots.count(MR))
435	return true;
436
437	if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
438	return isLive(SR->getSymbol());
439
440	if (const auto *VR = dyn_cast<VarRegion>(MR))
441	return isLive(VR, true);
442
443	// FIXME: This is a gross over-approximation. What we really need is a way to
444	// tell if anything still refers to this region. Unlike SymbolicRegions,
445	// AllocaRegions don't have associated symbols, though, so we don't actually
446	// have a way to track their liveness.
447	if (isa<AllocaRegion>(MR))
448	return true;
449
450	if (isa<CXXThisRegion>(MR))
451	return true;
452
453	if (isa<MemSpaceRegion>(MR))
454	return true;
455
456	if (isa<CodeTextRegion>(MR))
457	return true;
458
459	return false;
460	}
461
462	bool SymbolReaper::isLive(SymbolRef sym) {
463	if (TheLiving.count(sym)) {
464	markDependentsLive(sym);
465	return true;
466	}
467
468	bool KnownLive;
469
470	switch (sym->getKind()) {
471	case SymExpr::SymbolRegionValueKind:
472	KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion());
473	break;
474	case SymExpr::SymbolConjuredKind:
475	KnownLive = false;
476	break;
477	case SymExpr::SymbolDerivedKind:
478	KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
479	break;
480	case SymExpr::SymbolExtentKind:
481	KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
482	break;
483	case SymExpr::SymbolMetadataKind:
484	KnownLive = MetadataInUse.count(sym) &&
485	isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
486	if (KnownLive)
487	MetadataInUse.erase(sym);
488	break;
489	case SymExpr::SymIntExprKind:
490	KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
491	break;
492	case SymExpr::IntSymExprKind:
493	KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
494	break;
495	case SymExpr::SymSymExprKind:
496	KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
497	isLive(cast<SymSymExpr>(sym)->getRHS());
498	break;
499	case SymExpr::SymbolCastKind:
500	KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
501	break;
502	}
503
504	if (KnownLive)
505	markLive(sym);
506
507	return KnownLive;
508	}
509
510	bool
511	SymbolReaper::isLive(const Stmt ExprVal, const LocationContext ELCtx) const {
512	if (LCtx == nullptr)
513	return false;
514
515	if (LCtx != ELCtx) {
516	// If the reaper's location context is a parent of the expression's
517	// location context, then the expression value is now "out of scope".
518	if (LCtx->isParentOf(ELCtx))
519	return false;
520	return true;
521	}
522
523	// If no statement is provided, everything is this and parent contexts is live.
524	if (!Loc)
525	return true;
526
527	return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
528	}
529
530	bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
531	const StackFrameContext *VarContext = VR->getStackFrame();
532
533	if (!VarContext)
534	return true;
535
536	if (!LCtx)
537	return false;
538	const StackFrameContext *CurrentContext = LCtx->getStackFrame();
539
540	if (VarContext == CurrentContext) {
541	// If no statement is provided, everything is live.
542	if (!Loc)
543	return true;
544
545	if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
546	return true;
547
548	if (!includeStoreBindings)
549	return false;
550
551	unsigned &cachedQuery =
552	const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
553
554	if (cachedQuery) {
555	return cachedQuery == 1;
556	}
557
558	// Query the store to see if the region occurs in any live bindings.
559	if (Store store = reapedStore.getStore()) {
560	bool hasRegion =
561	reapedStore.getStoreManager().includedInBindings(store, VR);
562	cachedQuery = hasRegion ? 1 : 2;
563	return hasRegion;
564	}
565
566	return false;
567	}
568
569	return VarContext->isParentOf(CurrentContext);
570	}
571