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.

Verifying the Equality Semantics of a Type

My most recent contribution to Jolt.NET is implementing a set of assertion classes that verify if a type correctly implements equality semantics.  This is a unit testing task that is generally ignored, only because implementations of Object.Equals() are usually straightforward and implemented in terms of other types that meet this critieria.

 
When implementing an equality operator, you must make sure that it satisfies the following axioms.
 
  • Symmetry:  Equals(x,y) == Equals(y,x)
  • Transitivity:  Equals(x,z) == true if and only if (Equals(x,y) & Equals(y,z)) == true
  • Reflexivity:  Equals(x,x) == true
  • Hash-code:  Equals(x,y) => GetHashCode(x) == GetHashCode(y)
 
I've omitted the other axiom requirements for equality, which are described by the MSDN documentation for Object.Equals().
 

Jolt.NET provides the type EqualityAxiomAssertion<T> to validate the implementations of T.Equals() according to the prescribed axioms.  You may use the type as follows.

 
class TypeToValidate
{
public override bool Equals(object other)
{
return other is TypeToValidate &&
(other as TypeToValidate).m_name.Equals(m_name);
}

public string m_name;
}

class TypeFactory : IArgumentFactory<TypeToValidate>
{
public TypeFactory Create()
{
return new TypeToValidate() { m_name = "Hello world!" };
}

public void Modify(ret TypeToValdidate instance)
{
instance.m_name = "Goodbye world!";
}
}

class TestFixture()
{
void Test()
{
EqualityAxiomAssertion<TypeToValidate> assertion =
new EqualityAxiomAssertion<TypeToValidate>(new TypeFactory());

AssertionResult assertionResult = assertion.Validate();
System.Diagnostics.Debug.Assert(assertionResult.Result, assertionResult.Message);
}
}
 
IArgumentFactory<T> is required by the assertion type since it needs to be able to create and modify instances of the type that is being verified.  For instance, the transitivity axiom requires three distinct instances, and hash-code verification must modify an instance and verify that the resulting hash-code has changed.
 
There are many representations of an equality operator in .NET, some of which are Object.Equals(), IEquatable<T>, IComparable<T>, and IEqualityComparer<T>.  In addition to EqualityAxiomAssertion<T>, Jolt.NET also provides the EqualtableAxiomAssertion<T>, ComparableAxiomAssertion<T>, and EqualityComparerAxiomAssertion<T> to verify implementations of the aforementioned equality interfaces, with similar usage semantics.
 
Jolt.NET also provides a wrapper to these assertion types for straightforward integration with NUnit and Visual Studio's unit test environment.  An example of how to use a wrapped EqualityAxiomAssertion<T> in these environments follows.  Note that the remaining assertion types are also wrapped by similar methods and/or constructs.
 
class TestFixture()
{
// Visual Studio assertion model
[TestMethod]
public void EqualityAxiomTest()
{
AxiomAssert.Equality(new TypeFactory());
}
}

[TestFixture]
class NUnitFixture
{
// NUnit assertion model
[Test]
public void EqualityAxiomTest()
{
// verbose constraint model
Assert.That(typeof(TypeToValidate), new EqualityAxiomConstraint<TypeToValidate>(new TypeFactory()));

// syntax-helper constraint model
Assert.That(typeof(TypeToValidate), Implements.EqualityAxiom(new TypeFactory()));
}
}
 
The astute reader will notice that there is some duplication in the syntax for invoking the constraint.  Specifically, the type information is duplicated.  In fact, the first argument of the assertion is not used by the constraint at all -- it is merely present for readability when using a syntax helper.  Ideally, I would have liked to have used a syntax similar to the following.
 
[Test]
public void EqualityAxiomTest()
{
Assert.That<TypeToValidate>(Implements.EqualityAxiom(new TypeFactory()));
}
  
However, this is not possible for several reasons.
 
  • NUnit constraints are designed to compare an actual value against an expected value; an argument-less constraint is not possible.
    • This notiion is somewhat incompatible with the axiom assertion since the assertion is validating a property of a generic type argument.
    • The assertion could have been designed to be non-generic and operate on System.Type, but that implementation would be more cumbersome
  • An extension method on Assert is not possible since Assert methods are static.
 
Another option is to use the factory instance as the argument passed to the constraint, as in the following example.  However, while this option makes sense from an implementation standpoint, it suffers greatly in readability as a factory instance is not what is being asserted upon.
 
[Test]
public void EqualityAxiomTest()
{
// verbose constraint syntax
Assert.That(new TypeFactory(), new EqualityAxiomConstraint<TypeToValidate>());

// syntax-helper constraint syntax.
Assert.That(new TypeFactory(), Implements.EqualityAxiom<TypeToValidate>());
}
 
The documentation for these classes will be posted to the docs section shortly, and in the future, support will be added for the non-generic interfaces IEquatable, IComparable, IEqualityComparer.

Return to Developing Jolt.NET

Good day readers!

Over the past few months, I haven't spend any time time on the Jolt.NET project as I've experienced several life-changes that require the reallocation of the limited time I have to spend on hobbies.  My daughter was born in February and she has brought much joy to my family.  As with most newborns, she is a handful, and requires near-constant supervision.  I've also recently changed roles within my firm, and my new responsibilities require more of my time.  Recently, things have started to become more routine and so I'm hoping to return to the Jolt.NET project and complete some pending items of importance.  

Non-deterministic FSM Support

One such item of importance is the support of enumerating non-deterministic automata.  When implementing this feature, I realized that I needed to introduce a breaking change into the generalization of an FSM enumerator as the IFsmEnumerator<T> interface conveys that all enumerator implementations return one state as part of a transition.  Since this is not true for non-deterministic FSMs, the interface is changed to the following.

public interface IFsmEnumerator<TAlphabet>
{
bool Next(TAlphabet inputSymbol);
string CurrentState { get; }
IEnumerable<string> CurrentStates { get; }
}

The main differences in this interface revision are the semantics of the CurrentState and (new) CurrentStates properties for different types of enumerators.  When the enumerator is reading a deterministic FSM, CurrentState refers to the current enumeration state, and CurrentStates is a collection containing a single reference to CurrentStates.  However, when the enumerator is reading a non-deterministic FSM, CurrentStates contains the current enumeration states (which may be more than one) and CurrentState refers to the first element of the CurrentStates collection.

The consequences of this interface change propagate to the following FiniteStateMachine<T> methods.

public class FiniteStateMachine<TAlphabet>
{
// ... other members omitted for brevity ...

public virtual IFsmEnumerator<TAlphabet> CreateStateEnumerator(EnumerationType type, string startState);

public virtual ConsumptionResult<TAlphabet> Consume(EnumerationType type, IEnumerable<TAlphabet> inputSymbols);
}

When creating an enumerator via the CreateStateEnumerator() method, the type of enumeration must be specified.  Consequently, the type of enumeration must also be specified when consuming a set of input symbols via the Consume() method.

Finally, the ConsumptionResult<T>.LastState property is replaced with the LastStates property, returning a collection of states denoting the set of states viewed immediately prior to completing the symbol consumption.

public sealed class ConsumptionResult
{
// ... other members omitted for brevity ...

public IEnumerable LastStates { get; }
}

ReadOnlyDictionary<T,U> Support

Creating a read-only IDictionary<T,U> collection is a fairly straight-forward task, but this analog to ReadOnlyCollection<T> is surprisingly missing from .NET 4.0.  I have an immediate need for this type in a side project and thus will include a complete implementation it in the library.

For reference, ReadOnlyCollection<T> is an adaptor to IList<T> that prevents a caller from changing the internal structure of the adapted collection (i.e. adding/removing elements).  When a method to change the structure of the collection is called, a NotSupportException is raised and the collection remains unmodified.

Honoring Existing Interfaces on Generated Types

When first developing Jolt.NET, I focused on a tool that will generate an interface and proxy type to any other type.  The goal of this task was to facilitate dependency injection for static types as this is a common problem to tackle when unit testing with existing, non-modifiable static types.  Note that the current implementation doesn't restrict you from generating the interface/proxy pair for just static types.

One challenge that arose during the implementation was dealing with propagating public interface implementations to the proxy/interface pair.  This made a lot of sense since you could use the generated types with methods that accept the abstraction, and everything would just work.  Unfortunately, I found this to be very difficult at the time and postponed implementing it.

I believe I now have a good algorithm to solve this problem (as described in this forum post), and will to try to implement it.


Circular Collections and Enumeration

Sunday evening I committed revision #33654, which includes the first additions to the Jolt.Collections library: circular lists and enumerators.  A complete overview of the features enabled by these types, including usage examples, is available on the library's documentation page.  In this post, I will discuss some of the implementation decisions went into producing these types, as well as give a brief overview of how the new types work.

Adaptors v.s. Collections

The goal of the initial library release was to support three data types:

  • An enumerator capable of enumerating any collection in a circular manner
  • A circular list, with semantics similar to the System.Collections.Generic.List class
  • A circular linked list, with semantics similar to the System.Collections.Generic.LinkedList class

All three of these types were to be implemented as adaptors, providing circular-list semantics as a pseudo-"view" of the underlying collection.  In this view however, insertions and removals would indeed be propagated to the underlying collection wheres as other operations remained read-only.  In order to keep the implementation simple and straightforward (maintaining as many forwarding methods as possible), I decided to implement the circular collections with copy construction semantics (i.e. no adaptation), and in terms of their List and LinkedList counterparts.  It didn't seem right to provide an adaptor whose operations may or may not transform the underlying collection.  Furthermore, the implementation of the Shift operator for a linked list (see below), complicates the implementation of other operations when implemented as a non-destructive operator.

Cyclical v.s. Circular Collections

Another trade-off that was made was in choosing to implement cyclical collections, or the less-general circular collections (cyclical collections join the last collection element to any preceding collection element).  The challenge with a cyclical collection was in using an existing enumerator to implement the enumeration algorithm, again aiming at minimizing the amount of code to rewrite (e.g. version checking, storing collection element references, etc...).  With a cyclical collection, the enumerator needs to reset itself to an arbitrary position in the underlying collection, and unfortunately, there is no good way to do this in a generic fashion -- the .NET enumerator interface provides no such functionality.  The best we could do is store the reference to the start of the cycle and then implicitly enumerate to that element when enumerating beyond the end of the collection.  Clearly, this performs very poorly for large collections.

In the end, I chose circular collections for simplicity.  However, in retrospect, implementing a cyclical collection would not be too difficult if I chose not to reuse certain aspects of the List or LinkedList collections and their enumerators.

Circular Enumerator

CircularEnumerator<T> is an adaptor class accepting an IEnumerator<T> instance at construction time.  The enumerator forwards calls to the underlying enumerator except that when enumeration progresses beyond the last collection element (i.e. Next() returns false), the underlying enumerator is reset and moved to the first collection element.

It goes without saying that you should not use a circular enumerator within a foreach loop unless there is an explicit break condition with the loop body.

Circular List

CircularList<T> is effectively a List<T> with circular list semantics.  That is, the GetEnumerator() method returns a CircularEnumerator<T>, and given indexes for indexing operations are allowed to exceed the bounds of the collection (for positive indexes).  Modular arithmetic translates a user-specified index to the correct internal List index.

CircularList<T> also implements operator>>() and operator<<(), which effectively "rotates" the circular list, changing the sequence of elements.  For instance, if a collection containing the ordered elements {10, 1, 5, 58, 32} is forward-shifted by two elements, the resulting collection contains the elements {5, 58, 32, 10, 1}.  Since List<T> stores its elements in a contiguous memory block, CircularList<T> implements shifting as a "view" on the underlying collection to avoid the copying or moving of collection elements.  A virtual head-index is maintained, and user-specified indexes are adjusted accordingly.

Circular Linked List

CircularLinkedList<T> is effectively a LinkedList<T> with circular list semantics.  That is, the GetEnumerator() method returns a CircularEnumerator<T>, and the node-access methods return a CircularLinkedListNode<T> object.  Similarly, CircularLinkedListNode<T> encapsulates a LinkedListNode<T> and provides circular navigation semantics through its Next() and Previous() methods.

On a side note, the .NET 3.5 implementation of LinkedList<T> is internally implemented as a circular linked list.  The last collection element connected to the first element, and because of this, the implementation of certain list operations is simplified.  Unfortunately, this implementation detail is completely hidden from the user, and can not be leveraged by the CircularLinkedList<T> implementation.

Much like CircularList<T>, CircularLinkedList<T> also implements operator>>() and operator<<().  However, since LinkedList<T> doesn't provide direct-access to an arbitrary element, each call to a shift operation transforms the underlying collection.  An optimization in the shift algorithm places an upper-bound on the total number of shifts to N/2, where N is the size of the collection.  We accomplish this by noting that a forward shift of k elements is identical to a backwards shift of N - k elements.  Hence the maximum number of shifts occur when k = N - k, or k = N/2.

Circular Linked List Node

CircularLinkedListNode<T> encapsulates a LinkedListNode<T>, is used for inserting new nodes into the collection, and representing existing nodes in the collection.  Since LinkedListNode<T> exposes the list in which the node is contained, CircularLinkedListNode<T> must hide this list, but expose the circular list for consistency.  Furthermore, CircularLinkedListNode<T> references are never stored in a container; they are created on-demand.  Thus, it is possible to create two different CircularLinkedListNode<T> object for the same underlying node.  To minimize the impact of this draw-back, CircularLinkedListNode<T> implements IEqualityComparer<T> which performs a reference comparison on each object's underlying nodes.

Jolt.NET 0.4 Release and Future Features

Good day readers!

Yesterday I completed the final work items for Jolt.NET 0.4 and produced the release, available for download at CodePlex.  As mentioned earlier, this release was primarily a maintenance release aimed at addressing some long standing code quality issues and external library upgrades.  However, the release does contain some new features, summarized below.

  • Jolt.NET XML Assertions are now compatible with the Visual Studio test environment, through a set of adapter types
  • XML doc comment parsing for MethodInfo objects that refer to an operator
  • Generated proxy assemblies may now be signed programatically or via XML application configuration
  • All Jolt.NET assemblies are built with a strong name, enabling integrity verification and use with other strong-name assemblies

For more information on these features, please refer to the Jolt.NET library documentation.

The feature list for next release of Jolt.NET remains undefined as I am planning to take on a commercial project that will use the Jolt.NET libraries.  Jolt.NET features will be fueled by the requirements of this new project, but features won't be added unless they are sensible additions for a library.  I do maintain a short-list of potential feature work, and will say that the following features are likely to make the cut for the next Jolt.NET release.

  • Verification of the equality axiom, for implementations of Object.Equals and IEquatable<T>
  • XmlEqualityAssertion and XmlEquivalencyAssertion implementations that accept XPath statements

Do you have any feature requests?  If so, please post them on the work item page, or vote-up existing tasks!

Limitations to XML Doc Comment Parsing

Hello everyone!

I've been working on improving the support for XML doc comment queries with metadata types, but came across some limitations in the reflection API that have hindered my progress.  Specifically, I've been trying to add support for retrieving doc comments for methods containing a function pointer as a parameter, and methods containing a parameter that has been decorated with an optional or required custom modifier.  Unfortunately, given the current state of the reflection API (for which I will elaborate upon below), I don't believe that I can implement these features and achieve a general solution that works for all inputs.


The goal of this feature is to be able to retrieve the XML comments as given in the following code example.

public ref class T
{
public:
/// <summary/>
/// <param name="param">A function pointer of managed types</param>
void FnPtrMethod(String^ (*param)(TimeSpan, DateTime, array<int>^)) { }
};

Since a function pointer is a native C++ entity, it is not recognized by the CLR and consequently I don't believe it to be possible to adequately represent it with a metadata object.  Given the method FnPtrMethod above, the managed type of its sole parameter param is rendered by the reflection API as System.IntPtr.  This is understandable sense since the function pointer is really a raw native pointer to the address of executable code.  It makes no difference that its arguments are managed types, since the type that encompasses them is not managed. If all we have to work with is an IntPtr instance, then it is impossible to infer that the IntPtr is really a function pointer and fetch its managed arguments for processing.

I'm fairly confident that my analysis is correct, but in the hope of being wrong I've started a discussion on StackOverflow just to be sure.  If you know the trick to get this to work, please respond to this blog entry or to the discussion on StackOverflow.


The goal of this feature is to be able to retrieve the XML comments as given in the following code example.

public ref class T
{
public:
/// <summary/>
/// <param name="x">modopt</param>
/// <param name="y">modreq</param>
void modifiers(const int x, volatile int y) { }
};

This feature may be implemented, but only for a small number of variations in the types of method parameters.  The problem lies in the placement of the ParameterInfo.GetOptionalCustomModifiers() and ParameterInfo.GetRequiredCustomModifiers() methods.  These methods are specific to a parameter, and I believe that they should be generalized and applied to any instance of System.Type.  For instance, consider the following method.

public ref class C
{
public:
/// <summary/>
/// <param name="param">Generic action containing modreq/modopt generic argument.</param>
generic <typename T>
void f(Action<const volatile T>^ param) { }
};

The sole parameter param of function f does not have a custom modifier, however the generic method argument T that participates in the definition of the parameter type does.  In this case, it doesn't make sense to call param.GetOptionalCustomModifiers() since the modifiers apply to T.  To get the metadata for T, we need to call GetGenericArguments() resulting in a System.Type array.  But, System.Type does not provide a means to get its custom modifiers!  A similar problem also exists with array and pointer types as custom modifiers are applied to the element type of these entities.  We need to call GetElementType() on the array/pointer type, but are again presented with a System.Type instance and with no way to get its custom modifiers.

Regarding this issue, I've opened a bug report with Microsoft in hopes that the API flaw will be addressed in a future version of the .NET Framework.

However, all is not lost.  We can still use the ParameterInfo.GetOptionalCustomModifiers() and ParameterInfo.GetRequiredCustomModifiers() methods to get custom modifiers for a parameter that is not an array, pointer, or decorated with the by-ref/out attributes (all of these types require us to call GetElementType() to get the type to which the modifier is applied).  Also, the parameter can not be dependent on a generic method or type parameter having a custom modifier applied to it.  This will at least expose the feature to a small number of methods, but it clearly won't work in the general case.  Consequently, I've decided to postpone implementing this feature until I get clearer direction from the community.  If you would like to see this feature implement in Jolt.NET, please vote it up on the Jolt.NET CodePlex web site.

Recent Jolt.NET Revisions and Xml Doc Comment Parsing

I try to make a habit of posting to the development blog each time a significant feature or piece of code gets committed to the source repository.  Consequently, I would like to use this post to summarize what has been committed in the past month as several updates have been made.  Also, I'll describe some of the work I've been doing on matching XML doc comment elements with their corresponding metadata type from the System.Reflection namespace.

Commit Summary

Maintenance and refactoring is the main aspect of the Jolt.NET 0.4 release.  Prior to this release, I've intentionally delayed many code clean-up tasks as well as performing upgrades of 3rd party dependencies so that I could work on more important features.  Now that all those features are complete, I have spent some time to restore the code to its "pristine" state.  Here is a summary of the recent updates related to maintenance.

  • Updated QuickGraph dependency to QuickGraph 3.3.40824
    • Removed FSM->MSAGL conversion code as MSAGL is no longer supported by QuickGraph (superseded by GLEE)
    • Removed explicit implementation of equality semantics for Transition class as it is now supported natively by QuickGraph's EquatableEdge type
  • Updated RhinoMocks dependency to RhinoMocks 3.6
    • Modified relevant unit tests to utilize Act-Arrange-Assert syntax
  • Update NUnit dependency to NUnit 2.5.2
    • Adopted the use of new constraints to simplify and/or strengthen existing unit tests
    • Added additional unit tests to verify presence of attributes on types and their members, a task facilitated by the new constraints in NUnit 2.5
  • Unit test maintenance
    • Fixed many issues that prevented unit tests from being run in an NUnit project (aggregating many test fixtures)
    • Moved much of the reflection code for accessing types and members by strings into separate classes, improving the readability of some unit tests

The following commits introduced new features that were previously planned to be included with the Jolt.NET 0.4 release.

  • The Jolt.Convert class will now correctly generate the XML doc comments representation of an explicit or implicit operator
    • Predefined .NET operators were already supported
    • Consequently, you can now process XML doc comments with a System.Reflection.MethodInfo type referring to an operator
  • Created the Jolt.Testing.Assertions.VisualStudio.XmlAssert class to integrate the Jolt XML assertions to the Visual Studio test framework

XML Doc Comment Processing

"Processing the XML File (C# Programming Guide)" describes the supported XML doc comment markup for various types, methods, parameters, and fields.  For a given metadata type instance, Jolt.Convert will produce the correct markup, with the exception of the following constructs.

  • Function pointer parameter (ELEMENT_TYPE_FNPTR)
  • Optional understanding modifier (ELEMENT_TYPE_CMOD_OPT)
  • Required understanding modifier (ELEMENT_TYPE_CMOD_REQ)
  • Pinned field (ELEMENT_TYPE_PINNED)
  • Dimensionless and rank-less array (ELEMENT_TYPE_GENERICARRAY)

In order to verify that my implementation is correct, I compare the output of a .NET compiler with the output of the Jolt.Convert class.  Since the C# language does not currently support these constructs directly, other means are required for testing the implementation of the Jolt.Convert class, which are demonstrated below.

To produce XML doc comments with ELEMENT_TYPE_FNPTR, ELEMENT_TYPE_CMOD_OPT, and ELEMENT_TYPE_CMOD_REQ markup, we may use the the C++/CLI compiler to compile the following class.


public ref class XmlDocCommentTest
{
public:
typedef int (*function_ptr)(char, int, double);

void fnptr(function_ptr f); // ELEMENT_TYPE_FNPTR
void mod_opt(const int n); // ELEMENT_TYPE_CMOD_OPT
void mod_req(volatile int n); // ELEMENT_TYPE_CMOD_REQ
};


Function pointers are a common construct for C/C++ developers, but understanding why const and volatile translate to optional and required modifiers requires some explanation.  Paul DiLascia covers this topic in his article "C++ At Work: Rationales, Highlights, and a Farewell".

ELEMENT_TYPE_PINNED is a bit more tricky since the general C++ literature on pinned pointers states that their usage is restricted to non-static local stack variables, which can not be decorated with XML doc comments.  However, the System.Runtime.CompilerServices namespace gives some hints on how discover that a field is pinned.  Unfortunately I do not know of a way to verify this behavior using a .NET compiler or other tool.

Finally, ELEMENT_TYPE_GENERICARRAY appears to be deprecated as I can not locate any reference to it in modern .NET documentation (apart from the aforementioned document).

In the mean time, I plan to implement support for all ELEMENT_TYPE_FNPTR, ELEMENT_TYPE_CMOD_OPT, and ELEMENT_TYPE_CMOD_REQ in Jolt.NET 0.4.  For ELEMENT_TYPE_PINNED, I will wait until the feature is highly requested or until I stumble upon a tool that will produce the desired output.

Jolt.NET 0.3 and Future Features

This past afternoon, I committed source revision #26346, containing the final feature work for Jolt.NET 0.3.  This release took longer than expected because I added features to the release after thinking it may be too small, and those features ended up taking longer to implement than expected.  In the future, I will try to make the releases more timely, as long releases make the project appear unmaintained.

Jolt.NET 0.3 contains the following new features:

Please refer to the issue tracker for all features covered by the release, and to the release page for download options.

Jolt.NET 0.4 will be a short maintenance release, which will involve the upgrade of external dependencies.  The dependency upgrade will allow me to simplify some existing code by utilizing a new external library feature, as well as learn how to use such features so that they may be applied in the future..  Furthermore, there have been many maintenance related tasks I’ve been neglecting, and I feel that now is a good time to address them.  Some new features will be added, but only those were previously identified and not included in a preceding release.