Generated `Vec`s are really small

[jakoschiko]

To my surprise this test doesn't fail (I ran it ~10 times):

#[test]
fn my_test() {
    arbtest::arbtest(|u| {
        let x: Vec<u8> = u.arbitrary()?;
        assert!(x.len() < 10);
        Ok(())
    })
    .budget_ms(10000) // Try really hard
    .size_min(100000) // Provide a lot of bytes 
    .size_max(100000000);
}

I know, property-based testing is very limited. But this limit seems to be quite small (in comparison to something like quickcheck). And the limit can't be extended easily by increasing the budget or size parameters.

I checked the implementation of Arbitrary for Vec in the arbitrary crate:

impl<'a, A: Arbitrary<'a>> Arbitrary<'a> for Vec<A> {
    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
        u.arbitrary_iter()?.collect()
    }
    ...
}

And here the implementation of the Iterator returned by arbitrary_iter:

impl<'a, 'b, ElementType: Arbitrary<'a>> Iterator for ArbitraryIter<'a, 'b, ElementType> {
    type Item = Result<ElementType>;
    fn next(&mut self) -> Option<Result<ElementType>> {
        let keep_going = self.u.arbitrary().unwrap_or(false);
        if keep_going {
            Some(Arbitrary::arbitrary(self.u))
        } else {
            None
        }
    }
}

As far as I know arbtest is using random bytes for Unstructured (instead of using a feedback loop like a fuzzer). Based on the implementation above I can understand why the generated Vecs are so small. But still, it doesn't feel right. Did I do something wrong?

Tested with arbtest 0.3.1 and arbitrary 1.3.2.

[matklad]

I'd say this is both surprising and reasonable behavior.

It is surprising because one would indeed expect to see longer vecs.

But it is also reasonable, because longer vecs are unlikely to trigger faults. Eg, a binary search with a bug often loops forever if all elements of a vector are the same, and, with longer vecs, you are less likely to get all equal elements!

So, I'd say perfering to exhaustively check small collections rather than to try to generate random large collections is a reasonable default.

The cool thing is, it's just that --- a default. If you do want to see longer vectors, you can use custom generating function. For example, the following will try to use up most of the entropy to generate a vector:

#[test]
fn my_test() {
    arbtest(|u| {
        let len = u.arbitrary_len::<u8>()?;
        let x = std::iter::from_fn(|| Some(u.arbitrary::<u8>()))
            .take(len)
            .collect::<Result<Vec<_>, _>>()?;
        assert!(x.len() < 100000);
        Ok(())
    })
    .budget_ms(10000) // Try really hard
    .size_min(100000) // Provide a lot of bytes
    .size_max(100000000);
}

And, if you want to look at both large and small vectors, you could also do that by something like

if u.ratio(1, 4)? {
    u.arbitrary::<Vec<u8>>()?
} else {
    // Arbitrary len
}

More generally, I've personally found that I almost never want to use "ready-made" generation strategies, and rather almost always want to hand-tweak generation to a particular test, just manually constructing a test case out of primitives like "random choice" and "int in range".

[jakoschiko]

Thanks for your answer, even if it's not what I hoped for :)

But it is also reasonable, because longer vecs are unlikely to trigger faults. Eg, a binary search with a bug often loops forever if all elements of a vector are the same, and, with longer vecs, you are less likely to get all equal elements!

I agree that small random values are often very good at revealing bugs. But some kind of bugs only occur with large values (e.g. stack overflows), so it would be nice if I could opt in for larger values.

The cool thing is, it's just that --- a default. If you do want to see longer vectors, you can use custom generating function.

That's good, but also very time-consuming. In libraries like quickcheck you only have to increase the size parameter and the size of the generated collection will increase linearly.

Besides that, the most appealing reason for me for using arbtest is the popularity of the arbitrary crate. A lot of libraries are deriving Arbitrary for deeply nested data structures that I don't want to construct them myself. In these cases it's very difficult to tweak the generated values manually.