Auto merge of #21019 - nikomatsakis:issue-20871-ret-as-assoc-type, r=nrc

Fixes https://github.com/rust-lang/rust/issues/20871

r? @aturon (at least until we decide definitively if this is a good idea)

76 files changed, 1098 insertions, 482 deletions

diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs
index e95087fa846..a090e4f24ce 100644
--- a/src/libcollections/btree/set.rs
+++ b/src/libcollections/btree/set.rs
@@ -758,7 +758,9 @@ mod test {
         expected: &'b [int],
     }
 
-    impl<'a, 'b, 'c> FnMut(&'c int) -> bool for Counter<'a, 'b> {
+    impl<'a, 'b, 'c> FnMut<(&'c int,)> for Counter<'a, 'b> {
+        type Output = bool;
+
         extern "rust-call" fn call_mut(&mut self, (&x,): (&'c int,)) -> bool {
             assert_eq!(x, self.expected[*self.i]);
             *self.i += 1;
diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs
index d482888e3bc..0e99a2c9c3e 100644
--- a/src/libcore/ops.rs
+++ b/src/libcore/ops.rs
@@ -1117,29 +1117,33 @@ impl<'a, T: ?Sized> DerefMut for &'a mut T {
 #[lang="fn"]
 #[unstable(feature = "core",
            reason = "uncertain about variadic generics, input versus associated types")]
-pub trait Fn<Args,Result> {
+#[cfg(stage0)]
+pub trait Fn<Args,Output> {
     /// This is called when the call operator is used.
-    extern "rust-call" fn call(&self, args: Args) -> Result;
+    extern "rust-call" fn call(&self, args: Args) -> Output;
 }
 
 /// A version of the call operator that takes a mutable receiver.
 #[lang="fn_mut"]
 #[unstable(feature = "core",
            reason = "uncertain about variadic generics, input versus associated types")]
-pub trait FnMut<Args,Result> {
+#[cfg(stage0)]
+pub trait FnMut<Args,Output> {
     /// This is called when the call operator is used.
-    extern "rust-call" fn call_mut(&mut self, args: Args) -> Result;
+    extern "rust-call" fn call_mut(&mut self, args: Args) -> Output;
 }
 
 /// A version of the call operator that takes a by-value receiver.
 #[lang="fn_once"]
 #[unstable(feature = "core",
            reason = "uncertain about variadic generics, input versus associated types")]
-pub trait FnOnce<Args,Result> {
+#[cfg(stage0)]
+pub trait FnOnce<Args,Output> {
     /// This is called when the call operator is used.
-    extern "rust-call" fn call_once(self, args: Args) -> Result;
+    extern "rust-call" fn call_once(self, args: Args) -> Output;
 }
 
+#[cfg(stage0)]
 impl<F: ?Sized, A, R> FnMut<A, R> for F
     where F : Fn<A, R>
 {
@@ -1148,6 +1152,7 @@ impl<F: ?Sized, A, R> FnMut<A, R> for F
     }
 }
 
+#[cfg(stage0)]
 impl<F,A,R> FnOnce<A,R> for F
     where F : FnMut<A,R>
 {
@@ -1155,3 +1160,61 @@ impl<F,A,R> FnOnce<A,R> for F
         self.call_mut(args)
     }
 }
+
+/// A version of the call operator that takes an immutable receiver.
+#[lang="fn"]
+#[unstable(feature = "core",
+           reason = "uncertain about variadic generics, input versus associated types")]
+#[cfg(not(stage0))]
+pub trait Fn<Args> {
+    type Output;
+
+    /// 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"]
+#[unstable(feature = "core",
+           reason = "uncertain about variadic generics, input versus associated types")]
+#[cfg(not(stage0))]
+pub trait FnMut<Args> {
+    type Output;
+
+    /// 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"]
+#[unstable(feature = "core",
+           reason = "uncertain about variadic generics, input versus associated types")]
+#[cfg(not(stage0))]
+pub trait FnOnce<Args> {
+    type Output;
+
+    /// This is called when the call operator is used.
+    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
+}
+
+#[cfg(not(stage0))]
+impl<F: ?Sized, A> FnMut<A> for F
+    where F : Fn<A>
+{
+    type Output = <F as Fn<A>>::Output;
+
+    extern "rust-call" fn call_mut(&mut self, args: A) -> <F as Fn<A>>::Output {
+        self.call(args)
+    }
+}
+
+#[cfg(not(stage0))]
+impl<F,A> FnOnce<A> for F
+    where F : FnMut<A>
+{
+    type Output = <F as FnMut<A>>::Output;
+
+    extern "rust-call" fn call_once(mut self, args: A) -> <F as FnMut<A>>::Output {
+        self.call_mut(args)
+    }
+}
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index 5b94733ea6f..101d349c351 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -461,6 +461,7 @@ delegate_iter!{exact u8 : Bytes<'a>}
 #[derive(Copy, Clone)]
 struct BytesDeref;
 
+#[cfg(stage0)]
 impl<'a> Fn(&'a u8) -> u8 for BytesDeref {
     #[inline]
     extern "rust-call" fn call(&self, (ptr,): (&'a u8,)) -> u8 {
@@ -468,6 +469,16 @@ impl<'a> Fn(&'a u8) -> u8 for BytesDeref {
     }
 }
 
+#[cfg(not(stage0))]
+impl<'a> Fn<(&'a u8,)> for BytesDeref {
+    type Output = u8;
+
+    #[inline]
+    extern "rust-call" fn call(&self, (ptr,): (&'a u8,)) -> u8 {
+        *ptr
+    }
+}
+
 /// An iterator over the substrings of a string, separated by `sep`.
 #[derive(Clone)]
 struct CharSplits<'a, Sep> {
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index 091ef9d52eb..af41844b2df 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -904,8 +904,8 @@ impl<'a, 'tcx> rbml_writer_helpers<'tcx> for Encoder<'a> {
                             try!(this.emit_struct_field("method_num", 0, |this| {
                                 this.emit_uint(o.method_num)
                             }));
-                            try!(this.emit_struct_field("real_index", 0, |this| {
-                                this.emit_uint(o.real_index)
+                            try!(this.emit_struct_field("vtable_index", 0, |this| {
+                                this.emit_uint(o.vtable_index)
                             }));
                             Ok(())
                         })
@@ -1492,8 +1492,8 @@ impl<'a, 'tcx> rbml_decoder_decoder_helpers<'tcx> for reader::Decoder<'a> {
                                             this.read_uint()
                                         }).unwrap()
                                     },
-                                    real_index: {
-                                        this.read_struct_field("real_index", 3, |this| {
+                                    vtable_index: {
+                                        this.read_struct_field("vtable_index", 3, |this| {
                                             this.read_uint()
                                         }).unwrap()
                                     },
diff --git a/src/librustc/middle/traits/error_reporting.rs b/src/librustc/middle/traits/error_reporting.rs
index 7ccb5e6e711..5e7168b6735 100644
--- a/src/librustc/middle/traits/error_reporting.rs
+++ b/src/librustc/middle/traits/error_reporting.rs
@@ -408,7 +408,7 @@ fn note_obligation_cause_code<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
         }
         ObligationCauseCode::CompareImplMethodObligation => {
             span_note!(tcx.sess, cause_span,
-                      "the requirement `{}` appears on the impl method\
+                      "the requirement `{}` appears on the impl method \
                       but not on the corresponding trait method",
                       predicate.user_string(infcx.tcx));
         }
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 8d3888fcfdb..82a4a60cebb 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -18,7 +18,7 @@ pub use self::ObligationCauseCode::*;
 use middle::mem_categorization::Typer;
 use middle::subst;
 use middle::ty::{self, Ty};
-use middle::infer::InferCtxt;
+use middle::infer::{self, InferCtxt};
 use std::slice::Iter;
 use std::rc::Rc;
 use syntax::ast;
@@ -392,6 +392,65 @@ pub fn type_known_to_meet_builtin_bound<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
     }
 }
 
+pub fn normalize_param_env_or_error<'a,'tcx>(unnormalized_env: ty::ParameterEnvironment<'a,'tcx>,
+                                             cause: ObligationCause<'tcx>)
+                                             -> ty::ParameterEnvironment<'a,'tcx>
+{
+    match normalize_param_env(&unnormalized_env, cause) {
+        Ok(p) => p,
+        Err(errors) => {
+            // I'm not wild about reporting errors here; I'd prefer to
+            // have the errors get reported at a defined place (e.g.,
+            // during typeck). Instead I have all parameter
+            // environments, in effect, going through this function
+            // and hence potentially reporting errors. This ensurse of
+            // course that we never forget to normalize (the
+            // alternative seemed like it would involve a lot of
+            // manual invocations of this fn -- and then we'd have to
+            // deal with the errors at each of those sites).
+            //
+            // In any case, in practice, typeck constructs all the
+            // parameter environments once for every fn as it goes,
+            // and errors will get reported then; so after typeck we
+            // can be sure that no errors should occur.
+            let infcx = infer::new_infer_ctxt(unnormalized_env.tcx);
+            report_fulfillment_errors(&infcx, &errors);
+
+            // Normalized failed? use what they gave us, it's better than nothing.
+            unnormalized_env
+        }
+    }
+}
+
+pub fn normalize_param_env<'a,'tcx>(param_env: &ty::ParameterEnvironment<'a,'tcx>,
+                                    cause: ObligationCause<'tcx>)
+                                    -> Result<ty::ParameterEnvironment<'a,'tcx>,
+                                              Vec<FulfillmentError<'tcx>>>
+{
+    let tcx = param_env.tcx;
+
+    debug!("normalize_param_env(param_env={})",
+           param_env.repr(tcx));
+
+    let predicates: Vec<ty::Predicate<'tcx>> = {
+        let infcx = infer::new_infer_ctxt(tcx);
+        let mut selcx = &mut SelectionContext::new(&infcx, param_env);
+        let mut fulfill_cx = FulfillmentContext::new();
+        let Normalized { value: predicates, obligations } =
+            project::normalize(selcx, cause, &param_env.caller_bounds);
+        for obligation in obligations.into_iter() {
+            fulfill_cx.register_predicate_obligation(selcx.infcx(), obligation);
+        }
+        try!(fulfill_cx.select_all_or_error(selcx.infcx(), param_env));
+        predicates.iter().map(|p| infcx.resolve_type_vars_if_possible(p)).collect()
+    };
+
+    debug!("normalize_param_env: predicates={}",
+           predicates.repr(tcx));
+
+    Ok(param_env.with_caller_bounds(predicates))
+}
+
 impl<'tcx,O> Obligation<'tcx,O> {
     pub fn new(cause: ObligationCause<'tcx>,
                trait_ref: O)
diff --git a/src/librustc/middle/traits/object_safety.rs b/src/librustc/middle/traits/object_safety.rs
index c0399112c33..56c1419502f 100644
--- a/src/librustc/middle/traits/object_safety.rs
+++ b/src/librustc/middle/traits/object_safety.rs
@@ -122,17 +122,15 @@ fn trait_has_sized_self<'tcx>(tcx: &ty::ctxt<'tcx>,
                               trait_def_id: ast::DefId)
                               -> bool
 {
-    let trait_def = ty::lookup_trait_def(tcx, trait_def_id);
-    let param_env = ty::construct_parameter_environment(tcx,
-                                                        &trait_def.generics,
-                                                        ast::DUMMY_NODE_ID);
-    let predicates = param_env.caller_bounds.predicates.as_slice().to_vec();
     let sized_def_id = match tcx.lang_items.sized_trait() {
         Some(def_id) => def_id,
         None => { return false; /* No Sized trait, can't require it! */ }
     };
 
     // Search for a predicate like `Self : Sized` amongst the trait bounds.
+    let trait_def = ty::lookup_trait_def(tcx, trait_def_id);
+    let free_substs = ty::construct_free_substs(tcx, &trait_def.generics, ast::DUMMY_NODE_ID);
+    let predicates = trait_def.generics.to_bounds(tcx, &free_substs).predicates.into_vec();
     elaborate_predicates(tcx, predicates)
         .any(|predicate| {
             match predicate {
diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs
index c179153dbde..d1dd086a5a3 100644
--- a/src/librustc/middle/traits/project.rs
+++ b/src/librustc/middle/traits/project.rs
@@ -18,13 +18,17 @@ use super::PredicateObligation;
 use super::SelectionContext;
 use super::SelectionError;
 use super::VtableImplData;
+use super::util;
 
 use middle::infer;
-use middle::subst::Subst;
+use middle::subst::{Subst, Substs};
 use middle::ty::{self, AsPredicate, ReferencesError, RegionEscape,
                  HasProjectionTypes, ToPolyTraitRef, Ty};
 use middle::ty_fold::{self, TypeFoldable, TypeFolder};
 use std::rc::Rc;
+use syntax::ast;
+use syntax::parse::token;
+use util::common::FN_OUTPUT_NAME;
 use util::ppaux::Repr;
 
 pub type PolyProjectionObligation<'tcx> =
@@ -53,6 +57,8 @@ pub struct MismatchedProjectionTypes<'tcx> {
 enum ProjectionTyCandidate<'tcx> {
     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
     Impl(VtableImplData<'tcx, PredicateObligation<'tcx>>),
+    Closure(ast::DefId, Substs<'tcx>),
+    FnPointer(Ty<'tcx>),
 }
 
 struct ProjectionTyCandidateSet<'tcx> {
@@ -60,6 +66,11 @@ struct ProjectionTyCandidateSet<'tcx> {
     ambiguous: bool
 }
 
+/// Evaluates constraints of the form:
+///
+///     for<...> <T as Trait>::U == V
+///
+/// If successful, this may result in additional obligations.
 pub fn poly_project_and_unify_type<'cx,'tcx>(
     selcx: &mut SelectionContext<'cx,'tcx>,
     obligation: &PolyProjectionObligation<'tcx>)
@@ -102,8 +113,11 @@ pub fn poly_project_and_unify_type<'cx,'tcx>(
     }
 }
 
-/// Compute result of projecting an associated type and unify it with
-/// `obligation.predicate.ty` (if we can).
+/// Evaluates constraints of the form:
+///
+///     <T as Trait>::U == V
+///
+/// If successful, this may result in additional obligations.
 fn project_and_unify_type<'cx,'tcx>(
     selcx: &mut SelectionContext<'cx,'tcx>,
     obligation: &ProjectionObligation<'tcx>)
@@ -133,6 +147,10 @@ fn project_and_unify_type<'cx,'tcx>(
     }
 }
 
+/// Normalizes any associated type projections in `value`, replacing
+/// them with a fully resolved type where possible. The return value
+/// combines the normalized result and any additional obligations that
+/// were incurred as result.
 pub fn normalize<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
                                cause: ObligationCause<'tcx>,
                                value: &T)
@@ -142,6 +160,7 @@ pub fn normalize<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
     normalize_with_depth(selcx, cause, 0, value)
 }
 
+/// As `normalize`, but with a custom depth.
 pub fn normalize_with_depth<'a,'b,'tcx,T>(selcx: &'a mut SelectionContext<'b,'tcx>,
                                           cause: ObligationCause<'tcx>,
                                           depth: uint,
@@ -251,6 +270,12 @@ impl<'tcx,T> Normalized<'tcx,T> {
     }
 }
 
+/// The guts of `normalize`: normalize a specific projection like `<T
+/// as Trait>::Item`. The result is always a type (and possibly
+/// additional obligations). If ambiguity arises, which implies that
+/// there are unresolved type variables in the projection, we will
+/// substitute a fresh type variable `$X` and generate a new
+/// obligation `<T as Trait>::Item == $X` for later.
 pub fn normalize_projection_type<'a,'b,'tcx>(
     selcx: &'a mut SelectionContext<'b,'tcx>,
     projection_ty: ty::ProjectionTy<'tcx>,
@@ -277,6 +302,10 @@ pub fn normalize_projection_type<'a,'b,'tcx>(
         })
 }
 
+/// The guts of `normalize`: normalize a specific projection like `<T
+/// as Trait>::Item`. The result is always a type (and possibly
+/// additional obligations). Returns `None` in the case of ambiguity,
+/// which indicates that there are unbound type variables.
 fn opt_normalize_projection_type<'a,'b,'tcx>(
     selcx: &'a mut SelectionContext<'b,'tcx>,
     projection_ty: ty::ProjectionTy<'tcx>,
@@ -440,8 +469,7 @@ fn assemble_candidates_from_param_env<'cx,'tcx>(
     obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>,
     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 {
-    let env_predicates = selcx.param_env().caller_bounds.predicates.clone();
-    let env_predicates = env_predicates.iter().cloned().collect();
+    let env_predicates = selcx.param_env().caller_bounds.clone();
     assemble_candidates_from_predicates(selcx, obligation, obligation_trait_ref,
                                         candidate_set, env_predicates);
 }
@@ -464,20 +492,22 @@ fn assemble_candidates_from_predicates<'cx,'tcx>(
 
                 let is_match = same_name && infcx.probe(|_| {
                     let origin = infer::Misc(obligation.cause.span);
-                    let obligation_poly_trait_ref =
-                        obligation_trait_ref.to_poly_trait_ref();
                     let data_poly_trait_ref =
                         data.to_poly_trait_ref();
+                    let obligation_poly_trait_ref =
+                        obligation_trait_ref.to_poly_trait_ref();
                     infcx.sub_poly_trait_refs(false,
                                               origin,
-                                              obligation_poly_trait_ref,
-                                              data_poly_trait_ref).is_ok()
+                                              data_poly_trait_ref,
+                                              obligation_poly_trait_ref).is_ok()
                 });
 
-                if is_match {
-                    debug!("assemble_candidates_from_predicates: candidate {}",
-                           data.repr(selcx.tcx()));
+                debug!("assemble_candidates_from_predicates: candidate {} is_match {} same_name {}",
+                       data.repr(selcx.tcx()),
+                       is_match,
+                       same_name);
 
+                if is_match {
                     candidate_set.vec.push(
                         ProjectionTyCandidate::ParamEnv(data.clone()));
                 }
@@ -551,6 +581,14 @@ fn assemble_candidates_from_impls<'cx,'tcx>(
                 selcx, obligation, obligation_trait_ref, candidate_set,
                 data.object_ty);
         }
+        super::VtableClosure(closure_def_id, substs) => {
+            candidate_set.vec.push(
+                ProjectionTyCandidate::Closure(closure_def_id, substs));
+        }
+        super::VtableFnPointer(fn_type) => {
+            candidate_set.vec.push(
+                ProjectionTyCandidate::FnPointer(fn_type));
+        }
         super::VtableParam(..) => {
             // This case tell us nothing about the value of an
             // associated type. Consider:
@@ -578,9 +616,7 @@ fn assemble_candidates_from_impls<'cx,'tcx>(
             // projection. And the projection where clause is handled
             // in `assemble_candidates_from_param_env`.
         }
-        super::VtableBuiltin(..) |
-        super::VtableClosure(..) |
-        super::VtableFnPointer(..) => {
+        super::VtableBuiltin(..) => {
             // These traits have no associated types.
             selcx.tcx().sess.span_bug(
                 obligation.cause.span,
@@ -606,67 +642,150 @@ fn confirm_candidate<'cx,'tcx>(
 
     match candidate {
         ProjectionTyCandidate::ParamEnv(poly_projection) => {
-            let projection =
-                infcx.replace_late_bound_regions_with_fresh_var(
-                    obligation.cause.span,
-                    infer::LateBoundRegionConversionTime::HigherRankedType,
-                    &poly_projection).0;
-
-            assert_eq!(projection.projection_ty.item_name,
-                       obligation.predicate.item_name);
-
-            let origin = infer::RelateOutputImplTypes(obligation.cause.span);
-            match infcx.sub_trait_refs(false,
-                                       origin,
-                                       obligation.predicate.trait_ref.clone(),
-                                       projection.projection_ty.trait_ref.clone()) {
-                Ok(()) => { }
-                Err(e) => {
-                    selcx.tcx().sess.span_bug(
-                        obligation.cause.span,
-                        format!("Failed to unify `{}` and `{}` in projection: {}",
-                                obligation.repr(selcx.tcx()),
-                                projection.repr(selcx.tcx()),
-                                ty::type_err_to_str(selcx.tcx(), &e)).as_slice());
-                }
-            }
-
-            (projection.ty, vec!())
+            confirm_param_env_candidate(selcx, obligation, poly_projection)
         }
 
         ProjectionTyCandidate::Impl(impl_vtable) => {
-            // there don't seem to be nicer accessors to these:
-            let impl_items_map = selcx.tcx().impl_items.borrow();
-            let impl_or_trait_items_map = selcx.tcx().impl_or_trait_items.borrow();
-
-            let impl_items = &impl_items_map[impl_vtable.impl_def_id];
-            let mut impl_ty = None;
-            for impl_item in impl_items.iter() {
-                let assoc_type = match impl_or_trait_items_map[impl_item.def_id()] {
-                    ty::TypeTraitItem(ref assoc_type) => assoc_type.clone(),
-                    ty::MethodTraitItem(..) => { continue; }
-                };
-
-                if assoc_type.name != obligation.predicate.item_name {
-                    continue;
-                }
+            confirm_impl_candidate(selcx, obligation, impl_vtable)
+        }
 
-                let impl_poly_ty = ty::lookup_item_type(selcx.tcx(), assoc_type.def_id);
-                impl_ty = Some(impl_poly_ty.ty.subst(selcx.tcx(), &impl_vtable.substs));
-                break;
-            }
+        ProjectionTyCandidate::Closure(def_id, substs) => {
+            confirm_closure_candidate(selcx, obligation, def_id, &substs)
+        }
 
-            match impl_ty {
-                Some(ty) => (ty, impl_vtable.nested.into_vec()),
-                None => {
-                    // This means that the impl is missing a
-                    // definition for the associated type. This error
-                    // ought to be reported by the type checker method
-                    // `check_impl_items_against_trait`, so here we
-                    // just return ty_err.
-                    (selcx.tcx().types.err, vec!())
-                }
-            }
+        ProjectionTyCandidate::FnPointer(fn_type) => {
+            confirm_fn_pointer_candidate(selcx, obligation, fn_type)
+        }
+    }
+}
+
+fn confirm_fn_pointer_candidate<'cx,'tcx>(
+    selcx: &mut SelectionContext<'cx,'tcx>,
+    obligation: &ProjectionTyObligation<'tcx>,
+    fn_type: Ty<'tcx>)
+    -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
+{
+    let fn_type = selcx.infcx().shallow_resolve(fn_type);
+    let sig = ty::ty_fn_sig(fn_type);
+    confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
+}
+
+fn confirm_closure_candidate<'cx,'tcx>(
+    selcx: &mut SelectionContext<'cx,'tcx>,
+    obligation: &ProjectionTyObligation<'tcx>,
+    closure_def_id: ast::DefId,
+    substs: &Substs<'tcx>)
+    -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
+{
+    let closure_typer = selcx.closure_typer();
+    let closure_type = closure_typer.closure_type(closure_def_id, substs);
+    confirm_callable_candidate(selcx, obligation, &closure_type.sig, util::TupleArgumentsFlag::No)
+}
+
+fn confirm_callable_candidate<'cx,'tcx>(
+    selcx: &mut SelectionContext<'cx,'tcx>,
+    obligation: &ProjectionTyObligation<'tcx>,
+    fn_sig: &ty::PolyFnSig<'tcx>,
+    flag: util::TupleArgumentsFlag)
+    -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
+{
+    let tcx = selcx.tcx();
+
+    debug!("confirm_closure_candidate({},{})",
+           obligation.repr(tcx),
+           fn_sig.repr(tcx));
+
+    // 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,
+                                                obligation.predicate.trait_ref.self_ty(),
+                                                fn_sig,
+                                                flag);
+
+    let predicate = ty::Binder(ty::ProjectionPredicate { // (1) recreate binder here
+        projection_ty: ty::ProjectionTy {
+            trait_ref: trait_ref,
+            item_name: token::intern(FN_OUTPUT_NAME),
+        },
+        ty: ret_type
+    });
+
+    confirm_param_env_candidate(selcx, obligation, predicate)
+}
+
+fn confirm_param_env_candidate<'cx,'tcx>(
+    selcx: &mut SelectionContext<'cx,'tcx>,
+    obligation: &ProjectionTyObligation<'tcx>,
+    poly_projection: ty::PolyProjectionPredicate<'tcx>)
+    -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
+{
+    let infcx = selcx.infcx();
+
+    let projection =
+        infcx.replace_late_bound_regions_with_fresh_var(
+            obligation.cause.span,
+            infer::LateBoundRegionConversionTime::HigherRankedType,
+            &poly_projection).0;
+
+    assert_eq!(projection.projection_ty.item_name,
+               obligation.predicate.item_name);
+
+    let origin = infer::RelateOutputImplTypes(obligation.cause.span);
+    match infcx.sub_trait_refs(false,
+                               origin,
+                               obligation.predicate.trait_ref.clone(),
+                               projection.projection_ty.trait_ref.clone()) {
+        Ok(()) => { }
+        Err(e) => {
+            selcx.tcx().sess.span_bug(
+                obligation.cause.span,
+                format!("Failed to unify `{}` and `{}` in projection: {}",
+                        obligation.repr(selcx.tcx()),
+                        projection.repr(selcx.tcx()),
+                        ty::type_err_to_str(selcx.tcx(), &e)).as_slice());
+        }
+    }
+
+    (projection.ty, vec!())
+}
+
+fn confirm_impl_candidate<'cx,'tcx>(
+    selcx: &mut SelectionContext<'cx,'tcx>,
+    obligation: &ProjectionTyObligation<'tcx>,
+    impl_vtable: VtableImplData<'tcx, PredicateObligation<'tcx>>)
+    -> (Ty<'tcx>, Vec<PredicateObligation<'tcx>>)
+{
+    // there don't seem to be nicer accessors to these:
+    let impl_items_map = selcx.tcx().impl_items.borrow();
+    let impl_or_trait_items_map = selcx.tcx().impl_or_trait_items.borrow();
+
+    let impl_items = &impl_items_map[impl_vtable.impl_def_id];
+    let mut impl_ty = None;
+    for impl_item in impl_items.iter() {
+        let assoc_type = match impl_or_trait_items_map[impl_item.def_id()] {
+            ty::TypeTraitItem(ref assoc_type) => assoc_type.clone(),
+            ty::MethodTraitItem(..) => { continue; }
+        };
+
+        if assoc_type.name != obligation.predicate.item_name {
+            continue;
+        }
+
+        let impl_poly_ty = ty::lookup_item_type(selcx.tcx(), assoc_type.def_id);
+        impl_ty = Some(impl_poly_ty.ty.subst(selcx.tcx(), &impl_vtable.substs));
+        break;
+    }
+
+    match impl_ty {
+        Some(ty) => (ty, impl_vtable.nested.into_vec()),
+        None => {
+            // This means that the impl is missing a
+            // definition for the associated type. This error
+            // ought to be reported by the type checker method
+            // `check_impl_items_against_trait`, so here we
+            // just return ty_err.
+            (selcx.tcx().types.err, vec!())
         }
     }
 }
@@ -688,7 +807,11 @@ impl<'tcx> Repr<'tcx> for ProjectionTyCandidate<'tcx> {
             ProjectionTyCandidate::ParamEnv(ref data) =>
                 format!("ParamEnv({})", data.repr(tcx)),
             ProjectionTyCandidate::Impl(ref data) =>
-                format!("Impl({})", data.repr(tcx))
+                format!("Impl({})", data.repr(tcx)),
+            ProjectionTyCandidate::Closure(ref a, ref b) =>
+                format!("Closure(({},{}))", a.repr(tcx), b.repr(tcx)),
+            ProjectionTyCandidate::FnPointer(a) =>
+                format!("FnPointer(({}))", a.repr(tcx)),
         }
     }
 }
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index b18cb86a2f4..4d5f3d925b0 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -214,6 +214,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         self.closure_typer.param_env()
     }
 
+    pub fn closure_typer(&self) -> &'cx (ty::ClosureTyper<'tcx>+'cx) {
+        self.closure_typer
+    }
+
     ///////////////////////////////////////////////////////////////////////////
     // Selection
     //
@@ -951,7 +955,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                stack.obligation.repr(self.tcx()));
 
         let caller_trait_refs: Vec<_> =
-            self.param_env().caller_bounds.predicates.iter()
+            self.param_env().caller_bounds.iter()
             .filter_map(|o| o.to_opt_poly_trait_ref())
             .collect();
 
@@ -1913,33 +1917,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                obligation.repr(self.tcx()));
 
         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
-        let sig = match self_ty.sty {
-            ty::ty_bare_fn(_, &ty::BareFnTy {
-                unsafety: ast::Unsafety::Normal,
-                abi: abi::Rust,
-                ref sig
-            }) => {
-                sig
-            }
-            _ => {
-                self.tcx().sess.span_bug(
-                    obligation.cause.span,
-                    &format!("Fn pointer candidate for inappropriate self type: {}",
-                            self_ty.repr(self.tcx()))[]);
-            }
-        };
-
-        let arguments_tuple = ty::mk_tup(self.tcx(), sig.0.inputs.to_vec());
-        let output_type = sig.0.output.unwrap();
-        let substs =
-            Substs::new_trait(
-                vec![arguments_tuple, output_type],
-                vec![],
-                self_ty);
-        let trait_ref = ty::Binder(Rc::new(ty::TraitRef {
-            def_id: obligation.predicate.def_id(),
-            substs: self.tcx().mk_substs(substs),
-        }));
+        let sig = ty::ty_fn_sig(self_ty);
+        let ty::Binder((trait_ref, _)) =
+            util::closure_trait_ref_and_return_type(self.tcx(),
+                                                    obligation.predicate.def_id(),
+                                                    self_ty,
+                                                    sig,
+                                                    util::TupleArgumentsFlag::Yes);
+        let trait_ref = ty::Binder(trait_ref);
 
         try!(self.confirm_poly_trait_refs(obligation.cause.clone(),
                                           obligation.predicate.to_poly_trait_ref(),
@@ -1958,23 +1943,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                closure_def_id.repr(self.tcx()),
                substs.repr(self.tcx()));
 
-        let closure_type = self.closure_typer.closure_type(closure_def_id, substs);
-
-        debug!("confirm_closure_candidate: closure_def_id={} closure_type={}",
-               closure_def_id.repr(self.tcx()),
-               closure_type.repr(self.tcx()));
-
-        let closure_sig = &closure_type.sig;
-        let arguments_tuple = closure_sig.0.inputs[0];
-        let trait_substs =
-            Substs::new_trait(
-                vec![arguments_tuple, closure_sig.0.output.unwrap()],
-                vec![],
-                obligation.self_ty());
-        let trait_ref = ty::Binder(Rc::new(ty::TraitRef {
-            def_id: obligation.predicate.def_id(),
-            substs: self.tcx().mk_substs(trait_substs),
-        }));
+        let trait_ref = self.closure_trait_ref(obligation,
+                                               closure_def_id,
+                                               substs);
 
         debug!("confirm_closure_candidate(closure_def_id={}, trait_ref={})",
                closure_def_id.repr(self.tcx()),
@@ -2157,16 +2128,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                     where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
                                     -> Result<Vec<PredicateObligation<'tcx>>,()>
     {
-        let where_clause_trait_ref =
-            project::normalize_with_depth(self,
-                                          obligation.cause.clone(),
-                                          obligation.recursion_depth+1,
-                                          &where_clause_trait_ref);
-
         let () =
-            try!(self.match_poly_trait_ref(obligation, where_clause_trait_ref.value.clone()));
+            try!(self.match_poly_trait_ref(obligation, where_clause_trait_ref));
 
-        Ok(where_clause_trait_ref.obligations)
+        Ok(Vec::new())
     }
 
     /// Returns `Ok` if `poly_trait_ref` being true implies that the
@@ -2286,6 +2251,29 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
+    fn closure_trait_ref(&self,
+                         obligation: &TraitObligation<'tcx>,
+                         closure_def_id: ast::DefId,
+                         substs: &Substs<'tcx>)
+                         -> ty::PolyTraitRef<'tcx>
+    {
+        let closure_type = self.closure_typer.closure_type(closure_def_id, substs);
+        let ty::Binder((trait_ref, _)) =
+            util::closure_trait_ref_and_return_type(self.tcx(),
+                                                    obligation.predicate.def_id(),
+                                                    obligation.predicate.0.self_ty(), // (1)
+                                                    &closure_type.sig,
+                                                    util::TupleArgumentsFlag::No);
+
+        // (1) Feels icky to skip the binder here, but OTOH we know
+        // that the self-type is an unboxed closure type and hence is
+        // in fact unparameterized (or at least does not reference any
+        // regions bound in the obligation). Still probably some
+        // refactoring could make this nicer.
+
+        ty::Binder(trait_ref)
+    }
+
     fn impl_obligations(&mut self,
                         cause: ObligationCause<'tcx>,
                         recursion_depth: uint,
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index beb28260834..edeca83d569 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -329,28 +329,67 @@ pub fn upcast<'tcx>(tcx: &ty::ctxt<'tcx>,
 pub fn get_vtable_index_of_object_method<'tcx>(tcx: &ty::ctxt<'tcx>,
                                                object_trait_ref: ty::PolyTraitRef<'tcx>,
                                                trait_def_id: ast::DefId,
-                                               method_index_in_trait: uint) -> uint {
+                                               method_offset_in_trait: uint) -> uint {
     // We need to figure the "real index" of the method in a
     // listing of all the methods of an object. We do this by
     // iterating down the supertraits of the object's trait until
     // we find the trait the method came from, counting up the
     // methods from them.
     let mut method_count = 0;
-    ty::each_bound_trait_and_supertraits(tcx, &[object_trait_ref], |bound_ref| {
+
+    for bound_ref in transitive_bounds(tcx, &[object_trait_ref]) {
         if bound_ref.def_id() == trait_def_id {
-            false
-        } else {
-            let trait_items = ty::trait_items(tcx, bound_ref.def_id());
-            for trait_item in trait_items.iter() {
-                match *trait_item {
-                    ty::MethodTraitItem(_) => method_count += 1,
-                    ty::TypeTraitItem(_) => {}
-                }
+            break;
+        }
+
+        let trait_items = ty::trait_items(tcx, bound_ref.def_id());
+        for trait_item in trait_items.iter() {
+            match *trait_item {
+                ty::MethodTraitItem(_) => method_count += 1,
+                ty::TypeTraitItem(_) => {}
             }
-            true
         }
+    }
+
+    // count number of methods preceding the one we are selecting and
+    // add them to the total offset; skip over associated types.
+    let trait_items = ty::trait_items(tcx, trait_def_id);
+    for trait_item in trait_items.iter().take(method_offset_in_trait) {
+        match *trait_item {
+            ty::MethodTraitItem(_) => method_count += 1,
+            ty::TypeTraitItem(_) => {}
+        }
+    }
+
+    // the item at the offset we were given really ought to be a method
+    assert!(match trait_items[method_offset_in_trait] {
+        ty::MethodTraitItem(_) => true,
+        ty::TypeTraitItem(_) => false
+    });
+
+    method_count
+}
+
+pub enum TupleArgumentsFlag { Yes, No }
+
+pub fn closure_trait_ref_and_return_type<'tcx>(
+    tcx: &ty::ctxt<'tcx>,
+    fn_trait_def_id: ast::DefId,
+    self_ty: Ty<'tcx>,
+    sig: &ty::PolyFnSig<'tcx>,
+    tuple_arguments: TupleArgumentsFlag)
+    -> ty::Binder<(Rc<ty::TraitRef<'tcx>>, Ty<'tcx>)>
+{
+    let arguments_tuple = match tuple_arguments {
+        TupleArgumentsFlag::No => sig.0.inputs[0],
+        TupleArgumentsFlag::Yes => ty::mk_tup(tcx, sig.0.inputs.to_vec()),
+    };
+    let trait_substs = Substs::new_trait(vec![arguments_tuple], vec![], self_ty);
+    let trait_ref = Rc::new(ty::TraitRef {
+        def_id: fn_trait_def_id,
+        substs: tcx.mk_substs(trait_substs),
     });
-    method_count + method_index_in_trait
+    ty::Binder((trait_ref, sig.0.output.unwrap()))
 }
 
 impl<'tcx,O:Repr<'tcx>> Repr<'tcx> for super::Obligation<'tcx, O> {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 86cf030c828..062ddd23d9d 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -452,7 +452,10 @@ pub struct MethodParam<'tcx> {
     // never contains bound regions; those regions should have been
     // instantiated with fresh variables at this point.
     pub trait_ref: Rc<ty::TraitRef<'tcx>>,
-    // index of uint in the list of methods for the trait
+
+    // index of uint in the list of trait items. Note that this is NOT
+    // the index into the vtable, because the list of trait items
+    // includes associated types.
     pub method_num: uint,
 
     /// The impl for the trait from which the method comes. This
@@ -471,14 +474,14 @@ pub struct MethodObject<'tcx> {
     // the actual base trait id of the object
     pub object_trait_id: ast::DefId,
 
-    // index of the method to be invoked amongst the trait's methods
+    // index of the method to be invoked amongst the trait's items
     pub method_num: uint,
 
     // index into the actual runtime vtable.
     // the vtable is formed by concatenating together the method lists of
-    // the base object trait and all supertraits;  this is the index into
+    // the base object trait and all supertraits; this is the index into
     // that vtable
-    pub real_index: uint,
+    pub vtable_index: uint,
 }
 
 #[derive(Clone)]
@@ -2084,11 +2087,7 @@ impl<'tcx> TraitRef<'tcx> {
 pub struct ParameterEnvironment<'a, 'tcx:'a> {
     pub tcx: &'a ctxt<'tcx>,
 
-    /// A substitution that can be applied to move from
-    /// the "outer" view of a type or method to the "inner" view.
-    /// In general, this means converting from bound parameters to
-    /// free parameters. Since we currently represent bound/free type
-    /// parameters in the same way, this only has an effect on regions.
+    /// See `construct_free_substs` for details.
     pub free_substs: Substs<'tcx>,
 
     /// Each type parameter has an implicit region bound that
@@ -2100,7 +2099,7 @@ pub struct ParameterEnvironment<'a, 'tcx:'a> {
     /// Obligations that the caller must satisfy. This is basically
     /// the set of bounds on the in-scope type parameters, translated
     /// into Obligations.
-    pub caller_bounds: ty::GenericBounds<'tcx>,
+    pub caller_bounds: Vec<ty::Predicate<'tcx>>,
 
     /// Caches the results of trait selection. This cache is used
     /// for things that have to do with the parameters in scope.
@@ -2108,6 +2107,19 @@ pub struct ParameterEnvironment<'a, 'tcx:'a> {
 }
 
 impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> {
+    pub fn with_caller_bounds(&self,
+                              caller_bounds: Vec<ty::Predicate<'tcx>>)
+                              -> ParameterEnvironment<'a,'tcx>
+    {
+        ParameterEnvironment {
+            tcx: self.tcx,
+            free_substs: self.free_substs.clone(),
+            implicit_region_bound: self.implicit_region_bound,
+            caller_bounds: caller_bounds,
+            selection_cache: traits::SelectionCache::new(),
+        }
+    }
+
     pub fn for_item(cx: &'a ctxt<'tcx>, id: NodeId) -> ParameterEnvironment<'a, 'tcx> {
         match cx.map.find(id) {
             Some(ast_map::NodeImplItem(ref impl_item)) => {
@@ -2119,6 +2131,7 @@ impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> {
                                 let method_generics = &method_ty.generics;
                                 construct_parameter_environment(
                                     cx,
+                                    method.span,
                                     method_generics,
                                     method.pe_body().id)
                             }
@@ -2153,6 +2166,7 @@ impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> {
                                 let method_generics = &method_ty.generics;
                                 construct_parameter_environment(
                                     cx,
+                                    method.span,
                                     method_generics,
                                     method.pe_body().id)
                             }
@@ -2179,6 +2193,7 @@ impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> {
                         let fn_pty = ty::lookup_item_type(cx, fn_def_id);
 
                         construct_parameter_environment(cx,
+                                                        item.span,
                                                         &fn_pty.generics,
                                                         body.id)
                     }
@@ -2189,7 +2204,7 @@ impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> {
                     ast::ItemStatic(..) => {
                         let def_id = ast_util::local_def(id);
                         let pty = ty::lookup_item_type(cx, def_id);
-                        construct_parameter_environment(cx, &pty.generics, id)
+                        construct_parameter_environment(cx, item.span, &pty.generics, id)
                     }
                     _ => {
                         cx.sess.span_bug(item.span,
@@ -6258,23 +6273,22 @@ impl Variance {
 pub fn empty_parameter_environment<'a,'tcx>(cx: &'a ctxt<'tcx>) -> ParameterEnvironment<'a,'tcx> {
     ty::ParameterEnvironment { tcx: cx,
                                free_substs: Substs::empty(),
-                               caller_bounds: GenericBounds::empty(),
+                               caller_bounds: Vec::new(),
                                implicit_region_bound: ty::ReEmpty,
                                selection_cache: traits::SelectionCache::new(), }
 }
 
-/// See `ParameterEnvironment` struct def'n for details
-pub fn construct_parameter_environment<'a,'tcx>(
+/// Constructs and returns a substitution that can be applied to move from
+/// the "outer" view of a type or method to the "inner" view.
+/// In general, this means converting from bound parameters to
+/// free parameters. Since we currently represent bound/free type
+/// parameters in the same way, this only has an effect on regions.
+pub fn construct_free_substs<'a,'tcx>(
     tcx: &'a ctxt<'tcx>,
     generics: &ty::Generics<'tcx>,
     free_id: ast::NodeId)
-    -> ParameterEnvironment<'a, 'tcx>
+    -> Substs<'tcx>
 {
-
-    //
-    // Construct the free substs.
-    //
-
     // map T => T
     let mut types = VecPerParamSpace::empty();
     push_types_from_defs(tcx, &mut types, generics.types.as_slice());
@@ -6283,11 +6297,45 @@ pub fn construct_parameter_environment<'a,'tcx>(
     let mut regions = VecPerParamSpace::empty();
     push_region_params(&mut regions, free_id, generics.regions.as_slice());
 
-    let free_substs = Substs {
+    return Substs {
         types: types,
         regions: subst::NonerasedRegions(regions)
     };
 
+    fn push_region_params(regions: &mut VecPerParamSpace<ty::Region>,
+                          free_id: ast::NodeId,
+                          region_params: &[RegionParameterDef])
+    {
+        for r in region_params.iter() {
+            regions.push(r.space, ty::free_region_from_def(free_id, r));
+        }
+    }
+
+    fn push_types_from_defs<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                  types: &mut VecPerParamSpace<Ty<'tcx>>,
+                                  defs: &[TypeParameterDef<'tcx>]) {
+        for def in defs.iter() {
+            debug!("construct_parameter_environment(): push_types_from_defs: def={:?}",
+                   def.repr(tcx));
+            let ty = ty::mk_param_from_def(tcx, def);
+            types.push(def.space, ty);
+       }
+    }
+}
+
+/// See `ParameterEnvironment` struct def'n for details
+pub fn construct_parameter_environment<'a,'tcx>(
+    tcx: &'a ctxt<'tcx>,
+    span: Span,
+    generics: &ty::Generics<'tcx>,
+    free_id: ast::NodeId)
+    -> ParameterEnvironment<'a, 'tcx>
+{
+    //
+    // Construct the free substs.
+    //
+
+    let free_substs = construct_free_substs(tcx, generics, free_id);
     let free_id_scope = region::CodeExtent::from_node_id(free_id);
 
     //
@@ -6296,6 +6344,7 @@ pub fn construct_parameter_environment<'a,'tcx>(
 
     let bounds = generics.to_bounds(tcx, &free_substs);
     let bounds = liberate_late_bound_regions(tcx, free_id_scope, &ty::Binder(bounds));
+    let predicates = bounds.predicates.into_vec();
 
     //
     // Compute region bounds. For now, these relations are stored in a
@@ -6303,45 +6352,42 @@ pub fn construct_parameter_environment<'a,'tcx>(
     // crazy about this scheme, but it's convenient, at least.
     //
 
-    record_region_bounds(tcx, &bounds);
+    record_region_bounds(tcx, &*predicates);
 
-    debug!("construct_parameter_environment: free_id={:?} free_subst={:?} bounds={:?}",
+    debug!("construct_parameter_environment: free_id={:?} free_subst={:?} predicates={:?}",
            free_id,
            free_substs.repr(tcx),
-           bounds.repr(tcx));
+           predicates.repr(tcx));
+
+    //
+    // Finally, we have to normalize the bounds in the environment, in
+    // case they contain any associated type projections. This process
+    // can yield errors if the put in illegal associated types, like
+    // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We
+    // report these errors right here; this doesn't actually feel
+    // right to me, because constructing the environment feels like a
+    // kind of a "idempotent" action, but I'm not sure where would be
+    // a better place. In practice, we construct environments for
+    // every fn once during type checking, and we'll abort if there
+    // are any errors at that point, so after type checking you can be
+    // sure that this will succeed without errors anyway.
+    //
 
-    return ty::ParameterEnvironment {
+    let unnormalized_env = ty::ParameterEnvironment {
         tcx: tcx,
         free_substs: free_substs,
         implicit_region_bound: ty::ReScope(free_id_scope),
-        caller_bounds: bounds,
+        caller_bounds: predicates,
         selection_cache: traits::SelectionCache::new(),
     };
 
-    fn push_region_params(regions: &mut VecPerParamSpace<ty::Region>,
-                          free_id: ast::NodeId,
-                          region_params: &[RegionParameterDef])
-    {
-        for r in region_params.iter() {
-            regions.push(r.space, ty::free_region_from_def(free_id, r));
-        }
-    }
-
-    fn push_types_from_defs<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                  types: &mut VecPerParamSpace<Ty<'tcx>>,
-                                  defs: &[TypeParameterDef<'tcx>]) {
-        for def in defs.iter() {
-            debug!("construct_parameter_environment(): push_types_from_defs: def={:?}",
-                   def.repr(tcx));
-            let ty = ty::mk_param_from_def(tcx, def);
-            types.push(def.space, ty);
-       }
-    }
+    let cause = traits::ObligationCause::misc(span, free_id);
+    return traits::normalize_param_env_or_error(unnormalized_env, cause);
 
-    fn record_region_bounds<'tcx>(tcx: &ty::ctxt<'tcx>, bounds: &GenericBounds<'tcx>) {
-        debug!("record_region_bounds(bounds={:?})", bounds.repr(tcx));
+    fn record_region_bounds<'tcx>(tcx: &ty::ctxt<'tcx>, predicates: &[ty::Predicate<'tcx>]) {
+        debug!("record_region_bounds(predicates={:?})", predicates.repr(tcx));
 
-        for predicate in bounds.predicates.iter() {
+        for predicate in predicates.iter() {
             match *predicate {
                 Predicate::Projection(..) |
                 Predicate::Trait(..) |
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 86552705963..69d32c3f5fc 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -71,7 +71,7 @@ pub trait TypeFolder<'tcx> : Sized {
     fn exit_region_binder(&mut self) { }
 
     fn fold_binder<T>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T>
-        where T : TypeFoldable<'tcx> + Repr<'tcx>
+        where T : TypeFoldable<'tcx> + Repr<'tcx> + Clone
     {
         // FIXME(#20526) this should replace `enter_region_binder`/`exit_region_binder`.
         super_fold_binder(self, t)
@@ -186,7 +186,7 @@ impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Vec<T> {
     }
 }
 
-impl<'tcx, T:TypeFoldable<'tcx>+Repr<'tcx>> TypeFoldable<'tcx> for ty::Binder<T> {
+impl<'tcx, T:TypeFoldable<'tcx>+Repr<'tcx>+Clone> TypeFoldable<'tcx> for ty::Binder<T> {
     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Binder<T> {
         folder.fold_binder(self)
     }
@@ -319,7 +319,7 @@ impl<'tcx> TypeFoldable<'tcx> for ty::MethodOrigin<'tcx> {
                     trait_ref: object.trait_ref.fold_with(folder),
                     object_trait_id: object.object_trait_id,
                     method_num: object.method_num,
-                    real_index: object.real_index
+                    vtable_index: object.vtable_index,
                 })
             }
         }
diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs
index 8915d55e206..bdb6ea22f8b 100644
--- a/src/librustc/util/common.rs
+++ b/src/librustc/util/common.rs
@@ -22,6 +22,9 @@ use syntax::ast;
 use syntax::visit;
 use syntax::visit::Visitor;
 
+// The name of the associated type for `Fn` return types
+pub const FN_OUTPUT_NAME: &'static str = "Output";
+
 // Useful type to use with `Result<>` indicate that an error has already
 // been reported to the user, so no need to continue checking.
 #[derive(Clone, Copy, Show)]
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 5601898136c..1be99a8e569 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -298,17 +298,9 @@ pub fn ty_to_string<'tcx>(cx: &ctxt<'tcx>, typ: &ty::TyS<'tcx>) -> String {
 
     fn closure_to_string<'tcx>(cx: &ctxt<'tcx>, cty: &ty::ClosureTy<'tcx>) -> String {
         let mut s = String::new();
-
-        match cty.unsafety {
-            ast::Unsafety::Normal => {}
-            ast::Unsafety::Unsafe => {
-                s.push_str(cty.unsafety.to_string().as_slice());
-                s.push(' ');
-            }
-        };
-
-        push_sig_to_string(cx, &mut s, '|', '|', &cty.sig);
-
+        s.push_str("[closure");
+        push_sig_to_string(cx, &mut s, '(', ')', &cty.sig);
+        s.push(']');
         s
     }
 
@@ -399,18 +391,10 @@ pub fn ty_to_string<'tcx>(cx: &ctxt<'tcx>, typ: &ty::TyS<'tcx>) -> String {
         ty_enum(did, substs) | ty_struct(did, substs) => {
             let base = ty::item_path_str(cx, did);
             let generics = ty::lookup_item_type(cx, did).generics;
-            parameterized(cx, base.as_slice(), substs, &generics, did)
+            parameterized(cx, base.as_slice(), substs, &generics, did, &[])
         }
-        ty_trait(box ty::TyTrait {
-            ref principal, ref bounds
-        }) => {
-            let principal = principal.user_string(cx);
-            let bound_str = bounds.user_string(cx);
-            let bound_sep = if bound_str.is_empty() { "" } else { " + " };
-            format!("{}{}{}",
-                    principal,
-                    bound_sep,
-                    bound_str)
+        ty_trait(ref data) => {
+            data.user_string(cx)
         }
         ty::ty_projection(ref data) => {
             format!("<{} as {}>::{}",
@@ -420,14 +404,15 @@ pub fn ty_to_string<'tcx>(cx: &ctxt<'tcx>, typ: &ty::TyS<'tcx>) -> String {
         }
         ty_str => "str".to_string(),
         ty_closure(ref did, _, substs) => {
-            cx.closures.borrow().get(did).map(|cl| {
+            let closures = cx.closures.borrow();
+            closures.get(did).map(|cl| {
                 closure_to_string(cx, &cl.closure_type.subst(cx, substs))
             }).unwrap_or_else(|| {
                 if did.krate == ast::LOCAL_CRATE {
                     let span = cx.map.span(did.node);
-                    format!("closure[{}]", span.repr(cx))
+                    format!("[closure {}]", span.repr(cx))
                 } else {
-                    format!("closure")
+                    format!("[closure]")
                 }
             })
         }
@@ -458,7 +443,8 @@ pub fn parameterized<'tcx>(cx: &ctxt<'tcx>,
                            base: &str,
                            substs: &subst::Substs<'tcx>,
                            generics: &ty::Generics<'tcx>,
-                           did: ast::DefId)
+                           did: ast::DefId,
+                           projections: &[ty::ProjectionPredicate<'tcx>])
                            -> String
 {
     if cx.sess.verbose() {
@@ -511,7 +497,20 @@ pub fn parameterized<'tcx>(cx: &ctxt<'tcx>,
         strs.push(ty_to_string(cx, *t))
     }
 
-    if cx.lang_items.fn_trait_kind(did).is_some() {
+    for projection in projections.iter() {
+        strs.push(format!("{}={}",
+                          projection.projection_ty.item_name.user_string(cx),
+                          projection.ty.user_string(cx)));
+    }
+
+    if cx.lang_items.fn_trait_kind(did).is_some() && projections.len() == 1 {
+        let projection_ty = projections[0].ty;
+        let tail =
+            if ty::type_is_nil(projection_ty) {
+                format!("")
+            } else {
+                format!(" -> {}", projection_ty.user_string(cx))
+            };
         format!("{}({}){}",
                 base,
                 if strs[0].starts_with("(") && strs[0].ends_with(",)") {
@@ -521,7 +520,7 @@ pub fn parameterized<'tcx>(cx: &ctxt<'tcx>,
                 } else {
                     &strs[0][]
                 },
-                if &*strs[1] == "()" { String::new() } else { format!(" -> {}", strs[1]) })
+                tail)
     } else if strs.len() > 0 {
         format!("{}<{}>", base, strs.connect(", "))
     } else {
@@ -623,6 +622,65 @@ impl<'tcx> Repr<'tcx> for def::Def {
     }
 }
 
+/// This curious type is here to help pretty-print trait objects. In
+/// a trait object, the projections are stored separately from the
+/// main trait bound, but in fact we want to package them together
+/// when printing out; they also have separate binders, but we want
+/// them to share a binder when we print them out. (And the binder
+/// pretty-printing logic is kind of clever and we don't want to
+/// reproduce it.) So we just repackage up the structure somewhat.
+///
+/// Right now there is only one trait in an object that can have
+/// projection bounds, so we just stuff them altogether. But in
+/// reality we should eventually sort things out better.
+type TraitAndProjections<'tcx> =
+    (Rc<ty::TraitRef<'tcx>>, Vec<ty::ProjectionPredicate<'tcx>>);
+
+impl<'tcx> UserString<'tcx> for TraitAndProjections<'tcx> {
+    fn user_string(&self, tcx: &ctxt<'tcx>) -> String {
+        let &(ref trait_ref, ref projection_bounds) = self;
+        let base = ty::item_path_str(tcx, trait_ref.def_id);
+        let trait_def = ty::lookup_trait_def(tcx, trait_ref.def_id);
+        parameterized(tcx,
+                      base.as_slice(),
+                      trait_ref.substs,
+                      &trait_def.generics,
+                      trait_ref.def_id,
+                      &projection_bounds[])
+    }
+}
+
+impl<'tcx> UserString<'tcx> for ty::TyTrait<'tcx> {
+    fn user_string(&self, tcx: &ctxt<'tcx>) -> String {
+        let &ty::TyTrait { ref principal, ref bounds } = self;
+
+        let mut components = vec![];
+
+        let tap: ty::Binder<TraitAndProjections<'tcx>> =
+            ty::Binder((principal.0.clone(),
+                        bounds.projection_bounds.iter().map(|x| x.0.clone()).collect()));
+
+        // Generate the main trait ref, including associated types.
+        components.push(tap.user_string(tcx));
+
+        // Builtin bounds.
+        for bound in bounds.builtin_bounds.iter() {
+            components.push(bound.user_string(tcx));
+        }
+
+        // Region, if not obviously implied by builtin bounds.
+        if bounds.region_bound != ty::ReStatic ||
+            !bounds.builtin_bounds.contains(&ty::BoundSend)
+        { // Region bound is implied by builtin bounds:
+            components.push(bounds.region_bound.user_string(tcx));
+        }
+
+        components.retain(|s| !s.is_empty());
+
+        components.connect(" + ")
+    }
+}
+
 impl<'tcx> Repr<'tcx> for ty::TypeParameterDef<'tcx> {
     fn repr(&self, tcx: &ctxt<'tcx>) -> String {
         format!("TypeParameterDef({:?}, {}, {:?}/{})",
@@ -701,12 +759,6 @@ impl<'tcx> Repr<'tcx> for ty::BuiltinBounds {
     }
 }
 
-impl<'tcx> Repr<'tcx> for ty::ExistentialBounds<'tcx> {
-    fn repr(&self, tcx: &ctxt<'tcx>) -> String {
-        self.user_string(tcx)
-    }
-}
-
 impl<'tcx> Repr<'tcx> for ty::ParamBounds<'tcx> {
     fn repr(&self, tcx: &ctxt<'tcx>) -> String {
         let mut res = Vec::new();
@@ -727,7 +779,8 @@ impl<'tcx> Repr<'tcx> for ty::TraitRef<'tcx> {
         let trait_def = ty::lookup_trait_def(tcx, self.def_id);
         format!("TraitRef({}, {})",
                 self.substs.self_ty().repr(tcx),
-                parameterized(tcx, base.as_slice(), self.substs, &trait_def.generics, self.def_id))
+                parameterized(tcx, base.as_slice(), self.substs,
+                              &trait_def.generics, self.def_id, &[]))
     }
 }
 
@@ -1062,7 +1115,7 @@ impl<'tcx> Repr<'tcx> for ty::MethodObject<'tcx> {
         format!("MethodObject({},{},{})",
                 self.trait_ref.repr(tcx),
                 self.method_num,
-                self.real_index)
+                self.vtable_index)
     }
 }
 
@@ -1110,14 +1163,8 @@ impl<'tcx> UserString<'tcx> for ty::ParamBounds<'tcx> {
     }
 }
 
-impl<'tcx> UserString<'tcx> for ty::ExistentialBounds<'tcx> {
-    fn user_string(&self, tcx: &ctxt<'tcx>) -> String {
-        if self.builtin_bounds.contains(&ty::BoundSend) &&
-            self.region_bound == ty::ReStatic
-        { // Region bound is implied by builtin bounds:
-            return self.builtin_bounds.repr(tcx);
-        }
-
+impl<'tcx> Repr<'tcx> for ty::ExistentialBounds<'tcx> {
+    fn repr(&self, tcx: &ctxt<'tcx>) -> String {
         let mut res = Vec::new();
 
         let region_str = self.region_bound.user_string(tcx);
@@ -1129,6 +1176,10 @@ impl<'tcx> UserString<'tcx> for ty::ExistentialBounds<'tcx> {
             res.push(bound.user_string(tcx));
         }
 
+        for projection_bound in self.projection_bounds.iter() {
+            res.push(projection_bound.user_string(tcx));
+        }
+
         res.connect("+")
     }
 }
@@ -1184,7 +1235,7 @@ impl<'tcx> UserString<'tcx> for ty::TraitRef<'tcx> {
         let path_str = ty::item_path_str(tcx, self.def_id);
         let trait_def = ty::lookup_trait_def(tcx, self.def_id);
         parameterized(tcx, path_str.as_slice(), self.substs,
-                      &trait_def.generics, self.def_id)
+                      &trait_def.generics, self.def_id, &[])
     }
 }
 
diff --git a/src/librustc_trans/trans/meth.rs b/src/librustc_trans/trans/meth.rs
index 187b73b1b09..c4240fa9eba 100644
--- a/src/librustc_trans/trans/meth.rs
+++ b/src/librustc_trans/trans/meth.rs
@@ -13,7 +13,7 @@ use back::abi;
 use back::link;
 use llvm::{self, ValueRef, get_param};
 use metadata::csearch;
-use middle::subst::{Subst, Substs};
+use middle::subst::Substs;
 use middle::subst::VecPerParamSpace;
 use middle::subst;
 use middle::traits;
@@ -29,6 +29,7 @@ use trans::expr::{SaveIn, Ignore};
 use trans::expr;
 use trans::glue;
 use trans::machine;
+use trans::monomorphize;
 use trans::type_::Type;
 use trans::type_of::*;
 use middle::ty::{self, Ty};
@@ -162,7 +163,7 @@ pub fn trans_method_callee<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
             };
             trans_trait_callee(bcx,
                                monomorphize_type(bcx, method_ty),
-                               mt.real_index,
+                               mt.vtable_index,
                                self_expr,
                                arg_cleanup_scope)
         }
@@ -439,7 +440,7 @@ fn combine_impl_and_methods_tps<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 /// extract the self data and vtable out of the pair.
 fn trans_trait_callee<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                                   method_ty: Ty<'tcx>,
-                                  n_method: uint,
+                                  vtable_index: uint,
                                   self_expr: &ast::Expr,
                                   arg_cleanup_scope: cleanup::ScopeId)
                                   -> Callee<'blk, 'tcx> {
@@ -469,28 +470,28 @@ fn trans_trait_callee<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
         self_datum.val
     };
 
-    trans_trait_callee_from_llval(bcx, method_ty, n_method, llval)
+    trans_trait_callee_from_llval(bcx, method_ty, vtable_index, llval)
 }
 
 /// Same as `trans_trait_callee()` above, except that it is given a by-ref pointer to the object
 /// pair.
 pub fn trans_trait_callee_from_llval<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                                                  callee_ty: Ty<'tcx>,
-                                                 n_method: uint,
+                                                 vtable_index: uint,
                                                  llpair: ValueRef)
                                                  -> Callee<'blk, 'tcx> {
     let _icx = push_ctxt("meth::trans_trait_callee");
     let ccx = bcx.ccx();
 
     // Load the data pointer from the object.
-    debug!("(translating trait callee) loading second index from pair");
+    debug!("trans_trait_callee_from_llval(callee_ty={}, vtable_index={}, llpair={})",
+           callee_ty.repr(ccx.tcx()),
+           vtable_index,
+           bcx.val_to_string(llpair));
     let llboxptr = GEPi(bcx, llpair, &[0u, abi::FAT_PTR_ADDR]);
     let llbox = Load(bcx, llboxptr);
     let llself = PointerCast(bcx, llbox, Type::i8p(ccx));
 
-    // Load the function from the vtable and cast it to the expected type.
-    debug!("(translating trait callee) loading method");
-
     // Replace the self type (&Self or Box<Self>) with an opaque pointer.
     let llcallee_ty = match callee_ty.sty {
         ty::ty_bare_fn(_, ref f) if f.abi == Rust || f.abi == RustCall => {
@@ -500,10 +501,7 @@ pub fn trans_trait_callee_from_llval<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                     output: f.sig.0.output,
                     variadic: f.sig.0.variadic,
                 });
-            type_of_rust_fn(ccx,
-                            Some(Type::i8p(ccx)),
-                            &fake_sig,
-                            f.abi)
+            type_of_rust_fn(ccx, Some(Type::i8p(ccx)), &fake_sig, f.abi)
         }
         _ => {
             ccx.sess().bug("meth::trans_trait_callee given non-bare-rust-fn");
@@ -514,7 +512,7 @@ pub fn trans_trait_callee_from_llval<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                                     GEPi(bcx, llpair,
                                          &[0u, abi::FAT_PTR_EXTRA]),
                                     Type::vtable(ccx).ptr_to().ptr_to()));
-    let mptr = Load(bcx, GEPi(bcx, llvtable, &[0u, n_method + VTABLE_OFFSET]));
+    let mptr = Load(bcx, GEPi(bcx, llvtable, &[0u, vtable_index + VTABLE_OFFSET]));
     let mptr = PointerCast(bcx, mptr, llcallee_ty.ptr_to());
 
     return Callee {
@@ -558,7 +556,7 @@ pub fn trans_object_shim<'a, 'tcx>(
     let _icx = push_ctxt("trans_object_shim");
     let tcx = ccx.tcx();
 
-    debug!("trans_object_shim(object_ty={}, trait_id={}, n_method={})",
+    debug!("trans_object_shim(object_ty={}, trait_id={}, method_offset_in_trait={})",
            object_ty.repr(tcx),
            trait_id.repr(tcx),
            method_offset_in_trait);
@@ -587,7 +585,7 @@ pub fn trans_object_shim<'a, 'tcx>(
             tcx.sess.bug("can't create a method shim for an associated type")
         }
     };
-    let fty = method_ty.fty.subst(tcx, &object_substs);
+    let fty = monomorphize::apply_param_substs(tcx, &object_substs, &method_ty.fty);
     let fty = tcx.mk_bare_fn(fty);
     debug!("trans_object_shim: fty={}", fty.repr(tcx));
 
diff --git a/src/librustc_trans/trans/type_of.rs b/src/librustc_trans/trans/type_of.rs
index 61dbb551435..6b6ca600a88 100644
--- a/src/librustc_trans/trans/type_of.rs
+++ b/src/librustc_trans/trans/type_of.rs
@@ -103,6 +103,10 @@ pub fn type_of_rust_fn<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
                                  abi: abi::Abi)
                                  -> Type
 {
+    debug!("type_of_rust_fn(sig={},abi={:?})",
+           sig.repr(cx.tcx()),
+           abi);
+
     let sig = ty::erase_late_bound_regions(cx.tcx(), sig);
     assert!(!sig.variadic); // rust fns are never variadic
 
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 921ed505fa3..6e8dd6b0ae7 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -57,7 +57,7 @@ use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty};
 use rscope::{self, UnelidableRscope, RegionScope, SpecificRscope,
              ShiftedRscope, BindingRscope};
 use TypeAndSubsts;
-use util::common::ErrorReported;
+use util::common::{ErrorReported, FN_OUTPUT_NAME};
 use util::nodemap::DefIdMap;
 use util::ppaux::{self, Repr, UserString};
 
@@ -268,7 +268,7 @@ pub fn ast_path_substs_for_ty<'tcx>(
         ast::ParenthesizedParameters(ref data) => {
             span_err!(tcx.sess, path.span, E0214,
                 "parenthesized parameters may only be used with a trait");
-            (Vec::new(), convert_parenthesized_parameters(this, data), Vec::new())
+            convert_parenthesized_parameters(this, data)
         }
     };
 
@@ -479,7 +479,9 @@ fn convert_ty_with_lifetime_elision<'tcx>(this: &AstConv<'tcx>,
 
 fn convert_parenthesized_parameters<'tcx>(this: &AstConv<'tcx>,
                                           data: &ast::ParenthesizedParameterData)
-                                          -> Vec<Ty<'tcx>>
+                                          -> (Vec<ty::Region>,
+                                              Vec<Ty<'tcx>>,
+                                              Vec<ConvertedBinding<'tcx>>)
 {
     let binding_rscope = BindingRscope::new();
     let inputs = data.inputs.iter()
@@ -492,15 +494,26 @@ fn convert_parenthesized_parameters<'tcx>(this: &AstConv<'tcx>,
 
     let input_ty = ty::mk_tup(this.tcx(), inputs);
 
-    let output = match data.output {
-        Some(ref output_ty) => convert_ty_with_lifetime_elision(this,
-                                                                implied_output_region,
-                                                                params_lifetimes,
-                                                                &**output_ty),
-        None => ty::mk_nil(this.tcx()),
+    let (output, output_span) = match data.output {
+        Some(ref output_ty) => {
+            (convert_ty_with_lifetime_elision(this,
+                                              implied_output_region,
+                                              params_lifetimes,
+                                              &**output_ty),
+             output_ty.span)
+        }
+        None => {
+            (ty::mk_nil(this.tcx()), data.span)
+        }
+    };
+
+    let output_binding = ConvertedBinding {
+        item_name: token::intern(FN_OUTPUT_NAME),
+        ty: output,
+        span: output_span
     };
 
-    vec![input_ty, output]
+    (vec![], vec![input_ty], vec![output_binding])
 }
 
 pub fn instantiate_poly_trait_ref<'tcx>(
@@ -630,7 +643,7 @@ fn ast_path_to_trait_ref<'a,'tcx>(
                             the crate attributes to enable");
             }
 
-            (Vec::new(), convert_parenthesized_parameters(this, data), Vec::new())
+            convert_parenthesized_parameters(this, data)
         }
     };
 
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index 2d7a7634472..bdae34e7878 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -34,7 +34,7 @@ pub fn check_expr_closure<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
            expected.repr(fcx.tcx()));
 
     let expected_sig_and_kind = expected.to_option(fcx).and_then(|ty| {
-        deduce_closure_expectations_from_expected_type(fcx, ty)
+        deduce_expectations_from_expected_type(fcx, ty)
     });
 
     match opt_kind {
@@ -137,20 +137,21 @@ fn check_closure<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
     fcx.inh.closures.borrow_mut().insert(expr_def_id, closure);
 }
 
-fn deduce_closure_expectations_from_expected_type<'a,'tcx>(
+fn deduce_expectations_from_expected_type<'a,'tcx>(
     fcx: &FnCtxt<'a,'tcx>,
     expected_ty: Ty<'tcx>)
     -> Option<(ty::FnSig<'tcx>,ty::ClosureKind)>
 {
     match expected_ty.sty {
         ty::ty_trait(ref object_type) => {
-            let trait_ref =
-                object_type.principal_trait_ref_with_self_ty(fcx.tcx(),
-                                                             fcx.tcx().types.err);
-            deduce_closure_expectations_from_trait_ref(fcx, &trait_ref)
+            let proj_bounds = object_type.projection_bounds_with_self_ty(fcx.tcx(),
+                                                                         fcx.tcx().types.err);
+            proj_bounds.iter()
+                       .filter_map(|pb| deduce_expectations_from_projection(fcx, pb))
+                       .next()
         }
         ty::ty_infer(ty::TyVar(vid)) => {
-            deduce_closure_expectations_from_obligations(fcx, vid)
+            deduce_expectations_from_obligations(fcx, vid)
         }
         _ => {
             None
@@ -158,15 +159,51 @@ fn deduce_closure_expectations_from_expected_type<'a,'tcx>(
     }
 }
 
-fn deduce_closure_expectations_from_trait_ref<'a,'tcx>(
+fn deduce_expectations_from_obligations<'a,'tcx>(
     fcx: &FnCtxt<'a,'tcx>,
-    trait_ref: &ty::PolyTraitRef<'tcx>)
+    expected_vid: ty::TyVid)
+    -> Option<(ty::FnSig<'tcx>, ty::ClosureKind)>
+{
+    let fulfillment_cx = fcx.inh.fulfillment_cx.borrow();
+    // Here `expected_ty` is known to be a type inference variable.
+
+    fulfillment_cx.pending_obligations()
+                  .iter()
+                  .filter_map(|obligation| {
+                      match obligation.predicate {
+                          ty::Predicate::Projection(ref proj_predicate) => {
+                              let trait_ref = proj_predicate.to_poly_trait_ref();
+                              let self_ty = fcx.infcx().shallow_resolve(trait_ref.self_ty());
+                              match self_ty.sty {
+                                  ty::ty_infer(ty::TyVar(v)) if expected_vid == v => {
+                                      deduce_expectations_from_projection(fcx, proj_predicate)
+                                  }
+                                  _ => {
+                                      None
+                                  }
+                              }
+                          }
+                          _ => {
+                              None
+                          }
+                      }
+                  })
+                  .next()
+}
+
+/// 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>(
+    fcx: &FnCtxt<'a,'tcx>,
+    projection: &ty::PolyProjectionPredicate<'tcx>)
     -> Option<(ty::FnSig<'tcx>, ty::ClosureKind)>
 {
     let tcx = fcx.tcx();
 
-    debug!("deduce_closure_expectations_from_object_type({})",
-           trait_ref.repr(tcx));
+    debug!("deduce_expectations_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,
@@ -185,7 +222,7 @@ fn deduce_closure_expectations_from_trait_ref<'a,'tcx>(
     };
     debug!("input_tys {}", input_tys.repr(tcx));
 
-    let ret_param_ty = *trait_ref.substs().types.get(subst::TypeSpace, 1);
+    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));
 
@@ -199,30 +236,3 @@ fn deduce_closure_expectations_from_trait_ref<'a,'tcx>(
     return Some((fn_sig, kind));
 }
 
-fn deduce_closure_expectations_from_obligations<'a,'tcx>(
-    fcx: &FnCtxt<'a,'tcx>,
-    expected_vid: ty::TyVid)
-    -> Option<(ty::FnSig<'tcx>, ty::ClosureKind)>
-{
-    // Here `expected_ty` is known to be a type inference variable.
-    for obligation in fcx.inh.fulfillment_cx.borrow().pending_obligations().iter() {
-        match obligation.predicate {
-            ty::Predicate::Trait(ref trait_predicate) => {
-                let trait_ref = trait_predicate.to_poly_trait_ref();
-                let self_ty = fcx.infcx().shallow_resolve(trait_ref.self_ty());
-                match self_ty.sty {
-                    ty::ty_infer(ty::TyVar(v)) if expected_vid == v => { }
-                    _ => { continue; }
-                }
-
-                match deduce_closure_expectations_from_trait_ref(fcx, &trait_ref) {
-                    Some(e) => { return Some(e); }
-                    None => { }
-                }
-            }
-            _ => { }
-        }
-    }
-
-    None
-}
diff --git a/src/librustc_typeck/check/compare_method.rs b/src/librustc_typeck/check/compare_method.rs
index e3e5d67869f..31b14ea3f3d 100644
--- a/src/librustc_typeck/check/compare_method.rs
+++ b/src/librustc_typeck/check/compare_method.rs
@@ -215,14 +215,8 @@ pub fn compare_impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
     debug!("compare_impl_method: impl_bounds={}",
            impl_bounds.repr(tcx));
 
-    // // Normalize the associated types in the impl_bounds.
-    // let traits::Normalized { value: impl_bounds, .. } =
-    //     traits::normalize(&mut selcx, normalize_cause.clone(), &impl_bounds);
-
     // Normalize the associated types in the trait_bounds.
     let trait_bounds = trait_m.generics.to_bounds(tcx, &trait_to_skol_substs);
-    // let traits::Normalized { value: trait_bounds, .. } =
-    //     traits::normalize(&mut selcx, normalize_cause, &trait_bounds);
 
     // Obtain the predicate split predicate sets for each.
     let trait_pred = trait_bounds.predicates.split();
@@ -242,19 +236,18 @@ pub fn compare_impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
     );
 
     // Construct trait parameter environment and then shift it into the skolemized viewpoint.
-    let mut trait_param_env = impl_param_env.clone();
     // The key step here is to update the caller_bounds's predicates to be
     // the new hybrid bounds we computed.
-    trait_param_env.caller_bounds.predicates = hybrid_preds;
+    let normalize_cause = traits::ObligationCause::misc(impl_m_span, impl_m_body_id);
+    let trait_param_env = impl_param_env.with_caller_bounds(hybrid_preds.into_vec());
+    let trait_param_env = traits::normalize_param_env_or_error(trait_param_env,
+                                                               normalize_cause.clone());
 
     debug!("compare_impl_method: trait_bounds={}",
         trait_param_env.caller_bounds.repr(tcx));
 
     let mut selcx = traits::SelectionContext::new(&infcx, &trait_param_env);
 
-    let normalize_cause =
-        traits::ObligationCause::misc(impl_m_span, impl_m_body_id);
-
     for predicate in impl_pred.fns.into_iter() {
         let traits::Normalized { value: predicate, .. } =
             traits::normalize(&mut selcx, normalize_cause.clone(), &predicate);
diff --git a/src/librustc_typeck/check/method/confirm.rs b/src/librustc_typeck/check/method/confirm.rs
index 4aa0a211221..67b055ac946 100644
--- a/src/librustc_typeck/check/method/confirm.rs
+++ b/src/librustc_typeck/check/method/confirm.rs
@@ -206,7 +206,7 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
                 (impl_polytype.substs, MethodStatic(pick.method_ty.def_id))
             }
 
-            probe::ObjectPick(trait_def_id, method_num, real_index) => {
+            probe::ObjectPick(trait_def_id, method_num, vtable_index) => {
                 self.extract_trait_ref(self_ty, |this, object_ty, data| {
                     // The object data has no entry for the Self
                     // Type. For the purposes of this method call, we
@@ -233,7 +233,7 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
                         trait_ref: upcast_trait_ref,
                         object_trait_id: trait_def_id,
                         method_num: method_num,
-                        real_index: real_index,
+                        vtable_index: vtable_index,
                     });
                     (substs, origin)
                 })
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 4c5a8144cbd..6a3554314e2 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -59,7 +59,7 @@ struct Candidate<'tcx> {
 
 enum CandidateKind<'tcx> {
     InherentImplCandidate(/* Impl */ ast::DefId, subst::Substs<'tcx>),
-    ObjectCandidate(/* Trait */ ast::DefId, /* method_num */ uint, /* real_index */ uint),
+    ObjectCandidate(/* Trait */ ast::DefId, /* method_num */ uint, /* vtable index */ uint),
     ExtensionImplCandidate(/* Impl */ ast::DefId, Rc<ty::TraitRef<'tcx>>,
                            subst::Substs<'tcx>, MethodIndex),
     ClosureCandidate(/* Trait */ ast::DefId, MethodIndex),
@@ -318,7 +318,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
         // itself. Hence, a `&self` method will wind up with an
         // argument type like `&Trait`.
         let trait_ref = data.principal_trait_ref_with_self_ty(self.tcx(), self_ty);
-        self.elaborate_bounds(&[trait_ref.clone()], false, |this, new_trait_ref, m, method_num| {
+        self.elaborate_bounds(&[trait_ref.clone()], |this, new_trait_ref, m, method_num| {
             let new_trait_ref = this.erase_late_bound_regions(&new_trait_ref);
 
             let vtable_index =
@@ -343,7 +343,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
         // FIXME -- Do we want to commit to this behavior for param bounds?
 
         let bounds: Vec<_> =
-            self.fcx.inh.param_env.caller_bounds.predicates
+            self.fcx.inh.param_env.caller_bounds
             .iter()
             .filter_map(|predicate| {
                 match *predicate {
@@ -365,7 +365,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
             })
             .collect();
 
-        self.elaborate_bounds(bounds.as_slice(), true, |this, poly_trait_ref, m, method_num| {
+        self.elaborate_bounds(bounds.as_slice(), |this, poly_trait_ref, m, method_num| {
             let trait_ref =
                 this.erase_late_bound_regions(&poly_trait_ref);
 
@@ -405,7 +405,6 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
     fn elaborate_bounds<F>(
         &mut self,
         bounds: &[ty::PolyTraitRef<'tcx>],
-        num_includes_types: bool,
         mut mk_cand: F,
     ) where
         F: for<'b> FnMut(
@@ -427,8 +426,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
 
             let (pos, method) = match trait_method(tcx,
                                                    bound_trait_ref.def_id(),
-                                                   self.method_name,
-                                                   num_includes_types) {
+                                                   self.method_name) {
                 Some(v) => v,
                 None => { continue; }
             };
@@ -697,8 +695,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
         debug!("assemble_where_clause_candidates(trait_def_id={})",
                trait_def_id.repr(self.tcx()));
 
-        let caller_predicates =
-            self.fcx.inh.param_env.caller_bounds.predicates.as_slice().to_vec();
+        let caller_predicates = self.fcx.inh.param_env.caller_bounds.clone();
         for poly_bound in traits::elaborate_predicates(self.tcx(), caller_predicates)
                           .filter_map(|p| p.to_opt_poly_trait_ref())
                           .filter(|b| b.def_id() == trait_def_id)
@@ -1140,19 +1137,13 @@ fn impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
 /// index (or `None`, if no such method).
 fn trait_method<'tcx>(tcx: &ty::ctxt<'tcx>,
                       trait_def_id: ast::DefId,
-                      method_name: ast::Name,
-                      num_includes_types: bool)
+                      method_name: ast::Name)
                       -> Option<(uint, Rc<ty::Method<'tcx>>)>
 {
     let trait_items = ty::trait_items(tcx, trait_def_id);
     debug!("trait_method; items: {:?}", trait_items);
     trait_items
         .iter()
-        .filter(|item|
-            num_includes_types || match *item {
-                &ty::MethodTraitItem(_) => true,
-                &ty::TypeTraitItem(_) => false
-            })
         .enumerate()
         .find(|&(_, ref item)| item.name() == method_name)
         .and_then(|(idx, item)| item.as_opt_method().map(|m| (idx, m)))
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 09b65bcb1fc..fe3d9157be4 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -467,7 +467,8 @@ fn check_bare_fn<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                            body: &ast::Block,
                            id: ast::NodeId,
                            raw_fty: Ty<'tcx>,
-                           param_env: ty::ParameterEnvironment<'a, 'tcx>) {
+                           param_env: ty::ParameterEnvironment<'a, 'tcx>)
+{
     match raw_fty.sty {
         ty::ty_bare_fn(_, ref fn_ty) => {
             let inh = Inherited::new(ccx.tcx, param_env);
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index f2a3d660925..b039f3ab8e4 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -1482,7 +1482,7 @@ fn generic_must_outlive<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
     let mut param_bounds =
         ty::required_region_bounds(rcx.tcx(),
                                    generic.to_ty(rcx.tcx()),
-                                   param_env.caller_bounds.predicates.as_slice().to_vec());
+                                   param_env.caller_bounds.clone());
 
     // In the case of a projection T::Foo, we may be able to extract bounds from the trait def:
     match *generic {
diff --git a/src/librustc_typeck/check/wf.rs b/src/librustc_typeck/check/wf.rs
index 60284433ffe..db226295cd9 100644
--- a/src/librustc_typeck/check/wf.rs
+++ b/src/librustc_typeck/check/wf.rs
@@ -127,6 +127,7 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
         reject_non_type_param_bounds(ccx.tcx, item.span, &type_scheme.generics);
         let param_env =
             ty::construct_parameter_environment(ccx.tcx,
+                                                item.span,
                                                 &type_scheme.generics,
                                                 item.id);
         let inh = Inherited::new(ccx.tcx, param_env);
diff --git a/src/librustc_typeck/variance.rs b/src/librustc_typeck/variance.rs
index ed8a50110e5..63ad47ff31f 100644
--- a/src/librustc_typeck/variance.rs
+++ b/src/librustc_typeck/variance.rs
@@ -818,6 +818,12 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
                     trait_def.generics.regions.get_slice(subst::TypeSpace),
                     trait_ref.substs(),
                     variance);
+
+                let projections = data.projection_bounds_with_self_ty(self.tcx(),
+                                                                      self.tcx().types.err);
+                for projection in projections.iter() {
+                    self.add_constraints_from_ty(generics, projection.0.ty, self.invariant);
+                }
             }
 
             ty::ty_param(ref data) => {
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index c12726c8868..d2080419469 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -536,7 +536,7 @@ fn external_path_params(cx: &DocContext, trait_did: Option<ast::DefId>,
     match (trait_did, cx.tcx_opt()) {
         // Attempt to sugar an external path like Fn<(A, B,), C> to Fn(A, B) -> C
         (Some(did), Some(ref tcx)) if tcx.lang_items.fn_trait_kind(did).is_some() => {
-            assert_eq!(types.len(), 2);
+            assert_eq!(types.len(), 1);
             let inputs = match types[0].sty {
                 sty::ty_tup(ref tys) => tys.iter().map(|t| t.clean(cx)).collect(),
                 _ => {
@@ -547,10 +547,12 @@ fn external_path_params(cx: &DocContext, trait_did: Option<ast::DefId>,
                     }
                 }
             };
-            let output = match types[1].sty {
-                sty::ty_tup(ref v) if v.is_empty() => None, // -> ()
-                _ => Some(types[1].clean(cx))
-            };
+            let output = None;
+            // FIXME(#20299) return type comes from a projection now
+            // match types[1].sty {
+            //     sty::ty_tup(ref v) if v.is_empty() => None, // -> ()
+            //     _ => Some(types[1].clean(cx))
+            // };
             PathParameters::Parenthesized {
                 inputs: inputs,
                 output: output
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 4f6cd8ad356..4dada5bc81e 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -347,6 +347,9 @@ impl AngleBracketedParameterData {
 /// A path like `Foo(A,B) -> C`
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
 pub struct ParenthesizedParameterData {
+    /// Overall span
+    pub span: Span,
+
     /// `(A,B)`
     pub inputs: Vec<P<Ty>>,
 
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index bf822599a88..a1362f5382c 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -536,9 +536,10 @@ pub fn noop_fold_parenthesized_parameter_data<T: Folder>(data: ParenthesizedPara
                                                          fld: &mut T)
                                                          -> ParenthesizedParameterData
 {
-    let ParenthesizedParameterData { inputs, output } = data;
+    let ParenthesizedParameterData { inputs, output, span } = data;
     ParenthesizedParameterData { inputs: inputs.move_map(|ty| fld.fold_ty(ty)),
-                                 output: output.map(|ty| fld.fold_ty(ty)) }
+                                 output: output.map(|ty| fld.fold_ty(ty)),
+                                 span: fld.new_span(span) }
 }
 
 pub fn noop_fold_local<T: Folder>(l: P<Local>, fld: &mut T) -> P<Local> {
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index fbea265597c..4c1ae532d13 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -1796,6 +1796,8 @@ impl<'a> Parser<'a> {
                     bindings: OwnedSlice::from_vec(bindings),
                 })
             } else if self.eat(&token::OpenDelim(token::Paren)) {
+                let lo = self.last_span.lo;
+
                 let inputs = self.parse_seq_to_end(
                     &token::CloseDelim(token::Paren),
                     seq_sep_trailing_allowed(token::Comma),
@@ -1807,9 +1809,12 @@ impl<'a> Parser<'a> {
                     None
                 };
 
+                let hi = self.last_span.hi;
+
                 ast::ParenthesizedParameters(ast::ParenthesizedParameterData {
+                    span: mk_sp(lo, hi),
                     inputs: inputs,
-                    output: output_ty
+                    output: output_ty,
                 })
             } else {
                 ast::PathParameters::none()
diff --git a/src/test/compile-fail/borrowck-overloaded-call.rs b/src/test/compile-fail/borrowck-overloaded-call.rs
index 7d35a27c0ae..04d73cc36f0 100644
--- a/src/test/compile-fail/borrowck-overloaded-call.rs
+++ b/src/test/compile-fail/borrowck-overloaded-call.rs
@@ -17,7 +17,9 @@ struct SFn {
     y: isize,
 }
 
-impl Fn<(isize,),isize> for SFn {
+impl Fn<(isize,)> for SFn {
+    type Output = isize;
+
     extern "rust-call" fn call(&self, (z,): (isize,)) -> isize {
         self.x * self.y * z
     }
@@ -28,7 +30,9 @@ struct SFnMut {
     y: isize,
 }
 
-impl FnMut<(isize,),isize> for SFnMut {
+impl FnMut<(isize,)> for SFnMut {
+    type Output = isize;
+
     extern "rust-call" fn call_mut(&mut self, (z,): (isize,)) -> isize {
         self.x * self.y * z
     }
@@ -38,7 +42,9 @@ struct SFnOnce {
     x: String,
 }
 
-impl FnOnce<(String,),usize> for SFnOnce {
+impl FnOnce<(String,)> for SFnOnce {
+    type Output = usize;
+
     extern "rust-call" fn call_once(self, (z,): (String,)) -> usize {
         self.x.len() + z.len()
     }
diff --git a/src/test/compile-fail/extern-wrong-value-type.rs b/src/test/compile-fail/extern-wrong-value-type.rs
index d7586af291e..db3373ea027 100644
--- a/src/test/compile-fail/extern-wrong-value-type.rs
+++ b/src/test/compile-fail/extern-wrong-value-type.rs
@@ -16,5 +16,7 @@ fn is_fn<F>(_: F) where F: Fn() {}
 fn main() {
     // extern functions are extern "C" fn
     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()
+    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()
 }
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 cdb207f705f..e5e5ddadafc 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
@@ -8,18 +8,38 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// Test that manual impls of the `Fn` traits are not possible without
+// a feature gate. In fact, the specialized check for these cases
+// never triggers (yet), because they encounter other problems around
+// angle bracket vs parentheses notation.
+
 #![allow(dead_code)]
 
 struct Foo;
-impl Fn() for Foo { //~ ERROR manual implementations of `Fn` are experimental
+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: ()) -> () {}
+}
+struct Foo1;
+impl Fn() for Foo1 {
+    //~^ ERROR associated type bindings are not allowed here
+
     extern "rust-call" fn call(&self, args: ()) -> () {}
 }
 struct Bar;
-impl FnMut() for Bar { //~ ERROR manual implementations of `FnMut` are experimental
+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 manual implementations of `FnOnce` are experimental
+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 f19e27640cb..460e05c8438 100644
--- a/src/test/compile-fail/fn-trait-formatting.rs
+++ b/src/test/compile-fail/fn-trait-formatting.rs
@@ -34,5 +34,7 @@ fn main() {
     //~| expected ()
     //~| found box
 
-    needs_fn(1is); //~ ERROR `core::ops::Fn(isize) -> isize`
+    needs_fn(1is);
+    //~^ ERROR `core::ops::Fn<(isize,)>`
+    //~| ERROR `core::ops::Fn<(isize,)>`
 }
diff --git a/src/test/compile-fail/issue-15094.rs b/src/test/compile-fail/issue-15094.rs
index 2c03a9e0733..977586483b0 100644
--- a/src/test/compile-fail/issue-15094.rs
+++ b/src/test/compile-fail/issue-15094.rs
@@ -16,7 +16,9 @@ struct Debuger<T> {
     x: T
 }
 
-impl<T: fmt::Debug> ops::Fn<(), ()> for Debuger<T> {
+impl<T: fmt::Debug> ops::Fn<(),> for Debuger<T> {
+    type Output = ();
+
     fn call(&self, _args: ()) {
 //~^ ERROR `call` has an incompatible type for trait: expected "rust-call" fn, found "Rust" fn
         println!("{:?}", self.x);
diff --git a/src/test/compile-fail/issue-17545.rs b/src/test/compile-fail/issue-17545.rs
index 0501a3013cc..84800218efc 100644
--- a/src/test/compile-fail/issue-17545.rs
+++ b/src/test/compile-fail/issue-17545.rs
@@ -10,7 +10,7 @@
 
 #![feature(unboxed_closures)]
 
-pub fn foo<'a, F: Fn<(&'a (),), ()>>(bar: F) {
+pub fn foo<'a, F: Fn(&'a ())>(bar: F) {
     bar.call((
         &(), //~ ERROR borrowed value does not live long enough
     ));
diff --git a/src/test/compile-fail/overloaded-calls-bad.rs b/src/test/compile-fail/overloaded-calls-bad.rs
index d784ba2d0d6..61752e62abd 100644
--- a/src/test/compile-fail/overloaded-calls-bad.rs
+++ b/src/test/compile-fail/overloaded-calls-bad.rs
@@ -17,7 +17,9 @@ struct S {
     y: isize,
 }
 
-impl FnMut<(isize,),isize> for 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
     }
diff --git a/src/test/compile-fail/overloaded-calls-nontuple.rs b/src/test/compile-fail/overloaded-calls-nontuple.rs
index c06ab04cd84..41ecf714613 100644
--- a/src/test/compile-fail/overloaded-calls-nontuple.rs
+++ b/src/test/compile-fail/overloaded-calls-nontuple.rs
@@ -17,7 +17,8 @@ struct S {
     y: isize,
 }
 
-impl FnMut<isize,isize> for 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
     }
diff --git a/src/test/compile-fail/regions-infer-invariance-due-to-mutability-4.rs b/src/test/compile-fail/regions-infer-invariance-due-to-mutability-4.rs
index 2e634dfe3eb..2a246124f6f 100644
--- a/src/test/compile-fail/regions-infer-invariance-due-to-mutability-4.rs
+++ b/src/test/compile-fail/regions-infer-invariance-due-to-mutability-4.rs
@@ -9,15 +9,15 @@
 // except according to those terms.
 
 
-struct invariant<'a> {
+struct Invariant<'a> {
     f: Box<for<'b> FnOnce() -> &'b mut &'a isize + 'static>,
 }
 
-fn to_same_lifetime<'r>(bi: invariant<'r>) {
-    let bj: invariant<'r> = bi;
+fn to_same_lifetime<'r>(bi: Invariant<'r>) {
+    let bj: Invariant<'r> = bi;
 }
 
-fn to_longer_lifetime<'r>(bi: invariant<'r>) -> invariant<'static> {
+fn to_longer_lifetime<'r>(bi: Invariant<'r>) -> Invariant<'static> {
     bi //~ ERROR mismatched types
 }
 
diff --git a/src/test/compile-fail/unboxed-closure-feature-gate.rs b/src/test/compile-fail/unboxed-closure-feature-gate.rs
index 5eb67a9bb71..3536244f011 100644
--- a/src/test/compile-fail/unboxed-closure-feature-gate.rs
+++ b/src/test/compile-fail/unboxed-closure-feature-gate.rs
@@ -11,7 +11,8 @@
 // Check that parenthetical notation is feature-gated except with the
 // `Fn` traits.
 
-trait Foo<A,R> {
+trait Foo<A> {
+    type Output;
 }
 
 fn main() {
diff --git a/src/test/compile-fail/unboxed-closure-sugar-default.rs b/src/test/compile-fail/unboxed-closure-sugar-default.rs
index 0d9e406b086..870377bc1ad 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-default.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-default.rs
@@ -14,8 +14,9 @@
 #![feature(unboxed_closures)]
 #![allow(dead_code)]
 
-trait Foo<T,U,V=T> {
-    fn dummy(&self, t: T, u: U, v: V);
+trait Foo<T,V=T> {
+    type Output;
+    fn dummy(&self, t: T, v: V);
 }
 
 trait Eq<X: ?Sized> { }
@@ -24,14 +25,14 @@ fn eq<A: ?Sized,B: ?Sized>() where A : Eq<B> { }
 
 fn test<'a,'b>() {
     // Parens are equivalent to omitting default in angle.
-    eq::< Foo<(isize,),()>,               Foo(isize)                      >();
+    eq::< Foo<(isize,),Output=()>,                   Foo(isize)                      >();
 
     // In angle version, we supply something other than the default
-    eq::< Foo<(isize,),(),isize>,           Foo(isize)                      >();
+    eq::< Foo<(isize,),isize,Output=()>,      Foo(isize)                      >();
     //~^ ERROR not implemented
 
     // Supply default explicitly.
-    eq::< Foo<(isize,),(),(isize,)>,        Foo(isize)                      >();
+    eq::< Foo<(isize,),(isize,),Output=()>,   Foo(isize)                      >();
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/unboxed-closure-sugar-equiv.rs b/src/test/compile-fail/unboxed-closure-sugar-equiv.rs
index 9dff0e9e01e..dc5576aee65 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-equiv.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-equiv.rs
@@ -16,8 +16,9 @@
 #![feature(unboxed_closures)]
 #![allow(dead_code)]
 
-trait Foo<T,U> {
-    fn dummy(&self, t: T, u: U);
+trait Foo<T> {
+    type Output;
+    fn dummy(&self, t: T, u: Self::Output);
 }
 
 trait Eq<X: ?Sized> { }
@@ -26,31 +27,32 @@ fn eq<A: ?Sized,B: ?Sized +Eq<A>>() { }
 
 fn test<'a,'b>() {
     // No errors expected:
-    eq::< Foo<(),()>,                   Foo()                         >();
-    eq::< Foo<(isize,),()>,               Foo(isize)                      >();
-    eq::< Foo<(isize,usize),()>,           Foo(isize,usize)                 >();
-    eq::< Foo<(isize,usize),usize>,         Foo(isize,usize) -> usize         >();
-    eq::< Foo<(&'a isize,&'b usize),usize>, Foo(&'a isize,&'b usize) -> usize >();
+    eq::< Foo<(),Output=()>,                       Foo()                         >();
+    eq::< Foo<(isize,),Output=()>,                 Foo(isize)                      >();
+    eq::< Foo<(isize,usize),Output=()>,            Foo(isize,usize)                 >();
+    eq::< Foo<(isize,usize),Output=usize>,         Foo(isize,usize) -> usize         >();
+    eq::< Foo<(&'a isize,&'b usize),Output=usize>, Foo(&'a isize,&'b usize) -> usize >();
 
     // Test that anonymous regions in `()` form are equivalent
     // to fresh bound regions, and that we can intermingle
     // named and anonymous as we choose:
-    eq::< for<'x,'y> Foo<(&'x isize,&'y usize),usize>,
+    eq::< for<'x,'y> Foo<(&'x isize,&'y usize),Output=usize>,
           for<'x,'y> Foo(&'x isize,&'y usize) -> usize            >();
-    eq::< for<'x,'y> Foo<(&'x isize,&'y usize),usize>,
+    eq::< for<'x,'y> Foo<(&'x isize,&'y usize),Output=usize>,
           for<'x> Foo(&'x isize,&usize) -> usize                  >();
-    eq::< for<'x,'y> Foo<(&'x isize,&'y usize),usize>,
+    eq::< for<'x,'y> Foo<(&'x isize,&'y usize),Output=usize>,
           for<'y> Foo(&isize,&'y usize) -> usize                  >();
-    eq::< for<'x,'y> Foo<(&'x isize,&'y usize),usize>,
+    eq::< for<'x,'y> Foo<(&'x isize,&'y usize),Output=usize>,
           Foo(&isize,&usize) -> usize                             >();
 
     // lifetime elision
-    eq::< for<'x> Foo<(&'x isize,), &'x isize>,
+    eq::< for<'x> Foo<(&'x isize,), Output=&'x isize>,
           Foo(&isize) -> &isize                                   >();
 
     // Errors expected:
-    eq::< Foo<(),()>,                   Foo(char)                     >();
-    //~^ ERROR not implemented
+    eq::< Foo<(),Output=()>,
+          Foo(char)                                               >();
+    //~^^ ERROR not implemented
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/unboxed-closure-sugar-lifetime-elision.rs b/src/test/compile-fail/unboxed-closure-sugar-lifetime-elision.rs
index 29429c708d2..d2f781bba11 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-lifetime-elision.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-lifetime-elision.rs
@@ -16,8 +16,9 @@
 #![feature(unboxed_closures)]
 #![allow(dead_code)]
 
-trait Foo<T,U> {
-    fn dummy(&self, t: T, u: U);
+trait Foo<T> {
+    type Output;
+    fn dummy(&self, t: T);
 }
 
 trait Eq<X: ?Sized> { }
@@ -25,9 +26,9 @@ impl<X: ?Sized> Eq<X> for X { }
 fn eq<A: ?Sized,B: ?Sized +Eq<A>>() { }
 
 fn main() {
-    eq::< for<'a> Foo<(&'a isize,), &'a isize>,
+    eq::< for<'a> Foo<(&'a isize,), Output=&'a isize>,
           Foo(&isize) -> &isize                                   >();
-    eq::< for<'a> Foo<(&'a isize,), (&'a isize, &'a isize)>,
+    eq::< for<'a> Foo<(&'a isize,), Output=(&'a isize, &'a isize)>,
           Foo(&isize) -> (&isize, &isize)                           >();
 
     let _: Foo(&isize, &usize) -> &usize; //~ ERROR missing lifetime specifier
diff --git a/src/test/compile-fail/unboxed-closure-sugar-not-used-on-fn.rs b/src/test/compile-fail/unboxed-closure-sugar-not-used-on-fn.rs
index 21844e5b986..1f0d5aae36d 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-not-used-on-fn.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-not-used-on-fn.rs
@@ -11,11 +11,11 @@
 
 // Test that the `Fn` traits require `()` form without a feature gate.
 
-fn bar1(x: &Fn<(),()>) {
+fn bar1(x: &Fn<()>) {
     //~^ ERROR angle-bracket notation is not stable when used with the `Fn` family
 }
 
-fn bar2<T>(x: &T) where T: Fn<(),()> {
+fn bar2<T>(x: &T) where T: Fn<()> {
     //~^ ERROR angle-bracket notation is not stable when used with the `Fn` family
 }
 
diff --git a/src/test/compile-fail/unboxed-closure-sugar-region.rs b/src/test/compile-fail/unboxed-closure-sugar-region.rs
index c8dd33c11fd..75688e44e80 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-region.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-region.rs
@@ -17,8 +17,9 @@
 
 use std::marker;
 
-trait Foo<'a,T,U> {
-    fn dummy(&'a self) -> &'a (T,U);
+trait Foo<'a,T> {
+    type Output;
+    fn dummy(&'a self) -> &'a (T,Self::Output);
 }
 
 trait Eq<X: ?Sized> { }
@@ -29,16 +30,17 @@ fn same_type<A,B:Eq<A>>(a: A, b: B) { }
 
 fn test<'a,'b>() {
     // Parens are equivalent to omitting default in angle.
-    eq::< Foo<(isize,),()>,               Foo(isize)                      >();
+    eq::< Foo<(isize,),Output=()>,               Foo(isize)                      >();
 
     // Here we specify 'static explicitly in angle-bracket version.
     // Parenthesized winds up getting inferred.
-    eq::< Foo<'static, (isize,),()>,      Foo(isize)                      >();
+    eq::< Foo<'static, (isize,),Output=()>,      Foo(isize)                      >();
 }
 
-fn test2(x: &Foo<(isize,),()>, y: &Foo(isize)) {
+fn test2(x: &Foo<(isize,),Output=()>, y: &Foo(isize)) {
     // Here, the omitted lifetimes are expanded to distinct things.
     same_type(x, y) //~ ERROR cannot infer
+                    //~^ ERROR cannot infer
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/unboxed-closure-sugar-used-on-struct-1.rs b/src/test/compile-fail/unboxed-closure-sugar-used-on-struct-1.rs
index a6184caf68b..a3991a87b78 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-used-on-struct-1.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-used-on-struct-1.rs
@@ -11,13 +11,14 @@
 
 // Test that parentheses form doesn't work with struct types appearing in local variables.
 
-struct Bar<A,R> {
-    f: A, r: R
+struct Bar<A> {
+    f: A
 }
 
 fn bar() {
     let x: Box<Bar()> = panic!();
     //~^ ERROR parenthesized parameters may only be used with a trait
+    //~^^ ERROR associated type bindings are not allowed here
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/unboxed-closure-sugar-used-on-struct.rs b/src/test/compile-fail/unboxed-closure-sugar-used-on-struct.rs
index d5fb505715e..ad85cdcaa03 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-used-on-struct.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-used-on-struct.rs
@@ -10,12 +10,13 @@
 
 // Test that parentheses form doesn't work with struct types appearing in argument types.
 
-struct Bar<A,R> {
-    f: A, r: R
+struct Bar<A> {
+    f: A
 }
 
 fn foo(b: Box<Bar()>) {
     //~^ ERROR parenthesized parameters may only be used with a trait
+    //~^^ ERROR associated type bindings are not allowed here
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/unboxed-closure-sugar-wrong-number-number-type-parameters-1.rs b/src/test/compile-fail/unboxed-closure-sugar-wrong-number-number-type-parameters-1.rs
index d9efab974d8..c9837da58e7 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-wrong-number-number-type-parameters-1.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-wrong-number-number-type-parameters-1.rs
@@ -12,7 +12,7 @@
 
 trait One<A> { fn foo(&self) -> A; }
 
-fn foo(_: &One()) //~ ERROR wrong number of type arguments
+fn foo(_: &One()) //~ ERROR no associated type `Output` defined in `One<()>`
 {}
 
 fn main() { }
diff --git a/src/test/compile-fail/unboxed-closure-sugar-wrong-trait.rs b/src/test/compile-fail/unboxed-closure-sugar-wrong-trait.rs
index b58e08355c1..e63f510b890 100644
--- a/src/test/compile-fail/unboxed-closure-sugar-wrong-trait.rs
+++ b/src/test/compile-fail/unboxed-closure-sugar-wrong-trait.rs
@@ -13,7 +13,7 @@
 trait Trait {}
 
 fn f<F:Trait(isize) -> isize>(x: F) {}
-//~^ ERROR wrong number of type arguments: expected 0, found 2
+//~^ ERROR wrong number of type arguments: expected 0, found 1
 
 fn main() {}
 
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 fc87ec9f959..bbafd5109ed 100644
--- a/src/test/compile-fail/unboxed-closures-fnmut-as-fn.rs
+++ b/src/test/compile-fail/unboxed-closures-fnmut-as-fn.rs
@@ -18,7 +18,9 @@ use std::ops::{Fn,FnMut,FnOnce};
 
 struct S;
 
-impl FnMut<(isize,),isize> for S {
+impl FnMut<(isize,)> for S {
+    type Output = isize;
+
     extern "rust-call" fn call_mut(&mut self, (x,): (isize,)) -> isize {
         x * x
     }
@@ -29,6 +31,8 @@ fn call_it<F:Fn(isize)->isize>(f: &F, x: isize) -> isize {
 }
 
 fn main() {
-    let x = call_it(&S, 22); //~ ERROR not implemented
+    let x = call_it(&S, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
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 ab909717cab..23f7ee2b010 100644
--- a/src/test/compile-fail/unboxed-closures-unsafe-extern-fn.rs
+++ b/src/test/compile-fail/unboxed-closures-unsafe-extern-fn.rs
@@ -21,7 +21,9 @@ fn call_it_mut<F:FnMut(&isize)->isize>(_: &mut F, _: isize) -> isize { 0 }
 fn call_it_once<F:FnOnce(&isize)->isize>(_: F, _: isize) -> isize { 0 }
 
 fn a() {
-    let x = call_it(&square, 22); //~ ERROR not implemented
+    let x = call_it(&square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn b() {
diff --git a/src/test/compile-fail/unboxed-closures-vtable-mismatch.rs b/src/test/compile-fail/unboxed-closures-vtable-mismatch.rs
index 95673a51319..305dd33e5a0 100644
--- a/src/test/compile-fail/unboxed-closures-vtable-mismatch.rs
+++ b/src/test/compile-fail/unboxed-closures-vtable-mismatch.rs
@@ -12,13 +12,15 @@
 
 use std::ops::FnMut;
 
-fn call_it<F:FnMut<(isize,isize),isize>>(y: isize, mut f: F) -> isize {
+fn call_it<F:FnMut(isize,isize)->isize>(y: isize, mut f: F) -> isize {
     f(2, y)
 }
 
 pub fn main() {
     let f = |&mut: x: usize, y: isize| -> isize { (x as isize) + y };
-    let z = call_it(3, f);  //~ ERROR type mismatch
+    let z = call_it(3, f);
+    //~^ ERROR type mismatch
+    //~| ERROR type mismatch
     println!("{}", z);
 }
 
diff --git a/src/test/compile-fail/unboxed-closures-wrong-abi.rs b/src/test/compile-fail/unboxed-closures-wrong-abi.rs
index 4a0b55558c0..96619bef36f 100644
--- a/src/test/compile-fail/unboxed-closures-wrong-abi.rs
+++ b/src/test/compile-fail/unboxed-closures-wrong-abi.rs
@@ -21,7 +21,9 @@ fn call_it_mut<F:FnMut(&isize)->isize>(_: &mut F, _: isize) -> isize { 0 }
 fn call_it_once<F:FnOnce(&isize)->isize>(_: F, _: isize) -> isize { 0 }
 
 fn a() {
-    let x = call_it(&square, 22); //~ ERROR not implemented
+    let x = call_it(&square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn b() {
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 b2fdf792630..ebcbdbbc006 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
@@ -22,7 +22,9 @@ fn call_it_mut<F:FnMut(&isize)->isize>(_: &mut F, _: isize) -> isize { 0 }
 fn call_it_once<F:FnOnce(&isize)->isize>(_: F, _: isize) -> isize { 0 }
 
 fn a() {
-    let x = call_it(&square, 22); //~ ERROR not implemented
+    let x = call_it(&square, 22);
+    //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
 fn b() {
diff --git a/src/test/compile-fail/unboxed-closures-wrong-trait.rs b/src/test/compile-fail/unboxed-closures-wrong-trait.rs
index e4255d0024f..2ada0dd22e7 100644
--- a/src/test/compile-fail/unboxed-closures-wrong-trait.rs
+++ b/src/test/compile-fail/unboxed-closures-wrong-trait.rs
@@ -18,5 +18,6 @@ fn main() {
     let z: isize = 7;
     assert_eq!(c(|&mut: x: isize, y| x + y + z), 10);
     //~^ ERROR not implemented
+    //~| ERROR not implemented
 }
 
diff --git a/src/test/compile-fail/variance-object-types.rs b/src/test/compile-fail/variance-object-types.rs
new file mode 100644
index 00000000000..972ec96f5f2
--- /dev/null
+++ b/src/test/compile-fail/variance-object-types.rs
@@ -0,0 +1,24 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that Cell is considered invariant with respect to its
+// type.
+
+use std::cell::Cell;
+
+// For better or worse, associated types are invariant, and hence we
+// get an invariant result for `'a`.
+#[rustc_variance]
+struct Foo<'a> { //~ ERROR regions=[[o];[];[]]
+    x: Box<Fn(i32) -> &'a i32 + 'static>
+}
+
+fn main() {
+}
diff --git a/src/test/run-pass/associated-types-issue-21212.rs b/src/test/run-pass/associated-types-issue-21212.rs
new file mode 100644
index 00000000000..ced44250e4d
--- /dev/null
+++ b/src/test/run-pass/associated-types-issue-21212.rs
@@ -0,0 +1,28 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Regression test for #21212: an overflow occurred during trait
+// checking where normalizing `Self::Input` led to normalizing the
+// where clauses in the environment which in turn required normalizing
+// `Self::Input`.
+
+pub trait Parser {
+    type Input;
+
+    fn parse(input: <Self as Parser>::Input) {
+        panic!()
+    }
+}
+impl <P> Parser for P  {
+    type Input = ();
+}
+
+fn main() {
+}
diff --git a/src/test/run-pass/associated-types-normalize-in-bounds-binding.rs b/src/test/run-pass/associated-types-normalize-in-bounds-binding.rs
new file mode 100644
index 00000000000..dd5814f875b
--- /dev/null
+++ b/src/test/run-pass/associated-types-normalize-in-bounds-binding.rs
@@ -0,0 +1,42 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that we normalize associated types that appear in a bound that
+// contains a binding. Issue #21664.
+
+#![allow(dead_code)]
+
+pub trait Integral {
+    type Opposite;
+}
+
+impl Integral for i32 {
+    type Opposite = u32;
+}
+
+impl Integral for u32 {
+    type Opposite = i32;
+}
+
+pub trait FnLike<A> {
+    type R;
+}
+
+fn foo<T>()
+    where T : FnLike<<i32 as Integral>::Opposite, R=bool>
+{
+    bar::<T>();
+}
+
+fn bar<T>()
+    where T : FnLike<u32, R=bool>
+{}
+
+fn main() { }
diff --git a/src/test/run-pass/bare-fn-implements-fn-mut.rs b/src/test/run-pass/bare-fn-implements-fn-mut.rs
index 9d104afd646..fae83d4aa65 100644
--- a/src/test/run-pass/bare-fn-implements-fn-mut.rs
+++ b/src/test/run-pass/bare-fn-implements-fn-mut.rs
@@ -12,7 +12,7 @@
 
 use std::ops::FnMut;
 
-fn call_f<F:FnMut<(),()>>(mut f: F) {
+fn call_f<F:FnMut()>(mut f: F) {
     f();
 }
 
@@ -20,7 +20,7 @@ fn f() {
     println!("hello");
 }
 
-fn call_g<G:FnMut<(String,String),String>>(mut g: G, x: String, y: String)
+fn call_g<G:FnMut(String,String) -> String>(mut g: G, x: String, y: String)
           -> String {
     g(x, y)
 }
diff --git a/src/test/run-pass/hrtb-parse.rs b/src/test/run-pass/hrtb-parse.rs
index 41b7c0fae07..d5307c09103 100644
--- a/src/test/run-pass/hrtb-parse.rs
+++ b/src/test/run-pass/hrtb-parse.rs
@@ -22,23 +22,23 @@ trait Get<A,R> {
 // Parse HRTB with explicit `for` in a where-clause:
 
 fn foo00<T>(t: T)
-    where T : for<'a> Get<&'a int, &'a int>
+    where T : for<'a> Get<&'a i32, &'a i32>
 {
 }
 
-fn foo01<T: for<'a> Get<&'a int, &'a int>>(t: T)
+fn foo01<T: for<'a> Get<&'a i32, &'a i32>>(t: T)
 {
 }
 
 // Parse HRTB with explicit `for` in various sorts of types:
 
-fn foo10(t: Box<for<'a> Get<int, int>>) { }
-fn foo11(t: Box<for<'a> Get(int) -> int>) { }
+fn foo10(t: Box<for<'a> Get<i32, i32>>) { }
+fn foo11(t: Box<for<'a> Fn(i32) -> i32>) { }
 
-fn foo20(t: for<'a> fn(int) -> int) { }
-fn foo21(t: for<'a> unsafe fn(int) -> int) { }
-fn foo22(t: for<'a> extern "C" fn(int) -> int) { }
-fn foo23(t: for<'a> unsafe extern "C" fn(int) -> int) { }
+fn foo20(t: for<'a> fn(i32) -> i32) { }
+fn foo21(t: for<'a> unsafe fn(i32) -> i32) { }
+fn foo22(t: for<'a> extern "C" fn(i32) -> i32) { }
+fn foo23(t: for<'a> unsafe extern "C" fn(i32) -> i32) { }
 
 fn main() {
 }
diff --git a/src/test/run-pass/hrtb-trait-object-paren-notation.rs b/src/test/run-pass/hrtb-trait-object-paren-notation.rs
index e17e0ae2189..1b62a8e809c 100644
--- a/src/test/run-pass/hrtb-trait-object-paren-notation.rs
+++ b/src/test/run-pass/hrtb-trait-object-paren-notation.rs
@@ -16,7 +16,7 @@ trait FnLike<A,R> {
     fn call(&self, arg: A) -> R;
 }
 
-type FnObject<'b> = for<'a> FnLike(&'a int) -> (&'a int) + 'b;
+type FnObject<'b> = for<'a> FnLike<(&'a i32,), &'a i32> + 'b;
 
 struct Identity;
 
diff --git a/src/test/run-pass/issue-13655.rs b/src/test/run-pass/issue-13655.rs
index 6fdaac99204..81a8b29461c 100644
--- a/src/test/run-pass/issue-13655.rs
+++ b/src/test/run-pass/issue-13655.rs
@@ -13,7 +13,8 @@ use std::ops::Fn;
 
 struct Foo<T>(T);
 
-impl<T: Copy> Fn<(), T> for Foo<T> {
+impl<T: Copy> Fn<()> for Foo<T> {
+    type Output = T;
     extern "rust-call" fn call(&self, _: ()) -> T {
       match *self {
         Foo(t) => t
diff --git a/src/test/run-pass/issue-14958.rs b/src/test/run-pass/issue-14958.rs
index 1ffd349a653..814a743648d 100644
--- a/src/test/run-pass/issue-14958.rs
+++ b/src/test/run-pass/issue-14958.rs
@@ -14,7 +14,8 @@ trait Foo {}
 
 struct Bar;
 
-impl<'a> std::ops::Fn<(&'a (Foo+'a),), ()> for Bar {
+impl<'a> std::ops::Fn<(&'a (Foo+'a),)> for Bar {
+    type Output = ();
     extern "rust-call" fn call(&self, _: (&'a Foo,)) {}
 }
 
diff --git a/src/test/run-pass/issue-14959.rs b/src/test/run-pass/issue-14959.rs
index 99472bb3610..33281d7d78f 100644
--- a/src/test/run-pass/issue-14959.rs
+++ b/src/test/run-pass/issue-14959.rs
@@ -33,7 +33,9 @@ impl Alloy {
     }
 }
 
-impl<'a, 'b> Fn<(&'b mut (Response+'b),),()> for SendFile<'a> {
+impl<'a, 'b> Fn<(&'b mut (Response+'b),)> for SendFile<'a> {
+    type Output = ();
+
     extern "rust-call" fn call(&self, (_res,): (&'b mut (Response+'b),)) {}
 }
 
diff --git a/src/test/run-pass/issue-16668.rs b/src/test/run-pass/issue-16668.rs
index 75b1e11ddc1..e82add61aa3 100644
--- a/src/test/run-pass/issue-16668.rs
+++ b/src/test/run-pass/issue-16668.rs
@@ -15,7 +15,7 @@
 #![feature(unboxed_closures)]
 
 struct Parser<'a, I, O> {
-    parse: Box<FnMut<(I,), Result<O, String>> + 'a>
+    parse: Box<FnMut(I) -> Result<O, String> + 'a>
 }
 
 impl<'a, I, O: 'a> Parser<'a, I, O> {
diff --git a/src/test/run-pass/issue-16739.rs b/src/test/run-pass/issue-16739.rs
index cb6f068cf45..389baecafd1 100644
--- a/src/test/run-pass/issue-16739.rs
+++ b/src/test/run-pass/issue-16739.rs
@@ -15,27 +15,30 @@
 // Test that unboxing shim for calling rust-call ABI methods through a
 // trait box works and does not cause an ICE.
 
-struct Foo { foo: uint }
+struct Foo { foo: u32 }
 
-impl FnMut<(), uint> for Foo {
-    extern "rust-call" fn call_mut(&mut self, _: ()) -> uint { self.foo }
+impl FnMut<()> for Foo {
+    type Output = u32;
+    extern "rust-call" fn call_mut(&mut self, _: ()) -> u32 { self.foo }
 }
 
-impl FnMut<(uint,), uint> for Foo {
-    extern "rust-call" fn call_mut(&mut self, (x,): (uint,)) -> uint { self.foo + x }
+impl FnMut<(u32,)> for Foo {
+    type Output = u32;
+    extern "rust-call" fn call_mut(&mut self, (x,): (u32,)) -> u32 { self.foo + x }
 }
 
-impl FnMut<(uint, uint), uint> for Foo {
-    extern "rust-call" fn call_mut(&mut self, (x, y): (uint, uint)) -> uint { self.foo + x + y }
+impl FnMut<(u32,u32)> for Foo {
+    type Output = u32;
+    extern "rust-call" fn call_mut(&mut self, (x, y): (u32, u32)) -> u32 { self.foo + x + y }
 }
 
 fn main() {
-    let mut f = box Foo { foo: 42 } as Box<FnMut<(), uint>>;
+    let mut f = box Foo { foo: 42 } as Box<FnMut() -> u32>;
     assert_eq!(f.call_mut(()), 42);
 
-    let mut f = box Foo { foo: 40 } as Box<FnMut<(uint,), uint>>;
+    let mut f = box Foo { foo: 40 } as Box<FnMut(u32) -> u32>;
     assert_eq!(f.call_mut((2,)), 42);
 
-    let mut f = box Foo { foo: 40 } as Box<FnMut<(uint, uint), uint>>;
+    let mut f = box Foo { foo: 40 } as Box<FnMut(u32, u32) -> u32>;
     assert_eq!(f.call_mut((1, 1)), 42);
 }
diff --git a/src/test/run-pass/object-method-numbering.rs b/src/test/run-pass/object-method-numbering.rs
new file mode 100644
index 00000000000..8da753acb96
--- /dev/null
+++ b/src/test/run-pass/object-method-numbering.rs
@@ -0,0 +1,36 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test for using an object with an associated type binding as the
+// instantiation for a generic type with a bound.
+
+trait SomeTrait {
+    type SomeType;
+
+    fn get(&self) -> Self::SomeType;
+}
+
+fn get_int<T:SomeTrait<SomeType=i32>+?Sized>(x: &T) -> i32 {
+    x.get()
+}
+
+impl SomeTrait for i32 {
+    type SomeType = i32;
+    fn get(&self) -> i32 {
+        *self
+    }
+}
+
+fn main() {
+    let x = 22_i32;
+    let x1: &SomeTrait<SomeType=i32> = &x;
+    let y = get_int(x1);
+    assert_eq!(x, y);
+}
diff --git a/src/test/run-pass/overloaded-calls-param-vtables.rs b/src/test/run-pass/overloaded-calls-param-vtables.rs
index 56887636d5d..2838909c1be 100644
--- a/src/test/run-pass/overloaded-calls-param-vtables.rs
+++ b/src/test/run-pass/overloaded-calls-param-vtables.rs
@@ -17,13 +17,15 @@ use std::ops::Add;
 
 struct G<A>;
 
-impl<'a, A: Add<int, Output=int>> Fn<(A,), int> for G<A> {
-    extern "rust-call" fn call(&self, (arg,): (A,)) -> int {
+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)
     }
 }
 
 fn main() {
     // ICE trigger
-    G(1i);
+    G(1_i32);
 }
diff --git a/src/test/run-pass/overloaded-calls-simple.rs b/src/test/run-pass/overloaded-calls-simple.rs
index bb5b88d3674..f9e838d9b3d 100644
--- a/src/test/run-pass/overloaded-calls-simple.rs
+++ b/src/test/run-pass/overloaded-calls-simple.rs
@@ -13,34 +13,37 @@
 use std::ops::{Fn, FnMut, FnOnce};
 
 struct S1 {
-    x: int,
-    y: int,
+    x: i32,
+    y: i32,
 }
 
-impl FnMut<(int,),int> for S1 {
-    extern "rust-call" fn call_mut(&mut self, (z,): (int,)) -> int {
+impl FnMut<(i32,)> for S1 {
+    type Output = i32;
+    extern "rust-call" fn call_mut(&mut self, (z,): (i32,)) -> i32 {
         self.x * self.y * z
     }
 }
 
 struct S2 {
-    x: int,
-    y: int,
+    x: i32,
+    y: i32,
 }
 
-impl Fn<(int,),int> for S2 {
-    extern "rust-call" fn call(&self, (z,): (int,)) -> int {
+impl Fn<(i32,)> for S2 {
+    type Output = i32;
+    extern "rust-call" fn call(&self, (z,): (i32,)) -> i32 {
         self.x * self.y * z
     }
 }
 
 struct S3 {
-    x: int,
-    y: int,
+    x: i32,
+    y: i32,
 }
 
-impl FnOnce<(int,int),int> for S3 {
-    extern "rust-call" fn call_once(self, (z,zz): (int,int)) -> int {
+impl FnOnce<(i32,i32)> for S3 {
+    type Output = i32;
+    extern "rust-call" fn call_once(self, (z,zz): (i32,i32)) -> i32 {
         self.x * self.y * z * zz
     }
 }
diff --git a/src/test/run-pass/overloaded-calls-zero-args.rs b/src/test/run-pass/overloaded-calls-zero-args.rs
index 809a251fe80..ce7395673b3 100644
--- a/src/test/run-pass/overloaded-calls-zero-args.rs
+++ b/src/test/run-pass/overloaded-calls-zero-args.rs
@@ -13,12 +13,13 @@
 use std::ops::{FnMut};
 
 struct S {
-    x: int,
-    y: int,
+    x: i32,
+    y: i32,
 }
 
-impl FnMut<(),int> for S {
-    extern "rust-call" fn call_mut(&mut self, (): ()) -> int {
+impl FnMut<()> for S {
+    type Output = i32;
+    extern "rust-call" fn call_mut(&mut self, (): ()) -> i32 {
         self.x * self.y
     }
 }
diff --git a/src/test/run-pass/unboxed-closures-boxed.rs b/src/test/run-pass/unboxed-closures-boxed.rs
index dc35d5bf2ca..27528ca5d56 100644
--- a/src/test/run-pass/unboxed-closures-boxed.rs
+++ b/src/test/run-pass/unboxed-closures-boxed.rs
@@ -14,9 +14,9 @@
 
 use std::ops::FnMut;
 
- fn make_adder(x: int) -> Box<FnMut<(int,),int>+'static> {
-    (box move |&mut: y: int| -> int { x + y }) as
-        Box<FnMut<(int,),int>+'static>
+ fn make_adder(x: i32) -> Box<FnMut(i32)->i32+'static> {
+    (box move |&mut: y: i32| -> i32 { x + y }) as
+        Box<FnMut(i32)->i32+'static>
 }
 
 pub fn main() {
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 8af0547e5e5..5d6029e703b 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
@@ -18,21 +18,22 @@ use std::ops::{Fn,FnMut,FnOnce};
 
 struct S;
 
-impl Fn<(int,),int> for S {
-    extern "rust-call" fn call(&self, (x,): (int,)) -> int {
+impl Fn<(i32,)> for S {
+    type Output = i32;
+    extern "rust-call" fn call(&self, (x,): (i32,)) -> i32 {
         x * x
     }
 }
 
-fn call_it<F:Fn(int)->int>(f: &F, x: int) -> int {
+fn call_it<F:Fn(i32)->i32>(f: &F, x: i32) -> i32 {
     f(x)
 }
 
-fn call_it_mut<F:FnMut(int)->int>(f: &mut F, x: int) -> int {
+fn call_it_mut<F:FnMut(i32)->i32>(f: &mut F, x: i32) -> i32 {
     f(x)
 }
 
-fn call_it_once<F:FnOnce(int)->int>(f: F, x: int) -> int {
+fn call_it_once<F:FnOnce(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 068080e256d..95dae41c684 100644
--- a/src/test/run-pass/unboxed-closures-fnmut-as-fnonce.rs
+++ b/src/test/run-pass/unboxed-closures-fnmut-as-fnonce.rs
@@ -18,17 +18,19 @@ use std::ops::{FnMut,FnOnce};
 
 struct S;
 
-impl FnMut<(int,),int> for S {
-    extern "rust-call" fn call_mut(&mut self, (x,): (int,)) -> int {
+impl FnMut<(i32,)> for S {
+    type Output = i32;
+
+    extern "rust-call" fn call_mut(&mut self, (x,): (i32,)) -> i32 {
         x * x
     }
 }
 
-fn call_it_mut<F:FnMut(int)->int>(f: &mut F, x: int) -> int {
+fn call_it_mut<F:FnMut(i32)->i32>(f: &mut F, x: i32) -> i32 {
     f(x)
 }
 
-fn call_it_once<F:FnOnce(int)->int>(f: F, x: int) -> int {
+fn call_it_once<F:FnOnce(i32)->i32>(f: F, x: i32) -> i32 {
     f(x)
 }
 
diff --git a/src/test/run-pass/unboxed-closures-generic.rs b/src/test/run-pass/unboxed-closures-generic.rs
index 0edeeb8d198..04c124946c9 100644
--- a/src/test/run-pass/unboxed-closures-generic.rs
+++ b/src/test/run-pass/unboxed-closures-generic.rs
@@ -12,12 +12,12 @@
 
 use std::ops::FnMut;
 
-fn call_it<F:FnMut<(int,int),int>>(y: int, mut f: F) -> int {
+fn call_it<F:FnMut(i32,i32)->i32>(y: i32, mut f: F) -> i32 {
     f(2, y)
 }
 
 pub fn main() {
-    let f = |&mut: x: int, y: int| -> int { x + y };
+    let f = |&mut: x: i32, y: i32| -> i32 { x + y };
     let z = call_it(3, f);
     println!("{}", z);
     assert_eq!(z, 5);
diff --git a/src/test/run-pass/unboxed-closures-manual-impl.rs b/src/test/run-pass/unboxed-closures-manual-impl.rs
index 88c9ceae4a1..37075de0405 100644
--- a/src/test/run-pass/unboxed-closures-manual-impl.rs
+++ b/src/test/run-pass/unboxed-closures-manual-impl.rs
@@ -15,17 +15,19 @@ use std::ops::FnMut;
 
 struct S;
 
-impl FnMut<(int,),int> for S {
-    extern "rust-call" fn call_mut(&mut self, (x,): (int,)) -> int {
+impl FnMut<(i32,)> for S {
+    type Output = i32;
+
+    extern "rust-call" fn call_mut(&mut self, (x,): (i32,)) -> i32 {
         x * x
     }
 }
 
-fn call_it<F:FnMut(int)->int>(mut f: F, x: int) -> int {
+fn call_it<F:FnMut(i32)->i32>(mut f: F, x: i32) -> i32 {
     f(x) + 3
 }
 
-fn call_box(f: &mut FnMut(int) -> int, x: int) -> int {
+fn call_box(f: &mut FnMut(i32) -> i32, x: i32) -> i32 {
     f(x) + 3
 }
 
diff --git a/src/test/run-pass/unboxed-closures-monomorphization.rs b/src/test/run-pass/unboxed-closures-monomorphization.rs
index 6701f879e4f..6dfa4c124e2 100644
--- a/src/test/run-pass/unboxed-closures-monomorphization.rs
+++ b/src/test/run-pass/unboxed-closures-monomorphization.rs
@@ -16,17 +16,17 @@
 #![feature(unboxed_closures)]
 
 fn main(){
-    fn bar<'a, T:Clone+'a> (t: T) -> Box<FnMut<(),T> + 'a> {
+    fn bar<'a, T:Clone+'a> (t: T) -> Box<FnMut()->T + 'a> {
         box move |&mut:| t.clone()
     }
 
-    let mut f = bar(42u);
+    let mut f = bar(42_u32);
     assert_eq!(f.call_mut(()), 42);
 
     let mut f = bar("forty-two");
     assert_eq!(f.call_mut(()), "forty-two");
 
-    let x = 42u;
+    let x = 42_u32;
     let mut f = bar(&x);
     assert_eq!(f.call_mut(()), &x);
 
diff --git a/src/test/run-pass/unboxed-closures-sugar-object.rs b/src/test/run-pass/unboxed-closures-sugar-object.rs
index d65de438514..fff841a2f05 100644
--- a/src/test/run-pass/unboxed-closures-sugar-object.rs
+++ b/src/test/run-pass/unboxed-closures-sugar-object.rs
@@ -29,7 +29,7 @@ impl<X> Getter<X,X> for Identity {
 }
 
 fn main() {
-    let x: &Getter(int) -> (int,) = &Identity;
+    let x: &Getter<(i32,), (i32,)> = &Identity;
     let (y,) = x.get((22,));
     assert_eq!(y, 22);
 }