Introduction to Property Testing in JavaScript

## Abstract

Property testing helps developers express their intent in their tests more clearly while at the same time allowing them to surface more bugs in less time with fewer lines of code.

## Notes

### Slide 1: Introduction to Property Testing in JavaScript

Let's see what property testing looks like in the JavaScript world!

### Slide 2: What is a Property Test?

So what is a property test?

Ordinary example-based tests -- the kind we're all familiar with -- assert that, for a particular input, your program or function produces a particular output.

Property tests allow you to make a stronger assertion: that, for any acceptable input, your program produces an output where some property holds.

A generative property testing framework will repeatedly ensure that your output property holds for every input it generates.

And while a good type system makes property testing a lot easier, we'll be seeing today how it can be done even without type system integration — in JavaScript.

Property tests share a lot in common with contract systems: they both provide runtime facilities for making assertions about the values in your program. But where contracts are only run against the values that end up reaching that part of the program, the property testing framework will run your program or function against all acceptable inputs.

Let's look at some of the assertions we can make in a property test:

* For any list, regardless of the number or kind of its elements, reversing it twice will give you the input list.
* For any list, regardless of the number or kind of its elements, sorting it twice will give you the same result as sorting it once.
* And for any number, adding zero will give you the input number. (this one actually isn't true in JavaScript)

### Slide 3: Prior Art

As far as I'm aware, Haskell's QuickCheck was the first widely-adopted property testing library for a general-purpose programming language.

Clojure's clojure.spec had a big hand in popularising property testing, and now property testing libraries exist for many popular programming languages.

Modern libraries have added more advanced testing features such as StrongCheck's exhaustive and statistical tests.

And the state-of-the-art libraries like Jack are even rethinking their input generation to provide the best possible counterexamples.

### Slide 4: Built-in Generators

The testing library we'll be using is called "gentest". Its built-in generators can be used for generating

* subsets of the integers
* characters
* strings
* and Booleans.

### Slide 5: Sampling a Generator

The way we get values out of a generator is by sampling it.

gentest provides a "sample" function which takes a generator and a number of values to generate. The default is 10.

For built-in generators, later values are more "complex"; integers get larger magnitudes, arrays get longer, and so on.

### Slide 6

Here's a test that uses mocha and gentest together to test a JavaScript serialisation library.

In this very simple test, we are trying to make sure the encoder is fully deterministic in its integer serialisation.

### Slide 7

I've grayed out everything but the important bits. You can see here that we're sampling integers and making sure that calling encode on them more than once never produces different results.

Let's look at another example.

### Slide 8

A common property to test when we have both a function and its inverse is its ability to round-trip.

Here, we're sampling integers and ensuring that, after round-tripping through our serialisation library, we get the same integer back.

### Slide 9: Functions Which Produce Generators

The built-in generators aren't going to be sufficient for most use-cases.

That's why gentest provides us with some functions we can use to create our own generators.

The "elements" function turns any non-empty array into a generator. When sampled, this generator produces random elements from the given array.

"constantly" is simply a shorthand for the single element case.

### Slide 10: Generator Combinators: arrayOf

Some of the generator-producing functions that gentest gives us take other generators as input. We call these functions "combinators".

"arrayOf" takes a generator and gives us a generator of arrays. The elements of the array are sampled from the given generator.

### Slide 11: Generator Combinators: arrayOf

So if we pass "bool" instead of "int", the generated arrays are filled with Booleans instead of integers.

### Slide 12: Generator Combinators: arrayOf

And since this is just a generator like any other, we can pass it to "arrayOf" to create arrays of arrays!

### Slide 13

Back in the tests for our serialisation library, we can use arrayOf to confirm that round-tripping arrays preserves their length.

### Slide 14: Generator Combinators: oneOf/shape

Other combinators include

* "oneOf", which samples at random from the given generators
* "shape", which generates records (the value of each field is sampled from the respective generator)

### Slide 15: Generator Combinators: suchThat

* And "suchThat", which uses the given predicate to filter the values generated by the given generator

The top example ensures that each of the generated arrays is non-empty. The bottom example ensures that each of the generated integers is even.

We need to be careful when using suchThat to construct generators. A predicate that will rarely be true could cause the generator to be very expensive to sample.

It's better to generate values through construction rather than filtering. For this, we need a way to map over generators.

### Slide 16: fmap

"fmap" produces a generator that applies a function to each value generated by the given generator.

The top example shows how we can create an "even integers" generator through construction instead of filtering. "Odds" (below) isn't much different.

### Slide 17

In our test suite, we can use fmap with the absolute value function to make assertions about how our encoder treats non-negative integers.

### Slide 18: bind

But we can't create the non-empty array generator we saw earlier through construction using just fmap. For that, we'll need something more powerful.

"bind" is a function with a similar signature to fmap. Where the function given to fmap would take a generated value and produce an alternative generated value, the function given to bind takes a generated value and produces an alternative generator from which the value to be generated can be sampled. This small change makes bind so powerful, we could define every other function we've seen so far in terms of it.

### Slide 19: bind

This is what our "nonEmptyArrayOf" generator looks like, implemented in terms of bind.

In short, it puts another element on the front of any array generated by the arrayOf generator, ensuring the array will never be empty.

### Slide 20: Areas for Improvement

All of this is great, but it is far from perfect.

My biggest issue is that all values are generated eagerly, before any assertions are made. If JavaScript generator functions were used, values could be generated only as needed.

Shrinking is a common process for automatically minimising a counterexample once one is found. This technique is becoming very common, and some people would expect any generative property testing library to include it.

Some other property testing libraries have integration with the Flow type checker for automatically defining generators for your types.

And there's even academic projects looking into how a counterexample can produce a suggested resolution.

### Slide 21

Here's where the library we've been looking at lives on GitHub.

### Slide 22

And that's all.

Transcript

1. INTRODUCTION TO PROPERTY TESTING IN JAVASCRIPT property testing in plain-old-JS
2. What is a Property Test? • Example-based tests: a particular input produces a particular output • Generative property tests: for all acceptable inputs, the output has some property • Works really well with a good type system • Similar in denotation to contracts • Examples: ◦ Self-inverse: reverse(reverse(list)) == list ◦ Idempotency: sort(sort(list)) == sort(list) ◦ Identity: 0 + number == number
3. Prior Art • Haskell's QuickCheck ◦ Originated, 1999 • clojure.spec ◦ Popularised • PureScript's StrongCheck ◦ exhaustive and statistical tests • PureScript's Jack ◦ shrinking with provenance
4. Built-in Generators import { types as t } from 'gentest'; • t.int • t.int.nonNegative • t.int.nonZero • t.int.positive • t.char • t.string • t.bool
5. Sampling a Generator import { sample, types as t } from 'gentest'; sample(t.int) • [ 1, 0, -2, -2, -3, 3, 4, 2, -1, -1 ] sample(t.bool, 2) • [ true, false ] sample(t.char) • [ 'A', 'y', 'n', 'J', ' ', 'q', 'D', 'M', 'P', '6' ]
6. import { encode, decode } from '../'; import { sample, types as t } from 'gentest'; const SAMPLE_SIZE = 100; describe('integers should always encode to the same value', () => { gentest.sample( t.int , SAMPLE_SIZE).forEach(a => { it(`should deterministically encode ${a}`, () => { expect( encode(a) ).to.eql( encode(a) ); }); }); });
7. import { encode, decode } from '../'; import { sample, types as t } from 'gentest'; const SAMPLE_SIZE = 100; describe('integers should always encode to the same value', () => { gentest.sample( t.int , SAMPLE_SIZE).forEach(a => { it(`should deterministically encode ${a}`, () => { expect( encode(a) ).to.eql( encode(a) ); }); }); });
8. import { encode, decode } from '../'; import { sample, types as t } from 'gentest'; const SAMPLE_SIZE = 100; describe('integers should round-trip', () => { gentest.sample( t.int , SAMPLE_SIZE).forEach(a => { it(`should round-trip ${a}`, () => { expect( decode(encode(a)) ).to.eql( a ); }); }); });
9. Functions Which Produce Generators sample(t.elements(['a', 'b', 'c'])) • [ 'b', 'c', 'b', 'b', 'b', 'a', 'a', 'b', 'b', 'a' ] sample(t.elements([true, false]), 4) • [ true, false, false, false ] sample(t.elements([1])) • [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] sample(t.constantly(1)) • [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
10. Generator Combinators sample(t.arrayOf(t.int)) • [ [], [ -1 ], [ 1, 1 ], [ 0 ], [ 1, 1 ], [ 0 ], [ 2, -2, -1 ], [], [ -3, 2 ], [ -5, -5, 0 ] ]
11. Generator Combinators sample(t.arrayOf(t.bool)) • [ [ true ], [], [ true ], [ false, false ], [ false, true ], [ false, false ], [ false, false ], [ true, false, true ], [ false, false, false ], [ false ] ]
12. Generator Combinators sample(t.arrayOf(t.arrayOf(t.int))) • [ [], [], [ [] ], [ [ 0 ], [ -2 ] ], [ [ -2, -1 ] ], [ [ -1, 3, 0 ], [ -2 ] ], [ [ -2, 3, -2, 1 ] ], [ [], [ 0, 2, 3, -4 ], [ 3, 4, -1 ], [ 3, 3, 4, 3 ] ], [ [ 3 ], [ 0 ], [ 3, -1, -3, -1, 4 ], [ 2, -4 ], [ 0 ] ], [ [ -5, -2, 1 ], [ 4, -4, -2, 4 ], [ -2 ], [] ] ]
13. import { encode, decode } from '../'; import { sample, types as t } from 'gentest'; const SAMPLE_SIZE = 100; describe('arrays should preserve length through a round-trip', () => { gentest.sample( t.arrayOf(t.int) , SAMPLE_SIZE).forEach(a => { it(`should preserve length of ${JSON.stringify(a)}`, () => { expect( decode(encode(a)).length ).to.eql( a.length ); }); }); });
14. Generator Combinators sample(t.oneOf([t.int, t.bool])) • [ true, true, true, -2, -2, false, -1, 2, 3, false ] sample(t.oneOf([t.constantly(0), t.constantly(1)])) • [ 0, 1, 1, 0, 0, 1, 1, 1, 0, 1 ] sample(t.shape({x: t.int, y: t.int}), 6) • [ { x: -1, y: 1 }, { x: -1, y: -1 }, { x: -2, y: -2 }, { x: 1, y: -1 }, { x: 2, y: 0 }, { x: 2, y: 3 } ]
15. Generator Combinators sample(t.suchThat(a => a.length > 0, t.arrayOf(t.bool)), 5) • [ [ false ], [ false ], [ false, false ], [ true ], [ false, true, true ] ] sample(t.suchThat(a => (a & 1) == 0, t.int)) • [ 0, 0, 2, -2, -2, 2, 4, 4 ]
16. fmap sample(t.fmap(a => a * 2, t.int)) • [ 0, 2, 0, 4, -2, 0, 6, 2, -10, 4 ] sample(t.fmap(a => (a * 2) + 1, t.int)) • [ -1, -1, -3, 5, -3, 1, 5, -5, 11, 3 ] sample(t.fmap(a => a.toString(), t.int)) • [ '-1', '0', '2', '0', '2', '2', '-1', '4', '4', '5' ]
17. import { encode, decode } from '../'; import { sample, types as t } from 'gentest'; const SAMPLE_SIZE = 100; function isUint(typeTag) { /* implementation omitted */ } describe('non-negative integers should be encoded as uints', () => { let generator = t.fmap(Math.abs, t.int) ; gentest.sample(generator, SAMPLE_SIZE).forEach(a => { it(`should encode ${a} as a uint`, () => { expect( isUint(encode(a)) ).to.be.true; }); }); });
18. bind fmap :: (a -> b) -> Generator a -> Generator b bind :: (a -> Generator b) -> Generator a -> Generator b
19. bind function cons(head, arrayGen) { return t.fmap(tail => [head].concat(tail), arrayGen); } function nonEmptyArrayOf(gen) { return t.bind(gen, el => cons(el, t.arrayOf(gen))); } sample(nonEmptyArrayOf(t.int), 4) • [ [ 0 ], [ 0, -1 ], [ 1, -2, 0 ], [ -1, 2, -2 ] ]
20. Areas for Improvement • Use ES2015+ features such as generators • Shrinking • Jack-style provenance-based shrinking • Integration with type checker such as Flow • Suggestions for fixing violations
22. That's it! michaelficarra jspedant justgrahamthings