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],Christopher Di Bella,|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,83 @@ +//===----------------------------------------------------------------------===// +// +// 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> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 + +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_base_of_v::iterator_category> && + is_base_of_v::iterator_category>) { + // Fast path for random access iterators which computes the number of loop iterations up-front and + // then skips the iterator comparisons inside the loop. + size_t __len1 = __last1 - __first1; + size_t __len2 = __last2 - __first2; + size_t __min_len = std::min(__len1, __len2); + for (size_t __i = 0; __i < __min_len;) { + auto __c = __comp(*__first1, *__first2); + if (__c != 0) { + return __c; + } + ++__i; + ++__first1; + ++__first2; + } + return __len1 <=> __len2; + } else { + // Unoptimized implementation which compares the iterators against the end in every loop iteration + 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) { + 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); @@ -1756,6 +1768,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,7 @@ 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,147 @@ +//===----------------------------------------------------------------------===// +// +// 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_iterators.h" + +using std::array; + +// A struct for which only weak comparisons are defined +struct WeakInt { + int value; + friend std::weak_ordering operator<=>(WeakInt, WeakInt) = default; +}; + +// A struct for which only partial comparisons are defined +struct PartialInt { + int value; + friend std::partial_ordering operator<=>(PartialInt, PartialInt) = default; +}; + +template +constexpr void test_lexicographical_compare(const C1& a, const 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(array{}, array{}, std::strong_ordering::equal); + // Left input empty + test_lexicographical_compare(array{}, array{0, 1}, std::strong_ordering::less); + // Right input empty + test_lexicographical_compare(array{0, 1}, array{}, std::strong_ordering::greater); + + // Identical arrays + test_lexicographical_compare(array{0, 1}, array{0, 1}, std::strong_ordering::equal); + // "Less" on 2nd element + test_lexicographical_compare(array{0, 1}, array{0, 2}, std::strong_ordering::less); + // "Greater" on 2nd element + test_lexicographical_compare(array{0, 2}, array{0, 1}, std::strong_ordering::greater); + // "Greater" on 2nd element, but "less" on first entry + test_lexicographical_compare(array{0, 2}, array{1, 1}, std::strong_ordering::less); + // Identical elements, but longer + test_lexicographical_compare(array{0, 1}, array{0, 1, 2}, std::strong_ordering::less); + // Identical elements, but shorter + test_lexicographical_compare(array{0, 1, 2}, array{0, 1}, std::strong_ordering::greater); +} + +constexpr void test_iterator_types() { + // Exhaustively test all combinations of `const int*`, `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_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, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); + + test_given_iterator_types, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); + + test_given_iterator_types, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); + + test_given_iterator_types, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); + + test_given_iterator_types, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); +} + +// Check for other comparison categories +constexpr void test_comparison_categories() { + test_lexicographical_compare( + array{{{0}, {1}}}, array{{{1}, {1}}}, std::weak_ordering::less); + test_lexicographical_compare( + array{{{0}, {1}}}, array{{{1}, {1}}}, std::partial_ordering::less); + + // Check for other comparison categories with arrays of different sizes + test_lexicographical_compare( + array{{{0}}}, array{{{0}, {1}}}, std::weak_ordering::less); + test_lexicographical_compare( + array{{{0}}}, array{{{0}, {1}}}, std::partial_ordering::less); +} + +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,183 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_macros.h" +#include "test_iterators.h" + +using std::array; + +constexpr auto compare_last_digit = [](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 { 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(const C1& a, const 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( + array{}, array{}, std::strong_ordering::equal, compare_last_digit); + // Left input empty + test_lexicographical_compare( + array{}, array{0, 1}, std::strong_ordering::less, compare_last_digit); + // Right input empty + test_lexicographical_compare( + array{0, 1}, array{}, std::strong_ordering::greater, compare_last_digit); + + // Identical arrays + test_lexicographical_compare(array{0, 1}, array{0, 1}, std::strong_ordering::equal, compare_last_digit); + // "Less" on 2nd element + test_lexicographical_compare(array{0, 1}, array{0, 2}, std::strong_ordering::less, compare_last_digit); + // "Greater" on 2nd element + test_lexicographical_compare( + array{0, 2}, array{0, 1}, std::strong_ordering::greater, compare_last_digit); + // "Greater" on 2nd element, but "less" on first entry + test_lexicographical_compare(array{0, 2}, array{1, 1}, std::strong_ordering::less, compare_last_digit); + // Identical elements, but longer + test_lexicographical_compare( + array{0, 1}, array{0, 1, 2}, std::strong_ordering::less, compare_last_digit); + // Identical elements, but shorter + test_lexicographical_compare( + array{0, 1, 2}, array{0, 1}, std::strong_ordering::greater, compare_last_digit); +} + +constexpr void test_iterator_types() { + // Exhaustively test all combinations of `const int*`, `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_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, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); + + test_given_iterator_types, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); + + test_given_iterator_types, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); + + test_given_iterator_types, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); + + test_given_iterator_types, const int*>(); + test_given_iterator_types, cpp17_input_iterator>(); + test_given_iterator_types, forward_iterator>(); + test_given_iterator_types, bidirectional_iterator>(); + test_given_iterator_types, random_access_iterator>(); + test_given_iterator_types, contiguous_iterator>(); +} + +// Check for other comparison categories +constexpr void test_comparison_categories() { + test_lexicographical_compare( + array{0, 1}, array{10, 11}, std::weak_ordering::equivalent, compare_last_digit_weak); + test_lexicographical_compare( + array{0, 1}, array{20, 11}, std::partial_ordering::equivalent, compare_last_digit_partial); + + // Check for other comparison categories with arrays of different sizes + test_lexicographical_compare( + array{0}, array{0, 1}, std::weak_ordering::less, compare_last_digit_weak); + test_lexicographical_compare( + array{0}, array{0, 1}, std::partial_ordering::less, 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( + array{0, 1, 2, 3}, 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( + array{0, 1, 2}, 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,38 @@ +//===----------------------------------------------------------------------===// +// +// 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" + +constexpr bool incorrect_comparator(int a, int b) { return a < b; } + +int main(int, char**) { + 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}} + // expected-error-re@*:* {{conversion function{{.*}}invokes a deleted function}} + auto result = std::lexicographical_compare_three_way(a.begin(), a.end(), b.begin(), b.end(), incorrect_comparator); + assert(result == std::strong_ordering::equal); + + return 0; +}