diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -96,6 +96,8 @@ __algorithm/ranges_minmax.h __algorithm/ranges_minmax_element.h __algorithm/ranges_mismatch.h + __algorithm/ranges_move.h + __algorithm/ranges_move_backward.h __algorithm/ranges_none_of.h __algorithm/ranges_replace.h __algorithm/ranges_replace_if.h 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 @@ -74,13 +74,6 @@ return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); } -template <class _InIter, class _Sent, class _OutIter> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<reverse_iterator<reverse_iterator<_InIter> >, reverse_iterator<reverse_iterator<_OutIter> > > -__copy_impl(reverse_iterator<reverse_iterator<_InIter> > __first, - reverse_iterator<reverse_iterator<_Sent> > __last, - reverse_iterator<reverse_iterator<_OutIter> > __result); - template <class _InIter, class _Sent, class _OutIter, __enable_if_t<!(is_copy_constructible<_InIter>::value && is_copy_constructible<_Sent>::value @@ -101,18 +94,6 @@ return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); } -// __unwrap_iter can't unwrap random_access_iterators, so we need to unwrap two reverse_iterators manually -template <class _InIter, class _Sent, class _OutIter> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<reverse_iterator<reverse_iterator<_InIter> >, reverse_iterator<reverse_iterator<_OutIter> > > -__copy_impl(reverse_iterator<reverse_iterator<_InIter> > __first, - reverse_iterator<reverse_iterator<_Sent> > __last, - reverse_iterator<reverse_iterator<_OutIter> > __result) { - auto __ret = std::__copy(__first.base().base(), __last.base().base(), __result.base().base()); - return std::make_pair(reverse_iterator<reverse_iterator<_InIter> >(reverse_iterator<_InIter>(__ret.first)), - reverse_iterator<reverse_iterator<_OutIter> >(reverse_iterator<_OutIter>(__ret.second))); -} - template <class _InputIterator, class _OutputIterator> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator diff --git a/libcxx/include/__algorithm/move.h b/libcxx/include/__algorithm/move.h --- a/libcxx/include/__algorithm/move.h +++ b/libcxx/include/__algorithm/move.h @@ -11,7 +11,10 @@ #include <__algorithm/unwrap_iter.h> #include <__config> +#include <__iterator/iterator_traits.h> +#include <__iterator/reverse_iterator.h> #include <__utility/move.h> +#include <__utility/pair.h> #include <cstring> #include <type_traits> @@ -23,53 +26,88 @@ // move -template <class _InputIterator, class _OutputIterator> +template <class _InIter, class _Sent, class _OutIter> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -_OutputIterator -__move_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - for (; __first != __last; ++__first, (void) ++__result) - *__result = _VSTD::move(*__first); - return __result; +pair<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { + while (__first != __last) { + *__result = std::move(*__first); + ++__first; + ++__result; + } + return std::make_pair(std::move(__first), std::move(__result)); } -template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -_OutputIterator -__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - return _VSTD::__move_constexpr(__first, __last, __result); +template <class _InType, + class _OutType, + class = __enable_if_t<is_same<typename remove_const<_InType>::type, _OutType>::value + && is_trivially_move_assignable<_OutType>::value> > +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_InType*, _OutType*> __move_impl(_InType* __first, _InType* __last, _OutType* __result) { + if (__libcpp_is_constant_evaluated() +// TODO: Remove this once GCC supports __builtin_memmove during constant evaluation +#ifndef _LIBCPP_COMPILER_GCC + && !is_trivially_copyable<_InType>::value +#endif + ) + return std::__move_impl<_InType*, _InType*, _OutType*>(__first, __last, __result); + const size_t __n = static_cast<size_t>(__last - __first); + ::__builtin_memmove(__result, __first, __n * sizeof(_OutType)); + return std::make_pair(__first + __n, __result + __n); } -template <class _Tp, class _Up> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -typename enable_if -< - is_same<typename remove_const<_Tp>::type, _Up>::value && - is_trivially_move_assignable<_Up>::value, - _Up* ->::type -__move(_Tp* __first, _Tp* __last, _Up* __result) -{ - const size_t __n = static_cast<size_t>(__last - __first); - if (__n > 0) - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); - return __result + __n; +template <class> +struct __is_trivially_move_assignable_unwrapped_impl : false_type {}; + +template <class _Type> +struct __is_trivially_move_assignable_unwrapped_impl<_Type*> : is_trivially_move_assignable<_Type> {}; + +template <class _Iter> +struct __is_trivially_move_assignable_unwrapped + : __is_trivially_move_assignable_unwrapped_impl<decltype(std::__unwrap_iter<_Iter>(std::declval<_Iter>()))> {}; + +template <class _InIter, + class _OutIter, + __enable_if_t<is_same<typename remove_const<typename iterator_traits<_InIter>::value_type>::type, + typename iterator_traits<_OutIter>::value_type>::value + && __is_cpp17_contiguous_iterator<_InIter>::value + && __is_cpp17_contiguous_iterator<_OutIter>::value + && is_trivially_move_assignable<__iter_value_type<_OutIter> >::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14 +pair<reverse_iterator<_InIter>, reverse_iterator<_OutIter> > +__move_impl(reverse_iterator<_InIter> __first, + reverse_iterator<_InIter> __last, + reverse_iterator<_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::__move_impl(__last_base, __first_base, __result_first); + return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); +} + +template <class _InIter, class _Sent, class _OutIter> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +__enable_if_t<is_copy_constructible<_InIter>::value + && is_copy_constructible<_Sent>::value + && is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > +__move(_InIter __first, _Sent __last, _OutIter __result) { + auto __ret = std::__move_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result)); + return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); +} + +template <class _InIter, class _Sent, class _OutIter> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +__enable_if_t<!is_copy_constructible<_InIter>::value + || !is_copy_constructible<_Sent>::value + || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > +__move(_InIter __first, _Sent __last, _OutIter __result) { + return std::__move_impl(std::move(__first), std::move(__last), std::move(__result)); } template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - if (__libcpp_is_constant_evaluated()) { - return _VSTD::__move_constexpr(__first, __last, __result); - } else { - return _VSTD::__rewrap_iter(__result, - _VSTD::__move(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); - } +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + return std::__move(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/move_backward.h b/libcxx/include/__algorithm/move_backward.h --- a/libcxx/include/__algorithm/move_backward.h +++ b/libcxx/include/__algorithm/move_backward.h @@ -9,11 +9,9 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_BACKWARD_H #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H -#include <__algorithm/unwrap_iter.h> +#include <__algorithm/move.h> #include <__config> -#include <__utility/move.h> -#include <cstring> -#include <type_traits> +#include <__iterator/reverse_iterator.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,57 +19,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -_OutputIterator -__move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - while (__first != __last) - *--__result = _VSTD::move(*--__last); - return __result; -} - -template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -_OutputIterator -__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - return _VSTD::__move_backward_constexpr(__first, __last, __result); -} - -template <class _Tp, class _Up> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -typename enable_if -< - is_same<typename remove_const<_Tp>::type, _Up>::value && - is_trivially_move_assignable<_Up>::value, - _Up* ->::type -__move_backward(_Tp* __first, _Tp* __last, _Up* __result) -{ - const size_t __n = static_cast<size_t>(__last - __first); - if (__n > 0) - { - __result -= __n; - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); - } - return __result; -} - template <class _BidirectionalIterator1, class _BidirectionalIterator2> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator2 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - if (__libcpp_is_constant_evaluated()) { - return _VSTD::__move_backward_constexpr(__first, __last, __result); - } else { - return _VSTD::__rewrap_iter(__result, - _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); - } + return std::__move(reverse_iterator<_BidirectionalIterator1>(__last), + reverse_iterator<_BidirectionalIterator1>(__first), + reverse_iterator<_BidirectionalIterator2>(__result)).second.base(); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_move.h b/libcxx/include/__algorithm/ranges_move.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_move.h @@ -0,0 +1,83 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MOVE_H +#define _LIBCPP___ALGORITHM_RANGES_MOVE_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/move.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/iter_move.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter, class _OutIter> +using move_result = in_out_result<_InIter, _OutIter>; + +namespace __move { +struct __fn { + + template <class _InIter, class _Sent, class _OutIter> + requires __iter_move::__move_deref<_InIter> // check that we are allowed to std::move() the value + _LIBCPP_HIDE_FROM_ABI constexpr static + move_result<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { + auto __ret = std::__move(std::move(__first), std::move(__last), std::move(__result)); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template <class _InIter, class _Sent, class _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr static + move_result<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { + while (__first != __last) { + *__result = ranges::iter_move(__first); + ++__first; + ++__result; + } + return {std::move(__first), std::move(__result)}; + } + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter> + requires indirectly_movable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { + return __move_impl(std::move(__first), std::move(__last), std::move(__result)); + } + + template <input_range _Range, weakly_incrementable _OutIter> + requires indirectly_movable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range, _OutIter __result) const { + return __move_impl(ranges::begin(__range), ranges::end(__range), std::move(__result)); + } + +}; +} // namespace __move + +inline namespace __cpo { + inline constexpr auto move = __move::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MOVE_H diff --git a/libcxx/include/__algorithm/ranges_move_backward.h b/libcxx/include/__algorithm/ranges_move_backward.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_move_backward.h @@ -0,0 +1,75 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MOVE_BACKWARD_H +#define _LIBCPP___ALGORITHM_RANGES_MOVE_BACKWARD_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_move.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/iter_move.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter, class _OutIter> +using move_backward_result = in_out_result<_InIter, _OutIter>; + +namespace __move_backward { +struct __fn { + + template <class _InIter, class _Sent, class _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr static + move_backward_result<_InIter, _OutIter> __move_backward_impl(_InIter __first, _Sent __last, _OutIter __result) { + auto __ret = ranges::move(std::make_reverse_iterator(ranges::next(__first, __last)), + std::make_reverse_iterator(__first), + std::make_reverse_iterator(__result)); + return {std::move(__ret.first.base()), std::move(__ret.second.base())}; + } + + template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, bidirectional_iterator _OutIter> + requires indirectly_movable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_backward_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { + return __move_backward_impl(std::move(__first), std::move(__last), std::move(__result)); + } + + template <bidirectional_range _Range, bidirectional_iterator _Iter> + requires indirectly_movable<iterator_t<_Range>, _Iter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_backward_result<borrowed_iterator_t<_Range>, _Iter> operator()(_Range&& __range, _Iter __result) const { + return __move_backward_impl(ranges::begin(__range), ranges::end(__range), std::move(__result)); + } + +}; +} // namespace __move_backward + +inline namespace __cpo { + inline constexpr auto move_backward = __move_backward::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MOVE_BACKWARD_H diff --git a/libcxx/include/__algorithm/unwrap_iter.h b/libcxx/include/__algorithm/unwrap_iter.h --- a/libcxx/include/__algorithm/unwrap_iter.h +++ b/libcxx/include/__algorithm/unwrap_iter.h @@ -63,6 +63,22 @@ return _Impl::__apply(__i); } +template <class _OrigIter, class _UnwrappedIter> +struct __rewrap_iter_impl { + static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter __first, _UnwrappedIter __result) { + // Precondition: __result is reachable from __first + // Precondition: _OrigIter is a contiguous iterator + return __first + (__result - std::__unwrap_iter(__first)); + } +}; + +template <class _OrigIter> +struct __rewrap_iter_impl<_OrigIter, _OrigIter> { + static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter, _OrigIter __result) { + return __result; + } +}; + template<class _OrigIter> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) @@ -70,13 +86,11 @@ return __result; } -template<class _OrigIter, class _UnwrappedIter> +template<class _OrigIter, class _UnwrappedIter, class _Impl = __rewrap_iter_impl<_OrigIter, _UnwrappedIter>> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result) { - // Precondition: __result is reachable from __first - // Precondition: _OrigIter is a contiguous iterator - return __first + (__result - _VSTD::__unwrap_iter(__first)); + return _Impl::__apply(__first, __result); } _LIBCPP_END_NAMESPACE_STD 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 @@ -10,6 +10,7 @@ #ifndef _LIBCPP___ITERATOR_REVERSE_ITERATOR_H #define _LIBCPP___ITERATOR_REVERSE_ITERATOR_H +#include <__algorithm/unwrap_iter.h> #include <__compare/compare_three_way_result.h> #include <__compare/three_way_comparable.h> #include <__concepts/convertible_to.h> @@ -321,6 +322,53 @@ } #endif +template <class _Iter> +using _ReverseWrapper = reverse_iterator<reverse_iterator<_Iter> >; + +template <class _Iter, bool __b> +struct __unwrap_iter_impl<_ReverseWrapper<_Iter>, __b> { + static _LIBCPP_CONSTEXPR + decltype(std::__unwrap_iter(std::declval<_Iter>())) __apply(_ReverseWrapper<_Iter> __i) _NOEXCEPT { + return std::__unwrap_iter(__i.base().base()); + } +}; + +template <class _OrigIter, class _UnwrappedIter> +struct __rewrap_iter_impl<_ReverseWrapper<_OrigIter>, _UnwrappedIter> { + template <class _Iter> + struct _ReverseWrapperCount { static _LIBCPP_CONSTEXPR const size_t value = 1; }; + + template <class _Iter> + struct _ReverseWrapperCount<_ReverseWrapper<_Iter> > { + static _LIBCPP_CONSTEXPR const size_t value = 1 + _ReverseWrapperCount<_Iter>::value; + }; + + template <size_t _RewrapCount, + class _OIter, + class _UIter, + __enable_if_t<_RewrapCount != 0, int> = 0> + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR + _ReverseWrapper<_OIter> __rewrap(_ReverseWrapper<_OIter> __iter1, _UIter __iter2) { + auto __it = __rewrap<_RewrapCount - 1>(__iter1.base().base(), __iter2); + return _ReverseWrapper<_OIter>(reverse_iterator<_OIter>(__it)); + } + + template <size_t _RewrapCount, + class _OIter, + class _UIter, + __enable_if_t<_RewrapCount == 0, int> = 0> + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR + decltype(std::__rewrap_iter(std::declval<_OIter>(), std::declval<_UIter>())) + __rewrap(_OIter __iter1, _UIter __iter2) { + return std::__rewrap_iter(__iter1, __iter2); + } + + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR + _ReverseWrapper<_OrigIter> __apply(_ReverseWrapper<_OrigIter> __iter1, _UnwrappedIter __iter2) { + return __rewrap<_ReverseWrapperCount<_OrigIter>::value>(__iter1, __iter2); + } +}; + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -424,6 +424,27 @@ constexpr borrowed_iterator_t<R> ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {}); // since C++20 + template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2> + requires indirectly_movable<I1, I2> + constexpr ranges::move_backward_result<I1, I2> + ranges::move_backward(I1 first, S1 last, I2 result); // since C++20 + + template<bidirectional_range R, bidirectional_iterator I> + requires indirectly_movable<iterator_t<R>, I> + constexpr ranges::move_backward_result<borrowed_iterator_t<R>, I> + ranges::move_backward(R&& r, I result); // since C++20 + + template<input_iterator I, sentinel_for<I> S, weakly_incrementable O> + requires indirectly_movable<I, O> + constexpr ranges::move_result<I, O> + ranges::move(I first, S last, O result); // since C++20 + + template<input_range R, weakly_incrementable O> + requires indirectly_movable<iterator_t<R>, O> + constexpr ranges::move_result<borrowed_iterator_t<R>, O> + ranges::move(R&& r, O result); // since C++20 + + } constexpr bool // constexpr in C++20 @@ -1170,6 +1191,8 @@ #include <__algorithm/ranges_minmax.h> #include <__algorithm/ranges_minmax_element.h> #include <__algorithm/ranges_mismatch.h> +#include <__algorithm/ranges_move.h> +#include <__algorithm/ranges_move_backward.h> #include <__algorithm/ranges_none_of.h> #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.h> diff --git a/libcxx/include/ext/hash_map b/libcxx/include/ext/hash_map --- a/libcxx/include/ext/hash_map +++ b/libcxx/include/ext/hash_map @@ -209,6 +209,7 @@ #include <functional> #include <iterator> // TODO: Remove this include #include <stdexcept> +#include <iterator> // TODO: Remove this include #include <type_traits> #if defined(__DEPRECATED) && __DEPRECATED diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -335,6 +335,8 @@ module ranges_minmax { private header "__algorithm/ranges_minmax.h" } module ranges_minmax_element { private header "__algorithm/ranges_minmax_element.h" } module ranges_mismatch { private header "__algorithm/ranges_mismatch.h" } + module ranges_move { private header "__algorithm/ranges_move.h" } + module ranges_move_backward { private header "__algorithm/ranges_move_backward.h" } module ranges_none_of { private header "__algorithm/ranges_none_of.h" } module ranges_replace { private header "__algorithm/ranges_replace.h" } module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" } diff --git a/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp b/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp --- a/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp +++ b/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp @@ -19,6 +19,7 @@ #include <algorithm> #include <cassert> #include <iterator> +#include <ranges> #include <type_traits> struct S { @@ -43,6 +44,7 @@ using pointer = T*; using reference = T&; + constexpr NotIncrementableIt() = default; constexpr NotIncrementableIt(T* i_) : i(i_) {} friend constexpr bool operator==(const NotIncrementableIt& lhs, const NotIncrementableIt& rhs) { @@ -50,6 +52,7 @@ } constexpr T& operator*() { return *i; } + constexpr T& operator*() const { return *i; } constexpr T* operator->() { return i; } constexpr T* operator->() const { return i; } @@ -58,6 +61,11 @@ return *this; } + constexpr NotIncrementableIt& operator++(int) { + assert(false); + return *this; + } + constexpr NotIncrementableIt& operator--() { assert(false); return *this; @@ -70,39 +78,95 @@ static_assert(std::__is_cpp17_contiguous_iterator<NotIncrementableIt<S>>::value); -template <class Iter> +template <size_t N, class Iter, std::enable_if_t<N == 0>* = nullptr> +constexpr auto wrap_n_times(Iter i) { + return i; +} + +template <size_t N, class Iter, std::enable_if_t<N != 0>* = nullptr> +constexpr auto wrap_n_times(Iter i) { + return std::make_reverse_iterator(wrap_n_times<N - 1>(i)); +} + +static_assert(std::is_same_v<decltype(wrap_n_times<2>(std::declval<int*>())), + std::reverse_iterator<std::reverse_iterator<int*>>>); + +template <size_t InCount, size_t OutCount, class Iter> constexpr void test_normal() { - S a[] = {1, 2, 3, 4}; - S b[] = {0, 0, 0, 0}; - std::copy(Iter(a), Iter(a + 4), Iter(b)); - assert(std::equal(a, a + 4, b)); + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + std::copy(wrap_n_times<InCount>(Iter(a)), wrap_n_times<InCount>(Iter(a + 4)), wrap_n_times<OutCount>(Iter(b))); + assert(std::equal(a, a + 4, b)); + } + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + std::ranges::copy(wrap_n_times<InCount>(Iter(a)), + wrap_n_times<InCount>(Iter(a + 4)), + wrap_n_times<OutCount>(Iter(b))); + assert(std::equal(a, a + 4, b)); + } + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + auto range = std::ranges::subrange(wrap_n_times<InCount>(Iter(a)), wrap_n_times<InCount>(Iter(a + 4))); + std::ranges::copy(range, Iter(b)); + assert(std::equal(a, a + 4, b)); + } } -template <class Iter> +template <size_t InCount, size_t OutCount, class Iter> constexpr void test_reverse() { - S a[] = {1, 2, 3, 4}; - S b[] = {0, 0, 0, 0}; - std::copy(std::make_reverse_iterator(Iter(a + 4)), - std::make_reverse_iterator(Iter(a)), - std::make_reverse_iterator(Iter(b + 4))); + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + std::copy(std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a + 4))), + std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a))), + std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4)))); + assert(std::equal(a, a + 4, b)); + } + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + std::ranges::copy(std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a + 4))), + std::make_reverse_iterator(wrap_n_times<InCount>(Iter(a))), + std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4)))); + assert(std::equal(a, a + 4, b)); + } + { + S a[] = {1, 2, 3, 4}; + S b[] = {0, 0, 0, 0}; + auto range = std::ranges::subrange(wrap_n_times<InCount>(std::make_reverse_iterator(Iter(a + 4))), + wrap_n_times<InCount>(std::make_reverse_iterator(Iter(a)))); + std::ranges::copy(range, std::make_reverse_iterator(wrap_n_times<OutCount>(Iter(b + 4)))); + assert(std::equal(a, a + 4, b)); + } +} + +template <size_t InCount, size_t OutCount> +constexpr void test_normal_revese() { + test_normal<InCount, OutCount, S*>(); + test_normal<InCount, OutCount, NotIncrementableIt<S>>(); + test_reverse<InCount, OutCount, S*>(); + test_reverse<InCount, OutCount, NotIncrementableIt<S>>(); } -template <class Iter> -constexpr void test_reverse_reverse() { - S a[] = {1, 2, 3, 4}; - S b[] = {0, 0, 0, 0}; - std::copy(std::make_reverse_iterator(std::make_reverse_iterator(Iter(a))), - std::make_reverse_iterator(std::make_reverse_iterator(Iter(a + 4))), - std::make_reverse_iterator(std::make_reverse_iterator(Iter(b)))); +template <size_t InCount> +constexpr void test_out_count() { + test_normal_revese<InCount, 0>(); + test_normal_revese<InCount, 2>(); + test_normal_revese<InCount, 4>(); + test_normal_revese<InCount, 6>(); + test_normal_revese<InCount, 8>(); } constexpr bool test() { - test_normal<S*>(); - test_normal<NotIncrementableIt<S>>(); - test_reverse<S*>(); - test_reverse<NotIncrementableIt<S>>(); - test_reverse_reverse<S*>(); - test_reverse_reverse<NotIncrementableIt<S>>(); + test_out_count<0>(); + test_out_count<2>(); + test_out_count<4>(); + test_out_count<6>(); + test_out_count<8>(); return true; } diff --git a/libcxx/test/libcxx/algorithms/unwrap_iter.compile.pass.cpp b/libcxx/test/libcxx/algorithms/unwrap_iter.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/algorithms/unwrap_iter.compile.pass.cpp @@ -0,0 +1,37 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14 + +// check that std::__unwrap_iter() returns the correct type + +#include <algorithm> +#include <type_traits> + +#include "test_iterators.h" + +template <class Iter> +using UnwrapT = decltype(std::__unwrap_iter(std::declval<Iter>())); + +template <class Iter> +using rev_iter = std::reverse_iterator<Iter>; + +template <class Iter> +using rev_rev_iter = rev_iter<rev_iter<Iter>>; + +static_assert(std::is_same_v<UnwrapT<int*>, int*>); +static_assert(std::is_same_v<UnwrapT<std::__wrap_iter<int*>>, int*>); +static_assert(std::is_same_v<UnwrapT<rev_iter<int*>>, std::reverse_iterator<int*>>); +static_assert(std::is_same_v<UnwrapT<rev_rev_iter<int*>>, int*>); +static_assert(std::is_same_v<UnwrapT<rev_rev_iter<std::__wrap_iter<int*>>>, int*>); +static_assert(std::is_same_v<UnwrapT<rev_rev_iter<rev_iter<std::__wrap_iter<int*>>>>, rev_iter<std::__wrap_iter<int*>>>); + +static_assert(std::is_same_v<UnwrapT<random_access_iterator<int*>>, random_access_iterator<int*>>); +static_assert(std::is_same_v<UnwrapT<rev_iter<random_access_iterator<int*>>>, rev_iter<random_access_iterator<int*>>>); +static_assert(std::is_same_v<UnwrapT<rev_rev_iter<random_access_iterator<int*>>>, random_access_iterator<int*>>); +static_assert(std::is_same_v<UnwrapT<rev_rev_iter<rev_iter<random_access_iterator<int*>>>>, rev_iter<random_access_iterator<int*>>>); diff --git a/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp b/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/iterators/unwrap_iter.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// check that std::__unwrap_iter() returns the correct type + +#include <algorithm> +#include <cassert> +#include <string> +#include <type_traits> + +#include "test_iterators.h" +#include "test_macros.h" + +template <class Iter> +using UnwrapT = decltype(std::__unwrap_iter(std::declval<Iter>())); + +template <class Iter> +using rev_iter = std::reverse_iterator<Iter>; + +template <class Iter> +using rev_rev_iter = rev_iter<rev_iter<Iter> >; + +static_assert(std::is_same<UnwrapT<int*>, int*>::value, ""); +static_assert(std::is_same<UnwrapT<std::__wrap_iter<int*> >, int*>::value, ""); +static_assert(std::is_same<UnwrapT<rev_iter<int*> >, std::reverse_iterator<int*> >::value, ""); +static_assert(std::is_same<UnwrapT<rev_rev_iter<int*> >, int*>::value, ""); +static_assert(std::is_same<UnwrapT<rev_rev_iter<std::__wrap_iter<int*> > >, int*>::value, ""); +static_assert(std::is_same<UnwrapT<rev_rev_iter<rev_iter<std::__wrap_iter<int*> > > >, rev_iter<std::__wrap_iter<int*> > >::value, ""); + +static_assert(std::is_same<UnwrapT<random_access_iterator<int*> >, random_access_iterator<int*> >::value, ""); +static_assert(std::is_same<UnwrapT<rev_iter<random_access_iterator<int*> > >, rev_iter<random_access_iterator<int*> > >::value, ""); +static_assert(std::is_same<UnwrapT<rev_rev_iter<random_access_iterator<int*> > >, random_access_iterator<int*> >::value, ""); +static_assert(std::is_same<UnwrapT<rev_rev_iter<rev_iter<random_access_iterator<int*> > > >, rev_iter<random_access_iterator<int*> > >::value, ""); + +TEST_CONSTEXPR_CXX20 bool test() { + std::string str = "Banane"; + using Iter = std::string::iterator; + + assert(std::__unwrap_iter(str.begin()) == str.data()); + assert(std::__unwrap_iter(str.end()) == str.data() + str.size()); + assert(std::__unwrap_iter(rev_rev_iter<Iter>(rev_iter<Iter>(str.begin()))) == str.data()); + assert(std::__unwrap_iter(rev_rev_iter<Iter>(rev_iter<Iter>(str.end()))) == str.data() + str.size()); + + return true; +} + +int main(int, char**) { + test(); +#if TEST_STD_VER > 17 + static_assert(test()); +#endif + + return 0; +} diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -133,6 +133,8 @@ #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}} #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}} #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}} +#include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}} +#include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}} #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}} #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}} #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp @@ -0,0 +1,259 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// <algorithm> + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template<input_iterator I, sentinel_for<I> S, weakly_incrementable O> +// requires indirectly_movable<I, O> +// constexpr ranges::move_result<I, O> +// ranges::move(I first, S last, O result); +// template<input_range R, weakly_incrementable O> +// requires indirectly_movable<iterator_t<R>, O> +// constexpr ranges::move_result<borrowed_iterator_t<R>, O> +// ranges::move(R&& r, O result); + +#include <algorithm> +#include <array> +#include <cassert> +#include <ranges> + +#include "almost_satisfies_types.h" +#include "MoveOnly.h" +#include "test_iterators.h" + +template <class In, class Out = In, class Sent = sentinel_wrapper<In>> +concept HasMoveIt = requires(In in, Sent sent, Out out) { std::ranges::move(in, sent, out); }; + +static_assert(HasMoveIt<int*>); +static_assert(!HasMoveIt<InputIteratorNotDerivedFrom>); +static_assert(!HasMoveIt<InputIteratorNotIndirectlyReadable>); +static_assert(!HasMoveIt<InputIteratorNotInputOrOutputIterator>); +static_assert(!HasMoveIt<int*, WeaklyIncrementableNotMovable>); +struct NotIndirectlyMovable {}; +static_assert(!HasMoveIt<int*, NotIndirectlyMovable*>); +static_assert(!HasMoveIt<int*, int*, SentinelForNotSemiregular>); +static_assert(!HasMoveIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>); + +template <class Range, class Out> +concept HasMoveR = requires(Range range, Out out) { std::ranges::move(range, out); }; + +static_assert(HasMoveR<std::array<int, 10>, int*>); +static_assert(!HasMoveR<InputRangeNotDerivedFrom, int*>); +static_assert(!HasMoveR<InputRangeNotIndirectlyReadable, int*>); +static_assert(!HasMoveR<InputRangeNotInputOrOutputIterator, int*>); +static_assert(!HasMoveR<WeaklyIncrementableNotMovable, int*>); +static_assert(!HasMoveR<UncheckedRange<NotIndirectlyMovable*>, int*>); +static_assert(!HasMoveR<InputRangeNotSentinelSemiregular, int*>); +static_assert(!HasMoveR<InputRangeNotSentinelEqualityComparableWith, int*>); +static_assert(!HasMoveR<UncheckedRange<int*>, WeaklyIncrementableNotMovable>); + +static_assert(std::is_same_v<std::ranges::move_result<int, long>, std::ranges::in_out_result<int, long>>); + +template <class In, class Out, class Sent, int N> +constexpr void test(std::array<int, N> in) { + { + std::array<int, N> out; + std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret = + std::ranges::move(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data())); + assert(in == out); + assert(base(ret.in) == in.data() + in.size()); + assert(base(ret.out) == out.data() + out.size()); + } + { + std::array<int, N> out; + auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size()))); + std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret = + std::ranges::move(range, Out(out.data())); + assert(in == out); + assert(base(ret.in) == in.data() + in.size()); + assert(base(ret.out) == out.data() + out.size()); + } +} + +template <class In, class Out, class Sent = In> +constexpr void test_iterators() { + // simple test + test<In, Out, Sent, 4>({1, 2, 3, 4}); + // check that an empty range works + test<In, Out, Sent, 0>({}); +} + +template <class Out> +constexpr void test_in_iterators() { + test_iterators<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>(); + test_iterators<forward_iterator<int*>, Out>(); + test_iterators<bidirectional_iterator<int*>, Out>(); + test_iterators<random_access_iterator<int*>, Out>(); + test_iterators<contiguous_iterator<int*>, Out>(); +} + +struct IteratorWithMoveIter { + using value_type = int; + using difference_type = int; + explicit IteratorWithMoveIter() = default; + int* ptr; + constexpr IteratorWithMoveIter(int* ptr_) : ptr(ptr_) {} + + constexpr int& operator*() const; // iterator with iter_move should not be dereferenced + + constexpr IteratorWithMoveIter& operator++() { ++ptr; return *this; } + constexpr IteratorWithMoveIter operator++(int) { auto ret = *this; ++*this; return ret; } + + friend constexpr int iter_move(const IteratorWithMoveIter&) { return 42; } + + constexpr bool operator==(const IteratorWithMoveIter& other) const = default; +}; + +constexpr bool test() { + test_in_iterators<cpp17_output_iterator<int*>>(); + test_in_iterators<cpp20_output_iterator<int*>>(); + test_in_iterators<cpp17_input_iterator<int*>>(); + test_in_iterators<cpp20_input_iterator<int*>>(); + test_in_iterators<forward_iterator<int*>>(); + test_in_iterators<bidirectional_iterator<int*>>(); + test_in_iterators<random_access_iterator<int*>>(); + test_in_iterators<contiguous_iterator<int*>>(); + + { // check that a move-only type works + { + MoveOnly a[] = {1, 2, 3}; + MoveOnly b[3]; + std::ranges::move(a, std::begin(b)); + assert(b[0].get() == 1); + assert(b[1].get() == 2); + assert(b[2].get() == 3); + } + { + MoveOnly a[] = {1, 2, 3}; + MoveOnly b[3]; + std::ranges::move(std::begin(a), std::end(a), std::begin(b)); + assert(b[0].get() == 1); + assert(b[1].get() == 2); + assert(b[2].get() == 3); + } + } + + { // check that ranges::dangling is returned + std::array<int, 4> out; + std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> decltype(auto) ret = + std::ranges::move(std::array {1, 2, 3, 4}, out.data()); + assert(ret.out == out.data() + 4); + assert((out == std::array{1, 2, 3, 4})); + } + + { // check that an iterator is returned with a borrowing range + std::array in {1, 2, 3, 4}; + std::array<int, 4> out; + std::same_as<std::ranges::in_out_result<int*, int*>> decltype(auto) ret = + std::ranges::move(std::views::all(in), out.data()); + assert(ret.in == in.data() + 4); + assert(ret.out == out.data() + 4); + assert(in == out); + } + + { // check that every element is moved exactly once + struct MoveOnce { + bool moved = false; + constexpr MoveOnce() = default; + constexpr MoveOnce(const MoveOnce& other) = delete; + constexpr MoveOnce& operator=(MoveOnce&& other) { + assert(!other.moved); + moved = true; + return *this; + } + }; + { + std::array<MoveOnce, 4> in {}; + std::array<MoveOnce, 4> out {}; + auto ret = std::ranges::move(in.begin(), in.end(), out.begin()); + assert(ret.in == in.end()); + assert(ret.out == out.end()); + assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; })); + } + { + std::array<MoveOnce, 4> in {}; + std::array<MoveOnce, 4> out {}; + auto ret = std::ranges::move(in, out.begin()); + assert(ret.in == in.end()); + assert(ret.out == out.end()); + assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; })); + } + } + + { // check that the range is moved forwards + struct OnlyForwardsMovable { + OnlyForwardsMovable* next = nullptr; + bool canMove = false; + OnlyForwardsMovable() = default; + constexpr OnlyForwardsMovable& operator=(OnlyForwardsMovable&&) { + assert(canMove); + if (next != nullptr) + next->canMove = true; + return *this; + } + }; + { + std::array<OnlyForwardsMovable, 3> in {}; + std::array<OnlyForwardsMovable, 3> out {}; + out[0].next = &out[1]; + out[1].next = &out[2]; + out[0].canMove = true; + auto ret = std::ranges::move(in.begin(), in.end(), out.begin()); + assert(ret.in == in.end()); + assert(ret.out == out.end()); + assert(out[0].canMove); + assert(out[1].canMove); + assert(out[2].canMove); + } + { + std::array<OnlyForwardsMovable, 3> in {}; + std::array<OnlyForwardsMovable, 3> out {}; + out[0].next = &out[1]; + out[1].next = &out[2]; + out[0].canMove = true; + auto ret = std::ranges::move(in, out.begin()); + assert(ret.in == in.end()); + assert(ret.out == out.end()); + assert(out[0].canMove); + assert(out[1].canMove); + assert(out[2].canMove); + } + } + + { // check that iter_move is used properly + { + int a[] = {1, 2, 3, 4}; + std::array<int, 4> b; + auto ret = std::ranges::move(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4), b.data()); + assert(ret.in == a + 4); + assert(ret.out == b.data() + 4); + assert((b == std::array {42, 42, 42, 42})); + } + { + int a[] = {1, 2, 3, 4}; + std::array<int, 4> b; + auto range = std::ranges::subrange(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4)); + auto ret = std::ranges::move(range, b.data()); + assert(ret.in == a + 4); + assert(ret.out == b.data() + 4); + assert((b == std::array {42, 42, 42, 42})); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp @@ -0,0 +1,256 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// <algorithm> + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template<bidirectional_iterator I1, sentinel_for<I1> S1, bidirectional_iterator I2> +// requires indirectly_movable<I1, I2> +// constexpr ranges::move_backward_result<I1, I2> +// ranges::move_backward(I1 first, S1 last, I2 result); +// template<bidirectional_range R, bidirectional_iterator I> +// requires indirectly_movable<iterator_t<R>, I> +// constexpr ranges::move_backward_result<borrowed_iterator_t<R>, I> +// ranges::move_backward(R&& r, I result); + +#include <algorithm> +#include <array> +#include <cassert> +#include <ranges> + +#include "almost_satisfies_types.h" +#include "MoveOnly.h" +#include "test_iterators.h" + +template <class In, class Out = In, class Sent = sentinel_wrapper<In>> +concept HasMoveBackwardIt = requires(In in, Sent sent, Out out) { std::ranges::move_backward(in, sent, out); }; + +static_assert(HasMoveBackwardIt<int*>); +static_assert(!HasMoveBackwardIt<InputIteratorNotDerivedFrom>); +static_assert(!HasMoveBackwardIt<InputIteratorNotIndirectlyReadable>); +static_assert(!HasMoveBackwardIt<InputIteratorNotInputOrOutputIterator>); +static_assert(!HasMoveBackwardIt<int*, WeaklyIncrementableNotMovable>); +struct NotIndirectlyCopyable {}; +static_assert(!HasMoveBackwardIt<int*, NotIndirectlyCopyable*>); +static_assert(!HasMoveBackwardIt<int*, int*, SentinelForNotSemiregular>); +static_assert(!HasMoveBackwardIt<int*, int*, SentinelForNotWeaklyEqualityComparableWith>); + +template <class Range, class Out> +concept HasMoveBackwardR = requires(Range range, Out out) { std::ranges::move_backward(range, out); }; + +static_assert(HasMoveBackwardR<std::array<int, 10>, int*>); +static_assert(!HasMoveBackwardR<InputRangeNotDerivedFrom, int*>); +static_assert(!HasMoveBackwardR<InputRangeNotIndirectlyReadable, int*>); +static_assert(!HasMoveBackwardR<InputRangeNotInputOrOutputIterator, int*>); +static_assert(!HasMoveBackwardR<WeaklyIncrementableNotMovable, int*>); +static_assert(!HasMoveBackwardR<UncheckedRange<NotIndirectlyCopyable*>, int*>); +static_assert(!HasMoveBackwardR<InputRangeNotSentinelSemiregular, int*>); +static_assert(!HasMoveBackwardR<InputRangeNotSentinelEqualityComparableWith, int*>); +static_assert(!HasMoveBackwardR<UncheckedRange<int*>, WeaklyIncrementableNotMovable>); + +static_assert(std::is_same_v<std::ranges::copy_result<int, long>, std::ranges::in_out_result<int, long>>); + +template <class In, class Out, class Sent, int N> +constexpr void test(std::array<int, N> in) { + { + std::array<int, N> out; + std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret = + std::ranges::move_backward(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data() + out.size())); + assert(in == out); + assert(base(ret.in) == in.data()); + assert(base(ret.out) == out.data()); + } + { + std::array<int, N> out; + auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size()))); + std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret = + std::ranges::move_backward(range, Out(out.data() + out.size())); + assert(in == out); + assert(base(ret.in) == in.data()); + assert(base(ret.out) == out.data()); + } +} + +template <class In, class Out, class Sent = In> +constexpr void test_iterators() { + // simple test + test<In, Out, Sent, 4>({1, 2, 3, 4}); + // check that an empty range works + test<In, Out, Sent, 0>({}); +} + +template <class Out> +constexpr void test_in_iterators() { + test_iterators<bidirectional_iterator<int*>, Out, sentinel_wrapper<bidirectional_iterator<int*>>>(); + test_iterators<bidirectional_iterator<int*>, Out>(); + test_iterators<random_access_iterator<int*>, Out>(); + test_iterators<contiguous_iterator<int*>, Out>(); +} + +struct IteratorWithMoveIter { + using value_type = int; + using difference_type = int; + explicit IteratorWithMoveIter() = default; + int* ptr; + constexpr IteratorWithMoveIter(int* ptr_) : ptr(ptr_) {} + + constexpr int& operator*() const; // iterator with iter_move should not be dereferenced + + constexpr IteratorWithMoveIter& operator++() { ++ptr; return *this; } + constexpr IteratorWithMoveIter operator++(int) { auto ret = *this; ++*this; return ret; } + + constexpr IteratorWithMoveIter& operator--() { --ptr; return *this; } + constexpr IteratorWithMoveIter operator--(int) { auto ret = *this; --*this; return ret; } + + friend constexpr int iter_move(const IteratorWithMoveIter&) { return 42; } + + constexpr bool operator==(const IteratorWithMoveIter& other) const = default; +}; + +constexpr bool test() { + test_in_iterators<bidirectional_iterator<int*>>(); + test_in_iterators<random_access_iterator<int*>>(); + test_in_iterators<contiguous_iterator<int*>>(); + + { // check that a move-only type works + { + MoveOnly a[] = {1, 2, 3}; + MoveOnly b[3]; + std::ranges::move_backward(a, std::end(b)); + assert(b[0].get() == 1); + assert(b[1].get() == 2); + assert(b[2].get() == 3); + } + { + MoveOnly a[] = {1, 2, 3}; + MoveOnly b[3]; + std::ranges::move_backward(std::begin(a), std::end(a), std::end(b)); + assert(b[0].get() == 1); + assert(b[1].get() == 2); + assert(b[2].get() == 3); + } + } + + { // check that ranges::dangling is returned + std::array<int, 4> out; + std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> auto ret = + std::ranges::move_backward(std::array {1, 2, 3, 4}, out.data() + out.size()); + assert(ret.out == out.data()); + assert((out == std::array{1, 2, 3, 4})); + } + + { // check that an iterator is returned with a borrowing range + std::array in {1, 2, 3, 4}; + std::array<int, 4> out; + std::same_as<std::ranges::in_out_result<int*, int*>> auto ret = + std::ranges::move_backward(std::views::all(in), out.data() + out.size()); + assert(ret.in == in.data()); + assert(ret.out == out.data()); + assert(in == out); + } + + { // check that every element is moved exactly once + struct MoveOnce { + bool moved = false; + constexpr MoveOnce() = default; + constexpr MoveOnce(const MoveOnce& other) = delete; + constexpr MoveOnce& operator=(const MoveOnce& other) { + assert(!other.moved); + moved = true; + return *this; + } + }; + { + std::array<MoveOnce, 4> in {}; + std::array<MoveOnce, 4> out {}; + auto ret = std::ranges::move_backward(in.begin(), in.end(), out.end()); + assert(ret.in == in.begin()); + assert(ret.out == out.begin()); + assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; })); + } + { + std::array<MoveOnce, 4> in {}; + std::array<MoveOnce, 4> out {}; + auto ret = std::ranges::move_backward(in, out.end()); + assert(ret.in == in.begin()); + assert(ret.out == out.begin()); + assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; })); + } + } + + { // check that the range is moved backwards + struct OnlyBackwardsMovable { + OnlyBackwardsMovable* next = nullptr; + bool canMove = false; + OnlyBackwardsMovable() = default; + constexpr OnlyBackwardsMovable& operator=(const OnlyBackwardsMovable&) { + assert(canMove); + if (next != nullptr) + next->canMove = true; + return *this; + } + }; + { + std::array<OnlyBackwardsMovable, 3> in {}; + std::array<OnlyBackwardsMovable, 3> out {}; + out[1].next = &out[0]; + out[2].next = &out[1]; + out[2].canMove = true; + auto ret = std::ranges::move_backward(in, out.end()); + assert(ret.in == in.begin()); + assert(ret.out == out.begin()); + assert(out[0].canMove); + assert(out[1].canMove); + assert(out[2].canMove); + } + { + std::array<OnlyBackwardsMovable, 3> in {}; + std::array<OnlyBackwardsMovable, 3> out {}; + out[1].next = &out[0]; + out[2].next = &out[1]; + out[2].canMove = true; + auto ret = std::ranges::move_backward(in.begin(), in.end(), out.end()); + assert(ret.in == in.begin()); + assert(ret.out == out.begin()); + assert(out[0].canMove); + assert(out[1].canMove); + assert(out[2].canMove); + } + } + + { // check that iter_move is used properly + { + int a[] = {1, 2, 3, 4}; + std::array<int, 4> b; + auto ret = std::ranges::move_backward(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4), b.data() + b.size()); + assert(ret.in == a); + assert(ret.out == b.data()); + assert((b == std::array {42, 42, 42, 42})); + } + { + int a[] = {1, 2, 3, 4}; + std::array<int, 4> b; + auto range = std::ranges::subrange(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4)); + auto ret = std::ranges::move_backward(range, b.data() + b.size()); + assert(ret.in == a); + assert(ret.out == b.data()); + assert((b == std::array {42, 42, 42, 42})); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -104,8 +104,8 @@ static_assert(test(std::ranges::minmax, a)); static_assert(test(std::ranges::minmax_element, a)); static_assert(test(std::ranges::mismatch, a, a)); -//static_assert(test(std::ranges::move, a, a)); -//static_assert(test(std::ranges::move_backward, a, a)); +static_assert(test(std::ranges::move, a, a)); +static_assert(test(std::ranges::move_backward, a, a)); //static_assert(test(std::ranges::next_permutation, a)); static_assert(test(std::ranges::none_of, a, odd)); //static_assert(test(std::ranges::nth_element, a, a+5));