RangedConstraintManager.h Source File (original) (raw)

13#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_RANGEDCONSTRAINTMANAGER_H

14#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_RANGEDCONSTRAINTMANAGER_H

19#include "llvm/ADT/APSInt.h"

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

24namespace ento {

30public:

31 Range(const llvm::APSInt &From, const llvm::APSInt &To) : Impl(&From, &To) {

33 }

35 Range(const llvm::APSInt &Point) : Range(Point, Point) {}

37 bool Includes(const llvm::APSInt &Point) const {

38 return From() <= Point && Point <= To();

39 }

40 const llvm::APSInt &From() const { return *Impl.first; }

41 const llvm::APSInt &To() const { return *Impl.second; }

43 return &From() == &To() ? &From() : nullptr;

44 }

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

47 ID.AddPointer(&From());

48 ID.AddPointer(&To());

49 }

50 void dump(raw_ostream &OS) const;

51 void dump() const;

57 bool operator==(const Range &RHS) const { return Impl == RHS.Impl; }

60private:

61 std::pair<const llvm::APSInt *, const llvm::APSInt *> Impl;

62};

72public:

75private:

97 struct ContainerType : public ImplType, public llvm::FoldingSetNode {

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

99 for (const Range &It : *this) {

101 }

102 }

103 };

104

105

106

107

108

109 using UnderlyingType = const ContainerType *;

110 UnderlyingType Impl;

111

112public:

114

117 size_t size() const { return Impl->size(); }

118

119 bool isEmpty() const { return Impl->empty(); }

120

122 public:

124

125

126

127

128

129

131

132

133

134

135

137

138

139

140

141

143

144

145

146

147

149

150

151

152

153

155

156

157

158

159

161

162

163

164

165

167

169

170

171

175 }

178 }

179

180

181

182

183

184

186

187

188

189

190

191

192

193

194

195

196

198

199

200

201

202

203

204

206

207

208

209

210

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

263

264

266

267 private:

268

269 RangeSet makePersistent(ContainerType &&From);

270

271 ContainerType *construct(ContainerType &&From);

272

273 RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS);

274

275

276 ContainerType unite(const ContainerType &LHS, const ContainerType &RHS);

277

278

279

280

282

283

284

285

286

288

289

290

291

293

294

295

297

298

299

300 llvm::SpecificBumpPtrAllocator Arena;

301

302

303 llvm::FoldingSet Cache;

304 static ContainerType EmptySet;

305 };

306

312

313

314 RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)

315 : RangeSet(F.getRangeSet(From, To)) {}

316

317

319 : RangeSet(F.getRangeSet(Point)) {}

320

322 ID.AddPointer(RS.Impl);

323 }

324

325

326

328

329

330

331

333 return Impl->size() == 1 ? begin()->getConcreteValue() : nullptr;

334 }

335

336

337

338

340

341

342

344

348

349

350

351

352

353 bool contains(llvm::APSInt Point) const { return containsImpl(Point); }

354

357 return contains(T.getZeroValue());

358 }

359

360

361

362

365 return Constant && Constant->isZero();

366 }

367

368

369

370

371

373

374 void dump(raw_ostream &OS) const;

375 void dump() const;

376

379

380private:

381 RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {}

382 RangeSet(UnderlyingType Ptr) : Impl(Ptr) {}

383

384

385

386

387

388

389

390

391

392

393

394 bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;

395 bool pin(llvm::APSInt &Point) const;

396

397

398

399 bool containsImpl(llvm::APSInt &Point) const;

400

402};

403

404using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>;

406

408public:

411

413

414

415

416

417

419 bool Assumption) override;

420

422 const llvm::APSInt &From,

423 const llvm::APSInt &To,

424 bool InRange) override;

425

427 bool Assumption) override;

428

429protected:

430

433 const llvm::APSInt &Int);

434

435

436

437

438

439

440

441

443 const llvm::APSInt &V,

444 const llvm::APSInt &Adjustment) = 0;

445

447 const llvm::APSInt &V,

448 const llvm::APSInt &Adjustment) = 0;

449

451 const llvm::APSInt &V,

452 const llvm::APSInt &Adjustment) = 0;

453

455 const llvm::APSInt &V,

456 const llvm::APSInt &Adjustment) = 0;

457

459 const llvm::APSInt &V,

460 const llvm::APSInt &Adjustment) = 0;

461

463 const llvm::APSInt &V,

464 const llvm::APSInt &Adjustment) = 0;

465

468 const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;

469

472 const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0;

473

474

475

476

477private:

478 static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment);

479};

480

481

482

483

484

485

486

487

488

490

491

492

493

494

496

497}

498}

499

501

502#endif

#define REGISTER_FACTORY_WITH_PROGRAMSTATE(Type)

Declares a factory for objects of type Type in the program state manager.

TypePropertyCache< Private > Cache

A (possibly-)qualified type.

A record of the "type" of an APSInt, used for conversions.

RangeSet getRangeSet(const llvm::APSInt &Origin)

RangeSet unite(RangeSet LHS, RangeSet RHS)

Create a new set which is a union of two given ranges.

RangeSet negate(RangeSet What)

Negate the given range set.

RangeSet intersect(RangeSet LHS, RangeSet RHS)

Intersect the given range sets.

RangeSet deletePoint(RangeSet From, const llvm::APSInt &Point)

Delete the given point from the range set.

Factory(BasicValueFactory &BV)

RangeSet getRangeSet(Range Origin)

Create a new set with just one range.

BasicValueFactory & getValueFactory() const

Return associated value factory.

RangeSet add(RangeSet LHS, RangeSet RHS)

Create a new set with all ranges from both LHS and RHS.

RangeSet castTo(RangeSet What, APSIntType Ty)

Performs promotions, truncations and conversions of the given set.

RangeSet getRangeSet(const llvm::APSInt &From, const llvm::APSInt &To)

persistent set of non-overlapping ranges.

const_iterator end() const

APSIntType getAPSIntType() const

const llvm::APSInt & getMaxValue() const

Get the maximal value covered by the ranges in the set.

RangeSet(const RangeSet &)=default

bool encodesTrueRange() const

Test if the range doesn't contain zero.

RangeSet & operator=(const RangeSet &)=default

RangeSet(Factory &F, const llvm::APSInt &Point)

Construct a new RangeSet representing the given point as a range.

bool encodesFalseRange() const

Test if the range is the [0,0] range.

const_iterator begin() const

const llvm::APSInt & getMinValue() const

Get the minimal value covered by the ranges in the set.

bool operator!=(const RangeSet &Other) const

ImplType::const_iterator const_iterator

RangeSet & operator=(RangeSet &&)=default

RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)

Construct a new RangeSet representing '{ [From, To] }'.

RangeSet(RangeSet &&)=default

static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS)

bool contains(llvm::APSInt Point) const

Test whether the given point is contained by any of the ranges.

bool containsZero() const

uint32_t getBitWidth() const

void Profile(llvm::FoldingSetNodeID &ID) const

Profile - Generates a hash profile of this RangeSet for use by FoldingSet.

bool operator==(const RangeSet &Other) const

const llvm::APSInt * getConcreteValue() const

getConcreteValue - If a symbol is constrained to equal a specific integer constant then this method r...

A Range represents the closed range [from, to].

const llvm::APSInt & From() const

Range(const llvm::APSInt &From, const llvm::APSInt &To)

bool operator!=(const Range &RHS) const

void Profile(llvm::FoldingSetNodeID &ID) const

Range(const llvm::APSInt &Point)

bool operator<(const Range &RHS) const

bool Includes(const llvm::APSInt &Point) const

const llvm::APSInt * getConcreteValue() const

bool operator==(const Range &RHS) const

const llvm::APSInt & To() const

virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0

~RangedConstraintManager() override

virtual ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0

virtual ProgramStateRef assumeSymWithinInclusiveRange(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment)=0

ProgramStateRef assumeSym(ProgramStateRef State, SymbolRef Sym, bool Assumption) override

Given a symbolic expression that can be reasoned about, assume that it is true/false and generate the...

virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, BinaryOperator::Opcode op, const llvm::APSInt &Int)

Assume a constraint between a symbolic expression and a concrete integer.

ProgramStateRef assumeSymUnsupported(ProgramStateRef State, SymbolRef Sym, bool Assumption) override

Given a symbolic expression that cannot be reasoned about, assume that it is zero/nonzero and add it ...

virtual ProgramStateRef assumeSymOutsideInclusiveRange(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, const llvm::APSInt &Adjustment)=0

virtual ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0

virtual ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0

ProgramStateRef assumeSymInclusiveRange(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, const llvm::APSInt &To, bool InRange) override

Given a symbolic expression within the range [From, To], assume that it is true/false and generate th...

virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0

RangedConstraintManager(ExprEngine *EE, SValBuilder &SB)

virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, const llvm::APSInt &Adjustment)=0

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

SVal simplifyToSVal(ProgramStateRef State, SymbolRef Sym)

Try to simplify a given symbolic expression's associated SVal based on the constraints in State.

llvm::ImmutableMap< SymbolRef, RangeSet > ConstraintMap

SymbolRef simplify(ProgramStateRef State, SymbolRef Sym)

Try to simplify a given symbolic expression based on the constraints in State.

@ OS

Indicates that the tracking object is a descendant of a referenced-counted OSObject,...

ConstraintMap getConstraintMap(ProgramStateRef State)

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

const FunctionProtoType * T

@ Other

Other implicit parameter.