This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement P2443R1: `views::chunk_by`
ClosedPublic

Authored by JMazurkiewicz on Feb 24 2023, 4:31 PM.

Diff Detail

Event Timeline

JMazurkiewicz created this revision.Feb 24 2023, 4:31 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 24 2023, 4:31 PM
Herald added a subscriber: arichardson. · View Herald Transcript
JMazurkiewicz requested review of this revision.Feb 24 2023, 4:31 PM
JMazurkiewicz set the repository for this revision to rG LLVM Github Monorepo.Feb 24 2023, 5:09 PM
Herald added 1 blocking reviewer(s): Restricted Project. · View Herald TranscriptFeb 24 2023, 5:09 PM

Try to fix CI.

JMazurkiewicz set the repository for this revision to rG LLVM Github Monorepo.

Fix CI (add missing includes), and update release notes.

Improve test coverage.
I haven't fixed the problem with transitive includes yet - does anyone know what might be the reason of this failure? (I've marked problematic includes with FIXME transitive include comment)

Fix formatting.

fsb4000 added a subscriber: fsb4000.EditedMar 3 2023, 11:09 PM

I think you should add ranges new beetween these two lines: https://github.com/llvm/llvm-project/blob/fac4c476b97b9f2a9dace059f084696d856c033b/libcxx/test/libcxx/transitive_includes/cxx03.csv#L647-L648 and https://github.com/llvm/llvm-project/blob/main/libcxx/test/libcxx/transitive_includes/cxx11.csv#L648-L649

In theory these files should be updated when you run ninja -C build libcxx-generate-files but that command doesn't work on Windows...

https://github.com/llvm/llvm-project/issues/57458

Update transitive includes manually.

Ok, I think current CI failures are not your fault.

Look at the Scheduled build: https://buildkite.com/llvm-project/libcxx-ci/builds/20489

It also failed.

I think I fixed the CI when I revert the commit: https://github.com/llvm/llvm-project/commit/24416d22bb284cf24335ee7aa63131e5de56a1bb

And I restarted CI, so I hope it should pass now.

The tests passed and I added more reviewers to this patch.

Thanks for working on this!
I haven't reviewed the tests yet, but I wanted to give you some feedback.

libcxx/include/__ranges/chunk_by_view.h
30

Can you explain what issue you have with these transitive includes?

78

please search for similar in the asserts and fix them too. Note users of libc++ tend not to read the Standard, so it's better to use the name used in libc++ than the name in the Standard.

81

Now the object can be moved on line 85.

86

Is there a reason why this is written in a different fashion as in the Standard? This makes it harder to verify its correctness.

110

Without const this can be moved. Note that the libc++ code uses const very sparingly.

132

Is there a reason to make the exposition only type public?

157

Since you used _LIBCPP_ASSERT for most preconditions, it would be great to do the same here.

libcxx/include/ranges
315

Please align all since comments

libcxx/test/libcxx/ranges/range.adaptors/range.chunk.by/assert.begin.pass.cpp
14–18

Typically we stat the file with this part and then the header under test.

44

Can you also test the other asserts you added?

libcxx/test/libcxx/transitive_includes/cxx11.csv
670 ↗(On Diff #507328)

Did you remove headers or not?

libcxx/test/std/ranges/range.adaptors/range.chunk.by/adaptor.pass.cpp
11

Please add the header name here too.

JMazurkiewicz marked 8 inline comments as done.
  • Address some of @Mordante's comments
  • Rename iterator directory to range.chunk.by.iter

TODO: transitive includes, verify more assertions

JMazurkiewicz added inline comments.Apr 18 2023, 5:35 AM
libcxx/include/__ranges/chunk_by_view.h
86

Is there a reason why this is written in a different fashion as in the Standard?

This is based on reference implementation from P2443R1 (https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2443r1.html#pnum_16); I've only replaced not_fn(bind(ref(*pred_), _2, _1)) with lambda expression.

132

No, I think that I wanted to test something here.

  • Test all added assertions,
  • Rebase,
  • Fix CI?

TODO: transitive includes

JMazurkiewicz marked an inline comment as done.Apr 25 2023, 7:42 AM
JMazurkiewicz set the repository for this revision to rG LLVM Github Monorepo.Apr 25 2023, 12:07 PM

Rebase; try to fix CI.

Rebase; fix CI.

var-const requested changes to this revision.Jun 1 2023, 10:45 PM

Thank you for working on this! Sorry I'm slow with the review.

libcxx/include/__ranges/chunk_by_view.h
58

Question: can __base_ actually have be empty?

59

Can you please add a TODO to update this to __movable_box once D151629 lands?

63

Is it necessary to explicitly call the default constructor of __non_propagating_cache here?

69

Please add a blank line after this line.

78

Nit: I'd s/with begin iterator/on a begin iterator/.

80

Please add a blank line after this line.

109

Nit: can you add a blank line after this line to separate error checking from the main flow of the function?

151

Nit: s/past end/a past-the-end/.

var-const added inline comments.Jun 1 2023, 10:45 PM
libcxx/include/__ranges/chunk_by_view.h
78

Hmm, I don't feel too strongly, but I actually wrote a comment asking to do the opposite before I read this thread. I think that ideally we'd assert in public functions (so that the name difference doesn't apply), but if the Standard wants us to assert in private functions, I'd go with the standard name (which is the name of the function we're implementing) rather than our internal name (for the same reason that I would use non-uglified template argument names, etc.). Do we have any precedent for this?

109

Hmm, it's interesting that the standard allows creating an unusable chunk_by_view -- just curious, do you know if there's a use case for that?

109

I know it's in the standard, but it seems like this check is redundant with the one in find-next, or am I missing something?

204

Would any tests fail if we removed decay_t here?

libcxx/test/libcxx/ranges/range.adaptors/range.chunk.by/assert.find-next.pass.cpp
26 ↗(On Diff #520676)

Question: is this the only (or easiest) way to get an invalid predicate? Would a default-constructed view work here, perhaps?

libcxx/test/libcxx/transitive_includes/cxx11.csv
681 ↗(On Diff #520676)

Question: why is this include added?

libcxx/test/std/ranges/range.adaptors/range.chunk.by/adaptor.pass.cpp
60

Question: is it possible to simply compare for equality, or do we necessarily have to use mismatch?

61

Nit: we normally don't use "shallow" const much, and in this small scope in particular it seems unnecessary.

91

Ultranit: unclosed backtick.

187

Nit: please add newlines (here and in other similar places):

{
  [[maybe_unused]] auto partial = std::views::chunk_by(3.14159);
}
libcxx/test/std/ranges/range.adaptors/range.chunk.by/begin.pass.cpp
91

Ultranit: s/a/an/. Consider rephrasing the comment to something like over a longer range, though (the exact number isn't really important here, unlike in the previous two cases).

106

Optional: I don't think we need to assert this since we're testing begin, not the constructor.

147

Can you add a brief comment to explain why the number is 4?

152

I would inline these functions. Normally we use named functions in tests when they are reused.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/constraints.compile.pass.cpp
32

Ultranit: s/an/a/.

35

It looks like types from almost_satisfies_types.h would be helpful here.

59

Nit: can these be more descriptive names?

91

Nit: can you add blank lines after opening and before closing a namespace?

libcxx/test/std/ranges/range.adaptors/range.chunk.by/ctor.default.pass.cpp
76

Optional: I think it would be a little easier to compare the sizes of the inputs, it can simplify the loop as well if you could rely on them being the same size.

81

Please add brief comments to each test case.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/pred.pass.cpp
34

Question: can a default-constructed chunk_by_view contain a valid predicate?

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/compare.pass.cpp
92 ↗(On Diff #520676)

If I'm reading this correctly, the comments should be reversed -- test<Iterator> tests with a sentinel, and test<Iterator, Iterator> tests with a pair of iterators.

100 ↗(On Diff #520676)

You can use types::for_each to reduce boilerplate here.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/ctor.default.pass.cpp
25 ↗(On Diff #520676)

Note: honestly, I think it's a little overkill (to be clear, I'm not requesting to change it), the scope of the test is very small and I think a simple boolean with a comment would have sufficed (it would also avoid having to call to_underlying).

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/decrement.pass.cpp
72 ↗(On Diff #520676)

Nit: s/a two chunks/two chunks/.

139 ↗(On Diff #520676)

Ultranit: s/predicate/a predicate/.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/deref.pass.cpp
37 ↗(On Diff #520676)

Nit: if the intention is to check the return type, perhaps use std::same_as for the iterator?

39 ↗(On Diff #520676)

Can we check the exact contents of each chunk instead?

44 ↗(On Diff #520676)

This actually uses a sentinel, right? (and vice versa below)

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/increment.pass.cpp
47 ↗(On Diff #520676)

Ultranit: s/an/the/.

109 ↗(On Diff #520676)

Question: can you elaborate?

112 ↗(On Diff #520676)

Nit: this formatting looks weird, is it produced by clang-format?

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/types.compile.pass.cpp
43 ↗(On Diff #520676)

Using types::for_each would help reduce the boilerplate in this file (here and with the static assertions below too probably).

libcxx/test/std/ranges/range.adaptors/range.chunk.by/types.h
46

Question: why is this necessary? (Wouldn't the generated deduction guide do the same thing?)

This revision now requires changes to proceed.Jun 1 2023, 10:45 PM
JMazurkiewicz marked 39 inline comments as done.
JMazurkiewicz set the repository for this revision to rG LLVM Github Monorepo.
  • Rebase,
  • Address almost all comments from @var-const (thank you for the review!),
  • Enable std::ranges::chunk_by_view and std::views::chunk_by in std.cppm.

+comments

libcxx/include/__ranges/chunk_by_view.h
58

Yes, when it is for example ranges::empty_view.

63

It's not, I've removed it.

109

I know it's in the standard, but it seems like this check is redundant with the one in find-next, or am I missing something?

109

I know it's in the standard, but it seems like this check is redundant with the one in find-next, or am I missing something?

109

Hmm, it's interesting that the standard allows creating an unusable chunk_by_view -- just curious, do you know if there's a use case for that?

I have no idea.

I know it's in the standard, but it seems like this check is redundant with the one in find-next, or am I missing something?

This check is not redundant. I've explained why in comment in assert.find-next.pass.cpp file.

204

No... until now. I've added extra test coverage in adaptor.pass.cpp (marked with Test that one can call std::views::chunk_by with arbitrary stuff (...) comment).

libcxx/test/libcxx/ranges/range.adaptors/range.chunk.by/assert.find-next.pass.cpp
26 ↗(On Diff #520676)

This is the easiest way (I think) to get __find_next to fail. If we used default constructed view here, then begin() would fail instead of __find_next.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/adaptor.pass.cpp
60

Yes, replaced with std::ranges::equal.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/pred.pass.cpp
34

I don't think it is possible - default-constructed __copyable_box (or __movable_box) never contains a value.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/deref.pass.cpp
44 ↗(On Diff #520676)

Yes, I've swapped comments again.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/increment.pass.cpp
109 ↗(On Diff #520676)

All callables can be called like regular function f(), but not all invocables can (we need to use std::invoke for them). This tests checks if we use std::invoke properly or we just use pred() syntax.

I've added comment explaining this here and in decrement.pass.cpp.

112 ↗(On Diff #520676)

Yes, it is produced by clang-format. I'm going to fix it manually.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/range.chunk.by.iter/types.compile.pass.cpp
43 ↗(On Diff #520676)

Done for testValueTypeAndDifferenceType, but I don't think it is possible for static_assertions.

libcxx/test/std/ranges/range.adaptors/range.chunk.by/types.h
46

Yes, it is necessary. Without this deduction guide I get error: 'View' may not intend to support class template argument deduction warning, but since tests use -Werror this ends up as a hard error.

JMazurkiewicz marked an inline comment as not done.
  • Rebase,
  • Fix CI: use __movable_box.
var-const accepted this revision.Jul 17 2023, 5:06 PM

Thanks for working on this! LGTM (with just one comment), and feel free to ping me if you run into any problems when rebasing.

libcxx/test/libcxx/ranges/range.adaptors/range.chunk.by/assert.begin.pass.cpp
14

Quick tip: when you rebase, you can replace D_LIBCPP_ENABLE_ASSERTIONS=1 with // UNSUPPORTED: !libcpp-has-hardened-mode && !libcpp-has-debug-mode.

libcxx/test/libcxx/ranges/range.adaptors/range.chunk.by/assert.find-next.pass.cpp
26 ↗(On Diff #520676)

Thanks for explaining. I think it deserves a comment in the test file.

This revision is now accepted and ready to land.Jul 17 2023, 5:06 PM
  • Rebase,
  • Target LLVM 18,
  • Address more @var-const's comments.

Rebase and fix CI

Rebase, fix CI.

var-const added inline comments.Sep 1 2023, 2:53 PM
libcxx/include/__ranges/chunk_by_view.h
49

Quick question -- why do we need this?

var-const added inline comments.Sep 1 2023, 3:00 PM
libcxx/include/__ranges/chunk_by_view.h
49

Never mind -- it looks like it's to protect against macros like move.

@JMazurkiewicz Please let me know if you need any help to merge this patch.

Regarding the CI failure with reserved names -- I presume this is related to https://reviews.llvm.org/D147356, you might need to add the "push macros / pop macros" dance to ranges_adjacent_find.h and movable_box.h.

JMazurkiewicz updated this revision to Diff 555639.EditedSep 3 2023, 3:58 PM
  • Rebase
  • Defend against move macro
  • Replace _LIBCPP_ASSERT with _LIBCPP_ASSERT_UNCATEGORIZED
  • Add _LIBCPP_PUSH_MACROS; #include <__undef_macros> ... _LIBCPP_POP_MACROS in ranges_adjacent_find.h and movable_box.h
  • Try to fix CI and make this patch ready for the commit :)

Is this patch OK now? @var-const

If so, can you merge it for me? "Jakub Mazurkiewicz <mazkuba3@gmail.com>"

This revision was automatically updated to reflect the committed changes.

Is this patch OK now? @var-const

If so, can you merge it for me? "Jakub Mazurkiewicz <mazkuba3@gmail.com>"

Thank you for the patch! Merged now.

This seems to break the C++20 CI: https://buildkite.com/llvm-project/libcxx-ci/builds/29475#018a6a62-4d93-4db9-bb60-0d011a40552e

Did you folks ensure a green build before merging? I'll try to take a look at what's wrong and fix it.

Did you folks ensure a green build before merging?

Yes, it was green.

Looks like views::chunk_by and ranges::chunk_by_view should be guarded with #if _LIBCPP_STD_VER >= 23 in modules/std/ranges.inc file. Do you want me to publish pull request with fix on Github? @ldionne

Should be fixed by 98d28e947cc332f5bb9878e967ea5d7e414cf785! I reproduced and verified the fix locally.

I think what happened is a race condition with the enablement of C++23 modules in C++20. Basically the CI didn't run this test in C++20 mode when you triggered the CI. No big deal, it should work now.