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.

Racoon

50 types in boost::variant, why would anyone need that many? C++ is not a scripting language, if you don't want a statically typed language; it's not for you. – Muraida

Take a look at boost::any, if boost::variant is too constricting. Maybe combine those two even... – Bring

Show me an example of "multi-visitation" and I will write it for you. – Observation

@polkovnikov.ph: bottom of the Boost Variant Tutorial, it's about visiting multiple variants at once apply_visitor(visitor, v0, v1, v2, ...) – Clatter

@FilipRoséen-refp I want a high-performance-statically-typed language resolved at compile time. What I don't want are stupid limits coming from older dialects of it. – Racoon

@Bring I would like to avoid boost::any and any other dynamic_cast in order to achieve multiple dispatch at compile time. If it wasn't for that anachronistic fixed limit boost::variant would have been perfect. – Racoon

How many do you need? Anyway, I think with true variadic templates it should be possible... – Bring

@Deduplicator: the real challenge in visitation is passing the arguments. Fortunately here we can probably go with references, which tremendously help. – Clatter

@DarioP: by the way, this library you found is an interesting prototype, but don't trust it too much. For example, the assignment operator is written as destruct + init, so if the init throws you could be left in a sticky mess. It also does not handle alignment correctly, ... In short, not production ready. – Clatter

I don't have the time to answer right now, however an easy way to go about it is what I used here. Only deal with one argument at time, bind it, and move to the next. – Clatter

@MatthieuM. thanks, that answer of yours escaped from my previous searches! I'll have a look at it. I know about the alignment and the "Never-Empty" problems, I may find another design, but the fact that a full variadic variant is still missing from "official sources" got my curiosity. – Racoon

FWIW, I've written one... It also supports move-only types. The interface is slightly different from the boost one, since I disliked the implicit conversion between variant types, and the strange behaviour in which assignment sometimes caused reassignment to the contained type, and sometimes caused construction of the contained type. It lacks support for references (again, I found the boost semantics to be confusing and not sufficiently useful). – Koehler

Look towards the bottom of the file for the multi-visitation implementation. – Koehler

@Mankarse: if you were to extract your implementation of N-Ary Flattener, it think it would make a good answer. – Clatter

boost::variant doesn't do and cannot do static dispatch. It is an illusion. boost::variant implements a tagged union and dispatches on the tag. – Newcomer

@n.m. you are right. Still most of the work is done at compile time and I like very much the resulting code which is very clean compared to a bunch of pointers, virtuals and/or dynamic_casts. – Racoon

Cleanness is in the eye of the beholder. In my book, a tagged union with 50+ variants gets thrown out of the code review faster than you can say "static compile-time dispatch". But don't let it stop you from doing what's the right thing in your eyes. – Newcomer

In addition, in may totally unscientific tests double dispatch using boost::variant consistently takes about 10% to 20% longer than double dispatch implemented the good old way with a bunch of pointers and virtual functions (but no dynamic_cast). – Newcomer

@n.m. I think that this depends a lot on the number of types and on the compiler as well: codeproject.com/Articles/23304/… However what I really cannot understand is how a program like this codereview.stackexchange.com/questions/52495/… could be beaten in simplicity by the good old way.. I'm not experienced and I'm not sure of anything, I just want to understand! – Racoon

The good old way is not necessarily that good in the simplicity department, it just demonstrates that static dispatch (whatever it is) is overrated. You don't need ultra-fast dispatch in this kind of task anyway. You probably need easy extensibility more than you need speed. Neither solution is easily extensible. – Newcomer

Extensibility among other things means not having to change old code when adding new code. This is called Open/Closed Principle (google). You especially need extensibility when you have significantly more than 2 or 3 variants (something like 50 is way too much). You can have extensibility something like acyclic visitor (google). It normally uses dynamic_cast internally, but who cares, it's a library component, and performance is not important here. (You don't want to look inside boost either). – Newcomer

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.

Koehler

I don't know who downvoted and why. I cannot understand this code with my current knowledge. However I downloaded and tested it as black box with a simple main like this codereview.stackexchange.com/questions/52495/… but I get a compilation error: variant.h:375:40: error: request for member 'operator()' is ambiguous std::forward<Visitor>(v) when I try to allocate the vector of variants. (g++ 4.9) – Racoon

@DarioP: It looks like I got a bit too clever and triggered a g++ bug (maybe... I'm not too sure what the standard says about the particular piece of code, just that clang compiled the old version). Try this version (g++-4.8, clang++). – Koehler

+1 because this handles l-value/r-value differences, but honestly the coding style is not to my taste. This idea of cramming everything in a single statement (mixing definitions of new types, construction of new values, and call of methods altogether) makes it very hard to read. – Clatter

@MatthieuM.: I've edited it to split things up into multiple statements, though I'm honestly not convinced that it is any more readable. There is still the same amount of information to process, just it now takes up more lines of source-code. (Maybe I'm just used to the other style though). – Koehler

@Mankarse: Thanks! It is subjective, I admit. I wish I could upvote a second time but... – Clatter

I've been tracking the development of your variant and the last commit (2014-06-17) finally compiles also with gcc49. I tested it pushing into more than 100 types and I'm impressed by performances! You should document and publish it, it looks much better than the Boost's one. – Racoon

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

Clatter