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. 114263508Sdim virtual SVal ArrayToPointer(Loc Array, QualType ElementTy) = 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. 167218887Sdim /// \param[in] E The current statement being evaluated. Used to conjure 168218887Sdim /// symbols to mark the values of invalidated regions. 169218887Sdim /// \param[in] Count The current block count. Used to conjure 170218887Sdim /// symbols to mark the values of invalidated regions. 171249423Sdim /// \param[in] Call The call expression which will be used to determine which 172249423Sdim /// globals should get invalidated. 173218887Sdim /// \param[in,out] IS A set to fill with any symbols that are no longer 174218887Sdim /// accessible. Pass \c NULL if this information will not be used. 175263508Sdim /// \param[in] ITraits Information about invalidation for a particular 176263508Sdim /// region/symbol. 177249423Sdim /// \param[in,out] InvalidatedTopLevel A vector to fill with regions 178263508Sdim //// explicitly being invalidated. Pass \c NULL if this 179249423Sdim /// information will not be used. 180239462Sdim /// \param[in,out] Invalidated A vector to fill with any regions being 181218887Sdim /// invalidated. This should include any regions explicitly invalidated 182218887Sdim /// even if they do not currently have bindings. Pass \c NULL if this 183218887Sdim /// information will not be used. 184218887Sdim virtual StoreRef invalidateRegions(Store store, 185249423Sdim ArrayRef<SVal> Values, 186249423Sdim const Expr *E, unsigned Count, 187249423Sdim const LocationContext *LCtx, 188249423Sdim const CallEvent *Call, 189249423Sdim InvalidatedSymbols &IS, 190263508Sdim RegionAndSymbolInvalidationTraits &ITraits, 191249423Sdim InvalidatedRegions *InvalidatedTopLevel, 192249423Sdim InvalidatedRegions *Invalidated) = 0; 193218887Sdim 194218887Sdim /// enterStackFrame - Let the StoreManager to do something when execution 195218887Sdim /// engine is about to execute into a callee. 196239462Sdim StoreRef enterStackFrame(Store store, 197239462Sdim const CallEvent &Call, 198239462Sdim const StackFrameContext *CalleeCtx); 199218887Sdim 200239462Sdim /// Finds the transitive closure of symbols within the given region. 201239462Sdim /// 202239462Sdim /// Returns false if the visitor aborted the scan. 203239462Sdim virtual bool scanReachableSymbols(Store S, const MemRegion *R, 204239462Sdim ScanReachableSymbols &Visitor) = 0; 205239462Sdim 206226633Sdim virtual void print(Store store, raw_ostream &Out, 207218887Sdim const char* nl, const char *sep) = 0; 208218887Sdim 209218887Sdim class BindingsHandler { 210218887Sdim public: 211218887Sdim virtual ~BindingsHandler(); 212218887Sdim virtual bool HandleBinding(StoreManager& SMgr, Store store, 213218887Sdim const MemRegion *region, SVal val) = 0; 214218887Sdim }; 215218887Sdim 216234353Sdim class FindUniqueBinding : 217234353Sdim public BindingsHandler { 218234353Sdim SymbolRef Sym; 219234353Sdim const MemRegion* Binding; 220234353Sdim bool First; 221234353Sdim 222234353Sdim public: 223234353Sdim FindUniqueBinding(SymbolRef sym) : Sym(sym), Binding(0), First(true) {} 224234353Sdim 225234353Sdim bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R, 226234353Sdim SVal val); 227263508Sdim LLVM_EXPLICIT operator bool() { return First && Binding; } 228234353Sdim const MemRegion *getRegion() { return Binding; } 229234353Sdim }; 230234353Sdim 231218887Sdim /// iterBindings - Iterate over the bindings in the Store. 232218887Sdim virtual void iterBindings(Store store, BindingsHandler& f) = 0; 233218887Sdim 234218887Sdimprotected: 235218887Sdim const MemRegion *MakeElementRegion(const MemRegion *baseRegion, 236218887Sdim QualType pointeeTy, uint64_t index = 0); 237218887Sdim 238218887Sdim /// CastRetrievedVal - Used by subclasses of StoreManager to implement 239218887Sdim /// implicit casts that arise from loads from regions that are reinterpreted 240218887Sdim /// as another region. 241226633Sdim SVal CastRetrievedVal(SVal val, const TypedValueRegion *region, 242226633Sdim QualType castTy, bool performTestOnly = true); 243218887Sdim 244218887Sdimprivate: 245226633Sdim SVal getLValueFieldOrIvar(const Decl *decl, SVal base); 246218887Sdim}; 247218887Sdim 248218887Sdim 249218887Sdiminline StoreRef::StoreRef(Store store, StoreManager & smgr) 250218887Sdim : store(store), mgr(smgr) { 251218887Sdim if (store) 252218887Sdim mgr.incrementReferenceCount(store); 253218887Sdim} 254218887Sdim 255218887Sdiminline StoreRef::StoreRef(const StoreRef &sr) 256218887Sdim : store(sr.store), mgr(sr.mgr) 257218887Sdim{ 258218887Sdim if (store) 259218887Sdim mgr.incrementReferenceCount(store); 260218887Sdim} 261218887Sdim 262218887Sdiminline StoreRef::~StoreRef() { 263218887Sdim if (store) 264218887Sdim mgr.decrementReferenceCount(store); 265218887Sdim} 266218887Sdim 267218887Sdiminline StoreRef &StoreRef::operator=(StoreRef const &newStore) { 268218887Sdim assert(&newStore.mgr == &mgr); 269218887Sdim if (store != newStore.store) { 270218887Sdim mgr.incrementReferenceCount(newStore.store); 271218887Sdim mgr.decrementReferenceCount(store); 272218887Sdim store = newStore.getStore(); 273218887Sdim } 274218887Sdim return *this; 275218887Sdim} 276218887Sdim 277226633Sdim// FIXME: Do we need to pass ProgramStateManager anymore? 278226633SdimStoreManager *CreateRegionStoreManager(ProgramStateManager& StMgr); 279226633SdimStoreManager *CreateFieldsOnlyRegionStoreManager(ProgramStateManager& StMgr); 280218887Sdim 281218887Sdim} // end GR namespace 282218887Sdim 283218887Sdim} // end clang namespace 284218887Sdim 285218887Sdim#endif 286