diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -166,6 +166,7 @@ algorithms/min_max_element.bench.cpp algorithms/pop_heap.bench.cpp algorithms/push_heap.bench.cpp + algorithms/ranges_stable_sort.bench.cpp algorithms/sort.bench.cpp algorithms/sort_heap.bench.cpp algorithms/stable_sort.bench.cpp diff --git a/libcxx/benchmarks/algorithms/ranges_stable_sort.bench.cpp b/libcxx/benchmarks/algorithms/ranges_stable_sort.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/ranges_stable_sort.bench.cpp @@ -0,0 +1,39 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include + +#include "common.h" + +namespace { +template +struct StableSort { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, + [](auto& Copy) { std::ranges::stable_sort(Copy); }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_RangesStableSort" + ValueType::name() + Order::name() + "_" + + std::to_string(Quantity); + }; +}; +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + makeCartesianProductBenchmark(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} 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 @@ -74,7 +74,7 @@ Permutation,partition,Not assigned,n/a,Not started Permutation,stable_partition,Not assigned,n/a,Not started Permutation,sort,Konstantin Varlamov,n/a,In progress -Permutation,stable_sort,Konstantin Varlamov,n/a,In progress +Permutation,stable_sort,Konstantin Varlamov,`D125752 `_,Under review Permutation,partial_sort,Konstantin Varlamov,n/a,In progress Permutation,nth_element,Not assigned,n/a,Not started Permutation,inplace_merge,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 @@ -97,6 +97,7 @@ __algorithm/ranges_mismatch.h __algorithm/ranges_none_of.h __algorithm/ranges_reverse.h + __algorithm/ranges_stable_sort.h __algorithm/ranges_swap_ranges.h __algorithm/ranges_transform.h __algorithm/ranges_upper_bound.h diff --git a/libcxx/include/__algorithm/ranges_stable_sort.h b/libcxx/include/__algorithm/ranges_stable_sort.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_stable_sort.h @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// 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_STABLE_SORT_H +#define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H + +#include <__algorithm/stable_sort.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.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 { +namespace __stable_sort { + +struct __fn { + template + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) const { + auto __projected_comp = [&](const auto& __lhs, const auto& __rhs) { + return std::invoke(__comp, std::invoke(__proj, __lhs), std::invoke(__proj, __rhs)); + }; + + auto __last_iter = ranges::next(__first, __last); + std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp); + return __last_iter; + } + + template _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __stable_sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template + requires sortable, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return __stable_sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __stable_sort + +inline namespace __cpo { + inline constexpr auto stable_sort = __stable_sort::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h --- a/libcxx/include/__algorithm/stable_sort.h +++ b/libcxx/include/__algorithm/stable_sort.h @@ -15,6 +15,7 @@ #include <__algorithm/sort.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #include <__utility/swap.h> #include #include @@ -199,30 +200,31 @@ } template -inline _LIBCPP_INLINE_VISIBILITY -void -stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - difference_type __len = __last - __first; - pair __buf(0, 0); - unique_ptr __h; - if (__len > static_cast(__stable_sort_switch::value)) - { - __buf = _VSTD::get_temporary_buffer(__len); - __h.reset(__buf.first); - } - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); +inline _LIBCPP_HIDE_FROM_ABI +void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + difference_type __len = __last - __first; + pair __buf(0, 0); + unique_ptr __h; + if (__len > static_cast(__stable_sort_switch::value)) { + __buf = _VSTD::get_temporary_buffer(__len); + __h.reset(__buf.first); + } + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); +} + +template +inline _LIBCPP_HIDE_FROM_ABI +void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__stable_sort_impl(std::move(__first), std::move(__last), __comp); } template -inline _LIBCPP_INLINE_VISIBILITY -void -stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::stable_sort(__first, __last, __less::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI +void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::stable_sort(__first, __last, __less::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -274,7 +274,6 @@ 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 @@ -283,6 +282,16 @@ requires permutable> constexpr borrowed_iterator_t ranges::reverse(R&& r); // since C++20 + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + borrowed_iterator_t + ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + template O, sentinel_for S> constexpr O ranges::fill(O first, S last, const T& value); // since C++20 @@ -1138,6 +1147,7 @@ #include <__algorithm/ranges_mismatch.h> #include <__algorithm/ranges_none_of.h> #include <__algorithm/ranges_reverse.h> +#include <__algorithm/ranges_stable_sort.h> #include <__algorithm/ranges_swap_ranges.h> #include <__algorithm/ranges_transform.h> #include <__algorithm/ranges_upper_bound.h> diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -213,8 +213,8 @@ //(void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0); //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); } //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(&copies)); assert(copies == 0); } - //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); } - //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); } + if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); } + if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); } #if TEST_STD_VER > 20 //(void)std::ranges::starts_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0); #endif diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -204,8 +204,8 @@ //(void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0); //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); } //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); } - //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); } - //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); } + if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); } + if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); } #if TEST_STD_VER > 20 //(void)std::ranges::starts_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); #endif 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 @@ -134,6 +134,7 @@ #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.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_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.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'}} #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}} #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp @@ -0,0 +1,258 @@ +//===----------------------------------------------------------------------===// +// +// 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, class Comp = ranges::less, +// class Proj = identity> +// requires sortable +// I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 +// +// template +// requires sortable, Comp, Proj> +// borrowed_iterator_t +// ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "boolean_testable.h" +#include "test_iterators.h" + +// SFINAE tests. + +using BadComparator = ComparatorNotCopyable; +static_assert(!std::sortable); + +template , class Comp = std::ranges::less> +concept HasStableSortIt = requires(Iter first, Sent last, Comp comp) { std::ranges::stable_sort(first, last, comp); }; + +static_assert(HasStableSortIt); +static_assert(!HasStableSortIt); +static_assert(!HasStableSortIt); +static_assert(!HasStableSortIt); +static_assert(!HasStableSortIt); +static_assert(!HasStableSortIt); +static_assert(!HasStableSortIt); // Doesn't satisfy `sortable`. + +template +concept HasStableSortR = requires(Range range, Comp comp) { std::ranges::stable_sort(range, comp); }; + +static_assert(HasStableSortR>); +static_assert(!HasStableSortR); +static_assert(!HasStableSortR); +static_assert(!HasStableSortR>); +static_assert(!HasStableSortR>); +static_assert(!HasStableSortR, BadComparator>); +static_assert(!HasStableSortR>); // Doesn't satisfy `sortable`. + +template +void test_one(std::array input, std::array expected) { + { // (iterator, sentinel) overload. + auto sorted = input; + auto b = Iter(sorted.data()); + auto e = Sent(Iter(sorted.data() + sorted.size())); + + std::same_as decltype(auto) last = std::ranges::stable_sort(b, e); + assert(sorted == expected); + assert(base(last) == sorted.data() + sorted.size()); + } + + { // (range) overload. + auto sorted = input; + auto b = Iter(sorted.data()); + auto e = Sent(Iter(sorted.data() + sorted.size())); + auto range = std::ranges::subrange(b, e); + + std::same_as decltype(auto) last = std::ranges::stable_sort(range); + assert(sorted == expected); + assert(base(last) == sorted.data() + sorted.size()); + } +} + +template +void test_iterators_2() { + // Empty sequence. + test_one({}, {}); + // 1-element sequence. + test_one({1}, {1}); + // 2-element sequence. + test_one({2, 1}, {1, 2}); + // 3-element sequence. + test_one({2, 1, 3}, {1, 2, 3}); + // Longer sequence. + test_one({2, 1, 3, 6, 8, 4, 11, 5}, {1, 2, 3, 4, 5, 6, 8, 11}); + // Longer sequence with duplicates. + test_one({2, 1, 3, 6, 2, 8, 6}, {1, 2, 2, 3, 6, 6, 8}); + // All elements are the same. + test_one({1, 1, 1}, {1, 1, 1}); + // Already sorted. + test_one({1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}); + // Reverse-sorted. + test_one({5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}); + // Repeating pattern. + test_one({1, 2, 1, 2, 1, 2}, {1, 1, 1, 2, 2, 2}); +} + +template +void test_iterators_1() { + test_iterators_2(); + test_iterators_2>(); +} + +void test_iterators() { + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1(); +} + +void test() { + test_iterators(); + + { // The sort is stable (equivalent elements remain in the same order). + struct OrderedValue { + int value; + int original_order; + bool operator==(const OrderedValue&) const = default; + bool operator<(const OrderedValue& rhs) const { return value < rhs.value; } + bool operator<=(const OrderedValue& rhs) const { return value <= rhs.value; } + bool operator>(const OrderedValue& rhs) const { return value > rhs.value; } + bool operator>=(const OrderedValue& rhs) const { return value >= rhs.value; } + }; + + using V = OrderedValue; + using Array = std::array; + Array orig_in = { + V{10, 101}, {12, 121}, {3, 31}, {5, 51}, {3, 32}, {3, 33}, {11, 111}, {12, 122}, {4, 41}, {4, 42}, {4, 43}, + {1, 11}, {6, 61}, {3, 34}, {10, 102}, {8, 81}, {12, 123}, {1, 12}, {1, 13}, {5, 52} + }; + Array expected = { + V{1, 11}, {1, 12}, {1, 13}, + {3, 31}, {3, 32}, {3, 33}, {3, 34}, + {4, 41}, {4, 42}, {4, 43}, + {5, 51}, {5, 52}, + {6, 61}, + {8, 81}, + {10, 101}, {10, 102}, + {11, 111}, + {12, 121}, {12, 122}, {12, 123}, + }; + + { + auto in = orig_in; + auto last = std::ranges::stable_sort(in.begin(), in.end()); + assert(in == expected); + assert(last == in.end()); + } + + { + auto in = orig_in; + auto last = std::ranges::stable_sort(in); + assert(in == expected); + assert(last == in.end()); + } + } + + { // A custom comparator works. + { + std::array in = {1, 2, 3, 4, 5}; + auto last = std::ranges::stable_sort(in.begin(), in.end(), std::greater{}); + assert((in == std::array{5, 4, 3, 2, 1})); + assert(last == in.end()); + } + + { + std::array in = {1, 2, 3, 4, 5}; + auto last = std::ranges::stable_sort(in, std::greater{}); + assert((in == std::array{5, 4, 3, 2, 1})); + assert(last == in.end()); + } + } + + { // A custom projection works. + struct A { + int a; + bool operator==(const A&) const = default; + }; + + { + std::array in = {A{2}, A{3}, A{1}}; + auto last = std::ranges::stable_sort(in.begin(), in.end(), {}, &A::a); + assert((in == std::array{A{1}, A{2}, A{3}})); + assert(last == in.end()); + } + + { + std::array in = {A{2}, A{3}, A{1}}; + auto last = std::ranges::stable_sort(in, {}, &A::a); + assert((in == std::array{A{1}, A{2}, A{3}})); + assert(last == in.end()); + } + } + + { // `std::invoke` is used in the implementation. + struct S { + int i; + S(int i_) : i(i_) {} + + bool comparator(const S& rhs) const { return i < rhs.i; } + const S& projection() const { return *this; } + + bool operator==(const S&) const = default; + }; + + { + std::array in = {S{2}, S{3}, S{1}}; + auto last = std::ranges::stable_sort(in.begin(), in.end(), &S::comparator, &S::projection); + assert((in == std::array{S{1}, S{2}, S{3}})); + assert(last == in.end()); + } + + { + std::array in = {S{2}, S{3}, S{1}}; + auto last = std::ranges::stable_sort(in, &S::comparator, &S::projection); + assert((in == std::array{S{1}, S{2}, S{3}})); + assert(last == in.end()); + } + } + + { // The comparator can return any type that's convertible to `bool`. + { + std::array in = {2, 1, 3}; + auto last = std::ranges::stable_sort(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; }); + assert((in == std::array{1, 2, 3})); + assert(last == in.end()); + } + + { + std::array in = {2, 1, 3}; + auto last = std::ranges::stable_sort(in, [](int i, int j) { return BooleanTestable{i < j}; }); + assert((in == std::array{1, 2, 3})); + assert(last == in.end()); + } + } + + { // `std::ranges::dangling` is returned. + [[maybe_unused]] std::same_as decltype(auto) result = + std::ranges::stable_sort(std::array{1, 2, 3}); + } +} + +int main(int, char**) { + test(); + // Note: `stable_sort` is not `constexpr`. + + 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 @@ -140,7 +140,7 @@ //static_assert(test(std::ranges::sort, a)); //static_assert(test(std::ranges::sort_heap, a)); //static_assert(test(std::ranges::stable_partition, a, odd)); -//static_assert(test(std::ranges::stable_sort, a)); +static_assert(test(std::ranges::stable_sort, a)); //static_assert(test(std::ranges::starts_with, a, a)); static_assert(test(std::ranges::swap_ranges, a, a)); static_assert(test(std::ranges::transform, a, a, triple)); diff --git a/libcxx/test/support/almost_satisfies_types.h b/libcxx/test/support/almost_satisfies_types.h --- a/libcxx/test/support/almost_satisfies_types.h +++ b/libcxx/test/support/almost_satisfies_types.h @@ -301,4 +301,88 @@ static_assert(!std::output_iterator); static_assert(!std::ranges::output_range); +class RandomAccessIteratorNotDerivedFrom { + using Self = RandomAccessIteratorNotDerivedFrom; + +public: + using value_type = int; + using difference_type = long; + using pointer = int*; + using reference = int&; + // Deliberately not using the `std::random_access_iterator_tag` category. + using iterator_category = std::bidirectional_iterator_tag; + + reference operator*() const; + reference operator[](difference_type) const; + + Self& operator++(); + Self& operator--(); + Self operator++(int); + Self operator--(int); + + Self& operator+=(difference_type); + Self& operator-=(difference_type); + friend Self operator+(Self, difference_type); + friend Self operator+(difference_type, Self); + friend Self operator-(Self, difference_type); + friend difference_type operator-(Self, Self); + + friend bool operator==(const Self&, const Self&); + friend bool operator!=(const Self&, const Self&); + friend bool operator< (const Self&, const Self&); + friend bool operator<=(const Self&, const Self&); + friend bool operator> (const Self&, const Self&); + friend bool operator>=(const Self&, const Self&); +}; + +static_assert(std::bidirectional_iterator); +static_assert(!std::random_access_iterator); + +using RandomAccessRangeNotDerivedFrom = UncheckedRange; + +class RandomAccessIteratorBadIndex { + using Self = RandomAccessIteratorBadIndex; + +public: + using value_type = int; + using difference_type = long; + using pointer = int*; + using reference = int&; + using iterator_category = std::random_access_iterator_tag; + + reference operator*() const; + // Deliberately returning a type different from `reference`. + const int& operator[](difference_type) const; + + Self& operator++(); + Self& operator--(); + Self operator++(int); + Self operator--(int); + + Self& operator+=(difference_type); + Self& operator-=(difference_type); + friend Self operator+(Self, difference_type); + friend Self operator+(difference_type, Self); + friend Self operator-(Self, difference_type); + friend difference_type operator-(Self, Self); + + auto operator<=>(const Self&) const = default; +}; + +static_assert(std::bidirectional_iterator); +static_assert(!std::random_access_iterator); + +using RandomAccessRangeBadIndex = UncheckedRange; + +template +class ComparatorNotCopyable { +public: + ComparatorNotCopyable(ComparatorNotCopyable&&) = default; + ComparatorNotCopyable& operator=(ComparatorNotCopyable&&) = default; + ComparatorNotCopyable(const ComparatorNotCopyable&) = delete; + ComparatorNotCopyable& operator=(const ComparatorNotCopyable&) = delete; + + bool operator()(Iter&, Iter&) const; +}; + #endif // ALMOST_SATISFIES_TYPES_H