diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -99,6 +99,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/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 #include @@ -23,53 +26,88 @@ // move -template +template 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 -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -_OutputIterator -__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - return _VSTD::__move_constexpr(__first, __last, __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 -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(_Tp* __first, _Tp* __last, _Up* __result) -{ - const size_t __n = static_cast(__last - __first); - if (__n > 0) - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); - return __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 +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) { + return std::__move_impl(std::move(__first), std::move(__last), std::move(__result)); } template -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/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 +using move_result = in_out_result<_InIter, _OutIter>; + +namespace __move { +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)); + 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 + 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 + requires indirectly_movable, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_result, _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 +using move_backward_result = in_out_result<_InIter, _OutIter>; + +namespace __move_backward { +struct __fn { + + 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())}; + } + + template _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 + requires indirectly_movable, _Iter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_backward_result, _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 b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -450,6 +450,27 @@ ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + template S1, bidirectional_iterator I2> + requires indirectly_movable + constexpr ranges::move_backward_result + ranges::move_backward(I1 first, S1 last, I2 result); // since C++20 + + template + requires indirectly_movable, I> + constexpr ranges::move_backward_result, I> + ranges::move_backward(R&& r, I result); // since C++20 + + template S, weakly_incrementable O> + requires indirectly_movable + constexpr ranges::move_result + ranges::move(I first, S last, O result); // since C++20 + + template + requires indirectly_movable, O> + constexpr ranges::move_result, O> + ranges::move(R&& r, O result); // since C++20 + + } constexpr bool // constexpr in C++20 @@ -1195,6 +1216,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/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -338,6 +338,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/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 @@ -136,6 +136,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 +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, weakly_incrementable O> +// requires indirectly_movable +// constexpr ranges::move_result +// ranges::move(I first, S last, O result); +// template +// requires indirectly_movable, O> +// constexpr ranges::move_result, O> +// ranges::move(R&& r, O result); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "MoveOnly.h" +#include "test_iterators.h" + +template > +concept HasMoveIt = requires(In in, Sent sent, Out out) { std::ranges::move(in, sent, out); }; + +static_assert(HasMoveIt); +static_assert(!HasMoveIt); +static_assert(!HasMoveIt); +static_assert(!HasMoveIt); +static_assert(!HasMoveIt); +struct NotIndirectlyMovable {}; +static_assert(!HasMoveIt); +static_assert(!HasMoveIt); +static_assert(!HasMoveIt); + +template +concept HasMoveR = requires(Range range, Out out) { std::ranges::move(range, out); }; + +static_assert(HasMoveR, int*>); +static_assert(!HasMoveR); +static_assert(!HasMoveR); +static_assert(!HasMoveR); +static_assert(!HasMoveR); +static_assert(!HasMoveR, int*>); +static_assert(!HasMoveR); +static_assert(!HasMoveR); +static_assert(!HasMoveR, WeaklyIncrementableNotMovable>); + +static_assert(std::is_same_v, std::ranges::in_out_result>); + +template +constexpr void test(std::array in) { + { + std::array out; + std::same_as> 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 out; + auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size()))); + std::same_as> 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 +constexpr void test_iterators() { + // simple test + test({1, 2, 3, 4}); + // check that an empty range works + test({}); +} + +template +constexpr void test_in_iterators() { + test_iterators, Out, sentinel_wrapper>>(); + test_iterators, Out>(); + test_iterators, Out>(); + test_iterators, Out>(); + test_iterators, 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>(); + test_in_iterators>(); + test_in_iterators>(); + test_in_iterators>(); + test_in_iterators>(); + test_in_iterators>(); + test_in_iterators>(); + test_in_iterators>(); + + { // 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 out; + std::same_as> 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 out; + std::same_as> 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 in {}; + std::array 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 in {}; + std::array 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 in {}; + std::array 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 in {}; + std::array 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 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 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 +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S1, bidirectional_iterator I2> +// requires indirectly_movable +// constexpr ranges::move_backward_result +// ranges::move_backward(I1 first, S1 last, I2 result); +// template +// requires indirectly_movable, I> +// constexpr ranges::move_backward_result, I> +// ranges::move_backward(R&& r, I result); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "MoveOnly.h" +#include "test_iterators.h" + +template > +concept HasMoveBackwardIt = requires(In in, Sent sent, Out out) { std::ranges::move_backward(in, sent, out); }; + +static_assert(HasMoveBackwardIt); +static_assert(!HasMoveBackwardIt); +static_assert(!HasMoveBackwardIt); +static_assert(!HasMoveBackwardIt); +static_assert(!HasMoveBackwardIt); +struct NotIndirectlyCopyable {}; +static_assert(!HasMoveBackwardIt); +static_assert(!HasMoveBackwardIt); +static_assert(!HasMoveBackwardIt); + +template +concept HasMoveBackwardR = requires(Range range, Out out) { std::ranges::move_backward(range, out); }; + +static_assert(HasMoveBackwardR, int*>); +static_assert(!HasMoveBackwardR); +static_assert(!HasMoveBackwardR); +static_assert(!HasMoveBackwardR); +static_assert(!HasMoveBackwardR); +static_assert(!HasMoveBackwardR, int*>); +static_assert(!HasMoveBackwardR); +static_assert(!HasMoveBackwardR); +static_assert(!HasMoveBackwardR, WeaklyIncrementableNotMovable>); + +static_assert(std::is_same_v, std::ranges::in_out_result>); + +template +constexpr void test(std::array in) { + { + std::array out; + 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.out) == out.data()); + } + { + std::array out; + auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size()))); + 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.out) == out.data()); + } +} + +template +constexpr void test_iterators() { + // simple test + test({1, 2, 3, 4}); + // check that an empty range works + test({}); +} + +template +constexpr void test_in_iterators() { + test_iterators, Out, sentinel_wrapper>>(); + test_iterators, Out>(); + test_iterators, Out>(); + test_iterators, 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>(); + test_in_iterators>(); + test_in_iterators>(); + + { // 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 out; + std::same_as> 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 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.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 in {}; + std::array 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 in {}; + std::array 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 in {}; + std::array 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 in {}; + std::array 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 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 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));