ProgramState.h Source File (original) (raw)

13#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H

14#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATE_H

23#include "llvm/ADT/FoldingSet.h"

24#include "llvm/ADT/ImmutableMap.h"

25#include "llvm/Support/Allocator.h"

26#include

27#include

29namespace llvm {

31}

36namespace ento {

72public:

75private:

76 void operator=(const ProgramState& R) = delete;

84 Environment Env;

85 Store store;

86 GenericDataMap GDM;

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114 bool PosteriorlyOverconstrained = false;

115

116

117

119 bool isPosteriorlyOverconstrained() const {

120 return PosteriorlyOverconstrained;

121 }

122 ProgramStateRef cloneAsPosteriorlyOverconstrained() const;

123

124 unsigned refCount;

125

126

127

130

131 void setStore(const StoreRef &storeRef);

132

133public:

134

137

138

139

141

143

144 int64_t getID() const;

145

146

148 return *stateMgr;

149 }

150

152

153

155

156

157

159

160

161

163

164

166

168

169

170

171

173 V->Env.Profile(ID);

174 ID.AddPointer(V->store);

175 V->GDM.Profile(ID);

176 ID.AddBoolean(V->PosteriorlyOverconstrained);

177 }

178

179

180

181 void Profile(llvm::FoldingSetNodeID& ID) const {

183 }

184

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

220 bool assumption) const;

221

222

223

224

225

226

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

229

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

233

237

238

239

240

241

242

243

245 const llvm::APSInt &From,

246 const llvm::APSInt &To,

247 bool assumption) const;

248

249

250

251

252

253

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

256 const llvm::APSInt &To) const;

257

258

259

261

262

263

265

266

268

269

270 LLVM_ATTRIBUTE_RETURNS_NONNULL

272

273

274

275

276

277

278

281 bool Invalidate = true) const;

282

285 bool notifyChanges = true) const;

286

289

290

291

292

293

294

295

298

299

300

303

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

334

341

342

343

347

348

350

351

353

354

356 bool IsVirtual) const;

357

358

360

363

364

366

367

369

370

372

373

375

376

378

380

381

382

384

385

387

388

389

391

392

393

394

395

397

399

400

401

402

403

404

405

406

408

409

410

413

415 template CB

417

418

419

420

421

422 void *const* FindGDM(void *K) const;

423

424 template

427

428 template

433

434 template

440

441 template

443

444 template

447

448 template

452

454

455 template

458

459 template

463

464 template

469

470 template

475

476

478 const char *NL = "\n", unsigned int Space = 0,

479 bool IsDot = false) const;

480

482 unsigned int Space = 0) const;

483

484 void dump() const;

485

486private:

489

490 SVal desugarReference(SVal Val) const;

492};

493

494

495

496

497

501private:

502

504

506 std::unique_ptr StoreMgr;

507 std::unique_ptr ConstraintMgr;

508

509 ProgramState::GenericDataMap::Factory GDMFactory;

510

511 typedef llvm::DenseMap<void*,std::pair<void*,void (*)(void*)> > GDMContextsTy;

512 GDMContextsTy GDMContexts;

513

514

515

516 llvm::FoldingSet StateSet;

517

518

519 std::unique_ptr svalBuilder;

520

521

522 std::unique_ptr CallEventMgr;

523

524

525 llvm::BumpPtrAllocator &Alloc;

526

527

528 std::vector<ProgramState *> freeStates;

529

530public:

534 llvm::BumpPtrAllocator& alloc,

536

538

540

543

545 return svalBuilder->getBasicValueFactory();

546 }

547

549 return *svalBuilder;

550 }

551

553 return *svalBuilder;

554 }

555

557 return svalBuilder->getSymbolManager();

558 }

560 return svalBuilder->getSymbolManager();

561 }

562

564

566 return svalBuilder->getRegionManager();

567 }

569 return svalBuilder->getRegionManager();

570 }

571

573

578 return *ConstraintMgr;

579 }

581

586

587public:

588

590 return StoreMgr->ArrayToPointer(Array, ElementTy);

591 }

592

593

596

597

598

600 StoreMgr->iterBindings(state->getStore(), F);

601 }

602

606

608 return ConstraintMgr->haveEqualConstraints(S1, S2);

609 }

610

612 return S1->Env == S2->Env;

613 }

614

616 return S1->store == S2->store;

617 }

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638 template

643

644 template

653

654 template

661

662 template

670

671 template

675

677 void *(*CreateContext)(llvm::BumpPtrAllocator&),

678 void (*DeleteContext)(void*));

679

680 template

688};

689

690

691

692

693

694

696 return stateMgr->getConstraintManager();

697}

698

704

706 bool Assumption) const {

707 if (Cond.isUnknown())

708 return this;

709

712}

713

714inline std::pair<ProgramStateRef , ProgramStateRef >

716 if (Cond.isUnknown())

717 return std::make_pair(this, this);

718

721}

722

725 bool Assumption) const {

727 return this;

728

729 assert(isa(Val) && "Only NonLocs are supported!");

730

731 return getStateManager().ConstraintMgr->assumeInclusiveRange(

732 this, Val.castAs<NonLoc>(), From, To, Assumption);

733}

734

735inline std::pair<ProgramStateRef, ProgramStateRef>

737 const llvm::APSInt &From,

738 const llvm::APSInt &To) const {

740 return std::make_pair(this, this);

741

742 assert(isa(Val) && "Only NonLocs are supported!");

743

744 return getStateManager().ConstraintMgr->assumeInclusiveRangeDual(

746}

747

749 if (std::optional L = LV.getAs<Loc>())

751 return this;

752}

753

761

764 bool IsVirtual) const {

766 getStateManager().getRegionManager().getCXXBaseObjectRegion(

767 BaseClass, Super, IsVirtual));

768}

769

774

777 return getStateManager().StoreMgr->getLValueCompoundLiteral(literal, LC);

778}

779

783

789

795

799 if (const Expr *Ex = dyn_cast(S)) {

802 T->isIntegralOrEnumerationType())

804 }

805

807}

808

812

818

822

826

827template

831

832template

836

837template

841

842template

847

848template

852

853template

857

858template

863

864template

870

871template

873 CB cb(this);

875 return cb;

876}

877

878template

880 llvm::iterator_range<region_iterator> Reachable) const {

881 CB cb(this);

883 return cb;

884}

885

886

887

888

889

891 typedef llvm::DenseSet<const void*> VisitedItems;

892

893 VisitedItems visited;

896public:

898 : state(std::move(st)), visitor(v) {}

899

905};

906

907}

908

909}

910

911#endif

Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.

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

Represents a base class of a C++ class.

bool isVirtual() const

Determines whether the base class is a virtual base class (or not).

QualType getType() const

Retrieves the type of the base class.

Represents a C++ struct/union/class.

CompoundLiteralExpr - [C99 6.5.2.5].

This represents one expression.

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 ...

ObjCIvarDecl - Represents an ObjC instance variable.

A (possibly-)qualified type.

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

Stmt - This represents one statement.

CXXRecordDecl * getAsCXXRecordDecl() const

Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...

Represents a variable declaration or definition.

Manages the lifetime of CallEvent objects.

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

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

An immutable map from EnvironemntEntries to SVals.

static bool isLocType(QualType T)

const VarRegion * getVarRegion(const VarDecl *VD, const LocationContext *LC)

getVarRegion - Retrieve or create the memory region associated with a specified VarDecl and LocationC...

MemRegion - The root abstract class for all memory regions.

Definition ProgramState.h:498

SValBuilder & getSValBuilder()

Definition ProgramState.h:548

ProgramStateRef remove(ProgramStateRef st)

Definition ProgramState.h:672

const MemRegionManager & getRegionManager() const

Definition ProgramState.h:568

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

bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) const

Definition ProgramState.h:615

ExprEngine & getOwningEngine()

Definition ProgramState.h:580

const ASTContext & getContext() const

Definition ProgramState.h:542

const StoreManager & getStoreManager() const

Definition ProgramState.h:575

ProgramStateRef removeGDM(ProgramStateRef state, void *Key)

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

CallEventManager & getCallEventManager()

Definition ProgramState.h:572

bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) const

Definition ProgramState.h:611

const SymbolManager & getSymbolManager() const

Definition ProgramState.h:559

const SValBuilder & getSValBuilder() const

Definition ProgramState.h:552

friend class ProgramState

Definition ProgramState.h:499

friend void ProgramStateRelease(const ProgramState *state)

Decrement the number of times this state is referenced.

ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait< T >::data_type D)

Definition ProgramState.h:639

ASTContext & getContext()

Definition ProgramState.h:541

ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, ProgramStateRef GDMState)

MemRegionManager & getRegionManager()

Definition ProgramState.h:565

bool haveEqualConstraints(ProgramStateRef S1, ProgramStateRef S2) const

Definition ProgramState.h:607

ProgramStateRef remove(ProgramStateRef st, typename ProgramStateTrait< T >::key_type K, typename ProgramStateTrait< T >::context_type C)

Definition ProgramState.h:663

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

ProgramStateRef set(ProgramStateRef st, typename ProgramStateTrait< T >::key_type K, typename ProgramStateTrait< T >::value_type V, typename ProgramStateTrait< T >::context_type C)

Definition ProgramState.h:645

ProgramStateRef add(ProgramStateRef st, typename ProgramStateTrait< T >::key_type K, typename ProgramStateTrait< T >::context_type C)

Definition ProgramState.h:655

ProgramStateRef getPersistentState(ProgramState &Impl)

void iterBindings(ProgramStateRef state, StoreManager::BindingsHandler &F)

Definition ProgramState.h:599

SVal ArrayToPointer(Loc Array, QualType ElementTy)

Definition ProgramState.h:589

const ConstraintManager & getConstraintManager() const

Definition ProgramState.h:577

ProgramStateRef getInitialState(const LocationContext *InitLoc)

llvm::BumpPtrAllocator & getAllocator()

Definition ProgramState.h:563

BasicValueFactory & getBasicVals()

Definition ProgramState.h:544

StoreManager & getStoreManager()

Definition ProgramState.h:574

ProgramStateTrait< T >::context_type get_context()

Definition ProgramState.h:681

SymbolManager & getSymbolManager()

Definition ProgramState.h:556

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

ConstraintManager & getConstraintManager()

Definition ProgramState.h:576

ProgramState - This class encapsulates:

Definition ProgramState.h:71

bool scanReachableSymbols(SVal val, SymbolVisitor &visitor) const

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

ProgramStateTrait< T >::data_type get() const

Definition ProgramState.h:430

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

Get the lvalue for a base class object reference.

Definition ProgramState.h:754

friend void ProgramStateRetain(const ProgramState *state)

Increments the number of times this state is referenced.

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

Definition ProgramState.h:73

friend class ProgramStateManager

Definition ProgramState.h:78

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.

friend class ExplodedGraph

Definition ProgramState.h:79

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

ProgramStateRef assumeInclusiveRange(DefinedOrUnknownSVal Val, const llvm::APSInt &From, const llvm::APSInt &To, bool assumption) const

Assumes that the value of Val is bounded with [From; To] (if assumption is "true") or it is fully out...

Definition ProgramState.h:723

bool contains(typename ProgramStateTrait< T >::key_type key) const

Definition ProgramState.h:471

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.

Definition ProgramState.h:695

ProgramStateRef add(typename ProgramStateTrait< T >::key_type K) const

Definition ProgramState.h:828

friend class NodeBuilder

Definition ProgramState.h:81

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

Definition ProgramState.h:797

void Profile(llvm::FoldingSetNodeID &ID) const

Profile - Used to profile the contents of this object for inclusion in a FoldingSet.

Definition ProgramState.h:181

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 simplification.

Definition ProgramState.h:809

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.

Definition ProgramState.h:147

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.

GenericDataMap getGDM() const

getGDM - Return the generic data map associated with this state.

Definition ProgramState.h:165

const Environment & getEnvironment() const

getEnvironment - Return the environment associated with this state.

Definition ProgramState.h:158

friend void ProgramStateRelease(const ProgramState *state)

Decrement the number of times this state is referenced.

ProgramStateRef assume(DefinedOrUnknownSVal cond, bool assumption) const

Assumes that the value of cond is zero (if assumption is "false") or non-zero (if assumption is "true...

Definition ProgramState.h:705

Store getStore() const

Return the store associated with this state.

Definition ProgramState.h:162

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 set(typename ProgramStateTrait< T >::data_type D) const

Definition ProgramState.h:854

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.

Definition ProgramState.h:699

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

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

Definition ProgramState.h:790

ProgramStateTrait< T >::lookup_type get(typename ProgramStateTrait< T >::key_type key) const

Definition ProgramState.h:436

const MemRegion ** region_iterator

Definition ProgramState.h:398

ProgramStateTrait< T >::context_type get_context() const

Definition ProgramState.h:833

ProgramStateRef invalidateRegions(ArrayRef< const MemRegion * > Regions, ConstCFGElementRef Elem, 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.

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

friend class ConstraintManager

Definition ProgramState.h:118

static void Profile(llvm::FoldingSetNodeID &ID, const ProgramState *V)

Profile - Profile the contents of a ProgramState object for use in a FoldingSet.

Definition ProgramState.h:172

BasicValueFactory & getBasicVals() const

Definition ProgramState.h:819

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

ProgramStateRef invalidateRegions(ArrayRef< SVal > Values, ConstCFGElementRef Elem, unsigned BlockCount, const LocationContext *LCtx, bool CausesPointerEscape, InvalidatedSymbols *IS=nullptr, const CallEvent *Call=nullptr, RegionAndSymbolInvalidationTraits *ITraits=nullptr) const

ProgramStateRef remove() const

Definition ProgramState.h:849

void setGDM(GenericDataMap gdm)

Definition ProgramState.h:167

AnalysisManager & getAnalysisManager() const

friend class ExplodedNode

Definition ProgramState.h:80

void *const * FindGDM(void *K) const

SymbolManager & getSymbolManager() const

Definition ProgramState.h:823

Information about invalidation for a particular region/symbol.

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

std::optional< T > getAs() const

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

T castAs() const

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

ScanReachableSymbols(ProgramStateRef st, SymbolVisitor &v)

Definition ProgramState.h:897

bool scan(nonloc::LazyCompoundVal val)

SubRegion - A region that subsets another larger region.

A class responsible for cleaning up unused symbols.

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

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

const internal::VariadicAllOfMatcher< Decl > decl

Matches declarations.

llvm::DenseSet< SymbolRef > InvalidatedSymbols

IntrusiveRefCntPtr< const ProgramState > ProgramStateRef

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

Definition ProgramState.h:42

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

Definition ProgramState.h:44

const void * Store

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

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

bool isa(CodeGen::Address addr)

CFGBlock::ConstCFGElementRef ConstCFGElementRef

const FunctionProtoType * T

Diagnostic wrappers for TextAPI types for error reporting.

Definition ProgramState.h:51

T::data_type data_type

Definition ProgramState.h:52

static void * MakeVoidPtr(data_type D)

Definition ProgramState.h:53

static data_type MakeData(void *const *P)

Definition ProgramState.h:54