Immutability Matters
Testing Immutable Types

As alluded to previously, having a good suite of unit tests is critical for ensuring these immutable instances do what they should - after all, there’s no point in having a queue or stack that doesn’t behave.

But, given the complex interplay of different implementations we’ve created - with the interactions between EmptyImmutableQueue<T>, SimpleImmutableQueue<T>, ComplexImmutableQueue<T> and ConcatenatedQueue<T> - how do we ensure everything works?

Enter FsCheck - a property based testing framework (think property as in characteristic, not as in get/set). Testing with FsCheck involves defining tests that check the characteristics of our classes.

For a queue, the primary characteristic is that all of the items added into the queue are returned, in the same order. Here’s a simple test that checks this:

[Property(EndSize = 1000)]
public void QueueSuppliesItemsInOriginalOrder(IList<string> items)
{
    var queue = ImmutableQueue<string>.Empty
        .EnqueueAll(items);
    var list = queue.ToList();
    list.Should().Equal(items);
}

How does this work?

FsCheck will call this test 100 times, each time with a different list of items. The items in each list will be added to an empty queue and then read out again. If the resulting list has the same items, in the same order, the test passes. This example uses the FluentAssertions framework for the assert on the last line.

Here’s a (somewhat artificial, and slightly edited) sample test failure:

Test Name:     SampleTests.QueueTests.QueueSuppliesItemsInOriginalOrder
Test FullName: SampleTests.QueueTests.QueueSuppliesItemsInOriginalOrder
Test Source:   QueueTests.cs : line 17
Test Outcome:  Failed
Test Duration: 0:00:01.05

Result Message:
FsCheck.Xunit.PropertyFailedException : 
Falsifiable, after 3 tests (273 shrinks) (StdGen (2028434474,296270705)):
Original:
seq
  ["xf+!C9Jlb.s>4V"g]K("; "SIZ|r`%=    ND"; "$p5+M"; "]Sd|H/%GXNp<w B8"; ...]
Shrunk:
seq [""; ""; ""; ""; ...]

---- Expected collection to be equal to {"", "", "", "", <null>, "", "", "", "", "", "", "", "", "", <null>, "", "", ""}, but {"", "", "", "", <null>, "", "", "", "", "", "", "", "", "", <null>, "", ""} contains 1 item(s) less.

What’s clever about FsCheck is what it does when a failing test case is found. It tries to find a smaller test case that also fails, by applying a number of available shrinking techniques.

In the example shown above, the original failing test case was shrunk 273 times before a minimal example was found with 18 items. This result shows us that a sequence of 17 items is handled correctly, but a sequence of 18 is not. Given that our internal BufferLimit is set to 16 items, this is a big clue that the problem relates to our transition from a SimpleImmutableQueue<T> to ComplexImmutableQueue<T>.

Here’s one of my tests for the ImmutableStack<T> implementation, checking that any item pushed onto the stack is immediately visible through .Peek.

[Property]
public void ItemJustPushedShouldAlwaysBeOnTheTop(
    IList<string> items)
{
    var stack = ImmutableStack<string>.Empty;
    foreach (var i in items)
    {
        stack = stack.Push(i);
        stack.Peek.Should().Be(i);
    }
}

Checking out FsCheck is well worth the time and effort. To complement the testing shown here, you can also create your own generators, allowing FsCheck to create instances of your custom classes for testing needs.