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 1455fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "clang/Analysis/CFG.h" 16972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 19ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h" 202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek#include "llvm/Support/raw_ostream.h" 212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekusing namespace clang; 232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekusing namespace ento; 242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 25a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidisnamespace clang { namespace ento { 26a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis/// Increments the number of times this state is referenced. 27a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis 28a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidisvoid ProgramStateRetain(const ProgramState *state) { 29a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ++const_cast<ProgramState*>(state)->refCount; 30a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis} 31a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis 32a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis/// Decrement the number of times this state is referenced. 33a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidisvoid ProgramStateRelease(const ProgramState *state) { 34a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis assert(state->refCount > 0); 35a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ProgramState *s = const_cast<ProgramState*>(state); 36a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis if (--s->refCount == 0) { 37a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ProgramStateManager &Mgr = s->getStateManager(); 38a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis Mgr.StateSet.RemoveNode(s); 3987d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar s->~ProgramState(); 40a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis Mgr.freeStates.push_back(s); 41a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis } 42a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis} 43a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis}} 44a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis 452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreRef st, GenericDataMap gdm) 472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek : stateMgr(mgr), 482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Env(env), 492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store(st.getStore()), 502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDM(gdm), 512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek refCount(0) { 522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(store); 532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::ProgramState(const ProgramState &RHS) 562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek : llvm::FoldingSetNode(), 572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr(RHS.stateMgr), 582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Env(RHS.Env), 592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store(RHS.store), 602fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDM(RHS.GDM), 612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek refCount(0) { 622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(store); 632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramState::~ProgramState() { 662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (store) 672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().decrementReferenceCount(store); 682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 70972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan RoseProgramStateManager::ProgramStateManager(ASTContext &Ctx, 71972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose StoreManagerCreator CreateSMgr, 72972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose ConstraintManagerCreator CreateCMgr, 73972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose llvm::BumpPtrAllocator &alloc, 74ca5d78d0bc3010164f2f9682967d64d7e305a167Jordan Rose SubEngine *SubEng) 75ca5d78d0bc3010164f2f9682967d64d7e305a167Jordan Rose : Eng(SubEng), EnvMgr(alloc), GDMFactory(alloc), 76972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), 77972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) { 78176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines StoreMgr = (*CreateSMgr)(*this); 79176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ConstraintMgr = (*CreateCMgr)(*this, SubEng); 80972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose} 81972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose 82972a3680bdd95f2e9d6316b391f1c47513dc78ccJordan Rose 832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramStateManager::~ProgramStateManager() { 842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek I!=E; ++I) 862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek I->second.second(I->second.first); 872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 8987d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga NainarProgramStateRef 908bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateManager::removeDeadBindings(ProgramStateRef state, 912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StackFrameContext *LCtx, 922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolReaper& SymReaper) { 932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This code essentially performs a "mark-and-sweep" of the VariableBindings. 952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // The roots are any Block-level exprs and Decls that our liveness algorithm 962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // tells us are live. We then see what Decls they may reference, and keep 972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // those around. This code more than likely can be made faster, and the 982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // frequency of which this method is called should be experimented with 992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // for optimum performance. 1002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewState = *state; 1012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 1032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Clean up the store. 1052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 1062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymReaper); 1072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.setStore(newStore); 1082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymReaper.setReapedStore(newStore); 1090073a5c7ce38e98365c00921316030627b3d129fJordan Rose 1100073a5c7ce38e98365c00921316030627b3d129fJordan Rose ProgramStateRef Result = getPersistentState(NewState); 1110073a5c7ce38e98365c00921316030627b3d129fJordan Rose return ConstraintMgr->removeDeadBindings(Result, SymReaper); 1122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 11432a549a64922af0903bdb777613ae7ae4490b70fTed KremenekProgramStateRef ProgramState::bindLoc(Loc LV, SVal V, bool notifyChanges) const { 1152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 11687d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 1172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek LV, V)); 1182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion *MR = LV.getAsRegion(); 11932a549a64922af0903bdb777613ae7ae4490b70fTed Kremenek if (MR && Mgr.getOwningEngine() && notifyChanges) 1202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return Mgr.getOwningEngine()->processRegionChange(newState, MR); 1212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return newState; 1232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 1258bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::bindDefault(SVal loc, SVal V) const { 1262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 1275251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion(); 1282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V); 1298bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef new_state = makeWithStore(newStore); 13087d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar return Mgr.getOwningEngine() ? 13187d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar Mgr.getOwningEngine()->processRegionChange(new_state, R) : 1322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek new_state; 1332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 135f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rosetypedef ArrayRef<const MemRegion *> RegionList; 136658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zakstypedef ArrayRef<SVal> ValueList; 137f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan Rose 13887d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga NainarProgramStateRef 139f8ddc098981d4d85cad4e72fc6dfcfe83b842b66Jordan RoseProgramState::invalidateRegions(RegionList Regions, 140da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev const Expr *E, unsigned Count, 141da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev const LocationContext *LCtx, 142da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev bool CausedByPointerEscape, 143da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev InvalidatedSymbols *IS, 144da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev const CallEvent *Call, 145da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev RegionAndSymbolInvalidationTraits *ITraits) const { 146658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks SmallVector<SVal, 8> Values; 147658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks for (RegionList::const_iterator I = Regions.begin(), 14877e278880380fe9dc95a1491fe9216967d2e6d63Aaron Ballman End = Regions.end(); I != End; ++I) 149658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks Values.push_back(loc::MemRegionVal(*I)); 150658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks 151658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, 152da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev IS, ITraits, Call); 1532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 1542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 155658a28479dd775f6ff2c07fa5699a7ea01e04127Anna ZaksProgramStateRef 156658a28479dd775f6ff2c07fa5699a7ea01e04127Anna ZaksProgramState::invalidateRegions(ValueList Values, 157da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev const Expr *E, unsigned Count, 158da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev const LocationContext *LCtx, 159da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev bool CausedByPointerEscape, 160da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev InvalidatedSymbols *IS, 161da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev const CallEvent *Call, 162da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev RegionAndSymbolInvalidationTraits *ITraits) const { 163da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev 164658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, 165da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev IS, ITraits, Call); 166658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks} 167658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks 168658a28479dd775f6ff2c07fa5699a7ea01e04127Anna ZaksProgramStateRef 169658a28479dd775f6ff2c07fa5699a7ea01e04127Anna ZaksProgramState::invalidateRegionsImpl(ValueList Values, 170537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose const Expr *E, unsigned Count, 1713133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek const LocationContext *LCtx, 1721655bcd052a67a3050fc55df8ecce57342352e68Anna Zaks bool CausedByPointerEscape, 173da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev InvalidatedSymbols *IS, 174da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev RegionAndSymbolInvalidationTraits *ITraits, 175da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev const CallEvent *Call) const { 1762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 1772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SubEngine* Eng = Mgr.getOwningEngine(); 17841988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks 179da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev InvalidatedSymbols Invalidated; 180da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev if (!IS) 181da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev IS = &Invalidated; 182da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev 183da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev RegionAndSymbolInvalidationTraits ITraitsLocal; 184da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev if (!ITraits) 185da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev ITraits = &ITraitsLocal; 186da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev 187bf53dfac8195835028bd6347433f7dbebcc29fc1Anna Zaks if (Eng) { 188658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks StoreManager::InvalidatedRegions TopLevelInvalidated; 189537716ad8dd10f984b6cfe6985afade1185c5e3cJordy Rose StoreManager::InvalidatedRegions Invalidated; 1902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore 191da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, 192da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev *IS, *ITraits, &TopLevelInvalidated, 193658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks &Invalidated); 194bf53dfac8195835028bd6347433f7dbebcc29fc1Anna Zaks 1958bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef newState = makeWithStore(newStore); 196bf53dfac8195835028bd6347433f7dbebcc29fc1Anna Zaks 19741988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks if (CausedByPointerEscape) { 198da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev newState = Eng->notifyCheckersOfPointerEscape(newState, IS, 199658a28479dd775f6ff2c07fa5699a7ea01e04127Anna Zaks TopLevelInvalidated, 20087d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar Invalidated, Call, 201da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev *ITraits); 20241988f331a74a72cf243a2a68ffb56418e9a174eAnna Zaks } 203bf53dfac8195835028bd6347433f7dbebcc29fc1Anna Zaks 20487d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar return Eng->processRegionChanges(newState, IS, TopLevelInvalidated, 205da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev Invalidated, Call); 2062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const StoreRef &newStore = 209da8d37ce42d2db4e1e76ee6f7f38f10f6b0ef0f8Anton Yartsev Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, 2106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines *IS, *ITraits, nullptr, nullptr); 2112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 2122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 21456a46b51df691f857f7120aaf2d4deeff0b014deTed KremenekProgramStateRef ProgramState::killBinding(Loc LV) const { 2155251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead."); 2162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Store OldStore = getStore(); 21856a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek const StoreRef &newStore = 21956a46b51df691f857f7120aaf2d4deeff0b014deTed Kremenek getStateManager().StoreMgr->killBinding(OldStore, LV); 2202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newStore.getStore() == OldStore) 2222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return makeWithStore(newStore); 2252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 22787d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga NainarProgramStateRef 228e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan RoseProgramState::enterStackFrame(const CallEvent &Call, 229e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose const StackFrameContext *CalleeCtx) const { 230e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose const StoreRef &NewStore = 231e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx); 232e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rose return makeWithStore(NewStore); 2332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekSVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 2362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // We only want to do fetches from regions that we can actually bind 2372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // values. For example, SymbolicRegions of type 'id<...>' cannot 2382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // have direct bindings (but their can be bindings on their subregions). 2392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!R->isBoundable()) 2402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return UnknownVal(); 2412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 2432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek QualType T = TR->getValueType(); 244a5796f87229b4aeebca71fa6ee1790ae7a5a0382Jordan Rose if (Loc::isLocType(T) || T->isIntegralOrEnumerationType()) 2452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getSVal(R); 2462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return UnknownVal(); 2492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2502fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2512fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekSVal ProgramState::getSVal(Loc location, QualType T) const { 2522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal V = getRawSVal(cast<Loc>(location), T); 2532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If 'V' is a symbolic value that is *perfectly* constrained to 2552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // be a constant value, use that value instead to lessen the burden 2562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // on later analysis stages (so we have less symbolic values to reason 2572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // about). 2582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!T.isNull()) { 2592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (SymbolRef sym = V.getAsSymbol()) { 26047cbd0f3892c7965cf16a58393f9f17a22d4d4d9Ted Kremenek if (const llvm::APSInt *Int = getStateManager() 26147cbd0f3892c7965cf16a58393f9f17a22d4d4d9Ted Kremenek .getConstraintManager() 26247cbd0f3892c7965cf16a58393f9f17a22d4d4d9Ted Kremenek .getSymVal(this, sym)) { 2632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: Because we don't correctly model (yet) sign-extension 2642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // and truncation of symbolic values, we need to convert 2652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // the integer value to the correct signedness and bitwidth. 2662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This shows up in the following: 2682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // char foo(); 2702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // unsigned x = foo(); 2712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // if (x == 54) 2722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // ... 2732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // 2742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // The symbolic value stored to 'x' is actually the conjured 2752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // symbol for the call to foo(); the type of that symbol is 'char', 2762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // not unsigned. 2772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 27887d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 2795251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie if (V.getAs<Loc>()) 2802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return loc::ConcreteInt(NewV); 2812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek else 2822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return nonloc::ConcreteInt(NewV); 2832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 2852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 28687d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 2872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return V; 2882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 2892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2908bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::BindExpr(const Stmt *S, 2915eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek const LocationContext *LCtx, 2925eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal V, bool Invalidate) const{ 2935eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek Environment NewEnv = 2945eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V, 2955eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek Invalidate); 2962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (NewEnv == Env) 2972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 2982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 2992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *this; 3002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.Env = NewEnv; 3012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getStateManager().getPersistentState(NewSt); 3022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3048bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 3052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek DefinedOrUnknownSVal UpperBound, 306af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks bool Assumption, 307af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks QualType indexTy) const { 3082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (Idx.isUnknown() || UpperBound.isUnknown()) 3092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Build an expression for 0 <= Idx < UpperBound. 3122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 3132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: This should probably be part of SValBuilder. 3142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &SM = getStateManager(); 3152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SValBuilder &svalBuilder = SM.getSValBuilder(); 3162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ASTContext &Ctx = svalBuilder.getContext(); 3172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Get the offset: the minimum value of the array index type. 3192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 3202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // FIXME: This should be using ValueManager::ArrayindexTy...somehow. 321af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks if (indexTy.isNull()) 322af5f550de34525b27f0ff31dafce792caf8158b6Anna Zaks indexTy = Ctx.IntTy; 3232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 3242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Adjust the index. 3262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 3275251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie Idx.castAs<NonLoc>(), Min, indexTy); 3282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newIdx.isUnknownOrUndef()) 3292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Adjust the upper bound. 3322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SVal newBound = 3335251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(), 3342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Min, indexTy); 3352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newBound.isUnknownOrUndef()) 3372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Build the actual comparison. 3405251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(), 3415251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie newBound.castAs<NonLoc>(), Ctx.IntTy); 3422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (inBound.isUnknownOrUndef()) 3432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return this; 3442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Finally, let the constraint manager take care of it. 3462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ConstraintManager &CM = SM.getConstraintManager(); 3475251abea41b446c26e3239c8dd6c7edea6fc335dDavid Blaikie return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption); 3482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 350cc5dbdae70c6eb2423921f52a35ba4686d2969cfAnna ZaksConditionTruthVal ProgramState::isNull(SVal V) const { 351cc5dbdae70c6eb2423921f52a35ba4686d2969cfAnna Zaks if (V.isZeroConstant()) 352cc5dbdae70c6eb2423921f52a35ba4686d2969cfAnna Zaks return true; 353cc5dbdae70c6eb2423921f52a35ba4686d2969cfAnna Zaks 354c1bef5671e682de5a573c7c6b66871b36de0ec61Anna Zaks if (V.isConstant()) 355c1bef5671e682de5a573c7c6b66871b36de0ec61Anna Zaks return false; 35687d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 3578ef064d53fb33b5a8f8743bcbb0a2fd5c3e97be1Anna Zaks SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true); 358cc5dbdae70c6eb2423921f52a35ba4686d2969cfAnna Zaks if (!Sym) 359c1bef5671e682de5a573c7c6b66871b36de0ec61Anna Zaks return ConditionTruthVal(); 36087d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 361cc5dbdae70c6eb2423921f52a35ba4686d2969cfAnna Zaks return getStateManager().ConstraintMgr->isNull(this, Sym); 362cc5dbdae70c6eb2423921f52a35ba4686d2969cfAnna Zaks} 363cc5dbdae70c6eb2423921f52a35ba4686d2969cfAnna Zaks 3648bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 3652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState State(this, 3662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek EnvMgr.getInitialEnvironment(), 3672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StoreMgr->getInitialStore(InitLoc), 3682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek GDMFactory.getEmptyMap()); 3692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(State); 3712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3738bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::getPersistentStateWithGDM( 3748bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef FromState, 3758bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef GDMState) { 376a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ProgramState NewState(*FromState); 3772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.GDM = GDMState->GDM; 3782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewState); 3792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 3802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3818bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) { 3822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek llvm::FoldingSetNodeID ID; 3842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek State.Profile(ID); 3852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void *InsertPos; 3862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 3882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return I; 3892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 3906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ProgramState *newState = nullptr; 3912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!freeStates.empty()) { 3922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek newState = freeStates.back(); 39387d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar freeStates.pop_back(); 3942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 3952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek else { 3962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 3972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 3982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek new (newState) ProgramState(State); 3992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek StateSet.InsertNode(newState, InsertPos); 4002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return newState; 4012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4038bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const { 404a5888f61be9f8d76e9b48a453dbced50523bd2e0Argyrios Kyrtzidis ProgramState NewSt(*this); 4052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.setStore(store); 4062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getStateManager().getPersistentState(NewSt); 4072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4082fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4092fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid ProgramState::setStore(const StoreRef &newStore) { 4102fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek Store newStoreStore = newStore.getStore(); 4112fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (newStoreStore) 4122fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 4132fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (store) 4142fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek stateMgr->getStoreManager().decrementReferenceCount(store); 4152fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek store = newStoreStore; 4162fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4172fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4182fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4192fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// State pretty-printing. 4202fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4225eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekvoid ProgramState::print(raw_ostream &Out, 423dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose const char *NL, const char *Sep) const { 4242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Print the store. 4252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramStateManager &Mgr = getStateManager(); 426dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getStoreManager().print(getStore(), Out, NL, Sep); 4272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4285eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek // Print out the environment. 4295eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek Env.print(Out, NL, Sep); 4302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4315eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek // Print out the constraints. 432dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getConstraintManager().print(this, Out, NL, Sep); 4332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // Print checker-specific data. 435dbd658e139b3e0bf084f75feaea8d844af9e319fJordy Rose Mgr.getOwningEngine()->printState(Out, this, NL, Sep); 4362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4385eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekvoid ProgramState::printDOT(raw_ostream &Out) const { 4395eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek print(Out, "\\l", "\\|"); 4402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4424967a710c84587c654b56c828382219c3937dacbPirama Arumuga NainarLLVM_DUMP_METHOD void ProgramState::dump() const { 4435eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek print(llvm::errs()); 4442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 446be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaksvoid ProgramState::printTaint(raw_ostream &Out, 447be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks const char *NL, const char *Sep) const { 448be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks TaintMapImpl TM = get<TaintMap>(); 449be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 450be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks if (!TM.isEmpty()) 451be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks Out <<"Tainted Symbols:" << NL; 452be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 453be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks for (TaintMapImpl::iterator I = TM.begin(), E = TM.end(); I != E; ++I) { 454be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks Out << I->first << " : " << I->second << NL; 455be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks } 456be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks} 457be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 458be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaksvoid ProgramState::dumpTaint() const { 459be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks printTaint(llvm::errs()); 460be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks} 461be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 4622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4632fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek// Generic Data Map. 4642fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek//===----------------------------------------------------------------------===// 4652fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4662fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid *const* ProgramState::FindGDM(void *K) const { 4672fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return GDM.lookup(K); 4682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekvoid* 4712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted KremenekProgramStateManager::FindGDMContext(void *K, 4722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void *(*CreateContext)(llvm::BumpPtrAllocator&), 4732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek void (*DeleteContext)(void*)) { 4742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 4762fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!p.first) { 4772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek p.first = CreateContext(Alloc); 4782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek p.second = DeleteContext; 4792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 4802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return p.first; 4822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4848bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){ 4852fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap M1 = St->getGDM(); 4862fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 4872fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (M1 == M2) 4892fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return St; 4902fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4912fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewSt = *St; 4922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewSt.GDM = M2; 4932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewSt); 4942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 4952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 4968bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { 4972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap OldM = state->getGDM(); 4982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 4992fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5002fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (NewM == OldM) 5012fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return state; 5022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ProgramState NewState = *state; 5042fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek NewState.GDM = NewM; 5052fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return getPersistentState(NewState); 5062fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5072fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 508d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labathbool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { 509d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath bool wasVisited = !visited.insert(val.getCVData()).second; 510d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath if (wasVisited) 511d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath return true; 512d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath 513d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 514d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath // FIXME: We don't really want to use getBaseRegion() here because pointer 515d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath // arithmetic doesn't apply, but scanReachableSymbols only accepts base 516d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath // regions right now. 517d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath const MemRegion *R = val.getRegion()->getBaseRegion(); 518d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath return StoreMgr.scanReachableSymbols(val.getStore(), R, *this); 519d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath} 520d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath 5212fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 5222fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 5232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!scan(*I)) 5242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 5252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(const SymExpr *sym) { 530d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath bool wasVisited = !visited.insert(sym).second; 531d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath if (wasVisited) 5322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 53387d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 53476462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks if (!visitor.VisitSymbol(sym)) 53576462f00854171d2aa3ebc34f9aac1c60021b0eaAnna Zaks return false; 53687d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 537a91efb14cbf6af999dee02d9b611a57c7b52e209Anna Zaks // TODO: should be rewritten using SymExpr::symbol_iterator. 5382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek switch (sym->getKind()) { 5394967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::SymbolRegionValueKind: 5404967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::SymbolConjuredKind: 5414967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::SymbolDerivedKind: 5424967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::SymbolExtentKind: 5434967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::SymbolMetadataKind: 5442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek break; 5454967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::SymbolCastKind: 546aace9ef279be3dadd53b481aee568bd7701178b4Anna Zaks return scan(cast<SymbolCast>(sym)->getOperand()); 5474967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::SymIntExprKind: 5482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(cast<SymIntExpr>(sym)->getLHS()); 5494967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::IntSymExprKind: 55024d052cdb75d3c1afa5bef32eacaa224e9d0b85dAnna Zaks return scan(cast<IntSymExpr>(sym)->getRHS()); 5514967a710c84587c654b56c828382219c3937dacbPirama Arumuga Nainar case SymExpr::SymSymExprKind: { 5522fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const SymSymExpr *x = cast<SymSymExpr>(sym); 5532fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(x->getLHS()) && scan(x->getRHS()); 5542fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5552fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 5562fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5572fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5582fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5592fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(SVal val) { 560dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>()) 5612fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(X->getRegion()); 5622fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 563dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::LazyCompoundVal> X = 564d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath val.getAs<nonloc::LazyCompoundVal>()) 565d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath return scan(*X); 5660d53ab4024488d0c6cd283992be3fd4b67099bd3Jordan Rose 567dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>()) 5682fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(X->getLoc()); 5692fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5702fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (SymbolRef Sym = val.getAsSymbol()) 5712fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(Sym); 5722fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5732fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SymExpr *Sym = val.getAsSymbolicExpression()) 5742fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(Sym); 5752fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 576dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie if (Optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>()) 5772fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return scan(*X); 5782fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5792fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 5802fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 5812fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5822fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ScanReachableSymbols::scan(const MemRegion *R) { 5832fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (isa<MemSpaceRegion>(R)) 5842fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 58587d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 586d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath bool wasVisited = !visited.insert(R).second; 587d207f55cd58054aab77edca35b3e7f645738dfe2Pavel Labath if (wasVisited) 5882fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 58987d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 5907f9b1d963d4b7e2faff7305733e3453130b402feTed Kremenek if (!visitor.VisitMemRegion(R)) 5917f9b1d963d4b7e2faff7305733e3453130b402feTed Kremenek return false; 5922fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5932fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If this is a symbolic region, visit the symbol for the region. 5942fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 5952fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!visitor.VisitSymbol(SR->getSymbol())) 5962fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 5972fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 5982fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek // If this is a subregion, also visit the parent regions. 599e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (const SubRegion *SR = dyn_cast<SubRegion>(R)) { 600e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose const MemRegion *Super = SR->getSuperRegion(); 601e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (!scan(Super)) 6022fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6032fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 604e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose // When we reach the topmost region, scan all symbols in it. 605e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (isa<MemSpaceRegion>(Super)) { 606e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 607e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this)) 608e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose return false; 609e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 610e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose } 611e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose 6127fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek // Regions captured by a block are also implicitly reachable. 6137fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) { 6147fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), 6157fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek E = BDR->referenced_vars_end(); 6167fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek for ( ; I != E; ++I) { 6177fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek if (!scan(I.getCapturedRegion())) 6187fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek return false; 6197fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek } 6207fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek } 6217fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek 622e0d24eb1060a213ec9820dc02c45f26b2d5b348bJordan Rose return true; 6232fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6242fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6252fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 6262fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6272fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return S.scan(val); 6282fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6292fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6302fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 6312fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolVisitor &visitor) const { 6322fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6332fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for ( ; I != E; ++I) { 6342fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!S.scan(*I)) 6352fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6362fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 6372fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6382fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 6392fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek 6402fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenekbool ProgramState::scanReachableSymbols(const MemRegion * const *I, 6412fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek const MemRegion * const *E, 6422fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek SymbolVisitor &visitor) const { 6432fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek ScanReachableSymbols S(this, visitor); 6442fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek for ( ; I != E; ++I) { 6452fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek if (!S.scan(*I)) 6462fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return false; 6472fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek } 6482fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek return true; 6492fde35d89320a92cb5ec5ec7b0603697aa17b089Ted Kremenek} 650ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 6518bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::addTaint(const Stmt *S, 6525eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek const LocationContext *LCtx, 653ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks TaintTagType Kind) const { 654d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks if (const Expr *E = dyn_cast_or_null<Expr>(S)) 655d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks S = E->IgnoreParens(); 656d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks 6575eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SymbolRef Sym = getSVal(S, LCtx).getAsSymbol(); 658e55a22b917327651178ddea36b3615f579681eeaAnna Zaks if (Sym) 659e55a22b917327651178ddea36b3615f579681eeaAnna Zaks return addTaint(Sym, Kind); 660e55a22b917327651178ddea36b3615f579681eeaAnna Zaks 6615eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek const MemRegion *R = getSVal(S, LCtx).getAsRegion(); 66228fd98d66dab4569316de2b5881d91b534a42461Anna Zaks addTaint(R, Kind); 663e55a22b917327651178ddea36b3615f579681eeaAnna Zaks 664e55a22b917327651178ddea36b3615f579681eeaAnna Zaks // Cannot add taint, so just return the state. 665e55a22b917327651178ddea36b3615f579681eeaAnna Zaks return this; 666ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 667ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 6688bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::addTaint(const MemRegion *R, 66928fd98d66dab4569316de2b5881d91b534a42461Anna Zaks TaintTagType Kind) const { 67028fd98d66dab4569316de2b5881d91b534a42461Anna Zaks if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R)) 67128fd98d66dab4569316de2b5881d91b534a42461Anna Zaks return addTaint(SR->getSymbol(), Kind); 67228fd98d66dab4569316de2b5881d91b534a42461Anna Zaks return this; 67328fd98d66dab4569316de2b5881d91b534a42461Anna Zaks} 67428fd98d66dab4569316de2b5881d91b534a42461Anna Zaks 6758bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef ProgramState::addTaint(SymbolRef Sym, 676ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks TaintTagType Kind) const { 677be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks // If this is a symbol cast, remove the cast before adding the taint. Taint 678be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks // is cast agnostic. 679be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) 680be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks Sym = SC->getOperand(); 681be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 6828bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef NewState = set<TaintMap>(Sym, Kind); 683ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks assert(NewState); 684ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks return NewState; 685ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 686ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 6875eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekbool ProgramState::isTainted(const Stmt *S, const LocationContext *LCtx, 6885eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek TaintTagType Kind) const { 689d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks if (const Expr *E = dyn_cast_or_null<Expr>(S)) 690d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks S = E->IgnoreParens(); 691d3d8548e75f3fb6db53ed0927c1df30d78f4ce1dAnna Zaks 6925eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek SVal val = getSVal(S, LCtx); 693b39c5b4ddc9dcc7d9845c6c637e03e83302f8538Anna Zaks return isTainted(val, Kind); 694ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 695ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 696ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaksbool ProgramState::isTainted(SVal V, TaintTagType Kind) const { 697dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SymExpr *Sym = V.getAsSymExpr()) 698dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(Sym, Kind); 699777d706547ebc751d998134774d9d5388fff8e02Anna Zaks if (const MemRegion *Reg = V.getAsRegion()) 700777d706547ebc751d998134774d9d5388fff8e02Anna Zaks return isTainted(Reg, Kind); 701dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 702dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks} 703dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 704dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaksbool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const { 705dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (!Reg) 706dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 707dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 708dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // Element region (array element) is tainted if either the base or the offset 709dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // are tainted. 710dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) 711dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(ER->getSuperRegion(), K) || isTainted(ER->getIndex(), K); 712dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 713dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) 714dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(SR->getSymbol(), K); 715dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 716dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) 717dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return isTainted(ER->getSuperRegion(), K); 718dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks 719dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks return false; 720ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks} 721ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks 7229f03b62036a7abc0a227b17f4a49b9eefced9450Anna Zaksbool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const { 723ee081c4051cde4bd44475b5e29d695008c15a9ccAnna Zaks if (!Sym) 724ee081c4051cde4bd44475b5e29d695008c15a9ccAnna Zaks return false; 72587d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 726dcf06fa1fbb9c018e152629ef3f3fa7b1acffe7aAnna Zaks // Traverse all the symbols this symbol depends on to see if any are tainted. 7271d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks bool Tainted = false; 7281d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); 7291d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks SI != SE; ++SI) { 7300073a5c7ce38e98365c00921316030627b3d129fJordan Rose if (!isa<SymbolData>(*SI)) 7310073a5c7ce38e98365c00921316030627b3d129fJordan Rose continue; 73287d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 7331d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks const TaintTagType *Tag = get<TaintMap>(*SI); 7341d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks Tainted = (Tag && *Tag == Kind); 7351d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks 7361d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks // If this is a SymbolDerived with a tainted parent, it's also tainted. 7371d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) 7381d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks Tainted = Tainted || isTainted(SD->getParentSymbol(), Kind); 7395fc7def35ee858791e591d005b4ae343632ca931Anna Zaks 7405fc7def35ee858791e591d005b4ae343632ca931Anna Zaks // If memory region is tainted, data is also tainted. 7415fc7def35ee858791e591d005b4ae343632ca931Anna Zaks if (const SymbolRegionValue *SRV = dyn_cast<SymbolRegionValue>(*SI)) 7425fc7def35ee858791e591d005b4ae343632ca931Anna Zaks Tainted = Tainted || isTainted(SRV->getRegion(), Kind); 7435fc7def35ee858791e591d005b4ae343632ca931Anna Zaks 744be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks // If If this is a SymbolCast from a tainted value, it's also tainted. 745be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks if (const SymbolCast *SC = dyn_cast<SymbolCast>(*SI)) 746be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks Tainted = Tainted || isTainted(SC->getOperand(), Kind); 747be97b7edb112520d764c24e8b9a159cdc692bcb6Anna Zaks 7481d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks if (Tainted) 7491d1d515b2bafb59d624883d8fdda97d4b7dba0cbAnna Zaks return true; 750ceac1d6e0521161adf7ac9834b1a7ad79d73fea4Anna Zaks } 751148fee988e32efcad45ecf7b3bf714880c657ddaAnna Zaks 75287d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar return Tainted; 7532d18419a7c8f9a2975d4ed74a202de6467308ad1Anna Zaks} 754148fee988e32efcad45ecf7b3bf714880c657ddaAnna Zaks 755