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