This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by thomasanderson on Jan 24 2018, 8:02 PM.

Details

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

Diff Detail

Event Timeline

thomasanderson created this revision.Jan 24 2018, 8:02 PM

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

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

More context in diff

@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 added a comment.EditedJan 24 2018, 9:20 PM

Nevermind.

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

Disregard that, I'm an idiot.

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 added inline comments.Jan 25 2018, 6:07 AM
include/algorithm
1426

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

mclow.lists added inline comments.Jan 25 2018, 6:10 AM
include/algorithm
1426

Yes, I broke it.

mclow.lists accepted this revision.Jan 25 2018, 6:11 AM

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

This revision is now accepted and ready to land.Jan 25 2018, 6:11 AM
mclow.lists accepted this revision.Jan 25 2018, 9:18 PM

Looks good to me. Thanks!

thanks for the reviews

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

pcc added a comment.Jan 26 2018, 1:21 PM

I will land it.

This revision was automatically updated to reflect the committed changes.