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