Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[range.cartesian.view] Fix cartesian-product-is-common #5768

Closed
wants to merge 2 commits into from

Conversation

hewillk
Copy link
Contributor

@hewillk hewillk commented Aug 22, 2022

I think this should be correct.
(In fact, I implemented cartesian_product_view after the pre-version p2374r3 was published. From my experience, the constraints here should only be aimed at First)

@hewillk hewillk changed the title [range.cartesian.view] Simplify cartesian-product-is-common [range.cartesian.view] Fix cartesian-product-is-common Aug 22, 2022
@tkoeppe
Copy link
Contributor

tkoeppe commented Aug 22, 2022

This feels like it needs an LWG issue. Could you please file one?

@tkoeppe tkoeppe added the lwg Issue must be reviewed by LWG. label Aug 22, 2022
@hewillk
Copy link
Contributor Author

hewillk commented Aug 22, 2022

I don't think it's worth LWG.
The main consideration here is that the definition of cartesian-product-is-common in the original paper P2374R4 is as follows

template <class R>
  concept cartesian-product-common-arg = // exposition only
    common_range<R> || (sized_range<R> && random_access_range<R>);

template <class First, class... Vs>
  concept cartesian-product-is-common = // exposition only
    cartesian-product-common-arg<Const, First>>;

This is mentioned in #5750, and the reporter believes that the intent of the paper should have been to define it as

template<class First, class... Vs>
  concept cartesian-product-is-common =                 // exposition only
    (cartesian-product-common-arg<First> && ... &&
     cartesian-product-common-arg<Vs>);

which has been merged into the draft.

However, according to the description of common_range in Section 3.5 of the paper

cartesian_product_view can be a common range if the first range either is common, or is sized and random access. This paper reflects this.

And according to the implementation section of the paper for cartesian_product_view::end in [range.cartesian.view]

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...>;

Let:
(4.1) is-const be true for the const-qualified overload, and false otherwise;
(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.3) begin-or-first-end(rng) be expression-equivalent to is-empty ? ranges​::​begin(rng) : cartesian-common-arg-end(rng) if rng is the first underlying range and ranges​::​begin(rng) otherwise.
Effects: Equivalent to:

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

From the above context derivation, the merged fix is obviously not the intention of the paper. I think the fix that is closest to the intention of the paper should be

template <class First, class... Vs>
  concept cartesian-product-is-common = // exposition only
    cartesian-product-common-arg<First>;

And this pull request just removes the unused Vs... part of the template parameter list.

Can we ask the author for their opinion?

@jwakely
Copy link
Member

jwakely commented Aug 22, 2022

Can we ask the author for their opinion?

Paging @griwes and @TartanLlama

My feeling is that this needs an LWG issue.

@tkoeppe
Copy link
Contributor

tkoeppe commented Aug 22, 2022

See 8275c19 for the previous editorial-deemed fix, but we should take a closer look.

@griwes
Copy link

griwes commented Aug 22, 2022

No, the words in the paper are not a mistake. We only use a sentinel for the first range in the end iterator; for the rest of the ranges, we use an iterator, because in the end iterator we are storing begin(), not end(). So only the first range needs to be common for cartesian product to be common.

@tkoeppe
Copy link
Contributor

tkoeppe commented Aug 22, 2022

@griwes: Thanks! What about the Vs... in the original wording then?

@griwes
Copy link

griwes commented Aug 22, 2022

Oh, though it seems the paper was missing maybe-const in this concept?

Scratch that, we don't have a Const argument for this concept, I believe this maybe-const is done by the users of this concept.

@griwes
Copy link

griwes commented Aug 22, 2022

As for Vs..., I believe it's there to be consistent with the other helper concepts of cartesian product, because everywhere else we're passing around all the ranges.

@tkoeppe
Copy link
Contributor

tkoeppe commented Aug 22, 2022

@griwes Right, the initial issue #5735 by @JohelEGP was complaining both about the Const and the unused Vs..., my 8275c19 was an attempted "fix". But it sounds like that was wrong?

@tkoeppe
Copy link
Contributor

tkoeppe commented Aug 22, 2022

@griwes Would you perhaps be able to send a PR with the correct and intended wording?

@griwes
Copy link

griwes commented Aug 22, 2022

Not at the present, I'm on vacation :) I believe the intented wording shouldn't have the const part, but it also should use the common-arg helper concept only on the first argument. I'd also be happy to have an LWG discussion as to whether we should drop the parameter pack from is-common or not.

@tkoeppe
Copy link
Contributor

tkoeppe commented Aug 22, 2022

OK, I can make that change. So we go back to the original, but drop the Const?

@griwes
Copy link

griwes commented Aug 22, 2022

Yeah, that sounds correct to me.

@jwakely
Copy link
Member

jwakely commented Aug 22, 2022

@griwes, thanks for taking the time out from your vacation to advise.

@hewillk
Copy link
Contributor Author

hewillk commented Aug 22, 2022

As for Vs..., I believe it's there to be consistent with the other helper concepts of cartesian product, because everywhere else we're passing around all the ranges.

This is as I guessed.

I'd also be happy to have an LWG discussion as to whether we should drop the parameter pack from is-common or not.

template <class First, class... Vs>
  concept cartesian-product-is-common = // exposition only
    cartesian-product-common-arg<First>;

In fact, at first glance, I thought it was an editing error because it looks like the fold expression was left out, which is why it was removed from the pull request since I believe this will reduce confusion for people who haven't read the original paper.
If we consider keeps them, I think a more appropriate option would be to not name the rest packs like

template <class First, class...>
  concept cartesian-product-is-common = // exposition only
    cartesian-product-common-arg<First>;

This more clearly expresses the intent of ignoring non-first views.

@hewillk hewillk deleted the main-cartesian-common branch August 23, 2022 05:43
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
lwg Issue must be reviewed by LWG.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

4 participants