unittests/ADT/BitVectorTest.cpp

   1 //===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector tests --------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/BitVector.h"
  10 #include "llvm/ADT/SmallBitVector.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 // Test fixture
  18 template <typename T>
  19 class BitVectorTest : public ::testing::Test { };
  20
  21 // Test both BitVector and SmallBitVector with the same suite of tests.
  22 typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes;
  23 TYPED_TEST_CASE(BitVectorTest, BitVectorTestTypes);
  24
  25 TYPED_TEST(BitVectorTest, TrivialOperation) {
  26   TypeParam Vec;
  27   EXPECT_EQ(0U, Vec.count());
  28   EXPECT_EQ(0U, Vec.size());
  29   EXPECT_FALSE(Vec.any());
  30   EXPECT_TRUE(Vec.all());
  31   EXPECT_TRUE(Vec.none());
  32   EXPECT_TRUE(Vec.empty());
  33
  34   Vec.resize(5, true);
  35   EXPECT_EQ(5U, Vec.count());
  36   EXPECT_EQ(5U, Vec.size());
  37   EXPECT_TRUE(Vec.any());
  38   EXPECT_TRUE(Vec.all());
  39   EXPECT_FALSE(Vec.none());
  40   EXPECT_FALSE(Vec.empty());
  41
  42   Vec.resize(11);
  43   EXPECT_EQ(5U, Vec.count());
  44   EXPECT_EQ(11U, Vec.size());
  45   EXPECT_TRUE(Vec.any());
  46   EXPECT_FALSE(Vec.all());
  47   EXPECT_FALSE(Vec.none());
  48   EXPECT_FALSE(Vec.empty());
  49
  50   TypeParam Inv = Vec;
  51   Inv.flip();
  52   EXPECT_EQ(6U, Inv.count());
  53   EXPECT_EQ(11U, Inv.size());
  54   EXPECT_TRUE(Inv.any());
  55   EXPECT_FALSE(Inv.all());
  56   EXPECT_FALSE(Inv.none());
  57   EXPECT_FALSE(Inv.empty());
  58
  59   EXPECT_FALSE(Inv == Vec);
  60   EXPECT_TRUE(Inv != Vec);
  61   Vec.flip();
  62   EXPECT_TRUE(Inv == Vec);
  63   EXPECT_FALSE(Inv != Vec);
  64
  65   // Add some "interesting" data to Vec.
  66   Vec.resize(23, true);
  67   Vec.resize(25, false);
  68   Vec.resize(26, true);
  69   Vec.resize(29, false);
  70   Vec.resize(33, true);
  71   Vec.resize(57, false);
  72   unsigned Count = 0;
  73   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
  74     ++Count;
  75     EXPECT_TRUE(Vec[i]);
  76     EXPECT_TRUE(Vec.test(i));
  77   }
  78   EXPECT_EQ(Count, Vec.count());
  79   EXPECT_EQ(Count, 23u);
  80   EXPECT_FALSE(Vec[0]);
  81   EXPECT_TRUE(Vec[32]);
  82   EXPECT_FALSE(Vec[56]);
  83   Vec.resize(61, false);
  84
  85   TypeParam Copy = Vec;
  86   TypeParam Alt(3, false);
  87   Alt.resize(6, true);
  88   std::swap(Alt, Vec);
  89   EXPECT_TRUE(Copy == Alt);
  90   EXPECT_TRUE(Vec.size() == 6);
  91   EXPECT_TRUE(Vec.count() == 3);
  92   EXPECT_TRUE(Vec.find_first() == 3);
  93   std::swap(Copy, Vec);
  94
  95   // Add some more "interesting" data.
  96   Vec.resize(68, true);
  97   Vec.resize(78, false);
  98   Vec.resize(89, true);
  99   Vec.resize(90, false);
 100   Vec.resize(91, true);
 101   Vec.resize(130, false);
 102   Count = 0;
 103   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
 104     ++Count;
 105     EXPECT_TRUE(Vec[i]);
 106     EXPECT_TRUE(Vec.test(i));
 107   }
 108   EXPECT_EQ(Count, Vec.count());
 109   EXPECT_EQ(Count, 42u);
 110   EXPECT_FALSE(Vec[0]);
 111   EXPECT_TRUE(Vec[32]);
 112   EXPECT_FALSE(Vec[60]);
 113   EXPECT_FALSE(Vec[129]);
 114
 115   Vec.flip(60);
 116   EXPECT_TRUE(Vec[60]);
 117   EXPECT_EQ(Count + 1, Vec.count());
 118   Vec.flip(60);
 119   EXPECT_FALSE(Vec[60]);
 120   EXPECT_EQ(Count, Vec.count());
 121
 122   Vec.reset(32);
 123   EXPECT_FALSE(Vec[32]);
 124   EXPECT_EQ(Count - 1, Vec.count());
 125   Vec.set(32);
 126   EXPECT_TRUE(Vec[32]);
 127   EXPECT_EQ(Count, Vec.count());
 128
 129   Vec.flip();
 130   EXPECT_EQ(Vec.size() - Count, Vec.count());
 131
 132   Vec.reset();
 133   EXPECT_EQ(0U, Vec.count());
 134   EXPECT_EQ(130U, Vec.size());
 135   EXPECT_FALSE(Vec.any());
 136   EXPECT_FALSE(Vec.all());
 137   EXPECT_TRUE(Vec.none());
 138   EXPECT_FALSE(Vec.empty());
 139
 140   Vec.flip();
 141   EXPECT_EQ(130U, Vec.count());
 142   EXPECT_EQ(130U, Vec.size());
 143   EXPECT_TRUE(Vec.any());
 144   EXPECT_TRUE(Vec.all());
 145   EXPECT_FALSE(Vec.none());
 146   EXPECT_FALSE(Vec.empty());
 147
 148   Vec.resize(64);
 149   EXPECT_EQ(64U, Vec.count());
 150   EXPECT_EQ(64U, Vec.size());
 151   EXPECT_TRUE(Vec.any());
 152   EXPECT_TRUE(Vec.all());
 153   EXPECT_FALSE(Vec.none());
 154   EXPECT_FALSE(Vec.empty());
 155
 156   Vec.flip();
 157   EXPECT_EQ(0U, Vec.count());
 158   EXPECT_EQ(64U, Vec.size());
 159   EXPECT_FALSE(Vec.any());
 160   EXPECT_FALSE(Vec.all());
 161   EXPECT_TRUE(Vec.none());
 162   EXPECT_FALSE(Vec.empty());
 163
 164   Inv = TypeParam().flip();
 165   EXPECT_EQ(0U, Inv.count());
 166   EXPECT_EQ(0U, Inv.size());
 167   EXPECT_FALSE(Inv.any());
 168   EXPECT_TRUE(Inv.all());
 169   EXPECT_TRUE(Inv.none());
 170   EXPECT_TRUE(Inv.empty());
 171
 172   Vec.clear();
 173   EXPECT_EQ(0U, Vec.count());
 174   EXPECT_EQ(0U, Vec.size());
 175   EXPECT_FALSE(Vec.any());
 176   EXPECT_TRUE(Vec.all());
 177   EXPECT_TRUE(Vec.none());
 178   EXPECT_TRUE(Vec.empty());
 179 }
 180
 181 TYPED_TEST(BitVectorTest, SimpleFindOpsMultiWord) {
 182   TypeParam A;
 183
 184   // Test finding next set and unset bits in a BitVector with multiple words
 185   A.resize(100);
 186   A.set(12);
 187   A.set(13);
 188   A.set(75);
 189
 190   EXPECT_EQ(75, A.find_last());
 191   EXPECT_EQ(12, A.find_first());
 192   EXPECT_EQ(13, A.find_next(12));
 193   EXPECT_EQ(75, A.find_next(13));
 194   EXPECT_EQ(-1, A.find_next(75));
 195
 196   EXPECT_EQ(-1, A.find_prev(12));
 197   EXPECT_EQ(12, A.find_prev(13));
 198   EXPECT_EQ(13, A.find_prev(75));
 199   EXPECT_EQ(75, A.find_prev(90));
 200
 201   EXPECT_EQ(0, A.find_first_unset());
 202   EXPECT_EQ(99, A.find_last_unset());
 203   EXPECT_EQ(14, A.find_next_unset(11));
 204   EXPECT_EQ(14, A.find_next_unset(12));
 205   EXPECT_EQ(14, A.find_next_unset(13));
 206   EXPECT_EQ(16, A.find_next_unset(15));
 207   EXPECT_EQ(76, A.find_next_unset(74));
 208   EXPECT_EQ(76, A.find_next_unset(75));
 209   EXPECT_EQ(-1, A.find_next_unset(99));
 210
 211   A.set(0, 100);
 212   EXPECT_EQ(100U, A.count());
 213   EXPECT_EQ(0, A.find_first());
 214   EXPECT_EQ(-1, A.find_first_unset());
 215   EXPECT_EQ(-1, A.find_last_unset());
 216   EXPECT_EQ(99, A.find_last());
 217   EXPECT_EQ(99, A.find_next(98));
 218
 219   A.reset(0, 100);
 220   EXPECT_EQ(0U, A.count());
 221   EXPECT_EQ(-1, A.find_first());
 222   EXPECT_EQ(-1, A.find_last());
 223   EXPECT_EQ(0, A.find_first_unset());
 224   EXPECT_EQ(99, A.find_last_unset());
 225   EXPECT_EQ(99, A.find_next_unset(98));
 226 }
 227
 228 // Test finding next set and unset bits in a BitVector/SmallBitVector within a
 229 // uintptr_t - check both 32-bit (Multi) and 64-bit (Small) targets.
 230 TYPED_TEST(BitVectorTest, SimpleFindOps64Bit) {
 231   TypeParam A;
 232
 233   A.resize(57);
 234   A.set(12);
 235   A.set(13);
 236   A.set(47);
 237
 238   EXPECT_EQ(47, A.find_last());
 239   EXPECT_EQ(12, A.find_first());
 240   EXPECT_EQ(13, A.find_next(12));
 241   EXPECT_EQ(47, A.find_next(13));
 242   EXPECT_EQ(-1, A.find_next(47));
 243
 244   EXPECT_EQ(-1, A.find_prev(12));
 245   EXPECT_EQ(12, A.find_prev(13));
 246   EXPECT_EQ(13, A.find_prev(47));
 247   EXPECT_EQ(47, A.find_prev(56));
 248
 249   EXPECT_EQ(0, A.find_first_unset());
 250   EXPECT_EQ(56, A.find_last_unset());
 251   EXPECT_EQ(14, A.find_next_unset(11));
 252   EXPECT_EQ(14, A.find_next_unset(12));
 253   EXPECT_EQ(14, A.find_next_unset(13));
 254   EXPECT_EQ(16, A.find_next_unset(15));
 255   EXPECT_EQ(48, A.find_next_unset(46));
 256   EXPECT_EQ(48, A.find_next_unset(47));
 257   EXPECT_EQ(-1, A.find_next_unset(56));
 258 }
 259
 260 // Check if a SmallBitVector is in small mode. This check is used in tests
 261 // that run for both SmallBitVector and BitVector. This check doesn't apply
 262 // to BitVector so we provide an overload that returns true to get the tests
 263 // to compile.
 264 static bool SmallBitVectorIsSmallMode(const SmallBitVector &bv) {
 265   return bv.isSmall();
 266 }
 267 static bool SmallBitVectorIsSmallMode(const BitVector &) { return true; }
 268
 269 // These tests are intended to exercise the single-word case of BitVector
 270 // and the small-mode case of SmallBitVector.
 271 TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) {
 272   // Test finding in an empty BitVector.
 273   TypeParam A;
 274   ASSERT_TRUE(SmallBitVectorIsSmallMode(A));
 275   EXPECT_EQ(-1, A.find_first());
 276   EXPECT_EQ(-1, A.find_last());
 277   EXPECT_EQ(-1, A.find_first_unset());
 278   EXPECT_EQ(-1, A.find_last_unset());
 279
 280   A.resize(20);
 281   A.set(3);
 282   A.set(4);
 283   A.set(16);
 284   ASSERT_TRUE(SmallBitVectorIsSmallMode(A));
 285   EXPECT_EQ(16, A.find_last());
 286   EXPECT_EQ(3, A.find_first());
 287   EXPECT_EQ(3, A.find_next(1));
 288   EXPECT_EQ(4, A.find_next(3));
 289   EXPECT_EQ(16, A.find_next(4));
 290   EXPECT_EQ(-1, A.find_next(16));
 291
 292   EXPECT_EQ(-1, A.find_prev(3));
 293   EXPECT_EQ(3, A.find_prev(4));
 294   EXPECT_EQ(4, A.find_prev(16));
 295   EXPECT_EQ(16, A.find_prev(18));
 296
 297   EXPECT_EQ(0, A.find_first_unset());
 298   EXPECT_EQ(19, A.find_last_unset());
 299   EXPECT_EQ(5, A.find_next_unset(3));
 300   EXPECT_EQ(5, A.find_next_unset(4));
 301   EXPECT_EQ(13, A.find_next_unset(12));
 302   EXPECT_EQ(17, A.find_next_unset(15));
 303 }
 304
 305 TEST(BitVectorTest, FindInRangeMultiWord) {
 306   BitVector Vec;
 307
 308   Vec.resize(200);
 309   Vec.set(3, 7);
 310   Vec.set(24, 35);
 311   Vec.set(50, 70);
 312   Vec.set(150);
 313   Vec.set(152);
 314   Vec.set(154);
 315
 316   // find first
 317   EXPECT_EQ(-1, Vec.find_first_in(0, 0));
 318   EXPECT_EQ(-1, Vec.find_first_in(24, 24));
 319   EXPECT_EQ(-1, Vec.find_first_in(7, 24));
 320
 321   EXPECT_EQ(3, Vec.find_first_in(0, 10));
 322   EXPECT_EQ(4, Vec.find_first_in(4, 10));
 323   EXPECT_EQ(150, Vec.find_first_in(100, 200));
 324   EXPECT_EQ(152, Vec.find_first_in(151, 200));
 325   EXPECT_EQ(154, Vec.find_first_in(153, 200));
 326
 327   EXPECT_EQ(-1, Vec.find_first_in(155, 200));
 328   Vec.set(199);
 329   EXPECT_EQ(199, Vec.find_first_in(199, 200));
 330   Vec.reset(199);
 331
 332   // find last
 333   EXPECT_EQ(-1, Vec.find_last_in(0, 0));
 334   EXPECT_EQ(-1, Vec.find_last_in(24, 24));
 335   EXPECT_EQ(-1, Vec.find_last_in(7, 24));
 336
 337   EXPECT_EQ(6, Vec.find_last_in(0, 10));
 338   EXPECT_EQ(5, Vec.find_last_in(0, 6));
 339   EXPECT_EQ(154, Vec.find_last_in(100, 155));
 340   EXPECT_EQ(152, Vec.find_last_in(100, 154));
 341   EXPECT_EQ(150, Vec.find_last_in(100, 152));
 342   EXPECT_EQ(-1, Vec.find_last_in(100, 150));
 343   Vec.set(199);
 344   EXPECT_EQ(199, Vec.find_last_in(199, 200));
 345   Vec.reset(199);
 346
 347   // find first unset
 348   EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));
 349   EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));
 350   EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35));
 351
 352   EXPECT_EQ(0, Vec.find_first_unset_in(0, 10));
 353   EXPECT_EQ(1, Vec.find_first_unset_in(1, 10));
 354   EXPECT_EQ(7, Vec.find_first_unset_in(5, 25));
 355   EXPECT_EQ(151, Vec.find_first_unset_in(150, 200));
 356   EXPECT_EQ(151, Vec.find_first_unset_in(151, 200));
 357   EXPECT_EQ(153, Vec.find_first_unset_in(152, 200));
 358   EXPECT_EQ(153, Vec.find_first_unset_in(153, 200));
 359   EXPECT_EQ(155, Vec.find_first_unset_in(154, 200));
 360   EXPECT_EQ(155, Vec.find_first_unset_in(155, 200));
 361   EXPECT_EQ(199, Vec.find_first_unset_in(199, 200));
 362
 363   // find last unset
 364   EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));
 365   EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));
 366   EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35));
 367
 368   EXPECT_EQ(9, Vec.find_last_unset_in(0, 10));
 369   EXPECT_EQ(8, Vec.find_last_unset_in(0, 9));
 370   EXPECT_EQ(2, Vec.find_last_unset_in(0, 7));
 371   EXPECT_EQ(149, Vec.find_last_unset_in(100, 151));
 372   EXPECT_EQ(151, Vec.find_last_unset_in(100, 152));
 373   EXPECT_EQ(151, Vec.find_last_unset_in(100, 153));
 374   EXPECT_EQ(153, Vec.find_last_unset_in(100, 154));
 375   EXPECT_EQ(153, Vec.find_last_unset_in(100, 155));
 376   EXPECT_EQ(155, Vec.find_last_unset_in(100, 156));
 377   EXPECT_EQ(199, Vec.find_last_unset_in(199, 200));
 378 }
 379
 380 TEST(BitVectorTest, FindInRangeSingleWord) {
 381   // When the bit vector contains only a single word, this is slightly different
 382   // than when the bit vector contains multiple words, because masks are applied
 383   // to the front and back of the same word.  So make sure this works.
 384   BitVector Vec;
 385
 386   Vec.resize(25);
 387   Vec.set(2, 4);
 388   Vec.set(6, 9);
 389   Vec.set(12, 15);
 390   Vec.set(19);
 391   Vec.set(21);
 392   Vec.set(23);
 393
 394   // find first
 395   EXPECT_EQ(-1, Vec.find_first_in(0, 0));
 396   EXPECT_EQ(-1, Vec.find_first_in(24, 24));
 397   EXPECT_EQ(-1, Vec.find_first_in(9, 12));
 398
 399   EXPECT_EQ(2, Vec.find_first_in(0, 10));
 400   EXPECT_EQ(6, Vec.find_first_in(4, 10));
 401   EXPECT_EQ(19, Vec.find_first_in(18, 25));
 402   EXPECT_EQ(21, Vec.find_first_in(20, 25));
 403   EXPECT_EQ(23, Vec.find_first_in(22, 25));
 404   EXPECT_EQ(-1, Vec.find_first_in(24, 25));
 405
 406   // find last
 407   EXPECT_EQ(-1, Vec.find_last_in(0, 0));
 408   EXPECT_EQ(-1, Vec.find_last_in(24, 24));
 409   EXPECT_EQ(-1, Vec.find_last_in(9, 12));
 410
 411   EXPECT_EQ(8, Vec.find_last_in(0, 10));
 412   EXPECT_EQ(3, Vec.find_last_in(0, 6));
 413   EXPECT_EQ(23, Vec.find_last_in(18, 25));
 414   EXPECT_EQ(21, Vec.find_last_in(18, 23));
 415   EXPECT_EQ(19, Vec.find_last_in(18, 21));
 416   EXPECT_EQ(-1, Vec.find_last_in(18, 19));
 417
 418   // find first unset
 419   EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));
 420   EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));
 421   EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9));
 422
 423   EXPECT_EQ(0, Vec.find_first_unset_in(0, 6));
 424   EXPECT_EQ(1, Vec.find_first_unset_in(1, 6));
 425   EXPECT_EQ(9, Vec.find_first_unset_in(7, 13));
 426   EXPECT_EQ(18, Vec.find_first_unset_in(18, 25));
 427   EXPECT_EQ(20, Vec.find_first_unset_in(19, 25));
 428   EXPECT_EQ(20, Vec.find_first_unset_in(20, 25));
 429   EXPECT_EQ(22, Vec.find_first_unset_in(21, 25));
 430   EXPECT_EQ(22, Vec.find_first_unset_in(22, 25));
 431   EXPECT_EQ(24, Vec.find_first_unset_in(23, 25));
 432   EXPECT_EQ(24, Vec.find_first_unset_in(24, 25));
 433
 434   // find last unset
 435   EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));
 436   EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));
 437   EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9));
 438
 439   EXPECT_EQ(5, Vec.find_last_unset_in(0, 6));
 440   EXPECT_EQ(4, Vec.find_last_unset_in(0, 5));
 441   EXPECT_EQ(1, Vec.find_last_unset_in(0, 4));
 442   EXPECT_EQ(11, Vec.find_last_unset_in(7, 13));
 443   EXPECT_EQ(24, Vec.find_last_unset_in(18, 25));
 444   EXPECT_EQ(22, Vec.find_last_unset_in(18, 24));
 445   EXPECT_EQ(22, Vec.find_last_unset_in(18, 23));
 446   EXPECT_EQ(20, Vec.find_last_unset_in(18, 22));
 447   EXPECT_EQ(20, Vec.find_last_unset_in(18, 21));
 448   EXPECT_EQ(18, Vec.find_last_unset_in(18, 20));
 449   EXPECT_EQ(18, Vec.find_last_unset_in(18, 19));
 450 }
 451
 452 TYPED_TEST(BitVectorTest, CompoundAssignment) {
 453   TypeParam A;
 454   A.resize(10);
 455   A.set(4);
 456   A.set(7);
 457
 458   TypeParam B;
 459   B.resize(50);
 460   B.set(5);
 461   B.set(18);
 462
 463   A |= B;
 464   EXPECT_TRUE(A.test(4));
 465   EXPECT_TRUE(A.test(5));
 466   EXPECT_TRUE(A.test(7));
 467   EXPECT_TRUE(A.test(18));
 468   EXPECT_EQ(4U, A.count());
 469   EXPECT_EQ(50U, A.size());
 470
 471   B.resize(10);
 472   B.set();
 473   B.reset(2);
 474   B.reset(7);
 475   A &= B;
 476   EXPECT_FALSE(A.test(2));
 477   EXPECT_FALSE(A.test(7));
 478   EXPECT_TRUE(A.test(4));
 479   EXPECT_TRUE(A.test(5));
 480   EXPECT_EQ(2U, A.count());
 481   EXPECT_EQ(50U, A.size());
 482
 483   B.resize(100);
 484   B.set();
 485
 486   A ^= B;
 487   EXPECT_TRUE(A.test(2));
 488   EXPECT_TRUE(A.test(7));
 489   EXPECT_EQ(98U, A.count());
 490   EXPECT_EQ(100U, A.size());
 491 }
 492
 493 // Test SmallBitVector operations with mixed big/small representations
 494 TYPED_TEST(BitVectorTest, MixedBigSmall) {
 495   {
 496     TypeParam Big;
 497     TypeParam Small;
 498
 499     Big.reserve(100);
 500     Big.resize(20);
 501     Small.resize(10);
 502
 503     Small.set(0);
 504     Small.set(1);
 505     Big.set(0);
 506     Big.set(2);
 507     Big.set(16);
 508
 509     Small &= Big;
 510     EXPECT_TRUE(Small.test(0));
 511     EXPECT_EQ(1u, Small.count());
 512     // FIXME BitVector and SmallBitVector behave differently here.
 513     // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())
 514     // but BitVector does not.
 515     // EXPECT_EQ(20u, Small.size());
 516   }
 517
 518   {
 519     TypeParam Big;
 520     TypeParam Small;
 521
 522     Big.reserve(100);
 523     Big.resize(20);
 524     Small.resize(10);
 525
 526     Small.set(0);
 527     Small.set(1);
 528     Big.set(0);
 529     Big.set(2);
 530     Big.set(16);
 531
 532     Big &= Small;
 533     EXPECT_TRUE(Big.test(0));
 534     EXPECT_EQ(1u, Big.count());
 535     // FIXME BitVector and SmallBitVector behave differently here.
 536     // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())
 537     // but BitVector does not.
 538     // EXPECT_EQ(20u, Big.size());
 539   }
 540
 541   {
 542     TypeParam Big;
 543     TypeParam Small;
 544
 545     Big.reserve(100);
 546     Big.resize(20);
 547     Small.resize(10);
 548
 549     Small.set(0);
 550     Small.set(1);
 551     Big.set(0);
 552     Big.set(2);
 553     Big.set(16);
 554
 555     Small |= Big;
 556     EXPECT_TRUE(Small.test(0));
 557     EXPECT_TRUE(Small.test(1));
 558     EXPECT_TRUE(Small.test(2));
 559     EXPECT_TRUE(Small.test(16));
 560     EXPECT_EQ(4u, Small.count());
 561     EXPECT_EQ(20u, Small.size());
 562   }
 563
 564   {
 565     TypeParam Big;
 566     TypeParam Small;
 567
 568     Big.reserve(100);
 569     Big.resize(20);
 570     Small.resize(10);
 571
 572     Small.set(0);
 573     Small.set(1);
 574     Big.set(0);
 575     Big.set(2);
 576     Big.set(16);
 577
 578     Big |= Small;
 579     EXPECT_TRUE(Big.test(0));
 580     EXPECT_TRUE(Big.test(1));
 581     EXPECT_TRUE(Big.test(2));
 582     EXPECT_TRUE(Big.test(16));
 583     EXPECT_EQ(4u, Big.count());
 584     EXPECT_EQ(20u, Big.size());
 585   }
 586
 587   {
 588     TypeParam Big;
 589     TypeParam Small;
 590
 591     Big.reserve(100);
 592     Big.resize(20);
 593     Small.resize(10);
 594
 595     Small.set(0);
 596     Small.set(1);
 597     Big.set(0);
 598     Big.set(2);
 599     Big.set(16);
 600
 601     Small ^= Big;
 602     EXPECT_TRUE(Small.test(1));
 603     EXPECT_TRUE(Small.test(2));
 604     EXPECT_TRUE(Small.test(16));
 605     EXPECT_EQ(3u, Small.count());
 606     EXPECT_EQ(20u, Small.size());
 607   }
 608
 609   {
 610     TypeParam Big;
 611     TypeParam Small;
 612
 613     Big.reserve(100);
 614     Big.resize(20);
 615     Small.resize(10);
 616
 617     Small.set(0);
 618     Small.set(1);
 619     Big.set(0);
 620     Big.set(2);
 621     Big.set(16);
 622
 623     Big ^= Small;
 624     EXPECT_TRUE(Big.test(1));
 625     EXPECT_TRUE(Big.test(2));
 626     EXPECT_TRUE(Big.test(16));
 627     EXPECT_EQ(3u, Big.count());
 628     EXPECT_EQ(20u, Big.size());
 629   }
 630
 631   {
 632     TypeParam Big;
 633     TypeParam Small;
 634
 635     Big.reserve(100);
 636     Big.resize(20);
 637     Small.resize(10);
 638
 639     Small.set(0);
 640     Small.set(1);
 641     Big.set(0);
 642     Big.set(2);
 643     Big.set(16);
 644
 645     Small.reset(Big);
 646     EXPECT_TRUE(Small.test(1));
 647     EXPECT_EQ(1u, Small.count());
 648     EXPECT_EQ(10u, Small.size());
 649   }
 650
 651   {
 652     TypeParam Big;
 653     TypeParam Small;
 654
 655     Big.reserve(100);
 656     Big.resize(20);
 657     Small.resize(10);
 658
 659     Small.set(0);
 660     Small.set(1);
 661     Big.set(0);
 662     Big.set(2);
 663     Big.set(16);
 664
 665     Big.reset(Small);
 666     EXPECT_TRUE(Big.test(2));
 667     EXPECT_TRUE(Big.test(16));
 668     EXPECT_EQ(2u, Big.count());
 669     EXPECT_EQ(20u, Big.size());
 670   }
 671
 672   {
 673     TypeParam Big;
 674     TypeParam Small;
 675
 676     Big.reserve(100);
 677     Big.resize(10);
 678     Small.resize(10);
 679
 680     Small.set(0);
 681     Small.set(1);
 682     Big.set(0);
 683
 684     EXPECT_FALSE(Big == Small);
 685     EXPECT_FALSE(Small == Big);
 686     Big.set(1);
 687     EXPECT_TRUE(Big == Small);
 688     EXPECT_TRUE(Small == Big);
 689   }
 690
 691   {
 692     TypeParam Big;
 693     TypeParam Small;
 694
 695     Big.reserve(100);
 696     Big.resize(20);
 697     Small.resize(10);
 698
 699     Small.set(0);
 700     Big.set(1);
 701
 702     EXPECT_FALSE(Small.anyCommon(Big));
 703     EXPECT_FALSE(Big.anyCommon(Small));
 704     Big.set(0);
 705     EXPECT_TRUE(Small.anyCommon(Big));
 706     EXPECT_TRUE(Big.anyCommon(Small));
 707   }
 708
 709   {
 710     TypeParam Big;
 711     TypeParam Small;
 712
 713     Big.reserve(100);
 714     Big.resize(10);
 715     Small.resize(10);
 716
 717     Small.set(0);
 718     Small.set(1);
 719     Big.set(0);
 720
 721     EXPECT_TRUE(Small.test(Big));
 722     EXPECT_FALSE(Big.test(Small));
 723     Big.set(1);
 724     EXPECT_FALSE(Small.test(Big));
 725     EXPECT_FALSE(Big.test(Small));
 726   }
 727 }
 728
 729 TYPED_TEST(BitVectorTest, ProxyIndex) {
 730   TypeParam Vec(3);
 731   EXPECT_TRUE(Vec.none());
 732   Vec[0] = Vec[1] = Vec[2] = true;
 733   EXPECT_EQ(Vec.size(), Vec.count());
 734   Vec[2] = Vec[1] = Vec[0] = false;
 735   EXPECT_TRUE(Vec.none());
 736 }
 737
 738 TYPED_TEST(BitVectorTest, PortableBitMask) {
 739   TypeParam A;
 740   const uint32_t Mask1[] = { 0x80000000, 6, 5 };
 741
 742   A.resize(10);
 743   A.setBitsInMask(Mask1, 1);
 744   EXPECT_EQ(10u, A.size());
 745   EXPECT_FALSE(A.test(0));
 746
 747   A.resize(32);
 748   A.setBitsInMask(Mask1, 1);
 749   EXPECT_FALSE(A.test(0));
 750   EXPECT_TRUE(A.test(31));
 751   EXPECT_EQ(1u, A.count());
 752
 753   A.resize(33);
 754   A.setBitsInMask(Mask1, 1);
 755   EXPECT_EQ(1u, A.count());
 756   A.setBitsInMask(Mask1, 2);
 757   EXPECT_EQ(1u, A.count());
 758
 759   A.resize(34);
 760   A.setBitsInMask(Mask1, 2);
 761   EXPECT_EQ(2u, A.count());
 762
 763   A.resize(65);
 764   A.setBitsInMask(Mask1, 3);
 765   EXPECT_EQ(4u, A.count());
 766
 767   A.setBitsNotInMask(Mask1, 1);
 768   EXPECT_EQ(32u+3u, A.count());
 769
 770   A.setBitsNotInMask(Mask1, 3);
 771   EXPECT_EQ(65u, A.count());
 772
 773   A.resize(96);
 774   EXPECT_EQ(65u, A.count());
 775
 776   A.clear();
 777   A.resize(128);
 778   A.setBitsNotInMask(Mask1, 3);
 779   EXPECT_EQ(96u-5u, A.count());
 780
 781   A.clearBitsNotInMask(Mask1, 1);
 782   EXPECT_EQ(64-4u, A.count());
 783 }
 784
 785 TYPED_TEST(BitVectorTest, BinOps) {
 786   TypeParam A;
 787   TypeParam B;
 788
 789   A.resize(65);
 790   EXPECT_FALSE(A.anyCommon(B));
 791   EXPECT_FALSE(B.anyCommon(B));
 792
 793   B.resize(64);
 794   A.set(64);
 795   EXPECT_FALSE(A.anyCommon(B));
 796   EXPECT_FALSE(B.anyCommon(A));
 797
 798   B.set(63);
 799   EXPECT_FALSE(A.anyCommon(B));
 800   EXPECT_FALSE(B.anyCommon(A));
 801
 802   A.set(63);
 803   EXPECT_TRUE(A.anyCommon(B));
 804   EXPECT_TRUE(B.anyCommon(A));
 805
 806   B.resize(70);
 807   B.set(64);
 808   B.reset(63);
 809   A.resize(64);
 810   EXPECT_FALSE(A.anyCommon(B));
 811   EXPECT_FALSE(B.anyCommon(A));
 812 }
 813
 814 typedef std::vector<std::pair<int, int>> RangeList;
 815
 816 template <typename VecType>
 817 static inline VecType createBitVector(uint32_t Size,
 818                                       const RangeList &setRanges) {
 819   VecType V;
 820   V.resize(Size);
 821   for (auto &R : setRanges)
 822     V.set(R.first, R.second);
 823   return V;
 824 }
 825
 826 TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) {
 827   // Test that shift ops work when the desired shift amount is less
 828   // than one word.
 829
 830   // 1. Case where the number of bits in the BitVector also fit into a single
 831   // word.
 832   TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}});
 833   TypeParam B = A;
 834
 835   EXPECT_EQ(4U, A.count());
 836   EXPECT_TRUE(A.test(2));
 837   EXPECT_TRUE(A.test(3));
 838   EXPECT_TRUE(A.test(8));
 839   EXPECT_TRUE(A.test(9));
 840
 841   A >>= 1;
 842   EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A);
 843
 844   A <<= 1;
 845   EXPECT_EQ(B, A);
 846
 847   A >>= 10;
 848   EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
 849
 850   A = B;
 851   A <<= 10;
 852   EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
 853
 854   // 2. Case where the number of bits in the BitVector do not fit into a single
 855   // word.
 856
 857   // 31----------------------------------------------------------------------0
 858   // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
 859   A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}});
 860   EXPECT_EQ(40U, A.size());
 861   EXPECT_EQ(22U, A.count());
 862
 863   // 2a. Make sure that left shifting some 1 bits out of the vector works.
 864   //   31----------------------------------------------------------------------0
 865   // Before:
 866   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
 867   // After:
 868   //   XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
 869   A <<= 9;
 870   EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A);
 871
 872   // 2b. Make sure that keeping the number of one bits unchanged works.
 873   //   31----------------------------------------------------------------------0
 874   // Before:
 875   //   XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
 876   // After:
 877   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
 878   A >>= 6;
 879   EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A);
 880
 881   // 2c. Make sure that right shifting some 1 bits out of the vector works.
 882   //   31----------------------------------------------------------------------0
 883   // Before:
 884   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
 885   // After:
 886   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111
 887   A >>= 10;
 888   EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A);
 889
 890   // 3. Big test.
 891   A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
 892   A <<= 29;
 893   EXPECT_EQ(createBitVector<TypeParam>(
 894                 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}),
 895             A);
 896 }
 897
 898 TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) {
 899   // Test that shift ops work when the desired shift amount is greater than or
 900   // equal to the size of a single word.
 901   auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
 902
 903   // Make a copy so we can re-use it later.
 904   auto B = A;
 905
 906   // 1. Shift left by an exact multiple of the word size.  This should invoke
 907   // only a memmove and no per-word bit operations.
 908   A <<= 64;
 909   auto Expected = createBitVector<TypeParam>(
 910       300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}});
 911   EXPECT_EQ(Expected, A);
 912
 913   // 2. Shift left by a non multiple of the word size.  This should invoke both
 914   // a memmove and per-word bit operations.
 915   A = B;
 916   A <<= 93;
 917   EXPECT_EQ(createBitVector<TypeParam>(
 918                 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}),
 919             A);
 920
 921   // 1. Shift right by an exact multiple of the word size.  This should invoke
 922   // only a memmove and no per-word bit operations.
 923   A = B;
 924   A >>= 64;
 925   EXPECT_EQ(
 926       createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A);
 927
 928   // 2. Shift left by a non multiple of the word size.  This should invoke both
 929   // a memmove and per-word bit operations.
 930   A = B;
 931   A >>= 93;
 932   EXPECT_EQ(
 933       createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A);
 934 }
 935
 936 TYPED_TEST(BitVectorTest, RangeOps) {
 937   TypeParam A;
 938   A.resize(256);
 939   A.reset();
 940   A.set(1, 255);
 941
 942   EXPECT_FALSE(A.test(0));
 943   EXPECT_TRUE( A.test(1));
 944   EXPECT_TRUE( A.test(23));
 945   EXPECT_TRUE( A.test(254));
 946   EXPECT_FALSE(A.test(255));
 947
 948   TypeParam B;
 949   B.resize(256);
 950   B.set();
 951   B.reset(1, 255);
 952
 953   EXPECT_TRUE( B.test(0));
 954   EXPECT_FALSE(B.test(1));
 955   EXPECT_FALSE(B.test(23));
 956   EXPECT_FALSE(B.test(254));
 957   EXPECT_TRUE( B.test(255));
 958
 959   TypeParam C;
 960   C.resize(3);
 961   C.reset();
 962   C.set(0, 1);
 963
 964   EXPECT_TRUE(C.test(0));
 965   EXPECT_FALSE( C.test(1));
 966   EXPECT_FALSE( C.test(2));
 967
 968   TypeParam D;
 969   D.resize(3);
 970   D.set();
 971   D.reset(0, 1);
 972
 973   EXPECT_FALSE(D.test(0));
 974   EXPECT_TRUE( D.test(1));
 975   EXPECT_TRUE( D.test(2));
 976
 977   TypeParam E;
 978   E.resize(128);
 979   E.reset();
 980   E.set(1, 33);
 981
 982   EXPECT_FALSE(E.test(0));
 983   EXPECT_TRUE( E.test(1));
 984   EXPECT_TRUE( E.test(32));
 985   EXPECT_FALSE(E.test(33));
 986
 987   TypeParam BufferOverrun;
 988   unsigned size = sizeof(unsigned long) * 8;
 989   BufferOverrun.resize(size);
 990   BufferOverrun.reset(0, size);
 991   BufferOverrun.set(0, size);
 992 }
 993
 994 TYPED_TEST(BitVectorTest, CompoundTestReset) {
 995   TypeParam A(50, true);
 996   TypeParam B(50, false);
 997
 998   TypeParam C(100, true);
 999   TypeParam D(100, false);
1000
1001   EXPECT_FALSE(A.test(A));
1002   EXPECT_TRUE(A.test(B));
1003   EXPECT_FALSE(A.test(C));
1004   EXPECT_TRUE(A.test(D));
1005   EXPECT_FALSE(B.test(A));
1006   EXPECT_FALSE(B.test(B));
1007   EXPECT_FALSE(B.test(C));
1008   EXPECT_FALSE(B.test(D));
1009   EXPECT_TRUE(C.test(A));
1010   EXPECT_TRUE(C.test(B));
1011   EXPECT_FALSE(C.test(C));
1012   EXPECT_TRUE(C.test(D));
1013
1014   A.reset(B);
1015   A.reset(D);
1016   EXPECT_TRUE(A.all());
1017   A.reset(A);
1018   EXPECT_TRUE(A.none());
1019   A.set();
1020   A.reset(C);
1021   EXPECT_TRUE(A.none());
1022   A.set();
1023
1024   C.reset(A);
1025   EXPECT_EQ(50, C.find_first());
1026   C.reset(C);
1027   EXPECT_TRUE(C.none());
1028 }
1029
1030 TYPED_TEST(BitVectorTest, MoveConstructor) {
1031   TypeParam A(10, true);
1032   TypeParam B(std::move(A));
1033   // Check that the move ctor leaves the moved-from object in a valid state.
1034   // The following line used to crash.
1035   A = B;
1036
1037   TypeParam C(10, true);
1038   EXPECT_EQ(C, A);
1039   EXPECT_EQ(C, B);
1040 }
1041
1042 TYPED_TEST(BitVectorTest, MoveAssignment) {
1043   TypeParam A(10, true);
1044   TypeParam B;
1045   B = std::move(A);
1046   // Check that move assignment leaves the moved-from object in a valid state.
1047   // The following line used to crash.
1048   A = B;
1049
1050   TypeParam C(10, true);
1051   EXPECT_EQ(C, A);
1052   EXPECT_EQ(C, B);
1053 }
1054
1055 template<class TypeParam>
1056 static void testEmpty(const TypeParam &A) {
1057   EXPECT_TRUE(A.empty());
1058   EXPECT_EQ((size_t)0, A.size());
1059   EXPECT_EQ((size_t)0, A.count());
1060   EXPECT_FALSE(A.any());
1061   EXPECT_TRUE(A.all());
1062   EXPECT_TRUE(A.none());
1063   EXPECT_EQ(-1, A.find_first());
1064   EXPECT_EQ(A, TypeParam());
1065 }
1066
1067 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0
1068 TYPED_TEST(BitVectorTest, EmptyVector) {
1069   TypeParam A;
1070   testEmpty(A);
1071
1072   TypeParam B;
1073   B.reset();
1074   testEmpty(B);
1075
1076   TypeParam C;
1077   C.clear();
1078   testEmpty(C);
1079
1080   TypeParam D(A);
1081   testEmpty(D);
1082
1083   TypeParam E;
1084   E = A;
1085   testEmpty(E);
1086
1087   TypeParam F;
1088   E.reset(A);
1089   testEmpty(E);
1090 }
1091
1092 TYPED_TEST(BitVectorTest, Iterators) {
1093   TypeParam Filled(10, true);
1094   EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end());
1095   unsigned Counter = 0;
1096   for (unsigned Bit : Filled.set_bits())
1097     EXPECT_EQ(Bit, Counter++);
1098
1099   TypeParam Empty;
1100   EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end());
1101   for (unsigned Bit : Empty.set_bits()) {
1102     (void)Bit;
1103     EXPECT_TRUE(false);
1104   }
1105
1106   TypeParam ToFill(100, false);
1107   ToFill.set(0);
1108   EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end());
1109   EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end());
1110   EXPECT_EQ(*ToFill.set_bits_begin(), 0U);
1111   ToFill.reset(0);
1112   EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end());
1113
1114   const unsigned List[] = {1, 10, 25, 99};
1115   for (unsigned Num : List)
1116     ToFill.set(Num);
1117   unsigned i = 0;
1118   for (unsigned Bit : ToFill.set_bits())
1119     EXPECT_EQ(List[i++], Bit);
1120 }
1121
1122 TYPED_TEST(BitVectorTest, PushBack) {
1123   TypeParam Vec(10, false);
1124   EXPECT_EQ(-1, Vec.find_first());
1125   EXPECT_EQ(10U, Vec.size());
1126   EXPECT_EQ(0U, Vec.count());
1127
1128   Vec.push_back(true);
1129   EXPECT_EQ(10, Vec.find_first());
1130   EXPECT_EQ(11U, Vec.size());
1131   EXPECT_EQ(1U, Vec.count());
1132
1133   Vec.push_back(false);
1134   EXPECT_EQ(10, Vec.find_first());
1135   EXPECT_EQ(12U, Vec.size());
1136   EXPECT_EQ(1U, Vec.count());
1137
1138   Vec.push_back(true);
1139   EXPECT_EQ(10, Vec.find_first());
1140   EXPECT_EQ(13U, Vec.size());
1141   EXPECT_EQ(2U, Vec.count());
1142
1143   // Add a lot of values to cause reallocation.
1144   for (int i = 0; i != 100; ++i) {
1145     Vec.push_back(true);
1146     Vec.push_back(false);
1147   }
1148   EXPECT_EQ(10, Vec.find_first());
1149   EXPECT_EQ(213U, Vec.size());
1150   EXPECT_EQ(102U, Vec.count());
1151 }
1152 }