[boost] [RFC] Generic non-intrusive Visitor pattern utility

From: dizzy (dizzy_at_[hidden])
Date: 2008-01-10 04:36:05

Hi

It is often in my line of work that I need to perform several duties depending 
on the exact type (dynamic type) of a pointer/reference to base of a class 
hierarchy. This is done cleanly with a Visitor pattern aproach but usual 
implementations of Visitor (as far as I could see) are intrusive, meaning 
they require the original class hierarchy to have some Visitor API (usually 
in the form of a virtual function taking a pointer/reference to a base 
Visitor class). I find that undesirable because in my use cases at least, the 
design of the original class hierarchy does not need to know that it may be 
visited at some point nor does it care about that. Not to mention it is not 
very practical to modify the original hierarchy when you find out you need a 
Visitor (because it may be part of a separate project, you may not even have 
the sources to it).

So I thought I need something non-intrusive to work on any class hierarchy one 
desires to use Visitor upon. An aproach solving this would be implementing a 
parallel class hierarchy that is Visitor aware (in the form of a template 
wrapper class instantiated by with the types visited), thus is nonintrusive 
but when actually implementing this, I noticed several draw backs:
- using virtual functions it still imposes using some base class Visitor 
object and people have to use inheritance (which I don't think is really 
needed)
- how to wrap the actual type is tricky, you may value aggregate it and then 
you require a working copy ctor of it (not always available or maybe 
expensive) or you may store pointers to it and then deal with the overhead of 
dynamic memory allocation just because of the design and one more indirection 
(neither of these required in the end)

The final (best?) solution I came with now is using RTTI. RTTI's typeid() is 
by design non-intrusive (actually the way it is implemented by the compiler 
is intrusive but it happens anyway for any polymorphic type so why not use 
it) and it does not have any of the problems listed above, the implementation 
is "small enough" that I can include it here:

#include <typeinfo>
#include <stdexcept>
#include <string>

namespace detail
{

template<typename List>
struct VisitorHelper
{
        // empty body to compile error in case of wrong "List" parameter
};

template<typename Left, typename Right>
struct VisitorHelper< TypeList<Left, Right> >
{
        // notice how we copy "Visit" because it's suposed to be 
        // cheap to copy callback or similar thing
        template<typename Return, typename Visit, typename Visitee>
        static Return select(Visit visit, Visitee& visitee) {
                // typeid will consider the type without qualifiers so we need 
to 
                // preserve them in conversion
                // (FIXME: does not work with volatiles)
                if (typeid(Left) == typeid(visitee)) {
                        return Return(visit(static_cast<typename 
copy_cv<Visitee, 
Left>::type&>(visitee)));
                } else return VisitorHelper<Right>::template 
select<Return>(visit, visitee);
        }
};

template<>
struct VisitorHelper< NullType >
{
        template<typename Return, typename Visit, typename Visitee>
        static Return select(Visit, Visitee& visitee) {
                // type not found in the known types list
                throw std::runtime_error("Type unknown: " + 
std::string(typeid(visitee).name()));
        }
};

}

// List should be a canonical TypeList (without cv qualifiers, 
// no reference or pointer types, no array types)

template<typename List, typename Return, typename Visit, typename Visitee>
Return apply_visitor(Visit visit, Visitee& visitee)
{
        return detail::VisitorHelper<List>::template select<Return>(visit, 
visitee);
}

Not included here but used in the code are TypeList, NullType and copy_cv. 
They are easy to guess, TypeList is the usual TypeList (as in mr 
Alexandrescu's well known book), NullType is a incomplete type just to signal 
termination of the list and copy_cv is a type function that will add cv 
qualifiers of a type to another. It is used in the code where if the dynamic 
type is found, we need to static_cast the base type of the given parameter to 
that found dynamic type but we should static_cast by keeping the base type cv 
qualifiers.

Use case:
struct Base { virtual ~Base() {} };
struct Derived1: Base {};
struct Derived2: Base {};

typedef TypeList<Derived1, TypeList<Derived2, NullType> > VisitedTypes;

struct Visitor1 {
        void operator()(Derived1 const& op) const {}
        bool operator()(Derived2& op) { return false; }
};

struct Visitor2 {
        bool operator()(Derived1& arg) const { return false; }
        int operator()(Derived2 const& arg) const { return 10; }
};

struct Visitor3 {
        void operator()(Base const&) {}
};

struct Visitor4 {
        void operator()(Derived1 const&) const {}
};

int main()
{
        Visitor1 vis1;
        Visitor3 vis3;
        std::auto_ptr<Base> obj(new Derived1);

        // will call Visitor1::operator()(Derived1&) const;
        apply_visitor<VisitedTypes, void>(vis1, *obj); 

        // compile time error, cannot convert void to bool result 
        // of Visitor1::operator()(Derived1&)
        // apply_visitor<VisitedTypes, bool>(vis1, *obj); 

        // will call Visitor2::operator()(Derived1&) const
        // will convert int return type to bool if "*obj" dynamic type
        // were Derived2
        apply_visitor<VisitedTypes, bool>(Visitor2(), *obj);

        // will call Visitor3::operator()(Base const&)
        // even tho that beats the purpose of the Visitor
        apply_visitor<VisitedTypes, void>(vis3, *obj);

        // will compile time error, there is no matching function to call
        // with (Visitor4())(Derived2& argument)
        // apply_visitor<VisitedTypes, void>(Visitor4(), *obj);
}

I would like to know if boost implements something similar (I remember there 
was something related to visitors in the variant library) and if not if you 
find it interesting and a good addition to boost so I can work on it, 
performing the required changes to be included with boost. Of course any 
other technical comments pointing out problems, flaws or trying to improve 
this code are welcome.

Thanks!

-- 
Mihai RUSU					Email: dizzy_at_[hidden]
			"Linux is obsolete" -- AST