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