Contravariance and Acyclic Vistor Pattern

Yesterday a friend of mine showed me this post that discusses the Acyclic Visitor Pattern. In the post the author shows how to use generics to create a visitor interface that does not need to know each implementation type. Instead the accepting element (or visitee) tries to downcast the visitor to its own type. Although this requires a type check within each element it still keeps the visitor interface agnostic of the implementations.

Example (base on post from above)

Classic Visitor

public interface IClassicFruit
{
    void Accept(IClassicFruitVistor visitor);
}

public interface IClassicFruitVistor
{
    void Visit(ClassicOrange lemon);
    void Visit(ClassicApple apple);
}

public class ClassicApple : IClassicFruit
{
    public void Accept(IClassicFruitVistor visitor)
    {
        visitor.Visit(this);
    }
}

public class ClassicOrange : IClassicFruit
{
    public void Accept(IClassicFruitVistor visitor)
    {
        visitor.Visit(this);
    }
}

Acyclic Visitor

public interface IFruit
{
    void Accept(IFruitVisitor visitor);
}

public interface IFruitVisitor
{
}

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

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

public class Orange : IFruit
{
    public void Accept(IFruitVisitor visitor)
    {
        if (visitor is IFruitVisitor<Orange>)
            ((IFruitVisitor<Orange>)visitor).Visit(this);
    }
}

The friend who showed this to me had an objection. He said that although this removed the need for the visitor interface to know all implementation types, it remove the ability to handle inheritance without extra (not very pretty code)

In a classic visitor I can do this

public interface IClassicFruitVistor
{
    void Visit(ClassicOrange lemon);
    void Visit(ClassicApple apple);
    void Visit(IClassicFruit fruit);
}

public class ClassicLemon : IClassicFruit
{
    public void Accept(IClassicFruitVistor visitor)
    {
        visitor.Visit(this);
    }
}

Although there is no Visit for ClassicLemon it will get picked up by Visit(IFruit),

But in the generic visitor I would need to do this.

public class Lemon : IFruit
{
    public void Accept(IFruitVisitor visitor)
    {
        if (visitor is IFruitVisitor<Lemon>)
            ((IFruitVisitor<Lemon>)visitor).Visit(this);
        else if (visitor is IFruitVisitor<IFruit>)
            ((IFruitVisitor<IFruit>)visitor).Visit(this);
    }
}

And It would be worse if I added and ICitrusFruit into the mix.

C# to the Rescue

The good news is that there is a simple solution for this problem build right into C# and all it take is 3 characters

If we make IFruitVisitor Contravariant we don’t need the extra type check anymore and we can do this for any depth of inheritance.

I made these changes to the above generic sample

public abstract class CitrusFruit : IFruit
{
    public abstract void Accept(IFruitVisitor visitor);
    public decimal Weight { get; set; }
}

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

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

And added three visitors (Apple, Orange, CitrusFruit) that look like this

public class CitrusVisitor : IFruitVisitor<CitrusFruit>
{
    public int Count;

    public void Visit(CitrusFruit fruit)
    {
        Count++;
    }
}

And then I wrote this test to prove it.

[TestMethod]
public void TestVisitors()
{
    var citrusVisitor = new CitrusVisitor();
    var fruitVisitor = new FruitVisitor();
    var appleVisitor = new AppleVisitor();

    var vistors = new IFruitVisitor[] {citrusVisitor, appleVisitor, fruitVisitor};
    var fruits = new IFruit[] {new Orange(), new Lemon(), new Apple()};

    foreach (var visitor in vistors)
    {
        foreach (var fruit in fruits)
        {
            fruit.Accept(visitor);
        }
    }

    Assert.AreEqual(1, appleVisitor.Count);
    Assert.AreEqual(2, citrusVisitor.Count);
    Assert.AreEqual(3, fruitVisitor.Count);
}

As long as the IFruitObserver<TFruit> looks like it does above, this test will fail.

As soon as we make this minor (3 char) change to the interface

public interface IFruitVisitor<in TFruit> : IFruitVisitor where TFruit : IFruit
{
    void Visit(TFruit fruit);
}

The test passes.

Did I mention that I like Generics?

Summary

I don’t know if I would recommend this pattern in this form since it still requires a down cast to the generic version of the IFruitVisitor but it is a nice demonstration of Contravariance

Leave a Reply