The Artima Developer Community
Sponsored Link

Articles Forum
Cooperative Visitor: A Template Technique for Visitor Creation

11 replies on 1 page. Most recent reply: Dec 7, 2011 10:34 AM by Paul Eyermann

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 11 replies on 1 page
Bill Venners

Posts: 2248
Nickname: bv
Registered: Jan, 2002

Cooperative Visitor: A Template Technique for Visitor Creation Posted: Jul 11, 2007 1:00 PM
Reply to this message Reply
Advertisement
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?


Nemanja Trifunovic

Posts: 172
Nickname: ntrif
Registered: Jun, 2004

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Jul 12, 2007 8:40 AM
Reply to this message Reply
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

Anand Krishnamoorthi

Posts: 4
Nickname: anandsk
Registered: Apr, 2007

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Jul 12, 2007 12:14 PM
Reply to this message Reply
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.

Raoul Duke

Posts: 127
Nickname: raoulduke
Registered: Apr, 2006

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Jul 13, 2007 8:06 PM
Reply to this message Reply
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

Alex J. Champandard

Posts: 5
Nickname: alexjc
Registered: Sep, 2003

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Feb 19, 2008 9:41 AM
Reply to this message Reply
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

Anand Krishnamoorthi

Posts: 4
Nickname: anandsk
Registered: Apr, 2007

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Mar 5, 2008 8:43 AM
Reply to this message Reply
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.

József Mihalicza

Posts: 2
Nickname: jmihalicza
Registered: Mar, 2005

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Apr 4, 2008 8:35 AM
Reply to this message Reply
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?

Anand Krishnamoorthi

Posts: 4
Nickname: anandsk
Registered: Apr, 2007

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Apr 6, 2008 1:11 PM
Reply to this message Reply
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.

Mehmet Ali Meram

Posts: 1
Nickname: mmeram
Registered: Jul, 2008

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Jul 24, 2008 3:16 AM
Reply to this message Reply
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

Raikanta Sahu

Posts: 1
Nickname: raikanta
Registered: Oct, 2008

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Oct 28, 2008 1:01 AM
Reply to this message Reply
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

Anand Krishnamoorthi

Posts: 4
Nickname: anandsk
Registered: Apr, 2007

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Nov 12, 2008 2:49 PM
Reply to this message Reply
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.

Paul Eyermann

Posts: 1
Nickname: ep3681
Registered: Dec, 2011

Re: Cooperative Visitor: A Template Technique for Visitor Creation Posted: Dec 7, 2011 10:34 AM
Reply to this message Reply
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.

Flat View: This topic has 11 replies on 1 page
Topic: The DCI Architecture: A New Vision of Object-Oriented Programming Previous Topic   Next Topic Topic: Pure Virtual Function Called: An Explanation


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us