Comment by sunshowers
17 hours ago
Shrinking is by far the most important and impressive part of Hypothesis. Compared to how good it is in Hypothesis, it might as well not exist in QuickCheck.
Proptest in Rust is mostly there but has many more issues with monadic bind than Hypothesis does (I wrote about this in https://sunshowers.io/posts/monads-through-pbt/).
Python's Hypothesis has some very clever features to deal with shrinking past a monadic bind.
If I remember right, it basically uses a binary 'tape' of random decisions. Shrinking is expressed as manipulations of that tape. Your generators (implicitly) define a projection from that tape to your desired types. Shrinking an early part of the tape, leave the later sub-generators to try and re-use the later parts of the tape.
That's not guaranteed to work. But it doesn't have to work reliably for every shrink operation the library tries! It's sufficient, if you merely have a good-enough-chance to recover enough of the previous structure to trigger the bug again.
> Shrinking is expressed as manipulations of that tape.
How do you do that in general? I can't find any documentation on that.
This paper by the Hypothesis authors has some information: https://www.doc.ic.ac.uk/~afd/papers/2020/ECOOP_Hypothesis.p...
I've always wondered if there could be a small machine learning model trained on shrinking.
I'm not sure whether it would be useful, but it would definitely get you a grant (if done academically) or VC money (if done as a company) these days.