This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement ranges::transform
ClosedPublic

Authored by philnik on Mar 21 2022, 1:08 PM.

Details

Diff Detail

Event Timeline

philnik created this revision.Mar 21 2022, 1:08 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 21 2022, 1:08 PM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Mar 21 2022, 1:08 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 21 2022, 1:08 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik updated this revision to Diff 417069.Mar 21 2022, 1:15 PM
  • Add synopsis

Thanks a lot for working on this!

libcxx/include/__algorithm/ranges_transform.h
39

For consistency I think using _Op like in the unary type would be better.

45

Is there a reason why the naming of the types and variables differs from the other ranges algorithms?
For example ranges_find.h uses

template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, class _Proj = identity>
  requires indirect_binary_predicate<ranges::equal_to, projected<_Ip, _Proj>, const _Tp*>
_LIBCPP_HIDE_FROM_ABI constexpr
_Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const {
  auto __pred = [&](auto&& __e) { return std::forward<decltype(__e)>(__e) == __value; };
  return ranges::__find_if_impl(std::move(__first), std::move(__last), __pred, __proj);
}

I think it improves our codebase when we keep these names consistent.
I'm also not to fond of _InputIterator and _OutputIterator, they are used in the non-range algorithms and there they use the LegacyIterators. So I like that the range based algorithms use a different naming scheme,

libcxx/include/algorithm
99

unary_transform_result and binary_transform_result are also part of the synopsis.

libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/ranges.transform.pass.cpp
112

I find this test with the extra whitespace more readable, could you adjust the other test cases in this file accordingly?

259
297

I would like a test where an unrelated type is written, for example using a unary lambda like
[](int i) { return '0' + i } which returns a char instead of an int.

302

I think it would be good to also test cpp17_input_iterator, same for test_iterators_in1_in2.

321

We should add a test using the cpp20_output_iterator as proposed in D122072. We want to make sure a non-copyable iterator works.

331

Should these test also use decltype(auto)?

417
var-const requested changes to this revision.Mar 23 2022, 7:39 PM
var-const added inline comments.
libcxx/docs/Status/RangesAlgorithms.csv
47

Can you add a link to this patch here?

libcxx/include/__algorithm/ranges_transform.h
45

FWIW, I'm mildly in favor of using longer names (though I can see the argument for terser names given how verbose the template parameters are in these functions). I think range algorithms (both committed and in flight) aren't currently consistent in this regard.

libcxx/include/algorithm
104

Nit: s/first1/first/ (same for last1).

110

Nit: can you add blank lines at least between the unary and binary versions of transform, and perhaps between all of them? As it stands, I found it a little hard to find where one functions ends and another one starts due to how verbose the template arguments are.

libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/ranges.transform.pass.cpp
60

To make the SFINAE test exhaustive, I think it also needs to check the weakly_incrementable, copy_constructible, indirectly_writeable, etc. constraints.

79–85

Optional: do you think it would be worthwhile to try reducing duplication here? Perhaps something like:

template <class In1, class Out>
struct Result {
  std::ranges::in_out_result<In1, Out> ret;
  Out* out = nullptr;
};

// ...

int a[] = {1, 2, 3, 4, 5};
int b1[5], b2[5];

std::same_as<std::ranges::in_out_result<In1, Out>> decltype(auto) ret_iter =
    std::ranges::transform(In1(a), Sent1(In1(a + 5)), Out(b1), [](int i) { return i * 2; });
auto range = std::ranges::subrange(In1(a), Sent1(In1(a + 5)));
std::same_as<std::ranges::in_out_result<In1, Out>> decltype(auto) ret =
    std::ranges::transform(range, Out(b2), [](int i) { return i * 2; });

for (const auto& result : {Result{ret_iter, b1}, Result{ret_range, b2}}) {
  assert((std::to_array(result.out) == std::array{2, 4, 6, 8, 10}));
  assert(base(result.ret.in) == a + 5);
  assert(base(result.ret.out) == b + 5);
}
112

+1.

182

Perhaps also check the case when both ranges are empty for binary?

210–213

Nit: one extra blank line.

332

Nit: I think continued lines should be indented 4 columns.

416

Please add return 0.

This revision now requires changes to proceed.Mar 23 2022, 7:39 PM
Mordante added inline comments.Mar 24 2022, 11:46 AM
libcxx/include/__algorithm/ranges_transform.h
45

I'm not against longer names in general, but when I read _InputIterator I expect a LegacyIterator in the <algorithm> header. I also would like consistent naming, which can be achieved in two ways. Use the old names in new code or change the old code to use new names.There's a thread on Discord so I think it's easier to discuss it there.

philnik updated this revision to Diff 418474.Mar 27 2022, 4:27 PM
philnik marked 19 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_transform.h
39

I use _O1 for consistency with in_in_out_result here.

45

This has been discussed on discord.

libcxx/include/algorithm
104

This is consistent with the standard synopsis.

libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/ranges.transform.pass.cpp
79–85

This looks way more complicated to make it a bit shorter to me.

210–213

I think it looks nicer without a blank line here.

331

The decltype(auto) was specifically because ranges::min and friends return const T&. But I can also add a decltype here if you want.

ldionne requested changes to this revision.Mar 29 2022, 8:05 AM

I think this is good to go after my suggestions. I'll want to see this again just to double check, but there shouldn't be anything else to change. Thanks!

libcxx/include/__algorithm/ranges_transform.h
36–40

Can you please make sure you have tests that check that we define those two names in std::ranges specifically, i.e. not as part of testing ranges::transform() itself? This also applies to other reviews like minmax_element.

50

Can you make __unary and __binary private?

libcxx/include/algorithm
100–104

Those shouldn't use uglified names.

libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/ranges.transform.pass.cpp
215

You could consider checking the return type only once for each relevant call, and then use auto elsewhere. That would simplify these tests quite a bit.

394–398

This shouldn't be commented out (ditto below).

409

Would it be possible to move these tests into the test_iterators function? LMK if compile-times explode in a bad way.

445

I don't think you mean "predicate" here, maybe just "function" is what you mean.

493
This revision now requires changes to proceed.Mar 29 2022, 8:05 AM
ldionne added inline comments.Mar 29 2022, 8:07 AM
libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/ranges.transform.pass.cpp
51

You could fix the macOS CI issue (which is really an AppleClang-13 issue) by doing something like std::ranges::transform(r, out, std::identity()) instead.

philnik updated this revision to Diff 419038.Mar 29 2022, 7:37 PM
philnik marked 9 inline comments as done.
  • Address comments
libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/ranges.transform.pass.cpp
409

The test takes 40s to compile and run on my system now. The tests that aren't in test_iterators can't be moved there easily, because they don't use int.

var-const accepted this revision.Apr 1 2022, 9:29 PM
var-const added inline comments.
libcxx/include/algorithm
104

This is consistent with the standard synopsis.

Interesting. I presume it's a typo in the Standard, but sure, let's be consistent.

var-const requested changes to this revision.Apr 1 2022, 9:30 PM
This revision now requires changes to proceed.Apr 1 2022, 9:30 PM
var-const accepted this revision as: var-const.Apr 1 2022, 9:30 PM

LGTM, but leaving the final approval for @ldionne who had some comments.

ldionne accepted this revision.Apr 4 2022, 7:17 AM
ldionne added inline comments.
libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/ranges.transform.pass.cpp
455–461

Can you please add a comment like: static_asserting here to avoid hitting the constexpr evaluation step limit.

This revision is now accepted and ready to land.Apr 4 2022, 7:17 AM
This revision was landed with ongoing or failed builds.Apr 5 2022, 2:06 AM
This revision was automatically updated to reflect the committed changes.
philnik marked an inline comment as done.
Herald added a project: Restricted Project. · View Herald TranscriptApr 5 2022, 2:06 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
bkramer added a subscriber: bkramer.Apr 5 2022, 3:37 AM
bkramer added inline comments.
clang/lib/ExtractAPI/Serialization/ranges_transform.module.verify.cpp
1–15

This file doesn't belong in clang/lib. Deleted it in 302fe7b3c40f7b949f3bebb74997bef9bf74d59f.

philnik marked an inline comment as done.Apr 5 2022, 3:51 AM
philnik added inline comments.
clang/lib/ExtractAPI/Serialization/ranges_transform.module.verify.cpp
1–15

Sorry, this must be a weird merge conflict. Thanks for removing it!