Clang Project

clang_source_code/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
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"
17#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
20#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/TaintTag.h"
24#include "llvm/ADT/FoldingSet.h"
25#include "llvm/ADT/ImmutableMap.h"
26#include "llvm/Support/Allocator.h"
27#include <utility>
28
29namespace llvm {
30class APSInt;
31}
32
33namespace clang {
34class ASTContext;
35
36namespace ento {
37
38class AnalysisManager;
39class CallEvent;
40class CallEventManager;
41
42typedef std::unique_ptr<ConstraintManager>(*ConstraintManagerCreator)(
43    ProgramStateManager &, SubEngine *);
44typedef std::unique_ptr<StoreManager>(*StoreManagerCreator)(
45    ProgramStateManager &);
46typedef llvm::ImmutableMap<const SubRegion*, TaintTagType> TaintedSubRegions;
47
48//===----------------------------------------------------------------------===//
49// ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState.
50//===----------------------------------------------------------------------===//
51
52template <typename T> struct ProgramStatePartialTrait;
53
54template <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.
74class ProgramState : public llvm::FoldingSetNode {
75public:
76  typedef llvm::ImmutableSet<llvm::APSInt*>                IntSetTy;
77  typedef llvm::ImmutableMap<void*, void*>                 GenericDataMap;
78
79private:
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
98public:
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,
373           TaintTagType Kind = TaintTagGeneric) const;
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,
381                               TaintTagType Kind = TaintTagGeneric) const;
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,
393                  TaintTagType Kind = TaintTagGeneric) const;
394
395  /// Check if the statement is tainted in the current state.
396  bool isTainted(const Stmt *S, const LocationContext *LCtx,
397                 TaintTagType Kind = TaintTagGeneric) const;
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>
413  typename ProgramStateTrait<T>::data_type
414  get() const {
415    return ProgramStateTrait<T>::MakeData(FindGDM(ProgramStateTrait<T>::GDMIndex()));
416  }
417
418  template<typename T>
419  typename ProgramStateTrait<T>::lookup_type
420  get(typename ProgramStateTrait<T>::key_type key) const {
421    void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex());
422    return ProgramStateTrait<T>::Lookup(ProgramStateTrait<T>::MakeData(d), key);
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,
451      typename ProgramStateTrait<T>::value_type E,
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());
457    return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key);
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
470private:
471  friend void ProgramStateRetain(const ProgramState *state);
472  friend void ProgramStateRelease(const ProgramState *state);
473
474  /// \sa invalidateValues()
475  /// \sa invalidateRegions()
476  ProgramStateRef
477  invalidateRegionsImpl(ArrayRef<SVal> Values,
478                        const Expr *E, unsigned BlockCount,
479                        const LocationContext *LCtx,
480                        bool ResultsInSymbolEscape,
481                        InvalidatedSymbols *IS,
482                        RegionAndSymbolInvalidationTraits *HTraits,
483                        const CallEvent *Call) const;
484};
485
486//===----------------------------------------------------------------------===//
487// ProgramStateManager - Factory object for ProgramStates.
488//===----------------------------------------------------------------------===//
489
490class ProgramStateManager {
491  friend class ProgramState;
492  friend void ProgramStateRelease(const ProgramState *state);
493private:
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
523public:
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
537  BasicValueFactory &getBasicVals() {
538    return svalBuilder->getBasicValueFactory();
539  }
540
541  SValBuilder &getSValBuilder() {
542    return *svalBuilder;
543  }
544
545  SymbolManager &getSymbolManager() {
546    return svalBuilder->getSymbolManager();
547  }
548  const SymbolManager &getSymbolManager() const {
549    return svalBuilder->getSymbolManager();
550  }
551
552  llvm::BumpPtrAllocator& getAllocator() { return Alloc; }
553
554  MemRegionManager& getRegionManager() {
555    return svalBuilder->getRegionManager();
556  }
557  const MemRegionManager &getRegionManager() const {
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
571public:
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
583  void iterBindings(ProgramStateRef state, StoreManager::BindingsHandler& F) {
584    StoreMgr->iterBindings(state->getStore(), F);
585  }
586
587  ProgramStateRef getPersistentState(ProgramState &Impl);
588  ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState,
589                                           ProgramStateRef GDMState);
590
591  bool haveEqualConstraints(ProgramStateRef S1, ProgramStateRef S2) const {
592    return ConstraintMgr->haveEqualConstraints(S1, S2);
593  }
594
595  bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) const {
596    return S1->Env == S2->Env;
597  }
598
599  bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) const {
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>
623  ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait<T>::data_type D) {
624    return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
625                  ProgramStateTrait<T>::MakeVoidPtr(D));
626  }
627
628  template<typename T>
629  ProgramStateRef set(ProgramStateRef st,
630                     typename ProgramStateTrait<T>::key_type K,
631                     typename ProgramStateTrait<T>::value_type V,
632                     typename ProgramStateTrait<T>::context_type C) {
633
634    return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
635     ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Set(st->get<T>(), K, V, C)));
636  }
637
638  template <typename T>
639  ProgramStateRef add(ProgramStateRef st,
640                     typename ProgramStateTrait<T>::key_type K,
641                     typename ProgramStateTrait<T>::context_type C) {
642    return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
643        ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Add(st->get<T>(), K, C)));
644  }
645
646  template <typename T>
647  ProgramStateRef remove(ProgramStateRef st,
648                        typename ProgramStateTrait<T>::key_type K,
649                        typename ProgramStateTrait<T>::context_type C) {
650
651    return addGDM(st, ProgramStateTrait<T>::GDMIndex(),
652     ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Remove(st->get<T>(), K, C)));
653  }
654
655  template <typename T>
656  ProgramStateRef remove(ProgramStateRef st) {
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>
665  typename ProgramStateTrait<T>::context_type get_context() {
666    void *p = FindGDMContext(ProgramStateTrait<T>::GDMIndex(),
667                             ProgramStateTrait<T>::CreateContext,
668                             ProgramStateTrait<T>::DeleteContext);
669
670    return ProgramStateTrait<T>::MakeContext(p);
671  }
672
673  void EndPath(ProgramStateRef St) {
674    ConstraintMgr->EndPath(St);
675  }
676};
677
678
679//===----------------------------------------------------------------------===//
680// Out-of-line method definitions for ProgramState.
681//===----------------------------------------------------------------------===//
682
683inline ConstraintManager &ProgramState::getConstraintManager() const {
684  return stateMgr->getConstraintManager();
685}
686
687inline const VarRegion* ProgramState::getRegion(const VarDecl *D,
688                                                const LocationContext *LC) const
689{
690  return getStateManager().getRegionManager().getVarRegion(D, LC);
691}
692
693inline 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
702inline std::pair<ProgramStateRef , ProgramStateRef >
703ProgramState::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
711inline 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   (0) . __assert_fail ("Val.getAs() && \"Only NonLocs are supported!\"", "/home/seafit/code_projects/clang_source/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h", 717, __PRETTY_FUNCTION__))" file_link="../../../../../../include/assert.h.html#88" macro="true">assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!");
718
719  return getStateManager().ConstraintMgr->assumeInclusiveRange(
720      this, Val.castAs<NonLoc>(), From, To, Assumption);
721}
722
723inline std::pair<ProgramStateRef, ProgramStateRef>
724ProgramState::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   (0) . __assert_fail ("Val.getAs() && \"Only NonLocs are supported!\"", "/home/seafit/code_projects/clang_source/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h", 730, __PRETTY_FUNCTION__))" file_link="../../../../../../include/assert.h.html#88" macro="true">assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!");
731
732  return getStateManager().ConstraintMgr->assumeInclusiveRangeDual(
733      this, Val.castAs<NonLoc>(), From, To);
734}
735
736inline 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
742inline 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
750inline 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
758inline Loc ProgramState::getLValue(const VarDecl *VD,
759                               const LocationContext *LC) const {
760  return getStateManager().StoreMgr->getLValueVar(VD, LC);
761}
762
763inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal,
764                               const LocationContext *LC) const {
765  return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC);
766}
767
768inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const {
769  return getStateManager().StoreMgr->getLValueIvar(D, Base);
770}
771
772inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const {
773  return getStateManager().StoreMgr->getLValueField(D, Base);
774}
775
776inline 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
786inline 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
792inline SVal ProgramState::getSVal(const Stmt *Ex,
793                                  const LocationContext *LCtx) const{
794  return Env.getSVal(EnvironmentEntry(Ex, LCtx),
795                     *getStateManager().svalBuilder);
796}
797
798inline SVal
799ProgramState::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) ||
804        T->isIntegralOrEnumerationType())
805      return getSVal(S, LCtx);
806  }
807
808  return UnknownVal();
809}
810
811inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const {
812  return getStateManager().StoreMgr->getBinding(getStore(), LV, T);
813}
814
815inline SVal ProgramState::getSVal(const MemRegion* R, QualType T) const {
816  return getStateManager().StoreMgr->getBinding(getStore(),
817                                                loc::MemRegionVal(R),
818                                                T);
819}
820
821inline BasicValueFactory &ProgramState::getBasicVals() const {
822  return getStateManager().getBasicVals();
823}
824
825inline SymbolManager &ProgramState::getSymbolManager() const {
826  return getStateManager().getSymbolManager();
827}
828
829template<typename T>
830ProgramStateRef ProgramState::add(typename ProgramStateTrait<T>::key_type K) const {
831  return getStateManager().add<T>(this, K, get_context<T>());
832}
833
834template <typename T>
835typename ProgramStateTrait<T>::context_type ProgramState::get_context() const {
836  return getStateManager().get_context<T>();
837}
838
839template<typename T>
840ProgramStateRef ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const {
841  return getStateManager().remove<T>(this, K, get_context<T>());
842}
843
844template<typename T>
845ProgramStateRef 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
850template <typename T>
851ProgramStateRef ProgramState::remove() const {
852  return getStateManager().remove<T>(this);
853}
854
855template<typename T>
856ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::data_type D) const {
857  return getStateManager().set<T>(this, D);
858}
859
860template<typename T>
861ProgramStateRef 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
866template<typename T>
867ProgramStateRef ProgramState::set(typename ProgramStateTrait<T>::key_type K,
868                            typename ProgramStateTrait<T>::value_type E,
869                            typename ProgramStateTrait<T>::context_type C) const {
870  return getStateManager().set<T>(this, K, E, C);
871}
872
873template <typename CB>
874CB ProgramState::scanReachableSymbols(SVal val) const {
875  CB cb(this);
876  scanReachableSymbols(val, cb);
877  return cb;
878}
879
880template <typename CB>
881CB 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.
892class ScanReachableSymbols {
893  typedef llvm::DenseSet<const void*> VisitedItems;
894
895  VisitedItems visited;
896  ProgramStateRef state;
897  SymbolVisitor &visitor;
898public:
899  ScanReachableSymbols(ProgramStateRef st, SymbolVisitor &v)
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
914
clang::ento::ProgramStateTrait::MakeVoidPtr
clang::ento::ProgramStateTrait::MakeData
clang::ento::ProgramState::stateMgr
clang::ento::ProgramState::Env
clang::ento::ProgramState::store
clang::ento::ProgramState::GDM
clang::ento::ProgramState::refCount
clang::ento::ProgramState::makeWithStore
clang::ento::ProgramState::setStore
clang::ento::ProgramState::getID
clang::ento::ProgramState::getStateManager
clang::ento::ProgramState::getAnalysisManager
clang::ento::ProgramState::getConstraintManager
clang::ento::ProgramState::getEnvironment
clang::ento::ProgramState::getStore
clang::ento::ProgramState::getGDM
clang::ento::ProgramState::setGDM
clang::ento::ProgramState::Profile
clang::ento::ProgramState::Profile
clang::ento::ProgramState::getBasicVals
clang::ento::ProgramState::getSymbolManager
clang::ento::ProgramState::ProgramStateRef
clang::ento::ProgramState::isNonNull
clang::ento::ProgramState::isNull
clang::ento::ProgramState::areEqual
clang::ento::ProgramState::getRegion
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getSVal
clang::ento::ProgramState::getSValAsScalarOrLoc
clang::ento::ProgramState::getSVal
clang::ento::ProgramState::getRawSVal
clang::ento::ProgramState::getSVal
clang::ento::ProgramState::getSValAsScalarOrLoc
clang::ento::ProgramState::scanReachableSymbols
clang::ento::ProgramState::scanReachableSymbols
clang::ento::ProgramState::scanReachableSymbols
clang::ento::ProgramState::scanReachableSymbols
clang::ento::ProgramState::isTainted
clang::ento::ProgramState::isTainted
clang::ento::ProgramState::isTainted
clang::ento::ProgramState::isTainted
clang::ento::ProgramState::FindGDM
clang::ento::ProgramState::get
clang::ento::ProgramState::get
clang::ento::ProgramState::get_context
clang::ento::ProgramState::contains
clang::ento::ProgramState::print
clang::ento::ProgramState::printDOT
clang::ento::ProgramState::printTaint
clang::ento::ProgramState::dump
clang::ento::ProgramState::dumpTaint
clang::ento::ProgramState::invalidateRegionsImpl
clang::ento::ProgramStateManager::Eng
clang::ento::ProgramStateManager::EnvMgr
clang::ento::ProgramStateManager::StoreMgr
clang::ento::ProgramStateManager::ConstraintMgr
clang::ento::ProgramStateManager::GDMFactory
clang::ento::ProgramStateManager::TSRFactory
clang::ento::ProgramStateManager::GDMContexts
clang::ento::ProgramStateManager::StateSet
clang::ento::ProgramStateManager::svalBuilder
clang::ento::ProgramStateManager::CallEventMgr
clang::ento::ProgramStateManager::Alloc
clang::ento::ProgramStateManager::freeStates
clang::ento::ProgramStateManager::getInitialState
clang::ento::ProgramStateManager::getContext
clang::ento::ProgramStateManager::getContext
clang::ento::ProgramStateManager::getBasicVals
clang::ento::ProgramStateManager::getSValBuilder
clang::ento::ProgramStateManager::getSymbolManager
clang::ento::ProgramStateManager::getSymbolManager
clang::ento::ProgramStateManager::getAllocator
clang::ento::ProgramStateManager::getRegionManager
clang::ento::ProgramStateManager::getRegionManager
clang::ento::ProgramStateManager::getCallEventManager
clang::ento::ProgramStateManager::getStoreManager
clang::ento::ProgramStateManager::getConstraintManager
clang::ento::ProgramStateManager::getOwningEngine
clang::ento::ProgramStateManager::removeDeadBindings
clang::ento::ProgramStateManager::ArrayToPointer
clang::ento::ProgramStateManager::addGDM
clang::ento::ProgramStateManager::removeGDM
clang::ento::ProgramStateManager::iterBindings
clang::ento::ProgramStateManager::getPersistentState
clang::ento::ProgramStateManager::getPersistentStateWithGDM
clang::ento::ProgramStateManager::haveEqualConstraints
clang::ento::ProgramStateManager::haveEqualEnvironments
clang::ento::ProgramStateManager::haveEqualStores
clang::ento::ProgramStateManager::set
clang::ento::ProgramStateManager::set
clang::ento::ProgramStateManager::add
clang::ento::ProgramStateManager::remove
clang::ento::ProgramStateManager::remove
clang::ento::ProgramStateManager::FindGDMContext
clang::ento::ProgramStateManager::get_context
clang::ento::ProgramStateManager::EndPath
clang::ento::ProgramState::getConstraintManager
clang::ento::ProgramState::getRegion
clang::ento::ProgramState::assume
clang::ento::ProgramState::assume
clang::ento::ProgramState::assumeInclusiveRange
clang::ento::ProgramState::assumeInclusiveRange
clang::ento::ProgramState::bindLoc
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getLValue
clang::ento::ProgramState::getSVal
clang::ento::ProgramState::getSValAsScalarOrLoc
clang::ento::ProgramState::getRawSVal
clang::ento::ProgramState::getSVal
clang::ento::ProgramState::getBasicVals
clang::ento::ProgramState::getSymbolManager
clang::ento::ProgramState::add
clang::ento::ProgramState::get_context
clang::ento::ProgramState::remove
clang::ento::ProgramState::remove
clang::ento::ProgramState::remove
clang::ento::ProgramState::set
clang::ento::ProgramState::set
clang::ento::ProgramState::set
clang::ento::ProgramState::scanReachableSymbols
clang::ento::ScanReachableSymbols::visited
clang::ento::ScanReachableSymbols::state
clang::ento::ScanReachableSymbols::visitor
clang::ento::ScanReachableSymbols::scan
clang::ento::ScanReachableSymbols::scan
clang::ento::ScanReachableSymbols::scan
clang::ento::ScanReachableSymbols::scan
clang::ento::ScanReachableSymbols::scan
CodeThinker, Enjoy your reading code