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