Implement generalized object and type parameter bounds (Fixes #16462)

7 files changed, 219 insertions, 30 deletions

diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index 418bb147d20..47c56375ada 100644
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -49,19 +49,29 @@ struct Node<T> {
     value: T,
 }
 
-/// An iterator over references to the items of a `DList`.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct Items<'a, T> {
     head: &'a Link<T>,
     tail: Rawlink<Node<T>>,
     nelem: uint,
 }
 
+/// An iterator over references to the items of a `DList`.
+#[cfg(not(stage0))]
+pub struct Items<'a, T:'a> {
+    head: &'a Link<T>,
+    tail: Rawlink<Node<T>>,
+    nelem: uint,
+}
+
 // FIXME #11820: the &'a Option<> of the Link stops clone working.
 impl<'a, T> Clone for Items<'a, T> {
     fn clone(&self) -> Items<'a, T> { *self }
 }
 
-/// An iterator over mutable references to the items of a `DList`.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct MutItems<'a, T> {
     list: &'a mut DList<T>,
     head: Rawlink<Node<T>>,
@@ -69,7 +79,16 @@ pub struct MutItems<'a, T> {
     nelem: uint,
 }
 
-/// A consuming iterator over the items of a `DList`.
+/// An iterator over mutable references to the items of a `DList`.
+#[cfg(not(stage0))]
+pub struct MutItems<'a, T:'a> {
+    list: &'a mut DList<T>,
+    head: Rawlink<Node<T>>,
+    tail: Rawlink<Node<T>>,
+    nelem: uint,
+}
+
+/// An iterator over mutable references to the items of a `DList`.
 #[deriving(Clone)]
 pub struct MoveItems<T> {
     list: DList<T>
diff --git a/src/libcollections/priority_queue.rs b/src/libcollections/priority_queue.rs
index 674fa129943..905078ccc3c 100644
--- a/src/libcollections/priority_queue.rs
+++ b/src/libcollections/priority_queue.rs
@@ -515,11 +515,18 @@ impl<T: Ord> PriorityQueue<T> {
     }
 }
 
-/// `PriorityQueue` iterator.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct Items <'a, T> {
     iter: slice::Items<'a, T>,
 }
 
+/// `PriorityQueue` iterator.
+#[cfg(not(stage0))]
+pub struct Items <'a, T:'a> {
+    iter: slice::Items<'a, T>,
+}
+
 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
     #[inline]
     fn next(&mut self) -> Option<(&'a T)> { self.iter.next() }
diff --git a/src/libcollections/ringbuf.rs b/src/libcollections/ringbuf.rs
index 2f0fbfadb17..6b293c9f4d8 100644
--- a/src/libcollections/ringbuf.rs
+++ b/src/libcollections/ringbuf.rs
@@ -293,7 +293,8 @@ impl<T> RingBuf<T> {
     }
 }
 
-/// `RingBuf` iterator.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct Items<'a, T> {
     lo: uint,
     index: uint,
@@ -301,6 +302,15 @@ pub struct Items<'a, T> {
     elts: &'a [Option<T>],
 }
 
+/// `RingBuf` iterator.
+#[cfg(not(stage0))]
+pub struct Items<'a, T:'a> {
+    lo: uint,
+    index: uint,
+    rindex: uint,
+    elts: &'a [Option<T>],
+}
+
 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
     #[inline]
     fn next(&mut self) -> Option<&'a T> {
@@ -348,13 +358,22 @@ impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
     }
 }
 
-/// `RingBuf` mutable iterator.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct MutItems<'a, T> {
     remaining1: &'a mut [Option<T>],
     remaining2: &'a mut [Option<T>],
     nelts: uint,
 }
 
+/// `RingBuf` mutable iterator.
+#[cfg(not(stage0))]
+pub struct MutItems<'a, T:'a> {
+    remaining1: &'a mut [Option<T>],
+    remaining2: &'a mut [Option<T>],
+    nelts: uint,
+}
+
 impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
     #[inline]
     #[allow(deprecated)] // mut_shift_ref
diff --git a/src/libcollections/smallintmap.rs b/src/libcollections/smallintmap.rs
index 534262d79c9..5ef1dd2ab22 100644
--- a/src/libcollections/smallintmap.rs
+++ b/src/libcollections/smallintmap.rs
@@ -489,19 +489,37 @@ macro_rules! double_ended_iterator {
     }
 }
 
-/// Forward iterator over a map.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct Entries<'a, T> {
     front: uint,
     back: uint,
     iter: slice::Items<'a, Option<T>>
 }
 
+/// Forward iterator over a map.
+#[cfg(not(stage0))]
+pub struct Entries<'a, T:'a> {
+    front: uint,
+    back: uint,
+    iter: slice::Items<'a, Option<T>>
+}
+
 iterator!(impl Entries -> (uint, &'a T), get_ref)
 double_ended_iterator!(impl Entries -> (uint, &'a T), get_ref)
 
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
+pub struct MutEntries<'a, T> {
+    front: uint,
+    back: uint,
+    iter: slice::MutItems<'a, Option<T>>
+}
+
 /// Forward iterator over the key-value pairs of a map, with the
 /// values being mutable.
-pub struct MutEntries<'a, T> {
+#[cfg(not(stage0))]
+pub struct MutEntries<'a, T:'a> {
     front: uint,
     back: uint,
     iter: slice::MutItems<'a, Option<T>>
diff --git a/src/libcollections/treemap.rs b/src/libcollections/treemap.rs
index 8e5ffbd1686..6bb1e4a5ad0 100644
--- a/src/libcollections/treemap.rs
+++ b/src/libcollections/treemap.rs
@@ -668,7 +668,8 @@ impl<K: Ord, V> TreeMap<K, V> {
     }
 }
 
-/// A lazy forward iterator over a map.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct Entries<'a, K, V> {
     stack: Vec<&'a TreeNode<K, V>>,
     // See the comment on MutEntries; this is just to allow
@@ -679,13 +680,32 @@ pub struct Entries<'a, K, V> {
     remaining_max: uint
 }
 
-/// Lazy backward iterator over a map.
+/// Lazy forward iterator over a map
+#[cfg(not(stage0))]
+pub struct Entries<'a, K:'a, V:'a> {
+    stack: Vec<&'a TreeNode<K, V>>,
+    // See the comment on MutEntries; this is just to allow
+    // code-sharing (for this immutable-values iterator it *could* very
+    // well be Option<&'a TreeNode<K,V>>).
+    node: *const TreeNode<K, V>,
+    remaining_min: uint,
+    remaining_max: uint
+}
+
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct RevEntries<'a, K, V> {
     iter: Entries<'a, K, V>,
 }
 
-/// A lazy forward iterator over a map that allows for the mutation of
-/// the values.
+/// Lazy backward iterator over a map
+#[cfg(not(stage0))]
+pub struct RevEntries<'a, K:'a, V:'a> {
+    iter: Entries<'a, K, V>,
+}
+
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct MutEntries<'a, K, V> {
     stack: Vec<&'a mut TreeNode<K, V>>,
     // Unfortunately, we require some unsafe-ness to get around the
@@ -712,11 +732,46 @@ pub struct MutEntries<'a, K, V> {
     remaining_max: uint
 }
 
-/// Lazy backward iterator over a map.
+/// Lazy forward iterator over a map that allows for the mutation of
+/// the values.
+#[cfg(not(stage0))]
+pub struct MutEntries<'a, K:'a, V:'a> {
+    stack: Vec<&'a mut TreeNode<K, V>>,
+    // Unfortunately, we require some unsafe-ness to get around the
+    // fact that we would be storing a reference *into* one of the
+    // nodes in the stack.
+    //
+    // As far as the compiler knows, this would let us invalidate the
+    // reference by assigning a new value to this node's position in
+    // its parent, which would cause this current one to be
+    // deallocated so this reference would be invalid. (i.e. the
+    // compilers complaints are 100% correct.)
+    //
+    // However, as far as you humans reading this code know (or are
+    // about to know, if you haven't read far enough down yet), we are
+    // only reading from the TreeNode.{left,right} fields. the only
+    // thing that is ever mutated is the .value field (although any
+    // actual mutation that happens is done externally, by the
+    // iterator consumer). So, don't be so concerned, rustc, we've got
+    // it under control.
+    //
+    // (This field can legitimately be null.)
+    node: *mut TreeNode<K, V>,
+    remaining_min: uint,
+    remaining_max: uint
+}
+
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct RevMutEntries<'a, K, V> {
     iter: MutEntries<'a, K, V>,
 }
 
+/// Lazy backward iterator over a map
+#[cfg(not(stage0))]
+pub struct RevMutEntries<'a, K:'a, V:'a> {
+    iter: MutEntries<'a, K, V>,
+}
 
 /// TreeMap keys iterator.
 pub type Keys<'a, K, V> =
@@ -885,9 +940,7 @@ fn mut_deref<K, V>(x: &mut Option<Box<TreeNode<K, V>>>)
     }
 }
 
-
-
-/// A lazy forward iterator over a map that consumes the map while iterating.
+/// Lazy forward iterator over a map that consumes the map while iterating
 pub struct MoveEntries<K, V> {
     stack: Vec<TreeNode<K, V>>,
     remaining: uint
@@ -1322,45 +1375,90 @@ impl<T: Ord> TreeSet<T> {
     }
 }
 
-/// A lazy forward iterator over a set.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct SetItems<'a, T> {
     iter: Entries<'a, T, ()>
 }
 
-/// Lazy backward iterator over a set.
+/// A lazy forward iterator over a set.
+#[cfg(not(stage0))]
+pub struct SetItems<'a, T:'a> {
+    iter: Entries<'a, T, ()>
+}
+
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct RevSetItems<'a, T> {
     iter: RevEntries<'a, T, ()>
 }
 
+/// A lazy backward iterator over a set.
+#[cfg(not(stage0))]
+pub struct RevSetItems<'a, T:'a> {
+    iter: RevEntries<'a, T, ()>
+}
+
 /// A lazy forward iterator over a set that consumes the set while iterating.
 pub type MoveSetItems<T> = iter::Map<'static, (T, ()), T, MoveEntries<T, ()>>;
 
-/// A lazy iterator producing elements in the set difference (in-order).
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct DifferenceItems<'a, T> {
     a: Peekable<&'a T, SetItems<'a, T>>,
     b: Peekable<&'a T, SetItems<'a, T>>,
 }
 
-/// A lazy iterator producing elements in the set symmetric difference (in-order).
+/// A lazy iterator producing elements in the set difference (in-order).
+#[cfg(not(stage0))]
+pub struct DifferenceItems<'a, T:'a> {
+    a: Peekable<&'a T, SetItems<'a, T>>,
+    b: Peekable<&'a T, SetItems<'a, T>>,
+}
+
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct SymDifferenceItems<'a, T> {
     a: Peekable<&'a T, SetItems<'a, T>>,
     b: Peekable<&'a T, SetItems<'a, T>>,
 }
 
-/// A lazy iterator producing elements in the set intersection (in-order).
+/// A lazy iterator producing elements in the set symmetric difference (in-order).
+#[cfg(not(stage0))]
+pub struct SymDifferenceItems<'a, T:'a> {
+    a: Peekable<&'a T, SetItems<'a, T>>,
+    b: Peekable<&'a T, SetItems<'a, T>>,
+}
+
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct IntersectionItems<'a, T> {
     a: Peekable<&'a T, SetItems<'a, T>>,
     b: Peekable<&'a T, SetItems<'a, T>>,
 }
 
-/// A lazy iterator producing elements in the set union (in-order).
+/// A lazy iterator producing elements in the set intersection (in-order).
+#[cfg(not(stage0))]
+pub struct IntersectionItems<'a, T:'a> {
+    a: Peekable<&'a T, SetItems<'a, T>>,
+    b: Peekable<&'a T, SetItems<'a, T>>,
+}
+
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct UnionItems<'a, T> {
     a: Peekable<&'a T, SetItems<'a, T>>,
     b: Peekable<&'a T, SetItems<'a, T>>,
 }
 
-/// Compare `x` and `y`, but return `short` if x is None and `long` if y is
-/// `None`.
+/// A lazy iterator producing elements in the set union (in-order).
+#[cfg(not(stage0))]
+pub struct UnionItems<'a, T:'a> {
+    a: Peekable<&'a T, SetItems<'a, T>>,
+    b: Peekable<&'a T, SetItems<'a, T>>,
+}
+
+/// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
 fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>,
                         short: Ordering, long: Ordering) -> Ordering {
     match (x, y) {
diff --git a/src/libcollections/trie.rs b/src/libcollections/trie.rs
index 7943c1da2c8..e79ec67cba0 100644
--- a/src/libcollections/trie.rs
+++ b/src/libcollections/trie.rs
@@ -857,7 +857,8 @@ fn remove<T>(count: &mut uint, child: &mut Child<T>, key: uint,
     return ret;
 }
 
-/// A forward iterator over a map.
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
 pub struct Entries<'a, T> {
     stack: [slice::Items<'a, Child<T>>, .. NUM_CHUNKS],
     length: uint,
@@ -865,9 +866,28 @@ pub struct Entries<'a, T> {
     remaining_max: uint
 }
 
+/// A forward iterator over a map.
+#[cfg(not(stage0))]
+pub struct Entries<'a, T:'a> {
+    stack: [slice::Items<'a, Child<T>>, .. NUM_CHUNKS],
+    length: uint,
+    remaining_min: uint,
+    remaining_max: uint
+}
+
+/// Note: stage0-specific version that lacks bound on A.
+#[cfg(stage0)]
+pub struct MutEntries<'a, T> {
+    stack: [slice::MutItems<'a, Child<T>>, .. NUM_CHUNKS],
+    length: uint,
+    remaining_min: uint,
+    remaining_max: uint
+}
+
 /// A forward iterator over the key-value pairs of a map, with the
 /// values being mutable.
-pub struct MutEntries<'a, T> {
+#[cfg(not(stage0))]
+pub struct MutEntries<'a, T:'a> {
     stack: [slice::MutItems<'a, Child<T>>, .. NUM_CHUNKS],
     length: uint,
     remaining_min: uint,
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index d67a01b6dee..f383677ed14 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -1620,9 +1620,13 @@ pub struct MoveItems<T> {
 
 impl<T> Iterator<T> for MoveItems<T> {
     #[inline]
-    fn next(&mut self) -> Option<T> {
+    fn next<'a>(&'a mut self) -> Option<T> {
         unsafe {
-            self.iter.next().map(|x| ptr::read(x))
+            // Unsafely transmute from Items<'static, T> to Items<'a,
+            // T> because otherwise the type checker requires that T
+            // be bounded by 'static.
+            let iter: &mut Items<'a, T> = mem::transmute(&mut self.iter);
+            iter.next().map(|x| ptr::read(x))
         }
     }
 
@@ -1634,9 +1638,13 @@ impl<T> Iterator<T> for MoveItems<T> {
 
 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
     #[inline]
-    fn next_back(&mut self) -> Option<T> {
+    fn next_back<'a>(&'a mut self) -> Option<T> {
         unsafe {
-            self.iter.next_back().map(|x| ptr::read(x))
+            // Unsafely transmute from Items<'static, T> to Items<'a,
+            // T> because otherwise the type checker requires that T
+            // be bounded by 'static.
+            let iter: &mut Items<'a, T> = mem::transmute(&mut self.iter);
+            iter.next_back().map(|x| ptr::read(x))
         }
     }
 }