ProgramState.cpp revision 1d1d515b2bafb59d624883d8fdda97d4b7dba0cb
1//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--= 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements ProgramState and ProgramStateManager. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/Analysis/CFG.h" 15#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/TaintManager.h" 19#include "llvm/Support/raw_ostream.h" 20 21using namespace clang; 22using namespace ento; 23 24// Give the vtable for ConstraintManager somewhere to live. 25// FIXME: Move this elsewhere. 26ConstraintManager::~ConstraintManager() {} 27 28ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, 29 StoreRef st, GenericDataMap gdm) 30 : stateMgr(mgr), 31 Env(env), 32 store(st.getStore()), 33 GDM(gdm), 34 refCount(0) { 35 stateMgr->getStoreManager().incrementReferenceCount(store); 36} 37 38ProgramState::ProgramState(const ProgramState &RHS) 39 : llvm::FoldingSetNode(), 40 stateMgr(RHS.stateMgr), 41 Env(RHS.Env), 42 store(RHS.store), 43 GDM(RHS.GDM), 44 refCount(0) { 45 stateMgr->getStoreManager().incrementReferenceCount(store); 46} 47 48ProgramState::~ProgramState() { 49 if (store) 50 stateMgr->getStoreManager().decrementReferenceCount(store); 51} 52 53ProgramStateManager::~ProgramStateManager() { 54 for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); 55 I!=E; ++I) 56 I->second.second(I->second.first); 57} 58 59const ProgramState* 60ProgramStateManager::removeDeadBindings(const ProgramState *state, 61 const StackFrameContext *LCtx, 62 SymbolReaper& SymReaper) { 63 64 // This code essentially performs a "mark-and-sweep" of the VariableBindings. 65 // The roots are any Block-level exprs and Decls that our liveness algorithm 66 // tells us are live. We then see what Decls they may reference, and keep 67 // those around. This code more than likely can be made faster, and the 68 // frequency of which this method is called should be experimented with 69 // for optimum performance. 70 ProgramState NewState = *state; 71 72 NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); 73 74 // Clean up the store. 75 StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, 76 SymReaper); 77 NewState.setStore(newStore); 78 SymReaper.setReapedStore(newStore); 79 80 return getPersistentState(NewState); 81} 82 83const ProgramState *ProgramStateManager::MarshalState(const ProgramState *state, 84 const StackFrameContext *InitLoc) { 85 // make up an empty state for now. 86 ProgramState State(this, 87 EnvMgr.getInitialEnvironment(), 88 StoreMgr->getInitialStore(InitLoc), 89 GDMFactory.getEmptyMap()); 90 91 return getPersistentState(State); 92} 93 94const ProgramState *ProgramState::bindCompoundLiteral(const CompoundLiteralExpr *CL, 95 const LocationContext *LC, 96 SVal V) const { 97 const StoreRef &newStore = 98 getStateManager().StoreMgr->BindCompoundLiteral(getStore(), CL, LC, V); 99 return makeWithStore(newStore); 100} 101 102const ProgramState *ProgramState::bindDecl(const VarRegion* VR, SVal IVal) const { 103 const StoreRef &newStore = 104 getStateManager().StoreMgr->BindDecl(getStore(), VR, IVal); 105 return makeWithStore(newStore); 106} 107 108const ProgramState *ProgramState::bindDeclWithNoInit(const VarRegion* VR) const { 109 const StoreRef &newStore = 110 getStateManager().StoreMgr->BindDeclWithNoInit(getStore(), VR); 111 return makeWithStore(newStore); 112} 113 114const ProgramState *ProgramState::bindLoc(Loc LV, SVal V) const { 115 ProgramStateManager &Mgr = getStateManager(); 116 const ProgramState *newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), 117 LV, V)); 118 const MemRegion *MR = LV.getAsRegion(); 119 if (MR && Mgr.getOwningEngine()) 120 return Mgr.getOwningEngine()->processRegionChange(newState, MR); 121 122 return newState; 123} 124 125const ProgramState *ProgramState::bindDefault(SVal loc, SVal V) const { 126 ProgramStateManager &Mgr = getStateManager(); 127 const MemRegion *R = cast<loc::MemRegionVal>(loc).getRegion(); 128 const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V); 129 const ProgramState *new_state = makeWithStore(newStore); 130 return Mgr.getOwningEngine() ? 131 Mgr.getOwningEngine()->processRegionChange(new_state, R) : 132 new_state; 133} 134 135const ProgramState * 136ProgramState::invalidateRegions(ArrayRef<const MemRegion *> Regions, 137 const Expr *E, unsigned Count, 138 StoreManager::InvalidatedSymbols *IS, 139 bool invalidateGlobals) const { 140 if (!IS) { 141 StoreManager::InvalidatedSymbols invalidated; 142 return invalidateRegionsImpl(Regions, E, Count, 143 invalidated, invalidateGlobals); 144 } 145 return invalidateRegionsImpl(Regions, E, Count, *IS, invalidateGlobals); 146} 147 148const ProgramState * 149ProgramState::invalidateRegionsImpl(ArrayRef<const MemRegion *> Regions, 150 const Expr *E, unsigned Count, 151 StoreManager::InvalidatedSymbols &IS, 152 bool invalidateGlobals) const { 153 ProgramStateManager &Mgr = getStateManager(); 154 SubEngine* Eng = Mgr.getOwningEngine(); 155 156 if (Eng && Eng->wantsRegionChangeUpdate(this)) { 157 StoreManager::InvalidatedRegions Invalidated; 158 const StoreRef &newStore 159 = Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, IS, 160 invalidateGlobals, &Invalidated); 161 const ProgramState *newState = makeWithStore(newStore); 162 return Eng->processRegionChanges(newState, &IS, Regions, Invalidated); 163 } 164 165 const StoreRef &newStore = 166 Mgr.StoreMgr->invalidateRegions(getStore(), Regions, E, Count, IS, 167 invalidateGlobals, NULL); 168 return makeWithStore(newStore); 169} 170 171const ProgramState *ProgramState::unbindLoc(Loc LV) const { 172 assert(!isa<loc::MemRegionVal>(LV) && "Use invalidateRegion instead."); 173 174 Store OldStore = getStore(); 175 const StoreRef &newStore = getStateManager().StoreMgr->Remove(OldStore, LV); 176 177 if (newStore.getStore() == OldStore) 178 return this; 179 180 return makeWithStore(newStore); 181} 182 183const ProgramState *ProgramState::enterStackFrame(const StackFrameContext *frame) const { 184 const StoreRef &new_store = 185 getStateManager().StoreMgr->enterStackFrame(this, frame); 186 return makeWithStore(new_store); 187} 188 189SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { 190 // We only want to do fetches from regions that we can actually bind 191 // values. For example, SymbolicRegions of type 'id<...>' cannot 192 // have direct bindings (but their can be bindings on their subregions). 193 if (!R->isBoundable()) 194 return UnknownVal(); 195 196 if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { 197 QualType T = TR->getValueType(); 198 if (Loc::isLocType(T) || T->isIntegerType()) 199 return getSVal(R); 200 } 201 202 return UnknownVal(); 203} 204 205SVal ProgramState::getSVal(Loc location, QualType T) const { 206 SVal V = getRawSVal(cast<Loc>(location), T); 207 208 // If 'V' is a symbolic value that is *perfectly* constrained to 209 // be a constant value, use that value instead to lessen the burden 210 // on later analysis stages (so we have less symbolic values to reason 211 // about). 212 if (!T.isNull()) { 213 if (SymbolRef sym = V.getAsSymbol()) { 214 if (const llvm::APSInt *Int = getSymVal(sym)) { 215 // FIXME: Because we don't correctly model (yet) sign-extension 216 // and truncation of symbolic values, we need to convert 217 // the integer value to the correct signedness and bitwidth. 218 // 219 // This shows up in the following: 220 // 221 // char foo(); 222 // unsigned x = foo(); 223 // if (x == 54) 224 // ... 225 // 226 // The symbolic value stored to 'x' is actually the conjured 227 // symbol for the call to foo(); the type of that symbol is 'char', 228 // not unsigned. 229 const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); 230 231 if (isa<Loc>(V)) 232 return loc::ConcreteInt(NewV); 233 else 234 return nonloc::ConcreteInt(NewV); 235 } 236 } 237 } 238 239 return V; 240} 241 242const ProgramState *ProgramState::BindExpr(const Stmt *S, SVal V, bool Invalidate) const{ 243 Environment NewEnv = getStateManager().EnvMgr.bindExpr(Env, S, V, 244 Invalidate); 245 if (NewEnv == Env) 246 return this; 247 248 ProgramState NewSt = *this; 249 NewSt.Env = NewEnv; 250 return getStateManager().getPersistentState(NewSt); 251} 252 253const ProgramState *ProgramState::bindExprAndLocation(const Stmt *S, SVal location, 254 SVal V) const { 255 Environment NewEnv = 256 getStateManager().EnvMgr.bindExprAndLocation(Env, S, location, V); 257 258 if (NewEnv == Env) 259 return this; 260 261 ProgramState NewSt = *this; 262 NewSt.Env = NewEnv; 263 return getStateManager().getPersistentState(NewSt); 264} 265 266const ProgramState *ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, 267 DefinedOrUnknownSVal UpperBound, 268 bool Assumption) const { 269 if (Idx.isUnknown() || UpperBound.isUnknown()) 270 return this; 271 272 // Build an expression for 0 <= Idx < UpperBound. 273 // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. 274 // FIXME: This should probably be part of SValBuilder. 275 ProgramStateManager &SM = getStateManager(); 276 SValBuilder &svalBuilder = SM.getSValBuilder(); 277 ASTContext &Ctx = svalBuilder.getContext(); 278 279 // Get the offset: the minimum value of the array index type. 280 BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 281 // FIXME: This should be using ValueManager::ArrayindexTy...somehow. 282 QualType indexTy = Ctx.IntTy; 283 nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); 284 285 // Adjust the index. 286 SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, 287 cast<NonLoc>(Idx), Min, indexTy); 288 if (newIdx.isUnknownOrUndef()) 289 return this; 290 291 // Adjust the upper bound. 292 SVal newBound = 293 svalBuilder.evalBinOpNN(this, BO_Add, cast<NonLoc>(UpperBound), 294 Min, indexTy); 295 296 if (newBound.isUnknownOrUndef()) 297 return this; 298 299 // Build the actual comparison. 300 SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, 301 cast<NonLoc>(newIdx), cast<NonLoc>(newBound), 302 Ctx.IntTy); 303 if (inBound.isUnknownOrUndef()) 304 return this; 305 306 // Finally, let the constraint manager take care of it. 307 ConstraintManager &CM = SM.getConstraintManager(); 308 return CM.assume(this, cast<DefinedSVal>(inBound), Assumption); 309} 310 311const ProgramState *ProgramStateManager::getInitialState(const LocationContext *InitLoc) { 312 ProgramState State(this, 313 EnvMgr.getInitialEnvironment(), 314 StoreMgr->getInitialStore(InitLoc), 315 GDMFactory.getEmptyMap()); 316 317 return getPersistentState(State); 318} 319 320void ProgramStateManager::recycleUnusedStates() { 321 for (std::vector<ProgramState*>::iterator i = recentlyAllocatedStates.begin(), 322 e = recentlyAllocatedStates.end(); i != e; ++i) { 323 ProgramState *state = *i; 324 if (state->referencedByExplodedNode()) 325 continue; 326 StateSet.RemoveNode(state); 327 freeStates.push_back(state); 328 state->~ProgramState(); 329 } 330 recentlyAllocatedStates.clear(); 331} 332 333const ProgramState *ProgramStateManager::getPersistentStateWithGDM( 334 const ProgramState *FromState, 335 const ProgramState *GDMState) { 336 ProgramState NewState = *FromState; 337 NewState.GDM = GDMState->GDM; 338 return getPersistentState(NewState); 339} 340 341const ProgramState *ProgramStateManager::getPersistentState(ProgramState &State) { 342 343 llvm::FoldingSetNodeID ID; 344 State.Profile(ID); 345 void *InsertPos; 346 347 if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) 348 return I; 349 350 ProgramState *newState = 0; 351 if (!freeStates.empty()) { 352 newState = freeStates.back(); 353 freeStates.pop_back(); 354 } 355 else { 356 newState = (ProgramState*) Alloc.Allocate<ProgramState>(); 357 } 358 new (newState) ProgramState(State); 359 StateSet.InsertNode(newState, InsertPos); 360 recentlyAllocatedStates.push_back(newState); 361 return newState; 362} 363 364const ProgramState *ProgramState::makeWithStore(const StoreRef &store) const { 365 ProgramState NewSt = *this; 366 NewSt.setStore(store); 367 return getStateManager().getPersistentState(NewSt); 368} 369 370void ProgramState::setStore(const StoreRef &newStore) { 371 Store newStoreStore = newStore.getStore(); 372 if (newStoreStore) 373 stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); 374 if (store) 375 stateMgr->getStoreManager().decrementReferenceCount(store); 376 store = newStoreStore; 377} 378 379//===----------------------------------------------------------------------===// 380// State pretty-printing. 381//===----------------------------------------------------------------------===// 382 383static bool IsEnvLoc(const Stmt *S) { 384 // FIXME: This is a layering violation. Should be in environment. 385 return (bool) (((uintptr_t) S) & 0x1); 386} 387 388void ProgramState::print(raw_ostream &Out, CFG *C, 389 const char *NL, const char *Sep) const { 390 // Print the store. 391 ProgramStateManager &Mgr = getStateManager(); 392 Mgr.getStoreManager().print(getStore(), Out, NL, Sep); 393 bool isFirst = true; 394 395 // FIXME: All environment printing should be moved inside Environment. 396 if (C) { 397 // Print Subexpression bindings. 398 for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 399 if (C->isBlkExpr(I.getKey()) || IsEnvLoc(I.getKey())) 400 continue; 401 402 if (isFirst) { 403 Out << NL << NL << "Sub-Expressions:" << NL; 404 isFirst = false; 405 } else { 406 Out << NL; 407 } 408 409 Out << " (" << (void*) I.getKey() << ") "; 410 LangOptions LO; // FIXME. 411 I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); 412 Out << " : " << I.getData(); 413 } 414 415 // Print block-expression bindings. 416 isFirst = true; 417 for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 418 if (!C->isBlkExpr(I.getKey())) 419 continue; 420 421 if (isFirst) { 422 Out << NL << NL << "Block-level Expressions:" << NL; 423 isFirst = false; 424 } else { 425 Out << NL; 426 } 427 428 Out << " (" << (void*) I.getKey() << ") "; 429 LangOptions LO; // FIXME. 430 I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); 431 Out << " : " << I.getData(); 432 } 433 } else { 434 // Print All bindings - no info to differentiate block from subexpressions. 435 for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 436 if (IsEnvLoc(I.getKey())) 437 continue; 438 439 if (isFirst) { 440 Out << NL << NL << "Expressions:" << NL; 441 isFirst = false; 442 } else { 443 Out << NL; 444 } 445 446 Out << " (" << (void*) I.getKey() << ") "; 447 LangOptions LO; // FIXME. 448 I.getKey()->printPretty(Out, 0, PrintingPolicy(LO)); 449 Out << " : " << I.getData(); 450 } 451 } 452 453 // Print locations. 454 isFirst = true; 455 456 for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) { 457 if (!IsEnvLoc(I.getKey())) 458 continue; 459 460 if (isFirst) { 461 Out << NL << NL << "Load/store locations:" << NL; 462 isFirst = false; 463 } else { 464 Out << NL; 465 } 466 467 const Stmt *S = (Stmt*) (((uintptr_t) I.getKey()) & ((uintptr_t) ~0x1)); 468 469 Out << " (" << (void*) S << ") "; 470 LangOptions LO; // FIXME. 471 S->printPretty(Out, 0, PrintingPolicy(LO)); 472 Out << " : " << I.getData(); 473 } 474 475 Mgr.getConstraintManager().print(this, Out, NL, Sep); 476 477 // Print checker-specific data. 478 Mgr.getOwningEngine()->printState(Out, this, NL, Sep); 479} 480 481void ProgramState::printDOT(raw_ostream &Out, CFG &C) const { 482 print(Out, &C, "\\l", "\\|"); 483} 484 485void ProgramState::dump(CFG &C) const { 486 print(llvm::errs(), &C); 487} 488 489void ProgramState::dump() const { 490 print(llvm::errs(), 0); 491} 492 493//===----------------------------------------------------------------------===// 494// Generic Data Map. 495//===----------------------------------------------------------------------===// 496 497void *const* ProgramState::FindGDM(void *K) const { 498 return GDM.lookup(K); 499} 500 501void* 502ProgramStateManager::FindGDMContext(void *K, 503 void *(*CreateContext)(llvm::BumpPtrAllocator&), 504 void (*DeleteContext)(void*)) { 505 506 std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; 507 if (!p.first) { 508 p.first = CreateContext(Alloc); 509 p.second = DeleteContext; 510 } 511 512 return p.first; 513} 514 515const ProgramState *ProgramStateManager::addGDM(const ProgramState *St, void *Key, void *Data){ 516 ProgramState::GenericDataMap M1 = St->getGDM(); 517 ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); 518 519 if (M1 == M2) 520 return St; 521 522 ProgramState NewSt = *St; 523 NewSt.GDM = M2; 524 return getPersistentState(NewSt); 525} 526 527const ProgramState *ProgramStateManager::removeGDM(const ProgramState *state, void *Key) { 528 ProgramState::GenericDataMap OldM = state->getGDM(); 529 ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); 530 531 if (NewM == OldM) 532 return state; 533 534 ProgramState NewState = *state; 535 NewState.GDM = NewM; 536 return getPersistentState(NewState); 537} 538 539bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { 540 for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) 541 if (!scan(*I)) 542 return false; 543 544 return true; 545} 546 547bool ScanReachableSymbols::scan(const SymExpr *sym) { 548 unsigned &isVisited = visited[sym]; 549 if (isVisited) 550 return true; 551 isVisited = 1; 552 553 if (!visitor.VisitSymbol(sym)) 554 return false; 555 556 switch (sym->getKind()) { 557 case SymExpr::RegionValueKind: 558 case SymExpr::ConjuredKind: 559 case SymExpr::DerivedKind: 560 case SymExpr::ExtentKind: 561 case SymExpr::MetadataKind: 562 break; 563 case SymExpr::CastSymbolKind: 564 return scan(cast<SymbolCast>(sym)->getOperand()); 565 case SymExpr::SymIntKind: 566 return scan(cast<SymIntExpr>(sym)->getLHS()); 567 case SymExpr::SymSymKind: { 568 const SymSymExpr *x = cast<SymSymExpr>(sym); 569 return scan(x->getLHS()) && scan(x->getRHS()); 570 } 571 } 572 return true; 573} 574 575bool ScanReachableSymbols::scan(SVal val) { 576 if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val)) 577 return scan(X->getRegion()); 578 579 if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val)) 580 return scan(X->getLoc()); 581 582 if (SymbolRef Sym = val.getAsSymbol()) 583 return scan(Sym); 584 585 if (const SymExpr *Sym = val.getAsSymbolicExpression()) 586 return scan(Sym); 587 588 if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val)) 589 return scan(*X); 590 591 return true; 592} 593 594bool ScanReachableSymbols::scan(const MemRegion *R) { 595 if (isa<MemSpaceRegion>(R)) 596 return true; 597 598 unsigned &isVisited = visited[R]; 599 if (isVisited) 600 return true; 601 isVisited = 1; 602 603 // If this is a symbolic region, visit the symbol for the region. 604 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) 605 if (!visitor.VisitSymbol(SR->getSymbol())) 606 return false; 607 608 // If this is a subregion, also visit the parent regions. 609 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) 610 if (!scan(SR->getSuperRegion())) 611 return false; 612 613 // Now look at the binding to this region (if any). 614 if (!scan(state->getSValAsScalarOrLoc(R))) 615 return false; 616 617 // Now look at the subregions. 618 if (!SRM.get()) 619 SRM.reset(state->getStateManager().getStoreManager(). 620 getSubRegionMap(state->getStore())); 621 622 return SRM->iterSubRegions(R, *this); 623} 624 625bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { 626 ScanReachableSymbols S(this, visitor); 627 return S.scan(val); 628} 629 630bool ProgramState::scanReachableSymbols(const SVal *I, const SVal *E, 631 SymbolVisitor &visitor) const { 632 ScanReachableSymbols S(this, visitor); 633 for ( ; I != E; ++I) { 634 if (!S.scan(*I)) 635 return false; 636 } 637 return true; 638} 639 640bool ProgramState::scanReachableSymbols(const MemRegion * const *I, 641 const MemRegion * const *E, 642 SymbolVisitor &visitor) const { 643 ScanReachableSymbols S(this, visitor); 644 for ( ; I != E; ++I) { 645 if (!S.scan(*I)) 646 return false; 647 } 648 return true; 649} 650 651const ProgramState* ProgramState::addTaint(const Stmt *S, 652 TaintTagType Kind) const { 653 SymbolRef Sym = getSVal(S).getAsSymbol(); 654 assert(Sym && "Cannot add taint to statements whose value is not a symbol"); 655 return addTaint(Sym, Kind); 656} 657 658const ProgramState* ProgramState::addTaint(SymbolRef Sym, 659 TaintTagType Kind) const { 660 const ProgramState *NewState = set<TaintMap>(Sym, Kind); 661 assert(NewState); 662 return NewState; 663} 664 665bool ProgramState::isTainted(const Stmt *S, TaintTagType Kind) const { 666 return isTainted(getSVal(S), Kind); 667} 668 669bool ProgramState::isTainted(SVal V, TaintTagType Kind) const { 670 return isTainted(V.getAsSymExpr(), Kind); 671} 672 673bool ProgramState::isTainted(const SymExpr* Sym, TaintTagType Kind) const { 674 if (!Sym) 675 return false; 676 677 // Travese all the symbols this symbol depends on to see if any are tainted. 678 bool Tainted = false; 679 for (SymExpr::symbol_iterator SI = Sym->symbol_begin(), SE =Sym->symbol_end(); 680 SI != SE; ++SI) { 681 assert(isa<SymbolData>(*SI)); 682 const TaintTagType *Tag = get<TaintMap>(*SI); 683 Tainted = (Tag && *Tag == Kind); 684 685 // If this is a SymbolDerived with a tainted parent, it's also tainted. 686 if (const SymbolDerived *SD = dyn_cast<SymbolDerived>(*SI)) 687 Tainted = Tainted || isTainted(SD->getParentSymbol(), Kind); 688 if (Tainted) 689 return true; 690 } 691 692 return Tainted; 693} 694