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.
Details
- Reviewers
zoecarver cjdb - Group Reviewers
Restricted Project - Commits
- rGee44dd8062a2: [libc++] Implement the underlying mechanism for range adaptors
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
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.
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) |
Will do.
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.
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! |
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:
- Use _LIBCPP_EXPRESSION_EQUIVALENT in range_adaptors.h
- I want to see some more tests, specifically something like what I posted for the inline namespace example.
- And as we talked about, splitting this into separate patches would be great.
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 |
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. 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). | |
libcxx/test/std/ranges/range.adaptors/range.transform/types.h | ||
132–142 | Is Twice non-const-callable on purpose? |
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:
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 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 |
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. |
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?) |
libcxx/include/__ranges/range_adaptor.h | ||
---|---|---|
49 |
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. |
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 :-) |
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. |
libcxx/include/__ranges/range_adaptor.h | ||
---|---|---|
46–61 |
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. |
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. |
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. |