This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] implement `std::ranges::unique{_copy}`
ClosedPublic

Authored by huixie90 on Jul 22 2022, 5:45 PM.

Details

Summary

implement std::ranges::unique and std::ranges::unique_copy

Several changes:

  1. implement std::ranges::unique that delegates to std::unique
  1. fix classic std::unique_copy does not work with output iterator that satisfies both InputIterator and OutputIterator requirements.

background: The classic implementation does tag dispatch on the iteartor_category of the output iterator and uses output_iterator_tag as a fallback. However, if the user passes an output iterator that satisfy both
InputIterator and OutputIterator requirement, the iteartor_category is likely to be input_iteartor_tag and input_iteartor_tag does not derive from output_iterator_tag. So the fallback case would not work.

See this example where msvc stl correctly implemented and libc++ errors out
https://godbolt.org/z/7shKshEPa

The fix to the classic algorithm is strictly following the wording

If InputIterator meets the Cpp17ForwardIterator requirements, then there are no additional requirements for T.

Having an overload that takes __reread_from_input_tag, which does auto prev = in; comp(*prev, *in)

Otherwise, if OutputIterator meets the Cpp17ForwardIterator requirements and its value type is the same as T, then T meets the Cpp17CopyAssignable (Table 33) requirements.

Having an overload that takes __reread_from_output_tag, which does comp(*out, *in)

Otherwise, T meets both the Cpp17CopyConstructible (Table 31) and Cpp17CopyAssignable requirements.

Having an overload that takes __read_from_tmp_value_tag, which does value_type tmp = *in; ++in; comp(tmp, *in)

  1. implement std::ranges::unique_copy, which reuses the implementation above, but slightly different dispatching condition as ranges version has slightly different requires constraints.

Also I believe the std::ranges::unique_copy is incorrectly constrained. More specifically, the intent of the constraint (input_­iterator<O> && same_­as<iter_value_t<I>, iter_value_t<O>>) was to allow implementations to write comp(*in ,*out) (ignore std::invoke and projection for now). However, I and O having the same value_type is not enough to allow comp(*in ,*out), because that expression only uses the iter_reference_t of the I and O, instead of the iter_value_t. See discussion here
https://discord.com/channels/737189251069771789/737189251497721887/1000875764650094692

But anyway, I decided that in this patch, implement what exactly in the spec and bring up the issue in LWG later.

Diff Detail

Event Timeline

huixie90 created this revision.Jul 22 2022, 5:45 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 22 2022, 5:45 PM
huixie90 updated this revision to Diff 447152.Jul 24 2022, 3:57 PM

refactor unique_copy

huixie90 updated this revision to Diff 447367.Jul 25 2022, 9:04 AM

implement unique_copy

huixie90 published this revision for review.Jul 25 2022, 9:40 AM
huixie90 edited the summary of this revision. (Show Details)
Herald added a project: Restricted Project. · View Herald TranscriptJul 25 2022, 9:40 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const accepted this revision as: var-const.Jul 27 2022, 12:47 AM

LGTM, leaving the final approval to @ldionne.

libcxx/include/__algorithm/adjacent_find.h
51

Nit: move?

libcxx/include/__algorithm/unique.h
39

Nit: I'd move the increment back into its own line, otherwise there's a little too much going on on this line.

libcxx/include/__algorithm/unique_copy.h
80–94

Perhaps InputOrOutputIterator?

libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique.pass.cpp
129

Optional: maybe check a single-element range for good measure?

libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp
91

Please also update test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp.

huixie90 updated this revision to Diff 448015.Jul 27 2022, 5:52 AM
huixie90 marked 5 inline comments as done.

addresss feedback

libcxx/include/__algorithm/unique_copy.h
80–94

Renamed to InputAndOutputIterator

huixie90 updated this revision to Diff 448349.Jul 28 2022, 8:50 AM
  • finalise ranges::remove_copy{_if}
huixie90 updated this revision to Diff 448350.Jul 28 2022, 8:51 AM

got patch number wrong

ldionne accepted this revision.Jul 28 2022, 12:03 PM

Thanks a lot for the patch @huixie90! Since you're on vacation, @var-const can you please commandeer to finish this up? LGTM w/ comments applied.

libcxx/include/__algorithm/adjacent_find.h
28–38

How about this? It's equivalent, but I find it slightly easier to read.

Non-blocking if you disagree.

libcxx/include/__algorithm/ranges_unique_copy.h
95

FWIW this formatting is really hard to read for me, I assume it's produced by clang-format?

libcxx/include/__algorithm/unique_copy.h
37

I think we should call it __unique_copy instead for consistency with other algorithms (even though I understand we're passing an additional tag parameter).

47

Do we have a test for calling unique_copy with a value_type that is not copyable? IIUC that would be valid when the input range is at least a forward_iterator.

This revision is now accepted and ready to land.Jul 28 2022, 12:03 PM
huixie90 updated this revision to Diff 448424.Jul 28 2022, 1:05 PM
huixie90 marked 3 inline comments as done.

address review feedback

Also thanks to @Quuxplusone who contacted me and spotted that I missed an if constexpr in ranges::unique_copy and an unnecessary next call in adjacent_find

libcxx/include/__algorithm/adjacent_find.h
28–38

Yes your suggestion is easier to read

libcxx/include/__algorithm/ranges_unique_copy.h
95

yes it is done by clang-format. yes it is really hard to read. I will try manually formatting it.

libcxx/include/__algorithm/unique_copy.h
37

sure will rename. the direct reason I didn't use __unique_copy at the first place is that I used this name for the namespace few lines above. But I can rename that namespace

47

good spot. we do have tests in ranges version but no tests in classic

This revision was automatically updated to reflect the committed changes.