contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h

   1 //== ProgramState.h - Path-sensitive "State" for tracking 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 defines SymbolRef, ExprBindKey, and ProgramState*.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_GR_VALUESTATE_H
  15 #define LLVM_CLANG_GR_VALUESTATE_H
  16
  17 #include "clang/Basic/LLVM.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  22 #include "llvm/ADT/PointerIntPair.h"
  23 #include "llvm/ADT/FoldingSet.h"
  24 #include "llvm/ADT/ImmutableMap.h"
  25
  26 namespace llvm {
  27 class APSInt;
  28 class BumpPtrAllocator;
  29 }
  30
  31 namespace clang {
  32 class ASTContext;
  33
  34 namespace ento {
  35
  36 class ProgramStateManager;
  37
  38 typedef ConstraintManager* (*ConstraintManagerCreator)(ProgramStateManager&,
  39                                                        SubEngine&);
  40 typedef StoreManager* (*StoreManagerCreator)(ProgramStateManager&);
  41
  42 //===----------------------------------------------------------------------===//
  43 // ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState.
  44 //===----------------------------------------------------------------------===//
  45
  46 template <typename T> struct ProgramStatePartialTrait;
  47
  48 template <typename T> struct ProgramStateTrait {
  49   typedef typename T::data_type data_type;
  50   static inline void *GDMIndex() { return &T::TagInt; }
  51   static inline void *MakeVoidPtr(data_type D) { return (void*) D; }
  52   static inline data_type MakeData(void *const* P) {
  53     return P ? (data_type) *P : (data_type) 0;
  54   }
  55 };
  56
  57 class ProgramStateManager;
  58
  59 /// \class ProgramState
  60 /// ProgramState - This class encapsulates:
  61 ///
  62 ///    1. A mapping from expressions to values (Environment)
  63 ///    2. A mapping from locations to values (Store)
  64 ///    3. Constraints on symbolic values (GenericDataMap)
  65 ///
  66 ///  Together these represent the "abstract state" of a program.
  67 ///
  68 ///  ProgramState is intended to be used as a functional object; that is,
  69 ///  once it is created and made "persistent" in a FoldingSet, its
  70 ///  values will never change.
  71 class ProgramState : public llvm::FoldingSetNode {
  72 public:
  73   typedef llvm::ImmutableSet<llvm::APSInt*>                IntSetTy;
  74   typedef llvm::ImmutableMap<void*, void*>                 GenericDataMap;
  75
  76 private:
  77   void operator=(const ProgramState& R) const; // Do not implement.
  78
  79   friend class ProgramStateManager;
  80   friend class ExplodedGraph;
  81   friend class ExplodedNode;
  82
  83   ProgramStateManager *stateMgr;
  84   Environment Env;           // Maps a Stmt to its current SVal.
  85   Store store;               // Maps a location to its current value.
  86   GenericDataMap   GDM;      // Custom data stored by a client of this class.
  87   unsigned refCount;
  88
  89   /// makeWithStore - Return a ProgramState with the same values as the current
  90   ///  state with the exception of using the specified Store.
  91   const ProgramState *makeWithStore(const StoreRef &store) const;
  92
  93   void setStore(const StoreRef &storeRef);
  94
  95 public:
  96
  97   /// This ctor is used when creating the first ProgramState object.
  98   ProgramState(ProgramStateManager *mgr, const Environment& env,
  99           StoreRef st, GenericDataMap gdm);
 100
 101   /// Copy ctor - We must explicitly define this or else the "Next" ptr
 102   ///  in FoldingSetNode will also get copied.
 103   ProgramState(const ProgramState &RHS);
 104
 105   ~ProgramState();
 106
 107   /// Return the ProgramStateManager associated with this state.
 108   ProgramStateManager &getStateManager() const { return *stateMgr; }
 109
 110   /// Return true if this state is referenced by a persistent ExplodedNode.
 111   bool referencedByExplodedNode() const { return refCount > 0; }
 112
 113   /// getEnvironment - Return the environment associated with this state.
 114   ///  The environment is the mapping from expressions to values.
 115   const Environment& getEnvironment() const { return Env; }
 116
 117   /// Return the store associated with this state.  The store
 118   ///  is a mapping from locations to values.
 119   Store getStore() const { return store; }
 120
 121
 122   /// getGDM - Return the generic data map associated with this state.
 123   GenericDataMap getGDM() const { return GDM; }
 124
 125   void setGDM(GenericDataMap gdm) { GDM = gdm; }
 126
 127   /// Profile - Profile the contents of a ProgramState object for use in a
 128   ///  FoldingSet.  Two ProgramState objects are considered equal if they
 129   ///  have the same Environment, Store, and GenericDataMap.
 130   static void Profile(llvm::FoldingSetNodeID& ID, const ProgramState *V) {
 131     V->Env.Profile(ID);
 132     ID.AddPointer(V->store);
 133     V->GDM.Profile(ID);
 134   }
 135
 136   /// Profile - Used to profile the contents of this object for inclusion
 137   ///  in a FoldingSet.
 138   void Profile(llvm::FoldingSetNodeID& ID) const {
 139     Profile(ID, this);
 140   }
 141
 142   BasicValueFactory &getBasicVals() const;
 143   SymbolManager &getSymbolManager() const;
 144
 145   //==---------------------------------------------------------------------==//
 146   // Constraints on values.
 147   //==---------------------------------------------------------------------==//
 148   //
 149   // Each ProgramState records constraints on symbolic values.  These constraints
 150   // are managed using the ConstraintManager associated with a ProgramStateManager.
 151   // As constraints gradually accrue on symbolic values, added constraints
 152   // may conflict and indicate that a state is infeasible (as no real values
 153   // could satisfy all the constraints).  This is the principal mechanism
 154   // for modeling path-sensitivity in ExprEngine/ProgramState.
 155   //
 156   // Various "assume" methods form the interface for adding constraints to
 157   // symbolic values.  A call to 'assume' indicates an assumption being placed
 158   // on one or symbolic values.  'assume' methods take the following inputs:
 159   //
 160   //  (1) A ProgramState object representing the current state.
 161   //
 162   //  (2) The assumed constraint (which is specific to a given "assume" method).
 163   //
 164   //  (3) A binary value "Assumption" that indicates whether the constraint is
 165   //      assumed to be true or false.
 166   //
 167   // The output of "assume*" is a new ProgramState object with the added constraints.
 168   // If no new state is feasible, NULL is returned.
 169   //
 170
 171   const ProgramState *assume(DefinedOrUnknownSVal cond, bool assumption) const;
 172
 173   /// This method assumes both "true" and "false" for 'cond', and
 174   ///  returns both corresponding states.  It's shorthand for doing
 175   ///  'assume' twice.
 176   std::pair<const ProgramState*, const ProgramState*>
 177   assume(DefinedOrUnknownSVal cond) const;
 178
 179   const ProgramState *assumeInBound(DefinedOrUnknownSVal idx,
 180                                DefinedOrUnknownSVal upperBound,
 181                                bool assumption) const;
 182
 183   /// Utility method for getting regions.
 184   const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const;
 185
 186   //==---------------------------------------------------------------------==//
 187   // Binding and retrieving values to/from the environment and symbolic store.
 188   //==---------------------------------------------------------------------==//
 189
 190   /// BindCompoundLiteral - Return the state that has the bindings currently
 191   ///  in this state plus the bindings for the CompoundLiteral.
 192   const ProgramState *bindCompoundLiteral(const CompoundLiteralExpr *CL,
 193                                      const LocationContext *LC,
 194                                      SVal V) const;
 195
 196   /// Create a new state by binding the value 'V' to the statement 'S' in the
 197   /// state's environment.
 198   const ProgramState *BindExpr(const Stmt *S, SVal V, bool Invalidate = true) const;
 199
 200   /// Create a new state by binding the value 'V' and location 'locaton' to the
 201   /// statement 'S' in the state's environment.
 202   const ProgramState *bindExprAndLocation(const Stmt *S, SVal location, SVal V)
 203     const;
 204
 205   const ProgramState *bindDecl(const VarRegion *VR, SVal V) const;
 206
 207   const ProgramState *bindDeclWithNoInit(const VarRegion *VR) const;
 208
 209   const ProgramState *bindLoc(Loc location, SVal V) const;
 210
 211   const ProgramState *bindLoc(SVal location, SVal V) const;
 212
 213   const ProgramState *bindDefault(SVal loc, SVal V) const;
 214
 215   const ProgramState *unbindLoc(Loc LV) const;
 216
 217   /// invalidateRegions - Returns the state with bindings for the given regions
 218   ///  cleared from the store. The regions are provided as a continuous array
 219   ///  from Begin to End. Optionally invalidates global regions as well.
 220   const ProgramState *invalidateRegions(ArrayRef<const MemRegion *> Regions,
 221                                    const Expr *E, unsigned BlockCount,
 222                                    StoreManager::InvalidatedSymbols *IS = 0,
 223                                    bool invalidateGlobals = false) const;
 224
 225   /// enterStackFrame - Returns the state for entry to the given stack frame,
 226   ///  preserving the current state.
 227   const ProgramState *enterStackFrame(const StackFrameContext *frame) const;
 228
 229   /// Get the lvalue for a variable reference.
 230   Loc getLValue(const VarDecl *D, const LocationContext *LC) const;
 231
 232   /// Get the lvalue for a StringLiteral.
 233   Loc getLValue(const StringLiteral *literal) const;
 234
 235   Loc getLValue(const CompoundLiteralExpr *literal,
 236                 const LocationContext *LC) const;
 237
 238   /// Get the lvalue for an ivar reference.
 239   SVal getLValue(const ObjCIvarDecl *decl, SVal base) const;
 240
 241   /// Get the lvalue for a field reference.
 242   SVal getLValue(const FieldDecl *decl, SVal Base) const;
 243
 244   /// Get the lvalue for an array index.
 245   SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const;
 246
 247   const llvm::APSInt *getSymVal(SymbolRef sym) const;
 248
 249   /// Returns the SVal bound to the statement 'S' in the state's environment.
 250   SVal getSVal(const Stmt *S, bool useOnlyDirectBindings = false) const;
 251
 252   SVal getSValAsScalarOrLoc(const Stmt *Ex) const;
 253
 254   SVal getSVal(Loc LV, QualType T = QualType()) const;
 255
 256   /// Returns the "raw" SVal bound to LV before any value simplfication.
 257   SVal getRawSVal(Loc LV, QualType T= QualType()) const;
 258
 259   SVal getSVal(const MemRegion* R) const;
 260
 261   SVal getSValAsScalarOrLoc(const MemRegion *R) const;
 262
 263   /// \brief Visits the symbols reachable from the given SVal using the provided
 264   /// SymbolVisitor.
 265   ///
 266   /// This is a convenience API. Consider using ScanReachableSymbols class
 267   /// directly when making multiple scans on the same state with the same
 268   /// visitor to avoid repeated initialization cost.
 269   /// \sa ScanReachableSymbols
 270   bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const;
 271
 272   /// \brief Visits the symbols reachable from the SVals in the given range
 273   /// using the provided SymbolVisitor.
 274   bool scanReachableSymbols(const SVal *I, const SVal *E,
 275                             SymbolVisitor &visitor) const;
 276
 277   /// \brief Visits the symbols reachable from the regions in the given
 278   /// MemRegions range using the provided SymbolVisitor.
 279   bool scanReachableSymbols(const MemRegion * const *I,
 280                             const MemRegion * const *E,
 281                             SymbolVisitor &visitor) const;
 282
 283   template <typename CB> CB scanReachableSymbols(SVal val) const;
 284   template <typename CB> CB scanReachableSymbols(const SVal *beg,
 285                                                  const SVal *end) const;
 286
 287   template <typename CB> CB
 288   scanReachableSymbols(const MemRegion * const *beg,
 289                        const MemRegion * const *end) const;
 290
 291   //==---------------------------------------------------------------------==//
 292   // Accessing the Generic Data Map (GDM).
 293   //==---------------------------------------------------------------------==//
 294
 295   void *const* FindGDM(void *K) const;
 296
 297   template<typename T>
 298   const ProgramState *add(typename ProgramStateTrait<T>::key_type K) const;
 299
 300   template <typename T>
 301   typename ProgramStateTrait<T>::data_type
 302   get() const {
 303     return ProgramStateTrait<T>::MakeData(FindGDM(ProgramStateTrait<T>::GDMIndex()));
 304   }
 305
 306   template<typename T>
 307   typename ProgramStateTrait<T>::lookup_type
 308   get(typename ProgramStateTrait<T>::key_type key) const {
 309     void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex());
 310     return ProgramStateTrait<T>::Lookup(ProgramStateTrait<T>::MakeData(d), key);
 311   }
 312
 313   template <typename T>
 314   typename ProgramStateTrait<T>::context_type get_context() const;
 315
 316
 317   template<typename T>
 318   const ProgramState *remove(typename ProgramStateTrait<T>::key_type K) const;
 319
 320   template<typename T>
 321   const ProgramState *remove(typename ProgramStateTrait<T>::key_type K,
 322                         typename ProgramStateTrait<T>::context_type C) const;
 323   template <typename T>
 324   const ProgramState *remove() const;
 325
 326   template<typename T>
 327   const ProgramState *set(typename ProgramStateTrait<T>::data_type D) const;
 328
 329   template<typename T>
 330   const ProgramState *set(typename ProgramStateTrait<T>::key_type K,
 331                      typename ProgramStateTrait<T>::value_type E) const;
 332
 333   template<typename T>
 334   const ProgramState *set(typename ProgramStateTrait<T>::key_type K,
 335                      typename ProgramStateTrait<T>::value_type E,
 336                      typename ProgramStateTrait<T>::context_type C) const;
 337
 338   template<typename T>
 339   bool contains(typename ProgramStateTrait<T>::key_type key) const {
 340     void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex());
 341     return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key);
 342   }
 343
 344   // Pretty-printing.
 345   void print(raw_ostream &Out, CFG &C, const char *nl = "\n",
 346              const char *sep = "") const;
 347
 348   void printStdErr(CFG &C) const;
 349
 350   void printDOT(raw_ostream &Out, CFG &C) const;
 351
 352 private:
 353   /// Increments the number of times this state is referenced by ExplodeNodes.
 354   void incrementReferenceCount() { ++refCount; }
 355
 356   /// Decrement the number of times this state is referenced by ExplodeNodes.
 357   void decrementReferenceCount() {
 358     assert(refCount > 0);
 359     --refCount;
 360   }
 361
 362   const ProgramState *
 363   invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions,
 364                         const Expr *E, unsigned BlockCount,
 365                         StoreManager::InvalidatedSymbols &IS,
 366                         bool invalidateGlobals) const;
 367 };
 368
 369 class ProgramStateSet {
 370   typedef llvm::SmallPtrSet<const ProgramState*,5> ImplTy;
 371   ImplTy Impl;
 372 public:
 373   ProgramStateSet() {}
 374
 375   inline void Add(const ProgramState *St) {
 376     Impl.insert(St);
 377   }
 378
 379   typedef ImplTy::const_iterator iterator;
 380
 381   inline unsigned size() const { return Impl.size();  }
 382   inline bool empty()    const { return Impl.empty(); }
 383
 384   inline iterator begin() const { return Impl.begin(); }
 385   inline iterator end() const { return Impl.end();   }
 386
 387   class AutoPopulate {
 388     ProgramStateSet &S;
 389     unsigned StartSize;
 390     const ProgramState *St;
 391   public:
 392     AutoPopulate(ProgramStateSet &s, const ProgramState *st)
 393       : S(s), StartSize(S.size()), St(st) {}
 394
 395     ~AutoPopulate() {
 396       if (StartSize == S.size())
 397         S.Add(St);
 398     }
 399   };
 400 };
 401
 402 //===----------------------------------------------------------------------===//
 403 // ProgramStateManager - Factory object for ProgramStates.
 404 //===----------------------------------------------------------------------===//
 405
 406 class ProgramStateManager {
 407   friend class ProgramState;
 408 private:
 409   /// Eng - The SubEngine that owns this state manager.
 410   SubEngine *Eng; /* Can be null. */
 411
 412   EnvironmentManager                   EnvMgr;
 413   llvm::OwningPtr<StoreManager>        StoreMgr;
 414   llvm::OwningPtr<ConstraintManager>   ConstraintMgr;
 415
 416   ProgramState::GenericDataMap::Factory     GDMFactory;
 417
 418   typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy;
 419   GDMContextsTy GDMContexts;
 420
 421   /// StateSet - FoldingSet containing all the states created for analyzing
 422   ///  a particular function.  This is used to unique states.
 423   llvm::FoldingSet<ProgramState> StateSet;
 424
 425   /// Object that manages the data for all created SVals.
 426   llvm::OwningPtr<SValBuilder> svalBuilder;
 427
 428   /// A BumpPtrAllocator to allocate states.
 429   llvm::BumpPtrAllocator &Alloc;
 430
 431   /// A vector of recently allocated ProgramStates that can potentially be
 432   /// reused.
 433   std::vector<ProgramState *> recentlyAllocatedStates;
 434
 435   /// A vector of ProgramStates that we can reuse.
 436   std::vector<ProgramState *> freeStates;
 437
 438 public:
 439   ProgramStateManager(ASTContext &Ctx,
 440                  StoreManagerCreator CreateStoreManager,
 441                  ConstraintManagerCreator CreateConstraintManager,
 442                  llvm::BumpPtrAllocator& alloc,
 443                  SubEngine &subeng)
 444     : Eng(&subeng),
 445       EnvMgr(alloc),
 446       GDMFactory(alloc),
 447       svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)),
 448       Alloc(alloc) {
 449     StoreMgr.reset((*CreateStoreManager)(*this));
 450     ConstraintMgr.reset((*CreateConstraintManager)(*this, subeng));
 451   }
 452
 453   ProgramStateManager(ASTContext &Ctx,
 454                  StoreManagerCreator CreateStoreManager,
 455                  ConstraintManager* ConstraintManagerPtr,
 456                  llvm::BumpPtrAllocator& alloc)
 457     : Eng(0),
 458       EnvMgr(alloc),
 459       GDMFactory(alloc),
 460       svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)),
 461       Alloc(alloc) {
 462     StoreMgr.reset((*CreateStoreManager)(*this));
 463     ConstraintMgr.reset(ConstraintManagerPtr);
 464   }
 465
 466   ~ProgramStateManager();
 467
 468   const ProgramState *getInitialState(const LocationContext *InitLoc);
 469
 470   ASTContext &getContext() { return svalBuilder->getContext(); }
 471   const ASTContext &getContext() const { return svalBuilder->getContext(); }
 472
 473   BasicValueFactory &getBasicVals() {
 474     return svalBuilder->getBasicValueFactory();
 475   }
 476   const BasicValueFactory& getBasicVals() const {
 477     return svalBuilder->getBasicValueFactory();
 478   }
 479
 480   SValBuilder &getSValBuilder() {
 481     return *svalBuilder;
 482   }
 483
 484   SymbolManager &getSymbolManager() {
 485     return svalBuilder->getSymbolManager();
 486   }
 487   const SymbolManager &getSymbolManager() const {
 488     return svalBuilder->getSymbolManager();
 489   }
 490
 491   llvm::BumpPtrAllocator& getAllocator() { return Alloc; }
 492
 493   MemRegionManager& getRegionManager() {
 494     return svalBuilder->getRegionManager();
 495   }
 496   const MemRegionManager& getRegionManager() const {
 497     return svalBuilder->getRegionManager();
 498   }
 499
 500   StoreManager& getStoreManager() { return *StoreMgr; }
 501   ConstraintManager& getConstraintManager() { return *ConstraintMgr; }
 502   SubEngine* getOwningEngine() { return Eng; }
 503
 504   const ProgramState *removeDeadBindings(const ProgramState *St,
 505                                     const StackFrameContext *LCtx,
 506                                     SymbolReaper& SymReaper);
 507
 508   /// Marshal a new state for the callee in another translation unit.
 509   /// 'state' is owned by the caller's engine.
 510   const ProgramState *MarshalState(const ProgramState *state, const StackFrameContext *L);
 511
 512 public:
 513
 514   SVal ArrayToPointer(Loc Array) {
 515     return StoreMgr->ArrayToPointer(Array);
 516   }
 517
 518   // Methods that manipulate the GDM.
 519   const ProgramState *addGDM(const ProgramState *St, void *Key, void *Data);
 520   const ProgramState *removeGDM(const ProgramState *state, void *Key);
 521
 522   // Methods that query & manipulate the Store.
 523
 524   void iterBindings(const ProgramState *state, StoreManager::BindingsHandler& F) {
 525     StoreMgr->iterBindings(state->getStore(), F);
 526   }
 527
 528   const ProgramState *getPersistentState(ProgramState &Impl);
 529   const ProgramState *getPersistentStateWithGDM(const ProgramState *FromState,
 530                                            const ProgramState *GDMState);
 531
 532   bool haveEqualEnvironments(const ProgramState * S1, const ProgramState * S2) {
 533     return S1->Env == S2->Env;
 534   }
 535
 536   bool haveEqualStores(const ProgramState * S1, const ProgramState * S2) {
 537     return S1->store == S2->store;
 538   }
 539
 540   /// Periodically called by ExprEngine to recycle ProgramStates that were
 541   /// created but never used for creating an ExplodedNode.
 542   void recycleUnusedStates();
 543
 544   //==---------------------------------------------------------------------==//
 545   // Generic Data Map methods.
 546   //==---------------------------------------------------------------------==//
 547   //
 548   // ProgramStateManager and ProgramState support a "generic data map" that allows
 549   // different clients of ProgramState objects to embed arbitrary data within a
 550   // ProgramState object.  The generic data map is essentially an immutable map
 551   // from a "tag" (that acts as the "key" for a client) and opaque values.
 552   // Tags/keys and values are simply void* values.  The typical way that clients
 553   // generate unique tags are by taking the address of a static variable.
 554   // Clients are responsible for ensuring that data values referred to by a
 555   // the data pointer are immutable (and thus are essentially purely functional
 556   // data).
 557   //
 558   // The templated methods below use the ProgramStateTrait<T> class
 559   // to resolve keys into the GDM and to return data values to clients.
 560   //
 561
 562   // Trait based GDM dispatch.
 563   template <typename T>
 564   const ProgramState *set(const ProgramState *st, typename ProgramStateTrait<T>::data_type D) {
 565     return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
 566                   ProgramStateTrait<T>::MakeVoidPtr(D));
 567   }
 568
 569   template<typename T>
 570   const ProgramState *set(const ProgramState *st,
 571                      typename ProgramStateTrait<T>::key_type K,
 572                      typename ProgramStateTrait<T>::value_type V,
 573                      typename ProgramStateTrait<T>::context_type C) {
 574
 575     return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
 576      ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Set(st->get<T>(), K, V, C)));
 577   }
 578
 579   template <typename T>
 580   const ProgramState *add(const ProgramState *st,
 581                      typename ProgramStateTrait<T>::key_type K,
 582                      typename ProgramStateTrait<T>::context_type C) {
 583     return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
 584         ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Add(st->get<T>(), K, C)));
 585   }
 586
 587   template <typename T>
 588   const ProgramState *remove(const ProgramState *st,
 589                         typename ProgramStateTrait<T>::key_type K,
 590                         typename ProgramStateTrait<T>::context_type C) {
 591
 592     return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
 593      ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Remove(st->get<T>(), K, C)));
 594   }
 595
 596   template <typename T>
 597   const ProgramState *remove(const ProgramState *st) {
 598     return removeGDM(st, ProgramStateTrait<T>::GDMIndex());
 599   }
 600
 601   void *FindGDMContext(void *index,
 602                        void *(*CreateContext)(llvm::BumpPtrAllocator&),
 603                        void  (*DeleteContext)(void*));
 604
 605   template <typename T>
 606   typename ProgramStateTrait<T>::context_type get_context() {
 607     void *p = FindGDMContext(ProgramStateTrait<T>::GDMIndex(),
 608                              ProgramStateTrait<T>::CreateContext,
 609                              ProgramStateTrait<T>::DeleteContext);
 610
 611     return ProgramStateTrait<T>::MakeContext(p);
 612   }
 613
 614   const llvm::APSInt* getSymVal(const ProgramState *St, SymbolRef sym) {
 615     return ConstraintMgr->getSymVal(St, sym);
 616   }
 617
 618   void EndPath(const ProgramState *St) {
 619     ConstraintMgr->EndPath(St);
 620   }
 621 };
 622
 623
 624 //===----------------------------------------------------------------------===//
 625 // Out-of-line method definitions for ProgramState.
 626 //===----------------------------------------------------------------------===//
 627
 628 inline const VarRegion* ProgramState::getRegion(const VarDecl *D,
 629                                            const LocationContext *LC) const {
 630   return getStateManager().getRegionManager().getVarRegion(D, LC);
 631 }
 632
 633 inline const ProgramState *ProgramState::assume(DefinedOrUnknownSVal Cond,
 634                                       bool Assumption) const {
 635   if (Cond.isUnknown())
 636     return this;
 637
 638   return getStateManager().ConstraintMgr->assume(this, cast<DefinedSVal>(Cond),
 639                                                  Assumption);
 640 }
 641
 642 inline std::pair<const ProgramState*, const ProgramState*>
 643 ProgramState::assume(DefinedOrUnknownSVal Cond) const {
 644   if (Cond.isUnknown())
 645     return std::make_pair(this, this);
 646
 647   return getStateManager().ConstraintMgr->assumeDual(this,
 648                                                      cast<DefinedSVal>(Cond));
 649 }
 650
 651 inline const ProgramState *ProgramState::bindLoc(SVal LV, SVal V) const {
 652   return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V);
 653 }
 654
 655 inline Loc ProgramState::getLValue(const VarDecl *VD,
 656                                const LocationContext *LC) const {
 657   return getStateManager().StoreMgr->getLValueVar(VD, LC);
 658 }
 659
 660 inline Loc ProgramState::getLValue(const StringLiteral *literal) const {
 661   return getStateManager().StoreMgr->getLValueString(literal);
 662 }
 663
 664 inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal,
 665                                const LocationContext *LC) const {
 666   return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC);
 667 }
 668
 669 inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const {
 670   return getStateManager().StoreMgr->getLValueIvar(D, Base);
 671 }
 672
 673 inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const {
 674   return getStateManager().StoreMgr->getLValueField(D, Base);
 675 }
 676
 677 inline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{
 678   if (NonLoc *N = dyn_cast<NonLoc>(&Idx))
 679     return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base);
 680   return UnknownVal();
 681 }
 682
 683 inline const llvm::APSInt *ProgramState::getSymVal(SymbolRef sym) const {
 684   return getStateManager().getSymVal(this, sym);
 685 }
 686
 687 inline SVal ProgramState::getSVal(const Stmt *Ex, bool useOnlyDirectBindings) const{
 688   return Env.getSVal(Ex, *getStateManager().svalBuilder,
 689                      useOnlyDirectBindings);
 690 }
 691
 692 inline SVal ProgramState::getSValAsScalarOrLoc(const Stmt *S) const {
 693   if (const Expr *Ex = dyn_cast<Expr>(S)) {
 694     QualType T = Ex->getType();
 695     if (Ex->isLValue() || Loc::isLocType(T) || T->isIntegerType())
 696       return getSVal(S);
 697   }
 698
 699   return UnknownVal();
 700 }
 701
 702 inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const {
 703   return getStateManager().StoreMgr->Retrieve(getStore(), LV, T);
 704 }
 705
 706 inline SVal ProgramState::getSVal(const MemRegion* R) const {
 707   return getStateManager().StoreMgr->Retrieve(getStore(), loc::MemRegionVal(R));
 708 }
 709
 710 inline BasicValueFactory &ProgramState::getBasicVals() const {
 711   return getStateManager().getBasicVals();
 712 }
 713
 714 inline SymbolManager &ProgramState::getSymbolManager() const {
 715   return getStateManager().getSymbolManager();
 716 }
 717
 718 template<typename T>
 719 const ProgramState *ProgramState::add(typename ProgramStateTrait<T>::key_type K) const {
 720   return getStateManager().add<T>(this, K, get_context<T>());
 721 }
 722
 723 template <typename T>
 724 typename ProgramStateTrait<T>::context_type ProgramState::get_context() const {
 725   return getStateManager().get_context<T>();
 726 }
 727
 728 template<typename T>
 729 const ProgramState *ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const {
 730   return getStateManager().remove<T>(this, K, get_context<T>());
 731 }
 732
 733 template<typename T>
 734 const ProgramState *ProgramState::remove(typename ProgramStateTrait<T>::key_type K,
 735                                typename ProgramStateTrait<T>::context_type C) const {
 736   return getStateManager().remove<T>(this, K, C);
 737 }
 738
 739 template <typename T>
 740 const ProgramState *ProgramState::remove() const {
 741   return getStateManager().remove<T>(this);
 742 }
 743
 744 template<typename T>
 745 const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::data_type D) const {
 746   return getStateManager().set<T>(this, D);
 747 }
 748
 749 template<typename T>
 750 const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::key_type K,
 751                             typename ProgramStateTrait<T>::value_type E) const {
 752   return getStateManager().set<T>(this, K, E, get_context<T>());
 753 }
 754
 755 template<typename T>
 756 const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::key_type K,
 757                             typename ProgramStateTrait<T>::value_type E,
 758                             typename ProgramStateTrait<T>::context_type C) const {
 759   return getStateManager().set<T>(this, K, E, C);
 760 }
 761
 762 template <typename CB>
 763 CB ProgramState::scanReachableSymbols(SVal val) const {
 764   CB cb(this);
 765   scanReachableSymbols(val, cb);
 766   return cb;
 767 }
 768
 769 template <typename CB>
 770 CB ProgramState::scanReachableSymbols(const SVal *beg, const SVal *end) const {
 771   CB cb(this);
 772   scanReachableSymbols(beg, end, cb);
 773   return cb;
 774 }
 775
 776 template <typename CB>
 777 CB ProgramState::scanReachableSymbols(const MemRegion * const *beg,
 778                                  const MemRegion * const *end) const {
 779   CB cb(this);
 780   scanReachableSymbols(beg, end, cb);
 781   return cb;
 782 }
 783
 784 /// \class ScanReachableSymbols
 785 /// A Utility class that allows to visit the reachable symbols using a custom
 786 /// SymbolVisitor.
 787 class ScanReachableSymbols : public SubRegionMap::Visitor  {
 788   typedef llvm::DenseMap<const void*, unsigned> VisitedItems;
 789
 790   VisitedItems visited;
 791   const ProgramState *state;
 792   SymbolVisitor &visitor;
 793   llvm::OwningPtr<SubRegionMap> SRM;
 794 public:
 795
 796   ScanReachableSymbols(const ProgramState *st, SymbolVisitor& v)
 797     : state(st), visitor(v) {}
 798
 799   bool scan(nonloc::CompoundVal val);
 800   bool scan(SVal val);
 801   bool scan(const MemRegion *R);
 802   bool scan(const SymExpr *sym);
 803
 804   // From SubRegionMap::Visitor.
 805   bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) {
 806     return scan(SubRegion);
 807   }
 808 };
 809
 810 } // end GR namespace
 811
 812 } // end clang namespace
 813
 814 #endif