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