C# Visitor Pattern – Using with Large Object Hierarchy

cdesign-patternsobject-orientedvisitor-pattern

Context

I've been using with a hierarchy of objects (an expression tree) a "pseudo" visitor pattern (pseudo, as in it does not use double dispatch) :

 public interface MyInterface
 {
      void Accept(SomeClass operationClass);
 }

 public class MyImpl : MyInterface 
 {
      public void Accept(SomeClass operationClass)
      {   
           operationClass.DoSomething();
           operationClass.DoSomethingElse();
           // ... and so on ...
      }
 }

This design was, however questionnable, pretty comfortable since the number of implementations of MyInterface is significant (~50 or more) and I didn't need to add extra operations.

Each implementation is unique (it's a different expression or operator), and some are composites (ie, operator nodes that will contain other operator/leaf nodes).

Traversal is currently performed by calling the Accept operation on the root node of the tree, which in turns calls Accept on each of its child nodes, which in turn… and so on…

But the time has come where I need to add a new operation, such as pretty printing :

 public class MyImpl : MyInterface 
 {
      // Property does not come from MyInterface
      public string SomeProperty { get; set; }

      public void Accept(SomeClass operationClass)
      {   
           operationClass.DoSomething();
           operationClass.DoSomethingElse();
           // ... and so on ...
      }

      public void Accept(SomePrettyPrinter printer)
      {
           printer.PrettyPrint(this.SomeProperty);
      }
 }

I basically see two options :

Keep the same design, adding a new method for my operation to each derived class, at the expense of maintainibility (not an option, IMHO)
Use the "true" Visitor pattern, at the expense of extensibility (not an option, as I expect to have more implementations coming along the way…), with about 50+ overloads of the Visit method, each one matching a specific implementation ?

Question

Would you recommand using the Visitor pattern ? Is there any other pattern that could help solve this issue ?

Best Answer

I have been using the visitor pattern to represent expression trees over the course of 10+ years on six large-scale projects in three programming languages, and I am very pleased with the outcome. I found a couple of things that made applying the pattern a lot easier:

Do not use overloads in the interface of the visitor

Put the type into the method name, i.e use

IExpressionVisitor {
    void VisitPrimitive(IPrimitiveExpression expr);
    void VisitComposite(ICompositeExpression expr);
}

rather than

IExpressionVisitor {
    void Visit(IPrimitiveExpression expr);
    void Visit(ICompositeExpression expr);
}

Add an "catch unknown" method to your visitor interface.

It would make it possible for users who cannot modify your code:

IExpressionVisitor {
    void VisitPrimitive(IPrimitiveExpression expr);
    void VisitComposite(ICompositeExpression expr);
    void VisitExpression(IExpression expr);
};

This would let them build their own implementations of IExpression and IVisitor that "understands" their expressions by using run-time type information in the implementation of their catch-all VisitExpression method.

Provide a default do-nothing implementation of `IVisitor` interface

This would let users who need to deal with a subset of expression types build their visitors faster, and make their code immune to you adding more methods to IVisitor. For example, writing a visitor that harvests all variable names from your expressions becomes an easy task, and the code will not break even if you add a bunch of new expression types to your IVisitor later on.

Related Solutions

Java – Visitor stability vs instanceof flexibility

You could use visitor with instanceOf

interfaces:

interface Visitable {
  void accept(Object visitor);
}
interface AVisitor {
  void visitA(A a);
}
interface BVisitor {
  void visitB(B b);
}
interface CVisitor {
  void visitB(C c);
}

Visitables:

class C implements Visitable {
  public void accept(Object visitor) {
    if (visitor instanceof CVisitor) {
      ((BVisitor)vistor).visitC(this);
    }
  }
}

class B implements Visitable {
  public void accept(Object visitor) {
    if (visitor instanceof BVisitor) {
      ((BVisitor)vistor).visitB(this);
    }
  }
}

class A extends B implements Visitable {
  public void accept(Object visitor) {
    super.accept(visitor);
    if (visitor instanceof AVisitor) {
      ((AVisitor)vistor).visitA(this);
    }
  }
}

Visitors:

class PrintBs implements BVisitor {
  public void visitB(B b) {
    system.out.println(b);
  }
}

class PrintAs implements AVisitor {
  public void visitA(A a) {
    system.out.println(a);
  }
}

class PrintCs implements CVisitor {
  public void visitC(C c) {
    system.out.println(c);
  }
}
class PrintAsAndCs implements CVisitor, AVisitor{
  public void visitA(A a) {
    system.out.println(a);
  }
  public void visitC(C c) {
    system.out.println(c);
  }
}

each class knows only about its related interfaces, so adding new vistors nor visitables requires changing everything in that category (visitor/visitable) (for visitor, it does not require changing anything, for visitable it requires creating new visitor interface, but again, no changing of existing objects).

This way, there is no chain of instanceof tests and visitor for subset does not need to even know about types outside this subset.

Question is what to do with situation where A extends B (and B is Visitable too), in that case, you could just add super.accept(visitor) into accept (thus it would be short chain of instanceof-s, but onlu as long as hierarchy is deep, and it should not be too deep to matter, abd you don't need to write it whole manually).

Visitor Pattern – Implementing for an Abstract Syntax Tree

It is up to the visitor implementation to decide whether to visit child nodes and in which order. That's the whole point of the visitor pattern.

In order to adapt the visitor for more situations it is helpful (and quite common) to use generics like this (it's Java):

public interface ExpressionNodeVisitor<R, P> {
    R visitNumber(NumberNode number, P p);
    R visitBinary(BinaryNode expression, P p);
    // ...
}

And an accept method would look like this:

public interface ExpressionNode extends Node {
    <R, P> R accept(ExpressionNodeVisitor<R, P> visitor, P p);
    // ...
}

This allows to pass additional parameters to visitor and retrieve a result from it. So, the expression evaluation can be implemented like this:

public class EvaluatingVisitor
    implements ExpressionNodeVisitor<Double, Void> {
    public Double visitNumber(NumberNode number, Void p) {
        // Parse the number and return it.
        return Double.valueOf(number.getText());
    }
    public Double visitBinary(BinaryNode binary, Void p) {
        switch (binary.getOperator()) {
        case '+':
            return binary.getLeftOperand().accept(this, p)
                + binary.getRightOperand().accept(this, p);
        // More cases for other operators here.
        }
    }
}

The accept method parameter isn't used in the above example, but just believe me: it is quite useful to have one. For example, it can be a Logger instance to report errors to.