# Visitor Pattern

version 3.0.2

The Visitor Pattern is one of those well-known but not often used patterns. I think this is strange, as it is really a nice thing.

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.

## 1. 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.

    abstract class Shape { }

    class Rectangle extends Shape {
        def x, y, width, height

        Rectangle(x, y, width, height) {
            this.x = x; this.y = y; this.width = width; this.height = height
        }

        def union(rect) {
            if (!rect) return this
            def minx = [rect.x, x].min()
            def maxx = [rect.x + width, x + width].max()
            def miny = [rect.y, y].min()
            def maxy = [rect.y + height, y + height].max()
            new Rectangle(minx, miny, maxx - minx, maxy - miny)
        }

        def accept(visitor) {
            visitor.visit_rectangle(this)
        }
    }

    class Line extends Shape {
        def x1, y1, x2, y2

        Line(x1, y1, x2, y2) {
            this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2
        }

        def accept(visitor){
            visitor.visit_line(this)
        }
    }

    class Group extends Shape {
        def shapes = []
        def add(shape) { shapes += shape }
        def remove(shape) { shapes -= shape }
        def accept(visitor) {
            visitor.visit_group(this)
        }
    }

    class BoundingRectangleVisitor {
        def bounds

        def visit_rectangle(rectangle) {
            if (bounds)
                bounds = bounds.union(rectangle)
            else
                bounds = rectangle
        }

        def visit_line(line) {
            def line_bounds = new Rectangle(line.x1, line.y1, line.x2-line.y1, line.x2-line.y2)
            if (bounds)
                bounds = bounds.union(line_bounds)
            else
                bounds = line_bounds
        }

        def visit_group(group) {
            group.shapes.each { shape -> shape.accept(this) }
        }
    }

    def group = new Group()
    group.add(new Rectangle(100, 40, 10, 5))
    group.add(new Rectangle(100, 70, 10, 5))
    group.add(new Line(90, 30, 60, 5))
    def visitor = new BoundingRectangleVisitor()
    group.accept(visitor)
    bounding_box = visitor.bounds
    println bounding_box.dump()

That took quite a bit of code.

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

    abstract class Shape {
        def accept(Closure yield) { yield(this) }
    }

    class Rectangle extends Shape {
        def x, y, w, h
        def bounds() { this }
        def union(rect) {
            if (!rect) return this
            def minx = [ rect.x, x ].min()
            def maxx = [ rect.x + w, x + w ].max()
            def miny = [ rect.y, y ].min()
            def maxy = [ rect.y + h, y + h ].max()
            new Rectangle(x:minx, y:miny, w:maxx - minx, h:maxy - miny)
        }
    }

    class Line extends Shape {
        def x1, y1, x2, y2
        def bounds() {
            new Rectangle(x:[x1, x2].min(), y:[y1, y2].min(), w:(x2 - x1).abs(), h:(y2 - y1).abs())
        }
    }

    class Group {
        def shapes = []
        def leftShift(shape) { shapes += shape }
        def accept(Closure yield) { shapes.each{it.accept(yield)} }
    }

    def group = new Group()
    group << new Rectangle(x:100, y:40, w:10, h:5)
    group << new Rectangle(x:100, y:70, w:10, h:5)
    group << new Line(x1:90, y1:30, x2:60, y2:5)
    def bounds
    group.accept{ bounds = it.bounds().union(bounds) }
    println bounds.dump()

## 2. Advanced Example

    interface Visitor {
        void visit(NodeType1 n1)
        void visit(NodeType2 n2)
    }

    interface Visitable {
        void accept(Visitor visitor)
    }

    class NodeType1 implements Visitable {
        Visitable[] children = new Visitable[0]
        void accept(Visitor visitor) {
            visitor.visit(this)
            for(int i = 0; i < children.length; ++i) {
                children[i].accept(visitor)
            }
        }
    }

    class NodeType2 implements Visitable {
        Visitable[] children = new Visitable[0]
        void accept(Visitor visitor) {
            visitor.visit(this)
            for(int i = 0; i < children.length; ++i) {
                children[i].accept(visitor)
            }
        }
    }

    class NodeType1Counter implements Visitor {
        int count = 0
        void visit(NodeType1 n1) {
            count++
        }
        void visit(NodeType2 n2){}
    }

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

    NodeType1 root = new NodeType1()
    root.children = new Visitable[2]
    root.children[0] = new NodeType1()
    root.children[1] = new NodeType2()

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.

### 2.1. Why to use this

As you can see here very good we have a visitor that has a state while the tree of objects is not changed. That’s pretty useful in different areas, for example you could have a visitor counting all node types, or how many different types are used, or you could use methods special to the node to gather information about the tree and much more.

### 2.2. What happens if we add a new type?

In this case we have to do much work.. we have to change Visitor to accept the new type, we have to write the new type itself of course and we have to change every Visitor we have already implemented. After very few changes you will modify all your Visitors to extend a default implementation of the visitor, so you don’t need to change every Visitor each time you add a new type.

### 2.3. 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:

    interface Visitor {
        void visit(NodeType1 n1)
        void visit(NodeType2 n2)
    }

    class DefaultVisitor implements Visitor{
        void visit(NodeType1 n1) {
            for(int i = 0; i < n1.children.length; ++i) {
                n1.children[i].accept(this)
            }
        }
        void visit(NodeType2 n2) {
            for(int i = 0; i < n2.children.length; ++i) {
                n2.children[i].accept(this)
            }
        }
    }

    interface Visitable {
        void accept(Visitor visitor)
    }

    class NodeType1 implements Visitable {
        Visitable[] children = new Visitable[0]
        void accept(Visitor visitor) {
            visitor.visit(this)
        }
    }

    class NodeType2 implements Visitable {
        Visitable[] children = new Visitable[0];
        void accept(Visitor visitor) {
            visitor.visit(this)
        }
    }

    class NodeType1Counter extends DefaultVisitor {
        int count = 0
        void visit(NodeType1 n1) {
            count++
            super.visit(n1)
        }
    }

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.

### 2.4. 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 when I `visitor.visit(children[i])` then 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 I could do `visitor.visit(children[i])` directly. Hmm.. 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? I think you can guess that I would answer no. But we can do more. We had the disadvantage of not knowing how to handle unknown tree elements. We had to extends 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:

    class DefaultVisitor {
        void visit(NodeType1 n1) {
            n1.children.each { visit(it) }
        }
        void visit(NodeType2 n2) {
            n2.children.each { visit(it) }
        }
        void visit(Visitable v) { }
    }

    interface Visitable { }

    class NodeType1 implements Visitable {
        Visitable[] children = []
    }

    class NodeType2 implements Visitable {
        Visitable[] children = []
    }

    class NodeType1Counter extends DefaultVisitor {
        int count = 0
        void visit(NodeType1 n1) {
            count++
            super.visit(n1)
        }
    }

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. For me this is the best level of separation you could get here. But do we really need to stop here? No. Let us change the `Visitable` interface a little and let it return the children we want to visit next. This allows us a general iteration method.

    class DefaultVisitor {
        void visit(Visitable v) {
            doIteraton(v)
        }
        void doIteraton(Visitable v) {
            v.children.each {
                visit(it)
            }
        }
    }

    interface Visitable {
        Visitable[] getChildren()
    }

    class NodeType1 implements Visitable {
        Visitable[] children = []
    }

    class NodeType2 implements Visitable {
        Visitable[] children = []
    }

    class NodeType1Counter extends DefaultVisitor {
        int count = 0
        void visit(NodeType1 n1) {
            count++
            super.visit(n1)
        }
    }

`DefaultVisitor` now looks a bit different. I added 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. I changed `Visitable` to ensure that any node will be able to return children (even if empty). I didn’t have to change the `NodeType1` and `NodeType2` class, because the way the children filed was defined already made them a property, which means Groovy is so nice to generate a get method for us. No 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 I thought this variant is better, because 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)`.

### 2.5. Summary

In the end we got ~40% less code, a robust and stable architecture and we completely removed the Visitor from the Visitable. I heard about visitor implementations based on Reflection to get a more generic version. Well, with this you see there is really no need to do such thing. If we add new types we don’t need to change anything. It is said that the visitor pattern doesn’t fit extreme programming techniques very well because you need to make changes to so many classes all the time. I think I proved that this is because of Java not because the pattern is bad or something.

There are variants of the Visitor pattern, like the acyclic visitor pattern, that tries to solve the problem of adding new node types with special visitors. I don’t like that very much, it works with casts, catches the `ClassCastException` and other nasty things. In the end it tries to solve something we don’t even get with the Groovy version.

One more thing. `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.

## 3. Further Information

- Componentization: the Visitor example