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

Section: 25.7.33.2 [range.cartesian.view] Status: Open Submitter: Tomasz Kamiński Opened: 2022-09-12 Last modified: 2023-02-07

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 25.7.33.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 25.7.33.3 [range.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.