Double Dispatch To The Rescue
In working out a tricky design issue surrounding the usage of the Visitor pattern, I stumbled upon the related Double Dispatch pattern/mechanism.
In short, double dispatch, when implemented, allows an object – a “dispatcher” – to delegate method calls based on the runtime type or types involved in the interaction.
The two core problems with visitor are that:
- You must have access to the visitable object to implement an IVisitable interface. Often times, when dealing with binary code references, this is not an option.
- Each visitor must implement IVisitor, regardless of whether all of the Visit() interactions make any sense. This means that if there are 10 concrete IVisitable classes, then each IVisitor must implement 10 Visit() methods that support each of the concrete classes, even if the particular IVisitor has no valid operations on a given IVisitable.
I suppose point number 1 is not really a constraint, it’s just that it’s a criterion for a by-the-book visitor pattern implementation. But point number 2 is a really sticky situation since in many cases, not all of the IVisitor concrete classes should support all of the IVisitable concrete classes. Of course we could just add a blank method stub, even for operations that don’t make sense, but that just seems like bloat and a maintenance nightmare.
The key in understanding the use of double dispatch is to understand the core issue with the Visitor pattern. We want the visitor to perform different operations based on the runtime type passed into a call to an abstract Visitor base class. Unlike method overloading, which relies on compile time types to determine the method to invoke, we want the code to decide which method to invoke based on the runtime type of the object being passed in.
Ideally, we could have a scenario like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
public class Program { private static void Main(string[] args) { Collection<AbstractVisitor> visitors = new Collection<AbstractVisitor>(); Collection<Pet> pets = new Collection<Pet>(); pets.Add(new Fish()); pets.Add(new Dog()); visitors.Add(new Feeder()); visitors.Add(new Walker()); // Visit each of the pets. foreach (Pet pet in pets) { foreach (AbstractVisitor visitor in visitors) { visitor.Visit(pet); } } } } /// <summary> /// Abstract base class for visitors. /// </summary> public abstract class AbstractVisitor { public abstract void Visit(Pet pet); } /// <summary> /// Concrete visitor, a pet feeder. /// </summary> public class Feeder : AbstractVisitor { public void Visit(Dog dog) { // Feed the dog dog.Visitors.Add("Fed the dog"); } public void Visit(Fish fish) { // Feed the fish fish.Visitors.Add("Fed the fish"); } } /// <summary> /// Concrete visitor, a pet walker. /// </summary> public class Walker : AbstractVisitor { public void Visit(Dog dog) { dog.Visitors.Add("Walked the dog"); } // Fish can't be walked! } |
But this code doesn’t work! Both Walker an Feeder must now implement Visit(Pet pet) like so:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/// <summary> /// Abstract base class for visitors. /// </summary> public abstract class AbstractVisitor { public abstract void Visit(Pet pet); } /// <summary> /// Concrete visitor, a pet feeder. /// </summary> public class Feeder : AbstractVisitor { // Yucky if block... public override void Visit(Pet pet) { if(pet is Dog) { Visit(pet as Dog); } if(pet is Fish) { Visit(pet as Fish); } } public void Visit(Dog dog) { // Feed the dog dog.Visitors.Add("Fed the dog"); } public void Visit(Fish fish) { // Feed the fish fish.Visitors.Add("Fed the fish"); } } |
This is a less than desirable situation since for every new pet type we introduce, we need to introduce another entry in the if-else block. Yuck.
While there were many articles on how to implement double dispatch in C# using various techniques, by far, the simplest implementation that I found was one by Anthony Cowley.
So let’s see how our code would look using this technique (I’ll omit the implmentation of the abstract visitor class for now):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
public class Program { private static void Main(string[] args) { Collection<AbstractVisitor> visitors = new Collection<AbstractVisitor>(); Collection<Pet> pets = new Collection<Pet>(); pets.Add(new Fish()); pets.Add(new Dog()); visitors.Add(new Feeder()); visitors.Add(new Walker()); // Visit each of the pets. foreach (Pet pet in pets) { foreach (AbstractVisitor visitor in visitors) { visitor.Visit(pet); } } // Check the results. foreach(Pet pet in pets) { Console.Out.WriteLine(pet.GetType().Name); foreach(String note in pet.Visitors) { Console.Out.WriteLine("\t{0}", note); } } } } /// <summary> /// Concrete visitor, a pet feeder. /// </summary> public class Feeder : AbstractVisitor { public void Visit(Dog dog) { // Feed the dog dog.Visitors.Add("Fed the dog"); } public void Visit(Fish fish) { // Feed the fish fish.Visitors.Add("Fed the fish"); } } /// <summary> /// Concrete visitor, a pet walker. /// </summary> public class Walker : AbstractVisitor { public void Visit(Dog dog) { dog.Visitors.Add("Walked the dog"); } // Fish can't be walked! } /// <summary> /// Base class for pets. /// </summary> public abstract class Pet { private readonly Collection<string> visitors; public Collection<string> Visitors { get { return visitors; } } protected Pet() { visitors = new Collection<string>(); } } /// <summary> /// A pet fish. /// </summary> public class Fish : Pet {} /// <summary> /// A pet dog. /// </summary> public class Dog : Pet {} |
When I run this program, I get the following output:
As expected, the dog was walked and fed, but the fish was only fed. Now we can go about adding pets to our heart’s content and we won’t be forced to add another Visit() method declaration. If there is no Visit() method implemented for a particular pet type, then nothing happens and the default implementation of Visit() on the abstract class handles it. The magic all happens in Cowley’s implementation of AbstractVisitor:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/// <summary> /// Abstract base class for visitors. /// </summary> public abstract class AbstractVisitor { private static readonly Dictionary<long, MethodInfo> dispatch; static AbstractVisitor() { dispatch = new Dictionary<long, MethodInfo>(); foreach (Type t in Assembly.GetCallingAssembly().GetTypes()) { if (t.IsSubclassOf(typeof(AbstractVisitor))) { foreach (MethodInfo mi in t.GetMethods()) { if (mi.Name == "Visit") { ParameterInfo[] pars = mi.GetParameters(); if (pars.Length == 1) { Int64 code = ((Int64)t.GetHashCode() << 32) + pars[0].ParameterType.GetHashCode(); dispatch.Add(code, mi); } } } } } } public virtual void Visit(object pet) { Int64 hash = ((Int64)GetType().GetHashCode() << 32) + pet.GetType().GetHashCode(); if (dispatch.ContainsKey(hash)) { dispatch[hash].Invoke(this, new object[] { pet }); } else { // This is our fallback functionality Console.WriteLine("Visiting object " + pet.ToString()); } } } |
You may have spotted an issue here: since the Visit() method is virtual, the subclasses of AbstractVisitor aren’t strictly forced to define a Visit() method of any sort nor is there a constraint that forces any implementation to have only one argument. But this is just fine, since all of the classes must inherit from AbstractVisitor to participate in this pattern, it will also inherit the default implementation of Visit() which, conveniently, contains a fallback do-nothing behavior.
You can download the full source here: SimpleDoubleDispatchSample.zip (4.08 KB)
I also have a second sample that I modified from Cowley’s code that uses singleton instances of the visitors and improved encapsulation of the dispatch lookup table. I also modified the catch all virtual Visit() method to a call to another virtual method to allow subclasses to change the default implementation of the case that no specific Visit() is found: SimpleDoubleDispatchSample.2.zip (4.12 KB)
Once again, credit goes to Anthony Cowley for an excellent and simple implementation of double dispatch in C#. There were two others that I examined, namely one by Max Hajek (which actually generated IL) and one by Steve Love using Generics. In both cases, I thought the solutions were far more complex than the actual problem that they tried to solve, though Max’s solution seems far more powerful and may be more useful in some scenarios.
