Property based testing in JavaScript with jsverify

property.md

Property based testing

#jsverify #quickcheck #freaklies @phadej @futurice

---

Prelude

Who is familiar with Haskell

at least the syntax?

---

Learn Haskell

at least the syntax.

---

Act I: Sort example

We are going to write sort function!

---

TDD

assert $ sort [] == []
-- HACK HACK
assert $ sort [1] == [1]
-- HACK HACK
assert $ sort [2] == [2]
-- HACK HACK
assert $ sort [1, 2, 3] == [1, 2, 3]
-- HACK HACK
assert $ sort [3, 2, 1] == [1, 2, 3]

---

Refactor repetitive tests!

examples :: [([Integer], [Integer])] -- list of pairs of lists of integers!
examples =
  [ ([], [])
  , ([1], [1])
  , ([2], [2])
  , ([1,2,3], [1,2,3])
  , ([3,2,1], [1,2,3])
  ]

test = do
  forM_ examples $ \(input, expected) -> assert $ sort input == expected

---

Can we do better?

Yes we can! kind of.

---

Properties!

Let us define sort properties we care about

• sort doesn't change the length of the list: ∀ l : list, length (sort l) ≡ length l

• result of sort is sorted: ∀ l : list, isSorted (sort l)

  isSorted :: Ord a => [a] -> Bool
  isSorted []       = True
  isSorted [x]      = True
  isSorted (x:y:zs) = x <= y && isSorted (y:zs)

  NOTE here we have a problem as we probably have to test isSorted too. Let's assume isSorted is correct though.

  *In fact I failed to write this correctly first time. There wes just less than, <, not less than or equal to, <=.

---

• every element of input list is in result list: ∀ l : list, x ∈ l → x ∈ sort l

  • or more precisely sort l is a permutation of l
  • the length-property is prerequisite for this!

  isPermutation :: Eq a => [a] -> [a] -> Bool
  isPermutation [] []     = True
  isPermutation [] [_]    = False
  isPermutation [_] []    = False
  isPermutation (x:xs) ys = x `elem` ys && isPermutation xs (deleteFirst x ys)
    where deleteFirst _ []                 = []
          deleteFirst x (y:ys) | x == y    = ys
                               | otherwise = y : deleteFirst x ys 

---

QuickCheck properties!

lengthProp :: Ord a => [a] -> Bool
lengthProp ls = length (sort ls) == length ls

sortedProp :: Ord a => [a] -> Bool
sortedProp ls = isSorted (sort ls)

permutationProp :: Ord a => [a] -> Bool
permutationProp ls = isPermutation ls (sort ls)

main :: IO ()
main = do
  quickCheck (lengthProp :: [Int] -> Bool)
  quickCheck (sortedProp :: [Int] -> Bool)
  quickCheck (permutationProp :: [Int] -> Bool)

---

Interlude

Ok. it's very hard to sell the idea of property based testing. It's definitely not as easy as writing down few examples. Yet it makes you think about the problem. In sort example the process even gives you a naive solution: Take nextPermutation of the list, until it isSorted. Sometimes naive implementation is a good starting point, the model against which you can test better but more complex implementations:

sortEquivProp :: Ord a => [a] -> Bool
sortEquivProp ls = naiveSort ls == betterSort ls

---

Act II: JavaScript: jsverify

We can do quite the same in JavaScript with jsverify

---

isSorted

function isSorted(arr) {
  if (arr.length === 0) { return true; }
  var iterEnd = arr.length - 1;
  for (var i = 0; i < iterEnd; i++) {
    if (!(arr[i] <= arr[i + 1])) {
      return false;
    }
  }
  return true;
}

Ok, i believe this might be correct.

---

isPermutation

function isEqPermutation(a, b) {
  var len = a.length;
  if (b.length !== len) { return false; }

  var removed = b.map(function () { return false; });
  outer: for (var i = 0; i < len; i++) {
    for (var j = 0; j < len; j++) {
      if (a[i] === b[j] && removed[j] === false) {
        b[j] = true;
        continue outer;
      }
    }

    return false;
  }

  return true;
}

No, i don't believe this works

---

isPermutation test:

var shuffleProperty = jsc.forall("array number", function (arr) {
  // TODO: add shuffle to jsc tools
  // this is not repeatable test
  return isEqPermutation(_.shuffle(arr), arr);
});

jsc.assert(shuffleProperty, jscOptions);

OK, passed 100 tests

... but it does!

---

sort tests:

var lengthProperty = jsc.forall("array number", function (arr) {
  return _.sortBy(arr).length === arr.length;
});

var sortedProperty = jsc.forall("array number", function (arr) {
  return isSorted(_.sortBy(arr));
});

var permutationProperty = jsc.forall("array number", function (arr) {
  return isEqPermutation(arr, _.sortBy(arr));
});


jsc.assert(lengthProperty, jscOptions);
jsc.assert(sortedProperty, jscOptions);
jsc.assert(permutationProperty, jscOptions);

OK, passed 100 tests
OK, passed 100 tests
OK, passed 100 tests

---

Climax

Lodash's _.sortBy seems to be correct. \o/.

---

Act III: an unexpected twist – Rx.js

Erik Meijer is dual of itself. Co-Erik is Erik. This is because Erik is (almost) hue-invariant

---

Enumerable

var exampleArray = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];

var id = function (x) {
  return x;
}
var flatMap = function (arr, f) {
  return _.chain(arr).map(f).flatten(true).value();
}

console.log(flatMap(exampleArray, id));

[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

---

Dual: Observable

Rx.Observable.fromArray : Enumerable a → Observable a

function runObservable(arr, f) {
  var deferred = q.defer();
  var acc = [];

  var obs = Rx.Observable.fromArray(arr);

  obs
  .flatMap(f)
  .subscribe(
    function (x) {
      acc.push(x);
    },
    function () {},
    function () {
      deferred.resolve(acc.slice());
    });

  return deferred.promise;
}

runObservable(exampleArray, Rx.Observable.fromArray).then(console.log);

Here we have to use promises, because jsverify doesn't know about Rx. Promises are simpler. Note: You can use schedulers with Rx

---

Climax

jsverify works with promises too!

var enumerableObservableDualProp = jsc.forall("array (array nat)", function (arr) {
  var e = flatMap(arr, id);
  var op = runObservable(arr, Rx.Observable.fromArray);

  return op.then(function (o) {
    return _.isEqual(o, e);
  });
});

jsc.assert(enumerableObservableDualProp, jscOptions);

Failed after 2 tests and 10 shrinks. rngState: 035fda03e976b8412c; Counterexample: [[0, 0, 0], [1]];  [ [ [ 0, 0, 0 ], [ 1 ] ] ]

---

Resolution

runObservable([[0, 0, 0], [1]], Rx.Observable.fromArray).then(console.log);

[ 0, 0, 1, 0 ]

Is this a bug or not? have to RTFM.

The answer: we want .concatMap, not .flatMap. IMHO .flatMap should be named as .mergeMap.

---

The End

Questions?

• Q: What generators jsverify supports out of the box?

• A: Basic primitive types, arrays of everything, maps, json values...

• Q: And functions?

• A: Yes and functions. But TODO I have to make it possible to pass equality relation to jsc.fn generator.

• Q: What I can test with jsverify?

• A: Properties: Invariants, verifying against the model or reference implementation...

• Q: How do I test side-effects?

• A: In very the same way, as you'd test them otherwise. jsverify helps you with generating inputs, not actual tests.

• Q: What development happened lately to jsverify?

• A: I added small DSL for types so you can write "array (array nat)" in place of jsc.array(jsc.array(jsc.nat)). The difference is small, but strings stand out better.

• Q: And you used jsverify to verify parser is correct?

• A: No actually, I used original QuickCheck to generate test fixtures. The reference implementation parser was quite easy to make with parsec.

• Q: Why you didn't use PureScript or something else to port Haskell implementation?

• A: I actually tried to. But PureScript doesn't have parsec copy at the moment. And I didn't had time to do that :(

rx.js

"use strict";

var Rx = require("rx");
var q = require("q");
var _ = require("lodash");
var jsc = require("jsverify");

var jscOptions = {
  quiet: false,
};

var exampleArray = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];

var id = function (x) {
  return x;
}
var flatMap = function (arr, f) {
  return _.chain(arr).map(f).flatten(true).value();
}

console.log(flatMap(exampleArray, id));

function runObservable(arr, f) {
  var deferred = q.defer();
  var acc = [];

  var obs = Rx.Observable.fromArray(arr);

  obs
  .flatMap(f) // actually we want .concatMap
  .subscribe(
    function (x) {
      acc.push(x);
    },
    function () {},
    function () {
      deferred.resolve(acc.slice());
    });

  return deferred.promise;
}

runObservable(exampleArray, Rx.Observable.fromArray).then(console.log);

var enumerableObservableDualProp = jsc.forall("array (array nat)", function (arr) {
  var e = flatMap(arr, id);
  var op = runObservable(arr, Rx.Observable.fromArray);

  return op.then(function (o) {
    return _.isEqual(o, e);
  });
});

jsc.assert(enumerableObservableDualProp, jscOptions);

// outputs [0, 0, 1, 0]
runObservable([[0, 0, 0], [1]], Rx.Observable.fromArray).then(console.log);

function runObs(obs) {
  var deferred = q.defer();
  var acc = [];
  
  obs.subscribe(
    function (x) {
      acc.push(x);
    },
    function () {},
    function () {
      deferred.resolve(acc.slice());
    });

  return deferred.promise;
}

var mergeMapProp = jsc.forall("array (array nat)", function (arr) {
  var ap = runObs(Rx.Observable.fromArray(arr).map(Rx.Observable.fromArray).mergeAll());
  var bp = runObs(Rx.Observable.fromArray(arr).flatMap(Rx.Observable.fromArray));

  return q.all([ap, bp]).spread(function (a, b) {
    return _.isEqual(a, b);
  });
});

jsc.assert(mergeMapProp, jscOptions);

var concatMapProp = jsc.forall("array (array nat)", function (arr) {
  var ap = runObs(Rx.Observable.fromArray(arr).map(Rx.Observable.fromArray).concatAll());
  var bp = runObs(Rx.Observable.fromArray(arr).concatMap(Rx.Observable.fromArray));

  return q.all([ap, bp]).spread(function (a, b) {
    return _.isEqual(a, b);
  });
});

jsc.assert(concatMapProp, jscOptions);

sort.hs

module Main where

import Data.List (sort)

import Test.QuickCheck

fancyIsSorted :: Ord a => [a] -> Bool
fancyIsSorted [] = True
fancyIsSorted xs = and $ zipWith (<=) xs $ tail xs

isSorted :: Ord a => [a] -> Bool
isSorted []       = True
isSorted [x]      = True
isSorted (x:y:zs) = x <= y && isSorted (y:zs)

isPermutation :: Eq a => [a] -> [a] -> Bool
isPermutation [] []     = True
isPermutation [] [_]    = False
isPermutation [_] []    = False
isPermutation (x:xs) ys = x `elem` ys && isPermutation xs (deleteFirst x ys)
  where deleteFirst _ []                 = []
        deleteFirst x (y:ys) | x == y    = ys
                             | otherwise = y : deleteFirst x ys 
{- 
Note: first I had isSorted with (<), it failed!

λ: main
*** Failed! Falsifiable (after 5 tests and 2 shrinks):    
[-3,-3]
-}

lengthProp :: Ord a => [a] -> Property
lengthProp ls = length (sort ls) === length ls

sortedProp :: Ord a => [a] -> Bool
sortedProp = isSorted . sort

permutationProp :: Ord a => [a] -> Bool
permutationProp ls = isPermutation ls (sort ls)

classifiedSortedProp :: Ord a => [a] -> Property
classifiedSortedProp ls = classify True (classifier ls) $ isSorted $ sort ls
  where classifier ls = show (length ls `div` 10) ++ "x"

isSortedEquiv :: Ord a => [a] -> Property
isSortedEquiv ls = fancyIsSorted ls === isSorted ls

main :: IO ()
main = do
  quickCheck (lengthProp :: [Int] -> Property)
  quickCheck (sortedProp :: [Int] -> Bool)
  quickCheck (permutationProp :: [Int] -> Bool)
  quickCheck (classifiedSortedProp :: [Int] -> Property)
  quickCheck (isSortedEquiv :: [Int] -> Property)

sort.js

"use strict";

var _ = require("lodash");
var jsc = require("jsverify");

var jscOptions = {
  quiet: false,
};

function isSorted(arr) {
  if (arr.length === 0) { return true; }
  var iterEnd = arr.length - 1;
  for (var i = 0; i < iterEnd; i++) {
    if (!(arr[i] <= arr[i + 1])) {
      return false;
    }
  }
  return true;
}

function isEqPermutation(a, b) {
  var len = a.length;
  if (b.length !== len) { return false; }

  var removed = b.map(function () { return false; });
  outer: for (var i = 0; i < len; i++) {
    for (var j = 0; j < len; j++) {
      if (a[i] === b[j] && removed[j] === false) {
        b[j] = true;
        continue outer;
      }
    }

    return false;
  }

  return true;
}

var shuffleProperty = jsc.forall("array number", function (arr) {
  // TODO: add shuffle to jsc tools
  // this is not repeatable test
  return isEqPermutation(_.shuffle(arr), arr);
});

jsc.assert(shuffleProperty, jscOptions);

var lengthProperty = jsc.forall("array number", function (arr) {
  return _.sortBy(arr).length === arr.length;
});

var sortedProperty = jsc.forall("array number", function (arr) {
  return isSorted(_.sortBy(arr));
});

var permutationProperty = jsc.forall("array number", function (arr) {
  return isEqPermutation(arr, _.sortBy(arr));
});


jsc.assert(lengthProperty, jscOptions);
jsc.assert(sortedProperty, jscOptions);
jsc.assert(permutationProperty, jscOptions);

A: I added small SDL for types so you can write "array (array nat)" in place of jsc.array(jsc.array(jsc.nat)).

You mean DSL?