RangeConstraintManager.cpp Source File (original) (raw)

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

21#include "llvm/ADT/ImmutableSet.h"

22#include "llvm/ADT/STLExtras.h"

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

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

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

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

27#include

28#include

29#include

31using namespace clang;

32using namespace ento;

37 static_assert(BO_LT < BO_GT && BO_GT < BO_LE && BO_LE < BO_GE &&

38 BO_GE < BO_EQ && BO_EQ < BO_NE,

39 "This class relies on operators order. Rework it otherwise.");

41public:

46 };

48private:

76 static constexpr size_t CmpOpCount = BO_NE - BO_LT + 1;

77 const TriStateKind CmpOpTable[CmpOpCount][CmpOpCount + 1] = {

85 };

88 return static_cast<size_t>(OP - BO_LT);

89 }

91public:

92 constexpr size_t getCmpOpCount() const { return CmpOpCount; }

96 }

100 return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];

101 }

102

104 return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];

105 }

106};

107

108

109

110

111

112RangeSet::ContainerType RangeSet::Factory::EmptySet{};

113

115 ContainerType Result;

118 std::back_inserter(Result));

119 return makePersistent(std::move(Result));

120}

121

123 ContainerType Result;

124 Result.reserve(Original.size() + 1);

125

126 const_iterator Lower = llvm::lower_bound(Original, Element);

127 Result.insert(Result.end(), Original.begin(), Lower);

128 Result.push_back(Element);

129 Result.insert(Result.end(), Lower, Original.end());

130

131 return makePersistent(std::move(Result));

132}

133

135 return add(Original, Range(Point));

136}

137

139 ContainerType Result = unite(*LHS.Impl, *RHS.Impl);

140 return makePersistent(std::move(Result));

141}

142

144 ContainerType Result;

147 return makePersistent(std::move(Result));

148}

149

151 return unite(Original, Range(ValueFactory.getValue(Point)));

152}

153

155 llvm::APSInt To) {

156 return unite(Original,

157 Range(ValueFactory.getValue(From), ValueFactory.getValue(To)));

158}

159

160template

162 std::swap(First, Second);

163 std::swap(FirstEnd, SecondEnd);

164}

165

167 const ContainerType &RHS) {

168 if (LHS.empty())

169 return RHS;

170 if (RHS.empty())

171 return LHS;

172

173 using llvm::APSInt;

174 using iterator = ContainerType::const_iterator;

175

176 iterator First = LHS.begin();

177 iterator FirstEnd = LHS.end();

178 iterator Second = RHS.begin();

179 iterator SecondEnd = RHS.end();

182

183

184

185

186

187 if (Min == First->From() && Min == Second->From()) {

188 if (First->To() > Second->To()) {

189

190

191

192

193

194

195 if (++Second == SecondEnd)

196

197

198

199

200 return LHS;

201 } else {

202

203

204

205

206

207

208

209 if (++First == FirstEnd)

210

211

212

213

214 return RHS;

215 }

216 }

217

219 ContainerType Result;

220

221

222

223

224 const auto AppendTheRest = [&Result](iterator I, iterator E) {

227 };

228

229 while (true) {

230

231

232

233 if (First->From() > Second->From())

235

236

237

238

239

240

241 const llvm::APSInt &UnionStart = First->From();

242

243

244 while (true) {

245

246

247

248 while (First->To() >= Second->To()) {

249

250 if (++Second == SecondEnd) {

251

252

253

254

255

256 Result.emplace_back(UnionStart, First->To());

257

258

259

260 return AppendTheRest(++First, FirstEnd);

261 }

262 }

263

264

265

266

267

268

269 if (First->To() < Second->From() - One)

270 break;

271

272

273

274

275

276

277 if (++First == FirstEnd) {

278

279

280

281

282

283 Result.emplace_back(UnionStart, Second->To());

284

285

286

287 return AppendTheRest(++Second, SecondEnd);

288 }

289

290

291

292

293

294

295

297 }

298

299

300

301

302

303

304

305 Result.emplace_back(UnionStart, First->To());

306

307

308 if (++First == FirstEnd)

309

310

311

312 return AppendTheRest(Second, SecondEnd);

313 }

314

315 llvm_unreachable("Normally, we should not reach here");

316}

317

319 ContainerType Result;

320 Result.push_back(From);

321 return makePersistent(std::move(Result));

322}

323

324RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) {

325 llvm::FoldingSetNodeID ID;

326 void *InsertPos;

327

328 From.Profile(ID);

329 ContainerType *Result = Cache.FindNodeOrInsertPos(ID, InsertPos);

330

332

333

334

335 Result = construct(std::move(From));

337 }

338

340}

341

342RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) {

343 void *Buffer = Arena.Allocate();

344 return new (Buffer) ContainerType(std::move(From));

345}

346

349 return begin()->From();

350}

351

354 return std::prev(end())->To();

355}

356

359 return begin()->From().isUnsigned();

360}

361

364 return begin()->From().getBitWidth();

365}

366

370}

371

372bool RangeSet::containsImpl(llvm::APSInt &Point) const {

373 if (isEmpty() || !pin(Point))

374 return false;

375

376 Range Dummy(Point);

378 if (It == begin())

379 return false;

380

381 return std::prev(It)->Includes(Point);

382}

383

384bool RangeSet::pin(llvm::APSInt &Point) const {

387 return false;

388

389 Type.apply(Point);

390 return true;

391}

392

393bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {

394

395

396

397

398

402

403 switch (LowerTest) {

405 switch (UpperTest) {

407

408

409 if (Lower <= Upper)

410 return false;

411

412

413 Lower = Type.getMinValue();

414 Upper = Type.getMaxValue();

415 break;

417

418 Lower = Type.getMinValue();

419 Type.apply(Upper);

420 break;

422

423 Lower = Type.getMinValue();

424 Upper = Type.getMaxValue();

425 break;

426 }

427 break;

429 switch (UpperTest) {

431

432 Type.apply(Lower);

433 Upper = Type.getMaxValue();

434 break;

436

437 Type.apply(Lower);

438 Type.apply(Upper);

439 break;

441

442 Type.apply(Lower);

443 Upper = Type.getMaxValue();

444 break;

445 }

446 break;

448 switch (UpperTest) {

450

451 return false;

453

454 Lower = Type.getMinValue();

455 Type.apply(Upper);

456 break;

458

459

460 if (Lower <= Upper)

461 return false;

462

463

464 Lower = Type.getMinValue();

465 Upper = Type.getMaxValue();

466 break;

467 }

468 break;

469 }

470

471 return true;

472}

473

475 llvm::APSInt Upper) {

476 if (What.isEmpty() || !What.pin(Lower, Upper))

477 return getEmptySet();

478

479 ContainerType DummyContainer;

480

481 if (Lower <= Upper) {

482

483

484

485

486

487

488

489

490

491

493 return getEmptySet();

494

495 DummyContainer.push_back(

496 Range(ValueFactory.getValue(Lower), ValueFactory.getValue(Upper)));

497 } else {

498

499

500

501

502

503

504

506 return getEmptySet();

507

508 DummyContainer.push_back(

509 Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper)));

510 DummyContainer.push_back(

511 Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower)));

512 }

513

514 return intersect(*What.Impl, DummyContainer);

515}

516

518 const RangeSet::ContainerType &RHS) {

519 ContainerType Result;

520 Result.reserve(std::max(LHS.size(), RHS.size()));

521

523 FirstEnd = LHS.end(), SecondEnd = RHS.end();

524

525

526

527

528 while (First != FirstEnd && Second != SecondEnd) {

529

530

531

532

533 if (Second->From() < First->From())

535

536

537 do {

538

539

540

541

542

543

544 if (Second->From() > First->To()) {

545

546

547

548

550 break;

551 }

552

553

554

555

556

557

558

559

560 const llvm::APSInt &IntersectionStart = Second->From();

561

562

563

564

565 if (Second->To() > First->To()) {

566

567

569 }

570

571

572

573

574

575

576

577

578

579

580

581

582 Result.push_back(Range(IntersectionStart, Second->To()));

583 ++Second;

584

585

586 } while (Second != SecondEnd);

587 }

588

590 return getEmptySet();

591

592 return makePersistent(std::move(Result));

593}

594

596

599 return getEmptySet();

600

601 return intersect(*LHS.Impl, *RHS.Impl);

602}

603

605 if (LHS.containsImpl(Point))

606 return getRangeSet(ValueFactory.getValue(Point));

607

608 return getEmptySet();

609}

610

613 return getEmptySet();

614

615 const llvm::APSInt SampleValue = What.getMinValue();

616 const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);

617 const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);

618

619 ContainerType Result;

620 Result.reserve(What.size() + (SampleValue == MIN));

621

622

625

626 const llvm::APSInt &From = It->From();

627 const llvm::APSInt &To = It->To();

628

629 if (From == MIN) {

630

631 if (To == MAX) {

632 return What;

633 }

634

636

637

638

639 if (Last->To() == MAX) {

640

641

642

643 Result.emplace_back(MIN, ValueFactory.getValue(-Last->From()));

644

646 } else {

647

648 Result.emplace_back(MIN, MIN);

649 }

650

651

652 if (To != MIN) {

653 Result.emplace_back(ValueFactory.getValue(-To), MAX);

654 }

655

656

657 ++It;

658 }

659

660

661 for (; It != End; ++It) {

662

663 const llvm::APSInt &NewFrom = ValueFactory.getValue(-It->To());

664 const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From());

665

666

667 Result.emplace_back(NewFrom, NewTo);

668 }

669

671 return makePersistent(std::move(Result));

672}

673

674

675

677

679 return What;

680

684

685 if (IsTruncation)

686 return makePersistent(truncateTo(What, Ty));

687

688

689

690

691

692

693

694

695

696

697

698

699

700 if (IsConversion && (!IsPromotion || !What.isUnsigned()))

701 return makePersistent(convertTo(What, Ty));

702

703 assert(IsPromotion && "Only promotion operation from unsigneds left.");

704 return makePersistent(promoteTo(What, Ty));

705}

706

710}

711

712RangeSet::ContainerType RangeSet::Factory::truncateTo(RangeSet What,

714 using llvm::APInt;

715 using llvm::APSInt;

716 ContainerType Result;

717 ContainerType Dummy;

718

719

720

721

722

723

724

725 uint64_t CastRangeSize = APInt::getMaxValue(Ty.getBitWidth()).getZExtValue();

726 for (const Range &R : What) {

727

728 APSInt FromInt = R.From();

729 APSInt ToInt = R.To();

730

731

732 uint64_t CurrentRangeSize = (ToInt - FromInt).getZExtValue();

733

734

735 Dummy.clear();

736 if (CurrentRangeSize >= CastRangeSize) {

737 Dummy.emplace_back(ValueFactory.getMinValue(Ty),

738 ValueFactory.getMaxValue(Ty));

739 Result = std::move(Dummy);

740 break;

741 }

742

743 Ty.apply(FromInt);

745 const APSInt &PersistentFrom = ValueFactory.getValue(FromInt);

746 const APSInt &PersistentTo = ValueFactory.getValue(ToInt);

747 if (FromInt > ToInt) {

748 Dummy.emplace_back(ValueFactory.getMinValue(Ty), PersistentTo);

749 Dummy.emplace_back(PersistentFrom, ValueFactory.getMaxValue(Ty));

750 } else

751 Dummy.emplace_back(PersistentFrom, PersistentTo);

752

753

755 }

756

758}

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778RangeSet::ContainerType RangeSet::Factory::convertTo(RangeSet What,

780 using llvm::APInt;

781 using llvm::APSInt;

782 using Bounds = std::pair<const APSInt &, const APSInt &>;

783 ContainerType AscendArray;

784 ContainerType DescendArray;

785 auto CastRange = [Ty, &VF = ValueFactory](const Range &R) -> Bounds {

786

787 APSInt FromInt = R.From();

788 APSInt ToInt = R.To();

789

790 Ty.apply(FromInt);

792 return {VF.getValue(FromInt), VF.getValue(ToInt)};

793 };

794

796 const auto *It = What.begin();

797 const auto *E = What.end();

798 while (It != E) {

799 Bounds NewBounds = CastRange(*(It++));

800

801 if (NewBounds.first < LastConvertedInt) {

802 DescendArray.emplace_back(NewBounds.first, NewBounds.second);

803 break;

804 }

805

806

807

808

809 if (NewBounds.first > NewBounds.second) {

810 DescendArray.emplace_back(ValueFactory.getMinValue(Ty), NewBounds.second);

811 AscendArray.emplace_back(NewBounds.first, ValueFactory.getMaxValue(Ty));

812 } else

813

814 AscendArray.emplace_back(NewBounds.first, NewBounds.second);

815 LastConvertedInt = NewBounds.first;

816 }

817

818 while (It != E) {

819 Bounds NewBounds = CastRange(*(It++));

820 DescendArray.emplace_back(NewBounds.first, NewBounds.second);

821 }

822

823 return unite(AscendArray, DescendArray);

824}

825

826

827RangeSet::ContainerType RangeSet::Factory::promoteTo(RangeSet What,

829 ContainerType Result;

830

832

833

834

835

836 for (const Range &R : What) {

837

838 llvm::APSInt FromInt = R.From();

839 llvm::APSInt ToInt = R.To();

840

841 Ty.apply(FromInt);

843 Result.emplace_back(ValueFactory.getValue(FromInt),

844 ValueFactory.getValue(ToInt));

845 }

847}

848

850 const llvm::APSInt &Point) {

852 return From;

853

854 llvm::APSInt Upper = Point;

855 llvm::APSInt Lower = Point;

856

857 ++Upper;

858 --Lower;

859

860

861 return intersect(From, Upper, Lower);

862}

863

865 OS << '[' << toString(From(), 10) << ", " << toString(To(), 10) << ']';

866}

868

870 OS << "{ ";

871 llvm::interleaveComma(*this, OS, [&OS](const Range &R) { R.dump(OS); });

872 OS << " }";

873}

875

877

878namespace {

879class EquivalenceClass;

880}

881

885

888

889namespace {

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914class EquivalenceClass : public llvm::FoldingSetNode {

915public:

916

917 [[nodiscard]] static inline EquivalenceClass find(ProgramStateRef State,

919

920

925

928

929

931

932

933

934

935

936

937

938

939

940

941

942

944

945

946 [[nodiscard]] inline bool isTriviallyDead(ProgramStateRef State,

948

954 EquivalenceClass First, EquivalenceClass Second);

957 EquivalenceClass Other) const;

958 [[nodiscard]] static inline ClassSet getDisequalClasses(ProgramStateRef State,

960 [[nodiscard]] inline ClassSet getDisequalClasses(ProgramStateRef State) const;

961 [[nodiscard]] inline ClassSet

962 getDisequalClasses(DisequalityMapTy Map, ClassSet::Factory &Factory) const;

963

964 [[nodiscard]] static inline std::optional

966 EquivalenceClass Second);

967 [[nodiscard]] static inline std::optional

969

970

973

974

978 EquivalenceClass Class);

979

980 void dumpToStream(ProgramStateRef State, raw_ostream &os) const;

982 dumpToStream(State, llvm::errs());

983 }

984

985

986 [[nodiscard]] LLVM_ATTRIBUTE_UNUSED static bool

988

989 [[nodiscard]] QualType getType() const {

990 return getRepresentativeSymbol()->getType();

991 }

992

993 EquivalenceClass() = delete;

994 EquivalenceClass(const EquivalenceClass &) = default;

995 EquivalenceClass &operator=(const EquivalenceClass &) = delete;

996 EquivalenceClass(EquivalenceClass &&) = default;

997 EquivalenceClass &operator=(EquivalenceClass &&) = delete;

998

1001 }

1005 }

1006

1007 static void Profile(llvm::FoldingSetNodeID &ID, uintptr_t CID) {

1008 ID.AddInteger(CID);

1009 }

1010

1011 void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, this->ID); }

1012

1013private:

1014 EquivalenceClass(SymbolRef Sym)

1015 : ID(reinterpret_cast<uintptr_t>(Sym)) {}

1016

1017

1018

1019

1020

1021

1022 SymbolRef getRepresentativeSymbol() const {

1024 }

1025 static inline SymbolSet::Factory &getMembersFactory(ProgramStateRef State);

1026

1030

1031 static inline bool

1032 addToDisequalityInfo(DisequalityMapTy &Info, ConstraintRangeTy &Constraints,

1034 EquivalenceClass First, EquivalenceClass Second);

1035

1036

1038};

1039

1040

1041

1042

1043

1044[[nodiscard]] LLVM_ATTRIBUTE_UNUSED bool

1045areFeasible(ConstraintRangeTy Constraints) {

1046 return llvm::none_of(

1047 Constraints,

1048 [](const std::pair<EquivalenceClass, RangeSet> &ClassConstraint) {

1049 return ClassConstraint.second.isEmpty();

1050 });

1051}

1052

1054 EquivalenceClass Class) {

1055 return State->get(Class);

1056}

1057

1060 return getConstraint(State, EquivalenceClass::find(State, Sym));

1061}

1062

1064 EquivalenceClass Class,

1066 return State->set(Class, Constraint);

1067}

1068

1070 ConstraintRangeTy Constraints) {

1071 return State->set(Constraints);

1072}

1073

1074

1075

1076

1077

1078

1079

1080

1081

1082

1083

1084

1085

1086

1087std::optional meansEquality(const SymSymExpr *Sym) {

1089 case BO_Sub:

1090

1091 return false;

1092 case BO_EQ:

1093

1094 return true;

1095 case BO_NE:

1096

1097 return false;

1098 default:

1099 return std::nullopt;

1100 }

1101}

1102

1103

1104

1105

1106

1107template <class SecondTy, class... RestTy>

1109 SecondTy Second, RestTy... Tail);

1110

1111template <class... RangeTy> struct IntersectionTraits;

1112

1113template <class... TailTy> struct IntersectionTraits<RangeSet, TailTy...> {

1114

1116};

1117

1118template <> struct IntersectionTraits<> {

1119

1120

1121 using Type = std::optional;

1122};

1123

1124template <class OptionalOrPointer, class... TailTy>

1125struct IntersectionTraits<OptionalOrPointer, TailTy...> {

1126

1127 using Type = typename IntersectionTraits<TailTy...>::Type;

1128};

1129

1130template

1131[[nodiscard]] inline EndTy intersect(RangeSet::Factory &F, EndTy End) {

1132

1133

1134 return End;

1135}

1136

1137[[nodiscard]] LLVM_ATTRIBUTE_UNUSED inline std::optional

1139

1140

1141 if (End) {

1142 return *End;

1143 }

1144 return std::nullopt;

1145}

1146

1147template <class... RestTy>

1149 RangeSet Second, RestTy... Tail) {

1150

1151

1152 return intersect(F, F.intersect(Head, Second), Tail...);

1153}

1154

1155template <class SecondTy, class... RestTy>

1157 SecondTy Second, RestTy... Tail) {

1158 if (Second) {

1159

1160 return intersect(F, Head, *Second, Tail...);

1161 }

1162

1163

1164 return intersect(F, Head, Tail...);

1165}

1166

1167

1168

1169

1170

1171

1172

1173

1174

1175

1176

1177

1178

1179

1180

1181

1182

1183

1184

1185

1186

1187

1188template <class HeadTy, class SecondTy, class... RestTy>

1189[[nodiscard]] inline

1190 typename IntersectionTraits<HeadTy, SecondTy, RestTy...>::Type

1192 RestTy... Tail) {

1193 if (Head) {

1194 return intersect(F, *Head, Second, Tail...);

1195 }

1196 return intersect(F, Second, Tail...);

1197}

1198

1199

1200

1201

1202

1203

1204

1205

1206

1207

1208class SymbolicRangeInferrer

1209 : public SymExprVisitor<SymbolicRangeInferrer, RangeSet> {

1210public:

1211 template

1213 SourceType Origin) {

1214 SymbolicRangeInferrer Inferrer(F, State);

1215 return Inferrer.infer(Origin);

1216 }

1217

1219 if (std::optional RS = getRangeForNegatedSym(Sym))

1220 return *RS;

1221

1222

1223

1224

1225 return infer(Sym->getType());

1226 }

1227

1229 if (std::optional RS = getRangeForNegatedUnarySym(USE))

1230 return *RS;

1231 return infer(USE->getType());

1232 }

1233

1235 return VisitBinaryOperator(Sym);

1236 }

1237

1239 return VisitBinaryOperator(Sym);

1240 }

1241

1243 return intersect(

1244 RangeFactory,

1245

1246

1247

1248

1249

1250

1251 getRangeForNegatedSymSym(SSE),

1252

1253 getRangeCommutativeSymSym(SSE),

1254

1255

1256

1257 getRangeForComparisonSymbol(SSE),

1258

1259

1260 getRangeForEqualities(SSE),

1261

1262 VisitBinaryOperator(SSE));

1263 }

1264

1265private:

1267 : ValueFactory(F.getValueFactory()), RangeFactory(F), State(S) {}

1268

1269

1270

1271

1272

1274 return {RangeFactory, Val};

1275 }

1276

1277

1280

1283 return infer(Sym);

1284 }

1285

1286

1287 return infer(DestType);

1288 }

1289

1291 return intersect(RangeFactory,

1292

1293

1294 getConstraint(State, Sym),

1295

1296

1297 Visit(Sym));

1298 }

1299

1300 RangeSet infer(EquivalenceClass Class) {

1301 if (const RangeSet *AssociatedConstraint = getConstraint(State, Class))

1302 return *AssociatedConstraint;

1303

1304 return infer(Class.getType());

1305 }

1306

1307

1309

1310

1311 RangeSet Result(RangeFactory, ValueFactory.getMinValue(T),

1312 ValueFactory.getMaxValue(T));

1313

1314

1316 return assumeNonZero(Result, T);

1317

1318 return Result;

1319 }

1320

1321 template

1322 RangeSet VisitBinaryOperator(const BinarySymExprTy *Sym) {

1323

1324

1325

1326

1327

1328

1329

1330

1331

1332

1333

1334 QualType ResultType = Sym->getType();

1335 return VisitBinaryOperator(inferAs(Sym->getLHS(), ResultType),

1336 Sym->getOpcode(),

1337 inferAs(Sym->getRHS(), ResultType), ResultType);

1338 }

1339

1342

1343

1344

1345

1346

1347

1348

1349

1350

1351

1353 assert(!Origin.isEmpty());

1355 }

1356

1357

1358

1359

1360 std::optional convert(const Range &Origin, APSIntType To) {

1363 return std::nullopt;

1364 }

1365 return Range(ValueFactory.Convert(To, Origin.From()),

1366 ValueFactory.Convert(To, Origin.To()));

1367 }

1368

1369 template <BinaryOperator::Opcode Op>

1372

1373 Range CoarseLHS = fillGaps(LHS);

1374 Range CoarseRHS = fillGaps(RHS);

1375

1376 APSIntType ResultType = ValueFactory.getAPSIntType(T);

1377

1378

1379

1380 auto ConvertedCoarseLHS = convert(CoarseLHS, ResultType);

1381 auto ConvertedCoarseRHS = convert(CoarseRHS, ResultType);

1382

1383

1384

1385 if (!ConvertedCoarseLHS || !ConvertedCoarseRHS) {

1386 return infer(T);

1387 }

1388

1389 return VisitBinaryOperator(*ConvertedCoarseLHS, *ConvertedCoarseRHS, T);

1390 }

1391

1392 template <BinaryOperator::Opcode Op>

1394 return infer(T);

1395 }

1396

1397

1398

1399

1400

1401

1402

1403

1404

1406 APSIntType RangeType = ValueFactory.getAPSIntType(T);

1407

1409 return Range(ValueFactory.getMinValue(RangeType), Origin.To());

1410 }

1411

1412 if (Origin.From().isMinSignedValue()) {

1413

1414

1415

1416 return {ValueFactory.getMinValue(RangeType),

1417 ValueFactory.getMaxValue(RangeType)};

1418 }

1419

1420

1421

1422

1423

1424

1425

1426

1427

1428

1429

1430

1431 llvm::APSInt AbsMax = std::max(-Origin.From(), Origin.To());

1432

1433

1434 return {ValueFactory.getValue(-AbsMax), ValueFactory.getValue(AbsMax)};

1435 }

1436

1437

1439 APSIntType IntType = ValueFactory.getAPSIntType(T);

1441 }

1442

1443 template

1444 std::optional getRangeForNegatedExpr(ProduceNegatedSymFunc F,

1446

1449 return std::nullopt;

1450

1452 if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym))

1453 return RangeFactory.negate(*NegatedRange);

1454

1455 return std::nullopt;

1456 }

1457

1458 std::optional getRangeForNegatedUnarySym(const UnarySymExpr *USE) {

1459

1460

1461 return getRangeForNegatedExpr(

1463 if (USE->getOpcode() == UO_Minus)

1465 return nullptr;

1466 },

1468 }

1469

1470 std::optional getRangeForNegatedSymSym(const SymSymExpr *SSE) {

1471 return getRangeForNegatedExpr(

1472 [SSE, State = this->State]() -> SymbolRef {

1474 return State->getSymbolManager().acquire<SymSymExpr>(

1476 return nullptr;

1477 },

1479 }

1480

1481 std::optional getRangeForNegatedSym(SymbolRef Sym) {

1482 return getRangeForNegatedExpr(

1483 [Sym, State = this->State]() {

1484 return State->getSymbolManager().acquire(

1485 Sym, UO_Minus, Sym->getType());

1486 },

1488 }

1489

1490 std::optional getRangeCommutativeSymSym(const SymSymExpr *SSE) {

1492 bool IsCommutative = llvm::is_contained(

1493

1494 {BO_EQ, BO_NE, BO_Or, BO_And, BO_Add, BO_Mul, BO_Xor}, Op);

1495 if (!IsCommutative)

1496 return std::nullopt;

1497

1500 if (const RangeSet *Range = getConstraint(State, Commuted))

1502 return std::nullopt;

1503 }

1504

1505

1506

1507

1508

1509

1510

1511

1512

1513

1514

1515 std::optional getRangeForComparisonSymbol(const SymSymExpr *SSE) {

1517

1518

1520 return std::nullopt;

1521

1523

1527

1528 SymbolManager &SymMgr = State->getSymbolManager();

1529

1530

1531

1532

1533

1534

1536

1537

1538

1539 for (size_t i = 0; i < CmpOpTable.getCmpOpCount(); ++i) {

1540

1541

1545 const RangeSet *QueriedRangeSet = getConstraint(State, SymSym);

1546

1547

1548

1549 if (!QueriedRangeSet) {

1553 QueriedRangeSet = getConstraint(State, SymSym);

1554 }

1555

1556 if (!QueriedRangeSet || QueriedRangeSet->isEmpty())

1557 continue;

1558

1559 const llvm::APSInt *ConcreteValue = QueriedRangeSet->getConcreteValue();

1560 const bool isInFalseBranch =

1561 ConcreteValue ? (*ConcreteValue == 0) : false;

1562

1563

1564

1565

1566 if (isInFalseBranch)

1568

1570 CmpOpTable.getCmpOpState(CurrentOP, QueriedOP);

1571

1573 if (LastQueriedOpToUnknown != CurrentOP &&

1574 LastQueriedOpToUnknown != QueriedOP) {

1575

1576

1577

1578

1579

1580 BranchState = CmpOpTable.getCmpOpStateForUnknownX2(CurrentOP);

1581 } else {

1582 LastQueriedOpToUnknown = QueriedOP;

1583 continue;

1584 }

1585 }

1586

1588 : getFalseRange(T);

1589 }

1590

1591 return std::nullopt;

1592 }

1593

1594 std::optional getRangeForEqualities(const SymSymExpr *Sym) {

1595 std::optional Equality = meansEquality(Sym);

1596

1597 if (!Equality)

1598 return std::nullopt;

1599

1600 if (std::optional AreEqual =

1601 EquivalenceClass::areEqual(State, Sym->getLHS(), Sym->getRHS())) {

1602

1603

1604

1605 if (*AreEqual == *Equality) {

1606 return getTrueRange(Sym->getType());

1607 }

1608

1609 return getFalseRange(Sym->getType());

1610 }

1611

1612 return std::nullopt;

1613 }

1614

1617 return assumeNonZero(TypeRange, T);

1618 }

1619

1621 const llvm::APSInt &Zero = ValueFactory.getValue(0, T);

1622 return RangeSet(RangeFactory, Zero);

1623 }

1624

1628};

1629

1630

1631

1632

1633

1634template <>

1635RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_NE>(RangeSet LHS,

1639

1641 if (intersect(RangeFactory, LHS, RHS).isEmpty())

1642 return getTrueRange(T);

1643

1644 } else {

1645

1646

1647

1648

1649

1650

1651

1652

1653

1654

1655

1656

1661 return getTrueRange(T);

1662

1666 return getTrueRange(T);

1667 }

1668 }

1669

1670

1673

1674 RangeSet CastedLHS = RangeFactory.castTo(LHS, CastingType);

1675 RangeSet CastedRHS = RangeFactory.castTo(RHS, CastingType);

1676

1677 if (intersect(RangeFactory, CastedLHS, CastedRHS).isEmpty())

1678 return getTrueRange(T);

1679 }

1680

1681

1682 return infer(T);

1683}

1684

1685template <>

1686RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Or>(Range LHS, Range RHS,

1688 APSIntType ResultType = ValueFactory.getAPSIntType(T);

1690

1691 bool IsLHSPositiveOrZero = LHS.From() >= Zero;

1692 bool IsRHSPositiveOrZero = RHS.From() >= Zero;

1693

1694 bool IsLHSNegative = LHS.To() < Zero;

1695 bool IsRHSNegative = RHS.To() < Zero;

1696

1697

1698 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||

1699 (IsLHSNegative && IsRHSNegative)) {

1700

1701 const llvm::APSInt &Min = std::max(LHS.From(), RHS.From());

1702

1703

1704

1705

1706

1707

1708

1709

1710

1711

1712

1713

1714 const llvm::APSInt &Max = IsLHSNegative

1715 ? ValueFactory.getValue(--Zero)

1716 : ValueFactory.getMaxValue(ResultType);

1717

1718 return {RangeFactory, ValueFactory.getValue(Min), Max};

1719 }

1720

1721

1722 if (IsLHSNegative || IsRHSNegative) {

1723

1724 return {RangeFactory, ValueFactory.getMinValue(ResultType),

1725 ValueFactory.getValue(--Zero)};

1726 }

1727

1728 RangeSet DefaultRange = infer(T);

1729

1730

1731

1732

1733

1735 return assumeNonZero(DefaultRange, T);

1736 }

1737

1738

1739 return DefaultRange;

1740}

1741

1742template <>

1743RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_And>(Range LHS,

1746 APSIntType ResultType = ValueFactory.getAPSIntType(T);

1748

1749 bool IsLHSPositiveOrZero = LHS.From() >= Zero;

1750 bool IsRHSPositiveOrZero = RHS.From() >= Zero;

1751

1752 bool IsLHSNegative = LHS.To() < Zero;

1753 bool IsRHSNegative = RHS.To() < Zero;

1754

1755

1756 if ((IsLHSPositiveOrZero && IsRHSPositiveOrZero) ||

1757 (IsLHSNegative && IsRHSNegative)) {

1758

1759 const llvm::APSInt &Max = std::min(LHS.To(), RHS.To());

1760

1761

1762

1763 const llvm::APSInt &Min = IsLHSNegative

1764 ? ValueFactory.getMinValue(ResultType)

1765 : ValueFactory.getValue(Zero);

1766

1767 return {RangeFactory, Min, Max};

1768 }

1769

1770

1771 if (IsLHSPositiveOrZero || IsRHSPositiveOrZero) {

1772

1773

1774

1775

1776 const llvm::APSInt &Max = IsLHSPositiveOrZero ? LHS.To() : RHS.To();

1777

1778

1779

1780 return {RangeFactory, ValueFactory.getValue(Zero),

1781 ValueFactory.getValue(Max)};

1782 }

1783

1784

1785 return infer(T);

1786}

1787

1788template <>

1789RangeSet SymbolicRangeInferrer::VisitBinaryOperator<BO_Rem>(Range LHS,

1792 llvm::APSInt Zero = ValueFactory.getAPSIntType(T).getZeroValue();

1793

1794 Range ConservativeRange = getSymmetricalRange(RHS, T);

1795

1796 llvm::APSInt Max = ConservativeRange.To();

1797 llvm::APSInt Min = ConservativeRange.From();

1798

1799 if (Max == Zero) {

1800

1801

1802

1803 return RangeFactory.getEmptySet();

1804 }

1805

1806

1807

1808

1809

1810

1811

1812

1813

1814

1815

1816 if (Min.isSigned()) {

1818 }

1820

1821 bool IsLHSPositiveOrZero = LHS.From() >= Zero;

1822 bool IsRHSPositiveOrZero = RHS.From() >= Zero;

1823

1824

1825

1826 if (IsLHSPositiveOrZero && IsRHSPositiveOrZero) {

1827

1828

1829 Max = std::min(LHS.To(), Max);

1830

1831

1832

1833

1834

1835

1836

1838 }

1839

1840

1841

1842 return {RangeFactory, ValueFactory.getValue(Min), ValueFactory.getValue(Max)};

1843}

1844

1845RangeSet SymbolicRangeInferrer::VisitBinaryOperator(RangeSet LHS,

1848

1849

1851 return RangeFactory.getEmptySet();

1852 }

1853

1854 switch (Op) {

1855 case BO_NE:

1856 return VisitBinaryOperator<BO_NE>(LHS, RHS, T);

1857 case BO_Or:

1858 return VisitBinaryOperator<BO_Or>(LHS, RHS, T);

1859 case BO_And:

1860 return VisitBinaryOperator<BO_And>(LHS, RHS, T);

1861 case BO_Rem:

1862 return VisitBinaryOperator<BO_Rem>(LHS, RHS, T);

1863 default:

1864 return infer(T);

1865 }

1866}

1867

1868

1869

1870

1871

1873public:

1876

1877

1878

1879

1880

1883

1884

1885

1886 return S1->get() == S2->get() &&

1887 S1->get() == S2->get();

1888 }

1889

1890 bool canReasonAbout(SVal X) const override;

1891

1893

1896

1899

1902

1905

1906 void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",

1907 unsigned int Space = 0, bool IsDot = false) const override;

1908 void printValue(raw_ostream &Out, ProgramStateRef State,

1910 void printConstraints(raw_ostream &Out, ProgramStateRef State,

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

1912 bool IsDot = false) const;

1913 void printEquivalenceClasses(raw_ostream &Out, ProgramStateRef State,

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

1915 bool IsDot = false) const;

1916 void printDisequalities(raw_ostream &Out, ProgramStateRef State,

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

1918 bool IsDot = false) const;

1919

1920

1921

1922

1923

1925 const llvm::APSInt &V,

1926 const llvm::APSInt &Adjustment) override;

1927

1929 const llvm::APSInt &V,

1930 const llvm::APSInt &Adjustment) override;

1931

1933 const llvm::APSInt &V,

1934 const llvm::APSInt &Adjustment) override;

1935

1937 const llvm::APSInt &V,

1938 const llvm::APSInt &Adjustment) override;

1939

1941 const llvm::APSInt &V,

1942 const llvm::APSInt &Adjustment) override;

1943

1945 const llvm::APSInt &V,

1946 const llvm::APSInt &Adjustment) override;

1947

1950 const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;

1951

1954 const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;

1955

1956private:

1958

1962

1964 const llvm::APSInt &Int,

1965 const llvm::APSInt &Adjustment) const;

1967 const llvm::APSInt &Int,

1968 const llvm::APSInt &Adjustment) const;

1970 const llvm::APSInt &Int,

1971 const llvm::APSInt &Adjustment) const;

1973 const llvm::APSInt &Int,

1974 const llvm::APSInt &Adjustment) const;

1976 const llvm::APSInt &Int,

1977 const llvm::APSInt &Adjustment) const;

1978};

1979

1980

1981

1982

1983

1984

1985

1986

1987

1988

1989

1990

1991

1992

1993

1994

1995

1996

1997

1998template class ConstraintAssignorBase {

1999public:

2000 using Const = const llvm::APSInt &;

2001

2002#define DISPATCH(CLASS) return assign##CLASS##Impl(cast(Sym), Constraint)

2003

2004#define ASSIGN(CLASS, TO, SYM, CONSTRAINT) \

2005 if (!static_cast<Derived *>(this)->assign##CLASS##To##TO(SYM, CONSTRAINT)) \

2006 return false

2007

2009 assignImpl(Sym, Constraint);

2010 }

2011

2013 switch (Sym->getKind()) {

2014#define SYMBOL(Id, Parent) \

2015 case SymExpr::Id##Kind: \

2016 DISPATCH(Id);

2017#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"

2018 }

2019 llvm_unreachable("Unknown SymExpr kind!");

2020 }

2021

2022#define DEFAULT_ASSIGN(Id) \

2023 bool assign##Id##To##RangeSet(const Id *Sym, RangeSet Constraint) { \

2024 return true; \

2025 } \

2026 bool assign##Id##To##Range(const Id *Sym, Range Constraint) { return true; } \

2027 bool assign##Id##To##Const(const Id *Sym, Const Constraint) { return true; }

2028

2029

2030

2031

2032

2033#define CONSTRAINT_DISPATCH(Id) \

2034 if (const llvm::APSInt *Const = Constraint.getConcreteValue()) { \

2035 ASSIGN(Id, Const, Sym, *Const); \

2036 } \

2037 if (Constraint.size() == 1) { \

2038 ASSIGN(Id, Range, Sym, *Constraint.begin()); \

2039 } \

2040 ASSIGN(Id, RangeSet, Sym, Constraint)

2041

2042

2043

2044

2045#define SYMBOL(Id, Parent) \

2046 bool assign##Id##Impl(const Id *Sym, RangeSet Constraint) { \

2047 CONSTRAINT_DISPATCH(Id); \

2048 DISPATCH(Parent); \

2049 } \

2050 DEFAULT_ASSIGN(Id)

2051#define ABSTRACT_SYMBOL(Id, Parent) SYMBOL(Id, Parent)

2052#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"

2053

2054

2055 bool assignSymExprImpl(const SymExpr *Sym, RangeSet Constraint) {

2057 return true;

2058 }

2060

2061#undef DISPATCH

2062#undef CONSTRAINT_DISPATCH

2063#undef DEFAULT_ASSIGN

2064#undef ASSIGN

2065};

2066

2067

2068

2069

2070

2071

2072

2073

2074

2075

2076

2077

2078class ConstraintAssignor : public ConstraintAssignorBase {

2079public:

2080 template

2083 ClassOrSymbol CoS, RangeSet NewConstraint) {

2084 if (!State || NewConstraint.isEmpty())

2085 return nullptr;

2086

2087 ConstraintAssignor Assignor{State, Builder, F};

2088 return Assignor.assign(CoS, NewConstraint);

2089 }

2090

2091

2092 template

2093 bool handleRemainderOp(const SymT *Sym, RangeSet Constraint) {

2094 if (Sym->getOpcode() != BO_Rem)

2095 return true;

2096

2098 SVal SymSVal = Builder.makeSymbolVal(Sym->getLHS());

2100 State = State->assume(*NonLocSymSVal, true);

2101 if (!State)

2102 return false;

2103 }

2104 }

2105 return true;

2106 }

2107

2108 inline bool assignSymExprToConst(const SymExpr *Sym, Const Constraint);

2109 inline bool assignSymIntExprToRangeSet(const SymIntExpr *Sym,

2111 return handleRemainderOp(Sym, Constraint);

2112 }

2113 inline bool assignSymSymExprToRangeSet(const SymSymExpr *Sym,

2115

2116private:

2119 : State(State), Builder(Builder), RangeFactory(F) {}

2120 using Base = ConstraintAssignorBase;

2121

2122

2124

2125

2126 State = assign(EquivalenceClass::find(State, Sym), NewConstraint);

2127 if (!State)

2128 return nullptr;

2129

2130

2131

2132 Base::assign(Sym, NewConstraint);

2133 return State;

2134 }

2135

2136

2137 [[nodiscard]] ProgramStateRef assign(EquivalenceClass Class,

2139

2140

2141

2142

2143

2144 if (const llvm::APSInt *Point = NewConstraint.getConcreteValue()) {

2145

2146 ConstraintRangeTy Constraints = State->get();

2147 ConstraintRangeTy::Factory &CF = State->get_context();

2148

2149

2150 Constraints = CF.add(Constraints, Class, NewConstraint);

2151

2152 for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) {

2153 RangeSet UpdatedConstraint = SymbolicRangeInferrer::inferRange(

2154 RangeFactory, State, DisequalClass);

2155

2156 UpdatedConstraint = RangeFactory.deletePoint(UpdatedConstraint, *Point);

2157

2158

2159

2160 if (UpdatedConstraint.isEmpty())

2161 return nullptr;

2162

2163 Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint);

2164 }

2165 assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "

2166 "a state with infeasible constraints");

2167

2168 return setConstraints(State, Constraints);

2169 }

2170

2171 return setConstraint(State, Class, NewConstraint);

2172 }

2173

2176 return EquivalenceClass::markDisequal(RangeFactory, State, LHS, RHS);

2177 }

2178

2181 return EquivalenceClass::merge(RangeFactory, State, LHS, RHS);

2182 }

2183

2184 [[nodiscard]] std::optional interpreteAsBool(RangeSet Constraint) {

2185 assert(!Constraint.isEmpty() && "Empty ranges shouldn't get here");

2186

2189

2191 return true;

2192

2193 return std::nullopt;

2194 }

2195

2199};

2200

2201bool ConstraintAssignor::assignSymExprToConst(const SymExpr *Sym,

2202 const llvm::APSInt &Constraint) {

2203 llvm::SmallSet<EquivalenceClass, 4> SimplifiedClasses;

2204

2205 ClassMembersTy Members = State->get();

2206 for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members) {

2207 EquivalenceClass Class = ClassToSymbolSet.first;

2208 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);

2209 if (!State)

2210 return false;

2211 SimplifiedClasses.insert(Class);

2212 }

2213

2214

2215

2216

2217 ConstraintRangeTy Constraints = State->get();

2218 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {

2219 EquivalenceClass Class = ClassConstraint.first;

2220 if (SimplifiedClasses.count(Class))

2221 continue;

2222 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);

2223 if (!State)

2224 return false;

2225 }

2226

2227

2228

2229 DisequalityMapTy DisequalityInfo = State->get();

2230 for (std::pair<EquivalenceClass, ClassSet> DisequalityEntry :

2231 DisequalityInfo) {

2232 EquivalenceClass Class = DisequalityEntry.first;

2233 ClassSet DisequalClasses = DisequalityEntry.second;

2234 State = EquivalenceClass::simplify(Builder, RangeFactory, State, Class);

2235 if (!State)

2236 return false;

2237 }

2238

2239 return true;

2240}

2241

2242bool ConstraintAssignor::assignSymSymExprToRangeSet(const SymSymExpr *Sym,

2244 if (!handleRemainderOp(Sym, Constraint))

2245 return false;

2246

2247 std::optional ConstraintAsBool = interpreteAsBool(Constraint);

2248

2249 if (!ConstraintAsBool)

2250 return true;

2251

2252 if (std::optional Equality = meansEquality(Sym)) {

2253

2254

2255

2256

2257

2258 if (*Equality == *ConstraintAsBool) {

2259 State = trackEquality(State, Sym->getLHS(), Sym->getRHS());

2260 } else {

2261

2262 State = trackDisequality(State, Sym->getLHS(), Sym->getRHS());

2263 }

2264

2265 if (!State)

2266 return false;

2267 }

2268

2269 return true;

2270}

2271

2272}

2273

2274std::unique_ptr

2277 return std::make_unique(Eng, StMgr.getSValBuilder());

2278}

2279

2281 ConstraintMap::Factory &F = State->get_context<ConstraintMap>();

2283

2284 ConstraintRangeTy Constraints = State->get();

2285 for (std::pair<EquivalenceClass, RangeSet> ClassConstraint : Constraints) {

2286 EquivalenceClass Class = ClassConstraint.first;

2287 SymbolSet ClassMembers = Class.getClassMembers(State);

2288 assert(!ClassMembers.isEmpty() &&

2289 "Class must always have at least one member!");

2290

2291 SymbolRef Representative = *ClassMembers.begin();

2292 Result = F.add(Result, Representative, ClassConstraint.second);

2293 }

2294

2296}

2297

2298

2299

2300

2301

2302LLVM_DUMP_METHOD void EquivalenceClass::dumpToStream(ProgramStateRef State,

2303 raw_ostream &os) const {

2304 SymbolSet ClassMembers = getClassMembers(State);

2305 for (const SymbolRef &MemberSym : ClassMembers) {

2306 MemberSym->dump();

2307 os << "\n";

2308 }

2309}

2310

2311inline EquivalenceClass EquivalenceClass::find(ProgramStateRef State,

2313 assert(State && "State should not be null");

2314 assert(Sym && "Symbol should not be null");

2315

2316 if (const EquivalenceClass *NontrivialClass = State->get(Sym))

2317 return *NontrivialClass;

2318

2319

2320 return Sym;

2321}

2322

2327 EquivalenceClass FirstClass = find(State, First);

2328 EquivalenceClass SecondClass = find(State, Second);

2329

2330 return FirstClass.merge(F, State, SecondClass);

2331}

2332

2335 EquivalenceClass Other) {

2336

2337 if (*this == Other)

2338 return State;

2339

2340

2341

2342

2343

2344

2345

2346

2347

2348

2349

2350

2351 if (getType()->getCanonicalTypeUnqualified() !=

2352 Other.getType()->getCanonicalTypeUnqualified())

2353 return State;

2354

2355 SymbolSet Members = getClassMembers(State);

2356 SymbolSet OtherMembers = Other.getClassMembers(State);

2357

2358

2359

2360

2361 if (Members.getHeight() >= OtherMembers.getHeight()) {

2362 return mergeImpl(F, State, Members, Other, OtherMembers);

2363 } else {

2364 return Other.mergeImpl(F, State, OtherMembers, *this, Members);

2365 }

2366}

2367

2372

2373

2374

2375

2376

2377

2378

2379

2380

2381

2382

2383 ConstraintRangeTy Constraints = State->get();

2384 ConstraintRangeTy::Factory &CRF = State->get_context();

2385

2386

2387

2388

2389

2390

2391 if (std::optional NewClassConstraint =

2392 intersect(RangeFactory, getConstraint(State, *this),

2393 getConstraint(State, Other))) {

2394

2395

2396

2397

2398

2399 if (NewClassConstraint->isEmpty())

2400

2401 return nullptr;

2402

2403

2404 Constraints = CRF.remove(Constraints, Other);

2405

2406 Constraints = CRF.add(Constraints, *this, *NewClassConstraint);

2407

2408 assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "

2409 "a state with infeasible constraints");

2410

2411 State = State->set(Constraints);

2412 }

2413

2414

2415 ClassMapTy Classes = State->get();

2416 ClassMapTy::Factory &CMF = State->get_context();

2417

2418 ClassMembersTy Members = State->get();

2419 ClassMembersTy::Factory &MF = State->get_context();

2420

2421 DisequalityMapTy DisequalityInfo = State->get();

2422 DisequalityMapTy::Factory &DF = State->get_context();

2423

2424 ClassSet::Factory &CF = State->get_context();

2425 SymbolSet::Factory &F = getMembersFactory(State);

2426

2427

2428 SymbolSet NewClassMembers = MyMembers;

2429 for (SymbolRef Sym : OtherMembers) {

2430 NewClassMembers = F.add(NewClassMembers, Sym);

2431

2432 Classes = CMF.add(Classes, Sym, *this);

2433 }

2434

2435

2436

2437

2438 Members = MF.remove(Members, Other);

2439

2440 Members = MF.add(Members, *this, NewClassMembers);

2441

2442

2443 ClassSet DisequalToOther = Other.getDisequalClasses(DisequalityInfo, CF);

2444

2445

2446 if (DisequalToOther.contains(*this))

2447 return nullptr;

2448

2449 if (!DisequalToOther.isEmpty()) {

2450 ClassSet DisequalToThis = getDisequalClasses(DisequalityInfo, CF);

2451 DisequalityInfo = DF.remove(DisequalityInfo, Other);

2452

2453 for (EquivalenceClass DisequalClass : DisequalToOther) {

2454 DisequalToThis = CF.add(DisequalToThis, DisequalClass);

2455

2456

2457

2458

2459 ClassSet OriginalSetLinkedToOther =

2460 *DisequalityInfo.lookup(DisequalClass);

2461

2462

2463

2464 ClassSet NewSet = CF.remove(OriginalSetLinkedToOther, Other);

2465 NewSet = CF.add(NewSet, *this);

2466

2467 DisequalityInfo = DF.add(DisequalityInfo, DisequalClass, NewSet);

2468 }

2469

2470 DisequalityInfo = DF.add(DisequalityInfo, *this, DisequalToThis);

2471 State = State->set(DisequalityInfo);

2472 }

2473

2474

2475 State = State->set(Classes);

2476 State = State->set(Members);

2477

2478 return State;

2479}

2480

2481inline SymbolSet::Factory &

2482EquivalenceClass::getMembersFactory(ProgramStateRef State) {

2483 return State->get_context<SymbolSet>();

2484}

2485

2487 if (const SymbolSet *Members = State->get(*this))

2488 return *Members;

2489

2490

2491

2492 SymbolSet::Factory &F = getMembersFactory(State);

2493 return F.add(F.getEmptySet(), getRepresentativeSymbol());

2494}

2495

2496bool EquivalenceClass::isTrivial(ProgramStateRef State) const {

2497 return State->get(*this) == nullptr;

2498}

2499

2500bool EquivalenceClass::isTriviallyDead(ProgramStateRef State,

2502 return isTrivial(State) && Reaper.isDead(getRepresentativeSymbol());

2503}

2504

2509 return markDisequal(RF, State, find(State, First), find(State, Second));

2510}

2511

2514 EquivalenceClass First,

2515 EquivalenceClass Second) {

2516 return First.markDisequal(RF, State, Second);

2517}

2518

2521 EquivalenceClass Other) const {

2522

2523

2524 if (*this == Other) {

2525 return nullptr;

2526 }

2527

2528 DisequalityMapTy DisequalityInfo = State->get();

2529 ConstraintRangeTy Constraints = State->get();

2530

2531

2532

2533 if (!addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, *this,

2535 !addToDisequalityInfo(DisequalityInfo, Constraints, RF, State, Other,

2536 *this))

2537 return nullptr;

2538

2539 assert(areFeasible(Constraints) && "Constraint manager shouldn't produce "

2540 "a state with infeasible constraints");

2541

2542 State = State->set(DisequalityInfo);

2543 State = State->set(Constraints);

2544

2545 return State;

2546}

2547

2548inline bool EquivalenceClass::addToDisequalityInfo(

2549 DisequalityMapTy &Info, ConstraintRangeTy &Constraints,

2551 EquivalenceClass Second) {

2552

2553

2554 DisequalityMapTy::Factory &F = State->get_context();

2555 ClassSet::Factory &CF = State->get_context();

2556 ConstraintRangeTy::Factory &CRF = State->get_context();

2557

2558

2559 const ClassSet *CurrentSet = Info.lookup(First);

2560 ClassSet NewSet = CurrentSet ? *CurrentSet : CF.getEmptySet();

2561 NewSet = CF.add(NewSet, Second);

2562

2563 Info = F.add(Info, First, NewSet);

2564

2565

2566

2567

2568

2569

2570 if (const RangeSet *SecondConstraint = Constraints.lookup(Second))

2571 if (const llvm::APSInt *Point = SecondConstraint->getConcreteValue()) {

2572

2573 RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(

2574 RF, State, First.getRepresentativeSymbol());

2575

2576 FirstConstraint = RF.deletePoint(FirstConstraint, *Point);

2577

2578

2579

2580 if (FirstConstraint.isEmpty())

2581 return false;

2582

2583 Constraints = CRF.add(Constraints, First, FirstConstraint);

2584 }

2585

2586 return true;

2587}

2588

2589inline std::optional EquivalenceClass::areEqual(ProgramStateRef State,

2592 return EquivalenceClass::areEqual(State, find(State, FirstSym),

2593 find(State, SecondSym));

2594}

2595

2596inline std::optional EquivalenceClass::areEqual(ProgramStateRef State,

2597 EquivalenceClass First,

2598 EquivalenceClass Second) {

2599

2600 if (First == Second)

2601 return true;

2602

2603

2604

2605 ClassSet DisequalToFirst = First.getDisequalClasses(State);

2606 if (DisequalToFirst.contains(Second))

2607 return false;

2608

2609

2610 return std::nullopt;

2611}

2612

2615

2616 SymbolSet ClsMembers = getClassMembers(State);

2617 assert(ClsMembers.contains(Old));

2618

2619

2620 SymbolSet::Factory &F = getMembersFactory(State);

2621 ClassMembersTy::Factory &EMFactory = State->get_context();

2622 ClsMembers = F.remove(ClsMembers, Old);

2623

2624

2625 assert(!ClsMembers.isEmpty() &&

2626 "Class should have had at least two members before member removal");

2627

2628 ClassMembersTy ClassMembersMap = State->get();

2629 ClassMembersMap = EMFactory.add(ClassMembersMap, *this, ClsMembers);

2630 State = State->set(ClassMembersMap);

2631

2632

2633 ClassMapTy Classes = State->get();

2634 ClassMapTy::Factory &CMF = State->get_context();

2635 Classes = CMF.remove(Classes, Old);

2636 State = State->set(Classes);

2637

2638 return State;

2639}

2640

2641

2644 if (!Constraint)

2645 return State;

2646

2648

2649

2651 return State->assume(DefinedVal, false);

2652

2653

2654

2656 State = State->assume(DefinedVal, true);

2657 if (!State)

2658 return nullptr;

2659

2660 }

2661

2662

2663 return State->assumeInclusiveRange(DefinedVal, Constraint->getMinValue(),

2665}

2666

2667

2668

2669

2670

2671

2675 SymbolSet ClassMembers = Class.getClassMembers(State);

2676 for (const SymbolRef &MemberSym : ClassMembers) {

2677

2680

2681

2682

2684 const llvm::APSInt &SV = CI->getValue();

2685 const RangeSet *ClassConstraint = getConstraint(State, Class);

2686

2687 if (ClassConstraint && !ClassConstraint->contains(SV))

2688 return nullptr;

2689 }

2690

2691 if (SimplifiedMemberSym && MemberSym != SimplifiedMemberSym) {

2692

2693

2694

2696 State = merge(F, State, MemberSym, SimplifiedMemberSym);

2697 if (!State)

2698 return nullptr;

2699

2700 if (OldState == State)

2701 continue;

2702

2703

2704

2705

2706

2707

2708

2709

2710

2711

2712

2713

2714

2715

2716 State = find(State, MemberSym).removeMember(State, MemberSym);

2717

2718

2719

2720 const RangeSet *ClassConstraint = getConstraint(State, Class);

2721

2722

2723

2724

2725

2726

2727

2728

2729

2730

2731

2732

2733

2734

2735

2736

2737

2738

2739

2740

2741 State = reAssume(State, ClassConstraint, SimplifiedMemberVal);

2742 if (!State)

2743 return nullptr;

2744 }

2745 }

2746 return State;

2747}

2748

2749inline ClassSet EquivalenceClass::getDisequalClasses(ProgramStateRef State,

2751 return find(State, Sym).getDisequalClasses(State);

2752}

2753

2754inline ClassSet

2755EquivalenceClass::getDisequalClasses(ProgramStateRef State) const {

2756 return getDisequalClasses(State->get(),

2757 State->get_context());

2758}

2759

2760inline ClassSet

2761EquivalenceClass::getDisequalClasses(DisequalityMapTy Map,

2762 ClassSet::Factory &Factory) const {

2763 if (const ClassSet *DisequalClasses = Map.lookup(*this))

2764 return *DisequalClasses;

2765

2766 return Factory.getEmptySet();

2767}

2768

2769bool EquivalenceClass::isClassDataConsistent(ProgramStateRef State) {

2770 ClassMembersTy Members = State->get();

2771

2772 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair : Members) {

2774

2775 if (find(State, Member) == ClassMembersPair.first) {

2776 continue;

2777 }

2778

2779 return false;

2780 }

2781 }

2782

2783 DisequalityMapTy Disequalities = State->get();

2784 for (std::pair<EquivalenceClass, ClassSet> DisequalityInfo : Disequalities) {

2785 EquivalenceClass Class = DisequalityInfo.first;

2786 ClassSet DisequalClasses = DisequalityInfo.second;

2787

2788

2789 if (DisequalClasses.isEmpty())

2790 return false;

2791

2792

2793

2794 for (EquivalenceClass DisequalClass : DisequalClasses) {

2795 const ClassSet *DisequalToDisequalClasses =

2796 Disequalities.lookup(DisequalClass);

2797

2798

2799 if (!DisequalToDisequalClasses ||

2800 !DisequalToDisequalClasses->contains(Class))

2801 return false;

2802 }

2803 }

2804

2805 return true;

2806}

2807

2808

2809

2810

2811

2812bool RangeConstraintManager::canReasonAbout(SVal X) const {

2813 std::optionalnonloc::SymbolVal SymVal = X.getAs<nonloc::SymbolVal>();

2814 if (SymVal && SymVal->isExpression()) {

2815 const SymExpr *SE = SymVal->getSymbol();

2816

2817 if (const SymIntExpr *SIE = dyn_cast(SE)) {

2818 switch (SIE->getOpcode()) {

2819

2820 case BO_And:

2821 case BO_Or:

2822 case BO_Xor:

2823 return false;

2824

2825

2826 case BO_Mul:

2827 case BO_Div:

2828 case BO_Rem:

2829 case BO_Shl:

2830 case BO_Shr:

2831 return false;

2832

2833 default:

2834 return true;

2835 }

2836 }

2837

2838 if (const SymSymExpr *SSE = dyn_cast(SE)) {

2839

2842

2843

2844

2845

2848 }

2849 }

2850 }

2851

2852 return false;

2853 }

2854

2855 return true;

2856}

2857

2860 const RangeSet *Ranges = getConstraint(State, Sym);

2861

2862

2863 if (!Ranges)

2865

2866

2868 return *Value == 0;

2869

2873

2874

2875 if (!Ranges->contains(Zero))

2876 return false;

2877

2878

2880}

2881

2882const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,

2884 return getRange(St, Sym).getConcreteValue();

2885}

2886

2887const llvm::APSInt *RangeConstraintManager::getSymMinVal(ProgramStateRef St,

2890 return Range.isEmpty() ? nullptr : &Range.getMinValue();

2891}

2892

2893const llvm::APSInt *RangeConstraintManager::getSymMaxVal(ProgramStateRef St,

2896 return Range.isEmpty() ? nullptr : &Range.getMaxValue();

2897}

2898

2899

2900

2901

2902

2903

2904

2906RangeConstraintManager::removeDeadBindings(ProgramStateRef State,

2908 ClassMembersTy ClassMembersMap = State->get();

2909 ClassMembersTy NewClassMembersMap = ClassMembersMap;

2910 ClassMembersTy::Factory &EMFactory = State->get_context();

2911 SymbolSet::Factory &SetFactory = State->get_context<SymbolSet>();

2912

2913 ConstraintRangeTy Constraints = State->get();

2914 ConstraintRangeTy NewConstraints = Constraints;

2915 ConstraintRangeTy::Factory &ConstraintFactory =

2916 State->get_context();

2917

2918 ClassMapTy Map = State->get();

2919 ClassMapTy NewMap = Map;

2920 ClassMapTy::Factory &ClassFactory = State->get_context();

2921

2922 DisequalityMapTy Disequalities = State->get();

2923 DisequalityMapTy::Factory &DisequalityFactory =

2924 State->get_context();

2925 ClassSet::Factory &ClassSetFactory = State->get_context();

2926

2927 bool ClassMapChanged = false;

2928 bool MembersMapChanged = false;

2929 bool ConstraintMapChanged = false;

2930 bool DisequalitiesChanged = false;

2931

2932 auto removeDeadClass = [&](EquivalenceClass Class) {

2933

2934 Constraints = ConstraintFactory.remove(Constraints, Class);

2935 ConstraintMapChanged = true;

2936

2937

2938

2939 ClassSet DisequalClasses =

2940 Class.getDisequalClasses(Disequalities, ClassSetFactory);

2941 if (!DisequalClasses.isEmpty()) {

2942 for (EquivalenceClass DisequalClass : DisequalClasses) {

2943 ClassSet DisequalToDisequalSet =

2944 DisequalClass.getDisequalClasses(Disequalities, ClassSetFactory);

2945

2946

2947 assert(!DisequalToDisequalSet.isEmpty());

2948 ClassSet NewSet = ClassSetFactory.remove(DisequalToDisequalSet, Class);

2949

2950

2951 if (NewSet.isEmpty()) {

2952 Disequalities =

2953 DisequalityFactory.remove(Disequalities, DisequalClass);

2954 } else {

2955 Disequalities =

2956 DisequalityFactory.add(Disequalities, DisequalClass, NewSet);

2957 }

2958 }

2959

2960 Disequalities = DisequalityFactory.remove(Disequalities, Class);

2961 DisequalitiesChanged = true;

2962 }

2963 };

2964

2965

2966 for (std::pair<EquivalenceClass, RangeSet> ClassConstraintPair :

2967 Constraints) {

2968 EquivalenceClass Class = ClassConstraintPair.first;

2969 if (Class.isTriviallyDead(State, SymReaper)) {

2970

2971 removeDeadClass(Class);

2972 }

2973 }

2974

2975

2976 for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {

2977 SymbolRef Sym = SymbolClassPair.first;

2978

2979 if (SymReaper.isDead(Sym)) {

2980 ClassMapChanged = true;

2981 NewMap = ClassFactory.remove(NewMap, Sym);

2982 }

2983 }

2984

2985

2986

2987 for (std::pair<EquivalenceClass, SymbolSet> ClassMembersPair :

2988 ClassMembersMap) {

2989 EquivalenceClass Class = ClassMembersPair.first;

2990 SymbolSet LiveMembers = ClassMembersPair.second;

2991 bool MembersChanged = false;

2992

2995 MembersChanged = true;

2996 LiveMembers = SetFactory.remove(LiveMembers, Member);

2997 }

2998 }

2999

3000

3001 if (!MembersChanged)

3002 continue;

3003

3004 MembersMapChanged = true;

3005

3006 if (LiveMembers.isEmpty()) {

3007

3008 NewClassMembersMap = EMFactory.remove(NewClassMembersMap, Class);

3009

3010

3011 removeDeadClass(Class);

3012 } else {

3013

3014 NewClassMembersMap =

3015 EMFactory.add(NewClassMembersMap, Class, LiveMembers);

3016 }

3017 }

3018

3019

3020

3021

3022 if (ClassMapChanged)

3023 State = State->set(NewMap);

3024

3025 if (MembersMapChanged)

3026 State = State->set(NewClassMembersMap);

3027

3028 if (ConstraintMapChanged)

3029 State = State->set(Constraints);

3030

3031 if (DisequalitiesChanged)

3032 State = State->set(Disequalities);

3033

3034 assert(EquivalenceClass::isClassDataConsistent(State));

3035

3036 return State;

3037}

3038

3041 return SymbolicRangeInferrer::inferRange(F, State, Sym);

3042}

3043

3047 return ConstraintAssignor::assign(State, getSValBuilder(), F, Sym, Range);

3048}

3049

3050

3051

3052

3053

3054

3055

3056

3057

3058

3059

3060

3061

3064 const llvm::APSInt &Int,

3065 const llvm::APSInt &Adjustment) {

3066

3067 APSIntType AdjustmentType(Adjustment);

3069 return St;

3070

3071 llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;

3074

3075 return setRange(St, Sym, New);

3076}

3077

3080 const llvm::APSInt &Int,

3081 const llvm::APSInt &Adjustment) {

3082

3083 APSIntType AdjustmentType(Adjustment);

3085 return nullptr;

3086

3087

3088 llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;

3091

3092 return setRange(St, Sym, New);

3093}

3094

3097 const llvm::APSInt &Int,

3098 const llvm::APSInt &Adjustment) const {

3099

3100 APSIntType AdjustmentType(Adjustment);

3101 switch (AdjustmentType.testInRange(Int, true)) {

3105 break;

3108 }

3109

3110

3111 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);

3112 llvm::APSInt Min = AdjustmentType.getMinValue();

3113 if (ComparisonVal == Min)

3115

3116 llvm::APSInt Lower = Min - Adjustment;

3117 llvm::APSInt Upper = ComparisonVal - Adjustment;

3118 --Upper;

3119

3122}

3123

3126 const llvm::APSInt &Int,

3127 const llvm::APSInt &Adjustment) {

3128 RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);

3129 return setRange(St, Sym, New);

3130}

3131

3134 const llvm::APSInt &Int,

3135 const llvm::APSInt &Adjustment) const {

3136

3137 APSIntType AdjustmentType(Adjustment);

3138 switch (AdjustmentType.testInRange(Int, true)) {

3142 break;

3145 }

3146

3147

3148 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);

3149 llvm::APSInt Max = AdjustmentType.getMaxValue();

3150 if (ComparisonVal == Max)

3152

3153 llvm::APSInt Lower = ComparisonVal - Adjustment;

3154 llvm::APSInt Upper = Max - Adjustment;

3155 ++Lower;

3156

3158 return F.intersect(SymRange, Lower, Upper);

3159}

3160

3163 const llvm::APSInt &Int,

3164 const llvm::APSInt &Adjustment) {

3165 RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);

3166 return setRange(St, Sym, New);

3167}

3168

3171 const llvm::APSInt &Int,

3172 const llvm::APSInt &Adjustment) const {

3173

3174 APSIntType AdjustmentType(Adjustment);

3175 switch (AdjustmentType.testInRange(Int, true)) {

3179 break;

3182 }

3183

3184

3185 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);

3186 llvm::APSInt Min = AdjustmentType.getMinValue();

3187 if (ComparisonVal == Min)

3189

3190 llvm::APSInt Max = AdjustmentType.getMaxValue();

3191 llvm::APSInt Lower = ComparisonVal - Adjustment;

3192 llvm::APSInt Upper = Max - Adjustment;

3193

3195 return F.intersect(SymRange, Lower, Upper);

3196}

3197

3200 const llvm::APSInt &Int,

3201 const llvm::APSInt &Adjustment) {

3202 RangeSet New = getSymGERange(St, Sym, Int, Adjustment);

3203 return setRange(St, Sym, New);

3204}

3205

3207RangeConstraintManager::getSymLERange(llvm::function_ref<RangeSet()> RS,

3208 const llvm::APSInt &Int,

3209 const llvm::APSInt &Adjustment) const {

3210

3211 APSIntType AdjustmentType(Adjustment);

3212 switch (AdjustmentType.testInRange(Int, true)) {

3216 break;

3218 return RS();

3219 }

3220

3221

3222 llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);

3223 llvm::APSInt Max = AdjustmentType.getMaxValue();

3224 if (ComparisonVal == Max)

3225 return RS();

3226

3227 llvm::APSInt Min = AdjustmentType.getMinValue();

3228 llvm::APSInt Lower = Min - Adjustment;

3229 llvm::APSInt Upper = ComparisonVal - Adjustment;

3230

3233}

3234

3237 const llvm::APSInt &Int,

3238 const llvm::APSInt &Adjustment) const {

3239 return getSymLERange([&] { return getRange(St, Sym); }, Int, Adjustment);

3240}

3241

3244 const llvm::APSInt &Int,

3245 const llvm::APSInt &Adjustment) {

3246 RangeSet New = getSymLERange(St, Sym, Int, Adjustment);

3247 return setRange(St, Sym, New);

3248}

3249

3250ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(

3252 const llvm::APSInt &To, const llvm::APSInt &Adjustment) {

3253 RangeSet New = getSymGERange(State, Sym, From, Adjustment);

3255 return nullptr;

3256 RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);

3257 return setRange(State, Sym, Out);

3258}

3259

3260ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(

3262 const llvm::APSInt &To, const llvm::APSInt &Adjustment) {

3263 RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);

3264 RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);

3266 return setRange(State, Sym, New);

3267}

3268

3269

3270

3271

3272

3273void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,

3274 const char *NL, unsigned int Space,

3275 bool IsDot) const {

3276 printConstraints(Out, State, NL, Space, IsDot);

3277 printEquivalenceClasses(Out, State, NL, Space, IsDot);

3278 printDisequalities(Out, State, NL, Space, IsDot);

3279}

3280

3281void RangeConstraintManager::printValue(raw_ostream &Out, ProgramStateRef State,

3285 Out << "";

3286 return;

3287 }

3289 RS.dump(Out);

3290}

3291

3293 std::string S;

3294 llvm::raw_string_ostream O(S);

3296 return S;

3297}

3298

3299void RangeConstraintManager::printConstraints(raw_ostream &Out,

3301 const char *NL,

3302 unsigned int Space,

3303 bool IsDot) const {

3304 ConstraintRangeTy Constraints = State->get();

3305

3306 Indent(Out, Space, IsDot) << "\"constraints\": ";

3307 if (Constraints.isEmpty()) {

3308 Out << "null," << NL;

3309 return;

3310 }

3311

3312 std::map<std::string, RangeSet> OrderedConstraints;

3313 for (std::pair<EquivalenceClass, RangeSet> P : Constraints) {

3314 SymbolSet ClassMembers = P.first.getClassMembers(State);

3315 for (const SymbolRef &ClassMember : ClassMembers) {

3316 bool insertion_took_place;

3317 std::tie(std::ignore, insertion_took_place) =

3318 OrderedConstraints.insert({toString(ClassMember), P.second});

3319 assert(insertion_took_place &&

3320 "two symbols should not have the same dump");

3321 }

3322 }

3323

3324 ++Space;

3325 Out << '[' << NL;

3326 bool First = true;

3327 for (std::pair<std::string, RangeSet> P : OrderedConstraints) {

3330 } else {

3331 Out << ',';

3332 Out << NL;

3333 }

3334 Indent(Out, Space, IsDot)

3335 << "{ \"symbol\": \"" << P.first << "\", \"range\": \"";

3336 P.second.dump(Out);

3337 Out << "\" }";

3338 }

3339 Out << NL;

3340

3341 --Space;

3342 Indent(Out, Space, IsDot) << "]," << NL;

3343}

3344

3346 SymbolSet ClassMembers = Class.getClassMembers(State);

3348 ClassMembers.end());

3349 llvm::sort(ClassMembersSorted,

3352 });

3353

3354 bool FirstMember = true;

3355

3356 std::string Str;

3357 llvm::raw_string_ostream Out(Str);

3358 Out << "[ ";

3359 for (SymbolRef ClassMember : ClassMembersSorted) {

3360 if (FirstMember)

3361 FirstMember = false;

3362 else

3363 Out << ", ";

3364 Out << "\"" << ClassMember << "\"";

3365 }

3366 Out << " ]";

3367 return Str;

3368}

3369

3370void RangeConstraintManager::printEquivalenceClasses(raw_ostream &Out,

3372 const char *NL,

3373 unsigned int Space,

3374 bool IsDot) const {

3375 ClassMembersTy Members = State->get();

3376

3377 Indent(Out, Space, IsDot) << "\"equivalence_classes\": ";

3378 if (Members.isEmpty()) {

3379 Out << "null," << NL;

3380 return;

3381 }

3382

3383 std::setstd::string MembersStr;

3384 for (std::pair<EquivalenceClass, SymbolSet> ClassToSymbolSet : Members)

3385 MembersStr.insert(toString(State, ClassToSymbolSet.first));

3386

3387 ++Space;

3388 Out << '[' << NL;

3389 bool FirstClass = true;

3390 for (const std::string &Str : MembersStr) {

3391 if (FirstClass) {

3392 FirstClass = false;

3393 } else {

3394 Out << ',';

3395 Out << NL;

3396 }

3397 Indent(Out, Space, IsDot);

3398 Out << Str;

3399 }

3400 Out << NL;

3401

3402 --Space;

3403 Indent(Out, Space, IsDot) << "]," << NL;

3404}

3405

3406void RangeConstraintManager::printDisequalities(raw_ostream &Out,

3408 const char *NL,

3409 unsigned int Space,

3410 bool IsDot) const {

3411 DisequalityMapTy Disequalities = State->get();

3412

3413 Indent(Out, Space, IsDot) << "\"disequality_info\": ";

3414 if (Disequalities.isEmpty()) {

3415 Out << "null," << NL;

3416 return;

3417 }

3418

3419

3420

3421 using EqClassesStrTy = std::setstd::string;

3422 using DisequalityInfoStrTy = std::map<std::string, EqClassesStrTy>;

3423 DisequalityInfoStrTy DisequalityInfoStr;

3424 for (std::pair<EquivalenceClass, ClassSet> ClassToDisEqSet : Disequalities) {

3425 EquivalenceClass Class = ClassToDisEqSet.first;

3426 ClassSet DisequalClasses = ClassToDisEqSet.second;

3427 EqClassesStrTy MembersStr;

3428 for (EquivalenceClass DisEqClass : DisequalClasses)

3429 MembersStr.insert(toString(State, DisEqClass));

3430 DisequalityInfoStr.insert({toString(State, Class), MembersStr});

3431 }

3432

3433 ++Space;

3434 Out << '[' << NL;

3435 bool FirstClass = true;

3436 for (std::pair<std::string, EqClassesStrTy> ClassToDisEqSet :

3437 DisequalityInfoStr) {

3438 const std::string &Class = ClassToDisEqSet.first;

3439 if (FirstClass) {

3440 FirstClass = false;

3441 } else {

3442 Out << ',';

3443 Out << NL;

3444 }

3445 Indent(Out, Space, IsDot) << "{" << NL;

3446 unsigned int DisEqSpace = Space + 1;

3447 Indent(Out, DisEqSpace, IsDot) << "\"class\": ";

3449 const EqClassesStrTy &DisequalClasses = ClassToDisEqSet.second;

3450 if (!DisequalClasses.empty()) {

3451 Out << "," << NL;

3452 Indent(Out, DisEqSpace, IsDot) << "\"disequal_to\": [" << NL;

3453 unsigned int DisEqClassSpace = DisEqSpace + 1;

3454 Indent(Out, DisEqClassSpace, IsDot);

3455 bool FirstDisEqClass = true;

3456 for (const std::string &DisEqClass : DisequalClasses) {

3457 if (FirstDisEqClass) {

3458 FirstDisEqClass = false;

3459 } else {

3460 Out << ',' << NL;

3461 Indent(Out, DisEqClassSpace, IsDot);

3462 }

3463 Out << DisEqClass;

3464 }

3465 Out << "]" << NL;

3466 }

3467 Indent(Out, Space, IsDot) << "}";

3468 }

3469 Out << NL;

3470

3471 --Space;

3472 Indent(Out, Space, IsDot) << "]," << NL;

3473}

static bool isTrivial(ASTContext &Ctx, const Expr *E)

Checks if the expression is constant or does not have non-trivial function calls.

static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)

llvm::MachO::SymbolSet SymbolSet

#define REGISTER_MAP_WITH_PROGRAMSTATE(Name, Key, Value)

Declares an immutable map of type NameTy, suitable for placement into the ProgramState.

#define REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(Name, Elem)

Declares an immutable set type Name and registers the factory for such sets in the program state,...

#define CONSTRAINT_DISPATCH(Id)

static void swapIterators(T &First, T &FirstEnd, T &Second, T &SecondEnd)

static ProgramStateRef reAssume(ProgramStateRef State, const RangeSet *Constraint, SVal TheValue)

#define DEFAULT_ASSIGN(Id)

static std::string toString(const clang::SanitizerSet &Sanitizers)

Produce a string containing comma-separated names of sanitizers in Sanitizers set.

static CharSourceRange getRange(const CharSourceRange &EditRange, const SourceManager &SM, const LangOptions &LangOpts, bool IncludeMacroExpansion)

static BinaryOperatorKind getOpFromIndex(size_t Index)

constexpr size_t getCmpOpCount() const

TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP, BinaryOperatorKind QueriedOP) const

TriStateKind getCmpOpStateForUnknownX2(BinaryOperatorKind CurrentOP) const

bool isComparisonOp() const

bool isRelationalOp() const

static Opcode negateComparisonOp(Opcode Opc)

static Opcode reverseComparisonOp(Opcode Opc)

bool isEqualityOp() const

A (possibly-)qualified type.

The base class of the type hierarchy.

bool isSignedIntegerOrEnumerationType() const

Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...

bool isUnsignedIntegerOrEnumerationType() const

Determines whether this is an integer type that is unsigned or an enumeration types whose underlying ...

bool isReferenceType() const

bool isIntegralOrEnumerationType() const

Determine whether this type is an integral or enumeration type.

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

llvm::APSInt getZeroValue() const LLVM_READONLY

Returns an all-zero value for this type.

RangeTestResultKind

Used to classify whether a value is representable using this type.

@ RTR_Within

Value is representable using this type.

@ RTR_Below

Value is less than the minimum representable value.

@ RTR_Above

Value is greater than the maximum representable value.

uint32_t getBitWidth() const

RangeTestResultKind testInRange(const llvm::APSInt &Val, bool AllowMixedSign) const LLVM_READONLY

Tests whether a given value is losslessly representable using this type.

void apply(llvm::APSInt &Value) const

Convert a given APSInt, in place, to match this type.

llvm::APSInt getMinValue() const LLVM_READONLY

Returns the minimum value for this type.

llvm::APSInt convert(const llvm::APSInt &Value) const LLVM_READONLY

Convert and return a new APSInt with the given value, but this type's bit width and signedness.

llvm::APSInt getValue(uint64_t RawValue) const LLVM_READONLY

APSIntType getAPSIntType(QualType T) const

Returns the type of the APSInt used to store values of the given QualType.

Template implementation for all binary symbolic expressions.

QualType getType() const override

BinaryOperator::Opcode getOpcode() const

static bool isLocType(QualType T)

SValBuilder & getSValBuilder()

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.

RangeSet getRangeSet(Range Origin)

Create a new set with just one range.

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.

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.

bool encodesTrueRange() const

Test if the range doesn't contain zero.

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.

ImplType::const_iterator const_iterator

bool contains(llvm::APSInt Point) const

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

void dump(raw_ostream &OS) const

bool containsZero() const

uint32_t getBitWidth() 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

void dump(raw_ostream &OS) const

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

const llvm::APSInt & To() const

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

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.

T castAs() const

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

SymExprVisitor - this class implements a simple visitor for SymExpr subclasses.

virtual void dumpToStream(raw_ostream &os) const

virtual QualType getType() const =0

const SymExprT * acquire(Args &&...args)

Create or retrieve a SymExpr of type SymExprT for the given arguments.

A class responsible for cleaning up unused symbols.

bool isDead(SymbolRef sym)

Returns whether or not a symbol has been confirmed dead.

Represents a symbolic expression involving a unary operator.

QualType getType() const override

UnaryOperator::Opcode getOpcode() const

const SymExpr * getOperand() const

Value representing integer constant.

Represents symbolic expression that isn't a location.

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

@ CF

Indicates that the tracked object is a CF object.

std::unique_ptr< ConstraintManager > CreateRangeConstraintManager(ProgramStateManager &statemgr, ExprEngine *exprengine)

ConstraintMap getConstraintMap(ProgramStateRef State)

bool Zero(InterpState &S, CodePtr OpPC)

bool Const(InterpState &S, CodePtr OpPC, const T &Arg)

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

bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)

bool operator<(DeclarationName LHS, DeclarationName RHS)

Ordering on two declaration names.

@ Result

The result type of a method or function.

bool operator!=(CanQual< T > x, CanQual< U > y)

const FunctionProtoType * T

@ Class

The "class" keyword introduces the elaborated-type-specifier.

@ Other

Other implicit parameter.

__UINTPTR_TYPE__ uintptr_t

An unsigned integer type with the property that any valid pointer to void can be converted to this ty...