[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

5631

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

5631

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.

5631

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

645

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

662

Please unconditionally include headers.

5624

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

5624

I think I've done this one?

libcxx/include/compare

645

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/__config

 #if !defined(__cpp_coroutines) || __cpp_coroutines < 201703L
 #define _LIBCPP_HAS_NO_COROUTINES
 #endif
 
 #if !defined(__cpp_impl_three_way_comparison) || __cpp_impl_three_way_comparison < 201907L
 #define _LIBCPP_HAS_NO_SPACESHIP_OPERATOR
 #endif
 
+#if !defined(__cpp_concepts) || __cpp_concepts < 201811L
+#define _LIBCPP_HAS_NO_CONCEPTS
+#endif
+
 // Decide whether to use availability macros.
 #if !defined(_LIBCPP_BUILDING_LIBRARY) &&                                      \
     !defined(_LIBCXXABI_BUILDING_LIBRARY) &&                                   \
     !defined(_LIBCPP_DISABLE_AVAILABILITY) &&                                  \
     __has_feature(attribute_availability_with_strict) &&                       \
     __has_feature(attribute_availability_in_templates) &&                      \
     __has_extension(pragma_clang_attribute_external_declaration)
 #  ifdef __APPLE__

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);
 
 template <class BidirectionalIterator>
     bool
     prev_permutation(BidirectionalIterator first, BidirectionalIterator last);
 
 template <class BidirectionalIterator, class Compare>
     bool
     prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
 
 }  // std
 
 */
 
 #include <__config>
 #include <initializer_list>
 #include <type_traits>
+#include <compare>
 #include <cstring>
 #include <utility> // needed to provide swap_ranges.
 #include <memory>
 #include <functional>
 #include <iterator>
 #include <cstddef>
 #include <bit>
 #include <version>
 
 #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
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_SPACESHIP_OPERATOR)
+
+template <class _Compare, class _InputIterator1, class _InputIterator2>
+using __alg_three_way_result =
+    enable_if_t<!is_same_v<common_comparison_category_t<
+        invoke_result_t<_Compare&, typename iterator_traits<_InputIterator1>::reference, typename iterator_traits<_InputIterator2>::reference>>, void>,
+        invoke_result_t<_Compare&, typename iterator_traits<_InputIterator1>::reference, typename iterator_traits<_InputIterator2>::reference>>;
+
+template <class _InputIterator1, class _InputIterator2, class _Compare>
+constexpr auto lexicographical_compare_three_way(_InputIterator1 __first1, _InputIterator1 __last1,
+                                                 _InputIterator2 __first2, _InputIterator2 __last2,
+                                                 _Compare __comp)
+    -> __alg_three_way_result<_Compare, _InputIterator1, _InputIterator2>
+{
+    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 weak_ordering weak_order(const T& a, const T& b);
   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 <concepts>
 #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/include/concepts

 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-#if _LIBCPP_STD_VER > 17 && defined(__cpp_concepts) && __cpp_concepts >= 201811L
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
 
 // [concept.same]
 
 template<class _Tp, class _Up>
 concept __same_as_impl = _VSTD::_IsSame<_Tp, _Up>::value;
 
 template<class _Tp, class _Up>
 concept same_as = __same_as_impl<_Tp, _Up> && __same_as_impl<_Up, _Tp>;
 
-#endif //_LIBCPP_STD_VER > 17 && defined(__cpp_concepts) && __cpp_concepts >= 201811L
+#endif //_LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP_CONCEPTS

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"
+
+template <class Iter1, class Iter2>
+constexpr 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>
+constexpr 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>
+constexpr 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>
+constexpr 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);
+}
+
+constexpr bool test() {
+  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*>();
+
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(test());
+  test();
+
+  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 <array>
+#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);
+};
+
+template <class Iter1, class Iter2>
+constexpr void test_less() {
+  std::array<int, 4> a{1, 2, 3, 4};
+  std::array<int, 3> b{1, 2, 3};
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin()), Iter1(b.end() - 1), Iter2(a.begin()),
+             Iter2(a.end()), comp) == std::weak_ordering::less);
+
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin()), Iter1(b.end() - 1), Iter2(a.begin()),
+             Iter2(a.end()), comp) == std::weak_ordering::less);
+
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin()), Iter1(b.end()), Iter1(a.begin()), Iter1(a.end()),
+             comp) == std::weak_ordering::less);
+}
+
+template <class Iter1, class Iter2>
+constexpr void test_equal() {
+  std::array<int, 4> a{1, 2, 3, 4};
+  std::array<int, 4> b = a;
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin()), Iter1(b.end()), Iter2(a.begin()), Iter2(a.end()),
+             comp) == std::weak_ordering::equivalent);
+
+  std::array<int, 3> x{99, 64, 128};
+  std::array<int, 3> y = x;
+  assert(std::lexicographical_compare_three_way(
+             Iter1(x.begin()), Iter1(x.end()), Iter2(y.begin()), Iter2(y.end()),
+             comp) == std::weak_ordering::equivalent);
+}
+
+template <class Iter1, class Iter2>
+constexpr void test_greater() {
+  std::array<int, 4> a{1, 2, 3, 4};
+  std::array<int, 3> b{1, 2, 3};
+  assert(std::lexicographical_compare_three_way(
+             Iter1(a.begin()), Iter1(a.end()), Iter2(b.begin()),
+             Iter2(b.end() - 1), comp) == std::weak_ordering::greater);
+
+  assert(std::lexicographical_compare_three_way(
+             Iter1(a.begin()), Iter1(a.end()), Iter2(b.begin()), Iter2(b.end()),
+             comp) == std::weak_ordering::greater);
+
+  assert(std::lexicographical_compare_three_way(
+             Iter1(b.begin() + 1), Iter1(b.end()), Iter2(a.begin()),
+             Iter2(a.end()), comp) == std::weak_ordering::less);
+}
+
+template <class Iter1, class Iter2>
+constexpr void test() {
+  test_less<Iter1, Iter2>();
+  test_equal<Iter1, Iter2>();
+  test_equal<Iter1, Iter2>();
+  test_greater<Iter1, Iter2>();
+}
+
+constexpr bool test() {
+  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*>();
+
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(test());
+  test();
+
+  return 0;
+}