auto merge of #19683 : nikomatsakis/rust/generalized-where-clauses, r=nrc

This patch does not itself enable generalized where clauses, but it lays the groundwork. Rather than storing a list of bounds per type parameter, the trait selection and other logic is now driven by a unified list of predicates. All predicate handling is now driven through a common interface. This also fixes a number of bugs where region predicates were being dropped on the floor. As a drive-by, this patch also fixes some bugs in the opt-out-copy feature flag.

That said, this patch does not change the parser or AST in any way, so we still *generate* the list of predicates by walking a list of bounds (and we still *store* the bounds on the `TypeParameterDef` and so on). Those will get patched in a follow-up.

The commits in this case are standalone; the first few are simple refactorings.

r? @nick29581 
cc @aturon 

47 files changed, 1440 insertions, 1080 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/diagnostics.rs b/src/librustc/diagnostics.rs
index 0cdf6a68e44..fcac718b370 100644
--- a/src/librustc/diagnostics.rs
+++ b/src/librustc/diagnostics.rs
@@ -40,89 +40,8 @@ register_diagnostics!(
     E0019,
     E0020,
     E0022,
-    E0023,
-    E0024,
-    E0025,
-    E0026,
-    E0027,
-    E0029,
-    E0030,
-    E0031,
-    E0033,
-    E0034,
-    E0035,
-    E0036,
-    E0038,
-    E0040,
-    E0044,
-    E0045,
-    E0046,
-    E0049,
-    E0050,
-    E0051,
-    E0052,
-    E0053,
-    E0054,
-    E0055,
-    E0056,
-    E0057,
-    E0059,
-    E0060,
-    E0061,
-    E0062,
-    E0063,
-    E0066,
-    E0067,
-    E0068,
-    E0069,
-    E0070,
-    E0071,
-    E0072,
-    E0073,
-    E0074,
-    E0075,
-    E0076,
-    E0077,
-    E0079,
-    E0080,
-    E0081,
-    E0082,
-    E0083,
-    E0084,
-    E0085,
-    E0086,
-    E0087,
-    E0088,
-    E0089,
-    E0090,
-    E0091,
-    E0092,
-    E0093,
-    E0094,
-    E0100,
-    E0101,
-    E0102,
-    E0103,
-    E0104,
-    E0106,
-    E0107,
-    E0108,
     E0109,
     E0110,
-    E0116,
-    E0117,
-    E0118,
-    E0119,
-    E0120,
-    E0121,
-    E0122,
-    E0124,
-    E0127,
-    E0128,
-    E0129,
-    E0130,
-    E0131,
-    E0132,
     E0133,
     E0134,
     E0135,
@@ -131,16 +50,12 @@ register_diagnostics!(
     E0138,
     E0139,
     E0140,
-    E0141,
     E0152,
     E0153,
     E0157,
     E0158,
-    E0159,
     E0161,
     E0162,
-    E0163,
-    E0164,
     E0165,
     E0166,
     E0167,
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/csearch.rs b/src/librustc/metadata/csearch.rs
index b864dc39603..7ce9893afc8 100644
--- a/src/librustc/metadata/csearch.rs
+++ b/src/librustc/metadata/csearch.rs
@@ -21,7 +21,6 @@ use middle::def;
 use middle::lang_items;
 use middle::resolve;
 use middle::ty;
-use middle::subst::VecPerParamSpace;
 
 use rbml;
 use rbml::reader;
@@ -250,9 +249,8 @@ pub fn get_field_type<'tcx>(tcx: &ty::ctxt<'tcx>, class_id: ast::DefId,
         });
     let ty = decoder::item_type(def, the_field, tcx, &*cdata);
     ty::Polytype {
-        generics: ty::Generics {types: VecPerParamSpace::empty(),
-                                regions: VecPerParamSpace::empty()},
-        ty: ty
+        generics: ty::Generics::empty(),
+        ty: ty,
     }
 }
 
diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs
index 23bd37486bc..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,20 @@ fn doc_generics<'tcx>(base_doc: rbml::Doc,
         true
     });
 
-    ty::Generics { types: types, regions: regions }
+    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 }
 }
 
 pub fn is_associated_type(cdata: Cmd, id: ast::NodeId) -> bool {
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/astencode.rs b/src/librustc/middle/astencode.rs
index 113d127503f..50337ec25bd 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -830,6 +830,8 @@ trait rbml_writer_helpers<'tcx> {
     fn emit_tys<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>, tys: &[Ty<'tcx>]);
     fn emit_type_param_def<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
                                type_param_def: &ty::TypeParameterDef<'tcx>);
+    fn emit_predicate<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
+                          predicate: &ty::Predicate<'tcx>);
     fn emit_trait_ref<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
                           ty: &ty::TraitRef<'tcx>);
     fn emit_polytype<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
@@ -936,6 +938,15 @@ impl<'a, 'tcx> rbml_writer_helpers<'tcx> for Encoder<'a> {
         });
     }
 
+    fn emit_predicate<'a>(&mut self, ecx: &e::EncodeContext<'a, 'tcx>,
+                          predicate: &ty::Predicate<'tcx>) {
+        self.emit_opaque(|this| {
+            Ok(tyencode::enc_predicate(this.writer,
+                                       &ecx.ty_str_ctxt(),
+                                       predicate))
+        });
+    }
+
     fn emit_polytype<'a>(&mut self,
                          ecx: &e::EncodeContext<'a, 'tcx>,
                          pty: ty::Polytype<'tcx>) {
@@ -953,6 +964,11 @@ impl<'a, 'tcx> rbml_writer_helpers<'tcx> for Encoder<'a> {
                         Ok(encode_vec_per_param_space(
                             this, &pty.generics.regions,
                             |this, def| def.encode(this).unwrap()))
+                    });
+                    this.emit_struct_field("predicates", 2, |this| {
+                        Ok(encode_vec_per_param_space(
+                            this, &pty.generics.predicates,
+                            |this, def| this.emit_predicate(ecx, def)))
                     })
                 })
             });
@@ -1336,6 +1352,8 @@ trait rbml_decoder_decoder_helpers<'tcx> {
                               -> Rc<ty::TraitRef<'tcx>>;
     fn read_type_param_def<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
                                    -> ty::TypeParameterDef<'tcx>;
+    fn read_predicate<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
+                              -> ty::Predicate<'tcx>;
     fn read_polytype<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
                              -> ty::Polytype<'tcx>;
     fn read_existential_bounds<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
@@ -1536,6 +1554,15 @@ impl<'a, 'tcx> rbml_decoder_decoder_helpers<'tcx> for reader::Decoder<'a> {
         }).unwrap()
     }
 
+    fn read_predicate<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
+                              -> ty::Predicate<'tcx>
+    {
+        self.read_opaque(|this, doc| {
+            Ok(tydecode::parse_predicate_data(doc.data, doc.start, dcx.cdata.cnum, dcx.tcx,
+                                              |s, a| this.convert_def_id(dcx, s, a)))
+        }).unwrap()
+    }
+
     fn read_polytype<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>)
                              -> ty::Polytype<'tcx> {
         self.read_struct("Polytype", 2, |this| {
@@ -1553,7 +1580,13 @@ impl<'a, 'tcx> rbml_decoder_decoder_helpers<'tcx> for reader::Decoder<'a> {
                             this.read_struct_field("regions", 1, |this| {
                                 Ok(this.read_vec_per_param_space(
                                     |this| Decodable::decode(this).unwrap()))
-                            }).unwrap()
+                            }).unwrap(),
+
+                            predicates:
+                            this.read_struct_field("predicates", 2, |this| {
+                                Ok(this.read_vec_per_param_space(
+                                    |this| this.read_predicate(dcx)))
+                            }).unwrap(),
                         })
                     })
                 }).unwrap(),
diff --git a/src/librustc/middle/check_static.rs b/src/librustc/middle/check_static.rs
index a495d1e049d..5a53979d719 100644
--- a/src/librustc/middle/check_static.rs
+++ b/src/librustc/middle/check_static.rs
@@ -31,12 +31,13 @@ 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;
 use syntax::print::pprust;
 use syntax::visit::Visitor;
-use syntax::codemap::{DUMMY_SP, Span};
+use syntax::codemap::Span;
 use syntax::visit;
 
 #[deriving(Eq, PartialEq)]
@@ -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::misc(DUMMY_SP);
-        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/infer/error_reporting.rs b/src/librustc/middle/infer/error_reporting.rs
index d24eddf9ab0..e2a57629d7e 100644
--- a/src/librustc/middle/infer/error_reporting.rs
+++ b/src/librustc/middle/infer/error_reporting.rs
@@ -366,6 +366,7 @@ impl<'a, 'tcx> ErrorReporting<'tcx> for InferCtxt<'a, 'tcx> {
             infer::MatchExpressionArm(_, _) => "match arms have incompatible types",
             infer::IfExpression(_) => "if and else have incompatible types",
             infer::IfExpressionWithNoElse(_) => "if may be missing an else clause",
+            infer::EquatePredicate(_) => "equality predicate not satisfied",
         };
 
         self.tcx.sess.span_err(
@@ -1523,6 +1524,9 @@ impl<'a, 'tcx> ErrorReportingHelpers<'tcx> for InferCtxt<'a, 'tcx> {
                     infer::IfExpressionWithNoElse(_) => {
                         format!("if may be missing an else clause")
                     }
+                    infer::EquatePredicate(_) => {
+                        format!("equality where clause is satisfied")
+                    }
                 };
 
                 match self.values_str(&trace.values) {
diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index 81cd8dd20d2..3b62b96a3e9 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -129,7 +129,10 @@ pub enum TypeOrigin {
     IfExpression(Span),
 
     // Computing common supertype of an if expression with no else counter-part
-    IfExpressionWithNoElse(Span)
+    IfExpressionWithNoElse(Span),
+
+    // `where a == b`
+    EquatePredicate(Span),
 }
 
 impl Copy for TypeOrigin {}
@@ -1017,7 +1020,8 @@ impl TypeOrigin {
             RelateOutputImplTypes(span) => span,
             MatchExpressionArm(match_span, _) => match_span,
             IfExpression(span) => span,
-            IfExpressionWithNoElse(span) => span
+            IfExpressionWithNoElse(span) => span,
+            EquatePredicate(span) => span,
         }
     }
 }
@@ -1050,6 +1054,9 @@ impl<'tcx> Repr<'tcx> for TypeOrigin {
             IfExpressionWithNoElse(a) => {
                 format!("IfExpressionWithNoElse({})", a.repr(tcx))
             }
+            EquatePredicate(a) => {
+                format!("EquatePredicate({})", a.repr(tcx))
+            }
         }
     }
 }
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index 1bce353cb0c..822979c8601 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -11,7 +11,7 @@
 //! See `doc.rs` for high-level documentation
 
 use super::SelectionContext;
-use super::Obligation;
+use super::{Obligation, ObligationCause};
 use super::util;
 
 use middle::subst;
@@ -48,7 +48,7 @@ pub fn impl_can_satisfy(infcx: &InferCtxt,
     // same types.
     let param_env = ty::empty_parameter_environment();
     let mut selcx = SelectionContext::intercrate(infcx, &param_env, infcx.tcx);
-    let obligation = Obligation::misc(DUMMY_SP, impl1_trait_ref);
+    let obligation = Obligation::new(ObligationCause::dummy(), impl1_trait_ref);
     debug!("impl_can_satisfy(obligation={})", obligation.repr(infcx.tcx));
     selcx.evaluate_impl(impl2_def_id, &obligation)
 }
diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index 653c686ab19..412c188f5f4 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -9,17 +9,27 @@
 // except according to those terms.
 
 use middle::mem_categorization::Typer;
-use middle::ty;
-use middle::infer::InferCtxt;
+use middle::ty::{mod, Ty};
+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::Obligation;
-use super::FulfillmentError;
 use super::CodeSelectionError;
+use super::FulfillmentError;
+use super::Obligation;
+use super::ObligationCause;
+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)
@@ -37,37 +47,118 @@ 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<Obligation<'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
     // when `select_new_obligations` is called.
     attempted_mark: uint,
+
+    // A set of constraints that regionck must validate. Each
+    // constraint has the form `T:'a`, meaning "some type `T` must
+    // outlive the lifetime 'a". These constraints derive from
+    // instantiated type parameters. So if you had a struct defined
+    // like
+    //
+    //     struct Foo<T:'static> { ... }
+    //
+    // then in some expression `let x = Foo { ... }` it will
+    // instantiate the type parameter `T` with a fresh type `$0`. At
+    // the same time, it will record a region obligation of
+    // `$0:'static`. This will get checked later by regionck. (We
+    // can't generally check these things right away because we have
+    // to wait until types are resolved.)
+    //
+    // These are stored in a map keyed to the id of the innermost
+    // enclosing fn body / static initializer expression. This is
+    // because the location where the obligation was incurred can be
+    // relevant with respect to which sublifetime assumptions are in
+    // place. The reason that we store under the fn-id, and not
+    // something more fine-grained, is so that it is easier for
+    // regionck to be sure that it has found *all* the region
+    // obligations (otherwise, it's easy to fail to walk to a
+    // particular node-id).
+    region_obligations: NodeMap<Vec<RegionObligation<'tcx>>>,
+}
+
+pub struct RegionObligation<'tcx> {
+    pub sub_region: ty::Region,
+    pub sup_type: Ty<'tcx>,
+    pub cause: ObligationCause<'tcx>,
 }
 
 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_obligation(&mut self,
-                               tcx: &ty::ctxt<'tcx>,
-                               obligation: Obligation<'tcx>)
+    pub fn register_builtin_bound(&mut self,
+                                  tcx: &ty::ctxt<'tcx>,
+                                  ty: Ty<'tcx>,
+                                  builtin_bound: ty::BuiltinBound,
+                                  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));
+        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_trait_ref<'a>(&mut self,
+                                  tcx: &ty::ctxt<'tcx>,
+                                  trait_ref: Rc<ty::TraitRef<'tcx>>,
+                                  cause: ObligationCause<'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,
+                                      tcx: &ty::ctxt<'tcx>,
+                                      t_a: Ty<'tcx>,
+                                      r_b: ty::Region,
+                                      cause: ObligationCause<'tcx>)
+    {
+        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,
+                              body_id: ast::NodeId)
+                              -> &[RegionObligation<'tcx>]
+    {
+        match self.region_obligations.get(&body_id) {
+            None => Default::default(),
+            Some(vec) => vec.as_slice(),
         }
     }
 
@@ -81,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();
@@ -117,8 +208,8 @@ impl<'tcx> FulfillmentContext<'tcx> {
         self.select(&mut selcx, false)
     }
 
-    pub fn pending_trait_obligations(&self) -> &[Obligation<'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
@@ -129,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);
@@ -154,37 +245,26 @@ 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)));
+            {
+                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.
+                    let processed =
+                        if skip == 0 {
+                            process_predicate(selcx, predicate,
+                                              &mut selections, &mut errors, region_obligations)
+                        } else {
+                            skip -= 1;
                             false
-                        }
-                    }
-                }
-            });
+                        };
+                    !processed
+                });
+            }
 
-            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;
             }
@@ -192,13 +272,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 {
@@ -208,3 +287,101 @@ impl<'tcx> FulfillmentContext<'tcx> {
         }
     }
 }
+
+fn process_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
+{
+    /*!
+     * Processes a predicate obligation and modifies the appropriate
+     * output array with the successful/error result.  Returns `false`
+     * if the predicate could not be processed 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) => {
+                    false
+                }
+                Ok(Some(s)) => {
+                    selections.push(s);
+                    true
+                }
+                Err(selection_err) => {
+                    debug!("predicate: {} error: {}",
+                           predicate.repr(tcx),
+                           selection_err.repr(tcx));
+                    errors.push(
+                        FulfillmentError::new(
+                            predicate.clone(),
+                            CodeSelectionError(selection_err)));
+                    true
+                }
+            }
+        }
+
+        ty::Predicate::Equate(a, b) => {
+            let origin = infer::EquatePredicate(predicate.cause.span);
+            match infer::mk_eqty(selcx.infcx(), false, origin, a, b) {
+                Ok(()) => {
+                    true
+                }
+                Err(_) => {
+                    errors.push(
+                        FulfillmentError::new(
+                            predicate.clone(),
+                            CodeSelectionError(Unimplemented)));
+                    true
+                }
+            }
+        }
+
+        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`
+            true
+        }
+
+        ty::Predicate::TypeOutlives(t_a, r_b) => {
+            register_region_obligation(tcx, t_a, r_b, predicate.cause, region_obligations);
+            true
+        }
+    }
+}
+
+impl<'tcx> Repr<'tcx> for RegionObligation<'tcx> {
+    fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
+        format!("RegionObligation(sub_region={}, sup_type={})",
+                self.sub_region.repr(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 d410a456dc9..604a0607c0b 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,17 +22,18 @@ 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;
+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::transitive_bounds;
 pub use self::util::Supertraits;
 pub use self::util::search_trait_and_supertraits_from_bound;
+pub use self::util::transitive_bounds;
+pub use self::util::trait_ref_for_builtin_bound;
 
 mod coherence;
 mod fulfill;
@@ -47,22 +47,32 @@ mod util;
 /// provides the required vtable, or else finding a bound that is in
 /// scope. The eventual result is usually a `Selection` (defined below).
 #[deriving(Clone)]
-pub struct Obligation<'tcx> {
+pub struct Obligation<'tcx, T> {
     pub cause: ObligationCause<'tcx>,
     pub recursion_depth: uint,
-    pub trait_ref: Rc<ty::TraitRef<'tcx>>,
+    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.
-#[deriving(Clone)]
+#[deriving(Copy, Clone)]
 pub struct ObligationCause<'tcx> {
     pub span: Span,
+
+    // The id of the fn body that triggered this obligation. This is
+    // used for region obligations to determine the precise
+    // environment in which the region obligation should be evaluated
+    // (in particular, closures can add new assumptions). See the
+    // field `region_obligations` of the `FulfillmentContext` for more
+    // information.
+    pub body_id: ast::NodeId,
+
     pub code: ObligationCauseCode<'tcx>
 }
 
-impl<'tcx> Copy for ObligationCause<'tcx> {}
-
-#[deriving(Clone)]
+#[deriving(Copy, Clone)]
 pub enum ObligationCauseCode<'tcx> {
     /// Not well classified or should be obvious from span.
     MiscObligation,
@@ -86,7 +96,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,
@@ -95,21 +105,21 @@ pub enum ObligationCauseCode<'tcx> {
     ObjectSized,
 }
 
-pub type Obligations<'tcx> = subst::VecPerParamSpace<Obligation<'tcx>>;
-
-impl<'tcx> Copy for 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, Obligation<'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: Obligation<'tcx>,
+    pub obligation: PredicateObligation<'tcx>,
     pub code: FulfillmentErrorCode<'tcx>
 }
 
@@ -219,33 +229,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, Obligation<'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,
@@ -265,63 +248,56 @@ 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<Obligation<'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<Obligation<'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> Obligation<'tcx> {
-    pub fn new(cause: ObligationCause<'tcx>, trait_ref: Rc<ty::TraitRef<'tcx>>)
-               -> Obligation<'tcx> {
+impl<'tcx,O> Obligation<'tcx,O> {
+    pub fn new(cause: ObligationCause<'tcx>,
+               trait_ref: O)
+               -> Obligation<'tcx, O>
+    {
         Obligation { cause: cause,
                      recursion_depth: 0,
                      trait_ref: trait_ref }
     }
 
-    pub fn misc(span: Span, trait_ref: Rc<ty::TraitRef<'tcx>>) -> Obligation<'tcx> {
-        Obligation::new(ObligationCause::misc(span), trait_ref)
+    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>>> {
     pub fn self_ty(&self) -> Ty<'tcx> {
         self.trait_ref.self_ty()
     }
 }
 
 impl<'tcx> ObligationCause<'tcx> {
-    pub fn new(span: Span, code: ObligationCauseCode<'tcx>)
+    pub fn new(span: Span,
+               body_id: ast::NodeId,
+               code: ObligationCauseCode<'tcx>)
                -> ObligationCause<'tcx> {
-        ObligationCause { span: span, code: code }
+        ObligationCause { span: span, body_id: body_id, code: code }
     }
 
-    pub fn misc(span: Span) -> ObligationCause<'tcx> {
-        ObligationCause { span: span, code: MiscObligation }
+    pub fn misc(span: Span, body_id: ast::NodeId) -> ObligationCause<'tcx> {
+        ObligationCause { span: span, body_id: body_id, code: MiscObligation }
     }
 
     pub fn dummy() -> ObligationCause<'tcx> {
-        ObligationCause { span: DUMMY_SP, code: MiscObligation }
+        ObligationCause { span: DUMMY_SP, body_id: 0, code: MiscObligation }
     }
 }
 
@@ -406,7 +382,8 @@ impl<N> VtableBuiltinData<N> {
 }
 
 impl<'tcx> FulfillmentError<'tcx> {
-    fn new(obligation: Obligation<'tcx>, code: FulfillmentErrorCode<'tcx>)
+    fn new(obligation: PredicateObligation<'tcx>,
+           code: FulfillmentErrorCode<'tcx>)
            -> FulfillmentError<'tcx>
     {
         FulfillmentError { obligation: obligation, code: code }
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 06f8cbf1a6a..88c70f5557c 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::{Obligation, 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};
@@ -70,14 +69,14 @@ pub struct SelectionContext<'cx, 'tcx:'cx> {
 }
 
 // A stack that walks back up the stack frame.
-struct ObligationStack<'prev, 'tcx: 'prev> {
-    obligation: &'prev Obligation<'tcx>,
+struct TraitObligationStack<'prev, 'tcx: 'prev> {
+    obligation: &'prev TraitObligation<'tcx>,
 
     /// Trait ref from `obligation` but skolemized with the
     /// selection-context's skolemizer. Used to check for recursion.
     skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
 
-    previous: Option<&'prev ObligationStack<'prev, 'tcx>>
+    previous: Option<&'prev TraitObligationStack<'prev, 'tcx>>
 }
 
 #[deriving(Clone)]
@@ -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
     }
@@ -213,7 +216,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// Evaluates whether the obligation can be satisfied. Returns an indication of whether the
     /// obligation can be satisfied and, if so, by what means. Never affects surrounding typing
     /// environment.
-    pub fn select(&mut self, obligation: &Obligation<'tcx>)
+    pub fn select(&mut self, obligation: &TraitObligation<'tcx>)
                   -> SelectionResult<'tcx, Selection<'tcx>> {
         debug!("select({})", obligation.repr(self.tcx()));
         assert!(!obligation.trait_ref.has_escaping_regions());
@@ -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, Obligation<'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,25 +240,23 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     /// Evaluates whether the obligation `obligation` can be satisfied (by any means).
     pub fn evaluate_obligation(&mut self,
-                               obligation: &Obligation<'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,
                                               bound: ty::BuiltinBound,
-                                              previous_stack: &ObligationStack<'o, 'tcx>,
+                                              previous_stack: &TraitObligationStack<'o, 'tcx>,
                                               ty: Ty<'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,9 +273,39 @@ 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<&ObligationStack<'o, 'tcx>>,
-                                           obligation: &Obligation<'tcx>)
+                                           previous_stack: Option<&TraitObligationStack<'o, 'tcx>>,
+                                           obligation: &TraitObligation<'tcx>)
                                            -> EvaluationResult<'tcx>
     {
         debug!("evaluate_obligation_recursively({})",
@@ -312,7 +320,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn evaluate_stack<'o>(&mut self,
-                          stack: &ObligationStack<'o, 'tcx>)
+                          stack: &TraitObligationStack<'o, 'tcx>)
                           -> EvaluationResult<'tcx>
     {
         // In intercrate mode, whenever any of the types are unbound,
@@ -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;
         }
@@ -392,7 +400,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// `obligation_self_ty`. This can be used either for trait or inherent impls.
     pub fn evaluate_impl(&mut self,
                          impl_def_id: ast::DefId,
-                         obligation: &Obligation<'tcx>)
+                         obligation: &TraitObligation<'tcx>)
                          -> bool
     {
         debug!("evaluate_impl(impl_def_id={}, obligation={})",
@@ -423,7 +431,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     // candidates. See `doc.rs` and the `Candidate` type for more details.
 
     fn candidate_from_obligation<'o>(&mut self,
-                                     stack: &ObligationStack<'o, 'tcx>)
+                                     stack: &TraitObligationStack<'o, 'tcx>)
                                      -> SelectionResult<'tcx, Candidate<'tcx>>
     {
         // Watch out for overflow. This intentionally bypasses (and does
@@ -466,7 +474,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn candidate_from_obligation_no_cache<'o>(&mut self,
-                                              stack: &ObligationStack<'o, 'tcx>)
+                                              stack: &TraitObligationStack<'o, 'tcx>)
                                               -> SelectionResult<'tcx, Candidate<'tcx>>
     {
         if ty::type_is_error(stack.obligation.self_ty()) {
@@ -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))
         {
@@ -626,12 +633,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn assemble_candidates<'o>(&mut self,
-                               stack: &ObligationStack<'o, 'tcx>)
+                               stack: &TraitObligationStack<'o, 'tcx>)
                                -> Result<CandidateSet<'tcx>, SelectionError<'tcx>>
     {
         // Check for overflow.
 
-        let ObligationStack { obligation, .. } = *stack;
+        let TraitObligationStack { obligation, .. } = *stack;
 
         let mut candidates = CandidateSet {
             vec: Vec::new(),
@@ -682,7 +689,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     ///
     /// Never affects inference environment.
     fn assemble_candidates_from_caller_bounds(&mut self,
-                                              obligation: &Obligation<'tcx>,
+                                              obligation: &TraitObligation<'tcx>,
                                               candidates: &mut CandidateSet<'tcx>)
                                               -> Result<(),SelectionError<'tcx>>
     {
@@ -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 =
@@ -720,7 +727,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// parameters and hence do not affect whether this trait is a match or not. They will be
     /// unified during the confirmation step.
     fn assemble_unboxed_closure_candidates(&mut self,
-                                           obligation: &Obligation<'tcx>,
+                                           obligation: &TraitObligation<'tcx>,
                                            candidates: &mut CandidateSet<'tcx>)
                                            -> Result<(),SelectionError<'tcx>>
     {
@@ -762,7 +769,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     /// Implement one of the `Fn()` family for a fn pointer.
     fn assemble_fn_pointer_candidates(&mut self,
-                                      obligation: &Obligation<'tcx>,
+                                      obligation: &TraitObligation<'tcx>,
                                       candidates: &mut CandidateSet<'tcx>)
                                       -> Result<(),SelectionError<'tcx>>
     {
@@ -800,7 +807,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     /// Search for impls that might apply to `obligation`.
     fn assemble_candidates_from_impls(&mut self,
-                                      obligation: &Obligation<'tcx>,
+                                      obligation: &TraitObligation<'tcx>,
                                       candidates: &mut CandidateSet<'tcx>)
                                       -> Result<(), SelectionError<'tcx>>
     {
@@ -831,7 +838,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// obligations are met. Returns true if `candidate` remains viable after this further
     /// scrutiny.
     fn winnow_candidate<'o>(&mut self,
-                            stack: &ObligationStack<'o, 'tcx>,
+                            stack: &TraitObligationStack<'o, 'tcx>,
                             candidate: &Candidate<'tcx>)
                             -> EvaluationResult<'tcx>
     {
@@ -846,13 +853,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn winnow_selection<'o>(&mut self,
-                            stack: Option<&ObligationStack<'o, 'tcx>>,
+                            stack: Option<&TraitObligationStack<'o, 'tcx>>,
                             selection: Selection<'tcx>)
                             -> EvaluationResult<'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 => { }
@@ -885,7 +892,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     /// essentially harmless.  See issue #18453 for more details of
     /// a case where doing the opposite caused us harm.
     fn candidate_should_be_dropped_in_favor_of<'o>(&mut self,
-                                                   stack: &ObligationStack<'o, 'tcx>,
+                                                   stack: &TraitObligationStack<'o, 'tcx>,
                                                    candidate_i: &Candidate<'tcx>,
                                                    candidate_j: &Candidate<'tcx>)
                                                    -> bool
@@ -928,12 +935,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     fn assemble_builtin_bound_candidates<'o>(&mut self,
                                              bound: ty::BuiltinBound,
-                                             stack: &ObligationStack<'o, 'tcx>,
+                                             stack: &TraitObligationStack<'o, '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)
                     }
                 }
 
@@ -1266,6 +1289,15 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     // don't supply any form of builtin impl.
                     if !this.tcx().sess.features.borrow().opt_out_copy {
                         return Ok(ParameterBuiltin)
+                    } else {
+                        // Older, backwards compatibility behavior:
+                        if
+                            Some(def_id) == tcx.lang_items.no_copy_bound() ||
+                            Some(def_id) == tcx.lang_items.managed_bound() ||
+                            ty::has_dtor(tcx, def_id)
+                        {
+                            return Err(Unimplemented);
+                        }
                     }
                 }
 
@@ -1274,7 +1306,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()
                     {
@@ -1300,7 +1332,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     // type error.  See `doc.rs` for more details.
 
     fn confirm_candidate(&mut self,
-                         obligation: &Obligation<'tcx>,
+                         obligation: &TraitObligation<'tcx>,
                          candidate: Candidate<'tcx>)
                          -> Result<Selection<'tcx>,SelectionError<'tcx>>
     {
@@ -1343,7 +1375,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn confirm_param_candidate(&mut self,
-                               obligation: &Obligation<'tcx>,
+                               obligation: &TraitObligation<'tcx>,
                                param: VtableParamData<'tcx>)
                                -> Result<VtableParamData<'tcx>,
                                          SelectionError<'tcx>>
@@ -1359,15 +1391,15 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn confirm_builtin_candidate(&mut self,
-                                 obligation: &Obligation<'tcx>,
+                                 obligation: &TraitObligation<'tcx>,
                                  bound: ty::BuiltinBound)
-                                 -> Result<VtableBuiltinData<Obligation<'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(
@@ -1379,32 +1411,47 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn vtable_builtin_data(&mut self,
-                           obligation: &Obligation<'tcx>,
+                           obligation: &TraitObligation<'tcx>,
                            bound: ty::BuiltinBound,
                            nested: Vec<Ty<'tcx>>)
-                           -> VtableBuiltinData<Obligation<'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: &Obligation<'tcx>,
+                              obligation: &TraitObligation<'tcx>,
                               impl_def_id: ast::DefId)
-                              -> Result<VtableImplData<'tcx, Obligation<'tcx>>,
+                              -> Result<VtableImplData<'tcx, PredicateObligation<'tcx>>,
                                         SelectionError<'tcx>>
     {
         debug!("confirm_impl_candidate({},{})",
@@ -1414,6 +1461,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,20 +1470,20 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                    substs: Substs<'tcx>,
                    cause: ObligationCause<'tcx>,
                    recursion_depth: uint)
-                   -> VtableImplData<'tcx, Obligation<'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,
-                                    obligation: &Obligation<'tcx>)
+                                    obligation: &TraitObligation<'tcx>)
                                     -> Result<ty::Ty<'tcx>,SelectionError<'tcx>>
     {
         debug!("confirm_fn_pointer_candidate({})",
@@ -1480,7 +1528,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn confirm_unboxed_closure_candidate(&mut self,
-                                         obligation: &Obligation<'tcx>,
+                                         obligation: &TraitObligation<'tcx>,
                                          closure_def_id: ast::DefId,
                                          substs: &Substs<'tcx>)
                                          -> Result<(),SelectionError<'tcx>>
@@ -1531,7 +1579,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     fn rematch_impl(&mut self,
                     impl_def_id: ast::DefId,
-                    obligation: &Obligation<'tcx>)
+                    obligation: &TraitObligation<'tcx>)
                     -> Substs<'tcx>
     {
         match self.match_impl(impl_def_id, obligation) {
@@ -1550,7 +1598,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     fn match_impl(&mut self,
                   impl_def_id: ast::DefId,
-                  obligation: &Obligation<'tcx>)
+                  obligation: &TraitObligation<'tcx>)
                   -> Result<Substs<'tcx>, ()>
     {
         let impl_trait_ref = ty::impl_trait_ref(self.tcx(),
@@ -1577,7 +1625,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn fast_reject_trait_refs(&mut self,
-                              obligation: &Obligation,
+                              obligation: &TraitObligation,
                               impl_trait_ref: &ty::TraitRef)
                               -> bool
     {
@@ -1600,7 +1648,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     }
 
     fn match_trait_refs(&mut self,
-                        obligation: &Obligation<'tcx>,
+                        obligation: &TraitObligation<'tcx>,
                         trait_ref: Rc<ty::TraitRef<'tcx>>)
                         -> Result<(),()>
     {
@@ -1752,9 +1800,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))
         }
     }
 
@@ -1762,13 +1810,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     // Miscellany
 
     fn push_stack<'o,'s:'o>(&mut self,
-                            previous_stack: Option<&'s ObligationStack<'s, 'tcx>>,
-                            obligation: &'o Obligation<'tcx>)
-                            -> ObligationStack<'o, 'tcx>
+                            previous_stack: Option<&'s TraitObligationStack<'s, 'tcx>>,
+                            obligation: &'o TraitObligation<'tcx>)
+                            -> TraitObligationStack<'o, 'tcx>
     {
         let skol_trait_ref = obligation.trait_ref.fold_with(&mut self.skolemizer);
 
-        ObligationStack {
+        TraitObligationStack {
             obligation: obligation,
             skol_trait_ref: skol_trait_ref,
             previous: previous_stack.map(|p| p), // FIXME variance
@@ -1785,17 +1833,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<Obligation<'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,
@@ -1840,14 +1887,16 @@ impl<'tcx> SelectionCache<'tcx> {
     }
 }
 
-impl<'o, 'tcx> ObligationStack<'o, 'tcx> {
-    fn iter(&self) -> Option<&ObligationStack<'o, 'tcx>> {
+impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> {
+    fn iter(&self) -> Option<&TraitObligationStack<'o, 'tcx>> {
         Some(self)
     }
 }
 
-impl<'o, 'tcx> Iterator<&'o ObligationStack<'o, 'tcx>> for Option<&'o ObligationStack<'o, 'tcx>> {
-    fn next(&mut self) -> Option<&'o ObligationStack<'o, 'tcx>> {
+impl<'o, 'tcx> Iterator<&'o TraitObligationStack<'o,'tcx>>
+           for Option<&'o TraitObligationStack<'o, 'tcx>>
+{
+    fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> {
         match *self {
             Some(o) => {
                 *self = o.previous;
@@ -1860,9 +1909,9 @@ impl<'o, 'tcx> Iterator<&'o ObligationStack<'o, 'tcx>> for Option<&'o Obligation
     }
 }
 
-impl<'o, 'tcx> Repr<'tcx> for ObligationStack<'o, 'tcx> {
+impl<'o, 'tcx> Repr<'tcx> for TraitObligationStack<'o, 'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
-        format!("ObligationStack({})",
+        format!("TraitObligationStack({})",
                 self.obligation.repr(tcx))
     }
 }
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index 159b6961782..52154e0be7a 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,112 +20,138 @@ use syntax::codemap::Span;
 use util::common::ErrorReported;
 use util::ppaux::Repr;
 
-use super::{Obligation, ObligationCause, VtableImpl,
-            VtableParam, VtableParamData, VtableImplData};
+use super::{Obligation, ObligationCause, PredicateObligation,
+            VtableImpl, VtableParam, VtableParamData, VtableImplData};
 
 ///////////////////////////////////////////////////////////////////////////
-// Supertrait iterator
+// `Elaboration` iterator
+///////////////////////////////////////////////////////////////////////////
 
-pub struct Supertraits<'cx, 'tcx:'cx> {
+/// "Elaboration" is the process of identifying all the predicates that
+/// are implied by a source predicate. Currently this basically means
+/// walking the "supertraits" and other similar assumptions. For
+/// example, if we know that `T : Ord`, the elaborator would deduce
+/// that `T : PartialOrd` holds as well. Similarly, if we have `trait
+/// Foo : 'static`, and we know that `T : Foo`, then we know that `T :
+/// 'static`.
+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());
-            bound_trait_ref.map(|trait_ref| trait_bounds.push(trait_ref));
+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 => {
@@ -138,6 +163,55 @@ impl<'cx, 'tcx> Iterator<Rc<ty::TraitRef<'tcx>>> for Supertraits<'cx, 'tcx> {
     }
 }
 
+///////////////////////////////////////////////////////////////////////////
+// Supertrait iterator
+///////////////////////////////////////////////////////////////////////////
+
+/// A filter around the `Elaborator` that just yields up supertrait references,
+/// not other kinds of predicates.
+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(..)) => {
+                }
+            }
+        }
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Other
+///////////////////////////////////////////////////////////////////////////
+
 // 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
@@ -176,103 +250,56 @@ 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<Obligation<'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!("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<Obligation<'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() });
-    }
+    debug!("predicates_for_generics(generic_bounds={})",
+           generic_bounds.repr(tcx));
+
+    generic_bounds.predicates.map(|predicate| {
+        Obligation { cause: cause,
+                     recursion_depth: recursion_depth,
+                     trait_ref: predicate.clone() }
+    })
 }
 
 pub fn trait_ref_for_builtin_bound<'tcx>(
     tcx: &ty::ctxt<'tcx>,
     builtin_bound: ty::BuiltinBound,
     param_ty: Ty<'tcx>)
-    -> Option<Rc<ty::TraitRef<'tcx>>>
+    -> Result<Rc<ty::TraitRef<'tcx>>, ErrorReported>
 {
     match tcx.lang_items.from_builtin_kind(builtin_bound) {
         Ok(def_id) => {
-            Some(Rc::new(ty::TraitRef {
+            Ok(Rc::new(ty::TraitRef {
                 def_id: def_id,
                 substs: Substs::empty().with_self_ty(param_ty)
             }))
         }
         Err(e) => {
             tcx.sess.err(e.as_slice());
-            None
+            Err(ErrorReported)
         }
     }
 }
 
-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<Obligation<'tcx>, ErrorReported>
+    -> Result<PredicateObligation<'tcx>, ErrorReported>
 {
-    let trait_ref = trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty);
-    match trait_ref {
-        Some(trait_ref) => Ok(Obligation {
-                cause: cause,
-                recursion_depth: recursion_depth,
-                trait_ref: trait_ref
-            }),
-        None => Err(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: ty::Predicate::Trait(trait_ref),
+    })
 }
 
 /// Starting from a caller obligation `caller_bound` (which has coordinates `space`/`i` in the list
@@ -294,7 +321,7 @@ pub fn search_trait_and_supertraits_from_bound<'tcx>(tcx: &ty::ctxt<'tcx>,
     return None;
 }
 
-impl<'tcx> Repr<'tcx> for super::Obligation<'tcx> {
+impl<'tcx,O:Repr<'tcx>> Repr<'tcx> for super::Obligation<'tcx, O> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         format!("Obligation(trait_ref={},depth={})",
                 self.trait_ref.repr(tcx),
@@ -358,10 +385,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 3f555ec5c4c..ddbf69685cd 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,10 +77,10 @@ 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, FnStyle, Ident, ItemTrait, LOCAL_CRATE};
+use syntax::ast::{CrateNum, DefId, DUMMY_NODE_ID, FnStyle, Ident, ItemTrait, LOCAL_CRATE};
 use syntax::ast::{MutImmutable, MutMutable, Name, NamedField, NodeId};
 use syntax::ast::{Onceness, StmtExpr, StmtSemi, StructField, UnnamedField};
 use syntax::ast::{Visibility};
@@ -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,18 +1614,28 @@ 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>>,
     pub regions: VecPerParamSpace<RegionParameterDef>,
+    pub predicates: VecPerParamSpace<Predicate<'tcx>>,
 }
 
 impl<'tcx> Generics<'tcx> {
     pub fn empty() -> Generics<'tcx> {
-        Generics { types: VecPerParamSpace::empty(),
-                   regions: VecPerParamSpace::empty() }
+        Generics {
+            types: VecPerParamSpace::empty(),
+            regions: VecPerParamSpace::empty(),
+            predicates: VecPerParamSpace::empty(),
+        }
     }
 
     pub fn has_type_params(&self, space: subst::ParamSpace) -> bool {
@@ -1638,8 +1649,49 @@ 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> {
+    /// Corresponds to `where Foo : Bar<A,B,C>`. `Foo` here would be
+    /// the `Self` type of the trait reference and `A`, `B`, and `C`
+    /// would be the parameters in the `TypeSpace`.
+    Trait(Rc<TraitRef<'tcx>>),
+
+    /// where `T1 == T2`.
+    Equate(/* T1 */ Ty<'tcx>, /* T2 */ Ty<'tcx>),
+
+    /// where 'a : 'b
+    RegionOutlives(/* 'a */ Region, /* 'b */ 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
+            }
         }
     }
 }
@@ -1665,19 +1717,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()
     }
 }
 
@@ -1728,9 +1781,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
@@ -1740,10 +1790,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::Obligation<'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.
@@ -1762,7 +1809,6 @@ impl<'tcx> ParameterEnvironment<'tcx> {
                                 let method_generics = &method_ty.generics;
                                 construct_parameter_environment(
                                     cx,
-                                    method.span,
                                     method_generics,
                                     method.pe_body().id)
                             }
@@ -1797,7 +1843,6 @@ impl<'tcx> ParameterEnvironment<'tcx> {
                                 let method_generics = &method_ty.generics;
                                 construct_parameter_environment(
                                     cx,
-                                    method.span,
                                     method_generics,
                                     method.pe_body().id)
                             }
@@ -1824,7 +1869,6 @@ impl<'tcx> ParameterEnvironment<'tcx> {
                         let fn_pty = ty::lookup_item_type(cx, fn_def_id);
 
                         construct_parameter_environment(cx,
-                                                        item.span,
                                                         &fn_pty.generics,
                                                         body.id)
                     }
@@ -1835,8 +1879,7 @@ impl<'tcx> ParameterEnvironment<'tcx> {
                     ast::ItemStatic(..) => {
                         let def_id = ast_util::local_def(id);
                         let pty = ty::lookup_item_type(cx, def_id);
-                        construct_parameter_environment(cx, item.span,
-                                                        &pty.generics, id)
+                        construct_parameter_environment(cx, &pty.generics, id)
                     }
                     _ => {
                         cx.sess.span_bug(item.span,
@@ -3141,7 +3184,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 => {}
@@ -3156,20 +3200,26 @@ pub fn type_moves_by_default<'tcx>(cx: &ctxt<'tcx>,
 
     let infcx = infer::new_infer_ctxt(cx);
     let mut fulfill_cx = traits::FulfillmentContext::new();
-    let obligation = traits::obligation_for_builtin_bound(
-        cx,
-        ObligationCause::misc(DUMMY_SP),
-        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);
+
+    // we can use dummy values here because we won't report any errors
+    // that result nor will we pay any mind to region obligations that arise
+    // (there shouldn't really be any anyhow)
+    let cause = ObligationCause::misc(DUMMY_SP, DUMMY_NODE_ID);
+
+    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 {
@@ -4979,11 +5029,11 @@ 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>
+/// Given a reference to a trait, returns the "superbounds" declared
+/// on the trait, with appropriate substitutions applied.
+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);
 
@@ -5074,11 +5124,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.
@@ -5436,56 +5514,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> {
@@ -5835,8 +5919,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(), }
 }
@@ -5844,7 +5927,6 @@ pub fn empty_parameter_environment<'tcx>() -> ParameterEnvironment<'tcx> {
 /// See `ParameterEnvironment` struct def'n for details
 pub fn construct_parameter_environment<'tcx>(
     tcx: &ctxt<'tcx>,
-    span: Span,
     generics: &ty::Generics<'tcx>,
     free_id: ast::NodeId)
     -> ParameterEnvironment<'tcx>
@@ -5881,11 +5963,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::misc(span),
-                                                       &bounds,
-                                                       &free_substs.types);
-    let type_bounds = bounds.types.subst(tcx, &free_substs);
 
     //
     // Compute region bounds. For now, these relations are stored in a
@@ -5893,23 +5970,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(),
     };
 
@@ -5938,31 +6009,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());
                 }
             }
         }
@@ -6281,6 +6345,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 77092025349..8b54a46bfb9 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -137,11 +137,6 @@ pub trait TypeFolder<'tcx> {
     fn fold_item_substs(&mut self, i: ty::ItemSubsts<'tcx>) -> ty::ItemSubsts<'tcx> {
         super_fold_item_substs(self, i)
     }
-
-    fn fold_obligation(&mut self, o: &traits::Obligation<'tcx>)
-                       -> traits::Obligation<'tcx> {
-        super_fold_obligation(self, o)
-    }
 }
 
 ///////////////////////////////////////////////////////////////////////////
@@ -404,6 +399,25 @@ impl<'tcx> TypeFoldable<'tcx> for ty::Generics<'tcx> {
         ty::Generics {
             types: self.types.fold_with(folder),
             regions: self.regions.fold_with(folder),
+            predicates: self.predicates.fold_with(folder),
+        }
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for ty::Predicate<'tcx> {
+    fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Predicate<'tcx> {
+        match *self {
+            ty::Predicate::Trait(ref a) =>
+                ty::Predicate::Trait(a.fold_with(folder)),
+            ty::Predicate::Equate(ref a, ref b) =>
+                ty::Predicate::Equate(a.fold_with(folder),
+                                        b.fold_with(folder)),
+            ty::Predicate::RegionOutlives(ref a, ref b) =>
+                ty::Predicate::RegionOutlives(a.fold_with(folder),
+                                                b.fold_with(folder)),
+            ty::Predicate::TypeOutlives(ref a, ref b) =>
+                ty::Predicate::TypeOutlives(a.fold_with(folder),
+                                              b.fold_with(folder)),
         }
     }
 }
@@ -411,8 +425,7 @@ impl<'tcx> TypeFoldable<'tcx> for ty::Generics<'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),
         }
     }
 }
@@ -434,9 +447,15 @@ impl<'tcx> TypeFoldable<'tcx> for ty::UnsizeKind<'tcx> {
     }
 }
 
-impl<'tcx> TypeFoldable<'tcx> for traits::Obligation<'tcx> {
-    fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::Obligation<'tcx> {
-        folder.fold_obligation(self)
+impl<'tcx,O> TypeFoldable<'tcx> for traits::Obligation<'tcx,O>
+    where O : TypeFoldable<'tcx>
+{
+    fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::Obligation<'tcx, O> {
+        traits::Obligation {
+            cause: self.cause,
+            recursion_depth: self.recursion_depth,
+            trait_ref: self.trait_ref.fold_with(folder),
+        }
     }
 }
 
@@ -687,17 +706,6 @@ pub fn super_fold_item_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T,
     }
 }
 
-pub fn super_fold_obligation<'tcx, T:TypeFolder<'tcx>>(this: &mut T,
-                                                       obligation: &traits::Obligation<'tcx>)
-                                                       -> traits::Obligation<'tcx>
-{
-    traits::Obligation {
-        cause: obligation.cause,
-        recursion_depth: obligation.recursion_depth,
-        trait_ref: obligation.trait_ref.fold_with(this),
-    }
-}
-
 ///////////////////////////////////////////////////////////////////////////
 // Higher-ranked things
 
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 77412b00299..83938fa3357 100644
--- a/src/librustc_trans/trans/common.rs
+++ b/src/librustc_trans/trans/common.rs
@@ -793,7 +793,8 @@ pub fn fulfill_obligation<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
     // Do the initial selection for the obligation. This yields the
     // shallow result we are looking for -- that is, what specific impl.
     let mut selcx = traits::SelectionContext::new(&infcx, &param_env, tcx);
-    let obligation = traits::Obligation::misc(span, trait_ref.clone());
+    let obligation = traits::Obligation::new(traits::ObligationCause::dummy(),
+                                             trait_ref.clone());
     let selection = match selcx.select(&obligation) {
         Ok(Some(selection)) => selection,
         Ok(None) => {
@@ -826,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 b6a9e2cbc59..bf1f2c0ce80 100644
--- a/src/librustc_typeck/check/method/confirm.rs
+++ b/src/librustc_typeck/check/method/confirm.rs
@@ -462,8 +462,7 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
                method_bounds.repr(self.tcx()));
 
         self.fcx.add_obligations_for_parameters(
-            traits::ObligationCause::misc(self.span),
-            method_bounds_substs,
+            traits::ObligationCause::misc(self.span, self.fcx.body_id),
             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 53bda93b28e..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, 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()));
 
@@ -219,8 +224,7 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
     let method_bounds = method_ty.generics.to_bounds(fcx.tcx(), &trait_ref.substs);
     assert!(!method_bounds.has_escaping_regions());
     fcx.add_obligations_for_parameters(
-        traits::ObligationCause::misc(span),
-        &trait_ref.substs,
+        traits::ObligationCause::misc(span, fcx.body_id),
         &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 4d23161f6de..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),
-                            &impl_bounds,
-                            &substs.types);
+                            traits::ObligationCause::misc(self.span, self.fcx.body_id),
+                            &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 7e29e7078d4..573c63eb6af 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -84,13 +84,14 @@ use self::TupleArgumentsFlag::*;
 
 use astconv::{mod, ast_region_to_region, ast_ty_to_ty, AstConv};
 use check::_match::pat_ctxt;
-use middle::{const_eval, def, traits};
+use middle::{const_eval, def};
 use middle::infer;
 use middle::lang_items::IteratorItem;
 use middle::mem_categorization::{mod, McResult};
 use middle::pat_util::{mod, pat_id_map};
 use middle::region::CodeExtent;
 use middle::subst::{mod, Subst, Substs, VecPerParamSpace, ParamSpace};
+use middle::traits;
 use middle::ty::{FnSig, VariantInfo, Polytype};
 use middle::ty::{Disr, ParamTy, ParameterEnvironment};
 use middle::ty::{mod, Ty};
@@ -108,7 +109,6 @@ use util::ppaux::{mod, UserString, Repr};
 use util::nodemap::{DefIdMap, FnvHashMap, NodeMap};
 
 use std::cell::{Cell, Ref, RefCell};
-use std::collections::hash_map::{Occupied, Vacant};
 use std::mem::replace;
 use std::rc::Rc;
 use syntax::{mod, abi, attr};
@@ -161,42 +161,10 @@ pub struct Inherited<'a, 'tcx: 'a> {
     // one is never copied into the tcx: it is only used by regionck.
     fn_sig_map: RefCell<NodeMap<Vec<Ty<'tcx>>>>,
 
-    // A set of constraints that regionck must validate. Each
-    // constraint has the form `T:'a`, meaning "some type `T` must
-    // outlive the lifetime 'a". These constraints derive from
-    // instantiated type parameters. So if you had a struct defined
-    // like
-    //
-    //     struct Foo<T:'static> { ... }
-    //
-    // then in some expression `let x = Foo { ... }` it will
-    // instantiate the type parameter `T` with a fresh type `$0`. At
-    // the same time, it will record a region obligation of
-    // `$0:'static`. This will get checked later by regionck. (We
-    // can't generally check these things right away because we have
-    // to wait until types are resolved.)
-    //
-    // These are stored in a map keyed to the id of the innermost
-    // enclosing fn body / static initializer expression. This is
-    // because the location where the obligation was incurred can be
-    // relevant with respect to which sublifetime assumptions are in
-    // place. The reason that we store under the fn-id, and not
-    // something more fine-grained, is so that it is easier for
-    // regionck to be sure that it has found *all* the region
-    // obligations (otherwise, it's easy to fail to walk to a
-    // particular node-id).
-    region_obligations: RefCell<NodeMap<Vec<RegionObligation<'tcx>>>>,
-
     // Tracks trait obligations incurred during this function body.
     fulfillment_cx: RefCell<traits::FulfillmentContext<'tcx>>,
 }
 
-struct RegionObligation<'tcx> {
-    sub_region: ty::Region,
-    sup_type: Ty<'tcx>,
-    origin: infer::SubregionOrigin<'tcx>,
-}
-
 /// When type-checking an expression, we propagate downward
 /// whatever type hint we are able in the form of an `Expectation`.
 enum Expectation<'tcx> {
@@ -328,7 +296,6 @@ impl<'a, 'tcx> Inherited<'a, 'tcx> {
             upvar_borrow_map: RefCell::new(FnvHashMap::new()),
             unboxed_closures: RefCell::new(DefIdMap::new()),
             fn_sig_map: RefCell::new(NodeMap::new()),
-            region_obligations: RefCell::new(NodeMap::new()),
             fulfillment_cx: RefCell::new(traits::FulfillmentContext::new()),
         }
     }
@@ -1762,8 +1729,10 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
 
                 // If the type is `Foo+'a`, ensures that the type
                 // being cast to `Foo+'a` outlives `'a`:
-                let origin = infer::RelateObjectBound(span);
-                self.register_region_obligation(origin, self_ty, ty_trait.bounds.region_bound);
+                let cause = traits::ObligationCause { span: span,
+                                                      body_id: self.body_id,
+                                                      code: traits::ObjectCastObligation(self_ty) };
+                self.register_region_obligation(self_ty, ty_trait.bounds.region_bound, cause);
             }
         }
     }
@@ -1790,8 +1759,8 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         self.add_obligations_for_parameters(
             traits::ObligationCause::new(
                 span,
+                self.body_id,
                 traits::ItemObligation(def_id)),
-            &substs,
             &bounds);
         let monotype =
             polytype.ty.subst(self.tcx(), &substs);
@@ -1815,14 +1784,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, 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,
@@ -1840,15 +1805,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::Obligation<'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> {
@@ -1983,19 +1957,12 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     /// Registers an obligation for checking later, during regionck, that the type `ty` must
     /// outlive the region `r`.
     pub fn register_region_obligation(&self,
-                                      origin: infer::SubregionOrigin<'tcx>,
                                       ty: Ty<'tcx>,
-                                      r: ty::Region)
+                                      region: ty::Region,
+                                      cause: traits::ObligationCause<'tcx>)
     {
-        let mut region_obligations = self.inh.region_obligations.borrow_mut();
-        let region_obligation = RegionObligation { sub_region: r,
-                                                   sup_type: ty,
-                                                   origin: origin };
-
-        match region_obligations.entry(self.body_id) {
-            Vacant(entry) => { entry.set(vec![region_obligation]); },
-            Occupied(mut entry) => { entry.get_mut().push(region_obligation); },
-        }
+        let mut fulfillment_cx = self.inh.fulfillment_cx.borrow_mut();
+        fulfillment_cx.register_region_obligation(self.tcx(), ty, region, cause);
     }
 
     pub fn add_default_region_param_bounds(&self,
@@ -2004,8 +1971,9 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     {
         for &ty in substs.types.iter() {
             let default_bound = ty::ReScope(CodeExtent::from_node_id(expr.id));
-            let origin = infer::RelateDefaultParamBound(expr.span, ty);
-            self.register_region_obligation(origin, ty, default_bound);
+            let cause = traits::ObligationCause::new(expr.span, self.body_id,
+                                                     traits::MiscObligation);
+            self.register_region_obligation(ty, default_bound, cause);
         }
     }
 
@@ -2029,90 +1997,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);
-    }
-
-    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);
-        }
-    }
+        let obligations = traits::predicates_for_generics(self.tcx(),
+                                                          cause,
+                                                          generic_bounds);
 
-    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 origin = infer::RelateParamBound(span, ty);
-            self.register_region_obligation(origin, ty, r);
-        }
-    }
-
-    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));
     }
 }
 
@@ -4065,6 +3961,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),
@@ -5197,8 +5096,7 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
     debug!("after late-bounds have been replaced: bounds={}", bounds.repr(fcx.tcx()));
 
     fcx.add_obligations_for_parameters(
-        traits::ObligationCause::new(span, traits::ItemObligation(def.def_id())),
-        &substs,
+        traits::ObligationCause::new(span, fcx.body_id, traits::ItemObligation(def.def_id())),
         &bounds);
 
     // Substitute the values for the type parameters into the type of
@@ -5832,11 +5730,3 @@ pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &ast::ForeignItem) {
     }
 }
 
-impl<'tcx> Repr<'tcx> for RegionObligation<'tcx> {
-    fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
-        format!("RegionObligation(sub_region={}, sup_type={}, origin={})",
-                self.sub_region.repr(tcx),
-                self.sup_type.repr(tcx),
-                self.origin.repr(tcx))
-    }
-}
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 80ee2cce4ce..cadcee43b44 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -353,18 +353,13 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
     fn visit_region_obligations(&mut self, node_id: ast::NodeId)
     {
         debug!("visit_region_obligations: node_id={}", node_id);
-        let region_obligations = self.fcx.inh.region_obligations.borrow();
-        match region_obligations.get(&node_id) {
-            None => { }
-            Some(vec) => {
-                for r_o in vec.iter() {
-                    debug!("visit_region_obligations: r_o={}",
-                           r_o.repr(self.tcx()));
-                    let sup_type = self.resolve_type(r_o.sup_type);
-                    type_must_outlive(self, r_o.origin.clone(),
-                                      sup_type, r_o.sub_region);
-                }
-            }
+        let fulfillment_cx = self.fcx.inh.fulfillment_cx.borrow();
+        for r_o in fulfillment_cx.region_obligations(node_id).iter() {
+            debug!("visit_region_obligations: r_o={}",
+                   r_o.repr(self.tcx()));
+            let sup_type = self.resolve_type(r_o.sup_type);
+            let origin = infer::RelateRegionParamBound(r_o.cause.span);
+            type_must_outlive(self, origin, sup_type, r_o.sub_region);
         }
     }
 
@@ -937,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 cause = traits::ObligationCause::new(freevar.span, 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)
-                }
+                let code = traits::ClosureCapture(var_node_id, expr.span, builtin_bound);
+                let cause = traits::ObligationCause::new(freevar.span, rcx.fcx.body_id, code);
+                rcx.fcx.register_builtin_bound(var_ty, builtin_bound, cause);
             }
             type_must_outlive(
                 rcx, infer::RelateProcBound(expr.span, var_node_id, var_ty),
@@ -1864,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 80363055a4b..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, obligation_for_builtin_bound};
+use middle::traits::{Obligation, ObligationCause};
 use middle::traits::{FulfillmentError, CodeSelectionError, CodeAmbiguity};
-use middle::traits::{ObligationCause};
+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, 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.
@@ -287,24 +278,20 @@ pub fn register_object_cast_obligations<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
     let object_obligation =
         Obligation::new(
             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,
-                                     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
@@ -323,17 +310,6 @@ pub fn select_all_fcx_obligations_or_error(fcx: &FnCtxt) {
     }
 }
 
-fn resolve_trait_ref<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>, obligation: &Obligation<'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() {
@@ -354,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: &Obligation<'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;
@@ -378,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);
             }
@@ -411,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: &Obligation<'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()),
@@ -473,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()
@@ -500,9 +545,8 @@ pub fn select_new_fcx_obligations(fcx: &FnCtxt) {
 }
 
 fn note_obligation_cause<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
-                                   obligation: &Obligation<'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) => {
@@ -510,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 => {
@@ -558,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 a011982a1fc..8c82429e1c2 100644
--- a/src/librustc_typeck/check/wf.rs
+++ b/src/librustc_typeck/check/wf.rs
@@ -91,7 +91,6 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
         let polytype = ty::lookup_item_type(ccx.tcx, item_def_id);
         let param_env =
             ty::construct_parameter_environment(ccx.tcx,
-                                                item.span,
                                                 &polytype.generics,
                                                 item.id);
         let inh = Inherited::new(ccx.tcx, param_env);
@@ -122,14 +121,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, 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));
                     }
                 }
             }
@@ -218,33 +215,16 @@ 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,
+                    fcx.body_id,
                     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));
             }
         });
     }
@@ -291,8 +271,8 @@ impl<'cx,'tcx> BoundsChecker<'cx,'tcx> {
         self.fcx.add_obligations_for_parameters(
             traits::ObligationCause::new(
                 self.span,
+                self.fcx.body_id,
                 traits::ItemObligation(trait_ref.def_id)),
-            &trait_ref.substs,
             &bounds);
 
         for &ty in trait_ref.substs.types.iter() {
@@ -341,8 +321,8 @@ impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
                 if self.binding_count == 0 {
                     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));
                 } else {
                     // There are two circumstances in which we ignore
@@ -367,11 +347,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);
@@ -458,6 +440,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
 
@@ -469,14 +469,8 @@ fn check_struct_safe_for_destructor<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
     if !struct_tpt.generics.has_type_params(subst::TypeSpace)
         && !struct_tpt.generics.has_region_params(subst::TypeSpace)
     {
-        let cause = traits::ObligationCause::new(span, 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);
-        }
+        let cause = traits::ObligationCause::new(span, fcx.body_id, traits::DropTrait);
+        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 6b7f08e8104..09cf7080476 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -1407,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(_) => {
@@ -1596,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,
@@ -1644,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
@@ -1654,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
 }
 
@@ -1806,6 +1811,10 @@ fn ty_generics<'tcx,AC>(this: &AC,
         result.types.push(space, (*associated_type_param).clone());
     }
 
+    // Just for fun, also push the bounds from the type parameters
+    // into the predicates list. This is currently kind of non-DRY.
+    create_predicates(this.tcx(), &mut result, space);
+
     return result;
 
     fn create_type_parameters_for_associated_types<'tcx, AC>(
@@ -1892,6 +1901,27 @@ fn ty_generics<'tcx,AC>(this: &AC,
             }
         }
     }
+
+    fn create_predicates<'tcx>(
+        tcx: &ty::ctxt<'tcx>,
+        result: &mut ty::Generics<'tcx>,
+        space: subst::ParamSpace)
+    {
+        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 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));
+            }
+        }
+    }
 }
 
 fn get_or_create_type_parameter_def<'tcx,AC>(this: &AC,
@@ -2145,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/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index b83bbd6b4c0..41ed5b8ec36 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -160,8 +160,11 @@ fn lookup_def_ccx(ccx: &CrateCtxt, sp: Span, id: ast::NodeId)
 
 fn no_params<'tcx>(t: Ty<'tcx>) -> ty::Polytype<'tcx> {
     ty::Polytype {
-        generics: ty::Generics {types: VecPerParamSpace::empty(),
-                                regions: VecPerParamSpace::empty()},
+        generics: ty::Generics {
+            types: VecPerParamSpace::empty(),
+            regions: VecPerParamSpace::empty(),
+            predicates: VecPerParamSpace::empty(),
+        },
         ty: t
     }
 }
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/opt-out-copy-bad.rs b/src/test/compile-fail/opt-out-copy-bad.rs
new file mode 100644
index 00000000000..80f8a154d58
--- /dev/null
+++ b/src/test/compile-fail/opt-out-copy-bad.rs
@@ -0,0 +1,42 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(opt_out_copy)]
+
+// Test that when using the `opt-out-copy` feature we still consider
+// destructors to be non-movable
+
+struct CantCopyThis;
+
+impl Drop for CantCopyThis {
+    fn drop(&mut self) { }
+}
+
+struct IWantToCopyThis {
+    but_i_cant: CantCopyThis,
+}
+
+impl Copy for IWantToCopyThis {}
+//~^ ERROR the trait `Copy` may not be implemented for this type
+
+enum CantCopyThisEither {
+    A,
+    B(::std::kinds::marker::NoCopy),
+}
+
+enum IWantToCopyThisToo {
+    ButICant(CantCopyThisEither),
+}
+
+impl Copy for IWantToCopyThisToo {}
+//~^ ERROR the trait `Copy` may not be implemented for this type
+
+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>();
 }