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 28a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidisnamespace clang { namespace ento { 29a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis/// Increments the number of times this state is referenced. 30a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis 31a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidisvoid ProgramStateRetain(const ProgramState *state) { 32a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ++const_cast<ProgramState*>(state)->refCount; 33a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis} 34a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis 35a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis/// Decrement the number of times this state is referenced. 36a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidisvoid ProgramStateRelease(const ProgramState *state) { 37a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis assert(state->refCount > 0); 38a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ProgramState *s = const_cast<ProgramState*>(state); 39a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis if (--s->refCount == 0) { 40a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ProgramStateManager &Mgr = s->getStateManager(); 41a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis Mgr.StateSet.RemoveNode(s); 42a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis s->~ProgramState(); 43a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis Mgr.freeStates.push_back(s); 44a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis } 45a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis} 46a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis}} 47a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis 482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreRef st, GenericDataMap gdm) 502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek : stateMgr(mgr), 512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Env(env), 522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store(st.getStore()), 532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDM(gdm), 542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek refCount(0) { 552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(store); 562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::ProgramState(const ProgramState &RHS) 592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek : llvm::FoldingSetNode(), 602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr(RHS.stateMgr), 612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Env(RHS.Env), 622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store(RHS.store), 632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDM(RHS.GDM), 642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek refCount(0) { 652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(store); 662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::~ProgramState() { 692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (store) 702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().decrementReferenceCount(store); 712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramStateManager::~ProgramStateManager() { 742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek I!=E; ++I) 762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek I->second.second(I->second.first); 772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 798bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef 808bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateManager::removeDeadBindings(ProgramStateRef state, 812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StackFrameContext *LCtx, 822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolReaper& SymReaper) { 832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This code essentially performs a "mark-and-sweep" of the VariableBindings. 852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // The roots are any Block-level exprs and Decls that our liveness algorithm 862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // tells us are live. We then see what Decls they may reference, and keep 872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // those around. This code more than likely can be made faster, and the 882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // frequency of which this method is called should be experimented with 892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // for optimum performance. 902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewState = *state; 912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Clean up the store. 952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymReaper); 972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.setStore(newStore); 982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymReaper.setReapedStore(newStore); 992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewState); 1012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1038bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::MarshalState(ProgramStateRef state, 1042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StackFrameContext *InitLoc) { 1052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // make up an empty state for now. 1062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState State(this, 1072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek EnvMgr.getInitialEnvironment(), 1082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreMgr->getInitialStore(InitLoc), 1092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDMFactory.getEmptyMap()); 1102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(State); 1122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1148bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::bindCompoundLiteral(const CompoundLiteralExpr *CL, 1152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const LocationContext *LC, 1162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal V) const { 1172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 1182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getStateManager().StoreMgr->BindCompoundLiteral(getStore(), CL, LC, V); 1192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1228bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::bindDecl(const VarRegion* VR, SVal IVal) const { 1232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 1242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getStateManager().StoreMgr->BindDecl(getStore(), VR, IVal); 1252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1288bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::bindDeclWithNoInit(const VarRegion* VR) const { 1292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 1302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getStateManager().StoreMgr->BindDeclWithNoInit(getStore(), VR); 1312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1348bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::bindLoc(Loc LV, SVal V) const { 1352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 1368bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 1372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek LV, V)); 1382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion *MR = LV.getAsRegion(); 1392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (MR && Mgr.getOwningEngine()) 1402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return Mgr.getOwningEngine()->processRegionChange(newState, MR); 1412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return newState; 1432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1458bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::bindDefault(SVal loc, SVal V) const { 1462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 1472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion(); 1482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V); 1498bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef new_state = makeWithStore(newStore); 1502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return Mgr.getOwningEngine() ? 1512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Mgr.getOwningEngine()->processRegionChange(new_state, R) : 1522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek new_state; 1532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1558bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef 156537716ad8dd10f984b6cfe6985afade1185c5e3cJordy RoseProgramState::invalidateRegions(ArrayRef<const MemRegion *> Regions, 157537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose const Expr *E, unsigned Count, 1583133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx, 159537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose StoreManager::InvalidatedSymbols *IS, 160eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks const CallOrObjCMessage *Call) const { 1612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!IS) { 1622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreManager::InvalidatedSymbols invalidated; 1633133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek return invalidateRegionsImpl(Regions, E, Count, LCtx, 164eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks invalidated, Call); 1652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 1663133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek return invalidateRegionsImpl(Regions, E, Count, LCtx, *IS, Call); 1672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1698bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef 170537716ad8dd10f984b6cfe6985afade1185c5e3cJordy RoseProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, 171537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose const Expr *E, unsigned Count, 1723133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx, 173537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose StoreManager::InvalidatedSymbols &IS, 174eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks const CallOrObjCMessage *Call) const { 1752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 1762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SubEngine* Eng = Mgr.getOwningEngine(); 1772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (Eng && Eng->wantsRegionChangeUpdate(this)) { 179537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose StoreManager::InvalidatedRegions Invalidated; 1802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore 1813133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek = Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, LCtx, IS, 182eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks Call, &Invalidated); 1838bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef newState = makeWithStore(newStore); 18466c40400e7d6272b0cd675ada18dd62c1f0362c7Anna Zaks return Eng->processRegionChanges(newState, &IS, Regions, Invalidated, Call); 1852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 1862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 1883133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, LCtx, IS, 189eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks Call, NULL); 1902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 1912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1938bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::unbindLoc(Loc LV) const { 1942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek assert(!isa<loc::MemRegionVal>(LV) && "Use invalidateRegion instead."); 1952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Store OldStore = getStore(); 1972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = getStateManager().StoreMgr->Remove(OldStore, LV); 1982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newStore.getStore() == OldStore) 2002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 2032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2058bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef 2060849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted KremenekProgramState::enterStackFrame(const LocationContext *callerCtx, 2070849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek const StackFrameContext *calleeCtx) const { 2082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &new_store = 2090849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek getStateManager().StoreMgr->enterStackFrame(this, callerCtx, calleeCtx); 2102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(new_store); 2112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekSVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 2142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // We only want to do fetches from regions that we can actually bind 2152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // values. For example, SymbolicRegions of type 'id<...>' cannot 2162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // have direct bindings (but their can be bindings on their subregions). 2172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!R->isBoundable()) 2182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return UnknownVal(); 2192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 2212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek QualType T = TR->getValueType(); 2222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (Loc::isLocType(T) || T->isIntegerType()) 2232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getSVal(R); 2242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return UnknownVal(); 2272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekSVal ProgramState::getSVal(Loc location, QualType T) const { 2302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal V = getRawSVal(cast<Loc>(location), T); 2312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If 'V' is a symbolic value that is *perfectly* constrained to 2332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // be a constant value, use that value instead to lessen the burden 2342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // on later analysis stages (so we have less symbolic values to reason 2352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // about). 2362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!T.isNull()) { 2372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (SymbolRef sym = V.getAsSymbol()) { 2382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const llvm::APSInt *Int = getSymVal(sym)) { 2392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: Because we don't correctly model (yet) sign-extension 2402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // and truncation of symbolic values, we need to convert 2412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // the integer value to the correct signedness and bitwidth. 2422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This shows up in the following: 2442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // char foo(); 2462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // unsigned x = foo(); 2472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // if (x == 54) 2482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // ... 2492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // The symbolic value stored to 'x' is actually the conjured 2512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // symbol for the call to foo(); the type of that symbol is 'char', 2522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // not unsigned. 2532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 2542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isa<Loc>(V)) 2562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return loc::ConcreteInt(NewV); 2572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek else 2582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return nonloc::ConcreteInt(NewV); 2592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return V; 2642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2668bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::BindExpr(const Stmt *S, 2675eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek const LocationContext *LCtx, 2685eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal V, bool Invalidate) const{ 2695eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek Environment NewEnv = 2705eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V, 2715eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek Invalidate); 2722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (NewEnv == Env) 2732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *this; 2762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.Env = NewEnv; 2772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getStateManager().getPersistentState(NewSt); 2782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2808bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef 2815eca482fe895ea57bc82410222e6426c09e63284Ted KremenekProgramState::bindExprAndLocation(const Stmt *S, const LocationContext *LCtx, 2825eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal location, 2835eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal V) const { 2842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Environment NewEnv = 2855eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek getStateManager().EnvMgr.bindExprAndLocation(Env, 2865eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek EnvironmentEntry(S, LCtx), 2875eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek location, V); 2882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (NewEnv == Env) 2902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *this; 2932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.Env = NewEnv; 2942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getStateManager().getPersistentState(NewSt); 2952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2978bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 2982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek DefinedOrUnknownSVal UpperBound, 299af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks bool Assumption, 300af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks QualType indexTy) const { 3012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (Idx.isUnknown() || UpperBound.isUnknown()) 3022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Build an expression for 0 <= Idx < UpperBound. 3052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 3062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: This should probably be part of SValBuilder. 3072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &SM = getStateManager(); 3082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SValBuilder &svalBuilder = SM.getSValBuilder(); 3092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ASTContext &Ctx = svalBuilder.getContext(); 3102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Get the offset: the minimum value of the array index type. 3122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 3132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: This should be using ValueManager::ArrayindexTy...somehow. 314af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (indexTy.isNull()) 315af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks indexTy = Ctx.IntTy; 3162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 3172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Adjust the index. 3192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 3202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek cast<NonLoc>(Idx), Min, indexTy); 3212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newIdx.isUnknownOrUndef()) 3222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Adjust the upper bound. 3252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal newBound = 3262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek svalBuilder.evalBinOpNN(this, BO_Add, cast<NonLoc>(UpperBound), 3272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Min, indexTy); 3282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newBound.isUnknownOrUndef()) 3302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Build the actual comparison. 3332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, 3342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek cast<NonLoc>(newIdx), cast<NonLoc>(newBound), 3352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Ctx.IntTy); 3362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (inBound.isUnknownOrUndef()) 3372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Finally, let the constraint manager take care of it. 3402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ConstraintManager &CM = SM.getConstraintManager(); 3412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return CM.assume(this, cast<DefinedSVal>(inBound), Assumption); 3422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3448bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 3452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState State(this, 3462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek EnvMgr.getInitialEnvironment(), 3472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreMgr->getInitialStore(InitLoc), 3482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDMFactory.getEmptyMap()); 3492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(State); 3512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3538bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::getPersistentStateWithGDM( 3548bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef FromState, 3558bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef GDMState) { 356a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ProgramState NewState(*FromState); 3572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.GDM = GDMState->GDM; 3582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewState); 3592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3618bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) { 3622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek llvm::FoldingSetNodeID ID; 3642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek State.Profile(ID); 3652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void *InsertPos; 3662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 3682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return I; 3692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState *newState = 0; 3712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!freeStates.empty()) { 3722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek newState = freeStates.back(); 3732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek freeStates.pop_back(); 3742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 3752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek else { 3762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 3772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 3782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek new (newState) ProgramState(State); 3792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StateSet.InsertNode(newState, InsertPos); 3802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return newState; 3812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3838bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const { 384a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ProgramState NewSt(*this); 3852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.setStore(store); 3862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getStateManager().getPersistentState(NewSt); 3872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid ProgramState::setStore(const StoreRef &newStore) { 3902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Store newStoreStore = newStore.getStore(); 3912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newStoreStore) 3922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 3932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (store) 3942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().decrementReferenceCount(store); 3952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store = newStoreStore; 3962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 3992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// State pretty-printing. 4002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4025eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekvoid ProgramState::print(raw_ostream &Out, 403dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose const char *NL, const char *Sep) const { 4042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Print the store. 4052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 406dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getStoreManager().print(getStore(), Out, NL, Sep); 4072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4085eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek // Print out the environment. 4095eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek Env.print(Out, NL, Sep); 4102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4115eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek // Print out the constraints. 412dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getConstraintManager().print(this, Out, NL, Sep); 4132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Print checker-specific data. 415dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getOwningEngine()->printState(Out, this, NL, Sep); 4162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4185eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekvoid ProgramState::printDOT(raw_ostream &Out) const { 4195eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek print(Out, "\\l", "\\|"); 4202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 422d0167853f46cc78787b06255a44f9dcedd04a8ecAnna Zaksvoid ProgramState::dump() const { 4235eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek print(llvm::errs()); 4242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 426be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaksvoid ProgramState::printTaint(raw_ostream &Out, 427be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks const char *NL, const char *Sep) const { 428be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks TaintMapImpl TM = get<TaintMap>(); 429be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 430be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks if (!TM.isEmpty()) 431be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks Out <<"Tainted Symbols:" << NL; 432be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 433be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks for (TaintMapImpl::iterator I = TM.begin(), E = TM.end(); I != E; ++I) { 434be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks Out << I->first << " : " << I->second << NL; 435be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks } 436be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks} 437be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 438be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaksvoid ProgramState::dumpTaint() const { 439be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks printTaint(llvm::errs()); 440be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks} 441be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 4422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// Generic Data Map. 4442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid *const* ProgramState::FindGDM(void *K) const { 4472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return GDM.lookup(K); 4482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid* 4512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramStateManager::FindGDMContext(void *K, 4522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void *(*CreateContext)(llvm::BumpPtrAllocator&), 4532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void (*DeleteContext)(void*)) { 4542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 4562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!p.first) { 4572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek p.first = CreateContext(Alloc); 4582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek p.second = DeleteContext; 4592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 4602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return p.first; 4622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4648bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){ 4652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap M1 = St->getGDM(); 4662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 4672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (M1 == M2) 4692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return St; 4702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *St; 4722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.GDM = M2; 4732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewSt); 4742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4768bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { 4772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap OldM = state->getGDM(); 4782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 4792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (NewM == OldM) 4812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return state; 4822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewState = *state; 4842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.GDM = NewM; 4852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewState); 4862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 48899ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid ScanReachableSymbols::anchor() { } 48999ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 4902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 4912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 4922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(*I)) 4932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 4942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 4962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(const SymExpr *sym) { 4992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek unsigned &isVisited = visited[sym]; 5002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isVisited) 5012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek isVisited = 1; 5032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 50476462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks if (!visitor.VisitSymbol(sym)) 50576462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks return false; 5062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 507a91efb14cbf6af999dee02d9b611a57c7b52e209Anna Zaks // TODO: should be rewritten using SymExpr::symbol_iterator. 5082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek switch (sym->getKind()) { 5092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::RegionValueKind: 5102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::ConjuredKind: 5112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::DerivedKind: 5122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::ExtentKind: 5132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::MetadataKind: 5142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek break; 515aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks case SymExpr::CastSymbolKind: 516aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks return scan(cast<SymbolCast>(sym)->getOperand()); 5172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::SymIntKind: 5182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(cast<SymIntExpr>(sym)->getLHS()); 51924d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks case SymExpr::IntSymKind: 52024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return scan(cast<IntSymExpr>(sym)->getRHS()); 5212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek case SymExpr::SymSymKind: { 5222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const SymSymExpr *x = cast<SymSymExpr>(sym); 5232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(x->getLHS()) && scan(x->getRHS()); 5242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(SVal val) { 5302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val)) 5312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(X->getRegion()); 5322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val)) 5342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(X->getLoc()); 5352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (SymbolRef Sym = val.getAsSymbol()) 5372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(Sym); 5382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SymExpr *Sym = val.getAsSymbolicExpression()) 5402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(Sym); 5412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val)) 5432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(*X); 5442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(const MemRegion *R) { 5492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isa<MemSpaceRegion>(R)) 5502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek unsigned &isVisited = visited[R]; 5532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isVisited) 5542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek isVisited = 1; 5567f9b1d963d4b7e2faff7305733e3453130b402feTed Kremenek 5577f9b1d963d4b7e2faff7305733e3453130b402feTed Kremenek 5587f9b1d963d4b7e2faff7305733e3453130b402feTed Kremenek if (!visitor.VisitMemRegion(R)) 5597f9b1d963d4b7e2faff7305733e3453130b402feTed Kremenek return false; 5602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If this is a symbolic region, visit the symbol for the region. 5622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 5632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!visitor.VisitSymbol(SR->getSymbol())) 5642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 5652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If this is a subregion, also visit the parent regions. 5672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SubRegion *SR = dyn_cast<SubRegion>(R)) 5682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(SR->getSuperRegion())) 5692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 5702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Now look at the binding to this region (if any). 5722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(state->getSValAsScalarOrLoc(R))) 5732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 5742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Now look at the subregions. 5762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!SRM.get()) 5772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SRM.reset(state->getStateManager().getStoreManager(). 5782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek getSubRegionMap(state->getStore())); 5792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return SRM->iterSubRegions(R, *this); 5812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 5842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 5852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return S.scan(val); 5862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 5892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolVisitor &visitor) const { 5902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 5912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for ( ; I != E; ++I) { 5922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!S.scan(*I)) 5932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 5942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(const MemRegion * const *I, 5992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion * const *E, 6002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolVisitor &visitor) const { 6012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for ( ; I != E; ++I) { 6032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!S.scan(*I)) 6042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 6062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 608ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 6098bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::addTaint(const Stmt *S, 6105eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek const LocationContext *LCtx, 611ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks TaintTagType Kind) const { 612d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks if (const Expr *E = dyn_cast_or_null<Expr>(S)) 613d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks S = E->IgnoreParens(); 614d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks 6155eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SymbolRef Sym = getSVal(S, LCtx).getAsSymbol(); 616e55a22b917327651178ddea36b3615f579681eeaAnna Zaks if (Sym) 617e55a22b917327651178ddea36b3615f579681eeaAnna Zaks return addTaint(Sym, Kind); 618e55a22b917327651178ddea36b3615f579681eeaAnna Zaks 6195eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek const MemRegion *R = getSVal(S, LCtx).getAsRegion(); 62028fd98d66dab4569316de2b5881d91b534a42461Anna Zaks addTaint(R, Kind); 621e55a22b917327651178ddea36b3615f579681eeaAnna Zaks 622e55a22b917327651178ddea36b3615f579681eeaAnna Zaks // Cannot add taint, so just return the state. 623e55a22b917327651178ddea36b3615f579681eeaAnna Zaks return this; 624ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 625ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 6268bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::addTaint(const MemRegion *R, 62728fd98d66dab4569316de2b5881d91b534a42461Anna Zaks TaintTagType Kind) const { 62828fd98d66dab4569316de2b5881d91b534a42461Anna Zaks if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R)) 62928fd98d66dab4569316de2b5881d91b534a42461Anna Zaks return addTaint(SR->getSymbol(), Kind); 63028fd98d66dab4569316de2b5881d91b534a42461Anna Zaks return this; 63128fd98d66dab4569316de2b5881d91b534a42461Anna Zaks} 63228fd98d66dab4569316de2b5881d91b534a42461Anna Zaks 6338bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::addTaint(SymbolRef Sym, 634ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks TaintTagType Kind) const { 635be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks // If this is a symbol cast, remove the cast before adding the taint. Taint 636be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks // is cast agnostic. 637be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) 638be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks Sym = SC->getOperand(); 639be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 6408bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef NewState = set<TaintMap>(Sym, Kind); 641ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks assert(NewState); 642ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks return NewState; 643ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 644ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 6455eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekbool ProgramState::isTainted(const Stmt *S, const LocationContext *LCtx, 6465eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek TaintTagType Kind) const { 647d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks if (const Expr *E = dyn_cast_or_null<Expr>(S)) 648d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks S = E->IgnoreParens(); 649d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks 6505eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal val = getSVal(S, LCtx); 651b39c5b4ddc9dcc7d9845c6c637e03e83302f8538Anna Zaks return isTainted(val, Kind); 652ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 653ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 654ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksbool ProgramState::isTainted(SVal V, TaintTagType Kind) const { 655dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SymExpr *Sym = V.getAsSymExpr()) 656dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(Sym, Kind); 657777d706547ebc751d998134774d9d5388fff8e02Anna Zaks if (const MemRegion *Reg = V.getAsRegion()) 658777d706547ebc751d998134774d9d5388fff8e02Anna Zaks return isTainted(Reg, Kind); 659dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 660dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks} 661dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 662dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaksbool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const { 663dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (!Reg) 664dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 665dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 666dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // Element region (array element) is tainted if either the base or the offset 667dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // are tainted. 668dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) 669dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(ER->getSuperRegion(), K) || isTainted(ER->getIndex(), K); 670dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 671dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) 672dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(SR->getSymbol(), K); 673dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 674dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) 675dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(ER->getSuperRegion(), K); 676dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 677dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 678ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 679ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 6809f03b62036a7abc0a227b17f4a49b9eefced9450Anna Zaksbool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const { 681ee081c4051cde4bd44475b5e29d695008c15a9ccAnna Zaks if (!Sym) 682ee081c4051cde4bd44475b5e29d695008c15a9ccAnna Zaks return false; 6831d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 684dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // Traverse all the symbols this symbol depends on to see if any are tainted. 6851d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks bool Tainted = false; 6861d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); 6871d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks SI != SE; ++SI) { 6881d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks assert(isa<SymbolData>(*SI)); 6891d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks const TaintTagType *Tag = get<TaintMap>(*SI); 6901d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks Tainted = (Tag && *Tag == Kind); 6911d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 6921d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks // If this is a SymbolDerived with a tainted parent, it's also tainted. 6931d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) 6941d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks Tainted = Tainted || isTainted(SD->getParentSymbol(), Kind); 6955fc7def35ee858791e591d005b4ae343632ca931Anna Zaks 6965fc7def35ee858791e591d005b4ae343632ca931Anna Zaks // If memory region is tainted, data is also tainted. 6975fc7def35ee858791e591d005b4ae343632ca931Anna Zaks if (const SymbolRegionValue *SRV = dyn_cast<SymbolRegionValue>(*SI)) 6985fc7def35ee858791e591d005b4ae343632ca931Anna Zaks Tainted = Tainted || isTainted(SRV->getRegion(), Kind); 6995fc7def35ee858791e591d005b4ae343632ca931Anna Zaks 700be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks // If If this is a SymbolCast from a tainted value, it's also tainted. 701be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks if (const SymbolCast *SC = dyn_cast<SymbolCast>(*SI)) 702be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks Tainted = Tainted || isTainted(SC->getOperand(), Kind); 703be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 7041d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks if (Tainted) 7051d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return true; 706ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks } 7071d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 7081d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return Tainted; 709ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 710