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_sort.bench.cpp algorithms/sort.bench.cpp algorithms/sort_heap.bench.cpp algorithms/stable_sort.bench.cpp diff --git a/libcxx/benchmarks/algorithms/ranges_sort.bench.cpp b/libcxx/benchmarks/algorithms/ranges_sort.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/ranges_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 Sort { + size_t Quantity; + + void run(benchmark::State& state) const { + runOpOnCopies( + state, Quantity, Order(), BatchSize::CountElements, + [](auto& Copy) { std::ranges::sort(Copy); }); + } + + bool skip() const { return Order() == ::Order::Heap; } + + std::string name() const { + return "BM_RangesSort" + 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 @@ -73,7 +73,7 @@ Permutation,unique,Not assigned,n/a,Not started 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,sort,`D127557 `_,Konstantin Varlamov,✅ Permutation,stable_sort,Konstantin Varlamov,n/a,In progress Permutation,partial_sort,Konstantin Varlamov,n/a,In progress Permutation,nth_element,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 @@ -45,6 +45,7 @@ __algorithm/lexicographical_compare.h __algorithm/lower_bound.h __algorithm/make_heap.h + __algorithm/make_projected.h __algorithm/max.h __algorithm/max_element.h __algorithm/merge.h @@ -102,6 +103,7 @@ __algorithm/ranges_replace.h __algorithm/ranges_replace_if.h __algorithm/ranges_reverse.h + __algorithm/ranges_sort.h __algorithm/ranges_swap_ranges.h __algorithm/ranges_transform.h __algorithm/ranges_upper_bound.h diff --git a/libcxx/include/__algorithm/make_projected.h b/libcxx/include/__algorithm/make_projected.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/make_projected.h @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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_MAKE_PROJECTED_H +#define _LIBCPP___ALGORITHM_MAKE_PROJECTED_H + +#include <__concepts/same_as.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__utility/forward.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 +_LIBCPP_HIDE_FROM_ABI constexpr static +decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) { + if constexpr (same_as<_Proj, identity>) { + // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable + // optimizations that rely on the type of the comparator. + return __comp; + + } else { + return [&](auto&& __lhs, auto&& __rhs) { + return std::invoke(__comp, + std::invoke(__proj, std::forward(__lhs)), + std::invoke(__proj, std::forward(__rhs))); + }; + } +} + +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_MAKE_PROJECTED_H diff --git a/libcxx/include/__algorithm/ranges_sort.h b/libcxx/include/__algorithm/ranges_sort.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_sort.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// 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_SORT_H +#define _LIBCPP___ALGORITHM_RANGES_SORT_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/sort.h> +#include <__concepts/same_as.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/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.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 __sort { + +struct __fn { + template + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = __make_projected_comp(__comp, __proj); + std::__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 __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 __sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __sort + +inline namespace __cpo { + inline constexpr auto sort = __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_SORT_H diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -18,6 +18,7 @@ #include <__config> #include <__debug> #include <__functional/operations.h> +#include <__functional/ranges_operations.h> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> #include @@ -115,6 +116,7 @@ return __r; } +// The comparator being simple is a prerequisite for using the branchless optimization. template struct __is_simple_comparator : false_type {}; template @@ -123,6 +125,12 @@ struct __is_simple_comparator&> : true_type {}; template struct __is_simple_comparator&> : true_type {}; +#if _LIBCPP_STD_VER > 17 +template <> +struct __is_simple_comparator : true_type {}; +template <> +struct __is_simple_comparator : true_type {}; +#endif template ::value_type> using __use_branchless_sort = @@ -571,22 +579,28 @@ extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { +template +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + using _Comp_ref = typename __comp_ref_type<_Comp>::type; if (__libcpp_is_constant_evaluated()) { - _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); + std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); } else { - _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp)); + std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp)); } } +template +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { + std::__sort_impl(std::move(__first), std::move(__last), __comp); +} + template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void sort(_RandomAccessIterator __first, - _RandomAccessIterator __last) { - _VSTD::sort(__first, __last, __less::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::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 @@ -53,7 +53,6 @@ indirect_strict_weak_order, Proj>> Comp = ranges::less> constexpr borrowed_iterator_t ranges::max_element(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 - template S1, input_iterator I2, sentinel_for<_I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_comparable @@ -283,6 +282,17 @@ requires permutable> constexpr borrowed_iterator_t ranges::reverse(R&& r); // since C++20 + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + constexpr I + sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + constexpr borrowed_iterator_t + 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 @@ -1190,6 +1200,7 @@ #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.h> #include <__algorithm/ranges_reverse.h> +#include <__algorithm/ranges_sort.h> #include <__algorithm/ranges_swap_ranges.h> #include <__algorithm/ranges_transform.h> #include <__algorithm/ranges_upper_bound.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 @@ -284,6 +284,7 @@ module lexicographical_compare { private header "__algorithm/lexicographical_compare.h" } module lower_bound { private header "__algorithm/lower_bound.h" } module make_heap { private header "__algorithm/make_heap.h" } + module make_projected { private header "__algorithm/make_projected.h" } module max { private header "__algorithm/max.h" } module max_element { private header "__algorithm/max_element.h" } module merge { private header "__algorithm/merge.h" } @@ -341,6 +342,7 @@ module ranges_replace { private header "__algorithm/ranges_replace.h" } module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" } module ranges_reverse { private header "__algorithm/ranges_reverse.h" } + module ranges_sort { private header "__algorithm/ranges_sort.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" } module ranges_transform { private header "__algorithm/ranges_transform.h" } module ranges_upper_bound { private header "__algorithm/ranges_upper_bound.h" } diff --git a/libcxx/src/algorithm.cpp b/libcxx/src/algorithm.cpp --- a/libcxx/src/algorithm.cpp +++ b/libcxx/src/algorithm.cpp @@ -10,6 +10,8 @@ _LIBCPP_BEGIN_NAMESPACE_STD +// TODO(varconst): this currently doesn't benefit `ranges::sort` because it uses `ranges::less` instead of `__less`. + template void __sort<__less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS template void __sort<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); 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 @@ -207,8 +207,8 @@ //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0); - //(void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0); - //(void)std::ranges::sort(a, Less(&copies)); assert(copies == 0); + (void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0); + (void)std::ranges::sort(a, Less(&copies)); assert(copies == 0); //(void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0); //(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); } 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 @@ -198,8 +198,8 @@ //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); //(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); } 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 @@ -82,6 +82,7 @@ #include <__algorithm/lexicographical_compare.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/lexicographical_compare.h'}} #include <__algorithm/lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/lower_bound.h'}} #include <__algorithm/make_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/make_heap.h'}} +#include <__algorithm/make_projected.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/make_projected.h'}} #include <__algorithm/max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/max.h'}} #include <__algorithm/max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/max_element.h'}} #include <__algorithm/merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/merge.h'}} @@ -139,6 +140,7 @@ #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_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_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/sort/ranges.sort.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp @@ -0,0 +1,216 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// constexpr I +// sort(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 +// +// template +// requires sortable, Comp, Proj> +// constexpr borrowed_iterator_t +// 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 HasSortIt = requires(Iter first, Sent last, Comp comp) { std::ranges::sort(first, last, comp); }; + +static_assert(HasSortIt); +static_assert(!HasSortIt); +static_assert(!HasSortIt); +static_assert(!HasSortIt); +static_assert(!HasSortIt); +static_assert(!HasSortIt); +static_assert(!HasSortIt); // Doesn't satisfy `sortable`. + +template +concept HasSortR = requires(Range range, Comp comp) { std::ranges::sort(range, comp); }; + +static_assert(HasSortR>); +static_assert(!HasSortR); +static_assert(!HasSortR); +static_assert(!HasSortR>); +static_assert(!HasSortR>); +static_assert(!HasSortR, BadComparator>); +static_assert(!HasSortR>); // Doesn't satisfy `sortable`. + +template +constexpr 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::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::sort(range); + assert(sorted == expected); + assert(base(last) == sorted.data() + sorted.size()); + } +} + +template +constexpr 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 +constexpr void test_iterators_1() { + test_iterators_2(); + test_iterators_2>(); +} + +constexpr void test_iterators() { + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1(); +} + +constexpr bool test() { + test_iterators(); + + { // A custom comparator works. + { + std::array in = {1, 2, 3, 4, 5}; + auto last = std::ranges::sort(in.begin(), in.end(), std::ranges::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::sort(in, std::ranges::greater{}); + assert((in == std::array{5, 4, 3, 2, 1})); + assert(last == in.end()); + } + } + + { // A custom projection works. + struct A { + int a; + constexpr bool operator==(const A&) const = default; + }; + + { + std::array in = {A{2}, A{3}, A{1}}; + auto last = std::ranges::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::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; + constexpr S(int i_) : i(i_) {} + + constexpr bool comparator(const S& rhs) const { return i < rhs.i; } + constexpr const S& projection() const { return *this; } + + constexpr bool operator==(const S&) const = default; + }; + + { + std::array in = {S{2}, S{3}, S{1}}; + auto last = std::ranges::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::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::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::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::sort(std::array{1, 2, 3}); + } + + 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 @@ -137,7 +137,7 @@ //static_assert(test(std::ranges::set_symmetric_difference, a, a, a)); //static_assert(test(std::ranges::set_union, a, a, a)); //static_assert(test(std::ranges::shuffle, a, g)); -//static_assert(test(std::ranges::sort, a)); +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)); 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 @@ -317,4 +317,83 @@ static_assert(!std::indirect_binary_predicate); +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); + + auto operator<=>(const Self&) const = default; +}; + +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