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_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,132 @@ +//===----------------------------------------------------------------------===// +// +// 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/unwrap_iter.h> +#include <__config> +#include <__utility/move.h> +#include <__utility/pair.h> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct __can_memmove : false_type {}; + +template +struct __can_memmove<_In, _Out, __enable_if_t< + is_same::type, _Out>::value && + is_trivially_move_assignable<_Out>::value && + !(__libcpp_is_constant_evaluated() + // TODO: Remove this once GCC supports __builtin_memmove during constant evaluation +#ifndef _LIBCPP_COMPILER_GCC + && !is_trivially_copyable<_In>::value +#endif + ) +> > : true_type {}; + +template +struct __trivial_copy_func { + + template ::value>> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14 static + pair<_In*, _Out*> + __run(_In* __first, _In* __last, _Out* __result) { + const size_t __n = static_cast(__last - __first); + + if (_Backward) { + if (__n == 0) { + return pair<_In*, _Out*>(__last, __result); + } + __result -= __n; + } + + ::__builtin_memmove(__result, __first, __n * sizeof(_Out)); + return pair<_In*, _Out*>(__last, _Backward ? __result : __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>::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<_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 +struct __can_unwrap : false_type {}; + +template +struct __can_unwrap<_InIter, _Sent, _OutIter, __enable_if_t< + is_copy_constructible<_InIter>::value && + is_copy_constructible<_Sent>::value && + is_copy_constructible<_OutIter>::value +> > + : true_type {}; + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14 +__enable_if_t< + __can_unwrap<_InIter, _Sent, _OutIter>::value, + pair<_InIter, _OutIter>> +__dispatch_copy_or_move(_InIter __first, _Sent __last, _OutIter __out_first) { + auto __result = _AlgImpl::__run(std::__unwrap_iter(__first), + std::__unwrap_iter(__last), + std::__unwrap_iter(__out_first)); + return pair<_InIter, _OutIter>( + std::__rewrap_iter(__first, __result.first), + std::__rewrap_iter(__out_first, __result.second)); +} + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14 +__enable_if_t< + !__can_unwrap<_InIter, _Sent, _OutIter>::value, + pair<_InIter, _OutIter>> +__dispatch_copy_or_move(_InIter __first, _Sent __last, _OutIter __out_first) { + return _AlgImpl::__run(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,14 +9,12 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_H #define _LIBCPP___ALGORITHM_MOVE_H -#include <__algorithm/unwrap_iter.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 @@ -24,90 +22,39 @@ _LIBCPP_BEGIN_NAMESPACE_STD -// move - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -pair<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { - while (__first != __last) { - *__result = std::move(*__first); - ++__first; - ++__result; +template +struct __move_impl : __trivial_copy_func<_AlgPolicy> { + + using __trivial_copy_func<_AlgPolicy>::__run; + + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14 static + pair<_InputIterator, _OutputIterator> + __run(_InputIterator __first, _Sentinel __last, _OutputIterator __result) { + 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 ::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(__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>::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<_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 -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -__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(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 +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -__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(std::move(__first), std::move(__last), std::move(__result)); + using _AlgImpl = __move_impl<_AlgPolicy>; + return std::__dispatch_copy_or_move<_AlgImpl>( + std::move(__first), std::move(__last), std::move(__result)); } template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return std::__move(__first, __last, __result).second; + 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,11 +9,11 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_BACKWARD_H #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H -#include <__algorithm/unwrap_iter.h> +#include <__algorithm/copy_move_common.h> +#include <__algorithm/iterator_operations.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 @@ -21,41 +21,34 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -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 +struct __move_backward_impl : __trivial_copy_func<_AlgPolicy, /*_Backward=*/true> { -template -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); -} + using __trivial_copy_func<_AlgPolicy, /*_Backward=*/true>::__run; -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -typename enable_if -< - is_same::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(__last - __first); - if (__n > 0) - { - __result -= __n; - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14 static + pair<_InputIterator, _OutputIterator> + __run(_InputIterator __first, _Sentinel __last, _OutputIterator __result) { + auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last); + auto __original_last_iter = __last_iter; + + while (__first != __last_iter) { + *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last_iter); } - return __result; + + return pair<_InputIterator, _OutputIterator>(std::move(__original_last_iter), std::move(__result)); + } + +}; + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +pair<_BidirectionalIterator1, _BidirectionalIterator2> +__move_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) { + using _AlgImpl = __move_backward_impl<_AlgPolicy>; + return std::__dispatch_copy_or_move<_AlgImpl>( + std::move(__first), std::move(__last), std::move(__result)); } template @@ -64,14 +57,8 @@ 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_backward<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), std::move(__result)).second; } _LIBCPP_END_NAMESPACE_STD 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 @@ -10,10 +10,10 @@ #define _LIBCPP___ALGORITHM_RANGES_MOVE_H #include <__algorithm/in_out_result.h> +#include <__algorithm/iterator_operations.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> @@ -36,24 +36,12 @@ struct __fn { template - 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)); + auto __ret = std::__move<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } - template - _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 _Sent, weakly_incrementable _OutIter> requires indirectly_movable<_InIter, _OutIter> _LIBCPP_HIDE_FROM_ABI constexpr 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,7 +10,8 @@ #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> @@ -40,10 +41,8 @@ template _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.in.base()), 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/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -248,6 +248,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/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'}} 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 --- 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 @@ -155,7 +155,7 @@ assert(b[2].get() == 3); } } - + { // check that a move-only type works for ProxyIterator { MoveOnly a[] = {1, 2, 3}; 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 --- 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 @@ -64,7 +64,7 @@ std::same_as> 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.in) == in.data() + in.size()); assert(base(ret.out) == out.data()); } { @@ -73,7 +73,7 @@ std::same_as> 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.in) == in.data() + in.size()); assert(base(ret.out) == out.data()); } } @@ -186,7 +186,7 @@ std::array out; std::same_as> auto ret = std::ranges::move_backward(std::views::all(in), out.data() + out.size()); - assert(ret.in == in.data()); + assert(ret.in == in.data() + in.size()); assert(ret.out == out.data()); assert(in == out); } @@ -206,7 +206,7 @@ std::array in {}; std::array out {}; auto ret = std::ranges::move_backward(in.begin(), in.end(), out.end()); - assert(ret.in == in.begin()); + assert(ret.in == in.end()); assert(ret.out == out.begin()); assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; })); } @@ -214,7 +214,7 @@ std::array in {}; std::array out {}; auto ret = std::ranges::move_backward(in, out.end()); - assert(ret.in == in.begin()); + assert(ret.in == in.end()); assert(ret.out == out.begin()); assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.moved; })); } @@ -239,7 +239,7 @@ 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.in == in.end()); assert(ret.out == out.begin()); assert(out[0].canMove); assert(out[1].canMove); @@ -252,7 +252,7 @@ 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.in == in.end()); assert(ret.out == out.begin()); assert(out[0].canMove); assert(out[1].canMove); @@ -265,7 +265,7 @@ int a[] = {1, 2, 3, 4}; std::array b; auto ret = std::ranges::move_backward(IteratorWithMoveIter(a), IteratorWithMoveIter(a + 4), b.data() + b.size()); - assert(ret.in == a); + assert(ret.in == std::end(a)); assert(ret.out == b.data()); assert((b == std::array {42, 42, 42, 42})); } @@ -274,7 +274,7 @@ std::array 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.in == std::end(a)); assert(ret.out == b.data()); assert((b == std::array {42, 42, 42, 42})); }