Beyond Example-Based Testing in .NET

Steve Love

@IAmSteveLove@mastodon.social
@IAmSteveLove

steve@arventech.com

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

[ 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));
}

SHORT → GUNGE

[ -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);
}

SHORT → STARE

[ 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…

SHORT → STARE

STARE → SHORT

[ 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!

FsCheck

https://fscheck.github.io/
https://fsharpforfunandprofit.com/pbt/

CsCheck

https://github.com/AnthonyLloyd/CsCheck

Hedgehog

https://github.com/hedgehogqa/fsharp-hedgehog

FsUnit

https://fsprojects.github.io/FsUnit/

Fluent Assertions

https://fluentassertions.com/

csts

https://www.arventech.com/ — steve@arventech.com

https://www.penguinrandomhouse.com/authors/2248456/steve-love/

Beyond Example-Based Testing in .NET

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

Guess a word

The game replies…​

Breaking it down

A naive attempt

We can test for that!

A more general idea

We can test for that, too!

Another general test

A more specific test

So far, so good

Finding a counter-example

Breaking it down again

Revisit the code

Precise requirements

A new implementation

How do we test the new version?

Property-based testing

Enter FsCheck

Testing is all about confidence

Filtering

A little harder to test

Some FsCheck terminology

Generating strings of fixed length

Unique matched indices property

Back testing

Generating disjoint strings

Zero matches property

Observation

Testing in a foreign language

Custom generator

If there’s time…​.

Reciprocity

Quite interesting…​

Test switched words

Necessity & sufficiency

Property Based Testing

The game replies…

If there’s time….

Quite interesting…