Shrinking an argument will regenerate and reshrink subsequent arguments

[steinybot]

Scala 2.12 Scalacheck 1.14.0

Expected

When a property fails then each argument would only be shrunk and new arguments would not be generated.

Actual

The last argument is shrunk first. When that argument can not be shrunk any more then it moves onto the preceding argument. The preceding argument is shrunk one step and then the remaining arguments are regenerated. These regenerated arguments must then be shrunk all over again. This continues repeatedly until eventually the first argument has been shrunk.

If you combine this with a generator that filters out values, have arguments that shrink slowly higher up in the argument order, or get unlucky and the first argument is a large value then the shrinking can take an extremely long time.

Steps to reproduce

scala> import org.scalacheck.Prop.forAll
import org.scalacheck.Prop.forAll

scala> import org.scalacheck.Arbitrary
import org.scalacheck.Arbitrary

scala> case class Num(x: Int)
defined class Num

scala> implicit val arbNum = Arbitrary {
     |   Arbitrary.arbitrary[Int].map(Num)
     | }
arbNum: org.scalacheck.Arbitrary[Num] = org.scalacheck.ArbitraryLowPriority$$anon$1@2db6ad21

scala> val propShrink = forAll { (a: Int, b: Num, c: Int, d: Num) =>
     | println("----------")
     | println(s"a: $a")
     | println(s"b: $b")
     | println(s"c: $c")
     | println(s"d: $d")
     | false
     | }
propShrink: org.scalacheck.Prop = Prop

scala> propShrink.check
----------
a: -775860897
b: Num(-1)
c: 1417213460
d: Num(-1)
----------
a: -775860897
b: Num(-1)
c: 708606730
d: Num(-2147483648)
----------
a: -775860897
b: Num(-1)
c: 354303365
d: Num(1)
...
----------
a: -775860897
b: Num(-1)
c: 2
d: Num(0)
----------
a: -775860897
b: Num(-1)
c: 1
d: Num(300617567)
----------
a: -775860897
b: Num(-1)
c: 0
d: Num(-1)
----------
a: -387930448
b: Num(-1963866452)
c: 587290664
d: Num(1)
----------
a: -387930448
b: Num(-1963866452)
c: 293645332
d: Num(1784505235)
----------
a: -387930448
b: Num(-1963866452)
c: 146822666
d: Num(-1)
...

You may need to run the check a few times until the first argument is large enough to reproduce the problem.

You can see from this example that not only are the Num arguments b and d not constant as would be expected, but c has to be shrunk repeatedly.

[steinybot]

It is reproducable with only two arguments. For example:

scala> val propShrink = forAll { (a: Int, b: Int) =>
     | println(s"a: $a")
     | println(s"b: $b")
     | false
     | }
propShrink: org.scalacheck.Prop = Prop

[steinybot]

A side effect of this is that it is also biased towards shrinking the first argument. For example if you change it to:

scala> val propShrink = forAll { (a: Int, b: Int) =>
     | println(s"a: $a")
     | println(s"b: $b")
     | a + b < 10
     | }
propShrink: org.scalacheck.Prop = Prop

then you get smaller values for a than b.

This seems reasonable behaviour but it counters any argument that somehow shrinking b repeatedly has a better chance of finding a global minimum.

[steinybot]

The workaround is to only ever use the single argument version of forAll and to tuple all the arguments together.

So instead of:

forAll { (a: Int, b: Int) =>
  ...

use:

forAll { (x: (Int, Int)) =>
  val (a, b) = x
  ...

[steinybot]

The gitter discussion for this is at https://gitter.im/scalacheck/Lobby?at=5bb546dcccd72b2f073a1d8f

[ashawley]

I've explored a fix in #458. There's some more follow-up work needed, though. For instance, the pretty-printing is affected by the change and needs further study.

[jonaskoelker]

I think the root challenge is that shrinking happens when a Prop fails, no matter how deeply nested it is inside a property tree, and that's the wrong place for shrinking to happen.

ScalaCheck supports predicate calculus expressions (forAll, exists, Prop.&&, Prop.||, etc.); let's call those PCEs, and it also supports, uh, let's call them Checkables, things you run on multiple random inputs and which can fail and which can shrink the first failing input; note that a Checkable should contain a PCE and maybe other things.

The way I read the code, a Prop is simultaneously both a PCE and a Checkable. I think the root challenge is that shrinking really wants to belong at the Checkable level and not the PCE level, since it deals with the concepts that attach to a Checkable.

Maybe the solution is to either factor Prop into two different concepts, or else (if possible) do the shrinking at the root-most Prop, if am_I_the_root() queries can be answered?

I'm not certain what the semantics of forAll is, given https://github.com/typelevel/scalacheck/issues/425. I alluded to the conjecture that all properties can be rewritten to one where (1) the root is a universal quantifier; and (2) this is the only quantifier; and (3) everything else fancy can be expressed by moving data dependencies and such into the generator. I think this is the most common use of property testing and I'd be very happy if this scenario was lend lots of affordances, including good shrinking :-)

However, maybe the semantics you want for forAll does not allow this? It seems like you have made design decisions that commit you to the behavior which this bug (#432) is asking for a change of.