This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][ranges] Add `counted_iterator`.
ClosedPublic

Authored by zoecarver on Jul 16 2021, 6:20 PM.

Details

Reviewers
cjdb
ldionne
Quuxplusone
Group Reviewers
Restricted Project
Commits
rG8a48e6dda9f7: [libcxx][ranges] Add `counted_iterator`.

Diff Detail

Event Timeline

zoecarver created this revision.Jul 16 2021, 6:20 PM
zoecarver requested review of this revision.Jul 16 2021, 6:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 16 2021, 6:20 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
zoecarver updated this revision to Diff 359509.Jul 16 2021, 6:21 PM

Remove completed todo.

Mordante added inline comments.
libcxx/include/CMakeLists.txt
138

Did you run libcxx/utils/generate_private_header_tests.py?

libcxx/include/__iterator/counted_iterator.h
40

Please add _LIBCPP_TEMPLATE_VIS here and other structs.

74

These two are exposition only private members. Is there a reason why you made them public?

79

Please add _LIBCPP_HIDE_FROM_ABI here and other functions.

205

How do you feel about adding _LIBCPP_ASSERTS to validate the precondtions?

221

Can you add a TODO/FIXME to remind to implement this function?

libcxx/test/std/iterators/predef.iterators/counted.iterator/iter_swap.pass.cpp
17

I miss tests to validate the proper noexcept status.

zoecarver marked 4 inline comments as done.Jul 22 2021, 10:57 AM
zoecarver added inline comments.
libcxx/include/__iterator/counted_iterator.h
205

I feel good about that :) done.

zoecarver marked an inline comment as done.

Apply review comments. Thanks Mark!

ldionne requested changes to this revision.Jul 22 2021, 1:06 PM
ldionne added inline comments.
libcxx/include/__iterator/counted_iterator.h
43–46

And then you can remove the named concept above.

54

Ditto.

62

This should be constrained on indirectly_readable?

80

This one should be annotated too.

132–135

This needs to be conditional on #if _LIBCPP_NO_EXCEPTIONS.

libcxx/test/std/iterators/predef.iterators/counted.iterator/minus_minus.pass.cpp
1 ↗(On Diff #360888)

We typically call those increment.pass.cpp and decrement.pass.cpp.

ldionne added inline comments.Jul 22 2021, 1:06 PM
libcxx/include/__iterator/counted_iterator.h
74

[[no_unique_address]]?

83

_LIBCPP_ASSERT(__n >= 0, "message");? Might apply elsewhere we have Precondtions: in the spec.

108

Are you testing the noexcept-ness of this method in your tests? If not, you should, especially since it's in the spec.

118

Ditto for noexcept testing.

126

Precondition!

201

This should be __rhs.__count_ - __lhs.__count_. Also, if there's no test failing right now, we should add one that fails with this incorrect implementation.

223

Missing precondition check.

228

Suggestion: Move this right after operator-> to match the order it's in the spec.

260

Precondition.

268

Precondition.

libcxx/test/std/iterators/predef.iterators/counted.iterator/assign.pass.cpp
17

Here and in all the other tests where the tested function doesn't require more than input_or_output_iterator, I'd like us to pass the input_or_output_iterator archetype as well. That will ensure we don't use capabilities we're not allowed to in the implementation.

60

Can you do:

std::counted_iterator<...>& result = (iter1 = iter2);

and also assert(&result == &iter1)? That makes sure we return the correct object.

72

Can we also add a test for when I == I2, i.e. assigning two iterators of the same type?

80

Can you add a test checking that !std::is_assignable<counted-iterator1, counted-iterator2> when the underlying iterators are not assignable? To ensure we properly constrain the template.

libcxx/test/std/iterators/predef.iterators/counted.iterator/base.pass.cpp
26

Suggestion: templatize that test and call it with the various iterator archetypes to remove a bit of duplication.

libcxx/test/std/iterators/predef.iterators/counted.iterator/compare.pass.cpp
59

Suggestion: add assert(iter2 == iter1)

libcxx/test/std/iterators/predef.iterators/counted.iterator/ctor.pass.cpp
13 ↗(On Diff #360888)

Can you have three files here? ctor.default.pass.cpp, etc.

107 ↗(On Diff #360888)

For the converting constructor, let's add a static_assert(!std::is_constructible<counted_iterator, something-it-should-not-be-constructible-from>) to make sure we constrain the constructor properly.

libcxx/test/std/iterators/predef.iterators/counted.iterator/deref.pass.cpp
58

Can we add a test that *it is SFINAE-d away when the underlying iterator isn't const-dereferenceable? To make sure we have the requires dereferenceable<const I> constraint.

libcxx/test/std/iterators/predef.iterators/counted.iterator/iter_move.pass.cpp
46

We should check the noexcept-ness too.

libcxx/test/std/iterators/predef.iterators/counted.iterator/member_types.compile.pass.cpp
22

What you just told me: This isn't an actual output_iterator since it's not indirectly_writable. So we should rename it. Maybe InputOrOutputArchetype (with a comment like // archetype for input_or_output_iterator)?

Also, this makes me think we should probably move that type in test_iterators.h (even though it's not *technically* an iterator).

libcxx/test/std/iterators/predef.iterators/counted.iterator/minus.pass.cpp
13–23 ↗(On Diff #360888)

Please split (you can leave the default_sentinel overloads in the same file).

71 ↗(On Diff #360888)

using Counted?

72 ↗(On Diff #360888)

And here you can declare it as Counted iter instead of using CTAD.

86 ↗(On Diff #360888)

using Counted = std::counted_iterator<...> (without the const).

Then you just declare const Counted iter(...);, and you can get rid of the std::remove_const_t. WDYT?

149 ↗(On Diff #360888)

Can you add the reason why?

libcxx/test/std/iterators/predef.iterators/counted.iterator/plus_plus.pass.cpp
25 ↗(On Diff #360888)

Why don't you throw on operator++ instead? It seems like the try-catch in operator++(int) is probably meant to catch that more than throwing on copy (even though both are equally important).

113 ↗(On Diff #360888)

Why not just iter++, without assigning the result?

120–129 ↗(On Diff #360888)

I don't think you're testing anything of counted_iterator here, so I think we should remove this test altogether.

libcxx/test/support/test_iterators.h
701 ↗(On Diff #360888)

Nice catch!

This revision now requires changes to proceed.Jul 22 2021, 1:06 PM
zoecarver marked 31 inline comments as done.Jul 26 2021, 9:11 AM
zoecarver added inline comments.
libcxx/include/__iterator/counted_iterator.h
74

Yes, the hidden friends need to use them.

libcxx/test/std/iterators/predef.iterators/counted.iterator/base.pass.cpp
26

This test we could easily do that for, but I like having it be as easy as possible to read. Your brain has to do the absolute minimum amount of work to understand what's going on here. It's harder to get wrong when all the types are concrete.

Also, if there's a failure, say for input_iterators, it will be way easier to catch this way, then looking through a substitution failure/back trace.

libcxx/test/std/iterators/predef.iterators/counted.iterator/minus.pass.cpp
149 ↗(On Diff #360888)

This is just to call out that the iterator doesn't have to be a random access iterator because we never actually touch the iterator itself when doing the minus operation (we subtract the counts).

zoecarver updated this revision to Diff 361688.Jul 26 2021, 9:12 AM
zoecarver marked 3 inline comments as done.

Apply all review comments except for moving files around.

zoecarver marked 7 inline comments as done.Jul 26 2021, 9:35 AM
zoecarver added inline comments.
libcxx/include/__iterator/counted_iterator.h
40

AFAIU this macro doesn't actually do anything useful, so I'm not going to be applying it.

228

I went back and forth on this a lot. Ultimately I think it's better to have it in line with the synopsis because I think that's what people will reference more. However, I could easily be swayed to move it.

zoecarver updated this revision to Diff 361698.Jul 26 2021, 9:36 AM
zoecarver marked 2 inline comments as done.

Apply final few review comments.

ldionne accepted this revision.Jul 26 2021, 11:55 AM

LGTM pending comments and passing CI!

libcxx/include/__iterator/counted_iterator.h
40

It doesn't do anything useful *in this context* because we do not explicitly instantiate the type in the dylib.

libcxx/test/std/iterators/predef.iterators/counted.iterator/arrow.pass.cpp
23

Typo?

libcxx/test/std/iterators/predef.iterators/counted.iterator/base.pass.cpp
33

Weird comma separation.

libcxx/test/std/iterators/predef.iterators/counted.iterator/count.pass.cpp
61

// const versions?

libcxx/test/std/iterators/predef.iterators/counted.iterator/ctor.conv.pass.cpp
23

Consider using ConvertibleTo<IterType> instead? That way, in the tests below, we can see more clearly what types you're trying to test for convertibility, instead of having to look at the conversion operator below.

libcxx/test/std/iterators/predef.iterators/counted.iterator/ctor.default.pass.cpp
22

We need to run the default constructor and make sure it initializes the iterator as it should.

Using = default to implement something is till an implementation, and we need to test that. For example, your test would pass if we never defined it at all, but users would get a linker error when they tried using the default ctor.

libcxx/test/std/iterators/predef.iterators/counted.iterator/minus.iter.pass.cpp
92

I still don't understand this comment. Based on what you just told me, perhaps you should write this instead:

// no need to use a random_access_iterator since counted_iterator doesn't actually subtract the underlying iterators
This revision is now accepted and ready to land.Jul 26 2021, 11:55 AM
zoecarver marked 6 inline comments as done.Jul 26 2021, 12:50 PM

Apply review comments and fix CI.

cjdb accepted this revision.Jul 26 2021, 6:58 PM

I'd like for some of the simple-ish noexcept specifiers to return, but LGTM.

libcxx/include/__iterator/counted_iterator.h
108

Why did the noexcept specifier removed? It's not a difficult one to get right and is arguably useful.

Quuxplusone accepted this revision.Jul 26 2021, 7:48 PM
Quuxplusone added a subscriber: Quuxplusone.

(I didn't look at the tests.)

libcxx/include/__iterator/counted_iterator.h
108

noexcept specifiers are useful if-and-only-if someone has a use for them. For any function whose noexceptness is never used, marking it noexcept is unhelpful — and in fact may be harmful, because (even though I agree this one is "easy to get right") as soon as you get even one noexcept wrong, you end up with a rogue std::terminate. It is possible to introduce a bug by adding noexcept; it is not possible to introduce a bug by leaving it off. Combine this with the general mantra "The best code is no code," and you end up with my standard advice: Use noexcept on move constructors to avoid the vector pessimization, and (in libc++) use it where it's mandated by the paper standard, but otherwise play it safe and keep it simple.

235

This assertion is... confusing. My impression is that __count_ >= 0 is a class invariant. So -__n > __count_ would happen only when the user is trying to decrease by a large negative value, e.g. it -= -42; when it.count() < 42.
So the assertion is(?) correct; but the message should be more like "Attempted to advance a counted_iterator beyond the end of its range". (Compare the grammar to other _LIBCPP_ASSERTs, e.g. in <list>.)

264–267

This doesn't involve the three_way_comparable concept (just common_with), so couldn't you just land it now?

274

I recommend "Attempted to iter_move a non-dereferenceable counted_iterator"

284

I recommend "Attempted to iter_swap a non-dereferenceable counted_iterator"

zoecarver marked 6 inline comments as done.Jul 27 2021, 10:47 AM
zoecarver added inline comments.
libcxx/include/__iterator/counted_iterator.h
108

Why did the noexcept specifier removed? It's not a difficult one to get right and is arguably useful.

The noexcept specifier wasn't removed, this comment just moved.

235

Yes, I'll update the message to make it a bit clearer. Good idea.

274

I think what I have now is a bit clearer. If we answer the question, "why is the iterator non-dereferenceable" then we get the message I have here. And I think that's actually a simpler message; it gets the user to their solution more quickly.

zoecarver marked 2 inline comments as done.

Address review comments and fix 32bit CI.

cjdb requested changes to this revision.Jul 27 2021, 12:18 PM

I just realised there's no iterator concept conformance test.

This revision now requires changes to proceed.Jul 27 2021, 12:18 PM

@cjdb iterator_traits.compile.pass.cpp L71.

cjdb added a comment.Jul 27 2021, 2:40 PM

@cjdb iterator_traits.compile.pass.cpp L71.

Can you please move them out into their own file? We've adopted a convention now.

zoecarver updated this revision to Diff 362196.Jul 27 2021, 3:09 PM

Apply feedback. Fix modules build. Move conformance tests into their own file as requested by Chriss.

This revision was not accepted when it landed; it landed in state Needs Review.Jul 27 2021, 3:50 PM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.