Avoiding generator failures when size is zero

[travisbrown]

Failing generators are really bad now that we have non-constant arbitrary functions in ScalaCheck 1.13. Here's an example of a place this comes up in this library (derived from an example by @nrinaudo):

import org.scalacheck._, Shapeless._

sealed trait Foo; case object Bar extends Foo

val prop = Prop.forAll { (f: Int => Foo) => f(0); true }

And:

scala> prop.check
! Exception raised on property evaluation.
> ARG_0: <function1>
> Exception: org.scalacheck.Gen$RetrievalError: couldn't generate value
org.scalacheck.Gen.loop$1(Gen.scala:57)
org.scalacheck.Gen.doPureApply(Gen.scala:58)
...

I've taken a shot at a diagnosis here, but in short it looks like something like this in MkCoproductArbitrary.ccons would work:

Arbitrary {
  Gen.sized {
    case size =>
      val sig = math.signum(size)

      try {
        Gen.frequency(
          1   -> Gen.resize(size - sig, Gen.lzy(headArbitrary.value.arbitrary)).map(Inl(_)),
          n() -> Gen.resize(size - sig, Gen.lzy(tailArbitrary.arbitrary.arbitrary)).map(Inr(_))
        )
      } catch {
        case _: StackOverflowError => Gen.fail
      }
  }
}

(I'd also just use math.min(0, size - 1) instead of the signum stuff, but that's not really relevant.)

Catching the stack overflow is an awful hack, but it avoids the Gen.fail on size == 0 for non-recursive ADTs while still not stack-overflowing for recursive ones.

[ScalaWilliam]

Also, Gen.fail leads to a not particularly informative error message.

Maybe ScalaCheck could support a reason (def result: Either[String, T]) instead of (def result: Option[T]).
This might be related: typelevel/scalacheck#218 (comment)
And this: typelevel/scalacheck#258
I think at this point @non might have something to say too.

[ScalaWilliam]

This issue is derived as a result of this one fyi: nrinaudo/kantan.csv#59

[non]

@travisbrown I think your solution is probably the right one in the short-term.

I was thinking of adding error-recovery combinators on Gen (i.e. tryOrElse), which in theory would make it possible to fallback to the unchosen generator if the chosen one stack overflows (or throws other exceptions). But I don't think you should wait for me on that for this.

@ScalaWilliam That's an interesting idea. I would prefer to minimize the usage of Gen.fail as much as possible -- but maybe it's better not the make the best the enemy of the good.

[alexarchambault]

#51 seems to solve this issue, without resorting to catching stack overflows. But it it uses Gen.fail, on negative sizes (interpreted as the termination condition of coproduct generation).

[nrinaudo]

I've confirmed that #51 solves the issue as @travisbrown reported it. The following still fails, though:

  import org.scalacheck._, Shapeless._

  sealed trait Or[+A, +B] extends Product with Serializable
  case class Left[A](a: A) extends Or[A, Nothing]
  case class Right[B](b: B) extends Or[Nothing, B]

  val prop = Prop.forAll { (f: Int => Float Or Boolean) => f(0); true }

And then:

scala> prop.check
! Exception raised on property evaluation.
> ARG_0: <function1>
> Exception: org.scalacheck.Gen$RetrievalError: couldn't generate value
org.scalacheck.Gen.loop$1(Gen.scala:57)
org.scalacheck.Gen.doPureApply(Gen.scala:58)
org.scalacheck.Gen.pureApply(Gen.scala:72)
org.scalacheck.GenArities$$anonfun$function1$1$$anonfun$1.apply(GenArities.
  scala:15)
$line10.$read$$iw$$iw$$iw$$iw$$iw$$iw$$anonfun$1.apply(<console>:18)

[alexarchambault]

Quick heads up here. If my understanding is correct, the problem is actually more serious than initially though - and doesn't have a quick fix, it seems.

The problem here is we can't in a reliable way generate a recursive T with 100% guarantee. It might blow the stack, and so require a retry. Which in turn isn't fine with function generators, that require the generation to succeed upon the first attempt (again, if my understanding is correct).

[alexarchambault]

To workaround that, I may introduce two ways of deriving Arbitraries for coproducts,

• one that can fail, but fine with recursive types, and
• one that doesn't explicitly fail (and shoudn't with non recursive types), but that could blow the stack with recursive types.

One should be the default, the other would require a manual step to be enabled for a given type.

[alexarchambault]

Also, to clarify things, @travisbrown 's fix above wasn't fine with actually recursive ADTs (stack was blowing elsewhere), but things may be fine by catching the StackOverflow elsewhere... Trying that.

[nrinaudo]

I was actually wondering about this behaviour - that Gen of functions require Arbitrary instances for their return values that can never fail. Is that really an acceptable behaviour? I admit that I'll sometimes use suchThat when writing Arbitrary instances for custom types - it means that I can't use arbitrary functions into that type.

I'm wondering whether that's not a design flaw in the way arbitrary functions are built rather than a fault in scalacheck-shapeless. Generators that sometimes fail are part of the library's normal behaviour, and it's weird for them to cause arbitrary functions to fail.

[alexarchambault]

New fix pushed in #51. For a recursive type T to be fine with generated functions, one can define an implicit Recursive[T], giving it a simpler fallback generator (should be a Gen.const or Gen.oneOf - e.g. sealed trait Tree; object Tree { implicit val recursive = Recursive[Tree](Leaf) }), used if the size in of the coproduct generator goes negative (which happens in a deterministic fashion, unlike stack overflows). That allows the generation of T to always succeed, in a deterministic fashion.

For non recursive types, nothing has to be done, they should be fine out of the box.

[nrinaudo]

Is there still a need for this, given typelevel/scalacheck#301?