libstdc++: Implement monadic operations for std::optional (P0798R8)

Another new addition to the C++23 working draft.

The new member functions of std::optional are only defined for C++23,
but the new members of _Optional_payload_base are defined for C++20 so
that they can be used in non-propagating-cache in <ranges>. The
_Optional_payload_base::_M_construct member can also be used in
non-propagating-cache now, because it's constexpr since r12-4389.

There will be an LWG issue about the feature test macro, suggesting that
we should just bump the value of __cpp_lib_optional instead. I haven't
done that here, but it can be changed once consensus is reached on the
change.

libstdc++-v3/ChangeLog:

	* include/std/optional (_Optional_payload_base::_Storage): Add
	constructor taking a callable function to invoke.
	(_Optional_payload_base::_M_apply): New function.
	(__cpp_lib_monadic_optional): Define for C++23.
	(optional::and_then, optional::transform, optional::or_else):
	Define for C++23.
	* include/std/ranges (__detail::__cached): Remove.
	(__detail::__non_propagating_cache): Remove use of __cached for
	contained value. Use _Optional_payload_base::_M_construct and
	_Optional_payload_base::_M_apply to set the contained value.
	* include/std/version (__cpp_lib_monadic_optional): Define.
	* testsuite/20_util/optional/monadic/and_then.cc: New test.
	* testsuite/20_util/optional/monadic/or_else.cc: New test.
	* testsuite/20_util/optional/monadic/or_else_neg.cc: New test.
	* testsuite/20_util/optional/monadic/transform.cc: New test.
	* testsuite/20_util/optional/monadic/version.cc: New test.

3 files changed, 187 insertions, 40 deletions

diff --git a/libstdc++-v3/include/std/optional b/libstdc++-v3/include/std/optional
index b69268b..eac91d3 100644
--- a/libstdc++-v3/include/std/optional
+++ b/libstdc++-v3/include/std/optional
@@ -1,6 +1,7 @@
 // <optional> -*- C++ -*-
 
 // Copyright (C) 2013-2021 Free Software Foundation, Inc.
+// Copyright The GNU Toolchain Authors.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
@@ -44,6 +45,10 @@
 #include <bits/utility.h> // in_place_t
 #if __cplusplus > 201703L
 # include <compare>
+# include <bits/invoke.h> // std::__invoke
+#endif
+#if __cplusplus > 202002L
+# include <concepts>
 #endif
 
 namespace std _GLIBCXX_VISIBILITY(default)
@@ -81,6 +86,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /// Tag to disengage optional objects.
   inline constexpr nullopt_t nullopt { nullopt_t::_Construct::_Token };
 
+  template<typename _Fn> struct _Optional_func { _Fn& _M_f; };
+
   /**
    *  @brief Exception class thrown when a disengaged optional object is
    *  dereferenced.
@@ -211,6 +218,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    : _M_value(__il, std::forward<_Args>(__args)...)
 	    { }
 
+#if __cplusplus >= 202002L
+	  template<typename _Fn, typename _Arg>
+	    constexpr
+	    _Storage(_Optional_func<_Fn> __f, _Arg&& __arg)
+	    : _M_value(std::__invoke(std::forward<_Fn>(__f._M_f),
+				     std::forward<_Arg>(__arg)))
+	    { }
+#endif
+
 	  _Empty_byte _M_empty;
 	  _Up _M_value;
 	};
@@ -232,6 +248,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    : _M_value(__il, std::forward<_Args>(__args)...)
 	    { }
 
+#if __cplusplus >= 202002L
+	  template<typename _Fn, typename _Arg>
+	    constexpr
+	    _Storage(_Optional_func<_Fn> __f, _Arg&& __arg)
+	    : _M_value(std::__invoke(std::forward<_Fn>(__f._M_f),
+				     std::forward<_Arg>(__arg)))
+	    { }
+#endif
+
 	  // User-provided destructor is needed when _Up has non-trivial dtor.
 	  _GLIBCXX20_CONSTEXPR ~_Storage() { }
 
@@ -260,6 +285,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_payload._M_value.~_Stored_type();
       }
 
+#if __cplusplus >= 202002L
+      template<typename _Fn, typename _Up>
+	constexpr void
+	_M_apply(_Optional_func<_Fn> __f, _Up&& __x)
+	{
+	  std::construct_at(std::__addressof(this->_M_payload),
+			    __f, std::forward<_Up>(__x));
+	  _M_engaged = true;
+	}
+#endif
+
       // The _M_get() operations have _M_engaged as a precondition.
       // They exist to access the contained value with the appropriate
       // const-qualification, because _M_payload has had the const removed.
@@ -637,6 +673,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _Tp>
   class optional;
 
+  template<typename _Tp>
+    inline constexpr bool __is_optional_v = false;
+  template<typename _Tp>
+    inline constexpr bool __is_optional_v<optional<_Tp>> = true;
+
   template<typename _Tp, typename _Up>
     using __converts_from_optional =
       __or_<is_constructible<_Tp, const optional<_Up>&>,
@@ -1002,7 +1043,143 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    return static_cast<_Tp>(std::forward<_Up>(__u));
 	}
 
+#if __cplusplus > 202002L && __cpp_lib_concepts
+#define __cpp_lib_monadic_optional 202110L
+
+      // [optional.monadic]
+
+      template<typename _Fn> requires invocable<_Fn, _Tp&>
+	constexpr auto
+	and_then(_Fn&& __f) &
+	{
+	  using _Up = remove_cvref_t<invoke_result_t<_Fn, _Tp&>>;
+	  static_assert(__is_optional_v<remove_cvref_t<_Up>>);
+	  if (has_value())
+	    return std::__invoke(std::forward<_Fn>(__f), **this);
+	  else
+	    return _Up();
+	}
+
+      template<typename _Fn> requires invocable<_Fn, const _Tp&>
+	constexpr auto
+	and_then(_Fn&& __f) const &
+	{
+	  using _Up = remove_cvref_t<invoke_result_t<_Fn, const _Tp&>>;
+	  static_assert(__is_optional_v<_Up>);
+	  if (has_value())
+	    return std::__invoke(std::forward<_Fn>(__f), **this);
+	  else
+	    return _Up();
+	}
+
+      template<typename _Fn> requires invocable<_Fn, _Tp>
+	constexpr auto
+	and_then(_Fn&& __f) &&
+	{
+	  using _Up = remove_cvref_t<invoke_result_t<_Fn, _Tp>>;
+	  static_assert(__is_optional_v<remove_cvref_t<_Up>>);
+	  if (has_value())
+	    return std::__invoke(std::forward<_Fn>(__f), std::move(**this));
+	  else
+	    return _Up();
+	}
+
+      template<typename _Fn> requires invocable<_Fn, const _Tp>
+	constexpr auto
+	and_then(_Fn&& __f) const &&
+	{
+	  using _Up = remove_cvref_t<invoke_result_t<_Fn, const _Tp>>;
+	  static_assert(__is_optional_v<remove_cvref_t<_Up>>);
+	  if (has_value())
+	    return std::__invoke(std::forward<_Fn>(__f), std::move(**this));
+	  else
+	    return _Up();
+	}
+
+      template<typename _Fn> requires invocable<_Fn, _Tp&>
+	constexpr auto
+	transform(_Fn&& __f) &
+	{
+	  using _Up = invoke_result_t<_Fn, _Tp&>;
+	  if (has_value())
+	    return optional<_Up>(_Optional_func<_Fn>{__f}, **this);
+	  else
+	    return optional<_Up>();
+	}
+
+      template<typename _Fn> requires invocable<_Fn, const _Tp&>
+	constexpr auto
+	transform(_Fn&& __f) const &
+	{
+	  using _Up = invoke_result_t<_Fn, const _Tp&>;
+	  if (has_value())
+	    return optional<_Up>(_Optional_func<_Fn>{__f}, **this);
+	  else
+	    return optional<_Up>();
+	}
+
+      template<typename _Fn> requires invocable<_Fn, _Tp>
+	constexpr auto
+	transform(_Fn&& __f) &&
+	{
+	  using _Up = invoke_result_t<_Fn, _Tp>;
+	  if (has_value())
+	    return optional<_Up>(_Optional_func<_Fn>{__f}, std::move(**this));
+	  else
+	    return optional<_Up>();
+	}
+
+      template<typename _Fn> requires invocable<_Fn, const _Tp>
+	constexpr auto
+	transform(_Fn&& __f) const &&
+	{
+	  using _Up = invoke_result_t<_Fn, const _Tp>;
+	  if (has_value())
+	    return optional<_Up>(_Optional_func<_Fn>{__f}, std::move(**this));
+	  else
+	    return optional<_Up>();
+	}
+
+      template<typename _Fn> requires invocable<_Fn> && copy_constructible<_Tp>
+	constexpr optional
+	or_else(_Fn&& __f) const&
+	{
+	  using _Up = invoke_result_t<_Fn>;
+	  static_assert( is_same_v<remove_cvref_t<_Up>, optional> );
+
+	  if (has_value())
+	    return *this;
+	  else
+	    return std::forward<_Fn>(__f)();
+	}
+
+      template<typename _Fn> requires invocable<_Fn> && move_constructible<_Tp>
+	constexpr optional
+	or_else(_Fn&& __f) &&
+	{
+	  using _Up = invoke_result_t<_Fn>;
+	  static_assert( is_same_v<remove_cvref_t<_Up>, optional> );
+
+	  if (has_value())
+	    return std::move(*this);
+	  else
+	    return std::forward<_Fn>(__f)();
+	}
+#endif
+
       _GLIBCXX20_CONSTEXPR void reset() noexcept { this->_M_reset(); }
+
+    private:
+#if __cplusplus >= 202002L
+      template<typename _Up> friend class optional;
+
+      template<typename _Fn, typename _Value>
+	explicit constexpr
+	optional(_Optional_func<_Fn> __f, _Value&& __v)
+	{
+	  this->_M_payload._M_apply(__f, std::forward<_Value>(__v));
+	}
+#endif
     };
 
   template<typename _Tp>
@@ -1241,11 +1418,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     { return !__rhs || __lhs >= *__rhs; }
 
 #ifdef __cpp_lib_three_way_comparison
-  template<typename _Tp>
-    inline constexpr bool __is_optional_v = false;
-  template<typename _Tp>
-    inline constexpr bool __is_optional_v<optional<_Tp>> = true;
-
   template<typename _Tp, typename _Up>
     requires (!__is_optional_v<_Up>)
       && three_way_comparable_with<_Tp, _Up>
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index b8de400..18bd087 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -1160,33 +1160,9 @@ namespace views::__adaptor
       };
 
     template<typename _Tp>
-      struct __cached
-      {
-	struct _Deref_t { };
-	static constexpr _Deref_t __deref{};
-
-	// Initialize _M_t directly from the result of dereferencing __i.
-	// This avoids any unwanted temporary materialization that would
-	// occur if *__i was bound to a reference before initializing _M_t.
-	template<typename _Iter>
-	  constexpr explicit
-	  __cached(_Deref_t, _Iter&& __i)
-	  : _M_t(*__i)
-	  { }
-
-	template<typename... _Args>
-	  constexpr explicit
-	  __cached(_Args&&... __args)
-	  : _M_t(std::forward<_Args>(__args)...)
-	  { }
-
-	_Tp _M_t;
-      };
-
-    template<typename _Tp>
       requires is_object_v<_Tp>
       struct __non_propagating_cache<_Tp>
-      : protected _Optional_base<__cached<_Tp>>
+      : protected _Optional_base<_Tp>
       {
 	__non_propagating_cache() = default;
 
@@ -1218,9 +1194,7 @@ namespace views::__adaptor
 	operator=(_Tp __val)
 	{
 	  this->_M_reset();
-	  std::construct_at(std::__addressof(this->_M_payload._M_payload),
-			    std::in_place, std::move(__val));
-	  this->_M_payload._M_engaged = true;
+	  this->_M_payload._M_construct(std::move(__val));
 	  return *this;
 	}
 
@@ -1230,22 +1204,20 @@ namespace views::__adaptor
 
 	constexpr _Tp&
 	operator*() noexcept
-	{ return this->_M_get()._M_t; }
+	{ return this->_M_get(); }
 
 	constexpr const _Tp&
 	operator*() const noexcept
-	{ return this->_M_get()._M_t; }
+	{ return this->_M_get(); }
 
 	template<typename _Iter>
 	  constexpr _Tp&
 	  _M_emplace_deref(const _Iter& __i)
 	  {
 	    this->_M_reset();
-	    // Use the special constructor of __cached<_Tp> that does *__i.
-	    std::construct_at(std::__addressof(this->_M_payload._M_payload),
-			      std::in_place, __cached<_Tp>::__deref, __i);
-	    this->_M_payload._M_engaged = true;
-	    return **this;
+	    auto __f = [] (auto& __x) { return *__x; };
+	    this->_M_payload._M_apply(_Optional_func{__f}, __i);
+	    return this->_M_get();
 	  }
       };
 
diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version
index 2b11830..0a7b28a 100644
--- a/libstdc++-v3/include/std/version
+++ b/libstdc++-v3/include/std/version
@@ -292,6 +292,9 @@
 #define __cpp_lib_adaptor_iterator_pair_constructor 202106L
 #define __cpp_lib_invoke_r 202106L
 #define __cpp_lib_is_scoped_enum 202011L
+#if __cpp_lib_concepts
+# define __cpp_lib_monadic_optional 202110L
+#endif
 #define __cpp_lib_move_only_function 202110L
 #define __cpp_lib_string_contains 202011L
 #if _GLIBCXX_USE_CXX11_ABI // Only supported with cxx11-abi