Do recursive shrinking without recursive function calls #294
Conversation
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. This change switches from a recursive control flow to explicitly swapping out the shrinking iterator during the iteration.
|
This change is not yet tested. Also, I'm not sure whether or not the |
In the past, shrinking was implemented using recursion in the control
flow. `shrink_failure` would call itself. That function was introduced
originally in
5b19e7c
presumably in order to implement recursive shrinking. However, we
recently choose an approach which would not rely on recursive control
flow but on swapping out an iterator. Thus, the reason why
`shrink_failure` existed in the first place doesn't exist any more.
This change moves the logic in its original place, but also replaces the
`match` which enclosed the call to `shrink_failure` with an `if`.
|
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 defde6f I'd get the expected |
|
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 |
|
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 #285 (comment), 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. |
|
+, @BurntSushi encountered this issue too |
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.