src/spec/doc/_design-pattern-visitor.adoc

//////////////////////////////////////////

  Licensed to the Apache Software Foundation (ASF) under one
  or more contributor license agreements.  See the NOTICE file
  distributed with this work for additional information
  regarding copyright ownership.  The ASF licenses this file
  to you under the Apache License, Version 2.0 (the
  "License"); you may not use this file except in compliance
  with the License.  You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing,
  software distributed under the License is distributed on an
  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  KIND, either express or implied.  See the License for the
  specific language governing permissions and limitations
  under the License.

//////////////////////////////////////////

= Visitor Pattern

The https://en.wikipedia.org/wiki/Visitor_pattern[Visitor Pattern] is one of those well-known but not
often used patterns. Perhaps this is because it seems a little complex at first.
But once you become familiar with it, it becomes a powerful way to evolve your code
and as we'll see, Groovy provides ways to reduce some to the complexity, so there is
no reason not to consider using this pattern.

The goal of the pattern is to separate an algorithm from an object structure.
A practical result of this separation is the ability to add new operations to existing
object structures without modifying those structures.

== Simple Example

This example considers how to calculate the bounds of shapes (or collections of shapes).
Our first attempt uses the traditional visitor pattern.
We will see a more Groovy way to do this shortly.

[source,groovy]
----
include::../test/DesignPatternsTest.groovy[tags=visitor_simple_example,indent=0]
----

That took quite a bit of code, but the idea now is that we could add
further algorithms just by adding new visitors with our shape classes remaining
unchanged, e.g. we could add a total area visitor or a collision detection visitor.

We can improve the clarity of our code (and shrink it to about half the size) by
making use of Groovy Closures as follows:

[source,groovy]
----
include::../test/DesignPatternsTest.groovy[tags=visitor_simple_example2,indent=0]
----

Or, using lambdas as follows:

[source,groovy]
----
include::../test/DesignPatternsTest.groovy[tags=visitor_simple_example3,indent=0]
----

== Advanced Example

Let's consider another example to illustrate some more points about this pattern.

[source,groovy]
----
include::../test/DesignPatternsTest.groovy[tags=visitor_advanced_example,indent=0]
----

If we now use `NodeType1Counter` on a tree like this:

[source,groovy]
----
include::../test/DesignPatternsTest.groovy[tags=visitor_advanced_example2,indent=0]
----

Then we have one `NodeType1` object as root and one of the children is also a `NodeType1` instance.
The other child is a `NodeType2` instance.
That means using `NodeType1Counter` here should count 2 `NodeType1` objects as the last statement verifies.

=== When to use this

This example illustrates some of the advantages of the visitor pattern.
For example, while our visitor has state (the count of `NodeType1` objects), the tree of objects itself is not changed.
Similarly, if we wanted to have a visitor counting all node types,
or one that counts how many different types are used, or one that gathers information
using methods special to the node types, again, the visitor alone is all that would need to be written.

=== What happens if we add a new type?

In this case we might have a fair bit of work to do. We probably have to change the `Visitor` interface to accept the new type,
and change potentially most existing visitors based on that interface change,
and we have to write the new type itself.
A better approach is to write a default implementation of the visitor which all concrete visitors will extend.
We'll see this approach in use shortly.

=== What if we want to have different iteration patterns?

Then you have a problem.
Since the node describes how to iterate, you have no influence and stop iteration at a point or change the order.
So maybe we should change this a little to this:

[source,groovy]
----
include::../test/DesignPatternsTest.groovy[tags=visitor_advanced_example3,indent=0]
----

Some small changes but with big effect.
The visitor is now recursive and tells me how to iterate.
The implementation in the Nodes is minimized to `visitor.visit(this)`, `DefaultVisitor` is now able to catch the new types, we can stop iteration by not delegating to super.
Of course the big disadvantage now is that it is no longer iterative, but you can't get all the benefits.

=== Make it Groovy

The question now is how to make that a bit more Groovy.
Didn't you find this `visitor.visit(this)` strange? Why is it there?
The answer is to simulate double dispatch.
In Java, the compile time type is used, so for `visitor.visit(children[i])` the compiler won't be
able to find the correct method, because `Visitor` does not contain a method `visit(Visitable)`.
And even if it would, we would like to visit the more special methods with `NodeType1` or `NodeType2`.

Now Groovy is not using the static type, Groovy uses the runtime type.
This means we can use `visitor.visit(children[i])` without any problem.
Since we minimized the accept method to just do the double dispatch part and
since the runtime type system of Groovy will already cover that, do we need the accept method?
Not really, but we can do even more.
We had the disadvantage of not knowing how to handle unknown tree elements.
We had to _extend_ the interface `Visitor` for that, resulting in changes to `DefaultVisitor` and
then we have the task to provide a useful default like iterating the node or not doing anything at all.
Now with Groovy we can catch that case by adding a `visit(Visitable)` method that does nothing.
That would be the same in Java btw.

But don't let us stop here. Do we need the `Visitor` interface?
If we don't have the accept method, then we don't need the `Visitor` interface at all.
So the new code would be:

[source,groovy]
----
include::../test/DesignPatternsTest.groovy[tags=visitor_advanced_example4,indent=0]
----

Looks like we saved a few lines of code here, but we made more.
The `Visitable` nodes now do not refer to any `Visitor` class or interface.
This is about the best level of separation you might expect here, but we can go further.
Let's change the `Visitable` interface a little and let it return the children we want to visit next.
This allows us a general iteration method.

[source,groovy]
----
include::../test/DesignPatternsTest.groovy[tags=visitor_advanced_example5,indent=0]
----

`DefaultVisitor` now looks a bit different.
It has a `doIteration` method that will get the children it should iterate over and then call visit on each element.
Per default this will call `visit(Visitable)` which then iterates over the children of this child.
`Visitable` has also changed to ensure that any node will be able to return children (even if empty).
We didn't have to change the `NodeType1` and `NodeType2` class, because the way the children field was
defined already made them a property, which means Groovy is so nice to generate a get method for us.
Now the really interesting part is `NodeType1Counter`, it is interesting because we have not changed it.
`super.visit(n1)` will now call `visit(Visitable)` which will call `doIteration` which will start the next level of iteration.
So no change. But `visit(it)` will call `visit(NodeType1)` if it is of type `NodeType1`.
In fact, we don't need the `doIteration` method, we could do that in `visit(Visitable)` too,
but this variant has some benefits. It allows us to write a new `Visitor` that overwrites visit(`Visitable`)
for error cases which of course means we must not do `super.visit(n1)` but `doIteration(n1)`.

=== Summary

In the end we got ~40% less code, a robust and stable architecture,
and we completely removed the Visitor from the Visitable.
To achieve the same in Java, you would probably need to resort to reflection.

The visitor pattern has sometimes been described as a poor fit for extreme programming
techniques because you need to make changes to so many classes all the time.
With our design, if we add new types we don't need to change anything.
So, the pattern is a good fit for agile approaches when using Groovy.

There are variants of the Visitor pattern, like the https://java-design-patterns.com/patterns/acyclic-visitor/[acyclic visitor pattern],
that try to solve the problem of adding new node types with special visitors.
The implementations of these visitors have their own code smells, like using casts, overuse of `instanceof`, and other tricks.
What's more the problems such approaches are trying to solve don't occur within the Groovy version. We recommend avoiding that variant of this pattern.

Finally, in case it isn't obvious, `NodeType1Counter` could be implemented in Java as well.
Groovy will recognize the visit methods and call them as needed because `DefaultVisitor` is still Groovy and does all the magic.

== Further Information

- http://se.ethz.ch/~meyer/publications/computer/visitor.pdf[Componentization: the Visitor example]