3406. elements_view::begin() and elements_view::end() have incompatible constraints

Section: 25.7.23.2 [range.elements.view] Status: C++23 Submitter: Patrick Palka Opened: 2020-02-21 Last modified: 2023-11-22

Priority: 1

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

View all issues with C++23 status.

Discussion:

P1994R1 (elements_view needs its own sentinel) introduces a distinct sentinel type for elements_view. In doing so, it replaces the two existing overloads of elements_view::end() with four new ones: 

-    constexpr auto end() requires (!simple-view<V>)
-    { return ranges::end(base_); }
-
-    constexpr auto end() const requires simple-view<V>
-    { return ranges::end(base_); }

+    constexpr auto end()
+    { return sentinel<false>{ranges::end(base_)}; }
+
+    constexpr auto end() requires common_range<V>
+    { return iterator<false>{ranges::end(base_)}; }
+
+    constexpr auto end() const
+      requires range<const V>
+    { return sentinel<true>{ranges::end(base_)}; }
+
+    constexpr auto end() const
+      requires common_range<const V>
+    { return iterator<true>{ranges::end(base_)}; }

But now these new overloads of elements_view::end() have constraints that are no longer consistent with the constraints of elements_view::begin(): 

     constexpr auto begin() requires (!simple-view<V>)
     { return iterator<false>(ranges::begin(base_)); }

     constexpr auto begin() const requires simple-view<V>
     { return iterator<true>(ranges::begin(base_)); }

This inconsistency means that we can easily come up with a view V for which elements_view<V>::begin() returns an iterator<true> and elements_view<V>::end() returns an sentinel<false>, i.e. incomparable things of opposite constness. For example: 

tuple<int, int> x[] = {{0,0}};
ranges::subrange r = {counted_iterator(x, 1), default_sentinel};
auto v = r | views::elements<0>;
v.begin() == v.end(); // ill-formed

Here, overload resolution for begin() selects the const overload because the subrange r models simple-view. But overload resolution for end() selects the non-const non-common_range overload. Hence the last line of this snippet is ill-formed because it is comparing an iterator and sentinel of opposite constness, for which we have no matching operator== overload. So in this example v does not even model range because its begin() and end() are incomparable.

This issue can be resolved by making sure the constraints on elements_view::begin() and on elements_view::end() are consistent and compatible. The following proposed resolution seems to be one way to achieve that and takes inspiration from the design of transform_view.

[2020-04-04 Issue Prioritization]

Priority to 1 after reflector discussion.

[2020-07-17; telecon]

Should be considered together with 3448 and 3449.

Previous resolution [SUPERSEDED]:

This wording is relative to N4849 after application of P1994R1.

  1. Modify 25.7.23.2 [range.elements.view], class template elements_view synopsis, as indicated:

    namespace std::ranges {
  […]
  template<input_range V, size_t N>
    requires view<V> && has-tuple-element<range_value_t<V>, N> &&
      has-tuple-element<remove_reference_t<range_reference_t<V>>, N>
  class elements_view : public view_interface<elements_view<V, N>> {
  public:
    […]
    constexpr V base() && { return std::move(base_); }

    constexpr auto begin() requires (!simple-view<V>)
    { return iterator<false>(ranges::begin(base_)); }
    constexpr auto begin() const requires simple-view<V>range<const V>
    { return iterator<true>(ranges::begin(base_)); }
    […]
  };
}

[2020-06-05 Tim updates P/R in light of reflector discussions and LWG 3448 and comments]

The fact that, as currently specified, sentinel<false> is not comparable with iterator<true> is a problem with the specification of this comparison, as noted in LWG 3448. The P/R below repairs this problem along the lines suggested in that issue. The constraint mismatch does make this problem easier to observe for elements_view, but the mismatch is not independently a problem: since begin can only add constness on simple-views for which constness is immaterial, whether end also adds constness or not ought not to matter.

However, there is a problem with the begin overload set: if const V is a range, but V is not a simple-view, then a const elements_view<V, N> has no viable begin at all (the simplest example of such non-simple-views is probably single_view). That's simply broken; the fix is to constrain the const overload of begin with just range<const V> instead of simple-view<V>. Notably, this is how many other uses of simple-view work already (see, e.g., take_view in 25.7.10.2 [range.take.view]).

The previous simple-view constraint on end served a useful purpose (when done correctly): it reduces template instantiations if the underlying view is const-agnostic. This was lost in P1994 because that paper modeled the overload set on transform_view; however, discussion with Eric Niebler confirmed that the reason transform_view doesn't have the simple-view optimization is because it would add constness to the callable object as well, which can make a material difference in the result. Such concerns are not present in elements_view where the "callable object" is effectively hard-coded into the type and unaffected by const-qualification. The revised P/R below therefore restores the simple-view optimization.

I have implemented this P/R together with P1994 on top of libstdc++ trunk and can confirm that no existing test cases were broken by these changes, and that it fixes the issue reported here as well as in LWG 3448 (as it relates to elements_view).

[2020-10-02; Status to Tentatively Ready after five positive votes on the reflector]

[2020-11-09 Approved In November virtual meeting. Status changed: Tentatively Ready → WP.]

Proposed resolution:

This wording is relative to N4861. It assumes the maybe-const helper introduced by the P/R of LWG 3448.

  1. Modify 25.7.23.2 [range.elements.view], class template elements_view synopsis, as indicated:

    namespace std::ranges {
  […]
  template<input_range V, size_t N>
    requires view<V> && has-tuple-element<range_value_t<V>, N> &&
      has-tuple-element<remove_reference_t<range_reference_t<V>>, N>
  class elements_view : public view_interface<elements_view<V, N>> {
  public:
    […]
    constexpr V base() && { return std::move(base_); }

    constexpr auto begin() requires (!simple-view<V>)
    { return iterator<false>(ranges::begin(base_)); }

    constexpr auto begin() const requires simple-view<V>range<const V>
    { return iterator<true>(ranges::begin(base_)); }

    constexpr auto end() requires (!simple-view<V> && !common_range<V>)
    { return sentinel<false>{ranges::end(base_)}; }

    constexpr auto end() requires (!simple-view<V> && common_range<V>)
    { return iterator<false>{ranges::end(base_)}; }

    constexpr auto end() const requires range<const V>
    { return sentinel<true>{ranges::end(base_)}; }

    constexpr auto end() const requires common_range<const V>
    { return iterator<true>{ranges::end(base_)}; }
    […]
  };
}

  2. Modify 25.7.23.4 [range.elements.sentinel] as indicated:

    [Drafting note: Unlike the current P/R of LWG 3448, this P/R also changes the return type of operator- to depend on the constness of iterator rather than that of the sentinel. This is consistent with sized_sentinel_for<S, I> (24.3.4.8 [iterator.concept.sizedsentinel]), which requires decltype(i - s) to be iter_difference_t<I>.] 

    namespace std::ranges {
  template<input_range V, size_t N>
    requires view<V> && has-tuple-element<range_value_t<V>, N> &&
      has-tuple-element<remove_reference_t<range_reference_t<V>>, N>
  template<bool Const>
  class elements_view<V, F>::sentinel {
    […]
    constexpr sentinel_t<Base> base() const;

    template<bool OtherConst>
      requires sentinel_for<sentinel_t<Base>, iterator_t<maybe-const<OtherConst, V>>>
    friend constexpr bool operator==(const iterator<OtherConst>& x, const sentinel& y);

    template<bool OtherConst>
      requires sized_sentinel_for<sentinel_t<Base>, iterator_t<maybe-const<OtherConst, V>>>
    friend constexpr range_difference_t<Basemaybe-const<OtherConst, V>>
      operator-(const iterator<OtherConst>& x, const sentinel& y)
        requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;

    template<bool OtherConst>
      requires sized_sentinel_for<sentinel_t<Base>, iterator_t<maybe-const<OtherConst, V>>>
    friend constexpr range_difference_t<Basemaybe-const<OtherConst, V>>
      operator-(const sentinel& x, const iterator<OtherConst>& y)
        requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;
  };
}
    […] 
    template<bool OtherConst>
  requires sentinel_for<sentinel_t<Base>, iterator_t<maybe-const<OtherConst, V>>>
friend constexpr bool operator==(const iterator<OtherConst>& x, const sentinel& y);

    -4- Effects: Equivalent to: return x.current_ == y.end_; 

    template<bool OtherConst>
  requires sized_sentinel_for<sentinel_t<Base>, iterator_t<maybe-const<OtherConst, V>>>
friend constexpr range_difference_t<Basemaybe-const<OtherConst, V>>
  operator-(const iterator<OtherConst>& x, const sentinel& y)
    requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;

    -5- Effects: Equivalent to: return x.current_ - y.end_; 

    template<bool OtherConst>
  requires sized_sentinel_for<sentinel_t<Base>, iterator_t<maybe-const<OtherConst, V>>>
friend constexpr range_difference_t<Basemaybe-const<OtherConst, V>>
  operator-(const sentinel& x, const iterator<OtherConst>& y)
    requires sized_sentinel_for<sentinel_t<Base>, iterator_t<Base>>;

    -6- Effects: Equivalent to: return x.end_ - y.current_;