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.133.124]) by sourceware.org (Postfix) with ESMTPS id EEE8238A815F for ; Mon, 12 Sep 2022 16:45:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EEE8238A815F 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=1663001145; 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: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=L+EwGAsQOiPwZ1pW6C+ftRBmzrK06rWUBgz2uYYZ23g=; b=AysZOV2ks92P3ODg4yqBCMIdBcAi8gpj+ZGu4+9ctIB80W8TGuvw3h68Pffq1OVDgnxIun sfut/BldH3pHM7OwEtI5SzKDHHZOtOafnfGTCaFDoPkoF/oZiPdWFZ3w2GGDgovrtny2kR gzx9bGt+1LMKArShg9nR6FNhPL5nf7E= Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-450-bn6L4TQKPciuHYWxY_Er0g-1; Mon, 12 Sep 2022 12:45:44 -0400 X-MC-Unique: bn6L4TQKPciuHYWxY_Er0g-1 Received: by mail-qv1-f69.google.com with SMTP id ks13-20020a056214310d00b004a7c32300fcso6120592qvb.9 for ; Mon, 12 Sep 2022 09:45:44 -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:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date; bh=L+EwGAsQOiPwZ1pW6C+ftRBmzrK06rWUBgz2uYYZ23g=; b=1LOVZC1JJkJJFxsMVE/DyuXrYdcuLuwiSzflyMbI/1rSvoDWtMTT4nfSzcY6Vp7kMi ZIm0K3Lmswawflm3NkZJVRmqRhtsNu/SqZgIX1kj0y9dRr80vZwIaF6/V39GwWNBtALa dJfhf1Gms5EdzDqtdw6PeAb/HfyzS/ltXV9rEWXocxcPVDCLa7epNFI2K0SmPwVgKPaE 2r7GZjmXVeDVXztkvIZd2U1PSIo6Er4hzZm3IaMeYQ8Ng/ux+nqZc33fXl2uh51pA4NU GnDUh3lWAdaFn4GnqSNV8jTUwe2PbiVcCn2UhGqR5m0mfOIU9nlAHsHxuZtb8lSdbLSj e8xA== X-Gm-Message-State: ACgBeo0k03hOuT0tXpEseVSfNZ1ejMAQ9sM5Be7AGP/iOMuT1asP6ir1 Nh1OVqD6GhXstQZdicNQBnI6IL8Lxz7opv4OBSM3zJYG6OsNLuF0lMJLbjdufvLlzU33wJrhw9R /wAw/EBfrz1LzR2Y= X-Received: by 2002:a37:395:0:b0:6cd:cca6:4b8a with SMTP id 143-20020a370395000000b006cdcca64b8amr10704724qkd.573.1663001143932; Mon, 12 Sep 2022 09:45:43 -0700 (PDT) X-Google-Smtp-Source: AA6agR70DyH5DOWCmbMnTyFWI7NBDXFhxZ8pcm2+SHhzWNq2fAS76s6hjONiHac3jgrmD4LATlJzgQ== X-Received: by 2002:a37:395:0:b0:6cd:cca6:4b8a with SMTP id 143-20020a370395000000b006cdcca64b8amr10704709qkd.573.1663001143650; Mon, 12 Sep 2022 09:45:43 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id 17-20020ac85651000000b0035ba48c032asm6667350qtt.25.2022.09.12.09.45.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 12 Sep 2022 09:45:43 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH 4/4] libstdc++: Implement ranges::slide_view from P2442R1 Date: Mon, 12 Sep 2022 12:45:31 -0400 Message-Id: <20220912164531.1742034-4-ppalka@redhat.com> X-Mailer: git-send-email 2.37.3.542.gdd3f6c4cae In-Reply-To: <20220912164531.1742034-1-ppalka@redhat.com> References: <20220912164531.1742034-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-14.1 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_LOW,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE 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: This also implements the LWG 3711 and 3712 changes to slide_view. libstdc++-v3/ChangeLog: * include/std/ranges (__detail::__slide_caches_nothing): Define. (__detail::__slide_caches_last): Define. (__detail::__slide_caches_first): Define. (slide_view): Define. (enable_borrowed_range): Define. (slide_view::_Iterator): Define. (slide_view::_Sentinel): Define. (views::__detail::__can_slide_view): Define. (views::_Slide, views::slide): Define. * testsuite/std/ranges/adaptors/slide/1.cc: New test. --- libstdc++-v3/include/std/ranges | 364 ++++++++++++++++++ .../testsuite/std/ranges/adaptors/slide/1.cc | 105 +++++ 2 files changed, 469 insertions(+) create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/slide/1.cc diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 7533b60c1d6..bbe4fa278d2 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -6314,6 +6314,370 @@ namespace views::__adaptor inline constexpr _Chunk chunk; } + namespace __detail + { + template + concept __slide_caches_nothing = random_access_range<_Vp> && sized_range<_Vp>; + + template + concept __slide_caches_last + = !__slide_caches_nothing<_Vp> && bidirectional_range<_Vp> && common_range<_Vp>; + + template + concept __slide_caches_first + = !__slide_caches_nothing<_Vp> && !__slide_caches_last<_Vp>; + } + + template + requires view<_Vp> + class slide_view : public view_interface> + { + _Vp _M_base; + range_difference_t<_Vp> _M_n; + [[no_unique_address]] + __detail::__maybe_present_t<__detail::__slide_caches_first<_Vp>, + __detail::_CachedPosition<_Vp>> _M_cached_begin; + [[no_unique_address]] + __detail::__maybe_present_t<__detail::__slide_caches_last<_Vp>, + __detail::_CachedPosition<_Vp>> _M_cached_end; + + template class _Iterator; + class _Sentinel; + + public: + constexpr explicit + slide_view(_Vp __base, range_difference_t<_Vp> __n) + : _M_base(std::move(__base)), _M_n(__n) + { __glibcxx_assert(__n > 0); } + + constexpr auto + begin() requires (!(__detail::__simple_view<_Vp> + && __detail::__slide_caches_nothing)) + { + if constexpr (__detail::__slide_caches_first<_Vp>) + { + iterator_t<_Vp> __it; + if (_M_cached_begin._M_has_value()) + __it = _M_cached_begin._M_get(_M_base); + else + { + __it = ranges::next(ranges::begin(_M_base), _M_n - 1, ranges::end(_M_base)); + _M_cached_begin._M_set(_M_base, __it); + } + return _Iterator(ranges::begin(_M_base), std::move(__it), _M_n); + } + else + return _Iterator(ranges::begin(_M_base), _M_n); + } + + constexpr auto + begin() const requires __detail::__slide_caches_nothing + { return _Iterator(ranges::begin(_M_base), _M_n); } + + constexpr auto + end() requires (!(__detail::__simple_view<_Vp> + && __detail::__slide_caches_nothing)) + { + if constexpr (__detail::__slide_caches_nothing<_Vp>) + return _Iterator(ranges::begin(_M_base) + range_difference_t<_Vp>(size()), + _M_n); + else if constexpr (__detail::__slide_caches_last<_Vp>) + { + iterator_t<_Vp> __it; + if (_M_cached_end._M_has_value()) + __it = _M_cached_end._M_get(_M_base); + else + { + __it = ranges::prev(ranges::end(_M_base), _M_n - 1, + ranges::begin(_M_base)); + _M_cached_end._M_set(_M_base, __it); + } + return _Iterator(std::move(__it), _M_n); + } + else if constexpr (common_range<_Vp>) + return _Iterator(ranges::end(_M_base), ranges::end(_M_base), _M_n); + else + return _Sentinel(ranges::end(_M_base)); + } + + constexpr auto + end() const requires __detail::__slide_caches_nothing + { return begin() + range_difference_t(size()); } + + constexpr auto + size() requires sized_range<_Vp> + { + auto __sz = ranges::distance(_M_base) - _M_n + 1; + if (__sz < 0) + __sz = 0; + return __detail::__to_unsigned_like(__sz); + } + + constexpr auto + size() const requires sized_range + { + auto __sz = ranges::distance(_M_base) - _M_n + 1; + if (__sz < 0) + __sz = 0; + return __detail::__to_unsigned_like(__sz); + } + }; + + template + slide_view(_Range&&, range_difference_t<_Range>) -> slide_view>; + + template + inline constexpr bool enable_borrowed_range> + = enable_borrowed_range<_Vp>; + + template + requires view<_Vp> + template + class slide_view<_Vp>::_Iterator + { + using _Base = __detail::__maybe_const_t<_Const, _Vp>; + static constexpr bool _S_last_elt_present + = __detail::__slide_caches_first<_Base>; + + iterator_t<_Base> _M_current = iterator_t<_Base>(); + [[no_unique_address]] + __detail::__maybe_present_t<_S_last_elt_present, iterator_t<_Base>> + _M_last_elt = decltype(_M_last_elt)(); + range_difference_t<_Base> _M_n = 0; + + constexpr + _Iterator(iterator_t<_Base> __current, range_difference_t<_Base> __n) + requires (!_S_last_elt_present) + : _M_current(__current), _M_n(__n) + { } + + constexpr + _Iterator(iterator_t<_Base> __current, iterator_t<_Base> __last_elt, + range_difference_t<_Base> __n) + requires _S_last_elt_present + : _M_current(__current), _M_last_elt(__last_elt), _M_n(__n) + { } + + static auto + _S_iter_concept() + { + if constexpr (random_access_range<_Base>) + return random_access_iterator_tag{}; + else if constexpr (bidirectional_range<_Base>) + return bidirectional_iterator_tag{}; + else + return forward_iterator_tag{}; + } + + friend slide_view; + friend slide_view::_Sentinel; + + public: + using iterator_category = input_iterator_tag; + using iterator_concept = decltype(_S_iter_concept()); + using value_type = decltype(views::counted(_M_current, _M_n)); + using difference_type = range_difference_t<_Base>; + + _Iterator() = default; + + constexpr + _Iterator(_Iterator __i) + requires _Const && convertible_to, iterator_t<_Base>> + : _M_current(std::move(__i._M_current)), _M_n(__i._M_n) + { } + + constexpr auto + operator*() const + { return views::counted(_M_current, _M_n); } + + constexpr _Iterator& + operator++() + { + ++_M_current; + if constexpr (_S_last_elt_present) + ++_M_last_elt; + return *this; + } + + constexpr _Iterator + operator++(int) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Base> + { + --_M_current; + if constexpr (_S_last_elt_present) + --_M_last_elt; + return *this; + } + + constexpr _Iterator + operator--(int) requires bidirectional_range<_Base> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __x) + requires random_access_range<_Base> + { + _M_current += __x; + if constexpr (_S_last_elt_present) + _M_last_elt += __x; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __x) + requires random_access_range<_Base> + { + _M_current -= __x; + if constexpr (_S_last_elt_present) + _M_last_elt -= __x; + return *this; + } + + constexpr auto + operator[](difference_type __n) const + requires random_access_range<_Base> + { return views::counted(_M_current + __n, _M_n); } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + { + if constexpr (_S_last_elt_present) + return __x._M_last_elt == __y._M_last_elt; + else + return __x._M_current == __y._M_current; + } + + friend constexpr bool + operator<(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_current < __y._M_current; } + + friend constexpr bool + operator>(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __y < __x; } + + friend constexpr bool + operator<=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return !(__y < __x); } + + friend constexpr bool + operator>=(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return !(__x < __y); } + + friend constexpr auto + operator<=>(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + && three_way_comparable> + { return __x._M_current <=> __y._M_current; } + + friend constexpr _Iterator + operator+(const _Iterator& __i, difference_type __n) + requires random_access_range<_Base> + { + auto __r = __i; + __r += __n; + return __r; + } + + friend constexpr _Iterator + operator+(difference_type __n, const _Iterator& __i) + requires random_access_range<_Base> + { + auto __r = __i; + __r += __n; + return __r; + } + + friend constexpr _Iterator + operator-(const _Iterator& __i, difference_type __n) + requires random_access_range<_Base> + { + auto __r = __i; + __r -= __n; + return __r; + } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires sized_sentinel_for, iterator_t<_Base>> + { + if constexpr (_S_last_elt_present) + return __x._M_last_elt - __y._M_last_elt; + else + return __x._M_current - __y._M_current; + } + }; + + template + requires view<_Vp> + class slide_view<_Vp>::_Sentinel + { + sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); + + constexpr explicit + _Sentinel(sentinel_t<_Vp> __end) + : _M_end(__end) + { } + + friend slide_view; + + public: + _Sentinel() = default; + + friend constexpr bool + operator==(const _Iterator& __x, const _Sentinel& __y) + { return __x._M_last_elt == __y._M_end; } + + friend constexpr range_difference_t<_Vp> + operator-(const _Iterator& __x, const _Sentinel& __y) + requires sized_sentinel_for, iterator_t<_Vp>> + { return __x._M_last_elt - __y._M_end; } + + friend constexpr range_difference_t<_Vp> + operator-(const _Sentinel& __y, const _Iterator& __x) + requires sized_sentinel_for, iterator_t<_Vp>> + { return __y._M_end -__x._M_last_elt; } + }; + + namespace views + { + namespace __detail + { + template + concept __can_slide_view + = requires { slide_view(std::declval<_Range>(), std::declval<_Dp>()); }; + } + + struct _Slide : __adaptor::_RangeAdaptor<_Slide> + { + template> + requires __detail::__can_slide_view<_Range, _Dp> + constexpr auto + operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const + { return slide_view(std::forward<_Range>(__r), __n); } + + using __adaptor::_RangeAdaptor<_Slide>::operator(); + static constexpr int _S_arity = 2; + static constexpr bool _S_has_simple_extra_args = true; + }; + + inline constexpr _Slide slide; + } + #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/slide/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/slide/1.cc new file mode 100644 index 00000000000..98560420810 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/slide/1.cc @@ -0,0 +1,105 @@ +// { 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() +{ + auto v1 = std::array{1, 2} | views::slide(1); + const auto i0 = v1.begin(), i1 = v1.begin() + 1; + VERIFY( i0 + 1 - 1 == i0 ); + VERIFY( i0 < i1 ); + VERIFY( i1 < v1.end() ); + VERIFY( i1 - i0 == 1 ); + VERIFY( i0 - i1 == -1 ); + VERIFY( v1.end() - i1 == 1 ); + VERIFY( i1 - v1.end() == -1 ); + VERIFY( ranges::equal(std::move(v1) | views::join, (int[]){1, 2}) ); + + int x[] = {1, 2, 3, 4}; + auto v2 = x | views::slide(2); + auto i2 = v2.begin(); + i2 += 2; + i2 -= -1; + VERIFY( i2 == v2.end() ); + VERIFY( ranges::size(v2) == 3 ); + VERIFY( ranges::size(std::as_const(v2)) == 3 ); + VERIFY( ranges::equal(v2, (std::initializer_list[]){{1, 2}, {2, 3}, {3, 4}}, + ranges::equal) ); + + int y[] = {1, 2, 3, 4, 5}; + const auto v3 = y | views::slide(3); + VERIFY( ranges::size(v3) == 3 ); + for (unsigned i = 0; i < ranges::size(x); i++) + { + VERIFY( &v3[i][0] == &y[i] + 0 ); + VERIFY( &v3[i][1] == &y[i] + 1 ); + VERIFY( &v3[i][2] == &y[i] + 2 ); + } + + const auto v5 = y | views::slide(5); + VERIFY( ranges::size(v5) == 1 ); + VERIFY( ranges::equal(v5 | views::join, y) ); + + const auto v6 = y | views::slide(6); + VERIFY( ranges::empty(v6) ); + + return true; +} + +constexpr bool +test02() +{ + using __gnu_test::test_input_range; + using __gnu_test::test_forward_range; + using __gnu_test::test_random_access_range; + + using ty1 = ranges::slide_view>>; + static_assert(ranges::forward_range); + static_assert(!ranges::bidirectional_range); + static_assert(!ranges::sized_range); + + using ty2 = ranges::slide_view>>; + static_assert(ranges::random_access_range); + static_assert(ranges::sized_range); + + return true; +} + +constexpr bool +test03() +{ + auto v = views::iota(0, 4) | views::filter([](auto) { return true; }) | views::slide(2); + using ty = decltype(v); + static_assert(ranges::forward_range); + static_assert(ranges::common_range); + static_assert(!ranges::sized_range); + VERIFY( v.begin() == v.begin() ); + VERIFY( v.begin() != v.end() ); + VERIFY( ranges::next(v.begin(), 3) == v.end() ); + auto it = v.begin(); + ++it; + it++; + VERIFY( ranges::next(it) == v.end() ); + it--; + --it; + VERIFY( it == v.begin() ); + + return true; +} + +int +main() +{ + static_assert(test01()); + static_assert(test02()); + static_assert(test03()); +} -- 2.37.3.542.gdd3f6c4cae