From patchwork Thu Oct 27 16:47:50 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1695510 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=ro7ZT4I/; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Mys8N1Sxcz23kj for ; Fri, 28 Oct 2022 03:49:06 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id AFC083846451 for ; Thu, 27 Oct 2022 16:49:04 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AFC083846451 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1666889344; bh=ZHFq+V43xihzThl98ETuOPw80NblVdkzVh/1Hd+MPnk=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=ro7ZT4I/99lC+73EFXsVFe1h2NB04fOg/3jdwj53A4gATmUk3iZ0/KXzOaaYm7h2o FsYSMWfg8SDtZNAc7bVjxdIDomIPbO05ZOXsnFzpEOKAfbTAZR9/w1cSTkpfrErL4b 5cKwXYAvBUinqSvjh6pv+62yJkbprvh7hg3oCWrI= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id B6431384B402 for ; Thu, 27 Oct 2022 16:48:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B6431384B402 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-106-rNKtW2odP3CBJzyP6BfwKA-1; Thu, 27 Oct 2022 12:48:10 -0400 X-MC-Unique: rNKtW2odP3CBJzyP6BfwKA-1 Received: by mail-qk1-f200.google.com with SMTP id u6-20020a05620a430600b006e47fa02576so1463971qko.22 for ; Thu, 27 Oct 2022 09:48:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=ZHFq+V43xihzThl98ETuOPw80NblVdkzVh/1Hd+MPnk=; b=v2G346RMpcDekf3na5MTEwR9/7OgCf2V87qdmPV9yWBs7UQmnWFN42HCWJ/ZY2JCu3 pt5IuMFvl8Arlfs/+CIbQPxLJBBjj8NGwPDxhVDLhqB5442o2lKpHO6LzLfCeEx8yC5J nFlRbQLnbMu9KfjF2uvoSS8iQ6khieeu9ATlHq6TmzrBfsI+u/cGt64fZm95Q8UX4ouB lOh1kTvM/GqvQz3ODV61vbmhc/9oF4hs0W3hhNGVc0kTk/wca75u1G5wkv84XhHhPW3u aorLCiUGy2U9MTzAjPdMS5zKR+MIljgA9Aqufbf/F6g9SMH9XIpbVt4zu9msMZKZQ1un ehJg== X-Gm-Message-State: ACrzQf1c5wNKMuuDZ+RDdtJ9blOcdgRdSCoTLAmeLIwQyGpPlQwQZR0D tunVVk4lXTW0uXaS5udk+bsHFz6QCyv0MS/7fht05B0zL/ztMTyy0ZyVmN2vHzixRmYuNQ8nQ3d uJaDyQDYqE04yL/0BrS6K7a7uojl66wpYVZU4ZPaHzgAfeY4kSdzwqN2Lf0/m7MCj7BI= X-Received: by 2002:a05:6214:20a7:b0:4bb:9359:8368 with SMTP id 7-20020a05621420a700b004bb93598368mr9037749qvd.122.1666889288333; Thu, 27 Oct 2022 09:48:08 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6OLAjMQUilCWCT204YlSLsVyao5w9FGWCskqjXSn8ykxTh4l0JqAhIbGZjXyuVnKekWA/hNg== X-Received: by 2002:a05:6214:20a7:b0:4bb:9359:8368 with SMTP id 7-20020a05621420a700b004bb93598368mr9037708qvd.122.1666889287620; Thu, 27 Oct 2022 09:48:07 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id s4-20020ac85284000000b0039c7b9522ecsm1128666qtn.35.2022.10.27.09.48.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 27 Oct 2022 09:48:06 -0700 (PDT) To: gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4 Date: Thu, 27 Oct 2022 12:47:50 -0400 Message-Id: <20221027164750.97737-1-ppalka@redhat.com> X-Mailer: git-send-email 2.38.1.175.gdb29e6bbae MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-14.0 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Patrick Palka via Gcc-patches From: Patrick Palka Reply-To: Patrick Palka Cc: libstdc++@gcc.gnu.org Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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<_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; +#else + return (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...); +#endif + }(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...>) { +#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; +#else + return (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...); +#endif + }(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...>) { + difference_type __sum = static_cast(0); +#ifdef _GLIBCXX_ASSERTIONS + bool __overflow + = (__builtin_add_overflow(__sum, _M_scaled_distance<_Is>(__t) &__sum) + || ...); + __glibcxx_assert(!__overflow); +#else + __sum = (_M_scaled_distance<_Is>(__t) + ...); +#endif + 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 + bool __overflow = __builtin_mul_overflow(__dist, _M_scaled_size<_Nm+1>(), &__dist); + __glibcxx_assert(!__overflow); +#else + __dist *= _M_scaled_size<_Nm+1>(); +#endif + 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 + bool __overflow = __builtin_mul_overflow(__size, _M_scaled_size<_Nm+1>(), &__size); + __glibcxx_assert(!__overflow); +#else + __size *= _M_scaled_size<_Nm+1>(); +#endif + 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..2e4d80b0399 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc @@ -0,0 +1,162 @@ +// { 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 ); + } +} + +int +main() +{ + static_assert(test01()); + test02(); + test03(); + test04(); +}