This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implement ranges::{reverse, rotate}_copy
ClosedPublic

Authored by philnik on Jun 7 2022, 6:08 AM.

Details

Diff Detail

Event Timeline

philnik created this revision.Jun 7 2022, 6:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 7 2022, 6:08 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Jun 7 2022, 6:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 7 2022, 6:08 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const requested changes to this revision.Jun 9 2022, 6:17 PM
var-const added inline comments.
libcxx/docs/Status/RangesAlgorithms.csv
57–58

As per usual, please update. :)

libcxx/include/__algorithm/ranges_reverse_copy.h
20

Nit: include <__utility/move.h>.

26

Please add the language version / no incomplete ranges guard (other file as well).

40–41

These functions are verbose and using them seems a little clunky (they take a different number of arguments, it's not obvious whether e.g. begin in the name means "make rbegin" or "make rend from the begin iterator", etc.). How about having a single function that returns a pair of iterators instead? I don't think it should add any noticeable overhead:

auto [__rfirst, __rlast] = std::__to_reverse_iterators(__first, __last);
auto __ret = ranges::copy(std::move(__rfirst), std::move(__rlast), std::move(__result));
libcxx/include/algorithm
1153

Please add the synopsis.

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp
13

Missing synopsis.

48

Nit: decltype(auto).

libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges.rotate_copy.pass.cpp
13

Missing synopsis.

24

s/Reverse/Rotate/.

48

Nit: decltype(auto).

76

Please also check with a two-element range (the smallest range that can actually be rotated, and it has an even number of elements which otherwise is not tested).

This revision now requires changes to proceed.Jun 9 2022, 6:17 PM
philnik updated this revision to Diff 438588.Jun 21 2022, 1:15 AM
philnik marked 11 inline comments as done.
  • Address comments
ldionne added inline comments.Jun 30 2022, 6:11 AM
libcxx/include/__iterator/reverse_iterator.h
326

inline is unnecessary since this is a template.
I suspect constexpr won't work in C++11/14/17 (but you could check 17, it might).

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp
29

I would like an explicit test that is_same<reverse_copy_result<....>, in_out_result<...>>. In fact, I don't see that type mentioned anywhere in the tests, so we wouldn't even notice if we didn't define it. Please do that here but also for all the other algorithms that have been added and that had accompanying foo_result types.

var-const accepted this revision as: var-const.Jul 1 2022, 4:49 PM

LGTM with just a couple of minor things. I'll leave the final approval to @ldionne since he had comments.

libcxx/include/__iterator/reverse_iterator.h
336

make_pair?

libcxx/include/algorithm
396

Please add the definition of {reverse,rotate}_copy_result to the synopsis as well.

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp
29

Maybe create a dedicated file for this, similar to ranges_robust_against_copying_*? It seems like these checks will be really similar.

philnik updated this revision to Diff 442504.Jul 6 2022, 3:52 AM
philnik marked 5 inline comments as done.
  • Address comments

@var-const could you take another look? I basically rewrote ranges::reverse_copy.

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse_copy.pass.cpp
29

I'll make a dedicated ranges_result_alias_declarations.compile.pass.cpp in it's own PR.

LGTM

libcxx/include/__algorithm/ranges_reverse_copy.h
17

I might miss something but where is this used? (same apply to the other range algorithm header in the review

var-const requested changes to this revision.Jul 7 2022, 5:53 PM
var-const added inline comments.
libcxx/include/__algorithm/ranges_reverse_copy.h
52

While this allows for a very elegant implementation, the view is way more heavyweight than a simple eager implementation would be. I'd rather avoid the dependency: it adds compilation time overhead, gives users a way to accidentally depend on something they don't include directly, and it might be less efficient (caching logic looks suspicious in that regard).

Whichever approach we settle upon will likely affect some other algorithms as well, so let's check with @ldionne.

This revision now requires changes to proceed.Jul 7 2022, 5:53 PM
ldionne added inline comments.Jul 8 2022, 6:26 AM
libcxx/include/__algorithm/ranges_reverse_copy.h
52

I think I'd be OK with this. We're trying to granularize headers so that this kind of reuse becomes possible. And we do have an optimization for reverse iterators in std::__copy, so this should end up being as efficient as a hand-written implementation for contiguous iterators.

I would suggest creating a really simple utility, something like std::__reverse_range(rng) that returns a pair of reverse_iterators from a range. This basically does the job of reverse_view, but without the need for caching and any other complicated logic. It only needs to have logic for using std::make_reverse_iterator(ranges::end(rng)) or std::make_reverse_iterator(ranges::next(ranges::begin(rng), ranges::end(rng))) depending on whether rng is a common view. I suspect this would tackle the concern of pulling in too many dependencies.

philnik updated this revision to Diff 443295.Jul 8 2022, 11:12 AM
philnik marked 2 inline comments as done.
  • Address comments
var-const accepted this revision.Jul 8 2022, 12:01 PM
This revision is now accepted and ready to land.Jul 8 2022, 12:01 PM
philnik updated this revision to Diff 443385.Jul 8 2022, 4:10 PM
  • Try to fix CI
philnik updated this revision to Diff 443401.Jul 8 2022, 6:07 PM
  • Try to fix CI
philnik updated this revision to Diff 443490.Jul 10 2022, 3:55 AM
  • Add include
philnik updated this revision to Diff 443502.Jul 10 2022, 6:25 AM
  • Add header to modulemap
philnik updated this revision to Diff 443504.Jul 10 2022, 6:42 AM
  • Next tryx
philnik updated this revision to Diff 443629.Jul 11 2022, 7:08 AM
  • Fix modulemap
philnik updated this revision to Diff 443638.Jul 11 2022, 7:49 AM
  • Fix CMakeLists
philnik updated this revision to Diff 443647.Jul 11 2022, 8:07 AM
  • Next try
This revision was automatically updated to reflect the committed changes.