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

Comments

  1. Nice pattern.
    Thank you!

    ReplyDelete
  2. For the acyclic visitor you can make a generic base class removing the duplication for the accept method:

    Apple : VisitableFruit(Apple) { }
    Grape : VisitableFruit(Grape) { }

    public abstract class VisitableFruit(TFruit) : Fruit where TFruit : Fruit
    {
    public override void Accept(IFruitVisitor visitor)
    {
    var fruitVisitor = visitor as IFruitVisitor(TFruit);
    TFruit thisFruit = this as TFruit;

    if(fruitVisitor != null)
    fruitVisitor.Visit(thisFruit);
    }
    }

    ReplyDelete
  3. @GeoValy: Very interesting idea! This curiously recurring pattern serves well to remove duplication. Too bad it can't really be enforced, only by convention.

    ReplyDelete
  4. thoughts on this approach: https://gist.github.com/SoundLogic/11353161 ?

    ReplyDelete
    Replies
    1. Hey,

      These are all interesting approaches! Using the self-type is good, when the clients don't cheat. Look here for some interesting discussions on this: http://blogs.msdn.com/b/ericlippert/archive/2011/02/03/curiouser-and-curiouser.aspx

      Delete
    2. Never mind - I removed the gist as I realized it wouldn't work in more advanced scenarios. This is a great introductory article, but I think it would really benefit from some explanation as to how "Accept" would be used since from the examples here it's unclear why something like the below code would not be a perfectly valid approach ( or at least I feel that there may not have been enough attention given to why Accept needs to take IFruitVisitor and not IFruitVisitor )

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

      abstract class Fruit
      where TFruit : 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);
      }
      }

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

      public FruitPicker()
      {
      Fruits = new List();
      }

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

      also, for those looking to learn more about this pattern, I would suggest this link http://c2.com/cgi/wiki?HierarchicalVisitorPattern in addition to the above link to the "Uncle" Bob Martin article.

      Delete
    3. @ Jordao - looks like we were replying at the same time. +1 for the Eric Lippert link - most of his blog entries are pretty old by now, but they are still so useful. I discovered this bit of trickery (where TFruit : Fruit) while I was working with another double-dispatch problem, but I'm not sure it works with the visitor pattern or at least it wouldn't work in all scenarios (e.g. with the hierarchical visitor pattern when the Accept method returns a bool indicating if the type is valid or not).

      Delete

Post a Comment

Popular posts from this blog

Some OO Design

NRoles: An experiment with roles in C#