Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4
On Thu, 27 Oct 2022 at 19:48, Patrick Palka via Libstdc++
wrote:
>
> On Thu, 27 Oct 2022, Patrick Palka wrote:
>
> > This also implements the proposed resolutions of the tentatively ready
> > LWG issues 3760 and 3761.
> >
> > I'm not sure how/if we should implement the recommended practice of:
> >
> > difference_type should be the smallest signed-integer-like type that
> > is sufficiently wide to store the product of the maximum sizes of all
> > underlying ranges if such a type exists
> >
> > because for e.g.
> >
> > extern std::vector x, y;
> > auto v = views::cartesian_product(x, y);
> >
> > IIUC it'd mean difference_type should be __int128 or so, which seems
> > quite wasteful: in practice the size of the cartesian product probably
> > won't exceed the precision of say ptrdiff_t, and it's probably also not
> > worth adding logic for using less precision than that either. So this
> > patch chooses defines difference_type as
> >
> > common_type_t,
> > range_difference_t<_Vs>...>
> >
> > which should mean it's least as large as the difference_type of each
> > underlying range, and at least as large as ptrdiff_t. If overflow
> > occurs due to this choice of difference_type, this patch has debug mode
s/debug mode/assertions/ here I think, as _GLIBCXX_ASSERTIONS works
without the rest of debug mode.
Otherwise, the v2 patch looks good. OK for trunk, thanks!
> > checks to catch this.
> >
> > Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> >
> > libstdc++-v3/ChangeLog:
> >
> > * include/std/ranges (__maybe_const_t): New alias for
> > __detail::__maybe_const_t.
> > (__detail::__cartesian_product_is_random_access): Define.
> > (__detail::__cartesian_product_common_arg): Define.
> > (__detail::__cartesian_product_is_bidirectional): Define.
> > (__detail::__cartesian_product_is_common): Define.
> > (__detail::__cartesian_product_is_sized): Define.
> > (__detail::__cartesian_is_sized_sentinel): Define.
> > (__detail::__cartesian_common_arg_end): Define.
> > (cartesian_product_view): Define.
> > (cartesian_product_view::_Iterator): Define.
> > (views::__detail::__can_cartesian_product_view): Define.
> > (views::_Cartesian_product, views::cartesian_product): Define.
> > * testsuite/std/ranges/cartesian_product/1.cc: New test.
> > ---
> > libstdc++-v3/include/std/ranges | 500 ++
> > .../std/ranges/cartesian_product/1.cc | 162 ++
> > 2 files changed, 662 insertions(+)
> > create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> >
> > diff --git a/libstdc++-v3/include/std/ranges
> > b/libstdc++-v3/include/std/ranges
> > index a55e9e7f760..771da97ed6d 100644
> > --- a/libstdc++-v3/include/std/ranges
> > +++ b/libstdc++-v3/include/std/ranges
> > @@ -829,6 +829,9 @@ namespace __detail
> >
> > } // namespace __detail
> >
> > +// Shorthand for __detail::__maybe_const_t.
> > +using __detail::__maybe_const_t;
> > +
> > namespace views::__adaptor
> > {
> >// True if the range adaptor _Adaptor can be applied with _Args.
> > @@ -7973,6 +7976,503 @@ namespace views::__adaptor
> >
> > inline constexpr _Stride stride;
> >}
> > +
> > + namespace __detail
> > + {
> > +template
> > + concept __cartesian_product_is_random_access
> > + = (random_access_range<__maybe_const_t<_Const, _First>>
> > +&& ...
> > +&& (random_access_range<__maybe_const_t<_Const, _Vs>>
> > +&& sized_range<__maybe_const_t<_Const, _Vs>>));
> > +
> > +template
> > + concept __cartesian_product_common_arg = common_range<_Range>
> > + || (sized_range<_Range> && random_access_range<_Range>);
> > +
> > +template
> > + concept __cartesian_product_is_bidirectional
> > + = (bidirectional_range<__maybe_const_t<_Const, _First>>
> > +&& ...
> > +&& (bidirectional_range<__maybe_const_t<_Const, _Vs>>
> > +&& __cartesian_product_common_arg<__maybe_const_t<_Const,
> > _Vs>>));
> > +
> > +template
> > + concept __cartesian_product_is_common =
> > __cartesian_product_common_arg<_First>;
> > +
> > +template
> > + concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
> > +
> > +template class FirstSent, typename
> > _First, typename... _Vs>
> > + concept __cartesian_is_sized_sentinel
> > + = (sized_sentinel_for>,
> > + iterator_t<__maybe_const_t<_Const, _First>>>
> > + && ...
> > + && (sized_range<__maybe_const_t<_Const, _Vs>>
> > + && sized_sentinel_for>,
> > +iterator_t<__maybe_const_t<_Const,
> > _Vs>>>));
> > +
> > +template<__cartesian_product_common_arg _Range>
> > + constexpr auto
> > + __cartesian_common_arg_end(_Range& __r)
> > + {
> > + if constexpr (common_range<_Range>)
> > + return ranges::end(__r);
> > + else
> > +
Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4
On Thu, 27 Oct 2022, Patrick Palka wrote:
> On Thu, 27 Oct 2022, Patrick Palka wrote:
>
> > This also implements the proposed resolutions of the tentatively ready
> > LWG issues 3760 and 3761.
> >
> > I'm not sure how/if we should implement the recommended practice of:
> >
> > difference_type should be the smallest signed-integer-like type that
> > is sufficiently wide to store the product of the maximum sizes of all
> > underlying ranges if such a type exists
> >
> > because for e.g.
> >
> > extern std::vector x, y;
> > auto v = views::cartesian_product(x, y);
> >
> > IIUC it'd mean difference_type should be __int128 or so, which seems
> > quite wasteful: in practice the size of the cartesian product probably
> > won't exceed the precision of say ptrdiff_t, and it's probably also not
> > worth adding logic for using less precision than that either. So this
> > patch chooses defines difference_type as
> >
> > common_type_t,
> > range_difference_t<_Vs>...>
> >
> > which should mean it's least as large as the difference_type of each
> > underlying range, and at least as large as ptrdiff_t. If overflow
> > occurs due to this choice of difference_type, this patch has debug mode
> > checks to catch this.
> >
> > Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> >
> > libstdc++-v3/ChangeLog:
> >
> > * include/std/ranges (__maybe_const_t): New alias for
> > __detail::__maybe_const_t.
> > (__detail::__cartesian_product_is_random_access): Define.
> > (__detail::__cartesian_product_common_arg): Define.
> > (__detail::__cartesian_product_is_bidirectional): Define.
> > (__detail::__cartesian_product_is_common): Define.
> > (__detail::__cartesian_product_is_sized): Define.
> > (__detail::__cartesian_is_sized_sentinel): Define.
> > (__detail::__cartesian_common_arg_end): Define.
> > (cartesian_product_view): Define.
> > (cartesian_product_view::_Iterator): Define.
> > (views::__detail::__can_cartesian_product_view): Define.
> > (views::_Cartesian_product, views::cartesian_product): Define.
> > * testsuite/std/ranges/cartesian_product/1.cc: New test.
> > ---
> > libstdc++-v3/include/std/ranges | 500 ++
> > .../std/ranges/cartesian_product/1.cc | 162 ++
> > 2 files changed, 662 insertions(+)
> > create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> >
> > diff --git a/libstdc++-v3/include/std/ranges
> > b/libstdc++-v3/include/std/ranges
> > index a55e9e7f760..771da97ed6d 100644
> > --- a/libstdc++-v3/include/std/ranges
> > +++ b/libstdc++-v3/include/std/ranges
> > @@ -829,6 +829,9 @@ namespace __detail
> >
> > } // namespace __detail
> >
> > +// Shorthand for __detail::__maybe_const_t.
> > +using __detail::__maybe_const_t;
> > +
> > namespace views::__adaptor
> > {
> >// True if the range adaptor _Adaptor can be applied with _Args.
> > @@ -7973,6 +7976,503 @@ namespace views::__adaptor
> >
> > inline constexpr _Stride stride;
> >}
> > +
> > + namespace __detail
> > + {
> > +template
> > + concept __cartesian_product_is_random_access
> > + = (random_access_range<__maybe_const_t<_Const, _First>>
> > + && ...
> > + && (random_access_range<__maybe_const_t<_Const, _Vs>>
> > + && sized_range<__maybe_const_t<_Const, _Vs>>));
> > +
> > +template
> > + concept __cartesian_product_common_arg = common_range<_Range>
> > + || (sized_range<_Range> && random_access_range<_Range>);
> > +
> > +template
> > + concept __cartesian_product_is_bidirectional
> > + = (bidirectional_range<__maybe_const_t<_Const, _First>>
> > + && ...
> > + && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
> > + && __cartesian_product_common_arg<__maybe_const_t<_Const,
> > _Vs>>));
> > +
> > +template
> > + concept __cartesian_product_is_common =
> > __cartesian_product_common_arg<_First>;
> > +
> > +template
> > + concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
> > +
> > +template class FirstSent, typename
> > _First, typename... _Vs>
> > + concept __cartesian_is_sized_sentinel
> > + = (sized_sentinel_for>,
> > + iterator_t<__maybe_const_t<_Const, _First>>>
> > +&& ...
> > +&& (sized_range<__maybe_const_t<_Const, _Vs>>
> > +&& sized_sentinel_for>,
> > + iterator_t<__maybe_const_t<_Const, _Vs>>>));
> > +
> > +template<__cartesian_product_common_arg _Range>
> > + constexpr auto
> > + __cartesian_common_arg_end(_Range& __r)
> > + {
> > + if constexpr (common_range<_Range>)
> > + return ranges::end(__r);
> > + else
> > + return ranges::begin(__r) + ranges::distance(__r);
> > + }
> > + } // namespace __detail
> > +
> > + template
> > +requires (view<_First> && ... && view<_Vs>)
> > + class cartesian_product_view : public
> > view_interface>
> > +
Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4
On Thu, 27 Oct 2022, Patrick Palka wrote:
> This also implements the proposed resolutions of the tentatively ready
> LWG issues 3760 and 3761.
>
> I'm not sure how/if we should implement the recommended practice of:
>
> difference_type should be the smallest signed-integer-like type that
> is sufficiently wide to store the product of the maximum sizes of all
> underlying ranges if such a type exists
>
> because for e.g.
>
> extern std::vector x, y;
> auto v = views::cartesian_product(x, y);
>
> IIUC it'd mean difference_type should be __int128 or so, which seems
> quite wasteful: in practice the size of the cartesian product probably
> won't exceed the precision of say ptrdiff_t, and it's probably also not
> worth adding logic for using less precision than that either. So this
> patch chooses defines difference_type as
>
> common_type_t,
> range_difference_t<_Vs>...>
>
> which should mean it's least as large as the difference_type of each
> underlying range, and at least as large as ptrdiff_t. If overflow
> occurs due to this choice of difference_type, this patch has debug mode
> checks to catch this.
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
>
> libstdc++-v3/ChangeLog:
>
> * include/std/ranges (__maybe_const_t): New alias for
> __detail::__maybe_const_t.
> (__detail::__cartesian_product_is_random_access): Define.
> (__detail::__cartesian_product_common_arg): Define.
> (__detail::__cartesian_product_is_bidirectional): Define.
> (__detail::__cartesian_product_is_common): Define.
> (__detail::__cartesian_product_is_sized): Define.
> (__detail::__cartesian_is_sized_sentinel): Define.
> (__detail::__cartesian_common_arg_end): Define.
> (cartesian_product_view): Define.
> (cartesian_product_view::_Iterator): Define.
> (views::__detail::__can_cartesian_product_view): Define.
> (views::_Cartesian_product, views::cartesian_product): Define.
> * testsuite/std/ranges/cartesian_product/1.cc: New test.
> ---
> libstdc++-v3/include/std/ranges | 500 ++
> .../std/ranges/cartesian_product/1.cc | 162 ++
> 2 files changed, 662 insertions(+)
> create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
>
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index a55e9e7f760..771da97ed6d 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -829,6 +829,9 @@ namespace __detail
>
> } // namespace __detail
>
> +// Shorthand for __detail::__maybe_const_t.
> +using __detail::__maybe_const_t;
> +
> namespace views::__adaptor
> {
>// True if the range adaptor _Adaptor can be applied with _Args.
> @@ -7973,6 +7976,503 @@ namespace views::__adaptor
>
> inline constexpr _Stride stride;
>}
> +
> + namespace __detail
> + {
> +template
> + concept __cartesian_product_is_random_access
> + = (random_access_range<__maybe_const_t<_Const, _First>>
> +&& ...
> +&& (random_access_range<__maybe_const_t<_Const, _Vs>>
> +&& sized_range<__maybe_const_t<_Const, _Vs>>));
> +
> +template
> + concept __cartesian_product_common_arg = common_range<_Range>
> + || (sized_range<_Range> && random_access_range<_Range>);
> +
> +template
> + concept __cartesian_product_is_bidirectional
> + = (bidirectional_range<__maybe_const_t<_Const, _First>>
> +&& ...
> +&& (bidirectional_range<__maybe_const_t<_Const, _Vs>>
> +&& __cartesian_product_common_arg<__maybe_const_t<_Const,
> _Vs>>));
> +
> +template
> + concept __cartesian_product_is_common =
> __cartesian_product_common_arg<_First>;
> +
> +template
> + concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
> +
> +template class FirstSent, typename
> _First, typename... _Vs>
> + concept __cartesian_is_sized_sentinel
> + = (sized_sentinel_for>,
> + iterator_t<__maybe_const_t<_Const, _First>>>
> + && ...
> + && (sized_range<__maybe_const_t<_Const, _Vs>>
> + && sized_sentinel_for>,
> +iterator_t<__maybe_const_t<_Const, _Vs>>>));
> +
> +template<__cartesian_product_common_arg _Range>
> + constexpr auto
> + __cartesian_common_arg_end(_Range& __r)
> + {
> + if constexpr (common_range<_Range>)
> + return ranges::end(__r);
> + else
> + return ranges::begin(__r) + ranges::distance(__r);
> + }
> + } // namespace __detail
> +
> + template
> +requires (view<_First> && ... && view<_Vs>)
> + class cartesian_product_view : public
> view_interface>
> + {
> +tuple<_First, _Vs...> _M_bases;
> +
> +template class _Iterator;
> +
> +static auto
> +_S_difference_type()
> +{
> + // TODO: Implement the recommended practice of using the smallest
> + //
