Quickcheck Exploration

Cargo.toml

[package]
name = "modelqc"
version = "0.1.0"
authors = ["Caleb Jones <code@calebjones.net>"]

[dependencies]
rand = "*"

main.rs

extern crate rand;

use rand::Rng;
use std::cmp::Ord;
use std::collections::BTreeMap;

mod quickcheck;
use quickcheck::{quickcheck, Gen};

struct Node<K, V> {
    key: K,
    val: V,
    l: Option<Box<Node<K, V>>>,
    r: Option<Box<Node<K, V>>>,
}

impl<K, V> Node<K, V> {
    fn kv(key: K, val: V) -> Self {
        Node {
            key,
            val,
            l: None,
            r: None,
        }
    }
}

pub struct Map<K: Ord, V> {
    root: Option<Node<K, V>>,
}

impl<K: Ord, V> Map<K, V> {
    fn new() -> Self {
        Map { root: None }
    }

    fn insert(&mut self, key: K, val: V) -> Option<V> {
        fn insert_into<K: Ord, V>(node: &mut Node<K, V>, key: K, val: V) -> Option<V> {
            use std::cmp::Ordering::*;
            match key.cmp(&node.key) {
                Less => match node.l {
                    Some(ref mut l) => insert_into(&mut *l, key, val),
                    None => {
                        node.l = Some(Box::new(Node::kv(key, val)));
                        None
                    }
                },
                Equal => Some(std::mem::replace(&mut node.val, val)),
                Greater => match node.r {
                    Some(ref mut r) => insert_into(&mut *r, key, val),
                    None => {
                        node.r = Some(Box::new(Node::kv(key, val)));
                        None
                    }
                },
            }
        }

        match self.root {
            Some(ref mut root) => insert_into(root, key, val),
            None => {
                self.root = Some(Node::kv(key, val));
                None
            }
        }
    }

    fn get(&self, key: &K) -> Option<&V> {
        fn find<'a, K: Ord, V>(node: &'a Node<K, V>, key: &K) -> Option<&'a V> {
            use std::cmp::Ordering::*;
            match key.cmp(&node.key) {
                Less => match node.l {
                    Some(ref l) => find(&*l, key),
                    None => None,
                },
                Equal => Some(&node.val),
                Greater => match node.r {
                    Some(ref r) => find(&*r, key),
                    None => None,
                },
            }
        }

        match self.root {
            Some(ref root) => find(root, key),
            None => None,
        }
    }
}

#[derive(Clone, Copy, Debug)]
enum Op {
    Insert(u8, u8),
    Get(u8),
}

impl Gen for Op {
    fn gen() -> Self {
        let mut rng = rand::thread_rng();
        if rng.gen_weighted_bool(2) {
            Op::Insert(rng.gen(), rng.gen())
        } else {
            Op::Get(rng.gen())
        }
    }
}

macro_rules! require { ($e:expr) => (if ! $e { return false; }) }

fn main() {
    if let Some(x) = quickcheck(100_000, |ops: &Vec<Op>| {
        let mut model = BTreeMap::new();
        let mut test = Map::new();
        for &op in ops {
            match op {
                Op::Insert(k, v) => require!(model.insert(k, v) == test.insert(k, v)),
                Op::Get(k) => require!(model.get(&k) == test.get(&k)),
            }
        }
        true
    }) {
        println!("Counterexample: {:#?}", x);
    }
}

quickcheck.rs

use rand::{self, Rng};

pub trait Gen {
    fn gen() -> Self;
}

pub trait Shrink: Gen {
    fn shrink<Prop>(&self, prop: Prop) -> Self
    where
        Prop: Fn(&Self) -> bool;
}

pub fn quickcheck<T: Shrink, Prop>(iters: usize, prop: Prop) -> Option<T>
where
    Prop: Fn(&T) -> bool,
{
    for _ in 0..iters {
        let case = T::gen();
        if !prop(&case) {
            return Some(case.shrink(prop));
        }
    }
    None
}

impl<T: Gen> Gen for Vec<T> {
    fn gen() -> Self {
        (0..rand::thread_rng().gen_range(0, 200))
            .map(|_| T::gen())
            .collect()
    }
}

impl<T: Gen + Clone> Shrink for Vec<T> {
    fn shrink<Prop>(&self, prop: Prop) -> Self
    where
        Prop: Fn(&Self) -> bool,
    {
        let mut shrunk = self.clone();
        while !shrunk.is_empty() {
            let mut removed = 0;
            for i in (0..shrunk.len()).rev() {
                let mut s = shrunk.clone();
                s.remove(i);
                if !prop(&s) {
                    shrunk = s;
                    removed += 1;
                }
            }
            if removed == 0 {
                break;
            }
        }
        shrunk
    }
}