[libcxx] Fix std::equal not accepting volatile types by refactoring __equal_to

[alvinhochun]

Summary

Fixes https://github.com/llvm/llvm-project/issues/59021

[alvinhochun]

update test

[alvinhochun]

add the actual fix

[alvinhochun]

update test

[alvinhochun]

fix test

[philnik]

libcxx/include/__algorithm/equal.h

36

I think it would make more sense to refactor __equal_to to something like

struct __equal_to {
  template <class _Tp, class _Up>
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool operator()(_Tp&& __lhs, _Up&& __rhs) const {
    return __lhs == __rhs;
  }
};

This would allow us to just remove the typedefs and instead just have

return std::equal(__first1, __last1, __first2, __equal_to());

libcxx/test/libcxx/algorithms/equal.pass.cpp

1

Instead, you should update libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp.

17–20

Could you file a bug against GCC and link to it?

[ldionne]

libcxx/test/libcxx/algorithms/equal.pass.cpp

1

And add a comment linking to the bug report from the test.

[alvinhochun]

Updated test, refactored __equal_to according to comment

[alvinhochun]

Reformat

[philnik]

The implementation changes look pretty much good to me, but the test needs some more work.

libcxx/include/__algorithm/comp.h

20–22 ↗

(On Diff #476464)

I don't think this comment makes sense anymore. Let's remove it.

libcxx/include/__algorithm/equal.h

38

While we're refactoring the code we might as well replace the _VSTDs with std.

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp

29–32 ↗

(On Diff #476464)

47–49 ↗

(On Diff #476464)

70 ↗

(On Diff #476464)

I think it would make more sense factor out a function like this

template <class Iter1, class Iter2 = Iter1>
TEST_CONSTEXPR_CXX20 test_iterator() {
  int range1[] = {0, 1, 2, 3, 4, 5};
  int range2[] = {0, 1, 2, 5, 4, 5};

  assert(std::equal(Iter1(range1), Iter1(range1 + 6), Iter2(range1)));
  assert(!std::equal(Iter1(range1), Iter1(range1 + 6), Iter2(range2)));

#if TEST_STD_VER >= 14
  assert(std::equal(Iter1(range1), Iter1(range1 + 6), Iter2(range1), Iter2(range1 + 6)));
  assert(!std::equal(Iter1(range1), Iter1(range1 + 6), Iter2(range1), Iter2(range1 + 5)));
  assert(!std::equal(Iter1(range1), Iter1(range1 + 6), Iter2(range2), Iter2(range2 + 6)));
#endif
}

and then in the main just

test_iterator<cpp17_input_iterator<int*>>();
test_iterator<random_access_iterator<int*>>();
test_iterator<int*>();
test_iterator<const int*>();
etc.

[alvinhochun]

Addressed comments

[philnik]

LGTM with comments addressed and green CI.

libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp

27 ↗

(On Diff #476669)

We use Iter1 and Iter2 in newer tests to make clear what the type should be and I don't think we want to introduce other names for iterators, so please use these names instead.

67 ↗

(On Diff #476669)

To make it work in C++03.

69 ↗

(On Diff #476669)

I don't think we have to guard this. It doesn't hurt to test it in all versions.

[alvinhochun]

Addressed comments

[alvinhochun]

The CI build seems to have been stuck. @ldionne do you know what's going on? (I was told on IRC to ping you.)

[ldionne]

In D138268#3939747, @alvinhochun wrote:

The CI build seems to have been stuck. @ldionne do you know what's going on? (I was told on IRC to ping you.)

We've been having some trouble with the CI lately, but it should more or less be resolved now.

That being said, this patch needs work. You are changing several algorithms but only adding tests to std::equal.

Also, we probably have a similar problem in __less?

[alvinhochun]

In D138268#3949449, @ldionne wrote:

In D138268#3939747, @alvinhochun wrote:

The CI build seems to have been stuck. @ldionne do you know what's going on? (I was told on IRC to ping you.)

We've been having some trouble with the CI lately, but it should more or less be resolved now.

Thanks.

That being said, this patch needs work. You are changing several algorithms but only adding tests to std::equal.

My impression was that the existing tests would have been enough to cover them, because to the other algorithms this is just a refactoring. The main change allowing __equal_to to work with volatile types is already tested through the updated test of std::equal, which is the focus in the original issue report.

Also, we probably have a similar problem in __less?

It might be. I didn't look into it because I don't have a case that triggers the issue and I only planned to fix the bug I reported at first.

I could come back to this later if nobody has handled it...

libcxx/include/__algorithm/equal.h

for (; __first1 != __last1; ++__first1, (void)++__first2)
     if (!__pred(*__first1, *__first2))
       return false;
   return true;
 }
 
 template <class _InputIterator1, class _InputIterator2>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) {
-  typedef typename iterator_traits<_InputIterator1>::value_type __v1;
-  typedef typename iterator_traits<_InputIterator2>::value_type __v2;
+  typedef typename iterator_traits<_InputIterator1>::reference __v1;
+  typedef typename iterator_traits<_InputIterator2>::reference __v2;
   return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());
 }
 
 #if _LIBCPP_STD_VER > 11
 template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 __equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
         _BinaryPredicate __pred, input_iterator_tag, input_iterator_tag) {
   for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void)++__first2)
equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
   return _VSTD::__equal<_BinaryPredicate&>(
       __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_InputIterator1>::iterator_category(),
       typename iterator_traits<_InputIterator2>::iterator_category());
 }
 
 template <class _InputIterator1, class _InputIterator2>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
-  typedef typename iterator_traits<_InputIterator1>::value_type __v1;
-  typedef typename iterator_traits<_InputIterator2>::value_type __v2;
+  typedef typename iterator_traits<_InputIterator1>::reference __v1;
+  typedef typename iterator_traits<_InputIterator2>::reference __v2;
   return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(),
                         typename iterator_traits<_InputIterator1>::iterator_category(),
                         typename iterator_traits<_InputIterator2>::iterator_category());
 }
 #endif
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_EQUAL_H

libcxx/test/libcxx/algorithms/equal.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>
+
+// check that std::equal can accept iterators with cv-qualified types.
+
+#include <algorithm>
+
+#include "test_macros.h"
+
+// GCC 12 gives "warning: 'a' may be used uninitialized [-Wmaybe-uninitialized]"
+#if defined(__GNUC__) && !defined(__clang__)
+#  pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
+#endif
+
+template <class T1, class T2>
+void f() {
+  int a[3] = {1, 2, 3};
+  T1* x    = a;
+  T2* y    = a;
+  (void)std::equal(x, x + 3, y);
+  (void)std::equal(y, y + 3, x);
+#if TEST_STD_VER >= 14
+  (void)std::equal(x, x + 3, y, y + 3);
+  (void)std::equal(y, y + 3, x, x + 3);
+#endif
+}
+
+int main(int, char**) {
+  f<int, int>();
+  f<int, const int>();
+  f<int, volatile int>();
+  f<int, const volatile int>();
+  f<const int, const int>();
+  f<const int, volatile int>();
+  f<const int, const volatile int>();
+  f<volatile int, volatile int>();
+  f<volatile int, const volatile int>();
+  f<const volatile int, const volatile int>();
+  return 0;
+}