[libc++] Refactor __debug_three_way_comp

[ldionne]

Summary

This makes debug_three_way_comp consistent with debug_less and
in particular gets rid of a potential use-after-move caused by the
use of std::forward. In the previous version of the code, we would
call __do_compare_assert after forwarding the arguments into the
comparator, which could end up using the arguments after they've been
moved from.

This also simplifies how we call __do_compare_assert by using
if constexpr and adds a missing test for proxy iterators in
lexicographical_compare_three_way, which could have found this
issue.

[philnik]

libcxx/include/__algorithm/three_way_comp_ref_type.h

38–45

I might have missed it, but I can't find any reason why we need this overload in the old threads. Do you have any reasoning for having this overload?

[H-G-Hristov]

@ldionne Thank. you! LGTM

[ldionne]

libcxx/include/__algorithm/three_way_comp_ref_type.h

38–45

I'm not sure TBH. The tests seem to pass, and I do think it should be sufficient to use const&. I'll do it in a follow-up.

[ldionne]

libcxx/include/__algorithm/three_way_comp_ref_type.h

38–45

Actually some of our tests fail when I remove it.

[ldionne]

Update formatting.

[philnik]

LGTM with comment.

libcxx/include/__algorithm/three_way_comp_ref_type.h

38–45

Weird. I think this should be investigated and a comment added here, since it's not obvious.

[ldionne]

libcxx/include/__algorithm/three_way_comp_ref_type.h

38–45

I looked it up and it is https://github.com/llvm/llvm-project/issues/40362.

libcxx/include/__algorithm/three_way_comp_ref_type.h

 #if _LIBCPP_STD_VER >= 20
 
 template <class _Comp>
 struct __debug_three_way_comp {
   _Comp& __comp_;
   _LIBCPP_HIDE_FROM_ABI constexpr __debug_three_way_comp(_Comp& __c) : __comp_(__c) {}
 
   template <class _Tp, class _Up>
-  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp&& __x, _Up&& __y) {
-    auto __r = __comp_(std::forward<_Tp>(__x), std::forward<_Up>(__y));
-    __do_compare_assert(0, __y, __x, __r);
+  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(const _Tp& __x, const _Up& __y) {
+    auto __r = __comp_(__x, __y);
+    if constexpr (__comparison_category<decltype(__comp_(__x, __y))>)
+      __do_compare_assert(__y, __x, __r);
+    return __r;
+  }
+
+  template <class _Tp, class _Up>
+  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y) {
+    auto __r = __comp_(__x, __y);
+    if constexpr (__comparison_category<decltype(__comp_(__x, __y))>)
+      __do_compare_assert(__y, __x, __r);
     return __r;
   }
 
   template <class _LHS, class _RHS, class _Order>
-  _LIBCPP_HIDE_FROM_ABI constexpr inline void __do_compare_assert(int, _LHS& __l, _RHS& __r, _Order __o)
-    requires __comparison_category<decltype(std::declval<_Comp&>()(std::declval<_LHS&>(), std::declval<_RHS&>()))>
-  {
+  _LIBCPP_HIDE_FROM_ABI constexpr void __do_compare_assert(_LHS& __l, _RHS& __r, _Order __o) {
     _Order __expected = __o;
     if (__o == _Order::less)
       __expected = _Order::greater;
     if (__o == _Order::greater)
       __expected = _Order::less;
     _LIBCPP_DEBUG_ASSERT(__comp_(__l, __r) == __expected, "Comparator does not induce a strict weak ordering");
     (void)__l;
     (void)__r;
-    (void)__expected;
   }
-
-  template <class _LHS, class _RHS, class _Order>
-  _LIBCPP_HIDE_FROM_ABI constexpr inline void __do_compare_assert(long, _LHS&, _RHS&, _Order) {}
 };
 
 // Pass the comparator by lvalue reference. Or in debug mode, using a
 // debugging wrapper that stores a reference.
 #  ifdef _LIBCPP_ENABLE_DEBUG_MODE
 template <class _Comp>
 using __three_way_comp_ref_type = __debug_three_way_comp<_Comp>;
 #  else

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

 //     lexicographical_compare_three_way(InputIterator1 first1, InputIterator1 last1,
 //                                       InputIterator2 first2, InputIterator2 last2)
 
 #include <array>
 #include <algorithm>
 #include <cassert>
 #include <compare>
 #include <concepts>
+#include <vector>
 
 #include "test_macros.h"
 #include "test_comparisons.h"
 #include "test_iterators.h"
 
 template <typename Iter1, typename Iter2, typename C1, typename C2, typename Order>
 constexpr void test_lexicographical_compare(C1 a, C2 b, Order expected) {
   std::same_as<Order> decltype(auto) result =
constexpr void test_comparison_categories() {
 
   // Check for a `partial_ordering::unordered` result
   test_lexicographical_compare<const PartialOrder*, const PartialOrder*>(
       std::array<PartialOrder, 2>{std::numeric_limits<int>::min(), 1},
       std::array<PartialOrder, 3>{0, 1, 2},
       std::partial_ordering::unordered);
 }
 
+// Check that it works with proxy iterators
+constexpr void test_proxy_iterators() {
+    std::vector<bool> vec(10, true);
+    auto result = std::lexicographical_compare_three_way(vec.begin(), vec.end(), vec.begin(), vec.end());
+    assert(result == std::strong_ordering::equal);
+}
+
 constexpr bool test() {
   test_iterator_types();
   test_comparison_categories();
+  test_proxy_iterators();
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

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

 //       -> decltype(comp(*b1, *b2));
 
 #include <algorithm>
 #include <array>
 #include <cassert>
 #include <compare>
 #include <concepts>
 #include <limits>
+#include <vector>
 
 #include "test_iterators.h"
 #include "test_macros.h"
 
 using std::array;
 
 constexpr auto compare_last_digit_strong  = [](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); };
test_lexicographical_compare<const int*, const int*>(
       std::array{0, 1, 2}, std::array{0, 1, 2, 3}, compare_last_digit_counting, std::strong_ordering::less);
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
   assert(compare_invocation_count <= 6);
 #else
   assert(compare_invocation_count <= 3);
 #endif
 }
 
+// Check that it works with proxy iterators
+constexpr void test_proxy_iterators() {
+    std::vector<bool> vec(10, true);
+    auto result = std::lexicographical_compare_three_way(vec.begin(), vec.end(), vec.begin(), vec.end(), compare_last_digit_strong);
+    assert(result == std::strong_ordering::equal);
+}
+
 constexpr bool test() {
   test_iterator_types();
   test_comparison_categories();
   test_comparator_invocation_count();
+  test_proxy_iterators();
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }