std: Recreate a `rand` module

This commit shuffles around some of the `rand` code, along with some
reorganization. The new state of the world is as follows:

* The librand crate now only depends on libcore. This interface is experimental.
* The standard library has a new module, `std::rand`. This interface will
  eventually become stable.

Unfortunately, this entailed more of a breaking change than just shuffling some
names around. The following breaking changes were made to the rand library:

* Rng::gen_vec() was removed. This has been replaced with Rng::gen_iter() which
  will return an infinite stream of random values. Previous behavior can be
  regained with `rng.gen_iter().take(n).collect()`

* Rng::gen_ascii_str() was removed. This has been replaced with
  Rng::gen_ascii_chars() which will return an infinite stream of random ascii
  characters. Similarly to gen_iter(), previous behavior can be emulated with
  `rng.gen_ascii_chars().take(n).collect()`

* {IsaacRng, Isaac64Rng, XorShiftRng}::new() have all been removed. These all
  relied on being able to use an OSRng for seeding, but this is no longer
  available in librand (where these types are defined). To retain the same
  functionality, these types now implement the `Rand` trait so they can be
  generated with a random seed from another random number generator. This allows
  the stdlib to use an OSRng to create seeded instances of these RNGs.

* Rand implementations for `Box<T>` and `@T` were removed. These seemed to be
  pretty rare in the codebase, and it allows for librand to not depend on
  liballoc.  Additionally, other pointer types like Rc<T> and Arc<T> were not
  supported.  If this is undesirable, librand can depend on liballoc and regain
  these implementations.

* The WeightedChoice structure is no longer built with a `Vec<Weighted<T>>`,
  but rather a `&mut [Weighted<T>]`. This means that the WeightedChoice
  structure now has a lifetime associated with it.

* The `sample` method on `Rng` has been moved to a top-level function in the
  `rand` module due to its dependence on `Vec`.

cc #13851

[breaking-change]

7 files changed, 17 insertions, 20 deletions

diff --git a/src/libcore/any.rs b/src/libcore/any.rs
index 94ac344db34..f463c194424 100644
--- a/src/libcore/any.rs
+++ b/src/libcore/any.rs
@@ -119,7 +119,7 @@ mod tests {
     use prelude::*;
     use super::*;
     use realstd::owned::{Box, AnyOwnExt};
-    use realstd::str::{Str, StrAllocating};
+    use realstd::str::Str;
 
     #[deriving(Eq, Show)]
     struct Test;
diff --git a/src/libcore/char.rs b/src/libcore/char.rs
index 0c5d3151af0..2d1cab5d841 100644
--- a/src/libcore/char.rs
+++ b/src/libcore/char.rs
@@ -607,7 +607,7 @@ mod test {
     use slice::ImmutableVector;
     use option::{Some, None};
     use realstd::string::String;
-    use realstd::str::{Str, StrAllocating};
+    use realstd::str::Str;
 
     #[test]
     fn test_is_lowercase() {
diff --git a/src/libcore/fmt/mod.rs b/src/libcore/fmt/mod.rs
index 13236a1f654..f41efdbc1db 100644
--- a/src/libcore/fmt/mod.rs
+++ b/src/libcore/fmt/mod.rs
@@ -596,7 +596,6 @@ pub fn argument<'a, T>(f: extern "Rust" fn(&T, &mut Formatter) -> Result,
 #[cfg(test)]
 pub fn format(args: &Arguments) -> ::realstd::string::String {
     use str;
-    use realstd::str::StrAllocating;
     use realstd::io::MemWriter;
 
     fn mywrite<T: ::realstd::io::Writer>(t: &mut T, b: &[u8]) {
diff --git a/src/libcore/fmt/num.rs b/src/libcore/fmt/num.rs
index 731911185ff..7ad78df2fe8 100644
--- a/src/libcore/fmt/num.rs
+++ b/src/libcore/fmt/num.rs
@@ -194,7 +194,7 @@ mod tests {
     use fmt::radix;
     use super::{Binary, Octal, Decimal, LowerHex, UpperHex};
     use super::{GenericRadix, Radix};
-    use realstd::str::{Str, StrAllocating};
+    use realstd::str::Str;
 
     #[test]
     fn test_radix_base() {
@@ -399,35 +399,35 @@ mod bench {
     mod uint {
         use super::test::Bencher;
         use fmt::radix;
-        use rand::{XorShiftRng, Rng};
+        use realstd::rand::{weak_rng, Rng};
 
         #[bench]
         fn format_bin(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{:t}", rng.gen::<uint>()); })
         }
 
         #[bench]
         fn format_oct(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{:o}", rng.gen::<uint>()); })
         }
 
         #[bench]
         fn format_dec(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{:u}", rng.gen::<uint>()); })
         }
 
         #[bench]
         fn format_hex(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{:x}", rng.gen::<uint>()); })
         }
 
         #[bench]
         fn format_base_36(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{}", radix(rng.gen::<uint>(), 36)); })
         }
     }
@@ -435,35 +435,35 @@ mod bench {
     mod int {
         use super::test::Bencher;
         use fmt::radix;
-        use rand::{XorShiftRng, Rng};
+        use realstd::rand::{weak_rng, Rng};
 
         #[bench]
         fn format_bin(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{:t}", rng.gen::<int>()); })
         }
 
         #[bench]
         fn format_oct(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{:o}", rng.gen::<int>()); })
         }
 
         #[bench]
         fn format_dec(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{:d}", rng.gen::<int>()); })
         }
 
         #[bench]
         fn format_hex(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{:x}", rng.gen::<int>()); })
         }
 
         #[bench]
         fn format_base_36(b: &mut Bencher) {
-            let mut rng = XorShiftRng::new().unwrap();
+            let mut rng = weak_rng();
             b.iter(|| { format!("{}", radix(rng.gen::<int>(), 36)); })
         }
     }
diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs
index 56cbe2e2a30..2ff2dca0c86 100644
--- a/src/libcore/lib.rs
+++ b/src/libcore/lib.rs
@@ -59,7 +59,6 @@
 #[cfg(test)] extern crate realcore = "core";
 #[cfg(test)] extern crate libc;
 #[cfg(test)] extern crate native;
-#[cfg(test)] extern crate rand;
 #[cfg(test)] extern crate realstd = "std";
 
 #[cfg(test)] pub use cmp = realcore::cmp;
diff --git a/src/libcore/result.rs b/src/libcore/result.rs
index 926605dddb3..fd51ede204f 100644
--- a/src/libcore/result.rs
+++ b/src/libcore/result.rs
@@ -637,11 +637,10 @@ pub fn fold_<T,E,Iter:Iterator<Result<T,E>>>(iterator: Iter) -> Result<(),E> {
 #[cfg(test)]
 mod tests {
     use realstd::vec::Vec;
-    use realstd::string::String;
 
     use result::{collect, fold, fold_};
     use prelude::*;
-    use realstd::str::{Str, StrAllocating};
+    use realstd::str::Str;
     use iter::range;
 
     pub fn op1() -> Result<int, &'static str> { Ok(666) }
diff --git a/src/libcore/tuple.rs b/src/libcore/tuple.rs
index 059b96ffac7..edcb37dbb64 100644
--- a/src/libcore/tuple.rs
+++ b/src/libcore/tuple.rs
@@ -294,7 +294,7 @@ mod tests {
     use super::*;
     use clone::Clone;
     use cmp::*;
-    use realstd::str::{Str, StrAllocating};
+    use realstd::str::Str;
 
     #[test]
     fn test_clone() {