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