ProgramState.cpp revision 261991
1226586Sdim//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--= 2226586Sdim// 3226586Sdim// The LLVM Compiler Infrastructure 4226586Sdim// 5226586Sdim// This file is distributed under the University of Illinois Open Source 6226586Sdim// License. See LICENSE.TXT for details. 7226586Sdim// 8226586Sdim//===----------------------------------------------------------------------===// 9226586Sdim// 10226586Sdim// This file implements ProgramState and ProgramStateManager. 11226586Sdim// 12226586Sdim//===----------------------------------------------------------------------===// 13226586Sdim 14249423Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 15226586Sdim#include "clang/Analysis/CFG.h" 16239462Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 17226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 18226586Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 19234353Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h" 20226586Sdim#include "llvm/Support/raw_ostream.h" 21226586Sdim 22226586Sdimusing namespace clang; 23226586Sdimusing namespace ento; 24226586Sdim 25234353Sdimnamespace clang { namespace ento { 26234353Sdim/// Increments the number of times this state is referenced. 27234353Sdim 28234353Sdimvoid ProgramStateRetain(const ProgramState *state) { 29234353Sdim ++const_cast<ProgramState*>(state)->refCount; 30234353Sdim} 31234353Sdim 32234353Sdim/// Decrement the number of times this state is referenced. 33234353Sdimvoid ProgramStateRelease(const ProgramState *state) { 34234353Sdim assert(state->refCount > 0); 35234353Sdim ProgramState *s = const_cast<ProgramState*>(state); 36234353Sdim if (--s->refCount == 0) { 37234353Sdim ProgramStateManager &Mgr = s->getStateManager(); 38234353Sdim Mgr.StateSet.RemoveNode(s); 39234353Sdim s->~ProgramState(); 40234353Sdim Mgr.freeStates.push_back(s); 41234353Sdim } 42234353Sdim} 43234353Sdim}} 44234353Sdim 45226586SdimProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 46226586Sdim StoreRef st, GenericDataMap gdm) 47226586Sdim : stateMgr(mgr), 48226586Sdim Env(env), 49226586Sdim store(st.getStore()), 50226586Sdim GDM(gdm), 51226586Sdim refCount(0) { 52226586Sdim stateMgr->getStoreManager().incrementReferenceCount(store); 53226586Sdim} 54226586Sdim 55226586SdimProgramState::ProgramState(const ProgramState &RHS) 56226586Sdim : llvm::FoldingSetNode(), 57226586Sdim stateMgr(RHS.stateMgr), 58226586Sdim Env(RHS.Env), 59226586Sdim store(RHS.store), 60226586Sdim GDM(RHS.GDM), 61226586Sdim refCount(0) { 62226586Sdim stateMgr->getStoreManager().incrementReferenceCount(store); 63226586Sdim} 64226586Sdim 65226586SdimProgramState::~ProgramState() { 66226586Sdim if (store) 67226586Sdim stateMgr->getStoreManager().decrementReferenceCount(store); 68226586Sdim} 69226586Sdim 70239462SdimProgramStateManager::ProgramStateManager(ASTContext &Ctx, 71239462Sdim StoreManagerCreator CreateSMgr, 72239462Sdim ConstraintManagerCreator CreateCMgr, 73239462Sdim llvm::BumpPtrAllocator &alloc, 74243830Sdim SubEngine *SubEng) 75243830Sdim : Eng(SubEng), EnvMgr(alloc), GDMFactory(alloc), 76239462Sdim svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), 77239462Sdim CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) { 78239462Sdim StoreMgr.reset((*CreateSMgr)(*this)); 79239462Sdim ConstraintMgr.reset((*CreateCMgr)(*this, SubEng)); 80239462Sdim} 81239462Sdim 82239462Sdim 83226586SdimProgramStateManager::~ProgramStateManager() { 84226586Sdim for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 85226586Sdim I!=E; ++I) 86226586Sdim I->second.second(I->second.first); 87226586Sdim} 88226586Sdim 89234353SdimProgramStateRef 90234353SdimProgramStateManager::removeDeadBindings(ProgramStateRef state, 91226586Sdim const StackFrameContext *LCtx, 92226586Sdim SymbolReaper& SymReaper) { 93226586Sdim 94226586Sdim // This code essentially performs a "mark-and-sweep" of the VariableBindings. 95226586Sdim // The roots are any Block-level exprs and Decls that our liveness algorithm 96226586Sdim // tells us are live. We then see what Decls they may reference, and keep 97226586Sdim // those around. This code more than likely can be made faster, and the 98226586Sdim // frequency of which this method is called should be experimented with 99226586Sdim // for optimum performance. 100226586Sdim ProgramState NewState = *state; 101226586Sdim 102226586Sdim NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 103226586Sdim 104226586Sdim // Clean up the store. 105226586Sdim StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 106226586Sdim SymReaper); 107226586Sdim NewState.setStore(newStore); 108226586Sdim SymReaper.setReapedStore(newStore); 109226586Sdim 110243830Sdim ProgramStateRef Result = getPersistentState(NewState); 111243830Sdim return ConstraintMgr->removeDeadBindings(Result, SymReaper); 112226586Sdim} 113226586Sdim 114243830SdimProgramStateRef ProgramState::bindLoc(Loc LV, SVal V, bool notifyChanges) const { 115226586Sdim ProgramStateManager &Mgr = getStateManager(); 116234353Sdim ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 117226586Sdim LV, V)); 118226586Sdim const MemRegion *MR = LV.getAsRegion(); 119243830Sdim if (MR && Mgr.getOwningEngine() && notifyChanges) 120226586Sdim return Mgr.getOwningEngine()->processRegionChange(newState, MR); 121226586Sdim 122226586Sdim return newState; 123226586Sdim} 124226586Sdim 125234353SdimProgramStateRef ProgramState::bindDefault(SVal loc, SVal V) const { 126226586Sdim ProgramStateManager &Mgr = getStateManager(); 127249423Sdim const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion(); 128226586Sdim const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V); 129234353Sdim ProgramStateRef new_state = makeWithStore(newStore); 130226586Sdim return Mgr.getOwningEngine() ? 131226586Sdim Mgr.getOwningEngine()->processRegionChange(new_state, R) : 132226586Sdim new_state; 133226586Sdim} 134226586Sdim 135249423Sdimtypedef ArrayRef<const MemRegion *> RegionList; 136249423Sdimtypedef ArrayRef<SVal> ValueList; 137249423Sdim 138234353SdimProgramStateRef 139249423SdimProgramState::invalidateRegions(RegionList Regions, 140261991Sdim const Expr *E, unsigned Count, 141261991Sdim const LocationContext *LCtx, 142261991Sdim bool CausedByPointerEscape, 143261991Sdim InvalidatedSymbols *IS, 144261991Sdim const CallEvent *Call, 145261991Sdim RegionAndSymbolInvalidationTraits *ITraits) const { 146249423Sdim SmallVector<SVal, 8> Values; 147249423Sdim for (RegionList::const_iterator I = Regions.begin(), 148249423Sdim End = Regions.end(); I != End; ++I) 149249423Sdim Values.push_back(loc::MemRegionVal(*I)); 150249423Sdim 151249423Sdim return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, 152261991Sdim IS, ITraits, Call); 153226586Sdim} 154226586Sdim 155249423SdimProgramStateRef 156249423SdimProgramState::invalidateRegions(ValueList Values, 157261991Sdim const Expr *E, unsigned Count, 158261991Sdim const LocationContext *LCtx, 159261991Sdim bool CausedByPointerEscape, 160261991Sdim InvalidatedSymbols *IS, 161261991Sdim const CallEvent *Call, 162261991Sdim RegionAndSymbolInvalidationTraits *ITraits) const { 163261991Sdim 164249423Sdim return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, 165261991Sdim IS, ITraits, Call); 166249423Sdim} 167249423Sdim 168249423SdimProgramStateRef 169249423SdimProgramState::invalidateRegionsImpl(ValueList Values, 170226586Sdim const Expr *E, unsigned Count, 171234353Sdim const LocationContext *LCtx, 172249423Sdim bool CausedByPointerEscape, 173261991Sdim InvalidatedSymbols *IS, 174261991Sdim RegionAndSymbolInvalidationTraits *ITraits, 175261991Sdim const CallEvent *Call) const { 176226586Sdim ProgramStateManager &Mgr = getStateManager(); 177226586Sdim SubEngine* Eng = Mgr.getOwningEngine(); 178249423Sdim InvalidatedSymbols ConstIS; 179249423Sdim 180261991Sdim InvalidatedSymbols Invalidated; 181261991Sdim if (!IS) 182261991Sdim IS = &Invalidated; 183261991Sdim 184261991Sdim RegionAndSymbolInvalidationTraits ITraitsLocal; 185261991Sdim if (!ITraits) 186261991Sdim ITraits = &ITraitsLocal; 187261991Sdim 188249423Sdim if (Eng) { 189249423Sdim StoreManager::InvalidatedRegions TopLevelInvalidated; 190226586Sdim StoreManager::InvalidatedRegions Invalidated; 191226586Sdim const StoreRef &newStore 192261991Sdim = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, 193261991Sdim *IS, *ITraits, &TopLevelInvalidated, 194249423Sdim &Invalidated); 195249423Sdim 196234353Sdim ProgramStateRef newState = makeWithStore(newStore); 197249423Sdim 198249423Sdim if (CausedByPointerEscape) { 199261991Sdim newState = Eng->notifyCheckersOfPointerEscape(newState, IS, 200249423Sdim TopLevelInvalidated, 201261991Sdim Invalidated, Call, 202261991Sdim *ITraits); 203249423Sdim } 204249423Sdim 205261991Sdim return Eng->processRegionChanges(newState, IS, TopLevelInvalidated, 206261991Sdim Invalidated, Call); 207226586Sdim } 208226586Sdim 209226586Sdim const StoreRef &newStore = 210261991Sdim Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, 211261991Sdim *IS, *ITraits, NULL, NULL); 212226586Sdim return makeWithStore(newStore); 213226586Sdim} 214226586Sdim 215243830SdimProgramStateRef ProgramState::killBinding(Loc LV) const { 216249423Sdim assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead."); 217226586Sdim 218226586Sdim Store OldStore = getStore(); 219243830Sdim const StoreRef &newStore = 220243830Sdim getStateManager().StoreMgr->killBinding(OldStore, LV); 221226586Sdim 222226586Sdim if (newStore.getStore() == OldStore) 223226586Sdim return this; 224226586Sdim 225226586Sdim return makeWithStore(newStore); 226226586Sdim} 227226586Sdim 228234353SdimProgramStateRef 229239462SdimProgramState::enterStackFrame(const CallEvent &Call, 230239462Sdim const StackFrameContext *CalleeCtx) const { 231239462Sdim const StoreRef &NewStore = 232239462Sdim getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx); 233239462Sdim return makeWithStore(NewStore); 234226586Sdim} 235226586Sdim 236226586SdimSVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 237226586Sdim // We only want to do fetches from regions that we can actually bind 238226586Sdim // values. For example, SymbolicRegions of type 'id<...>' cannot 239226586Sdim // have direct bindings (but their can be bindings on their subregions). 240226586Sdim if (!R->isBoundable()) 241226586Sdim return UnknownVal(); 242226586Sdim 243226586Sdim if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 244226586Sdim QualType T = TR->getValueType(); 245251662Sdim if (Loc::isLocType(T) || T->isIntegralOrEnumerationType()) 246226586Sdim return getSVal(R); 247226586Sdim } 248226586Sdim 249226586Sdim return UnknownVal(); 250226586Sdim} 251226586Sdim 252226586SdimSVal ProgramState::getSVal(Loc location, QualType T) const { 253226586Sdim SVal V = getRawSVal(cast<Loc>(location), T); 254226586Sdim 255226586Sdim // If 'V' is a symbolic value that is *perfectly* constrained to 256226586Sdim // be a constant value, use that value instead to lessen the burden 257226586Sdim // on later analysis stages (so we have less symbolic values to reason 258226586Sdim // about). 259226586Sdim if (!T.isNull()) { 260226586Sdim if (SymbolRef sym = V.getAsSymbol()) { 261243830Sdim if (const llvm::APSInt *Int = getStateManager() 262243830Sdim .getConstraintManager() 263243830Sdim .getSymVal(this, sym)) { 264226586Sdim // FIXME: Because we don't correctly model (yet) sign-extension 265226586Sdim // and truncation of symbolic values, we need to convert 266226586Sdim // the integer value to the correct signedness and bitwidth. 267226586Sdim // 268226586Sdim // This shows up in the following: 269226586Sdim // 270226586Sdim // char foo(); 271226586Sdim // unsigned x = foo(); 272226586Sdim // if (x == 54) 273226586Sdim // ... 274226586Sdim // 275226586Sdim // The symbolic value stored to 'x' is actually the conjured 276226586Sdim // symbol for the call to foo(); the type of that symbol is 'char', 277226586Sdim // not unsigned. 278226586Sdim const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 279226586Sdim 280249423Sdim if (V.getAs<Loc>()) 281226586Sdim return loc::ConcreteInt(NewV); 282226586Sdim else 283226586Sdim return nonloc::ConcreteInt(NewV); 284226586Sdim } 285226586Sdim } 286226586Sdim } 287226586Sdim 288226586Sdim return V; 289226586Sdim} 290226586Sdim 291234353SdimProgramStateRef ProgramState::BindExpr(const Stmt *S, 292234353Sdim const LocationContext *LCtx, 293234353Sdim SVal V, bool Invalidate) const{ 294234353Sdim Environment NewEnv = 295234353Sdim getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V, 296234353Sdim Invalidate); 297226586Sdim if (NewEnv == Env) 298226586Sdim return this; 299226586Sdim 300226586Sdim ProgramState NewSt = *this; 301226586Sdim NewSt.Env = NewEnv; 302226586Sdim return getStateManager().getPersistentState(NewSt); 303226586Sdim} 304226586Sdim 305234353SdimProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 306226586Sdim DefinedOrUnknownSVal UpperBound, 307234353Sdim bool Assumption, 308234353Sdim QualType indexTy) const { 309226586Sdim if (Idx.isUnknown() || UpperBound.isUnknown()) 310226586Sdim return this; 311226586Sdim 312226586Sdim // Build an expression for 0 <= Idx < UpperBound. 313226586Sdim // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 314226586Sdim // FIXME: This should probably be part of SValBuilder. 315226586Sdim ProgramStateManager &SM = getStateManager(); 316226586Sdim SValBuilder &svalBuilder = SM.getSValBuilder(); 317226586Sdim ASTContext &Ctx = svalBuilder.getContext(); 318226586Sdim 319226586Sdim // Get the offset: the minimum value of the array index type. 320226586Sdim BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 321226586Sdim // FIXME: This should be using ValueManager::ArrayindexTy...somehow. 322234353Sdim if (indexTy.isNull()) 323234353Sdim indexTy = Ctx.IntTy; 324226586Sdim nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 325226586Sdim 326226586Sdim // Adjust the index. 327226586Sdim SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 328249423Sdim Idx.castAs<NonLoc>(), Min, indexTy); 329226586Sdim if (newIdx.isUnknownOrUndef()) 330226586Sdim return this; 331226586Sdim 332226586Sdim // Adjust the upper bound. 333226586Sdim SVal newBound = 334249423Sdim svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(), 335226586Sdim Min, indexTy); 336226586Sdim 337226586Sdim if (newBound.isUnknownOrUndef()) 338226586Sdim return this; 339226586Sdim 340226586Sdim // Build the actual comparison. 341249423Sdim SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(), 342249423Sdim newBound.castAs<NonLoc>(), Ctx.IntTy); 343226586Sdim if (inBound.isUnknownOrUndef()) 344226586Sdim return this; 345226586Sdim 346226586Sdim // Finally, let the constraint manager take care of it. 347226586Sdim ConstraintManager &CM = SM.getConstraintManager(); 348249423Sdim return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption); 349226586Sdim} 350226586Sdim 351249423SdimConditionTruthVal ProgramState::isNull(SVal V) const { 352249423Sdim if (V.isZeroConstant()) 353249423Sdim return true; 354249423Sdim 355249423Sdim if (V.isConstant()) 356249423Sdim return false; 357249423Sdim 358251662Sdim SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true); 359249423Sdim if (!Sym) 360249423Sdim return ConditionTruthVal(); 361249423Sdim 362249423Sdim return getStateManager().ConstraintMgr->isNull(this, Sym); 363249423Sdim} 364249423Sdim 365234353SdimProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 366226586Sdim ProgramState State(this, 367226586Sdim EnvMgr.getInitialEnvironment(), 368226586Sdim StoreMgr->getInitialStore(InitLoc), 369226586Sdim GDMFactory.getEmptyMap()); 370226586Sdim 371226586Sdim return getPersistentState(State); 372226586Sdim} 373226586Sdim 374234353SdimProgramStateRef ProgramStateManager::getPersistentStateWithGDM( 375234353Sdim ProgramStateRef FromState, 376234353Sdim ProgramStateRef GDMState) { 377234353Sdim ProgramState NewState(*FromState); 378226586Sdim NewState.GDM = GDMState->GDM; 379226586Sdim return getPersistentState(NewState); 380226586Sdim} 381226586Sdim 382234353SdimProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) { 383226586Sdim 384226586Sdim llvm::FoldingSetNodeID ID; 385226586Sdim State.Profile(ID); 386226586Sdim void *InsertPos; 387226586Sdim 388226586Sdim if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 389226586Sdim return I; 390226586Sdim 391226586Sdim ProgramState *newState = 0; 392226586Sdim if (!freeStates.empty()) { 393226586Sdim newState = freeStates.back(); 394226586Sdim freeStates.pop_back(); 395226586Sdim } 396226586Sdim else { 397226586Sdim newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 398226586Sdim } 399226586Sdim new (newState) ProgramState(State); 400226586Sdim StateSet.InsertNode(newState, InsertPos); 401226586Sdim return newState; 402226586Sdim} 403226586Sdim 404234353SdimProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const { 405234353Sdim ProgramState NewSt(*this); 406226586Sdim NewSt.setStore(store); 407226586Sdim return getStateManager().getPersistentState(NewSt); 408226586Sdim} 409226586Sdim 410226586Sdimvoid ProgramState::setStore(const StoreRef &newStore) { 411226586Sdim Store newStoreStore = newStore.getStore(); 412226586Sdim if (newStoreStore) 413226586Sdim stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 414226586Sdim if (store) 415226586Sdim stateMgr->getStoreManager().decrementReferenceCount(store); 416226586Sdim store = newStoreStore; 417226586Sdim} 418226586Sdim 419226586Sdim//===----------------------------------------------------------------------===// 420226586Sdim// State pretty-printing. 421226586Sdim//===----------------------------------------------------------------------===// 422226586Sdim 423234353Sdimvoid ProgramState::print(raw_ostream &Out, 424226586Sdim const char *NL, const char *Sep) const { 425226586Sdim // Print the store. 426226586Sdim ProgramStateManager &Mgr = getStateManager(); 427226586Sdim Mgr.getStoreManager().print(getStore(), Out, NL, Sep); 428226586Sdim 429234353Sdim // Print out the environment. 430234353Sdim Env.print(Out, NL, Sep); 431226586Sdim 432234353Sdim // Print out the constraints. 433234353Sdim Mgr.getConstraintManager().print(this, Out, NL, Sep); 434226586Sdim 435234353Sdim // Print checker-specific data. 436234353Sdim Mgr.getOwningEngine()->printState(Out, this, NL, Sep); 437234353Sdim} 438226586Sdim 439234353Sdimvoid ProgramState::printDOT(raw_ostream &Out) const { 440234353Sdim print(Out, "\\l", "\\|"); 441234353Sdim} 442226586Sdim 443234353Sdimvoid ProgramState::dump() const { 444234353Sdim print(llvm::errs()); 445234353Sdim} 446226586Sdim 447234353Sdimvoid ProgramState::printTaint(raw_ostream &Out, 448234353Sdim const char *NL, const char *Sep) const { 449234353Sdim TaintMapImpl TM = get<TaintMap>(); 450226586Sdim 451234353Sdim if (!TM.isEmpty()) 452234353Sdim Out <<"Tainted Symbols:" << NL; 453226586Sdim 454234353Sdim for (TaintMapImpl::iterator I = TM.begin(), E = TM.end(); I != E; ++I) { 455234353Sdim Out << I->first << " : " << I->second << NL; 456226586Sdim } 457226586Sdim} 458226586Sdim 459234353Sdimvoid ProgramState::dumpTaint() const { 460234353Sdim printTaint(llvm::errs()); 461226586Sdim} 462226586Sdim 463226586Sdim//===----------------------------------------------------------------------===// 464226586Sdim// Generic Data Map. 465226586Sdim//===----------------------------------------------------------------------===// 466226586Sdim 467226586Sdimvoid *const* ProgramState::FindGDM(void *K) const { 468226586Sdim return GDM.lookup(K); 469226586Sdim} 470226586Sdim 471226586Sdimvoid* 472226586SdimProgramStateManager::FindGDMContext(void *K, 473226586Sdim void *(*CreateContext)(llvm::BumpPtrAllocator&), 474226586Sdim void (*DeleteContext)(void*)) { 475226586Sdim 476226586Sdim std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 477226586Sdim if (!p.first) { 478226586Sdim p.first = CreateContext(Alloc); 479226586Sdim p.second = DeleteContext; 480226586Sdim } 481226586Sdim 482226586Sdim return p.first; 483226586Sdim} 484226586Sdim 485234353SdimProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){ 486226586Sdim ProgramState::GenericDataMap M1 = St->getGDM(); 487226586Sdim ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 488226586Sdim 489226586Sdim if (M1 == M2) 490226586Sdim return St; 491226586Sdim 492226586Sdim ProgramState NewSt = *St; 493226586Sdim NewSt.GDM = M2; 494226586Sdim return getPersistentState(NewSt); 495226586Sdim} 496226586Sdim 497234353SdimProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { 498226586Sdim ProgramState::GenericDataMap OldM = state->getGDM(); 499226586Sdim ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 500226586Sdim 501226586Sdim if (NewM == OldM) 502226586Sdim return state; 503226586Sdim 504226586Sdim ProgramState NewState = *state; 505226586Sdim NewState.GDM = NewM; 506226586Sdim return getPersistentState(NewState); 507226586Sdim} 508226586Sdim 509261991Sdimbool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { 510261991Sdim bool wasVisited = !visited.insert(val.getCVData()).second; 511261991Sdim if (wasVisited) 512261991Sdim return true; 513261991Sdim 514261991Sdim StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 515261991Sdim // FIXME: We don't really want to use getBaseRegion() here because pointer 516261991Sdim // arithmetic doesn't apply, but scanReachableSymbols only accepts base 517261991Sdim // regions right now. 518261991Sdim const MemRegion *R = val.getRegion()->getBaseRegion(); 519261991Sdim return StoreMgr.scanReachableSymbols(val.getStore(), R, *this); 520261991Sdim} 521261991Sdim 522226586Sdimbool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 523226586Sdim for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 524226586Sdim if (!scan(*I)) 525226586Sdim return false; 526226586Sdim 527226586Sdim return true; 528226586Sdim} 529226586Sdim 530226586Sdimbool ScanReachableSymbols::scan(const SymExpr *sym) { 531261991Sdim bool wasVisited = !visited.insert(sym).second; 532261991Sdim if (wasVisited) 533226586Sdim return true; 534226586Sdim 535234353Sdim if (!visitor.VisitSymbol(sym)) 536234353Sdim return false; 537226586Sdim 538234353Sdim // TODO: should be rewritten using SymExpr::symbol_iterator. 539226586Sdim switch (sym->getKind()) { 540226586Sdim case SymExpr::RegionValueKind: 541226586Sdim case SymExpr::ConjuredKind: 542226586Sdim case SymExpr::DerivedKind: 543226586Sdim case SymExpr::ExtentKind: 544226586Sdim case SymExpr::MetadataKind: 545226586Sdim break; 546234353Sdim case SymExpr::CastSymbolKind: 547234353Sdim return scan(cast<SymbolCast>(sym)->getOperand()); 548226586Sdim case SymExpr::SymIntKind: 549226586Sdim return scan(cast<SymIntExpr>(sym)->getLHS()); 550234353Sdim case SymExpr::IntSymKind: 551234353Sdim return scan(cast<IntSymExpr>(sym)->getRHS()); 552226586Sdim case SymExpr::SymSymKind: { 553226586Sdim const SymSymExpr *x = cast<SymSymExpr>(sym); 554226586Sdim return scan(x->getLHS()) && scan(x->getRHS()); 555226586Sdim } 556226586Sdim } 557226586Sdim return true; 558226586Sdim} 559226586Sdim 560226586Sdimbool ScanReachableSymbols::scan(SVal val) { 561249423Sdim if (Optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>()) 562226586Sdim return scan(X->getRegion()); 563226586Sdim 564249423Sdim if (Optional<nonloc::LazyCompoundVal> X = 565261991Sdim val.getAs<nonloc::LazyCompoundVal>()) 566261991Sdim return scan(*X); 567239462Sdim 568249423Sdim if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>()) 569226586Sdim return scan(X->getLoc()); 570226586Sdim 571226586Sdim if (SymbolRef Sym = val.getAsSymbol()) 572226586Sdim return scan(Sym); 573226586Sdim 574226586Sdim if (const SymExpr *Sym = val.getAsSymbolicExpression()) 575226586Sdim return scan(Sym); 576226586Sdim 577249423Sdim if (Optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>()) 578226586Sdim return scan(*X); 579226586Sdim 580226586Sdim return true; 581226586Sdim} 582226586Sdim 583226586Sdimbool ScanReachableSymbols::scan(const MemRegion *R) { 584226586Sdim if (isa<MemSpaceRegion>(R)) 585226586Sdim return true; 586226586Sdim 587261991Sdim bool wasVisited = !visited.insert(R).second; 588261991Sdim if (wasVisited) 589226586Sdim return true; 590234353Sdim 591234353Sdim if (!visitor.VisitMemRegion(R)) 592234353Sdim return false; 593226586Sdim 594226586Sdim // If this is a symbolic region, visit the symbol for the region. 595226586Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 596226586Sdim if (!visitor.VisitSymbol(SR->getSymbol())) 597226586Sdim return false; 598226586Sdim 599226586Sdim // If this is a subregion, also visit the parent regions. 600239462Sdim if (const SubRegion *SR = dyn_cast<SubRegion>(R)) { 601239462Sdim const MemRegion *Super = SR->getSuperRegion(); 602239462Sdim if (!scan(Super)) 603226586Sdim return false; 604226586Sdim 605239462Sdim // When we reach the topmost region, scan all symbols in it. 606239462Sdim if (isa<MemSpaceRegion>(Super)) { 607239462Sdim StoreManager &StoreMgr = state->getStateManager().getStoreManager(); 608239462Sdim if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this)) 609239462Sdim return false; 610239462Sdim } 611239462Sdim } 612226586Sdim 613239462Sdim // Regions captured by a block are also implicitly reachable. 614239462Sdim if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) { 615239462Sdim BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), 616239462Sdim E = BDR->referenced_vars_end(); 617239462Sdim for ( ; I != E; ++I) { 618239462Sdim if (!scan(I.getCapturedRegion())) 619239462Sdim return false; 620239462Sdim } 621239462Sdim } 622226586Sdim 623239462Sdim return true; 624226586Sdim} 625226586Sdim 626226586Sdimbool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 627226586Sdim ScanReachableSymbols S(this, visitor); 628226586Sdim return S.scan(val); 629226586Sdim} 630226586Sdim 631226586Sdimbool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 632226586Sdim SymbolVisitor &visitor) const { 633226586Sdim ScanReachableSymbols S(this, visitor); 634226586Sdim for ( ; I != E; ++I) { 635226586Sdim if (!S.scan(*I)) 636226586Sdim return false; 637226586Sdim } 638226586Sdim return true; 639226586Sdim} 640226586Sdim 641226586Sdimbool ProgramState::scanReachableSymbols(const MemRegion * const *I, 642226586Sdim const MemRegion * const *E, 643226586Sdim SymbolVisitor &visitor) const { 644226586Sdim ScanReachableSymbols S(this, visitor); 645226586Sdim for ( ; I != E; ++I) { 646226586Sdim if (!S.scan(*I)) 647226586Sdim return false; 648226586Sdim } 649226586Sdim return true; 650226586Sdim} 651234353Sdim 652234353SdimProgramStateRef ProgramState::addTaint(const Stmt *S, 653234353Sdim const LocationContext *LCtx, 654234353Sdim TaintTagType Kind) const { 655234353Sdim if (const Expr *E = dyn_cast_or_null<Expr>(S)) 656234353Sdim S = E->IgnoreParens(); 657234353Sdim 658234353Sdim SymbolRef Sym = getSVal(S, LCtx).getAsSymbol(); 659234353Sdim if (Sym) 660234353Sdim return addTaint(Sym, Kind); 661234353Sdim 662234353Sdim const MemRegion *R = getSVal(S, LCtx).getAsRegion(); 663234353Sdim addTaint(R, Kind); 664234353Sdim 665234353Sdim // Cannot add taint, so just return the state. 666234353Sdim return this; 667234353Sdim} 668234353Sdim 669234353SdimProgramStateRef ProgramState::addTaint(const MemRegion *R, 670234353Sdim TaintTagType Kind) const { 671234353Sdim if (const SymbolicRegion *SR = dyn_cast_or_null<SymbolicRegion>(R)) 672234353Sdim return addTaint(SR->getSymbol(), Kind); 673234353Sdim return this; 674234353Sdim} 675234353Sdim 676234353SdimProgramStateRef ProgramState::addTaint(SymbolRef Sym, 677234353Sdim TaintTagType Kind) const { 678234353Sdim // If this is a symbol cast, remove the cast before adding the taint. Taint 679234353Sdim // is cast agnostic. 680234353Sdim while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) 681234353Sdim Sym = SC->getOperand(); 682234353Sdim 683234353Sdim ProgramStateRef NewState = set<TaintMap>(Sym, Kind); 684234353Sdim assert(NewState); 685234353Sdim return NewState; 686234353Sdim} 687234353Sdim 688234353Sdimbool ProgramState::isTainted(const Stmt *S, const LocationContext *LCtx, 689234353Sdim TaintTagType Kind) const { 690234353Sdim if (const Expr *E = dyn_cast_or_null<Expr>(S)) 691234353Sdim S = E->IgnoreParens(); 692234353Sdim 693234353Sdim SVal val = getSVal(S, LCtx); 694234353Sdim return isTainted(val, Kind); 695234353Sdim} 696234353Sdim 697234353Sdimbool ProgramState::isTainted(SVal V, TaintTagType Kind) const { 698234353Sdim if (const SymExpr *Sym = V.getAsSymExpr()) 699234353Sdim return isTainted(Sym, Kind); 700234353Sdim if (const MemRegion *Reg = V.getAsRegion()) 701234353Sdim return isTainted(Reg, Kind); 702234353Sdim return false; 703234353Sdim} 704234353Sdim 705234353Sdimbool ProgramState::isTainted(const MemRegion *Reg, TaintTagType K) const { 706234353Sdim if (!Reg) 707234353Sdim return false; 708234353Sdim 709234353Sdim // Element region (array element) is tainted if either the base or the offset 710234353Sdim // are tainted. 711234353Sdim if (const ElementRegion *ER = dyn_cast<ElementRegion>(Reg)) 712234353Sdim return isTainted(ER->getSuperRegion(), K) || isTainted(ER->getIndex(), K); 713234353Sdim 714234353Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) 715234353Sdim return isTainted(SR->getSymbol(), K); 716234353Sdim 717234353Sdim if (const SubRegion *ER = dyn_cast<SubRegion>(Reg)) 718234353Sdim return isTainted(ER->getSuperRegion(), K); 719234353Sdim 720234353Sdim return false; 721234353Sdim} 722234353Sdim 723234353Sdimbool ProgramState::isTainted(SymbolRef Sym, TaintTagType Kind) const { 724234353Sdim if (!Sym) 725234353Sdim return false; 726234353Sdim 727234353Sdim // Traverse all the symbols this symbol depends on to see if any are tainted. 728234353Sdim bool Tainted = false; 729234353Sdim for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); 730234353Sdim SI != SE; ++SI) { 731243830Sdim if (!isa<SymbolData>(*SI)) 732243830Sdim continue; 733243830Sdim 734234353Sdim const TaintTagType *Tag = get<TaintMap>(*SI); 735234353Sdim Tainted = (Tag && *Tag == Kind); 736234353Sdim 737234353Sdim // If this is a SymbolDerived with a tainted parent, it's also tainted. 738234353Sdim if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) 739234353Sdim Tainted = Tainted || isTainted(SD->getParentSymbol(), Kind); 740234353Sdim 741234353Sdim // If memory region is tainted, data is also tainted. 742234353Sdim if (const SymbolRegionValue *SRV = dyn_cast<SymbolRegionValue>(*SI)) 743234353Sdim Tainted = Tainted || isTainted(SRV->getRegion(), Kind); 744234353Sdim 745234353Sdim // If If this is a SymbolCast from a tainted value, it's also tainted. 746234353Sdim if (const SymbolCast *SC = dyn_cast<SymbolCast>(*SI)) 747234353Sdim Tainted = Tainted || isTainted(SC->getOperand(), Kind); 748234353Sdim 749234353Sdim if (Tainted) 750234353Sdim return true; 751234353Sdim } 752234353Sdim 753234353Sdim return Tainted; 754234353Sdim} 755239462Sdim 756239462Sdim/// The GDM component containing the dynamic type info. This is a map from a 757243830Sdim/// symbol to its most likely type. 758243830SdimREGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicTypeMap, 759243830Sdim CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, 760243830Sdim DynamicTypeInfo)) 761239462Sdim 762239462SdimDynamicTypeInfo ProgramState::getDynamicTypeInfo(const MemRegion *Reg) const { 763239462Sdim Reg = Reg->StripCasts(); 764239462Sdim 765239462Sdim // Look up the dynamic type in the GDM. 766239462Sdim const DynamicTypeInfo *GDMType = get<DynamicTypeMap>(Reg); 767239462Sdim if (GDMType) 768239462Sdim return *GDMType; 769239462Sdim 770239462Sdim // Otherwise, fall back to what we know about the region. 771239462Sdim if (const TypedRegion *TR = dyn_cast<TypedRegion>(Reg)) 772239462Sdim return DynamicTypeInfo(TR->getLocationType(), /*CanBeSubclass=*/false); 773239462Sdim 774239462Sdim if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Reg)) { 775239462Sdim SymbolRef Sym = SR->getSymbol(); 776243830Sdim return DynamicTypeInfo(Sym->getType()); 777239462Sdim } 778239462Sdim 779239462Sdim return DynamicTypeInfo(); 780239462Sdim} 781239462Sdim 782239462SdimProgramStateRef ProgramState::setDynamicTypeInfo(const MemRegion *Reg, 783239462Sdim DynamicTypeInfo NewTy) const { 784239462Sdim Reg = Reg->StripCasts(); 785239462Sdim ProgramStateRef NewState = set<DynamicTypeMap>(Reg, NewTy); 786239462Sdim assert(NewState); 787239462Sdim return NewState; 788239462Sdim} 789