There are a few of different concepts to grapple with when learning property-based testing (PBT). Generating random inputs, writing properties and shrinking failures are some of them. Shrinking seems to be one of those difficult concepts for people to get their head around.

There’s a nice introduction to how QuickCheck shrinks failing input in The lazy programmer’s guide to writing 1000’s of tests starting at around the 22m:24s mark. While the above presentation depicts how QuickCheck works, I was curious to see if ScalaCheck also followed the same process for Shrinking.

So what is Shrinking? Shrinking is the process by which a PBT framework tries to reduce the failing random input to a property to its minimal value. And it does this so that we as programmers don’t have to do much further investigation to find the “simplest” failing input.

What does minimal mean?

That depends on how you want to reduce the supplied input to the simplest possible value that would still fail the property.

Let’s have a look at an example using ScalaCheck to make this a little clearer.

Let’s create a property that expects any integer value that is greater than a hundred and twenty to be even or less than a hundred and eleven and be odd:

val p1 = Prop.forAll((n: Int) => n > 120 && n % 2 == 0 || n < 111 && n % 2 != 0 )

This property fails when run:

p1.check
! Falsified after 5 passed tests.
> ARG_0: 0
> ARG_0_ORIGINAL: 2147483647

The initial failing input (before shrinking) is named ARG_0_ORIGINAL and has a value of 2147483647. ScalaCheck then tries to simplify this input value to something that would still fail the property. The final shrunk value is named ARG_0 in this case and has a value of 0.

How did ScalaCheck come up with the value for ARG_0 ?

It would be nice if ScalaCheck could explain how it shrunk that Int value supplied to our property. Unfortunately there doesn’t seem to be an easy way to get that to happen and we’ll have to find other ways of making ScalaCheck talk.

Let’s start our investigation by grabbing the default instance for shrinking Ints:

val intShrink = implicitly[Shrink[Int]]

Once we have the Shrink instance we can shrink the input value we received in the failing property (2147483647):

intShrink.shrink(2147483647).toList
List[Int] = List(1073741823, -1073741823, 536870911, -536870911, 268435455, -268435455, 134217727, -134217727, 67108863, -67108863, 33554431, -33554431, 16777215, -16777215, 8388607, -8388607, 4194303, -4194303, 2097151, -2097151, 1048575, -1048575, 524287, -524287, 262143, -262143, 131071, -131071, 65535, -65535, 32767, -32767, 16383, -16383, 8191, -8191, 4095, -4095, 2047, -2047, 1023, -1023, 511, -511, 255, -255, 127, -127, 63, -63, 31, -31, 15, -15, 7, -7, 3, -3, 1, -1, 0)

It’s too hard to see any patterns forming when shrinking a value as large as 2147483647. There are too many values returned by the shrinker.

(We use toList here to eagerly evaluate the (lazy) Stream return by the shrinker)

Let’s try shrinking something a little smaller that would still fail the property:

intShrink.shrink(110).toList
List[Int] = List(55, -55, 27, -27, 13, -13, 6, -6, 3, -3, 1, -1, 0)

Now that’s more manageable. We can see that the generated Stream of simpler values seems to follow this algorithm:

  1. Divide the input by 2 to get a shrunk value.
  2. Add the shrunk value to result Stream.
  3. Flip the sign of the shrunk value and add it to the Stream after [2].
  4. Repeat step 1 with the shrunk value as input until there are no further shrinks or you hit zero.

If we look at the source for the default Shrink[Int] instance we can see that it is doing what we expect with some special treatment when the input is zero:

final class ShrinkIntegral[T](implicit ev: Integral[T]) extends Shrink[T] {
  import ev.{ equiv, fromInt, zero, minus, times, quot }
  val minusOne = fromInt(-1)
  val two = fromInt(2)
  // assumes x is non-zero
  private def halves(x: T): Stream[T] = {
    val q = quot(x, two)
    if (equiv(q, zero)) Stream(zero)
    else q #:: times(q, minusOne) #:: halves(q)
  }
  def shrink(x: T): Stream[T] =
    if (equiv(x, zero)) Stream.empty[T] else halves(x)
}

From the shrink Stream for Ints, it looks like ScalaCheck keeps trying each possible shrunk value as an input to the failing property until it hits the last value (zero) and then returns that.

Stream(55, -55, 27, -27, 13, -13, 6, -6, 3, -3, 1, -1, 0) //looks like each value is tried in turn until 0

This is not exactly the case, so let’s try and find a way to get ScalaCheck to explain how it actually does its shrinking.

One way to get at the information we need is to write our own Shrink instance that writes out the following:

  1. The input value to shrinker
  2. The shrunk values generated by the shrinker

It would also be handy to be able to wrap any existing Shrink instance and have the explainer printout how the wrapped Shrinker works.

Here’s a first pass at writing our own Shrink explainer:

  def explain[T: Shrink] = Shrink[T] { input =>
    println(s"input to shrink: $input")
    val wrappedShrinker = implicitly[Shrink[T]]
    val shrunkValues = wrappedShrinker.shrink(input)
    //this eagerly evaluates the Stream of values. It could blow up on very large Streams or expensive computations.
    println(s"shrunk values: ${shrunkValues.mkString(",")}")
    shrunkValues
  }

Let’s also write a simple Generator to reduce our inputs to a much smaller range of between a hundred and a hundred and fifty:

Gen.choose(100, 150)

Now let’s use our Generator and our Shrink explainer in our property:

val p2 = Prop.forAll(Gen.choose(100, 150))((n: Int) => n > 120 && n % 2 == 0 || n < 111 && n % 2 != 0 )(implicitly,  explain[Int], implicitly)

The use of implicitly might be a bit confusing if you’ve never seen it before. Basically it uses the default implicit values for the parameters at the specified positions so you don’t have to explicitly pass them in yourself. We can now just supply our Shrink[Int] instance via the explain method without having to worry about any of the other parameters.

Now we have a property that can be explained. Let’s run it and see how the shrinking actually works:

p2.check
[1]  input to shrink: 133
[2]  shrunk values: 66,-66,33,-33,16,-16,8,-8,4,-4,2,-2,1,-1,0
[3]  input to shrink: 66
[4]  shrunk values: 33,-33,16,-16,8,-8,4,-4,2,-2,1,-1,0
[5]  input to shrink: 16
[6]  shrunk values: 8,-8,4,-4,2,-2,1,-1,0
[7]  input to shrink: 8
[8]  shrunk values: 4,-4,2,-2,1,-1,0
[9]  input to shrink: 4
[10] shrunk values: 2,-2,1,-1,0
[11] input to shrink: 2
[12] shrunk values: 1,-1,0
[13] input to shrink: 0
shrunk values:
! Falsified after 2 passed tests.
> ARG_0: 0
> ARG_0_ORIGINAL: 133

For p2 the original failing input is 133 and it is then shrunk down to 0. Let’s follow the shrink process from the top:

  1. The property fails for a value of 133
  2. The shrinker gets the value of 133 for shrinking [1]
  3. The shrinker shrinks the value of 133 and generates a Stream of shrunk values starting with 66 [2]
  4. The property is run with a value of 66 and fails
  5. The shrinker gets the value of 66 for shrinking [3]
  6. The shrinker shrinks the value of 66 and generates a Stream of shrunk values starting with 33 [4]
  7. The property is run with a value of 33 and passes
  8. The shrinker generates a value of -33 [4]
  9. The property is run with a value of -33 and passes
  10. The shrinker generates a value of 16 [4]
  11. The property is run with a value of 16 and fails
  12. The shrinker gets the value of 16 for shrinking [5]
  13. The shrinker shrinks the value of 16 and generates a Stream of shrunk values starting with 8 [6]
  14. The property is run with a value of 8 and fails
  15. The shrinker gets the value of 8 for shrinking [7]
  16. The shrinker shrinks the value of 8 and generates a Stream of shrunk values starting with 4 [8]
  17. The property is run with a value of 4 and fails
  18. The shrinker gets the value of 4 for shrinking [9]
  19. The shrinker shrinks the value of 4 and generates a Stream of shrunk values starting with 2 [10]
  20. The property is run with a value of 2 and fails
  21. The shrinker gets the value of 2 for shrinking [11]
  22. The shrinker shrinks the value of 2 and generates a Stream of shrunk values starting with 1 [12]
  23. The property is run with a value of 1 and passes
  24. The shrinker generates a value of -1 [12]
  25. The property is run with a value of -1 and passes
  26. The shrinker generates a value of 0 [12]
  27. The property is run with a value of 0 and fails
  28. The shrinker gets the value of 0 for shrinking [13]
  29. The shrinker shrinks the value of 0 and returns an empty Stream indicating there are no more shrinks
  30. The shrinker then returns the value of 0 as the “simplest” input that will fail the property as it can’t be further reduced

So we finally we have much clear idea about how all this “shrinking stuff” works! Here’s a simple diagram depicting how a shrinker works.

caption

How Shrinking Works

After a property fails, the failing input is used to generate a Stream of shrunk values. Each value is then fed into the property again until one of the shrunk values fails or the end of the Stream is reached. If the end of the Stream is reached, we can’t shrink the failing input any more so it is return without simplification.

If a shrunk value fails the property again, the shrunk value is then shrunk again and another shrink Stream is created from it. It keeps progressing this way until the shrinker can’t shrink any further (the end of the Stream is reached) or all the shrunk values pass the property. In either case last input value to the shrinker is returned (which is the simplest failing input).

Hopefully this sheds some light on the shrinking process used by ScalaCheck.