Is there a variadic template variant with a multi visitation method?

Question

I hit the limit of 50 types in boost::variant. I found this nice self-contained header but it lacks the multi visitation feature (I actually need the double visitation).

I tried to look a bit after it but such method seems very ambitious and clashes with my lack of experience with metaprogramming...

It would be wonderful if you could point out a precooked variant implementation or give some advices to expand the one that I liked above, thanks!

---

To Filip Roséen and upvoters: here you find a basic example of the design that I'm considering. Feel free to add more in-depth comments about that.

Answer 1

EDIT: Boost now supports multi-visitation, as does C++17 variant.

---

If you have a variant type with a unary visit member function, this can be extended to an n-ary-apply_visitor function as follows:

Include the necessary standard library dependencies:

#include <tuple>
#include <type_traits>
#include <utility> //For C++14 `std::integer_sequence`.
                   //If you don't want to use C++14, write your own.

Now a helper function for making a new tuple identical to an existing tuple but without the first element:

template<std::size_t ...S, typename Head, typename ...Tail>
std::tuple<Tail...> tuple_tail_impl(
    index_sequence<S...>,
    std::tuple<Head, Tail...> const &in_tuple)
{
    struct In {
        template<std::size_t N>
        using ElementType =
            typename std::tuple_element<N, std::tuple<Head, Tail...>>::type;
    };
    return std::tuple<Tail...>(
        std::forward<In::ElementType<S+1>>(std::get<S+1>(in_tuple))...);
}

template<typename Head, typename ...Tail>
std::tuple<Tail...> tuple_tail(std::tuple<Head, Tail...> const& in_tuple) {
    return tuple_tail_impl(index_sequence_for<Tail...>(), in_tuple);
}

Now, the class that does the work, and a helper function for creating that class:

template<typename Visitor, typename MatchedValueTuple, typename... TailVariants>
struct NAryVisitorFlattener;

template<typename Visitor, typename MatchedValueTuple, typename... TailVariants>
NAryVisitorFlattener<Visitor, MatchedValueTuple, TailVariants...>
make_NAryVisitorFlattener(
    Visitor &&visitor,
    MatchedValueTuple &&matchedValues,
    std::tuple<TailVariants...> &&tailVariants);

In the recursive case, NAryVisitorFlattener sequentially calls the apply member function on every variant and builds up the resulting values in MatchedValueTuple.

template<
    typename Visitor,
    typename MatchedValueTuple,
    typename CurrentVariant,
    typename... TailVariants>
struct NAryVisitorFlattener<
    Visitor, MatchedValueTuple, CurrentVariant, TailVariants...>
{
    typedef typename
        std::remove_reference<Visitor>::type::result_type result_type;

    Visitor visitor;
    MatchedValueTuple matchedValues;
    std::tuple<CurrentVariant, TailVariants...> tailVariants;

    template<typename A>
    result_type operator()(A &&a)
    {
      auto flattener = make_NAryVisitorFlattener(
        std::forward<Visitor>(visitor),
        std::tuple_cat(matchedValues, std::forward_as_tuple(std::forward<A>(a))),
        tuple_tail(tailVariants));

      return std::forward<CurrentVariant>(std::get<0>(tailVariants))
                                                             .visit(flattener);
    }
};

In the base-case, apply has been called on every variant, and the visitor is called with the values in MatchedValueTuple:

template<typename Visitor, typename MatchedValueTuple>
struct NAryVisitorFlattener<Visitor, MatchedValueTuple> {
    typedef typename
        std::remove_reference<Visitor>::type::result_type result_type;

    Visitor visitor;
    MatchedValueTuple matchedValues;
    std::tuple<> tailVariants;

    template<typename A>
    result_type operator()(A &&a) {
        return callFunc(
            std::make_index_sequence<std::tuple_size<MatchedValueTuple>::value>(),
            std::forward<A>(a));
    }

    template<std::size_t N>
    using MatchedValueType =
        typename std::tuple_element<N,MatchedValueTuple>::type;

    template<std::size_t ...S, typename A>
    result_type callFunc(std::index_sequence<S...>, A &&a) {
        return std::forward<Visitor>(visitor)(
            std::forward<MatchedValueType<S>>(matchedValues))...,
            std::forward<A>(a));
    }
};

And the definition of the helper function declared earlier:

template<typename Visitor, typename MatchedValueTuple, typename... TailVariants>
NAryVisitorFlattener<Visitor, MatchedValueTuple, TailVariants...>
make_NAryVisitorFlattener(
    Visitor &&visitor,
    MatchedValueTuple &&matchedValues,
    std::tuple<TailVariants...> &&tailVariants)
{
    return {
        std::forward<Visitor>(visitor),
        std::forward<MatchedValueTuple>(matchedValues),
        std::forward<std::tuple<TailVariants...>>(tailVariants)
    };
}

Now, the function you've been waiting for. Get the ball rolling with the first NAryVisitorFlattener:

template<typename Visitor, typename VariantA, typename... Variants>
typename std::remove_reference<Visitor>::type::result_type
apply_visitor(Visitor &&visitor, VariantA &&variantA, Variants &&...variants) {

  auto flattener = make_NAryVisitorFlattener(
    std::forward<Visitor>(visitor),
    std::tuple<>{},
    std::forward_as_tuple(std::forward<Variants>(variants)...));

  return std::forward<VariantA>(variantA).visit(flattener);
}

This is all taken from my complete C++11-compatible variant implementation available here.

Answer 2

Okay, since I was interested in the issue, I must admit to play around with it.

To overcome the limitation in Boost I implemented a lightweight prototype-level variant in terms of variadic templates that I will not link here (the full code is available on Coliru).

Instead, I will link to a simplistic implementation of multi-visitation. It is not perfect, especially as it does not respect l-value/r-valueness. Still, it has the conceptual advantage of being simple, and thus easy to understand.

If you wish to skip to the code, feel free, it's at the bottom. Here are some explanations prior to it.

The first trick is mplementing a fast dynamic dispatch is done with an array of pointer to functions:

• a static template function is created, with uniform signature, that will process the parameters according to one type

• an array of such functions is instantiated, with one element per element of the variadic template pack

• indexing in the array is done via a runtime index

This boils down to:

template <size_t N>
void print_number() { std::cout << N << "\n"; }

template <size_t... Is>
void doit(size_t index) {
    using Printer = void (*)();

    static Printer const AllPrinters[] = { &printer_number<Is>... };

    Printer const printer = AllPrinters[index];
    printer();
}

The array should be placed in .rodata (it's constant). This is slightly different from a v-ptr/v-table dispatch because the index is a runtime index, whereas with v-ptr/v-table dispatch the index is generally known at compile-time (3rd method in the table).

The second trick is implementing n-ary visitation as a succession of unary visitations:

• dispatch one variant at a time, passing the other variants as-is

• use the stack and recursion to collect the arguments one a time

• forward all arguments to base visitor

The forwarding visitor in my implementation is NaryVisitor, the co-recursion is implemented via the ping-pong between apply_nary_visitor_impl and NaryApplier:

• the former uses the array trick above to find the correct type in the variant to invoke stuff on
• the latter wraps the visitor and obtained reference in the NaryVisitor adaptor, and recurse on a N-1 list of remaining variants

The co-recursion is actually typical to unpack two-dimensional variadics.

Note: there may be hope in improving the implementation to keep the distinction of l-values and r-values, but already getting this to compile is quite a battle...

---

The full code for n-ary visitation:

namespace internal {
    template <typename Visitor, typename T>
    struct NaryVisitor {
        using result_type = typename Visitor::result_type;

        NaryVisitor(Visitor& visitor, T& t): visitor(visitor), ref(t) {}
        Visitor& visitor;
        T& ref;

        template <typename... Args>
        auto operator()(Args&&... args) -> result_type {
            return visitor(ref, std::forward<Args>(args)...);
        } // apply
    }; // struct NaryVisitor

    template <typename Visitor, typename T0, typename... Ts, typename... Vs>
    auto apply_nary_visitor_impl(
        Visitor& visitor, variant<T0, Ts...>&& v0, Vs&&... vs
    )
    -> typename Visitor::result_type;

    template <typename Visitor, typename Variant>
    struct NaryApplier {
        using result_type = typename Visitor::result_type;

        NaryApplier(Visitor& visitor, Variant& variant):
            visitor(visitor), variant(variant) {}

        Visitor& visitor;
        Variant& variant;

        template <typename T>
        auto apply() -> result_type {
            return visitor(*variant.template get<T>());
        }

        template <typename T, typename V0, typename... Vs>
        auto apply(V0&& v0, Vs&&... vs) -> result_type {
            NaryVisitor<Visitor, T> nary{
                visitor,
                *variant.template get<T>()
            };
            return apply_nary_visitor_impl(nary,
                                           std::forward<V0>(v0),
                                           std::forward<Vs>(vs)...);
        }
    }; // struct NaryApplier

    template <typename Visitor, typename T0, typename... Ts, typename... Vs>
    auto apply_nary_visitor_impl(
        Visitor& visitor, variant<T0, Ts...>& v0, Vs&&... vs
    )
    -> typename Visitor::result_type
    {
        using result_type = typename Visitor::result_type;

        using Variant = variant<T0, Types...>;
        using Applier = internal::NaryApplier<Visitor, Variant>;
        using Member = result_type (Applier::*)(Vs&&...);

        static Member const members[] = {
            (&Applier::template apply<T0, Vs...>), 
            (&Applier::template apply<Types, Vs...>)...
        };

        Member const m = members[v0.which()];
        Applier a{visitor, v0};
        return (a.*m)(std::forward<Vs>(vs)...);
    } // apply_nary_visitor_impl

} // namespace internal

template <typename Visitor, typename... Variants>
auto apply_nary_visitor(Visitor&& visitor, Variants&&... vs)
-> typename Visitor::result_type
{
    return internal::apply_nary_visitor_impl(visitor,
                                             std::forward<Variants>(vs)...);
} // apply_nary_visitor