[libcxx] adds lexicographical_compare_three_way

[cjdb]

Summary

[libcxx] adds lexicographical_compare_three_way

• adds lexicographical_compare_three_way algorithms
• adds tests
• replaces std::array with raw array to eliminate circular dep :-(

[miscco]

libcxx/include/algorithm

5634

The identation here is off. Could you please add braces so that it is clear where the loop ends

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp

41

These are rather subtle tests. To make it imediately clear what you are actually testing I would appreciate if you could go the extra mile and add comments

// lexicographical_compare_three_way(a, b), range b shorter than range a

// lexicographical_compare_three_way(a, b), range a shorter than range b

[cjdb]

libcxx/include/algorithm

5634

clang-format doesn't seem to care about this file, so I've had to do it manually. Weird.

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp

41

Done, but you might ask for further improvements.

[curdeius]

libcxx/include/algorithm

619

Return type in synopsis doesn't match the one in implementation.

624

Same here.

5634

FYI. If you use git-clang-format, it filters modified files based on their extension, and by default extensionless files are skipped. But there is a parameter for that.

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp

25

Constexpr test is... minimal to say the least. I think it would be better to have a single constexpr function (for applicable cases) and call it once on runtime and once on compile time.

31

Format?

39

Can't you use std::array?

50

Personally, I find it very difficult to read and to verify that you covered all possible cases of less/greater, shorter/longer, equal, empty with this style. I'd rather split them.

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp

13

Bool?

[cjdb]

Applies some of @curdeius's suggestions.

[cjdb]

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp

25

I can do that. This test is (mostly) a carbon copy of the test for std::lexicographical_compare, so many of your comments are also applicable to that test as well. That doesn't excuse me from improving this test, so I've applied the changes here.

Does libc++ have a way to assert based on whether it's compile-time or run-time yet?

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp

13

Fixed. How many of your comments from the above are also applicable here?

[curdeius]

libcxx/include/compare

644

Nit: you could avoid passing the size explicitly if you passed the array by reference.

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp

25

I'm not sure if I understand your question correctly. There is (__libcpp_)is_constant_evaluated, but there is, to my knowledge, nothing that asserts that a path is taken on runtime/compile time.

83

That's already better, even if personally I would create a different array in each of the test_x functions.

90

You can move all those calls to test<Iterator, Iterator> to another function and just call it twice from main (once in static_assert).

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp

13

Probably all.

[EricWF]

How do we implement the "Mandates" requirement specified here?

libcxx/include/algorithm

661

Please unconditionally include headers.

5627

blank line after after the #ifdef.

We should also gate this on the standard dialect, because three way comparison can be enabled as an extension.

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp

26

You don't need to use TEST_CONSTEXPR because the test is unsupported in C++03 (where constexpr can't be spelled without Clang getting mad).

[cjdb]

libcxx/include/algorithm

5627

I think I've done this one?

libcxx/include/compare

644

I did that at first, but apparently sizeof...(_Ts) can be 0.

[curdeius]

As a general remark, it would be call if you added a link to standard draft or proposal (or both) in the summary of each revision. It would make reviewing a bit easier :).

Otherwise, it seems good to me. But you need to wait for libc++ reviewers.

[avogelsgesang]

a new attempt at this: https://reviews.llvm.org/D131395

libcxx/include/algorithm

template <class InputIterator1, class InputIterator2>
     constexpr bool     // constexpr in C++20
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);
 
 template <class InputIterator1, class InputIterator2, class Compare>
     constexpr bool     // constexpr in C++20
     lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2, Compare comp);
 
+template <class InputIterator1, class InputIterator2>
+    constexpr auto
+    lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1,
+                                      InputIterator2 first2, InputIterator2 last2);
+
+template <class InputIterator1, class InputIterator2, class Compare>
+    constexpr auto
+    lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1,
+                                      InputIterator2 first2, InputIterator2 last2, Compare comp)
+    -> decltype(comp(*first1, *first2));
+
 template <class BidirectionalIterator>
     bool
     next_permutation(BidirectionalIterator first, BidirectionalIterator last);
 
 template <class BidirectionalIterator, class Compare>
     bool
     next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
 

 #include <utility> // needed to provide swap_ranges.
 #include <memory>
 #include <functional>
 #include <iterator>
 #include <cstddef>
 #include <bit>
 #include <version>
 
+#ifndef _LIBCPP_HAS_NO_SPACESHIP_OPERATOR
+#include <compare>
+#endif // _LIBCPP_HAS_NO_SPACESHIP_OPERATOR
+
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
                         _InputIterator2 __first2, _InputIterator2 __last2)
 {
     return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
                                          __less<typename iterator_traits<_InputIterator1>::value_type,
                                                 typename iterator_traits<_InputIterator2>::value_type>());
 }
 
+// lexicographical_compare_three_way
+#ifndef _LIBCPP_HAS_NO_SPACESHIP_OPERATOR
+template <class _InputIterator1, class _InputIterator2, class _Compare>
+constexpr auto lexicographical_compare_three_way(_InputIterator1 __first1, _InputIterator1 __last1,
+                                                 _InputIterator2 __first2, _InputIterator2 __last2,
+                                                 _Compare __comp) -> decltype(__comp(*__first1, *__first2))
+{
+    for (; __first1 != __last1 && __first2 != __last2; void(++__first1), void(++__first2))
+        if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
+            return __cmp;
+    return __first1 != __last1 ? strong_ordering::greater :
+           __first2 != __last2 ? strong_ordering::less :
+                                 strong_ordering::equal;
+}
+
+template <class _InputIterator1, class _InputIterator2>
+constexpr auto lexicographical_compare_three_way(_InputIterator1 __first1, _InputIterator1 __last1,
+                                                 _InputIterator2 __first2, _InputIterator2 __last2)
+{
+    return _VSTD::lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
+                                                    compare_three_way());
+}
+#endif // _LIBCPP_HAS_NO_SPACESHIP_OPERATOR
+
 // next_permutation
 
 template <class _Compare, class _BidirectionalIterator>
 bool
 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     _BidirectionalIterator __i = __last;
     if (__first == __last || __first == --__i)

libcxx/include/compare

namespace std {
   template<class T> constexpr partial_ordering partial_order(const T& a, const T& b);
   template<class T> constexpr strong_equality strong_equal(const T& a, const T& b);
   template<class T> constexpr weak_equality weak_equal(const T& a, const T& b);
 }
 */
 
 #include <__config>
 #include <type_traits>
-#include <array>
 
 #ifndef _LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 17
if (is_same_v<_Tp, weak_ordering>)
     return _WeakOrd;
   if (is_same_v<_Tp, strong_ordering>)
     return _StrongOrd;
   return _None;
 }
 
 template <size_t _Size>
 constexpr _ClassifyCompCategory
-__compute_comp_type(std::array<_ClassifyCompCategory, _Size> __types) {
-  std::array<int, _CCC_Size> __seen = {};
-  for (auto __type : __types)
-    ++__seen[__type];
+__compute_comp_type(const _ClassifyCompCategory* __types) {
+  int __seen[_CCC_Size] = {};
+  for (size_t __i = 0; __i < _Size; ++__i)
+    ++__seen[__types[__i]];
   if (__seen[_None])
     return _None;
   if (__seen[_WeakEq])
     return _WeakEq;
   if (__seen[_StrongEq] && (__seen[_PartialOrd] || __seen[_WeakOrd]))
     return _WeakEq;
   if (__seen[_StrongEq])
     return _StrongEq;
   if (__seen[_PartialOrd])
     return _PartialOrd;
   if (__seen[_WeakOrd])
     return _WeakOrd;
   return _StrongOrd;
 }
 
 template <class ..._Ts>
 constexpr auto __get_comp_type() {
   using _CCC = _ClassifyCompCategory;
-  constexpr array<_CCC, sizeof...(_Ts)> __type_kinds{{__comp_detail::__type_to_enum<_Ts>()...}};
+  constexpr _CCC __type_kinds[sizeof...(_Ts)] = {__comp_detail::__type_to_enum<_Ts>()...};
   constexpr _CCC _Cat = sizeof...(_Ts) == 0 ? _StrongOrd
-      : __compute_comp_type(__type_kinds);
+      : __compute_comp_type<sizeof...(_Ts)>(__type_kinds);
   if constexpr (_Cat == _None)
     return void();
   else if constexpr (_Cat == _WeakEq)
     return weak_equality::equivalent;
   else if constexpr (_Cat == _StrongEq)
     return strong_equality::equivalent;
   else if constexpr (_Cat == _PartialOrd)
     return partial_ordering::equivalent;

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<InputIterator Iter1, InputIterator Iter2>
+//   constexpr auto
+//   lexicographical_compare(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2);
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+
+#include <algorithm>
+#include <array>
+#include <compare>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+TEST_CONSTEXPR bool test_constexpr() {
+  std::array ia{1, 2, 3};
+  std::array ib{1, 3, 5, 2, 4, 6};
+
+  const auto ia_less_ib = std::lexicographical_compare_three_way(
+      std::begin(ia), std::end(ia), std::begin(ib), std::end(ib));
+  const auto ib_equal_ib = std::lexicographical_compare_three_way(
+      std::begin(ib), std::end(ib), std::begin(ib), std::end(ib));
+  const auto ib_greater_ia = std::lexicographical_compare_three_way(
+      std::begin(ib), std::end(ib), std::begin(ia), std::end(ia));
+  return ia_less_ib == std::strong_ordering::less &&
+         ib_greater_ia == std::strong_ordering::greater &&
+         ib_equal_ib == std::strong_ordering::equal;
+}
+
+template <class Iter1, class Iter2>
+void test_less(std::array<int, 4>& a, std::array<int, 3>& b) {
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin()), Iter1(b.end() - 1), Iter2(a.begin()),
+             Iter2(a.end())) == std::strong_ordering::less);
+
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin()), Iter1(b.end()), Iter2(a.begin()),
+             Iter2(a.end())) == std::strong_ordering::less);
+
+  assert(std::lexicographical_compare_three_way(
+             Iter1(a.begin()), Iter1(a.end()), Iter2(b.begin() + 1),
+             Iter2(b.end())) == std::strong_ordering::less);
+}
+
+template <class Iter1, class Iter2, class R>
+void test_equal(R& a, R& b) {
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin()), Iter1(b.end()), Iter2(a.begin()),
+             Iter2(a.end())) == std::strong_ordering::equal);
+}
+
+template <class Iter1, class Iter2>
+void test_greater(std::array<int, 4>& a, std::array<int, 3>& b) {
+  assert(std::lexicographical_compare_three_way(
+             Iter1(a.begin()), Iter1(a.end()), Iter2(b.begin()),
+             Iter2(b.end() - 1)) == std::strong_ordering::greater);
+
+  assert(std::lexicographical_compare_three_way(
+             Iter1(a.begin()), Iter1(a.end()), Iter2(b.begin()),
+             Iter2(b.end())) == std::strong_ordering::greater);
+
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin() + 1), Iter1(b.end()), Iter2(a.begin()),
+             Iter2(a.end())) == std::strong_ordering::greater);
+}
+
+template <class Iter1, class Iter2>
+void test() {
+  std::array a{1, 2, 3, 4};
+  std::array b{1, 2, 3};
+
+  test_less<Iter1, Iter2>(a, b);
+  test_equal<Iter1, Iter2>(a, a);
+  test_equal<Iter1, Iter2>(b, b);
+  test_greater<Iter1, Iter2>(a, b);
+}
+
+int main(int, char**) {
+  test<input_iterator<const int*>, input_iterator<const int*> >();
+  test<input_iterator<const int*>, forward_iterator<const int*> >();
+  test<input_iterator<const int*>, bidirectional_iterator<const int*> >();
+  test<input_iterator<const int*>, random_access_iterator<const int*> >();
+  test<input_iterator<const int*>, const int*>();
+
+  test<forward_iterator<const int*>, input_iterator<const int*> >();
+  test<forward_iterator<const int*>, forward_iterator<const int*> >();
+  test<forward_iterator<const int*>, bidirectional_iterator<const int*> >();
+  test<forward_iterator<const int*>, random_access_iterator<const int*> >();
+  test<forward_iterator<const int*>, const int*>();
+
+  test<bidirectional_iterator<const int*>, input_iterator<const int*> >();
+  test<bidirectional_iterator<const int*>, forward_iterator<const int*> >();
+  test<bidirectional_iterator<const int*>,
+       bidirectional_iterator<const int*> >();
+  test<bidirectional_iterator<const int*>,
+       random_access_iterator<const int*> >();
+  test<bidirectional_iterator<const int*>, const int*>();
+
+  test<random_access_iterator<const int*>, input_iterator<const int*> >();
+  test<random_access_iterator<const int*>, forward_iterator<const int*> >();
+  test<random_access_iterator<const int*>,
+       bidirectional_iterator<const int*> >();
+  test<random_access_iterator<const int*>,
+       random_access_iterator<const int*> >();
+  test<random_access_iterator<const int*>, const int*>();
+
+  test<const int*, input_iterator<const int*> >();
+  test<const int*, forward_iterator<const int*> >();
+  test<const int*, bidirectional_iterator<const int*> >();
+  test<const int*, random_access_iterator<const int*> >();
+  test<const int*, const int*>();
+
+  static_assert(test_constexpr());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.three.way/lexicographical_compare_three_way_comp.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<InputIterator Iter1, InputIterator Iter2, CopyConstructible Compare>
+//   constexpr auto
+//   lexicographical_compare_three_way(Iter1 first1, Iter1 last1,
+//                                     Iter2 first2, Iter2 last2, Compare comp)
+//       -> decltype(comp(*first1, *first2));
+
+#include <algorithm>
+#include <functional>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+// "simulates" use of std::greater in lex.comparison comp test
+auto comp = [](int x, int y) {
+  return static_cast<std::weak_ordering>(y <=> x);
+};
+
+TEST_CONSTEXPR bool test_constexpr() {
+  int ia[] = {1, 2, 3};
+  int ib[] = {1, 3, 5, 2, 4, 6};
+
+  return std::lexicographical_compare_three_way(
+             std::begin(ia), std::end(ia), std::begin(ib), std::end(ib),
+             comp) == std::weak_ordering::greater &&
+         std::lexicographical_compare_three_way(
+             std::begin(ib), std::end(ib), std::begin(ia), std::end(ia),
+             comp) == std::weak_ordering::less;
+}
+
+template <class Iter1, class Iter2>
+void test() {
+  int ia[] = {1, 2, 3, 4};
+  const unsigned sa = sizeof(ia) / sizeof(ia[0]);
+  int ib[] = {1, 2, 3};
+
+  // range ib is shorter than ia; all values are the same.
+  assert(std::lexicographical_compare_three_way(
+             Iter1(ia), Iter1(ia + sa), Iter2(ib), Iter2(ib + 2), comp) ==
+         std::weak_ordering::greater);
+  assert(std::lexicographical_compare_three_way(
+             Iter1(ib), Iter1(ib + 2), Iter2(ia), Iter2(ia + sa), comp) ==
+         std::weak_ordering::less);
+  assert(std::lexicographical_compare_three_way(
+             Iter1(ia), Iter1(ia + sa), Iter2(ib), Iter2(ib + 3), comp) ==
+         std::weak_ordering::greater);
+  assert(std::lexicographical_compare_three_way(
+             Iter1(ib), Iter1(ib + 3), Iter2(ia), Iter2(ia + sa), comp) ==
+         std::weak_ordering::less);
+
+  // range ib starts with a greater value than ia.
+  assert(std::lexicographical_compare_three_way(
+             Iter1(ia), Iter1(ia + sa), Iter2(ib + 1), Iter2(ib + 3), comp) ==
+         std::weak_ordering::greater);
+  assert(std::lexicographical_compare_three_way(
+             Iter1(ib + 1), Iter1(ib + 3), Iter2(ia), Iter2(ia + sa), comp) ==
+         std::weak_ordering::less);
+}
+
+int main(int, char**) {
+  test<input_iterator<const int*>, input_iterator<const int*> >();
+  test<input_iterator<const int*>, forward_iterator<const int*> >();
+  test<input_iterator<const int*>, bidirectional_iterator<const int*> >();
+  test<input_iterator<const int*>, random_access_iterator<const int*> >();
+  test<input_iterator<const int*>, const int*>();
+
+  test<forward_iterator<const int*>, input_iterator<const int*> >();
+  test<forward_iterator<const int*>, forward_iterator<const int*> >();
+  test<forward_iterator<const int*>, bidirectional_iterator<const int*> >();
+  test<forward_iterator<const int*>, random_access_iterator<const int*> >();
+  test<forward_iterator<const int*>, const int*>();
+
+  test<bidirectional_iterator<const int*>, input_iterator<const int*> >();
+  test<bidirectional_iterator<const int*>, forward_iterator<const int*> >();
+  test<bidirectional_iterator<const int*>,
+       bidirectional_iterator<const int*> >();
+  test<bidirectional_iterator<const int*>,
+       random_access_iterator<const int*> >();
+  test<bidirectional_iterator<const int*>, const int*>();
+
+  test<random_access_iterator<const int*>, input_iterator<const int*> >();
+  test<random_access_iterator<const int*>, forward_iterator<const int*> >();
+  test<random_access_iterator<const int*>,
+       bidirectional_iterator<const int*> >();
+  test<random_access_iterator<const int*>,
+       random_access_iterator<const int*> >();
+  test<random_access_iterator<const int*>, const int*>();
+
+  test<const int*, input_iterator<const int*> >();
+  test<const int*, forward_iterator<const int*> >();
+  test<const int*, bidirectional_iterator<const int*> >();
+  test<const int*, random_access_iterator<const int*> >();
+  test<const int*, const int*>();
+
+  static_assert(test_constexpr());
+
+  return 0;
+}