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 | |
34 | namespace clang { |
35 | |
36 | class AnalyzerOptions; |
37 | class BlockDecl; |
38 | class CXXBoolLiteralExpr; |
39 | class CXXMethodDecl; |
40 | class CXXRecordDecl; |
41 | class DeclaratorDecl; |
42 | class FunctionDecl; |
43 | class LocationContext; |
44 | class StackFrameContext; |
45 | class Stmt; |
46 | |
47 | namespace ento { |
48 | |
49 | class ConditionTruthVal; |
50 | class ProgramStateManager; |
51 | class StoreRef; |
52 | |
53 | class SValBuilder { |
54 | virtual void anchor(); |
55 | |
56 | protected: |
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 | |
78 | public: |
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 | |
411 | SValBuilder* 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 | |