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,61 @@ +//===----------------------------------------------------------------------===// +// +// 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"); + + 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 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 @@ -285,6 +285,7 @@ module iter_swap { private header "__algorithm/iter_swap.h" } module iterator_operations { private header "__algorithm/iterator_operations.h" } 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,98 @@ +//===----------------------------------------------------------------------===// +// +// 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 "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 +[[nodiscard]] constexpr bool test_lexicographical_compare(const C1& a, const C2& b, Order expected) { + auto result = + std::lexicographical_compare_three_way(Iter1{a.begin()}, Iter1{a.end()}, Iter2{b.begin()}, Iter2{b.end()}); + ASSERT_SAME_TYPE(decltype(result), Order); + return expected == result; +} + +template +constexpr void test_iterator_types() { + // Both inputs empty + assert((test_lexicographical_compare(array{}, array{}, std::strong_ordering::equal))); + // Left input empty + assert((test_lexicographical_compare(array{}, array{0, 1}, std::strong_ordering::less))); + // Right input empty + assert((test_lexicographical_compare(array{0, 1}, array{}, std::strong_ordering::greater))); + + // Identical arrays + assert((test_lexicographical_compare(array{0, 1}, array{0, 1}, std::strong_ordering::equal))); + // "Less" on 2nd element + assert((test_lexicographical_compare(array{0, 1}, array{0, 2}, std::strong_ordering::less))); + // "Greater" on 2nd element + assert((test_lexicographical_compare(array{0, 2}, array{0, 1}, std::strong_ordering::greater))); + // "Greater" on 2nd element, but "less" on first entry + assert((test_lexicographical_compare(array{0, 2}, array{1, 1}, std::strong_ordering::less))); + // Identical elements, but longer + assert((test_lexicographical_compare(array{0, 1}, array{0, 1, 2}, std::strong_ordering::less))); + // Identical elements, but shorter + assert((test_lexicographical_compare(array{0, 1, 2}, array{0, 1}, std::strong_ordering::greater))); +} + +constexpr bool test() { + // Check with various iterator types + test_iterator_types(); + test_iterator_types>(); + test_iterator_types, three_way_contiguous_iterator>(); + test_iterator_types, random_access_iterator>(); + test_iterator_types, cpp20_random_access_iterator>(); + + // Check for other comparison categories + assert((test_lexicographical_compare( + array{{{0}, {1}}}, array{{{1}, {1}}}, std::weak_ordering::less))); + assert((test_lexicographical_compare( + array{{{0}, {1}}}, array{{{1}, {1}}}, std::partial_ordering::less))); + + // Check for other comparison categories with arrays of different sizes + assert((test_lexicographical_compare( + array{{{0}}}, array{{{0}, {1}}}, std::weak_ordering::less))); + assert((test_lexicographical_compare( + array{{{0}}}, array{{{0}, {1}}}, std::partial_ordering::less))); + + 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,123 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_iterators.h" + +using std::array; + +constexpr std::strong_ordering compare_last_digit(int a, int b) { return (a % 10) <=> (b % 10); } +constexpr std::weak_ordering compare_last_digit_weak(int a, int b) { return (a % 10) <=> (b % 10); } +constexpr std::partial_ordering compare_last_digit_partial(int a, int b) { return (a % 10) <=> (b % 10); } + +template +[[nodiscard]] constexpr bool test_lexicographical_compare(const C1& a, const C2& b, Order expected, Comparator comp) { + auto result = + std::lexicographical_compare_three_way(Iter1{a.begin()}, Iter1{a.end()}, Iter2{b.begin()}, Iter2{b.end()}, comp); + ASSERT_SAME_TYPE(decltype(result), Order); + return expected == result; +} + +[[nodiscard]] constexpr bool test_lexicographical_compare(const auto& a, const auto& b, auto expected) { + auto result = std::lexicographical_compare_three_way(a.begin(), a.end(), b.begin(), b.end(), compare_last_digit); + ASSERT_SAME_TYPE(decltype(result), decltype(expected)); + return expected == result; +} + +template +constexpr void test_iterator_types() { + // Both inputs empty + assert((test_lexicographical_compare( + array{}, array{}, std::strong_ordering::equal, compare_last_digit))); + // Left input empty + assert((test_lexicographical_compare( + array{}, array{0, 1}, std::strong_ordering::less, compare_last_digit))); + // Right input empty + assert((test_lexicographical_compare( + array{0, 1}, array{}, std::strong_ordering::greater, compare_last_digit))); + + // Identical arrays + assert((test_lexicographical_compare( + array{0, 1}, array{0, 1}, std::strong_ordering::equal, compare_last_digit))); + // "Less" on 2nd element + assert((test_lexicographical_compare( + array{0, 1}, array{0, 2}, std::strong_ordering::less, compare_last_digit))); + // "Greater" on 2nd element + assert((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 + assert((test_lexicographical_compare( + array{0, 2}, array{1, 1}, std::strong_ordering::less, compare_last_digit))); + // Identical elements, but longer + assert((test_lexicographical_compare( + array{0, 1}, array{0, 1, 2}, std::strong_ordering::less, compare_last_digit))); + // Identical elements, but shorter + assert((test_lexicographical_compare( + array{0, 1, 2}, array{0, 1}, std::strong_ordering::greater, compare_last_digit))); +} + +constexpr bool test() { + // Check with various iterator types + test_iterator_types(); + test_iterator_types>(); + test_iterator_types, three_way_contiguous_iterator>(); + test_iterator_types, random_access_iterator>(); + test_iterator_types, cpp20_random_access_iterator>(); + + // Check for other comparison categories + assert((test_lexicographical_compare( + array{0, 1}, array{10, 11}, std::weak_ordering::equivalent, compare_last_digit_weak))); + assert((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 + assert((test_lexicographical_compare( + array{0}, array{0, 1}, std::weak_ordering::less, compare_last_digit_weak))); + assert((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." + 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; + assert((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 + assert((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); + + 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,40 @@ +//===----------------------------------------------------------------------===// +// +// 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@*:* {{no viable conversion}} + // 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; +}