auto merge of #7982 : thestinger/rust/iterator, r=thestinger

f0f4dcc r=huonw
25e9c4c r=graydon
a87c2d1 r=brson
16f369d r=cmr
9f05cc8 r=bstrie
e858055 r=huonw
5d80938 r=thestinger
05d03e7 r=cmr
8f86fa3 r=thestinger

8 files changed, 276 insertions, 94 deletions

diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index 198e63f83c6..0c2a7bb7b40 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -53,6 +53,16 @@ pub trait DoubleEndedIterator<A>: Iterator<A> {
     fn next_back(&mut self) -> Option<A>;
 }
 
+/// An object implementing random access indexing by `uint`
+pub trait RandomAccessIterator<A> {
+    /// Return the number of indexable elements. At most `std::uint::max_value`
+    /// elements are indexable, even if the iterator represents a longer range.
+    fn indexable(&self) -> uint;
+
+    /// Return an element at an index
+    fn idx(&self, index: uint) -> Option<A>;
+}
+
 /// Iterator adaptors provided for every `DoubleEndedIterator` implementation.
 ///
 /// In the future these will be default methods instead of a utility trait.
@@ -316,7 +326,7 @@ pub trait IteratorUtil<A> {
     /// use std::iterator::Counter;
     ///
     /// for Counter::new(0, 10).advance |i| {
-    ///     io::println(fmt!("%d", i));
+    ///     printfln!("%d", i);
     /// }
     /// ~~~
     fn advance(&mut self, f: &fn(A) -> bool) -> bool;
@@ -836,6 +846,30 @@ for ChainIterator<A, T, U> {
     }
 }
 
+impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
+for ChainIterator<A, T, U> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        let (a, b) = (self.a.indexable(), self.b.indexable());
+        let total = a + b;
+        if total < a || total < b {
+            uint::max_value
+        } else {
+            total
+        }
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<A> {
+        let len = self.a.indexable();
+        if index < len {
+            self.a.idx(index)
+        } else {
+            self.b.idx(index - len)
+        }
+    }
+}
+
 /// An iterator which iterates two other iterators simultaneously
 // FIXME #6967: Dummy A & B parameters to get around type inference bug
 #[deriving(Clone)]
@@ -1718,4 +1752,23 @@ mod tests {
         assert_eq!(it.next_back().unwrap(), &7)
         assert_eq!(it.next_back(), None)
     }
+
+    #[test]
+    fn test_random_access_chain() {
+        let xs = [1, 2, 3, 4, 5];
+        let ys = ~[7, 9, 11];
+        let mut it = xs.iter().chain_(ys.iter());
+        assert_eq!(it.idx(0).unwrap(), &1);
+        assert_eq!(it.idx(5).unwrap(), &7);
+        assert_eq!(it.idx(7).unwrap(), &11);
+        assert!(it.idx(8).is_none());
+
+        it.next();
+        it.next();
+        it.next_back();
+
+        assert_eq!(it.idx(0).unwrap(), &3);
+        assert_eq!(it.idx(4).unwrap(), &9);
+        assert!(it.idx(6).is_none());
+    }
 }
diff --git a/src/libstd/num/uint_macros.rs b/src/libstd/num/uint_macros.rs
index 54c1327fa93..acf7ea683fb 100644
--- a/src/libstd/num/uint_macros.rs
+++ b/src/libstd/num/uint_macros.rs
@@ -103,7 +103,7 @@ fn range_step_core(start: $T, stop: $T, step: $T_SIGNED, r: Range, it: &fn($T) -
 /// let nums = [1,2,3,4,5,6,7];
 ///
 /// for uint::range_step(0, nums.len() - 1, 2) |i| {
-///     println(fmt!("%d & %d", nums[i], nums[i+1]));
+///     printfln!("%d & %d", nums[i], nums[i+1]);
 /// }
 /// ~~~
 ///
diff --git a/src/libstd/rand.rs b/src/libstd/rand.rs
index 06c743edd2b..6d0613b2e67 100644
--- a/src/libstd/rand.rs
+++ b/src/libstd/rand.rs
@@ -28,7 +28,7 @@ use std::rand::RngUtil;
 fn main() {
     let mut rng = rand::rng();
     if rng.gen() { // bool
-        println(fmt!("int: %d, uint: %u", rng.gen(), rng.gen()))
+        printfln!("int: %d, uint: %u", rng.gen(), rng.gen())
     }
 }
 ~~~
@@ -38,7 +38,7 @@ use std::rand;
 
 fn main () {
     let tuple_ptr = rand::random::<~(f64, char)>();
-    println(fmt!("%?", tuple_ptr))
+    printfln!(tuple_ptr)
 }
 ~~~
 */
@@ -301,7 +301,7 @@ pub trait RngUtil {
      *
      * fn main() {
      *     let mut rng = rand::rng();
-     *     println(fmt!("%b",rng.gen_weighted_bool(3)));
+     *     printfln!("%b", rng.gen_weighted_bool(3));
      * }
      * ~~~
      */
@@ -335,7 +335,7 @@ pub trait RngUtil {
      *
      * fn main() {
      *     let mut rng = rand::rng();
-     *     println(fmt!("%?",rng.gen_bytes(8)));
+     *     printfln!(rng.gen_bytes(8));
      * }
      * ~~~
      */
@@ -352,7 +352,7 @@ pub trait RngUtil {
      *
      * fn main() {
      *     let mut rng = rand::rng();
-     *     println(fmt!("%d",rng.choose([1,2,4,8,16,32])));
+     *     printfln!("%d", rng.choose([1,2,4,8,16,32]));
      * }
      * ~~~
      */
@@ -375,7 +375,7 @@ pub trait RngUtil {
      *     let x = [rand::Weighted {weight: 4, item: 'a'},
      *              rand::Weighted {weight: 2, item: 'b'},
      *              rand::Weighted {weight: 2, item: 'c'}];
-     *     println(fmt!("%c",rng.choose_weighted(x)));
+     *     printfln!("%c", rng.choose_weighted(x));
      * }
      * ~~~
      */
@@ -396,7 +396,7 @@ pub trait RngUtil {
      *     let x = [rand::Weighted {weight: 4, item: 'a'},
      *              rand::Weighted {weight: 2, item: 'b'},
      *              rand::Weighted {weight: 2, item: 'c'}];
-     *     println(fmt!("%?",rng.choose_weighted_option(x)));
+     *     printfln!(rng.choose_weighted_option(x));
      * }
      * ~~~
      */
@@ -418,7 +418,7 @@ pub trait RngUtil {
      *     let x = [rand::Weighted {weight: 4, item: 'a'},
      *              rand::Weighted {weight: 2, item: 'b'},
      *              rand::Weighted {weight: 2, item: 'c'}];
-     *     println(fmt!("%?",rng.weighted_vec(x)));
+     *     printfln!(rng.weighted_vec(x));
      * }
      * ~~~
      */
@@ -435,7 +435,7 @@ pub trait RngUtil {
      *
      * fn main() {
      *     let mut rng = rand::rng();
-     *     println(fmt!("%?",rng.shuffle([1,2,3])));
+     *     printfln!(rng.shuffle([1,2,3]));
      * }
      * ~~~
      */
@@ -454,9 +454,9 @@ pub trait RngUtil {
      *     let mut rng = rand::rng();
      *     let mut y = [1,2,3];
      *     rng.shuffle_mut(y);
-     *     println(fmt!("%?",y));
+     *     printfln!(y);
      *     rng.shuffle_mut(y);
-     *     println(fmt!("%?",y));
+     *     printfln!(y);
      * }
      * ~~~
      */
diff --git a/src/libstd/rand/distributions.rs b/src/libstd/rand/distributions.rs
index 4d983b94954..56eae042875 100644
--- a/src/libstd/rand/distributions.rs
+++ b/src/libstd/rand/distributions.rs
@@ -70,7 +70,7 @@ fn ziggurat<R:Rng>(rng: &mut R,
 ///
 /// fn main() {
 ///     let normal = 2.0 + (*rand::random::<StandardNormal>()) * 3.0;
-///     println(fmt!("%f is from a N(2, 9) distribution", normal))
+///     printfln!("%f is from a N(2, 9) distribution", normal)
 /// }
 /// ~~~
 pub struct StandardNormal(f64);
@@ -124,7 +124,7 @@ impl Rand for StandardNormal {
 ///
 /// fn main() {
 ///     let exp2 = (*rand::random::<Exp1>()) * 0.5;
-///     println(fmt!("%f is from a Exp(2) distribution", exp2));
+///     printfln!("%f is from a Exp(2) distribution", exp2);
 /// }
 /// ~~~
 pub struct Exp1(f64);
diff --git a/src/libstd/rt/args.rs b/src/libstd/rt/args.rs
index 75ee4f381f6..85cdb9fc941 100644
--- a/src/libstd/rt/args.rs
+++ b/src/libstd/rt/args.rs
@@ -14,112 +14,167 @@
 //! the processes `argc` and `argv` arguments to be stored
 //! in a globally-accessible location for use by the `os` module.
 //!
+//! Only valid to call on linux. Mac and Windows use syscalls to
+//! discover the command line arguments.
+//!
 //! XXX: Would be nice for this to not exist.
 //! XXX: This has a lot of C glue for lack of globals.
 
-use libc;
-use option::{Option, Some, None};
-use str;
-use uint;
-use unstable::finally::Finally;
-use util;
+use option::Option;
 
 /// One-time global initialization.
 pub unsafe fn init(argc: int, argv: **u8) {
-    let args = load_argc_and_argv(argc, argv);
-    put(args);
+    imp::init(argc, argv)
 }
 
 /// One-time global cleanup.
 pub fn cleanup() {
-    rtassert!(take().is_some());
+    imp::cleanup()
 }
 
 /// Take the global arguments from global storage.
 pub fn take() -> Option<~[~str]> {
-    with_lock(|| unsafe {
-        let ptr = get_global_ptr();
-        let val = util::replace(&mut *ptr, None);
-        val.map(|s: &~~[~str]| (**s).clone())
-    })
+    imp::take()
 }
 
 /// Give the global arguments to global storage.
 ///
 /// It is an error if the arguments already exist.
 pub fn put(args: ~[~str]) {
-    with_lock(|| unsafe {
-        let ptr = get_global_ptr();
-        rtassert!((*ptr).is_none());
-        (*ptr) = Some(~args.clone());
-    })
+    imp::put(args)
 }
 
 /// Make a clone of the global arguments.
 pub fn clone() -> Option<~[~str]> {
-    with_lock(|| unsafe {
-        let ptr = get_global_ptr();
-        (*ptr).map(|s: &~~[~str]| (**s).clone())
-    })
+    imp::clone()
 }
 
-fn with_lock<T>(f: &fn() -> T) -> T {
-    do (|| {
-        unsafe {
-            rust_take_global_args_lock();
-            f()
+#[cfg(target_os = "linux")]
+#[cfg(target_os = "android")]
+#[cfg(target_os = "freebsd")]
+mod imp {
+
+    use libc;
+    use option::{Option, Some, None};
+    use str;
+    use uint;
+    use unstable::finally::Finally;
+    use util;
+
+    pub unsafe fn init(argc: int, argv: **u8) {
+        let args = load_argc_and_argv(argc, argv);
+        put(args);
+    }
+
+    pub fn cleanup() {
+        rtassert!(take().is_some());
+    }
+
+    pub fn take() -> Option<~[~str]> {
+        with_lock(|| unsafe {
+            let ptr = get_global_ptr();
+            let val = util::replace(&mut *ptr, None);
+            val.map(|s: &~~[~str]| (**s).clone())
+        })
+    }
+
+    pub fn put(args: ~[~str]) {
+        with_lock(|| unsafe {
+            let ptr = get_global_ptr();
+            rtassert!((*ptr).is_none());
+            (*ptr) = Some(~args.clone());
+        })
+    }
+
+    pub fn clone() -> Option<~[~str]> {
+        with_lock(|| unsafe {
+            let ptr = get_global_ptr();
+            (*ptr).map(|s: &~~[~str]| (**s).clone())
+        })
+    }
+
+    fn with_lock<T>(f: &fn() -> T) -> T {
+        do (|| {
+            unsafe {
+                rust_take_global_args_lock();
+                f()
+            }
+        }).finally {
+            unsafe {
+                rust_drop_global_args_lock();
+            }
         }
-    }).finally {
-        unsafe {
-            rust_drop_global_args_lock();
+    }
+
+    fn get_global_ptr() -> *mut Option<~~[~str]> {
+        unsafe { rust_get_global_args_ptr() }
+    }
+
+    // Copied from `os`.
+    unsafe fn load_argc_and_argv(argc: int, argv: **u8) -> ~[~str] {
+        let mut args = ~[];
+        for uint::range(0, argc as uint) |i| {
+            args.push(str::raw::from_c_str(*(argv as **libc::c_char).offset(i)));
         }
+        return args;
     }
-}
 
-fn get_global_ptr() -> *mut Option<~~[~str]> {
-    unsafe { rust_get_global_args_ptr() }
-}
+    extern {
+        fn rust_take_global_args_lock();
+        fn rust_drop_global_args_lock();
+        fn rust_get_global_args_ptr() -> *mut Option<~~[~str]>;
+    }
 
-// Copied from `os`.
-unsafe fn load_argc_and_argv(argc: int, argv: **u8) -> ~[~str] {
-    let mut args = ~[];
-    for uint::range(0, argc as uint) |i| {
-        args.push(str::raw::from_c_str(*(argv as **libc::c_char).offset(i)));
+    #[cfg(test)]
+    mod tests {
+        use option::{Some, None};
+        use super::*;
+        use unstable::finally::Finally;
+
+        #[test]
+        fn smoke_test() {
+            // Preserve the actual global state.
+            let saved_value = take();
+
+            let expected = ~[~"happy", ~"today?"];
+
+            put(expected.clone());
+            assert!(clone() == Some(expected.clone()));
+            assert!(take() == Some(expected.clone()));
+            assert!(take() == None);
+
+            do (|| {
+            }).finally {
+                // Restore the actual global state.
+                match saved_value {
+                    Some(ref args) => put(args.clone()),
+                    None => ()
+                }
+            }
+        }
     }
-    return args;
 }
 
-extern {
-    fn rust_take_global_args_lock();
-    fn rust_drop_global_args_lock();
-    fn rust_get_global_args_ptr() -> *mut Option<~~[~str]>;
-}
+#[cfg(target_os = "macos")]
+#[cfg(target_os = "win32")]
+mod imp {
+    use option::Option;
 
-#[cfg(test)]
-mod tests {
-    use option::{Some, None};
-    use super::*;
-    use unstable::finally::Finally;
+    pub unsafe fn init(_argc: int, _argv: **u8) {
+    }
 
-    #[test]
-    fn smoke_test() {
-        // Preserve the actual global state.
-        let saved_value = take();
+    pub fn cleanup() {
+    }
 
-        let expected = ~[~"happy", ~"today?"];
+    pub fn take() -> Option<~[~str]> {
+        fail!()
+    }
 
-        put(expected.clone());
-        assert!(clone() == Some(expected.clone()));
-        assert!(take() == Some(expected.clone()));
-        assert!(take() == None);
+    pub fn put(_args: ~[~str]) {
+        fail!()
+    }
 
-        do (|| {
-        }).finally {
-            // Restore the actual global state.
-            match saved_value {
-                Some(ref args) => put(args.clone()),
-                None => ()
-            }
-        }
+    pub fn clone() -> Option<~[~str]> {
+        fail!()
     }
 }
diff --git a/src/libstd/str.rs b/src/libstd/str.rs
index c49a0050266..5b83112fe6b 100644
--- a/src/libstd/str.rs
+++ b/src/libstd/str.rs
@@ -1727,7 +1727,7 @@ impl<'self> StrSlice<'self> for &'self str {
      * let i = 0u;
      * while i < s.len() {
      *     let CharRange {ch, next} = s.char_range_at(i);
-     *     std::io::println(fmt!("%u: %c",i,ch));
+     *     printfln!("%u: %c", i, ch);
      *     i = next;
      * }
      * ~~~
diff --git a/src/libstd/to_str.rs b/src/libstd/to_str.rs
index 227712e31e6..50cbd36ced9 100644
--- a/src/libstd/to_str.rs
+++ b/src/libstd/to_str.rs
@@ -50,7 +50,7 @@ impl<A:ToStr> ToStr for (A,) {
     }
 }
 
-impl<A:ToStr+Hash+Eq, B:ToStr+Hash+Eq> ToStr for HashMap<A, B> {
+impl<A:ToStr+Hash+Eq, B:ToStr> ToStr for HashMap<A, B> {
     #[inline]
     fn to_str(&self) -> ~str {
         let mut acc = ~"{";
@@ -182,6 +182,8 @@ mod tests {
     use hashmap::HashMap;
     use hashmap::HashSet;
     use container::{MutableSet, MutableMap};
+    use super::*;
+
     #[test]
     fn test_simple_types() {
         assert_eq!(1i.to_str(), ~"1");
@@ -212,17 +214,27 @@ mod tests {
                ~"[[], [1], [1, 1]]");
     }
 
+    struct StructWithToStrWithoutEqOrHash {
+        value: int
+    }
+
+    impl ToStr for StructWithToStrWithoutEqOrHash {
+        fn to_str(&self) -> ~str {
+            fmt!("s%d", self.value)
+        }
+    }
+
     #[test]
     fn test_hashmap() {
-        let mut table: HashMap<int, int> = HashMap::new();
-        let empty: HashMap<int, int> = HashMap::new();
+        let mut table: HashMap<int, StructWithToStrWithoutEqOrHash> = HashMap::new();
+        let empty: HashMap<int, StructWithToStrWithoutEqOrHash> = HashMap::new();
 
-        table.insert(3, 4);
-        table.insert(1, 2);
+        table.insert(3, StructWithToStrWithoutEqOrHash { value: 4 });
+        table.insert(1, StructWithToStrWithoutEqOrHash { value: 2 });
 
         let table_str = table.to_str();
 
-        assert!(table_str == ~"{1: 2, 3: 4}" || table_str == ~"{3: 4, 1: 2}");
+        assert!(table_str == ~"{1: s2, 3: s4}" || table_str == ~"{3: s4, 1: s2}");
         assert_eq!(empty.to_str(), ~"{}");
     }
 
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index baeb87e51b9..8432f28a969 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -833,7 +833,7 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
      * ~~~ {.rust}
      * let v = &[1,2,3,4];
      * for v.window_iter().advance |win| {
-     *     io::println(fmt!("%?", win));
+     *     printfln!(win);
      * }
      * ~~~
      *
@@ -862,7 +862,7 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
      * ~~~ {.rust}
      * let v = &[1,2,3,4,5];
      * for v.chunk_iter().advance |win| {
-     *     io::println(fmt!("%?", win));
+     *     printfln!(win);
      * }
      * ~~~
      *
@@ -2116,8 +2116,7 @@ macro_rules! iterator {
 
             #[inline]
             fn size_hint(&self) -> (uint, Option<uint>) {
-                let diff = (self.end as uint) - (self.ptr as uint);
-                let exact = diff / sys::nonzero_size_of::<$elem>();
+                let exact = self.indexable();
                 (exact, Some(exact))
             }
         }
@@ -2145,6 +2144,28 @@ macro_rules! double_ended_iterator {
     }
 }
 
+macro_rules! random_access_iterator {
+    (impl $name:ident -> $elem:ty) => {
+        impl<'self, T> RandomAccessIterator<$elem> for $name<'self, T> {
+            #[inline]
+            fn indexable(&self) -> uint {
+                let diff = (self.end as uint) - (self.ptr as uint);
+                diff / sys::nonzero_size_of::<T>()
+            }
+
+            fn idx(&self, index: uint) -> Option<$elem> {
+                unsafe {
+                    if index < self.indexable() {
+                        cast::transmute(self.ptr.offset(index))
+                    } else {
+                        None
+                    }
+                }
+            }
+        }
+    }
+}
+
 //iterator!{struct VecIterator -> *T, &'self T}
 /// An iterator for iterating over a vector.
 pub struct VecIterator<'self, T> {
@@ -2154,6 +2175,7 @@ pub struct VecIterator<'self, T> {
 }
 iterator!{impl VecIterator -> &'self T}
 double_ended_iterator!{impl VecIterator -> &'self T}
+random_access_iterator!{impl VecIterator -> &'self T}
 pub type VecRevIterator<'self, T> = InvertIterator<&'self T, VecIterator<'self, T>>;
 
 impl<'self, T> Clone for VecIterator<'self, T> {
@@ -2169,6 +2191,7 @@ pub struct VecMutIterator<'self, T> {
 }
 iterator!{impl VecMutIterator -> &'self mut T}
 double_ended_iterator!{impl VecMutIterator -> &'self mut T}
+random_access_iterator!{impl VecMutIterator -> &'self mut T}
 pub type VecMutRevIterator<'self, T> = InvertIterator<&'self mut T, VecMutIterator<'self, T>>;
 
 /// An iterator that moves out of a vector.
@@ -3109,6 +3132,45 @@ mod tests {
     }
 
     #[test]
+    fn test_random_access_iterator() {
+        use iterator::*;
+        let xs = [1, 2, 5, 10, 11];
+        let mut it = xs.iter();
+
+        assert_eq!(it.indexable(), 5);
+        assert_eq!(it.idx(0).unwrap(), &1);
+        assert_eq!(it.idx(2).unwrap(), &5);
+        assert_eq!(it.idx(4).unwrap(), &11);
+        assert!(it.idx(5).is_none());
+
+        assert_eq!(it.next().unwrap(), &1);
+        assert_eq!(it.indexable(), 4);
+        assert_eq!(it.idx(0).unwrap(), &2);
+        assert_eq!(it.idx(3).unwrap(), &11);
+        assert!(it.idx(4).is_none());
+
+        assert_eq!(it.next().unwrap(), &2);
+        assert_eq!(it.indexable(), 3);
+        assert_eq!(it.idx(1).unwrap(), &10);
+        assert!(it.idx(3).is_none());
+
+        assert_eq!(it.next().unwrap(), &5);
+        assert_eq!(it.indexable(), 2);
+        assert_eq!(it.idx(1).unwrap(), &11);
+
+        assert_eq!(it.next().unwrap(), &10);
+        assert_eq!(it.indexable(), 1);
+        assert_eq!(it.idx(0).unwrap(), &11);
+        assert!(it.idx(1).is_none());
+
+        assert_eq!(it.next().unwrap(), &11);
+        assert_eq!(it.indexable(), 0);
+        assert!(it.idx(0).is_none());
+
+        assert!(it.next().is_none());
+    }
+
+    #[test]
     fn test_iter_size_hints() {
         use iterator::*;
         let mut xs = [1, 2, 5, 10, 11];