Shrinking

Find bugs easier by reducing failed examples to their minimal form

🚧

Beta Feature

This feature is released for evaluation, but the APIs presented here should not be considered stable and should be used with care. They are likely to change in the next release of quick_check.js.

Let me start this with a contrived example. Imagine we are testing a sum function. We might (probably accidentally) write the following spec:

JavaScript

it('doesn\'t produce very small numbers', function() {
  expect(function(arr) {
    return sum(arr) > -1000;
  }).forAll(qc.arrayOf(qc.int));
});

CoffeeScript

it 'doesn\'t produce very small numbers', ->
  expect (arr) ->
    sum(arr) > -1000
  .forAll qc.arrayOf(qc.int)

TypeScript

it('doesn\'t produce very small numbers', function() {
  expect(arr => sum(arr) > -1000).forAll(qc.arrayOf(qc.int));
});

quick_check.js will find the problem right away. Before shrinking, or with shrinking disabled you will see this message:

PhantomJS 1.9.8 (Mac OS X) qc examples shrinks properly FAILED
	Falsified after 47 attempts. Counter-example: [0,0,-2,5,-6,17,26,30,-4,-3,19,-117,-103,115,-160,149,-237,-143,135,146,189,-37,-288,-184,-87,-240,165,-558,-577,-670,409,-770,806,211,461,723,-1127]

Just looking at the example it can be difficult to find why it fails. You can imagine that if you have a real world example, the output can conceivably span several pages. What we really want is a minimal example where we can debug this easily. With shrinking, you will get the following message:

PhantomJS 1.9.8 (Mac OS X) qc examples shrinks properly FAILED
	Falsified after 47 attempts. Counter-example (after 11 shrinks): [-1000]

	Non-shrunk counter-example: [0,0,-2,5,-6,17,26,30,-4,-3,19,-117,-103,115,-160,149,-237,-143,135,146,189,-37,-288,-184,-87,-240,165,-558,-577,-670,409,-770,806,211,461,723,-1127]

Notice the Counter-example (after 11 shrinks): [-1000]. That's pretty much as minimal an example as we can get. If only users could report bugs like that!

❗️

Limitations

Unfortunately, the support is currently quite limited. Shrinking doesn't necessarily respect the constraints on the datatype that the generators specify. (Which is why we print the non-shrunk value as well).

There are only a handful of shrinkers built in, but you can add your own:

qc.addShrinker(rule, shrinker)

This takes two functions. The first, rule(value), is a function that should return a boolean. This function is passed a value and returning true indicates that the shrinker is capable of handling and shrinking the value (at least in principle, the value may already be minimal).

The shrinker(value) should return an iterator that returns values that are strictly smaller than the original value. By smaller, we mean that a shrinker applied on a value should terminate. For good performance the values returned by the iterator should be ordered from smallest to largest wherever that makes sense.

Let's look at an example shrinker for strings:

JavaScript

function rule(value) {
  return typeof value === 'string';
}

function* shrink(value) {
  // The empty string is the smallest, we can't shrink it anymore
  if (value.length === 0) {
    return;
  }
  // First let's try the empty string, as its the smallest possible
  yield '';
  // Next we will systematically remove parts of the string
  var toRemove = Math.floor(value.length / 2);
  var offset;
  while (toRemove > 0) {
    offset = 0;
    while (offset + toRemove <= value.length) {
      yield value.slice(0, offset).concat(value.slice(offset + toRemove));
      offset += 1;
    }
    toRemove = Math.floor(toRemove / 2);
  }
}

var shrinker = qc.addShrinker(rule, shrink);

CoffeeScript

rule = (value) -> typeof value is 'string'
shrink = (value) ->
  return if value.length is 0

  yield ''

  toRemove = Math.floor(value.length / 2)

  while toRemove > 0
    offset = 0
    while offset + toRemove <= value.length
      yield value.slice(0, offset).concat(value.slice(offset + toRemove))
      offset += 1
    toRemove = Math.floor(toRemove / 2)

shrinker = qc.addShrinker rule, shrink

TypeScript

function rule(value) {
  return typeof value === 'string';
}

function* shrink(value: string) {
  // The empty string is the smallest, we can't shrink it anymore
  if (value.length === 0) {
    return;
  }
  // First let's try the empty string, as its the smallest possible
  yield '';
  // Next we will systematically remove parts of the string
  let toRemove = Math.floor(value.length / 2);
  let offset;
  while (toRemove > 0) {
    offset = 0;
    while (offset + toRemove <= value.length) {
      yield value.slice(0, offset).concat(value.slice(offset + toRemove));
      offset += 1;
    }
    toRemove = Math.floor(toRemove / 2);
  }
}

let shrinker = qc.addShrinker(rule, shrink);

In the example the shrink function systematically removes a portion of the string from various offsets. The portion starts at half the string. Calling shrink('abcdefgh') will yield in order the following values:

'', 
'efgh', 'afgh', 'abgh', 'abch', 'abcd', 'bfgh', 'bcgh', 'bcdh', 'bcde', 'cfgh', ...
'cdefgh', 'adefgh', 'abefgh', 'abcfgh', 'abcdgh', 'abcdeh', 'abcdef', 'bdefgh', ...
'bcdefgh', 'acdefgh', 'abdefgh', 'abcefgh', 'abcdfgh', 'abcdegh', 'abcdefh', 'abcdefg'

Notice that if we applied the shrink function to any of the values yielded, we would never get a longer string back.

The return type for this function is a shrinker object (which essentially wraps the two functions passed in). The function also registers this object into the global shrink registry where the framework will automatically apply them.

qc.shrink(value[, hint[, registry]])

This function will take a value and return an iterator for smaller values. By default this uses the global shrinker registry, but you can use a custom array of shrinker objects (see above) as the final argument.

The second argument, called hint, is a performance optimisation. Normally the algorithm has to invoke all the registered rules in order until it finds one that applies. If a hint is passed, the hints rule will be evaluated first - so if it passes, the evaluation loop can be avoided. This is useful when you have a recursive datatype.