[WIP] stateful property testing

[Horusiath]

This is an initial PR with API for building stateful property-based tests using the StateMachine<T>. To bring the issue closer, here are the docs about the same feature implemented in Erlang and F#.

API so far was extended by two new structures:

• Model trait which defines 3 functions:
  • run which mutates current model's state given the generated operation
  • next which is supposed to produce new operation to be applied
  • pre which is supposed to check if a given operation has any sense in a context of a current model's state.
• StateMachine<T: Model> which is just a configurable wrapper around model, which implements Testable trait.

The minimal case for non-negative counter with inc/dec functions could look like this:

#[derive(Clone, Debug, Default)]
struct Counter(u32);

impl Counter {
  fn inc(&mut self) -> u32 {
    self.0 += 1;
    self.0
  }

  fn dec(&mut self) -> u32 {
    self.0 -= 1; // better not to run below 0
    self.0
  }
}

// define test model

#[derive(Debug, Clone, PartialEq, Eq)]
enum CounterOp {
    Increment,
    Decrement,
}

impl Arbitrary for CounterOp {
    fn arbitrary<G: Gen>(g: &mut G) -> Self {
        if g.next_u32() % 2 == 0 {
            CounterOp::Increment
        } else {
            CounterOp::Decrement
        }
    }
}

#[derive(Default, Debug)]
struct CounterSpec {
    counter: Counter,
}

impl Model for CounterSpec {
    type Operation = CounterOp;

    fn pre(&self, op: &Self::Operation) -> bool {
        match op {
            CounterOp::Decrement => self.counter.0 > 0,
            _ => true // increments are always safe
        }
    }

    fn run(&mut self, op: &Self::Operation) -> bool {
        match op {
            CounterOp::Increment => {
                let expected = self.counter.0 + 1;
                expected == self.counter.inc()
            },
            CounterOp::Decrement => {
                let expected = self.counter.0 - 1;
                expected == self.counter.dec()
            }
        }
    }
}

#[test]
fn test_counter() {
    let spec = StateMachine::from(CounterSpec::default)
        .max_ops(50);
    QuickCheck::with_gen(StdGen::new(OsRng, 129))
        .quickcheck(spec);
}

At the moment, this library doesn't try to shrink the sequence of operations in case of failure.

[BurntSushi]

Thanks for the PR!

Unfortunately, I'm quite sure what to do with this just yet. I don't really have the bandwidth to dig into this. Could you say a few sentences at a very high level about what this does and how you'd want it integrated into this library? Additionally, is this something that could live in a different crate?

[Horusiath]

I'm not sure yet - I'd love to get some directions to get deeper insight into how shrinking works and how to integrate them into quickcheck. I'm quite tight on time myself, but would love to finish that contribution (especially given that it'd help me in my daily work).

[BurntSushi]

All righty. I definitely don't have the time to mentor this, sorry. :( I'm going to close this for now, but if you happen to get this into another crate I would be happy to link to this in the README.