auto merge of #20578 : japaric/rust/no-more-bc, r=nmatsakis

This PR removes boxed closures from the language, the closure type syntax (`let f: |int| -> bool = /* ... */`) has been obsoleted. Move all your uses of closures to the new unboxed closure system (i.e. `Fn*` traits).

[breaking-change] patterns

- `lef f = || {}`

This binding used to type check to a boxed closure. Now that boxed closures are gone, you need to annotate the "kind" of the unboxed closure, i.e. you need pick one of these: `|&:| {}`, `|&mut:| {}` or `|:| {}`.

In the (near) future we'll have closure "kind" inference, so the compiler will infer which `Fn*` trait to use based on how the closure is used. Once this inference machinery is in place, we'll be able to remove the kind annotation from most closures.

- `type Alias<'a> = |int|:'a -> bool`

Use a trait object: `type Alias<'a> = Box<FnMut(int) -> bool + 'a>`. Use the `Fn*` trait that makes sense for your use case.

- `fn foo(&self, f: |uint| -> bool)`

In this case you can use either a trait object or an unboxed closure:

``` rust
fn foo(&self, f: F) where F: FnMut(uint) -> bool;
// or
fn foo(&self, f: Box<FnMut(uint) -> bool>);
```

- `struct Struct<'a> { f: |uint|:'a -> bool }`

Again, you can use either a trait object or an unboxed closure:

``` rust
struct Struct<F> where F: FnMut(uint) -> bool { f: F }
// or
struct Struct<'a> { f: Box<FnMut(uint) -> bool + 'a> }
```

- Using `|x, y| f(x, y)` for closure "borrows"

This comes up in recursive functions, consider the following (contrived) example:

``` rust
fn foo(x: uint, f: |uint| -> bool) -> bool {
    //foo(x / 2, f) && f(x)  // can't use this because `f` gets moved away in the `foo` call
    foo(x / 2, |x| f(x)) && f(x)  // instead "borrow" `f` in the `foo` call
}
```

If you attempt to do the same with unboxed closures you'll hit ""error: reached the recursion limit during monomorphization" (see #19596):

``` rust
fn foo<F>(x: uint, mut f: F) -> bool where F: FnMut(uint) -> bool {
    foo(x / 2, |x| f(x)) && f(x)
    //~^ error: reached the recursion limit during monomorphization
}
```

Instead you *should* be able to write this:

``` rust
fn foo<F>(x: uint, mut f: F) -> bool where F: FnMut(uint) -> bool {
    foo(x / 2, &mut f) && f(x)
    //~^ error: the trait `FnMut` is not implemented for the type `&mut F`
}
```

But as you see above `&mut F` doesn't implement the `FnMut` trait. `&mut F` *should* implement the `FnMut` and the above code *should* work, but due to a bug (see #18835) it doesn't (for now).

You can work around the issue by rewriting the function to take `&mut F` instead of `F`:

``` rust
fn foo<F>(x: uint, f: &mut F) -> bool where F: FnMut(uint) -> bool {
    foo(x / 2, f) && (*f)(x)
}
```

This finally works! However writing `foo(0, &mut |x| x == 0)` is unergonomic. So you can use a private helper function to avoid this:

``` rust
// public API function
pub fn foo<F>(x: uint, mut f: F) -> bool where F: FnMut(uint) -> bool {
    foo_(x, &mut f)
}

// private helper function
fn foo_<F>(x: uint, f: &mut F) -> bool where F: FnMut(uint) -> bool {
    foo_(x / 2, f) && (*f)(x)
}
```

Closes #14798

---

There is more cleanup to do: like renaming functions/types from `unboxed_closure` to just `closure`, removing more dead code, simplify functions which now have unused arguments, update the documentation, etc. But that can be done in another PR.

r? @nikomatsakis @aturon (You probably want to focus on the deleted/modified tests.)
cc @eddyb 

13 files changed, 29 insertions, 33 deletions

diff --git a/src/libsyntax/ext/deriving/clone.rs b/src/libsyntax/ext/deriving/clone.rs
index eedec6f37c8..3c74a9f4431 100644
--- a/src/libsyntax/ext/deriving/clone.rs
+++ b/src/libsyntax/ext/deriving/clone.rs
@@ -40,7 +40,7 @@ pub fn expand_deriving_clone<F>(cx: &mut ExtCtxt,
                 args: Vec::new(),
                 ret_ty: Self,
                 attributes: attrs,
-                combine_substructure: combine_substructure(|c, s, sub| {
+                combine_substructure: combine_substructure(box |c, s, sub| {
                     cs_clone("Clone", c, s, sub)
                 }),
             }
diff --git a/src/libsyntax/ext/deriving/cmp/eq.rs b/src/libsyntax/ext/deriving/cmp/eq.rs
index 7a67fab820d..84d30a99004 100644
--- a/src/libsyntax/ext/deriving/cmp/eq.rs
+++ b/src/libsyntax/ext/deriving/cmp/eq.rs
@@ -40,7 +40,7 @@ pub fn expand_deriving_eq<F>(cx: &mut ExtCtxt,
                 cx.expr_binary(span, ast::BiAnd, subexpr, eq)
             },
             cx.expr_bool(span, true),
-            |cx, span, _, _| cx.expr_bool(span, false),
+            box |cx, span, _, _| cx.expr_bool(span, false),
             cx, span, substr)
     }
     fn cs_ne(cx: &mut ExtCtxt, span: Span, substr: &Substructure) -> P<Expr> {
@@ -57,7 +57,7 @@ pub fn expand_deriving_eq<F>(cx: &mut ExtCtxt,
                 cx.expr_binary(span, ast::BiOr, subexpr, eq)
             },
             cx.expr_bool(span, false),
-            |cx, span, _, _| cx.expr_bool(span, true),
+            box |cx, span, _, _| cx.expr_bool(span, true),
             cx, span, substr)
     }
 
@@ -72,7 +72,7 @@ pub fn expand_deriving_eq<F>(cx: &mut ExtCtxt,
                 args: vec!(borrowed_self()),
                 ret_ty: Literal(Path::new(vec!("bool"))),
                 attributes: attrs,
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     $f(a, b, c)
                 })
             }
diff --git a/src/libsyntax/ext/deriving/cmp/ord.rs b/src/libsyntax/ext/deriving/cmp/ord.rs
index c02416bfbea..f9c8d95b308 100644
--- a/src/libsyntax/ext/deriving/cmp/ord.rs
+++ b/src/libsyntax/ext/deriving/cmp/ord.rs
@@ -38,7 +38,7 @@ pub fn expand_deriving_ord<F>(cx: &mut ExtCtxt,
                 args: vec!(borrowed_self()),
                 ret_ty: Literal(Path::new(vec!("bool"))),
                 attributes: attrs,
-                combine_substructure: combine_substructure(|cx, span, substr| {
+                combine_substructure: combine_substructure(box |cx, span, substr| {
                     cs_op($op, $equal, cx, span, substr)
                 })
             }
@@ -61,7 +61,7 @@ pub fn expand_deriving_ord<F>(cx: &mut ExtCtxt,
         args: vec![borrowed_self()],
         ret_ty: ret_ty,
         attributes: attrs,
-        combine_substructure: combine_substructure(|cx, span, substr| {
+        combine_substructure: combine_substructure(box |cx, span, substr| {
             cs_partial_cmp(cx, span, substr)
         })
     };
@@ -174,7 +174,7 @@ pub fn cs_partial_cmp(cx: &mut ExtCtxt, span: Span,
             cx.expr_block(cx.block(span, vec!(assign), Some(if_)))
         },
         equals_expr.clone(),
-        |cx, span, (self_args, tag_tuple), _non_self_args| {
+        box |cx, span, (self_args, tag_tuple), _non_self_args| {
             if self_args.len() != 2 {
                 cx.span_bug(span, "not exactly 2 arguments in `deriving(PartialOrd)`")
             } else {
@@ -222,7 +222,7 @@ fn cs_op(less: bool, equal: bool, cx: &mut ExtCtxt,
             cx.expr_binary(span, ast::BiOr, cmp, and)
         },
         cx.expr_bool(span, equal),
-        |cx, span, (self_args, tag_tuple), _non_self_args| {
+        box |cx, span, (self_args, tag_tuple), _non_self_args| {
             if self_args.len() != 2 {
                 cx.span_bug(span, "not exactly 2 arguments in `deriving(PartialOrd)`")
             } else {
diff --git a/src/libsyntax/ext/deriving/cmp/totaleq.rs b/src/libsyntax/ext/deriving/cmp/totaleq.rs
index 2b986bea122..cdb36ede65d 100644
--- a/src/libsyntax/ext/deriving/cmp/totaleq.rs
+++ b/src/libsyntax/ext/deriving/cmp/totaleq.rs
@@ -32,7 +32,7 @@ pub fn expand_deriving_totaleq<F>(cx: &mut ExtCtxt,
             let block = cx.block(span, stmts, None);
             cx.expr_block(block)
         },
-                       |cx, sp, _, _| cx.span_bug(sp, "non matching enums in deriving(Eq)?"),
+                       box |cx, sp, _, _| cx.span_bug(sp, "non matching enums in deriving(Eq)?"),
                        cx,
                        span,
                        substr)
@@ -57,7 +57,7 @@ pub fn expand_deriving_totaleq<F>(cx: &mut ExtCtxt,
                 args: vec!(),
                 ret_ty: nil_ty(),
                 attributes: attrs,
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     cs_total_eq_assert(a, b, c)
                 })
             }
diff --git a/src/libsyntax/ext/deriving/cmp/totalord.rs b/src/libsyntax/ext/deriving/cmp/totalord.rs
index 65a4c569b44..10ecc86bda5 100644
--- a/src/libsyntax/ext/deriving/cmp/totalord.rs
+++ b/src/libsyntax/ext/deriving/cmp/totalord.rs
@@ -41,7 +41,7 @@ pub fn expand_deriving_totalord<F>(cx: &mut ExtCtxt,
                 args: vec!(borrowed_self()),
                 ret_ty: Literal(Path::new(vec!("std", "cmp", "Ordering"))),
                 attributes: attrs,
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     cs_cmp(a, b, c)
                 }),
             }
@@ -130,7 +130,7 @@ pub fn cs_cmp(cx: &mut ExtCtxt, span: Span,
             cx.expr_block(cx.block(span, vec!(assign), Some(if_)))
         },
         cx.expr_path(equals_path.clone()),
-        |cx, span, (self_args, tag_tuple), _non_self_args| {
+        box |cx, span, (self_args, tag_tuple), _non_self_args| {
             if self_args.len() != 2 {
                 cx.span_bug(span, "not exactly 2 arguments in `deriving(Ord)`")
             } else {
diff --git a/src/libsyntax/ext/deriving/decodable.rs b/src/libsyntax/ext/deriving/decodable.rs
index c0631b8350b..8094f0d3de8 100644
--- a/src/libsyntax/ext/deriving/decodable.rs
+++ b/src/libsyntax/ext/deriving/decodable.rs
@@ -76,7 +76,7 @@ fn expand_deriving_decodable_imp<F>(cx: &mut ExtCtxt,
                     true
                 )),
                 attributes: Vec::new(),
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     decodable_substructure(a, b, c, krate)
                 }),
             })
diff --git a/src/libsyntax/ext/deriving/default.rs b/src/libsyntax/ext/deriving/default.rs
index 49bcb26a4c2..047c4fef3c4 100644
--- a/src/libsyntax/ext/deriving/default.rs
+++ b/src/libsyntax/ext/deriving/default.rs
@@ -40,7 +40,7 @@ pub fn expand_deriving_default<F>(cx: &mut ExtCtxt,
                 args: Vec::new(),
                 ret_ty: Self,
                 attributes: attrs,
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     default_substructure(a, b, c)
                 })
             })
diff --git a/src/libsyntax/ext/deriving/encodable.rs b/src/libsyntax/ext/deriving/encodable.rs
index 4323d2979cc..0fceb0fbfda 100644
--- a/src/libsyntax/ext/deriving/encodable.rs
+++ b/src/libsyntax/ext/deriving/encodable.rs
@@ -152,7 +152,7 @@ fn expand_deriving_encodable_imp<F>(cx: &mut ExtCtxt,
                     true
                 )),
                 attributes: Vec::new(),
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     encodable_substructure(a, b, c)
                 }),
             })
diff --git a/src/libsyntax/ext/deriving/generic/mod.rs b/src/libsyntax/ext/deriving/generic/mod.rs
index 459abf15b33..1fb8189c63c 100644
--- a/src/libsyntax/ext/deriving/generic/mod.rs
+++ b/src/libsyntax/ext/deriving/generic/mod.rs
@@ -312,7 +312,7 @@ pub enum SubstructureFields<'a> {
 /// Combine the values of all the fields together. The last argument is
 /// all the fields of all the structures.
 pub type CombineSubstructureFunc<'a> =
-    |&mut ExtCtxt, Span, &Substructure|: 'a -> P<Expr>;
+    Box<FnMut(&mut ExtCtxt, Span, &Substructure) -> P<Expr> + 'a>;
 
 /// Deal with non-matching enum variants.  The tuple is a list of
 /// identifiers (one for each `Self` argument, which could be any of the
@@ -320,11 +320,7 @@ pub type CombineSubstructureFunc<'a> =
 /// holding the variant index value for each of the `Self` arguments.  The
 /// last argument is all the non-`Self` args of the method being derived.
 pub type EnumNonMatchCollapsedFunc<'a> =
-    |&mut ExtCtxt,
-     Span,
-     (&[Ident], &[Ident]),
-     &[P<Expr>]|: 'a
-     -> P<Expr>;
+    Box<FnMut(&mut ExtCtxt, Span, (&[Ident], &[Ident]), &[P<Expr>]) -> P<Expr> + 'a>;
 
 pub fn combine_substructure<'a>(f: CombineSubstructureFunc<'a>)
     -> RefCell<CombineSubstructureFunc<'a>> {
@@ -606,7 +602,7 @@ impl<'a> MethodDef<'a> {
         };
         let mut f = self.combine_substructure.borrow_mut();
         let f: &mut CombineSubstructureFunc = &mut *f;
-        (*f)(cx, trait_.span, &substructure)
+        f.call_mut((cx, trait_.span, &substructure))
     }
 
     fn get_ret_ty(&self,
@@ -1341,7 +1337,7 @@ impl<'a> TraitDef<'a> {
 pub fn cs_fold<F>(use_foldl: bool,
                   mut f: F,
                   base: P<Expr>,
-                  enum_nonmatch_f: EnumNonMatchCollapsedFunc,
+                  mut enum_nonmatch_f: EnumNonMatchCollapsedFunc,
                   cx: &mut ExtCtxt,
                   trait_span: Span,
                   substructure: &Substructure)
@@ -1369,8 +1365,8 @@ pub fn cs_fold<F>(use_foldl: bool,
             }
         },
         EnumNonMatchingCollapsed(ref all_args, _, tuple) =>
-            enum_nonmatch_f(cx, trait_span, (all_args[], tuple),
-                            substructure.nonself_args),
+            enum_nonmatch_f.call_mut((cx, trait_span, (all_args[], tuple),
+                                      substructure.nonself_args)),
         StaticEnum(..) | StaticStruct(..) => {
             cx.span_bug(trait_span, "static function in `derive`")
         }
@@ -1387,7 +1383,7 @@ pub fn cs_fold<F>(use_foldl: bool,
 /// ```
 #[inline]
 pub fn cs_same_method<F>(f: F,
-                         enum_nonmatch_f: EnumNonMatchCollapsedFunc,
+                         mut enum_nonmatch_f: EnumNonMatchCollapsedFunc,
                          cx: &mut ExtCtxt,
                          trait_span: Span,
                          substructure: &Substructure)
@@ -1409,8 +1405,8 @@ pub fn cs_same_method<F>(f: F,
             f(cx, trait_span, called)
         },
         EnumNonMatchingCollapsed(ref all_self_args, _, tuple) =>
-            enum_nonmatch_f(cx, trait_span, (all_self_args[], tuple),
-                            substructure.nonself_args),
+            enum_nonmatch_f.call_mut((cx, trait_span, (all_self_args[], tuple),
+                                     substructure.nonself_args)),
         StaticEnum(..) | StaticStruct(..) => {
             cx.span_bug(trait_span, "static function in `derive`")
         }
diff --git a/src/libsyntax/ext/deriving/hash.rs b/src/libsyntax/ext/deriving/hash.rs
index 9ff42d85cfb..b9acde4bf6b 100644
--- a/src/libsyntax/ext/deriving/hash.rs
+++ b/src/libsyntax/ext/deriving/hash.rs
@@ -55,7 +55,7 @@ pub fn expand_deriving_hash<F>(cx: &mut ExtCtxt,
                 args: vec!(Ptr(box Literal(args), Borrowed(None, MutMutable))),
                 ret_ty: nil_ty(),
                 attributes: attrs,
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     hash_substructure(a, b, c)
                 })
             }
diff --git a/src/libsyntax/ext/deriving/primitive.rs b/src/libsyntax/ext/deriving/primitive.rs
index 8abd846373a..d36bb2cd1c2 100644
--- a/src/libsyntax/ext/deriving/primitive.rs
+++ b/src/libsyntax/ext/deriving/primitive.rs
@@ -46,7 +46,7 @@ pub fn expand_deriving_from_primitive<F>(cx: &mut ExtCtxt,
                                            true)),
                 // #[inline] liable to cause code-bloat
                 attributes: attrs.clone(),
-                combine_substructure: combine_substructure(|c, s, sub| {
+                combine_substructure: combine_substructure(box |c, s, sub| {
                     cs_from("i64", c, s, sub)
                 }),
             },
@@ -62,7 +62,7 @@ pub fn expand_deriving_from_primitive<F>(cx: &mut ExtCtxt,
                                            true)),
                 // #[inline] liable to cause code-bloat
                 attributes: attrs,
-                combine_substructure: combine_substructure(|c, s, sub| {
+                combine_substructure: combine_substructure(box |c, s, sub| {
                     cs_from("u64", c, s, sub)
                 }),
             })
diff --git a/src/libsyntax/ext/deriving/rand.rs b/src/libsyntax/ext/deriving/rand.rs
index 1ddf5b2a5c3..5517019f804 100644
--- a/src/libsyntax/ext/deriving/rand.rs
+++ b/src/libsyntax/ext/deriving/rand.rs
@@ -45,7 +45,7 @@ pub fn expand_deriving_rand<F>(cx: &mut ExtCtxt,
                 ),
                 ret_ty: Self,
                 attributes: Vec::new(),
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     rand_substructure(a, b, c)
                 })
             }
diff --git a/src/libsyntax/ext/deriving/show.rs b/src/libsyntax/ext/deriving/show.rs
index 0513c75cf57..eceac4e9a83 100644
--- a/src/libsyntax/ext/deriving/show.rs
+++ b/src/libsyntax/ext/deriving/show.rs
@@ -46,7 +46,7 @@ pub fn expand_deriving_show<F>(cx: &mut ExtCtxt,
                 args: vec!(fmtr),
                 ret_ty: Literal(Path::new(vec!("std", "fmt", "Result"))),
                 attributes: Vec::new(),
-                combine_substructure: combine_substructure(|a, b, c| {
+                combine_substructure: combine_substructure(box |a, b, c| {
                     show_substructure(a, b, c)
                 })
             }