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