[rustc.git] / vendor / rand-0.7.3 / src / distributions / other.rs

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

//! The implementations of the `Standard` distribution for other built-in types.

use core::char;
use core::num::Wrapping;

use crate::distributions::{Distribution, Standard, Uniform};
use crate::Rng;

// ----- Sampling distributions -----

/// Sample a `char`, uniformly distributed over ASCII letters and numbers:
/// a-z, A-Z and 0-9.
///
/// # Example
///
/// ```
/// use std::iter;
/// use rand::{Rng, thread_rng};
/// use rand::distributions::Alphanumeric;
///
/// let mut rng = thread_rng();
/// let chars: String = iter::repeat(())
///         .map(|()| rng.sample(Alphanumeric))
///         .take(7)
///         .collect();
/// println!("Random chars: {}", chars);
/// ```
#[derive(Debug)]
pub struct Alphanumeric;


// ----- Implementations of distributions -----

impl Distribution<char> for Standard {
    #[inline]
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char {
        // A valid `char` is either in the interval `[0, 0xD800)` or
        // `(0xDFFF, 0x11_0000)`. All `char`s must therefore be in
        // `[0, 0x11_0000)` but not in the "gap" `[0xD800, 0xDFFF]` which is
        // reserved for surrogates. This is the size of that gap.
        const GAP_SIZE: u32 = 0xDFFF - 0xD800 + 1;

        // Uniform::new(0, 0x11_0000 - GAP_SIZE) can also be used but it
        // seemed slower.
        let range = Uniform::new(GAP_SIZE, 0x11_0000);

        let mut n = range.sample(rng);
        if n <= 0xDFFF {
            n -= GAP_SIZE;
        }
        unsafe { char::from_u32_unchecked(n) }
    }
}

impl Distribution<char> for Alphanumeric {
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char {
        const RANGE: u32 = 26 + 26 + 10;
        const GEN_ASCII_STR_CHARSET: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
                abcdefghijklmnopqrstuvwxyz\
                0123456789";
        // We can pick from 62 characters. This is so close to a power of 2, 64,
        // that we can do better than `Uniform`. Use a simple bitshift and
        // rejection sampling. We do not use a bitmask, because for small RNGs
        // the most significant bits are usually of higher quality.
        loop {
            let var = rng.next_u32() >> (32 - 6);
            if var < RANGE {
                return GEN_ASCII_STR_CHARSET[var as usize] as char;
            }
        }
    }
}

impl Distribution<bool> for Standard {
    #[inline]
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> bool {
        // We can compare against an arbitrary bit of an u32 to get a bool.
        // Because the least significant bits of a lower quality RNG can have
        // simple patterns, we compare against the most significant bit. This is
        // easiest done using a sign test.
        (rng.next_u32() as i32) < 0
    }
}

macro_rules! tuple_impl {
    // use variables to indicate the arity of the tuple
    ($($tyvar:ident),* ) => {
        // the trailing commas are for the 1 tuple
        impl< $( $tyvar ),* >
            Distribution<( $( $tyvar ),* , )>
            for Standard
            where $( Standard: Distribution<$tyvar> ),*
        {
            #[inline]
            fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> ( $( $tyvar ),* , ) {
                (
                    // use the $tyvar's to get the appropriate number of
                    // repeats (they're not actually needed)
                    $(
                        _rng.gen::<$tyvar>()
                    ),*
                    ,
                )
            }
        }
    }
}

impl Distribution<()> for Standard {
    #[allow(clippy::unused_unit)]
    #[inline]
    fn sample<R: Rng + ?Sized>(&self, _: &mut R) -> () {
        ()
    }
}
tuple_impl! {A}
tuple_impl! {A, B}
tuple_impl! {A, B, C}
tuple_impl! {A, B, C, D}
tuple_impl! {A, B, C, D, E}
tuple_impl! {A, B, C, D, E, F}
tuple_impl! {A, B, C, D, E, F, G}
tuple_impl! {A, B, C, D, E, F, G, H}
tuple_impl! {A, B, C, D, E, F, G, H, I}
tuple_impl! {A, B, C, D, E, F, G, H, I, J}
tuple_impl! {A, B, C, D, E, F, G, H, I, J, K}
tuple_impl! {A, B, C, D, E, F, G, H, I, J, K, L}

macro_rules! array_impl {
    // recursive, given at least one type parameter:
    {$n:expr, $t:ident, $($ts:ident,)*} => {
        array_impl!{($n - 1), $($ts,)*}

        impl<T> Distribution<[T; $n]> for Standard where Standard: Distribution<T> {
            #[inline]
            fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] {
                [_rng.gen::<$t>(), $(_rng.gen::<$ts>()),*]
            }
        }
    };
    // empty case:
    {$n:expr,} => {
        impl<T> Distribution<[T; $n]> for Standard {
            fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] { [] }
        }
    };
}

array_impl! {32, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T,}

impl<T> Distribution<Option<T>> for Standard
where Standard: Distribution<T>
{
    #[inline]
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<T> {
        // UFCS is needed here: https://github.com/rust-lang/rust/issues/24066
        if rng.gen::<bool>() {
            Some(rng.gen())
        } else {
            None
        }
    }
}

impl<T> Distribution<Wrapping<T>> for Standard
where Standard: Distribution<T>
{
    #[inline]
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Wrapping<T> {
        Wrapping(rng.gen())
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    use crate::RngCore;
    #[cfg(all(not(feature = "std"), feature = "alloc"))] use alloc::string::String;

    #[test]
    fn test_misc() {
        let rng: &mut dyn RngCore = &mut crate::test::rng(820);

        rng.sample::<char, _>(Standard);
        rng.sample::<bool, _>(Standard);
    }

    #[cfg(feature = "alloc")]
    #[test]
    fn test_chars() {
        use core::iter;
        let mut rng = crate::test::rng(805);

        // Test by generating a relatively large number of chars, so we also
        // take the rejection sampling path.
        let word: String = iter::repeat(())
            .map(|()| rng.gen::<char>())
            .take(1000)
            .collect();
        assert!(word.len() != 0);
    }

    #[test]
    fn test_alphanumeric() {
        let mut rng = crate::test::rng(806);

        // Test by generating a relatively large number of chars, so we also
        // take the rejection sampling path.
        let mut incorrect = false;
        for _ in 0..100 {
            let c = rng.sample(Alphanumeric);
            incorrect |= !((c >= '0' && c <= '9') ||
                           (c >= 'A' && c <= 'Z') ||
                           (c >= 'a' && c <= 'z') );
        }
        assert!(incorrect == false);
    }

    #[test]
    fn value_stability() {
        fn test_samples<T: Copy + core::fmt::Debug + PartialEq, D: Distribution<T>>(
            distr: &D, zero: T, expected: &[T],
        ) {
            let mut rng = crate::test::rng(807);
            let mut buf = [zero; 5];
            for x in &mut buf {
                *x = rng.sample(&distr);
            }
            assert_eq!(&buf, expected);
        }

        test_samples(&Standard, 'a', &[
            '\u{8cdac}',
            '\u{a346a}',
            '\u{80120}',
            '\u{ed692}',
            '\u{35888}',
        ]);
        test_samples(&Alphanumeric, 'a', &['h', 'm', 'e', '3', 'M']);
        test_samples(&Standard, false, &[true, true, false, true, false]);
        test_samples(&Standard, None as Option<bool>, &[
            Some(true),
            None,
            Some(false),
            None,
            Some(false),
        ]);
        test_samples(&Standard, Wrapping(0i32), &[
            Wrapping(-2074640887),
            Wrapping(-1719949321),
            Wrapping(2018088303),
            Wrapping(-547181756),
            Wrapping(838957336),
        ]);

        // We test only sub-sets of tuple and array impls
        test_samples(&Standard, (), &[(), (), (), (), ()]);
        test_samples(&Standard, (false,), &[
            (true,),
            (true,),
            (false,),
            (true,),
            (false,),
        ]);
        test_samples(&Standard, (false, false), &[
            (true, true),
            (false, true),
            (false, false),
            (true, false),
            (false, false),
        ]);

        test_samples(&Standard, [0u8; 0], &[[], [], [], [], []]);
        test_samples(&Standard, [0u8; 3], &[
            [9, 247, 111],
            [68, 24, 13],
            [174, 19, 194],
            [172, 69, 213],
            [149, 207, 29],
        ]);
    }
}
Commit	Line	Data
0731742a	1	// Copyright 2018 Developers of the Rand project.
b7449926 XL	2	//
	3	// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
	4	// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
	5	// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
	6	// option. This file may not be copied, modified, or distributed
	7	// except according to those terms.
	8
	9	//! The implementations of the `Standard` distribution for other built-in types.
	10
	11	use core::char;
	12	use core::num::Wrapping;
	13
416331ca	14	use crate::distributions::{Distribution, Standard, Uniform};
dfeec247	15	use crate::Rng;
b7449926 XL	16
	17	// ----- Sampling distributions -----
	18
	19	/// Sample a `char`, uniformly distributed over ASCII letters and numbers:
	20	/// a-z, A-Z and 0-9.
dfeec247	21	///
b7449926 XL	22	/// # Example
	23	///
	24	/// ```
	25	/// use std::iter;
	26	/// use rand::{Rng, thread_rng};
	27	/// use rand::distributions::Alphanumeric;
dfeec247	28	///
b7449926 XL	29	/// let mut rng = thread_rng();
	30	/// let chars: String = iter::repeat(())
	31	/// .map(\|()\| rng.sample(Alphanumeric))
	32	/// .take(7)
	33	/// .collect();
	34	/// println!("Random chars: {}", chars);
	35	/// ```
	36	#[derive(Debug)]
	37	pub struct Alphanumeric;
	38
	39
	40	// ----- Implementations of distributions -----
	41
	42	impl Distribution<char> for Standard {
	43	#[inline]
	44	fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char {
0731742a XL	45	// A valid `char` is either in the interval `[0, 0xD800)` or
	46	// `(0xDFFF, 0x11_0000)`. All `char`s must therefore be in
	47	// `[0, 0x11_0000)` but not in the "gap" `[0xD800, 0xDFFF]` which is
	48	// reserved for surrogates. This is the size of that gap.
	49	const GAP_SIZE: u32 = 0xDFFF - 0xD800 + 1;
	50
	51	// Uniform::new(0, 0x11_0000 - GAP_SIZE) can also be used but it
	52	// seemed slower.
	53	let range = Uniform::new(GAP_SIZE, 0x11_0000);
	54
	55	let mut n = range.sample(rng);
	56	if n <= 0xDFFF {
	57	n -= GAP_SIZE;
b7449926	58	}
0731742a	59	unsafe { char::from_u32_unchecked(n) }
b7449926 XL	60	}
	61	}
	62
	63	impl Distribution<char> for Alphanumeric {
	64	fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> char {
	65	const RANGE: u32 = 26 + 26 + 10;
dfeec247	66	const GEN_ASCII_STR_CHARSET: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
b7449926 XL	67	abcdefghijklmnopqrstuvwxyz\
	68	0123456789";
	69	// We can pick from 62 characters. This is so close to a power of 2, 64,
	70	// that we can do better than `Uniform`. Use a simple bitshift and
	71	// rejection sampling. We do not use a bitmask, because for small RNGs
	72	// the most significant bits are usually of higher quality.
	73	loop {
	74	let var = rng.next_u32() >> (32 - 6);
	75	if var < RANGE {
dfeec247	76	return GEN_ASCII_STR_CHARSET[var as usize] as char;
b7449926 XL	77	}
	78	}
	79	}
	80	}
	81
	82	impl Distribution<bool> for Standard {
	83	#[inline]
	84	fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> bool {
	85	// We can compare against an arbitrary bit of an u32 to get a bool.
	86	// Because the least significant bits of a lower quality RNG can have
	87	// simple patterns, we compare against the most significant bit. This is
	88	// easiest done using a sign test.
	89	(rng.next_u32() as i32) < 0
	90	}
	91	}
	92
	93	macro_rules! tuple_impl {
	94	// use variables to indicate the arity of the tuple
	95	($($tyvar:ident),* ) => {
	96	// the trailing commas are for the 1 tuple
	97	impl< $( $tyvar ),* >
	98	Distribution<( $( $tyvar ),* , )>
	99	for Standard
	100	where $( Standard: Distribution<$tyvar> ),*
	101	{
	102	#[inline]
	103	fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> ( $( $tyvar ),* , ) {
	104	(
	105	// use the $tyvar's to get the appropriate number of
	106	// repeats (they're not actually needed)
	107	$(
	108	_rng.gen::<$tyvar>()
	109	),*
	110	,
	111	)
	112	}
	113	}
	114	}
	115	}
	116
	117	impl Distribution<()> for Standard {
dfeec247	118	#[allow(clippy::unused_unit)]
b7449926	119	#[inline]
dfeec247 XL	120	fn sample<R: Rng + ?Sized>(&self, _: &mut R) -> () {
	121	()
	122	}
b7449926	123	}
dfeec247 XL	124	tuple_impl! {A}
	125	tuple_impl! {A, B}
	126	tuple_impl! {A, B, C}
	127	tuple_impl! {A, B, C, D}
	128	tuple_impl! {A, B, C, D, E}
	129	tuple_impl! {A, B, C, D, E, F}
	130	tuple_impl! {A, B, C, D, E, F, G}
	131	tuple_impl! {A, B, C, D, E, F, G, H}
	132	tuple_impl! {A, B, C, D, E, F, G, H, I}
	133	tuple_impl! {A, B, C, D, E, F, G, H, I, J}
	134	tuple_impl! {A, B, C, D, E, F, G, H, I, J, K}
	135	tuple_impl! {A, B, C, D, E, F, G, H, I, J, K, L}
b7449926 XL	136
	137	macro_rules! array_impl {
	138	// recursive, given at least one type parameter:
	139	{$n:expr, $t:ident, $($ts:ident,)*} => {
	140	array_impl!{($n - 1), $($ts,)*}
	141
	142	impl<T> Distribution<[T; $n]> for Standard where Standard: Distribution<T> {
	143	#[inline]
	144	fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] {
	145	[_rng.gen::<$t>(), $(_rng.gen::<$ts>()),*]
	146	}
	147	}
	148	};
	149	// empty case:
	150	{$n:expr,} => {
	151	impl<T> Distribution<[T; $n]> for Standard {
	152	fn sample<R: Rng + ?Sized>(&self, _rng: &mut R) -> [T; $n] { [] }
	153	}
	154	};
	155	}
	156
dfeec247	157	array_impl! {32, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T,}
b7449926	158
dfeec247 XL	159	impl<T> Distribution<Option<T>> for Standard
	160	where Standard: Distribution<T>
	161	{
b7449926 XL	162	#[inline]
	163	fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<T> {
	164	// UFCS is needed here: https://github.com/rust-lang/rust/issues/24066
	165	if rng.gen::<bool>() {
	166	Some(rng.gen())
	167	} else {
	168	None
	169	}
	170	}
	171	}
	172
dfeec247 XL	173	impl<T> Distribution<Wrapping<T>> for Standard
	174	where Standard: Distribution<T>
	175	{
b7449926 XL	176	#[inline]
	177	fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Wrapping<T> {
	178	Wrapping(rng.gen())
	179	}
	180	}
	181
	182
	183	#[cfg(test)]
	184	mod tests {
dfeec247 XL	185	use super::*;
	186	use crate::RngCore;
	187	#[cfg(all(not(feature = "std"), feature = "alloc"))] use alloc::string::String;
b7449926 XL	188
	189	#[test]
	190	fn test_misc() {
416331ca	191	let rng: &mut dyn RngCore = &mut crate::test::rng(820);
dfeec247	192
b7449926 XL	193	rng.sample::<char, _>(Standard);
	194	rng.sample::<bool, _>(Standard);
	195	}
dfeec247 XL	196
dfeec247 XL	197	#[cfg(feature = "alloc")]
b7449926 XL	198	#[test]
	199	fn test_chars() {
	200	use core::iter;
416331ca	201	let mut rng = crate::test::rng(805);
b7449926 XL	202
	203	// Test by generating a relatively large number of chars, so we also
	204	// take the rejection sampling path.
	205	let word: String = iter::repeat(())
dfeec247 XL	206	.map(\|()\| rng.gen::<char>())
	207	.take(1000)
	208	.collect();
b7449926 XL	209	assert!(word.len() != 0);
	210	}
	211
	212	#[test]
	213	fn test_alphanumeric() {
416331ca	214	let mut rng = crate::test::rng(806);
b7449926 XL	215
	216	// Test by generating a relatively large number of chars, so we also
	217	// take the rejection sampling path.
	218	let mut incorrect = false;
	219	for _ in 0..100 {
	220	let c = rng.sample(Alphanumeric);
	221	incorrect \|= !((c >= '0' && c <= '9') \|\|
	222	(c >= 'A' && c <= 'Z') \|\|
	223	(c >= 'a' && c <= 'z') );
	224	}
	225	assert!(incorrect == false);
	226	}
dfeec247 XL	227
	228	#[test]
	229	fn value_stability() {
	230	fn test_samples<T: Copy + core::fmt::Debug + PartialEq, D: Distribution<T>>(
	231	distr: &D, zero: T, expected: &[T],
	232	) {
	233	let mut rng = crate::test::rng(807);
	234	let mut buf = [zero; 5];
	235	for x in &mut buf {
	236	*x = rng.sample(&distr);
	237	}
	238	assert_eq!(&buf, expected);
	239	}
	240
	241	test_samples(&Standard, 'a', &[
	242	'\u{8cdac}',
	243	'\u{a346a}',
	244	'\u{80120}',
	245	'\u{ed692}',
	246	'\u{35888}',
	247	]);
	248	test_samples(&Alphanumeric, 'a', &['h', 'm', 'e', '3', 'M']);
	249	test_samples(&Standard, false, &[true, true, false, true, false]);
	250	test_samples(&Standard, None as Option<bool>, &[
	251	Some(true),
	252	None,
	253	Some(false),
	254	None,
	255	Some(false),
	256	]);
	257	test_samples(&Standard, Wrapping(0i32), &[
	258	Wrapping(-2074640887),
	259	Wrapping(-1719949321),
	260	Wrapping(2018088303),
	261	Wrapping(-547181756),
	262	Wrapping(838957336),
	263	]);
	264
	265	// We test only sub-sets of tuple and array impls
	266	test_samples(&Standard, (), &[(), (), (), (), ()]);
	267	test_samples(&Standard, (false,), &[
	268	(true,),
	269	(true,),
	270	(false,),
	271	(true,),
	272	(false,),
	273	]);
	274	test_samples(&Standard, (false, false), &[
	275	(true, true),
	276	(false, true),
	277	(false, false),
	278	(true, false),
	279	(false, false),
	280	]);
	281
	282	test_samples(&Standard, [0u8; 0], &[[], [], [], [], []]);
	283	test_samples(&Standard, [0u8; 3], &[
	284	[9, 247, 111],
	285	[68, 24, 13],
	286	[174, 19, 194],
	287	[172, 69, 213],
	288	[149, 207, 29],
	289	]);
	290	}
b7449926	291	}