auto merge of #8490 : huonw/rust/fromiterator-extendable, r=catamorphism

If they are on the trait then it is extremely annoying to use them as
generic parameters to a function, e.g. with the iterator param on the trait
itself, if one was to pass an Extendable<int> to a function that filled it
either from a Range or a Map<VecIterator>, one needs to write something
like:

    fn foo<E: Extendable<int, Range<int>> +
              Extendable<int, Map<&'self int, int, VecIterator<int>>>
          (e: &mut E, ...) { ... }

since using a generic, i.e. `foo<E: Extendable<int, I>, I: Iterator<int>>`
means that `foo` takes 2 type parameters, and the caller has to specify them
(which doesn't work anyway, as they'll mismatch with the iterators used in
`foo` itself).

This patch changes it to:

    fn foo<E: Extendable<int>>(e: &mut E, ...) { ... }

13 files changed, 71 insertions, 55 deletions

diff --git a/doc/po/tutorial-container.md.pot b/doc/po/tutorial-container.md.pot
index 7f4f896076f..a93d5801dcc 100644
--- a/doc/po/tutorial-container.md.pot
+++ b/doc/po/tutorial-container.md.pot
@@ -481,8 +481,8 @@ msgstr ""
 #, no-wrap
 msgid ""
 "~~~\n"
-"impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {\n"
-"    pub fn from_iterator(iterator: &mut T) -> ~[A] {\n"
+"impl<A> FromIterator<A> for ~[A] {\n"
+"    pub fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> ~[A] {\n"
 "        let (lower, _) = iterator.size_hint();\n"
 "        let mut xs = with_capacity(lower);\n"
 "        for x in iterator {\n"
diff --git a/doc/tutorial-container.md b/doc/tutorial-container.md
index 19cd58bd3b4..8d0e8e200d0 100644
--- a/doc/tutorial-container.md
+++ b/doc/tutorial-container.md
@@ -224,8 +224,8 @@ implementing the `FromIterator` trait. For example, the implementation for
 vectors is as follows:
 
 ~~~
-impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {
-    pub fn from_iterator(iterator: &mut T) -> ~[A] {
+impl<A> FromIterator<A> for ~[A] {
+    pub fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> ~[A] {
         let (lower, _) = iterator.size_hint();
         let mut xs = with_capacity(lower);
         for x in iterator {
diff --git a/src/libextra/dlist.rs b/src/libextra/dlist.rs
index 788ed726d0f..076e86dd5b0 100644
--- a/src/libextra/dlist.rs
+++ b/src/libextra/dlist.rs
@@ -573,16 +573,16 @@ impl<A> DoubleEndedIterator<A> for MoveIterator<A> {
     fn next_back(&mut self) -> Option<A> { self.list.pop_back() }
 }
 
-impl<A, T: Iterator<A>> FromIterator<A, T> for DList<A> {
-    fn from_iterator(iterator: &mut T) -> DList<A> {
+impl<A> FromIterator<A> for DList<A> {
+    fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> DList<A> {
         let mut ret = DList::new();
         ret.extend(iterator);
         ret
     }
 }
 
-impl<A, T: Iterator<A>> Extendable<A, T> for DList<A> {
-    fn extend(&mut self, iterator: &mut T) {
+impl<A> Extendable<A> for DList<A> {
+    fn extend<T: Iterator<A>>(&mut self, iterator: &mut T) {
         for elt in *iterator { self.push_back(elt); }
     }
 }
@@ -1163,4 +1163,3 @@ mod tests {
         }
     }
 }
-
diff --git a/src/libextra/priority_queue.rs b/src/libextra/priority_queue.rs
index 4b94219b30d..4f0fed5fccf 100644
--- a/src/libextra/priority_queue.rs
+++ b/src/libextra/priority_queue.rs
@@ -190,8 +190,8 @@ impl<'self, T> Iterator<&'self T> for PriorityQueueIterator<'self, T> {
     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 }
 
-impl<T: Ord, Iter: Iterator<T>> FromIterator<T, Iter> for PriorityQueue<T> {
-    fn from_iterator(iter: &mut Iter) -> PriorityQueue<T> {
+impl<T: Ord> FromIterator<T> for PriorityQueue<T> {
+    fn from_iterator<Iter: Iterator<T>>(iter: &mut Iter) -> PriorityQueue<T> {
         let mut q = PriorityQueue::new();
         q.extend(iter);
 
@@ -199,8 +199,8 @@ impl<T: Ord, Iter: Iterator<T>> FromIterator<T, Iter> for PriorityQueue<T> {
     }
 }
 
-impl<T: Ord, Iter: Iterator<T>> Extendable<T, Iter> for PriorityQueue<T> {
-    fn extend(&mut self, iter: &mut Iter) {
+impl<T: Ord> Extendable<T> for PriorityQueue<T> {
+    fn extend<Iter: Iterator<T>>(&mut self, iter: &mut Iter) {
         let (lower, _) = iter.size_hint();
 
         let len = self.capacity();
diff --git a/src/libextra/ringbuf.rs b/src/libextra/ringbuf.rs
index bb9ac74bc77..a38cb580c50 100644
--- a/src/libextra/ringbuf.rs
+++ b/src/libextra/ringbuf.rs
@@ -322,8 +322,8 @@ impl<A: Eq> Eq for RingBuf<A> {
     }
 }
 
-impl<A, T: Iterator<A>> FromIterator<A, T> for RingBuf<A> {
-    fn from_iterator(iterator: &mut T) -> RingBuf<A> {
+impl<A> FromIterator<A> for RingBuf<A> {
+    fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> RingBuf<A> {
         let (lower, _) = iterator.size_hint();
         let mut deq = RingBuf::with_capacity(lower);
         deq.extend(iterator);
@@ -331,8 +331,8 @@ impl<A, T: Iterator<A>> FromIterator<A, T> for RingBuf<A> {
     }
 }
 
-impl<A, T: Iterator<A>> Extendable<A, T> for RingBuf<A> {
-    fn extend(&mut self, iterator: &mut T) {
+impl<A> Extendable<A> for RingBuf<A> {
+    fn extend<T: Iterator<A>>(&mut self, iterator: &mut T) {
         for elt in *iterator {
             self.push_back(elt);
         }
diff --git a/src/libextra/treemap.rs b/src/libextra/treemap.rs
index 486a7dab5c1..118754ec028 100644
--- a/src/libextra/treemap.rs
+++ b/src/libextra/treemap.rs
@@ -835,34 +835,34 @@ fn remove<K: TotalOrd, V>(node: &mut Option<~TreeNode<K, V>>,
     };
 }
 
-impl<K: TotalOrd, V, T: Iterator<(K, V)>> FromIterator<(K, V), T> for TreeMap<K, V> {
-    fn from_iterator(iter: &mut T) -> TreeMap<K, V> {
+impl<K: TotalOrd, V> FromIterator<(K, V)> for TreeMap<K, V> {
+    fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> TreeMap<K, V> {
         let mut map = TreeMap::new();
         map.extend(iter);
         map
     }
 }
 
-impl<K: TotalOrd, V, T: Iterator<(K, V)>> Extendable<(K, V), T> for TreeMap<K, V> {
+impl<K: TotalOrd, V> Extendable<(K, V)> for TreeMap<K, V> {
     #[inline]
-    fn extend(&mut self, iter: &mut T) {
+    fn extend<T: Iterator<(K, V)>>(&mut self, iter: &mut T) {
         for (k, v) in *iter {
             self.insert(k, v);
         }
     }
 }
 
-impl<T: TotalOrd, Iter: Iterator<T>> FromIterator<T, Iter> for TreeSet<T> {
-    fn from_iterator(iter: &mut Iter) -> TreeSet<T> {
+impl<T: TotalOrd> FromIterator<T> for TreeSet<T> {
+    fn from_iterator<Iter: Iterator<T>>(iter: &mut Iter) -> TreeSet<T> {
         let mut set = TreeSet::new();
         set.extend(iter);
         set
     }
 }
 
-impl<T: TotalOrd, Iter: Iterator<T>> Extendable<T, Iter> for TreeSet<T> {
+impl<T: TotalOrd> Extendable<T> for TreeSet<T> {
     #[inline]
-    fn extend(&mut self, iter: &mut Iter) {
+    fn extend<Iter: Iterator<T>>(&mut self, iter: &mut Iter) {
         for elem in *iter {
             self.insert(elem);
         }
diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index 37f45142a11..9719460bbd3 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -879,7 +879,9 @@ pub fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
 
     let check_move: &fn(@pat, Option<@pat>) = |p, sub| {
         // check legality of moving out of the enum
-        if sub.is_some() {
+
+        // x @ Foo(*) is legal, but x @ Foo(y) isn't.
+        if sub.map_move_default(false, |p| pat_contains_bindings(def_map, p)) {
             tcx.sess.span_err(
                 p.span,
                 "cannot bind by-move with sub-bindings");
diff --git a/src/librustc/middle/pat_util.rs b/src/librustc/middle/pat_util.rs
index 9bf14697d9a..a67a488ef30 100644
--- a/src/librustc/middle/pat_util.rs
+++ b/src/librustc/middle/pat_util.rs
@@ -88,3 +88,18 @@ pub fn pat_binding_ids(dm: resolve::DefMap, pat: @pat) -> ~[NodeId] {
     pat_bindings(dm, pat, |_bm, b_id, _sp, _pt| found.push(b_id) );
     return found;
 }
+
+/// Checks if the pattern contains any patterns that bind something to
+/// an ident, e.g. `foo`, or `Foo(foo)` or `foo @ Bar(*)`.
+pub fn pat_contains_bindings(dm: resolve::DefMap, pat: @pat) -> bool {
+    let mut contains_bindings = false;
+    do walk_pat(pat) |p| {
+        if pat_is_binding(dm, p) {
+            contains_bindings = true;
+            false // there's at least one binding, can short circuit now.
+        } else {
+            true
+        }
+    };
+    contains_bindings
+}
diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs
index 201d4692694..50e59cf438d 100644
--- a/src/libstd/hashmap.rs
+++ b/src/libstd/hashmap.rs
@@ -605,8 +605,8 @@ impl<K> Iterator<K> for HashSetMoveIterator<K> {
     }
 }
 
-impl<K: Eq + Hash, V, T: Iterator<(K, V)>> FromIterator<(K, V), T> for HashMap<K, V> {
-    fn from_iterator(iter: &mut T) -> HashMap<K, V> {
+impl<K: Eq + Hash, V> FromIterator<(K, V)> for HashMap<K, V> {
+    fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> HashMap<K, V> {
         let (lower, _) = iter.size_hint();
         let mut map = HashMap::with_capacity(lower);
         map.extend(iter);
@@ -614,8 +614,8 @@ impl<K: Eq + Hash, V, T: Iterator<(K, V)>> FromIterator<(K, V), T> for HashMap<K
     }
 }
 
-impl<K: Eq + Hash, V, T: Iterator<(K, V)>> Extendable<(K, V), T> for HashMap<K, V> {
-    fn extend(&mut self, iter: &mut T) {
+impl<K: Eq + Hash, V> Extendable<(K, V)> for HashMap<K, V> {
+    fn extend<T: Iterator<(K, V)>>(&mut self, iter: &mut T) {
         for (k, v) in *iter {
             self.insert(k, v);
         }
@@ -753,8 +753,8 @@ impl<T:Hash + Eq + Clone> Clone for HashSet<T> {
     }
 }
 
-impl<K: Eq + Hash, T: Iterator<K>> FromIterator<K, T> for HashSet<K> {
-    fn from_iterator(iter: &mut T) -> HashSet<K> {
+impl<K: Eq + Hash> FromIterator<K> for HashSet<K> {
+    fn from_iterator<T: Iterator<K>>(iter: &mut T) -> HashSet<K> {
         let (lower, _) = iter.size_hint();
         let mut set = HashSet::with_capacity(lower);
         set.extend(iter);
@@ -762,8 +762,8 @@ impl<K: Eq + Hash, T: Iterator<K>> FromIterator<K, T> for HashSet<K> {
     }
 }
 
-impl<K: Eq + Hash, T: Iterator<K>> Extendable<K, T> for HashSet<K> {
-    fn extend(&mut self, iter: &mut T) {
+impl<K: Eq + Hash> Extendable<K> for HashSet<K> {
+    fn extend<T: Iterator<K>>(&mut self, iter: &mut T) {
         for k in *iter {
             self.insert(k);
         }
diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index bd89c271a36..1a5e364542b 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -26,15 +26,15 @@ use clone::Clone;
 use uint;
 
 /// Conversion from an `Iterator`
-pub trait FromIterator<A, T: Iterator<A>> {
+pub trait FromIterator<A> {
     /// Build a container with elements from an external iterator.
-    fn from_iterator(iterator: &mut T) -> Self;
+    fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> Self;
 }
 
 /// A type growable from an `Iterator` implementation
-pub trait Extendable<A, T: Iterator<A>>: FromIterator<A, T> {
+pub trait Extendable<A>: FromIterator<A> {
     /// Extend a container with the elements yielded by an iterator
-    fn extend(&mut self, iterator: &mut T);
+    fn extend<T: Iterator<A>>(&mut self, iterator: &mut T);
 }
 
 /// An interface for dealing with "external iterators". These types of iterators
@@ -353,7 +353,7 @@ pub trait Iterator<A> {
     /// assert!(a == b);
     /// ~~~
     #[inline]
-    fn collect<B: FromIterator<A, Self>>(&mut self) -> B {
+    fn collect<B: FromIterator<A>>(&mut self) -> B {
         FromIterator::from_iterator(self)
     }
 
diff --git a/src/libstd/str.rs b/src/libstd/str.rs
index 9148767851f..a759b8cbd62 100644
--- a/src/libstd/str.rs
+++ b/src/libstd/str.rs
@@ -2111,9 +2111,9 @@ impl Clone for @str {
     }
 }
 
-impl<T: Iterator<char>> FromIterator<char, T> for ~str {
+impl FromIterator<char> for ~str {
     #[inline]
-    fn from_iterator(iterator: &mut T) -> ~str {
+    fn from_iterator<T: Iterator<char>>(iterator: &mut T) -> ~str {
         let (lower, _) = iterator.size_hint();
         let mut buf = with_capacity(lower);
         buf.extend(iterator);
@@ -2121,9 +2121,9 @@ impl<T: Iterator<char>> FromIterator<char, T> for ~str {
     }
 }
 
-impl<T: Iterator<char>> Extendable<char, T> for ~str {
+impl Extendable<char> for ~str {
     #[inline]
-    fn extend(&mut self, iterator: &mut T) {
+    fn extend<T: Iterator<char>>(&mut self, iterator: &mut T) {
         let (lower, _) = iterator.size_hint();
         let reserve = lower + self.len();
         self.reserve_at_least(reserve);
diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs
index da1fb9abaee..f5c7b719c4f 100644
--- a/src/libstd/trie.rs
+++ b/src/libstd/trie.rs
@@ -205,16 +205,16 @@ impl<T> TrieMap<T> {
     }
 }
 
-impl<T, Iter: Iterator<(uint, T)>> FromIterator<(uint, T), Iter> for TrieMap<T> {
-    fn from_iterator(iter: &mut Iter) -> TrieMap<T> {
+impl<T> FromIterator<(uint, T)> for TrieMap<T> {
+    fn from_iterator<Iter: Iterator<(uint, T)>>(iter: &mut Iter) -> TrieMap<T> {
         let mut map = TrieMap::new();
         map.extend(iter);
         map
     }
 }
 
-impl<T, Iter: Iterator<(uint, T)>> Extendable<(uint, T), Iter> for TrieMap<T> {
-    fn extend(&mut self, iter: &mut Iter) {
+impl<T> Extendable<(uint, T)> for TrieMap<T> {
+    fn extend<Iter: Iterator<(uint, T)>>(&mut self, iter: &mut Iter) {
         for (k, v) in *iter {
             self.insert(k, v);
         }
@@ -294,16 +294,16 @@ impl TrieSet {
     }
 }
 
-impl<Iter: Iterator<uint>> FromIterator<uint, Iter> for TrieSet {
-    fn from_iterator(iter: &mut Iter) -> TrieSet {
+impl FromIterator<uint> for TrieSet {
+    fn from_iterator<Iter: Iterator<uint>>(iter: &mut Iter) -> TrieSet {
         let mut set = TrieSet::new();
         set.extend(iter);
         set
     }
 }
 
-impl<Iter: Iterator<uint>> Extendable<uint, Iter> for TrieSet {
-    fn extend(&mut self, iter: &mut Iter) {
+impl Extendable<uint> for TrieSet {
+    fn extend<Iter: Iterator<uint>>(&mut self, iter: &mut Iter) {
         for elem in *iter {
             self.insert(elem);
         }
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 6d27c43def8..a605ea4373f 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -2344,8 +2344,8 @@ impl<T> Iterator<T> for MoveRevIterator<T> {
     }
 }
 
-impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {
-    fn from_iterator(iterator: &mut T) -> ~[A] {
+impl<A> FromIterator<A> for ~[A] {
+    fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> ~[A] {
         let (lower, _) = iterator.size_hint();
         let mut xs = with_capacity(lower);
         for x in *iterator {
@@ -2355,8 +2355,8 @@ impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {
     }
 }
 
-impl<A, T: Iterator<A>> Extendable<A, T> for ~[A] {
-    fn extend(&mut self, iterator: &mut T) {
+impl<A> Extendable<A> for ~[A] {
+    fn extend<T: Iterator<A>>(&mut self, iterator: &mut T) {
         let (lower, _) = iterator.size_hint();
         let len = self.len();
         self.reserve(len + lower);