The Acyclic Visitor Pattern

Knock knock

The visitor design pattern is a way to add new operations to a hierarchy of classes without having to change the hierarchy itself.

For example, with a simple hierarchy of fruits, you can have an IFruitVisitor interface that operates on the different classes in the hierarchy (in C#):

interface IFruitVisitor {
  void Visit(Apple apple);
  void Visit(Grape grape);
}

The hierarchy classes then accept the visitor and fulfil the double-dispatching necessary to call the right Visit method:

abstract class Fruit {
  public abstract void Accept(IFruitVisitor visitor);
}

class Apple : Fruit {
  public override void Accept(IFruitVisitor visitor) {
    visitor.Visit(this);
  }
}

class Grape : Fruit {
  public int NumberOfGrapes { get; set; }
  public override void Accept(IFruitVisitor visitor) {
    visitor.Visit(this);
  }
}

Note how each Accept method looks the same but is actually dispatching to a different method in the visitor (Visit(Apple) and Visit(Grape)).

Visitors then implement the IFruitVisitor interface to execute their own specific logic against the hierarchy. Creating new visitors is akin to adding new behavior to the hierarchy classes without changing them. Here's a visitor that picks apples:

class ApplePicker : IFruitVisitor {
  public List<Apple> Apples { get; private set; }

  public ApplePicker() {
    Apples = new List<Apple>();
  }

  public void Visit(Apple apple) {
    Apples.Add(apple);
  }
  public void Visit(Grape grape) { }
}

It works as a builder, collecting all apples from the visited fruits:

List<Fruit> fruits = ....

var applePicker = new ApplePicker();
fruits.ForEach(fruit => fruit.Accept(applePicker));

var allApples = applePicker.Apples;

Other visitors can easily be created without impacting the hierarchy, like a price or a weight calculator visitor:

class FruitWeightCalculatorVisitor : IFruitVisitor {
  public decimal WeightInGrams { get; private set; }

  public void Visit(Apple apple) {
    WeightInGrams += appleWeight;
  }
  public void Visit(Grape grape) { 
    WeightInGrams += grape.NumberOfGrapes * singleGrapeWeight;
  }

  private readonly decimal appleWeight = 150m;
  private readonly decimal singleGrapeWeight = 0.6m;
}

The visitor also has some disadvantages:

• It's a clumsy pattern: it requires repetitive code in the hierarchy classes to implement double-dispatching. It can be seem as a workaroud for the shortcomings of mainstream languages (e.g. Java, C# and C++). Also, the client code has to deal with the visitors, resulting in a bulky API.
• It assumes that the hierarchy of visited classes doesn't change. If it changes, the visitor interface and all existing visitors must be updated to accomodate the change. There's a cyclic dependency between the classes in the hierarchy and the methods in the visitor.

Smoke and mirrors

Extension methods can be used to make the pattern look more transparent to users:

static class FruitExtensions {
  public static IEnumerable<Apple> PickApples(this IEnumerable<Fruit> fruits) {
    var applePicker = new ApplePicker();
    foreach (var fruit in fruits) fruit.Accept(applePicker);
    return applePicker.Apples;
  }
}

Clients now don't need to know about the visitor to execute its logic:

List<Fruit> fruits = new List<Fruit>();
var allApples = fruits.PickApples();

Other visitors can introduce similar methods to ease consumption of the added functionality.

The acyclic visitor

To remove the cyclic dependency between hierarchy classes and visitor methods, the acyclic visitor pattern prescribes separate visitor interfaces for each different class in the hierarchy. In C#, a generic interface can be used for this:

interface IFruitVisitor {}
interface IFruitVisitor<TFruit> : IFruitVisitor
  where TFruit : Fruit {
  void Visit(TFruit fruit);
}

In Java, because of type erasure, each class must have its own dedicated interface:

interface FruitVisitor {}
interface AppleVisitor extends FruitVisitor {
  void visit(Apple apple);
}
interface GrapeVisitor extends FruitVisitor {
  void visit(Grape grape);
}

Back to C#, the degenerate interface IFruitVisitor is used in the hierarchy base class:

abstract class Fruit {
  public abstract void Accept(IFruitVisitor visitor);
}

Each visitable class in the hierarchy then checks if the given visitor supports it before calling it:

class Apple : Fruit {
  public override void Accept(IFruitVisitor visitor) {
    if (visitor is IFruitVisitor<Apple>) {
      ((IFruitVisitor<Apple>)visitor).Visit(this);
    }
  }
}

class Grape : Fruit {
  public int NumberOfGrapes { get; set; }
  public override void Accept(IFruitVisitor visitor) {
    if (visitor is IFruitVisitor<Grape>) {
      ((IFruitVisitor<Grape>)visitor).Visit(this);
    }
  }
}

The type checks and casting expressions make many people uncomfortable. They're not a problem though, since each class only checks for its own visitor interface. Apples won't mix with grapes.

Visitor implementations can then pick and choose which hierarchy classes they visit.

The apple picker will only visit apples:

class ApplePicker : IFruitVisitor<Apple> {
  public List<Apple> Apples { get; private set; }

  public ApplePicker() {
    Apples = new List<Apple>();
  }

  public void Visit(Apple apple) {
    Apples.Add(apple);
  }
}

The weight calculator visitor will visit all fruits:

class FruitWeightCalculatorVisitor : 
  IFruitVisitor<Apple>, IFruitVisitor<Grape> {
  ...
}

Adding a new fruit to the hierarchy won't impact all the visitors, only the ones that are interested in the new fruit:

class Banana : Fruit {
  public int NumberOfFingers { get; set; }
  public override void Accept(IFruitVisitor visitor) {
    if (visitor is IFruitVisitor<Banana>) {
      ((IFruitVisitor<Banana>)visitor).Visit(this);
    }
  }
}

The apple picker doesn't need to change, only the weight calculator. To force visitors that always need to know about all fruits to fail compilation, the following interface can be used:

interface IAllFruitsVisitor : 
  IFruitVisitor<Apple>, 
  IFruitVisitor<Grape>, 
  IFruitVisitor<Banana> {}

Then, the introduction of the Banana class (and the change to the above interface) will make the following weight calculator fail compilation until the banana visitor method is implemented:

class FruitWeightCalculatorVisitor : IAllFruitsVisitor {
  ...
  public void Visit(Banana banana) { 
    WeightInGrams += 
      banana.NumberOfFingers * bananaFingerWeight;
  }

  private readonly decimal bananaFingerWeight = 125m;
  ...
}

Also, with the current generic implementation, some visitors can be made generic. The apple picker could become a generic fruit picker:

class FruitPicker<TFruit> : IFruitVisitor<TFruit>
  where TFruit : Fruit {
  public List<TFruit> Fruits { get; private set; }

  public FruitPicker() {
    Fruits = new List<TFruit>();
  }

  public void Visit(TFruit fruit) {
    Fruits.Add(fruit);
  }
}

The acyclic visitor is useful if you foresee changes to the hierarchy and if there are visitors that don't need to know about all types in the hierarchy, especially new ones. This way, adding a new type won't create a ripple effect of changes through all visitors, only to the ones that need to operate on all types.

Epilogue

I first learned about the acyclic visitor from an article by Robert Martin. Unfortunately, I can't seem to find that article on the web anymore. But, you can still find the pattern described in his book Agile Principles, Patterns, and Practices in C#.