Upgrade to Pro — share decks privately, control downloads, hide ads and more …

The Magic of Generative Testing: Fast-Check in ...

The Magic of Generative Testing: Fast-Check in JavaScript

(Video at https://youtu.be/a2J_FSkxWKo)

Generative testing (aka property testing), popularized by the Haskell library QuickCheck, is a technique of:

- specifying invariant laws your code expects to exhibit
- generating random inputs to verify the laws
- simplifying failures to find error boundaries
- providing replay mechanisms for easy debugging

In this BrooklynJS talk, I show the motivations for and basics of property testing in JavaScript, via the library fast-check.

Gabriel Lebec

June 20, 2019
Tweet

More Decks by Gabriel Lebec

Other Decks in Programming

Transcript

  1. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) })
  2. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) }) ✅ Passes!
  3. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) })
  4. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) }) • nums => [1, 2, 3] • nums => [nums[1], nums[0], nums[2]] • nums => realSort([ ...new Set(nums)]) • nums => realSort([nums[0], ...nums.slice(1)]) • nums => realSort(nums.map(n => Math.round(n)) • nums => nums.sort() All these pass…
  5. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) }) So what do we do?
  6. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) it('transforms `[2, 3, 1]` to `[1, 2, 3]`', () => { expect(sort([2, 3, 1])).toEqual([1, 2, 3]) }) })
  7. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) it('transforms `[2, 3, 1]` to `[1, 2, 3]`', () => { expect(sort([2, 3, 1])).toEqual([1, 2, 3]) }) it('transforms `[1.5, -4]` to `[-4, 1.5]`', () => { expect(sort([1.5, -4])).toEqual([-4, 1.5]) }) })
  8. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) it('transforms `[2, 3, 1]` to `[1, 2, 3]`', () => { expect(sort([2, 3, 1])).toEqual([1, 2, 3]) }) it('transforms `[1.5, -4]` to `[-4, 1.5]`', () => { expect(sort([1.5, -4])).toEqual([-4, 1.5]) }) it('transforms `[]` to `[]`', () => { expect(sort([])).toEqual([]) }) })
  9. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) it('transforms `[2, 3, 1]` to `[1, 2, 3]`', () => { expect(sort([2, 3, 1])).toEqual([1, 2, 3]) }) it('transforms `[1.5, -4]` to `[-4, 1.5]`', () => { expect(sort([1.5, -4])).toEqual([-4, 1.5]) }) it('transforms `[]` to `[]`', () => { expect(sort([])).toEqual([]) }) it('transforms `[1, 1, 1, 1, 1]` to `[1, 1, 1, 1, 1]`', () => { expect(sort([1, 1, 1, 1, 1])).toEqual([1, 1, 1, 1, 1]) }) it('transforms `[999, 500, 2]` to `[999. 500, 2]`', () => { expect(sort([999, 500, 2])).toEqual([2, 500, 999]) }) it('transforms `[0x821, 1.3e5]` to `[0x821, 1.3e5]`', () => { expect(sort([0x821, 1.3e5])).toEqual([0x821, 1.3e5]) }) it('transforms `[0]` to `[0]`', () => { expect(sort([0])).toEqual([0]) }) it('transforms `[-0]` to `[-0]`', () => { expect(sort([-0])).toEqual([-0]) }) it('transforms `[1, 2, 1, 2]` to `[1, 1, 2, 2]`', () => { expect(sort([1, 2, 1, 2])).toEqual([1, 1, 2, 2]) }) it('transforms `[10, 11, 12, 9001, -1]` to `[-1, 10, 11, 12, 9001]`', () => { expect(sort([10, 11, 12, 9001, -1])).toEqual([-1, 10, 11, 12, 9001]) }) it('transforms `[0.9999999, 1, 0.9999999]` to `[0.9999999, 0.9999999, 1]`', () => { expect(sort([0.9999999, 1, 0.9999999])).toEqual([0.9999999, 0.9999999, 1])
  10. ERROR: cannot read
 'name' of undefined 100% coverage Build succeeded

    Tests passed As humans, we focus
 on the "happy path"
  11. What are we saying in this test? What is the

    *point*? describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1, 2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) })
  12. describe('`sort`', () => { it('transforms `[2, 1, 3]` to `[1,

    2, 3]`', () => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) }) Is it this particular array we care about?
  13. describe('`sort`', () => { it('results in an ordered array', ()

    => { expect(sort([2, 1, 3])).toEqual([1, 2, 3]) }) }) …or is it this particular *law*? aka "property" (of sorting)? aka "invariant" (behavior, regardless of input)
  14. • Sorting a list of nums results in an ordered

    list • Sorting a sorted list is a no-op (idempotence) • Sorting neither adds, removes, nor changes elements ⚖
  15. ⚖ // :: [Number] -> Bool function sortOrders (arr) {

    const sorted = sort(arr) for (let i = 0; i < arr.length - 1; i ++) { if (arr[i] > arr[i + 1]) return false } return true } a predicate function (returns Bool) aka property check we've explicitly named our law
  16. // :: (Number) -> Number function randomInt (limit = 1)

    { return Math.floor(Math.random() * limit) } // :: () -> [Number] function randomArr () { return Array.from( { length: randomInt(LIMIT_LEN) }, () => randomInt(LIMIT_NUM) ) } ad-hoc data generators
  17. describe('`sort`', () => { it('outputs ordered arrays', () => {

    for (let t = 0; t < LIMIT_TESTS; t ++) { expect(isOrdered(sort(randomArr()))).toBe(true) } }) }) generate and verify many random cases ✅ Passes!
  18. describe('`sort`', () => { it('outputs ordered arrays', () => {

    for (let t = 0; t < LIMIT_TESTS; t ++) { expect(isOrdered(sort(randomArr()))).toBe(true) } }) }) …but what happens if it fails?
  19. FAIL src/01-sort.spec.ts • `sort` › outputs ordered arrays expect(received).toBe(expected) //

    Object.is equality Expected: true Received: false which input array failed? what was the output from sort? …let's just add a console.log…
  20. …re-ran, failed again… but why does THIS array fail? FAIL

    `sort` › outputs ordered arrays Input: [93, 2, 0, 1, 90101, 29, 350, 301, 620] Output: [0, 1, 2, 29, 301, 250, 620, 90101, 93] Expected: true Received: false
  21. laborious ad-hoc error-prone generators (did you notice we never generated

    negative ints?) random array generator maybe repeated empty arr non-instructive failure (input? output?) irreproducible failing cases may be unnecessarily large
  22. ⚖ specify law (predicate function) ⏳ support for async predicates

    generates progressively bigger random inputs . common edge cases baked-in failing cases progressively "shrunk" (simplified) ⚠ finds error boundary deterministically pseudorandom can specify seed
  23. import * as fc from 'fast-check' describe('`sort`', () => {

    it('outputs ordered arrays', () => { fc.assert( fc.property( fc.array(fc.integer()), (nums) => isOrdered(sort(nums)) ) ) }) })
  24. import * as fc from 'fast-check' describe('`sort`', () => {

    it('outputs ordered arrays', () => { fc.assert( fc.property( fc.array(fc.integer()), (nums) => isOrdered(sort(nums)) ) ) }) }) a fast-check "property" instance, which…
  25. import * as fc from 'fast-check' describe('`sort`', () => {

    it('outputs ordered arrays', () => { fc.assert( fc.property( fc.array(fc.integer()), (nums) => isOrdered(sort(nums)) ) ) }) }) generates arrays of ints, and…
  26. import * as fc from 'fast-check' describe('`sort`', () => {

    it('outputs ordered arrays', () => { fc.assert( fc.property( fc.array(fc.integer()), (nums) => isOrdered(sort(nums)) ) ) }) }) feeds them to this predicate
  27. import * as fc from 'fast-check' describe('`sort`', () => {

    it('outputs ordered arrays', () => { fc.assert( fc.property( fc.array(fc.integer()), (nums) => isOrdered(sort(nums)) ) ) }) }) run many times, and throw upon failure…
  28. FAIL src/01-sort.spec.ts `sort` ✕ outputs ordered arrays (9ms) • `sort`

    › outputs ordered arrays Property failed after 4 tests { seed: 1213330267, path: "3:1:3:2:3:2:3:2", endOnFailure: true } Counterexample: [[-1,-2]] Shrunk 7 time(s) but if it fails, it fails elegantly
  29. FAIL src/01-sort.spec.ts `sort` ✕ outputs ordered arrays (9ms) • `sort`

    › outputs ordered arrays Property failed after 4 tests { seed: 1213330267, path: "3:1:3:2:3:2:3:2", endOnFailure: true } Counterexample: [[-1,-2]] Shrunk 7 time(s) ran until failure (or configured limit)
  30. FAIL src/01-sort.spec.ts `sort` ✕ outputs ordered arrays (9ms) • `sort`

    › outputs ordered arrays Property failed after 4 tests { seed: 1213330267, path: "3:1:3:2:3:2:3:2", endOnFailure: true } Counterexample: [[-1,-2]] Shrunk 7 time(s) failure was simplified 7 times
  31. FAIL src/01-sort.spec.ts `sort` ✕ outputs ordered arrays (9ms) • `sort`

    › outputs ordered arrays Property failed after 4 tests { seed: 1213330267, path: "3:1:3:2:3:2:3:2", endOnFailure: true } Counterexample: [[-1,-2]] Shrunk 7 time(s) minimal edge case found
  32. FAIL src/01-sort.spec.ts `sort` ✕ outputs ordered arrays (9ms) • `sort`

    › outputs ordered arrays Property failed after 4 tests { seed: 1213330267, path: "3:1:3:2:3:2:3:2", endOnFailure: true } Counterexample: [[-1,-2]] Shrunk 7 time(s) can reproduce at will
  33. test assertion takes an optional config import * as fc

    from 'fast-check' describe('`sort`', () => { it('outputs ordered arrays', () => { fc.assert( fc.property( fc.array(fc.integer()), (nums) => isOrdered(sort(nums)) ), ) }) })
  34. import * as fc from 'fast-check' describe('`sort`', () => {

    it('outputs ordered arrays', () => { fc.assert( fc.property( fc.array(fc.integer()), (nums) => isOrdered(sort(nums)) ), { seed: 1213330267, verbose: true } ) }) }) can specify PRNG seed
  35. • `sort` › outputs ordered arrays Property failed after 4

    tests { seed: 1213330267, path: "3:1:3:2:3:2:3:2", endOnFailure: true } Counterexample: [[-1,-2]] Shrunk 7 time(s) Encountered failures were: - [[-10,-1823440029,-3,-8,109548166,22,236538465]] - [[-1823440029,-3,-8,22]] - [[-1823440029,-2,-8,22]] - [[-1,-1823440029,-8,22]] - [[-1,-8,22]] - [[-1,-8]] - [[-1,-4]] - [[-1,-2]] debug same code path, and/or see how minimal case was found
  36. describe("(one of) De Morgans Laws", () => { test('not (P

    and Q) <=> (not P) or (not Q)', () => { fc.assert(fc.property( fc.boolean(), fc.boolean(), (p, q) => { return !(p && q) === !p || !q } )) }) }) can easily request multiple arbitraries (generator + shrinker = "arbitrary")
  37. describe('`Array#filter`', () => { it('always results in a same-or-shorter-length arr',

    () => { fc.assert(fc.property( fc.array(fc.anything()), fc.func(fc.boolean()), (arr, pred) => { return arr.filter(pred).length <= arr.length } )) }) }) built-in arbitraries compose beautifully ("combinator pattern") array of any vals function returning bools
  38. describe('`isOdd`', () => { it('correctly identifies odd integers', () =>

    { fc.assert(fc.property( fc.integer().map(n => n * 2 + 1), isOdd )) }) }) function isOdd (num) { return num % 2 === 1 } a new arbitrary which generates odd integers can transform arbitraries via functional techniques like `map` and `filter` (fails on -1!)
  39. tons more! size minima / maxima ✍ special strings (ascii,

    unicode, ipv4, json) custom generators from scratch
  40. Complementary to other strats Unit tests for specific important cases

    Fuzzers for robustness against garbage input Prop tests for confidence that API contract holds <- property-based testing image credit: Nicolas Dubien
  41. Plain JS -> zero-effort integration No special plugins, matchers, or

    bindings needed Drop into Mocha, AVA, Jest, Tape, etc. Insert assertions from Chai, Sinon, Supertest, etc.
  42. THANKS! - https: //speakerdeck.com/glebec/the-magic-of-generative-testing - https: //dev.to/glebec/property-testing-with-jsverify-part-i-3one - https: //

    www.cs.tufts.edu/~nr/cs257/archive/john-hughes/quick.pdf - YouTube: "Don't Write Tests"! (John Hughes) - https: //github.com/dubzzz/fast-check