Generic Lambda Visitors, or Writing Haskell in C++0x (Part 4)

In part three, we built a generic alternative to visitors that used lambdas. Now we’ll do a few largely pointless but potentially interesting bits of trickery.

Previously, we worked out the return type of our when function by looking at the return type of the first lambda. Let’s get a bit more adventurous. We’ll make a class that works out what the return type should be.

template <typename... Funcs_>
struct WhenReturnType;

template <typename Val_, typename... Funcs_>
typename WhenReturnType<Funcs_...>::Type
when(Val_ && val, Funcs_ && ... funcs)
{
    LambdaVisitor<typename WhenReturnType<Funcs_...>::Type, Funcs_...> visitor(funcs...);
    return accept_returning<typename WhenReturnType<Funcs_...>::Type>(val, visitor);
}

For starters, we’ll say that if the first function returns void, our return type is void; otherwise, it’s an error:

template <typename... Funcs_>
struct WhenReturnType;

template <typename FirstFunc_, typename... Funcs_>
struct WhenReturnType<FirstFunc_, Funcs_...>
{
    typedef typename std::conditional<
        std::is_same<typename LambdaParameterTypes<FirstFunc_>::ReturnType, void>::value,
        void,
        UnknownTypeForOneOf
        >::type Type;
};

Let’s get a bit more adventurous. What if one lambda returns an int, and another returns a long? We could return a long. Similarly, if one returns a char, and another returns a double, we could return a double. And that’s what std::common_type does:

template <typename... Funcs_>
struct WhenReturnType;

template <typename FirstFunc_, typename... Funcs_>
struct WhenReturnType<FirstFunc_, Funcs_...>
{
    typedef typename std::conditional<
        std::is_same<typename LambdaParameterTypes<FirstFunc_>::ReturnType, void>::value,
        void,
        typename std::common_type<typename LambdaParameterTypes<Funcs_>::ReturnType ...>::type
        >::type Type;
};

Except, std::common_type isn’t useful for user defined types. What we really want to do is say “return a type that holds a value of any of the return types we could get”. If only we’d just spent the past few pages developing such a type…

First, though, let’s work out how to just return a value of a given type, if all the return types are the same:

template <typename... Funcs_>
struct AllReturnSame;

template <typename Func_>
struct AllReturnSame<Func_>
{
    enum { value = true };
};

template <typename A_, typename B_, typename... Funcs_>
struct AllReturnSame<A_, B_, Funcs_...>
{
    enum { value = std::is_same<typename LambdaParameterTypes<A_>::ReturnType, typename LambdaParameterTypes<B_>::ReturnType>::value &&
        AllReturnSame<B_, Funcs_...>::value };
};

template <typename... Funcs_>
struct WhenReturnType;

template <typename FirstFunc_, typename... Funcs_>
struct WhenReturnType<FirstFunc_, Funcs_...>
{
    typedef typename std::conditional<
        AllReturnSame<FirstFunc_, Funcs_...>::value,
        typename LambdaParameterTypes<FirstFunc_>::ReturnType,
        UnknownTypeForOneOf
        >::type Type;
};

Note that we no longer have to handle void specially here.

Next, we’ll add in handling for the easy case where all the lambdas return different things:

template <typename... Funcs_>
struct WhenReturnType;

template <typename FirstFunc_, typename... Funcs_>
struct WhenReturnType<FirstFunc_, Funcs_...>
{
    typedef typename std::conditional<
        AllReturnSame<FirstFunc_, Funcs_...>::value,
        typename LambdaParameterTypes<FirstFunc_>::ReturnType,
        OneOf<typename LambdaParameterTypes<FirstFunc_>::ReturnType, typename LambdaParameterTypes<Funcs_>::ReturnType...>
        >::type Type;
};

Again, note the complex expression used to the left of a ... operator.

Unfortunately, this barfs spectacularly if, say, two lambdas return an int and one returns a string. We need a way of removing the duplicates from a type list. It’s not possible to pass around two type lists directly, so we’ll first need a helper struct that stores all the types we’ve seen so far:

template <typename...>
struct SeenSoFar
{
};

Next, let’s have a helper that tells us whether a particular type is already in a SeenSoFar list:

template <typename...>
struct AlreadySeen;

template <typename Query_>
struct AlreadySeen<SeenSoFar<>, Query_>
{
    enum { value = false };
};

template <typename Query_, typename A_, typename... Rest_>
struct AlreadySeen<SeenSoFar<A_, Rest_...>, Query_>
{
    enum { value = std::is_same<Query_, A_>::value || AlreadySeen<SeenSoFar<Rest_...>, Query_>::value };
};

We also need to be able to create a new SeenSoFar with an extra type:

template <typename...>
struct ExtendSeenSoFar;

template <typename New_, typename... Current_>
struct ExtendSeenSoFar<New_, SeenSoFar<Current_...> >
{
    typedef SeenSoFar<Current_..., New_> Type;
};

Now we can put all that together:

template <typename...>
struct OneOfDeduplicatorBuilder;

template <typename... Values_>
struct OneOfDeduplicatorBuilder<SeenSoFar<Values_...> >
{
    typedef OneOf<Values_...> Type;
};

template <typename SeenSoFar_, typename Next_, typename... Funcs_>
struct OneOfDeduplicatorBuilder<SeenSoFar_, Next_, Funcs_...>
{
    typedef typename std::conditional<
        AlreadySeen<SeenSoFar_, Next_>::value,
        typename OneOfDeduplicatorBuilder<SeenSoFar_, Funcs_...>::Type,
        typename OneOfDeduplicatorBuilder<typename ExtendSeenSoFar<Next_, SeenSoFar_>::Type, Funcs_...>::Type
            >::type Type;
};

template <typename... Funcs_>
struct OneOfDeduplicator
{
    typedef typename OneOfDeduplicatorBuilder<SeenSoFar<>, Funcs_...>::Type Type;
};

And we can use it:

template <typename... Funcs_>
struct WhenReturnType;

template <typename FirstFunc_, typename... Funcs_>
struct WhenReturnType<FirstFunc_, Funcs_...>
{
    typedef typename std::conditional<
        AllReturnSame<FirstFunc_, Funcs_...>::value,
        typename LambdaParameterTypes<FirstFunc_>::ReturnType,
        typename OneOfDeduplicator<
            typename LambdaParameterTypes<FirstFunc_>::ReturnType,
            typename LambdaParameterTypes<Funcs_>::ReturnType ...>::Type
        >::type Type;
};

Letting us do horrible things like:

struct SomeType
{
};

int main(int, char *[])
{
    OneOf<int, std::string, SomeType> s(123);

    std::cout << when(
            when(s,
                [] (int & x)               -> std::string { return std::string(++x, 'x'); },
                [] (std::string & x)       -> int         { x.append(" spanker"); return x.length(); },
                [] (const SomeType &)      -> int         { return 42; }
                ),
            [] (const int x)           -> int { return x; },
            [] (const std::string & x) -> int { return x.length(); }
            ) << std::endl;

    return EXIT_SUCCESS;
}

You’ll note we’re explicitly specifying the return types. This is because std::string::length() probably doesn’t return an int, and our code does overload resolution on references, which allows conversions for classes but not integral types. Fixing this in a sane way is left as an easy exercise for the reader — one possibility is to see if the return types of all the lambdas have a std::common_type, and using that rather than a OneOf if they do. Implementing this is left to the reader; in the mean time, our code in full looks like:

#include <memory>
#include <type_traits>
#include <utility>

struct UnknownTypeForOneOf;

template <typename Want_, typename... Types_>
struct SelectOneOfType;

template <typename Want_>
struct SelectOneOfType<Want_>
{
    typedef UnknownTypeForOneOf Type;
};

template <typename Want_, typename Try_, typename... Rest_>
struct SelectOneOfType<Want_, Try_, Rest_...>
{
    typedef typename std::conditional<
        std::is_same<Want_, Try_>::value,
        Try_,
        typename SelectOneOfType<Want_, Rest_...>::Type
            >::type Type;
};

template <typename Type_>
struct ParameterTypes;

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_)>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_) const>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename Lambda_>
struct LambdaParameterTypes
{
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::FirstParameterType FirstParameterType;
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::ReturnType ReturnType;
};

template <typename Type_>
struct OneOfVisitorVisit
{
    virtual void visit(Type_ &) = 0;
};

template <typename... Types_>
struct OneOfVisitor :
    OneOfVisitorVisit<Types_>...
{
};

template <typename Visitor_, typename Underlying_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperVisit;

template <typename Visitor_, typename Underlying_, typename Result_>
struct OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_> :
    Visitor_
{
    Underlying_ & underlying;
    std::function<Result_ ()> execute;

    OneOfVisitorWrapperVisit(Underlying_ & u) :
        underlying(u)
    {
    }
};

template <typename Visitor_, typename Underlying_, typename Result_, typename Type_, typename... Rest_>
struct OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Type_, Rest_...> :
    OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Rest_...>
{
    OneOfVisitorWrapperVisit(Underlying_ & u) :
        OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Rest_...>(u)
    {
    }

    Result_ visit_returning(Type_ & t)
    {
        return this->underlying.visit(t);
    }

    virtual void visit(Type_ & t)
    {
        this->execute = std::bind(&OneOfVisitorWrapperVisit::visit_returning, this, std::ref(t));
    }
};

template <typename Underlying_, typename Result_, typename... Types_>
struct OneOfVisitorWrapper :
    OneOfVisitorWrapperVisit<OneOfVisitor<Types_...>, Underlying_, Result_, Types_...>
{
    OneOfVisitorWrapper(Underlying_ & u) :
        OneOfVisitorWrapperVisit<OneOfVisitor<Types_...>, Underlying_, Result_, Types_...>(u)
    {
    }
};

template <typename... Types_>
struct OneOfValueBase
{
    virtual ~OneOfValueBase() = 0;

    virtual void accept(OneOfVisitor<Types_...> &) = 0;
    virtual void accept(OneOfVisitor<const Types_...> &) const = 0;
};

template <typename... Types_>
OneOfValueBase<Types_...>::~OneOfValueBase() = default;

template <typename Type_, typename... Types_>
struct OneOfValue :
    OneOfValueBase<Types_...>
{
    Type_ value;

    OneOfValue(const Type_ & type) :
        value(type)
    {
    }

    virtual void accept(OneOfVisitor<Types_...> & visitor)
    {
        static_cast<OneOfVisitorVisit<Type_> &>(visitor).visit(value);
    }

    virtual void accept(OneOfVisitor<const Types_...> & visitor) const
    {
        static_cast<OneOfVisitorVisit<const Type_> &>(visitor).visit(value);
    }
};

template <typename... Types_>
class OneOf
{
    private:
        std::unique_ptr<OneOfValueBase<Types_...> > _value;

    public:
        template <typename Type_>
        OneOf(const Type_ & value) :
            _value(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value})
        {
        }

        OneOf(const OneOf & other) = delete;

        OneOf(OneOf && other) :
            _value(std::move(other._value))
        {
        }

        template <typename Type_>
        OneOf & operator= (const Type_ & value)
        {
            _value.reset(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value});
            return *this;
        }

        OneOf & operator= (const OneOf & other) = delete;

        OneOf & operator= (OneOf && other)
        {
            _value = std::move(other._value);
            return *this;
        }

        OneOfValueBase<Types_...> & value()
        {
            return *_value;
        }

        const OneOfValueBase<Types_...> & value() const
        {
            return *_value;
        }
};

template <typename Visitor_, typename Result_, typename OneOf_>
struct OneOfVisitorWrapperTypeFinder;

template <typename Visitor_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperTypeFinder<Visitor_, Result_, const OneOf<Types_...> &>
{
    typedef OneOfVisitorWrapper<Visitor_, Result_, const Types_...> Type;
};

template <typename Visitor_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperTypeFinder<Visitor_, Result_, OneOf<Types_...> &>
{
    typedef OneOfVisitorWrapper<Visitor_, Result_, Types_...> Type;
};

template <typename Result_, typename OneOf_, typename Visitor_>
Result_
accept_returning(OneOf_ && one_of, Visitor_ && visitor)
{
    typename OneOfVisitorWrapperTypeFinder<Visitor_, Result_, OneOf_>::Type visitor_wrapper(visitor);
    one_of.value().accept(visitor_wrapper);
    return visitor_wrapper.execute();
}

template <typename OneOf_, typename Visitor_>
void accept(OneOf_ && one_of, Visitor_ && visitor)
{
    accept_returning<void>(one_of, visitor);
}

template <typename Result_, typename... Funcs_>
struct LambdaVisitor;

template <typename Result_>
struct LambdaVisitor<Result_>
{
    void visit(struct NotReallyAType);
};

template <typename Result_, typename Func_, typename... Rest_>
struct LambdaVisitor<Result_, Func_, Rest_...> :
    LambdaVisitor<Result_, Rest_...>
{
    Func_ & func;

    LambdaVisitor(Func_ & f, Rest_ & ... rest) :
        LambdaVisitor<Result_, Rest_...>(rest...),
        func(f)
    {
    }

    Result_ visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        return func(v);
    }

    using LambdaVisitor<Result_, Rest_...>::visit;
};

template <typename... Funcs_>
struct AllReturnSame;

template <typename Func_>
struct AllReturnSame<Func_>
{
    enum { value = true };
};

template <typename A_, typename B_, typename... Funcs_>
struct AllReturnSame<A_, B_, Funcs_...>
{
    enum { value = std::is_same<typename LambdaParameterTypes<A_>::ReturnType, typename LambdaParameterTypes<B_>::ReturnType>::value &&
        AllReturnSame<B_, Funcs_...>::value };
};

template <typename...>
struct SeenSoFar
{
};

template <typename...>
struct ExtendSeenSoFar;

template <typename New_, typename... Current_>
struct ExtendSeenSoFar<New_, SeenSoFar<Current_...> >
{
    typedef SeenSoFar<Current_..., New_> Type;
};

template <typename...>
struct AlreadySeen;

template <typename Query_>
struct AlreadySeen<SeenSoFar<>, Query_>
{
    enum { value = false };
};

template <typename Query_, typename A_, typename... Rest_>
struct AlreadySeen<SeenSoFar<A_, Rest_...>, Query_>
{
    enum { value = std::is_same<Query_, A_>::value || AlreadySeen<SeenSoFar<Rest_...>, Query_>::value };
};

template <typename...>
struct OneOfDeduplicatorBuilder;

template <typename... Values_>
struct OneOfDeduplicatorBuilder<SeenSoFar<Values_...> >
{
    typedef OneOf<Values_...> Type;
};

template <typename SeenSoFar_, typename Next_, typename... Funcs_>
struct OneOfDeduplicatorBuilder<SeenSoFar_, Next_, Funcs_...>
{
    typedef typename std::conditional<
        AlreadySeen<SeenSoFar_, Next_>::value,
        typename OneOfDeduplicatorBuilder<SeenSoFar_, Funcs_...>::Type,
        typename OneOfDeduplicatorBuilder<typename ExtendSeenSoFar<Next_, SeenSoFar_>::Type, Funcs_...>::Type
            >::type Type;
};

template <typename... Funcs_>
struct OneOfDeduplicator
{
    typedef typename OneOfDeduplicatorBuilder<SeenSoFar<>, Funcs_...>::Type Type;
};

template <typename... Funcs_>
struct WhenReturnType;

template <typename FirstFunc_, typename... Funcs_>
struct WhenReturnType<FirstFunc_, Funcs_...>
{
    typedef typename std::conditional<
        AllReturnSame<FirstFunc_, Funcs_...>::value,
        typename LambdaParameterTypes<FirstFunc_>::ReturnType,
        typename OneOfDeduplicator<
            typename LambdaParameterTypes<FirstFunc_>::ReturnType,
            typename LambdaParameterTypes<Funcs_>::ReturnType ...>::Type
        >::type Type;
};

template <typename Val_, typename... Funcs_>
typename WhenReturnType<Funcs_...>::Type
when(Val_ && val, Funcs_ && ... funcs)
{
    LambdaVisitor<typename WhenReturnType<Funcs_...>::Type, Funcs_...> visitor(funcs...);
    return accept_returning<typename WhenReturnType<Funcs_...>::Type>(val, visitor);
}

Generic Lambda Visitors, or Writing Haskell in C++0x (Part 3)

In parts one and two, we built up a OneOf holder that could contain one of a number of different types of values, and developed a flexible variation on the visitor pattern to do things with the underlying values. Now we’ll adapt that to use lambdas.

We’ll need some helper classes so we can figure out the parameter types and return type of a lambda. A lambda itself is just fancy syntax for a struct with an operator(), so combined with the new decltype operator we can do this:

template <typename Type_>
struct ParameterTypes;

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_)>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_) const>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename Lambda_>
struct LambdaParameterTypes
{
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::FirstParameterType FirstParameterType;
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::ReturnType ReturnType;
};

Then we can use this to implement an adapter that turns a number of lambda functions into a visitable class. For starters we’ll ignore the return type:

template <typename... Funcs_>
struct LambdaVisitor;

template <>
struct LambdaVisitor<>
{
    void visit(struct NotReallyAType);
};

template <typename Func_, typename... Rest_>
struct LambdaVisitor<Func_, Rest_...> :
    LambdaVisitor<Rest_...>
{
    Func_ & func;

    LambdaVisitor(Func_ & f, Rest_ & ... rest) :
        LambdaVisitor<Rest_...>(rest...),
        func(f)
    {
    }

    void visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        func(v);
    }

    using LambdaVisitor<Rest_...>::visit;
};

Note the using statement, so all the visit methods defined have equal visibility for overload resolution. Also note how we define a dummy visit method in the base class, since it’s illegal to using something that doesn’t exist.

Incidentally, so far as I can see we have to use the “lots of inheritance” technique here. We can’t inherit using the ... operator, since there doesn’t seem to be a way of applying the ... operator to a using statement. Thus we can’t quite do something like:

template <typename Func_>
struct LambdaVisitorVisit
{
    Func_ func;

    LambdaVisitorVisit(Func_ & f) :
        func(f)
    {
    }

    void visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        func(v);
    }
};

template <typename... Funcs_>
struct LambdaVisitor :
    LambdaVisitorVisit<Funcs_>...
{
    LambdaVisitor(Funcs_ & ... funcs) :
        LambdaVisitorVisit<Funcs_>(funcs)...
    {
    }

    /* Can't do this: */
    using LambdaVisitorVisit<Funcs_>::visit...;
};

I’m not sure whether this is an intentional omission from the standard, or an oversight, or whether it’s just not considered useful.

That aside, now we just have to concoct the when function:

template <typename Val_, typename... Funcs_>
void when(Val_ && val, Funcs_ && ... funcs)
{
    accept(val, LambdaVisitor<Funcs_...>(funcs...));
}

And here we go:

int main(int, char *[])
{
    OneOf<int, std::string> s(123);

    when(s,
            [] (int & x)               { std::cout << "int " << ++x << std::endl; },
            [] (const std::string & x) { std::cout << "string " << x << std::endl; }
        );

    const OneOf<int, std::string> t(std::string("monkey"));

    when(t,
            [] (const int & x)         { std::cout << "int " << x << std::endl; },
            [] (const std::string & x) { std::cout << "string " << x << std::endl; }
        );

    return EXIT_SUCCESS;
}

What about return types? We could switch to using when_returning, but there’s another option: we could use the return type of the first lambda as our return type instead.

template <typename Result_, typename... Funcs_>
struct LambdaVisitor;

template <typename Result_>
struct LambdaVisitor<Result_>
{
    void visit(struct NotReallyAType);
};

template <typename Result_, typename Func_, typename... Rest_>
struct LambdaVisitor<Result_, Func_, Rest_...> :
    LambdaVisitor<Result_, Rest_...>
{
    Func_ & func;

    LambdaVisitor(Func_ & f, Rest_ & ... rest) :
        LambdaVisitor<Result_, Rest_...>(rest...),
        func(f)
    {
    }

    Result_ visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        return func(v);
    }

    using LambdaVisitor<Result_, Rest_...>::visit;
};

template <typename Val_, typename FirstFunc_, typename... Rest_>
typename LambdaParameterTypes<FirstFunc_>::ReturnType
when(Val_ && val, FirstFunc_ && first_func, Rest_ && ... rest)
{
    return accept_returning<typename LambdaParameterTypes<FirstFunc_>::ReturnType>(
            val,
            LambdaVisitor<typename LambdaParameterTypes<FirstFunc_>::ReturnType, FirstFunc_, Rest_...>(first_func, rest...));
}

And using it:

int main(int, char *[])
{
    OneOf<int, std::string> s(123);

    std::cout << when(s,
            [] (const int x)           { return x; },
            [] (const std::string & x) { return x.length(); }
        ) << std::endl;

    return EXIT_SUCCESS;
}

There we have it: a useful, highly generic alternative to visitors that makes use of lambdas. The code in full:

#include <string>
#include <memory>
#include <type_traits>
#include <utility>
#include <cstdlib>
#include <iostream>

struct UnknownTypeForOneOf;

template <typename Want_, typename... Types_>
struct SelectOneOfType;

template <typename Want_>
struct SelectOneOfType<Want_>
{
    typedef UnknownTypeForOneOf Type;
};

template <typename Want_, typename Try_, typename... Rest_>
struct SelectOneOfType<Want_, Try_, Rest_...>
{
    typedef typename std::conditional<
        std::is_same<Want_, Try_>::value,
        Try_,
        typename SelectOneOfType<Want_, Rest_...>::Type
            >::type Type;
};

template <typename Type_>
struct ParameterTypes;

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_)>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename C_, typename R_, typename P_>
struct ParameterTypes<R_ (C_::*)(P_) const>
{
    typedef P_ FirstParameterType;
    typedef R_ ReturnType;
};

template <typename Lambda_>
struct LambdaParameterTypes
{
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::FirstParameterType FirstParameterType;
    typedef typename ParameterTypes<decltype(&Lambda_::operator())>::ReturnType ReturnType;
};

template <typename Type_>
struct OneOfVisitorVisit
{
    virtual void visit(Type_ &) = 0;
};

template <typename... Types_>
struct OneOfVisitor :
    OneOfVisitorVisit<Types_>...
{
};

template <typename Visitor_, typename Underlying_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperVisit;

template <typename Visitor_, typename Underlying_, typename Result_>
struct OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_> :
    Visitor_
{
    Underlying_ & underlying;
    std::function<Result_ ()> execute;

    OneOfVisitorWrapperVisit(Underlying_ & u) :
        underlying(u)
    {
    }
};

template <typename Visitor_, typename Underlying_, typename Result_, typename Type_, typename... Rest_>
struct OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Type_, Rest_...> :
    OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Rest_...>
{
    OneOfVisitorWrapperVisit(Underlying_ & u) :
        OneOfVisitorWrapperVisit<Visitor_, Underlying_, Result_, Rest_...>(u)
    {
    }

    Result_ visit_returning(Type_ & t)
    {
        return this->underlying.visit(t);
    }

    virtual void visit(Type_ & t)
    {
        this->execute = std::bind(&OneOfVisitorWrapperVisit::visit_returning, this, std::ref(t));
    }
};

template <typename Underlying_, typename Result_, typename... Types_>
struct OneOfVisitorWrapper :
    OneOfVisitorWrapperVisit<OneOfVisitor<Types_...>, Underlying_, Result_, Types_...>
{
    OneOfVisitorWrapper(Underlying_ & u) :
        OneOfVisitorWrapperVisit<OneOfVisitor<Types_...>, Underlying_, Result_, Types_...>(u)
    {
    }
};

template <typename... Types_>
struct OneOfValueBase
{
    virtual ~OneOfValueBase() = 0;

    virtual void accept(OneOfVisitor<Types_...> &) = 0;
    virtual void accept(OneOfVisitor<const Types_...> &) const = 0;
};

template <typename... Types_>
OneOfValueBase<Types_...>::~OneOfValueBase() = default;

template <typename Type_, typename... Types_>
struct OneOfValue :
    OneOfValueBase<Types_...>
{
    Type_ value;

    OneOfValue(const Type_ & type) :
        value(type)
    {
    }

    virtual void accept(OneOfVisitor<Types_...> & visitor)
    {
        static_cast<OneOfVisitorVisit<Type_> &>(visitor).visit(value);
    }

    virtual void accept(OneOfVisitor<const Types_...> & visitor) const
    {
        static_cast<OneOfVisitorVisit<const Type_> &>(visitor).visit(value);
    }
};

template <typename... Types_>
class OneOf
{
    private:
        std::unique_ptr<OneOfValueBase<Types_...> > _value;

    public:
        template <typename Type_>
        OneOf(const Type_ & value) :
            _value(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value})
        {
        }

        OneOf(const OneOf & other) = delete;

        OneOf(OneOf && other) :
            _value(std::move(other._value))
        {
        }

        template <typename Type_>
        OneOf & operator= (const Type_ & value)
        {
            _value.reset(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value});
            return *this;
        }

        OneOf & operator= (const OneOf & other) = delete;

        OneOf & operator= (OneOf && other)
        {
            _value = std::move(other._value);
            return *this;
        }

        OneOfValueBase<Types_...> & value()
        {
            return *_value;
        }

        const OneOfValueBase<Types_...> & value() const
        {
            return *_value;
        }
};

template <typename Visitor_, typename Result_, typename OneOf_>
struct OneOfVisitorWrapperTypeFinder;

template <typename Visitor_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperTypeFinder<Visitor_, Result_, const OneOf<Types_...> &>
{
    typedef OneOfVisitorWrapper<Visitor_, Result_, const Types_...> Type;
};

template <typename Visitor_, typename Result_, typename... Types_>
struct OneOfVisitorWrapperTypeFinder<Visitor_, Result_, OneOf<Types_...> &>
{
    typedef OneOfVisitorWrapper<Visitor_, Result_, Types_...> Type;
};

template <typename Result_, typename OneOf_, typename Visitor_>
Result_
accept_returning(OneOf_ && one_of, Visitor_ && visitor)
{
    typename OneOfVisitorWrapperTypeFinder<Visitor_, Result_, OneOf_>::Type visitor_wrapper(visitor);
    one_of.value().accept(visitor_wrapper);
    return visitor_wrapper.execute();
}

template <typename OneOf_, typename Visitor_>
void accept(OneOf_ && one_of, Visitor_ && visitor)
{
    accept_returning<void>(one_of, visitor);
}

template <typename Result_, typename... Funcs_>
struct LambdaVisitor;

template <typename Result_>
struct LambdaVisitor<Result_>
{
    void visit(struct NotReallyAType);
};

template <typename Result_, typename Func_, typename... Rest_>
struct LambdaVisitor<Result_, Func_, Rest_...> :
    LambdaVisitor<Result_, Rest_...>
{
    Func_ & func;

    LambdaVisitor(Func_ & f, Rest_ & ... rest) :
        LambdaVisitor<Result_, Rest_...>(rest...),
        func(f)
    {
    }

    Result_ visit(typename LambdaParameterTypes<Func_>::FirstParameterType & v)
    {
        return func(v);
    }

    using LambdaVisitor<Result_, Rest_...>::visit;
};

template <typename Val_, typename FirstFunc_, typename... Rest_>
typename LambdaParameterTypes<FirstFunc_>::ReturnType
when(Val_ && val, FirstFunc_ && first_func, Rest_ && ... rest)
{
    return accept_returning<typename LambdaParameterTypes<FirstFunc_>::ReturnType>(
            val,
            LambdaVisitor<typename LambdaParameterTypes<FirstFunc_>::ReturnType, FirstFunc_, Rest_...>(first_func, rest...));
}

In part four we’ll start do some clever things with the return type, mostly because we can, rather than because it’s definitely useful.

Generic Lambda Visitors, or Writing Haskell in C++0x (Part 1)

A good FORTRAN programmer can write FORTRAN in any language. Now, I present Haskell written in C++0x!

struct Base { };
struct FirstDerived : Base { };
struct SecondDerived : Base { };
struct ThirdDerived : Base { };

int main(int, char *[])
{
    OneOf<int, std::string, FirstDerived, SecondDerived, ThirdDerived> s(123), t(std::string("monkey"));

    when(t,
            [] (int x)                   { std::cout << "t is int " << x << std::endl; },
            [] (const std::string & x)   { std::cout << "t is string " << x << std::endl; },
            [] (const Base &)            { std::cout << "t is a Base subclass" << std::endl; },
            [] (const FirstDerived &)    { std::cout << "t is Base subclass FirstDerived" << std::endl; }
        );

    s = SecondDerived();

    std::cout << when(
            when(s,
                [] (int & x)               -> std::string { return std::string(++x, 'x'); },
                [] (std::string & x)       -> int         { x.append(" spanker"); return x.length(); },
                [] (const Base &)          -> int         { return 42; },
                [] (const ThirdDerived &)  -> double      { return 3.14; }
                ),
            [] (const int x)           -> int { return x; },
            [] (const std::string & x) -> int { return x.length(); },
            [] (const double x)        -> int { return x > 3 ? 4 : 3; }
            ) << std::endl;

    return EXIT_SUCCESS;
}

Ok, that one’s rather silly. But there is a point to this: it’s a variation on the visitor pattern, with the visiting externalised rather than being a part of the classes itself. That in turn means classes can be part of different visitable hierarchies in different places — one example would be in handling Gentoo style dependency-like structures, where certain constructs make sense in certain contexts but not others (e.g. || ( ) blocks are legal in dependencies but not SRC_URI, and blockers are legal in dependencies but not provides). Rather than forcing all visitors to implement all methods, or having entirely independent hierarchies for similar things, or losing type safety, you can externalise the visiting parts.

As an added bonus, it’s a good way of getting to grips with variadic templates and type lists. The excessive return type cleverness for the second when above is of questionable real world use, but the techniques required to get it working may be of interest.

Let’s start with the bare minimum:

#include <string>
#include <memory>
#include <utility>
#include <cstdlib>

template <typename... Types_>
struct OneOfValueBase
{
    virtual ~OneOfValueBase() = 0;
};

template <typename... Types_>
OneOfValueBase<Types_...>::~OneOfValueBase() = default;

template <typename Type_, typename... Types_>
struct OneOfValue :
    OneOfValueBase<Types_...>
{
    Type_ value;

    OneOfValue(const Type_ & type) :
        value(type)
    {
    }
};

template <typename... Types_>
class OneOf
{
    private:
        std::unique_ptr<OneOfValueBase<Types_...> > _value;

    public:
        template <typename Type_>
        OneOf(const Type_ & value) :
            _value(new OneOfValue<Type_, Types_...>{value})
        {
        }

        OneOf(const OneOf & other) = delete;

        OneOf(OneOf && other) :
            _value(std::move(other._value))
        {
        }

        template <typename Type_>
        OneOf & operator= (const Type_ & value)
        {
            _value.reset(new OneOfValue<Type_, Types_...>{value});
            return *this;
        }

        OneOf & operator= (const OneOf & other) = delete;

        OneOf & operator= (OneOf && other)
        {
            _value = std::move(other._value);
            return *this;
        }
};

int main(int, char *[])
{
    OneOf<int, std::string> s(123);
    s = std::string("monkey");

    return EXIT_SUCCESS;
}

Note that we’ve made the type moveable but not copyable or default constructible; extending the type to clone its value and to support an uninitialised state isn’t particularly difficult, but isn’t necessary for what we’re after.

We have a problem, though:

    OneOf<int, std::string> s(123);
    s = 1.23;

Oops. So we need a way of checking whether a particular type is in a typelist:

struct UnknownTypeForOneOf;

template <typename Want_, typename... Types_>
struct SelectOneOfType;

template <typename Want_>
struct SelectOneOfType<Want_>
{
    typedef UnknownTypeForOneOf Type;
};

template <typename Want_, typename Try_, typename... Rest_>
struct SelectOneOfType<Want_, Try_, Rest_...>
{
    typedef typename std::conditional<
        std::is_same<Want_, Try_>::value,
        Try_,
        typename SelectOneOfType<Want_, Rest_...>::Type
            >::type Type;
};

Then we can make sure we’re only creating valid children:

template <typename... Types_>
class OneOf
{
    public:
        template <typename Type_>
        OneOf(const Type_ & value) :
            _value(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value})
        {
        }

        template <typename Type_>
        OneOf & operator= (const Type_ & value)
        {
            _value.reset(new OneOfValue<typename SelectOneOfType<Type_, Types_...>::Type, Types_...>{value});
            return *this;
        }
};

Yay. But none of this is much use if all we can do is create and assign legal things to our values. We need to be able to do things to the underlying value too. Let’s start with a very simple visitor pattern. We need a visitor base class:

template <typename Type_>
struct OneOfVisitorVisit
{
    virtual void visit(const Type_ &) = 0;
};

template <typename... Types_>
struct OneOfVisitor :
    OneOfVisitorVisit<Types_>...
{
};

We need to make our value holders able to accept a visitor:

template <typename... Types_>
struct OneOfValueBase
{
    virtual ~OneOfValueBase() = 0;

    virtual void accept(OneOfVisitor<Types_...> &) = 0;
};

template <typename... Types_>
OneOfValueBase<Types_...>::~OneOfValueBase() = default;

template <typename Type_, typename... Types_>
struct OneOfValue :
    OneOfValueBase<Types_...>
{
    Type_ value;

    OneOfValue(const Type_ & type) :
        value(type)
    {
    }

    virtual void accept(OneOfVisitor<Types_...> & visitor)
    {
        static_cast<OneOfVisitorVisit<Type_> &>(visitor).visit(value);
    }
};

And for convenience we’ll put an accept method in OneOf too:

template <typename... Types_>
class OneOf
{
    public:
        void accept(OneOfVisitor<Types_...> & visitor) const
        {
            _value->accept(visitor);
        }
};

Now we can try it out:

struct IntStringVisitor :
    OneOfVisitor<int, std::string>
{
    virtual void visit(const int & x)
    {
        std::cout << "int " << x << std::endl;
    }

    virtual void visit(const std::string & x)
    {
        std::cout << "string " << x << std::endl;
    }
};

int main(int, char *[])
{
    OneOf<int, std::string> s(123);
    s = std::string("monkey");

    IntStringVisitor visitor;
    s.accept(visitor);

    return EXIT_SUCCESS;
}

In part two, we’ll make visitors more flexible.