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 811EC3858404 for ; Wed, 31 Aug 2022 13:30:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 811EC3858404 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=1661952639; 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=kY78f0ATkA8B7Bt1YSBQZQybgz7rSw6IsrzcneUdHN0=; b=g+jylAlTzyjjvbNsbvWfCsKfQIN+pyS/WDg74Qtg9KT6Vj51DsftKxUK5d9byRYCJkvY9x qfbKTYKhaqepD/exS5AdxjHTNXvggcO1S4vi/Csl7QreRIH2V0M3aQOG3H+wPBH68TmxnT h19eafpXj9LWpXUJcYtAczAhdLJS1ZQ= Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-247-alEeifiZNdCbxL2OYIzESg-1; Wed, 31 Aug 2022 09:30:34 -0400 X-MC-Unique: alEeifiZNdCbxL2OYIzESg-1 Received: by mail-qt1-f199.google.com with SMTP id h19-20020ac85493000000b00343408bd8e5so11148849qtq.4 for ; Wed, 31 Aug 2022 06:30:34 -0700 (PDT) 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; bh=kY78f0ATkA8B7Bt1YSBQZQybgz7rSw6IsrzcneUdHN0=; b=X08Kk0Y1etA0IveIW2xNcesTXPv0iu6O7ZtPJ/vRkrr8a9nfD22Sx7G4fQhZaYhKVu NGz2YjkrIRuO2SwFScQ9l0lFK2hzt07Jl/IfsYN1W3eBohwC6Kg2/NS5h72+KVbyhWjr Bx+A363NCv34ZuWU3s4mp7T+R5kzZmroOvn6hz3budYFR5NxYni9D2G3bD2v0MAoc7f4 NrP+1DzGFuWACLj0x4Ob+zqpLUZtuoFBuFKWetRgsFGYuJGv1BtcotbvJBH3Hf/lDFLN /Zsj6kuiy6Jez6WBukgqG7Q+ecMOobjCp+Wv6nEkgP7z1XAS7g4MIitB/H7Cjc6m6SSB aWEA== X-Gm-Message-State: ACgBeo1u1d+YIeuEPcmgVWcx3PeMHh2oDCpfRU7M/4rGEVBGq0QHgcmm wOazliP5vZRnh9ASK8zJ3ECUQ364eMbRS71KpA2xqZWQxgFTJ0qDWEd5hSmYNEaNaLBzn3+Kk0l R+5khWaEsl05HRZo= X-Received: by 2002:a05:620a:46a7:b0:6bb:204d:5134 with SMTP id bq39-20020a05620a46a700b006bb204d5134mr15260351qkb.285.1661952633452; Wed, 31 Aug 2022 06:30:33 -0700 (PDT) X-Google-Smtp-Source: AA6agR499pO3fHkjhPyo6fqWTRKGA1t8s3p/foj2BvzO+dJauoNwkoOMbxt8pSqrWnXo83GjnhdQ0w== X-Received: by 2002:a05:620a:46a7:b0:6bb:204d:5134 with SMTP id bq39-20020a05620a46a700b006bb204d5134mr15260319qkb.285.1661952633084; Wed, 31 Aug 2022 06:30:33 -0700 (PDT) Received: from [192.168.1.130] (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id x17-20020a05620a449100b006bbd2c4cccfsm10604581qkp.53.2022.08.31.06.30.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 31 Aug 2022 06:30:32 -0700 (PDT) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Wed, 31 Aug 2022 09:30:31 -0400 (EDT) To: Jonathan Wakely cc: Patrick Palka , gcc-patches@gcc.gnu.org, libstdc++@gcc.gnu.org Subject: Re: [PATCH 1/2] libstdc++: Implement ranges::adjacent_view from P2321R2 In-Reply-To: Message-ID: <2fb1f58c-70ee-a271-d508-a7d172c61a1a@idea> References: <20220830171335.54110-1-ppalka@redhat.com> 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=-14.3 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=unavailable 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 Wed, 31 Aug 2022, Jonathan Wakely wrote: > On Tue, 30 Aug 2022 at 18:14, Patrick Palka via Libstdc++ > wrote: > > > > Tested on x86_64-pc-linux-gnu, does this look OK for trunk? > > > > + constexpr > > + _Iterator(__as_sentinel, iterator_t<_Base> __first, iterator_t<_Base> __last) > > + { > > + if constexpr (!bidirectional_range<_Base>) > > + for (auto& __it : _M_current) > > + __it = __last; > > + else > > + for (ssize_t __i = _Nm-1; __i >= 0; --__i) > > ssize_t is defined by POSIX in but isn't in ISO C or > C++. It looks like MinGW defines it to ... something ... sometimes, > but I don't think we can rely on it for non-POSIX targets. I see. Using ssize_t makes the loop a little cleaner but it's hardly necessary, so consider it rewritten into: for (size_t __i = 0; __i < _Nm; ++__i) { _M_current[_Nm - 1 - __i] = __last; ranges::advance(__last, -1, __first); } > > > > + template > > + struct _Adjacent : __adaptor::_RangeAdaptorClosure > > + { > > + template > > + requires (_Nm == 0) || __detail::__can_adjacent_view<_Nm, _Range> > > + [[nodiscard]] > > + constexpr auto > > + operator()(_Range&& __r) const > > Does this attribute actually work here? > > I thought we needed to use `operator() [[nodiscard]]` for functions > with a requires-clause, because otherwise the attribute gives a parse > error. Maybe I've misremembered the problem, and it just doesn't give > a -Wunused-result warning. The decl above is setting off my spidey > sense for some reason though. Oops yeah, it looks like this position of [[nodiscard]] works with standard concepts, but it's a parse error with -fconcepts-ts due to the different requires-clause grammar. Here's v2 which avoids using ssize_t, and puts the [[nodiscard]] after 'operator()' (_Zip and _ZipTransform have the same issue which I can fix separately): -- >8 -- libstdc++-v3/ChangeLog: * include/std/ranges (adjacent_view): Define. (enable_borrowed_range): Define. (__detail::__repeated_tuple): Define. (adjacent_view::_Iterator): Define. (adjacent_view::_Sentinel): Define. (views::__detail::__can_adjacent_view): Define. (views::_Adjacent): Define. (views::adjacent): Define. (views::pairwise): Define. * testsuite/std/ranges/adaptors/adjacent/1.cc: New test. --- libstdc++-v3/include/std/ranges | 358 ++++++++++++++++++ .../std/ranges/adaptors/adjacent/1.cc | 110 ++++++ 2 files changed, 468 insertions(+) create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 6e2e561ed12..2352aad76fc 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -5081,6 +5081,364 @@ namespace views::__adaptor inline constexpr _ZipTransform zip_transform; } + + template + requires view<_Vp> && (_Nm > 0) + class adjacent_view : public view_interface> + { + _Vp _M_base = _Vp(); + + template class _Iterator; + template class _Sentinel; + + struct __as_sentinel + { }; + + public: + adjacent_view() requires default_initializable<_Vp> = default; + + constexpr explicit + adjacent_view(_Vp __base) + : _M_base(std::move(__base)) + { } + + constexpr auto + begin() requires (!__detail::__simple_view<_Vp>) + { return _Iterator(ranges::begin(_M_base), ranges::end(_M_base)); } + + constexpr auto + begin() const requires range + { return _Iterator(ranges::begin(_M_base), ranges::end(_M_base)); } + + constexpr auto + end() requires (!__detail::__simple_view<_Vp>) + { + if constexpr (common_range<_Vp>) + return _Iterator(__as_sentinel{}, ranges::begin(_M_base), ranges::end(_M_base)); + else + return _Sentinel(ranges::end(_M_base)); + } + + constexpr auto + end() const requires range + { + if constexpr (common_range) + return _Iterator(__as_sentinel{}, ranges::begin(_M_base), ranges::end(_M_base)); + else + return _Sentinel(ranges::end(_M_base)); + } + + constexpr auto + size() requires sized_range<_Vp> + { + using _ST = decltype(ranges::size(_M_base)); + using _CT = common_type_t<_ST, size_t>; + auto __sz = static_cast<_CT>(ranges::size(_M_base)); + __sz -= std::min<_CT>(__sz, _Nm - 1); + return static_cast<_ST>(__sz); + } + + constexpr auto + size() const requires sized_range + { + using _ST = decltype(ranges::size(_M_base)); + using _CT = common_type_t<_ST, size_t>; + auto __sz = static_cast<_CT>(ranges::size(_M_base)); + __sz -= std::min<_CT>(__sz, _Nm - 1); + return static_cast<_ST>(__sz); + } + }; + + template + inline constexpr bool enable_borrowed_range> + = enable_borrowed_range<_Vp>; + + namespace __detail + { + // Yields tuple<_Tp, ..., _Tp> with _Nm elements. + template + using __repeated_tuple = decltype(std::tuple_cat(std::declval>())); + } + + template + requires view<_Vp> && (_Nm > 0) + template + class adjacent_view<_Vp, _Nm>::_Iterator + { + using _Base = __detail::__maybe_const_t<_Const, _Vp>; + array, _Nm> _M_current = array, _Nm>(); + + constexpr + _Iterator(iterator_t<_Base> __first, sentinel_t<_Base> __last) + { + for (auto& __i : _M_current) + { + __i = __first; + ranges::advance(__first, 1, __last); + } + } + + constexpr + _Iterator(__as_sentinel, iterator_t<_Base> __first, iterator_t<_Base> __last) + { + if constexpr (!bidirectional_range<_Base>) + for (auto& __it : _M_current) + __it = __last; + else + for (size_t __i = 0; __i < _Nm; ++__i) + { + _M_current[_Nm - 1 - __i] = __last; + ranges::advance(__last, -1, __first); + } + } + + 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 class adjacent_view; + + public: + using iterator_category = input_iterator_tag; + using iterator_concept = decltype(_S_iter_concept()); + using value_type = conditional_t<_Nm == 2, + pair, range_value_t<_Base>>, + __detail::__repeated_tuple, _Nm>>; + using difference_type = range_difference_t<_Base>; + + _Iterator() = default; + + constexpr + _Iterator(_Iterator __i) + requires _Const && convertible_to, iterator_t<_Base>> + { + for (size_t __j = 0; __j < _Nm; ++__j) + _M_current[__j] = std::move(__i[__j]); + } + + constexpr auto + operator*() const + { + auto __f = [](auto& __i) -> decltype(auto) { return *__i; }; + return __detail::__tuple_transform(__f, _M_current); + } + + constexpr _Iterator& + operator++() + { + for (auto& __i : _M_current) + ++__i; + return *this; + } + + constexpr _Iterator + operator++(int) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() requires bidirectional_range<_Base> + { + for (auto& __i : _M_current) + --__i; + 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> + { + for (auto& __i : _M_current) + __i += __x; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __x) + requires random_access_range<_Base> + { + for (auto& __i : _M_current) + __i -= __x; + return *this; + } + + constexpr auto + operator[](difference_type __n) const + requires random_access_range<_Base> + { + auto __f = [&](auto& __i) -> decltype(auto) { return __i[__n]; }; + return __detail::__tuple_transform(__f, _M_current); + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + { return __x._M_current.back() == __y._M_current.back(); } + + friend constexpr bool + operator<(const _Iterator& __x, const _Iterator& __y) + requires random_access_range<_Base> + { return __x._M_current.back() < __y._M_current.back(); } + + 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.back() <=> __y._M_current.back(); } + + 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>> + { return __x._M_current.back() - __y._M_current.back(); } + + 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> + { + for (size_t __i = 0; __i < _Nm; __i++) + ranges::iter_swap(__l._M_current[__i], __r._M_current[__i]); + } + }; + + template + requires view<_Vp> && (_Nm > 0) + template + class adjacent_view<_Vp, _Nm>::_Sentinel + { + using _Base = __detail::__maybe_const_t<_Const, _Vp>; + + sentinel_t<_Base> _M_end = sentinel_t<_Base>(); + + constexpr explicit + _Sentinel(sentinel_t<_Base> __end) + : _M_end(__end) + { } + + friend class adjacent_view; + + public: + _Sentinel() = default; + + constexpr + _Sentinel(_Sentinel __i) + requires _Const && convertible_to, sentinel_t<_Base>> + : _M_end(std::move(__i._M_end)) + { } + + template + requires sentinel_for, + iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>> + friend constexpr bool + operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) + { return __x._M_current.back() == __y._M_end; } + + template + requires sized_sentinel_for, + iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>> + friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _Vp>> + operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y) + { return __x._M_current.back() - __y._M_end; } + + template + requires sized_sentinel_for, + iterator_t<__detail::__maybe_const_t<_OtherConst, _Vp>>> + friend constexpr range_difference_t<__detail::__maybe_const_t<_OtherConst, _Vp>> + operator-(const _Sentinel& __y, const _Iterator<_OtherConst>& __x) + { return __y._M_end - __x._M_current.back(); } + }; + + namespace views + { + namespace __detail + { + template + concept __can_adjacent_view + = requires { adjacent_view, _Nm>(std::declval<_Range>()); }; + } + + template + struct _Adjacent : __adaptor::_RangeAdaptorClosure + { + template + requires (_Nm == 0) || __detail::__can_adjacent_view<_Nm, _Range> + constexpr auto + operator() [[nodiscard]] (_Range&& __r) const + { + if constexpr (_Nm == 0) + return views::empty>; + else + return adjacent_view, _Nm>(std::forward<_Range>(__r)); + } + }; + + template + inline constexpr _Adjacent<_Nm> adjacent; + + inline constexpr auto pairwise = adjacent<2>; + } #endif // C++23 } // namespace ranges diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc new file mode 100644 index 00000000000..9829f79364f --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent/1.cc @@ -0,0 +1,110 @@ +// { 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() +{ + static_assert(ranges::empty(std::array{1, 2, 3} | views::adjacent<0>)); + + auto v1 = std::array{1, 2} | views::adjacent<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 ); + ranges::iter_swap(i0, i1); + VERIFY( ranges::equal(std::move(v1) | views::keys, (int[]){2, 1}) ); + + int x[] = {1, 2, 3, 4}; + auto v2 = x | views::pairwise; + 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 | views::keys, (int[]){1, 2, 3}) ); + VERIFY( ranges::equal(v2 | views::values, (int[]){2, 3, 4}) ); + + int y[] = {1, 2, 3, 4, 5}; + const auto v3 = y | views::adjacent<3>; + VERIFY( ranges::size(v3) == 3 ); + for (unsigned i = 0; i < ranges::size(x); i++) + { + VERIFY( &std::get<0>(v3[i]) == &y[i] + 0 ); + VERIFY( &std::get<1>(v3[i]) == &y[i] + 1 ); + VERIFY( &std::get<2>(v3[i]) == &y[i] + 2 ); + } + + const auto v5 = y | views::adjacent<5>; + VERIFY( ranges::equal(v5, views::single(std::make_tuple(1, 2, 3, 4, 5))) ); + + const auto v6 = y | views::adjacent<6>; + VERIFY( ranges::empty(v6) ); + + const auto v0 = y | views::adjacent<0>; + VERIFY( ranges::empty(v0) ); + + 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::adjacent_view>, 2>; + static_assert(ranges::forward_range); + static_assert(!ranges::bidirectional_range); + static_assert(!ranges::sized_range); + + using ty2 = ranges::adjacent_view>, 3>; + 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::pairwise; + 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.2.490.g6c8e4ee870