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