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!

Generic Method Support Enabled

Revision #17390 includes support for parsing generic methods and emitting them via the ProxyTypeBuilder class. In addition to the generic type support described in a previous post, the following operations now demonstrate the complete set of public method proxy-generating operations (excluding explicit interface implementations, which are not really public).


void CreateMethods()
{
Type realSubjectType = typeof(System.Array);
ProxyTypeBuilder builder = new ProxyTypeBuilder("namespace", realSubjectType);

// ConvertAll and Find are implemented in terms of generic method arguments.
builder.AddMethod(realSubjectType.GetMethod("ConvertAll"));
builder.AddMethod(realSubjectType.GetMethod("Find"));

builder.CreateProxy();
}


This revision also includes the results of a tool-set upgrade to Visual Studio 9 (2008) with .NET 3.5 SP1. I took the liberty of simplifying some code by replacing many anonymous delegates with equivalent lambda expressions, and replacing explicit delegate types with specializations of System.Func.

I also noticed that upon removal of the initial explicit interface implementation feature, the ProxyMethodDeclarer and InterfaceMethodDeclarer types were very similar. The only difference between these types was that each type defined their own MethodAttributes value as a member variable. By factoring out this variable and moving its definition to a constructor, I was able to further simplify the code by removing one of the "method declarer" types. The following diagram shows the result of this refactoring and updates the class diagram from a previous post.

CodePlex Page Load Performance

Yesterday I noticed that it was taking too long to load a page on the Jolt.NET CodePlex site. I tracked this down to the BrightAds script that was running on the page and then noticed that it wasn't rendering any ads. Ironically, I didn't notice this sooner because I run an ad blocker on some computers, which effectively eliminates the call to the BrightAds server.

It turns out that BrightAds is no longer supported by Kanoodle (see email below), and thus any ad request will ultimately timeout. I don't know when the service was shutdown, but it at least explains some other performance issues reported at CodePlex.

from Adrienne Carrick <adriennec@pulse360.com>
date Fri, Nov 7, 2008 at 6:13 AM
subject RE: Your BrightAds Application Has Been Reviewed

Hi Steve -

The Bright Ads service is no longer available.
You should have received an e-mail notification regarding this.

I apologize for any inconvenience this has caused.

Thank you,
Adrienne


Adrienne Carrick
Associate, Client Relations

Consequently, I've since removed the BrightAds script from the Jolt.NET CodePlex site and guess what?  Pages now load at their normal speed.

Happy browsing!

Generic Type Support Enabled

This morning I committed revision 16788, which includes support for the acceptance of generic types by the ProxyTypeBuilder class. Consequently, the following tasks are now supported:


void CreateTypes()
{
ProxyAssemblyBuilder builder = new ProxyAssemblyBuilder();

// Creates IList<T> and ListProxy<T>:
builder.AddType(typeof(System.Collections.Generic.List<>));

// Creates IStack and StackProxy, the latter of which encapsulates a Stack<int> instance
builder.AddType(typeof(System.Collections.Generic.Stack<int>));

builder.CreateAssembly();
}

void CreateMethods()
{
Type realSubjectType = typeof(System.Collections.Generic.Dictionary<,>);
ProxyTypeBuilder builder = new ProxyTypeBuilder("namespace", realSubjectType);

// Add and ContainsKey are implemented in terms of generic type arguments.
builder.AddMethod(realSubjectType.GetMethod("Add"));
builder.AddMethod(realSubjectType.GetMethod("ContainsKey"));

builder.AddProperty(realSubjectType.GetProperty("Count"));

builder.CreateProxy();
}


If you use the ProxyAssemblyGen.exe program as your driver, then you should familiarize yourself with the .NET Assembly Qualified Name syntax for types. This syntax is used in the XML file that is passed to the console program, and the type names are ultimately passed to a Type.GetType() method for loading.

The ProxyTypeBuilder still lacks support for handling generic methods, and I've added code to explicitly warn a caller when such a method is encountered. My next task will be to work on issue #29, which addresses generic methods. Furthermore, I need to clean-up some of the code, remove some duplication, and ultimately update to Visual Studio 9/.NET 3.5/C# 3.0.

Things are looking good as we approach the first release!

Interface Implementations: Revisited

Yesterday I investigated stripping explicit interface implementation from the ProxyTypeBuilder as a result of my research described in this post. My preliminary conclusion is that this is the right way to go, as it will simplify some of the code and sidestep the generic interface issue.

I also started thinking about bug #27, as it relates to interface inheritance and implementation. The bug in question states that if a real subject type inherits a collection of interfaces, then the generated proxy should also inherit the same interfaces. Doing so allows you to pass the proxy reference to methods that accepted the real subject type as an interface handle.

It turns out that this is a complex problem to solve, as depicted by the following code.



public interface Ia { void f(); }
public interface Ib { void f(); }
public interface Ic { void f(); void h(); }
public interface Id<T> { T f(); }

public sealed class RealSubject : Ia, Ib, Ic, Id<int>, IDisposable
{
public void Dispose() { }

void Ia.f() { }
void Ib.f() { }

public void f() { }
void Ic.h() { }

int Id<int>.f() { return 0; }

public void g() { }
}

public interface IProxy : Ia, Ib, Ic, Id<int>, IDisposable
{
void g();
}

public sealed class Proxy : IProxy
{
public void Dispose() { m_t.Dispose(); }
public void f() { m_t.f(); } // Satisfies Ia, Ib, and Ic, but forwards to RealSubject.f().
public void g() { m_t.g(); }

void Ia.f() { (m_t as Ia).f(); }
void Ib.f() { (m_t as Ib).f(); }
void Ic.f() { (m_t as Ic).f(); }
int Id<int>.f() { return (m_t as Id).f(); }

void Ic.h() { (m_t as Ic).h(); }

private readonly RealSubject m_t = new RealSubject();
}


You will notice that the only method defined by the RealSubject is g(). All other methods implement an interface. Consequently, the only method that needs to be generated in the IProxy interface is g() since if IProxy inherits all of the interfaces inherited by RealSubject, then it will force Proxy to implement those interfaces.

The difficulty in solving this problem comes when the method f() is added to the ProxyTypeBuilder. It is o.k. for the ProxyTypeBuilder to not override any of the interface methods in Ia, Ib, and Ic, since it is still legal C# syntax. However, which interfaces should IProxy implement? If we say "all of them", then the code becomes illegal since Proxy doesn't implement Ic.h(). Infact, this problem arises when we give any method that implements an interface to the ProxyTypeBuilder. We can only add the inherited interface to IProxy once we know that all of its method implementations are satisifed.

Perhaps an interface change in ProxyTypeBuilder is required to better address this issue. In any case, I will move this bug to a post-initial release time period as I will need to think about it in order to derive the correct implementation.

Finally, the lack of this feature means that only public methods will be accepted by the ProxyTypeBuilder (which is the current implementation). Explicitly implemented interface methods require interface inheritance, which will be addressed later on. Note that the generic interface implementation issue will need to be addressed when this feature is implemented, so hopefully a patch is available by then!

Frustration with Reflection.Emit API

Over the past few months, I've been working on adding generics support to the Jolt.Testing library. I've been travelling too, so I haven't had as much time as I would have liked to spend on development.

I'm currently focusing on generic type definitions (generic method definitions will come later). For a given generic real subject type, the ProxyTypeBuilder needs to generate a generic interface and generic proxy type that match in number of arguments. Furthermore, the proxy's arguments must specialize the interface, and the interface must carry the same constraints as the real subject type. These requirements are demonstrated by the following example.



public class UserType<A,B,C>

where A : class

where B : struct

where C : A

{

bool Method() { return true; }

}



public interface IUserType<A,B,C>

where A : class

where B : struct

where C : A

{

bool Method();

}



public sealed class UserTypeProxy<Q,R,S> : IUserType<Q,R,S>

{

bool IUserType<Q,R,S>.Method() { return m_realSubjectType.Method(); }

private readonly UserType m_realSubjectType = new UserType<Q,R,S>();

}




In writing the code to implement this type of code generation, I believe I found a bug in the Reflection.Emit API. For reference, here is the code that I believe should emit the class interface and proxy relationship.


void CreateTypes(ModuleBuilder module)

{

TypeBuilder contractInterface = module.DefineType("IUserType", TypeAttributes.Public TypeAttributes.Interface TypeAttributes.Abstract TypeAttributes.AutoClass TypeAttributes.AnsiClass);

contractInterface.DefineGenericParameters("A", "B", "C");

MethodBuilder interfaceMethod = contractInterface.DefineMethod("Method",

MethodAttributes.Abstract MethodAttributes.HideBySig MethodAttributes.NewSlot MethodAttributes.Virtual MethodAttributes.Public,

typeof(bool), Type.EmptyTypes);



TypeBuilder implementationType = module.DefineType("UserTypeProxy", TypeAttributes.Public TypeAttributes.Sealed TypeAttributes.AutoClass TypeAttributes.AnsiClass TypeAttributes.BeforeFieldInit);

GenericTypeParameterBuilder[] implementationParams = implementationType.DefineGenericParameters("Q", "R", "S");

implementationType.DefineDefaultConstructor(MethodAttributes.Public MethodAttributes.SpecialName MethodAttributes.RTSpecialName);

MethodBuilder implementationMethod = implementationType.DefineMethod(contractInterface.FullName + "<Q,R,S>.Method",

MethodAttributes.Private MethodAttributes.HideBySig MethodAttributes.NewSlot MethodAttributes.Virtual MethodAttributes.Final,

typeof(bool), Type.EmptyTypes);



ILGenerator ilgen = implementationMethod.GetILGenerator();

ilgen.Emit(OpCodes.Ldc_I4_0);

ilgen.Emit(OpCodes.Ret);



Type specializedContract = contractInterface.CreateType().MakeGenericType(

implementationParams[0], implementationParams[1], implementationParams[2]);

implementationType.AddInterfaceImplementation(specializedContract);

implementationType.DefineMethodOverride(implementationMethod, interfaceMethod);

contractInterface.CreateType();

implementationType.CreateType();

}




Unfortunately, executing this code yields the following exception.

System.TypeLoadException : Type 'UserTypeProxy' from assembly 'test, Version=1.0.0.0, Culture=neutral, PublicKeyToken=null' tried to override method 'IUserType.Method' but does not implement or inherit that method.

I’ve done a considerable amount of experimenting with this code, and I’m no longer sure that I have implemented the routine correctly. The error message is confusing, because the code sure looks like it is creating a method override for a method that exists. What as more confusing is the the documentation for DefineMethodOverride, which states that the method call is not needed when overriding a base-class or interface method. However, I’ve found this to be untrue when explicitly implementing an interface. Also, the above routine works as expected when I removed the generic parameters from the routine, including the MakeGenericType call; you will notice that this case is almost identical to the code path that is currently checked in for non-generic types.

My research carried me to this bug report, which is very similar in nature to my issue, but it is unclear whether the bug is fixed in .NET 3.5. A look at mscorlib.dll shows a version of 2.0.0.0, which hasn't changed since the release of .NET 2.0 so the answer is likely "not fixed".


If there is a bug in the Reflection.Emit API, then this is a dissapointing setback as the bug is unlikely to be resolved in the near-term. In that time period, I would have to restrict the code generation to implement interfaces implicitly and doing so would limit the allowable methods from a real subject type to those that do not override another via an explicit interface implementation.


public class RealSubjectType : IDisposable

{

// One of these methods will be unavailable in IRealSubjectTypeProxy.

void IDisposable.Dispose() { /* do something */ }

public void Dispose() { /* do something else */ }

}




In the mean time, I'll keep tinkering with the code and determine if it is worthwhile to continue with the approach of explicit interface implementation. Who knows, maybe a reader will point out the fault with my current code generation implementation? :)

Abstracting MethodBuilder and ConstructorBuilder

I recently committed a revision to the Jolt.Testing library that changed the internal structure of how methods and constructors are defined. Prior to this change, the ProxyTypeBuilder class was responsible for declaration of all method types, constructor types, their parameters, and their implementations.

When I started to think about how the code should be structured to support generic types and methods, it was soon apparent that the declaration of methods needed to be separated from the definition of the proxy and interface types. Otherwise, I would need to introduce many conditional statements throughout the code to deal with the cases of generic/non-generic subject type and generic/non-generic method. Generic class state would also have to be stored in a shared location as generic type parameters can be used in a method signature. I think I could have written this quickly, but I didn't like what the code was going to look like and proceeded to come up with a structure that looked like the following.



The intent of this class layout is to separate the concerns of declaring methods (AbstractMethodDeclarerImpl) and declaring types of methods (AbstractMethodDeclarer). The AbstractMethodDeclarerImpl.DeclareMethod() method initializes the signature of the method (parameter types and return value), AbstractMethodDeclarerImpl.DefineMethodParameters() initializes the method's parameter names and attributes, and AbstractMethodDeclarer.Declare() is implemented in terms of the latter two methods. Unfortunately, this ideal solution assumes the existence of features that don't exist.

There is no common interface (or base class) between ConstructorBuilder and MethodBuilder.

The above diagram shows a MethodBuilder object in method signatures, however it is the intent is for this object to be an abstraction. This was crucial for both AbstractMethodBuilder[Impl] hierarchies to function as they would need to call the abstract DeclareMethod(), SetParameters(), SetReturnType(), and DefineParameters() methods, in different configurations. While I could create the abstraction manually and delegate to MethodBuilder and ConstructorBuilder as necessary, I won't be able to solve the following problem.

MethodBuilder and ConstructorBuilder have similar but different usage semantics.

If you look at the interface to TypeBuilder, you will notice that you can define a method in one step as part of the TypeBuilder.DefineMethod() method. Similarly, you can do the same for a constructor with TypeBuilder.DefineConstructor(). In addition to TypeBuilder.DefineMethod(), you can define the method in stages by calling MethodBuilder.SetParameters() and MethodBuilder.SetReturnType(). This is useful for introducing generic method parameters, which must be defined in stages via other MethodBuilder methods. Unfortunately, this set of methods are not paralleled to the ConstructorBuilder class. Why? My guess is that it doesn't make sense to do so: there is no such thing as a generic constructor (i.e. class C<T> { C<U>(U u, T t) { /* T is the only valid type /* }), nor can a constructor have a return value. So, you may as well declare the constructor in one shot and avoid creating a ConstructorBuilder with bad state.

Consequently, this second issue breaks the ideal design I was striving for. There is no way I can create an abstraction for MethodBuilder and ConstructorBuilder and cleanly separate the declaration of a method and its parameters -- an absolute requirement when dealing with generic methods. I tried and tried many tricks and hacks to get this to work cleanly, but the above design caveat finally convinced me to throw in the towel. The best I could do was to treat the ConstructorMethodDeclarer as a special case and introduce it into the hierarchy in a less-than-optimal manner. Here is the structure I settled upon.



The handling of generic/non-generic constructors are now done in two distinct types: NonGenericConstructorDeclarer and GenericConstructorDeclarer (TBD). The ConstructorDeclarerImpl class implements the IMethodDeclarerImpl.DefineMethodParameters() method as this call is needed for any method-building type, but throws when IMethodDeclarerImpl.DeclareMethod() is invoked.

To address the common base type issue, I made the base classes generic on two parameters: the method builder type, and the method result type (e.g. MethodBuilder, and MethodInfo). A constraint enforces the semantics that TMethodBuilder derives from TMethod and TMethod derives from MethodBase. This constraint still allows some illegal configurations, but implementing those configuration won't make much sense anyway.

Instantiation of these types is hidden by a factory class that assures objects are connected in the correct manner.

So, what has been created here? If you consider the bridge battern, there really are two bridges collapsed under one interface:

  • InterfaceMethodDeclarer and ProxyMethodDeclarer configured with GenericMethodDeclarerImpl and NonGenericMethodDeclarerImpl
  • NonGenericConstructorDeclarer and GenericConstructorDeclarer configured with ConstructorDeclarerImpl

There are also (or will be) two additional types required (the constructor permutations) when compared with ideal structure. Overall, I believe this solution addresses the issue of separation of concerns (method and type construction) well, given the previously described constraints. If readers have ideas to simplify this solution, please share them in the forum or as comments to this article.

Naturally, the client code in ProxyTypeBuilder has simplified significantly. Here is a snippet showing the usage of this hierarchy.


// Create a constructor on the proxy for each public constructor
// on the real subject type.
foreach (ConstructorInfo constructor in m_realSubjectType.GetConstructors(BindingFlags.Public | BindingFlags.Instance))
{
ILGenerator codeGenerator = m_methodDeclarerFactory.Create(constructor).Declare().GetILGenerator();

// ... implement body ...
}

// Declare the interface and proxy methods.
interfaceMethodBuilder = m_methodDeclarerFactory.Create(MethodDeclarerTypes.Interface, method).Declare();
proxyMethodBuilder = m_methodDeclarerFactory.Create(MethodDeclarerTypes.Proxy, method).Declare();

// ... implement bodies ...

Back from Inactivity

It has been almost one year since I started Jolt.NET and I've finally have been able to put some time aside to resuming work on the first release. I was hoping to have this release completed much sooner, but I've gone through some big life-changes that have kept me away from the code. Given this long period of inactivity, I thought it best to start a blog so readers can keep current on what is being developed, fixed, etc...

The story so far:

I've been working on and off on in the testing library, refactoring the classes that deal with proxy and interface creation. The library must support creation of generic types and methods, and the currently available architecture won't easily support the necessary extension.

The refactoring is complete and the next check-in will enable me to start to work on support for generic types and methods; I'm banking on this refactoring to make the upcoming implementation very straight-forward. Currently, I need to run some ad-hoc tests and make sure that I didn't break anything fundamental in the code-generation process, but the unit tests are giving me high confidence that the program still functions as expected.