Auto merge of #22512 - nikomatsakis:issue-20300-where-clause-not-bounds, r=nikomatsakis

This is a fix for #20300 though as a side-sweep it fixes a number of stack overflows because it integrates cycle detection into the conversion process. I didn't go through and retest everything.

The tricky part here is that in some cases we have to go find the information we need from the AST -- we can't use the converted form of the where-clauses because we often have to handle something like `T::Item` *while converting the where-clauses themselves*. Since this is also not a fixed-point process we can't just try and keep trying to find the best order. So instead I modified the `AstConv` interface to allow you to request the bounds for a type parameter; we'll then do a secondary scan of the where-clauses to figure out what we need. This may create a cycle in some cases, but we have code to catch that.

Another approach that is NOT taken by this PR would be to "convert" `T::Item` into a form that does not specify what trait it's using. This then kind of defers the problem of picking the trait till later. That might be a good idea, but it would make normalization and everything else much harder, so I'm holding off on that (and hoping to find a better way for handling things like `i32::T`).

This PR also removes "most of" the `bounds` struct from `TypeParameterDef`. Still a little ways to go before `ParamBounds` can be removed entirely -- it's used for supertraits, for example (though those really ought to be converted, I think, to a call to `get_type_parameter_bounds` on `Self` from within the trait definition).

cc @jroesch 

Fixes #20300 

18 files changed, 1066 insertions, 417 deletions

diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index 4a45b7fbfdc..baecfb7eb22 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -822,7 +822,6 @@ fn parse_type_param_def_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
     assert_eq!(next(st), '|');
     let index = parse_u32(st);
     assert_eq!(next(st), '|');
-    let bounds = parse_bounds_(st, conv);
     let default = parse_opt(st, |st| parse_ty_(st, conv));
     let object_lifetime_default = parse_object_lifetime_default(st, conv);
 
@@ -831,7 +830,6 @@ fn parse_type_param_def_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
         def_id: def_id,
         space: space,
         index: index,
-        bounds: bounds,
         default: default,
         object_lifetime_default: object_lifetime_default,
     }
@@ -924,18 +922,18 @@ fn parse_bounds_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
 {
     let builtin_bounds = parse_builtin_bounds_(st, conv);
 
+    let region_bounds = parse_region_bounds_(st, conv);
+
     let mut param_bounds = ty::ParamBounds {
-        region_bounds: Vec::new(),
+        region_bounds: region_bounds,
         builtin_bounds: builtin_bounds,
         trait_bounds: Vec::new(),
         projection_bounds: Vec::new(),
     };
+
+
     loop {
         match next(st) {
-            'R' => {
-                param_bounds.region_bounds.push(
-                    parse_region_(st, conv));
-            }
             'I' => {
                 param_bounds.trait_bounds.push(
                     ty::Binder(parse_trait_ref_(st, conv)));
@@ -953,3 +951,18 @@ fn parse_bounds_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
         }
     }
 }
+
+fn parse_region_bounds_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F)
+                              -> Vec<ty::Region> where
+    F: FnMut(DefIdSource, ast::DefId) -> ast::DefId,
+{
+    let mut region_bounds = Vec::new();
+    loop {
+        match next(st) {
+            'R' => { region_bounds.push(parse_region_(st, conv)); }
+            '.' => { return region_bounds; }
+            c => { panic!("parse_bounds: bad bounds ('{}')", c); }
+        }
+    }
+}
+
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 11609ebe675..76a365259aa 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -386,10 +386,7 @@ pub fn enc_bounds<'a, 'tcx>(w: &mut SeekableMemWriter, cx: &ctxt<'a, 'tcx>,
                             bs: &ty::ParamBounds<'tcx>) {
     enc_builtin_bounds(w, cx, &bs.builtin_bounds);
 
-    for &r in &bs.region_bounds {
-        mywrite!(w, "R");
-        enc_region(w, cx, r);
-    }
+    enc_region_bounds(w, cx, &bs.region_bounds);
 
     for tp in &bs.trait_bounds {
         mywrite!(w, "I");
@@ -404,12 +401,22 @@ pub fn enc_bounds<'a, 'tcx>(w: &mut SeekableMemWriter, cx: &ctxt<'a, 'tcx>,
     mywrite!(w, ".");
 }
 
+pub fn enc_region_bounds<'a, 'tcx>(w: &mut SeekableMemWriter,
+                            cx: &ctxt<'a, 'tcx>,
+                            rs: &[ty::Region]) {
+    for &r in rs {
+        mywrite!(w, "R");
+        enc_region(w, cx, r);
+    }
+
+    mywrite!(w, ".");
+}
+
 pub fn enc_type_param_def<'a, 'tcx>(w: &mut SeekableMemWriter, cx: &ctxt<'a, 'tcx>,
                                     v: &ty::TypeParameterDef<'tcx>) {
     mywrite!(w, "{}:{}|{}|{}|",
              token::get_name(v.name), (cx.ds)(v.def_id),
              v.space.to_uint(), v.index);
-    enc_bounds(w, cx, &v.bounds);
     enc_opt(w, v.default, |w, t| enc_ty(w, cx, t));
     enc_object_lifetime_default(w, cx, v.object_lifetime_default);
 }
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 91313633397..78b8d4f7b1e 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -55,7 +55,7 @@ use middle::region;
 use middle::resolve_lifetime;
 use middle::infer;
 use middle::stability;
-use middle::subst::{self, Subst, Substs, VecPerParamSpace};
+use middle::subst::{self, ParamSpace, Subst, Substs, VecPerParamSpace};
 use middle::traits;
 use middle::ty;
 use middle::ty_fold::{self, TypeFoldable, TypeFolder};
@@ -1750,7 +1750,6 @@ pub struct TypeParameterDef<'tcx> {
     pub def_id: ast::DefId,
     pub space: subst::ParamSpace,
     pub index: u32,
-    pub bounds: ParamBounds<'tcx>,
     pub default: Option<Ty<'tcx>>,
     pub object_lifetime_default: Option<ObjectLifetimeDefault>,
 }
@@ -2546,6 +2545,13 @@ impl<'tcx> ctxt<'tcx> {
     {
         self.closure_tys.borrow()[def_id].subst(self, substs)
     }
+
+    pub fn type_parameter_def(&self,
+                              node_id: ast::NodeId)
+                              -> TypeParameterDef<'tcx>
+    {
+        self.ty_param_defs.borrow()[node_id].clone()
+    }
 }
 
 // Interns a type/name combination, stores the resulting box in cx.interner,
@@ -2996,6 +3002,13 @@ impl<'tcx> TyS<'tcx> {
             _ => None,
         }
     }
+
+    pub fn is_param(&self, space: ParamSpace, index: u32) -> bool {
+        match self.sty {
+            ty::ty_param(ref data) => data.space == space && data.idx == index,
+            _ => false,
+        }
+    }
 }
 
 pub fn walk_ty<'tcx, F>(ty_root: Ty<'tcx>, mut f: F)
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index d2469c052ac..4bf47c3a75f 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -377,7 +377,6 @@ impl<'tcx> TypeFoldable<'tcx> for ty::TypeParameterDef<'tcx> {
             def_id: self.def_id,
             space: self.space,
             index: self.index,
-            bounds: self.bounds.fold_with(folder),
             default: self.default.fold_with(folder),
             object_lifetime_default: self.object_lifetime_default.fold_with(folder),
         }
diff --git a/src/librustc/session/config.rs b/src/librustc/session/config.rs
index efc12d00b10..efcde8b2fa1 100644
--- a/src/librustc/session/config.rs
+++ b/src/librustc/session/config.rs
@@ -99,6 +99,7 @@ pub struct Options {
     pub test: bool,
     pub parse_only: bool,
     pub no_trans: bool,
+    pub treat_err_as_bug: bool,
     pub no_analysis: bool,
     pub debugging_opts: DebuggingOptions,
     /// Whether to write dependency files. It's (enabled, optional filename).
@@ -223,6 +224,7 @@ pub fn basic_options() -> Options {
         test: false,
         parse_only: false,
         no_trans: false,
+        treat_err_as_bug: false,
         no_analysis: false,
         debugging_opts: basic_debugging_options(),
         write_dependency_info: (false, None),
@@ -573,6 +575,8 @@ options! {DebuggingOptions, DebuggingSetter, basic_debugging_options,
           "Parse only; do not compile, assemble, or link"),
     no_trans: bool = (false, parse_bool,
           "Run all passes except translation; no output"),
+    treat_err_as_bug: bool = (false, parse_bool,
+          "Treat all errors that occur as bugs"),
     no_analysis: bool = (false, parse_bool,
           "Parse and expand the source, but run no analysis"),
     extra_plugins: Vec<String> = (Vec::new(), parse_list,
@@ -843,6 +847,7 @@ pub fn build_session_options(matches: &getopts::Matches) -> Options {
 
     let parse_only = debugging_opts.parse_only;
     let no_trans = debugging_opts.no_trans;
+    let treat_err_as_bug = debugging_opts.treat_err_as_bug;
     let no_analysis = debugging_opts.no_analysis;
 
     if debugging_opts.debug_llvm {
@@ -1030,6 +1035,7 @@ pub fn build_session_options(matches: &getopts::Matches) -> Options {
         test: test,
         parse_only: parse_only,
         no_trans: no_trans,
+        treat_err_as_bug: treat_err_as_bug,
         no_analysis: no_analysis,
         debugging_opts: debugging_opts,
         write_dependency_info: write_dependency_info,
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index b690cc7f7d0..324ce1d66d0 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -74,18 +74,27 @@ impl Session {
         self.diagnostic().handler().fatal(msg)
     }
     pub fn span_err(&self, sp: Span, msg: &str) {
+        if self.opts.treat_err_as_bug {
+            self.span_bug(sp, msg);
+        }
         match split_msg_into_multilines(msg) {
             Some(msg) => self.diagnostic().span_err(sp, &msg[..]),
             None => self.diagnostic().span_err(sp, msg)
         }
     }
     pub fn span_err_with_code(&self, sp: Span, msg: &str, code: &str) {
+        if self.opts.treat_err_as_bug {
+            self.span_bug(sp, msg);
+        }
         match split_msg_into_multilines(msg) {
             Some(msg) => self.diagnostic().span_err_with_code(sp, &msg[..], code),
             None => self.diagnostic().span_err_with_code(sp, msg, code)
         }
     }
     pub fn err(&self, msg: &str) {
+        if self.opts.treat_err_as_bug {
+            self.bug(msg);
+        }
         self.diagnostic().handler().err(msg)
     }
     pub fn err_count(&self) -> uint {
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 9e50fdb4c48..844635117b5 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -73,9 +73,14 @@ use syntax::print::pprust;
 pub trait AstConv<'tcx> {
     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
 
-    fn get_item_type_scheme(&self, id: ast::DefId) -> ty::TypeScheme<'tcx>;
+    fn get_item_type_scheme(&self, span: Span, id: ast::DefId)
+                            -> Result<ty::TypeScheme<'tcx>, ErrorReported>;
 
-    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>>;
+    fn get_trait_def(&self, span: Span, id: ast::DefId)
+                     -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>;
+
+    fn get_type_parameter_bounds(&self, span: Span, def_id: ast::NodeId)
+                                 -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>;
 
     /// Return an (optional) substitution to convert bound type parameters that
     /// are in scope into free ones. This function should only return Some
@@ -683,7 +688,14 @@ fn ast_path_to_trait_ref<'a,'tcx>(
     -> Rc<ty::TraitRef<'tcx>>
 {
     debug!("ast_path_to_trait_ref {:?}", trait_segment);
-    let trait_def = this.get_trait_def(trait_def_id);
+    let trait_def = match this.get_trait_def(span, trait_def_id) {
+        Ok(trait_def) => trait_def,
+        Err(ErrorReported) => {
+            // No convenient way to recover from a cycle here. Just bail. Sorry!
+            this.tcx().sess.abort_if_errors();
+            this.tcx().sess.bug("ErrorReported returned, but no errors reports?")
+        }
+    };
 
     let (regions, types, assoc_bindings) = match trait_segment.parameters {
         ast::AngleBracketedParameters(ref data) => {
@@ -860,10 +872,15 @@ fn ast_path_to_ty<'tcx>(
     item_segment: &ast::PathSegment)
     -> Ty<'tcx>
 {
-    let ty::TypeScheme {
-        generics,
-        ty: decl_ty
-    } = this.get_item_type_scheme(did);
+    let tcx = this.tcx();
+    let (generics, decl_ty) = match this.get_item_type_scheme(span, did) {
+        Ok(ty::TypeScheme { generics,  ty: decl_ty }) => {
+            (generics, decl_ty)
+        }
+        Err(ErrorReported) => {
+            return tcx.types.err;
+        }
+    };
 
     let substs = ast_path_substs_for_ty(this, rscope,
                                         span, param_mode,
@@ -1001,20 +1018,17 @@ fn associated_path_def_to_ty<'tcx>(this: &AstConv<'tcx>,
         return (tcx.types.err, ty_path_def);
     };
 
-    let mut suitable_bounds: Vec<_>;
-    let ty_param_name: ast::Name;
-    { // contain scope of refcell:
-        let ty_param_defs = tcx.ty_param_defs.borrow();
-        let ty_param_def = &ty_param_defs[ty_param_node_id];
-        ty_param_name = ty_param_def.name;
+    let ty_param_name = tcx.ty_param_defs.borrow()[ty_param_node_id].name;
 
+    // FIXME(#20300) -- search where clauses, not bounds
+    let bounds =
+        this.get_type_parameter_bounds(span, ty_param_node_id)
+            .unwrap_or(Vec::new());
 
-        // FIXME(#20300) -- search where clauses, not bounds
-        suitable_bounds =
-            traits::transitive_bounds(tcx, &ty_param_def.bounds.trait_bounds)
-            .filter(|b| trait_defines_associated_type_named(this, b.def_id(), assoc_name))
-            .collect();
-    }
+    let mut suitable_bounds: Vec<_> =
+        traits::transitive_bounds(tcx, &bounds)
+        .filter(|b| trait_defines_associated_type_named(this, b.def_id(), assoc_name))
+        .collect();
 
     if suitable_bounds.len() == 0 {
         span_err!(tcx.sess, span, E0220,
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index d7a11b8a515..fd6ba79ec21 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -97,7 +97,7 @@ use middle::subst::{self, Subst, Substs, VecPerParamSpace, ParamSpace, TypeSpace
 use middle::traits;
 use middle::ty::{FnSig, GenericPredicates, VariantInfo, TypeScheme};
 use middle::ty::{Disr, ParamTy, ParameterEnvironment};
-use middle::ty::{self, HasProjectionTypes, RegionEscape, Ty};
+use middle::ty::{self, HasProjectionTypes, RegionEscape, ToPolyTraitRef, Ty};
 use middle::ty::liberate_late_bound_regions;
 use middle::ty::{MethodCall, MethodCallee, MethodMap, ObjectCastMap};
 use middle::ty_fold::{TypeFolder, TypeFoldable};
@@ -106,7 +106,7 @@ use session::Session;
 use {CrateCtxt, lookup_full_def, require_same_types};
 use TypeAndSubsts;
 use lint;
-use util::common::{block_query, indenter, loop_query};
+use util::common::{block_query, ErrorReported, indenter, loop_query};
 use util::ppaux::{self, Repr};
 use util::nodemap::{DefIdMap, FnvHashMap, NodeMap};
 use util::lev_distance::lev_distance;
@@ -1206,18 +1206,48 @@ fn check_cast<'a,'tcx>(fcx: &FnCtxt<'a,'tcx>,
 impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> {
     fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
 
-    fn get_item_type_scheme(&self, id: ast::DefId) -> ty::TypeScheme<'tcx> {
-        ty::lookup_item_type(self.tcx(), id)
+    fn get_item_type_scheme(&self, _: Span, id: ast::DefId)
+                            -> Result<ty::TypeScheme<'tcx>, ErrorReported>
+    {
+        Ok(ty::lookup_item_type(self.tcx(), id))
     }
 
-    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
-        ty::lookup_trait_def(self.tcx(), id)
+    fn get_trait_def(&self, _: Span, id: ast::DefId)
+                     -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>
+    {
+        Ok(ty::lookup_trait_def(self.tcx(), id))
     }
 
     fn get_free_substs(&self) -> Option<&Substs<'tcx>> {
         Some(&self.inh.param_env.free_substs)
     }
 
+    fn get_type_parameter_bounds(&self,
+                                 _: Span,
+                                 node_id: ast::NodeId)
+                                 -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
+    {
+        let def = self.tcx().type_parameter_def(node_id);
+        let r = self.inh.param_env.caller_bounds
+                                  .iter()
+                                  .filter_map(|predicate| {
+                                      match *predicate {
+                                          ty::Predicate::Trait(ref data) => {
+                                              if data.0.self_ty().is_param(def.space, def.index) {
+                                                  Some(data.to_poly_trait_ref())
+                                              } else {
+                                                  None
+                                              }
+                                          }
+                                          _ => {
+                                              None
+                                          }
+                                      }
+                                  })
+                                  .collect();
+        Ok(r)
+    }
+
     fn ty_infer(&self, _span: Span) -> Ty<'tcx> {
         self.infcx().next_ty_var()
     }
@@ -3607,7 +3637,7 @@ fn check_expr_with_unifier<'a, 'tcx, F>(fcx: &FnCtxt<'a, 'tcx>,
                 }
             } else {
               tcx.sess.span_bug(expr.span,
-                                &format!("unbound path {}", expr.repr(tcx))[])
+                                &format!("unbound path {}", expr.repr(tcx)))
           };
 
           let mut def = path_res.base_def;
diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs
index 366e934b4dd..a6ecafb6241 100644
--- a/src/librustc_typeck/coherence/overlap.rs
+++ b/src/librustc_typeck/coherence/overlap.rs
@@ -147,7 +147,7 @@ impl<'cx, 'tcx,'v> visit::Visitor<'v> for OverlapChecker<'cx, 'tcx> {
                             None => {
                                 self.tcx.sess.bug(
                                           &format!("no default implementation recorded for `{:?}`",
-                                          item)[]);
+                                          item));
                             }
                         }
                     }
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index bc0c61ad7ad..74fed6cbf39 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -91,19 +91,19 @@ use constrained_type_params::identify_constrained_type_params;
 use middle::lang_items::SizedTraitLangItem;
 use middle::region;
 use middle::resolve_lifetime;
-use middle::subst;
-use middle::subst::{Substs, SelfSpace, TypeSpace, VecPerParamSpace};
+use middle::subst::{Substs, FnSpace, ParamSpace, SelfSpace, TypeSpace, VecPerParamSpace};
 use middle::ty::{AsPredicate, ImplContainer, ImplOrTraitItemContainer, TraitContainer};
-use middle::ty::{self, RegionEscape, Ty, TypeScheme};
+use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty, TypeScheme};
 use middle::ty_fold::{self, TypeFolder, TypeFoldable};
 use middle::infer;
 use rscope::*;
-use util::common::memoized;
+use util::common::{ErrorReported, memoized};
 use util::nodemap::{FnvHashMap, FnvHashSet};
 use util::ppaux;
 use util::ppaux::{Repr,UserString};
 use write_ty_to_tcx;
 
+use std::cell::RefCell;
 use std::collections::HashSet;
 use std::rc::Rc;
 
@@ -121,7 +121,7 @@ use syntax::visit;
 // Main entry point
 
 pub fn collect_item_types(tcx: &ty::ctxt) {
-    let ccx = &CollectCtxt { tcx: tcx };
+    let ccx = &CrateCtxt { tcx: tcx, stack: RefCell::new(Vec::new()) };
 
     match ccx.tcx.lang_items.ty_desc() {
         Some(id) => { collect_intrinsic_type(ccx, id); }
@@ -141,17 +141,43 @@ pub fn collect_item_types(tcx: &ty::ctxt) {
 
 ///////////////////////////////////////////////////////////////////////////
 
-struct CollectCtxt<'a,'tcx:'a> {
+struct CrateCtxt<'a,'tcx:'a> {
     tcx: &'a ty::ctxt<'tcx>,
+
+    // This stack is used to identify cycles in the user's source.
+    // Note that these cycles can cross multiple items.
+    stack: RefCell<Vec<AstConvRequest>>,
+}
+
+/// Context specific to some particular item. This is what implements
+/// AstConv. It has information about the predicates that are defined
+/// on the trait. Unfortunately, this predicate information is
+/// available in various different forms at various points in the
+/// process. So we can't just store a pointer to e.g. the AST or the
+/// parsed ty form, we have to be more flexible. To this end, the
+/// `ItemCtxt` is parameterized by a `GetTypeParameterBounds` object
+/// that it uses to satisfy `get_type_parameter_bounds` requests.
+/// This object might draw the information from the AST
+/// (`ast::Generics`) or it might draw from a `ty::GenericPredicates`
+/// or both (a tuple).
+struct ItemCtxt<'a,'tcx:'a> {
+    ccx: &'a CrateCtxt<'a,'tcx>,
+    param_bounds: &'a (GetTypeParameterBounds<'tcx>+'a),
+}
+
+#[derive(Copy, PartialEq, Eq)]
+enum AstConvRequest {
+    GetItemTypeScheme(ast::DefId),
+    GetTraitDef(ast::DefId),
+    GetTypeParameterBounds(ast::NodeId),
 }
 
 ///////////////////////////////////////////////////////////////////////////
 // Zeroth phase: collect types of intrinsics
 
-fn collect_intrinsic_type(ccx: &CollectCtxt,
+fn collect_intrinsic_type(ccx: &CrateCtxt,
                           lang_item: ast::DefId) {
-    let ty::TypeScheme { ty, .. } =
-        ccx.get_item_type_scheme(lang_item);
+    let ty::TypeScheme { ty, .. } = type_scheme_of_def_id(ccx, lang_item);
     ccx.tcx.intrinsic_defs.borrow_mut().insert(lang_item, ty);
 }
 
@@ -161,7 +187,7 @@ fn collect_intrinsic_type(ccx: &CollectCtxt,
 // know later when parsing field defs.
 
 struct CollectTraitDefVisitor<'a, 'tcx: 'a> {
-    ccx: &'a CollectCtxt<'a, 'tcx>
+    ccx: &'a CrateCtxt<'a, 'tcx>
 }
 
 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectTraitDefVisitor<'a, 'tcx> {
@@ -182,7 +208,7 @@ impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectTraitDefVisitor<'a, 'tcx> {
 // Second phase: collection proper.
 
 struct CollectItemTypesVisitor<'a, 'tcx: 'a> {
-    ccx: &'a CollectCtxt<'a, 'tcx>
+    ccx: &'a CrateCtxt<'a, 'tcx>
 }
 
 impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
@@ -199,42 +225,143 @@ impl<'a, 'tcx, 'v> visit::Visitor<'v> for CollectItemTypesVisitor<'a, 'tcx> {
 ///////////////////////////////////////////////////////////////////////////
 // Utility types and common code for the above passes.
 
-pub trait ToTy<'tcx> {
-    fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx>;
-}
+impl<'a,'tcx> CrateCtxt<'a,'tcx> {
+    fn icx(&'a self, param_bounds: &'a GetTypeParameterBounds<'tcx>) -> ItemCtxt<'a,'tcx> {
+        ItemCtxt { ccx: self, param_bounds: param_bounds }
+    }
 
-impl<'a,'tcx> ToTy<'tcx> for CollectCtxt<'a,'tcx> {
-    fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx> {
-        ast_ty_to_ty(self, rs, ast_ty)
+    fn method_ty(&self, method_id: ast::NodeId) -> Rc<ty::Method<'tcx>> {
+        let def_id = local_def(method_id);
+        match self.tcx.impl_or_trait_items.borrow()[def_id] {
+            ty::MethodTraitItem(ref mty) => mty.clone(),
+            ty::TypeTraitItem(..) => {
+                self.tcx.sess.bug(&format!("method with id {} has the wrong type", method_id));
+            }
+        }
     }
-}
 
-impl<'a, 'tcx> AstConv<'tcx> for CollectCtxt<'a, 'tcx> {
-    fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx }
+    fn cycle_check<F,R>(&self,
+                        span: Span,
+                        request: AstConvRequest,
+                        code: F)
+                        -> Result<R,ErrorReported>
+        where F: FnOnce() -> R
+    {
+        {
+            let mut stack = self.stack.borrow_mut();
+            match stack.iter().enumerate().rev().find(|&(_, r)| *r == request) {
+                None => { }
+                Some((i, _)) => {
+                    let cycle = &stack[i..];
+                    self.report_cycle(span, cycle);
+                    return Err(ErrorReported);
+                }
+            }
+            stack.push(request);
+        }
+
+        let result = code();
 
-    fn get_item_type_scheme(&self, id: ast::DefId) -> ty::TypeScheme<'tcx> {
-        if id.krate != ast::LOCAL_CRATE {
-            return ty::lookup_item_type(self.tcx, id);
+        self.stack.borrow_mut().pop();
+        Ok(result)
+    }
+
+    fn report_cycle(&self,
+                    span: Span,
+                    cycle: &[AstConvRequest])
+    {
+        assert!(!cycle.is_empty());
+        let tcx = self.tcx;
+
+        tcx.sess.span_err(
+            span,
+            &format!("unsupported cyclic reference between types/traits detected"));
+
+        match cycle[0] {
+            AstConvRequest::GetItemTypeScheme(def_id) |
+            AstConvRequest::GetTraitDef(def_id) => {
+                tcx.sess.note(
+                    &format!("the cycle begins when processing `{}`...",
+                             ty::item_path_str(tcx, def_id)));
+            }
+            AstConvRequest::GetTypeParameterBounds(id) => {
+                let def = tcx.type_parameter_def(id);
+                tcx.sess.note(
+                    &format!("the cycle begins when computing the bounds \
+                              for type parameter `{}`...",
+                             def.name.user_string(tcx)));
+            }
         }
 
-        match self.tcx.map.find(id.node) {
-            Some(ast_map::NodeItem(item)) => {
-                type_scheme_of_item(self, &*item)
+        for request in cycle[1..].iter() {
+            match *request {
+                AstConvRequest::GetItemTypeScheme(def_id) |
+                AstConvRequest::GetTraitDef(def_id) => {
+                    tcx.sess.note(
+                        &format!("...which then requires processing `{}`...",
+                                 ty::item_path_str(tcx, def_id)));
+                }
+                AstConvRequest::GetTypeParameterBounds(id) => {
+                    let def = tcx.type_parameter_def(id);
+                    tcx.sess.note(
+                        &format!("...which then requires computing the bounds \
+                                  for type parameter `{}`...",
+                                 def.name.user_string(tcx)));
+                }
             }
-            Some(ast_map::NodeForeignItem(foreign_item)) => {
-                let abi = self.tcx.map.get_foreign_abi(id.node);
-                type_scheme_of_foreign_item(self, &*foreign_item, abi)
+        }
+
+        match cycle[0] {
+            AstConvRequest::GetItemTypeScheme(def_id) |
+            AstConvRequest::GetTraitDef(def_id) => {
+                tcx.sess.note(
+                    &format!("...which then again requires processing `{}`, completing the cycle.",
+                             ty::item_path_str(tcx, def_id)));
             }
-            x => {
-                self.tcx.sess.bug(&format!("unexpected sort of node \
-                                            in get_item_type_scheme(): {:?}",
-                                           x));
+            AstConvRequest::GetTypeParameterBounds(id) => {
+                let def = tcx.type_parameter_def(id);
+                tcx.sess.note(
+                    &format!("...which then again requires computing the bounds \
+                              for type parameter `{}`, completing the cycle.",
+                             def.name.user_string(tcx)));
             }
         }
     }
+}
 
-    fn get_trait_def(&self, id: ast::DefId) -> Rc<ty::TraitDef<'tcx>> {
-        get_trait_def(self, id)
+impl<'a,'tcx> ItemCtxt<'a,'tcx> {
+    fn to_ty<RS:RegionScope>(&self, rs: &RS, ast_ty: &ast::Ty) -> Ty<'tcx> {
+        ast_ty_to_ty(self, rs, ast_ty)
+    }
+}
+
+impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> {
+    fn tcx(&self) -> &ty::ctxt<'tcx> { self.ccx.tcx }
+
+    fn get_item_type_scheme(&self, span: Span, id: ast::DefId)
+                            -> Result<ty::TypeScheme<'tcx>, ErrorReported>
+    {
+        self.ccx.cycle_check(span, AstConvRequest::GetItemTypeScheme(id), || {
+            type_scheme_of_def_id(self.ccx, id)
+        })
+    }
+
+    fn get_trait_def(&self, span: Span, id: ast::DefId)
+                     -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>
+    {
+        self.ccx.cycle_check(span, AstConvRequest::GetTraitDef(id), || {
+            get_trait_def(self.ccx, id)
+        })
+    }
+
+    fn get_type_parameter_bounds(&self,
+                                 span: Span,
+                                 node_id: ast::NodeId)
+                                 -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>
+    {
+        self.ccx.cycle_check(span, AstConvRequest::GetTypeParameterBounds(node_id), || {
+            self.param_bounds.get_type_parameter_bounds(self, span, node_id)
+        })
     }
 
     fn ty_infer(&self, span: Span) -> Ty<'tcx> {
@@ -253,11 +380,147 @@ impl<'a, 'tcx> AstConv<'tcx> for CollectCtxt<'a, 'tcx> {
     }
 }
 
-fn get_enum_variant_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+/// Interface used to find the bounds on a type parameter from within
+/// an `ItemCtxt`. This allows us to use multiple kinds of sources.
+trait GetTypeParameterBounds<'tcx> {
+    fn get_type_parameter_bounds(&self,
+                                 astconv: &AstConv<'tcx>,
+                                 span: Span,
+                                 node_id: ast::NodeId)
+                                 -> Vec<ty::PolyTraitRef<'tcx>>;
+}
+
+/// Find bounds from both elements of the tuple.
+impl<'a,'b,'tcx,A,B> GetTypeParameterBounds<'tcx> for (&'a A,&'b B)
+    where A : GetTypeParameterBounds<'tcx>, B : GetTypeParameterBounds<'tcx>
+{
+    fn get_type_parameter_bounds(&self,
+                                 astconv: &AstConv<'tcx>,
+                                 span: Span,
+                                 node_id: ast::NodeId)
+                                 -> Vec<ty::PolyTraitRef<'tcx>>
+    {
+        let mut v = self.0.get_type_parameter_bounds(astconv, span, node_id);
+        v.extend(self.1.get_type_parameter_bounds(astconv, span, node_id).into_iter());
+        v
+    }
+}
+
+/// Empty set of bounds.
+impl<'tcx> GetTypeParameterBounds<'tcx> for () {
+    fn get_type_parameter_bounds(&self,
+                                 _astconv: &AstConv<'tcx>,
+                                 _span: Span,
+                                 _node_id: ast::NodeId)
+                                 -> Vec<ty::PolyTraitRef<'tcx>>
+    {
+        Vec::new()
+    }
+}
+
+/// Find bounds from the parsed and converted predicates.  This is
+/// used when converting methods, because by that time the predicates
+/// from the trait/impl have been fully converted.
+impl<'tcx> GetTypeParameterBounds<'tcx> for ty::GenericPredicates<'tcx> {
+    fn get_type_parameter_bounds(&self,
+                                 astconv: &AstConv<'tcx>,
+                                 _span: Span,
+                                 node_id: ast::NodeId)
+                                 -> Vec<ty::PolyTraitRef<'tcx>>
+    {
+        let def = astconv.tcx().type_parameter_def(node_id);
+
+        self.predicates
+            .iter()
+            .filter_map(|predicate| {
+                match *predicate {
+                    ty::Predicate::Trait(ref data) => {
+                        if data.0.self_ty().is_param(def.space, def.index) {
+                            Some(data.to_poly_trait_ref())
+                        } else {
+                            None
+                        }
+                    }
+                    ty::Predicate::Equate(..) |
+                    ty::Predicate::RegionOutlives(..) |
+                    ty::Predicate::TypeOutlives(..) |
+                    ty::Predicate::Projection(..) => {
+                        None
+                    }
+                }
+            })
+            .collect()
+    }
+}
+
+/// Find bounds from ast::Generics. This requires scanning through the
+/// AST. We do this to avoid having to convert *all* the bounds, which
+/// would create artificial cycles. Instead we can only convert the
+/// bounds for those a type parameter `X` if `X::Foo` is used.
+impl<'tcx> GetTypeParameterBounds<'tcx> for ast::Generics {
+    fn get_type_parameter_bounds(&self,
+                                 astconv: &AstConv<'tcx>,
+                                 _: Span,
+                                 node_id: ast::NodeId)
+                                 -> Vec<ty::PolyTraitRef<'tcx>>
+    {
+        // In the AST, bounds can derive from two places. Either
+        // written inline like `<T:Foo>` or in a where clause like
+        // `where T:Foo`.
+
+        let def = astconv.tcx().type_parameter_def(node_id);
+        let ty = ty::mk_param_from_def(astconv.tcx(), &def);
+
+        let from_ty_params =
+            self.ty_params
+                .iter()
+                .filter(|p| p.id == node_id)
+                .flat_map(|p| p.bounds.iter())
+                .filter_map(|b| poly_trait_ref_from_bound(astconv, ty, b, &mut Vec::new()));
+
+        let from_where_clauses =
+            self.where_clause
+                .predicates
+                .iter()
+                .filter_map(|wp| match *wp {
+                    ast::WherePredicate::BoundPredicate(ref bp) => Some(bp),
+                    _ => None
+                })
+                .filter(|bp| is_param(astconv.tcx(), &bp.bounded_ty, node_id))
+                .flat_map(|bp| bp.bounds.iter())
+                .filter_map(|b| poly_trait_ref_from_bound(astconv, ty, b, &mut Vec::new()));
+
+        from_ty_params.chain(from_where_clauses).collect()
+    }
+}
+
+/// Tests whether this is the AST for a reference to the type
+/// parameter with id `param_id`. We use this so as to avoid running
+/// `ast_ty_to_ty`, because we want to avoid triggering an all-out
+/// conversion of the type to avoid inducing unnecessary cycles.
+fn is_param<'tcx>(tcx: &ty::ctxt<'tcx>,
+                  ast_ty: &ast::Ty,
+                  param_id: ast::NodeId)
+                  -> bool
+{
+    if let ast::TyPath(None, _) = ast_ty.node {
+        let path_res = tcx.def_map.borrow()[ast_ty.id];
+        if let def::DefTyParam(_, _, def_id, _) = path_res.base_def {
+            path_res.depth == 0 && def_id == local_def(param_id)
+        } else {
+            false
+        }
+    } else {
+        false
+    }
+}
+
+fn get_enum_variant_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                     enum_scheme: ty::TypeScheme<'tcx>,
                                     enum_predicates: ty::GenericPredicates<'tcx>,
                                     variants: &[P<ast::Variant>]) {
     let tcx = ccx.tcx;
+    let icx = ccx.icx(&enum_predicates);
 
     // Create a set of parameter types shared among all the variants.
     for variant in variants {
@@ -268,8 +531,8 @@ fn get_enum_variant_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
         let result_ty = match variant.node.kind {
             ast::TupleVariantKind(ref args) if args.len() > 0 => {
                 let rs = ExplicitRscope;
-                let input_tys: Vec<_> = args.iter().map(|va| ccx.to_ty(&rs, &*va.ty)).collect();
-                ty::mk_ctor_fn(tcx, variant_def_id, &input_tys[..], enum_scheme.ty)
+                let input_tys: Vec<_> = args.iter().map(|va| icx.to_ty(&rs, &*va.ty)).collect();
+                ty::mk_ctor_fn(tcx, variant_def_id, &input_tys, enum_scheme.ty)
             }
 
             ast::TupleVariantKind(_) => {
@@ -294,7 +557,7 @@ fn get_enum_variant_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     }
 }
 
-fn collect_trait_methods<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn collect_trait_methods<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                    trait_id: ast::NodeId,
                                    trait_def: &ty::TraitDef<'tcx>,
                                    trait_predicates: &ty::GenericPredicates<'tcx>) {
@@ -393,7 +656,7 @@ fn collect_trait_methods<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
         }
     }
 
-    fn make_method_ty<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, m: &ty::Method<'tcx>) {
+    fn make_method_ty<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, m: &ty::Method<'tcx>) {
         ccx.tcx.tcache.borrow_mut().insert(
             m.def_id,
             TypeScheme {
@@ -405,7 +668,7 @@ fn collect_trait_methods<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
             m.predicates.clone());
     }
 
-    fn ty_method_of_trait_method<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+    fn ty_method_of_trait_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                            trait_id: ast::NodeId,
                                            trait_generics: &ty::Generics<'tcx>,
                                            trait_bounds: &ty::GenericPredicates<'tcx>,
@@ -417,21 +680,17 @@ fn collect_trait_methods<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
                                            m_generics: &ast::Generics,
                                            m_unsafety: &ast::Unsafety,
                                            m_decl: &ast::FnDecl)
-                                           -> ty::Method<'tcx> {
+                                           -> ty::Method<'tcx>
+    {
         let ty_generics =
-            ty_generics_for_fn_or_method(ccx,
-                                         m_generics,
-                                         trait_generics.clone());
+            ty_generics_for_fn(ccx, m_generics, trait_generics);
 
-        let ty_bounds =
-            ty_generic_bounds_for_fn_or_method(ccx,
-                                               m_generics,
-                                               &ty_generics,
-                                               trait_bounds.clone());
+        let ty_generic_predicates =
+            ty_generic_predicates_for_fn(ccx, m_generics, trait_bounds);
 
         let (fty, explicit_self_category) = {
             let trait_self_ty = ty::mk_self_type(ccx.tcx);
-            astconv::ty_of_method(ccx,
+            astconv::ty_of_method(&ccx.icx(&(trait_bounds, m_generics)),
                                   *m_unsafety,
                                   trait_self_ty,
                                   m_explicit_self,
@@ -442,7 +701,7 @@ fn collect_trait_methods<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
         ty::Method::new(
             *m_name,
             ty_generics,
-            ty_bounds,
+            ty_generic_predicates,
             fty,
             explicit_self_category,
             // assume public, because this is only invoked on trait methods
@@ -454,12 +713,14 @@ fn collect_trait_methods<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     }
 }
 
-fn convert_field<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
-                                struct_generics: &ty::Generics<'tcx>,
-                                struct_predicates: &ty::GenericPredicates<'tcx>,
-                                v: &ast::StructField,
-                                origin: ast::DefId) -> ty::field_ty {
-    let tt = ccx.to_ty(&ExplicitRscope, &*v.node.ty);
+fn convert_field<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
+                           struct_generics: &ty::Generics<'tcx>,
+                           struct_predicates: &ty::GenericPredicates<'tcx>,
+                           v: &ast::StructField,
+                           origin: ast::DefId)
+                           -> ty::field_ty
+{
+    let tt = ccx.icx(struct_predicates).to_ty(&ExplicitRscope, &*v.node.ty);
     write_ty_to_tcx(ccx.tcx, v.node.id, tt);
 
     /* add the field to the tcache */
@@ -491,7 +752,7 @@ fn convert_field<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     }
 }
 
-fn convert_associated_type<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn convert_associated_type<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                      trait_def: &ty::TraitDef<'tcx>,
                                      associated_type: &ast::AssociatedType)
 {
@@ -504,18 +765,18 @@ fn convert_associated_type<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     ccx.tcx
        .impl_or_trait_items
        .borrow_mut()
-       .insert(associated_type.def_id,
-               ty::TypeTraitItem(associated_type));
+       .insert(associated_type.def_id, ty::TypeTraitItem(associated_type));
 }
 
-fn convert_methods<'a,'tcx,'i,I>(ccx: &CollectCtxt<'a, 'tcx>,
+fn convert_methods<'a,'tcx,'i,I>(ccx: &CrateCtxt<'a, 'tcx>,
                                  container: ImplOrTraitItemContainer,
                                  ms: I,
                                  untransformed_rcvr_ty: Ty<'tcx>,
                                  rcvr_ty_generics: &ty::Generics<'tcx>,
                                  rcvr_ty_predicates: &ty::GenericPredicates<'tcx>,
                                  rcvr_visibility: ast::Visibility)
-                                 where I: Iterator<Item=&'i ast::Method> {
+                                 where I: Iterator<Item=&'i ast::Method>
+{
     debug!("convert_methods(untransformed_rcvr_ty={}, rcvr_ty_generics={})",
            untransformed_rcvr_ty.repr(ccx.tcx),
            rcvr_ty_generics.repr(ccx.tcx));
@@ -559,31 +820,28 @@ fn convert_methods<'a,'tcx,'i,I>(ccx: &CollectCtxt<'a, 'tcx>,
            .insert(mty.def_id, ty::MethodTraitItem(mty));
     }
 
-    fn ty_of_method<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+    fn ty_of_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                               container: ImplOrTraitItemContainer,
                               m: &ast::Method,
                               untransformed_rcvr_ty: Ty<'tcx>,
                               rcvr_ty_generics: &ty::Generics<'tcx>,
                               rcvr_ty_predicates: &ty::GenericPredicates<'tcx>,
                               rcvr_visibility: ast::Visibility)
-                              -> ty::Method<'tcx> {
+                              -> ty::Method<'tcx>
+    {
         let m_ty_generics =
-            ty_generics_for_fn_or_method(ccx,
-                                         m.pe_generics(),
-                                         rcvr_ty_generics.clone());
-
-        let m_ty_bounds =
-            ty_generic_bounds_for_fn_or_method(ccx,
-                                               m.pe_generics(),
-                                               &m_ty_generics,
-                                               rcvr_ty_predicates.clone());
-
-        let (fty, explicit_self_category) = astconv::ty_of_method(ccx,
-                                                                  m.pe_unsafety(),
-                                                                  untransformed_rcvr_ty,
-                                                                  m.pe_explicit_self(),
-                                                                  &*m.pe_fn_decl(),
-                                                                  m.pe_abi());
+            ty_generics_for_fn(ccx, m.pe_generics(), rcvr_ty_generics);
+
+        let m_ty_generic_predicates =
+            ty_generic_predicates_for_fn(ccx, m.pe_generics(), rcvr_ty_predicates);
+
+        let (fty, explicit_self_category) =
+            astconv::ty_of_method(&ccx.icx(&(rcvr_ty_predicates, m.pe_generics())),
+                                  m.pe_unsafety(),
+                                  untransformed_rcvr_ty,
+                                  m.pe_explicit_self(),
+                                  &*m.pe_fn_decl(),
+                                  m.pe_abi());
 
         // if the method specifies a visibility, use that, otherwise
         // inherit the visibility from the impl (so `foo` in `pub impl
@@ -593,7 +851,7 @@ fn convert_methods<'a,'tcx,'i,I>(ccx: &CollectCtxt<'a, 'tcx>,
 
         ty::Method::new(m.pe_ident().name,
                         m_ty_generics,
-                        m_ty_bounds,
+                        m_ty_generic_predicates,
                         fty,
                         explicit_self_category,
                         method_vis,
@@ -603,7 +861,7 @@ fn convert_methods<'a,'tcx,'i,I>(ccx: &CollectCtxt<'a, 'tcx>,
     }
 }
 
-fn ensure_no_ty_param_bounds(ccx: &CollectCtxt,
+fn ensure_no_ty_param_bounds(ccx: &CrateCtxt,
                                  span: Span,
                                  generics: &ast::Generics,
                                  thing: &'static str) {
@@ -632,7 +890,7 @@ fn ensure_no_ty_param_bounds(ccx: &CollectCtxt,
     }
 }
 
-fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
+fn convert_item(ccx: &CrateCtxt, it: &ast::Item) {
     let tcx = ccx.tcx;
     debug!("convert: item {} with id {}", token::get_ident(it.ident), it.id);
     match it.node {
@@ -649,7 +907,7 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
                                    &enum_definition.variants);
         },
         ast::ItemDefaultImpl(_, ref ast_trait_ref) => {
-            let trait_ref = astconv::instantiate_trait_ref(ccx,
+            let trait_ref = astconv::instantiate_trait_ref(&ccx.icx(&()),
                                                            &ExplicitRscope,
                                                            ast_trait_ref,
                                                            Some(it.id),
@@ -667,11 +925,11 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
 
             debug!("convert: ast_generics={:?}", generics);
             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
-            let ty_predicates = ty_generic_bounds_for_type_or_impl(ccx, &ty_generics, generics);
+            let ty_predicates = ty_generic_predicates_for_type_or_impl(ccx, generics);
 
             debug!("convert: impl_bounds={:?}", ty_predicates);
 
-            let selfty = ccx.to_ty(&ExplicitRscope, &**selfty);
+            let selfty = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, &**selfty);
             write_ty_to_tcx(tcx, it.id, selfty);
 
             tcx.tcache.borrow_mut().insert(local_def(it.id),
@@ -695,12 +953,6 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
             for impl_item in impl_items {
                 match *impl_item {
                     ast::MethodImplItem(ref method) => {
-                        let body_id = method.pe_body().id;
-                        check_method_self_type(ccx,
-                                               &BindingRscope::new(),
-                                               selfty,
-                                               method.pe_explicit_self(),
-                                               body_id);
                         methods.push(&**method);
                     }
                     ast::TypeImplItem(ref typedef) => {
@@ -709,7 +961,7 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
                                               "associated items are not allowed in inherent impls");
                         }
 
-                        let typ = ccx.to_ty(&ExplicitRscope, &*typedef.typ);
+                        let typ = ccx.icx(&ty_predicates).to_ty(&ExplicitRscope, &*typedef.typ);
                         tcx.tcache.borrow_mut().insert(local_def(typedef.id),
                                                        TypeScheme {
                                                            generics: ty::Generics::empty(),
@@ -741,8 +993,23 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
                             &ty_predicates,
                             parent_visibility);
 
+            for impl_item in impl_items {
+                match *impl_item {
+                    ast::MethodImplItem(ref method) => {
+                        let body_id = method.pe_body().id;
+                        check_method_self_type(ccx,
+                                               &BindingRscope::new(),
+                                               ccx.method_ty(method.id),
+                                               selfty,
+                                               method.pe_explicit_self(),
+                                               body_id);
+                    }
+                    ast::TypeImplItem(..) => { }
+                }
+            }
+
             if let Some(ref trait_ref) = *opt_trait_ref {
-                astconv::instantiate_trait_ref(ccx,
+                astconv::instantiate_trait_ref(&ccx.icx(&ty_predicates),
                                                &ExplicitRscope,
                                                trait_ref,
                                                Some(it.id),
@@ -754,20 +1021,42 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
                                                    generics,
                                                    local_def(it.id));
         },
-        ast::ItemTrait(_, _, _, ref trait_methods) => {
+        ast::ItemTrait(_, _, _, ref trait_items) => {
             let trait_def = trait_def_of_item(ccx, it);
             convert_trait_predicates(ccx, it);
             let trait_predicates = ty::lookup_predicates(ccx.tcx, local_def(it.id));
 
             debug!("convert: trait_bounds={:?}", trait_predicates);
 
-            for trait_method in trait_methods {
+            // Run convert_methods on the provided methods.
+            let untransformed_rcvr_ty = ty::mk_self_type(tcx);
+            convert_methods(ccx,
+                            TraitContainer(local_def(it.id)),
+                            trait_items.iter().filter_map(|m| match *m {
+                                ast::RequiredMethod(_) => None,
+                                ast::ProvidedMethod(ref m) => Some(&**m),
+                                ast::TypeTraitItem(_) => None,
+                            }),
+                            untransformed_rcvr_ty,
+                            &trait_def.generics,
+                            &trait_predicates,
+                            it.vis);
+
+            // We need to do this *after* converting methods, since
+            // convert_methods produces a tcache entry that is wrong for
+            // static trait methods. This is somewhat unfortunate.
+            collect_trait_methods(ccx, it.id, &*trait_def, &trait_predicates);
+
+            // This must be done after `collect_trait_methods` so that
+            // we have a method type stored for every method.
+            for trait_item in trait_items {
                 let self_type = ty::mk_self_type(tcx);
-                match *trait_method {
+                match *trait_item {
                     ast::RequiredMethod(ref type_method) => {
                         let rscope = BindingRscope::new();
                         check_method_self_type(ccx,
                                                &rscope,
+                                               ccx.method_ty(type_method.id),
                                                self_type,
                                                &type_method.explicit_self,
                                                it.id)
@@ -775,6 +1064,7 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
                     ast::ProvidedMethod(ref method) => {
                         check_method_self_type(ccx,
                                                &BindingRscope::new(),
+                                               ccx.method_ty(method.id),
                                                self_type,
                                                method.pe_explicit_self(),
                                                it.id)
@@ -786,25 +1076,6 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
                     }
                 }
             }
-
-            // Run convert_methods on the provided methods.
-            let untransformed_rcvr_ty = ty::mk_self_type(tcx);
-            convert_methods(ccx,
-                            TraitContainer(local_def(it.id)),
-                            trait_methods.iter().filter_map(|m| match *m {
-                                ast::RequiredMethod(_) => None,
-                                ast::ProvidedMethod(ref m) => Some(&**m),
-                                ast::TypeTraitItem(_) => None,
-                            }),
-                            untransformed_rcvr_ty,
-                            &trait_def.generics,
-                            &trait_predicates,
-                            it.vis);
-
-            // We need to do this *after* converting methods, since
-            // convert_methods produces a tcache entry that is wrong for
-            // static trait methods. This is somewhat unfortunate.
-            collect_trait_methods(ccx, it.id, &*trait_def, &trait_predicates);
         },
         ast::ItemStruct(ref struct_def, _) => {
             // Write the class type.
@@ -827,7 +1098,7 @@ fn convert_item(ccx: &CollectCtxt, it: &ast::Item) {
     }
 }
 
-fn convert_struct<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn convert_struct<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                             struct_def: &ast::StructDef,
                             scheme: ty::TypeScheme<'tcx>,
                             predicates: ty::GenericPredicates<'tcx>,
@@ -897,7 +1168,7 @@ fn convert_struct<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     }
 }
 
-fn get_trait_def<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn get_trait_def<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                            trait_id: ast::DefId)
                            -> Rc<ty::TraitDef<'tcx>> {
     let tcx = ccx.tcx;
@@ -915,7 +1186,7 @@ fn get_trait_def<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     }
 }
 
-fn trait_def_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                it: &ast::Item)
                                -> Rc<ty::TraitDef<'tcx>>
 {
@@ -958,7 +1229,7 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     let self_param_ty = ty::ParamTy::for_self().to_ty(ccx.tcx);
 
     // supertraits:
-    let bounds = compute_bounds(ccx,
+    let bounds = compute_bounds(&ccx.icx(generics),
                                 self_param_ty,
                                 bounds,
                                 SizedByDefault::No,
@@ -992,9 +1263,9 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 
     return trait_def;
 
-    fn mk_trait_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+    fn mk_trait_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                  generics: &ast::Generics)
-                                 -> subst::Substs<'tcx>
+                                 -> Substs<'tcx>
     {
         let tcx = ccx.tcx;
 
@@ -1004,7 +1275,7 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
                     .iter()
                     .enumerate()
                     .map(|(i, def)| ty::ReEarlyBound(def.lifetime.id,
-                                                     subst::TypeSpace,
+                                                     TypeSpace,
                                                      i as u32,
                                                      def.lifetime.name))
                     .collect();
@@ -1014,18 +1285,18 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
             generics.ty_params
                     .iter()
                     .enumerate()
-                    .map(|(i, def)| ty::mk_param(tcx, subst::TypeSpace,
+                    .map(|(i, def)| ty::mk_param(tcx, TypeSpace,
                                                  i as u32, def.ident.name))
                     .collect();
 
         // ...and also create the `Self` parameter.
         let self_ty = ty::mk_self_type(tcx);
 
-        subst::Substs::new_trait(types, regions, self_ty)
+        Substs::new_trait(types, regions, self_ty)
     }
 }
 
-fn convert_trait_predicates<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, it: &ast::Item) {
+fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item) {
     let tcx = ccx.tcx;
     let trait_def = trait_def_of_item(ccx, it);
 
@@ -1044,9 +1315,7 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, it: &ast::Ite
 
     let super_predicates = ty::predicates(ccx.tcx, self_param_ty, &trait_def.bounds);
 
-    let assoc_predicates = predicates_for_associated_types(ccx, &trait_def.trait_ref, items);
-
-    // `ty_generic_bounds` below will consider the bounds on the type
+    // `ty_generic_predicates` below will consider the bounds on the type
     // parameters (including `Self`) and the explicit where-clauses,
     // but to get the full set of predicates on a trait we need to add
     // in the supertrait bounds and anything declared on the
@@ -1055,27 +1324,31 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, it: &ast::Ite
         ty::GenericPredicates {
             predicates: VecPerParamSpace::new(super_predicates, vec![], vec![])
         };
-    base_predicates.predicates.extend(subst::TypeSpace, assoc_predicates.into_iter());
 
-    let self_bounds = &trait_def.generics.types.get_self().unwrap().bounds;
-    base_predicates.predicates.extend(
-        subst::SelfSpace,
-        ty::predicates(ccx.tcx, self_param_ty, self_bounds).into_iter());
+    // Add in a predicate that `Self:Trait` (where `Trait` is the
+    // current trait).  This is needed for builtin bounds.
+    let self_predicate = trait_def.trait_ref.to_poly_trait_ref().as_predicate();
+    base_predicates.predicates.push(SelfSpace, self_predicate);
 
     // add in the explicit where-clauses
-    let trait_predicates =
-        ty_generic_bounds(ccx,
-                          subst::TypeSpace,
-                          &trait_def.generics,
-                          base_predicates,
-                          &generics.where_clause);
+    let mut trait_predicates =
+        ty_generic_predicates(ccx, TypeSpace, generics, &base_predicates);
+
+    let assoc_predicates = predicates_for_associated_types(ccx,
+                                                           generics,
+                                                           &trait_predicates,
+                                                           &trait_def.trait_ref,
+                                                           items);
+    trait_predicates.predicates.extend(TypeSpace, assoc_predicates.into_iter());
 
     let prev_predicates = tcx.predicates.borrow_mut().insert(def_id, trait_predicates);
     assert!(prev_predicates.is_none());
 
     return;
 
-    fn predicates_for_associated_types<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+    fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
+                                                 ast_generics: &ast::Generics,
+                                                 trait_predicates: &ty::GenericPredicates<'tcx>,
                                                  self_trait_ref: &Rc<ty::TraitRef<'tcx>>,
                                                  trait_items: &[ast::TraitItem])
                                                  -> Vec<ty::Predicate<'tcx>>
@@ -1094,7 +1367,7 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, it: &ast::Ite
                                                  self_trait_ref.clone(),
                                                  assoc_type_def.ident.name);
 
-                let bounds = compute_bounds(ccx,
+                let bounds = compute_bounds(&ccx.icx(&(ast_generics, trait_predicates)),
                                             assoc_ty,
                                             &*assoc_type_def.bounds,
                                             SizedByDefault::Yes,
@@ -1106,7 +1379,31 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>, it: &ast::Ite
     }
 }
 
-fn type_scheme_of_item<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
+fn type_scheme_of_def_id<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                                  def_id: ast::DefId)
+                                  -> ty::TypeScheme<'tcx>
+{
+    if def_id.krate != ast::LOCAL_CRATE {
+        return ty::lookup_item_type(ccx.tcx, def_id);
+    }
+
+    match ccx.tcx.map.find(def_id.node) {
+        Some(ast_map::NodeItem(item)) => {
+            type_scheme_of_item(ccx, &*item)
+        }
+        Some(ast_map::NodeForeignItem(foreign_item)) => {
+            let abi = ccx.tcx.map.get_foreign_abi(def_id.node);
+            type_scheme_of_foreign_item(ccx, &*foreign_item, abi)
+        }
+        x => {
+            ccx.tcx.sess.bug(&format!("unexpected sort of node \
+                                            in get_item_type_scheme(): {:?}",
+                                       x));
+        }
+    }
+}
+
+fn type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
                                 it: &ast::Item)
                                 -> ty::TypeScheme<'tcx>
 {
@@ -1115,28 +1412,25 @@ fn type_scheme_of_item<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
              |_| compute_type_scheme_of_item(ccx, it))
 }
 
-
-fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                                              it: &ast::Item)
-                                              -> ty::TypeScheme<'tcx>
+fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                                        it: &ast::Item)
+                                        -> ty::TypeScheme<'tcx>
 {
     let tcx = ccx.tcx;
     match it.node {
         ast::ItemStatic(ref t, _, _) | ast::ItemConst(ref t, _) => {
-            let ty = ccx.to_ty(&ExplicitRscope, &**t);
+            let ty = ccx.icx(&()).to_ty(&ExplicitRscope, &**t);
             ty::TypeScheme { ty: ty, generics: ty::Generics::empty() }
         }
         ast::ItemFn(ref decl, unsafety, abi, ref generics, _) => {
-            let ty_generics = ty_generics_for_fn_or_method(ccx,
-                                                           generics,
-                                                           ty::Generics::empty());
-            let tofd = astconv::ty_of_bare_fn(ccx, unsafety, abi, &**decl);
+            let ty_generics = ty_generics_for_fn(ccx, generics, &ty::Generics::empty());
+            let tofd = astconv::ty_of_bare_fn(&ccx.icx(generics), unsafety, abi, &**decl);
             let ty = ty::mk_bare_fn(tcx, Some(local_def(it.id)), tcx.mk_bare_fn(tofd));
             ty::TypeScheme { ty: ty, generics: ty_generics }
         }
         ast::ItemTy(ref t, ref generics) => {
-            let ty = ccx.to_ty(&ExplicitRscope, &**t);
             let ty_generics = ty_generics_for_type_or_impl(ccx, generics);
+            let ty = ccx.icx(generics).to_ty(&ExplicitRscope, &**t);
             ty::TypeScheme { ty: ty, generics: ty_generics }
         }
         ast::ItemEnum(_, ref generics) => {
@@ -1168,7 +1462,7 @@ fn compute_type_scheme_of_item<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
     }
 }
 
-fn convert_typed_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn convert_typed_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                 it: &ast::Item)
                                 -> (ty::TypeScheme<'tcx>, ty::GenericPredicates<'tcx>)
 {
@@ -1181,19 +1475,16 @@ fn convert_typed_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
             ty::GenericPredicates::empty()
         }
         ast::ItemFn(_, _, _, ref ast_generics, _) => {
-            ty_generic_bounds_for_fn_or_method(ccx,
-                                               ast_generics,
-                                               &scheme.generics,
-                                               ty::GenericPredicates::empty())
+            ty_generic_predicates_for_fn(ccx, ast_generics, &ty::GenericPredicates::empty())
         }
         ast::ItemTy(_, ref generics) => {
-            ty_generic_bounds_for_type_or_impl(ccx, &scheme.generics, generics)
+            ty_generic_predicates_for_type_or_impl(ccx, generics)
         }
         ast::ItemEnum(_, ref generics) => {
-            ty_generic_bounds_for_type_or_impl(ccx, &scheme.generics, generics)
+            ty_generic_predicates_for_type_or_impl(ccx, generics)
         }
         ast::ItemStruct(_, ref generics) => {
-            ty_generic_bounds_for_type_or_impl(ccx, &scheme.generics, generics)
+            ty_generic_predicates_for_type_or_impl(ccx, generics)
         }
         ast::ItemDefaultImpl(..) |
         ast::ItemTrait(..) |
@@ -1205,8 +1496,8 @@ fn convert_typed_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
         ast::ItemMac(..) => {
             tcx.sess.span_bug(
                 it.span,
-                format!("compute_type_scheme_of_item: unexpected item type: {:?}",
-                        it.node).as_slice());
+                &format!("compute_type_scheme_of_item: unexpected item type: {:?}",
+                         it.node));
         }
     };
 
@@ -1222,7 +1513,7 @@ fn convert_typed_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
                                      Some(ty::ObjectLifetimeDefault::Specific(r)) =>
                                          r.user_string(tcx),
                                      d =>
-                                         d.repr(ccx.tcx()),
+                                         d.repr(ccx.tcx),
                                  })
                                  .collect::<Vec<String>>()
                                  .connect(",");
@@ -1234,18 +1525,18 @@ fn convert_typed_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 }
 
 fn type_scheme_of_foreign_item<'a, 'tcx>(
-    ccx: &CollectCtxt<'a, 'tcx>,
+    ccx: &CrateCtxt<'a, 'tcx>,
     it: &ast::ForeignItem,
     abi: abi::Abi)
     -> ty::TypeScheme<'tcx>
 {
-    memoized(&ccx.tcx().tcache,
+    memoized(&ccx.tcx.tcache,
              local_def(it.id),
              |_| compute_type_scheme_of_foreign_item(ccx, it, abi))
 }
 
 fn compute_type_scheme_of_foreign_item<'a, 'tcx>(
-    ccx: &CollectCtxt<'a, 'tcx>,
+    ccx: &CrateCtxt<'a, 'tcx>,
     it: &ast::ForeignItem,
     abi: abi::Abi)
     -> ty::TypeScheme<'tcx>
@@ -1257,13 +1548,13 @@ fn compute_type_scheme_of_foreign_item<'a, 'tcx>(
         ast::ForeignItemStatic(ref t, _) => {
             ty::TypeScheme {
                 generics: ty::Generics::empty(),
-                ty: ast_ty_to_ty(ccx, &ExplicitRscope, t)
+                ty: ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, t)
             }
         }
     }
 }
 
-fn convert_foreign_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn convert_foreign_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                   it: &ast::ForeignItem)
 {
     // For reasons I cannot fully articulate, I do so hate the AST
@@ -1278,10 +1569,7 @@ fn convert_foreign_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 
     let predicates = match it.node {
         ast::ForeignItemFn(_, ref generics) => {
-            ty_generic_bounds_for_fn_or_method(ccx,
-                                               generics,
-                                               &scheme.generics,
-                                               ty::GenericPredicates::empty())
+            ty_generic_predicates_for_fn(ccx, generics, &ty::GenericPredicates::empty())
         }
         ast::ForeignItemStatic(..) => {
             ty::GenericPredicates::empty()
@@ -1292,45 +1580,29 @@ fn convert_foreign_item<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     assert!(prev_predicates.is_none());
 }
 
-fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn ty_generics_for_type_or_impl<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                           generics: &ast::Generics)
                                           -> ty::Generics<'tcx> {
-    ty_generics(ccx,
-                subst::TypeSpace,
-                &generics.lifetimes,
-                &generics.ty_params,
-                &generics.where_clause,
-                ty::Generics::empty())
+    ty_generics(ccx, TypeSpace, generics, &ty::Generics::empty())
 }
 
-fn ty_generic_bounds_for_type_or_impl<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                                               ty_generics: &ty::Generics<'tcx>,
-                                               generics: &ast::Generics)
-                                               -> ty::GenericPredicates<'tcx>
+fn ty_generic_predicates_for_type_or_impl<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                                                   generics: &ast::Generics)
+                                                   -> ty::GenericPredicates<'tcx>
 {
-    ty_generic_bounds(ccx,
-                      subst::TypeSpace,
-                      ty_generics,
-                      ty::GenericPredicates::empty(),
-                      &generics.where_clause)
+    ty_generic_predicates(ccx, TypeSpace, generics, &ty::GenericPredicates::empty())
 }
 
-fn ty_generics_for_trait<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                    trait_id: ast::NodeId,
-                                   substs: &'tcx subst::Substs<'tcx>,
+                                   substs: &'tcx Substs<'tcx>,
                                    ast_generics: &ast::Generics)
                                    -> ty::Generics<'tcx>
 {
     debug!("ty_generics_for_trait(trait_id={}, substs={})",
            local_def(trait_id).repr(ccx.tcx), substs.repr(ccx.tcx));
 
-    let mut generics =
-        ty_generics(ccx,
-                    subst::TypeSpace,
-                    &ast_generics.lifetimes,
-                    &ast_generics.ty_params,
-                    &ast_generics.where_clause,
-                    ty::Generics::empty());
+    let mut generics = ty_generics_for_type_or_impl(ccx, ast_generics);
 
     // Add in the self type parameter.
     //
@@ -1338,65 +1610,46 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
     // the node id for the Self type parameter.
     let param_id = trait_id;
 
-    let self_trait_ref =
-        Rc::new(ty::TraitRef { def_id: local_def(trait_id),
-                               substs: substs });
-
     let def = ty::TypeParameterDef {
-        space: subst::SelfSpace,
+        space: SelfSpace,
         index: 0,
         name: special_idents::type_self.name,
         def_id: local_def(param_id),
-        bounds: ty::ParamBounds {
-            region_bounds: vec!(),
-            builtin_bounds: ty::empty_builtin_bounds(),
-            trait_bounds: vec!(ty::Binder(self_trait_ref.clone())),
-            projection_bounds: vec!(),
-        },
         default: None,
         object_lifetime_default: None,
     };
 
     ccx.tcx.ty_param_defs.borrow_mut().insert(param_id, def.clone());
 
-    generics.types.push(subst::SelfSpace, def);
+    generics.types.push(SelfSpace, def);
 
     return generics;
 }
 
-fn ty_generics_for_fn_or_method<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                                         generics: &ast::Generics,
-                                         base_generics: ty::Generics<'tcx>)
-                                         -> ty::Generics<'tcx>
+fn ty_generics_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                               generics: &ast::Generics,
+                               base_generics: &ty::Generics<'tcx>)
+                               -> ty::Generics<'tcx>
 {
-    let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
-    ty_generics(ccx,
-                subst::FnSpace,
-                &early_lifetimes[..],
-                &generics.ty_params,
-                &generics.where_clause,
-                base_generics)
+    ty_generics(ccx, FnSpace, generics, base_generics)
 }
 
-fn ty_generic_bounds_for_fn_or_method<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                                               generics: &ast::Generics,
-                                               ty_generics: &ty::Generics<'tcx>,
-                                               base: ty::GenericPredicates<'tcx>)
-                                               -> ty::GenericPredicates<'tcx>
+fn ty_generic_predicates_for_fn<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                                         generics: &ast::Generics,
+                                         base_predicates: &ty::GenericPredicates<'tcx>)
+                                         -> ty::GenericPredicates<'tcx>
 {
-    ty_generic_bounds(ccx,
-                      subst::FnSpace,
-                      ty_generics,
-                      base,
-                      &generics.where_clause)
+    ty_generic_predicates(ccx, FnSpace, generics, base_predicates)
 }
 
 // Add the Sized bound, unless the type parameter is marked as `?Sized`.
-fn add_unsized_bound<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                              bounds: &mut ty::BuiltinBounds,
-                              ast_bounds: &[ast::TyParamBound],
-                              span: Span)
+fn add_unsized_bound<'tcx>(astconv: &AstConv<'tcx>,
+                           bounds: &mut ty::BuiltinBounds,
+                           ast_bounds: &[ast::TyParamBound],
+                           span: Span)
 {
+    let tcx = astconv.tcx();
+
     // Try to find an unbound in bounds.
     let mut unbound = None;
     for ab in ast_bounds {
@@ -1405,80 +1658,108 @@ fn add_unsized_bound<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
                 assert!(ptr.bound_lifetimes.is_empty());
                 unbound = Some(ptr.trait_ref.clone());
             } else {
-                span_err!(ccx.tcx.sess, span, E0203,
+                span_err!(tcx.sess, span, E0203,
                           "type parameter has more than one relaxed default \
                                                 bound, only one is supported");
             }
         }
     }
 
-    let kind_id = ccx.tcx.lang_items.require(SizedTraitLangItem);
+    let kind_id = tcx.lang_items.require(SizedTraitLangItem);
     match unbound {
         Some(ref tpb) => {
             // FIXME(#8559) currently requires the unbound to be built-in.
-            let trait_def_id = ty::trait_ref_to_def_id(ccx.tcx, tpb);
+            let trait_def_id = ty::trait_ref_to_def_id(tcx, tpb);
             match kind_id {
                 Ok(kind_id) if trait_def_id != kind_id => {
-                    ccx.tcx.sess.span_warn(span,
-                                              "default bound relaxed for a type parameter, but \
-                                               this does nothing because the given bound is not \
-                                               a default. Only `?Sized` is supported");
-                    ty::try_add_builtin_trait(ccx.tcx,
-                                              kind_id,
-                                              bounds);
+                    tcx.sess.span_warn(span,
+                                       "default bound relaxed for a type parameter, but \
+                                       this does nothing because the given bound is not \
+                                       a default. Only `?Sized` is supported");
+                    ty::try_add_builtin_trait(tcx, kind_id, bounds);
                 }
                 _ => {}
             }
         }
         _ if kind_id.is_ok() => {
-            ty::try_add_builtin_trait(ccx.tcx, kind_id.unwrap(), bounds);
+            ty::try_add_builtin_trait(tcx, kind_id.unwrap(), bounds);
         }
         // No lang item for Sized, so we can't add it as a bound.
         None => {}
     }
 }
 
-fn ty_generic_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                              space: subst::ParamSpace,
-                              generics: &ty::Generics<'tcx>,
-                              base: ty::GenericPredicates<'tcx>,
-                              where_clause: &ast::WhereClause)
-                              -> ty::GenericPredicates<'tcx>
+/// Returns the early-bound lifetimes declared in this generics
+/// listing.  For anything other than fns/methods, this is just all
+/// the lifetimes that are declared. For fns or methods, we have to
+/// screen out those that do not appear in any where-clauses etc using
+/// `resolve_lifetime::early_bound_lifetimes`.
+fn early_bound_lifetimes_from_generics(space: ParamSpace,
+                                       ast_generics: &ast::Generics)
+                                       -> Vec<ast::LifetimeDef>
+{
+    match space {
+        SelfSpace | TypeSpace => ast_generics.lifetimes.to_vec(),
+        FnSpace => resolve_lifetime::early_bound_lifetimes(ast_generics),
+    }
+}
+
+fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                                  space: ParamSpace,
+                                  ast_generics: &ast::Generics,
+                                  base_predicates: &ty::GenericPredicates<'tcx>)
+                                  -> ty::GenericPredicates<'tcx>
 {
     let tcx = ccx.tcx;
-    let mut result = base;
-
-    // For now, scrape the bounds out of parameters from Generics. This is not great.
-    for def in generics.regions.get_slice(space) {
-        let r_a = def.to_early_bound_region();
-        for &r_b in &def.bounds {
-            let outlives = ty::Binder(ty::OutlivesPredicate(r_a, r_b));
-            result.predicates.push(def.space, ty::Predicate::RegionOutlives(outlives));
-        }
+    let mut result = base_predicates.clone();
+
+    // Collect the predicates that were written inline by the user on each
+    // type parameter (e.g., `<T:Foo>`).
+    for (index, param) in ast_generics.ty_params.iter().enumerate() {
+        let index = index as u32;
+        let param_ty = ty::ParamTy::new(space, index, param.ident.name).to_ty(ccx.tcx);
+        let bounds = compute_bounds(&ccx.icx(&(base_predicates, ast_generics)),
+                                    param_ty,
+                                    &param.bounds,
+                                    SizedByDefault::Yes,
+                                    param.span);
+        let predicates = ty::predicates(ccx.tcx, param_ty, &bounds);
+        result.predicates.extend(space, predicates.into_iter());
     }
-    for def in generics.types.get_slice(space) {
-        let t = ty::mk_param_from_def(ccx.tcx, def);
-        result.predicates.extend(def.space, ty::predicates(ccx.tcx, t, &def.bounds).into_iter());
+
+    // Collect the region predicates that were declared inline as
+    // well. In the case of parameters declared on a fn or method, we
+    // have to be careful to only iterate over early-bound regions.
+    let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
+    for (index, param) in early_lifetimes.iter().enumerate() {
+        let index = index as u32;
+        let region = ty::ReEarlyBound(param.lifetime.id, space, index, param.lifetime.name);
+        for bound in &param.bounds {
+            let bound_region = ast_region_to_region(ccx.tcx, bound);
+            let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
+            result.predicates.push(space, outlives.as_predicate());
+        }
     }
 
-    // Add the bounds not associated with a type parameter
+    // Add in the bounds that appear in the where-clause
+    let where_clause = &ast_generics.where_clause;
     for predicate in &where_clause.predicates {
         match predicate {
             &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
-                let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &*bound_pred.bounded_ty);
+                let ty = ast_ty_to_ty(&ccx.icx(&(base_predicates, ast_generics)),
+                                      &ExplicitRscope,
+                                      &*bound_pred.bounded_ty);
 
                 for bound in &*bound_pred.bounds {
                     match bound {
                         &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref, _) => {
                             let mut projections = Vec::new();
 
-                            let trait_ref = astconv::instantiate_poly_trait_ref(
-                                ccx,
-                                &ExplicitRscope,
-                                poly_trait_ref,
-                                Some(ty),
-                                &mut projections,
-                            );
+                            let trait_ref =
+                                conv_poly_trait_ref(&ccx.icx(&(base_predicates, ast_generics)),
+                                                    ty,
+                                                    poly_trait_ref,
+                                                    &mut projections);
 
                             result.predicates.push(space, trait_ref.as_predicate());
 
@@ -1517,18 +1798,17 @@ fn ty_generic_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
     return result;
 }
 
-fn ty_generics<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                        space: subst::ParamSpace,
-                        lifetime_defs: &[ast::LifetimeDef],
-                        types: &[ast::TyParam],
-                        where_clause: &ast::WhereClause,
-                        base_generics: ty::Generics<'tcx>)
+fn ty_generics<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                        space: ParamSpace,
+                        ast_generics: &ast::Generics,
+                        base_generics: &ty::Generics<'tcx>)
                         -> ty::Generics<'tcx>
 {
     let tcx = ccx.tcx;
-    let mut result = base_generics;
+    let mut result = base_generics.clone();
 
-    for (i, l) in lifetime_defs.iter().enumerate() {
+    let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
+    for (i, l) in early_lifetimes.iter().enumerate() {
         let bounds = l.bounds.iter()
                              .map(|l| ast_region_to_region(tcx, l))
                              .collect();
@@ -1537,16 +1817,14 @@ fn ty_generics<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
                                            index: i as u32,
                                            def_id: local_def(l.lifetime.id),
                                            bounds: bounds };
-        // debug!("ty_generics: def for region param: {:?}",
-        //        def.repr(tcx));
         result.regions.push(space, def);
     }
 
     assert!(result.types.is_empty_in(space));
 
     // Now create the real type parameters.
-    for (i, param) in types.iter().enumerate() {
-        let def = get_or_create_type_parameter_def(ccx, space, param, i as u32, where_clause);
+    for i in 0..ast_generics.ty_params.len() {
+        let def = get_or_create_type_parameter_def(ccx, ast_generics, space, i as u32);
         debug!("ty_generics: def for type param: {:?}, {:?}", def, space);
         result.types.push(space, def);
     }
@@ -1554,29 +1832,24 @@ fn ty_generics<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
     result
 }
 
-fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                                             space: subst::ParamSpace,
-                                             param: &ast::TyParam,
-                                             index: u32,
-                                             where_clause: &ast::WhereClause)
+fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                                             ast_generics: &ast::Generics,
+                                             space: ParamSpace,
+                                             index: u32)
                                              -> ty::TypeParameterDef<'tcx>
 {
+    let param = &ast_generics.ty_params[index as usize];
+
     let tcx = ccx.tcx;
     match tcx.ty_param_defs.borrow().get(&param.id) {
         Some(d) => { return d.clone(); }
         None => { }
     }
 
-    let param_ty = ty::ParamTy::new(space, index, param.ident.name);
-    let bounds = compute_bounds(ccx,
-                                param_ty.to_ty(ccx.tcx),
-                                &param.bounds,
-                                SizedByDefault::Yes,
-                                param.span);
     let default = match param.default {
         None => None,
         Some(ref path) => {
-            let ty = ast_ty_to_ty(ccx, &ExplicitRscope, &**path);
+            let ty = ast_ty_to_ty(&ccx.icx(&()), &ExplicitRscope, &**path);
             let cur_idx = index;
 
             ty::walk_ty(ty, |t| {
@@ -1595,14 +1868,14 @@ fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
     };
 
     let object_lifetime_default =
-        compute_object_lifetime_default(ccx, space, index, &param.bounds, where_clause);
+        compute_object_lifetime_default(ccx, param.id,
+                                        &param.bounds, &ast_generics.where_clause);
 
     let def = ty::TypeParameterDef {
         space: space,
         index: index,
         name: param.ident.name,
         def_id: local_def(param.id),
-        bounds: bounds,
         default: default,
         object_lifetime_default: object_lifetime_default,
     };
@@ -1618,15 +1891,14 @@ fn get_or_create_type_parameter_def<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
 /// intentionally avoid just asking astconv to convert all the where
 /// clauses into a `ty::Predicate`. This is because that could induce
 /// artificial cycles.
-fn compute_object_lifetime_default<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                                            space: subst::ParamSpace,
-                                            index: u32,
+fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                                            param_id: ast::NodeId,
                                             param_bounds: &[ast::TyParamBound],
                                             where_clause: &ast::WhereClause)
                                             -> Option<ty::ObjectLifetimeDefault>
 {
     let inline_bounds = from_bounds(ccx, param_bounds);
-    let where_bounds = from_predicates(ccx, space, index, &where_clause.predicates);
+    let where_bounds = from_predicates(ccx, param_id, &where_clause.predicates);
     let all_bounds: HashSet<_> = inline_bounds.into_iter()
                                               .chain(where_bounds.into_iter())
                                               .collect();
@@ -1638,7 +1910,7 @@ fn compute_object_lifetime_default<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
                   .map(ty::ObjectLifetimeDefault::Specific)
     };
 
-    fn from_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
+    fn from_bounds<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
                             bounds: &[ast::TyParamBound])
                             -> Vec<ty::Region>
     {
@@ -1648,15 +1920,14 @@ fn compute_object_lifetime_default<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
                       ast::TraitTyParamBound(..) =>
                           None,
                       ast::RegionTyParamBound(ref lifetime) =>
-                          Some(astconv::ast_region_to_region(ccx.tcx(), lifetime)),
+                          Some(astconv::ast_region_to_region(ccx.tcx, lifetime)),
                   }
               })
               .collect()
     }
 
-    fn from_predicates<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                                space: subst::ParamSpace,
-                                index: u32,
+    fn from_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                                param_id: ast::NodeId,
                                 predicates: &[ast::WherePredicate])
                                 -> Vec<ty::Region>
     {
@@ -1665,7 +1936,7 @@ fn compute_object_lifetime_default<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
                       match *predicate {
                           ast::WherePredicate::BoundPredicate(ref data) => {
                               if data.bound_lifetimes.len() == 0 &&
-                                  is_param(ccx, &data.bounded_ty, space, index)
+                                  is_param(ccx.tcx, &data.bounded_ty, param_id)
                               {
                                   from_bounds(ccx, &data.bounds).into_iter()
                               } else {
@@ -1680,24 +1951,6 @@ fn compute_object_lifetime_default<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
                   })
                   .collect()
     }
-
-    fn is_param(ccx: &CollectCtxt,
-                ast_ty: &ast::Ty,
-                space: subst::ParamSpace,
-                index: u32)
-                -> bool
-    {
-        if let ast::TyPath(None, _) = ast_ty.node {
-            let path_res = ccx.tcx.def_map.borrow()[ast_ty.id];
-            if let def::DefTyParam(s, i, _, _) = path_res.base_def {
-                path_res.depth == 0 && space == s && index == i
-            } else {
-                false
-            }
-        } else {
-            false
-        }
-    }
 }
 
 enum SizedByDefault { Yes, No }
@@ -1705,25 +1958,25 @@ enum SizedByDefault { Yes, No }
 /// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped Ty or
 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
 /// built-in trait (formerly known as kind): Send.
-fn compute_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                           param_ty: ty::Ty<'tcx>,
-                           ast_bounds: &[ast::TyParamBound],
-                           sized_by_default: SizedByDefault,
-                           span: Span)
-                           -> ty::ParamBounds<'tcx>
+fn compute_bounds<'tcx>(astconv: &AstConv<'tcx>,
+                        param_ty: ty::Ty<'tcx>,
+                        ast_bounds: &[ast::TyParamBound],
+                        sized_by_default: SizedByDefault,
+                        span: Span)
+                        -> ty::ParamBounds<'tcx>
 {
-    let mut param_bounds = conv_param_bounds(ccx,
+    let mut param_bounds = conv_param_bounds(astconv,
                                              span,
                                              param_ty,
                                              ast_bounds);
 
     if let SizedByDefault::Yes = sized_by_default {
-        add_unsized_bound(ccx,
+        add_unsized_bound(astconv,
                           &mut param_bounds.builtin_bounds,
                           ast_bounds,
                           span);
 
-        check_bounds_compatible(ccx,
+        check_bounds_compatible(astconv,
                                 param_ty,
                                 &param_bounds,
                                 span);
@@ -1734,35 +1987,72 @@ fn compute_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
     param_bounds
 }
 
-fn check_bounds_compatible<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
-                                    param_ty: Ty<'tcx>,
-                                    param_bounds: &ty::ParamBounds<'tcx>,
-                                    span: Span) {
+fn check_bounds_compatible<'tcx>(astconv: &AstConv<'tcx>,
+                                 param_ty: Ty<'tcx>,
+                                 param_bounds: &ty::ParamBounds<'tcx>,
+                                 span: Span) {
+    let tcx = astconv.tcx();
     if !param_bounds.builtin_bounds.contains(&ty::BoundSized) {
         ty::each_bound_trait_and_supertraits(
-            ccx.tcx,
+            tcx,
             &param_bounds.trait_bounds,
             |trait_ref| {
-                let trait_def = ccx.get_trait_def(trait_ref.def_id());
-                if trait_def.bounds.builtin_bounds.contains(&ty::BoundSized) {
-                    span_err!(ccx.tcx.sess, span, E0129,
-                              "incompatible bounds on `{}`, \
-                               bound `{}` does not allow unsized type",
-                              param_ty.user_string(ccx.tcx),
-                              trait_ref.user_string(ccx.tcx));
+                match astconv.get_trait_def(span, trait_ref.def_id()) {
+                    Ok(trait_def) => {
+                        if trait_def.bounds.builtin_bounds.contains(&ty::BoundSized) {
+                            span_err!(tcx.sess, span, E0129,
+                                      "incompatible bounds on `{}`, \
+                                        bound `{}` does not allow unsized type",
+                                      param_ty.user_string(tcx),
+                                      trait_ref.user_string(tcx));
+                        }
+                    }
+                    Err(ErrorReported) => { }
                 }
                 true
             });
     }
 }
 
-fn conv_param_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
+/// Converts a specific TyParamBound from the AST into the
+/// appropriate poly-trait-reference.
+fn poly_trait_ref_from_bound<'tcx>(astconv: &AstConv<'tcx>,
+                                   param_ty: Ty<'tcx>,
+                                   bound: &ast::TyParamBound,
+                                   projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
+                                   -> Option<ty::PolyTraitRef<'tcx>>
+{
+    match *bound {
+        ast::TraitTyParamBound(ref tr, ast::TraitBoundModifier::None) => {
+            Some(conv_poly_trait_ref(astconv, param_ty, tr, projections))
+        }
+        ast::TraitTyParamBound(_, ast::TraitBoundModifier::Maybe) |
+        ast::RegionTyParamBound(_) => {
+            None
+        }
+    }
+}
+
+fn conv_poly_trait_ref<'tcx>(astconv: &AstConv<'tcx>,
+                             param_ty: Ty<'tcx>,
+                             trait_ref: &ast::PolyTraitRef,
+                             projections: &mut Vec<ty::PolyProjectionPredicate<'tcx>>)
+                             -> ty::PolyTraitRef<'tcx>
+{
+    astconv::instantiate_poly_trait_ref(astconv,
+                                        &ExplicitRscope,
+                                        trait_ref,
+                                        Some(param_ty),
+                                        projections)
+}
+
+fn conv_param_bounds<'a,'tcx>(astconv: &AstConv<'tcx>,
                               span: Span,
                               param_ty: ty::Ty<'tcx>,
                               ast_bounds: &[ast::TyParamBound])
                               -> ty::ParamBounds<'tcx>
 {
-    let tcx = ccx.tcx;
+    let tcx = astconv.tcx();
     let astconv::PartitionedBounds {
         builtin_bounds,
         trait_bounds,
@@ -1772,19 +2062,16 @@ fn conv_param_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
     let mut projection_bounds = Vec::new();
 
     let trait_bounds: Vec<ty::PolyTraitRef> =
-        trait_bounds.into_iter()
-        .map(|bound| {
-            astconv::instantiate_poly_trait_ref(ccx,
-                                                &ExplicitRscope,
-                                                bound,
-                                                Some(param_ty),
-                                                &mut projection_bounds)
-        })
-    .collect();
+        trait_bounds.iter()
+                    .map(|bound| conv_poly_trait_ref(astconv,
+                                                     param_ty,
+                                                     *bound,
+                                                     &mut projection_bounds))
+                    .collect();
 
     let region_bounds: Vec<ty::Region> =
         region_bounds.into_iter()
-                     .map(|r| ast_region_to_region(ccx.tcx, r))
+                     .map(|r| ast_region_to_region(tcx, r))
                      .collect();
 
     ty::ParamBounds {
@@ -1796,7 +2083,7 @@ fn conv_param_bounds<'a,'tcx>(ccx: &CollectCtxt<'a,'tcx>,
 }
 
 fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
-    ccx: &CollectCtxt<'a, 'tcx>,
+    ccx: &CrateCtxt<'a, 'tcx>,
     decl: &ast::FnDecl,
     ast_generics: &ast::Generics,
     abi: abi::Abi)
@@ -1813,17 +2100,17 @@ fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
         }
     }
 
-    let ty_generics = ty_generics_for_fn_or_method(ccx, ast_generics, ty::Generics::empty());
+    let ty_generics = ty_generics_for_fn(ccx, ast_generics, &ty::Generics::empty());
 
     let rb = BindingRscope::new();
     let input_tys = decl.inputs
                         .iter()
-                        .map(|a| ty_of_arg(ccx, &rb, a, None))
+                        .map(|a| ty_of_arg(&ccx.icx(ast_generics), &rb, a, None))
                         .collect();
 
     let output = match decl.output {
         ast::Return(ref ty) =>
-            ty::FnConverging(ast_ty_to_ty(ccx, &rb, &**ty)),
+            ty::FnConverging(ast_ty_to_ty(&ccx.icx(ast_generics), &rb, &**ty)),
         ast::DefaultReturn(..) =>
             ty::FnConverging(ty::mk_nil(ccx.tcx)),
         ast::NoReturn(..) =>
@@ -1847,9 +2134,9 @@ fn compute_type_scheme_of_foreign_fn_decl<'a, 'tcx>(
     }
 }
 
-fn mk_item_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
+fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                             ty_generics: &ty::Generics<'tcx>)
-                            -> subst::Substs<'tcx>
+                            -> Substs<'tcx>
 {
     let types =
         ty_generics.types.map(
@@ -1859,7 +2146,7 @@ fn mk_item_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
         ty_generics.regions.map(
             |def| def.to_early_bound_region());
 
-    subst::Substs::new(types, regions)
+    Substs::new(types, regions)
 }
 
 /// Verifies that the explicit self type of a method matches the impl
@@ -1869,15 +2156,16 @@ fn mk_item_substs<'a, 'tcx>(ccx: &CollectCtxt<'a, 'tcx>,
 /// comes back to check after the fact that explicit type the user
 /// wrote actually matches what the pre-defined option said.
 fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
-    ccx: &CollectCtxt<'a, 'tcx>,
+    ccx: &CrateCtxt<'a, 'tcx>,
     rs: &RS,
+    method_type: Rc<ty::Method<'tcx>>,
     required_type: Ty<'tcx>,
     explicit_self: &ast::ExplicitSelf,
     body_id: ast::NodeId)
 {
     let tcx = ccx.tcx;
     if let ast::SelfExplicit(ref ast_type, _) = explicit_self.node {
-        let typ = ccx.to_ty(rs, &**ast_type);
+        let typ = ccx.icx(&method_type.predicates).to_ty(rs, &**ast_type);
         let base_type = match typ.sty {
             ty::ty_ptr(tm) | ty::ty_rptr(_, tm) => tm.ty,
             ty::ty_uniq(typ) => typ,
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index b88620d577f..36d39fa58ba 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -479,11 +479,10 @@ impl<'tcx> Clean<TyParam> for ty::TypeParameterDef<'tcx> {
     fn clean(&self, cx: &DocContext) -> TyParam {
         cx.external_typarams.borrow_mut().as_mut().unwrap()
           .insert(self.def_id, self.name.clean(cx));
-        let bounds = self.bounds.clean(cx);
         TyParam {
             name: self.name.clean(cx),
             did: self.def_id,
-            bounds: bounds,
+            bounds: vec![], // these are filled in from the where-clauses
             default: self.default.clean(cx),
         }
     }
@@ -892,9 +891,7 @@ impl<'a, 'tcx> Clean<Generics> for (&'a ty::Generics<'tcx>,
         // Bounds in the type_params and lifetimes fields are repeated in the predicates
         // field (see rustc_typeck::collect::ty_generics), so remove them.
         let stripped_typarams = gens.types.get_slice(space).iter().map(|tp| {
-            let mut stp = tp.clone();
-            stp.bounds = ty::ParamBounds::empty();
-            stp.clean(cx)
+            tp.clean(cx)
         }).collect::<Vec<_>>();
         let stripped_lifetimes = gens.regions.get_slice(space).iter().map(|rp| {
             let mut srp = rp.clone();
diff --git a/src/test/compile-fail/associated-type-projection-ambig-between-bound-and-where-clause.rs b/src/test/compile-fail/associated-type-projection-ambig-between-bound-and-where-clause.rs
new file mode 100644
index 00000000000..ce97019a2b2
--- /dev/null
+++ b/src/test/compile-fail/associated-type-projection-ambig-between-bound-and-where-clause.rs
@@ -0,0 +1,52 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test equality constraints in a where clause where the type being
+// equated appears in a supertrait.
+
+pub trait Vehicle {
+    type Color;
+
+    fn go(&self) {  }
+}
+
+pub trait Box {
+    type Color;
+
+    fn mail(&self) {  }
+}
+
+fn a<C:Vehicle+Box>(_: C::Color) {
+    //~^ ERROR ambiguous associated type `Color` in bounds of `C`
+}
+
+fn b<C>(_: C::Color) where C : Vehicle+Box {
+    //~^ ERROR ambiguous associated type `Color` in bounds of `C`
+}
+
+fn c<C>(_: C::Color) where C : Vehicle, C : Box {
+    //~^ ERROR ambiguous associated type `Color` in bounds of `C`
+}
+
+struct D<X>;
+impl<X> D<X> where X : Vehicle {
+    fn d(&self, _: X::Color) where X : Box { }
+    //~^ ERROR ambiguous associated type `Color` in bounds of `X`
+}
+
+trait E<X:Vehicle> {
+    fn e(&self, _: X::Color) where X : Box;
+    //~^ ERROR ambiguous associated type `Color` in bounds of `X`
+
+    fn f(&self, _: X::Color) where X : Box { }
+    //~^ ERROR ambiguous associated type `Color` in bounds of `X`
+}
+
+pub fn main() { }
diff --git a/src/test/compile-fail/cycle-projection-based-on-where-clause.rs b/src/test/compile-fail/cycle-projection-based-on-where-clause.rs
new file mode 100644
index 00000000000..abcbf567d44
--- /dev/null
+++ b/src/test/compile-fail/cycle-projection-based-on-where-clause.rs
@@ -0,0 +1,34 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Example cycle where a bound on `T` uses a shorthand for `T`. This
+// creates a cycle because we have to know the bounds on `T` to figure
+// out what trait defines `Item`, but we can't know the bounds on `T`
+// without knowing how to handle `T::Item`.
+//
+// Note that in the future cases like this could perhaps become legal,
+// if we got more fine-grained about our cycle detection or changed
+// how we handle `T::Item` resolution.
+
+use std::ops::Add;
+
+// Preamble.
+trait Trait { type Item; }
+
+struct A<T>
+    where T : Trait,
+          T : Add<T::Item>
+    //~^ ERROR illegal recursive type
+{
+    data: T
+}
+
+fn main() {
+}
diff --git a/src/test/compile-fail/cycle-trait-supertrait-direct.rs b/src/test/compile-fail/cycle-trait-supertrait-direct.rs
new file mode 100644
index 00000000000..ef3fead18f6
--- /dev/null
+++ b/src/test/compile-fail/cycle-trait-supertrait-direct.rs
@@ -0,0 +1,17 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test a supertrait cycle where a trait extends itself.
+
+trait Chromosome: Chromosome {
+    //~^ ERROR unsupported cyclic reference
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/cycle-trait-supertrait-indirect.rs b/src/test/compile-fail/cycle-trait-supertrait-indirect.rs
new file mode 100644
index 00000000000..6ebd9a1bcb6
--- /dev/null
+++ b/src/test/compile-fail/cycle-trait-supertrait-indirect.rs
@@ -0,0 +1,22 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test a supertrait cycle where the first trait we find (`A`) is not
+// a direct participant in the cycle.
+
+trait A: B {
+}
+
+trait B: C { }
+
+trait C: B { }
+    //~^ ERROR unsupported cyclic reference
+
+fn main() { }
diff --git a/src/test/run-pass/associated-types-project-from-type-param-via-bound-in-where-clause.rs b/src/test/run-pass/associated-types-project-from-type-param-via-bound-in-where-clause.rs
new file mode 100644
index 00000000000..2243e00ffa1
--- /dev/null
+++ b/src/test/run-pass/associated-types-project-from-type-param-via-bound-in-where-clause.rs
@@ -0,0 +1,107 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Various uses of `T::Item` syntax where the bound that supplies
+// `Item` originates in a where-clause, not the declaration of
+// `T`. Issue #20300.
+
+use std::marker::{MarkerTrait, PhantomData};
+use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT};
+use std::sync::atomic::Ordering::SeqCst;
+
+static COUNTER: AtomicUsize = ATOMIC_USIZE_INIT;
+
+// Preamble.
+trait Trait : MarkerTrait { type Item; }
+struct Struct;
+impl Trait for Struct {
+    type Item = u32;
+}
+
+// Where-clause attached on the method which declares `T`.
+struct A;
+impl A {
+    fn foo<T>(_x: T::Item) where T: Trait {
+        COUNTER.fetch_add(1, SeqCst);
+    }
+}
+
+// Where-clause attached on the method to a parameter from the struct.
+struct B<T>(PhantomData<T>);
+impl<T> B<T> {
+    fn foo(_x: T::Item) where T: Trait {
+        COUNTER.fetch_add(10, SeqCst);
+    }
+}
+
+// Where-clause attached to free fn.
+fn c<T>(_: T::Item) where T : Trait {
+    COUNTER.fetch_add(100, SeqCst);
+}
+
+// Where-clause attached to defaulted and non-defaulted trait method.
+trait AnotherTrait {
+    fn method<T>(&self, _: T::Item) where T: Trait;
+    fn default_method<T>(&self, _: T::Item) where T: Trait {
+        COUNTER.fetch_add(1000, SeqCst);
+    }
+}
+struct D;
+impl AnotherTrait for D {
+    fn method<T>(&self, _: T::Item) where T: Trait {
+        COUNTER.fetch_add(10000, SeqCst);
+    }
+}
+
+// Where-clause attached to trait and impl containing the method.
+trait YetAnotherTrait<T>
+    where T : Trait
+{
+    fn method(&self, _: T::Item);
+    fn default_method(&self, _: T::Item) {
+        COUNTER.fetch_add(100000, SeqCst);
+    }
+}
+struct E<T>(PhantomData<T>);
+impl<T> YetAnotherTrait<T> for E<T>
+    where T : Trait
+{
+    fn method(&self, _: T::Item) {
+        COUNTER.fetch_add(1000000, SeqCst);
+    }
+}
+
+// Where-clause attached to inherent impl containing the method.
+struct F<T>(PhantomData<T>);
+impl<T> F<T> where T : Trait {
+    fn method(&self, _: T::Item) {
+        COUNTER.fetch_add(10000000, SeqCst);
+    }
+}
+
+// Where-clause attached to struct.
+#[allow(dead_code)]
+struct G<T> where T : Trait {
+    data: T::Item,
+    phantom: PhantomData<T>,
+}
+
+fn main() {
+    A::foo::<Struct>(22);
+    B::<Struct>::foo(22);
+    c::<Struct>(22);
+    D.method::<Struct>(22);
+    D.default_method::<Struct>(22);
+    E(PhantomData::<Struct>).method(22);
+    E(PhantomData::<Struct>).default_method(22);
+    F(PhantomData::<Struct>).method(22);
+    G::<Struct> { data: 22, phantom: PhantomData };
+    assert_eq!(COUNTER.load(SeqCst), 11111111);
+}
diff --git a/src/test/run-pass/cycle-generic-bound.rs b/src/test/run-pass/cycle-generic-bound.rs
new file mode 100644
index 00000000000..2388a567f30
--- /dev/null
+++ b/src/test/run-pass/cycle-generic-bound.rs
@@ -0,0 +1,18 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Regression test for #15477. This test just needs to compile.
+
+use std::marker::PhantomFn;
+
+trait Chromosome<X: Chromosome<i32>> : PhantomFn<(Self,X)> {
+}
+
+fn main() { }
diff --git a/src/test/run-pass/cycle-trait-type-trait.rs b/src/test/run-pass/cycle-trait-type-trait.rs
new file mode 100644
index 00000000000..6e16e686106
--- /dev/null
+++ b/src/test/run-pass/cycle-trait-type-trait.rs
@@ -0,0 +1,23 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test a case where a supertrait references a type that references
+// the original trait. This poses no problem at the moment.
+
+trait Chromosome: Get<Struct<i32>> {
+}
+
+trait Get<A> {
+    fn get(&self) -> A;
+}
+
+struct Struct<C:Chromosome> { c: C }
+
+fn main() { }