[libcxx] Qualify make_pair in searcher implementations to prevent ADL

[logan-5]

Summary

This patch adds _VSTD:: to some calls to make_pair inside the implementations of searchers, to prevent things exploding if there is a make_pair in an associated namespace of a user-defined type. https://godbolt.org/z/xAFG98

I didn't fix (or add tests to) the Boyer-Moore or Boyer-Moore-Horspool searchers in experimental/, since I couldn't get those to work with user-defined types at all. After defining the hash function properly, there seems to be an issue with a vector<value_type> __scratch in a helper function that I don't understand. See https://godbolt.org/z/heJ75B -- the same code works with libstdc++. If this is a separate issue, I'd be happy to write up a bug. (Also, I don't even know... is the experimental/ stuff still actively supported/bugfixed/etc?)

I did, however, add tests to the regular (currently XFAILed) BM and BMH tests in utilities.

I found this (and a couple other issues, patches forthcoming) by running https://reviews.llvm.org/D72282 over libc++ locally.

[• Quuxplusone]

there seems to be an issue with a vector<value_type> __scratch in a helper function that I don't understand

My relatively uneducated guess is that it should have been a vector<size_t> __scratch all along. If you make that change, then your test case compiles. Also, if you're searching in a string of char, then char is smaller than size_t and bad stuff happens:
https://godbolt.org/z/i52zkN triggers an assertion failure corrupted size vs. prev_size and I can't even figure out where that message is coming from!

[logan-5]

Fixed some wrong author information in the patch.

[EricWF]

I don't know that you needed to duplicate all the tests, but this works for me.

LGTM.

libcxx/test/std/utilities/function.objects/func.search/func.search.bmh/pred.pass.cpp

70 ↗

(On Diff #238615)

delete;

[logan-5]

Thanks. In that case I'll need help committing this.

libcxx/test/std/utilities/function.objects/func.search/func.search.bmh/pred.pass.cpp

70 ↗

(On Diff #238615)

What's the advantage of = delete;ing this function versus what I've done here?

[• Quuxplusone]

@EricWF ping! (@logan-5 says he needs someone to land this patch, and I think that's you.)

@logan-5, you mentioned that you have found other cases of unintended ADL by applying the clang-tidy check in D72282, right? But those patches have not yet been uploaded to Phab? Is there any help I can offer that would advance that work?

[logan-5]

In D72640#1862239, @Quuxplusone wrote:

@logan-5, you mentioned that you have found other cases of unintended ADL by applying the clang-tidy check in D72282, right? But those patches have not yet been uploaded to Phab? Is there any help I can offer that would advance that work?

Hi @Quuxplusone, thanks a lot for the ping. I did indeed promise more patches for more cases found by that clang-tidy check, but I haven't gotten a chance to implement them yet. I think I was waiting for this one to land completely for some reason.

I think I'll be able to get to it this weekend... unless somebody beats me to it. :)

[logan-5]

Pinging this again.

[EricWF]

There are some simplifications suggested in the inline comments.
Once those are addressed, this LGTM.

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

51

Please add a single additional test for each function that was fixed.
Separation of test concerns is better than carpet bombing the tests to prevent ADL,
and it makes the added test more understandable.

Once that's done this diff should be much smaller than it currently is.

76

Make this a non-member.

82

= delete

[logan-5]

Pruned down tests to the essentials.

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

76

No problem, but curious about the reason.

82

Also curious. This doesn't seem like it makes much of a difference, although I suppose = delete communicates better that we don't intend to call this in the tests anywhere.

[logan-5]

Formatting.

[logan-5]

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

113

I used this formatting (and the rest of the formatting in this diff) to be consistent with the pre-existing surrounding code in this file. The clang-tidy lint check is complaining here though. Is it more important to make those checks pass, or be consistent with the surrounding file? Genuine question.

[EricWF]

LGTM.

Thanks!

[logan-5]

Thanks. I'll need committing help, if this is good to go.

[ldionne]

Thanks for the patch! Committed as

commit 5b4a98eb58aa7672bbdc5e31e573f8f1220fc9c7
Author: Logan Smith <[e-mail]>
Date:   Thu May 7 11:54:25 2020 -0400

    [libcxx] Qualify make_pair in searcher implementations to prevent ADL

    This patch adds `_VSTD::` to some calls to `make_pair` inside the
    implementations of searchers, to prevent things exploding if there is
    a make_pair in an associated namespace of a user-defined type.
    https://godbolt.org/z/xAFG98

    Differential Revision: https://reviews.llvm.org/D72640

libcxx/include/functional

 
 template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
 pair<_ForwardIterator1, _ForwardIterator1> _LIBCPP_CONSTEXPR_AFTER_CXX11
 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
          _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
          forward_iterator_tag, forward_iterator_tag)
 {
     if (__first2 == __last2)
-        return make_pair(__first1, __first1);  // Everything matches an empty sequence
+        return _VSTD::make_pair(__first1, __first1);  // Everything matches an empty sequence
     while (true)
     {
         // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
         while (true)
         {
             if (__first1 == __last1)  // return __last1 if no element matches *__first2
-                return make_pair(__last1, __last1);
+                return _VSTD::make_pair(__last1, __last1);
             if (__pred(*__first1, *__first2))
                 break;
             ++__first1;
         }
         // *__first1 matches *__first2, now match elements after here
         _ForwardIterator1 __m1 = __first1;
         _ForwardIterator2 __m2 = __first2;
         while (true)
         {
             if (++__m2 == __last2)  // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
-                return make_pair(__first1, __m1);
+                return _VSTD::make_pair(__first1, __m1);
             if (++__m1 == __last1)  // Otherwise if source exhaused, pattern not found
-                return make_pair(__last1, __last1);
+                return _VSTD::make_pair(__last1, __last1);
             if (!__pred(*__m1, *__m2))  // if there is a mismatch, restart with a new __first1
             {
                 ++__first1;
                 break;
             }  // else there is a match, check next elements
         }
     }
 }
 
 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
 _LIBCPP_CONSTEXPR_AFTER_CXX11
 pair<_RandomAccessIterator1, _RandomAccessIterator1>
 __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
          _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
            random_access_iterator_tag, random_access_iterator_tag)
 {
     typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
     typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
     // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
     const _D2 __len2 = __last2 - __first2;
     if (__len2 == 0)
-        return make_pair(__first1, __first1);
+        return _VSTD::make_pair(__first1, __first1);
     const _D1 __len1 = __last1 - __first1;
     if (__len1 < __len2)
-        return make_pair(__last1, __last1);
+        return _VSTD::make_pair(__last1, __last1);
     const _RandomAccessIterator1 __s = __last1 - (__len2 - 1);  // Start of pattern match can't go beyond here
 
     while (true)
     {
         while (true)
         {
             if (__first1 == __s)
-                return make_pair(__last1, __last1);
+                return _VSTD::make_pair(__last1, __last1);
             if (__pred(*__first1, *__first2))
                 break;
             ++__first1;
         }
 
         _RandomAccessIterator1 __m1 = __first1;
         _RandomAccessIterator2 __m2 = __first2;
          while (true)
          {
              if (++__m2 == __last2)
-                 return make_pair(__first1, __first1 + __len2);
+                 return _VSTD::make_pair(__first1, __first1 + __len2);
              ++__m1;          // no need to check range on __m1 because __s guarantees we have enough source
              if (!__pred(*__m1, *__m2))
              {
                  ++__first1;
                  break;
              }
          }
     }

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

return    (std::search(std::begin(ic), std::end(ic), std::begin(ia), std::end(ia)) == ic+3)
            ;
     }
 #endif
 
 int searcher_called = 0;
 
 struct MySearcher {
     template <typename Iterator>
     std::pair<Iterator, Iterator>
     operator() (Iterator b, Iterator e) const
     {
         ++searcher_called;
         return std::make_pair(b, e);
     }
 };
 
+namespace User {
+struct S {
+    S(int x) : x(x) {}
+    int x;
+};
+bool operator==(S lhs, S rhs)
+{
+    return lhs.x == rhs.x;
+}
+template <class T, class U>
+void make_pair(T&&, U&&) = delete;
+} // namespace User
+
 template <class Iter1, class Iter2>
 void
 test()
 {
     int ia[] = {0, 1, 2, 3, 4, 5};
     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia)) == Iter1(ia));
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1)) == Iter1(ia));
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2)) == Iter1(ia+1));
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2)) == Iter1(ia));
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3)) == Iter1(ia+2));
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3)) == Iter1(ia+2));
     assert(std::search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3)) == Iter1(ia));
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa)) == Iter1(ia+sa-1));
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa)) == Iter1(ia+sa-3));
     assert(std::search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa)) == Iter1(ia));
     assert(std::search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa)) == Iter1(ia+sa-1));
     assert(std::search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa)) == Iter1(ia+1));
     int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
test()
     assert(std::search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3)) == Iter1(ih+3));
     int ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
     const unsigned sj = sizeof(ij)/sizeof(ij[0]);
     int ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
     const unsigned sk = sizeof(ik)/sizeof(ik[0]);
     assert(std::search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk)) == Iter1(ij+6));
 }
 
+template <class Iter>
+void
+adl_test()
+{
+    User::S ua[] = {1};
+    assert(std::search(Iter(ua), Iter(ua), Iter(ua), Iter(ua)) == Iter(ua));
+}
+
 int main(int, char**)
 {
     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<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<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*> >();
 
+    adl_test<forward_iterator<User::S*> >();
+    adl_test<random_access_iterator<User::S*> >();
+
 #if TEST_STD_VER > 14
 {
     typedef int * RI;
     static_assert((std::is_same<RI, decltype(std::search(RI(), RI(), MySearcher()))>::value), "" );
 
     RI it(nullptr);
     assert(it == std::search(it, it, MySearcher()));
     assert(searcher_called == 1);