auto merge of #19467 : japaric/rust/uc, r=alexcrichton

This PR moves almost all our current uses of closures, both in public API and internal uses, to the new "unboxed" closures system.

In most cases, downstream code that *only uses* closures will continue to work as it is. The reason is that the `|| {}` syntax can be inferred either as a boxed or an "unboxed" closure according to the context. For example the following code will continue to work:

``` rust
some_option.map(|x| x.transform_with(upvar))
```

And will get silently upgraded to an "unboxed" closure.

In some other cases, it may be necessary to "annotate" which `Fn*` trait the closure implements:

```
// Change this
|x| { /* body */}
// to either of these
|: x| { /* body */}  // closure implements the FnOnce trait
|&mut : x| { /* body */}  // FnMut
|&: x| { /* body */}  // Fn
```

This mainly occurs when the closure is assigned to a variable first, and then passed to a function/method.

``` rust
let closure = |: x| x.transform_with(upvar);
some.option.map(closure)
```

(It's very likely that in the future, an improved inference engine will make this annotation unnecessary)

Other cases that require annotation are closures that implement some trait via a blanket `impl`, for example:

- `std::finally::Finally`
- `regex::Replacer`
- `std::str::CharEq`

``` rust
string.trim_left_chars(|c: char| c.is_whitespace())
//~^ ERROR: the trait `Fn<(char,), bool>` is not implemented for the type `|char| -> bool`
string.trim_left_chars(|&: c: char| c.is_whitespace())  // OK
```

Finally, all implementations of traits that contain boxed closures in the arguments of their methods are now broken. And will need to be updated to use unboxed closures. These are the main affected traits:

- `serialize::Decoder`
- `serialize::DecoderHelpers`
- `serialize::Encoder`
- `serialize::EncoderHelpers`
- `rustrt::ToCStr`

For example, change this:

``` rust
// libserialize/json.rs
impl<'a> Encoder<io::IoError> for Encoder<'a> {
    fn emit_enum(&mut self,
                 _name: &str,
                 f: |&mut Encoder<'a>| -> EncodeResult) -> EncodeResult {
        f(self)
    }
}
```

to:

``` rust
// libserialize/json.rs
impl<'a> Encoder<io::IoError> for Encoder<'a> {
    fn emit_enum<F>(&mut self, _name: &str, f: F) -> EncodeResult where
        F: FnOnce(&mut Encoder<'a>) -> EncodeResult
    {
        f(self)
    }
}
```

[breaking-change]

---

### How the `Fn*` bound has been selected

I've chosen the bounds to make the functions/structs as "generic as possible", i.e. to let them allow the maximum amount of input.

- An `F: FnOnce` bound accepts the three kinds of closures: `|:|`, `|&mut:|` and `|&:|`.
- An `F: FnMut` bound only accepts "non-consuming" closures: `|&mut:|` and `|&:|`.
- An `F: Fn` bound only accept the "immutable environment" closures: `|&:|`.

This means that whenever possible the `FnOnce` bound has been used, if the `FnOnce` bound couldn't be used, then the `FnMut` was used. The `Fn` bound was never used in the whole repository.

The `FnMut` bound was the most used, because it resembles the semantics of the current boxed closures: the closure can modify its environment, and the closure may be called several times.

The `FnOnce` bound allows new semantics: you can move out the upvars when the closure is called. This can be effectively paired with the `move || {}` syntax to transfer ownership from the environment to the closure caller.

In the case of trait methods, is hard to select the "right" bound since we can't control how the trait may be implemented by downstream users. In these cases, I have selected the bound based on how we use these traits in the repository. For this reason the selected bounds may not be ideal, and may require tweaking before stabilization.

r? @aturon

13 files changed, 211 insertions, 122 deletions

diff --git a/src/libcollections/bench.rs b/src/libcollections/bench.rs
index a212f22f899..3346e55158a 100644
--- a/src/libcollections/bench.rs
+++ b/src/libcollections/bench.rs
@@ -13,9 +13,14 @@ use std::rand;
 use std::rand::Rng;
 use test::Bencher;
 
-pub fn insert_rand_n<M>(n: uint, map: &mut M, b: &mut Bencher,
-                        insert: |&mut M, uint|,
-                        remove: |&mut M, uint|) {
+pub fn insert_rand_n<M, I, R>(n: uint,
+                              map: &mut M,
+                              b: &mut Bencher,
+                              mut insert: I,
+                              mut remove: R) where
+    I: FnMut(&mut M, uint),
+    R: FnMut(&mut M, uint),
+{
     // setup
     let mut rng = rand::weak_rng();
 
@@ -31,9 +36,14 @@ pub fn insert_rand_n<M>(n: uint, map: &mut M, b: &mut Bencher,
     })
 }
 
-pub fn insert_seq_n<M>(n: uint, map: &mut M, b: &mut Bencher,
-                       insert: |&mut M, uint|,
-                       remove: |&mut M, uint|) {
+pub fn insert_seq_n<M, I, R>(n: uint,
+                             map: &mut M,
+                             b: &mut Bencher,
+                             mut insert: I,
+                             mut remove: R) where
+    I: FnMut(&mut M, uint),
+    R: FnMut(&mut M, uint),
+{
     // setup
     for i in range(0u, n) {
         insert(map, i * 2);
@@ -48,9 +58,14 @@ pub fn insert_seq_n<M>(n: uint, map: &mut M, b: &mut Bencher,
     })
 }
 
-pub fn find_rand_n<M, T>(n: uint, map: &mut M, b: &mut Bencher,
-                         insert: |&mut M, uint|,
-                         find: |&M, uint| -> T) {
+pub fn find_rand_n<M, T, I, F>(n: uint,
+                               map: &mut M,
+                               b: &mut Bencher,
+                               mut insert: I,
+                               mut find: F) where
+    I: FnMut(&mut M, uint),
+    F: FnMut(&M, uint) -> T,
+{
     // setup
     let mut rng = rand::weak_rng();
     let mut keys = Vec::from_fn(n, |_| rng.gen::<uint>() % n);
@@ -70,9 +85,14 @@ pub fn find_rand_n<M, T>(n: uint, map: &mut M, b: &mut Bencher,
     })
 }
 
-pub fn find_seq_n<M, T>(n: uint, map: &mut M, b: &mut Bencher,
-                        insert: |&mut M, uint|,
-                        find: |&M, uint| -> T) {
+pub fn find_seq_n<M, T, I, F>(n: uint,
+                              map: &mut M,
+                              b: &mut Bencher,
+                              mut insert: I,
+                              mut find: F) where
+    I: FnMut(&mut M, uint),
+    F: FnMut(&M, uint) -> T,
+{
     // setup
     for i in range(0u, n) {
         insert(map, i);
diff --git a/src/libcollections/bit.rs b/src/libcollections/bit.rs
index b401978c9c9..a0c4f6e7ee8 100644
--- a/src/libcollections/bit.rs
+++ b/src/libcollections/bit.rs
@@ -174,7 +174,7 @@ impl<'a> Iterator<(uint, u32)> for MaskWords<'a> {
 
 impl Bitv {
     #[inline]
-    fn process(&mut self, other: &Bitv, op: |u32, u32| -> u32) -> bool {
+    fn process<F>(&mut self, other: &Bitv, mut op: F) -> bool where F: FnMut(u32, u32) -> u32 {
         let len = other.storage.len();
         assert_eq!(self.storage.len(), len);
         let mut changed = false;
@@ -816,7 +816,7 @@ pub fn from_bytes(bytes: &[u8]) -> Bitv {
 /// let bv = from_fn(5, |i| { i % 2 == 0 });
 /// assert!(bv.eq_vec(&[true, false, true, false, true]));
 /// ```
-pub fn from_fn(len: uint, f: |index: uint| -> bool) -> Bitv {
+pub fn from_fn<F>(len: uint, mut f: F) -> Bitv where F: FnMut(uint) -> bool {
     let mut bitv = Bitv::with_capacity(len, false);
     for i in range(0u, len) {
         bitv.set(i, f(i));
@@ -1182,7 +1182,7 @@ impl BitvSet {
     }
 
     #[inline]
-    fn other_op(&mut self, other: &BitvSet, f: |u32, u32| -> u32) {
+    fn other_op<F>(&mut self, other: &BitvSet, mut f: F) where F: FnMut(u32, u32) -> u32 {
         // Expand the vector if necessary
         self.reserve(other.capacity());
 
@@ -1277,10 +1277,12 @@ impl BitvSet {
     #[inline]
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn union<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
+        fn or(w1: u32, w2: u32) -> u32 { w1 | w2 }
+
         TwoBitPositions {
             set: self,
             other: other,
-            merge: |w1, w2| w1 | w2,
+            merge: or,
             current_word: 0u32,
             next_idx: 0u
         }
@@ -1306,11 +1308,13 @@ impl BitvSet {
     #[inline]
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn intersection<'a>(&'a self, other: &'a BitvSet) -> Take<TwoBitPositions<'a>> {
+        fn bitand(w1: u32, w2: u32) -> u32 { w1 & w2 }
+
         let min = cmp::min(self.capacity(), other.capacity());
         TwoBitPositions {
             set: self,
             other: other,
-            merge: |w1, w2| w1 & w2,
+            merge: bitand,
             current_word: 0u32,
             next_idx: 0
         }.take(min)
@@ -1343,10 +1347,12 @@ impl BitvSet {
     #[inline]
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
+        fn diff(w1: u32, w2: u32) -> u32 { w1 & !w2 }
+
         TwoBitPositions {
             set: self,
             other: other,
-            merge: |w1, w2| w1 & !w2,
+            merge: diff,
             current_word: 0u32,
             next_idx: 0
         }
@@ -1373,10 +1379,12 @@ impl BitvSet {
     #[inline]
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn symmetric_difference<'a>(&'a self, other: &'a BitvSet) -> TwoBitPositions<'a> {
+        fn bitxor(w1: u32, w2: u32) -> u32 { w1 ^ w2 }
+
         TwoBitPositions {
             set: self,
             other: other,
-            merge: |w1, w2| w1 ^ w2,
+            merge: bitxor,
             current_word: 0u32,
             next_idx: 0
         }
@@ -1614,7 +1622,7 @@ pub struct BitPositions<'a> {
 pub struct TwoBitPositions<'a> {
     set: &'a BitvSet,
     other: &'a BitvSet,
-    merge: |u32, u32|: 'a -> u32,
+    merge: fn(u32, u32) -> u32,
     current_word: u32,
     next_idx: uint
 }
diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index 3d5067d5a51..e49a8ddbe5a 100644
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -107,10 +107,12 @@ pub struct MoveEntries<K, V> {
 }
 
 /// An iterator over a BTreeMap's keys.
-pub type Keys<'a, K, V> = iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
+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>;
 
 /// An iterator over a BTreeMap's values.
-pub type Values<'a, K, V> = iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
+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>;
 
 /// A view into a single entry in a map, which may either be vacant or occupied.
 pub enum Entry<'a, K:'a, V:'a> {
@@ -1207,7 +1209,9 @@ impl<K, V> BTreeMap<K, V> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
-        self.iter().map(|(k, _)| k)
+        fn first<A, B>((a, _): (A, B)) -> A { a }
+
+        self.iter().map(first)
     }
 
     /// Gets an iterator over the values of the map.
@@ -1226,7 +1230,9 @@ impl<K, V> BTreeMap<K, V> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
-        self.iter().map(|(_, v)| v)
+        fn second<A, B>((_, b): (A, B)) -> B { b }
+
+        self.iter().map(second)
     }
 
     /// Return the number of elements in the map.
diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs
index 0fbc319f4ff..cd01c008fe1 100644
--- a/src/libcollections/btree/set.rs
+++ b/src/libcollections/btree/set.rs
@@ -36,7 +36,8 @@ pub struct BTreeSet<T>{
 pub type Items<'a, T> = Keys<'a, T, ()>;
 
 /// An owning iterator over a BTreeSet's items.
-pub type MoveItems<T> = iter::Map<'static, (T, ()), T, MoveEntries<T, ()>>;
+pub type MoveItems<T> =
+    iter::Map<(T, ()), T, MoveEntries<T, ()>, fn((T, ())) -> T>;
 
 /// A lazy iterator producing elements in the set difference (in-order).
 pub struct DifferenceItems<'a, T:'a> {
@@ -87,7 +88,9 @@ impl<T> BTreeSet<T> {
     /// Gets an iterator for moving out the BtreeSet's contents.
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveItems<T> {
-        self.map.into_iter().map(|(k, _)| k)
+        fn first<A, B>((a, _): (A, B)) -> A { a }
+
+        self.map.into_iter().map(first)
     }
 }
 
@@ -600,10 +603,23 @@ mod test {
       assert!(hash::hash(&x) == hash::hash(&y));
     }
 
-    fn check(a: &[int],
-             b: &[int],
-             expected: &[int],
-             f: |&BTreeSet<int>, &BTreeSet<int>, f: |&int| -> bool| -> bool) {
+    struct Counter<'a, 'b> {
+        i: &'a mut uint,
+        expected: &'b [int],
+    }
+
+    impl<'a, 'b> FnMut(&int) -> bool for Counter<'a, 'b> {
+        extern "rust-call" fn call_mut(&mut self, (&x,): (&int,)) -> bool {
+            assert_eq!(x, self.expected[*self.i]);
+            *self.i += 1;
+            true
+        }
+    }
+
+    fn check<F>(a: &[int], b: &[int], expected: &[int], f: F) where
+        // FIXME Replace Counter with `Box<FnMut(_) -> _>`
+        F: FnOnce(&BTreeSet<int>, &BTreeSet<int>, Counter) -> bool,
+    {
         let mut set_a = BTreeSet::new();
         let mut set_b = BTreeSet::new();
 
@@ -611,11 +627,7 @@ mod test {
         for y in b.iter() { assert!(set_b.insert(*y)) }
 
         let mut i = 0;
-        f(&set_a, &set_b, |x| {
-            assert_eq!(*x, expected[i]);
-            i += 1;
-            true
-        });
+        f(&set_a, &set_b, Counter { i: &mut i, expected: expected });
         assert_eq!(i, expected.len());
     }
 
diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index d50b212c7dd..f49a0c037de 100644
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -351,18 +351,16 @@ impl<T> DList<T> {
     ///     println!("{}", e); // prints 2, then 4, then 11, then 7, then 8
     /// }
     /// ```
-    pub fn insert_when(&mut self, elt: T, f: |&T, &T| -> bool) {
-        {
-            let mut it = self.iter_mut();
-            loop {
-                match it.peek_next() {
-                    None => break,
-                    Some(x) => if f(x, &elt) { break }
-                }
-                it.next();
+    pub fn insert_when<F>(&mut self, elt: T, mut f: F) where F: FnMut(&T, &T) -> bool {
+        let mut it = self.iter_mut();
+        loop {
+            match it.peek_next() {
+                None => break,
+                Some(x) => if f(x, &elt) { break }
             }
-            it.insert_next(elt);
+            it.next();
         }
+        it.insert_next(elt);
     }
 
     /// Merges `other` into this `DList`, using the function `f`.
@@ -371,7 +369,7 @@ impl<T> DList<T> {
     /// put `a` in the result if `f(a, b)` is true, and otherwise `b`.
     ///
     /// This operation should compute in O(max(N, M)) time.
-    pub fn merge(&mut self, mut other: DList<T>, f: |&T, &T| -> bool) {
+    pub fn merge<F>(&mut self, mut other: DList<T>, mut f: F) where F: FnMut(&T, &T) -> bool {
         {
             let mut it = self.iter_mut();
             loop {
diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index 6bdfa490748..463e28b420d 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -94,6 +94,7 @@ use core::cmp;
 use core::kinds::{Copy, Sized};
 use core::mem::size_of;
 use core::mem;
+use core::ops::FnMut;
 use core::prelude::{Clone, Greater, Iterator, IteratorExt, Less, None, Option};
 use core::prelude::{Ord, Ordering, RawPtr, Some, range};
 use core::ptr;
@@ -296,7 +297,7 @@ pub trait CloneSliceAllocPrelude<T> for Sized? {
 
     /// Partitions the vector into two vectors `(a, b)`, where all
     /// elements of `a` satisfy `f` and all elements of `b` do not.
-    fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>);
+    fn partitioned<F>(&self, f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool;
 
     /// Creates an iterator that yields every possible permutation of the
     /// vector in succession.
@@ -336,7 +337,7 @@ impl<T: Clone> CloneSliceAllocPrelude<T> for [T] {
 
 
     #[inline]
-    fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
+    fn partitioned<F>(&self, mut f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool {
         let mut lefts  = Vec::new();
         let mut rights = Vec::new();
 
@@ -361,7 +362,7 @@ impl<T: Clone> CloneSliceAllocPrelude<T> for [T] {
 
 }
 
-fn insertion_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
+fn insertion_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering {
     let len = v.len() as int;
     let buf_v = v.as_mut_ptr();
 
@@ -403,7 +404,7 @@ fn insertion_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
     }
 }
 
-fn merge_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
+fn merge_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering {
     // warning: this wildly uses unsafe.
     static BASE_INSERTION: uint = 32;
     static LARGE_INSERTION: uint = 16;
@@ -611,7 +612,7 @@ pub trait SliceAllocPrelude<T> for Sized? {
     /// v.sort_by(|a, b| b.cmp(a));
     /// assert!(v == [5, 4, 3, 2, 1]);
     /// ```
-    fn sort_by(&mut self, compare: |&T, &T| -> Ordering);
+    fn sort_by<F>(&mut self, compare: F) where F: FnMut(&T, &T) -> Ordering;
 
     /// Consumes `src` and moves as many elements as it can into `self`
     /// from the range [start,end).
@@ -639,7 +640,7 @@ pub trait SliceAllocPrelude<T> for Sized? {
 
 impl<T> SliceAllocPrelude<T> for [T] {
     #[inline]
-    fn sort_by(&mut self, compare: |&T, &T| -> Ordering) {
+    fn sort_by<F>(&mut self, compare: F) where F: FnMut(&T, &T) -> Ordering {
         merge_sort(self, compare)
     }
 
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index 2e96b941c08..bf568fd92d5 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -903,21 +903,21 @@ mod tests {
     #[test]
     fn test_find() {
         assert_eq!("hello".find('l'), Some(2u));
-        assert_eq!("hello".find(|c:char| c == 'o'), Some(4u));
+        assert_eq!("hello".find(|&: c:char| c == 'o'), Some(4u));
         assert!("hello".find('x').is_none());
-        assert!("hello".find(|c:char| c == 'x').is_none());
+        assert!("hello".find(|&: c:char| c == 'x').is_none());
         assert_eq!("ประเทศไทย中华Việt Nam".find('华'), Some(30u));
-        assert_eq!("ประเทศไทย中华Việt Nam".find(|c: char| c == '华'), Some(30u));
+        assert_eq!("ประเทศไทย中华Việt Nam".find(|&: c: char| c == '华'), Some(30u));
     }
 
     #[test]
     fn test_rfind() {
         assert_eq!("hello".rfind('l'), Some(3u));
-        assert_eq!("hello".rfind(|c:char| c == 'o'), Some(4u));
+        assert_eq!("hello".rfind(|&: c:char| c == 'o'), Some(4u));
         assert!("hello".rfind('x').is_none());
-        assert!("hello".rfind(|c:char| c == 'x').is_none());
+        assert!("hello".rfind(|&: c:char| c == 'x').is_none());
         assert_eq!("ประเทศไทย中华Việt Nam".rfind('华'), Some(30u));
-        assert_eq!("ประเทศไทย中华Việt Nam".rfind(|c: char| c == '华'), Some(30u));
+        assert_eq!("ประเทศไทย中华Việt Nam".rfind(|&: c: char| c == '华'), Some(30u));
     }
 
     #[test]
@@ -1281,7 +1281,7 @@ mod tests {
         assert_eq!("11foo1bar11".trim_left_chars('1'), "foo1bar11");
         let chars: &[char] = &['1', '2'];
         assert_eq!("12foo1bar12".trim_left_chars(chars), "foo1bar12");
-        assert_eq!("123foo1bar123".trim_left_chars(|c: char| c.is_numeric()), "foo1bar123");
+        assert_eq!("123foo1bar123".trim_left_chars(|&: c: char| c.is_numeric()), "foo1bar123");
     }
 
     #[test]
@@ -1296,7 +1296,7 @@ mod tests {
         assert_eq!("11foo1bar11".trim_right_chars('1'), "11foo1bar");
         let chars: &[char] = &['1', '2'];
         assert_eq!("12foo1bar12".trim_right_chars(chars), "12foo1bar");
-        assert_eq!("123foo1bar123".trim_right_chars(|c: char| c.is_numeric()), "123foo1bar");
+        assert_eq!("123foo1bar123".trim_right_chars(|&: c: char| c.is_numeric()), "123foo1bar");
     }
 
     #[test]
@@ -1311,7 +1311,7 @@ mod tests {
         assert_eq!("11foo1bar11".trim_chars('1'), "foo1bar");
         let chars: &[char] = &['1', '2'];
         assert_eq!("12foo1bar12".trim_chars(chars), "foo1bar");
-        assert_eq!("123foo1bar123".trim_chars(|c: char| c.is_numeric()), "foo1bar");
+        assert_eq!("123foo1bar123".trim_chars(|&: c: char| c.is_numeric()), "foo1bar");
     }
 
     #[test]
@@ -1787,14 +1787,14 @@ mod tests {
         let split: Vec<&str> = data.splitn(3, ' ').collect();
         assert_eq!(split, vec!["\nMäry", "häd", "ä", "little lämb\nLittle lämb\n"]);
 
-        let split: Vec<&str> = data.splitn(3, |c: char| c == ' ').collect();
+        let split: Vec<&str> = data.splitn(3, |&: c: char| c == ' ').collect();
         assert_eq!(split, vec!["\nMäry", "häd", "ä", "little lämb\nLittle lämb\n"]);
 
         // Unicode
         let split: Vec<&str> = data.splitn(3, 'ä').collect();
         assert_eq!(split, vec!["\nM", "ry h", "d ", " little lämb\nLittle lämb\n"]);
 
-        let split: Vec<&str> = data.splitn(3, |c: char| c == 'ä').collect();
+        let split: Vec<&str> = data.splitn(3, |&: c: char| c == 'ä').collect();
         assert_eq!(split, vec!["\nM", "ry h", "d ", " little lämb\nLittle lämb\n"]);
     }
 
@@ -2588,7 +2588,7 @@ mod bench {
         let s = "Mary had a little lamb, Little lamb, little-lamb.";
         let len = s.split(' ').count();
 
-        b.iter(|| assert_eq!(s.split(|c: char| c == ' ').count(), len));
+        b.iter(|| assert_eq!(s.split(|&: c: char| c == ' ').count(), len));
     }
 
     #[bench]
diff --git a/src/libcollections/tree/map.rs b/src/libcollections/tree/map.rs
index 24395ca6493..5c2cf4a8180 100644
--- a/src/libcollections/tree/map.rs
+++ b/src/libcollections/tree/map.rs
@@ -234,7 +234,9 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
-        self.iter().map(|(k, _v)| k)
+        fn first<A, B>((a, _): (A, B)) -> A { a }
+
+        self.iter().map(first)
     }
 
     /// Gets a lazy iterator over the values in the map, in ascending order
@@ -256,7 +258,9 @@ impl<K: Ord, V> TreeMap<K, V> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values<'a>(&'a self) -> Values<'a, K, V> {
-        self.iter().map(|(_k, v)| v)
+        fn second<A, B>((_, b): (A, B)) -> B { b }
+
+        self.iter().map(second)
     }
 
     /// Gets a lazy iterator over the key-value pairs in the map, in ascending order.
@@ -612,7 +616,7 @@ impl<K, V> TreeMap<K, V> {
     /// ```
     #[inline]
     #[experimental = "likely to be renamed, may be removed"]
-    pub fn find_with(&self, f:|&K| -> Ordering) -> Option<&V> {
+    pub fn find_with<F>(&self, f: F) -> Option<&V> where F: FnMut(&K) -> Ordering {
         tree_find_with(&self.root, f)
     }
 
@@ -637,7 +641,9 @@ impl<K, V> TreeMap<K, V> {
     /// ```
     #[inline]
     #[experimental = "likely to be renamed, may be removed"]
-    pub fn find_with_mut<'a>(&'a mut self, f:|&K| -> Ordering) -> Option<&'a mut V> {
+    pub fn find_with_mut<'a, F>(&'a mut self, f: F) -> Option<&'a mut V> where
+        F: FnMut(&K) -> Ordering
+    {
         tree_find_with_mut(&mut self.root, f)
     }
 }
@@ -863,11 +869,11 @@ pub struct RevMutEntries<'a, K:'a, V:'a> {
 
 /// TreeMap keys iterator.
 pub type Keys<'a, K, V> =
-    iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
+    iter::Map<(&'a K, &'a V), &'a K, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>;
 
 /// TreeMap values iterator.
 pub type Values<'a, K, V> =
-    iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
+    iter::Map<(&'a K, &'a V), &'a V, Entries<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>;
 
 
 // FIXME #5846 we want to be able to choose between &x and &mut x
@@ -1125,8 +1131,12 @@ fn split<K: Ord, V>(node: &mut Box<TreeNode<K, V>>) {
 // Next 2 functions have the same convention: comparator gets
 // at input current key and returns search_key cmp cur_key
 // (i.e. search_key.cmp(&cur_key))
-fn tree_find_with<'r, K, V>(node: &'r Option<Box<TreeNode<K, V>>>,
-                            f: |&K| -> Ordering) -> Option<&'r V> {
+fn tree_find_with<'r, K, V, F>(
+    node: &'r Option<Box<TreeNode<K, V>>>,
+    mut f: F,
+) -> Option<&'r V> where
+    F: FnMut(&K) -> Ordering,
+{
     let mut current: &'r Option<Box<TreeNode<K, V>>> = node;
     loop {
         match *current {
@@ -1143,8 +1153,12 @@ fn tree_find_with<'r, K, V>(node: &'r Option<Box<TreeNode<K, V>>>,
 }
 
 // See comments above tree_find_with
-fn tree_find_with_mut<'r, K, V>(node: &'r mut Option<Box<TreeNode<K, V>>>,
-                                f: |&K| -> Ordering) -> Option<&'r mut V> {
+fn tree_find_with_mut<'r, K, V, F>(
+    node: &'r mut Option<Box<TreeNode<K, V>>>,
+    mut f: F,
+) -> Option<&'r mut V> where
+    F: FnMut(&K) -> Ordering,
+{
 
     let mut current = node;
     loop {
diff --git a/src/libcollections/tree/set.rs b/src/libcollections/tree/set.rs
index 3af2f3e0193..bd8bf5c6cb6 100644
--- a/src/libcollections/tree/set.rs
+++ b/src/libcollections/tree/set.rs
@@ -205,7 +205,9 @@ impl<T: Ord> TreeSet<T> {
     #[inline]
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(self) -> MoveSetItems<T> {
-        self.map.into_iter().map(|(value, _)| value)
+        fn first<A, B>((a, _): (A, B)) -> A { a }
+
+        self.map.into_iter().map(first)
     }
 
     /// Gets a lazy iterator pointing to the first value not less than `v` (greater or equal).
@@ -560,7 +562,7 @@ pub struct RevSetItems<'a, T:'a> {
 }
 
 /// A lazy forward iterator over a set that consumes the set while iterating.
-pub type MoveSetItems<T> = iter::Map<'static, (T, ()), T, MoveEntries<T, ()>>;
+pub type MoveSetItems<T> = iter::Map<(T, ()), T, MoveEntries<T, ()>, fn((T, ())) -> T>;
 
 /// A lazy iterator producing elements in the set difference (in-order).
 pub struct DifferenceItems<'a, T:'a> {
@@ -934,10 +936,23 @@ mod test {
       assert!(hash::hash(&x) == hash::hash(&y));
     }
 
-    fn check(a: &[int],
-             b: &[int],
-             expected: &[int],
-             f: |&TreeSet<int>, &TreeSet<int>, f: |&int| -> bool| -> bool) {
+    struct Counter<'a, 'b> {
+        i: &'a mut uint,
+        expected: &'b [int],
+    }
+
+    impl<'a, 'b> FnMut(&int) -> bool for Counter<'a, 'b> {
+        extern "rust-call" fn call_mut(&mut self, (&x,): (&int,)) -> bool {
+            assert_eq!(x, self.expected[*self.i]);
+            *self.i += 1;
+            true
+        }
+    }
+
+    fn check<F>(a: &[int], b: &[int], expected: &[int], f: F) where
+        // FIXME Replace `Counter` with `Box<FnMut(&int) -> bool>`
+        F: FnOnce(&TreeSet<int>, &TreeSet<int>, Counter) -> bool,
+    {
         let mut set_a = TreeSet::new();
         let mut set_b = TreeSet::new();
 
@@ -945,11 +960,7 @@ mod test {
         for y in b.iter() { assert!(set_b.insert(*y)) }
 
         let mut i = 0;
-        f(&set_a, &set_b, |x| {
-            assert_eq!(*x, expected[i]);
-            i += 1;
-            true
-        });
+        f(&set_a, &set_b, Counter { i: &mut i, expected: expected });
         assert_eq!(i, expected.len());
     }
 
diff --git a/src/libcollections/trie/map.rs b/src/libcollections/trie/map.rs
index 1b087d2e63d..a4dee807648 100644
--- a/src/libcollections/trie/map.rs
+++ b/src/libcollections/trie/map.rs
@@ -197,14 +197,18 @@ impl<T> TrieMap<T> {
     /// The iterator's element type is `uint`.
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys<'r>(&'r self) -> Keys<'r, T> {
-        self.iter().map(|(k, _v)| k)
+        fn first<A, B>((a, _): (A, B)) -> A { a }
+
+        self.iter().map(first)
     }
 
     /// Gets an iterator visiting all values in ascending order by the keys.
     /// The iterator's element type is `&'r T`.
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values<'r>(&'r self) -> Values<'r, T> {
-        self.iter().map(|(_k, v)| v)
+        fn second<A, B>((_, b): (A, B)) -> B { b }
+
+        self.iter().map(second)
     }
 
     /// Gets an iterator over the key-value pairs in the map, ordered by keys.
@@ -1091,12 +1095,11 @@ pub struct MutEntries<'a, T:'a> {
 }
 
 /// A forward iterator over the keys of a map.
-pub type Keys<'a, T> =
-    iter::Map<'static, (uint, &'a T), uint, Entries<'a, T>>;
+pub type Keys<'a, T> = iter::Map<(uint, &'a T), uint, Entries<'a, T>, fn((uint, &'a T)) -> uint>;
 
 /// A forward iterator over the values of a map.
 pub type Values<'a, T> =
-    iter::Map<'static, (uint, &'a T), &'a T, Entries<'a, T>>;
+    iter::Map<(uint, &'a T), &'a T, Entries<'a, T>, fn((uint, &'a T)) -> &'a T>;
 
 // FIXME #5846: see `addr!` above.
 macro_rules! item { ($i:item) => {$i}}
diff --git a/src/libcollections/trie/set.rs b/src/libcollections/trie/set.rs
index 46052ff2f50..5621726dc56 100644
--- a/src/libcollections/trie/set.rs
+++ b/src/libcollections/trie/set.rs
@@ -743,10 +743,23 @@ mod test {
         assert!(a < b && a <= b);
     }
 
-    fn check(a: &[uint],
-             b: &[uint],
-             expected: &[uint],
-             f: |&TrieSet, &TrieSet, f: |uint| -> bool| -> bool) {
+    struct Counter<'a, 'b> {
+        i: &'a mut uint,
+        expected: &'b [uint],
+    }
+
+    impl<'a, 'b> FnMut(uint) -> bool for Counter<'a, 'b> {
+        extern "rust-call" fn call_mut(&mut self, (x,): (uint,)) -> bool {
+            assert_eq!(x, self.expected[*self.i]);
+            *self.i += 1;
+            true
+        }
+    }
+
+    fn check<F>(a: &[uint], b: &[uint], expected: &[uint], f: F) where
+        // FIXME Replace `Counter` with `Box<FnMut(&uint) -> bool>`
+        F: FnOnce(&TrieSet, &TrieSet, Counter) -> bool,
+    {
         let mut set_a = TrieSet::new();
         let mut set_b = TrieSet::new();
 
@@ -754,11 +767,7 @@ mod test {
         for y in b.iter() { assert!(set_b.insert(*y)) }
 
         let mut i = 0;
-        f(&set_a, &set_b, |x| {
-            assert_eq!(x, expected[i]);
-            i += 1;
-            true
-        });
+        f(&set_a, &set_b, Counter { i: &mut i, expected: expected });
         assert_eq!(i, expected.len());
     }
 
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index f8a971db173..2ed8686394c 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -206,7 +206,7 @@ impl<T> Vec<T> {
     #[inline]
     #[unstable = "the naming is uncertain as well as this migrating to unboxed \
                   closures in the future"]
-    pub fn from_fn(length: uint, op: |uint| -> T) -> Vec<T> {
+    pub fn from_fn<F>(length: uint, mut op: F) -> Vec<T> where F: FnMut(uint) -> T {
         unsafe {
             let mut xs = Vec::with_capacity(length);
             while xs.len < length {
@@ -289,7 +289,7 @@ impl<T> Vec<T> {
     /// ```
     #[inline]
     #[experimental]
-    pub fn partition(self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
+    pub fn partition<F>(self, mut f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool {
         let mut lefts  = Vec::new();
         let mut rights = Vec::new();
 
@@ -400,7 +400,7 @@ impl<T: Clone> Vec<T> {
     /// assert_eq!(odd, vec![1i, 3]);
     /// ```
     #[experimental]
-    pub fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
+    pub fn partitioned<F>(&self, mut f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool {
         let mut lefts = Vec::new();
         let mut rights = Vec::new();
 
@@ -991,7 +991,7 @@ impl<T> Vec<T> {
     /// assert_eq!(vec, vec![2, 4]);
     /// ```
     #[unstable = "the closure argument may become an unboxed closure"]
-    pub fn retain(&mut self, f: |&T| -> bool) {
+    pub fn retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool {
         let len = self.len();
         let mut del = 0u;
         {
@@ -1023,7 +1023,7 @@ impl<T> Vec<T> {
     /// assert_eq!(vec, vec![0, 1, 0, 1, 2]);
     /// ```
     #[unstable = "this function may be renamed or change to unboxed closures"]
-    pub fn grow_fn(&mut self, n: uint, f: |uint| -> T) {
+    pub fn grow_fn<F>(&mut self, n: uint, mut f: F) where F: FnMut(uint) -> T {
         self.reserve(n);
         for i in range(0u, n) {
             self.push(f(i));
@@ -1570,7 +1570,7 @@ impl<T> Vec<T> {
     /// let newtyped_bytes = bytes.map_in_place(|x| Newtype(x));
     /// assert_eq!(newtyped_bytes.as_slice(), [Newtype(0x11), Newtype(0x22)].as_slice());
     /// ```
-    pub fn map_in_place<U>(self, f: |T| -> U) -> Vec<U> {
+    pub fn map_in_place<U, F>(self, mut f: F) -> Vec<U> where F: FnMut(T) -> U {
         // FIXME: Assert statically that the types `T` and `U` have the same
         // size.
         assert!(mem::size_of::<T>() == mem::size_of::<U>());
diff --git a/src/libcollections/vec_map.rs b/src/libcollections/vec_map.rs
index 3b8c690e047..cc2fd0a6646 100644
--- a/src/libcollections/vec_map.rs
+++ b/src/libcollections/vec_map.rs
@@ -20,6 +20,7 @@ use core::fmt;
 use core::iter;
 use core::iter::{Enumerate, FilterMap};
 use core::mem::replace;
+use core::ops::FnOnce;
 
 use hash::{Hash, Writer};
 use {vec, slice};
@@ -141,14 +142,18 @@ impl<V> VecMap<V> {
     /// The iterator's element type is `uint`.
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn keys<'r>(&'r self) -> Keys<'r, V> {
-        self.iter().map(|(k, _v)| k)
+        fn first<A, B>((a, _): (A, B)) -> A { a }
+
+        self.iter().map(first)
     }
 
     /// Returns an iterator visiting all values in ascending order by the keys.
     /// The iterator's element type is `&'r V`.
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn values<'r>(&'r self) -> Values<'r, V> {
-        self.iter().map(|(_k, v)| v)
+        fn second<A, B>((_, b): (A, B)) -> B { b }
+
+        self.iter().map(second)
     }
 
     /// Returns an iterator visiting all key-value pairs in ascending order by the keys.
@@ -230,10 +235,12 @@ impl<V> VecMap<V> {
     /// ```
     #[unstable = "matches collection reform specification, waiting for dust to settle"]
     pub fn into_iter(&mut self) -> MoveItems<V> {
-        let values = replace(&mut self.v, vec!());
-        values.into_iter().enumerate().filter_map(|(i, v)| {
+        fn filter<A>((i, v): (uint, Option<A>)) -> Option<(uint, A)> {
             v.map(|v| (i, v))
-        })
+        }
+
+        let values = replace(&mut self.v, vec!());
+        values.into_iter().enumerate().filter_map(filter)
     }
 
     /// Return the number of elements in the map.
@@ -446,8 +453,8 @@ impl<V:Clone> VecMap<V> {
     /// assert!(!map.update(1, vec![3i, 4], |mut old, new| { old.extend(new.into_iter()); old }));
     /// assert_eq!(map[1], vec![1i, 2, 3, 4]);
     /// ```
-    pub fn update(&mut self, key: uint, newval: V, ff: |V, V| -> V) -> bool {
-        self.update_with_key(key, newval, |_k, v, v1| ff(v,v1))
+    pub fn update<F>(&mut self, key: uint, newval: V, ff: F) -> bool where F: FnOnce(V, V) -> V {
+        self.update_with_key(key, newval, move |_k, v, v1| ff(v,v1))
     }
 
     /// Updates a value in the map. If the key already exists in the map,
@@ -470,11 +477,9 @@ impl<V:Clone> VecMap<V> {
     /// assert!(!map.update_with_key(7, 20, |key, old, new| (old + new) % key));
     /// assert_eq!(map[7], 2);
     /// ```
-    pub fn update_with_key(&mut self,
-                           key: uint,
-                           val: V,
-                           ff: |uint, V, V| -> V)
-                           -> bool {
+    pub fn update_with_key<F>(&mut self, key: uint, val: V, ff: F) -> bool where
+        F: FnOnce(uint, V, V) -> V
+    {
         let new_val = match self.get(&key) {
             None => val,
             Some(orig) => ff(key, (*orig).clone(), val)
@@ -620,16 +625,18 @@ iterator!(impl MutEntries -> (uint, &'a mut V), as_mut)
 double_ended_iterator!(impl MutEntries -> (uint, &'a mut V), as_mut)
 
 /// Forward iterator over the keys of a map
-pub type Keys<'a, V> =
-    iter::Map<'static, (uint, &'a V), uint, Entries<'a, V>>;
+pub type Keys<'a, V> = iter::Map<(uint, &'a V), uint, Entries<'a, V>, fn((uint, &'a V)) -> uint>;
 
 /// Forward iterator over the values of a map
 pub type Values<'a, V> =
-    iter::Map<'static, (uint, &'a V), &'a V, Entries<'a, V>>;
+    iter::Map<(uint, &'a V), &'a V, Entries<'a, V>, fn((uint, &'a V)) -> &'a V>;
 
 /// Iterator over the key-value pairs of a map, the iterator consumes the map
-pub type MoveItems<V> =
-    FilterMap<'static, (uint, Option<V>), (uint, V), Enumerate<vec::MoveItems<Option<V>>>>;
+pub type MoveItems<V> = FilterMap<
+    (uint, Option<V>),
+    (uint, V),
+    Enumerate<vec::MoveItems<Option<V>>>,
+    fn((uint, Option<V>)) -> Option<(uint, V)>>;
 
 #[cfg(test)]
 mod test_map {