diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -9,6 +9,7 @@ __algorithm/copy.h __algorithm/copy_backward.h __algorithm/copy_if.h + __algorithm/copy_move_common.h __algorithm/copy_n.h __algorithm/count.h __algorithm/count_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 @@ -9,15 +9,11 @@ #ifndef _LIBCPP___ALGORITHM_COPY_H #define _LIBCPP___ALGORITHM_COPY_H -#include <__algorithm/unwrap_iter.h> -#include <__algorithm/unwrap_range.h> +#include <__algorithm/copy_move_common.h> +#include <__algorithm/iterator_operations.h> #include <__config> -#include <__iterator/iterator_traits.h> -#include <__iterator/reverse_iterator.h> #include <__utility/move.h> #include <__utility/pair.h> -#include -#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -25,82 +21,42 @@ _LIBCPP_BEGIN_NAMESPACE_STD -// copy +struct __copy_loop { + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result) const { + while (__first != __last) { + *__result = *__first; + ++__first; + ++__result; + } -template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -pair<_InIter, _OutIter> __copy_impl(_InIter __first, _Sent __last, _OutIter __result) { - while (__first != __last) { - *__result = *__first; - ++__first; - ++__result; + return std::make_pair(std::move(__first), std::move(__result)); } - return pair<_InIter, _OutIter>(std::move(__first), std::move(__result)); -} +}; -template , _OutValueT>::value - && is_trivially_copy_assignable<_OutValueT>::value> > -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -pair<_InValueT*, _OutValueT*> __copy_impl(_InValueT* __first, _InValueT* __last, _OutValueT* __result) { - if (__libcpp_is_constant_evaluated() -// TODO: Remove this once GCC supports __builtin_memmove during constant evaluation -#ifndef _LIBCPP_COMPILER_GCC - && !is_trivially_copyable<_InValueT>::value -#endif - ) - return std::__copy_impl<_InValueT*, _InValueT*, _OutValueT*>(__first, __last, __result); - const size_t __n = static_cast(__last - __first); - if (__n > 0) - ::__builtin_memmove(__result, __first, __n * sizeof(_OutValueT)); - return std::make_pair(__first + __n, __result + __n); -} +struct __copy_trivial { + // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer. + template = 0> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> + operator()(_In* __first, _In* __last, _Out* __result) const { + return std::__copy_trivial_impl(__first, __last, __result); + } +}; -template >, __iter_value_type<_OutIter> >::value - && __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_SINCE_CXX14 +template 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, _OutIter(std::__rewrap_iter(__result.base(), __result_first))); -} - -template ::value - && is_copy_constructible<_Sent>::value - && is_copy_constructible<_OutIter>::value), int> = 0 > -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) { - return std::__copy_impl(std::move(__first), std::move(__last), std::move(__result)); -} - -template ::value - && is_copy_constructible<_Sent>::value - && is_copy_constructible<_OutIter>::value, int> = 0> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) { - auto __range = std::__unwrap_range(__first, __last); - auto __ret = std::__copy_impl(std::move(__range.first), std::move(__range.second), std::__unwrap_iter(__result)); - return std::make_pair( - std::__rewrap_range<_Sent>(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); +__copy(_InIter __first, _Sent __last, _OutIter __result) { + return std::__dispatch_copy_or_move<_AlgPolicy, __copy_loop, __copy_trivial>( + std::move(__first), std::move(__last), std::move(__result)); } template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return std::__copy(__first, __last, __result).second; + return std::__copy<_ClassicAlgPolicy>(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/copy_backward.h b/libcxx/include/__algorithm/copy_backward.h --- a/libcxx/include/__algorithm/copy_backward.h +++ b/libcxx/include/__algorithm/copy_backward.h @@ -9,19 +9,11 @@ #ifndef _LIBCPP___ALGORITHM_COPY_BACKWARD_H #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H -#include <__algorithm/copy.h> +#include <__algorithm/copy_move_common.h> #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 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -29,32 +21,50 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template ::value, int> = 0> -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 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 +struct __copy_backward_loop { + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result) const { + auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last); + auto __original_last_iter = __last_iter; + + while (__first != __last_iter) { + *--__result = *--__last_iter; + } + + return std::make_pair(std::move(__original_last_iter), std::move(__result)); + } +}; -#if _LIBCPP_STD_VER > 17 -template ::value, int> = 0> -_LIBCPP_HIDE_FROM_ABI constexpr pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) { - auto __last_iter = _IterOps<_AlgPolicy>::next(__first, std::move(__last)); - auto __reverse_range = std::__reverse_range(std::ranges::subrange(std::move(__first), __last_iter)); - auto __ret = ranges::copy(std::move(__reverse_range), std::make_reverse_iterator(__result)); - return std::make_pair(__last_iter, __ret.out.base()); +struct __copy_backward_trivial { + // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer. + template = 0> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> + operator()(_In* __first, _In* __last, _Out* __result) const { + return std::__copy_backward_trivial_impl(__first, __last, __result); + } +}; + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 +pair<_BidirectionalIterator1, _BidirectionalIterator2> +__copy_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) { + return std::__dispatch_copy_or_move<_AlgPolicy, __copy_backward_loop<_AlgPolicy>, __copy_backward_trivial>( + std::move(__first), std::move(__last), std::move(__result)); } -#endif // _LIBCPP_STD_VER > 17 template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _BidirectionalIterator2 -copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result).second; +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 +_BidirectionalIterator2 +copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, + _BidirectionalIterator2 __result) +{ + static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value && + std::is_copy_constructible<_BidirectionalIterator1>::value, "Iterators must be copy constructible."); + + return std::__copy_backward<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), std::move(__result)).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/copy_move_common.h b/libcxx/include/__algorithm/copy_move_common.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/copy_move_common.h @@ -0,0 +1,152 @@ +//===----------------------------------------------------------------------===// +// +// 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_COPY_MOVE_COMMON_H +#define _LIBCPP___ALGORITHM_COPY_MOVE_COMMON_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/unwrap_iter.h> +#include <__algorithm/unwrap_range.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__memory/pointer_traits.h> +#include <__type_traits/enable_if.h> +#include <__type_traits/integral_constant.h> +#include <__type_traits/is_constant_evaluated.h> +#include <__type_traits/is_copy_constructible.h> +#include <__type_traits/is_trivially_assignable.h> +#include <__type_traits/remove_reference.h> +#include <__utility/move.h> +#include <__utility/pair.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +// Type trait. +template , + class _Out = __libcpp_remove_reference_t<_OutRef>> +using __enable_if_memmovable = __enable_if_t< + sizeof(_In) == sizeof(_Out) && + is_trivially_assignable<_OutRef, _InRef>::value && + (std::is_same<_In, _Out>::value || ( + std::is_integral<_In>::value && + std::is_integral<_Out>::value && + !std::is_same<_In, bool>::value && + !std::is_same<_Out, bool>::value)) +, int>; + +// `memmove` algorithms implementation. + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> +__copy_trivial_impl(_In* __first, _In* __last, _Out* __result) { + const size_t __n = static_cast(__last - __first); + ::__builtin_memmove(__result, __first, __n * sizeof(_Out)); + + return std::make_pair(__last, __result + __n); +} + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> +__copy_backward_trivial_impl(_In* __first, _In* __last, _Out* __result) { + const size_t __n = static_cast(__last - __first); + __result -= __n; + + ::__builtin_memmove(__result, __first, __n * sizeof(_Out)); + + return std::make_pair(__last, __result); +} + +// Iterator unwrapping and dispatching to the correct overload. + +template +struct __overload : _F1, _F2 { + using _F1::operator(); + using _F2::operator(); +}; + +template +struct __can_rewrap : false_type {}; + +template +struct __can_rewrap<_InIter, + _Sent, + _OutIter, + // Note that sentinels are always copy-constructible. + __enable_if_t< is_copy_constructible<_InIter>::value && + is_copy_constructible<_OutIter>::value > > : true_type {}; + +template ::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 pair<_InIter, _OutIter> +__unwrap_and_dispatch(_InIter __first, _Sent __last, _OutIter __out_first) { + auto __range = std::__unwrap_range(__first, std::move(__last)); + auto __result = _Algorithm()(std::move(__range.first), std::move(__range.second), std::__unwrap_iter(__out_first)); + return std::make_pair(std::__rewrap_range<_Sent>(std::move(__first), std::move(__result.first)), + std::__rewrap_iter(std::move(__out_first), std::move(__result.second))); +} + +template ::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 pair<_InIter, _OutIter> +__unwrap_and_dispatch(_InIter __first, _Sent __last, _OutIter __out_first) { + return _Algorithm()(std::move(__first), std::move(__last), std::move(__out_first)); +} + +template +struct __can_copy_without_conversion : false_type {}; + +template +struct __can_copy_without_conversion< + _IterOps, + _InValue, + _OutIter, + __enable_if_t >::value> > : true_type {}; + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 pair<_InIter, _OutIter> +__dispatch_copy_or_move(_InIter __first, _Sent __last, _OutIter __out_first) { +#ifdef _LIBCPP_COMPILER_GCC + // GCC doesn't support `__builtin_memmove` during constant evaluation. + if (__libcpp_is_constant_evaluated()) { + return std::__unwrap_and_dispatch<_NaiveAlgorithm>(std::move(__first), std::move(__last), std::move(__out_first)); + } +#else + // In Clang, `__builtin_memmove` only supports fully trivially copyable types (just having trivial copy assignment is + // insufficient). Also, conversions are not supported. + if (__libcpp_is_constant_evaluated()) { + using _InValue = typename _IterOps<_AlgPolicy>::template __value_type<_InIter>; + if (!is_trivially_copyable<_InValue>::value || + !__can_copy_without_conversion<_IterOps<_AlgPolicy>, _InValue, _OutIter>::value) { + return std::__unwrap_and_dispatch<_NaiveAlgorithm>(std::move(__first), std::move(__last), std::move(__out_first)); + } + } +#endif // _LIBCPP_COMPILER_GCC + + using _Algorithm = __overload<_NaiveAlgorithm, _OptimizedAlgorithm>; + return std::__unwrap_and_dispatch<_Algorithm>(std::move(__first), std::move(__last), std::move(__out_first)); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_COPY_MOVE_COMMON_H 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 @@ -9,15 +9,11 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_H #define _LIBCPP___ALGORITHM_MOVE_H +#include <__algorithm/copy_move_common.h> #include <__algorithm/iterator_operations.h> -#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 -#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -25,93 +21,45 @@ _LIBCPP_BEGIN_NAMESPACE_STD -// move - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17 -pair<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { - while (__first != __last) { - *__result = _IterOps<_AlgPolicy>::__iter_move(__first); - ++__first; - ++__result; +template +struct __move_loop { + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result) const { + while (__first != __last) { + *__result = _IterOps<_AlgPolicy>::__iter_move(__first); + ++__first; + ++__result; + } + return std::make_pair(std::move(__first), std::move(__result)); } - return std::make_pair(std::move(__first), std::move(__result)); -} - -template , _OutType>::value - && is_trivially_move_assignable<_OutType>::value> > -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -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<_AlgPolicy, _InType*, _InType*, _OutType*>(__first, __last, __result); - const size_t __n = static_cast(__last - __first); - ::__builtin_memmove(__result, __first, __n * sizeof(_OutType)); - return std::make_pair(__first + __n, __result + __n); -} - -template -struct __is_trivially_move_assignable_unwrapped_impl : false_type {}; - -template -struct __is_trivially_move_assignable_unwrapped_impl<_Type*> : is_trivially_move_assignable<_Type> {}; - -template -struct __is_trivially_move_assignable_unwrapped - : __is_trivially_move_assignable_unwrapped_impl(std::declval<_Iter>()))> {}; - -template ::value_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_SINCE_CXX17 -pair, 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<_AlgPolicy>(__last_base, __first_base, __result_first); - return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); -} - -template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -__enable_if_t::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<_AlgPolicy>( - 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)); -} +}; + +struct __move_trivial { + // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer. + template = 0> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> + operator()(_In* __first, _In* __last, _Out* __result) const { + return std::__copy_trivial_impl(__first, __last, __result); + } +}; template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -__enable_if_t::value - || !is_copy_constructible<_Sent>::value - || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > +pair<_InIter, _OutIter> __move(_InIter __first, _Sent __last, _OutIter __result) { - return std::__move_impl<_AlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); + return std::__dispatch_copy_or_move<_AlgPolicy, __move_loop<_AlgPolicy>, __move_trivial>( + std::move(__first), std::move(__last), std::move(__result)); } template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return std::__move<_ClassicAlgPolicy>(__first, __last, __result).second; + static_assert(is_copy_constructible<_InputIterator>::value, "Iterators has to be copy constructible."); + static_assert(is_copy_constructible<_OutputIterator>::value, "The output iterator has to be copy constructible."); + + return std::__move<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), std::move(__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,12 +9,11 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_BACKWARD_H #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H +#include <__algorithm/copy_move_common.h> #include <__algorithm/iterator_operations.h> -#include <__algorithm/unwrap_iter.h> #include <__config> #include <__utility/move.h> -#include -#include +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -22,57 +21,40 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17 -_OutputIterator -__move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - while (__first != __last) - *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last); - return __result; -} +template +struct __move_backward_loop { + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result) const { + auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last); + auto __original_last_iter = __last_iter; -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17 -_OutputIterator -__move_backward_impl(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result); -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17 -typename enable_if -< - is_same<__remove_const_t<_Tp>, _Up>::value && - is_trivially_move_assignable<_Up>::value, - _Up* ->::type -__move_backward_impl(_Tp* __first, _Tp* __last, _Up* __result) -{ - const size_t __n = static_cast(__last - __first); - if (__n > 0) - { - __result -= __n; - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + while (__first != __last_iter) { + *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last_iter); } - return __result; -} -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 -_BidirectionalIterator2 -__move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, - _BidirectionalIterator2 __result) -{ - if (__libcpp_is_constant_evaluated()) { - return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result); - } else { - return _VSTD::__rewrap_iter(__result, - _VSTD::__move_backward_impl<_AlgPolicy>(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); - } + return std::make_pair(std::move(__original_last_iter), std::move(__result)); + } +}; + +struct __move_backward_trivial { + // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer. + template = 0> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> + operator()(_In* __first, _In* __last, _Out* __result) const { + return std::__copy_backward_trivial_impl(__first, __last, __result); + } +}; + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 +pair<_BidirectionalIterator1, _BidirectionalIterator2> +__move_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) { + static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value && + std::is_copy_constructible<_BidirectionalIterator1>::value, "Iterators must be copy constructible."); + + return std::__dispatch_copy_or_move<_AlgPolicy, __move_backward_loop<_AlgPolicy>, __move_backward_trivial>( + std::move(__first), std::move(__last), std::move(__result)); } template @@ -81,7 +63,8 @@ move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - return std::__move_backward<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); + return std::__move_backward<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), std::move(__result)).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_copy.h b/libcxx/include/__algorithm/ranges_copy.h --- a/libcxx/include/__algorithm/ranges_copy.h +++ b/libcxx/include/__algorithm/ranges_copy.h @@ -11,6 +11,7 @@ #include <__algorithm/copy.h> #include <__algorithm/in_out_result.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__functional/identity.h> #include <__iterator/concepts.h> @@ -40,7 +41,7 @@ requires indirectly_copyable<_InIter, _OutIter> _LIBCPP_HIDE_FROM_ABI constexpr copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { - auto __ret = std::__copy(std::move(__first), std::move(__last), std::move(__result)); + auto __ret = std::__copy<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } @@ -48,7 +49,7 @@ requires indirectly_copyable, _OutIter> _LIBCPP_HIDE_FROM_ABI constexpr copy_result, _OutIter> operator()(_Range&& __r, _OutIter __result) const { - auto __ret = std::__copy(ranges::begin(__r), ranges::end(__r), std::move(__result)); + auto __ret = std::__copy<_RangeAlgPolicy>(ranges::begin(__r), ranges::end(__r), std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } }; 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 @@ -14,7 +14,6 @@ #include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/concepts.h> -#include <__iterator/reverse_iterator.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/dangling.h> diff --git a/libcxx/include/__algorithm/ranges_copy_n.h b/libcxx/include/__algorithm/ranges_copy_n.h --- a/libcxx/include/__algorithm/ranges_copy_n.h +++ b/libcxx/include/__algorithm/ranges_copy_n.h @@ -11,6 +11,7 @@ #include <__algorithm/copy.h> #include <__algorithm/in_out_result.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/ranges_copy.h> #include <__config> #include <__functional/identity.h> @@ -51,7 +52,7 @@ template _LIBCPP_HIDE_FROM_ABI constexpr static copy_n_result<_InIter, _OutIter> __go(_InIter __first, _DiffType __n, _OutIter __result) { - auto __ret = std::__copy(__first, __first + __n, __result); + auto __ret = std::__copy<_RangeAlgPolicy>(__first, __first + __n, __result); return {__ret.first, __ret.second}; } diff --git a/libcxx/include/__algorithm/ranges_move.h b/libcxx/include/__algorithm/ranges_move.h --- a/libcxx/include/__algorithm/ranges_move.h +++ b/libcxx/include/__algorithm/ranges_move.h @@ -14,7 +14,6 @@ #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> diff --git a/libcxx/include/__algorithm/ranges_move_backward.h b/libcxx/include/__algorithm/ranges_move_backward.h --- a/libcxx/include/__algorithm/ranges_move_backward.h +++ b/libcxx/include/__algorithm/ranges_move_backward.h @@ -10,12 +10,12 @@ #define _LIBCPP___ALGORITHM_RANGES_MOVE_BACKWARD_H #include <__algorithm/in_out_result.h> -#include <__algorithm/ranges_move.h> +#include <__algorithm/iterator_operations.h> +#include <__algorithm/move_backward.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> @@ -40,11 +40,8 @@ template _LIBCPP_HIDE_FROM_ABI constexpr static move_backward_result<_InIter, _OutIter> __move_backward_impl(_InIter __first, _Sent __last, _OutIter __result) { - auto __last_iter = ranges::next(__first, std::move(__last)); - auto __ret = ranges::move(std::make_reverse_iterator(__last_iter), - std::make_reverse_iterator(__first), - std::make_reverse_iterator(__result)); - return {std::move(__last_iter), std::move(__ret.out.base())}; + auto __ret = std::__move_backward<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); + return {std::move(__ret.first), std::move(__ret.second)}; } template _Sent, bidirectional_iterator _OutIter> diff --git a/libcxx/include/__algorithm/rotate.h b/libcxx/include/__algorithm/rotate.h --- a/libcxx/include/__algorithm/rotate.h +++ b/libcxx/include/__algorithm/rotate.h @@ -48,9 +48,9 @@ _BidirectionalIterator __lm1 = _Ops::prev(__last); value_type __tmp = _Ops::__iter_move(__lm1); - _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)); + auto __res = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)); *__first = _VSTD::move(__tmp); - return __fp1; + return __res.first; } template diff --git a/libcxx/include/__algorithm/set_symmetric_difference.h b/libcxx/include/__algorithm/set_symmetric_difference.h --- a/libcxx/include/__algorithm/set_symmetric_difference.h +++ b/libcxx/include/__algorithm/set_symmetric_difference.h @@ -41,7 +41,7 @@ _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) { while (__first1 != __last1) { if (__first2 == __last2) { - auto __ret1 = std::__copy_impl(std::move(__first1), std::move(__last1), std::move(__result)); + auto __ret1 = std::__copy(std::move(__first1), std::move(__last1), std::move(__result)); return __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>( std::move(__ret1.first), std::move(__first2), std::move((__ret1.second))); } @@ -59,7 +59,7 @@ ++__first2; } } - auto __ret2 = std::__copy_impl(std::move(__first2), std::move(__last2), std::move(__result)); + auto __ret2 = std::__copy(std::move(__first2), std::move(__last2), std::move(__result)); return __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>( std::move(__first1), std::move(__ret2.first), std::move((__ret2.second))); } diff --git a/libcxx/include/__algorithm/set_union.h b/libcxx/include/__algorithm/set_union.h --- a/libcxx/include/__algorithm/set_union.h +++ b/libcxx/include/__algorithm/set_union.h @@ -40,7 +40,7 @@ _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) { for (; __first1 != __last1; ++__result) { if (__first2 == __last2) { - auto __ret1 = std::__copy_impl(std::move(__first1), std::move(__last1), std::move(__result)); + auto __ret1 = std::__copy(std::move(__first1), std::move(__last1), std::move(__result)); return __set_union_result<_InIter1, _InIter2, _OutIter>( std::move(__ret1.first), std::move(__first2), std::move((__ret1.second))); } @@ -55,7 +55,7 @@ ++__first1; } } - auto __ret2 = std::__copy_impl(std::move(__first2), std::move(__last2), std::move(__result)); + auto __ret2 = std::__copy(std::move(__first2), std::move(__last2), std::move(__result)); return __set_union_result<_InIter1, _InIter2, _OutIter>( std::move(__first1), std::move(__ret2.first), std::move((__ret2.second))); } 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 @@ -251,6 +251,7 @@ module copy { private header "__algorithm/copy.h" } module copy_backward { private header "__algorithm/copy_backward.h" } module copy_if { private header "__algorithm/copy_if.h" } + module copy_move_common { private header "__algorithm/copy_move_common.h" } module copy_n { private header "__algorithm/copy_n.h" } module count { private header "__algorithm/count.h" } module count_if { private header "__algorithm/count_if.h" } diff --git a/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_nontrivial.pass.cpp b/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_nontrivial.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_nontrivial.pass.cpp @@ -0,0 +1,265 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=2000000 + +// + +#include +#include + +// These tests checks that `std::copy` and `std::move` (including their variations like `copy_n`) don't forward to +// `std::memmove` when doing so would be observable. + +// This template is a better match than the actual `builtin_memmove` (it can match the pointer type exactly, without an +// implicit conversion to `void*`), so it should hijack the call inside `std::copy` and similar algorithms if it's made. +template +constexpr void* __builtin_memmove(Dst*, Src*, size_t) { + assert(false); + return nullptr; +} + +#include +#include +#include +#include +#include + +#include "test_iterators.h" +#include "test_macros.h" + +template +requires (N == 0) +constexpr auto wrap_n_times(Iter i) { + return i; +} + +template +requires (N != 0) +constexpr auto wrap_n_times(Iter i) { + return std::make_reverse_iterator(wrap_n_times(i)); +} + +static_assert(std::is_same_v(std::declval())), + std::reverse_iterator>>); + +struct NonTrivialMoveAssignment { + int i; + + constexpr NonTrivialMoveAssignment() = default; + constexpr NonTrivialMoveAssignment(int set_i) : i(set_i) {} + + constexpr NonTrivialMoveAssignment(NonTrivialMoveAssignment&& rhs) = default; + constexpr NonTrivialMoveAssignment& operator=(NonTrivialMoveAssignment&& rhs) noexcept { + i = rhs.i; + return *this; + } + + constexpr friend bool operator==(const NonTrivialMoveAssignment&, const NonTrivialMoveAssignment&) = default; +}; + +static_assert(!std::is_trivially_move_assignable_v); +static_assert(!std::is_trivially_assignable::value); + +struct NonTrivialMoveCtr { + int i; + + constexpr NonTrivialMoveCtr() = default; + constexpr NonTrivialMoveCtr(int set_i) : i(set_i) {} + + constexpr NonTrivialMoveCtr(NonTrivialMoveCtr&& rhs) noexcept : i(rhs.i) {} + constexpr NonTrivialMoveCtr& operator=(NonTrivialMoveCtr&& rhs) = default; + + constexpr friend bool operator==(const NonTrivialMoveCtr&, const NonTrivialMoveCtr&) = default; +}; + +static_assert(std::is_trivially_move_assignable_v); +static_assert(!std::is_trivially_copyable_v); + +struct NonTrivialCopyAssignment { + int i; + + constexpr NonTrivialCopyAssignment() = default; + constexpr NonTrivialCopyAssignment(int set_i) : i(set_i) {} + + constexpr NonTrivialCopyAssignment(const NonTrivialCopyAssignment& rhs) = default; + constexpr NonTrivialCopyAssignment& operator=(const NonTrivialCopyAssignment& rhs) { + i = rhs.i; + return *this; + } + + constexpr friend bool operator==(const NonTrivialCopyAssignment&, const NonTrivialCopyAssignment&) = default; +}; + +static_assert(!std::is_trivially_copy_assignable_v); + +struct NonTrivialCopyCtr { + int i; + + constexpr NonTrivialCopyCtr() = default; + constexpr NonTrivialCopyCtr(int set_i) : i(set_i) {} + + constexpr NonTrivialCopyCtr(const NonTrivialCopyCtr& rhs) : i(rhs.i) {} + constexpr NonTrivialCopyCtr& operator=(const NonTrivialCopyCtr& rhs) = default; + + constexpr friend bool operator==(const NonTrivialCopyCtr&, const NonTrivialCopyCtr&) = default; +}; + +static_assert(std::is_trivially_copy_assignable_v); +static_assert(!std::is_trivially_copyable_v); + +template class SentWrapper, class OutIter, size_t W1, size_t W2, class Func> +constexpr void test_one(Func func) { + using From = typename std::iterator_traits::value_type; + using To = typename std::iterator_traits::value_type; + + { + const size_t N = 4; + + From input[N] = {From(1), From(2), From(3), From(4)}; + To output[N]; + + auto in = wrap_n_times(InIter(input)); + auto in_end = wrap_n_times(InIter(input + N)); + auto sent = SentWrapper(in_end); + auto out = wrap_n_times(OutIter(output)); + + func(in, sent, out, N); + if constexpr (!std::same_as) { + assert(std::equal(input, input + N, output)); + } else { + assert(std::all_of(output, output + N, [](bool e) { return e; })); + } + } + + { + const size_t N = 0; + + From input[1] = {1}; + To output[1] = {To(2)}; + + auto in = wrap_n_times(InIter(input)); + auto in_end = wrap_n_times(InIter(input + N)); + auto sent = SentWrapper(in_end); + auto out = wrap_n_times(OutIter(output)); + + func(in, sent, out, N); + assert(output[0] == To(2)); + } +} + +template class SentWrapper, class OutIter, size_t W1, size_t W2> +constexpr void test_copy() { + // Classic. + if constexpr (std::same_as>) { + test_one([](auto first, auto last, auto out, size_t) { + std::copy(first, last, out); + }); + test_one([](auto first, auto last, auto out, size_t n) { + std::copy_backward(first, last, out + n); + }); + test_one([](auto first, auto, auto out, size_t n) { + std::copy_n(first, n, out); + }); + } + + // Ranges. + test_one([](auto first, auto last, auto out, size_t) { + std::ranges::copy(first, last, out); + }); + test_one([](auto first, auto last, auto out, size_t n) { + std::ranges::copy_backward(first, last, out + n); + }); + test_one([](auto first, auto, auto out, size_t n) { + std::ranges::copy_n(first, n, out); + }); +} + +template class SentWrapper, class OutIter, size_t W1, size_t W2> +constexpr void test_move() { + if constexpr (std::same_as>) { + test_one([](auto first, auto last, auto out, size_t) { + std::move(first, last, out); + }); + test_one([](auto first, auto last, auto out, size_t n) { + std::move_backward(first, last, out + n); + }); + } + + // Ranges. + test_one([](auto first, auto last, auto out, size_t) { + std::ranges::move(first, last, out); + }); + test_one([](auto first, auto last, auto out, size_t n) { + std::ranges::move_backward(first, last, out + n); + }); +} + +template +constexpr void test_copy_with_type() { + using FromIter = contiguous_iterator; + using ToIter = contiguous_iterator; + + test_copy(); + test_copy(); + test_copy(); + test_copy(); + test_copy(); +} + +template +constexpr void test_move_with_type() { + using FromIter = contiguous_iterator; + using ToIter = contiguous_iterator; + + test_move(); + test_move(); + test_move(); + test_move(); + test_move(); +} + +template +constexpr void test_both_directions() { + test_copy_with_type(); + test_move_with_type(); + test_copy_with_type(); + test_move_with_type(); +} + +template +constexpr void test_copy_and_move() { + test_copy_with_type(); + test_move_with_type(); + + // Copying from a smaller type into a larger type and vice versa. + test_both_directions(); + // Copying between types with different representations. + test_both_directions(); + test_both_directions(); +} + +constexpr bool test() { + test_copy_and_move<0, 0>(); + test_copy_and_move<0, 2>(); + test_copy_and_move<2, 0>(); + test_copy_and_move<2, 2>(); + test_copy_and_move<2, 4>(); + test_copy_and_move<4, 4>(); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_trivial.pass.cpp b/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_trivial.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_trivial.pass.cpp @@ -0,0 +1,200 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17 +// When the debug mode is enabled, we don't unwrap iterators in `std::copy` and similar algorithms so we don't get this +// optimization. +// UNSUPPORTED: libcpp-has-debug-mode +// In the modules build, adding another overload of `memmove` doesn't work. +// UNSUPPORTED: modules-build +// GCC complains about "ambiguating" `__builtin_memmove`. +// UNSUPPORTED: gcc + +// + +// These tests checks that `std::copy` and `std::move` (including their variations like `copy_n`) forward to +// `memmove` when possible. + +#include + +struct Foo { + int i = 0; + + Foo() = default; + Foo(int set_i) : i(set_i) {} + + friend bool operator==(const Foo&, const Foo&) = default; +}; + +static bool memmove_called = false; + +// This template is a better match than the actual `builtin_memmove` (it can match the pointer type exactly, without an +// implicit conversion to `void*`), so it should hijack the call inside `std::copy` and similar algorithms if it's made. +template +constexpr void* __builtin_memmove(Dst* dst, Src* src, size_t count) { + memmove_called = true; + return __builtin_memmove(static_cast(dst), static_cast(src), count); +} + +#include +#include +#include +#include +#include +#include + +#include "test_iterators.h" + +static_assert(std::is_trivially_copyable_v); + +template +requires (N == 0) +constexpr auto wrap_n_times(Iter i) { + return i; +} + +template +requires (N != 0) +constexpr auto wrap_n_times(Iter i) { + return std::make_reverse_iterator(wrap_n_times(i)); +} + +static_assert(std::is_same_v(std::declval())), + std::reverse_iterator>>); + +template class SentWrapper, class OutIter, size_t W1, size_t W2, class Func> +void test_one(Func func) { + using From = std::iter_value_t; + using To = std::iter_value_t; + + // Normal case. + { + const size_t N = 4; + + From input[N] = {{1}, {2}, {3}, {4}}; + To output[N]; + + auto in = wrap_n_times(InIter(input)); + auto in_end = wrap_n_times(InIter(input + N)); + auto sent = SentWrapper(in_end); + auto out = wrap_n_times(OutIter(output)); + + assert(!memmove_called); + func(in, sent, out, N); + assert(memmove_called); + memmove_called = false; + + assert(std::equal(input, input + N, output, [](const From& lhs, const To& rhs) { + // Prevents warnings/errors due to mismatched signed-ness. + return lhs == static_cast(rhs); + })); + } + + // Empty input sequence. + { + const size_t N = 0; + + From input[1] = {1}; + To output[1] = {2}; + + auto in = wrap_n_times(InIter(input)); + auto in_end = wrap_n_times(InIter(input + N)); + auto sent = SentWrapper(in_end); + auto out = wrap_n_times(OutIter(output)); + + assert(!memmove_called); + func(in, sent, out, N); + + assert(output[0] == To{2}); + assert(memmove_called); + memmove_called = false; + } +} + +template class SentWrapper, class OutIter, size_t W1, size_t W2> +void test_copy_and_move() { + // Classic. + if constexpr (std::same_as>) { + test_one([](auto first, auto last, auto out, size_t) { + std::copy(first, last, out); + }); + test_one([](auto first, auto last, auto out, size_t n) { + std::copy_backward(first, last, out + n); + }); + test_one([](auto first, auto, auto out, size_t n) { + std::copy_n(first, n, out); + }); + test_one([](auto first, auto last, auto out, size_t) { + std::move(first, last, out); + }); + test_one([](auto first, auto last, auto out, size_t n) { + std::move_backward(first, last, out + n); + }); + } + + // Ranges. + test_one([](auto first, auto last, auto out, size_t) { + std::ranges::copy(first, last, out); + }); + test_one([](auto first, auto last, auto out, size_t n) { + std::ranges::copy_backward(first, last, out + n); + }); + test_one([](auto first, auto, auto out, size_t n) { + std::ranges::copy_n(first, n, out); + }); + test_one([](auto first, auto last, auto out, size_t) { + std::ranges::move(first, last, out); + }); + test_one([](auto first, auto last, auto out, size_t n) { + std::ranges::move_backward(first, last, out + n); + }); +} + +template class SentWrapper> +void test_all_permutations_with_counts_from_to_sent() { + test_copy_and_move(); + test_copy_and_move, SentWrapper, To*, W1, W2>(); + test_copy_and_move, W1, W2>(); + test_copy_and_move, SentWrapper, contiguous_iterator, W1, W2>(); + + if (!std::same_as) { + test_copy_and_move(); + test_copy_and_move, SentWrapper, From*, W1, W2>(); + test_copy_and_move, W1, W2>(); + test_copy_and_move, SentWrapper, contiguous_iterator, W1, W2>(); + } +} + +template +void test_all_permutations_with_counts() { + // Built-in. + test_all_permutations_with_counts_from_to_sent(); + // User-defined. + test_all_permutations_with_counts_from_to_sent(); + + // Conversions. + test_all_permutations_with_counts_from_to_sent(); + test_all_permutations_with_counts_from_to_sent(); +} + +void test() { + test_all_permutations_with_counts<0, 0>(); + test_all_permutations_with_counts<0, 2>(); + test_all_permutations_with_counts<2, 0>(); + test_all_permutations_with_counts<2, 2>(); + test_all_permutations_with_counts<2, 4>(); + test_all_permutations_with_counts<4, 4>(); +} + +int main(int, char**) { + test(); + // The test relies on a global variable, so it cannot be made `constexpr`; the `memmove` optimization is not used in + // `constexpr` mode anyway. + + 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 @@ -46,6 +46,7 @@ #include <__algorithm/copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy.h'}} #include <__algorithm/copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_backward.h'}} #include <__algorithm/copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_if.h'}} +#include <__algorithm/copy_move_common.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_move_common.h'}} #include <__algorithm/copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_n.h'}} #include <__algorithm/count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/count.h'}} #include <__algorithm/count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/count_if.h'}}