Home | History | Annotate | Download | only in PathSensitive 
      1 //== Store.h - Interface for maps from Locations to Values ------*- 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 defined the types Store and StoreManager.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #ifndef LLVM_CLANG_GR_STORE_H
     15 #define LLVM_CLANG_GR_STORE_H
     16 
     17 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
     18 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
     19 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
     20 #include "llvm/ADT/DenseSet.h"
     21 #include "llvm/ADT/Optional.h"
     22 
     23 namespace clang {
     24 
     25 class Stmt;
     26 class Expr;
     27 class ObjCIvarDecl;
     28 class CXXBasePath;
     29 class StackFrameContext;
     30 
     31 namespace ento {
     32 
     33 class CallEvent;
     34 class ProgramState;
     35 class ProgramStateManager;
     36 class ScanReachableSymbols;
     37 
     38 typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
     39 
     40 class StoreManager {
     41 protected:
     42   SValBuilder &svalBuilder;
     43   ProgramStateManager &StateMgr;
     44 
     45   /// MRMgr - Manages region objects associated with this StoreManager.
     46   MemRegionManager &MRMgr;
     47   ASTContext &Ctx;
     48 
     49   StoreManager(ProgramStateManager &stateMgr);
     50 
     51 public:
     52   virtual ~StoreManager() {}
     53 
     54   /// Return the value bound to specified location in a given state.
     55   /// \param[in] store The analysis state.
     56   /// \param[in] loc The symbolic memory location.
     57   /// \param[in] T An optional type that provides a hint indicating the
     58   ///   expected type of the returned value.  This is used if the value is
     59   ///   lazily computed.
     60   /// \return The value bound to the location \c loc.
     61   virtual SVal getBinding(Store store, Loc loc, QualType T = QualType()) = 0;
     62 
     63   /// Return a state with the specified value bound to the given location.
     64   /// \param[in] store The analysis state.
     65   /// \param[in] loc The symbolic memory location.
     66   /// \param[in] val The value to bind to location \c loc.
     67   /// \return A pointer to a ProgramState object that contains the same
     68   ///   bindings as \c state with the addition of having the value specified
     69   ///   by \c val bound to the location given for \c loc.
     70   virtual StoreRef Bind(Store store, Loc loc, SVal val) = 0;
     71 
     72   virtual StoreRef BindDefault(Store store, const MemRegion *R, SVal V);
     73 
     74   /// \brief Create a new store with the specified binding removed.
     75   /// \param ST the original store, that is the basis for the new store.
     76   /// \param L the location whose binding should be removed.
     77   virtual StoreRef killBinding(Store ST, Loc L) = 0;
     78 
     79   /// getInitialStore - Returns the initial "empty" store representing the
     80   ///  value bindings upon entry to an analyzed function.
     81   virtual StoreRef getInitialStore(const LocationContext *InitLoc) = 0;
     82 
     83   /// getRegionManager - Returns the internal RegionManager object that is
     84   ///  used to query and manipulate MemRegion objects.
     85   MemRegionManager& getRegionManager() { return MRMgr; }
     86 
     87   virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) {
     88     return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC));
     89   }
     90 
     91   Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL,
     92                                const LocationContext *LC) {
     93     return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC));
     94   }
     95 
     96   virtual SVal getLValueIvar(const ObjCIvarDecl *decl, SVal base);
     97 
     98   virtual SVal getLValueField(const FieldDecl *D, SVal Base) {
     99     return getLValueFieldOrIvar(D, Base);
    100   }
    101 
    102   virtual SVal getLValueElement(QualType elementType, NonLoc offset, SVal Base);
    103 
    104   // FIXME: This should soon be eliminated altogether; clients should deal with
    105   // region extents directly.
    106   virtual DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state,
    107                                                  const MemRegion *region,
    108                                                  QualType EleTy) {
    109     return UnknownVal();
    110   }
    111 
    112   /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
    113   ///  conversions between arrays and pointers.
    114   virtual SVal ArrayToPointer(Loc Array, QualType ElementTy) = 0;
    115 
    116   /// Evaluates a chain of derived-to-base casts through the path specified in
    117   /// \p Cast.
    118   SVal evalDerivedToBase(SVal Derived, const CastExpr *Cast);
    119 
    120   /// Evaluates a chain of derived-to-base casts through the specified path.
    121   SVal evalDerivedToBase(SVal Derived, const CXXBasePath &CastPath);
    122 
    123   /// Evaluates a derived-to-base cast through a single level of derivation.
    124   SVal evalDerivedToBase(SVal Derived, QualType DerivedPtrType,
    125                          bool IsVirtual);
    126 
    127   /// \brief Evaluates C++ dynamic_cast cast.
    128   /// The callback may result in the following 3 scenarios:
    129   ///  - Successful cast (ex: derived is subclass of base).
    130   ///  - Failed cast (ex: derived is definitely not a subclass of base).
    131   ///  - We don't know (base is a symbolic region and we don't have
    132   ///    enough info to determine if the cast will succeed at run time).
    133   /// The function returns an SVal representing the derived class; it's
    134   /// valid only if Failed flag is set to false.
    135   SVal evalDynamicCast(SVal Base, QualType DerivedPtrType, bool &Failed);
    136 
    137   const ElementRegion *GetElementZeroRegion(const MemRegion *R, QualType T);
    138 
    139   /// castRegion - Used by ExprEngine::VisitCast to handle casts from
    140   ///  a MemRegion* to a specific location type.  'R' is the region being
    141   ///  casted and 'CastToTy' the result type of the cast.
    142   const MemRegion *castRegion(const MemRegion *region, QualType CastToTy);
    143 
    144   virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
    145                                       SymbolReaper& SymReaper) = 0;
    146 
    147   virtual bool includedInBindings(Store store,
    148                                   const MemRegion *region) const = 0;
    149 
    150   /// If the StoreManager supports it, increment the reference count of
    151   /// the specified Store object.
    152   virtual void incrementReferenceCount(Store store) {}
    153 
    154   /// If the StoreManager supports it, decrement the reference count of
    155   /// the specified Store object.  If the reference count hits 0, the memory
    156   /// associated with the object is recycled.
    157   virtual void decrementReferenceCount(Store store) {}
    158 
    159   typedef SmallVector<const MemRegion *, 8> InvalidatedRegions;
    160 
    161   /// invalidateRegions - Clears out the specified regions from the store,
    162   ///  marking their values as unknown. Depending on the store, this may also
    163   ///  invalidate additional regions that may have changed based on accessing
    164   ///  the given regions. Optionally, invalidates non-static globals as well.
    165   /// \param[in] store The initial store
    166   /// \param[in] Values The values to invalidate.
    167   /// \param[in] E The current statement being evaluated. Used to conjure
    168   ///   symbols to mark the values of invalidated regions.
    169   /// \param[in] Count The current block count. Used to conjure
    170   ///   symbols to mark the values of invalidated regions.
    171   /// \param[in] Call The call expression which will be used to determine which
    172   ///   globals should get invalidated.
    173   /// \param[in,out] IS A set to fill with any symbols that are no longer
    174   ///   accessible. Pass \c NULL if this information will not be used.
    175   /// \param[in] ITraits Information about invalidation for a particular
    176   ///   region/symbol.
    177   /// \param[in,out] InvalidatedTopLevel A vector to fill with regions
    178   ////  explicitly being invalidated. Pass \c NULL if this
    179   ///   information will not be used.
    180   /// \param[in,out] Invalidated A vector to fill with any regions being
    181   ///   invalidated. This should include any regions explicitly invalidated
    182   ///   even if they do not currently have bindings. Pass \c NULL if this
    183   ///   information will not be used.
    184   virtual StoreRef invalidateRegions(Store store,
    185                                   ArrayRef<SVal> Values,
    186                                   const Expr *E, unsigned Count,
    187                                   const LocationContext *LCtx,
    188                                   const CallEvent *Call,
    189                                   InvalidatedSymbols &IS,
    190                                   RegionAndSymbolInvalidationTraits &ITraits,
    191                                   InvalidatedRegions *InvalidatedTopLevel,
    192                                   InvalidatedRegions *Invalidated) = 0;
    193 
    194   /// enterStackFrame - Let the StoreManager to do something when execution
    195   /// engine is about to execute into a callee.
    196   StoreRef enterStackFrame(Store store,
    197                            const CallEvent &Call,
    198                            const StackFrameContext *CalleeCtx);
    199 
    200   /// Finds the transitive closure of symbols within the given region.
    201   ///
    202   /// Returns false if the visitor aborted the scan.
    203   virtual bool scanReachableSymbols(Store S, const MemRegion *R,
    204                                     ScanReachableSymbols &Visitor) = 0;
    205 
    206   virtual void print(Store store, raw_ostream &Out,
    207                      const char* nl, const char *sep) = 0;
    208 
    209   class BindingsHandler {
    210   public:
    211     virtual ~BindingsHandler();
    212     virtual bool HandleBinding(StoreManager& SMgr, Store store,
    213                                const MemRegion *region, SVal val) = 0;
    214   };
    215 
    216   class FindUniqueBinding :
    217   public BindingsHandler {
    218     SymbolRef Sym;
    219     const MemRegion* Binding;
    220     bool First;
    221 
    222   public:
    223     FindUniqueBinding(SymbolRef sym)
    224       : Sym(sym), Binding(nullptr), First(true) {}
    225 
    226     bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
    227                        SVal val) override;
    228     LLVM_EXPLICIT operator bool() { return First && Binding; }
    229     const MemRegion *getRegion() { return Binding; }
    230   };
    231 
    232   /// iterBindings - Iterate over the bindings in the Store.
    233   virtual void iterBindings(Store store, BindingsHandler& f) = 0;
    234 
    235 protected:
    236   const MemRegion *MakeElementRegion(const MemRegion *baseRegion,
    237                                      QualType pointeeTy, uint64_t index = 0);
    238 
    239   /// CastRetrievedVal - Used by subclasses of StoreManager to implement
    240   ///  implicit casts that arise from loads from regions that are reinterpreted
    241   ///  as another region.
    242   SVal CastRetrievedVal(SVal val, const TypedValueRegion *region,
    243                         QualType castTy, bool performTestOnly = true);
    244 
    245 private:
    246   SVal getLValueFieldOrIvar(const Decl *decl, SVal base);
    247 };
    248 
    249 
    250 inline StoreRef::StoreRef(Store store, StoreManager & smgr)
    251   : store(store), mgr(smgr) {
    252   if (store)
    253     mgr.incrementReferenceCount(store);
    254 }
    255 
    256 inline StoreRef::StoreRef(const StoreRef &sr)
    257   : store(sr.store), mgr(sr.mgr)
    258 {
    259   if (store)
    260     mgr.incrementReferenceCount(store);
    261 }
    262 
    263 inline StoreRef::~StoreRef() {
    264   if (store)
    265     mgr.decrementReferenceCount(store);
    266 }
    267 
    268 inline StoreRef &StoreRef::operator=(StoreRef const &newStore) {
    269   assert(&newStore.mgr == &mgr);
    270   if (store != newStore.store) {
    271     mgr.incrementReferenceCount(newStore.store);
    272     mgr.decrementReferenceCount(store);
    273     store = newStore.getStore();
    274   }
    275   return *this;
    276 }
    277 
    278 // FIXME: Do we need to pass ProgramStateManager anymore?
    279 StoreManager *CreateRegionStoreManager(ProgramStateManager& StMgr);
    280 StoreManager *CreateFieldsOnlyRegionStoreManager(ProgramStateManager& StMgr);
    281 
    282 } // end GR namespace
    283 
    284 } // end clang namespace
    285 
    286 #endif
    287