[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 ↗

(On Diff #476392)

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

2

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

18–21

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

[ldionne]

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

2

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

36 ↗

(On Diff #476464)

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/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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11
+
+// <algorithm>
+
+// check that std::equal can accept iterators with cv-qualified types.
+
+#include <algorithm>
+
+template <typename T1, typename T2>
+void f() {
+  int a[3]{1, 2, 3};
+  T1* x = a;
+  T2* y = a;
+  (void)std::equal(x, x + 3, y, y + 3);
+  (void)std::equal(y, y + 3, x, x + 3);
+}
+
+int main(int, char**) {
+  f<int, int>();
+  f<int, const int>();
+  f<int, volatile int>();
+  f<int, const volatile int>();
+  f<const int, volatile int>();
+  f<const int, const volatile int>();
+  f<const volatile int, const volatile int>();
+  return 0;
+}