SValBuilder.h source code [clang_source_code/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h]

1	// SValBuilder.h - Construction of SVals from evaluating expressions -- 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 SValBuilder, a class that defines the interface for
10	// "symbolical evaluators" which construct an SVal from an expression.
11	//
12	//===----------------------------------------------------------------------===//
13
14	#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H
15	#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H
16
17	#include "clang/AST/ASTContext.h"
18	#include "clang/AST/DeclarationName.h"
19	#include "clang/AST/Expr.h"
20	#include "clang/AST/ExprObjC.h"
21	#include "clang/AST/Type.h"
22	#include "clang/Basic/LLVM.h"
23	#include "clang/Basic/LangOptions.h"
24	#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
25	#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
26	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
27	#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
28	#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
29	#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
30	#include "llvm/ADT/ImmutableList.h"
31	#include "llvm/ADT/Optional.h"
32	#include <cstdint>
33
34	namespace clang {
35
36	class BlockDecl;
37	class CXXBoolLiteralExpr;
38	class CXXMethodDecl;
39	class CXXRecordDecl;
40	class DeclaratorDecl;
41	class FunctionDecl;
42	class LocationContext;
43	class StackFrameContext;
44	class Stmt;
45
46	namespace ento {
47
48	class ConditionTruthVal;
49	class ProgramStateManager;
50	class StoreRef;
51
52	class SValBuilder {
53	virtual void anchor();
54
55	protected:
56	ASTContext &Context;
57
58	/// Manager of APSInt values.
59	BasicValueFactory BasicVals;
60
61	/// Manages the creation of symbols.
62	SymbolManager SymMgr;
63
64	/// Manages the creation of memory regions.
65	MemRegionManager MemMgr;
66
67	ProgramStateManager &StateMgr;
68
69	/// The scalar type to use for array indices.
70	const QualType ArrayIndexTy;
71
72	/// The width of the scalar type used for array indices.
73	const unsigned ArrayIndexWidth;
74
75	virtual SVal evalCastFromNonLoc(NonLoc val, QualType castTy) = 0;
76	virtual SVal evalCastFromLoc(Loc val, QualType castTy) = 0;
77
78	public:
79	// FIXME: Make these protected again once RegionStoreManager correctly
80	// handles loads from different bound value types.
81	virtual SVal dispatchCast(SVal val, QualType castTy) = 0;
82
83	public:
84	SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
85	ProgramStateManager &stateMgr)
86	: Context(context), BasicVals(context, alloc),
87	SymMgr(context, BasicVals, alloc), MemMgr(context, alloc),
88	StateMgr(stateMgr), ArrayIndexTy(context.LongLongTy),
89	ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {}
90
91	virtual ~SValBuilder() = default;
92
93	bool haveSameType(const SymExpr Sym1, const SymExpr Sym2) {
94	return haveSameType(Sym1->getType(), Sym2->getType());
95	}
96
97	bool haveSameType(QualType Ty1, QualType Ty2) {
98	// FIXME: Remove the second disjunct when we support symbolic
99	// truncation/extension.
100	return (Context.getCanonicalType(Ty1) == Context.getCanonicalType(Ty2) \|\|
101	(Ty1->isIntegralOrEnumerationType() &&
102	Ty2->isIntegralOrEnumerationType()));
103	}
104
105	SVal evalCast(SVal val, QualType castTy, QualType originalType);
106
107	// Handles casts of type CK_IntegralCast.
108	SVal evalIntegralCast(ProgramStateRef state, SVal val, QualType castTy,
109	QualType originalType);
110
111	virtual SVal evalMinus(NonLoc val) = 0;
112
113	virtual SVal evalComplement(NonLoc val) = 0;
114
115	/// Create a new value which represents a binary expression with two non-
116	/// location operands.
117	virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
118	NonLoc lhs, NonLoc rhs, QualType resultTy) = 0;
119
120	/// Create a new value which represents a binary expression with two memory
121	/// location operands.
122	virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
123	Loc lhs, Loc rhs, QualType resultTy) = 0;
124
125	/// Create a new value which represents a binary expression with a memory
126	/// location and non-location operands. For example, this would be used to
127	/// evaluate a pointer arithmetic operation.
128	virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
129	Loc lhs, NonLoc rhs, QualType resultTy) = 0;
130
131	/// Evaluates a given SVal. If the SVal has only one possible (integer) value,
132	/// that value is returned. Otherwise, returns NULL.
133	virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal val) = 0;
134
135	/// Simplify symbolic expressions within a given SVal. Return an SVal
136	/// that represents the same value, but is hopefully easier to work with
137	/// than the original SVal.
138	virtual SVal simplifySVal(ProgramStateRef State, SVal Val) = 0;
139
140	/// Constructs a symbolic expression for two non-location values.
141	SVal makeSymExprValNN(BinaryOperator::Opcode op,
142	NonLoc lhs, NonLoc rhs, QualType resultTy);
143
144	SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
145	SVal lhs, SVal rhs, QualType type);
146
147	/// \return Whether values in \p lhs and \p rhs are equal at \p state.
148	ConditionTruthVal areEqual(ProgramStateRef state, SVal lhs, SVal rhs);
149
150	SVal evalEQ(ProgramStateRef state, SVal lhs, SVal rhs);
151
152	DefinedOrUnknownSVal evalEQ(ProgramStateRef state, DefinedOrUnknownSVal lhs,
153	DefinedOrUnknownSVal rhs);
154
155	ASTContext &getContext() { return Context; }
156	const ASTContext &getContext() const { return Context; }
157
158	ProgramStateManager &getStateManager() { return StateMgr; }
159
160	QualType getConditionType() const {
161	return Context.getLangOpts().CPlusPlus ? Context.BoolTy : Context.IntTy;
162	}
163
164	QualType getArrayIndexType() const {
165	return ArrayIndexTy;
166	}
167
168	BasicValueFactory &getBasicValueFactory() { return BasicVals; }
169	const BasicValueFactory &getBasicValueFactory() const { return BasicVals; }
170
171	SymbolManager &getSymbolManager() { return SymMgr; }
172	const SymbolManager &getSymbolManager() const { return SymMgr; }
173
174	MemRegionManager &getRegionManager() { return MemMgr; }
175	const MemRegionManager &getRegionManager() const { return MemMgr; }
176
177	// Forwarding methods to SymbolManager.
178
179	const SymbolConjured* conjureSymbol(const Stmt *stmt,
180	const LocationContext *LCtx,
181	QualType type,
182	unsigned visitCount,
183	const void *symbolTag = nullptr) {
184	return SymMgr.conjureSymbol(stmt, LCtx, type, visitCount, symbolTag);
185	}
186
187	const SymbolConjured* conjureSymbol(const Expr *expr,
188	const LocationContext *LCtx,
189	unsigned visitCount,
190	const void *symbolTag = nullptr) {
191	return SymMgr.conjureSymbol(expr, LCtx, visitCount, symbolTag);
192	}
193
194	/// Construct an SVal representing '0' for the specified type.
195	DefinedOrUnknownSVal makeZeroVal(QualType type);
196
197	/// Make a unique symbol for value of region.
198	DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedValueRegion *region);
199
200	/// Create a new symbol with a unique 'name'.
201	///
202	/// We resort to conjured symbols when we cannot construct a derived symbol.
203	/// The advantage of symbols derived/built from other symbols is that we
204	/// preserve the relation between related(or even equivalent) expressions, so
205	/// conjured symbols should be used sparingly.
206	DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag,
207	const Expr *expr,
208	const LocationContext *LCtx,
209	unsigned count);
210	DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag,
211	const Expr *expr,
212	const LocationContext *LCtx,
213	QualType type,
214	unsigned count);
215	DefinedOrUnknownSVal conjureSymbolVal(const Stmt *stmt,
216	const LocationContext *LCtx,
217	QualType type,
218	unsigned visitCount);
219
220	/// Conjure a symbol representing heap allocated memory region.
221	///
222	/// Note, the expression should represent a location.
223	DefinedOrUnknownSVal getConjuredHeapSymbolVal(const Expr *E,
224	const LocationContext *LCtx,
225	unsigned Count);
226
227	DefinedOrUnknownSVal getDerivedRegionValueSymbolVal(
228	SymbolRef parentSymbol, const TypedValueRegion *region);
229
230	DefinedSVal getMetadataSymbolVal(const void *symbolTag,
231	const MemRegion *region,
232	const Expr *expr, QualType type,
233	const LocationContext *LCtx,
234	unsigned count);
235
236	DefinedSVal getMemberPointer(const DeclaratorDecl *DD);
237
238	DefinedSVal getFunctionPointer(const FunctionDecl *func);
239
240	DefinedSVal getBlockPointer(const BlockDecl *block, CanQualType locTy,
241	const LocationContext *locContext,
242	unsigned blockCount);
243
244	/// Returns the value of \p E, if it can be determined in a non-path-sensitive
245	/// manner.
246	///
247	/// If \p E is not a constant or cannot be modeled, returns \c None.
248	Optional<SVal> getConstantVal(const Expr *E);
249
250	NonLoc makeCompoundVal(QualType type, llvm::ImmutableList<SVal> vals) {
251	return nonloc::CompoundVal(BasicVals.getCompoundValData(type, vals));
252	}
253
254	NonLoc makeLazyCompoundVal(const StoreRef &store,
255	const TypedValueRegion *region) {
256	return nonloc::LazyCompoundVal(
257	BasicVals.getLazyCompoundValData(store, region));
258	}
259
260	NonLoc makePointerToMember(const DeclaratorDecl *DD) {
261	return nonloc::PointerToMember(DD);
262	}
263
264	NonLoc makePointerToMember(const PointerToMemberData *PTMD) {
265	return nonloc::PointerToMember(PTMD);
266	}
267
268	NonLoc makeZeroArrayIndex() {
269	return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy));
270	}
271
272	NonLoc makeArrayIndex(uint64_t idx) {
273	return nonloc::ConcreteInt(BasicVals.getValue(idx, ArrayIndexTy));
274	}
275
276	SVal convertToArrayIndex(SVal val);
277
278	nonloc::ConcreteInt makeIntVal(const IntegerLiteral* integer) {
279	return nonloc::ConcreteInt(
280	BasicVals.getValue(integer->getValue(),
281	integer->getType()->isUnsignedIntegerOrEnumerationType()));
282	}
283
284	nonloc::ConcreteInt makeBoolVal(const ObjCBoolLiteralExpr *boolean) {
285	return makeTruthVal(boolean->getValue(), boolean->getType());
286	}
287
288	nonloc::ConcreteInt makeBoolVal(const CXXBoolLiteralExpr *boolean);
289
290	nonloc::ConcreteInt makeIntVal(const llvm::APSInt& integer) {
291	return nonloc::ConcreteInt(BasicVals.getValue(integer));
292	}
293
294	loc::ConcreteInt makeIntLocVal(const llvm::APSInt &integer) {
295	return loc::ConcreteInt(BasicVals.getValue(integer));
296	}
297
298	NonLoc makeIntVal(const llvm::APInt& integer, bool isUnsigned) {
299	return nonloc::ConcreteInt(BasicVals.getValue(integer, isUnsigned));
300	}
301
302	DefinedSVal makeIntVal(uint64_t integer, QualType type) {
303	if (Loc::isLocType(type))
304	return loc::ConcreteInt(BasicVals.getValue(integer, type));
305
306	return nonloc::ConcreteInt(BasicVals.getValue(integer, type));
307	}
308
309	NonLoc makeIntVal(uint64_t integer, bool isUnsigned) {
310	return nonloc::ConcreteInt(BasicVals.getIntValue(integer, isUnsigned));
311	}
312
313	NonLoc makeIntValWithPtrWidth(uint64_t integer, bool isUnsigned) {
314	return nonloc::ConcreteInt(
315	BasicVals.getIntWithPtrWidth(integer, isUnsigned));
316	}
317
318	NonLoc makeLocAsInteger(Loc loc, unsigned bits) {
319	return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(loc, bits));
320	}
321
322	NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
323	const llvm::APSInt& rhs, QualType type);
324
325	NonLoc makeNonLoc(const llvm::APSInt& rhs, BinaryOperator::Opcode op,
326	const SymExpr *lhs, QualType type);
327
328	NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
329	const SymExpr *rhs, QualType type);
330
331	/// Create a NonLoc value for cast.
332	NonLoc makeNonLoc(const SymExpr *operand, QualType fromTy, QualType toTy);
333
334	nonloc::ConcreteInt makeTruthVal(bool b, QualType type) {
335	return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type));
336	}
337
338	nonloc::ConcreteInt makeTruthVal(bool b) {
339	return nonloc::ConcreteInt(BasicVals.getTruthValue(b));
340	}
341
342	/// Create NULL pointer, with proper pointer bit-width for given address
343	/// space.
344	/// \param type pointer type.
345	Loc makeNullWithType(QualType type) {
346	return loc::ConcreteInt(BasicVals.getZeroWithTypeSize(type));
347	}
348
349	Loc makeNull() {
350	return loc::ConcreteInt(BasicVals.getZeroWithPtrWidth());
351	}
352
353	Loc makeLoc(SymbolRef sym) {
354	return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
355	}
356
357	Loc makeLoc(const MemRegion* region) {
358	return loc::MemRegionVal(region);
359	}
360
361	Loc makeLoc(const AddrLabelExpr *expr) {
362	return loc::GotoLabel(expr->getLabel());
363	}
364
365	Loc makeLoc(const llvm::APSInt& integer) {
366	return loc::ConcreteInt(BasicVals.getValue(integer));
367	}
368
369	/// Make an SVal that represents the given symbol. This follows the convention
370	/// of representing Loc-type symbols (symbolic pointers and references)
371	/// as Loc values wrapping the symbol rather than as plain symbol values.
372	SVal makeSymbolVal(SymbolRef Sym) {
373	if (Loc::isLocType(Sym->getType()))
374	return makeLoc(Sym);
375	return nonloc::SymbolVal(Sym);
376	}
377
378	/// Return a memory region for the 'this' object reference.
379	loc::MemRegionVal getCXXThis(const CXXMethodDecl *D,
380	const StackFrameContext *SFC);
381
382	/// Return a memory region for the 'this' object reference.
383	loc::MemRegionVal getCXXThis(const CXXRecordDecl *D,
384	const StackFrameContext *SFC);
385	};
386
387	SValBuilder* createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
388	ASTContext &context,
389	ProgramStateManager &stateMgr);
390
391	} // namespace ento
392
393	} // namespace clang
394
395	#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H
396