unit testing order of items in a list

Question

How can I setup a deterministic test to verify that items in a list are ordered?

First I did the following:

public void SyncListContainsSortedItems(
    [Frozen] SyncItem[] expected, 
    SyncItemList sut)
{
    Assert.Equal(expected.OrderBy(x => x.Key).First(), sut.First());
}

But as with all good tests, I first looked for a failure before modifying my code. Of course, this succeeded as luck would have it, and then later failed. So my initial failure is not deterministic.

Second I did the following, thinking, 'surely this will guarantee a failure':

public void SyncListContainsSortedItems(
    [Frozen] SyncItem[] seed, 
    SyncItemList sut)
{
    var expected = seed.OrderByDescending(x => x.Key);
    Assert.Equal(expected.OrderBy(x => x.Key).First(), sut.First());
}

To my surprise it also did not provide a deterministic failure. I realized it is because the frozen seed might be naturally created in descending order to start with, so I really didn't improve the situation any.

Right now, my implementation does not order the items passing through the constructor. How do I establish a solid baseline for my test?

Additional Information The sync item list code is shown below. Its not much as it is the design I am exploring:

public class SyncItemList : List<SyncItem>
{
    public SyncItemList(SyncItem[] input)
    {
        foreach (var item in input) { this.Add(item); }
    }
}

Update I've been developing the test. The following works but with high verbosity.

public void SyncListContainsSortedItems(IFixture fixture, List<SyncItem> seed)
{
    var seconditem = seed.OrderBy(x => x.Key).Skip(1).First();
    seed.Remove(seconditem);
    seed.Insert(0, seconditem);
    var seedArray = seed.ToArray();

    var ascending = seedArray.OrderBy(x => x.Key).ToArray();
    var descending = seedArray.OrderByDescending(x => x.Key).ToArray();
    Assert.NotEqual(ascending, seedArray);
    Assert.NotEqual(descending, seedArray);

    fixture.Inject<SyncItem[]>(seedArray);
    var sut = fixture.Create<SyncItemList>();

    var expected = ascending;
    var actual = sut.ToArray();
    Assert.Equal(expected, actual);
}

One simple way to alter my implementation to make it pass is to inherit from SortedSet<SyncItem> instead of List<SyncItem>.

Answer 1

There are various ways to go about this.

Imperative version

Here's a simpler imperative version than the one provided in the OP:

[Fact]
public void ImperativeTest()
{
    var fixture = new Fixture();
    var expected = fixture.CreateMany<SyncItem>(3).OrderBy(si => si.Key);
    var unorderedItems = expected.Skip(1).Concat(expected.Take(1)).ToArray();
    fixture.Inject(unorderedItems);

    var sut = fixture.Create<SyncItemList>();

    Assert.Equal(expected, sut);
}

While the default number of many items is 3, I think that it's better to call it out explicitly in this test case. The scrambling algorithm used here takes advantage of the fact that after ordering a sequence of three (distinct) elements, moving the first element to the back must result in an unordered list.

However, the problem with this approach is that it relies on mutating the fixture, so it's hard to refactor to a more declarative approach.

Customized version

In an effort to refactor to a more declarative version, you can first encapsulate the scrambling algorithm in a Customization:

public class UnorderedSyncItems : ICustomization
{
    public void Customize(IFixture fixture)
    {
        fixture.Customizations.Add(new UnorderedSyncItemsGenerator());
    }

    private class UnorderedSyncItemsGenerator : ISpecimenBuilder
    {
        public object Create(object request, ISpecimenContext context)
        {
            var t = request as Type;
            if (t == null ||
                t != typeof(SyncItem[]))
                return new NoSpecimen(request);

            var items = ((IEnumerable)context
                .Resolve(new FiniteSequenceRequest(typeof(SyncItem), 3)))
                .Cast<SyncItem>();
            return items.Skip(1).Concat(items.Take(1)).ToArray();
        }
    }
}

Resolving a new FiniteSequenceRequest(typeof(SyncItem), 3)) is simply the weakly-typed (non-generic) way of creating a finite sequence of SyncItem instances; it's what CreateMany<SyncItem>(3) does behind the scenes.

This enables you to refactor the test to:

[Fact]
public void ImperativeTestWithCustomization()
{
    var fixture = new Fixture().Customize(new UnorderedSyncItems());
    var expected = fixture.Freeze<SyncItem[]>().OrderBy(si => si.Key);

    var sut = fixture.Create<SyncItemList>();

    Assert.Equal(expected, sut);
}

Notice the use of the Freeze method. This is necessary, because the UnorderedSyncItems Customization only changes the way SyncItem[] instances are created; it still creates a new array every time it receives a request to do so. Freeze ensures that the same array is being reused every time - also when fixture creates the sut instance.

Convention-based testing

The above test can be refactored to a declarative, convention-based test, by the introduction of an [UnorderedConventions] attribute:

public class UnorderedConventionsAttribute : AutoDataAttribute
{
    public UnorderedConventionsAttribute()
        : base(new Fixture().Customize(new UnorderedSyncItems()))
    {
    }
}

This is simply the declarative glue for applying the UnorderedSyncItems Customization. The test now becomes:

[Theory, UnorderedConventions]
public void ConventionBasedTest(
    [Frozen]SyncItem[] unorderedItems,
    SyncItemList sut)
{
    var expected = unorderedItems.OrderBy(si => si.Key);
    Assert.Equal(expected, sut);
}

Notice the use of the [UnorderedSyncItems] and [Frozen] attributes.

This test is very succinct, but may not be what you're after. The problem is that the change of behaviour is now hidden away in the [UnorderedSyncItems] attribute, so it's rather implicit what's happening. I prefer to use the same Customization as a set of conventions for an entire test suite, so I don't like to introduce test case variations at this level. However, if your conventions state that SyncItem[] instances should always be unordered, then this convention is good.

However, if you only wish to use unordered arrays for some test cases, the use of an [AutoData] attribute isn't the most optimal approach.

Declarative test case

It'd be nice if you could simply apply a parameter-level attribute, just like the [Frozen] attribute - perhaps combining them, like [Unordered][Frozen]. However, this approach doesn't work.

Notice from the previous examples that the order matters. You must apply UnorderedSyncItems before Freezing, because otherwise, the array being frozen may not be guaranteed unordered.

The problem with [Unordered][Frozen] parameter-level attributes is that, while it compiles, the .NET framework doesn't guarantee the order of attributes when the AutoFixture xUnit.net glue library reads and applies the attributes.

Instead, you can define a single attribute to apply, like this:

public class UnorderedFrozenAttribute : CustomizeAttribute
{
    public override ICustomization GetCustomization(ParameterInfo parameter)
    {
        return new CompositeCustomization(                
            new UnorderedSyncItems(),
            new FreezingCustomization(parameter.ParameterType));
    }
}

(FreezingCustomization provides the underlying implementation of the [Frozen] attribute.)

This enables you to write this test:

[Theory, AutoData]
public void DeclarativeTest(
    [UnorderedFrozen]SyncItem[] unorderedItems,
    SyncItemList sut)
{
    var expected = unorderedItems.OrderBy(si => si.Key);
    Assert.Equal(expected, sut);
}

Notice that this declarative test uses the default [AutoData] attribute without any Customizations, because the scrambling is now applied by the [UnorderedFrozen] attribute at the parameter level.

This would also enable you to use a set of (other) test suite-wide conventions encapsulated in an [AutoData]-derived attribute, and still use [UnorderedFrozen] as an opt-in mechanism.