Gen for a map of a case class containing Options fail with 'gave up after 16 successful property evaluations...'

[Eyal Farago]

hi,

first of all I'd like to say that scalacheck is great, any minute put into writing a test/generator pays of with infinite savings of debugging real world issues.

I have a case class comprised of 6 Options, I wrote a generator for this class using for comprehension and Gen.option, I also threw in a condition in the for comprehension checking that at least one of the options is defined (I actually check 4 out of the 6, since there are some inter dependencies between them). 

This generator worked out just great, so I moved on to the next task where I needed a Map[String,myCaseClass], I used the following to achieve this (genSlAgg is the case class generator mentioned above):

val aggIds = (1 to 5) map ( n => s"agg$n")

val genAggregatoIds = Gen.oneOf( aggIds 

Gen.mapOf(Gen.zip( genAggregatoIds, genSlAgg ))

running forAll based on two instances of this generator (I'm testing an operation on two maps), I started getting failures like this:

org.scalatest.exceptions.GeneratorDrivenPropertyCheckFailedException: Gave up after 16 successful property evaluations. 85 evaluations were discarded.

so I started digging into Gen's source code which led me to the conclusion that when generating a Collection (such as map), a single generation failure fails the entire collection generation. I then started crunching numbers (trying to reconstruct academic material from over 15 years ago):

probability for failing a single case class requires 4 Nones hence, assuming Gen.option is not biased: 0.5^4=0.0625
so the probability for a single success is 1-0.0625=0.9375, that seems quite high...
however when generating a map of say 20 elements, we need 20 successful generations, this leads to probability of: 0.9375^20=0.14425746361116484. hell this is quite close to the 16 out of 101 I actually got.

I managed to solve this by replacing the filter of the case class generator with a retryUntil, but I don't think this is a generally acceptable solution as there's no way to monitor the actual number of retries performed on the generator and the always exiting possibility of applying this to a generator with high probability of failing (such as my map generator outlined above).

I'd expect a more constraint version of retryUntil, perhaps one controlled by Gen.Parameters, is this achievable?
another approach that might reduce the failure probability in my case is a biasedOption construct, going back to my calculation a 70:30 biased option generator would lead to almost 80% success rate on the map generator, this seems to quite easy to implement, would you guys accept a pull request for this?

and finally, debugging generators is a pain, is it possible to somehow add slf4j support to Gen? perhaps even taking advantage of the labels for filtering... this could greatly ease (actually enable) debugging of this stuff.

thanks,
Eyal.

[Eyal Farago]

It's been a year an d a half, I've changed jobs in between, and hit the same issue again.

Just like the previous time, the root cause is Gen.listOf, Gen.listOfN and Gen.nonEmptyListOf.

This time replacing filter with tryUntill was not a real option so I did something else: I've implemented a family of stream generators (Gen[Stream[A]]) and then implemented an alternative family of list generators based on the stream generators.

basic idea is to use Gen.parameterized to generate a stream of Option[A] (by applying the underlying generator) and annotate this stream with statistics about the number of successful and failed generations seen up to each position in the stream, once I had this generator implemented I could implement streamOfN which observes the stats stroed in the generated stream and postpones failure up to a point where we've either succeeded or gathered enough information(currently max between 3*n and 100, should be configurable) and witnessed a high enough failure ratio (currently 2/3 but should be configurable).

streamOf is implemented as a simple for-comprehension on top of Gen.sized, Gen.choose and streamOfN.

nonEmptyStream is implemented using Gen.parameterized, the parameterized generator uses streamOfN to generate a single item stream and streamOf to generate a second stream of arbitrary length. in case of failoures generating one of these two list I revert to an empty stream, I then concatenate the two streams and use Gen.const(strm1 ++ strm2).filter(_.nonEmpty) to validate the resulting stream isn't empty.

Rickard Nilsson,

will you be willing to consider this stuff as a pull request?

thanks,

Eyal.