std: Remove `rand` crate and module

This commit removes the `rand` crate from the standard library facade as
well as the `__rand` module in the standard library. Neither of these
were used in any meaningful way in the standard library itself. The only
need for randomness in libstd is to initialize the thread-local keys of
a `HashMap`, and that unconditionally used `OsRng` defined in the
standard library anyway.

The cruft of the `rand` crate and the extra `rand` support in the
standard library makes libstd slightly more difficult to port to new
platforms, namely WebAssembly which doesn't have any randomness at all
(without interfacing with JS). The purpose of this commit is to clarify
and streamline randomness in libstd, focusing on how it's only required
in one location, hashmap seeds.

Note that the `rand` crate out of tree has almost always been a drop-in
replacement for the `rand` crate in-tree, so any usage (accidental or
purposeful) of the crate in-tree should switch to the `rand` crate on
crates.io. This then also has the further benefit of avoiding
duplication (mostly) between the two crates!

7 files changed, 107 insertions, 300 deletions

diff --git a/src/libstd/sys/redox/mod.rs b/src/libstd/sys/redox/mod.rs
index 7c728ebb1af..7137a506743 100644
--- a/src/libstd/sys/redox/mod.rs
+++ b/src/libstd/sys/redox/mod.rs
@@ -12,6 +12,8 @@
 
 use io::{self, ErrorKind};
 
+pub use self::rand::hashmap_random_keys;
+
 pub mod args;
 #[cfg(feature = "backtrace")]
 pub mod backtrace;
diff --git a/src/libstd/sys/redox/rand.rs b/src/libstd/sys/redox/rand.rs
index eb28eca38bc..3b378f53429 100644
--- a/src/libstd/sys/redox/rand.rs
+++ b/src/libstd/sys/redox/rand.rs
@@ -8,50 +8,6 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use io;
-use rand::Rng;
-
-// FIXME: Use rand:
-pub struct OsRng {
-    state: [u64; 2]
-}
-
-impl OsRng {
-    /// Create a new `OsRng`.
-    pub fn new() -> io::Result<OsRng> {
-        Ok(OsRng {
-            state: [0xBADF00D1, 0xDEADBEEF]
-        })
-    }
-}
-
-impl Rng for OsRng {
-    fn next_u32(&mut self) -> u32 {
-        self.next_u64() as u32
-    }
-    fn next_u64(&mut self) -> u64 {
-        // Store the first and second part.
-        let mut x = self.state[0];
-        let y = self.state[1];
-
-        // Put the second part into the first slot.
-        self.state[0] = y;
-        // Twist the first slot.
-        x ^= x << 23;
-        // Update the second slot.
-        self.state[1] = x ^ y ^ (x >> 17) ^ (y >> 26);
-
-        // Generate the final integer.
-        self.state[1].wrapping_add(y)
-
-    }
-    fn fill_bytes(&mut self, buf: &mut [u8]) {
-        for chunk in buf.chunks_mut(8) {
-            let mut rand: u64 = self.next_u64();
-            for b in chunk.iter_mut() {
-                *b = rand as u8;
-                rand = rand >> 8;
-            }
-        }
-    }
+pub fn hashmap_random_keys() -> (u64, u64) {
+    (0, 0)
 }
diff --git a/src/libstd/sys/unix/mod.rs b/src/libstd/sys/unix/mod.rs
index c2772e2e2cc..4669b2a636c 100644
--- a/src/libstd/sys/unix/mod.rs
+++ b/src/libstd/sys/unix/mod.rs
@@ -29,6 +29,8 @@ use libc;
 #[cfg(all(not(dox), target_os = "fuchsia"))]   pub use os::fuchsia as platform;
 #[cfg(all(not(dox), target_os = "l4re"))]      pub use os::linux as platform;
 
+pub use self::rand::hashmap_random_keys;
+
 #[macro_use]
 pub mod weak;
 
diff --git a/src/libstd/sys/unix/rand.rs b/src/libstd/sys/unix/rand.rs
index e2d40742c71..bbffe0f0ffe 100644
--- a/src/libstd/sys/unix/rand.rs
+++ b/src/libstd/sys/unix/rand.rs
@@ -8,20 +8,17 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-pub use self::imp::OsRng;
-
 use mem;
-
-fn next_u32(fill_buf: &mut FnMut(&mut [u8])) -> u32 {
-    let mut buf: [u8; 4] = [0; 4];
-    fill_buf(&mut buf);
-    unsafe { mem::transmute::<[u8; 4], u32>(buf) }
-}
-
-fn next_u64(fill_buf: &mut FnMut(&mut [u8])) -> u64 {
-    let mut buf: [u8; 8] = [0; 8];
-    fill_buf(&mut buf);
-    unsafe { mem::transmute::<[u8; 8], u64>(buf) }
+use slice;
+
+pub fn hashmap_random_keys() -> (u64, u64) {
+    let mut v = (0, 0);
+    unsafe {
+        let view = slice::from_raw_parts_mut(&mut v as *mut _ as *mut u8,
+                                             mem::size_of_val(&v));
+        imp::fill_bytes(view);
+    }
+    return v
 }
 
 #[cfg(all(unix,
@@ -30,14 +27,9 @@ fn next_u64(fill_buf: &mut FnMut(&mut [u8])) -> u64 {
           not(target_os = "freebsd"),
           not(target_os = "fuchsia")))]
 mod imp {
-    use self::OsRngInner::*;
-    use super::{next_u32, next_u64};
-
     use fs::File;
-    use io;
+    use io::Read;
     use libc;
-    use rand::Rng;
-    use rand::reader::ReaderRng;
     use sys::os::errno;
 
     #[cfg(all(target_os = "linux",
@@ -81,7 +73,7 @@ mod imp {
                       target_arch = "s390x"))))]
     fn getrandom(_buf: &mut [u8]) -> libc::c_long { -1 }
 
-    fn getrandom_fill_bytes(v: &mut [u8]) {
+    fn getrandom_fill_bytes(v: &mut [u8]) -> bool {
         let mut read = 0;
         while read < v.len() {
             let result = getrandom(&mut v[read..]);
@@ -90,18 +82,7 @@ mod imp {
                 if err == libc::EINTR {
                     continue;
                 } else if err == libc::EAGAIN {
-                    // if getrandom() returns EAGAIN it would have blocked
-                    // because the non-blocking pool (urandom) has not
-                    // initialized in the kernel yet due to a lack of entropy
-                    // the fallback we do here is to avoid blocking applications
-                    // which could depend on this call without ever knowing
-                    // they do and don't have a work around. The PRNG of
-                    // /dev/urandom will still be used but not over a completely
-                    // full entropy pool
-                    let reader = File::open("/dev/urandom").expect("Unable to open /dev/urandom");
-                    let mut reader_rng = ReaderRng::new(reader);
-                    reader_rng.fill_bytes(&mut v[read..]);
-                    read += v.len();
+                    return false
                 } else {
                     panic!("unexpected getrandom error: {}", err);
                 }
@@ -109,6 +90,8 @@ mod imp {
                 read += result as usize;
             }
         }
+
+        return true
     }
 
     #[cfg(all(target_os = "linux",
@@ -120,6 +103,7 @@ mod imp {
                   target_arch = "powerpc64",
                   target_arch = "s390x")))]
     fn is_getrandom_available() -> bool {
+        use io;
         use sync::atomic::{AtomicBool, Ordering};
         use sync::Once;
 
@@ -151,89 +135,37 @@ mod imp {
                       target_arch = "s390x"))))]
     fn is_getrandom_available() -> bool { false }
 
-    pub struct OsRng {
-        inner: OsRngInner,
-    }
-
-    enum OsRngInner {
-        OsGetrandomRng,
-        OsReaderRng(ReaderRng<File>),
-    }
-
-    impl OsRng {
-        /// Create a new `OsRng`.
-        pub fn new() -> io::Result<OsRng> {
-            if is_getrandom_available() {
-                return Ok(OsRng { inner: OsGetrandomRng });
-            }
-
-            let reader = File::open("/dev/urandom")?;
-            let reader_rng = ReaderRng::new(reader);
-
-            Ok(OsRng { inner: OsReaderRng(reader_rng) })
+    pub fn fill_bytes(v: &mut [u8]) {
+        // getrandom_fill_bytes here can fail if getrandom() returns EAGAIN,
+        // meaning it would have blocked because the non-blocking pool (urandom)
+        // has not initialized in the kernel yet due to a lack of entropy the
+        // fallback we do here is to avoid blocking applications which could
+        // depend on this call without ever knowing they do and don't have a
+        // work around.  The PRNG of /dev/urandom will still be used but not
+        // over a completely full entropy pool
+        if is_getrandom_available() && getrandom_fill_bytes(v) {
+            return
         }
-    }
 
-    impl Rng for OsRng {
-        fn next_u32(&mut self) -> u32 {
-            match self.inner {
-                OsGetrandomRng => next_u32(&mut getrandom_fill_bytes),
-                OsReaderRng(ref mut rng) => rng.next_u32(),
-            }
-        }
-        fn next_u64(&mut self) -> u64 {
-            match self.inner {
-                OsGetrandomRng => next_u64(&mut getrandom_fill_bytes),
-                OsReaderRng(ref mut rng) => rng.next_u64(),
-            }
-        }
-        fn fill_bytes(&mut self, v: &mut [u8]) {
-            match self.inner {
-                OsGetrandomRng => getrandom_fill_bytes(v),
-                OsReaderRng(ref mut rng) => rng.fill_bytes(v)
-            }
-        }
+        let mut file = File::open("/dev/urandom")
+            .expect("failed to open /dev/urandom");
+        file.read_exact(v).expect("failed to read /dev/urandom");
     }
 }
 
 #[cfg(target_os = "openbsd")]
 mod imp {
-    use super::{next_u32, next_u64};
-
-    use io;
     use libc;
     use sys::os::errno;
-    use rand::Rng;
-
-    pub struct OsRng {
-        // dummy field to ensure that this struct cannot be constructed outside
-        // of this module
-        _dummy: (),
-    }
-
-    impl OsRng {
-        /// Create a new `OsRng`.
-        pub fn new() -> io::Result<OsRng> {
-            Ok(OsRng { _dummy: () })
-        }
-    }
 
-    impl Rng for OsRng {
-        fn next_u32(&mut self) -> u32 {
-            next_u32(&mut |v| self.fill_bytes(v))
-        }
-        fn next_u64(&mut self) -> u64 {
-            next_u64(&mut |v| self.fill_bytes(v))
-        }
-        fn fill_bytes(&mut self, v: &mut [u8]) {
-            // getentropy(2) permits a maximum buffer size of 256 bytes
-            for s in v.chunks_mut(256) {
-                let ret = unsafe {
-                    libc::getentropy(s.as_mut_ptr() as *mut libc::c_void, s.len())
-                };
-                if ret == -1 {
-                    panic!("unexpected getentropy error: {}", errno());
-                }
+    pub fn fill_bytes(v: &mut [u8]) {
+        // getentropy(2) permits a maximum buffer size of 256 bytes
+        for s in v.chunks_mut(256) {
+            let ret = unsafe {
+                libc::getentropy(s.as_mut_ptr() as *mut libc::c_void, s.len())
+            };
+            if ret == -1 {
+                panic!("unexpected getentropy error: {}", errno());
             }
         }
     }
@@ -241,18 +173,9 @@ mod imp {
 
 #[cfg(target_os = "ios")]
 mod imp {
-    use super::{next_u32, next_u64};
-
     use io;
-    use ptr;
-    use rand::Rng;
     use libc::{c_int, size_t};
-
-    pub struct OsRng {
-        // dummy field to ensure that this struct cannot be constructed outside
-        // of this module
-        _dummy: (),
-    }
+    use ptr;
 
     enum SecRandom {}
 
@@ -261,79 +184,41 @@ mod imp {
 
     extern {
         fn SecRandomCopyBytes(rnd: *const SecRandom,
-                              count: size_t, bytes: *mut u8) -> c_int;
+                              count: size_t,
+                              bytes: *mut u8) -> c_int;
     }
 
-    impl OsRng {
-        /// Create a new `OsRng`.
-        pub fn new() -> io::Result<OsRng> {
-            Ok(OsRng { _dummy: () })
-        }
-    }
-
-    impl Rng for OsRng {
-        fn next_u32(&mut self) -> u32 {
-            next_u32(&mut |v| self.fill_bytes(v))
-        }
-        fn next_u64(&mut self) -> u64 {
-            next_u64(&mut |v| self.fill_bytes(v))
-        }
-        fn fill_bytes(&mut self, v: &mut [u8]) {
-            let ret = unsafe {
-                SecRandomCopyBytes(kSecRandomDefault, v.len(),
-                                   v.as_mut_ptr())
-            };
-            if ret == -1 {
-                panic!("couldn't generate random bytes: {}",
-                       io::Error::last_os_error());
-            }
+    pub fn fill_bytes(v: &mut [u8]) {
+        let ret = unsafe {
+            SecRandomCopyBytes(kSecRandomDefault,
+                               v.len(),
+                               v.as_mut_ptr())
+        };
+        if ret == -1 {
+            panic!("couldn't generate random bytes: {}",
+                   io::Error::last_os_error());
         }
     }
 }
 
 #[cfg(target_os = "freebsd")]
 mod imp {
-    use super::{next_u32, next_u64};
-
-    use io;
     use libc;
-    use rand::Rng;
     use ptr;
 
-    pub struct OsRng {
-        // dummy field to ensure that this struct cannot be constructed outside
-        // of this module
-        _dummy: (),
-    }
-
-    impl OsRng {
-        /// Create a new `OsRng`.
-        pub fn new() -> io::Result<OsRng> {
-            Ok(OsRng { _dummy: () })
-        }
-    }
-
-    impl Rng for OsRng {
-        fn next_u32(&mut self) -> u32 {
-            next_u32(&mut |v| self.fill_bytes(v))
-        }
-        fn next_u64(&mut self) -> u64 {
-            next_u64(&mut |v| self.fill_bytes(v))
-        }
-        fn fill_bytes(&mut self, v: &mut [u8]) {
-            let mib = [libc::CTL_KERN, libc::KERN_ARND];
-            // kern.arandom permits a maximum buffer size of 256 bytes
-            for s in v.chunks_mut(256) {
-                let mut s_len = s.len();
-                let ret = unsafe {
-                    libc::sysctl(mib.as_ptr(), mib.len() as libc::c_uint,
-                                 s.as_mut_ptr() as *mut _, &mut s_len,
-                                 ptr::null(), 0)
-                };
-                if ret == -1 || s_len != s.len() {
-                    panic!("kern.arandom sysctl failed! (returned {}, s.len() {}, oldlenp {})",
-                           ret, s.len(), s_len);
-                }
+    pub fn fill_bytes(v: &mut [u8]) {
+        let mib = [libc::CTL_KERN, libc::KERN_ARND];
+        // kern.arandom permits a maximum buffer size of 256 bytes
+        for s in v.chunks_mut(256) {
+            let mut s_len = s.len();
+            let ret = unsafe {
+                libc::sysctl(mib.as_ptr(), mib.len() as libc::c_uint,
+                             s.as_mut_ptr() as *mut _, &mut s_len,
+                             ptr::null(), 0)
+            };
+            if ret == -1 || s_len != s.len() {
+                panic!("kern.arandom sysctl failed! (returned {}, s.len() {}, oldlenp {})",
+                       ret, s.len(), s_len);
             }
         }
     }
@@ -341,11 +226,6 @@ mod imp {
 
 #[cfg(target_os = "fuchsia")]
 mod imp {
-    use super::{next_u32, next_u64};
-
-    use io;
-    use rand::Rng;
-
     #[link(name = "zircon")]
     extern {
         fn zx_cprng_draw(buffer: *mut u8, len: usize, actual: *mut usize) -> i32;
@@ -363,39 +243,18 @@ mod imp {
         }
     }
 
-    pub struct OsRng {
-        // dummy field to ensure that this struct cannot be constructed outside
-        // of this module
-        _dummy: (),
-    }
-
-    impl OsRng {
-        /// Create a new `OsRng`.
-        pub fn new() -> io::Result<OsRng> {
-            Ok(OsRng { _dummy: () })
-        }
-    }
-
-    impl Rng for OsRng {
-        fn next_u32(&mut self) -> u32 {
-            next_u32(&mut |v| self.fill_bytes(v))
-        }
-        fn next_u64(&mut self) -> u64 {
-            next_u64(&mut |v| self.fill_bytes(v))
-        }
-        fn fill_bytes(&mut self, v: &mut [u8]) {
-            let mut buf = v;
-            while !buf.is_empty() {
-                let ret = getrandom(buf);
-                match ret {
-                    Err(err) => {
-                        panic!("kernel zx_cprng_draw call failed! (returned {}, buf.len() {})",
-                            err, buf.len())
-                    }
-                    Ok(actual) => {
-                        let move_buf = buf;
-                        buf = &mut move_buf[(actual as usize)..];
-                    }
+    pub fn fill_bytes(v: &mut [u8]) {
+        let mut buf = v;
+        while !buf.is_empty() {
+            let ret = getrandom(buf);
+            match ret {
+                Err(err) => {
+                    panic!("kernel zx_cprng_draw call failed! (returned {}, buf.len() {})",
+                        err, buf.len())
+                }
+                Ok(actual) => {
+                    let move_buf = buf;
+                    buf = &mut move_buf[(actual as usize)..];
                 }
             }
         }
diff --git a/src/libstd/sys/windows/mod.rs b/src/libstd/sys/windows/mod.rs
index e7a9a121b25..ab8e155331e 100644
--- a/src/libstd/sys/windows/mod.rs
+++ b/src/libstd/sys/windows/mod.rs
@@ -17,6 +17,8 @@ use os::windows::ffi::{OsStrExt, OsStringExt};
 use path::PathBuf;
 use time::Duration;
 
+pub use self::rand::hashmap_random_keys;
+
 #[macro_use] pub mod compat;
 
 pub mod args;
diff --git a/src/libstd/sys/windows/pipe.rs b/src/libstd/sys/windows/pipe.rs
index 452d720ce59..f3b1185c6ea 100644
--- a/src/libstd/sys/windows/pipe.rs
+++ b/src/libstd/sys/windows/pipe.rs
@@ -15,11 +15,13 @@ use io;
 use mem;
 use path::Path;
 use ptr;
-use rand::{self, Rng};
 use slice;
+use sync::atomic::Ordering::SeqCst;
+use sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT};
 use sys::c;
 use sys::fs::{File, OpenOptions};
 use sys::handle::Handle;
+use sys::hashmap_random_keys;
 
 ////////////////////////////////////////////////////////////////////////////////
 // Anonymous pipes
@@ -71,10 +73,9 @@ pub fn anon_pipe(ours_readable: bool) -> io::Result<Pipes> {
         let mut reject_remote_clients_flag = c::PIPE_REJECT_REMOTE_CLIENTS;
         loop {
             tries += 1;
-            let key: u64 = rand::thread_rng().gen();
             name = format!(r"\\.\pipe\__rust_anonymous_pipe1__.{}.{}",
                            c::GetCurrentProcessId(),
-                           key);
+                           random_number());
             let wide_name = OsStr::new(&name)
                                   .encode_wide()
                                   .chain(Some(0))
@@ -156,6 +157,17 @@ pub fn anon_pipe(ours_readable: bool) -> io::Result<Pipes> {
     }
 }
 
+fn random_number() -> usize {
+    static N: AtomicUsize = ATOMIC_USIZE_INIT;
+    loop {
+        if N.load(SeqCst) != 0 {
+            return N.fetch_add(1, SeqCst)
+        }
+
+        N.store(hashmap_random_keys().0 as usize, SeqCst);
+    }
+}
+
 impl AnonPipe {
     pub fn handle(&self) -> &Handle { &self.inner }
     pub fn into_handle(self) -> Handle { self.inner }
diff --git a/src/libstd/sys/windows/rand.rs b/src/libstd/sys/windows/rand.rs
index f66b0a3bdc3..262323656aa 100644
--- a/src/libstd/sys/windows/rand.rs
+++ b/src/libstd/sys/windows/rand.rs
@@ -8,45 +8,19 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-
 use io;
 use mem;
-use rand::Rng;
 use sys::c;
 
-pub struct OsRng;
-
-impl OsRng {
-    /// Create a new `OsRng`.
-    pub fn new() -> io::Result<OsRng> {
-        Ok(OsRng)
-    }
-}
-
-impl Rng for OsRng {
-    fn next_u32(&mut self) -> u32 {
-        let mut v = [0; 4];
-        self.fill_bytes(&mut v);
-        unsafe { mem::transmute(v) }
-    }
-
-    fn next_u64(&mut self) -> u64 {
-        let mut v = [0; 8];
-        self.fill_bytes(&mut v);
-        unsafe { mem::transmute(v) }
-    }
-
-    fn fill_bytes(&mut self, v: &mut [u8]) {
-        // RtlGenRandom takes an ULONG (u32) for the length so we need to
-        // split up the buffer.
-        for slice in v.chunks_mut(<c::ULONG>::max_value() as usize) {
-            let ret = unsafe {
-                c::RtlGenRandom(slice.as_mut_ptr(), slice.len() as c::ULONG)
-            };
-            if ret == 0 {
-                panic!("couldn't generate random bytes: {}",
-                       io::Error::last_os_error());
-            }
-        }
+pub fn hashmap_random_keys() -> (u64, u64) {
+    let mut v = (0, 0);
+    let ret = unsafe {
+        c::RtlGenRandom(&mut v as *mut _ as *mut u8,
+                        mem::size_of_val(&v) as c::ULONG)
+    };
+    if ret == 0 {
+        panic!("couldn't generate random bytes: {}",
+               io::Error::last_os_error());
     }
+    return v
 }