Rust QuickCheck自定义shrink实现触发栈溢出问题问询

我定义了如下结构体：

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

我为该结构体实现了Arbitrary trait，代码如下：

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())
                }
            }
        }))
    }
}

我编写了如下测试用例：

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

现象如下：

• 未使用自定义shrink实现时，测试生成的反例为：

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

• 直观来看更精简的最小反例应为Restriction { min: Some(1), max: None }，Restriction { min: Some(1), max: Some(1) }也是可接受的结果。
• 但使用自定义shrink实现运行测试时，程序报错：fatal runtime error: stack overflow。
• 我专门编写了测试验证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(())
}

我目前无法定位自定义shrink实现的问题所在。

你的代码存在三个直接导致异常的问题：

1. arbitrary实现存在笔误：判断大小的分支写的是if x > y，但x和y是Option<u64>类型，你实际需要比较的是解包后的x_和y_，正确写法应为if x_ > y_。这个笔误会生成min > max的非法Restriction实例。
2. 自定义shrink的收缩效率极低：你采用逐次减1的方式收缩u64值，对于测试生成的1e19量级的大数值，需要近1e19次递减才能收缩到0，quickcheck的递归收缩逻辑会直接因为递归深度过大触发栈溢出。你单独写的小数值（3和7）测试覆盖不到大数值场景，自然不会触发这个问题。
3. 收缩逻辑没有做合法性校验：即使不考虑大数值的问题，当非法的min>max实例进入收缩流程时，也可能出现循环收缩的情况，进一步加剧栈溢出问题。

首先修正arbitrary里的比较笔误，然后放弃手写逐次减1的收缩逻辑，直接复用Option<u64>自带的成熟收缩实现（内置u64收缩是对数级递减，从1e19收缩到0仅需几十步，不会出现递归过深问题），最后过滤掉min > max的非法实例即可：

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>> {
        // 复用Option<u64>自带的收缩逻辑
        let min_shrinks = self.min.shrink().map({
            let current_max = self.max;
            move |new_min| Restriction { min: new_min, max: current_max }
        });
        let max_shrinks = self.max.shrink().map({
            let current_min = self.min;
            move |new_max| Restriction { min: current_min, max: new_max }
        });

        // 组合所有收缩结果，过滤非法实例
        Box::new(
            min_shrinks
                .chain(max_shrinks)
                .filter(|r| match (r.min, r.max) {
                    (Some(a), Some(b)) => a <= b,
                    _ => true
                })
        )
    }
}

修复后收缩速度极快，最终能得到你期望的最小反例，不会再出现栈溢出问题。

内容的提问来源于stack exchange，提问作者James Burton