Stack overflow in quickcheck case shrinking

[orlp]

The following code causes quickcheck to stack overflow on trying to shrink the testcase.

/// Greatest common divisor of two integers.
pub fn gcd(a: i64, b: i64) -> i64 {
    assert!(!(a == i64::MIN && b == i64::MIN));
    if a == 0 {
        b.abs()
    } else {
        gcd(b % a, a)
    }
}


/// Returns (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b) (ignoring overflow in the LHS).
pub fn egcd(a: i64, b: i64) -> (i64, i64, i64) {
    assert!(!(a == i64::MIN && b == i64::MIN));
    let mut r = (a, b);
    let mut s = (1, 0);
    let mut t = (0, 1);

    while r.1 != 0 {
        let q = r.0 / r.1;
        r = (r.1, r.0 - q*r.1);
        s = (s.1, s.0 - q*s.1);
        t = (t.1, t.0 - q*t.1);
    }

    if r.0 < 0 {
        (-r.0, -s.0, -t.0)
    } else {
        (r.0, s.0, t.0)
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    use quickcheck::quickcheck;

    quickcheck! {
        fn qc_egcd(a: i64, b: i64) -> bool {
            if a == 0 || b == 0 {
                return true;
            }

            let (g, x, y) = egcd(a, b);
            g == gcd(a, b) && a.wrapping_mul(x).wrapping_add(b.wrapping_mul(y)) == g
        }
    }
}

[BurntSushi]

Thanks for the easy reproduction.

The shrinking algorithm is recursive. I don't personally have any plans to work on fixing that (I don't know off-hand how hard that would be), but if someone wanted to submit a patch for it, that would be great.

[orlp]

Does there exist an option to disable the shrinking (either globally or per testcase)?

[BurntSushi]

Yes, albeit somewhat indirectly. You have to add wrapper types with trivial implementations of Arbitrary. The arbitrary method would just call the inner types arbitrary method. And the shrink method would just return nothing.