Page MenuHomePhabricator

[libc++] add zip_view and views::zip for C++23
ClosedPublic

Authored by huixie90 on Mar 31 2022, 6:14 AM.

Details

Summary
  • add zip_view and views::zip for C++23
  • added unit tests
  • implemented section 5.6 (zip) in P2321R2

I used clang-format to format the files but they look nothing like the rest of the code base. Manually indenting each line to match the styles sounds like an impossible task. Is there any clang-format file which can format it reasonable similar to the rest of the code base so that I can manually format the rest lines that look weird?

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
var-const added inline comments.Apr 21 2022, 4:54 PM
libcxx/include/__ranges/zip_view.h
241

Is the following section implemented and tested?

If the invocation of any non-const member function of `iterator` exits via an exception, the iterator acquires a singular value.

(http://eel.is/c++draft/range.zip#iterator-3)

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/arithmetic.pass.cpp
98

Nit: s/each/each of the/.

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/compare.pass.cpp
13

Please add the constraints to the synopsis.

22

Also check for the presence of operator==?

24

Same nit as another file: it's a little inconsistent that this class name is in snake_case.

24

Nit: s/smaller/less/ (throughout the file). I think less is more commonly used in the arithmetic context.

34

Question: is defining operator[] necessary?

70

Is this declaration necessary? It seems to go against the purpose of the test, which IIUC verifies that having just operator== is sufficient.

75

Question: do these operators have to be declared?

100

Ultranit: s/SubRange/Subrange/ (the Standard considers it a single word).

111

These checks are verbose and, as far as I can see, same across the test cases -- can you move them to a helper function?

187

Please also check that operator== is unavailable, and ideally all other operators.

This revision now requires changes to proceed.Apr 21 2022, 4:54 PM
huixie90 updated this revision to Diff 424438.Apr 22 2022, 4:37 AM
huixie90 marked 48 inline comments as done.

address review comments

libcxx/include/__ranges/zip_view.h
85

I guess I'd have to spell this type in the return statement (currently it is just return {.....}).

241

AFAIK, doing anything with iterator of singular value would result in undefined behaviour (except for very few operations). one question is can we take advantage of the undefined behaviour and not do anything here?

One thing we could do is to value initialise all the underlying iterators. but what if underlying iterators are not default constructible?

287

it is done by clang-format. happy to format manually.

but imo it would be great to come up with a clang-format file that everyone is sort of OK-ish with it. It would save everyone's time

395

isn't this just delegating to the above? (thus same as above?)

430

I think so. In the standard, it basically says all the iter_swap(std::get<i>(l.current_), std::get<i>(r.current_) are noexcept. std::get itself is always noexcept, so the standard basically equivalent to all the ranges::iter_swap are noexcept.

Here the implementation is checking the same thing

514

good catch. added unit test to lock down this. for some reason, I relied on the user defined CTAD (which has the all_t thing, but forgot about the implicit CTAD from copy constructors which don't have all_t)

libcxx/test/std/ranges/range.adaptors/range.zip/begin.pass.cpp
14

I don't think it is possible.
To make non-const overload not exist, all Views have to model simple-view. simple-view implies range<const View>. so the const overload must exist in that case.

libcxx/test/std/ranges/range.adaptors/range.zip/cpo.pass.cpp
13

views::zip is not an "adaptor". It is only a CPO. So it doesn't support pipe operation.
Therefore the test is not named as adaptor.pass.cpp but cpo.pass.cpp

The name views​::​zip denotes a customization point object ([customization.point.object]).

libcxx/test/std/ranges/range.adaptors/range.zip/ctor.default.pass.cpp
42

I had the same puzzle before I implemented this and asked sg9. Why there is no "requires (default_initializable<iterator_t<maybe-const<const, views>>> && ...)

The answer is that it is implicitly required by the tuple's constructor. if any of the iterators are not default constructible, zip_iterator's =default would be implicitly deleted.

libcxx/test/std/ranges/range.adaptors/range.zip/ctor.views.pass.cpp
28

My original thought was convertible_to doesn't work for multiple arguments but zip_view constructor can take multiple arguments. so i implemented a multi-args version.
But then I forgot to test the multi-args case.

40

I don't think this is UB. AFAIK, this is how single_view is implemented

https://eel.is/c++draft/range.single#view-5

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/compare.pass.cpp
70

This particular test point was suggested by @philnik . His point is that testing "zip_iterator is never calling underlying iterator's >, >=, <=, !=
because the spec says zip_iterator's >= is calling zip_iterator's (not less_than). So tested this way: declare all the operations >, >=, <= etc to make it satisfy random_access iterator concept. but not define them. if the zip_iterator's >,>=, <=, etc isn't implemented as the way standard defined but calling underlying iterator's >,>=,<=, we will get a linker error for runtime tests and non-constant expression for compile time test.

added comments to explain this

75

This particular test point was suggested by @philnik . His point is that testing "zip_iterator is never calling underlying iterator's >, >=, <=, !=
because the spec says zip_iterator's >= is calling zip_iterator's (not less_than). So tested this way: declare all the operations >, >=, <= etc to make it satisfy random_access iterator concept. but not define them. if the zip_iterator's >,>=, <=, etc isn't implemented as the way standard defined but calling underlying iterator's >,>=,<=, we will get a linker error for runtime tests and non-constant expression for compile time test

added comments to explain this

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/ctor.default.pass.cpp
48

this comes implicitly from the tuple's constructor

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/decrement.pass.cpp
64

In this case, zip_view is not a common_range, end returns a sentinel which can't be decremented

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/iter_move.pass.cpp
46

happy to add the extra test.
Just FYI, this is somehow implicitly tested by the #include order. we include <ranges> before the "types.h". If it were not using ADL, it couldn't find our test iterator's iter_move because normal lookup requires the declaration to be seen first.

huixie90 updated this revision to Diff 424463.Apr 22 2022, 6:49 AM
huixie90 marked 7 inline comments as done.

addressed comments

var-const requested changes to this revision.Apr 22 2022, 10:01 PM

Almost LGTM, just a few nits.

libcxx/include/__ranges/zip_view.h
85

I mean, could you rely on CTAD? To be clear, it's just a question -- perhaps CTAD won't work here.

241

Perhaps we should test that the iterator is reassignable/destroyable, but perhaps it's overkill. Let's check with Louis @ldionne.

287

I fully agree, being able to use clang-format would be great (though note that it's not fully straightforward on our code base).

395

It's a little easier to compare when things are close to the Standard text (unless, of course, there's a reason to diverge), but it's a really small thing -- we can keep as is.

428

Very optional: this comment can fit in one line.

430

Sounds reasonable, but I'd ask Louis @ldionne to double-check just in case.

libcxx/test/std/ranges/range.adaptors/range.zip/begin.pass.cpp
52

A word seems to be missing -- "should _be_ at the begin position"?

libcxx/test/std/ranges/range.adaptors/range.zip/cpo.pass.cpp
13

Ah, makes sense, never mind.

libcxx/test/std/ranges/range.adaptors/range.zip/ctor.default.pass.cpp
42

Because it's not obvious, can you please add this as a comment?

libcxx/test/std/ranges/range.adaptors/range.zip/ctor.views.pass.cpp
28

Ah, right (you might also want to check that the default constructor is explicit, though it starts going into the overkill territory).

40

Thanks for pointing it out -- it made me find this post that quotes the relevant part of the Standard (updated to the current draft):

When an expression J that has integral type is added to... an expression P of pointer type...

<...>

(4.2) Otherwise, if P points to an array element i of an array object x with n elements ([dcl.array]),70 the expressions P + J and J + P... point to the (possibly-hypothetical) array element i + j of x if 0 ≤ i+j ≤ n...

<...>

  1. As specified in [basic.compound], an object that is not an array element is considered to belong to a single-element array for this purpose and a pointer past the last element of an array of n elements is considered to be equivalent to a pointer to a hypothetical array element n for this purpose.
67

(By the way, ignoring optional comments is fine -- that's why they're optional, after all -- but if you decide not to implement an optional suggestion, can you please add a comment to that effect? This would help me understand whether this is something you plan to come back to later or something you decided to push back on. Once again, pushing back is fine -- I just want to make sure I understand the state of the patch, i.e. whether all comments are addressed one way or the other)

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/arithmetic.pass.cpp
20

Nit: I think the meaning would be a little more obvious if s/which/which instead/. (I know the current text is my suggestion)

102

Nit: with the new sentence structure, I think this should be sentinels.

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/compare.pass.cpp
36

Some nits:

  • s/as/in;
  • consider in the way defined by the standard;
  • I think there should be no comma between defined and but;
  • consider s/but/but instead/;
  • (ultranit) please add a full stop at the end of the sentence.
130

Nit: s/Opeartors/Operators/.

239

Should it also call inequalityOperatorsDoNotExistTest?

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/ctor.other.pass.cpp
48

Is it possible to also add a static_assert to show that the convertible_­to constraint is not satisfied in this case? (Only if it's straightforward, it's basically to "test the test" and to make it a little more obvious what exactly it's testing)

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/iter_move.pass.cpp
46

Thanks for adding the test! Relying implicitly on the include order would be too subtle, IMO.

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/member_types.compile.pass.cpp
70

Nit: s/shoud/should/.

70

Nit: probably s/ranges/views/? That's the name of the template argument / constructor argument.

147

Nit: s/multiple/of multiple (here and below).

libcxx/test/std/ranges/range.adaptors/range.zip/sentinel/eq.pass.cpp
132

Thanks for adding all the comments! Much easier to skim through now.

libcxx/test/std/ranges/range.adaptors/range.zip/sentinel/minus.pass.cpp
160

Optional nit: s/minus/subtract/.

This revision now requires changes to proceed.Apr 22 2022, 10:01 PM
huixie90 updated this revision to Diff 424712.Apr 23 2022, 4:15 AM
huixie90 marked 23 inline comments as done.

address review comments

libcxx/include/__ranges/zip_view.h
85

Originally I relied on tuple's CTAD, but that crashed gcc 11.2
https://discord.com/channels/636084430946959380/636732894974312448/960574541254496337

Later I tried make_tuple. There are two issues.

  1. It is inconsistent with the rest of the code, where in other places, two elements thing are stored in a pair. Although this function is internal only, but still... consistency is good.
  1. CTAD/make_tuple decays. In case the function returns references, I would get tuple of values instead of tuple of references. Again, this is not an issue for now, because the usages of this helper function only return values (booleans and integers at the moment). But again, if one day this is used with references, it would become a problem silently.
241

I asked around and people seem to agree on that that paragraph is to empower implementations not to do anything by given less guarantees that things should work. But let's wait until Louis is back

287

cool. I will hand format for now

libcxx/test/std/ranges/range.adaptors/range.zip/ctor.views.pass.cpp
28

The default constructor is not explicit and it is tested already

40

thanks for the explanation

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/compare.pass.cpp
34

yes. this is one of the requirement of random_access_iterator

libcxx/test/std/ranges/range.adaptors/range.zip/iterator/ctor.other.pass.cpp
48

yes good idea. added static_assert right after the declaration of ConstIterIncompatibleView

var-const accepted this revision as: var-const.Apr 23 2022, 2:05 PM

LGTM -- thanks a lot for working on this huge patch! I'll leave the final approval for @ldionne.

libcxx/include/__ranges/zip_view.h
85

Oh, interesting, thanks for explaining. It's certainly not worth it to work around compiler bugs and such, the current state is fine.

libcxx/test/std/ranges/range.adaptors/range.zip/ctor.default.pass.cpp
40

Ultranit: capitalize.

ldionne accepted this revision.Apr 24 2022, 9:15 AM

I looked around and it seemed like this had a thorough review already. I just replied to the comments where I was @'ed.

Thanks to everyone involved for the work and especially @huixie90 for authoring the patch. This LGTM with the last few missing comments addressed.

libcxx/include/__ranges/zip_view.h
241

Sorry, I feel I'm missing some context, but it seems to me that a singular iterator should still be destroyable and assignable-to (unless there's something in the spec that contradicts that, but I don't think there is). If that's correct, then we should make sure that works and test it. Please LMK if what I'm saying doesn't make sense, since I'm commenting out of context.

430

Yeah, this sounds reasonable to me.

This revision is now accepted and ready to land.Apr 24 2022, 9:15 AM
huixie90 updated this revision to Diff 424792.Apr 24 2022, 11:10 AM
huixie90 marked 8 inline comments as done.

added unit test for singular case

huixie90 updated this revision to Diff 424819.Apr 24 2022, 11:04 PM

fix CI failure

I don't have access to push the commits.
Name: Hui Xie
Email: hui.xie1990@gmail.com

This revision was landed with ongoing or failed builds.Apr 25 2022, 3:22 AM
This revision was automatically updated to reflect the committed changes.