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

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