Switch to using predicates to drive checking. Correct various tests --

in most cases, just the error message changed, but in some cases we
are reporting new errors that OUGHT to have been reported before but
we're overlooked (mostly involving the `'static` bound on `Send`).

39 files changed, 1063 insertions, 869 deletions

diff --git a/src/libcore/kinds.rs b/src/libcore/kinds.rs
index f932acffd3c..2b92ae8af0a 100644
--- a/src/libcore/kinds.rs
+++ b/src/libcore/kinds.rs
@@ -19,7 +19,7 @@
 
 /// Types able to be transferred across task boundaries.
 #[lang="send"]
-pub trait Send for Sized? {
+pub trait Send for Sized? : 'static {
     // empty.
 }
 
diff --git a/src/librustc/metadata/common.rs b/src/librustc/metadata/common.rs
index 315e0eea9b7..99e7966b66f 100644
--- a/src/librustc/metadata/common.rs
+++ b/src/librustc/metadata/common.rs
@@ -251,3 +251,7 @@ pub const tag_type_param_def: uint = 0xa5;
 
 pub const tag_item_generics: uint = 0xa6;
 pub const tag_method_ty_generics: uint = 0xa7;
+
+pub const tag_predicate: uint = 0xa8;
+pub const tag_predicate_space: uint = 0xa9;
+pub const tag_predicate_data: uint = 0xb0;
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 79bfc46dca8..898f5d2ef93 100644
--- a/src/librustc/metadata/decoder.rs
+++ b/src/librustc/metadata/decoder.rs
@@ -23,7 +23,8 @@ 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_bare_fn_ty_data, parse_trait_ref_data,
+                         parse_predicate_data};
 use middle::def;
 use middle::lang_items;
 use middle::resolve::{TraitItemKind, TypeTraitItemKind};
@@ -1437,7 +1438,18 @@ fn doc_generics<'tcx>(base_doc: rbml::Doc,
         true
     });
 
-    let predicates = subst::VecPerParamSpace::empty(); // TODO fix in later commit
+    let mut predicates = subst::VecPerParamSpace::empty();
+    reader::tagged_docs(doc, tag_predicate, |predicate_doc| {
+        let space_doc = reader::get_doc(predicate_doc, tag_predicate_space);
+        let space = subst::ParamSpace::from_uint(reader::doc_as_u8(space_doc) as uint);
+
+        let data_doc = reader::get_doc(predicate_doc, tag_predicate_data);
+        let data = parse_predicate_data(data_doc.data, data_doc.start, cdata.cnum, tcx,
+                                        |_, did| translate_def_id(cdata, did));
+
+        predicates.push(space, data);
+        true
+    });
 
     ty::Generics { types: types, regions: regions, predicates: predicates }
 }
diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index a3f56f7f655..48d1284f507 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -803,6 +803,18 @@ fn encode_generics<'a, 'tcx>(rbml_w: &mut Encoder,
         rbml_w.end_tag();
     }
 
+    for (space, _, predicate) in generics.predicates.iter_enumerated() {
+        rbml_w.start_tag(tag_predicate);
+
+        rbml_w.wr_tagged_u8(tag_predicate_space, space as u8);
+
+        rbml_w.start_tag(tag_predicate_data);
+        tyencode::enc_predicate(rbml_w.writer, ty_str_ctxt, predicate);
+        rbml_w.end_tag();
+
+        rbml_w.end_tag();
+    }
+
     rbml_w.end_tag();
 }
 
diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index e29741fb4a1..37d790df37f 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -470,7 +470,7 @@ fn parse_ty<'a, 'tcx>(st: &mut PState<'a, 'tcx>, conv: conv_did) -> Ty<'tcx> {
         st.tcx.rcache.borrow_mut().insert(key, tt);
         return tt;
       }
-      '"' => {
+      '\"' => {
         let _ = parse_def(st, TypeWithId, |x,y| conv(x,y));
         let inner = parse_ty(st, |x,y| conv(x,y));
         inner
@@ -646,6 +646,33 @@ pub fn parse_def_id(buf: &[u8]) -> ast::DefId {
     ast::DefId { krate: crate_num, node: def_num }
 }
 
+pub fn parse_predicate_data<'tcx>(data: &[u8],
+                                  start: uint,
+                                  crate_num: ast::CrateNum,
+                                  tcx: &ty::ctxt<'tcx>,
+                                  conv: conv_did)
+                                  -> ty::Predicate<'tcx>
+{
+    let mut st = parse_state_from_data(data, crate_num, start, tcx);
+    parse_predicate(&mut st, conv)
+}
+
+pub fn parse_predicate<'a,'tcx>(st: &mut PState<'a, 'tcx>,
+                                conv: conv_did)
+                                -> ty::Predicate<'tcx>
+{
+    match next(st) {
+        't' => ty::Predicate::Trait(Rc::new(parse_trait_ref(st, conv))),
+        'e' => ty::Predicate::Equate(parse_ty(st, |x,y| conv(x,y)),
+                                     parse_ty(st, |x,y| conv(x,y))),
+        'r' => ty::Predicate::RegionOutlives(parse_region(st, |x,y| conv(x,y)),
+                                             parse_region(st, |x,y| conv(x,y))),
+        'o' => ty::Predicate::TypeOutlives(parse_ty(st, |x,y| conv(x,y)),
+                                           parse_region(st, |x,y| conv(x,y))),
+        c => panic!("Encountered invalid character in metadata: {}", c)
+    }
+}
+
 pub fn parse_type_param_def_data<'tcx>(data: &[u8], start: uint,
                                        crate_num: ast::CrateNum, tcx: &ty::ctxt<'tcx>,
                                        conv: conv_did) -> ty::TypeParameterDef<'tcx>
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index bbb2faaae06..5c7d15e1601 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -413,3 +413,30 @@ pub fn enc_type_param_def<'a, 'tcx>(w: &mut SeekableMemWriter, cx: &ctxt<'a, 'tc
     enc_bounds(w, cx, &v.bounds);
     enc_opt(w, v.default, |w, t| enc_ty(w, cx, t));
 }
+
+pub fn enc_predicate<'a, 'tcx>(w: &mut SeekableMemWriter,
+                               cx: &ctxt<'a, 'tcx>,
+                               p: &ty::Predicate<'tcx>)
+{
+    match *p {
+        ty::Predicate::Trait(ref trait_ref) => {
+            mywrite!(w, "t");
+            enc_trait_ref(w, cx, &**trait_ref);
+        }
+        ty::Predicate::Equate(a, b) => {
+            mywrite!(w, "e");
+            enc_ty(w, cx, a);
+            enc_ty(w, cx, b);
+        }
+        ty::Predicate::RegionOutlives(a, b) => {
+            mywrite!(w, "r");
+            enc_region(w, cx, a);
+            enc_region(w, cx, b);
+        }
+        ty::Predicate::TypeOutlives(a, b) => {
+            mywrite!(w, "o");
+            enc_ty(w, cx, a);
+            enc_region(w, cx, b);
+        }
+    }
+}
diff --git a/src/librustc/middle/check_static.rs b/src/librustc/middle/check_static.rs
index 9aa258c16aa..5a53979d719 100644
--- a/src/librustc/middle/check_static.rs
+++ b/src/librustc/middle/check_static.rs
@@ -31,6 +31,7 @@ use middle::infer;
 use middle::traits;
 use middle::mem_categorization as mc;
 use middle::expr_use_visitor as euv;
+use util::common::ErrorReported;
 use util::nodemap::NodeSet;
 
 use syntax::ast;
@@ -119,15 +120,17 @@ impl<'a, 'tcx> CheckStaticVisitor<'a, 'tcx> {
         let ty = ty::node_id_to_type(self.tcx, e.id);
         let infcx = infer::new_infer_ctxt(self.tcx);
         let mut fulfill_cx = traits::FulfillmentContext::new();
-        let cause = traits::ObligationCause::dummy();
-        let obligation = traits::obligation_for_builtin_bound(self.tcx, cause, ty,
-                                                              ty::BoundSync);
-        fulfill_cx.register_obligation(self.tcx, obligation.unwrap());
-        let env = ty::empty_parameter_environment();
-        let result = fulfill_cx.select_all_or_error(&infcx, &env, self.tcx).is_ok();
-        if !result {
-            self.tcx.sess.span_err(e.span, "shared static items must have a \
-                                            type which implements Sync");
+        match traits::trait_ref_for_builtin_bound(self.tcx, ty::BoundSync, ty) {
+            Ok(trait_ref) => {
+                fulfill_cx.register_trait_ref(self.tcx, trait_ref,
+                                              traits::ObligationCause::dummy());
+                let env = ty::empty_parameter_environment();
+                if !fulfill_cx.select_all_or_error(&infcx, &env, self.tcx).is_ok() {
+                    self.tcx.sess.span_err(e.span, "shared static items must have a \
+                                                    type which implements Sync");
+                }
+            }
+            Err(ErrorReported) => { }
         }
     }
 }
diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index 28f92089ce9..9d9c3e238d4 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -10,22 +10,26 @@
 
 use middle::mem_categorization::Typer;
 use middle::ty::{mod, Ty};
-use middle::infer::{mod, InferCtxt, ures};
+use middle::infer::{mod, InferCtxt};
 use std::collections::HashSet;
 use std::collections::hash_map::{Occupied, Vacant};
 use std::default::Default;
 use std::rc::Rc;
 use syntax::ast;
+use util::common::ErrorReported;
 use util::ppaux::Repr;
 use util::nodemap::NodeMap;
 
 use super::CodeAmbiguity;
+use super::CodeSelectionError;
+use super::FulfillmentError;
 use super::Obligation;
 use super::ObligationCause;
-use super::TraitObligation;
-use super::FulfillmentError;
-use super::CodeSelectionError;
+use super::PredicateObligation;
+use super::Selection;
 use super::select::SelectionContext;
+use super::trait_ref_for_builtin_bound;
+use super::Unimplemented;
 
 /// The fulfillment context is used to drive trait resolution.  It
 /// consists of a list of obligations that must be (eventually)
@@ -43,11 +47,11 @@ pub struct FulfillmentContext<'tcx> {
     // than the `SelectionCache`: it avoids duplicate errors and
     // permits recursive obligations, which are often generated from
     // traits like `Send` et al.
-    duplicate_set: HashSet<Rc<ty::TraitRef<'tcx>>>,
+    duplicate_set: HashSet<ty::Predicate<'tcx>>,
 
     // A list of all obligations that have been registered with this
     // fulfillment context.
-    trait_obligations: Vec<TraitObligation<'tcx>>,
+    predicates: Vec<PredicateObligation<'tcx>>,
 
     // Remembers the count of trait obligations that we have already
     // attempted to select. This is used to avoid repeating work
@@ -91,63 +95,61 @@ impl<'tcx> FulfillmentContext<'tcx> {
     pub fn new() -> FulfillmentContext<'tcx> {
         FulfillmentContext {
             duplicate_set: HashSet::new(),
-            trait_obligations: Vec::new(),
+            predicates: Vec::new(),
             attempted_mark: 0,
             region_obligations: NodeMap::new(),
         }
     }
 
-    pub fn register_predicate<'a>(&mut self,
-                                  infcx: &InferCtxt<'a,'tcx>,
-                                  predicate: &Obligation<'tcx, ty::Predicate<'tcx>>)
-                                  -> ures<'tcx>
+    pub fn register_builtin_bound(&mut self,
+                                  tcx: &ty::ctxt<'tcx>,
+                                  ty: Ty<'tcx>,
+                                  builtin_bound: ty::BuiltinBound,
+                                  cause: ObligationCause<'tcx>)
     {
-        match predicate.trait_ref {
-            ty::Predicate::Trait(ref trait_ref) => {
-                let trait_obligation = Obligation { cause: predicate.cause,
-                                                    recursion_depth: predicate.recursion_depth,
-                                                    trait_ref: (*trait_ref).clone() };
-                Ok(self.register_obligation(infcx.tcx, trait_obligation))
-            }
-            ty::Predicate::Equate(a, b) => {
-                let origin = infer::EquatePredicate(predicate.cause.span);
-                infer::mk_eqty(infcx, false, origin, a, b) // `a == b` ==> ``
-            }
-            ty::Predicate::RegionOutlives(r_a, r_b) => {
-                let origin = infer::RelateRegionParamBound(predicate.cause.span);
-                Ok(infer::mk_subr(infcx, origin, r_b, r_a)) // `b : a` ==> `a <= b`
-            }
-            ty::Predicate::TypeOutlives(t_a, r_b) => {
-                Ok(self.register_region_obligation(t_a, r_b, predicate.cause))
+        match trait_ref_for_builtin_bound(tcx, builtin_bound, ty) {
+            Ok(trait_ref) => {
+                self.register_trait_ref(tcx, trait_ref, cause);
             }
+            Err(ErrorReported) => { }
         }
     }
 
-    pub fn register_obligation(&mut self,
-                               tcx: &ty::ctxt<'tcx>,
-                               obligation: TraitObligation<'tcx>)
+    pub fn register_trait_ref<'a>(&mut self,
+                                  tcx: &ty::ctxt<'tcx>,
+                                  trait_ref: Rc<ty::TraitRef<'tcx>>,
+                                  cause: ObligationCause<'tcx>)
     {
-        if self.duplicate_set.insert(obligation.trait_ref.clone()) {
-            debug!("register_obligation({})", obligation.repr(tcx));
-            assert!(!obligation.trait_ref.has_escaping_regions());
-            self.trait_obligations.push(obligation);
-        } else {
-            debug!("register_obligation({}) -- already seen, skip", obligation.repr(tcx));
-        }
+        /*!
+         * A convenience function for registering trait obligations.
+         */
+
+        let trait_obligation = Obligation { cause: cause,
+                                            recursion_depth: 0,
+                                            trait_ref: ty::Predicate::Trait(trait_ref) };
+        self.register_predicate(tcx, trait_obligation)
     }
 
     pub fn register_region_obligation(&mut self,
-                                      sup_type: Ty<'tcx>,
-                                      sub_region: ty::Region,
+                                      tcx: &ty::ctxt<'tcx>,
+                                      t_a: Ty<'tcx>,
+                                      r_b: ty::Region,
                                       cause: ObligationCause<'tcx>)
     {
-        let region_obligation = RegionObligation { sup_type: sup_type,
-                                                   sub_region: sub_region,
-                                                   cause: cause };
-        match self.region_obligations.entry(cause.body_id) {
-            Vacant(entry) => { entry.set(vec![region_obligation]); },
-            Occupied(mut entry) => { entry.get_mut().push(region_obligation); },
+        register_region_obligation(tcx, t_a, r_b, cause, &mut self.region_obligations);
+    }
+
+    pub fn register_predicate<'a>(&mut self,
+                                  tcx: &ty::ctxt<'tcx>,
+                                  predicate: PredicateObligation<'tcx>)
+    {
+        if !self.duplicate_set.insert(predicate.trait_ref.clone()) {
+            debug!("register_predicate({}) -- already seen, skip", predicate.repr(tcx));
+            return;
         }
+
+        debug!("register_predicate({})", predicate.repr(tcx));
+        self.predicates.push(predicate);
     }
 
     pub fn region_obligations(&self,
@@ -170,7 +172,7 @@ impl<'tcx> FulfillmentContext<'tcx> {
 
         // Anything left is ambiguous.
         let errors: Vec<FulfillmentError> =
-            self.trait_obligations
+            self.predicates
             .iter()
             .map(|o| FulfillmentError::new((*o).clone(), CodeAmbiguity))
             .collect();
@@ -206,8 +208,8 @@ impl<'tcx> FulfillmentContext<'tcx> {
         self.select(&mut selcx, false)
     }
 
-    pub fn pending_trait_obligations(&self) -> &[TraitObligation<'tcx>] {
-        self.trait_obligations[]
+    pub fn pending_obligations(&self) -> &[PredicateObligation<'tcx>] {
+        self.predicates[]
     }
 
     /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it
@@ -218,14 +220,14 @@ impl<'tcx> FulfillmentContext<'tcx> {
                   -> Result<(),Vec<FulfillmentError<'tcx>>>
     {
         debug!("select({} obligations, only_new_obligations={}) start",
-               self.trait_obligations.len(),
+               self.predicates.len(),
                only_new_obligations);
 
         let tcx = selcx.tcx();
         let mut errors = Vec::new();
 
         loop {
-            let count = self.trait_obligations.len();
+            let count = self.predicates.len();
 
             debug!("select_where_possible({} obligations) iteration",
                    count);
@@ -243,37 +245,24 @@ impl<'tcx> FulfillmentContext<'tcx> {
 
             // First pass: walk each obligation, retaining
             // only those that we cannot yet process.
-            self.trait_obligations.retain(|obligation| {
-                // Hack: Retain does not pass in the index, but we want
-                // to avoid processing the first `start_count` entries.
-                if skip > 0 {
-                    skip -= 1;
-                    true
-                } else {
-                    match selcx.select(obligation) {
-                        Ok(None) => {
-                            true
-                        }
-                        Ok(Some(s)) => {
-                            selections.push(s);
-                            false
-                        }
-                        Err(selection_err) => {
-                            debug!("obligation: {} error: {}",
-                                   obligation.repr(tcx),
-                                   selection_err.repr(tcx));
-                            errors.push(FulfillmentError::new(
-                                (*obligation).clone(),
-                                CodeSelectionError(selection_err)));
-                            false
-                        }
+            {
+                let region_obligations = &mut self.region_obligations;
+                self.predicates.retain(|predicate| {
+                    // Hack: Retain does not pass in the index, but we want
+                    // to avoid processing the first `start_count` entries.
+                    if skip == 0 {
+                        retain_predicate(selcx, predicate,
+                                         &mut selections, &mut errors, region_obligations)
+                    } else {
+                        skip -= 1;
+                        true
                     }
-                }
-            });
+                });
+            }
 
-            self.attempted_mark = self.trait_obligations.len();
+            self.attempted_mark = self.predicates.len();
 
-            if self.trait_obligations.len() == count {
+            if self.predicates.len() == count {
                 // Nothing changed.
                 break;
             }
@@ -281,13 +270,12 @@ impl<'tcx> FulfillmentContext<'tcx> {
             // Now go through all the successful ones,
             // registering any nested obligations for the future.
             for selection in selections.into_iter() {
-                selection.map_move_nested(
-                    |o| self.register_obligation(tcx, o));
+                selection.map_move_nested(|p| self.register_predicate(tcx, p));
             }
         }
 
         debug!("select({} obligations, {} errors) done",
-               self.trait_obligations.len(),
+               self.predicates.len(),
                errors.len());
 
         if errors.len() == 0 {
@@ -298,6 +286,76 @@ impl<'tcx> FulfillmentContext<'tcx> {
     }
 }
 
+fn retain_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
+                             predicate: &PredicateObligation<'tcx>,
+                             selections: &mut Vec<Selection<'tcx>>,
+                             errors: &mut Vec<FulfillmentError<'tcx>>,
+                             region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
+                             -> bool
+{
+    /*!
+     * Evaluates a predicate obligation and modifies the appropriate
+     * output array.  Returns `true` if the predicate must be retained
+     * because it could not be fully evaluated yet due to insufficient
+     * type inference.
+     */
+
+    let tcx = selcx.tcx();
+    match predicate.trait_ref {
+        ty::Predicate::Trait(ref trait_ref) => {
+            let trait_obligation = Obligation { cause: predicate.cause,
+                                                recursion_depth: predicate.recursion_depth,
+                                                trait_ref: trait_ref.clone() };
+            match selcx.select(&trait_obligation) {
+                Ok(None) => {
+                    true
+                }
+                Ok(Some(s)) => {
+                    selections.push(s);
+                    false
+                }
+                Err(selection_err) => {
+                    debug!("predicate: {} error: {}",
+                           predicate.repr(tcx),
+                           selection_err.repr(tcx));
+                    errors.push(
+                        FulfillmentError::new(
+                            predicate.clone(),
+                            CodeSelectionError(selection_err)));
+                    false
+                }
+            }
+        }
+
+        ty::Predicate::Equate(a, b) => {
+            let origin = infer::EquatePredicate(predicate.cause.span);
+            match infer::mk_eqty(selcx.infcx(), false, origin, a, b) {
+                Ok(()) => {
+                    false
+                }
+                Err(_) => {
+                    errors.push(
+                        FulfillmentError::new(
+                            predicate.clone(),
+                            CodeSelectionError(Unimplemented)));
+                    false
+                }
+            }
+        }
+
+        ty::Predicate::RegionOutlives(r_a, r_b) => {
+            let origin = infer::RelateRegionParamBound(predicate.cause.span);
+            let () = infer::mk_subr(selcx.infcx(), origin, r_b, r_a); // `b : a` ==> `a <= b`
+            false
+        }
+
+        ty::Predicate::TypeOutlives(t_a, r_b) => {
+            register_region_obligation(tcx, t_a, r_b, predicate.cause, region_obligations);
+            false
+        }
+    }
+}
+
 impl<'tcx> Repr<'tcx> for RegionObligation<'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         format!("RegionObligation(sub_region={}, sup_type={})",
@@ -305,3 +363,23 @@ impl<'tcx> Repr<'tcx> for RegionObligation<'tcx> {
                 self.sup_type.repr(tcx))
     }
 }
+
+fn register_region_obligation<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                    t_a: Ty<'tcx>,
+                                    r_b: ty::Region,
+                                    cause: ObligationCause<'tcx>,
+                                    region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
+{
+    let region_obligation = RegionObligation { sup_type: t_a,
+                                               sub_region: r_b,
+                                               cause: cause };
+
+    debug!("register_region_obligation({})",
+           region_obligation.repr(tcx));
+
+    match region_obligations.entry(region_obligation.cause.body_id) {
+        Vacant(entry) => { entry.set(vec![region_obligation]); },
+        Occupied(mut entry) => { entry.get_mut().push(region_obligation); },
+    }
+
+}
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 37da82891de..f438b61e27c 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -15,7 +15,6 @@ pub use self::FulfillmentErrorCode::*;
 pub use self::Vtable::*;
 pub use self::ObligationCauseCode::*;
 
-use middle::mem_categorization::Typer;
 use middle::subst;
 use middle::ty::{mod, Ty};
 use middle::infer::InferCtxt;
@@ -23,13 +22,13 @@ use std::rc::Rc;
 use std::slice::Items;
 use syntax::ast;
 use syntax::codemap::{Span, DUMMY_SP};
-use util::common::ErrorReported;
 
 pub use self::fulfill::{FulfillmentContext, RegionObligation};
 pub use self::select::SelectionContext;
 pub use self::select::SelectionCache;
 pub use self::select::{MethodMatchResult, MethodMatched, MethodAmbiguous, MethodDidNotMatch};
 pub use self::select::{MethodMatchedData}; // intentionally don't export variants
+pub use self::util::elaborate_predicates;
 pub use self::util::supertraits;
 pub use self::util::Supertraits;
 pub use self::util::search_trait_and_supertraits_from_bound;
@@ -54,6 +53,7 @@ pub struct Obligation<'tcx, T> {
     pub trait_ref: T,
 }
 
+pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
 pub type TraitObligation<'tcx> = Obligation<'tcx, Rc<ty::TraitRef<'tcx>>>;
 
 /// Why did we incur this obligation? Used for error reporting.
@@ -91,7 +91,7 @@ pub enum ObligationCauseCode<'tcx> {
 
     // Captures of variable the given id by a closure (span is the
     // span of the closure)
-    ClosureCapture(ast::NodeId, Span),
+    ClosureCapture(ast::NodeId, Span, ty::BuiltinBound),
 
     // Types of fields (other than the last) in a struct must be sized.
     FieldSized,
@@ -101,20 +101,20 @@ pub enum ObligationCauseCode<'tcx> {
 }
 
 pub type Obligations<'tcx, O> = subst::VecPerParamSpace<Obligation<'tcx, O>>;
-
+pub type PredicateObligations<'tcx> = subst::VecPerParamSpace<PredicateObligation<'tcx>>;
 pub type TraitObligations<'tcx> = subst::VecPerParamSpace<TraitObligation<'tcx>>;
 
-pub type Selection<'tcx> = Vtable<'tcx, TraitObligation<'tcx>>;
+pub type Selection<'tcx> = Vtable<'tcx, PredicateObligation<'tcx>>;
 
 #[deriving(Clone,Show)]
 pub enum SelectionError<'tcx> {
     Unimplemented,
     Overflow,
-    OutputTypeParameterMismatch(Rc<ty::TraitRef<'tcx>>, ty::type_err<'tcx>)
+    OutputTypeParameterMismatch(Rc<ty::TraitRef<'tcx>>, Rc<ty::TraitRef<'tcx>>, ty::type_err<'tcx>),
 }
 
 pub struct FulfillmentError<'tcx> {
-    pub obligation: TraitObligation<'tcx>,
+    pub obligation: PredicateObligation<'tcx>,
     pub code: FulfillmentErrorCode<'tcx>
 }
 
@@ -224,33 +224,6 @@ pub struct VtableParamData<'tcx> {
     pub bound: Rc<ty::TraitRef<'tcx>>,
 }
 
-/// Matches the self type of the inherent impl `impl_def_id`
-/// against `self_ty` and returns the resulting resolution.  This
-/// routine may modify the surrounding type context (for example,
-/// it may unify variables).
-pub fn select_inherent_impl<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
-                                     param_env: &ty::ParameterEnvironment<'tcx>,
-                                     typer: &Typer<'tcx>,
-                                     cause: ObligationCause<'tcx>,
-                                     impl_def_id: ast::DefId,
-                                     self_ty: Ty<'tcx>)
-                                     -> SelectionResult<'tcx,
-                                            VtableImplData<'tcx, TraitObligation<'tcx>>>
-{
-    // This routine is only suitable for inherent impls. This is
-    // because it does not attempt to unify the output type parameters
-    // from the trait ref against the values from the obligation.
-    // (These things do not apply to inherent impls, for which there
-    // is no trait ref nor obligation.)
-    //
-    // Matching against non-inherent impls should be done with
-    // `try_resolve_obligation()`.
-    assert!(ty::impl_trait_ref(infcx.tcx, impl_def_id).is_none());
-
-    let mut selcx = select::SelectionContext::new(infcx, param_env, typer);
-    selcx.select_inherent_impl(impl_def_id, cause, self_ty)
-}
-
 /// True if neither the trait nor self type is local. Note that `impl_def_id` must refer to an impl
 /// of a trait, not an inherent impl.
 pub fn is_orphan_impl(tcx: &ty::ctxt,
@@ -270,32 +243,13 @@ pub fn overlapping_impls(infcx: &InferCtxt,
     coherence::impl_can_satisfy(infcx, impl2_def_id, impl1_def_id)
 }
 
-/// Given generic bounds from an impl like:
-///
-///    impl<A:Foo, B:Bar+Qux> ...
-///
-/// along with the bindings for the types `A` and `B` (e.g., `<A=A0, B=B0>`), yields a result like
-///
-///    [[Foo for A0, Bar for B0, Qux for B0], [], []]
-///
-/// Expects that `generic_bounds` have already been fully substituted, late-bound regions liberated
-/// and so forth, so that they are in the same namespace as `type_substs`.
-pub fn obligations_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                      cause: ObligationCause<'tcx>,
-                                      generic_bounds: &ty::GenericBounds<'tcx>,
-                                      type_substs: &subst::VecPerParamSpace<Ty<'tcx>>)
-                                      -> subst::VecPerParamSpace<TraitObligation<'tcx>>
-{
-    util::obligations_for_generics(tcx, cause, 0, generic_bounds, type_substs)
-}
-
-pub fn obligation_for_builtin_bound<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                          cause: ObligationCause<'tcx>,
-                                          source_ty: Ty<'tcx>,
-                                          builtin_bound: ty::BuiltinBound)
-                                          -> Result<TraitObligation<'tcx>, ErrorReported>
+/// Creates predicate obligations from the generic bounds.
+pub fn predicates_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                     cause: ObligationCause<'tcx>,
+                                     generic_bounds: &ty::GenericBounds<'tcx>)
+                                     -> PredicateObligations<'tcx>
 {
-    util::obligation_for_builtin_bound(tcx, cause, builtin_bound, 0, source_ty)
+    util::predicates_for_generics(tcx, cause, 0, generic_bounds)
 }
 
 impl<'tcx,O> Obligation<'tcx,O> {
@@ -311,6 +265,12 @@ impl<'tcx,O> Obligation<'tcx,O> {
     pub fn misc(span: Span, body_id: ast::NodeId, trait_ref: O) -> Obligation<'tcx, O> {
         Obligation::new(ObligationCause::misc(span, body_id), trait_ref)
     }
+
+    pub fn with<P>(&self, value: P) -> Obligation<'tcx,P> {
+        Obligation { cause: self.cause.clone(),
+                     recursion_depth: self.recursion_depth,
+                     trait_ref: value }
+    }
 }
 
 impl<'tcx> Obligation<'tcx,Rc<ty::TraitRef<'tcx>>> {
@@ -417,7 +377,7 @@ impl<N> VtableBuiltinData<N> {
 }
 
 impl<'tcx> FulfillmentError<'tcx> {
-    fn new(obligation: TraitObligation<'tcx>,
+    fn new(obligation: PredicateObligation<'tcx>,
            code: FulfillmentErrorCode<'tcx>)
            -> FulfillmentError<'tcx>
     {
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 90fc663e829..c55335ea190 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -17,9 +17,8 @@ use self::Candidate::*;
 use self::BuiltinBoundConditions::*;
 use self::EvaluationResult::*;
 
-use super::{TraitObligation, ObligationCause};
-use super::{SelectionError, Unimplemented, Overflow,
-            OutputTypeParameterMismatch};
+use super::{PredicateObligation, Obligation, TraitObligation, ObligationCause};
+use super::{SelectionError, Unimplemented, Overflow, OutputTypeParameterMismatch};
 use super::{Selection};
 use super::{SelectionResult};
 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableUnboxedClosure, VtableFnPointer};
@@ -191,6 +190,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
+    pub fn infcx(&self) -> &'cx InferCtxt<'cx, 'tcx> {
+        self.infcx
+    }
+
     pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
         self.infcx.tcx
     }
@@ -225,29 +228,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
-    pub fn select_inherent_impl(&mut self,
-                                impl_def_id: ast::DefId,
-                                obligation_cause: ObligationCause<'tcx>,
-                                obligation_self_ty: Ty<'tcx>)
-                                -> SelectionResult<'tcx, VtableImplData<'tcx, TraitObligation<'tcx>>>
-    {
-        debug!("select_inherent_impl(impl_def_id={}, obligation_self_ty={})",
-               impl_def_id.repr(self.tcx()),
-               obligation_self_ty.repr(self.tcx()));
-
-        match self.match_inherent_impl(impl_def_id,
-                                       obligation_cause,
-                                       obligation_self_ty) {
-            Ok(substs) => {
-                let vtable_impl = self.vtable_impl(impl_def_id, substs, obligation_cause, 0);
-                Ok(Some(vtable_impl))
-            }
-            Err(()) => {
-                Err(Unimplemented)
-            }
-        }
-    }
-
     ///////////////////////////////////////////////////////////////////////////
     // EVALUATION
     //
@@ -260,15 +240,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
     pub fn evaluate_obligation(&mut self,
-                               obligation: &TraitObligation<'tcx>)
+                               obligation: &PredicateObligation<'tcx>)
                                -> bool
     {
         debug!("evaluate_obligation({})",
                obligation.repr(self.tcx()));
-        assert!(!obligation.trait_ref.has_escaping_regions());
 
-        let stack = self.push_stack(None, obligation);
-        self.evaluate_stack(&stack).may_apply()
+        self.evaluate_predicate_recursively(None, obligation).may_apply()
     }
 
     fn evaluate_builtin_bound_recursively<'o>(&mut self,
@@ -278,7 +256,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                               -> EvaluationResult<'tcx>
     {
         let obligation =
-            util::obligation_for_builtin_bound(
+            util::predicate_for_builtin_bound(
                 self.tcx(),
                 previous_stack.obligation.cause,
                 bound,
@@ -287,7 +265,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         match obligation {
             Ok(obligation) => {
-                self.evaluate_obligation_recursively(Some(previous_stack), &obligation)
+                self.evaluate_predicate_recursively(Some(previous_stack), &obligation)
             }
             Err(ErrorReported) => {
                 EvaluatedToOk
@@ -295,6 +273,36 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
+    fn evaluate_predicate_recursively<'o>(&mut self,
+                                          previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
+                                          obligation: &PredicateObligation<'tcx>)
+                                           -> EvaluationResult<'tcx>
+    {
+        debug!("evaluate_predicate_recursively({})",
+               obligation.repr(self.tcx()));
+
+        match obligation.trait_ref {
+            ty::Predicate::Trait(ref t) => {
+                assert!(!t.has_escaping_regions());
+                let obligation = obligation.with(t.clone());
+                self.evaluate_obligation_recursively(previous_stack, &obligation)
+            }
+
+            ty::Predicate::Equate(a, b) => {
+                match infer::can_mk_eqty(self.infcx, a, b) {
+                    Ok(()) => EvaluatedToOk,
+                    Err(_) => EvaluatedToErr(Unimplemented),
+                }
+            }
+
+            ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
+                // we do not consider region relationships when
+                // evaluating trait matches
+                EvaluatedToOk
+            }
+        }
+    }
+
     fn evaluate_obligation_recursively<'o>(&mut self,
                                            previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
                                            obligation: &TraitObligation<'tcx>)
@@ -347,7 +355,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
               stack.iter().skip(1).any(
                   |prev| stack.skol_trait_ref.def_id == prev.skol_trait_ref.def_id))
         {
-            debug!("evaluate_stack_intracrate({}) --> unbound argument, recursion -->  ambiguous",
+            debug!("evaluate_stack({}) --> unbound argument, recursion -->  ambiguous",
                    stack.skol_trait_ref.repr(self.tcx()));
             return EvaluatedToAmbig;
         }
@@ -376,7 +384,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             .skip(1) // skip top-most frame
             .any(|prev| stack.skol_trait_ref == prev.skol_trait_ref)
         {
-            debug!("evaluate_stack_intracrate({}) --> recursive",
+            debug!("evaluate_stack({}) --> recursive",
                    stack.skol_trait_ref.repr(self.tcx()));
             return EvaluatedToOk;
         }
@@ -595,8 +603,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // common case, then we can use the global environment.
         // See the discussion in doc.rs for more details.
         if
-            !self.param_env.caller_obligations.is_empty()
-            &&
+            !self.param_env.caller_bounds.is_empty() &&
             cache_skol_trait_ref.input_types().iter().any(
                 |&t| ty::type_has_ty_infer(t))
         {
@@ -690,8 +697,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                obligation.repr(self.tcx()));
 
         let caller_trait_refs: Vec<Rc<ty::TraitRef>> =
-            self.param_env.caller_obligations.iter()
-            .map(|o| o.trait_ref.clone())
+            self.param_env.caller_bounds.predicates.iter()
+            .filter_map(|o| o.to_trait())
             .collect();
 
         let all_bounds =
@@ -852,7 +859,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     {
         let mut result = EvaluatedToOk;
         for obligation in selection.iter_nested() {
-            match self.evaluate_obligation_recursively(stack, obligation) {
+            match self.evaluate_predicate_recursively(stack, obligation) {
                 EvaluatedToErr(e) => { return EvaluatedToErr(e); }
                 EvaluatedToAmbig => { result = EvaluatedToAmbig; }
                 EvaluatedToOk => { }
@@ -932,8 +939,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                              candidates: &mut CandidateSet<'tcx>)
                                              -> Result<(),SelectionError<'tcx>>
     {
-        match self.builtin_bound(bound, stack.obligation.self_ty()) {
-            Ok(If(_)) => {
+        match self.builtin_bound(bound, stack.obligation) {
+            Ok(If(..)) => {
                 debug!("builtin_bound: bound={}",
                        bound.repr(self.tcx()));
                 candidates.vec.push(BuiltinCandidate(bound));
@@ -947,10 +954,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     fn builtin_bound(&mut self,
                      bound: ty::BuiltinBound,
-                     self_ty: Ty<'tcx>)
+                     obligation: &TraitObligation<'tcx>)
                      -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
     {
-        let self_ty = self.infcx.shallow_resolve(self_ty);
+        let self_ty = self.infcx.shallow_resolve(obligation.trait_ref.self_ty());
         return match self_ty.sty {
             ty::ty_infer(ty::IntVar(_)) |
             ty::ty_infer(ty::FloatVar(_)) |
@@ -1023,8 +1030,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         match bound {
                             ty::BoundCopy => {
                                 match mutbl {
-                                    ast::MutMutable => Err(Unimplemented),  // &mut T is affine
-                                    ast::MutImmutable => Ok(If(Vec::new())),  // &T is copyable
+                                    ast::MutMutable => {
+                                        // &mut T is affine
+                                        Err(Unimplemented)
+                                    }
+                                    ast::MutImmutable => {
+                                        // &T is copyable, no matter what T is
+                                        Ok(If(Vec::new()))
+                                    }
                                 }
                             }
 
@@ -1083,10 +1096,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     ty::BoundCopy => {
                         match mutbl {
                             // &mut T is affine and hence never `Copy`
-                            ast::MutMutable => Err(Unimplemented),
+                            ast::MutMutable => {
+                                Err(Unimplemented)
+                            }
 
                             // &T is always copyable
-                            ast::MutImmutable => Ok(If(Vec::new())),
+                            ast::MutImmutable => {
+                                Ok(If(Vec::new()))
+                            }
                         }
                     }
 
@@ -1122,8 +1139,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 match bound {
                     ty::BoundCopy => {
                         match *len {
-                            Some(_) => Ok(If(vec![element_ty])), // [T, ..n] is copy iff T is copy
-                            None => Err(Unimplemented), // [T] is unsized and hence affine
+                            Some(_) => {
+                                // [T, ..n] is copy iff T is copy
+                                Ok(If(vec![element_ty]))
+                            }
+                            None => {
+                                // [T] is unsized and hence affine
+                                Err(Unimplemented)
+                            }
                         }
                     }
 
@@ -1256,7 +1279,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         Some(def_id) == tcx.lang_items.no_send_bound() ||
                         Some(def_id) == tcx.lang_items.managed_bound()
                     {
-                        return Err(Unimplemented);
+                        return Err(Unimplemented)
                     }
                 }
 
@@ -1274,7 +1297,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         Some(def_id) == tcx.lang_items.no_sync_bound() ||
                         Some(def_id) == tcx.lang_items.managed_bound()
                     {
-                        return Err(Unimplemented);
+                        return Err(Unimplemented)
                     } else if
                         Some(def_id) == tcx.lang_items.unsafe_type()
                     {
@@ -1361,13 +1384,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     fn confirm_builtin_candidate(&mut self,
                                  obligation: &TraitObligation<'tcx>,
                                  bound: ty::BuiltinBound)
-                                 -> Result<VtableBuiltinData<TraitObligation<'tcx>>,
+                                 -> Result<VtableBuiltinData<PredicateObligation<'tcx>>,
                                            SelectionError<'tcx>>
     {
         debug!("confirm_builtin_candidate({})",
                obligation.repr(self.tcx()));
 
-        match try!(self.builtin_bound(bound, obligation.self_ty())) {
+        match try!(self.builtin_bound(bound, obligation)) {
             If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
             AmbiguousBuiltin | ParameterBuiltin => {
                 self.tcx().sess.span_bug(
@@ -1382,29 +1405,44 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                            obligation: &TraitObligation<'tcx>,
                            bound: ty::BuiltinBound,
                            nested: Vec<Ty<'tcx>>)
-                           -> VtableBuiltinData<TraitObligation<'tcx>>
+                           -> VtableBuiltinData<PredicateObligation<'tcx>>
     {
         let obligations = nested.iter().map(|&t| {
-            util::obligation_for_builtin_bound(
+            util::predicate_for_builtin_bound(
                 self.tcx(),
                 obligation.cause,
                 bound,
                 obligation.recursion_depth + 1,
                 t)
         }).collect::<Result<_, _>>();
-        let obligations = match obligations {
+        let mut obligations = match obligations {
             Ok(o) => o,
             Err(ErrorReported) => Vec::new()
         };
+
+        // as a special case, `Send` requires `'static`
+        if bound == ty::BoundSend {
+            obligations.push(Obligation {
+                cause: obligation.cause,
+                recursion_depth: obligation.recursion_depth+1,
+                trait_ref: ty::Predicate::TypeOutlives(obligation.self_ty(),
+                                                       ty::ReStatic)
+            });
+        }
+
         let obligations = VecPerParamSpace::new(obligations, Vec::new(),
                                                 Vec::new(), Vec::new());
+
+        debug!("vtable_builtin_data: obligations={}",
+               obligations.repr(self.tcx()));
+
         VtableBuiltinData { nested: obligations }
     }
 
     fn confirm_impl_candidate(&mut self,
                               obligation: &TraitObligation<'tcx>,
                               impl_def_id: ast::DefId)
-                              -> Result<VtableImplData<'tcx, TraitObligation<'tcx>>,
+                              -> Result<VtableImplData<'tcx, PredicateObligation<'tcx>>,
                                         SelectionError<'tcx>>
     {
         debug!("confirm_impl_candidate({},{})",
@@ -1414,6 +1452,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // First, create the substitutions by matching the impl again,
         // this time not in a probe.
         let substs = self.rematch_impl(impl_def_id, obligation);
+        debug!("confirm_impl_candidate substs={}", substs);
         Ok(self.vtable_impl(impl_def_id, substs, obligation.cause, obligation.recursion_depth + 1))
     }
 
@@ -1422,16 +1461,16 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                    substs: Substs<'tcx>,
                    cause: ObligationCause<'tcx>,
                    recursion_depth: uint)
-                   -> VtableImplData<'tcx, TraitObligation<'tcx>>
+                   -> VtableImplData<'tcx, PredicateObligation<'tcx>>
     {
-        let impl_obligations =
-            self.impl_obligations(cause,
-                                  recursion_depth,
-                                  impl_def_id,
-                                  &substs);
+        let impl_predicates =
+            self.impl_predicates(cause,
+                                 recursion_depth,
+                                 impl_def_id,
+                                 &substs);
         VtableImplData { impl_def_id: impl_def_id,
                          substs: substs,
-                         nested: impl_obligations }
+                         nested: impl_predicates }
     }
 
     fn confirm_fn_pointer_candidate(&mut self,
@@ -1752,9 +1791,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         match self.infcx.sub_trait_refs(false,
                                         origin,
                                         expected_trait_ref.clone(),
-                                        obligation_trait_ref) {
+                                        obligation_trait_ref.clone()) {
             Ok(()) => Ok(()),
-            Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, e))
+            Err(e) => Err(OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
         }
     }
 
@@ -1785,17 +1824,16 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
-    fn impl_obligations(&self,
-                        cause: ObligationCause<'tcx>,
-                        recursion_depth: uint,
-                        impl_def_id: ast::DefId,
-                        impl_substs: &Substs<'tcx>)
-                        -> VecPerParamSpace<TraitObligation<'tcx>>
+    fn impl_predicates(&self,
+                       cause: ObligationCause<'tcx>,
+                       recursion_depth: uint,
+                       impl_def_id: ast::DefId,
+                       impl_substs: &Substs<'tcx>)
+                       -> VecPerParamSpace<PredicateObligation<'tcx>>
     {
         let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
         let bounds = impl_generics.to_bounds(self.tcx(), impl_substs);
-        util::obligations_for_generics(self.tcx(), cause, recursion_depth,
-                                       &bounds, &impl_substs.types)
+        util::predicates_for_generics(self.tcx(), cause, recursion_depth, &bounds)
     }
 
     fn fn_family_trait_kind(&self,
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index 360298feab7..a9532aceebb 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -9,8 +9,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use middle::subst;
-use middle::subst::{ParamSpace, Substs, VecPerParamSpace, Subst};
+use middle::subst::{Subst, Substs, VecPerParamSpace};
 use middle::infer::InferCtxt;
 use middle::ty::{mod, Ty};
 use std::collections::HashSet;
@@ -21,115 +20,130 @@ use syntax::codemap::Span;
 use util::common::ErrorReported;
 use util::ppaux::Repr;
 
-use super::{Obligation, ObligationCause, TraitObligation, VtableImpl,
-            VtableParam, VtableParamData, VtableImplData};
+use super::{Obligation, ObligationCause, PredicateObligation,
+            VtableImpl, VtableParam, VtableParamData, VtableImplData};
 
 ///////////////////////////////////////////////////////////////////////////
-// Supertrait iterator
+// Elaboration iterator
 
-pub struct Supertraits<'cx, 'tcx:'cx> {
+pub struct Elaborator<'cx, 'tcx:'cx> {
     tcx: &'cx ty::ctxt<'tcx>,
-    stack: Vec<SupertraitEntry<'tcx>>,
-    visited: HashSet<Rc<ty::TraitRef<'tcx>>>,
+    stack: Vec<StackEntry<'tcx>>,
+    visited: HashSet<ty::Predicate<'tcx>>,
 }
 
-struct SupertraitEntry<'tcx> {
+struct StackEntry<'tcx> {
     position: uint,
-    supertraits: Vec<Rc<ty::TraitRef<'tcx>>>,
+    predicates: Vec<ty::Predicate<'tcx>>,
 }
 
-pub fn supertraits<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
-                              trait_ref: Rc<ty::TraitRef<'tcx>>)
-                              -> Supertraits<'cx, 'tcx>
+pub fn elaborate_trait_ref<'cx, 'tcx>(
+    tcx: &'cx ty::ctxt<'tcx>,
+    trait_ref: Rc<ty::TraitRef<'tcx>>)
+    -> Elaborator<'cx, 'tcx>
 {
-    //! Returns an iterator over the trait reference `T` and all of its supertrait references. May
-    //! contain duplicates. In general the ordering is not defined.
-    //!
-    //! Example:
-    //!
-    //! ```
-    //! trait Foo { ... }
-    //! trait Bar : Foo { ... }
-    //! trait Baz : Bar+Foo { ... }
-    //! ```
-    //!
-    //! `supertraits(Baz)` yields `[Baz, Bar, Foo, Foo]` in some order.
-
-    transitive_bounds(tcx, &[trait_ref])
+    elaborate_predicates(tcx, vec![ty::Predicate::Trait(trait_ref)])
 }
 
-pub fn transitive_bounds<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
-                                    bounds: &[Rc<ty::TraitRef<'tcx>>])
-                                    -> Supertraits<'cx, 'tcx>
+pub fn elaborate_trait_refs<'cx, 'tcx>(
+    tcx: &'cx ty::ctxt<'tcx>,
+    trait_refs: &[Rc<ty::TraitRef<'tcx>>])
+    -> Elaborator<'cx, 'tcx>
 {
-    let bounds = Vec::from_fn(bounds.len(), |i| bounds[i].clone());
+    let predicates = trait_refs.iter()
+                               .map(|trait_ref| ty::Predicate::Trait((*trait_ref).clone()))
+                               .collect();
+    elaborate_predicates(tcx, predicates)
+}
 
-    let visited: HashSet<Rc<ty::TraitRef>> =
-        bounds.iter()
-              .map(|b| (*b).clone())
-              .collect();
+pub fn elaborate_predicates<'cx, 'tcx>(
+    tcx: &'cx ty::ctxt<'tcx>,
+    predicates: Vec<ty::Predicate<'tcx>>)
+    -> Elaborator<'cx, 'tcx>
+{
+    let visited: HashSet<ty::Predicate<'tcx>> =
+        predicates.iter()
+                  .map(|b| (*b).clone())
+                  .collect();
 
-    let entry = SupertraitEntry { position: 0, supertraits: bounds };
-    Supertraits { tcx: tcx, stack: vec![entry], visited: visited }
+    let entry = StackEntry { position: 0, predicates: predicates };
+    Elaborator { tcx: tcx, stack: vec![entry], visited: visited }
 }
 
-impl<'cx, 'tcx> Supertraits<'cx, 'tcx> {
-    fn push(&mut self, trait_ref: &ty::TraitRef<'tcx>) {
-        let ty::ParamBounds { builtin_bounds, mut trait_bounds, .. } =
-            ty::bounds_for_trait_ref(self.tcx, trait_ref);
-        for builtin_bound in builtin_bounds.iter() {
-            let bound_trait_ref = trait_ref_for_builtin_bound(self.tcx,
-                                                              builtin_bound,
-                                                              trait_ref.self_ty());
-            match bound_trait_ref {
-                Ok(trait_ref) => { trait_bounds.push(trait_ref); }
-                Err(ErrorReported) => { }
+impl<'cx, 'tcx> Elaborator<'cx, 'tcx> {
+    fn push(&mut self, predicate: &ty::Predicate<'tcx>) {
+        match *predicate {
+            ty::Predicate::Trait(ref trait_ref) => {
+                let mut predicates =
+                    ty::predicates_for_trait_ref(self.tcx, &**trait_ref);
+
+                // Only keep those bounds that we haven't already
+                // seen.  This is necessary to prevent infinite
+                // recursion in some cases.  One common case is when
+                // people define `trait Sized { }` rather than `trait
+                // Sized for Sized? { }`.
+                predicates.retain(|r| self.visited.insert((*r).clone()));
+
+                self.stack.push(StackEntry { position: 0,
+                                             predicates: predicates });
+            }
+            ty::Predicate::Equate(..) => {
+            }
+            ty::Predicate::RegionOutlives(..) |
+            ty::Predicate::TypeOutlives(..) => {
+                // Currently, we do not "elaborate" predicates like
+                // `'a : 'b` or `T : 'a`.  We could conceivably do
+                // more here.  For example,
+                //
+                //     &'a int : 'b
+                //
+                // implies that
+                //
+                //     'a : 'b
+                //
+                // and we could get even more if we took WF
+                // constraints into account. For example,
+                //
+                //     &'a &'b int : 'c
+                //
+                // implies that
+                //
+                //     'b : 'a
+                //     'a : 'c
             }
         }
-
-        // Only keep those bounds that we haven't already seen.  This
-        // is necessary to prevent infinite recursion in some cases.
-        // One common case is when people define `trait Sized { }`
-        // rather than `trait Sized for Sized? { }`.
-        trait_bounds.retain(|r| self.visited.insert((*r).clone()));
-
-        let entry = SupertraitEntry { position: 0, supertraits: trait_bounds };
-        self.stack.push(entry);
-    }
-
-    /// Returns the path taken through the trait supertraits to reach the current point.
-    pub fn indices(&self) -> Vec<uint> {
-        self.stack.iter().map(|e| e.position).collect()
     }
 }
 
-impl<'cx, 'tcx> Iterator<Rc<ty::TraitRef<'tcx>>> for Supertraits<'cx, 'tcx> {
-    fn next(&mut self) -> Option<Rc<ty::TraitRef<'tcx>>> {
+impl<'cx, 'tcx> Iterator<ty::Predicate<'tcx>> for Elaborator<'cx, 'tcx> {
+    fn next(&mut self) -> Option<ty::Predicate<'tcx>> {
         loop {
             // Extract next item from top-most stack frame, if any.
-            let next_trait = match self.stack.last_mut() {
+            let next_predicate = match self.stack.last_mut() {
                 None => {
                     // No more stack frames. Done.
                     return None;
                 }
                 Some(entry) => {
                     let p = entry.position;
-                    if p < entry.supertraits.len() {
-                        // Still more supertraits left in the top stack frame.
+                    if p < entry.predicates.len() {
+                        // Still more predicates left in the top stack frame.
                         entry.position += 1;
 
-                        let next_trait = entry.supertraits[p].clone();
-                        Some(next_trait)
+                        let next_predicate =
+                            entry.predicates[p].clone();
+
+                        Some(next_predicate)
                     } else {
                         None
                     }
                 }
             };
 
-            match next_trait {
-                Some(next_trait) => {
-                    self.push(&*next_trait);
-                    return Some(next_trait);
+            match next_predicate {
+                Some(next_predicate) => {
+                    self.push(&next_predicate);
+                    return Some(next_predicate);
                 }
 
                 None => {
@@ -141,6 +155,50 @@ impl<'cx, 'tcx> Iterator<Rc<ty::TraitRef<'tcx>>> for Supertraits<'cx, 'tcx> {
     }
 }
 
+///////////////////////////////////////////////////////////////////////////
+// Supertrait iterator
+
+pub struct Supertraits<'cx, 'tcx:'cx> {
+    elaborator: Elaborator<'cx, 'tcx>,
+}
+
+pub fn supertraits<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
+                              trait_ref: Rc<ty::TraitRef<'tcx>>)
+                              -> Supertraits<'cx, 'tcx>
+{
+    let elaborator = elaborate_trait_ref(tcx, trait_ref);
+    Supertraits { elaborator: elaborator }
+}
+
+pub fn transitive_bounds<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
+                                    bounds: &[Rc<ty::TraitRef<'tcx>>])
+                                    -> Supertraits<'cx, 'tcx>
+{
+    let elaborator = elaborate_trait_refs(tcx, bounds);
+    Supertraits { elaborator: elaborator }
+}
+
+impl<'cx, 'tcx> Iterator<Rc<ty::TraitRef<'tcx>>> for Supertraits<'cx, 'tcx> {
+    fn next(&mut self) -> Option<Rc<ty::TraitRef<'tcx>>> {
+        loop {
+            match self.elaborator.next() {
+                None => {
+                    return None;
+                }
+                Some(ty::Predicate::Trait(trait_ref)) => {
+                    return Some(trait_ref);
+                }
+                Some(ty::Predicate::Equate(..)) |
+                Some(ty::Predicate::RegionOutlives(..)) |
+                Some(ty::Predicate::TypeOutlives(..)) => {
+                }
+            }
+        }
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+
 // determine the `self` type, using fresh variables for all variables
 // declared on the impl declaration e.g., `impl<A,B> for Box<[(A,B)]>`
 // would return ($0, $1) where $0 and $1 are freshly instantiated type
@@ -179,64 +237,20 @@ impl<'tcx> fmt::Show for VtableParamData<'tcx> {
 }
 
 /// See `super::obligations_for_generics`
-pub fn obligations_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                      cause: ObligationCause<'tcx>,
-                                      recursion_depth: uint,
-                                      generic_bounds: &ty::GenericBounds<'tcx>,
-                                      type_substs: &VecPerParamSpace<Ty<'tcx>>)
-                                      -> VecPerParamSpace<TraitObligation<'tcx>>
+pub fn predicates_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                     cause: ObligationCause<'tcx>,
+                                     recursion_depth: uint,
+                                     generic_bounds: &ty::GenericBounds<'tcx>)
+                                     -> VecPerParamSpace<PredicateObligation<'tcx>>
 {
+    debug!("predicates_for_generics(generic_bounds={})",
+           generic_bounds.repr(tcx));
 
-    debug!("obligations_for_generics(generic_bounds={}, type_substs={})",
-           generic_bounds.repr(tcx), type_substs.repr(tcx));
-
-    let mut obligations = VecPerParamSpace::empty();
-
-    for (space, index, bounds) in generic_bounds.types.iter_enumerated() {
-        push_obligations_for_param_bounds(tcx,
-                                          cause,
-                                          recursion_depth,
-                                          space,
-                                          index,
-                                          bounds,
-                                          type_substs,
-                                          &mut obligations);
-    }
-
-    debug!("obligations() ==> {}", obligations.repr(tcx));
-
-    return obligations;
-}
-
-fn push_obligations_for_param_bounds<'tcx>(
-    tcx: &ty::ctxt<'tcx>,
-    cause: ObligationCause<'tcx>,
-    recursion_depth: uint,
-    space: subst::ParamSpace,
-    index: uint,
-    param_bounds: &ty::ParamBounds<'tcx>,
-    param_type_substs: &VecPerParamSpace<Ty<'tcx>>,
-    obligations: &mut VecPerParamSpace<TraitObligation<'tcx>>)
-{
-    let param_ty = *param_type_substs.get(space, index);
-    for builtin_bound in param_bounds.builtin_bounds.iter() {
-        let obligation = obligation_for_builtin_bound(tcx,
-                                                      cause,
-                                                      builtin_bound,
-                                                      recursion_depth,
-                                                      param_ty);
-        if let Ok(ob) = obligation {
-            obligations.push(space, ob);
-        }
-    }
-
-    for bound_trait_ref in param_bounds.trait_bounds.iter() {
-        obligations.push(
-            space,
-            Obligation { cause: cause,
-                         recursion_depth: recursion_depth,
-                         trait_ref: (*bound_trait_ref).clone() });
-    }
+    generic_bounds.predicates.map(|predicate| {
+        Obligation { cause: cause,
+                     recursion_depth: recursion_depth,
+                     trait_ref: predicate.clone() }
+    })
 }
 
 pub fn trait_ref_for_builtin_bound<'tcx>(
@@ -259,19 +273,19 @@ pub fn trait_ref_for_builtin_bound<'tcx>(
     }
 }
 
-pub fn obligation_for_builtin_bound<'tcx>(
+pub fn predicate_for_builtin_bound<'tcx>(
     tcx: &ty::ctxt<'tcx>,
     cause: ObligationCause<'tcx>,
     builtin_bound: ty::BuiltinBound,
     recursion_depth: uint,
     param_ty: Ty<'tcx>)
-    -> Result<TraitObligation<'tcx>, ErrorReported>
+    -> Result<PredicateObligation<'tcx>, ErrorReported>
 {
     let trait_ref = try!(trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty));
     Ok(Obligation {
         cause: cause,
         recursion_depth: recursion_depth,
-        trait_ref: trait_ref
+        trait_ref: ty::Predicate::Trait(trait_ref),
     })
 }
 
@@ -358,10 +372,11 @@ impl<'tcx> Repr<'tcx> for super::SelectionError<'tcx> {
             super::Unimplemented =>
                 format!("Unimplemented"),
 
-            super::OutputTypeParameterMismatch(ref t, ref e) =>
-                format!("OutputTypeParameterMismatch({}, {})",
-                        t.repr(tcx),
-                        e.repr(tcx)),
+            super::OutputTypeParameterMismatch(ref a, ref b, ref c) =>
+                format!("OutputTypeParameterMismatch({},{},{})",
+                        a.repr(tcx),
+                        b.repr(tcx),
+                        c.repr(tcx)),
         }
     }
 }
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index ef8e3f3b2d7..ca226e2ca3f 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -44,6 +44,7 @@ use back::svh::Svh;
 use session::Session;
 use lint;
 use metadata::csearch;
+use middle;
 use middle::const_eval;
 use middle::def;
 use middle::dependency_format;
@@ -60,13 +61,14 @@ use middle::traits::ObligationCause;
 use middle::traits;
 use middle::ty;
 use middle::ty_fold::{mod, TypeFoldable, TypeFolder, HigherRankedFoldable};
-use middle;
 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_string};
 use util::ppaux::{trait_store_to_string, ty_to_string};
 use util::ppaux::{Repr, UserString};
-use util::common::{indenter, memoized};
+use util::common::{indenter, memoized, ErrorReported};
 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet};
 use util::nodemap::{FnvHashMap, FnvHashSet};
+
+use arena::TypedArena;
 use std::borrow::BorrowFrom;
 use std::cell::{Cell, RefCell};
 use std::cmp;
@@ -75,8 +77,8 @@ use std::hash::{Hash, sip, Writer};
 use std::mem;
 use std::ops;
 use std::rc::Rc;
+use std::collections::enum_set::{EnumSet, CLike};
 use std::collections::hash_map::{HashMap, Occupied, Vacant};
-use arena::TypedArena;
 use syntax::abi;
 use syntax::ast::{CrateNum, DefId, DUMMY_NODE_ID, FnStyle, Ident, ItemTrait, LOCAL_CRATE};
 use syntax::ast::{MutImmutable, MutMutable, Name, NamedField, NodeId};
@@ -87,7 +89,6 @@ use syntax::attr::{mod, AttrMetaMethods};
 use syntax::codemap::{DUMMY_SP, Span};
 use syntax::parse::token::{mod, InternedString};
 use syntax::{ast, ast_map};
-use std::collections::enum_set::{EnumSet, CLike};
 
 pub type Disr = u64;
 
@@ -1613,8 +1614,14 @@ pub struct RegionParameterDef {
     pub bounds: Vec<ty::Region>,
 }
 
-/// Information about the formal type/lifetime parameters associated with an
-/// item or method. Analogous to ast::Generics.
+impl RegionParameterDef {
+    pub fn to_early_bound_region(&self) -> ty::Region {
+        ty::ReEarlyBound(self.def_id.node, self.space, self.index, self.name)
+    }
+}
+
+/// Information about the formal type/lifetime parameters associated
+/// with an item or method. Analogous to ast::Generics.
 #[deriving(Clone, Show)]
 pub struct Generics<'tcx> {
     pub types: VecPerParamSpace<TypeParameterDef<'tcx>>,
@@ -1622,21 +1629,6 @@ pub struct Generics<'tcx> {
     pub predicates: VecPerParamSpace<Predicate<'tcx>>,
 }
 
-#[deriving(Clone, Show)]
-pub enum Predicate<'tcx> {
-    /// where Foo : Bar
-    Trait(Rc<TraitRef<'tcx>>),
-
-    /// where Foo == Bar
-    Equate(Ty<'tcx>, Ty<'tcx>),
-
-    /// where 'a : 'b
-    RegionOutlives(Region, Region),
-
-    /// where T : 'a
-    TypeOutlives(Ty<'tcx>, Region),
-}
-
 impl<'tcx> Generics<'tcx> {
     pub fn empty() -> Generics<'tcx> {
         Generics {
@@ -1657,8 +1649,47 @@ impl<'tcx> Generics<'tcx> {
     pub fn to_bounds(&self, tcx: &ty::ctxt<'tcx>, substs: &Substs<'tcx>)
                      -> GenericBounds<'tcx> {
         GenericBounds {
-            types: self.types.map(|d| d.bounds.subst(tcx, substs)),
-            regions: self.regions.map(|d| d.bounds.subst(tcx, substs)),
+            predicates: self.predicates.subst(tcx, substs),
+        }
+    }
+}
+
+#[deriving(Clone, PartialEq, Eq, Hash, Show)]
+pub enum Predicate<'tcx> {
+    /// where Foo : Bar
+    Trait(Rc<TraitRef<'tcx>>),
+
+    /// where Foo == Bar
+    Equate(Ty<'tcx>, Ty<'tcx>),
+
+    /// where 'a : 'b
+    RegionOutlives(Region, Region),
+
+    /// where T : 'a
+    TypeOutlives(Ty<'tcx>, Region),
+}
+
+impl<'tcx> Predicate<'tcx> {
+    pub fn has_escaping_regions(&self) -> bool {
+        match *self {
+            Predicate::Trait(ref trait_ref) => trait_ref.has_escaping_regions(),
+            Predicate::Equate(a, b) => (ty::type_has_escaping_regions(a) ||
+                                        ty::type_has_escaping_regions(b)),
+            Predicate::RegionOutlives(a, b) => a.escapes_depth(0) || b.escapes_depth(0),
+            Predicate::TypeOutlives(a, b) => ty::type_has_escaping_regions(a) || b.escapes_depth(0),
+        }
+    }
+
+    pub fn to_trait(&self) -> Option<Rc<TraitRef<'tcx>>> {
+        match *self {
+            Predicate::Trait(ref t) => {
+                Some(t.clone())
+            }
+            Predicate::Equate(..) |
+            Predicate::RegionOutlives(..) |
+            Predicate::TypeOutlives(..) => {
+                None
+            }
         }
     }
 }
@@ -1684,19 +1715,20 @@ impl<'tcx> Generics<'tcx> {
 /// [uint:Bar<int>]]`.
 #[deriving(Clone, Show)]
 pub struct GenericBounds<'tcx> {
-    pub types: VecPerParamSpace<ParamBounds<'tcx>>,
-    pub regions: VecPerParamSpace<Vec<Region>>,
+    pub predicates: VecPerParamSpace<Predicate<'tcx>>,
 }
 
 impl<'tcx> GenericBounds<'tcx> {
     pub fn empty() -> GenericBounds<'tcx> {
-        GenericBounds { types: VecPerParamSpace::empty(),
-                        regions: VecPerParamSpace::empty() }
+        GenericBounds { predicates: VecPerParamSpace::empty() }
     }
 
     pub fn has_escaping_regions(&self) -> bool {
-        self.types.any(|pb| pb.trait_bounds.iter().any(|tr| tr.has_escaping_regions())) ||
-            self.regions.any(|rs| rs.iter().any(|r| r.escapes_depth(0)))
+        self.predicates.any(|p| p.has_escaping_regions())
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.predicates.is_empty()
     }
 }
 
@@ -1747,9 +1779,6 @@ pub struct ParameterEnvironment<'tcx> {
     /// parameters in the same way, this only has an effect on regions.
     pub free_substs: Substs<'tcx>,
 
-    /// Bounds on the various type parameters
-    pub bounds: VecPerParamSpace<ParamBounds<'tcx>>,
-
     /// Each type parameter has an implicit region bound that
     /// indicates it must outlive at least the function body (the user
     /// may specify stronger requirements). This field indicates the
@@ -1759,10 +1788,7 @@ pub struct ParameterEnvironment<'tcx> {
     /// Obligations that the caller must satisfy. This is basically
     /// the set of bounds on the in-scope type parameters, translated
     /// into Obligations.
-    ///
-    /// Note: This effectively *duplicates* the `bounds` array for
-    /// now.
-    pub caller_obligations: VecPerParamSpace<traits::TraitObligation<'tcx>>,
+    pub caller_bounds: ty::GenericBounds<'tcx>,
 
     /// Caches the results of trait selection. This cache is used
     /// for things that have to do with the parameters in scope.
@@ -3160,7 +3186,8 @@ pub fn type_contents<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> TypeContents {
 pub fn type_moves_by_default<'tcx>(cx: &ctxt<'tcx>,
                                    ty: Ty<'tcx>,
                                    param_env: &ParameterEnvironment<'tcx>)
-                                    -> bool {
+                                   -> bool
+{
     if !type_has_params(ty) && !type_has_self(ty) {
         match cx.type_moves_by_default_cache.borrow().get(&ty) {
             None => {}
@@ -3181,20 +3208,20 @@ pub fn type_moves_by_default<'tcx>(cx: &ctxt<'tcx>,
     // (there shouldn't really be any anyhow)
     let cause = ObligationCause::misc(DUMMY_SP, DUMMY_NODE_ID);
 
-    let obligation = traits::obligation_for_builtin_bound(
-        cx,
-        cause,
-        ty,
-        ty::BoundCopy).unwrap();
-    fulfill_cx.register_obligation(cx, obligation);
-    let result = !fulfill_cx.select_all_or_error(&infcx,
-                                                 param_env,
-                                                 cx).is_ok();
-    cx.type_moves_by_default_cache.borrow_mut().insert(ty, result);
+    fulfill_cx.register_builtin_bound(cx, ty, ty::BoundCopy, cause);
+
+    // Note: we only assuming something is `Copy` if we can
+    // *definitively* show that it implements `Copy`. Otherwise,
+    // assume it is move; linear is always ok.
+    let is_copy = fulfill_cx.select_all_or_error(&infcx, param_env, cx).is_ok();
+    let is_move = !is_copy;
+
     debug!("determined whether {} moves by default: {}",
            ty_to_string(cx, ty),
-           result);
-    result
+           is_move);
+
+    cx.type_moves_by_default_cache.borrow_mut().insert(ty, is_move);
+    is_move
 }
 
 pub fn is_ffi_safe<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
@@ -5006,9 +5033,9 @@ pub fn lookup_trait_def<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
 
 /// Given a reference to a trait, returns the bounds declared on the
 /// trait, with appropriate substitutions applied.
-pub fn bounds_for_trait_ref<'tcx>(tcx: &ctxt<'tcx>,
-                                  trait_ref: &TraitRef<'tcx>)
-                                  -> ty::ParamBounds<'tcx>
+pub fn predicates_for_trait_ref<'tcx>(tcx: &ctxt<'tcx>,
+                                      trait_ref: &TraitRef<'tcx>)
+                                      -> Vec<ty::Predicate<'tcx>>
 {
     let trait_def = lookup_trait_def(tcx, trait_ref.def_id);
 
@@ -5099,11 +5126,39 @@ pub fn bounds_for_trait_ref<'tcx>(tcx: &ctxt<'tcx>,
     let builtin_bounds =
         trait_def.bounds.builtin_bounds.subst(tcx, &trait_ref.substs);
 
-    ty::ParamBounds {
+    let bounds = ty::ParamBounds {
         trait_bounds: trait_bounds,
         region_bounds: region_bounds,
         builtin_bounds: builtin_bounds,
+    };
+
+    predicates(tcx, trait_ref.self_ty(), &bounds)
+}
+
+pub fn predicates<'tcx>(
+    tcx: &ctxt<'tcx>,
+    param_ty: Ty<'tcx>,
+    bounds: &ParamBounds<'tcx>)
+    -> Vec<Predicate<'tcx>>
+{
+    let mut vec = Vec::new();
+
+    for builtin_bound in bounds.builtin_bounds.iter() {
+        match traits::trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty) {
+            Ok(trait_ref) => { vec.push(Predicate::Trait(trait_ref)); }
+            Err(ErrorReported) => { }
+        }
+    }
+
+    for &region_bound in bounds.region_bounds.iter() {
+        vec.push(Predicate::TypeOutlives(param_ty, region_bound));
+    }
+
+    for bound_trait_ref in bounds.trait_bounds.iter() {
+        vec.push(Predicate::Trait((*bound_trait_ref).clone()));
     }
+
+    vec
 }
 
 /// Iterate over attributes of a definition.
@@ -5461,56 +5516,62 @@ pub fn each_bound_trait_and_supertraits<'tcx>(tcx: &ctxt<'tcx>,
     return true;
 }
 
+pub fn object_region_bounds<'tcx>(tcx: &ctxt<'tcx>,
+                                  opt_principal: Option<&TraitRef<'tcx>>, // None for boxed closures
+                                  others: BuiltinBounds)
+                                  -> Vec<ty::Region>
+{
+    // Since we don't actually *know* the self type for an object,
+    // this "open(err)" serves as a kind of dummy standin -- basically
+    // a skolemized type.
+    let open_ty = ty::mk_infer(tcx, SkolemizedTy(0));
+
+    let opt_trait_ref = opt_principal.map_or(Vec::new(), |principal| {
+        let substs = principal.substs.with_self_ty(open_ty);
+        vec!(Rc::new(ty::TraitRef::new(principal.def_id, substs)))
+    });
+
+    let param_bounds = ty::ParamBounds {
+        region_bounds: Vec::new(),
+        builtin_bounds: others,
+        trait_bounds: opt_trait_ref,
+    };
+
+    let predicates = ty::predicates(tcx, open_ty, &param_bounds);
+    ty::required_region_bounds(tcx, open_ty, predicates)
+}
+
 /// Given a type which must meet the builtin bounds and trait bounds, returns a set of lifetimes
 /// which the type must outlive.
 ///
 /// Requires that trait definitions have been processed.
 pub fn required_region_bounds<'tcx>(tcx: &ctxt<'tcx>,
-                                    region_bounds: &[ty::Region],
-                                    builtin_bounds: BuiltinBounds,
-                                    trait_bounds: &[Rc<TraitRef<'tcx>>])
+                                    param_ty: Ty<'tcx>,
+                                    predicates: Vec<ty::Predicate<'tcx>>)
                                     -> Vec<ty::Region>
 {
-    let mut all_bounds = Vec::new();
-
-    debug!("required_region_bounds(builtin_bounds={}, trait_bounds={})",
-           builtin_bounds.repr(tcx),
-           trait_bounds.repr(tcx));
-
-    all_bounds.push_all(region_bounds);
-
-    push_region_bounds(&[],
-                       builtin_bounds,
-                       &mut all_bounds);
-
-    debug!("from builtin bounds: all_bounds={}", all_bounds.repr(tcx));
-
-    each_bound_trait_and_supertraits(
-        tcx,
-        trait_bounds,
-        |trait_ref| {
-            let bounds = ty::bounds_for_trait_ref(tcx, &*trait_ref);
-            push_region_bounds(bounds.region_bounds.as_slice(),
-                               bounds.builtin_bounds,
-                               &mut all_bounds);
-            debug!("from {}: bounds={} all_bounds={}",
-                   trait_ref.repr(tcx),
-                   bounds.repr(tcx),
-                   all_bounds.repr(tcx));
-            true
-        });
-
-    return all_bounds;
-
-    fn push_region_bounds(region_bounds: &[ty::Region],
-                          builtin_bounds: ty::BuiltinBounds,
-                          all_bounds: &mut Vec<ty::Region>) {
-        all_bounds.push_all(region_bounds.as_slice());
-
-        if builtin_bounds.contains(&ty::BoundSend) {
-            all_bounds.push(ty::ReStatic);
-        }
-    }
+    debug!("required_region_bounds(param_ty={}, predicates={})",
+           param_ty.repr(tcx),
+           predicates.repr(tcx));
+
+    traits::elaborate_predicates(tcx, predicates)
+        .filter_map(|predicate| {
+            match predicate {
+                ty::Predicate::Trait(..) |
+                ty::Predicate::Equate(..) |
+                ty::Predicate::RegionOutlives(..) => {
+                    None
+                }
+                ty::Predicate::TypeOutlives(t, r) => {
+                    if t == param_ty {
+                        Some(r)
+                    } else {
+                        None
+                    }
+                }
+            }
+        })
+        .collect()
 }
 
 pub fn get_tydesc_ty<'tcx>(tcx: &ctxt<'tcx>) -> Result<Ty<'tcx>, String> {
@@ -5860,8 +5921,7 @@ impl Variance {
 /// are no free type/lifetime parameters in scope.
 pub fn empty_parameter_environment<'tcx>() -> ParameterEnvironment<'tcx> {
     ty::ParameterEnvironment { free_substs: Substs::empty(),
-                               bounds: VecPerParamSpace::empty(),
-                               caller_obligations: VecPerParamSpace::empty(),
+                               caller_bounds: GenericBounds::empty(),
                                implicit_region_bound: ty::ReEmpty,
                                selection_cache: traits::SelectionCache::new(), }
 }
@@ -5906,11 +5966,6 @@ pub fn construct_parameter_environment<'tcx>(
 
     let bounds = generics.to_bounds(tcx, &free_substs);
     let bounds = liberate_late_bound_regions(tcx, free_id_scope, &bind(bounds)).value;
-    let obligations = traits::obligations_for_generics(tcx,
-                                                       traits::ObligationCause::dummy(),
-                                                       &bounds,
-                                                       &free_substs.types);
-    let type_bounds = bounds.types.subst(tcx, &free_substs);
 
     //
     // Compute region bounds. For now, these relations are stored in a
@@ -5918,23 +5973,17 @@ pub fn construct_parameter_environment<'tcx>(
     // crazy about this scheme, but it's convenient, at least.
     //
 
-    for &space in subst::ParamSpace::all().iter() {
-        record_region_bounds(tcx, space, &free_substs, bounds.regions.get_slice(space));
-    }
-
+    record_region_bounds(tcx, &bounds);
 
-    debug!("construct_parameter_environment: free_id={} free_subst={} \
-           obligations={} type_bounds={}",
+    debug!("construct_parameter_environment: free_id={} free_subst={} bounds={}",
            free_id,
            free_substs.repr(tcx),
-           obligations.repr(tcx),
-           type_bounds.repr(tcx));
+           bounds.repr(tcx));
 
     return ty::ParameterEnvironment {
         free_substs: free_substs,
-        bounds: bounds.types,
         implicit_region_bound: ty::ReScope(free_id_scope),
-        caller_obligations: obligations,
+        caller_bounds: bounds,
         selection_cache: traits::SelectionCache::new(),
     };
 
@@ -5963,31 +6012,24 @@ pub fn construct_parameter_environment<'tcx>(
         }
     }
 
-    fn record_region_bounds<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                  space: subst::ParamSpace,
-                                  free_substs: &Substs<'tcx>,
-                                  bound_sets: &[Vec<ty::Region>]) {
-        for (subst_region, bound_set) in
-            free_substs.regions().get_slice(space).iter().zip(
-                bound_sets.iter())
-        {
-            // For each region parameter 'subst...
-            for bound_region in bound_set.iter() {
-                // Which is declared with a bound like 'subst:'bound...
-                match (subst_region, bound_region) {
-                    (&ty::ReFree(subst_fr), &ty::ReFree(bound_fr)) => {
-                        // Record that 'subst outlives 'bound. Or, put
-                        // another way, 'bound <= 'subst.
-                        tcx.region_maps.relate_free_regions(bound_fr, subst_fr);
-                    },
-                    _ => {
-                        // All named regions are instantiated with free regions.
-                        tcx.sess.bug(
-                            format!("record_region_bounds: \
-                                     non free region: {} / {}",
-                                    subst_region.repr(tcx),
-                                    bound_region.repr(tcx)).as_slice());
-                    }
+    fn record_region_bounds<'tcx>(tcx: &ty::ctxt<'tcx>, bounds: &GenericBounds<'tcx>) {
+        debug!("record_region_bounds(bounds={})", bounds.repr(tcx));
+
+        for predicate in bounds.predicates.iter() {
+            match *predicate {
+                Predicate::Trait(..) | Predicate::Equate(..) | Predicate::TypeOutlives(..) => {
+                    // No region bounds here
+                }
+                Predicate::RegionOutlives(ty::ReFree(fr_a), ty::ReFree(fr_b)) => {
+                    // Record that `'a:'b`. Or, put another way, `'b <= 'a`.
+                    tcx.region_maps.relate_free_regions(fr_b, fr_a);
+                }
+                Predicate::RegionOutlives(r_a, r_b) => {
+                    // All named regions are instantiated with free regions.
+                    tcx.sess.bug(
+                        format!("record_region_bounds: non free region: {} / {}",
+                                r_a.repr(tcx),
+                                r_b.repr(tcx)).as_slice());
                 }
             }
         }
@@ -6306,6 +6348,17 @@ impl<'tcx> Repr<'tcx> for TyTrait<'tcx> {
     }
 }
 
+impl<'tcx> Repr<'tcx> for ty::Predicate<'tcx> {
+    fn repr(&self, tcx: &ctxt<'tcx>) -> String {
+        match *self {
+            Predicate::Trait(ref a) => a.repr(tcx),
+            Predicate::Equate(a, b) => format!("Equate({},{})", a.repr(tcx), b.repr(tcx)),
+            Predicate::RegionOutlives(a, b) => format!("Outlives({}:{})", a.repr(tcx), b.repr(tcx)),
+            Predicate::TypeOutlives(a, b) => format!("Outlives({}:{})", a.repr(tcx), b.repr(tcx)),
+        }
+    }
+}
+
 impl<'tcx> Repr<'tcx> for vtable_origin<'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         match *self {
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 87467ba064a..8b54a46bfb9 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -425,8 +425,7 @@ impl<'tcx> TypeFoldable<'tcx> for ty::Predicate<'tcx> {
 impl<'tcx> TypeFoldable<'tcx> for ty::GenericBounds<'tcx> {
     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::GenericBounds<'tcx> {
         ty::GenericBounds {
-            types: self.types.fold_with(folder),
-            regions: self.regions.fold_with(folder),
+            predicates: self.predicates.fold_with(folder),
         }
     }
 }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 3895a113726..7a14ed9cca8 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -914,17 +914,17 @@ impl<'tcx> Repr<'tcx> for ty::Polytype<'tcx> {
 
 impl<'tcx> Repr<'tcx> for ty::Generics<'tcx> {
     fn repr(&self, tcx: &ctxt<'tcx>) -> String {
-        format!("Generics(types: {}, regions: {})",
+        format!("Generics(types: {}, regions: {}, predicates: {})",
                 self.types.repr(tcx),
-                self.regions.repr(tcx))
+                self.regions.repr(tcx),
+                self.predicates.repr(tcx))
     }
 }
 
 impl<'tcx> Repr<'tcx> for ty::GenericBounds<'tcx> {
     fn repr(&self, tcx: &ctxt<'tcx>) -> String {
-        format!("GenericBounds(types: {}, regions: {})",
-                self.types.repr(tcx),
-                self.regions.repr(tcx))
+        format!("GenericBounds({})",
+                self.predicates.repr(tcx))
     }
 }
 
diff --git a/src/librustc_trans/trans/common.rs b/src/librustc_trans/trans/common.rs
index da6aa84cfa1..83938fa3357 100644
--- a/src/librustc_trans/trans/common.rs
+++ b/src/librustc_trans/trans/common.rs
@@ -827,8 +827,8 @@ pub fn fulfill_obligation<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
     // fully bound. It could be a slight optimization to stop
     // iterating early.
     let mut fulfill_cx = traits::FulfillmentContext::new();
-    let vtable = selection.map_move_nested(|obligation| {
-        fulfill_cx.register_obligation(tcx, obligation);
+    let vtable = selection.map_move_nested(|predicate| {
+        fulfill_cx.register_predicate(infcx.tcx, predicate);
     });
     match fulfill_cx.select_all_or_error(&infcx, &param_env, tcx) {
         Ok(()) => { }
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index e4edfadb3aa..4ad0d2b8293 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -800,7 +800,7 @@ fn trait_ref_to_object_type<'tcx,AC,RS>(this: &AC,
     let existential_bounds = conv_existential_bounds(this,
                                                      rscope,
                                                      span,
-                                                     &[Rc::new(trait_ref.clone())],
+                                                     Some(&trait_ref),
                                                      bounds);
 
     let result = ty::mk_trait(this.tcx(), trait_ref, existential_bounds);
@@ -918,7 +918,7 @@ pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
                 let bounds = conv_existential_bounds(this,
                                                      rscope,
                                                      ast_ty.span,
-                                                     [].as_slice(),
+                                                     None,
                                                      f.bounds.as_slice());
                 let fn_decl = ty_of_closure(this,
                                             f.fn_style,
@@ -935,9 +935,10 @@ pub fn ast_ty_to_ty<'tcx, AC: AstConv<'tcx>, RS: RegionScope>(
             ast::TyProc(ref f) => {
                 // Use corresponding trait store to figure out default bounds
                 // if none were specified.
-                let bounds = conv_existential_bounds(this, rscope,
+                let bounds = conv_existential_bounds(this,
+                                                     rscope,
                                                      ast_ty.span,
-                                                     [].as_slice(),
+                                                     None,
                                                      f.bounds.as_slice());
 
                 let fn_decl = ty_of_closure(this,
@@ -1370,7 +1371,7 @@ pub fn conv_existential_bounds<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
     this: &AC,
     rscope: &RS,
     span: Span,
-    main_trait_refs: &[Rc<ty::TraitRef<'tcx>>],
+    principal_trait_ref: Option<&ty::TraitRef<'tcx>>, // None for boxed closures
     ast_bounds: &[ast::TyParamBound])
     -> ty::ExistentialBounds
 {
@@ -1381,7 +1382,7 @@ pub fn conv_existential_bounds<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
         partition_bounds(this.tcx(), span, ast_bound_refs.as_slice());
 
     conv_existential_bounds_from_partitioned_bounds(
-        this, rscope, span, main_trait_refs, partitioned_bounds)
+        this, rscope, span, principal_trait_ref, partitioned_bounds)
 }
 
 fn conv_ty_poly_trait_ref<'tcx, AC, RS>(
@@ -1411,11 +1412,12 @@ fn conv_ty_poly_trait_ref<'tcx, AC, RS>(
         }
     };
 
-    let bounds = conv_existential_bounds_from_partitioned_bounds(this,
-                                                                 rscope,
-                                                                 span,
-                                                                 main_trait_bound.as_slice(),
-                                                                 partitioned_bounds);
+    let bounds =
+        conv_existential_bounds_from_partitioned_bounds(this,
+                                                        rscope,
+                                                        span,
+                                                        main_trait_bound.as_ref().map(|tr| &**tr),
+                                                        partitioned_bounds);
 
     match main_trait_bound {
         None => ty::mk_err(),
@@ -1427,7 +1429,7 @@ pub fn conv_existential_bounds_from_partitioned_bounds<'tcx, AC, RS>(
     this: &AC,
     rscope: &RS,
     span: Span,
-    main_trait_refs: &[Rc<ty::TraitRef<'tcx>>],
+    principal_trait_ref: Option<&ty::TraitRef<'tcx>>, // None for boxed closures
     partitioned_bounds: PartitionedBounds)
     -> ty::ExistentialBounds
     where AC: AstConv<'tcx>, RS:RegionScope
@@ -1445,28 +1447,12 @@ pub fn conv_existential_bounds_from_partitioned_bounds<'tcx, AC, RS>(
                      as closure or object bounds").as_slice());
     }
 
-    // The "main trait refs", rather annoyingly, have no type
-    // specified for the `Self` parameter of the trait. The reason for
-    // this is that they are, after all, *existential* types, and
-    // hence that type is unknown. However, leaving this type missing
-    // causes the substitution code to go all awry when walking the
-    // bounds, so here we clone those trait refs and insert ty::err as
-    // the self type. Perhaps we should do this more generally, it'd
-    // be convenient (or perhaps something else, i.e., ty::erased).
-    let main_trait_refs: Vec<Rc<ty::TraitRef>> =
-        main_trait_refs.iter()
-        .map(|t|
-             Rc::new(ty::TraitRef {
-                 def_id: t.def_id,
-                 substs: t.substs.with_self_ty(ty::mk_err()) }))
-        .collect();
-
     let region_bound = compute_region_bound(this,
                                             rscope,
                                             span,
-                                            builtin_bounds,
                                             region_bounds.as_slice(),
-                                            main_trait_refs.as_slice());
+                                            principal_trait_ref,
+                                            builtin_bounds);
 
     ty::ExistentialBounds {
         region_bound: region_bound,
@@ -1478,33 +1464,35 @@ pub fn conv_existential_bounds_from_partitioned_bounds<'tcx, AC, RS>(
 /// (if any) we can use to summarize this type. The basic idea is that we will use the bound the
 /// user provided, if they provided one, and otherwise search the supertypes of trait bounds for
 /// region bounds. It may be that we can derive no bound at all, in which case we return `None`.
-pub fn compute_opt_region_bound<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                      span: Span,
-                                      builtin_bounds: ty::BuiltinBounds,
-                                      region_bounds: &[&ast::Lifetime],
-                                      trait_bounds: &[Rc<ty::TraitRef<'tcx>>])
-                                      -> Option<ty::Region>
+fn compute_opt_region_bound<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                  span: Span,
+                                  explicit_region_bounds: &[&ast::Lifetime],
+                                  principal_trait_ref: Option<&ty::TraitRef<'tcx>>,
+                                  builtin_bounds: ty::BuiltinBounds)
+                                  -> Option<ty::Region>
 {
-    if region_bounds.len() > 1 {
+    debug!("compute_opt_region_bound(explicit_region_bounds={}, \
+           principal_trait_ref={}, builtin_bounds={})",
+           explicit_region_bounds,
+           principal_trait_ref.repr(tcx),
+           builtin_bounds.repr(tcx));
+
+    if explicit_region_bounds.len() > 1 {
         tcx.sess.span_err(
-            region_bounds[1].span,
+            explicit_region_bounds[1].span,
             format!("only a single explicit lifetime bound is permitted").as_slice());
     }
 
-    if region_bounds.len() != 0 {
+    if explicit_region_bounds.len() != 0 {
         // Explicitly specified region bound. Use that.
-        let r = region_bounds[0];
+        let r = explicit_region_bounds[0];
         return Some(ast_region_to_region(tcx, r));
     }
 
     // No explicit region bound specified. Therefore, examine trait
     // bounds and see if we can derive region bounds from those.
     let derived_region_bounds =
-        ty::required_region_bounds(
-            tcx,
-            &[],
-            builtin_bounds,
-            trait_bounds);
+        ty::object_region_bounds(tcx, principal_trait_ref, builtin_bounds);
 
     // If there are no derived region bounds, then report back that we
     // can find no region bound.
@@ -1538,13 +1526,13 @@ fn compute_region_bound<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
     this: &AC,
     rscope: &RS,
     span: Span,
-    builtin_bounds: ty::BuiltinBounds,
     region_bounds: &[&ast::Lifetime],
-    trait_bounds: &[Rc<ty::TraitRef<'tcx>>])
+    principal_trait_ref: Option<&ty::TraitRef<'tcx>>, // None for closures
+    builtin_bounds: ty::BuiltinBounds)
     -> ty::Region
 {
-    match compute_opt_region_bound(this.tcx(), span, builtin_bounds,
-                                   region_bounds, trait_bounds) {
+    match compute_opt_region_bound(this.tcx(), span, region_bounds,
+                                   principal_trait_ref, builtin_bounds) {
         Some(r) => r,
         None => {
             match rscope.default_region_bound(span) {
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index 34030ae4493..2b34b4a55b7 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -232,16 +232,24 @@ fn deduce_unboxed_closure_expectations_from_obligations<'a,'tcx>(
     -> Option<(ty::FnSig<'tcx>, ty::UnboxedClosureKind)>
 {
     // Here `expected_ty` is known to be a type inference variable.
-    for obligation in fcx.inh.fulfillment_cx.borrow().pending_trait_obligations().iter() {
-        let obligation_self_ty = fcx.infcx().shallow_resolve(obligation.self_ty());
-        match obligation_self_ty.sty {
-            ty::ty_infer(ty::TyVar(v)) if expected_vid == v => { }
-            _ => { continue; }
-        }
+    for obligation in fcx.inh.fulfillment_cx.borrow().pending_obligations().iter() {
+        match obligation.trait_ref {
+            ty::Predicate::Trait(ref trait_ref) => {
+                let self_ty = fcx.infcx().shallow_resolve(trait_ref.self_ty());
+                match self_ty.sty {
+                    ty::ty_infer(ty::TyVar(v)) if expected_vid == v => { }
+                    _ => { continue; }
+                }
 
-        match deduce_unboxed_closure_expectations_from_trait_ref(fcx, &*obligation.trait_ref) {
-            Some(e) => { return Some(e); }
-            None => { }
+                match deduce_unboxed_closure_expectations_from_trait_ref(fcx, &**trait_ref) {
+                    Some(e) => { return Some(e); }
+                    None => { }
+                }
+            }
+            ty::Predicate::Equate(..) |
+            ty::Predicate::RegionOutlives(..) |
+            ty::Predicate::TypeOutlives(..) => {
+            }
         }
     }
 
diff --git a/src/librustc_typeck/check/method/confirm.rs b/src/librustc_typeck/check/method/confirm.rs
index 7b43b97a4bb..bf1f2c0ce80 100644
--- a/src/librustc_typeck/check/method/confirm.rs
+++ b/src/librustc_typeck/check/method/confirm.rs
@@ -463,7 +463,6 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
 
         self.fcx.add_obligations_for_parameters(
             traits::ObligationCause::misc(self.span, self.fcx.body_id),
-            method_bounds_substs,
             method_bounds);
 
         self.fcx.add_default_region_param_bounds(
diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs
index 1ab76740962..d081b97b71a 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -169,7 +169,9 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
     let trait_ref = Rc::new(ty::TraitRef::new(trait_def_id, substs));
 
     // Construct an obligation
-    let obligation = traits::Obligation::misc(span, fcx.body_id, trait_ref.clone());
+    let obligation = traits::Obligation::misc(span,
+                                              fcx.body_id,
+                                              ty::Predicate::Trait(trait_ref.clone()));
 
     // Now we want to know if this can be matched
     let mut selcx = traits::SelectionContext::new(fcx.infcx(),
@@ -187,6 +189,9 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
     assert_eq!(method_ty.generics.types.len(subst::FnSpace), 0);
     assert_eq!(method_ty.generics.regions.len(subst::FnSpace), 0);
 
+    debug!("lookup_in_trait_adjusted: method_num={} method_ty={}",
+           method_num, method_ty.repr(fcx.tcx()));
+
     // Substitute the trait parameters into the method type and
     // instantiate late-bound regions to get the actual method type.
     //
@@ -204,7 +209,7 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
         abi: bare_fn_ty.abi.clone(),
     });
 
-    debug!("matched method fty={} obligation={}",
+    debug!("lookup_in_trait_adjusted: matched method fty={} obligation={}",
            fty.repr(fcx.tcx()),
            obligation.repr(fcx.tcx()));
 
@@ -220,7 +225,6 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
     assert!(!method_bounds.has_escaping_regions());
     fcx.add_obligations_for_parameters(
         traits::ObligationCause::misc(span, fcx.body_id),
-        &trait_ref.substs,
         &method_bounds);
 
     // FIXME(#18653) -- Try to resolve obligations, giving us more
@@ -233,8 +237,8 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
         None => { }
 
         Some(self_expr) => {
-            debug!("inserting adjustment if needed (self-id = {}, \
-                   base adjustment = {}, explicit self = {})",
+            debug!("lookup_in_trait_adjusted: inserting adjustment if needed \
+                   (self-id={}, base adjustment={}, explicit_self={})",
                    self_expr.id, autoderefref, method_ty.explicit_self);
 
             match method_ty.explicit_self {
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 3d7590db748..f0f527f6673 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -353,11 +353,27 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                                                param_ty: ty::ParamTy) {
         // FIXME -- Do we want to commit to this behavior for param bounds?
 
-        let ty::ParamTy { space, idx: index, .. } = param_ty;
-        let bounds =
-            self.fcx.inh.param_env.bounds.get(space, index).trait_bounds
-            .as_slice();
-        self.elaborate_bounds(bounds, true, |this, trait_ref, m, method_num| {
+        let bounds: Vec<_> =
+            self.fcx.inh.param_env.caller_bounds.predicates
+            .iter()
+            .filter_map(|predicate| {
+                match *predicate {
+                    ty::Predicate::Trait(ref trait_ref) => {
+                        match trait_ref.self_ty().sty {
+                            ty::ty_param(ref p) if *p == param_ty => Some(trait_ref.clone()),
+                            _ => None
+                        }
+                    }
+                    ty::Predicate::Equate(..) |
+                    ty::Predicate::RegionOutlives(..) |
+                    ty::Predicate::TypeOutlives(..) => {
+                        None
+                    }
+                }
+            })
+            .collect();
+
+        self.elaborate_bounds(bounds.as_slice(), true, |this, trait_ref, m, method_num| {
             let xform_self_ty =
                 this.xform_self_ty(&m, &trait_ref.substs);
 
@@ -400,6 +416,8 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                           m: Rc<ty::Method<'tcx>>,
                           method_num: uint|)
     {
+        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) {
@@ -802,11 +820,10 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
 
                     // Convert the bounds into obligations.
                     let obligations =
-                        traits::obligations_for_generics(
+                        traits::predicates_for_generics(
                             self.tcx(),
                             traits::ObligationCause::misc(self.span, self.fcx.body_id),
-                            &impl_bounds,
-                            &substs.types);
+                            &impl_bounds);
                     debug!("impl_obligations={}", obligations.repr(self.tcx()));
 
                     // Evaluate those obligations to see if they might possibly hold.
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index cd5cade78db..73fae976097 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -104,6 +104,7 @@ use {CrateCtxt, lookup_def_ccx, no_params, require_same_types};
 use TypeAndSubsts;
 use middle::lang_items::TypeIdLangItem;
 use lint;
+use util::common::ErrorReported;
 use util::common::{block_query, indenter, loop_query};
 use util::ppaux::{mod, UserString, Repr};
 use util::nodemap::{DefIdMap, FnvHashMap, NodeMap};
@@ -1761,7 +1762,6 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 span,
                 self.body_id,
                 traits::ItemObligation(def_id)),
-            &substs,
             &bounds);
         let monotype =
             polytype.ty.subst(self.tcx(), &substs);
@@ -1785,14 +1785,10 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                               code: traits::ObligationCauseCode<'tcx>,
                               bound: ty::BuiltinBound)
     {
-        let obligation = traits::obligation_for_builtin_bound(
-            self.tcx(),
-            traits::ObligationCause::new(span, self.body_id, code),
+        self.register_builtin_bound(
             ty,
-            bound);
-        if let Ok(ob) = obligation {
-            self.register_obligation(ob);
-        }
+            bound,
+            traits::ObligationCause::new(span, self.body_id, code));
     }
 
     pub fn require_type_is_sized(&self,
@@ -1810,15 +1806,24 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         self.require_type_is_sized(self.expr_ty(expr), expr.span, code);
     }
 
-    pub fn register_obligation(&self,
-                               obligation: traits::TraitObligation<'tcx>)
+    pub fn register_builtin_bound(&self,
+                                  ty: Ty<'tcx>,
+                                  builtin_bound: ty::BuiltinBound,
+                                  cause: traits::ObligationCause<'tcx>)
+    {
+        self.inh.fulfillment_cx.borrow_mut()
+            .register_builtin_bound(self.tcx(), ty, builtin_bound, cause);
+    }
+
+    pub fn register_predicate(&self,
+                              obligation: traits::PredicateObligation<'tcx>)
     {
-        debug!("register_obligation({})",
+        debug!("register_predicate({})",
                obligation.repr(self.tcx()));
 
         self.inh.fulfillment_cx
             .borrow_mut()
-            .register_obligation(self.tcx(), obligation);
+            .register_predicate(self.tcx(), obligation);
     }
 
     pub fn to_ty(&self, ast_t: &ast::Ty) -> Ty<'tcx> {
@@ -1958,7 +1963,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                                       cause: traits::ObligationCause<'tcx>)
     {
         let mut fulfillment_cx = self.inh.fulfillment_cx.borrow_mut();
-        fulfillment_cx.register_region_obligation(ty, region, cause);
+        fulfillment_cx.register_region_obligation(self.tcx(), ty, region, cause);
     }
 
     pub fn add_default_region_param_bounds(&self,
@@ -1993,90 +1998,18 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     /// and `T`. This routine will add a region obligation `$1:'$0` and register it locally.
     pub fn add_obligations_for_parameters(&self,
                                           cause: traits::ObligationCause<'tcx>,
-                                          substs: &Substs<'tcx>,
                                           generic_bounds: &ty::GenericBounds<'tcx>)
     {
         assert!(!generic_bounds.has_escaping_regions());
 
-        debug!("add_obligations_for_parameters(substs={}, generic_bounds={})",
-               substs.repr(self.tcx()),
+        debug!("add_obligations_for_parameters(generic_bounds={})",
                generic_bounds.repr(self.tcx()));
 
-        self.add_trait_obligations_for_generics(cause, substs, generic_bounds);
-        self.add_region_obligations_for_generics(cause, substs, generic_bounds);
-    }
+        let obligations = traits::predicates_for_generics(self.tcx(),
+                                                          cause,
+                                                          generic_bounds);
 
-    fn add_trait_obligations_for_generics(&self,
-                                          cause: traits::ObligationCause<'tcx>,
-                                          substs: &Substs<'tcx>,
-                                          generic_bounds: &ty::GenericBounds<'tcx>) {
-        assert!(!generic_bounds.has_escaping_regions());
-        assert!(!substs.has_regions_escaping_depth(0));
-
-        let obligations =
-            traits::obligations_for_generics(self.tcx(),
-                                             cause,
-                                             generic_bounds,
-                                             &substs.types);
-        obligations.map_move(|o| self.register_obligation(o));
-    }
-
-    fn add_region_obligations_for_generics(&self,
-                                           cause: traits::ObligationCause<'tcx>,
-                                           substs: &Substs<'tcx>,
-                                           generic_bounds: &ty::GenericBounds<'tcx>)
-    {
-        assert!(!generic_bounds.has_escaping_regions());
-        assert_eq!(generic_bounds.types.iter().len(), substs.types.iter().len());
-
-        for (type_bounds, &type_param) in
-            generic_bounds.types.iter().zip(
-                substs.types.iter())
-        {
-            self.add_region_obligations_for_type_parameter(
-                cause.span, type_bounds, type_param);
-        }
-
-        assert_eq!(generic_bounds.regions.iter().len(),
-                   substs.regions().iter().len());
-        for (region_bounds, &region_param) in
-            generic_bounds.regions.iter().zip(
-                substs.regions().iter())
-        {
-            self.add_region_obligations_for_region_parameter(
-                cause.span, region_bounds.as_slice(), region_param);
-        }
-    }
-
-    fn add_region_obligations_for_type_parameter(&self,
-                                                 span: Span,
-                                                 param_bound: &ty::ParamBounds<'tcx>,
-                                                 ty: Ty<'tcx>)
-    {
-        // For each declared region bound `T:r`, `T` must outlive `r`.
-        let region_bounds =
-            ty::required_region_bounds(
-                self.tcx(),
-                param_bound.region_bounds.as_slice(),
-                param_bound.builtin_bounds,
-                param_bound.trait_bounds.as_slice());
-        for &r in region_bounds.iter() {
-            let cause = traits::ObligationCause::new(span, self.body_id, traits::MiscObligation);
-            self.register_region_obligation(ty, r, cause);
-        }
-    }
-
-    fn add_region_obligations_for_region_parameter(&self,
-                                                   span: Span,
-                                                   region_bounds: &[ty::Region],
-                                                   region_param: ty::Region)
-    {
-        for &b in region_bounds.iter() {
-            // For each bound `region:b`, `b <= region` must hold
-            // (i.e., `region` must outlive `b`).
-            let origin = infer::RelateRegionParamBound(span);
-            self.mk_subr(origin, b, region_param);
-        }
+        obligations.map_move(|o| self.register_predicate(o));
     }
 }
 
@@ -4029,6 +3962,9 @@ fn check_expr_with_unifier<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
         let typ = lookup_method_for_for_loop(fcx, &**head, expr.id);
         vtable::select_new_fcx_obligations(fcx);
 
+        debug!("ExprForLoop each item has type {}",
+               fcx.infcx().resolve_type_vars_if_possible(typ).repr(fcx.tcx()));
+
         let pcx = pat_ctxt {
             fcx: fcx,
             map: pat_id_map(&tcx.def_map, &**pat),
@@ -5162,7 +5098,6 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 
     fcx.add_obligations_for_parameters(
         traits::ObligationCause::new(span, fcx.body_id, traits::ItemObligation(def.def_id())),
-        &substs,
         &bounds);
 
     // Substitute the values for the type parameters into the type of
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 328c1eafae5..cadcee43b44 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -932,14 +932,9 @@ fn check_expr_fn_block(rcx: &mut Rcx,
 
             // Check that the type meets the criteria of the existential bounds:
             for builtin_bound in bounds.builtin_bounds.iter() {
-                let code = traits::ClosureCapture(var_node_id, expr.span);
+                let code = traits::ClosureCapture(var_node_id, expr.span, builtin_bound);
                 let cause = traits::ObligationCause::new(freevar.span, rcx.fcx.body_id, code);
-                let obligation = traits::obligation_for_builtin_bound(rcx.tcx(), cause,
-                                                                      var_ty, builtin_bound);
-                if let Ok(obligation) = obligation {
-                    rcx.fcx.inh.fulfillment_cx.borrow_mut().register_obligation(rcx.tcx(),
-                                                                                obligation)
-                }
+                rcx.fcx.register_builtin_bound(var_ty, builtin_bound, cause);
             }
             type_must_outlive(
                 rcx, infer::RelateProcBound(expr.span, var_node_id, var_ty),
@@ -1859,20 +1854,14 @@ fn param_must_outlive<'a, 'tcx>(rcx: &Rcx<'a, 'tcx>,
            region.repr(rcx.tcx()),
            param_ty.repr(rcx.tcx()));
 
-    // Collect all regions that `param_ty` is known to outlive into
-    // this vector:
-    let mut param_bounds;
-
     // To start, collect bounds from user:
-    let param_bound = param_env.bounds.get(param_ty.space, param_ty.idx);
-    param_bounds =
+    let mut param_bounds =
         ty::required_region_bounds(rcx.tcx(),
-                                   param_bound.region_bounds.as_slice(),
-                                   param_bound.builtin_bounds,
-                                   param_bound.trait_bounds.as_slice());
+                                   param_ty.to_ty(rcx.tcx()),
+                                   param_env.caller_bounds.predicates.as_slice().to_vec());
 
-    // Collect default bound of fn body that applies to all in scope
-    // type parameters:
+    // Add in the default bound of fn body that applies to all in
+    // scope type parameters:
     param_bounds.push(param_env.implicit_region_bound);
 
     // Finally, collect regions we scraped from the well-formedness
diff --git a/src/librustc_typeck/check/regionmanip.rs b/src/librustc_typeck/check/regionmanip.rs
index 92dfd8b5f56..112ad1fb5b9 100644
--- a/src/librustc_typeck/check/regionmanip.rs
+++ b/src/librustc_typeck/check/regionmanip.rs
@@ -97,7 +97,9 @@ impl<'a, 'tcx> Wf<'a, 'tcx> {
             }
 
             ty::ty_trait(ref t) => {
-                self.accumulate_from_object_ty(ty, &t.bounds)
+                let required_region_bounds =
+                    ty::object_region_bounds(self.tcx, Some(&t.principal), t.bounds.builtin_bounds);
+                self.accumulate_from_object_ty(ty, t.bounds.region_bound, required_region_bounds)
             }
 
             ty::ty_enum(def_id, ref substs) |
@@ -321,12 +323,15 @@ impl<'a, 'tcx> Wf<'a, 'tcx> {
             ty::UniqTraitStore => { }
         }
 
-        self.accumulate_from_object_ty(ty, &c.bounds)
+        let required_region_bounds =
+            ty::object_region_bounds(self.tcx, None, c.bounds.builtin_bounds);
+        self.accumulate_from_object_ty(ty, c.bounds.region_bound, required_region_bounds);
     }
 
     fn accumulate_from_object_ty(&mut self,
                                  ty: Ty<'tcx>,
-                                 bounds: &ty::ExistentialBounds)
+                                 region_bound: ty::Region,
+                                 required_region_bounds: Vec<ty::Region>)
     {
         // Imagine a type like this:
         //
@@ -362,17 +367,12 @@ impl<'a, 'tcx> Wf<'a, 'tcx> {
 
         // The content of this object type must outlive
         // `bounds.region_bound`:
-        let r_c = bounds.region_bound;
+        let r_c = region_bound;
         self.push_region_constraint_from_top(r_c);
 
         // And then, in turn, to be well-formed, the
         // `region_bound` that user specified must imply the
         // region bounds required from all of the trait types:
-        let required_region_bounds =
-            ty::required_region_bounds(self.tcx,
-                                       &[],
-                                       bounds.builtin_bounds,
-                                       &[]);
         for &r_d in required_region_bounds.iter() {
             // Each of these is an instance of the `'c <= 'b`
             // constraint above
diff --git a/src/librustc_typeck/check/vtable.rs b/src/librustc_typeck/check/vtable.rs
index 17651b9bfb6..7c5ceb6f510 100644
--- a/src/librustc_typeck/check/vtable.rs
+++ b/src/librustc_typeck/check/vtable.rs
@@ -12,15 +12,14 @@ use check::{FnCtxt, structurally_resolved_type};
 use middle::subst::{SelfSpace, FnSpace};
 use middle::traits;
 use middle::traits::{SelectionError, OutputTypeParameterMismatch, Overflow, Unimplemented};
-use middle::traits::{Obligation, ObligationCause, obligation_for_builtin_bound};
+use middle::traits::{Obligation, ObligationCause};
 use middle::traits::{FulfillmentError, CodeSelectionError, CodeAmbiguity};
-use middle::traits::{TraitObligation};
+use middle::traits::{PredicateObligation};
 use middle::ty::{mod, Ty};
 use middle::infer;
 use std::rc::Rc;
 use syntax::ast;
 use syntax::codemap::Span;
-use util::common::ErrorReported;
 use util::ppaux::{UserString, Repr, ty_to_string};
 
 pub fn check_object_cast<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
@@ -249,18 +248,10 @@ pub fn register_object_cast_obligations<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                                                   -> Rc<ty::TraitRef<'tcx>>
 {
     // We can only make objects from sized types.
-    let sized_obligation =
-        traits::obligation_for_builtin_bound(
-            fcx.tcx(),
-            traits::ObligationCause::new(span, fcx.body_id, traits::ObjectSized),
-            referent_ty,
-            ty::BoundSized);
-    match sized_obligation {
-        Ok(sized_obligation) => {
-            fcx.register_obligation(sized_obligation);
-        }
-        Err(ErrorReported) => { }
-    }
+    fcx.register_builtin_bound(
+        referent_ty,
+        ty::BoundSized,
+        traits::ObligationCause::new(span, fcx.body_id, traits::ObjectSized));
 
     // This is just for better error reporting. Kinda goofy. The object type stuff
     // needs some refactoring so there is a more convenient type to pass around.
@@ -289,24 +280,18 @@ pub fn register_object_cast_obligations<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
             ObligationCause::new(span,
                                  fcx.body_id,
                                  traits::ObjectCastObligation(object_trait_ty)),
-            object_trait_ref.clone());
-    fcx.register_obligation(object_obligation);
+            ty::Predicate::Trait(object_trait_ref.clone()));
+    fcx.register_predicate(object_obligation);
 
     // Create additional obligations for all the various builtin
     // bounds attached to the object cast. (In other words, if the
     // object type is Foo+Send, this would create an obligation
     // for the Send check.)
     for builtin_bound in object_trait.bounds.builtin_bounds.iter() {
-            let obligation = obligation_for_builtin_bound(
-                fcx.tcx(),
-                ObligationCause::new(span,
-                                     fcx.body_id,
-                                     traits::ObjectCastObligation(object_trait_ty)),
-                referent_ty,
-                builtin_bound);
-        if let Ok(obligation) = obligation {
-            fcx.register_obligation(obligation);
-        }
+        fcx.register_builtin_bound(
+            referent_ty,
+            builtin_bound,
+            ObligationCause::new(span, fcx.body_id, traits::ObjectCastObligation(object_trait_ty)));
     }
 
     object_trait_ref
@@ -325,17 +310,6 @@ pub fn select_all_fcx_obligations_or_error(fcx: &FnCtxt) {
     }
 }
 
-fn resolve_trait_ref<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>, obligation: &TraitObligation<'tcx>)
-                               -> (Rc<ty::TraitRef<'tcx>>, Ty<'tcx>)
-{
-    let trait_ref =
-        fcx.infcx().resolve_type_vars_in_trait_ref_if_possible(
-            &*obligation.trait_ref);
-    let self_ty =
-        trait_ref.substs.self_ty().unwrap();
-    (Rc::new(trait_ref), self_ty)
-}
-
 pub fn report_fulfillment_errors<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                                            errors: &Vec<FulfillmentError<'tcx>>) {
     for error in errors.iter() {
@@ -356,18 +330,42 @@ pub fn report_fulfillment_error<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 }
 
 pub fn report_selection_error<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
-                                        obligation: &TraitObligation<'tcx>,
+                                        obligation: &PredicateObligation<'tcx>,
                                         error: &SelectionError<'tcx>)
 {
     match *error {
         Overflow => {
-            let (trait_ref, self_ty) = resolve_trait_ref(fcx, obligation);
-            fcx.tcx().sess.span_err(
-                obligation.cause.span,
-                format!(
-                    "overflow evaluating the trait `{}` for the type `{}`",
-                    trait_ref.user_string(fcx.tcx()),
-                    self_ty.user_string(fcx.tcx())).as_slice());
+            // We could track the stack here more precisely if we wanted, I imagine.
+            match obligation.trait_ref {
+                ty::Predicate::Trait(ref trait_ref) => {
+                    let trait_ref =
+                        fcx.infcx().resolve_type_vars_in_trait_ref_if_possible(&**trait_ref);
+                    fcx.tcx().sess.span_err(
+                        obligation.cause.span,
+                        format!(
+                            "overflow evaluating the trait `{}` for the type `{}`",
+                            trait_ref.user_string(fcx.tcx()),
+                            trait_ref.self_ty().user_string(fcx.tcx())).as_slice());
+                }
+
+                ty::Predicate::Equate(a, b) => {
+                    let a = fcx.infcx().resolve_type_vars_if_possible(a);
+                    let b = fcx.infcx().resolve_type_vars_if_possible(b);
+                    fcx.tcx().sess.span_err(
+                        obligation.cause.span,
+                        format!(
+                            "overflow checking whether the types `{}` and `{}` are equal",
+                            a.user_string(fcx.tcx()),
+                            b.user_string(fcx.tcx())).as_slice());
+                }
+
+                ty::Predicate::TypeOutlives(..) |
+                ty::Predicate::RegionOutlives(..) => {
+                    fcx.tcx().sess.span_err(
+                        obligation.cause.span,
+                        format!("overflow evaluating lifetime predicate").as_slice());
+                }
+            }
 
             let current_limit = fcx.tcx().sess.recursion_limit.get();
             let suggested_limit = current_limit * 2;
@@ -380,31 +378,63 @@ pub fn report_selection_error<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
             note_obligation_cause(fcx, obligation);
         }
         Unimplemented => {
-            let (trait_ref, self_ty) = resolve_trait_ref(fcx, obligation);
-            if !ty::type_is_error(self_ty) {
-                fcx.tcx().sess.span_err(
-                    obligation.cause.span,
-                    format!(
-                        "the trait `{}` is not implemented for the type `{}`",
-                        trait_ref.user_string(fcx.tcx()),
-                        self_ty.user_string(fcx.tcx())).as_slice());
-                note_obligation_cause(fcx, obligation);
+            match obligation.trait_ref {
+                ty::Predicate::Trait(ref trait_ref) => {
+                    let trait_ref =
+                        fcx.infcx().resolve_type_vars_in_trait_ref_if_possible(
+                            &**trait_ref);
+                    if !ty::type_is_error(trait_ref.self_ty()) {
+                        fcx.tcx().sess.span_err(
+                            obligation.cause.span,
+                            format!(
+                                "the trait `{}` is not implemented for the type `{}`",
+                                trait_ref.user_string(fcx.tcx()),
+                                trait_ref.self_ty().user_string(fcx.tcx())).as_slice());
+                        note_obligation_cause(fcx, obligation);
+                    }
+                }
+
+                ty::Predicate::Equate(a, b) => {
+                    let a = fcx.infcx().resolve_type_vars_if_possible(a);
+                    let b = fcx.infcx().resolve_type_vars_if_possible(b);
+                    let err = infer::can_mk_eqty(fcx.infcx(), a, b).unwrap_err();
+                    fcx.tcx().sess.span_err(
+                        obligation.cause.span,
+                        format!(
+                            "mismatched types: the types `{}` and `{}` are not equal ({})",
+                            a.user_string(fcx.tcx()),
+                            b.user_string(fcx.tcx()),
+                            ty::type_err_to_str(fcx.tcx(), &err)).as_slice());
+                }
+
+                ty::Predicate::TypeOutlives(..) |
+                ty::Predicate::RegionOutlives(..) => {
+                    // these kinds of predicates turn into
+                    // constraints, and hence errors show up in region
+                    // inference.
+                    fcx.tcx().sess.span_bug(
+                        obligation.cause.span,
+                        format!("region predicate error {}",
+                                obligation.repr(fcx.tcx())).as_slice());
+                }
             }
         }
-        OutputTypeParameterMismatch(ref expected_trait_ref, ref e) => {
+        OutputTypeParameterMismatch(ref expected_trait_ref, ref actual_trait_ref, ref e) => {
             let expected_trait_ref =
                 fcx.infcx().resolve_type_vars_in_trait_ref_if_possible(
                     &**expected_trait_ref);
-            let (trait_ref, self_ty) = resolve_trait_ref(fcx, obligation);
-            if !ty::type_is_error(self_ty) {
+            let actual_trait_ref =
+                fcx.infcx().resolve_type_vars_in_trait_ref_if_possible(
+                    &**actual_trait_ref);
+            if !ty::type_is_error(actual_trait_ref.self_ty()) {
                 fcx.tcx().sess.span_err(
                     obligation.cause.span,
                     format!(
                         "type mismatch: the type `{}` implements the trait `{}`, \
                          but the trait `{}` is required ({})",
-                        self_ty.user_string(fcx.tcx()),
+                        expected_trait_ref.self_ty().user_string(fcx.tcx()),
                         expected_trait_ref.user_string(fcx.tcx()),
-                        trait_ref.user_string(fcx.tcx()),
+                        actual_trait_ref.user_string(fcx.tcx()),
                         ty::type_err_to_str(fcx.tcx(), e)).as_slice());
                 note_obligation_cause(fcx, obligation);
             }
@@ -413,12 +443,25 @@ pub fn report_selection_error<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 }
 
 pub fn maybe_report_ambiguity<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
-                                        obligation: &TraitObligation<'tcx>) {
+                                        obligation: &PredicateObligation<'tcx>) {
     // Unable to successfully determine, probably means
     // insufficient type information, but could mean
     // ambiguous impls. The latter *ought* to be a
     // coherence violation, so we don't report it here.
-    let (trait_ref, self_ty) = resolve_trait_ref(fcx, obligation);
+
+    let trait_ref = match obligation.trait_ref {
+        ty::Predicate::Trait(ref trait_ref) => {
+            fcx.infcx().resolve_type_vars_in_trait_ref_if_possible(&**trait_ref)
+        }
+        _ => {
+            fcx.tcx().sess.span_bug(
+                obligation.cause.span,
+                format!("ambiguity from something other than a trait: {}",
+                        obligation.trait_ref.repr(fcx.tcx())).as_slice());
+        }
+    };
+    let self_ty = trait_ref.self_ty();
+
     debug!("maybe_report_ambiguity(trait_ref={}, self_ty={}, obligation={})",
            trait_ref.repr(fcx.tcx()),
            self_ty.repr(fcx.tcx()),
@@ -475,8 +518,8 @@ pub fn maybe_report_ambiguity<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 }
 
 /// Select as many obligations as we can at present.
-pub fn select_fcx_obligations_where_possible(fcx: &FnCtxt) {
-
+pub fn select_fcx_obligations_where_possible(fcx: &FnCtxt)
+{
     match
         fcx.inh.fulfillment_cx
         .borrow_mut()
@@ -502,9 +545,8 @@ pub fn select_new_fcx_obligations(fcx: &FnCtxt) {
 }
 
 fn note_obligation_cause<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
-                                   obligation: &TraitObligation<'tcx>) {
+                                   obligation: &PredicateObligation<'tcx>) {
     let tcx = fcx.tcx();
-    let trait_name = ty::item_path_str(tcx, obligation.trait_ref.def_id);
     match obligation.cause.code {
         traits::MiscObligation => { }
         traits::ItemObligation(item_def_id) => {
@@ -512,17 +554,14 @@ fn note_obligation_cause<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
             tcx.sess.span_note(
                 obligation.cause.span,
                 format!(
-                    "the trait `{}` must be implemented because it is required by `{}`",
-                    trait_name,
+                    "required by `{}`",
                     item_name).as_slice());
         }
         traits::ObjectCastObligation(object_ty) => {
             tcx.sess.span_note(
                 obligation.cause.span,
                 format!(
-                    "the trait `{}` must be implemented for the cast \
-                     to the object type `{}`",
-                    trait_name,
+                    "required for the cast to the object type `{}`",
                     fcx.infcx().ty_to_string(object_ty)).as_slice());
         }
         traits::RepeatVec => {
@@ -560,7 +599,9 @@ fn note_obligation_cause<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                        "use \"#[unsafe_destructor]\" on the implementation \
                        to force the compiler to allow this");
         }
-        traits::ClosureCapture(var_id, closure_span) => {
+        traits::ClosureCapture(var_id, closure_span, builtin_bound) => {
+            let def_id = tcx.lang_items.from_builtin_kind(builtin_bound).unwrap();
+            let trait_name = ty::item_path_str(tcx, def_id);
             let name = ty::local_var_name_str(tcx, var_id);
             span_note!(tcx.sess, closure_span,
                        "the closure that captures `{}` requires that all captured variables \"
diff --git a/src/librustc_typeck/check/wf.rs b/src/librustc_typeck/check/wf.rs
index 23db98b3175..e89b127799c 100644
--- a/src/librustc_typeck/check/wf.rs
+++ b/src/librustc_typeck/check/wf.rs
@@ -122,16 +122,12 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
                 // For DST, all intermediate types must be sized.
                 if variant.fields.len() > 0 {
                     for field in variant.fields.init().iter() {
-                        let cause = traits::ObligationCause::new(field.span,
-                                                                 fcx.body_id,
-                                                                 traits::FieldSized);
-                        let obligation = traits::obligation_for_builtin_bound(fcx.tcx(),
-                                                                              cause,
-                                                                              field.ty,
-                                                                              ty::BoundSized);
-                        if let Ok(obligation) = obligation {
-                            fcx.register_obligation(obligation);
-                        }
+                        fcx.register_builtin_bound(
+                            field.ty,
+                            ty::BoundSized,
+                            traits::ObligationCause::new(field.span,
+                                                         fcx.body_id,
+                                                         traits::FieldSized));
                     }
                 }
             }
@@ -220,8 +216,6 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
             // the same way as we treat the self-type.
             bounds_checker.check_trait_ref(&trait_ref);
 
-            let trait_def = ty::lookup_trait_def(fcx.tcx(), trait_ref.def_id);
-
             let cause =
                 traits::ObligationCause::new(
                     item.span,
@@ -229,25 +223,9 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
                     traits::ItemObligation(trait_ref.def_id));
 
             // Find the supertrait bounds. This will add `int:Bar`.
-            //
-            // FIXME -- This is a bit ill-factored. There is very similar
-            // code in traits::util::obligations_for_generics.
-            fcx.add_region_obligations_for_type_parameter(item.span,
-                                                          &trait_def.bounds,
-                                                          trait_ref.self_ty());
-            for builtin_bound in trait_def.bounds.builtin_bounds.iter() {
-                let obligation = traits::obligation_for_builtin_bound(fcx.tcx(),
-                                                                      cause,
-                                                                      trait_ref.self_ty(),
-                                                                      builtin_bound);
-                if let Ok(obligation) = obligation {
-                    fcx.register_obligation(obligation);
-                }
-            }
-            for trait_bound in trait_def.bounds.trait_bounds.iter() {
-                let trait_bound = trait_bound.subst(fcx.tcx(), &trait_ref.substs);
-                fcx.register_obligation(
-                    traits::Obligation::new(cause, trait_bound));
+            let predicates = ty::predicates_for_trait_ref(fcx.tcx(), &trait_ref);
+            for predicate in predicates.into_iter() {
+                fcx.register_predicate(traits::Obligation::new(cause, predicate));
             }
         });
     }
@@ -296,7 +274,6 @@ impl<'cx,'tcx> BoundsChecker<'cx,'tcx> {
                 self.span,
                 self.fcx.body_id,
                 traits::ItemObligation(trait_ref.def_id)),
-            &trait_ref.substs,
             &bounds);
 
         for &ty in trait_ref.substs.types.iter() {
@@ -347,7 +324,6 @@ impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
                         traits::ObligationCause::new(self.span,
                                                      self.fcx.body_id,
                                                      traits::ItemObligation(type_id)),
-                        substs,
                         &polytype.generics.to_bounds(self.tcx(), substs));
                 } else {
                     // There are two circumstances in which we ignore
@@ -372,12 +348,13 @@ impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
                     //
                     // (I believe we should do the same for traits, but
                     // that will require an RFC. -nmatsakis)
-                    self.fcx.add_trait_obligations_for_generics(
+                    let bounds = polytype.generics.to_bounds(self.tcx(), substs);
+                    let bounds = filter_to_trait_obligations(bounds);
+                    self.fcx.add_obligations_for_parameters(
                         traits::ObligationCause::new(self.span,
                                                      self.fcx.body_id,
                                                      traits::ItemObligation(type_id)),
-                        substs,
-                        &polytype.generics.to_bounds(self.tcx(), substs));
+                        &bounds);
                 }
 
                 self.fold_substs(substs);
@@ -464,6 +441,24 @@ fn enum_variants<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
         .collect()
 }
 
+fn filter_to_trait_obligations<'tcx>(bounds: ty::GenericBounds<'tcx>)
+                                     -> ty::GenericBounds<'tcx>
+{
+    let mut result = ty::GenericBounds::empty();
+    for (space, _, predicate) in bounds.predicates.iter_enumerated() {
+        match *predicate {
+            ty::Predicate::Trait(..) => {
+                result.predicates.push(space, predicate.clone())
+            }
+            ty::Predicate::Equate(..) |
+            ty::Predicate::TypeOutlives(..) |
+            ty::Predicate::RegionOutlives(..) => {
+            }
+        }
+    }
+    result
+}
+
 ///////////////////////////////////////////////////////////////////////////
 // Special drop trait checking
 
@@ -476,13 +471,7 @@ fn check_struct_safe_for_destructor<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
         && !struct_tpt.generics.has_region_params(subst::TypeSpace)
     {
         let cause = traits::ObligationCause::new(span, fcx.body_id, traits::DropTrait);
-        let obligation = traits::obligation_for_builtin_bound(fcx.tcx(),
-                                                              cause,
-                                                              self_ty,
-                                                              ty::BoundSend);
-        if let Ok(obligation) = obligation {
-            fcx.register_obligation(obligation);
-        }
+        fcx.register_builtin_bound(self_ty, ty::BoundSend, cause);
     } else {
         span_err!(fcx.tcx().sess, span, E0141,
                   "cannot implement a destructor on a structure \
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 9cfb56fbf8c..09cf7080476 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -42,7 +42,6 @@ use middle::region;
 use middle::resolve_lifetime;
 use middle::subst;
 use middle::subst::{Substs};
-use middle::traits;
 use middle::ty::{ImplContainer, ImplOrTraitItemContainer, TraitContainer};
 use middle::ty::{Polytype};
 use middle::ty::{mod, Ty};
@@ -50,7 +49,6 @@ use middle::ty_fold::TypeFolder;
 use middle::infer;
 use rscope::*;
 use {CrateCtxt, lookup_def_tcx, no_params, write_ty_to_tcx};
-use util::common::ErrorReported;
 use util::nodemap::{FnvHashMap, FnvHashSet};
 use util::ppaux;
 use util::ppaux::{Repr,UserString};
@@ -1409,14 +1407,15 @@ pub fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                     .collect();
 
         // ...and also create generics synthesized from the associated types.
+        let mut index = 0;
         let assoc_types: Vec<_> =
             items.iter()
             .flat_map(|item| match *item {
                 ast::TypeTraitItem(ref trait_item) => {
-                    let index = types.len();
+                    index += 1;
                     Some(ty::mk_param(ccx.tcx,
                                       subst::AssocSpace,
-                                      index,
+                                      index - 1,
                                       local_def(trait_item.ty_param.id))).into_iter()
                 }
                 ast::RequiredMethod(_) | ast::ProvidedMethod(_) => {
@@ -1598,7 +1597,8 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                    substs: &subst::Substs<'tcx>,
                                    ast_generics: &ast::Generics,
                                    items: &[ast::TraitItem])
-                                   -> ty::Generics<'tcx> {
+                                   -> ty::Generics<'tcx>
+{
     let mut generics =
         ty_generics(ccx,
                     subst::TypeSpace,
@@ -1646,7 +1646,7 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         bounds: ty::ParamBounds {
             region_bounds: vec!(),
             builtin_bounds: ty::empty_builtin_bounds(),
-            trait_bounds: vec!(self_trait_ref),
+            trait_bounds: vec!(self_trait_ref.clone()),
         },
         associated_with: None,
         default: None
@@ -1656,6 +1656,9 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 
     generics.types.push(subst::SelfSpace, def);
 
+    generics.predicates.push(subst::SelfSpace,
+                             ty::Predicate::Trait(self_trait_ref));
+
     generics
 }
 
@@ -1904,24 +1907,18 @@ fn ty_generics<'tcx,AC>(this: &AC,
         result: &mut ty::Generics<'tcx>,
         space: subst::ParamSpace)
     {
-        for (index, type_param_def) in result.types.get_slice(space).iter().enumerate() {
-            let param_ty = ty::mk_param(tcx, space, index, type_param_def.def_id);
-
-            for builtin_bound in type_param_def.bounds.builtin_bounds.iter() {
-                match traits::trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty) {
-                    Ok(trait_ref) => {
-                        result.predicates.push(space, ty::Predicate::Trait(trait_ref));
-                    }
-                    Err(ErrorReported) => { }
-                }
-            }
-
-            for &region_bound in type_param_def.bounds.region_bounds.iter() {
-                result.predicates.push(space, ty::Predicate::TypeOutlives(param_ty, region_bound));
+        for type_param_def in result.types.get_slice(space).iter() {
+            let param_ty = ty::mk_param_from_def(tcx, type_param_def);
+            for predicate in ty::predicates(tcx, param_ty, &type_param_def.bounds).into_iter() {
+                result.predicates.push(space, predicate);
             }
+        }
 
-            for bound_trait_ref in type_param_def.bounds.trait_bounds.iter() {
-                result.predicates.push(space, ty::Predicate::Trait((*bound_trait_ref).clone()));
+        for region_param_def in result.regions.get_slice(space).iter() {
+            let region = region_param_def.to_early_bound_region();
+            for &bound_region in region_param_def.bounds.iter() {
+                result.predicates.push(space, ty::Predicate::RegionOutlives(region,
+                                                                            bound_region));
             }
         }
     }
@@ -2178,8 +2175,7 @@ pub fn mk_item_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 
     let regions =
         ty_generics.regions.map(
-            |def| ty::ReEarlyBound(def.def_id.node, def.space,
-                                   def.index, def.name));
+            |def| def.to_early_bound_region());
 
     subst::Substs::new(types, regions)
 }
diff --git a/src/test/compile-fail/builtin-superkinds-self-type.rs b/src/test/compile-fail/builtin-superkinds-self-type.rs
index 86d3d7e9cbc..4c7ff60fbdd 100644
--- a/src/test/compile-fail/builtin-superkinds-self-type.rs
+++ b/src/test/compile-fail/builtin-superkinds-self-type.rs
@@ -17,7 +17,6 @@ trait Foo : Sync+'static {
 
 impl <T: Sync> Foo for T { }
 //~^ ERROR the parameter type `T` may not live long enough
-//~^^ ERROR the parameter type `T` may not live long enough
 
 fn main() {
     let (tx, rx) = channel();
diff --git a/src/test/compile-fail/builtin-superkinds-simple.rs b/src/test/compile-fail/builtin-superkinds-simple.rs
index fda83c03a7d..2c689f6909b 100644
--- a/src/test/compile-fail/builtin-superkinds-simple.rs
+++ b/src/test/compile-fail/builtin-superkinds-simple.rs
@@ -14,6 +14,6 @@
 trait Foo : Send { }
 
 impl <'a> Foo for &'a mut () { }
-//~^ ERROR does not fulfill the required lifetime
+//~^ ERROR declared lifetime bound not satisfied
 
 fn main() { }
diff --git a/src/test/compile-fail/kindck-impl-type-params.rs b/src/test/compile-fail/kindck-impl-type-params.rs
index a430fe72333..57ee4cf7cc3 100644
--- a/src/test/compile-fail/kindck-impl-type-params.rs
+++ b/src/test/compile-fail/kindck-impl-type-params.rs
@@ -34,6 +34,7 @@ fn g<T>(val: T) {
 fn foo<'a>() {
     let t: S<&'a int> = S;
     let a = &t as &Gettable<&'a int>;
+    //~^ ERROR declared lifetime bound not satisfied
 }
 
 fn foo2<'a>() {
diff --git a/src/test/compile-fail/kindck-send-object1.rs b/src/test/compile-fail/kindck-send-object1.rs
index a5519753643..35e928d417c 100644
--- a/src/test/compile-fail/kindck-send-object1.rs
+++ b/src/test/compile-fail/kindck-send-object1.rs
@@ -22,7 +22,7 @@ fn test51<'a>() {
 }
 fn test52<'a>() {
     assert_send::<&'a (Dummy+Send)>();
-    //~^ ERROR does not fulfill the required lifetime
+    //~^ ERROR declared lifetime bound not satisfied
 }
 
 // ...unless they are properly bounded
diff --git a/src/test/compile-fail/kindck-send-owned.rs b/src/test/compile-fail/kindck-send-owned.rs
index 0eed05692b9..11148d2846c 100644
--- a/src/test/compile-fail/kindck-send-owned.rs
+++ b/src/test/compile-fail/kindck-send-owned.rs
@@ -19,7 +19,7 @@ fn test32() { assert_send::<Vec<int> >(); }
 
 // but not if they own a bad thing
 fn test40<'a>(_: &'a int) {
-    assert_send::<Box<&'a int>>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<Box<&'a int>>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/kindck-send-region-pointers.rs b/src/test/compile-fail/kindck-send-region-pointers.rs
index cc46d7f4de9..04172932cfe 100644
--- a/src/test/compile-fail/kindck-send-region-pointers.rs
+++ b/src/test/compile-fail/kindck-send-region-pointers.rs
@@ -22,13 +22,13 @@ fn test10() { assert_send::<&'static mut int>(); }
 
 // otherwise lifetime pointers are not ok
 fn test20<'a>(_: &'a int) {
-    assert_send::<&'a int>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<&'a int>(); //~ ERROR declared lifetime bound not satisfied
 }
 fn test21<'a>(_: &'a int) {
-    assert_send::<&'a str>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<&'a str>(); //~ ERROR declared lifetime bound not satisfied
 }
 fn test22<'a>(_: &'a int) {
-    assert_send::<&'a [int]>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<&'a [int]>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/kindck-send-unsafe.rs b/src/test/compile-fail/kindck-send-unsafe.rs
index a9bbfcfa262..33314149d1f 100644
--- a/src/test/compile-fail/kindck-send-unsafe.rs
+++ b/src/test/compile-fail/kindck-send-unsafe.rs
@@ -15,7 +15,7 @@ fn test70() {
     assert_send::<*mut int>();
 }
 fn test71<'a>() {
-    assert_send::<*mut &'a int>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<*mut &'a int>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn main() {
diff --git a/src/test/compile-fail/recursion_limit.rs b/src/test/compile-fail/recursion_limit.rs
index 17afb168a98..1da7f47677a 100644
--- a/src/test/compile-fail/recursion_limit.rs
+++ b/src/test/compile-fail/recursion_limit.rs
@@ -44,8 +44,8 @@ fn main() {
     is_send::<A>();
     //~^ ERROR overflow evaluating
     //~^^ NOTE consider adding a `#![recursion_limit="20"]` attribute to your crate
-    //~^^^ NOTE must be implemented
+    //~^^^ NOTE required by `is_send`
     //~^^^^ ERROR overflow evaluating
     //~^^^^^ NOTE consider adding a `#![recursion_limit="20"]` attribute to your crate
-    //~^^^^^^ NOTE must be implemented
+    //~^^^^^^ NOTE required by `is_send`
 }
diff --git a/src/test/compile-fail/region-object-lifetime-in-coercion.rs b/src/test/compile-fail/region-object-lifetime-in-coercion.rs
index dfeba041092..b2b2d3337c4 100644
--- a/src/test/compile-fail/region-object-lifetime-in-coercion.rs
+++ b/src/test/compile-fail/region-object-lifetime-in-coercion.rs
@@ -15,12 +15,12 @@ trait Foo {}
 impl<'a> Foo for &'a [u8] {}
 
 fn a(v: &[u8]) -> Box<Foo + 'static> {
-    let x: Box<Foo + 'static> = box v; //~ ERROR does not outlive
+    let x: Box<Foo + 'static> = box v; //~ ERROR declared lifetime bound not satisfied
     x
 }
 
 fn b(v: &[u8]) -> Box<Foo + 'static> {
-    box v //~ ERROR does not outlive
+    box v //~ ERROR declared lifetime bound not satisfied
 }
 
 fn c(v: &[u8]) -> Box<Foo> {
@@ -28,7 +28,7 @@ fn c(v: &[u8]) -> Box<Foo> {
 }
 
 fn d<'a,'b>(v: &'a [u8]) -> Box<Foo+'b> {
-    box v //~ ERROR does not outlive
+    box v //~ ERROR declared lifetime bound not satisfied
 }
 
 fn e<'a:'b,'b>(v: &'a [u8]) -> Box<Foo+'b> {
diff --git a/src/test/compile-fail/regions-bounded-by-send.rs b/src/test/compile-fail/regions-bounded-by-send.rs
index 660a9be4f63..ec679a7dda1 100644
--- a/src/test/compile-fail/regions-bounded-by-send.rs
+++ b/src/test/compile-fail/regions-bounded-by-send.rs
@@ -29,15 +29,15 @@ fn static_lifime_ok<'a,T,U:Send>(_: &'a int) {
 // otherwise lifetime pointers are not ok
 
 fn param_not_ok<'a>(x: &'a int) {
-    assert_send::<&'a int>(); //~ ERROR does not fulfill
+    assert_send::<&'a int>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn param_not_ok1<'a>(_: &'a int) {
-    assert_send::<&'a str>(); //~ ERROR does not fulfill
+    assert_send::<&'a str>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn param_not_ok2<'a>(_: &'a int) {
-    assert_send::<&'a [int]>(); //~ ERROR does not fulfill
+    assert_send::<&'a [int]>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 // boxes are ok
@@ -51,7 +51,7 @@ fn box_ok() {
 // but not if they own a bad thing
 
 fn box_with_region_not_ok<'a>() {
-    assert_send::<Box<&'a int>>(); //~ ERROR does not fulfill
+    assert_send::<Box<&'a int>>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 // objects with insufficient bounds no ok
@@ -63,7 +63,7 @@ fn object_with_random_bound_not_ok<'a>() {
 
 fn object_with_send_bound_not_ok<'a>() {
     assert_send::<&'a (Dummy+Send)>();
-    //~^ ERROR does not fulfill
+    //~^ ERROR declared lifetime bound not satisfied
 }
 
 fn proc_with_lifetime_not_ok<'a>() {
@@ -84,11 +84,11 @@ fn unsafe_ok1<'a>(_: &'a int) {
 }
 
 fn unsafe_ok2<'a>(_: &'a int) {
-    assert_send::<*const &'a int>(); //~ ERROR does not fulfill
+    assert_send::<*const &'a int>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn unsafe_ok3<'a>(_: &'a int) {
-    assert_send::<*mut &'a int>(); //~ ERROR does not fulfill
+    assert_send::<*mut &'a int>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn main() {
diff --git a/src/test/compile-fail/regions-bounded-by-trait-requiring-static.rs b/src/test/compile-fail/regions-bounded-by-trait-requiring-static.rs
index 04a94b75215..e3939a4e390 100644
--- a/src/test/compile-fail/regions-bounded-by-trait-requiring-static.rs
+++ b/src/test/compile-fail/regions-bounded-by-trait-requiring-static.rs
@@ -29,15 +29,15 @@ fn static_lifime_ok<'a,T,U:Send>(_: &'a int) {
 // otherwise lifetime pointers are not ok
 
 fn param_not_ok<'a>(x: &'a int) {
-    assert_send::<&'a int>(); //~ ERROR does not fulfill
+    assert_send::<&'a int>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn param_not_ok1<'a>(_: &'a int) {
-    assert_send::<&'a str>(); //~ ERROR does not fulfill
+    assert_send::<&'a str>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn param_not_ok2<'a>(_: &'a int) {
-    assert_send::<&'a [int]>(); //~ ERROR does not fulfill
+    assert_send::<&'a [int]>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 // boxes are ok
@@ -51,7 +51,7 @@ fn box_ok() {
 // but not if they own a bad thing
 
 fn box_with_region_not_ok<'a>() {
-    assert_send::<Box<&'a int>>(); //~ ERROR does not fulfill
+    assert_send::<Box<&'a int>>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 // unsafe pointers are ok unless they point at unsendable things
@@ -62,11 +62,11 @@ fn unsafe_ok1<'a>(_: &'a int) {
 }
 
 fn unsafe_ok2<'a>(_: &'a int) {
-    assert_send::<*const &'a int>(); //~ ERROR does not fulfill
+    assert_send::<*const &'a int>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn unsafe_ok3<'a>(_: &'a int) {
-    assert_send::<*mut &'a int>(); //~ ERROR does not fulfill
+    assert_send::<*mut &'a int>(); //~ ERROR declared lifetime bound not satisfied
 }
 
 fn main() {
diff --git a/src/test/compile-fail/regions-bounded-method-type-parameters.rs b/src/test/compile-fail/regions-bounded-method-type-parameters.rs
index 279139d8de9..10484925980 100644
--- a/src/test/compile-fail/regions-bounded-method-type-parameters.rs
+++ b/src/test/compile-fail/regions-bounded-method-type-parameters.rs
@@ -20,7 +20,7 @@ impl Foo {
 
 fn caller<'a>(x: &int) {
     Foo.some_method::<&'a int>();
-    //~^ ERROR does not fulfill the required lifetime
+    //~^ ERROR declared lifetime bound not satisfied
 }
 
 fn main() { }
diff --git a/src/test/compile-fail/regions-proc-bounds.rs b/src/test/compile-fail/regions-proc-bounds.rs
index db71bc4e15c..4c95e1eac6d 100644
--- a/src/test/compile-fail/regions-proc-bounds.rs
+++ b/src/test/compile-fail/regions-proc-bounds.rs
@@ -12,7 +12,7 @@ fn is_static<T: 'static>() {}
 
 fn foo<'a>() {
     is_static::<proc():'a>();
-    //~^ ERROR does not fulfill the required lifetime
+    //~^ ERROR declared lifetime bound not satisfied
 
     is_static::<proc():'static>();
 }