From b5b2e3879db9a251a2e7ff2553e188682d202c7e Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Mon, 9 Dec 2019 17:35:24 +0000 Subject: libstdc++: Implement ranges::safe_range for C++20 (P1870R1) This change replaces the __forwarding_range implementation detail with the ranges::safe_range concept and adds the ranges::enable_safe_range variable template for opt-in in to the concept. It also adjusts the begin/end/rbegin/rend customization point objects to match the new rules for accessing rvalue ranges only when safe to do so. * include/bits/range_access.h (ranges::enable_safe_range): Define. (ranges::begin, ranges::end, ranges::rbegin, ranges::rend): Constrain to only accept types satisfying safe_range and treat argument as an lvalue when calling a member of performing ADL. (ranges::__detail::__range_impl, ranges::__detail::__forwarding_range): Remove. (ranges::range): Adjust definition. (ranges::safe_range): Define. (ranges::iterator_t, ranges::range_difference_t): Reorder definitions to match the synopsis in the working draft. (ranges::disable_sized_range): Remove duplicate definition. * include/experimental/string_view (ranges::enable_safe_range): Add partial specialization for std::experimental::basic_string_view. * include/std/ranges (ranges::viewable_range, ranges::subrange) (ranges::empty_view, ranges::iota_view): Use safe_range. Specialize enable_safe_range. (ranges::safe_iterator_t, ranges::safe_subrange_t): Define. * include/std/span (ranges::enable_safe_range): Add partial specialization for std::span. * include/std/string_view (ranges::enable_safe_range): Likewise for std::basic_string_view. * testsuite/std/ranges/access/begin.cc: Adjust expected results. * testsuite/std/ranges/access/cbegin.cc: Likewise. * testsuite/std/ranges/access/cdata.cc: Likewise. * testsuite/std/ranges/access/cend.cc: Likewise. * testsuite/std/ranges/access/crbegin.cc: Likewise. * testsuite/std/ranges/access/crend.cc: Likewise. * testsuite/std/ranges/access/data.cc: Likewise. * testsuite/std/ranges/access/end.cc: Likewise. * testsuite/std/ranges/access/rbegin.cc: Likewise. * testsuite/std/ranges/access/rend.cc: Likewise. * testsuite/std/ranges/empty_view.cc: Test ranges::begin and ranges::end instead of unqualified calls to begin and end. * testsuite/std/ranges/safe_range.cc: New test. * testsuite/std/ranges/safe_range_types.cc: New test. * testsuite/util/testsuite_iterators.h: Add comment about safe_range. From-SVN: r279135 --- libstdc++-v3/include/bits/range_access.h | 183 +++++++++++++------------- libstdc++-v3/include/experimental/string_view | 12 ++ libstdc++-v3/include/std/ranges | 45 ++++--- libstdc++-v3/include/std/span | 18 ++- libstdc++-v3/include/std/string_view | 10 ++ 5 files changed, 152 insertions(+), 116 deletions(-) (limited to 'libstdc++-v3/include') diff --git a/libstdc++-v3/include/bits/range_access.h b/libstdc++-v3/include/bits/range_access.h index c94e965..6ebd667 100644 --- a/libstdc++-v3/include/bits/range_access.h +++ b/libstdc++-v3/include/bits/range_access.h @@ -342,6 +342,9 @@ namespace ranges template inline constexpr bool disable_sized_range = false; + template + inline constexpr bool enable_safe_range = false; + namespace __detail { using __max_diff_type = long long; @@ -359,10 +362,19 @@ namespace ranges constexpr make_unsigned_t<_Tp> __to_unsigned_like(_Tp __t) noexcept { return __t; } + + // Part of the constraints of ranges::safe_range + template + concept __maybe_safe_range + = is_lvalue_reference_v<_Tp> || enable_safe_range>; + } // namespace __detail namespace __cust_access { + using std::ranges::__detail::__maybe_safe_range; + using std::__detail::__class_or_enum; + template constexpr decay_t<_Tp> __decay_copy(_Tp&& __t) @@ -370,20 +382,19 @@ namespace ranges { return std::forward<_Tp>(__t); } template - concept __member_begin = is_lvalue_reference_v<_Tp> - && requires(_Tp __t) - { { __decay_copy(__t.begin()) } -> input_or_output_iterator; }; + concept __member_begin = requires(_Tp& __t) + { + { __decay_copy(__t.begin()) } -> input_or_output_iterator; + }; template void begin(_Tp&&) = delete; template void begin(initializer_list<_Tp>&&) = delete; template - concept __adl_begin - = std::__detail::__class_or_enum> - && requires(_Tp&& __t) + concept __adl_begin = __class_or_enum> + && requires(_Tp& __t) { - { __decay_copy(begin(std::forward<_Tp>(__t))) } - -> input_or_output_iterator; + { __decay_copy(begin(__t)) } -> input_or_output_iterator; }; struct _Begin @@ -396,47 +407,45 @@ namespace ranges if constexpr (is_array_v>) return true; else if constexpr (__member_begin<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp>().begin())); + return noexcept(__decay_copy(std::declval<_Tp&>().begin())); else - return noexcept(__decay_copy(begin(std::declval<_Tp>()))); + return noexcept(__decay_copy(begin(std::declval<_Tp&>()))); } public: - template + template<__maybe_safe_range _Tp> requires is_array_v> || __member_begin<_Tp> || __adl_begin<_Tp> constexpr auto - operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>()) + operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) { if constexpr (is_array_v>) { static_assert(is_lvalue_reference_v<_Tp>); - return __e; + return __t; } else if constexpr (__member_begin<_Tp>) - return __e.begin(); + return __t.begin(); else - return begin(std::forward<_Tp>(__e)); + return begin(__t); } }; template - concept __member_end = is_lvalue_reference_v<_Tp> - && requires(_Tp __t) + concept __member_end = requires(_Tp& __t) { { __decay_copy(__t.end()) } - -> sentinel_for; + -> sentinel_for(__t)))>; }; template void end(_Tp&&) = delete; template void end(initializer_list<_Tp>&&) = delete; template - concept __adl_end - = std::__detail::__class_or_enum> - && requires(_Tp&& __t) + concept __adl_end = __class_or_enum> + && requires(_Tp& __t) { - { __decay_copy(end(std::forward<_Tp>(__t))) } + { __decay_copy(end(__t)) } -> sentinel_for(__t)))>; }; @@ -450,28 +459,28 @@ namespace ranges if constexpr (is_array_v>) return true; else if constexpr (__member_end<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp>().end())); + return noexcept(__decay_copy(std::declval<_Tp&>().end())); else - return noexcept(__decay_copy(end(std::declval<_Tp>()))); + return noexcept(__decay_copy(end(std::declval<_Tp&>()))); } public: - template + template<__maybe_safe_range _Tp> requires is_array_v> || __member_end<_Tp> || __adl_end<_Tp> constexpr auto - operator()(_Tp&& __e) const noexcept(_S_noexcept<_Tp>()) + operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) { if constexpr (is_array_v>) { static_assert(is_lvalue_reference_v<_Tp>); static_assert(is_bounded_array_v>); - return __e + extent_v>; + return __t + extent_v>; } else if constexpr (__member_end<_Tp>) - return __e.end(); + return __t.end(); else - return end(std::forward<_Tp>(__e)); + return end(__t); } }; @@ -510,27 +519,25 @@ namespace ranges }; template - concept __member_rbegin = is_lvalue_reference_v<_Tp> - && requires(_Tp __t) - { { __decay_copy(__t.rbegin()) } -> input_or_output_iterator; }; + concept __member_rbegin = requires(_Tp& __t) + { + { __decay_copy(__t.rbegin()) } -> input_or_output_iterator; + }; template void rbegin(_Tp&&) = delete; template - concept __adl_rbegin - = std::__detail::__class_or_enum> - && requires(_Tp&& __t) + concept __adl_rbegin = __class_or_enum> + && requires(_Tp& __t) { - { __decay_copy(rbegin(std::forward<_Tp>(__t))) } - -> input_or_output_iterator; + { __decay_copy(rbegin(__t)) } -> input_or_output_iterator; }; template - concept __reversable = requires(_Tp&& __t) + concept __reversable = requires(_Tp& __t) { - { _Begin{}(std::forward<_Tp>(__t)) } -> bidirectional_iterator; - { _End{}(std::forward<_Tp>(__t)) } - -> same_as(__t)))>; + { _Begin{}(__t) } -> bidirectional_iterator; + { _End{}(__t) } -> same_as; }; struct _RBegin @@ -541,14 +548,14 @@ namespace ranges _S_noexcept() { if constexpr (__member_rbegin<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp>().rbegin())); + return noexcept(__decay_copy(std::declval<_Tp&>().rbegin())); else if constexpr (__adl_rbegin<_Tp>) - return noexcept(__decay_copy(rbegin(std::declval<_Tp>()))); + return noexcept(__decay_copy(rbegin(std::declval<_Tp&>()))); else { - if constexpr (noexcept(_End{}(std::declval<_Tp>()))) + if constexpr (noexcept(_End{}(std::declval<_Tp&>()))) { - using _It = decltype(_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>; } @@ -558,24 +565,23 @@ namespace ranges } public: - template + template<__maybe_safe_range _Tp> requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp> constexpr auto - operator()(_Tp&& __e) const + operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) { if constexpr (__member_rbegin<_Tp>) - return __e.rbegin(); + return __t.rbegin(); else if constexpr (__adl_rbegin<_Tp>) - return rbegin(std::forward<_Tp>(__e)); + return rbegin(__t); else - return std::make_reverse_iterator(_End{}(std::forward<_Tp>(__e))); + return std::make_reverse_iterator(_End{}(__t)); } }; template - concept __member_rend = is_lvalue_reference_v<_Tp> - && requires(_Tp __t) + concept __member_rend = requires(_Tp& __t) { { __decay_copy(__t.rend()) } -> sentinel_for; @@ -584,11 +590,10 @@ namespace ranges template void rend(_Tp&&) = delete; template - concept __adl_rend - = std::__detail::__class_or_enum> - && requires(_Tp&& __t) + concept __adl_rend = __class_or_enum> + && requires(_Tp& __t) { - { __decay_copy(rend(std::forward<_Tp>(__t))) } + { __decay_copy(rend(__t)) } -> sentinel_for(__t)))>; }; @@ -600,14 +605,14 @@ namespace ranges _S_noexcept() { if constexpr (__member_rend<_Tp>) - return noexcept(__decay_copy(std::declval<_Tp>().rend())); + return noexcept(__decay_copy(std::declval<_Tp&>().rend())); else if constexpr (__adl_rend<_Tp>) - return noexcept(__decay_copy(rend(std::declval<_Tp>()))); + return noexcept(__decay_copy(rend(std::declval<_Tp&>()))); else { - if constexpr (noexcept(_Begin{}(std::declval<_Tp>()))) + if constexpr (noexcept(_Begin{}(std::declval<_Tp&>()))) { - using _It = decltype(_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>; } @@ -617,18 +622,18 @@ namespace ranges } public: - template + template<__maybe_safe_range _Tp> requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp> constexpr auto - operator()(_Tp&& __e) const + operator()(_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) { if constexpr (__member_rend<_Tp>) - return __e.rend(); + return __t.rend(); else if constexpr (__adl_rend<_Tp>) - return rend(std::forward<_Tp>(__e)); + return rend(__t); else - return std::make_reverse_iterator(_Begin{}(std::forward<_Tp>(__e))); + return std::make_reverse_iterator(_Begin{}(__t)); } }; @@ -667,8 +672,7 @@ namespace ranges template void size(_Tp&&) = delete; template - concept __adl_size - = std::__detail::__class_or_enum> + concept __adl_size = __class_or_enum> && !disable_sized_range> && requires(_Tp&& __t) { @@ -842,25 +846,26 @@ namespace ranges inline constexpr __cust_access::_CData cdata{}; } - namespace __detail - { - template - concept __range_impl = requires(_Tp&& __t) { - ranges::begin(std::forward<_Tp>(__t)); - ranges::end(std::forward<_Tp>(__t)); + /// [range.range] The range concept. + template + concept range = requires(_Tp& __t) + { + ranges::begin(__t); + ranges::end(__t); }; - } // namespace __detail - - /// [range.range] The range concept. + /// [range.range] The safe_range concept. template - concept range = __detail::__range_impl<_Tp&>; + concept safe_range = range<_Tp> && __detail::__maybe_safe_range<_Tp>; + + template + using iterator_t = decltype(ranges::begin(std::declval<_Range&>())); template using sentinel_t = decltype(ranges::end(std::declval<_Range&>())); template - using iterator_t = decltype(ranges::begin(std::declval<_Range&>())); + using range_difference_t = iter_difference_t>; template using range_value_t = iter_value_t>; @@ -872,43 +877,38 @@ namespace ranges using range_rvalue_reference_t = iter_rvalue_reference_t>; - template - using range_difference_t = iter_difference_t>; - - namespace __detail - { - template - concept __forwarding_range = range<_Tp> && __range_impl<_Tp>; - } // namespace __detail - /// [range.sized] The sized_range concept. template concept sized_range = range<_Tp> && requires(_Tp& __t) { ranges::size(__t); }; - template - inline constexpr bool disable_sized_range = false; - // [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> @@ -917,11 +917,12 @@ namespace ranges { 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 + // [range.iter.ops] range iterator operations template constexpr void diff --git a/libstdc++-v3/include/experimental/string_view b/libstdc++-v3/include/experimental/string_view index 84b2a3e..cc9cb93 100644 --- a/libstdc++-v3/include/experimental/string_view +++ b/libstdc++-v3/include/experimental/string_view @@ -691,6 +691,18 @@ namespace experimental } // namespace literals } // namespace experimental +#if __cpp_lib_concepts + namespace ranges + { + template extern inline const bool enable_safe_range; + // Opt-in to safe_range concept + template + inline constexpr bool + enable_safe_range> + = true; + } +#endif + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index e1bf6ee..c256781 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -89,9 +89,10 @@ namespace ranges = 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> - && (__detail::__forwarding_range<_Tp> || view>); + && (safe_range<_Tp> || view>); namespace __detail { @@ -295,7 +296,7 @@ namespace ranges } template<__detail::__not_same_as _Rng> - requires __detail::__forwarding_range<_Rng> + requires safe_range<_Rng> && convertible_to, _It> && convertible_to, _Sent> constexpr @@ -306,7 +307,7 @@ namespace ranges _M_size._M_size = ranges::size(__r); } - template<__detail::__forwarding_range _Rng> + template requires convertible_to, _It> && convertible_to, _Sent> constexpr @@ -401,12 +402,6 @@ namespace ranges 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> @@ -424,14 +419,14 @@ namespace ranges -> subrange, tuple_element_t<1, _Pr>, subrange_kind::sized>; - template<__detail::__forwarding_range _Rng> + template 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> + template subrange(_Rng&&, __detail::__make_unsigned_like_t>) -> subrange, sentinel_t<_Rng>, subrange_kind::sized>; @@ -457,6 +452,12 @@ namespace ranges else return __r.end(); } + + template _Sent, + subrange_kind _Kind> + inline constexpr bool + enable_safe_range> = true; + } // namespace ranges using ranges::get; @@ -471,8 +472,19 @@ namespace ranges constexpr dangling(_Args&&...) noexcept { } }; + template + using safe_iterator_t = conditional_t, + iterator_t<_Range>, + dangling>; + + template + using safe_subrange_t = conditional_t, + subrange>, + dangling>; + template requires is_object_v<_Tp> - class empty_view : public view_interface> + class empty_view + : public view_interface> { public: static constexpr _Tp* begin() noexcept { return nullptr; } @@ -480,11 +492,11 @@ namespace ranges 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; } }; + template + inline constexpr bool enable_safe_range> = true; + namespace __detail { template requires is_object_v<_Tp> @@ -899,6 +911,9 @@ namespace ranges == __detail::__is_signed_integer_like<_Bound>)) iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>; + template + inline constexpr bool enable_safe_range> = true; + namespace views { template diff --git a/libstdc++-v3/include/std/span b/libstdc++-v3/include/std/span index c71f8bc..f215dec 100644 --- a/libstdc++-v3/include/std/span +++ b/libstdc++-v3/include/std/span @@ -399,16 +399,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return {this->data() + __offset, __count}; } - // observers: range helpers - - friend constexpr iterator - begin(span __sp) noexcept - { return __sp.begin(); } - - friend constexpr iterator - end(span __sp) noexcept - { return __sp.end(); } - private: [[no_unique_address]] __detail::__extent_storage _M_extent; pointer _M_ptr; @@ -478,6 +468,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using type = _Type; }; + namespace ranges + { + template extern inline const bool enable_safe_range; + // Opt-in to safe_range concept + template + inline constexpr bool + enable_safe_range> = true; + } _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // concepts diff --git a/libstdc++-v3/include/std/string_view b/libstdc++-v3/include/std/string_view index 9d2a8e8..add432b 100644 --- a/libstdc++-v3/include/std/string_view +++ b/libstdc++-v3/include/std/string_view @@ -724,6 +724,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // namespace string_literals } // namespace literals +#if __cpp_lib_concepts + namespace ranges + { + template extern inline const bool enable_safe_range; + // Opt-in to safe_range concept + template + inline constexpr bool + enable_safe_range> = true; + } +#endif _GLIBCXX_END_NAMESPACE_VERSION } // namespace std -- cgit v1.1