State Machines in C# 3.0 using T4 Templates

UPDATE: The original code for this post, that used to be available via a link on this page, is no longer available. I’m afraid that if you want to try this one out, you’ll have to piece it together using the snippets contained in this post. Sorry for the inconvenience – blame it on ISP churn.


Some time back I wrote about techniques for implementing non-deterministic finite automata (NDFAs) using some of the new features of C# 3.0. Recently I’ve had a need to revisit that work to provide a client with a means to generate a bunch of really complex state machines in a lightweight, extensible and easily understood model. VS 2008 and C# 3.0 are pretty much the perfect platform for the job – they combine partial classes and methods, lambda functions and T4 templates making it a total walk in the park. This post will look at the prototype system I put together. This is a very code intensive post – sorry about that, but it’s late and apparently my eyes are very red, puffy and panda like.

State machines are the core of many applications – yet we often find people hand coding them with nested switch statements and grizzly mixtures of state control and business logic. It’s a nightmare scenario making code completely unmaintainable for anything but the most trivial applications.

The key objective for a dedicated application framework that manages a state machine is to provide a clean way to break out the code that manages the state machine from the code that implements the activities performed as part of the state machine. C# 3.0 has a nice solution for this – partial types and methods.

Partial types and methods

A partial type is a type whose definition is not confined to a single code module – it can have multiple modules. Some of those can be written by you, others can be written by a code generator. Here’s an example of a partial class definition:

public partial class MyPartialClass{}

By by declaring the class to be partial, you say that other files may contain parts of the class definition. the point of this kind of structure is that you might have piece of code that you want to write by hand, and others that you want to have driven from a code generator, stuff that gets overwritten every time the generator runs. If your code got erased every time you ran the generator, you’d get bored very quickly. You need a way to chop out the bits that don’t change. Typically, these will be framework or infrastructure stuff.

Partial classes can also have partial methods. Partial methods allow you to define a method signature in case someone wants to define it in another part of the partial class. This might seem pointless, but wait and see – it’s nice. Here’s how you declare a partial method:

// the code generated part public partial class MyPartialClass {
    partial void DoIt(int x);
}

You can then implement it in another file like so:

// the hand-written part partial class MyPartialClass {
    partial void DoIt(int x)
    {
        throw new NotImplementedException();
    }
}

This is all a little abstract, right now, so let’s see how we can use this to implement a state machine framework. First we need a way to define a state machine. I’m going to use a simple XML file for this:

<?xml version="1.0" encoding="utf-8" ?> <StateModels> <StateModel ID="My" start="defcon1"> <States> <State ID="defcon1" name="defcon1"/> <State ID="defcon2" name="defcon2"/> <State ID="defcon3" name="defcon3"/> </States> <Inputs> <Input ID="diplomaticIncident" name="diplomaticIncident"/> <Input ID="assassination" name="assassination"/> <Input ID="coup" name="coup"/> </Inputs> <Transitions> <Transition from="defcon1" to="defcon2" on="diplomaticIncident"/> <Transition from="defcon2" to="defcon3" on="assassination"/> <Transition from="defcon3" to="defcon1" on="coup"/> </Transitions> </StateModel> </StateModels>

Here we have a really simple state machine with three states (defcon1, defcon2 and defcon3) as well as three kinds of input (diplomaticIncident, assassination and coup). Please excuse the militarism – I just finished watching a season of 24, so I’m all hyped up. This simple model also defines three transitions. it creates a model like this:

Microsoft released the Text Template Transformation Toolkit (T4) system with Visual Studio 2008. This toolkit has been part of GAT and DSL tools in the past, but this is the first time that it has been available by default in VS. It allows an ASP.NET syntax for defining templates. Here’s a snippet from the T4 template that generates the state machine:

<#@ template language="C#" #>
<#@ assembly name="System.Xml.dll" #>
<#@ import namespace="System.Xml" #>

<#
    XmlDocument doc = new XmlDocument();
    doc.Load(@"TestHarness\model.xml");
    XmlElement xnModel = (XmlElement)doc.SelectSingleNode("/StateModels/StateModel");
    string ns = xnModel.GetAttribute("ID");
    XmlNodeList states = xnModel.SelectNodes("descendant::State");
    XmlNodeList inputs = xnModel.SelectNodes("descendant::Input");
    XmlNodeList trns = xnModel.SelectNodes("descendant::Transition");
    #>
using System;
using System.Collections.Generic;

namespace <#=ns#> {
public enum <#=ns#>States : int{
<#
string sep = "";
foreach(XmlElement s in states)
    {
    Write(sep + s.GetAttribute("ID"));
    WriteLine(@"// " + s.GetAttribute("name"));
    sep = ",";
    }

#>
} // end enum <#=ns#>States

public enum <#=ns#>Inputs : int{
<#
sep = "";
foreach(XmlElement s in inputs)
    {
    Write(sep + s.GetAttribute("ID"));
    WriteLine(@"// " + s.GetAttribute("name"));
    sep = ",";
    }

#>
} // end enum <#=ns#>States

public partial class <#=ns#>StateModel{

        public <#=ns#>StateModel()
        {
            SetupStates();
            SetupTransitions();
            SetStartState();
        }
...

Naturally, there’s a lot in the template, but we’ll get to that later. First we need a representation of a state. You’ll see from the template that an enum get’s generated called <#=ns#>States. Here’s what it looks like for the defcon model.

public enum MyStates : int {
defcon1// defcon1 ,defcon2// defcon2 ,defcon3// defcon3 } // end enum MyStates 

This is still a bit too bare for my liking. I can’t attach an event model to these states, so here’s a class that can carry around one of these values:

public class State {
    public int Identifier { get; set; }
public delegate void OnEntryEventHandler(object sender, OnEntryEventArgs e);
    // ...public event OnEntryEventHandler OnEntryEvent;
    // ...}

There’s a lot left out of this, but the point is that as well as storing an identifier for a state, it has events for both entry into and exit from the state. This can be used by the event framework of the state machine to provide hooks for your custom state transition and entry code. The same model is used for transitions:

public class StateTransition {
    public State FromState { get; set; }
    public State ToState { get; set; }
public event OnStateTransitioningEventHandler OnStateTransitioningEvent;
public event OnStateTransitionedEventHandler OnStateTransitionedEvent;
}

Here’s the list of inputs that can trigger a transition between states:

public enum MyInputs : int {
diplomaticIncident// diplomaticIncident ,assassination// assassination ,coup// coup } // end enum MyStates

The template helps to define storage for the states and transitions of the model:

public static Dictionary<<#= ns#>States, State> states                = new Dictionary<<#= ns#>States, State>();
public static Dictionary<string, StateTransition> arcs                = new Dictionary<string, StateTransition>();
public State CurrentState { get; set; }

which for the model earlier, will yield the following:

public static Dictionary<MyStates, State> states = new Dictionary<MyStates, State>();
public static Dictionary<string, StateTransition> arcs = new Dictionary<string, StateTransition>();
public State CurrentState { get; set; }

Now we can create entries in these tables for the transitions in the model:

private void SetStartState()
{
    CurrentState = states[<#= ns#>States.<#=xnModel.GetAttribute("start")#>];
}

private void SetupStates()
{
<#
foreach(XmlElement s in states)
    {
    WriteLine("states[" + ns + "States."+s.GetAttribute("ID")+"] =               new State { Identifier = (int)"+ns+"States."+s.GetAttribute("ID")+" };");
    WriteLine("states[" + ns + "States."+s.GetAttribute("ID")+"].OnEntryEvent               += (x, y) => OnEnter_"+s.GetAttribute("ID")+"();");
    WriteLine("states[" + ns + "States."+s.GetAttribute("ID")+"].OnExitEvent               += (x, y) => OnLeave_"+s.GetAttribute("ID")+"(); ;");
    }
#>
}
private void SetupTransitions()
{
<#
foreach(XmlElement s in trns)
    {
    #>
    arcs["<#=s.GetAttribute("from")#>_<#=s.GetAttribute("on")#>"] = new StateTransition
    {
        FromState = states[<#= ns#>States.<#=s.GetAttribute("from")#>],
        ToState = states[<#= ns#>States.<#=s.GetAttribute("to")#>]
    };
    arcs["<#=s.GetAttribute("from")#>_<#=s.GetAttribute("on")#>"].OnStateTransitioningEvent              += (x,y)=>MovingFrom_<#=s.GetAttribute("from")#>_To_<#=s.GetAttribute("to")#>;
    arcs["<#=s.GetAttribute("from")#>_<#=s.GetAttribute("on")#>"].OnStateTransitionedEvent              += (x,y)=>MovedFrom_<#=s.GetAttribute("from")#>_To_<#=s.GetAttribute("to")#>;
    <#
    }
    #>
}

which is where the fun starts. First notice that we create a new state for each state in the model and attach a lambda to the entry and exit events of each state. For our model that would look like this:

private void SetupStates()
{
    states[MyStates.defcon1] = new State {Identifier = (int) MyStates.defcon1};
    states[MyStates.defcon1].OnEntryEvent += (x, y) => OnEnter_defcon1();
    states[MyStates.defcon1].OnExitEvent += (x, y) => OnLeave_defcon1();

    states[MyStates.defcon2] = new State {Identifier = (int) MyStates.defcon2};
    states[MyStates.defcon2].OnEntryEvent += (x, y) => OnEnter_defcon2();
    states[MyStates.defcon2].OnExitEvent += (x, y) => OnLeave_defcon2();

    states[MyStates.defcon3] = new State {Identifier = (int) MyStates.defcon3};
    states[MyStates.defcon3].OnEntryEvent += (x, y) => OnEnter_defcon3();
    states[MyStates.defcon3].OnExitEvent += (x, y) => OnLeave_defcon3();
}

For the Transitions the same sort of code gets generated, except that we have some simple work to generate a string key for a specific <state, input> pair. Here’s what comes out:

private void SetupTransitions()
{
    arcs["defcon1_diplomaticIncident"] = new StateTransition {
                 FromState = states[MyStates.defcon1],
                 ToState = states[MyStates.defcon2]
             };
    arcs["defcon1_diplomaticIncident"].OnStateTransitioningEvent                  += (x, y) => MovingFrom_defcon1_To_defcon2;
    arcs["defcon1_diplomaticIncident"].OnStateTransitionedEvent                 += (x, y) => MovedFrom_defcon1_To_defcon2;
    arcs["defcon2_assassination"] = new StateTransition {
                 FromState = states[MyStates.defcon2],
                 ToState = states[MyStates.defcon3]
            };
    arcs["defcon2_assassination"].OnStateTransitioningEvent                += (x, y) => MovingFrom_defcon2_To_defcon3;
    arcs["defcon2_assassination"].OnStateTransitionedEvent                += (x, y) => MovedFrom_defcon2_To_defcon3;
    arcs["defcon3_coup"] = new StateTransition {
                 FromState = states[MyStates.defcon3],
                 ToState = states[MyStates.defcon1]
           };
    arcs["defcon3_coup"].OnStateTransitioningEvent                += (x, y) => MovingFrom_defcon3_To_defcon1;
    arcs["defcon3_coup"].OnStateTransitionedEvent                += (x, y) => MovedFrom_defcon3_To_defcon1;
}

You can see that for each state and transition event I’m adding lambdas that invoke methods that are also being code generated. these are the partial methods described earlier. Here’s the generator:

foreach(XmlElement s in states)
    {
    WriteLine("partial void OnLeave_"+s.GetAttribute("ID")+"();");
    WriteLine("partial void OnEnter_"+s.GetAttribute("ID")+"();");
    }
foreach(XmlElement s in trns)
    {
    WriteLine("partial void MovingFrom_"+s.GetAttribute("from")+"_To_"+s.GetAttribute("to")+"();");
    WriteLine("partial void MovedFrom_"+s.GetAttribute("from")+"_To_"+s.GetAttribute("to")+"();");
    }

Which gives us:

partial void OnLeave_defcon1();
partial void OnEnter_defcon1();
partial void OnLeave_defcon2();
partial void OnEnter_defcon2();
partial void OnLeave_defcon3();
partial void OnEnter_defcon3();
partial void MovingFrom_defcon1_To_defcon2();
partial void MovedFrom_defcon1_To_defcon2();
partial void MovingFrom_defcon2_To_defcon3();
partial void MovedFrom_defcon2_To_defcon3();
partial void MovingFrom_defcon3_To_defcon1();
partial void MovedFrom_defcon3_To_defcon1();

The C# 3.0 spec states that if you don’t choose to implement one of these partial methods then the effect is similar to attaching a ConditionalAttribute to it – it gets taken out and no trace is left of it ever having been declared. That’s nice, because for some state models you may not want to do anything other than make the transition.

We now have a working state machine with masses of extensibility points that we can use as we see fit. Say we decided to implement a few of these methods like so:

public partial class MyStateModel {
    partial void OnEnter_defcon1()
    {
        Debug.WriteLine("Going Into defcon1.");
    }
    partial void OnEnter_defcon2()
    {
        Debug.WriteLine("Going Into defcon2.");
    }
    partial void OnEnter_defcon3()
    {
        Debug.WriteLine("Going Into defcon3.");
    }
}

Here’s how you’d invoke it:

MyStateModel dfa = new MyStateModel();
dfa.ProcessInput((int) MyInputs.diplomaticIncident);
dfa.ProcessInput((int) MyInputs.assassination);
dfa.ProcessInput((int) MyInputs.coup);

And here’s what you’d get:

Going Into defcon2.
Going Into defcon3.
Going Into defcon1.

There’s a lot you can do to improve the model I’ve presented (like passing context info into the event handlers, and allowing some of the event handlers to veto state transitions). But I hope that it shows how the partials support in conjunction with T4 templates makes light work of this perennial problem. This could easily save you from writing thousands of lines of tedious and error prone boiler plate code. That for me is a complete no-brainer.

What I like about this model is the ease with which I was able to get code generation. I just added a file with extension ‘.tt’ to VS 2008 and it immediately started generating C# from it. All I needed to do at that point was load up my XML file and feed it into the template. I like the fact that the system is lightweight. There is not a mass of framework that takes over the state management, it’s infinitely extensible, and it allows a very quick turnaround time on state model changes.

What do you think? How would you tackle this problem?

About these ads

21 comments

  1. I think the T4 templates are interesting, similar outcomes could be achieved with Code DOM, but it is nice that this can be keep in separate non-code file and can be included in the build process.

    That said, do you think your technique would scale well for having more complex transition conditions and state operations? One simple test would be to write a simple tokenizer using your tool.

  2. Hi Chris,
    Yes, you could get a similar outcome using CodeDOM, but the effort required to maintain the code for the generator would be enormous in comparison to the templates shown here.

    This framework is not designed for simple state machines – but only time will tell if it will scale up to larger models. But one things for sure – if your state model is complex, then no matter how you try to write it, the application code to support it will always be complex. If you can use a system like this to automate the generation of the fragile parts that are most subject to change (& combinatorial explosion), then you will save yourself a lot of pain.

    Having a code generator also makes it easy to roll out extensions to the code easily. For example – error transitions are something that can be automatically built into the framework, but which must be constantly maintained as the state model changes.

  3. Why not just have a bit of code that utilises
    the xml as a bit of data, and says yes or no
    for the transition based on start and end
    states?

  4. Andrew — thanks for the terrific article — T4 templates are a cool technology, and you provided an innovative use of them!

    I do have a question, though. How do you cause a T4 template to generate its output file upon the VS 2008 solution (.sln) file being built?

  5. I found the best approach to this from a blog by Oleg Sych.

    The bottom line — use the code generator at design time, but check-in the generated source always. Oleg points out that the code generation tool could change, and you don’t want that to affect reproducing a possible production problem.

    For what it’s worth, I discovered the answer to my original question – how to get VS 2008 to run a template when building (although now I don’t plan to use it as my final solution, per Oleg’s advice).

    Here’s how to do it:

    1. View the properties of the project file (.csproj).

    2. Add a pre-build step as follows (for a template called foo.tt):
    “C:\Program Files\Common Files\Microsoft Shared\TextTemplating\1.2\TextTransform” -out $(ProjectDir)\foo.cs -I $(ProjectDir) $(ProjectDir)\foo.tt

    3. Save and build.

    Good luck,
    -Mike

  6. Hi Mike,

    thanks.

    Do you mean – is there a mechanism to have pre-build steps on the solution file itself?

    I doubt it ;^}

    The only way I could imagine you building a solution that was dynamically generated would be to invoke T4 using the command line tool. Invoke it through the command line tool to generate the SLN file, then use MSBUILD to build the SLN file. I doubt that you could get VS 2008 to reload the SLN file mid-way through the build process.

    Andrew

  7. Regarding having VS 2008 invoking a text template build:

    Originally I was planning to check in to source control not the generated .cs files, but instead just the .tt files used to generate them, and was looking for a way to make VS 2008 cause as a pre-build step to generate them, much like when using COM and CORBA you run an IDL compiler first to generate the stubs.

    But Oleg recommended it is safer to just check in both the .tt and the generated .cs files, to ensure reproducibility of each build.

    My previous posting on this topic showed a technique to invoke the .tt-to-.cs pre-build step. If in Andrew’s example in the article above, you deleted statemodel.cs, and immediately tried to build the solution file, it would fail, claiming it could not find statemodel.cs. The pre-build step I described, changing foo.tt and foo.cs to statemodel.tt and statemodel.cs, respectively, would cause statemodel.cs to be generated before, resulting in a successful build.

    -Mike

  8. Hi Andrew,

    I am a student at San Jose State University and am working on Finite Automata.
    I am totally new to automata concept.
    Can you please send me a code in C or C++ that shows how to convert a regular expression into automata?

    Thanks,
    Varun

  9. Varun, If you’re totally new to the DFA concept, then I suggest that you complete your own assignments rather than asking others to do them for you. That way, you’ll begin to understand…

  10. Hi, thank you for an awesome article. I’m trying to implement something similar to what you did in one of my own projects, but but I’m running into a problem with loading the template. The XmlDocument.Load function always looks in the Visual Studio install directory instead of the solution path. How did you set it up to work correctly? Your project doesn’t have these problems or use full paths.

  11. Sorry, never mind – turns out I just needed to delete user files of my project for some reason. Thanks a lot for this article, it was a great help.

  12. Hey! This is a great article in two ways:

    1. I’d never heard of the whole T4 stuff before, and it seems awesome for codegen’ing stuff. I’m checking it out now a little more in-depth.

    2. The visiting of FSM type stuff with an XML table that auto-parses the acutal code too?! Holy cow, that’s glorious.

    But I’m having the same issue as above, with the “…but but I’m running into a problem with loading the template. The XmlDocument.Load function always looks in the Visual Studio install directory instead of the solution path. How did you set it up to work correctly?” part.

    How DO you set it to load from the app directory?

Comments are closed.