auto merge of #17466 : nikomatsakis/rust/oibt, r=pcwalton

Moves the vast majority of builtin bound checking out of type contents and into the trait system.

This is a preliminary step for a lot of follow-on work:

- opt-in builtin types, obviously
- generalized where clauses, because TypeContents has this notion that a type parameter has a single set of builtin kinds, but with where clauses it depends on context
- generalized coherence, because this adds support for recursive trait selection

Unfortunately I wasn't able to completely remove Type Contents from the front-end checking in this PR. It's still used by EUV to decide what gets moved and what doesn't.

r? @pcwalton 

46 files changed, 1193 insertions, 1112 deletions

diff --git a/src/doc/guide-unsafe.md b/src/doc/guide-unsafe.md
index ba79e828150..1e67c8a13e9 100644
--- a/src/doc/guide-unsafe.md
+++ b/src/doc/guide-unsafe.md
@@ -466,7 +466,7 @@ fn start(_argc: int, _argv: *const *const u8) -> int {
 // provided by libstd.
 #[lang = "stack_exhausted"] extern fn stack_exhausted() {}
 #[lang = "eh_personality"] extern fn eh_personality() {}
-#[lang = "sized"] trait Sized { }
+#[lang = "fail_fmt"] fn fail_fmt() -> ! { loop {} }
 # // fn main() {} tricked you, rustdoc!
 ```
 
@@ -489,32 +489,28 @@ pub extern fn main(argc: int, argv: *const *const u8) -> int {
 
 #[lang = "stack_exhausted"] extern fn stack_exhausted() {}
 #[lang = "eh_personality"] extern fn eh_personality() {}
-#[lang = "sized"] trait Sized { }
+#[lang = "fail_fmt"] fn fail_fmt() -> ! { loop {} }
 # // fn main() {} tricked you, rustdoc!
 ```
 
 
 The compiler currently makes a few assumptions about symbols which are available
 in the executable to call. Normally these functions are provided by the standard
-xlibrary, but without it you must define your own.
+library, but without it you must define your own.
 
-The first of these two functions, `stack_exhausted`, is invoked whenever stack
+The first of these three functions, `stack_exhausted`, is invoked whenever stack
 overflow is detected.  This function has a number of restrictions about how it
 can be called and what it must do, but if the stack limit register is not being
 maintained then a task always has an "infinite stack" and this function
 shouldn't get triggered.
 
-The second of these two functions, `eh_personality`, is used by the failure
-mechanisms of the compiler. This is often mapped to GCC's personality function
-(see the [libstd implementation](std/rt/unwind/index.html) for more
-information), but crates which do not trigger failure can be assured that this
-function is never called.
-
-The final item in the example is a trait called `Sized`. This a trait
-that represents data of a known static size: it is integral to the
-Rust type system, and so the compiler expects the standard library to
-provide it. Since you are not using the standard library, you have to
-provide it yourself.
+The second of these three functions, `eh_personality`, is used by the
+failure mechanisms of the compiler. This is often mapped to GCC's
+personality function (see the
+[libstd implementation](std/rt/unwind/index.html) for more
+information), but crates which do not trigger failure can be assured
+that this function is never called. The final function, `fail_fmt`, is
+also used by the failure mechanisms of the compiler.
 
 ## Using libcore
 
@@ -694,7 +690,7 @@ fn main(argc: int, argv: *const *const u8) -> int {
 
 #[lang = "stack_exhausted"] extern fn stack_exhausted() {}
 #[lang = "eh_personality"] extern fn eh_personality() {}
-#[lang = "sized"] trait Sized {}
+#[lang = "fail_fmt"] fn fail_fmt() -> ! { loop {} }
 ```
 
 Note the use of `abort`: the `exchange_malloc` lang item is assumed to
diff --git a/src/libcore/kinds.rs b/src/libcore/kinds.rs
index 0a1334e5d13..b0206e73e47 100644
--- a/src/libcore/kinds.rs
+++ b/src/libcore/kinds.rs
@@ -25,19 +25,19 @@ pub use self::Sync as Share;
 
 /// Types able to be transferred across task boundaries.
 #[lang="send"]
-pub trait Send {
+pub trait Send for Sized? {
     // empty.
 }
 
 /// Types with a constant size known at compile-time.
 #[lang="sized"]
-pub trait Sized {
+pub trait Sized for Sized? {
     // Empty.
 }
 
 /// Types that can be copied by simply copying bits (i.e. `memcpy`).
 #[lang="copy"]
-pub trait Copy {
+pub trait Copy for Sized? {
     // Empty.
 }
 
@@ -87,7 +87,7 @@ pub trait Copy {
 /// reference; not doing this is undefined behaviour (for example,
 /// `transmute`-ing from `&T` to `&mut T` is illegal).
 #[lang="sync"]
-pub trait Sync {
+pub trait Sync for Sized? {
     // Empty
 }
 
diff --git a/src/liblibc/lib.rs b/src/liblibc/lib.rs
index 494c98bc54d..eabc02e3e26 100644
--- a/src/liblibc/lib.rs
+++ b/src/liblibc/lib.rs
@@ -79,6 +79,8 @@
 #![allow(missing_doc)]
 #![allow(non_snake_case)]
 
+extern crate core;
+
 #[cfg(test)] extern crate std;
 #[cfg(test)] extern crate test;
 #[cfg(test)] extern crate native;
diff --git a/src/librustc/diagnostics.rs b/src/librustc/diagnostics.rs
index 20842beae16..36ba28dfc2a 100644
--- a/src/librustc/diagnostics.rs
+++ b/src/librustc/diagnostics.rs
@@ -58,8 +58,6 @@ register_diagnostics!(
     E0039,
     E0040,
     E0041,
-    E0042,
-    E0043,
     E0044,
     E0045,
     E0046,
@@ -92,7 +90,6 @@ register_diagnostics!(
     E0075,
     E0076,
     E0077,
-    E0078,
     E0079,
     E0080,
     E0081,
@@ -130,7 +127,6 @@ register_diagnostics!(
     E0121,
     E0122,
     E0124,
-    E0125,
     E0126,
     E0127,
     E0128,
@@ -147,12 +143,6 @@ register_diagnostics!(
     E0139,
     E0140,
     E0141,
-    E0143,
-    E0144,
-    E0145,
-    E0146,
-    E0148,
-    E0151,
     E0152,
     E0153,
     E0154,
diff --git a/src/librustc/driver/driver.rs b/src/librustc/driver/driver.rs
index 4ff9133c8a5..33e6579fb87 100644
--- a/src/librustc/driver/driver.rs
+++ b/src/librustc/driver/driver.rs
@@ -17,7 +17,7 @@ use lint;
 use llvm::{ContextRef, ModuleRef};
 use metadata::common::LinkMeta;
 use metadata::creader;
-use middle::{trans, stability, kind, ty, typeck, reachable};
+use middle::{trans, stability, ty, typeck, reachable};
 use middle::dependency_format;
 use middle;
 use plugin::load::Plugins;
@@ -462,8 +462,12 @@ pub fn phase_3_run_analysis_passes<'tcx>(sess: Session,
     time(time_passes, "rvalue checking", (), |_|
          middle::check_rvalues::check_crate(&ty_cx, krate));
 
-    time(time_passes, "kind checking", (), |_|
-         kind::check_crate(&ty_cx));
+    // Avoid overwhelming user with errors if type checking failed.
+    // I'm not sure how helpful this is, to be honest, but it avoids a
+    // lot of annoying errors in the compile-fail tests (basically,
+    // lint warnings and so on -- kindck used to do this abort, but
+    // kindck is gone now). -nmatsakis
+    ty_cx.sess.abort_if_errors();
 
     let reachable_map =
         time(time_passes, "reachability checking", (), |_|
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 2994954c3d7..c67f673879e 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -95,7 +95,6 @@ pub mod middle {
     pub mod expr_use_visitor;
     pub mod graph;
     pub mod intrinsicck;
-    pub mod kind;
     pub mod lang_items;
     pub mod liveness;
     pub mod mem_categorization;
diff --git a/src/librustc/middle/kind.rs b/src/librustc/middle/kind.rs
deleted file mode 100644
index f5d4ece3bcc..00000000000
--- a/src/librustc/middle/kind.rs
+++ /dev/null
@@ -1,404 +0,0 @@
-// Copyright 2012-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.
-
-use middle::mem_categorization::Typer;
-use middle::subst;
-use middle::ty;
-use middle::ty_fold::TypeFoldable;
-use middle::ty_fold;
-use util::ppaux::{ty_to_string};
-use util::ppaux::UserString;
-
-use syntax::ast::*;
-use syntax::attr;
-use syntax::codemap::Span;
-use syntax::print::pprust::{expr_to_string, ident_to_string};
-use syntax::visit::Visitor;
-use syntax::visit;
-
-// Kind analysis pass. This pass does some ad-hoc checks that are more
-// convenient to do after type checking is complete and all checks are
-// known. These are generally related to the builtin bounds `Copy` and
-// `Sized`. Note that many of the builtin bound properties that used
-// to be checked here are actually checked by trait checking these
-// days.
-
-pub struct Context<'a,'tcx:'a> {
-    tcx: &'a ty::ctxt<'tcx>,
-}
-
-impl<'a, 'tcx, 'v> Visitor<'v> for Context<'a, 'tcx> {
-    fn visit_expr(&mut self, ex: &Expr) {
-        check_expr(self, ex);
-    }
-
-    fn visit_fn(&mut self, fk: visit::FnKind, fd: &'v FnDecl,
-                b: &'v Block, s: Span, n: NodeId) {
-        check_fn(self, fk, fd, b, s, n);
-    }
-
-    fn visit_ty(&mut self, t: &Ty) {
-        check_ty(self, t);
-    }
-
-    fn visit_item(&mut self, i: &Item) {
-        check_item(self, i);
-    }
-
-    fn visit_pat(&mut self, p: &Pat) {
-        check_pat(self, p);
-    }
-}
-
-pub fn check_crate(tcx: &ty::ctxt) {
-    let mut ctx = Context {
-        tcx: tcx,
-    };
-    visit::walk_crate(&mut ctx, tcx.map.krate());
-    tcx.sess.abort_if_errors();
-}
-
-struct EmptySubstsFolder<'a, 'tcx: 'a> {
-    tcx: &'a ty::ctxt<'tcx>
-}
-impl<'a, 'tcx> ty_fold::TypeFolder<'tcx> for EmptySubstsFolder<'a, 'tcx> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
-        self.tcx
-    }
-    fn fold_substs(&mut self, _: &subst::Substs) -> subst::Substs {
-        subst::Substs::empty()
-    }
-}
-
-fn check_struct_safe_for_destructor(cx: &mut Context,
-                                    span: Span,
-                                    struct_did: DefId) {
-    let struct_tpt = ty::lookup_item_type(cx.tcx, struct_did);
-    if !struct_tpt.generics.has_type_params(subst::TypeSpace)
-      && !struct_tpt.generics.has_region_params(subst::TypeSpace) {
-        let mut folder = EmptySubstsFolder { tcx: cx.tcx };
-        if !ty::type_is_sendable(cx.tcx, struct_tpt.ty.fold_with(&mut folder)) {
-            span_err!(cx.tcx.sess, span, E0125,
-                      "cannot implement a destructor on a \
-                       structure or enumeration that does not satisfy Send");
-            span_note!(cx.tcx.sess, span,
-                       "use \"#[unsafe_destructor]\" on the implementation \
-                        to force the compiler to allow this");
-        }
-    } else {
-        span_err!(cx.tcx.sess, span, E0141,
-                  "cannot implement a destructor on a structure \
-                   with type parameters");
-        span_note!(cx.tcx.sess, span,
-                   "use \"#[unsafe_destructor]\" on the implementation \
-                    to force the compiler to allow this");
-    }
-}
-
-fn check_impl_of_trait(cx: &mut Context, it: &Item, trait_ref: &TraitRef, self_type: &Ty) {
-    let ast_trait_def = *cx.tcx.def_map.borrow()
-                              .find(&trait_ref.ref_id)
-                              .expect("trait ref not in def map!");
-    let trait_def_id = ast_trait_def.def_id();
-
-    // If this is a destructor, check kinds.
-    if cx.tcx.lang_items.drop_trait() == Some(trait_def_id) &&
-        !attr::contains_name(it.attrs.as_slice(), "unsafe_destructor")
-    {
-        match self_type.node {
-            TyPath(_, ref bounds, path_node_id) => {
-                assert!(bounds.is_none());
-                let struct_def = cx.tcx.def_map.borrow().get_copy(&path_node_id);
-                let struct_did = struct_def.def_id();
-                check_struct_safe_for_destructor(cx, self_type.span, struct_did);
-            }
-            _ => {
-                cx.tcx.sess.span_bug(self_type.span,
-                    "the self type for the Drop trait impl is not a path");
-            }
-        }
-    }
-}
-
-fn check_item(cx: &mut Context, item: &Item) {
-    match item.node {
-        ItemImpl(_, Some(ref trait_ref), ref self_type, _) => {
-            check_impl_of_trait(cx, item, trait_ref, &**self_type);
-        }
-        _ => {}
-    }
-
-    visit::walk_item(cx, item)
-}
-
-// Yields the appropriate function to check the kind of closed over
-// variables. `id` is the NodeId for some expression that creates the
-// closure.
-fn with_appropriate_checker(cx: &Context,
-                            id: NodeId,
-                            fn_span: Span,
-                            b: |checker: |&Context, &ty::Freevar||) {
-    fn check_for_uniq(cx: &Context,
-                      fn_span: Span,
-                      fv: &ty::Freevar,
-                      bounds: ty::BuiltinBounds) {
-        // all captured data must be owned, regardless of whether it is
-        // moved in or copied in.
-        let id = fv.def.def_id().node;
-        let var_t = ty::node_id_to_type(cx.tcx, id);
-
-        check_freevar_bounds(cx, fn_span, fv.span, var_t, bounds, None);
-    }
-
-    fn check_for_block(cx: &Context,
-                       fn_span: Span,
-                       fn_id: NodeId,
-                       fv: &ty::Freevar,
-                       bounds: ty::BuiltinBounds) {
-        let id = fv.def.def_id().node;
-        let var_t = ty::node_id_to_type(cx.tcx, id);
-        let upvar_id = ty::UpvarId { var_id: id, closure_expr_id: fn_id };
-        let upvar_borrow = cx.tcx.upvar_borrow(upvar_id);
-        let implicit_borrowed_type =
-            ty::mk_rptr(cx.tcx,
-                        upvar_borrow.region,
-                        ty::mt { mutbl: upvar_borrow.kind.to_mutbl_lossy(),
-                                 ty: var_t });
-        check_freevar_bounds(cx, fn_span, fv.span, implicit_borrowed_type,
-                             bounds, Some(var_t));
-    }
-
-    fn check_for_bare(cx: &Context, fv: &ty::Freevar) {
-        span_err!(cx.tcx.sess, fv.span, E0143,
-                  "can't capture dynamic environment in a fn item; \
-                   use the || {} closure form instead", "{ ... }");
-    } // same check is done in resolve.rs, but shouldn't be done
-
-    let fty = ty::node_id_to_type(cx.tcx, id);
-    match ty::get(fty).sty {
-        ty::ty_closure(box ty::ClosureTy {
-            store: ty::UniqTraitStore,
-            bounds: bounds,
-            ..
-        }) => {
-            b(|cx, fv| check_for_uniq(cx, fn_span, fv,
-                                      bounds.builtin_bounds))
-        }
-
-        ty::ty_closure(box ty::ClosureTy {
-            store: ty::RegionTraitStore(..), bounds, ..
-        }) => {
-            b(|cx, fv| check_for_block(cx, fn_span, id, fv,
-                                       bounds.builtin_bounds))
-        }
-
-        ty::ty_bare_fn(_) => {
-            b(check_for_bare)
-        }
-
-        ty::ty_unboxed_closure(..) => {}
-
-        ref s => {
-            cx.tcx.sess.bug(format!("expect fn type in kind checker, not \
-                                     {:?}",
-                                    s).as_slice());
-        }
-    }
-}
-
-// Check that the free variables used in a shared/sendable closure conform
-// to the copy/move kind bounds. Then recursively check the function body.
-fn check_fn(
-    cx: &mut Context,
-    fk: visit::FnKind,
-    decl: &FnDecl,
-    body: &Block,
-    sp: Span,
-    fn_id: NodeId) {
-
-    // <Check kinds on free variables:
-    with_appropriate_checker(cx, fn_id, sp, |chk| {
-        ty::with_freevars(cx.tcx, fn_id, |freevars| {
-            for fv in freevars.iter() {
-                chk(cx, fv);
-            }
-        });
-    });
-
-    match fk {
-        visit::FkFnBlock(..) => {
-            visit::walk_fn(cx, fk, decl, body, sp)
-        }
-        visit::FkItemFn(..) | visit::FkMethod(..) => {
-            visit::walk_fn(cx, fk, decl, body, sp);
-        }
-    }
-}
-
-pub fn check_expr(cx: &mut Context, e: &Expr) {
-    debug!("kind::check_expr({})", expr_to_string(e));
-
-    match e.node {
-        ExprRepeat(ref element, ref count_expr) => {
-            let count = ty::eval_repeat_count(cx.tcx, &**count_expr);
-            if count > 1 {
-                let element_ty = ty::expr_ty(cx.tcx, &**element);
-                check_copy(cx, element_ty, element.span,
-                           "repeated element will be copied");
-            }
-        }
-        ExprAssign(ref lhs, _) |
-        ExprAssignOp(_, ref lhs, _) => {
-            let lhs_ty = ty::expr_ty(cx.tcx, &**lhs);
-            if !ty::type_is_sized(cx.tcx, lhs_ty) {
-                cx.tcx.sess.span_err(lhs.span, "dynamically sized type on lhs of assignment");
-            }
-        }
-        ExprStruct(..) => {
-            let e_ty = ty::expr_ty(cx.tcx, e);
-            if !ty::type_is_sized(cx.tcx, e_ty) {
-                cx.tcx.sess.span_err(e.span, "trying to initialise a dynamically sized struct");
-            }
-        }
-        _ => {}
-    }
-
-    visit::walk_expr(cx, e);
-}
-
-fn check_ty(cx: &mut Context, aty: &Ty) {
-    match aty.node {
-        TyPath(_, _, id) => {
-            match cx.tcx.item_substs.borrow().find(&id) {
-                None => {}
-                Some(ref item_substs) => {
-                    let def_map = cx.tcx.def_map.borrow();
-                    let did = def_map.get_copy(&id).def_id();
-                    let generics = ty::lookup_item_type(cx.tcx, did).generics;
-                    for def in generics.types.iter() {
-                        let ty = *item_substs.substs.types.get(def.space,
-                                                               def.index);
-                        check_typaram_bounds(cx, aty.span, ty, def);
-                    }
-                }
-            }
-        }
-        _ => {}
-    }
-
-    visit::walk_ty(cx, aty);
-}
-
-// Calls "any_missing" if any bounds were missing.
-pub fn check_builtin_bounds(cx: &Context,
-                            ty: ty::t,
-                            bounds: ty::BuiltinBounds,
-                            any_missing: |ty::BuiltinBounds|) {
-    let kind = ty::type_contents(cx.tcx, ty);
-    let mut missing = ty::empty_builtin_bounds();
-    for bound in bounds.iter() {
-        if !kind.meets_builtin_bound(cx.tcx, bound) {
-            missing.add(bound);
-        }
-    }
-    if !missing.is_empty() {
-        any_missing(missing);
-    }
-}
-
-pub fn check_typaram_bounds(cx: &Context,
-                            sp: Span,
-                            ty: ty::t,
-                            type_param_def: &ty::TypeParameterDef) {
-    check_builtin_bounds(cx,
-                         ty,
-                         type_param_def.bounds.builtin_bounds,
-                         |missing| {
-        span_err!(cx.tcx.sess, sp, E0144,
-                  "instantiating a type parameter with an incompatible type \
-                   `{}`, which does not fulfill `{}`",
-                   ty_to_string(cx.tcx, ty),
-                   missing.user_string(cx.tcx));
-    });
-}
-
-pub fn check_freevar_bounds(cx: &Context, fn_span: Span, sp: Span, ty: ty::t,
-                            bounds: ty::BuiltinBounds, referenced_ty: Option<ty::t>)
-{
-    check_builtin_bounds(cx, ty, bounds, |missing| {
-        // Will be Some if the freevar is implicitly borrowed (stack closure).
-        // Emit a less mysterious error message in this case.
-        match referenced_ty {
-            Some(rty) => {
-                span_err!(cx.tcx.sess, sp, E0145,
-                    "cannot implicitly borrow variable of type `{}` in a \
-                     bounded stack closure (implicit reference does not fulfill `{}`)",
-                    ty_to_string(cx.tcx, rty), missing.user_string(cx.tcx));
-            }
-            None => {
-                span_err!(cx.tcx.sess, sp, E0146,
-                    "cannot capture variable of type `{}`, which does \
-                     not fulfill `{}`, in a bounded closure",
-                    ty_to_string(cx.tcx, ty), missing.user_string(cx.tcx));
-            }
-        }
-        span_note!(cx.tcx.sess, fn_span,
-            "this closure's environment must satisfy `{}`",
-            bounds.user_string(cx.tcx));
-    });
-}
-
-fn check_copy(cx: &Context, ty: ty::t, sp: Span, reason: &str) {
-    debug!("type_contents({})={}",
-           ty_to_string(cx.tcx, ty),
-           ty::type_contents(cx.tcx, ty).to_string());
-    if ty::type_moves_by_default(cx.tcx, ty) {
-        span_err!(cx.tcx.sess, sp, E0148,
-            "copying a value of non-copyable type `{}`",
-            ty_to_string(cx.tcx, ty));
-        span_note!(cx.tcx.sess, sp, "{}", reason.as_slice());
-    }
-}
-
-// Ensure that `ty` has a statically known size (i.e., it has the `Sized` bound).
-fn check_sized(tcx: &ty::ctxt, ty: ty::t, name: String, sp: Span) {
-    if !ty::type_is_sized(tcx, ty) {
-        span_err!(tcx.sess, sp, E0151,
-            "variable `{}` has dynamically sized type `{}`",
-            name, ty_to_string(tcx, ty));
-    }
-}
-
-// Check that any variables in a pattern have types with statically known size.
-fn check_pat(cx: &mut Context, pat: &Pat) {
-    let var_name = match pat.node {
-        PatWild(PatWildSingle) => Some("_".to_string()),
-        PatIdent(_, ref path1, _) => Some(ident_to_string(&path1.node).to_string()),
-        _ => None
-    };
-
-    match var_name {
-        Some(name) => {
-            let types = cx.tcx.node_types.borrow();
-            let ty = types.find(&(pat.id as uint));
-            match ty {
-                Some(ty) => {
-                    debug!("kind: checking sized-ness of variable {}: {}",
-                           name, ty_to_string(cx.tcx, *ty));
-                    check_sized(cx.tcx, *ty, name, pat.span);
-                }
-                None => {} // extern fn args
-            }
-        }
-        None => {}
-    }
-
-    visit::walk_pat(cx, pat);
-}
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index 415eed380fc..9b179d3e895 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -10,9 +10,9 @@
 
 /*! See `doc.rs` for high-level documentation */
 
-use super::DUMMY_CAUSE;
 use super::{EvaluatedToMatch, EvaluatedToAmbiguity, EvaluatedToUnmatch};
 use super::{evaluate_impl};
+use super::ObligationCause;
 use super::util;
 
 use middle::subst;
@@ -21,7 +21,6 @@ use middle::ty;
 use middle::typeck::infer::InferCtxt;
 use syntax::ast;
 use syntax::codemap::DUMMY_SP;
-use util::nodemap::DefIdMap;
 use util::ppaux::Repr;
 
 pub fn impl_can_satisfy(infcx: &InferCtxt,
@@ -40,8 +39,7 @@ pub fn impl_can_satisfy(infcx: &InferCtxt,
     // Determine whether `impl2` can provide an implementation for those
     // same types.
     let param_env = ty::empty_parameter_environment();
-    let unboxed_closures = DefIdMap::new();
-    match evaluate_impl(infcx, &param_env, &unboxed_closures, DUMMY_CAUSE,
+    match evaluate_impl(infcx, &param_env, infcx.tcx, ObligationCause::dummy(),
                         impl2_def_id, impl1_self_ty) {
         EvaluatedToMatch | EvaluatedToAmbiguity => true,
         EvaluatedToUnmatch => false,
diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index e7b1053b358..c0caa1d7c79 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -8,9 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use middle::mem_categorization::Typer;
 use middle::ty;
-use middle::typeck::infer::{InferCtxt, skolemize};
-use util::nodemap::DefIdMap;
+use middle::typeck::infer::InferCtxt;
 use util::ppaux::Repr;
 
 use super::CodeAmbiguity;
@@ -18,7 +18,6 @@ use super::Obligation;
 use super::FulfillmentError;
 use super::CodeSelectionError;
 use super::select::SelectionContext;
-use super::Unimplemented;
 
 /**
  * The fulfillment context is used to drive trait resolution.  It
@@ -36,17 +35,12 @@ pub struct FulfillmentContext {
     // A list of all obligations that have been registered with this
     // fulfillment context.
     trait_obligations: Vec<Obligation>,
-
-    // For semi-hacky reasons (see FIXME below) we keep the builtin
-    // trait obligations segregated.
-    builtin_obligations: Vec<Obligation>,
 }
 
 impl FulfillmentContext {
     pub fn new() -> FulfillmentContext {
         FulfillmentContext {
             trait_obligations: Vec::new(),
-            builtin_obligations: Vec::new()
         }
     }
 
@@ -55,24 +49,16 @@ impl FulfillmentContext {
                                obligation: Obligation)
     {
         debug!("register_obligation({})", obligation.repr(tcx));
-        match tcx.lang_items.to_builtin_kind(obligation.trait_ref.def_id) {
-            Some(_) => {
-                self.builtin_obligations.push(obligation);
-            }
-            None => {
-                self.trait_obligations.push(obligation);
-            }
-        }
+        self.trait_obligations.push(obligation);
     }
 
-    pub fn select_all_or_error(&mut self,
-                               infcx: &InferCtxt,
-                               param_env: &ty::ParameterEnvironment,
-                               unboxed_closures: &DefIdMap<ty::UnboxedClosure>)
-                               -> Result<(),Vec<FulfillmentError>>
+    pub fn select_all_or_error<'a,'tcx>(&mut self,
+                                        infcx: &InferCtxt<'a,'tcx>,
+                                        param_env: &ty::ParameterEnvironment,
+                                        typer: &Typer<'tcx>)
+                                        -> Result<(),Vec<FulfillmentError>>
     {
-        try!(self.select_where_possible(infcx, param_env,
-                                        unboxed_closures));
+        try!(self.select_where_possible(infcx, param_env, typer));
 
         // Anything left is ambiguous.
         let errors: Vec<FulfillmentError> =
@@ -88,15 +74,14 @@ impl FulfillmentContext {
         }
     }
 
-    pub fn select_where_possible(&mut self,
-                                 infcx: &InferCtxt,
-                                 param_env: &ty::ParameterEnvironment,
-                                 unboxed_closures: &DefIdMap<ty::UnboxedClosure>)
-                                 -> Result<(),Vec<FulfillmentError>>
+    pub fn select_where_possible<'a,'tcx>(&mut self,
+                                          infcx: &InferCtxt<'a,'tcx>,
+                                          param_env: &ty::ParameterEnvironment,
+                                          typer: &Typer<'tcx>)
+                                          -> Result<(),Vec<FulfillmentError>>
     {
         let tcx = infcx.tcx;
-        let selcx = SelectionContext::new(infcx, param_env,
-                                          unboxed_closures);
+        let mut selcx = SelectionContext::new(infcx, param_env, typer);
 
         debug!("select_where_possible({} obligations) start",
                self.trait_obligations.len());
@@ -158,92 +143,4 @@ impl FulfillmentContext {
             Err(errors)
         }
     }
-
-    pub fn check_builtin_bound_obligations(
-        &self,
-        infcx: &InferCtxt)
-        -> Result<(),Vec<FulfillmentError>>
-    {
-        let tcx = infcx.tcx;
-        let mut errors = Vec::new();
-        debug!("check_builtin_bound_obligations");
-        for obligation in self.builtin_obligations.iter() {
-            debug!("obligation={}", obligation.repr(tcx));
-
-            let def_id = obligation.trait_ref.def_id;
-            let bound = match tcx.lang_items.to_builtin_kind(def_id) {
-                Some(bound) => { bound }
-                None => { continue; }
-            };
-
-            let unskol_self_ty = obligation.self_ty();
-
-            // Skolemize the self-type so that it no longer contains
-            // inference variables. Note that this also replaces
-            // regions with 'static. You might think that this is not
-            // ok, because checking whether something is `Send`
-            // implies checking whether it is 'static: that's true,
-            // but in fact the region bound is fed into region
-            // inference separately and enforced there (and that has
-            // even already been done before this code executes,
-            // generally speaking).
-            let self_ty = skolemize(infcx, unskol_self_ty);
-
-            debug!("bound={} self_ty={}", bound, self_ty.repr(tcx));
-            if ty::type_is_error(self_ty) {
-                // Indicates an error that was/will-be
-                // reported elsewhere.
-                continue;
-            }
-
-            // Determine if builtin bound is met.
-            let tc = ty::type_contents(tcx, self_ty);
-            debug!("tc={}", tc);
-            let met = match bound {
-                ty::BoundSend   => tc.is_sendable(tcx),
-                ty::BoundSized  => tc.is_sized(tcx),
-                ty::BoundCopy   => tc.is_copy(tcx),
-                ty::BoundSync   => tc.is_sync(tcx),
-            };
-
-            if met {
-                continue;
-            }
-
-            // FIXME -- This is kind of a hack: it requently happens
-            // that some earlier error prevents types from being fully
-            // inferred, and then we get a bunch of uninteresting
-            // errors saying something like "<generic #0> doesn't
-            // implement Sized".  It may even be true that we could
-            // just skip over all checks where the self-ty is an
-            // inference variable, but I was afraid that there might
-            // be an inference variable created, registered as an
-            // obligation, and then never forced by writeback, and
-            // hence by skipping here we'd be ignoring the fact that
-            // we don't KNOW the type works out. Though even that
-            // would probably be harmless, given that we're only
-            // talking about builtin traits, which are known to be
-            // inhabited. But in any case I just threw in this check
-            // for has_errors() to be sure that compilation isn't
-            // happening anyway. In that case, why inundate the user.
-            if ty::type_needs_infer(self_ty) &&
-                tcx.sess.has_errors()
-            {
-                debug!("skipping printout because self_ty={}",
-                       self_ty.repr(tcx));
-                continue;
-            }
-
-            errors.push(
-                FulfillmentError::new(
-                    (*obligation).clone(),
-                    CodeSelectionError(Unimplemented)));
-        }
-
-        if errors.is_empty() {
-            Ok(())
-        } else {
-            Err(errors)
-        }
-    }
 }
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index dde733a6a3e..9d66108cfc9 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -12,16 +12,17 @@
  * Trait Resolution. See doc.rs.
  */
 
+use middle::mem_categorization::Typer;
 use middle::subst;
 use middle::ty;
 use middle::typeck::infer::InferCtxt;
 use std::rc::Rc;
 use syntax::ast;
 use syntax::codemap::{Span, DUMMY_SP};
-use util::nodemap::DefIdMap;
 
 pub use self::fulfill::FulfillmentContext;
 pub use self::select::SelectionContext;
+pub use self::select::SelectionCache;
 pub use self::util::supertraits;
 pub use self::util::transitive_bounds;
 pub use self::util::Supertraits;
@@ -68,16 +69,22 @@ pub enum ObligationCauseCode {
     /// Obligation incurred due to an object cast.
     ObjectCastObligation(/* Object type */ ty::t),
 
+    /// To implement drop, type must be sendable.
+    DropTrait,
+
     /// Various cases where expressions must be sized/copy/etc:
     AssignmentLhsSized,        // L = X implies that L is Sized
     StructInitializerSized,    // S { ... } must be Sized
     VariableType(ast::NodeId), // Type of each variable must be Sized
     RepeatVec,                 // [T,..n] --> T must be Copy
-}
 
-pub static DUMMY_CAUSE: ObligationCause =
-    ObligationCause { span: DUMMY_SP,
-                      code: MiscObligation };
+    // Captures of variable the given id by a closure (span is the
+    // span of the closure)
+    ClosureCapture(ast::NodeId, Span),
+
+    // Types of fields (other than the last) in a struct must be sized.
+    FieldSized,
+}
 
 pub type Obligations = subst::VecPerParamSpace<Obligation>;
 
@@ -208,31 +215,11 @@ pub struct VtableParamData {
     pub bound: Rc<ty::TraitRef>,
 }
 
-pub fn try_select_obligation(infcx: &InferCtxt,
-                             param_env: &ty::ParameterEnvironment,
-                             unboxed_closures: &DefIdMap<ty::UnboxedClosure>,
-                             obligation: &Obligation)
-                             -> SelectionResult<Selection>
-{
-    /*!
-     * Attempts to select the impl/bound/etc for the obligation
-     * given. Returns `None` if we are unable to resolve, either
-     * because of ambiguity or due to insufficient inference.  Note
-     * that selection is a shallow process and hence the result may
-     * contain nested obligations that must be resolved. The caller is
-     * responsible for ensuring that those get resolved. (But see
-     * `try_select_obligation_deep` below.)
-     */
-
-    let selcx = select::SelectionContext::new(infcx, param_env, unboxed_closures);
-    selcx.select(obligation)
-}
-
-pub fn evaluate_obligation(infcx: &InferCtxt,
-                           param_env: &ty::ParameterEnvironment,
-                           obligation: &Obligation,
-                           unboxed_closures: &DefIdMap<ty::UnboxedClosure>)
-                           -> EvaluationResult
+pub fn evaluate_obligation<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
+                                    param_env: &ty::ParameterEnvironment,
+                                    obligation: &Obligation,
+                                    typer: &Typer<'tcx>)
+                                    -> EvaluationResult
 {
     /*!
      * Attempts to resolve the obligation given. Returns `None` if
@@ -240,18 +227,17 @@ pub fn evaluate_obligation(infcx: &InferCtxt,
      * due to insufficient inference.
      */
 
-    let selcx = select::SelectionContext::new(infcx, param_env,
-                                              unboxed_closures);
+    let mut selcx = select::SelectionContext::new(infcx, param_env, typer);
     selcx.evaluate_obligation(obligation)
 }
 
-pub fn evaluate_impl(infcx: &InferCtxt,
-                     param_env: &ty::ParameterEnvironment,
-                     unboxed_closures: &DefIdMap<ty::UnboxedClosure>,
-                     cause: ObligationCause,
-                     impl_def_id: ast::DefId,
-                     self_ty: ty::t)
-                     -> EvaluationResult
+pub fn evaluate_impl<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
+                              param_env: &ty::ParameterEnvironment,
+                              typer: &Typer<'tcx>,
+                              cause: ObligationCause,
+                              impl_def_id: ast::DefId,
+                              self_ty: ty::t)
+                              -> EvaluationResult
 {
     /*!
      * Tests whether the impl `impl_def_id` can be applied to the self
@@ -264,17 +250,17 @@ pub fn evaluate_impl(infcx: &InferCtxt,
      *   (yes/no/unknown).
      */
 
-    let selcx = select::SelectionContext::new(infcx, param_env, unboxed_closures);
+    let mut selcx = select::SelectionContext::new(infcx, param_env, typer);
     selcx.evaluate_impl(impl_def_id, cause, self_ty)
 }
 
-pub fn select_inherent_impl(infcx: &InferCtxt,
-                            param_env: &ty::ParameterEnvironment,
-                            unboxed_closures: &DefIdMap<ty::UnboxedClosure>,
-                            cause: ObligationCause,
-                            impl_def_id: ast::DefId,
-                            self_ty: ty::t)
-                            -> SelectionResult<VtableImplData<Obligation>>
+pub fn select_inherent_impl<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
+                                     param_env: &ty::ParameterEnvironment,
+                                     typer: &Typer<'tcx>,
+                                     cause: ObligationCause,
+                                     impl_def_id: ast::DefId,
+                                     self_ty: ty::t)
+                                     -> SelectionResult<VtableImplData<Obligation>>
 {
     /*!
      * Matches the self type of the inherent impl `impl_def_id`
@@ -293,8 +279,7 @@ pub fn select_inherent_impl(infcx: &InferCtxt,
     // `try_resolve_obligation()`.
     assert!(ty::impl_trait_ref(infcx.tcx, impl_def_id).is_none());
 
-    let selcx = select::SelectionContext::new(infcx, param_env,
-                                              unboxed_closures);
+    let mut selcx = select::SelectionContext::new(infcx, param_env, typer);
     selcx.select_inherent_impl(impl_def_id, cause, self_ty)
 }
 
@@ -376,6 +361,10 @@ impl ObligationCause {
     pub fn misc(span: Span) -> ObligationCause {
         ObligationCause { span: span, code: MiscObligation }
     }
+
+    pub fn dummy() -> ObligationCause {
+        ObligationCause { span: DUMMY_SP, code: MiscObligation }
+    }
 }
 
 impl<N> Vtable<N> {
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index e475dc6063d..63fbeb797c4 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -21,32 +21,44 @@ use super::{VtableBuiltin, VtableImpl, VtableParam, VtableUnboxedClosure};
 use super::{VtableImplData, VtableParamData};
 use super::{util};
 
+use middle::mem_categorization::Typer;
 use middle::subst::{Subst, Substs, VecPerParamSpace};
 use middle::ty;
+use middle::ty_fold::TypeFoldable;
 use middle::typeck::check::regionmanip;
 use middle::typeck::infer;
-use middle::typeck::infer::InferCtxt;
+use middle::typeck::infer::{InferCtxt, TypeSkolemizer};
+use std::cell::RefCell;
+use std::collections::hashmap::HashMap;
 use std::rc::Rc;
 use syntax::ast;
-use util::nodemap::DefIdMap;
 use util::ppaux::Repr;
 
 pub struct SelectionContext<'cx, 'tcx:'cx> {
     infcx: &'cx InferCtxt<'cx, 'tcx>,
     param_env: &'cx ty::ParameterEnvironment,
-    unboxed_closures: &'cx DefIdMap<ty::UnboxedClosure>,
+    typer: &'cx Typer<'tcx>+'cx,
+    skolemizer: TypeSkolemizer<'cx, 'tcx>,
 }
 
-// pub struct SelectionCache {
-//     hashmap: RefCell<HashMap<CacheKey, Candidate>>,
-// }
+// A stack that walks back up the stack frame.
+struct ObligationStack<'prev> {
+    obligation: &'prev Obligation,
+    skol_obligation_self_ty: ty::t,
+    previous: Option<&'prev ObligationStack<'prev>>
+}
+
+pub struct SelectionCache {
+    hashmap: RefCell<HashMap<CacheKey, SelectionResult<Candidate>>>,
+}
 
-// #[deriving(Hash,Eq,PartialEq)]
-// struct CacheKey {
-//     trait_def_id: ast::DefId,
-//     skol_obligation_self_ty: ty::t,
-// }
+#[deriving(Hash,Eq,PartialEq)]
+struct CacheKey {
+    trait_def_id: ast::DefId,
+    skol_obligation_self_ty: ty::t,
+}
 
+#[deriving(PartialEq,Eq)]
 enum MatchResult<T> {
     Matched(T),
     AmbiguousMatch,
@@ -86,7 +98,8 @@ enum Candidate {
     MatchedParamCandidate(VtableParamData),
     AmbiguousParamCandidate,
     Impl(ImplCandidate),
-    MatchedUnboxedClosureCandidate(/* closure */ ast::DefId)
+    MatchedUnboxedClosureCandidate(/* closure */ ast::DefId),
+    ErrorCandidate,
 }
 
 #[deriving(Clone)]
@@ -98,10 +111,14 @@ enum ImplCandidate {
 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>,
                param_env: &'cx ty::ParameterEnvironment,
-               unboxed_closures: &'cx DefIdMap<ty::UnboxedClosure>)
+               typer: &'cx Typer<'tcx>)
                -> SelectionContext<'cx, 'tcx> {
-        SelectionContext { infcx: infcx, param_env: param_env,
-                           unboxed_closures: unboxed_closures }
+        SelectionContext {
+            infcx: infcx,
+            param_env: param_env,
+            typer: typer,
+            skolemizer: infcx.skolemizer(),
+        }
     }
 
     pub fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
@@ -123,7 +140,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     //    is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
     //    `impl<T> Iterable<T> for Vec<T>`, than an error would result.
 
-    pub fn select(&self, obligation: &Obligation) -> SelectionResult<Selection> {
+    pub fn select(&mut self, obligation: &Obligation) -> SelectionResult<Selection> {
         /*!
          * Evaluates whether the obligation can be satisfied. Returns
          * an indication of whether the obligation can be satisfied
@@ -133,13 +150,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         debug!("select({})", obligation.repr(self.tcx()));
 
-        match try!(self.candidate_from_obligation(obligation)) {
+        let stack = self.new_stack(obligation);
+        match try!(self.candidate_from_obligation(&stack)) {
             None => Ok(None),
             Some(candidate) => self.confirm_candidate(obligation, candidate),
         }
     }
 
-    pub fn select_inherent_impl(&self,
+    pub fn select_inherent_impl(&mut self,
                                 impl_def_id: ast::DefId,
                                 obligation_cause: ObligationCause,
                                 obligation_self_ty: ty::t)
@@ -177,7 +195,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     // applied to particular types. It skips the "confirmation" step and
     // hence completely ignores output type parameters.
 
-    pub fn evaluate_obligation(&self,
+    pub fn evaluate_obligation(&mut self,
                                obligation: &Obligation)
                                -> EvaluationResult
     {
@@ -189,14 +207,70 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         debug!("evaluate_obligation({})",
                obligation.repr(self.tcx()));
 
-        match self.candidate_from_obligation(obligation) {
+        let stack = self.new_stack(obligation);
+        match self.candidate_from_obligation(&stack) {
             Ok(Some(c)) => c.to_evaluation_result(),
             Ok(None) => EvaluatedToAmbiguity,
             Err(_) => EvaluatedToUnmatch,
         }
     }
 
-    pub fn evaluate_impl(&self,
+    fn evaluate_builtin_bound_recursively(&mut self,
+                                          bound: ty::BuiltinBound,
+                                          previous_stack: &ObligationStack,
+                                          ty: ty::t)
+                                          -> EvaluationResult
+    {
+        let obligation =
+            util::obligation_for_builtin_bound(
+                self.tcx(),
+                previous_stack.obligation.cause,
+                bound,
+                previous_stack.obligation.recursion_depth + 1,
+                ty);
+        self.evaluate_obligation_recursively(previous_stack, &obligation)
+    }
+
+    fn evaluate_obligation_recursively(&mut self,
+                                       previous_stack: &ObligationStack,
+                                       obligation: &Obligation)
+                                       -> EvaluationResult
+    {
+        debug!("evaluate_obligation_recursively({})",
+               obligation.repr(self.tcx()));
+
+        // If there is any previous entry on the stack that precisely
+        // matches this obligation, then we can assume that the
+        // obligation is satisfied for now (still all other conditions
+        // must be met of course). One obvious case this comes up is
+        // marker traits like `Send`. Think of a a linked list:
+        //
+        //    struct List<T> { data: T, next: Option<Box<List<T>>> {
+        //
+        // `Box<List<T>>` will be `Send` if `T` is `Send` and
+        // `Option<Box<List<T>>>` is `Send`, and in turn
+        // `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
+        // `Send`.
+        if
+            previous_stack.iter()
+            .filter(|e| e.obligation.trait_ref.def_id == obligation.trait_ref.def_id)
+            .find(|e| self.match_self_types(obligation.cause,
+                                            e.skol_obligation_self_ty,
+                                            obligation.self_ty()) == Matched(()))
+            .is_some()
+        {
+            return EvaluatedToMatch;
+        }
+
+        let stack = self.push_stack(previous_stack, obligation);
+        match self.candidate_from_obligation(&stack) {
+            Ok(Some(c)) => c.to_evaluation_result(),
+            Ok(None) => EvaluatedToAmbiguity,
+            Err(_) => EvaluatedToUnmatch,
+        }
+    }
+
+    pub fn evaluate_impl(&mut self,
                          impl_def_id: ast::DefId,
                          obligation_cause: ObligationCause,
                          obligation_self_ty: ty::t)
@@ -227,30 +301,46 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     // caller obligations, and so forth and assembling a list of
     // candidates. See `doc.rs` and the `Candidate` type for more details.
 
-    fn candidate_from_obligation(&self, obligation: &Obligation)
+    fn candidate_from_obligation(&mut self,
+                                 stack: &ObligationStack)
                                  -> SelectionResult<Candidate>
     {
-        debug!("candidate_from_obligation({}, self_ty={})",
-               obligation.repr(self.tcx()),
-               self.infcx.ty_to_string(obligation.self_ty()));
-
-        let skol_obligation_self_ty =
-            infer::skolemize(self.infcx, obligation.self_ty());
+        debug!("candidate_from_obligation({})",
+               stack.repr(self.tcx()));
 
         // First, check the cache.
-        match self.check_candidate_cache(obligation, skol_obligation_self_ty) {
+        match self.check_candidate_cache(stack.obligation, stack.skol_obligation_self_ty) {
             Some(c) => {
-                return Ok(Some(c));
+                debug!("check_candidate_cache(obligation={}, skol_obligation_self_ty={}, \
+                       candidate={})",
+                       stack.obligation.trait_ref.def_id,
+                       stack.skol_obligation_self_ty.repr(self.tcx()),
+                       c.repr(self.tcx()));
+                return c;
             }
             None => { }
         }
 
-        let mut candidates =
-            try!(self.assemble_candidates(obligation,
-                                          skol_obligation_self_ty));
+        // If no match, compute result and insert into cache.
+        let result = self.pick_candidate(stack);
+        self.insert_candidate_cache(stack.obligation,
+                                    stack.skol_obligation_self_ty,
+                                    result.clone());
+        result
+    }
+
+    fn pick_candidate(&mut self,
+                      stack: &ObligationStack)
+                      -> SelectionResult<Candidate>
+    {
+        if ty::type_is_error(stack.skol_obligation_self_ty) {
+            return Ok(Some(ErrorCandidate));
+        }
+
+        let mut candidates = try!(self.assemble_candidates(stack));
 
-        debug!("candidate_from_obligation: {} candidates for {}",
-               candidates.len(), obligation.repr(self.tcx()));
+        debug!("assembled {} candidates for {}",
+               candidates.len(), stack.repr(self.tcx()));
 
         // Examine candidates to determine outcome. Ideally we will
         // have exactly one candidate that is definitively applicable.
@@ -262,131 +352,127 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             // it is possible that one of those unbound variables will
             // be bound to a new type from some other crate which will
             // also contain impls.
-            let trait_ref = &*obligation.trait_ref;
-            return if !self.trait_ref_unconstrained(trait_ref) {
-                debug!("candidate_from_obligation({}) -> 0 matches, unimpl",
-                       obligation.repr(self.tcx()));
+            return if !self.contains_skolemized_types(stack.skol_obligation_self_ty) {
+                debug!("0 matches, unimpl");
                 Err(Unimplemented)
             } else {
-                debug!("candidate_from_obligation({}) -> 0 matches, ambig",
-                       obligation.repr(self.tcx()));
+                debug!("0 matches, ambig");
                 Ok(None)
-            };
-        }
-
-        if candidates.len() > 1 {
+            }
+        } else if candidates.len() > 1 {
             // Ambiguity. Possibly we should report back more
             // information on the potential candidates so we can give
             // a better error message.
-            debug!("candidate_from_obligation({}) -> multiple matches, ambig",
-                   obligation.repr(self.tcx()));
-
-            return Ok(None);
+            debug!("multiple matches, ambig");
+            Ok(None)
+        } else {
+            let candidate = candidates.pop().unwrap();
+            Ok(Some(candidate))
         }
+    }
 
-        let candidate = candidates.pop().unwrap();
-        self.insert_candidate_cache(obligation, skol_obligation_self_ty,
-                                    candidate.clone());
-        Ok(Some(candidate))
+    fn pick_candidate_cache(&self,
+                            _obligation: &Obligation,
+                            skol_obligation_self_ty: ty::t)
+                            -> &SelectionCache
+    {
+        if
+            ty::type_has_self(skol_obligation_self_ty) ||
+            ty::type_has_params(skol_obligation_self_ty)
+        {
+            &self.param_env.selection_cache
+        } else {
+            &self.tcx().selection_cache
+        }
     }
 
-    fn check_candidate_cache(&self,
-                             _obligation: &Obligation,
-                             _skol_obligation_self_ty: ty::t)
-                             -> Option<Candidate>
+    fn check_candidate_cache(&mut self,
+                             obligation: &Obligation,
+                             skol_obligation_self_ty: ty::t)
+                             -> Option<SelectionResult<Candidate>>
     {
-        // let cache_key = CacheKey::new(obligation.trait_ref.def_id,
-        //                               skol_obligation_self_ty);
-        // let hashmap = self.tcx().selection_cache.hashmap.borrow();
-        // hashmap.find(&cache_key).map(|c| (*c).clone())
-        None
+        let cache = self.pick_candidate_cache(obligation, skol_obligation_self_ty);
+        let cache_key = CacheKey::new(obligation.trait_ref.def_id,
+                                      skol_obligation_self_ty);
+        let hashmap = cache.hashmap.borrow();
+        hashmap.find(&cache_key).map(|c| (*c).clone())
     }
 
-    fn insert_candidate_cache(&self,
-                              _obligation: &Obligation,
-                              _skol_obligation_self_ty: ty::t,
-                              _candidate: Candidate)
+    fn insert_candidate_cache(&mut self,
+                              obligation: &Obligation,
+                              skol_obligation_self_ty: ty::t,
+                              candidate: SelectionResult<Candidate>)
     {
-        // FIXME -- Enable caching. I think the right place to put the cache
-        // is in the ParameterEnvironment, not the tcx, because otherwise
-        // when there are distinct where clauses in scope the cache can get
-        // confused.
-        //
-        //let cache_key = CacheKey::new(obligation.trait_ref.def_id,
-        //                              skol_obligation_self_ty);
-        //let mut hashmap = self.tcx().selection_cache.hashmap.borrow_mut();
-        //hashmap.insert(cache_key, candidate);
+        debug!("insert_candidate_cache(obligation={}, skol_obligation_self_ty={}, candidate={})",
+               obligation.trait_ref.def_id,
+               skol_obligation_self_ty.repr(self.tcx()),
+               candidate.repr(self.tcx()));
+
+        let cache = self.pick_candidate_cache(obligation, skol_obligation_self_ty);
+        let cache_key = CacheKey::new(obligation.trait_ref.def_id,
+                                      skol_obligation_self_ty);
+        let mut hashmap = cache.hashmap.borrow_mut();
+        hashmap.insert(cache_key, candidate);
     }
 
-    fn assemble_candidates(&self,
-                           obligation: &Obligation,
-                           skol_obligation_self_ty: ty::t)
+    fn assemble_candidates(&mut self,
+                           stack: &ObligationStack)
                            -> Result<Vec<Candidate>, SelectionError>
     {
         // Check for overflow.
 
+        let ObligationStack { obligation, skol_obligation_self_ty, .. } = *stack;
+
         let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
         if obligation.recursion_depth >= recursion_limit {
-            debug!("{} --> overflow", obligation.repr(self.tcx()));
+            debug!("{} --> overflow", stack.obligation.repr(self.tcx()));
             return Err(Overflow);
         }
 
         let mut candidates = Vec::new();
 
-        match self.tcx().lang_items.to_builtin_kind(obligation.trait_ref.def_id) {
-            Some(_) => {
-                // FIXME -- The treatment of builtin bounds is a bit
-                // hacky right now. Eventually, the idea is to move
-                // the logic for selection out of type_contents and
-                // into this module (And make it based on the generic
-                // mechanisms of OIBTT2).  However, I want to land
-                // some code today, so we're going to cut a few
-                // corners. What we do now is that the trait selection
-                // code always considers builtin obligations to
-                // match. The fulfillment code (which also has the job
-                // of tracking all the traits that must hold) will
-                // then just accumulate the various
-                // builtin-bound-related obligations that must be met.
-                // Later, at the end of typeck, after writeback etc,
-                // we will rewalk this list and extract all the
-                // builtin-bound-related obligations and test them
-                // again using type contents. Part of the motivation
-                // for this is that the type contents code requires
-                // that writeback has been completed in some cases.
-
-                candidates.push(AmbiguousBuiltinCandidate);
-            }
+        // Other bounds. Consider both in-scope bounds from fn decl
+        // and applicable impls. There is a certain set of precedence rules here.
 
-            None => {
-                // Other bounds. Consider both in-scope bounds from fn decl
-                // and applicable impls.
-
-                try!(self.assemble_candidates_from_caller_bounds(
-                    obligation,
-                    skol_obligation_self_ty,
-                    &mut candidates));
-
-                try!(self.assemble_unboxed_candidates(
-                    obligation,
-                    skol_obligation_self_ty,
-                    &mut candidates));
-
-                // If there is a fn bound that applies, forego the
-                // impl search. It can only generate conflicts.
-
-                if candidates.len() == 0 {
-                    try!(self.assemble_candidates_from_impls(
-                        obligation,
-                        skol_obligation_self_ty,
-                        &mut candidates));
+        // Where clauses have highest precedence.
+        try!(self.assemble_candidates_from_caller_bounds(
+            obligation,
+            skol_obligation_self_ty,
+            &mut candidates));
+
+        // In the special case of builtin bounds, consider the "compiler-supplied" impls.
+        if candidates.len() == 0 {
+            match self.tcx().lang_items.to_builtin_kind(obligation.trait_ref.def_id) {
+                Some(bound) => {
+                    try!(self.assemble_builtin_bound_candidates(bound, stack, &mut candidates));
                 }
+
+                None => { }
             }
         }
 
+        // In the special case of fn traits and synthesized unboxed
+        // closure types, consider the compiler-supplied impls. Note
+        // that this is exclusive with the builtin bound case above.
+        if candidates.len() == 0 {
+            try!(self.assemble_unboxed_candidates(
+                obligation,
+                skol_obligation_self_ty,
+                &mut candidates));
+        }
+
+        // Finally, consider the actual impls found in the program.
+        if candidates.len() == 0 {
+            try!(self.assemble_candidates_from_impls(
+                obligation,
+                skol_obligation_self_ty,
+                &mut candidates));
+        }
+
         Ok(candidates)
     }
 
-    fn assemble_candidates_from_caller_bounds(&self,
+    fn assemble_candidates_from_caller_bounds(&mut self,
                                               obligation: &Obligation,
                                               skol_obligation_self_ty: ty::t,
                                               candidates: &mut Vec<Candidate>)
@@ -398,28 +484,30 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
          * them.
          *
          * Never affects inference environment.
-v         */
+         */
 
-        debug!("assemble_candidates_from_caller_bounds({})",
-               obligation.repr(self.tcx()));
+        debug!("assemble_candidates_from_caller_bounds({}, {})",
+               obligation.repr(self.tcx()),
+               skol_obligation_self_ty.repr(self.tcx()));
 
         for caller_obligation in self.param_env.caller_obligations.iter() {
-            debug!("caller_obligation={}",
-                   caller_obligation.repr(self.tcx()));
-
             // Skip over obligations that don't apply to
             // `self_ty`.
             let caller_bound = &caller_obligation.trait_ref;
             let caller_self_ty = caller_bound.substs.self_ty().unwrap();
+            debug!("caller_obligation={}, caller_self_ty={}",
+                   caller_obligation.repr(self.tcx()),
+                   self.infcx.ty_to_string(caller_self_ty));
             match self.match_self_types(obligation.cause,
                                         caller_self_ty,
                                         skol_obligation_self_ty) {
                 AmbiguousMatch => {
-                    debug!("-> AmbiguousParamCandidate");
+                    debug!("-> AmbiguousMatch");
                     candidates.push(AmbiguousParamCandidate);
                     return Ok(());
                 }
                 NoMatch => {
+                    debug!("-> NoMatch");
                     continue;
                 }
                 Matched(()) => { }
@@ -428,26 +516,22 @@ v         */
             // Search through the trait (and its supertraits) to
             // see if it matches the def-id we are looking for.
             let caller_bound = (*caller_bound).clone();
-            match util::search_trait_and_supertraits_from_bound(
-                self.infcx.tcx, caller_bound,
-                |d| d == obligation.trait_ref.def_id)
-            {
-                Some(vtable_param) => {
+            for bound in util::transitive_bounds(self.tcx(), &[caller_bound]) {
+                debug!("-> check bound={}", bound.repr(self.tcx()));
+                if bound.def_id == obligation.trait_ref.def_id {
                     // If so, we're done!
-                    debug!("-> MatchedParamCandidate({})", vtable_param);
+                    debug!("-> MatchedParamCandidate({})", bound.repr(self.tcx()));
+                    let vtable_param = VtableParamData { bound: bound };
                     candidates.push(MatchedParamCandidate(vtable_param));
                     return Ok(());
                 }
-
-                None => {
-                }
             }
         }
 
         Ok(())
     }
 
-    fn assemble_unboxed_candidates(&self,
+    fn assemble_unboxed_candidates(&mut self,
                                    obligation: &Obligation,
                                    skol_obligation_self_ty: ty::t,
                                    candidates: &mut Vec<Candidate>)
@@ -481,7 +565,7 @@ v         */
             };
 
             // Check to see whether the argument and return types match.
-            let closure_kind = match self.unboxed_closures.find(&closure_def_id) {
+            let closure_kind = match self.typer.unboxed_closures().borrow().find(&closure_def_id) {
                 Some(closure) => closure.kind,
                 None => {
                     self.tcx().sess.span_bug(
@@ -501,7 +585,7 @@ v         */
         Ok(())
     }
 
-    fn assemble_candidates_from_impls(&self,
+    fn assemble_candidates_from_impls(&mut self,
                                       obligation: &Obligation,
                                       skol_obligation_self_ty: ty::t,
                                       candidates: &mut Vec<Candidate>)
@@ -528,7 +612,7 @@ v         */
         Ok(())
     }
 
-    fn candidate_from_impl(&self,
+    fn candidate_from_impl(&mut self,
                            impl_def_id: ast::DefId,
                            obligation_cause: ObligationCause,
                            skol_obligation_self_ty: ty::t)
@@ -552,13 +636,405 @@ v         */
     }
 
     ///////////////////////////////////////////////////////////////////////////
+    // BUILTIN BOUNDS
+    //
+    // These cover the traits that are built-in to the language
+    // itself.  This includes `Copy` and `Sized` for sure. For the
+    // moment, it also includes `Send` / `Sync` and a few others, but
+    // those will hopefully change to library-defined traits in the
+    // future.
+
+    fn assemble_builtin_bound_candidates(&mut self,
+                                         bound: ty::BuiltinBound,
+                                         stack: &ObligationStack,
+                                         candidates: &mut Vec<Candidate>)
+                                         -> Result<(),SelectionError>
+    {
+        // Copy -- owned, dtor, managed, marker, &mut -- only INTERIOR?
+        // Sized -- str, [T], Trait -- but only INTERIOR
+        // Send -- managed data, nonsend annot, borrowed data -- REACHABILITY
+        // Sync -- non-sync marker trait -- REACHABILITY
+
+        // Ideally, we'd only have to examine the immediate fields.
+        // But think this through carefully I guess.
+
+        enum WhenOk<'a> {
+            Always,
+            Unknown,
+            Never,
+            If(ty::t),
+            IfAll(&'a [ty::t]),
+            IfTrue(bool)
+        }
+
+        let ok = |this: &mut SelectionContext, w: WhenOk| {
+            let r = match w {
+                Always => EvaluatedToMatch,
+                Unknown => EvaluatedToAmbiguity,
+                Never => EvaluatedToUnmatch,
+                IfTrue(true) => EvaluatedToMatch,
+                IfTrue(false) => EvaluatedToUnmatch,
+                If(ty) => this.evaluate_builtin_bound_recursively(bound, stack, ty),
+                IfAll(tys) => {
+                    let mut result = EvaluatedToMatch;
+                    for &ty in tys.iter() {
+                        match this.evaluate_builtin_bound_recursively(bound, stack, ty) {
+                            EvaluatedToMatch => { }
+                            EvaluatedToAmbiguity => {
+                                result = EvaluatedToAmbiguity;
+                            }
+                            EvaluatedToUnmatch => {
+                                result = EvaluatedToUnmatch;
+                                break;
+                            }
+                        }
+                    }
+                    result
+                }
+            };
+
+            match r {
+                EvaluatedToMatch => Ok(candidates.push(MatchedBuiltinCandidate)),
+                EvaluatedToAmbiguity => Ok(candidates.push(AmbiguousBuiltinCandidate)),
+                EvaluatedToUnmatch => Err(Unimplemented)
+            }
+        };
+
+        return match ty::get(stack.skol_obligation_self_ty).sty {
+            ty::ty_uint(_) | ty::ty_int(_) | ty::ty_infer(ty::SkolemizedIntTy(_)) |
+            ty::ty_nil | ty::ty_bot | ty::ty_bool | ty::ty_float(_) |
+            ty::ty_bare_fn(_) | ty::ty_char => {
+                // safe for everything
+                ok(self, Always)
+            }
+
+            ty::ty_box(_) => {
+                match bound {
+                    ty::BoundSync |
+                    ty::BoundSend |
+                    ty::BoundCopy => {
+                        // Managed data is not copyable, sendable, nor
+                        // synchronized, regardless of referent.
+                        ok(self, Never)
+                    }
+
+                    ty::BoundSized => {
+                        // But it is sized, regardless of referent.
+                        ok(self, Always)
+                    }
+                }
+            }
+
+            ty::ty_uniq(referent_ty) => {  // Box<T>
+                match bound {
+                    ty::BoundCopy => {
+                        ok(self, Never)
+                    }
+
+                    ty::BoundSized => {
+                        ok(self, Always)
+                    }
+
+                    ty::BoundSync |
+                    ty::BoundSend => {
+                        ok(self, If(referent_ty))
+                    }
+                }
+            }
+
+            ty::ty_ptr(ty::mt { ty: referent_ty, .. }) => {     // *const T, *mut T
+                match bound {
+                    ty::BoundCopy |
+                    ty::BoundSized => {
+                        ok(self, Always)
+                    }
+
+                    ty::BoundSync |
+                    ty::BoundSend => {
+                        ok(self, If(referent_ty))
+                    }
+                }
+            }
+
+            ty::ty_closure(ref c) => {
+                match c.store {
+                    ty::UniqTraitStore => {
+                        // proc: Equivalent to `Box<FnOnce>`
+                        match bound {
+                            ty::BoundCopy => {
+                                ok(self, Never)
+                            }
+
+                            ty::BoundSized => {
+                                ok(self, Always)
+                            }
+
+                            ty::BoundSync |
+                            ty::BoundSend => {
+                                ok(self, IfTrue(c.bounds.builtin_bounds.contains_elem(bound)))
+                            }
+                        }
+                    }
+                    ty::RegionTraitStore(_, mutbl) => {
+                        // ||: Equivalent to `&FnMut` or `&mut FnMut` or something like that.
+                        match bound {
+                            ty::BoundCopy => {
+                                ok(self, match mutbl {
+                                    ast::MutMutable => Never,  // &mut T is affine
+                                    ast::MutImmutable => Always,  // &T is copyable
+                                })
+                            }
+
+                            ty::BoundSized => {
+                                ok(self, Always)
+                            }
+
+                            ty::BoundSync |
+                            ty::BoundSend => {
+                                ok(self, IfTrue(c.bounds.builtin_bounds.contains_elem(bound)))
+                            }
+                        }
+                    }
+                }
+            }
+
+            ty::ty_trait(box ty::TyTrait { bounds, .. }) => {
+                match bound {
+                    ty::BoundSized => {
+                        ok(self, Never)
+                    }
+                    ty::BoundCopy | ty::BoundSync | ty::BoundSend => {
+                        ok(self, IfTrue(bounds.builtin_bounds.contains_elem(bound)))
+                    }
+                }
+            }
+
+            ty::ty_rptr(_, ty::mt { ty: referent_ty, mutbl: mutbl }) => {
+                // &mut T or &T
+                match bound {
+                    ty::BoundCopy => {
+                        ok(self, match mutbl {
+                            ast::MutMutable => Never,  // &mut T is affine and hence never `Copy`
+                            ast::MutImmutable => Always,  // &T is copyable
+                        })
+                    }
+
+                    ty::BoundSized => {
+                        ok(self, Always)
+                    }
+
+                    ty::BoundSync |
+                    ty::BoundSend => {
+                        // Note: technically, a region pointer is only
+                        // sendable if it has lifetime
+                        // `'static`. However, we don't take regions
+                        // into account when doing trait matching:
+                        // instead, when we decide that `T : Send`, we
+                        // will register a separate constraint with
+                        // the region inferencer that `T : 'static`
+                        // holds as well (because the trait `Send`
+                        // requires it). This will ensure that there
+                        // is no borrowed data in `T` (or else report
+                        // an inference error). The reason we do it
+                        // this way is that we do not yet *know* what
+                        // lifetime the borrowed reference has, since
+                        // we haven't finished running inference -- in
+                        // other words, there's a kind of
+                        // chicken-and-egg problem.
+                        ok(self, If(referent_ty))
+                    }
+                }
+            }
+
+            ty::ty_vec(element_ty, ref len) => {
+                // [T, ..n] and [T]
+                match bound {
+                    ty::BoundCopy => {
+                        match *len {
+                            Some(_) => ok(self, If(element_ty)), // [T, ..n] is copy iff T is copy
+                            None => ok(self, Never), // [T] is unsized and hence affine
+                        }
+                    }
+
+                    ty::BoundSized => {
+                        ok(self, IfTrue(len.is_some()))
+                    }
+
+                    ty::BoundSync |
+                    ty::BoundSend => {
+                        ok(self, If(element_ty))
+                    }
+                }
+            }
+
+            ty::ty_str => {
+                // Equivalent to [u8]
+                match bound {
+                    ty::BoundSync |
+                    ty::BoundSend => {
+                        ok(self, Always)
+                    }
+
+                    ty::BoundCopy |
+                    ty::BoundSized => {
+                        ok(self, Never)
+                    }
+                }
+            }
+
+            ty::ty_tup(ref tys) => {
+                // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
+                ok(self, IfAll(tys.as_slice()))
+            }
+
+            ty::ty_unboxed_closure(def_id, _) => {
+                // FIXME -- This case is tricky. In the case of by-ref
+                // closures particularly, we need the results of
+                // inference to decide how to reflect the type of each
+                // upvar (the upvar may have type `T`, but the runtime
+                // type could be `&mut`, `&`, or just `T`). For now,
+                // though, we'll do this unsoundly and assume that all
+                // captures are by value. Really what we ought to do
+                // is reserve judgement and then intertwine this
+                // analysis with closure inference.
+                //
+                // FIXME -- this is wrong with respect to
+                // skolemization. We want to skolemize the types of
+                // the variables, but to do THAT we need the ability
+                // to "start" the skolemization numbering from a
+                // higher point. Perhaps this just means creating a
+                // single skolemizer and then using it again here?
+                assert_eq!(def_id.krate, ast::LOCAL_CRATE);
+                match self.tcx().freevars.borrow().find(&def_id.node) {
+                    None => {
+                        // No upvars.
+                        ok(self, Always)
+                    }
+
+                    Some(freevars) => {
+                        let tys: Vec<ty::t> =
+                            freevars
+                            .iter()
+                            .map(|freevar| {
+                                let freevar_def_id = freevar.def.def_id();
+                                let freevar_ty = self.typer.node_ty(freevar_def_id.node)
+                                    .unwrap_or(ty::mk_err());
+                                freevar_ty.fold_with(&mut self.skolemizer)
+                            })
+                            .collect();
+                        ok(self, IfAll(tys.as_slice()))
+                    }
+                }
+            }
+
+            ty::ty_struct(def_id, ref substs) => {
+                let types: Vec<ty::t> =
+                    ty::struct_fields(self.tcx(), def_id, substs)
+                    .iter()
+                    .map(|f| f.mt.ty)
+                    .collect();
+                nominal(self, bound, def_id, types, ok)
+            }
+
+            ty::ty_enum(def_id, ref substs) => {
+                let types: Vec<ty::t> =
+                    ty::substd_enum_variants(self.tcx(), def_id, substs)
+                    .iter()
+                    .flat_map(|variant| variant.args.iter())
+                    .map(|&ty| ty)
+                    .collect();
+                nominal(self, bound, def_id, types, ok)
+            }
+
+            ty::ty_param(_) => {
+                // Note: A type parameter is only considered to meet a
+                // particular bound if there is a where clause telling
+                // us that it does, and that case is handled by
+                // `assemble_candidates_from_caller_bounds()`.
+                ok(self, Never)
+            }
+
+            ty::ty_infer(ty::SkolemizedTy(_)) => {
+                // Skolemized types represent unbound type
+                // variables. They might or might not have applicable
+                // impls and so forth, depending on what those type
+                // variables wind up being bound to.
+                ok(self, Unknown)
+            }
+
+            ty::ty_open(_) |
+            ty::ty_infer(ty::TyVar(_)) |
+            ty::ty_infer(ty::IntVar(_)) |
+            ty::ty_infer(ty::FloatVar(_)) |
+            ty::ty_err => {
+                self.tcx().sess.span_bug(
+                    stack.obligation.cause.span,
+                    format!(
+                        "asked to compute contents of unexpected type: {}",
+                        stack.skol_obligation_self_ty.repr(self.tcx())).as_slice());
+            }
+        };
+
+        fn nominal(this: &mut SelectionContext,
+                   bound: ty::BuiltinBound,
+                   def_id: ast::DefId,
+                   types: Vec<ty::t>,
+                   ok: |&mut SelectionContext, WhenOk| -> Result<(),SelectionError>)
+                   -> Result<(),SelectionError>
+        {
+            // First check for markers and other nonsense.
+            let tcx = this.tcx();
+            match bound {
+                ty::BoundSend => {
+                    if
+                        Some(def_id) == tcx.lang_items.no_send_bound() ||
+                        Some(def_id) == tcx.lang_items.managed_bound()
+                    {
+                        return ok(this, Never);
+                    }
+                }
+
+                ty::BoundCopy => {
+                    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 ok(this, Never);
+                    }
+                }
+
+                ty::BoundSync => {
+                    if
+                        Some(def_id) == tcx.lang_items.no_sync_bound() ||
+                        Some(def_id) == tcx.lang_items.managed_bound()
+                    {
+                        return ok(this, Never);
+                    } else if
+                        Some(def_id) == tcx.lang_items.unsafe_type()
+                    {
+                        // FIXME(#13231) -- we currently consider `UnsafeCell<T>`
+                        // to always be sync. This is allow for types like `Queue`
+                        // and `Mutex`, where `Queue<T> : Sync` is `T : Send`.
+                        return ok(this, Always);
+                    }
+                }
+
+                ty::BoundSized => { }
+            }
+
+            ok(this, IfAll(types.as_slice()))
+        }
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
     // CONFIRMATION
     //
     // Confirmation unifies the output type parameters of the trait
     // with the values found in the obligation, possibly yielding a
     // type error.  See `doc.rs` for more details.
 
-    fn confirm_candidate(&self,
+    fn confirm_candidate(&mut self,
                          obligation: &Obligation,
                          candidate: Candidate)
                          -> SelectionResult<Selection>
@@ -574,6 +1050,7 @@ v         */
                 Ok(None)
             }
 
+            ErrorCandidate |
             MatchedBuiltinCandidate => {
                 Ok(Some(VtableBuiltin))
             }
@@ -596,7 +1073,7 @@ v         */
         }
     }
 
-    fn confirm_param_candidate(&self,
+    fn confirm_param_candidate(&mut self,
                                obligation: &Obligation,
                                param: VtableParamData)
                                -> Result<VtableParamData,SelectionError>
@@ -611,7 +1088,7 @@ v         */
         Ok(param)
     }
 
-    fn confirm_impl_candidate(&self,
+    fn confirm_impl_candidate(&mut self,
                               obligation: &Obligation,
                               impl_def_id: ast::DefId)
                               -> Result<VtableImplData<Obligation>,SelectionError>
@@ -638,7 +1115,7 @@ v         */
         Ok(vtable_impl)
     }
 
-    fn confirm_inherent_impl_candidate(&self,
+    fn confirm_inherent_impl_candidate(&mut self,
                                        impl_def_id: ast::DefId,
                                        obligation_cause: ObligationCause,
                                        obligation_self_ty: ty::t,
@@ -671,7 +1148,7 @@ v         */
         Ok(vtable_impl)
     }
 
-    fn confirm_unboxed_closure_candidate(&self,
+    fn confirm_unboxed_closure_candidate(&mut self,
                                          obligation: &Obligation,
                                          closure_def_id: ast::DefId)
                                          -> Result<(),SelectionError>
@@ -680,7 +1157,7 @@ v         */
                obligation.repr(self.tcx()),
                closure_def_id.repr(self.tcx()));
 
-        let closure_type = match self.unboxed_closures.find(&closure_def_id) {
+        let closure_type = match self.typer.unboxed_closures().borrow().find(&closure_def_id) {
             Some(closure) => closure.closure_type.clone(),
             None => {
                 self.tcx().sess.span_bug(
@@ -724,7 +1201,7 @@ v         */
     // run inside of a `probe()` so that their side-effects are
     // contained.
 
-    fn match_impl_self_types(&self,
+    fn match_impl_self_types(&mut self,
                              impl_def_id: ast::DefId,
                              obligation_cause: ObligationCause,
                              obligation_self_ty: ty::t)
@@ -776,7 +1253,7 @@ v         */
         }
     }
 
-    fn match_self_types(&self,
+    fn match_self_types(&mut self,
                         cause: ObligationCause,
 
                         // The self type provided by the impl/caller-obligation:
@@ -821,7 +1298,7 @@ v         */
     // the output type parameters from the obligation with those found
     // on the impl/bound, which may yield type errors.
 
-    fn confirm_impl_vtable(&self,
+    fn confirm_impl_vtable(&mut self,
                            impl_def_id: ast::DefId,
                            obligation_cause: ObligationCause,
                            obligation_trait_ref: Rc<ty::TraitRef>,
@@ -851,7 +1328,7 @@ v         */
         self.confirm(obligation_cause, obligation_trait_ref, impl_trait_ref)
     }
 
-    fn confirm(&self,
+    fn confirm(&mut self,
                obligation_cause: ObligationCause,
                obligation_trait_ref: Rc<ty::TraitRef>,
                expected_trait_ref: Rc<ty::TraitRef>)
@@ -898,6 +1375,32 @@ v         */
     ///////////////////////////////////////////////////////////////////////////
     // Miscellany
 
+    fn new_stack<'o>(&mut self, obligation: &'o Obligation) -> ObligationStack<'o> {
+        let skol_obligation_self_ty =
+            obligation.self_ty().fold_with(&mut self.skolemizer);
+
+        ObligationStack {
+            obligation: obligation,
+            skol_obligation_self_ty: skol_obligation_self_ty,
+            previous: None
+        }
+    }
+
+    fn push_stack<'o>(&self,
+                      previous_stack: &'o ObligationStack<'o>,
+                      obligation: &'o Obligation)
+                      -> ObligationStack<'o>
+    {
+        // No need to skolemize obligation.self_ty, because we
+        // guarantee the self-type for all recursive obligations are
+        // already skolemized.
+        ObligationStack {
+            obligation: obligation,
+            skol_obligation_self_ty: obligation.self_ty(),
+            previous: Some(previous_stack)
+        }
+    }
+
     fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> {
         /*!
          * Returns se tof all impls for a given trait.
@@ -924,22 +1427,17 @@ v         */
                                        &impl_generics, impl_substs)
     }
 
-    fn trait_ref_unconstrained(&self,
-                               trait_ref: &ty::TraitRef)
-                               -> bool
+    fn contains_skolemized_types(&self,
+                                 ty: ty::t)
+                                 -> bool
     {
         /*!
-         * True if the self type of the trait-ref contains
-         * unconstrained type variables.
+         * True if the type contains skolemized variables.
          */
 
         let mut found_skol = false;
 
-        // Skolemization replaces all unconstrained type vars with
-        // a SkolemizedTy instance. Then we search to see if we
-        // found any.
-        let skol_ty = infer::skolemize(self.infcx, trait_ref.self_ty());
-        ty::walk_ty(skol_ty, |t| {
+        ty::walk_ty(ty, |t| {
             match ty::get(t).sty {
                 ty::ty_infer(ty::SkolemizedTy(_)) => { found_skol = true; }
                 _ => { }
@@ -955,6 +1453,7 @@ impl Candidate {
         match *self {
             Impl(ref i) => i.to_evaluation_result(),
 
+            ErrorCandidate |
             MatchedUnboxedClosureCandidate(..) |
             MatchedBuiltinCandidate |
             MatchedParamCandidate(..) => {
@@ -981,6 +1480,7 @@ impl ImplCandidate {
 impl Repr for Candidate {
     fn repr(&self, tcx: &ty::ctxt) -> String {
         match *self {
+            ErrorCandidate => format!("ErrorCandidate"),
             MatchedBuiltinCandidate => format!("MatchedBuiltinCandidate"),
             AmbiguousBuiltinCandidate => format!("AmbiguousBuiltinCandidate"),
             MatchedUnboxedClosureCandidate(c) => format!("MatchedUnboxedClosureCandidate({})", c),
@@ -1003,23 +1503,50 @@ impl Repr for ImplCandidate {
     }
 }
 
+impl SelectionCache {
+    pub fn new() -> SelectionCache {
+        SelectionCache {
+            hashmap: RefCell::new(HashMap::new())
+        }
+    }
+}
+
+impl<'o> ObligationStack<'o> {
+    fn iter(&self) -> Option<&ObligationStack> {
+        Some(self)
+    }
+}
+
+impl<'o> Iterator<&'o ObligationStack<'o>> for Option<&'o ObligationStack<'o>> {
+    fn next(&mut self) -> Option<&'o ObligationStack<'o>> {
+        match *self {
+            Some(o) => {
+                *self = o.previous;
+                Some(o)
+            }
+            None => {
+                None
+            }
+        }
+    }
+}
+
+impl<'o> Repr for ObligationStack<'o> {
+    fn repr(&self, tcx: &ty::ctxt) -> String {
+        format!("ObligationStack({}, {})",
+                self.obligation.repr(tcx),
+                self.skol_obligation_self_ty.repr(tcx))
+    }
+}
 
-// impl SelectionCache {
-//     pub fn new() -> SelectionCache {
-//         SelectionCache {
-//             hashmap: RefCell::new(HashMap::new())
-//         }
-//     }
-// }
-
-// impl CacheKey {
-//     pub fn new(trait_def_id: ast::DefId,
-//                skol_obligation_self_ty: ty::t)
-//                -> CacheKey
-//     {
-//         CacheKey {
-//             trait_def_id: trait_def_id,
-//             skol_obligation_self_ty: skol_obligation_self_ty
-//         }
-//     }
-// }
+impl CacheKey {
+    pub fn new(trait_def_id: ast::DefId,
+               skol_obligation_self_ty: ty::t)
+               -> CacheKey
+    {
+        CacheKey {
+            trait_def_id: trait_def_id,
+            skol_obligation_self_ty: skol_obligation_self_ty
+        }
+    }
+}
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index c48b125ac35..cad86003ce9 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -13,6 +13,7 @@ use middle::subst;
 use middle::subst::{ParamSpace, Subst, Substs, VecPerParamSpace};
 use middle::typeck::infer::InferCtxt;
 use middle::ty;
+use std::collections::HashSet;
 use std::fmt;
 use std::rc::Rc;
 use syntax::ast;
@@ -27,6 +28,7 @@ use super::{Obligation, ObligationCause, VtableImpl, VtableParam, VtableParamDat
 pub struct Supertraits<'cx, 'tcx:'cx> {
     tcx: &'cx ty::ctxt<'tcx>,
     stack: Vec<SupertraitEntry>,
+    visited: HashSet<Rc<ty::TraitRef>>,
 }
 
 struct SupertraitEntry {
@@ -62,15 +64,34 @@ pub fn transitive_bounds<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
                                     -> Supertraits<'cx, 'tcx>
 {
     let bounds = Vec::from_fn(bounds.len(), |i| bounds[i].clone());
+
+    let visited: HashSet<Rc<ty::TraitRef>> =
+        bounds.iter()
+              .map(|b| (*b).clone())
+              .collect();
+
     let entry = SupertraitEntry { position: 0, supertraits: bounds };
-    Supertraits { tcx: tcx, stack: vec![entry] }
+    Supertraits { tcx: tcx, stack: vec![entry], visited: visited }
 }
 
 impl<'cx, 'tcx> Supertraits<'cx, 'tcx> {
     fn push(&mut self, trait_ref: &ty::TraitRef) {
-        let bounds = ty::bounds_for_trait_ref(self.tcx, trait_ref);
-        let entry = SupertraitEntry { position: 0,
-                                      supertraits: bounds.trait_bounds };
+        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());
+            trait_bounds.push(bound_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? { }`.
+        trait_bounds.retain(|r| self.visited.insert((*r).clone()));
+
+        let entry = SupertraitEntry { position: 0, supertraits: trait_bounds };
         self.stack.push(entry);
     }
 
@@ -211,31 +232,41 @@ fn push_obligations_for_param_bounds(
     }
 }
 
-pub fn obligation_for_builtin_bound(
+pub fn trait_ref_for_builtin_bound(
     tcx: &ty::ctxt,
-    cause: ObligationCause,
     builtin_bound: ty::BuiltinBound,
-    recursion_depth: uint,
     param_ty: ty::t)
-    -> Obligation
+    -> Rc<ty::TraitRef>
 {
     match tcx.lang_items.from_builtin_kind(builtin_bound) {
         Ok(def_id) => {
-            Obligation {
-                cause: cause,
-                recursion_depth: recursion_depth,
-                trait_ref: Rc::new(ty::TraitRef {
-                    def_id: def_id,
-                    substs: Substs::empty().with_self_ty(param_ty),
-                }),
-            }
+            Rc::new(ty::TraitRef {
+                def_id: def_id,
+                substs: Substs::empty().with_self_ty(param_ty)
+            })
         }
         Err(e) => {
-            tcx.sess.span_bug(cause.span, e.as_slice());
+            tcx.sess.bug(e.as_slice());
         }
     }
 }
 
+pub fn obligation_for_builtin_bound(
+    tcx: &ty::ctxt,
+    cause: ObligationCause,
+    builtin_bound: ty::BuiltinBound,
+    recursion_depth: uint,
+    param_ty: ty::t)
+    -> Obligation
+{
+    let trait_ref = trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty);
+    Obligation {
+        cause: cause,
+        recursion_depth: recursion_depth,
+        trait_ref: trait_ref
+    }
+}
+
 pub fn search_trait_and_supertraits_from_bound(tcx: &ty::ctxt,
                                                caller_bound: Rc<ty::TraitRef>,
                                                test: |ast::DefId| -> bool)
diff --git a/src/librustc/middle/trans/common.rs b/src/librustc/middle/trans/common.rs
index a5a9d685176..30f91c82930 100644
--- a/src/librustc/middle/trans/common.rs
+++ b/src/librustc/middle/trans/common.rs
@@ -31,6 +31,7 @@ use middle::trans::type_of;
 use middle::traits;
 use middle::ty;
 use middle::ty_fold;
+use middle::ty_fold::TypeFoldable;
 use middle::typeck;
 use middle::typeck::infer;
 use util::ppaux::Repr;
@@ -791,12 +792,10 @@ pub fn fulfill_obligation(ccx: &CrateContext,
     // Parameter environment is used to give details about type parameters,
     // but since we are in trans, everything is fully monomorphized.
     let param_env = ty::empty_parameter_environment();
-    let unboxed_closures = tcx.unboxed_closures.borrow();
 
     // Do the initial selection for the obligation. This yields the
     // shallow result we are looking for -- that is, what specific impl.
-    let selcx = traits::SelectionContext::new(&infcx, &param_env,
-                                              &*unboxed_closures);
+    let mut selcx = traits::SelectionContext::new(&infcx, &param_env, tcx);
     let obligation = traits::Obligation::misc(span, trait_ref.clone());
     let selection = match selcx.select(&obligation) {
         Ok(Some(selection)) => selection,
@@ -825,7 +824,7 @@ pub fn fulfill_obligation(ccx: &CrateContext,
     let vtable = selection.map_move_nested(|obligation| {
         fulfill_cx.register_obligation(tcx, obligation);
     });
-    match fulfill_cx.select_all_or_error(&infcx, &param_env, &*unboxed_closures) {
+    match fulfill_cx.select_all_or_error(&infcx, &param_env, tcx) {
         Ok(()) => { }
         Err(e) => {
             tcx.sess.span_bug(
@@ -841,7 +840,7 @@ pub fn fulfill_obligation(ccx: &CrateContext,
     // sort of overkill because we do not expect there to be any
     // unbound type variables, hence no skolemized types should ever
     // be inserted.
-    let vtable = infer::skolemize(&infcx, vtable);
+    let vtable = vtable.fold_with(&mut infcx.skolemizer());
 
     info!("Cache miss: {}", trait_ref.repr(ccx.tcx()));
     ccx.trait_cache().borrow_mut().insert(trait_ref,
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index 844ee0a60c6..85c43f3f281 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -561,6 +561,9 @@ pub fn get_vtable(bcx: Block,
                                         DUMMY_SP,
                                         trait_ref.clone());
         match vtable {
+            traits::VtableBuiltin => {
+                Vec::new().into_iter()
+            }
             traits::VtableImpl(
                 traits::VtableImplData {
                     impl_def_id: id,
@@ -634,7 +637,6 @@ pub fn get_vtable(bcx: Block,
 
                 (vec!(llfn)).into_iter()
             }
-            traits::VtableBuiltin |
             traits::VtableParam(..) => {
                 bcx.sess().bug(
                     format!("resolved vtable for {} to bad vtable {} in trans",
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 3014eb35e22..5ecf7c0d48d 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -579,6 +579,10 @@ pub struct ctxt<'tcx> {
     /// Maps def IDs of traits to information about their associated types.
     pub trait_associated_types:
         RefCell<DefIdMap<Rc<Vec<AssociatedTypeInfo>>>>,
+
+    /// Caches the results of trait selection. This cache is used
+    /// for things that do not have to do with the parameters in scope.
+    pub selection_cache: traits::SelectionCache,
 }
 
 pub enum tbox_flag {
@@ -1281,6 +1285,10 @@ pub struct ParameterEnvironment {
     /// Note: This effectively *duplicates* the `bounds` array for
     /// now.
     pub caller_obligations: VecPerParamSpace<traits::Obligation>,
+
+    /// Caches the results of trait selection. This cache is used
+    /// for things that have to do with the parameters in scope.
+    pub selection_cache: traits::SelectionCache,
 }
 
 impl ParameterEnvironment {
@@ -1524,7 +1532,8 @@ pub fn mk_ctxt<'tcx>(s: Session,
         capture_modes: capture_modes,
         associated_types: RefCell::new(DefIdMap::new()),
         trait_associated_types: RefCell::new(DefIdMap::new()),
-    }
+        selection_cache: traits::SelectionCache::new(),
+   }
 }
 
 // Type constructors
@@ -2235,35 +2244,25 @@ def_type_content_sets!(
         OwnsAll                             = 0b0000_0000__1111_1111__0000,
 
         // Things that are reachable by the value in any way (fourth nibble):
-        ReachesNonsendAnnot                 = 0b0000_0001__0000_0000__0000,
         ReachesBorrowed                     = 0b0000_0010__0000_0000__0000,
         // ReachesManaged /* see [1] below */  = 0b0000_0100__0000_0000__0000,
         ReachesMutable                      = 0b0000_1000__0000_0000__0000,
-        ReachesNoSync                       = 0b0001_0000__0000_0000__0000,
         ReachesFfiUnsafe                    = 0b0010_0000__0000_0000__0000,
         ReachesAll                          = 0b0011_1111__0000_0000__0000,
 
-        // Things that cause values to *move* rather than *copy*
+        // Things that cause values to *move* rather than *copy*. This
+        // is almost the same as the `Copy` trait, but for managed
+        // data -- atm, we consider managed data to copy, not move,
+        // but it does not impl Copy as a pure memcpy is not good
+        // enough. Yuck.
         Moves                               = 0b0000_0000__0000_1011__0000,
 
         // Things that mean drop glue is necessary
         NeedsDrop                           = 0b0000_0000__0000_0111__0000,
 
-        // Things that prevent values from being sent
-        //
-        // Note: For checking whether something is sendable, it'd
-        //       be sufficient to have ReachesManaged. However, we include
-        //       both ReachesManaged and OwnsManaged so that when
-        //       a parameter has a bound T:Send, we are able to deduce
-        //       that it neither reaches nor owns a managed pointer.
-        Nonsendable                         = 0b0000_0111__0000_0100__0000,
-
         // Things that prevent values from being considered sized
         Nonsized                            = 0b0000_0000__0000_0000__0001,
 
-        // Things that prevent values from being sync
-        Nonsync                             = 0b0001_0000__0000_0000__0000,
-
         // Things that make values considered not POD (would be same
         // as `Moves`, but for the fact that managed data `@` is
         // not considered POD)
@@ -2282,15 +2281,6 @@ def_type_content_sets!(
 )
 
 impl TypeContents {
-    pub fn meets_builtin_bound(&self, cx: &ctxt, bb: BuiltinBound) -> bool {
-        match bb {
-            BoundSend => self.is_sendable(cx),
-            BoundSized => self.is_sized(cx),
-            BoundCopy => self.is_copy(cx),
-            BoundSync => self.is_sync(cx),
-        }
-    }
-
     pub fn when(&self, cond: bool) -> TypeContents {
         if cond {*self} else {TC::None}
     }
@@ -2299,14 +2289,6 @@ impl TypeContents {
         (self.bits & tc.bits) != 0
     }
 
-    pub fn is_sendable(&self, _: &ctxt) -> bool {
-        !self.intersects(TC::Nonsendable)
-    }
-
-    pub fn is_sync(&self, _: &ctxt) -> bool {
-        !self.intersects(TC::Nonsync)
-    }
-
     pub fn owns_managed(&self) -> bool {
         self.intersects(TC::OwnsManaged)
     }
@@ -2319,10 +2301,6 @@ impl TypeContents {
         !self.intersects(TC::Nonsized)
     }
 
-    pub fn is_copy(&self, _: &ctxt) -> bool {
-        !self.intersects(TC::Noncopy)
-    }
-
     pub fn interior_unsafe(&self) -> bool {
         self.intersects(TC::InteriorUnsafe)
     }
@@ -2407,10 +2385,6 @@ impl fmt::Show for TypeContents {
     }
 }
 
-pub fn type_is_sendable(cx: &ctxt, t: ty::t) -> bool {
-    type_contents(cx, t).is_sendable(cx)
-}
-
 pub fn type_interior_is_unsafe(cx: &ctxt, t: ty::t) -> bool {
     type_contents(cx, t).interior_unsafe()
 }
@@ -2652,19 +2626,14 @@ pub fn type_contents(cx: &ctxt, ty: t) -> TypeContents {
     fn apply_lang_items(cx: &ctxt,
                         did: ast::DefId,
                         tc: TypeContents)
-                        -> TypeContents {
-        if Some(did) == cx.lang_items.no_send_bound() {
-            tc | TC::ReachesNonsendAnnot
-        } else if Some(did) == cx.lang_items.managed_bound() {
+                        -> TypeContents
+    {
+        if Some(did) == cx.lang_items.managed_bound() {
             tc | TC::Managed
         } else if Some(did) == cx.lang_items.no_copy_bound() {
             tc | TC::OwnsAffine
-        } else if Some(did) == cx.lang_items.no_sync_bound() {
-            tc | TC::ReachesNoSync
         } else if Some(did) == cx.lang_items.unsafe_type() {
-            // FIXME(#13231): This shouldn't be needed after
-            // opt-in built-in bounds are implemented.
-            (tc | TC::InteriorUnsafe) - TC::Nonsync
+            tc | TC::InteriorUnsafe
         } else {
             tc
         }
@@ -2724,10 +2693,9 @@ pub fn type_contents(cx: &ctxt, ty: t) -> TypeContents {
         let mut tc = TC::All;
         each_inherited_builtin_bound(cx, bounds, traits, |bound| {
             tc = tc - match bound {
-                BoundSend => TC::Nonsendable,
+                BoundSync | BoundSend => TC::None,
                 BoundSized => TC::Nonsized,
                 BoundCopy => TC::Noncopy,
-                BoundSync => TC::Nonsync,
             };
         });
         return tc;
@@ -5324,7 +5292,8 @@ pub fn empty_parameter_environment() -> ParameterEnvironment {
     ty::ParameterEnvironment { free_substs: Substs::empty(),
                                bounds: VecPerParamSpace::empty(),
                                caller_obligations: VecPerParamSpace::empty(),
-                               implicit_region_bound: ty::ReEmpty }
+                               implicit_region_bound: ty::ReEmpty,
+                               selection_cache: traits::SelectionCache::new(), }
 }
 
 pub fn construct_parameter_environment(
@@ -5396,6 +5365,7 @@ pub fn construct_parameter_environment(
         bounds: bounds,
         implicit_region_bound: ty::ReScope(free_id),
         caller_obligations: obligations,
+        selection_cache: traits::SelectionCache::new(),
     };
 
     fn push_region_params(regions: &mut VecPerParamSpace<ty::Region>,
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 8d6369bdbe1..c7be2430cc9 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -298,30 +298,29 @@ impl<'a, 'tcx> mem_categorization::Typer<'tcx> for FnCtxt<'a, 'tcx> {
         self.ccx.tcx
     }
     fn node_ty(&self, id: ast::NodeId) -> McResult<ty::t> {
-        self.ccx.tcx.node_ty(id)
+        Ok(self.node_ty(id))
     }
     fn node_method_ty(&self, method_call: typeck::MethodCall)
                       -> Option<ty::t> {
-        self.ccx.tcx.node_method_ty(method_call)
+        self.inh.method_map.borrow().find(&method_call).map(|m| m.ty)
     }
     fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment>> {
-        self.ccx.tcx.adjustments()
+        &self.inh.adjustments
     }
     fn is_method_call(&self, id: ast::NodeId) -> bool {
-        self.ccx.tcx.is_method_call(id)
+        self.inh.method_map.borrow().contains_key(&typeck::MethodCall::expr(id))
     }
     fn temporary_scope(&self, rvalue_id: ast::NodeId) -> Option<ast::NodeId> {
-        self.ccx.tcx.temporary_scope(rvalue_id)
+        self.tcx().temporary_scope(rvalue_id)
     }
     fn upvar_borrow(&self, upvar_id: ty::UpvarId) -> ty::UpvarBorrow {
-        self.ccx.tcx.upvar_borrow(upvar_id)
+        self.inh.upvar_borrow_map.borrow().get_copy(&upvar_id)
     }
     fn capture_mode(&self, closure_expr_id: ast::NodeId)
                     -> ast::CaptureClause {
         self.ccx.tcx.capture_mode(closure_expr_id)
     }
-    fn unboxed_closures<'a>(&'a self)
-                        -> &'a RefCell<DefIdMap<ty::UnboxedClosure>> {
+    fn unboxed_closures<'a>(&'a self) -> &'a RefCell<DefIdMap<ty::UnboxedClosure>> {
         &self.inh.unboxed_closures
     }
 }
@@ -369,12 +368,7 @@ fn static_inherited_fields<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>)
                                     -> Inherited<'a, 'tcx> {
     // It's kind of a kludge to manufacture a fake function context
     // and statement context, but we might as well do write the code only once
-    let param_env = ty::ParameterEnvironment {
-        free_substs: subst::Substs::empty(),
-        bounds: subst::VecPerParamSpace::empty(),
-        implicit_region_bound: ty::ReStatic,
-        caller_obligations: subst::VecPerParamSpace::empty(),
-    };
+    let param_env = ty::empty_parameter_environment();
     Inherited::new(ccx.tcx, param_env)
 }
 
@@ -387,17 +381,6 @@ impl<'a, 'tcx, 'v> Visitor<'v> for CheckItemTypesVisitor<'a, 'tcx> {
     }
 }
 
-struct CheckItemSizedTypesVisitor<'a, 'tcx: 'a> {
-    ccx: &'a CrateCtxt<'a, 'tcx>
-}
-
-impl<'a, 'tcx, 'v> Visitor<'v> for CheckItemSizedTypesVisitor<'a, 'tcx> {
-    fn visit_item(&mut self, i: &ast::Item) {
-        check_item_sized(self.ccx, i);
-        visit::walk_item(self, i);
-    }
-}
-
 pub fn check_item_types(ccx: &CrateCtxt) {
     let krate = ccx.tcx.map.krate();
     let mut visit = wf::CheckTypeWellFormedVisitor::new(ccx);
@@ -411,9 +394,6 @@ pub fn check_item_types(ccx: &CrateCtxt) {
     visit::walk_crate(&mut visit, krate);
 
     ccx.tcx.sess.abort_if_errors();
-
-    let mut visit = CheckItemSizedTypesVisitor { ccx: ccx };
-    visit::walk_crate(&mut visit, krate);
 }
 
 fn check_bare_fn(ccx: &CrateCtxt,
@@ -435,7 +415,6 @@ fn check_bare_fn(ccx: &CrateCtxt,
             vtable2::select_all_fcx_obligations_or_error(&fcx);
             regionck::regionck_fn(&fcx, id, body);
             writeback::resolve_type_vars_in_fn(&fcx, decl, body);
-            vtable2::check_builtin_bound_obligations(&fcx); // must happen after writeback
         }
         _ => ccx.tcx.sess.impossible_case(body.span,
                                  "check_bare_fn: function type expected")
@@ -677,33 +656,6 @@ fn check_for_field_shadowing(tcx: &ty::ctxt,
     }
 }
 
-fn check_fields_sized(tcx: &ty::ctxt,
-                      struct_def: &ast::StructDef) {
-    let len = struct_def.fields.len();
-    if len == 0 {
-        return;
-    }
-    for f in struct_def.fields.slice_to(len - 1).iter() {
-        let t = ty::node_id_to_type(tcx, f.node.id);
-        if !ty::type_is_sized(tcx, t) {
-            match f.node.kind {
-                ast::NamedField(ident, _) => {
-                    span_err!(tcx.sess, f.span, E0042,
-                        "type `{}` is dynamically sized. \
-                         dynamically sized types may only \
-                         appear as the type of the final \
-                         field in a struct",
-                        token::get_ident(ident));
-                }
-                ast::UnnamedField(_) => {
-                    span_err!(tcx.sess, f.span, E0043,
-                        "dynamically sized type in field");
-                }
-            }
-        }
-    }
-}
-
 pub fn check_struct(ccx: &CrateCtxt, id: ast::NodeId, span: Span) {
     let tcx = ccx.tcx;
 
@@ -718,24 +670,6 @@ pub fn check_struct(ccx: &CrateCtxt, id: ast::NodeId, span: Span) {
     }
 }
 
-pub fn check_item_sized(ccx: &CrateCtxt, it: &ast::Item) {
-    debug!("check_item(it.id={}, it.ident={})",
-           it.id,
-           ty::item_path_str(ccx.tcx, local_def(it.id)));
-    let _indenter = indenter();
-
-    match it.node {
-        ast::ItemEnum(ref enum_definition, _) => {
-            check_enum_variants_sized(ccx,
-                                      enum_definition.variants.as_slice());
-        }
-        ast::ItemStruct(..) => {
-            check_fields_sized(ccx.tcx, &*ccx.tcx.map.expect_struct(it.id));
-        }
-        _ => {}
-    }
-}
-
 pub fn check_item(ccx: &CrateCtxt, it: &ast::Item) {
     debug!("check_item(it.id={}, it.ident={})",
            it.id,
@@ -4866,7 +4800,6 @@ pub fn check_const_with_ty(fcx: &FnCtxt,
     vtable2::select_all_fcx_obligations_or_error(fcx);
     regionck::regionck_expr(fcx, e);
     writeback::resolve_type_vars_in_expr(fcx, e);
-    vtable2::check_builtin_bound_obligations(fcx);
 }
 
 /// Checks whether a type can be represented in memory. In particular, it
@@ -4954,39 +4887,6 @@ pub fn check_simd(tcx: &ty::ctxt, sp: Span, id: ast::NodeId) {
     }
 }
 
-
-pub fn check_enum_variants_sized(ccx: &CrateCtxt,
-                                 vs: &[P<ast::Variant>]) {
-    for v in vs.iter() {
-        match v.node.kind {
-            ast::TupleVariantKind(ref args) if args.len() > 0 => {
-                let ctor_ty = ty::node_id_to_type(ccx.tcx, v.node.id);
-                let arg_tys: Vec<ty::t> = ty::ty_fn_args(ctor_ty).iter().map(|a| *a).collect();
-                let len = arg_tys.len();
-                if len == 0 {
-                    return;
-                }
-                for (i, t) in arg_tys.slice_to(len - 1).iter().enumerate() {
-                    // Allow the last field in an enum to be unsized.
-                    // We want to do this so that we can support smart pointers.
-                    // A struct value with an unsized final field is itself
-                    // unsized and we must track this in the type system.
-                    if !ty::type_is_sized(ccx.tcx, *t) {
-                        span_err!(ccx.tcx.sess, args.get(i).ty.span, E0078,
-                            "type `{}` is dynamically sized. dynamically sized types may only \
-                             appear as the final type in a variant",
-                             ppaux::ty_to_string(ccx.tcx, *t));
-                    }
-                }
-            },
-            ast::StructVariantKind(ref struct_def) => {
-                check_fields_sized(ccx.tcx, &**struct_def)
-            }
-            _ => {}
-        }
-    }
-}
-
 pub fn check_enum_variants(ccx: &CrateCtxt,
                            sp: Span,
                            vs: &[P<ast::Variant>],
diff --git a/src/librustc/middle/typeck/check/regionck.rs b/src/librustc/middle/typeck/check/regionck.rs
index 85fe0a42c49..d45155c2ccd 100644
--- a/src/librustc/middle/typeck/check/regionck.rs
+++ b/src/librustc/middle/typeck/check/regionck.rs
@@ -120,11 +120,13 @@ and report an error, and it just seems like more mess in the end.)
 
 use middle::def;
 use middle::mem_categorization as mc;
+use middle::traits;
 use middle::ty::{ReScope};
 use middle::ty;
 use middle::typeck::astconv::AstConv;
 use middle::typeck::check::FnCtxt;
 use middle::typeck::check::regionmanip;
+use middle::typeck::check::vtable2;
 use middle::typeck::infer::resolve_and_force_all_but_regions;
 use middle::typeck::infer::resolve_type;
 use middle::typeck::infer;
@@ -165,6 +167,11 @@ pub fn regionck_fn(fcx: &FnCtxt, id: ast::NodeId, blk: &ast::Block) {
         // regionck assumes typeck succeeded
         rcx.visit_fn_body(id, blk);
     }
+
+    // Region checking a fn can introduce new trait obligations,
+    // particularly around closure bounds.
+    vtable2::select_all_fcx_obligations_or_error(fcx);
+
     fcx.infcx().resolve_regions_and_report_errors();
 }
 
@@ -848,16 +855,6 @@ fn check_expr_fn_block(rcx: &mut Rcx,
                 }
             });
         }
-        ty::ty_closure(box ty::ClosureTy{store: ty::UniqTraitStore,
-                                         bounds: ref bounds,
-                                         ..}) => {
-            // For proc, ensure that the *types* of the variables
-            // outlive region bound, since they are captured by value.
-            ty::with_freevars(tcx, expr.id, |freevars| {
-                ensure_free_variable_types_outlive_closure_bound(
-                    rcx, bounds.region_bound, expr, freevars);
-            });
-        }
         ty::ty_unboxed_closure(_, region) => {
             ty::with_freevars(tcx, expr.id, |freevars| {
                 // No free variables means that there is no environment and
@@ -868,8 +865,9 @@ fn check_expr_fn_block(rcx: &mut Rcx,
                 // NDM -- this seems wrong, discuss with pcwalton, should
                 // be straightforward enough.
                 if !freevars.is_empty() {
+                    let bounds = ty::region_existential_bound(region);
                     ensure_free_variable_types_outlive_closure_bound(
-                        rcx, region, expr, freevars);
+                        rcx, bounds, expr, freevars);
                 }
             })
         }
@@ -881,20 +879,26 @@ fn check_expr_fn_block(rcx: &mut Rcx,
     rcx.set_repeating_scope(repeating_scope);
 
     match ty::get(function_type).sty {
-        ty::ty_closure(box ty::ClosureTy {
-                store: ty::RegionTraitStore(..),
-                ..
-            }) => {
+        ty::ty_closure(box ty::ClosureTy { store: ty::RegionTraitStore(..), .. }) => {
             ty::with_freevars(tcx, expr.id, |freevars| {
                 propagate_upupvar_borrow_kind(rcx, expr, freevars);
             })
         }
-        _ => ()
+        _ => {}
+    }
+
+    match ty::get(function_type).sty {
+        ty::ty_closure(box ty::ClosureTy {bounds, ..}) => {
+            ty::with_freevars(tcx, expr.id, |freevars| {
+                ensure_free_variable_types_outlive_closure_bound(rcx, bounds, expr, freevars);
+            })
+        }
+        _ => {}
     }
 
     fn ensure_free_variable_types_outlive_closure_bound(
         rcx: &mut Rcx,
-        region_bound: ty::Region,
+        bounds: ty::ExistentialBounds,
         expr: &ast::Expr,
         freevars: &[ty::Freevar])
     {
@@ -908,7 +912,7 @@ fn check_expr_fn_block(rcx: &mut Rcx,
         let tcx = rcx.fcx.ccx.tcx;
 
         debug!("ensure_free_variable_types_outlive_closure_bound({}, {})",
-               region_bound.repr(tcx), expr.repr(tcx));
+               bounds.region_bound.repr(tcx), expr.repr(tcx));
 
         for freevar in freevars.iter() {
             let var_node_id = {
@@ -917,11 +921,35 @@ fn check_expr_fn_block(rcx: &mut Rcx,
                 def_id.node
             };
 
-            let var_ty = rcx.resolve_node_type(var_node_id);
+            // Compute the type of the field in the environment that
+            // represents `var_node_id`.  For a by-value closure, this
+            // will be the same as the type of the variable.  For a
+            // by-reference closure, this will be `&T` where `T` is
+            // the type of the variable.
+            let raw_var_ty = rcx.resolve_node_type(var_node_id);
+            let upvar_id = ty::UpvarId { var_id: var_node_id,
+                                         closure_expr_id: expr.id };
+            let var_ty = match rcx.fcx.inh.upvar_borrow_map.borrow().find(&upvar_id) {
+                Some(upvar_borrow) => {
+                    ty::mk_rptr(rcx.tcx(),
+                                upvar_borrow.region,
+                                ty::mt { mutbl: upvar_borrow.kind.to_mutbl_lossy(),
+                                         ty: raw_var_ty })
+                }
+                None => raw_var_ty
+            };
 
+            // 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);
+                rcx.fcx.inh.fulfillment_cx.borrow_mut().register_obligation(rcx.tcx(), obligation);
+            }
             type_must_outlive(
                 rcx, infer::RelateProcBound(expr.span, var_node_id, var_ty),
-                var_ty, region_bound);
+                var_ty, bounds.region_bound);
         }
     }
 
diff --git a/src/librustc/middle/typeck/check/vtable2.rs b/src/librustc/middle/typeck/check/vtable2.rs
index 61ff86afcec..bcbcebc3f59 100644
--- a/src/librustc/middle/typeck/check/vtable2.rs
+++ b/src/librustc/middle/typeck/check/vtable2.rs
@@ -186,32 +186,15 @@ pub fn select_all_fcx_obligations_or_error(fcx: &FnCtxt) {
     debug!("select_all_fcx_obligations_or_error");
 
     let mut fulfillment_cx = fcx.inh.fulfillment_cx.borrow_mut();
-    let r =
-        fulfillment_cx.select_all_or_error(
-            fcx.infcx(),
-            &fcx.inh.param_env,
-            &*fcx.inh.unboxed_closures.borrow());
+    let r = fulfillment_cx.select_all_or_error(fcx.infcx(),
+                                               &fcx.inh.param_env,
+                                               fcx);
     match r {
         Ok(()) => { }
         Err(errors) => { report_fulfillment_errors(fcx, &errors); }
     }
 }
 
-pub fn check_builtin_bound_obligations(fcx: &FnCtxt) {
-    /*!
-     * Hacky second pass to check builtin-bounds obligations *after*
-     * writeback occurs.
-     */
-
-    match
-        fcx.inh.fulfillment_cx.borrow()
-                              .check_builtin_bound_obligations(fcx.infcx())
-    {
-        Ok(()) => { }
-        Err(errors) => { report_fulfillment_errors(fcx, &errors); }
-    }
-}
-
 fn resolve_trait_ref(fcx: &FnCtxt, obligation: &Obligation)
                      -> (ty::TraitRef, ty::t)
 {
@@ -244,7 +227,8 @@ pub fn report_fulfillment_error(fcx: &FnCtxt,
 
 pub fn report_selection_error(fcx: &FnCtxt,
                               obligation: &Obligation,
-                              error: &SelectionError) {
+                              error: &SelectionError)
+{
     match *error {
         Unimplemented => {
             let (trait_ref, self_ty) = resolve_trait_ref(fcx, obligation);
@@ -309,15 +293,31 @@ pub fn maybe_report_ambiguity(fcx: &FnCtxt, obligation: &Obligation) {
            obligation.repr(fcx.tcx()));
     if ty::type_is_error(self_ty) {
     } else if ty::type_needs_infer(self_ty) {
-        fcx.tcx().sess.span_err(
-            obligation.cause.span,
-            format!(
-                "unable to infer enough type information to \
-             locate the impl of the trait `{}` for \
-             the type `{}`; type annotations required",
-            trait_ref.user_string(fcx.tcx()),
-            self_ty.user_string(fcx.tcx())).as_slice());
-        note_obligation_cause(fcx, obligation);
+        // This is kind of a hack: it frequently happens that some earlier
+        // error prevents types from being fully inferred, and then we get
+        // a bunch of uninteresting errors saying something like "<generic
+        // #0> doesn't implement Sized".  It may even be true that we
+        // could just skip over all checks where the self-ty is an
+        // inference variable, but I was afraid that there might be an
+        // inference variable created, registered as an obligation, and
+        // then never forced by writeback, and hence by skipping here we'd
+        // be ignoring the fact that we don't KNOW the type works
+        // out. Though even that would probably be harmless, given that
+        // we're only talking about builtin traits, which are known to be
+        // inhabited. But in any case I just threw in this check for
+        // has_errors() to be sure that compilation isn't happening
+        // anyway. In that case, why inundate the user.
+        if !fcx.tcx().sess.has_errors() {
+            fcx.tcx().sess.span_err(
+                obligation.cause.span,
+                format!(
+                    "unable to infer enough type information to \
+                     locate the impl of the trait `{}` for \
+                     the type `{}`; type annotations required",
+                    trait_ref.user_string(fcx.tcx()),
+                    self_ty.user_string(fcx.tcx())).as_slice());
+            note_obligation_cause(fcx, obligation);
+        }
     } else if fcx.tcx().sess.err_count() == 0 {
          // Ambiguity. Coherence should have reported an error.
         fcx.tcx().sess.span_bug(
@@ -337,9 +337,7 @@ pub fn select_fcx_obligations_where_possible(fcx: &FnCtxt) {
     match
         fcx.inh.fulfillment_cx
         .borrow_mut()
-        .select_where_possible(fcx.infcx(),
-                               &fcx.inh.param_env,
-                               &*fcx.inh.unboxed_closures.borrow())
+        .select_where_possible(fcx.infcx(), &fcx.inh.param_env, fcx)
     {
         Ok(()) => { }
         Err(errors) => { report_fulfillment_errors(fcx, &errors); }
@@ -392,5 +390,26 @@ fn note_obligation_cause(fcx: &FnCtxt,
                 obligation.cause.span,
                 "structs must have a statically known size to be initialized");
         }
+        traits::DropTrait => {
+            span_note!(tcx.sess, obligation.cause.span,
+                      "cannot implement a destructor on a \
+                      structure or enumeration that does not satisfy Send");
+            span_note!(tcx.sess, obligation.cause.span,
+                       "use \"#[unsafe_destructor]\" on the implementation \
+                       to force the compiler to allow this");
+        }
+        traits::ClosureCapture(var_id, closure_span) => {
+            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 \"
+                       implement the trait `{}`",
+                       name,
+                       trait_name);
+        }
+        traits::FieldSized => {
+            span_note!(tcx.sess, obligation.cause.span,
+                       "only the last field of a struct or enum variant \
+                       may have a dynamically sized type")
+        }
     }
 }
diff --git a/src/librustc/middle/typeck/check/wf.rs b/src/librustc/middle/typeck/check/wf.rs
index 73c0a4e10fc..67f93feae41 100644
--- a/src/librustc/middle/typeck/check/wf.rs
+++ b/src/librustc/middle/typeck/check/wf.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use middle::subst;
 use middle::subst::{Subst};
 use middle::traits;
 use middle::ty;
@@ -21,6 +22,7 @@ use util::ppaux::Repr;
 use std::collections::HashSet;
 use syntax::ast;
 use syntax::ast_util::{local_def};
+use syntax::attr;
 use syntax::codemap::Span;
 use syntax::visit;
 use syntax::visit::Visitor;
@@ -57,7 +59,6 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
                item.id,
                ty::item_path_str(ccx.tcx, local_def(item.id)));
 
-        let ccx = self.ccx;
         match item.node {
             ast::ItemImpl(..) => {
                 self.check_impl(item);
@@ -68,26 +69,14 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
             ast::ItemStatic(..) => {
                 self.check_item_type(item);
             }
-            ast::ItemStruct(..) => {
+            ast::ItemStruct(ref struct_def, _) => {
                 self.check_type_defn(item, |fcx| {
-                    ty::struct_fields(ccx.tcx, local_def(item.id),
-                                      &fcx.inh.param_env.free_substs)
-                        .iter()
-                        .map(|f| f.mt.ty)
-                        .collect()
+                    vec![struct_variant(fcx, &**struct_def)]
                 });
             }
-            ast::ItemEnum(..) => {
+            ast::ItemEnum(ref enum_def, _) => {
                 self.check_type_defn(item, |fcx| {
-                    ty::substd_enum_variants(ccx.tcx, local_def(item.id),
-                                             &fcx.inh.param_env.free_substs)
-                        .iter()
-                        .flat_map(|variant| {
-                            variant.args
-                                .iter()
-                                .map(|&arg_ty| arg_ty)
-                        })
-                        .collect()
+                    enum_variants(fcx, enum_def)
                 });
             }
             _ => {}
@@ -110,12 +99,11 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
         f(self, &fcx);
         vtable2::select_all_fcx_obligations_or_error(&fcx);
         regionck::regionck_item(&fcx, item);
-        vtable2::check_builtin_bound_obligations(&fcx);
     }
 
     fn check_type_defn(&mut self,
                        item: &ast::Item,
-                       lookup_fields: |&FnCtxt| -> Vec<ty::t>)
+                       lookup_fields: |&FnCtxt| -> Vec<AdtVariant>)
     {
         /*!
          * In a type definition, we check that to ensure that the types of the fields are
@@ -123,14 +111,31 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
          */
 
         self.with_fcx(self.ccx, item, |this, fcx| {
-            let field_tys = lookup_fields(fcx);
+            let variants = lookup_fields(fcx);
             let mut bounds_checker = BoundsChecker::new(fcx, item.span,
                                                         item.id, Some(&mut this.cache));
-            for &ty in field_tys.iter() {
-                // Regions are checked below.
-                bounds_checker.check_traits_in_ty(ty);
+            for variant in variants.iter() {
+                for field in variant.fields.iter() {
+                    // Regions are checked below.
+                    bounds_checker.check_traits_in_ty(field.ty);
+                }
+
+                // 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);
+                        fcx.register_obligation(
+                            traits::obligation_for_builtin_bound(fcx.tcx(),
+                                                                 cause,
+                                                                 field.ty,
+                                                                 ty::BoundSized));
+                    }
+                }
             }
 
+            let field_tys: Vec<ty::t> =
+                variants.iter().flat_map(|v| v.fields.iter().map(|f| f.ty)).collect();
+
             regionck::regionck_ensure_component_tys_wf(
                 fcx, item.span, field_tys.as_slice());
         });
@@ -166,6 +171,22 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
             };
             let trait_ref = (*trait_ref).subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
 
+            // There are special rules that apply to drop.
+            if
+                fcx.tcx().lang_items.drop_trait() == Some(trait_ref.def_id) &&
+                !attr::contains_name(item.attrs.as_slice(), "unsafe_destructor")
+            {
+                match ty::get(self_ty).sty {
+                    ty::ty_struct(def_id, _) |
+                    ty::ty_enum(def_id, _) => {
+                        check_struct_safe_for_destructor(fcx, item.span, self_ty, def_id);
+                    }
+                    _ => {
+                        // Coherence already reports an error in this case.
+                    }
+                }
+            }
+
             // We are stricter on the trait-ref in an impl than the
             // self-type.  In particular, we enforce region
             // relationships. The reason for this is that (at least
@@ -363,3 +384,87 @@ impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
         t // we're not folding to produce a new type, so just return `t` here
     }
 }
+
+///////////////////////////////////////////////////////////////////////////
+// ADT
+
+struct AdtVariant {
+    fields: Vec<AdtField>,
+}
+
+struct AdtField {
+    ty: ty::t,
+    span: Span,
+}
+
+fn struct_variant(fcx: &FnCtxt, struct_def: &ast::StructDef) -> AdtVariant {
+    let fields =
+        struct_def.fields
+        .iter()
+        .map(|field| {
+            let field_ty = ty::node_id_to_type(fcx.tcx(), field.node.id);
+            let field_ty = field_ty.subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
+            AdtField { ty: field_ty, span: field.span }
+        })
+        .collect();
+    AdtVariant { fields: fields }
+}
+
+fn enum_variants(fcx: &FnCtxt, enum_def: &ast::EnumDef) -> Vec<AdtVariant> {
+    enum_def.variants.iter()
+        .map(|variant| {
+            match variant.node.kind {
+                ast::TupleVariantKind(ref args) if args.len() > 0 => {
+                    let ctor_ty = ty::node_id_to_type(fcx.tcx(), variant.node.id);
+                    let arg_tys = ty::ty_fn_args(ctor_ty);
+                    AdtVariant {
+                        fields: args.iter().enumerate().map(|(index, arg)| {
+                            let arg_ty = arg_tys[index];
+                            let arg_ty = arg_ty.subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
+                            AdtField {
+                                ty: arg_ty,
+                                span: arg.ty.span
+                            }
+                        }).collect()
+                    }
+                }
+                ast::TupleVariantKind(_) => {
+                    AdtVariant {
+                        fields: Vec::new()
+                    }
+                }
+                ast::StructVariantKind(ref struct_def) => {
+                    struct_variant(fcx, &**struct_def)
+                }
+            }
+        })
+        .collect()
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Special drop trait checking
+
+fn check_struct_safe_for_destructor(fcx: &FnCtxt,
+                                    span: Span,
+                                    self_ty: ty::t,
+                                    struct_did: ast::DefId) {
+    let struct_tpt = ty::lookup_item_type(fcx.tcx(), struct_did);
+    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);
+        fcx.register_obligation(
+            traits::obligation_for_builtin_bound(
+                fcx.tcx(),
+                cause,
+                self_ty,
+                ty::BoundSend));
+    } else {
+        span_err!(fcx.tcx().sess, span, E0141,
+                  "cannot implement a destructor on a structure \
+                       with type parameters");
+            span_note!(fcx.tcx().sess, span,
+                       "use \"#[unsafe_destructor]\" on the implementation \
+                        to force the compiler to allow this");
+    }
+}
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index 742c2b8aabd..2ad6a1f72e2 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -1560,7 +1560,7 @@ impl<'a, 'tcx> ErrorReportingHelpers for InferCtxt<'a, 'tcx> {
                     "...so that it can be closed over into an object");
             }
             infer::RelateProcBound(span, var_node_id, _ty) => {
-                self.tcx.sess.span_err(
+                self.tcx.sess.span_note(
                     span,
                     format!(
                         "...so that the variable `{}` can be captured \
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index d1b754155f8..c36192777f0 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -13,20 +13,20 @@
 #![allow(non_camel_case_types)]
 
 pub use middle::ty::IntVarValue;
-pub use middle::typeck::infer::resolve::resolve_and_force_all_but_regions;
-pub use middle::typeck::infer::resolve::{force_all, not_regions};
-pub use middle::typeck::infer::resolve::{force_ivar};
-pub use middle::typeck::infer::resolve::{force_tvar, force_rvar};
-pub use middle::typeck::infer::resolve::{resolve_ivar, resolve_all};
-pub use middle::typeck::infer::resolve::{resolve_nested_tvar};
-pub use middle::typeck::infer::resolve::{resolve_rvar};
+pub use self::resolve::resolve_and_force_all_but_regions;
+pub use self::resolve::{force_all, not_regions};
+pub use self::resolve::{force_ivar};
+pub use self::resolve::{force_tvar, force_rvar};
+pub use self::resolve::{resolve_ivar, resolve_all};
+pub use self::resolve::{resolve_nested_tvar};
+pub use self::resolve::{resolve_rvar};
+pub use self::skolemize::TypeSkolemizer;
 
 use middle::subst;
 use middle::subst::Substs;
 use middle::ty::{TyVid, IntVid, FloatVid, RegionVid};
 use middle::ty;
 use middle::ty_fold;
-use middle::ty_fold::TypeFoldable;
 use middle::ty_fold::TypeFolder;
 use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
 use middle::typeck::infer::coercion::Coerce;
@@ -382,13 +382,6 @@ pub fn verify_param_bound(cx: &InferCtxt,
     cx.region_vars.verify_param_bound(origin, param_ty, a, bs);
 }
 
-pub fn skolemize<T:TypeFoldable+Repr>(cx: &InferCtxt, a: T) -> T {
-    let mut skol = skolemize::TypeSkolemizer::new(cx);
-    let b = a.fold_with(&mut skol);
-    debug!("skol(a={}) -> {}", a.repr(cx.tcx), b.repr(cx.tcx));
-    b
-}
-
 pub fn mk_eqty(cx: &InferCtxt,
                a_is_expected: bool,
                origin: TypeOrigin,
@@ -513,6 +506,10 @@ pub struct CombinedSnapshot {
 }
 
 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
+    pub fn skolemizer<'a>(&'a self) -> TypeSkolemizer<'a, 'tcx> {
+        skolemize::TypeSkolemizer::new(self)
+    }
+
     pub fn combine_fields<'a>(&'a self, a_is_expected: bool, trace: TypeTrace)
                               -> CombineFields<'a, 'tcx> {
         CombineFields {infcx: self,
diff --git a/src/librustc/middle/typeck/infer/skolemize.rs b/src/librustc/middle/typeck/infer/skolemize.rs
index e1d48407f2e..4002f598449 100644
--- a/src/librustc/middle/typeck/infer/skolemize.rs
+++ b/src/librustc/middle/typeck/infer/skolemize.rs
@@ -119,9 +119,16 @@ impl<'a, 'tcx> TypeFolder<'tcx> for TypeSkolemizer<'a, 'tcx> {
                 self.probe_unifiable(v)
             }
 
-            ty::ty_infer(ty::SkolemizedTy(_)) |
-            ty::ty_infer(ty::SkolemizedIntTy(_)) => {
-                self.tcx().sess.bug("Cannot skolemize a skolemized type");
+            ty::ty_infer(ty::SkolemizedTy(c)) |
+            ty::ty_infer(ty::SkolemizedIntTy(c)) => {
+                if c >= self.skolemization_count {
+                    self.tcx().sess.bug(
+                        format!("Encountered a skolemized type with id {} \
+                                 but our counter is only at {}",
+                                c,
+                                self.skolemization_count).as_slice());
+                }
+                t
             }
 
             ty::ty_open(..) => {
diff --git a/src/test/compile-fail/closure-bounds-static-cant-capture-borrowed.rs b/src/test/compile-fail/closure-bounds-static-cant-capture-borrowed.rs
index c0b463535d4..6769740294b 100644
--- a/src/test/compile-fail/closure-bounds-static-cant-capture-borrowed.rs
+++ b/src/test/compile-fail/closure-bounds-static-cant-capture-borrowed.rs
@@ -12,8 +12,9 @@ fn bar(blk: ||:'static) {
 }
 
 fn foo(x: &()) {
-    bar(|| {
-        let _ = x; //~ ERROR captured variable `x` does not outlive
+    bar(|| { //~ ERROR cannot infer an appropriate lifetime
+        let _ = x;
+        //~^ ERROR captured variable `x` does not outlive
     })
 }
 
diff --git a/src/test/compile-fail/issue-12187-1.rs b/src/test/compile-fail/issue-12187-1.rs
index ce21e33d807..356d95452b3 100644
--- a/src/test/compile-fail/issue-12187-1.rs
+++ b/src/test/compile-fail/issue-12187-1.rs
@@ -14,5 +14,5 @@ fn new<T>() -> &'static T {
 
 fn main() {
     let &v = new();
-    //~^ ERROR cannot determine a type for this local variable: unconstrained type
+    //~^ ERROR type annotations required
 }
diff --git a/src/test/compile-fail/issue-12187-2.rs b/src/test/compile-fail/issue-12187-2.rs
index 90da10959ed..a67d9dee976 100644
--- a/src/test/compile-fail/issue-12187-2.rs
+++ b/src/test/compile-fail/issue-12187-2.rs
@@ -14,5 +14,5 @@ fn new<'r, T>() -> &'r T {
 
 fn main() {
     let &v = new();
-    //~^ ERROR cannot determine a type for this local variable: unconstrained type
+    //~^ ERROR type annotations required
 }
diff --git a/src/test/compile-fail/issue-14915.rs b/src/test/compile-fail/issue-14915.rs
index 75b9626a659..4512eb3f70a 100644
--- a/src/test/compile-fail/issue-14915.rs
+++ b/src/test/compile-fail/issue-14915.rs
@@ -15,8 +15,5 @@ fn main() {
     let y: Gc<int> = box (GC) 0;
 
     println!("{}", x + 1); //~ ERROR binary operation `+` cannot be applied to type `Box<int>`
-    //~^ ERROR unable to infer enough type information
-    println!("{}", y + 1);
-    //~^ ERROR binary operation `+` cannot be applied to type `Gc<int>`
-    //~^^ ERROR unable to infer enough type information
+    println!("{}", y + 1); //~ ERROR binary operation `+` cannot be applied to type `Gc<int>`
 }
diff --git a/src/test/compile-fail/issue-5062.rs b/src/test/compile-fail/issue-5062.rs
index 1cf6dcda04c..df888fe7802 100644
--- a/src/test/compile-fail/issue-5062.rs
+++ b/src/test/compile-fail/issue-5062.rs
@@ -10,4 +10,5 @@
 
 extern crate debug;
 
-fn main() { format!("{:?}", None); } //~ ERROR unconstrained type
+fn main() { format!("{:?}", None); }
+    //~^ ERROR type annotations required
diff --git a/src/test/compile-fail/issue-6458-1.rs b/src/test/compile-fail/issue-6458-1.rs
index a54f05ec348..cb3ffae5dba 100644
--- a/src/test/compile-fail/issue-6458-1.rs
+++ b/src/test/compile-fail/issue-6458-1.rs
@@ -9,4 +9,5 @@
 // except according to those terms.
 
 fn foo<T>(t: T) {}
-fn main() { foo(fail!()) } //~ ERROR cannot determine a type for this expression: unconstrained type
+fn main() { foo(fail!()) }
+    //~^ ERROR type annotations required
diff --git a/src/test/compile-fail/issue-6458-2.rs b/src/test/compile-fail/issue-6458-2.rs
index 701bee85fd7..94884c133b7 100644
--- a/src/test/compile-fail/issue-6458-2.rs
+++ b/src/test/compile-fail/issue-6458-2.rs
@@ -12,5 +12,6 @@ extern crate debug;
 
 fn main() {
     // Unconstrained type:
-    format!("{:?}", None); //~ ERROR: E0101
+    format!("{:?}", None);
+    //~^ ERROR type annotations required
 }
diff --git a/src/test/compile-fail/issue-6458-3.rs b/src/test/compile-fail/issue-6458-3.rs
index 4e0131a5801..f96faeeec4b 100644
--- a/src/test/compile-fail/issue-6458-3.rs
+++ b/src/test/compile-fail/issue-6458-3.rs
@@ -11,5 +11,6 @@
 use std::mem;
 
 fn main() {
-    mem::transmute(0);  //~ ERROR: cannot determine a type for this expression: unconstrained type
+    mem::transmute(0);
+    //~^ ERROR type annotations required
 }
diff --git a/src/test/compile-fail/issue-6458-4.rs b/src/test/compile-fail/issue-6458-4.rs
index e920976069a..02274e5441e 100644
--- a/src/test/compile-fail/issue-6458-4.rs
+++ b/src/test/compile-fail/issue-6458-4.rs
@@ -10,7 +10,7 @@
 
 fn foo(b: bool) -> Result<bool,String> {
     Err("bar".to_string());
-    //~^ ERROR: cannot determine a type for this expression: unconstrained type
+    //~^ ERROR type annotations required
 }
 
 fn main() {
diff --git a/src/test/compile-fail/issue-6458.rs b/src/test/compile-fail/issue-6458.rs
index 8d9c63687ff..efa3100360b 100644
--- a/src/test/compile-fail/issue-6458.rs
+++ b/src/test/compile-fail/issue-6458.rs
@@ -14,7 +14,7 @@ pub struct MyState;
 pub fn foo<State>(_: TypeWithState<State>) {}
 
 pub fn bar() {
-   foo(TypeWithState); //~ ERROR: cannot determine a type for this expression: unconstrained type
+   foo(TypeWithState);  //~ ERROR type annotations required
 }
 
 fn main() {
diff --git a/src/test/compile-fail/issue-7813.rs b/src/test/compile-fail/issue-7813.rs
index be8b6715bc0..81421af4fa8 100644
--- a/src/test/compile-fail/issue-7813.rs
+++ b/src/test/compile-fail/issue-7813.rs
@@ -9,6 +9,6 @@
 // except according to those terms.
 
 fn main() {
-    let v = &[]; //~ ERROR cannot determine a type for this local variable: unconstrained type
-    let it = v.iter();
+    let v = &[];
+    let it = v.iter(); //~ ERROR type annotations required
 }
diff --git a/src/test/compile-fail/kindck-destructor-owned.rs b/src/test/compile-fail/kindck-destructor-owned.rs
index 4197464c600..e50bb8fbede 100644
--- a/src/test/compile-fail/kindck-destructor-owned.rs
+++ b/src/test/compile-fail/kindck-destructor-owned.rs
@@ -16,7 +16,27 @@ struct Foo {
 }
 
 impl Drop for Foo {
-//~^ ERROR cannot implement a destructor on a structure or enumeration that does not satisfy Send
+//~^ ERROR the trait `core::kinds::Send` is not implemented for the type `Foo`
+//~^^ NOTE cannot implement a destructor on a structure or enumeration that does not satisfy Send
+    fn drop(&mut self) {
+    }
+}
+
+struct Bar<'a> {
+    f: &'a int,
+}
+
+impl<'a> Drop for Bar<'a> {
+//~^ ERROR E0141
+    fn drop(&mut self) {
+    }
+}
+
+struct Baz {
+    f: &'static int,
+}
+
+impl Drop for Baz {
     fn drop(&mut self) {
     }
 }
diff --git a/src/test/compile-fail/kindck-nonsendable-1.rs b/src/test/compile-fail/kindck-nonsendable-1.rs
index de4b6ed3545..f292d159982 100644
--- a/src/test/compile-fail/kindck-nonsendable-1.rs
+++ b/src/test/compile-fail/kindck-nonsendable-1.rs
@@ -15,8 +15,8 @@ fn foo(_x: Gc<uint>) {}
 
 fn main() {
     let x = box(GC) 3u;
-    let _: proc():Send = proc() foo(x); //~ ERROR does not fulfill `Send`
-    let _: proc():Send = proc() foo(x); //~ ERROR does not fulfill `Send`
-    let _: proc():Send = proc() foo(x); //~ ERROR does not fulfill `Send`
+    let _: proc():Send = proc() foo(x); //~ ERROR `core::kinds::Send` is not implemented
+    let _: proc():Send = proc() foo(x); //~ ERROR `core::kinds::Send` is not implemented
+    let _: proc():Send = proc() foo(x); //~ ERROR `core::kinds::Send` is not implemented
     let _: proc() = proc() foo(x);
 }
diff --git a/src/test/compile-fail/kindck-send-object1.rs b/src/test/compile-fail/kindck-send-object1.rs
index 9b0991e9ac6..ff8daa045c6 100644
--- a/src/test/compile-fail/kindck-send-object1.rs
+++ b/src/test/compile-fail/kindck-send-object1.rs
@@ -17,11 +17,12 @@ trait Dummy { }
 
 // careful with object types, who knows what they close over...
 fn test51<'a>() {
-    assert_send::<&'a Dummy>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<&'a Dummy>();
     //~^ ERROR the trait `core::kinds::Send` is not implemented
 }
 fn test52<'a>() {
-    assert_send::<&'a Dummy+Send>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<&'a Dummy+Send>();
+    //~^ ERROR does not fulfill the required lifetime
 }
 
 // ...unless they are properly bounded
@@ -35,12 +36,12 @@ fn test61() {
 // closure and object types can have lifetime bounds which make
 // them not ok
 fn test_70<'a>() {
-    assert_send::<proc():'a>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<proc():'a>();
     //~^ ERROR the trait `core::kinds::Send` is not implemented
 }
 
 fn test_71<'a>() {
-    assert_send::<Box<Dummy+'a>>(); //~ ERROR does not fulfill the required lifetime
+    assert_send::<Box<Dummy+'a>>();
     //~^ ERROR the trait `core::kinds::Send` is not implemented
 }
 
diff --git a/src/test/compile-fail/no-send-res-ports.rs b/src/test/compile-fail/no-send-res-ports.rs
index f58350cf093..ddbfbc41eca 100644
--- a/src/test/compile-fail/no-send-res-ports.rs
+++ b/src/test/compile-fail/no-send-res-ports.rs
@@ -37,7 +37,7 @@ fn main() {
 
     task::spawn(proc() {
         let y = x;
-        //~^ ERROR does not fulfill `Send`
+        //~^ ERROR `core::kinds::Send` is not implemented
         println!("{:?}", y);
     });
 }
diff --git a/src/test/compile-fail/regions-bounded-by-send.rs b/src/test/compile-fail/regions-bounded-by-send.rs
index 50190411bf0..182b40ceaae 100644
--- a/src/test/compile-fail/regions-bounded-by-send.rs
+++ b/src/test/compile-fail/regions-bounded-by-send.rs
@@ -57,21 +57,22 @@ fn box_with_region_not_ok<'a>() {
 // objects with insufficient bounds no ok
 
 fn object_with_random_bound_not_ok<'a>() {
-    assert_send::<&'a Dummy+'a>(); //~ ERROR does not fulfill
+    assert_send::<&'a Dummy+'a>();
     //~^ ERROR not implemented
 }
 
 fn object_with_send_bound_not_ok<'a>() {
-    assert_send::<&'a Dummy+Send>(); //~ ERROR does not fulfill
+    assert_send::<&'a Dummy+Send>();
+    //~^ ERROR does not fulfill
 }
 
 fn proc_with_lifetime_not_ok<'a>() {
-    assert_send::<proc():'a>(); //~ ERROR does not fulfill
+    assert_send::<proc():'a>();
     //~^ ERROR not implemented
 }
 
 fn closure_with_lifetime_not_ok<'a>() {
-    assert_send::<||:'a>(); //~ ERROR does not fulfill
+    assert_send::<||:'a>();
     //~^ ERROR not implemented
 }
 
diff --git a/src/test/compile-fail/regions-enum-not-wf.rs b/src/test/compile-fail/regions-enum-not-wf.rs
index 6395ee62f16..0691ad0de73 100644
--- a/src/test/compile-fail/regions-enum-not-wf.rs
+++ b/src/test/compile-fail/regions-enum-not-wf.rs
@@ -10,7 +10,6 @@
 
 // Various examples of structs whose fields are not well-formed.
 
-#![no_std]
 #![allow(dead_code)]
 
 enum Ref1<'a, T> { //~ ERROR the parameter type `T` may not live long enough
diff --git a/src/test/compile-fail/unconstrained-none.rs b/src/test/compile-fail/unconstrained-none.rs
index 798b92fd57b..9879766a8fa 100644
--- a/src/test/compile-fail/unconstrained-none.rs
+++ b/src/test/compile-fail/unconstrained-none.rs
@@ -11,5 +11,5 @@
 // Issue #5062
 
 fn main() {
-    None; //~ ERROR cannot determine a type for this expression: unconstrained type
+    None; //~ ERROR type annotations required
 }
diff --git a/src/test/compile-fail/unconstrained-ref.rs b/src/test/compile-fail/unconstrained-ref.rs
index 87647cdb546..e03f60e758c 100644
--- a/src/test/compile-fail/unconstrained-ref.rs
+++ b/src/test/compile-fail/unconstrained-ref.rs
@@ -13,5 +13,5 @@ struct S<'a, T:'a> {
 }
 
 fn main() {
-    S { o: &None }; //~ ERROR cannot determine a type for this expression: unconstrained type
+    S { o: &None }; //~ ERROR type annotations required
 }
diff --git a/src/test/compile-fail/unsized5.rs b/src/test/compile-fail/unsized5.rs
index 6eecc723431..41196b60c8e 100644
--- a/src/test/compile-fail/unsized5.rs
+++ b/src/test/compile-fail/unsized5.rs
@@ -12,25 +12,25 @@
 // Test `Sized?` types not allowed in fields (except the last one).
 
 struct S1<Sized? X> {
-    f1: X, //~ ERROR type `f1` is dynamically sized. dynamically sized types may only appear as the
+    f1: X, //~ ERROR `core::kinds::Sized` is not implemented
     f2: int,
 }
 struct S2<Sized? X> {
     f: int,
-    g: X, //~ ERROR type `g` is dynamically sized. dynamically sized types may only appear as the ty
+    g: X, //~ ERROR `core::kinds::Sized` is not implemented
     h: int,
 }
 struct S3 {
-    f: str, //~ ERROR type `f` is dynamically sized. dynamically sized types may only appear
+    f: str, //~ ERROR `core::kinds::Sized` is not implemented
     g: [uint]
 }
 struct S4 {
-    f: str, //~ ERROR type `f` is dynamically sized. dynamically sized types may only appear
+    f: str, //~ ERROR `core::kinds::Sized` is not implemented
     g: uint
 }
 enum E<Sized? X> {
-    V1(X, int), //~ERROR type `X` is dynamically sized. dynamically sized types may only appear as t
-    V2{f1: X, f: int}, //~ERROR type `f1` is dynamically sized. dynamically sized types may only app
+    V1(X, int), //~ERROR `core::kinds::Sized` is not implemented
+    V2{f1: X, f: int}, //~ERROR `core::kinds::Sized` is not implemented
 }
 
 pub fn main() {
diff --git a/src/test/compile-fail/vector-no-ann.rs b/src/test/compile-fail/vector-no-ann.rs
index 9c41b0bc1c1..d48f5715ec1 100644
--- a/src/test/compile-fail/vector-no-ann.rs
+++ b/src/test/compile-fail/vector-no-ann.rs
@@ -10,5 +10,5 @@
 
 
 fn main() {
-    let _foo = Vec::new(); //~ ERROR unconstrained type
+    let _foo = Vec::new(); //~ ERROR type annotations required
 }
diff --git a/src/test/run-make/no-duplicate-libs/bar.rs b/src/test/run-make/no-duplicate-libs/bar.rs
index 8b87b5f0f9a..721d16b4810 100644
--- a/src/test/run-make/no-duplicate-libs/bar.rs
+++ b/src/test/run-make/no-duplicate-libs/bar.rs
@@ -19,3 +19,4 @@ pub extern fn bar() {}
 
 #[lang = "stack_exhausted"] fn stack_exhausted() {}
 #[lang = "eh_personality"] fn eh_personality() {}
+#[lang = "fail_fmt"] fn fail_fmt() -> ! { loop {} }
diff --git a/src/test/run-make/no-duplicate-libs/foo.rs b/src/test/run-make/no-duplicate-libs/foo.rs
index 6f9537c1f44..3382cc20799 100644
--- a/src/test/run-make/no-duplicate-libs/foo.rs
+++ b/src/test/run-make/no-duplicate-libs/foo.rs
@@ -19,3 +19,4 @@ pub extern fn foo() {}
 
 #[lang = "stack_exhausted"] fn stack_exhausted() {}
 #[lang = "eh_personality"] fn eh_personality() {}
+#[lang = "fail_fmt"] fn fail_fmt() -> ! { loop {} }
diff --git a/src/test/run-pass/smallest-hello-world.rs b/src/test/run-pass/smallest-hello-world.rs
index 52e71186537..fdddac6bc37 100644
--- a/src/test/run-pass/smallest-hello-world.rs
+++ b/src/test/run-pass/smallest-hello-world.rs
@@ -22,7 +22,7 @@ extern "rust-intrinsic" { fn transmute<T, U>(t: T) -> U; }
 
 #[lang = "stack_exhausted"] extern fn stack_exhausted() {}
 #[lang = "eh_personality"] extern fn eh_personality() {}
-#[lang = "sized"] pub trait Sized {}
+#[lang = "fail_fmt"] fn fail_fmt() -> ! { loop {} }
 
 #[start]
 #[no_split_stack]