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