diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -54,8 +54,8 @@ Write,replace_copy,Nikolas Klauser,n/a,Not started Write,replace_copy_if,Nikolas Klauser,n/a,Not started Write,swap_ranges,Nikolas Klauser,`D116303 `_,✅ -Write,reverse_copy,Nikolas Klauser,`D127211 `_,Under review -Write,rotate_copy,Nikolas Klauser,`D127211 `_,Under review +Write,reverse_copy,Nikolas Klauser,`D127211 `_,✅ +Write,rotate_copy,Nikolas Klauser,`D127211 `_,✅ Write,sample,Not assigned,n/a,Not started Write,unique_copy,Not assigned,n/a,Not started Write,partition_copy,Not assigned,n/a,Not started diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -106,6 +106,8 @@ __algorithm/ranges_replace.h __algorithm/ranges_replace_if.h __algorithm/ranges_reverse.h + __algorithm/ranges_reverse_copy.h + __algorithm/ranges_rotate_copy.h __algorithm/ranges_sort.h __algorithm/ranges_stable_sort.h __algorithm/ranges_swap_ranges.h diff --git a/libcxx/include/__algorithm/ranges_reverse_copy.h b/libcxx/include/__algorithm/ranges_reverse_copy.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_reverse_copy.h @@ -0,0 +1,66 @@ +//===----------------------------------------------------------------------===// +// +// 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_REVERSE_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_copy.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__ranges/subrange.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 reverse_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __reverse_copy { +struct __fn { + + template _Sent, weakly_incrementable _OutIter> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + reverse_copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { + return (*this)(subrange(std::move(__first), std::move(__last)), std::move(__result)); + } + + template + requires indirectly_copyable, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + reverse_copy_result, _OutIter> operator()(_Range&& __range, _OutIter __result) const { + auto __ret = ranges::copy(std::__reverse_range(__range), std::move(__result)); + return {ranges::next(ranges::begin(__range), ranges::end(__range)), std::move(__ret.out)}; + } + +}; +} // namespace __reverse_copy + +inline namespace __cpo { + inline constexpr auto reverse_copy = __reverse_copy::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H diff --git a/libcxx/include/__algorithm/ranges_rotate_copy.h b/libcxx/include/__algorithm/ranges_rotate_copy.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_rotate_copy.h @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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_ROTATE_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_copy.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.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 rotate_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __rotate_copy { +struct __fn { + + template _Sent, weakly_incrementable _OutIter> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + rotate_copy_result<_InIter, _OutIter> + operator()(_InIter __first, _InIter __middle, _Sent __last, _OutIter __result) const { + auto __res1 = ranges::copy(__middle, __last, std::move(__result)); + auto __res2 = ranges::copy(__first, __middle, std::move(__res1.out)); + return {std::move(__res1.in), std::move(__res2.out)}; + } + + template + requires indirectly_copyable, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + rotate_copy_result, _OutIter> + operator()(_Range&& __range, iterator_t<_Range> __middle, _OutIter __result) const { + return (*this)(ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__result)); + } + +}; +} // namespace __rotate_copy + +inline namespace __cpo { + inline constexpr auto rotate_copy = __rotate_copy::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H diff --git a/libcxx/include/__iterator/reverse_iterator.h b/libcxx/include/__iterator/reverse_iterator.h --- a/libcxx/include/__iterator/reverse_iterator.h +++ b/libcxx/include/__iterator/reverse_iterator.h @@ -15,15 +15,20 @@ #include <__compare/three_way_comparable.h> #include <__concepts/convertible_to.h> #include <__config> +#include <__iterator/advance.h> #include <__iterator/concepts.h> #include <__iterator/incrementable_traits.h> #include <__iterator/iter_move.h> #include <__iterator/iter_swap.h> #include <__iterator/iterator.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> #include <__iterator/prev.h> #include <__iterator/readable_traits.h> #include <__memory/addressof.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.h> #include <__utility/move.h> #include @@ -365,6 +370,16 @@ } }; +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +template +_LIBCPP_HIDE_FROM_ABI constexpr ranges:: + subrange>, reverse_iterator>> + __reverse_range(_Range&& __range) { + auto __first = ranges::begin(__range); + return {std::make_reverse_iterator(ranges::next(__first, ranges::end(__range))), std::make_reverse_iterator(__first)}; +} +#endif + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -511,6 +511,32 @@ merge(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + template + using reverse_copy_result = in_out_result<_InIter, _OutIter>; // since C++20 + + template S, weakly_incrementable O> + requires indirectly_copyable + constexpr ranges::reverse_copy_result + ranges::reverse_copy(I first, S last, O result); // since C++20 + + template + requires indirectly_copyable, O> + constexpr ranges::reverse_copy_result, O> + ranges::reverse_copy(R&& r, O result); // since C++20 + + template + using rotate_copy_result = in_out_result<_InIter, _OutIter>; // since C++20 + + template S, weakly_incrementable O> + requires indirectly_copyable + constexpr ranges::rotate_copy_result + ranges::rotate_copy(I first, I middle, S last, O result); // since C++20 + + template + requires indirectly_copyable, O> + constexpr ranges::rotate_copy_result, O> + ranges::rotate_copy(R&& r, iterator_t middle, O result); // since C++20 + } constexpr bool // constexpr in C++20 @@ -1278,6 +1304,8 @@ #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.h> #include <__algorithm/ranges_reverse.h> +#include <__algorithm/ranges_reverse_copy.h> +#include <__algorithm/ranges_rotate_copy.h> #include <__algorithm/ranges_sort.h> #include <__algorithm/ranges_stable_sort.h> #include <__algorithm/ranges_swap_ranges.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 @@ -143,6 +143,8 @@ #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'}} #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}} +#include <__algorithm/ranges_reverse_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse_copy.h'}} +#include <__algorithm/ranges_rotate_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate_copy.h'}} #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}} #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}} #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}} diff --git a/libcxx/test/libcxx/transitive_includes/expected.charconv b/libcxx/test/libcxx/transitive_includes/expected.charconv --- a/libcxx/test/libcxx/transitive_includes/expected.charconv +++ b/libcxx/test/libcxx/transitive_includes/expected.charconv @@ -6,6 +6,7 @@ cstdint cstdlib cstring +initializer_list iosfwd limits type_traits diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp @@ -0,0 +1,141 @@ +//===----------------------------------------------------------------------===// +// +// 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_copyable +// constexpr ranges::reverse_copy_result +// ranges::reverse_copy(I first, S last, O result); +// template +// requires indirectly_copyable, O> +// constexpr ranges::reverse_copy_result, O> +// ranges::reverse_copy(R&& r, O result); + +// + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template > +concept HasReverseCopyIt = requires(Iter first, Sent last, Out out) { std::ranges::reverse_copy(first, last, out); }; + +template +concept HasReverseCopyR = requires(Range range, Out out) { std::ranges::reverse_copy(range, out); }; + +static_assert(HasReverseCopyIt); +static_assert(!HasReverseCopyIt); +static_assert(!HasReverseCopyIt); +static_assert(!HasReverseCopyIt); +static_assert(!HasReverseCopyIt); +static_assert(!HasReverseCopyIt); +static_assert(!HasReverseCopyIt); + +static_assert(HasReverseCopyR>); +static_assert(!HasReverseCopyR); +static_assert(!HasReverseCopyR); +static_assert(!HasReverseCopyR>); +static_assert(!HasReverseCopyR, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasReverseCopyR, OutputIteratorNotInputOrOutputIterator>); + +static_assert(std::is_same_v, std::ranges::in_out_result>); + +template +constexpr void test(std::array value, std::array expected) { + { + std::array out; + std::same_as> decltype(auto) ret = + std::ranges::reverse_copy(Iter(value.data()), + Sent(Iter(value.data() + value.size())), + OutIter(out.data())); + assert(base(ret.in) == value.data() + value.size()); + assert(base(ret.out) == out.data() + out.size()); + assert(out == expected); + } + { + std::array out; + auto range = std::ranges::subrange(Iter(value.data()), Sent(Iter(value.data() + value.size()))); + std::same_as> decltype(auto) ret = + std::ranges::reverse_copy(range, OutIter(out.data())); + assert(base(ret.in) == value.data() + value.size()); + assert(base(ret.out) == out.data() + out.size()); + assert(out == expected); + } +} + +template +constexpr void test_iterators() { + // simple test + test({1, 2, 3, 4}, {4, 3, 2, 1}); + + // check that an empty range works + test({}, {}); + + // check that a single element range works + test({1}, {1}); + + // check that a two element range works + test({1, 2}, {2, 1}); +} + +template +constexpr void test_out_iterators() { + test_iterators, Sent>(); + test_iterators, Sent>(); + test_iterators, Sent>(); + test_iterators, Sent>(); + test_iterators, Sent>(); + test_iterators(); +} + +constexpr bool test() { + test_out_iterators>(); + test_out_iterators>(); + test_out_iterators>(); + test_out_iterators(); + test_out_iterators(); + + { + struct AssignmentCounter { + int* counter; + + constexpr AssignmentCounter(int* counter_) : counter(counter_) {} + constexpr AssignmentCounter& operator=(const AssignmentCounter&) { ++*counter; return *this; } + }; + + { + int c = 0; + AssignmentCounter a[] = {&c, &c, &c, &c}; + AssignmentCounter b[] = {&c, &c, &c, &c}; + std::ranges::reverse_copy(a, a + 4, b); + assert(c == 4); + } + { + int c = 0; + AssignmentCounter a[] = {&c, &c, &c, &c}; + AssignmentCounter b[] = {&c, &c, &c, &c}; + std::ranges::reverse_copy(a, b); + assert(c == 4); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges.rotate_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges.rotate_copy.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges.rotate_copy.pass.cpp @@ -0,0 +1,154 @@ +//===----------------------------------------------------------------------===// +// +// 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_copyable +// constexpr ranges::rotate_copy_result +// ranges::rotate_copy(I first, I middle, S last, O result); +// template +// requires indirectly_copyable, O> +// constexpr ranges::rotate_copy_result, O> +// ranges::rotate_copy(R&& r, iterator_t middle, O result); + +// + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template > +concept HasRotateCopyIt = requires(Iter first, Sent last, Out out) { std::ranges::rotate_copy(first, first, last, out); }; + +template +concept HasRotateCopyR = requires(Range range, Out out) { std::ranges::rotate_copy(range, nullptr, out); }; + +static_assert(HasRotateCopyIt); +static_assert(!HasRotateCopyIt); +static_assert(!HasRotateCopyIt); +static_assert(!HasRotateCopyIt); +static_assert(!HasRotateCopyIt); +static_assert(!HasRotateCopyIt); +static_assert(!HasRotateCopyIt); + +static_assert(HasRotateCopyR>); +static_assert(!HasRotateCopyR); +static_assert(!HasRotateCopyR); +static_assert(!HasRotateCopyR>); +static_assert(!HasRotateCopyR, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasRotateCopyR, OutputIteratorNotInputOrOutputIterator>); + +static_assert(std::is_same_v, std::ranges::in_out_result>); + +template +constexpr void test(std::array value, size_t middle, std::array expected) { + { + std::array out; + std::same_as> decltype(auto) ret = + std::ranges::rotate_copy(Iter(value.data()), + Iter(value.data() + middle), + Sent(Iter(value.data() + value.size())), + OutIter(out.data())); + assert(base(ret.in) == value.data() + value.size()); + assert(base(ret.out) == out.data() + out.size()); + assert(out == expected); + } + { + std::array out; + auto range = std::ranges::subrange(Iter(value.data()), Sent(Iter(value.data() + value.size()))); + std::same_as> decltype(auto) ret = + std::ranges::rotate_copy(range, Iter(value.data() + middle), OutIter(out.data())); + assert(base(ret.in) == value.data() + value.size()); + assert(base(ret.out) == out.data() + out.size()); + assert(out == expected); + } +} + +template +constexpr void test_iterators() { + // simple test + test({1, 2, 3, 4}, 2, {3, 4, 1, 2}); + + // check that an empty range works + test({}, 0, {}); + + // check that a single element range works + test({1}, 0, {1}); + + // check that a two element range works + test({1, 2}, 1, {2, 1}); + + // rotate on the first element + test({1, 2, 3, 4, 5, 6, 7}, 0, {1, 2, 3, 4, 5, 6, 7}); + + // rotate on the second element + test({1, 2, 3, 4, 5, 6, 7}, 1, {2, 3, 4, 5, 6, 7, 1}); + + // rotate on the last element + test({1, 2, 3, 4, 5, 6, 7}, 6, {7, 1, 2, 3, 4, 5, 6}); + + // rotate on the one-past-the-end pointer + test({1, 2, 3, 4, 5, 6, 7}, 7, {1, 2, 3, 4, 5, 6, 7}); +} + +template +constexpr void test_out_iterators() { + test_iterators, Sent>(); + test_iterators, Sent>(); + test_iterators, Sent>(); + test_iterators, Sent>(); + test_iterators, Sent>(); + test_iterators(); +} + +constexpr bool test() { + test_out_iterators>(); + test_out_iterators>(); + test_out_iterators>(); + test_out_iterators(); + test_out_iterators(); + + { + struct AssignmentCounter { + int* counter; + + constexpr AssignmentCounter(int* counter_) : counter(counter_) {} + constexpr AssignmentCounter& operator=(const AssignmentCounter&) { ++*counter; return *this; } + }; + + { + int c = 0; + AssignmentCounter a[] = {&c, &c, &c, &c}; + AssignmentCounter b[] = {&c, &c, &c, &c}; + std::ranges::rotate_copy(a, a + 2, a + 4, b); + assert(c == 4); + } + { + int c = 0; + AssignmentCounter a[] = {&c, &c, &c, &c}; + AssignmentCounter b[] = {&c, &c, &c, &c}; + std::ranges::rotate_copy(a, a + 2, b); + assert(c == 4); + } + } + + 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 @@ -126,9 +126,9 @@ //static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43)); static_assert(test(std::ranges::replace_if, a, odd, 43)); static_assert(test(std::ranges::reverse, a)); -//static_assert(test(std::ranges::reverse_copy, a, a)); +static_assert(test(std::ranges::reverse_copy, a, a)); //static_assert(test(std::ranges::rotate, a, a+5)); -//static_assert(test(std::ranges::rotate_copy, a, a+5, a)); +static_assert(test(std::ranges::rotate_copy, a, a+5, a)); //static_assert(test(std::ranges::sample, a, a, 5)); //static_assert(test(std::ranges::search, a, a)); //static_assert(test(std::ranges::search_n, a, 10, 42));