contrib/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h

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