Shrink should put its smallest guesses first

[chriswarbo]

Shrinking can require lots of property evaluations when there are multiple values to consider (multiple arguments to a property, or compound values like tuples, or both), which can be quite slow. Since we're aiming for the smallest counterexample, we should prefer the results of Shrink.shrink to be in ascending order; i.e. we only try the "less shrunk" guesses if the "more shrunk" guesses don't work.

In particular, values which are irrelevant to a failure will reduce down to their simplest form; e.g. strings will become empty, characters will become NUL, numbers will become zero, etc. ScalaCheck seems to take a while to reach these. As an example, I was diagnosing a slow test recently and saw the following behaviour when I stubbed out the test with fail("FOO") (i.e. it will always fail, regardless of arguments):

[info]   TestFailedException was thrown during property evaluation.
[info]     Message: FOO
[info]     Location: (MyFile.scala:121)
[info]     Occurred when passed generated values (
[info]       arg0 = ���, // 44 shrinks
[info]       arg1 = DateRange(1970-01-01T00:00:00Z,1970-01-01T00:00:01Z), // 31 shrinks
[info]       arg2 = Input(6.792740951212974E-21,None,None,None), // 3 shrinks
[info]       arg3 = 0 // 27 shrinks
[info].    )

The first argument is a String constrained to be three-characters; it took 44 evaluations to reach three NUL bytes. The DateRange is a pair of java.time.Instant values with the second occurring after the first; these are generated and shrunk by converting back and forth to seconds since the Unix epoch, so the above counterexample is essentially the tuple (0, 1), which required 31 shrinks to reach. The final argument is an Int, which took 27 shrinks to reach zero.

When I augmented the shrinkers for our custom datatypes, such that they tried the "simplest" value first, I managed to heavily reduce the number of evaluations (plus the BigDecimal at the start of arg2 becomes 0, which is simpler than the E-21 value above):

[info]   TestFailedException was thrown during property evaluation.
[info]     Message: FOO
[info]     Location: (MyFile.scala:121)
[info]     Occurred when passed generated values (
[info]       arg0 = ���, // 1 shrink
[info]       arg1 = DateRange(1970-01-01T00:00:00Z,1970-01-01T00:00:01Z), // 16 shrinks
[info]       arg2 = Input(0,None,None,None), // 4 shrinks
[info]       arg3 = 0 // 28 shrinks
[info]     )

Looking through the ScalaCheck source, I think a big reason for this is the way numbers shrink: halving and negating over and over (until stopping when near to zero). If we instead started with a literal zero, this would (a) short-cut a lot of cases and (b) give us "clean" zeros instead of arbitrary near-zeros. If we're willing to pre-compute the shrunken numbers, rather than doing it on-demand, then we could also reverse the stream-of-halvings to get a stream-of-doublings; this would cause O(log n) fewer property evaluations for counterexamples of value n (e.g. for (x: Int, y: Int) the value n would be x + y; not 2 for the number of ints). It would cost O(log n) numerical evaluations (creating the stream elements that get reversed); but this tradeoff seems reasonable to me.

The main drawback is that we may evaluate the same counterexamples multiple times. For example, a property P(x) which fails when x > 5 might find a counterexample of P(100). The current shrinker would guess something like -50, 50, -25, 25, -12, 12, -6, 6, which is a "chain" of counterexamples getting shrunk further and further; finally it will shrink the 6 to guess -3, 3, but these will both pass, so it stops with the counterexample x = 6.

Under my proposed scheme this would shrink like 0, 1, -1, 3, -3, all of which pass; then it reaches 6 which is a counterexample, so it shrinks again: 0, 1, -1, 3, -3. None of these are counterexamples, so it stops with x = 6. In this case we've evaluated 0, 1, -1, 3 and -3 multiple times, which is undesirable. We could avoid this with a memo table, but it doesn't seem worth the trouble.

I think the case for guessing 0 first is pretty solid, since it short-cuts a common situation and doesn't introduce much re-evaluation (if 0 passes, the next guess would try shrinking to 0 too). I think the case for reversing the Stream in numeric shrinkers is less clear.

[ashawley]

You've included the output from ScalaCheck, but it would be easier to understand your situation if you could send the property test and your improved shrinking definitions. I can guess what problems with shrinking you're likely running in to, but I don't know precisely what you're doing to tell.