This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[v3 PATCH, RFC] Rewrite variant. Also PR libstdc++/85517
- From: Ville Voutilainen <ville dot voutilainen at gmail dot com>
- To: "libstdc++" <libstdc++ at gcc dot gnu dot org>, gcc-patches List <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 6 Feb 2019 00:05:01 +0200
- Subject: [v3 PATCH, RFC] Rewrite variant. Also PR libstdc++/85517
Okay then. This patch takes the hopefully biggest steps towards
a std::variant rewrite. The problem we have with the current
approach is that we'd really like to write fairly straightforward
code for variant's special member functions, but can't, because
the specification suggests fairly straightforward compile-time-property
queries and selection of behavior based on those, but variant's selected
index is a run-time property. This leads to difficulties implementing
what the standard requires, like the differences of handling throwing and
non-throwing move/copy operations of the types held in variant.
Well. We apply the hammer of Pattern Matching. variant's visit()
can get us into code that can do the compile-time queries despite
variant's selected index being a run-time property. We modify
the visitation mechanism to not throw an exception if invoked
with a special kind of visitor that can handle valueless variants,
and then use polylambdas as such visitors, and do if-constexprs
in those polylambdas.
We can now get rid of the function-pointer tables that are used for
similar kind of dispatching in the original approach. Visitation
generates similar tables, so we keep the O(1) indexing into the right
function based on the current selected index, and there's the same
amount of indirect calls through a pointer-to-function, one.
Our code for e.g. variant's copy assignment is now straightforward;
it visits both the this-variant and the rhs-variant at the same time,
and does the right thing based on the compile-time properties of the
selected type,
and whether either variant is valueless. Modulo the polylambda wrapping
and the fact that all ifs in it are if-constexprs, it looks like it's just
doing conditional code based on what the nothrow-properties, for example,
of the type of the object held by the variant are.
This patch also partially gets rid of some of the cases where an object
is self-destroyed before it's reconstructed. We shouldn't do that.
We should be doing _M_reset followed by _M_construct, so that we only
ever destroy a variant member of a union object held in the variant's
storage, and then try to reconstruct that (or some other variant member),
and we should never self-destroy any object in the inheritance chain of
variant. The rest of that is work-in-progress, as is changing the rest
of the special member functions to use visitation.
Thoughts?
2019-02-05 Ville Voutilainen <ville.voutilainen@gmail.com>
Rewrite variant.
Also PR libstdc++/85517
* include/std/variant (__do_visit): New.
(__variant_cast): Likewise.
(__variant_cookie): Likewise.
(__erased_dtor): Remove.
(_Variant_storage::_S_vtable): Likewise.
(_Variant_storage::__M_reset_impl): Adjust to use __do_visit.
(_Variant_storage::__M_reset): Adjust.
(_Move_ctor_base::__M_destructive_copy): New.
(_Copy_assign_base::operator=): Adjust to use __do_visit.
(_Copy_assign_alias): Adjust to check both copy assignment
and copy construction for triviality.
(_Multi_array): Add support for visitors that accept and return
a __variant_cookie.
(__gen_vtable_impl::_S_apply_all_alts): Likewise.
(__gen_vtable_impl::_S_apply_single_alt): Likewise.
(__gen_vtable_impl::__element_by_index_or_cookie): New. Generate
a __variant_cookie temporary for a variant that is valueless and..
(__gen_vtable_impl::__visit_invoke): ..adjust here.
(__gen_vtable::_Array_type): Conditionally make space for
the __variant_cookie visitor case.
(variant): Add __variant_cast as a friend.
(variant::emplace): Use _M_reset() instead of self-destruction.
(visit): Reimplement in terms of __do_visit.
* testsuite/20_util/variant/compile.cc: Adjust.
* testsuite/20_util/variant/run.cc: Likewise.
diff --git a/libstdc++-v3/include/std/variant b/libstdc++-v3/include/std/variant
index 89deb14..c2f82a7 100644
--- a/libstdc++-v3/include/std/variant
+++ b/libstdc++-v3/include/std/variant
@@ -138,6 +138,19 @@ namespace __variant
constexpr variant_alternative_t<_Np, variant<_Types...>> const&&
get(const variant<_Types...>&&);
+ template<typename _Visitor, typename... _Variants>
+ constexpr decltype(auto)
+ __do_visit(_Visitor&& __visitor, _Variants&&... __variants);
+
+ template <typename... _Types, typename _Tp>
+ decltype(auto) __variant_cast(_Tp&& __rhs)
+ {
+ if constexpr (is_const_v<remove_reference_t<_Tp>>)
+ return static_cast<const variant<_Types...>&>(__rhs);
+ else
+ return static_cast<variant<_Types...>&>(__rhs);
+ }
+
namespace __detail
{
namespace __variant
@@ -155,6 +168,9 @@ namespace __variant
std::integral_constant<size_t, is_same_v<_Tp, _First>
? 0 : __index_of_v<_Tp, _Rest...> + 1> {};
+ // used for raw visitation
+ struct __variant_cookie {};
+
// _Uninitialized<T> is guaranteed to be a literal type, even if T is not.
// We have to do this, because [basic.types]p10.5.3 (n4606) is not implemented
// yet. When it's implemented, _Uninitialized<T> can be changed to the alias
@@ -246,11 +262,6 @@ namespace __variant
::new (__lhs) _Type(__variant::__ref_cast<_Rhs>(__rhs));
}
- template<typename _Variant, size_t _Np>
- void
- __erased_dtor(_Variant&& __v)
- { std::_Destroy(std::__addressof(__variant::__get<_Np>(__v))); }
-
template<typename _Lhs, typename _Rhs>
void
__erased_assign(void* __lhs, void* __rhs)
@@ -369,9 +380,6 @@ namespace __variant
template<typename... _Types>
struct _Variant_storage<false, _Types...>
{
- template<size_t... __indices>
- static constexpr void (*_S_vtable[])(const _Variant_storage&) =
- { &__erased_dtor<const _Variant_storage&, __indices>... };
constexpr _Variant_storage() : _M_index(variant_npos) { }
@@ -381,16 +389,21 @@ namespace __variant
_M_index(_Np)
{ }
- template<size_t... __indices>
- constexpr void _M_reset_impl(std::index_sequence<__indices...>)
- {
- if (_M_index != __index_type(variant_npos))
- _S_vtable<__indices...>[_M_index](*this);
+ constexpr void _M_reset_impl()
+ {
+ __do_visit([](auto&& __this_mem) mutable
+ -> __detail::__variant::__variant_cookie
+ {
+ if constexpr (!is_same_v<remove_reference_t<decltype(__this_mem)>,
+ __variant_cookie>)
+ std::_Destroy(std::__addressof(__this_mem));
+ return {};
+ }, __variant_cast<_Types...>(*this));
}
void _M_reset()
{
- _M_reset_impl(std::index_sequence_for<_Types...>{});
+ _M_reset_impl();
_M_index = variant_npos;
}
@@ -522,6 +535,20 @@ namespace __variant
}
}
+ void _M_destructive_copy(const _Move_ctor_base& __rhs)
+ {
+ this->~_Move_ctor_base();
+ __try
+ {
+ ::new (this) _Move_ctor_base(__rhs);
+ }
+ __catch (...)
+ {
+ this->_M_index = variant_npos;
+ __throw_exception_again;
+ }
+ }
+
_Move_ctor_base(const _Move_ctor_base&) = default;
_Move_ctor_base& operator=(const _Move_ctor_base&) = default;
_Move_ctor_base& operator=(_Move_ctor_base&&) = default;
@@ -538,6 +565,11 @@ namespace __variant
this->~_Move_ctor_base();
::new (this) _Move_ctor_base(std::move(__rhs));
}
+ void _M_destructive_copy(const _Move_ctor_base& __rhs)
+ {
+ this->~_Move_ctor_base();
+ ::new (this) _Move_ctor_base(__rhs);
+ }
};
template<typename... _Types>
@@ -554,21 +586,38 @@ namespace __variant
operator=(const _Copy_assign_base& __rhs)
noexcept(_Traits<_Types...>::_S_nothrow_copy_assign)
{
- if (this->_M_index == __rhs._M_index)
+ __do_visit([this, &__rhs](auto&& __this_mem, auto&& __rhs_mem) mutable
+ -> __detail::__variant::__variant_cookie
{
- if (__rhs._M_valid())
+ if constexpr (is_same_v<remove_reference_t<decltype(__this_mem)>, remove_reference_t<decltype(__rhs_mem)>>)
{
- static constexpr void (*_S_vtable[])(void*, void*) =
- { &__erased_assign<_Types&, const _Types&>... };
- _S_vtable[__rhs._M_index](this->_M_storage(),
- __rhs._M_storage());
+ if constexpr (!is_same_v<remove_reference_t<decltype(__rhs_mem)>, __variant_cookie>)
+ __this_mem = __rhs_mem;
}
- }
- else
- {
- _Copy_assign_base __tmp(__rhs);
- this->_M_destructive_move(std::move(__tmp));
- }
+ else
+ {
+ if constexpr (!is_same_v<remove_reference_t<decltype(__rhs_mem)>, __variant_cookie>)
+ {
+ using __rhs_type =
+ remove_reference_t<decltype(__rhs_mem)>;
+ if constexpr (is_nothrow_copy_constructible_v<__rhs_type>
+ || !is_nothrow_move_constructible_v<__rhs_type>)
+ {
+ this->_M_destructive_copy(__rhs);
+ }
+ else
+ {
+ _Copy_assign_base __tmp(__rhs);
+ this->_M_destructive_move(std::move(__tmp));
+ }
+ }
+ else
+ {
+ this->_M_reset();
+ }
+ }
+ return {};
+ }, __variant_cast<_Types...>(*this), __variant_cast<_Types...>(__rhs));
__glibcxx_assert(this->_M_index == __rhs._M_index);
return *this;
}
@@ -587,7 +636,8 @@ namespace __variant
template<typename... _Types>
using _Copy_assign_alias =
- _Copy_assign_base<_Traits<_Types...>::_S_trivial_copy_assign,
+ _Copy_assign_base<_Traits<_Types...>::_S_trivial_copy_assign
+ && _Traits<_Types...>::_S_trivial_copy_ctor,
_Types...>;
template<bool, typename... _Types>
@@ -733,15 +783,21 @@ namespace __variant
_Tp _M_data;
};
- template<typename _Tp, size_t __first, size_t... __rest>
- struct _Multi_array<_Tp, __first, __rest...>
+ template<typename _Ret,
+ typename _Visitor,
+ typename... _Variants,
+ size_t __first, size_t... __rest>
+ struct _Multi_array<_Ret(*)(_Visitor, _Variants...), __first, __rest...>
{
+ static constexpr int __do_cookie =
+ is_same_v<_Ret, __variant_cookie> ? 1 : 0;
+ using _Tp = _Ret(*)(_Visitor, _Variants...);
template<typename... _Args>
constexpr const _Tp&
_M_access(size_t __first_index, _Args... __rest_indices) const
- { return _M_arr[__first_index]._M_access(__rest_indices...); }
+ { return _M_arr[__first_index + __do_cookie]._M_access(__rest_indices...); }
- _Multi_array<_Tp, __rest...> _M_arr[__first];
+ _Multi_array<_Tp, __rest...> _M_arr[__first + __do_cookie];
};
// Creates a multi-dimensional vtable recursively.
@@ -801,18 +857,37 @@ namespace __variant
_S_apply_all_alts(_Array_type& __vtable,
std::index_sequence<__var_indices...>)
{
- (_S_apply_single_alt<__var_indices>(
- __vtable._M_arr[__var_indices]), ...);
+ if constexpr (is_same_v<_Result_type, __variant_cookie>)
+ (_S_apply_single_alt<true, __var_indices>(
+ __vtable._M_arr[__var_indices + 1],
+ &(__vtable._M_arr[0])), ...);
+ else
+ (_S_apply_single_alt<false, __var_indices>(
+ __vtable._M_arr[__var_indices]), ...);
}
- template<size_t __index, typename _Tp>
+ template<bool __do_cookie, size_t __index, typename _Tp>
static constexpr void
- _S_apply_single_alt(_Tp& __element)
+ _S_apply_single_alt(_Tp& __element, _Tp* __cookie_element = nullptr)
{
using _Alternative = variant_alternative_t<__index, _Next>;
- __element = __gen_vtable_impl<
- remove_reference_t<decltype(__element)>, tuple<_Variants...>,
- std::index_sequence<__indices..., __index>>::_S_apply();
+ if constexpr (__do_cookie)
+ {
+ __element = __gen_vtable_impl<
+ _Tp,
+ tuple<_Variants...>,
+ std::index_sequence<__indices..., __index>>::_S_apply();
+ *__cookie_element = __gen_vtable_impl<
+ _Tp,
+ tuple<_Variants...>,
+ std::index_sequence<__indices..., variant_npos>>::_S_apply();
+ }
+ else
+ {
+ __element = __gen_vtable_impl<
+ remove_reference_t<decltype(__element)>, tuple<_Variants...>,
+ std::index_sequence<__indices..., __index>>::_S_apply();
+ }
}
};
@@ -825,11 +900,22 @@ namespace __variant
using _Array_type =
_Multi_array<_Result_type (*)(_Visitor&&, _Variants...)>;
+ template<size_t __index, typename _Variant>
+ static constexpr decltype(auto)
+ __element_by_index_or_cookie(_Variant&& __var)
+ {
+ if constexpr (__index != variant_npos)
+ return __variant::__get<__index>(std::forward<_Variant>(__var));
+ else
+ return __variant_cookie{};
+ }
+
static constexpr decltype(auto)
__visit_invoke(_Visitor&& __visitor, _Variants... __vars)
{
return std::__invoke(std::forward<_Visitor>(__visitor),
- __variant::__get<__indices>(std::forward<_Variants>(__vars))...);
+ __element_by_index_or_cookie<__indices>(
+ std::forward<_Variants>(__vars))...);
}
static constexpr auto
@@ -843,7 +929,9 @@ namespace __variant
using _Func_ptr = _Result_type (*)(_Visitor&&, _Variants...);
using _Array_type =
_Multi_array<_Func_ptr,
- variant_size_v<remove_reference_t<_Variants>>...>;
+ (variant_size_v<remove_reference_t<_Variants>>
+ + (is_same_v<_Result_type, __variant_cookie> ? 1 : 0))
+ ...>;
static constexpr _Array_type
_S_apply()
@@ -1036,6 +1124,9 @@ namespace __variant
variant<_Types...>>
{
private:
+ template <typename... _UTypes, typename _Tp>
+ friend decltype(auto) __variant_cast(_Tp&&);
+
static_assert(sizeof...(_Types) > 0,
"variant must have at least one alternative");
static_assert(!(std::is_reference_v<_Types> || ...),
@@ -1185,7 +1276,6 @@ namespace __variant
{
static_assert(_Np < sizeof...(_Types),
"The index should be in [0, number of alternatives)");
-
using type = variant_alternative_t<_Np, variant>;
// If constructing the value can throw but move assigning it can't,
// construct in a temporary and then move assign from it. This gives
@@ -1202,7 +1292,7 @@ namespace __variant
return std::get<_Np>(*this);
}
- this->~variant();
+ this->_M_reset();
__try
{
::new (this) variant(in_place_index<_Np>,
@@ -1225,7 +1315,6 @@ namespace __variant
{
static_assert(_Np < sizeof...(_Types),
"The index should be in [0, number of alternatives)");
-
using type = variant_alternative_t<_Np, variant>;
if constexpr (is_trivially_copyable_v<type>
&& !is_nothrow_constructible_v<type, initializer_list<_Up>,
@@ -1239,7 +1328,7 @@ namespace __variant
return std::get<_Np>(*this);
}
- this->~variant();
+ this->_M_reset();
__try
{
::new (this) variant(in_place_index<_Np>, __il,
@@ -1401,11 +1490,8 @@ namespace __variant
template<typename _Visitor, typename... _Variants>
constexpr decltype(auto)
- visit(_Visitor&& __visitor, _Variants&&... __variants)
+ __do_visit(_Visitor&& __visitor, _Variants&&... __variants)
{
- if ((__variants.valueless_by_exception() || ...))
- __throw_bad_variant_access("Unexpected index");
-
using _Result_type =
decltype(std::forward<_Visitor>(__visitor)(
std::get<0>(std::forward<_Variants>(__variants))...));
@@ -1418,6 +1504,17 @@ namespace __variant
std::forward<_Variants>(__variants)...);
}
+ template<typename _Visitor, typename... _Variants>
+ constexpr decltype(auto)
+ visit(_Visitor&& __visitor, _Variants&&... __variants)
+ {
+ if ((__variants.valueless_by_exception() || ...))
+ __throw_bad_variant_access("Unexpected index");
+
+ return __do_visit(std::forward<_Visitor>(__visitor),
+ std::forward<_Variants>(__variants)...);
+ }
+
template<bool, typename... _Types>
struct __variant_hash_call_base_impl
{
diff --git a/libstdc++-v3/testsuite/20_util/variant/compile.cc b/libstdc++-v3/testsuite/20_util/variant/compile.cc
index 8a43092..04fef0b 100644
--- a/libstdc++-v3/testsuite/20_util/variant/compile.cc
+++ b/libstdc++-v3/testsuite/20_util/variant/compile.cc
@@ -488,12 +488,12 @@ void test_triviality()
TEST_TEMPLATE(=default, =default, , =default, , true, false, true, false)
TEST_TEMPLATE(=default, =default, , , =default, true, false, false, true)
TEST_TEMPLATE(=default, =default, , , , true, false, false, false)
- TEST_TEMPLATE(=default, , =default, =default, =default, false, true, true, true)
- TEST_TEMPLATE(=default, , =default, =default, , false, true, true, false)
+ TEST_TEMPLATE(=default, , =default, =default, =default, false, true, false, true)
+ TEST_TEMPLATE(=default, , =default, =default, , false, true, false, false)
TEST_TEMPLATE(=default, , =default, , =default, false, true, false, true)
TEST_TEMPLATE(=default, , =default, , , false, true, false, false)
- TEST_TEMPLATE(=default, , , =default, =default, false, false, true, true)
- TEST_TEMPLATE(=default, , , =default, , false, false, true, false)
+ TEST_TEMPLATE(=default, , , =default, =default, false, false, false, true)
+ TEST_TEMPLATE(=default, , , =default, , false, false, false, false)
TEST_TEMPLATE(=default, , , , =default, false, false, false, true)
TEST_TEMPLATE(=default, , , , , false, false, false, false)
TEST_TEMPLATE( , =default, =default, =default, =default, false, false, false, false)
diff --git a/libstdc++-v3/testsuite/20_util/variant/run.cc b/libstdc++-v3/testsuite/20_util/variant/run.cc
index c5ea7df..565b0e2 100644
--- a/libstdc++-v3/testsuite/20_util/variant/run.cc
+++ b/libstdc++-v3/testsuite/20_util/variant/run.cc
@@ -88,6 +88,21 @@ void arbitrary_ctor()
VERIFY(get<1>(v) == "a");
}
+struct ThrowingMoveCtorThrowsCopyCtor
+{
+ ThrowingMoveCtorThrowsCopyCtor() noexcept = default;
+ ThrowingMoveCtorThrowsCopyCtor(ThrowingMoveCtorThrowsCopyCtor&&) {}
+ ThrowingMoveCtorThrowsCopyCtor(ThrowingMoveCtorThrowsCopyCtor const&)
+ {
+ throw 0;
+ }
+
+ ThrowingMoveCtorThrowsCopyCtor& operator=(ThrowingMoveCtorThrowsCopyCtor&&) noexcept
+ = default;
+ ThrowingMoveCtorThrowsCopyCtor& operator=(ThrowingMoveCtorThrowsCopyCtor const&) noexcept
+ = default;
+};
+
void copy_assign()
{
variant<monostate, string> v("a");
@@ -96,6 +111,20 @@ void copy_assign()
u = v;
VERIFY(holds_alternative<string>(u));
VERIFY(get<string>(u) == "a");
+ {
+ std::variant<int, ThrowingMoveCtorThrowsCopyCtor> v1,
+ v2 = ThrowingMoveCtorThrowsCopyCtor();
+ bool should_throw = false;
+ try
+ {
+ v1 = v2;
+ }
+ catch(int)
+ {
+ should_throw = true;
+ }
+ VERIFY(should_throw);
+ }
}
void move_assign()
@@ -183,11 +212,15 @@ void emplace()
AlwaysThrow a;
try { v.emplace<1>(a); } catch (nullptr_t) { }
VERIFY(v.valueless_by_exception());
+ v.emplace<0>(42);
+ VERIFY(!v.valueless_by_exception());
}
{
variant<int, AlwaysThrow> v;
try { v.emplace<1>(AlwaysThrow{}); } catch (nullptr_t) { }
VERIFY(v.valueless_by_exception());
+ v.emplace<0>(42);
+ VERIFY(!v.valueless_by_exception());
}
VERIFY(&v.emplace<0>(1) == &std::get<0>(v));
VERIFY(&v.emplace<int>(1) == &std::get<int>(v));