Generating arbitrary recursive datastructures can overflow the stack pretty easily

[burntsushi]

Generating arbitrary recursive datastructures can overflow the stack pretty easily

[BurntSushi]

I'm not really sure either. One idea is to convert your Arbitrary impl to an iterative algorithm and bound your stack explicitly using the size method on g. Otherwise, I'm not sure what else QuickCheck might do for you? Unless you have a specific idea in mind?

You could try to use my trampoline library for this. Not sure how easy it would be. Basically for some recursive type A you'd build a Trampoline<A> instead. At the end you run the trampoline to get A without blowing the stack.

[BurntSushi]

@darinmorrison Wicked cool. I second your suggestion. :-)

I'll see if I can cook up a demonstration of how it might work. Been meaning to put together some more concrete examples for that :)

[shepmaster]

From what I can gather from the Haskell version, you would use size to control the depth of the tree. I tried to implement that myself, but ran into an issue while trying to reuse the RNG:

impl Arbitrary for ArbitraryTree {
    fn arbitrary<G>(g: &mut G) -> Self
        where G: quickcheck::Gen
    {
        let generate_leaf: bool = g.gen();

        if g.size() == 0 || generate_leaf {
            let leaf: Leaf = Arbitrary::arbitrary(g);
            ArbitraryTree(Box::new(extents))
        } else {
            // let mut inner_gen = quickcheck::StdGen::new(g, g.size() / 2);

            let a: ArbitraryTree = Arbitrary::arbitrary(g);
            let b: ArbitraryTree = Arbitrary::arbitrary(g);

            let c: Box<Algebra> = match g.gen_range(0, 4) {
                0 => Box::new(A { lhs: a, rhs: b }),
                1 => Box::new(B { lhs: a, rhs: b }),
                2 => Box::new(C { lhs: a, rhs: b }),
                3 => Box::new(D { lhs: a, rhs: b }),
                _ => unreachable!(),
            };

            ArbitraryTree(c)
        }
    }
}

If I uncomment the inner_mut line, then I get that

error: the trait `rand::Rng` is not implemented for the type `&mut G`

I'm currently working around it by just

let mut inner_gen = quickcheck::StdGen::new(rand::thread_rng(), g.size() / 2);

[BurntSushi]

@shepmaster Neat, I hadn't thought of doing it that way. I usually just control the size explicitly, e.g., https://github.com/rust-lang/regex/blob/master/regex-syntax/src/properties.rs#L202-L209 (Once the depth reaches the size limit, it hits the base case.)

[shepmaster]

FWIW, I got the idea from this Stack Overflow post, which references the Haskell QuickCheck manual

[bluss]

@shepmaster Rng reuse should be fine now that &mut R where R: Rng implements Rng.

[shepmaster]

@bluss kind of, but it gets ugly... and then doesn't work. 😈

The &mut G would be moved into the new StdGen, so you have to do something for the new size calculation and the next choice:

// ...
let sz = g.size() / 2; 
let choice = g.gen_range(0, 4);

let mut inner_gen = quickcheck::StdGen::new(g, sz);
let a: ArbitraryTree = Arbitrary::arbitrary(g);
let b: ArbitraryTree = Arbitrary::arbitrary(g);

let c: Box<Algebra> = match choice {
// ...

But then this fails with the wonderful error message:

error: overflow evaluating the requirement `core::nonzero::NonZero<*const alloc::rc::RcBox<core::cell::RefCell<test::rand::reseeding::ReseedingRng<test::rand::StdRng, test::rand::ThreadRngReseeder>>>> : core::marker::Sized` [E0275]
src/lib.rs:1809             let generate_leaf: bool = g.gen();
                                                      ^~~~~~~

Of course, I searched for the error message, and would you believe who answered this question 😇? Sadly, I'm not sure how to apply that fix here.

I feel like a nice solution would be to have StdGen (or maybe the trait?) have a way of bifurcating itself.

[bluss]

I have this thing in my "library", I think that means it can work.. (This neat adaptor certainly does).

#[derive(Copy, Clone, Debug)]
/// quickcheck Arbitrary adaptor - half the size of `T` on average
struct Short<T>(T);

impl<T> Deref for Short<T> {
    type Target = T;
    fn deref(&self) -> &T { &self.0 }
}

impl<T> Arbitrary for Short<T>
    where T: Arbitrary
{
    fn arbitrary<G: qc::Gen>(g: &mut G) -> Self {
        let sz = g.size() / 2;
        Short(T::arbitrary(&mut qc::StdGen::new(g, sz)))
    }

    fn shrink(&self) -> Box<Iterator<Item=Self>> {
        Box::new((**self).shrink().map(Short))
    }
}

[bluss]

😄 gotta love when you search and find an answer you wrote yourself.. Sometimes it helps! This time it was a double strike hehe.

[shepmaster]

I think the difference is that your Short isn't recursive on the "outer" type. If I reduce to this:

impl Arbitrary for ArbitraryTree {
    fn arbitrary<G>(g: &mut G) -> Self
        where G: quickcheck::Gen
    {
        ArbitraryTree::arbitrary(&mut quickcheck::StdGen::new(g, 0))
    }
}

Then the error message changes a bit:

error: reached the recursion limit during monomorphization

Which makes sense as StdGen has the RNG as a type parameter. Trying to use g as &mut qc::Gen doesn't work as qc::Gen isn't Sized, and Box<qc::Gen> doesn't implement qc::Gen (and implementing it leads to lifetime woes.

Programming is hard, yo.

[bluss]

I'd probably solve it like the following. It sidesteps the problem by not making a smaller generator, but you could do that too by combining g and the passed down size variable (at each level).

use quickcheck::Arbitrary;

#[derive(Clone, Debug)]
enum ArbitraryTree<T> {
    Leaf(T),
    Branch(Box<ArbitraryTree<T>>, Box<ArbitraryTree<T>>),
}

impl<T> Arbitrary for ArbitraryTree<T> where T: Arbitrary {
    fn arbitrary<G>(g: &mut G) -> Self
        where G: quickcheck::Gen
    {
        let g_size = g.size();
        let sz = g.gen_range(0, g_size);
        println!("tree size: {}", sz);
        arbitrary_tree(g, sz)
    }
}

fn arbitrary_tree<G, T>(g: &mut G, size: usize) -> ArbitraryTree<T>
    where T: Arbitrary,
          G: quickcheck::Gen,
{
    if size == 0 {
        ArbitraryTree::Leaf(T::arbitrary(g))
    } else {
        ArbitraryTree::Branch(
            Box::new(arbitrary_tree(g, size / 2)),
            Box::new(arbitrary_tree(g, size / 2)))
    }
}

#[test]
fn tree() {
    fn prop(t: ArbitraryTree<i32>) -> bool {
        //println!("{:#?}", t);
        true
    }
    quickcheck::quickcheck(prop as fn(_) -> bool);
}

[shepmaster]

Ah, very nice — being able to reuse the same RNG seems like an important thing for repeatability / shrinkability, but I still wonder if this whole concept is a bit wonky as the size no longer is controlled by quickcheck but instead by my own means. I don't know the mechanics deep enough to know if that's a bad idea or not...

[bluss]

Oh that's just me forgetting how to set the size correctly. It should be let sz = usize::arbitrary(g) at the start, then it's all under qc's normal size control.

[shepmaster]

Heh, I wasn't even noticing that — I just meant the general concept of what I'm doing by manipulating the size. But now that I've seen this example, I think I understand what @BurntSushi was trying to point out originally in the regex crate. That also has a function that has a depth parameter (which should be conceptually the same) that is then incremented and provides a eventual bound.