This article presents a flexible and efficient variation of the Visitor design pattern in C++ that accommodates arbitrary argument and return types.

Read this article from The C++ Source:

http://www.artima.com/cppsource/cooperative_visitor.html

What do you think of the technique?

One detail. From the article:

"Windows DLLs present a problem: every DLL gets its own copy of static variables. This would result in the same class being associated with different tags in different DLLs."

Now, my apologies if I understand this statement wrong, but in general there is nothing special about DLLs and static variables (unless you play with #pragma section or similar). See this reference: http://msdn2.microsoft.com/en-us/library/ms682594.aspx

Thanks for the link.
The problem with using class-static variables is explained in this article relating to an issue with VC++ (6) STL implementation:

http://support.microsoft.com/default.aspx?scid=http://support.microsoft.com:80/support/kb/articles/Q172/3/96.ASP&NoWebContent=1

Cooperative Visitor uses class-static counters and tags.

The problem can be avoided by moving the tag generation to a separate dll and thus keeping the multiple copies of tag variables in sync.

Anand.

Random interesting links to other takes on the "Expression Problem" as it is A.K.A.:

http://www.google.com/search?hl=en&domains=http%3A%2F%2Flambda-the-ultimate.org&q=expression+problem

This thing is pretty cool once you get it working :-)

One thing though, how would you implement a visitor that supports falling back through the type hierarchy? So if BigCircle is visited, and there's no render() function for that type, then it'd automatically fallback to the render() for Circle.

That seems quite hard to do as you can't get the correct types from the tags.

Any insights welcome.

alexjc

1)There's an easy solution to the fall-back problem:

BigCircle could also be added to the typelist so that the slot for BigCircle be filled in the vtable:

Visits( *this, Seq< Shape, Circle, BigCircle >::Type(), RenderInvoker() );

The invokers would follow C++ conversion rules and choose render(Circle) for BigCircle as well.

This implies that the visitor class knows about BigCircle.
In general to achieve automatic fall back for a hierarchy:


typedef Seq<all classes that visitor can know of>::Type ClassesInHierarchy;

use the above typedef for all visitors:

Visits( *this, ClassesInHierarchy(), Invoker() );


Since the slot for BigCircle is also filled, there's no additional performance cost for fallback.




2)There's another more flexible approach:
The visitor asks the object being visited -
"Here's how my vtable looks like. Tell me what function in the table i should use?"

Along with the vtable, the visitor builds a status table (std::vector<bool>) that indicates whether a slot in the vtable is filled or not.

Each Visitable class needs to have it's base class typedef-ed:


class BigCircle: public Circle {
....
typedef Circle Super;
};


Rather than (or in addition to) the GetTag function in every visitable object, there's a GetMethodInvocationInfo:

struct InvocationInfo {
   size_t vtableIndex;
   void*  visitedObject;
};

class BigCircle : public Circle {
.....
   /// the following can be put in a macro
  virtual InvocationInfo GetMethodInvocationInfo(const std::vector<bool>& statusTable)
  {
    size_t myTag = GetTag(this);
    // check whether the visitor has a visit method for this class
   if( myTag < statusTable.size() && statusTable[myTag] ) {
     return InvocationInfo( myTag, this );
   }

   // there's no visit method for this class
   // fallback to base class
    return Super::GetMethodInvocationInfo( statusTable );
  }
};

The visitor is given the entire information for making the call - the index to the function and the properly casted object.

in Visitor:
  ReturnType operator() ( Base& b )
  {
    InvocationInfo info= b.GetMethodInvocationInfo( statusTable );
    Func thunk = (*vtable_ )[ info.vtableIndex ];
    return ( this->*thunk ) ( info.visitedObject ); 
  }

This scheme doesn't require the visitor to know about BigCircle - BigCircle could be any class that inherits from Circle and provides the appropriate GetMethodInvocationInfo implementation.
The look up time is proportional to how many level's of inheritance away BigCircle is from Circle. I think this would be better than falling back through acyclic visitor.

I think both techniques could be used simultaneously.

Multiple inheritance could also be handled using a similar scheme: each class declares (typedefs) its immediate base classes as a typelist. This results in a type-graph that models the inheritance hierarchy. The sub-graph for a particular visitable class could be walked (at compile time) to generate RTTI like data (tags and convertor functions) that can be used in method forwarding. They are also helpful in generating constant time dynamic casts.

Hi,

I like this implementation very much, indeed it has the same performance cost as the traditional one.

The dll issue makes me a bit hesitating, but there is another thing I would like to see clearly.
From the code it seems that I cannot have more visitors with different visitedlists simultaneously, because the Visits call repoints the vtable in the constructor.
So the following code would probably not run as expected:

struct MyVisitor1 : public Visitor<Shape,void>
{
typedef Seq<Circle,Triangle>::Type VisitedList;
// ...
};

struct MyVisitor2 : public Visitor<Shape,void>
{
typedef Seq<Circle,Rectangle>::Type VisitedList;
// ...
};

MyVisitor1 vis1;
MyVisitor2 vis2; // Visitor<Shape,void>::vtable repointed

void f(Shape* s)
{
vis1(s); // Triangles are passed to the Shape handler
vis2(s);
}

This can be cured easily by putting vtable to a template class which depends on the VisitedList too.

What do you think?
Was that an intentional decision bacause of some reasons?

Hi,

The vtable is indeed parameterized over the typelist. Here's the declaration for GetStaticVtable which creates shared vtables:


template< typename Visitor, typename VisitedList, typename Invoker >
struct GetStaticVtable;


In your example, there would be a vtable shared by all instances of MyVisitor1 and another shared by all instances of MyVisitor2.

The vtable pointer, in this case Visitor<Shape,void>::vtable_, is a member variable.
So changing the vtable pointer should be safe.


The vtable pointer can be changed by calling Visits again with a new invoker and/or new typelist (visited list). This coupled with the fact that any legal C++ code (say logging, traversal of sub-objects etc) can be put in invoker::invoke, provides dynamic configuration of visitation behavior.

Changing vtable pointer, doesn't affect existing vtables. A new shared vtable is created for the <Visitor, VisitedList, Invoker> triple.

Hi,

it's an interesting approach for me exploring the generic programming methods recently. Did you post the complete code or i missed the link?


Thanks in advance

Hi Anand.

I stumbled upon a technique similar to yours while I was trying to come up with a clean solution to what I call "The Need for Extensible Virtual Functions". After I finished prototyping my ideas, I realized that it was vaguely similar to the visitor pattern. Then I started looking on the web for any work that has improved upon the visitor pattern. While I was doing that, I stumbled upon your work. Needless to say, I found this work very interesting. You have touched upon a lot of subjects that I had not thought about. Have you had any chance to add further refinements to your work? I will be interested in knowing, if you have.

Thanks for sharing your work.

--Raikanta

Hi Raikanta,

Thanks for your interest in Cooperative Visitor.
I've been making improvements to the technique in directions driven by it active application. Here's a list of some of them:

1) Make the technique work across dll/so boundaries in Windows, Linux, Mac etc. Its interesting to know that a workaround, beyond the technique as presented in the article, is needed only for windows.

2) Support inheritance fallback. This I think is the most important improvement. This allows visitors to have the same behavior as if the code was expressed using virtual functions.I've outlined a scheme for doing so in previous posts.

3) Constant time "dynamic casts" can be supported with the same infrastructure required for inheritance fallback. This opens up ability to control cast semantics in addition to significant improvements in speed for code that uses "dynamic casts".

4) Extensible object factories can be supported, but I haven't spent much time on that.

5) I haven't gotten around to extending the technique to support multimethods.

Anand.

Hi, is there a whole C++ implementation of this pattern. I have only expierence in C# and want to unterstand this pattern, so its very difficult to understand with small parts.