Rust Quickie: random generator pattern

In rust, you implement Distribution<SomeType> for Standard (from crate rand) to implement random generation of data structures. Things get messy if the data structures are recursive however. One needs to thread state down so that recursive structures are bounded. This pattern wasn’t obvious to me on first glance so I’m writing about it here.

I needed the ability to generate random programs and data structures, but rust doesn’t allow an obvious way to pass down context through Distribution. In the case of recursive data structures, they can become arbitrarily large unless there’s some limit.

Here’s the pattern I discovered for this:

Given this:

pub struct Things { pub elements: Vec<Stuff> }
pub enum Stuff { Simple(usize), Complex(Things) }

First, put the random generation of each constituent in a function or trait that allows state to be passed down:

fn random_stuff<R: Rng + ?Sized>(rng: &mut R, gen_weight: &mut Weight) -> Stuff {
  if rng.gen() {
    Stuff::Simple(rng.gen())
  } else {
    let want_length = rng.gen_range(0..=gen_weight.allowed_len());
    Stuff::Complex((0..=want_length).map(|_| {
      gen_weight.step();
      random_stuff(rng, &mut gen_weight.recurse())
    }).collect())
  }
}

Then use that from your implementation of Distribution with a suitable default Weight.

impl Distribution<Stuff> for Standard {
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Stuff {
        random_stuff(rng, &mut Default::default())
    }
}

Stated like this, taking random_<x> for each element down the tree, passing down the generation state, you can preserve seed idempotence and consistent use of your passed-in Rng while retaining the ability to generate a random version of every object type in the graph via plain random() if desired. Every random generation can be made to do whatever Weight does, but most likely it provides some kind of countdown and distance horizon that limits the size of the data structure being generated.