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.