diff --git a/libcxx/include/__algorithm/copy.h b/libcxx/include/__algorithm/copy.h --- a/libcxx/include/__algorithm/copy.h +++ b/libcxx/include/__algorithm/copy.h @@ -58,20 +58,20 @@ template >::type, __iter_value_type<_OutIter> >::value - && __is_cpp17_contiguous_iterator<_InIter>::value - && __is_cpp17_contiguous_iterator<_OutIter>::value - && is_trivially_copy_assignable<__iter_value_type<_OutIter> >::value, int> = 0> + && __is_cpp17_contiguous_iterator::value + && __is_cpp17_contiguous_iterator::value + && is_trivially_copy_assignable<__iter_value_type<_OutIter> >::value + && __is_reverse_iterator<_InIter>::value + && __is_reverse_iterator<_OutIter>::value, int> = 0> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair, reverse_iterator<_OutIter> > -__copy_impl(reverse_iterator<_InIter> __first, - reverse_iterator<_InIter> __last, - reverse_iterator<_OutIter> __result) { +pair<_InIter, _OutIter> +__copy_impl(_InIter __first, _InIter __last, _OutIter __result) { auto __first_base = std::__unwrap_iter(__first.base()); auto __last_base = std::__unwrap_iter(__last.base()); auto __result_base = std::__unwrap_iter(__result.base()); auto __result_first = __result_base - (__first_base - __last_base); std::__copy_impl(__last_base, __first_base, __result_first); - return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); + return std::make_pair(__last, _OutIter(std::__rewrap_iter(__result.base(), __result_first))); } template +#include <__algorithm/iterator_operations.h> +#include <__algorithm/ranges_copy.h> #include <__algorithm/unwrap_iter.h> +#include <__concepts/same_as.h> #include <__config> #include <__iterator/iterator_traits.h> #include <__iterator/reverse_iterator.h> +#include <__ranges/subrange.h> +#include <__utility/move.h> +#include <__utility/pair.h> #include #include @@ -23,29 +29,31 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter1, _Iter2> __copy_backward_impl(_Iter1 __first, _Sent1 __last, _Iter2 __result) { - auto __ret = std::__copy(reverse_iterator<_Iter1>(__last), - reverse_iterator<_Sent1>(__first), - reverse_iterator<_Iter2>(__result)); - return pair<_Iter1, _Iter2>(__ret.first.base(), __ret.second.base()); +template ::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_InputIterator, _OutputIterator> +__copy_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + auto __ret = std::__copy( + __unconstrained_reverse_iterator<_InputIterator>(__last), + __unconstrained_reverse_iterator<_InputIterator>(__first), + __unconstrained_reverse_iterator<_OutputIterator>(__result)); + return pair<_InputIterator, _OutputIterator>(__ret.first.base(), __ret.second.base()); } -template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) { - auto __ret = std::__copy_backward_impl(std::__unwrap_iter(__first), - std::__unwrap_iter(__last), - std::__unwrap_iter(__result)); - return pair<_Iter1, _Iter2>(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +template ::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI constexpr pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) { + auto __reverse_range = std::__reverse_range(std::ranges::subrange(std::move(__first), std::move(__last))); + auto __ret = ranges::copy(std::move(__reverse_range), std::make_reverse_iterator(__result)); + return std::make_pair(__ret.in.base(), __ret.out.base()); } +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_BidirectionalIterator2 +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator2 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - return std::__copy_backward(__first, __last, __result).second; + return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -105,8 +105,8 @@ value_type* __p = __buff; for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr(), (void) ++__i, (void) ++__p) ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i)); - typedef reverse_iterator<_BidirectionalIterator> _RBi; - typedef reverse_iterator _Rv; + typedef __unconstrained_reverse_iterator<_BidirectionalIterator> _RBi; + typedef __unconstrained_reverse_iterator _Rv; typedef __invert<_Compare> _Inverted; std::__half_inplace_merge<_AlgPolicy, _Inverted>(_Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), diff --git a/libcxx/include/__algorithm/ranges_copy_backward.h b/libcxx/include/__algorithm/ranges_copy_backward.h --- a/libcxx/include/__algorithm/ranges_copy_backward.h +++ b/libcxx/include/__algorithm/ranges_copy_backward.h @@ -11,6 +11,7 @@ #include <__algorithm/copy_backward.h> #include <__algorithm/in_out_result.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/concepts.h> #include <__iterator/reverse_iterator.h> @@ -39,7 +40,7 @@ requires indirectly_copyable<_InIter1, _InIter2> _LIBCPP_HIDE_FROM_ABI constexpr copy_backward_result<_InIter1, _InIter2> operator()(_InIter1 __first, _Sent1 __last, _InIter2 __result) const { - auto __ret = std::__copy_backward(std::move(__first), std::move(__last), std::move(__result)); + auto __ret = std::__copy_backward<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } @@ -47,9 +48,7 @@ requires indirectly_copyable, _Iter> _LIBCPP_HIDE_FROM_ABI constexpr copy_backward_result, _Iter> operator()(_Range&& __r, _Iter __result) const { - auto __ret = std::__copy_backward(ranges::begin(__r), - ranges::end(__r), - std::move(__result)); + auto __ret = std::__copy_backward<_RangeAlgPolicy>(ranges::begin(__r), ranges::end(__r), std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } }; diff --git a/libcxx/include/__iterator/iterator_traits.h b/libcxx/include/__iterator/iterator_traits.h --- a/libcxx/include/__iterator/iterator_traits.h +++ b/libcxx/include/__iterator/iterator_traits.h @@ -501,6 +501,12 @@ typename add_const::value_type::first_type>::type, typename iterator_traits<_InputIterator>::value_type::second_type>; +template +using __iterator_category_type = typename iterator_traits<_Iter>::iterator_category; + +template +using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer; + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H diff --git a/libcxx/include/__iterator/reverse_iterator.h b/libcxx/include/__iterator/reverse_iterator.h --- a/libcxx/include/__iterator/reverse_iterator.h +++ b/libcxx/include/__iterator/reverse_iterator.h @@ -197,6 +197,12 @@ #endif // _LIBCPP_STD_VER > 17 }; +template +struct __is_reverse_iterator : false_type {}; + +template +struct __is_reverse_iterator > : true_type {}; + template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 bool @@ -327,20 +333,162 @@ } #endif +#if _LIBCPP_STD_VER <= 17 template -using _ReverseWrapper = reverse_iterator >; +using __unconstrained_reverse_iterator = reverse_iterator<_Iter>; +#else -template -struct __unwrap_iter_impl<_ReverseWrapper<_Iter>, __b> { +// __unconstrained_reverse_iterator allows us to use reverse iterators in the implementation of algorithms by working +// around a language issue in C++20. +// In C++20, when a reverse iterator wraps certain C++20-hostile iterators, calling comparison operators on it will +// result in a compilation error. However, calling comparison operators on the pristine hostile iterator is not +// an error. Thus, we cannot use reverse_iterators in the implementation of an algorithm that accepts a +// C++20-hostile iterator. This class is an internal workaround -- it is a copy of reverse_iterator with +// tweaks to make it support hostile iterators. +// +// A C++20-hostile iterator is one that defines a comparison operator where one of the arguments is an exact match +// and the other requires an implicit conversion, for example: +// friend bool operator==(const BaseIter&, const DerivedIter&); +// +// C++20 rules for rewriting equality operators create another overload of this function with parameters reversed: +// friend bool operator==(const DerivedIter&, const BaseIter&); +// +// This creates an ambiguity in overload resolution. +// +// Clang treats this ambiguity differently in different contexts. When operator== is actually called in the function +// body, the code is accepted with a warning. When a concept requires operator== to be a valid expression, however, +// it evaluates to false. Thus, the implementation of reverse_iterator::operator== can actually call operator== on its +// base iterators, but the constraints on reverse_iterator::operator== prevent it from being considered during overload +// resolution. This class simply removes the problematic constraints from comparison functions. +template +class __unconstrained_reverse_iterator { + _Iter __iter_; + +public: + static_assert(__is_cpp17_bidirectional_iterator<_Iter>::value); + + using iterator_type = _Iter; + using iterator_category = + _If<__is_cpp17_random_access_iterator<_Iter>::value, random_access_iterator_tag, __iterator_category_type<_Iter>>; + using pointer = __iterator_pointer_type<_Iter>; + using value_type = iter_value_t<_Iter>; + using difference_type = iter_difference_t<_Iter>; + using reference = iter_reference_t<_Iter>; + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator() = default; + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator(const __unconstrained_reverse_iterator&) = default; + _LIBCPP_HIDE_FROM_ABI constexpr explicit __unconstrained_reverse_iterator(_Iter __iter) : __iter_(__iter) {} + + _LIBCPP_HIDE_FROM_ABI constexpr _Iter base() const { return __iter_; } + _LIBCPP_HIDE_FROM_ABI constexpr reference operator*() const { + auto __tmp = __iter_; + return *--__tmp; + } + + _LIBCPP_HIDE_FROM_ABI constexpr pointer operator->() const { + if constexpr (is_pointer_v<_Iter>) { + return std::prev(__iter_); + } else { + return std::prev(__iter_).operator->(); + } + } + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator++() { + --__iter_; + return *this; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator++(int) { + auto __tmp = *this; + --__iter_; + return __tmp; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator--() { + ++__iter_; + return *this; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator--(int) { + auto __tmp = *this; + ++__iter_; + return __tmp; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator+=(difference_type __n) { + __iter_ -= __n; + return *this; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator-=(difference_type __n) { + __iter_ += __n; + return *this; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator+(difference_type __n) const { + return __unconstrained_reverse_iterator(__iter_ - __n); + } + + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator operator-(difference_type __n) const { + return __unconstrained_reverse_iterator(__iter_ + __n); + } + + _LIBCPP_HIDE_FROM_ABI constexpr difference_type operator-(const __unconstrained_reverse_iterator& __other) const { + return __other.__iter_ - __iter_; + } + + _LIBCPP_HIDE_FROM_ABI constexpr auto operator[](difference_type __n) const { return *(*this + __n); } + + // Deliberately unconstrained unlike the comparison functions in `reverse_iterator` -- see the class comment for the + // rationale. + _LIBCPP_HIDE_FROM_ABI friend constexpr bool + operator==(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) { + return __lhs.base() == __rhs.base(); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool + operator!=(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) { + return __lhs.base() != __rhs.base(); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool + operator<(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) { + return __lhs.base() > __rhs.base(); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool + operator>(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) { + return __lhs.base() < __rhs.base(); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool + operator<=(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) { + return __lhs.base() >= __rhs.base(); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool + operator>=(const __unconstrained_reverse_iterator& __lhs, const __unconstrained_reverse_iterator& __rhs) { + return __lhs.base() <= __rhs.base(); + } +}; + +template +struct __is_reverse_iterator<__unconstrained_reverse_iterator<_Iter>> : true_type {}; + +#endif // _LIBCPP_STD_VER <= 17 + +template