Beyond Example-Based Testing in .NET

Steve Love


@IAmSteveLove@mastodon.social
@IAmSteveLove


Introduction to property-based testing in (mostly) C#

  • Example-based testing

  • Generalization

  • Triangulation

  • Property-based testing

  • Generating data

  • A bit of the other

Guess a word

STARE

The game replies…​

STARE

Breaking it down

SHORT

STARE

0 → 0 : S
1 → 4 : T
2 → x : A
3 → 3 : R
4 → x : E


[ 0, 4, -1, 3, -1 ]

A naive attempt

public static int[] Match(string word, string guess) 
{
    return guess.Select((ch, idx) 
            => ch == word[idx] ? idx    // prefer exact match 
                : word.IndexOf(ch))     // returns -1 if not found
        .ToArray();        
}

We can test for that!

[Test]
public void Simple_eg_test()
{
    var set = "SHORT";
    var guess = "STARE";
    
    var result = Match(set, guess);
    
    int[] expected = [0, 4, -1, 3, -1];
    
    Assert.That(result, Is.EqualTo(expected));
}

A more general idea

Matching a string with itself should always produce the same output

a.k.a. Reflexivity

SHORT

SHORT

[ 0, 1, 2, 3, 4 ]

We can test for that, too!

[Test]
public void A_string_matches_itself_exactly()
{
    string word = "ANYOLDSTRING";
    var result = Match(word, word);
    
    var expected = Enumerable.Range(0, word.Length);
    
    Assert.That(result, Is.EqualTo(expected));
}

Another general test

[TestCase("SHORT", "GUNGE")]
[TestCase("GUNGE", "SHORT")]
public void Disjoint_strings_have_no_matches(string set, string guess)
{
    var result = Match(set, guess);
    
    var expected = Enumerable.Repeat(-1, set.Length);   // every element is -1
    
    Assert.That(result, Is.EqualTo(expected));
}

SHORTGUNGE

[ -1, -1, -1, -1, -1 ]

A more specific test

Each matched letter is matched only once

[TestCase("SHORT", "STARE")]
[TestCase("STARE", "SHORT")]
public void Matched_indices_are_unique(string left, string right)
{
    var result = Match(left, right);
    
    var matches = result.Where(i => i != -1).ToArray();
    
    Assert.That(matches, Is.Unique);
}

SHORTSTARE

[ 0, 4, -1, 3, -1 ]

So far, so good

  • Reflexivity

  • no matches

  • uniqueness

Hypothesis

These are properties that should apply to any arbitrary string with respect to the Match method

Finding a counter-example

[TestCase("GRASP", "STASH")]
[TestCase("SHORT", "STARE")]
[TestCase("STARE", "SHORT")]
public void Matched_indices_are_unique(string left, string right)
{
    var result = Match(left, right);
    
    var matches = result.Where(i => i != -1).ToArray();
    
    Assert.That(matches, Is.Unique);
}
    Failed Matched_indices_are_unique("GRASP","STASH") [103 ms]
    Error Message:
        Assert.That(matches, Is.Unique)
        Expected: all items unique
        But was:  < 3, 2, 3 >
        Not unique items: < 3 >

Breaking it down again

GRASP

STASH

Should have been:

[ -1, -1, 2, 3, -1 ]

But was:

[ 3, -1, 2, 3, -1 ]

Revisit the code

public static int[] Match(string word, string guess) 
{
    return guess.Select((ch, idx) 
            => ch == word[idx] ? idx    // prefer exact match 
                : word.IndexOf(ch))     // returns -1 if not found
        .ToArray();        
}

GRASP

STASH

Precise requirements

A letter in the set word should be matched by only one letter in the guess, with an exact match being preferred

A new implementation

public static int[] Match(string word, string guess) 
{
    var found = Enumerable.Range(0, word.Length)
        .Select(idx => word[idx] == guess[idx] ? idx : -1)
        .ToArray();
    
    foreach(var i in Enumerable.Range(0, word.Length))
    {
        if(found[i] == -1)
        {
            found[i] = Enumerable.Range(0, word.Length)
                .FirstOrDefault(idx => word[idx] == guess[i] 
                       && !found.Contains(idx), -1);
        }
    }

    return found;
}

How do we test the new version?

Our example-based tests now pass…​

…​but we identified properties that should hold for all strings

Property-based testing

Define properties that should hold for all inputs…​
…​which may be (often are) generated randomly

  • Identifies counter-examples that don’t hold

  • Exposes corner-cases you haven’t thought of

Enter FsCheck

Property-based testing for .NET

Property

a function that tests an assumption.

  • a predicate—​a false return indicates a falsifiable case

  • a unit (void) method—​thrown exception is a falsifiable case

Testing is all about confidence

[FsCheck.NUnit.Property]
public void Any_string_matches_itself_exactly(string word)
{
    var result = Match(word, word);

    Assert.That(result, Is.EqualTo(Enumerable.Range(0, word.Length)));
}
        Falsifiable, after 32 tests (0 shrinks) (StdGen (1595582682,297278030)):
        Original:
        <null>
        with exception:
        System.NullReferenceException: 
            Object reference not set to an instance of an object.

Filtering

[FsCheck.NUnit.Property]
public void Any_string_matches_itself_exactly(NonEmptyString word)
{
    var result = Match(word.Get, word.Get);
    
    var exp = Enumerable.Range(0, word.Get.Length);
    Assert.That(result, Is.EqualTo(exp));
}

A little harder to test

Uniqueness of matched indices

Requires guess to be at least as long as the set word (ideally they are equal length).

Disjoint strings

Requires two strings with no matching characters.

Some FsCheck terminology

  • NUnit property throws exception rather than returning false

    • Arbitrary<T> — supplies data to a property parameter

    • Gen<T> — generate instances (usually random) of T

  • used by Arbitrary<T> along with a shrinker

Generating strings of fixed length

class ArbitraryStrings
{
    private static Gen<string> StringOfLength(int n)
        => Arb.Default.Char().Generator     // 'char' gen as shipped with FsCheck
            .Where(char.IsLetterOrDigit)    // for readability
            .ArrayOf(n)                     // fixed size array of char
            .Select(string.Concat);         // create a string
    

    public static Arbitrary<string> FixedLengthString()
        => StringOfLength(15).ToArbitrary();
}

Unique matched indices property

[FsCheck.NUnit.Property(Arbitrary = [ typeof(ArbitraryStrings) ])]
public void Matched_indices_are_unique(string left, string right)
{
    var result = Match(left, right);
    
    var matches = result.Where(i => i != -1).ToArray();
    
    Assert.That(matches, Is.Unique);
}

Back testing

Our original implementation fails this test:

    Falsifiable, after 4 tests (0 shrinks) (StdGen (1105325589,297278101)):
    Original:
    ("yW606jYvi8Bd7P2", "Z7QjVj4oJcycyct")
    with exception:
    NUnit.Framework.AssertionException:   Assert.That(matches, Is.Unique)
        Expected: all items unique
        But was:  < 12, 5, 5, 0, 0 >
        Not unique items: < 5, 0 >

We can use this output to write a concrete example-based test!

Generating disjoint strings

public static Arbitrary<(string, string)> DisjointStringPair()
    => StringOfLength(15).Two()
        .Where(pair => !pair.Item1.Intersect(pair.Item2).Any())
        .Select(pair => (pair.Item1, pair.Item2))
        .ToArbitrary();

Filtering like this can be expensive.

Optimizing input data may be more efficient.

Zero matches property

[FsCheck.NUnit.Property(Arbitrary = [ typeof(ArbitraryStrings) ])]
public void Disjoint_strings_have_no_matched_indices((string, string) pair)
{
    var (left, right) = pair;
    var result = Match(left, right).Where(i => i != -1);
    
    result.Should().BeEmpty();
}

or…​

Assert.That(result, Is.Empty);

Observation

We discovered our original counter-example manually, but the property based test for unique matched indices would have found it.

Any other properties?

Testing in a foreign language

module WordTests =
    
    [< Property >]
    let ``Any string matches itself exactly``(word: NonEmptyString) =
        Match(word.Get, word.Get)
        |> should equalSeq [| 0..word.Get.Length - 1 |]

    [< Property(Arbitrary=[| typeof<ArbitraryStrings> |]) >]
    let ``Matched indices are unique``(left: string, right: string) =
        Match(left, right)
        |> Array.filter(fun i -> i <> -1)
        |> should be unique

Custom generator

type ArbitraryStrings =
    static member StringOfLength n =
       Arb.generate<char>
       |> Gen.filter Char.IsLetterOrDigit
       |> Gen.arrayOfLength n
       |> Gen.map String.Concat

    static member FixedLengthString =
        ArbitraryStrings.StringOfLength(15)
        |> Arb.fromGen
class ArbitraryStrings
{
    private static Gen<string> StringOfLength(int n)
        => Arb.Default.Char().Generator     // 'char' gen as shipped with FsCheck
            .Where(char.IsLetterOrDigit)    // for readability
            .ArrayOf(n)                     // fixed size array of char
            .Select(string.Concat);         // create a string
    

    public static Arbitrary<string> FixedLengthString()
        => StringOfLength(15).ToArbitrary();
}

If there’s time…​.

One more interesting property…​

Reciprocity

SHORT

STARE

[ 0, 4, -1, 3, -1 ]

STARE

SHORT

[ 0, -1, -1, 3, 1 ]

Quite interesting…​

SHORTSTARE

STARESHORT

[ 0, 4, -1, 3, -1 ]

[ 0, -1, -1, 3, 1 ]

(0, 0)
(1, 4)
(3, 3)

(0, 0)
(3, 3)
(4, 1)

Hypothesis

it’s true for all matches between strings of the same length

Test switched words

[< Property(Arbitrary=[| typeof<ArbitraryStrings> |]) >]
let ``Matched indices roundtrip in switched words``(left: string, right: string) =
    let orig = Match(left, right) |> Seq.ofArray
    let rev = Match(right, left) |> Seq.ofArray
    
    let inOrder = Seq.zip orig { 0..left.Length - 1 }
                |> Seq.where(fun(x, y) -> x <> -1)
                
    let switched = Seq.zip rev { 0..right.Length - 1 } 
                |> Seq.where(fun(x, y) -> x <> -1)
                |> Seq.map(fun(x, y) -> y, x)

    inOrder |> should equivalent switched
inOrder:  (0, 0), (1, 4), (3, 3)
switched: (0, 0), (3, 3), (4, 1)

Necessity & sufficiency

Reflexive, no matches, unique indices

  • Definitely all necessary

    • the latter identified a counter-example in the original algorithm

  • How to determine sufficiency?

Property Based Testing

Finding all those edge cases you forgot!