Open neithernut opened 3 years ago
This change is not yet tested. Also, I'm not sure whether or not the shrink_failure
function should be integrated into the final match
. I suspect the primary reason to have a separate function in the first place was the recursion (although it doesn't say so explicitly in 5b19e7c21e1afdcabb894668ad61be70bb023ef0).
Sadly, I couldn't reproduce the failure using the reproducer from #285 (because the probability of hitting integer overflows is much higher). Hence, I used the following artificial test-case:
#[derive(Clone, Debug)]
struct Num(u32);
impl Arbitrary for Num {
fn arbitrary(g: &mut Gen) -> Self {
Num(u32::arbitrary(g) & 0x00ffffff) // Replace with contrete num if needed
}
fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
Box::new(self.0.checked_sub(1).map(Num).into_iter())
}
}
fn fail(n: Num) -> bool {
n.0 < 3
}
quickcheck(fail as fn (Num) -> bool)
While this would provoke a stack overflow on defde6fb0ce20b0c8c4e672aa9ae821f7d1f5b38 I'd get the expected '[quickcheck] TEST FAILED. Arguments: (Num(3))
with these changes.
Just wanted to note: with these changes, faulty shrinkers which would previously provoke a stack-overflow may now produce endless repetition of a test for a small set of values (e.g. a single value).
It would thus be a good idea to bound the number of reproductions. We could introduce another setting to Gen
which could be configured through an environment variable (e.g. QUICKCHECK_REPRODUCTIONS
). I decided to hold off crafting such changes for now, as they would conflict with #287.
Just came across a use-case where I hit the recursion limit (and where I actually don't think a bug is involved), and this PR looks reasonable to me. @BurntSushi given your comment in https://github.com/BurntSushi/quickcheck/issues/285#issuecomment-830269194, it'd be useful to get your guidance on whether you think this is an acceptable path to take, or if not, what kind of shape you'd like to see an acceptable solution take.
We try to shrink values recursively, i.e. when a shrunk value witnesses a failure, we'd shrink that value further. Previously, this recursion would be implemented via actual control flow recursion, i.e. a function calling itself. Since the recursion could not be unrolled by the compiler, this could result in stack overflows in some situations.
Albeit such an overflow would often hint at a faulty shrinker (e.g. a shrinker yielding the original value), the stack overflow could also occur in other situations.
Fixes #285.