Coverage Report

Created: 2022-07-16 07:03

/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