This is an archive of the discontinued LLVM Phabricator instance.

[libc++] [ranges] Implement std::ranges::distance
ClosedPublic

Authored by Quuxplusone on Jan 21 2022, 8:01 PM.

Details

Summary
This includes an experimental workaround for
LWG3664 "LWG3392 broke std::ranges::distance(a, a+3)",
but the workaround may be incomplete, I'm not sure.
This should be re-audited when LWG3664 is actually adopted,
to see if we need to change anything about our implementation.

See also https://github.com/microsoft/STL/pull/2500

The current draft standard says

template<input_or_output_iterator I, sentinel_for<I> S>
  requires (!sized_sentinel_for<S, I>)
    constexpr iter_difference_t<I> distance(I first, S last);

template<input_or_output_iterator I, sized_sentinel_for<I> S>
  constexpr iter_difference_t<I> distance(const I& first, const S& last);

My P/R is

template<class I, sentinel_for<I> S>
  requires (!sized_sentinel_for<S, I>)
    constexpr iter_difference_t<I> distance(I first, S last);

template<class I, sized_sentinel_for<decay_t<I>> S>
  constexpr iter_difference_t<I> distance(const I& first, S last);

Microsoft STL is also planning to adopt the P/R: https://github.com/microsoft/STL/pull/2500

However, @tcanens pointed out a problem with the P/R: you can have an evil sentinel that is a sized_sentinel_for<int*> but doesn't support last - first when first is not literally an int*.

Diff Detail

Event Timeline

Quuxplusone requested review of this revision.Jan 21 2022, 8:01 PM
Quuxplusone created this revision.
Herald added 1 blocking reviewer(s): Restricted Project. · View Herald TranscriptJan 21 2022, 8:01 PM
philnik accepted this revision as: philnik.Jan 22 2022, 5:20 AM

LGTM % nits

libcxx/docs/Status/RangesPaper.csv
74
libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
34

Since you're testing 3/4 possible combinations also test the fourth? ditto below.

113–114

Please move the static_asserts together.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/range.pass.cpp
53

Why not std::move?

Quuxplusone marked 3 inline comments as done.
Quuxplusone edited the summary of this revision. (Show Details)
Quuxplusone added a reviewer: CaseyCarter.

Wow, niebloid.compile.pass.cpp caught a real LWG-worthy bug! std::ranges::distance(a, a+10) didn't compile, and I hadn't thought to test that case directly in my new tests. Now I'm testing it (and have implemented a workaround while we wait for the LWG issue to be recorded).

s/Complete/|Complete|/

Quuxplusone edited the summary of this revision. (Show Details)

Try to fix the Apple build's CI failure: https://buildkite.com/llvm-project/libcxx-ci/builds/8074
by adding UNSUPPORTED: libcpp-has-no-incomplete-ranges to the test that uses subrange.

Since the current Standard seems to be broken I agree with implementing your proposed LWG-issue.
I prefer to wait with landing until you have a number so it can be used in the issue table and commit message.

libcxx/docs/Status/Cxx2bIssues.csv
140

Can you add your new issue here once you have a number?

libcxx/include/__iterator/distance.h
63

input_or_output_iterator doesn't match the description. Should this be input_or_output_iterator if just class _Ip?

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
17

Please update this to match the implementation.

81

Likewise two lines above.

Quuxplusone marked 4 inline comments as done.Jan 23 2022, 7:49 AM
Quuxplusone added inline comments.
libcxx/docs/Status/RangesPaper.csv
74

Meh, we only have one row here, and he did 3/4 of them.

libcxx/include/__iterator/distance.h
63

Oops, good catch. This should be class _Ip. (The constraint is superfluous, because it's already implied by sentinel_for<_Ip> _Sp right afterward. Therefore, we remove the superfluous constraint, to save the environment.)

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
113–114

These four tests are always in the same order: lvalue-lvalue, lvalue-rvalue, rvalue-lvalue, rvalue-rvalue.
Although, in this case, I did throw in line 115, which broke up the pattern a bit. I should just remove line 115.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/range.pass.cpp
53

I was waffling between using static_cast for all of the cvref-qualifications, or using the more "normal-looking" versions; e.g. line 51 could have said static_cast<R&>(r) too. I think I'll change line 39 to avoid std::move, which might help avoid the question. :)

Quuxplusone marked 2 inline comments as done.

Review comments. CI should still be green.
Still waiting on an LWG issue number; will add it to libcxx/docs/ when I get it.

Quuxplusone edited the summary of this revision. (Show Details)Jan 23 2022, 7:53 AM
Mordante accepted this revision as: Mordante.Jan 23 2022, 9:18 AM

LGTM.

Quuxplusone updated this revision to Diff 402647.
Quuxplusone edited the summary of this revision. (Show Details)
Quuxplusone added a subscriber: tcanens.

Improve the LWG3664 evil test case a bit more.

s/remove_reference/__uncvref/, and regression-test.

var-const added inline comments.Jan 24 2022, 4:59 PM
libcxx/docs/Status/RangesPaper.csv
74

You can do Christopher Di Bella and Arthur O'Dwyer (see line 100).

A few comments, nothing big. Overall LGTM, thanks.

This supersedes D102789 (mentioning so it gets cross-referenced).

libcxx/docs/Status/Cxx2bIssues.csv
101

Can you add an entry for not-yet-voted LWG3664 and mark it as implemented?

However, @tcanens pointed out a problem with the P/R: you can have an evil sentinel that is a sized_sentinel_for<int*> but doesn't support last - first when first is not literally an int*.

So do I understand correctly that the resolution of LWG3664 might change? I just want to be careful to avoid implementing stale resolutions.

libcxx/docs/Status/RangesPaper.csv
74

I've used various in the past too. Just to clarify, the goal of these is not attribution, it's only to keep track of who's doing what. In fact, this page will be removed as soon as all of the original "One Ranges Proposal" is fully implemented, and then we'll fold that into a simple green check-mark in front of P0896.

74
libcxx/include/__iterator/distance.h
81

This is to handle the array case, right? I assume the answer is yes, but do you have a test case for this if constexpr?

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
2

We seem to be missing tests that count the number of operations we're doing. Can you add some using stride_counting_iterator?

ldionne requested changes to this revision.Jan 26 2022, 10:32 AM
This revision now requires changes to proceed.Jan 26 2022, 10:32 AM
libcxx/include/__iterator/distance.h
81

The current (but problematic) P/R for LWG3664 fixes the array-vs-pointer case. This if constexpr is specifically for the array-vs-EvilSentinel case, and yes, that's tested.

A more helpful way to look at is probably: line 81 is actually the happy path, that works for almost all iterator types and for all array types... but line 81 doesn't work for move-only iterator types such as cpp20_input_iterator. For those move-only types, we must use line 78 instead.

This is my current-informally-suggested P/R for LWG3664. The P/R will change at some point, because we need ranges::distance(a, a) to work — it's just unacceptable for it not to work. Therefore, I'm willing to add a line for LWG3664 but wouldn't mark it "Complete", which also means maybe we don't need to add a line at all, and can just wait for LWG3664 to be adopted before we revisit and audit it. WDYT?

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
2

Sure, will do, although you probably know I'm not a fan of stride_counting_iterator in its current state.

ldionne added inline comments.Jan 26 2022, 12:27 PM
libcxx/include/__iterator/distance.h
81

Hmm, tricky. Let's not mention LWG3664 at all then, and we can audit the state of our implementation when it is actually filed.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
2

Yeah, me neither, but it still provides something of value for test coverage.

ldionne added inline comments.Jan 26 2022, 1:00 PM
libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
7

We also seem to be missing tests for the return type of ranges::distance, unless I missed them.

Quuxplusone marked 7 inline comments as done.
Quuxplusone edited the summary of this revision. (Show Details)

Add two stride-counting tests. (I made my own type rather than use stride_counting_iterator, because (1) it seemed easier, and (2) I need something that holds a pointer *inc_ rather than incrementing a count stored inside the iterator itself. Seems like stride_counting_iterator was written specifically for ranges::advance and nothing else, because it assumes the iterator will never be copied.)
Add ASSERT_SAME_TYPE tests.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
17

I guess it's still unclear what we should put here. What's here right now is the P/R for LWG3664, but we know the P/R is buggy — what I actually implemented uses I&& in place of const I&. I can fix that before landing, if we decide it needs fixing. No matter what, the person who fixes LWG3664 should re-audit this comment anyway.

Alternative ideas: use the P/R as written (i.e. what's here now); or, use the working draft's wording (i.e., remove the decay_t and replace S with const S&).

Mordante added inline comments.Jan 30 2022, 5:51 AM
libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/iterator_sentinel.pass.cpp
17

I think it would be better to use I&& since that's what you've implemented. Maybe add a comment this wording needs updating for LWG3664.

s/const I&/I&&/ in the test comment. Leave a TODO for when LWG3664 is actually resolved by LWG.
@ldionne I believe all your comments have been addressed; let me know if that's not the case.

ldionne accepted this revision.Jan 31 2022, 8:54 AM

LGTM. We could/should look into simplifying some of the existing tests we have that use stride_counting_iterator. It occurs to me that those existing tests probably don't need to check stride_counting_iterator<various archetypes>, and a simple check like what you do here provides basically the same coverage.

This revision is now accepted and ready to land.Jan 31 2022, 8:54 AM