rustc: fix fallout from the addition of a 'tcx lifetime on tcx.

65 files changed, 742 insertions, 759 deletions

diff --git a/src/librustc/driver/pretty.rs b/src/librustc/driver/pretty.rs
index b535de69288..a3227e4dbf1 100644
--- a/src/librustc/driver/pretty.rs
+++ b/src/librustc/driver/pretty.rs
@@ -262,25 +262,25 @@ impl pprust::PpAnn for HygieneAnnotation {
 }
 
 
-struct TypedAnnotation {
-    analysis: CrateAnalysis,
+struct TypedAnnotation<'tcx> {
+    analysis: CrateAnalysis<'tcx>,
 }
 
-impl PrinterSupport for TypedAnnotation {
+impl<'tcx> PrinterSupport for TypedAnnotation<'tcx> {
     fn pp_ann<'a>(&'a self) -> &'a pprust::PpAnn { self as &pprust::PpAnn }
 }
 
-impl SessionCarrier for TypedAnnotation {
+impl<'tcx> SessionCarrier for TypedAnnotation<'tcx> {
     fn sess<'a>(&'a self) -> &'a Session { &self.analysis.ty_cx.sess }
 }
 
-impl AstMapCarrier for TypedAnnotation {
+impl<'tcx> AstMapCarrier for TypedAnnotation<'tcx> {
     fn ast_map<'a>(&'a self) -> Option<&'a ast_map::Map> {
         Some(&self.analysis.ty_cx.map)
     }
 }
 
-impl pprust::PpAnn for TypedAnnotation {
+impl<'tcx> pprust::PpAnn for TypedAnnotation<'tcx> {
     fn pre(&self,
            s: &mut pprust::State,
            node: pprust::AnnNode) -> io::IoResult<()> {
diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs
index 355cd8203c5..c3c4cf51f57 100644
--- a/src/librustc/lint/builtin.rs
+++ b/src/librustc/lint/builtin.rs
@@ -340,11 +340,11 @@ impl LintPass for TypeLimits {
 declare_lint!(CTYPES, Warn,
               "proper use of libc types in foreign modules")
 
-struct CTypesVisitor<'a> {
-    cx: &'a Context<'a>
+struct CTypesVisitor<'a, 'tcx: 'a> {
+    cx: &'a Context<'a, 'tcx>
 }
 
-impl<'a> CTypesVisitor<'a> {
+impl<'a, 'tcx> CTypesVisitor<'a, 'tcx> {
     fn check_def(&mut self, sp: Span, ty_id: ast::NodeId, path_id: ast::NodeId) {
         match self.cx.tcx.def_map.borrow().get_copy(&path_id) {
             def::DefPrimTy(ast::TyInt(ast::TyI)) => {
@@ -375,7 +375,7 @@ impl<'a> CTypesVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<()> for CTypesVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for CTypesVisitor<'a, 'tcx> {
     fn visit_ty(&mut self, ty: &ast::Ty, _: ()) {
         match ty.node {
             ast::TyPath(_, _, id) => self.check_def(ty.span, ty.id, id),
@@ -505,11 +505,11 @@ impl LintPass for HeapMemory {
 declare_lint!(RAW_POINTER_DERIVING, Warn,
               "uses of #[deriving] with raw pointers are rarely correct")
 
-struct RawPtrDerivingVisitor<'a> {
-    cx: &'a Context<'a>
+struct RawPtrDerivingVisitor<'a, 'tcx: 'a> {
+    cx: &'a Context<'a, 'tcx>
 }
 
-impl<'a> Visitor<()> for RawPtrDerivingVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for RawPtrDerivingVisitor<'a, 'tcx> {
     fn visit_ty(&mut self, ty: &ast::Ty, _: ()) {
         static MSG: &'static str = "use of `#[deriving]` with a raw pointer";
         match ty.node {
diff --git a/src/librustc/lint/context.rs b/src/librustc/lint/context.rs
index 18e44cbac37..26ed5cbfb2c 100644
--- a/src/librustc/lint/context.rs
+++ b/src/librustc/lint/context.rs
@@ -231,9 +231,9 @@ impl LintStore {
 }
 
 /// Context for lint checking.
-pub struct Context<'a> {
+pub struct Context<'a, 'tcx: 'a> {
     /// Type context we're checking in.
-    pub tcx: &'a ty::ctxt,
+    pub tcx: &'a ty::ctxt<'tcx>,
 
     /// The crate being checked.
     pub krate: &'a ast::Crate,
@@ -345,10 +345,10 @@ pub fn raw_emit_lint(sess: &Session, lint: &'static Lint,
     }
 }
 
-impl<'a> Context<'a> {
-    fn new(tcx: &'a ty::ctxt,
+impl<'a, 'tcx> Context<'a, 'tcx> {
+    fn new(tcx: &'a ty::ctxt<'tcx>,
            krate: &'a ast::Crate,
-           exported_items: &'a ExportedItems) -> Context<'a> {
+           exported_items: &'a ExportedItems) -> Context<'a, 'tcx> {
         // We want to own the lint store, so move it out of the session.
         let lint_store = mem::replace(&mut *tcx.sess.lint_store.borrow_mut(),
                                       LintStore::new());
@@ -476,8 +476,8 @@ impl<'a> Context<'a> {
     }
 }
 
-impl<'a> AstConv for Context<'a>{
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.tcx }
+impl<'a, 'tcx> AstConv<'tcx> for Context<'a, 'tcx>{
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 
     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
         ty::lookup_item_type(self.tcx, id)
@@ -492,7 +492,7 @@ impl<'a> AstConv for Context<'a>{
     }
 }
 
-impl<'a> Visitor<()> for Context<'a> {
+impl<'a, 'tcx> Visitor<()> for Context<'a, 'tcx> {
     fn visit_item(&mut self, it: &ast::Item, _: ()) {
         self.with_lint_attrs(it.attrs.as_slice(), |cx| {
             run_lints!(cx, check_item, it);
@@ -663,7 +663,7 @@ impl<'a> Visitor<()> for Context<'a> {
 }
 
 // Output any lints that were previously added to the session.
-impl<'a> IdVisitingOperation for Context<'a> {
+impl<'a, 'tcx> IdVisitingOperation for Context<'a, 'tcx> {
     fn visit_id(&self, id: ast::NodeId) {
         match self.tcx.sess.lints.borrow_mut().pop(&id) {
             None => {}
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index da73f25b6d1..a105a56a09b 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -71,9 +71,9 @@ pub type EncodeInlinedItem<'a> = |ecx: &EncodeContext,
                                   rbml_w: &mut Encoder,
                                   ii: InlinedItemRef|: 'a;
 
-pub struct EncodeParams<'a> {
+pub struct EncodeParams<'a, 'tcx: 'a> {
     pub diag: &'a SpanHandler,
-    pub tcx: &'a ty::ctxt,
+    pub tcx: &'a ty::ctxt<'tcx>,
     pub reexports2: &'a middle::resolve::ExportMap2,
     pub item_symbols: &'a RefCell<NodeMap<String>>,
     pub non_inlineable_statics: &'a RefCell<NodeSet>,
@@ -83,9 +83,9 @@ pub struct EncodeParams<'a> {
     pub reachable: &'a NodeSet,
 }
 
-pub struct EncodeContext<'a> {
+pub struct EncodeContext<'a, 'tcx: 'a> {
     pub diag: &'a SpanHandler,
-    pub tcx: &'a ty::ctxt,
+    pub tcx: &'a ty::ctxt<'tcx>,
     pub reexports2: &'a middle::resolve::ExportMap2,
     pub item_symbols: &'a RefCell<NodeMap<String>>,
     pub non_inlineable_statics: &'a RefCell<NodeSet>,
@@ -1793,12 +1793,12 @@ fn encode_struct_field_attrs(rbml_w: &mut Encoder, krate: &Crate) {
 
 
 
-struct ImplVisitor<'a,'b:'a,'c:'a> {
-    ecx: &'a EncodeContext<'b>,
+struct ImplVisitor<'a, 'b:'a, 'c:'a, 'tcx:'b> {
+    ecx: &'a EncodeContext<'b, 'tcx>,
     rbml_w: &'a mut Encoder<'c>,
 }
 
-impl<'a,'b,'c> Visitor<()> for ImplVisitor<'a,'b,'c> {
+impl<'a, 'b, 'c, 'tcx> Visitor<()> for ImplVisitor<'a, 'b, 'c, 'tcx> {
     fn visit_item(&mut self, item: &Item, _: ()) {
         match item.node {
             ItemImpl(_, Some(ref trait_ref), _, _) => {
diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index c18d2a7ebf4..53203663bb1 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -59,11 +59,11 @@ pub enum DefIdSource {
 pub type conv_did<'a> =
     |source: DefIdSource, ast::DefId|: 'a -> ast::DefId;
 
-pub struct PState<'a> {
+pub struct PState<'a, 'tcx: 'a> {
     data: &'a [u8],
     krate: ast::CrateNum,
     pos: uint,
-    tcx: &'a ty::ctxt
+    tcx: &'a ty::ctxt<'tcx>
 }
 
 fn peek(st: &PState) -> char {
@@ -105,8 +105,9 @@ fn parse_ident_(st: &mut PState, is_last: |char| -> bool) -> ast::Ident {
     })
 }
 
-pub fn parse_state_from_data<'a>(data: &'a [u8], crate_num: ast::CrateNum,
-                             pos: uint, tcx: &'a ty::ctxt) -> PState<'a> {
+pub fn parse_state_from_data<'a, 'tcx>(data: &'a [u8], crate_num: ast::CrateNum,
+                                       pos: uint, tcx: &'a ty::ctxt<'tcx>)
+                                       -> PState<'a, 'tcx> {
     PState {
         data: data,
         krate: crate_num,
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 09be5094dc5..cbf558b6b48 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -31,12 +31,12 @@ use rbml::io::SeekableMemWriter;
 
 macro_rules! mywrite( ($($arg:tt)*) => ({ write!($($arg)*); }) )
 
-pub struct ctxt<'a> {
+pub struct ctxt<'a, 'tcx: 'a> {
     pub diag: &'a SpanHandler,
     // Def -> str Callback:
     pub ds: fn(DefId) -> String,
     // The type context.
-    pub tcx: &'a ty::ctxt,
+    pub tcx: &'a ty::ctxt<'tcx>,
     pub abbrevs: &'a abbrev_map
 }
 
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index ee964c729fc..0e64be3d0b7 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -54,13 +54,13 @@ use serialize::{EncoderHelpers};
 #[cfg(test)] use syntax::print::pprust;
 #[cfg(test)] use std::gc::Gc;
 
-struct DecodeContext<'a> {
+struct DecodeContext<'a, 'tcx: 'a> {
     cdata: &'a cstore::crate_metadata,
-    tcx: &'a ty::ctxt,
+    tcx: &'a ty::ctxt<'tcx>,
 }
 
-struct ExtendedDecodeContext<'a> {
-    dcx: &'a DecodeContext<'a>,
+struct ExtendedDecodeContext<'a, 'tcx: 'a> {
+    dcx: &'a DecodeContext<'a, 'tcx>,
     from_id_range: ast_util::IdRange,
     to_id_range: ast_util::IdRange
 }
@@ -176,7 +176,7 @@ fn reserve_id_range(sess: &Session,
     ast_util::IdRange { min: to_id_min, max: to_id_max }
 }
 
-impl<'a> ExtendedDecodeContext<'a> {
+impl<'a, 'tcx> ExtendedDecodeContext<'a, 'tcx> {
     pub fn tr_id(&self, id: ast::NodeId) -> ast::NodeId {
         /*!
          * Translates an internal id, meaning a node id that is known
@@ -382,11 +382,11 @@ fn decode_ast(par_doc: rbml::Doc) -> ast::InlinedItem {
     Decodable::decode(&mut d).unwrap()
 }
 
-struct AstRenumberer<'a> {
-    xcx: &'a ExtendedDecodeContext<'a>,
+struct AstRenumberer<'a, 'tcx: 'a> {
+    xcx: &'a ExtendedDecodeContext<'a, 'tcx>,
 }
 
-impl<'a> ast_map::FoldOps for AstRenumberer<'a> {
+impl<'a, 'tcx> ast_map::FoldOps for AstRenumberer<'a, 'tcx> {
     fn new_id(&self, id: ast::NodeId) -> ast::NodeId {
         if id == ast::DUMMY_NODE_ID {
             // Used by ast_map to map the NodeInlinedParent.
@@ -914,12 +914,12 @@ fn encode_vec_per_param_space<T>(rbml_w: &mut Encoder,
 // ______________________________________________________________________
 // Encoding and decoding the side tables
 
-trait get_ty_str_ctxt {
-    fn ty_str_ctxt<'a>(&'a self) -> tyencode::ctxt<'a>;
+trait get_ty_str_ctxt<'tcx> {
+    fn ty_str_ctxt<'a>(&'a self) -> tyencode::ctxt<'a, 'tcx>;
 }
 
-impl<'a> get_ty_str_ctxt for e::EncodeContext<'a> {
-    fn ty_str_ctxt<'a>(&'a self) -> tyencode::ctxt<'a> {
+impl<'a, 'tcx> get_ty_str_ctxt<'tcx> for e::EncodeContext<'a, 'tcx> {
+    fn ty_str_ctxt<'a>(&'a self) -> tyencode::ctxt<'a, 'tcx> {
         tyencode::ctxt {
             diag: self.tcx.sess.diagnostic(),
             ds: e::def_to_string,
diff --git a/src/librustc/middle/borrowck/check_loans.rs b/src/librustc/middle/borrowck/check_loans.rs
index a69fe6958e1..df637e7a052 100644
--- a/src/librustc/middle/borrowck/check_loans.rs
+++ b/src/librustc/middle/borrowck/check_loans.rs
@@ -79,14 +79,14 @@ fn owned_ptr_base_path_rc(loan_path: &Rc<LoanPath>) -> Rc<LoanPath> {
     }
 }
 
-struct CheckLoanCtxt<'a> {
-    bccx: &'a BorrowckCtxt<'a>,
-    dfcx_loans: &'a LoanDataFlow<'a>,
-    move_data: move_data::FlowedMoveData<'a>,
+struct CheckLoanCtxt<'a, 'tcx: 'a> {
+    bccx: &'a BorrowckCtxt<'a, 'tcx>,
+    dfcx_loans: &'a LoanDataFlow<'a, 'tcx>,
+    move_data: move_data::FlowedMoveData<'a, 'tcx>,
     all_loans: &'a [Loan],
 }
 
-impl<'a> euv::Delegate for CheckLoanCtxt<'a> {
+impl<'a, 'tcx> euv::Delegate for CheckLoanCtxt<'a, 'tcx> {
     fn consume(&mut self,
                consume_id: ast::NodeId,
                consume_span: Span,
@@ -179,12 +179,12 @@ impl<'a> euv::Delegate for CheckLoanCtxt<'a> {
     fn decl_without_init(&mut self, _id: ast::NodeId, _span: Span) { }
 }
 
-pub fn check_loans(bccx: &BorrowckCtxt,
-                   dfcx_loans: &LoanDataFlow,
-                   move_data: move_data::FlowedMoveData,
-                   all_loans: &[Loan],
-                   decl: &ast::FnDecl,
-                   body: &ast::Block) {
+pub fn check_loans<'a, 'b, 'c, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
+                                     dfcx_loans: &LoanDataFlow<'b, 'tcx>,
+                                     move_data: move_data::FlowedMoveData<'c, 'tcx>,
+                                     all_loans: &[Loan],
+                                     decl: &ast::FnDecl,
+                                     body: &ast::Block) {
     debug!("check_loans(body id={:?})", body.id);
 
     let mut clcx = CheckLoanCtxt {
@@ -212,8 +212,8 @@ fn compatible_borrow_kinds(borrow_kind1: ty::BorrowKind,
     borrow_kind1 == ty::ImmBorrow && borrow_kind2 == ty::ImmBorrow
 }
 
-impl<'a> CheckLoanCtxt<'a> {
-    pub fn tcx(&self) -> &'a ty::ctxt { self.bccx.tcx }
+impl<'a, 'tcx> CheckLoanCtxt<'a, 'tcx> {
+    pub fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.bccx.tcx }
 
     pub fn each_issued_loan(&self, scope_id: ast::NodeId, op: |&Loan| -> bool)
                             -> bool {
diff --git a/src/librustc/middle/borrowck/gather_loans/lifetime.rs b/src/librustc/middle/borrowck/gather_loans/lifetime.rs
index c6fbbed1f8a..e13717e5abd 100644
--- a/src/librustc/middle/borrowck/gather_loans/lifetime.rs
+++ b/src/librustc/middle/borrowck/gather_loans/lifetime.rs
@@ -45,8 +45,8 @@ pub fn guarantee_lifetime(bccx: &BorrowckCtxt,
 ///////////////////////////////////////////////////////////////////////////
 // Private
 
-struct GuaranteeLifetimeContext<'a> {
-    bccx: &'a BorrowckCtxt<'a>,
+struct GuaranteeLifetimeContext<'a, 'tcx: 'a> {
+    bccx: &'a BorrowckCtxt<'a, 'tcx>,
 
     // the node id of the function body for the enclosing item
     item_scope_id: ast::NodeId,
@@ -57,7 +57,7 @@ struct GuaranteeLifetimeContext<'a> {
     cmt_original: mc::cmt
 }
 
-impl<'a> GuaranteeLifetimeContext<'a> {
+impl<'a, 'tcx> GuaranteeLifetimeContext<'a, 'tcx> {
 
     fn check(&self, cmt: &mc::cmt, discr_scope: Option<ast::NodeId>) -> R {
         //! Main routine. Walks down `cmt` until we find the "guarantor".
diff --git a/src/librustc/middle/borrowck/gather_loans/mod.rs b/src/librustc/middle/borrowck/gather_loans/mod.rs
index 82e1748465f..11189390df5 100644
--- a/src/librustc/middle/borrowck/gather_loans/mod.rs
+++ b/src/librustc/middle/borrowck/gather_loans/mod.rs
@@ -57,15 +57,15 @@ pub fn gather_loans_in_fn(bccx: &BorrowckCtxt,
     (all_loans, move_data)
 }
 
-struct GatherLoanCtxt<'a> {
-    bccx: &'a BorrowckCtxt<'a>,
+struct GatherLoanCtxt<'a, 'tcx: 'a> {
+    bccx: &'a BorrowckCtxt<'a, 'tcx>,
     move_data: move_data::MoveData,
     move_error_collector: move_error::MoveErrorCollector,
     all_loans: Vec<Loan>,
     item_ub: ast::NodeId,
 }
 
-impl<'a> euv::Delegate for GatherLoanCtxt<'a> {
+impl<'a, 'tcx> euv::Delegate for GatherLoanCtxt<'a, 'tcx> {
     fn consume(&mut self,
                consume_id: ast::NodeId,
                _consume_span: Span,
@@ -204,8 +204,8 @@ fn check_aliasability(bccx: &BorrowckCtxt,
     }
 }
 
-impl<'a> GatherLoanCtxt<'a> {
-    pub fn tcx(&self) -> &'a ty::ctxt { self.bccx.tcx }
+impl<'a, 'tcx> GatherLoanCtxt<'a, 'tcx> {
+    pub fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.bccx.tcx }
 
     fn guarantee_valid(&mut self,
                        borrow_id: ast::NodeId,
@@ -467,11 +467,11 @@ impl<'a> GatherLoanCtxt<'a> {
 ///
 /// This visitor walks static initializer's expressions and makes
 /// sure the loans being taken are sound.
-struct StaticInitializerCtxt<'a> {
-    bccx: &'a BorrowckCtxt<'a>
+struct StaticInitializerCtxt<'a, 'tcx: 'a> {
+    bccx: &'a BorrowckCtxt<'a, 'tcx>
 }
 
-impl<'a> visit::Visitor<()> for StaticInitializerCtxt<'a> {
+impl<'a, 'tcx> visit::Visitor<()> for StaticInitializerCtxt<'a, 'tcx> {
     fn visit_expr(&mut self, ex: &Expr, _: ()) {
         match ex.node {
             ast::ExprAddrOf(mutbl, ref base) => {
diff --git a/src/librustc/middle/borrowck/gather_loans/restrictions.rs b/src/librustc/middle/borrowck/gather_loans/restrictions.rs
index a686084a4a2..90e17e4d79c 100644
--- a/src/librustc/middle/borrowck/gather_loans/restrictions.rs
+++ b/src/librustc/middle/borrowck/gather_loans/restrictions.rs
@@ -44,14 +44,14 @@ pub fn compute_restrictions(bccx: &BorrowckCtxt,
 ///////////////////////////////////////////////////////////////////////////
 // Private
 
-struct RestrictionsContext<'a> {
-    bccx: &'a BorrowckCtxt<'a>,
+struct RestrictionsContext<'a, 'tcx: 'a> {
+    bccx: &'a BorrowckCtxt<'a, 'tcx>,
     span: Span,
     loan_region: ty::Region,
     cause: euv::LoanCause,
 }
 
-impl<'a> RestrictionsContext<'a> {
+impl<'a, 'tcx> RestrictionsContext<'a, 'tcx> {
     fn restrict(&self,
                 cmt: mc::cmt) -> RestrictionResult {
         debug!("restrict(cmt={})", cmt.repr(self.bccx.tcx));
diff --git a/src/librustc/middle/borrowck/graphviz.rs b/src/librustc/middle/borrowck/graphviz.rs
index b19d0118728..e75378de5a5 100644
--- a/src/librustc/middle/borrowck/graphviz.rs
+++ b/src/librustc/middle/borrowck/graphviz.rs
@@ -43,14 +43,14 @@ impl Variant {
     }
 }
 
-pub struct DataflowLabeller<'a> {
+pub struct DataflowLabeller<'a, 'tcx: 'a> {
     pub inner: cfg_dot::LabelledCFG<'a>,
     pub variants: Vec<Variant>,
-    pub borrowck_ctxt: &'a BorrowckCtxt<'a>,
-    pub analysis_data: &'a borrowck::AnalysisData<'a>,
+    pub borrowck_ctxt: &'a BorrowckCtxt<'a, 'tcx>,
+    pub analysis_data: &'a borrowck::AnalysisData<'a, 'tcx>,
 }
 
-impl<'a> DataflowLabeller<'a> {
+impl<'a, 'tcx> DataflowLabeller<'a, 'tcx> {
     fn dataflow_for(&self, e: EntryOrExit, n: &Node<'a>) -> String {
         let id = n.val1().data.id;
         debug!("dataflow_for({}, id={}) {}", e, id, self.variants);
@@ -77,7 +77,7 @@ impl<'a> DataflowLabeller<'a> {
     fn build_set<O:DataFlowOperator>(&self,
                                      e: EntryOrExit,
                                      cfgidx: CFGIndex,
-                                     dfcx: &DataFlowContext<'a, O>,
+                                     dfcx: &DataFlowContext<'a, 'tcx, O>,
                                      to_lp: |uint| -> Rc<LoanPath>) -> String {
         let mut saw_some = false;
         let mut set = "{".to_string();
@@ -126,7 +126,7 @@ impl<'a> DataflowLabeller<'a> {
     }
 }
 
-impl<'a> dot::Labeller<'a, Node<'a>, Edge<'a>> for DataflowLabeller<'a> {
+impl<'a, 'tcx> dot::Labeller<'a, Node<'a>, Edge<'a>> for DataflowLabeller<'a, 'tcx> {
     fn graph_id(&'a self) -> dot::Id<'a> { self.inner.graph_id() }
     fn node_id(&'a self, n: &Node<'a>) -> dot::Id<'a> { self.inner.node_id(n) }
     fn node_label(&'a self, n: &Node<'a>) -> dot::LabelText<'a> {
@@ -140,7 +140,7 @@ impl<'a> dot::Labeller<'a, Node<'a>, Edge<'a>> for DataflowLabeller<'a> {
     fn edge_label(&'a self, e: &Edge<'a>) -> dot::LabelText<'a> { self.inner.edge_label(e) }
 }
 
-impl<'a> dot::GraphWalk<'a, Node<'a>, Edge<'a>> for DataflowLabeller<'a> {
+impl<'a, 'tcx> dot::GraphWalk<'a, Node<'a>, Edge<'a>> for DataflowLabeller<'a, 'tcx> {
     fn nodes(&self) -> dot::Nodes<'a, Node<'a>> { self.inner.nodes() }
     fn edges(&self) -> dot::Edges<'a, Edge<'a>> { self.inner.edges() }
     fn source(&self, edge: &Edge<'a>) -> Node<'a> { self.inner.source(edge) }
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index 230786924d7..f4d3678271c 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -58,9 +58,9 @@ pub mod move_data;
 #[deriving(Clone)]
 pub struct LoanDataFlowOperator;
 
-pub type LoanDataFlow<'a> = DataFlowContext<'a, LoanDataFlowOperator>;
+pub type LoanDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, LoanDataFlowOperator>;
 
-impl<'a> Visitor<()> for BorrowckCtxt<'a> {
+impl<'a, 'tcx> Visitor<()> for BorrowckCtxt<'a, 'tcx> {
     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl,
                 b: &Block, s: Span, n: NodeId, _: ()) {
         borrowck_fn(self, fk, fd, b, s, n);
@@ -120,10 +120,10 @@ fn borrowck_item(this: &mut BorrowckCtxt, item: &ast::Item) {
 }
 
 /// Collection of conclusions determined via borrow checker analyses.
-pub struct AnalysisData<'a> {
+pub struct AnalysisData<'a, 'tcx: 'a> {
     pub all_loans: Vec<Loan>,
-    pub loans: DataFlowContext<'a, LoanDataFlowOperator>,
-    pub move_data: move_data::FlowedMoveData<'a>,
+    pub loans: DataFlowContext<'a, 'tcx, LoanDataFlowOperator>,
+    pub move_data: move_data::FlowedMoveData<'a, 'tcx>,
 }
 
 fn borrowck_fn(this: &mut BorrowckCtxt,
@@ -145,13 +145,13 @@ fn borrowck_fn(this: &mut BorrowckCtxt,
     visit::walk_fn(this, fk, decl, body, sp, ());
 }
 
-fn build_borrowck_dataflow_data<'a>(this: &mut BorrowckCtxt<'a>,
-                                    fk: &FnKind,
-                                    decl: &ast::FnDecl,
-                                    cfg: &cfg::CFG,
-                                    body: &ast::Block,
-                                    sp: Span,
-                                    id: ast::NodeId) -> AnalysisData<'a> {
+fn build_borrowck_dataflow_data<'a, 'tcx>(this: &mut BorrowckCtxt<'a, 'tcx>,
+                                          fk: &FnKind,
+                                          decl: &ast::FnDecl,
+                                          cfg: &cfg::CFG,
+                                          body: &ast::Block,
+                                          sp: Span,
+                                          id: ast::NodeId) -> AnalysisData<'a, 'tcx> {
     // Check the body of fn items.
     let id_range = ast_util::compute_id_range_for_fn_body(fk, decl, body, sp, id);
     let (all_loans, move_data) =
@@ -200,9 +200,9 @@ impl<'a> FnPartsWithCFG<'a> {
 
 /// Accessor for introspective clients inspecting `AnalysisData` and
 /// the `BorrowckCtxt` itself , e.g. the flowgraph visualizer.
-pub fn build_borrowck_dataflow_data_for_fn<'a>(
-    tcx: &'a ty::ctxt,
-    input: FnPartsWithCFG<'a>) -> (BorrowckCtxt<'a>, AnalysisData<'a>) {
+pub fn build_borrowck_dataflow_data_for_fn<'a, 'tcx>(
+    tcx: &'a ty::ctxt<'tcx>,
+    input: FnPartsWithCFG<'a>) -> (BorrowckCtxt<'a, 'tcx>, AnalysisData<'a, 'tcx>) {
 
     let mut bccx = BorrowckCtxt {
         tcx: tcx,
@@ -230,8 +230,8 @@ pub fn build_borrowck_dataflow_data_for_fn<'a>(
 // ----------------------------------------------------------------------
 // Type definitions
 
-pub struct BorrowckCtxt<'a> {
-    tcx: &'a ty::ctxt,
+pub struct BorrowckCtxt<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
 
     // Statistics:
     stats: Gc<BorrowStats>,
@@ -390,7 +390,7 @@ pub enum MovedValueUseKind {
 ///////////////////////////////////////////////////////////////////////////
 // Misc
 
-impl<'a> BorrowckCtxt<'a> {
+impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
     pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
                            -> bool {
         self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
@@ -401,7 +401,7 @@ impl<'a> BorrowckCtxt<'a> {
         self.tcx.region_maps.is_subscope_of(r_sub, r_sup)
     }
 
-    pub fn mc(&self) -> mc::MemCategorizationContext<'a,ty::ctxt> {
+    pub fn mc(&self) -> mc::MemCategorizationContext<'a, ty::ctxt<'tcx>> {
         mc::MemCategorizationContext::new(self.tcx)
     }
 
diff --git a/src/librustc/middle/borrowck/move_data.rs b/src/librustc/middle/borrowck/move_data.rs
index 340056875f2..fdd16c88686 100644
--- a/src/librustc/middle/borrowck/move_data.rs
+++ b/src/librustc/middle/borrowck/move_data.rs
@@ -56,15 +56,15 @@ pub struct MoveData {
     pub assignee_ids: RefCell<HashSet<ast::NodeId>>,
 }
 
-pub struct FlowedMoveData<'a> {
+pub struct FlowedMoveData<'a, 'tcx: 'a> {
     pub move_data: MoveData,
 
-    pub dfcx_moves: MoveDataFlow<'a>,
+    pub dfcx_moves: MoveDataFlow<'a, 'tcx>,
 
     // We could (and maybe should, for efficiency) combine both move
     // and assign data flow into one, but this way it's easier to
     // distinguish the bits that correspond to moves and assignments.
-    pub dfcx_assign: AssignDataFlow<'a>
+    pub dfcx_assign: AssignDataFlow<'a, 'tcx>
 }
 
 /// Index into `MoveData.paths`, used like a pointer
@@ -154,12 +154,12 @@ pub struct Assignment {
 #[deriving(Clone)]
 pub struct MoveDataFlowOperator;
 
-pub type MoveDataFlow<'a> = DataFlowContext<'a, MoveDataFlowOperator>;
+pub type MoveDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, MoveDataFlowOperator>;
 
 #[deriving(Clone)]
 pub struct AssignDataFlowOperator;
 
-pub type AssignDataFlow<'a> = DataFlowContext<'a, AssignDataFlowOperator>;
+pub type AssignDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, AssignDataFlowOperator>;
 
 fn loan_path_is_precise(loan_path: &LoanPath) -> bool {
     match *loan_path {
@@ -531,14 +531,14 @@ impl MoveData {
     }
 }
 
-impl<'a> FlowedMoveData<'a> {
+impl<'a, 'tcx> FlowedMoveData<'a, 'tcx> {
     pub fn new(move_data: MoveData,
-               tcx: &'a ty::ctxt,
+               tcx: &'a ty::ctxt<'tcx>,
                cfg: &cfg::CFG,
                id_range: ast_util::IdRange,
                decl: &ast::FnDecl,
                body: &ast::Block)
-               -> FlowedMoveData<'a> {
+               -> FlowedMoveData<'a, 'tcx> {
         let mut dfcx_moves =
             DataFlowContext::new(tcx,
                                  "flowed_move_data_moves",
diff --git a/src/librustc/middle/cfg/construct.rs b/src/librustc/middle/cfg/construct.rs
index 776067d49a2..ec414b85818 100644
--- a/src/librustc/middle/cfg/construct.rs
+++ b/src/librustc/middle/cfg/construct.rs
@@ -19,8 +19,8 @@ use util::nodemap::NodeMap;
 
 use std::gc::Gc;
 
-struct CFGBuilder<'a> {
-    tcx: &'a ty::ctxt,
+struct CFGBuilder<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     exit_map: NodeMap<CFGIndex>,
     graph: CFGGraph,
     fn_exit: CFGIndex,
@@ -65,7 +65,7 @@ fn add_initial_dummy_node(g: &mut CFGGraph) -> CFGIndex {
     g.add_node(CFGNodeData { id: ast::DUMMY_NODE_ID })
 }
 
-impl<'a> CFGBuilder<'a> {
+impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
     fn block(&mut self, blk: &ast::Block, pred: CFGIndex) -> CFGIndex {
         let mut stmts_exit = pred;
         for stmt in blk.stmts.iter() {
diff --git a/src/librustc/middle/check_const.rs b/src/librustc/middle/check_const.rs
index 629aba8092c..3c8db8d0480 100644
--- a/src/librustc/middle/check_const.rs
+++ b/src/librustc/middle/check_const.rs
@@ -21,11 +21,11 @@ use syntax::{ast_util, ast_map};
 use syntax::visit::Visitor;
 use syntax::visit;
 
-pub struct CheckCrateVisitor<'a> {
-    tcx: &'a ty::ctxt,
+pub struct CheckCrateVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
 }
 
-impl<'a> Visitor<bool> for CheckCrateVisitor<'a> {
+impl<'a, 'tcx> Visitor<bool> for CheckCrateVisitor<'a, 'tcx> {
     fn visit_item(&mut self, i: &Item, env: bool) {
         check_item(self, i, env);
     }
diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index c2346824710..6676ea9851d 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -86,8 +86,8 @@ impl FromIterator<Vec<Gc<Pat>>> for Matrix {
     }
 }
 
-pub struct MatchCheckCtxt<'a> {
-    pub tcx: &'a ty::ctxt
+pub struct MatchCheckCtxt<'a, 'tcx: 'a> {
+    pub tcx: &'a ty::ctxt<'tcx>
 }
 
 #[deriving(Clone, PartialEq)]
@@ -119,7 +119,7 @@ enum WitnessPreference {
     LeaveOutWitness
 }
 
-impl<'a> Visitor<()> for MatchCheckCtxt<'a> {
+impl<'a, 'tcx> Visitor<()> for MatchCheckCtxt<'a, 'tcx> {
     fn visit_expr(&mut self, ex: &Expr, _: ()) {
         check_expr(self, ex);
     }
@@ -304,13 +304,13 @@ fn const_val_to_expr(value: &const_val) -> Gc<Expr> {
     }
 }
 
-pub struct StaticInliner<'a> {
-    pub tcx: &'a ty::ctxt,
+pub struct StaticInliner<'a, 'tcx: 'a> {
+    pub tcx: &'a ty::ctxt<'tcx>,
     pub failed: bool
 }
 
-impl<'a> StaticInliner<'a> {
-    pub fn new<'a>(tcx: &'a ty::ctxt) -> StaticInliner<'a> {
+impl<'a, 'tcx> StaticInliner<'a, 'tcx> {
+    pub fn new<'a>(tcx: &'a ty::ctxt<'tcx>) -> StaticInliner<'a, 'tcx> {
         StaticInliner {
             tcx: tcx,
             failed: false
@@ -318,7 +318,7 @@ impl<'a> StaticInliner<'a> {
     }
 }
 
-impl<'a> Folder for StaticInliner<'a> {
+impl<'a, 'tcx> Folder for StaticInliner<'a, 'tcx> {
     fn fold_pat(&mut self, pat: Gc<Pat>) -> Gc<Pat> {
         match pat.node {
             PatIdent(..) | PatEnum(..) => {
@@ -963,7 +963,7 @@ fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
 
 /// Ensures that a pattern guard doesn't borrow by mutable reference or
 /// assign.
-fn check_for_mutation_in_guard<'a>(cx: &'a MatchCheckCtxt<'a>, guard: &Expr) {
+fn check_for_mutation_in_guard<'a, 'tcx>(cx: &'a MatchCheckCtxt<'a, 'tcx>, guard: &Expr) {
     let mut checker = MutationChecker {
         cx: cx,
     };
@@ -971,11 +971,11 @@ fn check_for_mutation_in_guard<'a>(cx: &'a MatchCheckCtxt<'a>, guard: &Expr) {
     visitor.walk_expr(guard);
 }
 
-struct MutationChecker<'a> {
-    cx: &'a MatchCheckCtxt<'a>,
+struct MutationChecker<'a, 'tcx: 'a> {
+    cx: &'a MatchCheckCtxt<'a, 'tcx>,
 }
 
-impl<'a> Delegate for MutationChecker<'a> {
+impl<'a, 'tcx> Delegate for MutationChecker<'a, 'tcx> {
     fn consume(&mut self, _: NodeId, _: Span, _: cmt, _: ConsumeMode) {}
     fn consume_pat(&mut self, _: &Pat, _: cmt, _: ConsumeMode) {}
     fn borrow(&mut self,
@@ -1020,11 +1020,11 @@ fn check_legality_of_bindings_in_at_patterns(cx: &MatchCheckCtxt, pat: &Pat) {
     visitor.visit_pat(pat, true);
 }
 
-struct AtBindingPatternVisitor<'a,'b:'a> {
-    cx: &'a MatchCheckCtxt<'b>,
+struct AtBindingPatternVisitor<'a, 'b:'a, 'tcx:'b> {
+    cx: &'a MatchCheckCtxt<'b, 'tcx>,
 }
 
-impl<'a,'b> Visitor<bool> for AtBindingPatternVisitor<'a,'b> {
+impl<'a, 'b, 'tcx> Visitor<bool> for AtBindingPatternVisitor<'a, 'b, 'tcx> {
     fn visit_pat(&mut self, pat: &Pat, bindings_allowed: bool) {
         if !bindings_allowed && pat_is_binding(&self.cx.tcx.def_map, pat) {
             self.cx.tcx.sess.span_err(pat.span,
diff --git a/src/librustc/middle/check_rvalues.rs b/src/librustc/middle/check_rvalues.rs
index 0ac6f21dc1f..f851ddbeeac 100644
--- a/src/librustc/middle/check_rvalues.rs
+++ b/src/librustc/middle/check_rvalues.rs
@@ -26,11 +26,11 @@ pub fn check_crate(tcx: &ty::ctxt,
     visit::walk_crate(&mut rvcx, krate, ());
 }
 
-struct RvalueContext<'a> {
-    tcx: &'a ty::ctxt
+struct RvalueContext<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>
 }
 
-impl<'a> visit::Visitor<()> for RvalueContext<'a> {
+impl<'a, 'tcx> visit::Visitor<()> for RvalueContext<'a, 'tcx> {
     fn visit_fn(&mut self,
                 _: &visit::FnKind,
                 fd: &ast::FnDecl,
@@ -43,7 +43,7 @@ impl<'a> visit::Visitor<()> for RvalueContext<'a> {
     }
 }
 
-impl<'a> euv::Delegate for RvalueContext<'a> {
+impl<'a, 'tcx> euv::Delegate for RvalueContext<'a, 'tcx> {
     fn consume(&mut self,
                _: ast::NodeId,
                span: Span,
diff --git a/src/librustc/middle/check_static.rs b/src/librustc/middle/check_static.rs
index 042a5b8f60a..7b00bb4589c 100644
--- a/src/librustc/middle/check_static.rs
+++ b/src/librustc/middle/check_static.rs
@@ -52,15 +52,15 @@ fn safe_type_for_static_mut(cx: &ty::ctxt, e: &ast::Expr) -> Option<String> {
     Some(format!("mutable static items are not allowed to have {}", suffix))
 }
 
-struct CheckStaticVisitor<'a> {
-    tcx: &'a ty::ctxt,
+struct CheckStaticVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
 }
 
 pub fn check_crate(tcx: &ty::ctxt, krate: &ast::Crate) {
     visit::walk_crate(&mut CheckStaticVisitor { tcx: tcx }, krate, false)
 }
 
-impl<'a> CheckStaticVisitor<'a> {
+impl<'a, 'tcx> CheckStaticVisitor<'a, 'tcx> {
     fn report_error(&self, span: Span, result: Option<String>) -> bool {
         match result {
             None => { false }
@@ -72,7 +72,7 @@ impl<'a> CheckStaticVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<bool> for CheckStaticVisitor<'a> {
+impl<'a, 'tcx> Visitor<bool> for CheckStaticVisitor<'a, 'tcx> {
 
     fn visit_item(&mut self, i: &ast::Item, _is_const: bool) {
         debug!("visit_item(item={})", pprust::item_to_string(i));
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index 2a00724cafb..e853b5961ec 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -176,12 +176,12 @@ pub fn lookup_const_by_id(tcx: &ty::ctxt, def_id: ast::DefId)
     }
 }
 
-struct ConstEvalVisitor<'a> {
-    tcx: &'a ty::ctxt,
+struct ConstEvalVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     ccache: constness_cache,
 }
 
-impl<'a> ConstEvalVisitor<'a> {
+impl<'a, 'tcx> ConstEvalVisitor<'a, 'tcx> {
     fn classify(&mut self, e: &Expr) -> constness {
         let did = ast_util::local_def(e.id);
         match self.ccache.find(&did) {
@@ -266,7 +266,7 @@ impl<'a> ConstEvalVisitor<'a> {
 
 }
 
-impl<'a> Visitor<()> for ConstEvalVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for ConstEvalVisitor<'a, 'tcx> {
     fn visit_ty(&mut self, t: &Ty, _: ()) {
         match t.node {
             TyFixedLengthVec(_, expr) => {
@@ -365,8 +365,7 @@ pub fn eval_const_expr(tcx: &ty::ctxt, e: &Expr) -> const_val {
     }
 }
 
-pub fn eval_const_expr_partial<T: ty::ExprTyProvider>(tcx: &T, e: &Expr)
-                            -> Result<const_val, String> {
+pub fn eval_const_expr_partial(tcx: &ty::ctxt, e: &Expr) -> Result<const_val, String> {
     fn fromb(b: bool) -> Result<const_val, String> { Ok(const_int(b as i64)) }
     match e.node {
       ExprUnary(UnNeg, ref inner) => {
@@ -494,12 +493,11 @@ pub fn eval_const_expr_partial<T: ty::ExprTyProvider>(tcx: &T, e: &Expr)
         // This tends to get called w/o the type actually having been
         // populated in the ctxt, which was causing things to blow up
         // (#5900). Fall back to doing a limited lookup to get past it.
-        let ety = ty::expr_ty_opt(tcx.ty_ctxt(), e)
-                .or_else(|| astconv::ast_ty_to_prim_ty(tcx.ty_ctxt(), &**target_ty))
+        let ety = ty::expr_ty_opt(tcx, e)
+                .or_else(|| astconv::ast_ty_to_prim_ty(tcx, &**target_ty))
                 .unwrap_or_else(|| {
-                    tcx.ty_ctxt().sess.span_fatal(target_ty.span,
-                                                  "target type not found for \
-                                                   const cast")
+                    tcx.sess.span_fatal(target_ty.span,
+                                        "target type not found for const cast")
                 });
 
         let base = eval_const_expr_partial(tcx, &**base);
@@ -540,8 +538,8 @@ pub fn eval_const_expr_partial<T: ty::ExprTyProvider>(tcx: &T, e: &Expr)
         }
       }
       ExprPath(_) => {
-          match lookup_const(tcx.ty_ctxt(), e) {
-              Some(actual_e) => eval_const_expr_partial(tcx.ty_ctxt(), &*actual_e),
+          match lookup_const(tcx, e) {
+              Some(actual_e) => eval_const_expr_partial(tcx, &*actual_e),
               None => Err("non-constant path in constant expr".to_string())
           }
       }
diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs
index 097f49a1e6e..c32f8db2380 100644
--- a/src/librustc/middle/dataflow.rs
+++ b/src/librustc/middle/dataflow.rs
@@ -32,8 +32,8 @@ use util::nodemap::NodeMap;
 pub enum EntryOrExit { Entry, Exit }
 
 #[deriving(Clone)]
-pub struct DataFlowContext<'a, O> {
-    tcx: &'a ty::ctxt,
+pub struct DataFlowContext<'a, 'tcx: 'a, O> {
+    tcx: &'a ty::ctxt<'tcx>,
 
     /// a name for the analysis using this dataflow instance
     analysis_name: &'static str,
@@ -80,8 +80,8 @@ pub trait DataFlowOperator : BitwiseOperator {
     fn initial_value(&self) -> bool;
 }
 
-struct PropagationContext<'a, 'b:'a, O:'a> {
-    dfcx: &'a mut DataFlowContext<'b, O>,
+struct PropagationContext<'a, 'b: 'a, 'tcx: 'b, O: 'a> {
+    dfcx: &'a mut DataFlowContext<'b, 'tcx, O>,
     changed: bool
 }
 
@@ -92,14 +92,14 @@ fn to_cfgidx_or_die(id: ast::NodeId, index: &NodeMap<CFGIndex>) -> CFGIndex {
     })
 }
 
-impl<'a, O:DataFlowOperator> DataFlowContext<'a, O> {
+impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
     fn has_bitset_for_nodeid(&self, n: ast::NodeId) -> bool {
         assert!(n != ast::DUMMY_NODE_ID);
         self.nodeid_to_index.contains_key(&n)
     }
 }
 
-impl<'a, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, O> {
+impl<'a, 'tcx, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, 'tcx, O> {
     fn pre(&self,
            ps: &mut pprust::State,
            node: pprust::AnnNode) -> io::IoResult<()> {
@@ -182,14 +182,14 @@ fn build_nodeid_to_index(decl: Option<&ast::FnDecl>,
     }
 }
 
-impl<'a, O:DataFlowOperator> DataFlowContext<'a, O> {
-    pub fn new(tcx: &'a ty::ctxt,
+impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
+    pub fn new(tcx: &'a ty::ctxt<'tcx>,
                analysis_name: &'static str,
                decl: Option<&ast::FnDecl>,
                cfg: &cfg::CFG,
                oper: O,
                id_range: IdRange,
-               bits_per_id: uint) -> DataFlowContext<'a, O> {
+               bits_per_id: uint) -> DataFlowContext<'a, 'tcx, O> {
         let words_per_id = (bits_per_id + uint::BITS - 1) / uint::BITS;
         let num_nodes = cfg.graph.all_nodes().len();
 
@@ -427,8 +427,8 @@ impl<'a, O:DataFlowOperator> DataFlowContext<'a, O> {
     }
 }
 
-impl<'a, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, O> {
-//                          ^^^^^^^^^^^^^ only needed for pretty printing
+impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> {
+//                                ^^^^^^^^^^^^^ only needed for pretty printing
     pub fn propagate(&mut self, cfg: &cfg::CFG, blk: &ast::Block) {
         //! Performs the data flow analysis.
 
@@ -469,7 +469,7 @@ impl<'a, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, O> {
     }
 }
 
-impl<'a, 'b, O:DataFlowOperator> PropagationContext<'a, 'b, O> {
+impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> {
     fn walk_cfg(&mut self,
                 cfg: &cfg::CFG,
                 in_out: &mut [uint]) {
diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs
index 0dfdf455743..b7cddd0c23f 100644
--- a/src/librustc/middle/dead.rs
+++ b/src/librustc/middle/dead.rs
@@ -47,9 +47,9 @@ fn should_explore(tcx: &ty::ctxt, def_id: ast::DefId) -> bool {
     }
 }
 
-struct MarkSymbolVisitor<'a> {
+struct MarkSymbolVisitor<'a, 'tcx: 'a> {
     worklist: Vec<ast::NodeId>,
-    tcx: &'a ty::ctxt,
+    tcx: &'a ty::ctxt<'tcx>,
     live_symbols: Box<HashSet<ast::NodeId>>,
 }
 
@@ -58,9 +58,9 @@ struct MarkSymbolVisitorContext {
     struct_has_extern_repr: bool
 }
 
-impl<'a> MarkSymbolVisitor<'a> {
-    fn new(tcx: &'a ty::ctxt,
-           worklist: Vec<ast::NodeId>) -> MarkSymbolVisitor<'a> {
+impl<'a, 'tcx> MarkSymbolVisitor<'a, 'tcx> {
+    fn new(tcx: &'a ty::ctxt<'tcx>,
+           worklist: Vec<ast::NodeId>) -> MarkSymbolVisitor<'a, 'tcx> {
         MarkSymbolVisitor {
             worklist: worklist,
             tcx: tcx,
@@ -232,7 +232,7 @@ impl<'a> MarkSymbolVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<MarkSymbolVisitorContext> for MarkSymbolVisitor<'a> {
+impl<'a, 'tcx> Visitor<MarkSymbolVisitorContext> for MarkSymbolVisitor<'a, 'tcx> {
 
     fn visit_struct_def(&mut self, def: &ast::StructDef, _: ast::Ident, _: &ast::Generics,
                         _: ast::NodeId, ctxt: MarkSymbolVisitorContext) {
@@ -418,12 +418,12 @@ fn get_struct_ctor_id(item: &ast::Item) -> Option<ast::NodeId> {
     }
 }
 
-struct DeadVisitor<'a> {
-    tcx: &'a ty::ctxt,
+struct DeadVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     live_symbols: Box<HashSet<ast::NodeId>>,
 }
 
-impl<'a> DeadVisitor<'a> {
+impl<'a, 'tcx> DeadVisitor<'a, 'tcx> {
     fn should_warn_about_field(&mut self, node: &ast::StructField_) -> bool {
         let is_named = node.ident().is_some();
         let field_type = ty::node_id_to_type(self.tcx, node.id);
@@ -490,7 +490,7 @@ impl<'a> DeadVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<()> for DeadVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for DeadVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &ast::Item, _: ()) {
         let ctor_id = get_struct_ctor_id(item);
         if !self.symbol_is_live(item.id, ctor_id) && should_warn(item) {
diff --git a/src/librustc/middle/effect.rs b/src/librustc/middle/effect.rs
index dc4ecb35830..ec1430edcdd 100644
--- a/src/librustc/middle/effect.rs
+++ b/src/librustc/middle/effect.rs
@@ -37,14 +37,14 @@ fn type_is_unsafe_function(ty: ty::t) -> bool {
     }
 }
 
-struct EffectCheckVisitor<'a> {
-    tcx: &'a ty::ctxt,
+struct EffectCheckVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
 
     /// Whether we're in an unsafe context.
     unsafe_context: UnsafeContext,
 }
 
-impl<'a> EffectCheckVisitor<'a> {
+impl<'a, 'tcx> EffectCheckVisitor<'a, 'tcx> {
     fn require_unsafe(&mut self, span: Span, description: &str) {
         match self.unsafe_context {
             SafeContext => {
@@ -86,7 +86,7 @@ impl<'a> EffectCheckVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<()> for EffectCheckVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for EffectCheckVisitor<'a, 'tcx> {
     fn visit_fn(&mut self, fn_kind: &visit::FnKind, fn_decl: &ast::FnDecl,
                 block: &ast::Block, span: Span, _: ast::NodeId, _:()) {
 
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index a7e49edbc8e..207620b1829 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -214,7 +214,7 @@ macro_rules! return_if_err(
     )
 )
 
-impl<'d,'t,TYPER:mc::Typer> ExprUseVisitor<'d,'t,TYPER> {
+impl<'d,'t,'tcx,TYPER:mc::Typer<'tcx>> ExprUseVisitor<'d,'t,TYPER> {
     pub fn new(delegate: &'d mut Delegate,
                typer: &'t TYPER)
                -> ExprUseVisitor<'d,'t,TYPER> {
@@ -246,7 +246,7 @@ impl<'d,'t,TYPER:mc::Typer> ExprUseVisitor<'d,'t,TYPER> {
         }
     }
 
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+    fn tcx(&self) -> &'t ty::ctxt<'tcx> {
         self.typer.tcx()
     }
 
diff --git a/src/librustc/middle/freevars.rs b/src/librustc/middle/freevars.rs
index 1a2d21baa21..df5a6b6d2a1 100644
--- a/src/librustc/middle/freevars.rs
+++ b/src/librustc/middle/freevars.rs
@@ -180,7 +180,7 @@ pub fn with_freevars<T>(tcx: &ty::ctxt, fid: ast::NodeId, f: |&[freevar_entry]|
     }
 }
 
-pub fn get_capture_mode<T:Typer>(tcx: &T, closure_expr_id: ast::NodeId)
-                        -> CaptureMode {
+pub fn get_capture_mode<'tcx, T:Typer<'tcx>>(tcx: &T, closure_expr_id: ast::NodeId)
+                                             -> CaptureMode {
     tcx.capture_mode(closure_expr_id)
 }
diff --git a/src/librustc/middle/intrinsicck.rs b/src/librustc/middle/intrinsicck.rs
index be587c25574..25a8555565c 100644
--- a/src/librustc/middle/intrinsicck.rs
+++ b/src/librustc/middle/intrinsicck.rs
@@ -67,11 +67,11 @@ fn type_size_is_affected_by_type_parameters(tcx: &ty::ctxt, typ: ty::t)
     result
 }
 
-struct IntrinsicCheckingVisitor<'a> {
-    tcx: &'a ctxt,
+struct IntrinsicCheckingVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ctxt<'tcx>,
 }
 
-impl<'a> IntrinsicCheckingVisitor<'a> {
+impl<'a, 'tcx> IntrinsicCheckingVisitor<'a, 'tcx> {
     fn def_id_is_transmute(&self, def_id: DefId) -> bool {
         let intrinsic = match ty::get(ty::lookup_item_type(self.tcx, def_id).ty).sty {
             ty::ty_bare_fn(ref bfty) => bfty.abi == RustIntrinsic,
@@ -116,7 +116,7 @@ impl<'a> IntrinsicCheckingVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<()> for IntrinsicCheckingVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for IntrinsicCheckingVisitor<'a, 'tcx> {
     fn visit_expr(&mut self, expr: &ast::Expr, (): ()) {
         match expr.node {
             ast::ExprPath(..) => {
diff --git a/src/librustc/middle/kind.rs b/src/librustc/middle/kind.rs
index 99c1d65d2b5..e556c5a59c2 100644
--- a/src/librustc/middle/kind.rs
+++ b/src/librustc/middle/kind.rs
@@ -50,13 +50,13 @@ use syntax::visit;
 // primitives in the stdlib are explicitly annotated to only take sendable
 // types.
 
-pub struct Context<'a> {
-    tcx: &'a ty::ctxt,
+pub struct Context<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     struct_and_enum_bounds_checked: HashSet<ty::t>,
     parameter_environments: Vec<ParameterEnvironment>,
 }
 
-impl<'a> Visitor<()> for Context<'a> {
+impl<'a, 'tcx> Visitor<()> for Context<'a, 'tcx> {
     fn visit_expr(&mut self, ex: &Expr, _: ()) {
         check_expr(self, ex);
     }
@@ -94,11 +94,11 @@ pub fn check_crate(tcx: &ty::ctxt,
     tcx.sess.abort_if_errors();
 }
 
-struct EmptySubstsFolder<'a> {
-    tcx: &'a ty::ctxt
+struct EmptySubstsFolder<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>
 }
-impl<'a> ty_fold::TypeFolder for EmptySubstsFolder<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+impl<'a, 'tcx> ty_fold::TypeFolder<'tcx> for EmptySubstsFolder<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         self.tcx
     }
     fn fold_substs(&mut self, _: &subst::Substs) -> subst::Substs {
diff --git a/src/librustc/middle/liveness.rs b/src/librustc/middle/liveness.rs
index 6ff09916b35..26aa51b9099 100644
--- a/src/librustc/middle/liveness.rs
+++ b/src/librustc/middle/liveness.rs
@@ -179,7 +179,7 @@ fn live_node_kind_to_string(lnk: LiveNodeKind, cx: &ty::ctxt) -> String {
     }
 }
 
-impl<'a> Visitor<()> for IrMaps<'a> {
+impl<'a, 'tcx> Visitor<()> for IrMaps<'a, 'tcx> {
     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl, b: &Block, s: Span, n: NodeId, _: ()) {
         visit_fn(self, fk, fd, b, s, n);
     }
@@ -252,8 +252,8 @@ enum VarKind {
     ImplicitRet
 }
 
-struct IrMaps<'a> {
-    tcx: &'a ty::ctxt,
+struct IrMaps<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
 
     num_live_nodes: uint,
     num_vars: uint,
@@ -264,8 +264,8 @@ struct IrMaps<'a> {
     lnks: Vec<LiveNodeKind>,
 }
 
-impl<'a> IrMaps<'a> {
-    fn new(tcx: &'a ty::ctxt) -> IrMaps<'a> {
+impl<'a, 'tcx> IrMaps<'a, 'tcx> {
+    fn new(tcx: &'a ty::ctxt<'tcx>) -> IrMaps<'a, 'tcx> {
         IrMaps {
             tcx: tcx,
             num_live_nodes: 0,
@@ -343,7 +343,7 @@ impl<'a> IrMaps<'a> {
     }
 }
 
-impl<'a> Visitor<()> for Liveness<'a> {
+impl<'a, 'tcx> Visitor<()> for Liveness<'a, 'tcx> {
     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl, b: &Block, s: Span, n: NodeId, _: ()) {
         check_fn(self, fk, fd, b, s, n);
     }
@@ -555,8 +555,8 @@ static ACC_READ: uint = 1u;
 static ACC_WRITE: uint = 2u;
 static ACC_USE: uint = 4u;
 
-struct Liveness<'a> {
-    ir: &'a mut IrMaps<'a>,
+struct Liveness<'a, 'tcx: 'a> {
+    ir: &'a mut IrMaps<'a, 'tcx>,
     s: Specials,
     successors: Vec<LiveNode>,
     users: Vec<Users>,
@@ -570,8 +570,8 @@ struct Liveness<'a> {
     cont_ln: NodeMap<LiveNode>
 }
 
-impl<'a> Liveness<'a> {
-    fn new(ir: &'a mut IrMaps<'a>, specials: Specials) -> Liveness<'a> {
+impl<'a, 'tcx> Liveness<'a, 'tcx> {
+    fn new(ir: &'a mut IrMaps<'a, 'tcx>, specials: Specials) -> Liveness<'a, 'tcx> {
         let num_live_nodes = ir.num_live_nodes;
         let num_vars = ir.num_vars;
         Liveness {
@@ -607,7 +607,7 @@ impl<'a> Liveness<'a> {
 
     fn pat_bindings(&mut self,
                     pat: &Pat,
-                    f: |&mut Liveness<'a>, LiveNode, Variable, Span, NodeId|) {
+                    f: |&mut Liveness<'a, 'tcx>, LiveNode, Variable, Span, NodeId|) {
         pat_util::pat_bindings(&self.ir.tcx.def_map, pat, |_bm, p_id, sp, _n| {
             let ln = self.live_node(p_id, sp);
             let var = self.variable(p_id, sp);
@@ -617,7 +617,7 @@ impl<'a> Liveness<'a> {
 
     fn arm_pats_bindings(&mut self,
                          pats: &[Gc<Pat>],
-                         f: |&mut Liveness<'a>, LiveNode, Variable, Span, NodeId|) {
+                         f: |&mut Liveness<'a, 'tcx>, LiveNode, Variable, Span, NodeId|) {
         // only consider the first pattern; any later patterns must have
         // the same bindings, and we also consider the first pattern to be
         // the "authoritative" set of ids
@@ -683,7 +683,7 @@ impl<'a> Liveness<'a> {
     fn indices2(&mut self,
                 ln: LiveNode,
                 succ_ln: LiveNode,
-                op: |&mut Liveness<'a>, uint, uint|) {
+                op: |&mut Liveness<'a, 'tcx>, uint, uint|) {
         let node_base_idx = self.idx(ln, Variable(0u));
         let succ_base_idx = self.idx(succ_ln, Variable(0u));
         for var_idx in range(0u, self.ir.num_vars) {
@@ -1376,7 +1376,7 @@ impl<'a> Liveness<'a> {
                           loop_node_id: NodeId,
                           break_ln: LiveNode,
                           cont_ln: LiveNode,
-                          f: |&mut Liveness<'a>| -> R)
+                          f: |&mut Liveness<'a, 'tcx>| -> R)
                           -> R {
         debug!("with_loop_nodes: {} {}", loop_node_id, break_ln.get());
         self.loop_scope.push(loop_node_id);
@@ -1465,7 +1465,7 @@ fn check_fn(_v: &Liveness,
     // do not check contents of nested fns
 }
 
-impl<'a> Liveness<'a> {
+impl<'a, 'tcx> Liveness<'a, 'tcx> {
     fn check_ret(&self,
                  id: NodeId,
                  sp: Span,
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 56e501388f1..abed04c8f33 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -264,8 +264,8 @@ pub type McResult<T> = Result<T, ()>;
  * know that no errors have occurred, so we simply consult the tcx and we
  * can be sure that only `Ok` results will occur.
  */
-pub trait Typer {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt;
+pub trait Typer<'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
     fn node_ty(&self, id: ast::NodeId) -> McResult<ty::t>;
     fn node_method_ty(&self, method_call: typeck::MethodCall) -> Option<ty::t>;
     fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment>>;
@@ -375,12 +375,12 @@ macro_rules! if_ok(
     )
 )
 
-impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
+impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
     pub fn new(typer: &'t TYPER) -> MemCategorizationContext<'t,TYPER> {
         MemCategorizationContext { typer: typer }
     }
 
-    fn tcx(&self) -> &'t ty::ctxt {
+    fn tcx(&self) -> &'t ty::ctxt<'tcx> {
         self.typer.tcx()
     }
 
diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index 42d6cee9654..6017444267a 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -133,8 +133,8 @@ impl Visitor<()> for ParentVisitor {
 /// The embargo visitor, used to determine the exports of the ast
 ////////////////////////////////////////////////////////////////////////////////
 
-struct EmbargoVisitor<'a> {
-    tcx: &'a ty::ctxt,
+struct EmbargoVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     exp_map2: &'a resolve::ExportMap2,
 
     // This flag is an indicator of whether the previous item in the
@@ -163,7 +163,7 @@ struct EmbargoVisitor<'a> {
     prev_public: bool,
 }
 
-impl<'a> EmbargoVisitor<'a> {
+impl<'a, 'tcx> EmbargoVisitor<'a, 'tcx> {
     // There are checks inside of privacy which depend on knowing whether a
     // trait should be exported or not. The two current consumers of this are:
     //
@@ -180,7 +180,7 @@ impl<'a> EmbargoVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<()> for EmbargoVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for EmbargoVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &ast::Item, _: ()) {
         let orig_all_pub = self.prev_public;
         self.prev_public = orig_all_pub && item.vis == ast::Public;
@@ -355,8 +355,8 @@ impl<'a> Visitor<()> for EmbargoVisitor<'a> {
 /// The privacy visitor, where privacy checks take place (violations reported)
 ////////////////////////////////////////////////////////////////////////////////
 
-struct PrivacyVisitor<'a> {
-    tcx: &'a ty::ctxt,
+struct PrivacyVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     curitem: ast::NodeId,
     in_foreign: bool,
     parents: NodeMap<ast::NodeId>,
@@ -376,7 +376,7 @@ enum FieldName {
     NamedField(ast::Ident),
 }
 
-impl<'a> PrivacyVisitor<'a> {
+impl<'a, 'tcx> PrivacyVisitor<'a, 'tcx> {
     // used when debugging
     fn nodestr(&self, id: ast::NodeId) -> String {
         self.tcx.map.node_to_string(id).to_string()
@@ -802,7 +802,7 @@ impl<'a> PrivacyVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<()> for PrivacyVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for PrivacyVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &ast::Item, _: ()) {
         let orig_curitem = replace(&mut self.curitem, item.id);
         visit::walk_item(self, item, ());
@@ -1023,12 +1023,12 @@ impl<'a> Visitor<()> for PrivacyVisitor<'a> {
 /// The privacy sanity check visitor, ensures unnecessary visibility isn't here
 ////////////////////////////////////////////////////////////////////////////////
 
-struct SanePrivacyVisitor<'a> {
-    tcx: &'a ty::ctxt,
+struct SanePrivacyVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     in_fn: bool,
 }
 
-impl<'a> Visitor<()> for SanePrivacyVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for SanePrivacyVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &ast::Item, _: ()) {
         if self.in_fn {
             self.check_all_inherited(item);
@@ -1076,7 +1076,7 @@ impl<'a> Visitor<()> for SanePrivacyVisitor<'a> {
     }
 }
 
-impl<'a> SanePrivacyVisitor<'a> {
+impl<'a, 'tcx> SanePrivacyVisitor<'a, 'tcx> {
     /// Validates all of the visibility qualifiers placed on the item given. This
     /// ensures that there are no extraneous qualifiers that don't actually do
     /// anything. In theory these qualifiers wouldn't parse, but that may happen
@@ -1215,14 +1215,14 @@ impl<'a> SanePrivacyVisitor<'a> {
     }
 }
 
-struct VisiblePrivateTypesVisitor<'a> {
-    tcx: &'a ty::ctxt,
+struct VisiblePrivateTypesVisitor<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     exported_items: &'a ExportedItems,
     public_items: &'a PublicItems,
 }
 
-struct CheckTypeForPrivatenessVisitor<'a, 'b:'a> {
-    inner: &'a VisiblePrivateTypesVisitor<'b>,
+struct CheckTypeForPrivatenessVisitor<'a, 'b: 'a, 'tcx: 'b> {
+    inner: &'a VisiblePrivateTypesVisitor<'b, 'tcx>,
     /// whether the type refers to private types.
     contains_private: bool,
     /// whether we've recurred at all (i.e. if we're pointing at the
@@ -1232,7 +1232,7 @@ struct CheckTypeForPrivatenessVisitor<'a, 'b:'a> {
     outer_type_is_public_path: bool,
 }
 
-impl<'a> VisiblePrivateTypesVisitor<'a> {
+impl<'a, 'tcx> VisiblePrivateTypesVisitor<'a, 'tcx> {
     fn path_is_private_type(&self, path_id: ast::NodeId) -> bool {
         let did = match self.tcx.def_map.borrow().find_copy(&path_id) {
             // `int` etc. (None doesn't seem to occur.)
@@ -1256,7 +1256,7 @@ impl<'a> VisiblePrivateTypesVisitor<'a> {
     }
 }
 
-impl<'a, 'b> Visitor<()> for CheckTypeForPrivatenessVisitor<'a, 'b> {
+impl<'a, 'b, 'tcx> Visitor<()> for CheckTypeForPrivatenessVisitor<'a, 'b, 'tcx> {
     fn visit_ty(&mut self, ty: &ast::Ty, _: ()) {
         match ty.node {
             ast::TyPath(_, _, path_id) => {
@@ -1279,7 +1279,7 @@ impl<'a, 'b> Visitor<()> for CheckTypeForPrivatenessVisitor<'a, 'b> {
     fn visit_expr(&mut self, _: &ast::Expr, _: ()) {}
 }
 
-impl<'a> Visitor<()> for VisiblePrivateTypesVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for VisiblePrivateTypesVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &ast::Item, _: ()) {
         match item.node {
             // contents of a private mod can be reexported, so we need
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index 5dfc43daa64..7ba5144985e 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -89,9 +89,9 @@ fn method_might_be_inlined(tcx: &ty::ctxt, method: &ast::Method,
 }
 
 // Information needed while computing reachability.
-struct ReachableContext<'a> {
+struct ReachableContext<'a, 'tcx: 'a> {
     // The type context.
-    tcx: &'a ty::ctxt,
+    tcx: &'a ty::ctxt<'tcx>,
     // The set of items which must be exported in the linkage sense.
     reachable_symbols: NodeSet,
     // A worklist of item IDs. Each item ID in this worklist will be inlined
@@ -101,7 +101,7 @@ struct ReachableContext<'a> {
     any_library: bool,
 }
 
-impl<'a> Visitor<()> for ReachableContext<'a> {
+impl<'a, 'tcx> Visitor<()> for ReachableContext<'a, 'tcx> {
 
     fn visit_expr(&mut self, expr: &ast::Expr, _: ()) {
 
@@ -164,9 +164,9 @@ impl<'a> Visitor<()> for ReachableContext<'a> {
     }
 }
 
-impl<'a> ReachableContext<'a> {
+impl<'a, 'tcx> ReachableContext<'a, 'tcx> {
     // Creates a new reachability computation context.
-    fn new(tcx: &'a ty::ctxt) -> ReachableContext<'a> {
+    fn new(tcx: &'a ty::ctxt<'tcx>) -> ReachableContext<'a, 'tcx> {
         let any_library = tcx.sess.crate_types.borrow().iter().any(|ty| {
             *ty != config::CrateTypeExecutable
         });
diff --git a/src/librustc/middle/save/mod.rs b/src/librustc/middle/save/mod.rs
index cd3f47e8b2f..7c7960e0918 100644
--- a/src/librustc/middle/save/mod.rs
+++ b/src/librustc/middle/save/mod.rs
@@ -74,9 +74,9 @@ fn generated_code(span: Span) -> bool {
     span.expn_info.is_some() || span  == DUMMY_SP
 }
 
-struct DxrVisitor<'l> {
+struct DxrVisitor<'l, 'tcx: 'l> {
     sess: &'l Session,
-    analysis: &'l CrateAnalysis,
+    analysis: &'l CrateAnalysis<'tcx>,
 
     collected_paths: Vec<(NodeId, ast::Path, bool, recorder::Row)>,
     collecting: bool,
@@ -85,7 +85,7 @@ struct DxrVisitor<'l> {
     fmt: FmtStrs<'l>,
 }
 
-impl <'l> DxrVisitor<'l> {
+impl <'l, 'tcx> DxrVisitor<'l, 'tcx> {
     fn dump_crate_info(&mut self, name: &str, krate: &ast::Crate) {
         // the current crate
         self.fmt.crate_str(krate.span, name);
@@ -1023,7 +1023,7 @@ impl <'l> DxrVisitor<'l> {
     }
 }
 
-impl<'l> Visitor<DxrVisitorEnv> for DxrVisitor<'l> {
+impl<'l, 'tcx> Visitor<DxrVisitorEnv> for DxrVisitor<'l, 'tcx> {
     fn visit_item(&mut self, item:&ast::Item, e: DxrVisitorEnv) {
         if generated_code(item.span) {
             return
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index d992e840b46..c1c23dff984 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -548,8 +548,8 @@ impl<T:TypeFoldable> Subst for T {
 ///////////////////////////////////////////////////////////////////////////
 // The actual substitution engine itself is a type folder.
 
-struct SubstFolder<'a> {
-    tcx: &'a ty::ctxt,
+struct SubstFolder<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     substs: &'a Substs,
 
     // The location for which the substitution is performed, if available.
@@ -562,8 +562,8 @@ struct SubstFolder<'a> {
     ty_stack_depth: uint,
 }
 
-impl<'a> TypeFolder for SubstFolder<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.tcx }
+impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 
     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
         // Note: This routine only handles regions that are bound on
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index 30f50067bdd..dc1be08e444 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -137,15 +137,16 @@ pub fn push_ctxt(s: &'static str) -> _InsnCtxt {
     _InsnCtxt { _cannot_construct_outside_of_this_module: () }
 }
 
-pub struct StatRecorder<'a> {
-    ccx: &'a CrateContext<'a>,
+pub struct StatRecorder<'a, 'tcx: 'a> {
+    ccx: &'a CrateContext<'a, 'tcx>,
     name: Option<String>,
     start: u64,
     istart: uint,
 }
 
-impl<'a> StatRecorder<'a> {
-    pub fn new(ccx: &'a CrateContext, name: String) -> StatRecorder<'a> {
+impl<'a, 'tcx> StatRecorder<'a, 'tcx> {
+    pub fn new(ccx: &'a CrateContext<'a, 'tcx>, name: String)
+               -> StatRecorder<'a, 'tcx> {
         let start = if ccx.sess().trans_stats() {
             time::precise_time_ns()
         } else {
@@ -162,7 +163,7 @@ impl<'a> StatRecorder<'a> {
 }
 
 #[unsafe_destructor]
-impl<'a> Drop for StatRecorder<'a> {
+impl<'a, 'tcx> Drop for StatRecorder<'a, 'tcx> {
     fn drop(&mut self) {
         if self.ccx.sess().trans_stats() {
             let end = time::precise_time_ns();
@@ -2142,11 +2143,11 @@ fn enum_variant_size_lint(ccx: &CrateContext, enum_def: &ast::EnumDef, sp: Span,
     }
 }
 
-pub struct TransItemVisitor<'a> {
-    pub ccx: &'a CrateContext<'a>,
+pub struct TransItemVisitor<'a, 'tcx: 'a> {
+    pub ccx: &'a CrateContext<'a, 'tcx>,
 }
 
-impl<'a> Visitor<()> for TransItemVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for TransItemVisitor<'a, 'tcx> {
     fn visit_item(&mut self, i: &ast::Item, _:()) {
         trans_item(self.ccx, i);
     }
@@ -2911,20 +2912,20 @@ pub fn p2i(ccx: &CrateContext, v: ValueRef) -> ValueRef {
     }
 }
 
-pub fn crate_ctxt_to_encode_parms<'r>(cx: &'r SharedCrateContext,
-                                      ie: encoder::EncodeInlinedItem<'r>)
-    -> encoder::EncodeParams<'r> {
-        encoder::EncodeParams {
-            diag: cx.sess().diagnostic(),
-            tcx: cx.tcx(),
-            reexports2: cx.exp_map2(),
-            item_symbols: cx.item_symbols(),
-            non_inlineable_statics: cx.non_inlineable_statics(),
-            link_meta: cx.link_meta(),
-            cstore: &cx.sess().cstore,
-            encode_inlined_item: ie,
-            reachable: cx.reachable(),
-        }
+pub fn crate_ctxt_to_encode_parms<'a, 'tcx>(cx: &'a SharedCrateContext<'tcx>,
+                                            ie: encoder::EncodeInlinedItem<'a>)
+                                            -> encoder::EncodeParams<'a, 'tcx> {
+    encoder::EncodeParams {
+        diag: cx.sess().diagnostic(),
+        tcx: cx.tcx(),
+        reexports2: cx.exp_map2(),
+        item_symbols: cx.item_symbols(),
+        non_inlineable_statics: cx.non_inlineable_statics(),
+        link_meta: cx.link_meta(),
+        cstore: &cx.sess().cstore,
+        encode_inlined_item: ie,
+        reachable: cx.reachable(),
+    }
 }
 
 pub fn write_metadata(cx: &SharedCrateContext, krate: &ast::Crate) -> Vec<u8> {
diff --git a/src/librustc/middle/trans/build.rs b/src/librustc/middle/trans/build.rs
index fd988eb7fc1..95f6118908e 100644
--- a/src/librustc/middle/trans/build.rs
+++ b/src/librustc/middle/trans/build.rs
@@ -34,7 +34,7 @@ pub fn check_not_terminated(cx: &Block) {
     }
 }
 
-pub fn B<'a>(cx: &'a Block) -> Builder<'a> {
+pub fn B<'b, 'tcx>(cx: &'b Block<'b, 'tcx>) -> Builder<'b, 'tcx> {
     let b = cx.fcx.ccx.builder();
     b.position_at_end(cx.llbb);
     b
diff --git a/src/librustc/middle/trans/builder.rs b/src/librustc/middle/trans/builder.rs
index 322a6a3cc90..ca7adb97f3d 100644
--- a/src/librustc/middle/trans/builder.rs
+++ b/src/librustc/middle/trans/builder.rs
@@ -23,9 +23,9 @@ use libc::{c_uint, c_ulonglong, c_char};
 use std::string::String;
 use syntax::codemap::Span;
 
-pub struct Builder<'a> {
+pub struct Builder<'a, 'tcx: 'a> {
     pub llbuilder: BuilderRef,
-    pub ccx: &'a CrateContext<'a>,
+    pub ccx: &'a CrateContext<'a, 'tcx>,
 }
 
 // This is a really awful way to get a zero-length c-string, but better (and a
@@ -35,8 +35,8 @@ pub fn noname() -> *const c_char {
     &cnull as *const c_char
 }
 
-impl<'a> Builder<'a> {
-    pub fn new(ccx: &'a CrateContext) -> Builder<'a> {
+impl<'a, 'tcx> Builder<'a, 'tcx> {
+    pub fn new(ccx: &'a CrateContext<'a, 'tcx>) -> Builder<'a, 'tcx> {
         Builder {
             llbuilder: ccx.raw_builder(),
             ccx: ccx,
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index 4ea60a4e128..4d62386260b 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -233,7 +233,7 @@ pub type LvalueDatum = datum::Datum<datum::Lvalue>;
 
 // Function context.  Every LLVM function we create will have one of
 // these.
-pub struct FunctionContext<'a> {
+pub struct FunctionContext<'a, 'tcx: 'a> {
     // The ValueRef returned from a call to llvm::LLVMAddFunction; the
     // address of the first instruction in the sequence of
     // instructions for this function that will go in the .text
@@ -297,7 +297,7 @@ pub struct FunctionContext<'a> {
     pub block_arena: &'a TypedArena<Block<'a>>,
 
     // This function's enclosing crate context.
-    pub ccx: &'a CrateContext<'a>,
+    pub ccx: &'a CrateContext<'a, 'tcx>,
 
     // Used and maintained by the debuginfo module.
     pub debug_context: debuginfo::FunctionDebugContext,
@@ -306,7 +306,7 @@ pub struct FunctionContext<'a> {
     pub scopes: RefCell<Vec<cleanup::CleanupScope<'a>> >,
 }
 
-impl<'a> FunctionContext<'a> {
+impl<'a, 'tcx> FunctionContext<'a, 'tcx> {
     pub fn arg_pos(&self, arg: uint) -> uint {
         let arg = self.env_arg_pos() + arg;
         if self.llenv.is_some() {
@@ -410,7 +410,7 @@ impl<'a> FunctionContext<'a> {
 // code.  Each basic block we generate is attached to a function, typically
 // with many basic blocks per function.  All the basic blocks attached to a
 // function are organized as a directed graph.
-pub struct Block<'a> {
+pub struct Block<'a, 'tcx> {
     // The BasicBlockRef returned from a call to
     // llvm::LLVMAppendBasicBlock(llfn, name), which adds a basic
     // block to the function pointed to by llfn.  We insert
@@ -429,16 +429,15 @@ pub struct Block<'a> {
 
     // The function context for the function to which this block is
     // attached.
-    pub fcx: &'a FunctionContext<'a>,
+    pub fcx: &'a FunctionContext<'a, 'tcx>,
 }
 
-impl<'a> Block<'a> {
-    pub fn new<'a>(
-               llbb: BasicBlockRef,
+impl<'a, 'tcx> Block<'a, 'tcx> {
+    pub fn new(llbb: BasicBlockRef,
                is_lpad: bool,
                opt_node_id: Option<ast::NodeId>,
-               fcx: &'a FunctionContext<'a>)
-               -> &'a Block<'a> {
+               fcx: &'a FunctionContext<'a, 'tcx>)
+               -> &'a Block<'a, 'tcx> {
         fcx.block_arena.alloc(Block {
             llbb: llbb,
             terminated: Cell::new(false),
@@ -449,8 +448,8 @@ impl<'a> Block<'a> {
         })
     }
 
-    pub fn ccx(&self) -> &'a CrateContext<'a> { self.fcx.ccx }
-    pub fn tcx(&self) -> &'a ty::ctxt {
+    pub fn ccx(&self) -> &'a CrateContext<'a, 'tcx> { self.fcx.ccx }
+    pub fn tcx(&self) -> &'a ty::ctxt<'tcx> {
         self.fcx.ccx.tcx()
     }
     pub fn sess(&self) -> &'a Session { self.fcx.ccx.sess() }
@@ -495,8 +494,8 @@ impl<'a> Block<'a> {
     }
 }
 
-impl<'a> mc::Typer for Block<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+impl<'blk, 'tcx> mc::Typer<'tcx> for Block<'blk, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         self.tcx()
     }
 
@@ -535,13 +534,13 @@ impl<'a> mc::Typer for Block<'a> {
     }
 }
 
-pub struct Result<'a> {
-    pub bcx: &'a Block<'a>,
+pub struct Result<'blk, 'tcx: 'blk> {
+    pub bcx: &'blk Block<'blk, 'tcx>,
     pub val: ValueRef
 }
 
-impl<'a> Result<'a> {
-    pub fn new(bcx: &'a Block<'a>, val: ValueRef) -> Result<'a> {
+impl<'b, 'tcx> Result<'b, 'tcx> {
+    pub fn new(bcx: &'b Block<'b, 'tcx>, val: ValueRef) -> Result<'b, 'tcx> {
         Result {
             bcx: bcx,
             val: val,
@@ -746,11 +745,11 @@ pub fn is_null(val: ValueRef) -> bool {
     }
 }
 
-pub fn monomorphize_type(bcx: &Block, t: ty::t) -> ty::t {
+pub fn monomorphize_type(bcx: Block, t: ty::t) -> ty::t {
     t.subst(bcx.tcx(), &bcx.fcx.param_substs.substs)
 }
 
-pub fn node_id_type(bcx: &Block, id: ast::NodeId) -> ty::t {
+pub fn node_id_type(bcx: Block, id: ast::NodeId) -> ty::t {
     let tcx = bcx.tcx();
     let t = ty::node_id_to_type(tcx, id);
     monomorphize_type(bcx, t)
diff --git a/src/librustc/middle/trans/context.rs b/src/librustc/middle/trans/context.rs
index 5bdd5f6739d..3b4b50c7e85 100644
--- a/src/librustc/middle/trans/context.rs
+++ b/src/librustc/middle/trans/context.rs
@@ -55,7 +55,7 @@ pub struct Stats {
 /// per crate.  The data here is shared between all compilation units of the
 /// crate, so it must not contain references to any LLVM data structures
 /// (aside from metadata-related ones).
-pub struct SharedCrateContext {
+pub struct SharedCrateContext<'tcx> {
     local_ccxs: Vec<LocalCrateContext>,
 
     metadata_llmod: ModuleRef,
@@ -70,7 +70,7 @@ pub struct SharedCrateContext {
     /// that is generated
     non_inlineable_statics: RefCell<NodeSet>,
     symbol_hasher: RefCell<Sha256>,
-    tcx: ty::ctxt,
+    tcx: ty::ctxt<'tcx>,
     stats: Stats,
 
     available_monomorphizations: RefCell<HashSet<String>>,
@@ -152,21 +152,21 @@ pub struct LocalCrateContext {
     n_llvm_insns: Cell<uint>,
 }
 
-pub struct CrateContext<'a> {
-    shared: &'a SharedCrateContext,
+pub struct CrateContext<'a, 'tcx: 'a> {
+    shared: &'a SharedCrateContext<'tcx>,
     local: &'a LocalCrateContext,
     /// The index of `local` in `shared.local_ccxs`.  This is used in
     /// `maybe_iter(true)` to identify the original `LocalCrateContext`.
     index: uint,
 }
 
-pub struct CrateContextIterator<'a> {
-    shared: &'a SharedCrateContext,
+pub struct CrateContextIterator<'a, 'tcx: 'a> {
+    shared: &'a SharedCrateContext<'tcx>,
     index: uint,
 }
 
-impl<'a> Iterator<CrateContext<'a>> for CrateContextIterator<'a> {
-    fn next(&mut self) -> Option<CrateContext<'a>> {
+impl<'a, 'tcx> Iterator<CrateContext<'a, 'tcx>> for CrateContextIterator<'a,'tcx> {
+    fn next(&mut self) -> Option<CrateContext<'a, 'tcx>> {
         if self.index >= self.shared.local_ccxs.len() {
             return None;
         }
@@ -183,15 +183,15 @@ impl<'a> Iterator<CrateContext<'a>> for CrateContextIterator<'a> {
 }
 
 /// The iterator produced by `CrateContext::maybe_iter`.
-pub struct CrateContextMaybeIterator<'a> {
-    shared: &'a SharedCrateContext,
+pub struct CrateContextMaybeIterator<'a, 'tcx: 'a> {
+    shared: &'a SharedCrateContext<'tcx>,
     index: uint,
     single: bool,
     origin: uint,
 }
 
-impl<'a> Iterator<(CrateContext<'a>, bool)> for CrateContextMaybeIterator<'a> {
-    fn next(&mut self) -> Option<(CrateContext<'a>, bool)> {
+impl<'a, 'tcx> Iterator<(CrateContext<'a, 'tcx>, bool)> for CrateContextMaybeIterator<'a, 'tcx> {
+    fn next(&mut self) -> Option<(CrateContext<'a, 'tcx>, bool)> {
         if self.index >= self.shared.local_ccxs.len() {
             return None;
         }
@@ -234,15 +234,15 @@ unsafe fn create_context_and_module(sess: &Session, mod_name: &str) -> (ContextR
     (llcx, llmod)
 }
 
-impl SharedCrateContext {
+impl<'tcx> SharedCrateContext<'tcx> {
     pub fn new(crate_name: &str,
                local_count: uint,
-               tcx: ty::ctxt,
+               tcx: ty::ctxt<'tcx>,
                emap2: resolve::ExportMap2,
                symbol_hasher: Sha256,
                link_meta: LinkMeta,
                reachable: NodeSet)
-               -> SharedCrateContext {
+               -> SharedCrateContext<'tcx> {
         let (metadata_llcx, metadata_llmod) = unsafe {
             create_context_and_module(&tcx.sess, "metadata")
         };
@@ -293,14 +293,14 @@ impl SharedCrateContext {
         shared_ccx
     }
 
-    pub fn iter<'a>(&'a self) -> CrateContextIterator<'a> {
+    pub fn iter<'a>(&'a self) -> CrateContextIterator<'a, 'tcx> {
         CrateContextIterator {
             shared: self,
             index: 0,
         }
     }
 
-    pub fn get_ccx<'a>(&'a self, index: uint) -> CrateContext<'a> {
+    pub fn get_ccx<'a>(&'a self, index: uint) -> CrateContext<'a, 'tcx> {
         CrateContext {
             shared: self,
             local: &self.local_ccxs[index],
@@ -308,7 +308,7 @@ impl SharedCrateContext {
         }
     }
 
-    fn get_smallest_ccx<'a>(&'a self) -> CrateContext<'a> {
+    fn get_smallest_ccx<'a>(&'a self) -> CrateContext<'a, 'tcx> {
         let (local_ccx, index) =
             self.local_ccxs
                 .iter()
@@ -355,11 +355,11 @@ impl SharedCrateContext {
         &self.symbol_hasher
     }
 
-    pub fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+    pub fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         &self.tcx
     }
 
-    pub fn take_tcx(self) -> ty::ctxt {
+    pub fn take_tcx(self) -> ty::ctxt<'tcx> {
         self.tcx
     }
 
@@ -459,7 +459,8 @@ impl LocalCrateContext {
     /// This is used in the `LocalCrateContext` constructor to allow calling
     /// functions that expect a complete `CrateContext`, even before the local
     /// portion is fully initialized and attached to the `SharedCrateContext`.
-    fn dummy_ccx<'a>(&'a self, shared: &'a SharedCrateContext) -> CrateContext<'a> {
+    fn dummy_ccx<'a, 'tcx>(&'a self, shared: &'a SharedCrateContext<'tcx>)
+                           -> CrateContext<'a, 'tcx> {
         CrateContext {
             shared: shared,
             local: self,
@@ -468,8 +469,8 @@ impl LocalCrateContext {
     }
 }
 
-impl<'b> CrateContext<'b> {
-    pub fn shared(&self) -> &'b SharedCrateContext {
+impl<'b, 'tcx> CrateContext<'b, 'tcx> {
+    pub fn shared(&self) -> &'b SharedCrateContext<'tcx> {
         self.shared
     }
 
@@ -480,7 +481,7 @@ impl<'b> CrateContext<'b> {
 
     /// Get a (possibly) different `CrateContext` from the same
     /// `SharedCrateContext`.
-    pub fn rotate(&self) -> CrateContext<'b> {
+    pub fn rotate(&self) -> CrateContext<'b, 'tcx> {
         self.shared.get_smallest_ccx()
     }
 
@@ -490,7 +491,7 @@ impl<'b> CrateContext<'b> {
     /// otherwise.  This method is useful for avoiding code duplication in
     /// cases where it may or may not be necessary to translate code into every
     /// context.
-    pub fn maybe_iter(&self, iter_all: bool) -> CrateContextMaybeIterator<'b> {
+    pub fn maybe_iter(&self, iter_all: bool) -> CrateContextMaybeIterator<'b, 'tcx> {
         CrateContextMaybeIterator {
             shared: self.shared,
             index: if iter_all { 0 } else { self.index },
@@ -500,7 +501,7 @@ impl<'b> CrateContext<'b> {
     }
 
 
-    pub fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+    pub fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         &self.shared.tcx
     }
 
@@ -508,7 +509,7 @@ impl<'b> CrateContext<'b> {
         &self.shared.tcx.sess
     }
 
-    pub fn builder<'a>(&'a self) -> Builder<'a> {
+    pub fn builder<'a>(&'a self) -> Builder<'a, 'tcx> {
         Builder::new(self)
     }
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index ff558ce5cff..feed76233d6 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -3468,10 +3468,10 @@ impl AutoRef {
     }
 }
 
-pub fn method_call_type_param_defs<T>(typer: &T,
-                                      origin: typeck::MethodOrigin)
-                                      -> VecPerParamSpace<TypeParameterDef>
-                                      where T: mc::Typer {
+pub fn method_call_type_param_defs<'tcx, T>(typer: &T,
+                                            origin: typeck::MethodOrigin)
+                                            -> VecPerParamSpace<TypeParameterDef>
+                                            where T: mc::Typer<'tcx> {
     match origin {
         typeck::MethodStatic(did) => {
             ty::lookup_item_type(typer.tcx(), did).generics.types.clone()
@@ -4660,10 +4660,10 @@ pub fn normalize_ty(cx: &ctxt, t: t) -> t {
     let u = TypeNormalizer(cx).fold_ty(t);
     return u;
 
-    struct TypeNormalizer<'a>(&'a ctxt);
+    struct TypeNormalizer<'a, 'tcx: 'a>(&'a ctxt<'tcx>);
 
-    impl<'a> TypeFolder for TypeNormalizer<'a> {
-        fn tcx<'a>(&'a self) -> &'a ctxt { let TypeNormalizer(c) = *self; c }
+    impl<'a, 'tcx> TypeFolder<'tcx> for TypeNormalizer<'a, 'tcx> {
+        fn tcx<'a>(&'a self) -> &'a ctxt<'tcx> { let TypeNormalizer(c) = *self; c }
 
         fn fold_ty(&mut self, t: ty::t) -> ty::t {
             match self.tcx().normalized_cache.borrow().find_copy(&t) {
@@ -4702,70 +4702,55 @@ pub fn normalize_ty(cx: &ctxt, t: t) -> t {
     }
 }
 
-pub trait ExprTyProvider {
-    fn expr_ty(&self, ex: &ast::Expr) -> t;
-    fn ty_ctxt<'a>(&'a self) -> &'a ctxt;
-}
-
-impl ExprTyProvider for ctxt {
-    fn expr_ty(&self, ex: &ast::Expr) -> t {
-        expr_ty(self, ex)
-    }
-
-    fn ty_ctxt<'a>(&'a self) -> &'a ctxt {
-        self
-    }
-}
-
 // Returns the repeat count for a repeating vector expression.
-pub fn eval_repeat_count<T: ExprTyProvider>(tcx: &T, count_expr: &ast::Expr) -> uint {
+pub fn eval_repeat_count(tcx: &ctxt, count_expr: &ast::Expr) -> uint {
     match const_eval::eval_const_expr_partial(tcx, count_expr) {
       Ok(ref const_val) => match *const_val {
         const_eval::const_int(count) => if count < 0 {
-            tcx.ty_ctxt().sess.span_err(count_expr.span,
-                                        "expected positive integer for \
-                                         repeat count, found negative integer");
-            return 0;
+            tcx.sess.span_err(count_expr.span,
+                              "expected positive integer for \
+                               repeat count, found negative integer");
+            0
         } else {
-            return count as uint
+            count as uint
         },
-        const_eval::const_uint(count) => return count as uint,
+        const_eval::const_uint(count) => count as uint,
         const_eval::const_float(count) => {
-            tcx.ty_ctxt().sess.span_err(count_expr.span,
-                                        "expected positive integer for \
-                                         repeat count, found float");
-            return count as uint;
+            tcx.sess.span_err(count_expr.span,
+                              "expected positive integer for \
+                               repeat count, found float");
+            count as uint
         }
         const_eval::const_str(_) => {
-            tcx.ty_ctxt().sess.span_err(count_expr.span,
-                                        "expected positive integer for \
-                                         repeat count, found string");
-            return 0;
+            tcx.sess.span_err(count_expr.span,
+                              "expected positive integer for \
+                               repeat count, found string");
+            0
         }
         const_eval::const_bool(_) => {
-            tcx.ty_ctxt().sess.span_err(count_expr.span,
-                                        "expected positive integer for \
-                                         repeat count, found boolean");
-            return 0;
+            tcx.sess.span_err(count_expr.span,
+                              "expected positive integer for \
+                               repeat count, found boolean");
+            0
         }
         const_eval::const_binary(_) => {
-            tcx.ty_ctxt().sess.span_err(count_expr.span,
-                                        "expected positive integer for \
-                                         repeat count, found binary array");
-            return 0;
+            tcx.sess.span_err(count_expr.span,
+                              "expected positive integer for \
+                               repeat count, found binary array");
+            0
         }
         const_eval::const_nil => {
-            tcx.ty_ctxt().sess.span_err(count_expr.span,
-                                        "expected positive integer for \
-                                         repeat count, found ()");
-            return 0;
+            tcx.sess.span_err(count_expr.span,
+                              "expected positive integer for \
+                               repeat count, found ()");
+            0
         }
       },
       Err(..) => {
-        tcx.ty_ctxt().sess.span_err(count_expr.span,
-                                    "expected constant integer for repeat count, \
-                                     found variable");
-        return 0;
+        tcx.sess.span_err(count_expr.span,
+                          "expected constant integer for repeat count, \
+                           found variable");
+        0
       }
     }
 }
@@ -5402,8 +5387,8 @@ impl BorrowKind {
     }
 }
 
-impl mc::Typer for ty::ctxt {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+impl<'tcx> mc::Typer<'tcx> for ty::ctxt<'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         self
     }
 
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 07c8573ef85..bc53568694d 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -25,7 +25,7 @@ use util::ppaux::Repr;
 /// The TypeFoldable trait is implemented for every type that can be folded.
 /// Basically, every type that has a corresponding method in TypeFolder.
 pub trait TypeFoldable {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> Self;
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self;
 }
 
 /// The TypeFolder trait defines the actual *folding*. There is a
@@ -33,8 +33,8 @@ pub trait TypeFoldable {
 /// default implementation that does an "identity" fold. Within each
 /// identity fold, it should invoke `foo.fold_with(self)` to fold each
 /// sub-item.
-pub trait TypeFolder {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt;
+pub trait TypeFolder<'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
 
     fn fold_ty(&mut self, t: ty::t) -> ty::t {
         super_fold_ty(self, t)
@@ -111,97 +111,97 @@ pub trait TypeFolder {
 // needed.
 
 impl<T:TypeFoldable> TypeFoldable for Option<T> {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> Option<T> {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Option<T> {
         self.as_ref().map(|t| t.fold_with(folder))
     }
 }
 
 impl<T:TypeFoldable> TypeFoldable for Rc<T> {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> Rc<T> {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Rc<T> {
         Rc::new((**self).fold_with(folder))
     }
 }
 
 impl<T:TypeFoldable> TypeFoldable for Vec<T> {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> Vec<T> {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Vec<T> {
         self.iter().map(|t| t.fold_with(folder)).collect()
     }
 }
 
 impl<T:TypeFoldable> TypeFoldable for OwnedSlice<T> {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> OwnedSlice<T> {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> OwnedSlice<T> {
         self.iter().map(|t| t.fold_with(folder)).collect()
     }
 }
 
 impl<T:TypeFoldable> TypeFoldable for VecPerParamSpace<T> {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> VecPerParamSpace<T> {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> VecPerParamSpace<T> {
         self.map(|t| t.fold_with(folder))
     }
 }
 
 impl TypeFoldable for ty::TraitStore {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::TraitStore {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitStore {
         folder.fold_trait_store(*self)
     }
 }
 
 impl TypeFoldable for ty::t {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::t {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::t {
         folder.fold_ty(*self)
     }
 }
 
 impl TypeFoldable for ty::BareFnTy {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::BareFnTy {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::BareFnTy {
         folder.fold_bare_fn_ty(self)
     }
 }
 
 impl TypeFoldable for ty::ClosureTy {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::ClosureTy {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ClosureTy {
         folder.fold_closure_ty(self)
     }
 }
 
 impl TypeFoldable for ty::mt {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::mt {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::mt {
         folder.fold_mt(self)
     }
 }
 
 impl TypeFoldable for ty::FnSig {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::FnSig {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::FnSig {
         folder.fold_sig(self)
     }
 }
 
 impl TypeFoldable for ty::sty {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::sty {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::sty {
         folder.fold_sty(self)
     }
 }
 
 impl TypeFoldable for ty::TraitRef {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::TraitRef {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitRef {
         folder.fold_trait_ref(self)
     }
 }
 
 impl TypeFoldable for ty::Region {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::Region {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Region {
         folder.fold_region(*self)
     }
 }
 
 impl TypeFoldable for subst::Substs {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> subst::Substs {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> subst::Substs {
         folder.fold_substs(self)
     }
 }
 
 impl TypeFoldable for ty::ItemSubsts {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::ItemSubsts {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ItemSubsts {
         ty::ItemSubsts {
             substs: self.substs.fold_with(folder),
         }
@@ -209,13 +209,13 @@ impl TypeFoldable for ty::ItemSubsts {
 }
 
 impl TypeFoldable for ty::AutoRef {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::AutoRef {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::AutoRef {
         folder.fold_autoref(self)
     }
 }
 
 impl TypeFoldable for typeck::vtable_origin {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> typeck::vtable_origin {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> typeck::vtable_origin {
         match *self {
             typeck::vtable_static(def_id, ref substs, ref origins) => {
                 let r_substs = substs.fold_with(folder);
@@ -236,19 +236,19 @@ impl TypeFoldable for typeck::vtable_origin {
 }
 
 impl TypeFoldable for ty::BuiltinBounds {
-    fn fold_with<F:TypeFolder>(&self, _folder: &mut F) -> ty::BuiltinBounds {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, _folder: &mut F) -> ty::BuiltinBounds {
         *self
     }
 }
 
 impl TypeFoldable for ty::ExistentialBounds {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::ExistentialBounds {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ExistentialBounds {
         folder.fold_existential_bounds(*self)
     }
 }
 
 impl TypeFoldable for ty::ParamBounds {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::ParamBounds {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ParamBounds {
         ty::ParamBounds {
             opt_region_bound: self.opt_region_bound.fold_with(folder),
             builtin_bounds: self.builtin_bounds.fold_with(folder),
@@ -258,7 +258,7 @@ impl TypeFoldable for ty::ParamBounds {
 }
 
 impl TypeFoldable for ty::TypeParameterDef {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::TypeParameterDef {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TypeParameterDef {
         ty::TypeParameterDef {
             ident: self.ident,
             def_id: self.def_id,
@@ -271,7 +271,7 @@ impl TypeFoldable for ty::TypeParameterDef {
 }
 
 impl TypeFoldable for ty::RegionParameterDef {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::RegionParameterDef {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::RegionParameterDef {
         ty::RegionParameterDef {
             name: self.name,
             def_id: self.def_id,
@@ -283,7 +283,7 @@ impl TypeFoldable for ty::RegionParameterDef {
 }
 
 impl TypeFoldable for ty::Generics {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::Generics {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Generics {
         ty::Generics {
             types: self.types.fold_with(folder),
             regions: self.regions.fold_with(folder),
@@ -292,7 +292,7 @@ impl TypeFoldable for ty::Generics {
 }
 
 impl TypeFoldable for ty::UnsizeKind {
-    fn fold_with<F:TypeFolder>(&self, folder: &mut F) -> ty::UnsizeKind {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::UnsizeKind {
         match *self {
             ty::UnsizeLength(len) => ty::UnsizeLength(len),
             ty::UnsizeStruct(box ref k, n) => ty::UnsizeStruct(box k.fold_with(folder), n),
@@ -307,17 +307,16 @@ impl TypeFoldable for ty::UnsizeKind {
 // "super" routines: these are the default implementations for TypeFolder.
 //
 // They should invoke `foo.fold_with()` to do recursive folding.
-
-pub fn super_fold_ty<T:TypeFolder>(this: &mut T,
-                                   t: ty::t)
-                                   -> ty::t {
+pub fn super_fold_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                t: ty::t)
+                                                -> ty::t {
     let sty = ty::get(t).sty.fold_with(this);
     ty::mk_t(this.tcx(), sty)
 }
 
-pub fn super_fold_substs<T:TypeFolder>(this: &mut T,
-                                       substs: &subst::Substs)
-                                       -> subst::Substs {
+pub fn super_fold_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                    substs: &subst::Substs)
+                                                    -> subst::Substs {
     let regions = match substs.regions {
         subst::ErasedRegions => {
             subst::ErasedRegions
@@ -331,27 +330,27 @@ pub fn super_fold_substs<T:TypeFolder>(this: &mut T,
                     types: substs.types.fold_with(this) }
 }
 
-pub fn super_fold_sig<T:TypeFolder>(this: &mut T,
-                                    sig: &ty::FnSig)
-                                    -> ty::FnSig {
+pub fn super_fold_sig<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                 sig: &ty::FnSig)
+                                                 -> ty::FnSig {
     ty::FnSig { binder_id: sig.binder_id,
                 inputs: sig.inputs.fold_with(this),
                 output: sig.output.fold_with(this),
                 variadic: sig.variadic }
 }
 
-pub fn super_fold_bare_fn_ty<T:TypeFolder>(this: &mut T,
-                                           fty: &ty::BareFnTy)
-                                           -> ty::BareFnTy
+pub fn super_fold_bare_fn_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                        fty: &ty::BareFnTy)
+                                                        -> ty::BareFnTy
 {
     ty::BareFnTy { sig: fty.sig.fold_with(this),
                    abi: fty.abi,
                    fn_style: fty.fn_style }
 }
 
-pub fn super_fold_closure_ty<T:TypeFolder>(this: &mut T,
-                                           fty: &ty::ClosureTy)
-                                           -> ty::ClosureTy
+pub fn super_fold_closure_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                        fty: &ty::ClosureTy)
+                                                        -> ty::ClosureTy
 {
     ty::ClosureTy {
         store: fty.store.fold_with(this),
@@ -362,24 +361,23 @@ pub fn super_fold_closure_ty<T:TypeFolder>(this: &mut T,
         abi: fty.abi,
     }
 }
-
-pub fn super_fold_trait_ref<T:TypeFolder>(this: &mut T,
-                                          t: &ty::TraitRef)
-                                          -> ty::TraitRef {
+pub fn super_fold_trait_ref<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                       t: &ty::TraitRef)
+                                                       -> ty::TraitRef {
     ty::TraitRef {
         def_id: t.def_id,
         substs: t.substs.fold_with(this),
     }
 }
 
-pub fn super_fold_mt<T:TypeFolder>(this: &mut T,
-                                   mt: &ty::mt) -> ty::mt {
+pub fn super_fold_mt<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                mt: &ty::mt) -> ty::mt {
     ty::mt {ty: mt.ty.fold_with(this),
             mutbl: mt.mutbl}
 }
 
-pub fn super_fold_sty<T:TypeFolder>(this: &mut T,
-                                    sty: &ty::sty) -> ty::sty {
+pub fn super_fold_sty<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                 sty: &ty::sty) -> ty::sty {
     match *sty {
         ty::ty_box(typ) => {
             ty::ty_box(typ.fold_with(this))
@@ -437,9 +435,9 @@ pub fn super_fold_sty<T:TypeFolder>(this: &mut T,
     }
 }
 
-pub fn super_fold_trait_store<T:TypeFolder>(this: &mut T,
-                                            trait_store: ty::TraitStore)
-                                            -> ty::TraitStore {
+pub fn super_fold_trait_store<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                         trait_store: ty::TraitStore)
+                                                         -> ty::TraitStore {
     match trait_store {
         ty::UniqTraitStore => ty::UniqTraitStore,
         ty::RegionTraitStore(r, m) => {
@@ -448,18 +446,18 @@ pub fn super_fold_trait_store<T:TypeFolder>(this: &mut T,
     }
 }
 
-pub fn super_fold_existential_bounds<T:TypeFolder>(this: &mut T,
-                                                   bounds: ty::ExistentialBounds)
-                                                   -> ty::ExistentialBounds {
+pub fn super_fold_existential_bounds<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                                bounds: ty::ExistentialBounds)
+                                                                -> ty::ExistentialBounds {
     ty::ExistentialBounds {
         region_bound: bounds.region_bound.fold_with(this),
         builtin_bounds: bounds.builtin_bounds,
     }
 }
 
-pub fn super_fold_autoref<T:TypeFolder>(this: &mut T,
-                                        autoref: &ty::AutoRef)
-                                        -> ty::AutoRef
+pub fn super_fold_autoref<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                     autoref: &ty::AutoRef)
+                                                     -> ty::AutoRef
 {
     match *autoref {
         ty::AutoPtr(r, m, None) => ty::AutoPtr(this.fold_region(r), m, None),
@@ -475,9 +473,9 @@ pub fn super_fold_autoref<T:TypeFolder>(this: &mut T,
     }
 }
 
-pub fn super_fold_item_substs<T:TypeFolder>(this: &mut T,
-                                            substs: ty::ItemSubsts)
-                                            -> ty::ItemSubsts
+pub fn super_fold_item_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
+                                                         substs: ty::ItemSubsts)
+                                                         -> ty::ItemSubsts
 {
     ty::ItemSubsts {
         substs: substs.substs.fold_with(this),
@@ -487,13 +485,13 @@ pub fn super_fold_item_substs<T:TypeFolder>(this: &mut T,
 ///////////////////////////////////////////////////////////////////////////
 // Some sample folders
 
-pub struct BottomUpFolder<'a> {
-    pub tcx: &'a ty::ctxt,
+pub struct BottomUpFolder<'a, 'tcx: 'a> {
+    pub tcx: &'a ty::ctxt<'tcx>,
     pub fldop: |ty::t|: 'a -> ty::t,
 }
 
-impl<'a> TypeFolder for BottomUpFolder<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.tcx }
+impl<'a, 'tcx> TypeFolder<'tcx> for BottomUpFolder<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 
     fn fold_ty(&mut self, ty: ty::t) -> ty::t {
         let t1 = super_fold_ty(self, ty);
@@ -516,18 +514,18 @@ impl<'a> TypeFolder for BottomUpFolder<'a> {
 /// (The distinction between "free" and "bound" is represented by
 /// keeping track of each `FnSig` in the lexical context of the
 /// current position of the fold.)
-pub struct RegionFolder<'a> {
-    tcx: &'a ty::ctxt,
+pub struct RegionFolder<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     fld_t: |ty::t|: 'a -> ty::t,
     fld_r: |ty::Region|: 'a -> ty::Region,
     within_binder_ids: Vec<ast::NodeId>,
 }
 
-impl<'a> RegionFolder<'a> {
-    pub fn general(tcx: &'a ty::ctxt,
+impl<'a, 'tcx> RegionFolder<'a, 'tcx> {
+    pub fn general(tcx: &'a ty::ctxt<'tcx>,
                    fld_r: |ty::Region|: 'a -> ty::Region,
                    fld_t: |ty::t|: 'a -> ty::t)
-                   -> RegionFolder<'a> {
+                   -> RegionFolder<'a, 'tcx> {
         RegionFolder {
             tcx: tcx,
             fld_t: fld_t,
@@ -536,8 +534,8 @@ impl<'a> RegionFolder<'a> {
         }
     }
 
-    pub fn regions(tcx: &'a ty::ctxt, fld_r: |ty::Region|: 'a -> ty::Region)
-                   -> RegionFolder<'a> {
+    pub fn regions(tcx: &'a ty::ctxt<'tcx>, fld_r: |ty::Region|: 'a -> ty::Region)
+                   -> RegionFolder<'a, 'tcx> {
         fn noop(t: ty::t) -> ty::t { t }
 
         RegionFolder {
@@ -559,8 +557,8 @@ fn opt_binder_id_of_function(t: ty::t) -> Option<ast::NodeId> {
     }
 }
 
-impl<'a> TypeFolder for RegionFolder<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.tcx }
+impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 
     fn fold_ty(&mut self, ty: ty::t) -> ty::t {
         debug!("RegionFolder.fold_ty({})", ty.repr(self.tcx()));
diff --git a/src/librustc/middle/typeck/astconv.rs b/src/librustc/middle/typeck/astconv.rs
index 6cd61a8c3f8..f5fa6168a41 100644
--- a/src/librustc/middle/typeck/astconv.rs
+++ b/src/librustc/middle/typeck/astconv.rs
@@ -71,8 +71,8 @@ use syntax::abi;
 use syntax::{ast, ast_util};
 use syntax::codemap::Span;
 
-pub trait AstConv {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt;
+pub trait AstConv<'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype;
     fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef>;
 
@@ -118,7 +118,7 @@ pub fn ast_region_to_region(tcx: &ty::ctxt, lifetime: &ast::Lifetime)
     r
 }
 
-pub fn opt_ast_region_to_region<AC:AstConv,RS:RegionScope>(
+pub fn opt_ast_region_to_region<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
     this: &AC,
     rscope: &RS,
     default_span: Span,
@@ -152,7 +152,7 @@ pub fn opt_ast_region_to_region<AC:AstConv,RS:RegionScope>(
     r
 }
 
-fn ast_path_substs<AC:AstConv,RS:RegionScope>(
+fn ast_path_substs<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
     this: &AC,
     rscope: &RS,
     decl_generics: &ty::Generics,
@@ -271,7 +271,7 @@ fn ast_path_substs<AC:AstConv,RS:RegionScope>(
     substs
 }
 
-pub fn ast_path_to_trait_ref<AC:AstConv,RS:RegionScope>(
+pub fn ast_path_to_trait_ref<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
         this: &AC,
         rscope: &RS,
         trait_def_id: ast::DefId,
@@ -284,7 +284,7 @@ pub fn ast_path_to_trait_ref<AC:AstConv,RS:RegionScope>(
     })
 }
 
-pub fn ast_path_to_ty<AC:AstConv,RS:RegionScope>(
+pub fn ast_path_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
     this: &AC,
     rscope: &RS,
     did: ast::DefId,
@@ -307,7 +307,7 @@ pub fn ast_path_to_ty<AC:AstConv,RS:RegionScope>(
 /// and/or region variables are substituted.
 ///
 /// This is used when checking the constructor in struct literals.
-pub fn ast_path_to_ty_relaxed<AC:AstConv,
+pub fn ast_path_to_ty_relaxed<'tcx, AC: AstConv<'tcx>,
                               RS:RegionScope>(
                               this: &AC,
                               rscope: &RS,
@@ -412,12 +412,11 @@ pub fn ast_ty_to_prim_ty(tcx: &ty::ctxt, ast_ty: &ast::Ty) -> Option<ty::t> {
 
 /// Converts the given AST type to a built-in type. A "built-in type" is, at
 /// present, either a core numeric type, a string, or `Box`.
-pub fn ast_ty_to_builtin_ty<AC:AstConv,
-                            RS:RegionScope>(
-                            this: &AC,
-                            rscope: &RS,
-                            ast_ty: &ast::Ty)
-                            -> Option<ty::t> {
+pub fn ast_ty_to_builtin_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
+        this: &AC,
+        rscope: &RS,
+        ast_ty: &ast::Ty)
+        -> Option<ty::t> {
     match ast_ty_to_prim_ty(this.tcx(), ast_ty) {
         Some(typ) => return Some(typ),
         None => {}
@@ -531,7 +530,7 @@ impl PointerTy {
     }
 }
 
-pub fn trait_ref_for_unboxed_function<AC:AstConv,
+pub fn trait_ref_for_unboxed_function<'tcx, AC: AstConv<'tcx>,
                                       RS:RegionScope>(
                                       this: &AC,
                                       rscope: &RS,
@@ -576,14 +575,13 @@ pub fn trait_ref_for_unboxed_function<AC:AstConv,
 // Handle `~`, `Box`, and `&` being able to mean strs and vecs.
 // If a_seq_ty is a str or a vec, make it a str/vec.
 // Also handle first-class trait types.
-fn mk_pointer<AC:AstConv,
-              RS:RegionScope>(
-              this: &AC,
-              rscope: &RS,
-              a_seq_ty: &ast::MutTy,
-              ptr_ty: PointerTy,
-              constr: |ty::t| -> ty::t)
-              -> ty::t {
+fn mk_pointer<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
+        this: &AC,
+        rscope: &RS,
+        a_seq_ty: &ast::MutTy,
+        ptr_ty: PointerTy,
+        constr: |ty::t| -> ty::t)
+        -> ty::t {
     let tcx = this.tcx();
     debug!("mk_pointer(ptr_ty={})", ptr_ty);
 
@@ -695,8 +693,8 @@ fn mk_pointer<AC:AstConv,
 
 // Parses the programmer's textual representation of a type into our
 // internal notion of a type.
-pub fn ast_ty_to_ty<AC:AstConv, RS:RegionScope>(
-    this: &AC, rscope: &RS, ast_ty: &ast::Ty) -> ty::t {
+pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
+        this: &AC, rscope: &RS, ast_ty: &ast::Ty) -> ty::t {
 
     let tcx = this.tcx();
 
@@ -914,8 +912,10 @@ pub fn ast_ty_to_ty<AC:AstConv, RS:RegionScope>(
     return typ;
 }
 
-pub fn ty_of_arg<AC: AstConv, RS: RegionScope>(this: &AC, rscope: &RS, a: &ast::Arg,
-                                               expected_ty: Option<ty::t>) -> ty::t {
+pub fn ty_of_arg<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(this: &AC, rscope: &RS,
+                                                           a: &ast::Arg,
+                                                           expected_ty: Option<ty::t>)
+                                                           -> ty::t {
     match a.ty.node {
         ast::TyInfer if expected_ty.is_some() => expected_ty.unwrap(),
         ast::TyInfer => this.ty_infer(a.ty.span),
@@ -928,7 +928,7 @@ struct SelfInfo<'a> {
     explicit_self: ast::ExplicitSelf,
 }
 
-pub fn ty_of_method<AC:AstConv>(
+pub fn ty_of_method<'tcx, AC: AstConv<'tcx>>(
                     this: &AC,
                     id: ast::NodeId,
                     fn_style: ast::FnStyle,
@@ -951,15 +951,15 @@ pub fn ty_of_method<AC:AstConv>(
     (bare_fn_ty, optional_explicit_self_category.unwrap())
 }
 
-pub fn ty_of_bare_fn<AC:AstConv>(this: &AC, id: ast::NodeId,
-                                 fn_style: ast::FnStyle, abi: abi::Abi,
-                                 decl: &ast::FnDecl) -> ty::BareFnTy {
+pub fn ty_of_bare_fn<'tcx, AC: AstConv<'tcx>>(this: &AC, id: ast::NodeId,
+                                              fn_style: ast::FnStyle, abi: abi::Abi,
+                                              decl: &ast::FnDecl) -> ty::BareFnTy {
     let (bare_fn_ty, _) =
         ty_of_method_or_bare_fn(this, id, fn_style, abi, None, decl);
     bare_fn_ty
 }
 
-fn ty_of_method_or_bare_fn<AC:AstConv>(
+fn ty_of_method_or_bare_fn<'tcx, AC: AstConv<'tcx>>(
                            this: &AC,
                            id: ast::NodeId,
                            fn_style: ast::FnStyle,
@@ -1070,7 +1070,7 @@ fn ty_of_method_or_bare_fn<AC:AstConv>(
     }, explicit_self_category_result)
 }
 
-fn determine_explicit_self_category<AC:AstConv,
+fn determine_explicit_self_category<'tcx, AC: AstConv<'tcx>,
                                     RS:RegionScope>(
                                     this: &AC,
                                     rscope: &RS,
@@ -1145,7 +1145,7 @@ fn determine_explicit_self_category<AC:AstConv,
     }
 }
 
-pub fn ty_of_closure<AC:AstConv>(
+pub fn ty_of_closure<'tcx, AC: AstConv<'tcx>>(
     this: &AC,
     id: ast::NodeId,
     fn_style: ast::FnStyle,
@@ -1196,7 +1196,7 @@ pub fn ty_of_closure<AC:AstConv>(
     }
 }
 
-pub fn conv_existential_bounds<AC:AstConv, RS:RegionScope>(
+pub fn conv_existential_bounds<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
     this: &AC,
     rscope: &RS,
     span: Span,
@@ -1330,7 +1330,7 @@ pub fn compute_opt_region_bound(tcx: &ty::ctxt,
     return Some(r);
 }
 
-fn compute_region_bound<AC:AstConv, RS:RegionScope>(
+fn compute_region_bound<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
     this: &AC,
     rscope: &RS,
     span: Span,
diff --git a/src/librustc/middle/typeck/check/_match.rs b/src/librustc/middle/typeck/check/_match.rs
index 77e5fbae6ee..247178770d2 100644
--- a/src/librustc/middle/typeck/check/_match.rs
+++ b/src/librustc/middle/typeck/check/_match.rs
@@ -107,8 +107,8 @@ pub fn check_match(fcx: &FnCtxt,
     fcx.write_ty(expr.id, result_ty);
 }
 
-pub struct pat_ctxt<'a> {
-    pub fcx: &'a FnCtxt<'a>,
+pub struct pat_ctxt<'a, 'tcx: 'a> {
+    pub fcx: &'a FnCtxt<'a, 'tcx>,
     pub map: PatIdMap,
 }
 
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 3c15135807b..88d9a58ab14 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -123,8 +123,8 @@ pub enum StaticMethodsFlag {
     IgnoreStaticMethods,
 }
 
-pub fn lookup<'a>(
-        fcx: &'a FnCtxt<'a>,
+pub fn lookup<'a, 'tcx>(
+        fcx: &'a FnCtxt<'a, 'tcx>,
 
         // In a call `a.b::<X, Y, ...>(...)`:
         expr: &ast::Expr,                   // The expression `a.b(...)`.
@@ -170,8 +170,8 @@ pub fn lookup<'a>(
     lcx.search(self_ty)
 }
 
-pub fn lookup_in_trait<'a>(
-        fcx: &'a FnCtxt<'a>,
+pub fn lookup_in_trait<'a, 'tcx>(
+        fcx: &'a FnCtxt<'a, 'tcx>,
 
         // In a call `a.b::<X, Y, ...>(...)`:
         span: Span,                         // The expression `a.b(...)`'s span.
@@ -303,8 +303,8 @@ fn construct_transformed_self_ty_for_object(
     }
 }
 
-struct LookupContext<'a> {
-    fcx: &'a FnCtxt<'a>,
+struct LookupContext<'a, 'tcx: 'a> {
+    fcx: &'a FnCtxt<'a, 'tcx>,
     span: Span,
 
     // The receiver to the method call. Only `None` in the case of
@@ -350,7 +350,7 @@ pub enum RcvrMatchCondition {
     RcvrMatchesIfSubtype(ty::t),
 }
 
-impl<'a> LookupContext<'a> {
+impl<'a, 'tcx> LookupContext<'a, 'tcx> {
     fn search(&self, self_ty: ty::t) -> Option<MethodCallee> {
         let span = self.self_expr.map_or(self.span, |e| e.span);
         let self_expr_id = self.self_expr.map(|e| e.id);
@@ -1615,11 +1615,11 @@ impl<'a> LookupContext<'a> {
             idx + 1u, ty::item_path_str(self.tcx(), did));
     }
 
-    fn infcx(&'a self) -> &'a infer::InferCtxt<'a> {
+    fn infcx(&'a self) -> &'a infer::InferCtxt<'a, 'tcx> {
         &self.fcx.inh.infcx
     }
 
-    fn tcx(&self) -> &'a ty::ctxt {
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> {
         self.fcx.tcx()
     }
 
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index c70e8505174..01b5fd6e429 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -89,7 +89,7 @@ use middle::subst;
 use middle::subst::{Subst, Substs, VecPerParamSpace, ParamSpace};
 use middle::ty::{FnSig, VariantInfo};
 use middle::ty::{Polytype};
-use middle::ty::{Disr, ExprTyProvider, ParamTy, ParameterEnvironment};
+use middle::ty::{Disr, ParamTy, ParameterEnvironment};
 use middle::ty;
 use middle::ty_fold::TypeFolder;
 use middle::typeck::astconv::AstConv;
@@ -159,8 +159,8 @@ pub mod method;
 /// Here, the function `foo()` and the closure passed to
 /// `bar()` will each have their own `FnCtxt`, but they will
 /// share the inherited fields.
-pub struct Inherited<'a> {
-    infcx: infer::InferCtxt<'a>,
+pub struct Inherited<'a, 'tcx: 'a> {
+    infcx: infer::InferCtxt<'a, 'tcx>,
     locals: RefCell<NodeMap<ty::t>>,
     param_env: ty::ParameterEnvironment,
 
@@ -267,7 +267,7 @@ enum IsBinopAssignment{
 }
 
 #[deriving(Clone)]
-pub struct FnCtxt<'a> {
+pub struct FnCtxt<'a, 'tcx: 'a> {
     body_id: ast::NodeId,
 
     // This flag is set to true if, during the writeback phase, we encounter
@@ -284,13 +284,13 @@ pub struct FnCtxt<'a> {
 
     ps: RefCell<FnStyleState>,
 
-    inh: &'a Inherited<'a>,
+    inh: &'a Inherited<'a, 'tcx>,
 
-    ccx: &'a CrateCtxt<'a>,
+    ccx: &'a CrateCtxt<'a, 'tcx>,
 }
 
-impl<'a> mem_categorization::Typer for FnCtxt<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+impl<'a, 'tcx> mem_categorization::Typer<'tcx> for FnCtxt<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         self.ccx.tcx
     }
     fn node_ty(&self, id: ast::NodeId) -> McResult<ty::t> {
@@ -322,10 +322,10 @@ impl<'a> mem_categorization::Typer for FnCtxt<'a> {
     }
 }
 
-impl<'a> Inherited<'a> {
-    fn new(tcx: &'a ty::ctxt,
+impl<'a, 'tcx> Inherited<'a, 'tcx> {
+    fn new(tcx: &'a ty::ctxt<'tcx>,
            param_env: ty::ParameterEnvironment)
-           -> Inherited<'a> {
+           -> Inherited<'a, 'tcx> {
         Inherited {
             infcx: infer::new_infer_ctxt(tcx),
             locals: RefCell::new(NodeMap::new()),
@@ -344,12 +344,11 @@ impl<'a> Inherited<'a> {
 }
 
 // Used by check_const and check_enum_variants
-pub fn blank_fn_ctxt<'a>(
-                     ccx: &'a CrateCtxt<'a>,
-                     inh: &'a Inherited<'a>,
-                     rty: ty::t,
-                     body_id: ast::NodeId)
-                     -> FnCtxt<'a> {
+pub fn blank_fn_ctxt<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>,
+                               inh: &'a Inherited<'a, 'tcx>,
+                               rty: ty::t,
+                               body_id: ast::NodeId)
+                               -> FnCtxt<'a, 'tcx> {
     FnCtxt {
         body_id: body_id,
         writeback_errors: Cell::new(false),
@@ -361,7 +360,8 @@ pub fn blank_fn_ctxt<'a>(
     }
 }
 
-fn static_inherited_fields<'a>(ccx: &'a CrateCtxt<'a>) -> Inherited<'a> {
+fn static_inherited_fields<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>)
+                                    -> Inherited<'a, 'tcx> {
     // It's kind of a kludge to manufacture a fake function context
     // and statement context, but we might as well do write the code only once
     let param_env = ty::ParameterEnvironment {
@@ -372,37 +372,29 @@ fn static_inherited_fields<'a>(ccx: &'a CrateCtxt<'a>) -> Inherited<'a> {
     Inherited::new(ccx.tcx, param_env)
 }
 
-impl<'a> ExprTyProvider for FnCtxt<'a> {
-    fn expr_ty(&self, ex: &ast::Expr) -> ty::t {
-        self.expr_ty(ex)
-    }
-
-    fn ty_ctxt<'a>(&'a self) -> &'a ty::ctxt {
-        self.ccx.tcx
-    }
-}
-
-struct CheckTypeWellFormedVisitor<'a> { ccx: &'a CrateCtxt<'a> }
+struct CheckItemTypesVisitor<'a, 'tcx: 'a> { ccx: &'a CrateCtxt<'a, 'tcx> }
+struct CheckTypeWellFormedVisitor<'a, 'tcx: 'a> { ccx: &'a CrateCtxt<'a, 'tcx> }
 
-impl<'a> Visitor<()> for CheckTypeWellFormedVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for CheckTypeWellFormedVisitor<'a, 'tcx> {
     fn visit_item(&mut self, i: &ast::Item, _: ()) {
         check_type_well_formed(self.ccx, i);
         visit::walk_item(self, i, ());
     }
 }
 
-struct CheckItemTypesVisitor<'a> { ccx: &'a CrateCtxt<'a> }
 
-impl<'a> Visitor<()> for CheckItemTypesVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for CheckItemTypesVisitor<'a, 'tcx> {
     fn visit_item(&mut self, i: &ast::Item, _: ()) {
         check_item(self.ccx, i);
         visit::walk_item(self, i, ());
     }
 }
 
-struct CheckItemSizedTypesVisitor<'a> { ccx: &'a CrateCtxt<'a> }
+struct CheckItemSizedTypesVisitor<'a, 'tcx: 'a> {
+    ccx: &'a CrateCtxt<'a, 'tcx>
+}
 
-impl<'a> Visitor<()> for CheckItemSizedTypesVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for CheckItemSizedTypesVisitor<'a, 'tcx> {
     fn visit_item(&mut self, i: &ast::Item, _: ()) {
         check_item_sized(self.ccx, i);
         visit::walk_item(self, i, ());
@@ -451,11 +443,11 @@ fn check_bare_fn(ccx: &CrateCtxt,
     }
 }
 
-struct GatherLocalsVisitor<'a> {
-    fcx: &'a FnCtxt<'a>
+struct GatherLocalsVisitor<'a, 'tcx: 'a> {
+    fcx: &'a FnCtxt<'a, 'tcx>
 }
 
-impl<'a> GatherLocalsVisitor<'a> {
+impl<'a, 'tcx> GatherLocalsVisitor<'a, 'tcx> {
     fn assign(&mut self, nid: ast::NodeId, ty_opt: Option<ty::t>) {
             match ty_opt {
                 None => {
@@ -472,7 +464,7 @@ impl<'a> GatherLocalsVisitor<'a> {
     }
 }
 
-impl<'a> Visitor<()> for GatherLocalsVisitor<'a> {
+impl<'a, 'tcx> Visitor<()> for GatherLocalsVisitor<'a, 'tcx> {
     // Add explicitly-declared locals.
     fn visit_local(&mut self, local: &ast::Local, _: ()) {
         let o_ty = match local.ty.node {
@@ -530,17 +522,15 @@ impl<'a> Visitor<()> for GatherLocalsVisitor<'a> {
 
 }
 
-fn check_fn<'a>(
-    ccx: &'a CrateCtxt<'a>,
-    fn_style: ast::FnStyle,
-    fn_style_id: ast::NodeId,
-    fn_sig: &ty::FnSig,
-    decl: &ast::FnDecl,
-    fn_id: ast::NodeId,
-    body: &ast::Block,
-    inherited: &'a Inherited<'a>)
-    -> FnCtxt<'a>
-{
+fn check_fn<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>,
+                      fn_style: ast::FnStyle,
+                      fn_style_id: ast::NodeId,
+                      fn_sig: &ty::FnSig,
+                      decl: &ast::FnDecl,
+                      fn_id: ast::NodeId,
+                      body: &ast::Block,
+                      inherited: &'a Inherited<'a, 'tcx>)
+                      -> FnCtxt<'a, 'tcx> {
     /*!
      * Helper used by check_bare_fn and check_expr_fn.  Does the
      * grungy work of checking a function body and returns the
@@ -1563,8 +1553,8 @@ fn check_cast(fcx: &FnCtxt,
     fcx.write_ty(id, t_1);
 }
 
-impl<'a> AstConv for FnCtxt<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.ccx.tcx }
+impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.ccx.tcx }
 
     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
         ty::lookup_item_type(self.tcx(), id)
@@ -1579,10 +1569,10 @@ impl<'a> AstConv for FnCtxt<'a> {
     }
 }
 
-impl<'a> FnCtxt<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.ccx.tcx }
+impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.ccx.tcx }
 
-    pub fn infcx<'b>(&'b self) -> &'b infer::InferCtxt<'a> {
+    pub fn infcx<'b>(&'b self) -> &'b infer::InferCtxt<'a, 'tcx> {
         &self.inh.infcx
     }
 
@@ -1590,7 +1580,7 @@ impl<'a> FnCtxt<'a> {
         self.ccx.tcx.sess.err_count() - self.err_count_on_creation
     }
 
-    pub fn vtable_context<'a>(&'a self) -> VtableContext<'a> {
+    pub fn vtable_context<'a>(&'a self) -> VtableContext<'a, 'tcx> {
         VtableContext {
             infcx: self.infcx(),
             param_env: &self.inh.param_env,
@@ -1599,7 +1589,7 @@ impl<'a> FnCtxt<'a> {
     }
 }
 
-impl<'a> RegionScope for infer::InferCtxt<'a> {
+impl<'a, 'tcx> RegionScope for infer::InferCtxt<'a, 'tcx> {
     fn default_region_bound(&self, span: Span) -> Option<ty::Region> {
         Some(self.next_region_var(infer::MiscVariable(span)))
     }
@@ -1612,7 +1602,7 @@ impl<'a> RegionScope for infer::InferCtxt<'a> {
     }
 }
 
-impl<'a> FnCtxt<'a> {
+impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     pub fn tag(&self) -> String {
         format!("{}", self as *const FnCtxt)
     }
@@ -3919,7 +3909,7 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
       }
       ast::ExprRepeat(ref element, ref count_expr) => {
         check_expr_has_type(fcx, &**count_expr, ty::mk_uint());
-        let count = ty::eval_repeat_count(fcx, &**count_expr);
+        let count = ty::eval_repeat_count(fcx.tcx(), &**count_expr);
 
         let uty = match expected {
             ExpectHasType(uty) => {
diff --git a/src/librustc/middle/typeck/check/regionck.rs b/src/librustc/middle/typeck/check/regionck.rs
index 16ecaa9714e..eb630d0fc7b 100644
--- a/src/librustc/middle/typeck/check/regionck.rs
+++ b/src/librustc/middle/typeck/check/regionck.rs
@@ -196,8 +196,8 @@ macro_rules! ignore_err(
     )
 )
 
-pub struct Rcx<'a> {
-    fcx: &'a FnCtxt<'a>,
+pub struct Rcx<'a, 'tcx: 'a> {
+    fcx: &'a FnCtxt<'a, 'tcx>,
 
     region_param_pairs: Vec<(ty::Region, ty::ParamTy)>,
 
@@ -250,15 +250,15 @@ fn region_of_def(fcx: &FnCtxt, def: def::Def) -> ty::Region {
     }
 }
 
-impl<'a> Rcx<'a> {
-    pub fn new(fcx: &'a FnCtxt<'a>,
-               initial_repeating_scope: ast::NodeId) -> Rcx<'a> {
+impl<'a, 'tcx> Rcx<'a, 'tcx> {
+    pub fn new(fcx: &'a FnCtxt<'a, 'tcx>,
+               initial_repeating_scope: ast::NodeId) -> Rcx<'a, 'tcx> {
         Rcx { fcx: fcx,
               repeating_scope: initial_repeating_scope,
               region_param_pairs: Vec::new() }
     }
 
-    pub fn tcx(&self) -> &'a ty::ctxt {
+    pub fn tcx(&self) -> &'a ty::ctxt<'tcx> {
         self.fcx.ccx.tcx
     }
 
@@ -438,8 +438,8 @@ impl<'a> Rcx<'a> {
     }
 }
 
-impl<'fcx> mc::Typer for Rcx<'fcx> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+impl<'fcx, 'tcx> mc::Typer<'tcx> for Rcx<'fcx, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         self.fcx.ccx.tcx
     }
 
@@ -479,7 +479,7 @@ impl<'fcx> mc::Typer for Rcx<'fcx> {
     }
 }
 
-impl<'a> Visitor<()> for Rcx<'a> {
+impl<'a, 'tcx> Visitor<()> for Rcx<'a, 'tcx> {
     // (..) FIXME(#3238) should use visit_pat, not visit_arm/visit_local,
     // However, right now we run into an issue whereby some free
     // regions are not properly related if they appear within the
diff --git a/src/librustc/middle/typeck/check/regionmanip.rs b/src/librustc/middle/typeck/check/regionmanip.rs
index 577da159162..60e502786ab 100644
--- a/src/librustc/middle/typeck/check/regionmanip.rs
+++ b/src/librustc/middle/typeck/check/regionmanip.rs
@@ -51,8 +51,8 @@ pub enum WfConstraint {
     RegionSubParamConstraint(Option<ty::t>, ty::Region, ty::ParamTy),
 }
 
-struct Wf<'a> {
-    tcx: &'a ty::ctxt,
+struct Wf<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     stack: Vec<(ty::Region, Option<ty::t>)>,
     out: Vec<WfConstraint>,
 }
@@ -78,7 +78,7 @@ pub fn region_wf_constraints(
     wf.out
 }
 
-impl<'a> Wf<'a> {
+impl<'a, 'tcx> Wf<'a, 'tcx> {
     fn accumulate_from_ty(&mut self, ty: ty::t) {
         debug!("Wf::accumulate_from_ty(ty={})",
                ty.repr(self.tcx));
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index da4bc4dbc76..16136fcf3e8 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -68,14 +68,14 @@ use syntax::visit::Visitor;
 
 /// A vtable context includes an inference context, a parameter environment,
 /// and a list of unboxed closure types.
-pub struct VtableContext<'a> {
-    pub infcx: &'a infer::InferCtxt<'a>,
+pub struct VtableContext<'a, 'tcx: 'a> {
+    pub infcx: &'a infer::InferCtxt<'a, 'tcx>,
     pub param_env: &'a ty::ParameterEnvironment,
     pub unboxed_closures: &'a RefCell<DefIdMap<ty::UnboxedClosure>>,
 }
 
-impl<'a> VtableContext<'a> {
-    pub fn tcx(&self) -> &'a ty::ctxt { self.infcx.tcx }
+impl<'a, 'tcx> VtableContext<'a, 'tcx> {
+    pub fn tcx(&self) -> &'a ty::ctxt<'tcx> { self.infcx.tcx }
 }
 
 fn lookup_vtables(vcx: &VtableContext,
@@ -1025,7 +1025,7 @@ pub fn trans_resolve_method(tcx: &ty::ctxt, id: ast::NodeId,
                    false)
 }
 
-impl<'a, 'b> visit::Visitor<()> for &'a FnCtxt<'b> {
+impl<'a, 'b, 'tcx> visit::Visitor<()> for &'a FnCtxt<'b, 'tcx> {
     fn visit_expr(&mut self, ex: &ast::Expr, _: ()) {
         early_resolve_expr(ex, *self, false);
         visit::walk_expr(self, ex, ());
diff --git a/src/librustc/middle/typeck/check/writeback.rs b/src/librustc/middle/typeck/check/writeback.rs
index 7951c8dfc19..d65172cc0c1 100644
--- a/src/librustc/middle/typeck/check/writeback.rs
+++ b/src/librustc/middle/typeck/check/writeback.rs
@@ -84,16 +84,16 @@ pub fn resolve_impl_res(infcx: &infer::InferCtxt,
 // there, it applies a few ad-hoc checks that were not convenient to
 // do elsewhere.
 
-struct WritebackCx<'cx> {
-    fcx: &'cx FnCtxt<'cx>,
+struct WritebackCx<'cx, 'tcx: 'cx> {
+    fcx: &'cx FnCtxt<'cx, 'tcx>,
 }
 
-impl<'cx> WritebackCx<'cx> {
-    fn new(fcx: &'cx FnCtxt) -> WritebackCx<'cx> {
+impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
+    fn new(fcx: &'cx FnCtxt<'cx, 'tcx>) -> WritebackCx<'cx, 'tcx> {
         WritebackCx { fcx: fcx }
     }
 
-    fn tcx(&self) -> &'cx ty::ctxt {
+    fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
         self.fcx.tcx()
     }
 }
@@ -106,7 +106,7 @@ impl<'cx> WritebackCx<'cx> {
 // below. In general, a function is made into a `visitor` if it must
 // traffic in node-ids or update tables in the type context etc.
 
-impl<'cx> Visitor<()> for WritebackCx<'cx> {
+impl<'cx, 'tcx> Visitor<()> for WritebackCx<'cx, 'tcx> {
     fn visit_item(&mut self, _: &ast::Item, _: ()) {
         // Ignore items
     }
@@ -192,7 +192,7 @@ impl<'cx> Visitor<()> for WritebackCx<'cx> {
     }
 }
 
-impl<'cx> WritebackCx<'cx> {
+impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
     fn visit_upvar_borrow_map(&self) {
         if self.fcx.writeback_errors.get() {
             return;
@@ -400,17 +400,17 @@ impl<T:TypeFoldable> ResolveIn for T {
 // The Resolver. This is the type folding engine that detects
 // unresolved types and so forth.
 
-struct Resolver<'cx> {
-    tcx: &'cx ty::ctxt,
-    infcx: &'cx infer::InferCtxt<'cx>,
+struct Resolver<'cx, 'tcx: 'cx> {
+    tcx: &'cx ty::ctxt<'tcx>,
+    infcx: &'cx infer::InferCtxt<'cx, 'tcx>,
     writeback_errors: &'cx Cell<bool>,
     reason: ResolveReason,
 }
 
-impl<'cx> Resolver<'cx> {
-    fn new(fcx: &'cx FnCtxt<'cx>,
+impl<'cx, 'tcx> Resolver<'cx, 'tcx> {
+    fn new(fcx: &'cx FnCtxt<'cx, 'tcx>,
            reason: ResolveReason)
-           -> Resolver<'cx>
+           -> Resolver<'cx, 'tcx>
     {
         Resolver { infcx: fcx.infcx(),
                    tcx: fcx.tcx(),
@@ -418,10 +418,10 @@ impl<'cx> Resolver<'cx> {
                    reason: reason }
     }
 
-    fn from_infcx(infcx: &'cx infer::InferCtxt<'cx>,
+    fn from_infcx(infcx: &'cx infer::InferCtxt<'cx, 'tcx>,
                   writeback_errors: &'cx Cell<bool>,
                   reason: ResolveReason)
-                  -> Resolver<'cx>
+                  -> Resolver<'cx, 'tcx>
     {
         Resolver { infcx: infcx,
                    tcx: infcx.tcx,
@@ -475,8 +475,8 @@ impl<'cx> Resolver<'cx> {
     }
 }
 
-impl<'cx> TypeFolder for Resolver<'cx> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+impl<'cx, 'tcx> TypeFolder<'tcx> for Resolver<'cx, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         self.tcx
     }
 
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index 9c58a4c79f0..2c6dc94f182 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -182,16 +182,16 @@ fn get_base_type_def_id(inference_context: &InferCtxt,
     }
 }
 
-struct CoherenceChecker<'a> {
-    crate_context: &'a CrateCtxt<'a>,
-    inference_context: InferCtxt<'a>,
+struct CoherenceChecker<'a, 'tcx: 'a> {
+    crate_context: &'a CrateCtxt<'a, 'tcx>,
+    inference_context: InferCtxt<'a, 'tcx>,
 }
 
-struct CoherenceCheckVisitor<'a> {
-    cc: &'a CoherenceChecker<'a>
+struct CoherenceCheckVisitor<'a, 'tcx: 'a> {
+    cc: &'a CoherenceChecker<'a, 'tcx>
 }
 
-impl<'a> visit::Visitor<()> for CoherenceCheckVisitor<'a> {
+impl<'a, 'tcx> visit::Visitor<()> for CoherenceCheckVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &Item, _: ()) {
 
         //debug!("(checking coherence) item '{}'", token::get_ident(item.ident));
@@ -214,9 +214,11 @@ impl<'a> visit::Visitor<()> for CoherenceCheckVisitor<'a> {
     }
 }
 
-struct PrivilegedScopeVisitor<'a> { cc: &'a CoherenceChecker<'a> }
+struct PrivilegedScopeVisitor<'a, 'tcx: 'a> {
+    cc: &'a CoherenceChecker<'a, 'tcx>
+}
 
-impl<'a> visit::Visitor<()> for PrivilegedScopeVisitor<'a> {
+impl<'a, 'tcx> visit::Visitor<()> for PrivilegedScopeVisitor<'a, 'tcx> {
     fn visit_item(&mut self, item: &Item, _: ()) {
 
         match item.node {
@@ -263,7 +265,7 @@ impl<'a> visit::Visitor<()> for PrivilegedScopeVisitor<'a> {
     }
 }
 
-impl<'a> CoherenceChecker<'a> {
+impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
     fn check(&self, krate: &Crate) {
         // Check implementations and traits. This populates the tables
         // containing the inherent methods and extension methods. It also
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index c22baa1d9e5..742d22cc379 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -95,11 +95,11 @@ pub fn collect_item_types(ccx: &CrateCtxt, krate: &ast::Crate) {
 // of type parameters and supertraits. This is information we need to
 // know later when parsing field defs.
 
-struct CollectTraitDefVisitor<'a> {
-    ccx: &'a CrateCtxt<'a>
+struct CollectTraitDefVisitor<'a, 'tcx: 'a> {
+    ccx: &'a CrateCtxt<'a, 'tcx>
 }
 
-impl<'a> visit::Visitor<()> for CollectTraitDefVisitor<'a> {
+impl<'a, 'tcx> visit::Visitor<()> for CollectTraitDefVisitor<'a, 'tcx> {
     fn visit_item(&mut self, i: &ast::Item, _: ()) {
         match i.node {
             ast::ItemTrait(..) => {
@@ -116,11 +116,11 @@ impl<'a> visit::Visitor<()> for CollectTraitDefVisitor<'a> {
 ///////////////////////////////////////////////////////////////////////////
 // Second phase: collection proper.
 
-struct CollectItemTypesVisitor<'a> {
-    ccx: &'a CrateCtxt<'a>
+struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
+    ccx: &'a CrateCtxt<'a, 'tcx>
 }
 
-impl<'a> visit::Visitor<()> for CollectItemTypesVisitor<'a> {
+impl<'a, 'tcx> visit::Visitor<()> for CollectItemTypesVisitor<'a, 'tcx> {
     fn visit_item(&mut self, i: &ast::Item, _: ()) {
         convert(self.ccx, i);
         visit::walk_item(self, i, ());
@@ -138,14 +138,14 @@ pub trait ToTy {
     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t;
 }
 
-impl<'a> ToTy for CrateCtxt<'a> {
+impl<'a, 'tcx> ToTy for CrateCtxt<'a, 'tcx> {
     fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> ty::t {
         ast_ty_to_ty(self, rs, ast_ty)
     }
 }
 
-impl<'a> AstConv for CrateCtxt<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt { self.tcx }
+impl<'a, 'tcx> AstConv<'tcx> for CrateCtxt<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 
     fn get_item_ty(&self, id: ast::DefId) -> ty::Polytype {
         if id.krate != ast::LOCAL_CRATE {
diff --git a/src/librustc/middle/typeck/infer/coercion.rs b/src/librustc/middle/typeck/infer/coercion.rs
index 7763a992c8f..44141f25418 100644
--- a/src/librustc/middle/typeck/infer/coercion.rs
+++ b/src/librustc/middle/typeck/infer/coercion.rs
@@ -82,10 +82,10 @@ use syntax::ast;
 // Note: Coerce is not actually a combiner, in that it does not
 // conform to the same interface, though it performs a similar
 // function.
-pub struct Coerce<'f>(pub CombineFields<'f>);
+pub struct Coerce<'f, 'tcx: 'f>(pub CombineFields<'f, 'tcx>);
 
-impl<'f> Coerce<'f> {
-    pub fn get_ref<'a>(&'a self) -> &'a CombineFields<'f> {
+impl<'f, 'tcx> Coerce<'f, 'tcx> {
+    pub fn get_ref<'a>(&'a self) -> &'a CombineFields<'f, 'tcx> {
         let Coerce(ref v) = *self; v
     }
 
diff --git a/src/librustc/middle/typeck/infer/combine.rs b/src/librustc/middle/typeck/infer/combine.rs
index 2a44ef9de2b..66caf10cb40 100644
--- a/src/librustc/middle/typeck/infer/combine.rs
+++ b/src/librustc/middle/typeck/infer/combine.rs
@@ -57,16 +57,16 @@ use syntax::ast::{Onceness, FnStyle};
 use syntax::ast;
 use syntax::abi;
 
-pub trait Combine {
-    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a>;
+pub trait Combine<'tcx> {
+    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx>;
     fn tag(&self) -> String;
     fn a_is_expected(&self) -> bool;
     fn trace(&self) -> TypeTrace;
 
-    fn equate<'a>(&'a self) -> Equate<'a>;
-    fn sub<'a>(&'a self) -> Sub<'a>;
-    fn lub<'a>(&'a self) -> Lub<'a>;
-    fn glb<'a>(&'a self) -> Glb<'a>;
+    fn equate<'a>(&'a self) -> Equate<'a, 'tcx>;
+    fn sub<'a>(&'a self) -> Sub<'a, 'tcx>;
+    fn lub<'a>(&'a self) -> Lub<'a, 'tcx>;
+    fn glb<'a>(&'a self) -> Glb<'a, 'tcx>;
 
     fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt>;
     fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t>;
@@ -138,13 +138,12 @@ pub trait Combine {
 
         return Ok(substs);
 
-        fn relate_region_params<C:Combine>(this: &C,
-                                           item_def_id: ast::DefId,
-                                           variances: &[ty::Variance],
-                                           a_rs: &[ty::Region],
-                                           b_rs: &[ty::Region])
-                                           -> cres<Vec<ty::Region>>
-        {
+        fn relate_region_params<'tcx, C: Combine<'tcx>>(this: &C,
+                                                        item_def_id: ast::DefId,
+                                                        variances: &[ty::Variance],
+                                                        a_rs: &[ty::Region],
+                                                        b_rs: &[ty::Region])
+                                                        -> cres<Vec<ty::Region>> {
             let tcx = this.infcx().tcx;
             let num_region_params = variances.len();
 
@@ -305,13 +304,13 @@ pub trait Combine {
 }
 
 #[deriving(Clone)]
-pub struct CombineFields<'a> {
-    pub infcx: &'a InferCtxt<'a>,
+pub struct CombineFields<'a, 'tcx: 'a> {
+    pub infcx: &'a InferCtxt<'a, 'tcx>,
     pub a_is_expected: bool,
     pub trace: TypeTrace,
 }
 
-pub fn expected_found<C:Combine,T>(
+pub fn expected_found<'tcx, C: Combine<'tcx>, T>(
         this: &C, a: T, b: T) -> ty::expected_found<T> {
     if this.a_is_expected() {
         ty::expected_found {expected: a, found: b}
@@ -320,9 +319,15 @@ pub fn expected_found<C:Combine,T>(
     }
 }
 
-pub fn super_fn_sigs<C:Combine>(this: &C, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig> {
+pub fn super_fn_sigs<'tcx, C: Combine<'tcx>>(this: &C,
+                                             a: &ty::FnSig,
+                                             b: &ty::FnSig)
+                                             -> cres<ty::FnSig> {
 
-    fn argvecs<C:Combine>(this: &C, a_args: &[ty::t], b_args: &[ty::t]) -> cres<Vec<ty::t> > {
+    fn argvecs<'tcx, C: Combine<'tcx>>(this: &C,
+                                       a_args: &[ty::t],
+                                       b_args: &[ty::t])
+                                       -> cres<Vec<ty::t>> {
         if a_args.len() == b_args.len() {
             result::collect(a_args.iter().zip(b_args.iter())
                             .map(|(a, b)| this.args(*a, *b)))
@@ -345,18 +350,18 @@ pub fn super_fn_sigs<C:Combine>(this: &C, a: &ty::FnSig, b: &ty::FnSig) -> cres<
               variadic: a.variadic})
 }
 
-pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
+pub fn super_tys<'tcx, C: Combine<'tcx>>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
 
     // This is a horrible hack - historically, [T] was not treated as a type,
     // so, for example, &T and &[U] should not unify. In fact the only thing
     // &[U] should unify with is &[T]. We preserve that behaviour with this
     // check.
-    fn check_ptr_to_unsized<C:Combine>(this: &C,
-                                       a: ty::t,
-                                       b: ty::t,
-                                       a_inner: ty::t,
-                                       b_inner: ty::t,
-                                       result: ty::t) -> cres<ty::t> {
+    fn check_ptr_to_unsized<'tcx, C: Combine<'tcx>>(this: &C,
+                                                    a: ty::t,
+                                                    b: ty::t,
+                                                    a_inner: ty::t,
+                                                    b_inner: ty::t,
+                                                    result: ty::t) -> cres<ty::t> {
         match (&ty::get(a_inner).sty, &ty::get(b_inner).sty) {
             (&ty::ty_vec(_, None), &ty::ty_vec(_, None)) |
             (&ty::ty_str, &ty::ty_str) |
@@ -547,7 +552,7 @@ pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
       _ => Err(ty::terr_sorts(expected_found(this, a, b)))
     };
 
-    fn unify_integral_variable<C:Combine>(
+    fn unify_integral_variable<'tcx, C: Combine<'tcx>>(
         this: &C,
         vid_is_expected: bool,
         vid: ty::IntVid,
@@ -560,7 +565,7 @@ pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
         }
     }
 
-    fn unify_float_variable<C:Combine>(
+    fn unify_float_variable<'tcx, C: Combine<'tcx>>(
         this: &C,
         vid_is_expected: bool,
         vid: ty::FloatVid,
@@ -571,19 +576,19 @@ pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
     }
 }
 
-impl<'f> CombineFields<'f> {
-    pub fn switch_expected(&self) -> CombineFields<'f> {
+impl<'f, 'tcx> CombineFields<'f, 'tcx> {
+    pub fn switch_expected(&self) -> CombineFields<'f, 'tcx> {
         CombineFields {
             a_is_expected: !self.a_is_expected,
             ..(*self).clone()
         }
     }
 
-    fn equate(&self) -> Equate<'f> {
+    fn equate(&self) -> Equate<'f, 'tcx> {
         Equate((*self).clone())
     }
 
-    fn sub(&self) -> Sub<'f> {
+    fn sub(&self) -> Sub<'f, 'tcx> {
         Sub((*self).clone())
     }
 
diff --git a/src/librustc/middle/typeck/infer/equate.rs b/src/librustc/middle/typeck/infer/equate.rs
index 223d37ee1ea..fd4a5927362 100644
--- a/src/librustc/middle/typeck/infer/equate.rs
+++ b/src/librustc/middle/typeck/infer/equate.rs
@@ -23,25 +23,25 @@ use util::ppaux::{Repr};
 
 use syntax::ast::{Onceness, FnStyle};
 
-pub struct Equate<'f> {
-    fields: CombineFields<'f>
+pub struct Equate<'f, 'tcx: 'f> {
+    fields: CombineFields<'f, 'tcx>
 }
 
 #[allow(non_snake_case)]
-pub fn Equate<'f>(cf: CombineFields<'f>) -> Equate<'f> {
+pub fn Equate<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Equate<'f, 'tcx> {
     Equate { fields: cf }
 }
 
-impl<'f> Combine for Equate<'f> {
-    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a> { self.fields.infcx }
+impl<'f, 'tcx> Combine<'tcx> for Equate<'f, 'tcx> {
+    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx> { self.fields.infcx }
     fn tag(&self) -> String { "eq".to_string() }
     fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
     fn trace(&self) -> TypeTrace { self.fields.trace.clone() }
 
-    fn equate<'a>(&'a self) -> Equate<'a> { Equate(self.fields.clone()) }
-    fn sub<'a>(&'a self) -> Sub<'a> { Sub(self.fields.clone()) }
-    fn lub<'a>(&'a self) -> Lub<'a> { Lub(self.fields.clone()) }
-    fn glb<'a>(&'a self) -> Glb<'a> { Glb(self.fields.clone()) }
+    fn equate<'a>(&'a self) -> Equate<'a, 'tcx> { Equate(self.fields.clone()) }
+    fn sub<'a>(&'a self) -> Sub<'a, 'tcx> { Sub(self.fields.clone()) }
+    fn lub<'a>(&'a self) -> Lub<'a, 'tcx> { Lub(self.fields.clone()) }
+    fn glb<'a>(&'a self) -> Glb<'a, 'tcx> { Glb(self.fields.clone()) }
 
     fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
         self.tys(a, b)
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index bd355d2f580..e602e6a7b3c 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -166,7 +166,7 @@ trait ErrorReportingHelpers {
                                 span: codemap::Span);
 }
 
-impl<'a> ErrorReporting for InferCtxt<'a> {
+impl<'a, 'tcx> ErrorReporting for InferCtxt<'a, 'tcx> {
     fn report_region_errors(&self,
                             errors: &Vec<RegionResolutionError>) {
         let p_errors = self.process_errors(errors);
@@ -900,8 +900,8 @@ struct RebuildPathInfo<'a> {
     region_names: &'a HashSet<ast::Name>
 }
 
-struct Rebuilder<'a> {
-    tcx: &'a ty::ctxt,
+struct Rebuilder<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     fn_decl: ast::P<ast::FnDecl>,
     expl_self_opt: Option<ast::ExplicitSelf_>,
     generics: &'a ast::Generics,
@@ -916,14 +916,14 @@ enum FreshOrKept {
     Kept
 }
 
-impl<'a> Rebuilder<'a> {
-    fn new(tcx: &'a ty::ctxt,
+impl<'a, 'tcx> Rebuilder<'a, 'tcx> {
+    fn new(tcx: &'a ty::ctxt<'tcx>,
            fn_decl: ast::P<ast::FnDecl>,
            expl_self_opt: Option<ast::ExplicitSelf_>,
            generics: &'a ast::Generics,
            same_regions: &'a [SameRegions],
            life_giver: &'a LifeGiver)
-           -> Rebuilder<'a> {
+           -> Rebuilder<'a, 'tcx> {
         Rebuilder {
             tcx: tcx,
             fn_decl: fn_decl,
@@ -1403,7 +1403,7 @@ impl<'a> Rebuilder<'a> {
     }
 }
 
-impl<'a> ErrorReportingHelpers for InferCtxt<'a> {
+impl<'a, 'tcx> ErrorReportingHelpers for InferCtxt<'a, 'tcx> {
     fn give_expl_lifetime_param(&self,
                                 decl: &ast::FnDecl,
                                 fn_style: ast::FnStyle,
diff --git a/src/librustc/middle/typeck/infer/glb.rs b/src/librustc/middle/typeck/infer/glb.rs
index 8ae141ea19c..08d4f9f3a86 100644
--- a/src/librustc/middle/typeck/infer/glb.rs
+++ b/src/librustc/middle/typeck/infer/glb.rs
@@ -30,25 +30,25 @@ use util::ppaux::mt_to_string;
 use util::ppaux::Repr;
 
 /// "Greatest lower bound" (common subtype)
-pub struct Glb<'f> {
-    fields: CombineFields<'f>
+pub struct Glb<'f, 'tcx: 'f> {
+    fields: CombineFields<'f, 'tcx>
 }
 
 #[allow(non_snake_case)]
-pub fn Glb<'f>(cf: CombineFields<'f>) -> Glb<'f> {
+pub fn Glb<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Glb<'f, 'tcx> {
     Glb { fields: cf }
 }
 
-impl<'f> Combine for Glb<'f> {
-    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a> { self.fields.infcx }
+impl<'f, 'tcx> Combine<'tcx> for Glb<'f, 'tcx> {
+    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx> { self.fields.infcx }
     fn tag(&self) -> String { "glb".to_string() }
     fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
     fn trace(&self) -> TypeTrace { self.fields.trace.clone() }
 
-    fn equate<'a>(&'a self) -> Equate<'a> { Equate(self.fields.clone()) }
-    fn sub<'a>(&'a self) -> Sub<'a> { Sub(self.fields.clone()) }
-    fn lub<'a>(&'a self) -> Lub<'a> { Lub(self.fields.clone()) }
-    fn glb<'a>(&'a self) -> Glb<'a> { Glb(self.fields.clone()) }
+    fn equate<'a>(&'a self) -> Equate<'a, 'tcx> { Equate(self.fields.clone()) }
+    fn sub<'a>(&'a self) -> Sub<'a, 'tcx> { Sub(self.fields.clone()) }
+    fn lub<'a>(&'a self) -> Lub<'a, 'tcx> { Lub(self.fields.clone()) }
+    fn glb<'a>(&'a self) -> Glb<'a, 'tcx> { Glb(self.fields.clone()) }
 
     fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt> {
         let tcx = self.fields.infcx.tcx;
diff --git a/src/librustc/middle/typeck/infer/lattice.rs b/src/librustc/middle/typeck/infer/lattice.rs
index f09773d30b5..6095e5b0504 100644
--- a/src/librustc/middle/typeck/infer/lattice.rs
+++ b/src/librustc/middle/typeck/infer/lattice.rs
@@ -51,7 +51,7 @@ pub trait LatticeDir {
     fn relate_bound<'a>(&'a self, v: ty::t, a: ty::t, b: ty::t) -> cres<()>;
 }
 
-impl<'a> LatticeDir for Lub<'a> {
+impl<'a, 'tcx> LatticeDir for Lub<'a, 'tcx> {
     fn ty_bot(&self, t: ty::t) -> cres<ty::t> {
         Ok(t)
     }
@@ -64,7 +64,7 @@ impl<'a> LatticeDir for Lub<'a> {
     }
 }
 
-impl<'a> LatticeDir for Glb<'a> {
+impl<'a, 'tcx> LatticeDir for Glb<'a, 'tcx> {
     fn ty_bot(&self, _: ty::t) -> cres<ty::t> {
         Ok(ty::mk_bot())
     }
@@ -77,10 +77,10 @@ impl<'a> LatticeDir for Glb<'a> {
     }
 }
 
-pub fn super_lattice_tys<L:LatticeDir+Combine>(this: &L,
-                                               a: ty::t,
-                                               b: ty::t)
-                                               -> cres<ty::t>
+pub fn super_lattice_tys<'tcx, L:LatticeDir+Combine<'tcx>>(this: &L,
+                                                           a: ty::t,
+                                                           b: ty::t)
+                                                           -> cres<ty::t>
 {
     debug!("{}.lattice_tys({}, {})",
            this.tag(),
@@ -115,9 +115,9 @@ pub fn super_lattice_tys<L:LatticeDir+Combine>(this: &L,
 // Random utility functions used by LUB/GLB when computing LUB/GLB of
 // fn types
 
-pub fn var_ids<T:Combine>(this: &T,
-                          map: &HashMap<ty::BoundRegion, ty::Region>)
-                          -> Vec<RegionVid> {
+pub fn var_ids<'tcx, T: Combine<'tcx>>(this: &T,
+                                       map: &HashMap<ty::BoundRegion, ty::Region>)
+                                       -> Vec<RegionVid> {
     map.iter().map(|(_, r)| match *r {
             ty::ReInfer(ty::ReVar(r)) => { r }
             r => {
diff --git a/src/librustc/middle/typeck/infer/lub.rs b/src/librustc/middle/typeck/infer/lub.rs
index 49760ac92bf..276a2264837 100644
--- a/src/librustc/middle/typeck/infer/lub.rs
+++ b/src/librustc/middle/typeck/infer/lub.rs
@@ -29,25 +29,25 @@ use util::ppaux::mt_to_string;
 use util::ppaux::Repr;
 
 /// "Least upper bound" (common supertype)
-pub struct Lub<'f> {
-    fields: CombineFields<'f>
+pub struct Lub<'f, 'tcx: 'f> {
+    fields: CombineFields<'f, 'tcx>
 }
 
 #[allow(non_snake_case)]
-pub fn Lub<'f>(cf: CombineFields<'f>) -> Lub<'f> {
+pub fn Lub<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Lub<'f, 'tcx> {
     Lub { fields: cf }
 }
 
-impl<'f> Combine for Lub<'f> {
-    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a> { self.fields.infcx }
+impl<'f, 'tcx> Combine<'tcx> for Lub<'f, 'tcx> {
+    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx> { self.fields.infcx }
     fn tag(&self) -> String { "lub".to_string() }
     fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
     fn trace(&self) -> TypeTrace { self.fields.trace.clone() }
 
-    fn equate<'a>(&'a self) -> Equate<'a> { Equate(self.fields.clone()) }
-    fn sub<'a>(&'a self) -> Sub<'a> { Sub(self.fields.clone()) }
-    fn lub<'a>(&'a self) -> Lub<'a> { Lub(self.fields.clone()) }
-    fn glb<'a>(&'a self) -> Glb<'a> { Glb(self.fields.clone()) }
+    fn equate<'a>(&'a self) -> Equate<'a, 'tcx> { Equate(self.fields.clone()) }
+    fn sub<'a>(&'a self) -> Sub<'a, 'tcx> { Sub(self.fields.clone()) }
+    fn lub<'a>(&'a self) -> Lub<'a, 'tcx> { Lub(self.fields.clone()) }
+    fn glb<'a>(&'a self) -> Glb<'a, 'tcx> { Glb(self.fields.clone()) }
 
     fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt> {
         let tcx = self.fields.infcx.tcx;
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index f86857f97f6..44ee7ba2de6 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -75,8 +75,8 @@ pub type ures = cres<()>; // "unify result"
 pub type fres<T> = Result<T, fixup_err>; // "fixup result"
 pub type CoerceResult = cres<Option<ty::AutoAdjustment>>;
 
-pub struct InferCtxt<'a> {
-    pub tcx: &'a ty::ctxt,
+pub struct InferCtxt<'a, 'tcx: 'a> {
+    pub tcx: &'a ty::ctxt<'tcx>,
 
     // We instantiate UnificationTable with bounds<ty::t> because the
     // types that might instantiate a general type variable have an
@@ -93,7 +93,7 @@ pub struct InferCtxt<'a> {
 
     // For region variables.
     region_vars:
-        RegionVarBindings<'a>,
+        RegionVarBindings<'a, 'tcx>,
 }
 
 /// Why did we require that the two types be related?
@@ -291,7 +291,8 @@ pub fn fixup_err_to_string(f: fixup_err) -> String {
     }
 }
 
-pub fn new_infer_ctxt<'a>(tcx: &'a ty::ctxt) -> InferCtxt<'a> {
+pub fn new_infer_ctxt<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>)
+                                -> InferCtxt<'a, 'tcx> {
     InferCtxt {
         tcx: tcx,
         type_variables: RefCell::new(type_variable::TypeVariableTable::new()),
@@ -518,23 +519,23 @@ pub struct CombinedSnapshot {
     region_vars_snapshot: RegionSnapshot,
 }
 
-impl<'a> InferCtxt<'a> {
+impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
     pub fn combine_fields<'a>(&'a self, a_is_expected: bool, trace: TypeTrace)
-                              -> CombineFields<'a> {
+                              -> CombineFields<'a, 'tcx> {
         CombineFields {infcx: self,
                        a_is_expected: a_is_expected,
                        trace: trace}
     }
 
-    pub fn equate<'a>(&'a self, a_is_expected: bool, trace: TypeTrace) -> Equate<'a> {
+    pub fn equate<'a>(&'a self, a_is_expected: bool, trace: TypeTrace) -> Equate<'a, 'tcx> {
         Equate(self.combine_fields(a_is_expected, trace))
     }
 
-    pub fn sub<'a>(&'a self, a_is_expected: bool, trace: TypeTrace) -> Sub<'a> {
+    pub fn sub<'a>(&'a self, a_is_expected: bool, trace: TypeTrace) -> Sub<'a, 'tcx> {
         Sub(self.combine_fields(a_is_expected, trace))
     }
 
-    pub fn lub<'a>(&'a self, a_is_expected: bool, trace: TypeTrace) -> Lub<'a> {
+    pub fn lub<'a>(&'a self, a_is_expected: bool, trace: TypeTrace) -> Lub<'a, 'tcx> {
         Lub(self.combine_fields(a_is_expected, trace))
     }
 
@@ -635,7 +636,7 @@ impl<'a> InferCtxt<'a> {
     }
 }
 
-impl<'a> InferCtxt<'a> {
+impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
     pub fn next_ty_var_id(&self) -> TyVid {
         self.type_variables
             .borrow_mut()
diff --git a/src/librustc/middle/typeck/infer/region_inference/mod.rs b/src/librustc/middle/typeck/infer/region_inference/mod.rs
index f34894346f6..7e61c254a65 100644
--- a/src/librustc/middle/typeck/infer/region_inference/mod.rs
+++ b/src/librustc/middle/typeck/infer/region_inference/mod.rs
@@ -151,8 +151,8 @@ impl SameRegions {
 
 pub type CombineMap = HashMap<TwoRegions, RegionVid>;
 
-pub struct RegionVarBindings<'a> {
-    tcx: &'a ty::ctxt,
+pub struct RegionVarBindings<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     var_origins: RefCell<Vec<RegionVariableOrigin>>,
 
     // Constraints of the form `A <= B` introduced by the region
@@ -217,8 +217,8 @@ pub struct RegionMark {
     length: uint
 }
 
-impl<'a> RegionVarBindings<'a> {
-    pub fn new(tcx: &'a ty::ctxt) -> RegionVarBindings<'a> {
+impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
+    pub fn new(tcx: &'a ty::ctxt<'tcx>) -> RegionVarBindings<'a, 'tcx> {
         RegionVarBindings {
             tcx: tcx,
             var_origins: RefCell::new(Vec::new()),
@@ -711,9 +711,7 @@ impl<'a> RegionVarBindings<'a> {
         *self.values.borrow_mut() = Some(v);
         errors
     }
-}
 
-impl<'a> RegionVarBindings<'a> {
     fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
         self.tcx.region_maps.is_subregion_of(sub, sup)
     }
@@ -959,7 +957,7 @@ struct RegionAndOrigin {
 
 type RegionGraph = graph::Graph<(), Constraint>;
 
-impl<'a> RegionVarBindings<'a> {
+impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     fn infer_variable_values(&self,
                              errors: &mut Vec<RegionResolutionError>)
                              -> Vec<VarValue>
diff --git a/src/librustc/middle/typeck/infer/resolve.rs b/src/librustc/middle/typeck/infer/resolve.rs
index f9742c522da..dcdae7ed29c 100644
--- a/src/librustc/middle/typeck/infer/resolve.rs
+++ b/src/librustc/middle/typeck/infer/resolve.rs
@@ -74,18 +74,18 @@ pub static try_resolve_tvar_shallow: uint = 0;
 pub static resolve_and_force_all_but_regions: uint =
     (resolve_all | force_all) & not_regions;
 
-pub struct ResolveState<'a> {
-    infcx: &'a InferCtxt<'a>,
+pub struct ResolveState<'a, 'tcx: 'a> {
+    infcx: &'a InferCtxt<'a, 'tcx>,
     modes: uint,
     err: Option<fixup_err>,
     v_seen: Vec<TyVid> ,
     type_depth: uint,
 }
 
-pub fn resolver<'a>(infcx: &'a InferCtxt,
-                    modes: uint,
-                    _: Option<Span>)
-                    -> ResolveState<'a> {
+pub fn resolver<'a, 'tcx>(infcx: &'a InferCtxt<'a, 'tcx>,
+                          modes: uint,
+                          _: Option<Span>)
+                          -> ResolveState<'a, 'tcx> {
     ResolveState {
         infcx: infcx,
         modes: modes,
@@ -95,8 +95,8 @@ pub fn resolver<'a>(infcx: &'a InferCtxt,
     }
 }
 
-impl<'a> ty_fold::TypeFolder for ResolveState<'a> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt {
+impl<'a, 'tcx> ty_fold::TypeFolder<'tcx> for ResolveState<'a, 'tcx> {
+    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
         self.infcx.tcx
     }
 
@@ -109,7 +109,7 @@ impl<'a> ty_fold::TypeFolder for ResolveState<'a> {
     }
 }
 
-impl<'a> ResolveState<'a> {
+impl<'a, 'tcx> ResolveState<'a, 'tcx> {
     pub fn should(&mut self, mode: uint) -> bool {
         (self.modes & mode) == mode
     }
diff --git a/src/librustc/middle/typeck/infer/sub.rs b/src/librustc/middle/typeck/infer/sub.rs
index be4abb1ad82..7403d50a210 100644
--- a/src/librustc/middle/typeck/infer/sub.rs
+++ b/src/librustc/middle/typeck/infer/sub.rs
@@ -28,25 +28,25 @@ use syntax::ast::{Onceness, FnStyle, MutImmutable, MutMutable};
 
 
 /// "Greatest lower bound" (common subtype)
-pub struct Sub<'f> {
-    fields: CombineFields<'f>
+pub struct Sub<'f, 'tcx: 'f> {
+    fields: CombineFields<'f, 'tcx>
 }
 
 #[allow(non_snake_case)]
-pub fn Sub<'f>(cf: CombineFields<'f>) -> Sub<'f> {
+pub fn Sub<'f, 'tcx>(cf: CombineFields<'f, 'tcx>) -> Sub<'f, 'tcx> {
     Sub { fields: cf }
 }
 
-impl<'f> Combine for Sub<'f> {
-    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a> { self.fields.infcx }
+impl<'f, 'tcx> Combine<'tcx> for Sub<'f, 'tcx> {
+    fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx> { self.fields.infcx }
     fn tag(&self) -> String { "sub".to_string() }
     fn a_is_expected(&self) -> bool { self.fields.a_is_expected }
     fn trace(&self) -> TypeTrace { self.fields.trace.clone() }
 
-    fn equate<'a>(&'a self) -> Equate<'a> { Equate(self.fields.clone()) }
-    fn sub<'a>(&'a self) -> Sub<'a> { Sub(self.fields.clone()) }
-    fn lub<'a>(&'a self) -> Lub<'a> { Lub(self.fields.clone()) }
-    fn glb<'a>(&'a self) -> Glb<'a> { Glb(self.fields.clone()) }
+    fn equate<'a>(&'a self) -> Equate<'a, 'tcx> { Equate(self.fields.clone()) }
+    fn sub<'a>(&'a self) -> Sub<'a, 'tcx> { Sub(self.fields.clone()) }
+    fn lub<'a>(&'a self) -> Lub<'a, 'tcx> { Lub(self.fields.clone()) }
+    fn glb<'a>(&'a self) -> Glb<'a, 'tcx> { Glb(self.fields.clone()) }
 
     fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
         Sub(self.fields.switch_expected()).tys(b, a)
diff --git a/src/librustc/middle/typeck/infer/test.rs b/src/librustc/middle/typeck/infer/test.rs
index dd00fc62079..198857fca50 100644
--- a/src/librustc/middle/typeck/infer/test.rs
+++ b/src/librustc/middle/typeck/infer/test.rs
@@ -39,10 +39,11 @@ use syntax::diagnostic::{Level, RenderSpan, Bug, Fatal, Error, Warning, Note};
 use syntax::ast;
 use util::ppaux::{ty_to_string, UserString};
 
-struct Env<'a> {
+use arena::TypedArena;
+
+struct Env<'a, 'tcx: 'a> {
     krate: ast::Crate,
-    tcx: &'a ty::ctxt,
-    infcx: &'a infer::InferCtxt<'a>,
+    infcx: &'a infer::InferCtxt<'a, 'tcx>,
 }
 
 struct RH<'a> {
@@ -129,7 +130,9 @@ fn test_env(_test_name: &str,
     let named_region_map = resolve_lifetime::krate(&sess, &krate);
     let region_map = region::resolve_crate(&sess, &krate);
     let stability_index = stability::Index::build(&krate);
+    let type_arena = TypedArena::new();
     let tcx = ty::mk_ctxt(sess,
+                          &type_arena,
                           def_map,
                           named_region_map,
                           ast_map,
@@ -139,19 +142,20 @@ fn test_env(_test_name: &str,
                           lang_items,
                           stability_index);
     let infcx = infer::new_infer_ctxt(&tcx);
-    let env = Env {krate: krate,
-                   tcx: &tcx,
-                   infcx: &infcx};
+    let env = Env {
+        krate: krate,
+        infcx: &infcx
+    };
     body(env);
     infcx.resolve_regions_and_report_errors();
     assert_eq!(tcx.sess.err_count(), expected_err_count);
 }
 
-impl<'a> Env<'a> {
+impl<'a, 'tcx> Env<'a, 'tcx> {
     pub fn create_region_hierarchy(&self, rh: &RH) {
         for child_rh in rh.sub.iter() {
             self.create_region_hierarchy(child_rh);
-            self.tcx.region_maps.record_encl_scope(child_rh.id, rh.id);
+            self.infcx.tcx.region_maps.record_encl_scope(child_rh.id, rh.id);
         }
     }
 
@@ -181,7 +185,7 @@ impl<'a> Env<'a> {
                       -> Option<ast::NodeId> {
             assert!(idx < names.len());
             for item in m.items.iter() {
-                if item.ident.user_string(this.tcx) == names[idx] {
+                if item.ident.user_string(this.infcx.tcx) == names[idx] {
                     return search(this, &**item, idx+1, names);
                 }
             }
@@ -220,7 +224,7 @@ impl<'a> Env<'a> {
         match infer::mk_subty(self.infcx, true, infer::Misc(DUMMY_SP), a, b) {
             Ok(_) => true,
             Err(ref e) => fail!("Encountered error: {}",
-                                ty::type_err_to_str(self.tcx, e))
+                                ty::type_err_to_str(self.infcx.tcx, e))
         }
     }
 
@@ -253,7 +257,7 @@ impl<'a> Env<'a> {
     }
 
     pub fn ty_to_string(&self, a: ty::t) -> String {
-        ty_to_string(self.tcx, a)
+        ty_to_string(self.infcx.tcx, a)
     }
 
     pub fn t_fn(&self,
@@ -262,7 +266,7 @@ impl<'a> Env<'a> {
                 output_ty: ty::t)
                 -> ty::t
     {
-        ty::mk_ctor_fn(self.tcx, binder_id, input_tys, output_ty)
+        ty::mk_ctor_fn(self.infcx.tcx, binder_id, input_tys, output_ty)
     }
 
     pub fn t_int(&self) -> ty::t {
@@ -270,23 +274,23 @@ impl<'a> Env<'a> {
     }
 
     pub fn t_rptr_late_bound(&self, binder_id: ast::NodeId, id: uint) -> ty::t {
-        ty::mk_imm_rptr(self.tcx, ty::ReLateBound(binder_id, ty::BrAnon(id)),
+        ty::mk_imm_rptr(self.infcx.tcx, ty::ReLateBound(binder_id, ty::BrAnon(id)),
                         self.t_int())
     }
 
     pub fn t_rptr_scope(&self, id: ast::NodeId) -> ty::t {
-        ty::mk_imm_rptr(self.tcx, ty::ReScope(id), self.t_int())
+        ty::mk_imm_rptr(self.infcx.tcx, ty::ReScope(id), self.t_int())
     }
 
     pub fn t_rptr_free(&self, nid: ast::NodeId, id: uint) -> ty::t {
-        ty::mk_imm_rptr(self.tcx,
+        ty::mk_imm_rptr(self.infcx.tcx,
                         ty::ReFree(ty::FreeRegion {scope_id: nid,
                                                     bound_region: ty::BrAnon(id)}),
                         self.t_int())
     }
 
     pub fn t_rptr_static(&self) -> ty::t {
-        ty::mk_imm_rptr(self.tcx, ty::ReStatic, self.t_int())
+        ty::mk_imm_rptr(self.infcx.tcx, ty::ReStatic, self.t_int())
     }
 
     pub fn dummy_type_trace(&self) -> infer::TypeTrace {
@@ -299,12 +303,12 @@ impl<'a> Env<'a> {
         }
     }
 
-    pub fn lub(&self) -> Lub<'a> {
+    pub fn lub(&self) -> Lub<'a, 'tcx> {
         let trace = self.dummy_type_trace();
         Lub(self.infcx.combine_fields(true, trace))
     }
 
-    pub fn glb(&self) -> Glb<'a> {
+    pub fn glb(&self) -> Glb<'a, 'tcx> {
         let trace = self.dummy_type_trace();
         Glb(self.infcx.combine_fields(true, trace))
     }
@@ -317,7 +321,7 @@ impl<'a> Env<'a> {
         match self.lub().tys(t1, t2) {
             Ok(t) => t,
             Err(ref e) => fail!("unexpected error computing LUB: {:?}",
-                                ty::type_err_to_str(self.tcx, e))
+                                ty::type_err_to_str(self.infcx.tcx, e))
         }
     }
 
@@ -329,7 +333,7 @@ impl<'a> Env<'a> {
             }
             Err(ref e) => {
                 fail!("unexpected error in LUB: {}",
-                      ty::type_err_to_str(self.tcx, e))
+                      ty::type_err_to_str(self.infcx.tcx, e))
             }
         }
     }
diff --git a/src/librustc/middle/typeck/infer/unify.rs b/src/librustc/middle/typeck/infer/unify.rs
index adf0a25ce40..22d78340e96 100644
--- a/src/librustc/middle/typeck/infer/unify.rs
+++ b/src/librustc/middle/typeck/infer/unify.rs
@@ -288,8 +288,8 @@ pub trait InferCtxtMethodsForSimplyUnifiableTypes<V:SimplyUnifiable,
                     -> ures;
 }
 
-impl<'tcx,V:SimplyUnifiable,K:UnifyKey<Option<V>>>
-    InferCtxtMethodsForSimplyUnifiableTypes<V,K> for InferCtxt<'tcx>
+impl<'a,'tcx,V:SimplyUnifiable,K:UnifyKey<Option<V>>>
+    InferCtxtMethodsForSimplyUnifiableTypes<V,K> for InferCtxt<'a, 'tcx>
 {
     fn simple_vars(&self,
                    a_is_expected: bool,
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index 4000807ec1b..7104cb95844 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -281,10 +281,10 @@ pub type vtable_map = RefCell<FnvHashMap<MethodCall, vtable_res>>;
 
 pub type impl_vtable_map = RefCell<DefIdMap<vtable_res>>;
 
-pub struct CrateCtxt<'a> {
+pub struct CrateCtxt<'a, 'tcx: 'a> {
     // A mapping from method call sites to traits that have that method.
     trait_map: resolve::TraitMap,
-    tcx: &'a ty::ctxt
+    tcx: &'a ty::ctxt<'tcx>
 }
 
 // Functions that write types into the node type table
diff --git a/src/librustc/middle/typeck/variance.rs b/src/librustc/middle/typeck/variance.rs
index e6227b9c128..7e8c53159fb 100644
--- a/src/librustc/middle/typeck/variance.rs
+++ b/src/librustc/middle/typeck/variance.rs
@@ -254,8 +254,8 @@ impl<'a> fmt::Show for VarianceTerm<'a> {
  * The first pass over the crate simply builds up the set of inferreds.
  */
 
-struct TermsContext<'a> {
-    tcx: &'a ty::ctxt,
+struct TermsContext<'a, 'tcx: 'a> {
+    tcx: &'a ty::ctxt<'tcx>,
     arena: &'a Arena,
 
     empty_variances: Rc<ty::ItemVariances>,
@@ -283,10 +283,10 @@ struct InferredInfo<'a> {
     term: VarianceTermPtr<'a>,
 }
 
-fn determine_parameters_to_be_inferred<'a>(tcx: &'a ty::ctxt,
-                                           arena: &'a mut Arena,
-                                           krate: &ast::Crate)
-                                           -> TermsContext<'a> {
+fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
+                                                 arena: &'a mut Arena,
+                                                 krate: &ast::Crate)
+                                                 -> TermsContext<'a, 'tcx> {
     let mut terms_cx = TermsContext {
         tcx: tcx,
         arena: arena,
@@ -306,7 +306,7 @@ fn determine_parameters_to_be_inferred<'a>(tcx: &'a ty::ctxt,
     terms_cx
 }
 
-impl<'a> TermsContext<'a> {
+impl<'a, 'tcx> TermsContext<'a, 'tcx> {
     fn add_inferred(&mut self,
                     item_id: ast::NodeId,
                     kind: ParamKind,
@@ -337,7 +337,7 @@ impl<'a> TermsContext<'a> {
     }
 }
 
-impl<'a> Visitor<()> for TermsContext<'a> {
+impl<'a, 'tcx> Visitor<()> for TermsContext<'a, 'tcx> {
     fn visit_item(&mut self, item: &ast::Item, _: ()) {
         debug!("add_inferreds for item {}", item.repr(self.tcx));
 
@@ -402,8 +402,8 @@ impl<'a> Visitor<()> for TermsContext<'a> {
  * We walk the set of items and, for each member, generate new constraints.
  */
 
-struct ConstraintContext<'a> {
-    terms_cx: TermsContext<'a>,
+struct ConstraintContext<'a, 'tcx: 'a> {
+    terms_cx: TermsContext<'a, 'tcx>,
 
     // These are the def-id of the std::kinds::marker::InvariantType,
     // std::kinds::marker::InvariantLifetime, and so on. The arrays
@@ -431,9 +431,9 @@ struct Constraint<'a> {
     variance: &'a VarianceTerm<'a>,
 }
 
-fn add_constraints_from_crate<'a>(terms_cx: TermsContext<'a>,
-                                  krate: &ast::Crate)
-                                  -> ConstraintContext<'a> {
+fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>,
+                                        krate: &ast::Crate)
+                                        -> ConstraintContext<'a, 'tcx> {
     let mut invariant_lang_items = [None, ..2];
     let mut covariant_lang_items = [None, ..2];
     let mut contravariant_lang_items = [None, ..2];
@@ -477,7 +477,7 @@ fn add_constraints_from_crate<'a>(terms_cx: TermsContext<'a>,
     constraint_cx
 }
 
-impl<'a> Visitor<()> for ConstraintContext<'a> {
+impl<'a, 'tcx> Visitor<()> for ConstraintContext<'a, 'tcx> {
     fn visit_item(&mut self, item: &ast::Item, _: ()) {
         let did = ast_util::local_def(item.id);
         let tcx = self.terms_cx.tcx;
@@ -546,8 +546,8 @@ fn is_lifetime(map: &ast_map::Map, param_id: ast::NodeId) -> bool {
     }
 }
 
-impl<'a> ConstraintContext<'a> {
-    fn tcx(&self) -> &'a ty::ctxt {
+impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> {
         self.terms_cx.tcx
     }
 
@@ -942,8 +942,8 @@ impl<'a> ConstraintContext<'a> {
  * inferred is then written into the `variance_map` in the tcx.
  */
 
-struct SolveContext<'a> {
-    terms_cx: TermsContext<'a>,
+struct SolveContext<'a, 'tcx: 'a> {
+    terms_cx: TermsContext<'a, 'tcx>,
     constraints: Vec<Constraint<'a>> ,
 
     // Maps from an InferredIndex to the inferred value for that variable.
@@ -961,7 +961,7 @@ fn solve_constraints(constraints_cx: ConstraintContext) {
     solutions_cx.write();
 }
 
-impl<'a> SolveContext<'a> {
+impl<'a, 'tcx> SolveContext<'a, 'tcx> {
     fn solve(&mut self) {
         // Propagate constraints until a fixed point is reached.  Note
         // that the maximum number of iterations is 2C where C is the