Coverage Report

Created: 2018-11-16 02:38

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/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
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
//  This file defines SValBuilder, a class that defines the interface for
11
//  "symbolical evaluators" which construct an SVal from an expression.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H
16
#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H
17
18
#include "clang/AST/ASTContext.h"
19
#include "clang/AST/DeclarationName.h"
20
#include "clang/AST/Expr.h"
21
#include "clang/AST/ExprObjC.h"
22
#include "clang/AST/Type.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 "llvm/ADT/Optional.h"
33
#include <cstdint>
34
35
namespace clang {
36
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
  /// The scalar type to use for array indices.
71
  const QualType ArrayIndexTy;
72
73
  /// The width of the scalar type used for array indices.
74
  const unsigned ArrayIndexWidth;
75
76
  virtual SVal evalCastFromNonLoc(NonLoc val, QualType castTy) = 0;
77
  virtual SVal evalCastFromLoc(Loc val, QualType castTy) = 0;
78
79
public:
80
  // FIXME: Make these protected again once RegionStoreManager correctly
81
  // handles loads from different bound value types.
82
  virtual SVal dispatchCast(SVal val, QualType castTy) = 0;
83
84
public:
85
  SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
86
              ProgramStateManager &stateMgr)
87
      : Context(context), BasicVals(context, alloc),
88
        SymMgr(context, BasicVals, alloc), MemMgr(context, alloc),
89
        StateMgr(stateMgr), ArrayIndexTy(context.LongLongTy),
90
9.80k
        ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {}
91
92
9.80k
  virtual ~SValBuilder() = default;
93
94
0
  bool haveSameType(const SymExpr *Sym1, const SymExpr *Sym2) {
95
0
    return haveSameType(Sym1->getType(), Sym2->getType());
96
0
  }
97
98
95.6k
  bool haveSameType(QualType Ty1, QualType Ty2) {
99
95.6k
    // FIXME: Remove the second disjunct when we support symbolic
100
95.6k
    // truncation/extension.
101
95.6k
    return (Context.getCanonicalType(Ty1) == Context.getCanonicalType(Ty2) ||
102
95.6k
            
(36.8k
Ty1->isIntegralOrEnumerationType()36.8k
&&
103
36.8k
             
Ty2->isIntegralOrEnumerationType()36.8k
));
104
95.6k
  }
105
106
  SVal evalCast(SVal val, QualType castTy, QualType originalType);
107
108
  // Handles casts of type CK_IntegralCast.
109
  SVal evalIntegralCast(ProgramStateRef state, SVal val, QualType castTy,
110
                        QualType originalType);
111
112
  virtual SVal evalMinus(NonLoc val) = 0;
113
114
  virtual SVal evalComplement(NonLoc val) = 0;
115
116
  /// Create a new value which represents a binary expression with two non-
117
  /// location operands.
118
  virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
119
                           NonLoc lhs, NonLoc rhs, QualType resultTy) = 0;
120
121
  /// Create a new value which represents a binary expression with two memory
122
  /// location operands.
123
  virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
124
                           Loc lhs, Loc rhs, QualType resultTy) = 0;
125
126
  /// Create a new value which represents a binary expression with a memory
127
  /// location and non-location operands. For example, this would be used to
128
  /// evaluate a pointer arithmetic operation.
129
  virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
130
                           Loc lhs, NonLoc rhs, QualType resultTy) = 0;
131
132
  /// Evaluates a given SVal. If the SVal has only one possible (integer) value,
133
  /// that value is returned. Otherwise, returns NULL.
134
  virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal val) = 0;
135
136
  /// Simplify symbolic expressions within a given SVal. Return an SVal
137
  /// that represents the same value, but is hopefully easier to work with
138
  /// than the original SVal.
139
  virtual SVal simplifySVal(ProgramStateRef State, SVal Val) = 0;
140
141
  /// Constructs a symbolic expression for two non-location values.
142
  SVal makeSymExprValNN(BinaryOperator::Opcode op,
143
                        NonLoc lhs, NonLoc rhs, QualType resultTy);
144
145
  SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
146
                 SVal lhs, SVal rhs, QualType type);
147
148
  /// \return Whether values in \p lhs and \p rhs are equal at \p state.
149
  ConditionTruthVal areEqual(ProgramStateRef state, SVal lhs, SVal rhs);
150
151
  SVal evalEQ(ProgramStateRef state, SVal lhs, SVal rhs);
152
153
  DefinedOrUnknownSVal evalEQ(ProgramStateRef state, DefinedOrUnknownSVal lhs,
154
                              DefinedOrUnknownSVal rhs);
155
156
1.01M
  ASTContext &getContext() { return Context; }
157
0
  const ASTContext &getContext() const { return Context; }
158
159
0
  ProgramStateManager &getStateManager() { return StateMgr; }
160
161
28.7k
  QualType getConditionType() const {
162
28.7k
    return Context.getLangOpts().CPlusPlus ? 
Context.BoolTy10.6k
:
Context.IntTy18.1k
;
163
28.7k
  }
164
165
36.9k
  QualType getArrayIndexType() const {
166
36.9k
    return ArrayIndexTy;
167
36.9k
  }
168
169
541k
  BasicValueFactory &getBasicValueFactory() { return BasicVals; }
170
0
  const BasicValueFactory &getBasicValueFactory() const { return BasicVals; }
171
172
14.6k
  SymbolManager &getSymbolManager() { return SymMgr; }
173
0
  const SymbolManager &getSymbolManager() const { return SymMgr; }
174
175
106k
  MemRegionManager &getRegionManager() { return MemMgr; }
176
0
  const MemRegionManager &getRegionManager() const { return MemMgr; }
177
178
  // Forwarding methods to SymbolManager.
179
180
  const SymbolConjured* conjureSymbol(const Stmt *stmt,
181
                                      const LocationContext *LCtx,
182
                                      QualType type,
183
                                      unsigned visitCount,
184
0
                                      const void *symbolTag = nullptr) {
185
0
    return SymMgr.conjureSymbol(stmt, LCtx, type, visitCount, symbolTag);
186
0
  }
187
188
  const SymbolConjured* conjureSymbol(const Expr *expr,
189
                                      const LocationContext *LCtx,
190
                                      unsigned visitCount,
191
0
                                      const void *symbolTag = nullptr) {
192
0
    return SymMgr.conjureSymbol(expr, LCtx, visitCount, symbolTag);
193
0
  }
194
195
  /// Construct an SVal representing '0' for the specified type.
196
  DefinedOrUnknownSVal makeZeroVal(QualType type);
197
198
  /// Make a unique symbol for value of region.
199
  DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedValueRegion *region);
200
201
  /// Create a new symbol with a unique 'name'.
202
  ///
203
  /// We resort to conjured symbols when we cannot construct a derived symbol.
204
  /// The advantage of symbols derived/built from other symbols is that we
205
  /// preserve the relation between related(or even equivalent) expressions, so
206
  /// conjured symbols should be used sparingly.
207
  DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag,
208
                                        const Expr *expr,
209
                                        const LocationContext *LCtx,
210
                                        unsigned count);
211
  DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag,
212
                                        const Expr *expr,
213
                                        const LocationContext *LCtx,
214
                                        QualType type,
215
                                        unsigned count);
216
  DefinedOrUnknownSVal conjureSymbolVal(const Stmt *stmt,
217
                                        const LocationContext *LCtx,
218
                                        QualType type,
219
                                        unsigned visitCount);
220
221
  /// Conjure a symbol representing heap allocated memory region.
222
  ///
223
  /// Note, the expression should represent a location.
224
  DefinedOrUnknownSVal getConjuredHeapSymbolVal(const Expr *E,
225
                                                const LocationContext *LCtx,
226
                                                unsigned Count);
227
228
  DefinedOrUnknownSVal getDerivedRegionValueSymbolVal(
229
      SymbolRef parentSymbol, const TypedValueRegion *region);
230
231
  DefinedSVal getMetadataSymbolVal(const void *symbolTag,
232
                                   const MemRegion *region,
233
                                   const Expr *expr, QualType type,
234
                                   const LocationContext *LCtx,
235
                                   unsigned count);
236
237
  DefinedSVal getMemberPointer(const DeclaratorDecl *DD);
238
239
  DefinedSVal getFunctionPointer(const FunctionDecl *func);
240
241
  DefinedSVal getBlockPointer(const BlockDecl *block, CanQualType locTy,
242
                              const LocationContext *locContext,
243
                              unsigned blockCount);
244
245
  /// Returns the value of \p E, if it can be determined in a non-path-sensitive
246
  /// manner.
247
  ///
248
  /// If \p E is not a constant or cannot be modeled, returns \c None.
249
  Optional<SVal> getConstantVal(const Expr *E);
250
251
879
  NonLoc makeCompoundVal(QualType type, llvm::ImmutableList<SVal> vals) {
252
879
    return nonloc::CompoundVal(BasicVals.getCompoundValData(type, vals));
253
879
  }
254
255
  NonLoc makeLazyCompoundVal(const StoreRef &store,
256
37.0k
                             const TypedValueRegion *region) {
257
37.0k
    return nonloc::LazyCompoundVal(
258
37.0k
        BasicVals.getLazyCompoundValData(store, region));
259
37.0k
  }
260
261
0
  NonLoc makePointerToMember(const DeclaratorDecl *DD) {
262
0
    return nonloc::PointerToMember(DD);
263
0
  }
264
265
24
  NonLoc makePointerToMember(const PointerToMemberData *PTMD) {
266
24
    return nonloc::PointerToMember(PTMD);
267
24
  }
268
269
10.4k
  NonLoc makeZeroArrayIndex() {
270
10.4k
    return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy));
271
10.4k
  }
272
273
12.2k
  NonLoc makeArrayIndex(uint64_t idx) {
274
12.2k
    return nonloc::ConcreteInt(BasicVals.getValue(idx, ArrayIndexTy));
275
12.2k
  }
276
277
  SVal convertToArrayIndex(SVal val);
278
279
67.5k
  nonloc::ConcreteInt makeIntVal(const IntegerLiteral* integer) {
280
67.5k
    return nonloc::ConcreteInt(
281
67.5k
        BasicVals.getValue(integer->getValue(),
282
67.5k
                     integer->getType()->isUnsignedIntegerOrEnumerationType()));
283
67.5k
  }
284
285
243
  nonloc::ConcreteInt makeBoolVal(const ObjCBoolLiteralExpr *boolean) {
286
243
    return makeTruthVal(boolean->getValue(), boolean->getType());
287
243
  }
288
289
  nonloc::ConcreteInt makeBoolVal(const CXXBoolLiteralExpr *boolean);
290
291
44.8k
  nonloc::ConcreteInt makeIntVal(const llvm::APSInt& integer) {
292
44.8k
    return nonloc::ConcreteInt(BasicVals.getValue(integer));
293
44.8k
  }
294
295
3.01k
  loc::ConcreteInt makeIntLocVal(const llvm::APSInt &integer) {
296
3.01k
    return loc::ConcreteInt(BasicVals.getValue(integer));
297
3.01k
  }
298
299
0
  NonLoc makeIntVal(const llvm::APInt& integer, bool isUnsigned) {
300
0
    return nonloc::ConcreteInt(BasicVals.getValue(integer, isUnsigned));
301
0
  }
302
303
49.5k
  DefinedSVal makeIntVal(uint64_t integer, QualType type) {
304
49.5k
    if (Loc::isLocType(type))
305
258
      return loc::ConcreteInt(BasicVals.getValue(integer, type));
306
49.2k
307
49.2k
    return nonloc::ConcreteInt(BasicVals.getValue(integer, type));
308
49.2k
  }
309
310
468
  NonLoc makeIntVal(uint64_t integer, bool isUnsigned) {
311
468
    return nonloc::ConcreteInt(BasicVals.getIntValue(integer, isUnsigned));
312
468
  }
313
314
94
  NonLoc makeIntValWithPtrWidth(uint64_t integer, bool isUnsigned) {
315
94
    return nonloc::ConcreteInt(
316
94
        BasicVals.getIntWithPtrWidth(integer, isUnsigned));
317
94
  }
318
319
112
  NonLoc makeLocAsInteger(Loc loc, unsigned bits) {
320
112
    return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(loc, bits));
321
112
  }
322
323
  NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
324
                    const llvm::APSInt& rhs, QualType type);
325
326
  NonLoc makeNonLoc(const llvm::APSInt& rhs, BinaryOperator::Opcode op,
327
                    const SymExpr *lhs, QualType type);
328
329
  NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
330
                    const SymExpr *rhs, QualType type);
331
332
  /// Create a NonLoc value for cast.
333
  NonLoc makeNonLoc(const SymExpr *operand, QualType fromTy, QualType toTy);
334
335
384k
  nonloc::ConcreteInt makeTruthVal(bool b, QualType type) {
336
384k
    return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type));
337
384k
  }
338
339
1.49k
  nonloc::ConcreteInt makeTruthVal(bool b) {
340
1.49k
    return nonloc::ConcreteInt(BasicVals.getTruthValue(b));
341
1.49k
  }
342
343
  /// Create NULL pointer, with proper pointer bit-width for given address
344
  /// space.
345
  /// \param type pointer type.
346
200
  Loc makeNullWithType(QualType type) {
347
200
    return loc::ConcreteInt(BasicVals.getZeroWithTypeSize(type));
348
200
  }
349
350
4.04k
  Loc makeNull() {
351
4.04k
    return loc::ConcreteInt(BasicVals.getZeroWithPtrWidth());
352
4.04k
  }
353
354
432
  Loc makeLoc(SymbolRef sym) {
355
432
    return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
356
432
  }
357
358
173k
  Loc makeLoc(const MemRegion* region) {
359
173k
    return loc::MemRegionVal(region);
360
173k
  }
361
362
60
  Loc makeLoc(const AddrLabelExpr *expr) {
363
60
    return loc::GotoLabel(expr->getLabel());
364
60
  }
365
366
15
  Loc makeLoc(const llvm::APSInt& integer) {
367
15
    return loc::ConcreteInt(BasicVals.getValue(integer));
368
15
  }
369
370
  /// Make an SVal that represents the given symbol. This follows the convention
371
  /// of representing Loc-type symbols (symbolic pointers and references)
372
  /// as Loc values wrapping the symbol rather than as plain symbol values.
373
246k
  SVal makeSymbolVal(SymbolRef Sym) {
374
246k
    if (Loc::isLocType(Sym->getType()))
375
177
      return makeLoc(Sym);
376
245k
    return nonloc::SymbolVal(Sym);
377
245k
  }
378
379
  /// Return a memory region for the 'this' object reference.
380
  loc::MemRegionVal getCXXThis(const CXXMethodDecl *D,
381
                               const StackFrameContext *SFC);
382
383
  /// Return a memory region for the 'this' object reference.
384
  loc::MemRegionVal getCXXThis(const CXXRecordDecl *D,
385
                               const StackFrameContext *SFC);
386
};
387
388
SValBuilder* createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
389
                                     ASTContext &context,
390
                                     ProgramStateManager &stateMgr);
391
392
} // namespace ento
393
394
} // namespace clang
395
396
#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALBUILDER_H