Visitor pattern

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Visitor in UML
Visitor in LePUS3 (legend)

In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure it operates on. A practical result of this separation is the ability to add new operations to existing object structures without modifying those structures. Thus, using the visitor pattern allows to conform with the open/closed principle.

In essence, the visitor allows one to add new virtual functions to a family of classes without modifying the classes themselves; instead, one creates a visitor class that implements all of the appropriate specializations of the virtual function. The visitor takes the instance reference as input, and implements the goal through double dispatch.

While powerful, the visitor pattern is more limited than conventional virtual functions. It is not possible to create visitors for objects without adding a small callback method inside each class. In naive implementations, the callback method in each of the classes is not inheritable.

Contents

[edit] Details

A user object receives a pointer to another object which implements an algorithm. The first is designated 'element class' and the latter 'the visitor class'. The idea is to use a structure of element classes, each of which has an accept() method taking a visitor object for an argument. visitor is an interface having a visit() method for each element class. The accept() method of an element class calls back the visit() method for its class. Separate concrete visitor classes can then be written to perform some particular operations, by implementing these operations in their respective visit() methods.

One of these visit() methods of a concrete visitor can be thought of as a method not of a single class, but rather a method of a pair of classes: the concrete visitor and the particular element class. Thus the visitor pattern simulates double dispatch in a conventional single-dispatch object-oriented language such as Java, Smalltalk, and C++. For an explanation of how double dispatch differs from function overloading, see Double dispatch is more than function overloading in the double dispatch article. In the Java language, two techniques have been documented that use reflection to simplify the mechanics of double dispatch simulation in the visitor pattern: getting rid of accept() methods (the Walkabout variation), and getting rid of extra visit() methods.

The visitor pattern also specifies how iteration occurs over the object structure. In the simplest version, where each algorithm needs to iterate in the same way, the accept() method of a container element, in addition to calling back the visit() method of the visitor, also passes the visitor object to the accept() method of all its constituent child elements.

Because the visitor object has one principal function (manifested in a plurality of specialized methods) and that function is called visit(), the visitor can be readily identified as a potential function object. Likewise, the accept() function can be identified as a function applicator, a mapper, which knows how to traverse a particular type of object and apply a function to its elements. Lisp's object system with its multiple dispatch does not replace the Visitor pattern, but merely provides a more concise implementation of it in which the pattern all but disappears.

[edit] Java example

The following example is in the Java programming language, and shows how the contents of a tree of nodes (in this case describing the components of a car) can be printed. Instead of creating "print" methods for each subclass (Wheel, Engine, Body, and Car), a single class (CarElementPrintVisitor) performs the required printing action. Because different subclasses require slightly different actions to print properly, CarElementDoVisitor dispatches actions based on the class of the argument passed to it.

[edit] Diagram

alt=A Diagram of the Java Code Example. I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide. In case this is not legally possible, I grant any entity the right to use this work for any purpose, without any conditions, unless such conditions are required by law.

[edit] Source

interface CarElementVisitor {
    void visit(Wheel wheel);
    void visit(Engine engine);
    void visit(Body body);
    void visit(Car car);
}
 
interface CarElement {
    void accept(CarElementVisitor visitor); // CarElements have to provide accept().
}
 
class Wheel implements CarElement {
    private String name;
 
    public Wheel(String name) {
        this.name = name;
    }
 
    public String getName() {
        return this.name;
    }
 
    public void accept(CarElementVisitor visitor) {
        visitor.visit(this);
    }
}
 
class Engine implements CarElement {
    public void accept(CarElementVisitor visitor) {
        visitor.visit(this);
    }
}
 
class Body implements CarElement {
    public void accept(CarElementVisitor visitor) {
        visitor.visit(this);
    }
}
 
class Car implements CarElement{
    CarElement[] elements;
 
    public CarElement[] getElements() {
        return elements.clone(); // Return a copy of the array of references.
    }
 
    public Car() {
        this.elements = new CarElement[]
          { new Wheel("front left"), new Wheel("front right"),
            new Wheel("back left") , new Wheel("back right"),
            new Body(), new Engine() };
    }
 
    public void accept(CarElementVisitor visitor) {	
        for(CarElement element : this.getElements()) {
            element.accept(visitor);
        }
        visitor.visit(this);	
    }
}
 
class CarElementPrintVisitor implements CarElementVisitor {
    public void visit(Wheel wheel) {      
        System.out.println("Visiting "+ wheel.getName()
                            + " wheel");
    }
 
    public void visit(Engine engine) {
        System.out.println("Visiting engine");
    }
 
    public void visit(Body body) {
        System.out.println("Visiting body");
    }
 
    public void visit(Car car) {      
        System.out.println("Visiting car");
    }
}
 
class CarElementDoVisitor implements CarElementVisitor {
    public void visit(Wheel wheel) {
        System.out.println("Kicking my "+ wheel.getName() + " wheel");
    }
 
    public void visit(Engine engine) {
        System.out.println("Starting my engine");
    }
 
    public void visit(Body body) {
        System.out.println("Moving my body");
    }
 
    public void visit(Car car) {
        System.out.println("Starting my car");
    }
}
 
public class VisitorDemo {
    static public void main(String[] args){
        Car car = new Car();
        car.accept(new CarElementPrintVisitor());
        car.accept(new CarElementDoVisitor());
    }
}

[edit] C++ Example

 This section contains instructions, advice, or how-to content. The purpose of Wikipedia is to present facts, not to train. Please help improve this article either by rewriting the how-to content or by moving it to Wikiversity or Wikibooks. (July 2010)

[edit] Before visitor pattern

Suppose that you have a class hierarchy with a common base class. For example, like this:

struct Element
{
  virtual ~Element() {}
};
 
struct Foo : public Element
{
  void make_foo() { cout << "Making some Foo..." << endl; }
};
 
struct Bar : public Element
{
  void make_bar() { cout << "Making some Bar..." << endl; }
};
 
struct Baz : public Element
{
  void make_baz() { cout << "Making some Baz..." << endl; }
};

You have to add several unrelated algorithms to the class hierarchy. The algorithms will work differently for each derived class.

With these conditions you can still extend the class hierarchy with the algoritms using the visitor pattern.

[edit] Adding visitor pattern

In this example we extend the above class hierarchy with

Implementing the visitor pattern is done in two steps.

  1. Define a Visitor abstact base class, and in the derived classes (MakeVisitor, CountVisitor) implement the make and count logic for Foo, Bar and Baz separately.
  2. Extend the Element hierarchy with only one member function, which is called accept(Visitor*) by convention. This needs the forward declaration of the Visitor class.

[edit] After visitor pattern

After applying the visitor pattern the code looks like this:

#include <iostream>
#include <list>
using namespace std;
 
struct Visitor;  // forward declaration (step 2)
 
struct Element
{
  virtual ~Element() {}
  virtual void accept(Visitor*) = 0;  // step 2
};
 
struct Foo : public Element
{
  void make_foo() { cout << "Making some Foo..." << endl; }
  virtual void accept(Visitor*);  // step 2
};
 
struct Bar : public Element
{
  void make_bar() { cout << "Making some Bar..." << endl; }
  virtual void accept(Visitor*);  // step 2
};
 
struct Baz : public Element
{
  void make_baz() { cout << "Making some Baz..." << endl; }
  virtual void accept(Visitor*);  // step 2
};
 
// Visitor classes (step 1)
struct Visitor
{
  virtual ~Visitor() { }
  virtual void visit(Foo*) = 0;
  virtual void visit(Bar*) = 0;
  virtual void visit(Baz*) = 0;
};
 
struct MakeVisitor : public Visitor
{
  virtual void visit(Foo* foo) { foo->make_foo(); }
  virtual void visit(Bar* bar) { bar->make_bar(); }
  virtual void visit(Baz* baz) { baz->make_baz(); }
};
 
struct CountVisitor : public Visitor
{
  CountVisitor() : foo_count(0), bar_count(0), baz_count(0) { }
  void print_counters() { cout << "Counters: Foo(" << foo_count << ") Bar("
    << bar_count << ") Baz(" << baz_count << ")" << endl; }
 
  virtual void visit(Foo*) { ++foo_count; }
  virtual void visit(Bar*) { ++bar_count; }
  virtual void visit(Baz*) { ++baz_count; }
private:
  int foo_count, bar_count, baz_count;
};
 
// Implementing the accept(Visitor*) methods (step 2)
// This has to come after the definition of the Visitor base class.
void Foo::accept(Visitor* v) { v->visit(this); }
void Bar::accept(Visitor* v) { v->visit(this); }
void Baz::accept(Visitor* v) { v->visit(this); }

The Element hierarchy with the visitors could be used like this:

int main()
{
  list<Element*> e;
  list<Visitor*> v;
  typedef list<Element*>::const_iterator e_list_iterator;
  typedef list<Visitor*>::const_iterator v_list_iterator;
 
  e.push_back(new Foo);
  e.push_back(new Foo);
  e.push_back(new Bar);
  e.push_back(new Baz);
 
  CountVisitor* cv = new CountVisitor;
  v.push_back(cv);
  v.push_back(new MakeVisitor);
 
  for (e_list_iterator i = e.begin(); i != e.end(); ++i)
    for (v_list_iterator j = v.begin(); j != v.end(); ++j)
      (*i)->accept(*j);  // double dispatch
 
  cv->print_counters();
 
  for (e_list_iterator i = e.begin(); i != e.end(); ++i) delete *i;
  for (v_list_iterator j = v.begin(); j != v.end(); ++j) delete *j;
 
  return 0;
}

Standard output of this program:

Making some Foo...
Making some Foo...
Making some Bar...
Making some Baz...
Counters: Foo(2) Bar(1) Baz(1)

Note, that adding further algorithms with the visitor pattern does not need any modification to the Element hierarchy. The accept(Visitor*) method is used for all algorithms.

The visitor pattern uses double dispatch. This means that which visit() method is called depends on two types: the dynamic type of the Element (*i), and the dynamic type of the Visitor (*j).

[edit] Alternative model

The above code is extensible only in one area, i.e. you can add more implementations of Visitor. You cannot add more implementations of Element without modifying the Visitor class. It is intrusive in that the elements like Foo are required to derive from Element, which itself is tightly coupled with Visitor, which knows all the implementations of Element. So Element is indirectly independent on all its implementations. In order to create a new Element based on an existing class without actually modifying it, it is required to write an adapter and then modify Visitor to handle this adapter.

The model can be made fully extensible through means of using handler tables. This would use polymorphism in one direction and lookup in the other.

To do this you must consider that a Visitor is no more than an identification and that the classes you write are not actually derived from a Visitor class but a Visitor<T> template class where T is the specific element. It should ideally look something like this:

template <typename T> class VisitorT<T> : public Visitor
{
public:
  typedef T value_type;
  virtual ~Visitor<T>() {}
  virtual void accept( T* t ) const = 0;
 
  explicit VisitorT( int id)
  {
     VisitorTable<T>::insert(id, this);
  }
};
 
class Element
{
public:
   virtual ~Element() {}
   virtual void visit( int id ) = 0; // or string or whatever id type you are using
};
 
template <typename T> 
class ElementT : public Element
{
private:
   T * concrete_this;
 
protected:
   explicit ElementT( T* ptr ) :
      concrete_this( ptr )
   {
   }
public:
 
   void visit( int id )
   {
      const Visitor<T> * visitor = VisitorTable<T>::lookup( id ); // to be implemented per T
      if( visitor )
      {
         visitor->accept( concrete_this );
      }
   }
};

The code is a bit more complex than above (and requires more code to write VisitorTable) however is extensible now in both directions.

element implementation over an existing class eg class Bar : ElementT<Foo> as long as Bar passes in a Foo* to the constructor of its base class.

The latter needs to be done through some global function it calls. One unique instance of the visitor should exist for each type it is handling.

There is an assumption here that Visitors do not keep state but visit() may change the state of the object being visited. Handling const-correctness is quite tricky as Visitor<const T> is not a simple co-variant of Visitor<T> so would be handled through a different table, although this is not necessarily a bad thing.

The functions do not need to return void and can take other parameters. You may want them to be able to do this to return "results" or take additional parameter information. The above should be adapted accordingly, although it is difficult to see how one can completely avoid casting if one model is applied throughout your codebase.

However if it is simply to implement a model of, say, printing objects, where you may wish to print different types, and may want to print them in different formats (eg flat text, XML, D-Bus binary), the model can be applied well passing in some kind of output stream object (that might hold state). You will be required to write implementations for the types you wish to print in their different formats but the model will be extensible in that you can add new types to be printed and new formats without having to modify any existing code.

[edit] State

Aside from potentially improving separation of concerns, the visitor pattern has an additional advantage over simply calling a polymorphic method: a visitor object can have state. This is extremely useful in many cases where the action performed on the object depends on previous such actions.

An example of this is a pretty-printer in a programming language implementation (such as a compiler or interpreter). Such a pretty-printer object (implemented as a visitor, in this example), will visit nodes in a data structure that represents a parsed and processed program. The pretty-printer will then generate a textual representation of the program tree. To make the representation human-readable, the pretty-printer should properly indent program statements and expressions. The current indentation level can then be tracked by the visitor as its state, correctly applying encapsulation, whereas in a simple polymorphic method invocation, the indentation level would have to be exposed as a parameter and the caller would rely on the method implementation to use and propagate this parameter correctly.

[edit] Visitor Pattern in a Dynamic programming language

In a dynamic object-oriented language like Common Lisp many patterns have simple implementations. The visitor pattern disappears completely. No extra classes and methods are needed. The functionality to map over the object structure can be extracted. The mapping function gets as a parameter a generic function which provides the methods for each possible class.

The Java example from above in idiomatic Common Lisp:

(defclass wheel-class ()
  ((name :accessor wheel-name :initarg :name)))
 
(defclass engine-class () ())
 
(defclass body-class () ())
 
(defclass car-class ()
  ((elements :initform nil :initarg :elements :accessor elements)))
 
(defmethod elements (object) nil)
 
(defgeneric print-it (object)
  (:method ((o wheel-class))
   (format t "Visiting ~a wheel~%" (wheel-name o)))
  (:method ((o engine-class))
   (format t "Visiting engine~%"))
  (:method ((o body-class))
   (format t "Visiting body~%"))
  (:method ((o car-class))
   (format t "Visiting car~%")))
 
(defgeneric do-it (object)
  (:method ((o wheel-class))
   (format t "Kicking my ~a wheel~%" (wheel-name o)))
  (:method ((o engine-class))
   (format t "Starting my engine~%"))
  (:method ((o body-class))
   (format t "Moving my body~%"))
  (:method ((o car-class))
   (format t "Starting my car~%")))
 
(defun map-object (function children-fn object)
  (when object
    (funcall function object)
    (mapc (lambda (child) (map-object function children-fn child))
          (funcall children-fn object))))
 
(defmethod initialize-instance :after ((o car-class) &rest initargs)
  (setf (elements o)
        (list (make-instance 'engine-class)
              (make-instance 'body-class)
              (make-instance 'wheel-class :name "front left")
              (make-instance 'wheel-class :name "front-right")
              (make-instance 'wheel-class :name "back-left")
              (make-instance 'wheel-class :name "back-right")))) 
 
(let ((car-1 (make-instance 'car-class)))
  (map-object #'print-it #'elements car-1)
  (map-object #'do-it    #'elements car-1))

[edit] See also

[edit] External links

The Wikibook Computer Science/Design Patterns has a page on the topic of
v • d • e
Design patterns in the book Design Patterns
Creational
Structural
Behavioral
Retrieved from "http://en.wikipedia.org/wiki/Visitor_pattern"
Personal tools
Namespaces
Variants
Actions
Navigation
Interaction
Toolbox
Print/export
Languages