[libc++] Implement the underlying mechanism for range adaptors

[ldionne]

Summary

This patch implements the underlying mechanism for range adaptors. It
does so based on http://wg21.link/p2387, even though that paper hasn't
been adopted yet. In the future, if p2387 is adopted, it would suffice
to rename __bind_back to std::bind_back and __range_adaptor_closure
to std::range_adaptor_closure to implement that paper by the spec.

[• Quuxplusone]

libcxx/include/__functional/bind_back.h

2

High-level question: Why is this so complicated? All it needs to do AFAICT is just take the N arguments passed to it (for N=1 in C++20, but arguably we might see N>1 at some point), keep them in a tuple of args..., and then later take a range auto&& lhs and call the bound function __f(lhs, args...). This doesn't feel like it ought to involve such a generic name as __invoke_shuffle. Is this overengineered, or what am I missing?

libcxx/include/__ranges/range_adaptor.h

30–34

I think it's good that you picked all and transform for this PR; that's one "nullary" adaptor and one "unary" adaptor. I'm still confused how you're managing to get away with just one __range_adaptor_closure template; it intuitively feels like you should just have one __nullary_range_adaptor for things invoked as rng | x and one __unary_range_adaptor for things invoked as rng | x(a). (These are the only two types of adaptors AFAIK.)
How do you avoid making rng | views::all() well-formed?
...
Ah, I'm slowly seeing it. Your __range_adaptor_closure is something that can be piped into; so views::all IS-A __range_adaptor_closure, and views::transform has an operator() that returns a __range_adaptor_closure. But then why does views::transform itself inherit from __range_adaptor_closure? Does that make rng | views::transform (with no args) compile when it shouldn't? Why is that inheritance there?

libcxx/include/__ranges/transform_view.h

424

In all.h, we create a nested namespace views::__all, place struct __fn in there, and then define the niebloid itself in

inline namespace __cpo {
  inline constexpr auto all = __all::__fn{};
} // namespace __cpo

(all this basically to avoid unintentional ADL when views::all is passed as a function argument). If there's no technical reason to diverge here, please stick to that pattern; it'll make it easier to tell what's significant in this PR.

libcxx/include/module.modulemap

422

Naming nit: It looks like our style for implementation-detail headers is module __bind_back and __functional/__bind_back.h. Compare to __decay_copy.h below; and I've proliferated the underscored style in my [cmp.alg] patch.
(However, perfect_forward.h seems to break the pattern already.)

libcxx/test/std/ranges/range.adaptors/range.transform/adaptor.pass.cpp

53

I'd like to see an explicit test here that r | std::views::transform is not supported. E.g.

template<class T>
auto can_be_piped(T&& t) -> decltype("abcd" | static_cast<T&&>(t), std::true_type())
{
    return std::true_type();
}

std::false_type can_be_piped(...) { return std::false_type{}; }

assert( can_be_piped(std::views::all));
assert(!can_be_piped(std::views::transform));
assert( can_be_piped(std::views::transform([](char){return 1;})));

We also want a test for the (highly unfortunate) fact that auto x = std::views::transform(1) is valid. It's not pipeable, but it's valid to create such an object as long as you don't try to use it for anything meaningful. (I dunno, it might be IFNDR somehow; but GCC and MSVC accept it.)

[zoecarver]

libcxx/include/__functional/bind_back.h

2

As I mentioned in discord, I have a much simpler implementation (that still allows us to have N arguments):

template<class _Tuple, class _Idxs = typename __make_tuple_indices<tuple_size<_Tuple>::value>::type>
struct __bind_back_op;

template<class _Tuple, size_t... _Idxs>
struct __bind_back_op<_Tuple, __tuple_indices<_Idxs...>> {
    template <class _Fn, class _T2, class ..._Args>
    _LIBCPP_HIDE_FROM_ABI
    static constexpr auto __call(_Fn&& __f, _T2&& __t, _Args&& ...__args)
        noexcept(noexcept(_VSTD::invoke(_VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)..., get<_Idxs>(__t)...)))
        -> decltype(      _VSTD::invoke(_VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)..., get<_Idxs>(__t)...))
    { return              _VSTD::invoke(_VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)..., get<_Idxs>(__t)...); }
};

template <class _Fn, class ..._Args, class = _EnableIf<
    conjunction_v<
        is_constructible<decay_t<_Fn>, _Fn>,
        is_move_constructible<decay_t<_Fn>>,
        is_constructible<decay_t<_Args>, _Args>...,
        is_move_constructible<decay_t<_Args>>...
    >
>>
_LIBCPP_HIDE_FROM_ABI
constexpr auto __bind_back(_Fn&& __f, _Args&&... __args)
{
    auto __t = tuple<decay_t<_Args>...>(__args...);
    return __perfect_forward<__bind_back_op<decltype(__t)>, _Fn, tuple<decay_t<_Args>...>>(_VSTD::forward<_Fn>(__f), __t);
}

libcxx/include/__ranges/range_adaptor.h

31

Why does this need to be a template?

libcxx/include/__ranges/transform_view.h

424

Not sure if this is UB, but we can actually see this trigger a ODR violation like so:

namespace std { namespace views {

struct dummy {
  friend void transform() { }
};

}}

(If it's not UB we should definitely add those as tests.)

---

Refs (why we put all niebloids into their own inline namespace): https://stackoverflow.com/questions/50010074/why-does-range-v3-put-its-function-objects-into-an-inline-namespace and https://github.com/ericniebler/range-v3/pull/423

[zoecarver]

Anyway, beyond those mostly unrelated comments, I like this implementation a lot. Thanks for working out all the details and exploring this!

[• Quuxplusone]

libcxx/include/__functional/bind_back.h

2

Definitely seems simpler! Nits on your last three lines (IIUC):
auto __t = tuple<decay_t<_Args>...>(__args...); should be auto __t = tuple<decay_t<_Args>...>(_VSTD::forward<_Args>(__args)...);
(_VSTD::forward<_Fn>(__f), __t) should be (_VSTD::forward<_Fn>(__f), _VSTD::move(__t))
I'm not sure if get<_Idxs>(__t)... needs to be get<_Idxs>(_VSTD::forward<_T2>(__t))... in each case or not.

libcxx/include/__ranges/range_adaptor.h

31

Probably because EBO, specifically the "empty-base exclusion principle." You don't want to have multiple types A,B with the same empty base type, especially when A might have B as its first member.
( https://quuxplusone.github.io/blog/2021/05/07/std-iterator-as-a-base-class/ )

libcxx/include/__ranges/transform_view.h

424

I'm confident that the user-programmer is not allowed to add their own struct dummy into libc++'s namespace std::views. So this would be IFNDR if they tried it. (Technically the symptom wouldn't be ODR-violation but simply "transform has already been declared as a different kind of entity.")
But yeah, replace the name transform with swap and this is exactly the sort of thing the library itself needs to be able to do. Barry's top SO answer is spot-on. And I was totally wrong about this being ADL-related.

[cjdb]

There are a lot of moving parts here and it's going to take me a while to digest everything that's happening (so expect multiple rounds of commentary over a few days). I don't recall my pipe design being as complex; perhaps we should set up a 1:1 to chat about the differences between our respective designs?

libcxx/include/__functional/bind_back.h

63–68

Isn't conjunction really expensive to use and non-short circuiting?

libcxx/include/__ranges/range_adaptor.h

66

__is_range_adaptor_closure should either be renamed to remove is and replace class, or should be a constexpr bool.

74–75

Why is this an atomic copnstraint?

libcxx/test/std/ranges/range.adaptors/range.transform/types.h

10–11 ↗

(On Diff #362852)

This concept's addition and removal seems... arbitrary.

[tcanens]

Just a quick note: when P2281R1 talks about perfect forwarding call wrappers, it really means perfect forwarding call wrappers exactly as specified in the standard, that is:

A perfect forwarding call wrapper is an argument forwarding call wrapper that forwards its state entities to the underlying call expression. This forwarding step delivers a state entity of type T as cv T& when the call is performed on an lvalue of the call wrapper type and as cv T&& otherwise, where cv represents the cv-qualifiers of the call wrapper and where cv shall be neither volatile nor const volatile.

In particular, invoking an rvalue wrapper must deliver the state entity as an xvalue and cannot fall back to const lvalue the way __perfect_forward does (without deducing this, I believe that this requires additional deleted operator() overloads). This is particularly significant for split - see the examples in the paper.

[ldionne]

In D107098#2915589, @tcanens wrote:

Just a quick note: when P2281R1 talks about perfect forwarding call wrappers, it really means perfect forwarding call wrappers exactly as specified in the standard, that is:

A perfect forwarding call wrapper is an argument forwarding call wrapper that forwards its state entities to the underlying call expression. This forwarding step delivers a state entity of type T as cv T& when the call is performed on an lvalue of the call wrapper type and as cv T&& otherwise, where cv represents the cv-qualifiers of the call wrapper and where cv shall be neither volatile nor const volatile.

In particular, invoking an rvalue wrapper must deliver the state entity as an xvalue and cannot fall back to const lvalue the way __perfect_forward does (without deducing this, I believe that this requires additional deleted operator() overloads). This is particularly significant for split - see the examples in the paper.

Thanks a lot for the heads up. However, I'm not entirely sure I understand where the issue is, because what I'm seeing for __perfect_forward is this (leaving aside noexcept and -> decltype):

template<class... _Args>
constexpr auto operator()(_Args&&... __args) &&
{return _Op::__call(std::get<_Idxs>(std::move(__bound_))..., std::forward<_Args>(__args)...);}

Since we call std::get on std::move(tuple), I think we end up passing rvalue references to __call, don't we? Or did you mean something else?

In D107098#2915532, @cjdb wrote:

There are a lot of moving parts here and it's going to take me a while to digest everything that's happening (so expect multiple rounds of commentary over a few days). I don't recall my pipe design being as complex; perhaps we should set up a 1:1 to chat about the differences between our respective designs?

FWIW, if you take out the helpers, there really isn't that much going on. We basically have one CRTP base that enables piping (__range_adaptor_closure), and then one helper class that n-ary adaptors can use to create partially applied closures (__partial_range_adaptor_closure). __composed_range_adaptor_closure is "local", IOW it's only used for the composing operator|, but nobody outside of that file needs it.

That being said, I just found a way to eliminate both __partial_range_adaptor_closure and __composed_range_adaptor_closure by making something slightly more general.

libcxx/include/__functional/bind_back.h

2

@Quuxplusone

High-level question: Why is this so complicated? All it needs to do AFAICT is just take the N arguments passed to it (for N=1 in C++20, but arguably we might see N>1 at some point)

Well, I'm implementing this so that when bind_back is added, we already have it. And except for the "creating an additional tuple" trick suggested by Zoe (see tradeoffs below), I can't think of a simpler way to implement this.

@zoecarver The interesting idea here is to store the bound arguments in a tuple directly, and that indeed simplifies quite a few things. The downside is that, even after doing all the std::forwarding properly, we still end up creating an extra tuple with the bound arguments and moving it around. In other words, my implementation creates a single tuple<Function, BoundArgs...> (inside __perfect_forward and then invokes Function by shuffling the order in which BoundArgs is accessed.

Your implementation creates this: tuple<Function, tuple<BoundArgs>>. In doing so, we have an additional move-construction of a tuple, when you do this here:

return __perfect_forward<__bind_back_op<decltype(__t)>, _Fn, tuple<decay_t<_Args>...>>(_VSTD::forward<_Fn>(__f), tuple<decay_t<_Args>...>(std::forward<_Args>(__args)...));

I'm not entirely sure which one is best - more complexity or an additional move construction?

Also, side comment: I won't get rid of the __bind_back_t type, even though doing so would yield fewer lines of code. I really want to hide __perfect_forward behind an opaque type so that error messages are a bit more understandable. You'd *much* rather see an error message involving __bind_back_t<Args...> than __perfect_forward_impl<__bind_back_op<....>, Args...>.

Since I'm not sure which implementation to go with yet, I'm putting the diff between our two implementations here: https://gist.github.com/ldionne/a8ca54b04a158748ddb8a7696d701ef1. I can apply it or discard it once we've agreed on something here.

So, I think the question is: Is it acceptable to trigger an additional move-construction of the tuple that contains bound arguments? FWIW, I have extensive experience with these sorts of things from when I was working on Boost.Hana (where basically everything is tuples moving around), and I remember that at the time, we could sometimes get pretty terrible codegen when we were moving around tuples of trivial types (so imagine non-trivial types). I don't know whether that's still relevant though, it was a couple years ago.

Also, in the expression __perfect_forward<__bind_back_op<decltype(__t)>, _Fn, tuple<decay_t<_Args>...>>(_VSTD::forward<_Fn>(__f), tuple<decay_t<_Args>...>(std::forward<_Args>(__args)...)), there's nothing that mandates in-place construction of the tuple inside the __perfect_forward object, right? The C++20 rules for copy elision wouldn't have an influence on that, would it (if so, then my concern about an additional move is moot)? @Quuxplusone

63–68

conjunction is short-circuiting. We implement it with _And, which is our internal helper and is as fast as we're able to make it.

libcxx/include/__ranges/range_adaptor.h

30–34

I think it's good that you picked all and transform for this PR; that's one "nullary" adaptor and one "unary" adaptor.

Yes, that was the goal.

it intuitively feels like you should just have one __nullary_range_adaptor for things invoked as rng | x and one __unary_range_adaptor for things invoked as rng | x(a). (These are the only two types of adaptors AFAIK.)

With http://wg21.link/p2387, it is conceivable that we'd have adaptors that take more than one argument, so that's why I support those more generically. You're right, supporting only nullary or unary adaptors would have been easier (basically it doesn't require implementing a general bind_back mechanism).

How do you avoid making rng | views::all() well-formed?

views::all() is not well-formed itself. You *have* to provide at least one argument if you're going to call views::all.

But then why does views::transform itself inherit from __range_adaptor_closure?

Hmm, you're right, it shouldn't. I fixed it and added a test.

31

There's what Arthur says, and also I'm sticking closely to http://wg21.link/p2387 so that it's trivial to implement once/if it gets voted in.

66

As I explain below, __is_range_adaptor_closure started as a constexpr bool, and then I changed it to a concept per Barry's paper. I can't just call it __range_adaptor_closure since that would conflict with the class of the same name, but I'll find another name.

74–75

You're right, it shouldn't. Actually, the code started with __is_range_adaptor_closure being a constexpr bool, so then I had to do this. When I changed it to being a concept, I didn't update that code. Fixed.

libcxx/include/__ranges/transform_view.h

424

There's a lot here.

@Quuxplusone

In all.h, we create a nested namespace views::__all, place struct __fn in there, and then define the niebloid itself in [...]

We don't have other types with a friend auto all() function in them, which would clash with views::all and mandate the use of the inline namespace trick. So I don't think there is an actual reason to define it like the other CPOs, and it would be simpler and cleaner not to. I think we might just have cargo-culted niebloids a little bit. I just proposed changing how we define views::all in D107169.

If I'm misunderstanding something, please let me know in D107169. But otherwise, I think both views::transform and views::all (and all the other non-CPOs) should be defined as simply as possible, without an inline namespace.

@zoecarver

Not sure if this is UB, but we can actually see this trigger a ODR violation like so: [...]

As Arthur said, folks are not allowed to add such things in namespace std, so this can't happen.

libcxx/include/module.modulemap

422

I thought we had actually agreed on the contrary, that is we don't name headers with a leading __? I'm pretty sure we had that discussion in a prior review. We certainly follow that convention (no leading __ for several headers, like __memory/compressed_pair.h, etc.)

libcxx/test/std/ranges/range.adaptors/range.transform/types.h

10–11 ↗

(On Diff #362852)

It's a copy-paste error (@zoecarver). Those are the tests for transform_view, not drop_view, and it's not used anywhere. But actually, now that I revisit that, I think what we want instead is to rename it to ValidTransformView and test it somewhere. Done as a NFC (7b3ada712aff7254791b1c8cf905361fc478b70d).

[ldionne]

Implement most review feedback

[ldionne]

Implement views::transform as a CPO for consistency.

[tcanens]

In D107098#2916919, @ldionne wrote:

In D107098#2915589, @tcanens wrote:

Just a quick note: when P2281R1 talks about perfect forwarding call wrappers, it really means perfect forwarding call wrappers exactly as specified in the standard, that is:

A perfect forwarding call wrapper is an argument forwarding call wrapper that forwards its state entities to the underlying call expression. This forwarding step delivers a state entity of type T as cv T& when the call is performed on an lvalue of the call wrapper type and as cv T&& otherwise, where cv represents the cv-qualifiers of the call wrapper and where cv shall be neither volatile nor const volatile.

In particular, invoking an rvalue wrapper must deliver the state entity as an xvalue and cannot fall back to const lvalue the way __perfect_forward does (without deducing this, I believe that this requires additional deleted operator() overloads). This is particularly significant for split - see the examples in the paper.

Thanks a lot for the heads up. However, I'm not entirely sure I understand where the issue is, because what I'm seeing for __perfect_forward is this (leaving aside noexcept and -> decltype):

template<class... _Args>
constexpr auto operator()(_Args&&... __args) &&
{return _Op::__call(std::get<_Idxs>(std::move(__bound_))..., std::forward<_Args>(__args)...);}

Since we call std::get on std::move(tuple), I think we end up passing rvalue references to __call, don't we? Or did you mean something else?

The decltype part is important - when _Op::__call(std::get<_Idxs>(std::move(__bound_))..., std::forward<_Args>(__args)...) is ill-formed, this overload SFINAEs away, and if the const& overload is viable, that can be used, which ends up delivering lvalues.

[• Quuxplusone]

libcxx/include/__functional/bind_back.h

2

Why is this so complicated?

I didn't know this was basically implementing p2387r0 "Pipe support for user-defined range adaptors ". It would be helpful to add that paper number to the title/summary, and also elaborate in the summary on any bits that aren't quite conforming to p2387 (except of course for some double-underscores here and there because it's not standard yet).
IIUC, an argument against @zoecarver's "simpler" approach is simply that it doesn't precisely implement p2387, and we want to implement p2387? Is that an accurate assessment of the situation?

Based on my limited understanding of where p2387 actually is in the cycle, IMHO it would be very good to pull __bind_back out into its own PR and get it tested and pushed, essentially orthogonal to whatever else happens with this patch. bind_back's behavior seems pretty obvious, and thus very unlikely to change, and at least somewhat likely to get standardized into C++2b sooner or later.

@ldionne:

there's nothing that mandates in-place construction...?

Correct. If __perfect_forward<F, Args...> were an aggregate, then that syntax would mandate in-place construction (even with the parens, as of C++20); but it's not an aggregate (I checked just now against is_aggregate_v). Also, FYI, it's not trivially copyable even when Args... are trivially copyable; that kind of sucks. It'd be an ABI break to change now?

63–68

Nit: FWIW, I'd prefer _And over conjunction_v just for readability. But that was the kind of style comment I wasn't going to make except now we've started talking about it. ;)

libcxx/include/__ranges/transform_view.h

424

(This has now been adjusted to match my preference and the thread is closed AFAIC; thanks.)

libcxx/include/__utility/integer_sequence.h

97

Naming bikeshed: __integer_sequence_cat for consistency with tuple_cat?

libcxx/include/module.modulemap

422

I suppose omit-the-underscores does make it simpler for things that are expected to become standard. When __bind_back gains a bind_back facade in C++2b, we don't have to update the filename, just add ~5 lines at the bottom of the existing file.
That's a great reason to omit the underscores here. I'm ambivalent as to whether it affects e.g. __boolean_testable.h (or even __decay_copy.h now that a core-language solution to the latter is being pursued in [p0849] so the library version will probably never be standardized). Anyway, let's take this tangent to D107036.

[ldionne]

Use zoe's implementation of bind_back

[ldionne]

In D107098#2917052, @tcanens wrote:

The decltype part is important - when _Op::__call(std::get<_Idxs>(std::move(__bound_))..., std::forward<_Args>(__args)...) is ill-formed, this overload SFINAEs away, and if the const& overload is viable, that can be used, which ends up delivering lvalues.

Ooooookay, thanks to your help, I finally understood what was wrong and what the expected behavior should be. I think D107199 should resolve these issues.

@Quuxplusone

Based on my limited understanding of where p2387 actually is in the cycle, IMHO it would be very good to pull __bind_back out into its own PR and get it tested and pushed, essentially orthogonal to whatever else happens with this patch. bind_back's behavior seems pretty obvious, and thus very unlikely to change, and at least somewhat likely to get standardized into C++2b sooner or later.

I will pull it into its own PR and give it the tests it deserves. I just wanted to put the adaptor mechanism up for discussion so we can agree on how to do it, and then I'll split all the bits and pieces into separate PRs as makes sense.

libcxx/include/__functional/bind_back.h

2

It would be helpful to add that paper number to the title/summary, and also elaborate in the summary on any bits

Will do.

IIUC, an argument against @zoecarver's "simpler" approach is simply that it doesn't precisely implement p2387, and we want to implement p2387? Is that an accurate assessment of the situation?

No. The Standard doesn't mention whether we're allowed to create a temporary tuple or now. I'm confident we are. It's just about QOI. However, I think we found a solution that was both efficient and simple, see the next update.

Also, FYI, it's not trivially copyable even when Args... are trivially copyable; that kind of sucks. It'd be an ABI break to change now?

Yes, it would technically be an ABI break because we use this in not_fn. But honestly, it's probably a very very benign ABI break since most people are probably not passing that unspecified type across an ABI boundary. And if they are, they're kind of crazy. If we had a compelling way to make it trivial, I'd be open to that discussion. Unfortunately, I kind of like using std::tuple here in the implementation, and that alone prevents it from being trivially copyable.

libcxx/include/__utility/integer_sequence.h

97

This is going away!

[zoecarver]

This implementation looks good to me. It's actually pretty simple, and I don't think we can shave anything else off. I have a few suggestions:

1. Use _LIBCPP_EXPRESSION_EQUIVALENT in range_adaptors.h
2. I want to see some more tests, specifically something like what I posted for the inline namespace example.
3. And as we talked about, splitting this into separate patches would be great.

[cjdb]

libcxx/include/__ranges/range_adaptor.h

31

A heads up: I expect P2387 to undergo a few revisions before it gets to LEWG, let alone LWG, so we shouldn't marry ourselves to P2387R0.

37

I think __pipeable is a better name in this case.

46–47

46–61

I'd really like for us to make these hidden friends. It's definitely doable for range | closure, and I think it's doable for closure | closure too.

54–56

libcxx/include/__ranges/transform_view.h

404–430

There's not really a point in us doing the checks twice, but if you're wanting to do them, we should probably do them properly.

428

[cjdb]

libcxx/include/__ranges/range_adaptor.h

46–61

What am I saying? If it's possible for range | closure, of course it's possible for closure | closure :facepalm:

49

a | b; is always a bug for views and is pretty common, not only for folks who are just starting out, but also experienced users too.

58

[ldionne]

Apply most review comments and rebase onto main, which now contains __bind_back

[• Quuxplusone]

libcxx/include/__ranges/range_adaptor.h

30–34

Okay, I get it now (I think). Inheriting from __range_adaptor_closure gets you the pipe operator, but __all::__fn and __transform::__fn provide their own operator() overloads; __range_adaptor_closure doesn't say anything about operator(), just operator|.

I'd like to see a test for

static_assert(!std::is_invocable_v<decltype(std::views::all)>);  // invocable but only with one arg
static_assert(!std::is_invocable_v<decltype(std::views::transform)>);  // invocable but only with one or two args

although that might be considered a bit out of scope for this patch.

37

+1 for at least something snake-case. (I wouldn't object to __pipeable, although it doesn't capture what's going on very well IMHO.) Basically, I don't like the look of the template parameter _RangeAdaptorClosure _Closure on line 45: concepts should have snake-case names. __range_adaptor_closure _Closure would be better, but you've already gobbled up that name for the class template itself.
Alternatively, abandon the terse syntax (abandon the need for a concept representing the class template) and just write

template <ranges::viewable_range _View, class _Closure>
    requires __is_range_adaptor_closure<_Closure>

Alternatively alternatively, is @cjdb right that these could just be hidden friends of the _Closure class? I could imagine that leading to surprising ambiguities when LHS and RHS are both closure classes, so it might need some fiddling-with; but hidden friends would certainly be nice to have.

37

remove_cvref_t, not decay_t, surely? (Although if decay_t is suspected to be faster because compiler builtins, I'll acquiesce instantly.)

libcxx/test/std/ranges/range.adaptors/range.transform/adaptor.pass.cpp

43

Line 34 tests partial(v) but not transform(f)(v).
Line 44 tests v | transform(f) but not v | partial.
I suggest testing all four permutations.

libcxx/test/std/ranges/range.adaptors/range.transform/types.h

132–142 ↗

(On Diff #366721)

Is Twice non-const-callable on purpose?
Tangent: Since callables should generally be const-callable (especially stateless callables), I'd actually prefer to see Increment renamed to something like PlusOneMutable and IncrementConst renamed to just PlusOne. Give the weird name to the weird callable.
Also, if you rename to PlusOne, then Twice should become TimesTwo to match it (and return x * 2, too).

[ldionne]

Apply review comments.

libcxx/include/__ranges/range_adaptor.h

31

Yup - we're not married to it, only using the same mechanism since IMO that's the best way of doing this anyways.

37

Changed. They were using decay_t in the paper, but I agree it makes more sense to use remove_cv_t.

37

I am OK with moving the decay_t (well, uncvref_t) to the concept, however I don't think it makes sense to rename the concept to __pipeable if we keep the helper that makes piping available named __range_adaptor_closure. In other words, either we have

template <class _Tp>
struct __range_adaptor_closure { };

template <class _Tp>
concept _RangeAdaptorClosure = ...;

or we have

template <class _Tp>
struct __pipeable { };

template <class _Tp>
concept _Pipeable = ...;

Otherwise, it seems to me like we're just using inconsistent naming. I'd rather stick with _RangeAdaptorClosure for three reasons:

1. http://wg21.link/p2387 uses that naming
2. Being "pipeable" is more general than being a range adaptor closure. One could imagine a pipeable concept describing any type for which operator| is defined, but in reality _RangeAdaptorClosure describes something more narrow.
3. I think we'll get better diagnostics if we use a concept here than if we use an "opaque" __is_range_adaptor_closure constexpr bool variable template.

Alternatively, I'd be fine with naming this concept __is_range_adaptor_closure, but @cjdb didn't like having __is in a concept name (and I agree, but we've got a naming conflict to resolve so that would be an OK workaround for me).

46–61

This is what we'd end up with:

template <class _Closure>
struct __range_adaptor_closure {
    template <ranges::viewable_range _View>
    _LIBCPP_HIDE_FROM_ABI
    friend constexpr auto operator|(_View&& __view, _Closure&& __closure)
    noexcept(noexcept(_VSTD::invoke(_VSTD::move(__closure), _VSTD::forward<_View>(__view))))
    -> decltype(      _VSTD::invoke(_VSTD::move(__closure), _VSTD::forward<_View>(__view)))
    { return          _VSTD::invoke(_VSTD::move(__closure), _VSTD::forward<_View>(__view)); }

    template <ranges::viewable_range _View>
    _LIBCPP_HIDE_FROM_ABI
    friend constexpr auto operator|(_View&& __view, _Closure const& __closure)
    noexcept(noexcept(_VSTD::invoke(__closure, _VSTD::forward<_View>(__view))))
    -> decltype(      _VSTD::invoke(__closure, _VSTD::forward<_View>(__view)))
    { return          _VSTD::invoke(__closure, _VSTD::forward<_View>(__view)); }

    template <_RangeAdaptorClosure _OtherClosure>
    _LIBCPP_HIDE_FROM_ABI
    constexpr auto operator|(_Closure&& __c1, _OtherClosure&& __c2)
    noexcept(noexcept(__range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_OtherClosure>(__c2), _VSTD::move(__c1)))))
    -> decltype(      __range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_OtherClosure>(__c2), _VSTD::move(__c1))))
    { return          __range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_OtherClosure>(__c2), _VSTD::move(__c1))); }

    template <_RangeAdaptorClosure _OtherClosure>
    _LIBCPP_HIDE_FROM_ABI
    constexpr auto operator|(_Closure const& __c1, _OtherClosure&& __c2)
    noexcept(noexcept(__range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_OtherClosure>(__c2), __c1))))
    -> decltype(      __range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_OtherClosure>(__c2), __c1)))
    { return          __range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_OtherClosure>(__c2), __c1)); }
};

A few remarks:

• For range | closure, it's not clear to me that we gain much since we need two overloads. And perhaps we'd actually need more to handle _Closure& and _Closure const&&?
• For closure | closure, that simply doesn't work because that will cause an ambiguity. If we have two closures Closure1 c1 and Closure2 c2, c1 | c2 could use either the operator|(Closure1, auto) injected by __range_adaptor_closure<Closure1>, or the operator|(Closure2, auto) injected by __range_adaptor_closure<Closure2>. I don't see an easy way to solve that problem.

For those reasons, I'd be tempted to leave both as-is.

49

Isn't this valid?

std::vector<int> ints = {...};
ints | views::transform([](int i) { std::cout << i; return i + 1; }); // intentionally discard the result

Someone using transform like that would never pass my code review, but it's valid and I think it's too bold to make that ill-formed.

libcxx/include/__ranges/transform_view.h

404–430

So the reason why I added this constraint it because it's mentioned in http://eel.is/c++draft/range.adaptors#range.adaptor.object-2.

I am a bit ambivalent. I'll remove the constraint altogether, and if someone gets an error, it should mention why ranges::transform_view(...) is ill-formed.

libcxx/test/std/ranges/range.adaptors/range.transform/types.h

132–142 ↗

(On Diff #366721)

Done in 9de882fdbf7436c9ddd9b35b335ec91a524353a5.

[ldionne]

Fix issues with the modular build (thanks @cjdb for the help)

[cjdb]

Will respond to other comments when I have the time to properly mull them over.

libcxx/include/__ranges/range_adaptor.h

49

Since all views are lazy by definition, that second line is a no-op.

[• Quuxplusone]

libcxx/include/__ranges/range_adaptor.h

49

Riiight. Sneaky. :) And is that also true for the (non-standard) pipey things I see in Conor Hoekstra's talks, like hs::accumulate? E.g.

auto print_and_add = [](int a, int i) { std::cout << a; return a + i; };
ints | hs::accumulate(print_and_add); // intentionally discard the result

Of course such things are non-standard and I don't know how they'd be implemented; maybe the answer is just "Such things would be lazy, or else such things wouldn't be implemented in terms of __range_adaptor_closure."

libcxx/include/module.modulemap

642–643

These exports shouldn't be needed. (If they're needed, something is wrong with these classes. In the case of __functional_like, we traced it down to a Clang bug; is that what's wrong here too?)

[ldionne]

Address review comments about nodiscard

[ldionne]

libcxx/include/__ranges/range_adaptor.h

49

Since all views are lazy by definition, that second line is a no-op.

You're right, and the fact that I had that brainfart justifies adding [[nodiscard]] IMO.

libcxx/include/module.modulemap

642–643

Honestly, I'm not too sure because the errors are way too cryptic. However, adding them fixes issues we have in the modular build, so I think it's OK to do it, as we do elsewhere. The current state of modules makes it so that I think it's reasonable to make a few blind fixes if it resolves issues and allows us to ship patches. Once the QOI has increased, we can revisit the whole modulemap and figure out what actually needs to be there and make those changes.

[ldionne]

Try to fix the modules build

[ldionne]

Poke CI

[cjdb]

libcxx/include/__ranges/range_adaptor.h

46–50

Unless I'm mistaken, the decltypes are only there for SFINAE friendliness?

46–61

Here's a minimised version of what I have in mind. I don't think there's a lot you'll need to do to integrate it: just decorations and seeing if your existing concepts have a mapping (I couldn't see it: from what I could tell, we need both yours and mine).

57

Ditto, but you'll also need a constructible_from for this one.

libcxx/include/__ranges/transform_view.h

411

Same dealeo as above: this should be a requirement, not expression-SFINAE. Gonna leave it at three comments, I trust you to find all the rest :-)

[ldionne]

Apply review comments.

libcxx/include/__ranges/range_adaptor.h

46–50

We need to use decltype(auto) here, but indeed I added the invocable<...> requirement. It's not clear to me we need regular_invocable semantically - I don't think anything would prevent users from having a stateful function object that isn't equality preserving?

46–61

I was going to say this:

---

I don't see the benefit of using hidden friends in that way. If we have N specializations of __range_adaptor_closure, we end up injecting N function overloads like:

template<ranges::viewable_range _View, class _C2>
    requires std::same_as<std::remove_cvref_t<_C2>, __range_adaptor_closure<F1>>
constexpr auto operator|(_View&&, _C2&&);

template<ranges::viewable_range _View, class _C2>
    requires std::same_as<std::remove_cvref_t<_C2>, __range_adaptor_closure<F2>>
constexpr auto operator|(_View&&, _C2&&);

...

template<ranges::viewable_range _View, class _C2>
    requires std::same_as<std::remove_cvref_t<_C2>, __range_adaptor_closure<FN>>
constexpr auto operator|(_View&&, _C2&&);

It seems strictly simpler (and more compile-time efficient) to inject a single function template like:

template <ranges::viewable_range _View, _RangeAdaptorClosure _Closure>
constexpr auto operator|(_View&&, _Closure&&);

That way, overload resolution has a single additional candidate to consider instead of N additional candidates. Also, the error messages will show only one candidate, as opposed to the N candidates with the friend injection approach.

---

But then I reviewed how hidden friends worked again and learned that a hidden friend was only considered by overload resolution if it was in an associated namespace of one of the arguments. In other words, I thought hidden friends were injected in the enclosing namespace and from then on always considered for overload resolution, but that's not the case. TIL!

libcxx/include/__ranges/transform_view.h

411

For this one, http://eel.is/c++draft/range.adaptors#range.transform.overview-2 says it should be expression equivalent to transform_view(range, f). But you're correct in general for the other ones and I changed a bunch.

[• Quuxplusone]

libcxx/include/__ranges/range_adaptor.h

46–61

But then I reviewed how hidden friends worked again and learned that a hidden friend was only considered by overload resolution if it was in an associated namespace of one of the arguments

Yep — that's the "hidden" part of "hidden friend idiom". :) The names are "hidden" from ordinary lookup, and findable only via ADL. This generally has exactly the effect you thought was going to happen the other way around: hidden friends shrink the overload set and thus produce shorter error messages, whereas "un-hiding" things tends to grow the overload set and produce longer candidate lists in error messages.
https://quuxplusone.github.io/blog/2020/12/09/barton-nackman-in-practice/ is highly relevant. (So is a lot of the stuff in https://quuxplusone.github.io/blog/tags/#argument-dependent-lookup generally.)

[cjdb]

One change left, then I think we're ready to rock! I'm going to conditionally LGTM it on my proposed change, but please ping me on Discord if you want to discuss my proposed change (we can move back here for the actual discussion, but Discord ping > email ping in terms of responsiveness due to Phab latency).

libcxx/include/__ranges/range_adaptor.h

46–50

Let's keep it at invocable for now, and if I can come up with a proof before the branch point, we can change it then.

46–61

Great, I think we have synergy on this topic! As an aside, I'd like to write a paper proposing turning all stdlib operators as free functions into hidden friends, but that requires a lot of time that I don't have.

61–62

constructible_from<decay_t<_Closure>, _Closure> &&
constructible_from<decay_t<_OtherClosure>, _OtherClosure>

should be rewritten as

move_constructible<decay_t<_Closure>> && move_constructible<decay_t<_OtherClosure>>

but I don't think that's what we want anyway.

libcxx/include/__ranges/transform_view.h

411

I have a bad feeling about the diagnostics this is gonna produce. Hopefully I'm wrong.

[ldionne]

libcxx/include/__ranges/range_adaptor.h

61–62

Per the live call we just did, I think the current code is correct (we agreed).

libcxx/include/__ranges/transform_view.h

411

Yeah, writing expression-equivalent stuff leads to not-super-great error messages, but I still think it's the correct way to do it in this case.

libcxx/include/CMakeLists.txt

set(files
   __debug
   __errc
   __format/format_error.h
   __format/format_parse_context.h
   __function_like.h
   __functional_base
   __functional/binary_function.h
   __functional/binary_negate.h
+  __functional/bind_back.h
   __functional/bind_front.h
   __functional/bind.h
   __functional/binder1st.h
   __functional/binder2nd.h
+  __functional/compose.h
   __functional/default_searcher.h
   __functional/function.h
   __functional/hash.h
   __functional/identity.h
   __functional/invoke.h
   __functional/is_transparent.h
   __functional/mem_fn.h
   __functional/mem_fun_ref.h
set(files
   __ranges/dangling.h
   __ranges/data.h
   __ranges/drop_view.h
   __ranges/empty_view.h
   __ranges/empty.h
   __ranges/enable_borrowed_range.h
   __ranges/enable_view.h
   __ranges/non_propagating_cache.h
+  __ranges/range_adaptor.h
   __ranges/ref_view.h
-  __ranges/take_view.h
   __ranges/size.h
   __ranges/subrange.h
+  __ranges/take_view.h
   __ranges/transform_view.h
   __ranges/view_interface.h
   __split_buffer
   __std_stream
   __string
   __support/android/locale_bionic.h
   __support/fuchsia/xlocale.h
   __support/ibm/gettod_zos.h

libcxx/include/__functional/bind_back.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___FUNCTIONAL_BIND_BACK_H
+#define _LIBCPP___FUNCTIONAL_BIND_BACK_H
+
+#include <__config>
+#include <__functional/invoke.h>
+#include <__functional/perfect_forward.h>
+#include <__utility/forward.h>
+#include <__utility/integer_sequence.h>
+#include <tuple>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17
+
+// Passes the provided arguments to std::invoke in the order specified by the given index_sequence.
+template <size_t ..._Ip, class ..._Args, class _AsTuple = tuple<_Args&&...>>
+_LIBCPP_HIDE_FROM_ABI
+constexpr auto __invoke_shuffle(index_sequence<_Ip...>, _Args&& ...__args)
+    noexcept(is_nothrow_invocable_v<tuple_element_t<_Ip, _AsTuple>...>)
+    -> typename invoke_result<tuple_element_t<_Ip, _AsTuple>...>::type
+{
+    _AsTuple __as_tuple = _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...);
+    return _VSTD::invoke(_VSTD::forward<tuple_element_t<_Ip, _AsTuple>>(_VSTD::get<_Ip>(__as_tuple))...);
+}
+
+template <size_t _NBound>
+struct __bind_back_op {
+    template <class _Fn, class ..._Args,
+        size_t _NUnbound = sizeof...(_Args) - _NBound,
+        class _Sequence = __join_integer_sequences<
+            index_sequence<0>,                                                    // [0, 1) = the function object to invoke
+            __shift_index_sequence_by<_NBound+1, make_index_sequence<_NUnbound>>, // [_NBound+1, _NUnbound) = the passed arguments, which go first
+            __shift_index_sequence_by<1, make_index_sequence<_NBound>>            // [1, _NBound) = the bound arguments, which go last
+        >>
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto __call(_Fn&& __f, _Args&& ...__args)
+    noexcept(noexcept(_VSTD::__invoke_shuffle(_Sequence{}, _VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)...)))
+    -> decltype(      _VSTD::__invoke_shuffle(_Sequence{}, _VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)...))
+    { return          _VSTD::__invoke_shuffle(_Sequence{}, _VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)...); }
+};
+
+template <class _Fn, class ..._BoundArgs>
+struct __bind_back_t : __perfect_forward<__bind_back_op<sizeof...(_BoundArgs)>, _Fn, _BoundArgs...> {
+    using __perfect_forward<__bind_back_op<sizeof...(_BoundArgs)>, _Fn, _BoundArgs...>::__perfect_forward;
+};
+
+template <class _Fn, class ..._Args, class = _EnableIf<
+    conjunction_v<
+        is_constructible<decay_t<_Fn>, _Fn>,
+        is_move_constructible<decay_t<_Fn>>,
+        is_constructible<decay_t<_Args>, _Args>...,
+        is_move_constructible<decay_t<_Args>>...
+    >
+>>
+_LIBCPP_HIDE_FROM_ABI
+constexpr auto __bind_back(_Fn&& __f, _Args&&... __args)
+noexcept(noexcept(__bind_back_t<decay_t<_Fn>, decay_t<_Args>...>(_VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)...)))
+-> decltype(      __bind_back_t<decay_t<_Fn>, decay_t<_Args>...>(_VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)...))
+{ return          __bind_back_t<decay_t<_Fn>, decay_t<_Args>...>(_VSTD::forward<_Fn>(__f), _VSTD::forward<_Args>(__args)...); }
+
+#endif // _LIBCPP_STD_VER > 17
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___FUNCTIONAL_BIND_BACK_H

libcxx/include/__functional/compose.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___FUNCTIONAL_COMPOSE_H
+#define _LIBCPP___FUNCTIONAL_COMPOSE_H
+
+#include <__config>
+#include <__functional/invoke.h>
+#include <__functional/perfect_forward.h>
+#include <__utility/forward.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17
+
+struct __compose_op {
+    template<class _Fn1, class _Fn2, class ..._Args>
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto __call(_Fn1&& __f1, _Fn2&& __f2, _Args&&... __args)
+    noexcept(noexcept(_VSTD::invoke(_VSTD::forward<_Fn1>(__f1), _VSTD::invoke(_VSTD::forward<_Fn2>(__f2), _VSTD::forward<_Args>(__args)...))))
+    -> decltype(      _VSTD::invoke(_VSTD::forward<_Fn1>(__f1), _VSTD::invoke(_VSTD::forward<_Fn2>(__f2), _VSTD::forward<_Args>(__args)...)))
+    { return          _VSTD::invoke(_VSTD::forward<_Fn1>(__f1), _VSTD::invoke(_VSTD::forward<_Fn2>(__f2), _VSTD::forward<_Args>(__args)...)); }
+};
+
+template <class _Fn1, class _Fn2>
+struct __compose_t : __perfect_forward<__compose_op, _Fn1, _Fn2> {
+    using __perfect_forward<__compose_op, _Fn1, _Fn2>::__perfect_forward;
+};
+
+template <class _Fn1, class _Fn2>
+_LIBCPP_HIDE_FROM_ABI
+constexpr auto __compose(_Fn1&& __f1, _Fn2&& __f2)
+noexcept(noexcept(__compose_t<decay_t<_Fn1>, decay_t<_Fn2>>(_VSTD::forward<_Fn1>(__f1), _VSTD::forward<_Fn2>(__f2))))
+-> decltype(      __compose_t<decay_t<_Fn1>, decay_t<_Fn2>>(_VSTD::forward<_Fn1>(__f1), _VSTD::forward<_Fn2>(__f2)))
+{ return          __compose_t<decay_t<_Fn1>, decay_t<_Fn2>>(_VSTD::forward<_Fn1>(__f1), _VSTD::forward<_Fn2>(__f2)); }
+
+#endif // _LIBCPP_STD_VER > 17
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___FUNCTIONAL_COMPOSE_H

libcxx/include/__ranges/all.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #ifndef _LIBCPP___RANGES_ALL_H
 #define _LIBCPP___RANGES_ALL_H
 
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
+#include <__ranges/range_adaptor.h>
 #include <__ranges/ref_view.h>
 #include <__ranges/subrange.h>
 #include <__utility/__decay_copy.h>
 #include <__utility/declval.h>
 #include <__utility/forward.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
 namespace views {
 
 namespace __all {
-  struct __fn {
+  struct __fn : __range_adaptor_closure<__fn> {
     template<class _Tp>
       requires ranges::view<decay_t<_Tp>>
     _LIBCPP_HIDE_FROM_ABI
     constexpr auto operator()(_Tp&& __t) const
       noexcept(noexcept(_VSTD::__decay_copy(_VSTD::forward<_Tp>(__t))))
     {
       return _VSTD::forward<_Tp>(__t);
     }

libcxx/include/__ranges/range_adaptor.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___RANGES_RANGE_ADAPTOR_H
+#define _LIBCPP___RANGES_RANGE_ADAPTOR_H
+
+#include <__config>
+#include <__functional/compose.h>
+#include <__functional/invoke.h>
+#include <__ranges/concepts.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+#include <concepts>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+// CRTP base that one can derive from in order to be considered a range adaptor closure
+// by the library. That allows opting into the `operator|`s provided below.
+template <class _Tp>
+struct __range_adaptor_closure { };
+
+template <class _Tp>
+concept _RangeAdaptorClosure = derived_from<_Tp, __range_adaptor_closure<_Tp>>;
+
+// Type that wraps an arbitrary function object and makes it into a range adaptor closure,
+// i.e. something that can be called via the `x | f` notation.
+template <class _Fn>
+struct __range_adaptor_closure_t : _Fn, __range_adaptor_closure<__range_adaptor_closure_t<_Fn>> {
+    constexpr explicit __range_adaptor_closure_t(_Fn&& __f) : _Fn(_VSTD::move(__f)) { }
+};
+
+template <ranges::viewable_range _View, class _Closure>
+    requires _RangeAdaptorClosure<decay_t<_Closure>>
+_LIBCPP_HIDE_FROM_ABI
+constexpr auto operator|(_View&& __view, _Closure&& __closure)
+noexcept(noexcept(_VSTD::invoke(_VSTD::forward<_Closure>(__closure), _VSTD::forward<_View>(__view))))
+-> decltype(      _VSTD::invoke(_VSTD::forward<_Closure>(__closure), _VSTD::forward<_View>(__view)))
+{ return          _VSTD::invoke(_VSTD::forward<_Closure>(__closure), _VSTD::forward<_View>(__view)); }
+
+template <class _Closure1, class _Closure2>
+    requires _RangeAdaptorClosure<decay_t<_Closure1>> &&
+             _RangeAdaptorClosure<decay_t<_Closure2>>
+_LIBCPP_HIDE_FROM_ABI
+constexpr auto operator|(_Closure1&& __c1, _Closure2&& __c2)
+noexcept(noexcept(__range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_Closure2>(__c2), _VSTD::forward<_Closure1>(__c1)))))
+-> decltype(      __range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_Closure2>(__c2), _VSTD::forward<_Closure1>(__c1))))
+{ return          __range_adaptor_closure_t(_VSTD::__compose(_VSTD::forward<_Closure2>(__c2), _VSTD::forward<_Closure1>(__c1))); }
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___RANGES_RANGE_ADAPTOR_H

libcxx/include/__ranges/transform_view.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #ifndef _LIBCPP___RANGES_TRANSFORM_VIEW_H
 #define _LIBCPP___RANGES_TRANSFORM_VIEW_H
 
 #include <__config>
+#include <__functional/bind_back.h>
+#include <__functional/invoke.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator_traits.h>
 #include <__ranges/access.h>
 #include <__ranges/all.h>
 #include <__ranges/concepts.h>
 #include <__ranges/copyable_box.h>
 #include <__ranges/empty.h>
+#include <__ranges/range_adaptor.h>
 #include <__ranges/size.h>
 #include <__ranges/view_interface.h>
+#include <__utility/forward.h>
 #include <concepts>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
template<bool _OtherConst>
     requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
   _LIBCPP_HIDE_FROM_ABI
   friend constexpr range_difference_t<__maybe_const<_OtherConst, _View>>
   operator-(const __sentinel& __x, const __iterator<_OtherConst>& __y) {
     return __x.__end_ - __y.__current_;
   }
 };
 
 } // namespace ranges
 
+namespace views {
+namespace __transform {
+  struct __fn {
+    template<ranges::viewable_range _Range, class _Fn>
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr auto operator()(_Range&& __range, _Fn&& __f) const
+    noexcept(noexcept(ranges::transform_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Fn>(__f))))
+    -> decltype(      ranges::transform_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Fn>(__f)))
+    { return          ranges::transform_view(_VSTD::forward<_Range>(__range), _VSTD::forward<_Fn>(__f)); }
+
+    template<class _Fn>
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr auto operator()(_Fn&& __f) const
+    noexcept(noexcept(__range_adaptor_closure_t(_VSTD::__bind_back(*this, _VSTD::forward<_Fn>(__f)))))
+    -> decltype(      __range_adaptor_closure_t(_VSTD::__bind_back(*this, _VSTD::forward<_Fn>(__f))))
+    { return          __range_adaptor_closure_t(_VSTD::__bind_back(*this, _VSTD::forward<_Fn>(__f))); }
+  };
+}
+
+inline namespace __cpo {
+  inline constexpr auto transform = __transform::__fn{};
+}
+} // end namespace views
+
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___RANGES_TRANSFORM_VIEW_H

libcxx/include/__utility/integer_sequence.h

template<class _Tp, _Tp _Np>
     using make_integer_sequence = __make_integer_sequence<_Tp, _Np>;
 
 template<size_t _Np>
     using make_index_sequence = make_integer_sequence<size_t, _Np>;
 
 template<class... _Tp>
     using index_sequence_for = make_index_sequence<sizeof...(_Tp)>;
 
+
+template<class ..._Sequences>
+struct __join_integer_sequences_impl;
+
+template<class _S1>
+struct __join_integer_sequences_impl<_S1> {
+    using type = _S1;
+};
+
+template<class _Tp, _Tp ..._Ip1, _Tp ..._Ip2>
+struct __join_integer_sequences_impl<integer_sequence<_Tp, _Ip1...>, integer_sequence<_Tp, _Ip2...>> {
+    using type = integer_sequence<_Tp, _Ip1..., _Ip2...>;
+};
+
+template<class _S1, class _S2, class ..._Sn>
+struct __join_integer_sequences_impl<_S1, _S2, _Sn...>
+    : __join_integer_sequences_impl<typename __join_integer_sequences_impl<_S1, _S2>::type, _Sn...>
+{ };
+
+template<class ..._Sequences>
+using __join_integer_sequences = typename __join_integer_sequences_impl<_Sequences...>::type;
+
+template<size_t _Np, class _Sequence>
+struct __shift_index_sequence_by_impl;
+
+template<size_t _Np, size_t ..._Ips>
+struct __shift_index_sequence_by_impl<_Np, index_sequence<_Ips...>> {
+    using type = index_sequence<(_Np + _Ips)...>;
+};
+
+template<size_t _Np, class _Sequence>
+using __shift_index_sequence_by = typename __shift_index_sequence_by_impl<_Np, _Sequence>::type;
+
 #endif // _LIBCPP_STD_VER > 11
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___UTILITY_INTEGER_SEQUENCE_H

libcxx/include/functional

 
 */
 
 #include <__algorithm/search.h>
 #include <__config>
 #include <__debug>
 #include <__functional/binary_function.h> // TODO: deprecate
 #include <__functional/binary_negate.h>
+#include <__functional/bind_back.h>
 #include <__functional/bind_front.h>
 #include <__functional/bind.h>
 #include <__functional/binder1st.h>
 #include <__functional/binder2nd.h>
 #include <__functional/default_searcher.h>
 #include <__functional/function.h>
 #include <__functional/hash.h>
 #include <__functional/identity.h>

libcxx/include/module.modulemap

module std [system] {
   module functional {
     header "functional"
     export *
 
     module __functional {
       module binary_function            { private header "__functional/binary_function.h" }
       module binary_negate              { private header "__functional/binary_negate.h" }
       module bind                       { private header "__functional/bind.h" }
+      module bind_back                  { private header "__functional/bind_back.h" }
       module bind_front                 { private header "__functional/bind_front.h" }
       module binder1st                  { private header "__functional/binder1st.h" }
       module binder2nd                  { private header "__functional/binder2nd.h" }
+      module compose                    { private header "__functional/compose.h" }
       module default_searcher           { private header "__functional/default_searcher.h" }
       module function                   { private header "__functional/function.h" }
       module hash                       { private header "__functional/hash.h" }
       module identity                   { private header "__functional/identity.h" }
-      module is_transparent             { private header "__functional/is_transparent.h" }
       module invoke                     { private header "__functional/invoke.h" }
+      module is_transparent             { private header "__functional/is_transparent.h" }
       module mem_fn                     { private header "__functional/mem_fn.h"  }
       module mem_fun_ref                { private header "__functional/mem_fun_ref.h"  }
       module not_fn                     { private header "__functional/not_fn.h" }
       module operations                 { private header "__functional/operations.h" }
       module perfect_forward            { private header "__functional/perfect_forward.h" }
       module pointer_to_binary_function { private header "__functional/pointer_to_binary_function.h" }
       module pointer_to_unary_function  { private header "__functional/pointer_to_unary_function.h" }
       module ranges_operations          { private header "__functional/ranges_operations.h" }
module __ranges {
       module dangling               { private header "__ranges/dangling.h"              }
       module data                   { private header "__ranges/data.h"                  }
       module drop_view              { private header "__ranges/drop_view.h"             }
       module empty                  { private header "__ranges/empty.h"                 }
       module empty_view             { private header "__ranges/empty_view.h"            }
       module enable_borrowed_range  { private header "__ranges/enable_borrowed_range.h" }
       module enable_view            { private header "__ranges/enable_view.h"           }
       module non_propagating_cache  { private header "__ranges/non_propagating_cache.h" }
+      module range_adaptor          { private header "__ranges/range_adaptor.h"         }
       module ref_view               { private header "__ranges/ref_view.h"              }
       module size                   { private header "__ranges/size.h"                  }
       module subrange               { private header "__ranges/subrange.h"              }
       module take_view              { private header "__ranges/take_view.h"             }
       module transform_view         { private header "__ranges/transform_view.h"        }
       module view_interface         { private header "__ranges/view_interface.h"        }
     }
   }
   module ratio {
     header "ratio"
     export *
   }
   module regex {
     header "regex"
     export initializer_list
     export *

libcxx/test/libcxx/diagnostics/detail.headers/functional/bind_back.module.verify.cpp

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__functional/bind_back.h'}}
+#include <__functional/bind_back.h>

libcxx/test/libcxx/diagnostics/detail.headers/functional/compose.module.verify.cpp

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__functional/compose.h'}}
+#include <__functional/compose.h>

libcxx/test/libcxx/diagnostics/detail.headers/ranges/range_adaptor.module.verify.cpp

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__ranges/range_adaptor.h'}}
+#include <__ranges/range_adaptor.h>

libcxx/test/libcxx/utilities/function.objects/func.bind_back/bind_back.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// functional
+
+// template <class F, class... Args>
+// constexpr unspecified __bind_back(F&&, Args&&...);
+
+// This isn't part of the standard, however we use it internally and there is a
+// chance that it will be added to the standard, so we implement those tests
+// as-if it were part of the spec.
+
+#include <functional>
+#include <cassert>
+#include <tuple>
+#include <utility>
+
+struct MakeTuple {
+  template <class ...Args>
+  constexpr auto operator()(Args&& ...args) const {
+    return std::make_tuple(std::forward<Args>(args)...);
+  }
+};
+
+constexpr bool test() {
+  // Bind arguments, call without arguments
+  {
+    {
+      auto f = std::__bind_back(MakeTuple{});
+      assert(f() == std::make_tuple());
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1);
+      assert(f() == std::make_tuple(1));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1, '2');
+      assert(f() == std::make_tuple(1, '2'));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1, '2', 3.0f);
+      assert(f() == std::make_tuple(1, '2', 3.0f));
+    }
+  }
+
+  // Bind no arguments, call with arguments
+  {
+    {
+      auto f = std::__bind_back(MakeTuple{});
+      assert(f(1) == std::make_tuple(1));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{});
+      assert(f(1, '2') == std::make_tuple(1, '2'));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{});
+      assert(f(1, '2', 3.0f) == std::make_tuple(1, '2', 3.0f));
+    }
+  }
+
+  // Bind arguments, call with arguments
+  {
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1);
+      assert(f(10) == std::make_tuple(10, 1));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1, 2);
+      assert(f(10) == std::make_tuple(10, 1, 2));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1, 2, 3);
+      assert(f(10) == std::make_tuple(10, 1, 2, 3));
+    }
+
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1);
+      assert(f(10, 11) == std::make_tuple(10, 11, 1));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1, 2);
+      assert(f(10, 11) == std::make_tuple(10, 11, 1, 2));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1, 2, 3);
+      assert(f(10, 11) == std::make_tuple(10, 11, 1, 2, 3));
+    }
+
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1);
+      assert(f(10, 11, 12) == std::make_tuple(10, 11, 12, 1));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1, 2);
+      assert(f(10, 11, 12) == std::make_tuple(10, 11, 12, 1, 2));
+    }
+    {
+      auto f = std::__bind_back(MakeTuple{}, 1, 2, 3);
+      assert(f(10, 11, 12) == std::make_tuple(10, 11, 12, 1, 2, 3));
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.all/adaptor.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// std::views::all
+
+#include <ranges>
+#include <cassert>
+#include <type_traits>
+
+struct Range {
+  int* ptr_;
+  int start_;
+  int end_;
+  constexpr explicit Range(int* ptr, int start, int end) noexcept : ptr_(ptr), start_(start), end_(end) { }
+  friend constexpr int* begin(Range const& range) { return range.ptr_ + range.start_; }
+  friend constexpr int* begin(Range& range) { return range.ptr_ + range.start_; }
+  friend constexpr int* end(Range const& range) { return range.ptr_ + range.end_; }
+  friend constexpr int* end(Range& range) { return range.ptr_ + range.end_; }
+};
+
+constexpr bool test() {
+  int buff[8] = {0, 1, 2, 3, 4, 5, 6, 7};
+
+  {
+    Range range(buff, 0, 8);
+    auto result = range | std::views::all;
+    static_assert(std::is_same_v<decltype(result), std::ranges::ref_view<Range>>);
+    assert(&result.base() == &range);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/ranges/range.adaptors/range.transform/adaptor.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// std::views::transform
+
+#include <ranges>
+#include <cassert>
+#include <type_traits>
+#include <utility>
+
+#include "test_macros.h"
+#include "types.h"
+
+template <class T>
+concept CanBePiped = requires (int* buff, T&& t) {
+  { ContiguousView{buff} | std::forward<T>(t) };
+};
+
+static_assert(!CanBePiped<decltype(std::views::transform)>);
+static_assert( CanBePiped<decltype(std::views::transform(Increment{}))>);
+
+constexpr bool test() {
+  int buff[8] = {0, 1, 2, 3, 4, 5, 6, 7};
+
+  {
+    auto partial = std::views::transform(Increment{});
+    auto result = partial(ContiguousView{buff});
+    ASSERT_SAME_TYPE(decltype(result), std::ranges::transform_view<ContiguousView, Increment>);
+    assert(result.begin().base() == buff);
+    assert(result[0] == 1);
+    assert(result[1] == 2);
+    assert(result[2] == 3);
+  }
+  {
+    auto result = ContiguousView{buff} | std::views::transform(Increment{});
+    ASSERT_SAME_TYPE(decltype(result), std::ranges::transform_view<ContiguousView, Increment>);
+    assert(result.begin().base() == buff);
+    assert(result[0] == 1);
+    assert(result[1] == 2);
+    assert(result[2] == 3);
+  }
+
+  // Test that one can call std::views::transform with arbitrary stuff, as long as we
+  // don't try to actually complete the call by passing it a range.
+  //
+  // That makes no sense and we can't do anything with the result, but it's valid.
+  {
+    struct X { };
+    auto partial = std::views::transform(X{});
+    (void)partial;
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}