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