| I l@ve RuBoard |
|
10.4 A Generic Implementation of VisitorLet's divide the implementation into two major units:
The approach is simple and consistent: We try to factor out as much code as possible into the library. If we succeed in doing that, we will be rewarded with simplified dependencies. That is, instead of the two parts—visitor and visitable—depending on each other, both will depend on the library. This is good because the library is supposed to be much more immutable than the application. We first try to implement a generic Acyclic Visitor, since it has better behavior with regard to dependency and insulation. Later, we'll tweak it for performance. In the end, we return to implementing a classic GoF Visitor that is speedier at the expense of some flexibility. In the discussion on implementation, the names listed and defined in Table 10.1 apply. Some of the names in the table actually describe class templates, or, better said, will become class templates as we increasingly make our code more generic. For now, it's important to define the entities that the names represent. Let's focus on the visitor hierarchy first. Here things are quite simple—we must provide some base classes for the user, classes that define a Visit operation for a given type. In addition, we must provide the strawman class that's used by the dynamic cast as required by the Acyclic Visitor pattern. Here it is:
class BaseVisitor
{
public:
virtual ~BaseVisitor() {}
};
That's not a lot of reuse, but somebody has to write this little class. Now we provide a simple class template Visitor. Visitor<T> defines a pure virtual function for visiting an object of type T.
template <class T>
class Visitor
{
public:
virtual void Visit(T&) = 0;
};
In the general case, Visitor<T>::Visit might return something other than void. Visitor<T>::Visit can pass a useful result via Visitable::Accept. Consequently, let's add a second template parameter to Visitor:
template <class T, typename R = void>
class Visitor
{
public:
typedef R ReturnType;
virtual ReturnType Visit(T&) = 0;
};
Whenever you want to visit a hierarchy, you first derive your ConcreteVisitor from BaseVisitor, and as many Visitor instantiations as types you want to visit.
class SomeVisitor :
public BaseVisitor // required
public Visitor<RasterBitmap>,
public Visitor<Paragraph>
{
public:
void Visit(RasterBitmap&); // visit a RasterBitmap
void Visit(Paragraph &); // visit a Paragraph
};
The code looks clean, simple, and easy to use. Its structure makes it clear which classes your code visits. Even better, the compiler does not allow you to instantiate SomeVisitor if you don't define all the Visit functions. There is a name dependency between SomeVisitor's class definition and the names of the classes it visits (RasterBitmap and Paragraph). This dependency is quite understandable, because SomeVisitor knows about these types and needs to do specific operations on them. We have now concluded the visitor side of the implementation. We defined a simple base class that acts as the boot for dynamic_cast (BaseVisitor) and a class template (Visitor) that generates a pure virtual function (Visit) for each visited type. The code we have written so far, in spite of its small quantity, has fairly good reuse potential. The Visitor class template generates a separate type for each visited class. The library client is relieved of the burden of littering the implementation with all those little classes such as ParagraphVisitor and RasterBitmapVisitor. The types generated by the Visitor class template will ensure the link with the Visitable classes. This brings us to the visitable hierarchy. As discussed in the previous section, the visitable hierarchy in an Acyclic Visitor implementation has the following responsibilities:
To carry the first responsibility we add a pure virtual function to the BaseVisitable class and require DocElement—and in general any root of a visitable hierarchy in the application space—to inherit from it. BaseVisitable looks like this:
template <typename R = void>
class BaseVisitable
{
public:
typedef R ReturnType;
virtual ~BaseVisitable() {}
virtual ReturnType Accept(BaseVisitor&) = 0;
};
Trivial. Things become interesting when we try to carry the second responsibility, that is, to implement Accept in the library (not in the client). The Accept function implementation is not big, but it's annoying to have each client class take care of it. It would be nice if its code belonged to the library. As prescribed by the Acyclic Visitor pattern, if T is a visited class, T::Accept's implementation applies dynamic_cast<Vistor<T>*> to the BaseVisitor. If the cast succeeds, T::Accept bounces back to the Visitor<T>::Visit. However, as mentioned in Section 10.2, simply defining Accept in the Base Visitable class does not work, because the static type of *this in BaseVisitable does not provide the appropriate information to visitors. We need a way to implement Accept in the library and to inject this function into the application's DocElement hierarchy. Alas, C++ has no such direct mechanism. There are workarounds that use virtual inheritance, but they are less than stellar and have non-negligible costs. We have to resort to a macro and require each class in the visitable hierarchy to use that macro inside the class definition. Using macros, with all the clumsiness they bring, is not an easy decision to make, but any other solution does not add much commodity, at considerable expense in time and space. Because C++ programmers are known to be practical people, efficiency is reason enough for relying on macros from time to time instead of using esoteric but ineffective techniques. The single most important rule in defining a macro is to let it do as little as possible by itself and to forward to a "real" entity (function, class) as quickly as possible. We define the macro for visitable classes as follows:
#define DEFINE_VISITABLE() \
virtual ReturnType Accept(BaseVisitor& guest) \
{ return AcceptImpl(*this, guest); }
The client must insert DEFINE_VISITABLE() in each class of the visitable hierarchy. DEFINE_VISITABLE() defines the Accept member function to forward to another function—AcceptImpl. AcceptImpl is a template function parameterized with the type of *this. This way AcceptImpl gains access to the much-needed static type. We define AcceptImpl in the very base of the hierarchy, in BaseVisitor. This way, all derivatives will have access to it. Here's the changed BaseVisitable class:
template <typename R = void>
class BaseVisitable
{
public:
typedef R ReturnType;
virtual ~BaseVisitable() {}
virtual ReturnType Accept(BaseVisitor&) = 0;
protected: // Give access only to the hierarchy
template <class T>
static ReturnType AcceptImpl(T& visited, BaseVisitor& guest)
{
// Apply the Acyclic Visitor
if (Visitor<T>* p = dynamic_cast<Visitor<T>*>(&guest))
{
return p->Visit(visited);
}
return ReturnType();
}
};
The fact that we have managed to move AcceptImpl to the library is important. It's not only a matter of automating the client's job. The presence of AcceptImpl in the library gives us the opportunity to adjust its implementation depending on various design constraints, as will become clear later. The resulting design of Visitor/Visitable hides a great many details from the user, doesn't have annoying usage caveats, and works like a charm. Here's the current codebase for our generic Acyclic Visitor implementation.
// Visitor part
class BaseVisitor
{
public:
virtual ~BaseVisitor() {}
};
template <class T, typename R = void>
class Visitor
{
public:
typedef R ReturnType; // Available for clients
virtual ReturnType Visit(T&) = 0;
};
// Visitable part
template <typename R = void>
class BaseVisitable
{
public:
typedef R ReturnType;
virtual ~BaseVisitable() {}
virtual R Accept(BaseVisitor&) = 0;
protected:
template <class T>
static ReturnType AcceptImpl(T& visited, BaseVisitor& guest)
{
// Apply the Acyclic Visitor
if (Visitor<T>* p =
dynamic_cast<Visitor<T>*>(&guest))
{
return p->Visit(visited);
}
return ReturnType();
}
};
#define DEFINE_VISITABLE() \
virtual ReturnType Accept(BaseVisitor& guest) \
{ return AcceptImpl(*this, guest); }
Ready for a test drive? Here it is:
class DocElement : public BaseVisitable<>
{
public:
DEFINE_VISITABLE()
};
class Paragraph : public DocElement
{
public:
DEFINE_VISITABLE()
};
class MyConcreteVisitor :
public BaseVisitor, // required
public Visitor<DocElement>,// visits DocElements
public Visitor<Paragraph> // visits Paragraphs
{
public:
void Visit(DocElement&) { std::cout << "Visit(DocElement&) \n"; }
void Visit(Paragraph&) { std::cout << "Visit(Paragraph&) \n"; }
};
int main()
{
MyConcreteVisitor visitor;
Paragraph par;
DocElement* d = ∥ // "hide" the static type of 'par'
d->Accept(visitor);
}
This little program will output Visit(Paragraph&) which means that everything works just fine. Of course, this toy example doesn't show very much about the power of the codebase we've put together. However, given all the pains we've been through in implementing visitors from scratch in the previous sections, it's clear we now have a device that makes it easy to create visitable hierarchies correctly and to visit them. Let us review the actions you must carry out to define a visitable hierarchy.
The resulting dependency chart is simple. The class definition of SomeVisitor depends by name on each visited class. The implementations of the Visit member functions fully depend on the classes they manipulate. That's pretty much it. Compared with the previously discussed implementations, this one leaves us much better off. With the help of our Visitor implementation, we now have an ordered way to make visitable hierarchies, and we have reduced client code and dependencies to the bare necessity. In special cases, you might prefer to implement Accept directly rather than to use the DEFINE_VISITABLE macro. Suppose you define a Section class, derived from DocElement, which contains several Paragraphs. For a Section object, you would like to visit each Paragraph in that Section. In this case, you might want to implement Accept manually: class Section : public DocElement
// Won't use the DEFINE_VISITABLE() macro
// because it's going to implement Accept by itself
{
...
virtual ReturnType Accept(BaseVisitor& v)
{
for (each paragraph in this section)
{
current_paragraph->Accept(v);
}
}
};
As you can see, there's nothing you cannot do when you use the Visitor implementation. The code we defined only frees you from the grunt work you would have to do if you started from scratch. We have finished defining the kernel Visitor implementation, which includes pretty much anything that is germane to basic visiting needs. But read on, there's a lot more to come.  |
| I l@ve RuBoard |
|