1226586Sdim//== ProgramState.h - Path-sensitive "State" for tracking values -*- C++ -*--=// 2226586Sdim// 3226586Sdim// The LLVM Compiler Infrastructure 4226586Sdim// 5226586Sdim// This file is distributed under the University of Illinois Open Source 6226586Sdim// License. See LICENSE.TXT for details. 7226586Sdim// 8226586Sdim//===----------------------------------------------------------------------===// 9226586Sdim// 10243830Sdim// This file defines the state of the program along the analysisa path. 11226586Sdim// 12226586Sdim//===----------------------------------------------------------------------===// 13226586Sdim 14226586Sdim#ifndef LLVM_CLANG_GR_VALUESTATE_H 15226586Sdim#define LLVM_CLANG_GR_VALUESTATE_H 16226586Sdim 17226586Sdim#include "clang/Basic/LLVM.h" 18226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" 19243830Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h" 20226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" 21249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 22249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 23226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 24234353Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h" 25226586Sdim#include "llvm/ADT/FoldingSet.h" 26226586Sdim#include "llvm/ADT/ImmutableMap.h" 27249423Sdim#include "llvm/ADT/PointerIntPair.h" 28226586Sdim 29226586Sdimnamespace llvm { 30226586Sdimclass APSInt; 31226586Sdimclass BumpPtrAllocator; 32226586Sdim} 33226586Sdim 34226586Sdimnamespace clang { 35226586Sdimclass ASTContext; 36226586Sdim 37226586Sdimnamespace ento { 38226586Sdim 39239462Sdimclass CallEvent; 40239462Sdimclass CallEventManager; 41226586Sdim 42226586Sdimtypedef ConstraintManager* (*ConstraintManagerCreator)(ProgramStateManager&, 43243830Sdim SubEngine*); 44226586Sdimtypedef StoreManager* (*StoreManagerCreator)(ProgramStateManager&); 45226586Sdim 46226586Sdim//===----------------------------------------------------------------------===// 47226586Sdim// ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState. 48226586Sdim//===----------------------------------------------------------------------===// 49226586Sdim 50226586Sdimtemplate <typename T> struct ProgramStatePartialTrait; 51226586Sdim 52226586Sdimtemplate <typename T> struct ProgramStateTrait { 53226586Sdim typedef typename T::data_type data_type; 54226586Sdim static inline void *MakeVoidPtr(data_type D) { return (void*) D; } 55226586Sdim static inline data_type MakeData(void *const* P) { 56226586Sdim return P ? (data_type) *P : (data_type) 0; 57226586Sdim } 58226586Sdim}; 59226586Sdim 60226586Sdim/// \class ProgramState 61226586Sdim/// ProgramState - This class encapsulates: 62226586Sdim/// 63226586Sdim/// 1. A mapping from expressions to values (Environment) 64226586Sdim/// 2. A mapping from locations to values (Store) 65226586Sdim/// 3. Constraints on symbolic values (GenericDataMap) 66226586Sdim/// 67226586Sdim/// Together these represent the "abstract state" of a program. 68226586Sdim/// 69226586Sdim/// ProgramState is intended to be used as a functional object; that is, 70226586Sdim/// once it is created and made "persistent" in a FoldingSet, its 71226586Sdim/// values will never change. 72226586Sdimclass ProgramState : public llvm::FoldingSetNode { 73226586Sdimpublic: 74226586Sdim typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; 75226586Sdim typedef llvm::ImmutableMap<void*, void*> GenericDataMap; 76226586Sdim 77226586Sdimprivate: 78243830Sdim void operator=(const ProgramState& R) LLVM_DELETED_FUNCTION; 79226586Sdim 80226586Sdim friend class ProgramStateManager; 81226586Sdim friend class ExplodedGraph; 82226586Sdim friend class ExplodedNode; 83226586Sdim 84226586Sdim ProgramStateManager *stateMgr; 85226586Sdim Environment Env; // Maps a Stmt to its current SVal. 86226586Sdim Store store; // Maps a location to its current value. 87226586Sdim GenericDataMap GDM; // Custom data stored by a client of this class. 88226586Sdim unsigned refCount; 89226586Sdim 90226586Sdim /// makeWithStore - Return a ProgramState with the same values as the current 91226586Sdim /// state with the exception of using the specified Store. 92234353Sdim ProgramStateRef makeWithStore(const StoreRef &store) const; 93226586Sdim 94226586Sdim void setStore(const StoreRef &storeRef); 95226586Sdim 96226586Sdimpublic: 97226586Sdim /// This ctor is used when creating the first ProgramState object. 98226586Sdim ProgramState(ProgramStateManager *mgr, const Environment& env, 99226586Sdim StoreRef st, GenericDataMap gdm); 100226586Sdim 101226586Sdim /// Copy ctor - We must explicitly define this or else the "Next" ptr 102226586Sdim /// in FoldingSetNode will also get copied. 103226586Sdim ProgramState(const ProgramState &RHS); 104226586Sdim 105226586Sdim ~ProgramState(); 106226586Sdim 107226586Sdim /// Return the ProgramStateManager associated with this state. 108243830Sdim ProgramStateManager &getStateManager() const { 109243830Sdim return *stateMgr; 110243830Sdim } 111243830Sdim 112243830Sdim /// Return the ConstraintManager. 113243830Sdim ConstraintManager &getConstraintManager() const; 114226586Sdim 115226586Sdim /// getEnvironment - Return the environment associated with this state. 116226586Sdim /// The environment is the mapping from expressions to values. 117226586Sdim const Environment& getEnvironment() const { return Env; } 118226586Sdim 119226586Sdim /// Return the store associated with this state. The store 120226586Sdim /// is a mapping from locations to values. 121226586Sdim Store getStore() const { return store; } 122226586Sdim 123226586Sdim 124226586Sdim /// getGDM - Return the generic data map associated with this state. 125226586Sdim GenericDataMap getGDM() const { return GDM; } 126226586Sdim 127226586Sdim void setGDM(GenericDataMap gdm) { GDM = gdm; } 128226586Sdim 129226586Sdim /// Profile - Profile the contents of a ProgramState object for use in a 130226586Sdim /// FoldingSet. Two ProgramState objects are considered equal if they 131226586Sdim /// have the same Environment, Store, and GenericDataMap. 132226586Sdim static void Profile(llvm::FoldingSetNodeID& ID, const ProgramState *V) { 133226586Sdim V->Env.Profile(ID); 134226586Sdim ID.AddPointer(V->store); 135226586Sdim V->GDM.Profile(ID); 136226586Sdim } 137226586Sdim 138226586Sdim /// Profile - Used to profile the contents of this object for inclusion 139226586Sdim /// in a FoldingSet. 140226586Sdim void Profile(llvm::FoldingSetNodeID& ID) const { 141226586Sdim Profile(ID, this); 142226586Sdim } 143226586Sdim 144226586Sdim BasicValueFactory &getBasicVals() const; 145226586Sdim SymbolManager &getSymbolManager() const; 146226586Sdim 147226586Sdim //==---------------------------------------------------------------------==// 148226586Sdim // Constraints on values. 149226586Sdim //==---------------------------------------------------------------------==// 150226586Sdim // 151226586Sdim // Each ProgramState records constraints on symbolic values. These constraints 152226586Sdim // are managed using the ConstraintManager associated with a ProgramStateManager. 153226586Sdim // As constraints gradually accrue on symbolic values, added constraints 154226586Sdim // may conflict and indicate that a state is infeasible (as no real values 155226586Sdim // could satisfy all the constraints). This is the principal mechanism 156226586Sdim // for modeling path-sensitivity in ExprEngine/ProgramState. 157226586Sdim // 158226586Sdim // Various "assume" methods form the interface for adding constraints to 159226586Sdim // symbolic values. A call to 'assume' indicates an assumption being placed 160226586Sdim // on one or symbolic values. 'assume' methods take the following inputs: 161226586Sdim // 162226586Sdim // (1) A ProgramState object representing the current state. 163226586Sdim // 164226586Sdim // (2) The assumed constraint (which is specific to a given "assume" method). 165226586Sdim // 166226586Sdim // (3) A binary value "Assumption" that indicates whether the constraint is 167226586Sdim // assumed to be true or false. 168226586Sdim // 169226586Sdim // The output of "assume*" is a new ProgramState object with the added constraints. 170226586Sdim // If no new state is feasible, NULL is returned. 171226586Sdim // 172226586Sdim 173249423Sdim /// Assumes that the value of \p cond is zero (if \p assumption is "false") 174249423Sdim /// or non-zero (if \p assumption is "true"). 175249423Sdim /// 176249423Sdim /// This returns a new state with the added constraint on \p cond. 177249423Sdim /// If no new state is feasible, NULL is returned. 178234353Sdim ProgramStateRef assume(DefinedOrUnknownSVal cond, bool assumption) const; 179226586Sdim 180249423Sdim /// Assumes both "true" and "false" for \p cond, and returns both 181249423Sdim /// corresponding states (respectively). 182249423Sdim /// 183249423Sdim /// This is more efficient than calling assume() twice. Note that one (but not 184249423Sdim /// both) of the returned states may be NULL. 185249423Sdim std::pair<ProgramStateRef, ProgramStateRef> 186226586Sdim assume(DefinedOrUnknownSVal cond) const; 187226586Sdim 188234353Sdim ProgramStateRef assumeInBound(DefinedOrUnknownSVal idx, 189226586Sdim DefinedOrUnknownSVal upperBound, 190234353Sdim bool assumption, 191234353Sdim QualType IndexType = QualType()) const; 192249423Sdim 193249423Sdim /// \brief Check if the given SVal is constrained to zero or is a zero 194249423Sdim /// constant. 195249423Sdim ConditionTruthVal isNull(SVal V) const; 196249423Sdim 197226586Sdim /// Utility method for getting regions. 198226586Sdim const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; 199226586Sdim 200226586Sdim //==---------------------------------------------------------------------==// 201226586Sdim // Binding and retrieving values to/from the environment and symbolic store. 202226586Sdim //==---------------------------------------------------------------------==// 203226586Sdim 204226586Sdim /// Create a new state by binding the value 'V' to the statement 'S' in the 205226586Sdim /// state's environment. 206234353Sdim ProgramStateRef BindExpr(const Stmt *S, const LocationContext *LCtx, 207234353Sdim SVal V, bool Invalidate = true) const; 208226586Sdim 209243830Sdim ProgramStateRef bindLoc(Loc location, 210243830Sdim SVal V, 211243830Sdim bool notifyChanges = true) const; 212226586Sdim 213234353Sdim ProgramStateRef bindLoc(SVal location, SVal V) const; 214226586Sdim 215234353Sdim ProgramStateRef bindDefault(SVal loc, SVal V) const; 216226586Sdim 217243830Sdim ProgramStateRef killBinding(Loc LV) const; 218226586Sdim 219249423Sdim /// \brief Returns the state with bindings for the given regions 220249423Sdim /// cleared from the store. 221249423Sdim /// 222249423Sdim /// Optionally invalidates global regions as well. 223249423Sdim /// 224249423Sdim /// \param Regions the set of regions to be invalidated. 225249423Sdim /// \param E the expression that caused the invalidation. 226249423Sdim /// \param BlockCount The number of times the current basic block has been 227249423Sdim // visited. 228249423Sdim /// \param CausesPointerEscape the flag is set to true when 229249423Sdim /// the invalidation entails escape of a symbol (representing a 230249423Sdim /// pointer). For example, due to it being passed as an argument in a 231249423Sdim /// call. 232249423Sdim /// \param IS the set of invalidated symbols. 233249423Sdim /// \param Call if non-null, the invalidated regions represent parameters to 234249423Sdim /// the call and should be considered directly invalidated. 235263508Sdim /// \param ITraits information about special handling for a particular 236263508Sdim /// region/symbol. 237249423Sdim ProgramStateRef 238249423Sdim invalidateRegions(ArrayRef<const MemRegion *> Regions, const Expr *E, 239249423Sdim unsigned BlockCount, const LocationContext *LCtx, 240249423Sdim bool CausesPointerEscape, InvalidatedSymbols *IS = 0, 241249423Sdim const CallEvent *Call = 0, 242263508Sdim RegionAndSymbolInvalidationTraits *ITraits = 0) const; 243226586Sdim 244249423Sdim ProgramStateRef 245249423Sdim invalidateRegions(ArrayRef<SVal> Regions, const Expr *E, 246249423Sdim unsigned BlockCount, const LocationContext *LCtx, 247249423Sdim bool CausesPointerEscape, InvalidatedSymbols *IS = 0, 248249423Sdim const CallEvent *Call = 0, 249263508Sdim RegionAndSymbolInvalidationTraits *ITraits = 0) const; 250249423Sdim 251226586Sdim /// enterStackFrame - Returns the state for entry to the given stack frame, 252226586Sdim /// preserving the current state. 253239462Sdim ProgramStateRef enterStackFrame(const CallEvent &Call, 254239462Sdim const StackFrameContext *CalleeCtx) const; 255226586Sdim 256226586Sdim /// Get the lvalue for a variable reference. 257226586Sdim Loc getLValue(const VarDecl *D, const LocationContext *LC) const; 258226586Sdim 259226586Sdim Loc getLValue(const CompoundLiteralExpr *literal, 260226586Sdim const LocationContext *LC) const; 261226586Sdim 262226586Sdim /// Get the lvalue for an ivar reference. 263226586Sdim SVal getLValue(const ObjCIvarDecl *decl, SVal base) const; 264226586Sdim 265226586Sdim /// Get the lvalue for a field reference. 266226586Sdim SVal getLValue(const FieldDecl *decl, SVal Base) const; 267226586Sdim 268239462Sdim /// Get the lvalue for an indirect field reference. 269239462Sdim SVal getLValue(const IndirectFieldDecl *decl, SVal Base) const; 270239462Sdim 271226586Sdim /// Get the lvalue for an array index. 272226586Sdim SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; 273226586Sdim 274226586Sdim /// Returns the SVal bound to the statement 'S' in the state's environment. 275243830Sdim SVal getSVal(const Stmt *S, const LocationContext *LCtx) const; 276226586Sdim 277234353Sdim SVal getSValAsScalarOrLoc(const Stmt *Ex, const LocationContext *LCtx) const; 278226586Sdim 279234353Sdim /// \brief Return the value bound to the specified location. 280234353Sdim /// Returns UnknownVal() if none found. 281226586Sdim SVal getSVal(Loc LV, QualType T = QualType()) const; 282226586Sdim 283226586Sdim /// Returns the "raw" SVal bound to LV before any value simplfication. 284226586Sdim SVal getRawSVal(Loc LV, QualType T= QualType()) const; 285226586Sdim 286234353Sdim /// \brief Return the value bound to the specified location. 287234353Sdim /// Returns UnknownVal() if none found. 288226586Sdim SVal getSVal(const MemRegion* R) const; 289226586Sdim 290226586Sdim SVal getSValAsScalarOrLoc(const MemRegion *R) const; 291226586Sdim 292226586Sdim /// \brief Visits the symbols reachable from the given SVal using the provided 293226586Sdim /// SymbolVisitor. 294226586Sdim /// 295226586Sdim /// This is a convenience API. Consider using ScanReachableSymbols class 296226586Sdim /// directly when making multiple scans on the same state with the same 297226586Sdim /// visitor to avoid repeated initialization cost. 298226586Sdim /// \sa ScanReachableSymbols 299226586Sdim bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; 300226586Sdim 301226586Sdim /// \brief Visits the symbols reachable from the SVals in the given range 302226586Sdim /// using the provided SymbolVisitor. 303226586Sdim bool scanReachableSymbols(const SVal *I, const SVal *E, 304226586Sdim SymbolVisitor &visitor) const; 305226586Sdim 306226586Sdim /// \brief Visits the symbols reachable from the regions in the given 307226586Sdim /// MemRegions range using the provided SymbolVisitor. 308226586Sdim bool scanReachableSymbols(const MemRegion * const *I, 309226586Sdim const MemRegion * const *E, 310226586Sdim SymbolVisitor &visitor) const; 311226586Sdim 312226586Sdim template <typename CB> CB scanReachableSymbols(SVal val) const; 313226586Sdim template <typename CB> CB scanReachableSymbols(const SVal *beg, 314226586Sdim const SVal *end) const; 315226586Sdim 316226586Sdim template <typename CB> CB 317226586Sdim scanReachableSymbols(const MemRegion * const *beg, 318226586Sdim const MemRegion * const *end) const; 319226586Sdim 320234353Sdim /// Create a new state in which the statement is marked as tainted. 321234353Sdim ProgramStateRef addTaint(const Stmt *S, const LocationContext *LCtx, 322234353Sdim TaintTagType Kind = TaintTagGeneric) const; 323234353Sdim 324234353Sdim /// Create a new state in which the symbol is marked as tainted. 325234353Sdim ProgramStateRef addTaint(SymbolRef S, 326234353Sdim TaintTagType Kind = TaintTagGeneric) const; 327234353Sdim 328234353Sdim /// Create a new state in which the region symbol is marked as tainted. 329234353Sdim ProgramStateRef addTaint(const MemRegion *R, 330234353Sdim TaintTagType Kind = TaintTagGeneric) const; 331234353Sdim 332234353Sdim /// Check if the statement is tainted in the current state. 333234353Sdim bool isTainted(const Stmt *S, const LocationContext *LCtx, 334234353Sdim TaintTagType Kind = TaintTagGeneric) const; 335234353Sdim bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const; 336234353Sdim bool isTainted(SymbolRef Sym, TaintTagType Kind = TaintTagGeneric) const; 337234353Sdim bool isTainted(const MemRegion *Reg, TaintTagType Kind=TaintTagGeneric) const; 338234353Sdim 339239462Sdim /// \brief Get dynamic type information for a region. 340239462Sdim DynamicTypeInfo getDynamicTypeInfo(const MemRegion *Reg) const; 341239462Sdim 342239462Sdim /// \brief Set dynamic type information of the region; return the new state. 343239462Sdim ProgramStateRef setDynamicTypeInfo(const MemRegion *Reg, 344239462Sdim DynamicTypeInfo NewTy) const; 345239462Sdim 346239462Sdim /// \brief Set dynamic type information of the region; return the new state. 347239462Sdim ProgramStateRef setDynamicTypeInfo(const MemRegion *Reg, 348239462Sdim QualType NewTy, 349239462Sdim bool CanBeSubClassed = true) const { 350239462Sdim return setDynamicTypeInfo(Reg, DynamicTypeInfo(NewTy, CanBeSubClassed)); 351239462Sdim } 352239462Sdim 353226586Sdim //==---------------------------------------------------------------------==// 354226586Sdim // Accessing the Generic Data Map (GDM). 355226586Sdim //==---------------------------------------------------------------------==// 356226586Sdim 357226586Sdim void *const* FindGDM(void *K) const; 358226586Sdim 359226586Sdim template<typename T> 360234353Sdim ProgramStateRef add(typename ProgramStateTrait<T>::key_type K) const; 361226586Sdim 362226586Sdim template <typename T> 363226586Sdim typename ProgramStateTrait<T>::data_type 364226586Sdim get() const { 365226586Sdim return ProgramStateTrait<T>::MakeData(FindGDM(ProgramStateTrait<T>::GDMIndex())); 366226586Sdim } 367226586Sdim 368226586Sdim template<typename T> 369226586Sdim typename ProgramStateTrait<T>::lookup_type 370226586Sdim get(typename ProgramStateTrait<T>::key_type key) const { 371226586Sdim void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); 372226586Sdim return ProgramStateTrait<T>::Lookup(ProgramStateTrait<T>::MakeData(d), key); 373226586Sdim } 374226586Sdim 375226586Sdim template <typename T> 376226586Sdim typename ProgramStateTrait<T>::context_type get_context() const; 377226586Sdim 378226586Sdim 379226586Sdim template<typename T> 380234353Sdim ProgramStateRef remove(typename ProgramStateTrait<T>::key_type K) const; 381226586Sdim 382226586Sdim template<typename T> 383234353Sdim ProgramStateRef remove(typename ProgramStateTrait<T>::key_type K, 384226586Sdim typename ProgramStateTrait<T>::context_type C) const; 385226586Sdim template <typename T> 386234353Sdim ProgramStateRef remove() const; 387226586Sdim 388226586Sdim template<typename T> 389234353Sdim ProgramStateRef set(typename ProgramStateTrait<T>::data_type D) const; 390226586Sdim 391226586Sdim template<typename T> 392234353Sdim ProgramStateRef set(typename ProgramStateTrait<T>::key_type K, 393226586Sdim typename ProgramStateTrait<T>::value_type E) const; 394226586Sdim 395226586Sdim template<typename T> 396234353Sdim ProgramStateRef set(typename ProgramStateTrait<T>::key_type K, 397226586Sdim typename ProgramStateTrait<T>::value_type E, 398226586Sdim typename ProgramStateTrait<T>::context_type C) const; 399226586Sdim 400226586Sdim template<typename T> 401226586Sdim bool contains(typename ProgramStateTrait<T>::key_type key) const { 402226586Sdim void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); 403226586Sdim return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key); 404226586Sdim } 405226586Sdim 406226586Sdim // Pretty-printing. 407234353Sdim void print(raw_ostream &Out, const char *nl = "\n", 408226586Sdim const char *sep = "") const; 409234353Sdim void printDOT(raw_ostream &Out) const; 410234353Sdim void printTaint(raw_ostream &Out, const char *nl = "\n", 411234353Sdim const char *sep = "") const; 412226586Sdim 413234353Sdim void dump() const; 414234353Sdim void dumpTaint() const; 415226586Sdim 416226586Sdimprivate: 417234353Sdim friend void ProgramStateRetain(const ProgramState *state); 418234353Sdim friend void ProgramStateRelease(const ProgramState *state); 419249423Sdim 420249423Sdim /// \sa invalidateValues() 421249423Sdim /// \sa invalidateRegions() 422249423Sdim ProgramStateRef 423249423Sdim invalidateRegionsImpl(ArrayRef<SVal> Values, 424226586Sdim const Expr *E, unsigned BlockCount, 425234353Sdim const LocationContext *LCtx, 426249423Sdim bool ResultsInSymbolEscape, 427263508Sdim InvalidatedSymbols *IS, 428263508Sdim RegionAndSymbolInvalidationTraits *HTraits, 429263508Sdim const CallEvent *Call) const; 430226586Sdim}; 431226586Sdim 432226586Sdim//===----------------------------------------------------------------------===// 433226586Sdim// ProgramStateManager - Factory object for ProgramStates. 434226586Sdim//===----------------------------------------------------------------------===// 435226586Sdim 436226586Sdimclass ProgramStateManager { 437226586Sdim friend class ProgramState; 438234353Sdim friend void ProgramStateRelease(const ProgramState *state); 439226586Sdimprivate: 440226586Sdim /// Eng - The SubEngine that owns this state manager. 441226586Sdim SubEngine *Eng; /* Can be null. */ 442226586Sdim 443226586Sdim EnvironmentManager EnvMgr; 444234353Sdim OwningPtr<StoreManager> StoreMgr; 445234353Sdim OwningPtr<ConstraintManager> ConstraintMgr; 446226586Sdim 447226586Sdim ProgramState::GenericDataMap::Factory GDMFactory; 448226586Sdim 449226586Sdim typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy; 450226586Sdim GDMContextsTy GDMContexts; 451226586Sdim 452226586Sdim /// StateSet - FoldingSet containing all the states created for analyzing 453226586Sdim /// a particular function. This is used to unique states. 454226586Sdim llvm::FoldingSet<ProgramState> StateSet; 455226586Sdim 456226586Sdim /// Object that manages the data for all created SVals. 457234353Sdim OwningPtr<SValBuilder> svalBuilder; 458226586Sdim 459239462Sdim /// Manages memory for created CallEvents. 460239462Sdim OwningPtr<CallEventManager> CallEventMgr; 461239462Sdim 462226586Sdim /// A BumpPtrAllocator to allocate states. 463226586Sdim llvm::BumpPtrAllocator &Alloc; 464226586Sdim 465226586Sdim /// A vector of ProgramStates that we can reuse. 466226586Sdim std::vector<ProgramState *> freeStates; 467226586Sdim 468226586Sdimpublic: 469226586Sdim ProgramStateManager(ASTContext &Ctx, 470226586Sdim StoreManagerCreator CreateStoreManager, 471226586Sdim ConstraintManagerCreator CreateConstraintManager, 472226586Sdim llvm::BumpPtrAllocator& alloc, 473243830Sdim SubEngine *subeng); 474226586Sdim 475226586Sdim ~ProgramStateManager(); 476226586Sdim 477234353Sdim ProgramStateRef getInitialState(const LocationContext *InitLoc); 478226586Sdim 479226586Sdim ASTContext &getContext() { return svalBuilder->getContext(); } 480226586Sdim const ASTContext &getContext() const { return svalBuilder->getContext(); } 481226586Sdim 482226586Sdim BasicValueFactory &getBasicVals() { 483226586Sdim return svalBuilder->getBasicValueFactory(); 484226586Sdim } 485226586Sdim 486226586Sdim SValBuilder &getSValBuilder() { 487226586Sdim return *svalBuilder; 488226586Sdim } 489226586Sdim 490226586Sdim SymbolManager &getSymbolManager() { 491226586Sdim return svalBuilder->getSymbolManager(); 492226586Sdim } 493226586Sdim const SymbolManager &getSymbolManager() const { 494226586Sdim return svalBuilder->getSymbolManager(); 495226586Sdim } 496226586Sdim 497226586Sdim llvm::BumpPtrAllocator& getAllocator() { return Alloc; } 498226586Sdim 499226586Sdim MemRegionManager& getRegionManager() { 500226586Sdim return svalBuilder->getRegionManager(); 501226586Sdim } 502226586Sdim const MemRegionManager& getRegionManager() const { 503226586Sdim return svalBuilder->getRegionManager(); 504226586Sdim } 505226586Sdim 506239462Sdim CallEventManager &getCallEventManager() { return *CallEventMgr; } 507239462Sdim 508226586Sdim StoreManager& getStoreManager() { return *StoreMgr; } 509226586Sdim ConstraintManager& getConstraintManager() { return *ConstraintMgr; } 510226586Sdim SubEngine* getOwningEngine() { return Eng; } 511226586Sdim 512234353Sdim ProgramStateRef removeDeadBindings(ProgramStateRef St, 513226586Sdim const StackFrameContext *LCtx, 514226586Sdim SymbolReaper& SymReaper); 515226586Sdim 516226586Sdimpublic: 517226586Sdim 518263508Sdim SVal ArrayToPointer(Loc Array, QualType ElementTy) { 519263508Sdim return StoreMgr->ArrayToPointer(Array, ElementTy); 520226586Sdim } 521226586Sdim 522226586Sdim // Methods that manipulate the GDM. 523234353Sdim ProgramStateRef addGDM(ProgramStateRef St, void *Key, void *Data); 524234353Sdim ProgramStateRef removeGDM(ProgramStateRef state, void *Key); 525226586Sdim 526226586Sdim // Methods that query & manipulate the Store. 527226586Sdim 528234353Sdim void iterBindings(ProgramStateRef state, StoreManager::BindingsHandler& F) { 529226586Sdim StoreMgr->iterBindings(state->getStore(), F); 530226586Sdim } 531226586Sdim 532234353Sdim ProgramStateRef getPersistentState(ProgramState &Impl); 533234353Sdim ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, 534234353Sdim ProgramStateRef GDMState); 535226586Sdim 536234353Sdim bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) { 537226586Sdim return S1->Env == S2->Env; 538226586Sdim } 539226586Sdim 540234353Sdim bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) { 541226586Sdim return S1->store == S2->store; 542226586Sdim } 543226586Sdim 544226586Sdim //==---------------------------------------------------------------------==// 545226586Sdim // Generic Data Map methods. 546226586Sdim //==---------------------------------------------------------------------==// 547226586Sdim // 548226586Sdim // ProgramStateManager and ProgramState support a "generic data map" that allows 549226586Sdim // different clients of ProgramState objects to embed arbitrary data within a 550226586Sdim // ProgramState object. The generic data map is essentially an immutable map 551226586Sdim // from a "tag" (that acts as the "key" for a client) and opaque values. 552226586Sdim // Tags/keys and values are simply void* values. The typical way that clients 553226586Sdim // generate unique tags are by taking the address of a static variable. 554226586Sdim // Clients are responsible for ensuring that data values referred to by a 555226586Sdim // the data pointer are immutable (and thus are essentially purely functional 556226586Sdim // data). 557226586Sdim // 558226586Sdim // The templated methods below use the ProgramStateTrait<T> class 559226586Sdim // to resolve keys into the GDM and to return data values to clients. 560226586Sdim // 561226586Sdim 562226586Sdim // Trait based GDM dispatch. 563226586Sdim template <typename T> 564234353Sdim ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait<T>::data_type D) { 565226586Sdim return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 566226586Sdim ProgramStateTrait<T>::MakeVoidPtr(D)); 567226586Sdim } 568226586Sdim 569226586Sdim template<typename T> 570234353Sdim ProgramStateRef set(ProgramStateRef st, 571226586Sdim typename ProgramStateTrait<T>::key_type K, 572226586Sdim typename ProgramStateTrait<T>::value_type V, 573226586Sdim typename ProgramStateTrait<T>::context_type C) { 574226586Sdim 575226586Sdim return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 576226586Sdim ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Set(st->get<T>(), K, V, C))); 577226586Sdim } 578226586Sdim 579226586Sdim template <typename T> 580234353Sdim ProgramStateRef add(ProgramStateRef st, 581226586Sdim typename ProgramStateTrait<T>::key_type K, 582226586Sdim typename ProgramStateTrait<T>::context_type C) { 583226586Sdim return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 584226586Sdim ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Add(st->get<T>(), K, C))); 585226586Sdim } 586226586Sdim 587226586Sdim template <typename T> 588234353Sdim ProgramStateRef remove(ProgramStateRef st, 589226586Sdim typename ProgramStateTrait<T>::key_type K, 590226586Sdim typename ProgramStateTrait<T>::context_type C) { 591226586Sdim 592226586Sdim return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 593226586Sdim ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Remove(st->get<T>(), K, C))); 594226586Sdim } 595226586Sdim 596226586Sdim template <typename T> 597234353Sdim ProgramStateRef remove(ProgramStateRef st) { 598226586Sdim return removeGDM(st, ProgramStateTrait<T>::GDMIndex()); 599226586Sdim } 600226586Sdim 601226586Sdim void *FindGDMContext(void *index, 602226586Sdim void *(*CreateContext)(llvm::BumpPtrAllocator&), 603226586Sdim void (*DeleteContext)(void*)); 604226586Sdim 605226586Sdim template <typename T> 606226586Sdim typename ProgramStateTrait<T>::context_type get_context() { 607226586Sdim void *p = FindGDMContext(ProgramStateTrait<T>::GDMIndex(), 608226586Sdim ProgramStateTrait<T>::CreateContext, 609226586Sdim ProgramStateTrait<T>::DeleteContext); 610226586Sdim 611226586Sdim return ProgramStateTrait<T>::MakeContext(p); 612226586Sdim } 613226586Sdim 614234353Sdim void EndPath(ProgramStateRef St) { 615226586Sdim ConstraintMgr->EndPath(St); 616226586Sdim } 617226586Sdim}; 618226586Sdim 619226586Sdim 620226586Sdim//===----------------------------------------------------------------------===// 621226586Sdim// Out-of-line method definitions for ProgramState. 622226586Sdim//===----------------------------------------------------------------------===// 623226586Sdim 624243830Sdiminline ConstraintManager &ProgramState::getConstraintManager() const { 625243830Sdim return stateMgr->getConstraintManager(); 626243830Sdim} 627243830Sdim 628226586Sdiminline const VarRegion* ProgramState::getRegion(const VarDecl *D, 629234353Sdim const LocationContext *LC) const 630234353Sdim{ 631226586Sdim return getStateManager().getRegionManager().getVarRegion(D, LC); 632226586Sdim} 633226586Sdim 634234353Sdiminline ProgramStateRef ProgramState::assume(DefinedOrUnknownSVal Cond, 635226586Sdim bool Assumption) const { 636226586Sdim if (Cond.isUnknown()) 637226586Sdim return this; 638249423Sdim 639249423Sdim return getStateManager().ConstraintMgr 640249423Sdim ->assume(this, Cond.castAs<DefinedSVal>(), Assumption); 641226586Sdim} 642226586Sdim 643234353Sdiminline std::pair<ProgramStateRef , ProgramStateRef > 644226586SdimProgramState::assume(DefinedOrUnknownSVal Cond) const { 645226586Sdim if (Cond.isUnknown()) 646226586Sdim return std::make_pair(this, this); 647249423Sdim 648249423Sdim return getStateManager().ConstraintMgr 649249423Sdim ->assumeDual(this, Cond.castAs<DefinedSVal>()); 650226586Sdim} 651226586Sdim 652234353Sdiminline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V) const { 653249423Sdim if (Optional<Loc> L = LV.getAs<Loc>()) 654249423Sdim return bindLoc(*L, V); 655249423Sdim return this; 656226586Sdim} 657226586Sdim 658226586Sdiminline Loc ProgramState::getLValue(const VarDecl *VD, 659226586Sdim const LocationContext *LC) const { 660226586Sdim return getStateManager().StoreMgr->getLValueVar(VD, LC); 661226586Sdim} 662226586Sdim 663226586Sdiminline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal, 664226586Sdim const LocationContext *LC) const { 665226586Sdim return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); 666226586Sdim} 667226586Sdim 668226586Sdiminline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const { 669226586Sdim return getStateManager().StoreMgr->getLValueIvar(D, Base); 670226586Sdim} 671226586Sdim 672226586Sdiminline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const { 673226586Sdim return getStateManager().StoreMgr->getLValueField(D, Base); 674226586Sdim} 675226586Sdim 676239462Sdiminline SVal ProgramState::getLValue(const IndirectFieldDecl *D, 677239462Sdim SVal Base) const { 678239462Sdim StoreManager &SM = *getStateManager().StoreMgr; 679239462Sdim for (IndirectFieldDecl::chain_iterator I = D->chain_begin(), 680239462Sdim E = D->chain_end(); 681239462Sdim I != E; ++I) { 682239462Sdim Base = SM.getLValueField(cast<FieldDecl>(*I), Base); 683239462Sdim } 684239462Sdim 685239462Sdim return Base; 686239462Sdim} 687239462Sdim 688226586Sdiminline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ 689249423Sdim if (Optional<NonLoc> N = Idx.getAs<NonLoc>()) 690226586Sdim return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base); 691226586Sdim return UnknownVal(); 692226586Sdim} 693226586Sdim 694243830Sdiminline SVal ProgramState::getSVal(const Stmt *Ex, 695243830Sdim const LocationContext *LCtx) const{ 696234353Sdim return Env.getSVal(EnvironmentEntry(Ex, LCtx), 697243830Sdim *getStateManager().svalBuilder); 698226586Sdim} 699226586Sdim 700234353Sdiminline SVal 701234353SdimProgramState::getSValAsScalarOrLoc(const Stmt *S, 702234353Sdim const LocationContext *LCtx) const { 703226586Sdim if (const Expr *Ex = dyn_cast<Expr>(S)) { 704226586Sdim QualType T = Ex->getType(); 705251662Sdim if (Ex->isGLValue() || Loc::isLocType(T) || 706251662Sdim T->isIntegralOrEnumerationType()) 707234353Sdim return getSVal(S, LCtx); 708226586Sdim } 709226586Sdim 710226586Sdim return UnknownVal(); 711226586Sdim} 712226586Sdim 713226586Sdiminline SVal ProgramState::getRawSVal(Loc LV, QualType T) const { 714234353Sdim return getStateManager().StoreMgr->getBinding(getStore(), LV, T); 715226586Sdim} 716226586Sdim 717226586Sdiminline SVal ProgramState::getSVal(const MemRegion* R) const { 718234353Sdim return getStateManager().StoreMgr->getBinding(getStore(), 719234353Sdim loc::MemRegionVal(R)); 720226586Sdim} 721226586Sdim 722226586Sdiminline BasicValueFactory &ProgramState::getBasicVals() const { 723226586Sdim return getStateManager().getBasicVals(); 724226586Sdim} 725226586Sdim 726226586Sdiminline SymbolManager &ProgramState::getSymbolManager() const { 727226586Sdim return getStateManager().getSymbolManager(); 728226586Sdim} 729226586Sdim 730226586Sdimtemplate<typename T> 731234353SdimProgramStateRef ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { 732226586Sdim return getStateManager().add<T>(this, K, get_context<T>()); 733226586Sdim} 734226586Sdim 735226586Sdimtemplate <typename T> 736226586Sdimtypename ProgramStateTrait<T>::context_type ProgramState::get_context() const { 737226586Sdim return getStateManager().get_context<T>(); 738226586Sdim} 739226586Sdim 740226586Sdimtemplate<typename T> 741234353SdimProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { 742226586Sdim return getStateManager().remove<T>(this, K, get_context<T>()); 743226586Sdim} 744226586Sdim 745226586Sdimtemplate<typename T> 746234353SdimProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K, 747226586Sdim typename ProgramStateTrait<T>::context_type C) const { 748226586Sdim return getStateManager().remove<T>(this, K, C); 749226586Sdim} 750226586Sdim 751226586Sdimtemplate <typename T> 752234353SdimProgramStateRef ProgramState::remove() const { 753226586Sdim return getStateManager().remove<T>(this); 754226586Sdim} 755226586Sdim 756226586Sdimtemplate<typename T> 757234353SdimProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { 758226586Sdim return getStateManager().set<T>(this, D); 759226586Sdim} 760226586Sdim 761226586Sdimtemplate<typename T> 762234353SdimProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, 763226586Sdim typename ProgramStateTrait<T>::value_type E) const { 764226586Sdim return getStateManager().set<T>(this, K, E, get_context<T>()); 765226586Sdim} 766226586Sdim 767226586Sdimtemplate<typename T> 768234353SdimProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K, 769226586Sdim typename ProgramStateTrait<T>::value_type E, 770226586Sdim typename ProgramStateTrait<T>::context_type C) const { 771226586Sdim return getStateManager().set<T>(this, K, E, C); 772226586Sdim} 773226586Sdim 774226586Sdimtemplate <typename CB> 775226586SdimCB ProgramState::scanReachableSymbols(SVal val) const { 776226586Sdim CB cb(this); 777226586Sdim scanReachableSymbols(val, cb); 778226586Sdim return cb; 779226586Sdim} 780226586Sdim 781226586Sdimtemplate <typename CB> 782226586SdimCB ProgramState::scanReachableSymbols(const SVal *beg, const SVal *end) const { 783226586Sdim CB cb(this); 784226586Sdim scanReachableSymbols(beg, end, cb); 785226586Sdim return cb; 786226586Sdim} 787226586Sdim 788226586Sdimtemplate <typename CB> 789226586SdimCB ProgramState::scanReachableSymbols(const MemRegion * const *beg, 790226586Sdim const MemRegion * const *end) const { 791226586Sdim CB cb(this); 792226586Sdim scanReachableSymbols(beg, end, cb); 793226586Sdim return cb; 794226586Sdim} 795226586Sdim 796226586Sdim/// \class ScanReachableSymbols 797226586Sdim/// A Utility class that allows to visit the reachable symbols using a custom 798226586Sdim/// SymbolVisitor. 799239462Sdimclass ScanReachableSymbols { 800263508Sdim typedef llvm::DenseSet<const void*> VisitedItems; 801226586Sdim 802226586Sdim VisitedItems visited; 803234353Sdim ProgramStateRef state; 804226586Sdim SymbolVisitor &visitor; 805226586Sdimpublic: 806226586Sdim 807234353Sdim ScanReachableSymbols(ProgramStateRef st, SymbolVisitor& v) 808226586Sdim : state(st), visitor(v) {} 809226586Sdim 810263508Sdim bool scan(nonloc::LazyCompoundVal val); 811226586Sdim bool scan(nonloc::CompoundVal val); 812226586Sdim bool scan(SVal val); 813226586Sdim bool scan(const MemRegion *R); 814226586Sdim bool scan(const SymExpr *sym); 815226586Sdim}; 816226586Sdim 817243830Sdim} // end ento namespace 818226586Sdim 819226586Sdim} // end clang namespace 820226586Sdim 821226586Sdim#endif 822