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 "llvm/Support/raw_ostream.h" |
21 | #include <optional> |
22 | |
23 | using namespace clang; |
24 | using namespace ento; |
25 | |
26 | namespace clang { namespace ento { |
27 | /// Increments the number of times this state is referenced. |
28 | |
29 | void ProgramStateRetain(const ProgramState *state) { |
30 | ++const_cast<ProgramState*>(state)->refCount; |
31 | } |
32 | |
33 | /// Decrement the number of times this state is referenced. |
34 | void ProgramStateRelease(const ProgramState *state) { |
35 | assert(state->refCount > 0); |
36 | ProgramState *s = const_cast<ProgramState*>(state); |
37 | if (--s->refCount == 0) { |
38 | ProgramStateManager &Mgr = s->getStateManager(); |
39 | Mgr.StateSet.RemoveNode(N: s); |
40 | s->~ProgramState(); |
41 | Mgr.freeStates.push_back(x: s); |
42 | } |
43 | } |
44 | }} |
45 | |
46 | ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, |
47 | StoreRef st, GenericDataMap gdm) |
48 | : stateMgr(mgr), |
49 | Env(env), |
50 | store(st.getStore()), |
51 | GDM(gdm), |
52 | refCount(0) { |
53 | stateMgr->getStoreManager().incrementReferenceCount(store); |
54 | } |
55 | |
56 | ProgramState::ProgramState(const ProgramState &RHS) |
57 | : stateMgr(RHS.stateMgr), Env(RHS.Env), store(RHS.store), GDM(RHS.GDM), |
58 | PosteriorlyOverconstrained(RHS.PosteriorlyOverconstrained), refCount(0) { |
59 | stateMgr->getStoreManager().incrementReferenceCount(store); |
60 | } |
61 | |
62 | ProgramState::~ProgramState() { |
63 | if (store) |
64 | stateMgr->getStoreManager().decrementReferenceCount(store); |
65 | } |
66 | |
67 | int64_t ProgramState::getID() const { |
68 | return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(Ptr: this); |
69 | } |
70 | |
71 | ProgramStateManager::ProgramStateManager(ASTContext &Ctx, |
72 | StoreManagerCreator CreateSMgr, |
73 | ConstraintManagerCreator CreateCMgr, |
74 | llvm::BumpPtrAllocator &alloc, |
75 | ExprEngine *ExprEng) |
76 | : Eng(ExprEng), EnvMgr(alloc), GDMFactory(alloc), |
77 | svalBuilder(createSimpleSValBuilder(alloc, context&: Ctx, stateMgr&: *this)), |
78 | CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) { |
79 | StoreMgr = (*CreateSMgr)(*this); |
80 | ConstraintMgr = (*CreateCMgr)(*this, ExprEng); |
81 | } |
82 | |
83 | |
84 | ProgramStateManager::~ProgramStateManager() { |
85 | for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); |
86 | I!=E; ++I) |
87 | I->second.second(I->second.first); |
88 | } |
89 | |
90 | ProgramStateRef ProgramStateManager::removeDeadBindingsFromEnvironmentAndStore( |
91 | ProgramStateRef state, const StackFrameContext *LCtx, |
92 | SymbolReaper &SymReaper) { |
93 | |
94 | // This code essentially performs a "mark-and-sweep" of the VariableBindings. |
95 | // The roots are any Block-level exprs and Decls that our liveness algorithm |
96 | // tells us are live. We then see what Decls they may reference, and keep |
97 | // those around. This code more than likely can be made faster, and the |
98 | // frequency of which this method is called should be experimented with |
99 | // for optimum performance. |
100 | ProgramState NewState = *state; |
101 | |
102 | NewState.Env = EnvMgr.removeDeadBindings(Env: NewState.Env, SymReaper, state); |
103 | |
104 | // Clean up the store. |
105 | StoreRef newStore = StoreMgr->removeDeadBindings(store: NewState.getStore(), LCtx, |
106 | SymReaper); |
107 | NewState.setStore(newStore); |
108 | SymReaper.setReapedStore(newStore); |
109 | |
110 | return getPersistentState(Impl&: NewState); |
111 | } |
112 | |
113 | ProgramStateRef ProgramState::bindLoc(Loc LV, |
114 | SVal V, |
115 | const LocationContext *LCtx, |
116 | bool notifyChanges) const { |
117 | ProgramStateManager &Mgr = getStateManager(); |
118 | ExprEngine &Eng = Mgr.getOwningEngine(); |
119 | ProgramStateRef State = makeWithStore(BindRes: Mgr.StoreMgr->Bind(store: getStore(), loc: LV, val: V)); |
120 | const MemRegion *MR = LV.getAsRegion(); |
121 | |
122 | if (MR && notifyChanges) |
123 | return Eng.processRegionChange(state: State, MR, LCtx); |
124 | |
125 | return State; |
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 | BindResult BindRes = Mgr.StoreMgr->BindDefaultInitial(store: getStore(), R, V); |
134 | ProgramStateRef State = makeWithStore(BindRes); |
135 | return Mgr.getOwningEngine().processRegionChange(state: 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 | BindResult BindRes = Mgr.StoreMgr->BindDefaultZero(store: getStore(), R); |
143 | ProgramStateRef State = makeWithStore(BindRes); |
144 | return Mgr.getOwningEngine().processRegionChange(state: State, MR: R, LCtx); |
145 | } |
146 | |
147 | typedef ArrayRef<const MemRegion *> RegionList; |
148 | typedef ArrayRef<SVal> ValueList; |
149 | |
150 | ProgramStateRef ProgramState::invalidateRegions( |
151 | RegionList Regions, ConstCFGElementRef Elem, 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(Elt: loc::MemRegionVal(Reg)); |
158 | |
159 | return invalidateRegions(Values, Elem, BlockCount: Count, LCtx, CausesPointerEscape: CausedByPointerEscape, IS, |
160 | Call, ITraits); |
161 | } |
162 | |
163 | ProgramStateRef ProgramState::invalidateRegions( |
164 | ValueList Values, ConstCFGElementRef Elem, 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 | store: getStore(), Values, Elem, Count, LCtx, Call, IS&: *IS, ITraits&: *ITraits, |
184 | TopLevelRegions: &TopLevelInvalidated, Invalidated: &Invalidated); |
185 | |
186 | ProgramStateRef NewState = makeWithStore(store: NewStore); |
187 | |
188 | if (CausedByPointerEscape) { |
189 | NewState = Eng.notifyCheckersOfPointerEscape( |
190 | State: NewState, Invalidated: IS, ExplicitRegions: TopLevelInvalidated, Call, ITraits&: *ITraits); |
191 | } |
192 | |
193 | return Eng.processRegionChanges(state: NewState, invalidated: IS, ExplicitRegions: TopLevelInvalidated, |
194 | Regions: Invalidated, LCtx, Call); |
195 | } |
196 | |
197 | ProgramStateRef ProgramState::killBinding(Loc LV) const { |
198 | Store OldStore = getStore(); |
199 | const StoreRef &newStore = |
200 | getStateManager().StoreMgr->killBinding(ST: OldStore, L: LV); |
201 | |
202 | if (newStore.getStore() == OldStore) |
203 | return this; |
204 | |
205 | return makeWithStore(store: 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: Val.getAsRegion()); |
213 | if (!TyReg || !TyReg->getValueType()->isReferenceType()) |
214 | return Val; |
215 | return getSVal(R: 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: 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(R: BaseReg, T: ElemTy)}; |
230 | } |
231 | |
232 | ProgramStateRef |
233 | ProgramState::enterStackFrame(const CallEvent &Call, |
234 | const StackFrameContext *CalleeCtx) const { |
235 | return makeWithStore( |
236 | BindRes: getStateManager().StoreMgr->enterStackFrame(store: getStore(), Call, CalleeCtx)); |
237 | } |
238 | |
239 | SVal ProgramState::getSelfSVal(const LocationContext *LCtx) const { |
240 | const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl(); |
241 | if (!SelfDecl) |
242 | return SVal(); |
243 | return getSVal(R: getRegion(SelfDecl, LCtx)); |
244 | } |
245 | |
246 | SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { |
247 | // We only want to do fetches from regions that we can actually bind |
248 | // values. For example, SymbolicRegions of type 'id<...>' cannot |
249 | // have direct bindings (but their can be bindings on their subregions). |
250 | if (!R->isBoundable()) |
251 | return UnknownVal(); |
252 | |
253 | if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(Val: R)) { |
254 | QualType T = TR->getValueType(); |
255 | if (Loc::isLocType(T) || T->isIntegralOrEnumerationType()) |
256 | return getSVal(R); |
257 | } |
258 | |
259 | return UnknownVal(); |
260 | } |
261 | |
262 | SVal ProgramState::getSVal(Loc location, QualType T) const { |
263 | SVal V = getRawSVal(LV: location, T); |
264 | |
265 | // If 'V' is a symbolic value that is *perfectly* constrained to |
266 | // be a constant value, use that value instead to lessen the burden |
267 | // on later analysis stages (so we have less symbolic values to reason |
268 | // about). |
269 | // We only go into this branch if we can convert the APSInt value we have |
270 | // to the type of T, which is not always the case (e.g. for void). |
271 | if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) { |
272 | if (SymbolRef sym = V.getAsSymbol()) { |
273 | if (const llvm::APSInt *Int = getStateManager() |
274 | .getConstraintManager() |
275 | .getSymVal(state: this, sym)) { |
276 | // FIXME: Because we don't correctly model (yet) sign-extension |
277 | // and truncation of symbolic values, we need to convert |
278 | // the integer value to the correct signedness and bitwidth. |
279 | // |
280 | // This shows up in the following: |
281 | // |
282 | // char foo(); |
283 | // unsigned x = foo(); |
284 | // if (x == 54) |
285 | // ... |
286 | // |
287 | // The symbolic value stored to 'x' is actually the conjured |
288 | // symbol for the call to foo(); the type of that symbol is 'char', |
289 | // not unsigned. |
290 | APSIntPtr NewV = getBasicVals().Convert(T, From: *Int); |
291 | if (V.getAs<Loc>()) |
292 | return loc::ConcreteInt(NewV); |
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::makeWithStore(const BindResult &BindRes) const { |
440 | ExprEngine &Eng = getStateManager().getOwningEngine(); |
441 | ProgramStateRef State = makeWithStore(store: BindRes.ResultingStore); |
442 | |
443 | // We must always notify the checkers for failing binds because otherwise they |
444 | // may keep stale traits for these symbols. |
445 | // Eg., Malloc checker may report leaks if we failed to bind that symbol. |
446 | if (BindRes.FailedToBindValues.empty()) |
447 | return State; |
448 | return Eng.escapeValues(State, Vs: BindRes.FailedToBindValues, K: PSK_EscapeOnBind); |
449 | } |
450 | |
451 | ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const { |
452 | ProgramState NewSt(*this); |
453 | NewSt.PosteriorlyOverconstrained = true; |
454 | return getStateManager().getPersistentState(State&: NewSt); |
455 | } |
456 | |
457 | void ProgramState::setStore(const StoreRef &newStore) { |
458 | Store newStoreStore = newStore.getStore(); |
459 | if (newStoreStore) |
460 | stateMgr->getStoreManager().incrementReferenceCount(store: newStoreStore); |
461 | if (store) |
462 | stateMgr->getStoreManager().decrementReferenceCount(store); |
463 | store = newStoreStore; |
464 | } |
465 | |
466 | SVal ProgramState::getLValue(const FieldDecl *D, SVal Base) const { |
467 | Base = desugarReference(Val: Base); |
468 | Base = wrapSymbolicRegion(Val: Base); |
469 | return getStateManager().StoreMgr->getLValueField(D, Base); |
470 | } |
471 | |
472 | SVal ProgramState::getLValue(const IndirectFieldDecl *D, SVal Base) const { |
473 | StoreManager &SM = *getStateManager().StoreMgr; |
474 | Base = desugarReference(Val: Base); |
475 | Base = wrapSymbolicRegion(Val: Base); |
476 | |
477 | // FIXME: This should work with `SM.getLValueField(D->getAnonField(), Base)`, |
478 | // but that would break some tests. There is probably a bug somewhere that it |
479 | // would expose. |
480 | for (const auto *I : D->chain()) { |
481 | Base = SM.getLValueField(D: cast<FieldDecl>(Val: I), Base); |
482 | } |
483 | return Base; |
484 | } |
485 | |
486 | //===----------------------------------------------------------------------===// |
487 | // State pretty-printing. |
488 | //===----------------------------------------------------------------------===// |
489 | |
490 | void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx, |
491 | const char *NL, unsigned int Space, |
492 | bool IsDot) const { |
493 | Indent(Out, Space, IsDot) << "\"program_state\": {"<< NL; |
494 | ++Space; |
495 | |
496 | ProgramStateManager &Mgr = getStateManager(); |
497 | |
498 | // Print the store. |
499 | Mgr.getStoreManager().printJson(Out, S: getStore(), NL, Space, IsDot); |
500 | |
501 | // Print out the environment. |
502 | Env.printJson(Out, Ctx: Mgr.getContext(), LCtx, NL, Space, IsDot); |
503 | |
504 | // Print out the constraints. |
505 | Mgr.getConstraintManager().printJson(Out, State: this, NL, Space, IsDot); |
506 | |
507 | // Print out the tracked dynamic types. |
508 | printDynamicTypeInfoJson(Out, State: this, NL, Space, IsDot); |
509 | |
510 | // Print checker-specific data. |
511 | Mgr.getOwningEngine().printJson(Out, State: this, LCtx, NL, Space, IsDot); |
512 | |
513 | --Space; |
514 | Indent(Out, Space, IsDot) << '}'; |
515 | } |
516 | |
517 | void ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx, |
518 | unsigned int Space) const { |
519 | printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true); |
520 | } |
521 | |
522 | LLVM_DUMP_METHOD void ProgramState::dump() const { |
523 | printJson(Out&: llvm::errs()); |
524 | } |
525 | |
526 | AnalysisManager& ProgramState::getAnalysisManager() const { |
527 | return stateMgr->getOwningEngine().getAnalysisManager(); |
528 | } |
529 | |
530 | //===----------------------------------------------------------------------===// |
531 | // Generic Data Map. |
532 | //===----------------------------------------------------------------------===// |
533 | |
534 | void *const* ProgramState::FindGDM(void *K) const { |
535 | return GDM.lookup(K); |
536 | } |
537 | |
538 | void* |
539 | ProgramStateManager::FindGDMContext(void *K, |
540 | void *(*CreateContext)(llvm::BumpPtrAllocator&), |
541 | void (*DeleteContext)(void*)) { |
542 | |
543 | std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; |
544 | if (!p.first) { |
545 | p.first = CreateContext(Alloc); |
546 | p.second = DeleteContext; |
547 | } |
548 | |
549 | return p.first; |
550 | } |
551 | |
552 | ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){ |
553 | ProgramState::GenericDataMap M1 = St->getGDM(); |
554 | ProgramState::GenericDataMap M2 = GDMFactory.add(Old: M1, K: Key, D: Data); |
555 | |
556 | if (M1 == M2) |
557 | return St; |
558 | |
559 | ProgramState NewSt = *St; |
560 | NewSt.GDM = M2; |
561 | return getPersistentState(State&: NewSt); |
562 | } |
563 | |
564 | ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { |
565 | ProgramState::GenericDataMap OldM = state->getGDM(); |
566 | ProgramState::GenericDataMap NewM = GDMFactory.remove(Old: OldM, K: Key); |
567 | |
568 | if (NewM == OldM) |
569 | return state; |
570 | |
571 | ProgramState NewState = *state; |
572 | NewState.GDM = NewM; |
573 | return getPersistentState(State&: NewState); |
574 | } |
575 | |
576 | bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { |
577 | bool wasVisited = !visited.insert(V: val.getCVData()).second; |
578 | if (wasVisited) |
579 | return true; |
580 | |
581 | StoreManager &StoreMgr = state->getStateManager().getStoreManager(); |
582 | // FIXME: We don't really want to use getBaseRegion() here because pointer |
583 | // arithmetic doesn't apply, but scanReachableSymbols only accepts base |
584 | // regions right now. |
585 | const MemRegion *R = val.getRegion()->getBaseRegion(); |
586 | return StoreMgr.scanReachableSymbols(S: val.getStore(), R, Visitor&: *this); |
587 | } |
588 | |
589 | bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { |
590 | for (SVal V : val) |
591 | if (!scan(val: V)) |
592 | return false; |
593 | |
594 | return true; |
595 | } |
596 | |
597 | bool ScanReachableSymbols::scan(const SymExpr *sym) { |
598 | for (SymbolRef SubSym : sym->symbols()) { |
599 | bool wasVisited = !visited.insert(V: SubSym).second; |
600 | if (wasVisited) |
601 | continue; |
602 | |
603 | if (!visitor.VisitSymbol(sym: SubSym)) |
604 | return false; |
605 | } |
606 | |
607 | return true; |
608 | } |
609 | |
610 | bool ScanReachableSymbols::scan(SVal val) { |
611 | if (std::optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>()) |
612 | return scan(R: X->getRegion()); |
613 | |
614 | if (std::optional<nonloc::LazyCompoundVal> X = |
615 | val.getAs<nonloc::LazyCompoundVal>()) |
616 | return scan(val: *X); |
617 | |
618 | if (std::optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>()) |
619 | return scan(val: X->getLoc()); |
620 | |
621 | if (SymbolRef Sym = val.getAsSymbol()) |
622 | return scan(sym: Sym); |
623 | |
624 | if (std::optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>()) |
625 | return scan(val: *X); |
626 | |
627 | return true; |
628 | } |
629 | |
630 | bool ScanReachableSymbols::scan(const MemRegion *R) { |
631 | if (isa<MemSpaceRegion>(Val: R)) |
632 | return true; |
633 | |
634 | bool wasVisited = !visited.insert(V: R).second; |
635 | if (wasVisited) |
636 | return true; |
637 | |
638 | if (!visitor.VisitMemRegion(R)) |
639 | return false; |
640 | |
641 | // If this is a symbolic region, visit the symbol for the region. |
642 | if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(Val: R)) |
643 | if (!visitor.VisitSymbol(sym: SR->getSymbol())) |
644 | return false; |
645 | |
646 | // If this is a subregion, also visit the parent regions. |
647 | if (const SubRegion *SR = dyn_cast<SubRegion>(Val: R)) { |
648 | const MemRegion *Super = SR->getSuperRegion(); |
649 | if (!scan(R: Super)) |
650 | return false; |
651 | |
652 | // When we reach the topmost region, scan all symbols in it. |
653 | if (isa<MemSpaceRegion>(Val: Super)) { |
654 | StoreManager &StoreMgr = state->getStateManager().getStoreManager(); |
655 | if (!StoreMgr.scanReachableSymbols(S: state->getStore(), R: SR, Visitor&: *this)) |
656 | return false; |
657 | } |
658 | } |
659 | |
660 | // Regions captured by a block are also implicitly reachable. |
661 | if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(Val: R)) { |
662 | for (auto Var : BDR->referenced_vars()) { |
663 | if (!scan(R: Var.getCapturedRegion())) |
664 | return false; |
665 | } |
666 | } |
667 | |
668 | return true; |
669 | } |
670 | |
671 | bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { |
672 | ScanReachableSymbols S(this, visitor); |
673 | return S.scan(val); |
674 | } |
675 | |
676 | bool ProgramState::scanReachableSymbols( |
677 | llvm::iterator_range<region_iterator> Reachable, |
678 | SymbolVisitor &visitor) const { |
679 | ScanReachableSymbols S(this, visitor); |
680 | for (const MemRegion *R : Reachable) { |
681 | if (!S.scan(R)) |
682 | return false; |
683 | } |
684 | return true; |
685 | } |
686 |
Definitions
- ProgramStateRetain
- ProgramStateRelease
- ProgramState
- ProgramState
- ~ProgramState
- getID
- ProgramStateManager
- ~ProgramStateManager
- removeDeadBindingsFromEnvironmentAndStore
- bindLoc
- bindDefaultInitial
- bindDefaultZero
- invalidateRegions
- invalidateRegions
- killBinding
- desugarReference
- wrapSymbolicRegion
- enterStackFrame
- getSelfSVal
- getSValAsScalarOrLoc
- getSVal
- BindExpr
- assumeInBoundDual
- assumeInBound
- isNonNull
- areEqual
- isNull
- getInitialState
- getPersistentStateWithGDM
- getPersistentState
- makeWithStore
- makeWithStore
- cloneAsPosteriorlyOverconstrained
- setStore
- getLValue
- getLValue
- printJson
- printDOT
- dump
- getAnalysisManager
- FindGDM
- FindGDMContext
- addGDM
- removeGDM
- scan
- scan
- scan
- scan
- scan
- scanReachableSymbols
Learn to use CMake with our Intro Training
Find out more