Introduction
Visual Studio has a facility for editing Directed Graph Markup Language (DGML) graphically to create a directed flow diagram. After creating such a diagram for a state machine that I needed to implement, it seemed advantageous to use the diagram, directly as an assembly resource to run the state machine. I have appreciated the flexibility that the classes below has given my projects. With more time, a compiler tool could be written to compare the diagram with the code and provide sanity errors or warnings.
An Example State Machine
Here is a visual example of a DGML state machine design, followed by a simplified version of the .dgml file.
="1.0" ="utf-8"
<DirectedGraph xmlns="http://schemas.microsoft.com/vs/2009/dgml">
<Nodes>
<Node Id="Aborting" />
<Node Id="AutoUpdating" />
<Node Id="End" NodeRadius="50" />
<Node Id="EnteringPasscode" />
<Node Id="IssuingTravelToken" />
<Node Id="Restarting" />
<Node Id="RetrievingAuthorities" />
<Node Id="Start" NodeRadius="50" />
<Node Id="StartingSiteManager" />
<Node Id="ValidatingAuthorities" />
<Node Id="ValidatingSigOnFile" />
<Node Id="ValidatingTravelToken" />
<Node Id="VerifyingPasscode" />
</Nodes>
<Links>
<Link Source="Aborting" Target="End" Label="Exit" />
<Link Source="AutoUpdating" Target="Aborting" Label="SigOrUpdateFailed" />
<Link Source="AutoUpdating" Target="IssuingTravelToken" Label="SWUpdatesNotRequired" />
<Link Source="AutoUpdating" Target="Restarting" Label="SWUpdatesApplied" />
<Link Source="EnteringPasscode" Target="Aborting" Label="PasscodeEntryCanceled" />
<Link Source="EnteringPasscode" Target="VerifyingPasscode" Label="PasscodeSubmitted" />
<Link Source="IssuingTravelToken" Target="StartingSiteManager" Label="TravelTokenIssued" />
<Link Source="Restarting" Target="End" Label="Restart" />
<Link Source="RetrievingAuthorities" Target="ValidatingAuthorities" Label="AuthoritiesRetrieved" />
<Link Source="RetrievingAuthorities" Target="ValidatingTravelToken" Label="AuthoritiesRetrievalFailed" />
<Link Source="Start" Target="RetrievingAuthorities" Label="Start" />
<Link Source="StartingSiteManager" Target="End" Label="Continue" />
<Link Source="ValidatingAuthorities" Target="Aborting" Index="2147483647" Label="AuthoritiesValidationFailed" />
<Link Source="ValidatingAuthorities" Target="ValidatingSigOnFile" Label="AuthoritiesValidated" />
<Link Source="ValidatingSigOnFile" Target="AutoUpdating" Label="SigOnFileValidationFailed" />
<Link Source="ValidatingSigOnFile" Target="EnteringPasscode" Label="SigOnFileValidated" />
<Link Source="ValidatingTravelToken" Target="Aborting" Label="TravelTokenExpired" />
<Link Source="ValidatingTravelToken" Target="StartingSiteManager" Label="TravelTokenApproved" />
<Link Source="VerifyingPasscode" Target="AutoUpdating" Label="PasscodeVerified" />
<Link Source="VerifyingPasscode" Target="EnteringPasscode" Label="PasscodeNotVerified" />
</Links>
<Properties>
<Property Id="GraphDirection" DataType="Microsoft.VisualStudio.Diagrams.Layout.LayoutOrientation" />
<Property Id="Label" Label="Label" Description="Displayable label of an Annotatable object" DataType="System.String" />
<Property Id="Layout" DataType="System.String" />
<Property Id="NodeRadius" Label="Node Radius" Description="Node Radius" DataType="System.Double" />
</Properties>
</DirectedGraph>
As a visual indicator for the start and end states, I manually added the attribute NodeRadious="50". This graphically rounds the corners of these states.
Link nodes are represented by lines between states in the graph and are used as triggers for the state machine.
In your application derive an instance class from the abstract StateMachine class and begin coding the transitions.
public partial class EntryStateMachine : StateMachine
{
private Entry _EntryWindow;
public EntryStateMachine(Entry _ew) : base(_ew.GetType().Name)
{
_EntryWindow = _ew;
}
protected void OnStartExit()
{
_EntryWindow.Dispatcher.BeginInvoke((Action)(() =>
{
_EntryWindow._Progress.Maximum = 2 + this.Count() / 2;
_EntryWindow._Progress.Value = 1;
_EntryWindow._Instruction.Text = "Please wait,... AutoUpdate cleanup in progress.";
}));
}
}
In your derived class create protected void methods for any of the Exit, Trigger, or Entry boundaries of your DGML. Note the naming convention of "On"+state.name+"Exit"|"Entry" as well as "On"+trigger.name+"Trigger" (more on this later). When you want to begin executing your state machine, such as after the MainWindow has been loaded, call the constructor and submit the initial "Start" trigger.
void MainWindow_Loaded(object sender, RoutedEventArgs e)
{
_EntrySM = new EntryStateMachine(this);
_EntrySM.ProcessTrigger("Start");
}
Note that the state machine is running on a thread separate from the UI, so all UI interaction must be bracketed through the BeginInvoke() method of a window element. A nice feature of C# is that the code for the BeginInvoke() can be written in-line. Above I am setting the initial state of the progress bar and instruction text.
Also note that the state machine must be explicitly started with an initial call to ProcessTrigger(). There might also be times, such as waiting for user input, that the state machine will be paused and need to be nudged back into processing through such a call to ProcessTrigger().
The StateMachine Base Class
Let's walk through highlights of the state machine class. You can download the full source of the class HERE.
Set up an exception for a bad state transition that might need to be thrown.
[Serializable()]
public class InvalidStateTransitionException : System.Exception
{
public InvalidStateTransitionException() : base() { }
public InvalidStateTransitionException(string message) : base(message) { }
public InvalidStateTransitionException(string message, System.Exception inner) : base(message, inner) { }
protected InvalidStateTransitionException(System.Runtime.Serialization.SerializationInfo info,
System.Runtime.Serialization.StreamingContext context) { }
}
Setup the association class to track triggers, sources and destinations.
public struct StateAssociation
{
public string trigger;
public string source;
public string target;
public StateAssociation(string _trigger, string _source, string _target)
{
trigger = _trigger;
source = _source;
target = _target;
}
}
Setup the thread action class to be used from a sequential queue. Each instance holds a single executable reflection from a state transition.
public class StateAction
{
public MethodInfo mi;
public Object[] parms;
public StateAction(MethodInfo _mi, Object[] _parms)
{
mi = _mi;
parms = _parms;
}
}
Declare the abstract partial class and member variables and constructor for the StateMachine class.
public abstract partial class StateMachine
{
private List<StateAssociation> _Associations;
private ConcurrentQueue<string> _Triggers;
private BlockingCollection<StateAction> _Actions;
private ManualResetEvent _ActionRequired;
public volatile string _CurrentState;
public volatile string _LastTrigger;
public StateMachine(string _StateMachineResource)
{
_Associations = new List<StateAssociation>();
_Triggers = new ConcurrentQueue<string>();
_Actions = new BlockingCollection<StateAction>();
_ActionRequired = new ManualResetEvent(false);
XmlDocument xDoc = new XmlDocument();
xDoc.Load(GetType().Assembly.GetManifestResourceStream("CONTROL." + _StateMachineResource + ".dgml"));
foreach (XmlNode n in xDoc.DocumentElement.GetElementsByTagName("Link"))
{
_Associations.Add(new StateAssociation(n.Attributes["Label"].Value , n.Attributes["Source"].Value , n.Attributes["Target"].Value ));
}
_CurrentState = "Start";
Task.Run(() => ActionThread());
}
I have the constructor load the .dgml file from the assembly's resources. As an additional convenience, I name the .dgml file and the controlling window the same root name. This way they are grouped together in Visual Studio's Solution Explorer. The namespace argument "CONTROL" would be replaced by your application's namespace; you could pass this in or you could change the constructor to take an XmlDocument for the .dgml directly.
Only the Link nodes of the .dgml need to be harvested with the Label attribute being interpreted as the trigger of the association between the source and the destination states. The _CurrentState is then set to "Start" and the background thread started.
Note that the .dgml must have an initial state named "Start", serving its named function.
public int Count() { return _Associations.Count; }
public virtual void ProcessTrigger(string _trigger)
{
_Triggers.Enqueue(_trigger);
_ActionRequired.Set();
}
private void UpdateState(string _state, string _trigger)
{
_CurrentState = _state;
_LastTrigger = _trigger;
if (String.Equals(_state, "End", StringComparison.OrdinalIgnoreCase))
_Actions.CompleteAdding();
}
Count() is provided as a convenience function which can be used to gauge complexity or estimate the upper bound of a progress bar. ProcessTriger() is exposed so that the state machine can be manipulated externally. _Triggers is a thread safe, reentrant queue, forcing triggers to be fully processed in order. It is supported for an external entity to impose a trigger asynchronously. This Enqueue() gate channels all transition requests into a serial queue without interrupting the state machine's processing thread. Each trigger is fully processed by the state machine before the next trigger in the queue is released for processing.
_ActionRequired is a synchronizing event, used here to wake up the state machine's processing thread if needed.
The private, non-thread safe, UpdateState() method is used internally by the _Action queue to demarcate and coordinate the transitions of states (more on this later). The _Actions queue is used as a thread safe coordination mechanism. As a queue of actions it can be full or empty, but it also has a state as to whether it is expecting further additions to the queue or not. This is set here when the "End" state is transitioned to and no further actions are expected. This is how the state machine's background thread to know when to exit.
private void ActionThread()
{
while (!_Actions.IsCompleted)
{
StateAction a = null;
_ActionRequired.Reset();
while (_Actions.TryTake(out a))
{
if (a != null && a.mi != null)
{
a.mi.Invoke(this, a.parms);
}
}
ActionThread() is run in the background. The first statement checks whether the _Actions queue is empty AND if it no longer expects to receive additional actions. Since the thread currently has control (is awake), the sychronization event _ActionRequired is cleared. All waiting actions are then serially invoked, in the order in which they were submitted until the _Actions queue is emptied.
After the _Actions queue is emptied, the _Triggers queue is allowed to process a single waiting trigger. As triggers will enqueue actions, and actions will enqueue triggers the ActionThread() is designed to complete the processing of all enqueued actions before processing the next trigger. This keeps the state machine sane and deterministic.
string _trigger;
if (_Triggers.TryDequeue(out _trigger))
{
bool state_trigger_match_found = false;
foreach (StateAssociation sa in _Associations)
{
if (sa.source.CompareTo(_CurrentState) == 0 && sa.trigger.CompareTo(_trigger) == 0)
{
Extracting the next trigger (if any) I look through the _Associations to validate that the trigger has the _CurrentState as a related source for the transition.
MethodInfo mi = null;
mi = GetType().GetMethod("On" + sa.source + "Exit",
System.Reflection.BindingFlags.NonPublic |
System.Reflection.BindingFlags.Instance);
if (mi != null) _Actions.Add(new StateAction(mi,null));
If the transition is legitimate, I use C# Reflection to look for an "On"+state.name+"Exit" method in the assembly. If found I add this method to the _Actions queue. If not, I continue. The state machine does not require any particular state transition to implement an action. Note, the _CurrentState is not yet changed.
mi = GetType().GetMethod("On" + _trigger + "Trigger",
System.Reflection.BindingFlags.NonPublic |
System.Reflection.BindingFlags.Instance);
if (mi != null) _Actions.Add(new StateAction(mi, null));
Next I use C# Reflection to look for an "On"+trigger.name+"Trigger" method in the assembly. If found I add this method to the _Actions queue. If not, I continue. Note, the _CurrentState is not yet changed.
mi = GetType().BaseType.GetMethod("UpdateState"
, BindingFlags.NonPublic | BindingFlags.Instance
, Type.DefaultBinder
, new Type[] { typeof(string), typeof(string) }
, null );
if (mi != null)
_Actions.Add(new StateAction(mi, new Object[] { sa.target, _trigger.ToString() } ));
Now that all state exit actions have been queued, as well as all trigger actions, I enqueue the private UpdateState() method with the details of the trigger's state transition. This will allow all previous action fuctions to run ahead of the state transition from out of the _Actions queue. Note that the member variables for _CurrentState and _LastTrigger (or how the _CurrentState was entered) are accessible publically in case they are helpful to the action functions. The "Exit" actions and the "Trigger" actions operate ahead of the change of state, "Entry" actions subsequently operate after the change of state. Queuing the UpdateState() in this way ensures that the state change happens in an isolated way on the background thread.
mi = GetType().GetMethod("On" + sa.target + "Entry",
System.Reflection.BindingFlags.NonPublic |
System.Reflection.BindingFlags.Instance);
if (mi != null) _Actions.Add(new StateAction(mi, null));
state_trigger_match_found = true;
break;
}
}
if (!state_trigger_match_found)
throw new InvalidStateTransitionException("Transition for [" + _trigger + "] not found in current state (" + _CurrentState + ").");
}
Lastly, I use C# Reflection to look for an "On"+state.name+"Entry" method in the assembly. If found I add this method to the _Actions queue, which will not be called until after the state has been changed. If not, I continue. Before breaking from the search for trigger associations, I set a flag to indicate that a sane trigger was found and handled. If the search for triggers does not find a match, an exception is thrown.
else
{
if (!_Actions.IsAddingCompleted)
_ActionRequired.WaitOne();
}
}
}
In the case that there are no actions to run and no triggers to process, I put the state machine's background thread to sleep, waiting on an external call to ProcessTrigger() to wake up the thread.
Conclusion
The crux of this class is to enable one to design a state machine visually in DGML and execute it on a background thread using a simple naming convention in your derived state machine code of "On"+name+"Exit"|"Trigger"|"Entry" methods. With the base class handling the transitions, one can focus on the simpler task of implementation of each individual state transition.
Caveats
Though the Visual Studio DGML designer supports nesting of states within states, this code does not support the nesting of states.
It would be nice to have a lint type tool in Visual Studio that would compare the code in the assembly with the .dgml file. It could then produce warnings or errors when
- there is no "Start" state in the .dgml.
- there existed nesting in the .dgml file, which is currently unsupported by this state machine code.
- there existed an "On"+some.name+"Exit"|"Trigger"|"Entry" method that was not matched in the .dgml file, which could be a typo.
- a check of all
ProcessTrigger() calls could verify the existence of the trigger in the .dgml.
For now, these variances have to be checked manually.
