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