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

source code of clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h