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.

9 files changed, 204 insertions, 195 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))
     }
 }