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","|Done|","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 @@ -282,6 +282,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/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,71 @@ +//===----------------------------------------------------------------------===// +// +// 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; +}; + +template +[[nodiscard]] constexpr bool testLexicographicalCompare(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 bool test() { + // Identical arrays + assert((testLexicographicalCompare(array{0, 1}, array{0, 1}, std::strong_ordering::equal))); + // "Greater" on 2nd element + assert((testLexicographicalCompare(array{0, 1}, array{0, 2}, std::strong_ordering::less))); + // "Less" on 2nd element + assert((testLexicographicalCompare(array{0, 2}, array{0, 1}, std::strong_ordering::greater))); + // "Greater" on 2nd element, but less on first entry + assert((testLexicographicalCompare(array{0, 2}, array{1, 1}, std::strong_ordering::less))); + // Identical elements, but shorter + assert((testLexicographicalCompare(array{0, 1}, array{0, 1, 2}, std::strong_ordering::less))); + // Identical elements, but longer + assert((testLexicographicalCompare(array{0, 1, 2}, array{0, 1}, std::strong_ordering::greater))); + + return true; +} + +int main(int, char**) { + // Check with various iterator types + test(); + static_assert(test()); + test>(); + test, random_access_iterator>(); + + // Check that the comparison category is correctly propagated + assert((testLexicographicalCompare( + array{{{0}, {1}}}, array{{{1}, {1}}}, std::weak_ordering::less))); + + 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,60 @@ +//===----------------------------------------------------------------------===// +// +// 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" + +using std::strong_ordering; + +constexpr strong_ordering compareLastDigit(int a, int b) { return (a % 10) <=> (b % 10); } + +[[nodiscard]] constexpr bool testLexicographicalCompare(const auto& a, const auto& b, auto expected) { + auto result = std::lexicographical_compare_three_way(a.begin(), a.end(), b.begin(), b.end(), compareLastDigit); + ASSERT_SAME_TYPE(decltype(result), decltype(expected)); + return expected == result; +} + +constexpr bool test() { + using std::array; + + // Identical arrays + assert(testLexicographicalCompare(array{90, 81}, array{10, 11}, std::strong_ordering::equal)); + // "Greater" on 2nd element + assert(testLexicographicalCompare(array{70, 81}, array{10, 12}, std::strong_ordering::less)); + // "Less" on 2nd element + assert(testLexicographicalCompare(array{10, 82}, array{20, 41}, std::strong_ordering::greater)); + // "Greater" on 2nd element, but less on first entry + assert(testLexicographicalCompare(array{20, 72}, array{11, 31}, std::strong_ordering::less)); + // Identical elements, but shorter + assert(testLexicographicalCompare(array{10, 11}, array{20, 21, 22}, std::strong_ordering::less)); + // Identical elements, but longer + assert(testLexicographicalCompare(array{10, 11, 12}, array{10, 11}, std::strong_ordering::greater)); + + 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 incorrectComparator(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(), incorrectComparator); + assert(result == std::strong_ordering::equal); + + return 0; +}