From 2a06757a200cc8dd4c3aeca98509d50d75bb4a27 Mon Sep 17 00:00:00 2001 From: Adrian Vogelsgesang Date: Thu, 4 Aug 2022 15:21:27 -0700 Subject: [PATCH] [libc++][spaceship] Implement `lexicographical_compare_three_way` The implementation makes use of the freedom added by LWG 3410. We have two variants of this algorithm: * a fast path for random access iterators: This fast path computes the maximum number of loop iterations up-front and does not compare the iterators against their limits on every loop iteration. * A basic implementation for all other iterators: This implementation compares the iterators against their limits in every loop iteration. However, it still takes advantage of the freedom added by LWG 3410 to avoid unnecessary additional iterator comparisons, as originally specified by P1614R2. https://godbolt.org/z/7xbMEen5e shows the benefit of the fast path: The hot loop generated of `lexicographical_compare_three_way3` is more tight than for `lexicographical_compare_three_way1`. The added benchmark illustrates how this leads to a 30% - 50% performance improvement on integer vectors. Implements part of P1614R2 "The Mothership has Landed" Fixes LWG 3410 and LWG 3350 Differential Revision: https://reviews.llvm.org/D131395 --- libcxx/benchmarks/CMakeLists.txt | 1 + .../lexicographical_compare_three_way.bench.cpp | 96 ++++++++++++ libcxx/docs/Status/Cxx20Issues.csv | 3 +- libcxx/docs/Status/Cxx2bIssues.csv | 2 +- libcxx/docs/Status/SpaceshipProjects.csv | 2 +- libcxx/include/CMakeLists.txt | 2 + .../lexicographical_compare_three_way.h | 125 +++++++++++++++ .../include/__algorithm/three_way_comp_ref_type.h | 70 +++++++++ libcxx/include/algorithm | 13 ++ libcxx/include/module.modulemap.in | 4 + .../debug_three_way_comp.inconsistent.pass.cpp | 55 +++++++ .../robust_against_copying_comparators.pass.cpp | 5 +- ...gainst_cpp20_hostile_iterators.compile.pass.cpp | 4 + .../diagnostics/nodiscard_extensions.verify.cpp | 8 + libcxx/test/libcxx/private_headers.verify.cpp | 2 + .../lexicographical_compare_three_way.pass.cpp | 122 +++++++++++++++ ...lexicographical_compare_three_way_comp.pass.cpp | 174 +++++++++++++++++++++ ...xicographical_compare_three_way_comp.verify.cpp | 47 ++++++ .../algorithms/robust_against_adl.compile.pass.cpp | 5 +- .../robust_re_difference_type.compile.pass.cpp | 7 +- libcxx/test/support/almost_satisfies_types.h | 33 ++++ libcxx/test/support/test_comparisons.h | 31 ++++ 22 files changed, 804 insertions(+), 7 deletions(-) create mode 100644 libcxx/benchmarks/lexicographical_compare_three_way.bench.cpp create mode 100644 libcxx/include/__algorithm/lexicographical_compare_three_way.h create mode 100644 libcxx/include/__algorithm/three_way_comp_ref_type.h create mode 100644 libcxx/test/libcxx/algorithms/debug_three_way_comp.inconsistent.pass.cpp create mode 100644 libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp create mode 100644 libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp create mode 100644 libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.verify.cpp diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt index 7eb76ac..2c3c39e 100644 --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -186,6 +186,7 @@ set(BENCHMARK_TESTS 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 index 0000000..e58134a --- /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 index 0a7542e..588d29b 100644 --- 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 index dbcdcb3..2e0ea6e 100644 --- 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 index f732ec7..e09ef9e 100644 --- a/libcxx/docs/Status/SpaceshipProjects.csv +++ b/libcxx/docs/Status/SpaceshipProjects.csv @@ -11,7 +11,7 @@ Section,Description,Dependencies,Assignee,Complete | `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 index 602d6e7..0388df3 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -44,6 +44,7 @@ set(files __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 @@ set(files __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 index 0000000..919b418 --- /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 index 0000000..029a50b --- /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()(std::declval<_LHS&>(), std::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 index cb2d27c..52d9cc9 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1684,6 +1684,18 @@ template 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 @@ template #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 index d1e3b70..53bfd1a 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -286,6 +286,9 @@ module std [system] { 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 std [system] { 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/debug_three_way_comp.inconsistent.pass.cpp b/libcxx/test/libcxx/algorithms/debug_three_way_comp.inconsistent.pass.cpp new file mode 100644 index 0000000..eb2a483 --- /dev/null +++ b/libcxx/test/libcxx/algorithms/debug_three_way_comp.inconsistent.pass.cpp @@ -0,0 +1,55 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// template struct __debug_three_way_comp + +// Make sure __debug_three_way_comp asserts when the comparator is not consistent. + +// UNSUPPORTED: !libcpp-has-debug-mode, c++03, c++11, c++14, c++17 + +#include +#include + +#include "check_assertion.h" + +struct AlwaysLess { + std::strong_ordering operator()(int, int) const { return std::strong_ordering::less; } +}; + +struct AlwaysGreater { + std::strong_ordering operator()(int, int) const { return std::strong_ordering::greater; } +}; + +struct InconsistentEquals { + std::strong_ordering operator()(int a, int) const { + if (a == 0) + return std::strong_ordering::equal; + return std::strong_ordering::greater; + } +}; + +int main(int, char**) { + int zero = 0; + int one = 1; + + AlwaysLess alwaysLess; + std::__debug_three_way_comp debugAlwaysLess(alwaysLess); + TEST_LIBCPP_ASSERT_FAILURE(debugAlwaysLess(zero, one), "Comparator does not induce a strict weak ordering"); + + AlwaysGreater alwaysGreater; + std::__debug_three_way_comp debugAlwaysGreater(alwaysGreater); + TEST_LIBCPP_ASSERT_FAILURE(debugAlwaysGreater(zero, one), "Comparator does not induce a strict weak ordering"); + + InconsistentEquals inconsistentEquals; + std::__debug_three_way_comp debugInconsistentEquals(inconsistentEquals); + TEST_LIBCPP_ASSERT_FAILURE(debugInconsistentEquals(zero, one), "Comparator does not induce a strict weak ordering"); + + return 0; +} diff --git a/libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/robust_against_copying_comparators.pass.cpp index 0f50d1c..307610d 100644 --- 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 @@ struct BinaryTransform { }; #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 @@ TEST_CONSTEXPR_CXX20 bool all_the_algorithms() 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 index a7ddf22..78a5863 100644 --- 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 test() { (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 index e816624..fe5fe24 100644 --- a/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_extensions.verify.cpp @@ -174,6 +174,14 @@ void test_algorithms() { 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 index f629ce0..d94bb18 100644 --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -81,6 +81,7 @@ END-SCRIPT #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 @@ END-SCRIPT #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 index 0000000..4c940eb --- /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 index 0000000..201ff9e --- /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 index 0000000..bac3ec5 --- /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 index d457baf..2d5ece6 100644 --- 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 @@ TEST_CONSTEXPR_CXX20 bool all_the_algorithms() // 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 index c060f46..8016cd7 100644 --- 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 @@ TEST_CONSTEXPR_CXX20 bool all_the_algorithms() (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 index 2a60c22..13f28c1 100644 --- a/libcxx/test/support/almost_satisfies_types.h +++ b/libcxx/test/support/almost_satisfies_types.h @@ -389,6 +389,39 @@ static_assert(!std::random_access_iterator); 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 index 8187a7c..c54e877 100644 --- 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 @@ struct LessAndEqComp { 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 -- 2.7.4