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/SmallVector.h" |
27 | #include <cassert> |
28 | #include <cstdint> |
29 | #include <memory> |
30 | #include <optional> |
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 std::optional<SVal> getDefaultBinding(Store store, |
87 | 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. |
97 | std::optional<SVal> getDefaultBinding(nonloc::LazyCompoundVal lcv) { |
98 | return getDefaultBinding(store: lcv.getStore(), R: 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. |
131 | MemRegionManager& getRegionManager() { return MRMgr; } |
132 | |
133 | SValBuilder& getSValBuilder() { return svalBuilder; } |
134 | |
135 | virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) { |
136 | return svalBuilder.makeLoc(region: MRMgr.getVarRegion(VD, LC)); |
137 | } |
138 | |
139 | Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL, |
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 | /// ArrayToPointer - Used by ExprEngine::VistCast to handle implicit |
153 | /// conversions between arrays and pointers. |
154 | virtual SVal ArrayToPointer(Loc Array, QualType ElementTy) = 0; |
155 | |
156 | /// Evaluates a chain of derived-to-base casts through the path specified in |
157 | /// \p Cast. |
158 | SVal evalDerivedToBase(SVal Derived, const CastExpr *Cast); |
159 | |
160 | /// Evaluates a chain of derived-to-base casts through the specified path. |
161 | SVal evalDerivedToBase(SVal Derived, const CXXBasePath &CastPath); |
162 | |
163 | /// Evaluates a derived-to-base cast through a single level of derivation. |
164 | SVal evalDerivedToBase(SVal Derived, QualType DerivedPtrType, |
165 | bool IsVirtual); |
166 | |
167 | /// Attempts to do a down cast. Used to model BaseToDerived and C++ |
168 | /// dynamic_cast. |
169 | /// The callback may result in the following 3 scenarios: |
170 | /// - Successful cast (ex: derived is subclass of base). |
171 | /// - Failed cast (ex: derived is definitely not a subclass of base). |
172 | /// The distinction of this case from the next one is necessary to model |
173 | /// dynamic_cast. |
174 | /// - We don't know (base is a symbolic region and we don't have |
175 | /// enough info to determine if the cast will succeed at run time). |
176 | /// The function returns an optional with SVal representing the derived class |
177 | /// in case of a successful cast and `std::nullopt` otherwise. |
178 | std::optional<SVal> evalBaseToDerived(SVal Base, QualType DerivedPtrType); |
179 | |
180 | const ElementRegion *GetElementZeroRegion(const SubRegion *R, QualType T); |
181 | |
182 | /// castRegion - Used by ExprEngine::VisitCast to handle casts from |
183 | /// a MemRegion* to a specific location type. 'R' is the region being |
184 | /// casted and 'CastToTy' the result type of the cast. |
185 | std::optional<const MemRegion *> castRegion(const MemRegion *region, |
186 | QualType CastToTy); |
187 | |
188 | virtual StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx, |
189 | SymbolReaper &SymReaper) = 0; |
190 | |
191 | virtual bool includedInBindings(Store store, |
192 | const MemRegion *region) const = 0; |
193 | |
194 | /// If the StoreManager supports it, increment the reference count of |
195 | /// the specified Store object. |
196 | virtual void incrementReferenceCount(Store store) {} |
197 | |
198 | /// If the StoreManager supports it, decrement the reference count of |
199 | /// the specified Store object. If the reference count hits 0, the memory |
200 | /// associated with the object is recycled. |
201 | virtual void decrementReferenceCount(Store store) {} |
202 | |
203 | using InvalidatedRegions = SmallVector<const MemRegion *, 8>; |
204 | |
205 | /// invalidateRegions - Clears out the specified regions from the store, |
206 | /// marking their values as unknown. Depending on the store, this may also |
207 | /// invalidate additional regions that may have changed based on accessing |
208 | /// the given regions. Optionally, invalidates non-static globals as well. |
209 | /// \param[in] store The initial store |
210 | /// \param[in] Values The values to invalidate. |
211 | /// \param[in] E The current statement being evaluated. Used to conjure |
212 | /// symbols to mark the values of invalidated regions. |
213 | /// \param[in] Count The current block count. Used to conjure |
214 | /// symbols to mark the values of invalidated regions. |
215 | /// \param[in] Call The call expression which will be used to determine which |
216 | /// globals should get invalidated. |
217 | /// \param[in,out] IS A set to fill with any symbols that are no longer |
218 | /// accessible. Pass \c NULL if this information will not be used. |
219 | /// \param[in] ITraits Information about invalidation for a particular |
220 | /// region/symbol. |
221 | /// \param[in,out] InvalidatedTopLevel A vector to fill with regions |
222 | //// explicitly being invalidated. Pass \c NULL if this |
223 | /// information will not be used. |
224 | /// \param[in,out] Invalidated A vector to fill with any regions being |
225 | /// invalidated. This should include any regions explicitly invalidated |
226 | /// even if they do not currently have bindings. Pass \c NULL if this |
227 | /// information will not be used. |
228 | virtual StoreRef invalidateRegions(Store store, |
229 | ArrayRef<SVal> Values, |
230 | const Expr *E, unsigned Count, |
231 | const LocationContext *LCtx, |
232 | const CallEvent *Call, |
233 | InvalidatedSymbols &IS, |
234 | RegionAndSymbolInvalidationTraits &ITraits, |
235 | InvalidatedRegions *InvalidatedTopLevel, |
236 | InvalidatedRegions *Invalidated) = 0; |
237 | |
238 | /// enterStackFrame - Let the StoreManager to do something when execution |
239 | /// engine is about to execute into a callee. |
240 | StoreRef enterStackFrame(Store store, |
241 | const CallEvent &Call, |
242 | const StackFrameContext *CalleeCtx); |
243 | |
244 | /// Finds the transitive closure of symbols within the given region. |
245 | /// |
246 | /// Returns false if the visitor aborted the scan. |
247 | virtual bool scanReachableSymbols(Store S, const MemRegion *R, |
248 | ScanReachableSymbols &Visitor) = 0; |
249 | |
250 | virtual void printJson(raw_ostream &Out, Store S, const char *NL, |
251 | unsigned int Space, bool IsDot) const = 0; |
252 | |
253 | class BindingsHandler { |
254 | public: |
255 | virtual ~BindingsHandler(); |
256 | |
257 | /// \return whether the iteration should continue. |
258 | virtual bool HandleBinding(StoreManager& SMgr, Store store, |
259 | const MemRegion *region, SVal val) = 0; |
260 | }; |
261 | |
262 | class FindUniqueBinding : public BindingsHandler { |
263 | SymbolRef Sym; |
264 | const MemRegion* Binding = nullptr; |
265 | bool First = true; |
266 | |
267 | public: |
268 | FindUniqueBinding(SymbolRef sym) : Sym(sym) {} |
269 | |
270 | explicit operator bool() { return First && Binding; } |
271 | |
272 | bool HandleBinding(StoreManager& SMgr, Store store, const MemRegion* R, |
273 | SVal val) override; |
274 | const MemRegion *getRegion() { return Binding; } |
275 | }; |
276 | |
277 | /// iterBindings - Iterate over the bindings in the Store. |
278 | virtual void iterBindings(Store store, BindingsHandler& f) = 0; |
279 | |
280 | protected: |
281 | const ElementRegion *MakeElementRegion(const SubRegion *baseRegion, |
282 | QualType pointeeTy, |
283 | uint64_t index = 0); |
284 | |
285 | private: |
286 | SVal getLValueFieldOrIvar(const Decl *decl, SVal base); |
287 | }; |
288 | |
289 | inline StoreRef::StoreRef(Store store, StoreManager & smgr) |
290 | : store(store), mgr(smgr) { |
291 | if (store) |
292 | mgr.incrementReferenceCount(store); |
293 | } |
294 | |
295 | inline StoreRef::StoreRef(const StoreRef &sr) |
296 | : store(sr.store), mgr(sr.mgr) |
297 | { |
298 | if (store) |
299 | mgr.incrementReferenceCount(store); |
300 | } |
301 | |
302 | inline StoreRef::~StoreRef() { |
303 | if (store) |
304 | mgr.decrementReferenceCount(store); |
305 | } |
306 | |
307 | inline StoreRef &StoreRef::operator=(StoreRef const &newStore) { |
308 | assert(&newStore.mgr == &mgr); |
309 | if (store != newStore.store) { |
310 | mgr.incrementReferenceCount(store: newStore.store); |
311 | mgr.decrementReferenceCount(store); |
312 | store = newStore.getStore(); |
313 | } |
314 | return *this; |
315 | } |
316 | |
317 | // FIXME: Do we need to pass ProgramStateManager anymore? |
318 | std::unique_ptr<StoreManager> |
319 | CreateRegionStoreManager(ProgramStateManager &StMgr); |
320 | |
321 | } // namespace ento |
322 | |
323 | } // namespace clang |
324 | |
325 | #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_STORE_H |
326 | |