rollup merge of #23282: nikomatsakis/fn-trait-inheritance

The primary motivation here is to sidestep #19032 -- for a time, I thought that we should improve coherence or otherwise extend the language, but I now think that any such changes will require more time to bake. In the meantime, inheritance amongst the fn traits is both logically correct *and* a simple solution to that obstacle. This change introduces inheritance and modifies the compiler so that it can properly generate impls for closures and fns.

Things enabled by this PR (but not included in this PR):

1. An impl of `FnMut` for `&mut F` where `F : FnMut` (https://github.com/rust-lang/rust/issues/23015).
2. A better version of `Thunk` I've been calling `FnBox`.

I did not include either of these in the PR because:

1. Adding the impls in 1 currently induces a coherence conflict with the pattern trait. This is interesting and merits some discussion.
2. `FnBox` deserves to be a PR of its own.

The main downside to this design is (a) the need to write impls by hand; (b) the possibility of implementing `FnMut` with different semantics from `Fn`, etc. Point (a) is minor -- in particular, it does not affect normal closure usage -- and could be addressed in the future in many ways (better defaults; convenient macros; specialization; etc). Point (b) is unfortunate but "just a bug" from my POV, and certainly not unique to these traits (c.f. Copy/Clone, PartialEq/Eq, etc). (Until we lift the feature-gate on implementing the Fn traits, in any case, there is room to correct both of these if we find a nice way.)

Note that I believe this change is reversible in the future if we decide on another course of action, due to the feature gate on implementing the `Fn` traits, though I do not (currently) think we should reverse it.

Fixes #18835.

r? @nrc

40 files changed, 711 insertions, 261 deletions

diff --git a/src/libcollectionstest/btree/set.rs b/src/libcollectionstest/btree/set.rs
index 488f0d756d3..234cd6e0fd2 100644
--- a/src/libcollectionstest/btree/set.rs
+++ b/src/libcollectionstest/btree/set.rs
@@ -43,8 +43,6 @@ struct Counter<'a, 'b> {
 }
 
 impl<'a, 'b, 'c> FnMut<(&'c i32,)> for Counter<'a, 'b> {
-    type Output = bool;
-
     extern "rust-call" fn call_mut(&mut self, (&x,): (&'c i32,)) -> bool {
         assert_eq!(x, self.expected[*self.i]);
         *self.i += 1;
@@ -52,6 +50,14 @@ impl<'a, 'b, 'c> FnMut<(&'c i32,)> for Counter<'a, 'b> {
     }
 }
 
+impl<'a, 'b, 'c> FnOnce<(&'c i32,)> for Counter<'a, 'b> {
+    type Output = bool;
+
+    extern "rust-call" fn call_once(mut self, args: (&'c i32,)) -> bool {
+        self.call_mut(args)
+    }
+}
+
 fn check<F>(a: &[i32], b: &[i32], expected: &[i32], f: F) where
     // FIXME Replace Counter with `Box<FnMut(_) -> _>`
     F: FnOnce(&BTreeSet<i32>, &BTreeSet<i32>, Counter) -> bool,
diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs
index 6e6f97a7af7..fee40115f39 100644
--- a/src/libcore/ops.rs
+++ b/src/libcore/ops.rs
@@ -1148,6 +1148,7 @@ impl<'a, T: ?Sized> DerefMut for &'a mut T {
 #[lang="fn"]
 #[stable(feature = "rust1", since = "1.0.0")]
 #[rustc_paren_sugar]
+#[cfg(stage0)]
 pub trait Fn<Args> {
     /// The returned type after the call operator is used.
     type Output;
@@ -1156,10 +1157,21 @@ pub trait Fn<Args> {
     extern "rust-call" fn call(&self, args: Args) -> Self::Output;
 }
 
+/// A version of the call operator that takes an immutable receiver.
+#[lang="fn"]
+#[stable(feature = "rust1", since = "1.0.0")]
+#[rustc_paren_sugar]
+#[cfg(not(stage0))]
+pub trait Fn<Args> : FnMut<Args> {
+    /// This is called when the call operator is used.
+    extern "rust-call" fn call(&self, args: Args) -> Self::Output;
+}
+
 /// A version of the call operator that takes a mutable receiver.
 #[lang="fn_mut"]
 #[stable(feature = "rust1", since = "1.0.0")]
 #[rustc_paren_sugar]
+#[cfg(stage0)]
 pub trait FnMut<Args> {
     /// The returned type after the call operator is used.
     type Output;
@@ -1168,6 +1180,16 @@ pub trait FnMut<Args> {
     extern "rust-call" fn call_mut(&mut self, args: Args) -> Self::Output;
 }
 
+/// A version of the call operator that takes a mutable receiver.
+#[lang="fn_mut"]
+#[stable(feature = "rust1", since = "1.0.0")]
+#[rustc_paren_sugar]
+#[cfg(not(stage0))]
+pub trait FnMut<Args> : FnOnce<Args> {
+    /// This is called when the call operator is used.
+    extern "rust-call" fn call_mut(&mut self, args: Args) -> Self::Output;
+}
+
 /// A version of the call operator that takes a by-value receiver.
 #[lang="fn_once"]
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1180,6 +1202,7 @@ pub trait FnOnce<Args> {
     extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
 }
 
+#[cfg(stage0)]
 impl<F: ?Sized, A> FnMut<A> for F
     where F : Fn<A>
 {
@@ -1190,6 +1213,7 @@ impl<F: ?Sized, A> FnMut<A> for F
     }
 }
 
+#[cfg(stage0)]
 impl<F,A> FnOnce<A> for F
     where F : FnMut<A>
 {
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index b7285d30a73..7197649a0ea 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -29,7 +29,7 @@ use iter::{Map, Iterator, IteratorExt, DoubleEndedIterator};
 use marker::Sized;
 use mem;
 use num::Int;
-use ops::{Fn, FnMut};
+use ops::{Fn, FnMut, FnOnce};
 use option::Option::{self, None, Some};
 use raw::{Repr, Slice};
 use result::Result::{self, Ok, Err};
@@ -541,6 +541,7 @@ delegate_iter!{exact u8 : Bytes<'a>}
 #[derive(Copy, Clone)]
 struct BytesDeref;
 
+#[cfg(stage0)]
 impl<'a> Fn<(&'a u8,)> for BytesDeref {
     type Output = u8;
 
@@ -550,6 +551,32 @@ impl<'a> Fn<(&'a u8,)> for BytesDeref {
     }
 }
 
+#[cfg(not(stage0))]
+impl<'a> Fn<(&'a u8,)> for BytesDeref {
+    #[inline]
+    extern "rust-call" fn call(&self, (ptr,): (&'a u8,)) -> u8 {
+        *ptr
+    }
+}
+
+#[cfg(not(stage0))]
+impl<'a> FnMut<(&'a u8,)> for BytesDeref {
+    #[inline]
+    extern "rust-call" fn call_mut(&mut self, (ptr,): (&'a u8,)) -> u8 {
+        Fn::call(&*self, (ptr,))
+    }
+}
+
+#[cfg(not(stage0))]
+impl<'a> FnOnce<(&'a u8,)> for BytesDeref {
+    type Output = u8;
+
+    #[inline]
+    extern "rust-call" fn call_once(self, (ptr,): (&'a u8,)) -> u8 {
+        Fn::call(&self, (ptr,))
+    }
+}
+
 /// An iterator over the substrings of a string, separated by `sep`.
 struct CharSplits<'a, P: Pattern<'a>> {
     /// The slice remaining to be iterated
diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs
index 92d54887308..2232bb7bcdb 100644
--- a/src/librustc/middle/traits/project.rs
+++ b/src/librustc/middle/traits/project.rs
@@ -789,10 +789,13 @@ fn confirm_callable_candidate<'cx,'tcx>(
            obligation.repr(tcx),
            fn_sig.repr(tcx));
 
+    // the `Output` associated type is declared on `FnOnce`
+    let fn_once_def_id = tcx.lang_items.fn_once_trait().unwrap();
+
     // Note: we unwrap the binder here but re-create it below (1)
     let ty::Binder((trait_ref, ret_type)) =
         util::closure_trait_ref_and_return_type(tcx,
-                                                obligation.predicate.trait_ref.def_id,
+                                                fn_once_def_id,
                                                 obligation.predicate.trait_ref.self_ty(),
                                                 fn_sig,
                                                 flag);
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 9878661c9f6..0d6a1f7df5e 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -1069,7 +1069,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         match self.closure_typer.closure_kind(closure_def_id) {
             Some(closure_kind) => {
                 debug!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind);
-                if closure_kind == kind {
+                if closure_kind.extends(kind) {
                     candidates.vec.push(ClosureCandidate(closure_def_id, substs.clone()));
                 }
             }
@@ -1088,10 +1088,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                       candidates: &mut SelectionCandidateSet<'tcx>)
                                       -> Result<(),SelectionError<'tcx>>
     {
-        // We provide a `Fn` impl for fn pointers. There is no need to provide
-        // the other traits (e.g. `FnMut`) since those are provided by blanket
-        // impls.
-        if Some(obligation.predicate.def_id()) != self.tcx().lang_items.fn_trait() {
+        // We provide impl of all fn traits for fn pointers.
+        if self.tcx().lang_items.fn_trait_kind(obligation.predicate.def_id()).is_none() {
             return Ok(());
         }
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index e5e89c3fbd4..5e3f430615a 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -2462,8 +2462,11 @@ pub struct ItemSubsts<'tcx> {
     pub substs: Substs<'tcx>,
 }
 
-#[derive(Clone, Copy, PartialEq, Eq, Debug, RustcEncodable, RustcDecodable)]
+#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Debug, RustcEncodable, RustcDecodable)]
 pub enum ClosureKind {
+    // Warning: Ordering is significant here! The ordering is chosen
+    // because the trait Fn is a subtrait of FnMut and so in turn, and
+    // hence we order it so that Fn < FnMut < FnOnce.
     FnClosureKind,
     FnMutClosureKind,
     FnOnceClosureKind,
@@ -2485,6 +2488,20 @@ impl ClosureKind {
             Err(err) => cx.sess.fatal(&err[..]),
         }
     }
+
+    /// True if this a type that impls this closure kind
+    /// must also implement `other`.
+    pub fn extends(self, other: ty::ClosureKind) -> bool {
+        match (self, other) {
+            (FnClosureKind, FnClosureKind) => true,
+            (FnClosureKind, FnMutClosureKind) => true,
+            (FnClosureKind, FnOnceClosureKind) => true,
+            (FnMutClosureKind, FnMutClosureKind) => true,
+            (FnMutClosureKind, FnOnceClosureKind) => true,
+            (FnOnceClosureKind, FnOnceClosureKind) => true,
+            _ => false,
+        }
+    }
 }
 
 pub trait ClosureTyper<'tcx> {
diff --git a/src/librustc_trans/trans/callee.rs b/src/librustc_trans/trans/callee.rs
index 088a34857e7..e7911d5cc19 100644
--- a/src/librustc_trans/trans/callee.rs
+++ b/src/librustc_trans/trans/callee.rs
@@ -264,14 +264,29 @@ fn trans_fn_ref_with_substs_to_callee<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 /// but for the bare function type given.
 pub fn trans_fn_pointer_shim<'a, 'tcx>(
     ccx: &'a CrateContext<'a, 'tcx>,
+    closure_kind: ty::ClosureKind,
     bare_fn_ty: Ty<'tcx>)
     -> ValueRef
 {
     let _icx = push_ctxt("trans_fn_pointer_shim");
     let tcx = ccx.tcx();
 
+    // Normalize the type for better caching.
     let bare_fn_ty = common::erase_regions(tcx, &bare_fn_ty);
-    match ccx.fn_pointer_shims().borrow().get(&bare_fn_ty) {
+
+    // If this is an impl of `Fn` or `FnMut` trait, the receiver is `&self`.
+    let is_by_ref = match closure_kind {
+        ty::FnClosureKind | ty::FnMutClosureKind => true,
+        ty::FnOnceClosureKind => false,
+    };
+    let bare_fn_ty_maybe_ref = if is_by_ref {
+        ty::mk_imm_rptr(tcx, tcx.mk_region(ty::ReStatic), bare_fn_ty)
+    } else {
+        bare_fn_ty
+    };
+
+    // Check if we already trans'd this shim.
+    match ccx.fn_pointer_shims().borrow().get(&bare_fn_ty_maybe_ref) {
         Some(&llval) => { return llval; }
         None => { }
     }
@@ -279,9 +294,6 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
     debug!("trans_fn_pointer_shim(bare_fn_ty={})",
            bare_fn_ty.repr(tcx));
 
-    // This is an impl of `Fn` trait, so receiver is `&self`.
-    let bare_fn_ty_ref = ty::mk_imm_rptr(tcx, tcx.mk_region(ty::ReStatic), bare_fn_ty);
-
     // Construct the "tuply" version of `bare_fn_ty`. It takes two arguments: `self`,
     // which is the fn pointer, and `args`, which is the arguments tuple.
     let (opt_def_id, sig) =
@@ -306,7 +318,7 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
                                          unsafety: ast::Unsafety::Normal,
                                          abi: synabi::RustCall,
                                          sig: ty::Binder(ty::FnSig {
-                                             inputs: vec![bare_fn_ty_ref,
+                                             inputs: vec![bare_fn_ty_maybe_ref,
                                                           tuple_input_ty],
                                              output: sig.output,
                                              variadic: false
@@ -337,8 +349,11 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
     let mut bcx = init_function(&fcx, false, sig.output);
 
     // the first argument (`self`) will be ptr to the the fn pointer
-    let llfnpointer =
-        Load(bcx, get_param(fcx.llfn, fcx.arg_pos(0) as u32));
+    let llfnpointer = if is_by_ref {
+        Load(bcx, get_param(fcx.llfn, fcx.arg_pos(0) as u32))
+    } else {
+        get_param(fcx.llfn, fcx.arg_pos(0) as u32)
+    };
 
     // the remaining arguments will be the untupled values
     let llargs: Vec<_> =
@@ -361,7 +376,7 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
 
     finish_fn(&fcx, bcx, sig.output, DebugLoc::None);
 
-    ccx.fn_pointer_shims().borrow_mut().insert(bare_fn_ty, llfn);
+    ccx.fn_pointer_shims().borrow_mut().insert(bare_fn_ty_maybe_ref, llfn);
 
     llfn
 }
diff --git a/src/librustc_trans/trans/closure.rs b/src/librustc_trans/trans/closure.rs
index c1bc7219ad8..5a48b8e4bce 100644
--- a/src/librustc_trans/trans/closure.rs
+++ b/src/librustc_trans/trans/closure.rs
@@ -8,24 +8,27 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use back::link::mangle_internal_name_by_path_and_seq;
-use llvm::ValueRef;
+use arena::TypedArena;
+use back::link::{self, mangle_internal_name_by_path_and_seq};
+use llvm::{ValueRef, get_param};
 use middle::mem_categorization::Typer;
 use trans::adt;
 use trans::base::*;
 use trans::build::*;
-use trans::cleanup::{CleanupMethods, ScopeId};
+use trans::callee::{self, ArgVals, Callee, TraitItem, MethodData};
+use trans::cleanup::{CleanupMethods, CustomScope, ScopeId};
 use trans::common::*;
-use trans::datum::{Datum, rvalue_scratch_datum};
-use trans::datum::{Rvalue, ByValue};
-use trans::debuginfo;
+use trans::datum::{self, Datum, rvalue_scratch_datum, Rvalue, ByValue};
+use trans::debuginfo::{self, DebugLoc};
 use trans::expr;
 use trans::monomorphize::{self, MonoId};
 use trans::type_of::*;
 use middle::ty::{self, ClosureTyper};
 use middle::subst::{Substs};
 use session::config::FullDebugInfo;
+use util::ppaux::Repr;
 
+use syntax::abi::RustCall;
 use syntax::ast;
 use syntax::ast_util;
 
@@ -239,11 +242,7 @@ pub fn trans_closure_expr<'a, 'tcx>(dest: Dest<'a, 'tcx>,
     // Create the closure.
     for (i, freevar) in freevars.iter().enumerate() {
         let datum = expr::trans_local_var(bcx, freevar.def);
-        let upvar_slot_dest = adt::trans_field_ptr(bcx,
-                                                   &*repr,
-                                                   dest_addr,
-                                                   0,
-                                                   i);
+        let upvar_slot_dest = adt::trans_field_ptr(bcx, &*repr, dest_addr, 0, i);
         let upvar_id = ty::UpvarId { var_id: freevar.def.local_node_id(),
                                      closure_expr_id: id };
         match tcx.upvar_capture(upvar_id).unwrap() {
@@ -259,3 +258,186 @@ pub fn trans_closure_expr<'a, 'tcx>(dest: Dest<'a, 'tcx>,
 
     Some(bcx)
 }
+
+pub fn trans_closure_method<'a, 'tcx>(ccx: &'a CrateContext<'a, 'tcx>,
+                                      closure_def_id: ast::DefId,
+                                      substs: Substs<'tcx>,
+                                      node: ExprOrMethodCall,
+                                      param_substs: &'tcx Substs<'tcx>,
+                                      trait_closure_kind: ty::ClosureKind)
+                                      -> ValueRef
+{
+    // The substitutions should have no type parameters remaining
+    // after passing through fulfill_obligation
+    let llfn = callee::trans_fn_ref_with_substs(ccx,
+                                                closure_def_id,
+                                                node,
+                                                param_substs,
+                                                substs.clone()).val;
+
+    // If the closure is a Fn closure, but a FnOnce is needed (etc),
+    // then adapt the self type
+    let closure_kind = ccx.tcx().closure_kind(closure_def_id);
+    trans_closure_adapter_shim(ccx,
+                               closure_def_id,
+                               substs,
+                               closure_kind,
+                               trait_closure_kind,
+                               llfn)
+}
+
+fn trans_closure_adapter_shim<'a, 'tcx>(
+    ccx: &'a CrateContext<'a, 'tcx>,
+    closure_def_id: ast::DefId,
+    substs: Substs<'tcx>,
+    llfn_closure_kind: ty::ClosureKind,
+    trait_closure_kind: ty::ClosureKind,
+    llfn: ValueRef)
+    -> ValueRef
+{
+    let _icx = push_ctxt("trans_closure_adapter_shim");
+    let tcx = ccx.tcx();
+
+    debug!("trans_closure_adapter_shim(llfn_closure_kind={:?}, \
+           trait_closure_kind={:?}, \
+           llfn={})",
+           llfn_closure_kind,
+           trait_closure_kind,
+           ccx.tn().val_to_string(llfn));
+
+    match (llfn_closure_kind, trait_closure_kind) {
+        (ty::FnClosureKind, ty::FnClosureKind) |
+        (ty::FnMutClosureKind, ty::FnMutClosureKind) |
+        (ty::FnOnceClosureKind, ty::FnOnceClosureKind) => {
+            // No adapter needed.
+            llfn
+        }
+        (ty::FnClosureKind, ty::FnMutClosureKind) => {
+            // The closure fn `llfn` is a `fn(&self, ...)`.  We want a
+            // `fn(&mut self, ...)`. In fact, at trans time, these are
+            // basically the same thing, so we can just return llfn.
+            llfn
+        }
+        (ty::FnClosureKind, ty::FnOnceClosureKind) |
+        (ty::FnMutClosureKind, ty::FnOnceClosureKind) => {
+            // The closure fn `llfn` is a `fn(&self, ...)` or `fn(&mut
+            // self, ...)`.  We want a `fn(self, ...)`. We can produce
+            // this by doing something like:
+            //
+            //     fn call_once(self, ...) { call_mut(&self, ...) }
+            //     fn call_once(mut self, ...) { call_mut(&mut self, ...) }
+            //
+            // These are both the same at trans time.
+            trans_fn_once_adapter_shim(ccx, closure_def_id, substs, llfn)
+        }
+        _ => {
+            tcx.sess.bug(&format!("trans_closure_adapter_shim: cannot convert {:?} to {:?}",
+                                  llfn_closure_kind,
+                                  trait_closure_kind));
+        }
+    }
+}
+
+fn trans_fn_once_adapter_shim<'a, 'tcx>(
+    ccx: &'a CrateContext<'a, 'tcx>,
+    closure_def_id: ast::DefId,
+    substs: Substs<'tcx>,
+    llreffn: ValueRef)
+    -> ValueRef
+{
+    debug!("trans_fn_once_adapter_shim(closure_def_id={}, substs={}, llreffn={})",
+           closure_def_id.repr(ccx.tcx()),
+           substs.repr(ccx.tcx()),
+           ccx.tn().val_to_string(llreffn));
+
+    let tcx = ccx.tcx();
+    let typer = NormalizingClosureTyper::new(tcx);
+
+    // Find a version of the closure type. Substitute static for the
+    // region since it doesn't really matter.
+    let substs = tcx.mk_substs(substs);
+    let closure_ty = ty::mk_closure(tcx, closure_def_id, substs);
+    let ref_closure_ty = ty::mk_imm_rptr(tcx, tcx.mk_region(ty::ReStatic), closure_ty);
+
+    // Make a version with the type of by-ref closure.
+    let ty::ClosureTy { unsafety, abi, mut sig } = typer.closure_type(closure_def_id, substs);
+    sig.0.inputs.insert(0, ref_closure_ty); // sig has no self type as of yet
+    let llref_bare_fn_ty = tcx.mk_bare_fn(ty::BareFnTy { unsafety: unsafety,
+                                                               abi: abi,
+                                                               sig: sig.clone() });
+    let llref_fn_ty = ty::mk_bare_fn(tcx, None, llref_bare_fn_ty);
+    debug!("trans_fn_once_adapter_shim: llref_fn_ty={}",
+           llref_fn_ty.repr(tcx));
+
+    // Make a version of the closure type with the same arguments, but
+    // with argument #0 being by value.
+    assert_eq!(abi, RustCall);
+    sig.0.inputs[0] = closure_ty;
+    let llonce_bare_fn_ty = tcx.mk_bare_fn(ty::BareFnTy { unsafety: unsafety,
+                                                                abi: abi,
+                                                                sig: sig });
+    let llonce_fn_ty = ty::mk_bare_fn(tcx, None, llonce_bare_fn_ty);
+
+    // Create the by-value helper.
+    let function_name = link::mangle_internal_name_by_type_and_seq(ccx, llonce_fn_ty, "once_shim");
+    let lloncefn = decl_internal_rust_fn(ccx, llonce_fn_ty, &function_name);
+
+    let sig = ty::erase_late_bound_regions(tcx, &llonce_bare_fn_ty.sig);
+    let (block_arena, fcx): (TypedArena<_>, FunctionContext);
+    block_arena = TypedArena::new();
+    fcx = new_fn_ctxt(ccx,
+                      lloncefn,
+                      ast::DUMMY_NODE_ID,
+                      false,
+                      sig.output,
+                      substs,
+                      None,
+                      &block_arena);
+    let mut bcx = init_function(&fcx, false, sig.output);
+
+    // the first argument (`self`) will be the (by value) closure env.
+    let self_scope = fcx.push_custom_cleanup_scope();
+    let self_scope_id = CustomScope(self_scope);
+    let rvalue_mode = datum::appropriate_rvalue_mode(ccx, closure_ty);
+    let llself = get_param(lloncefn, fcx.arg_pos(0) as u32);
+    let env_datum = Datum::new(llself, closure_ty, Rvalue::new(rvalue_mode));
+    let env_datum = unpack_datum!(bcx,
+                                  env_datum.to_lvalue_datum_in_scope(bcx, "self",
+                                                                     self_scope_id));
+
+    debug!("trans_fn_once_adapter_shim: env_datum={}",
+           bcx.val_to_string(env_datum.val));
+
+    // the remaining arguments will be packed up in a tuple.
+    let input_tys = match sig.inputs[1].sty {
+        ty::ty_tup(ref tys) => &**tys,
+        _ => bcx.sess().bug(&format!("trans_fn_once_adapter_shim: not rust-call! \
+                                      closure_def_id={}",
+                                     closure_def_id.repr(tcx)))
+    };
+    let llargs: Vec<_> =
+        input_tys.iter()
+                 .enumerate()
+                 .map(|(i, _)| get_param(lloncefn, fcx.arg_pos(i+1) as u32))
+                 .collect();
+
+    let dest =
+        fcx.llretslotptr.get().map(
+            |_| expr::SaveIn(fcx.get_ret_slot(bcx, sig.output, "ret_slot")));
+
+    let callee_data = TraitItem(MethodData { llfn: llreffn,
+                                             llself: env_datum.val });
+
+    bcx = callee::trans_call_inner(bcx,
+                                   DebugLoc::None,
+                                   llref_fn_ty,
+                                   |bcx, _| Callee { bcx: bcx, data: callee_data },
+                                   ArgVals(&llargs),
+                                   dest).bcx;
+
+    fcx.pop_custom_cleanup_scope(self_scope);
+
+    finish_fn(&fcx, bcx, sig.output, DebugLoc::None);
+
+    lloncefn
+}
diff --git a/src/librustc_trans/trans/meth.rs b/src/librustc_trans/trans/meth.rs
index 4da17972c55..aa038f8ddca 100644
--- a/src/librustc_trans/trans/meth.rs
+++ b/src/librustc_trans/trans/meth.rs
@@ -17,11 +17,13 @@ use middle::subst::Substs;
 use middle::subst::VecPerParamSpace;
 use middle::subst;
 use middle::traits;
+use middle::ty::ClosureTyper;
 use trans::base::*;
 use trans::build::*;
 use trans::callee::*;
 use trans::callee;
 use trans::cleanup;
+use trans::closure;
 use trans::common::*;
 use trans::consts;
 use trans::datum::*;
@@ -358,19 +360,21 @@ fn trans_monomorphized_callee<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
         traits::VtableClosure(closure_def_id, substs) => {
             // The substitutions should have no type parameters remaining
             // after passing through fulfill_obligation
-            let llfn = trans_fn_ref_with_substs(bcx.ccx(),
-                                                closure_def_id,
-                                                MethodCallKey(method_call),
-                                                bcx.fcx.param_substs,
-                                                substs).val;
-
+            let trait_closure_kind = bcx.tcx().lang_items.fn_trait_kind(trait_id).unwrap();
+            let llfn = closure::trans_closure_method(bcx.ccx(),
+                                                     closure_def_id,
+                                                     substs,
+                                                     MethodCallKey(method_call),
+                                                     bcx.fcx.param_substs,
+                                                     trait_closure_kind);
             Callee {
                 bcx: bcx,
                 data: Fn(llfn),
             }
         }
         traits::VtableFnPointer(fn_ty) => {
-            let llfn = trans_fn_pointer_shim(bcx.ccx(), fn_ty);
+            let trait_closure_kind = bcx.tcx().lang_items.fn_trait_kind(trait_id).unwrap();
+            let llfn = trans_fn_pointer_shim(bcx.ccx(), trait_closure_kind, fn_ty);
             Callee { bcx: bcx, data: Fn(llfn) }
         }
         traits::VtableObject(ref data) => {
@@ -645,9 +649,6 @@ pub fn trans_object_shim<'a, 'tcx>(
 
     assert!(!fcx.needs_ret_allocas);
 
-    let sig =
-        ty::erase_late_bound_regions(bcx.tcx(), &fty.sig);
-
     let dest =
         fcx.llretslotptr.get().map(
             |_| expr::SaveIn(fcx.get_ret_slot(bcx, sig.output, "ret_slot")));
@@ -714,17 +715,18 @@ pub fn get_vtable<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                 emit_vtable_methods(ccx, id, substs, param_substs).into_iter()
             }
             traits::VtableClosure(closure_def_id, substs) => {
-                let llfn = trans_fn_ref_with_substs(
-                    ccx,
-                    closure_def_id,
-                    ExprId(0),
-                    param_substs,
-                    substs).val;
-
+                let trait_closure_kind = tcx.lang_items.fn_trait_kind(trait_ref.def_id()).unwrap();
+                let llfn = closure::trans_closure_method(ccx,
+                                                         closure_def_id,
+                                                         substs,
+                                                         ExprId(0),
+                                                         param_substs,
+                                                         trait_closure_kind);
                 vec![llfn].into_iter()
             }
             traits::VtableFnPointer(bare_fn_ty) => {
-                vec![trans_fn_pointer_shim(ccx, bare_fn_ty)].into_iter()
+                let trait_closure_kind = tcx.lang_items.fn_trait_kind(trait_ref.def_id()).unwrap();
+                vec![trans_fn_pointer_shim(ccx, trait_closure_kind, bare_fn_ty)].into_iter()
             }
             traits::VtableObject(ref data) => {
                 // this would imply that the Self type being erased is
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 71900855266..e9de8bd879e 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -55,7 +55,7 @@ use middle::resolve_lifetime as rl;
 use middle::privacy::{AllPublic, LastMod};
 use middle::subst::{FnSpace, TypeSpace, SelfSpace, Subst, Substs};
 use middle::traits;
-use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty};
+use middle::ty::{self, RegionEscape, Ty};
 use rscope::{self, UnelidableRscope, RegionScope, ElidableRscope,
              ObjectLifetimeDefaultRscope, ShiftedRscope, BindingRscope};
 use util::common::{ErrorReported, FN_OUTPUT_NAME};
@@ -608,24 +608,16 @@ pub fn instantiate_poly_trait_ref<'tcx>(
     poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
     -> ty::PolyTraitRef<'tcx>
 {
-    let mut projections = Vec::new();
-
-    // The trait reference introduces a binding level here, so
-    // we need to shift the `rscope`. It'd be nice if we could
-    // do away with this rscope stuff and work this knowledge
-    // into resolve_lifetimes, as we do with non-omitted
-    // lifetimes. Oh well, not there yet.
-    let shifted_rscope = ShiftedRscope::new(rscope);
-
-    let trait_ref = instantiate_trait_ref(this, &shifted_rscope,
-                                          &ast_trait_ref.trait_ref,
-                                          None, self_ty, Some(&mut projections));
-
-    for projection in projections {
-        poly_projections.push(ty::Binder(projection));
-    }
-
-    ty::Binder(trait_ref)
+    let trait_ref = &ast_trait_ref.trait_ref;
+    let trait_def_id = trait_def_id(this, trait_ref);
+    ast_path_to_poly_trait_ref(this,
+                               rscope,
+                               trait_ref.path.span,
+                               PathParamMode::Explicit,
+                               trait_def_id,
+                               self_ty,
+                               trait_ref.path.segments.last().unwrap(),
+                               poly_projections)
 }
 
 /// Instantiates the path for the given trait reference, assuming that it's
@@ -634,31 +626,27 @@ pub fn instantiate_poly_trait_ref<'tcx>(
 ///
 /// If the `projections` argument is `None`, then assoc type bindings like `Foo<T=X>`
 /// are disallowed. Otherwise, they are pushed onto the vector given.
-pub fn instantiate_trait_ref<'tcx>(
+pub fn instantiate_mono_trait_ref<'tcx>(
     this: &AstConv<'tcx>,
     rscope: &RegionScope,
     trait_ref: &ast::TraitRef,
-    impl_id: Option<ast::NodeId>,
-    self_ty: Option<Ty<'tcx>>,
-    projections: Option<&mut Vec<ty::ProjectionPredicate<'tcx>>>)
+    self_ty: Option<Ty<'tcx>>)
     -> Rc<ty::TraitRef<'tcx>>
 {
+    let trait_def_id = trait_def_id(this, trait_ref);
+    ast_path_to_mono_trait_ref(this,
+                               rscope,
+                               trait_ref.path.span,
+                               PathParamMode::Explicit,
+                               trait_def_id,
+                               self_ty,
+                               trait_ref.path.segments.last().unwrap())
+}
+
+fn trait_def_id<'tcx>(this: &AstConv<'tcx>, trait_ref: &ast::TraitRef) -> ast::DefId {
     let path = &trait_ref.path;
     match ::lookup_full_def(this.tcx(), path.span, trait_ref.ref_id) {
-        def::DefTrait(trait_def_id) => {
-            let trait_ref = ast_path_to_trait_ref(this,
-                                                  rscope,
-                                                  path.span,
-                                                  PathParamMode::Explicit,
-                                                  trait_def_id,
-                                                  self_ty,
-                                                  path.segments.last().unwrap(),
-                                                  projections);
-            if let Some(id) = impl_id {
-                this.tcx().impl_trait_refs.borrow_mut().insert(id, trait_ref.clone());
-            }
-            trait_ref
-        }
+        def::DefTrait(trait_def_id) => trait_def_id,
         _ => {
             span_fatal!(this.tcx().sess, path.span, E0245, "`{}` is not a trait",
                         path.user_string(this.tcx()));
@@ -676,24 +664,17 @@ fn object_path_to_poly_trait_ref<'a,'tcx>(
     mut projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
     -> ty::PolyTraitRef<'tcx>
 {
-    // we are introducing a binder here, so shift the
-    // anonymous regions depth to account for that
-    let shifted_rscope = ShiftedRscope::new(rscope);
-
-    let mut tmp = Vec::new();
-    let trait_ref = ty::Binder(ast_path_to_trait_ref(this,
-                                                     &shifted_rscope,
-                                                     span,
-                                                     param_mode,
-                                                     trait_def_id,
-                                                     None,
-                                                     trait_segment,
-                                                     Some(&mut tmp)));
-    projections.extend(tmp.into_iter().map(ty::Binder));
-    trait_ref
+    ast_path_to_poly_trait_ref(this,
+                               rscope,
+                               span,
+                               param_mode,
+                               trait_def_id,
+                               None,
+                               trait_segment,
+                               projections)
 }
 
-fn ast_path_to_trait_ref<'a,'tcx>(
+fn ast_path_to_poly_trait_ref<'a,'tcx>(
     this: &AstConv<'tcx>,
     rscope: &RegionScope,
     span: Span,
@@ -701,10 +682,78 @@ fn ast_path_to_trait_ref<'a,'tcx>(
     trait_def_id: ast::DefId,
     self_ty: Option<Ty<'tcx>>,
     trait_segment: &ast::PathSegment,
-    mut projections: Option<&mut Vec<ty::ProjectionPredicate<'tcx>>>)
-    -> Rc<ty::TraitRef<'tcx>>
+    poly_projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
+    -> ty::PolyTraitRef<'tcx>
+{
+    // The trait reference introduces a binding level here, so
+    // we need to shift the `rscope`. It'd be nice if we could
+    // do away with this rscope stuff and work this knowledge
+    // into resolve_lifetimes, as we do with non-omitted
+    // lifetimes. Oh well, not there yet.
+    let shifted_rscope = &ShiftedRscope::new(rscope);
+
+    let (substs, assoc_bindings) =
+        create_substs_for_ast_trait_ref(this,
+                                        shifted_rscope,
+                                        span,
+                                        param_mode,
+                                        trait_def_id,
+                                        self_ty,
+                                        trait_segment);
+    let poly_trait_ref = ty::Binder(Rc::new(ty::TraitRef::new(trait_def_id, substs)));
+
+    {
+        let converted_bindings =
+            assoc_bindings
+            .iter()
+            .filter_map(|binding| {
+                // specify type to assert that error was already reported in Err case:
+                let predicate: Result<_, ErrorReported> =
+                    ast_type_binding_to_poly_projection_predicate(this,
+                                                                  poly_trait_ref.clone(),
+                                                                  self_ty,
+                                                                  binding);
+                predicate.ok() // ok to ignore Err() because ErrorReported (see above)
+            });
+        poly_projections.extend(converted_bindings);
+    }
+
+    poly_trait_ref
+}
+
+fn ast_path_to_mono_trait_ref<'a,'tcx>(this: &AstConv<'tcx>,
+                                       rscope: &RegionScope,
+                                       span: Span,
+                                       param_mode: PathParamMode,
+                                       trait_def_id: ast::DefId,
+                                       self_ty: Option<Ty<'tcx>>,
+                                       trait_segment: &ast::PathSegment)
+                                       -> Rc<ty::TraitRef<'tcx>>
 {
-    debug!("ast_path_to_trait_ref {:?}", trait_segment);
+    let (substs, assoc_bindings) =
+        create_substs_for_ast_trait_ref(this,
+                                        rscope,
+                                        span,
+                                        param_mode,
+                                        trait_def_id,
+                                        self_ty,
+                                        trait_segment);
+    prohibit_projections(this.tcx(), &assoc_bindings);
+    Rc::new(ty::TraitRef::new(trait_def_id, substs))
+}
+
+fn create_substs_for_ast_trait_ref<'a,'tcx>(this: &AstConv<'tcx>,
+                                            rscope: &RegionScope,
+                                            span: Span,
+                                            param_mode: PathParamMode,
+                                            trait_def_id: ast::DefId,
+                                            self_ty: Option<Ty<'tcx>>,
+                                            trait_segment: &ast::PathSegment)
+                                            -> (&'tcx Substs<'tcx>, Vec<ConvertedBinding<'tcx>>)
+{
+    debug!("create_substs_for_ast_trait_ref(trait_segment={:?})",
+           trait_segment);
+
     let trait_def = match this.get_trait_def(span, trait_def_id) {
         Ok(trait_def) => trait_def,
         Err(ErrorReported) => {
@@ -752,34 +801,16 @@ fn ast_path_to_trait_ref<'a,'tcx>(
                                             self_ty,
                                             types,
                                             regions);
-    let substs = this.tcx().mk_substs(substs);
 
-    let trait_ref = Rc::new(ty::TraitRef::new(trait_def_id, substs));
-
-    match projections {
-        None => {
-            prohibit_projections(this.tcx(), &assoc_bindings);
-        }
-        Some(ref mut v) => {
-            for binding in &assoc_bindings {
-                match ast_type_binding_to_projection_predicate(this, trait_ref.clone(),
-                                                               self_ty, binding) {
-                    Ok(pp) => { v.push(pp); }
-                    Err(ErrorReported) => { }
-                }
-            }
-        }
-    }
-
-    trait_ref
+    (this.tcx().mk_substs(substs), assoc_bindings)
 }
 
-fn ast_type_binding_to_projection_predicate<'tcx>(
+fn ast_type_binding_to_poly_projection_predicate<'tcx>(
     this: &AstConv<'tcx>,
-    mut trait_ref: Rc<ty::TraitRef<'tcx>>,
+    mut trait_ref: ty::PolyTraitRef<'tcx>,
     self_ty: Option<Ty<'tcx>>,
     binding: &ConvertedBinding<'tcx>)
-    -> Result<ty::ProjectionPredicate<'tcx>, ErrorReported>
+    -> Result<ty::PolyProjectionPredicate<'tcx>, ErrorReported>
 {
     let tcx = this.tcx();
 
@@ -800,14 +831,14 @@ fn ast_type_binding_to_projection_predicate<'tcx>(
     // We want to produce `<B as SuperTrait<int>>::T == foo`.
 
     // Simple case: X is defined in the current trait.
-    if this.trait_defines_associated_type_named(trait_ref.def_id, binding.item_name) {
-        return Ok(ty::ProjectionPredicate {
-            projection_ty: ty::ProjectionTy {
-                trait_ref: trait_ref,
+    if this.trait_defines_associated_type_named(trait_ref.def_id(), binding.item_name) {
+        return Ok(ty::Binder(ty::ProjectionPredicate {      // <-------------------+
+            projection_ty: ty::ProjectionTy {               //                     |
+                trait_ref: trait_ref.skip_binder().clone(), // Binder moved here --+
                 item_name: binding.item_name,
             },
             ty: binding.ty,
-        });
+        }));
     }
 
     // Otherwise, we have to walk through the supertraits to find
@@ -820,17 +851,17 @@ fn ast_type_binding_to_projection_predicate<'tcx>(
 
     let dummy_self_ty = ty::mk_infer(tcx, ty::FreshTy(0));
     if self_ty.is_none() { // if converting for an object type
-        let mut dummy_substs = trait_ref.substs.clone();
-        assert!(dummy_substs.self_ty().is_none());
-        dummy_substs.types.push(SelfSpace, dummy_self_ty);
-        trait_ref = Rc::new(ty::TraitRef::new(trait_ref.def_id,
-                                              tcx.mk_substs(dummy_substs)));
+        let mut dummy_substs = trait_ref.skip_binder().substs.clone(); // binder moved here -+
+        assert!(dummy_substs.self_ty().is_none());                     //                    |
+        dummy_substs.types.push(SelfSpace, dummy_self_ty);             //                    |
+        trait_ref = ty::Binder(Rc::new(ty::TraitRef::new(trait_ref.def_id(), // <------------+
+                                                         tcx.mk_substs(dummy_substs))));
     }
 
-    try!(this.ensure_super_predicates(binding.span, trait_ref.def_id));
+    try!(this.ensure_super_predicates(binding.span, trait_ref.def_id()));
 
     let mut candidates: Vec<ty::PolyTraitRef> =
-        traits::supertraits(tcx, trait_ref.to_poly_trait_ref())
+        traits::supertraits(tcx, trait_ref.clone())
         .filter(|r| this.trait_defines_associated_type_named(r.def_id(), binding.item_name))
         .collect();
 
@@ -865,21 +896,13 @@ fn ast_type_binding_to_projection_predicate<'tcx>(
         }
     };
 
-    if ty::binds_late_bound_regions(tcx, &candidate) {
-        span_err!(tcx.sess, binding.span, E0219,
-            "associated type `{}` defined in higher-ranked supertrait `{}`",
-                    token::get_name(binding.item_name),
-                    candidate.user_string(tcx));
-        return Err(ErrorReported);
-    }
-
-    Ok(ty::ProjectionPredicate {
-        projection_ty: ty::ProjectionTy {
-            trait_ref: candidate.0,
+    Ok(ty::Binder(ty::ProjectionPredicate {             // <-------------------------+
+        projection_ty: ty::ProjectionTy {               //                           |
+            trait_ref: candidate.skip_binder().clone(), // binder is moved up here --+
             item_name: binding.item_name,
         },
         ty: binding.ty,
-    })
+    }))
 }
 
 fn ast_path_to_ty<'tcx>(
@@ -1134,14 +1157,14 @@ fn qpath_to_ty<'tcx>(this: &AstConv<'tcx>,
 
     debug!("qpath_to_ty: self_type={}", self_ty.repr(tcx));
 
-    let trait_ref = ast_path_to_trait_ref(this,
-                                          rscope,
-                                          span,
-                                          param_mode,
-                                          trait_def_id,
-                                          Some(self_ty),
-                                          trait_segment,
-                                          None);
+    let trait_ref =
+        ast_path_to_mono_trait_ref(this,
+                                   rscope,
+                                   span,
+                                   param_mode,
+                                   trait_def_id,
+                                   Some(self_ty),
+                                   trait_segment);
 
     debug!("qpath_to_ty: trait_ref={}", trait_ref.repr(tcx));
 
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index 32f91a175f3..d2a06fcf990 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -16,6 +16,7 @@ use astconv;
 use middle::region;
 use middle::subst;
 use middle::ty::{self, ToPolyTraitRef, Ty};
+use std::cmp;
 use syntax::abi;
 use syntax::ast;
 use syntax::ast_util;
@@ -109,15 +110,11 @@ fn deduce_expectations_from_expected_type<'a,'tcx>(
         ty::ty_trait(ref object_type) => {
             let proj_bounds = object_type.projection_bounds_with_self_ty(fcx.tcx(),
                                                                          fcx.tcx().types.err);
-            let expectations =
-                proj_bounds.iter()
-                           .filter_map(|pb| deduce_expectations_from_projection(fcx, pb))
-                           .next();
-
-            match expectations {
-                Some((sig, kind)) => (Some(sig), Some(kind)),
-                None => (None, None)
-            }
+            let sig = proj_bounds.iter()
+                                 .filter_map(|pb| deduce_sig_from_projection(fcx, pb))
+                                 .next();
+            let kind = fcx.tcx().lang_items.fn_trait_kind(object_type.principal_def_id());
+            (sig, kind)
         }
         ty::ty_infer(ty::TyVar(vid)) => {
             deduce_expectations_from_obligations(fcx, vid)
@@ -136,7 +133,7 @@ fn deduce_expectations_from_obligations<'a,'tcx>(
     let fulfillment_cx = fcx.inh.fulfillment_cx.borrow();
     // Here `expected_ty` is known to be a type inference variable.
 
-    let expected_sig_and_kind =
+    let expected_sig =
         fulfillment_cx
         .pending_obligations()
         .iter()
@@ -150,7 +147,7 @@ fn deduce_expectations_from_obligations<'a,'tcx>(
                 ty::Predicate::Projection(ref proj_predicate) => {
                     let trait_ref = proj_predicate.to_poly_trait_ref();
                     self_type_matches_expected_vid(fcx, trait_ref, expected_vid)
-                        .and_then(|_| deduce_expectations_from_projection(fcx, proj_predicate))
+                        .and_then(|_| deduce_sig_from_projection(fcx, proj_predicate))
                 }
                 _ => {
                     None
@@ -159,14 +156,10 @@ fn deduce_expectations_from_obligations<'a,'tcx>(
         })
         .next();
 
-    match expected_sig_and_kind {
-        Some((sig, kind)) => { return (Some(sig), Some(kind)); }
-        None => { }
-    }
-
     // Even if we can't infer the full signature, we may be able to
     // infer the kind. This can occur if there is a trait-reference
-    // like `F : Fn<A>`.
+    // like `F : Fn<A>`. Note that due to subtyping we could encounter
+    // many viable options, so pick the most restrictive.
     let expected_kind =
         fulfillment_cx
         .pending_obligations()
@@ -183,54 +176,61 @@ fn deduce_expectations_from_obligations<'a,'tcx>(
                 .and_then(|trait_ref| self_type_matches_expected_vid(fcx, trait_ref, expected_vid))
                 .and_then(|trait_ref| fcx.tcx().lang_items.fn_trait_kind(trait_ref.def_id()))
         })
-        .next();
+        .fold(None, pick_most_restrictive_closure_kind);
+
+    (expected_sig, expected_kind)
+}
 
-    (None, expected_kind)
+fn pick_most_restrictive_closure_kind(best: Option<ty::ClosureKind>,
+                                      cur: ty::ClosureKind)
+                                      -> Option<ty::ClosureKind>
+{
+    match best {
+        None => Some(cur),
+        Some(best) => Some(cmp::min(best, cur))
+    }
 }
 
 /// Given a projection like "<F as Fn(X)>::Result == Y", we can deduce
 /// everything we need to know about a closure.
-fn deduce_expectations_from_projection<'a,'tcx>(
+fn deduce_sig_from_projection<'a,'tcx>(
     fcx: &FnCtxt<'a,'tcx>,
     projection: &ty::PolyProjectionPredicate<'tcx>)
-    -> Option<(ty::FnSig<'tcx>, ty::ClosureKind)>
+    -> Option<ty::FnSig<'tcx>>
 {
     let tcx = fcx.tcx();
 
-    debug!("deduce_expectations_from_projection({})",
+    debug!("deduce_sig_from_projection({})",
            projection.repr(tcx));
 
     let trait_ref = projection.to_poly_trait_ref();
 
-    let kind = match tcx.lang_items.fn_trait_kind(trait_ref.def_id()) {
-        Some(k) => k,
-        None => { return None; }
-    };
-
-    debug!("found object type {:?}", kind);
+    if tcx.lang_items.fn_trait_kind(trait_ref.def_id()).is_none() {
+        return None;
+    }
 
     let arg_param_ty = *trait_ref.substs().types.get(subst::TypeSpace, 0);
     let arg_param_ty = fcx.infcx().resolve_type_vars_if_possible(&arg_param_ty);
-    debug!("arg_param_ty {}", arg_param_ty.repr(tcx));
+    debug!("deduce_sig_from_projection: arg_param_ty {}", arg_param_ty.repr(tcx));
 
     let input_tys = match arg_param_ty.sty {
         ty::ty_tup(ref tys) => { (*tys).clone() }
         _ => { return None; }
     };
-    debug!("input_tys {}", input_tys.repr(tcx));
+    debug!("deduce_sig_from_projection: input_tys {}", input_tys.repr(tcx));
 
     let ret_param_ty = projection.0.ty;
     let ret_param_ty = fcx.infcx().resolve_type_vars_if_possible(&ret_param_ty);
-    debug!("ret_param_ty {}", ret_param_ty.repr(tcx));
+    debug!("deduce_sig_from_projection: ret_param_ty {}", ret_param_ty.repr(tcx));
 
     let fn_sig = ty::FnSig {
         inputs: input_tys,
         output: ty::FnConverging(ret_param_ty),
         variadic: false
     };
-    debug!("fn_sig {}", fn_sig.repr(tcx));
+    debug!("deduce_sig_from_projection: fn_sig {}", fn_sig.repr(tcx));
 
-    return Some((fn_sig, kind));
+    Some(fn_sig)
 }
 
 fn self_type_matches_expected_vid<'a,'tcx>(
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index bc581a6af41..b95e0ce8cb3 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -725,7 +725,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
             };
 
             // this closure doesn't implement the right kind of `Fn` trait
-            if closure_kind != kind {
+            if !closure_kind.extends(kind) {
                 continue;
             }
 
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 5efc26825ea..5816fe58bc9 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -784,14 +784,15 @@ fn convert_item(ccx: &CrateCtxt, it: &ast::Item) {
                                    &enum_definition.variants);
         },
         ast::ItemDefaultImpl(_, ref ast_trait_ref) => {
-            let trait_ref = astconv::instantiate_trait_ref(&ccx.icx(&()),
-                                                           &ExplicitRscope,
-                                                           ast_trait_ref,
-                                                           Some(it.id),
-                                                           None,
-                                                           None);
+            let trait_ref =
+                astconv::instantiate_mono_trait_ref(&ccx.icx(&()),
+                                                    &ExplicitRscope,
+                                                    ast_trait_ref,
+                                                    None);
 
             ty::record_trait_has_default_impl(tcx, trait_ref.def_id);
+
+            tcx.impl_trait_refs.borrow_mut().insert(it.id, trait_ref);
         }
         ast::ItemImpl(_, _,
                       ref generics,
@@ -890,13 +891,14 @@ fn convert_item(ccx: &CrateCtxt, it: &ast::Item) {
                 }
             }
 
-            if let Some(ref trait_ref) = *opt_trait_ref {
-                astconv::instantiate_trait_ref(&ccx.icx(&ty_predicates),
-                                               &ExplicitRscope,
-                                               trait_ref,
-                                               Some(it.id),
-                                               Some(selfty),
-                                               None);
+            if let Some(ref ast_trait_ref) = *opt_trait_ref {
+                let trait_ref =
+                    astconv::instantiate_mono_trait_ref(&ccx.icx(&ty_predicates),
+                                                        &ExplicitRscope,
+                                                        ast_trait_ref,
+                                                        Some(selfty));
+
+                tcx.impl_trait_refs.borrow_mut().insert(it.id, trait_ref);
             }
 
             enforce_impl_ty_params_are_constrained(tcx,
diff --git a/src/test/compile-fail/borrowck-overloaded-call.rs b/src/test/compile-fail/borrowck-overloaded-call.rs
index 673c025e863..93c37524bf5 100644
--- a/src/test/compile-fail/borrowck-overloaded-call.rs
+++ b/src/test/compile-fail/borrowck-overloaded-call.rs
@@ -18,26 +18,36 @@ struct SFn {
 }
 
 impl Fn<(isize,)> for SFn {
-    type Output = isize;
-
     extern "rust-call" fn call(&self, (z,): (isize,)) -> isize {
         self.x * self.y * z
     }
 }
 
+impl FnMut<(isize,)> for SFn {
+    extern "rust-call" fn call_mut(&mut self, args: (isize,)) -> isize { self.call(args) }
+}
+
+impl FnOnce<(isize,)> for SFn {
+    type Output = isize;
+    extern "rust-call" fn call_once(self, args: (isize,)) -> isize { self.call(args) }
+}
+
 struct SFnMut {
     x: isize,
     y: isize,
 }
 
 impl FnMut<(isize,)> for SFnMut {
-    type Output = isize;
-
     extern "rust-call" fn call_mut(&mut self, (z,): (isize,)) -> isize {
         self.x * self.y * z
     }
 }
 
+impl FnOnce<(isize,)> for SFnMut {
+    type Output = isize;
+    extern "rust-call" fn call_once(mut self, args: (isize,)) -> isize { self.call_mut(args) }
+}
+
 struct SFnOnce {
     x: String,
 }
diff --git a/src/test/compile-fail/coerce-unsafe-to-closure.rs b/src/test/compile-fail/coerce-unsafe-to-closure.rs
index fe7635f065c..27b4a04054f 100644
--- a/src/test/compile-fail/coerce-unsafe-to-closure.rs
+++ b/src/test/compile-fail/coerce-unsafe-to-closure.rs
@@ -10,5 +10,6 @@
 
 fn main() {
     let x: Option<&[u8]> = Some("foo").map(std::mem::transmute);
-    //~^ ERROR: is not implemented for the type
+    //~^ ERROR E0277
+    //~| ERROR E0277
 }
diff --git a/src/test/compile-fail/extern-wrong-value-type.rs b/src/test/compile-fail/extern-wrong-value-type.rs
index db3373ea027..d1abed9b262 100644
--- a/src/test/compile-fail/extern-wrong-value-type.rs
+++ b/src/test/compile-fail/extern-wrong-value-type.rs
@@ -18,5 +18,5 @@ fn main() {
     let _x: extern "C" fn() = f; // OK
     is_fn(f);
     //~^ ERROR the trait `core::ops::Fn<()>` is not implemented for the type `extern "C" fn()
-    //~| ERROR the trait `core::ops::Fn<()>` is not implemented for the type `extern "C" fn()
+    //~| ERROR the trait `core::ops::FnOnce<()>` is not implemented for the type `extern "C" fn()
 }
diff --git a/src/test/compile-fail/feature-gate-unboxed-closures-manual-impls.rs b/src/test/compile-fail/feature-gate-unboxed-closures-manual-impls.rs
index e5e5ddadafc..d86c5d211dc 100644
--- a/src/test/compile-fail/feature-gate-unboxed-closures-manual-impls.rs
+++ b/src/test/compile-fail/feature-gate-unboxed-closures-manual-impls.rs
@@ -18,28 +18,21 @@
 struct Foo;
 impl Fn<()> for Foo {
     //~^ ERROR angle-bracket notation is not stable when used with the `Fn` family of traits
-    type Output = ();
-
-    extern "rust-call" fn call(&self, args: ()) -> () {}
+    extern "rust-call" fn call(self, args: ()) -> () {}
 }
 struct Foo1;
-impl Fn() for Foo1 {
+impl FnOnce() for Foo1 {
     //~^ ERROR associated type bindings are not allowed here
-
-    extern "rust-call" fn call(&self, args: ()) -> () {}
+    extern "rust-call" fn call_once(self, args: ()) -> () {}
 }
 struct Bar;
 impl FnMut<()> for Bar {
     //~^ ERROR angle-bracket notation is not stable when used with the `Fn` family of traits
-    type Output = ();
-
     extern "rust-call" fn call_mut(&self, args: ()) -> () {}
 }
 struct Baz;
 impl FnOnce<()> for Baz {
     //~^ ERROR angle-bracket notation is not stable when used with the `Fn` family of traits
-    type Output = ();
-
     extern "rust-call" fn call_once(&self, args: ()) -> () {}
 }
 
diff --git a/src/test/compile-fail/fn-trait-formatting.rs b/src/test/compile-fail/fn-trait-formatting.rs
index 35c55193136..6433255bd4d 100644
--- a/src/test/compile-fail/fn-trait-formatting.rs
+++ b/src/test/compile-fail/fn-trait-formatting.rs
@@ -35,5 +35,5 @@ fn main() {
 
     needs_fn(1);
     //~^ ERROR `core::ops::Fn<(isize,)>`
-    //~| ERROR `core::ops::Fn<(isize,)>`
+    //~| ERROR `core::ops::FnOnce<(isize,)>`
 }
diff --git a/src/test/compile-fail/fn-variance-1.rs b/src/test/compile-fail/fn-variance-1.rs
index 838e65e1d05..8e1e88a92e4 100644
--- a/src/test/compile-fail/fn-variance-1.rs
+++ b/src/test/compile-fail/fn-variance-1.rs
@@ -17,9 +17,13 @@ fn apply<T, F>(t: T, f: F) where F: FnOnce(T) {
 }
 
 fn main() {
-    apply(&3, takes_mut); //~ ERROR (values differ in mutability)
     apply(&3, takes_imm);
+    apply(&3, takes_mut);
+    //~^ ERROR (values differ in mutability)
+    //~| ERROR (values differ in mutability)
 
     apply(&mut 3, takes_mut);
-    apply(&mut 3, takes_imm); //~ ERROR (values differ in mutability)
+    apply(&mut 3, takes_imm);
+    //~^ ERROR (values differ in mutability)
+    //~| ERROR (values differ in mutability)
 }
diff --git a/src/test/compile-fail/issue-15094.rs b/src/test/compile-fail/issue-15094.rs
index 8f79022405e..3853434e128 100644
--- a/src/test/compile-fail/issue-15094.rs
+++ b/src/test/compile-fail/issue-15094.rs
@@ -16,11 +16,10 @@ struct Debuger<T> {
     x: T
 }
 
-impl<T: fmt::Debug> ops::Fn<(),> for Debuger<T> {
+impl<T: fmt::Debug> ops::FnOnce<(),> for Debuger<T> {
     type Output = ();
-
-    fn call(&self, _args: ()) {
-//~^ ERROR `call` has an incompatible type for trait: expected "rust-call" fn, found "Rust" fn
+    fn call_once(self, _args: ()) {
+//~^ ERROR `call_once` has an incompatible type for trait: expected "rust-call" fn, found "Rust" fn
         println!("{:?}", self.x);
     }
 }
diff --git a/src/test/compile-fail/issue-20225.rs b/src/test/compile-fail/issue-20225.rs
index e4bedbbb7e1..fe427e02451 100644
--- a/src/test/compile-fail/issue-20225.rs
+++ b/src/test/compile-fail/issue-20225.rs
@@ -13,9 +13,19 @@
 struct Foo;
 
 impl<'a, T> Fn<(&'a T,)> for Foo {
+  extern "rust-call" fn call(&self, (_,): (T,)) {}
+  //~^ ERROR: has an incompatible type for trait: expected &-ptr
+}
+
+impl<'a, T> FnMut<(&'a T,)> for Foo {
+  extern "rust-call" fn call_mut(&mut self, (_,): (T,)) {}
+  //~^ ERROR: has an incompatible type for trait: expected &-ptr
+}
+
+impl<'a, T> FnOnce<(&'a T,)> for Foo {
   type Output = ();
 
-  extern "rust-call" fn call(&self, (_,): (T,)) {}
+  extern "rust-call" fn call_once(self, (_,): (T,)) {}
   //~^ ERROR: has an incompatible type for trait: expected &-ptr
 }
 
diff --git a/src/test/compile-fail/overloaded-calls-bad.rs b/src/test/compile-fail/overloaded-calls-bad.rs
index 61752e62abd..77ac97bc8b8 100644
--- a/src/test/compile-fail/overloaded-calls-bad.rs
+++ b/src/test/compile-fail/overloaded-calls-bad.rs
@@ -18,13 +18,18 @@ struct S {
 }
 
 impl FnMut<(isize,)> for S {
-    type Output = isize;
-
     extern "rust-call" fn call_mut(&mut self, (z,): (isize,)) -> isize {
         self.x * self.y * z
     }
 }
 
+impl FnOnce<(isize,)> for S {
+    type Output = isize;
+    extern "rust-call" fn call_once(mut self, (z,): (isize,)) -> isize {
+        self.call_mut((z,))
+    }
+}
+
 fn main() {
     let mut s = S {
         x: 3,
diff --git a/src/test/compile-fail/overloaded-calls-nontuple.rs b/src/test/compile-fail/overloaded-calls-nontuple.rs
index c4019fa2209..ea47d676412 100644
--- a/src/test/compile-fail/overloaded-calls-nontuple.rs
+++ b/src/test/compile-fail/overloaded-calls-nontuple.rs
@@ -18,12 +18,16 @@ struct S {
 }
 
 impl FnMut<isize> for S {
-    type Output = isize;
     extern "rust-call" fn call_mut(&mut self, z: isize) -> isize {
         self.x + self.y + z
     }
 }
 
+impl FnOnce<isize> for S {
+    type Output = isize;
+    extern "rust-call" fn call_once(mut self, z: isize) -> isize { self.call_mut(z) }
+}
+
 fn main() {
     let mut s = S {
         x: 1,
diff --git a/src/test/compile-fail/unboxed-closures-fnmut-as-fn.rs b/src/test/compile-fail/unboxed-closures-fnmut-as-fn.rs
index 92e6affa4c2..93498ac7f83 100644
--- a/src/test/compile-fail/unboxed-closures-fnmut-as-fn.rs
+++ b/src/test/compile-fail/unboxed-closures-fnmut-as-fn.rs
@@ -19,13 +19,17 @@ use std::ops::{Fn,FnMut,FnOnce};
 struct S;
 
 impl FnMut<(isize,)> for S {
-    type Output = isize;
-
     extern "rust-call" fn call_mut(&mut self, (x,): (isize,)) -> isize {
         x * x
     }
 }
 
+impl FnOnce<(isize,)> for S {
+    type Output = isize;
+
+    extern "rust-call" fn call_once(mut self, args: (isize,)) -> isize { self.call_mut(args) }
+}
+
 fn call_it<F:Fn(isize)->isize>(f: &F, x: isize) -> isize {
     f.call((x,))
 }
@@ -33,5 +37,4 @@ fn call_it<F:Fn(isize)->isize>(f: &F, x: isize) -> isize {
 fn main() {
     let x = call_it(&S, 22);
     //~^ ERROR not implemented
-    //~| ERROR not implemented
 }
diff --git a/src/test/compile-fail/unboxed-closures-recursive-fn-using-fn-mut.rs b/src/test/compile-fail/unboxed-closures-recursive-fn-using-fn-mut.rs
index 713b64b1349..2dcd7a97d89 100644
--- a/src/test/compile-fail/unboxed-closures-recursive-fn-using-fn-mut.rs
+++ b/src/test/compile-fail/unboxed-closures-recursive-fn-using-fn-mut.rs
@@ -28,14 +28,19 @@ impl<F,A,R> YCombinator<F,A,R> {
 }
 
 impl<A,R,F : FnMut(&mut FnMut(A) -> R, A) -> R> FnMut<(A,)> for YCombinator<F,A,R> {
-    type Output = R;
-
     extern "rust-call" fn call_mut(&mut self, (arg,): (A,)) -> R {
         (self.func)(self, arg)
             //~^ ERROR cannot borrow `*self` as mutable more than once at a time
     }
 }
 
+impl<A,R,F : FnMut(&mut FnMut(A) -> R, A) -> R> FnOnce<(A,)> for YCombinator<F,A,R> {
+    type Output = R;
+    extern "rust-call" fn call_once(mut self, args: (A,)) -> R {
+        self.call_mut(args)
+    }
+}
+
 fn main() {
     let mut counter = 0;
     let factorial = |recur: &mut FnMut(u32) -> u32, arg: u32| -> u32 {
diff --git a/src/test/compile-fail/unboxed-closures-unsafe-extern-fn.rs b/src/test/compile-fail/unboxed-closures-unsafe-extern-fn.rs
index 23f7ee2b010..dc7c70ba649 100644
--- a/src/test/compile-fail/unboxed-closures-unsafe-extern-fn.rs
+++ b/src/test/compile-fail/unboxed-closures-unsafe-extern-fn.rs
@@ -27,11 +27,15 @@ fn a() {
 }
 
 fn b() {
-    let y = call_it_mut(&mut square, 22); //~ ERROR not implemented
+    let y = call_it_mut(&mut square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn c() {
-    let z = call_it_once(square, 22); //~ ERROR not implemented
+    let z = call_it_once(square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/unboxed-closures-wrong-abi.rs b/src/test/compile-fail/unboxed-closures-wrong-abi.rs
index 40655f8a3ce..cdcb435b65a 100644
--- a/src/test/compile-fail/unboxed-closures-wrong-abi.rs
+++ b/src/test/compile-fail/unboxed-closures-wrong-abi.rs
@@ -27,11 +27,15 @@ fn a() {
 }
 
 fn b() {
-    let y = call_it_mut(&mut square, 22); //~ ERROR not implemented
+    let y = call_it_mut(&mut square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn c() {
-    let z = call_it_once(square, 22); //~ ERROR not implemented
+    let z = call_it_once(square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/unboxed-closures-wrong-arg-type-extern-fn.rs b/src/test/compile-fail/unboxed-closures-wrong-arg-type-extern-fn.rs
index ebcbdbbc006..150bf36dcc2 100644
--- a/src/test/compile-fail/unboxed-closures-wrong-arg-type-extern-fn.rs
+++ b/src/test/compile-fail/unboxed-closures-wrong-arg-type-extern-fn.rs
@@ -28,11 +28,15 @@ fn a() {
 }
 
 fn b() {
-    let y = call_it_mut(&mut square, 22); //~ ERROR not implemented
+    let y = call_it_mut(&mut square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn c() {
-    let z = call_it_once(square, 22); //~ ERROR not implemented
+    let z = call_it_once(square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn main() { }
diff --git a/src/test/run-pass/issue-13655.rs b/src/test/run-pass/issue-13655.rs
index cd5da3844e1..11219b04f2b 100644
--- a/src/test/run-pass/issue-13655.rs
+++ b/src/test/run-pass/issue-13655.rs
@@ -14,7 +14,6 @@ use std::ops::Fn;
 struct Foo<T>(T);
 
 impl<T: Copy> Fn<()> for Foo<T> {
-    type Output = T;
     extern "rust-call" fn call(&self, _: ()) -> T {
       match *self {
         Foo(t) => t
@@ -22,6 +21,20 @@ impl<T: Copy> Fn<()> for Foo<T> {
     }
 }
 
+impl<T: Copy> FnMut<()> for Foo<T> {
+    extern "rust-call" fn call_mut(&mut self, _: ()) -> T {
+        self.call(())
+    }
+}
+
+impl<T: Copy> FnOnce<()> for Foo<T> {
+    type Output = T;
+
+    extern "rust-call" fn call_once(self, _: ()) -> T {
+        self.call(())
+    }
+}
+
 fn main() {
   let t: u8 = 1;
   println!("{}", Foo(t)());
diff --git a/src/test/run-pass/issue-14958.rs b/src/test/run-pass/issue-14958.rs
index be13d0bc80c..ec482a776de 100644
--- a/src/test/run-pass/issue-14958.rs
+++ b/src/test/run-pass/issue-14958.rs
@@ -17,10 +17,18 @@ trait Foo { fn dummy(&self) { }}
 struct Bar;
 
 impl<'a> std::ops::Fn<(&'a (Foo+'a),)> for Bar {
-    type Output = ();
     extern "rust-call" fn call(&self, _: (&'a Foo,)) {}
 }
 
+impl<'a> std::ops::FnMut<(&'a (Foo+'a),)> for Bar {
+    extern "rust-call" fn call_mut(&mut self, a: (&'a Foo,)) { self.call(a) }
+}
+
+impl<'a> std::ops::FnOnce<(&'a (Foo+'a),)> for Bar {
+    type Output = ();
+    extern "rust-call" fn call_once(self, a: (&'a Foo,)) { self.call(a) }
+}
+
 struct Baz;
 
 impl Foo for Baz {}
diff --git a/src/test/run-pass/issue-14959.rs b/src/test/run-pass/issue-14959.rs
index d6fdd9f230a..5accaf36349 100644
--- a/src/test/run-pass/issue-14959.rs
+++ b/src/test/run-pass/issue-14959.rs
@@ -36,9 +36,21 @@ impl Alloy {
 }
 
 impl<'b> Fn<(&'b mut (Response+'b),)> for SendFile {
+    extern "rust-call" fn call(&self, (_res,): (&'b mut (Response+'b),)) {}
+}
+
+impl<'b> FnMut<(&'b mut (Response+'b),)> for SendFile {
+    extern "rust-call" fn call_mut(&mut self, (_res,): (&'b mut (Response+'b),)) {
+        self.call((_res,))
+    }
+}
+
+impl<'b> FnOnce<(&'b mut (Response+'b),)> for SendFile {
     type Output = ();
 
-    extern "rust-call" fn call(&self, (_res,): (&'b mut (Response+'b),)) {}
+    extern "rust-call" fn call_once(self, (_res,): (&'b mut (Response+'b),)) {
+        self.call((_res,))
+    }
 }
 
 impl<Rq: Request, Rs: Response> Ingot<Rq, Rs> for HelloWorld {
diff --git a/src/test/run-pass/issue-16739.rs b/src/test/run-pass/issue-16739.rs
index 5270ef9268c..99ddaba4e55 100644
--- a/src/test/run-pass/issue-16739.rs
+++ b/src/test/run-pass/issue-16739.rs
@@ -20,20 +20,36 @@
 struct Foo { foo: u32 }
 
 impl FnMut<()> for Foo {
-    type Output = u32;
     extern "rust-call" fn call_mut(&mut self, _: ()) -> u32 { self.foo }
 }
 
-impl FnMut<(u32,)> for Foo {
+impl FnOnce<()> for Foo {
     type Output = u32;
+    extern "rust-call" fn call_once(mut self, _: ()) -> u32 { self.call_mut(()) }
+}
+
+/////////////////////////////////////////////////////////////////////////
+
+impl FnMut<(u32,)> for Foo {
     extern "rust-call" fn call_mut(&mut self, (x,): (u32,)) -> u32 { self.foo + x }
 }
 
-impl FnMut<(u32,u32)> for Foo {
+impl FnOnce<(u32,)> for Foo {
     type Output = u32;
+    extern "rust-call" fn call_once(mut self, args: (u32,)) -> u32 { self.call_mut(args) }
+}
+
+/////////////////////////////////////////////////////////////////////////
+
+impl FnMut<(u32,u32)> for Foo {
     extern "rust-call" fn call_mut(&mut self, (x, y): (u32, u32)) -> u32 { self.foo + x + y }
 }
 
+impl FnOnce<(u32,u32)> for Foo {
+    type Output = u32;
+    extern "rust-call" fn call_once(mut self, args: (u32,u32)) -> u32 { self.call_mut(args) }
+}
+
 fn main() {
     let mut f = box Foo { foo: 42 } as Box<FnMut() -> u32>;
     assert_eq!(f.call_mut(()), 42);
diff --git a/src/test/run-pass/issue-19982.rs b/src/test/run-pass/issue-19982.rs
index 41d202c4635..9442b039bc6 100644
--- a/src/test/run-pass/issue-19982.rs
+++ b/src/test/run-pass/issue-19982.rs
@@ -16,9 +16,17 @@
 struct Foo;
 
 impl<'a> Fn<(&'a (),)> for Foo {
+    extern "rust-call" fn call(&self, (_,): (&(),)) {}
+}
+
+impl<'a> FnMut<(&'a (),)> for Foo {
+    extern "rust-call" fn call_mut(&mut self, (_,): (&(),)) {}
+}
+
+impl<'a> FnOnce<(&'a (),)> for Foo {
     type Output = ();
 
-    extern "rust-call" fn call(&self, (_,): (&(),)) {}
+    extern "rust-call" fn call_once(self, (_,): (&(),)) {}
 }
 
 fn main() {}
diff --git a/src/test/run-pass/overloaded-calls-param-vtables.rs b/src/test/run-pass/overloaded-calls-param-vtables.rs
index f5ccd87fd25..597075c5500 100644
--- a/src/test/run-pass/overloaded-calls-param-vtables.rs
+++ b/src/test/run-pass/overloaded-calls-param-vtables.rs
@@ -21,13 +21,20 @@ use std::ops::Add;
 struct G<A>(PhantomData<A>);
 
 impl<'a, A: Add<i32, Output=i32>> Fn<(A,)> for G<A> {
-    type Output = i32;
-
     extern "rust-call" fn call(&self, (arg,): (A,)) -> i32 {
         arg.add(1)
     }
 }
 
+impl<'a, A: Add<i32, Output=i32>> FnMut<(A,)> for G<A> {
+    extern "rust-call" fn call_mut(&mut self, args: (A,)) -> i32 { self.call(args) }
+}
+
+impl<'a, A: Add<i32, Output=i32>> FnOnce<(A,)> for G<A> {
+    type Output = i32;
+    extern "rust-call" fn call_once(self, args: (A,)) -> i32 { self.call(args) }
+}
+
 fn main() {
     // ICE trigger
     (G(PhantomData))(1);
diff --git a/src/test/run-pass/overloaded-calls-simple.rs b/src/test/run-pass/overloaded-calls-simple.rs
index 17990bb1bd1..eeb705a2e3c 100644
--- a/src/test/run-pass/overloaded-calls-simple.rs
+++ b/src/test/run-pass/overloaded-calls-simple.rs
@@ -20,24 +20,38 @@ struct S1 {
 }
 
 impl FnMut<(i32,)> for S1 {
-    type Output = i32;
     extern "rust-call" fn call_mut(&mut self, (z,): (i32,)) -> i32 {
         self.x * self.y * z
     }
 }
 
+impl FnOnce<(i32,)> for S1 {
+    type Output = i32;
+    extern "rust-call" fn call_once(mut self, args: (i32,)) -> i32 {
+        self.call_mut(args)
+    }
+}
+
 struct S2 {
     x: i32,
     y: i32,
 }
 
 impl Fn<(i32,)> for S2 {
-    type Output = i32;
     extern "rust-call" fn call(&self, (z,): (i32,)) -> i32 {
         self.x * self.y * z
     }
 }
 
+impl FnMut<(i32,)> for S2 {
+    extern "rust-call" fn call_mut(&mut self, args: (i32,)) -> i32 { self.call(args) }
+}
+
+impl FnOnce<(i32,)> for S2 {
+    type Output = i32;
+    extern "rust-call" fn call_once(self, args: (i32,)) -> i32 { self.call(args) }
+}
+
 struct S3 {
     x: i32,
     y: i32,
diff --git a/src/test/run-pass/overloaded-calls-zero-args.rs b/src/test/run-pass/overloaded-calls-zero-args.rs
index ea78a75c0c7..110109018db 100644
--- a/src/test/run-pass/overloaded-calls-zero-args.rs
+++ b/src/test/run-pass/overloaded-calls-zero-args.rs
@@ -20,12 +20,16 @@ struct S {
 }
 
 impl FnMut<()> for S {
-    type Output = i32;
     extern "rust-call" fn call_mut(&mut self, (): ()) -> i32 {
         self.x * self.y
     }
 }
 
+impl FnOnce<()> for S {
+    type Output = i32;
+    extern "rust-call" fn call_once(mut self, args: ()) -> i32 { self.call_mut(args) }
+}
+
 fn main() {
     let mut s = S {
         x: 3,
diff --git a/src/test/run-pass/unboxed-closures-fn-as-fnmut-and-fnonce.rs b/src/test/run-pass/unboxed-closures-fn-as-fnmut-and-fnonce.rs
index 5ec280dabc9..9b71abf3653 100644
--- a/src/test/run-pass/unboxed-closures-fn-as-fnmut-and-fnonce.rs
+++ b/src/test/run-pass/unboxed-closures-fn-as-fnmut-and-fnonce.rs
@@ -20,12 +20,20 @@ use std::ops::{Fn,FnMut,FnOnce};
 struct S;
 
 impl Fn<(i32,)> for S {
-    type Output = i32;
     extern "rust-call" fn call(&self, (x,): (i32,)) -> i32 {
         x * x
     }
 }
 
+impl FnMut<(i32,)> for S {
+    extern "rust-call" fn call_mut(&mut self, args: (i32,)) -> i32 { self.call(args) }
+}
+
+impl FnOnce<(i32,)> for S {
+    type Output = i32;
+    extern "rust-call" fn call_once(self, args: (i32,)) -> i32 { self.call(args) }
+}
+
 fn call_it<F:Fn(i32)->i32>(f: &F, x: i32) -> i32 {
     f(x)
 }
diff --git a/src/test/run-pass/unboxed-closures-fnmut-as-fnonce.rs b/src/test/run-pass/unboxed-closures-fnmut-as-fnonce.rs
index 79be7dae8d7..6261058b867 100644
--- a/src/test/run-pass/unboxed-closures-fnmut-as-fnonce.rs
+++ b/src/test/run-pass/unboxed-closures-fnmut-as-fnonce.rs
@@ -20,13 +20,17 @@ use std::ops::{FnMut,FnOnce};
 struct S;
 
 impl FnMut<(i32,)> for S {
-    type Output = i32;
-
     extern "rust-call" fn call_mut(&mut self, (x,): (i32,)) -> i32 {
         x * x
     }
 }
 
+impl FnOnce<(i32,)> for S {
+    type Output = i32;
+
+    extern "rust-call" fn call_once(mut self, args: (i32,)) -> i32 { self.call_mut(args) }
+}
+
 fn call_it_mut<F:FnMut(i32)->i32>(f: &mut F, x: i32) -> i32 {
     f(x)
 }
diff --git a/src/test/run-pass/unboxed-closures-infer-recursive-fn.rs b/src/test/run-pass/unboxed-closures-infer-recursive-fn.rs
index ece583e8d63..e02784f917a 100644
--- a/src/test/run-pass/unboxed-closures-infer-recursive-fn.rs
+++ b/src/test/run-pass/unboxed-closures-infer-recursive-fn.rs
@@ -32,13 +32,20 @@ impl<F,A,R> YCombinator<F,A,R> {
 }
 
 impl<A,R,F : Fn(&Fn(A) -> R, A) -> R> Fn<(A,)> for YCombinator<F,A,R> {
-    type Output = R;
-
     extern "rust-call" fn call(&self, (arg,): (A,)) -> R {
         (self.func)(self, arg)
     }
 }
 
+impl<A,R,F : Fn(&Fn(A) -> R, A) -> R> FnMut<(A,)> for YCombinator<F,A,R> {
+    extern "rust-call" fn call_mut(&mut self, args: (A,)) -> R { self.call(args) }
+}
+
+impl<A,R,F : Fn(&Fn(A) -> R, A) -> R> FnOnce<(A,)> for YCombinator<F,A,R> {
+    type Output = R;
+    extern "rust-call" fn call_once(self, args: (A,)) -> R { self.call(args) }
+}
+
 fn main() {
     let factorial = |recur: &Fn(u32) -> u32, arg: u32| -> u32 {
         if arg == 0 {1} else {arg * recur(arg-1)}
diff --git a/src/test/run-pass/unboxed-closures-manual-impl.rs b/src/test/run-pass/unboxed-closures-manual-impl.rs
index b505caf6dd8..38f15d6e449 100644
--- a/src/test/run-pass/unboxed-closures-manual-impl.rs
+++ b/src/test/run-pass/unboxed-closures-manual-impl.rs
@@ -17,13 +17,17 @@ use std::ops::FnMut;
 struct S;
 
 impl FnMut<(i32,)> for S {
-    type Output = i32;
-
     extern "rust-call" fn call_mut(&mut self, (x,): (i32,)) -> i32 {
         x * x
     }
 }
 
+impl FnOnce<(i32,)> for S {
+    type Output = i32;
+
+    extern "rust-call" fn call_once(mut self, args: (i32,)) -> i32 { self.call_mut(args) }
+}
+
 fn call_it<F:FnMut(i32)->i32>(mut f: F, x: i32) -> i32 {
     f(x) + 3
 }