Variant Visitation

Introduction

variant reached a design consensus at the fall ISO C++ committee meeting in Kona, HI, USA. While the design is still not final, I’ve been experimenting to deliver a reference implementation.

In this post, I’ll be presenting my approach and implementation of the visitation mechanism. There are interesting parts in the implementation of variant itself, but a lot of those aspects are already covered in Eggs.Variant - Part I and Eggs.Variant - Part II by Agustín “K-ballo” Bergé.

Variant

Let us get started with a minimal variant interface. This will give us a frame of reference throughout the post. We only need the following:

  • v.index(): Returns the index of the currently stored value.
  • get<I>(v): Returns the currently stored value if v.index() == I else throws std::bad_variant_access.

Visitation

Here is the signature of visit:

template <typename F, typename... Vs>
decltype(auto) visit(F &&f, Vs &&... vs);

It invokes f with the currently stored value of each of the vs....

Consider the following function:

// `F` and `Vs...` is in context from outer scope.
template <std::size_t... Is>
constexpr decltype(auto) dispatch(F f, Vs... vs) {
  static_assert(sizeof...(Is) == sizeof...(Vs));
  std::invoke(static_cast<F>(f), get<Is>(static_cast<Vs>(vs))...);
}

Since get<I>(v) returns the currently stored value of v for us, we ultimately want to invoke dispatch<Is...>(f, vs...) where Is... are the compile-time values of vs.index()....

How do we do that?

N-dimensional Matrix of Function Pointers

The approach is to build an N-dimensional matrix of function pointers (representative of the N-ary cartesian product), then use vs.index()... to index into the matrix at runtime where the appropriate &dispatch<Is...> will be waiting for us.

For example, given variant<A, B> we have the following function matrix:

A B
&dispatch<0> &dispatch<1>

given variant<A, B> and variant<X, Y, Z>, we have:

  X Y Z
A &dispatch<0, 0> &dispatch<0, 1> &dispatch<0, 2>
B &dispatch<1, 0> &dispatch<1, 1> &dispatch<2, 2>

Implementation

make_fmatrix

The base case should look familiar. Given F, Vs... and Is..., it returns the function pointer &dispatch<Is...> from above.

// Base case for `make_fmatrix_impl`.
template <typename F, typename... Vs, std::size_t... Is>
constexpr auto make_fmatrix_impl(std::index_sequence<Is...>) {
  struct dispatcher {
    static constexpr decltype(auto) dispatch(F f, Vs... vs) {
      return std::invoke(static_cast<F>(f), get<Is>(static_cast<Vs>(vs))...);
    }
  };
  return &dispatcher::dispatch;
}

The recursive case implements the N-ary cartesian product resulting in the N-dimensional matrix. We build this recursively, keeping the first std::index_sequence as our accumulator. For each given list, we make a recursive call with each of its elements appended onto the accumulator, and the rest of the lists.

// Recursive case for `make_fmatrix_impl`.
template <typename F,
          typename... Vs,
          std::size_t... Is,
          std::size_t... Js,
          typename... Ls>
constexpr auto make_fmatrix_impl(
    std::index_sequence<Is...>, std::index_sequence<Js...>, Ls... ls) {
  return std::experimental::make_array(
      make_fmatrix_impl<F, Vs...>(std::index_sequence<Is..., Js>{}, ls...)...);
}

Let’s go through an example with three lists , , :

make_fmatrix bootstraps the above with the empty list [] as the initial accumulator, and index sequences [0, tuple_size_v<V_i>) for each of the V_i in Vs....

template <typename F, typename... Vs>
constexpr auto make_fmatrix() {
  return make_fmatrix_impl<F, Vs...>(
      std::index_sequence<>{},
      std::make_index_sequence<std::tuple_size<std::decay_t<Vs>>::value>{}...);
}

Now we can construct a static constexpr instance of fmatrix within visit.

template <typename F, typename... Vs>
decltype(auto) visit(F &&f, Vs &&... vs) {
  static constexpr auto fmatrix = make_fmatrix<F &&, Vs &&...>();
  /* ... */
}

We’re now left with the task of accessing the fmatrix with vs.index().... Since we can’t say something like: fmatrix([vs.index()]...) to mean fmatrix[i_0][i_1]...[i_N], we need to introduce a helper function.

at for N-dimensional arrays

at(array, i_0, i_1, ..., i_N) returns array[i_0][i_1]...[i_N].

// Base case for `at_impl`.
template <typename T>
constexpr T &&at_impl(T &&elem) { return std::forward<T>(elem); }

// Recursive case for `at_impl`.
template <typename T, typename... Is>
constexpr auto &&at_impl(T &&elems, std::size_t i, Is... is) {
  return at_impl(std::forward<T>(elems)[i], is...);
}

template <typename T, typename... Is>
constexpr auto &&at(T &&elems, Is... is) {
  // Commented out since `std::rank` is not defined for `std::array`.
  // static_assert(std::rank<std::decay_t<T>>::value == sizeof...(Is));
  return at_impl(std::forward<T>(elems), is...);
}

Alright, almost there! We can now use at to retrieve the &dispatch<Is...> corresponding to vs.index()... in fmatrix and invoke it like this:

template <typename F, typename... Vs>
decltype(auto) visit(F &&f, Vs &&... vs) {
  static constexpr auto fmatrix = make_fmatrix<F &&, Vs &&...>();
  return at(fmatrix, vs.index()...)(std::forward<F>(f), std::forward<Vs>(vs)...);
}

That’s it!

We’ve managed to decouple the implementation of variant and the visitation mechanism, generalized to any N. This means that we can implement parts of variant that required single visitation using visit. For example, copy construction could look something along the lines of:

template <typename... Ts>
class variant {
public:
  /* ... */

  variant(const variant &that) : variant{/* valueless_by_exception */} {
    if (!that.valueless_by_exception()) {
      visit([this](auto &&value) {
              this->construct(std::forward<decltype(value)>(value));
            },
            that);
    }
  }

  /* ... */
};

NOTE: It’s actually a little more complicated than this because duplicate types in a variant have distinct states. We therefore need to initialize the alternative in this at the same index as the one stored in that.

The full reference implementation of std::variant can be found here.

Thanks to Agustín “K-ballo” Bergé for reviewing this post!