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/StoreRef.h"
     18 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
     19 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.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 StackFrameContext;
     29 
     30 namespace ento {
     31 
     32 class ProgramState;
     33 class ProgramStateManager;
     34 class SubRegionMap;
     35 
     36 class StoreManager {
     37 protected:
     38   SValBuilder &svalBuilder;
     39   ProgramStateManager &StateMgr;
     40 
     41   /// MRMgr - Manages region objects associated with this StoreManager.
     42   MemRegionManager &MRMgr;
     43   ASTContext &Ctx;
     44 
     45   StoreManager(ProgramStateManager &stateMgr);
     46 
     47 public:
     48   virtual ~StoreManager() {}
     49 
     50   /// Return the value bound to specified location in a given state.
     51   /// \param[in] state The analysis state.
     52   /// \param[in] loc The symbolic memory location.
     53   /// \param[in] T An optional type that provides a hint indicating the
     54   ///   expected type of the returned value.  This is used if the value is
     55   ///   lazily computed.
     56   /// \return The value bound to the location \c loc.
     57   virtual SVal Retrieve(Store store, Loc loc, QualType T = QualType()) = 0;
     58 
     59   /// Return a state with the specified value bound to the given location.
     60   /// \param[in] state The analysis state.
     61   /// \param[in] loc The symbolic memory location.
     62   /// \param[in] val The value to bind to location \c loc.
     63   /// \return A pointer to a ProgramState object that contains the same bindings as
     64   ///   \c state with the addition of having the value specified by \c val bound
     65   ///   to the location given for \c loc.
     66   virtual StoreRef Bind(Store store, Loc loc, SVal val) = 0;
     67 
     68   virtual StoreRef BindDefault(Store store, const MemRegion *R, SVal V);
     69   virtual StoreRef Remove(Store St, Loc L) = 0;
     70 
     71   /// BindCompoundLiteral - Return the store that has the bindings currently
     72   ///  in 'store' plus the bindings for the CompoundLiteral.  'R' is the region
     73   ///  for the compound literal and 'BegInit' and 'EndInit' represent an
     74   ///  array of initializer values.
     75   virtual StoreRef BindCompoundLiteral(Store store,
     76                                        const CompoundLiteralExpr *cl,
     77                                        const LocationContext *LC, SVal v) = 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   /// getSubRegionMap - Returns an opaque map object that clients can query
     88   ///  to get the subregions of a given MemRegion object.  It is the
     89   //   caller's responsibility to 'delete' the returned map.
     90   virtual SubRegionMap *getSubRegionMap(Store store) = 0;
     91 
     92   virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) {
     93     return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC));
     94   }
     95 
     96   virtual Loc getLValueString(const StringLiteral* S) {
     97     return svalBuilder.makeLoc(MRMgr.getStringRegion(S));
     98   }
     99 
    100   Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL,
    101                                const LocationContext *LC) {
    102     return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC));
    103   }
    104 
    105   virtual SVal getLValueIvar(const ObjCIvarDecl *decl, SVal base) {
    106     return getLValueFieldOrIvar(decl, base);
    107   }
    108 
    109   virtual SVal getLValueField(const FieldDecl *D, SVal Base) {
    110     return getLValueFieldOrIvar(D, Base);
    111   }
    112 
    113   virtual SVal getLValueElement(QualType elementType, NonLoc offset, SVal Base);
    114 
    115   // FIXME: This should soon be eliminated altogether; clients should deal with
    116   // region extents directly.
    117   virtual DefinedOrUnknownSVal getSizeInElements(const ProgramState *state,
    118                                                  const MemRegion *region,
    119                                                  QualType EleTy) {
    120     return UnknownVal();
    121   }
    122 
    123   /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
    124   ///  conversions between arrays and pointers.
    125   virtual SVal ArrayToPointer(Loc Array) = 0;
    126 
    127   /// Evaluates DerivedToBase casts.
    128   virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType) {
    129     return UnknownVal();
    130   }
    131 
    132   class CastResult {
    133     const ProgramState *state;
    134     const MemRegion *region;
    135   public:
    136     const ProgramState *getState() const { return state; }
    137     const MemRegion* getRegion() const { return region; }
    138     CastResult(const ProgramState *s, const MemRegion* r = 0) : state(s), region(r){}
    139   };
    140 
    141   const ElementRegion *GetElementZeroRegion(const MemRegion *R, QualType T);
    142 
    143   /// castRegion - Used by ExprEngine::VisitCast to handle casts from
    144   ///  a MemRegion* to a specific location type.  'R' is the region being
    145   ///  casted and 'CastToTy' the result type of the cast.
    146   const MemRegion *castRegion(const MemRegion *region, QualType CastToTy);
    147 
    148   virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
    149                                       SymbolReaper& SymReaper) = 0;
    150 
    151   virtual StoreRef BindDecl(Store store, const VarRegion *VR, SVal initVal) = 0;
    152 
    153   virtual StoreRef BindDeclWithNoInit(Store store, const VarRegion *VR) = 0;
    154 
    155   virtual bool includedInBindings(Store store,
    156                                   const MemRegion *region) const = 0;
    157 
    158   /// If the StoreManager supports it, increment the reference count of
    159   /// the specified Store object.
    160   virtual void incrementReferenceCount(Store store) {}
    161 
    162   /// If the StoreManager supports it, decrement the reference count of
    163   /// the specified Store object.  If the reference count hits 0, the memory
    164   /// associated with the object is recycled.
    165   virtual void decrementReferenceCount(Store store) {}
    166 
    167   typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
    168   typedef SmallVector<const MemRegion *, 8> InvalidatedRegions;
    169 
    170   /// invalidateRegions - Clears out the specified regions from the store,
    171   ///  marking their values as unknown. Depending on the store, this may also
    172   ///  invalidate additional regions that may have changed based on accessing
    173   ///  the given regions. Optionally, invalidates non-static globals as well.
    174   /// \param[in] store The initial store
    175   /// \param[in] Begin A pointer to the first region to invalidate.
    176   /// \param[in] End A pointer just past the last region to invalidate.
    177   /// \param[in] E The current statement being evaluated. Used to conjure
    178   ///   symbols to mark the values of invalidated regions.
    179   /// \param[in] Count The current block count. Used to conjure
    180   ///   symbols to mark the values of invalidated regions.
    181   /// \param[in,out] IS A set to fill with any symbols that are no longer
    182   ///   accessible. Pass \c NULL if this information will not be used.
    183   /// \param[in] invalidateGlobals If \c true, any non-static global regions
    184   ///   are invalidated as well.
    185   /// \param[in,out] Regions A vector to fill with any regions being
    186   ///   invalidated. This should include any regions explicitly invalidated
    187   ///   even if they do not currently have bindings. Pass \c NULL if this
    188   ///   information will not be used.
    189   virtual StoreRef invalidateRegions(Store store,
    190                                      ArrayRef<const MemRegion *> Regions,
    191                                      const Expr *E, unsigned Count,
    192                                      InvalidatedSymbols &IS,
    193                                      bool invalidateGlobals,
    194                                      InvalidatedRegions *Invalidated) = 0;
    195 
    196   /// enterStackFrame - Let the StoreManager to do something when execution
    197   /// engine is about to execute into a callee.
    198   virtual StoreRef enterStackFrame(const ProgramState *state,
    199                                    const StackFrameContext *frame);
    200 
    201   virtual void print(Store store, raw_ostream &Out,
    202                      const char* nl, const char *sep) = 0;
    203 
    204   class BindingsHandler {
    205   public:
    206     virtual ~BindingsHandler();
    207     virtual bool HandleBinding(StoreManager& SMgr, Store store,
    208                                const MemRegion *region, SVal val) = 0;
    209   };
    210 
    211   /// iterBindings - Iterate over the bindings in the Store.
    212   virtual void iterBindings(Store store, BindingsHandler& f) = 0;
    213 
    214 protected:
    215   const MemRegion *MakeElementRegion(const MemRegion *baseRegion,
    216                                      QualType pointeeTy, uint64_t index = 0);
    217 
    218   /// CastRetrievedVal - Used by subclasses of StoreManager to implement
    219   ///  implicit casts that arise from loads from regions that are reinterpreted
    220   ///  as another region.
    221   SVal CastRetrievedVal(SVal val, const TypedValueRegion *region,
    222                         QualType castTy, bool performTestOnly = true);
    223 
    224 private:
    225   SVal getLValueFieldOrIvar(const Decl *decl, SVal base);
    226 };
    227 
    228 
    229 inline StoreRef::StoreRef(Store store, StoreManager & smgr)
    230   : store(store), mgr(smgr) {
    231   if (store)
    232     mgr.incrementReferenceCount(store);
    233 }
    234 
    235 inline StoreRef::StoreRef(const StoreRef &sr)
    236   : store(sr.store), mgr(sr.mgr)
    237 {
    238   if (store)
    239     mgr.incrementReferenceCount(store);
    240 }
    241 
    242 inline StoreRef::~StoreRef() {
    243   if (store)
    244     mgr.decrementReferenceCount(store);
    245 }
    246 
    247 inline StoreRef &StoreRef::operator=(StoreRef const &newStore) {
    248   assert(&newStore.mgr == &mgr);
    249   if (store != newStore.store) {
    250     mgr.incrementReferenceCount(newStore.store);
    251     mgr.decrementReferenceCount(store);
    252     store = newStore.getStore();
    253   }
    254   return *this;
    255 }
    256 
    257 // FIXME: Do we still need this?
    258 /// SubRegionMap - An abstract interface that represents a queryable map
    259 ///  between MemRegion objects and their subregions.
    260 class SubRegionMap {
    261 public:
    262   virtual ~SubRegionMap() {}
    263 
    264   class Visitor {
    265   public:
    266     virtual ~Visitor() {}
    267     virtual bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) = 0;
    268   };
    269 
    270   virtual bool iterSubRegions(const MemRegion *region, Visitor& V) const = 0;
    271 };
    272 
    273 // FIXME: Do we need to pass ProgramStateManager anymore?
    274 StoreManager *CreateRegionStoreManager(ProgramStateManager& StMgr);
    275 StoreManager *CreateFieldsOnlyRegionStoreManager(ProgramStateManager& StMgr);
    276 
    277 } // end GR namespace
    278 
    279 } // end clang namespace
    280 
    281 #endif
    282