contrib/llvm-project/clang/lib/StaticAnalyzer/Core/ProgramState.cpp

   1 //= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--=
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file implements ProgramState and ProgramStateManager.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  14 #include "clang/Analysis/CFG.h"
  15 #include "clang/Basic/JsonSupport.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  21 #include "llvm/Support/raw_ostream.h"
  22
  23 using namespace clang;
  24 using namespace ento;
  25
  26 namespace clang { namespace  ento {
  27 /// Increments the number of times this state is referenced.
  28
  29 void ProgramStateRetain(const ProgramState *state) {
  30   ++const_cast<ProgramState*>(state)->refCount;
  31 }
  32
  33 /// Decrement the number of times this state is referenced.
  34 void ProgramStateRelease(const ProgramState *state) {
  35   assert(state->refCount > 0);
  36   ProgramState *s = const_cast<ProgramState*>(state);
  37   if (--s->refCount == 0) {
  38     ProgramStateManager &Mgr = s->getStateManager();
  39     Mgr.StateSet.RemoveNode(s);
  40     s->~ProgramState();
  41     Mgr.freeStates.push_back(s);
  42   }
  43 }
  44 }}
  45
  46 ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env,
  47                  StoreRef st, GenericDataMap gdm)
  48   : stateMgr(mgr),
  49     Env(env),
  50     store(st.getStore()),
  51     GDM(gdm),
  52     refCount(0) {
  53   stateMgr->getStoreManager().incrementReferenceCount(store);
  54 }
  55
  56 ProgramState::ProgramState(const ProgramState &RHS)
  57     : stateMgr(RHS.stateMgr), Env(RHS.Env), store(RHS.store), GDM(RHS.GDM),
  58       refCount(0) {
  59   stateMgr->getStoreManager().incrementReferenceCount(store);
  60 }
  61
  62 ProgramState::~ProgramState() {
  63   if (store)
  64     stateMgr->getStoreManager().decrementReferenceCount(store);
  65 }
  66
  67 int64_t ProgramState::getID() const {
  68   return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(this);
  69 }
  70
  71 ProgramStateManager::ProgramStateManager(ASTContext &Ctx,
  72                                          StoreManagerCreator CreateSMgr,
  73                                          ConstraintManagerCreator CreateCMgr,
  74                                          llvm::BumpPtrAllocator &alloc,
  75                                          ExprEngine *ExprEng)
  76   : Eng(ExprEng), EnvMgr(alloc), GDMFactory(alloc),
  77     svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)),
  78     CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) {
  79   StoreMgr = (*CreateSMgr)(*this);
  80   ConstraintMgr = (*CreateCMgr)(*this, ExprEng);
  81 }
  82
  83
  84 ProgramStateManager::~ProgramStateManager() {
  85   for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
  86        I!=E; ++I)
  87     I->second.second(I->second.first);
  88 }
  89
  90 ProgramStateRef ProgramStateManager::removeDeadBindingsFromEnvironmentAndStore(
  91     ProgramStateRef state, const StackFrameContext *LCtx,
  92     SymbolReaper &SymReaper) {
  93
  94   // This code essentially performs a "mark-and-sweep" of the VariableBindings.
  95   // The roots are any Block-level exprs and Decls that our liveness algorithm
  96   // tells us are live.  We then see what Decls they may reference, and keep
  97   // those around.  This code more than likely can be made faster, and the
  98   // frequency of which this method is called should be experimented with
  99   // for optimum performance.
 100   ProgramState NewState = *state;
 101
 102   NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);
 103
 104   // Clean up the store.
 105   StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
 106                                                    SymReaper);
 107   NewState.setStore(newStore);
 108   SymReaper.setReapedStore(newStore);
 109
 110   return getPersistentState(NewState);
 111 }
 112
 113 ProgramStateRef ProgramState::bindLoc(Loc LV,
 114                                       SVal V,
 115                                       const LocationContext *LCtx,
 116                                       bool notifyChanges) const {
 117   ProgramStateManager &Mgr = getStateManager();
 118   ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(),
 119                                                              LV, V));
 120   const MemRegion *MR = LV.getAsRegion();
 121   if (MR && notifyChanges)
 122     return Mgr.getOwningEngine().processRegionChange(newState, MR, LCtx);
 123
 124   return newState;
 125 }
 126
 127 ProgramStateRef
 128 ProgramState::bindDefaultInitial(SVal loc, SVal V,
 129                                  const LocationContext *LCtx) const {
 130   ProgramStateManager &Mgr = getStateManager();
 131   const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
 132   const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V);
 133   ProgramStateRef new_state = makeWithStore(newStore);
 134   return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
 135 }
 136
 137 ProgramStateRef
 138 ProgramState::bindDefaultZero(SVal loc, const LocationContext *LCtx) const {
 139   ProgramStateManager &Mgr = getStateManager();
 140   const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
 141   const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R);
 142   ProgramStateRef new_state = makeWithStore(newStore);
 143   return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
 144 }
 145
 146 typedef ArrayRef<const MemRegion *> RegionList;
 147 typedef ArrayRef<SVal> ValueList;
 148
 149 ProgramStateRef
 150 ProgramState::invalidateRegions(RegionList Regions,
 151                              const Expr *E, unsigned Count,
 152                              const LocationContext *LCtx,
 153                              bool CausedByPointerEscape,
 154                              InvalidatedSymbols *IS,
 155                              const CallEvent *Call,
 156                              RegionAndSymbolInvalidationTraits *ITraits) const {
 157   SmallVector<SVal, 8> Values;
 158   for (RegionList::const_iterator I = Regions.begin(),
 159                                   End = Regions.end(); I != End; ++I)
 160     Values.push_back(loc::MemRegionVal(*I));
 161
 162   return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
 163                                IS, ITraits, Call);
 164 }
 165
 166 ProgramStateRef
 167 ProgramState::invalidateRegions(ValueList Values,
 168                              const Expr *E, unsigned Count,
 169                              const LocationContext *LCtx,
 170                              bool CausedByPointerEscape,
 171                              InvalidatedSymbols *IS,
 172                              const CallEvent *Call,
 173                              RegionAndSymbolInvalidationTraits *ITraits) const {
 174
 175   return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
 176                                IS, ITraits, Call);
 177 }
 178
 179 ProgramStateRef
 180 ProgramState::invalidateRegionsImpl(ValueList Values,
 181                                     const Expr *E, unsigned Count,
 182                                     const LocationContext *LCtx,
 183                                     bool CausedByPointerEscape,
 184                                     InvalidatedSymbols *IS,
 185                                     RegionAndSymbolInvalidationTraits *ITraits,
 186                                     const CallEvent *Call) const {
 187   ProgramStateManager &Mgr = getStateManager();
 188   ExprEngine &Eng = Mgr.getOwningEngine();
 189
 190   InvalidatedSymbols InvalidatedSyms;
 191   if (!IS)
 192     IS = &InvalidatedSyms;
 193
 194   RegionAndSymbolInvalidationTraits ITraitsLocal;
 195   if (!ITraits)
 196     ITraits = &ITraitsLocal;
 197
 198   StoreManager::InvalidatedRegions TopLevelInvalidated;
 199   StoreManager::InvalidatedRegions Invalidated;
 200   const StoreRef &newStore
 201   = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call,
 202                                     *IS, *ITraits, &TopLevelInvalidated,
 203                                     &Invalidated);
 204
 205   ProgramStateRef newState = makeWithStore(newStore);
 206
 207   if (CausedByPointerEscape) {
 208     newState = Eng.notifyCheckersOfPointerEscape(newState, IS,
 209                                                  TopLevelInvalidated,
 210                                                  Call,
 211                                                  *ITraits);
 212   }
 213
 214   return Eng.processRegionChanges(newState, IS, TopLevelInvalidated,
 215                                   Invalidated, LCtx, Call);
 216 }
 217
 218 ProgramStateRef ProgramState::killBinding(Loc LV) const {
 219   assert(!LV.getAs<loc::MemRegionVal>() && "Use invalidateRegion instead.");
 220
 221   Store OldStore = getStore();
 222   const StoreRef &newStore =
 223     getStateManager().StoreMgr->killBinding(OldStore, LV);
 224
 225   if (newStore.getStore() == OldStore)
 226     return this;
 227
 228   return makeWithStore(newStore);
 229 }
 230
 231 ProgramStateRef
 232 ProgramState::enterStackFrame(const CallEvent &Call,
 233                               const StackFrameContext *CalleeCtx) const {
 234   const StoreRef &NewStore =
 235     getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx);
 236   return makeWithStore(NewStore);
 237 }
 238
 239 SVal ProgramState::getSelfSVal(const LocationContext *LCtx) const {
 240   const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl();
 241   if (!SelfDecl)
 242     return SVal();
 243   return getSVal(getRegion(SelfDecl, LCtx));
 244 }
 245
 246 SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const {
 247   // We only want to do fetches from regions that we can actually bind
 248   // values.  For example, SymbolicRegions of type 'id<...>' cannot
 249   // have direct bindings (but their can be bindings on their subregions).
 250   if (!R->isBoundable())
 251     return UnknownVal();
 252
 253   if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
 254     QualType T = TR->getValueType();
 255     if (Loc::isLocType(T) || T->isIntegralOrEnumerationType())
 256       return getSVal(R);
 257   }
 258
 259   return UnknownVal();
 260 }
 261
 262 SVal ProgramState::getSVal(Loc location, QualType T) const {
 263   SVal V = getRawSVal(location, T);
 264
 265   // If 'V' is a symbolic value that is *perfectly* constrained to
 266   // be a constant value, use that value instead to lessen the burden
 267   // on later analysis stages (so we have less symbolic values to reason
 268   // about).
 269   // We only go into this branch if we can convert the APSInt value we have
 270   // to the type of T, which is not always the case (e.g. for void).
 271   if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) {
 272     if (SymbolRef sym = V.getAsSymbol()) {
 273       if (const llvm::APSInt *Int = getStateManager()
 274                                     .getConstraintManager()
 275                                     .getSymVal(this, sym)) {
 276         // FIXME: Because we don't correctly model (yet) sign-extension
 277         // and truncation of symbolic values, we need to convert
 278         // the integer value to the correct signedness and bitwidth.
 279         //
 280         // This shows up in the following:
 281         //
 282         //   char foo();
 283         //   unsigned x = foo();
 284         //   if (x == 54)
 285         //     ...
 286         //
 287         //  The symbolic value stored to 'x' is actually the conjured
 288         //  symbol for the call to foo(); the type of that symbol is 'char',
 289         //  not unsigned.
 290         const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int);
 291
 292         if (V.getAs<Loc>())
 293           return loc::ConcreteInt(NewV);
 294         else
 295           return nonloc::ConcreteInt(NewV);
 296       }
 297     }
 298   }
 299
 300   return V;
 301 }
 302
 303 ProgramStateRef ProgramState::BindExpr(const Stmt *S,
 304                                            const LocationContext *LCtx,
 305                                            SVal V, bool Invalidate) const{
 306   Environment NewEnv =
 307     getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V,
 308                                       Invalidate);
 309   if (NewEnv == Env)
 310     return this;
 311
 312   ProgramState NewSt = *this;
 313   NewSt.Env = NewEnv;
 314   return getStateManager().getPersistentState(NewSt);
 315 }
 316
 317 ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx,
 318                                       DefinedOrUnknownSVal UpperBound,
 319                                       bool Assumption,
 320                                       QualType indexTy) const {
 321   if (Idx.isUnknown() || UpperBound.isUnknown())
 322     return this;
 323
 324   // Build an expression for 0 <= Idx < UpperBound.
 325   // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
 326   // FIXME: This should probably be part of SValBuilder.
 327   ProgramStateManager &SM = getStateManager();
 328   SValBuilder &svalBuilder = SM.getSValBuilder();
 329   ASTContext &Ctx = svalBuilder.getContext();
 330
 331   // Get the offset: the minimum value of the array index type.
 332   BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
 333   if (indexTy.isNull())
 334     indexTy = svalBuilder.getArrayIndexType();
 335   nonloc::ConcreteInt Min(BVF.getMinValue(indexTy));
 336
 337   // Adjust the index.
 338   SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add,
 339                                         Idx.castAs<NonLoc>(), Min, indexTy);
 340   if (newIdx.isUnknownOrUndef())
 341     return this;
 342
 343   // Adjust the upper bound.
 344   SVal newBound =
 345     svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(),
 346                             Min, indexTy);
 347
 348   if (newBound.isUnknownOrUndef())
 349     return this;
 350
 351   // Build the actual comparison.
 352   SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(),
 353                                          newBound.castAs<NonLoc>(), Ctx.IntTy);
 354   if (inBound.isUnknownOrUndef())
 355     return this;
 356
 357   // Finally, let the constraint manager take care of it.
 358   ConstraintManager &CM = SM.getConstraintManager();
 359   return CM.assume(this, inBound.castAs<DefinedSVal>(), Assumption);
 360 }
 361
 362 ConditionTruthVal ProgramState::isNonNull(SVal V) const {
 363   ConditionTruthVal IsNull = isNull(V);
 364   if (IsNull.isUnderconstrained())
 365     return IsNull;
 366   return ConditionTruthVal(!IsNull.getValue());
 367 }
 368
 369 ConditionTruthVal ProgramState::areEqual(SVal Lhs, SVal Rhs) const {
 370   return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs);
 371 }
 372
 373 ConditionTruthVal ProgramState::isNull(SVal V) const {
 374   if (V.isZeroConstant())
 375     return true;
 376
 377   if (V.isConstant())
 378     return false;
 379
 380   SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true);
 381   if (!Sym)
 382     return ConditionTruthVal();
 383
 384   return getStateManager().ConstraintMgr->isNull(this, Sym);
 385 }
 386
 387 ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) {
 388   ProgramState State(this,
 389                 EnvMgr.getInitialEnvironment(),
 390                 StoreMgr->getInitialStore(InitLoc),
 391                 GDMFactory.getEmptyMap());
 392
 393   return getPersistentState(State);
 394 }
 395
 396 ProgramStateRef ProgramStateManager::getPersistentStateWithGDM(
 397                                                      ProgramStateRef FromState,
 398                                                      ProgramStateRef GDMState) {
 399   ProgramState NewState(*FromState);
 400   NewState.GDM = GDMState->GDM;
 401   return getPersistentState(NewState);
 402 }
 403
 404 ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) {
 405
 406   llvm::FoldingSetNodeID ID;
 407   State.Profile(ID);
 408   void *InsertPos;
 409
 410   if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
 411     return I;
 412
 413   ProgramState *newState = nullptr;
 414   if (!freeStates.empty()) {
 415     newState = freeStates.back();
 416     freeStates.pop_back();
 417   }
 418   else {
 419     newState = (ProgramState*) Alloc.Allocate<ProgramState>();
 420   }
 421   new (newState) ProgramState(State);
 422   StateSet.InsertNode(newState, InsertPos);
 423   return newState;
 424 }
 425
 426 ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const {
 427   ProgramState NewSt(*this);
 428   NewSt.setStore(store);
 429   return getStateManager().getPersistentState(NewSt);
 430 }
 431
 432 void ProgramState::setStore(const StoreRef &newStore) {
 433   Store newStoreStore = newStore.getStore();
 434   if (newStoreStore)
 435     stateMgr->getStoreManager().incrementReferenceCount(newStoreStore);
 436   if (store)
 437     stateMgr->getStoreManager().decrementReferenceCount(store);
 438   store = newStoreStore;
 439 }
 440
 441 //===----------------------------------------------------------------------===//
 442 //  State pretty-printing.
 443 //===----------------------------------------------------------------------===//
 444
 445 void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx,
 446                              const char *NL, unsigned int Space,
 447                              bool IsDot) const {
 448   Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;
 449   ++Space;
 450
 451   ProgramStateManager &Mgr = getStateManager();
 452
 453   // Print the store.
 454   Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot);
 455
 456   // Print out the environment.
 457   Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot);
 458
 459   // Print out the constraints.
 460   Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot);
 461
 462   // Print out the tracked dynamic types.
 463   printDynamicTypeInfoJson(Out, this, NL, Space, IsDot);
 464
 465   // Print checker-specific data.
 466   Mgr.getOwningEngine().printJson(Out, this, LCtx, NL, Space, IsDot);
 467
 468   --Space;
 469   Indent(Out, Space, IsDot) << '}';
 470 }
 471
 472 void ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx,
 473                             unsigned int Space) const {
 474   printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true);
 475 }
 476
 477 LLVM_DUMP_METHOD void ProgramState::dump() const {
 478   printJson(llvm::errs());
 479 }
 480
 481 AnalysisManager& ProgramState::getAnalysisManager() const {
 482   return stateMgr->getOwningEngine().getAnalysisManager();
 483 }
 484
 485 //===----------------------------------------------------------------------===//
 486 // Generic Data Map.
 487 //===----------------------------------------------------------------------===//
 488
 489 void *const* ProgramState::FindGDM(void *K) const {
 490   return GDM.lookup(K);
 491 }
 492
 493 void*
 494 ProgramStateManager::FindGDMContext(void *K,
 495                                void *(*CreateContext)(llvm::BumpPtrAllocator&),
 496                                void (*DeleteContext)(void*)) {
 497
 498   std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
 499   if (!p.first) {
 500     p.first = CreateContext(Alloc);
 501     p.second = DeleteContext;
 502   }
 503
 504   return p.first;
 505 }
 506
 507 ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){
 508   ProgramState::GenericDataMap M1 = St->getGDM();
 509   ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data);
 510
 511   if (M1 == M2)
 512     return St;
 513
 514   ProgramState NewSt = *St;
 515   NewSt.GDM = M2;
 516   return getPersistentState(NewSt);
 517 }
 518
 519 ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) {
 520   ProgramState::GenericDataMap OldM = state->getGDM();
 521   ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key);
 522
 523   if (NewM == OldM)
 524     return state;
 525
 526   ProgramState NewState = *state;
 527   NewState.GDM = NewM;
 528   return getPersistentState(NewState);
 529 }
 530
 531 bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
 532   bool wasVisited = !visited.insert(val.getCVData()).second;
 533   if (wasVisited)
 534     return true;
 535
 536   StoreManager &StoreMgr = state->getStateManager().getStoreManager();
 537   // FIXME: We don't really want to use getBaseRegion() here because pointer
 538   // arithmetic doesn't apply, but scanReachableSymbols only accepts base
 539   // regions right now.
 540   const MemRegion *R = val.getRegion()->getBaseRegion();
 541   return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
 542 }
 543
 544 bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
 545   for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I)
 546     if (!scan(*I))
 547       return false;
 548
 549   return true;
 550 }
 551
 552 bool ScanReachableSymbols::scan(const SymExpr *sym) {
 553   for (SymExpr::symbol_iterator SI = sym->symbol_begin(),
 554                                 SE = sym->symbol_end();
 555        SI != SE; ++SI) {
 556     bool wasVisited = !visited.insert(*SI).second;
 557     if (wasVisited)
 558       continue;
 559
 560     if (!visitor.VisitSymbol(*SI))
 561       return false;
 562   }
 563
 564   return true;
 565 }
 566
 567 bool ScanReachableSymbols::scan(SVal val) {
 568   if (Optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>())
 569     return scan(X->getRegion());
 570
 571   if (Optional<nonloc::LazyCompoundVal> X =
 572           val.getAs<nonloc::LazyCompoundVal>())
 573     return scan(*X);
 574
 575   if (Optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
 576     return scan(X->getLoc());
 577
 578   if (SymbolRef Sym = val.getAsSymbol())
 579     return scan(Sym);
 580
 581   if (Optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>())
 582     return scan(*X);
 583
 584   return true;
 585 }
 586
 587 bool ScanReachableSymbols::scan(const MemRegion *R) {
 588   if (isa<MemSpaceRegion>(R))
 589     return true;
 590
 591   bool wasVisited = !visited.insert(R).second;
 592   if (wasVisited)
 593     return true;
 594
 595   if (!visitor.VisitMemRegion(R))
 596     return false;
 597
 598   // If this is a symbolic region, visit the symbol for the region.
 599   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
 600     if (!visitor.VisitSymbol(SR->getSymbol()))
 601       return false;
 602
 603   // If this is a subregion, also visit the parent regions.
 604   if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
 605     const MemRegion *Super = SR->getSuperRegion();
 606     if (!scan(Super))
 607       return false;
 608
 609     // When we reach the topmost region, scan all symbols in it.
 610     if (isa<MemSpaceRegion>(Super)) {
 611       StoreManager &StoreMgr = state->getStateManager().getStoreManager();
 612       if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this))
 613         return false;
 614     }
 615   }
 616
 617   // Regions captured by a block are also implicitly reachable.
 618   if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
 619     BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
 620                                               E = BDR->referenced_vars_end();
 621     for ( ; I != E; ++I) {
 622       if (!scan(I.getCapturedRegion()))
 623         return false;
 624     }
 625   }
 626
 627   return true;
 628 }
 629
 630 bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
 631   ScanReachableSymbols S(this, visitor);
 632   return S.scan(val);
 633 }
 634
 635 bool ProgramState::scanReachableSymbols(
 636     llvm::iterator_range<region_iterator> Reachable,
 637     SymbolVisitor &visitor) const {
 638   ScanReachableSymbols S(this, visitor);
 639   for (const MemRegion *R : Reachable) {
 640     if (!S.scan(R))
 641       return false;
 642   }
 643   return true;
 644 }