This PR fixes #241 causing the QCheck.Shrink.int* shrinkers to emit duplicates (read: wasted effort) for certain inputs.
I was re-reminded of this while attempting to improve the Shrink.string shrinker, as it uses Shrink.char which again uses Shrink.int underneath and hence inherits the bug.
The bug is fixed by slightly expanding the condition after the while loop in all 3 int{,32,64} cases.
The expect test updates nicely eliminates quite a few WTF? cases from the unit test suite.
While looking at the code, I realized that Shrink.list_spine could also emit duplicate shrinking candidates as a base-case inside its recursive approach, so I added a small fix to that too.
To document that Shrink.string may still be too exhaustive I've added unit test examples of it.
80c8c88 contains a commit with the current behaviour and f37621a then improves it.
As the test shows, there is still room for improvement.
Finally with the shrinker benchmark from #177 restored in #274 I ran it to measure the difference.
Time-wise it is a small improvement to the QCheck(1) shrinkers, but there are occasional drops in the number of shrink attempts which may matter when testing more expensive properties.
Some highlight examples include:
bind list_size constant drops from 230 to 207 shrink attempts
lists shorter than 432 drops from 20417 to 18727 shrink attempts
fail_pred_map_commute drops from 507 to 444 shrink attempts
fold_left fold_right uncurried drops from 724 to 645 shrink attempts
Here's a selection before (only the Q1 columns are relevant):
This PR fixes #241 causing the
QCheck.Shrink.int*shrinkers to emit duplicates (read: wasted effort) for certain inputs.I was re-reminded of this while attempting to improve the
Shrink.stringshrinker, as it usesShrink.charwhich again usesShrink.intunderneath and hence inherits the bug.The bug is fixed by slightly expanding the condition after the
whileloop in all 3int{,32,64}cases. The expect test updates nicely eliminates quite a fewWTF?cases from the unit test suite.While looking at the code, I realized that
Shrink.list_spinecould also emit duplicate shrinking candidates as a base-case inside its recursive approach, so I added a small fix to that too.To document that
Shrink.stringmay still be too exhaustive I've added unit test examples of it. 80c8c88 contains a commit with the current behaviour and f37621a then improves it. As the test shows, there is still room for improvement.Finally with the shrinker benchmark from #177 restored in #274 I ran it to measure the difference. Time-wise it is a small improvement to the QCheck(1) shrinkers, but there are occasional drops in the number of shrink attempts which may matter when testing more expensive properties. Some highlight examples include:
bind list_size constantdrops from 230 to 207 shrink attemptslists shorter than 432drops from 20417 to 18727 shrink attemptsfail_pred_map_commutedrops from 507 to 444 shrink attemptsfold_left fold_right uncurrieddrops from 724 to 645 shrink attemptsHere's a selection before (only the Q1 columns are relevant):
Here's the same selection after: