Copy Page

You are not logged in. Any changes you make will be marked as anonymous. You may want to Log In if you already have an account. You can also Sign Up for a new account.

<p>The <a href="http://en.wikipedia.org/wiki/Visitor_pattern">Visitor Pattern</a> is one of those well-known but not often used patterns. I think this is strange, as it is really a nice thing.</p>

<p>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.</p>

<h2>Simple Example</h2>

<p>This example (inspired by <a href="http://wiki.rubygarden.org/Ruby/page/show/VisitorPattern">this</a>) 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.</p>
<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
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()
</pre></td></tr></table>
<p>That took quite a bit of code.</p>

<p>We can improve the clarity of our code (and make it about half the size) by making use of Groovy Closures as follows:</p>
<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
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, y:y1, w:x2-y1, h:x2-y2)
    }
}

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

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

<h2>Advanced Example</h2>
<p><br class="atl-forced-newline" /></p>
<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
interface Visitor {
   public void visit(NodeType1 n1);
   public void visit(NodeType2 n2);
}

interface Visitable {
    public void accept(Visitor visitor);
}

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

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

public class NodeType1Counter implements Visitor {
  int count = 0;
  public void visit(NodeType1 n1) {
     count++;
  }
  public void visit(NodeType2 n2){}
}
</pre></td></tr></table>
<p><br class="atl-forced-newline" />
<br class="atl-forced-newline" /></p>

<p>If we now use NodeType1Counter on a tree like this:</p>

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
NodeType1 root = new NodeType1()
root.children = new Visitable[2];
root.children[0] = new NodeType1();
root.children[1] = new NodeType2();
</pre></td></tr></table>
<p><br class="atl-forced-newline" />
<br class="atl-forced-newline" /></p>

<p>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.</p>

<p>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.</p>

<h3>What happens if we add a new type?</h3>

<p>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.</p>

<h3>What if we want to have different iteration patterns? </h3>

<p>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:</p>

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
interface Visitor {
   public void visit(NodeType1 n1);
   public void visit(NodeType2 n2);
}

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

interface Visitable {
    public void accept(Visitor visitor);
}

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

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

public class NodeType1Counter extends DefaultVisitor {
  int count = 0;
  public void visit(NodeType1 n1) {
     count++;
    super.visit(n1);
  }
}
</pre></td></tr></table>
<p><br class="atl-forced-newline" />
<br class="atl-forced-newline" /></p>

<p>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.</p>

<h3>Make it Groovy</h3>

<p>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.</p>

<p>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.</p>

<p>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:</p>

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
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 = []
}

public class NodeType1Counter extends DefaultVisitor {
  int count = 0;
  public void visit(NodeType1 n1) {
     count++
     super.visit(n1)
  }
}
</pre></td></tr></table>
<p><br class="atl-forced-newline" />
<br class="atl-forced-newline" /></p>

<p>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.</p>

<table class="wysiwyg-macro" data-macro-name="code" style="background-image: url(/plugins/servlet/confluence/placeholder/macro-heading?definition=e2NvZGV9&amp;locale=en_GB&amp;version=2); background-repeat: no-repeat;" data-macro-body-type="PLAIN_TEXT"><tr><td class="wysiwyg-macro-body"><pre>
class DefaultVisitor {
  void visit(Visitable v) {
    doIteration(v)
  }
  doIteraton(Visitable v) {
    v.children.each { visit(it) }
  }
}

interface Visitable {
  Visitable[] getChildren()
}

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

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

public class NodeType1Counter extends DefaultVisitor {
  int count = 0
  public void visit(NodeType1 n1) {
     count++
     super.visit(n1)
  }
}
</pre></td></tr></table>
<p><br class="atl-forced-newline" />
<br class="atl-forced-newline" /></p>

<p>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 <code>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)</code> will now call <code>visit(Visitable)}}which will call doIterate 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 doIterate method, we could do that in {{visit(Visitable)</code> too, but I thought this variant is better, because it allows us to write a new Visitor that overwrites <code>visit(Visitable)</code> for error cases which of course means we must not do <code>super.visit(n1)</code> but <code>doIterate(n1)</code>.</p>

<h3>Summary</h3>

<p>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.</p>

<p>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 <code>ClassCastException</code> and other nasty things. In the end it tries to solve something we don't even get with the Groovy version.</p>

<p>One more thing. <code>NodeType1Counter</code> could be implemented in Java as well. Groovy will recognize the visit methods and call them as needed because <code>DefaultVisitor</code> is still Groovy and does all the magic.</p>

<h2>Further Information</h2>

<ol>
	<li><a href="http://se.ethz.ch/~meyer/publications/computer/visitor.pdf">Componentization: the Visitor example</a></li>
</ol>