rollup merge of #20645: nikomatsakis/rustbook-ice

Conflicts:
	src/librustc/middle/mem_categorization.rs
	src/librustc/middle/ty.rs
	src/librustc_trans/trans/base.rs
	src/librustc_trans/trans/expr.rs
	src/librustc_trans/trans/foreign.rs
	src/librustc_typeck/check/mod.rs

23 files changed, 386 insertions, 177 deletions

diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs
index de3ce9f115e..f7fc90bcef6 100644
--- a/src/librustc/middle/cfg/construct.rs
+++ b/src/librustc/middle/cfg/construct.rs
@@ -514,7 +514,7 @@ impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
 
         let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
         let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
-        if return_ty == ty::FnDiverging {
+        if return_ty.diverges() {
             self.add_node(ast::DUMMY_NODE_ID, &[])
         } else {
             ret
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index 046271613ca..d93b323ad07 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -848,7 +848,12 @@ impl<'d,'t,'tcx,TYPER:mc::Typer<'tcx>> ExprUseVisitor<'d,'t,'tcx,TYPER> {
                 None => {}
                 Some(method_ty) => {
                     let cmt = return_if_err!(self.mc.cat_expr_autoderefd(expr, i));
-                    let self_ty = ty::ty_fn_args(method_ty)[0];
+
+                    // the method call infrastructure should have
+                    // replaced all late-bound regions with variables:
+                    let self_ty = ty::ty_fn_sig(method_ty).input(0);
+                    let self_ty = ty::assert_no_late_bound_regions(self.tcx(), &self_ty);
+
                     let (m, r) = match self_ty.sty {
                         ty::ty_rptr(r, ref m) => (m.mutbl, r),
                         _ => self.tcx().sess.span_bug(expr.span,
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index dab8faa3f78..850033b3ed1 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -112,6 +112,7 @@ use self::VarKind::*;
 use middle::def::*;
 use middle::mem_categorization::Typer;
 use middle::pat_util;
+use middle::region::CodeExtent;
 use middle::ty;
 use middle::ty::UnboxedClosureTyper;
 use lint;
@@ -1149,8 +1150,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> {
 
           ast::ExprCall(ref f, ref args) => {
             let diverges = !self.ir.tcx.is_method_call(expr.id) && {
-                let t_ret = ty::ty_fn_ret(ty::expr_ty_adjusted(self.ir.tcx, &**f));
-                t_ret == ty::FnDiverging
+                ty::ty_fn_ret(ty::expr_ty_adjusted(self.ir.tcx, &**f)).diverges()
             };
             let succ = if diverges {
                 self.s.exit_ln
@@ -1164,7 +1164,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> {
           ast::ExprMethodCall(_, _, ref args) => {
             let method_call = ty::MethodCall::expr(expr.id);
             let method_ty = self.ir.tcx.method_map.borrow().get(&method_call).unwrap().ty;
-            let diverges = ty::ty_fn_ret(method_ty) == ty::FnDiverging;
+            let diverges = ty::ty_fn_ret(method_ty).diverges();
             let succ = if diverges {
                 self.s.exit_ln
             } else {
@@ -1514,11 +1514,11 @@ fn check_fn(_v: &Liveness,
 }
 
 impl<'a, 'tcx> Liveness<'a, 'tcx> {
-    fn fn_ret(&self, id: NodeId) -> ty::FnOutput<'tcx> {
+    fn fn_ret(&self, id: NodeId) -> ty::PolyFnOutput<'tcx> {
         let fn_ty = ty::node_id_to_type(self.ir.tcx, id);
         match fn_ty.sty {
             ty::ty_unboxed_closure(closure_def_id, _, substs) =>
-                self.ir.tcx.unboxed_closure_type(closure_def_id, substs).sig.0.output,
+                self.ir.tcx.unboxed_closure_type(closure_def_id, substs).sig.output(),
             _ =>
                 ty::ty_fn_ret(fn_ty),
         }
@@ -1529,8 +1529,16 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> {
                  sp: Span,
                  _fk: FnKind,
                  entry_ln: LiveNode,
-                 body: &ast::Block) {
-        match self.fn_ret(id) {
+                 body: &ast::Block)
+    {
+        // within the fn body, late-bound regions are liberated:
+        let fn_ret =
+            ty::liberate_late_bound_regions(
+                self.ir.tcx,
+                CodeExtent::from_node_id(body.id),
+                &self.fn_ret(id));
+
+        match fn_ret {
             ty::FnConverging(t_ret)
                 if self.live_on_entry(entry_ln, self.s.no_ret_var).is_some() => {
 
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index c472ea4a814..b1afd30a13a 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -857,7 +857,9 @@ impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
 
         let base_cmt = match method_ty {
             Some(method_ty) => {
-                let ref_ty = ty::ty_fn_ret(method_ty).unwrap();
+                let ref_ty =
+                    ty::assert_no_late_bound_regions(
+                        self.tcx(), &ty::ty_fn_ret(method_ty)).unwrap();
                 self.cat_rvalue_node(node.id(), node.span(), ref_ty)
             }
             None => base_cmt
@@ -937,9 +939,12 @@ impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
 
         let element_ty = match method_ty {
             Some(method_ty) => {
-                let ref_ty = ty::ty_fn_ret(method_ty).unwrap();
+                let ref_ty = self.overloaded_method_return_ty(method_ty);
                 base_cmt = self.cat_rvalue_node(elt.id(), elt.span(), ref_ty);
-                ty::ty_fn_args(method_ty)[0]
+
+                // FIXME(#20649) -- why are we using the `self_ty` as the element type...?
+                let self_ty = ty::ty_fn_sig(method_ty).input(0);
+                ty::assert_no_late_bound_regions(self.tcx(), &self_ty)
             }
             None => {
                 match ty::array_element_ty(self.tcx(), base_cmt.ty) {
@@ -1261,6 +1266,19 @@ impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
 
         Ok(())
     }
+
+    fn overloaded_method_return_ty(&self,
+                                   method_ty: Ty<'tcx>)
+                                   -> Ty<'tcx>
+    {
+        // When we process an overloaded `*` or `[]` etc, we often
+        // need to extract the return type of the method. These method
+        // types are generated by method resolution and always have
+        // all late-bound regions fully instantiated, so we just want
+        // to skip past the binder.
+        ty::assert_no_late_bound_regions(self.tcx(), &ty::ty_fn_ret(method_ty))
+            .unwrap() // overloaded ops do not diverge, either
+    }
 }
 
 #[derive(Copy)]
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 593c144f888..9f44d02e07e 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1054,6 +1054,10 @@ pub enum FnOutput<'tcx> {
 }
 
 impl<'tcx> FnOutput<'tcx> {
+    pub fn diverges(&self) -> bool {
+        *self == FnDiverging
+    }
+
     pub fn unwrap(self) -> Ty<'tcx> {
         match self {
             ty::FnConverging(t) => t,
@@ -1062,6 +1066,14 @@ impl<'tcx> FnOutput<'tcx> {
     }
 }
 
+pub type PolyFnOutput<'tcx> = Binder<FnOutput<'tcx>>;
+
+impl<'tcx> PolyFnOutput<'tcx> {
+    pub fn diverges(&self) -> bool {
+        self.0.diverges()
+    }
+}
+
 /// Signature of a function type, which I have arbitrarily
 /// decided to use to refer to the input/output types.
 ///
@@ -1077,6 +1089,21 @@ pub struct FnSig<'tcx> {
 
 pub type PolyFnSig<'tcx> = Binder<FnSig<'tcx>>;
 
+impl<'tcx> PolyFnSig<'tcx> {
+    pub fn inputs(&self) -> ty::Binder<Vec<Ty<'tcx>>> {
+        ty::Binder(self.0.inputs.clone())
+    }
+    pub fn input(&self, index: uint) -> ty::Binder<Ty<'tcx>> {
+        ty::Binder(self.0.inputs[index])
+    }
+    pub fn output(&self) -> ty::Binder<FnOutput<'tcx>> {
+        ty::Binder(self.0.output.clone())
+    }
+    pub fn variadic(&self) -> bool {
+        self.0.variadic
+    }
+}
+
 #[derive(Clone, Copy, PartialEq, Eq, Hash, Show)]
 pub struct ParamTy {
     pub space: subst::ParamSpace,
@@ -4146,8 +4173,8 @@ pub fn ty_fn_abi(fty: Ty) -> abi::Abi {
 }
 
 // Type accessors for substructures of types
-pub fn ty_fn_args<'tcx>(fty: Ty<'tcx>) -> &'tcx [Ty<'tcx>] {
-    ty_fn_sig(fty).0.inputs.as_slice()
+pub fn ty_fn_args<'tcx>(fty: Ty<'tcx>) -> ty::Binder<Vec<Ty<'tcx>>> {
+    ty_fn_sig(fty).inputs()
 }
 
 pub fn ty_closure_store(fty: Ty) -> TraitStore {
@@ -4163,9 +4190,9 @@ pub fn ty_closure_store(fty: Ty) -> TraitStore {
     }
 }
 
-pub fn ty_fn_ret<'tcx>(fty: Ty<'tcx>) -> FnOutput<'tcx> {
+pub fn ty_fn_ret<'tcx>(fty: Ty<'tcx>) -> Binder<FnOutput<'tcx>> {
     match fty.sty {
-        ty_bare_fn(_, ref f) => f.sig.0.output,
+        ty_bare_fn(_, ref f) => f.sig.output(),
         ref s => {
             panic!("ty_fn_ret() called on non-fn type: {:?}", s)
         }
@@ -4320,9 +4347,12 @@ pub fn adjust_ty<'tcx, F>(cx: &ctxt<'tcx>,
                             let method_call = MethodCall::autoderef(expr_id, i);
                             match method_type(method_call) {
                                 Some(method_ty) => {
-                                    if let ty::FnConverging(result_type) = ty_fn_ret(method_ty) {
-                                        adjusted_ty = result_type;
-                                    }
+                                    // overloaded deref operators have all late-bound
+                                    // regions fully instantiated and coverge
+                                    let fn_ret =
+                                        ty::assert_no_late_bound_regions(cx,
+                                                                         &ty_fn_ret(method_ty));
+                                    adjusted_ty = fn_ret.unwrap();
                                 }
                                 None => {}
                             }
@@ -5144,7 +5174,9 @@ impl<'tcx> VariantInfo<'tcx> {
         match ast_variant.node.kind {
             ast::TupleVariantKind(ref args) => {
                 let arg_tys = if args.len() > 0 {
-                    ty_fn_args(ctor_ty).iter().map(|a| *a).collect()
+                    // the regions in the argument types come from the
+                    // enum def'n, and hence will all be early bound
+                    ty::assert_no_late_bound_regions(cx, &ty_fn_args(ctor_ty))
                 } else {
                     Vec::new()
                 };
@@ -5160,7 +5192,6 @@ impl<'tcx> VariantInfo<'tcx> {
                 };
             },
             ast::StructVariantKind(ref struct_def) => {
-
                 let fields: &[StructField] = struct_def.fields.index(&FullRange);
 
                 assert!(fields.len() > 0);
@@ -5792,40 +5823,6 @@ pub fn is_binopable<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>, op: ast::BinOp) -> bool
     return tbl[tycat(cx, ty) as uint ][opcat(op) as uint];
 }
 
-/// Returns an equivalent type with all the typedefs and self regions removed.
-pub fn normalize_ty<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
-    let u = TypeNormalizer(cx).fold_ty(ty);
-    return u;
-
-    struct TypeNormalizer<'a, 'tcx: 'a>(&'a ctxt<'tcx>);
-
-    impl<'a, 'tcx> TypeFolder<'tcx> for TypeNormalizer<'a, 'tcx> {
-        fn tcx(&self) -> &ctxt<'tcx> { let TypeNormalizer(c) = *self; c }
-
-        fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
-            match self.tcx().normalized_cache.borrow().get(&ty).cloned() {
-                None => {}
-                Some(u) => return u
-            }
-
-            let t_norm = ty_fold::super_fold_ty(self, ty);
-            self.tcx().normalized_cache.borrow_mut().insert(ty, t_norm);
-            return t_norm;
-        }
-
-        fn fold_region(&mut self, _: ty::Region) -> ty::Region {
-            ty::ReStatic
-        }
-
-        fn fold_substs(&mut self,
-                       substs: &subst::Substs<'tcx>)
-                       -> subst::Substs<'tcx> {
-            subst::Substs { regions: subst::ErasedRegions,
-                            types: substs.types.fold_with(self) }
-        }
-    }
-}
-
 // Returns the repeat count for a repeating vector expression.
 pub fn eval_repeat_count(tcx: &ctxt, count_expr: &ast::Expr) -> uint {
     match const_eval::eval_const_expr_partial(tcx, count_expr) {
@@ -6205,7 +6202,7 @@ pub fn hash_crate_independent<'tcx>(tcx: &ctxt<'tcx>, ty: Ty<'tcx>, svh: &Svh) -
             mt.mutbl.hash(state);
         };
         let fn_sig = |&: state: &mut sip::SipState, sig: &Binder<FnSig<'tcx>>| {
-            let sig = anonymize_late_bound_regions(tcx, sig);
+            let sig = anonymize_late_bound_regions(tcx, sig).0;
             for a in sig.inputs.iter() { helper(tcx, *a, svh, state); }
             if let ty::FnConverging(output) = sig.output {
                 helper(tcx, output, svh, state);
@@ -6266,7 +6263,7 @@ pub fn hash_crate_independent<'tcx>(tcx: &ctxt<'tcx>, ty: Ty<'tcx>, svh: &Svh) -
                     did(state, data.principal_def_id());
                     hash!(data.bounds);
 
-                    let principal = anonymize_late_bound_regions(tcx, &data.principal);
+                    let principal = anonymize_late_bound_regions(tcx, &data.principal).0;
                     for subty in principal.substs.types.iter() {
                         helper(tcx, *subty, svh, state);
                     }
@@ -6697,6 +6694,16 @@ pub fn binds_late_bound_regions<'tcx, T>(
     count_late_bound_regions(tcx, value) > 0
 }
 
+pub fn assert_no_late_bound_regions<'tcx, T>(
+    tcx: &ty::ctxt<'tcx>,
+    value: &Binder<T>)
+    -> T
+    where T : TypeFoldable<'tcx> + Repr<'tcx> + Clone
+{
+    assert!(!binds_late_bound_regions(tcx, value));
+    value.0.clone()
+}
+
 /// Replace any late-bound regions bound in `value` with `'static`. Useful in trans but also
 /// method lookup and a few other places where precise region relationships are not required.
 pub fn erase_late_bound_regions<'tcx, T>(
@@ -6719,14 +6726,14 @@ pub fn erase_late_bound_regions<'tcx, T>(
 pub fn anonymize_late_bound_regions<'tcx, T>(
     tcx: &ctxt<'tcx>,
     sig: &Binder<T>)
-    -> T
+    -> Binder<T>
     where T : TypeFoldable<'tcx> + Repr<'tcx>,
 {
     let mut counter = 0;
-    replace_late_bound_regions(tcx, sig, |_, db| {
+    ty::Binder(replace_late_bound_regions(tcx, sig, |_, db| {
         counter += 1;
         ReLateBound(db, BrAnon(counter))
-    }).0
+    }).0)
 }
 
 /// Replaces the late-bound-regions in `value` that are bound by `value`.
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 15c2845882c..dadbae9349f 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -868,6 +868,9 @@ impl<'a, 'tcx> TypeFolder<'tcx> for RegionEraser<'a, 'tcx> {
     fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
 
     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
+        // because whether or not a region is bound affects subtyping,
+        // we can't erase the bound/free distinction, but we can
+        // replace all free regions with 'static
         match r {
             ty::ReLateBound(..) | ty::ReEarlyBound(..) => r,
             _ => ty::ReStatic
diff --git a/src/librustc_trans/trans/base.rs b/src/librustc_trans/trans/base.rs
index b0339529fd8..057d0f378e6 100644
--- a/src/librustc_trans/trans/base.rs
+++ b/src/librustc_trans/trans/base.rs
@@ -283,35 +283,40 @@ pub fn decl_rust_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                               fn_ty: Ty<'tcx>, name: &str) -> ValueRef {
     let fn_ty = monomorphize::normalize_associated_type(ccx.tcx(), &fn_ty);
 
-    let (inputs, output, abi, env) = match fn_ty.sty {
+    let function_type; // placeholder so that the memory ownership works out ok
+
+    let (sig, abi, env) = match fn_ty.sty {
         ty::ty_bare_fn(_, ref f) => {
-            (f.sig.0.inputs.clone(), f.sig.0.output, f.abi, None)
+            (&f.sig, f.abi, None)
         }
         ty::ty_unboxed_closure(closure_did, _, substs) => {
             let typer = common::NormalizingUnboxedClosureTyper::new(ccx.tcx());
-            let function_type = typer.unboxed_closure_type(closure_did, substs);
+            function_type = typer.unboxed_closure_type(closure_did, substs);
             let self_type = self_type_for_unboxed_closure(ccx, closure_did, fn_ty);
             let llenvironment_type = type_of_explicit_arg(ccx, self_type);
             debug!("decl_rust_fn: function_type={} self_type={}",
                    function_type.repr(ccx.tcx()),
                    self_type.repr(ccx.tcx()));
-            (function_type.sig.0.inputs,
-             function_type.sig.0.output,
-             RustCall,
-             Some(llenvironment_type))
+            (&function_type.sig, RustCall, Some(llenvironment_type))
         }
         _ => panic!("expected closure or fn")
     };
 
-    let llfty = type_of_rust_fn(ccx, env, inputs.index(&FullRange), output, abi);
-    debug!("decl_rust_fn(input count={},type={})",
-           inputs.len(),
+    let sig = ty::erase_late_bound_regions(ccx.tcx(), sig);
+    let sig = ty::Binder(sig);
+
+    let llfty = type_of_rust_fn(ccx, env, &sig, abi);
+
+    debug!("decl_rust_fn(sig={}, type={})",
+           sig.repr(ccx.tcx()),
            ccx.tn().type_to_string(llfty));
 
-    let llfn = decl_fn(ccx, name, llvm::CCallConv, llfty, output);
+    let llfn = decl_fn(ccx, name, llvm::CCallConv, llfty, sig.0.output /* (1) */);
     let attrs = get_fn_llvm_attributes(ccx, fn_ty);
     attrs.apply_llfn(llfn);
 
+    // (1) it's ok to directly access sig.0.output because we erased all late-bound-regions above
+
     llfn
 }
 
@@ -1938,7 +1943,7 @@ pub fn trans_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
     debug!("trans_fn(param_substs={})", param_substs.repr(ccx.tcx()));
     let _icx = push_ctxt("trans_fn");
     let fn_ty = ty::node_id_to_type(ccx.tcx(), id);
-    let output_type = ty::ty_fn_ret(fn_ty);
+    let output_type = ty::erase_late_bound_regions(ccx.tcx(), &ty::ty_fn_ret(fn_ty));
     let abi = ty::ty_fn_abi(fn_ty);
     trans_closure(ccx,
                   decl,
@@ -1981,7 +1986,9 @@ pub fn trans_named_tuple_constructor<'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>,
     let tcx = ccx.tcx();
 
     let result_ty = match ctor_ty.sty {
-        ty::ty_bare_fn(_, ref bft) => bft.sig.0.output.unwrap(),
+        ty::ty_bare_fn(_, ref bft) => {
+            ty::erase_late_bound_regions(bcx.tcx(), &bft.sig.output()).unwrap()
+        }
         _ => ccx.sess().bug(
             format!("trans_enum_variant_constructor: \
                      unexpected ctor return type {}",
@@ -2053,7 +2060,9 @@ fn trans_enum_variant_or_tuple_like_struct<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx
     let ctor_ty = monomorphize::apply_param_substs(ccx.tcx(), param_substs, &ctor_ty);
 
     let result_ty = match ctor_ty.sty {
-        ty::ty_bare_fn(_, ref bft) => bft.sig.0.output,
+        ty::ty_bare_fn(_, ref bft) => {
+            ty::erase_late_bound_regions(ccx.tcx(), &bft.sig.output())
+        }
         _ => ccx.sess().bug(
             format!("trans_enum_variant_or_tuple_like_struct: \
                      unexpected ctor return type {}",
@@ -2067,7 +2076,9 @@ fn trans_enum_variant_or_tuple_like_struct<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx
 
     assert!(!fcx.needs_ret_allocas);
 
-    let arg_tys = ty::ty_fn_args(ctor_ty);
+    let arg_tys =
+        ty::erase_late_bound_regions(
+            ccx.tcx(), &ty::ty_fn_args(ctor_ty));
 
     let arg_datums = create_datums_for_fn_args(&fcx, arg_tys.index(&FullRange));
 
@@ -2426,25 +2437,28 @@ fn register_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 }
 
 pub fn get_fn_llvm_attributes<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, fn_ty: Ty<'tcx>)
-                                        -> llvm::AttrBuilder {
+                                        -> llvm::AttrBuilder
+{
     use middle::ty::{BrAnon, ReLateBound};
 
+    let function_type;
     let (fn_sig, abi, has_env) = match fn_ty.sty {
-        ty::ty_bare_fn(_, ref f) => (f.sig.clone(), f.abi, false),
+        ty::ty_bare_fn(_, ref f) => (&f.sig, f.abi, false),
         ty::ty_unboxed_closure(closure_did, _, substs) => {
             let typer = common::NormalizingUnboxedClosureTyper::new(ccx.tcx());
-            let function_type = typer.unboxed_closure_type(closure_did, substs);
-            (function_type.sig, RustCall, true)
+            function_type = typer.unboxed_closure_type(closure_did, substs);
+            (&function_type.sig, RustCall, true)
         }
         _ => ccx.sess().bug("expected closure or function.")
     };
 
+    let fn_sig = ty::erase_late_bound_regions(ccx.tcx(), fn_sig);
 
     // Since index 0 is the return value of the llvm func, we start
     // at either 1 or 2 depending on whether there's an env slot or not
     let mut first_arg_offset = if has_env { 2 } else { 1 };
     let mut attrs = llvm::AttrBuilder::new();
-    let ret_ty = fn_sig.0.output;
+    let ret_ty = fn_sig.output;
 
     // These have an odd calling convention, so we need to manually
     // unpack the input ty's
@@ -2452,15 +2466,15 @@ pub fn get_fn_llvm_attributes<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, fn_ty: Ty<
         ty::ty_unboxed_closure(_, _, _) => {
             assert!(abi == RustCall);
 
-            match fn_sig.0.inputs[0].sty {
+            match fn_sig.inputs[0].sty {
                 ty::ty_tup(ref inputs) => inputs.clone(),
                 _ => ccx.sess().bug("expected tuple'd inputs")
             }
         },
         ty::ty_bare_fn(..) if abi == RustCall => {
-            let mut inputs = vec![fn_sig.0.inputs[0]];
+            let mut inputs = vec![fn_sig.inputs[0]];
 
-            match fn_sig.0.inputs[1].sty {
+            match fn_sig.inputs[1].sty {
                 ty::ty_tup(ref t_in) => {
                     inputs.push_all(t_in.index(&FullRange));
                     inputs
@@ -2468,7 +2482,7 @@ pub fn get_fn_llvm_attributes<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, fn_ty: Ty<
                 _ => ccx.sess().bug("expected tuple'd inputs")
             }
         }
-        _ => fn_sig.0.inputs.clone()
+        _ => fn_sig.inputs.clone()
     };
 
     if let ty::FnConverging(ret_ty) = ret_ty {
diff --git a/src/librustc_trans/trans/callee.rs b/src/librustc_trans/trans/callee.rs
index 7b38f26913d..b7b486f1d0a 100644
--- a/src/librustc_trans/trans/callee.rs
+++ b/src/librustc_trans/trans/callee.rs
@@ -265,7 +265,7 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
     let _icx = push_ctxt("trans_fn_pointer_shim");
     let tcx = ccx.tcx();
 
-    let bare_fn_ty = ty::normalize_ty(tcx, bare_fn_ty);
+    let bare_fn_ty = normalize_ty(tcx, bare_fn_ty);
     match ccx.fn_pointer_shims().borrow().get(&bare_fn_ty) {
         Some(&llval) => { return llval; }
         None => { }
@@ -279,16 +279,13 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
 
     // Construct the "tuply" version of `bare_fn_ty`. It takes two arguments: `self`,
     // which is the fn pointer, and `args`, which is the arguments tuple.
-    let (opt_def_id, input_tys, output_ty) =
+    let (opt_def_id, sig) =
         match bare_fn_ty.sty {
             ty::ty_bare_fn(opt_def_id,
                            &ty::BareFnTy { unsafety: ast::Unsafety::Normal,
-                                          abi: synabi::Rust,
-                                          sig: ty::Binder(ty::FnSig { inputs: ref input_tys,
-                                                                      output: output_ty,
-                                                                      variadic: false })}) =>
-            {
-                (opt_def_id, input_tys, output_ty)
+                                           abi: synabi::Rust,
+                                           ref sig }) => {
+                (opt_def_id, sig)
             }
 
             _ => {
@@ -296,7 +293,8 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
                                            bare_fn_ty.repr(tcx)).index(&FullRange));
             }
         };
-    let tuple_input_ty = ty::mk_tup(tcx, input_tys.to_vec());
+    let sig = ty::erase_late_bound_regions(tcx, sig);
+    let tuple_input_ty = ty::mk_tup(tcx, sig.inputs.to_vec());
     let tuple_fn_ty = ty::mk_bare_fn(tcx,
                                      opt_def_id,
                                      tcx.mk_bare_fn(ty::BareFnTy {
@@ -305,7 +303,7 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
                                          sig: ty::Binder(ty::FnSig {
                                              inputs: vec![bare_fn_ty_ref,
                                                           tuple_input_ty],
-                                             output: output_ty,
+                                             output: sig.output,
                                              variadic: false
                                          })}));
     debug!("tuple_fn_ty: {}", tuple_fn_ty.repr(tcx));
@@ -326,11 +324,11 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
                           llfn,
                           ast::DUMMY_NODE_ID,
                           false,
-                          output_ty,
+                          sig.output,
                           &empty_substs,
                           None,
                           &block_arena);
-    let mut bcx = init_function(&fcx, false, output_ty);
+    let mut bcx = init_function(&fcx, false, sig.output);
 
     // the first argument (`self`) will be ptr to the the fn pointer
     let llfnpointer =
@@ -338,14 +336,14 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
 
     // the remaining arguments will be the untupled values
     let llargs: Vec<_> =
-        input_tys.iter()
+        sig.inputs.iter()
         .enumerate()
         .map(|(i, _)| get_param(fcx.llfn, fcx.arg_pos(i+1) as u32))
         .collect();
     assert!(!fcx.needs_ret_allocas);
 
     let dest = fcx.llretslotptr.get().map(|_|
-        expr::SaveIn(fcx.get_ret_slot(bcx, output_ty, "ret_slot"))
+        expr::SaveIn(fcx.get_ret_slot(bcx, sig.output, "ret_slot"))
     );
 
     bcx = trans_call_inner(bcx,
@@ -355,7 +353,7 @@ pub fn trans_fn_pointer_shim<'a, 'tcx>(
                            ArgVals(llargs.index(&FullRange)),
                            dest).bcx;
 
-    finish_fn(&fcx, bcx, output_ty);
+    finish_fn(&fcx, bcx, sig.output);
 
     ccx.fn_pointer_shims().borrow_mut().insert(bare_fn_ty, llfn);
 
@@ -668,7 +666,10 @@ pub fn trans_call_inner<'a, 'blk, 'tcx, F>(bcx: Block<'blk, 'tcx>,
     let mut bcx = callee.bcx;
 
     let (abi, ret_ty) = match callee_ty.sty {
-        ty::ty_bare_fn(_, ref f) => (f.abi, f.sig.0.output),
+        ty::ty_bare_fn(_, ref f) => {
+            let output = ty::erase_late_bound_regions(bcx.tcx(), &f.sig.output());
+            (f.abi, output)
+        }
         _ => panic!("expected bare rust fn or closure in trans_call_inner")
     };
 
@@ -865,13 +866,18 @@ fn trans_args_under_call_abi<'blk, 'tcx>(
                              llargs: &mut Vec<ValueRef>,
                              arg_cleanup_scope: cleanup::ScopeId,
                              ignore_self: bool)
-                             -> Block<'blk, 'tcx> {
+                             -> Block<'blk, 'tcx>
+{
+    let args =
+        ty::erase_late_bound_regions(
+            bcx.tcx(), &ty::ty_fn_args(fn_ty));
+
     // Translate the `self` argument first.
     if !ignore_self {
         let arg_datum = unpack_datum!(bcx, expr::trans(bcx, &*arg_exprs[0]));
         llargs.push(unpack_result!(bcx, {
             trans_arg_datum(bcx,
-                            ty::ty_fn_args(fn_ty)[0],
+                            args[0],
                             arg_datum,
                             arg_cleanup_scope,
                             DontAutorefArg)
@@ -926,7 +932,7 @@ fn trans_overloaded_call_args<'blk, 'tcx>(
                               ignore_self: bool)
                               -> Block<'blk, 'tcx> {
     // Translate the `self` argument first.
-    let arg_tys = ty::ty_fn_args(fn_ty);
+    let arg_tys = ty::erase_late_bound_regions(bcx.tcx(),  &ty::ty_fn_args(fn_ty));
     if !ignore_self {
         let arg_datum = unpack_datum!(bcx, expr::trans(bcx, arg_exprs[0]));
         llargs.push(unpack_result!(bcx, {
@@ -974,7 +980,7 @@ pub fn trans_args<'a, 'blk, 'tcx>(cx: Block<'blk, 'tcx>,
     debug!("trans_args(abi={})", abi);
 
     let _icx = push_ctxt("trans_args");
-    let arg_tys = ty::ty_fn_args(fn_ty);
+    let arg_tys = ty::erase_late_bound_regions(cx.tcx(), &ty::ty_fn_args(fn_ty));
     let variadic = ty::fn_is_variadic(fn_ty);
 
     let mut bcx = cx;
diff --git a/src/librustc_trans/trans/closure.rs b/src/librustc_trans/trans/closure.rs
index f057d4bcab8..ad2ed67b22c 100644
--- a/src/librustc_trans/trans/closure.rs
+++ b/src/librustc_trans/trans/closure.rs
@@ -442,7 +442,7 @@ pub fn trans_expr_fn<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                   bcx.fcx.param_substs,
                   id,
                   &[],
-                  ty::ty_fn_ret(fty),
+                  ty::erase_late_bound_regions(ccx.tcx(), &ty::ty_fn_ret(fty)),
                   ty::ty_fn_abi(fty),
                   ClosureEnv::new(freevars.index(&FullRange),
                                   BoxedClosure(cdata_ty, store)));
@@ -466,7 +466,7 @@ pub fn get_or_create_declaration_if_unboxed_closure<'a, 'tcx>(ccx: &CrateContext
 
     // Normalize type so differences in regions and typedefs don't cause
     // duplicate declarations
-    let function_type = ty::normalize_ty(ccx.tcx(), function_type);
+    let function_type = normalize_ty(ccx.tcx(), function_type);
     let params = match function_type.sty {
         ty::ty_unboxed_closure(_, _, ref substs) => substs.types.clone(),
         _ => unreachable!()
@@ -533,6 +533,8 @@ pub fn trans_unboxed_closure<'blk, 'tcx>(
         ty::with_freevars(bcx.tcx(), id, |fv| fv.iter().map(|&fv| fv).collect());
     let freevar_mode = bcx.tcx().capture_mode(id);
 
+    let sig = ty::erase_late_bound_regions(bcx.tcx(), &function_type.sig);
+
     trans_closure(bcx.ccx(),
                   decl,
                   body,
@@ -540,7 +542,7 @@ pub fn trans_unboxed_closure<'blk, 'tcx>(
                   bcx.fcx.param_substs,
                   id,
                   &[],
-                  function_type.sig.0.output,
+                  sig.output,
                   function_type.abi,
                   ClosureEnv::new(freevars.index(&FullRange),
                                   UnboxedClosure(freevar_mode)));
diff --git a/src/librustc_trans/trans/common.rs b/src/librustc_trans/trans/common.rs
index 5d3eeb39e31..237fc185636 100644
--- a/src/librustc_trans/trans/common.rs
+++ b/src/librustc_trans/trans/common.rs
@@ -58,6 +58,61 @@ use util::nodemap::FnvHashSet;
 
 pub use trans::context::CrateContext;
 
+/// Returns an equivalent type with all the typedefs and self regions removed.
+pub fn normalize_ty<'tcx>(cx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
+    let u = TypeNormalizer(cx).fold_ty(ty);
+    debug!("normalize_ty({}) = {}",
+           ty.repr(cx), u.repr(cx));
+    return u;
+
+    struct TypeNormalizer<'a, 'tcx: 'a>(&'a ty::ctxt<'tcx>);
+
+    impl<'a, 'tcx> TypeFolder<'tcx> for TypeNormalizer<'a, 'tcx> {
+        fn tcx(&self) -> &ty::ctxt<'tcx> { self.0 }
+
+        fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
+            match self.tcx().normalized_cache.borrow().get(&ty).cloned() {
+                None => {}
+                Some(u) => return u
+            }
+
+            let t_norm = ty_fold::super_fold_ty(self, ty);
+            self.tcx().normalized_cache.borrow_mut().insert(ty, t_norm);
+            return t_norm;
+        }
+
+        fn fold_binder<T>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T>
+            where T : TypeFoldable<'tcx> + Repr<'tcx>
+        {
+            // FIXME(#20526) this should replace `enter_region_binder`/`exit_region_binder`.
+            let u = ty::anonymize_late_bound_regions(self.tcx(), t);
+            ty_fold::super_fold_binder(self, &u)
+        }
+
+        fn fold_region(&mut self, r: ty::Region) -> ty::Region {
+            // because late-bound regions affect subtyping, we can't
+            // erase the bound/free distinction, but we can replace
+            // all free regions with 'static.
+            //
+            // Note that we *CAN* replace early-bound regions -- the
+            // type system never "sees" those, they get substituted
+            // away. In trans, they will always be erased to 'static
+            // whenever a substitution occurs.
+            match r {
+                ty::ReLateBound(..) => r,
+                _ => ty::ReStatic
+            }
+        }
+
+        fn fold_substs(&mut self,
+                       substs: &subst::Substs<'tcx>)
+                       -> subst::Substs<'tcx> {
+            subst::Substs { regions: subst::ErasedRegions,
+                            types: substs.types.fold_with(self) }
+        }
+    }
+}
+
 // Is the type's representation size known at compile time?
 pub fn type_is_sized<'tcx>(cx: &ty::ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
 ty::type_contents(cx, ty).is_sized(cx)
diff --git a/src/librustc_trans/trans/controlflow.rs b/src/librustc_trans/trans/controlflow.rs
index 86f0cbf7933..38d40a8322f 100644
--- a/src/librustc_trans/trans/controlflow.rs
+++ b/src/librustc_trans/trans/controlflow.rs
@@ -265,7 +265,8 @@ pub fn trans_for<'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>,
                              pat: &ast::Pat,
                              head: &ast::Expr,
                              body: &ast::Block)
-                             -> Block<'blk, 'tcx> {
+                             -> Block<'blk, 'tcx>
+{
     let _icx = push_ctxt("trans_for");
 
     //            bcx
@@ -306,7 +307,9 @@ pub fn trans_for<'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>,
                                      .borrow())[method_call]
                                      .ty;
     let method_type = monomorphize_type(loopback_bcx_in, method_type);
-    let method_result_type = ty::ty_fn_ret(method_type).unwrap();
+    let method_result_type =
+        ty::assert_no_late_bound_regions( // LB regions are instantiated in invoked methods
+            loopback_bcx_in.tcx(), &ty::ty_fn_ret(method_type)).unwrap();
     let option_cleanup_scope = body_bcx_in.fcx.push_custom_cleanup_scope();
     let option_cleanup_scope_id = cleanup::CustomScope(option_cleanup_scope);
 
diff --git a/src/librustc_trans/trans/debuginfo.rs b/src/librustc_trans/trans/debuginfo.rs
index dd612a06bca..e2e1b3a799b 100644
--- a/src/librustc_trans/trans/debuginfo.rs
+++ b/src/librustc_trans/trans/debuginfo.rs
@@ -425,10 +425,14 @@ impl<'tcx> TypeMap<'tcx> {
             ty::ty_trait(ref trait_data) => {
                 unique_type_id.push_str("trait ");
 
+                let principal =
+                    ty::erase_late_bound_regions(cx.tcx(),
+                                                 &trait_data.principal);
+
                 from_def_id_and_substs(self,
                                        cx,
-                                       trait_data.principal_def_id(),
-                                       trait_data.principal.0.substs,
+                                       principal.def_id,
+                                       principal.substs,
                                        &mut unique_type_id);
             },
             ty::ty_bare_fn(_, &ty::BareFnTy{ unsafety, abi, ref sig } ) => {
@@ -440,7 +444,9 @@ impl<'tcx> TypeMap<'tcx> {
 
                 unique_type_id.push_str(" fn(");
 
-                for &parameter_type in sig.0.inputs.iter() {
+                let sig = ty::erase_late_bound_regions(cx.tcx(), sig);
+
+                for &parameter_type in sig.inputs.iter() {
                     let parameter_type_id =
                         self.get_unique_type_id_of_type(cx, parameter_type);
                     let parameter_type_id =
@@ -449,12 +455,12 @@ impl<'tcx> TypeMap<'tcx> {
                     unique_type_id.push(',');
                 }
 
-                if sig.0.variadic {
+                if sig.variadic {
                     unique_type_id.push_str("...");
                 }
 
                 unique_type_id.push_str(")->");
-                match sig.0.output {
+                match sig.output {
                     ty::FnConverging(ret_ty) => {
                         let return_type_id = self.get_unique_type_id_of_type(cx, ret_ty);
                         let return_type_id = self.get_unique_type_id_as_string(return_type_id);
@@ -568,7 +574,9 @@ impl<'tcx> TypeMap<'tcx> {
             }
         };
 
-        for &parameter_type in sig.0.inputs.iter() {
+        let sig = ty::erase_late_bound_regions(cx.tcx(), sig);
+
+        for &parameter_type in sig.inputs.iter() {
             let parameter_type_id =
                 self.get_unique_type_id_of_type(cx, parameter_type);
             let parameter_type_id =
@@ -577,13 +585,13 @@ impl<'tcx> TypeMap<'tcx> {
             unique_type_id.push(',');
         }
 
-        if sig.0.variadic {
+        if sig.variadic {
             unique_type_id.push_str("...");
         }
 
         unique_type_id.push_str("|->");
 
-        match sig.0.output {
+        match sig.output {
             ty::FnConverging(ret_ty) => {
                 let return_type_id = self.get_unique_type_id_of_type(cx, ret_ty);
                 let return_type_id = self.get_unique_type_id_as_string(return_type_id);
@@ -2822,11 +2830,14 @@ fn subroutine_type_metadata<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
                                       unique_type_id: UniqueTypeId,
                                       signature: &ty::PolyFnSig<'tcx>,
                                       span: Span)
-                                      -> MetadataCreationResult {
-    let mut signature_metadata: Vec<DIType> = Vec::with_capacity(signature.0.inputs.len() + 1);
+                                      -> MetadataCreationResult
+{
+    let signature = ty::erase_late_bound_regions(cx.tcx(), signature);
+
+    let mut signature_metadata: Vec<DIType> = Vec::with_capacity(signature.inputs.len() + 1);
 
     // return type
-    signature_metadata.push(match signature.0.output {
+    signature_metadata.push(match signature.output {
         ty::FnConverging(ret_ty) => match ret_ty.sty {
             ty::ty_tup(ref tys) if tys.is_empty() => ptr::null_mut(),
             _ => type_metadata(cx, ret_ty, span)
@@ -2835,7 +2846,7 @@ fn subroutine_type_metadata<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
     });
 
     // regular arguments
-    for &argument_type in signature.0.inputs.iter() {
+    for &argument_type in signature.inputs.iter() {
         signature_metadata.push(type_metadata(cx, argument_type, span));
     }
 
@@ -3794,8 +3805,9 @@ fn push_debuginfo_type_name<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
             output.push(']');
         },
         ty::ty_trait(ref trait_data) => {
-            push_item_name(cx, trait_data.principal_def_id(), false, output);
-            push_type_params(cx, trait_data.principal.0.substs, output);
+            let principal = ty::erase_late_bound_regions(cx.tcx(), &trait_data.principal);
+            push_item_name(cx, principal.def_id, false, output);
+            push_type_params(cx, principal.substs, output);
         },
         ty::ty_bare_fn(_, &ty::BareFnTy{ unsafety, abi, ref sig } ) => {
             if unsafety == ast::Unsafety::Unsafe {
@@ -3810,8 +3822,9 @@ fn push_debuginfo_type_name<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 
             output.push_str("fn(");
 
-            if sig.0.inputs.len() > 0 {
-                for &parameter_type in sig.0.inputs.iter() {
+            let sig = ty::erase_late_bound_regions(cx.tcx(), sig);
+            if sig.inputs.len() > 0 {
+                for &parameter_type in sig.inputs.iter() {
                     push_debuginfo_type_name(cx, parameter_type, true, output);
                     output.push_str(", ");
                 }
@@ -3819,8 +3832,8 @@ fn push_debuginfo_type_name<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
                 output.pop();
             }
 
-            if sig.0.variadic {
-                if sig.0.inputs.len() > 0 {
+            if sig.variadic {
+                if sig.inputs.len() > 0 {
                     output.push_str(", ...");
                 } else {
                     output.push_str("...");
@@ -3829,7 +3842,7 @@ fn push_debuginfo_type_name<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 
             output.push(')');
 
-            match sig.0.output {
+            match sig.output {
                 ty::FnConverging(result_type) if ty::type_is_nil(result_type) => {}
                 ty::FnConverging(result_type) => {
                     output.push_str(" -> ");
diff --git a/src/librustc_trans/trans/expr.rs b/src/librustc_trans/trans/expr.rs
index c8db661e9c6..120e2e955e4 100644
--- a/src/librustc_trans/trans/expr.rs
+++ b/src/librustc_trans/trans/expr.rs
@@ -699,12 +699,16 @@ fn trans_index<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                        .map(|method| method.ty);
     let elt_datum = match method_ty {
         Some(method_ty) => {
+            let method_ty = monomorphize_type(bcx, method_ty);
+
             let base_datum = unpack_datum!(bcx, trans(bcx, base));
 
             // Translate index expression.
             let ix_datum = unpack_datum!(bcx, trans(bcx, idx));
 
-            let ref_ty = ty::ty_fn_ret(monomorphize_type(bcx, method_ty)).unwrap();
+            let ref_ty = // invoked methods have LB regions instantiated:
+                ty::assert_no_late_bound_regions(
+                    bcx.tcx(), &ty::ty_fn_ret(method_ty)).unwrap();
             let elt_ty = match ty::deref(ref_ty, true) {
                 None => {
                     bcx.tcx().sess.span_bug(index_expr.span,
@@ -2149,6 +2153,8 @@ fn deref_once<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                        .get(&method_call).map(|method| method.ty);
     let datum = match method_ty {
         Some(method_ty) => {
+            let method_ty = monomorphize_type(bcx, method_ty);
+
             // Overloaded. Evaluate `trans_overloaded_op`, which will
             // invoke the user's deref() method, which basically
             // converts from the `Smaht<T>` pointer that we have into
@@ -2160,7 +2166,9 @@ fn deref_once<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                 _ => datum
             };
 
-            let ref_ty = ty::ty_fn_ret(monomorphize_type(bcx, method_ty)).unwrap();
+            let ref_ty = // invoked methods have their LB regions instantiated
+                ty::assert_no_late_bound_regions(
+                    ccx.tcx(), &ty::ty_fn_ret(method_ty)).unwrap();
             let scratch = rvalue_scratch_datum(bcx, ref_ty, "overloaded_deref");
 
             unpack_result!(bcx, trans_overloaded_op(bcx, expr, method_call,
diff --git a/src/librustc_trans/trans/foreign.rs b/src/librustc_trans/trans/foreign.rs
index c8112e03707..25eb66ab2eb 100644
--- a/src/librustc_trans/trans/foreign.rs
+++ b/src/librustc_trans/trans/foreign.rs
@@ -43,7 +43,7 @@ use util::ppaux::Repr;
 
 struct ForeignTypes<'tcx> {
     /// Rust signature of the function
-    fn_sig: ty::PolyFnSig<'tcx>,
+    fn_sig: ty::FnSig<'tcx>,
 
     /// Adapter object for handling native ABI rules (trust me, you
     /// don't want to know)
@@ -180,7 +180,7 @@ pub fn register_foreign_item_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 
     // Make sure the calling convention is right for variadic functions
     // (should've been caught if not in typeck)
-    if tys.fn_sig.0.variadic {
+    if tys.fn_sig.variadic {
         assert!(cc == llvm::CCallConv);
     }
 
@@ -218,7 +218,8 @@ pub fn trans_native_call<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                                      llretptr: ValueRef,
                                      llargs_rust: &[ValueRef],
                                      passed_arg_tys: Vec<Ty<'tcx>>)
-                                     -> Block<'blk, 'tcx> {
+                                     -> Block<'blk, 'tcx>
+{
     let ccx = bcx.ccx();
     let tcx = bcx.tcx();
 
@@ -230,9 +231,10 @@ pub fn trans_native_call<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
            ccx.tn().val_to_string(llretptr));
 
     let (fn_abi, fn_sig) = match callee_ty.sty {
-        ty::ty_bare_fn(_, ref fn_ty) => (fn_ty.abi, fn_ty.sig.clone()),
+        ty::ty_bare_fn(_, ref fn_ty) => (fn_ty.abi, &fn_ty.sig),
         _ => ccx.sess().bug("trans_native_call called on non-function type")
     };
+    let fn_sig = ty::erase_late_bound_regions(ccx.tcx(), fn_sig);
     let llsig = foreign_signature(ccx, &fn_sig, passed_arg_tys.index(&FullRange));
     let fn_type = cabi::compute_abi_info(ccx,
                                          llsig.llarg_tys.index(&FullRange),
@@ -387,7 +389,7 @@ pub fn trans_native_call<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
         debug!("llforeign_ret_ty={}", ccx.tn().type_to_string(llforeign_ret_ty));
 
         if llrust_ret_ty == llforeign_ret_ty {
-            match fn_sig.0.output {
+            match fn_sig.output {
                 ty::FnConverging(result_ty) => {
                     base::store_ty(bcx, llforeign_retval, llretptr, result_ty)
                 }
@@ -635,7 +637,7 @@ pub fn trans_rust_fn_with_foreign_abi<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
         };
 
         // Push Rust return pointer, using null if it will be unused.
-        let rust_uses_outptr = match tys.fn_sig.0.output {
+        let rust_uses_outptr = match tys.fn_sig.output {
             ty::FnConverging(ret_ty) => type_of::return_uses_outptr(ccx, ret_ty),
             ty::FnDiverging => false
         };
@@ -668,7 +670,7 @@ pub fn trans_rust_fn_with_foreign_abi<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                             return_ty={}",
                            ccx.tn().val_to_string(slot),
                            ccx.tn().type_to_string(llrust_ret_ty),
-                           tys.fn_sig.0.output.repr(tcx));
+                           tys.fn_sig.output.repr(tcx));
                     llrust_args.push(slot);
                     return_alloca = Some(slot);
                 }
@@ -683,8 +685,8 @@ pub fn trans_rust_fn_with_foreign_abi<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
         // Build up the arguments to the call to the rust function.
         // Careful to adapt for cases where the native convention uses
         // a pointer and Rust does not or vice versa.
-        for i in range(0, tys.fn_sig.0.inputs.len()) {
-            let rust_ty = tys.fn_sig.0.inputs[i];
+        for i in range(0, tys.fn_sig.inputs.len()) {
+            let rust_ty = tys.fn_sig.inputs[i];
             let llrust_ty = tys.llsig.llarg_tys[i];
             let rust_indirect = type_of::arg_is_indirect(ccx, rust_ty);
             let llforeign_arg_ty = tys.fn_ty.arg_tys[i];
@@ -829,10 +831,11 @@ pub fn link_name(i: &ast::ForeignItem) -> InternedString {
 /// because foreign functions just plain ignore modes. They also don't pass aggregate values by
 /// pointer like we do.
 fn foreign_signature<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
-                               fn_sig: &ty::PolyFnSig<'tcx>, arg_tys: &[Ty<'tcx>])
+                               fn_sig: &ty::FnSig<'tcx>,
+                               arg_tys: &[Ty<'tcx>])
                                -> LlvmSignature {
     let llarg_tys = arg_tys.iter().map(|&arg| arg_type_of(ccx, arg)).collect();
-    let (llret_ty, ret_def) = match fn_sig.0.output {
+    let (llret_ty, ret_def) = match fn_sig.output {
         ty::FnConverging(ret_ty) =>
             (type_of::arg_type_of(ccx, ret_ty), !return_type_is_void(ccx, ret_ty)),
         ty::FnDiverging =>
@@ -853,10 +856,11 @@ fn foreign_types_for_id<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 fn foreign_types_for_fn_ty<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                                      ty: Ty<'tcx>) -> ForeignTypes<'tcx> {
     let fn_sig = match ty.sty {
-        ty::ty_bare_fn(_, ref fn_ty) => fn_ty.sig.clone(),
+        ty::ty_bare_fn(_, ref fn_ty) => &fn_ty.sig,
         _ => ccx.sess().bug("foreign_types_for_fn_ty called on non-function type")
     };
-    let llsig = foreign_signature(ccx, &fn_sig, fn_sig.0.inputs.as_slice());
+    let fn_sig = ty::erase_late_bound_regions(ccx.tcx(), fn_sig);
+    let llsig = foreign_signature(ccx, &fn_sig, fn_sig.inputs.as_slice());
     let fn_ty = cabi::compute_abi_info(ccx,
                                        llsig.llarg_tys.index(&FullRange),
                                        llsig.llret_ty,
@@ -916,7 +920,7 @@ fn lltype_for_fn_from_foreign_types(ccx: &CrateContext, tys: &ForeignTypes) -> T
         llargument_tys.push(llarg_ty);
     }
 
-    if tys.fn_sig.0.variadic {
+    if tys.fn_sig.variadic {
         Type::variadic_func(llargument_tys.as_slice(), &llreturn_ty)
     } else {
         Type::func(llargument_tys.index(&FullRange), &llreturn_ty)
diff --git a/src/librustc_trans/trans/glue.rs b/src/librustc_trans/trans/glue.rs
index 056842657ad..52e7a986d7e 100644
--- a/src/librustc_trans/trans/glue.rs
+++ b/src/librustc_trans/trans/glue.rs
@@ -212,7 +212,8 @@ fn trans_struct_drop<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                                  dtor_did: ast::DefId,
                                  class_did: ast::DefId,
                                  substs: &subst::Substs<'tcx>)
-                                 -> Block<'blk, 'tcx> {
+                                 -> Block<'blk, 'tcx>
+{
     let repr = adt::represent_type(bcx.ccx(), t);
 
     // Find and call the actual destructor
@@ -228,8 +229,9 @@ fn trans_struct_drop<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
     let fty = ty::lookup_item_type(bcx.tcx(), dtor_did).ty.subst(bcx.tcx(), substs);
     let self_ty = match fty.sty {
         ty::ty_bare_fn(_, ref f) => {
-            assert!(f.sig.0.inputs.len() == 1);
-            f.sig.0.inputs[0]
+            let sig = ty::erase_late_bound_regions(bcx.tcx(), &f.sig);
+            assert!(sig.inputs.len() == 1);
+            sig.inputs[0]
         }
         _ => bcx.sess().bug(format!("Expected function type, found {}",
                                     bcx.ty_to_string(fty)).index(&FullRange))
diff --git a/src/librustc_trans/trans/intrinsic.rs b/src/librustc_trans/trans/intrinsic.rs
index 6e716538911..ed75445b993 100644
--- a/src/librustc_trans/trans/intrinsic.rs
+++ b/src/librustc_trans/trans/intrinsic.rs
@@ -150,14 +150,16 @@ pub fn trans_intrinsic_call<'a, 'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>,
                                             dest: expr::Dest,
                                             substs: subst::Substs<'tcx>,
                                             call_info: NodeInfo)
-                                            -> Result<'blk, 'tcx> {
-
+                                            -> Result<'blk, 'tcx>
+{
     let fcx = bcx.fcx;
     let ccx = fcx.ccx;
     let tcx = bcx.tcx();
 
     let ret_ty = match callee_ty.sty {
-        ty::ty_bare_fn(_, ref f) => f.sig.0.output,
+        ty::ty_bare_fn(_, ref f) => {
+            ty::erase_late_bound_regions(bcx.tcx(), &f.sig.output())
+        }
         _ => panic!("expected bare_fn in trans_intrinsic_call")
     };
     let foreign_item = tcx.map.expect_foreign_item(node);
diff --git a/src/librustc_trans/trans/meth.rs b/src/librustc_trans/trans/meth.rs
index 1dcdad302d3..c618889f3f5 100644
--- a/src/librustc_trans/trans/meth.rs
+++ b/src/librustc_trans/trans/meth.rs
@@ -477,13 +477,19 @@ pub fn trans_trait_callee_from_llval<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 
     // 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 => {
+            let fake_sig =
+                ty::Binder(ty::FnSig {
+                    inputs: f.sig.0.inputs.slice_from(1).to_vec(),
+                    output: f.sig.0.output,
+                    variadic: f.sig.0.variadic,
+                });
             type_of_rust_fn(ccx,
                             Some(Type::i8p(ccx)),
-                            f.sig.0.inputs.slice_from(1),
-                            f.sig.0.output,
+                            &fake_sig,
                             f.abi)
         }
         _ => {
@@ -557,7 +563,8 @@ pub fn trans_object_shim<'a, 'tcx>(
 
     // Upcast to the trait in question and extract out the substitutions.
     let upcast_trait_ref = traits::upcast(ccx.tcx(), object_trait_ref.clone(), trait_id).unwrap();
-    let object_substs = upcast_trait_ref.substs().clone().erase_regions();
+    let upcast_trait_ref = ty::erase_late_bound_regions(tcx, &upcast_trait_ref);
+    let object_substs = upcast_trait_ref.substs.clone().erase_regions();
     debug!("trans_object_shim: object_substs={}", object_substs.repr(tcx));
 
     // Lookup the type of this method as deeclared in the trait and apply substitutions.
@@ -579,6 +586,8 @@ pub fn trans_object_shim<'a, 'tcx>(
     let llfn =
         decl_internal_rust_fn(ccx, method_bare_fn_ty, function_name.as_slice());
 
+    let sig = ty::erase_late_bound_regions(ccx.tcx(), &fty.sig);
+
     //
     let block_arena = TypedArena::new();
     let empty_substs = Substs::trans_empty();
@@ -586,11 +595,11 @@ pub fn trans_object_shim<'a, 'tcx>(
                           llfn,
                           ast::DUMMY_NODE_ID,
                           false,
-                          fty.sig.0.output,
+                          sig.output,
                           &empty_substs,
                           None,
                           &block_arena);
-    let mut bcx = init_function(&fcx, false, fty.sig.0.output);
+    let mut bcx = init_function(&fcx, false, sig.output);
 
     // the first argument (`self`) will be a trait object
     let llobject = get_param(fcx.llfn, fcx.arg_pos(0) as u32);
@@ -603,18 +612,18 @@ pub fn trans_object_shim<'a, 'tcx>(
         match fty.abi {
             RustCall => {
                 // unpack the tuple to extract the input type arguments:
-                match fty.sig.0.inputs[1].sty {
+                match sig.inputs[1].sty {
                     ty::ty_tup(ref tys) => tys.as_slice(),
                     _ => {
                         bcx.sess().bug(
                             format!("rust-call expects a tuple not {}",
-                                    fty.sig.0.inputs[1].repr(tcx)).as_slice());
+                                    sig.inputs[1].repr(tcx)).as_slice());
                     }
                 }
             }
             _ => {
                 // skip the self parameter:
-                fty.sig.0.inputs.slice_from(1)
+                sig.inputs.slice_from(1)
             }
         };
 
@@ -631,9 +640,12 @@ pub fn trans_object_shim<'a, 'tcx>(
 
     assert!(!fcx.needs_ret_allocas);
 
+    let sig =
+        ty::erase_late_bound_regions(bcx.tcx(), &fty.sig);
+
     let dest =
         fcx.llretslotptr.get().map(
-            |_| expr::SaveIn(fcx.get_ret_slot(bcx, fty.sig.0.output, "ret_slot")));
+            |_| expr::SaveIn(fcx.get_ret_slot(bcx, sig.output, "ret_slot")));
 
     let method_offset_in_vtable =
         traits::get_vtable_index_of_object_method(bcx.tcx(),
@@ -653,7 +665,7 @@ pub fn trans_object_shim<'a, 'tcx>(
                            ArgVals(llargs.as_slice()),
                            dest).bcx;
 
-    finish_fn(&fcx, bcx, fty.sig.0.output);
+    finish_fn(&fcx, bcx, sig.output);
 
     llfn
 }
diff --git a/src/librustc_trans/trans/type_of.rs b/src/librustc_trans/trans/type_of.rs
index 40cf11783ad..19d50cdd483 100644
--- a/src/librustc_trans/trans/type_of.rs
+++ b/src/librustc_trans/trans/type_of.rs
@@ -17,7 +17,7 @@ use trans::adt;
 use trans::common::*;
 use trans::foreign;
 use trans::machine;
-use middle::ty::{self, Ty};
+use middle::ty::{self, RegionEscape, Ty};
 use util::ppaux;
 use util::ppaux::Repr;
 
@@ -99,18 +99,21 @@ pub fn untuple_arguments_if_necessary<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 
 pub fn type_of_rust_fn<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
                                  llenvironment_type: Option<Type>,
-                                 inputs: &[Ty<'tcx>],
-                                 output: ty::FnOutput<'tcx>,
+                                 sig: &ty::Binder<ty::FnSig<'tcx>>,
                                  abi: abi::Abi)
-                                 -> Type {
+                                 -> Type
+{
+    let sig = ty::erase_late_bound_regions(cx.tcx(), sig);
+    assert!(!sig.variadic); // rust fns are never variadic
+
     let mut atys: Vec<Type> = Vec::new();
 
     // First, munge the inputs, if this has the `rust-call` ABI.
-    let inputs = untuple_arguments_if_necessary(cx, inputs, abi);
+    let inputs = untuple_arguments_if_necessary(cx, sig.inputs.as_slice(), abi);
 
     // Arg 0: Output pointer.
     // (if the output type is non-immediate)
-    let lloutputtype = match output {
+    let lloutputtype = match sig.output {
         ty::FnConverging(output) => {
             let use_out_pointer = return_uses_outptr(cx, output);
             let lloutputtype = arg_type_of(cx, output);
@@ -147,11 +150,7 @@ pub fn type_of_fn_from_ty<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, fty: Ty<'tcx>)
             // FIXME(#19925) once fn item types are
             // zero-sized, we'll need to do something here
             if f.abi == abi::Rust || f.abi == abi::RustCall {
-                type_of_rust_fn(cx,
-                                None,
-                                f.sig.0.inputs.as_slice(),
-                                f.sig.0.output,
-                                f.abi)
+                type_of_rust_fn(cx, None, &f.sig, f.abi)
             } else {
                 foreign::lltype_for_foreign_fn(cx, fty)
             }
@@ -279,12 +278,14 @@ pub fn type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Type {
 
     debug!("type_of {} {:?}", t.repr(cx.tcx()), t.sty);
 
+    assert!(!t.has_escaping_regions());
+
     // Replace any typedef'd types with their equivalent non-typedef
     // type. This ensures that all LLVM nominal types that contain
     // Rust types are defined as the same LLVM types.  If we don't do
     // this then, e.g. `Option<{myfield: bool}>` would be a different
     // type than `Option<myrec>`.
-    let t_norm = ty::normalize_ty(cx.tcx(), t);
+    let t_norm = normalize_ty(cx.tcx(), t);
 
     if t != t_norm {
         let llty = type_of(cx, t_norm);
diff --git a/src/librustc_typeck/check/_match.rs b/src/librustc_typeck/check/_match.rs
index 80e7e706059..8cd181c3774 100644
--- a/src/librustc_typeck/check/_match.rs
+++ b/src/librustc_typeck/check/_match.rs
@@ -505,9 +505,10 @@ pub fn check_pat_enum<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>, pat: &ast::Pat,
 
     let ctor_scheme = ty::lookup_item_type(tcx, enum_def);
     let path_scheme = if ty::is_fn_ty(ctor_scheme.ty) {
+        let fn_ret = ty::assert_no_late_bound_regions(tcx, &ty::ty_fn_ret(ctor_scheme.ty));
         ty::TypeScheme {
-            ty: ty::ty_fn_ret(ctor_scheme.ty).unwrap(),
-            ..ctor_scheme
+            ty: fn_ret.unwrap(),
+            generics: ctor_scheme.generics,
         }
     } else {
         ctor_scheme
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index c60851b9228..05906c03328 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -2317,7 +2317,9 @@ fn make_overloaded_lvalue_return_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 {
     match method {
         Some(method) => {
-            let ref_ty = ty::ty_fn_ret(method.ty);
+            let ref_ty = // invoked methods have all LB regions instantiated
+                ty::assert_no_late_bound_regions(
+                    fcx.tcx(), &ty::ty_fn_ret(method.ty));
             match method_call {
                 Some(method_call) => {
                     fcx.inh.method_map.borrow_mut().insert(method_call,
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 7974e99c521..11ad7bcb091 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -582,7 +582,9 @@ fn visit_expr(rcx: &mut Rcx, expr: &ast::Expr) {
                 Some(method) => {
                     constrain_call(rcx, expr, Some(&**base),
                                    None::<ast::Expr>.iter(), true);
-                    ty::ty_fn_ret(method.ty).unwrap()
+                    let fn_ret = // late-bound regions in overloaded method calls are instantiated
+                        ty::assert_no_late_bound_regions(rcx.tcx(), &ty::ty_fn_ret(method.ty));
+                    fn_ret.unwrap()
                 }
                 None => rcx.resolve_node_type(base.id)
             };
diff --git a/src/librustc_typeck/check/wf.rs b/src/librustc_typeck/check/wf.rs
index 329ae85082f..84823b0fd57 100644
--- a/src/librustc_typeck/check/wf.rs
+++ b/src/librustc_typeck/check/wf.rs
@@ -449,7 +449,13 @@ fn enum_variants<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
             match variant.node.kind {
                 ast::TupleVariantKind(ref args) if args.len() > 0 => {
                     let ctor_ty = ty::node_id_to_type(fcx.tcx(), variant.node.id);
-                    let arg_tys = ty::ty_fn_args(ctor_ty);
+
+                    // the regions in the argument types come from the
+                    // enum def'n, and hence will all be early bound
+                    let arg_tys =
+                        ty::assert_no_late_bound_regions(
+                            fcx.tcx(), &ty::ty_fn_args(ctor_ty));
+
                     AdtVariant {
                         fields: args.iter().enumerate().map(|(index, arg)| {
                             let arg_ty = arg_tys[index];
diff --git a/src/test/run-pass/issue-20644.rs b/src/test/run-pass/issue-20644.rs
new file mode 100644
index 00000000000..4a57ed56594
--- /dev/null
+++ b/src/test/run-pass/issue-20644.rs
@@ -0,0 +1,35 @@
+// Copyright 2014 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.
+
+// A reduced version of the rustbook ice. The problem this encountered
+// had to do with trans ignoring binders.
+
+#![feature(slicing_syntax)]
+#![feature(associated_types)]
+#![feature(macro_rules)]
+
+use std::iter;
+use std::os;
+use std::io::File;
+
+#[allow(unused)]
+pub fn parse_summary<R: Reader>(_: R, _: &Path) {
+     let path_from_root = Path::new("");
+     Path::new(iter::repeat("../")
+               .take(path_from_root.components().count() - 1)
+               .collect::<String>());
+ }
+
+fn main() {
+    let cwd = os::getcwd().unwrap();
+    let src = cwd.clone();
+    let summary = File::open(&src.join("SUMMARY.md"));
+    let _ = parse_summary(summary, &src);
+}