This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implements ranges::enable_borrowed_range
ClosedPublic

Authored by Mordante on Nov 7 2020, 1:30 AM.

Details

Summary

This is the initial patch to implement ranges in libc++.

Implements parts of:

  • P0896R4 One Ranges Proposal
  • P1870 forwarding-range is too subtle
  • LWG3379 in several library names is misleading

Diff Detail

Event Timeline

Mordante created this revision.Nov 7 2020, 1:30 AM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 7 2020, 1:30 AM
Mordante requested review of this revision.Nov 7 2020, 1:30 AM

Don't forget to add the new <ranges> header to std_includes test. Otherwise no other remarks from my side.

Don't forget to add the new <ranges> header to std_includes test. Otherwise no other remarks from my side.

Thanks for the pointer. I'll update the patch shortly.

Mordante updated this revision to Diff 303635.Nov 7 2020, 5:21 AM

Added the double_include.sh.cpp test as suggested by @curdeius.
move a test from ranges/ranges to ranges/range.range.

Mordante updated this revision to Diff 303636.Nov 7 2020, 5:45 AM

Added the other steps required when adding a new header as suggested by @tschuett.

miscco added a comment.Nov 7 2020, 1:16 PM

I am wondering whether we should split the ranges header up into a smaller part that we use to include in other headers adn the rest.

Including all of ranges just for one trait seems a bit of an overkill.

We could always add it to concepts as that should be a transitive include for everything that includes range. Thoughts @ldionne?

libcxx/include/ranges
16

I am slightly surprised that concepts is not required

23

I am wondering whether it is wise to copy the synopsis as it should be rather than how it is. This might trick the user to believe all of it is supported. What are the conventions here?

libcxx/test/std/ranges/range.range/enable_borrowed_range.pass.cpp
25

I believe you are missing coverage for all the ranges that are not borrowed, e.g. vector, list, ...

tschuett added inline comments.Nov 7 2020, 10:26 PM
libcxx/include/ranges
326

Why is the curly bracket not at the end of the line above?

Mordante marked 4 inline comments as done.Nov 8 2020, 5:59 AM

I am wondering whether we should split the ranges header up into a smaller part that we use to include in other headers adn the rest.

Including all of ranges just for one trait seems a bit of an overkill.

I agree including the full ranges header in string_view and span feels a bit overkill. But I'll leave the decisions whether or not to split the header with the libc++ maintainers.

libcxx/include/ranges
16

Agreed. For this patch I don't need concepts, but std::ranges::begin() will require them.

23

Looking at other headers it does they do the same for example concepts also uses 'unspecified' and 'see below'.

326

Because that's what 'chrono' uses. However I have no objection against putting it on one line. Not sure what the libc++ coding style has to say about this.

libcxx/test/std/ranges/range.range/enable_borrowed_range.pass.cpp
25

I'm not convinced they really need to be tested, but adding them is not much effort. So I'll add them.

Mordante updated this revision to Diff 303717.Nov 8 2020, 6:23 AM
Mordante marked 4 inline comments as done.

Adds the additional unit tests as requested by @miscco.
Found some accidental tabs in the patch replaced them with spaces.

Mordante updated this revision to Diff 304252.Nov 10 2020, 10:31 AM

Change the unit tests to compile time test, based on the review comment in D91004.

I am wondering whether we should split the ranges header up into a smaller part that we use to include in other headers adn the rest.

Including all of ranges just for one trait seems a bit of an overkill.

We could always add it to concepts as that should be a transitive include for everything that includes range. Thoughts @ldionne?

I'd be fine with splitting various parts of ranges into separate headers if that makes the implementation clearer, etc.

Mordante updated this revision to Diff 307561.Nov 25 2020, 2:48 AM
Mordante edited the summary of this revision. (Show Details)

Move the enable_borrowed_range to a helper header to avoid including <ranges> in <span> and <string_view> as suggested by @miscco.

Mordante updated this revision to Diff 309287.Dec 3 2020, 9:37 AM

Implement all new header tests as suggested by @curdeius in D92214.

Mordante updated this revision to Diff 318547.Jan 22 2021, 9:14 AM
  • Removed unimplemented part of the synopsis
  • Ran clang-format on the patch
  • Rebased to trigger CI again
Mordante updated this revision to Diff 318745.Jan 23 2021, 4:13 AM

Rebase to trigger CI. The last build failed, but so did main.

cjdb added a subscriber: cjdb.Jan 25 2021, 11:50 AM
Mordante updated this revision to Diff 321466.Feb 4 2021, 8:58 AM

Rebased to trigger CI.

Mordante updated this revision to Diff 332724.Mar 23 2021, 10:47 AM

Rebased to update to main and a friendly ping.

cjdb added a comment.Mar 23 2021, 12:46 PM

Overall, LGTM, but I'm wondering if we should hold off on merging till we've got consensus on how detail headers are going to be handled.
This is only because I'm seeing __ranges_enable_helpers.

libcxx/include/ranges
16

It's transitively included by <iterator>.

libcxx/test/std/ranges/range.range/enable_borrowed_range.compile.pass.cpp
1 ↗(On Diff #332724)

Please change to enable_borrowed_range.pass.cpp (we've agreed in other patches to move away from .compile). Same with other files (this is just the first I noticed).

Quuxplusone added inline comments.
libcxx/include/module.modulemap
410

We don't do this line for any other header, e.g. __functional_base, so I don't think it should be necessary here.

Mordante updated this revision to Diff 335143.Apr 4 2021, 5:31 AM
Mordante marked an inline comment as done.

Addresses review comments, rebased on main.

Mordante added inline comments.Apr 4 2021, 5:42 AM
libcxx/include/module.modulemap
410

I looked at __string, but that seems to be the exception. So I'll remove this one.

libcxx/include/ranges
16

Agreed, but this mandated by the standard. Since the overhead is minimal I prefer to follow the standard. If in a future revision <initializer_list> no longer requires <compare> we don't silently break our implementation.

libcxx/test/std/ranges/range.range/enable_borrowed_range.compile.pass.cpp
1 ↗(On Diff #332724)

In the past had requests to rename test to use .compile. I asked for a policy on its usage on Discord, depending on the answer there I'll keep this name or rename the file.

Mordante marked an inline comment as done.Apr 7 2021, 9:38 AM
Mordante added inline comments.
libcxx/test/std/ranges/range.range/enable_borrowed_range.compile.pass.cpp
1 ↗(On Diff #332724)

As discussed on Discord we can keep compile only tests .compile. To future-proof them they shouldn't contain a main. So I'll update the .compile tests to have no main.

Mordante updated this revision to Diff 335849.Apr 7 2021, 9:49 AM

Remove main() from the compile time tests.
Rebased on main.

cjdb accepted this revision.Apr 8 2021, 10:45 AM
cjdb added inline comments.Apr 12 2021, 10:08 PM
libcxx/include/__ranges_enable_helpers
1 ↗(On Diff #335849)

Please change the path to __ranges/enable_helpers.h and move the synopsis to <ranges>.

38 ↗(On Diff #335849)

We've got a _LIBCPP_HAS_NO_RANGES macro now that guards on C++20 now.

zoecarver added inline comments.
libcxx/include/__ranges_enable_helpers
10 ↗(On Diff #335849)

I don't think we ever use triple underscore. This makes it hard to read. I think single underscore here is sufficient.

libcxx/include/module.modulemap
410

Hmm, my vote would be to export it as well. But I don't feel strongly. Do we have a policy on this @ldionne @EricWF?

libcxx/include/ranges
39

Same as the other comment, you can use _LIBCPP_HAS_NO_RANGES (in fact, let's guard the whole header on that).

41

Nit: I don't think it makes sense to have an empty namespace here.

libcxx/include/__ranges_enable_helpers
10 ↗(On Diff #335849)

Actually this is libc++ style, and has the benefit of being machine-generable (the header-inclusion test generator actually relies on their machine-generability, but only for public headers, not for these internal headers):

$ git grep '#define.*___' __*
__availability:#define _LIBCPP___AVAILABILITY
__bit_reference:#define _LIBCPP___BIT_REFERENCE
__bits:#define _LIBCPP___BITS
__errc:#define _LIBCPP___ERRC
__locale:#define _LIBCPP___LOCALE
__memory/allocator.h:#define _LIBCPP___MEMORY_ALLOCATOR_H
__memory/allocator_traits.h:#define _LIBCPP___MEMORY_ALLOCATOR_TRAITS_H
__memory/auto_ptr.h:#define _LIBCPP___MEMORY_AUTO_PTR_H
__memory/base.h:#define _LIBCPP___MEMORY_BASE_H
__memory/pointer_traits.h:#define _LIBCPP___MEMORY_POINTER_TRAITS_H
__memory/temporary_buffer.h:#define _LIBCPP___MEMORY_TEMPORARY_BUFFER_H
__memory/utilities.h:#define _LIBCPP___MEMORY_UTILITIES_H
__mutex_base:#define _LIBCPP___MUTEX_BASE
__node_handle:#define _LIBCPP___NODE_HANDLE
__sso_allocator:#define _LIBCPP___SSO_ALLOCATOR
__std_stream:#define _LIBCPP___STD_STREAM
__string:#define _LIBCPP___STRING
__tree:#define _LIBCPP___TREE
__tuple:#define _LIBCPP___TUPLE

The current exceptions-to-the-rule are

__config:#define _LIBCPP_CONFIG
__debug:#define _LIBCPP_DEBUG_H
__functional_03:#define _LIBCPP_FUNCTIONAL_03
__functional_base:#define _LIBCPP_FUNCTIONAL_BASE
__functional_base_03:#define _LIBCPP_FUNCTIONAL_BASE_03
__hash_table:#define _LIBCPP__HASH_TABLE
__nullptr:#define _LIBCPP_NULLPTR
__split_buffer:#define _LIBCPP_SPLIT_BUFFER

That said, this header name is a bit unwieldy, and vague to boot. <__enable_borrowed_range> would be strictly better. Plus, I imagine @ldionne will push for <__ranges/enable_borrowed_range.h> to match the new <__memory/*.h> regime.

If there's some reason we might want more in this header than just enable_borrowed_range, I think it's important for someone to speak up and say so now. The only other "enable helper" I'm aware of is disable_sized_range, and that can go loose in <ranges> because (unlike enable_borrowed_range) disable_sized_range is never used by anything in the library.

libcxx/test/std/containers/views/enable_borrowed_range.compile.pass.cpp
29–30 ↗(On Diff #335849)

Same thing tested twice in a row. What was meant here? Ditto twice in the lines below.

35 ↗(On Diff #335849)

Again, I recommend using something other than 1 as your "regular ordinary span" type. I suggest 10.

libcxx/test/std/language.support/support.limits/support.limits.general/ranges.version.pass.cpp
10 ↗(On Diff #335849)

When adding a new header, I strongly recommend git grep-ing for the names of some other recently added headers, e.g. <charconv> and <barrier> and <concepts>, and seeing where they're used, both in util/ and in test/.

You'll need to modify some of the generators in util/, notably the header-inclusion-test generator.

I can't think of anything else you missed off the top of my head, but grepping will always tell you.

libcxx/test/std/ranges/range.range/enable_borrowed_range.compile.pass.cpp
42 ↗(On Diff #335849)

I recommend using something like std::array<int, 10> as your "regular ordinary std::array" example (in general, not limited to this specific test). array<int, 1> seems like it might get some special cases, especially in Ranges, where there's a lot of obscure logic around the nebulous distinction between "O(1)" and "O(n)".

libcxx/include/module.modulemap
410

FYI @zoecarver, this comment has moved since I made it. We shouldn't export __ranges_enable_borrowed_range or whatever we're calling it; but of course we should export ranges! :)

Mordante marked 2 inline comments as done.Apr 14 2021, 12:15 PM
Mordante added inline comments.
libcxx/include/__ranges_enable_helpers
10 ↗(On Diff #335849)

When I originally wrote this header we weren't as keen on splitting out our headers. I originally planned to add more small helpers to the header. IIRC disable_sized_range was on the list. But I agree it would be good avoid tech debt and change the header to our current style. I used __string as example which uses triple underscore. I don't have a strong opinion on what we use as long as it's consistent.

38 ↗(On Diff #335849)

Thanks for the information, will adjust this code.

libcxx/include/ranges
39

I'll switch to the new guard.
I disagree on guarding the entire header. This is they normal way how we do things and I love consistency.
In fact guarding the entire header won't work; we need to include <__config> to define _LIBCPP_HAS_NO_RANGES.

libcxx/test/std/containers/views/enable_borrowed_range.compile.pass.cpp
29–30 ↗(On Diff #335849)

It seems I wanted to test volatile but made a typical classical copy-paste error.

40 ↗(On Diff #335849)

Dito.

zoecarver accepted this revision as: zoecarver.Apr 14 2021, 5:06 PM

Please fix the remaining few nits and land this! Thanks @Mordante! (You can accept on behalf of libc++ yourself.)

libcxx/include/__ranges_enable_helpers
10 ↗(On Diff #335849)

Good to know. In that case I'm fine with triple underscore, or whatever's appropriate for the header name we land on.

ldionne accepted this revision.Apr 15 2021, 12:10 PM

AFAICT, the only things are:

  1. Rename the header to __ranges/borrowed_range.h or similar, with the intent of having both the concept and the helper in it.
  2. Move the synopsis to <ranges>.

If I missed something else from another reviewer, please do it too, and then ship-it. No need for another round of reviews.

libcxx/include/__ranges_enable_helpers
10 ↗(On Diff #335849)

I also have no opinion on the triple underscore story - I just did it that way cause it was consistent with the name of the files, but I agree triple underscores are not super pretty. 🤷🏼‍♂️

I think we should name this __ranges/borrowed_range.h and define both the concept (in the future) and this helper in it. As an example of what kind of granularity I think is good, I don't think it makes sense to have separate headers for std::enable_borrowed_range and the std::borrowed_range concept, not sure whether that was the intent in the long term or not.

libcxx/include/string_view
619

TBH, I haven't thought yet about whether we want _LIBCPP_INLINE_VISIBILITY on such inline variables. I guess it's fine if the compilers don't complain (I would have expected GCC to complain cause it expands to __always_inline__ on it).

This revision is now accepted and ready to land.Apr 15 2021, 12:10 PM

AFAICT, the only things are:

  1. Rename the header to __ranges/borrowed_range.h or similar, with the intent of having both the concept and the helper in it.

Forget about this. I just spoke to Arthur and he explained that the very purpose of splitting the customization point into its own header was to avoid dragging all of <ranges> in the other headers. That makes total sense, I had missed that. So then I think the name of the header should just reflect what's in it, i.e. enable_borrowed_range.h or the like.

Still LGTM with that naming sorted out.

Mordante marked 13 inline comments as done.Apr 17 2021, 5:44 AM

Thanks for all the reviews. I'll give it one more CI run to see whether the renaming didn't break things. Once that passes I'll land this patch.

libcxx/include/__ranges_enable_helpers
38 ↗(On Diff #335849)

Note I still keep the _LIBCPP_STD_VER > 17 part, just like we did in <concepts>.

libcxx/include/string_view
619

This patch passed our CI so it should work with GCC. Since I still have quite some modifications to make I already wanted to give it one more CI run before landing.

libcxx/test/std/language.support/support.limits/support.limits.general/ranges.version.pass.cpp
10 ↗(On Diff #335849)

IMO if something is needed for a new header it should be documented in https://libcxx.llvm.org/docs/Contributing.html#adding-a-new-header-todo.
Thanks for catching the missing python utils/generate_header_inclusion_tests.py;. That one wasn't done since that script wasn't available when I wrote this patch.

libcxx/test/std/ranges/range.range/enable_borrowed_range.compile.pass.cpp
42 ↗(On Diff #335849)

Good suggestion, thanks!

Mordante updated this revision to Diff 338297.Apr 17 2021, 5:46 AM
Mordante marked 3 inline comments as done.

Addressed all review comments.
Rebased to main.

Mordante updated this revision to Diff 338299.Apr 17 2021, 6:07 AM

Remove __ranges/enable_borrowed_range.h from include/module.modulemap.
This seems to break the build. The recently added headers in __memory
also aren't in this file so this seems not to be required.

Mordante updated this revision to Diff 338307.Apr 17 2021, 7:27 AM

Disable ranges on Apple since it requires concepts.

Mordante updated this revision to Diff 338311.Apr 17 2021, 8:15 AM

Disable another test for Apple.

Quuxplusone accepted this revision.Apr 17 2021, 8:48 AM

LGTM % comments. I suspect we will end up removing _LIBCPP_INLINE_VISIBILITY in the place it's commented-on, but that can be done in post.

libcxx/include/span
525

Nit: I'd prefer not to see _VSTD:: here.
Could someone (presumably @ldionne) comment on whether _LIBCPP_INLINE_VISIBILITY is a good idea here? My intuitive impression is "no, it shouldn't be here"; compare how we did it in <numbers>. (But those are partial specializations expressed via C++20 constraints, whereas this is a partial specialization expressed in the old-fashioned way. I don't know if that makes a subtle difference.)

(Note that _LIBCPP_INLINE_VAR is also a thing, but I think we don't want it here (because this is post-C++14-only) and my grepping didn't turn up any more precedents for what we're doing here with partial specialization.)

libcxx/test/std/containers/views/enable_borrowed_range.compile.pass.cpp
46–52 ↗(On Diff #338311)

This test is overly complicated. Please replace the whole thing with these five lines, which test everything you've got now plus the fact that cvref-qualification matters to the specialization plus will give better error messages in the extremely unlikely case that this test ever fails.

void test() {
    static_assert(std::ranges::enable_borrowed_range<std::span<int, 0>>);
    static_assert(std::ranges::enable_borrowed_range<std::span<int, 42>>);
    static_assert(std::ranges::enable_borrowed_range<std::span<int, std::dynamic_extent>>);
    static_assert(!std::ranges::enable_borrowed_range<std::span<int, 42>&>);
    static_assert(!std::ranges::enable_borrowed_range<std::span<int, 42> const>);
}
Mordante added inline comments.Apr 17 2021, 9:45 AM
libcxx/include/span
525

@ldionne also had doubts, https://reviews.llvm.org/D90999#inline-947749. If we don't do that in <numbers> then I'll remove them before committing. The same for the _VSTD::.

Mordante marked 2 inline comments as done.Apr 18 2021, 1:14 AM
Mordante updated this revision to Diff 338360.Apr 18 2021, 1:18 AM

Addresses the final review comments.
Giving it one more CI run before landing the patch.

This revision was automatically updated to reflect the committed changes.