Integrate builtin bounds fully into the trait checker

28 files changed, 821 insertions, 404 deletions

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/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index 415eed380fc..d84729d1935 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -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, DUMMY_CAUSE,
                         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..f69eb2e17ea 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -12,13 +12,13 @@
  * 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;
@@ -208,31 +208,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 +220,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 +243,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 +272,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)
 }
 
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index e475dc6063d..5395e966887 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -21,20 +21,29 @@ 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::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>,
+}
+
+// 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 {
@@ -47,6 +56,7 @@ pub struct SelectionContext<'cx, 'tcx:'cx> {
 //     skol_obligation_self_ty: ty::t,
 // }
 
+#[deriving(PartialEq,Eq)]
 enum MatchResult<T> {
     Matched(T),
     AmbiguousMatch,
@@ -86,7 +96,8 @@ enum Candidate {
     MatchedParamCandidate(VtableParamData),
     AmbiguousParamCandidate,
     Impl(ImplCandidate),
-    MatchedUnboxedClosureCandidate(/* closure */ ast::DefId)
+    MatchedUnboxedClosureCandidate(/* closure */ ast::DefId),
+    ErrorCandidate,
 }
 
 #[deriving(Clone)]
@@ -98,10 +109,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 +138,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 +148,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 +193,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 +205,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,
+        }
+    }
+
+    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(&self,
+    pub fn evaluate_impl(&mut self,
                          impl_def_id: ast::DefId,
                          obligation_cause: ObligationCause,
                          obligation_self_ty: ty::t)
@@ -227,30 +299,40 @@ 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));
             }
             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(obligation, 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()));
+               candidates.len(),
+               stack.repr(self.tcx()));
 
         // Examine candidates to determine outcome. Ideally we will
         // have exactly one candidate that is definitively applicable.
@@ -262,14 +344,12 @@ 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()));
+                       stack.repr(self.tcx()));
                 Ok(None)
             };
         }
@@ -279,18 +359,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             // information on the potential candidates so we can give
             // a better error message.
             debug!("candidate_from_obligation({}) -> multiple matches, ambig",
-                   obligation.repr(self.tcx()));
+                   stack.repr(self.tcx()));
 
             return Ok(None);
         }
 
         let candidate = candidates.pop().unwrap();
-        self.insert_candidate_cache(obligation, skol_obligation_self_ty,
+        self.insert_candidate_cache(stack.obligation,
+                                    stack.skol_obligation_self_ty,
                                     candidate.clone());
         Ok(Some(candidate))
     }
 
-    fn check_candidate_cache(&self,
+    fn check_candidate_cache(&mut self,
                              _obligation: &Obligation,
                              _skol_obligation_self_ty: ty::t)
                              -> Option<Candidate>
@@ -302,7 +383,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         None
     }
 
-    fn insert_candidate_cache(&self,
+    fn insert_candidate_cache(&mut self,
                               _obligation: &Obligation,
                               _skol_obligation_self_ty: ty::t,
                               _candidate: Candidate)
@@ -318,75 +399,64 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         //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 +468,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 +500,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 +549,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 +569,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 +596,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 +620,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 +1034,7 @@ v         */
                 Ok(None)
             }
 
+            ErrorCandidate |
             MatchedBuiltinCandidate => {
                 Ok(Some(VtableBuiltin))
             }
@@ -596,7 +1057,7 @@ v         */
         }
     }
 
-    fn confirm_param_candidate(&self,
+    fn confirm_param_candidate(&mut self,
                                obligation: &Obligation,
                                param: VtableParamData)
                                -> Result<VtableParamData,SelectionError>
@@ -611,7 +1072,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 +1099,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 +1132,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 +1141,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 +1185,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 +1237,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 +1282,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 +1312,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 +1359,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 +1411,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 +1437,7 @@ impl Candidate {
         match *self {
             Impl(ref i) => i.to_evaluation_result(),
 
+            ErrorCandidate |
             MatchedUnboxedClosureCandidate(..) |
             MatchedBuiltinCandidate |
             MatchedParamCandidate(..) => {
@@ -981,6 +1464,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,6 +1487,33 @@ impl Repr for ImplCandidate {
     }
 }
 
+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 {
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/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 8d6369bdbe1..9009644eb0c 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
     }
 }
@@ -435,7 +434,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")
@@ -4866,7 +4864,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
diff --git a/src/librustc/middle/typeck/check/vtable2.rs b/src/librustc/middle/typeck/check/vtable2.rs
index 61ff86afcec..63a17cec575 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); }
diff --git a/src/librustc/middle/typeck/check/wf.rs b/src/librustc/middle/typeck/check/wf.rs
index 73c0a4e10fc..6a63464c4b6 100644
--- a/src/librustc/middle/typeck/check/wf.rs
+++ b/src/librustc/middle/typeck/check/wf.rs
@@ -110,7 +110,6 @@ 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,
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/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-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/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/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/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
 }