[llvm][ADT] Enable range-based for loops for `BitVector`

[jansvoboda11]

Summary

LLVM Programmer’s Manual strongly discourages the use of std::vector<bool> and suggests llvm::BitVector as a possible replacement.

Currently, some users of std::vector<bool> cannot switch to llvm::BitVector because it doesn't support range-based for loops. (Note: BitVector currently only provides iterator over set bits.)

To enable easy transition of std::vector<bool> users, this patch implements llvm::BitVector::begin() and llvm::BitVector::end().

Depends on D117115.

[dexonsmith]

Given that BitVector::reference already exists for operator[], might be nice to add iterator as well.

llvm/include/llvm/ADT/BitVector.h

33

It'd probably be easiest to use iterator_facade_base (from ADT/Iterator.h IIRC?). Value type should be const bool here.

163

Maybe this should just be const_iterator?

[dblaikie]

In D117116#3238579, @dexonsmith wrote:

Given that BitVector::reference already exists for operator[], might be nice to add iterator as well.

Yeah, sounds plausible to me.

[jansvoboda11]

In D117116#3238579, @dexonsmith wrote:

Given that BitVector::reference already exists for operator[], might be nice to add iterator as well.

That sounds nice, but there are two pitfalls exposed by non-const iterators.

The first:

void test(BitVector &Bits) {
  for (bool Bit : Bits) Bit = true; // no effect, we have a copy
  for (auto Bit : Bits) Bit = true; // modifies Bits through BitVector::reference
}

The second:

void test(const BitVector &Bits) {
  for (const bool &Bit : Bits) ; // works fine
}
void test(      BitVector &Bits) {
  for (      bool &Bit : Bits) ; // fails to compile, cannot bind non-const lvalue reference to temporary BitVector::reference
}

Is that worth the trouble? Do we have ways to deal with this?

llvm/include/llvm/ADT/BitVector.h

33

Thanks for the pointer to iterator_facade_base.

Its documentation states my iterator should implement const T &operator*() const. However, contents of BitVector are being handed out by value (bool operator[](unsigned) const). Naively returning that from iterator's operator* would return reference to a temporary. I don't see a simple solution/workaround to this with the current iterator_facade_base requirements.

But I think there's a bug in iterator_facade_base's documentation: it should probably say the iterator should implement ReferenceT operator*() const (where ReferenceT = T &) by default.

If we fix this, we could create new BitVector::const_reference type, make it the return type of BitVector::operator[](unsigned) const and explicitly specify it as the ReferenceT for iterator_facade_base. I think there is precedent in LLVM for this.

But looking at the standard, all iterator types except input iterators require the reference type to be a reference type (T &). The iterator at hand should be random access iterator though. Do we care about the standard here?

[dexonsmith]

In D117116#3240612, @jansvoboda11 wrote:

In D117116#3238579, @dexonsmith wrote:

Given that BitVector::reference already exists for operator[], might be nice to add iterator as well.

That sounds nice, but there are two pitfalls exposed by non-const iterators.

for (auto Bit : Bits) Bit = true; // modifies Bits through BitVector::reference

Agreed this would be unexpected.

for (bool &Bit : Bits) ; // fails to compile, cannot bind non-const lvalue reference to temporary BitVector::reference

Not really worried about this. The compiler error teaches you to spell it for (auto &Bit : Bits). And I think the benefit of BitVector::iterator would be more for generic algorithms (like zip_first()) than for a ranged-based for anyway.

I don't feel strongly that iterator should be added... but I also think using BitVector (or a std::vector<bool>) in a range-based for at all is a bit of an odd pattern, so the primary benefit I see of adding iterators at all is enabling parallel iteration/etc (generic algorithms). As long as those work I'm probably fine with these gotchas.

What happens for something like zip_first()/etc. from STLExtras.h?

llvm/include/llvm/ADT/BitVector.h

33

Agreed on the iterator_facade_base documentation bug; it should probably say ReferenceT.

The iterator at hand should be random access iterator though. Do we care about the standard here?

I think the workaround for this is for the iterator to store a bool that gets updated on operator++(); then you can return const bool &.

[jansvoboda11]

Ok, I think for the time being it's more straightforward to remove both uses of iterators: D118111, D118109.

[dexonsmith]

In D117116#3268603, @jansvoboda11 wrote:

Ok, I think for the time being it's more straightforward to remove both uses of iterators: D118111, D118109.

Fair enough!

llvm/include/llvm/ADT/BitVector.h

 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
 #include <initializer_list>
 #include <utility>
 
 namespace llvm {
 
+/// ForwardIterator for all bits.
+/// Iterators get invalidated when resize / reserve is called.
+template <typename BitVectorT> class const_all_bits_iterator_impl {
+  using size_type = typename BitVectorT::size_type;
+
+  const BitVectorT &Parent;
+  size_type Current;
+
+public:
+  const_all_bits_iterator_impl(const BitVectorT &Parent, size_type Current)
+      : Parent(Parent), Current(Current) {}
+  const_all_bits_iterator_impl(const const_all_bits_iterator_impl &) = default;
+
+  const_all_bits_iterator_impl operator++(int) {
+    auto Prev = *this;
+    ++Current;
+    return Prev;
+  }
+
+  const_all_bits_iterator_impl &operator++() {
+    ++Current;
+    return *this;
+  }
+
+  bool operator*() { return Parent[Current]; }
+
+  bool operator==(const const_all_bits_iterator_impl &Other) const {
+    assert(&Parent == &Other.Parent &&
+           "Comparing iterators from different BitVectors");
+    return Current == Other.Current;
+  }
+
+  bool operator!=(const const_all_bits_iterator_impl &Other) const {
+    assert(&Parent == &Other.Parent &&
+           "Comparing iterators from different BitVectors");
+    return Current != Other.Current;
+  }
+};
+
 /// ForwardIterator for the bits that are set.
 /// Iterators get invalidated when resize / reserve is called.
 template <typename BitVectorT> class const_set_bits_iterator_impl {
   const BitVectorT &Parent;
   int Current = 0;
 
   void advance() {
     assert(Current != -1 && "Trying to advance past end.");
reference& operator=(bool t) {
       return *this;
     }
 
     operator bool() const {
       return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
     }
   };
 
+  using const_all_bits_iterator = const_all_bits_iterator_impl<BitVector>;
+
+  const_all_bits_iterator begin() const { return {*this, 0}; }
+  const_all_bits_iterator end() const { return {*this, size()}; }
+
   typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator;
   typedef const_set_bits_iterator set_iterator;
 
   const_set_bits_iterator set_bits_begin() const {
     return const_set_bits_iterator(*this);
   }
   const_set_bits_iterator set_bits_end() const {
     return const_set_bits_iterator(*this, -1);

llvm/include/llvm/ADT/SmallBitVector.h

SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
     RHS.X = 1;
   }
 
   ~SmallBitVector() {
     if (!isSmall())
       delete getPointer();
   }
 
+  using const_all_bits_iterator = const_all_bits_iterator_impl<SmallBitVector>;
+
+  const_all_bits_iterator begin() const { return {*this, 0}; }
+  const_all_bits_iterator end() const { return {*this, size()}; }
+
   using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
   using set_iterator = const_set_bits_iterator;
 
   const_set_bits_iterator set_bits_begin() const {
     return const_set_bits_iterator(*this);
   }
 
   const_set_bits_iterator set_bits_end() const {

llvm/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, EmptyVector) {
   E = A;
   testEmpty(E);
 
   TypeParam F;
   E.reset(A);
   testEmpty(E);
 }
 
-TYPED_TEST(BitVectorTest, Iterators) {
+TYPED_TEST(BitVectorTest, AllBitsIterators) {
+  TypeParam Empty;
+  EXPECT_EQ(Empty.begin(), Empty.end());
+  unsigned BitCount = 0;
+  for (bool Bit : Empty) {
+    (void)Bit;
+    BitCount++;
+  }
+  ASSERT_EQ(BitCount, 0U);
+
+  TypeParam ToFill(100, false);
+  const unsigned List[] = {1, 10, 25, 99};
+  for (unsigned Idx : List)
+    ToFill.set(Idx);
+
+  unsigned Idx = 0;
+  for (bool Bit : ToFill) {
+    ASSERT_TRUE(Bit ? llvm::is_contained(List, Idx)
+                    : !llvm::is_contained(List, Idx));
+    ++Idx;
+  }
+  ASSERT_EQ(Idx, 100U);
+}
+
+TYPED_TEST(BitVectorTest, SetBitsIterators) {
   TypeParam Filled(10, true);
   EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end());
   unsigned Counter = 0;
   for (unsigned Bit : Filled.set_bits())
     EXPECT_EQ(Bit, Counter++);
 
   TypeParam Empty;
   EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end());