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

The `extra::iter` module wasn't actually included in `extra.rs` when it was moved from `std`... I assume no one is going to miss it.

5 files changed, 89 insertions, 31 deletions

diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index e86f4d7a85e..1be398966bb 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -313,7 +313,7 @@ pub trait IteratorUtil<A> {
     /// ~~~ {.rust}
     /// let xs = [2u, 3];
     /// let ys = [0u, 1, 0, 1, 2];
-    /// let mut it = xs.iter().flat_map_(|&x| Counter::new(0u, 1).take_(x));
+    /// let mut it = xs.iter().flat_map_(|&x| count(0u, 1).take_(x));
     /// // Check that `it` has the same elements as `ys`
     /// let mut i = 0;
     /// for x: uint in it {
@@ -351,7 +351,7 @@ pub trait IteratorUtil<A> {
     /// ~~~ {.rust}
     /// use std::iterator::Counter;
     ///
-    /// for i in Counter::new(0, 10) {
+    /// for i in count(0, 10) {
     ///     printfln!("%d", i);
     /// }
     /// ~~~
@@ -723,7 +723,7 @@ pub trait MultiplicativeIterator<A> {
     /// use std::iterator::Counter;
     ///
     /// fn factorial(n: uint) -> uint {
-    ///     Counter::new(1u, 1).take_while(|&i| i <= n).product()
+    ///     count(1u, 1).take_while(|&i| i <= n).product()
     /// }
     /// assert!(factorial(0) == 1);
     /// assert!(factorial(1) == 1);
@@ -790,7 +790,7 @@ pub trait ClonableIterator {
     /// # Example
     ///
     /// ~~~ {.rust}
-    /// let a = Counter::new(1,1).take_(1);
+    /// let a = count(1,1).take_(1);
     /// let mut cy = a.cycle();
     /// assert_eq!(cy.next(), Some(1));
     /// assert_eq!(cy.next(), Some(1));
@@ -1300,10 +1300,9 @@ pub struct Take<T> {
 impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
     #[inline]
     fn next(&mut self) -> Option<A> {
-        let next = self.iter.next();
         if self.n != 0 {
             self.n -= 1;
-            next
+            self.iter.next()
         } else {
             None
         }
@@ -1512,12 +1511,10 @@ pub struct Counter<A> {
     step: A
 }
 
-impl<A> Counter<A> {
-    /// Creates a new counter with the specified start/step
-    #[inline]
-    pub fn new(start: A, step: A) -> Counter<A> {
-        Counter{state: start, step: step}
-    }
+/// Creates a new counter with the specified start/step
+#[inline]
+pub fn count<A>(start: A, step: A) -> Counter<A> {
+    Counter{state: start, step: step}
 }
 
 /// A range of numbers from [0, N)
@@ -1604,7 +1601,7 @@ mod tests {
 
     #[test]
     fn test_counter_from_iter() {
-        let mut it = Counter::new(0, 5).take_(10);
+        let mut it = count(0, 5).take_(10);
         let xs: ~[int] = FromIterator::from_iterator(&mut it);
         assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
     }
@@ -1622,7 +1619,7 @@ mod tests {
         }
         assert_eq!(i, expected.len());
 
-        let ys = Counter::new(30u, 10).take_(4);
+        let ys = count(30u, 10).take_(4);
         let mut it = xs.iter().transform(|&x| x).chain_(ys);
         let mut i = 0;
         for x in it {
@@ -1634,7 +1631,7 @@ mod tests {
 
     #[test]
     fn test_filter_map() {
-        let mut it = Counter::new(0u, 1u).take_(10)
+        let mut it = count(0u, 1u).take_(10)
             .filter_map(|x| if x.is_even() { Some(x*x) } else { None });
         assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]);
     }
@@ -1723,7 +1720,7 @@ mod tests {
     fn test_iterator_flat_map() {
         let xs = [0u, 3, 6];
         let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
-        let mut it = xs.iter().flat_map_(|&x| Counter::new(x, 1).take_(3));
+        let mut it = xs.iter().flat_map_(|&x| count(x, 1).take_(3));
         let mut i = 0;
         for x in it {
             assert_eq!(x, ys[i]);
@@ -1770,13 +1767,13 @@ mod tests {
     #[test]
     fn test_cycle() {
         let cycle_len = 3;
-        let it = Counter::new(0u, 1).take_(cycle_len).cycle();
+        let it = count(0u, 1).take_(cycle_len).cycle();
         assert_eq!(it.size_hint(), (uint::max_value, None));
         for (i, x) in it.take_(100).enumerate() {
             assert_eq!(i % cycle_len, x);
         }
 
-        let mut it = Counter::new(0u, 1).take_(0).cycle();
+        let mut it = count(0u, 1).take_(0).cycle();
         assert_eq!(it.size_hint(), (0, Some(0)));
         assert_eq!(it.next(), None);
     }
@@ -1838,7 +1835,7 @@ mod tests {
 
     #[test]
     fn test_iterator_size_hint() {
-        let c = Counter::new(0, 1);
+        let c = count(0, 1);
         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
         let v2 = &[10, 11, 12];
         let vi = v.iter();
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index 517bc4a441a..65db55297b3 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -49,6 +49,7 @@ pub use char::Char;
 pub use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
 pub use hash::Hash;
 pub use iter::Times;
+pub use iterator::Extendable;
 pub use iterator::{Iterator, IteratorUtil, DoubleEndedIterator, DoubleEndedIteratorUtil};
 pub use iterator::{ClonableIterator, OrdIterator};
 pub use num::{Num, NumCast};
@@ -64,7 +65,7 @@ pub use path::WindowsPath;
 pub use ptr::RawPtr;
 pub use ascii::{Ascii, AsciiCast, OwnedAsciiCast, AsciiStr, ToBytesConsume};
 pub use str::{Str, StrVector, StrSlice, OwnedStr, NullTerminatedStr};
-pub use from_str::{FromStr};
+pub use from_str::FromStr;
 pub use to_bytes::IterBytes;
 pub use to_str::{ToStr, ToStrConsume};
 pub use tuple::{CopyableTuple, ImmutableTuple, ExtendedTupleOps};
diff --git a/src/libstd/ptr.rs b/src/libstd/ptr.rs
index dfd11f9227d..5a2bd0c4de9 100644
--- a/src/libstd/ptr.rs
+++ b/src/libstd/ptr.rs
@@ -272,6 +272,7 @@ pub trait RawPtr<T> {
     fn is_not_null(&self) -> bool;
     unsafe fn to_option(&self) -> Option<&T>;
     fn offset(&self, count: int) -> Self;
+    unsafe fn offset_inbounds(self, count: int) -> Self;
 }
 
 /// Extension methods for immutable pointers
@@ -304,6 +305,22 @@ impl<T> RawPtr<T> for *T {
     /// Calculates the offset from a pointer.
     #[inline]
     fn offset(&self, count: int) -> *T { offset(*self, count) }
+
+    /// Calculates the offset from a pointer. The offset *must* be in-bounds of
+    /// the object, or one-byte-past-the-end.
+    #[inline]
+    #[cfg(stage0)]
+    unsafe fn offset_inbounds(self, count: int) -> *T {
+        intrinsics::offset(self, count)
+    }
+
+    /// Calculates the offset from a pointer. The offset *must* be in-bounds of
+    /// the object, or one-byte-past-the-end.
+    #[inline]
+    #[cfg(not(stage0))]
+    unsafe fn offset_inbounds(self, count: int) -> *T {
+        intrinsics::offset_inbounds(self, count)
+    }
 }
 
 /// Extension methods for mutable pointers
@@ -336,6 +353,30 @@ impl<T> RawPtr<T> for *mut T {
     /// Calculates the offset from a mutable pointer.
     #[inline]
     fn offset(&self, count: int) -> *mut T { mut_offset(*self, count) }
+
+    /// Calculates the offset from a pointer. The offset *must* be in-bounds of
+    /// the object, or one-byte-past-the-end. An arithmetic overflow is also
+    /// undefined behaviour.
+    ///
+    /// This method should be preferred over `offset` when the guarantee can be
+    /// satisfied, to enable better optimization.
+    #[inline]
+    #[cfg(stage0)]
+    unsafe fn offset_inbounds(self, count: int) -> *mut T {
+        intrinsics::offset(self as *T, count) as *mut T
+    }
+
+    /// Calculates the offset from a pointer. The offset *must* be in-bounds of
+    /// the object, or one-byte-past-the-end. An arithmetic overflow is also
+    /// undefined behaviour.
+    ///
+    /// This method should be preferred over `offset` when the guarantee can be
+    /// satisfied, to enable better optimization.
+    #[inline]
+    #[cfg(not(stage0))]
+    unsafe fn offset_inbounds(self, count: int) -> *mut T {
+        intrinsics::offset_inbounds(self as *T, count) as *mut T
+    }
 }
 
 // Equality for pointers
diff --git a/src/libstd/unstable/intrinsics.rs b/src/libstd/unstable/intrinsics.rs
index 1270a80c354..c60edad3dbd 100644
--- a/src/libstd/unstable/intrinsics.rs
+++ b/src/libstd/unstable/intrinsics.rs
@@ -317,12 +317,21 @@ extern "rust-intrinsic" {
     /// Get the address of the `__morestack` stack growth function.
     pub fn morestack_addr() -> *();
 
-    /// Adjust a pointer by an offset.
+    /// Calculates the offset from a pointer.
     ///
     /// This is implemented as an intrinsic to avoid converting to and from an
     /// integer, since the conversion would throw away aliasing information.
     pub fn offset<T>(dst: *T, offset: int) -> *T;
 
+    /// Calculates the offset from a pointer. The offset *must* be in-bounds of
+    /// the object, or one-byte-past-the-end. An arithmetic overflow is also
+    /// undefined behaviour.
+    ///
+    /// This intrinsic should be preferred over `offset` when the guarantee can
+    /// be satisfied, to enable better optimization.
+    #[cfg(not(stage0))]
+    pub fn offset_inbounds<T>(dst: *T, offset: int) -> *T;
+
     /// Equivalent to the `llvm.memcpy.p0i8.0i8.i32` intrinsic, with a size of
     /// `count` * `size_of::<T>()` and an alignment of `min_align_of::<T>()`
     pub fn memcpy32<T>(dst: *mut T, src: *T, count: u32);
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 0259b547ab3..36201dc5e82 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -849,10 +849,15 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     fn iter(self) -> VecIterator<'self, T> {
         unsafe {
             let p = vec::raw::to_ptr(self);
-            VecIterator{ptr: p,
-                        end: (p as uint + self.len() *
-                              sys::nonzero_size_of::<T>()) as *T,
-                        lifetime: cast::transmute(p)}
+            if sys::size_of::<T>() == 0 {
+                VecIterator{ptr: p,
+                            end: (p as uint + self.len()) as *T,
+                            lifetime: cast::transmute(p)}
+            } else {
+                VecIterator{ptr: p,
+                            end: p.offset_inbounds(self.len() as int),
+                            lifetime: cast::transmute(p)}
+            }
         }
     }
 
@@ -1826,10 +1831,15 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] {
     fn mut_iter(self) -> VecMutIterator<'self, T> {
         unsafe {
             let p = vec::raw::to_mut_ptr(self);
-            VecMutIterator{ptr: p,
-                           end: (p as uint + self.len() *
-                                 sys::nonzero_size_of::<T>()) as *mut T,
-                           lifetime: cast::transmute(p)}
+            if sys::size_of::<T>() == 0 {
+                VecMutIterator{ptr: p,
+                               end: (p as uint + self.len()) as *mut T,
+                               lifetime: cast::transmute(p)}
+            } else {
+                VecMutIterator{ptr: p,
+                               end: p.offset_inbounds(self.len() as int),
+                               lifetime: cast::transmute(p)}
+            }
         }
     }
 
@@ -2183,7 +2193,7 @@ macro_rules! iterator {
                             // same pointer.
                             cast::transmute(self.ptr as uint + 1)
                         } else {
-                            self.ptr.offset(1)
+                            self.ptr.offset_inbounds(1)
                         };
 
                         Some(cast::transmute(old))
@@ -2215,7 +2225,7 @@ macro_rules! double_ended_iterator {
                             // See above for why 'ptr.offset' isn't used
                             cast::transmute(self.end as uint - 1)
                         } else {
-                            self.end.offset(-1)
+                            self.end.offset_inbounds(-1)
                         };
                         Some(cast::transmute(self.end))
                     }