Page MenuHomePhabricator

[libcxx][ranges] Add `counted_iterator`.

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


Group Reviewers
Restricted Project
rG8a48e6dda9f7: [libcxx][ranges] Add `counted_iterator`.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
ldionne added inline comments.Jul 22 2021, 1:06 PM



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


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


Ditto for noexcept testing.




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.


Missing precondition check.


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






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.


Can you do:

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

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


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


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.


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


Suggestion: add assert(iter2 == iter1)

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.


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.


We should check the noexcept-ness too.


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).

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?

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.

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.

Yes, the hidden friends need to use them.


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.

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.

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


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!


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




Weird comma separation.


// const versions?


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.


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.


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.


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.)


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.


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>.)


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


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


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.

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.


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


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.