ProgramState.cpp Source File (original) (raw)

21#include "llvm/Support/raw_ostream.h"

22#include

24using namespace clang;

25using namespace ento;

27namespace clang { namespace ento {

32}

36 assert(state->refCount > 0);

38 if (--s->refCount == 0) {

40 Mgr.StateSet.RemoveNode(s);

41 s->~ProgramState();

42 Mgr.freeStates.push_back(s);

43 }

44}

45}}

49 : stateMgr(mgr),

51 store(st.getStore()),

52 GDM(gdm),

53 refCount(0) {

55}

58 : stateMgr(RHS.stateMgr), Env(RHS.Env), store(RHS.store), GDM(RHS.GDM),

59 PosteriorlyOverconstrained(RHS.PosteriorlyOverconstrained), refCount(0) {

61}

64 if (store)

66}

70}

75 llvm::BumpPtrAllocator &alloc,

77 : Eng(ExprEng), EnvMgr(alloc), GDMFactory(alloc),

80 StoreMgr = (*CreateSMgr)(*this);

81 ConstraintMgr = (*CreateCMgr)(*this, ExprEng);

82}

86 for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();

87 I!=E; ++I)

88 I->second.second(I->second.first);

89}

100

102

103 NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);

104

105

106 StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,

107 SymReaper);

108 NewState.setStore(newStore);

110

112}

113

117 bool notifyChanges) const {

120 LV, V));

122 if (MR && notifyChanges)

124

125 return newState;

126}

127

133 const StoreRef &newStore = Mgr.StoreMgr->BindDefaultInitial(getStore(), R, V);

136}

137

142 const StoreRef &newStore = Mgr.StoreMgr->BindDefaultZero(getStore(), R);

145}

146

149

156 for (const MemRegion *Reg : Regions)

158

159 return invalidateRegions(Values, S, Count, LCtx, CausedByPointerEscape, IS,

160 Call, ITraits);

161}

162

168

171

173 if (!IS)

174 IS = &InvalidatedSyms;

175

177 if (!ITraits)

178 ITraits = &ITraitsLocal;

179

182 const StoreRef &NewStore = Mgr.StoreMgr->invalidateRegions(

183 getStore(), Values, S, Count, LCtx, Call, *IS, *ITraits,

184 &TopLevelInvalidated, &Invalidated);

185

187

188 if (CausedByPointerEscape) {

190 NewState, IS, TopLevelInvalidated, Call, *ITraits);

191 }

192

194 Invalidated, LCtx, Call);

195}

196

201

202 if (newStore.getStore() == OldStore)

203 return this;

204

205 return makeWithStore(newStore);

206}

207

208

209

210

211SVal ProgramState::desugarReference(SVal Val) const {

212 const auto *TyReg = dyn_cast_or_null(Val.getAsRegion());

213 if (!TyReg || !TyReg->getValueType()->isReferenceType())

214 return Val;

216}

217

218

219

220

221

222SVal ProgramState::wrapSymbolicRegion(SVal Val) const {

223 const auto *BaseReg = dyn_cast_or_null(Val.getAsRegion());

224 if (!BaseReg)

225 return Val;

226

228 QualType ElemTy = BaseReg->getPointeeStaticType();

230}

231

237 return makeWithStore(NewStore);

238}

239

242 if (!SelfDecl)

243 return SVal();

245}

246

248

249

250

253

254 if (const TypedValueRegion *TR = dyn_cast(R)) {

258 }

259

261}

262

265

266

267

268

269

270

271

273 if (SymbolRef sym = V.getAsSymbol()) {

276 .getSymVal(this, sym)) {

277

278

279

280

281

282

283

284

285

286

287

288

289

290

292 if (V.getAs<Loc>())

295 }

296 }

297 }

298

299 return V;

300}

301

304 SVal V, bool Invalidate) const{

307 Invalidate);

308 if (NewEnv == Env)

309 return this;

310

312 NewSt.Env = NewEnv;

314}

315

316[[nodiscard]] std::pair<ProgramStateRef, ProgramStateRef>

321 return {this, this};

322

323

324

325

329

330

332 if (indexTy.isNull())

335

336

340 return {this, this};

341

342

343 SVal newBound =

345 Min, indexTy);

346

348 return {this, this};

349

350

354 return {this, this};

355

356

359}

360

363 bool Assumption,

365 std::pair<ProgramStateRef, ProgramStateRef> R =

367 return Assumption ? R.first : R.second;

368}

369

372 if (IsNull.isUnderconstrained())

375}

376

379}

380

382 if (V.isZeroConstant())

383 return true;

384

385 if (V.isConstant())

386 return false;

387

388 SymbolRef Sym = V.getAsSymbol( true);

389 if (!Sym)

391

392 return getStateManager().ConstraintMgr->isNull(this, Sym);

393}

394

398 StoreMgr->getInitialStore(InitLoc),

399 GDMFactory.getEmptyMap());

400

402}

403

408 NewState.GDM = GDMState->GDM;

410}

411

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

422 if (!freeStates.empty()) {

423 newState = freeStates.back();

424 freeStates.pop_back();

425 }

426 else {

428 }

430 StateSet.InsertNode(newState, InsertPos);

431 return newState;

432}

433

436 NewSt.setStore(store);

438}

439

440ProgramStateRef ProgramState::cloneAsPosteriorlyOverconstrained() const {

442 NewSt.PosteriorlyOverconstrained = true;

444}

445

446void ProgramState::setStore(const StoreRef &newStore) {

448 if (newStoreStore)

450 if (store)

452 store = newStoreStore;

453}

454

456 Base = desugarReference(Base);

457 Base = wrapSymbolicRegion(Base);

459}

460

463 Base = desugarReference(Base);

464 Base = wrapSymbolicRegion(Base);

465

466

467

468

469 for (const auto *I : D->chain()) {

470 Base = SM.getLValueField(cast(I), Base);

471 }

473}

474

475

476

477

478

480 const char *NL, unsigned int Space,

481 bool IsDot) const {

482 Indent(Out, Space, IsDot) << "\"program_state\": {" << NL;

483 ++Space;

484

486

487

489

490

492

493

495

496

498

499

501

502 --Space;

503 Indent(Out, Space, IsDot) << '}';

504}

505

507 unsigned int Space) const {

508 printJson(Out, LCtx, "\\l", Space, true);

509}

510

513}

514

517}

518

519

520

521

522

524 return GDM.lookup(K);

525}

526

527void*

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

544

545 if (M1 == M2)

546 return St;

547

549 NewSt.GDM = M2;

551}

552

556

557 if (NewM == OldM)

558 return state;

559

561 NewState.GDM = NewM;

563}

564

566 bool wasVisited = !visited.insert(val.getCVData()).second;

567 if (wasVisited)

568 return true;

569

570 StoreManager &StoreMgr = state->getStateManager().getStoreManager();

571

572

573

576}

577

579 for (SVal V : val)

581 return false;

582

583 return true;

584}

585

588 bool wasVisited = !visited.insert(SubSym).second;

589 if (wasVisited)

590 continue;

591

593 return false;

594 }

595

596 return true;

597}

598

601 return scan(X->getRegion());

602

603 if (std::optionalnonloc::LazyCompoundVal X =

606

608 return scan(X->getLoc());

609

611 return scan(Sym);

612

615

616 return true;

617}

618

620 if (isa(R))

621 return true;

622

623 bool wasVisited = !visited.insert(R).second;

624 if (wasVisited)

625 return true;

626

628 return false;

629

630

631 if (const SymbolicRegion *SR = dyn_cast(R))

632 if (!visitor.VisitSymbol(SR->getSymbol()))

633 return false;

634

635

636 if (const SubRegion *SR = dyn_cast(R)) {

637 const MemRegion *Super = SR->getSuperRegion();

638 if ( scan (Super))

639 return false;

640

641

642 if (isa(Super)) {

643 StoreManager &StoreMgr = state->getStateManager().getStoreManager();

645 return false;

646 }

647 }

648

649

650 if (const BlockDataRegion *BDR = dyn_cast(R)) {

651 for (auto Var : BDR->referenced_vars()) {

652 if ( scan (Var.getCapturedRegion()))

653 return false;

654 }

655 }

656

657 return true;

658}

659

662 return S.scan(val);

663}

664

666 llvm::iterator_range<region_iterator> Reachable,

669 for (const MemRegion *R : Reachable) {

670 if (!S.scan(R))

671 return false;

672 }

673 return true;

674}

ArrayRef< const MemRegion * > RegionList

ArrayRef< SVal > ValueList

__device__ __2f16 float __ockl_bool s

Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...

Represents a member of a struct/union/class.

Represents a field injected from an anonymous union/struct into the parent scope.

It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...

const ImplicitParamDecl * getSelfDecl() const

A (possibly-)qualified type.

bool isNull() const

Return true if this QualType doesn't point to a type yet.

It represents a stack frame of the call stack (based on CallEvent).

Stmt - This represents one statement.

bool isIntegralOrEnumerationType() const

Determine whether this type is an integral or enumeration type.

A safe wrapper around APSInt objects allocated and owned by BasicValueFactory.

APSIntPtr getMinValue(const llvm::APSInt &v)

APSIntPtr Convert(const llvm::APSInt &To, const llvm::APSInt &From)

Convert - Create a new persistent APSInt with the same value as 'From' but with the bitwidth and sign...

BlockDataRegion - A region that represents a block instance.

Manages the lifetime of CallEvent objects.

Represents an abstract call to a function or method along a particular path.

ProgramStatePair assumeDual(ProgramStateRef State, DefinedSVal Cond)

Returns a pair of states (StTrue, StFalse) where the given condition is assumed to be true or false,...

virtual void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL, unsigned int Space, bool IsDot) const =0

An entry in the environment consists of a Stmt and an LocationContext.

Environment getInitialEnvironment()

Environment bindExpr(Environment Env, const EnvironmentEntry &E, SVal V, bool Invalidate)

Bind a symbolic value to the given environment entry.

Environment removeDeadBindings(Environment Env, SymbolReaper &SymReaper, ProgramStateRef state)

An immutable map from EnvironemntEntries to SVals.

void printJson(raw_ostream &Out, const ASTContext &Ctx, const LocationContext *LCtx=nullptr, const char *NL="\n", unsigned int Space=0, bool IsDot=false) const

ProgramStateRef processRegionChange(ProgramStateRef state, const MemRegion *MR, const LocationContext *LCtx)

void printJson(raw_ostream &Out, ProgramStateRef State, const LocationContext *LCtx, const char *NL, unsigned int Space, bool IsDot) const

printJson - Called by ProgramStateManager to print checker-specific data.

ProgramStateRef processRegionChanges(ProgramStateRef state, const InvalidatedSymbols *invalidated, ArrayRef< const MemRegion * > ExplicitRegions, ArrayRef< const MemRegion * > Regions, const LocationContext *LCtx, const CallEvent *Call)

processRegionChanges - Called by ProgramStateManager whenever a change is made to the store.

ProgramStateRef notifyCheckersOfPointerEscape(ProgramStateRef State, const InvalidatedSymbols *Invalidated, ArrayRef< const MemRegion * > ExplicitRegions, const CallEvent *Call, RegionAndSymbolInvalidationTraits &ITraits)

Call PointerEscape callback when a value escapes as a result of region invalidation.

AnalysisManager & getAnalysisManager()

static bool isLocType(QualType T)

MemRegion - The root abstract class for all memory regions.

virtual bool isBoundable() const

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getBaseRegion() const

SValBuilder & getSValBuilder()

ProgramStateRef removeDeadBindingsFromEnvironmentAndStore(ProgramStateRef St, const StackFrameContext *LCtx, SymbolReaper &SymReaper)

ExprEngine & getOwningEngine()

ProgramStateRef removeGDM(ProgramStateRef state, void *Key)

void * FindGDMContext(void *index, void *(*CreateContext)(llvm::BumpPtrAllocator &), void(*DeleteContext)(void *))

friend class ProgramState

ASTContext & getContext()

ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, ProgramStateRef GDMState)

ProgramStateRef addGDM(ProgramStateRef St, void *Key, void *Data)

ProgramStateRef getPersistentState(ProgramState &Impl)

ProgramStateRef getInitialState(const LocationContext *InitLoc)

StoreManager & getStoreManager()

ProgramStateManager(ASTContext &Ctx, StoreManagerCreator CreateStoreManager, ConstraintManagerCreator CreateConstraintManager, llvm::BumpPtrAllocator &alloc, ExprEngine *expreng)

ConstraintManager & getConstraintManager()

ProgramState - This class encapsulates:

bool scanReachableSymbols(SVal val, SymbolVisitor &visitor) const

Visits the symbols reachable from the given SVal using the provided SymbolVisitor.

Loc getLValue(const CXXBaseSpecifier &BaseSpec, const SubRegion *Super) const

Get the lvalue for a base class object reference.

ProgramStateRef bindDefaultZero(SVal loc, const LocationContext *LCtx) const

Performs C++ zero-initialization procedure on the region of memory represented by loc.

llvm::ImmutableMap< void *, void * > GenericDataMap

ProgramStateRef BindExpr(const Stmt *S, const LocationContext *LCtx, SVal V, bool Invalidate=true) const

Create a new state by binding the value 'V' to the statement 'S' in the state's environment.

void printJson(raw_ostream &Out, const LocationContext *LCtx=nullptr, const char *NL="\n", unsigned int Space=0, bool IsDot=false) const

ProgramStateRef bindDefaultInitial(SVal loc, SVal V, const LocationContext *LCtx) const

Initializes the region of memory represented by loc with an initial value.

ConstraintManager & getConstraintManager() const

Return the ConstraintManager.

SVal getSValAsScalarOrLoc(const Stmt *Ex, const LocationContext *LCtx) const

ProgramStateRef invalidateRegions(ArrayRef< const MemRegion * > Regions, const Stmt *S, unsigned BlockCount, const LocationContext *LCtx, bool CausesPointerEscape, InvalidatedSymbols *IS=nullptr, const CallEvent *Call=nullptr, RegionAndSymbolInvalidationTraits *ITraits=nullptr) const

Returns the state with bindings for the given regions cleared from the store.

SVal getSelfSVal(const LocationContext *LC) const

Return the value of 'self' if available in the given context.

SVal getRawSVal(Loc LV, QualType T=QualType()) const

Returns the "raw" SVal bound to LV before any value simplfication.

ConditionTruthVal isNull(SVal V) const

Check if the given SVal is constrained to zero or is a zero constant.

ProgramStateManager & getStateManager() const

Return the ProgramStateManager associated with this state.

ProgramStateRef killBinding(Loc LV) const

ProgramState(ProgramStateManager *mgr, const Environment &env, StoreRef st, GenericDataMap gdm)

This ctor is used when creating the first ProgramState object.

Store getStore() const

Return the store associated with this state.

ConditionTruthVal areEqual(SVal Lhs, SVal Rhs) const

void printDOT(raw_ostream &Out, const LocationContext *LCtx=nullptr, unsigned int Space=0) const

ConditionTruthVal isNonNull(SVal V) const

Check if the given SVal is not constrained to zero and is not a zero constant.

ProgramStateRef assumeInBound(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, bool assumption, QualType IndexType=QualType()) const

ProgramStateRef enterStackFrame(const CallEvent &Call, const StackFrameContext *CalleeCtx) const

enterStackFrame - Returns the state for entry to the given stack frame, preserving the current state.

LLVM_ATTRIBUTE_RETURNS_NONNULL const VarRegion * getRegion(const VarDecl *D, const LocationContext *LC) const

Utility method for getting regions.

SVal getSVal(const Stmt *S, const LocationContext *LCtx) const

Returns the SVal bound to the statement 'S' in the state's environment.

ProgramStateRef bindLoc(Loc location, SVal V, const LocationContext *LCtx, bool notifyChanges=true) const

BasicValueFactory & getBasicVals() const

std::pair< ProgramStateRef, ProgramStateRef > assumeInBoundDual(DefinedOrUnknownSVal idx, DefinedOrUnknownSVal upperBound, QualType IndexType=QualType()) const

AnalysisManager & getAnalysisManager() const

void *const * FindGDM(void *K) const

Information about invalidation for a particular region/symbol.

BasicValueFactory & getBasicValueFactory()

ASTContext & getContext()

QualType getArrayIndexType() const

virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy)=0

Create a new value which represents a binary expression with two non- location operands.

ConditionTruthVal areEqual(ProgramStateRef state, SVal lhs, SVal rhs)

SVal - This represents a symbolic expression, which can be either an L-value or an R-value.

bool isUnknownOrUndef() const

SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const

If this SVal wraps a symbol return that SymbolRef.

std::optional< T > getAs() const

Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.

const MemRegion * getAsRegion() const

T castAs() const

Convert to the specified SVal type, asserting that this SVal is of the desired type.

A utility class that visits the reachable symbols using a custom SymbolVisitor.

bool scan(nonloc::LazyCompoundVal val)

virtual bool scanReachableSymbols(Store S, const MemRegion *R, ScanReachableSymbols &Visitor)=0

Finds the transitive closure of symbols within the given region.

virtual void decrementReferenceCount(Store store)

If the StoreManager supports it, decrement the reference count of the specified Store object.

virtual void incrementReferenceCount(Store store)

If the StoreManager supports it, increment the reference count of the specified Store object.

virtual void printJson(raw_ostream &Out, Store S, const char *NL, unsigned int Space, bool IsDot) const =0

SubRegion - A region that subsets another larger region.

llvm::iterator_range< symbol_iterator > symbols() const

A class responsible for cleaning up unused symbols.

void setReapedStore(StoreRef st)

Set to the value of the symbolic store after StoreManager::removeDeadBindings has been called.

virtual bool VisitMemRegion(const MemRegion *)

virtual bool VisitSymbol(SymbolRef sym)=0

A visitor method invoked by ProgramStateManager::scanReachableSymbols.

SymbolicRegion - A special, "non-concrete" region.

TypedValueRegion - An abstract class representing regions having a typed value.

The simplest example of a concrete compound value is nonloc::CompoundVal, which represents a concrete...

Value representing integer constant.

While nonloc::CompoundVal covers a few simple use cases, nonloc::LazyCompoundVal is a more performant...

LLVM_ATTRIBUTE_RETURNS_NONNULL const LazyCompoundValData * getCVData() const

LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion * getRegion() const

This function itself is immaterial.

const void * getStore() const

It might return null.

SValBuilder * createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, ProgramStateManager &stateMgr)

void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State, const char *NL="\n", unsigned int Space=0, bool IsDot=false)

std::unique_ptr< ConstraintManager >(* ConstraintManagerCreator)(ProgramStateManager &, ExprEngine *)

std::unique_ptr< StoreManager >(* StoreManagerCreator)(ProgramStateManager &)

llvm::DenseSet< SymbolRef > InvalidatedSymbols

const void * Store

Store - This opaque type encapsulates an immutable mapping from locations to values.

void ProgramStateRetain(const ProgramState *state)

Increments the number of times this state is referenced.

void ProgramStateRelease(const ProgramState *state)

Decrement the number of times this state is referenced.

The JSON file list parser is used to communicate input to InstallAPI.

const FunctionProtoType * T