ADT: Fix const-correctness of iterator adaptors

[dexonsmith]

Summary

This fixes const-correctness of iterator adaptors, dropping non-const
overloads for operator*().

Iterators, like the pointers that they generalize, have two types of
const.

The const qualifier on members indicates whether the iterator itself
can be changed. This is analagous to int *const.

The const qualifier on return values of operator*(), operator[](),
and operator->() controls whether the the pointed-to value can be
changed. This is analogous to const int *.

Since operator*() does not (in principle) change the iterator, then
there should only be one definition, which is const-qualified. E.g.,
iterators wrapping int* should look like:

int *operator*() const; // always const-qualified, no overloads

ba7a6b314fd14bb2c9ff5d3f4fe2b6525514cada changed iterator_adaptor_base
away from this to work around bugs in other iterator adaptors. That was
already reverted. This patch adds back its test, which combined
llvm::enumerate() and llvm::make_filter_range(), adds a test for
iterator_adaptor_base itself, and cleans up the const-ness of the
other iterator adaptors.

This also updates the documented requirements for
iterator_facade_base:

/// OLD:
///   - const T &operator*() const;
///   - T &operator*();

/// New:
///   - T &operator*() const;

In a future commit we might also clean up iterator_facade's overloads
of operator->() and operator[](). These already (correctly) return
non-const proxies regardless of the iterator's const qualifier.

[dexonsmith]

llvm/unittests/ADT/IteratorTest.cpp

104

I expected this test to fail (and the proof below not to compile) after https://reviews.llvm.org/D112981, but locally it seemed fine. It appears that const ReferenceT is equivalent to int& when ReferenceT==int&... which confuses me a bit, but so be it.

124

This returned false after https://reviews.llvm.org/D112981 and the proof below failed to compile.

[mehdi_amini]

Thanks for all the fixes!
@dblaikie is a better reviewer than I am for this, I'm easily lost in the layers of iterators wrapping iterators...

llvm/unittests/ADT/IteratorTest.cpp

104

Right this always confuses me as well, this is "reference is a const reference, but not a reference to const", so the "const" applies to the reference, but a reference is always "const" (as in int *const).
This is why we have std::remove_reference_t in generic code right?

[dexonsmith]

Squashed in https://reviews.llvm.org/D112981 since it was reverted (effectively just picks up its test).

[dexonsmith]

llvm/unittests/ADT/IteratorTest.cpp

104

Right, right; thanks!

In which case, https://reviews.llvm.org/D112981 only adds const to by-value returns (which are super rare, outside of proxies).

[dexonsmith]

@dblaikie / others, I have some doubts after doing a deeper audit of custom iterators in LLVM.

There are lots of custom iterators that *only* define a non-const qualified operator*(). In some cases, it'd make sense to make a member mutable, or change the return type to always be const-qualified. But perhaps not in every case?

Another option, which would be consistent with iterator_facade_base's implementations of [] and ->, would be to define both here but not adjust the return type:

ReferenceT operator*() { return *I; } // Note: return has no `const`
ReferenceT operator*() const { return *I; }

Other adaptors could also overload operator*(), but also would avoid adding const to the return.

This would:

• Conform to the ReferenceT defined in the template parameters (avoids my main concern from https://reviews.llvm.org/D112981).
• Support adapting iterators where operator*() is non-const.
• Error on const-qualified dereferences if the adapted iterator doesn't return ReferenceT for that.

WDYT?

[dblaikie]

There are lots of custom iterators that *only* define a non-const qualified operator*(). In some cases, it'd make sense to make a member mutable, or change the return type to always be const-qualified. But perhaps not in every case?

I think that covers all cases I can think of, and seems like the right thing - but if it means lots of cleanup, and just keeping/making two overloads (const/non-const) that both return non-const ref (well, return ref, whatever that is - const ref for const_iterators (that themselves may or may not be const... you know what I mean)) is significantly cheaper right now - I'd be OK with that. Seems like it'd make things incrementally better at least - leave a comment aobut it being a stop-gap, not a complete solution, maybe some comments about the functionality or patterns that are deprecated/urge people towards just writing the one const op*?

[dexonsmith]

In D113158#3120023, @dblaikie wrote:

There are lots of custom iterators that *only* define a non-const qualified operator*(). In some cases, it'd make sense to make a member mutable, or change the return type to always be const-qualified. But perhaps not in every case?

I think that covers all cases I can think of, and seems like the right thing - but if it means lots of cleanup, and just keeping/making two overloads (const/non-const) that both return non-const ref (well, return ref, whatever that is - const ref for const_iterators (that themselves may or may not be const... you know what I mean)) is significantly cheaper right now - I'd be OK with that. Seems like it'd make things incrementally better at least - leave a comment aobut it being a stop-gap, not a complete solution, maybe some comments about the functionality or patterns that are deprecated/urge people towards just writing the one const op*?

I think I'd rather commit as-is with just one operator*() const if you agree it's the right answer. (I found the counter-examples by doing a grep for operator*() {, but they aren't being used in iterator adaptors right now... so I don't think we need a stop-gap.)

Think there's value in adding a test that a second operator non-const-qualified operator isn't added as a place to add a comment, something like:

// There should only be one `operator*()` and it should be const-qualified.
// Rather than adding overloads, fields in adapted iterators should be made
// mutable or ReferenceT should be `const`-qualified.
auto x = &decltype(make_filter_range(...).begin())::operator*;
auto x = &decltype(make_map_range(...).begin())::operator*;
auto x = &decltype(reverse(...).begin())::operator*;
...

?

[dblaikie]

In D113158#3122372, @dexonsmith wrote:

In D113158#3120023, @dblaikie wrote:

There are lots of custom iterators that *only* define a non-const qualified operator*(). In some cases, it'd make sense to make a member mutable, or change the return type to always be const-qualified. But perhaps not in every case?

I think that covers all cases I can think of, and seems like the right thing - but if it means lots of cleanup, and just keeping/making two overloads (const/non-const) that both return non-const ref (well, return ref, whatever that is - const ref for const_iterators (that themselves may or may not be const... you know what I mean)) is significantly cheaper right now - I'd be OK with that. Seems like it'd make things incrementally better at least - leave a comment aobut it being a stop-gap, not a complete solution, maybe some comments about the functionality or patterns that are deprecated/urge people towards just writing the one const op*?

I think I'd rather commit as-is with just one operator*() const if you agree it's the right answer. (I found the counter-examples by doing a grep for operator*() {, but they aren't being used in iterator adaptors right now... so I don't think we need a stop-gap.)

Yep, I'm on board!

Think there's value in adding a test that a second operator non-const-qualified operator isn't added as a place to add a comment, something like:

// There should only be one `operator*()` and it should be const-qualified.
// Rather than adding overloads, fields in adapted iterators should be made
// mutable or ReferenceT should be `const`-qualified.
auto x = &decltype(make_filter_range(...).begin())::operator*;
auto x = &decltype(make_map_range(...).begin())::operator*;
auto x = &decltype(reverse(...).begin())::operator*;
...

?

Can we put that in the iterator adapter base somehow, so we don't have to make it a statement about each use of iterator adapters?

[dexonsmith]

Thanks for the review! Landed in 1b651be0465de70cfa22ce4f715d3501a4dcffc1.

In D113158#3123101, @dblaikie wrote:

Think there's value in adding a test that a second operator non-const-qualified operator isn't added as a place to add a comment, something like:

// There should only be one `operator*()` and it should be const-qualified.
// Rather than adding overloads, fields in adapted iterators should be made
// mutable or ReferenceT should be `const`-qualified.
auto x = &decltype(make_filter_range(...).begin())::operator*;
auto x = &decltype(make_map_range(...).begin())::operator*;
auto x = &decltype(reverse(...).begin())::operator*;
...

?

Can we put that in the iterator adapter base somehow, so we don't have to make it a statement about each use of iterator adapters?

I tried adding something like static_assert(&DerivedT::operator*, "") to iterator_adaptor_base but at the point of evaluation (DerivedT's parent class), DerivedT doesn't have an operator* yet. For now I've left this alone.

(BTW, I have some follow-ups to clean up operator-> and operator[].)

llvm/include/llvm/ADT/STLExtras.h

bool test_all_equals(const zip_common &other,
     return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) ==
                                               std::get<Ns>(other.iterators)...},
                   identity<bool>{});
   }
 
 public:
   zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
 
-  value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
-
-  const value_type operator*() const {
+  value_type operator*() const {
     return deref(std::index_sequence_for<Iters...>{});
   }
 
   ZipType &operator++() {
     iterators = tup_inc(std::index_sequence_for<Iters...>{});
     return *reinterpret_cast<ZipType *>(this);
   }
 
return std::tuple<Iters...>(
         next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
   }
 
 public:
   zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
       : iterators(std::forward<Iters>(ts.first)...),
         end_iterators(std::forward<Iters>(ts.second)...) {}
 
-  value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
-
   value_type operator*() const {
     return deref(std::index_sequence_for<Iters...>{});
   }
 
   zip_longest_iterator<Iters...> &operator++() {
     iterators = tup_inc(std::index_sequence_for<Iters...>{});
     return *this;
   }
result_pair(const result_pair<R> &Other)
       : Index(Other.Index), Iter(Other.Iter) {}
   result_pair &operator=(const result_pair &Other) {
     Index = Other.Index;
     Iter = Other.Iter;
     return *this;
   }
 
   std::size_t index() const { return Index; }
-  const value_reference value() const { return *Iter; }
-  value_reference value() { return *Iter; }
+  value_reference value() const { return *Iter; }
 
 private:
   std::size_t Index = std::numeric_limits<std::size_t>::max();
   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> {
+    : public iterator_facade_base<enumerator_iter<R>, std::forward_iterator_tag,
+                                  const result_pair<R>> {
   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

 ///
 /// Classes wishing to use `iterator_facade_base` should implement the following
 /// methods:
 ///
 /// Forward Iterators:
 ///   (All of the following methods)
 ///   - DerivedT &operator=(const DerivedT &R);
 ///   - bool operator==(const DerivedT &R) const;
-///   - const T &operator*() const;
-///   - T &operator*();
+///   - T &operator*() const;
 ///   - DerivedT &operator++();
 ///
 /// Bidirectional Iterators:
 ///   (All methods of forward iterators, plus the following)
 ///   - DerivedT &operator--();
 ///
 /// Random-access Iterators:
 ///   (All methods of bidirectional iterators excluding the following)
class pointer_iterator
   mutable T Ptr;
 
 public:
   pointer_iterator() = default;
 
   explicit pointer_iterator(WrappedIteratorT u)
       : pointer_iterator::iterator_adaptor_base(std::move(u)) {}
 
-  T &operator*() { return Ptr = &*this->I; }
-  const T &operator*() const { return Ptr = &*this->I; }
+  T &operator*() const { return Ptr = &*this->I; }
 };
 
 template <typename RangeT, typename WrappedIteratorT =
                                decltype(std::begin(std::declval<RangeT>()))>
 iterator_range<pointer_iterator<WrappedIteratorT>>
 make_pointer_range(RangeT &&Range) {
   using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
   return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),

llvm/unittests/ADT/IteratorTest.cpp

 using pointer_iterator_defaulted = pointer_iterator<T>;
 
 // Ensures that an iterator and its adaptation have the same iterator_category.
 template<template<typename> class A, typename It>
 using IsAdaptedIterCategorySame =
   std::is_same<typename std::iterator_traits<It>::iterator_category,
                typename std::iterator_traits<A<It>>::iterator_category>;
 
+// Check that dereferencing works correctly adapting pointers and proxies.
+template <class T>
+struct PointerWrapper : public iterator_adaptor_base<PointerWrapper<T>, T *> {
+  PointerWrapper(T *I) : iterator_adaptor_base<PointerWrapper, T *>(I) {}
+};
+struct IntProxy {
+  int &I;
+  IntProxy(int &I) : I(I) {}
+  void operator=(int NewValue) { I = NewValue; }
+};
+struct ConstIntProxy {
+  const int &I;
+  ConstIntProxy(const int &I) : I(I) {}
+};
+template <class T, class ProxyT>
+struct PointerProxyWrapper
+    : public iterator_adaptor_base<PointerProxyWrapper<T, ProxyT>, T *,
+                                   std::random_access_iterator_tag, T,
+                                   ptrdiff_t, T *, ProxyT> {
+  PointerProxyWrapper(T *I)
+      : iterator_adaptor_base<PointerProxyWrapper, T *,
+                              std::random_access_iterator_tag, T, ptrdiff_t,
+                              T *, ProxyT>(I) {}
+};
+using IntIterator = PointerWrapper<int>;
+using ConstIntIterator = PointerWrapper<const int>;
+using IntProxyIterator = PointerProxyWrapper<int, IntProxy>;
+using ConstIntProxyIterator = PointerProxyWrapper<const int, ConstIntProxy>;
+
+template <class T,
+          std::enable_if_t<std::is_assignable<T, int>::value, bool> = false>
+constexpr bool canAssignFromInt(T &&) {
+  return true;
+}
+template <class T,
+          std::enable_if_t<!std::is_assignable<T, int>::value, bool> = false>
+constexpr bool canAssignFromInt(T &&) {
+  return false;
+}
+
+TEST(IteratorAdaptorTest, Dereference) {
+  int Number = 1;
+
+  // Construct some iterators and check whether they can be assigned to.
+  IntIterator I(&Number);
+  const IntIterator IC(&Number);
+  ConstIntIterator CI(&Number);
+  const ConstIntIterator CIC(&Number);
+  EXPECT_EQ(true, canAssignFromInt(*I));    // int *
+  EXPECT_EQ(true, canAssignFromInt(*IC));   // int *const
+  EXPECT_EQ(false, canAssignFromInt(*CI));  // const int *
+  EXPECT_EQ(false, canAssignFromInt(*CIC)); // const int *const
+
+  // Prove that dereference and assignment work.
+  EXPECT_EQ(1, *I);
+  EXPECT_EQ(1, *IC);
+  EXPECT_EQ(1, *CI);
+  EXPECT_EQ(1, *CIC);
+  *I = 2;
+  EXPECT_EQ(2, Number);
+  *IC = 3;
+  EXPECT_EQ(3, Number);
+
+  // Construct some proxy iterators and check whether they can be assigned to.
+  IntProxyIterator P(&Number);
+  const IntProxyIterator PC(&Number);
+  ConstIntProxyIterator CP(&Number);
+  const ConstIntProxyIterator CPC(&Number);
+  EXPECT_EQ(true, canAssignFromInt(*P));    // int *
+  EXPECT_EQ(true, canAssignFromInt(*PC));   // int *const
+  EXPECT_EQ(false, canAssignFromInt(*CP));  // const int *
+  EXPECT_EQ(false, canAssignFromInt(*CPC)); // const int *const
+
+  // Prove that dereference and assignment work.
+  EXPECT_EQ(3, (*P).I);
+  EXPECT_EQ(3, (*PC).I);
+  EXPECT_EQ(3, (*CP).I);
+  EXPECT_EQ(3, (*CPC).I);
+  *P = 4;
+  EXPECT_EQ(4, Number);
+  *PC = 5;
+  EXPECT_EQ(5, Number);
+}
+
 // pointeE_iterator
 static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,
                                         RandomAccessIter>::value, "");
 static_assert(IsAdaptedIterCategorySame<pointee_iterator_defaulted,
                                         BidiIter>::value, "");
 // pointeR_iterator
 static_assert(IsAdaptedIterCategorySame<pointer_iterator_defaulted,
                                         RandomAccessIter>::value, "");

 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) {