diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -186,6 +186,7 @@ formatter_int.bench.cpp function.bench.cpp join_view.bench.cpp + lexicographical_compare_three_way.bench.cpp map.bench.cpp monotonic_buffer.bench.cpp ordered_set.bench.cpp diff --git a/libcxx/benchmarks/lexicographical_compare_three_way.bench.cpp b/libcxx/benchmarks/lexicographical_compare_three_way.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/lexicographical_compare_three_way.bench.cpp @@ -0,0 +1,96 @@ +//===----------------------------------------------------------------------===// +// 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 "benchmark/benchmark.h" +#include "test_iterators.h" + +static void BM_lexicographical_compare_three_way_slow_path(benchmark::State& state) { + auto size = state.range(0); + std::vector v1; + v1.resize(size); + // v2 is identical except for the last value. + // This means, that `lexicographical_compare_three_way` actually has to + // compare the complete vector and cannot bail out early. + std::vector v2 = v1; + v2.back() += 1; + int* b1 = v1.data(); + int* e1 = b1 + v1.size(); + int* b2 = v2.data(); + int* e2 = b2 + v2.size(); + + for (auto _ : state) { + auto cmp = std::compare_three_way(); + benchmark::DoNotOptimize(std::__lexicographical_compare_three_way_slow_path(b1, e1, b2, e2, cmp)); + } +} + +BENCHMARK(BM_lexicographical_compare_three_way_slow_path)->RangeMultiplier(4)->Range(1, 1 << 20); + +static void BM_lexicographical_compare_three_way_fast_path(benchmark::State& state) { + auto size = state.range(0); + std::vector v1; + v1.resize(size); + // v2 is identical except for the last value. + // This means, that `lexicographical_compare_three_way` actually has to + // compare the complete vector and cannot bail out early. + std::vector v2 = v1; + v2.back() += 1; + int* b1 = v1.data(); + int* e1 = b1 + v1.size(); + int* b2 = v2.data(); + int* e2 = b2 + v2.size(); + + for (auto _ : state) { + auto cmp = std::compare_three_way(); + benchmark::DoNotOptimize(std::__lexicographical_compare_three_way_fast_path(b1, e1, b2, e2, cmp)); + } +} + +BENCHMARK(BM_lexicographical_compare_three_way_fast_path)->RangeMultiplier(4)->Range(1, 1 << 20); + +template +static void BM_lexicographical_compare_three_way(benchmark::State& state) { + auto size = state.range(0); + std::vector v1; + v1.resize(size); + // v2 is identical except for the last value. + // This means, that `lexicographical_compare_three_way` actually has to + // compare the complete vector and cannot bail out early. + std::vector v2 = v1; + v2.back() += 1; + auto b1 = IteratorT{v1.data()}; + auto e1 = IteratorT{v1.data() + v1.size()}; + auto b2 = IteratorT{v2.data()}; + auto e2 = IteratorT{v2.data() + v2.size()}; + + for (auto _ : state) { + benchmark::DoNotOptimize(std::lexicographical_compare_three_way(b1, e1, b2, e2)); + } +} + +// Type alias to make sure the `*` does not appear in the benchmark name. +// A `*` would confuse the Python test runner running this google benchmark. +using IntPtr = int*; + +// `lexicographical_compare_three_way` has a fast path for random access iterators. +BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, IntPtr)->RangeMultiplier(4)->Range(1, 1 << 20); +BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, random_access_iterator) + ->RangeMultiplier(4) + ->Range(1, 1 << 20); +BENCHMARK_TEMPLATE(BM_lexicographical_compare_three_way, cpp17_input_iterator) + ->RangeMultiplier(4) + ->Range(1, 1 << 20); + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + benchmark::RunSpecifiedBenchmarks(); +} diff --git a/libcxx/docs/Status/Cxx20Issues.csv b/libcxx/docs/Status/Cxx20Issues.csv --- a/libcxx/docs/Status/Cxx20Issues.csv +++ b/libcxx/docs/Status/Cxx20Issues.csv @@ -262,7 +262,8 @@ "`3347 `__","``std::pair``\ now requires ``T``\ and ``U``\ to be less-than-comparable","Prague","","" "`3348 `__","``__cpp_lib_unwrap_ref``\ in wrong header","Prague","|Complete|","12.0" "`3349 `__","Missing ``__cpp_lib_constexpr_complex``\ for P0415R1","Prague","|Complete|","16.0" -"`3350 `__","Simplify return type of ``lexicographical_compare_three_way``\ ","Prague","","","|spaceship|" +"`3349 `__","Missing ``__cpp_lib_constexpr_complex``\ for P0415R1","Prague","","" +"`3350 `__","Simplify return type of ``lexicographical_compare_three_way``\ ","Prague","|Complete|","17.0","|spaceship|" "`3351 `__","``ranges::enable_safe_range``\ should not be constrained","Prague","|Complete|","15.0","|ranges|" "`3352 `__","``strong_equality``\ isn't a thing","Prague","|Nothing To Do|","","|spaceship|" "`3354 `__","``has_strong_structural_equality``\ has a meaningless definition","Prague","|Nothing To Do|","","|spaceship|" diff --git a/libcxx/docs/Status/Cxx2bIssues.csv b/libcxx/docs/Status/Cxx2bIssues.csv --- a/libcxx/docs/Status/Cxx2bIssues.csv +++ b/libcxx/docs/Status/Cxx2bIssues.csv @@ -63,7 +63,7 @@ `2774 `__,"``std::function`` construction vs assignment","June 2021","","" `2818 `__,"``::std::`` everywhere rule needs tweaking","June 2021","|Nothing To Do|","" `2997 `__,"LWG 491 and the specification of ``{forward_,}list::unique``","June 2021","","" -`3410 `__,"``lexicographical_compare_three_way`` is overspecified","June 2021","","","|spaceship|" +`3410 `__,"``lexicographical_compare_three_way`` is overspecified","June 2021","|Complete|","17.0","|spaceship|" `3430 `__,"``std::fstream`` & co. should be constructible from string_view","June 2021","","" `3462 `__,"ยง[formatter.requirements]: Formatter requirements forbid use of ``fc.arg()``","June 2021","","","|format|" `3481 `__,"``viewable_range`` mishandles lvalue move-only views","June 2021","Superseded by `P2415R2 `__","","|ranges|" diff --git a/libcxx/docs/Status/SpaceshipProjects.csv b/libcxx/docs/Status/SpaceshipProjects.csv --- a/libcxx/docs/Status/SpaceshipProjects.csv +++ b/libcxx/docs/Status/SpaceshipProjects.csv @@ -11,7 +11,7 @@ | `strong_order_fallback `_ | `weak_order_fallback `_ | `partial_order_fallback `_",None,Arthur O'Dwyer,|Complete| [#note-strongorder]_ -| `[alg.three.way] `_,| `lexicographical_compare_three_way `_,[comparisons.three.way],Adrian Vogelsgesang,|In Progress| +| `[alg.three.way] `_,| `lexicographical_compare_three_way `_,[comparisons.three.way],Adrian Vogelsgesang,|Complete| | `[type.info] `_,| `typeinfo `_,None,Adrian Vogelsgesang,|Complete| | `[coroutine.handle.compare] `_,| `coroutine_handle `_,[comparisons.three.way],Chuanqi Xu,|Complete| | `[pairs.spec] `_,| `pair `_,[expos.only.func],Kent Ross,|Complete| diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -44,6 +44,7 @@ __algorithm/iter_swap.h __algorithm/iterator_operations.h __algorithm/lexicographical_compare.h + __algorithm/lexicographical_compare_three_way.h __algorithm/lower_bound.h __algorithm/make_heap.h __algorithm/make_projected.h @@ -183,6 +184,7 @@ __algorithm/stable_partition.h __algorithm/stable_sort.h __algorithm/swap_ranges.h + __algorithm/three_way_comp_ref_type.h __algorithm/transform.h __algorithm/uniform_random_bit_generator_adaptor.h __algorithm/unique.h diff --git a/libcxx/include/__algorithm/lexicographical_compare_three_way.h b/libcxx/include/__algorithm/lexicographical_compare_three_way.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/lexicographical_compare_three_way.h @@ -0,0 +1,125 @@ +//===----------------------------------------------------------------------===// +// +// 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_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H +#define _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H + +#include <__algorithm/min.h> +#include <__algorithm/three_way_comp_ref_type.h> +#include <__compare/compare_three_way.h> +#include <__compare/ordering.h> +#include <__concepts/arithmetic.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__type_traits/common_type.h> +#include <__type_traits/is_copy_constructible.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 + +// Fast path for random access iterators which computes the number of loop iterations up-front and +// then skips the iterator comparisons inside the loop. +template +_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path( + _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp) + -> decltype(__comp(*__first1, *__first2)) { + static_assert( + signed_integral<__iter_diff_t<_InputIterator1>>, "Using a non-integral difference_type is undefined behavior."); + static_assert( + signed_integral<__iter_diff_t<_InputIterator2>>, "Using a non-integral difference_type is undefined behavior."); + + using _Len1 = __iter_diff_t<_InputIterator1>; + using _Len2 = __iter_diff_t<_InputIterator2>; + using _Common = common_type_t<_Len1, _Len2>; + + _Len1 __len1 = __last1 - __first1; + _Len2 __len2 = __last2 - __first2; + _Common __min_len = std::min<_Common>(__len1, __len2); + + for (_Common __i = 0; __i < __min_len; ++__i) { + auto __c = __comp(*__first1, *__first2); + if (__c != 0) { + return __c; + } + ++__first1; + ++__first2; + } + + return __len1 <=> __len2; +} + +// Unoptimized implementation which compares the iterators against the end in every loop iteration +template +_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_slow_path( + _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp) + -> decltype(__comp(*__first1, *__first2)) { + while (true) { + bool __exhausted1 = __first1 == __last1; + bool __exhausted2 = __first2 == __last2; + + if (__exhausted1 || __exhausted2) { + if (!__exhausted1) + return strong_ordering::greater; + if (!__exhausted2) + return strong_ordering::less; + return strong_ordering::equal; + } + + auto __c = __comp(*__first1, *__first2); + if (__c != 0) { + return __c; + } + + ++__first1; + ++__first2; + } +} + +template +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way( + _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp __comp) + -> decltype(__comp(*__first1, *__first2)) { + static_assert(__comparison_category, + "The comparator passed to lexicographical_compare_three_way must return a comparison category type."); + static_assert(std::is_copy_constructible_v<_InputIterator1>, "Iterators must be copy constructible."); + static_assert(std::is_copy_constructible_v<_InputIterator2>, "Iterators must be copy constructible."); + __three_way_comp_ref_type<_Cmp> __wrapped_comp_ref(__comp); + if constexpr (__is_cpp17_random_access_iterator<_InputIterator1>::value && + __is_cpp17_random_access_iterator<_InputIterator2>::value) { + return std::__lexicographical_compare_three_way_fast_path( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref); + } else { + // Unoptimized implementation which compares the iterators against the end in every loop iteration + return std::__lexicographical_compare_three_way_slow_path( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref); + } +} + +template +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way( + _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { + return std::lexicographical_compare_three_way( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::compare_three_way()); +} + +#endif // _LIBCPP_STD_VER > 17 + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H diff --git a/libcxx/include/__algorithm/three_way_comp_ref_type.h b/libcxx/include/__algorithm/three_way_comp_ref_type.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/three_way_comp_ref_type.h @@ -0,0 +1,70 @@ +//===----------------------------------------------------------------------===// +// +// 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_THREE_WAY_COMP_REF_TYPE_H +#define _LIBCPP___ALGORITHM_THREE_WAY_COMP_REF_TYPE_H + +#include <__compare/ordering.h> +#include <__config> +#include <__debug> +#include <__utility/declval.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 + +template +struct __debug_three_way_comp { + _Comp& __comp_; + _LIBCPP_HIDE_FROM_ABI constexpr __debug_three_way_comp(_Comp& __c) : __comp_(__c) {} + + template + _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y) { + auto __r = __comp_(__x, __y); + __do_compare_assert(0, __y, __x, __r); + return __r; + } + + template + _LIBCPP_HIDE_FROM_ABI constexpr inline void __do_compare_assert(int, _LHS& __l, _RHS& __r, _Order __o) + requires __comparison_category()(declval<_LHS&>(), declval<_RHS&>()))> + { + _Order __expected = __o; + if (__o == _Order::less) + __expected = _Order::greater; + if (__o == _Order::greater) + __expected = _Order::less; + _LIBCPP_DEBUG_ASSERT(__comp_(__l, __r) == __expected, "Comparator does not induce a strict weak ordering"); + (void)__l; + (void)__r; + (void)__expected; + } + + template + _LIBCPP_HIDE_FROM_ABI constexpr inline void __do_compare_assert(long, _LHS&, _RHS&, _Order) {} +}; + +// Pass the comparator by lvalue reference. Or in debug mode, using a +// debugging wrapper that stores a reference. +# ifndef _LIBCPP_ENABLE_DEBUG_MODE +template +using __three_way_comp_ref_type = __debug_three_way_comp<_Comp>; +# else +template +using __three_way_comp_ref_type = _Comp&; +# endif + +#endif // _LIBCPP_STD_VER > 17 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_THREE_WAY_COMP_REF_TYPE_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1684,6 +1684,18 @@ lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); +template + constexpr auto + lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2, + Cmp comp) + -> decltype(comp(*b1, *b2)); // since C++20 + +template + constexpr auto + lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2); // since C++20 + template constexpr bool // constexpr in C++20 next_permutation(BidirectionalIterator first, BidirectionalIterator last); @@ -1753,6 +1765,7 @@ #include <__algorithm/is_sorted_until.h> #include <__algorithm/iter_swap.h> #include <__algorithm/lexicographical_compare.h> +#include <__algorithm/lexicographical_compare_three_way.h> #include <__algorithm/lower_bound.h> #include <__algorithm/make_heap.h> #include <__algorithm/max.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 @@ -286,6 +286,9 @@ export * } module lexicographical_compare { private header "__algorithm/lexicographical_compare.h" } + module lexicographical_compare_three_way { + private header "__algorithm/lexicographical_compare_three_way.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" } @@ -596,6 +599,7 @@ module stable_partition { private header "__algorithm/stable_partition.h" } module stable_sort { private header "__algorithm/stable_sort.h" } module swap_ranges { private header "__algorithm/swap_ranges.h" } + module three_way_comp_ref_type { private header "__algorithm/three_way_comp_ref_type.h" } module transform { private header "__algorithm/transform.h" } module unique { private header "__algorithm/unique.h" } module unique_copy { private header "__algorithm/unique_copy.h" } diff --git a/libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp @@ -79,12 +79,13 @@ }; #if TEST_STD_VER > 17 +template struct ThreeWay { int *copies_; constexpr explicit ThreeWay(int *copies) : copies_(copies) {} constexpr ThreeWay(const ThreeWay& rhs) : copies_(rhs.copies_) { *copies_ += 1; } constexpr ThreeWay& operator=(const ThreeWay&) = default; - constexpr std::strong_ordering operator()(void*, void*) const { return std::strong_ordering::equal; } + constexpr std::strong_ordering operator()(T, T) const { return std::strong_ordering::equal; } }; #endif @@ -142,7 +143,7 @@ if (!TEST_IS_CONSTANT_EVALUATED) { (void)std::inplace_merge(first, mid, last, Less(&copies)); assert(copies == 0); } (void)std::lexicographical_compare(first, last, first2, last2, Less(&copies)); assert(copies == 0); #if TEST_STD_VER > 17 - //(void)std::lexicographical_compare_three_way(first, last, first2, last2, ThreeWay(&copies)); assert(copies == 0); + (void)std::lexicographical_compare_three_way(first, last, first2, last2, ThreeWay(&copies)); assert(copies == 0); #endif (void)std::lower_bound(first, last, value, Less(&copies)); assert(copies == 0); (void)std::make_heap(first, last, Less(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/robust_against_cpp20_hostile_iterators.compile.pass.cpp b/libcxx/test/libcxx/algorithms/robust_against_cpp20_hostile_iterators.compile.pass.cpp --- a/libcxx/test/libcxx/algorithms/robust_against_cpp20_hostile_iterators.compile.pass.cpp +++ b/libcxx/test/libcxx/algorithms/robust_against_cpp20_hostile_iterators.compile.pass.cpp @@ -138,6 +138,10 @@ (void) std::is_sorted(it, it, pred); (void) std::lexicographical_compare(it, it, it, it); (void) std::lexicographical_compare(it, it, it, it, pred); +#if TEST_STD_VER > 17 + (void)std::lexicographical_compare_three_way(it, it, it, it); + (void)std::lexicographical_compare_three_way(it, it, it, it, std::compare_three_way()); +#endif (void) std::lower_bound(it, it, 0); (void) std::lower_bound(it, it, 0, pred); (void) std::make_heap(it, it); diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp --- a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp @@ -174,6 +174,14 @@ std::lexicographical_compare(std::begin(arr), std::end(arr), std::begin(arr), std::end(arr), std::greater()); +#if TEST_STD_VER >= 20 + // expected-warning@+1 {{ignoring return value of function declared with 'nodiscard' attribute}} + std::lexicographical_compare_three_way(std::begin(arr), std::end(arr), std::begin(arr), std::end(arr)); + + // expected-warning@+1 {{ignoring return value of function declared with 'nodiscard' attribute}} + std::lexicographical_compare_three_way(std::begin(arr), std::end(arr), std::begin(arr), std::end(arr), std::compare_three_way()); +#endif + // expected-warning@+1 {{ignoring return value of function declared with 'nodiscard' attribute}} std::lower_bound(std::begin(arr), std::end(arr), 1); 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 @@ -81,6 +81,7 @@ #include <__algorithm/iter_swap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/iter_swap.h'}} #include <__algorithm/iterator_operations.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/iterator_operations.h'}} #include <__algorithm/lexicographical_compare.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/lexicographical_compare.h'}} +#include <__algorithm/lexicographical_compare_three_way.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/lexicographical_compare_three_way.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'}} @@ -220,6 +221,7 @@ #include <__algorithm/stable_partition.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/stable_partition.h'}} #include <__algorithm/stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/stable_sort.h'}} #include <__algorithm/swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/swap_ranges.h'}} +#include <__algorithm/three_way_comp_ref_type.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/three_way_comp_ref_type.h'}} #include <__algorithm/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/transform.h'}} #include <__algorithm/uniform_random_bit_generator_adaptor.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/uniform_random_bit_generator_adaptor.h'}} #include <__algorithm/unique.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/unique.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp @@ -0,0 +1,122 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// + +// template +// constexpr auto +// lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, +// InputIterator2 first2, InputIterator2 last2) + +#include +#include +#include +#include +#include + +#include "test_macros.h" +#include "test_comparisons.h" +#include "test_iterators.h" + +template +constexpr void test_lexicographical_compare(C1 a, C2 b, Order expected) { + std::same_as decltype(auto) result = + std::lexicographical_compare_three_way(Iter1{a.begin()}, Iter1{a.end()}, Iter2{b.begin()}, Iter2{b.end()}); + assert(expected == result); +} + +template +constexpr void test_given_iterator_types() { + // Both inputs empty + test_lexicographical_compare(std::array{}, std::array{}, std::strong_ordering::equal); + // Left input empty + test_lexicographical_compare(std::array{}, std::array{0, 1}, std::strong_ordering::less); + // Right input empty + test_lexicographical_compare(std::array{0, 1}, std::array{}, std::strong_ordering::greater); + + // Identical arrays + test_lexicographical_compare(std::array{0, 1}, std::array{0, 1}, std::strong_ordering::equal); + // "Less" on 2nd element + test_lexicographical_compare(std::array{0, 1}, std::array{0, 2}, std::strong_ordering::less); + // "Greater" on 2nd element + test_lexicographical_compare(std::array{0, 2}, std::array{0, 1}, std::strong_ordering::greater); + // "Greater" on 2nd element, but "less" on first entry + test_lexicographical_compare(std::array{0, 2}, std::array{1, 1}, std::strong_ordering::less); + // Identical elements, but longer + test_lexicographical_compare(std::array{0, 1}, std::array{0, 1, 2}, std::strong_ordering::less); + // Identical elements, but shorter + test_lexicographical_compare(std::array{0, 1, 2}, std::array{0, 1}, std::strong_ordering::greater); +} + +template +constexpr void test_iterator_types1() { + test_given_iterator_types(); + test_given_iterator_types(); + test_given_iterator_types>(); + test_given_iterator_types>(); + test_given_iterator_types>(); + test_given_iterator_types>(); + test_given_iterator_types>(); +} + +constexpr void test_iterator_types() { + // Exhaustively test all combinations of `int*`, `const int*`, `cpp17_input_iterator`, + // `forward_iterator`, `bidirectional_iterator`, `random_access_iterator`, + // `contiguous_iterator`. + // + // `lexicographical_compare_three_way` has a fast path which triggers if both + // iterators are random access iterators. + + test_iterator_types1(); + test_iterator_types1(); + test_iterator_types1>(); + test_iterator_types1>(); + test_iterator_types1>(); + test_iterator_types1>(); + test_iterator_types1>(); +} + +// Check for other comparison categories +constexpr void test_comparison_categories() { + // Check all comparison categories for inputs with a difference in the contained elements + test_lexicographical_compare( + std::array{0, 1}, std::array{1, 1}, std::strong_ordering::less); + test_lexicographical_compare( + std::array{0, 1}, std::array{1, 1}, std::weak_ordering::less); + test_lexicographical_compare( + std::array{0, 1}, std::array{1, 1}, std::partial_ordering::less); + + // Check comparison categories with arrays of different sizes + test_lexicographical_compare( + std::array{0, 1}, std::array{0, 1, 2}, std::strong_ordering::less); + test_lexicographical_compare( + std::array{0, 1}, std::array{0, 1, 2}, std::weak_ordering::less); + test_lexicographical_compare( + std::array{0, 1}, std::array{0, 1, 2}, std::partial_ordering::less); + + // Check for a `partial_ordering::unordered` result + test_lexicographical_compare( + std::array{std::numeric_limits::min(), 1}, + std::array{0, 1, 2}, + std::partial_ordering::unordered); +} + +constexpr bool test() { + test_iterator_types(); + test_comparison_categories(); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp @@ -0,0 +1,174 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// + +// template +// constexpr auto +// lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, +// InputIterator2 first2, InputIterator2 last2, +// Cmp comp) +// -> decltype(comp(*b1, *b2)); + +#include +#include +#include +#include +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" + +using std::array; + +constexpr auto compare_last_digit_strong = [](int a, int b) -> std::strong_ordering { return (a % 10) <=> (b % 10); }; +constexpr auto compare_last_digit_weak = [](int a, int b) -> std::weak_ordering { return (a % 10) <=> (b % 10); }; +constexpr auto compare_last_digit_partial = [](int a, int b) -> std::partial_ordering { + if (a == std::numeric_limits::min() || b == std::numeric_limits::min()) + return std::partial_ordering::unordered; + return (a % 10) <=> (b % 10); +}; +constexpr auto compare_int_result = [](int a, int b) -> int { return (a % 10) - (b % 10); }; + +struct StructWithoutCallOperator {}; + +template +concept has_lexicographical_compare = + requires(int* ptr, T comp) { std::lexicographical_compare_three_way(ptr, ptr, ptr, ptr, comp); }; + +// `std::lexicographical_compare_three_way` accepts valid types +static_assert(has_lexicographical_compare); +static_assert(has_lexicographical_compare); +static_assert(has_lexicographical_compare); +// `std::lexicographical_compare_three_way` rejects non-invocable comparators +static_assert(!has_lexicographical_compare); +// `std::lexicographical_compare_three_way` accepts invalid comparators returning a wrong type. +// This will trigger a `static_assert` only when actually invoking `has_lexicographical_compare`. +static_assert(has_lexicographical_compare); + +template +constexpr void test_lexicographical_compare(C1 a, C2 b, Comparator comp, Order expected) { + std::same_as decltype(auto) result = + std::lexicographical_compare_three_way(Iter1{a.begin()}, Iter1{a.end()}, Iter2{b.begin()}, Iter2{b.end()}, comp); + assert(expected == result); +} + +template +constexpr void test_given_iterator_types() { + auto cmp = compare_last_digit_strong; + // Both inputs empty + test_lexicographical_compare( + std::array{}, std::array{}, cmp, std::strong_ordering::equal); + // Left input empty + test_lexicographical_compare(std::array{}, std::array{0, 1}, cmp, std::strong_ordering::less); + // Right input empty + test_lexicographical_compare( + std::array{0, 1}, std::array{}, cmp, std::strong_ordering::greater); + + // Identical arrays + test_lexicographical_compare(std::array{0, 1}, std::array{0, 1}, cmp, std::strong_ordering::equal); + // "Less" on 2nd element + test_lexicographical_compare(std::array{0, 1}, std::array{0, 2}, cmp, std::strong_ordering::less); + // "Greater" on 2nd element + test_lexicographical_compare(std::array{0, 2}, std::array{0, 1}, cmp, std::strong_ordering::greater); + // "Greater" on 2nd element, but "less" on first entry + test_lexicographical_compare(std::array{0, 2}, std::array{1, 1}, cmp, std::strong_ordering::less); + // Identical elements, but longer + test_lexicographical_compare(std::array{0, 1}, std::array{0, 1, 2}, cmp, std::strong_ordering::less); + // Identical elements, but shorter + test_lexicographical_compare(std::array{0, 1, 2}, std::array{0, 1}, cmp, std::strong_ordering::greater); + // Identical arrays, but only if we take the comparator + // into account instead of using the default comparator + test_lexicographical_compare(std::array{10, 21}, std::array{10, 31}, cmp, std::strong_ordering::equal); +} + +template +constexpr void test_iterator_types1() { + test_given_iterator_types(); + test_given_iterator_types(); + test_given_iterator_types>(); + test_given_iterator_types>(); + test_given_iterator_types>(); + test_given_iterator_types>(); + test_given_iterator_types>(); +} + +constexpr void test_iterator_types() { + // Exhaustively test all combinations of `int*`, `const int*`, `cpp17_input_iterator`, + // `forward_iterator`, `bidirectional_iterator`, `random_access_iterator`, + // `contiguous_iterator`. + // + // `lexicographical_compare_three_way` has a fast path which triggers if both + // iterators are random access iterators. + + test_iterator_types1(); + test_iterator_types1(); + test_iterator_types1>(); + test_iterator_types1>(); + test_iterator_types1>(); + test_iterator_types1>(); + test_iterator_types1>(); +} + +// Check for other comparison categories +constexpr void test_comparison_categories() { + test_lexicographical_compare( + std::array{0, 1}, std::array{10, 11}, compare_last_digit_weak, std::weak_ordering::equivalent); + test_lexicographical_compare( + std::array{0, 1}, std::array{20, 11}, compare_last_digit_partial, std::partial_ordering::equivalent); + + // Check for all comparison categories with arrays of different sizes + test_lexicographical_compare( + std::array{0}, std::array{0, 1}, compare_last_digit_strong, std::strong_ordering::less); + test_lexicographical_compare( + std::array{0}, std::array{0, 1}, compare_last_digit_weak, std::weak_ordering::less); + test_lexicographical_compare( + std::array{0}, std::array{0, 1}, compare_last_digit_partial, std::partial_ordering::less); + + // Check for a `partial_ordering::unordered` result + test_lexicographical_compare( + std::array{std::numeric_limits::min(), 1}, + std::array{0, 1, 2}, + compare_last_digit_partial, + std::partial_ordering::unordered); +} + +// Test for "Complexity: At most N applications of comp." +constexpr void test_comparator_invocation_count() { + int compare_invocation_count = 0; + auto compare_last_digit_counting = [&](int a, int b) -> std::strong_ordering { + ++compare_invocation_count; + return (a % 10) <=> (b % 10); + }; + // If one of the ranges is empty, the comparator must not be called at all + compare_invocation_count = 0; + test_lexicographical_compare( + std::array{0, 1, 2, 3}, std::array{}, compare_last_digit_counting, std::strong_ordering::greater); + assert(compare_invocation_count == 0); + // The comparator is invoked only `min(left.size(), right.size())` times + test_lexicographical_compare( + std::array{0, 1, 2}, std::array{0, 1, 2, 3}, compare_last_digit_counting, std::strong_ordering::less); + assert(compare_invocation_count == 3); +} + +constexpr bool test() { + test_iterator_types(); + test_comparison_categories(); + test_comparator_invocation_count(); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.verify.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.verify.cpp @@ -0,0 +1,47 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// + +// template +// constexpr auto +// lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1, +// InputIterator2 first2, InputIterator2 last2, +// Cmp comp) +// -> decltype(comp(*b1, *b2)); + +#include +#include +#include +#include + +#include "test_macros.h" +#include "almost_satisfies_types.h" + +constexpr bool incorrect_comparator(int a, int b) { return a < b; } + +auto test_incorrect_comparator() { + std::array a{90, 81}; + std::array b{10, 11}; + // expected-error-re@*:* {{{{(static_assert|static assertion)}} failed{{.*}}The comparator passed to lexicographical_compare_three_way must return a comparison category type}} + // expected-error@*:* {{no viable conversion}} + return std::lexicographical_compare_three_way(a.begin(), a.end(), b.begin(), b.end(), incorrect_comparator); +} + +auto test_invalid_difference_type_first( + RandomAccessIteratorBadDifferenceType a, RandomAccessIteratorBadDifferenceType b, int* c, int* d) { + // expected-error-re@*:* {{{{(static_assert|static assertion)}} failed{{.*}}Using a non-integral difference_type is undefined behavior}}}} + return std::lexicographical_compare_three_way(a, b, c, d, std::compare_three_way()); +} + +auto test_invalid_difference_type_second( + int* a, int* b, RandomAccessIteratorBadDifferenceType c, RandomAccessIteratorBadDifferenceType d) { + // expected-error-re@*:* {{{{(static_assert|static assertion)}} failed{{.*}}Using a non-integral difference_type is undefined behavior}}}} + return std::lexicographical_compare_three_way(a, b, c, d, std::compare_three_way()); +} diff --git a/libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp b/libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp --- a/libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp +++ b/libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp @@ -108,7 +108,10 @@ // RELIES ON ADL SWAP (void)std::iter_swap(first, mid); (void)std::lexicographical_compare(first, last, first2, last2); (void)std::lexicographical_compare(first, last, first2, last2, std::less()); - // TODO: lexicographical_compare_three_way +#if TEST_STD_VER > 17 + (void)std::lexicographical_compare_three_way(first, last, first2, last2); + (void)std::lexicographical_compare_three_way(first, last, first2, last2, std::compare_three_way()); +#endif (void)std::lower_bound(first, last, value); (void)std::lower_bound(first, last, value, std::less()); (void)std::make_heap(first, last); diff --git a/libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp b/libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp --- a/libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp +++ b/libcxx/test/std/algorithms/robust_re_difference_type.compile.pass.cpp @@ -145,7 +145,12 @@ (void)std::iter_swap(first, mid); (void)std::lexicographical_compare(first, last, first2, last2); (void)std::lexicographical_compare(first, last, first2, last2, std::less()); - // TODO: lexicographical_compare_three_way +#if TEST_STD_VER > 17 + // `lexicographical_compare_three_way` static_asserts that the difference type is an integer, as + // required by https://eel.is/c++draft/iterator.iterators#2.2 + //(void)std::lexicographical_compare_three_way(first, last, first2, last2); + //(void)std::lexicographical_compare_three_way(first, last, first2, last2, std::compare_three_way()); +#endif (void)std::lower_bound(first, last, value); (void)std::lower_bound(first, last, value, std::less()); (void)std::make_heap(first, last); 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 @@ -389,6 +389,39 @@ using RandomAccessRangeBadIndex = UncheckedRange; +class RandomAccessIteratorBadDifferenceType { + using Self = RandomAccessIteratorBadDifferenceType; + +public: + using value_type = int; + // Deliberately use a non-integer `difference_type` + using difference_type = double; + using pointer = double*; + using reference = double&; + using iterator_category = std::random_access_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::regular); +static_assert(!std::weakly_incrementable); +static_assert(!std::random_access_iterator); + template class ComparatorNotCopyable { public: diff --git a/libcxx/test/support/test_comparisons.h b/libcxx/test/support/test_comparisons.h --- a/libcxx/test/support/test_comparisons.h +++ b/libcxx/test/support/test_comparisons.h @@ -24,7 +24,9 @@ #define TEST_COMPARISONS_H #include +#include #include +#include #include #include @@ -238,4 +240,33 @@ return lhs.value == rhs.value; } }; + +#if TEST_STD_VER > 17 +struct StrongOrder { + int value; + constexpr StrongOrder(int v) : value(v) {} + friend std::strong_ordering operator<=>(StrongOrder, StrongOrder) = default; +}; + +struct WeakOrder { + int value; + constexpr WeakOrder(int v) : value(v) {} + friend std::weak_ordering operator<=>(WeakOrder, WeakOrder) = default; +}; + +struct PartialOrder { + int value; + constexpr PartialOrder(int v) : value(v) {} + friend constexpr std::partial_ordering operator<=>(PartialOrder lhs, PartialOrder rhs) { + if (lhs.value == std::numeric_limits::min() || rhs.value == std::numeric_limits::min()) + return std::partial_ordering::unordered; + return lhs.value <=> rhs.value; + } + friend constexpr bool operator==(PartialOrder lhs, PartialOrder rhs) { + return (lhs <=> rhs) == std::partial_ordering::equivalent; + } +}; + +#endif + #endif // TEST_COMPARISONS_H