The birth of unexpected-check
Property based testing
-what is it all about?
Property based testings makes statements about a piece of code while being exercised with data taken from a given input space.
Problems that are well suited for property based testing
Functions that have an inverse function
- reverse
- encode/decode
- add/remove
Imagine we wanted to test the encodeURIComponent function.
Example-based testing
expect(encodeURIComponent(''), 'to equal', '')
expect(encodeURIComponent('Hello ATF'), 'to equal', 'Hello%20ATF')
expect(encodeURIComponent('100% cool!'), 'to equal', '100%25%20cool!')
expect(encodeURIComponent('~&?'), 'to equal', '~%26%3F')
Property-based testing
decodeURIComponent(encodeURIComponent(s)) = s
Let's start out by generating some strings:
var Generators = require('chance-generators')
var { natural, string } = new Generators(42)
var strings = string({ length: natural({ max: 50 })})
expect.use(require('unexpected-check'))
expect((string) => {
expect(
decodeURIComponent(encodeURIComponent(string)),
'to equal',
string
)
}, 'to be valid for all', strings)
Functions where it is easier to check the result than computing it
- sorting
- searching
- most transformations
Testing a sorting function
isSorted(sort(a)) = true
function isSortedAscending (array) {
return array.every((x, i) => {
return array.slice(i).every((y) => x <= y)
})
}
Let's make an assertion for checking
that arrays are sorted ascending:
expect.addAssertion('to be sorted ascending', (expect, subject) => {
expect(isSortedAscending(subject), 'to be true')
})
Quicksort sorts arrays of strings correctly
var quicksort = require('quicksort.js');
var { array, string } = new Generators(42)
var stringArrays = array(string)
expect((array) => {
expect(quicksort.asc(array), 'to be sorted ascending')
}, 'to be valid for all', stringArrays)
...and integer arrays:
var { array, integer } = new Generators(42)
var integerArrays = array(
integer({ min: -100, max: 100 })
)
expect((array) => {
expect(quicksort.asc(array), 'to be sorted ascending')
}, 'to be valid for all', integerArrays)
Let's try the same with the build-in sorting function:
expect((array) => {
expect(array.sort(), 'to be sorted ascending')
}, 'to be valid for all', integerArrays)
And it fails!
We get the following error:
Ran 1000 iterations and found 20 errors
counterexample:
Generated input: [ 10, 2 ]
with: n(integer({ min: -100, max: 100 }), natural({ max: 50 }))
expected [ 10, 2 ] to be sorted ascending
Objects that maintains an invariant
- sets
- queues
- balanced search trees
Testing a queue
While adding and removing items, the items should always be retrieved in the same order they where inserted.
Let's generate some operations:
var { array, integer, pickone, shape } = new Generators(42)
var addOperation = shape({
type: 'add',
value: integer
})
var removeOperation = shape({
type: 'remove'
})
var operations = array(
pickone([addOperation, removeOperation])
)
This will generate arrays with the following structure:
[
{ type: 'remove' },
{ type: 'remove' },
{ type: 'add', value: -1331529414344704 },
{ type: 'remove' },
{ type: 'remove' },
{ type: 'remove' },
{ type: 'add', value: -4654237011148800 },
{ type: 'remove' },
{ type: 'add', value: 3344884333281280 },
{ type: 'remove' },
{ type: 'add', value: 1939033726910464 }
]
function execute(queue, operations) {
const added = [], removed = []
operations.forEach(({ type, value }) => {
if (type === 'add' && !queue.isFull()) {
queue.offer(value)
added.push(value)
} else if (type === 'remove' && !queue.isEmpty()) {
removed.push(queue.poll())
}
})
return { added, removed }
}
var CircularQueue = require('circular-queue');
var capacities = natural({ min: 1, max: 50 })
expect((capacity, operations) => {
const queue = new CircularQueue(capacity);
const { added, removed } = execute(queue, operations)
expect(
removed,
'to equal',
added.slice(0, added.length - queue.size)
)
}, 'to be valid for all', capacities, operations)
Reuse generated operations:
expect(function (capacity, operations) {
const queue = new CircularQueue(capacity);
operations.forEach(({ type, value }) => {
const currentSize = queue.size
if (type === 'add' && !queue.isFull()) {
queue.offer(value)
expect(queue.size, 'to equal', currentSize + 1)
} else if (type === 'remove' && !queue.isEmpty()) {
queue.poll()
expect(queue.size, 'to equal', currentSize - 1)
}
})
}, 'to be valid for all', capacities, operations)
Input shrinking
var arrayEqual = require('array-equal')
function containsSubArray(array, subArray) {
return array.some((v, i) => (
arrayEqual(array.slice(i, i + subArray.length), subArray)
))
}
var { array, integer, natural } = new Generators(314)
var lengths = natural({ max: 100 })
var arrays = array(integer, lengths)
var offsets = natural({ max: 100 })
expect((array, offset, length) => {
const subArray = array.slice(offset, offset + length)
expect(
containsSubArray, 'when called with', [array, subArray],
'to be true'
)
}, 'to be valid for all', arrays, offsets, lengths)
Ran 14 iterations and found 14 errors
counterexample:
Generated input: [], 0, 0
with: n(integer, natural({ max: 100 })), natural({ max: 100 }), natural({ max: 100 })
expected
function containsSubArray(array, subArray) {
return array.some((v, i) => (
arrayEqual(array.slice(i, i + subArray.length), subArray)
))
}
when called with [], [] to be true
expected false to be true
The assertion finds an error in the first iteration and shrinks it to the optimal output in 14 iterations. Here are the last iterations:
...
input([], 3, 3) => containsSubArray([], [].slice(3, 3 + 3)) === true
input([], 2, 3) => containsSubArray([], [].slice(2, 2 + 3)) === true
input([], 1, 1) => containsSubArray([], [].slice(1, 1 + 1)) === true
input([], 1, 1) => containsSubArray([], [].slice(1, 1 + 1)) === true
input([], 1, 1) => containsSubArray([], [].slice(1, 1 + 1)) === true
input([], 1, 0) => containsSubArray([], [].slice(1, 1 + 0)) === true
input([], 1, 0) => containsSubArray([], [].slice(1, 1 + 0)) === true
input([], 1, 0) => containsSubArray([], [].slice(1, 1 + 0)) === true
input([], 0, 0) => containsSubArray([], [].slice(0, 0 + 0)) === true
Shrinking a number:
var { integer } = new Generators(42)
var numbers = integer({ min: -100, max: 100 })
var shrunkenGenerator = numbers.shrink(22)
// will return: integer({ min: 0, max: 22 })
expect(shrunkenGenerator(), 'to be within', 0, 22)
var shrunkenGenerator = numbers.shrink(-33)
// will return: integer({ min: -33, max: 0 })
expect(shrunkenGenerator(), 'to be within', -33, 0)
The shrunken values will converge towards zero.
Shrinking an array:
var { array, natural } = new Generators(42)
var arrays = array(natural({ max: 100 }), natural({ min: 2, max: 100 }))
var shrunkenGenerator = arrays.shrink([79, 25, 42, 94, 27])
// will return: pickset([79, 25, 42, 94, 27], natural({ min: 2, max: 5 })
expect(shrunkenGenerator(), 'to equal', [ 94, 27, 79 ])
expect(shrunkenGenerator(), 'to equal', [ 42, 79, 94, 25 ])
expect(shrunkenGenerator(), 'to equal', [ 42, 27 ])
The shrunken arrays will converge towards the smallest possible array.
What will the future bring?
Improved shrinking
Shrinking nested generators
The sorting failure we saw earlier: [-45,-95]
should have been: [10,2].
Done
More generators
- json-schema-faker
- immutable-js generators
- Generator for React prop types
Support asynchronous assertions
Useful for testing for race conditions with random executions plans.
Done