This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][ranges] Add ranges::size CPO.
ClosedPublic

Authored by zoecarver on Apr 22 2021, 9:30 AM.

Details

Summary

The begining of [range.prim].

Diff Detail

Event Timeline

zoecarver created this revision.Apr 22 2021, 9:30 AM
zoecarver requested review of this revision.Apr 22 2021, 9:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 22 2021, 9:30 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
zoecarver added inline comments.
libcxx/include/__ranges/size.h
35

Note: phab CLI gets confused if I put multiple dependencies on a patch, so I'm just re-implementing this here and I'll remove it once D100587 lands.

59

Also note: as I understand it, integral and integer like are interchangeable for us, if this is not the case, let me know.

cjdb added a subscriber: tcanens.Apr 22 2021, 9:43 AM

Implementation LGTM, will look at tests soonish.

libcxx/include/__ranges/size.h
55

Thanks for making something that clears up the double negative!

73

Yeah, I don't think this one is necessary here.

78

See http://eel.is/c++draft/ranges.syn#1.

The result needs to be the iter_difference_t<_Tp>, and since I've asserted that we only care about (extended) integral types, we're clear to use make_unsigned_t<iter_difference_t<_Tp>>.

105

@tcanens mentioned in D100255 that __decay_copy isn't necessary in the actual function calls.

  • Apply clarification and feedback from @cjdb.
libcxx/include/__ranges/size.h
78

Okay good to know. sized_sentinel_for requires the result to be iter_difference_t so I don't think we need to check that here. I'll add a static cast below, though.

libcxx/include/__ranges/size.h
86–90

(A) I see how integral auto is mimicking https://eel.is/c++draft/range.prim.size#4 ; however, that seems to inappropriately restrict people from trying to use their own "integer-like" types, at the cost of compile-time-slowness and source-code-size. I propose that you remove the word integral from every overload here and below.

(B) Your noexcept specification fails to account for the decay-copy that happens if __t.size() returns const SomeType&. Admittedly, this is a problem only if you remove the integral constraint, because decay-copying a primitive integral type can't possibly throw.

(C) for the record: One might observe that all these conditional-noexcept-specifications violate the spirit of P0884 "Extending the noexcept Policy" and propose removing them; but @tcanens has pointed out that "expression-equivalent to" implies "has the same noexceptness as," so we are actually mandated to use (correct) noexcept-specifications throughout basically all of Ranges. (Ugh, but unavoidable.)

105

Could you explain why this =delete'd overload is necessary?
I see how it is observable ( https://godbolt.org/z/PGxzf4jGz ) and I assume it is permitted, but I don't see why it's necessary in libc++. Other implementors (GCC, MSVC) get away without it.

116

You can delete this line now. Thanks for removing this macro.

libcxx/test/std/ranges/range.access/range.prim/size.compile.pass.cpp
122–123

Throughout: s/Convertable/Convertible/

126

(A) Remove constexpr. Remove the function body. size_t size() const; is sufficient.
(B) I notice you didn't const-qualify this member; I assume it was unintentional; but this is a good place to ask, what is supposed to happen if a type has a non-const-qualified size()? What does that imply for the truthiness of sized_range<{const,} T{&,&&,}>?

192–196

You use assert and have a main, but this file's name is size.compile.pass.cpp.
I suppose we need yet another CI step to prevent people from putting mains in their .compile.pass.cpp tests... and probably to prevent using the identifier-token assert in those files, either.

libcxx/test/support/test_range.h
20

This function body should be unnecessary. If it's needed by some test, that test is wrong.
If for testing purposes we want a sentinel type that always produces an empty range, then we should name it something clearer than struct sentinel.

cjdb added inline comments.Apr 22 2021, 11:12 AM
libcxx/include/__ranges/size.h
86–90

that seems to inappropriately restrict people from trying to use their own "integer-like" types, at the cost of compile-time-slowness and source-code-size.

Only the implementation may provide integer-like types, so this is a non-concern.

101

This can be range_difference_t<remove_cvref_t<_Tp>>.

105

It provides good intrinsic documentation. @zoecarver can you please contrast the diagnostic with/without this deletion, and maybe upload them to a GitHub gist?

zoecarver added inline comments.Apr 22 2021, 11:16 AM
libcxx/include/__ranges/size.h
86–90

See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1522r1.pdf, specifically para 2.2

We do this in such a way that (a) only implementors of the Standard Library can define and use such types for now, and (b) is forward ABI compatible...

Also, this: https://reviews.llvm.org/D100080#inline-952255


The Standard requires that these are only integer like types, and tells us that we get to decide what that means. I think, if for no other reason than we should strive for maximum compatibility (i.e., someone shouldn't be able to write some integer type and use it in their program such that libc++ compiles and libstdc++ or msvc doesn't) we should require these types are integral. Also, I think there is an argument for correctness here.

The "compile-time-slowness and source-code-size" are extremely minimal here. The former likely can't be measured over noise.

105

This is a so called poison pill. I could be persuaded to remove it, but I think it makes the error message nicer for users. I'd like to point out that other implementations do use it.

zoecarver added inline comments.Apr 22 2021, 11:25 AM
libcxx/include/__ranges/size.h
105

@cjdb I didn't see your comments when I made mine :)

Anyway, here's a gist: https://gist.github.com/zoecarver/594015f42664e3daa7ab7c3978027682

I'm now less convinced that deleting this overload is the correct way to go.

libcxx/include/__ranges/size.h
105

@zoecarver: No. The "poison pill" is the thing on lines 50-51. This is a plain old deleted overload of operator(), and GCC/MSVC seem not to use it. Check out the godbolt where the difference is observable: https://godbolt.org/z/PGxzf4jGz and compare it locally versus your implementation.

cjdb added inline comments.Apr 22 2021, 11:51 AM
libcxx/include/__ranges/size.h
105

Admittedly the deleted function is less useful in ranges::size than in ranges::begin because ranges::size accommodates all array bounded arrays, not just lvalue arrays. I support whichever provides cleaner diagnostics.

cjdb added inline comments.Apr 22 2021, 11:51 AM
libcxx/include/__ranges/size.h
82

Otherwise, if T is an array type, ranges​::​size(E) is expression-equivalent to decay-copy(extent_­v<T>).

This needs to be changed to support all bounded arrays, not just lvalue bounded arrays (especially in the wake of the deleted overload).

zoecarver updated this revision to Diff 339809.Apr 22 2021, 3:59 PM
  • Fix based on review.
libcxx/test/std/ranges/range.access/range.prim/size.compile.pass.cpp
126

(B) I notice you didn't const-qualify this member; I assume it was unintentional; but this is a good place to ask, what is supposed to happen if a type has a non-const-qualified size()? What does that imply for the truthiness of sized_range<{const,} T{&,&&,}>?

sized_range<const T> is true when T has a const member. It's false if the size member isn't const. That's why I actually wanted to keep this as simple as possible. It's exactly the same as SizeMember except it's disabled. I can add another one to test with a const member.

cjdb added a comment.Apr 22 2021, 4:11 PM

Tests mostly LGTM, but I couldn't find any tests for when member size and ADL size return signed integers. It's important that signedness is preserved in both cases, so we should add tests if there aren't any.

libcxx/include/type_traits
2814

No longer necessary (I'd prefer it be added in a separate commit).

libcxx/test/std/ranges/range.access/range.prim/size.pass.cpp
38 ↗(On Diff #339809)

Please also test SizeFunctionRef and SizeFunctionRefToConst.

136–139 ↗(On Diff #339809)
148–153 ↗(On Diff #339809)

This, however, is fine :-)

170–176 ↗(On Diff #339809)

Please add a test for when the iterator isn't a forward_iterator.

zoecarver updated this revision to Diff 339821.Apr 22 2021, 5:02 PM
  • Update based on review.
zoecarver updated this revision to Diff 339823.Apr 22 2021, 5:05 PM

BidirectionalRange -> RandomAccesslRange

Harbormaster completed remote builds in B100407: Diff 339821.
ldionne requested changes to this revision.Apr 23 2021, 11:05 AM

Overall looks great, with a few comments.

Also:

  1. Is there something to update in the Ranges progress document?
  2. Can we add conformance tests for the types defined in libc++? std::vector & friends.
libcxx/include/__ranges/size.h
10

_LIBCPP___RANGES_SIZE_H if we want to be consistent? I agree it's ugly as hell though, so maybe we should revisit that policy! But for now let's be consistent?

59

I think we need to introduce a proper concept for integer-like types:

template <typename _Ip>
concept __integer_like = !same_as<bool, _Ip> && integral<_Ip>;

According to the Standard:

A type I other than cv bool is integer-like if it models integral<I> or if it is an integer-class type.

That would also be an indirection point where we can add our own implementation-defined integer-class type if we have one.

Right now, my understanding is that this concept would be satisfied if t.size() returned a bool. Instead, we should use -> __integer_like so that bool is excluded. Can you confirm that it's a problem and add a test that fails when that's the case?

This comment applies to other uses of integral below (and so we should add tests for those too).

82–90

Just thinking out loud, but this works if you pass a reference to a const array because it'll deduce _Tp = Foo const such that the whole signature is Foo const (&)[_Sz]?

107–108

Would it be worth creating a __to_unsigned_like helper function that we can reuse? I don't know the spec by heart, but I imagine that if they factored out the term of art to-unsigned-like in the spec (https://eel.is/c++draft/ranges#syn-1), it must be because we're re-using it elsewhere?

111

// end namespace __size

114

Indent inside the namespace!

This revision now requires changes to proceed.Apr 23 2021, 11:05 AM
cjdb added a comment.Apr 23 2021, 11:33 AM

Can we add conformance tests for the types defined in libc++? std::vector & friends.

This should be done in the sized_range patch IMO, similar to how I deferred conformance tests for D100255 to D100269.

libcxx/include/__ranges/size.h
59

Yes, but it looks like I can do this in D100080. Nice catch! http://eel.is/c++draft/iterators#iterator.concept.winc-11

zoecarver added inline comments.Apr 23 2021, 2:30 PM
libcxx/include/__ranges/size.h
59

@cjdb I agree. It would be great if you could implement __integer_like as Louis described and then implement __is_signed_integer_like in terms of that. Once __integer_like exists I'll update this patch to use it.

82–90

Yes. Added a test.

zoecarver updated this revision to Diff 340168.Apr 23 2021, 2:32 PM
  • Apply review comments.

(Sorry forgot to respond to a few comments...)

Is there something to update in the Ranges progress document?

I already marked [range.prim] as in progress/assigned to me. Once it's done I'll mark it as complete.

This should be done in the sized_range patch IMO, similar to how I deferred conformance tests for D100255 to D100269.

As usual, I don't feel strongly. I'm happy to implement this with sized_range.

zoecarver added inline comments.Apr 30 2021, 10:08 AM
libcxx/include/__ranges/size.h
59

Ping: use __integer_like after rebasing.

libcxx/test/std/ranges/range.access/range.prim/size.pass.cpp
11 ↗(On Diff #340168)

Add msvc and clang.

zoecarver updated this revision to Diff 342035.Apr 30 2021, 2:15 PM
  • Remove filename in header/license comment.
  • Use __integer_like.
  • XFAIL msvc.
zoecarver updated this revision to Diff 342048.Apr 30 2021, 2:43 PM
  • Fix includes.
ldionne accepted this revision.Apr 30 2021, 2:50 PM

LGTM once you add a test with bool (to catch the change you made by using __integer_like), and CI passes.

This revision is now accepted and ready to land.Apr 30 2021, 2:50 PM
zoecarver updated this revision to Diff 342054.Apr 30 2021, 2:53 PM
  • Add test for function/member with bool return type.
cjdb accepted this revision.Apr 30 2021, 3:17 PM
cjdb added inline comments.
libcxx/test/std/ranges/range.access/range.prim/size.pass.cpp
22 ↗(On Diff #342054)

Please add a test to ensure RangeSizeT is semiregular.

zoecarver updated this revision to Diff 342552.May 3 2021, 2:53 PM
  • Rebase.
  • Add test for semiregular.
zoecarver updated this revision to Diff 342763.May 4 2021, 8:57 AM

int -> short so the tests pass on 32 bit.

Quuxplusone added inline comments.May 4 2021, 9:33 AM
libcxx/include/__iterator/concepts.h
142–145 ↗(On Diff #342763)

It seems to me that this function belongs right below make_unsigned_t, and not right below bidirectional_iterator.

libcxx/test/std/ranges/range.access/range.prim/size.pass.cpp
47 ↗(On Diff #342763)
172 ↗(On Diff #342763)

size_t size() const

182–185 ↗(On Diff #342763)

The comment doesn't match the code. I believe you intended to write

inline constexpr bool std::disable_sized_range<const ConstSizeMemberDisabled> = true;

Also, please rename to something like s/ConstSizeMemberDisabled/ImproperlyDisabled/

195 ↗(On Diff #342763)

Pass-by-const-value alert!
Either add the &, or remove the const. (Personally I'd add the &.)
https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/
That blog post ends with some git grep lines; please run them over this and the rest of your patches and see how many other typos they catch.

212–222 ↗(On Diff #342763)

Do this instead:

struct HasMinusBeginEnd {
  struct sentinel {
    friend bool operator==(sentinel, forward_iterator<int*>);
    friend constexpr long operator-(sentinel, forward_iterator<int*>) { return 2; }
    friend long operator-(forward_iterator<int*>, sentinel);
  };
  friend constexpr forward_iterator<int*> begin(HasMinusBeginEnd) { return {}; }
  friend constexpr sentinel end(HasMinusBeginEnd) { return {}; }
};

This keeps everything nicely packaged together, and also indicates (by the presence of function bodies) which functions are actually called by the test, and even (by the presence of constexpr) which functions are constexpr-called by the test.

Similarly for the other tests.

231 ↗(On Diff #342763)

Should this comment s/Int/short/ or do I not understand it? What is capital-i Int in this context?

238 ↗(On Diff #342763)

Is the l meaningful?

252–260 ↗(On Diff #342763)

This is a good test. I'd like to see a similar one where disable_sized_range is not specialized; then my understanding is that std::ranges::size(a) would be supposed to return a.size() i.e. 1, is that right?

266 ↗(On Diff #342763)

This should be std::make_unsigned_t<std::ptrdiff_t>, I believe. I don't think we should assume ptrdiff_t is invariably signed long.
Ditto throughout.
Let's test against long (or short or whatever) only when it's possible for the reader to grep back and see where that long (or short or whatever) comes from.

zoecarver added inline comments.May 4 2021, 1:36 PM
libcxx/test/std/ranges/range.access/range.prim/size.pass.cpp
212–222 ↗(On Diff #342763)

I don't want to have to define sentinel three times, so I'm going to keep it out-of-line. But I'll make the comparison operator a hidden friend.

266 ↗(On Diff #342763)
struct HasMinusBeginEnd {
  friend constexpr forward_iterator<int*> begin(HasMinusBeginEnd) { return {}; }
  friend constexpr sentinel end(HasMinusBeginEnd) { return {}; }
};

constexpr long operator-(const sentinel, const forward_iterator<int*>) { return 2; }
constexpr long operator-(const forward_iterator<int*>, const sentinel) { return 2; }

So long is hardcoded in this case (as the minus operator's return type).

266 ↗(On Diff #342763)

I don't think we should assume ptrdiff_t is invariably signed long.

If that assumption is ever made in this test, it will be caught by the windows and arm bots.

zoecarver updated this revision to Diff 342851.May 4 2021, 1:36 PM
  • Apply Arthur's comments.
ldionne accepted this revision.May 4 2021, 2:48 PM

This still LGTM.

libcxx/include/ranges
53

Synopsis!

Quuxplusone added inline comments.May 4 2021, 3:02 PM
libcxx/test/std/ranges/range.access/range.prim/size.pass.cpp
212–222 ↗(On Diff #342763)

Please put the sentinel in-line in the body of the class. Yes, three times.
This test should not rely on the fact that HasMinusBeginEnd::sentinel is the same type as RangeAccessRange::sentinel — those two types should be different. Making them members is the easiest way to ensure that. And also, readability for the maintainer.

You mention below that the unsigned long I thought was due to the difference_type` of forward_iterator is actually due to the return type of the operator- on line 221. This is exactly the kind of subtle detail that is best dealt with by keeping code close together and using member classes. Please do. If you don't, I'll have to do it in a separate followup commit, and I don't want to have to remember that.

zoecarver updated this revision to Diff 342900.May 4 2021, 4:14 PM
  • Add synopsis.
  • Apply Arthur's comment.
  • Fix the arm build.
This revision was landed with ongoing or failed builds.May 4 2021, 9:54 PM
This revision was automatically updated to reflect the committed changes.