auto merge of #19958 : alexcrichton/rust/rollup, r=alexcrichton

13 files changed, 170 insertions, 174 deletions

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 2a8d97eed05..0ff29a94f2f 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -20,7 +20,7 @@ use cmp::{max, Eq, Equiv, PartialEq};
 use default::Default;
 use fmt::{mod, Show};
 use hash::{Hash, Hasher, RandomSipHasher};
-use iter::{mod, Iterator, IteratorExt, FromIterator, Extend};
+use iter::{mod, Iterator, IteratorExt, FromIterator, Extend, Map};
 use kinds::Sized;
 use mem::{mod, replace};
 use num::{Int, UnsignedInt};
@@ -297,7 +297,7 @@ pub struct HashMap<K, V, H = RandomSipHasher> {
 
 /// Search for a pre-hashed key.
 fn search_hashed<K, V, M, F>(table: M,
-                             hash: &SafeHash,
+                             hash: SafeHash,
                              mut is_match: F)
                              -> SearchResult<K, V, M> where
     M: Deref<RawTable<K, V>>,
@@ -320,14 +320,9 @@ fn search_hashed<K, V, M, F>(table: M,
         }
 
         // If the hash doesn't match, it can't be this one..
-        if *hash == full.hash() {
-            let matched = {
-                let (k, _) = full.read();
-                is_match(k)
-            };
-
+        if hash == full.hash() {
             // If the key doesn't match, it can't be this one..
-            if matched {
+            if is_match(full.read().0) {
                 return FoundExisting(full);
             }
         }
@@ -353,7 +348,7 @@ fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
     }
 
     // Now we've done all our shifting. Return the value we grabbed earlier.
-    return (retkey, retval);
+    (retkey, retval)
 }
 
 /// Perform robin hood bucket stealing at the given `bucket`. You must
@@ -389,10 +384,11 @@ fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
                     let b = bucket.put(old_hash, old_key, old_val);
                     // Now that it's stolen, just read the value's pointer
                     // right out of the table!
-                    let (_, v) = Bucket::at_index(b.into_table(), starting_index).peek()
-                                                                                 .expect_full()
-                                                                                 .into_mut_refs();
-                    return v;
+                    return Bucket::at_index(b.into_table(), starting_index)
+                               .peek()
+                               .expect_full()
+                               .into_mut_refs()
+                               .1;
                 },
                 table::Full(bucket) => bucket
             };
@@ -441,14 +437,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     fn search_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, q: &Q)
                     -> Option<FullBucketImm<'a, K, V>> {
         let hash = self.make_hash(q);
-        search_hashed(&self.table, &hash, |k| q.equiv(k)).into_option()
+        search_hashed(&self.table, hash, |k| q.equiv(k)).into_option()
     }
 
     #[allow(deprecated)]
     fn search_equiv_mut<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a mut self, q: &Q)
                     -> Option<FullBucketMut<'a, K, V>> {
         let hash = self.make_hash(q);
-        search_hashed(&mut self.table, &hash, |k| q.equiv(k)).into_option()
+        search_hashed(&mut self.table, hash, |k| q.equiv(k)).into_option()
     }
 
     /// Search for a key, yielding the index if it's found in the hashtable.
@@ -458,7 +454,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         where Q: BorrowFrom<K> + Eq + Hash<S>
     {
         let hash = self.make_hash(q);
-        search_hashed(&self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k)))
+        search_hashed(&self.table, hash, |k| q.eq(BorrowFrom::borrow_from(k)))
             .into_option()
     }
 
@@ -466,14 +462,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         where Q: BorrowFrom<K> + Eq + Hash<S>
     {
         let hash = self.make_hash(q);
-        search_hashed(&mut self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k)))
+        search_hashed(&mut self.table, hash, |k| q.eq(BorrowFrom::borrow_from(k)))
             .into_option()
     }
 
     // The caller should ensure that invariants by Robin Hood Hashing hold.
     fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
         let cap = self.table.capacity();
-        let mut buckets = Bucket::new(&mut self.table, &hash);
+        let mut buckets = Bucket::new(&mut self.table, hash);
         let ib = buckets.index();
 
         while buckets.index() != ib + cap {
@@ -762,26 +758,22 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     {
         // Worst case, we'll find one empty bucket among `size + 1` buckets.
         let size = self.table.size();
-        let mut probe = Bucket::new(&mut self.table, &hash);
+        let mut probe = Bucket::new(&mut self.table, hash);
         let ib = probe.index();
 
         loop {
             let mut bucket = match probe.peek() {
                 Empty(bucket) => {
                     // Found a hole!
-                    let bucket = bucket.put(hash, k, v);
-                    let (_, val) = bucket.into_mut_refs();
-                    return val;
-                },
+                    return bucket.put(hash, k, v).into_mut_refs().1;
+                }
                 Full(bucket) => bucket
             };
 
+            // hash matches?
             if bucket.hash() == hash {
-                let found_match = {
-                    let (bucket_k, _) = bucket.read_mut();
-                    k == *bucket_k
-                };
-                if found_match {
+                // key matches?
+                if k == *bucket.read_mut().0 {
                     let (bucket_k, bucket_v) = bucket.into_mut_refs();
                     debug_assert!(k == *bucket_k);
                     // Key already exists. Get its reference.
@@ -811,13 +803,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// Deprecated: use `get` and `BorrowFrom` instead.
     #[deprecated = "use get and BorrowFrom instead"]
     pub fn find_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> {
-        match self.search_equiv(k) {
-            None      => None,
-            Some(bucket) => {
-                let (_, v_ref) = bucket.into_refs();
-                Some(v_ref)
-            }
-        }
+        self.search_equiv(k).map(|bucket| bucket.into_refs().1)
     }
 
     /// Deprecated: use `remove` and `BorrowFrom` instead.
@@ -829,13 +815,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
 
         self.reserve(1);
 
-        match self.search_equiv_mut(k) {
-            Some(bucket) => {
-                let (_k, val) = pop_internal(bucket);
-                Some(val)
-            }
-            _ => None
-        }
+        self.search_equiv_mut(k).map(|bucket| pop_internal(bucket).1)
     }
 
     /// An iterator visiting all keys in arbitrary order.
@@ -859,7 +839,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     pub fn keys(&self) -> Keys<K, V> {
         fn first<A, B>((a, _): (A, B)) -> A { a }
 
-        self.iter().map(first)
+        Keys { inner: self.iter().map(first) }
     }
 
     /// An iterator visiting all values in arbitrary order.
@@ -883,7 +863,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     pub fn values(&self) -> Values<K, V> {
         fn second<A, B>((_, b): (A, B)) -> B { b }
 
-        self.iter().map(second)
+        Values { inner: self.iter().map(second) }
     }
 
     /// An iterator visiting all key-value pairs in arbitrary order.
@@ -1022,11 +1002,8 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
 
         while buckets.index() != cap {
             buckets = match buckets.peek() {
-                Empty(b)  => b.next(),
-                Full(full) => {
-                    let (b, _, _) = full.take();
-                    b.next()
-                }
+                Empty(b)   => b.next(),
+                Full(full) => full.take().0.next(),
             };
         }
     }
@@ -1057,10 +1034,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     pub fn get<Sized? Q>(&self, k: &Q) -> Option<&V>
         where Q: Hash<S> + Eq + BorrowFrom<K>
     {
-        self.search(k).map(|bucket| {
-            let (_, v) = bucket.into_refs();
-            v
-        })
+        self.search(k).map(|bucket| bucket.into_refs().1)
     }
 
     /// Returns true if the map contains a value for the specified key.
@@ -1115,13 +1089,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     pub fn get_mut<Sized? Q>(&mut self, k: &Q) -> Option<&mut V>
         where Q: Hash<S> + Eq + BorrowFrom<K>
     {
-        match self.search_mut(k) {
-            Some(bucket) => {
-                let (_, v) = bucket.into_mut_refs();
-                Some(v)
-            }
-            _ => None
-        }
+        self.search_mut(k).map(|bucket| bucket.into_mut_refs().1)
     }
 
     /// Deprecated: Renamed to `insert`.
@@ -1189,10 +1157,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
             return None
         }
 
-        self.search_mut(k).map(|bucket| {
-            let (_k, val) = pop_internal(bucket);
-            val
-        })
+        self.search_mut(k).map(|bucket| pop_internal(bucket).1)
     }
 }
 
@@ -1200,7 +1165,7 @@ fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHas
         -> Entry<'a, K, V> {
     // Worst case, we'll find one empty bucket among `size + 1` buckets.
     let size = table.size();
-    let mut probe = Bucket::new(table, &hash);
+    let mut probe = Bucket::new(table, hash);
     let ib = probe.index();
 
     loop {
@@ -1216,13 +1181,10 @@ fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHas
             Full(bucket) => bucket
         };
 
+        // hash matches?
         if bucket.hash() == hash {
-            let is_eq = {
-                let (bucket_k, _) = bucket.read();
-                k == *bucket_k
-            };
-
-            if is_eq {
+            // key matches?
+            if k == *bucket.read().0 {
                 return Occupied(OccupiedEntry{
                     elem: bucket,
                 });
@@ -1288,7 +1250,9 @@ impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H>
     }
 }
 
+#[stable]
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
+    #[stable]
     fn default() -> HashMap<K, V, H> {
         HashMap::with_hasher(Default::default())
     }
@@ -1308,10 +1272,7 @@ impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> IndexMut<Q, V> for HashMap<K
 {
     #[inline]
     fn index_mut<'a>(&'a mut self, index: &Q) -> &'a mut V {
-        match self.get_mut(index) {
-            Some(v) => v,
-            None => panic!("no entry found for key")
-        }
+        self.get_mut(index).expect("no entry found for key")
     }
 }
 
@@ -1335,6 +1296,16 @@ pub struct MoveEntries<K, V> {
     >
 }
 
+/// HashMap keys iterator
+pub struct Keys<'a, K: 'a, V: 'a> {
+    inner: Map<(&'a K, &'a V), &'a K, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
+}
+
+/// HashMap values iterator
+pub struct Values<'a, K: 'a, V: 'a> {
+    inner: Map<(&'a K, &'a V), &'a V, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
+}
+
 /// A view into a single occupied location in a HashMap
 pub struct OccupiedEntry<'a, K:'a, V:'a> {
     elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
@@ -1365,56 +1336,45 @@ enum VacantEntryState<K, V, M> {
 }
 
 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
-    #[inline]
-    fn next(&mut self) -> Option<(&'a K, &'a V)> {
-        self.inner.next()
-    }
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        self.inner.size_hint()
-    }
+    #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for MutEntries<'a, K, V> {
-    #[inline]
-    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
-        self.inner.next()
-    }
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        self.inner.size_hint()
-    }
+    #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
 impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
-    #[inline]
-    fn next(&mut self) -> Option<(K, V)> {
-        self.inner.next()
-    }
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) {
-        self.inner.size_hint()
-    }
+    #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
+}
+
+impl<'a, K, V> Iterator<&'a K> for Keys<'a, K, V> {
+    #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
+}
+
+impl<'a, K, V> Iterator<&'a V> for Values<'a, K, V> {
+    #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next() }
+    #[inline] fn size_hint(&self) -> (uint, Option<uint>) { self.inner.size_hint() }
 }
 
 impl<'a, K, V> OccupiedEntry<'a, K, V> {
     /// Gets a reference to the value in the entry
     pub fn get(&self) -> &V {
-        let (_, v) = self.elem.read();
-        v
+        self.elem.read().1
     }
 
     /// Gets a mutable reference to the value in the entry
     pub fn get_mut(&mut self) -> &mut V {
-        let (_, v) = self.elem.read_mut();
-        v
+        self.elem.read_mut().1
     }
 
     /// Converts the OccupiedEntry into a mutable reference to the value in the entry
     /// with a lifetime bound to the map itself
     pub fn into_mut(self) -> &'a mut V {
-        let (_, v) = self.elem.into_mut_refs();
-        v
+        self.elem.into_mut_refs().1
     }
 
     /// Sets the value of the entry, and returns the entry's old value
@@ -1426,8 +1386,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> {
 
     /// Takes the value out of the entry, and returns it
     pub fn take(self) -> V {
-        let (_, v) = pop_internal(self.elem);
-        v
+        pop_internal(self.elem).1
     }
 }
 
@@ -1440,25 +1399,15 @@ impl<'a, K, V> VacantEntry<'a, K, V> {
                 robin_hood(bucket, ib, self.hash, self.key, value)
             }
             NoElem(bucket) => {
-                let full = bucket.put(self.hash, self.key, value);
-                let (_, v) = full.into_mut_refs();
-                v
+                bucket.put(self.hash, self.key, value).into_mut_refs().1
             }
         }
     }
 }
 
-/// HashMap keys iterator
-pub type Keys<'a, K, V> =
-    iter::Map<(&'a K, &'a V), &'a K, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>;
-
-/// HashMap values iterator
-pub type Values<'a, K, V> =
-    iter::Map<(&'a K, &'a V), &'a V, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>;
-
 impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
     fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
-        let (lower, _) = iter.size_hint();
+        let lower = iter.size_hint().0;
         let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
         map.extend(iter);
         map
diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs
index c71f0d5b935..67c0f887832 100644
--- a/src/libstd/collections/hash/set.rs
+++ b/src/libstd/collections/hash/set.rs
@@ -17,12 +17,11 @@ use default::Default;
 use fmt::Show;
 use fmt;
 use hash::{Hash, Hasher, RandomSipHasher};
-use iter::{Iterator, IteratorExt, FromIterator, FilterMap, Chain, Repeat, Zip, Extend, repeat};
-use iter;
+use iter::{Iterator, IteratorExt, FromIterator, Map, FilterMap, Chain, Repeat, Zip, Extend, repeat};
 use option::Option::{Some, None, mod};
 use result::Result::{Ok, Err};
 
-use super::map::{HashMap, Entries, MoveEntries, INITIAL_CAPACITY};
+use super::map::{HashMap, MoveEntries, Keys, INITIAL_CAPACITY};
 
 // FIXME(conventions): implement BitOr, BitAnd, BitXor, and Sub
 
@@ -252,7 +251,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn iter<'a>(&'a self) -> SetItems<'a, T> {
-        self.map.keys()
+        SetItems { iter: self.map.keys() }
     }
 
     /// Creates a consuming iterator, that is, one that moves each value out
@@ -279,7 +278,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     pub fn into_iter(self) -> SetMoveItems<T> {
         fn first<A, B>((a, _): (A, B)) -> A { a }
 
-        self.map.into_iter().map(first)
+        SetMoveItems { iter: self.map.into_iter().map(first) }
     }
 
     /// Visit the values representing the difference.
@@ -312,7 +311,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
             if !other.contains(elt) { Some(elt) } else { None }
         }
 
-        repeat(other).zip(self.iter()).filter_map(filter)
+        SetAlgebraItems { iter: repeat(other).zip(self.iter()).filter_map(filter) }
     }
 
     /// Visit the values representing the symmetric difference.
@@ -337,8 +336,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, H>)
-        -> Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>> {
-        self.difference(other).chain(other.difference(self))
+        -> SymDifferenceItems<'a, T, H> {
+        SymDifferenceItems { iter: self.difference(other).chain(other.difference(self)) }
     }
 
     /// Visit the values representing the intersection.
@@ -366,7 +365,7 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
             if other.contains(elt) { Some(elt) } else { None }
         }
 
-        repeat(other).zip(self.iter()).filter_map(filter)
+        SetAlgebraItems { iter: repeat(other).zip(self.iter()).filter_map(filter) }
     }
 
     /// Visit the values representing the union.
@@ -387,9 +386,8 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// assert_eq!(diff, [1i, 2, 3, 4].iter().map(|&x| x).collect());
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
-    pub fn union<'a>(&'a self, other: &'a HashSet<T, H>)
-        -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> {
-        self.iter().chain(other.difference(self))
+    pub fn union<'a>(&'a self, other: &'a HashSet<T, H>) -> UnionItems<'a, T, H> {
+        UnionItems { iter: self.iter().chain(other.difference(self)) }
     }
 
     /// Return the number of elements in the set
@@ -595,7 +593,7 @@ impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
 
 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
     fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> {
-        let (lower, _) = iter.size_hint();
+        let lower = iter.size_hint().0;
         let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
         set.extend(iter);
         set
@@ -610,28 +608,70 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extend<T> for HashSet<T, H> {
     }
 }
 
+#[stable]
 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
+    #[stable]
     fn default() -> HashSet<T, H> {
         HashSet::with_hasher(Default::default())
     }
 }
 
 /// HashSet iterator
-pub type SetItems<'a, K> =
-    iter::Map<(&'a K, &'a ()), &'a K, Entries<'a, K, ()>, fn((&'a K, &'a ())) -> &'a K>;
+pub struct SetItems<'a, K: 'a> {
+    iter: Keys<'a, K, ()>
+}
 
 /// HashSet move iterator
-pub type SetMoveItems<K> = iter::Map<(K, ()), K, MoveEntries<K, ()>, fn((K, ())) -> K>;
+pub struct SetMoveItems<K> {
+    iter: Map<(K, ()), K, MoveEntries<K, ()>, fn((K, ())) -> K>
+}
 
 // `Repeat` is used to feed the filter closure an explicit capture
 // of a reference to the other set
-/// Set operations iterator
-pub type SetAlgebraItems<'a, T, H> = FilterMap<
-    (&'a HashSet<T, H>, &'a T),
-    &'a T,
-    Zip<Repeat<&'a HashSet<T, H>>, SetItems<'a, T>>,
-    for<'b> fn((&HashSet<T, H>, &'b T)) -> Option<&'b T>,
->;
+/// Set operations iterator, used directly for intersection and difference
+pub struct SetAlgebraItems<'a, T: 'a, H: 'a> {
+    iter: FilterMap<
+        (&'a HashSet<T, H>, &'a T),
+        &'a T,
+        Zip<Repeat<&'a HashSet<T, H>>, SetItems<'a, T>>,
+        for<'b> fn((&HashSet<T, H>, &'b T)) -> Option<&'b T>,
+    >
+}
+
+/// Symmetric difference iterator.
+pub struct SymDifferenceItems<'a, T: 'a, H: 'a> {
+    iter: Chain<SetAlgebraItems<'a, T, H>, SetAlgebraItems<'a, T, H>>
+}
+
+/// Set union iterator.
+pub struct UnionItems<'a, T: 'a, H: 'a> {
+    iter: Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>>
+}
+
+impl<'a, K> Iterator<&'a K> for SetItems<'a, K> {
+    fn next(&mut self) -> Option<&'a K> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<K> Iterator<K> for SetMoveItems<K> {
+    fn next(&mut self) -> Option<K> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<'a, T, H> Iterator<&'a T> for SetAlgebraItems<'a, T, H> {
+    fn next(&mut self) -> Option<&'a T> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<'a, T, H> Iterator<&'a T> for SymDifferenceItems<'a, T, H> {
+    fn next(&mut self) -> Option<&'a T> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<'a, T, H> Iterator<&'a T> for UnionItems<'a, T, H> {
+    fn next(&mut self) -> Option<&'a T> { self.iter.next() }
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
 
 #[cfg(test)]
 mod test_set {
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index ef4cabedc47..da06387e9a5 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -124,7 +124,7 @@ struct GapThenFull<K, V, M> {
 
 /// A hash that is not zero, since we use a hash of zero to represent empty
 /// buckets.
-#[deriving(PartialEq)]
+#[deriving(PartialEq, Copy)]
 pub struct SafeHash {
     hash: u64,
 }
@@ -211,7 +211,7 @@ impl<K, V, M> Bucket<K, V, M> {
 }
 
 impl<K, V, M: Deref<RawTable<K, V>>> Bucket<K, V, M> {
-    pub fn new(table: M, hash: &SafeHash) -> Bucket<K, V, M> {
+    pub fn new(table: M, hash: SafeHash) -> Bucket<K, V, M> {
         Bucket::at_index(table, hash.inspect() as uint)
     }
 
diff --git a/src/libstd/comm/mod.rs b/src/libstd/comm/mod.rs
index 0a5b3e5771b..72ddbe19f54 100644
--- a/src/libstd/comm/mod.rs
+++ b/src/libstd/comm/mod.rs
@@ -81,7 +81,7 @@
 //! Shared usage:
 //!
 //! ```
-//! // Create a shared channel which can be sent along from many tasks
+//! // Create a shared channel that can be sent along from many tasks
 //! // where tx is the sending half (tx for transmission), and rx is the receiving
 //! // half (rx for receiving).
 //! let (tx, rx) = channel();
@@ -176,7 +176,7 @@
 // The choice of implementation of all channels is to be built on lock-free data
 // structures. The channels themselves are then consequently also lock-free data
 // structures. As always with lock-free code, this is a very "here be dragons"
-// territory, especially because I'm unaware of any academic papers which have
+// territory, especially because I'm unaware of any academic papers that have
 // gone into great length about channels of these flavors.
 //
 // ## Flavors of channels
@@ -190,7 +190,7 @@
 //              They contain as few atomics as possible and involve one and
 //              exactly one allocation.
 // * Streams - these channels are optimized for the non-shared use case. They
-//             use a different concurrent queue which is more tailored for this
+//             use a different concurrent queue that is more tailored for this
 //             use case. The initial allocation of this flavor of channel is not
 //             optimized.
 // * Shared - this is the most general form of channel that this module offers,
@@ -205,7 +205,7 @@
 // shared and concurrent queue holding all of the actual data.
 //
 // With two flavors of channels, two flavors of queues are also used. We have
-// chosen to use queues from a well-known author which are abbreviated as SPSC
+// chosen to use queues from a well-known author that are abbreviated as SPSC
 // and MPSC (single producer, single consumer and multiple producer, single
 // consumer). SPSC queues are used for streams while MPSC queues are used for
 // shared channels.
@@ -309,7 +309,7 @@
 //
 // Sadly this current implementation requires multiple allocations, so I have
 // seen the throughput of select() be much worse than it should be. I do not
-// believe that there is anything fundamental which needs to change about these
+// believe that there is anything fundamental that needs to change about these
 // channels, however, in order to support a more efficient select().
 //
 // # Conclusion
@@ -910,7 +910,7 @@ impl<T: Send> Receiver<T> {
         }
     }
 
-    /// Returns an iterator which will block waiting for messages, but never
+    /// Returns an iterator that will block waiting for messages, but never
     /// `panic!`. It will return `None` when the channel has hung up.
     #[unstable]
     pub fn iter<'a>(&'a self) -> Messages<'a, T> {
diff --git a/src/libstd/hash.rs b/src/libstd/hash.rs
index a63abec96d5..52e3c718b2d 100644
--- a/src/libstd/hash.rs
+++ b/src/libstd/hash.rs
@@ -95,7 +95,9 @@ impl Hasher<sip::SipState> for RandomSipHasher {
     }
 }
 
+#[stable]
 impl Default for RandomSipHasher {
+    #[stable]
     #[inline]
     fn default() -> RandomSipHasher {
         RandomSipHasher::new()
diff --git a/src/libstd/io/fs.rs b/src/libstd/io/fs.rs
index 40c28877548..f8df7e9b1f3 100644
--- a/src/libstd/io/fs.rs
+++ b/src/libstd/io/fs.rs
@@ -200,7 +200,7 @@ impl File {
              .update_desc("couldn't create file")
     }
 
-    /// Returns the original path which was used to open this file.
+    /// Returns the original path that was used to open this file.
     pub fn path<'a>(&'a self) -> &'a Path {
         &self.path
     }
@@ -215,7 +215,7 @@ impl File {
     }
 
     /// This function is similar to `fsync`, except that it may not synchronize
-    /// file metadata to the filesystem. This is intended for use case which
+    /// file metadata to the filesystem. This is intended for use cases that
     /// must synchronize content, but don't need the metadata on disk. The goal
     /// of this method is to reduce disk operations.
     pub fn datasync(&mut self) -> IoResult<()> {
@@ -456,7 +456,7 @@ pub fn symlink(src: &Path, dst: &Path) -> IoResult<()> {
 /// # Error
 ///
 /// This function will return an error on failure. Failure conditions include
-/// reading a file that does not exist or reading a file which is not a symlink.
+/// reading a file that does not exist or reading a file that is not a symlink.
 pub fn readlink(path: &Path) -> IoResult<Path> {
     fs_imp::readlink(path)
            .update_err("couldn't resolve symlink for path", |e|
@@ -546,7 +546,7 @@ pub fn readdir(path: &Path) -> IoResult<Vec<Path>> {
                        |e| format!("{}; path={}", e, path.display()))
 }
 
-/// Returns an iterator which will recursively walk the directory structure
+/// Returns an iterator that will recursively walk the directory structure
 /// rooted at `path`. The path given will not be iterated over, and this will
 /// perform iteration in some top-down order.  The contents of unreadable
 /// subdirectories are ignored.
@@ -557,7 +557,7 @@ pub fn walk_dir(path: &Path) -> IoResult<Directories> {
     })
 }
 
-/// An iterator which walks over a directory
+/// An iterator that walks over a directory
 pub struct Directories {
     stack: Vec<Path>,
 }
diff --git a/src/libstd/io/mod.rs b/src/libstd/io/mod.rs
index 6fc9d0bd172..6a6d467e86c 100644
--- a/src/libstd/io/mod.rs
+++ b/src/libstd/io/mod.rs
@@ -1911,7 +1911,9 @@ bitflags! {
 }
 
 
+#[stable]
 impl Default for FilePermission {
+    #[stable]
     #[inline]
     fn default() -> FilePermission { FilePermission::empty() }
 }
diff --git a/src/libstd/io/net/udp.rs b/src/libstd/io/net/udp.rs
index 78951b8dae2..ce7e5ca5f5e 100644
--- a/src/libstd/io/net/udp.rs
+++ b/src/libstd/io/net/udp.rs
@@ -557,11 +557,12 @@ mod test {
         let addr1 = next_test_ip4();
         let addr2 = next_test_ip4();
         let mut a = UdpSocket::bind(addr1).unwrap();
+        let a2 = UdpSocket::bind(addr2).unwrap();
 
         let (tx, rx) = channel();
         let (tx2, rx2) = channel();
         spawn(move|| {
-            let mut a = UdpSocket::bind(addr2).unwrap();
+            let mut a = a2;
             assert_eq!(a.recv_from(&mut [0]), Ok((1, addr1)));
             assert_eq!(a.send_to(&[0], addr1), Ok(()));
             rx.recv();
diff --git a/src/libstd/io/stdio.rs b/src/libstd/io/stdio.rs
index c180476efb8..844814fbfdd 100644
--- a/src/libstd/io/stdio.rs
+++ b/src/libstd/io/stdio.rs
@@ -41,6 +41,7 @@ use option::Option;
 use option::Option::{Some, None};
 use ops::{Deref, DerefMut, FnOnce};
 use result::Result::{Ok, Err};
+use rt;
 use rustrt;
 use rustrt::local::Local;
 use rustrt::task::Task;
@@ -224,6 +225,12 @@ pub fn stdin() -> StdinReader {
                 inner: Arc::new(Mutex::new(stdin))
             };
             STDIN = mem::transmute(box stdin);
+
+            // Make sure to free it at exit
+            rt::at_exit(|| {
+                mem::transmute::<_, Box<StdinReader>>(STDIN);
+                STDIN = 0 as *const _;
+            });
         });
 
         (*STDIN).clone()
diff --git a/src/libstd/rand/os.rs b/src/libstd/rand/os.rs
index bbe8edc0f00..6bccef07131 100644
--- a/src/libstd/rand/os.rs
+++ b/src/libstd/rand/os.rs
@@ -117,7 +117,8 @@ mod imp {
     ///   `/dev/urandom`, or from `getrandom(2)` system call if available.
     /// - Windows: calls `CryptGenRandom`, using the default cryptographic
     ///   service provider with the `PROV_RSA_FULL` type.
-    /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed
+    /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed.
+    ///
     /// This does not block.
     pub struct OsRng {
         inner: OsRngInner,
@@ -184,10 +185,13 @@ mod imp {
     ///   `/dev/urandom`, or from `getrandom(2)` system call if available.
     /// - Windows: calls `CryptGenRandom`, using the default cryptographic
     ///   service provider with the `PROV_RSA_FULL` type.
-    /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed
+    /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed.
+    ///
     /// This does not block.
+    #[allow(missing_copy_implementations)]
     pub struct OsRng {
-        marker: marker::NoCopy
+        // dummy field to ensure that this struct cannot be constructed outside of this module
+        _dummy: (),
     }
 
     #[repr(C)]
@@ -205,7 +209,7 @@ mod imp {
     impl OsRng {
         /// Create a new `OsRng`.
         pub fn new() -> IoResult<OsRng> {
-            Ok(OsRng {marker: marker::NoCopy} )
+            Ok(OsRng { _dummy: () })
         }
     }
 
@@ -254,7 +258,8 @@ mod imp {
     ///   `/dev/urandom`, or from `getrandom(2)` system call if available.
     /// - Windows: calls `CryptGenRandom`, using the default cryptographic
     ///   service provider with the `PROV_RSA_FULL` type.
-    /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed
+    /// - iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed.
+    ///
     /// This does not block.
     pub struct OsRng {
         hcryptprov: HCRYPTPROV
diff --git a/src/libstd/sys/common/thread_local.rs b/src/libstd/sys/common/thread_local.rs
index 3eb0e3f46cb..cf56a71d67a 100644
--- a/src/libstd/sys/common/thread_local.rs
+++ b/src/libstd/sys/common/thread_local.rs
@@ -58,7 +58,6 @@
 
 use prelude::*;
 
-use kinds::marker;
 use rustrt::exclusive::Exclusive;
 use sync::atomic::{mod, AtomicUint};
 use sync::{Once, ONCE_INIT};
@@ -100,7 +99,6 @@ pub struct StaticKey {
 /// Inner contents of `StaticKey`, created by the `INIT_INNER` constant.
 pub struct StaticKeyInner {
     key: AtomicUint,
-    nc: marker::NoCopy,
 }
 
 /// A type for a safely managed OS-based TLS slot.
@@ -141,7 +139,6 @@ pub const INIT: StaticKey = StaticKey {
 /// This value allows specific configuration of the destructor for a TLS key.
 pub const INIT_INNER: StaticKeyInner = StaticKeyInner {
     key: atomic::INIT_ATOMIC_UINT,
-    nc: marker::NoCopy,
 };
 
 static INIT_KEYS: Once = ONCE_INIT;
diff --git a/src/libstd/task.rs b/src/libstd/task.rs
index 562afd33e2f..324b594209a 100644
--- a/src/libstd/task.rs
+++ b/src/libstd/task.rs
@@ -49,7 +49,7 @@ use boxed::Box;
 use comm::channel;
 use core::ops::FnOnce;
 use io::{Writer, stdio};
-use kinds::{Send, marker};
+use kinds::Send;
 use option::Option;
 use option::Option::{None, Some};
 use result::Result;
@@ -83,7 +83,6 @@ pub struct TaskBuilder {
     stderr: Option<Box<Writer + Send>>,
     // Optionally wrap the eventual task body
     gen_body: Option<Thunk<Thunk, Thunk>>,
-    nocopy: marker::NoCopy,
 }
 
 impl TaskBuilder {
@@ -96,7 +95,6 @@ impl TaskBuilder {
             stdout: None,
             stderr: None,
             gen_body: None,
-            nocopy: marker::NoCopy,
         }
     }
 }
@@ -137,7 +135,7 @@ impl TaskBuilder {
         on_exit: Option<Thunk<task::Result>>)
     {
         let TaskBuilder {
-            name, stack_size, stdout, stderr, mut gen_body, nocopy: _
+            name, stack_size, stdout, stderr, mut gen_body
         } = self;
 
         let f = match gen_body.take() {
diff --git a/src/libstd/thread_local/mod.rs b/src/libstd/thread_local/mod.rs
index 2d5766c2393..76fb703514b 100644
--- a/src/libstd/thread_local/mod.rs
+++ b/src/libstd/thread_local/mod.rs
@@ -185,7 +185,6 @@ macro_rules! __thread_local_inner(
                 inner: ::std::cell::UnsafeCell { value: $init },
                 dtor_registered: ::std::cell::UnsafeCell { value: false },
                 dtor_running: ::std::cell::UnsafeCell { value: false },
-                marker: ::std::kinds::marker::NoCopy,
             }
         };
 
@@ -247,7 +246,6 @@ mod imp {
 
     use cell::UnsafeCell;
     use intrinsics;
-    use kinds::marker;
     use ptr;
 
     #[doc(hidden)]
@@ -264,9 +262,6 @@ mod imp {
         // these variables are thread-local, not global.
         pub dtor_registered: UnsafeCell<bool>, // should be Cell
         pub dtor_running: UnsafeCell<bool>, // should be Cell
-
-        // These shouldn't be copied around.
-        pub marker: marker::NoCopy,
     }
 
     #[doc(hidden)]