Home | History | Annotate | Line # | Download | only in PathSensitive 
      1 //==- BasicValueFactory.h - Basic values for Path Sens analysis --*- 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 BasicValueFactory, a class that manages the lifetime
     10 //  of APSInt objects and symbolic constraints used by ExprEngine
     11 //  and related classes.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H
     16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H
     17 
     18 #include "clang/AST/ASTContext.h"
     19 #include "clang/AST/Expr.h"
     20 #include "clang/AST/Type.h"
     21 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
     22 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
     23 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
     24 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
     25 #include "llvm/ADT/APSInt.h"
     26 #include "llvm/ADT/FoldingSet.h"
     27 #include "llvm/ADT/ImmutableList.h"
     28 #include "llvm/ADT/iterator_range.h"
     29 #include "llvm/Support/Allocator.h"
     30 #include <cassert>
     31 #include <cstdint>
     32 #include <utility>
     33 
     34 namespace clang {
     35 
     36 class CXXBaseSpecifier;
     37 class DeclaratorDecl;
     38 
     39 namespace ento {
     40 
     41 class CompoundValData : public llvm::FoldingSetNode {
     42   QualType T;
     43   llvm::ImmutableList<SVal> L;
     44 
     45 public:
     46   CompoundValData(QualType t, llvm::ImmutableList<SVal> l) : T(t), L(l) {
     47     assert(NonLoc::isCompoundType(t));
     48   }
     49 
     50   using iterator = llvm::ImmutableList<SVal>::iterator;
     51 
     52   iterator begin() const { return L.begin(); }
     53   iterator end() const { return L.end(); }
     54 
     55   static void Profile(llvm::FoldingSetNodeID& ID, QualType T,
     56                       llvm::ImmutableList<SVal> L);
     57 
     58   void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); }
     59 };
     60 
     61 class LazyCompoundValData : public llvm::FoldingSetNode {
     62   StoreRef store;
     63   const TypedValueRegion *region;
     64 
     65 public:
     66   LazyCompoundValData(const StoreRef &st, const TypedValueRegion *r)
     67       : store(st), region(r) {
     68     assert(NonLoc::isCompoundType(r->getValueType()));
     69   }
     70 
     71   const void *getStore() const { return store.getStore(); }
     72   const TypedValueRegion *getRegion() const { return region; }
     73 
     74   static void Profile(llvm::FoldingSetNodeID& ID,
     75                       const StoreRef &store,
     76                       const TypedValueRegion *region);
     77 
     78   void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, store, region); }
     79 };
     80 
     81 class PointerToMemberData : public llvm::FoldingSetNode {
     82   const NamedDecl *D;
     83   llvm::ImmutableList<const CXXBaseSpecifier *> L;
     84 
     85 public:
     86   PointerToMemberData(const NamedDecl *D,
     87                       llvm::ImmutableList<const CXXBaseSpecifier *> L)
     88       : D(D), L(L) {}
     89 
     90   using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator;
     91 
     92   iterator begin() const { return L.begin(); }
     93   iterator end() const { return L.end(); }
     94 
     95   static void Profile(llvm::FoldingSetNodeID &ID, const NamedDecl *D,
     96                       llvm::ImmutableList<const CXXBaseSpecifier *> L);
     97 
     98   void Profile(llvm::FoldingSetNodeID &ID) { Profile(ID, D, L); }
     99   const NamedDecl *getDeclaratorDecl() const { return D; }
    100 
    101   llvm::ImmutableList<const CXXBaseSpecifier *> getCXXBaseList() const {
    102     return L;
    103   }
    104 };
    105 
    106 class BasicValueFactory {
    107   using APSIntSetTy =
    108       llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt>>;
    109 
    110   ASTContext &Ctx;
    111   llvm::BumpPtrAllocator& BPAlloc;
    112 
    113   APSIntSetTy APSIntSet;
    114   void *PersistentSVals = nullptr;
    115   void *PersistentSValPairs = nullptr;
    116 
    117   llvm::ImmutableList<SVal>::Factory SValListFactory;
    118   llvm::ImmutableList<const CXXBaseSpecifier *>::Factory CXXBaseListFactory;
    119   llvm::FoldingSet<CompoundValData>  CompoundValDataSet;
    120   llvm::FoldingSet<LazyCompoundValData> LazyCompoundValDataSet;
    121   llvm::FoldingSet<PointerToMemberData> PointerToMemberDataSet;
    122 
    123   // This is private because external clients should use the factory
    124   // method that takes a QualType.
    125   const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned);
    126 
    127 public:
    128   BasicValueFactory(ASTContext &ctx, llvm::BumpPtrAllocator &Alloc)
    129       : Ctx(ctx), BPAlloc(Alloc), SValListFactory(Alloc),
    130         CXXBaseListFactory(Alloc) {}
    131 
    132   ~BasicValueFactory();
    133 
    134   ASTContext &getContext() const { return Ctx; }
    135 
    136   const llvm::APSInt& getValue(const llvm::APSInt& X);
    137   const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned);
    138   const llvm::APSInt& getValue(uint64_t X, QualType T);
    139 
    140   /// Returns the type of the APSInt used to store values of the given QualType.
    141   APSIntType getAPSIntType(QualType T) const {
    142     // For the purposes of the analysis and constraints, we treat atomics
    143     // as their underlying types.
    144     if (const AtomicType *AT = T->getAs<AtomicType>()) {
    145       T = AT->getValueType();
    146     }
    147 
    148     assert(T->isIntegralOrEnumerationType() || Loc::isLocType(T));
    149     return APSIntType(Ctx.getIntWidth(T),
    150                       !T->isSignedIntegerOrEnumerationType());
    151   }
    152 
    153   /// Convert - Create a new persistent APSInt with the same value as 'From'
    154   ///  but with the bitwidth and signedness of 'To'.
    155   const llvm::APSInt &Convert(const llvm::APSInt& To,
    156                               const llvm::APSInt& From) {
    157     APSIntType TargetType(To);
    158     if (TargetType == APSIntType(From))
    159       return From;
    160 
    161     return getValue(TargetType.convert(From));
    162   }
    163 
    164   const llvm::APSInt &Convert(QualType T, const llvm::APSInt &From) {
    165     APSIntType TargetType = getAPSIntType(T);
    166     return Convert(TargetType, From);
    167   }
    168 
    169   const llvm::APSInt &Convert(APSIntType TargetType, const llvm::APSInt &From) {
    170     if (TargetType == APSIntType(From))
    171       return From;
    172 
    173     return getValue(TargetType.convert(From));
    174   }
    175 
    176   const llvm::APSInt &getIntValue(uint64_t X, bool isUnsigned) {
    177     QualType T = isUnsigned ? Ctx.UnsignedIntTy : Ctx.IntTy;
    178     return getValue(X, T);
    179   }
    180 
    181   const llvm::APSInt &getMaxValue(const llvm::APSInt &v) {
    182     return getValue(APSIntType(v).getMaxValue());
    183   }
    184 
    185   const llvm::APSInt &getMinValue(const llvm::APSInt &v) {
    186     return getValue(APSIntType(v).getMinValue());
    187   }
    188 
    189   const llvm::APSInt &getMaxValue(QualType T) {
    190     return getMaxValue(getAPSIntType(T));
    191   }
    192 
    193   const llvm::APSInt &getMinValue(QualType T) {
    194     return getMinValue(getAPSIntType(T));
    195   }
    196 
    197   const llvm::APSInt &getMaxValue(APSIntType T) {
    198     return getValue(T.getMaxValue());
    199   }
    200 
    201   const llvm::APSInt &getMinValue(APSIntType T) {
    202     return getValue(T.getMinValue());
    203   }
    204 
    205   const llvm::APSInt &Add1(const llvm::APSInt &V) {
    206     llvm::APSInt X = V;
    207     ++X;
    208     return getValue(X);
    209   }
    210 
    211   const llvm::APSInt &Sub1(const llvm::APSInt &V) {
    212     llvm::APSInt X = V;
    213     --X;
    214     return getValue(X);
    215   }
    216 
    217   const llvm::APSInt &getZeroWithTypeSize(QualType T) {
    218     assert(T->isScalarType());
    219     return getValue(0, Ctx.getTypeSize(T), true);
    220   }
    221 
    222   const llvm::APSInt &getZeroWithPtrWidth(bool isUnsigned = true) {
    223     return getValue(0, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned);
    224   }
    225 
    226   const llvm::APSInt &getIntWithPtrWidth(uint64_t X, bool isUnsigned) {
    227     return getValue(X, Ctx.getTypeSize(Ctx.VoidPtrTy), isUnsigned);
    228   }
    229 
    230   const llvm::APSInt &getTruthValue(bool b, QualType T) {
    231     return getValue(b ? 1 : 0, Ctx.getIntWidth(T),
    232                     T->isUnsignedIntegerOrEnumerationType());
    233   }
    234 
    235   const llvm::APSInt &getTruthValue(bool b) {
    236     return getTruthValue(b, Ctx.getLogicalOperationType());
    237   }
    238 
    239   const CompoundValData *getCompoundValData(QualType T,
    240                                             llvm::ImmutableList<SVal> Vals);
    241 
    242   const LazyCompoundValData *getLazyCompoundValData(const StoreRef &store,
    243                                             const TypedValueRegion *region);
    244 
    245   const PointerToMemberData *
    246   getPointerToMemberData(const NamedDecl *ND,
    247                          llvm::ImmutableList<const CXXBaseSpecifier *> L);
    248 
    249   llvm::ImmutableList<SVal> getEmptySValList() {
    250     return SValListFactory.getEmptyList();
    251   }
    252 
    253   llvm::ImmutableList<SVal> prependSVal(SVal X, llvm::ImmutableList<SVal> L) {
    254     return SValListFactory.add(X, L);
    255   }
    256 
    257   llvm::ImmutableList<const CXXBaseSpecifier *> getEmptyCXXBaseList() {
    258     return CXXBaseListFactory.getEmptyList();
    259   }
    260 
    261   llvm::ImmutableList<const CXXBaseSpecifier *> prependCXXBase(
    262       const CXXBaseSpecifier *CBS,
    263       llvm::ImmutableList<const CXXBaseSpecifier *> L) {
    264     return CXXBaseListFactory.add(CBS, L);
    265   }
    266 
    267   const PointerToMemberData *
    268   accumCXXBase(llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
    269                const nonloc::PointerToMember &PTM, const clang::CastKind &kind);
    270 
    271   const llvm::APSInt* evalAPSInt(BinaryOperator::Opcode Op,
    272                                      const llvm::APSInt& V1,
    273                                      const llvm::APSInt& V2);
    274 
    275   const std::pair<SVal, uintptr_t>&
    276   getPersistentSValWithData(const SVal& V, uintptr_t Data);
    277 
    278   const std::pair<SVal, SVal>&
    279   getPersistentSValPair(const SVal& V1, const SVal& V2);
    280 
    281   const SVal* getPersistentSVal(SVal X);
    282 };
    283 
    284 } // namespace ento
    285 
    286 } // namespace clang
    287 
    288 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H
    289