Page MenuHomePhabricator

[libc++] Implement P0798R8 (Monadic operations for std::optional)
ClosedPublic

Authored by philnik on Nov 8 2021, 8:30 AM.

Details

Summary

Implement P0798R8

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 8 2021, 8:30 AM

Thanks for working on this! The paper looks really interesting.
I want to do a proper review later. I just noticed the modification to version while looking at my e-mail.

libcxx/include/version
356

This won't work. I just mentioned the proper way to do this in D113013.

philnik retitled this revision from Implement P0798R8 (Monadic operations for std::optional) to [libc++] Implement P0798R8 (Monadic operations for std::optional).Nov 9 2021, 5:25 AM
philnik updated this revision to Diff 385811.Nov 9 2021, 7:27 AM
philnik marked an inline comment as done.

Updated Status and added feature-test macro

Wmbat added a subscriber: Wmbat.Nov 9 2021, 9:02 AM
ldionne requested changes to this revision.Nov 9 2021, 11:25 AM
ldionne added a subscriber: ldionne.
ldionne added inline comments.
libcxx/include/optional
618

We generally don't qualify types in namespace std. So just false_type would be consistent with what we do everywhere. This applies throughout the patch.

1049

Everywhere (for consistency).

1066

Note that this qualification of _VSTD::move is good because it protects against ADL. My comment above about qualifications do not apply to cases that prevent ADL from being triggered.

1089

The paper says:

Mandates: U is a non-array object type other than in_place_t or nullopt_t.

Here we're checking that it's not an array, it's not in_place_t, and it's not nullopt_t. But we are not checking that it's an object type. For instance, if __result_type ends up being a function type or void, we won't trigger any static_assert. I'm pretty sure it's going to fail in some other way, but I still think we should check for it explicitly.

1095

This isn't what the paper is expressing. The full wording of the paper is:

Let U be remove_cv_t<invoke_result_t<F, decltype(value())>>.

Mandates: U is a non-array object type other than in_place_t or nullopt_t. The declaration U u(invoke(std::forward<F>(f), value())); is well-formed for some invented variable u. [Note: is_move_constructible_v<U> can be false. -- end note]

Returns: If *this does not contain a value, optional<U>(); otherwise, an optional<U> object whose contained value is initialized as if direct-non-list-initializing an object of type U with invoke(std::forward<F>(f), value()).

What they mean in the Returns: section is that the object inside the optional should be direct-non-list-initialized as-if one had used U u(invoke(std::forward<F>(f), value())); exactly. Combined with the note that U doesn't have to be move-constructible, I am fairly convinced they are telling us to allow move-elision, like what I did in D107932. At the end of the day, I suspect this will have to look something like

optional<__result_type>(__construct_from_invoke_tag{}, _VSTD::forward<_Func>(__f), value());

where there's a special optional constructor that looks like

template<class _Fp, class ..._Args>
constexpr explicit optional(__construct_from_invoke_tag, _Fp&& __f, _Args&& ...__args) 
  : __value_(_VSTD::invoke(_VSTD::forward<_Fp>(__f), _VSTD::forward<_Args>(__args)...)))
{ }

This is of course going to be more complicated due to inheritance and stuff, but you get the idea. Here, at least, we allow move elision to occur.

Also, please add tests for all the methods that have this Note: where __result_type is not move-constructible. Those should fail with your current implementation and they should start working once you implement something like what I just laid out.

libcxx/test/std/utilities/optional/optional.monadic/or_else.pass.cpp
2

Please add tests for SFINAE friendliness when the Constraints: are not met.

This revision now requires changes to proceed.Nov 9 2021, 11:25 AM
Quuxplusone requested changes to this revision.Nov 9 2021, 1:17 PM
Quuxplusone added a subscriber: Quuxplusone.

Looks pretty good to me so far!

libcxx/include/optional
621

I suggest __is_std_optional for consistency with __is_std_{span,array}. I also think there's no need for the __is_optional_v variable template (again for consistency).

(Or, if you absolutely want the variable template for efficiency — which you shouldn't — then I'd say to get rid of the struct template and just specialize the variable template directly.)

1055

Style nit: The Standard calls this U, and I think we should call it _Up. __lower_snake_case looks too much like a local variable to me (and is also verboser than needed). (Alternatively, _Rp; but I think it makes sense to follow the Standard's U.)

1116

Here decltype(std::move(value())) is just _Tp&& (and ditto throughout, with cvref-qualification differences). IMO the shorter _Tp&& form should be used for clarity.
Also, I'm like 95% sure that invoke_result_t<_Func, _Tp&&> is just invoke_result_t<_Func, _Tp> (because it all boils down to declval stuff in the end, and declval can't distinguish xvalues from prvalues).

libcxx/test/std/utilities/optional/optional.monadic/and_then.pass.cpp
2

For each of the new methods, I'd like to see one simple test case each sanity-checking that

  • f is not gratuitously copied (it might not even be copyable)
  • f's operator() is called with the correct constness and ref-qualification (e.g. operator()(int) & vs operator()(int) const&&)
  • The argument to f is passed with the correct value category (e.g. operator()(int&) const vs operator()(int&&) const)
  • The argument to f (that is, value()) is not gratuitously copied (it might not even be copyable)
33

static_cast<const std::optional<int>&>(opt) could be std::as_const(opt). However, that still doesn't help with the const&& cast, so maybe you just want to introduce a const version right at the top of the function?

std::optional<int> o;
const std::optional<int>& co = o;
auto never_called = [](int) { assert(false); return std::optional<long>(); };
o.and_then(never_called);
co.and_then(never_called);
std::move(o).and_then(never_called);
std::move(co).and_then(never_called);

o = 1;
assert(...
philnik updated this revision to Diff 387080.Nov 14 2021, 6:39 AM
philnik marked 9 inline comments as done.

Updated tests and implemented transform() correctly

libcxx/test/std/utilities/optional/optional.monadic/or_else.pass.cpp
2

Could you reference something where that is done? I have no idea what you are asking for.

libcxx/test/std/utilities/optional/optional.monadic/or_else.pass.cpp
2

Something like libcxx/test/std/utilities/tuple/tuple.tuple/tuple.helper/tuple_size_value_sfinae.pass.cpp. Basically:

#include "MoveOnly.h"

struct NonMovable {
    NonMovable() = default;
    NonMovable(NonMovable&&) = delete;
};

// TODO: rewrite to use 'requires' when _LIBCPP_HAS_NO_CONCEPTS goes away
template<class O, class F>
auto has_or_else(int, O&& o, F&& f)
    -> decltype(static_cast<O&&>(o).or_else(static_cast<F&&>(f)), true)
    { return true; }

template<class O, class F>
bool has_or_else(long, O&& o, F&& f)
    { return false; }

void test_sfinae() {
    std::optional<int> o1;
    std::optional<MoveOnly> o2;
    std::optional<NonMovable> o3;
    assert( has_or_else(0, o1, [&](){ return std::optional<int>(); }));
    assert( has_or_else(0, std::move(o1), [&](){ return std::optional<int>(); }));
    assert(!has_or_else(0, o2, [&](){ return std::optional<MoveOnly>(); }));
    assert( has_or_else(0, std::move(o2), [&](){ return std::optional<MoveOnly>(); }));
    assert(!has_or_else(0, o3, [&](){ return std::optional<NonMovable>(); }));
    assert(!has_or_else(0, std::move(o3), [&](){ return std::optional<NonMovable>(); }));

    assert(!has_or_else(0, o1, [&](int){ return std::optional<int>(); }));
    assert(!has_or_else(0, o1, [&](int){}));
    assert(!has_or_else(0, o1, 42));
}
tcanens added inline comments.
libcxx/include/optional
1088

This should be remove_cv_t. Ditto for other instances of transform.

1095

This isn't what the paper is expressing. The full wording of the paper is:

Let U be remove_cv_t<invoke_result_t<F, decltype(value())>>.

Mandates: U is a non-array object type other than in_place_t or nullopt_t. The declaration U u(invoke(std::forward<F>(f), value())); is well-formed for some invented variable u. [Note: is_move_constructible_v<U> can be false. -- end note]

Returns: If *this does not contain a value, optional<U>(); otherwise, an optional<U> object whose contained value is initialized as if direct-non-list-initializing an object of type U with invoke(std::forward<F>(f), value()).

What they mean in the Returns: section is that the object inside the optional should be direct-non-list-initialized as-if one had used U u(invoke(std::forward<F>(f), value())); exactly. Combined with the note that U doesn't have to be move-constructible, I am fairly convinced they are telling us to allow move-elision, like what I did in D107932. At the end of the day, I suspect this will have to look something like

optional<__result_type>(__construct_from_invoke_tag{}, _VSTD::forward<_Func>(__f), value());

where there's a special optional constructor that looks like

template<class _Fp, class ..._Args>
constexpr explicit optional(__construct_from_invoke_tag, _Fp&& __f, _Args&& ...__args) 
  : __value_(_VSTD::invoke(_VSTD::forward<_Fp>(__f), _VSTD::forward<_Args>(__args)...)))
{ }

This is of course going to be more complicated due to inheritance and stuff, but you get the idea. Here, at least, we allow move elision to occur.

Also, please add tests for all the methods that have this Note: where __result_type is not move-constructible. Those should fail with your current implementation and they should start working once you implement something like what I just laid out.

1149

Not just an optional - it needs to be this particular specialization of optional.

libcxx/test/std/utilities/optional/optional.monadic/and_then.pass.cpp
9

For the ones returning auto, I'd suggest a test using a SFINAE-unfriendly generic lambda to verify that they don't try to instantiate its body during overload resolution. See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0798r8.html#sfinae-friendliness

libcxx/test/std/utilities/optional/optional.monadic/transform.pass.cpp
130

This seems to be missing a test where the transform function actually returns something immovable.

tcanens added inline comments.Nov 14 2021, 3:37 PM
libcxx/include/optional
1095

I thought I dropped this one... anyway, I wrote this wording and yes, that's the intent.

philnik updated this revision to Diff 387179.Nov 15 2021, 2:00 AM
philnik marked 6 inline comments as done.

Added sfinae tests and changed remove_cvfet_t to remove_cv_t

philnik marked an inline comment as done.Nov 15 2021, 2:01 AM
philnik updated this revision to Diff 387209.Nov 15 2021, 4:16 AM

Moved constructor

ldionne requested changes to this revision.Nov 22 2021, 9:50 AM
ldionne added inline comments.
libcxx/test/std/utilities/optional/optional.monadic/and_then.pass.cpp
87–103

I find this somewhat hard to follow. Instead, I'd have an easier time if things were grouped by the method overload you are testing:

constexpr void test_val_types() {
  // Test & overload
  {
    // Without & qualifier on F's operator()
    {
      std::optional<int> i{};
      i.and_then(LVal{});
    }

    // With & qualifier on F's operator()
    {
      std::optional<int> i{};
      RefQual l{};
      i.and_then(l);
    }
  }

  // Test const& overload
  {
    // Without & qualifier on F's operator()
    {
      std::optional<int> const i{};
      ci.and_then(CLVal{});
    }

    // With & qualifier on F's operator()
    {
        std::optional<int> const i{};
        const CRefQual cl{};
        ci.and_then(cl);
    }
  }

  // etc...
}

This applies everywhere else AFAICT. This is more verbose, however at the end of the day it's way easier to follow and see the pattern in the tests.

Other things that apply to all tests AFAICT:

  • We are not testing the return type and return values of the functions.
  • We are not testing with a F that returns an empty optional. Above, your LVal & friends always return an engaged optional.
  • We are not exhaustively testing with a i that is engaged and non-engaged. Above, you only test with a disengaged optional.
105–110

This needs a comment explaining what it's testing. test_sfinae isn't very descriptive, I'm staring at this and it's not immediately obvious to me what you're trying to test SFINAE for.

This revision now requires changes to proceed.Nov 22 2021, 9:50 AM
philnik updated this revision to Diff 392035.Dec 6 2021, 5:48 AM
philnik marked 2 inline comments as done.
  • rebased
  • Updated tests
ldionne requested changes to this revision.Dec 8 2021, 2:05 PM

Almost LGTM, thanks for working on this!

libcxx/include/optional
135–145
614

I think it is fine to unconditionally define this template. We'll only be using it in C++20, but I don't think it's worth the complexity to add the #if.

1056

The spec says:

Let U be invoke_result_t<F, decltype(std::move(value()))>.
Mandates: remove_cvref_t<U> is a specialization of optional.

I think we should be checking this instead:

static_assert(__is_std_optional<remove_cvref_t<_Up>>::value, ...);

This comment probably applies elsewhere.

libcxx/test/std/utilities/optional/optional.monadic/or_else.pass.cpp
26–33

I believe this would work and be equivalent:

template <class Opt, class F>
concept has_or_else = requires(Opt&& opt, F&& f) {
  { std::forward<Opt>(opt).or_else(std::forward<F>(f)) };
};
This revision now requires changes to proceed.Dec 8 2021, 2:05 PM
philnik updated this revision to Diff 392945.Dec 8 2021, 3:06 PM
philnik marked 4 inline comments as done.
  • rebased
  • Addressed ldionne's comments
philnik updated this revision to Diff 392975.Dec 8 2021, 4:30 PM
  • Removed lambdas from unevaluated contexts
ldionne accepted this revision.Dec 9 2021, 10:18 AM
Quuxplusone accepted this revision.Dec 15 2021, 11:37 AM

I suspect it may be important to add some tests involving optional<optional<int>> just to make sure we strip (or don't strip) the right number of levels of optional. (This is one of the pernicious cases for CTAD, where the expression std::optional(e) changes meaning depending on the type of e.) However, please don't block this PR over that; just consider whether you agree, and then make a followup PR with some additional tests if you think it's important enough to test. (I'm also willing to believe it's not so important, if that's what you think.)

libcxx/include/optional
256–257

Nit: match {} brace style from lines 244 and 250. (Ditto line 299.)

1057

I wonder if this should say a specialization of std::optional, without the T, for pedantic correctness. This can totally be done post-commit, though, if we want to, rather than holding up this PR waiting for a round-trip to see if @ldionne agrees or whatever. :)

1149

Please make this Result of f() should be the same type as this optional — note the addition of "type." It might not be "the same (object)" in the same sense as operator='s return type must be "the same as this optional." Adding type makes that unambiguous, and it's cheap to do.
Ditto line 1161.

This revision is now accepted and ready to land.Dec 15 2021, 11:37 AM
ldionne added inline comments.Dec 15 2021, 11:38 AM
libcxx/include/optional
1057

Yeah, I agree, let's reword the warning.

philnik updated this revision to Diff 394628.Dec 15 2021, 11:56 AM
philnik marked 3 inline comments as done.
  • Updated brace style
  • Updated error messages