QuickCheck Stack Overflow

I have the following struct:

pub struct Restriction {
    pub min: Option<u64>,
    pub max: Option<u64>,
}

for which I have defined Arbitrary as follows:

impl Arbitrary for Restriction {
    fn arbitrary(g: &mut Gen) -> Self {
        let x = Option::<u64>::arbitrary(g);
        let y = Option::<u64>::arbitrary(g);

        let (min, max) = match (x, y) {
            (Some(x_), Some(y_)) if x > y => (Some(y_), Some(x_)),
            vals => vals,
        };

        Restriction { min, max }
    }

    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
        Box::new(unfold(self.clone(), |r| {
            let next_min = match r.min {
                None => None,
                Some(0) => Some(None),
                Some(x) => Some(Some(x - 1)),
            };

            let next_max = match r.max {
                None => None,
                Some(0) => Some(None),
                Some(x) => Some(Some(x - 1)),
            };

            match (next_min, next_max) {
                (None, None) => None,
                (None, Some(max)) => {
                    r.max = max;
                    Some(r.clone())
                }
                (Some(min), None) => {
                    r.min = min;
                    Some(r.clone())
                }
                (Some(min), Some(max)) => {
                    r.min = min;
                    r.max = max;
                    Some(r.clone())
                }
            }
        }))
    }
}

I also have this test case:

    #[quickcheck]
    fn restriction_silly(x: Restriction) -> bool {
        let y = Restriction {
            min: None,
            max: None,
        };
        x == y
    }

Without my custom implementation of shrink, the counter example produced is:

Restriction { min: Some(15789104099073884865), max: Some(16586241492943163879) }

Intuitively one can see that a better counter example could be Restriction { min: Some(1), max: None }, I would even accept Restriction { min: Some(1), max: Some(1) }.

Unfortunately when using my custom shrink implementation the test errors with fatal runtime error: stack overflow.

I even wrote the following test, which passes fine, to check that a restriction does in fact shrink to the empty restriction:

    #[test]
    fn restriction_shrink_to_empty() -> Result<(), std::io::Error> {
        let r = Restriction {
            min: Some(3),
            max: Some(7),
        };

        assert_eq!(r.shrink().last(), Some(Restriction::EMPTY));
        Ok(())
    }

So I'm now rather confused as to what is wrong with my shrink implementation.

Your shrink implementation will need 15 billion billion iterations to finish. I don't know how quickcheck works, but if it's calling shrink from a recursive function, no wonder you get a stack overflow. Even if it called your function iteratively, you would need a very long time to finish. I suggest you try some faster-converging function (e.g. using x/2 instead of x-1):

fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
    Box::new(unfold(self.clone(), |r| {
        let next_min = match r.min {
            None => None,
            Some(0) => Some(None),
            Some(x) => Some(Some(x / 2)),
        };

        let next_max = match r.max {
            None => None,
            Some(0) => Some(None),
            Some(x) => Some(Some(x / 2)),
        };

        match (next_min, next_max) {
            (None, None) => None,
            (None, Some(max)) => {
                r.max = max;
                Some(r.clone())
            }
            (Some(min), None) => {
                r.min = min;
                Some(r.clone())
            }
            (Some(min), Some(max)) => {
                r.min = min;
                r.max = max;
                Some(r.clone())
            }
        }
    }))
}