August 20, 2020
I recently watched a talk on Property-based testing and its a really interesting approach. When we write a unit test we generally use what they call example based testing. What this means is that we create an expected response and run our test to confirm that the function returns that response. Its great but the nature of bugs is that they generally occur when there is an unexpected input. The question that property based tests try to answer is: Will an allowable input break your function? It will try random values against your function to check if it behaves as expected.
The tricky part if you think in terms of Example-based tests is how do you know what the result should be against a random input? Its a little of a pivot against normal testing because you obviously can't know what it will return without re-implementing the function in your tests. Obviously there really is no point doing that. Instead you tell the framework what the shape of the response should look like. For example if you method returns distinct values from a collection, you can rather confirm things like:
Its a little difficult to do it properly since it requires to you really understand your function but its really powerful. I will show an example but just to be clear: This is not a replacement for example based testing. Its something that can be added in combination with example based tests.
The main library to use for this in .NET is FsCheck which is an implementation of the Haskell package QuickCheck.
I'm going to start with a simple example. I implemented a merge sort but theres a subtle bug in the code.
public class SortExample
{
public static int[] MergeSort(int[] numbers)
{
if (numbers.Length <= 1)
{
return numbers;
}
var numSpan = numbers.AsSpan<int>();
int mid = numbers.Length / 2;
var first = numSpan[..mid];
var second = numSpan[mid..];
return Merge(first, second).ToArray();
}
private static Span<int> Merge(Span<int> firstNums, Span<int> secondNums)
{
if (firstNums.Length == 0) return secondNums;
if (secondNums.Length == 0) return firstNums;
int mid1 = firstNums.Length / 2;
var first1 = firstNums[..mid1];
var second1 = firstNums[mid1..];
var merged1 = Merge(first1, second1);
int mid2 = secondNums.Length / 2;
var first2 = secondNums[..mid2];
var second2 = secondNums[mid2..];
var merged2 = Merge(first2, second2);
Span<int> final = new int[merged1.Length + merged2.Length];
int i1 = 0;
int i2 = 0;
while (i1 < merged1.Length || i2 < merged2.Length)
{
if (i1 >= merged1.Length)
{
final[i1 + i2] = merged2[i2++];
}
else if (i2 >= merged2.Length)
{
final[i1 + i2] = merged1[i1++];
}
else
{
int num1 = merged1[i1];
int num2 = merged2[i2];
if (Math.Abs(num1) <= Math.Abs(num2))
{
final[i1 + i2] = merged1[i1++];
}
else
{
final[i1 + i2] = merged2[i2++];
}
}
}
return final;
}
}
I created an example based test to confirm that its working and it passes. Ship it!
public class ExampleBasedTesting
{
[Fact]
public void Can_Sort()
{
int[] expected = new int[] { 4, 6, 12, 4324, 5234234 };
int[] input = new int[] { 12, 5234234, 4, 6, 4324 };
int[] sorted = SortExample.MergeSort(input);
Assert.Equal(expected,sorted);
}
}
Just to be sure I created a property based test to make sure it had the properties of a sort. First I created two methods to inspect an array. One checks if each number is smaller than the next and the other checks if they are the same length.
public static class Properties
{
public static bool NumbersInSortedOrder(this int[] numbers)
{
for (int i = 0; i < numbers.Length - 1; i++)
{
if (numbers[i] > numbers[i + 1]) return false;
}
return true;
}
public static bool IsSameLength(this int[] numbers, int[] original)
{
return numbers.Length == original.Length;
}
}
Then I write my first property based test. I created a func that will check if both of the previous properties are true and use the Prop.ForAll<int[]>
function to run random values into the IsSorted func. QuickCheckThrowOnFailure
will throw an error to the output window when it fails.
public class PropertyBased
{
[Fact]
public void Can_Sort()
{
Func<int[], int[], bool> IsSorted = (int[] original, int[] sorted)
=> original.IsSameLength(sorted)
&& sorted.NumbersInSortedOrder();
Prop.ForAll<int[]>(num =>
IsSorted(num, SortExample.MergeSort(num)))
.QuickCheckThrowOnFailure();
}
}
Interesting enough, I get the following error. It fails on the input |-2; -1|
but then tries to shrink the input until it can find what is the smallest input that throws the error.
Message:
System.Exception : Falsifiable, after 3 tests (3 shrinks) (StdGen (1129930099,296782368)):
Original:
[|-2; -1|]
Shrunk:
[|-1; 0|]
It turns out that this line if (Math.Abs(num1) <= Math.Abs(num2))
is sorting them by magnitude without sign which isn't what I expected. After finding this issue I then write another example based test to confirm that my function can handle negative numbers correctly.
[Fact]
public void Can_Sort_negative()
{
int[] expected = new int[] { -4324, 4, 6, 12, 5234234 };
int[] numbers = new int[] { 12, 5234234, 4, 6, -4324 };
int[] sorted = SortExample.MergeSort(numbers);
Assert.Equal(expected, sorted);
}
August 24, 2020
August 12, 2020