clang  7.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 
133  virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) {
134  return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC));
135  }
136 
138  const LocationContext *LC) {
139  return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC));
140  }
141 
142  virtual SVal getLValueIvar(const ObjCIvarDecl *decl, SVal base);
143 
144  virtual SVal getLValueField(const FieldDecl *D, SVal Base) {
145  return getLValueFieldOrIvar(D, Base);
146  }
147 
148  virtual SVal getLValueElement(QualType elementType, NonLoc offset, SVal Base);
149 
150  // FIXME: This should soon be eliminated altogether; clients should deal with
151  // region extents directly.
153  const MemRegion *region,
154  QualType EleTy) {
155  return UnknownVal();
156  }
157 
158  /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit
159  /// conversions between arrays and pointers.
160  virtual SVal ArrayToPointer(Loc Array, QualType ElementTy) = 0;
161 
162  /// Evaluates a chain of derived-to-base casts through the path specified in
163  /// \p Cast.
164  SVal evalDerivedToBase(SVal Derived, const CastExpr *Cast);
165 
166  /// Evaluates a chain of derived-to-base casts through the specified path.
167  SVal evalDerivedToBase(SVal Derived, const CXXBasePath &CastPath);
168 
169  /// Evaluates a derived-to-base cast through a single level of derivation.
170  SVal evalDerivedToBase(SVal Derived, QualType DerivedPtrType,
171  bool IsVirtual);
172 
173  /// Attempts to do a down cast. Used to model BaseToDerived and C++
174  /// dynamic_cast.
175  /// The callback may result in the following 3 scenarios:
176  /// - Successful cast (ex: derived is subclass of base).
177  /// - Failed cast (ex: derived is definitely not a subclass of base).
178  /// The distinction of this case from the next one is necessary to model
179  /// dynamic_cast.
180  /// - We don't know (base is a symbolic region and we don't have
181  /// enough info to determine if the cast will succeed at run time).
182  /// The function returns an SVal representing the derived class; it's
183  /// valid only if Failed flag is set to false.
184  SVal attemptDownCast(SVal Base, QualType DerivedPtrType, bool &Failed);
185 
187 
188  /// castRegion - Used by ExprEngine::VisitCast to handle casts from
189  /// a MemRegion* to a specific location type. 'R' is the region being
190  /// casted and 'CastToTy' the result type of the cast.
191  const MemRegion *castRegion(const MemRegion *region, QualType CastToTy);
192 
193  virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
194  SymbolReaper &SymReaper) = 0;
195 
196  virtual bool includedInBindings(Store store,
197  const MemRegion *region) const = 0;
198 
199  /// If the StoreManager supports it, increment the reference count of
200  /// the specified Store object.
201  virtual void incrementReferenceCount(Store store) {}
202 
203  /// If the StoreManager supports it, decrement the reference count of
204  /// the specified Store object. If the reference count hits 0, the memory
205  /// associated with the object is recycled.
206  virtual void decrementReferenceCount(Store store) {}
207 
209 
210  /// invalidateRegions - Clears out the specified regions from the store,
211  /// marking their values as unknown. Depending on the store, this may also
212  /// invalidate additional regions that may have changed based on accessing
213  /// the given regions. Optionally, invalidates non-static globals as well.
214  /// \param[in] store The initial store
215  /// \param[in] Values The values to invalidate.
216  /// \param[in] E The current statement being evaluated. Used to conjure
217  /// symbols to mark the values of invalidated regions.
218  /// \param[in] Count The current block count. Used to conjure
219  /// symbols to mark the values of invalidated regions.
220  /// \param[in] Call The call expression which will be used to determine which
221  /// globals should get invalidated.
222  /// \param[in,out] IS A set to fill with any symbols that are no longer
223  /// accessible. Pass \c NULL if this information will not be used.
224  /// \param[in] ITraits Information about invalidation for a particular
225  /// region/symbol.
226  /// \param[in,out] InvalidatedTopLevel A vector to fill with regions
227  //// explicitly being invalidated. Pass \c NULL if this
228  /// information will not be used.
229  /// \param[in,out] Invalidated A vector to fill with any regions being
230  /// invalidated. This should include any regions explicitly invalidated
231  /// even if they do not currently have bindings. Pass \c NULL if this
232  /// information will not be used.
233  virtual StoreRef invalidateRegions(Store store,
234  ArrayRef<SVal> Values,
235  const Expr *E, unsigned Count,
236  const LocationContext *LCtx,
237  const CallEvent *Call,
238  InvalidatedSymbols &IS,
240  InvalidatedRegions *InvalidatedTopLevel,
241  InvalidatedRegions *Invalidated) = 0;
242 
243  /// enterStackFrame - Let the StoreManager to do something when execution
244  /// engine is about to execute into a callee.
246  const CallEvent &Call,
247  const StackFrameContext *CalleeCtx);
248 
249  /// Finds the transitive closure of symbols within the given region.
250  ///
251  /// Returns false if the visitor aborted the scan.
252  virtual bool scanReachableSymbols(Store S, const MemRegion *R,
253  ScanReachableSymbols &Visitor) = 0;
254 
255  virtual void print(Store store, raw_ostream &Out,
256  const char* nl, const char *sep) = 0;
257 
259  public:
260  virtual ~BindingsHandler();
261 
262  virtual bool HandleBinding(StoreManager& SMgr, Store store,
263  const MemRegion *region, SVal val) = 0;
264  };
265 
267  public BindingsHandler {
268  SymbolRef Sym;
269  const MemRegion* Binding = nullptr;
270  bool First = true;
271 
272  public:
273  FindUniqueBinding(SymbolRef sym) : Sym(sym) {}
274 
275  explicit operator bool() { return First && Binding; }
276 
277  bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R,
278  SVal val) override;
279  const MemRegion *getRegion() { return Binding; }
280  };
281 
282  /// iterBindings - Iterate over the bindings in the Store.
283  virtual void iterBindings(Store store, BindingsHandler& f) = 0;
284 
285 protected:
286  const ElementRegion *MakeElementRegion(const SubRegion *baseRegion,
287  QualType pointeeTy,
288  uint64_t index = 0);
289 
290  /// CastRetrievedVal - Used by subclasses of StoreManager to implement
291  /// implicit casts that arise from loads from regions that are reinterpreted
292  /// as another region.
293  SVal CastRetrievedVal(SVal val, const TypedValueRegion *region,
294  QualType castTy);
295 
296 private:
297  SVal getLValueFieldOrIvar(const Decl *decl, SVal base);
298 };
299 
300 inline StoreRef::StoreRef(Store store, StoreManager & smgr)
301  : store(store), mgr(smgr) {
302  if (store)
303  mgr.incrementReferenceCount(store);
304 }
305 
306 inline StoreRef::StoreRef(const StoreRef &sr)
307  : store(sr.store), mgr(sr.mgr)
308 {
309  if (store)
310  mgr.incrementReferenceCount(store);
311 }
312 
314  if (store)
315  mgr.decrementReferenceCount(store);
316 }
317 
318 inline StoreRef &StoreRef::operator=(StoreRef const &newStore) {
319  assert(&newStore.mgr == &mgr);
320  if (store != newStore.store) {
321  mgr.incrementReferenceCount(newStore.store);
322  mgr.decrementReferenceCount(store);
323  store = newStore.getStore();
324  }
325  return *this;
326 }
327 
328 // FIXME: Do we need to pass ProgramStateManager anymore?
329 std::unique_ptr<StoreManager>
331 std::unique_ptr<StoreManager>
333 
334 } // namespace ento
335 
336 } // namespace clang
337 
338 #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:305
virtual DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, const MemRegion *region, QualType EleTy)
Definition: Store.h:152
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:248
A (possibly-)qualified type.
Definition: Type.h:655
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:1384
C Language Family Type Representation.
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
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:900
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:2715
StoreRef(Store store, StoreManager &smgr)
Definition: Store.h:300
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:150
Represents a member of a struct/union/class.
Definition: Decl.h:2521
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...
virtual void decrementReferenceCount(Store store)
If the StoreManager supports it, decrement the reference count of the specified Store object...
Definition: Store.h:206
CastExpr - Base class for type casts, including both implicit casts (ImplicitCastExpr) and explicit c...
Definition: Expr.h:2788
virtual SVal getLValueField(const FieldDecl *D, SVal Base)
Definition: Store.h:144
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:439
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:318
Expr - This represents one expression.
Definition: Expr.h:106
const FunctionProtoType * T
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:133
#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:945
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:819
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:164
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:376
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:443
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:1964
virtual void incrementReferenceCount(Store store)
If the StoreManager supports it, increment the reference count of the specified Store object...
Definition: Store.h:201
ElementRegin is used to represent both array elements and casts.
Definition: MemRegion.h:1076
virtual ~StoreManager()=default
StoreManager(ProgramStateManager &stateMgr)
Definition: Store.cpp:43
Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL, const LocationContext *LC)
Definition: Store.h:137