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/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) = 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] ConstValues The values to invalidate; these are known to be
 168   ///   const, so only regions accesible from them should be invalidated.
 169   /// \param[in] E The current statement being evaluated. Used to conjure
 170   ///   symbols to mark the values of invalidated regions.
 171   /// \param[in] Count The current block count. Used to conjure
 172   ///   symbols to mark the values of invalidated regions.
 173   /// \param[in] Call The call expression which will be used to determine which
 174   ///   globals should get invalidated.
 175   /// \param[in,out] IS A set to fill with any symbols that are no longer
 176   ///   accessible. Pass \c NULL if this information will not be used.
 177   /// \param[in,out] ConstIS A set to fill with any symbols corresponding to
 178   ///   the ConstValues.
 179   /// \param[in,out] InvalidatedTopLevel A vector to fill with regions
 180   ////  explicitely being invalidated. Pass \c NULL if this
 181   ///   information will not be used.
 182   /// \param[in,out] InvalidatedTopLevelConst A vector to fill with const
 183   ////  regions explicitely being invalidated. Pass \c NULL if this
 184   ///   information will not be used.
 185   /// \param[in,out] Invalidated 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<SVal> Values,
 191                                   ArrayRef<SVal> ConstValues,
 192                                   const Expr *E, unsigned Count,
 193                                   const LocationContext *LCtx,
 194                                   const CallEvent *Call,
 195                                   InvalidatedSymbols &IS,
 196                                   InvalidatedSymbols &ConstIS,
 197                                   InvalidatedRegions *InvalidatedTopLevel,
 198                                   InvalidatedRegions *InvalidatedTopLevelConst,
 199                                   InvalidatedRegions *Invalidated) = 0;
 200
 201   /// enterStackFrame - Let the StoreManager to do something when execution
 202   /// engine is about to execute into a callee.
 203   StoreRef enterStackFrame(Store store,
 204                            const CallEvent &Call,
 205                            const StackFrameContext *CalleeCtx);
 206
 207   /// Finds the transitive closure of symbols within the given region.
 208   ///
 209   /// Returns false if the visitor aborted the scan.
 210   virtual bool scanReachableSymbols(Store S, const MemRegion *R,
 211                                     ScanReachableSymbols &Visitor) = 0;
 212
 213   virtual void print(Store store, raw_ostream &Out,
 214                      const char* nl, const char *sep) = 0;
 215
 216   class BindingsHandler {
 217   public:
 218     virtual ~BindingsHandler();
 219     virtual bool HandleBinding(StoreManager& SMgr, Store store,
 220                                const MemRegion *region, SVal val) = 0;
 221   };
 222
 223   class FindUniqueBinding :
 224   public BindingsHandler {
 225     SymbolRef Sym;
 226     const MemRegion* Binding;
 227     bool First;
 228
 229   public:
 230     FindUniqueBinding(SymbolRef sym) : Sym(sym), Binding(0), First(true) {}
 231
 232     bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
 233                        SVal val);
 234     operator bool() { return First && Binding; }
 235     const MemRegion *getRegion() { return Binding; }
 236   };
 237
 238   /// iterBindings - Iterate over the bindings in the Store.
 239   virtual void iterBindings(Store store, BindingsHandler& f) = 0;
 240
 241 protected:
 242   const MemRegion *MakeElementRegion(const MemRegion *baseRegion,
 243                                      QualType pointeeTy, uint64_t index = 0);
 244
 245   /// CastRetrievedVal - Used by subclasses of StoreManager to implement
 246   ///  implicit casts that arise from loads from regions that are reinterpreted
 247   ///  as another region.
 248   SVal CastRetrievedVal(SVal val, const TypedValueRegion *region,
 249                         QualType castTy, bool performTestOnly = true);
 250
 251 private:
 252   SVal getLValueFieldOrIvar(const Decl *decl, SVal base);
 253 };
 254
 255
 256 inline StoreRef::StoreRef(Store store, StoreManager & smgr)
 257   : store(store), mgr(smgr) {
 258   if (store)
 259     mgr.incrementReferenceCount(store);
 260 }
 261
 262 inline StoreRef::StoreRef(const StoreRef &sr)
 263   : store(sr.store), mgr(sr.mgr)
 264 {
 265   if (store)
 266     mgr.incrementReferenceCount(store);
 267 }
 268
 269 inline StoreRef::~StoreRef() {
 270   if (store)
 271     mgr.decrementReferenceCount(store);
 272 }
 273
 274 inline StoreRef &StoreRef::operator=(StoreRef const &newStore) {
 275   assert(&newStore.mgr == &mgr);
 276   if (store != newStore.store) {
 277     mgr.incrementReferenceCount(newStore.store);
 278     mgr.decrementReferenceCount(store);
 279     store = newStore.getStore();
 280   }
 281   return *this;
 282 }
 283
 284 // FIXME: Do we need to pass ProgramStateManager anymore?
 285 StoreManager *CreateRegionStoreManager(ProgramStateManager& StMgr);
 286 StoreManager *CreateFieldsOnlyRegionStoreManager(ProgramStateManager& StMgr);
 287
 288 } // end GR namespace
 289
 290 } // end clang namespace
 291
 292 #endif