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}

34class ASTContext;

36namespace ento {

38class AnalysisManager;

39class CallEvent;

40class CallEventManager;

56 }

57};

72public:

75private:

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

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

129

130 void setStore(const StoreRef &storeRef);

131

132public:

133

136

137

138

140

142

143 int64_t getID() const;

144

145

147 return *stateMgr;

148 }

149

151

152

154

155

156

158

159

160

162

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

333

340

341

342

346

347

349

350

352

353

355 bool IsVirtual) const;

356

357

359

362

363

365

366

368

369

371

372

374

375

377

379

380

381

383

384

386

387

388

390

391

392

393

394

396

398

399

400

401

402

403

404

405

407

408

409

412

414 template CB

416

417

418

419

420

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

422

423 template

426

427 template

431 }

432

433 template

438 }

439

440 template

442

443 template

446

447 template

451

453

454 template

457

458 template

462

463 template

468

469 template

473 }

474

475

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

478 bool IsDot = false) const;

479

481 unsigned int Space = 0) const;

482

483 void dump() const;

484

485private:

488

489 SVal desugarReference(SVal Val) const;

491};

492

493

494

495

496

500private:

501

503

505 std::unique_ptr StoreMgr;

506 std::unique_ptr ConstraintMgr;

507

508 ProgramState::GenericDataMap::Factory GDMFactory;

509

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

511 GDMContextsTy GDMContexts;

512

513

514

515 llvm::FoldingSet StateSet;

516

517

518 std::unique_ptr svalBuilder;

519

520

521 std::unique_ptr CallEventMgr;

522

523

524 llvm::BumpPtrAllocator &Alloc;

525

526

527 std::vector<ProgramState *> freeStates;

528

529public:

533 llvm::BumpPtrAllocator& alloc,

535

537

539

542

544 return svalBuilder->getBasicValueFactory();

545 }

546

548 return *svalBuilder;

549 }

550

552 return *svalBuilder;

553 }

554

556 return svalBuilder->getSymbolManager();

557 }

559 return svalBuilder->getSymbolManager();

560 }

561

563

565 return svalBuilder->getRegionManager();

566 }

568 return svalBuilder->getRegionManager();

569 }

570

572

576

581

582public:

583

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

586 }

587

588

591

592

593

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

596 }

597

601

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

604 }

605

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

608 }

609

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

612 }

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633 template

637 }

638

639 template

644

647 }

648

649 template

655 }

656

657 template

661

664 }

665

666 template

669 }

670

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

673 void (*DeleteContext)(void*));

674

675 template

680

682 }

683};

684

685

686

687

688

689

692}

693

696{

698}

699

701 bool Assumption) const {

703 return this;

704

707}

708

709inline std::pair<ProgramStateRef , ProgramStateRef >

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

713

716}

717

720 bool Assumption) const {

722 return this;

723

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

725

726 return getStateManager().ConstraintMgr->assumeInclusiveRange(

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

728}

729

730inline std::pair<ProgramStateRef, ProgramStateRef>

732 const llvm::APSInt &From,

733 const llvm::APSInt &To) const {

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

736

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

738

739 return getStateManager().ConstraintMgr->assumeInclusiveRangeDual(

741}

742

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

746 return this;

747}

748

753 getStateManager().getRegionManager().getCXXBaseObjectRegion(

755}

756

759 bool IsVirtual) const {

761 getStateManager().getRegionManager().getCXXBaseObjectRegion(

762 BaseClass, Super, IsVirtual));

763}

764

768}

769

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

773}

774

777}

778

780 if (std::optional N = Idx.getAs<NonLoc>())

781 return getStateManager().StoreMgr->getLValueElement(ElementType, *N, Base);

783}

784

789}

790

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

799 }

800

802}

803

806}

807

811 T);

812}

813

816}

817

820}

821

822template

825}

826

827template

830}

831

832template

835}

836

837template

841}

842

843template

846}

847

848template

851}

852

853template

857}

858

859template

864}

865

866template

868 CB cb(this);

870 return cb;

871}

872

873template

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

876 CB cb(this);

878 return cb;

879}

880

881

882

883

884

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

887

888 VisitedItems visited;

891public:

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

894

900};

901

902}

903

904}

905

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

bool isIntegralOrEnumerationType() const

Determine whether this type is an integral or enumeration type.

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.

This is the simplest builder which generates nodes in the ExplodedGraph.

SValBuilder & getSValBuilder()

ProgramStateRef remove(ProgramStateRef st)

const MemRegionManager & getRegionManager() const

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

bool haveEqualStores(ProgramStateRef S1, ProgramStateRef S2) const

ExprEngine & getOwningEngine()

const ASTContext & getContext() const

ProgramStateRef removeGDM(ProgramStateRef state, void *Key)

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

CallEventManager & getCallEventManager()

bool haveEqualEnvironments(ProgramStateRef S1, ProgramStateRef S2) const

const SymbolManager & getSymbolManager() const

const SValBuilder & getSValBuilder() const

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)

ASTContext & getContext()

ProgramStateRef getPersistentStateWithGDM(ProgramStateRef FromState, ProgramStateRef GDMState)

MemRegionManager & getRegionManager()

bool haveEqualConstraints(ProgramStateRef S1, ProgramStateRef S2) const

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

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)

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

ProgramStateRef getPersistentState(ProgramState &Impl)

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

SVal ArrayToPointer(Loc Array, QualType ElementTy)

ProgramStateRef getInitialState(const LocationContext *InitLoc)

llvm::BumpPtrAllocator & getAllocator()

BasicValueFactory & getBasicVals()

StoreManager & getStoreManager()

ProgramStateTrait< T >::context_type get_context()

SymbolManager & getSymbolManager()

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.

ProgramStateTrait< T >::data_type get() const

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

Get the lvalue for a base class object reference.

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

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

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

ProgramStateRef invalidateRegions(ArrayRef< SVal > Values, const Stmt *S, unsigned BlockCount, const LocationContext *LCtx, bool CausesPointerEscape, InvalidatedSymbols *IS=nullptr, const CallEvent *Call=nullptr, RegionAndSymbolInvalidationTraits *ITraits=nullptr) 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.

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

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

void Profile(llvm::FoldingSetNodeID &ID) const

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

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

GenericDataMap getGDM() const

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

const Environment & getEnvironment() const

getEnvironment - Return the environment associated with this state.

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

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

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.

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

ProgramStateTrait< T >::context_type get_context() const

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

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

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

BasicValueFactory & getBasicVals() const

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

ProgramStateRef remove() const

void setGDM(GenericDataMap gdm)

AnalysisManager & getAnalysisManager() const

void *const * FindGDM(void *K) const

SymbolManager & getSymbolManager() const

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.

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

ScanReachableSymbols(ProgramStateRef st, SymbolVisitor &v)

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.

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.

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

const FunctionProtoType * T

Diagnostic wrappers for TextAPI types for error reporting.

static void * MakeVoidPtr(data_type D)

static data_type MakeData(void *const *P)