This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][ranges] implement `std::ranges::set_difference`
ClosedPublic

Authored by huixie90 on Jul 1 2022, 4:34 AM.

Details

Summary

implement std::ranges::set_difference
reused classic std::set_difference
added unit tests

Diff Detail

Event Timeline

huixie90 created this revision.Jul 1 2022, 4:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 1 2022, 4:34 AM
Herald added a subscriber: mgorny. · View Herald Transcript
huixie90 requested review of this revision.Jul 1 2022, 4:34 AM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const requested changes to this revision.Jul 2 2022, 2:31 PM

Looks pretty good overall, the only substantial comment is about avoid observable changes in behavior in the classic set_difference algorithm. Thanks for working on this!

libcxx/docs/Status/RangesAlgorithms.csv
64

Please add a link to this patch.

libcxx/include/__algorithm/ranges_set_difference.h
47

Nit: unnecessary std::.

51

Nit: unnecessary (I think) space. Is this done by clang-format? If yes, it's not worth changing.

libcxx/include/__algorithm/set_difference.h
38

Does using decay here lead to any observable difference?

53

Wouldn't using invoke here create an observable change in behavior for the classic algorithm? It seems like it would cause e.g. passing a pointer to member to work with the classic algorithm which wasn't the case before.

Instead, I would strongly recommend the following trick: in the range algorithm, create a lambda that wraps the comparator and the projection functors and pass it as the comparator. It also avoids the need to pass the projections directly. See e.g. ranges_sort.h:

auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
std::__sort_impl(std::move(__first), __last_iter, __projected_comp);
62–76

Optional: you can also s/_LIBCPP_INLINE_VISIBILITY/_LIBCPP_HIDE_FROM_ABI/ since you're changing this line anyway. _LIBCPP_HIDE_FROM_ABI is the newer name for the same macro (we use it in new code and IMO it's good to update the old code to use the new name when opportunity arises).

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp
97

Ultranit: qualify std:: for consistency?

150

Can you also check the case when the lengths are the same (but the elements are different)?

206

Nit: the test case doesn't seem to check borrowed_range, so remove that part of the comment?

235

Nit: probably needs renaming for consistency with the merge test.

245

Question: does cpp17_input_iterator not work? If yes, can you add a short comment indicating why it doesn't work, to make it clear it wasn't forgotten but deliberately omitted?

262

Since this class is already used here and in merge test, and will likely be used more in further tests, it should probably be moved into a shared header with helpers.

This revision now requires changes to proceed.Jul 2 2022, 2:31 PM
huixie90 updated this revision to Diff 442115.Jul 4 2022, 9:33 AM
huixie90 marked 11 inline comments as done.

address comments

huixie90 added inline comments.Jul 4 2022, 9:49 AM
libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp
245

The algorithm requires the input to be std::input_iterator which is a c++ 20 concept. cpp_17_input_iterator might or might not work, depending on whether or not it models C++20 input_iterator concept.

IMO it doesn't add too much in the test, and at the same time it couples the test to the implementation of cpp_17_input_iterator. Whether or not model c++ 20's input_iterator might change for that particular class.

If we really want to test it must work, we should probably create another class cpp17_and_cpp20_input_iterator

What do you think?

huixie90 updated this revision to Diff 442138.Jul 4 2022, 1:07 PM

remove non ascii characters

var-const accepted this revision as: var-const.Jul 5 2022, 4:10 PM

Thanks for addressing the feedback!

libcxx/include/__algorithm/make_projected.h
50

Question: why is this check necessary (is_member_pointer)?

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp
245

If a type modeling the _bare minimum_ required to satisfy cpp17_input_iterator doesn't meet the requirements, then we can say that cpp17_input_iterator doesn't work. Consider a comment like "cpp17_input_iterator doesn't satisfy the std::input_iterator constraint".

huixie90 added inline comments.Jul 5 2022, 4:29 PM
libcxx/include/__algorithm/make_projected.h
50

if the caller is passing a member function pointer as comparator and two identitys as projections, without this check, if would just return __comp, which is a member function pointer. And the returned member function pointer is used by the __impl function and the __impl function simply invoke operator() as __comp(*first, *second). This would fail because member function pointer don't support this syntax.

I suspect the overload above needs the same treatment. For the algorithms you've implemented, do you have any tests that pass a member function pointer as comparator and std::identity as projection?

huixie90 updated this revision to Diff 442451.Jul 6 2022, 12:10 AM
huixie90 marked 3 inline comments as done.

address feedback

var-const accepted this revision.Jul 6 2022, 4:12 PM
var-const added inline comments.
libcxx/include/__algorithm/make_projected.h
50

Thanks a lot for fixing the existing overload!

This revision is now accepted and ready to land.Jul 6 2022, 4:12 PM
philnik accepted this revision.Jul 7 2022, 3:47 PM

LGTM % nits.

libcxx/include/__algorithm/ranges_set_difference.h
68–96

This formatting is really weird. Hopefully I'll have some time soon to fix clang-format a bit.

libcxx/include/__algorithm/set_difference.h
68–76

Why aren't you returning std::__set_difference(...).second here? IIUC explicitly doing the move is either redundant because of implicit move or detrimental because of copy elision.

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
127

Could you also uncomment the corresponding line in ranges_result_alias_declarations.compile.pass.cpp?

var-const added inline comments.Jul 7 2022, 4:59 PM
libcxx/include/__algorithm/set_difference.h
68–76

I think implicit move doesn't apply when returning a member of an object, even if the object itself is a local variable.

philnik added inline comments.Jul 7 2022, 5:06 PM
libcxx/include/__algorithm/set_difference.h
68–76

https://godbolt.org/z/q1rj39Tdf looks to me a lot like an implicit move.

huixie90 updated this revision to Diff 443091.Jul 7 2022, 5:09 PM
huixie90 marked 3 inline comments as done.

address feedback

libcxx/include/__algorithm/set_difference.h
68–76

Double checked with several compilers, it is always a move
https://godbolt.org/z/GPTnzhj38

not because it is implicit move, it is because the expression make_pair(x, y).second yields an rvalue reference to the second member,
so no need for explicit move here

This revision was automatically updated to reflect the committed changes.
huixie90 marked an inline comment as done.