How does boost::variant allow string constants?

Question

So I've been playing around with typelists and boy are they interesting. One of things I wanted to do was attempt to implement my own variant class simply as an experiment in education on how typelists work and how they can be useful. Here's what my code currently looks like:

#include <cstddef>
#include <typeinfo>

#ifndef VARIANT_H_
#define VARIANT_H_

struct NullType {};

template <class T, class U>
struct TypeList {
    typedef T Head;
    typedef U Tail;
};

#define TYPELIST_1(T1)                                 TypeList<T1, NullType> 
#define TYPELIST_2(T1, T2)                             TypeList<T1, TYPELIST_1(T2) > 
#define TYPELIST_3(T1, T2, T3)                         TypeList<T1, TYPELIST_2(T2, T3) > 
#define TYPELIST_4(T1, T2, T3, T4)                     TypeList<T1, TYPELIST_3(T2, T3, T4) > 
#define TYPELIST_5(T1, T2, T3, T4, T5)                 TypeList<T1, TYPELIST_4(T2, T3, T4, T5) > 
#define TYPELIST_6(T1, T2, T3, T4, T5, T6)             TypeList<T1, TYPELIST_5(T2, T3, T4, T5, T6) >
#define TYPELIST_7(T1, T2, T3, T4, T5, T6, T7)         TypeList<T1, TYPELIST_6(T2, T3, T4, T5, T6, T7) > 
#define TYPELIST_8(T1, T2, T3, T4, T5, T6, T7, T8)     TypeList<T1, TYPELIST_7(T2, T3, T4, T5, T6, T7, T8) > 
#define TYPELIST_9(T1, T2, T3, T4, T5, T6, T7, T8, T9) TypeList<T1, TYPELIST_8(T2, T3, T4, T5, T6, T7, T8, T9) >

namespace util {

    namespace {
        template <class TL>                 struct MaxSize;
        template <class TL>                 struct Length;
        template <class TL, class T>        struct IndexOf;
        template <class TL, unsigned int i> struct TypeAt;

        template <>
        struct MaxSize<NullType> {
            static const size_t value = 0;
        };

        template <class Head, class Tail>
        struct MaxSize<TypeList<Head, Tail> > {
            static const size_t value = (sizeof(Head) > MaxSize<Tail>::value) ? sizeof(Head) : MaxSize<Tail>::value;
        };

        template <>
        struct Length<NullType> {
            enum { value = 0 };
        };

        template <class Head, class Tail>
        struct Length<TypeList<Head, Tail> > {
            enum { value = 1 + Length<Tail>::value };
        };

        template <class T>
        struct IndexOf<NullType, T> {
            enum { value = -1 };
        };

        template <class Tail, class T>
        struct IndexOf<TypeList<T, Tail>, T> {
            enum { value = 0 };
        };

        template <class Head, class Tail, class T>
        struct IndexOf<TypeList<Head, Tail>, T> {
            enum { value = (IndexOf<Tail, T>::value == -1) ? -1 : 1 + IndexOf<Tail, T>::value };
        };

        template <class Head, class Tail>
        struct TypeAt<TypeList<Head, Tail>, 0> {
            typedef Head type;
        };

        template <class Head, class Tail, unsigned int i>
        struct TypeAt<TypeList<Head, Tail>, i> {
            typedef typename TypeAt<Tail, i - 1>::type type;
        };
    }

    template <class TL>
    class variant;

    template<class U, class TL> 
    U *get(variant<TL> *v);

    template<class U, class TL> 
    const U *get(const variant<TL> *v);

    template<class U, class TL> 
    U &get(variant<TL> &v);

    template<class U, class TL> 
    const U &get(const variant<TL> &v);

    // this stuff is a visitation pattern used to make sure
    // that contained objects get properly destroyed
    namespace {
        template <class TL>
        struct apply_visitor;

        struct destroy_visitor {
            template <class T>
            void operator()(T *p) {
                p->~T();
            }
        };

        template <class H, class T>
        struct visitor_impl {
            template <class U, class Pred>
            static void visit(U *p, Pred pred) {
                if(H *x = get<H>(p)) {
                    pred(x);
                } else {
                    apply_visitor<T>::visit(p, pred);
                }
            }
        };

        template <class H>
        struct visitor_impl<H, NullType> {
            template <class U, class Pred>
            static void visit(U *p, Pred pred) {
                if(H *x = get<H>(p)) {
                    pred(x);
                } else {
                    throw std::bad_cast();
                }
            }
        };

        template <class TL>
        struct apply_visitor {
            typedef typename TL::Head H;
            typedef typename TL::Tail T;

            template <class U, class Pred>
            static void visit(U *p, Pred pred) {
                visitor_impl<H, T>::visit(p, pred);
            }
        };
    }

    template <class TL>
    class variant {
        template<class U, class X> friend U *get(variant<X> *v);
        template<class U, class X> friend const U *get(const variant<X> *v);
        template<class U, class X> friend U &get(variant<X> &v);
        template<class U, class X> friend const U &get(const variant<X> &v);

    public :            
        variant() : type_index_(0){
            new (&storage_) typename TypeAt<TL, 0>::type();
        }

        ~variant() {
            apply_visitor<TL>::visit(this, destroy_visitor());
        }

        template <class T>
        variant(const T &x) : type_index_(IndexOf<TL, T>::value) {
            typedef typename TypeAt<TL, IndexOf<TL, T>::value>::type value_type;
            new (&storage_) value_type(x);
        }

        template <class T>
        variant(T &x) : type_index_(IndexOf<TL, T>::value) {
            typedef typename TypeAt<TL, IndexOf<TL, T>::value>::type value_type;
            new (&storage_) value_type(x);
        }

        template <class T>
        variant &operator=(const T &rhs) {
            variant(rhs).swap(*this);
            return *this;
        }

        variant &operator=(const variant &rhs) {
            variant(rhs).swap(*this);
            return *this;
        }

    public:
        void swap(variant &other) {
            using std::swap;
            swap(storage_, other.storage_);
            swap(type_index_, other.type_index_);
        }

    private:
        template <class T>
        const T &get_ref() const {
            typedef typename TypeAt<TL, IndexOf<TL, T>::value>::type value_type;

            if(IndexOf<TL, T>::value != type_index_) {
                throw std::bad_cast();
            }

            return *reinterpret_cast<const value_type *>(&storage_);
        }

        template <class T>
        T &get_ref() {
            typedef typename TypeAt<TL, IndexOf<TL, T>::value>::type value_type;

            if(IndexOf<TL, T>::value != type_index_) {
                throw std::bad_cast();
            }

            return *reinterpret_cast<value_type *>(&storage_);
        }

        template <class T>
        const T *get_ptr() const {
            typedef typename TypeAt<TL, IndexOf<TL, T>::value>::type value_type;

            if(IndexOf<TL, T>::value != type_index_) {
                return 0;
            }

            return reinterpret_cast<const value_type *>(&storage_);
        }

        template <class T>
        T *get_ptr() {
            typedef typename TypeAt<TL, IndexOf<TL, T>::value>::type value_type;

            if(IndexOf<TL, T>::value != type_index_) {
                return 0;
            }

            return reinterpret_cast<value_type *>(&storage_);
        }

    public:
        int which() const {
            return type_index_;
        }

        bool empty() const {
            return false;
        }

        const std::type_info &type() const;

    private:
        struct { unsigned char buffer_[MaxSize<TL>::value]; } storage_;
        int                                                   type_index_;
    };

    // accessors
    template<class U, class TL> 
    U *get(variant<TL> *v) {
        return v->template get_ptr<U>();
    }

    template<class U, class TL> 
    const U *get(const variant<TL> *v) {
        return v->template get_ptr<U>();
    }

    template<class U, class TL> 
    U &get(variant<TL> &v) {
        return v.template get_ref<U>();
    }

    template<class U, class TL> 
    const U &get(const variant<TL> &v) {
        return v.template get_ref<U>();
    }
}

#endif

And this works very well! I can write things like the following and it works great:

typedef util::variant<TYPELIST_3(std::string, int, double)> variant;
variant x = std::string("hello world");
variant y = 10;
variant z = 123.45;

std::cout << util::get<std::string>(x) << std::endl;
std::cout << util::get<int>(y) << std::endl;
std::cout << util::get<double>(z) << std::endl;

And all works as expected :-). Here's my question. With boost::variant I can write the following with no issues:

boost::variant<int, std::string> v = "hello world";

With my version, if I write similarly:

util::variant<TYPELIST_2(int, std::string)> v = "hello world";

I get an error like this:

variant.hpp: In instantiation of 'util::<unnamed>::TypeAt<TypeList<std::basic_string<char>, NullType>, 4294967294u>':
variant.hpp:76:47:   instantiated from 'util::<unnamed>::TypeAt<TypeList<int, TypeList<std::basic_string<char>, NullType> >, 4294967295u>'
variant.hpp:161:61:   instantiated from 'util::variant<TL>::variant(const T&) [with T = char [12], TL = TypeList<int, TypeList<std::basic_string<char>, NullType> >]'
test.cc:27:50:   instantiated from here
variant.hpp:76:47: error: invalid use of incomplete type 'struct util::<unnamed>::TypeAt<NullType, 4294967293u>'
variant.hpp:32:46: error: declaration of 'struct util::<unnamed>::TypeAt<NullType, 4294967293u>'

Essentially, it can't find char[12] in the typelist in variant. Which makes sense since char[12] is in fact not explicitly listed as one of the types...

How does boost::variant make this work so seamlessly? I feel like it is the only real missing piece in my understanding of how boost::variant works. Thoughts?

Answer 1

You don't want to do is_convertible as another answer suggested. You would basically be reimplementing the C++ conversion mechanism using C++ type traits. Instead, you can use the C++ infrastructure that you already have.

The way boost does it is by having a class with a function that takes every type that the variant can accept. I'm not sure how boost does it exactly with C++03, but in C++11 syntax:

template <typename First, typename... Rest>
class constructor : public constructor<Rest...>
{
  using constructor<Rest...>::construct;

  static void
  construct(variant& v, First&& value);
};

Then your operator= and other functions call constructor<Types...>::construct(*this, value) and if there is an unambiguous conversion then C++ finds it for you.

I wrote a rather detailed blog post dissecting how all this works: http://thenewcpp.wordpress.com/2012/02/15/variadic-templates-part-3-or-how-i-wrote-a-variant-class/

Answer 2

You can make use of type traits like is_convertible (or the C++11 stdlib version).

As @Andreas' comment says, you need to amend your templated constructor / assignment operator a bit, as in, don't search for a specific type, but for the first match.

#include <boost/mpl/if.hpp>
#include <boost/type_traits/is_convertible.hpp>

template<class T, class TList>
struct FirstMatch;

template<class T, class Head, class Tail>
struct FirstMatch<T, TypeList<Head, Tail>>{
  static bool const is_conv = boost::is_convertible<T, Head>::value;
  typedef typename boost::mpl::if_c<is_conv, Head,
      typename FirstMatch<T, Tail>::type>::type type;
};

template<class T>
struct FirstMatch<T, NullType>{
  typedef struct ERROR_no_convertible_type_found type;
};

template<class T, class TList>
struct FirstOrExactMatch{
  static int const idx = IndexOf<TList, T>::value;
  typedef typename boost::mpl::if_c<idx != -1,
      TypeAt<TList, idx>,
      FirstMatch<T, TList>
      >::type::type type;
};

The code is untested, but should work (minus typos).