A variadic typelist which models boost::mpl Sequence concept

README.md

Description Current boost::variant (1.57) is capable of handling any kind of type sequences until it fulfills (models) mpl's Sequence concept [1][2]. However boost::mpl::vector can't handle more than 50 types at the moment. Even with a C++11 compiler that limits is strict. So I took Dave Abrahams' C++11 variadic typelist [3] and added some glue code to that, so it models the mpl's Sequence concept.

I've tested it with boost 1.56 and with the clang compiler which comes with OSX Yosemite (Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn))

Also I've made some measurements on a private project:

Measurement For every measure, I modified the header file which contains the definition of the type aliased variant. Then started my build system (ninja) to compile all the dependent cpp files, which are containing varaint visitors and boost::apply_visitor calls.

25 types in variant, mpl::vector25
memory: not measured
time: 14.2s, 14.3s, 14.3s

25 types in variant, xvector
memory: not measured
time: 14.2s, 14.2s, 14.3s

50 types in variant, mpl::vector50
memory: not measured
time: 16.5s, 16.5s, 16.3s

50 types in variant, xvector
memory: not measured
time: 16.5s, 16,4s, 17.0s

100 types in variant, xvector
memory: 500M
time: 32.5s, 32.5s, 32.3s

234 types in variant (+1 would exceed template instantiation max depth 256), xvector
memory: 1G-5G mem / clang process
time: could not wait to finish

Conclusion We should really try to get the number of types below 50. 100 can be handled. Around 200, the compiler is blowing up. Looks like there is something exponential in boost::variant visitation. I don't consider this practical limit of 50 problematic, because we can make grouping of the events. We can have enums to distinguish trivial types, and we can have variants inside variants. Also, we can have recursive variants as well [4].

[1] http://www.boost.org/doc/libs/1_57_0/doc/html/boost/make_variant_over.html
[2] http://www.boost.org/doc/libs/1_57_0/libs/mpl/doc/refmanual/forward-sequence.html
[3] https://github.com/dabrahams/mpl11/blob/master/standalone/O1_variadics.cpp
[4] http://www.boost.org/doc/libs/1_57_0/doc/html/variant/tutorial.html#variant.tutorial.recursive

typelist.h

// Copyright Dave Abrahams 2012. Distributed under the Boost
// Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

/// martong: Putting Dave's code in a namespace
namespace typelist {

//
//   assert_same -- a low-rent assertion
//__________________________________________________________
template <class T, class U> struct assert_same;
template <class T> struct assert_same<T,T> {};

//
//   places -- a wrapper for "N variadic parameters"
//__________________________________________________________

enum place { _ };
template <place...>
struct places {};

// Glue two specializations of places together
template <class P1, class P2> struct append_places;

template <place...X1, place...X2>
struct append_places<places<X1...>, places<X2...> >
{
    typedef places<X1...,X2...> type;
};

// Generate places<_,_,_,..._> with N arguments in O(log N)
template <unsigned N>
struct make_places
  : append_places<
        typename make_places<N/2>::type, 
        typename make_places<N-N/2>::type
    >
{};

template <> struct make_places<0> { typedef places<> type; };
template <> struct make_places<1> { typedef places<_> type; };

inline void test_places()
{
  assert_same<make_places<2>::type, places<_,_> > a2;
  assert_same<make_places<3>::type, places<_,_,_> > a3;
  assert_same<make_places<4>::type, places<_,_,_,_> > a4;
  assert_same<make_places<5>::type, places<_,_,_,_,_> > a5;
}

//
//   types -- a basic type sequence
//__________________________________________________________
template <class...T> struct types
{
    typedef types type;
};

//
//   nth_type -- get the Nth type in a sequence in O(1)
//__________________________________________________________

// Wrapper to prevent type decay
template <class T>
struct no_decay
{
    typedef T type;
};

// Use as function parameter that eats any POD
template <place ignored>
struct eat
{ eat(...); };

// inner beauty
template <class T> struct nth_type_impl;

template <place...X>
struct nth_type_impl<places<X...> >
{
    template <class U, class...Tail>
    static U result(eat<X>..., U*, Tail*...);
};

// Select the Nth type in O(1) (once all the necessary places<...> have
// been instantiated, which is O(log N) but happens only once.
template <unsigned N, class S> struct nth_type;

template <unsigned N, class...T>
struct nth_type<N, types<T...> >
  : decltype(
      nth_type_impl<typename make_places<N>::type>::result(
          (no_decay<T>*)0 ...))
{};

inline void test_nth_type()
{
    using seq = types<void(int),char[3],long>;
    
    {  assert_same<nth_type<0,seq>::type, void(int)> a; }
    {  assert_same<nth_type<1,seq>::type, char[3]> a; }
    {  assert_same<nth_type<2,seq>::type, long> a; }
}
    
//
//   drop -- drop N elements from the front of a type sequence in O(1)
//______________________________________________________________________


// inner beauty
template <class T> struct drop_impl;

template <place...X>
struct drop_impl<places<X...> >
{
    template <class...Tail>
    static types<Tail...> result(eat<X>..., no_decay<Tail>*...);
};

template <unsigned N, class S> struct drop;

template <unsigned N, class...T>
struct drop<N, types<T...> >
  : decltype(
      drop_impl<typename make_places<N>::type>::result(
          (no_decay<T>*)0 ...))
{};

inline void test_drop()
{
    using seq = types<void(int),char[3],long>;
    
    assert_same<drop<0,seq>::type, types<void(int),char[3],long> > a0;
    assert_same<drop<1,seq>::type, types<char[3],long> > a1;
    assert_same<drop<2,seq>::type, types<long> > a2;
    assert_same<drop<3,seq>::type, types<> > a3;
}

//
//   indices -- a sequence of unsigned integers
//__________________________________________________________
template <unsigned...N> struct indices
{
    typedef indices type;
};

// Glue two sets of indices together
template <class I1, class I2> struct append_indices;

template <unsigned...N1, unsigned...N2>
struct append_indices<indices<N1...>, indices<N2...> >
{
    typedef indices<N1..., (sizeof...(N1)+N2)...> type;
};

// generate indices [0,N) in O(log(N)) time
template <unsigned N>
struct make_indices
  : append_indices<
        typename make_indices<N/2>::type
      , typename make_indices<N-N/2>::type
    >
{};
template <> struct make_indices<0> { typedef indices<> type; };
template <> struct make_indices<1> { typedef indices<0> type; };


inline void test_make_indices()
{
    assert_same<make_indices<12>::type, indices<0,1,2,3,4,5,6,7,8,9,10,11> > a0;
}

//
//   take -- return the first N types in the sequence
//   Note: this is an O(N) algorithm.
//___________________________________________________________
template <class I, class S> struct take_impl;

template <unsigned...N, class S>
struct take_impl<indices<N...>, S>
{
    typedef types<typename nth_type<N,S>::type...> type;
};

template <unsigned N, class S>
struct take
  : take_impl<typename make_indices<N>::type, S>
{};

inline void test_take()
{
    using seq = types<void(int),char[3],long,double>;
    
    assert_same<take<0,seq>::type, types<> > a0;
    assert_same<take<1,seq>::type, types<void(int)> > a1;
    assert_same<take<2,seq>::type, types<void(int),char[3]> > a2;
    assert_same<take<3,seq>::type, types<void(int),char[3],long> > a3;
    assert_same<take<4,seq>::type, seq> a4;
}

//
//   front -- return the first type in the sequence
//___________________________________________________________
template <class S> struct front;

template <class H, class...T>
struct front<types<H,T...> >
{
    typedef H type;
};

inline void test_front()
{
    using seq = types<void(int),char[3],long>;
    
    assert_same<front<drop<0,seq>::type>::type, void(int)> a0;
    assert_same<front<drop<1,seq>::type>::type, char[3]> a1;
    assert_same<front<drop<2,seq>::type>::type, long> a2;
}

//
//   back -- return the last type in the sequence
//___________________________________________________________
template <class S> struct back;

template <class...T>
struct back<types<T...> >
  : nth_type<sizeof...(T)-1, types<T...> >
{};


inline void test_back()
{
    using seq = types<void(int),char[3],long>;
    
    assert_same<back<take<1,seq>::type>::type, void(int)> a0;
    assert_same<back<take<2,seq>::type>::type, char[3]> a1;
    assert_same<back<take<3,seq>::type>::type, long> a2;
}

template <class S> struct begin : front<S> {};

} // namespace typelist

/// ===========================================================================
/// making Dave's type container to fulfill mpl's Sequence concept

#include <boost/mpl/long.hpp>
#include <boost/mpl/is_sequence.hpp>
#include <boost/variant.hpp>
#include <boost/mpl/advance_fwd.hpp>
#include <boost/mpl/distance_fwd.hpp>

namespace typelist {

struct xvector_tag;
namespace aux {
struct v_iter_tag;
}

template<typename Vector, long n_>
struct v_iter {
    typedef aux::v_iter_tag tag;
    typedef boost::mpl::random_access_iterator_tag category;
    typedef typename nth_type<n_, typename Vector::types>::type type;

    typedef Vector vector_;
    typedef boost::mpl::long_<n_> pos;

    enum {
          next_ = n_ + 1
        , prior_ = n_ - 1
        , pos_ = n_
    };

    typedef v_iter<Vector,next_> next;
    typedef v_iter<Vector,prior_> prior;
};

struct none;
// Drop-in replacement of the 50 size limited boost::mpl::vector
template <typename... Ts>
struct xvector {
    // none is used to avoid accessing out-of-bounds type with nth_type.
    using types = types<Ts..., none>;
    using tag = xvector_tag;
    typedef v_iter<xvector,0> begin;
    typedef v_iter<xvector,sizeof...(Ts)> end;
};
} // namespace typelist

namespace boost { namespace mpl {

template<>
struct clear_impl< typelist::xvector_tag >
{
    template< typename Vector > struct apply
    {
        typedef typelist::xvector<> type;
    };
};

template <typename... Ts> struct xv_p_apply_helper;
template<typename T, typename... Ts>
struct xv_p_apply_helper<typelist::xvector<Ts...>, T> {
    using type = typelist::xvector<T, Ts...>;
};
template<>
struct push_front_impl< typelist::xvector_tag >
{
    template< typename Vector, typename T > struct apply
    {
        //typedef v_item<T,Vector,1> type;
        using type = typename xv_p_apply_helper<Vector, T>::type;
    };
};

template<> struct advance_impl<typelist::aux::v_iter_tag>
{
    template< typename Iterator, typename N > struct apply
    {
        enum { pos_ = Iterator::pos_, n_ = N::value };
        typedef typelist::v_iter<
              typename Iterator::vector_
            , (pos_ + n_)
            > type;
    };
};

template<> struct distance_impl<typelist::aux::v_iter_tag>
{
    template< typename Iter1, typename Iter2 > struct apply
    {
        enum { pos1_ = Iter1::pos_, pos2_ = Iter2::pos_ };
        typedef boost::mpl::long_<( pos2_ - pos1_ )> type;
        BOOST_STATIC_CONSTANT(long, value = ( pos2_ - pos1_ ));
    };
};

}} // namespace boost::mpl

namespace typelist {

inline void test_is_sequence() {
    using namespace typelist;
    using seq = xvector<int, double, long, char>;
    static_assert(boost::mpl::is_sequence<seq>::value, "");
    using Variant = boost::make_variant_over<seq>::type;
    Variant variant = int{3};
}

} // namespace typelist