1218887Sdim//== Store.h - Interface for maps from Locations to Values ------*- C++ -*--==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defined the types Store and StoreManager. 11218887Sdim// 12218887Sdim//===----------------------------------------------------------------------===// 13218887Sdim 14218887Sdim#ifndef LLVM_CLANG_GR_STORE_H 15218887Sdim#define LLVM_CLANG_GR_STORE_H 16218887Sdim 17218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 18218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 19249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 20218887Sdim#include "llvm/ADT/DenseSet.h" 21218887Sdim#include "llvm/ADT/Optional.h" 22218887Sdim 23218887Sdimnamespace clang { 24218887Sdim 25218887Sdimclass Stmt; 26218887Sdimclass Expr; 27218887Sdimclass ObjCIvarDecl; 28243830Sdimclass CXXBasePath; 29218887Sdimclass StackFrameContext; 30218887Sdim 31218887Sdimnamespace ento { 32218887Sdim 33239462Sdimclass CallEvent; 34226633Sdimclass ProgramState; 35226633Sdimclass ProgramStateManager; 36239462Sdimclass ScanReachableSymbols; 37218887Sdim 38249423Sdimtypedef llvm::DenseSet<SymbolRef> InvalidatedSymbols; 39249423Sdim 40218887Sdimclass StoreManager { 41218887Sdimprotected: 42218887Sdim SValBuilder &svalBuilder; 43226633Sdim ProgramStateManager &StateMgr; 44218887Sdim 45218887Sdim /// MRMgr - Manages region objects associated with this StoreManager. 46218887Sdim MemRegionManager &MRMgr; 47218887Sdim ASTContext &Ctx; 48218887Sdim 49226633Sdim StoreManager(ProgramStateManager &stateMgr); 50218887Sdim 51218887Sdimpublic: 52218887Sdim virtual ~StoreManager() {} 53218887Sdim 54218887Sdim /// Return the value bound to specified location in a given state. 55239462Sdim /// \param[in] store The analysis state. 56218887Sdim /// \param[in] loc The symbolic memory location. 57218887Sdim /// \param[in] T An optional type that provides a hint indicating the 58218887Sdim /// expected type of the returned value. This is used if the value is 59218887Sdim /// lazily computed. 60218887Sdim /// \return The value bound to the location \c loc. 61234353Sdim virtual SVal getBinding(Store store, Loc loc, QualType T = QualType()) = 0; 62218887Sdim 63218887Sdim /// Return a state with the specified value bound to the given location. 64239462Sdim /// \param[in] store The analysis state. 65218887Sdim /// \param[in] loc The symbolic memory location. 66218887Sdim /// \param[in] val The value to bind to location \c loc. 67239462Sdim /// \return A pointer to a ProgramState object that contains the same 68239462Sdim /// bindings as \c state with the addition of having the value specified 69239462Sdim /// by \c val bound to the location given for \c loc. 70218887Sdim virtual StoreRef Bind(Store store, Loc loc, SVal val) = 0; 71218887Sdim 72218887Sdim virtual StoreRef BindDefault(Store store, const MemRegion *R, SVal V); 73218887Sdim 74243830Sdim /// \brief Create a new store with the specified binding removed. 75243830Sdim /// \param ST the original store, that is the basis for the new store. 76243830Sdim /// \param L the location whose binding should be removed. 77243830Sdim virtual StoreRef killBinding(Store ST, Loc L) = 0; 78218887Sdim 79218887Sdim /// getInitialStore - Returns the initial "empty" store representing the 80218887Sdim /// value bindings upon entry to an analyzed function. 81218887Sdim virtual StoreRef getInitialStore(const LocationContext *InitLoc) = 0; 82218887Sdim 83218887Sdim /// getRegionManager - Returns the internal RegionManager object that is 84218887Sdim /// used to query and manipulate MemRegion objects. 85218887Sdim MemRegionManager& getRegionManager() { return MRMgr; } 86218887Sdim 87218887Sdim virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) { 88218887Sdim return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC)); 89218887Sdim } 90218887Sdim 91226633Sdim Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL, 92218887Sdim const LocationContext *LC) { 93218887Sdim return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC)); 94218887Sdim } 95218887Sdim 96234353Sdim virtual SVal getLValueIvar(const ObjCIvarDecl *decl, SVal base); 97218887Sdim 98226633Sdim virtual SVal getLValueField(const FieldDecl *D, SVal Base) { 99218887Sdim return getLValueFieldOrIvar(D, Base); 100218887Sdim } 101218887Sdim 102218887Sdim virtual SVal getLValueElement(QualType elementType, NonLoc offset, SVal Base); 103218887Sdim 104218887Sdim // FIXME: This should soon be eliminated altogether; clients should deal with 105218887Sdim // region extents directly. 106234353Sdim virtual DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, 107218887Sdim const MemRegion *region, 108218887Sdim QualType EleTy) { 109218887Sdim return UnknownVal(); 110218887Sdim } 111218887Sdim 112218887Sdim /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit 113218887Sdim /// conversions between arrays and pointers. 114218887Sdim virtual SVal ArrayToPointer(Loc Array) = 0; 115218887Sdim 116243830Sdim /// Evaluates a chain of derived-to-base casts through the path specified in 117243830Sdim /// \p Cast. 118243830Sdim SVal evalDerivedToBase(SVal Derived, const CastExpr *Cast); 119218887Sdim 120243830Sdim /// Evaluates a chain of derived-to-base casts through the specified path. 121243830Sdim SVal evalDerivedToBase(SVal Derived, const CXXBasePath &CastPath); 122243830Sdim 123239462Sdim /// Evaluates a derived-to-base cast through a single level of derivation. 124249423Sdim SVal evalDerivedToBase(SVal Derived, QualType DerivedPtrType, 125249423Sdim bool IsVirtual); 126239462Sdim 127234353Sdim /// \brief Evaluates C++ dynamic_cast cast. 128234353Sdim /// The callback may result in the following 3 scenarios: 129234353Sdim /// - Successful cast (ex: derived is subclass of base). 130234353Sdim /// - Failed cast (ex: derived is definitely not a subclass of base). 131234353Sdim /// - We don't know (base is a symbolic region and we don't have 132234353Sdim /// enough info to determine if the cast will succeed at run time). 133234353Sdim /// The function returns an SVal representing the derived class; it's 134234353Sdim /// valid only if Failed flag is set to false. 135243830Sdim SVal evalDynamicCast(SVal Base, QualType DerivedPtrType, bool &Failed); 136234353Sdim 137218887Sdim const ElementRegion *GetElementZeroRegion(const MemRegion *R, QualType T); 138218887Sdim 139218887Sdim /// castRegion - Used by ExprEngine::VisitCast to handle casts from 140218887Sdim /// a MemRegion* to a specific location type. 'R' is the region being 141218887Sdim /// casted and 'CastToTy' the result type of the cast. 142218887Sdim const MemRegion *castRegion(const MemRegion *region, QualType CastToTy); 143218887Sdim 144218887Sdim virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, 145226633Sdim SymbolReaper& SymReaper) = 0; 146218887Sdim 147226633Sdim virtual bool includedInBindings(Store store, 148226633Sdim const MemRegion *region) const = 0; 149226633Sdim 150218887Sdim /// If the StoreManager supports it, increment the reference count of 151218887Sdim /// the specified Store object. 152218887Sdim virtual void incrementReferenceCount(Store store) {} 153218887Sdim 154218887Sdim /// If the StoreManager supports it, decrement the reference count of 155218887Sdim /// the specified Store object. If the reference count hits 0, the memory 156218887Sdim /// associated with the object is recycled. 157218887Sdim virtual void decrementReferenceCount(Store store) {} 158218887Sdim 159226633Sdim typedef SmallVector<const MemRegion *, 8> InvalidatedRegions; 160218887Sdim 161218887Sdim /// invalidateRegions - Clears out the specified regions from the store, 162218887Sdim /// marking their values as unknown. Depending on the store, this may also 163218887Sdim /// invalidate additional regions that may have changed based on accessing 164218887Sdim /// the given regions. Optionally, invalidates non-static globals as well. 165218887Sdim /// \param[in] store The initial store 166249423Sdim /// \param[in] Values The values to invalidate. 167249423Sdim /// \param[in] ConstValues The values to invalidate; these are known to be 168249423Sdim /// const, so only regions accesible from them should be invalidated. 169218887Sdim /// \param[in] E The current statement being evaluated. Used to conjure 170218887Sdim /// symbols to mark the values of invalidated regions. 171218887Sdim /// \param[in] Count The current block count. Used to conjure 172218887Sdim /// symbols to mark the values of invalidated regions. 173249423Sdim /// \param[in] Call The call expression which will be used to determine which 174249423Sdim /// globals should get invalidated. 175218887Sdim /// \param[in,out] IS A set to fill with any symbols that are no longer 176218887Sdim /// accessible. Pass \c NULL if this information will not be used. 177249423Sdim /// \param[in,out] ConstIS A set to fill with any symbols corresponding to 178249423Sdim /// the ConstValues. 179249423Sdim /// \param[in,out] InvalidatedTopLevel A vector to fill with regions 180249423Sdim //// explicitely being invalidated. Pass \c NULL if this 181249423Sdim /// information will not be used. 182249423Sdim /// \param[in,out] InvalidatedTopLevelConst A vector to fill with const 183249423Sdim //// regions explicitely being invalidated. Pass \c NULL if this 184249423Sdim /// information will not be used. 185239462Sdim /// \param[in,out] Invalidated A vector to fill with any regions being 186218887Sdim /// invalidated. This should include any regions explicitly invalidated 187218887Sdim /// even if they do not currently have bindings. Pass \c NULL if this 188218887Sdim /// information will not be used. 189218887Sdim virtual StoreRef invalidateRegions(Store store, 190249423Sdim ArrayRef<SVal> Values, 191249423Sdim ArrayRef<SVal> ConstValues, 192249423Sdim const Expr *E, unsigned Count, 193249423Sdim const LocationContext *LCtx, 194249423Sdim const CallEvent *Call, 195249423Sdim InvalidatedSymbols &IS, 196249423Sdim InvalidatedSymbols &ConstIS, 197249423Sdim InvalidatedRegions *InvalidatedTopLevel, 198249423Sdim InvalidatedRegions *InvalidatedTopLevelConst, 199249423Sdim InvalidatedRegions *Invalidated) = 0; 200218887Sdim 201218887Sdim /// enterStackFrame - Let the StoreManager to do something when execution 202218887Sdim /// engine is about to execute into a callee. 203239462Sdim StoreRef enterStackFrame(Store store, 204239462Sdim const CallEvent &Call, 205239462Sdim const StackFrameContext *CalleeCtx); 206218887Sdim 207239462Sdim /// Finds the transitive closure of symbols within the given region. 208239462Sdim /// 209239462Sdim /// Returns false if the visitor aborted the scan. 210239462Sdim virtual bool scanReachableSymbols(Store S, const MemRegion *R, 211239462Sdim ScanReachableSymbols &Visitor) = 0; 212239462Sdim 213226633Sdim virtual void print(Store store, raw_ostream &Out, 214218887Sdim const char* nl, const char *sep) = 0; 215218887Sdim 216218887Sdim class BindingsHandler { 217218887Sdim public: 218218887Sdim virtual ~BindingsHandler(); 219218887Sdim virtual bool HandleBinding(StoreManager& SMgr, Store store, 220218887Sdim const MemRegion *region, SVal val) = 0; 221218887Sdim }; 222218887Sdim 223234353Sdim class FindUniqueBinding : 224234353Sdim public BindingsHandler { 225234353Sdim SymbolRef Sym; 226234353Sdim const MemRegion* Binding; 227234353Sdim bool First; 228234353Sdim 229234353Sdim public: 230234353Sdim FindUniqueBinding(SymbolRef sym) : Sym(sym), Binding(0), First(true) {} 231234353Sdim 232234353Sdim bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R, 233234353Sdim SVal val); 234234353Sdim operator bool() { return First && Binding; } 235234353Sdim const MemRegion *getRegion() { return Binding; } 236234353Sdim }; 237234353Sdim 238218887Sdim /// iterBindings - Iterate over the bindings in the Store. 239218887Sdim virtual void iterBindings(Store store, BindingsHandler& f) = 0; 240218887Sdim 241218887Sdimprotected: 242218887Sdim const MemRegion *MakeElementRegion(const MemRegion *baseRegion, 243218887Sdim QualType pointeeTy, uint64_t index = 0); 244218887Sdim 245218887Sdim /// CastRetrievedVal - Used by subclasses of StoreManager to implement 246218887Sdim /// implicit casts that arise from loads from regions that are reinterpreted 247218887Sdim /// as another region. 248226633Sdim SVal CastRetrievedVal(SVal val, const TypedValueRegion *region, 249226633Sdim QualType castTy, bool performTestOnly = true); 250218887Sdim 251218887Sdimprivate: 252226633Sdim SVal getLValueFieldOrIvar(const Decl *decl, SVal base); 253218887Sdim}; 254218887Sdim 255218887Sdim 256218887Sdiminline StoreRef::StoreRef(Store store, StoreManager & smgr) 257218887Sdim : store(store), mgr(smgr) { 258218887Sdim if (store) 259218887Sdim mgr.incrementReferenceCount(store); 260218887Sdim} 261218887Sdim 262218887Sdiminline StoreRef::StoreRef(const StoreRef &sr) 263218887Sdim : store(sr.store), mgr(sr.mgr) 264218887Sdim{ 265218887Sdim if (store) 266218887Sdim mgr.incrementReferenceCount(store); 267218887Sdim} 268218887Sdim 269218887Sdiminline StoreRef::~StoreRef() { 270218887Sdim if (store) 271218887Sdim mgr.decrementReferenceCount(store); 272218887Sdim} 273218887Sdim 274218887Sdiminline StoreRef &StoreRef::operator=(StoreRef const &newStore) { 275218887Sdim assert(&newStore.mgr == &mgr); 276218887Sdim if (store != newStore.store) { 277218887Sdim mgr.incrementReferenceCount(newStore.store); 278218887Sdim mgr.decrementReferenceCount(store); 279218887Sdim store = newStore.getStore(); 280218887Sdim } 281218887Sdim return *this; 282218887Sdim} 283218887Sdim 284226633Sdim// FIXME: Do we need to pass ProgramStateManager anymore? 285226633SdimStoreManager *CreateRegionStoreManager(ProgramStateManager& StMgr); 286226633SdimStoreManager *CreateFieldsOnlyRegionStoreManager(ProgramStateManager& StMgr); 287218887Sdim 288218887Sdim} // end GR namespace 289218887Sdim 290218887Sdim} // end clang namespace 291218887Sdim 292218887Sdim#endif 293