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         ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {}
104 
105   virtual ~SValBuilder() = default;
106 
107   bool haveSameType(const SymExpr *Sym1, const SymExpr *Sym2) {
108     return haveSameType(Sym1->getType(), Sym2->getType());
109   }
110 
111   bool haveSameType(QualType Ty1, QualType Ty2) {
112     // FIXME: Remove the second disjunct when we support symbolic
113     // truncation/extension.
114     return (Context.getCanonicalType(Ty1) == Context.getCanonicalType(Ty2) ||
115             (Ty1->isIntegralOrEnumerationType() &&
116              Ty2->isIntegralOrEnumerationType()));
117   }
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   ASTContext &getContext() { return Context; }
170   const ASTContext &getContext() const { return Context; }
171 
172   ProgramStateManager &getStateManager() { return StateMgr; }
173 
174   QualType getConditionType() const {
175     return Context.getLangOpts().CPlusPlus ? Context.BoolTy : Context.IntTy;
176   }
177 
178   QualType getArrayIndexType() const {
179     return ArrayIndexTy;
180   }
181 
182   BasicValueFactory &getBasicValueFactory() { return BasicVals; }
183   const BasicValueFactory &getBasicValueFactory() const { return BasicVals; }
184 
185   SymbolManager &getSymbolManager() { return SymMgr; }
186   const SymbolManager &getSymbolManager() const { return SymMgr; }
187 
188   MemRegionManager &getRegionManager() { return MemMgr; }
189   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                                       const void *symbolTag = nullptr) {
198     return SymMgr.conjureSymbol(stmt, LCtx, type, visitCount, symbolTag);
199   }
200 
201   const SymbolConjured* conjureSymbol(const Expr *expr,
202                                       const LocationContext *LCtx,
203                                       unsigned visitCount,
204                                       const void *symbolTag = nullptr) {
205     return SymMgr.conjureSymbol(expr, LCtx, visitCount, symbolTag);
206   }
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   NonLoc makeCompoundVal(QualType type, llvm::ImmutableList<SVal> vals) {
273     return nonloc::CompoundVal(BasicVals.getCompoundValData(type, vals));
274   }
275 
276   NonLoc makeLazyCompoundVal(const StoreRef &store,
277                              const TypedValueRegion *region) {
278     return nonloc::LazyCompoundVal(
279         BasicVals.getLazyCompoundValData(store, region));
280   }
281 
282   NonLoc makePointerToMember(const DeclaratorDecl *DD) {
283     return nonloc::PointerToMember(DD);
284   }
285 
286   NonLoc makePointerToMember(const PointerToMemberData *PTMD) {
287     return nonloc::PointerToMember(PTMD);
288   }
289 
290   NonLoc makeZeroArrayIndex() {
291     return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy));
292   }
293 
294   NonLoc makeArrayIndex(uint64_t idx) {
295     return nonloc::ConcreteInt(BasicVals.getValue(idx, ArrayIndexTy));
296   }
297 
298   SVal convertToArrayIndex(SVal val);
299 
300   nonloc::ConcreteInt makeIntVal(const IntegerLiteral* integer) {
301     return nonloc::ConcreteInt(
302         BasicVals.getValue(integer->getValue(),
303                      integer->getType()->isUnsignedIntegerOrEnumerationType()));
304   }
305 
306   nonloc::ConcreteInt makeBoolVal(const ObjCBoolLiteralExpr *boolean) {
307     return makeTruthVal(boolean->getValue(), boolean->getType());
308   }
309 
310   nonloc::ConcreteInt makeBoolVal(const CXXBoolLiteralExpr *boolean);
311 
312   nonloc::ConcreteInt makeIntVal(const llvm::APSInt& integer) {
313     return nonloc::ConcreteInt(BasicVals.getValue(integer));
314   }
315 
316   loc::ConcreteInt makeIntLocVal(const llvm::APSInt &integer) {
317     return loc::ConcreteInt(BasicVals.getValue(integer));
318   }
319 
320   NonLoc makeIntVal(const llvm::APInt& integer, bool isUnsigned) {
321     return nonloc::ConcreteInt(BasicVals.getValue(integer, isUnsigned));
322   }
323 
324   DefinedSVal makeIntVal(uint64_t integer, QualType type) {
325     if (Loc::isLocType(type))
326       return loc::ConcreteInt(BasicVals.getValue(integer, type));
327 
328     return nonloc::ConcreteInt(BasicVals.getValue(integer, type));
329   }
330 
331   NonLoc makeIntVal(uint64_t integer, bool isUnsigned) {
332     return nonloc::ConcreteInt(BasicVals.getIntValue(integer, isUnsigned));
333   }
334 
335   NonLoc makeIntValWithPtrWidth(uint64_t integer, bool isUnsigned) {
336     return nonloc::ConcreteInt(
337         BasicVals.getIntWithPtrWidth(integer, isUnsigned));
338   }
339 
340   NonLoc makeLocAsInteger(Loc loc, unsigned bits) {
341     return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(loc, bits));
342   }
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   nonloc::ConcreteInt makeTruthVal(bool b, QualType type) {
357     return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type));
358   }
359 
360   nonloc::ConcreteInt makeTruthVal(bool b) {
361     return nonloc::ConcreteInt(BasicVals.getTruthValue(b));
362   }
363 
364   /// Create NULL pointer, with proper pointer bit-width for given address
365   /// space.
366   /// \param type pointer type.
367   Loc makeNullWithType(QualType type) {
368     return loc::ConcreteInt(BasicVals.getZeroWithTypeSize(type));
369   }
370 
371   Loc makeNull() {
372     return loc::ConcreteInt(BasicVals.getZeroWithPtrWidth());
373   }
374 
375   Loc makeLoc(SymbolRef sym) {
376     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
377   }
378 
379   Loc makeLoc(const MemRegion* region) {
380     return loc::MemRegionVal(region);
381   }
382 
383   Loc makeLoc(const AddrLabelExpr *expr) {
384     return loc::GotoLabel(expr->getLabel());
385   }
386 
387   Loc makeLoc(const llvm::APSInt& integer) {
388     return loc::ConcreteInt(BasicVals.getValue(integer));
389   }
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   SVal makeSymbolVal(SymbolRef Sym) {
399     if (Loc::isLocType(Sym->getType()))
400       return makeLoc(Sym);
401     return nonloc::SymbolVal(Sym);
402   }
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
422