BurntSushi / BurntSushi/quickcheck

Stack overflow in quickcheck case shrinking

Open
#285 3 comments 3 reactions 0 assignees View on GitHub
bug
Dominant language
Rust
Stars
2.8k
Forks
165
PR merge metrics
No merged PRs in 30d

Description

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

```rust
/// 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
}
}
}
```

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.