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