[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.

[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

1 ↗

(On Diff #362852)

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 ↗

(On Diff #363136)

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

431–433

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.

455

[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.

36

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

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.

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

42

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

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.

36

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

431–433

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

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

673–674

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

673–674

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

414

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

414

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

414

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

414

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.