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