From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id B6648385802A for ; Mon, 7 Nov 2022 14:12:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B6648385802A Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1667830373; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=f+dR52C4uw9rBnFoWhZuFqn/E6Y3BwdoADpgifcaLNA=; b=MafzqKM+TzJW0iYuJv+P4EY+pccIigOTJ+vmHPmriPWGBA13Xqe7XqYIJDGOFt8l1TsP0p ImcXewJOquN/ytsuz9LTkYxew1lJaUic6P9ItVmqkZ+ULwkEKvtnZXDcWvzlscTCxxkd4D qvw2KINKeV556QVYl5KDIuZcqPnfRKw= Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-115-0x_IKogKOJSslQ5BFNBFgg-1; Mon, 07 Nov 2022 09:12:52 -0500 X-MC-Unique: 0x_IKogKOJSslQ5BFNBFgg-1 Received: by mail-qk1-f200.google.com with SMTP id bm2-20020a05620a198200b006fa6eeee4a9so10228403qkb.14 for ; Mon, 07 Nov 2022 06:12:52 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:references:message-id:in-reply-to:subject:cc:to:date :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=f+dR52C4uw9rBnFoWhZuFqn/E6Y3BwdoADpgifcaLNA=; b=w/VXEKlRl91bECruwyUmSjHlGr/ULuGVXqWsiGYMZtng3pe5kZMZNfYfPIwdyxmYzD iELB0YY5GRHBr+XQHzAQDixhmaum9RtPY0+pQXB30EB7VtgD1KBRkXvKUhLLbKqRJ8PJ lWrRNGzz8aEpyT6XodyM+nf8AxsQkZy14IKzXkdHc2tvv6FTbf5sluwMZY5YZnzOz6fo OZxmAgu2UJr3fTguVstUXtnvUMvUu/oDu8KL9bu3786AzC8HEMvQtrfnBRvLfEdhkt8P NY6lR939Kna1zOwzetymipxh5Td4UWSTEJ8iVzJO1h8n8VHtbMWJgU6vU2YILuW10DRs 8YfA== X-Gm-Message-State: ACrzQf1JSnxu/cdDUvADDzF3umDmU2oy9tWfJC6kLTxlvAK6mTDW8vXS XVhClq/Qll1FaDDv2ou69biF2fhZp69hQAZpHgXwsfhJwalszyNVgCQOQ2RI8rwAhe09SOijO3F fYCDYhPmujNvcZxA= X-Received: by 2002:a0c:90a2:0:b0:47b:6b36:f94a with SMTP id p31-20020a0c90a2000000b0047b6b36f94amr45248303qvp.26.1667830371347; Mon, 07 Nov 2022 06:12:51 -0800 (PST) X-Google-Smtp-Source: AMsMyM4PFHYJK7oWCSr6Jia2OYcHxlxbqAK1TNskuPFMi6s/9Jn3T2T6LDEBJWg27382UBDIkfbKAw== X-Received: by 2002:a0c:90a2:0:b0:47b:6b36:f94a with SMTP id p31-20020a0c90a2000000b0047b6b36f94amr45248252qvp.26.1667830370886; Mon, 07 Nov 2022 06:12:50 -0800 (PST) Received: from [192.168.1.130] (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id w27-20020a05620a0e9b00b006ee949b8051sm6754275qkm.51.2022.11.07.06.12.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Nov 2022 06:12:50 -0800 (PST) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Mon, 7 Nov 2022 09:12:49 -0500 (EST) To: Patrick Palka cc: gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Subject: Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4 In-Reply-To: <91ff0d4c-0a29-c9e1-2872-d07cde50fbde@idea> Message-ID: References: <20221027164750.97737-1-ppalka@redhat.com> <91ff0d4c-0a29-c9e1-2872-d07cde50fbde@idea> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-13.6 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,KAM_NUMSUBJECT,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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> > > + { > > + tuple<_First, _Vs...> _M_bases; > > + > > + template class _Iterator; > > + > > + static auto > > + _S_difference_type() > > + { > > + // TODO: Implement the recommended practice of using the smallest > > + // sufficiently wide type according to the maximum sizes of the > > + // underlying ranges? > > + return common_type_t > + range_difference_t<_First>, > > + range_difference_t<_Vs>...>{}; > > + } > > + > > + public: > > + cartesian_product_view() = default; > > + > > + constexpr explicit > > + cartesian_product_view(_First __first, _Vs... __rest) > > + : _M_bases(std::move(__first), std::move(__rest)...) > > + { } > > + > > + constexpr _Iterator > > + begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>) > > + { return _Iterator(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); } > > + > > + constexpr _Iterator > > + begin() const requires (range && ... && range) > > + { return _Iterator(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); } > > + > > + constexpr _Iterator > > + end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>) > > + && __detail::__cartesian_product_is_common<_First, _Vs...>) > > + { > > + bool __empty_tail = [this](index_sequence<_Is...>) { > > + return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...); > > + }(make_index_sequence{}); > > + > > + auto __it = __detail::__tuple_transform(ranges::begin, _M_bases); > > + if (!__empty_tail) > > + std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases)); > > + return _Iterator{*this, std::move(__it)}; > > + } > > + > > + constexpr _Iterator > > + end() const requires __detail::__cartesian_product_is_common > > + { > > + bool __empty_tail = [this](index_sequence<_Is...>) { > > + return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...); > > + }(make_index_sequence{}); > > + > > + auto __it = __detail::__tuple_transform(ranges::begin, _M_bases); > > + if (!__empty_tail) > > + std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases)); > > + return _Iterator{*this, std::move(__it)}; > > + } > > + > > + constexpr default_sentinel_t > > + end() const noexcept > > + { return default_sentinel; } > > + > > + constexpr auto > > + size() requires __detail::__cartesian_product_is_sized<_First, _Vs...> > > + { > > + using _ST = __detail::__make_unsigned_like_t; > > + return [&](index_sequence<_Is...>) { > > +#ifdef _GLIBCXX_ASSERTIONS > > + _ST __sz = 1; > > + bool __overflow > > + = (__builtin_mul_overflow(__sz, > > + static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))), > > + &__sz) > > + || ...); > > + __glibcxx_assert(!__overflow); > > + return __sz; > > __builtin_add/mul_overflow can't handle integer-class types so these > debug-mode checks must be disabled for such types. Here's v2 which > corrects and adds a test for the case where the difference type is > an integer-class type: Ping. > > -- >8 -- > > Subject: [PATCH] libstdc++: Implement ranges::cartesian_product_view from > P2374R4 > > 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 | 515 ++++++++++++++++++ > .../std/ranges/cartesian_product/1.cc | 178 ++++++ > 2 files changed, 693 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..92d15c81e51 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,518 @@ 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 > + // sufficiently wide type according to the maximum sizes of the > + // underlying ranges? > + return common_type_t + range_difference_t<_First>, > + range_difference_t<_Vs>...>{}; > + } > + > + public: > + cartesian_product_view() = default; > + > + constexpr explicit > + cartesian_product_view(_First __first, _Vs... __rest) > + : _M_bases(std::move(__first), std::move(__rest)...) > + { } > + > + constexpr _Iterator > + begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>) > + { return _Iterator(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); } > + > + constexpr _Iterator > + begin() const requires (range && ... && range) > + { return _Iterator(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); } > + > + constexpr _Iterator > + end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>) > + && __detail::__cartesian_product_is_common<_First, _Vs...>) > + { > + bool __empty_tail = [this](index_sequence<_Is...>) { > + return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...); > + }(make_index_sequence{}); > + > + auto __it = __detail::__tuple_transform(ranges::begin, _M_bases); > + if (!__empty_tail) > + std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases)); > + return _Iterator{*this, std::move(__it)}; > + } > + > + constexpr _Iterator > + end() const requires __detail::__cartesian_product_is_common > + { > + bool __empty_tail = [this](index_sequence<_Is...>) { > + return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...); > + }(make_index_sequence{}); > + > + auto __it = __detail::__tuple_transform(ranges::begin, _M_bases); > + if (!__empty_tail) > + std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases)); > + return _Iterator{*this, std::move(__it)}; > + } > + > + constexpr default_sentinel_t > + end() const noexcept > + { return default_sentinel; } > + > + constexpr auto > + size() requires __detail::__cartesian_product_is_sized<_First, _Vs...> > + { > + using _ST = __detail::__make_unsigned_like_t; > + return [&](index_sequence<_Is...>) { > + auto __size = static_cast<_ST>(1); > +#ifdef _GLIBCXX_ASSERTIONS > + if constexpr (integral<_ST>) > + { > + bool __overflow > + = (__builtin_mul_overflow(__size, > + static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))), > + &__size) > + || ...); > + __glibcxx_assert(!__overflow); > + } > + else > +#endif > + __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...); > + return __size; > + }(make_index_sequence<1 + sizeof...(_Vs)>{}); > + } > + > + constexpr auto > + size() const requires __detail::__cartesian_product_is_sized > + { > + using _ST = __detail::__make_unsigned_like_t; > + return [&](index_sequence<_Is...>) { > + auto __size = static_cast<_ST>(1); > +#ifdef _GLIBCXX_ASSERTIONS > + if constexpr (integral<_ST>) > + { > + bool __overflow > + = (__builtin_mul_overflow(__size, > + static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))), > + &__size) > + || ...); > + __glibcxx_assert(!__overflow); > + } > + else > +#endif > + __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...); > + return __size; > + }(make_index_sequence<1 + sizeof...(_Vs)>{}); > + } > + }; > + > + template > + cartesian_product_view(_Vs&&...) -> cartesian_product_view...>; > + > + template > + requires (view<_First> && ... && view<_Vs>) > + template > + class cartesian_product_view<_First, _Vs...>::_Iterator > + { > + using _Parent = __maybe_const_t<_Const, cartesian_product_view>; > + _Parent* _M_parent = nullptr; > + __detail::__tuple_or_pair_t>, > + iterator_t<__maybe_const_t<_Const, _Vs>>...> _M_current; > + > + template > + constexpr void > + _M_next() > + { > + auto& __it = std::get<_Nm>(_M_current); > + ++__it; > + if constexpr (_Nm > 0) > + if (__it == ranges::end(std::get<_Nm>(_M_parent->_M_bases))) > + { > + __it = ranges::begin(std::get<_Nm>(_M_parent->_M_bases)); > + _M_next<_Nm - 1>(); > + } > + } > + > + template > + constexpr void > + _M_prev() > + { > + auto& __it = std::get<_Nm>(_M_current); > + if (__it == ranges::begin(std::get<_Nm>(_M_parent->_M_bases))) > + { > + __it = __detail::__cartesian_common_arg_end(std::get<_Nm>(_M_parent->_M_bases)); > + if constexpr (_Nm > 0) > + _M_prev<_Nm - 1>(); > + } > + --__it; > + } > + > + constexpr > + _Iterator(_Parent& __parent, decltype(_M_current) __current) > + : _M_parent(std::__addressof(__parent)), > + _M_current(std::move(__current)) > + { } > + > + static auto > + _S_iter_concept() > + { > + if constexpr (__detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>) > + return random_access_iterator_tag{}; > + else if constexpr (__detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>) > + return bidirectional_iterator_tag{}; > + else if constexpr (forward_range<__maybe_const_t<_Const, _First>>) > + return forward_iterator_tag{}; > + else > + return input_iterator_tag{}; > + } > + > + friend cartesian_product_view; > + > + public: > + using iterator_category = input_iterator_tag; > + using iterator_concept = decltype(_S_iter_concept()); > + using value_type > + = __detail::__tuple_or_pair_t>, > + range_value_t<__maybe_const_t<_Const, _Vs>>...>; > + using reference > + = __detail::__tuple_or_pair_t>, > + range_reference_t<__maybe_const_t<_Const, _Vs>>...>; > + using difference_type = decltype(cartesian_product_view::_S_difference_type()); > + > + _Iterator() requires forward_range<__maybe_const_t<_Const, _First>> = default; > + > + constexpr > + _Iterator(_Iterator __i) > + requires _Const > + && (convertible_to, iterator_t> > + && ... && convertible_to, iterator_t>) > + : _M_parent(std::__addressof(__i._M_parent)), > + _M_current(std::move(__i._M_current)) > + { } > + > + constexpr auto > + operator*() const > + { > + auto __f = [](auto& __i) -> decltype(auto) { > + return *__i; > + }; > + return __detail::__tuple_transform(__f, _M_current); > + } > + > + constexpr _Iterator& > + operator++() > + { > + _M_next(); > + return *this; > + } > + > + constexpr void > + operator++(int) > + { ++*this; } > + > + constexpr _Iterator > + operator++(int) requires forward_range<__maybe_const_t<_Const, _First>> > + { > + auto __tmp = *this; > + ++*this; > + return __tmp; > + } > + > + constexpr _Iterator& > + operator--() > + requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...> > + { > + _M_prev(); > + return *this; > + } > + > + constexpr _Iterator > + operator--(int) > + requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...> > + { > + auto __tmp = *this; > + --*this; > + return __tmp; > + } > + > + private: > + template > + constexpr void > + _M_advance(difference_type __x) > + requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> > + { > + if (__x == 1) > + _M_next<_Nm>(); > + else if (__x == -1) > + _M_prev<_Nm>(); > + else if (__x != 0) > + { > + // Constant time iterator addition. > + auto& __r = std::get<_Nm>(_M_parent->_M_bases); > + auto& __it = std::get<_Nm>(_M_current); > + if constexpr (_Nm == 0) > + { > +#ifdef _GLIBCXX_ASSERTIONS > + auto __size = ranges::ssize(__r); > + auto __begin = ranges::begin(__r); > + auto __offset = __it - __begin; > + __glibcxx_assert(__offset + __x >= 0 && __offset + __x <= __size); > +#endif > + __it += __x; > + } > + else > + { > + auto __size = ranges::ssize(__r); > + auto __begin = ranges::begin(__r); > + auto __offset = __it - __begin; > + __offset += __x; > + __x = __offset / __size; > + __offset %= __size; > + if (__offset < 0) > + { > + __offset = __size + __offset; > + --__x; > + } > + __it = __begin + __offset; > + _M_advance<_Nm - 1>(__x); > + } > + } > + } > + > + public: > + constexpr _Iterator& > + operator+=(difference_type __x) > + requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> > + { > + _M_advance(__x); > + return *this; > + } > + > + constexpr _Iterator& > + operator-=(difference_type __x) > + requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> > + { return *this += -__x; } > + > + constexpr reference > + operator[](difference_type __n) const > + requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> > + { return *((*this) + __n); } > + > + friend constexpr bool > + operator==(const _Iterator& __x, const _Iterator& __y) > + requires equality_comparable>> > + { return __x._M_current == __y._M_current; } > + > + friend constexpr bool > + operator==(const _Iterator& __x, default_sentinel_t) > + { > + return [&](index_sequence<_Is...>) { > + return ((std::get<_Is>(__x._M_current) > + == ranges::end(std::get<_Is>(__x._M_parent->_M_bases))) > + || ...); > + }(make_index_sequence<1 + sizeof...(_Vs)>{}); > + } > + > + friend constexpr auto > + operator<=>(const _Iterator& __x, const _Iterator& __y) > + requires __detail::__all_random_access<_Const, _First, _Vs...> > + { return __x._M_current <=> __y._M_current; } > + > + friend constexpr _Iterator > + operator+(_Iterator __x, difference_type __y) > + requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> > + { return __x += __y; } > + > + friend constexpr _Iterator > + operator+(difference_type __x, const _Iterator& __y) > + requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> > + { return __y + __x; } > + > + friend constexpr _Iterator > + operator-(_Iterator __x, difference_type __y) > + requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...> > + { return __x -= __y; } > + > + friend constexpr difference_type > + operator-(const _Iterator& __x, const _Iterator& __y) > + requires __detail::__cartesian_is_sized_sentinel<_Const, iterator_t, _First, _Vs...> > + { return __x._M_distance_from(__y._M_current); } > + > + friend constexpr difference_type > + operator-(const _Iterator& __i, default_sentinel_t) > + requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...> > + { > + tuple __end_tuple = [&](index_sequence<_Is...>) { > + return tuple{ranges::end(std::get<0>(__i._M_parent->_M_bases)), > + ranges::begin(std::get<1 + _Is>(__i._M_parent->_M_bases))...}; > + }(make_index_sequence{}); > + return __i._M_distance_from(__end_tuple); > + } > + > + friend constexpr difference_type > + operator-(default_sentinel_t, const _Iterator& __i) > + requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...> > + { return -(__i - default_sentinel); } > + > + friend constexpr auto > + iter_move(const _Iterator& __i) > + { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); } > + > + friend constexpr void > + iter_swap(const _Iterator& __l, const _Iterator& __r) > + requires (indirectly_swappable>> > + && ... > + && indirectly_swappable>>) > + { > + [&](index_sequence<_Is...>) { > + (ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...); > + }(make_index_sequence<1 + sizeof...(_Vs)>{}); > + } > + > + private: > + template > + constexpr difference_type > + _M_distance_from(const _Tuple& __t) const > + { > + return [&](index_sequence<_Is...>) { > + auto __sum = static_cast(0); > +#ifdef _GLIBCXX_ASSERTIONS > + if constexpr (integral) > + { > + bool __overflow > + = (__builtin_add_overflow(__sum, _M_scaled_distance<_Is>(__t), &__sum) > + || ...); > + __glibcxx_assert(!__overflow); > + } > + else > +#endif > + __sum = (_M_scaled_distance<_Is>(__t) + ...); > + return __sum; > + }(make_index_sequence<1 + sizeof...(_Vs)>{}); > + } > + > + template > + constexpr difference_type > + _M_scaled_distance(const _Tuple& __t) const > + { > + auto __dist = static_cast(std::get<_Nm>(_M_current) > + - std::get<_Nm>(__t)); > +#ifdef _GLIBCXX_ASSERTIONS > + if constexpr (integral) > + { > + bool __overflow = __builtin_mul_overflow(__dist, _M_scaled_size<_Nm+1>(), &__dist); > + __glibcxx_assert(!__overflow); > + } > + else > +#endif > + __dist *= _M_scaled_size<_Nm+1>(); > + return __dist; > + } > + > + template > + constexpr difference_type > + _M_scaled_size() const > + { > + if constexpr (_Nm <= sizeof...(_Vs)) > + { > + auto __size = static_cast(ranges::size > + (std::get<_Nm>(_M_parent->_M_bases))); > +#ifdef _GLIBCXX_ASSERTIONS > + if constexpr (integral) > + { > + bool __overflow = __builtin_mul_overflow(__size, _M_scaled_size<_Nm+1>(), &__size); > + __glibcxx_assert(!__overflow); > + } > + else > +#endif > + __size *= _M_scaled_size<_Nm+1>(); > + return __size; > + } > + else > + return static_cast(1); > + } > + }; > + > + namespace views > + { > + namespace __detail > + { > + template > + concept __can_cartesian_product_view > + = requires { cartesian_product_view...>(std::declval<_Ts>()...); }; > + } > + > + struct _CartesianProduct > + { > + template > + requires (sizeof...(_Ts) == 0 || __detail::__can_cartesian_product_view<_Ts...>) > + constexpr auto > + operator() [[nodiscard]] (_Ts&&... __ts) const > + { > + if constexpr (sizeof...(_Ts) == 0) > + return views::empty>; > + else > + return cartesian_product_view...>(std::forward<_Ts>(__ts)...); > + } > + }; > + > + inline constexpr _CartesianProduct cartesian_product; > + } > #endif // C++23 > } // namespace ranges > > diff --git a/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc > new file mode 100644 > index 00000000000..5f1610d6458 > --- /dev/null > +++ b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc > @@ -0,0 +1,178 @@ > +// { dg-options "-std=gnu++23" } > +// { dg-do run { target c++23 } } > + > +#include > +#include > +#include > +#include > +#include > + > +namespace ranges = std::ranges; > +namespace views = std::views; > + > +constexpr bool > +test01() > +{ > + int x[] = {1, 2, 3}; > + int y[] = {4, 5, 6}; > + int z[] = {7, 8}; > + int w[] = {9}; > + > + auto v0 = views::cartesian_product(); > + VERIFY( ranges::end(v0) - ranges::begin(v0) == 0 ); > + VERIFY( ranges::size(v0) == 0 ); > + VERIFY( ranges::empty(v0) ); > + > + auto v1 = views::cartesian_product(x); > + VERIFY( ranges::end(v1) - ranges::begin(v1) == 3 ); > + VERIFY( ranges::size(v1) == 3 ); > + VERIFY( ranges::equal(v1 | views::keys, x) ); > + VERIFY( std::get<0>(v1[0]) == 1 ); > + VERIFY( std::get<0>(v1[1]) == 2 ); > + VERIFY( std::get<0>(v1[2]) == 3 ); > + VERIFY( ranges::equal(v1 | views::reverse | views::keys, x | views::reverse)); > + > + auto v2 = views::cartesian_product(x, y); > + VERIFY( ranges::size(v2) == 9 ); > + VERIFY( ranges::end(v2) - ranges::begin(v2) == 9 ); > + VERIFY( ranges::equal(v2 | views::keys, (int[]){1, 1, 1, 2, 2, 2, 3, 3, 3})); > + VERIFY( ranges::equal(v2 | views::values, (int[]){4, 5, 6, 4, 5, 6, 4, 5, 6})); > + VERIFY( ranges::equal(v2 | views::reverse | views::keys, (int[]){3, 3, 3, 2, 2, 2, 1, 1, 1}) ); > + VERIFY( ranges::equal(v2 | views::reverse | views::values, (int[]){6, 5, 4, 6, 5, 4, 6, 5, 4}) ); > + > + auto v3 = views::cartesian_product(x, y, z); > + VERIFY( ranges::size(v3) == 18 ); > + VERIFY( ranges::equal(v3, (std::tuple[]){{1,4,7}, {1,4,8}, {1,5,7}, {1,5,8}, > + {1,6,7}, {1,6,8}, {2,4,7}, {2,4,8}, > + {2,5,7}, {2,5,8}, {2,6,7}, {2,6,8}, > + {3,4,7}, {3,4,8}, {3,5,7}, {3,5,8}, > + {3,6,7}, {3,6,8}}) ); > + > + auto v4 = views::cartesian_product(x, y, z, w); > + VERIFY( ranges::size(v4) == 18 ); > + VERIFY( ranges::equal(v4 | views::elements<3>, views::repeat(9, 18)) ); > + > + auto i4 = v4.begin(), j4 = i4 + 1; > + VERIFY( j4 > i4 ); > + VERIFY( i4[0] == std::tuple(1, 4, 7, 9) ); > + VERIFY( i4 + 18 == v4.end() ); > + i4 += 5; > + VERIFY( i4 != v4.begin() ); > + VERIFY( i4 - 5 == v4.begin() ); > + VERIFY( *i4 == std::tuple(1, 6, 8, 9) ); > + VERIFY( i4 - 5 != i4 ); > + i4 -= 3; > + VERIFY( *i4 == std::tuple(1, 5, 7, 9) ); > + VERIFY( j4 + 1 == i4 ); > + ranges::iter_swap(i4, j4); > + VERIFY( *j4 == std::tuple(1, 5, 7, 9) ); > + VERIFY( *i4 == std::tuple(1, 4, 8, 9) ); > + > + return true; > +} > + > +void > +test02() > +{ > + int x[] = {1, 2}; > + __gnu_test::test_input_range rx(x); > + auto v = views::cartesian_product(rx, x); > + auto i = v.begin(); > + std::default_sentinel_t s = v.end(); > + VERIFY( i != s ); > + VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 1 ); > + ++i; > + VERIFY( i != s ); > + VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 2 ); > + ++i; > + VERIFY( i != s ); > + VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 1 ); > + ++i; > + VERIFY( i != s ); > + VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 2 ); > + ++i; > + VERIFY( i == s ); > +} > + > +void > +test03() > +{ > + int x[] = {1, 2}; > + __gnu_test::test_input_range rx(x); > + auto v = views::cartesian_product(views::counted(rx.begin(), 2), x); > + VERIFY( v.size() == 4 ); > + VERIFY( std::as_const(v).size() == 4 ); > + auto i = v.begin(); > + std::default_sentinel_t s = v.end(); > + VERIFY( i - s == -4 ); > + VERIFY( s - i == 4 ); > + ++i; > + VERIFY( i - s == -3 ); > + VERIFY( s - i == 3 ); > + ++i; > + VERIFY( i - s == -2 ); > + VERIFY( s - i == 2 ); > + ++i; > + VERIFY( i - s == -1 ); > + VERIFY( s - i == 1 ); > + ++i; > + VERIFY( i - s == 0 ); > + VERIFY( s - i == 0 ); > +} > + > +void > +test04() > +{ > + // Exhaustively verify correctness of our iterator addition implementation > + // (which runs in constant time) for this 18-element cartesian_product_view. > + int x[] = {1, 2, 3}; > + int y[] = {4, 5, 6}; > + int z[] = {7, 8}; > + int w[] = {9}; > + auto v = views::cartesian_product(x, y, z, w); > + > + for (int i = 0; i <= ranges::ssize(v); i++) > + for (int j = 0; i + j <= ranges::ssize(v); j++) > + { > + auto b1 = v.begin(); > + for (int k = 0; k < i + j; k++) > + ++b1; > + VERIFY( b1 - v.begin() == i + j ); > + auto b2 = (v.begin() + i) + j; > + auto b3 = v.begin() + (i + j); > + VERIFY( b1 == b2 && b2 == b3 ); > + > + auto e1 = v.end(); > + for (int k = 0; k < i + j; k++) > + --e1; > + VERIFY( v.end() - e1 == i + j ); > + auto e2 = (v.end() - i) - j; > + auto e3 = v.end() - (i + j); > + VERIFY( e1 == e2 && e2 == e3 ); > + } > +} > + > +void > +test05() > +{ > +#if __SIZEOF_INT128__ > + auto r = views::iota(__int128(0), __int128(5)); > +#else > + auto r = views::iota(0ll, 5ll); > +#endif > + auto v = views::cartesian_product(r, r); > + VERIFY( ranges::size(v) == 25 ); > + VERIFY( ranges::size(std::as_const(v)) == 25 ); > + VERIFY( v.end() - v.begin() == 25 ); > + VERIFY( v.begin() + ranges::size(v) - v.begin() == 25 ); > +} > + > +int > +main() > +{ > + static_assert(test01()); > + test02(); > + test03(); > + test04(); > + test05(); > +} > -- > 2.38.1.175.gdb29e6bbae > >