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