llvm::zip should not require assignment operator

[tlongeri]

Add zip test. Fix tup_inc incorrectly remaining const. Rename increment_or_end to increment_if_not_end.

[tlongeri]

clang-format

[dblaikie]

I've got mixed feelings - the mechanics of the change seem fine, but iterator requirements include copy assignability and copy constructibility - so whatever iterator you're going to use with this feature isn't implementing the iterator requirements and probably should be fixed? I guess the C++20 iterator concepts are a bit more flexible and may include this situation.

[mehdi_amini]

I've got mixed feelings - the mechanics of the change seem fine, but iterator requirements include copy assignability and copy constructibility - so whatever iterator you're going to use with this feature isn't implementing the iterator requirements and probably should be fixed?

It's a good point that we're supporting here iterators that aren't compliant with the general requirements. But I'm wondering if this isn't still a good thing?

That is: isn't it just good for ranges and all adaptors/filters/... to require the minimum amount of things they need from an iterator? (it's not like we're checking on every properties of an iterator everywhere just to force an arbitrary contract).

(we should also fix the iterator if possible, but I know also that some iterators are "fat" and avoiding copies may be valuable!)

[dblaikie]

In D136777#3890029, @mehdi_amini wrote:

I've got mixed feelings - the mechanics of the change seem fine, but iterator requirements include copy assignability and copy constructibility - so whatever iterator you're going to use with this feature isn't implementing the iterator requirements and probably should be fixed?

It's a good point that we're supporting here iterators that aren't compliant with the general requirements. But I'm wondering if this isn't still a good thing?

That is: isn't it just good for ranges and all adaptors/filters/... to require the minimum amount of things they need from an iterator? (it's not like we're checking on every properties of an iterator everywhere just to force an arbitrary contract).

(we should also fix the iterator if possible, but I know also that some iterators are "fat" and avoiding copies may be valuable!)

Yeah, that's roughly my thinking on approving this.

[tlongeri]

I've got mixed feelings - the mechanics of the change seem fine, but iterator requirements include copy assignability and copy constructibility - so whatever iterator you're going to use with this feature isn't implementing the iterator requirements and probably should be fixed?

I missed this, to be honest. The context is just that I tried and failed to zip MLIR's ElementsAttrIterator, and I saw no reason why zip needed assignment.

I guess the C++20 iterator concepts are a bit more flexible and may include this situation.

Unfortunately, it looks like the C++20 input_or_output_iterator concept still requires move assignability (through -> weakly_incrementable -> movable)

Isn't it still a small improvement, though? Besides what Mehdi said, I would just add that it still seems like incrementing the iterators in-place is a bit better. Maybe I should adjust the description, though.

Edit: didn't see your reply

[dblaikie]

In D136777#3890093, @tlongeri wrote:

I've got mixed feelings - the mechanics of the change seem fine, but iterator requirements include copy assignability and copy constructibility - so whatever iterator you're going to use with this feature isn't implementing the iterator requirements and probably should be fixed?

I missed this, to be honest. The context is just that I tried and failed to zip MLIR's ElementsAttrIterator, and I saw no reason why zip needed assignment.

I guess the C++20 iterator concepts are a bit more flexible and may include this situation.

Unfortunately, it looks like the C++20 input_or_output_iterator concept still requires move assignability (through -> weakly_incrementable -> movable)

Yeah - though I think the existing code before your patch here requires copy constructibliity - so this patch does fix llvm::zip to work with these newer iterator concepts, which is good.

Isn't it still a small improvement, though? Besides what Mehdi said, I would just add that it still seems like incrementing the iterators in-place is a bit better. Maybe I should adjust the description, though.

Yep - might be worth checking the ElementsAttrIterator to ensure it at least meets the newer iterator concepts at least. (my usual concern here is not that changing one algorithm to be more lenient - but that a non-conforming iterator will run up against other problems, standard algorithms will have difficult/might have more stringent checks, etc).

[mehdi_amini]

In D136777#3890280, @dblaikie wrote:

Yep - might be worth checking the ElementsAttrIterator to ensure it at least meets the newer iterator concepts at least.

On top of the patch here, we're also adding copy construction and copy assignment on ElementsAttrIterator by the way, it seems like reasonable addition and it seems like it was an oversight to not have it there (this particular iterator isn't that "fat": two bools and two pointers).

[dblaikie]

In D136777#3890394, @mehdi_amini wrote:

In D136777#3890280, @dblaikie wrote:

Yep - might be worth checking the ElementsAttrIterator to ensure it at least meets the newer iterator concepts at least.

On top of the patch here, we're also adding copy construction and copy assignment on ElementsAttrIterator by the way, it seems like reasonable addition and it seems like it was an oversight to not have it there (this particular iterator isn't that "fat": two bools and two pointers).

Awesome - thanks for the details!

llvm/include/llvm/ADT/STLExtras.h

struct zip_common : public zip_traits<ZipType, Iters...> {
 
   std::tuple<Iters...> iterators;
 
 protected:
   template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
     return value_type(*std::get<Ns>(iterators)...);
   }
 
-  template <size_t... Ns>
-  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
-    return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
+  template <size_t... Ns> void tup_inc(std::index_sequence<Ns...>) {
+    (++std::get<Ns>(iterators), ...);
   }
 
-  template <size_t... Ns>
-  decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
-    return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
+  template <size_t... Ns> void tup_dec(std::index_sequence<Ns...>) {
+    (--std::get<Ns>(iterators), ...);
   }
 
   template <size_t... Ns>
   bool test_all_equals(const zip_common &other,
             std::index_sequence<Ns...>) const {
     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*() const {
     return deref(std::index_sequence_for<Iters...>{});
   }
 
   ZipType &operator++() {
-    iterators = tup_inc(std::index_sequence_for<Iters...>{});
+    tup_inc(std::index_sequence_for<Iters...>{});
     return *reinterpret_cast<ZipType *>(this);
   }
 
   ZipType &operator--() {
     static_assert(Base::IsBidirectional,
                   "All inner iterators must be at least bidirectional.");
-    iterators = tup_dec(std::index_sequence_for<Iters...>{});
+    tup_dec(std::index_sequence_for<Iters...>{});
     return *reinterpret_cast<ZipType *>(this);
   }
 
   /// Return true if all the iterator are matching `other`'s iterators.
   bool all_equals(zip_common &other) {
     return test_all_equals(other, std::index_sequence_for<Iters...>{});
   }
 };

 template <typename T, typename U, typename... Args>
 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
                                                           Args &&... args) {
   return detail::zippy<detail::zip_first, T, U, Args...>(
       std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
 }
 
 namespace detail {
-template <typename Iter>
-Iter next_or_end(const Iter &I, const Iter &End) {
-  if (I == End)
-    return End;
-  return std::next(I);
+template <typename Iter> void increment_if_not_end(Iter &I, const Iter &End) {
+  if (I != End)
+    ++I;
 }
 
 template <typename Iter>
 auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional<
     std::remove_const_t<std::remove_reference_t<decltype(*I)>>> {
   if (I == End)
     return None;
   return *I;
return llvm::any_of(
         identity<bool>{});
   }
 
   template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
     return value_type(
         deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
   }
 
-  template <size_t... Ns>
-  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
-    return std::tuple<Iters...>(
-        next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
+  template <size_t... Ns> void tup_inc(std::index_sequence<Ns...>) {
+    (increment_if_not_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*() const {
     return deref(std::index_sequence_for<Iters...>{});
   }
 
   zip_longest_iterator<Iters...> &operator++() {
-    iterators = tup_inc(std::index_sequence_for<Iters...>{});
+    tup_inc(std::index_sequence_for<Iters...>{});
     return *this;
   }
 
   bool operator==(const zip_longest_iterator<Iters...> &other) const {
     return !test(other, std::index_sequence_for<Iters...>{});
   }
 };
 

llvm/unittests/ADT/STLExtrasTest.cpp

int Destructors = 0;
     EXPECT_EQ(0, Moves);
     EXPECT_EQ(1, Destructors);
   }
   EXPECT_EQ(1, Copies);
   EXPECT_EQ(0, Moves);
   EXPECT_EQ(2, Destructors);
 }
 
+TEST(STLExtrasTest, Zip) {
+  struct CountingIterator {
+    // For std::iterator_traits
+    using difference_type = int;
+    using value_type = int;
+    using pointer = void;
+    using reference = int;
+    using iterator_category = std::input_iterator_tag;
+
+    // Test that zip does not require copy assign operator
+    CountingIterator &operator=(const CountingIterator &other) = delete;
+
+    CountingIterator(int count) : count(count) {}
+    CountingIterator(const CountingIterator &other) : count(other.count) {}
+    bool operator==(const CountingIterator &other) const {
+      return count == other.count;
+    }
+    bool operator!=(const CountingIterator &other) const {
+      return !(*this == other);
+    }
+    CountingIterator &operator++() {
+      ++count;
+      return *this;
+    }
+    int operator*() const { return count; }
+    int count;
+  };
+
+  auto r1 = make_range(CountingIterator(5), CountingIterator(9));
+  auto r2 = make_range(CountingIterator(8), CountingIterator(11));
+
+  {
+    auto zip_range = zip(r1, r2);
+    auto it = zip_range.begin();
+    EXPECT_EQ(*it, std::make_tuple(5, 8));
+    ++it;
+    EXPECT_EQ(*it, std::make_tuple(6, 9));
+    ++it;
+    EXPECT_EQ(*it, std::make_tuple(7, 10));
+    ++it;
+    EXPECT_EQ(it, zip_range.end());
+  }
+  {
+    auto zip_range = zip_longest(r1, r2);
+    auto it = zip_range.begin();
+    EXPECT_EQ(*it, std::make_tuple(5, 8));
+    ++it;
+    EXPECT_EQ(*it, std::make_tuple(6, 9));
+    ++it;
+    EXPECT_EQ(*it, std::make_tuple(7, 10));
+    ++it;
+    EXPECT_EQ(*it, std::make_tuple(8, None));
+    ++it;
+    EXPECT_EQ(it, zip_range.end());
+  }
+}
+
 TEST(STLExtrasTest, AllOfZip) {
   std::vector<int> v1 = {0, 4, 2, 1};
   std::vector<int> v2 = {1, 4, 3, 6};
   EXPECT_TRUE(all_of_zip(v1, v2, [](int v1, int v2) { return v1 <= v2; }));
   EXPECT_FALSE(all_of_zip(v1, v2, [](int L, int R) { return L < R; }));
 
   // Triple vectors
   std::vector<int> v3 = {1, 6, 5, 7};