Last week or so there was a thread on the altnetconf message board that about a usage of the Visitor pattern for validating a hierarchy of objects. At work I'm using the Visitor pattern with some frequency in my financial projects to deal with heterogeneous collections of financial elements. Over and over again I'm seeing the Composite and Visitor patterns come up as good solutions to a certain range of problems, but these patterns are often a source of almost superstitious fear to those developers who aren't familiar with them. From past experience I know that developers don't necessarily grok these patterns at the first exposure. I avoided the Visitor for a long time because it's just plain weird looking. I changed my mind only after having some positive experiences with the pattern.
I've had a post on these patterns backlogged forever, so now seems like as good of time as any to try to help introduce these important patterns. All of the example code from this post is part of my StoryTeller OSS project and can be perused to your heart's content from the Subversion repository on Tigris.
Specifically, I'm going to talk about design patterns that are useful for processing heterogeneous lists and object hierarchies without resorting to an uncontrolled proliferation of "if/then" branches:
- The almost forgotten art of Double Dispatch
- Fear not the Visitor
- The Big, Bad Composite Pattern
I struggled quite a bit with the ordering of topics in this post because the patterns seem to be so closely interrelated in my mind. Double Dispatch stands alone, but the reason for doing it is largely to make the Visitor implementation work. I've used a Visitor pattern frequently at work the past couple months without a Composite, but most of the time the Visitor and Composite seem to be found together.
Before I get started...
<BoilerPlateDesignPatternDisclaimer>
Design Patterns are a very useful are of study for serious software designers. Design Patterns are an important form of common language between developers and a way to catalogue and reuse design wisdom from the ancients. Design Patterns can be a huge shortcut for designing applications or services. Overusing Design Patterns is bad. Using Design Patterns out of their proper context is usually bad. Committing to a Design Pattern too quickly can often be bad. Using Design Patterns at the right times can reduce the amount of ugly, bugridden "if/then" logic in code and make the code easier to test, change, and read. Don't just memorize pattern names. Climb up to the top of Bloom's Taxonomy.
</BoilerPlateDesignPatternDisclaimer>
Now that that's out of the way...
The Problem
My Domain Model in StoryTeller is largely made up of a series of classes that inherit from a common ILeaf interface and represent the concepts in Fit-style testing.
- Suite - a group of tests and/or child suites
- Test - contains a mix of Comment's and Tables, could contain a reference to a Fragment
- Comment
- Table - The actual test. A Table contains rows which contains cells.
- Fragment - a reusable piece of test logic. Think SetUp or TearDown. Can contain Comments and/or Tables
- Include - simply a reference to a Fragment
- SystemUnderTest - the configuration and list of Suites for an entire system. Effectively the equivalent to a "project" for StoryTeller.
In hierarchical form a SystemUnderTest and its children may look something like:
- SystemUnderTest: "StoryTeller UI"
- Suite: "Test Operations"
- Fragment: "SetUp"
- Fragment: "TearDown"
- Suite: "Add Test"
- Test: "Add Test Happy Path from Tree"
- Test: "Strip illegal characters from Test name"
- Table
- Comment
- Include/Fragment
- Table
- Table
- Suite: "Delete Test"
- Suite: "Tagging"
- Suite: "Test Execution"
Introducing the Composite and Visitor Patterns
From the original Gang of Four:
Compose objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly.
A composite object is simply an object that is composed of other objects. A SystemUnderTest object will contain one or more Suite objects. A Suite class from StoryTeller will contain other Suites and Test objects in an n-deep hierarchy. I have to do many different operations against an array or hierarchy of ILeaf objects. For example, starting from any particular ILeaf object I need to:
- Save each ILeaf, but all the different types of ILeaf classes are persisted a little bit differently
- When constructing the TreeView in the UI I need to create a TreeNode for each ILeaf object in the hierarchy, but I use a different subclass of TreeNode for each specific type of ILeaf
- Render each ILeaf into an HTML representation, but each ILeaf is rendered somewhat differently
- Find all the Tests that match a given criteria starting from anywhere in the hierarchy
- Execute all the Tests at any level of the hierarchy
- Find any particular ILeaf by the path or a unique identification
- Later on I'm planning on adding syntax checking and possibly refactoring that will have to scan the entire hierarchy
All of the different types of "node" have a consistent set of operations, so it makes sense to create a common interface for all of these "node" classes. Going farther, doing an operation on any given node usually means that I also need to perform that same operation on all the children of that node and the descendents. This is where the Composite Pattern comes into play. Implementing the Composite Pattern means that I need to treat the leaf and branch nodes of the hierarchy in a common manner.
To implement the Composite Pattern I've created the ILeaf interface below:
public interface ILeaf
{ IEnumerable<ILeaf> ChildLeaves { get; } ILeaf[] Children { get; } void AcceptVisitor(IVisitor visitor);
}
In StoryTeller I've chosen to implement almost all of the hierarchical operations in Visitor pattern classes, but as we'll see in a later section the Visitor approach wouldn't work without the Composite pattern implemented by the common ILeaf interface. If I hadn't decided to keep almost all infrastructure concerns out of the ILeaf nodes, I might have added an "Execute()" method on the ILeaf interface. If you had called Test.Execute() it would simply execute itself. If you called Suite.Execute() it would call Execute() on all of its children Suites and all of its Tests so that every Test that descended from that Suite would be executed.
Other Examples for the Composite Pattern
The average software developer probably uses the Composite pattern every single day in existing libraries and API's:
- The DHTML DOM in web browsers
- The Control hierarchy in WinForms. Many of the methods you call on a Control will propagate down into its children and its children's children.
- The FileSystem is composed of an n-deep hierarchy of folders and files. Deleting a folder also deletes all of its subfolders and all of the files that it contains.
- The Xml DOM is the canonical example. No matter where it is in the hierarchy, you basically treat each XmlNode as an XmlNode.
- In manufacturing systems an assembly of parts is often treated as just another part. I used to work for a computer manufacturer in Texas. With the advent of blade servers a server could be said to be composed of an array of blade servers which all had their own set of parts. If the manufacturing system had been built along OOP lines with the Composite pattern describing the constituent parts, sliding in support for a rack server composed of blade servers wouldn't have had to hurt too much. Alas, the manufacturing system was still written in spaghetti code COBOL and out came the "if/then" duct tape.
I can't say that I create new Composite pattern implementations from scratch on a regular basis, but it pops up often enough to warrant an inclusion in your design toolbox. I've used the Composite for:
- The StoryTeller domain model of Suites and Tests
- In StructureMap, I create an in memory hierarchy of the configuration model for the diagnostics. One instance has child instances which may have child instances which may have constructor arguments.
- In an insurance application we had a model of regions, customers, and policies that naturally fit a Composite model. I got a lot of push back from other developers on this project that weren't familiar with the Composite pattern because it seemed too "weird." I still think it was the simplest way to pull off the model with our requirements, but the unfamiliarity with the pattern was a real problem. I'm writing this post in no small part to have a published explanation for the Composite and Visitor for the next time I'm in this situation.
- Any number of custom filter "trees." I'd like to have a quarter for every time I've written an IFilter interface of some kind. Any time you do, there's almost inevitably a "NotFilter" and "OrFilter" and "AndFilter" that combine other IFilters to create more complex query behavior.
Double Dispatch
Before I introduce the Visitor pattern, I need to first demonstrate the ancient technique of Double Dispatch. To illustrate the concept, let's take a look at the Double Dispatch you've used your entire .Net career to do Xml serialization. Here's a sample snippet of code to Xml serialize an object to a file.
public void PersistToFile<T>(T target, string filename)
{ XmlSerializer serializer = new XmlSerializer(typeof (T));
using (FileStream stream = new FileStream(filename, FileMode.Create, FileAccess.Write))
{ serializer.Serialize(stream, target);
}
}
We create an XmlSerializer object for the Type of object that we're serializing. Then we create a FileStream object that we want the data written to, eventually landing in an Xml file. The last thing we do is to pass the FileStream object into the XmlSerializer. As the XmlSerializer works, it figures out the content to write and tells the FileStream to write this content. If the FileStream and XmlSerializer were people, their conversation might be summed up as:
FileStream: "Here I am, now you tell me what to do for you."
XmlSerializer: "Write <SomeClass>. Write <SomeProperty>SomeValue</SomeProperty>..."
So the two classes aren't great conversationalists, but the technique is a powerful slayer of if/then logic. Think about this for a minute. XmlSerializer, the binary serialization, and the newer JSON serializer's all have very different logic to determine the exact bytes or characters that represent an object, but the bytes produced are basically stored in the same way. When you serialize an object, however, the Stream object doesn't need to care what type of serialization is taking place. The specific serializer will tell the Stream what to write.
Here's a sample usage of Double Dispatch from StoryTeller. At various times in the code I need to take an ILeaf object and write out the HTML representation of it. Let's say I'm writing out a single Test to use as the HTML input to the FitnesseDotNet test engine. Any given Test will be composed of a mix of Comments, Tables, and Fragments. All three of these things will be rendered to HTML in a different way. In this case there's a finite number of tasks that need to take place to render a Test into HTML. I came up with a simple interface for all of these little HTML writing tasks:
public interface IHTMLBuilder
{ void StartTable();
void StartTable(Type type);
void AddComment(string commentText);
void AddRow();
void AddRow(params string[] contents);
void AddRow(string delimitedList);
void AddCell(string contents, int width);
string GetHTML();
void WriteTitle(string title);
void WriteTag(string tag);
void AddStyle(string style);
void StartInclude(string path);
void EndInclude();
void WriteBigTitle(string title);
void AddDivider();
void WriteStatus(Status status);
}
Next, we've got the issue of where to put the specific logic for rendering each type of ILeaf. HTML rendering in StoryTeller is so intrinsic that I decided to embed the HTML rendering into each ILeaf type that needs to be rendered. Let Table and Row and Column know how to render themselves. That decision led to the creation of one more interface shown below:
public interface IHTMLFragment
{ void WriteHTML(IHTMLBuilder htmlBuilder);
}
To render a Comment object I simply pass an IHTMLBuilder into the WriteHTML(IHTMLBuilder) method and let the Comment class tell the IHTMLBuilder what to do.
public void WriteHTML(IHTMLBuilder builder)
{ builder.AddComment(_contents);
}
The Table class is a little bit more complicated, but it's still the same concept. For the sake of completeness, I'm also showing the code in Row and Cell.
public void WriteHTML(IHTMLBuilder builder)
{ CalculateCellWidths();
builder.StartTable();
foreach (Row row in _rows)
{ row.WriteHTML(builder);
}
}
// Row.WriteHTML(IHTMLBuilder builder)
public void WriteHTML(IHTMLBuilder builder)
{ builder.AddRow();
foreach (Cell cell in _cells)
{ cell.WriteHTML(builder);
}
}
// Cell.WriteHTML(IHTMLBuilder builder)
public void WriteHTML(IHTMLBuilder htmlBuilder)
{ htmlBuilder.AddCell(_contents, this.Width);
}
In my first pass at this code the Test class could only contain Comments or Tables. In a later pass I added the ability to "include" fragments of tests into other tests. No worries though, I simply have yet another class called Include that also implements IHTMLFragment (oops, I just found a bug related to this in StoryTeller while writing this). When the Test is being rendered the HTMLWriter just iterates over all of the ILeaf children.
Okay, so each thing knows how to tell an IHTMLBuilder how to persist itself, but how does an IHTMLBuilder get around to each Table, Comment, and Fragment? That's where the other patterns come into play. We've used the Composite pattern already to standardize the navigation from an ILeaf to its children all the way down. Now we need to introduce the Visitor as a way of creating a logical action that starts working from any given ILeaf node.
Fear not the Visitor
From the Computer Science department of my alma mater:
The purpose of the Visitor Pattern is to encapsulate an operation that you want to perform on the elements of a data structure. In this way, you can change the operation being performed on a structure without the need of changing the classes of the elements that you are operating on. Using a Visitor pattern allows you to decouple the classes for the data structure and the algorithms used upon them.
As I said before, I need to perform a series of operations against all or part of an ILeaf hierarchy in StoryTeller. Some of these operations pertain to infrastructure or user interface concerns. I don't want these concerns embedded in my domain model, so its advantageous to implement these operations in other classes. Very often these operations will involve a mix of the different types of ILeaf objects. If I were to use straight up procedural programming, I'd be constantly writing the same set of if/then/switch statements all over the place every time I need new operations against a mix bag of ILeaf objects.
The Composite Pattern gives us a standard pattern for navigating the data structure. The next step is to be able to differentiate the proper action based on the type of ILeaf object that we're processing. Once again we're going to turn to Double Dispatch to help us out. We first define a new interface called IVisitor that exposes specific methods for processing each specific kind of ILeaf.
public interface IVisitor
{ void ProcessTest(Test test);
void ProcessTable(Table table);
void ProcessComment(Comment comment);
void ProcessSuite(Suite suite);
void ProcessInclude(Include include);
void ProcessFragment(Fragment fragment);
}
As we saw earlier, each ILeaf exposes methods to support both the Composite structure and a single method called AcceptVisitor(ILeaf) that enables the Visitor pattern.
public interface ILeaf
{ IEnumerable<ILeaf> ChildLeaves { get; } ILeaf[] Children { get; } void AcceptVisitor(IVisitor visitor);
}
When the AcceptVisitor(ILeaf) method is called on an ILeaf, the ILeaf simply turns right around and calls the proper method on the IVisitor and passes itself in as the argument. Here's the implementation of AcceptVisitor() for the Test class.
public override void AcceptVisitor(IVisitor visitor)
{ visitor.ProcessTest(this);
}
All the Test has done is simply told the incoming IVisitor that "I'm a Test, so do whatever it is you do with a Test."
So why is this advantageous over simply doing a switch statement on the type? I'd say it's advantageous because:
- We've eliminated the need to write the same switch statement over and over again as new operations are added to the system
- The code to split processing by the type of ILeaf is cleaner in my opinion because we've removed "noise" code by letting the Visitor pattern handle the conditional logic
- It provides a template for new operations to follow
- It provides an obvious entry point for unit testing against any particular kind of node in the hierarchy. A couple years ago I hit a point in StructureMap where the diagnostic code was an abominable mess. Unit testing was hard because there was a tight coupling between configuration code and the diagnostics. I largely cured the problem by refactoring the diagnostics to a Visitor pattern to the point where it was easy to skip the configuration setup in unit tests to go right to the smaller scenario that I wanted to unit test. Using the Visitor pattern ended up making the diagnostic code far easier to work with.
Creating TreeNodes with the Visitor
The StoryTeller UI has a TreeView on the left that shows a TreeNode for each ILeaf in the open SystemUnderTest.
I use a specific subclass of the WinForms TreeNode class for each type of ILeaf in order to expose specific actions and screen navigation. When I'm constructing the TreeNode hierarchy I logically need to iterate over each ILeaf's children and create the proper type of TreeNode for each ILeaf child. This construction of the TreeView really became very simple by using the IVisitor interface that already existed by this time. All of my TreeNode's extend the abstract LeafNode class shown in elided form below:
public abstract class LeafNode<T> : TreeNode, ILeafNode, IVisitor where T : ILeaf
{ private readonly T _screenSubject;
protected LeafNode(T subject)
{ _screenSubject = subject;
...
RefreshNodes();
}
public void RefreshNodes()
{ Nodes.Clear();
...
foreach (ILeaf child in ((ILeaf) _screenSubject).ChildLeaves)
{ child.AcceptVisitor(this);
}
}
public virtual void ProcessTest(Test test)
{
TestNode node = new TestNode(test);
Nodes.Add(node);
}
public virtual void ProcessSuite(Suite suite)
{ SuiteNode node = new SuiteNode(suite);
Nodes.Add(node);
}
When LeafNode's constructor is called it takes in an ILeaf as its "subject." The last step in its constructor is to call the RefreshNodes() method to create all of its child TreeNodes. If this were the SuiteNode, the steps in code would be:
- Take in a Suite object as an argument to the constructor
- In the RefreshNodes() method, iterate over each ILeaf child in the Suite (_screenSubject above)
- For each ILeaf child the SuiteNode will pass itself into the ILeaf.AcceptVisitor() method
- If the ILeaf child is a Test, the Test will immediately call the ProcessTest(Test) method on the SuiteNode object...
- ...which causes a new TestNode to be created for that Test and added to the Nodes collection of the SuiteNode
- If the ILeaf child is another Suite, that child Suite will immediately call the ProcessSuite(Suite) method on the SuiteNode object...
- ...which causes a new SuiteNode to be created for that child Suite -- which will in turn follow the same process to build its children before...
- ...the new child SuiteNode is added to the Nodes collection of the original SuiteNode...
It may not seem this way at first glance, but this strategy made the population of the TreeView very simple to implement and unit test.
Combining the Visitor and Composite
The StoryTeller version of the Visitor is relatively simple and I think fairly representative. I use a simple abstract class called Visitor as a common superclass. That class is shown below:
public abstract class Visitor : IVisitor
{ #region IVisitor Members
public abstract void ProcessTest(Test test);
public abstract void ProcessTable(Table table);
public abstract void ProcessComment(Comment comment);
public abstract void ProcessSuite(Suite suite);
public virtual void ProcessInclude(Include include){} public virtual void ProcessFragment(Fragment fragment){}
#endregion
public void VisitLeaf(ILeaf leaf)
{ // Hook method before processing an ILeaf
startLeaf(leaf);
// Another hook to filter ILeaf's before processing
if (isInterested(leaf))
{ leaf.AcceptVisitor(this);
}
// Now, visit each child of the original ILeaf
foreach (ILeaf child in leaf.ChildLeaves)
{ VisitLeaf(child);
}
// Hook method after processing an ILeaf and all
// of its children
endLeaf(leaf);
}
protected virtual void startLeaf(ILeaf leaf){}
protected virtual void endLeaf(ILeaf leaf){}
protected virtual bool isInterested(ILeaf leaf)
{ return true;
}
}
The mechanics for navigating the ILeaf hierarchy is completely implemented in the VisitLeaf(ILeaf) method. In its simplest form a Visitor implementation would simply call AcceptVisitor(this) on the leaf argument, then iterate over all of leaf's children to visit each of them in turn.
When doing a Visitor implementation I've often found it to be advantageous to provide "hook" methods before and/or after the processing of each node. These hooks are usually for bookkeeping or times when you can really perform the operation through the common interface of the nodes. One of the ways I use this in StoryTeller is in the HTML rendering of an ILeaf hierarchy. Several of the ILeaf types also implement the IHTMLFragment interface I introduced earlier to write themselves out in HTML. HTML rendering is done in a subclass of Visitor called HTMLWriter. In HTMLWriter I override the startLeaf() method to write out HTML for each ILeaf in a generic manner:
protected override void startLeaf(ILeaf leaf)
{ IHTMLFragment fragment = leaf as IHTMLFragment;
if (fragment != null)
{ fragment.WriteHTML(_builder);
}
}
Usually, however, the meat of the Visitor operation is happening in the ProcessXXXXXXXX() methods. In the HTMLWriter I have specific logic for handling a Suite or a Test in the IVisitor methods shown below:
private IHTMLBuilder _builder;
private ILeaf _leaf;
public HTMLWriter(ILeaf leaf, IHTMLBuilder builder)
{ _leaf = leaf;
_builder = builder;
}
public string GetHTML(bool withStyle)
{ addStyle(withStyle);
VisitLeaf(_leaf);
return _builder.GetHTML();
}
private void include(Fragment fragment)
{ ...
}
protected override void startLeaf(ILeaf leaf)
{ IHTMLFragment fragment = leaf as IHTMLFragment;
if (fragment != null)
{ fragment.WriteHTML(_builder);
}
}
public override void ProcessTest(Test test)
{ _builder.WriteTitle(test.Name);
_builder.WriteStatus(test.Status);
foreach (string tag in test.Tags)
{ _builder.WriteTag(tag);
}
}
...
public override void ProcessSuite(Suite suite)
{ _builder.WriteBigTitle("Suite " + suite.Name); foreach (string tag in suite.Tags)
{ _builder.WriteTag(tag);
}
_builder.AddDivider();
}
By making HTMLWriter a Visitor, I can take any given ILeaf and write it and all of its children into HTML. Because I can start the HTML rendering from any point in the hierarchy I've been able to reuse the same class for:
- Exporting an entire Suite of tests to HTML
- Exporting all of the tests in a SystemUnderTest to HTML
- Writing out a single Test prior to execution
- Rendering a Fragment into an HTML preview view
When I've needed to alter the way ILeaf objects are rendered to HTML it's been easy to find the write code to change. I simply have to find the appropriate ProcessXXXXXXX() method on HTMLWriter and make the changes there without having to be concerned about the code for rendering any other kind of ILeaf.
How does the Visitor Get Around?
I'm aware of three different ways to handle the navigation of the Visitor through a list or hierarchy.
- The Visitor itself is responsible for navigating the hierarchy. This is the approach I've used in StoryTeller's ILeaf hierarchy. Each ILeaf exposes a ChildLeaves property that standardizes the navigation from parent to children for all types of ILeaf. In this case my Visitor classes don't really need to know that much about the internals of the hierarchy and I didn't feel that it created an unacceptable coupling. I don't like this option if it means making the Visitor intimately aware of the internal structure of the hierarchy that it's visiting.
- Make each node in the hierarchy responsible for passing the Visitor down to its children. I use this approach when I don't want to expose the internal structure of the hierarchy to the Visitor. It's also a great way to make each node responsible for conditional propagation of the Visitor.
- Use a separate class as an iterator to walk the hierarchy and "push" the Visitor to each node in the hierarchy. I think this can simplify the Visitor classes by removing the need for inheritance relationships. It also makes the navigation of the hierarchy easier to maintain and test by isolating the navigation from the Visitor actions. The downside is potentially a little extra mechanical complexity in using the Visitor against a hierarchy because of the extra class.
Yield is your Friend
The new "yield" keyword is almost tailor made for creating Visitor/Composite pattern implementations. With the yield keyword I can structure my hierarchy in any way that's appropriate and still make the enumeration of the children seem simple to the outside callers. In my Suite class it's advantageous for me to keep the child Fragments, Tests, and child Suites in separate data structures. However, when the ChildLeaves property is requested for a Suite I want to iterate through all three collections. In .Net 1.1 I probably would have created some sort of temporary ArrayList or ILeaf[] array just to hold the returned value. In .Net 2.0 I can use the "yield" keyword to eliminate the unnecessary shuttling of data in temporary lists like this:
public override IEnumerable<ILeaf> ChildLeaves
{ get
{ foreach (KeyValuePair<string, Suite> pair in _childSuites)
{ yield return pair.Value;
}
foreach (KeyValuePair<string, Test> test in _tests)
{ yield return test.Value;
}
foreach (KeyValuePair<string, Fragment> pair in _fragments)
{ yield return pair.Value;
}
}
}
Yes, I know this is easier in Ruby!
The Ruby Visitor from ObjectMentor. Ruby guys love to use this example to poke fun at the compiler driven noise in static typed language like Java, C#, and VB.Net.
Summary
So was all of this worth it to me? Looking back I'd say the answer is an emphatic yes. I counted 20 implementations of the IVisitor interface in StoryTeller. I've been able to add new operations across the hierarchy with relative ease. I know I've got at least a couple more hierarchy operations yet to do in later phases and the Visitor/Composite pairing gives me a clean way to add these operations.
If you have a need to process an object hierarchy and/or a mixed list of objects, the Visitor and Composite patterns can do a lot for you to control the complexity of dealing with the data structure.
Other Reading
I did quite a bit of reading in the course of writing this post. In particular, I found these references helpful:
If you peruse these links you might notice that not one single one of the links uses .Net or even mentions .Net. Not really making a statement of any kind, just pointing that out.