1 //=== CoalescingBitVectorTest.cpp - CoalescingBitVector unit 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/CoalescingBitVector.h"
10 #include "gtest/gtest.h"
11 
12 using namespace llvm;
13 
14 namespace {
15 
16 using UBitVec = CoalescingBitVector<unsigned>;
17 using U64BitVec = CoalescingBitVector<uint64_t>;
18 
19 bool elementsMatch(const UBitVec &BV, std::initializer_list<unsigned> List) {
20   if (!std::equal(BV.begin(), BV.end(), List.begin(), List.end())) {
21     UBitVec::Allocator Alloc;
22     UBitVec Expected(Alloc);
23     Expected.set(List);
24     dbgs() << "elementsMatch:\n"
25            << "     Expected: ";
26     Expected.print(dbgs());
27     dbgs() << "          Got: ";
28     BV.print(dbgs());
29     return false;
30   }
31   return true;
32 }
33 
34 TEST(CoalescingBitVectorTest, Set) {
35   UBitVec::Allocator Alloc;
36   UBitVec BV1(Alloc);
37   UBitVec BV2(Alloc);
38 
39   BV1.set(0);
40   EXPECT_TRUE(BV1.test(0));
41   EXPECT_FALSE(BV1.test(1));
42 
43   BV2.set(BV1);
44   EXPECT_TRUE(BV2.test(0));
45 }
46 
47 TEST(CoalescingBitVectorTest, Count) {
48   UBitVec::Allocator Alloc;
49   UBitVec BV(Alloc);
50   EXPECT_EQ(BV.count(), 0u);
51   BV.set(0);
52   EXPECT_EQ(BV.count(), 1u);
53   BV.set({11, 12, 13, 14, 15});
54   EXPECT_EQ(BV.count(), 6u);
55 }
56 
57 TEST(CoalescingBitVectorTest, ClearAndEmpty) {
58   UBitVec::Allocator Alloc;
59   UBitVec BV(Alloc);
60   EXPECT_TRUE(BV.empty());
61   BV.set(1);
62   EXPECT_FALSE(BV.empty());
63   BV.clear();
64   EXPECT_TRUE(BV.empty());
65 }
66 
67 TEST(CoalescingBitVector, Copy) {
68   UBitVec::Allocator Alloc;
69   UBitVec BV1(Alloc);
70   BV1.set(0);
71   UBitVec BV2 = BV1;
72   EXPECT_TRUE(elementsMatch(BV1, {0}));
73   EXPECT_TRUE(elementsMatch(BV2, {0}));
74   BV2.set(5);
75   BV2 = BV1;
76   EXPECT_TRUE(elementsMatch(BV1, {0}));
77   EXPECT_TRUE(elementsMatch(BV2, {0}));
78 }
79 
80 TEST(CoalescingBitVector, Move) {
81   UBitVec::Allocator Alloc;
82   UBitVec BV1(Alloc);
83   BV1.set(0);
84   UBitVec BV2 = std::move(BV1);
85   EXPECT_TRUE(elementsMatch(BV2, {0}));
86   BV2.set(5);
87   BV1 = std::move(BV2);
88   EXPECT_TRUE(elementsMatch(BV1, {0, 5}));
89 }
90 
91 TEST(CoalescingBitVectorTest, Iterators) {
92   UBitVec::Allocator Alloc;
93   UBitVec BV(Alloc);
94 
95   BV.set({0, 1, 2});
96 
97   auto It = BV.begin();
98   EXPECT_TRUE(It == BV.begin());
99   EXPECT_EQ(*It, 0u);
100   ++It;
101   EXPECT_EQ(*It, 1u);
102   ++It;
103   EXPECT_EQ(*It, 2u);
104   ++It;
105   EXPECT_TRUE(It == BV.end());
106   EXPECT_TRUE(BV.end() == BV.end());
107 
108   It = BV.begin();
109   EXPECT_TRUE(It == BV.begin());
110   auto ItCopy = It++;
111   EXPECT_TRUE(ItCopy == BV.begin());
112   EXPECT_EQ(*ItCopy, 0u);
113   EXPECT_EQ(*It, 1u);
114 
115   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2}));
116 
117   BV.set({4, 5, 6});
118   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6}));
119 
120   BV.set(3);
121   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6}));
122 
123   BV.set(10);
124   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6, 10}));
125 
126   // Should be able to reset unset bits.
127   BV.reset(3);
128   BV.reset(3);
129   BV.reset(20000);
130   BV.set({1000, 1001, 1002});
131   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6, 10, 1000, 1001, 1002}));
132 
133   auto It1 = BV.begin();
134   EXPECT_TRUE(It1 == BV.begin());
135   EXPECT_TRUE(++It1 == ++BV.begin());
136   EXPECT_TRUE(It1 != BV.begin());
137   EXPECT_TRUE(It1 != BV.end());
138 }
139 
140 TEST(CoalescingBitVectorTest, Reset) {
141   UBitVec::Allocator Alloc;
142   UBitVec BV(Alloc);
143 
144   BV.set(0);
145   EXPECT_TRUE(BV.test(0));
146   BV.reset(0);
147   EXPECT_FALSE(BV.test(0));
148 
149   BV.clear();
150   BV.set({1, 2, 3});
151   BV.reset(1);
152   EXPECT_TRUE(elementsMatch(BV, {2, 3}));
153 
154   BV.clear();
155   BV.set({1, 2, 3});
156   BV.reset(2);
157   EXPECT_TRUE(elementsMatch(BV, {1, 3}));
158 
159   BV.clear();
160   BV.set({1, 2, 3});
161   BV.reset(3);
162   EXPECT_TRUE(elementsMatch(BV, {1, 2}));
163 }
164 
165 TEST(CoalescingBitVectorTest, Comparison) {
166   UBitVec::Allocator Alloc;
167   UBitVec BV1(Alloc);
168   UBitVec BV2(Alloc);
169 
170   // Single interval.
171   BV1.set({1, 2, 3});
172   BV2.set({1, 2, 3});
173   EXPECT_EQ(BV1, BV2);
174   EXPECT_FALSE(BV1 != BV2);
175 
176   // Different number of intervals.
177   BV1.clear();
178   BV2.clear();
179   BV1.set({1, 2, 3});
180   EXPECT_NE(BV1, BV2);
181 
182   // Multiple intervals.
183   BV1.clear();
184   BV2.clear();
185   BV1.set({1, 2, 11, 12});
186   BV2.set({1, 2, 11, 12});
187   EXPECT_EQ(BV1, BV2);
188   BV2.reset(1);
189   EXPECT_NE(BV1, BV2);
190   BV2.set(1);
191   BV2.reset(11);
192   EXPECT_NE(BV1, BV2);
193 }
194 
195 // A simple implementation of set union, used to double-check the human
196 // "expected" answer.
197 UBitVec simpleUnion(UBitVec::Allocator &Alloc, const UBitVec &LHS,
198                     const UBitVec &RHS) {
199   UBitVec Union(Alloc);
200   for (unsigned Bit : LHS)
201     Union.test_and_set(Bit);
202   for (unsigned Bit : RHS)
203     Union.test_and_set(Bit);
204   return Union;
205 }
206 
207 TEST(CoalescingBitVectorTest, Union) {
208   UBitVec::Allocator Alloc;
209 
210   // Check that after doing LHS |= RHS, LHS == Expected.
211   auto unionIs = [&](std::initializer_list<unsigned> LHS,
212                      std::initializer_list<unsigned> RHS,
213                      std::initializer_list<unsigned> Expected) {
214     UBitVec BV1(Alloc);
215     BV1.set(LHS);
216     UBitVec BV2(Alloc);
217     BV2.set(RHS);
218     const UBitVec &DoubleCheckedExpected = simpleUnion(Alloc, BV1, BV2);
219     ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
220     BV1 |= BV2;
221     ASSERT_TRUE(elementsMatch(BV1, Expected));
222   };
223 
224   // Check that "LHS |= RHS" and "RHS |= LHS" both produce the expected result.
225   auto testUnionSymmetrically = [&](std::initializer_list<unsigned> LHS,
226                      std::initializer_list<unsigned> RHS,
227                      std::initializer_list<unsigned> Expected) {
228     unionIs(LHS, RHS, Expected);
229     unionIs(RHS, LHS, Expected);
230   };
231 
232   // Empty LHS.
233   testUnionSymmetrically({}, {1, 2, 3}, {1, 2, 3});
234 
235   // Empty RHS.
236   testUnionSymmetrically({1, 2, 3}, {}, {1, 2, 3});
237 
238   // Full overlap.
239   testUnionSymmetrically({1}, {1}, {1});
240   testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12});
241 
242   // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
243   // it. Repeat this swapping LHS and RHS.
244   testUnionSymmetrically({2, 3, 4}, {1, 2, 3}, {1, 2, 3, 4});
245   testUnionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
246   testUnionSymmetrically({2, 3, 4}, {3, 4, 5}, {2, 3, 4, 5});
247   testUnionSymmetrically({1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4});
248   testUnionSymmetrically({3, 4, 5}, {2, 3, 4}, {2, 3, 4, 5});
249 
250   // Multiple overlaps, but at least one of the overlaps forces us to split an
251   // interval (and possibly both do). For ease of understanding, fix LHS to be
252   // {1, 2, 11, 12}, but vary RHS.
253   testUnionSymmetrically({1, 2, 11, 12}, {1}, {1, 2, 11, 12});
254   testUnionSymmetrically({1, 2, 11, 12}, {2}, {1, 2, 11, 12});
255   testUnionSymmetrically({1, 2, 11, 12}, {11}, {1, 2, 11, 12});
256   testUnionSymmetrically({1, 2, 11, 12}, {12}, {1, 2, 11, 12});
257   testUnionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 2, 11, 12});
258   testUnionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 2, 11, 12});
259   testUnionSymmetrically({1, 2, 11, 12}, {2, 11}, {1, 2, 11, 12});
260   testUnionSymmetrically({1, 2, 11, 12}, {2, 12}, {1, 2, 11, 12});
261   testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11, 12});
262   testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 11, 12});
263   testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 2, 11, 12});
264   testUnionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {1, 2, 11, 12});
265   testUnionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {0, 1, 2, 11, 12});
266   testUnionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {1, 2, 3, 11, 12});
267   testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 2, 11, 12, 13});
268   testUnionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 2, 10, 11, 12});
269 
270   // Partial overlap, but the existing interval covers future overlaps.
271   testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
272                          {1, 2, 3, 4, 5, 6, 7, 8});
273   testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 7, 8, 9},
274                          {1, 2, 3, 4, 5, 6, 7, 8, 9});
275 
276   // More partial overlaps.
277   testUnionSymmetrically({1, 2, 3, 4, 5}, {0, 1, 2, 4, 5, 6},
278                          {0, 1, 2, 3, 4, 5, 6});
279   testUnionSymmetrically({2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4});
280   testUnionSymmetrically({3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4});
281   testUnionSymmetrically({1, 2}, {1, 2, 3, 4}, {1, 2, 3, 4});
282   testUnionSymmetrically({0, 1}, {1, 2, 3, 4}, {0, 1, 2, 3, 4});
283 
284   // Merge non-overlapping.
285   testUnionSymmetrically({0, 1}, {2, 3}, {0, 1, 2, 3});
286   testUnionSymmetrically({0, 3}, {1, 2}, {0, 1, 2, 3});
287 }
288 
289 // A simple implementation of set intersection, used to double-check the
290 // human "expected" answer.
291 UBitVec simpleIntersection(UBitVec::Allocator &Alloc, const UBitVec &LHS,
292                            const UBitVec &RHS) {
293   UBitVec Intersection(Alloc);
294   for (unsigned Bit : LHS)
295     if (RHS.test(Bit))
296       Intersection.set(Bit);
297   return Intersection;
298 }
299 
300 TEST(CoalescingBitVectorTest, Intersection) {
301   UBitVec::Allocator Alloc;
302 
303   // Check that after doing LHS &= RHS, LHS == Expected.
304   auto intersectionIs = [&](std::initializer_list<unsigned> LHS,
305                             std::initializer_list<unsigned> RHS,
306                             std::initializer_list<unsigned> Expected) {
307     UBitVec BV1(Alloc);
308     BV1.set(LHS);
309     UBitVec BV2(Alloc);
310     BV2.set(RHS);
311     const UBitVec &DoubleCheckedExpected = simpleIntersection(Alloc, BV1, BV2);
312     ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
313     BV1 &= BV2;
314     ASSERT_TRUE(elementsMatch(BV1, Expected));
315   };
316 
317   // Check that "LHS &= RHS" and "RHS &= LHS" both produce the expected result.
318   auto testIntersectionSymmetrically = [&](std::initializer_list<unsigned> LHS,
319                      std::initializer_list<unsigned> RHS,
320                      std::initializer_list<unsigned> Expected) {
321     intersectionIs(LHS, RHS, Expected);
322     intersectionIs(RHS, LHS, Expected);
323   };
324 
325   // Empty case, one-element case.
326   testIntersectionSymmetrically({}, {}, {});
327   testIntersectionSymmetrically({1}, {1}, {1});
328   testIntersectionSymmetrically({1}, {2}, {});
329 
330   // Exact overlaps cases: single overlap and multiple overlaps.
331   testIntersectionSymmetrically({1, 2}, {1, 2}, {1, 2});
332   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12});
333 
334   // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
335   // it.
336   testIntersectionSymmetrically({2, 3, 4}, {1, 2, 3}, {2, 3});
337   testIntersectionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
338   testIntersectionSymmetrically({2, 3, 4}, {3, 4, 5}, {3, 4});
339 
340   // No overlap, but we have multiple intervals.
341   testIntersectionSymmetrically({1, 2, 11, 12}, {3, 4, 13, 14}, {});
342 
343   // Multiple overlaps, but at least one of the overlaps forces us to split an
344   // interval (and possibly both do). For ease of understanding, fix LHS to be
345   // {1, 2, 11, 12}, but vary RHS.
346   testIntersectionSymmetrically({1, 2, 11, 12}, {1}, {1});
347   testIntersectionSymmetrically({1, 2, 11, 12}, {2}, {2});
348   testIntersectionSymmetrically({1, 2, 11, 12}, {11}, {11});
349   testIntersectionSymmetrically({1, 2, 11, 12}, {12}, {12});
350   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 11});
351   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 12});
352   testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11}, {2, 11});
353   testIntersectionSymmetrically({1, 2, 11, 12}, {2, 12}, {2, 12});
354   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11});
355   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 12});
356   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 11, 12});
357   testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {2, 11, 12});
358   testIntersectionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {11, 12});
359   testIntersectionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {11, 12});
360   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 11});
361   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 11});
362 
363   // Partial overlap, but the existing interval covers future overlaps.
364   testIntersectionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
365                                 {2, 3, 4, 6, 7});
366 }
367 
368 // A simple implementation of set intersection-with-complement, used to
369 // double-check the human "expected" answer.
370 UBitVec simpleIntersectionWithComplement(UBitVec::Allocator &Alloc,
371                                          const UBitVec &LHS,
372                                          const UBitVec &RHS) {
373   UBitVec Intersection(Alloc);
374   for (unsigned Bit : LHS)
375     if (!RHS.test(Bit))
376       Intersection.set(Bit);
377   return Intersection;
378 }
379 
380 TEST(CoalescingBitVectorTest, IntersectWithComplement) {
381   UBitVec::Allocator Alloc;
382 
383   // Check that after doing LHS.intersectWithComplement(RHS), LHS == Expected.
384   auto intersectionWithComplementIs =
385       [&](std::initializer_list<unsigned> LHS,
386           std::initializer_list<unsigned> RHS,
387           std::initializer_list<unsigned> Expected) {
388         UBitVec BV1(Alloc);
389         BV1.set(LHS);
390         UBitVec BV2(Alloc);
391         BV2.set(RHS);
392         const UBitVec &DoubleCheckedExpected =
393             simpleIntersectionWithComplement(Alloc, BV1, BV2);
394         ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
395         BV1.intersectWithComplement(BV2);
396         ASSERT_TRUE(elementsMatch(BV1, Expected));
397       };
398 
399   // Empty case, one-element case.
400   intersectionWithComplementIs({}, {}, {});
401   intersectionWithComplementIs({1}, {1}, {});
402   intersectionWithComplementIs({1}, {2}, {1});
403 
404   // Exact overlaps cases: single overlap and multiple overlaps.
405   intersectionWithComplementIs({1, 2}, {1, 2}, {});
406   intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11, 12}, {});
407 
408   // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
409   // it. Repeat this swapping LHS and RHS.
410   intersectionWithComplementIs({2, 3, 4}, {1, 2, 3}, {4});
411   intersectionWithComplementIs({2, 3, 4}, {2, 3, 4}, {});
412   intersectionWithComplementIs({2, 3, 4}, {3, 4, 5}, {2});
413   intersectionWithComplementIs({1, 2, 3}, {2, 3, 4}, {1});
414   intersectionWithComplementIs({3, 4, 5}, {2, 3, 4}, {5});
415 
416   // No overlap, but we have multiple intervals.
417   intersectionWithComplementIs({1, 2, 11, 12}, {3, 4, 13, 14}, {1, 2, 11, 12});
418 
419   // Multiple overlaps. For ease of understanding, fix LHS to be
420   // {1, 2, 11, 12}, but vary RHS.
421   intersectionWithComplementIs({1, 2, 11, 12}, {1}, {2, 11, 12});
422   intersectionWithComplementIs({1, 2, 11, 12}, {2}, {1, 11, 12});
423   intersectionWithComplementIs({1, 2, 11, 12}, {11}, {1, 2, 12});
424   intersectionWithComplementIs({1, 2, 11, 12}, {12}, {1, 2, 11});
425   intersectionWithComplementIs({1, 2, 11, 12}, {1, 11}, {2, 12});
426   intersectionWithComplementIs({1, 2, 11, 12}, {1, 12}, {2, 11});
427   intersectionWithComplementIs({1, 2, 11, 12}, {2, 11}, {1, 12});
428   intersectionWithComplementIs({1, 2, 11, 12}, {2, 12}, {1, 11});
429   intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11}, {12});
430   intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 12}, {11});
431   intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 12}, {2});
432   intersectionWithComplementIs({1, 2, 11, 12}, {2, 11, 12}, {1});
433   intersectionWithComplementIs({1, 2, 11, 12}, {0, 11, 12}, {1, 2});
434   intersectionWithComplementIs({1, 2, 11, 12}, {3, 11, 12}, {1, 2});
435   intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 13}, {2, 12});
436   intersectionWithComplementIs({1, 2, 11, 12}, {1, 10, 11}, {2, 12});
437 
438   // Partial overlap, but the existing interval covers future overlaps.
439   intersectionWithComplementIs({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
440                                {1, 5, 8});
441 }
442 
443 TEST(CoalescingBitVectorTest, FindLowerBound) {
444   U64BitVec::Allocator Alloc;
445   U64BitVec BV(Alloc);
446   uint64_t BigNum1 = uint64_t(1) << 32;
447   uint64_t BigNum2 = (uint64_t(1) << 33) + 1;
448   EXPECT_TRUE(BV.find(BigNum1) == BV.end());
449   BV.set(BigNum1);
450   auto Find1 = BV.find(BigNum1);
451   EXPECT_EQ(*Find1, BigNum1);
452   BV.set(BigNum2);
453   auto Find2 = BV.find(BigNum1);
454   EXPECT_EQ(*Find2, BigNum1);
455   auto Find3 = BV.find(BigNum2);
456   EXPECT_EQ(*Find3, BigNum2);
457   BV.reset(BigNum1);
458   auto Find4 = BV.find(BigNum1);
459   EXPECT_EQ(*Find4, BigNum2);
460 
461   BV.clear();
462   BV.set({1, 2, 3});
463   EXPECT_EQ(*BV.find(2), 2u);
464   EXPECT_EQ(*BV.find(3), 3u);
465 }
466 
467 TEST(CoalescingBitVectorTest, Print) {
468   std::string S;
469   {
470     raw_string_ostream OS(S);
471     UBitVec::Allocator Alloc;
472     UBitVec BV(Alloc);
473     BV.set({1});
474     BV.print(OS);
475 
476     BV.clear();
477     BV.set({1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20});
478     BV.print(OS);
479   }
480   EXPECT_EQ(S, "{[1]}"
481                "{[1][11, 20]}");
482 }
483 
484 } // namespace
485