Store.h revision 341825
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" 18#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 22#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" 23#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.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 33namespace clang { 34 35class ASTContext; 36class CastExpr; 37class CompoundLiteralExpr; 38class CXXBasePath; 39class Decl; 40class Expr; 41class LocationContext; 42class ObjCIvarDecl; 43class StackFrameContext; 44 45namespace ento { 46 47class CallEvent; 48class ProgramStateManager; 49class ScanReachableSymbols; 50class SymbolReaper; 51 52using InvalidatedSymbols = llvm::DenseSet<SymbolRef>; 53 54class StoreManager { 55protected: 56 SValBuilder &svalBuilder; 57 ProgramStateManager &StateMgr; 58 59 /// MRMgr - Manages region objects associated with this StoreManager. 60 MemRegionManager &MRMgr; 61 ASTContext &Ctx; 62 63 StoreManager(ProgramStateManager &stateMgr); 64 65public: 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. 97 Optional<SVal> getDefaultBinding(nonloc::LazyCompoundVal lcv) { 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. 131 MemRegionManager& getRegionManager() { return MRMgr; } 132 133 virtual Loc getLValueVar(const VarDecl *VD, const LocationContext *LC) { 134 return svalBuilder.makeLoc(MRMgr.getVarRegion(VD, LC)); 135 } 136 137 Loc getLValueCompoundLiteral(const CompoundLiteralExpr *CL, 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. 152 virtual DefinedOrUnknownSVal getSizeInElements(ProgramStateRef state, 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 186 const ElementRegion *GetElementZeroRegion(const SubRegion *R, QualType T); 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 208 using InvalidatedRegions = SmallVector<const MemRegion *, 8>; 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, 239 RegionAndSymbolInvalidationTraits &ITraits, 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. 245 StoreRef enterStackFrame(Store store, 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 258 class BindingsHandler { 259 public: 260 virtual ~BindingsHandler(); 261 262 virtual bool HandleBinding(StoreManager& SMgr, Store store, 263 const MemRegion *region, SVal val) = 0; 264 }; 265 266 class FindUniqueBinding : 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 285protected: 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 296private: 297 SVal getLValueFieldOrIvar(const Decl *decl, SVal base); 298}; 299 300inline StoreRef::StoreRef(Store store, StoreManager & smgr) 301 : store(store), mgr(smgr) { 302 if (store) 303 mgr.incrementReferenceCount(store); 304} 305 306inline StoreRef::StoreRef(const StoreRef &sr) 307 : store(sr.store), mgr(sr.mgr) 308{ 309 if (store) 310 mgr.incrementReferenceCount(store); 311} 312 313inline StoreRef::~StoreRef() { 314 if (store) 315 mgr.decrementReferenceCount(store); 316} 317 318inline 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? 329std::unique_ptr<StoreManager> 330CreateRegionStoreManager(ProgramStateManager &StMgr); 331std::unique_ptr<StoreManager> 332CreateFieldsOnlyRegionStoreManager(ProgramStateManager &StMgr); 333 334} // namespace ento 335 336} // namespace clang 337 338#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_STORE_H 339