From 1d1a191edcfa87bf77331ffcc8fa29562b17f517 Mon Sep 17 00:00:00 2001 From: Nikolas Klauser Date: Tue, 24 May 2022 10:32:50 +0200 Subject: [PATCH] [libc++] Implement ranges::reverse Reviewed By: var-const, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D125752 --- libcxx/docs/Status/RangesAlgorithms.csv | 2 +- libcxx/include/CMakeLists.txt | 1 + libcxx/include/__algorithm/ranges_reverse.h | 83 ++++++++++++++ libcxx/include/algorithm | 10 ++ libcxx/include/module.modulemap | 1 + libcxx/test/libcxx/private_headers.verify.cpp | 1 + .../alg.reverse/ranges.reverse.pass.cpp | 120 +++++++++++++++++++++ .../niebloid.compile.pass.cpp | 2 +- libcxx/test/support/almost_satisfies_types.h | 81 ++++++++++++++ 9 files changed, 299 insertions(+), 2 deletions(-) create mode 100644 libcxx/include/__algorithm/ranges_reverse.h create mode 100644 libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse.pass.cpp diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv index 3664106..4395c91 100644 --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -67,7 +67,7 @@ Merge,set_symmetric_difference,Not assigned,n/a,Not started Merge,set_union,Not assigned,n/a,Not started Permutation,remove,Not assigned,n/a,Not started Permutation,remove_if,Not assigned,n/a,Not started -Permutation,reverse,Not assigned,n/a,Not started +Permutation,reverse,Nikolas Klauser,`D125752 `_,✅ Permutation,rotate,Not assigned,n/a,Not started Permutation,shuffle,Not assigned,n/a,Not started Permutation,unique,Not assigned,n/a,Not started diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index 74336ed..b6e4f6d 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -85,6 +85,7 @@ set(files __algorithm/ranges_minmax.h __algorithm/ranges_minmax_element.h __algorithm/ranges_mismatch.h + __algorithm/ranges_reverse.h __algorithm/ranges_swap_ranges.h __algorithm/ranges_transform.h __algorithm/remove.h diff --git a/libcxx/include/__algorithm/ranges_reverse.h b/libcxx/include/__algorithm/ranges_reverse.h new file mode 100644 index 0000000..e7555d0 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_reverse.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_REVERSE_H +#define _LIBCPP___ALGORITHM_RANGES_REVERSE_H + +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/iter_swap.h> +#include <__iterator/next.h> +#include <__iterator/permutable.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 { +namespace __reverse { +struct __fn { + + template _Sent> + requires permutable<_Iter> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last) const { + if constexpr (random_access_iterator<_Iter>) { + if (__first == __last) + return __first; + + auto __end = ranges::next(__first, __last); + auto __ret = __end; + + while (__first < --__end) { + ranges::iter_swap(__first, __end); + ++__first; + } + return __ret; + } else { + auto __end = ranges::next(__first, __last); + auto __ret = __end; + + while (__first != __end) { + if (__first == --__end) + break; + + ranges::iter_swap(__first, __end); + ++__first; + } + return __ret; + } + } + + template + requires permutable> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range) const { + return (*this)(ranges::begin(__range), ranges::end(__range)); + } + +}; +} // namespace __reverse + +inline namespace __cpo { + inline constexpr auto reverse = __reverse::__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_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index a95fa76..224c9e1 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -274,6 +274,15 @@ namespace ranges { indirect_unary_predicate, Proj>> Pred> constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); // since C++20 + + template S> + requires permutable + constexpr I ranges::reverse(I first, S last); // since C++20 + + template + requires permutable> + constexpr borrowed_iterator_t ranges::reverse(R&& r); // since C++20 + } constexpr bool // constexpr in C++20 @@ -1009,6 +1018,7 @@ template #include <__algorithm/ranges_minmax.h> #include <__algorithm/ranges_minmax_element.h> #include <__algorithm/ranges_mismatch.h> +#include <__algorithm/ranges_reverse.h> #include <__algorithm/ranges_swap_ranges.h> #include <__algorithm/ranges_transform.h> #include <__algorithm/remove.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap index d62e6ae..132793f 100644 --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -318,6 +318,7 @@ module std [system] { 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_reverse { private header "__algorithm/ranges_reverse.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" } module ranges_transform { private header "__algorithm/ranges_transform.h" } module remove { private header "__algorithm/remove.h" } diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp index d85a7e9..fe0f19b 100644 --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -122,6 +122,7 @@ END-SCRIPT #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_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}} #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}} #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}} #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse.pass.cpp new file mode 100644 index 0000000..1447470 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse.pass.cpp @@ -0,0 +1,120 @@ +//===----------------------------------------------------------------------===// +// +// 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> +// requires permutable +// constexpr I ranges::reverse(I first, S last); +// template +// requires permutable> +// constexpr borrowed_iterator_t ranges::reverse(R&& r); + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template > +concept HasReverseIt = requires (Iter first, Sent last) { std::ranges::reverse(first, last); }; + +static_assert(HasReverseIt); +static_assert(!HasReverseIt); +static_assert(!HasReverseIt); +static_assert(!HasReverseIt); +static_assert(!HasReverseIt); + + +template +concept HasReverseR = requires (Range range) { std::ranges::reverse(range); }; + +static_assert(HasReverseR>); +static_assert(!HasReverseR); +static_assert(!HasReverseR); +static_assert(!HasReverseR); +static_assert(!HasReverseR); + +template +constexpr void test(std::array value, std::array expected) { + { + auto val = value; + std::same_as decltype(auto) ret = std::ranges::reverse(Iter(val.data()), Sent(Iter(val.data() + val.size()))); + assert(val == expected); + assert(base(ret) == val.data() + val.size()); + } + { + auto val = value; + auto range = std::ranges::subrange(Iter(val.data()), Sent(Iter(val.data() + val.size()))); + std::same_as decltype(auto) ret = std::ranges::reverse(range); + assert(val == expected); + assert(base(ret) == val.data() + val.size()); + } +} + +template +constexpr void test_iterators() { + // simple test + test({1, 2, 3, 4}, {4, 3, 2, 1}); + // check that an odd number of elements works + test({1, 2, 3, 4, 5, 6, 7}, {7, 6, 5, 4, 3, 2, 1}); + // check that an empty range works + test({}, {}); + // check that a single element works + test({5}, {5}); +} + +struct SwapCounter { + int* counter; + constexpr SwapCounter(int* counter_) : counter(counter_) {} + friend constexpr void swap(SwapCounter& lhs, SwapCounter&) { ++*lhs.counter; } +}; + +constexpr bool test() { + test_iterators>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators, sentinel_wrapper>>(); + test_iterators(); + + // check that std::ranges::dangling is returned + { + [[maybe_unused]] std::same_as auto ret = std::ranges::reverse(std::array {1, 2, 3, 4}); + } + + { + { + int counter = 0; + SwapCounter a[] = {&counter, &counter, &counter, &counter}; + std::ranges::reverse(a); + assert(counter == 2); + } + { + int counter = 0; + SwapCounter a[] = {&counter, &counter, &counter, &counter}; + std::ranges::reverse(a, a + 4); + assert(counter == 2); + } + } + + 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 index 812b585..03c0563 100644 --- 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 @@ -125,7 +125,7 @@ static_assert(test(std::ranges::mismatch, a, a)); //static_assert(test(std::ranges::replace_copy, a, a, 42, 43)); //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, 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)); diff --git a/libcxx/test/support/almost_satisfies_types.h b/libcxx/test/support/almost_satisfies_types.h index 95d9b47..49984a4 100644 --- a/libcxx/test/support/almost_satisfies_types.h +++ b/libcxx/test/support/almost_satisfies_types.h @@ -139,4 +139,85 @@ public: static_assert(!std::movable); static_assert(!std::weakly_incrementable); +class BidirectionalIteratorNotDerivedFrom { +public: + using difference_type = long; + using value_type = int; + using iterator_category = std::forward_iterator_tag; + + BidirectionalIteratorNotDerivedFrom& operator++(); + BidirectionalIteratorNotDerivedFrom operator++(int); + BidirectionalIteratorNotDerivedFrom& operator--(); + BidirectionalIteratorNotDerivedFrom operator--(int); + int& operator*() const; + + bool operator==(const BidirectionalIteratorNotDerivedFrom&) const = default; +}; + +using BidirectionalRangeNotDerivedFrom = UncheckedRange; + +static_assert(std::forward_iterator); +static_assert(!std::bidirectional_iterator); +static_assert(!std::ranges::bidirectional_range); + +class BidirectionalIteratorNotDecrementable { +public: + using difference_type = long; + using value_type = int; + using iterator_category = std::bidirectional_iterator_tag; + + BidirectionalIteratorNotDecrementable& operator++(); + BidirectionalIteratorNotDecrementable operator++(int); + int& operator*() const; + + bool operator==(const BidirectionalIteratorNotDecrementable&) const = default; +}; + +using BidirectionalRangeNotDecrementable = UncheckedRange; + +static_assert(std::forward_iterator); +static_assert(!std::bidirectional_iterator); +static_assert(!std::ranges::bidirectional_range); + +class PermutableNotForwardIterator { +public: + using difference_type = long; + using value_type = int; + using iterator_category = std::input_iterator_tag; + + PermutableNotForwardIterator& operator++(); + void operator++(int); + int& operator*() const; +}; + +using PermutableRangeNotForwardIterator = UncheckedRange; + +static_assert(std::input_iterator); +static_assert(!std::forward_iterator); +static_assert(!std::permutable); + +class PermutableNotSwappable { +public: + class NotSwappable { + NotSwappable(NotSwappable&&) = delete; + }; + + using difference_type = long; + using value_type = NotSwappable; + using iterator_category = std::contiguous_iterator_tag; + + PermutableNotSwappable& operator++(); + PermutableNotSwappable operator++(int); + NotSwappable& operator*() const; + + bool operator==(const PermutableNotSwappable&) const = default; +}; + +using PermutableRangeNotSwappable = UncheckedRange; + +static_assert(std::input_iterator); +static_assert(std::forward_iterator); +static_assert(!std::permutable); +static_assert(!std::indirectly_swappable); + #endif // ALMOST_SATISFIES_TYPES_H -- 2.7.4