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