ProgramState.cpp revision b39c5b4ddc9dcc7d9845c6c637e03e83302f8538
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 5392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 5402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 5412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(*I)) 5422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 5432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(const SymExpr *sym) { 5482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek unsigned &isVisited = visited[sym]; 5492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isVisited) 5502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek isVisited = 1; 5522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 55376462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks if (!visitor.VisitSymbol(sym)) 55476462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks return false; 5552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 556a91efb14cbf6af999dee02d9b611a57c7b52e209Anna Zaks // TODO: should be rewritten using SymExpr::symbol_iterator. 5572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek switch (sym->getKind()) { 5582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::RegionValueKind: 5592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::ConjuredKind: 5602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::DerivedKind: 5612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::ExtentKind: 5622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::MetadataKind: 5632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek break; 564aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks case SymExpr::CastSymbolKind: 565aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks return scan(cast<SymbolCast>(sym)->getOperand()); 5662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::SymIntKind: 5672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(cast<SymIntExpr>(sym)->getLHS()); 5682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::SymSymKind: { 5692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const SymSymExpr *x = cast<SymSymExpr>(sym); 5702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(x->getLHS()) && scan(x->getRHS()); 5712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(SVal val) { 5772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val)) 5782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(X->getRegion()); 5792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val)) 5812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(X->getLoc()); 5822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (SymbolRef Sym = val.getAsSymbol()) 5842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(Sym); 5852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SymExpr *Sym = val.getAsSymbolicExpression()) 5872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(Sym); 5882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val)) 5902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(*X); 5912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(const MemRegion *R) { 5962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isa<MemSpaceRegion>(R)) 5972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek unsigned &isVisited = visited[R]; 6002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isVisited) 6012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek isVisited = 1; 6032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If this is a symbolic region, visit the symbol for the region. 6052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 6062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!visitor.VisitSymbol(SR->getSymbol())) 6072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If this is a subregion, also visit the parent regions. 6102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SubRegion *SR = dyn_cast<SubRegion>(R)) 6112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(SR->getSuperRegion())) 6122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Now look at the binding to this region (if any). 6152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(state->getSValAsScalarOrLoc(R))) 6162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Now look at the subregions. 6192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!SRM.get()) 6202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SRM.reset(state->getStateManager().getStoreManager(). 6212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getSubRegionMap(state->getStore())); 6222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return SRM->iterSubRegions(R, *this); 6242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 6272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return S.scan(val); 6292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 6322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolVisitor &visitor) const { 6332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for ( ; I != E; ++I) { 6352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!S.scan(*I)) 6362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 6382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(const MemRegion * const *I, 6422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion * const *E, 6432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolVisitor &visitor) const { 6442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for ( ; I != E; ++I) { 6462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!S.scan(*I)) 6472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 6492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 651ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 652ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksconst ProgramState* ProgramState::addTaint(const Stmt *S, 653ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks TaintTagType Kind) const { 654ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks SymbolRef Sym = getSVal(S).getAsSymbol(); 655ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks assert(Sym && "Cannot add taint to statements whose value is not a symbol"); 656ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks return addTaint(Sym, Kind); 657ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 658ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 659ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksconst ProgramState* ProgramState::addTaint(SymbolRef Sym, 660ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks TaintTagType Kind) const { 661ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks const ProgramState *NewState = set<TaintMap>(Sym, Kind); 662ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks assert(NewState); 663ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks return NewState; 664ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 665ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 666ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksbool ProgramState::isTainted(const Stmt *S, TaintTagType Kind) const { 667dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks SVal val = getSVal(S); 668b39c5b4ddc9dcc7d9845c6c637e03e83302f8538Anna Zaks return isTainted(val, Kind); 669ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 670ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 671ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksbool ProgramState::isTainted(SVal V, TaintTagType Kind) const { 672dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SymExpr *Sym = V.getAsSymExpr()) 673dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(Sym, Kind); 674dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (loc::MemRegionVal *RegVal = dyn_cast<loc::MemRegionVal>(&V)) 675dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(RegVal->getRegion(), Kind); 676dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 677dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks} 678dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 679dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaksbool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const { 680dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (!Reg) 681dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 682dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 683dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // Element region (array element) is tainted if either the base or the offset 684dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // are tainted. 685dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) 686dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(ER->getSuperRegion(), K) || isTainted(ER->getIndex(), K); 687dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 688dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) 689dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(SR->getSymbol(), K); 690dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 691dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) 692dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(ER->getSuperRegion(), K); 693dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 694dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 695ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 696ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 697ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksbool ProgramState::isTainted(const SymExpr* Sym, TaintTagType Kind) const { 698ee081c4051cde4bd44475b5e29d695008c15a9ccAnna Zaks if (!Sym) 699ee081c4051cde4bd44475b5e29d695008c15a9ccAnna Zaks return false; 7001d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 701dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // Traverse all the symbols this symbol depends on to see if any are tainted. 7021d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks bool Tainted = false; 7031d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); 7041d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks SI != SE; ++SI) { 7051d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks assert(isa<SymbolData>(*SI)); 7061d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks const TaintTagType *Tag = get<TaintMap>(*SI); 7071d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks Tainted = (Tag && *Tag == Kind); 7081d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 7091d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks // If this is a SymbolDerived with a tainted parent, it's also tainted. 7101d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) 7111d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks Tainted = Tainted || isTainted(SD->getParentSymbol(), Kind); 7121d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks if (Tainted) 7131d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return true; 714ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks } 7151d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 7161d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return Tainted; 717ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 718