ProgramState.cpp revision 99ba9e3bd70671f3441fb974895f226a83ce0e66
12fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--= 22fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// 32fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// The LLVM Compiler Infrastructure 42fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// 52fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// This file is distributed under the University of Illinois Open Source 62fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// License. See LICENSE.TXT for details. 72fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// 82fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 92fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// 102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// This file implements ProgramState and ProgramStateManager. 112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// 122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "clang/Analysis/CFG.h" 152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 18ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h" 192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "llvm/Support/raw_ostream.h" 202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekusing namespace clang; 222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekusing namespace ento; 232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// Give the vtable for ConstraintManager somewhere to live. 252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// FIXME: Move this elsewhere. 262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekConstraintManager::~ConstraintManager() {} 272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreRef st, GenericDataMap gdm) 302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek : stateMgr(mgr), 312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Env(env), 322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store(st.getStore()), 332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDM(gdm), 342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek refCount(0) { 352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(store); 362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::ProgramState(const ProgramState &RHS) 392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek : llvm::FoldingSetNode(), 402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr(RHS.stateMgr), 412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Env(RHS.Env), 422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store(RHS.store), 432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDM(RHS.GDM), 442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek refCount(0) { 452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(store); 462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::~ProgramState() { 492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (store) 502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().decrementReferenceCount(store); 512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramStateManager::~ProgramStateManager() { 542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek I!=E; ++I) 562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek I->second.second(I->second.first); 572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState* 602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramStateManager::removeDeadBindings(const ProgramState *state, 612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StackFrameContext *LCtx, 622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolReaper& SymReaper) { 632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This code essentially performs a "mark-and-sweep" of the VariableBindings. 652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // The roots are any Block-level exprs and Decls that our liveness algorithm 662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // tells us are live. We then see what Decls they may reference, and keep 672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // those around. This code more than likely can be made faster, and the 682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // frequency of which this method is called should be experimented with 692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // for optimum performance. 702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewState = *state; 712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Clean up the store. 752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymReaper); 772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.setStore(newStore); 782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymReaper.setReapedStore(newStore); 792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewState); 812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramStateManager::MarshalState(const ProgramState *state, 842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StackFrameContext *InitLoc) { 852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // make up an empty state for now. 862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState State(this, 872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek EnvMgr.getInitialEnvironment(), 882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreMgr->getInitialStore(InitLoc), 892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDMFactory.getEmptyMap()); 902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(State); 922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::bindCompoundLiteral(const CompoundLiteralExpr *CL, 952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const LocationContext *LC, 962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal V) const { 972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getStateManager().StoreMgr->BindCompoundLiteral(getStore(), CL, LC, V); 992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::bindDecl(const VarRegion* VR, SVal IVal) const { 1032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 1042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getStateManager().StoreMgr->BindDecl(getStore(), VR, IVal); 1052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::bindDeclWithNoInit(const VarRegion* VR) const { 1092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 1102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getStateManager().StoreMgr->BindDeclWithNoInit(getStore(), VR); 1112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::bindLoc(Loc LV, SVal V) const { 1152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 1162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const ProgramState *newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 1172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek LV, V)); 1182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion *MR = LV.getAsRegion(); 1192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (MR && Mgr.getOwningEngine()) 1202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return Mgr.getOwningEngine()->processRegionChange(newState, MR); 1212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return newState; 1232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::bindDefault(SVal loc, SVal V) const { 1262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 1272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion(); 1282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V); 1292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const ProgramState *new_state = makeWithStore(newStore); 1302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return Mgr.getOwningEngine() ? 1312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Mgr.getOwningEngine()->processRegionChange(new_state, R) : 1322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek new_state; 1332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 135537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Roseconst ProgramState * 136537716ad8dd10f984b6cfe6985afade1185c5e3cJordy RoseProgramState::invalidateRegions(ArrayRef<const MemRegion *> Regions, 137537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose const Expr *E, unsigned Count, 138537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose StoreManager::InvalidatedSymbols *IS, 139537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose bool invalidateGlobals) const { 1402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!IS) { 1412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreManager::InvalidatedSymbols invalidated; 142537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose return invalidateRegionsImpl(Regions, E, Count, 143537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose invalidated, invalidateGlobals); 1442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 145537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose return invalidateRegionsImpl(Regions, E, Count, *IS, invalidateGlobals); 1462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState * 149537716ad8dd10f984b6cfe6985afade1185c5e3cJordy RoseProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, 150537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose const Expr *E, unsigned Count, 151537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose StoreManager::InvalidatedSymbols &IS, 152537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose bool invalidateGlobals) const { 1532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 1542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SubEngine* Eng = Mgr.getOwningEngine(); 1552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (Eng && Eng->wantsRegionChangeUpdate(this)) { 157537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose StoreManager::InvalidatedRegions Invalidated; 1582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore 159537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose = Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, IS, 160537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose invalidateGlobals, &Invalidated); 1612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const ProgramState *newState = makeWithStore(newStore); 162537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose return Eng->processRegionChanges(newState, &IS, Regions, Invalidated); 1632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 1642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 166537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, IS, 1672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek invalidateGlobals, NULL); 1682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::unbindLoc(Loc LV) const { 1722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek assert(!isa<loc::MemRegionVal>(LV) && "Use invalidateRegion instead."); 1732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Store OldStore = getStore(); 1752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = getStateManager().StoreMgr->Remove(OldStore, LV); 1762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newStore.getStore() == OldStore) 1782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 1792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::enterStackFrame(const StackFrameContext *frame) const { 1842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &new_store = 1852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getStateManager().StoreMgr->enterStackFrame(this, frame); 1862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(new_store); 1872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekSVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 1902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // We only want to do fetches from regions that we can actually bind 1912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // values. For example, SymbolicRegions of type 'id<...>' cannot 1922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // have direct bindings (but their can be bindings on their subregions). 1932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!R->isBoundable()) 1942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return UnknownVal(); 1952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 1972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek QualType T = TR->getValueType(); 1982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (Loc::isLocType(T) || T->isIntegerType()) 1992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getSVal(R); 2002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return UnknownVal(); 2032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekSVal ProgramState::getSVal(Loc location, QualType T) const { 2062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal V = getRawSVal(cast<Loc>(location), T); 2072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If 'V' is a symbolic value that is *perfectly* constrained to 2092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // be a constant value, use that value instead to lessen the burden 2102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // on later analysis stages (so we have less symbolic values to reason 2112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // about). 2122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!T.isNull()) { 2132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (SymbolRef sym = V.getAsSymbol()) { 2142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const llvm::APSInt *Int = getSymVal(sym)) { 2152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: Because we don't correctly model (yet) sign-extension 2162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // and truncation of symbolic values, we need to convert 2172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // the integer value to the correct signedness and bitwidth. 2182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This shows up in the following: 2202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // char foo(); 2222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // unsigned x = foo(); 2232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // if (x == 54) 2242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // ... 2252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // The symbolic value stored to 'x' is actually the conjured 2272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // symbol for the call to foo(); the type of that symbol is 'char', 2282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // not unsigned. 2292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 2302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isa<Loc>(V)) 2322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return loc::ConcreteInt(NewV); 2332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek else 2342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return nonloc::ConcreteInt(NewV); 2352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return V; 2402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::BindExpr(const Stmt *S, SVal V, bool Invalidate) const{ 2432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Environment NewEnv = getStateManager().EnvMgr.bindExpr(Env, S, V, 2442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Invalidate); 2452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (NewEnv == Env) 2462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *this; 2492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.Env = NewEnv; 2502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getStateManager().getPersistentState(NewSt); 2512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::bindExprAndLocation(const Stmt *S, SVal location, 2542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal V) const { 2552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Environment NewEnv = 2562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getStateManager().EnvMgr.bindExprAndLocation(Env, S, location, V); 2572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (NewEnv == Env) 2592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *this; 2622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.Env = NewEnv; 2632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getStateManager().getPersistentState(NewSt); 2642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 2672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek DefinedOrUnknownSVal UpperBound, 2682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek bool Assumption) const { 2692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (Idx.isUnknown() || UpperBound.isUnknown()) 2702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Build an expression for 0 <= Idx < UpperBound. 2732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 2742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: This should probably be part of SValBuilder. 2752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &SM = getStateManager(); 2762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SValBuilder &svalBuilder = SM.getSValBuilder(); 2772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ASTContext &Ctx = svalBuilder.getContext(); 2782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Get the offset: the minimum value of the array index type. 2802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 2812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: This should be using ValueManager::ArrayindexTy...somehow. 2822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek QualType indexTy = Ctx.IntTy; 2832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 2842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Adjust the index. 2862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 2872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek cast<NonLoc>(Idx), Min, indexTy); 2882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newIdx.isUnknownOrUndef()) 2892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Adjust the upper bound. 2922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal newBound = 2932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek svalBuilder.evalBinOpNN(this, BO_Add, cast<NonLoc>(UpperBound), 2942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Min, indexTy); 2952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newBound.isUnknownOrUndef()) 2972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Build the actual comparison. 3002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, 3012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek cast<NonLoc>(newIdx), cast<NonLoc>(newBound), 3022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Ctx.IntTy); 3032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (inBound.isUnknownOrUndef()) 3042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Finally, let the constraint manager take care of it. 3072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ConstraintManager &CM = SM.getConstraintManager(); 3082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return CM.assume(this, cast<DefinedSVal>(inBound), Assumption); 3092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 3122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState State(this, 3132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek EnvMgr.getInitialEnvironment(), 3142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreMgr->getInitialStore(InitLoc), 3152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDMFactory.getEmptyMap()); 3162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(State); 3182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid ProgramStateManager::recycleUnusedStates() { 3212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (std::vector<ProgramState*>::iterator i = recentlyAllocatedStates.begin(), 3222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek e = recentlyAllocatedStates.end(); i != e; ++i) { 3232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState *state = *i; 3242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (state->referencedByExplodedNode()) 3252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek continue; 3262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StateSet.RemoveNode(state); 3272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek freeStates.push_back(state); 3282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek state->~ProgramState(); 3292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 3302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek recentlyAllocatedStates.clear(); 3312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramStateManager::getPersistentStateWithGDM( 3342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const ProgramState *FromState, 3352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const ProgramState *GDMState) { 3362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewState = *FromState; 3372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.GDM = GDMState->GDM; 3382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewState); 3392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramStateManager::getPersistentState(ProgramState &State) { 3422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek llvm::FoldingSetNodeID ID; 3442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek State.Profile(ID); 3452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void *InsertPos; 3462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 3482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return I; 3492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState *newState = 0; 3512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!freeStates.empty()) { 3522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek newState = freeStates.back(); 3532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek freeStates.pop_back(); 3542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 3552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek else { 3562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 3572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 3582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek new (newState) ProgramState(State); 3592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StateSet.InsertNode(newState, InsertPos); 3602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek recentlyAllocatedStates.push_back(newState); 3612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return newState; 3622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramState::makeWithStore(const StoreRef &store) const { 3652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *this; 3662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.setStore(store); 3672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getStateManager().getPersistentState(NewSt); 3682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid ProgramState::setStore(const StoreRef &newStore) { 3712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Store newStoreStore = newStore.getStore(); 3722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newStoreStore) 3732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 3742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (store) 3752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().decrementReferenceCount(store); 3762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store = newStoreStore; 3772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 3802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// State pretty-printing. 3812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 3822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekstatic bool IsEnvLoc(const Stmt *S) { 3842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: This is a layering violation. Should be in environment. 3852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return (bool) (((uintptr_t) S) & 0x1); 3862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 388d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaksvoid ProgramState::print(raw_ostream &Out, CFG *C, 389dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose const char *NL, const char *Sep) const { 3902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Print the store. 3912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 392dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getStoreManager().print(getStore(), Out, NL, Sep); 3932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek bool isFirst = true; 3942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: All environment printing should be moved inside Environment. 396d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks if (C) { 397d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks // Print Subexpression bindings. 398d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 399d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks if (C->isBlkExpr(I.getKey()) || IsEnvLoc(I.getKey())) 400d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks continue; 401d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks 402d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks if (isFirst) { 403d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << NL << NL << "Sub-Expressions:" << NL; 404d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks isFirst = false; 405d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks } else { 406d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << NL; 407d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks } 4082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 409d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << " (" << (void*) I.getKey() << ") "; 410d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks LangOptions LO; // FIXME. 411d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); 412d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << " : " << I.getData(); 4132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 4142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 415d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks // Print block-expression bindings. 416d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks isFirst = true; 417d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 418d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks if (!C->isBlkExpr(I.getKey())) 419d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks continue; 420d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks 421d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks if (isFirst) { 422d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << NL << NL << "Block-level Expressions:" << NL; 423d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks isFirst = false; 424d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks } else { 425d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << NL; 426d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks } 4272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 428d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << " (" << (void*) I.getKey() << ") "; 429d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks LangOptions LO; // FIXME. 430d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); 431d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << " : " << I.getData(); 4322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 433d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks } else { 434d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks // Print All bindings - no info to differentiate block from subexpressions. 435d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 436d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks if (IsEnvLoc(I.getKey())) 437d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks continue; 438d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks 439d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks if (isFirst) { 440d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << NL << NL << "Expressions:" << NL; 441d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks isFirst = false; 442d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks } else { 443d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << NL; 444d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks } 4452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 446d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << " (" << (void*) I.getKey() << ") "; 447d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks LangOptions LO; // FIXME. 448d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); 449d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks Out << " : " << I.getData(); 450d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks } 4512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 452d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks 4532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Print locations. 4542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek isFirst = true; 4552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 4572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!IsEnvLoc(I.getKey())) 4582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek continue; 4592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isFirst) { 461dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Out << NL << NL << "Load/store locations:" << NL; 4622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek isFirst = false; 463dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose } else { 464dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Out << NL; 4652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 4662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const Stmt *S = (Stmt*) (((uintptr_t) I.getKey()) & ((uintptr_t) ~0x1)); 4682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Out << " (" << (void*) S << ") "; 4702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek LangOptions LO; // FIXME. 4712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek S->printPretty(Out, 0, PrintingPolicy(LO)); 4722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Out << " : " << I.getData(); 4732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 4742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 475dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getConstraintManager().print(this, Out, NL, Sep); 4762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Print checker-specific data. 478dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getOwningEngine()->printState(Out, this, NL, Sep); 4792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid ProgramState::printDOT(raw_ostream &Out, CFG &C) const { 482d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks print(Out, &C, "\\l", "\\|"); 483d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks} 484d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks 485d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaksvoid ProgramState::dump(CFG &C) const { 486d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks print(llvm::errs(), &C); 4872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 489d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaksvoid ProgramState::dump() const { 490d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaks print(llvm::errs(), 0); 4912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// Generic Data Map. 4952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid *const* ProgramState::FindGDM(void *K) const { 4982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return GDM.lookup(K); 4992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid* 5022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramStateManager::FindGDMContext(void *K, 5032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void *(*CreateContext)(llvm::BumpPtrAllocator&), 5042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void (*DeleteContext)(void*)) { 5052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 5072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!p.first) { 5082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek p.first = CreateContext(Alloc); 5092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek p.second = DeleteContext; 5102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return p.first; 5132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramStateManager::addGDM(const ProgramState *St, void *Key, void *Data){ 5162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap M1 = St->getGDM(); 5172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 5182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (M1 == M2) 5202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return St; 5212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *St; 5232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.GDM = M2; 5242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewSt); 5252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekconst ProgramState *ProgramStateManager::removeGDM(const ProgramState *state, void *Key) { 5282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap OldM = state->getGDM(); 5292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 5302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (NewM == OldM) 5322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return state; 5332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewState = *state; 5352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.GDM = NewM; 5362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewState); 5372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 53999ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid ScanReachableSymbols::anchor() { } 54099ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 5412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 5422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 5432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(*I)) 5442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 5452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(const SymExpr *sym) { 5502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek unsigned &isVisited = visited[sym]; 5512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isVisited) 5522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek isVisited = 1; 5542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 55576462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks if (!visitor.VisitSymbol(sym)) 55676462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks return false; 5572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 558a91efb14cbf6af999dee02d9b611a57c7b52e209Anna Zaks // TODO: should be rewritten using SymExpr::symbol_iterator. 5592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek switch (sym->getKind()) { 5602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::RegionValueKind: 5612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::ConjuredKind: 5622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::DerivedKind: 5632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::ExtentKind: 5642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::MetadataKind: 5652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek break; 566aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks case SymExpr::CastSymbolKind: 567aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks return scan(cast<SymbolCast>(sym)->getOperand()); 5682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::SymIntKind: 5692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(cast<SymIntExpr>(sym)->getLHS()); 57024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::IntSymKind: 57124d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return scan(cast<IntSymExpr>(sym)->getRHS()); 5722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::SymSymKind: { 5732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const SymSymExpr *x = cast<SymSymExpr>(sym); 5742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(x->getLHS()) && scan(x->getRHS()); 5752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(SVal val) { 5812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val)) 5822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(X->getRegion()); 5832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val)) 5852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(X->getLoc()); 5862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (SymbolRef Sym = val.getAsSymbol()) 5882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(Sym); 5892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SymExpr *Sym = val.getAsSymbolicExpression()) 5912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(Sym); 5922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val)) 5942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(*X); 5952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(const MemRegion *R) { 6002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isa<MemSpaceRegion>(R)) 6012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek unsigned &isVisited = visited[R]; 6042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isVisited) 6052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek isVisited = 1; 6072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If this is a symbolic region, visit the symbol for the region. 6092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 6102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!visitor.VisitSymbol(SR->getSymbol())) 6112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If this is a subregion, also visit the parent regions. 6142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SubRegion *SR = dyn_cast<SubRegion>(R)) 6152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(SR->getSuperRegion())) 6162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Now look at the binding to this region (if any). 6192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(state->getSValAsScalarOrLoc(R))) 6202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Now look at the subregions. 6232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!SRM.get()) 6242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SRM.reset(state->getStateManager().getStoreManager(). 6252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getSubRegionMap(state->getStore())); 6262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return SRM->iterSubRegions(R, *this); 6282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 6312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return S.scan(val); 6332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 6362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolVisitor &visitor) const { 6372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for ( ; I != E; ++I) { 6392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!S.scan(*I)) 6402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 6422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(const MemRegion * const *I, 6462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion * const *E, 6472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolVisitor &visitor) const { 6482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for ( ; I != E; ++I) { 6502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!S.scan(*I)) 6512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 6532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 655ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 656ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksconst ProgramState* ProgramState::addTaint(const Stmt *S, 657ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks TaintTagType Kind) const { 658d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks if (const Expr *E = dyn_cast_or_null<Expr>(S)) 659d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks S = E->IgnoreParens(); 660d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks 661ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks SymbolRef Sym = getSVal(S).getAsSymbol(); 662e55a22b917327651178ddea36b3615f579681eeaAnna Zaks if (Sym) 663e55a22b917327651178ddea36b3615f579681eeaAnna Zaks return addTaint(Sym, Kind); 664e55a22b917327651178ddea36b3615f579681eeaAnna Zaks 665e55a22b917327651178ddea36b3615f579681eeaAnna Zaks const MemRegion *R = getSVal(S).getAsRegion(); 66628fd98d66dab4569316de2b5881d91b534a42461Anna Zaks addTaint(R, Kind); 667e55a22b917327651178ddea36b3615f579681eeaAnna Zaks 668e55a22b917327651178ddea36b3615f579681eeaAnna Zaks // Cannot add taint, so just return the state. 669e55a22b917327651178ddea36b3615f579681eeaAnna Zaks return this; 670ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 671ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 67228fd98d66dab4569316de2b5881d91b534a42461Anna Zaksconst ProgramState* ProgramState::addTaint(const MemRegion *R, 67328fd98d66dab4569316de2b5881d91b534a42461Anna Zaks TaintTagType Kind) const { 67428fd98d66dab4569316de2b5881d91b534a42461Anna Zaks if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R)) 67528fd98d66dab4569316de2b5881d91b534a42461Anna Zaks return addTaint(SR->getSymbol(), Kind); 67628fd98d66dab4569316de2b5881d91b534a42461Anna Zaks return this; 67728fd98d66dab4569316de2b5881d91b534a42461Anna Zaks} 67828fd98d66dab4569316de2b5881d91b534a42461Anna Zaks 679ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksconst ProgramState* ProgramState::addTaint(SymbolRef Sym, 680ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks TaintTagType Kind) const { 681ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks const ProgramState *NewState = set<TaintMap>(Sym, Kind); 682ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks assert(NewState); 683ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks return NewState; 684ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 685ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 686ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksbool ProgramState::isTainted(const Stmt *S, TaintTagType Kind) const { 687d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks if (const Expr *E = dyn_cast_or_null<Expr>(S)) 688d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks S = E->IgnoreParens(); 689d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks 690dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks SVal val = getSVal(S); 691b39c5b4ddc9dcc7d9845c6c637e03e83302f8538Anna Zaks return isTainted(val, Kind); 692ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 693ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 694ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksbool ProgramState::isTainted(SVal V, TaintTagType Kind) const { 695dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SymExpr *Sym = V.getAsSymExpr()) 696dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(Sym, Kind); 697777d706547ebc751d998134774d9d5388fff8e02Anna Zaks if (const MemRegion *Reg = V.getAsRegion()) 698777d706547ebc751d998134774d9d5388fff8e02Anna Zaks return isTainted(Reg, Kind); 699dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 700dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks} 701dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 702dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaksbool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const { 703dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (!Reg) 704dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 705dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 706dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // Element region (array element) is tainted if either the base or the offset 707dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // are tainted. 708dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) 709dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(ER->getSuperRegion(), K) || isTainted(ER->getIndex(), K); 710dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 711dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) 712dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(SR->getSymbol(), K); 713dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 714dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) 715dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(ER->getSuperRegion(), K); 716dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 717dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 718ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 719ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 720ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksbool ProgramState::isTainted(const SymExpr* Sym, TaintTagType Kind) const { 721ee081c4051cde4bd44475b5e29d695008c15a9ccAnna Zaks if (!Sym) 722ee081c4051cde4bd44475b5e29d695008c15a9ccAnna Zaks return false; 7231d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 724dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // Traverse all the symbols this symbol depends on to see if any are tainted. 7251d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks bool Tainted = false; 7261d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); 7271d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks SI != SE; ++SI) { 7281d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks assert(isa<SymbolData>(*SI)); 7291d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks const TaintTagType *Tag = get<TaintMap>(*SI); 7301d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks Tainted = (Tag && *Tag == Kind); 7311d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 7321d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks // If this is a SymbolDerived with a tainted parent, it's also tainted. 7331d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) 7341d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks Tainted = Tainted || isTainted(SD->getParentSymbol(), Kind); 7355fc7def35ee858791e591d005b4ae343632ca931Anna Zaks 7365fc7def35ee858791e591d005b4ae343632ca931Anna Zaks // If memory region is tainted, data is also tainted. 7375fc7def35ee858791e591d005b4ae343632ca931Anna Zaks if (const SymbolRegionValue *SRV = dyn_cast<SymbolRegionValue>(*SI)) 7385fc7def35ee858791e591d005b4ae343632ca931Anna Zaks Tainted = Tainted || isTainted(SRV->getRegion(), Kind); 7395fc7def35ee858791e591d005b4ae343632ca931Anna Zaks 7401d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks if (Tainted) 7411d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return true; 742ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks } 7431d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 7441d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return Tainted; 745ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 746