Introduction
Sometimes you come across a design problem that cries out for using the Visitor pattern, but you just cannot use it because new Visitors are to be loaded at runtime, for example from plug-ins. Other times, you have a situation where the action chosen is parameterized over two types instead of one - and again you cannot use a classical Visitor pattern. This article presents a solution to both kind of scenarios. Included with the source is a quite complete suite of unit tests. Beware that in order to build the source, you need the PowerCollections library from Wintellect - a library which I could not live without, cheers to the folks at Wintellect - and MbUnit.
The classical Visitor pattern, its motivation, its benefits
Let's look at the classical Visitor pattern. Say you want to implement a model of mathematical expressions as a composite:
public interface IExpression
{
}
public class UnaryFunction : IExpression
{
readonly string mName;
readonly IExpression mArgument;
public UnaryFunctionNode(string name, IExpression argument)
{
mName= name;
mArgument= argument;
}
public string Name
{
get { return mName; }
}
public IExpression Argument
{
get { return mArgument; }
}
}
public class Addition : IExpression
{
readonly IExpression mLeftHandSide;
readonly IExpression mRightHandSide;
public Addition(IExpression lhs, IExpression rhs)
{
mLeftHandSide= lhs;
mRightHandSide= rhs;
}
public IExpression LeftHandSide
{
get { return mLeftHandSide; }
}
public IExpression RightHandSide
{
get { return mRightHandSide; }
}
}
public class Number : IExpression
{
readonly int mValue;
public Number(int value)
{
mValue= value;
}
public int Value
{
get { return mValue; }
}
}With such a structure, you could build composite expressions like:
IExpression exp= new UnaryFunction("sin",
new Addition(new Number(30), new Number(15)));Now at some point, you want to do something with such expressions. For simplicities sake, let's assume you want to pretty-print them. A non-OO approach for doing that could look like that:
public class ExpressionPrinter
{
public void Print(IExpression expression)
{
if (expression is Number)
{
Console.Write(expression as Number).Value);
}
else if (expression is Addition)
{
Addition add= expression as Addition;
Print(add.LeftHandSide);
Console.Write('+');
Print(add.RightHandSide);
}
else if (expression is UnaryFunction)
{
UnaryFunction fun= expression as UnaryFunction;
Console.Write(fun.Name);
Console.Write('(');
Print(fun.Argument);
Console.Write(')');
}
else
throw new ArgumentException("Unknown type.")
}
}There are several drawbacks with this approach. For one, we got plenty of conditional statements in there, thus increasing the cyclomatic complexity of the code with each new type. Second, if a new type implementing
IExpression is added, it's easy to forget to code the corresponding if-branch in the
Print() method. Third, if you want to add a new operation on expressions, you'll have to write all the logic for determining the concrete type again. The typical OO way of achieving the same would look like this:
public interface IExpression
{
void Accept(IExpressionVisitor visitor);
}
public interface IExpressionVisitor
{
void Visit(UnaryFunction function);
void Visit(Addition addition);
void Visit(Number number);
}
public class UnaryFunction : IExpression
{
readonly string mName;
readonly IExpression mArgument;
public UnaryFunctionNode(string name, IExpression argument)
{
mName= name;
mArgument= argument;
}
public string Name
{
get { return mName; }
}
public IExpression Argument
{
get { return mArgument; }
}
public void Accept(IExpressionVisitor visitor)
{
visitor.Visit(this);
}
}
public class Addition : IExpression
{
readonly IExpression mLeftHandSide;
readonly IExpression mRightHandSide;
public Addition(IExpression lhs, IExpression rhs)
{
mLeftHandSide= lhs;
mRightHandSide= rhs;
}
public IExpression LeftHandSide
{
get { return mLeftHandSide; }
}
public IExpression RightHandSide
{
get { return mRightHandSide; }
}
public void Accept(IExpressionVisitor visitor)
{
visitor.Visit(this);
}
}
public class Number : IExpression
{
readonly int mValue;
public Number(int value)
{
mValue= value;
}
public int Value
{
get { return mValue; }
}
public void Accept(IExpressionVisitor visitor)
{
visitor.Visit(this);
}
}
public class ExpressionPrinter : IExpressionVisitor
{
public void Visit(UnaryFunction function)
{
Console.Write(function.Name);
Console.Write('(');
function.Argument.Accept(this);
Console.Write(')');
}
public void Visit(Addition addition)
{
addition.LeftHandSide.Accept(this);
Console.Write('+');
addition.RightHandSide.Accept(this);
}
public void Visit(Number number)
{
Console.Write(number.Value);
}
}The logic for dispatching to the concrete type is now moved to the compiler. In the
Accept() implementations, it knows the concrete type of this and thus can infer which overload of
Visit() it needs to call. If you add a new implementation of
IExpression, you will need to implement the
Accept() method, otherwise the compiler will give you an error. Once you implement it, you'll also have to add the corresponding
Visit() method to
IExpressionVisitor to avoid compile-time errors. Once you have done this, all implementations of
IExpressionVisitor need to implement the new
Visit() method, too. So there's really no way you could forget to add logic for printing the new expression type. Last, when you want to implement another operation working on expressions, you won't have to repeat any code that the compiler doesn't prompt you to, anyway. With a reasonable IDE, this is actually no work because it'll generate stub methods for you. As an additional benefit, the logic for printing a number, printing a function and printing an addition is now clearly and cleanly separated. You also can easily write separate tests for each.
Note that there is no point in trying to refactor the
Accept() method into a common base class - doing so would take away the ability to know the concrete type from the compiler.
A common variation is to create a class deriving from IExpressionVisitor and implement all Visit() overloads with an empty body. The drawback here is that you loose the luxury of having the compiler tell you when you forget to treat a specific implementation of IExpression in any of your visitors. Also note that whenever you add new implementation of IExpression, you need to adapt IExpressionVisitor and all its implementors. In other words, a precondition for using the visitor pattern is that you know that your class hierarchy won't change much or at all after a certain time of stabilizing.
Situations where you cannot use the visitor pattern
There are several situations where you just cannot use the visitor pattern, however much you would want to:
- The most simplistic problem is if some of the types you want to operate on are not under your control, i.e., you cannot add the
Accept() method to them and cannot add a common interface to their interface list. Imagine for example that your code for printing does something really fancy, and at some point you realize you'd like to re-use that functionality for regular ints or floats. It's a cheesy example, and you obviously could extract the fancy functionality into some other class, but you get the point. It could be also that you want your operational code to work on several types from a third-party library and that library did not implement the visitor pattern.
- Another scenario is if new visitables and new visitors should be added at runtime, eg, being loaded from plug-ins. You could not allow a plug-in author to add a new implementation of
IExpression, say, Subtraction, and provide the code for printing it if you chose to use the visitor pattern. This is probably the most common situation where you just cannot use the visitor pattern despite its significant benefits.
- The third problematic scenario is if you'd like your visitor to visit combinations of visitables. Imagine for example an application for converting many file formats into many others. You'd probably have an interface
IImporter with plenty of implementors and another one IExporter with again a bunch of implementors. For many pairs of import and export formats you want to do exactly the same, but there are a few special cases of specific combinations where you need to perform some extra steps. Now you'd probably want to avoid introducing a bowl of if-else-spaghetti and use a visitor, but again you can't.
Using dynamic method dispatching instead of a visitor pattern
In all three scenarios mentioned, it would be nice to find a solution that gives at least some of the benefits of the visitor pattern. The four main benefits were:
- Avoiding the complexity of many conditionals for dispatching to the concrete type.
- Clean separation of treating individual concrete types.
- No duplication of dispatching code.
- Forgetting to implement an operation for a specific concrete type is caught at compile-time instead of run-time.
The solution I'm going to present gives you three of these four benefits. Only the compile-time checks are lost. At the heart of
DynamicActionDispatcher is the idea to shift responsibilities: instead of requiring the types we want to be visitable to implement an interface in order to facilitate type dispatch, we create a class which is solely responsible for dispatching without any specific requirements on the visitable types. This class handles registration for being visitable as well as actually visiting. Ideally, we would want to write something like that:
public class Dispatcher
{
readonly Dictionary<typeof(T), Action<T>> mRegistry=
new Dictionary<typeof(T), Action<T>>();
public void Register<T>(Action <T> action)
{
mRegistry[typeof(T)]= action;
}
public void Visit<T>(T visitable)
{
Action<T> action= mRegistry[typeof(T)];
action(visitable);
}
}But, alas, the construct
typeof(T) is not legal in such a context as the declaration of
mRegistry. The compiler expects the type parameters for generics to be deductible at compile-time which here it clearly is not. So how can we work around this? First, we get rid of the construct which would offend the compiler and change it to something completely untyped:
readonly Dictionary<object, object> mRegistry =
new Dictionary<object, object>();We will still use the type of objects as keys in this registry, and a delegate as value:
delegate void UnaryDynamicMethod(object visitable);
Now we can write our
Visit() and
Register() methods like this:
public void Register<T>(Action<T> action)
{
mRegistry[typeof(T)]= (UnaryDynamicMethod)action;
}
public void Visit(object visitable)
{
UnaryDynamicMethod visitorMethod =
mRegistry[visitable.GetType()] as UnaryDynamicMethod;
visitorMethod(visitable);
}Unfortunately, the cast of
action to
UnaryDynamicMethod in
Register() is not legal. If on the other hand we replaced the parameter type
Action<T> with
UnaryDynamicMethod, we'd loose all type-safety in the visitor methods which is unacceptable, beside and even worse, we would have no way of determining the type for which to register the method. So we want to be able to pass a strongly typed method, but save the weakly typed
UnaryDynamicMethod. Somehow we still need to call the originally passed strongly typed method, too. So, ideally we want to create a method with
UnaryDynamicMethod's signature which in its body just calls the strongly typed method. One of the nice things of the .NET framework is that this is actually possible.
We want to create a method at run-time, but to save us emitting more intermediate language (IL) code instructions than necessary, we will put the actual hard work into a regular method which we then will call from our dynamically created method:
readonly Dictionary<object, Delegate> mDelegates =
new Dictionary<object, Delegate>();
void Handle<T>(object visitable)
{
Action<T> action = (Action<T>) mDelegates[typeof (T)];
action.Invoke((T) visitable);
}This method gets the visitable passed as an object, but is already strongly typed via the type parameter
T. It gets a delegate mapped to the type of visitable from another dictionary we introduced, downcasts the weakly typed
Delegate type down to an
Action of the appropriate type and invokes this action.
Now, let's move to the Register() method. First of all we need to be able to get the parameter type of the passed visitor method; we will later need it inside an array, so let's create one right away:
public void Register<T>(Action<T>action)
{
ParameterInfo[] parameterInfo = action.Method.GetParameters();
Type[] originalParameterTypes = new Type[1];
originalParameterTypes[0] = parameterInfo[0].ParameterType;Note that we get the actual type via reflection. This is because reflection is handled at run-time when there is already a concrete type bound to
T. Next, save
action for later retrieval in
Handle():
mDelegates[originalParameterTypes[0]] = action;
Next, construct a
DynamicMethod instance:
Type[] dynamicParameterTypes= new Type[2];
dynamicParameterTypes[0]= this.GetType();
dynamicParameterTypes[1]= typeof(object);
DynamicMethod method = new DynamicMethod(string.Empty, typeof(void),
dynamicParameterTypes, this.GetType());
The first parameter to
DynamicMethod's constructor is the desired name for the method about which we don't care. The second parameter specifies the return type which needs to be <void>in our case. The third specifies the parameters the method will be passed. We need two, the type of the object upon which the method will be invoked and
typeof(object) for the actual visitable. The first is needed because we are an instance method and we also will call another instance method,
Handle(). IL works analogous to Python in that regard, i.e., the instance an instance method is invoked upon is passed as the first parameter. The last parameters specifies the type of the class to which the method is to be bound, in our case our own class. Now let's generate the IL code that will fill the body of our dynamically generated method:
ILGenerator generator = method.GetILGenerator();
generator.Emit(OpCodes.Ldarg, 0);
generator.Emit(OpCodes.Ldarg, 1);
MethodInfo handleMethod = GetType().GetMethod("Handle",
BindingFlags.Instance | BindingFlags.NonPublic);
handleMethod = handleMethod.MakeGenericMethod(originalParameterTypes);
generator.EmitCall(OpCodes.Call, handleMethod, null);
generator.Emit(OpCodes.Ret);
The two
Ldarg opcodes push the passed arguments onto the stack so that the method we will call can retrieve them. The next two lines create a method description which we need for the call opcode. Basically, we get a description for our
Handle(), specifying that it's an instance method and that it's not public. As that method is generic, we need to translate the description into a generic method description. This involves binding the generic type argument
T to the actually used type. Next we just emit the opcode for actually calling our
Handle() method and another one for exiting our dynamically generated function. The last step is to map our dynamically generated method to the type argument of
Action<T>:
mRegistry[originalParameterTypes[0]] =
method.CreateDelegate(typeof (UnaryDynamicMethod), this);
}We store the method as a delegate as to be able to invoke it in our
Visit() method.
The actual DynamicActionDispatcher class
The actual
DynamicActionDispatcher class in the source code attached to this article uses the technique described above in a more flexible and complex way. The code above would not allow you to register more than one visitor for a specific type of visitable, nor would it allow you to register visitor for pairs of types. Also, it would generate the same dynamic method over and over again, even if it doesn't need to - which is bad because creating a dynamic method isn't excruciatingly slow, but not very fast, either.
DynamicActionDispatcher improves on all these problems. Let's walk through its public API:
-
public delegate void BinaryAction<FirstParameterType,
SecondParameterType>(FirstParameterType first,
SecondParameterType second);
defines an analogon to Action<T> for methods with two parameters.
-
public void AddAction<T>(Action<T> action)
registers an action to be executed on objects of type T.
-
public void AddBinaryAction<T, U>(BinaryAction<T, U> binaryAction)
registers an action with two parameters which can be of different type.
-
public void AddDelegate(Delegate action);
registers either a regular Action<T> or a BinaryAction<T, U>.
-
public void Visit(object input);
calls all registered actions for this type of object.
-
public void VisitBinary(object first, object second);
same as above, but for combinations of two objects.
-
public Action<object> OnUnaryTypeNotFound { get; set; }
attach to this delegate if you want to handle situations where Visit() is called with an object of a type for which there is no handler registered.
-
public BinaryAction<object, object> OnBinaryTypeNotFound { get; set; }
same as above, but for combinations of two objects.
Note also that the source code is accompanied with a quite complete suite of unit tests which provide good documentation of the API.
Some examples for using DynamicActionDispatcher
Let's first revisit the motivating example with expressions. It could be written now like this:
public interface IExpression
{
}
public class UnaryFunction : IExpression
{
readonly string mName;
readonly IExpression mArgument;
public UnaryFunctionNode(string name, IExpression argument)
{
mName= name;
mArgument= argument;
}
public string Name
{
get { return mName; }
}
public IExpression Argument
{
get { return mArgument; }
}
}
public class Addition : IExpression
{
readonly IExpression mLeftHandSide;
readonly IExpression mRightHandSide;
public Addition(IExpression lhs, IExpression rhs)
{
mLeftHandSide= lhs;
mRightHandSide= rhs;
}
public IExpression LeftHandSide
{
get { return mLeftHandSide; }
}
public IExpression RightHandSide
{
get { return mRightHandSide; }
}
}
public class Number : IExpression
{
readonly int mValue;
public Number(int value)
{
mValue= value;
}
public int Value
{
get { return mValue; }
}
}
public class ExpressionPrinter
{
public void PrintUnaryFunction(UnaryFunction function)
{
Console.Write(function.Name);
Console.Write('(');
function.Argument.Accept(this);
Console.Write(')');
}
public void PrintAddition(Addition addition)
{
addition.LeftHandSide.Accept(this);
Console.Write('+');
addition.RightHandSide.Accept(this);
}
public void PrintNumber(Number number)
{
Console.Write(number.Value);
}
}
ExpressionPrinter printer= new ExpressionPrinter()
DynamicActionDispatcher dispatcher= new DynamicActionDispatcher();
dispatcher.AddAction<Number>(printer.PrintNumber);
dispatcher.AddAction<UnaryFunction>(printer.PrintUnaryFunction);
dispatcher.AddActionvAddition>(printer.PrintAddition);Note that you need to specify the type argument explicitly as the compiler cannot deduce it at compile-time. Also, in contrast to the regular visitor implementation,
ExpressionPrinter could just as well be a static class with static methods. We now could also implement our example of the converter application relatively easily:
public interface IImporter
{
void Load(Stream stream);
}
public interface IExporter
{
void Save(Stream steam);
}
public class CSVImporter : IImporter
{ }
public class FixedLengthImporter : IImporter
{ }
public class XmlImporter : IImporter
{ }
public class CSVExporter : IExporter
{ }
public class FixedLengthExporter : IExporter
{ }
public class XmlExporter : IExporter
{ }
DynamicActionDispatcher dispatcher= new DynamicActionDispatcher();
dispatcher.AddBinaryAction<CSVImporter, XmlExporter>(handleCSV2Xml);
dispatcher.AddBinaryAction<XmlImporter, CSVExporter>(handleXml2CSV);
dispatcher.OnBinaryTypeNotFound+= delegate(object lhs, object rhs)
{
IImporter importer= (IImporter) lhs;
IExporter exporter= (IExporter) rhs;
};The very nature of
DynamicActionDispatcher makes it totally unproblematic to add new visitables and new operations to be executed on them at run-time - so allowing plug-ins to do the same is relatively easy.
Thanks
A big thanks go out to Peter Reiterer, a dear friend and colleague, who very much helped in ironing out some of the creases of my concept ;-)
History
- 2006-10-26: released initial version to CodeProject.
