Fix iterator_adaptor_base/enumerator_iter to allow composition of llvm::enumerate with llvm::make_filter_range

[mehdi_amini]

llvm/unittests/ADT/IteratorTest.cpp

186

(This is to fail to compile)

186

(I meant: this used to fail to compile)

[rriddle]

Can you update the description with information on what this is fixing?

[mehdi_amini]

Can you update the description with information on what this is fixing?

I am not sure how to phrase this, the first error was:

/llvm/include/llvm/ADT/iterator.h:299:41: error: binding reference of type 'result_pair<...>' to value of type 'const result_pair<...>' drops 'const' qualifier
  ReferenceT operator*() const { return *I; }
                                        ^~
llvm/unittests/ADT/IteratorTest.cpp:186:26: note: in instantiation of member function 'llvm::iterator_adaptor_base<llvm::filter_iterator_base<llvm::detail::enumerator_iter<int (&)[7]>, (lambda at llvm/unittests/ADT/IteratorTest.cpp:182:16), std::forward_iterator_tag>, llvm::detail::enumerator_iter<int (&)[7]>, std::forward_iterator_tag, llvm::detail::result_pair<int (&)[7]>, long, int *, llvm::detail::result_pair<int (&)[7]> &>::operator*' requested here
  for (auto IndexedValue : make_filter_range(Enumerate, IsOdd))
                         ^

The fix in STLExtra is for:

llvm/unittests/ADT/IteratorTest.cpp:187:34: error: member reference base type 'int' is not a structure or union
    Actual.push_back(IndexedValue.value());
                     ~~~~~~~~~~~~^~~~~~
In file included from llvm/unittests/ADT/IteratorTest.cpp:10:
llvm/include/llvm/ADT/iterator.h:300:35: error: non-const lvalue reference to type 'int' cannot bind to a value of unrelated type 'llvm::detail::enumerator_iter<int (&)[7]>::result_type' (aka 'result_pair<int (&)[7]>')
  ReferenceT operator*() { return *I; }
                                  ^~
llvm/unittests/ADT/IteratorTest.cpp:186:26: note: in instantiation of member function 'llvm::iterator_adaptor_base<llvm::filter_iterator_base<llvm::detail::enumerator_iter<int (&)[7]>, (lambda at llvm/unittests/ADT/IteratorTest.cpp:182:16), std::forward_iterator_tag>, llvm::detail::enumerator_iter<int (&)[7]>, std::forward_iterator_tag, llvm::detail::result_pair<int (&)[7]>, long, int *, int &>::operator*' requested here
  for (auto IndexedValue : make_filter_range(Enumerate, IsOdd))
                         ^

[rriddle]

In D112981#3101944, @mehdi_amini wrote:

Can you update the description with information on what this is fixing?

I am not sure how to phrase this, the first error was:

/llvm/include/llvm/ADT/iterator.h:299:41: error: binding reference of type 'result_pair<...>' to value of type 'const result_pair<...>' drops 'const' qualifier
  ReferenceT operator*() const { return *I; }
                                        ^~
llvm/unittests/ADT/IteratorTest.cpp:186:26: note: in instantiation of member function 'llvm::iterator_adaptor_base<llvm::filter_iterator_base<llvm::detail::enumerator_iter<int (&)[7]>, (lambda at llvm/unittests/ADT/IteratorTest.cpp:182:16), std::forward_iterator_tag>, llvm::detail::enumerator_iter<int (&)[7]>, std::forward_iterator_tag, llvm::detail::result_pair<int (&)[7]>, long, int *, llvm::detail::result_pair<int (&)[7]> &>::operator*' requested here
  for (auto IndexedValue : make_filter_range(Enumerate, IsOdd))
                         ^

The fix in STLExtra is for:

llvm/unittests/ADT/IteratorTest.cpp:187:34: error: member reference base type 'int' is not a structure or union
    Actual.push_back(IndexedValue.value());
                     ~~~~~~~~~~~~^~~~~~
In file included from llvm/unittests/ADT/IteratorTest.cpp:10:
llvm/include/llvm/ADT/iterator.h:300:35: error: non-const lvalue reference to type 'int' cannot bind to a value of unrelated type 'llvm::detail::enumerator_iter<int (&)[7]>::result_type' (aka 'result_pair<int (&)[7]>')
  ReferenceT operator*() { return *I; }
                                  ^~
llvm/unittests/ADT/IteratorTest.cpp:186:26: note: in instantiation of member function 'llvm::iterator_adaptor_base<llvm::filter_iterator_base<llvm::detail::enumerator_iter<int (&)[7]>, (lambda at llvm/unittests/ADT/IteratorTest.cpp:182:16), std::forward_iterator_tag>, llvm::detail::enumerator_iter<int (&)[7]>, std::forward_iterator_tag, llvm::detail::result_pair<int (&)[7]>, long, int *, int &>::operator*' requested here
  for (auto IndexedValue : make_filter_range(Enumerate, IsOdd))
                         ^

It was more of a passing comment, but something as simple as:

* Properly specify reference type in enumerator_iter
* Fix constness of iterator_adaptor_base::operator*

[dexonsmith]

This doesn't look correct to me.

Here are two examples that I think this patch breaks:

// Setup: simple wrappers around `int *` and `const int *`.
struct const_iterator : public iterator_adaptor_base<const_iterator, const int *> {};
struct iterator : public iterator_adaptor_base<iterator, int *> {};

// `const`-qualified iterators (wrapping `int *const` and `const int *const`).
const int &ConstRef = *std::declval<const const_iterator &>(); // (example #1)
int &Ref = *std::declval<const iterator &>(); // (example #2)

The const-qualification on iterator_adaptor_base should not affect the reference value:

• non-const iterator: int * (dereferencing returns int &)
• non-const iterator with const: int *const (dereferencing returns int &)
• const iterator: const int * (dereferencing returns const int &)
• const iterator with const: const int *const (dereferencing returns const int &)

I think I found the actual bug; see my inline comments.

llvm/include/llvm/ADT/STLExtras.h

1920–1921

This is the actual bug. The const-ness of the iterator shouldn't affect the const-ness of the returned value.

The non-const operator*() should be deleted and only a const result_type& should ever be returned. The caller should never be allowed to modify Result.Iter or Result.Index.

llvm/include/llvm/ADT/iterator.h

299–300

If you used std::add_const_t<ReferenceT> then I think (1) would start compiling again but (2) would still fail.

I think this code change would "fix" the problem you encountered:

ReferenceT operator*() const { return *const_cast<WrappedIteratorT &>(I); }

... but I think the actual bug is in the WrappedIteratorT.

[dexonsmith]

In D112981#3107398, @dexonsmith wrote:

Here are two examples that I think this patch breaks:

const int &ConstRef = *std::declval<const const_iterator &>(); // (example #1)
int &Ref = *std::declval<const iterator &>(); // (example #2)

I was wrong that these would fail, but the reason seems a bit subtle: it appears that const ReferenceT is the same as int& when ReferenceT is int&.

I didn't see the revert here, and wrote https://reviews.llvm.org/D113158 to go on top. There were a few other problems to work through. Happy to rebase that if it makes sense.

[mehdi_amini]

Ah if you can rebase then that'd be great :)

llvm/include/llvm/ADT/STLExtras.h

private:
   IterOfRange<R> Iter;
 };
 
 template <typename R>
 class enumerator_iter
     : public iterator_facade_base<
           enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
           typename std::iterator_traits<IterOfRange<R>>::difference_type,
-          typename std::iterator_traits<IterOfRange<R>>::pointer,
-          typename std::iterator_traits<IterOfRange<R>>::reference> {
+          typename std::iterator_traits<IterOfRange<R>>::pointer> {
   using result_type = result_pair<R>;
 
 public:
   explicit enumerator_iter(IterOfRange<R> EndIter)
       : Result(std::numeric_limits<size_t>::max(), EndIter) {}
 
   enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
       : Result(Index, Iter) {}
 
   result_type &operator*() { return Result; }
   const result_type &operator*() const { return Result; }
 
   enumerator_iter &operator++() {
     assert(Result.Index != std::numeric_limits<size_t>::max());
     ++Result.Iter;
     ++Result.Index;
     return *this;
   }
 

llvm/include/llvm/ADT/iterator.h

public:
   friend bool operator<(const iterator_adaptor_base &LHS,
                         const iterator_adaptor_base &RHS) {
     static_assert(
         BaseT::IsRandomAccess,
         "Relational operators are only defined for random access iterators.");
     return LHS.I < RHS.I;
   }
 
-  ReferenceT operator*() const { return *I; }
+  const ReferenceT operator*() const { return *I; }
+  ReferenceT operator*() { return *I; }
 };
 
 /// An iterator type that allows iterating over the pointees via some
 /// other iterator.
 ///
 /// The typical usage of this is to expose a type that iterates over Ts, but
 /// which is implemented with some iterator over T*s:
 ///

llvm/unittests/ADT/IteratorTest.cpp

 TEST(FilterIteratorTest, Lambda) {
   auto IsOdd = [](int N) { return N % 2 == 1; };
   int A[] = {0, 1, 2, 3, 4, 5, 6};
   auto Range = make_filter_range(A, IsOdd);
   SmallVector<int, 3> Actual(Range.begin(), Range.end());
   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
 }
 
+TEST(FilterIteratorTest, Enumerate) {
+  auto IsOdd = [](auto N) { return N.value() % 2 == 1; };
+  int A[] = {0, 1, 2, 3, 4, 5, 6};
+  auto Enumerate = llvm::enumerate(A);
+  SmallVector<int> Actual;
+  for (auto IndexedValue : make_filter_range(Enumerate, IsOdd))
+    Actual.push_back(IndexedValue.value());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
+}
+
 TEST(FilterIteratorTest, CallableObject) {
   int Counter = 0;
   struct Callable {
     int &Counter;
 
     Callable(int &Counter) : Counter(Counter) {}
 
     bool operator()(int N) {