ProgramState.h revision 5f625712f622f6e57de17b6f7eec242956b993ee
12228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project//== ProgramState.h - Path-sensitive "State" for tracking values -*- C++ -*--=// 22228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// 32228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// The LLVM Compiler Infrastructure 42228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// 54f0d97057c5c640b25518358886f8c47da9fc052Jean-Michel Trivi// This file is distributed under the University of Illinois Open Source 62228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// License. See LICENSE.TXT for details. 72228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// 82228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project//===----------------------------------------------------------------------===// 92228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// 102228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// This file defines SymbolRef, ExprBindKey, and ProgramState*. 112228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// 122228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project//===----------------------------------------------------------------------===// 132228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 142228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#ifndef LLVM_CLANG_GR_VALUESTATE_H 152228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#define LLVM_CLANG_GR_VALUESTATE_H 162228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 172228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#include "clang/Basic/LLVM.h" 182228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h" 192228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h" 202228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h" 212228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 222228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#include "llvm/ADT/PointerIntPair.h" 232228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#include "llvm/ADT/FoldingSet.h" 242228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project#include "llvm/ADT/ImmutableMap.h" 252228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 262228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectnamespace llvm { 272228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectclass APSInt; 282228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectclass BumpPtrAllocator; 292228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project} 302228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 312228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectnamespace clang { 322228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectclass ASTContext; 332228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 342228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectnamespace ento { 352228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 362228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectclass ProgramStateManager; 372228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 382228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projecttypedef ConstraintManager* (*ConstraintManagerCreator)(ProgramStateManager&, 392228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SubEngine&); 402228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projecttypedef StoreManager* (*StoreManagerCreator)(ProgramStateManager&); 412228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 422228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project//===----------------------------------------------------------------------===// 432228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project// ProgramStateTrait - Traits used by the Generic Data Map of a ProgramState. 442228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project//===----------------------------------------------------------------------===// 452228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 462228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projecttemplate <typename T> struct ProgramStatePartialTrait; 472228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 482228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projecttemplate <typename T> struct ProgramStateTrait { 492228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typedef typename T::data_type data_type; 502228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project static inline void *GDMIndex() { return &T::TagInt; } 512228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project static inline void *MakeVoidPtr(data_type D) { return (void*) D; } 522228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project static inline data_type MakeData(void *const* P) { 532228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project return P ? (data_type) *P : (data_type) 0; 542228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project } 552228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project}; 562228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 572228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectclass ProgramStateManager; 582228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 592228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// \class ProgramState 602228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// ProgramState - This class encapsulates: 612228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// 622228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// 1. A mapping from expressions to values (Environment) 632228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// 2. A mapping from locations to values (Store) 642228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// 3. Constraints on symbolic values (GenericDataMap) 652228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// 662228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// Together these represent the "abstract state" of a program. 672228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// 682228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// ProgramState is intended to be used as a functional object; that is, 692228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// once it is created and made "persistent" in a FoldingSet, its 702228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project/// values will never change. 712228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectclass ProgramState : public llvm::FoldingSetNode { 722228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectpublic: 732228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; 742228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typedef llvm::ImmutableMap<void*, void*> GenericDataMap; 752228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 762228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectprivate: 772228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void operator=(const ProgramState& R) const; // Do not implement. 782228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 792228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project friend class ProgramStateManager; 802228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project friend class ExplodedGraph; 812228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project friend class ExplodedNode; 822228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 832228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ProgramStateManager *stateMgr; 842228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project Environment Env; // Maps a Stmt to its current SVal. 852228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project Store store; // Maps a location to its current value. 862228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project GenericDataMap GDM; // Custom data stored by a client of this class. 872228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project unsigned refCount; 882228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 892228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// makeWithStore - Return a ProgramState with the same values as the current 902228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// state with the exception of using the specified Store. 912228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *makeWithStore(const StoreRef &store) const; 922228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 932228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void setStore(const StoreRef &storeRef); 942228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 952228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectpublic: 962228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 972228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// This ctor is used when creating the first ProgramState object. 982228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ProgramState(ProgramStateManager *mgr, const Environment& env, 992228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project StoreRef st, GenericDataMap gdm); 1002228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1012228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Copy ctor - We must explicitly define this or else the "Next" ptr 1022228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// in FoldingSetNode will also get copied. 1032228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ProgramState(const ProgramState &RHS); 1042228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1052228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ~ProgramState(); 1062228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1072228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Return the ProgramStateManager associated with this state. 1082228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ProgramStateManager &getStateManager() const { return *stateMgr; } 1092228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1102228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Return true if this state is referenced by a persistent ExplodedNode. 1112228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project bool referencedByExplodedNode() const { return refCount > 0; } 1122228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1132228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// getEnvironment - Return the environment associated with this state. 1142228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// The environment is the mapping from expressions to values. 1152228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const Environment& getEnvironment() const { return Env; } 1162228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1172228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Return the store associated with this state. The store 1182228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// is a mapping from locations to values. 1192228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project Store getStore() const { return store; } 1202228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1212228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1222228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// getGDM - Return the generic data map associated with this state. 1232228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project GenericDataMap getGDM() const { return GDM; } 1242228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1252228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void setGDM(GenericDataMap gdm) { GDM = gdm; } 1262228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1272228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Profile - Profile the contents of a ProgramState object for use in a 1282228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// FoldingSet. Two ProgramState objects are considered equal if they 1292228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// have the same Environment, Store, and GenericDataMap. 1302228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project static void Profile(llvm::FoldingSetNodeID& ID, const ProgramState *V) { 1312228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project V->Env.Profile(ID); 1322228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ID.AddPointer(V->store); 1332228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project V->GDM.Profile(ID); 1342228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project } 1352228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1362228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Profile - Used to profile the contents of this object for inclusion 1372228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// in a FoldingSet. 1382228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void Profile(llvm::FoldingSetNodeID& ID) const { 1392228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project Profile(ID, this); 1402228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project } 1412228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1422228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project BasicValueFactory &getBasicVals() const; 1432228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SymbolManager &getSymbolManager() const; 1442228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1452228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project //==---------------------------------------------------------------------==// 1462228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // Constraints on values. 1472228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project //==---------------------------------------------------------------------==// 1482228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // 1492228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // Each ProgramState records constraints on symbolic values. These constraints 1502228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // are managed using the ConstraintManager associated with a ProgramStateManager. 1512228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // As constraints gradually accrue on symbolic values, added constraints 1522228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // may conflict and indicate that a state is infeasible (as no real values 1532228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // could satisfy all the constraints). This is the principal mechanism 1542228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // for modeling path-sensitivity in ExprEngine/ProgramState. 1552228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // 1562228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // Various "assume" methods form the interface for adding constraints to 1572228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // symbolic values. A call to 'assume' indicates an assumption being placed 1582228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // on one or symbolic values. 'assume' methods take the following inputs: 1592228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // 1602228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // (1) A ProgramState object representing the current state. 1612228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // 1622228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // (2) The assumed constraint (which is specific to a given "assume" method). 1632228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // 1642228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // (3) A binary value "Assumption" that indicates whether the constraint is 1652228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // assumed to be true or false. 1662228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // 1672228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // The output of "assume*" is a new ProgramState object with the added constraints. 1682228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // If no new state is feasible, NULL is returned. 1692228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // 1702228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1712228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *assume(DefinedOrUnknownSVal cond, bool assumption) const; 1722228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1732228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// This method assumes both "true" and "false" for 'cond', and 1742228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// returns both corresponding states. It's shorthand for doing 1752228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// 'assume' twice. 1762228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project std::pair<const ProgramState*, const ProgramState*> 1772228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project assume(DefinedOrUnknownSVal cond) const; 1782228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1792228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *assumeInBound(DefinedOrUnknownSVal idx, 1802228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project DefinedOrUnknownSVal upperBound, 1812228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project bool assumption) const; 1822228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1832228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Utility method for getting regions. 1842228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; 1852228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1862228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project //==---------------------------------------------------------------------==// 1872228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // Binding and retrieving values to/from the environment and symbolic store. 1882228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project //==---------------------------------------------------------------------==// 1892228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1902228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// BindCompoundLiteral - Return the state that has the bindings currently 1912228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// in this state plus the bindings for the CompoundLiteral. 1922228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *bindCompoundLiteral(const CompoundLiteralExpr *CL, 1932228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const LocationContext *LC, 1942228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal V) const; 1952228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 1962228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Create a new state by binding the value 'V' to the statement 'S' in the 1972228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// state's environment. 1982228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *BindExpr(const Stmt *S, SVal V, bool Invalidate = true) const; 1992228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2002228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Create a new state by binding the value 'V' and location 'locaton' to the 2012228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// statement 'S' in the state's environment. 2022228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *bindExprAndLocation(const Stmt *S, SVal location, SVal V) 2032228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const; 2042228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2052228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *bindDecl(const VarRegion *VR, SVal V) const; 2062228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2072228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *bindDeclWithNoInit(const VarRegion *VR) const; 2082228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2092228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *bindLoc(Loc location, SVal V) const; 2102228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2112228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *bindLoc(SVal location, SVal V) const; 2122228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2132228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *bindDefault(SVal loc, SVal V) const; 2142228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2152228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *unbindLoc(Loc LV) const; 2162228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2172228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// invalidateRegions - Returns the state with bindings for the given regions 2182228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// cleared from the store. The regions are provided as a continuous array 2192228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// from Begin to End. Optionally invalidates global regions as well. 2202228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *invalidateRegions(ArrayRef<const MemRegion *> Regions, 2212228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const Expr *E, unsigned BlockCount, 2222228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project StoreManager::InvalidatedSymbols *IS = 0, 2232228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project bool invalidateGlobals = false) const; 2242228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2252228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// enterStackFrame - Returns the state for entry to the given stack frame, 2262228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// preserving the current state. 2272228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *enterStackFrame(const StackFrameContext *frame) const; 2282228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2292228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Get the lvalue for a variable reference. 2302228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project Loc getLValue(const VarDecl *D, const LocationContext *LC) const; 2312228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2322228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Get the lvalue for a StringLiteral. 2332228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project Loc getLValue(const StringLiteral *literal) const; 2342228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2352228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project Loc getLValue(const CompoundLiteralExpr *literal, 2362228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const LocationContext *LC) const; 2372228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2382228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Get the lvalue for an ivar reference. 2392228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getLValue(const ObjCIvarDecl *decl, SVal base) const; 2402228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2412228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Get the lvalue for a field reference. 2422228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getLValue(const FieldDecl *decl, SVal Base) const; 2432228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2442228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Get the lvalue for an array index. 2452228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; 2462228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2472228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const llvm::APSInt *getSymVal(SymbolRef sym) const; 2482228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2492228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Returns the SVal bound to the statement 'S' in the state's environment. 2502228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getSVal(const Stmt *S, bool useOnlyDirectBindings = false) const; 2512228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2522228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getSValAsScalarOrLoc(const Stmt *Ex) const; 2532228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2542228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getSVal(Loc LV, QualType T = QualType()) const; 2552228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2562228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Returns the "raw" SVal bound to LV before any value simplfication. 2572228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getRawSVal(Loc LV, QualType T= QualType()) const; 2582228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2592228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getSVal(const MemRegion* R) const; 2602228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2612228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SVal getSValAsScalarOrLoc(const MemRegion *R) const; 2622228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2632228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// \brief Visits the symbols reachable from the given SVal using the provided 2642228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// SymbolVisitor. 2652228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// 2662228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// This is a convenience API. Consider using ScanReachableSymbols class 2672228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// directly when making multiple scans on the same state with the same 2682228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// visitor to avoid repeated initialization cost. 2692228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// \sa ScanReachableSymbols 2702228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project bool scanReachableSymbols(SVal val, SymbolVisitor& visitor) const; 2712228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2722228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// \brief Visits the symbols reachable from the SVals in the given range 2732228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// using the provided SymbolVisitor. 2742228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project bool scanReachableSymbols(const SVal *I, const SVal *E, 2752228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SymbolVisitor &visitor) const; 2762228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2772228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// \brief Visits the symbols reachable from the regions in the given 2782228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// MemRegions range using the provided SymbolVisitor. 2792228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project bool scanReachableSymbols(const MemRegion * const *I, 2802228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const MemRegion * const *E, 2812228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project SymbolVisitor &visitor) const; 2822228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2832228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template <typename CB> CB scanReachableSymbols(SVal val) const; 2842228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template <typename CB> CB scanReachableSymbols(const SVal *beg, 2852228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const SVal *end) const; 2862228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2872228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template <typename CB> CB 2882228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project scanReachableSymbols(const MemRegion * const *beg, 2892228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const MemRegion * const *end) const; 2902228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2912228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project //==---------------------------------------------------------------------==// 2922228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // Accessing the Generic Data Map (GDM). 2932228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project //==---------------------------------------------------------------------==// 2942228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2952228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void *const* FindGDM(void *K) const; 2962228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 2972228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template<typename T> 2982228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *add(typename ProgramStateTrait<T>::key_type K) const; 2992228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3002228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template <typename T> 3012228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typename ProgramStateTrait<T>::data_type 3022228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project get() const { 3032228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project return ProgramStateTrait<T>::MakeData(FindGDM(ProgramStateTrait<T>::GDMIndex())); 3042228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project } 3052228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3062228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template<typename T> 3072228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typename ProgramStateTrait<T>::lookup_type 3082228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project get(typename ProgramStateTrait<T>::key_type key) const { 3092228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); 3102228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project return ProgramStateTrait<T>::Lookup(ProgramStateTrait<T>::MakeData(d), key); 3112228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project } 3122228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3132228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template <typename T> 3142228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typename ProgramStateTrait<T>::context_type get_context() const; 3152228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3162228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3172228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template<typename T> 3182228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *remove(typename ProgramStateTrait<T>::key_type K) const; 3192228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3202228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template<typename T> 3212228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *remove(typename ProgramStateTrait<T>::key_type K, 3222228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typename ProgramStateTrait<T>::context_type C) const; 3232228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template <typename T> 3242228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *remove() const; 3252228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3262228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template<typename T> 3272228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *set(typename ProgramStateTrait<T>::data_type D) const; 3282228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3292228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template<typename T> 3302228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *set(typename ProgramStateTrait<T>::key_type K, 3312228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typename ProgramStateTrait<T>::value_type E) const; 3322228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3332228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template<typename T> 3342228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState *set(typename ProgramStateTrait<T>::key_type K, 3352228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typename ProgramStateTrait<T>::value_type E, 3362228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typename ProgramStateTrait<T>::context_type C) const; 3372228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3382228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project template<typename T> 3392228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project bool contains(typename ProgramStateTrait<T>::key_type key) const { 3402228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void *const* d = FindGDM(ProgramStateTrait<T>::GDMIndex()); 3412228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project return ProgramStateTrait<T>::Contains(ProgramStateTrait<T>::MakeData(d), key); 3422228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project } 3432228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3442228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project // Pretty-printing. 3452228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void print(raw_ostream &Out, CFG &C, const char *nl = "\n", 3462228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const char *sep = "") const; 3472228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3482228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void printStdErr(CFG &C) const; 3492228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3502228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void printDOT(raw_ostream &Out, CFG &C) const; 3512228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3522228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectprivate: 3532228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Increments the number of times this state is referenced by ExplodeNodes. 3542228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void incrementReferenceCount() { ++refCount; } 3552228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3562228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project /// Decrement the number of times this state is referenced by ExplodeNodes. 3572228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project void decrementReferenceCount() { 3582228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project assert(refCount > 0); 3592228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project --refCount; 3602228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project } 3612228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3622228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const ProgramState * 3632228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, 3642228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project const Expr *E, unsigned BlockCount, 3652228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project StoreManager::InvalidatedSymbols &IS, 3662228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project bool invalidateGlobals) const; 3672228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project}; 3682228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3692228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectclass ProgramStateSet { 3702228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typedef llvm::SmallPtrSet<const ProgramState*,5> ImplTy; 3712228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ImplTy Impl; 3722228e360595641dd906bf1773307f43d304f5b2The Android Open Source Projectpublic: 3732228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ProgramStateSet() {} 3742228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3752228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project inline void Add(const ProgramState *St) { 3762228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project Impl.insert(St); 3775016eb7f6582fbb2d72d79be782325a12df08864Jean-Michel Trivi } 3782228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3792228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project typedef ImplTy::const_iterator iterator; 3802228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3812228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project inline unsigned size() const { return Impl.size(); } 3825016eb7f6582fbb2d72d79be782325a12df08864Jean-Michel Trivi inline bool empty() const { return Impl.empty(); } 3832228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3842228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project inline iterator begin() const { return Impl.begin(); } 3852228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project inline iterator end() const { return Impl.end(); } 3862228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project 3872228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project class AutoPopulate { 3882228e360595641dd906bf1773307f43d304f5b2The Android Open Source Project ProgramStateSet &S; 389 unsigned StartSize; 390 const ProgramState *St; 391 public: 392 AutoPopulate(ProgramStateSet &s, const ProgramState *st) 393 : S(s), StartSize(S.size()), St(st) {} 394 395 ~AutoPopulate() { 396 if (StartSize == S.size()) 397 S.Add(St); 398 } 399 }; 400}; 401 402//===----------------------------------------------------------------------===// 403// ProgramStateManager - Factory object for ProgramStates. 404//===----------------------------------------------------------------------===// 405 406class ProgramStateManager { 407 friend class ProgramState; 408private: 409 /// Eng - The SubEngine that owns this state manager. 410 SubEngine *Eng; /* Can be null. */ 411 412 EnvironmentManager EnvMgr; 413 llvm::OwningPtr<StoreManager> StoreMgr; 414 llvm::OwningPtr<ConstraintManager> ConstraintMgr; 415 416 ProgramState::GenericDataMap::Factory GDMFactory; 417 418 typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy; 419 GDMContextsTy GDMContexts; 420 421 /// StateSet - FoldingSet containing all the states created for analyzing 422 /// a particular function. This is used to unique states. 423 llvm::FoldingSet<ProgramState> StateSet; 424 425 /// Object that manages the data for all created SVals. 426 llvm::OwningPtr<SValBuilder> svalBuilder; 427 428 /// A BumpPtrAllocator to allocate states. 429 llvm::BumpPtrAllocator &Alloc; 430 431 /// A vector of recently allocated ProgramStates that can potentially be 432 /// reused. 433 std::vector<ProgramState *> recentlyAllocatedStates; 434 435 /// A vector of ProgramStates that we can reuse. 436 std::vector<ProgramState *> freeStates; 437 438public: 439 ProgramStateManager(ASTContext &Ctx, 440 StoreManagerCreator CreateStoreManager, 441 ConstraintManagerCreator CreateConstraintManager, 442 llvm::BumpPtrAllocator& alloc, 443 SubEngine &subeng) 444 : Eng(&subeng), 445 EnvMgr(alloc), 446 GDMFactory(alloc), 447 svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), 448 Alloc(alloc) { 449 StoreMgr.reset((*CreateStoreManager)(*this)); 450 ConstraintMgr.reset((*CreateConstraintManager)(*this, subeng)); 451 } 452 453 ProgramStateManager(ASTContext &Ctx, 454 StoreManagerCreator CreateStoreManager, 455 ConstraintManager* ConstraintManagerPtr, 456 llvm::BumpPtrAllocator& alloc) 457 : Eng(0), 458 EnvMgr(alloc), 459 GDMFactory(alloc), 460 svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), 461 Alloc(alloc) { 462 StoreMgr.reset((*CreateStoreManager)(*this)); 463 ConstraintMgr.reset(ConstraintManagerPtr); 464 } 465 466 ~ProgramStateManager(); 467 468 const ProgramState *getInitialState(const LocationContext *InitLoc); 469 470 ASTContext &getContext() { return svalBuilder->getContext(); } 471 const ASTContext &getContext() const { return svalBuilder->getContext(); } 472 473 BasicValueFactory &getBasicVals() { 474 return svalBuilder->getBasicValueFactory(); 475 } 476 const BasicValueFactory& getBasicVals() const { 477 return svalBuilder->getBasicValueFactory(); 478 } 479 480 SValBuilder &getSValBuilder() { 481 return *svalBuilder; 482 } 483 484 SymbolManager &getSymbolManager() { 485 return svalBuilder->getSymbolManager(); 486 } 487 const SymbolManager &getSymbolManager() const { 488 return svalBuilder->getSymbolManager(); 489 } 490 491 llvm::BumpPtrAllocator& getAllocator() { return Alloc; } 492 493 MemRegionManager& getRegionManager() { 494 return svalBuilder->getRegionManager(); 495 } 496 const MemRegionManager& getRegionManager() const { 497 return svalBuilder->getRegionManager(); 498 } 499 500 StoreManager& getStoreManager() { return *StoreMgr; } 501 ConstraintManager& getConstraintManager() { return *ConstraintMgr; } 502 SubEngine* getOwningEngine() { return Eng; } 503 504 const ProgramState *removeDeadBindings(const ProgramState *St, 505 const StackFrameContext *LCtx, 506 SymbolReaper& SymReaper); 507 508 /// Marshal a new state for the callee in another translation unit. 509 /// 'state' is owned by the caller's engine. 510 const ProgramState *MarshalState(const ProgramState *state, const StackFrameContext *L); 511 512public: 513 514 SVal ArrayToPointer(Loc Array) { 515 return StoreMgr->ArrayToPointer(Array); 516 } 517 518 // Methods that manipulate the GDM. 519 const ProgramState *addGDM(const ProgramState *St, void *Key, void *Data); 520 const ProgramState *removeGDM(const ProgramState *state, void *Key); 521 522 // Methods that query & manipulate the Store. 523 524 void iterBindings(const ProgramState *state, StoreManager::BindingsHandler& F) { 525 StoreMgr->iterBindings(state->getStore(), F); 526 } 527 528 const ProgramState *getPersistentState(ProgramState &Impl); 529 const ProgramState *getPersistentStateWithGDM(const ProgramState *FromState, 530 const ProgramState *GDMState); 531 532 bool haveEqualEnvironments(const ProgramState * S1, const ProgramState * S2) { 533 return S1->Env == S2->Env; 534 } 535 536 bool haveEqualStores(const ProgramState * S1, const ProgramState * S2) { 537 return S1->store == S2->store; 538 } 539 540 /// Periodically called by ExprEngine to recycle ProgramStates that were 541 /// created but never used for creating an ExplodedNode. 542 void recycleUnusedStates(); 543 544 //==---------------------------------------------------------------------==// 545 // Generic Data Map methods. 546 //==---------------------------------------------------------------------==// 547 // 548 // ProgramStateManager and ProgramState support a "generic data map" that allows 549 // different clients of ProgramState objects to embed arbitrary data within a 550 // ProgramState object. The generic data map is essentially an immutable map 551 // from a "tag" (that acts as the "key" for a client) and opaque values. 552 // Tags/keys and values are simply void* values. The typical way that clients 553 // generate unique tags are by taking the address of a static variable. 554 // Clients are responsible for ensuring that data values referred to by a 555 // the data pointer are immutable (and thus are essentially purely functional 556 // data). 557 // 558 // The templated methods below use the ProgramStateTrait<T> class 559 // to resolve keys into the GDM and to return data values to clients. 560 // 561 562 // Trait based GDM dispatch. 563 template <typename T> 564 const ProgramState *set(const ProgramState *st, typename ProgramStateTrait<T>::data_type D) { 565 return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 566 ProgramStateTrait<T>::MakeVoidPtr(D)); 567 } 568 569 template<typename T> 570 const ProgramState *set(const ProgramState *st, 571 typename ProgramStateTrait<T>::key_type K, 572 typename ProgramStateTrait<T>::value_type V, 573 typename ProgramStateTrait<T>::context_type C) { 574 575 return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 576 ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Set(st->get<T>(), K, V, C))); 577 } 578 579 template <typename T> 580 const ProgramState *add(const ProgramState *st, 581 typename ProgramStateTrait<T>::key_type K, 582 typename ProgramStateTrait<T>::context_type C) { 583 return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 584 ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Add(st->get<T>(), K, C))); 585 } 586 587 template <typename T> 588 const ProgramState *remove(const ProgramState *st, 589 typename ProgramStateTrait<T>::key_type K, 590 typename ProgramStateTrait<T>::context_type C) { 591 592 return addGDM(st, ProgramStateTrait<T>::GDMIndex(), 593 ProgramStateTrait<T>::MakeVoidPtr(ProgramStateTrait<T>::Remove(st->get<T>(), K, C))); 594 } 595 596 template <typename T> 597 const ProgramState *remove(const ProgramState *st) { 598 return removeGDM(st, ProgramStateTrait<T>::GDMIndex()); 599 } 600 601 void *FindGDMContext(void *index, 602 void *(*CreateContext)(llvm::BumpPtrAllocator&), 603 void (*DeleteContext)(void*)); 604 605 template <typename T> 606 typename ProgramStateTrait<T>::context_type get_context() { 607 void *p = FindGDMContext(ProgramStateTrait<T>::GDMIndex(), 608 ProgramStateTrait<T>::CreateContext, 609 ProgramStateTrait<T>::DeleteContext); 610 611 return ProgramStateTrait<T>::MakeContext(p); 612 } 613 614 const llvm::APSInt* getSymVal(const ProgramState *St, SymbolRef sym) { 615 return ConstraintMgr->getSymVal(St, sym); 616 } 617 618 void EndPath(const ProgramState *St) { 619 ConstraintMgr->EndPath(St); 620 } 621}; 622 623 624//===----------------------------------------------------------------------===// 625// Out-of-line method definitions for ProgramState. 626//===----------------------------------------------------------------------===// 627 628inline const VarRegion* ProgramState::getRegion(const VarDecl *D, 629 const LocationContext *LC) const { 630 return getStateManager().getRegionManager().getVarRegion(D, LC); 631} 632 633inline const ProgramState *ProgramState::assume(DefinedOrUnknownSVal Cond, 634 bool Assumption) const { 635 if (Cond.isUnknown()) 636 return this; 637 638 return getStateManager().ConstraintMgr->assume(this, cast<DefinedSVal>(Cond), 639 Assumption); 640} 641 642inline std::pair<const ProgramState*, const ProgramState*> 643ProgramState::assume(DefinedOrUnknownSVal Cond) const { 644 if (Cond.isUnknown()) 645 return std::make_pair(this, this); 646 647 return getStateManager().ConstraintMgr->assumeDual(this, 648 cast<DefinedSVal>(Cond)); 649} 650 651inline const ProgramState *ProgramState::bindLoc(SVal LV, SVal V) const { 652 return !isa<Loc>(LV) ? this : bindLoc(cast<Loc>(LV), V); 653} 654 655inline Loc ProgramState::getLValue(const VarDecl *VD, 656 const LocationContext *LC) const { 657 return getStateManager().StoreMgr->getLValueVar(VD, LC); 658} 659 660inline Loc ProgramState::getLValue(const StringLiteral *literal) const { 661 return getStateManager().StoreMgr->getLValueString(literal); 662} 663 664inline Loc ProgramState::getLValue(const CompoundLiteralExpr *literal, 665 const LocationContext *LC) const { 666 return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC); 667} 668 669inline SVal ProgramState::getLValue(const ObjCIvarDecl *D, SVal Base) const { 670 return getStateManager().StoreMgr->getLValueIvar(D, Base); 671} 672 673inline SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const { 674 return getStateManager().StoreMgr->getLValueField(D, Base); 675} 676 677inline SVal ProgramState::getLValue(QualType ElementType, SVal Idx, SVal Base) const{ 678 if (NonLoc *N = dyn_cast<NonLoc>(&Idx)) 679 return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base); 680 return UnknownVal(); 681} 682 683inline const llvm::APSInt *ProgramState::getSymVal(SymbolRef sym) const { 684 return getStateManager().getSymVal(this, sym); 685} 686 687inline SVal ProgramState::getSVal(const Stmt *Ex, bool useOnlyDirectBindings) const{ 688 return Env.getSVal(Ex, *getStateManager().svalBuilder, 689 useOnlyDirectBindings); 690} 691 692inline SVal ProgramState::getSValAsScalarOrLoc(const Stmt *S) const { 693 if (const Expr *Ex = dyn_cast<Expr>(S)) { 694 QualType T = Ex->getType(); 695 if (Ex->isLValue() || Loc::isLocType(T) || T->isIntegerType()) 696 return getSVal(S); 697 } 698 699 return UnknownVal(); 700} 701 702inline SVal ProgramState::getRawSVal(Loc LV, QualType T) const { 703 return getStateManager().StoreMgr->Retrieve(getStore(), LV, T); 704} 705 706inline SVal ProgramState::getSVal(const MemRegion* R) const { 707 return getStateManager().StoreMgr->Retrieve(getStore(), loc::MemRegionVal(R)); 708} 709 710inline BasicValueFactory &ProgramState::getBasicVals() const { 711 return getStateManager().getBasicVals(); 712} 713 714inline SymbolManager &ProgramState::getSymbolManager() const { 715 return getStateManager().getSymbolManager(); 716} 717 718template<typename T> 719const ProgramState *ProgramState::add(typename ProgramStateTrait<T>::key_type K) const { 720 return getStateManager().add<T>(this, K, get_context<T>()); 721} 722 723template <typename T> 724typename ProgramStateTrait<T>::context_type ProgramState::get_context() const { 725 return getStateManager().get_context<T>(); 726} 727 728template<typename T> 729const ProgramState *ProgramState::remove(typename ProgramStateTrait<T>::key_type K) const { 730 return getStateManager().remove<T>(this, K, get_context<T>()); 731} 732 733template<typename T> 734const ProgramState *ProgramState::remove(typename ProgramStateTrait<T>::key_type K, 735 typename ProgramStateTrait<T>::context_type C) const { 736 return getStateManager().remove<T>(this, K, C); 737} 738 739template <typename T> 740const ProgramState *ProgramState::remove() const { 741 return getStateManager().remove<T>(this); 742} 743 744template<typename T> 745const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::data_type D) const { 746 return getStateManager().set<T>(this, D); 747} 748 749template<typename T> 750const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::key_type K, 751 typename ProgramStateTrait<T>::value_type E) const { 752 return getStateManager().set<T>(this, K, E, get_context<T>()); 753} 754 755template<typename T> 756const ProgramState *ProgramState::set(typename ProgramStateTrait<T>::key_type K, 757 typename ProgramStateTrait<T>::value_type E, 758 typename ProgramStateTrait<T>::context_type C) const { 759 return getStateManager().set<T>(this, K, E, C); 760} 761 762template <typename CB> 763CB ProgramState::scanReachableSymbols(SVal val) const { 764 CB cb(this); 765 scanReachableSymbols(val, cb); 766 return cb; 767} 768 769template <typename CB> 770CB ProgramState::scanReachableSymbols(const SVal *beg, const SVal *end) const { 771 CB cb(this); 772 scanReachableSymbols(beg, end, cb); 773 return cb; 774} 775 776template <typename CB> 777CB ProgramState::scanReachableSymbols(const MemRegion * const *beg, 778 const MemRegion * const *end) const { 779 CB cb(this); 780 scanReachableSymbols(beg, end, cb); 781 return cb; 782} 783 784/// \class ScanReachableSymbols 785/// A Utility class that allows to visit the reachable symbols using a custom 786/// SymbolVisitor. 787class ScanReachableSymbols : public SubRegionMap::Visitor { 788 typedef llvm::DenseMap<const void*, unsigned> VisitedItems; 789 790 VisitedItems visited; 791 const ProgramState *state; 792 SymbolVisitor &visitor; 793 llvm::OwningPtr<SubRegionMap> SRM; 794public: 795 796 ScanReachableSymbols(const ProgramState *st, SymbolVisitor& v) 797 : state(st), visitor(v) {} 798 799 bool scan(nonloc::CompoundVal val); 800 bool scan(SVal val); 801 bool scan(const MemRegion *R); 802 bool scan(const SymExpr *sym); 803 804 // From SubRegionMap::Visitor. 805 bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) { 806 return scan(SubRegion); 807 } 808}; 809 810} // end GR namespace 811 812} // end clang namespace 813 814#endif 815