About Jolt.NET Libraries

Inspired by the Boost C++ libraries, Jolt.NET aims to complement the .NET Base Class Library (BCL) with algorithms, data structures, and general productivity tools. It is the hope of the authors that the features of Jolt.NET will one day be part of, or represented in the BCL and the .NET Framework.

Finite State Machine Interface Overview

Merry Christmas all!

I've been working on flushing out the interface to the FiniteStateMachine (FSM) class and have reached a point of near-completion; you may review the source code at revision 17779. The current implementation will let one add states and transitions to an FSM, set/clear an FSM's final state(s), and set/clear an FSM's start state. State enumeration and input symbol acceptance are also supported, along with an implicit error state. For examples on how to accomplish these tasks, please review the Jolt FSM documentation.

The following diagram shows the public interface of the available classes and their methods (less constructors for brevity).



The methods that are missing from this interface are those to serialize/deserialize the FSM, and those that allow you to export the FSM to a QuickGraph data structure. The latter methods are important because they enable the former, and they also provide access to the transitions and states of the FSM (as edges and vertices, respectively). Having access to the graph also allows analysis via QuickGraph algorithms. Thus, the next work item I will take on will be in adding these missing methods, and also to address the serialization/deserialization issues I brought up in my previous post. Some of the work-items that are required for this task are to ensure that transition (edge) labels are created when converting the graph to GLEE, MSAGL, GraphViz, or GraphML, along with making sure a final state is appropriately tagged in the target format.

Draft Implementation of the Finite State Machine

Good day all!

Revision #17566 contains a somewhat usable implementation of the FiniteStateMachine (FSM) class. I say somewhat, because the current class interface and available features are not providing the level of abstractions needed to encapsulate the error-prone tasks of using an FSM.

Overview
Here is a quick overview of what can be done with the current implementation.
  • Programmatically add states and transitions to an FSM.
  • Specify a predicate per transition, denoting which input symbols cause the transition.
  • Construct an enumerator to walk the FSM, one input symbol at a time.
For most cases, one is interested if a collection of input symbols are accepted or rejected by an FSM. With the current implementation, you would need to feed the symbols to the enumerator one at a time and check the enumerator's return value for failure. Also, the FSM has no notion of a final state, so the caller of the enumerator has the burden of checking the validity of the resulting state. All of this is tedious work, and will be encapsulated in the FSM class as part of a future work item.

The following is a code sample that demonstrates the usage of the FSM to validate a Canadian postal code.


// Validates a Canadian postal code (xnx-nxn, where x is a letter and n is a digit; e.g. H0H-0H0).
bool ValidatePostalCode(string postalCode)
{
FiniteStateMachine<char> fsm = new FiniteStateMachine<char>;
fsm.AddState("start");
fsm.AddState("final");
fsm.AddState("letter_0");
fsm.AddState("letter_1");
fsm.AddState("letter_2");
fsm.AddState("hyphen");
fsm.AddState("digit_0");
fsm.AddState("digit_1");

fsm.AddTransition(new Transition<char>("start", "letter_0", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_0", "digit_0", Char.IsDigit));
fsm.AddTransition(new Transition<char>("digit_0", "letter_1", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_1", "hyphen", ch => ch == '-'));
fsm.AddTransition(new Transition<char>("hyphen", "digit_1", Char.IsDigit));
fsm.AddTransition(new Transition<char>("digit_1", "letter_2", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_2", "final", Char.IsDigit));

IFsmEnumerator<char> enumerator = fsm.CreateStateEnumerator("start");
foreach(char symbol in postalCode)
{
if(!enumerator.NextState(symbol)) { return false; }
}

return enumerator.CurrentState == "final";
}

Overall, a bit laborious but it sets a good foundation to get the internals working.

QuickGraph and FSM Persistence
The FSM classes use QuickGraph as the underlying storage for the representation of the FSM. I chose to use this library over the tabular FSM representation because the graph data structure avoids a sparse FSM table, and that the graph library supports graph serialization, persistence, and visualization. A quick comparison of the two data structures shows that navigation speed of the graph from vertex to vertex is on the same order as a table lookup, however the memory overhead is slightly higher due to the management of hash tables versus a single two-dimensional array. In the future, I may consider abstracting the data storage of the FSM into a policy to support the tabular implementation.

I've also been concerned with the ability to serialize and persist a graph that contains dynamic data structures such as anonymous delegates. How does one represent a non-static method call in XML? I've verified that the binary serializer supports method and parameter serialization, but this doesn't bode well with users that want to manage and create an FSM in a human-readable file. So, I'm going to revisit this issue when addressing the serialization work item; the QuickGraph graph visualizers may have some native support to address this issue.

Jolt.NET Intial Release and Future Features

Preparing the Initial Release

Sometime today, I will commit a revision that completes the list of work items for the release marked "Initial Release".  This release will contain a very functional and near-complete version of proxy generation tool for mocking/dependency injection.  The release will also contain one known issue that may cause some grief, specifically, adding nested public types from non-public declaring types, demonstrated as follows.


internal class List<T>
{
// ... list methods ...

public class Iterator<T>
{
// ... iterator methods ...
}
}

As you can see, the frequency of this situation is rare.  You wouldn't be able to use the nested type outside the scope of the assembly, so you wouldn't be able to mock it to begin with.  However, such a situation becomes valid when the assembly grants internal access to another assembly.  So, I would like to revisit this usage in the future and perhaps add some ability for a client to provide a list of friend assemblies to the ProxyTypeBuilder or ProxyAssemblyBuilder.

Future Features

I first had the idea for Jolt.NET about one year ago after working on a .NET port of the Boost Graph Library (BGL). I had completed a generic Graph<T> data structure with some rudimentary algorithms, including serialization support. It was at that point that I discovered the .NET 1.1 version of QuickGraph, which looked like an abandoned project at the time -- ironically, my initial searches for a BGL port didn't produce anything :(.  Today, the QuickGraph authors have implemented all the features that I had intended to, including Linq support!  It trully is a formidable BGL port.

After implementing a solid graph data structure, my next goal was to build a generic finite state machine on top of the graph.  And so, this will be the next big feature.  Jolt.NET will contain a new library with the first feature being a generic finite state machine, using QuickGraph as its underlying data structure.

I also wanted to work on XML assertions for many of the popular managed-language testing tools, NUnit being one of them.  This feature would basically extend the NUnit assertion set via a constraint, and allow one to write assertions like the following.



[Test]
public void VerifyXml()
{
Assert.That(GetXmlReader(), Is.Valid(GetXmlSchema()));
Assert.That(GetXmlReader(), Is.EquivalentTo(GetOtherXmlReader()));
Assert.That(GetXmlReader(), Is.EqualTo(GetXmlReader()));
}


After looking at the vision document for NUnit 3.0 and some discussions in NUnit-discuss, it looks like the implementation of  feature is already under way, so I won't start work on in for Jolt.NET.  Way to go guys!