clang  8.0.0svn
Store.h
Go to the documentation of this file.
1 //===- Store.h - Interface for maps from Locations to 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 defined the types Store and StoreManager.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_STORE_H
15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_STORE_H
16 
17 #include "clang/AST/Type.h"
24 #include "clang/Basic/LLVM.h"
25 #include "llvm/ADT/ArrayRef.h"
26 #include "llvm/ADT/DenseSet.h"
27 #include "llvm/ADT/Optional.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include <cassert>
30 #include <cstdint>
31 #include <memory>
32 
33 namespace clang {
34 
35 class ASTContext;
36 class CastExpr;
37 class CompoundLiteralExpr;
38 class CXXBasePath;
39 class Decl;
40 class Expr;
41 class LocationContext;
42 class ObjCIvarDecl;
43 class StackFrameContext;
44 
45 namespace ento {
46 
47 class CallEvent;
48 class ProgramStateManager;
49 class ScanReachableSymbols;
50 class SymbolReaper;
51 
53 
54 class StoreManager {
55 protected:
58 
59  /// MRMgr - Manages region objects associated with this StoreManager.
62 
64 
65 public:
66  virtual ~StoreManager() = default;
67 
68  /// Return the value bound to specified location in a given state.
69  /// \param[in] store The store in which to make the lookup.
70  /// \param[in] loc The symbolic memory location.
71  /// \param[in] T An optional type that provides a hint indicating the
72  /// expected type of the returned value. This is used if the value is
73  /// lazily computed.
74  /// \return The value bound to the location \c loc.
75  virtual SVal getBinding(Store store, Loc loc, QualType T = QualType()) = 0;
76 
77  /// Return the default value bound to a region in a given store. The default
78  /// binding is the value of sub-regions that were not initialized separately
79  /// from their base region. For example, if the structure is zero-initialized
80  /// upon construction, this method retrieves the concrete zero value, even if
81  /// some or all fields were later overwritten manually. Default binding may be
82  /// an unknown, undefined, concrete, or symbolic value.
83  /// \param[in] store The store in which to make the lookup.
84  /// \param[in] R The region to find the default binding for.
85  /// \return The default value bound to the region in the store, if a default
86  /// binding exists.
87  virtual Optional<SVal> getDefaultBinding(Store store, const MemRegion *R) = 0;
88 
89  /// Return the default value bound to a LazyCompoundVal. The default binding
90  /// is used to represent the value of any fields or elements within the
91  /// structure represented by the LazyCompoundVal which were not initialized
92  /// explicitly separately from the whole structure. Default binding may be an
93  /// unknown, undefined, concrete, or symbolic value.
94  /// \param[in] lcv The lazy compound value.
95  /// \return The default value bound to the LazyCompoundVal \c lcv, if a
96  /// default binding exists.
98  return getDefaultBinding(lcv.getStore(), lcv.getRegion());
99  }
100 
101  /// Return a store with the specified value bound to the given location.
102  /// \param[in] store The store in which to make the binding.
103  /// \param[in] loc The symbolic memory location.
104  /// \param[in] val The value to bind to location \c loc.
105  /// \return A StoreRef object that contains the same
106  /// bindings as \c store with the addition of having the value specified
107  /// by \c val bound to the location given for \c loc.
108  virtual StoreRef Bind(Store store, Loc loc, SVal val) = 0;
109 
110  /// Return a store with the specified value bound to all sub-regions of the
111  /// region. The region must not have previous bindings. If you need to
112  /// invalidate existing bindings, consider invalidateRegions().
113  virtual StoreRef BindDefaultInitial(Store store, const MemRegion *R,
114  SVal V) = 0;
115 
116  /// Return a store with in which all values within the given region are
117  /// reset to zero. This method is allowed to overwrite previous bindings.
118  virtual StoreRef BindDefaultZero(Store store, const MemRegion *R) = 0;
119 
120  /// Create a new store with the specified binding removed.
121  /// \param ST the original store, that is the basis for the new store.
122  /// \param L the location whose binding should be removed.
123  virtual StoreRef killBinding(Store ST, Loc L) = 0;
124 
125  /// getInitialStore - Returns the initial "empty" store representing the
126  /// value bindings upon entry to an analyzed function.
127  virtual StoreRef getInitialStore(const LocationContext *InitLoc) = 0;
128 
129  /// getRegionManager - Returns the internal RegionManager object that is
130  /// used to query and manipulate MemRegion objects.
132 
134 
135  virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) {
136  return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC));
137  }
138 
140  const LocationContext *LC) {
141  return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC));
142  }
143 
144  virtual SVal getLValueIvar(const ObjCIvarDecl *decl, SVal base);
145 
146  virtual SVal getLValueField(const FieldDecl *D, SVal Base) {
147  return getLValueFieldOrIvar(D, Base);
148  }
149 
150  virtual SVal getLValueElement(QualType elementType, NonLoc offset, SVal Base);
151 
152  // FIXME: This should soon be eliminated altogether; clients should deal with
153  // region extents directly.
155  const MemRegion *region,
156  QualType EleTy) {
157  return UnknownVal();
158  }
159 
160  /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
161  /// conversions between arrays and pointers.
162  virtual SVal ArrayToPointer(Loc Array, QualType ElementTy) = 0;
163 
164  /// Evaluates a chain of derived-to-base casts through the path specified in
165  /// \p Cast.
166  SVal evalDerivedToBase(SVal Derived, const CastExpr *Cast);
167 
168  /// Evaluates a chain of derived-to-base casts through the specified path.
169  SVal evalDerivedToBase(SVal Derived, const CXXBasePath &CastPath);
170 
171  /// Evaluates a derived-to-base cast through a single level of derivation.
172  SVal evalDerivedToBase(SVal Derived, QualType DerivedPtrType,
173  bool IsVirtual);
174 
175  /// Attempts to do a down cast. Used to model BaseToDerived and C++
176  /// dynamic_cast.
177  /// The callback may result in the following 3 scenarios:
178  /// - Successful cast (ex: derived is subclass of base).
179  /// - Failed cast (ex: derived is definitely not a subclass of base).
180  /// The distinction of this case from the next one is necessary to model
181  /// dynamic_cast.
182  /// - We don't know (base is a symbolic region and we don't have
183  /// enough info to determine if the cast will succeed at run time).
184  /// The function returns an SVal representing the derived class; it's
185  /// valid only if Failed flag is set to false.
186  SVal attemptDownCast(SVal Base, QualType DerivedPtrType, bool &Failed);
187 
189 
190  /// castRegion - Used by ExprEngine::VisitCast to handle casts from
191  /// a MemRegion* to a specific location type. 'R' is the region being
192  /// casted and 'CastToTy' the result type of the cast.
193  const MemRegion *castRegion(const MemRegion *region, QualType CastToTy);
194 
195  virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
196  SymbolReaper &SymReaper) = 0;
197 
198  virtual bool includedInBindings(Store store,
199  const MemRegion *region) const = 0;
200 
201  /// If the StoreManager supports it, increment the reference count of
202  /// the specified Store object.
203  virtual void incrementReferenceCount(Store store) {}
204 
205  /// If the StoreManager supports it, decrement the reference count of
206  /// the specified Store object. If the reference count hits 0, the memory
207  /// associated with the object is recycled.
208  virtual void decrementReferenceCount(Store store) {}
209 
211 
212  /// invalidateRegions - Clears out the specified regions from the store,
213  /// marking their values as unknown. Depending on the store, this may also
214  /// invalidate additional regions that may have changed based on accessing
215  /// the given regions. Optionally, invalidates non-static globals as well.
216  /// \param[in] store The initial store
217  /// \param[in] Values The values to invalidate.
218  /// \param[in] E The current statement being evaluated. Used to conjure
219  /// symbols to mark the values of invalidated regions.
220  /// \param[in] Count The current block count. Used to conjure
221  /// symbols to mark the values of invalidated regions.
222  /// \param[in] Call The call expression which will be used to determine which
223  /// globals should get invalidated.
224  /// \param[in,out] IS A set to fill with any symbols that are no longer
225  /// accessible. Pass \c NULL if this information will not be used.
226  /// \param[in] ITraits Information about invalidation for a particular
227  /// region/symbol.
228  /// \param[in,out] InvalidatedTopLevel A vector to fill with regions
229  //// explicitly being invalidated. Pass \c NULL if this
230  /// information will not be used.
231  /// \param[in,out] Invalidated A vector to fill with any regions being
232  /// invalidated. This should include any regions explicitly invalidated
233  /// even if they do not currently have bindings. Pass \c NULL if this
234  /// information will not be used.
235  virtual StoreRef invalidateRegions(Store store,
236  ArrayRef<SVal> Values,
237  const Expr *E, unsigned Count,
238  const LocationContext *LCtx,
239  const CallEvent *Call,
240  InvalidatedSymbols &IS,
242  InvalidatedRegions *InvalidatedTopLevel,
243  InvalidatedRegions *Invalidated) = 0;
244 
245  /// enterStackFrame - Let the StoreManager to do something when execution
246  /// engine is about to execute into a callee.
248  const CallEvent &Call,
249  const StackFrameContext *CalleeCtx);
250 
251  /// Finds the transitive closure of symbols within the given region.
252  ///
253  /// Returns false if the visitor aborted the scan.
254  virtual bool scanReachableSymbols(Store S, const MemRegion *R,
255  ScanReachableSymbols &Visitor) = 0;
256 
257  virtual void print(Store store, raw_ostream &Out,
258  const char* nl, const char *sep) = 0;
259 
261  public:
262  virtual ~BindingsHandler();
263 
264  virtual bool HandleBinding(StoreManager& SMgr, Store store,
265  const MemRegion *region, SVal val) = 0;
266  };
267 
269  public BindingsHandler {
270  SymbolRef Sym;
271  const MemRegion* Binding = nullptr;
272  bool First = true;
273 
274  public:
275  FindUniqueBinding(SymbolRef sym) : Sym(sym) {}
276 
277  explicit operator bool() { return First && Binding; }
278 
279  bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
280  SVal val) override;
281  const MemRegion *getRegion() { return Binding; }
282  };
283 
284  /// iterBindings - Iterate over the bindings in the Store.
285  virtual void iterBindings(Store store, BindingsHandler& f) = 0;
286 
287 protected:
288  const ElementRegion *MakeElementRegion(const SubRegion *baseRegion,
289  QualType pointeeTy,
290  uint64_t index = 0);
291 
292  /// CastRetrievedVal - Used by subclasses of StoreManager to implement
293  /// implicit casts that arise from loads from regions that are reinterpreted
294  /// as another region.
295  SVal CastRetrievedVal(SVal val, const TypedValueRegion *region,
296  QualType castTy);
297 
298 private:
299  SVal getLValueFieldOrIvar(const Decl *decl, SVal base);
300 };
301 
302 inline StoreRef::StoreRef(Store store, StoreManager & smgr)
303  : store(store), mgr(smgr) {
304  if (store)
305  mgr.incrementReferenceCount(store);
306 }
307 
308 inline StoreRef::StoreRef(const StoreRef &sr)
309  : store(sr.store), mgr(sr.mgr)
310 {
311  if (store)
312  mgr.incrementReferenceCount(store);
313 }
314 
316  if (store)
317  mgr.decrementReferenceCount(store);
318 }
319 
320 inline StoreRef &StoreRef::operator=(StoreRef const &newStore) {
321  assert(&newStore.mgr == &mgr);
322  if (store != newStore.store) {
323  mgr.incrementReferenceCount(newStore.store);
324  mgr.decrementReferenceCount(store);
325  store = newStore.getStore();
326  }
327  return *this;
328 }
329 
330 // FIXME: Do we need to pass ProgramStateManager anymore?
331 std::unique_ptr<StoreManager>
333 std::unique_ptr<StoreManager>
335 
336 } // namespace ento
337 
338 } // namespace clang
339 
340 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_STORE_H
SVal attemptDownCast(SVal Base, QualType DerivedPtrType, bool &Failed)
Attempts to do a down cast.
Definition: Store.cpp:315
virtual DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, const MemRegion *region, QualType EleTy)
Definition: Store.h:154
TypedValueRegion - An abstract class representing regions having a typed value.
Definition: MemRegion.h:525
SVal evalDerivedToBase(SVal Derived, const CastExpr *Cast)
Evaluates a chain of derived-to-base casts through the path specified in Cast.
Definition: Store.cpp:249
A (possibly-)qualified type.
Definition: Type.h:642
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
Store getStore() const
Definition: StoreRef.h:47
Information about invalidation for a particular region/symbol.
Definition: MemRegion.h:1438
C Language Family Type Representation.
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:87
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
virtual StoreRef invalidateRegions(Store store, ArrayRef< SVal > Values, const Expr *E, unsigned Count, const LocationContext *LCtx, const CallEvent *Call, InvalidatedSymbols &IS, RegionAndSymbolInvalidationTraits &ITraits, InvalidatedRegions *InvalidatedTopLevel, InvalidatedRegions *Invalidated)=0
invalidateRegions - Clears out the specified regions from the store, marking their values as unknown...
Represents a path from a specific derived class (which is not represented as part of the path) to a p...
A utility class that visits the reachable symbols using a custom SymbolVisitor.
Definition: ProgramState.h:905
virtual StoreRef BindDefaultZero(Store store, const MemRegion *R)=0
Return a store with in which all values within the given region are reset to zero.
virtual StoreRef getInitialStore(const LocationContext *InitLoc)=0
getInitialStore - Returns the initial "empty" store representing the value bindings upon entry to an ...
Represents a variable declaration or definition.
Definition: Decl.h:812
CompoundLiteralExpr - [C99 6.5.2.5].
Definition: Expr.h:2717
StoreRef(Store store, StoreManager &smgr)
Definition: Store.h:302
const void * Store
Store - This opaque type encapsulates an immutable mapping from locations to values.
Definition: StoreRef.h:28
const ElementRegion * GetElementZeroRegion(const SubRegion *R, QualType T)
Definition: Store.cpp:68
virtual SVal getBinding(Store store, Loc loc, QualType T=QualType())=0
Return the value bound to specified location in a given state.
std::unique_ptr< StoreManager > CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr)
const MemRegion * castRegion(const MemRegion *region, QualType CastToTy)
castRegion - Used by ExprEngine::VisitCast to handle casts from a MemRegion* to a specific location t...
Definition: Store.cpp:75
ASTContext & Ctx
Definition: Store.h:61
Symbolic value.
Definition: SymExpr.h:30
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:2556
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
Optional< SVal > getDefaultBinding(nonloc::LazyCompoundVal lcv)
Return the default value bound to a LazyCompoundVal.
Definition: Store.h:97
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
SValBuilder & getSValBuilder()
Definition: Store.h:133
virtual void decrementReferenceCount(Store store)
If the StoreManager supports it, decrement the reference count of the specified Store object...
Definition: Store.h:208
CastExpr - Base class for type casts, including both implicit casts (ImplicitCastExpr) and explicit c...
Definition: Expr.h:2790
virtual SVal getLValueField(const FieldDecl *D, SVal Base)
Definition: Store.h:146
StoreRef enterStackFrame(Store store, const CallEvent &Call, const StackFrameContext *CalleeCtx)
enterStackFrame - Let the StoreManager to do something when execution engine is about to execute into...
Definition: Store.cpp:47
virtual SVal getLValueIvar(const ObjCIvarDecl *decl, SVal base)
Definition: Store.cpp:453
virtual StoreRef BindDefaultInitial(Store store, const MemRegion *R, SVal V)=0
Return a store with the specified value bound to all sub-regions of the region.
std::unique_ptr< StoreManager > CreateRegionStoreManager(ProgramStateManager &StMgr)
Loc makeLoc(SymbolRef sym)
Definition: SValBuilder.h:354
StoreRef & operator=(StoreRef const &newStore)
Definition: Store.h:320
This represents one expression.
Definition: Expr.h:105
SValBuilder & svalBuilder
Definition: Store.h:56
const internal::VariadicAllOfMatcher< Decl > decl
Matches declarations.
virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC)
Definition: Store.h:135
#define bool
Definition: stdbool.h:31
virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, SymbolReaper &SymReaper)=0
ProgramStateManager & StateMgr
Definition: Store.h:57
virtual StoreRef Bind(Store store, Loc loc, SVal val)=0
Return a store with the specified value bound to the given location.
virtual Optional< SVal > getDefaultBinding(Store store, const MemRegion *R)=0
Return the default value bound to a region in a given store.
virtual StoreRef killBinding(Store ST, Loc L)=0
Create a new store with the specified binding removed.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:76
A class responsible for cleaning up unused symbols.
const CompoundLiteralRegion * getCompoundLiteralRegion(const CompoundLiteralExpr *CL, const LocationContext *LC)
getCompoundLiteralRegion - Retrieve the region associated with a given CompoundLiteral.
Definition: MemRegion.cpp:972
Dataflow Directional Tag Classes.
virtual void iterBindings(Store store, BindingsHandler &f)=0
iterBindings - Iterate over the bindings in the Store.
const VarRegion * getVarRegion(const VarDecl *D, const LocationContext *LC)
getVarRegion - Retrieve or create the memory region associated with a specified VarDecl and LocationC...
Definition: MemRegion.cpp:846
const void * getStore() const
Definition: SVals.cpp:166
virtual bool includedInBindings(Store store, const MemRegion *region) const =0
virtual void print(Store store, raw_ostream &Out, const char *nl, const char *sep)=0
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:182
virtual bool scanReachableSymbols(Store S, const MemRegion *R, ScanReachableSymbols &Visitor)=0
Finds the transitive closure of symbols within the given region.
MemRegionManager & getRegionManager()
getRegionManager - Returns the internal RegionManager object that is used to query and manipulate Mem...
Definition: Store.h:131
SubRegion - A region that subsets another larger region.
Definition: MemRegion.h:431
virtual SVal ArrayToPointer(Loc Array, QualType ElementTy)=0
ArrayToPointer - Used by ExprEngine::VistCast to handle implicit conversions between arrays and point...
const ElementRegion * MakeElementRegion(const SubRegion *baseRegion, QualType pointeeTy, uint64_t index=0)
Definition: Store.cpp:61
SVal CastRetrievedVal(SVal val, const TypedValueRegion *region, QualType castTy)
CastRetrievedVal - Used by subclasses of StoreManager to implement implicit casts that arise from loa...
Definition: Store.cpp:390
MemRegionManager & MRMgr
MRMgr - Manages region objects associated with this StoreManager.
Definition: Store.h:60
virtual SVal getLValueElement(QualType elementType, NonLoc offset, SVal Base)
Definition: Store.cpp:457
const TypedValueRegion * getRegion() const
Definition: SVals.cpp:170
virtual bool HandleBinding(StoreManager &SMgr, Store store, const MemRegion *region, SVal val)=0
ObjCIvarDecl - Represents an ObjC instance variable.
Definition: DeclObjC.h:1937
virtual void incrementReferenceCount(Store store)
If the StoreManager supports it, increment the reference count of the specified Store object...
Definition: Store.h:203
ElementRegin is used to represent both array elements and casts.
Definition: MemRegion.h:1081
virtual ~StoreManager()=default
StoreManager(ProgramStateManager &stateMgr)
Definition: Store.cpp:43
Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL, const LocationContext *LC)
Definition: Store.h:139