Home | History | Annotate | Download | only in PathSensitive
      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/Expr.h"
     20 #include "clang/AST/ExprObjC.h"
     21 #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
     22 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
     23 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
     24 
     25 namespace clang {
     26 
     27 class CXXBoolLiteralExpr;
     28 
     29 namespace ento {
     30 
     31 class SValBuilder {
     32   virtual void anchor();
     33 protected:
     34   ASTContext &Context;
     35 
     36   /// Manager of APSInt values.
     37   BasicValueFactory BasicVals;
     38 
     39   /// Manages the creation of symbols.
     40   SymbolManager SymMgr;
     41 
     42   /// Manages the creation of memory regions.
     43   MemRegionManager MemMgr;
     44 
     45   ProgramStateManager &StateMgr;
     46 
     47   /// The scalar type to use for array indices.
     48   const QualType ArrayIndexTy;
     49 
     50   /// The width of the scalar type used for array indices.
     51   const unsigned ArrayIndexWidth;
     52 
     53   virtual SVal evalCastFromNonLoc(NonLoc val, QualType castTy) = 0;
     54   virtual SVal evalCastFromLoc(Loc val, QualType castTy) = 0;
     55 
     56 public:
     57   // FIXME: Make these protected again once RegionStoreManager correctly
     58   // handles loads from different bound value types.
     59   virtual SVal dispatchCast(SVal val, QualType castTy) = 0;
     60 
     61 public:
     62   SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
     63               ProgramStateManager &stateMgr)
     64     : Context(context), BasicVals(context, alloc),
     65       SymMgr(context, BasicVals, alloc),
     66       MemMgr(context, alloc),
     67       StateMgr(stateMgr),
     68       ArrayIndexTy(context.IntTy),
     69       ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {}
     70 
     71   virtual ~SValBuilder() {}
     72 
     73   bool haveSameType(const SymExpr *Sym1, const SymExpr *Sym2) {
     74     return haveSameType(Sym1->getType(), Sym2->getType());
     75   }
     76 
     77   bool haveSameType(QualType Ty1, QualType Ty2) {
     78     // FIXME: Remove the second disjunct when we support symbolic
     79     // truncation/extension.
     80     return (Context.getCanonicalType(Ty1) == Context.getCanonicalType(Ty2) ||
     81             (Ty1->isIntegralOrEnumerationType() &&
     82              Ty2->isIntegralOrEnumerationType()));
     83   }
     84 
     85   SVal evalCast(SVal val, QualType castTy, QualType originalType);
     86 
     87   virtual SVal evalMinus(NonLoc val) = 0;
     88 
     89   virtual SVal evalComplement(NonLoc val) = 0;
     90 
     91   /// Create a new value which represents a binary expression with two non-
     92   /// location operands.
     93   virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
     94                            NonLoc lhs, NonLoc rhs, QualType resultTy) = 0;
     95 
     96   /// Create a new value which represents a binary expression with two memory
     97   /// location operands.
     98   virtual SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
     99                            Loc lhs, Loc rhs, QualType resultTy) = 0;
    100 
    101   /// Create a new value which represents a binary expression with a memory
    102   /// location and non-location operands. For example, this would be used to
    103   /// evaluate a pointer arithmetic operation.
    104   virtual SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
    105                            Loc lhs, NonLoc rhs, QualType resultTy) = 0;
    106 
    107   /// Evaluates a given SVal. If the SVal has only one possible (integer) value,
    108   /// that value is returned. Otherwise, returns NULL.
    109   virtual const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal val) = 0;
    110 
    111   /// Constructs a symbolic expression for two non-location values.
    112   SVal makeSymExprValNN(ProgramStateRef state, BinaryOperator::Opcode op,
    113                       NonLoc lhs, NonLoc rhs, QualType resultTy);
    114 
    115   SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
    116                  SVal lhs, SVal rhs, QualType type);
    117 
    118   DefinedOrUnknownSVal evalEQ(ProgramStateRef state, DefinedOrUnknownSVal lhs,
    119                               DefinedOrUnknownSVal rhs);
    120 
    121   ASTContext &getContext() { return Context; }
    122   const ASTContext &getContext() const { return Context; }
    123 
    124   ProgramStateManager &getStateManager() { return StateMgr; }
    125 
    126   QualType getConditionType() const {
    127     return Context.getLangOpts().CPlusPlus ? Context.BoolTy : Context.IntTy;
    128   }
    129 
    130   QualType getArrayIndexType() const {
    131     return ArrayIndexTy;
    132   }
    133 
    134   BasicValueFactory &getBasicValueFactory() { return BasicVals; }
    135   const BasicValueFactory &getBasicValueFactory() const { return BasicVals; }
    136 
    137   SymbolManager &getSymbolManager() { return SymMgr; }
    138   const SymbolManager &getSymbolManager() const { return SymMgr; }
    139 
    140   MemRegionManager &getRegionManager() { return MemMgr; }
    141   const MemRegionManager &getRegionManager() const { return MemMgr; }
    142 
    143   // Forwarding methods to SymbolManager.
    144 
    145   const SymbolConjured* conjureSymbol(const Stmt *stmt,
    146                                       const LocationContext *LCtx,
    147                                       QualType type,
    148                                       unsigned visitCount,
    149                                       const void *symbolTag = nullptr) {
    150     return SymMgr.conjureSymbol(stmt, LCtx, type, visitCount, symbolTag);
    151   }
    152 
    153   const SymbolConjured* conjureSymbol(const Expr *expr,
    154                                       const LocationContext *LCtx,
    155                                       unsigned visitCount,
    156                                       const void *symbolTag = nullptr) {
    157     return SymMgr.conjureSymbol(expr, LCtx, visitCount, symbolTag);
    158   }
    159 
    160   /// Construct an SVal representing '0' for the specified type.
    161   DefinedOrUnknownSVal makeZeroVal(QualType type);
    162 
    163   /// Make a unique symbol for value of region.
    164   DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedValueRegion *region);
    165 
    166   /// \brief Create a new symbol with a unique 'name'.
    167   ///
    168   /// We resort to conjured symbols when we cannot construct a derived symbol.
    169   /// The advantage of symbols derived/built from other symbols is that we
    170   /// preserve the relation between related(or even equivalent) expressions, so
    171   /// conjured symbols should be used sparingly.
    172   DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag,
    173                                         const Expr *expr,
    174                                         const LocationContext *LCtx,
    175                                         unsigned count);
    176   DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag,
    177                                         const Expr *expr,
    178                                         const LocationContext *LCtx,
    179                                         QualType type,
    180                                         unsigned count);
    181 
    182   DefinedOrUnknownSVal conjureSymbolVal(const Stmt *stmt,
    183                                         const LocationContext *LCtx,
    184                                         QualType type,
    185                                         unsigned visitCount);
    186   /// \brief Conjure a symbol representing heap allocated memory region.
    187   ///
    188   /// Note, the expression should represent a location.
    189   DefinedOrUnknownSVal getConjuredHeapSymbolVal(const Expr *E,
    190                                                 const LocationContext *LCtx,
    191                                                 unsigned Count);
    192 
    193   DefinedOrUnknownSVal getDerivedRegionValueSymbolVal(
    194       SymbolRef parentSymbol, const TypedValueRegion *region);
    195 
    196   DefinedSVal getMetadataSymbolVal(
    197       const void *symbolTag, const MemRegion *region,
    198       const Expr *expr, QualType type, unsigned count);
    199 
    200   DefinedSVal getFunctionPointer(const FunctionDecl *func);
    201 
    202   DefinedSVal getBlockPointer(const BlockDecl *block, CanQualType locTy,
    203                               const LocationContext *locContext,
    204                               unsigned blockCount);
    205 
    206   /// Returns the value of \p E, if it can be determined in a non-path-sensitive
    207   /// manner.
    208   ///
    209   /// If \p E is not a constant or cannot be modeled, returns \c None.
    210   Optional<SVal> getConstantVal(const Expr *E);
    211 
    212   NonLoc makeCompoundVal(QualType type, llvm::ImmutableList<SVal> vals) {
    213     return nonloc::CompoundVal(BasicVals.getCompoundValData(type, vals));
    214   }
    215 
    216   NonLoc makeLazyCompoundVal(const StoreRef &store,
    217                              const TypedValueRegion *region) {
    218     return nonloc::LazyCompoundVal(
    219         BasicVals.getLazyCompoundValData(store, region));
    220   }
    221 
    222   NonLoc makeZeroArrayIndex() {
    223     return nonloc::ConcreteInt(BasicVals.getValue(0, ArrayIndexTy));
    224   }
    225 
    226   NonLoc makeArrayIndex(uint64_t idx) {
    227     return nonloc::ConcreteInt(BasicVals.getValue(idx, ArrayIndexTy));
    228   }
    229 
    230   SVal convertToArrayIndex(SVal val);
    231 
    232   nonloc::ConcreteInt makeIntVal(const IntegerLiteral* integer) {
    233     return nonloc::ConcreteInt(
    234         BasicVals.getValue(integer->getValue(),
    235                      integer->getType()->isUnsignedIntegerOrEnumerationType()));
    236   }
    237 
    238   nonloc::ConcreteInt makeBoolVal(const ObjCBoolLiteralExpr *boolean) {
    239     return makeTruthVal(boolean->getValue(), boolean->getType());
    240   }
    241 
    242   nonloc::ConcreteInt makeBoolVal(const CXXBoolLiteralExpr *boolean);
    243 
    244   nonloc::ConcreteInt makeIntVal(const llvm::APSInt& integer) {
    245     return nonloc::ConcreteInt(BasicVals.getValue(integer));
    246   }
    247 
    248   loc::ConcreteInt makeIntLocVal(const llvm::APSInt &integer) {
    249     return loc::ConcreteInt(BasicVals.getValue(integer));
    250   }
    251 
    252   NonLoc makeIntVal(const llvm::APInt& integer, bool isUnsigned) {
    253     return nonloc::ConcreteInt(BasicVals.getValue(integer, isUnsigned));
    254   }
    255 
    256   DefinedSVal makeIntVal(uint64_t integer, QualType type) {
    257     if (Loc::isLocType(type))
    258       return loc::ConcreteInt(BasicVals.getValue(integer, type));
    259 
    260     return nonloc::ConcreteInt(BasicVals.getValue(integer, type));
    261   }
    262 
    263   NonLoc makeIntVal(uint64_t integer, bool isUnsigned) {
    264     return nonloc::ConcreteInt(BasicVals.getIntValue(integer, isUnsigned));
    265   }
    266 
    267   NonLoc makeIntValWithPtrWidth(uint64_t integer, bool isUnsigned) {
    268     return nonloc::ConcreteInt(
    269         BasicVals.getIntWithPtrWidth(integer, isUnsigned));
    270   }
    271 
    272   NonLoc makeLocAsInteger(Loc loc, unsigned bits) {
    273     return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(loc, bits));
    274   }
    275 
    276   NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
    277                     const llvm::APSInt& rhs, QualType type);
    278 
    279   NonLoc makeNonLoc(const llvm::APSInt& rhs, BinaryOperator::Opcode op,
    280                     const SymExpr *lhs, QualType type);
    281 
    282   NonLoc makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op,
    283                     const SymExpr *rhs, QualType type);
    284 
    285   /// \brief Create a NonLoc value for cast.
    286   NonLoc makeNonLoc(const SymExpr *operand, QualType fromTy, QualType toTy);
    287 
    288   nonloc::ConcreteInt makeTruthVal(bool b, QualType type) {
    289     return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type));
    290   }
    291 
    292   nonloc::ConcreteInt makeTruthVal(bool b) {
    293     return nonloc::ConcreteInt(BasicVals.getTruthValue(b));
    294   }
    295 
    296   Loc makeNull() {
    297     return loc::ConcreteInt(BasicVals.getZeroWithPtrWidth());
    298   }
    299 
    300   Loc makeLoc(SymbolRef sym) {
    301     return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym));
    302   }
    303 
    304   Loc makeLoc(const MemRegion* region) {
    305     return loc::MemRegionVal(region);
    306   }
    307 
    308   Loc makeLoc(const AddrLabelExpr *expr) {
    309     return loc::GotoLabel(expr->getLabel());
    310   }
    311 
    312   Loc makeLoc(const llvm::APSInt& integer) {
    313     return loc::ConcreteInt(BasicVals.getValue(integer));
    314   }
    315 
    316   /// Return a memory region for the 'this' object reference.
    317   loc::MemRegionVal getCXXThis(const CXXMethodDecl *D,
    318                                const StackFrameContext *SFC);
    319 
    320   /// Return a memory region for the 'this' object reference.
    321   loc::MemRegionVal getCXXThis(const CXXRecordDecl *D,
    322                                const StackFrameContext *SFC);
    323 };
    324 
    325 SValBuilder* createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
    326                                      ASTContext &context,
    327                                      ProgramStateManager &stateMgr);
    328 
    329 } // end GR namespace
    330 
    331 } // end clang namespace
    332 
    333 #endif
    334