Steve Love
@IAmSteveLove@mastodon.social
@IAmSteveLove
Example-based testing
Generalization
Triangulation
Property-based testing
Generating data
A bit of the other
STARE
STARE
SHORT
STARE
0 → 0 : S
1 → 4 : T
2 → x : A
3 → 3 : R
4 → x : E
[ 0, 4, -1, 3, -1 ]
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();
}
[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));
}
Matching a string with itself should always produce the same output
a.k.a. Reflexivity
SHORT
SHORT
[ 0, 1, 2, 3, 4 ]
[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));
}
[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 |
|
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 |
|
Reflexivity
no matches
uniqueness
These are properties that should apply to any arbitrary string with respect to the
Match
method
[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 >
GRASP
STASH
Should have been:
[ -1, -1, 2, 3, -1 ]
But was:
[ 3, -1, 2, 3, -1 ]
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
A letter in the set word should be matched by only one letter in the guess, with an exact match being preferred
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;
}
Our example-based tests now pass…
…but we identified properties that should hold for all strings
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
Property-based testing for .NET
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
[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.
[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));
}
Requires guess to be at least as long as the set word (ideally they are equal length).
Requires two strings with no matching characters.
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
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();
}
[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);
}
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!
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.
[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);
We discovered our original counter-example manually, but the property based test for unique matched indices would have found it.
Any other properties?
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
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();
}
One more interesting property…
SHORT
STARE
[ 0, 4, -1, 3, -1 ]
STARE
SHORT
[ 0, -1, -1, 3, 1 ]
SHORT → STARE | STARE → SHORT |
|
|
(0, 0) | (0, 0) |
it’s true for all matches between strings of the same length
[< 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)
Reflexive, no matches, unique indices
Definitely all necessary
the latter identified a counter-example in the original algorithm
How to determine sufficiency?
Finding all those edge cases you forgot!