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 | |
35 | namespace clang { |
36 | |
37 | class AnalyzerOptions; |
38 | class BlockDecl; |
39 | class CXXBoolLiteralExpr; |
40 | class CXXMethodDecl; |
41 | class CXXRecordDecl; |
42 | class DeclaratorDecl; |
43 | class FunctionDecl; |
44 | class LocationContext; |
45 | class StackFrameContext; |
46 | class Stmt; |
47 | |
48 | namespace ento { |
49 | |
50 | class CallEvent; |
51 | class ConditionTruthVal; |
52 | class ProgramStateManager; |
53 | class StoreRef; |
54 | class SValBuilder { |
55 | virtual void anchor(); |
56 | |
57 | protected: |
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 | |
79 | public: |
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 | |
401 | SValBuilder* 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 |
Definitions
- SValBuilder
- ~SValBuilder
- getContext
- getContext
- getStateManager
- getConditionType
- getArrayIndexType
- getBasicValueFactory
- getBasicValueFactory
- getSymbolManager
- getSymbolManager
- getRegionManager
- getRegionManager
- getAnalyzerOptions
- conjureSymbol
- makeCompoundVal
- makeLazyCompoundVal
- makePointerToMember
- makePointerToMember
- makeZeroArrayIndex
- makeArrayIndex
- makeIntVal
- makeBoolVal
- makeIntVal
- makeIntLocVal
- makeIntVal
- makeIntVal
- makeIntVal
- makeIntValWithWidth
- makeLocAsInteger
- makeTruthVal
- makeTruthVal
- makeNullWithType
- makeLoc
- makeLoc
- makeLoc
- makeLoc
Improve your Profiling and Debugging skills
Find out more