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

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

Section: 26.7.22.2 [range.elements.view] Status: WP Submitter: Patrick Palka Opened: 2020-02-21 Last modified: 2020-11-09

Priority: 1

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

View all issues with WP 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 26.7.22.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-view`s 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 26.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 26.7.22.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 26.7.22.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>` (25.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_;`