lib/Analysis/BasicStore.cpp - platform/external/clang - Gitiles

 //== BasicStore.cpp - Basic map from Locations to Values --------*- C++ -*--==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defined the BasicStore and BasicStoreManager classes.
 //
 //===----------------------------------------------------------------------===//

 #include "clang/AST/ExprObjC.h"
 #include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/Analysis/PathSensitive/GRState.h"
 #include "llvm/ADT/ImmutableMap.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Streams.h"

 using namespace clang;

 typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;

 namespace {

 class VISIBILITY_HIDDEN BasicStoreSubRegionMap : public SubRegionMap {
 public:
   BasicStoreSubRegionMap() {}

   bool iterSubRegions(const MemRegion* R, Visitor& V) const {
     return true; // Do nothing.  No subregions.
   }
 };

 class VISIBILITY_HIDDEN BasicStoreManager : public StoreManager {
   BindingsTy::Factory VBFactory;
   GRStateManager& StateMgr;
   const MemRegion* SelfRegion;

 public:
   BasicStoreManager(GRStateManager& mgr)
     : StoreManager(mgr.getValueManager()),
       VBFactory(mgr.getAllocator()),
       StateMgr(mgr),
       SelfRegion(0) {}

   ~BasicStoreManager() {}

   SubRegionMap* getSubRegionMap(const GRState *state) {
     return new BasicStoreSubRegionMap();
   }

   SVal Retrieve(const GRState *state, Loc loc, QualType T = QualType());

   const GRState* Bind(const GRState* St, Loc L, SVal V) {
     Store store = BindInternal(St->getStore(), L, V);
     return StateMgr.MakeStateWithStore(St, store);
   }

   Store scanForIvars(Stmt *B, const Decl* SelfDecl, Store St);

   Store BindInternal(Store St, Loc loc, SVal V);
   Store Remove(Store St, Loc loc);
   Store getInitialStore();

   // FIXME: Investigate what is using this. This method should be removed.
   virtual Loc getLoc(const VarDecl* VD) {
     return Loc::MakeVal(MRMgr.getVarRegion(VD));
   }

   const GRState* BindCompoundLiteral(const GRState* St,
                                      const CompoundLiteralExpr* CL,
                                      SVal V) {
     return St;
   }

   SVal getLValueVar(const GRState* St, const VarDecl* VD);
   SVal getLValueString(const GRState* St, const StringLiteral* S);
   SVal getLValueCompoundLiteral(const GRState* St,
                                 const CompoundLiteralExpr* CL);
   SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
   SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
   SVal getLValueElement(const GRState* St, SVal Base, SVal Offset);

   /// ArrayToPointer - Used by GRExprEngine::VistCast to handle implicit
   ///  conversions between arrays and pointers.
   SVal ArrayToPointer(Loc Array) { return Array; }

   /// CastRegion - Used by GRExprEngine::VisitCast to handle casts from
   ///  a MemRegion* to a specific location type.  'R' is the region being
   ///  casted and 'CastToTy' the result type of the cast.
   CastResult CastRegion(const GRState* state, const MemRegion* R,
                         QualType CastToTy);

   /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
   ///  'this' object (C++).  When used when analyzing a normal function this
   ///  method returns NULL.
   const MemRegion* getSelfRegion(Store) { return SelfRegion; }

   /// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
   ///  It returns a new Store with these values removed, and populates LSymbols
   ///  and DSymbols with the known set of live and dead symbols respectively.
   Store
   RemoveDeadBindings(const GRState* state, Stmt* Loc,
                      SymbolReaper& SymReaper,
                      llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);

   void iterBindings(Store store, BindingsHandler& f);

   const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal InitVal) {
     Store store = BindDeclInternal(St->getStore(), VD, &InitVal);
     return StateMgr.MakeStateWithStore(St, store);
   }

   const GRState* BindDeclWithNoInit(const GRState* St, const VarDecl* VD) {
     Store store = BindDeclInternal(St->getStore(), VD, 0);
     return StateMgr.MakeStateWithStore(St, store);
   }

   Store BindDeclInternal(Store store, const VarDecl* VD, SVal* InitVal);

   static inline BindingsTy GetBindings(Store store) {
     return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
   }

   void print(Store store, std::ostream& Out, const char* nl, const char *sep);

 private:
   ASTContext& getContext() { return StateMgr.getContext(); }
 };

 } // end anonymous namespace


 StoreManager* clang::CreateBasicStoreManager(GRStateManager& StMgr) {
   return new BasicStoreManager(StMgr);
 }

 SVal BasicStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
   return Loc::MakeVal(MRMgr.getVarRegion(VD));
 }

 SVal BasicStoreManager::getLValueString(const GRState* St,
                                         const StringLiteral* S) {
   return Loc::MakeVal(MRMgr.getStringRegion(S));
 }

 SVal BasicStoreManager::getLValueCompoundLiteral(const GRState* St,
                                                  const CompoundLiteralExpr* CL){
   return Loc::MakeVal(MRMgr.getCompoundLiteralRegion(CL));
 }

 SVal BasicStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
                                       SVal Base) {

   if (Base.isUnknownOrUndef())
     return Base;

   Loc BaseL = cast<Loc>(Base);

   if (isa<loc::MemRegionVal>(BaseL)) {
     const MemRegion *BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();

     if (BaseR == SelfRegion)
       return loc::MemRegionVal(MRMgr.getObjCIvarRegion(D, BaseR));
   }

   return UnknownVal();
 }

 /// CastRegion - Used by GRExprEngine::VisitCast to handle casts from
 ///  a MemRegion* to a specific location type.  'R' is the region being
 ///  casted and 'CastToTy' the result type of the cast.
 StoreManager::CastResult
 BasicStoreManager::CastRegion(const GRState* state, const MemRegion* R,
                               QualType CastToTy) {

   // Return the same region if the region types are compatible.
   if (const TypedRegion* TR = dyn_cast<TypedRegion>(R)) {
     ASTContext& Ctx = StateMgr.getContext();
     QualType Ta = Ctx.getCanonicalType(TR->getLValueType(Ctx));
     QualType Tb = Ctx.getCanonicalType(CastToTy);

     if (Ta == Tb)
       return CastResult(state, R);
   }

   return CastResult(state, MRMgr.getTypedViewRegion(CastToTy, R));
 }

 SVal BasicStoreManager::getLValueField(const GRState* St, SVal Base,
                                        const FieldDecl* D) {

   if (Base.isUnknownOrUndef())
     return Base;

   Loc BaseL = cast<Loc>(Base);
   const MemRegion* BaseR = 0;

   switch(BaseL.getSubKind()) {
     case loc::GotoLabelKind:
     case loc::FuncValKind:
       // Technically we can get here if people do funny things with casts.
       return UndefinedVal();

     case loc::MemRegionKind:
       BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
       break;

     case loc::ConcreteIntKind:
       // While these seem funny, this can happen through casts.
       // FIXME: What we should return is the field offset.  For example,
       //  add the field offset to the integer value.  That way funny things
       //  like this work properly:  &(((struct foo *) 0xa)->f)
       return Base;

     default:
       assert ("Unhandled Base.");
       return Base;
   }

   return Loc::MakeVal(MRMgr.getFieldRegion(D, BaseR));
 }

 SVal BasicStoreManager::getLValueElement(const GRState* St, SVal Base,
                                          SVal Offset) {

   if (Base.isUnknownOrUndef())
     return Base;

   Loc BaseL = cast<Loc>(Base);
   const TypedRegion* BaseR = 0;

   switch(BaseL.getSubKind()) {
     case loc::GotoLabelKind:
     case loc::FuncValKind:
       // Technically we can get here if people do funny things with casts.
       return UndefinedVal();

     case loc::MemRegionKind: {
       const MemRegion *R = cast<loc::MemRegionVal>(BaseL).getRegion();

       if (isa<ElementRegion>(R)) {
         // Basic example:
         //   char buf[100];
         //   char *q = &buf[1];  // p points to ElementRegion(buf,Unknown)
         //   &q[10]
         assert(cast<ElementRegion>(R)->getIndex().isUnknown());
         return Base;
       }


       if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
         BaseR = TR;
         break;
       }

       if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
         SymbolRef Sym = SR->getSymbol();
         BaseR = MRMgr.getTypedViewRegion(Sym->getType(getContext()), SR);
       }

       break;
     }

     case loc::ConcreteIntKind:
       // While these seem funny, this can happen through casts.
       // FIXME: What we should return is the field offset.  For example,
       //  add the field offset to the integer value.  That way funny things
       //  like this work properly:  &(((struct foo *) 0xa)->f)
       return Base;

     default:
       assert ("Unhandled Base.");
       return Base;
   }

   if (BaseR)
     return Loc::MakeVal(MRMgr.getElementRegion(UnknownVal(), BaseR));
   else
     return UnknownVal();
 }

 static bool isHigherOrderVoidPtr(QualType T, ASTContext &C) {
   bool foundPointer = false;
   while (1) {
     const PointerType *PT = T->getAsPointerType();
     if (!PT) {
       if (!foundPointer)
         return false;

       QualType X = C.getCanonicalType(T).getUnqualifiedType();
       return X == C.VoidTy;
     }

     foundPointer = true;
     T = PT->getPointeeType();
   }
 }

 SVal BasicStoreManager::Retrieve(const GRState* state, Loc loc, QualType T) {

   if (isa<UnknownVal>(loc))
     return UnknownVal();

   assert (!isa<UndefinedVal>(loc));

   switch (loc.getSubKind()) {

     case loc::MemRegionKind: {
       const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();

       if (const TypedViewRegion *TR = dyn_cast<TypedViewRegion>(R)) {
         // Just support void**, void***, etc., for now.  This is needed
         // to handle OSCompareAndSwapPtr().
         ASTContext &Ctx = StateMgr.getContext();
         QualType T = TR->getLValueType(Ctx);

         if (!isHigherOrderVoidPtr(T, Ctx))
           return UnknownVal();

         // Otherwise, strip the views.
         // FIXME: Should we layer a TypedView on the result?
         R = TR->removeViews();
       }

       if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
         return UnknownVal();

       BindingsTy B = GetBindings(state->getStore());
       BindingsTy::data_type* T = B.lookup(R);
       return T ? *T : UnknownVal();
     }

     case loc::ConcreteIntKind:
       // Some clients may call GetSVal with such an option simply because
       // they are doing a quick scan through their Locs (potentially to
       // invalidate their bindings).  Just return Undefined.
       return UndefinedVal();
     case loc::FuncValKind:
       return loc;

     default:
       assert (false && "Invalid Loc.");
       break;
   }

   return UnknownVal();
 }

 Store BasicStoreManager::BindInternal(Store store, Loc loc, SVal V) {
   switch (loc.getSubKind()) {
     case loc::MemRegionKind: {
       const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();

       if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
         return store;

       // We only track bindings to self.ivar.
       if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R))
         if (IVR->getSuperRegion() != SelfRegion)
           return store;

       BindingsTy B = GetBindings(store);
       return V.isUnknown()
         ? VBFactory.Remove(B, R).getRoot()
         : VBFactory.Add(B, R, V).getRoot();
     }
     default:
       assert ("SetSVal for given Loc type not yet implemented.");
       return store;
   }
 }

 Store BasicStoreManager::Remove(Store store, Loc loc) {
   switch (loc.getSubKind()) {
     case loc::MemRegionKind: {
       const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();

       if (!(isa<VarRegion>(R) || isa<ObjCIvarRegion>(R)))
         return store;

       return VBFactory.Remove(GetBindings(store), R).getRoot();
     }
     default:
       assert ("Remove for given Loc type not yet implemented.");
       return store;
   }
 }

 Store
 BasicStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
                                       SymbolReaper& SymReaper,
                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
 {

   Store store = state->getStore();
   BindingsTy B = GetBindings(store);
   typedef SVal::symbol_iterator symbol_iterator;

   // Iterate over the variable bindings.
   for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
     if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
       if (SymReaper.isLive(Loc, VR->getDecl()))
         RegionRoots.push_back(VR);
       else
         continue;
     }
     else if (isa<ObjCIvarRegion>(I.getKey())) {
       RegionRoots.push_back(I.getKey());
     }
     else
       continue;

     // Mark the bindings in the data as live.
     SVal X = I.getData();
     for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
       SymReaper.markLive(*SI);
   }

   // Scan for live variables and live symbols.
   llvm::SmallPtrSet<const MemRegion*, 10> Marked;

   while (!RegionRoots.empty()) {
     const MemRegion* MR = RegionRoots.back();
     RegionRoots.pop_back();

     while (MR) {
       if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
         SymReaper.markLive(SymR->getSymbol());
         break;
       }
       else if (isa<VarRegion>(MR) || isa<ObjCIvarRegion>(MR)) {
         if (Marked.count(MR))
           break;

         Marked.insert(MR);
         SVal X = Retrieve(state, loc::MemRegionVal(MR));

         // FIXME: We need to handle symbols nested in region definitions.
         for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
           SymReaper.markLive(*SI);

         if (!isa<loc::MemRegionVal>(X))
           break;

         const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
         RegionRoots.push_back(LVD.getRegion());
         break;
       }
       else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
         MR = R->getSuperRegion();
       else
         break;
     }
   }

   // Remove dead variable bindings.
   for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
     const MemRegion* R = I.getKey();

     if (!Marked.count(R)) {
       store = Remove(store, Loc::MakeVal(R));
       SVal X = I.getData();

       for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
         SymReaper.maybeDead(*SI);
     }
   }

   return store;
 }

 Store BasicStoreManager::scanForIvars(Stmt *B, const Decl* SelfDecl, Store St) {
   for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
        CI != CE; ++CI) {

     if (!*CI)
       continue;

     // Check if the statement is an ivar reference.  We only
     // care about self.ivar.
     if (ObjCIvarRefExpr *IV = dyn_cast<ObjCIvarRefExpr>(*CI)) {
       const Expr *Base = IV->getBase()->IgnoreParenCasts();
       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
         if (DR->getDecl() == SelfDecl) {
           const MemRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
                                                          SelfRegion);
           SVal X = ValMgr.getRValueSymbolVal(IVR);
           St = BindInternal(St, Loc::MakeVal(IVR), X);
         }
       }
     }
     else
       St = scanForIvars(*CI, SelfDecl, St);
   }

   return St;
 }

 Store BasicStoreManager::getInitialStore() {
   // The LiveVariables information already has a compilation of all VarDecls
   // used in the function.  Iterate through this set, and "symbolicate"
   // any VarDecl whose value originally comes from outside the function.
   typedef LiveVariables::AnalysisDataTy LVDataTy;
   LVDataTy& D = StateMgr.getLiveVariables().getAnalysisData();
   Store St = VBFactory.GetEmptyMap().getRoot();

   for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
     NamedDecl* ND = const_cast<NamedDecl*>(I->first);

     // Handle implicit parameters.
     if (ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
       const Decl& CD = StateMgr.getCodeDecl();
       if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
         if (MD->getSelfDecl() == PD) {
           // Create a region for "self".
           assert (SelfRegion == 0);
           SelfRegion = MRMgr.getObjCObjectRegion(MD->getClassInterface(),
                                                  MRMgr.getHeapRegion());

           St = BindInternal(St, Loc::MakeVal(MRMgr.getVarRegion(PD)),
                             Loc::MakeVal(SelfRegion));

           // Scan the method for ivar references.  While this requires an
           // entire AST scan, the cost should not be high in practice.
           St = scanForIvars(MD->getBody(), PD, St);
         }
       }
     }
     else if (VarDecl* VD = dyn_cast<VarDecl>(ND)) {
       // Punt on static variables for now.
       if (VD->getStorageClass() == VarDecl::Static)
         continue;

       // Only handle simple types that we can symbolicate.
       if (!SymbolManager::canSymbolicate(VD->getType()))
         continue;

       // Initialize globals and parameters to symbolic values.
       // Initialize local variables to undefined.
       const MemRegion *R = StateMgr.getRegion(VD);
       SVal X = (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD) ||
                 isa<ImplicitParamDecl>(VD))
             ? ValMgr.getRValueSymbolVal(R)
             : UndefinedVal();

       St = BindInternal(St, Loc::MakeVal(R), X);
     }
   }
   return St;
 }

 Store BasicStoreManager::BindDeclInternal(Store store, const VarDecl* VD,
                                           SVal* InitVal) {

   BasicValueFactory& BasicVals = StateMgr.getBasicVals();

   // BasicStore does not model arrays and structs.
   if (VD->getType()->isArrayType() || VD->getType()->isStructureType())
     return store;

   if (VD->hasGlobalStorage()) {
     // Handle variables with global storage: extern, static, PrivateExtern.

     // FIXME:: static variables may have an initializer, but the second time a
     // function is called those values may not be current. Currently, a function
     // will not be called more than once.

     // Static global variables should not be visited here.
     assert(!(VD->getStorageClass() == VarDecl::Static &&
              VD->isFileVarDecl()));

     // Process static variables.
     if (VD->getStorageClass() == VarDecl::Static) {
       // C99: 6.7.8 Initialization
       //  If an object that has static storage duration is not initialized
       //  explicitly, then:
       //   —if it has pointer type, it is initialized to a null pointer;
       //   —if it has arithmetic type, it is initialized to (positive or
       //     unsigned) zero;
       if (!InitVal) {
         QualType T = VD->getType();
         if (Loc::IsLocType(T))
           store = BindInternal(store, getLoc(VD),
                        loc::ConcreteInt(BasicVals.getValue(0, T)));
         else if (T->isIntegerType())
           store = BindInternal(store, getLoc(VD),
                        nonloc::ConcreteInt(BasicVals.getValue(0, T)));
         else {
           // assert(0 && "ignore other types of variables");
         }
       } else {
         store = BindInternal(store, getLoc(VD), *InitVal);
       }
     }
   } else {
     // Process local scalar variables.
     QualType T = VD->getType();
     if (Loc::IsLocType(T) || T->isIntegerType()) {
       SVal V = InitVal ? *InitVal : UndefinedVal();
       store = BindInternal(store, getLoc(VD), V);
     }
   }

   return store;
 }

 void BasicStoreManager::print(Store store, std::ostream& O,
                               const char* nl, const char *sep) {

   llvm::raw_os_ostream Out(O);
   BindingsTy B = GetBindings(store);
   Out << "Variables:" << nl;

   bool isFirst = true;

   for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
     if (isFirst) isFirst = false;
     else Out << nl;

     Out << ' ' << I.getKey() << " : ";
     I.getData().print(Out);
   }
 }


 void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
   BindingsTy B = GetBindings(store);

   for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
     f.HandleBinding(*this, store, I.getKey(), I.getData());

 }

 StoreManager::BindingsHandler::~BindingsHandler() {}
	//== BasicStore.cpp - Basic map from Locations to Values --------- C++ ---==//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// This file defined the BasicStore and BasicStoreManager classes.
	//
	//===----------------------------------------------------------------------===//

	#include "clang/AST/ExprObjC.h"
	#include "clang/Analysis/Analyses/LiveVariables.h"
	#include "clang/Analysis/PathSensitive/GRState.h"
	#include "llvm/ADT/ImmutableMap.h"
	#include "llvm/Support/Compiler.h"
	#include "llvm/Support/Streams.h"

	using namespace clang;

	typedef llvm::ImmutableMap<const MemRegion*,SVal> BindingsTy;

	namespace {

	class VISIBILITY_HIDDEN BasicStoreSubRegionMap : public SubRegionMap {
	public:
	BasicStoreSubRegionMap() {}

	bool iterSubRegions(const MemRegion* R, Visitor& V) const {
	return true; // Do nothing. No subregions.
	}
	};

	class VISIBILITY_HIDDEN BasicStoreManager : public StoreManager {
	BindingsTy::Factory VBFactory;
	GRStateManager& StateMgr;
	const MemRegion* SelfRegion;

	public:
	BasicStoreManager(GRStateManager& mgr)
	: StoreManager(mgr.getValueManager()),
	VBFactory(mgr.getAllocator()),
	StateMgr(mgr),
	SelfRegion(0) {}

	~BasicStoreManager() {}

	SubRegionMap* getSubRegionMap(const GRState *state) {
	return new BasicStoreSubRegionMap();
	}

	SVal Retrieve(const GRState *state, Loc loc, QualType T = QualType());

	const GRState* Bind(const GRState* St, Loc L, SVal V) {
	Store store = BindInternal(St->getStore(), L, V);
	return StateMgr.MakeStateWithStore(St, store);
	}

	Store scanForIvars(Stmt B, const Decl SelfDecl, Store St);

	Store BindInternal(Store St, Loc loc, SVal V);
	Store Remove(Store St, Loc loc);
	Store getInitialStore();

	// FIXME: Investigate what is using this. This method should be removed.
	virtual Loc getLoc(const VarDecl* VD) {
	return Loc::MakeVal(MRMgr.getVarRegion(VD));
	}

	const GRState* BindCompoundLiteral(const GRState* St,
	const CompoundLiteralExpr* CL,
	SVal V) {
	return St;
	}

	SVal getLValueVar(const GRState* St, const VarDecl* VD);
	SVal getLValueString(const GRState* St, const StringLiteral* S);
	SVal getLValueCompoundLiteral(const GRState* St,
	const CompoundLiteralExpr* CL);
	SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
	SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
	SVal getLValueElement(const GRState* St, SVal Base, SVal Offset);

	/// ArrayToPointer - Used by GRExprEngine::VistCast to handle implicit
	/// conversions between arrays and pointers.
	SVal ArrayToPointer(Loc Array) { return Array; }

	/// CastRegion - Used by GRExprEngine::VisitCast to handle casts from
	/// a MemRegion* to a specific location type. 'R' is the region being
	/// casted and 'CastToTy' the result type of the cast.
	CastResult CastRegion(const GRState* state, const MemRegion* R,
	QualType CastToTy);

	/// getSelfRegion - Returns the region for the 'self' (Objective-C) or
	/// 'this' object (C++). When used when analyzing a normal function this
	/// method returns NULL.
	const MemRegion* getSelfRegion(Store) { return SelfRegion; }

	/// RemoveDeadBindings - Scans a BasicStore of 'state' for dead values.
	/// It returns a new Store with these values removed, and populates LSymbols
	/// and DSymbols with the known set of live and dead symbols respectively.
	Store
	RemoveDeadBindings(const GRState* state, Stmt* Loc,
	SymbolReaper& SymReaper,
	llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);

	void iterBindings(Store store, BindingsHandler& f);

	const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal InitVal) {
	Store store = BindDeclInternal(St->getStore(), VD, &InitVal);
	return StateMgr.MakeStateWithStore(St, store);
	}

	const GRState* BindDeclWithNoInit(const GRState* St, const VarDecl* VD) {
	Store store = BindDeclInternal(St->getStore(), VD, 0);
	return StateMgr.MakeStateWithStore(St, store);
	}

	Store BindDeclInternal(Store store, const VarDecl* VD, SVal* InitVal);

	static inline BindingsTy GetBindings(Store store) {
	return BindingsTy(static_cast<const BindingsTy::TreeTy*>(store));
	}

	void print(Store store, std::ostream& Out, const char* nl, const char *sep);

	private:
	ASTContext& getContext() { return StateMgr.getContext(); }
	};

	} // end anonymous namespace


	StoreManager* clang::CreateBasicStoreManager(GRStateManager& StMgr) {
	return new BasicStoreManager(StMgr);
	}

	SVal BasicStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
	return Loc::MakeVal(MRMgr.getVarRegion(VD));
	}

	SVal BasicStoreManager::getLValueString(const GRState* St,
	const StringLiteral* S) {
	return Loc::MakeVal(MRMgr.getStringRegion(S));
	}

	SVal BasicStoreManager::getLValueCompoundLiteral(const GRState* St,
	const CompoundLiteralExpr* CL){
	return Loc::MakeVal(MRMgr.getCompoundLiteralRegion(CL));
	}

	SVal BasicStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
	SVal Base) {

	if (Base.isUnknownOrUndef())
	return Base;

	Loc BaseL = cast<Loc>(Base);

	if (isa<loc::MemRegionVal>(BaseL)) {
	const MemRegion *BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();

	if (BaseR == SelfRegion)
	return loc::MemRegionVal(MRMgr.getObjCIvarRegion(D, BaseR));
	}

	return UnknownVal();
	}

	/// CastRegion - Used by GRExprEngine::VisitCast to handle casts from
	/// a MemRegion* to a specific location type. 'R' is the region being
	/// casted and 'CastToTy' the result type of the cast.
	StoreManager::CastResult
	BasicStoreManager::CastRegion(const GRState* state, const MemRegion* R,
	QualType CastToTy) {

	// Return the same region if the region types are compatible.
	if (const TypedRegion* TR = dyn_cast<TypedRegion>(R)) {
	ASTContext& Ctx = StateMgr.getContext();
	QualType Ta = Ctx.getCanonicalType(TR->getLValueType(Ctx));
	QualType Tb = Ctx.getCanonicalType(CastToTy);

	if (Ta == Tb)
	return CastResult(state, R);
	}

	return CastResult(state, MRMgr.getTypedViewRegion(CastToTy, R));
	}

	SVal BasicStoreManager::getLValueField(const GRState* St, SVal Base,
	const FieldDecl* D) {

	if (Base.isUnknownOrUndef())
	return Base;

	Loc BaseL = cast<Loc>(Base);
	const MemRegion* BaseR = 0;

	switch(BaseL.getSubKind()) {
	case loc::GotoLabelKind:
	case loc::FuncValKind:
	// Technically we can get here if people do funny things with casts.
	return UndefinedVal();

	case loc::MemRegionKind:
	BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
	break;

	case loc::ConcreteIntKind:
	// While these seem funny, this can happen through casts.
	// FIXME: What we should return is the field offset. For example,
	// add the field offset to the integer value. That way funny things
	// like this work properly: &(((struct foo *) 0xa)->f)
	return Base;

	default:
	assert ("Unhandled Base.");
	return Base;
	}

	return Loc::MakeVal(MRMgr.getFieldRegion(D, BaseR));
	}

	SVal BasicStoreManager::getLValueElement(const GRState* St, SVal Base,
	SVal Offset) {

	if (Base.isUnknownOrUndef())
	return Base;

	Loc BaseL = cast<Loc>(Base);
	const TypedRegion* BaseR = 0;

	switch(BaseL.getSubKind()) {
	case loc::GotoLabelKind:
	case loc::FuncValKind:
	// Technically we can get here if people do funny things with casts.
	return UndefinedVal();

	case loc::MemRegionKind: {
	const MemRegion *R = cast<loc::MemRegionVal>(BaseL).getRegion();

	if (isa<ElementRegion>(R)) {
	// Basic example:
	// char buf[100];
	// char *q = &buf[1]; // p points to ElementRegion(buf,Unknown)
	// &q[10]
	assert(cast<ElementRegion>(R)->getIndex().isUnknown());
	return Base;
	}


	if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
	BaseR = TR;
	break;
	}

	if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
	SymbolRef Sym = SR->getSymbol();
	BaseR = MRMgr.getTypedViewRegion(Sym->getType(getContext()), SR);
	}

	break;
	}

	case loc::ConcreteIntKind:
	// While these seem funny, this can happen through casts.
	// FIXME: What we should return is the field offset. For example,
	// add the field offset to the integer value. That way funny things
	// like this work properly: &(((struct foo *) 0xa)->f)
	return Base;

	default:
	assert ("Unhandled Base.");
	return Base;
	}

	if (BaseR)
	return Loc::MakeVal(MRMgr.getElementRegion(UnknownVal(), BaseR));
	else
	return UnknownVal();
	}

	static bool isHigherOrderVoidPtr(QualType T, ASTContext &C) {
	bool foundPointer = false;
	while (1) {
	const PointerType *PT = T->getAsPointerType();
	if (!PT) {
	if (!foundPointer)
	return false;

	QualType X = C.getCanonicalType(T).getUnqualifiedType();
	return X == C.VoidTy;
	}

	foundPointer = true;
	T = PT->getPointeeType();
	}
	}

	SVal BasicStoreManager::Retrieve(const GRState* state, Loc loc, QualType T) {

	if (isa<UnknownVal>(loc))
	return UnknownVal();

	assert (!isa<UndefinedVal>(loc));

	switch (loc.getSubKind()) {

	case loc::MemRegionKind: {
	const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();

	if (const TypedViewRegion *TR = dyn_cast<TypedViewRegion>(R)) {
	// Just support void, void*, etc., for now. This is needed
	// to handle OSCompareAndSwapPtr().
	ASTContext &Ctx = StateMgr.getContext();
	QualType T = TR->getLValueType(Ctx);

	if (!isHigherOrderVoidPtr(T, Ctx))
	return UnknownVal();

	// Otherwise, strip the views.
	// FIXME: Should we layer a TypedView on the result?
	R = TR->removeViews();
	}

	if (!(isa<VarRegion>(R) \|\| isa<ObjCIvarRegion>(R)))
	return UnknownVal();

	BindingsTy B = GetBindings(state->getStore());
	BindingsTy::data_type* T = B.lookup(R);
	return T ? *T : UnknownVal();
	}

	case loc::ConcreteIntKind:
	// Some clients may call GetSVal with such an option simply because
	// they are doing a quick scan through their Locs (potentially to
	// invalidate their bindings). Just return Undefined.
	return UndefinedVal();
	case loc::FuncValKind:
	return loc;

	default:
	assert (false && "Invalid Loc.");
	break;
	}

	return UnknownVal();
	}

	Store BasicStoreManager::BindInternal(Store store, Loc loc, SVal V) {
	switch (loc.getSubKind()) {
	case loc::MemRegionKind: {
	const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();

	if (!(isa<VarRegion>(R) \|\| isa<ObjCIvarRegion>(R)))
	return store;

	// We only track bindings to self.ivar.
	if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R))
	if (IVR->getSuperRegion() != SelfRegion)
	return store;

	BindingsTy B = GetBindings(store);
	return V.isUnknown()
	? VBFactory.Remove(B, R).getRoot()
	: VBFactory.Add(B, R, V).getRoot();
	}
	default:
	assert ("SetSVal for given Loc type not yet implemented.");
	return store;
	}
	}

	Store BasicStoreManager::Remove(Store store, Loc loc) {
	switch (loc.getSubKind()) {
	case loc::MemRegionKind: {
	const MemRegion* R = cast<loc::MemRegionVal>(loc).getRegion();

	if (!(isa<VarRegion>(R) \|\| isa<ObjCIvarRegion>(R)))
	return store;

	return VBFactory.Remove(GetBindings(store), R).getRoot();
	}
	default:
	assert ("Remove for given Loc type not yet implemented.");
	return store;
	}
	}

	Store
	BasicStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
	SymbolReaper& SymReaper,
	llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
	{

	Store store = state->getStore();
	BindingsTy B = GetBindings(store);
	typedef SVal::symbol_iterator symbol_iterator;

	// Iterate over the variable bindings.
	for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
	if (const VarRegion *VR = dyn_cast<VarRegion>(I.getKey())) {
	if (SymReaper.isLive(Loc, VR->getDecl()))
	RegionRoots.push_back(VR);
	else
	continue;
	}
	else if (isa<ObjCIvarRegion>(I.getKey())) {
	RegionRoots.push_back(I.getKey());
	}
	else
	continue;

	// Mark the bindings in the data as live.
	SVal X = I.getData();
	for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
	SymReaper.markLive(*SI);
	}

	// Scan for live variables and live symbols.
	llvm::SmallPtrSet<const MemRegion*, 10> Marked;

	while (!RegionRoots.empty()) {
	const MemRegion* MR = RegionRoots.back();
	RegionRoots.pop_back();

	while (MR) {
	if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(MR)) {
	SymReaper.markLive(SymR->getSymbol());
	break;
	}
	else if (isa<VarRegion>(MR) \|\| isa<ObjCIvarRegion>(MR)) {
	if (Marked.count(MR))
	break;

	Marked.insert(MR);
	SVal X = Retrieve(state, loc::MemRegionVal(MR));

	// FIXME: We need to handle symbols nested in region definitions.
	for (symbol_iterator SI=X.symbol_begin(),SE=X.symbol_end();SI!=SE;++SI)
	SymReaper.markLive(*SI);

	if (!isa<loc::MemRegionVal>(X))
	break;

	const loc::MemRegionVal& LVD = cast<loc::MemRegionVal>(X);
	RegionRoots.push_back(LVD.getRegion());
	break;
	}
	else if (const SubRegion* R = dyn_cast<SubRegion>(MR))
	MR = R->getSuperRegion();
	else
	break;
	}
	}

	// Remove dead variable bindings.
	for (BindingsTy::iterator I=B.begin(), E=B.end(); I!=E ; ++I) {
	const MemRegion* R = I.getKey();

	if (!Marked.count(R)) {
	store = Remove(store, Loc::MakeVal(R));
	SVal X = I.getData();

	for (symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end(); SI!=SE; ++SI)
	SymReaper.maybeDead(*SI);
	}
	}

	return store;
	}

	Store BasicStoreManager::scanForIvars(Stmt B, const Decl SelfDecl, Store St) {
	for (Stmt::child_iterator CI=B->child_begin(), CE=B->child_end();
	CI != CE; ++CI) {

	if (!*CI)
	continue;

	// Check if the statement is an ivar reference. We only
	// care about self.ivar.
	if (ObjCIvarRefExpr IV = dyn_cast<ObjCIvarRefExpr>(CI)) {
	const Expr *Base = IV->getBase()->IgnoreParenCasts();
	if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Base)) {
	if (DR->getDecl() == SelfDecl) {
	const MemRegion *IVR = MRMgr.getObjCIvarRegion(IV->getDecl(),
	SelfRegion);
	SVal X = ValMgr.getRValueSymbolVal(IVR);
	St = BindInternal(St, Loc::MakeVal(IVR), X);
	}
	}
	}
	else
	St = scanForIvars(*CI, SelfDecl, St);
	}

	return St;
	}

	Store BasicStoreManager::getInitialStore() {
	// The LiveVariables information already has a compilation of all VarDecls
	// used in the function. Iterate through this set, and "symbolicate"
	// any VarDecl whose value originally comes from outside the function.
	typedef LiveVariables::AnalysisDataTy LVDataTy;
	LVDataTy& D = StateMgr.getLiveVariables().getAnalysisData();
	Store St = VBFactory.GetEmptyMap().getRoot();

	for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
	NamedDecl* ND = const_cast<NamedDecl*>(I->first);

	// Handle implicit parameters.
	if (ImplicitParamDecl* PD = dyn_cast<ImplicitParamDecl>(ND)) {
	const Decl& CD = StateMgr.getCodeDecl();
	if (const ObjCMethodDecl* MD = dyn_cast<ObjCMethodDecl>(&CD)) {
	if (MD->getSelfDecl() == PD) {
	// Create a region for "self".
	assert (SelfRegion == 0);
	SelfRegion = MRMgr.getObjCObjectRegion(MD->getClassInterface(),
	MRMgr.getHeapRegion());

	St = BindInternal(St, Loc::MakeVal(MRMgr.getVarRegion(PD)),
	Loc::MakeVal(SelfRegion));

	// Scan the method for ivar references. While this requires an
	// entire AST scan, the cost should not be high in practice.
	St = scanForIvars(MD->getBody(), PD, St);
	}
	}
	}
	else if (VarDecl* VD = dyn_cast<VarDecl>(ND)) {
	// Punt on static variables for now.
	if (VD->getStorageClass() == VarDecl::Static)
	continue;

	// Only handle simple types that we can symbolicate.
	if (!SymbolManager::canSymbolicate(VD->getType()))
	continue;

	// Initialize globals and parameters to symbolic values.
	// Initialize local variables to undefined.
	const MemRegion *R = StateMgr.getRegion(VD);
	SVal X = (VD->hasGlobalStorage() \|\| isa<ParmVarDecl>(VD) \|\|
	isa<ImplicitParamDecl>(VD))
	? ValMgr.getRValueSymbolVal(R)
	: UndefinedVal();

	St = BindInternal(St, Loc::MakeVal(R), X);
	}
	}
	return St;
	}

	Store BasicStoreManager::BindDeclInternal(Store store, const VarDecl* VD,
	SVal* InitVal) {

	BasicValueFactory& BasicVals = StateMgr.getBasicVals();

	// BasicStore does not model arrays and structs.
	if (VD->getType()->isArrayType() \|\| VD->getType()->isStructureType())
	return store;

	if (VD->hasGlobalStorage()) {
	// Handle variables with global storage: extern, static, PrivateExtern.

	// FIXME:: static variables may have an initializer, but the second time a
	// function is called those values may not be current. Currently, a function
	// will not be called more than once.

	// Static global variables should not be visited here.
	assert(!(VD->getStorageClass() == VarDecl::Static &&
	VD->isFileVarDecl()));

	// Process static variables.
	if (VD->getStorageClass() == VarDecl::Static) {
	// C99: 6.7.8 Initialization
	// If an object that has static storage duration is not initialized
	// explicitly, then:
	// —if it has pointer type, it is initialized to a null pointer;
	// —if it has arithmetic type, it is initialized to (positive or
	// unsigned) zero;
	if (!InitVal) {
	QualType T = VD->getType();
	if (Loc::IsLocType(T))
	store = BindInternal(store, getLoc(VD),
	loc::ConcreteInt(BasicVals.getValue(0, T)));
	else if (T->isIntegerType())
	store = BindInternal(store, getLoc(VD),
	nonloc::ConcreteInt(BasicVals.getValue(0, T)));
	else {
	// assert(0 && "ignore other types of variables");
	}
	} else {
	store = BindInternal(store, getLoc(VD), *InitVal);
	}
	}
	} else {
	// Process local scalar variables.
	QualType T = VD->getType();
	if (Loc::IsLocType(T) \|\| T->isIntegerType()) {
	SVal V = InitVal ? *InitVal : UndefinedVal();
	store = BindInternal(store, getLoc(VD), V);
	}
	}

	return store;
	}

	void BasicStoreManager::print(Store store, std::ostream& O,
	const char* nl, const char *sep) {

	llvm::raw_os_ostream Out(O);
	BindingsTy B = GetBindings(store);
	Out << "Variables:" << nl;

	bool isFirst = true;

	for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I) {
	if (isFirst) isFirst = false;
	else Out << nl;

	Out << ' ' << I.getKey() << " : ";
	I.getData().print(Out);
	}
	}


	void BasicStoreManager::iterBindings(Store store, BindingsHandler& f) {
	BindingsTy B = GetBindings(store);

	for (BindingsTy::iterator I=B.begin(), E=B.end(); I != E; ++I)
	f.HandleBinding(*this, store, I.getKey(), I.getData());

	}

	StoreManager::BindingsHandler::~BindingsHandler() {}