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(N: s); |
41 | s->~ProgramState(); |
42 | Mgr.freeStates.push_back(x: 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>(Ptr: 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, context&: Ctx, stateMgr&: *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(Env: NewState.Env, SymReaper, state); |
104 | |
105 | // Clean up the store. |
106 | StoreRef newStore = StoreMgr->removeDeadBindings(store: NewState.getStore(), LCtx, |
107 | SymReaper); |
108 | NewState.setStore(newStore); |
109 | SymReaper.setReapedStore(newStore); |
110 | |
111 | return getPersistentState(Impl&: 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(store: Mgr.StoreMgr->Bind(store: getStore(), |
120 | loc: LV, val: V)); |
121 | const MemRegion *MR = LV.getAsRegion(); |
122 | if (MR && notifyChanges) |
123 | return Mgr.getOwningEngine().processRegionChange(state: 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(store: getStore(), R, V); |
134 | ProgramStateRef new_state = makeWithStore(store: newStore); |
135 | return Mgr.getOwningEngine().processRegionChange(state: new_state, MR: 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(store: getStore(), R); |
143 | ProgramStateRef new_state = makeWithStore(store: newStore); |
144 | return Mgr.getOwningEngine().processRegionChange(state: new_state, MR: 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(Elt: loc::MemRegionVal(Reg)); |
161 | |
162 | return invalidateRegionsImpl(Values, E, BlockCount: Count, LCtx, ResultsInSymbolEscape: CausedByPointerEscape, |
163 | IS, HTraits: 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, BlockCount: Count, LCtx, ResultsInSymbolEscape: CausedByPointerEscape, |
176 | IS, HTraits: 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(store: getStore(), Values, E, Count, LCtx, Call, |
202 | IS&: *IS, ITraits&: *ITraits, InvalidatedTopLevel: &TopLevelInvalidated, |
203 | Invalidated: &Invalidated); |
204 | |
205 | ProgramStateRef newState = makeWithStore(store: newStore); |
206 | |
207 | if (CausedByPointerEscape) { |
208 | newState = Eng.notifyCheckersOfPointerEscape(State: newState, Invalidated: IS, |
209 | ExplicitRegions: TopLevelInvalidated, |
210 | Call, |
211 | ITraits&: *ITraits); |
212 | } |
213 | |
214 | return Eng.processRegionChanges(state: newState, invalidated: IS, ExplicitRegions: TopLevelInvalidated, |
215 | Regions: Invalidated, LCtx, Call); |
216 | } |
217 | |
218 | ProgramStateRef ProgramState::killBinding(Loc LV) const { |
219 | Store OldStore = getStore(); |
220 | const StoreRef &newStore = |
221 | getStateManager().StoreMgr->killBinding(ST: OldStore, L: LV); |
222 | |
223 | if (newStore.getStore() == OldStore) |
224 | return this; |
225 | |
226 | return makeWithStore(store: newStore); |
227 | } |
228 | |
229 | ProgramStateRef |
230 | ProgramState::enterStackFrame(const CallEvent &Call, |
231 | const StackFrameContext *CalleeCtx) const { |
232 | const StoreRef &NewStore = |
233 | getStateManager().StoreMgr->enterStackFrame(store: getStore(), Call, CalleeCtx); |
234 | return makeWithStore(store: 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(R: 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>(Val: 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(LV: 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(state: 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, From: *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, E: 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(Impl&: 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(T: indexTy)); |
334 | |
335 | // Adjust the index. |
336 | SVal newIdx = svalBuilder.evalBinOpNN(state: this, op: BO_Add, |
337 | lhs: Idx.castAs<NonLoc>(), rhs: Min, resultTy: indexTy); |
338 | if (newIdx.isUnknownOrUndef()) |
339 | return {this, this}; |
340 | |
341 | // Adjust the upper bound. |
342 | SVal newBound = |
343 | svalBuilder.evalBinOpNN(state: this, op: BO_Add, lhs: UpperBound.castAs<NonLoc>(), |
344 | rhs: Min, resultTy: indexTy); |
345 | |
346 | if (newBound.isUnknownOrUndef()) |
347 | return {this, this}; |
348 | |
349 | // Build the actual comparison. |
350 | SVal inBound = svalBuilder.evalBinOpNN(state: this, op: BO_LT, lhs: newIdx.castAs<NonLoc>(), |
351 | rhs: newBound.castAs<NonLoc>(), resultTy: 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(State: this, Cond: 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(state: this, lhs: Lhs, rhs: 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 */ IncludeBaseRegions: true); |
388 | if (!Sym) |
389 | return ConditionTruthVal(); |
390 | |
391 | return getStateManager().ConstraintMgr->isNull(State: 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(Impl&: 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(Impl&: 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(N: 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(State&: NewSt); |
437 | } |
438 | |
439 | ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const { |
440 | ProgramState NewSt(*this); |
441 | NewSt.PosteriorlyOverconstrained = true; |
442 | return getStateManager().getPersistentState(State&: NewSt); |
443 | } |
444 | |
445 | void ProgramState::setStore(const StoreRef &newStore) { |
446 | Store newStoreStore = newStore.getStore(); |
447 | if (newStoreStore) |
448 | stateMgr->getStoreManager().incrementReferenceCount(store: 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, S: getStore(), NL, Space, IsDot); |
468 | |
469 | // Print out the environment. |
470 | Env.printJson(Out, Ctx: Mgr.getContext(), LCtx, NL, Space, IsDot); |
471 | |
472 | // Print out the constraints. |
473 | Mgr.getConstraintManager().printJson(Out, State: this, NL, Space, IsDot); |
474 | |
475 | // Print out the tracked dynamic types. |
476 | printDynamicTypeInfoJson(Out, State: this, NL, Space, IsDot); |
477 | |
478 | // Print checker-specific data. |
479 | Mgr.getOwningEngine().printJson(Out, State: 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(Out&: 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(Old: M1, K: Key, D: Data); |
523 | |
524 | if (M1 == M2) |
525 | return St; |
526 | |
527 | ProgramState NewSt = *St; |
528 | NewSt.GDM = M2; |
529 | return getPersistentState(State&: NewSt); |
530 | } |
531 | |
532 | ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { |
533 | ProgramState::GenericDataMap OldM = state->getGDM(); |
534 | ProgramState::GenericDataMap NewM = GDMFactory.remove(Old: OldM, K: Key); |
535 | |
536 | if (NewM == OldM) |
537 | return state; |
538 | |
539 | ProgramState NewState = *state; |
540 | NewState.GDM = NewM; |
541 | return getPersistentState(State&: NewState); |
542 | } |
543 | |
544 | bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { |
545 | bool wasVisited = !visited.insert(V: 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(S: val.getStore(), R, Visitor&: *this); |
555 | } |
556 | |
557 | bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { |
558 | for (SVal V : val) |
559 | if (!scan(val: 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(V: SubSym).second; |
568 | if (wasVisited) |
569 | continue; |
570 | |
571 | if (!visitor.VisitSymbol(sym: 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(R: X->getRegion()); |
581 | |
582 | if (std::optional<nonloc::LazyCompoundVal> X = |
583 | val.getAs<nonloc::LazyCompoundVal>()) |
584 | return scan(val: *X); |
585 | |
586 | if (std::optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>()) |
587 | return scan(val: X->getLoc()); |
588 | |
589 | if (SymbolRef Sym = val.getAsSymbol()) |
590 | return scan(sym: Sym); |
591 | |
592 | if (std::optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>()) |
593 | return scan(val: *X); |
594 | |
595 | return true; |
596 | } |
597 | |
598 | bool ScanReachableSymbols::scan(const MemRegion *R) { |
599 | if (isa<MemSpaceRegion>(Val: R)) |
600 | return true; |
601 | |
602 | bool wasVisited = !visited.insert(V: 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>(Val: R)) |
611 | if (!visitor.VisitSymbol(sym: 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>(Val: R)) { |
616 | const MemRegion *Super = SR->getSuperRegion(); |
617 | if (!scan(R: Super)) |
618 | return false; |
619 | |
620 | // When we reach the topmost region, scan all symbols in it. |
621 | if (isa<MemSpaceRegion>(Val: Super)) { |
622 | StoreManager &StoreMgr = state->getStateManager().getStoreManager(); |
623 | if (!StoreMgr.scanReachableSymbols(S: state->getStore(), R: SR, Visitor&: *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>(Val: R)) { |
630 | for (auto Var : BDR->referenced_vars()) { |
631 | if (!scan(R: 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 | } |
654 | |