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 ifv.index() == Ielse throwsstd::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!