Issue 3731: zip_view and adjacent_view are underconstrained

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

3731. `zip_view` and `adjacent_view` are underconstrained

Section: 26.7.25.2 [range.zip.view], 26.7.27.2 [range.adjacent.view], 26.7.33.2 [range.cartesian.view] Status: New Submitter: Hewill Kang Opened: 2022-07-04 Last modified: 2023-08-12

Priority: 3

View all other issues in [range.zip.view].

View all issues with New status.

Discussion:

Both zip_view::iterator's (26.7.25.3 [range.zip.iterator]) and adjacent_view::iterator's (26.7.27.3 [range.adjacent.iterator]) operator* have similar Effects: elements:

return tuple-transform([](auto& i) -> decltype(auto) { return *i; }, current_);

where tuple-transform is defined as:

template<class F, class Tuple>
constexpr auto tuple-transform(F&& f, Tuple&& tuple) { // exposition only
  return apply([&]<class... Ts>(Ts&&... elements) {
    return tuple-or-pair<invoke_result_t<F&, Ts>...>(
      invoke(f, std::forward<Ts>(elements))...
    );
  }, std::forward<Tuple>(tuple));
}

That is, zip_view::iterator will invoke the operator* of each iterator of Views and return a tuple containing its reference.

This is not a problem when the reference of iterators is actually the reference type. However, when the operator* returns a prvalue of non-movable type, tuple-transform will be ill-formed since there are no suitable constructors for tuple:

#include <ranges>

struct NonMovable {
  NonMovable() = default;
  NonMovable(NonMovable&&) = delete;
};

auto r = std::views::iota(0, 5)
       | std::views::transform([](int) { return NonMovable{}; });
auto z = std::views::zip(r);
auto f = *z.begin(); // hard error

We should constrain the range_reference_t of the underlying range to be move_constructible when it is not a reference type, which also solves similar issues in zip_view::iterator and adjacent_view::iterator's operator[] and iter_move.

[2022-08-23; Reflector poll]

Set priority to 3 after reflector poll. "The constraint should just be move_constructible."

Previous resolution [SUPERSEDED]:

This wording is relative to N4910.

Modify 26.2 [ranges.syn], header <ranges> synopsis, as indicated:

namespace std::ranges {
  […]
  // 26.7.25 [range.zip], zip view
  template<class Ref>
    concept tuple-constructible-reference = see below; // exposition only

  template<input_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0) &&
             (tuple-constructible-reference<range_reference_t<Views>> && ...)
  class zip_view;

  […]

  // 26.7.27 [range.adjacent], adjacent view
  template<forward_range V, size_t N>
    requires view<V> && (N > 0) && 
             tuple-constructible-reference<range_reference_t<V>>
  class adjacent_view;
}
[…]

Modify 26.7.25.2 [range.zip.view] as indicated:

namespace std::ranges {
  template<class Ref>
    concept tuple-constructible-reference =            // exposition only
      is_reference_v<Ref> || move_constructible<Ref>;
  […]
  template<input_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0) &&
             (tuple-constructible-reference<range_reference_t<Views>> && ...)
  class zip_view : public view_interface<zip_view<Views...>> {
    […]
  };
  […]
}

Modify 26.7.27.2 [range.adjacent.view] as indicated:

namespace std::ranges {
  template<forward_range V, size_t N>
    requires view<V> && (N > 0) && 
             tuple-constructible-reference<range_reference_t<V>>
  class adjacent_view : public view_interface<adjacent_view<V, N>> {
    […]
  };
  […]
}

[2022-09-25; Hewill provides improved wording]

Previous resolution [SUPERSEDED]:

This wording is relative to N4917.

Modify 26.2 [ranges.syn], header <ranges> synopsis, as indicated:

namespace std::ranges {
  […]

  template<class R>
    concept has-tuplable-ref =            // exposition only
      move_constructible<range_reference_t<R>>;

  // 26.7.25 [range.zip], zip view
  template<input_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0) &&
             (has-tuplable-ref<Views> && ...)
  class zip_view;

  […]

  // 26.7.27 [range.adjacent], adjacent view
  template<forward_range V, size_t N>
    requires view<V> && (N > 0) && has-tuplable-ref<V>
  class adjacent_view;

  […]

  // 26.7.33 [range.cartesian], cartesian product view
  template<input_range First, forward_range... Vs>
    requires (view<First> && ... && view<Vs>) &&
             (has-tuplable-ref<First> && ... && has-tuplable-ref<Vs>)
  class cartesian_product_view;

  […]
}

Modify 26.7.25.2 [range.zip.view] as indicated:

namespace std::ranges {
  […]
  
  template<input_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0) &&
             (has-tuplable-ref<Views> && ...)
  class zip_view : public view_interface<zip_view<Views...>> {
    […]
  };
}

Modify 26.7.25.3 [range.zip.iterator] as indicated:

namespace std::ranges {
  […]
  template<input_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0) &&
             (has-tuplable-ref<Views> && ...)
  template<bool Const>
  class zip_view<Views...>::iterator {
    […]
  };
}

Modify 26.7.25.4 [range.zip.sentinel] as indicated:

namespace std::ranges {
  template<input_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0) &&
             (has-tuplable-ref<Views> && ...)
  template<bool Const>
  class zip_view<Views...>::sentinel {
    […]
  };
}

Modify 26.7.27.2 [range.adjacent.view] as indicated:

namespace std::ranges {
  template<forward_range V, size_t N>
    requires view<V> && (N > 0) && has-tuplable-ref<V>
  class adjacent_view : public view_interface<adjacent_view<V, N>> {
    […]
  };
}

Modify 26.7.27.3 [range.adjacent.iterator] as indicated:

namespace std::ranges {
  template<forward_range V, size_t N>
    requires view<V> && (N > 0) && has-tuplable-ref<V>
  template<bool Const>
  class adjacent_view<V, N>::iterator {
    […]
  };
}

Modify 26.7.27.4 [range.adjacent.sentinel] as indicated:

namespace std::ranges {
  template<forward_range V, size_t N>
    requires view<V> && (N > 0) && has-tuplable-ref<V>
  template<bool Const>
  class adjacent_view<V, N>::sentinel {
    […]
  };
}

Modify 26.7.33.2 [range.cartesian.view] as indicated:

namespace std::ranges {
  […]
  template<input_range First, forward_range... Vs>
    requires (view<First> && ... && view<Vs>) &&
             (has-tuplable-ref<First> && ... && has-tuplable-ref<Vs>)
  class cartesian_product_view : public view_interface<cartesian_product_view<First, Vs...>> {
    […]
  };
}

Modify 26.7.33.3 [range.cartesian.iterator] as indicated:

namespace std::ranges {
  template<input_range First, forward_range... Vs>
    requires (view<First> && ... && view<Vs>) &&
             (has-tuplable-ref<First> && ... && has-tuplable-ref<Vs>)
  template<bool Const>
  class cartesian_product_view<First, Vs...>::iterator {
    […]
  };
}

[2023-08-08; Hewill provides improved wording]

Proposed resolution:

This wording is relative to N4950.

Modify 26.2 26.2 [ranges.syn], header <ranges> synopsis, as indicated:

namespace std::ranges {
  […]

  // 26.5.2 [range.utility.helpers], helper concepts
  template<class R>
    concept range-with-movable-references = see below; // exposition only

  // 26.5.3 [view.interface], class template view_interface
  template<class D>
    requires is_class_v<D> && same_as<D, remove_cv_t<D>>
  class view_interface;                                                             // freestanding

  […]

  // 26.7.24 [range.enumerate], enumerate view
  template<input_rangeview V>
    requires range-with-movable-references<V>view<View>
  class enumerate_view;                                                             // freestanding

  […]

  // 26.7.25 [range.zip], zip view
  template<range-with-movable-referencesinput_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0)
  class zip_view;                                                                   // freestanding

  […]

  // 26.7.27 [range.adjacent], adjacent view
  template<range-with-movable-referencesforward_range V, size_t N>
    requires forward_range<V> && view<V> && (N > 0)
  class adjacent_view;                                                              // freestanding

  […]

  // 26.7.33 [range.cartesian], cartesian product view
  template<range-with-movable-referencesinput_range First, 
           range-with-movable-referencesforward_range... Vs>
    requires (view<First> && ... && (forward_range<Vs> && view<Vs>))
  class cartesian_product_view;                                                     // freestanding

  […]
}

Modify 26.7.25.2 [range.zip.view] as indicated:

namespace std::ranges {
  […]
  
  template<range-with-movable-referencesinput_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0)
  class zip_view : public view_interface<zip_view<Views...>> {
    […]
  public:
    […]
    constexpr auto begin() const requires (range-with-movable-referencesrange<const Views> && ...) {
      return iterator<true>(tuple-transform(ranges::begin, views_));
    }
    […]
    constexpr auto end() const requires (range-with-movable-referencesrange<const Views> && ...) {
      if constexpr (!zip-is-common<const Views...>) {
        return sentinel<true>(tuple-transform(ranges::end, views_));
      } else if constexpr ((random_access_range<const Views> && ...)) {
        return begin() + iter_difference_t<iterator<true>>(size());
      } else {
        return iterator<true>(tuple-transform(ranges::end, views_));
      }
    }
    […]
  };
}

Modify 26.7.25.3 [range.zip.iterator] as indicated:

namespace std::ranges {
  […]
  template<range-with-movable-referencesinput_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0)
  template<bool Const>
  class zip_view<Views...>::iterator {
    […]
  };
}

Modify 26.7.25.4 [range.zip.sentinel] as indicated:

namespace std::ranges {
  template<range-with-movable-referencesinput_range... Views>
    requires (view<Views> && ...) && (sizeof...(Views) > 0)
  template<bool Const>
  class zip_view<Views...>::sentinel {
    […]
  };
}

Modify 26.7.27.2 [range.adjacent.view] as indicated:

namespace std::ranges {
  template<range-with-movable-referencesforward_range V, size_t N>
    requires forward_range<V> && view<V> && (N > 0)
  class adjacent_view : public view_interface<adjacent_view<V, N>> {
    […]
  public:
    […]
    constexpr auto begin() const requires range-with-movable-referencesrange<const V> {
      return iterator<true>(ranges::begin(base_), ranges::end(base_));
    }
    […]
    constexpr auto end() const requires range-with-movable-referencesrange<const V> {
      if constexpr (common_range<const V>) {
        return iterator<true>(as-sentinel{}, ranges::begin(base_), ranges::end(base_));
      } else {
        return sentinel<true>(ranges::end(base_));
      }
    }
    […]
  };
}

Modify 26.7.27.3 [range.adjacent.iterator] as indicated:

namespace std::ranges {
  template<range-with-movable-referencesforward_range V, size_t N>
    requires forward_range<V> && view<V> && (N > 0)
  template<bool Const>
  class adjacent_view<V, N>::iterator {
    […]
  };
}

Modify 26.7.27.4 [range.adjacent.sentinel] as indicated:

namespace std::ranges {
  template<range-with-movable-referencesforward_range V, size_t N>
    requires forward_range<V> && view<V> && (N > 0)
  template<bool Const>
  class adjacent_view<V, N>::sentinel {
    […]
  };
}

Modify 26.7.33.2 [range.cartesian.view] as indicated:

namespace std::ranges {
  […]
  template<range-with-movable-referencesinput_range First, 
           range-with-movable-referencesforward_range... Vs>
    requires (view<First> && ... && (forward_range<Vs> && view<Vs>))
  class cartesian_product_view : public view_interface<cartesian_product_view<First, Vs...>> {
    […]
  public:
    […]
    constexpr iterator<true> begin() const
      requires (range-with-movable-referencesrange<const First> && ... && 
                range-with-movable-referencesrange<const Vs>);
    […]
    constexpr iterator<true> end() const
      requires (range-with-movable-references<const First> && ... && 
                range-with-movable-references<const Vs>) &&
               cartesian-product-is-common<const First, const Vs...>;
    […]
  };
}

[…]

constexpr iterator<true> begin() const
  requires (range-with-movable-referencesrange<const First> && ... && 
            range-with-movable-referencesrange<const Vs>);

-3- Effects: Equivalent to:

return iterator<true>(*this, tuple-transform(ranges::begin, bases_));

constexpr iterator<false> end()
  requires ((!simple-view<First> || ... || !simple-view<Vs>)
    && cartesian-product-is-common<First, Vs...>);
constexpr iterator<true> end() const
  requires (range-with-movable-references<const First> && ... && range-with-movable-references<const Vs>)
    && cartesian-product-is-common<const First, const Vs...>;

-4- Let:

[…]

Modify 26.7.33.3 [range.cartesian.iterator] as indicated:

namespace std::ranges {
  […]
  template<range-with-movable-referencesinput_range First, range-with-movable-referencesforward_range... Vs>
    requires (view<First> && ... && (forward_range<Vs> && view<Vs>))
  class cartesian_product_view<First, Vs...>::iterator {
    […]
  };
}

3731. zip_view and adjacent_view are underconstrained

3731. `zip_view` and `adjacent_view` are underconstrained