Non-intrusive and Acyclic Visitor

The Visitor Pattern

The Visitor is a behavioral pattern that is used to apply different algorithms to a Composite tree structure. It is mainly used to parse the tree in various ways to achieve different outcomes. The Visitor separates the algorithm from the objects that they operate on. It can be implemented in different ways depending upon the design options and choices available at the instance.

The most straightforward implementation is highly intrusive in which the base composite class is modified to have a virtual visit method and the visit behavior is delegated to the subclasses for a particular algorithm, say printing. This is a bad design choice as the composite tree may have to be parsed differently and not just for printing. If we stick to this design choice, we would have to modify the composite classes again with virtual methods for different algorithms and this isn't good from a code maintenance point of view. If we recall, the Visitor was supposed to separate the algorithm from the objects and it seems like it's not doing its job quite well.

The next choice is a reflective visitor, which behaves more like a visitor in which the algorithm is separate from the data. This visitor relies heavily on recursion and RTTI and does a lot of condition-decision in a single file. The readability and maintenance aspect of this approach is clumsy.

Can we do any better? Implementing the visitor for a strongly typed language such as C++ can be tricky. From the UML diagrams, the problem is apparent. The concrete Visitors need to know the base-type of the object to perform different operations. We can't resort to method overloading since it would default to the base composite class. To avoid this problem, we use a double dispatch visitor.

This beautiful trick uses a conjunction of dynamic binding and method overloading to figure out the composite type. It then uses this information to call the appropriate method for the object type.

Although neat, it also creates a cyclic dependency between the composite objects and the Visitor objects, which could be deficient in code compilation and maintenance. An Acyclic Visitor invented by Robert C. Martin solves this problem but introduces dynamic_cast to the equation with its own set of problems. The implementation relies heavily on the use case. I am more concerned with instances where modifying the Composite may not be an option, and the scenario demands non-intrusive visitors. Let's see if we can make it better.

Non Intrusion

I've taken the below composite from Dmitri Nesteruk's course Design Patterns in Modern C++ on Udemy. I've used the same structure for the UMLs above to maintain consistency. I am using structs here to avoid unnecessary getter setter methods, which are trivial and should be implemented.

I have decoupled the dependency of Composite objects on Visitor class using polymorphism and typeid, which still uses RTTI but dispatches the requests internally via the Visitor base class. This approach reduces compilation times by making the Composite objects independent of the Visitor objects. You can notice that the accept(Visitor&) methods are abandoned in the Composite. It only requires polymorphism among the Composite classes otherwise, typeid will return the base type for every subtype. That's why I've added a virtual destructor in the base Composite.

We are still going to dispatch twice, but the dispatch responsibility is completely on the Visitor base class. I construct a map between the type_index and a function. In the accept(Expression&) method, we figure out the type of the object and if the type exists in the map, we call the function associated with that type. The function related to the type_index needs to cast the expression to the appropriate type. We already know this from the typeid and the casting is performed using generics.

The function Visitor::castAndHandle(Expression&) is generic and it static_casts the Expression for the typeid it is associated with and call the polymorphic handle method. To make the correct associations, we bind the template specialization of castAndHandle in the Vistor::Visitor() constructor associated with the type_index.

I've deliberately separated the Handler class to make this code more reliable. Suppose a new composite Division was introduced and the client made some changes and included these Expressions in the tree. We won't see any compilation failures, but an error will be logged when the code is run in the Vistor::accept(Expression&) method, notifying this change to the developer. Then we only have to update two members: the Visitor::Visitor() to insert new types and the Handler to include new polymorphic methods for the new type of expression. Then, update ConcreteVisitors and compile only the Visitor module to add support for the new subclass.

Let us see two concrete implementations of the Visitor which use this approach. The casting duties have already been delegated to the base Visitor class and the Concrete classes need to handle the type of Expression based on function polymorphism.

The Printer and Evaluator are two types of concrete visitors which print and evaluate the Expression tree. These would naturally have to be modified if new Expressions are introduced. The complete source code source code is here. It's in a single file and is a simple toy example, but ideally, every class will be in its separate file and doing that will reduce the compilation time significantly.