Coverage Report

Created: 2021-08-24 07:12

/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 BlockDecl;
37
class CXXBoolLiteralExpr;
38
class CXXMethodDecl;
39
class CXXRecordDecl;
40
class DeclaratorDecl;
41
class FunctionDecl;
42
class LocationContext;
43
class StackFrameContext;
44
class Stmt;
45
46
namespace ento {
47
48
class ConditionTruthVal;
49
class ProgramStateManager;
50
class StoreRef;
51
52
class SValBuilder {
53
  virtual void anchor();
54
55
protected:
56
  ASTContext &Context;
57
58
  /// Manager of APSInt values.
59
  BasicValueFactory BasicVals;
60
61
  /// Manages the creation of symbols.
62
  SymbolManager SymMgr;
63
64
  /// Manages the creation of memory regions.
65
  MemRegionManager MemMgr;
66
67
  ProgramStateManager &StateMgr;
68
69
  /// The scalar type to use for array indices.
70
  const QualType ArrayIndexTy;
71
72
  /// The width of the scalar type used for array indices.
73
  const unsigned ArrayIndexWidth;
74
75
  SVal evalCastKind(UndefinedVal V, QualType CastTy, QualType OriginalTy);
76
  SVal evalCastKind(UnknownVal V, QualType CastTy, QualType OriginalTy);
77
  SVal evalCastKind(Loc V, QualType CastTy, QualType OriginalTy);
78
  SVal evalCastKind(NonLoc V, QualType CastTy, QualType OriginalTy);
79
  SVal evalCastSubKind(loc::ConcreteInt V, QualType CastTy,
80
                       QualType OriginalTy);
81
  SVal evalCastSubKind(loc::GotoLabel V, QualType CastTy, QualType OriginalTy);
82
  SVal evalCastSubKind(loc::MemRegionVal V, QualType CastTy,
83
                       QualType OriginalTy);
84
  SVal evalCastSubKind(nonloc::CompoundVal V, QualType CastTy,
85
                       QualType OriginalTy);
86
  SVal evalCastSubKind(nonloc::ConcreteInt V, QualType CastTy,
87
                       QualType OriginalTy);
88
  SVal evalCastSubKind(nonloc::LazyCompoundVal V, QualType CastTy,
89
                       QualType OriginalTy);
90
  SVal evalCastSubKind(nonloc::LocAsInteger V, QualType CastTy,
91
                       QualType OriginalTy);
92
  SVal evalCastSubKind(nonloc::SymbolVal V, QualType CastTy,
93
                       QualType OriginalTy);
94
  SVal evalCastSubKind(nonloc::PointerToMember V, QualType CastTy,
95
                       QualType OriginalTy);
96
97
public:
98
  SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
99
              ProgramStateManager &stateMgr)
100
      : Context(context), BasicVals(context, alloc),
101
        SymMgr(context, BasicVals, alloc), MemMgr(context, alloc),
102
        StateMgr(stateMgr), ArrayIndexTy(context.LongLongTy),
103
14.3k
        ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {}
104
105
14.3k
  virtual ~SValBuilder() = default;
106
107
0
  bool haveSameType(const SymExpr *Sym1, const SymExpr *Sym2) {
108
0
    return haveSameType(Sym1->getType(), Sym2->getType());
109
0
  }
110
111
117k
  bool haveSameType(QualType Ty1, QualType Ty2) {
112
    // FIXME: Remove the second disjunct when we support symbolic
113
    // truncation/extension.
114
117k
    return (Context.getCanonicalType(Ty1) == Context.getCanonicalType(Ty2) ||
115
117k
            
(36.4k
Ty1->isIntegralOrEnumerationType()36.4k
&&
116
36.4k
             
Ty2->isIntegralOrEnumerationType()36.4k
));
117
117k
  }
118
119
  SVal evalCast(SVal V, QualType CastTy, QualType OriginalTy);
120
121
  // Handles casts of type CK_IntegralCast.
122
  SVal evalIntegralCast(ProgramStateRef state, SVal val, QualType castTy,
123
                        QualType originalType);
124
125
  virtual SVal evalMinus(NonLoc val) = 0;
126
127
  virtual SVal evalComplement(NonLoc val) = 0;
128
129
  /// Create a new value which represents a binary expression with two non-
130
  /// location operands.
131
  virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
132
                           NonLoc lhs, NonLoc rhs, QualType resultTy) = 0;
133
134
  /// Create a new value which represents a binary expression with two memory
135
  /// location operands.
136
  virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
137
                           Loc lhs, Loc rhs, QualType resultTy) = 0;
138
139
  /// Create a new value which represents a binary expression with a memory
140
  /// location and non-location operands. For example, this would be used to
141
  /// evaluate a pointer arithmetic operation.
142
  virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
143
                           Loc lhs, NonLoc rhs, QualType resultTy) = 0;
144
145
  /// Evaluates a given SVal. If the SVal has only one possible (integer) value,
146
  /// that value is returned. Otherwise, returns NULL.
147
  virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal val) = 0;
148
149
  /// Simplify symbolic expressions within a given SVal. Return an SVal
150
  /// that represents the same value, but is hopefully easier to work with
151
  /// than the original SVal.
152
  virtual SVal simplifySVal(ProgramStateRef State, SVal Val) = 0;
153
154
  /// Constructs a symbolic expression for two non-location values.
155
  SVal makeSymExprValNN(BinaryOperator::Opcode op,
156
                        NonLoc lhs, NonLoc rhs, QualType resultTy);
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.49M
  ASTContext &getContext() { return Context; }
170
0
  const ASTContext &getContext() const { return Context; }
171
172
0
  ProgramStateManager &getStateManager() { return StateMgr; }
173
174
57.0k
  QualType getConditionType() const {
175
57.0k
    return Context.getLangOpts().CPlusPlus ? 
Context.BoolTy36.8k
:
Context.IntTy20.1k
;
176
57.0k
  }
177
178
41.9k
  QualType getArrayIndexType() const {
179
41.9k
    return ArrayIndexTy;
180
41.9k
  }
181
182
264k
  BasicValueFactory &getBasicValueFactory() { return BasicVals; }
183
0
  const BasicValueFactory &getBasicValueFactory() const { return BasicVals; }
184
185
55.2k
  SymbolManager &getSymbolManager() { return SymMgr; }
186
0
  const SymbolManager &getSymbolManager() const { return SymMgr; }
187
188
231k
  MemRegionManager &getRegionManager() { return MemMgr; }
189
0
  const MemRegionManager &getRegionManager() const { return MemMgr; }
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
0
                                      const void *symbolTag = nullptr) {
198
0
    return SymMgr.conjureSymbol(stmt, LCtx, type, visitCount, symbolTag);
199
0
  }
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.14k
  NonLoc makeCompoundVal(QualType type, llvm::ImmutableList<SVal> vals) {
273
1.14k
    return nonloc::CompoundVal(BasicVals.getCompoundValData(type, vals));
274
1.14k
  }
275
276
  NonLoc makeLazyCompoundVal(const StoreRef &store,
277
56.0k
                             const TypedValueRegion *region) {
278
56.0k
    return nonloc::LazyCompoundVal(
279
56.0k
        BasicVals.getLazyCompoundValData(store, region));
280
56.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
19.2k
  NonLoc makeZeroArrayIndex() {
291
19.2k
    return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy));
292
19.2k
  }
293
294
14.3k
  NonLoc makeArrayIndex(uint64_t idx) {
295
14.3k
    return nonloc::ConcreteInt(BasicVals.getValue(idx, ArrayIndexTy));
296
14.3k
  }
297
298
  SVal convertToArrayIndex(SVal val);
299
300
67.5k
  nonloc::ConcreteInt makeIntVal(const IntegerLiteral* integer) {
301
67.5k
    return nonloc::ConcreteInt(
302
67.5k
        BasicVals.getValue(integer->getValue(),
303
67.5k
                     integer->getType()->isUnsignedIntegerOrEnumerationType()));
304
67.5k
  }
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
85.3k
  nonloc::ConcreteInt makeIntVal(const llvm::APSInt& integer) {
313
85.3k
    return nonloc::ConcreteInt(BasicVals.getValue(integer));
314
85.3k
  }
315
316
495
  loc::ConcreteInt makeIntLocVal(const llvm::APSInt &integer) {
317
495
    return loc::ConcreteInt(BasicVals.getValue(integer));
318
495
  }
319
320
0
  NonLoc makeIntVal(const llvm::APInt& integer, bool isUnsigned) {
321
0
    return nonloc::ConcreteInt(BasicVals.getValue(integer, isUnsigned));
322
0
  }
323
324
55.8k
  DefinedSVal makeIntVal(uint64_t integer, QualType type) {
325
55.8k
    if (Loc::isLocType(type))
326
260
      return loc::ConcreteInt(BasicVals.getValue(integer, type));
327
328
55.5k
    return nonloc::ConcreteInt(BasicVals.getValue(integer, type));
329
55.8k
  }
330
331
715
  NonLoc makeIntVal(uint64_t integer, bool isUnsigned) {
332
715
    return nonloc::ConcreteInt(BasicVals.getIntValue(integer, isUnsigned));
333
715
  }
334
335
151
  NonLoc makeIntValWithPtrWidth(uint64_t integer, bool isUnsigned) {
336
151
    return nonloc::ConcreteInt(
337
151
        BasicVals.getIntWithPtrWidth(integer, isUnsigned));
338
151
  }
339
340
158
  NonLoc makeLocAsInteger(Loc loc, unsigned bits) {
341
158
    return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(loc, bits));
342
158
  }
343
344
  NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
345
                    const llvm::APSInt& rhs, QualType type);
346
347
  NonLoc makeNonLoc(const llvm::APSInt& rhs, BinaryOperator::Opcode op,
348
                    const SymExpr *lhs, QualType type);
349
350
  NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
351
                    const SymExpr *rhs, QualType type);
352
353
  /// Create a NonLoc value for cast.
354
  NonLoc makeNonLoc(const SymExpr *operand, QualType fromTy, QualType toTy);
355
356
553k
  nonloc::ConcreteInt makeTruthVal(bool b, QualType type) {
357
553k
    return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type));
358
553k
  }
359
360
3.39k
  nonloc::ConcreteInt makeTruthVal(bool b) {
361
3.39k
    return nonloc::ConcreteInt(BasicVals.getTruthValue(b));
362
3.39k
  }
363
364
  /// Create NULL pointer, with proper pointer bit-width for given address
365
  /// space.
366
  /// \param type pointer type.
367
281
  Loc makeNullWithType(QualType type) {
368
281
    return loc::ConcreteInt(BasicVals.getZeroWithTypeSize(type));
369
281
  }
370
371
8.60k
  Loc makeNull() {
372
8.60k
    return loc::ConcreteInt(BasicVals.getZeroWithPtrWidth());
373
8.60k
  }
374
375
238k
  Loc makeLoc(SymbolRef sym) {
376
238k
    return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
377
238k
  }
378
379
242k
  Loc makeLoc(const MemRegion* region) {
380
242k
    return loc::MemRegionVal(region);
381
242k
  }
382
383
96
  Loc makeLoc(const AddrLabelExpr *expr) {
384
96
    return loc::GotoLabel(expr->getLabel());
385
96
  }
386
387
20
  Loc makeLoc(const llvm::APSInt& integer) {
388
20
    return loc::ConcreteInt(BasicVals.getValue(integer));
389
20
  }
390
391
  /// Return MemRegionVal on success cast, otherwise return None.
392
  Optional<loc::MemRegionVal> getCastedMemRegionVal(const MemRegion *region,
393
                                                    QualType type);
394
395
  /// Make an SVal that represents the given symbol. This follows the convention
396
  /// of representing Loc-type symbols (symbolic pointers and references)
397
  /// as Loc values wrapping the symbol rather than as plain symbol values.
398
2.72M
  SVal makeSymbolVal(SymbolRef Sym) {
399
2.72M
    if (Loc::isLocType(Sym->getType()))
400
237k
      return makeLoc(Sym);
401
2.49M
    return nonloc::SymbolVal(Sym);
402
2.72M
  }
403
404
  /// Return a memory region for the 'this' object reference.
405
  loc::MemRegionVal getCXXThis(const CXXMethodDecl *D,
406
                               const StackFrameContext *SFC);
407
408
  /// Return a memory region for the 'this' object reference.
409
  loc::MemRegionVal getCXXThis(const CXXRecordDecl *D,
410
                               const StackFrameContext *SFC);
411
};
412
413
SValBuilder* createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
414
                                     ASTContext &context,
415
                                     ProgramStateManager &stateMgr);
416
417
} // namespace ento
418
419
} // namespace clang
420
421
#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H