C# Method Dispatch

Sometimes some of us do things just to see how they'll work out. I recently had a situation building a system in C# in which I wanted multiple dispatch (double dispatch, in particular), so I'm posting this to show how I made my system work in the hopes that it will be helpful to others, or that someone else can point out an obviously preferable solution that I missed in my excitement to try something I hadn't done before.

The main problem is that I wanted to incrementally build a system by creating subclasses capable of handling particular events. As new events are added to the system, a new subclass is created that can store any relevant state and implement handlers for the relevant events. This can generically be viewed as a state machine formulation, in which the subclasses are states, and the events, as I've called them, initiate state transitions. So, I've got a reference to one of these state objects at runtime — the reference is of a type that is defined by a class that is a common ancestor of all the state classes — that I want to use to handle events given to me by some factory mechanism. The event object I want the current state to handle is similarly referenced by a variable of a type defined by a class that is a common ancestor of all my event subclasses. Well, the problem here is that the compiler, using static type information, can only ever call the event handler of the state base class. Making that method virtual would allow for a runtime resolution of the type of the caller, so that I could overload a handler method with a particular signature. But that would mean that my base class would need to define virtual handlers for every event type, and that sounds like a big pain in the neck. On the one hand, the system that doesn't involve overloading a single virtual method doesn't do what I need at all (the custom handlers defined in the subclasses are never invoked), but, on the other hand, there's already built-in support for fallback functionality. I'd like to retain the behavior that the base state class' handler method will be called if there is no more specific handler implemented by the state object's type.



Double Dispatch

What I really want to happen at this juncture is to have a line of code that looks like

currentState.Handle(currentEvent);

that invokes the most type-specific Handle method possible given the type of the currentState object and the type of the currentEvent object. This behavior is known as multiple dispatch, which is in contrast to the way most object-oriented languages work. Typical method invocation syntax in object-oriented languages puts one parameter of the method in a very special syntactic position: before the dot. For example, the invocation foo.bar(); looks up the bar method defined by the type of foo. But note that foo, here, is actually a parameter of some implementation of the bar method, even though it is not written that way in the source code.

That behavior — single dispatch — is not enough in this case. I'm going to pass my method a parameter with code that looks like this:

BaseState currentState;
...
BaseEvent currentEvent = GetEvent();
currentState.Handle(currentEvent);

and I want the message to dispatch to the correct method based on the runtime types of both currentState and currentEvent. Overloading virtual functions won't get me that far!

What I need is double dispatch, and the fact that C# doesn't provide this should not be an impediment. Sure, we could build a big conditional statement that looks at the type of the argument and then figures out what to do from there, but that would make everyone who looked at the program ill. Not only would a bunch of conditional statements be ugly, it would mean that we would have to update the base class' Handle method every time we add an event type. That's nuts! So here's another approach.

The basic idea is that the base class' Handle method should reflect over its own type to find what Handle methods it has defined. When this happens on an object that derives from the base class, we will discover the "overloaded" methods defined in the subclasses (note: this is not, strictly speaking, overriding, but it is, intuitively, overloading the method name). We can look at all the versions of the Handle method, and pick the one that takes a parameter of the same type as the parameter that was passed to this base class method. If no match exists, the base class can provide some fallback functionality (maybe just raise an error to describe what happened).

So that gets us to a simplistic form of multiple dispatch, but it does involve reflecting over a type at each method invocation. Luckily, we can speed that up a bit very easily. In a static constructor of the base class, we can reflect over all the types in the assembly (note, you could do this whenever an assembly is loaded if you wanted a more dynamic plugin architecture), picking out those that derive from our base state class. We can then find all the Handle methods in those classes, and store them in a hash table that will be inspected whenever the base class' instance Handle method is called. Now we can add state classes that handle certain events, but have fallback functionality for event types that aren't explicitly handled, without having to change any code anywhere else!

Here we see code from the base class' static constructor. It finds all the relevant types in the Assembly, and caches method information for each.

dispatch = new Dictionary<Int64, MethodInfo>();

foreach(Type t in Assembly.GetCallingAssembly().GetTypes())
{
    if(t.IsSubclassOf(typeof(MyBase)))
    {
        foreach(MethodInfo mi in t.GetMethods())
        {
            if(mi.Name == "Handle")
            {
                ParameterInfo[] pars = mi.GetParameters();
                if(pars.Length == 1)
                {
                    Int64 code = ((Int64)t.GetHashCode() << 32) + 
                        pars[0].ParameterType.GetHashCode();
                    dispatch.Add(code, mi);
                }
            }
        }
    }
}

The base class' instance method that we want to overload with more specific behaviors in subclasses is where the double dispatch actually happens.

// This is the magic method that we want to overload based on runtime types.
public virtual void Handle(object o)
{
    Int64 hash = ((Int64)this.GetType().GetHashCode() << 32) + 
        o.GetType().GetHashCode();

    if(dispatch.ContainsKey(hash))
    {
        dispatch[hash].Invoke(this, new object[] {o});
    }
    else
    {
        // This is our fallback functionality
        Console.WriteLine("Handling object " + o.ToString());
    }
}

Here is a simple C# program that demonstrates this technique. I've tried to keep things simple so that you can basically drop the static constructor code into any base class, and just change the name of the method you want to invoke with double dispatch. By keeping state classes in their own files, you can keep a project highly modular, so that multiple developers can add new subclasses to the system without ever even having to edit the same file.