clang  9.0.0svn
ProgramState.h
Go to the documentation of this file.
1 //== ProgramState.h - Path-sensitive "State" for tracking values -*- C++ -*--=//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the state of the program along the analysisa path.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H
14 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H
15 
16 #include "clang/Basic/LLVM.h"
24 #include "llvm/ADT/FoldingSet.h"
25 #include "llvm/ADT/ImmutableMap.h"
26 #include "llvm/Support/Allocator.h"
27 #include <utility>
28 
29 namespace llvm {
30 class APSInt;
31 }
32 
33 namespace clang {
34 class ASTContext;
35 
36 namespace ento {
37 
38 class AnalysisManager;
39 class CallEvent;
40 class CallEventManager;
41 
42 typedef std::unique_ptr<ConstraintManager>(*ConstraintManagerCreator)(
44 typedef std::unique_ptr<StoreManager>(*StoreManagerCreator)(
45  ProgramStateManager &);
46 typedef llvm::ImmutableMap<const SubRegion*, TaintTagType> TaintedSubRegions;
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:
76  typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy;
77  typedef llvm::ImmutableMap<void*, void*> GenericDataMap;
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  int64_t getID() const;
110 
111  /// Return the ProgramStateManager associated with this state.
112  ProgramStateManager &getStateManager() const {
113  return *stateMgr;
114  }
115 
116  AnalysisManager &getAnalysisManager() const;
117 
118  /// Return the ConstraintManager.
119  ConstraintManager &getConstraintManager() const;
120 
121  /// getEnvironment - Return the environment associated with this state.
122  /// The environment is the mapping from expressions to values.
123  const Environment& getEnvironment() const { return Env; }
124 
125  /// Return the store associated with this state. The store
126  /// is a mapping from locations to values.
127  Store getStore() const { return store; }
128 
129 
130  /// getGDM - Return the generic data map associated with this state.
131  GenericDataMap getGDM() const { return GDM; }
132 
133  void setGDM(GenericDataMap gdm) { GDM = gdm; }
134 
135  /// Profile - Profile the contents of a ProgramState object for use in a
136  /// FoldingSet. Two ProgramState objects are considered equal if they
137  /// have the same Environment, Store, and GenericDataMap.
138  static void Profile(llvm::FoldingSetNodeID& ID, const ProgramState *V) {
139  V->Env.Profile(ID);
140  ID.AddPointer(V->store);
141  V->GDM.Profile(ID);
142  }
143 
144  /// Profile - Used to profile the contents of this object for inclusion
145  /// in a FoldingSet.
146  void Profile(llvm::FoldingSetNodeID& ID) const {
147  Profile(ID, this);
148  }
149 
150  BasicValueFactory &getBasicVals() const;
151  SymbolManager &getSymbolManager() const;
152 
153  //==---------------------------------------------------------------------==//
154  // Constraints on values.
155  //==---------------------------------------------------------------------==//
156  //
157  // Each ProgramState records constraints on symbolic values. These constraints
158  // are managed using the ConstraintManager associated with a ProgramStateManager.
159  // As constraints gradually accrue on symbolic values, added constraints
160  // may conflict and indicate that a state is infeasible (as no real values
161  // could satisfy all the constraints). This is the principal mechanism
162  // for modeling path-sensitivity in ExprEngine/ProgramState.
163  //
164  // Various "assume" methods form the interface for adding constraints to
165  // symbolic values. A call to 'assume' indicates an assumption being placed
166  // on one or symbolic values. 'assume' methods take the following inputs:
167  //
168  // (1) A ProgramState object representing the current state.
169  //
170  // (2) The assumed constraint (which is specific to a given "assume" method).
171  //
172  // (3) A binary value "Assumption" that indicates whether the constraint is
173  // assumed to be true or false.
174  //
175  // The output of "assume*" is a new ProgramState object with the added constraints.
176  // If no new state is feasible, NULL is returned.
177  //
178 
179  /// Assumes that the value of \p cond is zero (if \p assumption is "false")
180  /// or non-zero (if \p assumption is "true").
181  ///
182  /// This returns a new state with the added constraint on \p cond.
183  /// If no new state is feasible, NULL is returned.
184  LLVM_NODISCARD ProgramStateRef assume(DefinedOrUnknownSVal cond,
185  bool assumption) const;
186 
187  /// Assumes both "true" and "false" for \p cond, and returns both
188  /// corresponding states (respectively).
189  ///
190  /// This is more efficient than calling assume() twice. Note that one (but not
191  /// both) of the returned states may be NULL.
192  LLVM_NODISCARD std::pair<ProgramStateRef, ProgramStateRef>
193  assume(DefinedOrUnknownSVal cond) const;
194 
195  LLVM_NODISCARD ProgramStateRef
196  assumeInBound(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound,
197  bool assumption, QualType IndexType = QualType()) const;
198 
199  /// Assumes that the value of \p Val is bounded with [\p From; \p To]
200  /// (if \p assumption is "true") or it is fully out of this range
201  /// (if \p assumption is "false").
202  ///
203  /// This returns a new state with the added constraint on \p cond.
204  /// If no new state is feasible, NULL is returned.
205  LLVM_NODISCARD ProgramStateRef assumeInclusiveRange(DefinedOrUnknownSVal Val,
206  const llvm::APSInt &From,
207  const llvm::APSInt &To,
208  bool assumption) const;
209 
210  /// Assumes given range both "true" and "false" for \p Val, and returns both
211  /// corresponding states (respectively).
212  ///
213  /// This is more efficient than calling assume() twice. Note that one (but not
214  /// both) of the returned states may be NULL.
215  LLVM_NODISCARD std::pair<ProgramStateRef, ProgramStateRef>
216  assumeInclusiveRange(DefinedOrUnknownSVal Val, const llvm::APSInt &From,
217  const llvm::APSInt &To) const;
218 
219  /// Check if the given SVal is not constrained to zero and is not
220  /// a zero constant.
221  ConditionTruthVal isNonNull(SVal V) const;
222 
223  /// Check if the given SVal is constrained to zero or is a zero
224  /// constant.
225  ConditionTruthVal isNull(SVal V) const;
226 
227  /// \return Whether values \p Lhs and \p Rhs are equal.
228  ConditionTruthVal areEqual(SVal Lhs, SVal Rhs) const;
229 
230  /// Utility method for getting regions.
231  const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const;
232 
233  //==---------------------------------------------------------------------==//
234  // Binding and retrieving values to/from the environment and symbolic store.
235  //==---------------------------------------------------------------------==//
236 
237  /// Create a new state by binding the value 'V' to the statement 'S' in the
238  /// state's environment.
239  LLVM_NODISCARD ProgramStateRef BindExpr(const Stmt *S,
240  const LocationContext *LCtx, SVal V,
241  bool Invalidate = true) const;
242 
243  LLVM_NODISCARD ProgramStateRef bindLoc(Loc location, SVal V,
244  const LocationContext *LCtx,
245  bool notifyChanges = true) const;
246 
247  LLVM_NODISCARD ProgramStateRef bindLoc(SVal location, SVal V,
248  const LocationContext *LCtx) const;
249 
250  /// Initializes the region of memory represented by \p loc with an initial
251  /// value. Once initialized, all values loaded from any sub-regions of that
252  /// region will be equal to \p V, unless overwritten later by the program.
253  /// This method should not be used on regions that are already initialized.
254  /// If you need to indicate that memory contents have suddenly become unknown
255  /// within a certain region of memory, consider invalidateRegions().
256  LLVM_NODISCARD ProgramStateRef
257  bindDefaultInitial(SVal loc, SVal V, const LocationContext *LCtx) const;
258 
259  /// Performs C++ zero-initialization procedure on the region of memory
260  /// represented by \p loc.
261  LLVM_NODISCARD ProgramStateRef
262  bindDefaultZero(SVal loc, const LocationContext *LCtx) const;
263 
264  LLVM_NODISCARD ProgramStateRef killBinding(Loc LV) const;
265 
266  /// Returns the state with bindings for the given regions
267  /// cleared from the store.
268  ///
269  /// Optionally invalidates global regions as well.
270  ///
271  /// \param Regions the set of regions to be invalidated.
272  /// \param E the expression that caused the invalidation.
273  /// \param BlockCount The number of times the current basic block has been
274  // visited.
275  /// \param CausesPointerEscape the flag is set to true when
276  /// the invalidation entails escape of a symbol (representing a
277  /// pointer). For example, due to it being passed as an argument in a
278  /// call.
279  /// \param IS the set of invalidated symbols.
280  /// \param Call if non-null, the invalidated regions represent parameters to
281  /// the call and should be considered directly invalidated.
282  /// \param ITraits information about special handling for a particular
283  /// region/symbol.
284  LLVM_NODISCARD ProgramStateRef
285  invalidateRegions(ArrayRef<const MemRegion *> Regions, const Expr *E,
286  unsigned BlockCount, const LocationContext *LCtx,
287  bool CausesPointerEscape, InvalidatedSymbols *IS = nullptr,
288  const CallEvent *Call = nullptr,
289  RegionAndSymbolInvalidationTraits *ITraits = nullptr) const;
290 
291  LLVM_NODISCARD ProgramStateRef
292  invalidateRegions(ArrayRef<SVal> Regions, const Expr *E,
293  unsigned BlockCount, const LocationContext *LCtx,
294  bool CausesPointerEscape, InvalidatedSymbols *IS = nullptr,
295  const CallEvent *Call = nullptr,
296  RegionAndSymbolInvalidationTraits *ITraits = nullptr) const;
297 
298  /// enterStackFrame - Returns the state for entry to the given stack frame,
299  /// preserving the current state.
300  LLVM_NODISCARD ProgramStateRef enterStackFrame(
301  const CallEvent &Call, const StackFrameContext *CalleeCtx) const;
302 
303  /// Get the lvalue for a base class object reference.
304  Loc getLValue(const CXXBaseSpecifier &BaseSpec, const SubRegion *Super) const;
305 
306  /// Get the lvalue for a base class object reference.
307  Loc getLValue(const CXXRecordDecl *BaseClass, const SubRegion *Super,
308  bool IsVirtual) const;
309 
310  /// Get the lvalue for a variable reference.
311  Loc getLValue(const VarDecl *D, const LocationContext *LC) const;
312 
313  Loc getLValue(const CompoundLiteralExpr *literal,
314  const LocationContext *LC) const;
315 
316  /// Get the lvalue for an ivar reference.
317  SVal getLValue(const ObjCIvarDecl *decl, SVal base) const;
318 
319  /// Get the lvalue for a field reference.
320  SVal getLValue(const FieldDecl *decl, SVal Base) const;
321 
322  /// Get the lvalue for an indirect field reference.
323  SVal getLValue(const IndirectFieldDecl *decl, SVal Base) const;
324 
325  /// Get the lvalue for an array index.
326  SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const;
327 
328  /// Returns the SVal bound to the statement 'S' in the state's environment.
329  SVal getSVal(const Stmt *S, const LocationContext *LCtx) const;
330 
331  SVal getSValAsScalarOrLoc(const Stmt *Ex, const LocationContext *LCtx) const;
332 
333  /// Return the value bound to the specified location.
334  /// Returns UnknownVal() if none found.
335  SVal getSVal(Loc LV, QualType T = QualType()) const;
336 
337  /// Returns the "raw" SVal bound to LV before any value simplfication.
338  SVal getRawSVal(Loc LV, QualType T= QualType()) const;
339 
340  /// Return the value bound to the specified location.
341  /// Returns UnknownVal() if none found.
342  SVal getSVal(const MemRegion* R, QualType T = QualType()) const;
343 
344  /// Return the value bound to the specified location, assuming
345  /// that the value is a scalar integer or an enumeration or a pointer.
346  /// Returns UnknownVal() if none found or the region is not known to hold
347  /// a value of such type.
348  SVal getSValAsScalarOrLoc(const MemRegion *R) const;
349 
350  using region_iterator = const MemRegion **;
351 
352  /// Visits the symbols reachable from the given SVal using the provided
353  /// SymbolVisitor.
354  ///
355  /// This is a convenience API. Consider using ScanReachableSymbols class
356  /// directly when making multiple scans on the same state with the same
357  /// visitor to avoid repeated initialization cost.
358  /// \sa ScanReachableSymbols
359  bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const;
360 
361  /// Visits the symbols reachable from the regions in the given
362  /// MemRegions range using the provided SymbolVisitor.
363  bool scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable,
364  SymbolVisitor &visitor) const;
365 
366  template <typename CB> CB scanReachableSymbols(SVal val) const;
367  template <typename CB> CB
368  scanReachableSymbols(llvm::iterator_range<region_iterator> Reachable) const;
369 
370  /// Create a new state in which the statement is marked as tainted.
371  LLVM_NODISCARD ProgramStateRef
372  addTaint(const Stmt *S, const LocationContext *LCtx,
374 
375  /// Create a new state in which the value is marked as tainted.
376  LLVM_NODISCARD ProgramStateRef
377  addTaint(SVal V, TaintTagType Kind = TaintTagGeneric) const;
378 
379  /// Create a new state in which the symbol is marked as tainted.
380  LLVM_NODISCARD ProgramStateRef addTaint(SymbolRef S,
382 
383  /// Create a new state in which the region symbol is marked as tainted.
384  LLVM_NODISCARD ProgramStateRef
385  addTaint(const MemRegion *R, TaintTagType Kind = TaintTagGeneric) const;
386 
387  /// Create a new state in a which a sub-region of a given symbol is tainted.
388  /// This might be necessary when referring to regions that can not have an
389  /// individual symbol, e.g. if they are represented by the default binding of
390  /// a LazyCompoundVal.
391  LLVM_NODISCARD ProgramStateRef
392  addPartialTaint(SymbolRef ParentSym, const SubRegion *SubRegion,
394 
395  /// Check if the statement is tainted in the current state.
396  bool isTainted(const Stmt *S, const LocationContext *LCtx,
398  bool isTainted(SVal V, TaintTagType Kind = TaintTagGeneric) const;
399  bool isTainted(SymbolRef Sym, TaintTagType Kind = TaintTagGeneric) const;
400  bool isTainted(const MemRegion *Reg, TaintTagType Kind=TaintTagGeneric) const;
401 
402  //==---------------------------------------------------------------------==//
403  // Accessing the Generic Data Map (GDM).
404  //==---------------------------------------------------------------------==//
405 
406  void *const* FindGDM(void *K) const;
407 
408  template <typename T>
409  LLVM_NODISCARD ProgramStateRef
410  add(typename ProgramStateTrait<T>::key_type K) const;
411 
412  template <typename T>
414  get() const {
416  }
417 
418  template<typename T>
420  get(typename ProgramStateTrait<T>::key_type key) const {
421  void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex());
423  }
424 
425  template <typename T>
426  typename ProgramStateTrait<T>::context_type get_context() const;
427 
428  template <typename T>
429  LLVM_NODISCARD ProgramStateRef
430  remove(typename ProgramStateTrait<T>::key_type K) const;
431 
432  template <typename T>
433  LLVM_NODISCARD ProgramStateRef
434  remove(typename ProgramStateTrait<T>::key_type K,
435  typename ProgramStateTrait<T>::context_type C) const;
436 
437  template <typename T> LLVM_NODISCARD ProgramStateRef remove() const;
438 
439  template <typename T>
440  LLVM_NODISCARD ProgramStateRef
441  set(typename ProgramStateTrait<T>::data_type D) const;
442 
443  template <typename T>
444  LLVM_NODISCARD ProgramStateRef
445  set(typename ProgramStateTrait<T>::key_type K,
446  typename ProgramStateTrait<T>::value_type E) const;
447 
448  template <typename T>
449  LLVM_NODISCARD ProgramStateRef
450  set(typename ProgramStateTrait<T>::key_type K,
452  typename ProgramStateTrait<T>::context_type C) const;
453 
454  template<typename T>
455  bool contains(typename ProgramStateTrait<T>::key_type key) const {
456  void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex());
458  }
459 
460  // Pretty-printing.
461  void print(raw_ostream &Out, const char *nl = "\n", const char *sep = "",
462  const LocationContext *CurrentLC = nullptr) const;
463  void printDOT(raw_ostream &Out,
464  const LocationContext *CurrentLC = nullptr) const;
465  void printTaint(raw_ostream &Out, const char *nl = "\n") const;
466 
467  void dump() const;
468  void dumpTaint() const;
469 
470 private:
471  friend void ProgramStateRetain(const ProgramState *state);
472  friend void ProgramStateRelease(const ProgramState *state);
473 
474  /// \sa invalidateValues()
475  /// \sa invalidateRegions()
477  invalidateRegionsImpl(ArrayRef<SVal> Values,
478  const Expr *E, unsigned BlockCount,
479  const LocationContext *LCtx,
480  bool ResultsInSymbolEscape,
481  InvalidatedSymbols *IS,
483  const CallEvent *Call) const;
484 };
485 
486 //===----------------------------------------------------------------------===//
487 // ProgramStateManager - Factory object for ProgramStates.
488 //===----------------------------------------------------------------------===//
489 
490 class ProgramStateManager {
491  friend class ProgramState;
492  friend void ProgramStateRelease(const ProgramState *state);
493 private:
494  /// Eng - The SubEngine that owns this state manager.
495  SubEngine *Eng; /* Can be null. */
496 
497  EnvironmentManager EnvMgr;
498  std::unique_ptr<StoreManager> StoreMgr;
499  std::unique_ptr<ConstraintManager> ConstraintMgr;
500 
501  ProgramState::GenericDataMap::Factory GDMFactory;
502  TaintedSubRegions::Factory TSRFactory;
503 
504  typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy;
505  GDMContextsTy GDMContexts;
506 
507  /// StateSet - FoldingSet containing all the states created for analyzing
508  /// a particular function. This is used to unique states.
509  llvm::FoldingSet<ProgramState> StateSet;
510 
511  /// Object that manages the data for all created SVals.
512  std::unique_ptr<SValBuilder> svalBuilder;
513 
514  /// Manages memory for created CallEvents.
515  std::unique_ptr<CallEventManager> CallEventMgr;
516 
517  /// A BumpPtrAllocator to allocate states.
518  llvm::BumpPtrAllocator &Alloc;
519 
520  /// A vector of ProgramStates that we can reuse.
521  std::vector<ProgramState *> freeStates;
522 
523 public:
524  ProgramStateManager(ASTContext &Ctx,
525  StoreManagerCreator CreateStoreManager,
526  ConstraintManagerCreator CreateConstraintManager,
527  llvm::BumpPtrAllocator& alloc,
528  SubEngine *subeng);
529 
530  ~ProgramStateManager();
531 
532  ProgramStateRef getInitialState(const LocationContext *InitLoc);
533 
534  ASTContext &getContext() { return svalBuilder->getContext(); }
535  const ASTContext &getContext() const { return svalBuilder->getContext(); }
536 
538  return svalBuilder->getBasicValueFactory();
539  }
540 
542  return *svalBuilder;
543  }
544 
546  return svalBuilder->getSymbolManager();
547  }
549  return svalBuilder->getSymbolManager();
550  }
551 
552  llvm::BumpPtrAllocator& getAllocator() { return Alloc; }
553 
555  return svalBuilder->getRegionManager();
556  }
558  return svalBuilder->getRegionManager();
559  }
560 
561  CallEventManager &getCallEventManager() { return *CallEventMgr; }
562 
563  StoreManager &getStoreManager() { return *StoreMgr; }
564  ConstraintManager &getConstraintManager() { return *ConstraintMgr; }
565  SubEngine &getOwningEngine() { return *Eng; }
566 
567  ProgramStateRef removeDeadBindings(ProgramStateRef St,
568  const StackFrameContext *LCtx,
569  SymbolReaper& SymReaper);
570 
571 public:
572 
573  SVal ArrayToPointer(Loc Array, QualType ElementTy) {
574  return StoreMgr->ArrayToPointer(Array, ElementTy);
575  }
576 
577  // Methods that manipulate the GDM.
578  ProgramStateRef addGDM(ProgramStateRef St, void *Key, void *Data);
579  ProgramStateRef removeGDM(ProgramStateRef state, void *Key);
580 
581  // Methods that query & manipulate the Store.
582 
584  StoreMgr->iterBindings(state->getStore(), F);
585  }
586 
587  ProgramStateRef getPersistentState(ProgramState &Impl);
588  ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState,
589  ProgramStateRef GDMState);
590 
592  return ConstraintMgr->haveEqualConstraints(S1, S2);
593  }
594 
596  return S1->Env == S2->Env;
597  }
598 
600  return S1->store == S2->store;
601  }
602 
603  //==---------------------------------------------------------------------==//
604  // Generic Data Map methods.
605  //==---------------------------------------------------------------------==//
606  //
607  // ProgramStateManager and ProgramState support a "generic data map" that allows
608  // different clients of ProgramState objects to embed arbitrary data within a
609  // ProgramState object. The generic data map is essentially an immutable map
610  // from a "tag" (that acts as the "key" for a client) and opaque values.
611  // Tags/keys and values are simply void* values. The typical way that clients
612  // generate unique tags are by taking the address of a static variable.
613  // Clients are responsible for ensuring that data values referred to by a
614  // the data pointer are immutable (and thus are essentially purely functional
615  // data).
616  //
617  // The templated methods below use the ProgramStateTrait<T> class
618  // to resolve keys into the GDM and to return data values to clients.
619  //
620 
621  // Trait based GDM dispatch.
622  template <typename T>
624  return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
626  }
627 
628  template<typename T>
633 
634  return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
636  }
637 
638  template <typename T>
642  return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
644  }
645 
646  template <typename T>
650 
651  return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
653  }
654 
655  template <typename T>
657  return removeGDM(st, ProgramStateTrait<T>::GDMIndex());
658  }
659 
660  void *FindGDMContext(void *index,
661  void *(*CreateContext)(llvm::BumpPtrAllocator&),
662  void (*DeleteContext)(void*));
663 
664  template <typename T>
666  void *p = FindGDMContext(ProgramStateTrait<T>::GDMIndex(),
669 
671  }
672 
674  ConstraintMgr->EndPath(St);
675  }
676 };
677 
678 
679 //===----------------------------------------------------------------------===//
680 // Out-of-line method definitions for ProgramState.
681 //===----------------------------------------------------------------------===//
682 
683 inline ConstraintManager &ProgramState::getConstraintManager() const {
684  return stateMgr->getConstraintManager();
685 }
686 
687 inline const VarRegion* ProgramState::getRegion(const VarDecl *D,
688  const LocationContext *LC) const
689 {
690  return getStateManager().getRegionManager().getVarRegion(D, LC);
691 }
692 
693 inline ProgramStateRef ProgramState::assume(DefinedOrUnknownSVal Cond,
694  bool Assumption) const {
695  if (Cond.isUnknown())
696  return this;
697 
698  return getStateManager().ConstraintMgr
699  ->assume(this, Cond.castAs<DefinedSVal>(), Assumption);
700 }
701 
702 inline std::pair<ProgramStateRef , ProgramStateRef >
703 ProgramState::assume(DefinedOrUnknownSVal Cond) const {
704  if (Cond.isUnknown())
705  return std::make_pair(this, this);
706 
707  return getStateManager().ConstraintMgr
708  ->assumeDual(this, Cond.castAs<DefinedSVal>());
709 }
710 
711 inline ProgramStateRef ProgramState::assumeInclusiveRange(
712  DefinedOrUnknownSVal Val, const llvm::APSInt &From, const llvm::APSInt &To,
713  bool Assumption) const {
714  if (Val.isUnknown())
715  return this;
716 
717  assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!");
718 
719  return getStateManager().ConstraintMgr->assumeInclusiveRange(
720  this, Val.castAs<NonLoc>(), From, To, Assumption);
721 }
722 
723 inline std::pair<ProgramStateRef, ProgramStateRef>
724 ProgramState::assumeInclusiveRange(DefinedOrUnknownSVal Val,
725  const llvm::APSInt &From,
726  const llvm::APSInt &To) const {
727  if (Val.isUnknown())
728  return std::make_pair(this, this);
729 
730  assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!");
731 
732  return getStateManager().ConstraintMgr->assumeInclusiveRangeDual(
733  this, Val.castAs<NonLoc>(), From, To);
734 }
735 
736 inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V, const LocationContext *LCtx) const {
737  if (Optional<Loc> L = LV.getAs<Loc>())
738  return bindLoc(*L, V, LCtx);
739  return this;
740 }
741 
742 inline Loc ProgramState::getLValue(const CXXBaseSpecifier &BaseSpec,
743  const SubRegion *Super) const {
744  const auto *Base = BaseSpec.getType()->getAsCXXRecordDecl();
745  return loc::MemRegionVal(
746  getStateManager().getRegionManager().getCXXBaseObjectRegion(
747  Base, Super, BaseSpec.isVirtual()));
748 }
749 
750 inline Loc ProgramState::getLValue(const CXXRecordDecl *BaseClass,
751  const SubRegion *Super,
752  bool IsVirtual) const {
753  return loc::MemRegionVal(
754  getStateManager().getRegionManager().getCXXBaseObjectRegion(
755  BaseClass, Super, IsVirtual));
756 }
757 
758 inline Loc ProgramState::getLValue(const VarDecl *VD,
759  const LocationContext *LC) const {
760  return getStateManager().StoreMgr->getLValueVar(VD, LC);
761 }
762 
763 inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal,
764  const LocationContext *LC) const {
765  return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC);
766 }
767 
768 inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const {
769  return getStateManager().StoreMgr->getLValueIvar(D, Base);
770 }
771 
772 inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const {
773  return getStateManager().StoreMgr->getLValueField(D, Base);
774 }
775 
776 inline SVal ProgramState::getLValue(const IndirectFieldDecl *D,
777  SVal Base) const {
778  StoreManager &SM = *getStateManager().StoreMgr;
779  for (const auto *I : D->chain()) {
780  Base = SM.getLValueField(cast<FieldDecl>(I), Base);
781  }
782 
783  return Base;
784 }
785 
786 inline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{
787  if (Optional<NonLoc> N = Idx.getAs<NonLoc>())
788  return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base);
789  return UnknownVal();
790 }
791 
792 inline SVal ProgramState::getSVal(const Stmt *Ex,
793  const LocationContext *LCtx) const{
794  return Env.getSVal(EnvironmentEntry(Ex, LCtx),
795  *getStateManager().svalBuilder);
796 }
797 
798 inline SVal
799 ProgramState::getSValAsScalarOrLoc(const Stmt *S,
800  const LocationContext *LCtx) const {
801  if (const Expr *Ex = dyn_cast<Expr>(S)) {
802  QualType T = Ex->getType();
803  if (Ex->isGLValue() || Loc::isLocType(T) ||
805  return getSVal(S, LCtx);
806  }
807 
808  return UnknownVal();
809 }
810 
811 inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const {
812  return getStateManager().StoreMgr->getBinding(getStore(), LV, T);
813 }
814 
815 inline SVal ProgramState::getSVal(const MemRegion* R, QualType T) const {
816  return getStateManager().StoreMgr->getBinding(getStore(),
818  T);
819 }
820 
821 inline BasicValueFactory &ProgramState::getBasicVals() const {
822  return getStateManager().getBasicVals();
823 }
824 
825 inline SymbolManager &ProgramState::getSymbolManager() const {
826  return getStateManager().getSymbolManager();
827 }
828 
829 template<typename T>
830 ProgramStateRef ProgramState::add(typename ProgramStateTrait<T>::key_type K) const {
831  return getStateManager().add<T>(this, K, get_context<T>());
832 }
833 
834 template <typename T>
835 typename ProgramStateTrait<T>::context_type ProgramState::get_context() const {
836  return getStateManager().get_context<T>();
837 }
838 
839 template<typename T>
840 ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const {
841  return getStateManager().remove<T>(this, K, get_context<T>());
842 }
843 
844 template<typename T>
845 ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K,
846  typename ProgramStateTrait<T>::context_type C) const {
847  return getStateManager().remove<T>(this, K, C);
848 }
849 
850 template <typename T>
851 ProgramStateRef ProgramState::remove() const {
852  return getStateManager().remove<T>(this);
853 }
854 
855 template<typename T>
856 ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::data_type D) const {
857  return getStateManager().set<T>(this, D);
858 }
859 
860 template<typename T>
861 ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K,
862  typename ProgramStateTrait<T>::value_type E) const {
863  return getStateManager().set<T>(this, K, E, get_context<T>());
864 }
865 
866 template<typename T>
867 ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K,
869  typename ProgramStateTrait<T>::context_type C) const {
870  return getStateManager().set<T>(this, K, E, C);
871 }
872 
873 template <typename CB>
874 CB ProgramState::scanReachableSymbols(SVal val) const {
875  CB cb(this);
876  scanReachableSymbols(val, cb);
877  return cb;
878 }
879 
880 template <typename CB>
881 CB ProgramState::scanReachableSymbols(
882  llvm::iterator_range<region_iterator> Reachable) const {
883  CB cb(this);
884  scanReachableSymbols(Reachable, cb);
885  return cb;
886 }
887 
888 /// \class ScanReachableSymbols
889 /// A utility class that visits the reachable symbols using a custom
890 /// SymbolVisitor. Terminates recursive traversal when the visitor function
891 /// returns false.
894 
895  VisitedItems visited;
897  SymbolVisitor &visitor;
898 public:
900  : state(std::move(st)), visitor(v) {}
901 
902  bool scan(nonloc::LazyCompoundVal val);
903  bool scan(nonloc::CompoundVal val);
904  bool scan(SVal val);
905  bool scan(const MemRegion *R);
906  bool scan(const SymExpr *sym);
907 };
908 
909 } // end ento namespace
910 
911 } // end clang namespace
912 
913 #endif
const Environment & getEnvironment() const
getEnvironment - Return the environment associated with this state.
Definition: ProgramState.h:123
A (possibly-)qualified type.
Definition: Type.h:639
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:29
Stmt - This represents one statement.
Definition: Stmt.h:65
Information about invalidation for a particular region/symbol.
Definition: MemRegion.h:1439
BasicValueFactory & getBasicVals()
Definition: ProgramState.h:537
bool contains(typename ProgramStateTrait< T >::key_type key) const
Definition: ProgramState.h:455
Manages the lifetime of CallEvent objects.
Definition: CallEvent.h:1086
llvm::ImmutableSet< llvm::APSInt * > IntSetTy
Definition: ProgramState.h:76
bool isVirtual() const
Determines whether the base class is a virtual base class (or not).
Definition: DeclCXX.h:244
StringRef P
A utility class that visits the reachable symbols using a custom SymbolVisitor.
Definition: ProgramState.h:892
Represents a variable declaration or definition.
Definition: Decl.h:812
CompoundLiteralExpr - [C99 6.5.2.5].
Definition: Expr.h:2963
const void * Store
Store - This opaque type encapsulates an immutable mapping from locations to values.
Definition: StoreRef.h:27
Store getStore() const
Return the store associated with this state.
Definition: ProgramState.h:127
const SymbolManager & getSymbolManager() const
Definition: ProgramState.h:548
Symbolic value.
Definition: SymExpr.h:29
bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) const
Definition: ProgramState.h:595
ProgramStateRef add(ProgramStateRef st, typename ProgramStateTrait< T >::key_type K, typename ProgramStateTrait< T >::context_type C)
Definition: ProgramState.h:639
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
Represents a member of a struct/union/class.
Definition: Decl.h:2578
bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) const
Definition: ProgramState.h:599
Definition: Format.h:2118
std::unique_ptr< StoreManager >(* StoreManagerCreator)(ProgramStateManager &)
Definition: ProgramState.h:44
MemRegionManager & getRegionManager()
Definition: ProgramState.h:554
void EndPath(ProgramStateRef St)
Definition: ProgramState.h:673
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:6662
ProgramStateManager & getStateManager() const
Return the ProgramStateManager associated with this state.
Definition: ProgramState.h:112
GenericDataMap getGDM() const
getGDM - Return the generic data map associated with this state.
Definition: ProgramState.h:131
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:2846
bool isUnknown() const
Definition: SVals.h:136
virtual SVal getLValueField(const FieldDecl *D, SVal Base)
Definition: Store.h:145
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition: Type.cpp:1635
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:146
ProgramState - This class encapsulates:
Definition: ProgramState.h:74
This represents one expression.
Definition: Expr.h:108
const internal::VariadicAllOfMatcher< Decl > decl
Matches declarations.
do v
Definition: arm_acle.h:78
const SourceManager & SM
Definition: Format.cpp:1528
Optional< T > getAs() const
Convert to the specified SVal type, returning None if this SVal is not of the desired type...
Definition: SVals.h:111
llvm::DOTGraphTraits< ExplodedGraph * > DefaultDOTGraphTraits const ExplodedNode const ExplodedNode *Out<< "\l\|";Out<< "StateID: ST"<< State-> getID()<< "
llvm::BumpPtrAllocator & getAllocator()
Definition: ProgramState.h:552
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:80
CallEventManager & getCallEventManager()
Definition: ProgramState.h:561
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:75
ProgramStateTrait< T >::context_type get_context()
Definition: ProgramState.h:665
static const TaintTagType TaintTagGeneric
Definition: TaintTag.h:24
A class responsible for cleaning up unused symbols.
ScanReachableSymbols(ProgramStateRef st, SymbolVisitor &v)
Definition: ProgramState.h:899
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:545
An immutable map from EnvironemntEntries to SVals.
Definition: Environment.h:56
Dataflow Directional Tag Classes.
SVal ArrayToPointer(Loc Array, QualType ElementTy)
Definition: ProgramState.h:573
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:2824
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:170
ConstraintManager & getConstraintManager()
Definition: ProgramState.h:564
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
Definition: SVals.h:103
SubRegion - A region that subsets another larger region.
Definition: MemRegion.h:435
bool haveEqualConstraints(ProgramStateRef S1, ProgramStateRef S2) const
Definition: ProgramState.h:591
void ProgramStateRetain(const ProgramState *state)
Increments the number of times this state is referenced.
Represents a base class of a C++ class.
Definition: DeclCXX.h:191
Represents a C++ struct/union/class.
Definition: DeclCXX.h:299
const MemRegionManager & getRegionManager() const
Definition: ProgramState.h:557
ObjCIvarDecl - Represents an ObjC instance variable.
Definition: DeclObjC.h:1944
unsigned TaintTagType
The type of taint, which helps to differentiate between different types of taint. ...
Definition: TaintTag.h:22
const ASTContext & getContext() const
Definition: ProgramState.h:535
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:138
void iterBindings(ProgramStateRef state, StoreManager::BindingsHandler &F)
Definition: ProgramState.h:583
void setGDM(GenericDataMap gdm)
Definition: ProgramState.h:133
QualType getType() const
Retrieves the type of the base class.
Definition: DeclCXX.h:290