contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h

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