From patchwork Sun Nov 17 01:07:48 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 1196227 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-513811-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="gApjI9Dq"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="TxZNgHGR"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47Fv943Q8kz9s3Z for ; Sun, 17 Nov 2019 12:08:21 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=yA+PKYTaS9h2N04qL2BPCfpydRTj3cJRjC7Jq9VpOl3nTxPniZhrw JNtA/8Ygi0sKY0MLqInZKCcun+UqDZxvBkxY2k/TLTaRM/OVCspthfaTbEzywPxm m0aUvmceBskgiGLr2vxNtSp41KNMMZOwmZZulPW9XFg95M8c613JWc= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=3QItRkv7OjKc91nCtfZvT81J2cY=; b=gApjI9DqxYiTfcPIcxRQ xxXV7drhjEj02oujRSZrB5FFaiiHaiTvaFpeAoCKSkvp786PGA+eAL5po2v57Pwd u1wn9DN2vo+2BCFteoVMYk4UYfxb2iIRlR/DtiqgpoUfZ3ZFFeWxD7aqzTRqdxy8 TcqWsvEByUPW1K8mpOlQqec= Received: (qmail 18570 invoked by alias); 17 Nov 2019 01:08:01 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 18554 invoked by uid 89); 17 Nov 2019 01:08:01 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-17.2 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT autolearn=unavailable version=3.3.1 spammy=subrange, match_results, factories X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-1.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (205.139.110.61) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 17 Nov 2019 01:07:55 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1573952873; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type; bh=7uxiw1vGCabeZvdCpmhkgi+6eSpDhoDUJpjXq9LIwBE=; b=TxZNgHGRpZVSkiO7fLqjTJwKdEvy9bKcUJFjNhrgcYGv+WSW6I4Fk8jbzubIoFJtuebHJI p4hZB5Y/Ih4tVGbqFE/Hc4UgfvGHx5hJlGyzHOyV8qa9L+eMRb9Yvaan/CDwB+qgvUJu8A 5BVqgQ5uGB8O7PeCUbhna1Elcjyhj40= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-110-EoJ4-RlhPS2IKh7pPgu-WA-1; Sat, 16 Nov 2019 20:07:50 -0500 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 2F6E21005500; Sun, 17 Nov 2019 01:07:49 +0000 (UTC) Received: from localhost (unknown [10.33.36.113]) by smtp.corp.redhat.com (Postfix) with ESMTP id 7181746479; Sun, 17 Nov 2019 01:07:48 +0000 (UTC) Date: Sun, 17 Nov 2019 01:07:48 +0000 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: Define C++20 range utilities and range factories Message-ID: <20191117010748.GA26915@redhat.com> MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett User-Agent: Mutt/1.12.1 (2019-06-15) X-Mimecast-Spam-Score: 0 Content-Disposition: inline This adds another chunk of the header. The changes from P1456R1 (Move-only views) and P1862R1 (Range adaptors for non-copyable iterators) are included, but not the changes from P1870R1 (forwarding-range is too subtle). The tests for subrange and iota_view are poor and should be improved. * include/bits/regex.h (match_results): Specialize __enable_view_impl. * include/bits/stl_set.h (set): Likewise. * include/bits/unordered_set.h (unordered_set, unordered_multiset): Likewise. * include/debug/multiset.h (__debug::multiset): Likewise. * include/debug/set.h (__debug::set): Likewise. * include/debug/unordered_set (__debug::unordered_set) (__debug::unordered_multiset): Likewise. * include/std/ranges (ranges::view, ranges::enable_view) (ranges::view_interface, ranges::subrange, ranges::empty_view) (ranges::single_view, ranges::views::single, ranges::iota_view) (ranges::views::iota): Define for C++20. * testsuite/std/ranges/empty_view.cc: New test. * testsuite/std/ranges/iota_view.cc: New test. * testsuite/std/ranges/single_view.cc: New test. * testsuite/std/ranges/view.cc: New test. Tested powerpc64le-linux, committed to trunk. commit 6567feabca709d030a37e275de58a1186218cf36 Author: Jonathan Wakely Date: Sun Nov 17 00:52:45 2019 +0000 libstdc++: Define C++20 range utilities and range factories This adds another chunk of the header. The changes from P1456R1 (Move-only views) and P1862R1 (Range adaptors for non-copyable iterators) are included, but not the changes from P1870R1 (forwarding-range is too subtle). The tests for subrange and iota_view are poor and should be improved. * include/bits/regex.h (match_results): Specialize __enable_view_impl. * include/bits/stl_set.h (set): Likewise. * include/bits/unordered_set.h (unordered_set, unordered_multiset): Likewise. * include/debug/multiset.h (__debug::multiset): Likewise. * include/debug/set.h (__debug::set): Likewise. * include/debug/unordered_set (__debug::unordered_set) (__debug::unordered_multiset): Likewise. * include/std/ranges (ranges::view, ranges::enable_view) (ranges::view_interface, ranges::subrange, ranges::empty_view) (ranges::single_view, ranges::views::single, ranges::iota_view) (ranges::views::iota): Define for C++20. * testsuite/std/ranges/empty_view.cc: New test. * testsuite/std/ranges/iota_view.cc: New test. * testsuite/std/ranges/single_view.cc: New test. * testsuite/std/ranges/view.cc: New test. diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++-v3/include/bits/regex.h index 7869c3fd1c1..49994369563 100644 --- a/libstdc++-v3/include/bits/regex.h +++ b/libstdc++-v3/include/bits/regex.h @@ -2056,9 +2056,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 match_results<_Bi_iter, _Alloc>& __rhs) noexcept { __lhs.swap(__rhs); } - _GLIBCXX_END_NAMESPACE_CXX11 +#if __cplusplus > 201703L +namespace ranges::__detail +{ + template inline constexpr bool __enable_view_impl; + template + inline constexpr bool __enable_view_impl> + = false; +} // namespace ranges::__detail +#endif // C++20 + // [28.11.2] Function template regex_match /** * @name Matching, Searching, and Replacing diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h index 96fa14e2afa..9e34961f4a5 100644 --- a/libstdc++-v3/include/bits/stl_multiset.h +++ b/libstdc++-v3/include/bits/stl_multiset.h @@ -1039,6 +1039,16 @@ _GLIBCXX_END_NAMESPACE_CONTAINER { return __set._M_t; } }; +#if __cplusplus > 201703L +namespace ranges::__detail +{ + template inline constexpr bool __enable_view_impl; + template + inline constexpr bool + __enable_view_impl<_GLIBCXX_STD_C::multiset<_Key, _Compare, _Alloc>> + = false; +} // namespace ranges::__detail +#endif // C++20 #endif // C++17 _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index 279b9705d78..135d57af496 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -1051,6 +1051,15 @@ _GLIBCXX_END_NAMESPACE_CONTAINER _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set) { return __set._M_t; } }; +#if __cplusplus > 201703L +namespace ranges::__detail +{ + template inline constexpr bool __enable_view_impl; + template + inline constexpr bool + __enable_view_impl<_GLIBCXX_STD_C::set<_Key, _Compare, _Alloc>> = false; +} // namespace ranges::__detail +#endif // C++20 #endif // C++17 _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 8ebcaf40263..98943fb1a47 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -1771,6 +1771,21 @@ _GLIBCXX_END_NAMESPACE_CONTAINER _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) { return __set._M_h; } }; + +#if __cplusplus > 201703L +namespace ranges::__detail +{ + template inline constexpr bool __enable_view_impl; + template + inline constexpr bool + __enable_view_impl<_GLIBCXX_STD_C::unordered_set<_Val, _Hash, _Eq, + _Alloc>> = false; + template + inline constexpr bool + __enable_view_impl<_GLIBCXX_STD_C::unordered_multiset<_Val, _Hash, _Eq, + _Alloc>> = false; +} // namespace ranges::__detail +#endif // C++20 #endif // C++17 _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h index 8fb11f871ac..00c5bcc0f24 100644 --- a/libstdc++-v3/include/debug/multiset.h +++ b/libstdc++-v3/include/debug/multiset.h @@ -630,6 +630,19 @@ namespace __debug { return __x.swap(__y); } } // namespace __debug + +#if __cplusplus > 201703L +_GLIBCXX_BEGIN_NAMESPACE_VERSION +namespace ranges::__detail +{ + template inline constexpr bool __enable_view_impl; + template + inline constexpr bool + __enable_view_impl> + = false; +} // namespace ranges::__detail +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++20 } // namespace std #endif diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h index 9f16a9190b8..16eee2947c9 100644 --- a/libstdc++-v3/include/debug/set.h +++ b/libstdc++-v3/include/debug/set.h @@ -641,6 +641,18 @@ namespace __debug { return __x.swap(__y); } } // namespace __debug + +#if __cplusplus > 201703L +_GLIBCXX_BEGIN_NAMESPACE_VERSION +namespace ranges::__detail +{ + template inline constexpr bool __enable_view_impl; + template + inline constexpr bool + __enable_view_impl> = false; +} // namespace ranges::__detail +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++20 } // namespace std #endif diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index ecc084e3846..5dbb754a100 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -1183,6 +1183,22 @@ namespace __debug { return !(__x == __y); } } // namespace __debug +#if __cplusplus > 201703L +_GLIBCXX_BEGIN_NAMESPACE_VERSION +namespace ranges::__detail +{ + template inline constexpr bool __enable_view_impl; + template + inline constexpr bool + __enable_view_impl> + = false; + template + inline constexpr bool + __enable_view_impl> = false; +} // namespace ranges::__detail +_GLIBCXX_END_NAMESPACE_VERSION +#endif // C++20 } // namespace std #endif // C++11 diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 884fa1d1408..333d110b67e 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -38,7 +38,11 @@ #if __cpp_lib_concepts +#include +#include #include +#include +#include /** * @defgroup ranges Ranges @@ -68,6 +72,12 @@ namespace ranges using range_rvalue_reference_t = iter_rvalue_reference_t>; + namespace __detail + { + template + concept __forwarding_range = range<_Tp> && __range_impl<_Tp>; + } // namespace __detail + // [range.sized] The sized_range concept. // Defined in // template concept sized_range; @@ -104,6 +114,875 @@ namespace ranges template concept common_range = range<_Tp> && same_as, sentinel_t<_Tp>>; + + struct view_base { }; + + namespace __detail + { + template + concept __deep_const_range = range<_Tp> && range + && same_as, range_reference_t>; + + template + inline constexpr bool __enable_view_impl + = derived_from<_Tp, view_base> || (!__deep_const_range<_Tp>); + + template + inline constexpr bool __enable_view_impl> + = false; + + } // namespace __detail + + template + inline constexpr bool enable_view + = __detail::__enable_view_impl>; + + template + concept view + = range<_Tp> && movable<_Tp> && default_initializable<_Tp> + && enable_view<_Tp>; + + template + concept viewable_range = range<_Tp> + && (__detail::__forwarding_range<_Tp> || view>); + + namespace __detail + { + template + concept __simple_view = view<_Range> && range + && same_as, iterator_t> + && same_as, sentinel_t>; + + template + concept __has_arrow = input_iterator<_It> + && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); }); + + template + concept __not_same_as + = !same_as, remove_cvref_t<_Up>>; + } // namespace __detail + + template + requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>> + class view_interface : public view_base + { + private: + constexpr _Derived& _M_derived() noexcept + { + static_assert(derived_from<_Derived, view_interface<_Derived>>); + static_assert(view<_Derived>); + return static_cast<_Derived&>(*this); + } + + constexpr const _Derived& _M_derived() const noexcept + { + static_assert(derived_from<_Derived, view_interface<_Derived>>); + static_assert(view<_Derived>); + return static_cast(*this); + } + + public: + constexpr bool + empty() requires forward_range<_Derived> + { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); } + + constexpr bool + empty() const requires forward_range + { return ranges::begin(_M_derived()) == ranges::end(_M_derived()); } + + constexpr explicit + operator bool() requires requires { ranges::empty(_M_derived()); } + { return !ranges::empty(_M_derived()); } + + constexpr explicit + operator bool() const requires requires { ranges::empty(_M_derived()); } + { return !ranges::empty(_M_derived()); } + + constexpr auto + data() requires contiguous_iterator> + { return to_address(ranges::begin(_M_derived())); } + + constexpr auto + data() const + requires range + && contiguous_iterator> + { return to_address(ranges::begin(_M_derived())); } + + constexpr auto + size() + requires forward_range<_Derived> + && sized_sentinel_for, iterator_t<_Derived>> + { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); } + + constexpr auto + size() const + requires forward_range + && sized_sentinel_for, + iterator_t> + { return ranges::end(_M_derived()) - ranges::begin(_M_derived()); } + + constexpr decltype(auto) + front() requires forward_range<_Derived> + { + __glibcxx_assert(!empty()); + return *ranges::begin(_M_derived()); + } + + constexpr decltype(auto) + front() const requires forward_range + { + __glibcxx_assert(!empty()); + return *ranges::begin(_M_derived()); + } + + constexpr decltype(auto) + back() + requires bidirectional_range<_Derived> && common_range<_Derived> + { + __glibcxx_assert(!empty()); + return *ranges::prev(ranges::end(_M_derived())); + } + + constexpr decltype(auto) + back() const + requires bidirectional_range + && common_range + { + __glibcxx_assert(!empty()); + return *ranges::prev(ranges::end(_M_derived())); + } + + template + constexpr decltype(auto) + operator[](range_difference_t<_Range> __n) + { return ranges::begin(_M_derived())[__n]; } + + template + constexpr decltype(auto) + operator[](range_difference_t<_Range> __n) const + { return ranges::begin(_M_derived())[__n]; } + }; + + namespace __detail + { + template + concept __pair_like + = !is_reference_v<_Tp> && requires(_Tp __t) + { + typename tuple_size<_Tp>::type; + requires derived_from, integral_constant>; + typename tuple_element_t<0, remove_const_t<_Tp>>; + typename tuple_element_t<1, remove_const_t<_Tp>>; + { get<0>(__t) } -> convertible_to&>; + { get<1>(__t) } -> convertible_to&>; + }; + + template + concept __pair_like_convertible_to + = !range<_Tp> && __pair_like> + && requires(_Tp&& __t) + { + { get<0>(std::forward<_Tp>(__t)) } -> convertible_to<_Up>; + { get<1>(std::forward<_Tp>(__t)) } -> convertible_to<_Vp>; + }; + + template + concept __pair_like_convertible_from + = !range<_Tp> && __pair_like<_Tp> + && constructible_from<_Tp, _Up, _Vp>; + + template + concept __iterator_sentinel_pair + = !range<_Tp> && __pair_like<_Tp> + && sentinel_for, tuple_element_t<0, _Tp>>; + + template> + using __make_unsigned_like_t + = conditional_t<_MaxDiff, __max_size_type, make_unsigned_t<_Tp>>; + + } // namespace __detail + + enum class subrange_kind : bool { unsized, sized }; + + template _Sent = _It, + subrange_kind _Kind = sized_sentinel_for<_Sent, _It> + ? subrange_kind::sized : subrange_kind::unsized> + requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>) + class subrange : public view_interface> + { + private: + static constexpr bool _S_store_size + = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>; + + _It _M_begin = _It(); + _Sent _M_end = _Sent(); + + template + struct _Size + { }; + + template + struct _Size<_Tp, true> + { __detail::__make_unsigned_like_t<_Tp> _M_size; }; + + [[no_unique_address]] _Size> _M_size = {}; + + public: + subrange() = default; + + constexpr + subrange(_It __i, _Sent __s) requires (!_S_store_size) + : _M_begin(std::move(__i)), _M_end(__s) + { } + + constexpr + subrange(_It __i, _Sent __s, + __detail::__make_unsigned_like_t> __n) + requires (_Kind == subrange_kind::sized) + : _M_begin(std::move(__i)), _M_end(__s) + { + using __detail::__to_unsigned_like; + __glibcxx_assert(__n == __to_unsigned_like(ranges::distance(__i, __s))); + if constexpr (_S_store_size) + _M_size._M_size = __n; + } + + template<__detail::__not_same_as _Rng> + requires __detail::__forwarding_range<_Rng> + && convertible_to, _It> + && convertible_to, _Sent> + constexpr + subrange(_Rng&& __r) requires (!_S_store_size || sized_range<_Rng>) + : subrange{ranges::begin(__r), ranges::end(__r)} + { + if constexpr (_S_store_size) + _M_size._M_size = ranges::size(__r); + } + + template<__detail::__forwarding_range _Rng> + requires convertible_to, _It> + && convertible_to, _Sent> + constexpr + subrange(_Rng&& __r, + __detail::__make_unsigned_like_t> __n) + requires (_Kind == subrange_kind::sized) + : subrange{ranges::begin(__r), ranges::end(__r), __n} + { } + + template<__detail::__not_same_as _PairLike> + requires __detail::__pair_like_convertible_to<_PairLike, _It, _Sent> + constexpr + subrange(_PairLike&& __r) requires (!_S_store_size) + : subrange{std::get<0>(std::forward<_PairLike>(__r)), + std::get<1>(std::forward<_PairLike>(__r))} + { } + + template<__detail::__pair_like_convertible_to<_It, _Sent> _PairLike> + constexpr + subrange(_PairLike&& __r, + __detail::__make_unsigned_like_t> __n) + requires (_Kind == subrange_kind::sized) + : subrange{std::get<0>(std::forward<_PairLike>(__r)), + std::get<1>(std::forward<_PairLike>(__r)), __n} + { } + + template<__detail::__not_same_as _PairLike> + requires __detail::__pair_like_convertible_from<_PairLike, const _It&, + const _Sent&> + constexpr + operator _PairLike() const + { return _PairLike(_M_begin, _M_end); } + + constexpr _It + begin() const requires copyable<_It> + { return _M_begin; } + + [[nodiscard]] constexpr _It + begin() requires (!copyable<_It>) + { return std::move(_M_begin); } + + constexpr _Sent end() const { return _M_end; } + + constexpr bool empty() const { return _M_begin == _M_end; } + + constexpr __detail::__make_unsigned_like_t> + size() const requires (_Kind == subrange_kind::sized) + { + if constexpr (_S_store_size) + return _M_size._M_size; + else + return __detail::__to_unsigned_like(_M_end - _M_begin); + } + + [[nodiscard]] constexpr subrange + next(iter_difference_t<_It> __n = 1) const & + requires forward_iterator<_It> + { + auto __tmp = *this; + __tmp.advance(__n); + return __tmp; + } + + [[nodiscard]] constexpr subrange + next(iter_difference_t<_It> __n = 1) && + { + advance(__n); + return std::move(*this); + } + + [[nodiscard]] constexpr subrange + prev(iter_difference_t<_It> __n = 1) const + requires bidirectional_iterator<_It> + { + auto __tmp = *this; + __tmp.advance(--__n); + return __tmp; + } + + constexpr subrange& + advance(iter_difference_t<_It> __n) + { + if constexpr (_S_store_size) + { + auto __d = __n - ranges::advance(_M_begin, __n, _M_end); + if (__d >= 0) + _M_size._M_size -= __detail::__to_unsigned_like(__d); + else + _M_size._M_size += __detail::__to_unsigned_like(-__d); + } + else + ranges::advance(_M_begin, __n, _M_end); + return *this; + } + + friend constexpr _It + begin(subrange&& __r) { return __r.begin(); } + + friend constexpr _Sent + end(subrange&& __r) { return __r.end(); } + }; + + template _Sent> + subrange(_It, _Sent, + __detail::__make_unsigned_like_t>) + -> subrange<_It, _Sent, subrange_kind::sized>; + + template<__detail::__iterator_sentinel_pair _Pr> + subrange(_Pr) + -> subrange, tuple_element_t<1, _Pr>>; + + template<__detail::__iterator_sentinel_pair _Pr> + subrange(_Pr, __detail::__make_unsigned_like_t>>) + -> subrange, tuple_element_t<1, _Pr>, + subrange_kind::sized>; + + template<__detail::__forwarding_range _Rng> + subrange(_Rng&&) + -> subrange, sentinel_t<_Rng>, + (sized_range<_Rng> + || sized_sentinel_for, iterator_t<_Rng>>) + ? subrange_kind::sized : subrange_kind::unsized>; + + template<__detail::__forwarding_range _Rng> + subrange(_Rng&&, + __detail::__make_unsigned_like_t>) + -> subrange, sentinel_t<_Rng>, subrange_kind::sized>; + + template + requires (_Num < 2) + constexpr auto + get(const subrange<_It, _Sent, _Kind>& __r) + { + if constexpr (_Num == 0) + return __r.begin(); + else + return __r.end(); + } + + template + requires (_Num < 2) + constexpr auto + get(subrange<_It, _Sent, _Kind>&& __r) + { + if constexpr (_Num == 0) + return __r.begin(); + else + return __r.end(); + } +} // namespace ranges + + using ranges::get; + +namespace ranges +{ + /// Type returned by algorithms instead of a dangling iterator or subrange. + struct dangling + { + constexpr dangling() noexcept = default; + template + constexpr dangling(_Args&&...) noexcept { } + }; + + template requires is_object_v<_Tp> + class empty_view : public view_interface> + { + public: + static constexpr _Tp* begin() noexcept { return nullptr; } + static constexpr _Tp* end() noexcept { return nullptr; } + static constexpr _Tp* data() noexcept { return nullptr; } + static constexpr size_t size() noexcept { return 0; } + static constexpr bool empty() noexcept { return true; } + + friend constexpr _Tp* begin(empty_view) noexcept { return nullptr; } + friend constexpr _Tp* end(empty_view) noexcept { return nullptr; } + }; + + namespace __detail + { + template requires is_object_v<_Tp> + struct __box : std::optional<_Tp> + { + using std::optional<_Tp>::optional; + + constexpr + __box() + noexcept(is_nothrow_default_constructible_v<_Tp>) + requires default_initializable<_Tp> + : std::optional<_Tp>{std::in_place} + { } + + using std::optional<_Tp>::operator=; + + __box& + operator=(const __box& __that) + noexcept(is_nothrow_copy_constructible_v<_Tp>) + requires (!assignable_from<_Tp&, const _Tp&>) + { + if ((bool)__that) + this->emplace(*__that); + else + this->reset(); + return *this; + } + + __box& + operator=(__box&& __that) + noexcept(is_nothrow_move_constructible_v<_Tp>) + requires (!assignable_from<_Tp&, _Tp>) + { + if ((bool)__that) + this->emplace(std::move(*__that)); + else + this->reset(); + return *this; + } + }; + + } // namespace __detail + + /// A view that contains exactly one element. + template requires is_object_v<_Tp> + class single_view : public view_interface> + { + public: + single_view() = default; + + constexpr explicit + single_view(const _Tp& __t) + : _M_value(__t) + { } + + constexpr explicit + single_view(_Tp&& __t) + : _M_value(std::move(__t)) + { } + + template + requires constructible_from<_Tp, _Args...> + constexpr + single_view(in_place_t, _Args&&... __args) + : _M_value{in_place, std::forward<_Args>(__args)...} + { } + + constexpr _Tp* + begin() noexcept + { return data(); } + + constexpr const _Tp* + begin() const noexcept + { return data(); } + + constexpr _Tp* + end() noexcept + { return data() + 1; } + + constexpr const _Tp* + end() const noexcept + { return data() + 1; } + + static constexpr size_t + size() noexcept + { return 1; } + + constexpr _Tp* + data() noexcept + { return _M_value.operator->(); } + + constexpr const _Tp* + data() const noexcept + { return _M_value.operator->(); } + + private: + __detail::__box<_Tp> _M_value; + }; + + namespace __detail + { + template + constexpr auto __to_signed_like(_Wp __w) noexcept + { + if constexpr (!integral<_Wp>) + return iter_difference_t<_Wp>(); + else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp)) + return iter_difference_t<_Wp>(__w); + else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp)) + return ptrdiff_t(__w); + else if constexpr (sizeof(long long) > sizeof(_Wp)) + return (long long)(__w); +#ifdef __SIZEOF_INT128__ + else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp)) + return __int128(__w); +#endif + else + return __max_diff_type(__w); + } + + template + using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>())); + + template + concept __decrementable = incrementable<_It> + && requires(_It __i) + { + { --__i } -> same_as<_It&>; + { __i-- } -> same_as<_It>; + }; + + template + concept __advanceable = __decrementable<_It> && totally_ordered<_It> + && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n) + { + { __i += __n } -> same_as<_It&>; + { __i -= __n } -> same_as<_It&>; + _It(__j + __n); + _It(__n + __j); + _It(__j - __n); + { __j - __j } -> convertible_to<__iota_diff_t<_It>>; + }; + + } // namespace __detail + + template + requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound> + class iota_view : public view_interface> + { + private: + struct _Iterator + { + private: + static auto + _S_iter_cat() + { + using namespace __detail; + if constexpr (__advanceable<_Winc>) + return random_access_iterator_tag{}; + else if constexpr (__decrementable<_Winc>) + return bidirectional_iterator_tag{}; + else if constexpr (incrementable<_Winc>) + return forward_iterator_tag{}; + else + return input_iterator_tag{}; + } + + public: + using iterator_category = decltype(_S_iter_cat()); + using value_type = _Winc; + using difference_type = __detail::__iota_diff_t<_Winc>; + + _Iterator() = default; + + constexpr explicit + _Iterator(_Winc __value) + : _M_value(__value) { } + + constexpr _Winc + operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>) + { return _M_value; } + + constexpr _Iterator& + operator++() + { + ++_M_value; + return *this; + } + + constexpr void + operator++(int) + { ++*this; } + + constexpr _Iterator + operator++(int) requires incrementable<_Winc> + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + constexpr _Iterator& + operator--() requires __detail::__decrementable<_Winc> + { + --_M_value; + return *this; + } + + constexpr _Iterator + operator--(int) requires __detail::__decrementable<_Winc> + { + auto __tmp = *this; + --*this; + return __tmp; + } + + constexpr _Iterator& + operator+=(difference_type __n) requires __detail::__advanceable<_Winc> + { + using namespace __detail; + if constexpr (__is_integer_like<_Winc> + && !__is_signed_integer_like<_Winc>) + { + if (__n >= difference_type(0)) + _M_value += static_cast<_Winc>(__n); + else + _M_value -= static_cast<_Winc>(-__n); + } + else + _M_value += __n; + return *this; + } + + constexpr _Iterator& + operator-=(difference_type __n) requires __detail::__advanceable<_Winc> + { + using namespace __detail; + if constexpr (__is_integer_like<_Winc> + && !__is_signed_integer_like<_Winc>) + { + if (__n >= difference_type(0)) + _M_value -= static_cast<_Winc>(__n); + else + _M_value += static_cast<_Winc>(-__n); + } + else + _M_value -= __n; + return *this; + } + + constexpr _Winc + operator[](difference_type __n) const + requires __detail::__advanceable<_Winc> + { return _Winc(_M_value + __n); } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + requires equality_comparable<_Winc> + { return __x._M_value == __y._M_value; } + + friend constexpr bool + operator<(const _Iterator& __x, const _Iterator& __y) + requires totally_ordered<_Winc> + { return __x._M_value < __y._M_value; } + + friend constexpr bool + operator>(const _Iterator& __x, const _Iterator& __y) + requires totally_ordered<_Winc> + { return __y < __x; } + + friend constexpr bool + operator<=(const _Iterator& __x, const _Iterator& __y) + requires totally_ordered<_Winc> + { return !(__y < __x); } + + friend constexpr bool + operator>=(const _Iterator& __x, const _Iterator& __y) + requires totally_ordered<_Winc> + { return !(__x < __y); } + +#ifdef __cpp_lib_threeway_comparison + friend constexpr compare_three_way_result_t<_Winc> + operator<=>(const _Iterator& __x, const _Iterator& __y) + requires totally_ordered<_Winc> && three_way_comparable<_Winc> + { return __x._M_value <=> __y._M_value; } +#endif + + friend constexpr _Iterator + operator+(_Iterator __i, difference_type __n) + requires __detail::__advanceable<_Winc> + { return __i += __n; } + + friend constexpr _Iterator + operator+(difference_type __n, _Iterator __i) + requires __detail::__advanceable<_Winc> + { return __i += __n; } + + friend constexpr _Iterator + operator-(_Iterator __i, difference_type __n) + requires __detail::__advanceable<_Winc> + { return __i -= __n; } + + friend constexpr difference_type + operator-(const _Iterator& __x, const _Iterator& __y) + requires __detail::__advanceable<_Winc> + { + using namespace __detail; + using _Dt = difference_type; + if constexpr (__is_integer_like<_Winc>) + { + if constexpr (__is_signed_integer_like<_Winc>) + return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value)); + else + return (__y._M_value > __x._M_value) + ? _Dt(-_Dt(__y._M_value - __x._M_value)) + : _Dt(__x._M_value - __y._M_value); + } + else + return __x._M_value - __y._M_value; + } + + private: + _Winc _M_value = _Winc(); + }; + + struct _Sentinel + { + private: + _Bound _M_bound = _Bound(); + + public: + _Sentinel() = default; + + constexpr explicit + _Sentinel(_Bound __bound) + : _M_bound(__bound) { } + + friend constexpr bool + operator==(const _Iterator& __x, const _Sentinel& __y) + { return __x._M_value == __y._M_bound; } + + friend constexpr iter_difference_t<_Winc> + operator-(const _Iterator& __x, const _Sentinel& __y) + requires sized_sentinel_for<_Bound, _Winc> + { return __x._M_value - __y._M_bound; } + + friend constexpr iter_difference_t<_Winc> + operator-(const _Sentinel& __x, const _Iterator& __y) + requires sized_sentinel_for<_Bound, _Winc> + { return -(__y - __x); } + }; + + _Winc _M_value = _Winc(); + _Bound _M_bound = _Bound(); + + public: + iota_view() = default; + + constexpr explicit + iota_view(_Winc __value) + : _M_value(__value) + { } + + constexpr + iota_view(type_identity_t<_Winc> __value, + type_identity_t<_Bound> __bound) + : _M_value(__value), _M_bound(__bound) + { + if constexpr (totally_ordered_with<_Winc, _Bound>) + __glibcxx_assert( bool(__value <= __bound) ); + } + + constexpr _Iterator + begin() const { return _Iterator{_M_value}; } + + constexpr auto + end() const + { + if constexpr (same_as<_Bound, unreachable_sentinel_t>) + return unreachable_sentinel; + else + return _Sentinel{_M_bound}; + } + + constexpr _Iterator + end() const requires same_as<_Winc, _Bound> + { return _Iterator{_M_bound}; } + + constexpr auto + size() const + requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>) + || (integral<_Winc> && integral<_Bound>) + || sized_sentinel_for<_Bound, _Winc> + { + using namespace __detail; + if constexpr (__is_integer_like<_Winc> && __is_integer_like<_Bound>) + return (_M_value < 0) + ? ((_M_bound < 0) + ? __to_unsigned_like(-_M_value) - __to_unsigned_like(-_M_bound) + : __to_unsigned_like(_M_bound) + __to_unsigned_like(-_M_value)) + : __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value); + else + return __to_unsigned_like(_M_bound - _M_value); + } + }; + + template + requires (!__detail::__is_integer_like<_Winc> + || !__detail::__is_integer_like<_Bound> + || (__detail::__is_signed_integer_like<_Winc> + == __detail::__is_signed_integer_like<_Bound>)) + iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>; + +namespace views +{ + template + inline constexpr empty_view<_Tp> empty{}; + + struct _Single + { + template + auto + operator()(_Tp&& __e) const + { return single_view{std::forward<_Tp>(__e)}; } + }; + + inline constexpr _Single single{}; + + struct _Iota + { + template + auto + operator()(_Tp&& __e) const + { return iota_view{std::forward<_Tp>(__e)}; } + + template + auto + operator()(_Tp&& __e, _Up&& __f) const + { return iota_view{std::forward<_Tp>(__e), std::forward<_Tp>(__f)}; } + }; + + inline constexpr _Iota iota{}; + +} // namespace views } // namespace ranges _GLIBCXX_END_NAMESPACE_VERSION } // namespace diff --git a/libstdc++-v3/testsuite/std/ranges/empty_view.cc b/libstdc++-v3/testsuite/std/ranges/empty_view.cc new file mode 100644 index 00000000000..6524b37d699 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/empty_view.cc @@ -0,0 +1,35 @@ +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do compile { target c++2a } } + +#include + +static_assert(std::ranges::view>); + +std::ranges::empty_view e; +static_assert(std::ranges::empty(e)); +static_assert(0 == e.size()); + +static_assert(e.begin() == nullptr); +static_assert(e.end() == nullptr); +static_assert(e.data() == nullptr); +static_assert(e.empty()); + +static_assert(begin(e) == nullptr); +static_assert(end(e) == nullptr); diff --git a/libstdc++-v3/testsuite/std/ranges/iota_view.cc b/libstdc++-v3/testsuite/std/ranges/iota_view.cc new file mode 100644 index 00000000000..db63f89d898 --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/iota_view.cc @@ -0,0 +1,70 @@ +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +void +test01() +{ + int vals[5] = { }; + int* out = vals; + for (int i : std::ranges::iota_view{1, 4}) + *out++ = i; + VERIFY(out == vals + 3); + VERIFY(vals[0] == 1); + VERIFY(vals[1] == 2); + VERIFY(vals[2] == 3); + VERIFY(vals[3] == 0); +} + +void +test02() +{ + auto v = std::ranges::views::iota(4); + auto it = v.begin(); + VERIFY( *it == 4 ); + ++it; + VERIFY( *it == 5 ); + it++; + VERIFY( *it == 6 ); +} + +void +test03() +{ + auto v = std::ranges::views::iota(10, 15); + auto it = v.begin(); + VERIFY( *it == 10 ); + it += 2; + VERIFY( *it == 12 ); + it += 2; + VERIFY( *it == 14 ); + ++it; + VERIFY( it == v.end() ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/single_view.cc b/libstdc++-v3/testsuite/std/ranges/single_view.cc new file mode 100644 index 00000000000..785ece1b9bf --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/single_view.cc @@ -0,0 +1,66 @@ +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +void +test01() +{ + std::ranges::single_view s{4}; + static_assert(std::same_as, int>); + static_assert(std::ranges::size(s) == 1); + + int count = 0; + for (auto i : s) + ++count; + VERIFY(count == 1); + VERIFY(*std::ranges::begin(s) == 4); +} + +void +test02() +{ + std::ranges::single_view s2; + static_assert(std::same_as, long>); + static_assert(std::ranges::size(s2) == 1); + + int count = 0; + for (auto l : s2) + ++count; + VERIFY(count == 1); + VERIFY(*std::ranges::begin(s2) == 0L); +} + +void +test03() +{ + auto s3 = std::ranges::views::single('a'); + static_assert(std::same_as, char>); + static_assert(std::ranges::size(s3) == 1); + VERIFY(*std::ranges::begin(s3) == 'a'); +} + +int main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/view.cc b/libstdc++-v3/testsuite/std/ranges/view.cc new file mode 100644 index 00000000000..fc1e04e06ad --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/view.cc @@ -0,0 +1,55 @@ +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do compile { target c++2a } } + +#include +#include +#include +#include +#include +#include + +static_assert(std::ranges::view>); +static_assert(!std::ranges::view>); +static_assert(!std::ranges::view>); +static_assert(!std::ranges::view>); +static_assert(!std::ranges::view>); +static_assert(!std::ranges::view>); +static_assert(!std::ranges::view>); +static_assert(!std::ranges::view>); +static_assert(!std::ranges::view>); +static_assert(!std::ranges::view); + +// const test_random_access_range is not a range: +static_assert(!std::ranges::view<__gnu_test::test_random_access_range>); + +template +struct test_view +: __gnu_test::test_random_access_range, std::ranges::view_base +{ + // views must be default-initializable: + test_view() : __gnu_test::test_random_access_range(nullptr, nullptr) { } +}; + +static_assert(std::ranges::view>); + +template<> +constexpr bool std::ranges::enable_view> = false; + +static_assert(!std::ranges::view>);