This is an archive of the discontinued LLVM Phabricator instance.

[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

zoecarver created this revision.Aug 3 2021, 1:14 PM
zoecarver requested review of this revision.Aug 3 2021, 1:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 3 2021, 1:14 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
zoecarver updated this revision to Diff 363861.Aug 3 2021, 1:18 PM
  • Generate private header tests
  • Add hide from ABI
  • Remove log file
cjdb added a comment.Aug 3 2021, 2:03 PM

Mostly LGTM, but a few blockers before I'm happy to give it a green light. A few more comments below.

  • Can you please implement std::ranges::views::iota as well? That one doesn't need a closure, so we can* get away with adding it in this patch.
  • Don't forget the range concept conformance test.
  • You've got a 2.5K log file at the end of this; I don't think that's supposed to be there.
libcxx/include/__ranges/iota_view.h
65

Not that I super care, but why is this is_integral_v and not integral?

99

I really find it cluttering that the iterator is defined inside the range. Took me a whole two minutes to realise I was no longer reviewing iota_view, but rather iota_view::__iterator. (Two mins is probably a slight exaggeration, but it took me longer than I'd have liked.)

Can we please move the definition out-of-line to improve readability?

106–118
123

Since this type is exposition-only, I think we can make this constructor private. That'll lead to fewer users attempting to declare an iterator outright.

132–134
187–191

I'm surprised this can't be just = default;

245–248

I'd also like to see conditional operator use, but the salient feature of the suggested edit is the added else-clause.

250
262

Suggest making this private to limit user-touchability.

285

I know the standard has this, but I don't think it's strictly necessary?

290

I'd really like to see the precondition partially applied, particularly for integers, which are a very common use-case for iota_view. Same with the above constructor.

318–319

It took me editing this to realise that sized_sentinel_for doesn't have parens at all.

321–328

I'd honestly prefer a conditional expression here.

330

Please put this in an else-clause to account for constexpr instantiation..

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

Please add commented-out tests for <=>, or a FIXME, or both. We also still need to test != is not (x == y).

zoecarver marked 10 inline comments as done.Aug 9 2021, 1:40 PM
zoecarver added inline comments.
libcxx/include/__ranges/iota_view.h
123

It also means it's impossible to test.

But more importantly: the standard explicitly stated that this type must be default constructible. If users shouldn't care about it being default constructible, why do that? Why not leave it as an implementation detail? There's nothing about iota_view that requires this iterator to be default constructible.

245–248

We can discuss further about the conditional operator.

290

Just to make sure we're on the same page: you want if constexpr (in-debug-mode and is-valid-operation) _LIBCPP_ASSERT(ranges::less_equal(__value, __bound));? Done.

330

It seems like all compilers that we support, at least, are OK with this.

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

This is not testing == or !=. That's in eq.pass.cpp.

zoecarver updated this revision to Diff 365282.Aug 9 2021, 1:54 PM
zoecarver marked 2 inline comments as done.

Apply Chris' comments.

zoecarver updated this revision to Diff 365300.Aug 9 2021, 3:32 PM

Make ranges::iota_view<bool> invalid everywhere.

Make start private to fix friends in gcc.

zoecarver added inline comments.
libcxx/test/std/ranges/range.factories/range.iota.view/sentinel/minus.pass.cpp
48

@tcanens thoughts?

ldionne requested changes to this revision.Aug 10 2021, 12:23 PM
ldionne added inline comments.
libcxx/include/__ranges/iota_view.h
2

Can you also add views::iota in this patch? It's just a CPO, so it doesn't require the range adaptor stuff (which is close to being done BTW).

28

Not necessary.

44–61
64

Can you please add tests that checks the member typedefs of iota_view::iterator itself? In particular, I'd like to confirm that iterator_difference_t is deduced correctly when W::difference_type has sizes less than short, int, long, etc.

Note per our discussion: If it's not possible to have W::difference_type both be an integral type and be smaller than short, we should perhaps add a static_assert to keep us honest about it. But as we discussed, I think it is possible by having W::difference_type be char.

67

This _If is too eager. It will fail if you pass a non-integer-like-type to it that is larger than sizeof(long long), because you will eagerly instantiate __get_wider_signed_integer here and fail in the static_assert. This can be fixed by changing to this (not super pretty because we lack iter_difference, but oh-well):

template<class _Start>
using _IotaDiffT = typename _If<
  (!integral<_Start> || sizeof(iter_difference_t<_Start>) > sizeof(_Start)),
  type_identity<iter_difference_t<_Start>>,
  __get_wider_signed<_Start>
>::type;

Can you add a test with a non-integer type with a size that's larger than long long and confirm that it fails? If it does not fail, we'll learn something interesting. If it does, we can fix it.

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.

313

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

376–379

Possible spec issue:

I'm kind of wondering why we don't define the constructor like this instead, and avoid defining a deduction guide altogether:

constexpr iota_view(W value, Bound bound) 
    requires (!is-integer-like<W> || !is-integer-like<Bound> ||
             (is-signed-integer-like<W> == is-signed-integer-like<Bound>));

As specified in the Standard, we have the following situation, which seems to be weird and inconsistent:

iota_view<signed, unsigned> view(x, y); // works
iota_view view((signed)x, (unsigned)y); // doesn't work

I think both of them should not work.

@tcanens is that intentional?

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

Not necessary anymore, we don't support GCC 10.

I have a patch to remove them everywhere, but it would be nice if we stopped introducing those in new patches from now on.

ldionne added inline comments.Aug 10 2021, 12:23 PM
libcxx/include/__ranges/iota_view.h
283

Nit: make sure you test explicitness.

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.

230–231

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

237

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.

369

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
45–46

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
147

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
45–46

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
147

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
45–46

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
48

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
48

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.

237

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
1 ↗(On Diff #366123)

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.

237

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.