[RFC] Generic non-intrusive Visitor pattern utility

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@roedu.net "Linux is obsolete" -- AST

dizzy wrote:
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:
If I understand correctly, your implementation is O(n) with n = size(typelist), right? The advantage of virtual calls is that they're O(1), no matter how big the hierarchy. Though if that is a problem in the real world is a different question. How big are visited class hierarchies usually? Sebastian Redl

On Thursday 10 January 2008 16:35:22 Sebastian Redl wrote:
dizzy wrote:
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:
If I understand correctly, your implementation is O(n) with n = size(typelist), right? The advantage of virtual calls is that they're O(1), no matter how big the hierarchy.
Yes, that is true. But at the same time, AFAIK, the CPU optimizes my case better than jumping to a memory loaded address, in general code of the form: if (case1) func1(); if (case2) func2(); Should be faster than of: typedef void (*Function)(); Function funcs[2] = { &func1, &func2 }; funcs[getindex(input)](); As I understand it in the first case it can realise the possible outcomes from analyzing of the CPU instructions loaded (and thus may start to load instructions at the possible jump locations it has seen), in the later it cannot until it has loaded the contents of the array from memory (it probably does not matter if that is already cached as it happens for often used vtables).
Though if that is a problem in the real world is a different question. How big are visited class hierarchies usually?
In my case I use that visitor for 2 hierarchies of an average 5-6 visitable types. Your questions make me think of possibly implementing a virtual function based solution too (with that parallel hierarchy template wrapper technique described in the previous mail) and maybe have the user decide which of them to use? As there are user variables here that may decide the best to use in terms of CPU and memory resources: - number of visitable types - number of visits (or better, the ratio of visits/visitable-types) -- Mihai RUSU Email: dizzy@roedu.net "Linux is obsolete" -- AST

dizzy wrote:
I would like to know if boost implements something similar
I just skimmed your post very quicky, but it seems you might perhaps want to read this thread: http://permalink.gmane.org/gmane.comp.lib.boost.user/27516 Regards, Tobias

Hello On Friday 11 January 2008 15:47:59 Tobias Schwinger wrote:
dizzy wrote:
I would like to know if boost implements something similar
I just skimmed your post very quicky, but it seems you might perhaps want to read this thread:
Thanks for your link, it was an interesting read (along with the referenced article). It appears this if-istype/else technique is widely employed when needing a non-intrusive Visitor, when one cannot modify original hierarchy API (even tho I can modify it I still prefer the nonintrusive version as I find the action of needing to visit the hierarchy a decision of the user and not a feature for the hierarchy to provide it). So the logic of finding the type liniarly can be rewritten in my code to use boost::mpl features as from the link provided. Even so, if boost does not have such a generic Visitor feature, wouldn't it be a good addition? -- Mihai RUSU Email: dizzy@roedu.net "Linux is obsolete" -- AST

Hi, FWIW what's discussed here is known as multi-methods in some corners of programming world. A multi-method with one "virtual" argument would simply be a virtual function outside a class, which is probably what the original poster was looking for. Some relatively dynamic languages, e.g. clos and dylan, support multi-methods as a native concept. I believe there have been past discussions on multi-methods in boost. I believe at least Jesse Jones was involved in one discussion thread around September 2004. I implemented multi-methods for C++ long time ago as a library. We've used them in one data visualisation project, but not really otherwise. See the links below for some documentation and examples. I doubt that particular library in the form boost would like to have, but perhaps it gives you ideas to take further. Note that the code is GPLed. http://cmslxr.fnal.gov/lxr/source/Iguana/Utilities/classlib/utils/ MultiMethod.h#093 http://cmslxr.fnal.gov/lxr/source/Iguana/Utilities/test/utils/ MultiMethod01.cpp http://cmslxr.fnal.gov/lxr/source/Iguana/Utilities/test/utils/ MultiMethod02.cpp http://cmslxr.fnal.gov/lxr/source/Iguana/Utilities/test/utils/ MultiMethod03.cpp Lassi

dizzy wrote:
Hello
On Friday 11 January 2008 15:47:59 Tobias Schwinger wrote:
dizzy wrote:
I would like to know if boost implements something similar I just skimmed your post very quicky, but it seems you might perhaps want to read this thread:
Thanks for your link, it was an interesting read (along with the referenced article). It appears this if-istype/else technique is widely employed when needing a non-intrusive Visitor, when one cannot modify original hierarchy API (even tho I can modify it I still prefer the nonintrusive version as I find the action of needing to visit the hierarchy a decision of the user and not a feature for the hierarchy to provide it).
So the logic of finding the type liniarly can be rewritten in my code to use boost::mpl features as from the link provided. Even so, if boost does not have such a generic Visitor feature, wouldn't it be a good addition?
Honestly, I find its practical value rather questionable. From where I stand, the need for such a thing does most likely indicate that inheritance is probably used in a place where it shouldn't. Regards, Tobias
participants (4)
-
dizzy
-
Lassi A. Tuura
-
Sebastian Redl
-
Tobias Schwinger