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 46 47 48 49 50 51 52 53 54 |
<span style="font-family: Courier New;"><span style="color: #0000ff;">public class </span><span style="color: #000000;">Program {</span> <span style="color: #0000ff;">private static void </span><span style="color: #000000;">Main(</span><span style="color: #0000ff;">string</span><span style="color: #000000;">[] args) {</span> <span style="color: #000000;">Collection<AbstractVisitor> visitors </span> <span style="color: #000000;">= </span><span style="color: #0000ff;">new </span><span style="color: #000000;">Collection<AbstractVisitor>();</span> <span style="color: #000000;">Collection<Pet> pets = </span><span style="color: #0000ff;">new </span><span style="color: #000000;">Collection<Pet>();</span></span> <span style="font-family: Courier New;"> <span style="color: #000000;">pets.Add(</span><span style="color: #0000ff;">new </span><span style="color: #000000;">Fish());</span> <span style="color: #000000;">pets.Add(</span><span style="color: #0000ff;">new </span><span style="color: #000000;">Dog());</span></span> <span style="font-family: Courier New;"> <span style="color: #000000;">visitors.Add(</span><span style="color: #0000ff;">new </span><span style="color: #000000;">Feeder());</span> <span style="color: #000000;">visitors.Add(</span><span style="color: #0000ff;">new </span><span style="color: #000000;">Walker());</span></span> <span style="font-family: Courier New;"> <span style="color: #008000;">// Visit each of the pets.</span> <span style="color: #0000ff;">foreach </span><span style="color: #000000;">(Pet pet </span><span style="color: #0000ff;">in </span><span style="color: #000000;">pets) {</span> <span style="color: #0000ff;">foreach </span><span style="color: #000000;">(AbstractVisitor visitor </span><span style="color: #0000ff;">in </span><span style="color: #000000;">visitors) {</span> <span style="color: #000000;">visitor.Visit(pet);</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #000000;"><span style="color: #003300;"> </span>}</span> <span style="color: #000000;">}</span></span> <span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Abstract base class for visitors.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public abstract class </span><span style="color: #000000;">AbstractVisitor {</span> <span style="color: #0000ff;">public abstract void </span><span style="color: #000000;">Visit(Pet pet);</span> <span style="color: #000000;">}</span> <span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Concrete visitor, a pet feeder.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public class </span><span style="color: #000000;">Feeder : AbstractVisitor {</span> <span style="color: #0000ff;">public void </span><span style="color: #000000;">Visit(Dog dog) {</span> <span style="color: #008000;">// Feed the dog</span> <span style="color: #000000;">dog.Visitors.Add(</span><span style="color: #ff00ff;">"Fed the dog"</span><span style="color: #000000;">);</span> <span style="color: #000000;">}</span> <span style="color: #0000ff;">public void </span><span style="color: #000000;">Visit(Fish fish) {</span> <span style="color: #008000;">// Feed the fish</span> <span style="color: #000000;">fish.Visitors.Add(</span><span style="color: #ff00ff;">"Fed the fish"</span><span style="color: #000000;">);</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Concrete visitor, a pet walker.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public class </span><span style="color: #000000;">Walker : AbstractVisitor {</span> <span style="color: #0000ff;">public void </span><span style="color: #000000;">Visit(Dog dog) {</span> <span style="color: #000000;">dog.Visitors.Add(</span><span style="color: #ff00ff;">"Walked the dog"</span><span style="color: #000000;">);</span> <span style="color: #000000;">}</span> <span style="color: #008000;">// Fish can't be walked!</span> <span style="color: #000000;">}</span> |
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 29 30 31 32 |
<span style="font-family: Courier New;"><span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Abstract base class for visitors.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public abstract class </span><span style="color: #000000;">AbstractVisitor {</span> <span style="color: #0000ff;">public abstract void </span><span style="color: #000000;">Visit(Pet pet);</span> <span style="color: #000000;">}</span></span> <span style="font-family: Courier New;"><span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Concrete visitor, a pet feeder.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public class </span><span style="color: #000000;">Feeder : AbstractVisitor {</span> <span style="color: #008000;">// Yucky if block...</span> <span style="color: #0000ff;">public override void </span><span style="color: #000000;">Visit(Pet pet) {</span> <span style="color: #0000ff;">if</span><span style="color: #000000;">(pet </span><span style="color: #0000ff;">is </span><span style="color: #000000;">Dog) {</span> <span style="color: #000000;">Visit(pet </span><span style="color: #0000ff;">as </span><span style="color: #000000;">Dog);</span> <span style="color: #000000;">}</span> <span style="color: #0000ff;">if</span><span style="color: #000000;">(pet </span><span style="color: #0000ff;">is </span><span style="color: #000000;">Fish) {</span> <span style="color: #000000;">Visit(pet </span><span style="color: #0000ff;">as </span><span style="color: #000000;">Fish);</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span></span> <span style="font-family: Courier New;"> <span style="color: #0000ff;">public void </span><span style="color: #000000;">Visit(Dog dog) {</span> <span style="color: #008000;">// Feed the dog</span> <span style="color: #000000;">dog.Visitors.Add(</span><span style="color: #ff00ff;">"Fed the dog"</span><span style="color: #000000;">);</span> <span style="color: #000000;">}</span></span> <span style="font-family: Courier New;"> <span style="color: #0000ff;">public void </span><span style="color: #000000;">Visit(Fish fish) {</span> <span style="color: #008000;">// Feed the fish</span> <span style="color: #000000;">fish.Visitors.Add(</span><span style="color: #ff00ff;">"Fed the fish"</span><span style="color: #000000;">);</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span></span> |
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
<span><span style="color: #0000ff;">public class </span><span style="color: #000000;">Program {</span> <span style="color: #0000ff;">private static void </span><span style="color: #000000;">Main(</span><span style="color: #0000ff;">string</span><span style="color: #000000;">[] args) {</span> <span style="color: #000000;">Collection<AbstractVisitor> visitors </span> <span style="color: #000000;">= </span><span style="color: #0000ff;">new </span><span style="color: #000000;">Collection<AbstractVisitor>();</span> <span style="color: #000000;">Collection<Pet> pets = </span><span style="color: #0000ff;">new </span><span style="color: #000000;">Collection<Pet>();</span></span> <span> <span style="color: #000000;">pets.Add(</span><span style="color: #0000ff;">new </span><span style="color: #000000;">Fish());</span> <span style="color: #000000;">pets.Add(</span><span style="color: #0000ff;">new </span><span style="color: #000000;">Dog());</span></span> <span> <span style="color: #000000;">visitors.Add(</span><span style="color: #0000ff;">new </span><span style="color: #000000;">Feeder());</span> <span style="color: #000000;">visitors.Add(</span><span style="color: #0000ff;">new </span><span style="color: #000000;">Walker());</span></span> <span> <span style="color: #008000;">// Visit each of the pets.</span> <span style="color: #0000ff;">foreach </span><span style="color: #000000;">(Pet pet </span><span style="color: #0000ff;">in </span><span style="color: #000000;">pets) {</span> <span style="color: #0000ff;">foreach </span><span style="color: #000000;">(AbstractVisitor visitor </span><span style="color: #0000ff;">in </span><span style="color: #000000;">visitors) {</span> <span style="color: #000000;">visitor.Visit(pet);</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span></span> <span> <span style="color: #008000;">// Check the results.</span> <span style="color: #0000ff;">foreach</span><span style="color: #000000;">(Pet pet </span><span style="color: #0000ff;">in </span><span style="color: #000000;">pets) {</span> <span style="color: #808000;">Console</span><span style="color: #000000;">.Out.WriteLine(pet.GetType().Name);</span> <span style="color: #0000ff;">foreach</span><span style="color: #000000;">(</span><span style="color: #808000;">String </span><span style="color: #000000;">note </span><span style="color: #0000ff;">in </span><span style="color: #000000;">pet.Visitors) {</span> <span style="color: #808000;">Console</span><span style="color: #000000;">.Out.WriteLine(</span><span style="color: #ff00ff;">"\t{0}"</span><span style="color: #000000;">, note);</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span></span> <span><span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Concrete visitor, a pet feeder.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public class </span><span style="color: #000000;">Feeder : AbstractVisitor {</span> <span style="color: #0000ff;">public void </span><span style="color: #000000;">Visit(Dog dog) {</span> <span style="color: #008000;">// Feed the dog</span> <span style="color: #000000;">dog.Visitors.Add(</span><span style="color: #ff00ff;">"Fed the dog"</span><span style="color: #000000;">);</span> <span style="color: #000000;">}</span></span> <span> <span style="color: #0000ff;">public void </span><span style="color: #000000;">Visit(Fish fish) {</span> <span style="color: #008000;">// Feed the fish</span> <span style="color: #000000;">fish.Visitors.Add(</span><span style="color: #ff00ff;">"Fed the fish"</span><span style="color: #000000;">);</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span></span> <span><span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Concrete visitor, a pet walker.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public class </span><span style="color: #000000;">Walker : AbstractVisitor {</span> <span style="color: #0000ff;">public void </span><span style="color: #000000;">Visit(Dog dog) {</span> <span style="color: #000000;">dog.Visitors.Add(</span><span style="color: #ff00ff;">"Walked the dog"</span><span style="color: #000000;">);</span> <span style="color: #000000;">}</span></span> <span> <span style="color: #008000;">// Fish can't be walked!</span> <span style="color: #000000;">}</span></span> <span><span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Base class for pets.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public abstract class </span><span style="color: #000000;">Pet {</span> <span style="color: #0000ff;">private readonly </span><span style="color: #000000;">Collection<</span><span style="color: #0000ff;">string</span><span style="color: #000000;">> visitors;</span></span> <span> <span style="color: #0000ff;">public </span><span style="color: #000000;">Collection<</span><span style="color: #0000ff;">string</span><span style="color: #000000;">> Visitors {</span> <span style="color: #000000;">get { </span><span style="color: #0000ff;">return </span><span style="color: #000000;">visitors; }</span> <span style="color: #000000;">}</span></span> <span> <span style="color: #0000ff;">protected </span><span style="color: #000000;">Pet() {</span> <span style="color: #000000;">visitors = </span><span style="color: #0000ff;">new </span><span style="color: #000000;">Collection<</span><span style="color: #0000ff;">string</span><span style="color: #000000;">>();</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span></span> <span><span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// A pet fish.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public class </span><span style="color: #000000;">Fish : Pet {}</span></span> <span><span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// A pet dog.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public class </span><span style="color: #000000;">Dog : Pet {}</span></span> |
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 35 36 37 38 |
<span style="font-family: Courier New;"><span style="color: #008000;">/// <summary></span> <span style="color: #008000;">/// Abstract base class for visitors.</span> <span style="color: #008000;">/// </summary></span> <span style="color: #0000ff;">public abstract class </span><span style="color: #000000;">AbstractVisitor {</span> <span style="color: #0000ff;">private static readonly </span><span style="color: #000000;">Dictionary<</span><span style="color: #0000ff;">long</span><span style="color: #000000;">, </span><span style="color: #808000;">MethodInfo</span><span style="color: #000000;">> dispatch;</span></span> <span style="font-family: Courier New;"> <span style="color: #0000ff;">static </span><span style="color: #000000;">AbstractVisitor() {</span> <span style="color: #000000;">dispatch = </span><span style="color: #0000ff;">new </span><span style="color: #000000;">Dictionary<</span><span style="color: #0000ff;">long</span><span style="color: #000000;">, </span><span style="color: #808000;">MethodInfo</span><span style="color: #000000;">>();</span></span> <span style="font-family: Courier New;"> <span style="color: #0000ff;">foreach </span><span style="color: #000000;">(</span><span style="color: #808000;">Type </span><span style="color: #000000;">t </span><span style="color: #0000ff;">in </span><span style="color: #808000;">Assembly</span><span style="color: #000000;">.GetCallingAssembly().GetTypes()) {</span> <span style="color: #0000ff;">if </span><span style="color: #000000;">(t.IsSubclassOf(</span><span style="color: #0000ff;">typeof</span><span style="color: #000000;">(AbstractVisitor))) {</span> <span style="color: #0000ff;">foreach </span><span style="color: #000000;">(</span><span style="color: #808000;">MethodInfo </span><span style="color: #000000;">mi </span><span style="color: #0000ff;">in </span><span style="color: #000000;">t.GetMethods()) {</span> <span style="color: #0000ff;">if </span><span style="color: #000000;">(mi.Name == </span><span style="color: #ff00ff;">"Visit"</span><span style="color: #000000;">) {</span> <span style="color: #808000;">ParameterInfo</span><span style="color: #000000;">[] pars = mi.GetParameters();</span> <span style="color: #0000ff;">if </span><span style="color: #000000;">(pars.Length == </span><span style="color: #800080;">1</span><span style="color: #000000;">) {</span> <span style="color: #808000;">Int64 </span><span style="color: #000000;">code = ((</span><span style="color: #808000;">Int64</span><span style="color: #000000;">)t.GetHashCode() << </span><span style="color: #800080;">32</span><span style="color: #000000;">) +</span> <span style="color: #000000;">pars[</span><span style="color: #800080;">0</span><span style="color: #000000;">].ParameterType.GetHashCode();</span> <span style="color: #000000;">dispatch.Add(code, mi);</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span></span> <span style="font-family: Courier New;"> <span style="color: #0000ff;">public virtual void </span><span style="color: #000000;">Visit(</span><span style="color: #0000ff;">object </span><span style="color: #000000;">pet) {</span> <span style="color: #808000;">Int64 </span><span style="color: #000000;">hash = ((</span><span style="color: #808000;">Int64</span><span style="color: #000000;">)GetType().GetHashCode() << </span><span style="color: #800080;">32</span><span style="color: #000000;">) + </span> <span style="color: #000000;">pet.GetType().GetHashCode();</span> <span style="color: #0000ff;">if </span><span style="color: #000000;">(dispatch.ContainsKey(hash)) {</span> <span style="color: #000000;">dispatch[hash].Invoke(</span><span style="color: #0000ff;">this</span><span style="color: #000000;">, </span><span style="color: #0000ff;">new object</span><span style="color: #000000;">[] { pet });</span> <span style="color: #000000;">}</span> <span style="color: #0000ff;">else </span><span style="color: #000000;">{</span> <span style="color: #008000;">// This is our fallback functionality</span> <span style="color: #808000;">Console</span><span style="color: #000000;">.WriteLine(</span><span style="color: #ff00ff;">"Visiting object " </span><span style="color: #000000;">+ pet.ToString());</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span> <span style="color: #000000;">}</span></span> |
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.