Tuple shrinking should go to 11 (and beyond)

[jonaskoelker]

The largest tuple size for which ScalaCheck provides built-in shrinking is 9. I think ScalaCheck should provide built-in shrinking for all tuple sizes (i.e. 2 to 22).

At work we would like to shrink both 11- and 22-tuples, and they might change size as the underlying case classes acquire new fields. I'll happily do the copy-paste grunt work of writing the patch if you think this is a feature you want.

[jonaskoelker]

I added pull request #744 which implements this.

[ashawley]

I was going to suggest adding to the existing code-generation, so that seems like the right approach in #744 rather than copy-paste.

[ashawley]

I have one concern about "fixing" this: Was the limit to tuples of 9 an historical artifact of either Scala or ScalaCheck or was it intentional? One reason it might be intentional is because raising the shrinking to greater tuple sizes means that shrinking complexity is increased and failures might be extremely slow. Unfortunately, issues around test failures like this aren't likely to be caught in our test suite. I believe the complexity would be something on the order of n^m where n is the bit-length of the value and m is the number of tuples. I'll need to run some experiments to verify that suspicion.

[jonaskoelker]

Unfortunately, issues around test failures like this aren't likely to be caught in our test suite.

I guess we could re-implement a small part of the shrinking process, a la shrinkClosure, and test the size of the total shrink stream?

I believe the complexity would be something on the order of n^m where n is the bit-length of the value and m is the number of tuples. I'll need to run some experiments to verify that suspicion.

Empiricism ftw :-)

I think for tuples of ints, I can half-way persuade myself that shrinking n down to 0 takes at most $O(log^2 n)$ time, and so shrinking m of them takes at most $((log^2 n)^m)$ time, uh maybe plus some overhead in when the shrinking process recurs and you go through the shrinks of each already-shrunk component, left to right.

However, that's assuming 0 is the shrink target. If you use a sized generator (generating e.g. min(32, size/3) bit integers), adding one bit at a time means you likely hit a counterexample that's not much larger than the smallest counterexample (although things look grim if you need all 22 components to line up exactly). A smaller distance to the shrink target means a faster shrink process.

Anyways, on the assumption that this is a problem, we could perhaps make the shrinkers available but only make the first 9 implicit; then users can uh implicitize whatever they want to use. Maybe if it's only marginally a problem, big tuple shrinking could be enabled by default if the old behavior can be restored?

was it intentional?

I'm not sure how I could know for sure, but here's a probably-relevant observation: the most recent change which touches the tuple shrinking lines in Shrink.scala are older than the addition of codegen.scala. Maybe someone got tired of copy-pasting? ;-) [Or, to attribute it to something not even close to looking like it might be adjacent to laziness, someone considered the opportunity cost of spending effort on shrinking larger tuples vs. working on other aspects of ScalaCheck.]