[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