proptest 0.9.3

//-
// Copyright 2017, 2018, 2019 The proptest developers
//
// 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.

use core::{u8, fmt, str};
use core::result::Result;
use crate::std_facade::{Arc, String, Vec, ToOwned};

use byteorder::{ByteOrder, LittleEndian};
use rand::{self, RngCore, Rng, SeedableRng};
use rand_xorshift::XorShiftRng;
use rand_chacha::ChaChaRng;

/// Identifies a particular RNG algorithm supported by proptest.
///
/// Proptest supports dynamic configuration of algorithms to allow it to
/// continue operating with persisted regression files and to allow the
/// configuration to be expressed in the `Config` struct.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum RngAlgorithm {
    /// The [XorShift](https://rust-random.github.io/rand/rand_xorshift/struct.XorShiftRng.html)
    /// algorithm. This was the default up through and including Proptest 0.9.0.
    ///
    /// It is faster than ChaCha but produces lower quality randomness and has
    /// some pathological cases where it may fail to produce outputs that are
    /// random even to casual observation.
    ///
    /// The seed must be exactly 16 bytes.
    XorShift,
    /// The [ChaCha](https://rust-random.github.io/rand/rand_chacha/struct.ChaChaRng.html)
    /// algorithm. This became the default with Proptest 0.9.1.
    ///
    /// The seed must be exactly 32 bytes.
    ChaCha,
    /// This is not an actual RNG algorithm, but instead returns data directly
    /// from its "seed".
    ///
    /// This is useful when Proptest is being driven from some other entropy
    /// source, such as a fuzzer.
    ///
    /// It is the user's responsibility to ensure that the seed is "big
    /// enough". Proptest makes no guarantees about how much data is consumed
    /// from the seed for any particular strategy. If the seed is exhausted,
    /// the RNG panics.
    ///
    /// Note that in cases where a new RNG is to be derived from an existing
    /// one, *the data is split evenly between them*, regardless of how much
    /// entropy is actually needed. This means that combinators like
    /// `prop_perturb` and `prop_flat_map` can require extremely large inputs.
    PassThrough,
    #[allow(missing_docs)] #[doc(hidden)] _NonExhaustive,
}

impl Default for RngAlgorithm {
    fn default() -> Self {
        RngAlgorithm::ChaCha
    }
}

impl RngAlgorithm {
    pub(crate) fn persistence_key(self) -> &'static str {
        match self {
            RngAlgorithm::XorShift => "xs",
            RngAlgorithm::ChaCha => "cc",
            RngAlgorithm::PassThrough => "pt",
            RngAlgorithm::_NonExhaustive => unreachable!(),
        }
    }

    pub(crate) fn from_persistence_key(k: &str) -> Option<Self> {
        match k {
            "xs" => Some(RngAlgorithm::XorShift),
            "cc" => Some(RngAlgorithm::ChaCha),
            "pt" => Some(RngAlgorithm::PassThrough),
            _ => None,
        }
    }
}

// These two are only used for parsing the environment variable
// PROPTEST_RNG_ALGORITHM.
impl str::FromStr for RngAlgorithm {
    type Err = ();
    fn from_str(s: &str) -> Result<Self, ()> {
        RngAlgorithm::from_persistence_key(s).ok_or(())
    }
}
impl fmt::Display for RngAlgorithm {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self.persistence_key())
    }
}

/// Proptest's random number generator.
#[derive(Clone, Debug)]
pub struct TestRng { rng: TestRngImpl }

#[derive(Clone, Debug)]
enum TestRngImpl {
    XorShift(XorShiftRng),
    ChaCha(ChaChaRng),
    PassThrough { off: usize, end: usize, data: Arc<[u8]> },
}

impl RngCore for TestRng {
    fn next_u32(&mut self) -> u32 {
        match &mut self.rng {
            &mut TestRngImpl::XorShift(ref mut rng) =>
                rng.next_u32(),

            &mut TestRngImpl::ChaCha(ref mut rng) =>
                rng.next_u32(),

            &mut TestRngImpl::PassThrough { .. } => {
                let mut buf = [0; 4];
                self.fill_bytes(&mut buf[..]);
                LittleEndian::read_u32(&buf[..])
            },
        }
    }

    fn next_u64(&mut self) -> u64 {
        match &mut self.rng {
            &mut TestRngImpl::XorShift(ref mut rng) =>
                rng.next_u64(),

            &mut TestRngImpl::ChaCha(ref mut rng) =>
                rng.next_u64(),

            &mut TestRngImpl::PassThrough { .. } => {
                let mut buf = [0; 8];
                self.fill_bytes(&mut buf[..]);
                LittleEndian::read_u64(&buf[..])
            },
        }
    }

    fn fill_bytes(&mut self, dest: &mut [u8]) {
        match &mut self.rng {
            &mut TestRngImpl::XorShift(ref mut rng) =>
                rng.fill_bytes(dest),

            &mut TestRngImpl::ChaCha(ref mut rng) =>
                rng.fill_bytes(dest),

            &mut TestRngImpl::PassThrough { ref mut off, end, ref data } => {
                assert!(*off + dest.len() <= end, "out of PassThrough data");
                dest.copy_from_slice(&data[*off..*off + dest.len()]);
                *off += dest.len();
            },
        }
    }

    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rand::Error> {
        match self.rng {
            TestRngImpl::XorShift(ref mut rng) =>
                rng.try_fill_bytes(dest),

            TestRngImpl::ChaCha(ref mut rng) =>
                rng.try_fill_bytes(dest),

            TestRngImpl::PassThrough { ref mut off, end, ref data } => {
                if *off + dest.len() > end {
                    return Err(rand::Error::new(
                        rand::ErrorKind::Unavailable,
                        "out of PassThrough data"));
                }

                dest.copy_from_slice(&data[*off..*off + dest.len()]);
                *off += dest.len();
                Ok(())
            },
        }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(crate) enum Seed {
    XorShift([u8; 16]),
    ChaCha([u8; 32]),
    PassThrough(Option<(usize, usize)>, Arc<[u8]>),
}

impl Seed {
    pub(crate) fn from_bytes(algorithm: RngAlgorithm, seed: &[u8]) -> Self {
        match algorithm {
            RngAlgorithm::XorShift => {
                assert_eq!(16, seed.len(), "XorShift requires a 16-byte seed");
                let mut buf = [0; 16];
                buf.copy_from_slice(seed);
                Seed::XorShift(buf)
            },

            RngAlgorithm::ChaCha => {
                assert_eq!(32, seed.len(), "ChaCha requires a 32-byte seed");
                let mut buf = [0; 32];
                buf.copy_from_slice(seed);
                Seed::ChaCha(buf)
            },

            RngAlgorithm::PassThrough =>
                Seed::PassThrough(None, seed.into()),

            RngAlgorithm::_NonExhaustive => unreachable!(),
        }
    }

    pub(crate) fn from_persistence(string: &str) -> Option<Seed> {
        fn from_base16(dst: &mut [u8], src: &str) -> Option<()> {
            if dst.len() * 2 != src.len() {
                return None;
            }

            for (dst_byte, src_pair) in dst.into_iter().zip(src.as_bytes().chunks(2)) {
                *dst_byte = u8::from_str_radix(str::from_utf8(src_pair).ok()?, 16).ok()?;
            }

            Some(())
        }

        let parts = string.trim().split(char::is_whitespace).collect::<Vec<_>>();
        RngAlgorithm::from_persistence_key(&parts[0]).and_then(|alg| match alg {
            RngAlgorithm::XorShift => {
                if 5 != parts.len() {
                    return None;
                }

                let mut dwords = [0u32; 4];
                for (dword, part) in (&mut dwords[..]).into_iter().zip(&parts[1..]) {
                    *dword = part.parse().ok()?;
                }

                let mut seed = [0u8; 16];
                LittleEndian::write_u32_into(&dwords[..], &mut seed[..]);
                Some(Seed::XorShift(seed))
            },

            RngAlgorithm::ChaCha => {
                if 2 != parts.len() {
                    return None;
                }

                let mut seed = [0u8; 32];
                from_base16(&mut seed, &parts[1])?;
                Some(Seed::ChaCha(seed))
            },

            RngAlgorithm::PassThrough => {
                if 1 == parts.len() {
                    return Some(Seed::PassThrough(None, vec![].into()));
                }

                if 2 != parts.len() {
                    return None;
                }

                let mut seed = vec![0u8; parts[1].len() / 2];
                from_base16(&mut seed, &parts[1])?;
                Some(Seed::PassThrough(None, seed.into()))
            },

            RngAlgorithm::_NonExhaustive => unreachable!(),
        })
    }

    pub(crate) fn to_persistence(&self) -> String {
        fn to_base16(dst: &mut String, src: &[u8]) {
            for byte in src {
                dst.push_str(&format!("{:02x}", byte));
            }
        }

        match *self {
            Seed::XorShift(ref seed) => {
                let mut dwords = [0u32; 4];
                LittleEndian::read_u32_into(seed, &mut dwords[..]);
                format!("{} {} {} {} {}",
                        RngAlgorithm::XorShift.persistence_key(),
                        dwords[0], dwords[1], dwords[2], dwords[3])
            },

            Seed::ChaCha(ref seed) => {
                let mut string =
                    RngAlgorithm::ChaCha.persistence_key().to_owned();
                string.push(' ');
                to_base16(&mut string, seed);
                string
            },

            Seed::PassThrough(bounds, ref data) => {
                let data = bounds
                    .map_or(&data[..], |(start, end)| &data[start..end]);
                let mut string =
                    RngAlgorithm::PassThrough.persistence_key().to_owned();
                string.push(' ');
                to_base16(&mut string, data);
                string
            },
        }
    }
}

impl TestRng {
    /// Create a new RNG with the given algorithm and seed.
    ///
    /// Any RNG created with the same algorithm-seed pair will produce the same
    /// sequence of values on all systems and all supporting versions of
    /// proptest.
    ///
    /// ## Panics
    ///
    /// Panics if `seed` is not an appropriate length for `algorithm`.
    pub fn from_seed(algorithm: RngAlgorithm, seed: &[u8]) -> Self {
        TestRng::from_seed_internal(Seed::from_bytes(algorithm, seed))
    }

    /// Construct a default TestRng from entropy.
    pub(crate) fn default_rng(algorithm: RngAlgorithm) -> Self {
        #[cfg(feature = "std")]
        {
            use rand::FromEntropy;
            Self { rng: match algorithm {
                RngAlgorithm::XorShift =>
                    TestRngImpl::XorShift(XorShiftRng::from_entropy()),
                RngAlgorithm::ChaCha =>
                    TestRngImpl::ChaCha(ChaChaRng::from_entropy()),
                RngAlgorithm::PassThrough =>
                    panic!("cannot create default instance of PassThrough"),
                RngAlgorithm::_NonExhaustive => unreachable!(),
            } }
        }
        #[cfg(not(feature = "std"))]
        Self::deterministic_rng(algorithm)
    }

    /// Returns a `TestRng` with a particular hard-coded seed.
    ///
    /// The seed value will always be the same for a particular version of
    /// Proptest and algorithm, but may change across releases.
    ///
    /// This is useful for testing things like strategy implementations without
    /// risking getting "unlucky" RNGs which deviate from average behaviour
    /// enough to cause spurious failures. For example, a strategy for `bool`
    /// which is supposed to produce `true` 50% of the time might have a test
    /// which checks that the distribution is "close enough" to 50%. If every
    /// test run starts with a different RNG, occasionally there will be
    /// spurious test failures when the RNG happens to produce a very skewed
    /// distribution. Using this or `TestRunner::deterministic()` avoids such
    /// issues.
    pub fn deterministic_rng(algorithm: RngAlgorithm) -> Self {
        Self::from_seed_internal(match algorithm {
            RngAlgorithm::XorShift => Seed::XorShift([
                0xf4, 0x16, 0x16, 0x48, 0xc3, 0xac, 0x77, 0xac,
                0x72, 0x20, 0x0b, 0xea, 0x99, 0x67, 0x2d, 0x6d,
            ]),
            RngAlgorithm::ChaCha => Seed::ChaCha([
                0xf4, 0x16, 0x16, 0x48, 0xc3, 0xac, 0x77, 0xac,
                0x72, 0x20, 0x0b, 0xea, 0x99, 0x67, 0x2d, 0x6d,
                0xca, 0x9f, 0x76, 0xaf, 0x1b, 0x09, 0x73, 0xa0,
                0x59, 0x22, 0x6d, 0xc5, 0x46, 0x39, 0x1c, 0x4a,
            ]),
            RngAlgorithm::PassThrough =>
                panic!("deterministic RNG not available for PassThrough"),
            RngAlgorithm::_NonExhaustive => unreachable!(),
        })
    }

    /// Construct a TestRng by the perturbed randomized seed
    /// from an existing TestRng.
    pub(crate) fn gen_rng(&mut self) -> Self {
        Self::from_seed_internal(self.new_rng_seed())
    }

    /// Overwrite the given TestRng with the provided seed.
    pub(crate) fn set_seed(&mut self, seed: Seed) {
        *self = Self::from_seed_internal(seed);
    }

    /// Generate a new randomized seed, set it to this TestRng,
    /// and return the seed.
    pub(crate) fn gen_get_seed(&mut self) -> Seed {
        let seed = self.new_rng_seed();
        self.set_seed(seed.clone());
        seed
    }

    /// Randomize a perturbed randomized seed from the given TestRng.
    pub(crate) fn new_rng_seed(&mut self) -> Seed {
        match self.rng {
            TestRngImpl::XorShift(ref mut rng) => {
                let mut seed = rng.gen::<[u8;16]>();

                // Directly using XorShiftRng::from_seed() at this point would
                // result in rng and the returned value being exactly the same.
                // Perturb the seed with some arbitrary values to prevent this.
                for word in seed.chunks_mut(4) {
                    word[3] ^= 0xde;
                    word[2] ^= 0xad;
                    word[1] ^= 0xbe;
                    word[0] ^= 0xef;
                }

                Seed::XorShift(seed)
            },

            TestRngImpl::ChaCha(ref mut rng) =>
                Seed::ChaCha(rng.gen()),

            TestRngImpl::PassThrough { ref mut off, ref mut end, ref data } => {
                let len = *end - *off;
                let child_start = *off + len / 2;
                let child_end = *off + len;
                *end = child_start;
                Seed::PassThrough(Some((child_start, child_end)), Arc::clone(data))
            },
        }
    }

    /// Construct a TestRng from a given seed.
    fn from_seed_internal(seed: Seed) -> Self {
        Self { rng: match seed {
            Seed::XorShift(seed) =>
                TestRngImpl::XorShift(XorShiftRng::from_seed(seed)),

            Seed::ChaCha(seed) =>
                TestRngImpl::ChaCha(ChaChaRng::from_seed(seed)),

            Seed::PassThrough(bounds, data) => {
                let (start, end) = bounds.unwrap_or((0, data.len()));
                TestRngImpl::PassThrough { off: start, end, data }
            }
        } }
    }
}

#[cfg(test)]
mod test {
    use crate::std_facade::Vec;

    use rand::{Rng, RngCore};

    use super::{RngAlgorithm, Seed, TestRng};
    use crate::arbitrary::any;
    use crate::strategy::*;

    proptest! {
        #[test]
        fn gen_parse_seeds(
            seed in prop_oneof![
                any::<[u8;16]>().prop_map(Seed::XorShift),
                any::<[u8;32]>().prop_map(Seed::ChaCha),
                any::<Vec<u8>>().prop_map(|data| Seed::PassThrough(None, data.into())),
            ])
        {
            assert_eq!(seed, Seed::from_persistence(&seed.to_persistence()).unwrap());
        }

        #[test]
        fn rngs_dont_clone_self_on_genrng(
            seed in prop_oneof![
                any::<[u8;16]>().prop_map(Seed::XorShift),
                any::<[u8;32]>().prop_map(Seed::ChaCha),
                Just(()).prop_perturb(|_, mut rng| {
                    let mut buf = vec![0u8; 2048];
                    rng.fill_bytes(&mut buf);
                    Seed::PassThrough(None, buf.into())
                }),
            ])
        {
            type Value = [u8;32];
            let orig = TestRng::from_seed_internal(seed);

            {
                let mut rng1 = orig.clone();
                let mut rng2 = rng1.gen_rng();
                assert_ne!(rng1.gen::<Value>(), rng2.gen::<Value>());
            }

            {
                let mut rng1 = orig.clone();
                let mut rng2 = rng1.gen_rng();
                let mut rng3 = rng1.gen_rng();
                let mut rng4 = rng2.gen_rng();
                let a = rng1.gen::<Value>();
                let b = rng2.gen::<Value>();
                let c = rng3.gen::<Value>();
                let d = rng4.gen::<Value>();
                assert_ne!(a, b);
                assert_ne!(a, c);
                assert_ne!(a, d);
                assert_ne!(b, c);
                assert_ne!(b, d);
                assert_ne!(c, d);
            }
        }
    }

    #[test]
    fn passthrough_rng_behaves_properly() {
        let mut rng = TestRng::from_seed(
            RngAlgorithm::PassThrough,
            &[0xDE, 0xC0, 0x12, 0x34,
              0x56, 0x78, 0xFE, 0xCA, 0xEF, 0xBE, 0xAD, 0xDE,
              0x01, 0x02, 0x03]);

        assert_eq!(0x3412C0DE, rng.next_u32());
        assert_eq!(0xDEADBEEFCAFE7856, rng.next_u64());

        let mut buf = [0u8; 4];
        assert!(rng.try_fill_bytes(&mut buf[0..4]).is_err());
        rng.fill_bytes(&mut buf[0..2]);
        rng.fill_bytes(&mut buf[2..3]);
        assert_eq!([1, 2, 3, 0], buf);
    }
}