Variant class with full move support

Question

I tried to write my own variant class, that is fully move-semantics enabled. WRT to implemented visitors, they don't require any policy and like to be derived from boost::static_visitor or to contain typedefed result_type. The result type of the visitor deduced by means of std::result_of and also can be prvalue, rref, lref or const lref. The only requirement is that all the returning types for all possible invocations of visitor must be of the same type exactly. It can be improved using std::common_type or something alike but better (to keep referenceness). Multivisitor provides the ability to pass some (non-visitable, i.e. not derived from variant<> class) of the arguments to visitor. It is very useful (for me).

Forward substitution of partial visitors (is a part of implementation details) of multivisitor is perfectly inlining. But backstroke is evidently no, due to type erasure points facing. It is non-avoidable anyways.

The following code (5⁵ = 3125 functions generated for visitor functor) compiles 20.9s vs 51.2s for boost::variant:

struct P
    : boost::static_visitor< void >
{

    template< typename ...T >
    result_type
    operator () (T &&...) const
    {
        //return __PRETTY_FUNCTION__;
    }

};

int main()
{
    struct A {};
    struct B {};
    struct C {};
    struct D {};
    struct E {};
    using V = boost::variant< A, B, C, D, E >;
    P p;
    V v0(A{}), v1(B{}), v2(C{}), v3(D{}), v4(E{});
    boost::apply_visitor(p, v0, v1, v2, v3, v4);
    return 0;
}

The compilation time of the code for my variant class significantly depends on lengths of symbol names (both on type names provided as template parameters to variant<>, and, say, on enclosing my variant machinery into own namespace). Dependence have nonlinear character and such behaviour is very strange. Definitely, there is the matter for issue. Compilation time for boost::variant does not depend on indicated above.

On my mind the never-empty-guarantee observed completely.

Following code works on gcc perfectly. Live example on Coliru.

Code of the variant implementation part itself:

#pragma once

#include "traits.hpp"
#include "recursive_wrapper.hpp"

#include <exception>
#include <memory>
#include <utility>
#include <type_traits>
#include <typeinfo>

namespace insituc
{

struct bad_get
        : std::exception
{

    ~bad_get() noexcept = default;

    bad_get() = default;

    bad_get(const char * const _what)
        : what_(_what)
    { ; }

    virtual
    const char *
    what() const noexcept
    {
        return what_;
    }

private :

    const char * const what_ = "bad_get: failed value get using get()";

};

template< typename ...types >
struct variant
{

    static_assert((0 < sizeof...(types)),
                  "type list should not be empty");

    static_assert(and_< !std::is_reference< types >::value... >::value,
                  "type list should not contain a reference");

    static_assert(and_< !std::is_const< types >::value... >::value,
                  "type list should not contain a const");

    static_assert(and_< !std::is_volatile< types >::value... >::value,
                  "type list should not contain a volatile");

    template< typename type >
    using which_type = get_offset< 0, is_same< type, unwrap_type< types > >::value... >;

    template< int _which >
    using type = typename nth_type< _which, unwrap_type< types >... >::type;

    using types_count = int_< sizeof...(types) >;

private :

    template< typename type >
    using is_this_type = bool_< !(which_type< unrefcv< type > >::value < 0) >;

    template< int _which >
    using internal_type = typename nth_type< _which, types... >::type;

    template< typename ...arguments >
    using which_is_constructible_from = get_offset< 0, std::is_constructible< unwrap_type< types >, arguments... >::value... >;

    template< typename type >
    using which_is_assignable_from = get_offset< 0, std::is_assignable< unwrap_type< types > &, type >::value... >;

    template< typename ...arguments >
    using is_there_constructible = or_< std::is_constructible< unwrap_type< types >, arguments... >::value... >;

    template< typename type >
    using is_there_assignable = or_< std::is_assignable< unwrap_type< types > &, type >::value... >;

    constexpr static std::size_t const size = max_value< std::size_t, sizeof(types)... >::value;
    constexpr static std::size_t const align = max_value< std::size_t, alignof(types)... >::value;
    using storage_type = typename std::aligned_storage< size, align >::type; // std::aligned_union would be better to use
    std::unique_ptr< storage_type > storage_ = std::make_unique< storage_type >();
    int which_ = -1;

    template< typename storage, typename visitor, typename type, typename ...arguments >
    static
    result_of< visitor, unwrap_type< type >, arguments... >
    caller(storage && _storage, visitor && _visitor, arguments &&... _arguments)
    {
        //static_assert(std::is_same< unrefcv< storage >, storage_type >::value, "!");
        return std::forward< visitor >(_visitor)(unwrap(reinterpret_cast< type >(_storage)), std::forward< arguments >(_arguments)...);
    }

    struct destroyer
    {

        template< typename type >
        void
        operator () (type & _value) const
        {
            _value.~type();
        }

    };

    template< typename rhs >
    enable_if< is_this_type< unrefcv< rhs > >::value >
    construct(rhs && _rhs)
    {
        static_assert(std::is_constructible< unrefcv< rhs >, rhs >::value, "type selected, but it cannot be constructed");
        constexpr int _which = which_type< unrefcv< rhs > >::value;
        ::new (storage_.get()) internal_type< _which >(std::forward< rhs >(_rhs));
        which_ = _which;
    }

    template< typename ...arguments >
    void
    construct(arguments &&... _arguments)
    {
        constexpr int _which = which_is_constructible_from< arguments... >::value;
        static_assert(!(_which < 0), "no one type can be constructed from specified parameter pack");
        // -Wconversion warning here means, that construction or assignmnet may imply undesirable type conversion
        ::new (storage_.get()) internal_type< _which >(std::forward< arguments >(_arguments)...);
        which_ = _which;
    }

    struct constructor
    {

        template< typename rhs >
        void
        operator () (rhs && _rhs) const
        {
            destination_.construct(std::forward< rhs >(_rhs));
        }

        variant & destination_;

    };

    struct assigner
    {

        template< int _which, typename rhs >
        void
        assign(rhs && _rhs) const
        {
            if (lhs_.which() == _which) {
                // -Wconversion warning here means, that assignment may imply undesirable type conversion
                lhs_.get< type< _which > >() = std::forward< rhs >(_rhs);
            } else {
                variant backup_(std::forward< rhs >(_rhs));
                lhs_.swap(backup_);
            }
        }

        template< typename rhs >
        enable_if< is_this_type< unrefcv< rhs > >::value >
        operator () (rhs && _rhs) const
        {
            static_assert(std::is_assignable< unrefcv< rhs > &, rhs >::value, "type selected, but it cannot be assigned");
            static_assert(std::is_constructible< unrefcv< rhs >, rhs >::value, "type selected, but it cannot be constructed");
            assign< which_type< unrefcv< rhs > >::value >(std::forward< rhs >(_rhs));
        }

        template< typename rhs >
        enable_if< (!is_this_type< unrefcv< rhs > >::value && (is_there_assignable< rhs >::value && is_there_constructible< rhs >::value)) >
        operator () (rhs && _rhs) const
        {
            assign< which_is_assignable_from< rhs >::value >(std::forward< rhs >(_rhs));
        }

        template< typename rhs >
        enable_if< (!is_this_type< unrefcv< rhs > >::value && (is_there_assignable< rhs >::value && !is_there_constructible< rhs >::value)) >
        operator () (rhs && _rhs) const
        {
            constexpr int _which = which_is_assignable_from< rhs >::value;
            if (lhs_.which() == _which) {
                // -Wconversion warning here means, that assignment may imply undesirable conversion
                lhs_.get< type< _which > >() = std::forward< rhs >(_rhs);
            } else {
                throw bad_get();
            }
        }

        template< typename rhs >
        enable_if< (!is_this_type< unrefcv< rhs > >::value && (!is_there_assignable< rhs >::value && is_there_constructible< rhs >::value)) >
        operator () (rhs && _rhs) const
        {
            constexpr int _which = which_is_constructible_from< rhs >::value;
            if (lhs_.which() == _which) {
                throw bad_get();
            } else {
                variant backup_(std::forward< rhs >(_rhs));
                lhs_.swap(backup_);
            }
        }

        template< typename rhs >
        enable_if< (!is_this_type< unrefcv< rhs > >::value && !(is_there_assignable< rhs >::value || is_there_constructible< rhs >::value)) >
        operator () (rhs &&) const
        {
            throw bad_get();
        }

        variant & lhs_;

    };

    struct reflect
    {

        template< typename type >
        std::type_info const &
        operator () (type const &) const noexcept
        {
            return typeid(type);
        }

    };

public :

    ~variant() noexcept
    {
        apply_visitor(destroyer{});
    }

    void
    swap(variant & _other) noexcept
    {
        storage_.swap(_other.storage_);
        std::swap(which_, _other.which_);
    }

    int
    which() const
    {
        return which_;
    }

    template< typename visitor, typename ...arguments >
    result_of< visitor, type< 0 > const &, arguments... >
    apply_visitor(visitor && _visitor, arguments &&... _arguments) const &
    {
        static_assert(is_same< result_of< visitor, unwrap_type< types > const &, arguments... >... >::value,
                      "non-identical return types in visitor");
        using result_type = result_of< visitor &&, type< 0 > const &, arguments... >;
        using caller_type = result_type (*)(storage_type const & _storage, visitor && _visitor, arguments &&... _arguments);
        constexpr static caller_type const dispatcher_[sizeof...(types)] = {&variant::caller< storage_type const &, visitor &&, types const &, arguments... >...};
        return dispatcher_[which_](*storage_, std::forward< visitor >(_visitor), std::forward< arguments >(_arguments)...);
    }

    template< typename visitor, typename ...arguments >
    result_of< visitor, type< 0 > &, arguments... >
    apply_visitor(visitor && _visitor, arguments &&... _arguments) &
    {
        static_assert(is_same< result_of< visitor, unwrap_type< types > &, arguments... >... >::value,
                      "non-identical return types in visitor");
        using result_type = result_of< visitor &&, type< 0 > &, arguments... >;
        using caller_type = result_type (*)(storage_type & _storage, visitor && _visitor, arguments &&... _arguments);
        constexpr static caller_type const dispatcher_[sizeof...(types)] = {&variant::caller< storage_type &, visitor &&, types &, arguments... >...};
        return dispatcher_[which_](*storage_, std::forward< visitor >(_visitor), std::forward< arguments >(_arguments)...);
    }

    template< typename visitor, typename ...arguments >
    result_of< visitor, type< 0 > &&, arguments... >
    apply_visitor(visitor && _visitor, arguments &&... _arguments) &&
    {
        static_assert(is_same< result_of< visitor, unwrap_type< types > &&, arguments... >... >::value,
                      "non-identical return types in visitor");
        using result_type = result_of< visitor &&, type< 0 > &&, arguments... >;
        using caller_type = result_type (*)(storage_type && _storage, visitor && _visitor, arguments &&... _arguments);
        constexpr static caller_type const dispatcher_[sizeof...(types)] = {&variant::caller< storage_type &&, visitor &&, types &&, arguments... >...};
        return dispatcher_[which_](std::move(*storage_), std::forward< visitor >(_visitor), std::forward< arguments >(_arguments)...);
    }

    variant()
    {
        static_assert(is_there_constructible<>::value, "no one type is default constructible");
        construct();
    }

    variant(variant const & _rhs)
    {
        _rhs.apply_visitor(constructor{*this});
    }

    variant(variant && _rhs)
    {
        std::move(_rhs).apply_visitor(constructor{*this});
    }

    template< typename ...other_types >
    variant(variant< other_types... > const & _rhs)
    {
        _rhs.apply_visitor(constructor{*this});
    }

    template< typename ...other_types >
    variant(variant< other_types... > & _rhs)
    {
        _rhs.apply_visitor(constructor{*this});
    }

    template< typename ...other_types >
    variant(variant< other_types... > && _rhs)
    {
        std::move(_rhs).apply_visitor(constructor{*this});
    }

    template< typename ...arguments >
    variant(arguments &&... _arguments)
    {
        construct(std::forward< arguments >(_arguments)...);
    }

    variant &
    operator = (variant const & _rhs)
    {
        _rhs.apply_visitor(assigner{*this});
        return *this;
    }

    variant &
    operator = (variant && _rhs)
    {
        std::move(_rhs).apply_visitor(assigner{*this});
        return *this;
    }

    template< typename ...other_types >
    variant &
    operator = (variant< other_types... > const & _rhs)
    {
        _rhs.apply_visitor(assigner{*this});
        return *this;
    }

    template< typename ...other_types >
    variant &
    operator = (variant< other_types... > & _rhs)
    {
        _rhs.apply_visitor(assigner{*this});
        return *this;
    }

    template< typename ...other_types >
    variant &
    operator = (variant< other_types... > && _rhs)
    {
        std::move(_rhs).apply_visitor(assigner{*this});
        return *this;
    }

    template< typename rhs >
    variant &
    operator = (rhs && _rhs)
    {
        static_assert((is_this_type< unrefcv< rhs > >::value || (is_there_assignable< rhs >::value || is_there_constructible< rhs >::value)),
                      "no one underlying type is proper to assignment");
        assigner{*this}(std::forward< rhs >(_rhs));
        return *this;
    }

    template< typename type >
    type const &
    get() const &
    {
        constexpr int _which = which_type< type >::value;
        static_assert(!(_which < 0), "type is not listed");
        if (which_ != _which) {
            throw bad_get();
        } else {
            return unwrap(reinterpret_cast< internal_type< _which > const & >(*storage_));
        }
    }

    template< typename type >
    type &
    get() &
    {
        constexpr int _which = which_type< type >::value;
        static_assert(!(_which < 0), "type is not listed");
        if (which_ != _which) {
            throw bad_get();
        } else {
            return unwrap(reinterpret_cast< internal_type< _which > & >(*storage_));
        }
    }

    template< typename type >
    type &&
    get() &&
    {
        constexpr int _which = which_type< type >::value;
        static_assert(!(_which < 0), "type is not listed");
        if (which_ != _which) {
            throw bad_get();
        } else {
            return unwrap(reinterpret_cast< internal_type< _which > && >(*storage_));
        }
    }

    std::type_info const &
    get_type_info() const
    {
        return apply_visitor(reflect{});
    }

};

template< typename type >
struct is_variant
        : bool_< false >
{

};

template< typename first, typename ...rest >
struct is_variant< variant< first, rest... > >
        : bool_< true >
{

};

template< typename ...types >
void
swap(variant< types... > & _lhs, variant< types... > & _rhs) noexcept
{
    _lhs.swap(_rhs);
}

template< typename variant, typename ...arguments >
variant
make_variant(arguments &&... _arguments)
{
    return variant(std::forward< arguments >(_arguments)...);
}

template< typename type, typename ...types >
type const &
get(variant< types... > const & _variant)
{
    return _variant.template get< type >();
}

template< typename type, typename ...types >
type &
get(variant< types... > & _variant)
{
    return _variant.template get< type >();
}

template< typename type, typename ...types >
type &&
get(variant< types... > && _variant)
{
    return std::move(_variant).template get< type >();
}

} // namespace insituc

And code of the visitor implementation part (all the rest is on Coliru):

#pragma once

#include "traits.hpp"
#include "variant.hpp"

#include <utility>

namespace insituc
{

namespace details
{

template< typename visitable >
using cvref_qualified_first_type = copy_cvref< visitable, typename unref< visitable >::template type< 0 > >;

template< typename supervisitor, typename type, bool = is_variant< unrefcv< type > >::value >
struct subvisitor;

template< typename supervisitor, typename visitable >
struct subvisitor< supervisitor, visitable, true >
{ // visitation

    template< typename ...visited >
    result_of< supervisitor, cvref_qualified_first_type< visitable >, visited... >
    operator () (visited &&... _visited) const
    {
        return std::forward< visitable >(visitable_).apply_visitor(std::forward< supervisitor >(supervisitor_), std::forward< visited >(_visited)...);
    }

    supervisitor && supervisitor_;
    visitable && visitable_;

};

template< typename supervisitor, typename type >
struct subvisitor< supervisitor, type, false >
{ // forwarding

    template< typename ...visited >
    result_of< supervisitor, type, visited... >
    operator () (visited &&... _visited) const
    {
        return std::forward< supervisitor >(supervisitor_)(std::forward< type >(value_), std::forward< visited >(_visited)...);
    }

    supervisitor && supervisitor_;
    type && value_;

};

template< typename ...visitables >
struct visitor_partially_applier;

template<>
struct visitor_partially_applier<>
{ // backward

    template< typename visitor >
    result_of< visitor >
    operator () (visitor && _visitor) const
    {
        return std::forward< visitor >(_visitor)();
    }

};

template< typename first, typename ...rest >
struct visitor_partially_applier< first, rest... >
        : visitor_partially_applier< rest... >
{ // forward

    using base = visitor_partially_applier< rest... >;

    template< typename visitor >
    result_of< base, subvisitor< visitor, first >, rest... >
    operator () (visitor && _visitor, first && _first, rest &&... _rest) const
    {
        subvisitor< visitor, first > const subvisitor_{std::forward< visitor >(_visitor), std::forward< first >(_first)};
        return base::operator () (subvisitor_, std::forward< rest >(_rest)...);
    }

};

} // namespace details

template< typename visitor, typename first, typename ...rest >
//constexpr // C++14 // body of constexpr function not a return-statement
result_of< details::visitor_partially_applier< first, rest... > const, visitor, first, rest... >
apply_visitor(visitor && _visitor, first && _first, rest &&... _rest) // visitables can contain non-visitor types
{
    details::visitor_partially_applier< first, rest... > const apply_visitor_partially_;
    return apply_visitor_partially_(std::forward< visitor >(_visitor), std::forward< first >(_first), std::forward< rest >(_rest)...);
}

namespace details
{

template< typename visitor >
struct delayed_visitor_applier
{

    /*static_assert(std::is_lvalue_reference< visitor >::value || !std::is_rvalue_reference< visitor >::value,
                  "visitor is not lvalue reference or value");*/

    delayed_visitor_applier(visitor && _visitor)
        : visitor_(std::forward< visitor >(_visitor))
    { ; }

    result_of< visitor >
    operator () () const
    {
        return visitor_();
    }

    result_of< visitor >
    operator () ()
    {
        return visitor_();
    }

    template< typename visitable,
              typename = enable_if< is_variant< unrefcv< visitable > >::value > >
    result_of< visitor, cvref_qualified_first_type< visitable > >
    operator () (visitable && _visitable) const
    {
        return std::forward< visitable >(_visitable).apply_visitor(visitor_);
    }

    template< typename visitable,
              typename = enable_if< is_variant< unrefcv< visitable > >::value > >
    result_of< visitor, cvref_qualified_first_type< visitable > >
    operator () (visitable && _visitable)
    {
        return std::forward< visitable >(_visitable).apply_visitor(visitor_);
    }

    template< typename ...visitables >
    result_of< details::visitor_partially_applier< visitables... > const, visitor, visitables... >
    operator () (visitables &&... _visitables) const
    {
        return apply_visitor(visitor_, std::forward< visitables >(_visitables)...);
    }

    template< typename ...visitables >
    result_of< details::visitor_partially_applier< visitables... > const, visitor, visitables... >
    operator () (visitables &&... _visitables)
    {
        return apply_visitor(visitor_, std::forward< visitables >(_visitables)...);
    }

private :

    visitor visitor_;

};

} // namespace details

template< typename visitor >
constexpr
details::delayed_visitor_applier< visitor >
apply_visitor(visitor && _visitor)
{
    return details::delayed_visitor_applier< visitor >(std::forward< visitor >(_visitor));
}

} // namespace insituc

Main cons are totally non-guaranteed exception safety on construction, copying, moving and so on. The implementation is based on smart pointers, and, thus, on dynamic memory allocation.

How can I improve exception safety? How can I get rid of using smart pointers and use different type of storage from the heap?

ADDITIONAL:

Recently I performed the test of compilation time for multivisitation. Three-dimentional results are presented as two cartesian projections. Upper one is dependence of compilation time (in seconds) on number of variant's bounded types for different apply_visitor arities (different lines). Bottom one is dependence of compilation time (in seconds) on apply_visitor arities for different numbers of variant's bounded types (different lines).

It is notable that compilation time have close to exponential dependence with respect to any dimesionality (apply_visitor arity or number of variant's bounded types).

Answer 1

The things you did right

Almost all of your code:

• Correct use of rvalue references, move semantics and perfect forwarding.
• You provided namespace-level functions that help with ADL (even though namespace-level get will probably not be found by ADL, but you can't do anything about that).
• You ensured that swap was noexcept.
• You gave meaningful names to your types and variables.
• You did some "concept check" with static_assert, which helps avoiding horrible error messages.

Basically, what you did is really good, especially since your edit. There's almost nothing left to say. Almost...

Naming stuff

There are only two hard things in Computer Science: cache invalidation, naming things and of-by-one errors.

Your variable names have generally good names. However, for some reason, you seem to hate capital letters. You could use some, at least for you template parameter names. That would also allow you to drop many underscores. This piece of code:

template< typename storage, typename visitor, typename type, typename ...arguments >
static
result_of< visitor, unwrap_type< type >, arguments... >
caller(storage && _storage, visitor && _visitor, arguments &&... _arguments)
{
    // ...
}

would probably be easier to read written as:

template< typename Storage, typename Visitor, typename Type, typename ...Arguments >
static
result_of< Visitor, unwrap_type< Type >, Arguments... >
caller(Storage && storage, Visitor && visitor, Arguments &&... arguments)
{
    // ...
}

I also almost got lost when I read this:

which_ = _which;

I understand the logic (leading underscore for class members), but I think that I would still make errors hard to detect if I wrote code with names so close from each other.

Exceptions

While I like the name bad_get for your exception (close to the names of the exceptions in the standard library), there are still some things that you can change in that class so that it looks even more like a standard library exception:

• You can make the destructor explicitly virtual.
• You can add a std::string overload to the constructor.

• You could also add an explicit override qualifier to the method what to clarify your intent (even though the standard library does not do it):

  virtual const char * what() const noexcept override { /* .... */ }
  

  I have to admit that there are many keywords on the same line. You can find information about why you should use the override keyword here. But basically, remember that sometimes, you want to override a function in a derived class, but write a function with a slightly different signature. Sometimes, this kind of error can be really hard to spot (because of implicit base class name hiding for example). If you add override to make it clear that you intend to override a base class function, the compiler will tell you if you messed the signature and ended up not overriding anything. In short, it helps to prevent silent errors.

Dead code

You have some pieces of dead code left:

/*static_assert(std::is_lvalue_reference< visitor >::value || !std::is_rvalue_reference< visitor >::value,
              "visitor is not lvalue reference or value");*/

You should simply remove it. Dead code will not help you, and revision control software can help you to find old code that you may need but already removed.

Simplify your return statements

You can use list initialization to make some of your return statements more readable provided the return type is already known by the function:

template< typename visitor >
constexpr
details::delayed_visitor_applier< visitor >
apply_visitor(visitor && _visitor)
{
    return details::delayed_visitor_applier< visitor >(std::forward< visitor >(_visitor));
}

The code above can be reduced to:

template< typename visitor >
constexpr
details::delayed_visitor_applier< visitor >
apply_visitor(visitor && _visitor)
{
    return { std::forward< visitor >(_visitor) };
}

That said, list initialization won't work if the constructor of details::delayed_visitor_applier< visitor > is marked explicit.

Answer 2

Have you tried the assignment? Using clang3.5, I get the following if I just add v3 = v0; near the end of your main function posted above (I got your latest version of your code from your web site):

In file included from main.cpp:53:
./traits.hpp:33:28: error: no matching function for call to object of type 'insituc::variant<A, B, C, D>::assigner'
using result_of = decltype(std::declval< type >()(std::declval< arguments >()...));
                           ^~~~~~~~~~~~~~~~~~~~~~
./variant/variant.hpp:275:32: note: in instantiation of template type alias 'result_of' requested here
    static_assert(is_same< result_of< visitor &&, unwrap_type< types > &, arguments &&... >... >,
                           ^
./variant/variant.hpp:351:14: note: in instantiation of function template specialization 'insituc::variant<A, B, C, D>::apply_visitor<insituc::variant<A, B, C, D>::assigner>' requested here
    _rhs.apply_visitor(assigner{*this});
         ^
main.cpp:89:8: note: in instantiation of member function 'insituc::variant<A, B, C, D>::operator=' requested here
v3 = v0;
   ^
./variant/variant.hpp:176:9: note: candidate template ignored: substitution failure [with rhs = A &]: non-type template argument is not a constant expression
    operator () (rhs && _rhs) const
    ^
./variant/variant.hpp:205:9: note: candidate template ignored: substitution failure [with rhs = A &]: non-type template argument is not a constant expression
    operator () (rhs && _rhs) const
    ^
./variant/variant.hpp:218:9: note: candidate template ignored: substitution failure [with rhs = A &]: non-type template argument is not a constant expression
    operator () (rhs && _rhs) const