Visitor Pattern: Should the visitor or the visited object decide the visiting order?

Question

I've seen examples in both ways, particularly Wikipedia shows an example where the visited object decides the visiting order and I think this is a sounding approach.

I'm in a situation in which I will need several visiting orders so It seems reasonable to let the Visitor decide the visiting order. However, If the visitor is responsible for the visiting order (i.e., for calling the accept method of the object being visited) I could make the visitor just call some visiting method directly (i.e., bypass the call to the visiting object's accept method) and this seems totally contrary to what the pattern proposes..

What is the correct way to implement the visiting pattern and how to deal when we have several different visiting orders?

Answer 1

I believe there is no "one correct way". Correct way is the way that meets your needs.

A visitor must visit each element of the object structure. The question is, how does it get there? Who is responsible for traversing the object structure? GoF Design Patterns book answers the question as follows:

1- Often the object structure is responsible for iteration. A collection will simply iterate over its elements, calling the Accept operation on each.

2- Another solution is to use an iterator to visit the elements.

3- You could even put the traversal algorithm in the visitor, although you'll end up duplicating the traversal code in each ConcreteVisitor for each aggregate ConcreteElement. The main reason to put the traversal strategy in the visitor is to implement a particularly complex traversal, one that depends on the results of the operations on the object structure.

So it is fine to let visitor to decide visiting order.

Answer 2

Good question. You seem to be looking at design patterns as recipes or even algorithms, when they're really just a way of discussing things that programmers do all the time. There's no right way to implement a pattern.

In the case of the Visitor pattern, the point of invoking accept on the visited object is that each visited object may have a different internal structure. In such a case (for example, the syntax tree of a program), it makes sense to hide this internal structure from the visitor. In other cases the structure of the visited data is homogeneous, such as an XML document, it makes perfect sense for the visitor to decide the order.

In cases where the visited objects have varying internal structure but you want to visit them in different orders, you can have different accept methods (acceptPreOrder and acceptPostOrder) to visit, for example, the node and then it's children or the children and then the node. To keep things simple, you could also have a single accept method that takes an order parameter. This is problematic as well, because the visited objects need to implement all possible traversal orders. If the visitor knows enough about the structure of the visited objects to decide on a traversal order, it may in fact be better to let the visitor handle visiting children of a given object directly.

Answer 3

For most languages, decide everything in the visitor. The only purpose for accept() is to dispatch on the runtime type of the visited object. It's a neat solution except that built-in types like number/bool/null and closed/finalized types without accept cannot be visited. If you need to handle these cases then you wind up with type-reflection spaghetti code distributed across your visitors, visited objects, and client code. Simplify type reflection and dispatch by deleting accept(). Handle all types and dispatch uniformly in the visitor, including exceptions. Now, without accept, it is obvious where to put your visiting logic. Make a base visitor that handles types and exceptions, then extend that to handle visitation order, then extend that again to make actual visitors.

If you have special navigation needs for a visited object then that visited object (or its class) can expose a special purpose visitor that is derived from the general visitor above. For example, when the general visitation handler visits Foo it can get a FooVisitor from foo and fooVisitor.visit(foo.child). In this way you can handle an e.g. String or Array child of Foo differently than you would handle a String or Array child of Bar. Consider how messy this would get using that god awful accept() method. You'd have to give accept a context... say to accept "yes, you're a string but you're a string in foo". Now we have accept(context) and that's just terrible.