From 160061ac10f9143d9698daac5f7e46b5a615825c Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Tue, 22 Sep 2020 15:45:54 +0100 Subject: [PATCH] libstdc++: Introduce new headers for C++20 ranges components This introduces two new headers: defines the minimal components needed for using C++20 ranges (customization point objects such as std::ranges::begin, concepts such as std::ranges::range, etc.) includes and additionally defines subrange, which is needed by . Most of the content of was previously defined in , but a few pieces were only defined in . This meant the entire header was needed in and , even though they don't use all the range adaptors. By moving the ranges components out of that file is left defining just the contents of [iterator.range] i.e. std::begin, std::end, std::size etc. and not C++20 ranges components. For consistency with other C++20 ranges headers, is renamed to . libstdc++-v3/ChangeLog: * include/Makefile.am: Add new headers and adjust for renamed header. * include/Makefile.in: Regenerate. * include/bits/iterator_concepts.h: Adjust for renamed header. * include/bits/range_access.h (ranges::*): Move to new header. * include/bits/ranges_algobase.h: Include new header instead of . * include/bits/ranges_algo.h: Include new header. * include/bits/range_cmp.h: Moved to... * include/bits/ranges_cmp.h: ...here. * include/bits/ranges_base.h: New header. * include/bits/ranges_util.h: New header. * include/experimental/string_view: Include new header. * include/std/functional: Adjust for renamed header. * include/std/ranges (ranges::view_base, ranges::enable_view) (ranges::dangling, ranges::borrowed_iterator_t): Move to new header. (ranges::view_interface, ranges::subrange) (ranges::borrowed_subrange_t): Move to new header. * include/std/span: Include new header. * include/std/string_view: Likewise. * testsuite/24_iterators/back_insert_iterator/pr93884.cc: Add missing header. * testsuite/24_iterators/front_insert_iterator/pr93884.cc: Likewise. --- libstdc++-v3/include/Makefile.am | 4 +- libstdc++-v3/include/Makefile.in | 4 +- libstdc++-v3/include/bits/iterator_concepts.h | 2 +- libstdc++-v3/include/bits/range_access.h | 827 +--------------- libstdc++-v3/include/bits/ranges_algo.h | 1 + libstdc++-v3/include/bits/ranges_algobase.h | 5 +- libstdc++-v3/include/bits/ranges_base.h | 887 ++++++++++++++++++ .../bits/{range_cmp.h => ranges_cmp.h} | 8 +- libstdc++-v3/include/bits/ranges_util.h | 417 ++++++++ libstdc++-v3/include/experimental/string_view | 1 + libstdc++-v3/include/std/functional | 2 +- libstdc++-v3/include/std/ranges | 415 +------- libstdc++-v3/include/std/span | 2 +- libstdc++-v3/include/std/string_view | 1 + .../back_insert_iterator/pr93884.cc | 1 + .../front_insert_iterator/pr93884.cc | 1 + 16 files changed, 1341 insertions(+), 1237 deletions(-) create mode 100644 libstdc++-v3/include/bits/ranges_base.h rename libstdc++-v3/include/bits/{range_cmp.h => ranges_cmp.h} (98%) create mode 100644 libstdc++-v3/include/bits/ranges_util.h diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index c9df9a9d6c6..28d273924ee 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -158,10 +158,12 @@ bits_headers = \ ${bits_srcdir}/random.h \ ${bits_srcdir}/random.tcc \ ${bits_srcdir}/range_access.h \ - ${bits_srcdir}/range_cmp.h \ ${bits_srcdir}/ranges_algobase.h \ ${bits_srcdir}/ranges_algo.h \ + ${bits_srcdir}/ranges_base.h \ + ${bits_srcdir}/ranges_cmp.h \ ${bits_srcdir}/ranges_uninitialized.h \ + ${bits_srcdir}/ranges_util.h \ ${bits_srcdir}/refwrap.h \ ${bits_srcdir}/regex.h \ ${bits_srcdir}/regex.tcc \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 3d86b733ccd..2dfd8d2cb36 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -504,10 +504,12 @@ bits_headers = \ ${bits_srcdir}/random.h \ ${bits_srcdir}/random.tcc \ ${bits_srcdir}/range_access.h \ - ${bits_srcdir}/range_cmp.h \ ${bits_srcdir}/ranges_algobase.h \ ${bits_srcdir}/ranges_algo.h \ + ${bits_srcdir}/ranges_base.h \ + ${bits_srcdir}/ranges_cmp.h \ ${bits_srcdir}/ranges_uninitialized.h \ + ${bits_srcdir}/ranges_util.h \ ${bits_srcdir}/refwrap.h \ ${bits_srcdir}/regex.h \ ${bits_srcdir}/regex.tcc \ diff --git a/libstdc++-v3/include/bits/iterator_concepts.h b/libstdc++-v3/include/bits/iterator_concepts.h index a568f2ab825..8ff4f8667dd 100644 --- a/libstdc++-v3/include/bits/iterator_concepts.h +++ b/libstdc++-v3/include/bits/iterator_concepts.h @@ -34,7 +34,7 @@ #include #include // to_address -#include // identity, ranges::less +#include // identity, ranges::less #if __cpp_lib_concepts namespace std _GLIBCXX_VISIBILITY(default) diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h index 5c5b2fe0c6c..c8d8185172d 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -1,4 +1,4 @@ -// -*- C++ -*- +// Range access functions for containers -*- C++ -*- // Copyright (C) 2010-2020 Free Software Foundation, Inc. // @@ -34,11 +34,7 @@ #if __cplusplus >= 201103L #include -#include -#include -#if __cplusplus > 201703L -#include -#endif +#include // common_type_t, make_signed_t namespace std _GLIBCXX_VISIBILITY(default) { @@ -322,8 +318,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION data(initializer_list<_Tp> __il) noexcept { return __il.begin(); } -#endif // C++17 - #if __cplusplus > 201703L #define __cpp_lib_ssize 201902L template @@ -340,824 +334,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION constexpr ptrdiff_t ssize(const _Tp (&)[_Num]) noexcept { return _Num; } - -#ifdef __cpp_lib_concepts -namespace ranges -{ - template - inline constexpr bool disable_sized_range = false; - - template - inline constexpr bool enable_borrowed_range = false; - - template - extern const bool enable_view; - - namespace __detail - { - constexpr __max_size_type - __to_unsigned_like(__max_size_type __t) noexcept - { return __t; } - - constexpr __max_size_type - __to_unsigned_like(__max_diff_type __t) noexcept - { return __max_size_type(__t); } - - template - constexpr auto - __to_unsigned_like(_Tp __t) noexcept - { return static_cast>(__t); } - -#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__ - constexpr unsigned __int128 - __to_unsigned_like(__int128 __t) noexcept - { return __t; } - - constexpr unsigned __int128 - __to_unsigned_like(unsigned __int128 __t) noexcept - { return __t; } -#endif - - template - using __make_unsigned_like_t - = decltype(__detail::__to_unsigned_like(std::declval<_Tp>())); - - // Part of the constraints of ranges::borrowed_range - template - concept __maybe_borrowed_range - = is_lvalue_reference_v<_Tp> - || enable_borrowed_range>; - - } // namespace __detail - - namespace __cust_access - { - using std::ranges::__detail::__maybe_borrowed_range; - using std::__detail::__class_or_enum; - using std::__detail::__decay_copy; - using std::__detail::__member_begin; - using std::__detail::__adl_begin; - - struct _Begin - { - private: - template - static constexpr bool - _S_noexcept() - { - if constexpr (is_array_v>) - return true; - else if constexpr (__member_begin<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp&>().begin())); - else - return noexcept(__decay_copy(begin(std::declval<_Tp&>()))); - } - - public: - template<__maybe_borrowed_range _Tp> - requires is_array_v> || __member_begin<_Tp> - || __adl_begin<_Tp> - constexpr auto - operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) - { - if constexpr (is_array_v>) - { - static_assert(is_lvalue_reference_v<_Tp>); - using _Up = remove_all_extents_t>; - static_assert(sizeof(_Up) != 0, "not array of incomplete type"); - return __t + 0; - } - else if constexpr (__member_begin<_Tp>) - return __t.begin(); - else - return begin(__t); - } - }; - - template - concept __member_end = requires(_Tp& __t) - { - { __decay_copy(__t.end()) } - -> sentinel_for(__t)))>; - }; - - void end(auto&) = delete; - void end(const auto&) = delete; - - template - concept __adl_end = __class_or_enum> - && requires(_Tp& __t) - { - { __decay_copy(end(__t)) } - -> sentinel_for(__t)))>; - }; - - struct _End - { - private: - template - static constexpr bool - _S_noexcept() - { - if constexpr (is_bounded_array_v>) - return true; - else if constexpr (__member_end<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp&>().end())); - else - return noexcept(__decay_copy(end(std::declval<_Tp&>()))); - } - - public: - template<__maybe_borrowed_range _Tp> - requires is_bounded_array_v> || __member_end<_Tp> - || __adl_end<_Tp> - constexpr auto - operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) - { - if constexpr (is_bounded_array_v>) - { - static_assert(is_lvalue_reference_v<_Tp>); - return __t + extent_v>; - } - else if constexpr (__member_end<_Tp>) - return __t.end(); - else - return end(__t); - } - }; - - template - constexpr decltype(auto) - __as_const(_Tp&& __t) noexcept - { - if constexpr (is_lvalue_reference_v<_Tp>) - return static_cast&>(__t); - else - return static_cast(__t); - } - - struct _CBegin - { - template - constexpr auto - operator()(_Tp&& __e) const - noexcept(noexcept(_Begin{}(__cust_access::__as_const((_Tp&&)__e)))) - requires requires { _Begin{}(__cust_access::__as_const((_Tp&&)__e)); } - { - return _Begin{}(__cust_access::__as_const(std::forward<_Tp>(__e))); - } - }; - - struct _CEnd - { - template - constexpr auto - operator()(_Tp&& __e) const - noexcept(noexcept(_End{}(__cust_access::__as_const((_Tp&&)__e)))) - requires requires { _End{}(__cust_access::__as_const((_Tp&&)__e)); } - { - return _End{}(__cust_access::__as_const(std::forward<_Tp>(__e))); - } - }; - - template - concept __member_rbegin = requires(_Tp& __t) - { - { __decay_copy(__t.rbegin()) } -> input_or_output_iterator; - }; - - void rbegin(auto&) = delete; - void rbegin(const auto&) = delete; - - template - concept __adl_rbegin = __class_or_enum> - && requires(_Tp& __t) - { - { __decay_copy(rbegin(__t)) } -> input_or_output_iterator; - }; - - template - concept __reversable = requires(_Tp& __t) - { - { _Begin{}(__t) } -> bidirectional_iterator; - { _End{}(__t) } -> same_as; - }; - - struct _RBegin - { - private: - template - static constexpr bool - _S_noexcept() - { - if constexpr (__member_rbegin<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp&>().rbegin())); - else if constexpr (__adl_rbegin<_Tp>) - return noexcept(__decay_copy(rbegin(std::declval<_Tp&>()))); - else - { - if constexpr (noexcept(_End{}(std::declval<_Tp&>()))) - { - using _It = decltype(_End{}(std::declval<_Tp&>())); - // std::reverse_iterator copy-initializes its member. - return is_nothrow_copy_constructible_v<_It>; - } - else - return false; - } - } - - public: - template<__maybe_borrowed_range _Tp> - requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp> - constexpr auto - operator()(_Tp&& __t) const - noexcept(_S_noexcept<_Tp>()) - { - if constexpr (__member_rbegin<_Tp>) - return __t.rbegin(); - else if constexpr (__adl_rbegin<_Tp>) - return rbegin(__t); - else - return std::make_reverse_iterator(_End{}(__t)); - } - }; - - template - concept __member_rend = requires(_Tp& __t) - { - { __decay_copy(__t.rend()) } - -> sentinel_for; - }; - - void rend(auto&) = delete; - void rend(const auto&) = delete; - - template - concept __adl_rend = __class_or_enum> - && requires(_Tp& __t) - { - { __decay_copy(rend(__t)) } - -> sentinel_for(__t)))>; - }; - - struct _REnd - { - private: - template - static constexpr bool - _S_noexcept() - { - if constexpr (__member_rend<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp&>().rend())); - else if constexpr (__adl_rend<_Tp>) - return noexcept(__decay_copy(rend(std::declval<_Tp&>()))); - else - { - if constexpr (noexcept(_Begin{}(std::declval<_Tp&>()))) - { - using _It = decltype(_Begin{}(std::declval<_Tp&>())); - // std::reverse_iterator copy-initializes its member. - return is_nothrow_copy_constructible_v<_It>; - } - else - return false; - } - } - - public: - template<__maybe_borrowed_range _Tp> - requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp> - constexpr auto - operator()(_Tp&& __t) const - noexcept(_S_noexcept<_Tp>()) - { - if constexpr (__member_rend<_Tp>) - return __t.rend(); - else if constexpr (__adl_rend<_Tp>) - return rend(__t); - else - return std::make_reverse_iterator(_Begin{}(__t)); - } - }; - - struct _CRBegin - { - template - constexpr auto - operator()(_Tp&& __e) const - noexcept(noexcept(_RBegin{}(__cust_access::__as_const((_Tp&&)__e)))) - requires requires { _RBegin{}(__cust_access::__as_const((_Tp&&)__e)); } - { - return _RBegin{}(__cust_access::__as_const(std::forward<_Tp>(__e))); - } - }; - - struct _CREnd - { - template - constexpr auto - operator()(_Tp&& __e) const - noexcept(noexcept(_REnd{}(__cust_access::__as_const((_Tp&&)__e)))) - requires requires { _REnd{}(__cust_access::__as_const((_Tp&&)__e)); } - { - return _REnd{}(__cust_access::__as_const(std::forward<_Tp>(__e))); - } - }; - - template - concept __member_size = !disable_sized_range> - && requires(_Tp&& __t) - { - { __decay_copy(std::forward<_Tp>(__t).size()) } - -> __detail::__is_integer_like; - }; - - void size(auto&) = delete; - void size(const auto&) = delete; - - template - concept __adl_size = __class_or_enum> - && !disable_sized_range> - && requires(_Tp&& __t) - { - { __decay_copy(size(std::forward<_Tp>(__t))) } - -> __detail::__is_integer_like; - }; - - template - concept __sentinel_size = requires(_Tp&& __t) - { - { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator; - - { _End{}(std::forward<_Tp>(__t)) } - -> sized_sentinel_for(__t)))>; - }; - - struct _Size - { - private: - template - static constexpr bool - _S_noexcept() - { - if constexpr (is_bounded_array_v>) - return true; - else if constexpr (__member_size<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp>().size())); - else if constexpr (__adl_size<_Tp>) - return noexcept(__decay_copy(size(std::declval<_Tp>()))); - else if constexpr (__sentinel_size<_Tp>) - return noexcept(_End{}(std::declval<_Tp>()) - - _Begin{}(std::declval<_Tp>())); - } - - public: - template - requires is_bounded_array_v> - || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp> - constexpr auto - operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>()) - { - if constexpr (is_bounded_array_v>) - { - return extent_v>; - } - else if constexpr (__member_size<_Tp>) - return std::forward<_Tp>(__e).size(); - else if constexpr (__adl_size<_Tp>) - return size(std::forward<_Tp>(__e)); - else if constexpr (__sentinel_size<_Tp>) - return __detail::__to_unsigned_like( - _End{}(std::forward<_Tp>(__e)) - - _Begin{}(std::forward<_Tp>(__e))); - } - }; - - struct _SSize - { - template - requires requires (_Tp&& __e) - { - _Begin{}(std::forward<_Tp>(__e)); - _Size{}(std::forward<_Tp>(__e)); - } - constexpr auto - operator()(_Tp&& __e) const - noexcept(noexcept(_Size{}(std::forward<_Tp>(__e)))) - { - using __iter_type = decltype(_Begin{}(std::forward<_Tp>(__e))); - using __diff_type = iter_difference_t<__iter_type>; - using __gnu_cxx::__int_traits; - auto __size = _Size{}(std::forward<_Tp>(__e)); - if constexpr (integral<__diff_type>) - { - if constexpr (__int_traits<__diff_type>::__digits - < __int_traits::__digits) - return static_cast(__size); - } - return static_cast<__diff_type>(__size); - } - }; - - template - concept __member_empty = requires(_Tp&& __t) - { bool(std::forward<_Tp>(__t).empty()); }; - - template - concept __size0_empty = requires(_Tp&& __t) - { _Size{}(std::forward<_Tp>(__t)) == 0; }; - - template - concept __eq_iter_empty = requires(_Tp&& __t) - { - { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator; - bool(_Begin{}(std::forward<_Tp>(__t)) - == _End{}(std::forward<_Tp>(__t))); - }; - - struct _Empty - { - private: - template - static constexpr bool - _S_noexcept() - { - if constexpr (__member_empty<_Tp>) - return noexcept(std::declval<_Tp>().empty()); - else if constexpr (__size0_empty<_Tp>) - return noexcept(_Size{}(std::declval<_Tp>()) == 0); - else - return noexcept(bool(_Begin{}(std::declval<_Tp>()) - == _End{}(std::declval<_Tp>()))); - } - - public: - template - requires __member_empty<_Tp> || __size0_empty<_Tp> - || __eq_iter_empty<_Tp> - constexpr bool - operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>()) - { - if constexpr (__member_empty<_Tp>) - return bool(std::forward<_Tp>(__e).empty()); - else if constexpr (__size0_empty<_Tp>) - return _Size{}(std::forward<_Tp>(__e)) == 0; - else - return bool(_Begin{}(std::forward<_Tp>(__e)) - == _End{}(std::forward<_Tp>(__e))); - } - }; - - template - concept __pointer_to_object = is_pointer_v<_Tp> - && is_object_v>; - - template - concept __member_data = is_lvalue_reference_v<_Tp> - && requires(_Tp __t) { { __t.data() } -> __pointer_to_object; }; - - template - concept __begin_data = requires(_Tp&& __t) - { { _Begin{}(std::forward<_Tp>(__t)) } -> contiguous_iterator; }; - - struct _Data - { - private: - template - static constexpr bool - _S_noexcept() - { - if constexpr (__member_data<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp>().data())); - else - return noexcept(_Begin{}(std::declval<_Tp>())); - } - - public: - template<__maybe_borrowed_range _Tp> - requires __member_data<_Tp> || __begin_data<_Tp> - constexpr auto - operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>()) - { - if constexpr (__member_data<_Tp>) - return __e.data(); - else - return std::to_address(_Begin{}(std::forward<_Tp>(__e))); - } - }; - - struct _CData - { - template - constexpr auto - operator()(_Tp&& __e) const - noexcept(noexcept(_Data{}(__cust_access::__as_const((_Tp&&)__e)))) - requires requires { _Data{}(__cust_access::__as_const((_Tp&&)__e)); } - { - return _Data{}(__cust_access::__as_const(std::forward<_Tp>(__e))); - } - }; - - } // namespace __cust_access - - inline namespace __cust - { - inline constexpr __cust_access::_Begin begin{}; - inline constexpr __cust_access::_End end{}; - inline constexpr __cust_access::_CBegin cbegin{}; - inline constexpr __cust_access::_CEnd cend{}; - inline constexpr __cust_access::_RBegin rbegin{}; - inline constexpr __cust_access::_REnd rend{}; - inline constexpr __cust_access::_CRBegin crbegin{}; - inline constexpr __cust_access::_CREnd crend{}; - inline constexpr __cust_access::_Size size{}; - inline constexpr __cust_access::_SSize ssize{}; - inline constexpr __cust_access::_Empty empty{}; - inline constexpr __cust_access::_Data data{}; - inline constexpr __cust_access::_CData cdata{}; - } - - /// [range.range] The range concept. - template - concept range = requires(_Tp& __t) - { - ranges::begin(__t); - ranges::end(__t); - }; - - /// [range.range] The borrowed_range concept. - template - concept borrowed_range - = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>; - - template - using iterator_t = std::__detail::__range_iter_t<_Tp>; - - template - using sentinel_t = decltype(ranges::end(std::declval<_Range&>())); - - template - using range_difference_t = iter_difference_t>; - - template - using range_value_t = iter_value_t>; - - template - using range_reference_t = iter_reference_t>; - - template - using range_rvalue_reference_t - = iter_rvalue_reference_t>; - - /// [range.sized] The sized_range concept. - template - concept sized_range = range<_Tp> - && requires(_Tp& __t) { ranges::size(__t); }; - - template - using range_size_t = decltype(ranges::size(std::declval<_Range&>())); - - // [range.refinements] - - /// A range for which ranges::begin returns an output iterator. - template - concept output_range - = range<_Range> && output_iterator, _Tp>; - - /// A range for which ranges::begin returns an input iterator. - template - concept input_range = range<_Tp> && input_iterator>; - - /// A range for which ranges::begin returns a forward iterator. - template - concept forward_range - = input_range<_Tp> && forward_iterator>; - - /// A range for which ranges::begin returns a bidirectional iterator. - template - concept bidirectional_range - = forward_range<_Tp> && bidirectional_iterator>; - - /// A range for which ranges::begin returns a random access iterator. - template - concept random_access_range - = bidirectional_range<_Tp> && random_access_iterator>; - - /// A range for which ranges::begin returns a contiguous iterator. - template - concept contiguous_range - = random_access_range<_Tp> && contiguous_iterator> - && requires(_Tp& __t) - { - { ranges::data(__t) } -> same_as>>; - }; - - /// A range for which ranges::begin and ranges::end return the same type. - template - concept common_range - = range<_Tp> && same_as, sentinel_t<_Tp>>; - - // [range.iter.ops] range iterator operations - - template - constexpr void - advance(_It& __it, iter_difference_t<_It> __n) - { - if constexpr (random_access_iterator<_It>) - __it += __n; - else if constexpr (bidirectional_iterator<_It>) - { - if (__n > 0) - { - do - { - ++__it; - } - while (--__n); - } - else if (__n < 0) - { - do - { - --__it; - } - while (++__n); - } - } - else - { - // cannot decrement a non-bidirectional iterator - __glibcxx_assert(__n >= 0); - while (__n-- > 0) - ++__it; - } - } - - template _Sent> - constexpr void - advance(_It& __it, _Sent __bound) - { - if constexpr (assignable_from<_It&, _Sent>) - __it = std::move(__bound); - else if constexpr (sized_sentinel_for<_Sent, _It>) - ranges::advance(__it, __bound - __it); - else - { - while (__it != __bound) - ++__it; - } - } - - template _Sent> - constexpr iter_difference_t<_It> - advance(_It& __it, iter_difference_t<_It> __n, _Sent __bound) - { - if constexpr (sized_sentinel_for<_Sent, _It>) - { - const auto __diff = __bound - __it; -#ifdef __cpp_lib_is_constant_evaluated - if (std::is_constant_evaluated() - && !(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0))) - throw "inconsistent directions for distance and bound"; -#endif - // n and bound must not lead in opposite directions: - __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0)); - const auto __absdiff = __diff < 0 ? -__diff : __diff; - const auto __absn = __n < 0 ? -__n : __n;; - if (__absn >= __absdiff) - { - ranges::advance(__it, __bound); - return __n - __diff; - } - else - { - ranges::advance(__it, __n); - return 0; - } - } - else if (__it == __bound || __n == 0) - return iter_difference_t<_It>(0); - else if (__n > 0) - { - iter_difference_t<_It> __m = 0; - do - { - ++__it; - ++__m; - } - while (__m != __n && __it != __bound); - return __n - __m; - } - else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>) - { - iter_difference_t<_It> __m = 0; - do - { - --__it; - --__m; - } - while (__m != __n && __it != __bound); - return __n - __m; - } - else - { - // cannot decrement a non-bidirectional iterator - __glibcxx_assert(__n >= 0); - return __n; - } - } - - template _Sent> - constexpr iter_difference_t<_It> - distance(_It __first, _Sent __last) - { - if constexpr (sized_sentinel_for<_Sent, _It>) - return __last - __first; - else - { - iter_difference_t<_It> __n = 0; - while (__first != __last) - { - ++__first; - ++__n; - } - return __n; - } - } - - template - constexpr range_difference_t<_Range> - distance(_Range&& __r) - { - if constexpr (sized_range<_Range>) - return static_cast>(ranges::size(__r)); - else - return ranges::distance(ranges::begin(__r), ranges::end(__r)); - } - - template - constexpr _It - next(_It __x) - { - ++__x; - return __x; - } - - template - constexpr _It - next(_It __x, iter_difference_t<_It> __n) - { - ranges::advance(__x, __n); - return __x; - } - - template _Sent> - constexpr _It - next(_It __x, _Sent __bound) - { - ranges::advance(__x, __bound); - return __x; - } - - template _Sent> - constexpr _It - next(_It __x, iter_difference_t<_It> __n, _Sent __bound) - { - ranges::advance(__x, __n, __bound); - return __x; - } - - template - constexpr _It - prev(_It __x) - { - --__x; - return __x; - } - - template - constexpr _It - prev(_It __x, iter_difference_t<_It> __n) - { - ranges::advance(__x, -__n); - return __x; - } - - template - constexpr _It - prev(_It __x, iter_difference_t<_It> __n, _It __bound) - { - ranges::advance(__x, -__n, __bound); - return __x; - } - -} // namespace ranges -#endif // library concepts #endif // C++20 + +#endif // C++17 _GLIBCXX_END_NAMESPACE_VERSION } // namespace #endif // C++11 - #endif // _GLIBCXX_RANGE_ACCESS_H diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index a5539650edc..61673e38fa6 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -33,6 +33,7 @@ #if __cplusplus > 201703L #include +#include #include // concept uniform_random_bit_generator #if __cpp_lib_concepts diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h index 2adff643ac2..eb8573972fa 100644 --- a/libstdc++-v3/include/bits/ranges_algobase.h +++ b/libstdc++-v3/include/bits/ranges_algobase.h @@ -34,9 +34,8 @@ #include #include -// #include -#include -#include +#include // ranges::begin, ranges::range etc. +#include // __invoke #include // __is_byte #if __cpp_lib_concepts diff --git a/libstdc++-v3/include/bits/ranges_base.h b/libstdc++-v3/include/bits/ranges_base.h new file mode 100644 index 00000000000..681b24e5cce --- /dev/null +++ b/libstdc++-v3/include/bits/ranges_base.h @@ -0,0 +1,887 @@ +// Core concepts and definitions for -*- C++ -*- + +// Copyright (C) 2019-2020 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file bits/ranges_base.h + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{ranges} + */ + +#ifndef _GLIBCXX_RANGES_BASE_H +#define _GLIBCXX_RANGES_BASE_H 1 + +#pragma GCC system_header + +#if __cplusplus > 201703L +#include +#include +#include + +#ifdef __cpp_lib_concepts +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION +namespace ranges +{ + template + inline constexpr bool disable_sized_range = false; + + template + inline constexpr bool enable_borrowed_range = false; + + namespace __detail + { + constexpr __max_size_type + __to_unsigned_like(__max_size_type __t) noexcept + { return __t; } + + constexpr __max_size_type + __to_unsigned_like(__max_diff_type __t) noexcept + { return __max_size_type(__t); } + + template + constexpr auto + __to_unsigned_like(_Tp __t) noexcept + { return static_cast>(__t); } + +#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__ + constexpr unsigned __int128 + __to_unsigned_like(__int128 __t) noexcept + { return __t; } + + constexpr unsigned __int128 + __to_unsigned_like(unsigned __int128 __t) noexcept + { return __t; } +#endif + + template + using __make_unsigned_like_t + = decltype(__detail::__to_unsigned_like(std::declval<_Tp>())); + + // Part of the constraints of ranges::borrowed_range + template + concept __maybe_borrowed_range + = is_lvalue_reference_v<_Tp> + || enable_borrowed_range>; + + } // namespace __detail + + namespace __cust_access + { + using std::ranges::__detail::__maybe_borrowed_range; + using std::__detail::__class_or_enum; + using std::__detail::__decay_copy; + using std::__detail::__member_begin; + using std::__detail::__adl_begin; + + struct _Begin + { + private: + template + static constexpr bool + _S_noexcept() + { + if constexpr (is_array_v>) + return true; + else if constexpr (__member_begin<_Tp>) + return noexcept(__decay_copy(std::declval<_Tp&>().begin())); + else + return noexcept(__decay_copy(begin(std::declval<_Tp&>()))); + } + + public: + template<__maybe_borrowed_range _Tp> + requires is_array_v> || __member_begin<_Tp> + || __adl_begin<_Tp> + constexpr auto + operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) + { + if constexpr (is_array_v>) + { + static_assert(is_lvalue_reference_v<_Tp>); + using _Up = remove_all_extents_t>; + static_assert(sizeof(_Up) != 0, "not array of incomplete type"); + return __t + 0; + } + else if constexpr (__member_begin<_Tp>) + return __t.begin(); + else + return begin(__t); + } + }; + + template + concept __member_end = requires(_Tp& __t) + { + { __decay_copy(__t.end()) } + -> sentinel_for(__t)))>; + }; + + void end(auto&) = delete; + void end(const auto&) = delete; + + template + concept __adl_end = __class_or_enum> + && requires(_Tp& __t) + { + { __decay_copy(end(__t)) } + -> sentinel_for(__t)))>; + }; + + struct _End + { + private: + template + static constexpr bool + _S_noexcept() + { + if constexpr (is_bounded_array_v>) + return true; + else if constexpr (__member_end<_Tp>) + return noexcept(__decay_copy(std::declval<_Tp&>().end())); + else + return noexcept(__decay_copy(end(std::declval<_Tp&>()))); + } + + public: + template<__maybe_borrowed_range _Tp> + requires is_bounded_array_v> || __member_end<_Tp> + || __adl_end<_Tp> + constexpr auto + operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) + { + if constexpr (is_bounded_array_v>) + { + static_assert(is_lvalue_reference_v<_Tp>); + return __t + extent_v>; + } + else if constexpr (__member_end<_Tp>) + return __t.end(); + else + return end(__t); + } + }; + + template + constexpr decltype(auto) + __as_const(_Tp&& __t) noexcept + { + if constexpr (is_lvalue_reference_v<_Tp>) + return static_cast&>(__t); + else + return static_cast(__t); + } + + struct _CBegin + { + template + constexpr auto + operator()(_Tp&& __e) const + noexcept(noexcept(_Begin{}(__cust_access::__as_const((_Tp&&)__e)))) + requires requires { _Begin{}(__cust_access::__as_const((_Tp&&)__e)); } + { + return _Begin{}(__cust_access::__as_const(std::forward<_Tp>(__e))); + } + }; + + struct _CEnd + { + template + constexpr auto + operator()(_Tp&& __e) const + noexcept(noexcept(_End{}(__cust_access::__as_const((_Tp&&)__e)))) + requires requires { _End{}(__cust_access::__as_const((_Tp&&)__e)); } + { + return _End{}(__cust_access::__as_const(std::forward<_Tp>(__e))); + } + }; + + template + concept __member_rbegin = requires(_Tp& __t) + { + { __decay_copy(__t.rbegin()) } -> input_or_output_iterator; + }; + + void rbegin(auto&) = delete; + void rbegin(const auto&) = delete; + + template + concept __adl_rbegin = __class_or_enum> + && requires(_Tp& __t) + { + { __decay_copy(rbegin(__t)) } -> input_or_output_iterator; + }; + + template + concept __reversable = requires(_Tp& __t) + { + { _Begin{}(__t) } -> bidirectional_iterator; + { _End{}(__t) } -> same_as; + }; + + struct _RBegin + { + private: + template + static constexpr bool + _S_noexcept() + { + if constexpr (__member_rbegin<_Tp>) + return noexcept(__decay_copy(std::declval<_Tp&>().rbegin())); + else if constexpr (__adl_rbegin<_Tp>) + return noexcept(__decay_copy(rbegin(std::declval<_Tp&>()))); + else + { + if constexpr (noexcept(_End{}(std::declval<_Tp&>()))) + { + using _It = decltype(_End{}(std::declval<_Tp&>())); + // std::reverse_iterator copy-initializes its member. + return is_nothrow_copy_constructible_v<_It>; + } + else + return false; + } + } + + public: + template<__maybe_borrowed_range _Tp> + requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp> + constexpr auto + operator()(_Tp&& __t) const + noexcept(_S_noexcept<_Tp>()) + { + if constexpr (__member_rbegin<_Tp>) + return __t.rbegin(); + else if constexpr (__adl_rbegin<_Tp>) + return rbegin(__t); + else + return std::make_reverse_iterator(_End{}(__t)); + } + }; + + template + concept __member_rend = requires(_Tp& __t) + { + { __decay_copy(__t.rend()) } + -> sentinel_for; + }; + + void rend(auto&) = delete; + void rend(const auto&) = delete; + + template + concept __adl_rend = __class_or_enum> + && requires(_Tp& __t) + { + { __decay_copy(rend(__t)) } + -> sentinel_for(__t)))>; + }; + + struct _REnd + { + private: + template + static constexpr bool + _S_noexcept() + { + if constexpr (__member_rend<_Tp>) + return noexcept(__decay_copy(std::declval<_Tp&>().rend())); + else if constexpr (__adl_rend<_Tp>) + return noexcept(__decay_copy(rend(std::declval<_Tp&>()))); + else + { + if constexpr (noexcept(_Begin{}(std::declval<_Tp&>()))) + { + using _It = decltype(_Begin{}(std::declval<_Tp&>())); + // std::reverse_iterator copy-initializes its member. + return is_nothrow_copy_constructible_v<_It>; + } + else + return false; + } + } + + public: + template<__maybe_borrowed_range _Tp> + requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp> + constexpr auto + operator()(_Tp&& __t) const + noexcept(_S_noexcept<_Tp>()) + { + if constexpr (__member_rend<_Tp>) + return __t.rend(); + else if constexpr (__adl_rend<_Tp>) + return rend(__t); + else + return std::make_reverse_iterator(_Begin{}(__t)); + } + }; + + struct _CRBegin + { + template + constexpr auto + operator()(_Tp&& __e) const + noexcept(noexcept(_RBegin{}(__cust_access::__as_const((_Tp&&)__e)))) + requires requires { _RBegin{}(__cust_access::__as_const((_Tp&&)__e)); } + { + return _RBegin{}(__cust_access::__as_const(std::forward<_Tp>(__e))); + } + }; + + struct _CREnd + { + template + constexpr auto + operator()(_Tp&& __e) const + noexcept(noexcept(_REnd{}(__cust_access::__as_const((_Tp&&)__e)))) + requires requires { _REnd{}(__cust_access::__as_const((_Tp&&)__e)); } + { + return _REnd{}(__cust_access::__as_const(std::forward<_Tp>(__e))); + } + }; + + template + concept __member_size = !disable_sized_range> + && requires(_Tp&& __t) + { + { __decay_copy(std::forward<_Tp>(__t).size()) } + -> __detail::__is_integer_like; + }; + + void size(auto&) = delete; + void size(const auto&) = delete; + + template + concept __adl_size = __class_or_enum> + && !disable_sized_range> + && requires(_Tp&& __t) + { + { __decay_copy(size(std::forward<_Tp>(__t))) } + -> __detail::__is_integer_like; + }; + + template + concept __sentinel_size = requires(_Tp&& __t) + { + { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator; + + { _End{}(std::forward<_Tp>(__t)) } + -> sized_sentinel_for(__t)))>; + }; + + struct _Size + { + private: + template + static constexpr bool + _S_noexcept() + { + if constexpr (is_bounded_array_v>) + return true; + else if constexpr (__member_size<_Tp>) + return noexcept(__decay_copy(std::declval<_Tp>().size())); + else if constexpr (__adl_size<_Tp>) + return noexcept(__decay_copy(size(std::declval<_Tp>()))); + else if constexpr (__sentinel_size<_Tp>) + return noexcept(_End{}(std::declval<_Tp>()) + - _Begin{}(std::declval<_Tp>())); + } + + public: + template + requires is_bounded_array_v> + || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp> + constexpr auto + operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>()) + { + if constexpr (is_bounded_array_v>) + { + return extent_v>; + } + else if constexpr (__member_size<_Tp>) + return std::forward<_Tp>(__e).size(); + else if constexpr (__adl_size<_Tp>) + return size(std::forward<_Tp>(__e)); + else if constexpr (__sentinel_size<_Tp>) + return __detail::__to_unsigned_like( + _End{}(std::forward<_Tp>(__e)) + - _Begin{}(std::forward<_Tp>(__e))); + } + }; + + struct _SSize + { + template + requires requires (_Tp&& __e) + { + _Begin{}(std::forward<_Tp>(__e)); + _Size{}(std::forward<_Tp>(__e)); + } + constexpr auto + operator()(_Tp&& __e) const + noexcept(noexcept(_Size{}(std::forward<_Tp>(__e)))) + { + using __iter_type = decltype(_Begin{}(std::forward<_Tp>(__e))); + using __diff_type = iter_difference_t<__iter_type>; + using __gnu_cxx::__int_traits; + auto __size = _Size{}(std::forward<_Tp>(__e)); + if constexpr (integral<__diff_type>) + { + if constexpr (__int_traits<__diff_type>::__digits + < __int_traits::__digits) + return static_cast(__size); + } + return static_cast<__diff_type>(__size); + } + }; + + template + concept __member_empty = requires(_Tp&& __t) + { bool(std::forward<_Tp>(__t).empty()); }; + + template + concept __size0_empty = requires(_Tp&& __t) + { _Size{}(std::forward<_Tp>(__t)) == 0; }; + + template + concept __eq_iter_empty = requires(_Tp&& __t) + { + { _Begin{}(std::forward<_Tp>(__t)) } -> forward_iterator; + bool(_Begin{}(std::forward<_Tp>(__t)) + == _End{}(std::forward<_Tp>(__t))); + }; + + struct _Empty + { + private: + template + static constexpr bool + _S_noexcept() + { + if constexpr (__member_empty<_Tp>) + return noexcept(std::declval<_Tp>().empty()); + else if constexpr (__size0_empty<_Tp>) + return noexcept(_Size{}(std::declval<_Tp>()) == 0); + else + return noexcept(bool(_Begin{}(std::declval<_Tp>()) + == _End{}(std::declval<_Tp>()))); + } + + public: + template + requires __member_empty<_Tp> || __size0_empty<_Tp> + || __eq_iter_empty<_Tp> + constexpr bool + operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>()) + { + if constexpr (__member_empty<_Tp>) + return bool(std::forward<_Tp>(__e).empty()); + else if constexpr (__size0_empty<_Tp>) + return _Size{}(std::forward<_Tp>(__e)) == 0; + else + return bool(_Begin{}(std::forward<_Tp>(__e)) + == _End{}(std::forward<_Tp>(__e))); + } + }; + + template + concept __pointer_to_object = is_pointer_v<_Tp> + && is_object_v>; + + template + concept __member_data = is_lvalue_reference_v<_Tp> + && requires(_Tp __t) { { __t.data() } -> __pointer_to_object; }; + + template + concept __begin_data = requires(_Tp&& __t) + { { _Begin{}(std::forward<_Tp>(__t)) } -> contiguous_iterator; }; + + struct _Data + { + private: + template + static constexpr bool + _S_noexcept() + { + if constexpr (__member_data<_Tp>) + return noexcept(__decay_copy(std::declval<_Tp>().data())); + else + return noexcept(_Begin{}(std::declval<_Tp>())); + } + + public: + template<__maybe_borrowed_range _Tp> + requires __member_data<_Tp> || __begin_data<_Tp> + constexpr auto + operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>()) + { + if constexpr (__member_data<_Tp>) + return __e.data(); + else + return std::to_address(_Begin{}(std::forward<_Tp>(__e))); + } + }; + + struct _CData + { + template + constexpr auto + operator()(_Tp&& __e) const + noexcept(noexcept(_Data{}(__cust_access::__as_const((_Tp&&)__e)))) + requires requires { _Data{}(__cust_access::__as_const((_Tp&&)__e)); } + { + return _Data{}(__cust_access::__as_const(std::forward<_Tp>(__e))); + } + }; + + } // namespace __cust_access + + inline namespace __cust + { + inline constexpr __cust_access::_Begin begin{}; + inline constexpr __cust_access::_End end{}; + inline constexpr __cust_access::_CBegin cbegin{}; + inline constexpr __cust_access::_CEnd cend{}; + inline constexpr __cust_access::_RBegin rbegin{}; + inline constexpr __cust_access::_REnd rend{}; + inline constexpr __cust_access::_CRBegin crbegin{}; + inline constexpr __cust_access::_CREnd crend{}; + inline constexpr __cust_access::_Size size{}; + inline constexpr __cust_access::_SSize ssize{}; + inline constexpr __cust_access::_Empty empty{}; + inline constexpr __cust_access::_Data data{}; + inline constexpr __cust_access::_CData cdata{}; + } + + /// [range.range] The range concept. + template + concept range = requires(_Tp& __t) + { + ranges::begin(__t); + ranges::end(__t); + }; + + /// [range.range] The borrowed_range concept. + template + concept borrowed_range + = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>; + + template + using iterator_t = std::__detail::__range_iter_t<_Tp>; + + template + using sentinel_t = decltype(ranges::end(std::declval<_Range&>())); + + template + using range_difference_t = iter_difference_t>; + + template + using range_value_t = iter_value_t>; + + template + using range_reference_t = iter_reference_t>; + + template + using range_rvalue_reference_t + = iter_rvalue_reference_t>; + + /// [range.sized] The sized_range concept. + template + concept sized_range = range<_Tp> + && requires(_Tp& __t) { ranges::size(__t); }; + + template + using range_size_t = decltype(ranges::size(std::declval<_Range&>())); + + /// [range.view] The ranges::view_base type. + struct view_base { }; + + /// [range.view] The ranges::enable_view boolean. + template + inline constexpr bool enable_view = derived_from<_Tp, view_base>; + + /// [range.view] The ranges::view concept. + template + concept view + = range<_Tp> && movable<_Tp> && default_initializable<_Tp> + && enable_view<_Tp>; + + // [range.refinements] + + /// A range for which ranges::begin returns an output iterator. + template + concept output_range + = range<_Range> && output_iterator, _Tp>; + + /// A range for which ranges::begin returns an input iterator. + template + concept input_range = range<_Tp> && input_iterator>; + + /// A range for which ranges::begin returns a forward iterator. + template + concept forward_range + = input_range<_Tp> && forward_iterator>; + + /// A range for which ranges::begin returns a bidirectional iterator. + template + concept bidirectional_range + = forward_range<_Tp> && bidirectional_iterator>; + + /// A range for which ranges::begin returns a random access iterator. + template + concept random_access_range + = bidirectional_range<_Tp> && random_access_iterator>; + + /// A range for which ranges::begin returns a contiguous iterator. + template + concept contiguous_range + = random_access_range<_Tp> && contiguous_iterator> + && requires(_Tp& __t) + { + { ranges::data(__t) } -> same_as>>; + }; + + /// A range for which ranges::begin and ranges::end return the same type. + template + concept common_range + = range<_Tp> && same_as, sentinel_t<_Tp>>; + + /// A range which can be safely converted to a view. + template + concept viewable_range = range<_Tp> + && (borrowed_range<_Tp> || view>); + + // [range.iter.ops] range iterator operations + + template + constexpr void + advance(_It& __it, iter_difference_t<_It> __n) + { + if constexpr (random_access_iterator<_It>) + __it += __n; + else if constexpr (bidirectional_iterator<_It>) + { + if (__n > 0) + { + do + { + ++__it; + } + while (--__n); + } + else if (__n < 0) + { + do + { + --__it; + } + while (++__n); + } + } + else + { + // cannot decrement a non-bidirectional iterator + __glibcxx_assert(__n >= 0); + while (__n-- > 0) + ++__it; + } + } + + template _Sent> + constexpr void + advance(_It& __it, _Sent __bound) + { + if constexpr (assignable_from<_It&, _Sent>) + __it = std::move(__bound); + else if constexpr (sized_sentinel_for<_Sent, _It>) + ranges::advance(__it, __bound - __it); + else + { + while (__it != __bound) + ++__it; + } + } + + template _Sent> + constexpr iter_difference_t<_It> + advance(_It& __it, iter_difference_t<_It> __n, _Sent __bound) + { + if constexpr (sized_sentinel_for<_Sent, _It>) + { + const auto __diff = __bound - __it; +#ifdef __cpp_lib_is_constant_evaluated + if (std::is_constant_evaluated() + && !(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0))) + throw "inconsistent directions for distance and bound"; +#endif + // n and bound must not lead in opposite directions: + __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0)); + const auto __absdiff = __diff < 0 ? -__diff : __diff; + const auto __absn = __n < 0 ? -__n : __n;; + if (__absn >= __absdiff) + { + ranges::advance(__it, __bound); + return __n - __diff; + } + else + { + ranges::advance(__it, __n); + return 0; + } + } + else if (__it == __bound || __n == 0) + return iter_difference_t<_It>(0); + else if (__n > 0) + { + iter_difference_t<_It> __m = 0; + do + { + ++__it; + ++__m; + } + while (__m != __n && __it != __bound); + return __n - __m; + } + else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>) + { + iter_difference_t<_It> __m = 0; + do + { + --__it; + --__m; + } + while (__m != __n && __it != __bound); + return __n - __m; + } + else + { + // cannot decrement a non-bidirectional iterator + __glibcxx_assert(__n >= 0); + return __n; + } + } + + template _Sent> + constexpr iter_difference_t<_It> + distance(_It __first, _Sent __last) + { + if constexpr (sized_sentinel_for<_Sent, _It>) + return __last - __first; + else + { + iter_difference_t<_It> __n = 0; + while (__first != __last) + { + ++__first; + ++__n; + } + return __n; + } + } + + template + constexpr range_difference_t<_Range> + distance(_Range&& __r) + { + if constexpr (sized_range<_Range>) + return static_cast>(ranges::size(__r)); + else + return ranges::distance(ranges::begin(__r), ranges::end(__r)); + } + + template + constexpr _It + next(_It __x) + { + ++__x; + return __x; + } + + template + constexpr _It + next(_It __x, iter_difference_t<_It> __n) + { + ranges::advance(__x, __n); + return __x; + } + + template _Sent> + constexpr _It + next(_It __x, _Sent __bound) + { + ranges::advance(__x, __bound); + return __x; + } + + template _Sent> + constexpr _It + next(_It __x, iter_difference_t<_It> __n, _Sent __bound) + { + ranges::advance(__x, __n, __bound); + return __x; + } + + template + constexpr _It + prev(_It __x) + { + --__x; + return __x; + } + + template + constexpr _It + prev(_It __x, iter_difference_t<_It> __n) + { + ranges::advance(__x, -__n); + return __x; + } + + template + constexpr _It + prev(_It __x, iter_difference_t<_It> __n, _It __bound) + { + ranges::advance(__x, -__n, __bound); + return __x; + } + + /// Type returned by algorithms instead of a dangling iterator or subrange. + struct dangling + { + constexpr dangling() noexcept = default; + template + constexpr dangling(_Args&&...) noexcept { } + }; + + template + using borrowed_iterator_t = conditional_t, + iterator_t<_Range>, + dangling>; + +} // namespace ranges +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std +#endif // library concepts +#endif // C++20 +#endif // _GLIBCXX_RANGES_BASE_H diff --git a/libstdc++-v3/include/bits/range_cmp.h b/libstdc++-v3/include/bits/ranges_cmp.h similarity index 98% rename from libstdc++-v3/include/bits/range_cmp.h rename to libstdc++-v3/include/bits/ranges_cmp.h index 0587c599c4b..a48f950f5ab 100644 --- a/libstdc++-v3/include/bits/range_cmp.h +++ b/libstdc++-v3/include/bits/ranges_cmp.h @@ -22,13 +22,13 @@ // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see // . -/** @file bits/range_cmp.h +/** @file bits/ranges_cmp.h * This is an internal header file, included by other library headers. * Do not attempt to use it directly. @headername{functional} */ -#ifndef _RANGE_CMP_H -#define _RANGE_CMP_H 1 +#ifndef _RANGES_CMP_H +#define _RANGES_CMP_H 1 #if __cplusplus > 201703L # include @@ -192,4 +192,4 @@ namespace ranges _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // C++20 -#endif // _RANGE_CMP_H +#endif // _RANGES_CMP_H diff --git a/libstdc++-v3/include/bits/ranges_util.h b/libstdc++-v3/include/bits/ranges_util.h new file mode 100644 index 00000000000..694ae796399 --- /dev/null +++ b/libstdc++-v3/include/bits/ranges_util.h @@ -0,0 +1,417 @@ +// Utilities for representing and manipulating ranges -*- C++ -*- + +// Copyright (C) 2019-2020 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file bits/ranges_util.h + * This is an internal header file, included by other library headers. + * Do not attempt to use it directly. @headername{ranges} + */ + +#ifndef _RANGES_UTIL_H +#define _RANGES_UTIL_H 1 + +#if __cplusplus > 201703L +# include + +#ifdef __cpp_lib_ranges +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION +namespace ranges +{ + // C++20 24.5 [range.utility] Range utilities + + 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 + + /// The ranges::view_interface class template + 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 __convertible_to_non_slicing = convertible_to<_From, _To> + && !(is_pointer_v> && is_pointer_v> + && __not_same_as>, + remove_pointer_t>>); + + 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_from + = !range<_Tp> && __pair_like<_Tp> + && constructible_from<_Tp, _Up, _Vp> + && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>> + && convertible_to<_Vp, tuple_element_t<1, _Tp>>; + + template + concept __iterator_sentinel_pair + = !range<_Tp> && __pair_like<_Tp> + && sentinel_for, tuple_element_t<0, _Tp>>; + + } // namespace __detail + + enum class subrange_kind : bool { unsized, sized }; + + /// The ranges::subrange class template + 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: + // XXX: gcc complains when using constexpr here + static const 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(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s) + requires (!_S_store_size) + : _M_begin(std::move(__i)), _M_end(__s) + { } + + constexpr + subrange(__detail::__convertible_to_non_slicing<_It> auto __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 borrowed_range<_Rng> + && __detail::__convertible_to_non_slicing, _It> + && convertible_to, _Sent> + constexpr + subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng> + : subrange{__r, ranges::size(__r)} + { } + + template<__detail::__not_same_as _Rng> + requires borrowed_range<_Rng> + && __detail::__convertible_to_non_slicing, _It> + && convertible_to, _Sent> + constexpr + subrange(_Rng&& __r) requires (!_S_store_size) + : subrange{ranges::begin(__r), ranges::end(__r)} + { } + + template + requires __detail::__convertible_to_non_slicing, _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_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) + { + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 3433. subrange::advance(n) has UB when n < 0 + if constexpr (bidirectional_iterator<_It>) + if (__n < 0) + { + ranges::advance(_M_begin, __n); + if constexpr (_S_store_size) + _M_size._M_size += __detail::__to_unsigned_like(-__n); + return *this; + } + + __glibcxx_assert(__n >= 0); + auto __d = __n - ranges::advance(_M_begin, __n, _M_end); + if constexpr (_S_store_size) + _M_size._M_size -= __detail::__to_unsigned_like(__d); + return *this; + } + }; + + template _Sent> + subrange(_It, _Sent) -> subrange<_It, _Sent>; + + 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 + subrange(_Rng&&) + -> subrange, sentinel_t<_Rng>, + (sized_range<_Rng> + || sized_sentinel_for, iterator_t<_Rng>>) + ? subrange_kind::sized : subrange_kind::unsized>; + + template + 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(); + } + + template _Sent, + subrange_kind _Kind> + inline constexpr bool + enable_borrowed_range> = true; + + template + using borrowed_subrange_t = conditional_t, + subrange>, + dangling>; + +} // namespace ranges + + using ranges::get; + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std +#endif // library concepts +#endif // C++20 +#endif // _RANGES_UTIL_H diff --git a/libstdc++-v3/include/experimental/string_view b/libstdc++-v3/include/experimental/string_view index 5567184cf0e..1d6399acbed 100644 --- a/libstdc++-v3/include/experimental/string_view +++ b/libstdc++-v3/include/experimental/string_view @@ -40,6 +40,7 @@ #include #include +#include // enable_borrowed_range, enable_view #include namespace std _GLIBCXX_VISIBILITY(default) diff --git a/libstdc++-v3/include/std/functional b/libstdc++-v3/include/std/functional index 407b93f3eb7..9bad692f2ad 100644 --- a/libstdc++-v3/include/std/functional +++ b/libstdc++-v3/include/std/functional @@ -65,7 +65,7 @@ # include #endif #if __cplusplus > 201703L -# include +# include # include #endif diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 1bf894dd570..e7fa4493612 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -38,12 +38,13 @@ #if __cpp_lib_concepts -#include #include #include #include #include #include +#include +#include /** * @defgroup ranges Ranges @@ -56,410 +57,18 @@ namespace std _GLIBCXX_VISIBILITY(default) _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace ranges { - // [range.range] The range concept. - // [range.sized] The sized_range concept. - // Defined in - - // [range.refinements] - // Defined in - - struct view_base { }; - - template - inline constexpr bool enable_view = derived_from<_Tp, view_base>; - - template - concept view - = range<_Tp> && movable<_Tp> && default_initializable<_Tp> - && enable_view<_Tp>; - - /// A range which can be safely converted to a view. - template - concept viewable_range = range<_Tp> - && (borrowed_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 __convertible_to_non_slicing = convertible_to<_From, _To> - && !(is_pointer_v> && is_pointer_v> - && __not_same_as>, - remove_pointer_t>>); - - 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_from - = !range<_Tp> && __pair_like<_Tp> - && constructible_from<_Tp, _Up, _Vp> - && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>> - && convertible_to<_Vp, tuple_element_t<1, _Tp>>; - - template - concept __iterator_sentinel_pair - = !range<_Tp> && __pair_like<_Tp> - && sentinel_for, tuple_element_t<0, _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: - // XXX: gcc complains when using constexpr here - static const 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(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s) - requires (!_S_store_size) - : _M_begin(std::move(__i)), _M_end(__s) - { } - - constexpr - subrange(__detail::__convertible_to_non_slicing<_It> auto __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 borrowed_range<_Rng> - && __detail::__convertible_to_non_slicing, _It> - && convertible_to, _Sent> - constexpr - subrange(_Rng&& __r) requires _S_store_size && sized_range<_Rng> - : subrange{__r, ranges::size(__r)} - { } - - template<__detail::__not_same_as _Rng> - requires borrowed_range<_Rng> - && __detail::__convertible_to_non_slicing, _It> - && convertible_to, _Sent> - constexpr - subrange(_Rng&& __r) requires (!_S_store_size) - : subrange{ranges::begin(__r), ranges::end(__r)} - { } - - template - requires __detail::__convertible_to_non_slicing, _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_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) - { - // _GLIBCXX_RESOLVE_LIB_DEFECTS - // 3433. subrange::advance(n) has UB when n < 0 - if constexpr (bidirectional_iterator<_It>) - if (__n < 0) - { - ranges::advance(_M_begin, __n); - if constexpr (_S_store_size) - _M_size._M_size += __detail::__to_unsigned_like(-__n); - return *this; - } - - __glibcxx_assert(__n >= 0); - auto __d = __n - ranges::advance(_M_begin, __n, _M_end); - if constexpr (_S_store_size) - _M_size._M_size -= __detail::__to_unsigned_like(__d); - return *this; - } - }; - - template _Sent> - subrange(_It, _Sent) -> subrange<_It, _Sent>; - - 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 - subrange(_Rng&&) - -> subrange, sentinel_t<_Rng>, - (sized_range<_Rng> - || sized_sentinel_for, iterator_t<_Rng>>) - ? subrange_kind::sized : subrange_kind::unsized>; - - template - 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(); - } - - template _Sent, - subrange_kind _Kind> - inline constexpr bool - enable_borrowed_range> = true; - -} // 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 { } - }; + // [range.access] customization point objects + // [range.req] range and view concepts + // [range.dangling] dangling iterator handling + // Defined in - template - using borrowed_iterator_t = conditional_t, - iterator_t<_Range>, - dangling>; + // [view.interface] View interface + // [range.subrange] Sub-ranges + // Defined in - template - using borrowed_subrange_t = conditional_t, - subrange>, - dangling>; + // C++20 24.6 [range.factories] Range factories + /// A view that contains no elements. template requires is_object_v<_Tp> class empty_view : public view_interface> @@ -1038,6 +647,8 @@ namespace views istream_view(basic_istream<_CharT, _Traits>& __s) { return basic_istream_view<_Val, _CharT, _Traits>{__s}; } + // C++20 24.7 [range.adaptors] Range adaptors + namespace __detail { struct _Empty { }; diff --git a/libstdc++-v3/include/std/span b/libstdc++-v3/include/std/span index 1cdc0589ddb..fb349403c9e 100644 --- a/libstdc++-v3/include/std/span +++ b/libstdc++-v3/include/std/span @@ -41,7 +41,7 @@ #include #include #include -#include +#include #if __cpp_lib_concepts namespace std _GLIBCXX_VISIBILITY(default) diff --git a/libstdc++-v3/include/std/string_view b/libstdc++-v3/include/std/string_view index f05ff32d9e5..32c51b2bbd4 100644 --- a/libstdc++-v3/include/std/string_view +++ b/libstdc++-v3/include/std/string_view @@ -41,6 +41,7 @@ #include #include #include +#include #include #include diff --git a/libstdc++-v3/testsuite/24_iterators/back_insert_iterator/pr93884.cc b/libstdc++-v3/testsuite/24_iterators/back_insert_iterator/pr93884.cc index 5a6287ddd40..b620be8cb98 100644 --- a/libstdc++-v3/testsuite/24_iterators/back_insert_iterator/pr93884.cc +++ b/libstdc++-v3/testsuite/24_iterators/back_insert_iterator/pr93884.cc @@ -21,6 +21,7 @@ #include #include #include +#include #include namespace ranges = std::ranges; diff --git a/libstdc++-v3/testsuite/24_iterators/front_insert_iterator/pr93884.cc b/libstdc++-v3/testsuite/24_iterators/front_insert_iterator/pr93884.cc index eaf4e9a187f..0f6e9f57ebf 100644 --- a/libstdc++-v3/testsuite/24_iterators/front_insert_iterator/pr93884.cc +++ b/libstdc++-v3/testsuite/24_iterators/front_insert_iterator/pr93884.cc @@ -21,6 +21,7 @@ #include #include #include +#include #include namespace ranges = std::ranges; -- 2.30.2