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 #include <optional>
  23
  24 using namespace clang;
  25 using namespace ento;
  26
  27 namespace clang { namespace  ento {
  28 /// Increments the number of times this state is referenced.
  29
  30 void ProgramStateRetain(const ProgramState *state) {
  31   ++const_cast<ProgramState*>(state)->refCount;
  32 }
  33
  34 /// Decrement the number of times this state is referenced.
  35 void ProgramStateRelease(const ProgramState *state) {
  36   assert(state->refCount > 0);
  37   ProgramState *s = const_cast<ProgramState*>(state);
  38   if (--s->refCount == 0) {
  39     ProgramStateManager &Mgr = s->getStateManager();
  40     Mgr.StateSet.RemoveNode(s);
  41     s->~ProgramState();
  42     Mgr.freeStates.push_back(s);
  43   }
  44 }
  45 }}
  46
  47 ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env,
  48                  StoreRef st, GenericDataMap gdm)
  49   : stateMgr(mgr),
  50     Env(env),
  51     store(st.getStore()),
  52     GDM(gdm),
  53     refCount(0) {
  54   stateMgr->getStoreManager().incrementReferenceCount(store);
  55 }
  56
  57 ProgramState::ProgramState(const ProgramState &RHS)
  58     : stateMgr(RHS.stateMgr), Env(RHS.Env), store(RHS.store), GDM(RHS.GDM),
  59       PosteriorlyOverconstrained(RHS.PosteriorlyOverconstrained), refCount(0) {
  60   stateMgr->getStoreManager().incrementReferenceCount(store);
  61 }
  62
  63 ProgramState::~ProgramState() {
  64   if (store)
  65     stateMgr->getStoreManager().decrementReferenceCount(store);
  66 }
  67
  68 int64_t ProgramState::getID() const {
  69   return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(this);
  70 }
  71
  72 ProgramStateManager::ProgramStateManager(ASTContext &Ctx,
  73                                          StoreManagerCreator CreateSMgr,
  74                                          ConstraintManagerCreator CreateCMgr,
  75                                          llvm::BumpPtrAllocator &alloc,
  76                                          ExprEngine *ExprEng)
  77   : Eng(ExprEng), EnvMgr(alloc), GDMFactory(alloc),
  78     svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)),
  79     CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) {
  80   StoreMgr = (*CreateSMgr)(*this);
  81   ConstraintMgr = (*CreateCMgr)(*this, ExprEng);
  82 }
  83
  84
  85 ProgramStateManager::~ProgramStateManager() {
  86   for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
  87        I!=E; ++I)
  88     I->second.second(I->second.first);
  89 }
  90
  91 ProgramStateRef ProgramStateManager::removeDeadBindingsFromEnvironmentAndStore(
  92     ProgramStateRef state, const StackFrameContext *LCtx,
  93     SymbolReaper &SymReaper) {
  94
  95   // This code essentially performs a "mark-and-sweep" of the VariableBindings.
  96   // The roots are any Block-level exprs and Decls that our liveness algorithm
  97   // tells us are live.  We then see what Decls they may reference, and keep
  98   // those around.  This code more than likely can be made faster, and the
  99   // frequency of which this method is called should be experimented with
 100   // for optimum performance.
 101   ProgramState NewState = *state;
 102
 103   NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);
 104
 105   // Clean up the store.
 106   StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
 107                                                    SymReaper);
 108   NewState.setStore(newStore);
 109   SymReaper.setReapedStore(newStore);
 110
 111   return getPersistentState(NewState);
 112 }
 113
 114 ProgramStateRef ProgramState::bindLoc(Loc LV,
 115                                       SVal V,
 116                                       const LocationContext *LCtx,
 117                                       bool notifyChanges) const {
 118   ProgramStateManager &Mgr = getStateManager();
 119   ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(),
 120                                                              LV, V));
 121   const MemRegion *MR = LV.getAsRegion();
 122   if (MR && notifyChanges)
 123     return Mgr.getOwningEngine().processRegionChange(newState, MR, LCtx);
 124
 125   return newState;
 126 }
 127
 128 ProgramStateRef
 129 ProgramState::bindDefaultInitial(SVal loc, SVal V,
 130                                  const LocationContext *LCtx) const {
 131   ProgramStateManager &Mgr = getStateManager();
 132   const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
 133   const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V);
 134   ProgramStateRef new_state = makeWithStore(newStore);
 135   return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
 136 }
 137
 138 ProgramStateRef
 139 ProgramState::bindDefaultZero(SVal loc, const LocationContext *LCtx) const {
 140   ProgramStateManager &Mgr = getStateManager();
 141   const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
 142   const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R);
 143   ProgramStateRef new_state = makeWithStore(newStore);
 144   return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx);
 145 }
 146
 147 typedef ArrayRef<const MemRegion *> RegionList;
 148 typedef ArrayRef<SVal> ValueList;
 149
 150 ProgramStateRef
 151 ProgramState::invalidateRegions(RegionList Regions,
 152                              const Expr *E, unsigned Count,
 153                              const LocationContext *LCtx,
 154                              bool CausedByPointerEscape,
 155                              InvalidatedSymbols *IS,
 156                              const CallEvent *Call,
 157                              RegionAndSymbolInvalidationTraits *ITraits) const {
 158   SmallVector<SVal, 8> Values;
 159   for (RegionList::const_iterator I = Regions.begin(),
 160                                   End = Regions.end(); I != End; ++I)
 161     Values.push_back(loc::MemRegionVal(*I));
 162
 163   return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
 164                                IS, ITraits, Call);
 165 }
 166
 167 ProgramStateRef
 168 ProgramState::invalidateRegions(ValueList Values,
 169                              const Expr *E, unsigned Count,
 170                              const LocationContext *LCtx,
 171                              bool CausedByPointerEscape,
 172                              InvalidatedSymbols *IS,
 173                              const CallEvent *Call,
 174                              RegionAndSymbolInvalidationTraits *ITraits) const {
 175
 176   return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape,
 177                                IS, ITraits, Call);
 178 }
 179
 180 ProgramStateRef
 181 ProgramState::invalidateRegionsImpl(ValueList Values,
 182                                     const Expr *E, unsigned Count,
 183                                     const LocationContext *LCtx,
 184                                     bool CausedByPointerEscape,
 185                                     InvalidatedSymbols *IS,
 186                                     RegionAndSymbolInvalidationTraits *ITraits,
 187                                     const CallEvent *Call) const {
 188   ProgramStateManager &Mgr = getStateManager();
 189   ExprEngine &Eng = Mgr.getOwningEngine();
 190
 191   InvalidatedSymbols InvalidatedSyms;
 192   if (!IS)
 193     IS = &InvalidatedSyms;
 194
 195   RegionAndSymbolInvalidationTraits ITraitsLocal;
 196   if (!ITraits)
 197     ITraits = &ITraitsLocal;
 198
 199   StoreManager::InvalidatedRegions TopLevelInvalidated;
 200   StoreManager::InvalidatedRegions Invalidated;
 201   const StoreRef &newStore
 202   = Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call,
 203                                     *IS, *ITraits, &TopLevelInvalidated,
 204                                     &Invalidated);
 205
 206   ProgramStateRef newState = makeWithStore(newStore);
 207
 208   if (CausedByPointerEscape) {
 209     newState = Eng.notifyCheckersOfPointerEscape(newState, IS,
 210                                                  TopLevelInvalidated,
 211                                                  Call,
 212                                                  *ITraits);
 213   }
 214
 215   return Eng.processRegionChanges(newState, IS, TopLevelInvalidated,
 216                                   Invalidated, LCtx, Call);
 217 }
 218
 219 ProgramStateRef ProgramState::killBinding(Loc LV) const {
 220   Store OldStore = getStore();
 221   const StoreRef &newStore =
 222     getStateManager().StoreMgr->killBinding(OldStore, LV);
 223
 224   if (newStore.getStore() == OldStore)
 225     return this;
 226
 227   return makeWithStore(newStore);
 228 }
 229
 230 ProgramStateRef
 231 ProgramState::enterStackFrame(const CallEvent &Call,
 232                               const StackFrameContext *CalleeCtx) const {
 233   const StoreRef &NewStore =
 234     getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx);
 235   return makeWithStore(NewStore);
 236 }
 237
 238 SVal ProgramState::getSelfSVal(const LocationContext *LCtx) const {
 239   const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl();
 240   if (!SelfDecl)
 241     return SVal();
 242   return getSVal(getRegion(SelfDecl, LCtx));
 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 [[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef>
 317 ProgramState::assumeInBoundDual(DefinedOrUnknownSVal Idx,
 318                                 DefinedOrUnknownSVal UpperBound,
 319                                 QualType indexTy) const {
 320   if (Idx.isUnknown() || UpperBound.isUnknown())
 321     return {this, 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, 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, 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, this};
 355
 356   // Finally, let the constraint manager take care of it.
 357   ConstraintManager &CM = SM.getConstraintManager();
 358   return CM.assumeDual(this, inBound.castAs<DefinedSVal>());
 359 }
 360
 361 ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx,
 362                                             DefinedOrUnknownSVal UpperBound,
 363                                             bool Assumption,
 364                                             QualType indexTy) const {
 365   std::pair<ProgramStateRef, ProgramStateRef> R =
 366       assumeInBoundDual(Idx, UpperBound, indexTy);
 367   return Assumption ? R.first : R.second;
 368 }
 369
 370 ConditionTruthVal ProgramState::isNonNull(SVal V) const {
 371   ConditionTruthVal IsNull = isNull(V);
 372   if (IsNull.isUnderconstrained())
 373     return IsNull;
 374   return ConditionTruthVal(!IsNull.getValue());
 375 }
 376
 377 ConditionTruthVal ProgramState::areEqual(SVal Lhs, SVal Rhs) const {
 378   return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs);
 379 }
 380
 381 ConditionTruthVal ProgramState::isNull(SVal V) const {
 382   if (V.isZeroConstant())
 383     return true;
 384
 385   if (V.isConstant())
 386     return false;
 387
 388   SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true);
 389   if (!Sym)
 390     return ConditionTruthVal();
 391
 392   return getStateManager().ConstraintMgr->isNull(this, Sym);
 393 }
 394
 395 ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) {
 396   ProgramState State(this,
 397                 EnvMgr.getInitialEnvironment(),
 398                 StoreMgr->getInitialStore(InitLoc),
 399                 GDMFactory.getEmptyMap());
 400
 401   return getPersistentState(State);
 402 }
 403
 404 ProgramStateRef ProgramStateManager::getPersistentStateWithGDM(
 405                                                      ProgramStateRef FromState,
 406                                                      ProgramStateRef GDMState) {
 407   ProgramState NewState(*FromState);
 408   NewState.GDM = GDMState->GDM;
 409   return getPersistentState(NewState);
 410 }
 411
 412 ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) {
 413
 414   llvm::FoldingSetNodeID ID;
 415   State.Profile(ID);
 416   void *InsertPos;
 417
 418   if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
 419     return I;
 420
 421   ProgramState *newState = nullptr;
 422   if (!freeStates.empty()) {
 423     newState = freeStates.back();
 424     freeStates.pop_back();
 425   }
 426   else {
 427     newState = (ProgramState*) Alloc.Allocate<ProgramState>();
 428   }
 429   new (newState) ProgramState(State);
 430   StateSet.InsertNode(newState, InsertPos);
 431   return newState;
 432 }
 433
 434 ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const {
 435   ProgramState NewSt(*this);
 436   NewSt.setStore(store);
 437   return getStateManager().getPersistentState(NewSt);
 438 }
 439
 440 ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const {
 441   ProgramState NewSt(*this);
 442   NewSt.PosteriorlyOverconstrained = true;
 443   return getStateManager().getPersistentState(NewSt);
 444 }
 445
 446 void ProgramState::setStore(const StoreRef &newStore) {
 447   Store newStoreStore = newStore.getStore();
 448   if (newStoreStore)
 449     stateMgr->getStoreManager().incrementReferenceCount(newStoreStore);
 450   if (store)
 451     stateMgr->getStoreManager().decrementReferenceCount(store);
 452   store = newStoreStore;
 453 }
 454
 455 //===----------------------------------------------------------------------===//
 456 //  State pretty-printing.
 457 //===----------------------------------------------------------------------===//
 458
 459 void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx,
 460                              const char *NL, unsigned int Space,
 461                              bool IsDot) const {
 462   Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;
 463   ++Space;
 464
 465   ProgramStateManager &Mgr = getStateManager();
 466
 467   // Print the store.
 468   Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot);
 469
 470   // Print out the environment.
 471   Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot);
 472
 473   // Print out the constraints.
 474   Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot);
 475
 476   // Print out the tracked dynamic types.
 477   printDynamicTypeInfoJson(Out, this, NL, Space, IsDot);
 478
 479   // Print checker-specific data.
 480   Mgr.getOwningEngine().printJson(Out, this, LCtx, NL, Space, IsDot);
 481
 482   --Space;
 483   Indent(Out, Space, IsDot) << '}';
 484 }
 485
 486 void ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx,
 487                             unsigned int Space) const {
 488   printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true);
 489 }
 490
 491 LLVM_DUMP_METHOD void ProgramState::dump() const {
 492   printJson(llvm::errs());
 493 }
 494
 495 AnalysisManager& ProgramState::getAnalysisManager() const {
 496   return stateMgr->getOwningEngine().getAnalysisManager();
 497 }
 498
 499 //===----------------------------------------------------------------------===//
 500 // Generic Data Map.
 501 //===----------------------------------------------------------------------===//
 502
 503 void *const* ProgramState::FindGDM(void *K) const {
 504   return GDM.lookup(K);
 505 }
 506
 507 void*
 508 ProgramStateManager::FindGDMContext(void *K,
 509                                void *(*CreateContext)(llvm::BumpPtrAllocator&),
 510                                void (*DeleteContext)(void*)) {
 511
 512   std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
 513   if (!p.first) {
 514     p.first = CreateContext(Alloc);
 515     p.second = DeleteContext;
 516   }
 517
 518   return p.first;
 519 }
 520
 521 ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){
 522   ProgramState::GenericDataMap M1 = St->getGDM();
 523   ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data);
 524
 525   if (M1 == M2)
 526     return St;
 527
 528   ProgramState NewSt = *St;
 529   NewSt.GDM = M2;
 530   return getPersistentState(NewSt);
 531 }
 532
 533 ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) {
 534   ProgramState::GenericDataMap OldM = state->getGDM();
 535   ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key);
 536
 537   if (NewM == OldM)
 538     return state;
 539
 540   ProgramState NewState = *state;
 541   NewState.GDM = NewM;
 542   return getPersistentState(NewState);
 543 }
 544
 545 bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
 546   bool wasVisited = !visited.insert(val.getCVData()).second;
 547   if (wasVisited)
 548     return true;
 549
 550   StoreManager &StoreMgr = state->getStateManager().getStoreManager();
 551   // FIXME: We don't really want to use getBaseRegion() here because pointer
 552   // arithmetic doesn't apply, but scanReachableSymbols only accepts base
 553   // regions right now.
 554   const MemRegion *R = val.getRegion()->getBaseRegion();
 555   return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
 556 }
 557
 558 bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
 559   for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I)
 560     if (!scan(*I))
 561       return false;
 562
 563   return true;
 564 }
 565
 566 bool ScanReachableSymbols::scan(const SymExpr *sym) {
 567   for (SymExpr::symbol_iterator SI = sym->symbol_begin(),
 568                                 SE = sym->symbol_end();
 569        SI != SE; ++SI) {
 570     bool wasVisited = !visited.insert(*SI).second;
 571     if (wasVisited)
 572       continue;
 573
 574     if (!visitor.VisitSymbol(*SI))
 575       return false;
 576   }
 577
 578   return true;
 579 }
 580
 581 bool ScanReachableSymbols::scan(SVal val) {
 582   if (std::optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>())
 583     return scan(X->getRegion());
 584
 585   if (std::optional<nonloc::LazyCompoundVal> X =
 586           val.getAs<nonloc::LazyCompoundVal>())
 587     return scan(*X);
 588
 589   if (std::optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
 590     return scan(X->getLoc());
 591
 592   if (SymbolRef Sym = val.getAsSymbol())
 593     return scan(Sym);
 594
 595   if (std::optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>())
 596     return scan(*X);
 597
 598   return true;
 599 }
 600
 601 bool ScanReachableSymbols::scan(const MemRegion *R) {
 602   if (isa<MemSpaceRegion>(R))
 603     return true;
 604
 605   bool wasVisited = !visited.insert(R).second;
 606   if (wasVisited)
 607     return true;
 608
 609   if (!visitor.VisitMemRegion(R))
 610     return false;
 611
 612   // If this is a symbolic region, visit the symbol for the region.
 613   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
 614     if (!visitor.VisitSymbol(SR->getSymbol()))
 615       return false;
 616
 617   // If this is a subregion, also visit the parent regions.
 618   if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
 619     const MemRegion *Super = SR->getSuperRegion();
 620     if (!scan(Super))
 621       return false;
 622
 623     // When we reach the topmost region, scan all symbols in it.
 624     if (isa<MemSpaceRegion>(Super)) {
 625       StoreManager &StoreMgr = state->getStateManager().getStoreManager();
 626       if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this))
 627         return false;
 628     }
 629   }
 630
 631   // Regions captured by a block are also implicitly reachable.
 632   if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
 633     BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
 634                                               E = BDR->referenced_vars_end();
 635     for ( ; I != E; ++I) {
 636       if (!scan(I.getCapturedRegion()))
 637         return false;
 638     }
 639   }
 640
 641   return true;
 642 }
 643
 644 bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
 645   ScanReachableSymbols S(this, visitor);
 646   return S.scan(val);
 647 }
 648
 649 bool ProgramState::scanReachableSymbols(
 650     llvm::iterator_range<region_iterator> Reachable,
 651     SymbolVisitor &visitor) const {
 652   ScanReachableSymbols S(this, visitor);
 653   for (const MemRegion *R : Reachable) {
 654     if (!S.scan(R))
 655       return false;
 656   }
 657   return true;
 658 }