Fix the BinaryPredicate form of std::is_permutation to not rely on operator==

[thomasanderson]

Summary

According to [1], forms 2 and 4 of std::is_permutation should use the passed in
binary predicate to compare elements. operator== should only be used for forms
1 and 3 which do not take a binary predicate.

This CL fixes forms 2 and 4 which relied on operator== for some comparisons.

[1] http://en.cppreference.com/w/cpp/algorithm/is_permutation

[thomasanderson]

thakis and/or pcc ptal. This is necessary for https://chromium-review.googlesource.com/c/chromium/src/+/875330 to land

[pcc]

Can you please upload a patch with more context (pass -U9999 to diff or use arc diff)?

[thomasanderson]

More context in diff

[EricWF]

@thomasanderson The comparison you're removing is one between iterators, not values. I don't believe there is any restrictions preventing the iterators operator== from being invoked -- only the value types. I only glanced at the Chrome patch you cited, but it wasn't immediately clear why that patch might require this change.

Also, any change like this requires additional tests for libc++ to ensure we don't regress. This document should help you get started testing libc++, but let me know if I can be of any help.

[EricWF]

Nevermind.

In D42518#987418, @EricWF wrote:

@thomasanderson The comparison you're removing is one between iterators, not values.

Disregard that, I'm an idiot.

[EricWF]

After my initial silly mistake, I think this LGTM. I'll wait until tomorrow to green light it in case @mclow.lists wants to review.

(Plus, we still need a test :-) )

[mclow.lists]

include/algorithm

1426

I wonder if I broke this with my recent changes to this routine.

[mclow.lists]

include/algorithm

1426

Yes, I broke it.

[mclow.lists]

This LGTM. Sorry for the breakage.
Clearly we need a test with a non op== BinaryPredicate

[thomasanderson]

Added test

[mclow.lists]

Looks good to me. Thanks!

[thomasanderson]

thanks for the reviews

Also, I don't have write permissions in the repo, so I would appreciate if anyone could land this

[pcc]

I will land it.

include/algorithm

//  __first1 != __last1 && *__first1 != *__first2
     if (__l1 == _D1(1))
         return false;
     _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1);
     // For each element in [f1, l1) see if there are the same number of
     //    equal elements in [f2, l2)
     for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
     {
     //  Have we already counted the number of *__i in [f1, l1)?
-        if (find(__first1, __i, *__i) == __i) {
+        _ForwardIterator1 __match = __first1;
+        for (; __match != __i; ++__match)
+            if (__pred(*__match, *__i))
+                break;
+        if (__match == __i) {
             // Count number of *__i in [f2, l2)
             _D1 __c2 = 0;
             for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
                 if (__pred(*__i, *__j))
                     ++__c2;
             if (__c2 == 0)
                 return false;
             // Count number of *__i in [__i, l1) (we can start with 1)
             _D1 __c1 = 1;
//  shorten sequences as much as possible by lopping of any equal prefix
     if (__l1 != __l2)
         return false;
 
     // For each element in [f1, l1) see if there are the same number of
     //    equal elements in [f2, l2)
     for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i)
     {
     //  Have we already counted the number of *__i in [f1, l1)?
-        if (find(__first1, __i, *__i) == __i) {
+        _ForwardIterator1 __match = __first1;
+        for (; __match != __i; ++__match)
+            if (__pred(*__match, *__i))
+                break;
+        if (__match == __i) {
             // Count number of *__i in [f2, l2)
             _D1 __c2 = 0;
             for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j)
                 if (__pred(*__i, *__j))
                     ++__c2;
             if (__c2 == 0)
                 return false;
             // Count number of *__i in [__i, l1) (we can start with 1)

test/std/algorithms/alg.nonmodifying/alg.is_permutation/is_permutation_pred.pass.cpp

 #if TEST_STD_VER >= 14
         assert(std::is_permutation(forward_iterator<const int*>(ia),
                                    forward_iterator<const int*>(ia + sa),
                                    forward_iterator<const int*>(ib),
                                    forward_iterator<const int*>(ib + sa),
                                    std::equal_to<const int>()) == false);
 #endif
     }
+    {
+      struct S {
+          S(int i) : i_(i) {}
+          bool operator==(const S& other) = delete;
+          int i_;
+      };
+      struct eq {
+          bool operator()(const S& a, const S&b) { return a.i_ == b.i_; }
+      };
+      const S a[] = {S(0), S(1)};
+      const S b[] = {S(1), S(0)};
+      const unsigned sa = sizeof(a)/sizeof(a[0]);
+      assert(std::is_permutation(forward_iterator<const S*>(a),
+                                 forward_iterator<const S*>(a + sa),
+                                 forward_iterator<const S*>(b),
+                                 eq()));
+#if TEST_STD_VER >= 14
+      assert(std::is_permutation(forward_iterator<const S*>(a),
+                                 forward_iterator<const S*>(a + sa),
+                                 forward_iterator<const S*>(b),
+                                 forward_iterator<const S*>(b + sa),
+                                 eq()));
+#endif
+    }
 
 #if TEST_STD_VER > 17
     static_assert(test_constexpr());
 #endif
 }