Make iterators of BitVector easier to use by inheriting iterator_facade_base

[jdh8]

Summary

This change is needed to apply generic algorithmic functions (like in
STLExtras.h) to the result of SmallBitVector::set_bits

[dblaikie]

llvm/include/llvm/ADT/BitVector.h

36

Looks like this isn't a forward iterator - it's an input iterator.

A forward iterator requires:

"The type std::iterator_traits<It>::reference must be exactly
T& if It satisfies LegacyOutputIterator (It is mutable)
const T& otherwise (It is constant),"

And that the return type of "op*" is referenec.

Since the return type of op* is unsigned, this could be an input iterator.

Or, I guess, the return type could be changed, since there is ongoing storage for the value (so long as the iterator isn't incremented - but that gets complicated with reverse iterators... ).

[thegameg]

I had an attempt here: https://reviews.llvm.org/D33419, I think similar concerns came up in that review.

[jdh8]

Indeed it is not a forward iterator because it is bound to no object. I am changing it to an input iterator.

[jdh8]

BitVector's iterator should be an input iterator instead of a forward iterator
because it is bound to no unsigned object

[dblaikie]

In D84690#2177066, @thegameg wrote:

I had an attempt here: https://reviews.llvm.org/D33419, I think similar concerns came up in that review.

Indeed, sorry that fell through & I didn't understand enough about iterators to instead suggest falling back to an input iterator instead of figuring out how to fit the semantics of the forward iterator. Perhaps after this is committed you could resurrect your original patch to remove the op!= and maybe add the extra checks you were proposing to the facade?

In D84690#2177876, @jdh8 wrote:

BitVector's iterator should be an input iterator instead of a forward iterator
because it is bound to no unsigned object

Great, thanks!

[thegameg]

In D84690#2179205, @dblaikie wrote:

Indeed, sorry that fell through & I didn't understand enough about iterators to instead suggest falling back to an input iterator instead of figuring out how to fit the semantics of the forward iterator.

No worries, I was quite confused as well there. Thanks for figuring this stuff out!

llvm/include/llvm/ADT/BitVector.h

 #include <cstdlib>
 #include <cstring>
 #include <utility>
 
 namespace llvm {
 
 /// ForwardIterator for the bits that are set.
 /// Iterators get invalidated when resize / reserve is called.
-template <typename BitVectorT> class const_set_bits_iterator_impl {
+template <typename BitVectorT>
+class const_set_bits_iterator_impl
+    : public iterator_facade_base<const_set_bits_iterator_impl<BitVectorT>,
+                                  std::input_iterator_tag, unsigned,
+                                  std::ptrdiff_t, const unsigned *, unsigned> {
   const BitVectorT &Parent;
   int Current = 0;
 
   void advance() {
     assert(Current != -1 && "Trying to advance past end.");
     Current = Parent.find_next(Current);
   }
 
 public:
   const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
       : Parent(Parent), Current(Current) {}
   explicit const_set_bits_iterator_impl(const BitVectorT &Parent)
       : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
-  const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default;
 
   const_set_bits_iterator_impl operator++(int) {
     auto Prev = *this;
     advance();
     return Prev;
   }
 
   const_set_bits_iterator_impl &operator++() {