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