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

### 3777. Common `cartesian_product_view` produces an invalid range if the first range is input and one of the ranges is empty

Section: 26.7.31.2 [range.cartesian.view] Status: Open Submitter: Tomasz Kamiński Opened: 2022-09-12 Last modified: 2022-09-29

Priority: 2

View all issues with Open status.

Discussion:

In case when `cartesian_product_view` is common and one of the inner ranges is empty, it needs to produce equal iterators from `begin`/`end`. We currently create a sequence of `begin` iterators as both `begin` and `end` iterators. This assumes that `begin` iterator is copyable, which may not be the case with the input range, even in the case if that range is common — in such case, we require that only sentinel is semantically copy-constructible, not begin even if they are the same type.

To illustrate, C++98 input iterators (like `directory_iterator`) are syntactically copy-constructible, but only default constructed object, that corresponds to sentinels are semantically copyable — the copy produces an equivalent result. As a consequence for `directory_iterator d`, and empty `std::string_view sv`, the `view::cartesian_product(d, sv)` produces an invalid range.

To fix the problem, we need to move the logic of adjusting the first range iterator to return `[end, begin, ..., begin]` for `begin`. This is safe, as we require the end to be always semantically copy-constructible. This again can be done only if computing the end can be done in `𝒪(1)` i.e. the first range is common.

[2022-09-28; Reflector poll]

Set priority to 2 after reflector poll.

[2022-09-28; LWG telecon]

Discussed issue. Tim suggested to add a new semantic requirement to `sentinel_for` that when `S` and `I` are the same type then `i == i` is true for any non-singular `i` of type `I`.

Proposed resolution:

This wording is relative to N4910.

1. Modify 26.7.31.2 [range.cartesian.view] as indicated:

   > [Drafting note: We can optimize the comparison with `default_sentinel_t` to compare only the iterator to the first range if the range is common. This is observable, as we call comparison of user-provided iterators.]

   >     constexpr iterator<false> begin()
   >       requires (!simple-view<First> || ... || !simple-view<Vs>);

   > > -2- Effects: Equivalent to: `return iterator<false>(tuple-transform(ranges::begin, bases_));`

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

   > > -3- Effects: Equivalent to: `return iterator<true>(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 cartesian-product-is-common<const First, const Vs...>;

   > > -4- Let:

   > > 1. (4.1) — `is-const` be `true` for the const-qualified overloads, and `false` otherwise;

   > > 2. (4.?) — `is-end` be `true` for the `end` overloads, and `false` otherwise;

   > > 3. (4.2) — `is-empty` be `true` if the expression `ranges::empty(rng)` is `true` for any `rng` among the underlying ranges except the first one and `false` otherwise; and

   > > 4. (4.3) — `begin-or-first-end(rng)` be expression-equivalent to `is-end || is-empty ? cartesian-common-arg-end(rng) : ranges::begin(rng)is-empty ? ranges::begin(rng) : cartesian-common-arg-end(rng)` if `cartesian-product-common-arg<maybe-const<is-const, First>>` is `true` and `rng` is the first underlying range, and `ranges::begin(rng)` otherwise.

   > > -5- Effects: Equivalent to:

   > > >     iterator<is-const> it(tuple-transform(
   > > >       [](auto& rng){ return begin-or-first-end(rng); }, bases_));
   > > >     return it;

2. Modify 26.7.31.3 [ranges.cartesian.iterator] as indicated:

   >     friend constexpr bool operator==(const iterator& x, default_sentinel_t);

   > > -26- Returns:

   > > 1. (?.1) — If `cartesian-product-common-arg<maybe-const<Const, First>>` is `true`, returns `std::get<0>(x.current_) == ranges::end(std::get<0>(x.parent_->bases_))`.

   > > 2. (?.2) — Otherwise, `true` if `std::get<i>(x.current_) == ranges::end(std::get<i>(x.parent_->bases_))` is `true` for any integer `0 ≤ i ≤ sizeof...(Vs)`,; otherwise, `false` returns `true`.

   > > 3. (?.3) — Otherwise, returns `false`.