proptest-quickcheck-interop 1.0.5

//-
// Copyright 2017 Mazdak Farrokhzad
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! [`proptest`] is a property testing framework (i.e., the [`QuickCheck`] family)
//! inspired by the [Hypothesis](http://hypothesis.works/) framework for
//! Python.
//!
//! [`quickcheck`] is another property testing framework for Rust which uses
//! a shrinking logic similar to Haskell's [`QuickCheck`].
//!
//! **This crate provides interoperability between quickcheck and proptest.**
//! Currently, this is one way - if you've implemented quickcheck's
//! [`Arbitrary`] trait as well as [`Debug`], which is a temporary requirement,
//! then you may get back the equivalent [`Strategy`] in proptest.
//!
//! ## Status of this crate
//!
//! This crate is unlikely to see major changes. Any breaking changes
//! are only likely to come as a result of changes in the dependencies used by
//! this crate, in particular proptest or quickcheck. When any of those crates
//! make breaking changes that affect this crate, then the major version of
//! this crate will be bumped.
//!
//! See the [changelog] for a full list of substantial historical changes,
//! breaking and otherwise.
//!
//! ## Using the interoperability layer
//!
//! Assuming that you already have a `Cargo.toml` file in your project with,
//! among other things, the following:
//!
//! ```toml 
//! [dependencies]
//!
//! quickcheck = "0.5.0"
//! proptest   = "0.3.4"
//! ```
//!
//! Now add this crate to your dependencies:
//! 
//! ```toml
//! [dependencies]
//!
//! quickcheck = "0.5.0"
//! proptest   = "0.3.4"
//! proptest_quickcheck_interop = "1.0.5"
//! ```
//!
//! Let's now assume that `usize` is a complex type for which you have
//! implemented `quickcheck::Arbitrary`. You wish you reuse this in proptest
//! or if you simply prefer the implementation provided by quickcheck.
//! To do so, you can use [`from_qc`]:
//!
//! ```rust
//! // Import crates:
//! #[macro_use] extern crate proptest;
//! extern crate proptest_quickcheck_interop as pqci;
//!
//! // And what we need into our scope:
//! use proptest::strategy::Strategy;
//! use pqci::from_qc;
//!
//! /// Given a usize returns the nearest usize that is also even.
//! fn make_even(x: usize) -> usize {
//!     if x % 2 == 1 { x - 1 } else { x }
//! }
//!
//! proptest! {
//!    /// A property asserting that make_even always produces an even usize.
//!    fn always_even(ref x in from_qc::<usize>().prop_map(make_even)) {
//!        prop_assert!(x % 2 == 0);
//!    }
//! }
//!
//! fn main() {
//!     always_even();
//! }
//! ```
//!
//! If you want to control the `size` of the input generated by quickcheck
//! you may instead use [`from_qc_sized(size)`][`from_qc_sized`]. If you use,
//! [`from_qc`], then the default size used by quickcheck is used.
//!
//! [`from_qc`]: https://docs.rs/proptest-quickcheck-interop/1.0.5/proptest_quickcheck_interop/fn.from_qc.html
//! [`from_qc_sized`]: https://docs.rs/proptest-quickcheck-interop/1.0.5/proptest_quickcheck_interop/fn.from_qc_sized.html
//!
//! [changelog]:
//! https://github.com/Centril/proptest-quickcheck-interop/blob/master/CHANGELOG.md
//!
//! [`Debug`]: https://doc.rust-lang.org/nightly/std/fmt/trait.Debug.html
//!
//! [`Arbitrary`]: https://docs.rs/quickcheck/0.5.0/quickcheck/trait.Arbitrary.html
//!
//! [`proptest`]: https://crates.io/crates/proptest
//!
//! [`quickcheck`]: https://crates.io/crates/quickcheck
//!
//! [`Strategy`]: https://docs.rs/proptest/0.3.4/proptest/strategy/trait.Strategy.html

#![deny(missing_docs)]

//==============================================================================
// Imports:
//==============================================================================

extern crate rand;
extern crate proptest;
extern crate quickcheck as quickcheck_crate;

use std::mem;
use std::marker::PhantomData;
use std::fmt::{Debug, Formatter, Result as FResult};

use quickcheck_crate::{Arbitrary, Gen, Rng};
use rand::XorShiftRng;

use proptest::strategy::*;
use proptest::test_runner::TestRunner;

//==============================================================================
// Convenience API:
//==============================================================================

/// Constructs a new [`Strategy`] for any type that implements [`quickcheck`]'s
/// [`Arbitrary`] trait as well as [`Debug`] (a temporary requirement).
/// You may use this to gain interoperability by reusing implementations of
/// [`Arbitrary`] that you've already defined for some type.
///
/// Using this version, the size parameter controlling the size of inputs will
/// be the default one used by `quickcheck`. This parameter is passed to the
/// implementation of `Arbitrary`. If you want to provide some other value,
/// you may instead use [`from_qc_sized`].
///
/// [`Debug`]: https://doc.rust-lang.org/nightly/std/fmt/trait.Debug.html
/// [`Arbitrary`]: https://docs.rs/quickcheck/0.5.0/quickcheck/trait.Arbitrary.html
/// [`from_qc_sized`]: https://docs.rs/proptest-quickcheck-interop//proptest_quickcheck_interop/fn.from_qc_sized.html
/// [`quickcheck`]: https://crates.io/crates/quickcheck
/// [`Strategy`]: https://docs.rs/proptest/0.3.4/proptest/strategy/trait.Strategy.html
pub fn from_qc<A: Arbitrary + Debug>() -> QCStrategy<A> {
    QCStrategy::new(qc_gen_size())
}

/// Copied from:
/// https://docs.rs/quickcheck/0.5.0/src/quickcheck/tester.rs.html#35-41
/// TODO: Remove if @burntsushi makes this pub.
fn qc_gen_size() -> usize {
    use std::env;
    let default = 100;
    match env::var("QUICKCHECK_GENERATOR_SIZE") {
        Ok(val) => val.parse().unwrap_or(default),
        Err(_) => default,
    }
}

/// Constructs a new [`Strategy`] for any type that implements [`quickcheck`]'s
/// [`Arbitrary`] trait as well as [`Debug`] (a temporary requirement).
/// You may use this to gain interoperability by reusing implementations of
/// [`Arbitrary`] that you've already defined for some type.
///
/// Using this version, you may provide a size parameter controlling the size
/// of inputs. This parameter is passed to the implementation of `Arbitrary`.
///
/// [`Debug`]: https://doc.rust-lang.org/nightly/std/fmt/trait.Debug.html
/// [`Arbitrary`]: https://docs.rs/quickcheck/0.5.0/quickcheck/trait.Arbitrary.html
/// [`quickcheck`]: https://crates.io/crates/quickcheck
/// [`Strategy`]: https://docs.rs/proptest/0.3.4/proptest/strategy/trait.Strategy.html
pub fn from_qc_sized<A: Arbitrary + Debug>(size: usize) -> QCStrategy<A> {
    QCStrategy::new(size)
}

//==============================================================================
// The strategy
//==============================================================================

/// `QCStrategy` is a [`Strategy`] that provides interoperability with
/// [`quickcheck`]'s [`Arbitrary`] trait. If you have any type implementing
/// [`Arbitrary`] and [`Debug`], which a temporary requirement, then you may
/// get back the equivalent Strategy in proptest.
///
/// [`Debug`]: https://doc.rust-lang.org/nightly/std/fmt/trait.Debug.html
/// [`Arbitrary`]: https://docs.rs/quickcheck/0.5.0/quickcheck/trait.Arbitrary.html
/// [`quickcheck`]: https://crates.io/crates/quickcheck
/// [`Strategy`]: https://docs.rs/proptest/0.3.4/proptest/strategy/trait.Strategy.html
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct QCStrategy<A: Arbitrary + Debug> {
    __ph: PhantomData<A>,
    size: usize,
}

/// The [`ValueTree`] implementation for [`QCStrategy`].
///
/// [`QCStrategy`]: https://docs.rs/proptest-quickcheck-interop//proptest_quickcheck_interop/struct.QCStrategy.html
/// [`ValueTree`]: https://docs.rs/proptest/0.3.4/proptest/strategy/trait.ValueTree.html
pub struct QCValueTree<A: Debug> {
    curr: A,
    prev: Option<A>,
    shrinker: Box<Iterator<Item = A>>
}

impl<A: Arbitrary + Debug> QCStrategy<A> {
    /// Constructs a new `QCStrategy` given a `size` parameter that:
    ///
    /// > controls the size of random values generated. For example, it
    /// > specifies the maximum length of a randomly generated vector and also
    /// > will specify the maximum magnitude of a randomly generated number.
    ///
    /// as defined by [`quickcheck`]
    ///
    /// [`quickcheck`]: https://crates.io/crates/quickcheck
    pub fn new(size: usize) -> Self {
        Self { __ph: PhantomData, size }
    }
}

impl<A: Debug> QCValueTree<A> {
    /// Constructs a new `QCValueTree`, that is the [`ValueTree`] for
    /// [`QCStrategy`] given:
    /// + the current value,
    /// + the iterator producing increasingly shrunken versions of the current
    /// value given.
    ///
    /// [`QCStrategy`]: struct.QCStrategy
    /// [`ValueTree`]: trait.ValueTree
    fn new(curr: A, shrinker: Box<Iterator<Item = A>>) -> Self {
        Self { prev: None, curr, shrinker }
    }
}

type NewTree<S> = Result<<S as Strategy>::Value, String>;

impl<A: Arbitrary + Debug> Strategy for QCStrategy<A> {
    type Value = QCValueTree<A>;

    fn new_value(&self, runner: &mut TestRunner) -> NewTree<Self> {
        let mut gen = XorShiftGen::new(runner.rng(), self.size);
        let curr = A::arbitrary(&mut gen);
        let shrinker = curr.shrink();
        Ok(QCValueTree::new(curr, shrinker))
    }
}

impl<A: Clone + Debug> ValueTree for QCValueTree<A> {
    type Value = A;

    fn current(&self) -> Self::Value {
        self.curr.clone()
    }

    fn complicate(&mut self) -> bool {
        // We can only complicate if we previously simplified.
        // Complicating twice in a row without interleaved simplification
        // is guaranteed to always yield false for the second call.
        if let Some(prev) = self.prev.take() {
            // Throw away the current value!
            self.curr = prev;
            true
        } else {
            false
        }
    }

    fn simplify(&mut self) -> bool {
        if let Some(simpler) = self.shrinker.next() {
            // Throw away the previous value and set the current value as prev.
            // Advance the iterator and set the current value to the next one.
            self.prev = Some(mem::replace(&mut self.curr, simpler));
            true
        } else {
            // Successive calls to .next() are now assumed to yield None,
            // Can't shrink anymore.
            false
        }
    }
}

impl<A: Debug> Debug for QCValueTree<A> {
    fn fmt(&self, fmt: &mut Formatter) -> FResult {
        fmt.debug_struct("QCValueTree")
           .field("curr", &self.curr)
           .field("prev", &self.prev)
           // We could change shrinker to be : Vec<A> instead, but that seems
           // not worth the cost of maintaining all the shrinked-to elements
           // in the ValueTree. If the iterator is side-effecting the behaviour
           // may also be quite strange.
           .field("shrinker", &"<iterator>")
           .finish()
    }
}

//==============================================================================
// XorShiftGen wrapper
//==============================================================================

/// A wrapper around a mutable reference of [`XorShiftRng`] and a `size` that
/// controls the size of random values generated makes for an implementation
/// of a [`Gen`].
///
/// [`XorShiftRng`]: https://docs.rs/rand/0.3.18/rand/struct.XorShiftRng.html
/// [`Gen`]: https://docs.rs/quickcheck/0.5.0/quickcheck/trait.Gen.html
#[derive(Debug)]
struct XorShiftGen<'a> {
    rng:  &'a mut XorShiftRng,
    size: usize,
}

impl<'a> XorShiftGen<'a> {
    /// Construct a new generator given the backing RNG and the
    /// size controlling the size of random values generated.
    pub fn new(rng: &'a mut XorShiftRng, size: usize) -> Self {
        Self { rng, size }
    }
}

impl<'a> Rng for XorShiftGen<'a> {
    fn next_u32(&mut self) -> u32 { self.rng.next_u32() }
}

impl<'a> Gen for XorShiftGen<'a> {
    fn size(&self) -> usize { self.size }
}

//==============================================================================
// Tests
//==============================================================================

#[cfg(test)]
mod tests {
    use super::*;

    impl Clone for QCValueTree<Vec<u32>> {
        /// Only implemented so that the implementation can be tested.
        /// As to why this is not a public API, read the note below.
        fn clone(&self) -> Self {
            // We assume that:
            //
            // let x = A::arbitrary(gen);
            // let s1 = x.clone().shrink();
            // let s2 = x.shrink();
            // assert_eq(s1.collect::<Vec<A>>(), s2.collect::<Vec<A>>());
            //
            // always holds. In other words, that shrinking is deterministic.
            // We also assume that:
            //
            // A::arbitrary(gen);
            // let s = x.shrink();
            // let y = x.next()?;
            // assert_eq!(x.next(), y.shrink().next());
            //
            // always holds.
            //
            // It may not actually hold for all A, but we don't care, as we only
            // provide Clone for testing purposes and we pick A = u32 for which
            // it always holds.
            QCValueTree {
                prev: self.prev.clone(),
                curr: self.curr.clone(),
                shrinker: self.curr.shrink()
            }
        }
    }

    #[test]
    fn contract_followed_by_qc_strategy() {
        check_strategy_sanity(from_qc_sized::<Vec<u32>>(10), None);
    }
}