This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implement ranges::copy{, _n, _if, _backward}
ClosedPublic

Authored by philnik on Apr 2 2022, 9:50 AM.

Diff Detail

Event Timeline

philnik created this revision.Apr 2 2022, 9:50 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 2 2022, 9:50 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Apr 2 2022, 9:50 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 2 2022, 9:50 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik updated this revision to Diff 420105.Apr 3 2022, 11:21 PM
  • Try to fix CI
philnik updated this revision to Diff 420109.Apr 4 2022, 12:00 AM
  • Try to fix GCC

In general looks good, several small issues.

libcxx/include/__algorithm/copy.h
85

Do we need to have an additional specialization? where

__enable_if_t<is_copy_constructible<_InIter>::value
             && is_copy_constructible<_Sent>::value
             && !is_copy_constructible<_OutIter>::value> >

Just to make sure that a copy of a std::string to a non-copyable output iterator is still unwrapped.
This is will be used in std::format.

libcxx/include/__algorithm/copy_backward.h
56

Did you have a look at the codegen for this change?

libcxx/include/__algorithm/ranges_copy.h
34

_InIter and _OutIter for consistency?

libcxx/include/__algorithm/ranges_copy_backward.h
32

:-) Happy you didn't follow the wording in the Standard.

38

I would suggest to use _Ip and _Op or change the copy_backward_result above.
In general this naming doesn't seem to use the new slightly longer names.

libcxx/include/__algorithm/ranges_copy_if.h
50

The original is correct, but this is closer to the wording of the Standard.

libcxx/include/algorithm
88

Are the copy*result types already in the synopsis?

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_copy.module.verify.cpp
1 ↗(On Diff #420109)

These files will no longer be needed after D123028.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp
161

Seems a copy paste.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
14

Please add the synopsis.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_if.pass.cpp
113

Please count the number of invocations the predicated, same for the projection below.

151

I would like to see tests for cpp20_output_iterator.

var-const requested changes to this revision.Apr 4 2022, 6:10 PM
var-const added inline comments.
libcxx/include/__algorithm/copy.h
40–80

Hmm, if I'm reading this correctly, the previous condition supported copying from const T* to T*, whereas the new condition only supports T* to T*. Am I missing something?

45

Can you please add a comment to explain the GCC workaround?

52

Question: what's the advantage of using __builtin_memmove directly?

57

Question: what's the reason to change from _LIBCPP_CONSTEXPR_AFTER_CXX17 to _LIBCPP_CONSTEXPR_AFTER_CXX11?

59

Question: can this simply return std::__copy_impl ...?

96

Nit: move?

libcxx/include/__algorithm/ranges_copy.h
33

Nit: this should probably use longer names.

libcxx/include/__algorithm/ranges_copy_backward.h
38

Nit: looks like these need to be renamed to something like Iter1 or InIter.

42

Nit: move the arguments? (for consistency with ranges_copy.h)

libcxx/include/__algorithm/ranges_copy_if.h
44

Question: why doesn't this algorithm delegate to the non-ranges version (is it to avoid having to deal with the projection)?

libcxx/include/__algorithm/ranges_copy_n.h
27

Nit: there's an extra blank line here (2 in a row).

libcxx/include/algorithm
109

ranges::copy_backward seems to be missing.

var-const added inline comments.Apr 4 2022, 6:10 PM
libcxx/include/__algorithm/copy.h
89

Question: any reason not to use make_pair?

libcxx/include/__algorithm/copy_backward.h
29

Optional: make_reverse_iterator to omit the type?

38

Optional: I think it would be more readable to create another variable for __result_first or similar instead of calculating it on the fly below.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp
179

Nit: in most of these tests, the ranges version goes after the iterator version.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
26

Nit: for consistency, s/HasCopyIt/HasCopyBackwardIt (throughout the file).

51

I think the current tests always use trivially copyable values -- can we add at least one test case where values are not trivially copyable?

155

Optional: s/next/prev/?

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_if.pass.cpp
115

Nit: can you please add a few more even elements to the array? Currently, only the contiguous range in the beginning matches, which is a bit of a special case. Ideally, the matching elements should be more dispersed.

116

I'd suggest making this array as large as in and relying on the return value to make sure only two elements are copied. Otherwise, it's not clear if the implementation would stop at two elements if the output array was larger.

163

Check the range version as well?

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_n.pass.cpp
99

Question: should this algorithm also check the order in which the elements are copied? (same with copy_if.pass.cpp)

This revision now requires changes to proceed.Apr 4 2022, 6:10 PM
philnik updated this revision to Diff 420412.Apr 5 2022, 1:53 AM
philnik marked 31 inline comments as done.
  • Address comments
libcxx/include/__algorithm/copy.h
40–80

No, I missed something. I thought the old version said is_same<remove_const<_Tp>::type, _Tp>, which is obviously just is_const.

52

I can't use std::memmove in a constant expression and using __builtin_memmove costs a lot less steps (https://godbolt.org/z/nqb75KGa3).

57

AFAIK the general style is to use the earliest constexpr possible for internal stuff.

85

What would you expect to change between it being wrapped and not? It's not like we can optimize that in any way.

89

I didn't know std::make_pair existed. Thanks!

96

This patch exists in part because we want to avoid this exact extension, so no - this should definitely not be moved. See D122074.

libcxx/include/__algorithm/copy_backward.h
56

What change are you asking for exactly? The change from std::memmove to __builtin_memmove?

libcxx/include/__algorithm/ranges_copy_if.h
44

Why would it? It's a really simple algorithm and has no pitfalls AFAIK.

50

The problem is that your version isn't correct. _Sent doesn't have to be the same type as _InIter.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
51

CopyOnce and OnlyBackwardsCopyable aren't trivial.

155

I thought of it as 'the next copyable value'. I'd rather keep it as-is.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_if.pass.cpp
116

I'd argue that it should be exact. std::ranges::copy_if can't know the size of the range it gets passed, and if it would try to write to more elements than are available this will error during constant evaluation. i.e. an implementation could *(out + 1) = *in and you suggestion wouldn't catch that, while making the array wit the exact size would.

151

I'll do that as soon as you land D122072.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_n.pass.cpp
99

for copy_if and copy_n it isn't specified in which order the elements are copied.

philnik updated this revision to Diff 420450.Apr 5 2022, 4:27 AM
  • Remove std::make_reverse_iterator again
libcxx/include/__algorithm/copy_backward.h
29

This isn't available in C++03 and C++11.

var-const requested changes to this revision.Apr 5 2022, 4:57 PM
var-const added inline comments.
libcxx/include/__algorithm/copy.h
45

Sorry about nitpicking, but reading the comment, I think it would be better phrased as a TODO (something like Remove this workaround once GCC supports using __builtin_memmove in constexpr contexts).

libcxx/include/__algorithm/ranges_copy_if.h
44

I don't disagree -- I'm just wondering because it's inconsistent with what ranges::copy does, which is to delegate.

libcxx/include/algorithm
59–60

Hmm, looks accidentally deleted?

242–243

Looks accidentally deleted?

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
51

Yes, but those tests are focused on checking something else. I'd prefer to have a dedicated test for this, even if it's somewhat redundant with the other tests.

This revision now requires changes to proceed.Apr 5 2022, 4:57 PM
philnik marked 5 inline comments as done.Apr 6 2022, 12:49 AM
philnik added inline comments.
libcxx/include/__algorithm/ranges_copy_if.h
44

Yes, because std::copy does a few optimizations and isn't just a simple loop.

libcxx/include/algorithm
59–60

Looks like it, but has nothing to do with this PR. I'll fix it.

242–243

I'll upload a fix.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
51

What exactly do you want to check just with a non-trivially copyable type? If we do nothing inside the copy constructor/assignment operator there is nothing to check. The implementation could just as well memcpy the whole thing.

philnik updated this revision to Diff 420728.Apr 6 2022, 12:49 AM
philnik marked 3 inline comments as done.
  • Address comments; try to fix CI
philnik updated this revision to Diff 420739.Apr 6 2022, 1:37 AM
  • Try to fix CI
philnik updated this revision to Diff 420762.Apr 6 2022, 2:59 AM
  • Try again
philnik updated this revision to Diff 420767.Apr 6 2022, 3:33 AM
  • This should fix the CI
Mordante added inline comments.Apr 6 2022, 9:52 AM
libcxx/include/__algorithm/copy.h
47

Do you know whether this is available in GCC-12?

85

The cpp20 output iterator isn't copy constructible. But std::basic_string<CharT>::iterator can still be unwrapped. So I wondered whether we want an overload for that case. Something like

template <class _InIter, class _Sent, class _OutIter,
           __enable_if_t<is_copy_constructible<_InIter>::value
                      && is_copy_constructible<_Sent>::value> >
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
  pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
  auto __ret = std::__copy_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::move__result));
  return std::make_pair(std::__rewrap_iter(__first, __ret.first), _ret.second);
}
libcxx/include/__algorithm/copy_backward.h
56

No the removal of this overload. Does that affect the generated code or not.

libcxx/include/__algorithm/ranges_copy_if.h
50

I trusted the wording of the Standard, but it seems that's wrong ;-)
http://eel.is/c++draft/alg.copy#18.2

{last, result + N} for the overloads in namespace ranges.

Do you want to file an LWG issue?

var-const accepted this revision as: var-const.EditedApr 7 2022, 4:49 PM

LGTM once the comment about a missing test case is addressed. Thanks a lot for working on this!

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
51

Right, this is one thing to check -- that the implementation doesn't try to memcpy non-trivial types, for example. But really, all I want to check is that the result is correct, not for any particular kind of problem because too many are possible to consider. Just the fact that it would produce the correct result without crashing is a valuable thing to test, even if it appears trivial. Furthermore, tests are written for the future as well. Even if an algorithm is "obviously" trivial and seemingly cannot be incorrect now, it could change in the future.

philnik updated this revision to Diff 421773.Apr 10 2022, 1:27 AM
philnik marked 3 inline comments as done.
  • Rebased
  • Address comments
philnik added inline comments.Apr 10 2022, 1:28 AM
libcxx/include/__algorithm/copy.h
47

It's not available in GCC trunk.

85

I think the unwrapping is mostly so that we can do a memmove if we have only raw pointers. I don't think that the unwrapping of only part of the iterators makes any difference. The compiler should still be able to see through the wrapper and optimize it away.

libcxx/include/__algorithm/copy_backward.h
56

The codegen is a bit worse, but I doubt it would even be measurable. It's two instructions more. https://godbolt.org/z/Pb7YbnsK3

libcxx/include/__algorithm/ranges_copy_if.h
50

I'm not sure if this is an oversight or if this is expected. Most ranges algorithms return last according to the standard, while in practice they have to return first + N. It's the same with N itself. The standard says last - first, while in practice it would have to be std::distance(first, last).

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
51

I don't disagree that it's a valuable test. My problem is that the test you propose is a strict subset of what // check that the range is copied backwards tests IIUC. I don't think the test adds any coverage.

Mordante requested changes to this revision.Apr 13 2022, 10:19 AM

Something went wrong it seems you accidentally replaced this patch with the contents of D120637.

This revision now requires changes to proceed.Apr 13 2022, 10:19 AM
Mordante accepted this revision.Apr 14 2022, 11:01 AM

LGTM!

libcxx/include/__algorithm/copy_backward.h
29

What I've done in the past for similar cases is add __make_reverse_iterator and let make_reverse_iterator call that function. Just something to keep in mind, no need to change it now.

libcxx/include/__algorithm/ranges_copy_n.h
56

How do you feel about moving these iterators for consistency?

This revision is now accepted and ready to land.Apr 14 2022, 11:01 AM
This revision was landed with ongoing or failed builds.Apr 15 2022, 4:44 AM
This revision was automatically updated to reflect the committed changes.