Page MenuHomePhabricator

[libc++][ranges] Make sure all range algorithms support differing projection types:
ClosedPublic

Authored by var-const on Jul 25 2022, 1:46 PM.

Details

Summary
  • for all algorithms taking more than one range, add a robust test to check the case where the ranges have different value types and the given projections are different, with each projection applying to a different value type;
  • fix ranges::include to apply the correct projection to each range.

Diff Detail

Event Timeline

var-const created this revision.Jul 25 2022, 1:46 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 25 2022, 1:46 PM
var-const requested review of this revision.Jul 25 2022, 1:46 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 447457.Jul 25 2022, 1:50 PM

Make sure the classic include doesn't change behavior.

The fix looks good to me and I think we should delete the overload __make_projected_comp(__comp, __proj1, __proj2) and replace all the usages with hand coded std::invoke

Fix the CI and rebase.

huixie90 accepted this revision.Jul 26 2022, 3:53 AM

This is a definitely needed fix. Whether or not to fix set_* algorithms in the same patch should not block this patch.

This revision is now accepted and ready to land.Jul 26 2022, 3:53 AM
ldionne accepted this revision.Jul 26 2022, 12:22 PM

The CI failure is unrelated.

This revision was landed with ongoing or failed builds.Jul 26 2022, 3:52 PM
This revision was automatically updated to reflect the committed changes.

The fix looks good to me and I think we should delete the overload __make_projected_comp(__comp, __proj1, __proj2) and replace all the usages with hand coded std::invoke

Without this test, I'd agree. With the test, however, I think the benefits outweigh the drawbacks. If an algorithm switches the comparison order, this test will break. However, make_projected_comp not only reduces on boilerplate and keeps most internal algorithms unaware of projections, it also allows passing in the original comparator without modification and "eliding" identity when possible.

The fix looks good to me and I think we should delete the overload __make_projected_comp(__comp, __proj1, __proj2) and replace all the usages with hand coded std::invoke

Without this test, I'd agree. With the test, however, I think the benefits outweigh the drawbacks. If an algorithm switches the comparison order, this test will break. However, make_projected_comp not only reduces on boilerplate and keeps most internal algorithms unaware of projections, it also allows passing in the original comparator without modification and "eliding" identity when possible.

Yes I do agree in general it keeps things tidy. I only have concerns with this particular overload that takes two projections. The problem is that the algorithm's concept constrained the __comp to be able to call __comp(*in1, *in1), __comp(*in1, *in2), __comp(*in2, *in1), __comp(*in2, *in2).
For example, https://en.cppreference.com/w/cpp/iterator/mergeable which calls https://en.cppreference.com/w/cpp/concepts/relation

But this particular overload assumes it always calls __comp(*in1, *in2). By having this overload available, in the future it could break things if we add new algorithms or even just use it internally

The fix looks good to me and I think we should delete the overload __make_projected_comp(__comp, __proj1, __proj2) and replace all the usages with hand coded std::invoke

Without this test, I'd agree. With the test, however, I think the benefits outweigh the drawbacks. If an algorithm switches the comparison order, this test will break. However, make_projected_comp not only reduces on boilerplate and keeps most internal algorithms unaware of projections, it also allows passing in the original comparator without modification and "eliding" identity when possible.

Yes I do agree in general it keeps things tidy. I only have concerns with this particular overload that takes two projections. The problem is that the algorithm's concept constrained the __comp to be able to call __comp(*in1, *in1), __comp(*in1, *in2), __comp(*in2, *in1), __comp(*in2, *in2).
For example, https://en.cppreference.com/w/cpp/iterator/mergeable which calls https://en.cppreference.com/w/cpp/concepts/relation

But this particular overload assumes it always calls __comp(*in1, *in2). By having this overload available, in the future it could break things if we add new algorithms or even just use it internally

Yes, but then the new test from this patch would break, right? I guess if we add a new algorithm, then we have to remember to update this test if appropriate, which is a downside. I still think that if we can verify that the projected comparator is only used with the non-reversed order of arguments, it's better to use it.

If you can think of a case where we could use the projected comparator incorrectly and this test would *not* break, let me know -- that would be pretty bad.