| 1 |
//= ProgramState.cpp - Path-Sensitive "State" for tracking values --*- C++ -*--= |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// This file implements ProgramState and ProgramStateManager. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
|
| 13 |
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" |
| 14 |
#include "clang/Analysis/CFG.h" |
| 15 |
#include "clang/Basic/JsonSupport.h" |
| 16 |
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" |
| 17 |
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" |
| 18 |
#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" |
| 19 |
#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" |
| 20 |
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" |
| 21 |
#include "llvm/Support/raw_ostream.h" |
| 22 |
#include <optional> |
| 23 |
|
| 24 |
using namespace clang; |
| 25 |
using namespace ento; |
| 26 |
|
| 27 |
namespace clang { namespace ento { |
| 28 |
/// Increments the number of times this state is referenced. |
| 29 |
|
| 30 |
void ProgramStateRetain(const ProgramState *state) { |
| 31 |
++const_cast<ProgramState*>(state)->refCount; |
| 32 |
} |
| 33 |
|
| 34 |
/// Decrement the number of times this state is referenced. |
| 35 |
void ProgramStateRelease(const ProgramState *state) { |
| 36 |
assert(state->refCount > 0); |
| 37 |
ProgramState *s = const_cast<ProgramState*>(state); |
| 38 |
if (--s->refCount == 0) { |
| 39 |
ProgramStateManager &Mgr = s->getStateManager(); |
| 40 |
Mgr.StateSet.RemoveNode(s); |
| 41 |
s->~ProgramState(); |
| 42 |
Mgr.freeStates.push_back(s); |
| 43 |
} |
| 44 |
} |
| 45 |
}} |
| 46 |
|
| 47 |
ProgramState::ProgramState(ProgramStateManager *mgr, const Environment& env, |
| 48 |
StoreRef st, GenericDataMap gdm) |
| 49 |
: stateMgr(mgr), |
| 50 |
Env(env), |
| 51 |
store(st.getStore()), |
| 52 |
GDM(gdm), |
| 53 |
refCount(0) { |
| 54 |
stateMgr->getStoreManager().incrementReferenceCount(store); |
| 55 |
} |
| 56 |
|
| 57 |
ProgramState::ProgramState(const ProgramState &RHS) |
| 58 |
: stateMgr(RHS.stateMgr), Env(RHS.Env), store(RHS.store), GDM(RHS.GDM), |
| 59 |
PosteriorlyOverconstrained(RHS.PosteriorlyOverconstrained), refCount(0) { |
| 60 |
stateMgr->getStoreManager().incrementReferenceCount(store); |
| 61 |
} |
| 62 |
|
| 63 |
ProgramState::~ProgramState() { |
| 64 |
if (store) |
| 65 |
stateMgr->getStoreManager().decrementReferenceCount(store); |
| 66 |
} |
| 67 |
|
| 68 |
int64_t ProgramState::getID() const { |
| 69 |
return getStateManager().Alloc.identifyKnownAlignedObject<ProgramState>(this); |
| 70 |
} |
| 71 |
|
| 72 |
ProgramStateManager::ProgramStateManager(ASTContext &Ctx, |
| 73 |
StoreManagerCreator CreateSMgr, |
| 74 |
ConstraintManagerCreator CreateCMgr, |
| 75 |
llvm::BumpPtrAllocator &alloc, |
| 76 |
ExprEngine *ExprEng) |
| 77 |
: Eng(ExprEng), EnvMgr(alloc), GDMFactory(alloc), |
| 78 |
svalBuilder(createSimpleSValBuilder(alloc, Ctx, *this)), |
| 79 |
CallEventMgr(new CallEventManager(alloc)), Alloc(alloc) { |
| 80 |
StoreMgr = (*CreateSMgr)(*this); |
| 81 |
ConstraintMgr = (*CreateCMgr)(*this, ExprEng); |
| 82 |
} |
| 83 |
|
| 84 |
|
| 85 |
ProgramStateManager::~ProgramStateManager() { |
| 86 |
for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end(); |
| 87 |
I!=E; ++I) |
| 88 |
I->second.second(I->second.first); |
| 89 |
} |
| 90 |
|
| 91 |
ProgramStateRef ProgramStateManager::removeDeadBindingsFromEnvironmentAndStore( |
| 92 |
ProgramStateRef state, const StackFrameContext *LCtx, |
| 93 |
SymbolReaper &SymReaper) { |
| 94 |
|
| 95 |
// This code essentially performs a "mark-and-sweep" of the VariableBindings. |
| 96 |
// The roots are any Block-level exprs and Decls that our liveness algorithm |
| 97 |
// tells us are live. We then see what Decls they may reference, and keep |
| 98 |
// those around. This code more than likely can be made faster, and the |
| 99 |
// frequency of which this method is called should be experimented with |
| 100 |
// for optimum performance. |
| 101 |
ProgramState NewState = *state; |
| 102 |
|
| 103 |
NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state); |
| 104 |
|
| 105 |
// Clean up the store. |
| 106 |
StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx, |
| 107 |
SymReaper); |
| 108 |
NewState.setStore(newStore); |
| 109 |
SymReaper.setReapedStore(newStore); |
| 110 |
|
| 111 |
return getPersistentState(NewState); |
| 112 |
} |
| 113 |
|
| 114 |
ProgramStateRef ProgramState::bindLoc(Loc LV, |
| 115 |
SVal V, |
| 116 |
const LocationContext *LCtx, |
| 117 |
bool notifyChanges) const { |
| 118 |
ProgramStateManager &Mgr = getStateManager(); |
| 119 |
ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(), |
| 120 |
LV, V)); |
| 121 |
const MemRegion *MR = LV.getAsRegion(); |
| 122 |
if (MR && notifyChanges) |
| 123 |
return Mgr.getOwningEngine().processRegionChange(newState, MR, LCtx); |
| 124 |
|
| 125 |
return newState; |
| 126 |
} |
| 127 |
|
| 128 |
ProgramStateRef |
| 129 |
ProgramState::bindDefaultInitial(SVal loc, SVal V, |
| 130 |
const LocationContext *LCtx) const { |
| 131 |
ProgramStateManager &Mgr = getStateManager(); |
| 132 |
const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion(); |
| 133 |
const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V); |
| 134 |
ProgramStateRef new_state = makeWithStore(newStore); |
| 135 |
return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx); |
| 136 |
} |
| 137 |
|
| 138 |
ProgramStateRef |
| 139 |
ProgramState::bindDefaultZero(SVal loc, const LocationContext *LCtx) const { |
| 140 |
ProgramStateManager &Mgr = getStateManager(); |
| 141 |
const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion(); |
| 142 |
const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R); |
| 143 |
ProgramStateRef new_state = makeWithStore(newStore); |
| 144 |
return Mgr.getOwningEngine().processRegionChange(new_state, R, LCtx); |
| 145 |
} |
| 146 |
|
| 147 |
typedef ArrayRef<const MemRegion *> RegionList; |
| 148 |
typedef ArrayRef<SVal> ValueList; |
| 149 |
|
| 150 |
ProgramStateRef |
| 151 |
ProgramState::invalidateRegions(RegionList Regions, |
| 152 |
const Expr *E, unsigned Count, |
| 153 |
const LocationContext *LCtx, |
| 154 |
bool CausedByPointerEscape, |
| 155 |
InvalidatedSymbols *IS, |
| 156 |
const CallEvent *Call, |
| 157 |
RegionAndSymbolInvalidationTraits *ITraits) const { |
| 158 |
SmallVector<SVal, 8> Values; |
| 159 |
for (RegionList::const_iterator I = Regions.begin(), |
| 160 |
End = Regions.end(); I != End; ++I) |
| 161 |
Values.push_back(loc::MemRegionVal(*I)); |
| 162 |
|
| 163 |
return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, |
| 164 |
IS, ITraits, Call); |
| 165 |
} |
| 166 |
|
| 167 |
ProgramStateRef |
| 168 |
ProgramState::invalidateRegions(ValueList Values, |
| 169 |
const Expr *E, unsigned Count, |
| 170 |
const LocationContext *LCtx, |
| 171 |
bool CausedByPointerEscape, |
| 172 |
InvalidatedSymbols *IS, |
| 173 |
const CallEvent *Call, |
| 174 |
RegionAndSymbolInvalidationTraits *ITraits) const { |
| 175 |
|
| 176 |
return invalidateRegionsImpl(Values, E, Count, LCtx, CausedByPointerEscape, |
| 177 |
IS, ITraits, Call); |
| 178 |
} |
| 179 |
|
| 180 |
ProgramStateRef |
| 181 |
ProgramState::invalidateRegionsImpl(ValueList Values, |
| 182 |
const Expr *E, unsigned Count, |
| 183 |
const LocationContext *LCtx, |
| 184 |
bool CausedByPointerEscape, |
| 185 |
InvalidatedSymbols *IS, |
| 186 |
RegionAndSymbolInvalidationTraits *ITraits, |
| 187 |
const CallEvent *Call) const { |
| 188 |
ProgramStateManager &Mgr = getStateManager(); |
| 189 |
ExprEngine &Eng = Mgr.getOwningEngine(); |
| 190 |
|
| 191 |
InvalidatedSymbols InvalidatedSyms; |
| 192 |
if (!IS) |
| 193 |
IS = &InvalidatedSyms; |
| 194 |
|
| 195 |
RegionAndSymbolInvalidationTraits ITraitsLocal; |
| 196 |
if (!ITraits) |
| 197 |
ITraits = &ITraitsLocal; |
| 198 |
|
| 199 |
StoreManager::InvalidatedRegions TopLevelInvalidated; |
| 200 |
StoreManager::InvalidatedRegions Invalidated; |
| 201 |
const StoreRef &newStore |
| 202 |
= Mgr.StoreMgr->invalidateRegions(getStore(), Values, E, Count, LCtx, Call, |
| 203 |
*IS, *ITraits, &TopLevelInvalidated, |
| 204 |
&Invalidated); |
| 205 |
|
| 206 |
ProgramStateRef newState = makeWithStore(newStore); |
| 207 |
|
| 208 |
if (CausedByPointerEscape) { |
| 209 |
newState = Eng.notifyCheckersOfPointerEscape(newState, IS, |
| 210 |
TopLevelInvalidated, |
| 211 |
Call, |
| 212 |
*ITraits); |
| 213 |
} |
| 214 |
|
| 215 |
return Eng.processRegionChanges(newState, IS, TopLevelInvalidated, |
| 216 |
Invalidated, LCtx, Call); |
| 217 |
} |
| 218 |
|
| 219 |
ProgramStateRef ProgramState::killBinding(Loc LV) const { |
| 220 |
Store OldStore = getStore(); |
| 221 |
const StoreRef &newStore = |
| 222 |
getStateManager().StoreMgr->killBinding(OldStore, LV); |
| 223 |
|
| 224 |
if (newStore.getStore() == OldStore) |
| 225 |
return this; |
| 226 |
|
| 227 |
return makeWithStore(newStore); |
| 228 |
} |
| 229 |
|
| 230 |
ProgramStateRef |
| 231 |
ProgramState::enterStackFrame(const CallEvent &Call, |
| 232 |
const StackFrameContext *CalleeCtx) const { |
| 233 |
const StoreRef &NewStore = |
| 234 |
getStateManager().StoreMgr->enterStackFrame(getStore(), Call, CalleeCtx); |
| 235 |
return makeWithStore(NewStore); |
| 236 |
} |
| 237 |
|
| 238 |
SVal ProgramState::getSelfSVal(const LocationContext *LCtx) const { |
| 239 |
const ImplicitParamDecl *SelfDecl = LCtx->getSelfDecl(); |
| 240 |
if (!SelfDecl) |
| 241 |
return SVal(); |
| 242 |
return getSVal(getRegion(SelfDecl, LCtx)); |
| 243 |
} |
| 244 |
|
| 245 |
SVal ProgramState::getSValAsScalarOrLoc(const MemRegion *R) const { |
| 246 |
// We only want to do fetches from regions that we can actually bind |
| 247 |
// values. For example, SymbolicRegions of type 'id<...>' cannot |
| 248 |
// have direct bindings (but their can be bindings on their subregions). |
| 249 |
if (!R->isBoundable()) |
| 250 |
return UnknownVal(); |
| 251 |
|
| 252 |
if (const TypedValueRegion *TR = dyn_cast<TypedValueRegion>(R)) { |
| 253 |
QualType T = TR->getValueType(); |
| 254 |
if (Loc::isLocType(T) || T->isIntegralOrEnumerationType()) |
| 255 |
return getSVal(R); |
| 256 |
} |
| 257 |
|
| 258 |
return UnknownVal(); |
| 259 |
} |
| 260 |
|
| 261 |
SVal ProgramState::getSVal(Loc location, QualType T) const { |
| 262 |
SVal V = getRawSVal(location, T); |
| 263 |
|
| 264 |
// If 'V' is a symbolic value that is *perfectly* constrained to |
| 265 |
// be a constant value, use that value instead to lessen the burden |
| 266 |
// on later analysis stages (so we have less symbolic values to reason |
| 267 |
// about). |
| 268 |
// We only go into this branch if we can convert the APSInt value we have |
| 269 |
// to the type of T, which is not always the case (e.g. for void). |
| 270 |
if (!T.isNull() && (T->isIntegralOrEnumerationType() || Loc::isLocType(T))) { |
| 271 |
if (SymbolRef sym = V.getAsSymbol()) { |
| 272 |
if (const llvm::APSInt *Int = getStateManager() |
| 273 |
.getConstraintManager() |
| 274 |
.getSymVal(this, sym)) { |
| 275 |
// FIXME: Because we don't correctly model (yet) sign-extension |
| 276 |
// and truncation of symbolic values, we need to convert |
| 277 |
// the integer value to the correct signedness and bitwidth. |
| 278 |
// |
| 279 |
// This shows up in the following: |
| 280 |
// |
| 281 |
// char foo(); |
| 282 |
// unsigned x = foo(); |
| 283 |
// if (x == 54) |
| 284 |
// ... |
| 285 |
// |
| 286 |
// The symbolic value stored to 'x' is actually the conjured |
| 287 |
// symbol for the call to foo(); the type of that symbol is 'char', |
| 288 |
// not unsigned. |
| 289 |
const llvm::APSInt &NewV = getBasicVals().Convert(T, *Int); |
| 290 |
|
| 291 |
if (V.getAs<Loc>()) |
| 292 |
return loc::ConcreteInt(NewV); |
| 293 |
else |
| 294 |
return nonloc::ConcreteInt(NewV); |
| 295 |
} |
| 296 |
} |
| 297 |
} |
| 298 |
|
| 299 |
return V; |
| 300 |
} |
| 301 |
|
| 302 |
ProgramStateRef ProgramState::BindExpr(const Stmt *S, |
| 303 |
const LocationContext *LCtx, |
| 304 |
SVal V, bool Invalidate) const{ |
| 305 |
Environment NewEnv = |
| 306 |
getStateManager().EnvMgr.bindExpr(Env, EnvironmentEntry(S, LCtx), V, |
| 307 |
Invalidate); |
| 308 |
if (NewEnv == Env) |
| 309 |
return this; |
| 310 |
|
| 311 |
ProgramState NewSt = *this; |
| 312 |
NewSt.Env = NewEnv; |
| 313 |
return getStateManager().getPersistentState(NewSt); |
| 314 |
} |
| 315 |
|
| 316 |
[[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef> |
| 317 |
ProgramState::assumeInBoundDual(DefinedOrUnknownSVal Idx, |
| 318 |
DefinedOrUnknownSVal UpperBound, |
| 319 |
QualType indexTy) const { |
| 320 |
if (Idx.isUnknown() || UpperBound.isUnknown()) |
| 321 |
return {this, this}; |
| 322 |
|
| 323 |
// Build an expression for 0 <= Idx < UpperBound. |
| 324 |
// This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed. |
| 325 |
// FIXME: This should probably be part of SValBuilder. |
| 326 |
ProgramStateManager &SM = getStateManager(); |
| 327 |
SValBuilder &svalBuilder = SM.getSValBuilder(); |
| 328 |
ASTContext &Ctx = svalBuilder.getContext(); |
| 329 |
|
| 330 |
// Get the offset: the minimum value of the array index type. |
| 331 |
BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); |
| 332 |
if (indexTy.isNull()) |
| 333 |
indexTy = svalBuilder.getArrayIndexType(); |
| 334 |
nonloc::ConcreteInt Min(BVF.getMinValue(indexTy)); |
| 335 |
|
| 336 |
// Adjust the index. |
| 337 |
SVal newIdx = svalBuilder.evalBinOpNN(this, BO_Add, |
| 338 |
Idx.castAs<NonLoc>(), Min, indexTy); |
| 339 |
if (newIdx.isUnknownOrUndef()) |
| 340 |
return {this, this}; |
| 341 |
|
| 342 |
// Adjust the upper bound. |
| 343 |
SVal newBound = |
| 344 |
svalBuilder.evalBinOpNN(this, BO_Add, UpperBound.castAs<NonLoc>(), |
| 345 |
Min, indexTy); |
| 346 |
|
| 347 |
if (newBound.isUnknownOrUndef()) |
| 348 |
return {this, this}; |
| 349 |
|
| 350 |
// Build the actual comparison. |
| 351 |
SVal inBound = svalBuilder.evalBinOpNN(this, BO_LT, newIdx.castAs<NonLoc>(), |
| 352 |
newBound.castAs<NonLoc>(), Ctx.IntTy); |
| 353 |
if (inBound.isUnknownOrUndef()) |
| 354 |
return {this, this}; |
| 355 |
|
| 356 |
// Finally, let the constraint manager take care of it. |
| 357 |
ConstraintManager &CM = SM.getConstraintManager(); |
| 358 |
return CM.assumeDual(this, inBound.castAs<DefinedSVal>()); |
| 359 |
} |
| 360 |
|
| 361 |
ProgramStateRef ProgramState::assumeInBound(DefinedOrUnknownSVal Idx, |
| 362 |
DefinedOrUnknownSVal UpperBound, |
| 363 |
bool Assumption, |
| 364 |
QualType indexTy) const { |
| 365 |
std::pair<ProgramStateRef, ProgramStateRef> R = |
| 366 |
assumeInBoundDual(Idx, UpperBound, indexTy); |
| 367 |
return Assumption ? R.first : R.second; |
| 368 |
} |
| 369 |
|
| 370 |
ConditionTruthVal ProgramState::isNonNull(SVal V) const { |
| 371 |
ConditionTruthVal IsNull = isNull(V); |
| 372 |
if (IsNull.isUnderconstrained()) |
| 373 |
return IsNull; |
| 374 |
return ConditionTruthVal(!IsNull.getValue()); |
| 375 |
} |
| 376 |
|
| 377 |
ConditionTruthVal ProgramState::areEqual(SVal Lhs, SVal Rhs) const { |
| 378 |
return stateMgr->getSValBuilder().areEqual(this, Lhs, Rhs); |
| 379 |
} |
| 380 |
|
| 381 |
ConditionTruthVal ProgramState::isNull(SVal V) const { |
| 382 |
if (V.isZeroConstant()) |
| 383 |
return true; |
| 384 |
|
| 385 |
if (V.isConstant()) |
| 386 |
return false; |
| 387 |
|
| 388 |
SymbolRef Sym = V.getAsSymbol(/* IncludeBaseRegion */ true); |
| 389 |
if (!Sym) |
| 390 |
return ConditionTruthVal(); |
| 391 |
|
| 392 |
return getStateManager().ConstraintMgr->isNull(this, Sym); |
| 393 |
} |
| 394 |
|
| 395 |
ProgramStateRef ProgramStateManager::getInitialState(const LocationContext *InitLoc) { |
| 396 |
ProgramState State(this, |
| 397 |
EnvMgr.getInitialEnvironment(), |
| 398 |
StoreMgr->getInitialStore(InitLoc), |
| 399 |
GDMFactory.getEmptyMap()); |
| 400 |
|
| 401 |
return getPersistentState(State); |
| 402 |
} |
| 403 |
|
| 404 |
ProgramStateRef ProgramStateManager::getPersistentStateWithGDM( |
| 405 |
ProgramStateRef FromState, |
| 406 |
ProgramStateRef GDMState) { |
| 407 |
ProgramState NewState(*FromState); |
| 408 |
NewState.GDM = GDMState->GDM; |
| 409 |
return getPersistentState(NewState); |
| 410 |
} |
| 411 |
|
| 412 |
ProgramStateRef ProgramStateManager::getPersistentState(ProgramState &State) { |
| 413 |
|
| 414 |
llvm::FoldingSetNodeID ID; |
| 415 |
State.Profile(ID); |
| 416 |
void *InsertPos; |
| 417 |
|
| 418 |
if (ProgramState *I = StateSet.FindNodeOrInsertPos(ID, InsertPos)) |
| 419 |
return I; |
| 420 |
|
| 421 |
ProgramState *newState = nullptr; |
| 422 |
if (!freeStates.empty()) { |
| 423 |
newState = freeStates.back(); |
| 424 |
freeStates.pop_back(); |
| 425 |
} |
| 426 |
else { |
| 427 |
newState = (ProgramState*) Alloc.Allocate<ProgramState>(); |
| 428 |
} |
| 429 |
new (newState) ProgramState(State); |
| 430 |
StateSet.InsertNode(newState, InsertPos); |
| 431 |
return newState; |
| 432 |
} |
| 433 |
|
| 434 |
ProgramStateRef ProgramState::makeWithStore(const StoreRef &store) const { |
| 435 |
ProgramState NewSt(*this); |
| 436 |
NewSt.setStore(store); |
| 437 |
return getStateManager().getPersistentState(NewSt); |
| 438 |
} |
| 439 |
|
| 440 |
ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const { |
| 441 |
ProgramState NewSt(*this); |
| 442 |
NewSt.PosteriorlyOverconstrained = true; |
| 443 |
return getStateManager().getPersistentState(NewSt); |
| 444 |
} |
| 445 |
|
| 446 |
void ProgramState::setStore(const StoreRef &newStore) { |
| 447 |
Store newStoreStore = newStore.getStore(); |
| 448 |
if (newStoreStore) |
| 449 |
stateMgr->getStoreManager().incrementReferenceCount(newStoreStore); |
| 450 |
if (store) |
| 451 |
stateMgr->getStoreManager().decrementReferenceCount(store); |
| 452 |
store = newStoreStore; |
| 453 |
} |
| 454 |
|
| 455 |
//===----------------------------------------------------------------------===// |
| 456 |
// State pretty-printing. |
| 457 |
//===----------------------------------------------------------------------===// |
| 458 |
|
| 459 |
void ProgramState::printJson(raw_ostream &Out, const LocationContext *LCtx, |
| 460 |
const char *NL, unsigned int Space, |
| 461 |
bool IsDot) const { |
| 462 |
Indent(Out, Space, IsDot) << "\"program_state\": {" << NL; |
| 463 |
++Space; |
| 464 |
|
| 465 |
ProgramStateManager &Mgr = getStateManager(); |
| 466 |
|
| 467 |
// Print the store. |
| 468 |
Mgr.getStoreManager().printJson(Out, getStore(), NL, Space, IsDot); |
| 469 |
|
| 470 |
// Print out the environment. |
| 471 |
Env.printJson(Out, Mgr.getContext(), LCtx, NL, Space, IsDot); |
| 472 |
|
| 473 |
// Print out the constraints. |
| 474 |
Mgr.getConstraintManager().printJson(Out, this, NL, Space, IsDot); |
| 475 |
|
| 476 |
// Print out the tracked dynamic types. |
| 477 |
printDynamicTypeInfoJson(Out, this, NL, Space, IsDot); |
| 478 |
|
| 479 |
// Print checker-specific data. |
| 480 |
Mgr.getOwningEngine().printJson(Out, this, LCtx, NL, Space, IsDot); |
| 481 |
|
| 482 |
--Space; |
| 483 |
Indent(Out, Space, IsDot) << '}'; |
| 484 |
} |
| 485 |
|
| 486 |
void ProgramState::printDOT(raw_ostream &Out, const LocationContext *LCtx, |
| 487 |
unsigned int Space) const { |
| 488 |
printJson(Out, LCtx, /*NL=*/"\\l", Space, /*IsDot=*/true); |
| 489 |
} |
| 490 |
|
| 491 |
LLVM_DUMP_METHOD void ProgramState::dump() const { |
| 492 |
printJson(llvm::errs()); |
| 493 |
} |
| 494 |
|
| 495 |
AnalysisManager& ProgramState::getAnalysisManager() const { |
| 496 |
return stateMgr->getOwningEngine().getAnalysisManager(); |
| 497 |
} |
| 498 |
|
| 499 |
//===----------------------------------------------------------------------===// |
| 500 |
// Generic Data Map. |
| 501 |
//===----------------------------------------------------------------------===// |
| 502 |
|
| 503 |
void *const* ProgramState::FindGDM(void *K) const { |
| 504 |
return GDM.lookup(K); |
| 505 |
} |
| 506 |
|
| 507 |
void* |
| 508 |
ProgramStateManager::FindGDMContext(void *K, |
| 509 |
void *(*CreateContext)(llvm::BumpPtrAllocator&), |
| 510 |
void (*DeleteContext)(void*)) { |
| 511 |
|
| 512 |
std::pair<void*, void (*)(void*)>& p = GDMContexts[K]; |
| 513 |
if (!p.first) { |
| 514 |
p.first = CreateContext(Alloc); |
| 515 |
p.second = DeleteContext; |
| 516 |
} |
| 517 |
|
| 518 |
return p.first; |
| 519 |
} |
| 520 |
|
| 521 |
ProgramStateRef ProgramStateManager::addGDM(ProgramStateRef St, void *Key, void *Data){ |
| 522 |
ProgramState::GenericDataMap M1 = St->getGDM(); |
| 523 |
ProgramState::GenericDataMap M2 = GDMFactory.add(M1, Key, Data); |
| 524 |
|
| 525 |
if (M1 == M2) |
| 526 |
return St; |
| 527 |
|
| 528 |
ProgramState NewSt = *St; |
| 529 |
NewSt.GDM = M2; |
| 530 |
return getPersistentState(NewSt); |
| 531 |
} |
| 532 |
|
| 533 |
ProgramStateRef ProgramStateManager::removeGDM(ProgramStateRef state, void *Key) { |
| 534 |
ProgramState::GenericDataMap OldM = state->getGDM(); |
| 535 |
ProgramState::GenericDataMap NewM = GDMFactory.remove(OldM, Key); |
| 536 |
|
| 537 |
if (NewM == OldM) |
| 538 |
return state; |
| 539 |
|
| 540 |
ProgramState NewState = *state; |
| 541 |
NewState.GDM = NewM; |
| 542 |
return getPersistentState(NewState); |
| 543 |
} |
| 544 |
|
| 545 |
bool ScanReachableSymbols::scan(nonloc::LazyCompoundVal val) { |
| 546 |
bool wasVisited = !visited.insert(val.getCVData()).second; |
| 547 |
if (wasVisited) |
| 548 |
return true; |
| 549 |
|
| 550 |
StoreManager &StoreMgr = state->getStateManager().getStoreManager(); |
| 551 |
// FIXME: We don't really want to use getBaseRegion() here because pointer |
| 552 |
// arithmetic doesn't apply, but scanReachableSymbols only accepts base |
| 553 |
// regions right now. |
| 554 |
const MemRegion *R = val.getRegion()->getBaseRegion(); |
| 555 |
return StoreMgr.scanReachableSymbols(val.getStore(), R, *this); |
| 556 |
} |
| 557 |
|
| 558 |
bool ScanReachableSymbols::scan(nonloc::CompoundVal val) { |
| 559 |
for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I) |
| 560 |
if (!scan(*I)) |
| 561 |
return false; |
| 562 |
|
| 563 |
return true; |
| 564 |
} |
| 565 |
|
| 566 |
bool ScanReachableSymbols::scan(const SymExpr *sym) { |
| 567 |
for (SymExpr::symbol_iterator SI = sym->symbol_begin(), |
| 568 |
SE = sym->symbol_end(); |
| 569 |
SI != SE; ++SI) { |
| 570 |
bool wasVisited = !visited.insert(*SI).second; |
| 571 |
if (wasVisited) |
| 572 |
continue; |
| 573 |
|
| 574 |
if (!visitor.VisitSymbol(*SI)) |
| 575 |
return false; |
| 576 |
} |
| 577 |
|
| 578 |
return true; |
| 579 |
} |
| 580 |
|
| 581 |
bool ScanReachableSymbols::scan(SVal val) { |
| 582 |
if (std::optional<loc::MemRegionVal> X = val.getAs<loc::MemRegionVal>()) |
| 583 |
return scan(X->getRegion()); |
| 584 |
|
| 585 |
if (std::optional<nonloc::LazyCompoundVal> X = |
| 586 |
val.getAs<nonloc::LazyCompoundVal>()) |
| 587 |
return scan(*X); |
| 588 |
|
| 589 |
if (std::optional<nonloc::LocAsInteger> X = val.getAs<nonloc::LocAsInteger>()) |
| 590 |
return scan(X->getLoc()); |
| 591 |
|
| 592 |
if (SymbolRef Sym = val.getAsSymbol()) |
| 593 |
return scan(Sym); |
| 594 |
|
| 595 |
if (std::optional<nonloc::CompoundVal> X = val.getAs<nonloc::CompoundVal>()) |
| 596 |
return scan(*X); |
| 597 |
|
| 598 |
return true; |
| 599 |
} |
| 600 |
|
| 601 |
bool ScanReachableSymbols::scan(const MemRegion *R) { |
| 602 |
if (isa<MemSpaceRegion>(R)) |
| 603 |
return true; |
| 604 |
|
| 605 |
bool wasVisited = !visited.insert(R).second; |
| 606 |
if (wasVisited) |
| 607 |
return true; |
| 608 |
|
| 609 |
if (!visitor.VisitMemRegion(R)) |
| 610 |
return false; |
| 611 |
|
| 612 |
// If this is a symbolic region, visit the symbol for the region. |
| 613 |
if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) |
| 614 |
if (!visitor.VisitSymbol(SR->getSymbol())) |
| 615 |
return false; |
| 616 |
|
| 617 |
// If this is a subregion, also visit the parent regions. |
| 618 |
if (const SubRegion *SR = dyn_cast<SubRegion>(R)) { |
| 619 |
const MemRegion *Super = SR->getSuperRegion(); |
| 620 |
if (!scan(Super)) |
| 621 |
return false; |
| 622 |
|
| 623 |
// When we reach the topmost region, scan all symbols in it. |
| 624 |
if (isa<MemSpaceRegion>(Super)) { |
| 625 |
StoreManager &StoreMgr = state->getStateManager().getStoreManager(); |
| 626 |
if (!StoreMgr.scanReachableSymbols(state->getStore(), SR, *this)) |
| 627 |
return false; |
| 628 |
} |
| 629 |
} |
| 630 |
|
| 631 |
// Regions captured by a block are also implicitly reachable. |
| 632 |
if (const BlockDataRegion *BDR = dyn_cast<BlockDataRegion>(R)) { |
| 633 |
BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(), |
| 634 |
E = BDR->referenced_vars_end(); |
| 635 |
for ( ; I != E; ++I) { |
| 636 |
if (!scan(I.getCapturedRegion())) |
| 637 |
return false; |
| 638 |
} |
| 639 |
} |
| 640 |
|
| 641 |
return true; |
| 642 |
} |
| 643 |
|
| 644 |
bool ProgramState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const { |
| 645 |
ScanReachableSymbols S(this, visitor); |
| 646 |
return S.scan(val); |
| 647 |
} |
| 648 |
|
| 649 |
bool ProgramState::scanReachableSymbols( |
| 650 |
llvm::iterator_range<region_iterator> Reachable, |
| 651 |
SymbolVisitor &visitor) const { |
| 652 |
ScanReachableSymbols S(this, visitor); |
| 653 |
for (const MemRegion *R : Reachable) { |
| 654 |
if (!S.scan(R)) |
| 655 |
return false; |
| 656 |
} |
| 657 |
return true; |
| 658 |
} |