Separate supertrait collection from processing a `TraitDef`. This allows

us to construct trait-references and do other things without forcing a
full evaluation of the supertraits. One downside of this scheme is that
we must invoke `ensure_super_predicates` before using any construct that
might require knowing about the super-predicates.

23 files changed, 487 insertions, 417 deletions

diff --git a/src/librustc/metadata/common.rs b/src/librustc/metadata/common.rs
index b3c1d6cd15f..b28106a72e0 100644
--- a/src/librustc/metadata/common.rs
+++ b/src/librustc/metadata/common.rs
@@ -84,7 +84,6 @@ pub const tag_mod_impl: uint = 0x38;
 pub const tag_item_trait_item: uint = 0x39;
 
 pub const tag_item_trait_ref: uint = 0x3a;
-pub const tag_item_super_trait_ref: uint = 0x3b;
 
 // discriminator value for variants
 pub const tag_disr_val: uint = 0x3c;
@@ -221,8 +220,6 @@ pub const tag_struct_field_id: uint = 0x8b;
 
 pub const tag_attribute_is_sugared_doc: uint = 0x8c;
 
-pub const tag_trait_def_bounds: uint = 0x8d;
-
 pub const tag_items_data_region: uint = 0x8e;
 
 pub const tag_region_param_def: uint = 0x8f;
@@ -255,3 +252,5 @@ pub const tag_paren_sugar: uint = 0xa0;
 
 pub const tag_codemap: uint = 0xa1;
 pub const tag_codemap_filemap: uint = 0xa2;
+
+pub const tag_item_super_predicates: uint = 0xa3;
diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs
index f5c4cce0659..c7785ff4c87 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -175,14 +175,6 @@ pub fn get_provided_trait_methods<'tcx>(tcx: &ty::ctxt<'tcx>,
     decoder::get_provided_trait_methods(cstore.intr.clone(), &*cdata, def.node, tcx)
 }
 
-pub fn get_supertraits<'tcx>(tcx: &ty::ctxt<'tcx>,
-                             def: ast::DefId)
-                             -> Vec<Rc<ty::TraitRef<'tcx>>> {
-    let cstore = &tcx.sess.cstore;
-    let cdata = cstore.get_crate_data(def.krate);
-    decoder::get_supertraits(&*cdata, def.node, tcx)
-}
-
 pub fn get_type_name_if_impl(cstore: &cstore::CStore, def: ast::DefId)
                           -> Option<ast::Name> {
     let cdata = cstore.get_crate_data(def.krate);
@@ -238,6 +230,14 @@ pub fn get_predicates<'tcx>(tcx: &ty::ctxt<'tcx>, def: ast::DefId)
     decoder::get_predicates(&*cdata, def.node, tcx)
 }
 
+pub fn get_super_predicates<'tcx>(tcx: &ty::ctxt<'tcx>, def: ast::DefId)
+                                  -> ty::GenericPredicates<'tcx>
+{
+    let cstore = &tcx.sess.cstore;
+    let cdata = cstore.get_crate_data(def.krate);
+    decoder::get_super_predicates(&*cdata, def.node, tcx)
+}
+
 pub fn get_field_type<'tcx>(tcx: &ty::ctxt<'tcx>, class_id: ast::DefId,
                             def: ast::DefId) -> ty::TypeScheme<'tcx> {
     let cstore = &tcx.sess.cstore;
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 994cb3f0f25..68edae7435b 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -22,9 +22,8 @@ use metadata::csearch::MethodInfo;
 use metadata::csearch;
 use metadata::cstore;
 use metadata::tydecode::{parse_ty_data, parse_region_data, parse_def_id,
-                         parse_type_param_def_data, parse_bounds_data,
-                         parse_bare_fn_ty_data, parse_trait_ref_data,
-                         parse_predicate_data};
+                         parse_type_param_def_data, parse_bare_fn_ty_data,
+                         parse_trait_ref_data, parse_predicate_data};
 use middle::def;
 use middle::lang_items;
 use middle::subst;
@@ -260,18 +259,6 @@ fn item_trait_ref<'tcx>(doc: rbml::Doc, tcx: &ty::ctxt<'tcx>, cdata: Cmd)
     doc_trait_ref(tp, tcx, cdata)
 }
 
-fn doc_bounds<'tcx>(doc: rbml::Doc, tcx: &ty::ctxt<'tcx>, cdata: Cmd)
-                    -> ty::ParamBounds<'tcx> {
-    parse_bounds_data(doc.data, cdata.cnum, doc.start, tcx,
-                      |_, did| translate_def_id(cdata, did))
-}
-
-fn trait_def_bounds<'tcx>(doc: rbml::Doc, tcx: &ty::ctxt<'tcx>, cdata: Cmd)
-                          -> ty::ParamBounds<'tcx> {
-    let d = reader::get_doc(doc, tag_trait_def_bounds);
-    doc_bounds(d, tcx, cdata)
-}
-
 fn enum_variant_ids(item: rbml::Doc, cdata: Cmd) -> Vec<ast::DefId> {
     let mut ids: Vec<ast::DefId> = Vec::new();
     let v = tag_items_data_item_variant;
@@ -406,7 +393,6 @@ pub fn get_trait_def<'tcx>(cdata: Cmd,
 {
     let item_doc = lookup_item(item_id, cdata.data());
     let generics = doc_generics(item_doc, tcx, cdata, tag_item_generics);
-    let bounds = trait_def_bounds(item_doc, tcx, cdata);
     let unsafety = parse_unsafety(item_doc);
     let associated_type_names = parse_associated_type_names(item_doc);
     let paren_sugar = parse_paren_sugar(item_doc);
@@ -415,7 +401,6 @@ pub fn get_trait_def<'tcx>(cdata: Cmd,
         paren_sugar: paren_sugar,
         unsafety: unsafety,
         generics: generics,
-        bounds: bounds,
         trait_ref: item_trait_ref(item_doc, tcx, cdata),
         associated_type_names: associated_type_names,
     }
@@ -430,6 +415,15 @@ pub fn get_predicates<'tcx>(cdata: Cmd,
     doc_predicates(item_doc, tcx, cdata, tag_item_generics)
 }
 
+pub fn get_super_predicates<'tcx>(cdata: Cmd,
+                                  item_id: ast::NodeId,
+                                  tcx: &ty::ctxt<'tcx>)
+                                  -> ty::GenericPredicates<'tcx>
+{
+    let item_doc = lookup_item(item_id, cdata.data());
+    doc_predicates(item_doc, tcx, cdata, tag_item_super_predicates)
+}
+
 pub fn get_type<'tcx>(cdata: Cmd, id: ast::NodeId, tcx: &ty::ctxt<'tcx>)
                       -> ty::TypeScheme<'tcx>
 {
@@ -971,24 +965,6 @@ pub fn get_provided_trait_methods<'tcx>(intr: Rc<IdentInterner>,
     return result;
 }
 
-/// Returns the supertraits of the given trait.
-pub fn get_supertraits<'tcx>(cdata: Cmd, id: ast::NodeId, tcx: &ty::ctxt<'tcx>)
-                             -> Vec<Rc<ty::TraitRef<'tcx>>> {
-    let mut results = Vec::new();
-    let item_doc = lookup_item(id, cdata.data());
-    reader::tagged_docs(item_doc, tag_item_super_trait_ref, |trait_doc| {
-        // NB. Only reads the ones that *aren't* builtin-bounds. See also
-        // get_trait_def() for collecting the builtin bounds.
-        // FIXME(#8559): The builtin bounds shouldn't be encoded in the first place.
-        let trait_ref = doc_trait_ref(trait_doc, tcx, cdata);
-        if tcx.lang_items.to_builtin_kind(trait_ref.def_id).is_none() {
-            results.push(trait_ref);
-        }
-        true
-    });
-    return results;
-}
-
 pub fn get_type_name_if_impl(cdata: Cmd,
                              node_id: ast::NodeId) -> Option<ast::Name> {
     let item = lookup_item(node_id, cdata.data());
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index b9e0e452c83..c4ba2373b9f 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -206,21 +206,6 @@ pub fn write_region(ecx: &EncodeContext,
     tyencode::enc_region(rbml_w, ty_str_ctxt, r);
 }
 
-fn encode_bounds<'a, 'tcx>(rbml_w: &mut Encoder,
-                           ecx: &EncodeContext<'a, 'tcx>,
-                           bounds: &ty::ParamBounds<'tcx>,
-                           tag: uint) {
-    rbml_w.start_tag(tag);
-
-    let ty_str_ctxt = &tyencode::ctxt { diag: ecx.diag,
-                                        ds: def_to_string,
-                                        tcx: ecx.tcx,
-                                        abbrevs: &ecx.type_abbrevs };
-    tyencode::enc_bounds(rbml_w, ty_str_ctxt, bounds);
-
-    rbml_w.end_tag();
-}
-
 fn encode_type<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>,
                          rbml_w: &mut Encoder,
                          typ: Ty<'tcx>) {
@@ -728,6 +713,7 @@ fn encode_generics<'a, 'tcx>(rbml_w: &mut Encoder,
         tcx: ecx.tcx,
         abbrevs: &ecx.type_abbrevs
     };
+
     for param in generics.types.iter() {
         rbml_w.start_tag(tag_type_param_def);
         tyencode::enc_type_param_def(rbml_w, ty_str_ctxt, param);
@@ -758,6 +744,22 @@ fn encode_generics<'a, 'tcx>(rbml_w: &mut Encoder,
         rbml_w.end_tag();
     }
 
+    encode_predicates_in_current_doc(rbml_w, ecx, predicates);
+
+    rbml_w.end_tag();
+}
+
+fn encode_predicates_in_current_doc<'a,'tcx>(rbml_w: &mut Encoder,
+                                             ecx: &EncodeContext<'a,'tcx>,
+                                             predicates: &ty::GenericPredicates<'tcx>)
+{
+    let ty_str_ctxt = &tyencode::ctxt {
+        diag: ecx.diag,
+        ds: def_to_string,
+        tcx: ecx.tcx,
+        abbrevs: &ecx.type_abbrevs
+    };
+
     for (space, _, predicate) in predicates.predicates.iter_enumerated() {
         rbml_w.start_tag(tag_predicate);
 
@@ -769,7 +771,15 @@ fn encode_generics<'a, 'tcx>(rbml_w: &mut Encoder,
 
         rbml_w.end_tag();
     }
+}
 
+fn encode_predicates<'a,'tcx>(rbml_w: &mut Encoder,
+                              ecx: &EncodeContext<'a,'tcx>,
+                              predicates: &ty::GenericPredicates<'tcx>,
+                              tag: uint)
+{
+    rbml_w.start_tag(tag);
+    encode_predicates_in_current_doc(rbml_w, ecx, predicates);
     rbml_w.end_tag();
 }
 
@@ -1280,6 +1290,8 @@ fn encode_info_for_item(ecx: &EncodeContext,
         encode_paren_sugar(rbml_w, trait_def.paren_sugar);
         encode_associated_type_names(rbml_w, &trait_def.associated_type_names);
         encode_generics(rbml_w, ecx, &trait_def.generics, &trait_predicates, tag_item_generics);
+        encode_predicates(rbml_w, ecx, &ty::lookup_super_predicates(tcx, def_id),
+                          tag_item_super_predicates);
         encode_trait_ref(rbml_w, ecx, &*trait_def.trait_ref, tag_item_trait_ref);
         encode_name(rbml_w, item.ident.name);
         encode_attributes(rbml_w, &item.attrs);
@@ -1304,8 +1316,6 @@ fn encode_info_for_item(ecx: &EncodeContext,
         }
         encode_path(rbml_w, path.clone());
 
-        encode_bounds(rbml_w, ecx, &trait_def.bounds, tag_trait_def_bounds);
-
         // Encode the implementations of this trait.
         encode_extension_implementations(ecx, rbml_w, def_id);
 
diff --git a/src/librustc/middle/traits/object_safety.rs b/src/librustc/middle/traits/object_safety.rs
index 64835a666fa..881487a2dad 100644
--- a/src/librustc/middle/traits/object_safety.rs
+++ b/src/librustc/middle/traits/object_safety.rs
@@ -22,7 +22,7 @@ use super::elaborate_predicates;
 
 use middle::subst::{self, SelfSpace, TypeSpace};
 use middle::traits;
-use middle::ty::{self, Ty};
+use middle::ty::{self, ToPolyTraitRef, Ty};
 use std::rc::Rc;
 use syntax::ast;
 use util::ppaux::Repr;
@@ -128,9 +128,12 @@ fn supertraits_reference_self<'tcx>(tcx: &ty::ctxt<'tcx>,
 {
     let trait_def = ty::lookup_trait_def(tcx, trait_def_id);
     let trait_ref = trait_def.trait_ref.clone();
-    let predicates = ty::predicates_for_trait_ref(tcx, &ty::Binder(trait_ref));
+    let trait_ref = trait_ref.to_poly_trait_ref();
+    let predicates = ty::lookup_super_predicates(tcx, trait_def_id);
     predicates
+        .predicates
         .into_iter()
+        .map(|predicate| predicate.subst_supertrait(tcx, &trait_ref))
         .any(|predicate| {
             match predicate {
                 ty::Predicate::Trait(ref data) => {
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 470315c78f8..36efec0a367 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -1455,9 +1455,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                             let principal =
                                 data.principal_trait_ref_with_self_ty(self.tcx(),
                                                                       self.tcx().types.err);
+                            let desired_def_id = obligation.predicate.def_id();
                             for tr in util::supertraits(self.tcx(), principal) {
-                                let td = ty::lookup_trait_def(self.tcx(), tr.def_id());
-                                if td.bounds.builtin_bounds.contains(&bound) {
+                                if tr.def_id() == desired_def_id {
                                     return Ok(If(Vec::new()))
                                 }
                             }
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index fdd8d2ee977..0366fc07855 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -117,9 +117,17 @@ impl<'cx, 'tcx> Elaborator<'cx, 'tcx> {
     fn push(&mut self, predicate: &ty::Predicate<'tcx>) {
         match *predicate {
             ty::Predicate::Trait(ref data) => {
-                let mut predicates =
-                    ty::predicates_for_trait_ref(self.tcx,
-                                                 &data.to_poly_trait_ref());
+                // Predicates declared on the trait.
+                let predicates = ty::lookup_super_predicates(self.tcx, data.def_id());
+
+                let mut predicates: Vec<_> =
+                    predicates.predicates
+                              .iter()
+                              .map(|p| p.subst_supertrait(self.tcx, &data.to_poly_trait_ref()))
+                              .collect();
+
+                debug!("super_predicates: data={} predicates={}",
+                       data.repr(self.tcx), predicates.repr(self.tcx));
 
                 // Only keep those bounds that we haven't already
                 // seen.  This is necessary to prevent infinite
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 36c42b70795..dfdb4002be2 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -17,7 +17,6 @@ pub use self::InferTy::*;
 pub use self::InferRegion::*;
 pub use self::ImplOrTraitItemId::*;
 pub use self::ClosureKind::*;
-pub use self::ast_ty_to_ty_cache_entry::*;
 pub use self::Variance::*;
 pub use self::AutoAdjustment::*;
 pub use self::Representability::*;
@@ -266,12 +265,6 @@ pub struct creader_cache_key {
     pub len: uint
 }
 
-#[derive(Copy)]
-pub enum ast_ty_to_ty_cache_entry<'tcx> {
-    atttce_unresolved,  /* not resolved yet */
-    atttce_resolved(Ty<'tcx>)  /* resolved to a type, irrespective of region */
-}
-
 #[derive(Clone, PartialEq, RustcDecodable, RustcEncodable)]
 pub struct ItemVariances {
     pub types: VecPerParamSpace<Variance>,
@@ -716,6 +709,14 @@ pub struct ctxt<'tcx> {
     /// associated predicates.
     pub predicates: RefCell<DefIdMap<GenericPredicates<'tcx>>>,
 
+    /// Maps from the def-id of a trait to the list of
+    /// super-predicates. This is a subset of the full list of
+    /// predicates. We store these in a separate map because we must
+    /// evaluate them even during type conversion, often before the
+    /// full predicates are available (note that supertraits have
+    /// additional acyclicity requirements).
+    pub super_predicates: RefCell<DefIdMap<GenericPredicates<'tcx>>>,
+
     /// Maps from node-id of a trait object cast (like `foo as
     /// Box<Trait>`) to the trait reference.
     pub object_cast_map: ObjectCastMap<'tcx>,
@@ -727,7 +728,7 @@ pub struct ctxt<'tcx> {
     pub rcache: RefCell<FnvHashMap<creader_cache_key, Ty<'tcx>>>,
     pub short_names_cache: RefCell<FnvHashMap<Ty<'tcx>, String>>,
     pub tc_cache: RefCell<FnvHashMap<Ty<'tcx>, TypeContents>>,
-    pub ast_ty_to_ty_cache: RefCell<NodeMap<ast_ty_to_ty_cache_entry<'tcx>>>,
+    pub ast_ty_to_ty_cache: RefCell<NodeMap<Ty<'tcx>>>,
     pub enum_var_cache: RefCell<DefIdMap<Rc<Vec<Rc<VariantInfo<'tcx>>>>>>,
     pub ty_param_defs: RefCell<NodeMap<TypeParameterDef<'tcx>>>,
     pub adjustments: RefCell<NodeMap<AutoAdjustment<'tcx>>>,
@@ -1352,7 +1353,7 @@ pub enum sty<'tcx> {
     /// definition and not a concrete use of it. To get the correct `ty_enum`
     /// from the tcx, use the `NodeId` from the `ast::Ty` and look it up in
     /// the `ast_ty_to_ty_cache`. This is probably true for `ty_struct` as
-    /// well.`
+    /// well.
     ty_enum(DefId, &'tcx Substs<'tcx>),
     ty_uniq(Ty<'tcx>),
     ty_str,
@@ -1495,6 +1496,27 @@ impl<'tcx> PolyTraitRef<'tcx> {
 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
 pub struct Binder<T>(pub T);
 
+impl<T> Binder<T> {
+    /// Skips the binder and returns the "bound" value. This is a
+    /// risky thing to do because it's easy to get confused about
+    /// debruijn indices and the like. It is usually better to
+    /// discharge the binder using `no_late_bound_regions` or
+    /// `replace_late_bound_regions` or something like
+    /// that. `skip_binder` is only valid when you are either
+    /// extracting data that has nothing to do with bound regions, you
+    /// are doing some sort of test that does not involve bound
+    /// regions, or you are being very careful about your depth
+    /// accounting.
+    ///
+    /// Some examples where `skip_binder` is reasonable:
+    /// - extracting the def-id from a PolyTraitRef;
+    /// - compariing the self type of a PolyTraitRef to see if it is equal to
+    ///   a type parameter `X`, since the type `X`  does not reference any regions
+    pub fn skip_binder(&self) -> &T {
+        &self.0
+    }
+}
+
 #[derive(Clone, Copy, PartialEq)]
 pub enum IntVarValue {
     IntType(ast::IntTy),
@@ -1817,6 +1839,16 @@ impl<'tcx> GenericPredicates<'tcx> {
             predicates: self.predicates.subst(tcx, substs),
         }
     }
+
+    pub fn instantiate_supertrait(&self,
+                                  tcx: &ty::ctxt<'tcx>,
+                                  poly_trait_ref: &ty::PolyTraitRef<'tcx>)
+                                  -> InstantiatedPredicates<'tcx>
+    {
+        InstantiatedPredicates {
+            predicates: self.predicates.map(|pred| pred.subst_supertrait(tcx, poly_trait_ref))
+        }
+    }
 }
 
 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
@@ -1840,6 +1872,93 @@ pub enum Predicate<'tcx> {
     Projection(PolyProjectionPredicate<'tcx>),
 }
 
+impl<'tcx> Predicate<'tcx> {
+    /// Performs a substituion suitable for going from a
+    /// poly-trait-ref to supertraits that must hold if that
+    /// poly-trait-ref holds. This is slightly different from a normal
+    /// substitution in terms of what happens with bound regions.  See
+    /// lengthy comment below for details.
+    pub fn subst_supertrait(&self,
+                            tcx: &ty::ctxt<'tcx>,
+                            trait_ref: &ty::PolyTraitRef<'tcx>)
+                            -> ty::Predicate<'tcx>
+    {
+        // The interaction between HRTB and supertraits is not entirely
+        // obvious. Let me walk you (and myself) through an example.
+        //
+        // Let's start with an easy case. Consider two traits:
+        //
+        //     trait Foo<'a> : Bar<'a,'a> { }
+        //     trait Bar<'b,'c> { }
+        //
+        // Now, if we have a trait reference `for<'x> T : Foo<'x>`, then
+        // we can deduce that `for<'x> T : Bar<'x,'x>`. Basically, if we
+        // knew that `Foo<'x>` (for any 'x) then we also know that
+        // `Bar<'x,'x>` (for any 'x). This more-or-less falls out from
+        // normal substitution.
+        //
+        // In terms of why this is sound, the idea is that whenever there
+        // is an impl of `T:Foo<'a>`, it must show that `T:Bar<'a,'a>`
+        // holds.  So if there is an impl of `T:Foo<'a>` that applies to
+        // all `'a`, then we must know that `T:Bar<'a,'a>` holds for all
+        // `'a`.
+        //
+        // Another example to be careful of is this:
+        //
+        //     trait Foo1<'a> : for<'b> Bar1<'a,'b> { }
+        //     trait Bar1<'b,'c> { }
+        //
+        // Here, if we have `for<'x> T : Foo1<'x>`, then what do we know?
+        // The answer is that we know `for<'x,'b> T : Bar1<'x,'b>`. The
+        // reason is similar to the previous example: any impl of
+        // `T:Foo1<'x>` must show that `for<'b> T : Bar1<'x, 'b>`.  So
+        // basically we would want to collapse the bound lifetimes from
+        // the input (`trait_ref`) and the supertraits.
+        //
+        // To achieve this in practice is fairly straightforward. Let's
+        // consider the more complicated scenario:
+        //
+        // - We start out with `for<'x> T : Foo1<'x>`. In this case, `'x`
+        //   has a De Bruijn index of 1. We want to produce `for<'x,'b> T : Bar1<'x,'b>`,
+        //   where both `'x` and `'b` would have a DB index of 1.
+        //   The substitution from the input trait-ref is therefore going to be
+        //   `'a => 'x` (where `'x` has a DB index of 1).
+        // - The super-trait-ref is `for<'b> Bar1<'a,'b>`, where `'a` is an
+        //   early-bound parameter and `'b' is a late-bound parameter with a
+        //   DB index of 1.
+        // - If we replace `'a` with `'x` from the input, it too will have
+        //   a DB index of 1, and thus we'll have `for<'x,'b> Bar1<'x,'b>`
+        //   just as we wanted.
+        //
+        // There is only one catch. If we just apply the substitution `'a
+        // => 'x` to `for<'b> Bar1<'a,'b>`, the substitution code will
+        // adjust the DB index because we substituting into a binder (it
+        // tries to be so smart...) resulting in `for<'x> for<'b>
+        // Bar1<'x,'b>` (we have no syntax for this, so use your
+        // imagination). Basically the 'x will have DB index of 2 and 'b
+        // will have DB index of 1. Not quite what we want. So we apply
+        // the substitution to the *contents* of the trait reference,
+        // rather than the trait reference itself (put another way, the
+        // substitution code expects equal binding levels in the values
+        // from the substitution and the value being substituted into, and
+        // this trick achieves that).
+
+        let substs = &trait_ref.0.substs;
+        match *self {
+            Predicate::Trait(ty::Binder(ref data)) =>
+                Predicate::Trait(ty::Binder(data.subst(tcx, substs))),
+            Predicate::Equate(ty::Binder(ref data)) =>
+                Predicate::Equate(ty::Binder(data.subst(tcx, substs))),
+            Predicate::RegionOutlives(ty::Binder(ref data)) =>
+                Predicate::RegionOutlives(ty::Binder(data.subst(tcx, substs))),
+            Predicate::TypeOutlives(ty::Binder(ref data)) =>
+                Predicate::TypeOutlives(ty::Binder(data.subst(tcx, substs))),
+            Predicate::Projection(ty::Binder(ref data)) =>
+                Predicate::Projection(ty::Binder(data.subst(tcx, substs))),
+        }
+    }
+}
+
 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
 pub struct TraitPredicate<'tcx> {
     pub trait_ref: Rc<TraitRef<'tcx>>
@@ -2324,9 +2443,6 @@ pub struct TraitDef<'tcx> {
     /// implements the trait.
     pub generics: Generics<'tcx>,
 
-    /// The "supertrait" bounds.
-    pub bounds: ParamBounds<'tcx>,
-
     pub trait_ref: Rc<ty::TraitRef<'tcx>>,
 
     /// A list of the associated types defined in this trait. Useful
@@ -2451,6 +2567,7 @@ pub fn mk_ctxt<'tcx>(s: Session,
         impl_trait_refs: RefCell::new(NodeMap()),
         trait_defs: RefCell::new(DefIdMap()),
         predicates: RefCell::new(DefIdMap()),
+        super_predicates: RefCell::new(DefIdMap()),
         object_cast_map: RefCell::new(NodeMap()),
         map: map,
         intrinsic_defs: RefCell::new(DefIdMap()),
@@ -5432,7 +5549,7 @@ pub fn lookup_trait_def<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
     })
 }
 
-/// Given the did of a trait, returns its full set of predicates.
+/// Given the did of an item, returns its full set of predicates.
 pub fn lookup_predicates<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
                                 -> GenericPredicates<'tcx>
 {
@@ -5442,117 +5559,14 @@ pub fn lookup_predicates<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
     })
 }
 
-/// Given a reference to a trait, returns the "superbounds" declared
-/// on the trait, with appropriate substitutions applied. Basically,
-/// this applies a filter to the where clauses on the trait, returning
-/// those that have the form:
-///
-///     Self : SuperTrait<...>
-///     Self : 'region
-pub fn predicates_for_trait_ref<'tcx>(tcx: &ctxt<'tcx>,
-                                      trait_ref: &PolyTraitRef<'tcx>)
-                                      -> Vec<ty::Predicate<'tcx>>
+/// Given the did of a trait, returns its superpredicates.
+pub fn lookup_super_predicates<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
+                                     -> GenericPredicates<'tcx>
 {
-    let trait_def = lookup_trait_def(tcx, trait_ref.def_id());
-
-    debug!("bounds_for_trait_ref(trait_def={:?}, trait_ref={:?})",
-           trait_def.repr(tcx), trait_ref.repr(tcx));
-
-    // The interaction between HRTB and supertraits is not entirely
-    // obvious. Let me walk you (and myself) through an example.
-    //
-    // Let's start with an easy case. Consider two traits:
-    //
-    //     trait Foo<'a> : Bar<'a,'a> { }
-    //     trait Bar<'b,'c> { }
-    //
-    // Now, if we have a trait reference `for<'x> T : Foo<'x>`, then
-    // we can deduce that `for<'x> T : Bar<'x,'x>`. Basically, if we
-    // knew that `Foo<'x>` (for any 'x) then we also know that
-    // `Bar<'x,'x>` (for any 'x). This more-or-less falls out from
-    // normal substitution.
-    //
-    // In terms of why this is sound, the idea is that whenever there
-    // is an impl of `T:Foo<'a>`, it must show that `T:Bar<'a,'a>`
-    // holds.  So if there is an impl of `T:Foo<'a>` that applies to
-    // all `'a`, then we must know that `T:Bar<'a,'a>` holds for all
-    // `'a`.
-    //
-    // Another example to be careful of is this:
-    //
-    //     trait Foo1<'a> : for<'b> Bar1<'a,'b> { }
-    //     trait Bar1<'b,'c> { }
-    //
-    // Here, if we have `for<'x> T : Foo1<'x>`, then what do we know?
-    // The answer is that we know `for<'x,'b> T : Bar1<'x,'b>`. The
-    // reason is similar to the previous example: any impl of
-    // `T:Foo1<'x>` must show that `for<'b> T : Bar1<'x, 'b>`.  So
-    // basically we would want to collapse the bound lifetimes from
-    // the input (`trait_ref`) and the supertraits.
-    //
-    // To achieve this in practice is fairly straightforward. Let's
-    // consider the more complicated scenario:
-    //
-    // - We start out with `for<'x> T : Foo1<'x>`. In this case, `'x`
-    //   has a De Bruijn index of 1. We want to produce `for<'x,'b> T : Bar1<'x,'b>`,
-    //   where both `'x` and `'b` would have a DB index of 1.
-    //   The substitution from the input trait-ref is therefore going to be
-    //   `'a => 'x` (where `'x` has a DB index of 1).
-    // - The super-trait-ref is `for<'b> Bar1<'a,'b>`, where `'a` is an
-    //   early-bound parameter and `'b' is a late-bound parameter with a
-    //   DB index of 1.
-    // - If we replace `'a` with `'x` from the input, it too will have
-    //   a DB index of 1, and thus we'll have `for<'x,'b> Bar1<'x,'b>`
-    //   just as we wanted.
-    //
-    // There is only one catch. If we just apply the substitution `'a
-    // => 'x` to `for<'b> Bar1<'a,'b>`, the substitution code will
-    // adjust the DB index because we substituting into a binder (it
-    // tries to be so smart...) resulting in `for<'x> for<'b>
-    // Bar1<'x,'b>` (we have no syntax for this, so use your
-    // imagination). Basically the 'x will have DB index of 2 and 'b
-    // will have DB index of 1. Not quite what we want. So we apply
-    // the substitution to the *contents* of the trait reference,
-    // rather than the trait reference itself (put another way, the
-    // substitution code expects equal binding levels in the values
-    // from the substitution and the value being substituted into, and
-    // this trick achieves that).
-
-    // Carefully avoid the binder introduced by each trait-ref by
-    // substituting over the substs, not the trait-refs themselves,
-    // thus achieving the "collapse" described in the big comment
-    // above.
-    let trait_bounds: Vec<_> =
-        trait_def.bounds.trait_bounds
-        .iter()
-        .map(|poly_trait_ref| ty::Binder(poly_trait_ref.0.subst(tcx, trait_ref.substs())))
-        .collect();
-
-    let projection_bounds: Vec<_> =
-        trait_def.bounds.projection_bounds
-        .iter()
-        .map(|poly_proj| ty::Binder(poly_proj.0.subst(tcx, trait_ref.substs())))
-        .collect();
-
-    debug!("bounds_for_trait_ref: trait_bounds={} projection_bounds={}",
-           trait_bounds.repr(tcx),
-           projection_bounds.repr(tcx));
-
-    // The region bounds and builtin bounds do not currently introduce
-    // binders so we can just substitute in a straightforward way here.
-    let region_bounds =
-        trait_def.bounds.region_bounds.subst(tcx, trait_ref.substs());
-    let builtin_bounds =
-        trait_def.bounds.builtin_bounds.subst(tcx, trait_ref.substs());
-
-    let bounds = ty::ParamBounds {
-        trait_bounds: trait_bounds,
-        region_bounds: region_bounds,
-        builtin_bounds: builtin_bounds,
-        projection_bounds: projection_bounds,
-    };
-
-    predicates(tcx, trait_ref.self_ty(), &bounds)
+    memoized(&cx.super_predicates, did, |did: DefId| {
+        assert!(did.krate != ast::LOCAL_CRATE);
+        csearch::get_super_predicates(cx, did)
+    })
 }
 
 pub fn predicates<'tcx>(
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 0eeb746022c..09a12254414 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -820,9 +820,8 @@ impl<'tcx> Repr<'tcx> for ty::TraitRef<'tcx> {
 
 impl<'tcx> Repr<'tcx> for ty::TraitDef<'tcx> {
     fn repr(&self, tcx: &ctxt<'tcx>) -> String {
-        format!("TraitDef(generics={}, bounds={}, trait_ref={})",
+        format!("TraitDef(generics={}, trait_ref={})",
                 self.generics.repr(tcx),
-                self.bounds.repr(tcx),
                 self.trait_ref.repr(tcx))
     }
 }
diff --git a/src/librustc_lint/builtin.rs b/src/librustc_lint/builtin.rs
index 22311a71583..3682fdb74b7 100644
--- a/src/librustc_lint/builtin.rs
+++ b/src/librustc_lint/builtin.rs
@@ -432,8 +432,8 @@ impl<'a, 'tcx> ImproperCTypesVisitor<'a, 'tcx> {
             }
             def::DefTy(..) => {
                 let tty = match self.cx.tcx.ast_ty_to_ty_cache.borrow().get(&id) {
-                    Some(&ty::atttce_resolved(t)) => t,
-                    _ => panic!("ast_ty_to_ty_cache was incomplete after typeck!")
+                    Some(&t) => t,
+                    None => panic!("ast_ty_to_ty_cache was incomplete after typeck!")
                 };
 
                 if !ty::is_ffi_safe(self.cx.tcx, tty) {
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index e70bef5a44f..0da2c86066a 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -59,7 +59,6 @@ use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty};
 use rscope::{self, UnelidableRscope, RegionScope, ElidableRscope,
              ObjectLifetimeDefaultRscope, ShiftedRscope, BindingRscope};
 use util::common::{ErrorReported, FN_OUTPUT_NAME};
-use util::nodemap::DefIdMap;
 use util::ppaux::{self, Repr, UserString};
 
 use std::iter::{repeat, AdditiveIterator};
@@ -73,15 +72,30 @@ use syntax::print::pprust;
 pub trait AstConv<'tcx> {
     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
 
+    /// Identify the type scheme for an item with a type, like a type
+    /// alias, fn, or struct. This allows you to figure out the set of
+    /// type parameters defined on the item.
     fn get_item_type_scheme(&self, span: Span, id: ast::DefId)
                             -> Result<ty::TypeScheme<'tcx>, ErrorReported>;
 
+    /// Returns the `TraitDef` for a given trait. This allows you to
+    /// figure out the set of type parameters defined on the trait.
     fn get_trait_def(&self, span: Span, id: ast::DefId)
                      -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>;
 
+    /// Ensure that the super-predicates for the trait with the given
+    /// id are available and also for the transitive set of
+    /// super-predicates.
+    fn ensure_super_predicates(&self, span: Span, id: ast::DefId)
+                               -> Result<(), ErrorReported>;
+
+    /// Returns the set of bounds in scope for the type parameter with
+    /// the given id.
     fn get_type_parameter_bounds(&self, span: Span, def_id: ast::NodeId)
                                  -> Result<Vec<ty::PolyTraitRef<'tcx>>, ErrorReported>;
 
+    /// Returns true if the trait with id `trait_def_id` defines an
+    /// associated type with the name `name`.
     fn trait_defines_associated_type_named(&self, trait_def_id: ast::DefId, name: ast::Name)
                                            -> bool;
 
@@ -813,6 +827,8 @@ fn ast_type_binding_to_projection_predicate<'tcx>(
                                               tcx.mk_substs(dummy_substs)));
     }
 
+    try!(this.ensure_super_predicates(binding.span, trait_ref.def_id));
+
     let mut candidates: Vec<ty::PolyTraitRef> =
         traits::supertraits(tcx, trait_ref.to_poly_trait_ref())
         .filter(|r| this.trait_defines_associated_type_named(r.def_id(), binding.item_name))
@@ -1032,10 +1048,15 @@ fn associated_path_def_to_ty<'tcx>(this: &AstConv<'tcx>,
 
     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());
+    let bounds = match this.get_type_parameter_bounds(span, ty_param_node_id) {
+        Ok(v) => v,
+        Err(ErrorReported) => { return (tcx.types.err, ty_path_def); }
+    };
+
+    // ensure the super predicates and stop if we encountered an error
+    if bounds.iter().any(|b| this.ensure_super_predicates(span, b.def_id()).is_err()) {
+        return (this.tcx().types.err, ty_path_def);
+    }
 
     let mut suitable_bounds: Vec<_> =
         traits::transitive_bounds(tcx, &bounds)
@@ -1268,20 +1289,9 @@ pub fn ast_ty_to_ty<'tcx>(this: &AstConv<'tcx>,
 
     let tcx = this.tcx();
 
-    let mut ast_ty_to_ty_cache = tcx.ast_ty_to_ty_cache.borrow_mut();
-    match ast_ty_to_ty_cache.get(&ast_ty.id) {
-        Some(&ty::atttce_resolved(ty)) => return ty,
-        Some(&ty::atttce_unresolved) => {
-            span_err!(tcx.sess, ast_ty.span, E0246,
-                                "illegal recursive type; insert an enum \
-                                 or struct in the cycle, if this is \
-                                 desired");
-            return this.tcx().types.err;
-        }
-        None => { /* go on */ }
+    if let Some(&ty) = tcx.ast_ty_to_ty_cache.borrow().get(&ast_ty.id) {
+        return ty;
     }
-    ast_ty_to_ty_cache.insert(ast_ty.id, ty::atttce_unresolved);
-    drop(ast_ty_to_ty_cache);
 
     let typ = match ast_ty.node {
         ast::TyVec(ref ty) => {
@@ -1414,7 +1424,7 @@ pub fn ast_ty_to_ty<'tcx>(this: &AstConv<'tcx>,
         }
     };
 
-    tcx.ast_ty_to_ty_cache.borrow_mut().insert(ast_ty.id, ty::atttce_resolved(typ));
+    tcx.ast_ty_to_ty_cache.borrow_mut().insert(ast_ty.id, typ);
     return typ;
 }
 
@@ -1831,6 +1841,10 @@ fn compute_object_lifetime_bound<'tcx>(
         return ast_region_to_region(tcx, r);
     }
 
+    if let Err(ErrorReported) = this.ensure_super_predicates(span,principal_trait_ref.def_id()) {
+        return ty::ReStatic;
+    }
+
     // No explicit region bound specified. Therefore, examine trait
     // bounds and see if we can derive region bounds from those.
     let derived_region_bounds =
@@ -1916,34 +1930,11 @@ pub fn partition_bounds<'a>(tcx: &ty::ctxt,
     let mut builtin_bounds = ty::empty_builtin_bounds();
     let mut region_bounds = Vec::new();
     let mut trait_bounds = Vec::new();
-    let mut trait_def_ids = DefIdMap();
     for ast_bound in ast_bounds {
         match *ast_bound {
             ast::TraitTyParamBound(ref b, ast::TraitBoundModifier::None) => {
                 match ::lookup_full_def(tcx, b.trait_ref.path.span, b.trait_ref.ref_id) {
                     def::DefTrait(trait_did) => {
-                        match trait_def_ids.get(&trait_did) {
-                            // Already seen this trait. We forbid
-                            // duplicates in the list (for some
-                            // reason).
-                            Some(span) => {
-                                span_err!(
-                                    tcx.sess, b.trait_ref.path.span, E0127,
-                                    "trait `{}` already appears in the \
-                                     list of bounds",
-                                    b.trait_ref.path.user_string(tcx));
-                                tcx.sess.span_note(
-                                    *span,
-                                    "previous appearance is here");
-
-                                continue;
-                            }
-
-                            None => { }
-                        }
-
-                        trait_def_ids.insert(trait_did, b.trait_ref.path.span);
-
                         if ty::try_add_builtin_trait(tcx,
                                                      trait_did,
                                                      &mut builtin_bounds) {
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index fbf002b709e..718804d317f 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -456,13 +456,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
         debug!("elaborate_bounds(bounds={})", bounds.repr(self.tcx()));
 
         let tcx = self.tcx();
-        let mut cache = HashSet::new();
         for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
-            // Already visited this trait, skip it.
-            if !cache.insert(bound_trait_ref.def_id()) {
-                continue;
-            }
-
             let (pos, method) = match trait_method(tcx,
                                                    bound_trait_ref.def_id(),
                                                    self.method_name) {
@@ -1269,10 +1263,12 @@ impl<'tcx> Candidate<'tcx> {
 
     fn to_trait_data(&self) -> Option<(ast::DefId,MethodIndex)> {
         match self.kind {
-            InherentImplCandidate(..) |
-            ObjectCandidate(..) => {
+            InherentImplCandidate(..) => {
                 None
             }
+            ObjectCandidate(trait_def_id, method_num, _) => {
+                Some((trait_def_id, method_num))
+            }
             ClosureCandidate(trait_def_id, method_num) => {
                 Some((trait_def_id, method_num))
             }
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 16cef193e45..9db98bf00cd 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1218,6 +1218,11 @@ impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> {
         Ok(ty::lookup_trait_def(self.tcx(), id))
     }
 
+    fn ensure_super_predicates(&self, _: Span, _: ast::DefId) -> Result<(), ErrorReported> {
+        // all super predicates are ensured during collect pass
+        Ok(())
+    }
+
     fn get_free_substs(&self) -> Option<&Substs<'tcx>> {
         Some(&self.inh.param_env.free_substs)
     }
diff --git a/src/librustc_typeck/check/wf.rs b/src/librustc_typeck/check/wf.rs
index e024526d001..fcc5eea7606 100644
--- a/src/librustc_typeck/check/wf.rs
+++ b/src/librustc_typeck/check/wf.rs
@@ -281,12 +281,13 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
 
             // Find the supertrait bounds. This will add `int:Bar`.
             let poly_trait_ref = ty::Binder(trait_ref);
-            let predicates = ty::predicates_for_trait_ref(fcx.tcx(), &poly_trait_ref);
+            let predicates = ty::lookup_super_predicates(fcx.tcx(), poly_trait_ref.def_id());
+            let predicates = predicates.instantiate_supertrait(fcx.tcx(), &poly_trait_ref);
             let predicates = {
                 let selcx = &mut traits::SelectionContext::new(fcx.infcx(), fcx);
                 traits::normalize(selcx, cause.clone(), &predicates)
             };
-            for predicate in predicates.value {
+            for predicate in predicates.value.predicates {
                 fcx.register_predicate(traits::Obligation::new(cause.clone(), predicate));
             }
             for obligation in predicates.obligations {
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 1ba49714bcf..8f9ede32ae4 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -26,35 +26,17 @@ represented by an instance of `ty::TypeScheme`.  This combines the
 core type along with a list of the bounds for each parameter. Type
 parameters themselves are represented as `ty_param()` instances.
 
-The phasing of type conversion is somewhat complicated. There are a
-number of possible cycles that can arise.
-
-Converting types can require:
-
-1. `Foo<X>` where `Foo` is a type alias, or trait requires knowing:
-   - number of region / type parameters
-   - for type parameters, `T:'a` annotations to control defaults for object lifetimes
-   - defaults for type parameters (which are themselves types!)
-2. `Foo<X>` where `Foo` is a type alias requires knowing what `Foo` expands to
-3. Translating `SomeTrait` with no explicit lifetime bound requires knowing
-   - supertraits of `SomeTrait`
-4. Translating `T::X` (vs `<T as Trait>::X`) requires knowing
-   - bounds on `T`
-   - supertraits of those bounds
-
-So as you can see, in general translating types requires knowing the
-trait hierarchy. But this gets a bit tricky because translating the
-trait hierarchy requires converting the types that appear in trait
-references. One potential saving grace is that in general knowing the
-trait hierarchy is only necessary for shorthands like `T::X` or
-handling omitted lifetime bounds on object types. Therefore, if we are
-lazy about expanding out the trait hierachy, users can sever cycles if
-necessary. Lazy expansion is also needed for type aliases.
-
-This system is not perfect yet. Currently, we "convert" types and
-traits in three phases (note that conversion only affects the types of
-items / enum variants / methods; it does not e.g. compute the types of
-individual expressions):
+The phasing of type conversion is somewhat complicated. There is no
+clear set of phases we can enforce (e.g., converting traits first,
+then types, or something like that) because the user can introduce
+arbitrary interdependencies. So instead we generally convert things
+lazilly and on demand, and include logic that checks for cycles.
+Demand is driven by calls to `AstConv::get_item_type_scheme` or
+`AstConv::lookup_trait_def`.
+
+Currently, we "convert" types and traits in three phases (note that
+conversion only affects the types of items / enum variants / methods;
+it does not e.g. compute the types of individual expressions):
 
 0. Intrinsics
 1. Trait definitions
@@ -64,16 +46,13 @@ Conversion itself is done by simply walking each of the items in turn
 and invoking an appropriate function (e.g., `trait_def_of_item` or
 `convert_item`). However, it is possible that while converting an
 item, we may need to compute the *type scheme* or *trait definition*
-for other items. This is a kind of shallow conversion that is
-triggered on demand by calls to `AstConv::get_item_type_scheme` or
-`AstConv::lookup_trait_def`. It is possible for cycles to result from
-this (e.g., `type A = B; type B = A;`), in which case astconv
-(currently) reports the error.
+for other items.
 
 There are some shortcomings in this design:
 
-- Cycles through trait definitions (e.g. supertraits) are not currently
-  detected by astconv. (#12511)
+- Before walking the set of supertraits for a given trait, you must
+  call `ensure_super_predicates` on that trait def-id. Otherwise,
+  `lookup_super_predicates` will result in ICEs.
 - Because the type scheme includes defaults, cycles through type
   parameter defaults are illegal even if those defaults are never
   employed. This is not necessarily a bug.
@@ -169,6 +148,7 @@ struct ItemCtxt<'a,'tcx:'a> {
 enum AstConvRequest {
     GetItemTypeScheme(ast::DefId),
     GetTraitDef(ast::DefId),
+    EnsureSuperPredicates(ast::DefId),
     GetTypeParameterBounds(ast::NodeId),
 }
 
@@ -245,7 +225,7 @@ impl<'a,'tcx> CrateCtxt<'a,'tcx> {
                         request: AstConvRequest,
                         code: F)
                         -> Result<R,ErrorReported>
-        where F: FnOnce() -> R
+        where F: FnOnce() -> Result<R,ErrorReported>
     {
         {
             let mut stack = self.stack.borrow_mut();
@@ -263,7 +243,7 @@ impl<'a,'tcx> CrateCtxt<'a,'tcx> {
         let result = code();
 
         self.stack.borrow_mut().pop();
-        Ok(result)
+        result
     }
 
     fn report_cycle(&self,
@@ -284,6 +264,11 @@ impl<'a,'tcx> CrateCtxt<'a,'tcx> {
                     &format!("the cycle begins when processing `{}`...",
                              ty::item_path_str(tcx, def_id)));
             }
+            AstConvRequest::EnsureSuperPredicates(def_id) => {
+                tcx.sess.note(
+                    &format!("the cycle begins when computing the supertraits of `{}`...",
+                             ty::item_path_str(tcx, def_id)));
+            }
             AstConvRequest::GetTypeParameterBounds(id) => {
                 let def = tcx.type_parameter_def(id);
                 tcx.sess.note(
@@ -301,6 +286,11 @@ impl<'a,'tcx> CrateCtxt<'a,'tcx> {
                         &format!("...which then requires processing `{}`...",
                                  ty::item_path_str(tcx, def_id)));
                 }
+                AstConvRequest::EnsureSuperPredicates(def_id) => {
+                    tcx.sess.note(
+                        &format!("...which then requires computing the supertraits of `{}`...",
+                                 ty::item_path_str(tcx, def_id)));
+                }
                 AstConvRequest::GetTypeParameterBounds(id) => {
                     let def = tcx.type_parameter_def(id);
                     tcx.sess.note(
@@ -318,6 +308,12 @@ impl<'a,'tcx> CrateCtxt<'a,'tcx> {
                     &format!("...which then again requires processing `{}`, completing the cycle.",
                              ty::item_path_str(tcx, def_id)));
             }
+            AstConvRequest::EnsureSuperPredicates(def_id) => {
+                tcx.sess.note(
+                    &format!("...which then again requires computing the supertraits of `{}`, \
+                              completing the cycle.",
+                             ty::item_path_str(tcx, def_id)));
+            }
             AstConvRequest::GetTypeParameterBounds(id) => {
                 let def = tcx.type_parameter_def(id);
                 tcx.sess.note(
@@ -327,6 +323,41 @@ impl<'a,'tcx> CrateCtxt<'a,'tcx> {
             }
         }
     }
+
+    /// Loads the trait def for a given trait, returning ErrorReported if a cycle arises.
+    fn get_trait_def(&self, trait_id: ast::DefId)
+                     -> Rc<ty::TraitDef<'tcx>>
+    {
+        let tcx = self.tcx;
+
+        if trait_id.krate != ast::LOCAL_CRATE {
+            return ty::lookup_trait_def(tcx, trait_id)
+        }
+
+        let item = match tcx.map.get(trait_id.node) {
+            ast_map::NodeItem(item) => item,
+            _ => tcx.sess.bug(&format!("get_trait_def({}): not an item", trait_id.repr(tcx)))
+        };
+
+        trait_def_of_item(self, &*item)
+    }
+
+    /// Ensure that the (transitive) super predicates for
+    /// `trait_def_id` are available. This will report a cycle error
+    /// if a trait `X` (transitively) extends itself in some form.
+    fn ensure_super_predicates(&self, span: Span, trait_def_id: ast::DefId)
+                               -> Result<(), ErrorReported>
+    {
+        self.cycle_check(span, AstConvRequest::EnsureSuperPredicates(trait_def_id), || {
+            let def_ids = ensure_super_predicates_step(self, trait_def_id);
+
+            for def_id in def_ids {
+                try!(self.ensure_super_predicates(span, def_id));
+            }
+
+            Ok(())
+        })
+    }
 }
 
 impl<'a,'tcx> ItemCtxt<'a,'tcx> {
@@ -342,7 +373,7 @@ impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> {
                             -> Result<ty::TypeScheme<'tcx>, ErrorReported>
     {
         self.ccx.cycle_check(span, AstConvRequest::GetItemTypeScheme(id), || {
-            type_scheme_of_def_id(self.ccx, id)
+            Ok(type_scheme_of_def_id(self.ccx, id))
         })
     }
 
@@ -350,17 +381,33 @@ impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> {
                      -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>
     {
         self.ccx.cycle_check(span, AstConvRequest::GetTraitDef(id), || {
-            get_trait_def(self.ccx, id)
+            Ok(self.ccx.get_trait_def(id))
         })
     }
 
+    fn ensure_super_predicates(&self,
+                               span: Span,
+                               trait_def_id: ast::DefId)
+                               -> Result<(), ErrorReported>
+    {
+        debug!("ensure_super_predicates(trait_def_id={})",
+               trait_def_id.repr(self.tcx()));
+
+        self.ccx.ensure_super_predicates(span, trait_def_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)
+            let v = self.param_bounds.get_type_parameter_bounds(self, span, node_id)
+                                     .into_iter()
+                                     .filter_map(|p| p.to_opt_poly_trait_ref())
+                                     .collect();
+            Ok(v)
         })
     }
 
@@ -400,7 +447,7 @@ trait GetTypeParameterBounds<'tcx> {
                                  astconv: &AstConv<'tcx>,
                                  span: Span,
                                  node_id: ast::NodeId)
-                                 -> Vec<ty::PolyTraitRef<'tcx>>;
+                                 -> Vec<ty::Predicate<'tcx>>;
 }
 
 /// Find bounds from both elements of the tuple.
@@ -411,7 +458,7 @@ impl<'a,'b,'tcx,A,B> GetTypeParameterBounds<'tcx> for (&'a A,&'b B)
                                  astconv: &AstConv<'tcx>,
                                  span: Span,
                                  node_id: ast::NodeId)
-                                 -> Vec<ty::PolyTraitRef<'tcx>>
+                                 -> Vec<ty::Predicate<'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());
@@ -425,7 +472,7 @@ impl<'tcx> GetTypeParameterBounds<'tcx> for () {
                                  _astconv: &AstConv<'tcx>,
                                  _span: Span,
                                  _node_id: ast::NodeId)
-                                 -> Vec<ty::PolyTraitRef<'tcx>>
+                                 -> Vec<ty::Predicate<'tcx>>
     {
         Vec::new()
     }
@@ -439,29 +486,28 @@ impl<'tcx> GetTypeParameterBounds<'tcx> for ty::GenericPredicates<'tcx> {
                                  astconv: &AstConv<'tcx>,
                                  _span: Span,
                                  node_id: ast::NodeId)
-                                 -> Vec<ty::PolyTraitRef<'tcx>>
+                                 -> Vec<ty::Predicate<'tcx>>
     {
         let def = astconv.tcx().type_parameter_def(node_id);
 
         self.predicates
             .iter()
-            .filter_map(|predicate| {
-                match *predicate {
+            .filter(|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
-                        }
+                        data.skip_binder().self_ty().is_param(def.space, def.index)
+                    }
+                    ty::Predicate::TypeOutlives(ref data) => {
+                        data.skip_binder().0.is_param(def.space, def.index)
                     }
                     ty::Predicate::Equate(..) |
                     ty::Predicate::RegionOutlives(..) |
-                    ty::Predicate::TypeOutlives(..) |
                     ty::Predicate::Projection(..) => {
-                        None
+                        false
                     }
                 }
             })
+            .cloned()
             .collect()
     }
 }
@@ -475,7 +521,7 @@ impl<'tcx> GetTypeParameterBounds<'tcx> for ast::Generics {
                                  astconv: &AstConv<'tcx>,
                                  _: Span,
                                  node_id: ast::NodeId)
-                                 -> Vec<ty::PolyTraitRef<'tcx>>
+                                 -> Vec<ty::Predicate<'tcx>>
     {
         // In the AST, bounds can derive from two places. Either
         // written inline like `<T:Foo>` or in a where clause like
@@ -489,7 +535,7 @@ impl<'tcx> GetTypeParameterBounds<'tcx> for ast::Generics {
                 .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()));
+                .flat_map(|b| predicates_from_bound(astconv, ty, b).into_iter());
 
         let from_where_clauses =
             self.where_clause
@@ -501,7 +547,7 @@ impl<'tcx> GetTypeParameterBounds<'tcx> for ast::Generics {
                 })
                 .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()));
+                .flat_map(|b| predicates_from_bound(astconv, ty, b).into_iter());
 
         from_ty_params.chain(from_where_clauses).collect()
     }
@@ -518,10 +564,15 @@ fn is_param<'tcx>(tcx: &ty::ctxt<'tcx>,
 {
     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
+        match path_res.base_def {
+            def::DefSelfTy(node_id) =>
+                path_res.depth == 0 && node_id == param_id,
+
+            def::DefTyParam(_, _, def_id, _) =>
+                path_res.depth == 0 && def_id == local_def(param_id),
+
+            _ =>
+                false,
         }
     } else {
         false
@@ -790,9 +841,10 @@ fn convert_methods<'a,'tcx,'i,I>(ccx: &CrateCtxt<'a, 'tcx>,
                                  rcvr_visibility: ast::Visibility)
                                  where I: Iterator<Item=&'i ast::Method>
 {
-    debug!("convert_methods(untransformed_rcvr_ty={}, rcvr_ty_generics={})",
+    debug!("convert_methods(untransformed_rcvr_ty={}, rcvr_ty_generics={}, rcvr_ty_predicates={})",
            untransformed_rcvr_ty.repr(ccx.tcx),
-           rcvr_ty_generics.repr(ccx.tcx));
+           rcvr_ty_generics.repr(ccx.tcx),
+           rcvr_ty_predicates.repr(ccx.tcx));
 
     let tcx = ccx.tcx;
     let mut seen_methods = FnvHashSet();
@@ -1036,6 +1088,8 @@ fn convert_item(ccx: &CrateCtxt, it: &ast::Item) {
         },
         ast::ItemTrait(_, _, _, ref trait_items) => {
             let trait_def = trait_def_of_item(ccx, it);
+            let _: Result<(), ErrorReported> = // any error is already reported, can ignore
+                ccx.ensure_super_predicates(it.span, local_def(it.id));
             convert_trait_predicates(ccx, it);
             let trait_predicates = ty::lookup_predicates(ccx.tcx, local_def(it.id));
 
@@ -1181,22 +1235,84 @@ fn convert_struct<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
     }
 }
 
-fn get_trait_def<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
-                           trait_id: ast::DefId)
-                           -> Rc<ty::TraitDef<'tcx>> {
+/// Ensures that the super-predicates of the trait with def-id
+/// trait_def_id are converted and stored. This does NOT ensure that
+/// the transitive super-predicates are converted; that is the job of
+/// the `ensure_super_predicates()` method in the `AstConv` impl
+/// above. Returns a list of trait def-ids that must be ensured as
+/// well to guarantee that the transitive superpredicates are
+/// converted.
+fn ensure_super_predicates_step(ccx: &CrateCtxt,
+                                trait_def_id: ast::DefId)
+                                -> Vec<ast::DefId>
+{
     let tcx = ccx.tcx;
 
-    if trait_id.krate != ast::LOCAL_CRATE {
-        return ty::lookup_trait_def(tcx, trait_id)
-    }
+    debug!("ensure_super_predicates_step(trait_def_id={})", trait_def_id.repr(tcx));
 
-    match tcx.map.get(trait_id.node) {
-        ast_map::NodeItem(item) => trait_def_of_item(ccx, &*item),
-        _ => {
-            tcx.sess.bug(&format!("get_trait_def({}): not an item",
-                                  trait_id.node))
-        }
+    if trait_def_id.krate != ast::LOCAL_CRATE {
+        return Vec::new();
     }
+
+    let superpredicates = tcx.super_predicates.borrow().get(&trait_def_id).cloned();
+    let superpredicates = superpredicates.unwrap_or_else(|| {
+        let trait_node_id = trait_def_id.node;
+
+        let item = match ccx.tcx.map.get(trait_node_id) {
+            ast_map::NodeItem(item) => item,
+            _ => ccx.tcx.sess.bug(&format!("trait_node_id {} is not an item", trait_node_id))
+        };
+
+        let (generics, bounds) = match item.node {
+            ast::ItemTrait(_, ref generics, ref supertraits, _) => (generics, supertraits),
+            _ => tcx.sess.span_bug(item.span,
+                                   "ensure_super_predicates_step invoked on non-trait"),
+        };
+
+        // In-scope when converting the superbounds for `Trait` are
+        // that `Self:Trait` as well as any bounds that appear on the
+        // generic types:
+        let trait_def = trait_def_of_item(ccx, item);
+        let self_predicate = ty::GenericPredicates {
+            predicates: VecPerParamSpace::new(vec![],
+                                              vec![trait_def.trait_ref.as_predicate()],
+                                              vec![])
+        };
+        let scope = &(generics, &self_predicate);
+
+        // Convert the bounds that follow the colon, e.g. `Bar+Zed` in `trait Foo : Bar+Zed`.
+        let self_param_ty = ty::mk_self_type(tcx);
+        let superbounds1 = compute_bounds(&ccx.icx(scope), self_param_ty, bounds,
+                                          SizedByDefault::No, item.span);
+        let superbounds1 = ty::predicates(tcx, self_param_ty, &superbounds1);
+
+        // Convert any explicit superbounds in the where clause,
+        // e.g. `trait Foo where Self : Bar`:
+        let superbounds2 = generics.get_type_parameter_bounds(&ccx.icx(scope), item.span, item.id);
+
+        // Combine the two lists to form the complete set of superbounds:
+        let superbounds = superbounds1.into_iter().chain(superbounds2.into_iter()).collect();
+        let superpredicates = ty::GenericPredicates {
+            predicates: VecPerParamSpace::new(superbounds, vec![], vec![])
+        };
+        debug!("superpredicates for trait {} = {}",
+               local_def(item.id).repr(ccx.tcx),
+               superpredicates.repr(ccx.tcx));
+
+        tcx.super_predicates.borrow_mut().insert(trait_def_id, superpredicates.clone());
+
+        superpredicates
+    });
+
+    let def_ids: Vec<_> = superpredicates.predicates
+                                         .iter()
+                                         .filter_map(|p| p.to_opt_poly_trait_ref())
+                                         .map(|tr| tr.def_id())
+                                         .collect();
+
+    debug!("ensure_super_predicates_step: def_ids={}", def_ids.repr(tcx));
+
+    def_ids
 }
 
 fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
@@ -1210,18 +1326,9 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         return def.clone();
     }
 
-    let (unsafety, generics, bounds, items) = match it.node {
-        ast::ItemTrait(unsafety,
-                       ref generics,
-                       ref supertraits,
-                       ref items) => {
-            (unsafety, generics, supertraits, items)
-        }
-        ref s => {
-            tcx.sess.span_bug(
-                it.span,
-                &format!("trait_def_of_item invoked on {:?}", s));
-        }
+    let (unsafety, generics, items) = match it.node {
+        ast::ItemTrait(unsafety, ref generics, _, ref items) => (unsafety, generics, items),
+        _ => tcx.sess.span_bug(it.span, "trait_def_of_item invoked on non-trait"),
     };
 
     let paren_sugar = ty::has_attr(tcx, def_id, "rustc_paren_sugar");
@@ -1239,15 +1346,6 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 
     let ty_generics = ty_generics_for_trait(ccx, it.id, substs, generics);
 
-    let self_param_ty = ty::ParamTy::for_self().to_ty(ccx.tcx);
-
-    // supertraits:
-    let bounds = compute_bounds(&ccx.icx(generics),
-                                self_param_ty,
-                                bounds,
-                                SizedByDefault::No,
-                                it.span);
-
     let associated_type_names: Vec<_> =
         items.iter()
              .filter_map(|item| {
@@ -1267,7 +1365,6 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         paren_sugar: paren_sugar,
         unsafety: unsafety,
         generics: ty_generics,
-        bounds: bounds,
         trait_ref: trait_ref,
         associated_type_names: associated_type_names,
     });
@@ -1348,19 +1445,14 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item)
         }
     };
 
-    let self_param_ty = ty::ParamTy::for_self().to_ty(ccx.tcx);
-
-    let super_predicates = ty::predicates(ccx.tcx, self_param_ty, &trait_def.bounds);
+    let super_predicates = ty::lookup_super_predicates(ccx.tcx, def_id);
 
     // `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
     // associated types.
-    let mut base_predicates =
-        ty::GenericPredicates {
-            predicates: VecPerParamSpace::new(super_predicates, vec![], vec![])
-        };
+    let mut base_predicates = super_predicates;
 
     // Add in a predicate that `Self:Trait` (where `Trait` is the
     // current trait).  This is needed for builtin bounds.
@@ -1990,7 +2082,7 @@ fn compute_object_lifetime_default<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
     }
 }
 
-enum SizedByDefault { Yes, No }
+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
@@ -2012,11 +2104,6 @@ fn compute_bounds<'tcx>(astconv: &AstConv<'tcx>,
                           &mut param_bounds.builtin_bounds,
                           ast_bounds,
                           span);
-
-        check_bounds_compatible(astconv,
-                                param_ty,
-                                &param_bounds,
-                                span);
     }
 
     param_bounds.trait_bounds.sort_by(|a,b| a.def_id().cmp(&b.def_id()));
@@ -2024,48 +2111,29 @@ fn compute_bounds<'tcx>(astconv: &AstConv<'tcx>,
     param_bounds
 }
 
-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(
-            tcx,
-            &param_bounds.trait_bounds,
-            |trait_ref| {
-                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
-            });
-    }
-}
-
 /// 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>>
+fn predicates_from_bound<'tcx>(astconv: &AstConv<'tcx>,
+                               param_ty: Ty<'tcx>,
+                               bound: &ast::TyParamBound)
+                               -> Vec<ty::Predicate<'tcx>>
 {
     match *bound {
         ast::TraitTyParamBound(ref tr, ast::TraitBoundModifier::None) => {
-            Some(conv_poly_trait_ref(astconv, param_ty, tr, projections))
+            let mut projections = Vec::new();
+            let pred = conv_poly_trait_ref(astconv, param_ty, tr, &mut projections);
+            projections.into_iter()
+                       .map(|p| p.as_predicate())
+                       .chain(Some(pred.as_predicate()).into_iter())
+                       .collect()
         }
-        ast::TraitTyParamBound(_, ast::TraitBoundModifier::Maybe) |
-        ast::RegionTyParamBound(_) => {
-            None
+        ast::RegionTyParamBound(ref lifetime) => {
+            let region = ast_region_to_region(astconv.tcx(), lifetime);
+            let pred = ty::Binder(ty::OutlivesPredicate(param_ty, region));
+            vec![ty::Predicate::TypeOutlives(pred)]
+        }
+        ast::TraitTyParamBound(_, ast::TraitBoundModifier::Maybe) => {
+            Vec::new()
         }
     }
 }
diff --git a/src/librustc_typeck/variance.rs b/src/librustc_typeck/variance.rs
index 1fba4a21ccd..9b27128ce2f 100644
--- a/src/librustc_typeck/variance.rs
+++ b/src/librustc_typeck/variance.rs
@@ -644,9 +644,9 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
 
             ast::ItemTrait(..) => {
                 let trait_def = ty::lookup_trait_def(tcx, did);
-                let predicates = ty::predicates(tcx, ty::mk_self_type(tcx), &trait_def.bounds);
+                let predicates = ty::lookup_super_predicates(tcx, did);
                 self.add_constraints_from_predicates(&trait_def.generics,
-                                                     &predicates,
+                                                     predicates.predicates.as_slice(),
                                                      self.covariant);
 
                 let trait_items = ty::trait_items(tcx, did);
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index 2bb4424822a..db41bf9fee3 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -165,14 +165,12 @@ pub fn build_external_trait(cx: &DocContext, tcx: &ty::ctxt,
             _ => unreachable!()
         }
     });
-    let trait_def = ty::lookup_trait_def(tcx, did);
     let predicates = ty::lookup_predicates(tcx, did);
-    let bounds = trait_def.bounds.clean(cx);
     clean::Trait {
         unsafety: def.unsafety,
         generics: (&def.generics, &predicates, subst::TypeSpace).clean(cx),
         items: items.collect(),
-        bounds: bounds,
+        bounds: vec![], // supertraits can be found in the list of predicates
     }
 }
 
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
index abcbf567d44..5ca0700ce6e 100644
--- a/src/test/compile-fail/cycle-projection-based-on-where-clause.rs
+++ b/src/test/compile-fail/cycle-projection-based-on-where-clause.rs
@@ -25,7 +25,7 @@ trait Trait { type Item; }
 struct A<T>
     where T : Trait,
           T : Add<T::Item>
-    //~^ ERROR illegal recursive type
+    //~^ ERROR unsupported cyclic reference between types/traits detected
 {
     data: T
 }
diff --git a/src/test/compile-fail/duplicate-trait-bounds.rs b/src/test/compile-fail/cycle-trait-default-type-trait.rs
index d9aa9d9dfcc..e6caeb34a8c 100644
--- a/src/test/compile-fail/duplicate-trait-bounds.rs
+++ b/src/test/compile-fail/cycle-trait-default-type-trait.rs
@@ -1,4 +1,4 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// 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.
 //
@@ -8,8 +8,11 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-trait Foo {}
+// Test a cycle where a type parameter on a trait has a default that
+// again references the trait.
 
-fn foo<T: Foo + Foo>() {} //~ ERROR `Foo` already appears in the list of bounds
+trait Foo<X = Box<Foo>> {
+    //~^ ERROR unsupported cyclic reference
+}
 
-fn main() {}
+fn main() { }
diff --git a/src/test/compile-fail/cycle-trait-supertrait-indirect.rs b/src/test/compile-fail/cycle-trait-supertrait-indirect.rs
index 6ebd9a1bcb6..c9bfde3f4ed 100644
--- a/src/test/compile-fail/cycle-trait-supertrait-indirect.rs
+++ b/src/test/compile-fail/cycle-trait-supertrait-indirect.rs
@@ -12,9 +12,12 @@
 // a direct participant in the cycle.
 
 trait A: B {
+    //~^ ERROR unsupported cyclic reference
 }
 
-trait B: C { }
+trait B: C {
+    //~^ ERROR unsupported cyclic reference
+}
 
 trait C: B { }
     //~^ ERROR unsupported cyclic reference
diff --git a/src/test/compile-fail/infinite-vec-type-recursion.rs b/src/test/compile-fail/infinite-vec-type-recursion.rs
index 5bcba350b2e..e5120840f76 100644
--- a/src/test/compile-fail/infinite-vec-type-recursion.rs
+++ b/src/test/compile-fail/infinite-vec-type-recursion.rs
@@ -8,9 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: illegal recursive type
-
-
 type x = Vec<x>;
+//~^ ERROR unsupported cyclic reference
 
 fn main() { let b: x = Vec::new(); }
diff --git a/src/test/compile-fail/issue-18389.rs b/src/test/compile-fail/issue-18389.rs
index 9065a5b9605..271c31bd375 100644
--- a/src/test/compile-fail/issue-18389.rs
+++ b/src/test/compile-fail/issue-18389.rs
@@ -12,18 +12,17 @@
 
 use std::any::Any;
 use std::any::TypeId;
+use std::marker::MarkerTrait;
 
-pub trait Pt {}
-pub trait Rt {}
+pub trait Pt : MarkerTrait {}
+pub trait Rt : MarkerTrait {}
 
 trait Private<P: Pt, R: Rt> {
     fn call(&self, p: P, r: R);
 }
-pub trait Public: Private<
+pub trait Public: Private< //~ ERROR private trait in exported type parameter bound
     <Self as Public>::P,
-//~^ ERROR illegal recursive type; insert an enum or struct in the cycle, if this is desired
     <Self as Public>::R
-//~^ ERROR unsupported cyclic reference between types/traits detected
 > {
     type P;
     type R;
diff --git a/src/test/compile-fail/issue-3953.rs b/src/test/compile-fail/issue-3953.rs
index 0f1dd2d7fd6..678a7806e7a 100644
--- a/src/test/compile-fail/issue-3953.rs
+++ b/src/test/compile-fail/issue-3953.rs
@@ -13,7 +13,6 @@
 use std::cmp::PartialEq;
 
 trait Hahaha: PartialEq + PartialEq {
-    //~^ ERROR trait `PartialEq` already appears in the list of bounds
 }
 
 struct Lol(isize);
@@ -21,8 +20,8 @@ struct Lol(isize);
 impl Hahaha for Lol { }
 
 impl PartialEq for Lol {
-    fn eq(&self, other: &Lol) -> bool { **self != **other }
-    fn ne(&self, other: &Lol) -> bool { **self == **other }
+    fn eq(&self, other: &Lol) -> bool { loop { } }
+    fn ne(&self, other: &Lol) -> bool { loop { } }
 }
 
 fn main() {