Different approach to shrinking

[Icelandjack]

May be of interest: Integrated vs type based shrinking

[reiddraper]

I proposed this several years ago, and unfortunately have heard nothing from the QuickCheck maintainers.

[phadej]

I wonder, whether RoseTree approach will work with Fun?

[thumphries]

I use an implementation of this idea every day, it really improves the ergonomics of property testing! Would love to see it in QuickCheck.

[nick8325]

It's a nice approach which I have a lot of time for, but it also has a couple of drawbacks.

1. This style of Gen works well as an Applicative, but less well as a Monad. For example, if you generate pairs by writing (,) <$> arbitrary <*> arbitrary then both components can be shrunk independently. However, if you write the following generator instead:

do
  x <- arbitrary
  y <- arbitrary
  return (x, y)

then the shrinking behaviour is: first x is shrunk, then y, but once it's finished shrinking y it won't try shrinking x again. (It wouldn't be safe to do so because if the generator made decisions based on x's value, you might end up in an infinite shrinking loop.)

ApplicativeDo helps here of course but it still seems a bit fragile.

2. It's a bit less flexible, because your shrinking strategy has to follow the recursive structure of your generator.

For example, QuickCheck's shrinking for lists (function shrinkList) first tries to remove half the list, then a quarter, then an eighth, and so on until it gets down to single elements. This is just defined using normal list functions. It's harder to do this with shrinking built into the generators - I think you'd have to write your generator in a divide-and-conquer style, where you recursively generate both halves of the list, then append them together while trying to shrink them both to the empty list.

Now imagine that we want to change shrinking so that it (say) also tries to remove the middle third of the list. This is a simple change in QuickCheck at the moment, but I don't know how to add it in this other design. You might try adding it as an extra shrinking step at the end, but that means that once you remove the middle third of a list you can no longer shrink the individual elements. (I suppose that this is related to the problem in number 1 above - shrinking becomes sensitive to the order in which you generate things, which is not really the case in current QuickCheck.)

In general, I think QuickCheck is better at doing "non-local" shrinking steps, where you want to look at an entire generated value, pick out different parts of it and rearrange them into something new.

So, although I like this approach, I don't think we should adopt it in QuickCheck. I think both approaches are valid and QuickCheck's is more work to use but also more powerful - it's a trade-off. I find that the generic helpers for shrink help a lot (which get rid of most of the boilerplate, even though they don't help with preserving the invariant during shrinking). But if anyone has ideas to improve the shrinking situation, for example more kinds of generic shrink steps or ways to better integrate libraries like disorder-jack with QuickCheck, then I'd be happy to hear them!

[jacobstanley]

(author of disorder-jack here)

I agree with @nick8325's analysis. It is a trade-off and although I personally think integrated shrinking is a better trade-off, I think it would be quite hard to retrofit this style in a non-breaking way to QuickCheck.

You might try adding it as an extra shrinking step at the end, but that means that once you remove the middle third of a list you can no longer shrink the individual elements

This is indeed what we do in disorder-jack.

You are right about problem 1, but it hasn't been a big deal in practice because you can work around it using the reshrink function I linked above.

The main issue we found with using QuickCheck-style shrinking in our team was not a technical, but a social one, people are too lazy to write shrinkers. In practice, at least at our company, QuickCheck doesn't have shrinking at all.

[Icelandjack]

Reddit discussion.

[phadej]

I made a proof-of-concept of rose tree based shrinking, see #136.

However, the test generating well-typed stlc expression (with natural numbers) fails to produce any shrinked arguments. If someone know how to improve that example, that would be great.

EDIT: now when written the shrink for Ty manually, the expressions are shrunkable as well.

[dnadales]

However, if you write the following generator instead:

 x <- arbitrary
 y <- arbitrary
 return (x, y)

then the shrinking behaviour is: first x is shrunk, then y, but once it's finished shrinking y it won't try shrinking x again. (It wouldn't be safe to do so because if the generator made decisions based on x's value, you might end up in an infinite shrinking loop.)

Sorry to resurrect this, but I'm trying to conjure a more or less realistic example in which integrated shrinking will fail to find a minimal counter-example. Do you have such an example at hand (or at least some hints?). Thanks :pray:

[nick8325]

The simplest property would be something like prop (x,y) = x < y. Suppose that we come up with the counterexample (9,4). Then integrated shrinking will start by shrinking x to 4 (it can't be shrunk to 3 because (3,4) isn't a counterexample). Next it will shrink y to 0. The final counterexample will be (4,0), but the minimal counterexample is (0,0)!

By the way, QuickCheck has the same problem too, if you write the property in the form prop x y = x < y! (To see this in action, you need to force the size to be nonzero by doing e.g. quickCheck (mapSize (const 100) prop).) This is because the Property type in QuickCheck has integrated shrinking.

[dnadales]

Thanks @nick8325 for this. In the meantime I wrote this more convoluted example (in hedgehog):

import Hedgehog
import qualified Hedgehog.Gen as Gen
import qualified Hedgehog.Range as Range

notLargeOrBothNotEmpty :: Property
notLargeOrBothNotEmpty = property $ do
  xs <- forAll randomIntLists
  ys <- forAll randomIntLists
  assert $ length xs < 10 && (xs /= [] && ys /=[])
  where
    randomIntLists = Gen.frequency
      [ (1, Gen.list (Range.constant 0 1) randomInt)
      , (10, Gen.list (Range.constant 1 100000) randomInt)
      ]
    randomInt = Gen.integral (Range.constant 1 100)

This will consume all my system memory in some cases, and will give a non-minimal counter examples in others. Even though it is a contrived, and maybe poorly written example, it shows the problems one might run into when composing generators if one is not careful (or stupid like me :)).