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

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