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 (const MemRegion *Reg : Regions)
 160     Values.push_back(loc::MemRegionVal(Reg));
 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   Store OldStore = getStore();
 220   const StoreRef &newStore =
 221     getStateManager().StoreMgr->killBinding(OldStore, LV);
 222
 223   if (newStore.getStore() == OldStore)
 224     return this;
 225
 226   return makeWithStore(newStore);
 227 }
 228
 229 ProgramStateRef
 230 ProgramState::enterStackFrame(const CallEvent &Call,
 231                               const StackFrameContext *CalleeCtx) const {
 232   const StoreRef &NewStore =
 233     getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx);
 234   return makeWithStore(NewStore);
 235 }
 236
 237 SVal ProgramState::getSelfSVal(const LocationContext *LCtx) const {
 238   const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl();
 239   if (!SelfDecl)
 240     return SVal();
 241   return getSVal(getRegion(SelfDecl, LCtx));
 242 }
 243
 244 SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const {
 245   // We only want to do fetches from regions that we can actually bind
 246   // values.  For example, SymbolicRegions of type 'id<...>' cannot
 247   // have direct bindings (but their can be bindings on their subregions).
 248   if (!R->isBoundable())
 249     return UnknownVal();
 250
 251   if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
 252     QualType T = TR->getValueType();
 253     if (Loc::isLocType(T) || T->isIntegralOrEnumerationType())
 254       return getSVal(R);
 255   }
 256
 257   return UnknownVal();
 258 }
 259
 260 SVal ProgramState::getSVal(Loc location, QualType T) const {
 261   SVal V = getRawSVal(location, T);
 262
 263   // If 'V' is a symbolic value that is *perfectly* constrained to
 264   // be a constant value, use that value instead to lessen the burden
 265   // on later analysis stages (so we have less symbolic values to reason
 266   // about).
 267   // We only go into this branch if we can convert the APSInt value we have
 268   // to the type of T, which is not always the case (e.g. for void).
 269   if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) {
 270     if (SymbolRef sym = V.getAsSymbol()) {
 271       if (const llvm::APSInt *Int = getStateManager()
 272                                     .getConstraintManager()
 273                                     .getSymVal(this, sym)) {
 274         // FIXME: Because we don't correctly model (yet) sign-extension
 275         // and truncation of symbolic values, we need to convert
 276         // the integer value to the correct signedness and bitwidth.
 277         //
 278         // This shows up in the following:
 279         //
 280         //   char foo();
 281         //   unsigned x = foo();
 282         //   if (x == 54)
 283         //     ...
 284         //
 285         //  The symbolic value stored to 'x' is actually the conjured
 286         //  symbol for the call to foo(); the type of that symbol is 'char',
 287         //  not unsigned.
 288         const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int);
 289
 290         if (V.getAs<Loc>())
 291           return loc::ConcreteInt(NewV);
 292         else
 293           return nonloc::ConcreteInt(NewV);
 294       }
 295     }
 296   }
 297
 298   return V;
 299 }
 300
 301 ProgramStateRef ProgramState::BindExpr(const Stmt *S,
 302                                            const LocationContext *LCtx,
 303                                            SVal V, bool Invalidate) const{
 304   Environment NewEnv =
 305     getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V,
 306                                       Invalidate);
 307   if (NewEnv == Env)
 308     return this;
 309
 310   ProgramState NewSt = *this;
 311   NewSt.Env = NewEnv;
 312   return getStateManager().getPersistentState(NewSt);
 313 }
 314
 315 [[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef>
 316 ProgramState::assumeInBoundDual(DefinedOrUnknownSVal Idx,
 317                                 DefinedOrUnknownSVal UpperBound,
 318                                 QualType indexTy) const {
 319   if (Idx.isUnknown() || UpperBound.isUnknown())
 320     return {this, this};
 321
 322   // Build an expression for 0 <= Idx < UpperBound.
 323   // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
 324   // FIXME: This should probably be part of SValBuilder.
 325   ProgramStateManager &SM = getStateManager();
 326   SValBuilder &svalBuilder = SM.getSValBuilder();
 327   ASTContext &Ctx = svalBuilder.getContext();
 328
 329   // Get the offset: the minimum value of the array index type.
 330   BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
 331   if (indexTy.isNull())
 332     indexTy = svalBuilder.getArrayIndexType();
 333   nonloc::ConcreteInt Min(BVF.getMinValue(indexTy));
 334
 335   // Adjust the index.
 336   SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add,
 337                                         Idx.castAs<NonLoc>(), Min, indexTy);
 338   if (newIdx.isUnknownOrUndef())
 339     return {this, this};
 340
 341   // Adjust the upper bound.
 342   SVal newBound =
 343     svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(),
 344                             Min, indexTy);
 345
 346   if (newBound.isUnknownOrUndef())
 347     return {this, this};
 348
 349   // Build the actual comparison.
 350   SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(),
 351                                          newBound.castAs<NonLoc>(), Ctx.IntTy);
 352   if (inBound.isUnknownOrUndef())
 353     return {this, this};
 354
 355   // Finally, let the constraint manager take care of it.
 356   ConstraintManager &CM = SM.getConstraintManager();
 357   return CM.assumeDual(this, inBound.castAs<DefinedSVal>());
 358 }
 359
 360 ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx,
 361                                             DefinedOrUnknownSVal UpperBound,
 362                                             bool Assumption,
 363                                             QualType indexTy) const {
 364   std::pair<ProgramStateRef, ProgramStateRef> R =
 365       assumeInBoundDual(Idx, UpperBound, indexTy);
 366   return Assumption ? R.first : R.second;
 367 }
 368
 369 ConditionTruthVal ProgramState::isNonNull(SVal V) const {
 370   ConditionTruthVal IsNull = isNull(V);
 371   if (IsNull.isUnderconstrained())
 372     return IsNull;
 373   return ConditionTruthVal(!IsNull.getValue());
 374 }
 375
 376 ConditionTruthVal ProgramState::areEqual(SVal Lhs, SVal Rhs) const {
 377   return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs);
 378 }
 379
 380 ConditionTruthVal ProgramState::isNull(SVal V) const {
 381   if (V.isZeroConstant())
 382     return true;
 383
 384   if (V.isConstant())
 385     return false;
 386
 387   SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true);
 388   if (!Sym)
 389     return ConditionTruthVal();
 390
 391   return getStateManager().ConstraintMgr->isNull(this, Sym);
 392 }
 393
 394 ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) {
 395   ProgramState State(this,
 396                 EnvMgr.getInitialEnvironment(),
 397                 StoreMgr->getInitialStore(InitLoc),
 398                 GDMFactory.getEmptyMap());
 399
 400   return getPersistentState(State);
 401 }
 402
 403 ProgramStateRef ProgramStateManager::getPersistentStateWithGDM(
 404                                                      ProgramStateRef FromState,
 405                                                      ProgramStateRef GDMState) {
 406   ProgramState NewState(*FromState);
 407   NewState.GDM = GDMState->GDM;
 408   return getPersistentState(NewState);
 409 }
 410
 411 ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) {
 412
 413   llvm::FoldingSetNodeID ID;
 414   State.Profile(ID);
 415   void *InsertPos;
 416
 417   if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
 418     return I;
 419
 420   ProgramState *newState = nullptr;
 421   if (!freeStates.empty()) {
 422     newState = freeStates.back();
 423     freeStates.pop_back();
 424   }
 425   else {
 426     newState = Alloc.Allocate<ProgramState>();
 427   }
 428   new (newState) ProgramState(State);
 429   StateSet.InsertNode(newState, InsertPos);
 430   return newState;
 431 }
 432
 433 ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const {
 434   ProgramState NewSt(*this);
 435   NewSt.setStore(store);
 436   return getStateManager().getPersistentState(NewSt);
 437 }
 438
 439 ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const {
 440   ProgramState NewSt(*this);
 441   NewSt.PosteriorlyOverconstrained = true;
 442   return getStateManager().getPersistentState(NewSt);
 443 }
 444
 445 void ProgramState::setStore(const StoreRef &newStore) {
 446   Store newStoreStore = newStore.getStore();
 447   if (newStoreStore)
 448     stateMgr->getStoreManager().incrementReferenceCount(newStoreStore);
 449   if (store)
 450     stateMgr->getStoreManager().decrementReferenceCount(store);
 451   store = newStoreStore;
 452 }
 453
 454 //===----------------------------------------------------------------------===//
 455 //  State pretty-printing.
 456 //===----------------------------------------------------------------------===//
 457
 458 void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx,
 459                              const char *NL, unsigned int Space,
 460                              bool IsDot) const {
 461   Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;
 462   ++Space;
 463
 464   ProgramStateManager &Mgr = getStateManager();
 465
 466   // Print the store.
 467   Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot);
 468
 469   // Print out the environment.
 470   Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot);
 471
 472   // Print out the constraints.
 473   Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot);
 474
 475   // Print out the tracked dynamic types.
 476   printDynamicTypeInfoJson(Out, this, NL, Space, IsDot);
 477
 478   // Print checker-specific data.
 479   Mgr.getOwningEngine().printJson(Out, this, LCtx, NL, Space, IsDot);
 480
 481   --Space;
 482   Indent(Out, Space, IsDot) << '}';
 483 }
 484
 485 void ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx,
 486                             unsigned int Space) const {
 487   printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true);
 488 }
 489
 490 LLVM_DUMP_METHOD void ProgramState::dump() const {
 491   printJson(llvm::errs());
 492 }
 493
 494 AnalysisManager& ProgramState::getAnalysisManager() const {
 495   return stateMgr->getOwningEngine().getAnalysisManager();
 496 }
 497
 498 //===----------------------------------------------------------------------===//
 499 // Generic Data Map.
 500 //===----------------------------------------------------------------------===//
 501
 502 void *const* ProgramState::FindGDM(void *K) const {
 503   return GDM.lookup(K);
 504 }
 505
 506 void*
 507 ProgramStateManager::FindGDMContext(void *K,
 508                                void *(*CreateContext)(llvm::BumpPtrAllocator&),
 509                                void (*DeleteContext)(void*)) {
 510
 511   std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
 512   if (!p.first) {
 513     p.first = CreateContext(Alloc);
 514     p.second = DeleteContext;
 515   }
 516
 517   return p.first;
 518 }
 519
 520 ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){
 521   ProgramState::GenericDataMap M1 = St->getGDM();
 522   ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data);
 523
 524   if (M1 == M2)
 525     return St;
 526
 527   ProgramState NewSt = *St;
 528   NewSt.GDM = M2;
 529   return getPersistentState(NewSt);
 530 }
 531
 532 ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) {
 533   ProgramState::GenericDataMap OldM = state->getGDM();
 534   ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key);
 535
 536   if (NewM == OldM)
 537     return state;
 538
 539   ProgramState NewState = *state;
 540   NewState.GDM = NewM;
 541   return getPersistentState(NewState);
 542 }
 543
 544 bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
 545   bool wasVisited = !visited.insert(val.getCVData()).second;
 546   if (wasVisited)
 547     return true;
 548
 549   StoreManager &StoreMgr = state->getStateManager().getStoreManager();
 550   // FIXME: We don't really want to use getBaseRegion() here because pointer
 551   // arithmetic doesn't apply, but scanReachableSymbols only accepts base
 552   // regions right now.
 553   const MemRegion *R = val.getRegion()->getBaseRegion();
 554   return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
 555 }
 556
 557 bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
 558   for (SVal V : val)
 559     if (!scan(V))
 560       return false;
 561
 562   return true;
 563 }
 564
 565 bool ScanReachableSymbols::scan(const SymExpr *sym) {
 566   for (SymbolRef SubSym : sym->symbols()) {
 567     bool wasVisited = !visited.insert(SubSym).second;
 568     if (wasVisited)
 569       continue;
 570
 571     if (!visitor.VisitSymbol(SubSym))
 572       return false;
 573   }
 574
 575   return true;
 576 }
 577
 578 bool ScanReachableSymbols::scan(SVal val) {
 579   if (std::optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>())
 580     return scan(X->getRegion());
 581
 582   if (std::optional<nonloc::LazyCompoundVal> X =
 583           val.getAs<nonloc::LazyCompoundVal>())
 584     return scan(*X);
 585
 586   if (std::optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
 587     return scan(X->getLoc());
 588
 589   if (SymbolRef Sym = val.getAsSymbol())
 590     return scan(Sym);
 591
 592   if (std::optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>())
 593     return scan(*X);
 594
 595   return true;
 596 }
 597
 598 bool ScanReachableSymbols::scan(const MemRegion *R) {
 599   if (isa<MemSpaceRegion>(R))
 600     return true;
 601
 602   bool wasVisited = !visited.insert(R).second;
 603   if (wasVisited)
 604     return true;
 605
 606   if (!visitor.VisitMemRegion(R))
 607     return false;
 608
 609   // If this is a symbolic region, visit the symbol for the region.
 610   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
 611     if (!visitor.VisitSymbol(SR->getSymbol()))
 612       return false;
 613
 614   // If this is a subregion, also visit the parent regions.
 615   if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
 616     const MemRegion *Super = SR->getSuperRegion();
 617     if (!scan(Super))
 618       return false;
 619
 620     // When we reach the topmost region, scan all symbols in it.
 621     if (isa<MemSpaceRegion>(Super)) {
 622       StoreManager &StoreMgr = state->getStateManager().getStoreManager();
 623       if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this))
 624         return false;
 625     }
 626   }
 627
 628   // Regions captured by a block are also implicitly reachable.
 629   if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
 630     for (auto Var : BDR->referenced_vars()) {
 631       if (!scan(Var.getCapturedRegion()))
 632         return false;
 633     }
 634   }
 635
 636   return true;
 637 }
 638
 639 bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
 640   ScanReachableSymbols S(this, visitor);
 641   return S.scan(val);
 642 }
 643
 644 bool ProgramState::scanReachableSymbols(
 645     llvm::iterator_range<region_iterator> Reachable,
 646     SymbolVisitor &visitor) const {
 647   ScanReachableSymbols S(this, visitor);
 648   for (const MemRegion *R : Reachable) {
 649     if (!S.scan(R))
 650       return false;
 651   }
 652   return true;
 653 }