Page MenuHomePhabricator

[libcxx][ranges] Add `ranges::iota_view`.
ClosedPublic

Authored by zoecarver on Aug 3 2021, 1:14 PM.

Details

Reviewers
cjdb
ldionne
Group Reviewers
Restricted Project
Commits
rG7b20e05c714e: [libcxx][ranges] Add `ranges::iota_view`.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
ldionne added inline comments.Aug 10 2021, 12:23 PM
libcxx/include/__ranges/iota_view.h
99

I think the correct location to fix this issue is in whatever concept currently accepts bool when it shouldn't, which is weakly_incrementable IIUC. So I would suggest fixing that in weakly_incrementable with a && !same_as<bool, T>, along with a test that bool doesn't model weakly_incrementable (which we must be lacking right now), and also a TODO comment to remove the special case for bool once Clang has been fixed.

283

Nit: make sure you test explicitness.

313

Do you test the explicitness by checking !std::is_convertible? If not, please do.

319–321

That would match the spec better.

332

This is very nitpicky, but I would rather define this as iota_view(__iterator __first, _Bound __last) even though those are the same, simply because it matches the spec more closely and IMO it is easier to read that way (see http://eel.is/c++draft/range.iota#view-11.2).

363

Can you please add tests at boundary conditions like numeric_limits<T>::max() & friends?

libcxx/test/std/ranges/range.factories/range.iota.view/sentinel/minus.pass.cpp
49

Instead, can we add tests to confirm that this *doesn't* work? Can we file a LWG issue to relax this requirement? If this is indeed issue-worthy, our test is going to fail when we fix it, as it should.

libcxx/test/std/ranges/range.factories/range.iota.view/types.h
2

Missing license.

This revision now requires changes to proceed.Aug 10 2021, 12:23 PM

Minor nits.

libcxx/include/__ranges/iota_view.h
99

+1 what Louis said; and anyway, since iota_view is supposed to be constrained, the mechanism needs to be SFINAE-friendly (as Louis's suggestion is). E.g. we expect https://godbolt.org/z/fcx3r61PT

template<class T> iota_view<T> f(int);
template<class T> void f(...);
int main() { f<bool>(42); }

to be unambiguous because SFINAE.

231–232

Nit: You might as well provide the commented-out definition of this function's body. Also, bool should be auto.

238

This matches the Standard reference implementation, but it might be worth noting that return a += b; does a copy-construct of parameter a, whereas a += b; return a; would do only a move-construct.

370

Style nit: Even though the arguments are going to be integral, I'd like to see the usual ADL-proofing on this function call: _VSTD::__to_unsigned_like(...) throughout.

libcxx/test/std/ranges/range.factories/range.iota.view/begin.pass.cpp
46–47

I notice a conspicuous lack of long long and unsigned long long here.
Notice that iota_view<long long>::difference_type needs to be __int128_t or some other integer-like class type suitable for holding the signed difference between LLONG_MIN and LLONG_MAX.

libcxx/test/std/ranges/range.factories/range.iota.view/types.h
148

I bet you could use forward_iterator<int*> out of test_iterators.h here, instead of having to invent your own type. You can make an iota_view<forward_iterator<int*>>, right?

zoecarver marked 17 inline comments as done.Aug 10 2021, 5:42 PM
zoecarver added inline comments.
libcxx/include/__ranges/iota_view.h
2

I will do this later tonight or tomorrow morning.

67

error: static_assert failed due to requirement 'sizeof(BigType) <= sizeof(long long)' "Found integer-like type that is bigger than largest integer like type."

libcxx/test/std/ranges/range.factories/range.iota.view/begin.pass.cpp
46–47

Notice that iota_view<long long>::difference_type needs to be __int128_t or some other integer-like class type suitable for holding the signed difference between LLONG_MIN and LLONG_MAX.

Is that standard? Are we supposed to support types larger than long? That is why I dropped it from this test. (I should have made a comment, though).

libcxx/test/std/ranges/range.factories/range.iota.view/sentinel/minus.pass.cpp
49

Test added. I'll file the LWG issue tomorrow.

libcxx/test/std/ranges/range.factories/range.iota.view/types.h
148

While I suppose we could, the problem is we need to somehow get a buffer to forward_iterator and then we can't use it to test a default constructible iterator. I think this is a bit simpler.

zoecarver updated this revision to Diff 365634.Aug 10 2021, 5:44 PM
zoecarver marked 3 inline comments as done.

Apply review comments

cjdb added inline comments.Aug 10 2021, 6:04 PM
libcxx/include/__ranges/iota_view.h
258–261
319–321

This suggestion is too general: we're deliberately restricting this to integers and pointers because general reachability is not detectable.

356–362

Yes, I inverted the first condition and moved it to the top.

libcxx/test/std/ranges/range.factories/range.iota.view/begin.pass.cpp
46–47

Are we supposed to support types larger than long?

Yes, this is a reason why integer-like exists.

libcxx/test/std/ranges/range.factories/range.iota.view/iterator/compare.pass.cpp
2

I count four assertions for an ==?

tcanens added inline comments.Aug 10 2021, 9:46 PM
libcxx/include/__ranges/iota_view.h
376–379

This seems to me to be a "we'll protect you from accidentally shooting yourself in your foot, but not from intentionally pointing your gun at your foot and pulling the trigger" case. Mixing signs isn't inherently incorrect, so if people want to do it explicitly they can, but the deduction guide forces the type to be spelled out so that the mixedness is obvious.

It's more of an Eric/Casey question though.

libcxx/test/std/ranges/range.factories/range.iota.view/sentinel/minus.pass.cpp
49

sized_sentinel_for has an opt-out, and any relaxation would need to both respect that and perhaps supply its own opt-out mechanism. That gets hairy pretty quickly and doesn't seem to be worth the extra complexity.

zoecarver marked 4 inline comments as done.Aug 11 2021, 9:42 AM
zoecarver added inline comments.
libcxx/include/__ranges/iota_view.h
258–261

The conditional expression here does not seem easier to read. I could see an argument for it to be the same difficulty, but to me it is harder to read than the if statement. I don't see a reason to change this.

319–321

What does "general reachability is not detectable" mean?

I think this is fine because the standard says:

Preconditions: Bound denotes unreachable_­sentinel_­t or bound is reachable from value. When W and Bound model totally_­ordered_­with, then bool(value <= bound) is true.

356–362

Same as above, but this is even harder to read. I really think nested ternaries are an anti pattern, especially when there is a lot going on in each condition. If it was just a variable, that would be one thing, but there are operators inside operators inside operators here, and that makes this very hard to parse. What are we gaining by using the conditional operator here?

libcxx/test/std/ranges/range.factories/range.iota.view/iterator/compare.pass.cpp
2

It's just a sanity check to show that we're starting from the same place. If you feel strongly I can remove them.

libcxx/test/std/ranges/range.factories/range.iota.view/sentinel/minus.pass.cpp
49

I will never understand the decision matrix that leads to the Committee thinking some things are worth the complexity and others aren't :P

Anyway, thanks for the info about this, Tim. I guess I won't file an LWG issue, then.

zoecarver marked 4 inline comments as done.Aug 11 2021, 9:44 AM
zoecarver added inline comments.
libcxx/include/__ranges/iota_view.h
376–379

This seems to me to be a "we'll protect you from accidentally shooting yourself in your foot, but not from intentionally pointing your gun at your foot and pulling the trigger" case. Mixing signs isn't inherently incorrect, so if people want to do it explicitly they can, but the deduction guide forces the type to be spelled out so that the mixedness is obvious.

This logic makes sense. I suppose that also explains why the deduction guide is here in the first place (and we don't just remove the type_identity_ts from the _Start/_Bound ctor). As always, thanks for interpreting the Standard for us :)

  • Add views::iota.
  • Fix all the bots except for UBSan.
ldionne requested changes to this revision.Aug 11 2021, 1:23 PM
ldionne added a subscriber: CaseyCarter.
ldionne added inline comments.
libcxx/include/__ranges/iota_view.h
32–39

This can go away now too.

42

This can go away.

376–379

Ping @CaseyCarter, is that really the intent here?

@zoecarver For the time being, can you please make sure those are tested? I'd like a test that fails if we add the constraints to the constructor, and one that fails if we remove them from the deduction guide.

381–391

Those are not expression-equivalent as they are required to by http://eel.is/c++draft/range.iota#overview-2. Please also add tests that we're SFINAE friendly (which would fail right now).

libcxx/test/std/ranges/range.factories/range.iota.view/iterator/member_typedefs.compile.pass.cpp
94
110

As you said live, I think this is valid per https://eel.is/c++draft/range.iota.view#1.3. I would suggest this:

// comment with link to spec
static_assert(sizeof(Iter::difference_type) >= sizeof(long long));
static_assert(std::is_signed_v<Iter::difference_type>);
LIBCPP_STATIC_ASSERT(std::same_as<Iter::difference_type, long long>);
libcxx/test/std/ranges/range.factories/range.iota.view/iterator/minus.pass.cpp
25–29
libcxx/test/std/ranges/range.factories/range.iota.view/sentinel/minus.pass.cpp
58

This should go away now. And the comment above with !MinusInvocable<int> should be fixed.

This revision now requires changes to proceed.Aug 11 2021, 1:23 PM
zoecarver marked 9 inline comments as done.Aug 12 2021, 10:29 AM
zoecarver marked an inline comment as done.

Rebase and apply review comments.

ldionne accepted this revision.Aug 12 2021, 11:11 AM

LGTM assuming you fix my comments and CI passes! Thanks!

libcxx/test/std/ranges/range.factories/range.iota.view/begin.pass.cpp
2

Throughout: please make sure you test mixing signed and unsigned bounds (and unsigned/signed too).

libcxx/test/std/ranges/range.factories/range.iota.view/size.pass.cpp
40

This is currently UB until we fix the spec IIUC. Please comment it out and add a comment explaining this is pending on LWG issue resolution.

91

Uncomment this.

This revision is now accepted and ready to land.Aug 12 2021, 11:11 AM

Apply comments.

zoecarver updated this revision to Diff 366123.Aug 12 2021, 3:09 PM

Fix modules build and windows build.

cjdb added a comment.Aug 13 2021, 10:45 AM

Please add range concept conformance tests.

libcxx/include/__ranges/iota_view.h
45

Since Clang supports __int128 and acknowledges that as an integral type (as does libc++), we should fix this to account for that too.

95

Keep the conditions and the results in distinct columns please.

238

Since it's an effects-equivalent-to, I'm not sure if we're allowed to change this at all without first filing an LWG issue (which I'd be okay with). @tcanens any input?

241

This should match operator+= or vice versa.

258–261

We're at a bit of an impasse then, because I find the if-statement approach to be the less-readable one.

319–321

Being able to detect whether an iterator can reach a sentinel is not something that we can always check. However, given that precondition, I think it's okay in this case.

356–362

especially when there is a lot going on in each condition

The conditions are very simple.

I really think nested ternaries are an anti pattern

The reason I inverted the expression and moved it to the top was to flatten the expression. In its current state, there the expressions aren't nested (but the standard wording is nested).

What are we gaining by using the conditional operator here?

It's flat and it's a single expression that can be reasoned about. The way the proposes conditional expression is structured is the same as my rewrite of iterator_concept and similar to Louis' rewrite of __get_wideer_signed.
By collecting these if-statements into a single expression, we transform imperative code into declarative code, which reduces complexity, and we get to rely on pattern matching:

case 1    -> result 1
case 2    -> result 2
otherwise -> default result
370–371

Please move this into namespace ranges.

378

What's wrong with having an auto return type?

387

Ditto.

393–396

Up to you as to whether or not you wanna do it in this patch or separately, but please add the following to <ranges>:

_LIBCPP_BEGIN_NAMESPACE_STD

namespace views = namespace ranges::views;

_LIBCPP_END_NAMESPACE_STD

Now that we've got something in ranges::views, this is worth adding ASAP.

libcxx/test/std/ranges/range.factories/range.iota.view/iterator/compare.pass.cpp
2

Oh, in that case please rename it to inequality.pass.cpp, since I thought this was checking all the comparison operations, not just inequalities.

libcxx/test/std/ranges/range.factories/range.iota.view/views_iota.pass.cpp
2

You'll also need to add tests for std::ranges::views::iota.

This revision was automatically updated to reflect the committed changes.
zoecarver marked 11 inline comments as done.Aug 13 2021, 4:17 PM
zoecarver added inline comments.
libcxx/include/__ranges/iota_view.h
45

As we discussed offline, I have concerns about portability here.

I'd be open to it, but let's do it in it's own patch so we can discuss more thoroughly.

238

I'll send something to the lwg chair.

241

done.

258–261

See discord discussion.

370–371

Done in a separate patch.

378

(As discussed offline) We want this for SFINAE.

libcxx/test/std/ranges/range.factories/range.iota.view/iterator/compare.pass.cpp
2

I just deleted eq.pass.cpp and test not-equals here.

libcxx/include/__ranges/iota_view.h
258–261

IIUC, you're discussing the cascade that currently looks like this:

if constexpr (__integer_like<_Start>) {
  if constexpr (__signed_integer_like<_Start>) {
    return difference_type(difference_type(__x.__value_) - difference_type(__y.__value_));
  }
  if (__y.__value_ > __x.__value_) {
    return difference_type(-difference_type(__y.__value_ - __x.__value_));
  }
  return difference_type(__x.__value_ - __y.__value_);
}
return __x.__value_ - __y.__value_;

for which the Standard reference implementation is

if constexpr (is-integer-like<W>) {
  if constexpr (is-signed-integer-like<W>)
    return D(D(x.value_) - D(y.value_));
  else
    return (y.value_ > x.value_)
      ? D(-D(y.value_ - x.value_))
      : D(x.value_ - y.value_);
} else {
  return x.value_ - y.value_;
}

Personally I'd recommend sticking to the reference implementation (including the ?:), to make it easy to verify that libc++ matches the Standard-mandated behavior (even though it is not obvious what that behavior actually is!). Alternatively, if we wanted to make it easy to read the code, one way to do that is to disentangle the nested ifs and turn it into a plain if-else-if ladder:

if constexpr (!__integer_like<_Start>) {
  return __x.__value_ - __y.__value_;
} else if constexpr (__signed_integer_like<_Start>) {
  return difference_type(difference_type(__x.__value_) - difference_type(__y.__value_));
} else if (__y.__value_ > __x.__value_) {
  return difference_type(-difference_type(__y.__value_ - __x.__value_));
} else {
  return difference_type(__x.__value_ - __y.__value_);
}

Writing it out longhand this way really illustrates the insanity of the reference implementation: each branch puts its explicit casts to difference_type in different places! Particularly the first and fourth branches (in the if-else-if ladder version above) are gratuitously different: the first uses an implicit conversion, the last an explicit conversion. If these conversions can have observably different behavior, something is seriously broken.