Implement std::experimental::variant

On Fri, Aug 5, 2016 at 4:08 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
>> --- a/libstdc++-v3/include/bits/uses_allocator.h
>> +++ b/libstdc++-v3/include/bits/uses_allocator.h
>> @@ -113,6 +113,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>     constexpr bool uses_allocator_v = uses_allocator<_Tp, _Alloc>::value;
>> #endif // C++17
>>
>> +  template<typename _Tp, typename _Alloc, typename... _Args>
>> +    struct __is_uses_allocator_constructible
>> +    : conditional<uses_allocator<_Tp, _Alloc>::value,
>> +      __or_<is_constructible<_Tp, allocator_arg_t, _Alloc, _Args...>,
>> +           is_constructible<_Tp, _Args..., _Alloc>>,
>> +      is_constructible<_Tp, _Args...>>::type { };
>> +
>> +  template<typename _Tp, typename _Alloc, typename... _Args>
>> +    static constexpr bool __is_uses_allocator_constructible_v =
>> +      __is_uses_allocator_constructible<_Tp, _Alloc, _Args...>::value;
>
>
> This doesn't need to be 'static'

Done.

>
>
>> +  template<typename _Tp, typename _Alloc, typename... _Args>
>> +    struct __is_nothrow_uses_allocator_constructible
>> +    : conditional<uses_allocator<_Tp, _Alloc>::value,
>> +      __or_<is_nothrow_constructible<_Tp, allocator_arg_t, _Alloc,
>> _Args...>,
>> +           is_nothrow_constructible<_Tp, _Args..., _Alloc>>,
>> +      is_nothrow_constructible<_Tp, _Args...>>::type { };
>
>
> I wonder if there's any benefit to removing the duplication in the
> definitions of __is_nothrow_uses_allocator_constructible and
> __is_uses_allocator_constructible by defining a single template that
> can be instantation with either is_constructible or
> is_nothrow_constructible as needed:
>
>  template<template<typename, typename...> class _Trait, typename _Tp,
>           typename _Alloc, typename... _Args>
>    struct __is_uses_allocator_constructible_impl
>    : conditional<uses_allocator<_Tp, _Alloc>::value,
>      __or_<_Trait<_Tp, allocator_arg_t, _Alloc, _Args...>,
>          _Trait<_Tp, _Args..., _Alloc>>,
>      _Trait<_Tp, _Args...>>::type { };
>
>  template<typename _Tp, typename _Alloc, typename... _Args>
>    using __is_uses_allocator_constructible
>      = __is_uses_allocator_constructible_impl<is_constructible,
>                                               _Tp, _Alloc, _Args...>;
>
>  template<typename _Tp, typename _Alloc, typename... _Args>
>    using __is_nothrow_uses_allocator_constructible
>      = __is_uses_allocator_constructible_impl<is_nothrow_constructible,
>                                               _Tp, _Alloc, _Args...>;
>
> What do you think?
>
> (The variable templates would be unchanged).

Done. I don't have strong opinion on this.

>
>
>> +
>> +  template<typename _Tp, typename _Alloc, typename... _Args>
>> +    static constexpr bool __is_nothrow_uses_allocator_constructible_v =
>> +      __is_uses_allocator_constructible<_Tp, _Alloc, _Args...>::value;
>
>
> This should be using __is_nothrow_uses_allocator_constructible
> (and doesn't need to be static)

Good catch. :)

>
>
>
>> +
>> +  template<typename _Tp, typename... _Args>
>> +    void __uses_allocator_construct_impl(__uses_alloc0 __a, _Tp* __ptr,
>> +                                        _Args&&... __args)
>> +    { new (__ptr) _Tp(forward<_Args>(__args)...); }
>> +
>> +  template<typename _Tp, typename _Alloc, typename... _Args>
>> +    void __uses_allocator_construct_impl(__uses_alloc1<_Alloc> __a, _Tp*
>> __ptr,
>> +                                        _Args&&... __args)
>> +    { new (__ptr) _Tp(allocator_arg, *__a._M_a,
>> forward<_Args>(__args)...); }
>> +
>> +  template<typename _Tp, typename _Alloc, typename... _Args>
>> +    void __uses_allocator_construct_impl(__uses_alloc2<_Alloc> __a, _Tp*
>> __ptr,
>> +                                        _Args&&... __args)
>> +    { new (__ptr) _Tp(forward<_Args>(__args)..., *__a._M_a); }
>
>
> I think these all need to use ::new (__ptr) with qualification, see
> below.

Done. I didn't add a testcase for this. Do you think that we need one/some?

>
>
>> +/** @file variant
>> + *  This is a TS C++ Library header.
>
>
> This should be updated.

Done.

>
>> + */
>> +
>> +#ifndef _GLIBCXX_VARIANT
>> +#define _GLIBCXX_VARIANT 1
>> +
>> +#pragma GCC system_header
>> +
>> +#if __cplusplus <= 201103L
>
>
> This should be 201402L

Done.

>
>> +# include <bits/c++17_warning.h>
>> +#else
>> +
>> +#include <tuple>
>> +#include <type_traits>
>> +#include <utility>
>> +#include <bits/enable_special_members.h>
>> +#include <bits/uses_allocator.h>
>> +
>> +namespace std _GLIBCXX_VISIBILITY(default)
>> +{
>> +_GLIBCXX_BEGIN_NAMESPACE_VERSION
>> +
>> +  template<typename... _Types> class variant;
>> +
>> +  template<typename _Variant>
>> +    struct variant_size;
>> +
>> +  template<typename _Variant>
>> +    struct variant_size<const _Variant> : variant_size<_Variant> {};
>> +
>> +  template<typename _Variant>
>> +    struct variant_size<volatile _Variant> : variant_size<_Variant> {};
>> +
>> +  template<typename _Variant>
>> +    struct variant_size<const volatile _Variant> : variant_size<_Variant>
>> {};
>> +
>> +  template<typename... _Types>
>> +    struct variant_size<variant<_Types...>>
>> +    : std::integral_constant<size_t, sizeof...(_Types)> {};
>> +
>> +  template<typename _Variant>
>> +    static constexpr size_t variant_size_v =
>> variant_size<_Variant>::value;
>
>
> We don't need 'static' here.

Done.

>
>> +
>> +  template<size_t _Np, typename _Variant>
>> +    struct variant_alternative;
>> +
>> +  template<size_t _Np, typename _First, typename... _Rest>
>> +    struct variant_alternative<_Np, variant<_First, _Rest...>>
>> +    : variant_alternative<_Np-1, variant<_Rest...>> {};
>> +
>> +  template<typename _First, typename... _Rest>
>> +    struct variant_alternative<0, variant<_First, _Rest...>>
>> +    { using type = _First; };
>> +
>> +  template<size_t _Np, typename _Variant>
>> +    using variant_alternative_t =
>> +      typename variant_alternative<_Np, _Variant>::type;
>> +
>> +  static constexpr size_t variant_npos = -1;
>
>
> Or here.

Done.

>
>> +
>> +namespace __detail
>> +{
>> +namespace __variant
>> +{
>> +  // Returns the first apparence of _Tp in _Types.
>> +  // Returns sizeof...(_Types) if _Tp is not in _Types.
>> +  template<typename _Tp, typename... _Types>
>> +    struct __index_of : std::integral_constant<size_t, 0> {};
>> +
>> +  template<typename _Tp, typename... _Types>
>> +    static constexpr size_t __index_of_v = __index_of<_Tp,
>> _Types...>::value;
>
>
> Or here.

Done.

>
>> +  // Stores a void alternative, until void becomes a regular type.
>
>
> Personally I hope it won't become a regular type :-)

Sorry :)

Do you mind to share your insights?

> Let's say "because void is not a regault type" here. That avoids the
> comment becoming stale. If the language changes we'll need to update
> this bit of the code anyway. so the comment can be updated then too.

Done.

>
>> +      return __reserved_type_map<_Qualified_storage, _Alternative>(
>> +       *static_cast<_Storage*>(__ptr));
>> +    }
>> +
>> +  // Various functions as "vtable" entries, where those vtables are used
>> by
>> +  // polymorphic operations.
>> +  template<typename _Lhs, typename _Rhs>
>> +    constexpr void
>> +    __erased_ctor(void* __lhs, void* __rhs)
>> +    { new (__lhs) decay_t<_Lhs>(__get_alternative<_Rhs>(__rhs)); }
>> +
>> +  template<typename _Alloc, typename _Lhs, typename _Rhs>
>> +    constexpr void
>> +    __erased_use_alloc_ctor(const _Alloc& __a, void* __lhs, void* __rhs)
>> +    {
>> +      __uses_allocator_construct(__a, static_cast<decay_t<_Lhs>*>(__lhs),
>> +                                __get_alternative<_Rhs>(__rhs));
>> +    }
>> +
>> +  template<typename _Tp>
>> +    constexpr void
>> +    __erased_dtor(void* __ptr)
>> +    {
>> +      using _Storage = decay_t<_Tp>;
>> +      static_cast<_Storage*>(__ptr)->~_Storage();
>> +    }
>
>
> This is almost the same as the __exception_ptr::__dest_thunk(void*)
> function we're about to add with Gleb's patch. I wonder if we should
> reuse the same function in both places. We can do that later though.

Added a TODO.

>
>
>> +  // For how many times does _Tp appear in _Tuple?
>> +  template<typename _Tp, typename _Tuple>
>> +    struct __tuple_count;
>> +
>> +  template<typename _Tp, typename _Tuple>
>> +    static constexpr size_t __tuple_count_v = __tuple_count<_Tp,
>> _Tuple>::value;
>> +
>> +  template<typename _Tp, typename... _Types>
>> +    struct __tuple_count<_Tp, tuple<_Types...>>
>> +    : integral_constant<size_t, 0> { };
>> +
>> +  template<typename _Tp, typename _First, typename... _Rest>
>> +    struct __tuple_count<_Tp, tuple<_First, _Rest...>>
>> +    : integral_constant<
>> +       size_t,
>> +       __tuple_count_v<_Tp, tuple<_Rest...>> + is_same_v<_Tp, _First>> {
>> };
>> +
>> +  template<typename _Tp, typename... _Types>
>> +    static constexpr bool __exactly_once =
>> +      __tuple_count_v<_Tp, tuple<_Types...>> == 1;
>
>
> I was going to say we could reuse this nice utility in <tuple> for
> std::get<T> but actually our implementation does need to count the
> types, it just works by an implicit conversion to the unique base
> class with that type (and is ambiguous otherwise). We could use your
> __exactly_once to give a nice static assertion for invalid calls to
> std::get<T>, but that would add unnecessary compile-time overhead to
> valid calls. Anyway, that's another tangent that isn't relevant to
> variant ...

These are good thoughts! Added a TODO.

Removed static.

>
>
>> +
>> +  // Takes _Types and create an overloaded _S_fun for each type.
>> +  // If a type appears for more than one times in _Types,
>
>
> s/for more than one times/more than once/

Done.

>
>> +  // only create one overload for it.
>> +  template<typename... _Types>
>> +    struct __overload_set
>> +    { static void _S_fun(); };
>> +
>> +  template<typename _First, typename... _Rest>
>> +    struct __overload_set<_First, _Rest...> : __overload_set<_Rest...>
>> +    {
>> +      using __overload_set<_Rest...>::_S_fun;
>> +      static integral_constant<size_t, sizeof...(_Rest)> _S_fun(_First);
>> +    };
>> +
>> +  template<typename... _Rest>
>> +    struct __overload_set<void, _Rest...> : __overload_set<_Rest...>
>> +    {
>> +      using __overload_set<_Rest...>::_S_fun;
>> +    };
>> +
>> +  // Helper for variant(_Tp&&) and variant::operator=(_Tp&&).
>> +  // __accepted_index maps the arbitrary _Tp to an alternative type in
>> _Variant.
>> +  template<typename _Tp, typename _Variant, typename = void>
>> +    struct __accepted_index
>> +    { static constexpr size_t value = variant_npos; };
>> +
>> +  template<typename _Tp, typename... _Types>
>> +    struct __accepted_index<
>> +      _Tp, variant<_Types...>,
>> +      decltype(__overload_set<_Types...>::_S_fun(declval<_Tp>()),
>
>
> This I think all uses of declval<_Tp> need to be qualified with std::
>
>> +              declval<void>())>
>
>
> (The decval<void>() case is OK as that won't do ADL).

Done for all of them, for consistency.

>
>> +  template<typename _Array_type, typename _First, typename... _Rest,
>> +          typename... _Args>
>> +    struct __gen_vtable_impl<_Array_type, tuple<_First, _Rest...>,
>> +                            tuple<_Args...>>
>
>
> Do you actually need to use std::tuple here, or would something much
> more lightweight be OK too?

I actually just need a template to hold all alternatives. How about
forward declaring tuple, and not including the header?

I was totally unaware of the cost of <tuple>, and tried to use
tuple_cat() on a bunch of function calls:
(void)tuple_cat(foo<_Types>()...) where foo returns tuple<>.

But not we have fold expression \o/! So I can directly write:
(foo<_Types>, ...)

which is perfect.

>
> For example we have std::tr2::__reflection_typelist in
> <tr2/type_traits>. Or it looks like this could just use something even
> simpler:
>  template<typename... T> struct __type_list
>
> What we really need is to standardize Eric Niebler's metapgroamming
> library, or Peter Dimov's one, or *anything* that gives us a set of
> nice tools for doing this stuff. std::tuple is a very heavyweight type
> to use for simple type lists.

I don't need the whole pack of metaprogramming tools here, lucky me. ;)

>
> It doesn't look like you're using any members of std::tuple, so maybe
> it won't actually instantiate any of the base classes or member
> functions, which is what would be inefficient.
>
>> +  template<typename _Tp, typename... _Types>
>> +    _Tp& get(variant<_Types...>& __v)
>
>
> Please add 'inline' to these one-line functions. All the get and
> get_if overloads are tiny.

What's the difference between non-inline function templates and inline
function templates? At some point you may already explained that to
me, but I'm still confused.

>
>> +  template<typename... _Types>
>> +    bool operator!=(const variant<_Types...>& __lhs,
>> +                   const variant<_Types...>& __rhs)
>> +    { return !(__lhs == __rhs); }
>
>
> Inline.

Done.

>
>> +  template<typename... _Types>
>> +    bool operator>(const variant<_Types...>& __lhs,
>> +                  const variant<_Types...>& __rhs)
>> +    { return __rhs < __lhs; }
>
>
> Inline.

Done.

>
>> +  template<typename... _Types>
>> +    bool operator<=(const variant<_Types...>& __lhs,
>> +                   const variant<_Types...>& __rhs)
>> +    { return !(__lhs > __rhs); }
>
>
> etc. :-)

Done.

>
>> +  constexpr bool operator<(monostate, monostate) noexcept
>> +  { return false; }
>
>
> These are implicitly inline because of 'constexpr' so that's OK :-)
>
>> +      template<size_t _Np, typename... _Args>
>> +       void emplace(_Args&&... __args)
>> +       {
>> +         static_assert(_Np < sizeof...(_Types),
>> +                       "_Np should be in [0, number of alternatives)");
>> +         this->~variant();
>> +         __try
>> +           {
>> +             new (this) variant(in_place<_Np>,
>> +                                forward<_Args>(__args)...);
>
>
> I think this needs to be qualified:  ::new (this) ...
>
> Otherwise you can't emplace some types into a variant:
>
>  #include <cstddef>
>  #include <new>
>
>  struct foo {
>    static void* operator new(std::size_t, void* p);
>  };
>
>  template<typename T>
>  struct variant {
>    alignas(T) char buf[sizeof(T)];
>    void emplace(T t) {
>      new (this) T(t);
>    }
>  };
>
>  int main()
>  {
>    variant<foo> v;
>    v.emplace( {} );
>  }
>
> (We get this wrong in std::function too, which I'll fix).

Done.

>
>> +  // To hornor algebraic data type, variant<> should be a bottom type,
>> which
>
>
> s/hornor/honor/

...Oops. :)

>
>> +  // is 0 (as opposed to a void type, which is 1). Use incomplete type to
>> model
>> +  // bottom type.
>> +  template<> class variant<>;
>> +
>> +  template<size_t _Np, typename... _Types>
>> +    variant_alternative_t<_Np, variant<_Types...>>&
>> +    get(variant<_Types...>& __v)
>> +    {
>> +      static_assert(_Np < sizeof...(_Types),
>> +                   "_Np should be in [0, number of alternatives)");
>
>
> I wonder if this message would be more user-friendly if it said
> "index" instead of "_Np", since _Np isn't a symbol the user will
> recognize. What do you think?

Done. Sorry, I don't always have time to care about user-friendliness.
When I do, I don't. ;)

>
>> +      using argument_type = monostate;
>> +
>> +      size_t
>> +      operator()(const monostate& __t) const noexcept
>> +      {
>> +       constexpr size_t __magic_monostate_hash =
>> +         static_cast<size_t>(-7777);
>> +       return static_cast<size_t>(__magic_monostate_hash);
>
>
> Do we really need to static_cast<size_t> again when it's already a
> size_t? :-)
> Do we need either static_cast?
>
>         constexpr size_t __magic_monostate_hash = -7777;
>         return __magic_monostate_hash;

Done. I seriously have no idea why that will happen.

>
>> diff --git a/libstdc++-v3/testsuite/experimental/variant/compile.cc
>> b/libstdc++-v3/testsuite/experimental/variant/compile.cc
>> new file mode 100644
>> index 0000000..5cc7738
>> --- /dev/null
>> +++ b/libstdc++-v3/testsuite/experimental/variant/compile.cc
>> @@ -0,0 +1,392 @@
>> +// { dg-options "-std=gnu++17" }
>> +// { dg-do compile }
>> +
>> +// Copyright (C) 2016 Free Software Foundation, Inc.
>> +//
>> +// 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
>> +// terms of the GNU General Public License as published by the
>> +// Free Software Foundation; either version 3, or (at your option)
>> +// any later version.
>> +
>> +// This library is distributed in the hope that it will be useful,
>> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
>> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>> +// GNU General Public License for more details.
>> +
>> +// You should have received a copy of the GNU General Public License
>> along
>> +// with this library; see the file COPYING3.  If not see
>> +// <http://www.gnu.org/licenses/>.
>> +
>> +#include <variant>
>> +#include <string>
>> +#include <vector>
>> +#include <testsuite_hooks.h>
>
>
> There's no need for testsuite_hooks.h in this { do-do compile } test.
>
> /endreview
>
>
> This is some truly impressive code, I'm not sure I understand all of
> it yet!
>
> As before, my only reservation is that this fails to compile, but
> should work (because the selected constructor for the chosen
> alternative is constexpr):
>
>  #include <variant>
>
>  struct literal {
>   constexpr literal() = default;
>  };
>
>  struct nonliteral {
>   nonliteral() { }
>  };
>
>  using namespace std;
>  constexpr variant<literal, nonliteral> v{};
>  constexpr variant<literal, nonliteral> v1{in_place_type<literal>};
>  constexpr variant<literal, nonliteral> v2{in_place_index<0>};

Good news! This compiles now! I learned the technique from Anthony
Williams's implementation, whose code also compiles, but it requires a
close-to-trunk gcc, which implements
"...for unions, at least one non-static data member is of non-volatile
literal type, ...".

Also added it as a test.

Please verify the implementation by looking at _Uninitialized and
_Variant_storage.

>
>
> However, I think we could commit this for now as it's 99% complete.
> What do you think?
>
> I am concerned that if we commit this implementation now, and *don't*
> get a 100% conforming rewrite before we want to declare C++17 support
> stable and non-experimental, then we'd have to introduce an
> incompatible change. That could be done by replacing std::variant with
> std::_V2::variant, so it would still be possible.
>
> If you want to propose this for trunk please make the fixes noted
> above and send a new patch, CCing gcc-patches.
>
> Thanks!
>
>

I also moved the tests from experiemntal/variant to 20_util/variant.

Bootstrapped and tested on x86_64-linux-gnu.

Thank you all for reviewing all of these!

Implement std::experimental::variant

Commit Message

Comments

Patch