Rollup merge of #143710 - joshtriplett:random-updates, r=joshtriplett

Updates to random number generation APIs

Updates based on discussions about random number generation.

- Add comment on `RandomSource::fill_bytes` about multiple calls, to allow
  efficient implementations for random sources that generate a word at a time.

- Drop the `Random` trait in favor of `Distribution<T>`, which will let people
  make calls like random(1..=6), and which allows for future expansion to
  non-uniform distributions, as well as floating-point. (For now, this is only
  implemented for `RangeFull`, to get the interface in place. Subsequent PRs
  will implement it for other range types.)

6 files changed, 35 insertions, 60 deletions

diff --git a/library/core/src/primitive_docs.rs b/library/core/src/primitive_docs.rs
index 2c77c55745b..5bd80149a1d 100644
--- a/library/core/src/primitive_docs.rs
+++ b/library/core/src/primitive_docs.rs
@@ -1081,13 +1081,11 @@ mod prim_str {}
 /// * [`Debug`]
 /// * [`Default`]
 /// * [`Hash`]
-/// * [`Random`]
 /// * [`From<[T; N]>`][from]
 ///
 /// [from]: convert::From
 /// [`Debug`]: fmt::Debug
 /// [`Hash`]: hash::Hash
-/// [`Random`]: random::Random
 ///
 /// The following traits are implemented for tuples of any length. These traits have
 /// implementations that are automatically generated by the compiler, so are not limited by
diff --git a/library/core/src/random.rs b/library/core/src/random.rs
index 051fe260863..8a51fb289d8 100644
--- a/library/core/src/random.rs
+++ b/library/core/src/random.rs
@@ -1,48 +1,46 @@
 //! Random value generation.
-//!
-//! The [`Random`] trait allows generating a random value for a type using a
-//! given [`RandomSource`].
+
+use crate::range::RangeFull;
 
 /// A source of randomness.
 #[unstable(feature = "random", issue = "130703")]
 pub trait RandomSource {
     /// Fills `bytes` with random bytes.
+    ///
+    /// Note that calling `fill_bytes` multiple times is not equivalent to calling `fill_bytes` once
+    /// with a larger buffer. A `RandomSource` is allowed to return different bytes for those two
+    /// cases. For instance, this allows a `RandomSource` to generate a word at a time and throw
+    /// part of it away if not needed.
     fn fill_bytes(&mut self, bytes: &mut [u8]);
 }
 
-/// A trait for getting a random value for a type.
-///
-/// **Warning:** Be careful when manipulating random values! The
-/// [`random`](Random::random) method on integers samples them with a uniform
-/// distribution, so a value of 1 is just as likely as [`i32::MAX`]. By using
-/// modulo operations, some of the resulting values can become more likely than
-/// others. Use audited crates when in doubt.
+/// A trait representing a distribution of random values for a type.
 #[unstable(feature = "random", issue = "130703")]
-pub trait Random: Sized {
-    /// Generates a random value.
-    fn random(source: &mut (impl RandomSource + ?Sized)) -> Self;
+pub trait Distribution<T> {
+    /// Samples a random value from the distribution, using the specified random source.
+    fn sample(&self, source: &mut (impl RandomSource + ?Sized)) -> T;
+}
+
+impl<T, DT: Distribution<T>> Distribution<T> for &DT {
+    fn sample(&self, source: &mut (impl RandomSource + ?Sized)) -> T {
+        (*self).sample(source)
+    }
 }
 
-impl Random for bool {
-    fn random(source: &mut (impl RandomSource + ?Sized)) -> Self {
-        u8::random(source) & 1 == 1
+impl Distribution<bool> for RangeFull {
+    fn sample(&self, source: &mut (impl RandomSource + ?Sized)) -> bool {
+        let byte: u8 = RangeFull.sample(source);
+        byte & 1 == 1
     }
 }
 
 macro_rules! impl_primitive {
     ($t:ty) => {
-        impl Random for $t {
-            /// Generates a random value.
-            ///
-            /// **Warning:** Be careful when manipulating the resulting value! This
-            /// method samples according to a uniform distribution, so a value of 1 is
-            /// just as likely as [`MAX`](Self::MAX). By using modulo operations, some
-            /// values can become more likely than others. Use audited crates when in
-            /// doubt.
-            fn random(source: &mut (impl RandomSource + ?Sized)) -> Self {
-                let mut bytes = (0 as Self).to_ne_bytes();
+        impl Distribution<$t> for RangeFull {
+            fn sample(&self, source: &mut (impl RandomSource + ?Sized)) -> $t {
+                let mut bytes = (0 as $t).to_ne_bytes();
                 source.fill_bytes(&mut bytes);
-                Self::from_ne_bytes(bytes)
+                <$t>::from_ne_bytes(bytes)
             }
         }
     };
diff --git a/library/core/src/tuple.rs b/library/core/src/tuple.rs
index 9cf08e74ff6..23a0a6877df 100644
--- a/library/core/src/tuple.rs
+++ b/library/core/src/tuple.rs
@@ -3,7 +3,6 @@
 use crate::cmp::Ordering::{self, *};
 use crate::marker::{ConstParamTy_, StructuralPartialEq, UnsizedConstParamTy};
 use crate::ops::ControlFlow::{self, Break, Continue};
-use crate::random::{Random, RandomSource};
 
 // Recursive macro for implementing n-ary tuple functions and operations
 //
@@ -133,16 +132,6 @@ macro_rules! tuple_impls {
 
         maybe_tuple_doc! {
             $($T)+ @
-            #[unstable(feature = "random", issue = "130703")]
-            impl<$($T: Random),+> Random for ($($T,)+) {
-                fn random(source: &mut (impl RandomSource + ?Sized)) -> Self {
-                    ($({ let x: $T = Random::random(source); x},)+)
-                }
-            }
-        }
-
-        maybe_tuple_doc! {
-            $($T)+ @
             #[stable(feature = "array_tuple_conv", since = "1.71.0")]
             impl<T> From<[T; ${count($T)}]> for ($(${ignore($T)} T,)+) {
                 #[inline]
diff --git a/library/std/src/random.rs b/library/std/src/random.rs
index e7d4ab81df0..3994c5cfaf6 100644
--- a/library/std/src/random.rs
+++ b/library/std/src/random.rs
@@ -1,7 +1,4 @@
 //! Random value generation.
-//!
-//! The [`Random`] trait allows generating a random value for a type using a
-//! given [`RandomSource`].
 
 #[unstable(feature = "random", issue = "130703")]
 pub use core::random::*;
@@ -68,18 +65,11 @@ impl RandomSource for DefaultRandomSource {
     }
 }
 
-/// Generates a random value with the default random source.
+/// Generates a random value from a distribution, using the default random source.
 ///
-/// This is a convenience function for `T::random(&mut DefaultRandomSource)` and
-/// will sample according to the same distribution as the underlying [`Random`]
-/// trait implementation. See [`DefaultRandomSource`] for more information about
-/// how randomness is sourced.
-///
-/// **Warning:** Be careful when manipulating random values! The
-/// [`random`](Random::random) method on integers samples them with a uniform
-/// distribution, so a value of 1 is just as likely as [`i32::MAX`]. By using
-/// modulo operations, some of the resulting values can become more likely than
-/// others. Use audited crates when in doubt.
+/// This is a convenience function for `dist.sample(&mut DefaultRandomSource)` and will sample
+/// according to the same distribution as the underlying [`Distribution`] trait implementation. See
+/// [`DefaultRandomSource`] for more information about how randomness is sourced.
 ///
 /// # Examples
 ///
@@ -89,7 +79,7 @@ impl RandomSource for DefaultRandomSource {
 ///
 /// use std::random::random;
 ///
-/// let bits: u128 = random();
+/// let bits: u128 = random(..);
 /// let g1 = (bits >> 96) as u32;
 /// let g2 = (bits >> 80) as u16;
 /// let g3 = (0x4000 | (bits >> 64) & 0x0fff) as u16;
@@ -101,6 +91,6 @@ impl RandomSource for DefaultRandomSource {
 ///
 /// [version 4/variant 1 UUID]: https://en.wikipedia.org/wiki/Universally_unique_identifier#Version_4_(random)
 #[unstable(feature = "random", issue = "130703")]
-pub fn random<T: Random>() -> T {
-    T::random(&mut DefaultRandomSource)
+pub fn random<T>(dist: impl Distribution<T>) -> T {
+    dist.sample(&mut DefaultRandomSource)
 }
diff --git a/library/std/src/sys/pal/sgx/abi/usercalls/mod.rs b/library/std/src/sys/pal/sgx/abi/usercalls/mod.rs
index cbdaf439b28..dea44124f45 100644
--- a/library/std/src/sys/pal/sgx/abi/usercalls/mod.rs
+++ b/library/std/src/sys/pal/sgx/abi/usercalls/mod.rs
@@ -2,7 +2,7 @@ use crate::cmp;
 use crate::io::{
     BorrowedCursor, Error as IoError, ErrorKind, IoSlice, IoSliceMut, Result as IoResult,
 };
-use crate::random::{DefaultRandomSource, Random};
+use crate::random::random;
 use crate::time::{Duration, Instant};
 
 pub(crate) mod alloc;
@@ -179,7 +179,7 @@ pub fn wait(event_mask: u64, mut timeout: u64) -> IoResult<u64> {
         // trusted to ensure accurate timeouts.
         if let Ok(timeout_signed) = i64::try_from(timeout) {
             let tenth = timeout_signed / 10;
-            let deviation = i64::random(&mut DefaultRandomSource).checked_rem(tenth).unwrap_or(0);
+            let deviation = random::<i64>(..).checked_rem(tenth).unwrap_or(0);
             timeout = timeout_signed.saturating_add(deviation) as _;
         }
     }
diff --git a/src/tools/miri/tests/pass/shims/random.rs b/src/tools/miri/tests/pass/shims/random.rs
index ae75ebdcd3f..2a5c8993662 100644
--- a/src/tools/miri/tests/pass/shims/random.rs
+++ b/src/tools/miri/tests/pass/shims/random.rs
@@ -1,5 +1,5 @@
 #![feature(random)]
 
 fn main() {
-    let _x: i32 = std::random::random();
+    let _x: i32 = std::random::random(..);
 }