Skip to content

Variadic templates, part 3 (or how I wrote a variant class)

February 15, 2012

Now that I have explained r-value references and variadic templates (part 1 and part 2), I will explain in great detail a stack based replacement for boost::variant. The only assumption that needs to be made here is that all of the objects contained in it have a nothrow move constructor.

A variant is essentially a tagged union. It is a variadic template class which holds one of the types specified in the template. The interface to the class is then designed in such a way that it is impossible to get a type error at runtime. If a value of the wrong type is requested, either nullptr is returned or an exception is thrown, depending on the version of get.

The variant interface

The interface to a variant is pretty simple, all you can do with a variant is construct it with different objects. On top of that, there are two functions, one to retrieve values from the variant, the other calls an appropriate visitor depending on the type of whatever is held in the variant. The Variant has two template parameters, the first is there because a Variant must hold at least one thing, the second is a variadic template pack which holds the remainder of the types that can be held.

template <typename First, typename... Types>
class Variant
{
  //default constructs a variant with the First type
  //which must be default constructible
  Variant();

  //the perfect-forwarding constructor
  template <typename T>
  Variant(T&& t);
};

The get function is declared as:

template <typename T>
T&
get(Variant&);

template <typename T>
const T&
get(const Variant&);

template <typename T>
T*
get(Variant*);

template <typename T>
const T*
get(const Variant*);

If the object held in a Variant isn't of the type requested, the reference version of get throws the exception bad_get, and the pointer version returns nullptr.

The visitor interface is:

template <typename Visitor, typename Visitable, typename... Args>
typename Visitor::result_type                                                 
apply_visitor(Visitor& visitor, Visitable& visitable, Args&&... args)

template <typename Visitor, typename Visitable, typename... Args>
typename Visitor::result_type
apply_visitor(const Visitor& visitor, Visitable& visitable, Args&&... args)

Both of these functions will call visitable.operator() on the object held in the Variant. The second passes the argument as a const reference. Any class used as Visitable must have operator() defined that can take everything contained in the Variant. Furthermore, each function in the visitor must return the same thing, and the return type is typedef'ed as result_type. Additionally, arbitrary extra arguments can be passed to the visitor functions. For example, suppose that we had the following variant object:

Variant<int, char, bool> a;

both of the following visitors would be usable with this Variant:

class VisitorA
{
  public:
  typedef void result_type;

  void
  operator()(int);

  void
  operator()(char);

  void
  operator()(bool);
};

class VisitorB
{
  public:
  typedef void result_type;

  void
  operator()(int);

  template <typename T>
  void
  operator()(T&& t);
};

Data storage

The storage for the Variant is simply a char[] that is big enough to hold the biggest type contained in the Variant, and aligned to the object with the biggest alignment.

The variant has the following fields defined:

static constexpr size_t m_size =
  max
  <
    Sizeof,
    First,
    Types...
  >::value;

union
{
  char m_storage[m_size];
  typename max<Alignof, First, Types...>::type m_align;
};

There are a few things going on here all at once, the main point is that we want a field m_storage to be an array big enough to hold the biggest object, and we need it to have the correct alignment for the object with the biggest alignment.
The union will be aligned to the alignment of its biggest member, so m_align is simply ensuring that m_storage has the correct alignment. Both the alignment and the size are computed with the metafunction max. I won't show its code here because it is long and distracts from the Variant, but you can get it in the supplied files. It takes as arguments a metafunction which is applied to the remainder of the arguments, and the biggest type as determined by the metafunction defines the result.

Recursive Wrapper

To store tree-like structures, where some objects could have one or more members of the same Variant, there is a class called recursive_wrapper, which essentially stores a pointer to the object instead of the actual object. There is a little bit of magic to make all of this work transparently which I will describe in the next section on visiting.

An example use of recursive_wrapper might be to store a binary tree that only has values at the leaves:

class InternalNode;

typedef Variant<recursive_wrapper<InternalNode>, int> BinaryTree;

class InternalNode
{
  public:
  BinaryTree left;
  BinaryTree right;
};

Visiting

Everything else in the Variant is implemented with visitors, so I will explain that next. This is also where most of the magic is, so you should pay particular attention to this part to understand the details.

The first thing that apply_visitor does is to call Variant::apply_visitor, there are two versions of this, one for a non-const Variant, one for a const Variant. They both do exactly the same thing, which results in the constness being captured in the template parameters rather than being explicit. From this point onward we only need one version of everything.

template <typename Internal, typename Visitor, typename... Args>
typename Visitor::result_type
apply_visitor(Visitor& visitor, Args&&... args)
{
  return do_visit<First, Types...>()(Internal(), m_which, 
    m_storage, visitor, 
    std::forward<Args>(args)...);                                  
}

template <typename Internal, typename Visitor, typename... Args>
typename Visitor::result_type
apply_visitor(Visitor& visitor, Args&&... args) const
{
  return do_visit<First, Types...>()(Internal(), m_which, 
    m_storage, visitor, 
    std::forward<Args>(args)...);
}

The template argument Internal is for the recursive_wrapper. When doing some of the internal visitors, we want the recursive_wrapper type, not the type that it's holding. I will explain that in more detail later.

The class do_visit is defined as a template class, with a templated operator(), this is so that it can have two sets of template arguments, the set of types, and the arguments that the visitor will pass. It's definition is as follows:

template <typename... AllTypes>
struct do_visit                                                             
{       
  template
  <     
    typename Internal,
    typename VoidPtrCV,
    typename Visitor,
    typename... Args
  >     
  typename Visitor::result_type
  operator()
  (     
    Internal&& internal,
    size_t which,
    VoidPtrCV&& storage,
    Visitor& visitor,
    Args&&... args
  )     
  {     
    typedef typename Visitor::result_type (*whichCaller)
      (Internal&&, VoidPtrCV&&, Visitor&&, Args&&...);
        
    static whichCaller callers[sizeof...(AllTypes)] =
      { 
        &visitor_caller<Internal&&, AllTypes,
          VoidPtrCV&&, Visitor, Args&&...>...
      } 
    ;   
        
    assert(which >= 0 && which < sizeof...(AllTypes));
        
    return (*callers[which])
      ( 
        std::forward<Internal>(internal),
        std::forward<VoidPtrCV>(storage),
        std::forward<Visitor>(visitor),
        std::forward<Args>(args)...
      );
  }     
};

There is a lot here, but it doesn't really do much. The magic is all in the static array callers. There is an entry for every possible type that can be stored in the Variant, and each entry is a function which calls the visitor, after casting the storage to the appropriate type, with the object and the arguments supplied. So what we have is a different array for every combination of types, visitors, and arguments that are called on any Variant. Then we simply call the appropriate function, indexing it with the which variable.

Most of the functionality of the variant is implemented with the visitor---copy
construction, move construction, destruction, assignment, and the get function. The only thing left is initialisation. The reason that we need an internal visit is to handle the four previously mentioned operations. When copying and deleting an object, we need a reference to the recursive_wrapper that holds it, not just the actual object. Unlike when a user uses a Variant, they don't care about the recursive_wrapper, the whole point is to pretend that we're only holding exactly the types that the user wanted.

Initialising

To initialise a Variant, the appropriate tag needs to be chosen for the object. To do this, we create a template class who has an initialise function for the first type from a parameter pack, and derives from itself but instantiated with the remainder of the parameter pack. It also counts which type that it is handling. This way, calling initialise will use the normal rules of C++ to decide which overload to call. If the object being initialised isn't unambiguously convertible to one of the types, then that is a user error.

The initialiser looks like:

template <size_t Which, typename... MyTypes>
struct initialiser;
 
template <size_t Which, typename Current, typename... MyTypes>
struct initialiser<Which, Current, MyTypes...>
  : public initialiser<Which+1, MyTypes...>
{
  typedef initialiser<Which+1, MyTypes...> base;
  using base::initialise;
 
  static void
  initialise(Variant& v, Current&& current)
  {
    v.construct(std::forward<Current>(current));
    v.indicate_which(Which);
  }
 
  static void
  initialise(Variant& v, const Current& current)
  {
    v.construct(current);
    v.indicate_which(Which);
  }
};

This is called from the Variant's perfect forwarding constructor.

The get function

Lastly, we have the get function. This allows the user to retrieve a value from the Variant in a typesafe manner. One can request a type from the Variant, and if that is not what is being held, then an exception will be thrown, or a null pointer returned, depending on the version of get.

The get function uses the class get_visitor. This is a visitor which checks if the type we want is the type contained in the Variant. Its definition is below:

template <typename T>
struct get_visitor
{
  typedef T* result_type;

  result_type
  operator()(T& val) const
  {
    return &val;
  }

  template <typename U>
  result_type
  operator()(const U& u) const
  {
    return nullptr;
  }
};

Here is one of the versions of the get function to show how the visitor is called. The idea is that if get_visitor::operator() matches the type requested, then the object is returned, otherwise nullptr is returned.

template <typename T, typename First, typename... Types>
T&
get (Variant<First, Types...>& var)
{
  T* t = apply_visitor(get_visitor<T>(), var);
  if (t == nullptr){throw bad_get();}

  return *t;
}

For this particular version of get, since we need a reference, if an invalid object is returned, we will throw bad_get.

The complete code can be found at http://www.cse.unsw.edu.au/~jarrydb/thenewcpp/variant.hpp
and http://www.cse.unsw.edu.au/~jarrydb/thenewcpp/mpl.hpp

About these ads
7 Comments
  1. Larry E permalink

    VisitorB::result_type is int; yet, the operator()’s all return void, which contradicts
    the previous paragraph’s statement, “the return type is typedef’ed as result_type”.

  2. Stefan A. permalink

    Great work. But what about licencing the code under a less restrictive licence than GPL so it can be used in closed sourced applications, too? MIT, LGPL, Boost?

Trackbacks & Pingbacks

  1. Alignment support « The New C++
  2. Improving the variant class | The New C++
  3. Code on github | The New C++

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: