Blag

He's not dead, he's resting

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.

Advertisements

One response to “Generic Lambda Visitors, or Writing Haskell in C++0x (Part 2)

  1. Pingback: Generic Lambda Visitors, or Writing Haskell in C++0x (Part 3) « Ciaran McCreesh’s Blag

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s