diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -184,6 +184,7 @@ formatter_float.bench.cpp formatter_int.bench.cpp function.bench.cpp + lexicographical_compare_three_way.bench.cpp map.bench.cpp ordered_set.bench.cpp std_format_spec_string_unicode.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; + + for (auto _ : state) { + int* b1 = v1.data(); + int* e1 = b1 + v1.size(); + int* b2 = v2.data(); + int* e2 = b2 + v2.size(); + benchmark::DoNotOptimize( + std::__lexicographical_compare_three_way_slow_path(b1, e1, b2, e2, std::compare_three_way())); + } +} + +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; + + for (auto _ : state) { + int* b1 = v1.data(); + int* e1 = b1 + v1.size(); + int* b2 = v2.data(); + int* e2 = b2 + v2.size(); + benchmark::DoNotOptimize( + std::__lexicographical_compare_three_way_fast_path(b1, e1, b2, e2, std::compare_three_way())); + } +} + +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; + + for (auto _ : state) { + auto b1 = IteratorT{v1.data()}; + auto e1 = IteratorT{v1.data() + v1.size()}; + auto b2 = IteratorT{v2.data()}; + auto e2 = IteratorT{v2.data() + v2.size()}; + benchmark::DoNotOptimize(std::lexicographical_compare_three_way(b1, e1, b2, e2, std::compare_three_way())); + } +} + +// 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,7 @@ "`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","","" -"`3350 `__","Simplify return type of ``lexicographical_compare_three_way``\ ","Prague","","","|spaceship|" +"`3350 `__","Simplify return type of ``lexicographical_compare_three_way``\ ","Prague","|Complete|","16.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|","16.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 @@ -43,6 +43,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 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,109 @@ +//===----------------------------------------------------------------------===// +// +// 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 <__compare/compare_three_way.h> +#include <__compare/ordering.h> +#include <__config> +#include <__iterator/iterator_traits.h> +#include <__type_traits/is_integral.h> +#include <__utility/forward.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_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(is_integral_v::difference_type>, + "Using a non-integral difference_type is undefined behavior"); + static_assert(is_integral_v::difference_type>, + "Using a non-integral difference_type is undefined behavior"); + + auto __len1 = __last1 - __first1; + auto __len2 = __last2 - __first2; + auto __min_len = __len1 < __len2 ? __len1 : __len2; + + for (decltype(__min_len) __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_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"); + + if constexpr (__is_cpp17_random_access_iterator<_InputIterator1>::value && + __is_cpp17_random_access_iterator<_InputIterator2>::value) { + return __lexicographical_compare_three_way_fast_path( + __first1, __last1, __first2, __last2, std::forward<_Cmp>(__comp)); + } else { + // Unoptimized implementation which compares the iterators against the end in every loop iteration + return __lexicographical_compare_three_way_slow_path( + __first1, __last1, __first2, __last2, std::forward<_Cmp>(__comp)); + } +} + +template +_LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way( + _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { + return std::lexicographical_compare_three_way(__first1, __last1, __first2, __last2, compare_three_way()); +} + +#endif // _LIBCPP_STD_VER > 17 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_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); @@ -1755,6 +1767,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 @@ -288,6 +288,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" } 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 @@ -80,6 +80,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'}} 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 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,177 @@ +//===----------------------------------------------------------------------===// +// +// 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, Order expected, Comparator comp) { + std::same_as 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() { + // Both inputs empty + test_lexicographical_compare( + std::array{}, std::array{}, std::strong_ordering::equal, compare_last_digit_strong); + // Left input empty + test_lexicographical_compare( + std::array{}, std::array{0, 1}, std::strong_ordering::less, compare_last_digit_strong); + // Right input empty + test_lexicographical_compare( + std::array{0, 1}, std::array{}, std::strong_ordering::greater, compare_last_digit_strong); + + // Identical arrays + test_lexicographical_compare( + std::array{0, 1}, std::array{0, 1}, std::strong_ordering::equal, compare_last_digit_strong); + // "Less" on 2nd element + test_lexicographical_compare( + std::array{0, 1}, std::array{0, 2}, std::strong_ordering::less, compare_last_digit_strong); + // "Greater" on 2nd element + test_lexicographical_compare( + std::array{0, 2}, std::array{0, 1}, std::strong_ordering::greater, compare_last_digit_strong); + // "Greater" on 2nd element, but "less" on first entry + test_lexicographical_compare( + std::array{0, 2}, std::array{1, 1}, std::strong_ordering::less, compare_last_digit_strong); + // Identical elements, but longer + test_lexicographical_compare( + std::array{0, 1}, std::array{0, 1, 2}, std::strong_ordering::less, compare_last_digit_strong); + // Identical elements, but shorter + test_lexicographical_compare( + std::array{0, 1, 2}, std::array{0, 1}, std::strong_ordering::greater, compare_last_digit_strong); +} + +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}, std::weak_ordering::equivalent, compare_last_digit_weak); + test_lexicographical_compare( + std::array{0, 1}, std::array{20, 11}, std::partial_ordering::equivalent, compare_last_digit_partial); + + // Check for all comparison categories with arrays of different sizes + test_lexicographical_compare( + std::array{0}, std::array{0, 1}, std::strong_ordering::less, compare_last_digit_strong); + test_lexicographical_compare( + std::array{0}, std::array{0, 1}, std::weak_ordering::less, compare_last_digit_weak); + test_lexicographical_compare( + std::array{0}, std::array{0, 1}, std::partial_ordering::less, compare_last_digit_partial); + + // 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, + compare_last_digit_partial); +} + +// 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 both 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{}, std::strong_ordering::greater, compare_last_digit_counting); + 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}, std::strong_ordering::less, compare_last_digit_counting); + 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,41 @@ +//===----------------------------------------------------------------------===// +// +// 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( + 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()); +} 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,40 @@ 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,34 @@ 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