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 ProgramState::invalidateRegions(
 151     RegionList Regions, const Stmt *S, unsigned Count,
 152     const LocationContext *LCtx, bool CausedByPointerEscape,
 153     InvalidatedSymbols *IS, const CallEvent *Call,
 154     RegionAndSymbolInvalidationTraits *ITraits) const {
 155   SmallVector<SVal, 8> Values;
 156   for (const MemRegion *Reg : Regions)
 157     Values.push_back(loc::MemRegionVal(Reg));
 158
 159   return invalidateRegions(Values, S, Count, LCtx, CausedByPointerEscape, IS,
 160                            Call, ITraits);
 161 }
 162
 163 ProgramStateRef ProgramState::invalidateRegions(
 164     ValueList Values, const Stmt *S, unsigned Count,
 165     const LocationContext *LCtx, bool CausedByPointerEscape,
 166     InvalidatedSymbols *IS, const CallEvent *Call,
 167     RegionAndSymbolInvalidationTraits *ITraits) const {
 168
 169   ProgramStateManager &Mgr = getStateManager();
 170   ExprEngine &Eng = Mgr.getOwningEngine();
 171
 172   InvalidatedSymbols InvalidatedSyms;
 173   if (!IS)
 174     IS = &InvalidatedSyms;
 175
 176   RegionAndSymbolInvalidationTraits ITraitsLocal;
 177   if (!ITraits)
 178     ITraits = &ITraitsLocal;
 179
 180   StoreManager::InvalidatedRegions TopLevelInvalidated;
 181   StoreManager::InvalidatedRegions Invalidated;
 182   const StoreRef &NewStore = Mgr.StoreMgr->invalidateRegions(
 183       getStore(), Values, S, Count, LCtx, Call, *IS, *ITraits,
 184       &TopLevelInvalidated, &Invalidated);
 185
 186   ProgramStateRef NewState = makeWithStore(NewStore);
 187
 188   if (CausedByPointerEscape) {
 189     NewState = Eng.notifyCheckersOfPointerEscape(
 190         NewState, IS, TopLevelInvalidated, Call, *ITraits);
 191   }
 192
 193   return Eng.processRegionChanges(NewState, IS, TopLevelInvalidated,
 194                                   Invalidated, LCtx, Call);
 195 }
 196
 197 ProgramStateRef ProgramState::killBinding(Loc LV) const {
 198   Store OldStore = getStore();
 199   const StoreRef &newStore =
 200     getStateManager().StoreMgr->killBinding(OldStore, LV);
 201
 202   if (newStore.getStore() == OldStore)
 203     return this;
 204
 205   return makeWithStore(newStore);
 206 }
 207
 208 /// We should never form a MemRegion that would wrap a TypedValueRegion of a
 209 /// reference type. What we actually wanted was to create a MemRegion refering
 210 /// to the pointee of that reference.
 211 SVal ProgramState::desugarReference(SVal Val) const {
 212   const auto *TyReg = dyn_cast_or_null<TypedValueRegion>(Val.getAsRegion());
 213   if (!TyReg || !TyReg->getValueType()->isReferenceType())
 214     return Val;
 215   return getSVal(TyReg);
 216 }
 217
 218 /// SymbolicRegions are expected to be wrapped by an ElementRegion as a
 219 /// canonical representation. As a canonical representation, SymbolicRegions
 220 /// should be wrapped by ElementRegions before getting a FieldRegion.
 221 /// See f8643a9b31c4029942f67d4534c9139b45173504 why.
 222 SVal ProgramState::wrapSymbolicRegion(SVal Val) const {
 223   const auto *BaseReg = dyn_cast_or_null<SymbolicRegion>(Val.getAsRegion());
 224   if (!BaseReg)
 225     return Val;
 226
 227   StoreManager &SM = getStateManager().getStoreManager();
 228   QualType ElemTy = BaseReg->getPointeeStaticType();
 229   return loc::MemRegionVal{SM.GetElementZeroRegion(BaseReg, ElemTy)};
 230 }
 231
 232 ProgramStateRef
 233 ProgramState::enterStackFrame(const CallEvent &Call,
 234                               const StackFrameContext *CalleeCtx) const {
 235   const StoreRef &NewStore =
 236     getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx);
 237   return makeWithStore(NewStore);
 238 }
 239
 240 SVal ProgramState::getSelfSVal(const LocationContext *LCtx) const {
 241   const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl();
 242   if (!SelfDecl)
 243     return SVal();
 244   return getSVal(getRegion(SelfDecl, LCtx));
 245 }
 246
 247 SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const {
 248   // We only want to do fetches from regions that we can actually bind
 249   // values.  For example, SymbolicRegions of type 'id<...>' cannot
 250   // have direct bindings (but their can be bindings on their subregions).
 251   if (!R->isBoundable())
 252     return UnknownVal();
 253
 254   if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) {
 255     QualType T = TR->getValueType();
 256     if (Loc::isLocType(T) || T->isIntegralOrEnumerationType())
 257       return getSVal(R);
 258   }
 259
 260   return UnknownVal();
 261 }
 262
 263 SVal ProgramState::getSVal(Loc location, QualType T) const {
 264   SVal V = getRawSVal(location, T);
 265
 266   // If 'V' is a symbolic value that is *perfectly* constrained to
 267   // be a constant value, use that value instead to lessen the burden
 268   // on later analysis stages (so we have less symbolic values to reason
 269   // about).
 270   // We only go into this branch if we can convert the APSInt value we have
 271   // to the type of T, which is not always the case (e.g. for void).
 272   if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) {
 273     if (SymbolRef sym = V.getAsSymbol()) {
 274       if (const llvm::APSInt *Int = getStateManager()
 275                                     .getConstraintManager()
 276                                     .getSymVal(this, sym)) {
 277         // FIXME: Because we don't correctly model (yet) sign-extension
 278         // and truncation of symbolic values, we need to convert
 279         // the integer value to the correct signedness and bitwidth.
 280         //
 281         // This shows up in the following:
 282         //
 283         //   char foo();
 284         //   unsigned x = foo();
 285         //   if (x == 54)
 286         //     ...
 287         //
 288         //  The symbolic value stored to 'x' is actually the conjured
 289         //  symbol for the call to foo(); the type of that symbol is 'char',
 290         //  not unsigned.
 291         APSIntPtr NewV = getBasicVals().Convert(T, *Int);
 292         if (V.getAs<Loc>())
 293           return loc::ConcreteInt(NewV);
 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 = 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 SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const {
 456   Base = desugarReference(Base);
 457   Base = wrapSymbolicRegion(Base);
 458   return getStateManager().StoreMgr->getLValueField(D, Base);
 459 }
 460
 461 SVal ProgramState::getLValue(const IndirectFieldDecl *D, SVal Base) const {
 462   StoreManager &SM = *getStateManager().StoreMgr;
 463   Base = desugarReference(Base);
 464   Base = wrapSymbolicRegion(Base);
 465
 466   // FIXME: This should work with `SM.getLValueField(D->getAnonField(), Base)`,
 467   // but that would break some tests. There is probably a bug somewhere that it
 468   // would expose.
 469   for (const auto *I : D->chain()) {
 470     Base = SM.getLValueField(cast<FieldDecl>(I), Base);
 471   }
 472   return Base;
 473 }
 474
 475 //===----------------------------------------------------------------------===//
 476 //  State pretty-printing.
 477 //===----------------------------------------------------------------------===//
 478
 479 void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx,
 480                              const char *NL, unsigned int Space,
 481                              bool IsDot) const {
 482   Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;
 483   ++Space;
 484
 485   ProgramStateManager &Mgr = getStateManager();
 486
 487   // Print the store.
 488   Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot);
 489
 490   // Print out the environment.
 491   Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot);
 492
 493   // Print out the constraints.
 494   Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot);
 495
 496   // Print out the tracked dynamic types.
 497   printDynamicTypeInfoJson(Out, this, NL, Space, IsDot);
 498
 499   // Print checker-specific data.
 500   Mgr.getOwningEngine().printJson(Out, this, LCtx, NL, Space, IsDot);
 501
 502   --Space;
 503   Indent(Out, Space, IsDot) << '}';
 504 }
 505
 506 void ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx,
 507                             unsigned int Space) const {
 508   printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true);
 509 }
 510
 511 LLVM_DUMP_METHOD void ProgramState::dump() const {
 512   printJson(llvm::errs());
 513 }
 514
 515 AnalysisManager& ProgramState::getAnalysisManager() const {
 516   return stateMgr->getOwningEngine().getAnalysisManager();
 517 }
 518
 519 //===----------------------------------------------------------------------===//
 520 // Generic Data Map.
 521 //===----------------------------------------------------------------------===//
 522
 523 void *const* ProgramState::FindGDM(void *K) const {
 524   return GDM.lookup(K);
 525 }
 526
 527 void*
 528 ProgramStateManager::FindGDMContext(void *K,
 529                                void *(*CreateContext)(llvm::BumpPtrAllocator&),
 530                                void (*DeleteContext)(void*)) {
 531
 532   std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
 533   if (!p.first) {
 534     p.first = CreateContext(Alloc);
 535     p.second = DeleteContext;
 536   }
 537
 538   return p.first;
 539 }
 540
 541 ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){
 542   ProgramState::GenericDataMap M1 = St->getGDM();
 543   ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data);
 544
 545   if (M1 == M2)
 546     return St;
 547
 548   ProgramState NewSt = *St;
 549   NewSt.GDM = M2;
 550   return getPersistentState(NewSt);
 551 }
 552
 553 ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) {
 554   ProgramState::GenericDataMap OldM = state->getGDM();
 555   ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key);
 556
 557   if (NewM == OldM)
 558     return state;
 559
 560   ProgramState NewState = *state;
 561   NewState.GDM = NewM;
 562   return getPersistentState(NewState);
 563 }
 564
 565 bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) {
 566   bool wasVisited = !visited.insert(val.getCVData()).second;
 567   if (wasVisited)
 568     return true;
 569
 570   StoreManager &StoreMgr = state->getStateManager().getStoreManager();
 571   // FIXME: We don't really want to use getBaseRegion() here because pointer
 572   // arithmetic doesn't apply, but scanReachableSymbols only accepts base
 573   // regions right now.
 574   const MemRegion *R = val.getRegion()->getBaseRegion();
 575   return StoreMgr.scanReachableSymbols(val.getStore(), R, *this);
 576 }
 577
 578 bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
 579   for (SVal V : val)
 580     if (!scan(V))
 581       return false;
 582
 583   return true;
 584 }
 585
 586 bool ScanReachableSymbols::scan(const SymExpr *sym) {
 587   for (SymbolRef SubSym : sym->symbols()) {
 588     bool wasVisited = !visited.insert(SubSym).second;
 589     if (wasVisited)
 590       continue;
 591
 592     if (!visitor.VisitSymbol(SubSym))
 593       return false;
 594   }
 595
 596   return true;
 597 }
 598
 599 bool ScanReachableSymbols::scan(SVal val) {
 600   if (std::optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>())
 601     return scan(X->getRegion());
 602
 603   if (std::optional<nonloc::LazyCompoundVal> X =
 604           val.getAs<nonloc::LazyCompoundVal>())
 605     return scan(*X);
 606
 607   if (std::optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>())
 608     return scan(X->getLoc());
 609
 610   if (SymbolRef Sym = val.getAsSymbol())
 611     return scan(Sym);
 612
 613   if (std::optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>())
 614     return scan(*X);
 615
 616   return true;
 617 }
 618
 619 bool ScanReachableSymbols::scan(const MemRegion *R) {
 620   if (isa<MemSpaceRegion>(R))
 621     return true;
 622
 623   bool wasVisited = !visited.insert(R).second;
 624   if (wasVisited)
 625     return true;
 626
 627   if (!visitor.VisitMemRegion(R))
 628     return false;
 629
 630   // If this is a symbolic region, visit the symbol for the region.
 631   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
 632     if (!visitor.VisitSymbol(SR->getSymbol()))
 633       return false;
 634
 635   // If this is a subregion, also visit the parent regions.
 636   if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
 637     const MemRegion *Super = SR->getSuperRegion();
 638     if (!scan(Super))
 639       return false;
 640
 641     // When we reach the topmost region, scan all symbols in it.
 642     if (isa<MemSpaceRegion>(Super)) {
 643       StoreManager &StoreMgr = state->getStateManager().getStoreManager();
 644       if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this))
 645         return false;
 646     }
 647   }
 648
 649   // Regions captured by a block are also implicitly reachable.
 650   if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) {
 651     for (auto Var : BDR->referenced_vars()) {
 652       if (!scan(Var.getCapturedRegion()))
 653         return false;
 654     }
 655   }
 656
 657   return true;
 658 }
 659
 660 bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
 661   ScanReachableSymbols S(this, visitor);
 662   return S.scan(val);
 663 }
 664
 665 bool ProgramState::scanReachableSymbols(
 666     llvm::iterator_range<region_iterator> Reachable,
 667     SymbolVisitor &visitor) const {
 668   ScanReachableSymbols S(this, visitor);
 669   for (const MemRegion *R : Reachable) {
 670     if (!S.scan(R))
 671       return false;
 672   }
 673   return true;
 674 }