Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Stack overflow in quickcheck case shrinking #285

Open
orlp opened this issue Apr 30, 2021 · 3 comments · May be fixed by #294
Open

Stack overflow in quickcheck case shrinking #285

orlp opened this issue Apr 30, 2021 · 3 comments · May be fixed by #294
Labels
bug

Comments

@orlp
Copy link

orlp commented Apr 30, 2021

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
Copy link
Owner

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.

@BurntSushi BurntSushi added the bug label Apr 30, 2021
@orlp
Copy link
Author

orlp commented Apr 30, 2021

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

@BurntSushi
Copy link
Owner

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.

This was referenced Jun 12, 2021
Open
Open
@Alexhuszagh Alexhuszagh mentioned this issue Aug 30, 2021
Open
@wucke13 wucke13 mentioned this issue Oct 5, 2022
Open
@AnIrishDuck AnIrishDuck mentioned this issue Jun 22, 2023
Merged
dead-claudia added a commit to dead-claudia/journald-exporter that referenced this issue Jul 6, 2024
@dead-claudia
Replace QuickCheck with an own propcheck utility
b3c20e1 
...and switch the 32-bit integer parser to just exhaustive checking.
(More on that later.)

Why move away from QuickCheck?

1. The maintainer appears to have little interest in actually
   maintaining it. BurntSushi/quickcheck#315

2. Its API is incredibly inefficient, especially on failure, and it's
   far too rigid for my needs. For one, I need something looser than
   `Arbitrary: Clone` so things like `std::io::Error` can be generated
   more easily. Also, with larger structures, efficiency will directly
   correlate to faster test runs. Also, I've run into the limitations
   of not being able to access the underlying random number generator
   far too many times to count, as I frequently need to generate random
   values within ranges, among other things.
   - BurntSushi/quickcheck#279
   - BurntSushi/quickcheck#312
   - BurntSushi/quickcheck#320
   - BurntSushi/quickcheck#267

3. It correctly limits generated `Vec` and `String` length, but it
   doesn't similarly enforce limits on test length.

4. There's numerous open issues in it that I've addressed, in some
   cases by better core design. To name a few particularly bad ones:
   - Misuse of runtime bounds in `Duration` generation, `SystemTime`
     generation able to panic for unrelated reasons:
     BurntSushi/quickcheck#321
   - Incorrect generation of `SystemTime`:
     BurntSushi/quickcheck#321
   - Unbounded float shrinkers:
     BurntSushi/quickcheck#295
   - Avoiding pointless debug string building:
     BurntSushi/quickcheck#303
   - Signed shrinker shrinks to the most negative value, leading to
     occasional internal panics:
     BurntSushi/quickcheck#301

There's still some room for improvement, like switching away from a
recursive loop: BurntSushi/quickcheck#285.
But, this is good enough for my use cases right now. And this code
base is structured such that such a change is *much* easier to do.
(It's also considerably simpler.)

As for the integer parser change, I found a way to re-structure it so
I could perform true exhaustive testing on it. Every code path has
every combination of inputs tested, except for memory space as a whole.
This gives me enough confidence that I can ditch the randomized
property checking for it.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Do recursive shrinking without recursive function calls neithernut/quickcheck
2 participants
@orlp @BurntSushi