Blag

He's not dead, he's resting

Tag Archives: c++

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 2)

In part one, we created a basic OneOf type which allowed us to store one of a specific list of types, and we created a simple visitor framework for it. It allowed us to write a visitor that looks like:

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;
    }
};

This isn’t very flexible. What if we want to visit by non-const reference, or by value? What if we want to make our visit methods const? What if we want to return something?

Because the visitor pattern relies upon virtual methods, and because virtual template methods don’t make sense, we need to keep the same basic underlying pattern. But how we present this to the programmer can change: rather than requiring visitors to be derived from OneOfVisitor, we can accept visitors of an arbitrary class, and create a OneOfVisitor implementation that, for each visit method, calls the appropriate visit method in the wrapper.

Here’s what our wrapper looks like:

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

template <typename Visitor_, typename Underlying_>
struct OneOfVisitorWrapperVisit<Visitor_, Underlying_> :
    Visitor_
{
    Underlying_ & underlying;

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

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

    virtual void visit(Type_ & t)
    {
        this->underlying.visit(t);
    }
};

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

Something to note here: we’re saying “make me a visit method that takes the first item in our type list as a parameter, and also inherit from OneOfVisitorWrapperVisit with the remainder of our type list”. Then we use the leaf class to inherit from the original abstract visitor class we’re implementing, and also to handle holding the underlying type.

This is slightly more convoluted than how we handled type lists for OneOfVisitor, where we used expansion instead:

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

There we start to see what the ... operator really means: it says “expand the pattern to our left once for each item in the specified type list, replacing the type list name with the value of the expansion each time, and then join the whole lot together with commas”.

Which technique is better? It depends. The expansion form is more compact. However, if we used that for our visitor wrapper, we’d then have to have some additional way of inheriting from the abstract visitor, and of handling the underlying type. This would involve either virtual base classes or lots of extremely icky casting.

We also need to modify our accept method to create the wrapper:

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

Now we can make our visitor more flexible:

struct IntStringVisitor
{
    void visit(const int x) const
    {
        std::cout << "int " << x << std::endl;
    }

    void visit(std::string & x)
    {
        x.append("-spanker");
        std::cout << "string " << x << std::endl;
    }
};

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

    IntStringVisitor visitor;
    s.accept(visitor);
    s.accept(visitor);

    return EXIT_SUCCESS;
}

This has another neat implication:

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

struct DerivedVisitor
{
    void visit(const int x)
    {
        std::cout << "int " << x << std::endl;
    }

    void visit(const Base &)
    {
        std::cout << "derived from base" << std::endl;
    }

    void visit(const ThirdDerived &)
    {
        std::cout << "third derived" << std::endl;
    }
};

int main(int, char *[])
{
    OneOf<int, FirstDerived, SecondDerived, ThirdDerived> s(123);
    DerivedVisitor visitor;

    s.accept(visitor);

    s = FirstDerived();
    s.accept(visitor);

    s = SecondDerived();
    s.accept(visitor);

    s = ThirdDerived();
    s.accept(visitor);

    return EXIT_SUCCESS;
}

If some of the visitable items are derived from the same base class, we can just visit that base class rather than each of the derived items. We can also implement specific visit methods for some of the derived classes, whilst falling back to visiting the base class for any in which we don’t have a specific interest. This uses the normal overload selection rules, except decided at runtime rather than compile time, giving us a much more flexible kind of dynamic dispatch than conventional visitors.

What about return types? Well, we could store the result in our visitor wrapper:

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;
    Result_ result;

    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)
    {
    }

    virtual void visit(Type_ & t)
    {
        this->result = this->underlying.visit(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)
    {
    }
};

Then we could add a new accept_returning method:

template <typename... Types_>
class OneOf
{
    public:
        template <typename Result_, typename Visitor_>
        Result_ accept_returning(Visitor_ & visitor) const
        {
            OneOfVisitorWrapper<Visitor_, Result_, Types_...> visitor_wrapper(visitor);
            _value->accept(visitor_wrapper);
            return visitor_wrapper.result;
        }
};

And use it thusly:

struct IntStringVisitor
{
    int visit(const int x) const
    {
        return x;
    }

    int visit(const std::string & s) const
    {
        return s.length();
    }
};

int main(int, char *[])
{
    OneOf<int, std::string> s(123);
    IntStringVisitor visitor;
    std::cout << s.accept_returning<int>(visitor) << std::endl;

    return EXIT_SUCCESS;
}

Except now we’ve broken the void case, so we need to add some specialisations:

template <typename Visitor_, typename Underlying_>
struct OneOfVisitorWrapperVisit<Visitor_, Underlying_, void> :
    Visitor_
{
    Underlying_ & underlying;

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

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

    virtual void visit(Type_ & t)
    {
        this->underlying.visit(t);
    }
};

And we need to fix the old accept method:

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

This isn’t pretty. It also assumes that our result type is regular (specifically, default constructible and copyable), which is much too tight. We can approach this another way: rather than having our visitor wrapper directly call the underlying method and store the result, we can have it create a bound function.

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)
    {
    }
};

Then we can modify our accept methods:

template <typename... Types_>
class OneOf
{
    public:
        void accept(Visitor_ & visitor) const
        {
            OneOfVisitorWrapper<Visitor_, void, Types_...> visitor_wrapper(visitor);
            _value->accept(visitor_wrapper);
            visitor_wrapper.execute();
        }

        template <typename Result_, typename Visitor_>
        Result_ accept_returning(Visitor_ & visitor) const
        {
            OneOfVisitorWrapper<Visitor_, Result_, Types_...> visitor_wrapper(visitor);
            _value->accept(visitor_wrapper);
            return visitor_wrapper.execute();
        }
};

But wait, there’s more! In C++0x an expression of the form “return func();” is legal inside a template function if func and our function both ‘return’ void. So we can rewrite accept as:

template <typename... Types_>
class OneOf
{
    public:
        template <typename Visitor_>
        void accept(Visitor_ & visitor) const
        {
            return accept_returning<void>(visitor);
        }
};

We can now deal with return types that are only moveable:

struct IckyType
{
    int value;

    explicit IckyType(const int x) :
        value(x)
    {
    }

    IckyType(IckyType && other) :
        value(other.value)
    {
    }

    IckyType(const IckyType &) = delete;
    IckyType & operator= (const IckyType &) = delete;
};

struct IckyVisitor
{
    IckyType visit(const int i)
    {
        return IckyType{i};
    }

    IckyType visit(const std::string & s)
    {
        return IckyType{s.length()};
    }
};

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

    std::cout << s.accept_returning<IckyType>(visitor).value << std::endl;

    return EXIT_SUCCESS;
}

Up until now we’ve mostly ignored constness. A visitor must be non-const, even if all its visit methods are const, which is an arbitrary restriction. More importantly, a visitor can currently modify the value stored in a const OneOf, which shouldn’t be allowed.

First up, let’s change how we get at the value for OneOf:

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;
        }
};

That closes up the hole introduced by using std::unique_ptr, which behaves like a pointer for const rules rather than behaving like a transparent holder. Next, we need both const and non-const accept methods in our values. However, the const variant must accept a visitor that visits const versions of our types. Again, we can make use of the fact that ... works by expanding a possibly non-trivial pattern into a list:

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);
    }
};

With current C++, what would follow would be even more overloading for the accept method in OneOf. With C++0x we have another option: we can move to using free template functions, and taking rvalue references:

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);
}

But what is OneOfVisitorWrapperTypeFinder<Visitor, Result_, OneOf_>? We need it to be OneOfVisitorWrapper<Visitor_, Result, OneOf Types...> if one_of is non-const, but OneOfVisitorWrapper<Visitor_, Result, OneOf Types made const...> if it is const. This is where the rvalue reference comes in. In the form specified above, the type value of OneOf_ will be an lvalue reference if the parameter is non-const, and a const lvalue reference if the parameter is const. Thus:

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;
};

Now we can do this:

struct ChangeVisitor
{
    void visit(int & x)
    {
        ++x;
    }

    void visit(std::string & x)
    {
        x.append(" spanker");
    }
};

struct NoChangeVisitor
{
    void visit(int x)
    {
        std::cout << "int " << x << std::endl;
    }

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

struct ConstChangeVisitor
{
    void visit(int & x) const
    {
        ++x;
    }

    void visit(std::string & x) const
    {
        x.append(" spanker");
    }
};

struct ConstNoChangeVisitor
{
    void visit(int x) const
    {
        std::cout << "int " << x << std::endl;
    }

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

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

    accept(s, ChangeVisitor());
    accept(s, NoChangeVisitor());
    accept(s, ConstChangeVisitor());
    accept(s, ConstNoChangeVisitor());

    const ConstChangeVisitor const_change_visitor{};
    const ConstNoChangeVisitor const_no_change_visitor{};

    accept(s, const_change_visitor);
    accept(s, const_no_change_visitor);

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

    // accept(t, ChangeVisitor());
    accept(t, NoChangeVisitor());
    // accept(t, ConstChangeVisitor());
    accept(t, ConstNoChangeVisitor());

    // accept(t, const_change_visitor);
    accept(t, const_no_change_visitor);

    return EXIT_SUCCESS;
}

In part three we’ll start using lambdas to avoid the need for all those ugly visitor classes.

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.

Runtime Type Checking in C++ without RTTI

A technique I always seem to forget is how to map C++ types to an integer without relying upon RTTI. A variation on this is used in <locale> in standard library, for std::use_facet<>. But let’s take a much simpler, and highly contrived, example.

Let’s say we’ve got some values of different types, and we want to give those types to a library to store somewhere, and then we later want to get them back again. Crucially, the library itself doesn’t know anything about the types in question. So, for a very simple case:

#include <vector>
#include <iostream>
#include <string>

int main(int, char *[])
{
    std::vector<Something> things = { std::string("foo"), 123 };
    /* ... */
    std::cout << things[0].as<std::string>() << " " << things[1].as<int>() << std::endl;
}

Note the gratuitous use of c++0x initialiser lists, just because we can.

Those familiar with Boost might think that Something is like boost::any. However, boost::any uses RTTI, which is slow and completely unnecessary.

A first implementation of Something might look like this:

#include <memory>

class Something
{
    private:
        struct SomethingValueBase
        {
            virtual ~SomethingValueBase()
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            return static_cast<const SomethingValue<T_> &>(*_value).value;
        }
};

This works, but has a major flaw: if you get the types wrong when calling Something.as<>, you’ll get a segfault or something similarly horrible. We’d like to replace that with something safer.

One way to do it is to use runtime type information. The simplest variation on this is to replace the static_cast with a dynamic_cast. However, we can only do this if SomethingValueBase is a polymorphic type, which it isn’t. We can make it so by adding in a virtual destructor:

#include <memory>

class Something
{
    private:
        struct SomethingValueBase
        {
            virtual ~SomethingValueBase()
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            return dynamic_cast<const SomethingValue<T_> &>(*_value).value;
        }
};

Now, if we get the types wrong, a std::bad_cast will be thrown. Alternatively, we can use our own exception type:

class SomethingIsSomethingElse
{
};

class Something
{
    /* snip */

    public:
        template <typename T_>
        const T_ & as() const
        {
            auto value_casted(dynamic_cast<const SomethingValue<T_> *>(_value.get()));
            if (! value_casted)
                throw SomethingIsSomethingElse();
            return value_casted->value;
        }
};

We can also make use of std::dynamic_pointer_cast, which is possibly slightly less ugly syntactically:

class Something
{
    /* snip */

    public:
        template <typename T_>
        const T_ & as() const
        {
            auto value_casted(std::dynamic_pointer_cast<const SomethingValue<T_> >(_value));
            if (! value_casted)
                throw SomethingIsSomethingElse();
            return value_casted->value;
        }
};

All of this is using RTTI, though, and RTTI is a huge amount of overkill for what we need. Before eliminating the RTTI, though, we’ll switch to using it in a different way:

#include <memory>
#include <string>
#include <typeinfo>

class Something
{
    private:
        template <typename T_>
        struct SomethingValueType
        {
            virtual ~SomethingValueBase()
            {
            }
        };

        struct SomethingValueBase
        {
            std::string type_info_name;

            SomethingValueBase(const std::string & t) :
                type_info_name(t)
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                SomethingValueBase(typeid(SomethingValueType<T_>()).name()),
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            if (typeid(SomethingValueType<T_>()).name() != _value->type_info_name)
                throw SomethingIsSomethingElse();
            return std::static_pointer_cast<const SomethingValue<T_> >(_value)->value;
        }
};

Here we make use of typeid explicitly, which is widely considered to be about on par with use of goto. However, it paves the way for our next step. Can we replace typeid(SomethingValueType<T_>()).name() with a different, non-evil expression? Let’s think about what properties the result of that expression must have:

  • We must be able to store it, so it needs to be a regular type.
  • We must be able to compare values of it, and be guaranteed true if and only if the two types used to create the value are the same, and false if and only if they are different. (Note that RTTI doesn’t even provide this guarantee.)

Let’s try this:

#include <memory>
#include <string>

class SomethingIsSomethingElse
{
};

template <typename T_>
struct SomethingTypeTraits;

class Something
{
    private:
        struct SomethingValueBase
        {
            int magic_number;

            SomethingValueBase(const int m) :
                magic_number(m)
            {
            }

            virtual ~SomethingValueBase()
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                SomethingValueBase(SomethingTypeTraits<T_>::magic_number),
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            if (SomethingTypeTraits<T_>::magic_number != _value->magic_number)
                throw SomethingIsSomethingElse();
            return std::static_pointer_cast<const SomethingValue<T_> >(_value)->value;
        }
};

Now, our library user has to provide specialisations of SomethingTypeTraits for every type they wish to use:

#include <string>
#include <iostream>
#include <vector>

template <>
struct SomethingTypeTraits<int>
{
    enum { magic_number = 1 };
};

template <>
struct SomethingTypeTraits<std::string>
{
    enum { magic_number = 2 };
};

int main(int, char *[])
{
    std::vector<Something> things = { std::string("foo"), 123 };
    std::cout << things[0].as<std::string>() << " " << things[1].as<int>() << std::endl;
}

No RTTI at all there, and it is type safe, but it relies upon a lot of boilerplate from the library user, and that boilerplate is very easy to screw up. So, we’ll allocate magic numbers automatically instead:

#include <memory>

class Something
{
    private:
        static int next_magic_number()
        {
            static int magic(0);
            return magic++;
        }

        template <typename T_>
        static int magic_number_for()
        {
            static int result(next_magic_number());
            return result;
        }

        struct SomethingValueBase
        {
            int magic_number;

            SomethingValueBase(const int m) :
                magic_number(m)
            {
            }

            virtual ~SomethingValueBase()
            {
            }
        };

        template <typename T_>
        struct SomethingValue :
            SomethingValueBase
        {
            T_ value;

            SomethingValue(const T_ & v) :
                SomethingValueBase(magic_number_for<T_>()),
                value(v)
            {
            }
        };

        std::shared_ptr<SomethingValueBase> _value;

    public:
        template <typename T_>
        Something(const T_ & t) :
            _value(new SomethingValue<T_>(t))
        {
        }

        template <typename T_>
        const T_ & as() const
        {
            if (magic_number_for<T_>() != _value->magic_number)
                throw SomethingIsSomethingElse();
            return std::static_pointer_cast<const SomethingValue<T_> >(_value)->value;
        }
};

How does this work? Each instantiation of the magic_number_for<T_> function needs to return the same magic number every time it is called. The first time any particular instantiation is called, its static int result requests the next magic number. On subsequent calls, the allocated number is remembered. (Note that static values inside a template are not shared between different instantiations of that template.) Finally, next_magic_number just returns a new magic number every time it is called.

And there we have it: fast runtime type checking with no boilerplate and no RTTI. What we’ve done here is more or less useless, but the techniques do have other applications. For the curious, std::use_facet<> is probably the most common, and anyone brave enough to delve into its design will eventually see why this isn’t either pointless wankery or reinventing the wheel. For the rest, if you think that using RTTI can solve your problem adequately, then it probably can, and you don’t need to go into the kind of devious trickery the standard library uses internally.

C++ Named Function Parameters

C++ doesn’t have named function parameters. In some ways this isn’t a huge deal, since the compiler will usually catch when you screw up the ordering of arguments to a function. But if you’ve got a function accepting multiple arguments of the same type, the compiler isn’t going to save you. So we want to allow something like following:

shop.populate(
    param::number_of_cheeses() = 0,
    param::number_of_parrots() = 1,
    param::parrot_variety() = "Norwegian Blue"
    );

We also want:

  • As little as possible boilerplate from the programmer.
  • Type safety. It shouldn’t compile if the arguments are wrong.
  • Zero overhead.

It would be nice to allow arguments to be specified in any order, and there is a way of doing that using C++0x, but it’s rather convoluted, so we’ll stick with the requirement that arguments be in the right order for now.

First, we want to work out the type of those param::foo() things. Since we’re using operator=, they need to be structs or constants of some kind (since operator= can only be overloaded as a member function). Since we want lots of them of different types, and since we don’t want to have to worry about declaring the same name multiple times (which means we’d start hitting the ODR), a typedef of a template seems in order. Thus, we’d like to do:

namespace params
{
    typedef Name</* something */> number_of_cheeses;
    typedef Name</* something */> number_of_parrots;
    typedef Name</* something */> parrot_variety;
}

As for the something, the best I’ve been able to come up with is an inline forward declaration of a meaningless struct:

namespace params
{
    typedef Name<struct N_number_of_cheeses> number_of_cheeses;
    typedef Name<struct N_number_of_parrots> number_of_parrots;
    typedef Name<struct N_parrot_variety> parrot_variety;
}

What about the function parameters?

void Shop::populate(
    const NamedValue<param::number_of_cheeses, int> & number_of_cheeses,
    const NamedValue<param::number_of_parrots, int> & number_of_parrots,
    const NamedValue<param::number_of_cheeses, std::string> & parrot_variety)
{
    /* ... */
}

There’s a small amount of duplication there, but that’s a necessity: it’s considered a useful feature of C and C++ that declarations and implementations of functions can use different names for parameters.

As for using the parameters, we’ve got two options. We could add a super magic cast operator to NamedValue, or we could make it explicit. Since super magic casts have a nasty habit of doing really weird things, we’ll make it explicit using operator():

void Shop::populate(
    const NamedValue<param::number_of_cheeses, int> & number_of_cheeses,
    const NamedValue<param::number_of_parrots, int> & number_of_parrots,
    const NamedValue<param::number_of_cheeses, std::string> & parrot_variety)
{
    cheeses.resize(number_of_cheeses());
    cage.insert(number_of_parrots(), parrot_variety());
}

Now we just have to make it work. First, NamedValue, remembering to provide const and non-const versions of our operator:

template <typename T_, typename V_>
class NamedValue
{
    private:
        V_ _value;

    public:
        explicit NamedValue(const V_ & v) :
            _value(v)
        {
        }

        V_ & operator() ()
        {
            return _value;
        }

        const V_ & operator() () const
        {
            return _value;
        }
};

Then Name. Our first attempt might look like this:

template <typename T_>
struct Name
{
    template <typename V_>
    NamedValue<Name<T_>, V_> operator= (const V_ & v) const
    {
        return NamedValue<Name<T_>, V_>(v);
    }
};

But there’s a problem: whilst this works for int and most classes, it does something immensely stupid when fed a string literal. We could require users to write out parameters like:

    param::parrot_variety() = std::string("Norwegian Blue")

but that’s rather silly. So instead we’ll add in a way of overriding types for NamedValue, keeping it nice and generic in case any similar situations crop up elsewhere:

template <typename T_>
struct NamedValueType
{
    typedef T_ Type;
};

template <int n>
struct NamedValueType<char [n]>
{
    typedef std::string Type;
};

template <typename T_>
struct Name
{
    template <typename V_>
    NamedValue<Name<T_>, typename NamedValueType<V_>::Type> operator= (const V_ & v) const
    {
        return NamedValue<Name<T_>, typename NamedValueType<V_>::Type>(v);
    }
};

Fortunately, g++ is smart enough to compile all of this into exactly the same code as it would if named parameters weren’t used.

And there we have it: very low boilerplate type safe named parameters with no icky macros.

C++ Explicit Template Instantiation Hate Redux

Today’s hatred of C++ is brought to you by the section [temp.explicit]:

A definition of a class template or class member template shall be in scope at the point of the explicit instantiation of the class template or class member template.

Unfortunately, it doesn’t “explicit instantiation definition” there, so you can’t do an explicit instantiation declaration when you only have a class declaration available. I can’t figure out what changing this would break, and whether it’s just an omission (explicit instantiation declarations are new in C++0x, but explicit instantiations are not) or a deliberate restriction.

Whilst we’re on the subject, not being able to use typedef names when explicitly instantiating is still a pain in the arse too, although the implications of allowing that are almost certainly moderately icky.

C++ Template Specialisation Hate

Today’s annoying C++ feature is that partial specialisations of a nested type of a template class don’t work:

template <typename T_>
struct S;

template <typename T_>
struct T
{
    struct U;
};

template <typename T_>
struct S<typename T<T_>::U>
{
};

Depending upon your compiler, the specialisation will either be rejected with a highly cryptic error message, or accepted but ignored. I don’t seem to be able to find the part of the standard that bans doing this, either, but that doesn’t necessarily mean it’s legal…

The solution, in any case, is to hoist the nested class out of the template, and use a typedef instead:

template <typename T_>
struct S;

template <typename T_>
struct T_U;

template <typename T_>
struct T
{
    typedef T_U<T_> U;
};

template <typename T_>
struct S<T_U<T_> >
{
};

I’ve been of the opinion that nested classes are generally far more pain than they’re worth for a while now (they also can’t be forward-declared); I’m highly tempted to just stop using them anywhere at all, and switch exclusively to using typedefs.

Assorted C++ Linkage

C++ Const Curiosity

GCC will accept the following (look closely at S::f‘s signature in both places):

struct T
{
    void foo()
    {
    }
};

struct S
{
    void f(const T);
};

void
S::f(T t)
{
    t.foo();
}

int main(int, char *[])
{
    T t;
    S s;
    s.f(t);
}

The question is, should it?

Update: and the answer is, yes, it should, according to [dcl.fct] in the standard. This is both useful and annoying.