Auto merge of #30533 - nikomatsakis:fulfillment-tree, r=aturon

This PR introduces an `ObligationForest` data structure that the fulfillment context can use to track what's going on, instead of the current flat vector. This enables a number of improvements:

1. transactional support, at least for pushing new obligations
2. remove the "errors will be reported" hack -- instead, we only add types to the global cache once their entire subtree has been proven safe. Before, we never knew when this point was reached because we didn't track the subtree.
   - this in turn allows us to limit coinductive reasoning to structural traits, which sidesteps #29859
3. keeping the backtrace should allow for an improved error message, where we give the user full context
    - we can also remove chained obligation causes

This PR is not 100% complete. In particular:

- [x] Currently, types that embed themselves like `struct Foo { f: Foo }` give an overflow when evaluating whether `Foo: Sized`. This is not a very user-friendly error message, and this is a common beginner error. I plan to special-case this scenario, I think.
- [x] I should do some perf. measurements. (Update: 2% regression.)
- [x] More tests targeting #29859
- [ ] The transactional support is not fully integrated, though that should be easy enough.
- [ ] The error messages are not taking advantage of the backtrace.

I'd certainly like to do 1 through 3 before landing, but 4 and 5 could come as separate PRs.

r? @aturon // good way to learn more about this part of the trait system
f? @arielb1 // already knows this part of the trait system :)

66 files changed, 1467 insertions, 356 deletions

diff --git a/src/librustc/diagnostics.rs b/src/librustc/diagnostics.rs
index 9f323379b95..aa2f60f71f9 100644
--- a/src/librustc/diagnostics.rs
+++ b/src/librustc/diagnostics.rs
@@ -679,6 +679,43 @@ There's no easy fix for this, generally code will need to be refactored so that
 you no longer need to derive from `Super<Self>`.
 "####,
 
+E0072: r##"
+When defining a recursive struct or enum, any use of the type being defined
+from inside the definition must occur behind a pointer (like `Box` or `&`).
+This is because structs and enums must have a well-defined size, and without
+the pointer the size of the type would need to be unbounded.
+
+Consider the following erroneous definition of a type for a list of bytes:
+
+```
+// error, invalid recursive struct type
+struct ListNode {
+    head: u8,
+    tail: Option<ListNode>,
+}
+```
+
+This type cannot have a well-defined size, because it needs to be arbitrarily
+large (since we would be able to nest `ListNode`s to any depth). Specifically,
+
+```plain
+size of `ListNode` = 1 byte for `head`
+                   + 1 byte for the discriminant of the `Option`
+                   + size of `ListNode`
+```
+
+One way to fix this is by wrapping `ListNode` in a `Box`, like so:
+
+```
+struct ListNode {
+    head: u8,
+    tail: Option<Box<ListNode>>,
+}
+```
+
+This works because `Box` is a pointer, so its size is well-known.
+"##,
+
 E0109: r##"
 You tried to give a type parameter to a type which doesn't need it. Erroneous
 code example:
diff --git a/src/librustc/middle/check_const.rs b/src/librustc/middle/check_const.rs
index 6001b120587..5822b3dc5e9 100644
--- a/src/librustc/middle/check_const.rs
+++ b/src/librustc/middle/check_const.rs
@@ -125,7 +125,7 @@ impl<'a, 'tcx> CheckCrateVisitor<'a, 'tcx> {
             None => self.tcx.empty_parameter_environment()
         };
 
-        let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, Some(param_env), false);
+        let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, Some(param_env));
 
         f(&mut euv::ExprUseVisitor::new(self, &infcx))
     }
@@ -280,7 +280,7 @@ impl<'a, 'tcx> CheckCrateVisitor<'a, 'tcx> {
 
     fn check_static_type(&self, e: &hir::Expr) {
         let ty = self.tcx.node_id_to_type(e.id);
-        let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, None, false);
+        let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, None);
         let cause = traits::ObligationCause::new(e.span, e.id, traits::SharedStatic);
         let mut fulfill_cx = infcx.fulfillment_cx.borrow_mut();
         fulfill_cx.register_builtin_bound(&infcx, ty, ty::BoundSync, cause);
diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index dc777585e41..8e5c5788201 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -1095,8 +1095,7 @@ fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
                         //FIXME: (@jroesch) this code should be floated up as well
                         let infcx = infer::new_infer_ctxt(cx.tcx,
                                                           &cx.tcx.tables,
-                                                          Some(cx.param_env.clone()),
-                                                          false);
+                                                          Some(cx.param_env.clone()));
                         if infcx.type_moves_by_default(pat_ty, pat.span) {
                             check_move(p, sub.as_ref().map(|p| &**p));
                         }
@@ -1128,8 +1127,7 @@ fn check_for_mutation_in_guard<'a, 'tcx>(cx: &'a MatchCheckCtxt<'a, 'tcx>,
 
     let infcx = infer::new_infer_ctxt(cx.tcx,
                                       &cx.tcx.tables,
-                                      Some(checker.cx.param_env.clone()),
-                                      false);
+                                      Some(checker.cx.param_env.clone()));
 
     let mut visitor = ExprUseVisitor::new(&mut checker, &infcx);
     visitor.walk_expr(guard);
diff --git a/src/librustc/middle/check_rvalues.rs b/src/librustc/middle/check_rvalues.rs
index 8a3e039ac6e..5ead8fb95f8 100644
--- a/src/librustc/middle/check_rvalues.rs
+++ b/src/librustc/middle/check_rvalues.rs
@@ -44,8 +44,7 @@ impl<'a, 'tcx, 'v> intravisit::Visitor<'v> for RvalueContext<'a, 'tcx> {
             let param_env = ParameterEnvironment::for_item(self.tcx, fn_id);
             let infcx = infer::new_infer_ctxt(self.tcx,
                                               &self.tcx.tables,
-                                              Some(param_env.clone()),
-                                              false);
+                                              Some(param_env.clone()));
             let mut delegate = RvalueContextDelegate { tcx: self.tcx, param_env: &param_env };
             let mut euv = euv::ExprUseVisitor::new(&mut delegate, &infcx);
             euv.walk_fn(fd, b);
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index de7f543e328..ab421b27c08 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -1262,7 +1262,7 @@ fn resolve_trait_associated_const<'a, 'tcx: 'a>(tcx: &'a ty::ctxt<'tcx>,
                                               substs: trait_substs });
 
     tcx.populate_implementations_for_trait_if_necessary(trait_ref.def_id());
-    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
+    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None);
 
     let mut selcx = traits::SelectionContext::new(&infcx);
     let obligation = traits::Obligation::new(traits::ObligationCause::dummy(),
diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index 922d4c251bb..15e368812f2 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -354,16 +354,9 @@ pub fn fixup_err_to_string(f: FixupError) -> String {
     }
 }
 
-/// errors_will_be_reported is required to proxy to the fulfillment context
-/// FIXME -- a better option would be to hold back on modifying
-/// the global cache until we know that all dependent obligations
-/// are also satisfied. In that case, we could actually remove
-/// this boolean flag, and we'd also avoid the problem of squelching
-/// duplicate errors that occur across fns.
 pub fn new_infer_ctxt<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
                                 tables: &'a RefCell<ty::Tables<'tcx>>,
-                                param_env: Option<ty::ParameterEnvironment<'a, 'tcx>>,
-                                errors_will_be_reported: bool)
+                                param_env: Option<ty::ParameterEnvironment<'a, 'tcx>>)
                                 -> InferCtxt<'a, 'tcx> {
     InferCtxt {
         tcx: tcx,
@@ -373,7 +366,7 @@ pub fn new_infer_ctxt<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
         float_unification_table: RefCell::new(UnificationTable::new()),
         region_vars: RegionVarBindings::new(tcx),
         parameter_environment: param_env.unwrap_or(tcx.empty_parameter_environment()),
-        fulfillment_cx: RefCell::new(traits::FulfillmentContext::new(errors_will_be_reported)),
+        fulfillment_cx: RefCell::new(traits::FulfillmentContext::new()),
         reported_trait_errors: RefCell::new(FnvHashSet()),
         normalize: false,
         err_count_on_creation: tcx.sess.err_count()
@@ -383,7 +376,7 @@ pub fn new_infer_ctxt<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
 pub fn normalizing_infer_ctxt<'a, 'tcx>(tcx: &'a ty::ctxt<'tcx>,
                                         tables: &'a RefCell<ty::Tables<'tcx>>)
                                         -> InferCtxt<'a, 'tcx> {
-    let mut infcx = new_infer_ctxt(tcx, tables, None, false);
+    let mut infcx = new_infer_ctxt(tcx, tables, None);
     infcx.normalize = true;
     infcx
 }
@@ -522,7 +515,7 @@ pub fn normalize_associated_type<'tcx,T>(tcx: &ty::ctxt<'tcx>, value: &T) -> T
         return value;
     }
 
-    let infcx = new_infer_ctxt(tcx, &tcx.tables, None, true);
+    let infcx = new_infer_ctxt(tcx, &tcx.tables, None);
     let mut selcx = traits::SelectionContext::new(&infcx);
     let cause = traits::ObligationCause::dummy();
     let traits::Normalized { value: result, obligations } =
diff --git a/src/librustc/middle/traits/error_reporting.rs b/src/librustc/middle/traits/error_reporting.rs
index 883c5e7bb40..d09bbc37fe4 100644
--- a/src/librustc/middle/traits/error_reporting.rs
+++ b/src/librustc/middle/traits/error_reporting.rs
@@ -182,7 +182,8 @@ fn report_on_unimplemented<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
 /// if the program type checks or not -- and they are unusual
 /// occurrences in any case.
 pub fn report_overflow_error<'a, 'tcx, T>(infcx: &InferCtxt<'a, 'tcx>,
-                                          obligation: &Obligation<'tcx, T>)
+                                          obligation: &Obligation<'tcx, T>,
+                                          suggest_increasing_limit: bool)
                                           -> !
     where T: fmt::Display + TypeFoldable<'tcx>
 {
@@ -192,7 +193,9 @@ pub fn report_overflow_error<'a, 'tcx, T>(infcx: &InferCtxt<'a, 'tcx>,
                                    "overflow evaluating the requirement `{}`",
                                    predicate);
 
-    suggest_new_overflow_limit(infcx.tcx, &mut err, obligation.cause.span);
+    if suggest_increasing_limit {
+        suggest_new_overflow_limit(infcx.tcx, &mut err, obligation.cause.span);
+    }
 
     note_obligation_cause(infcx, &mut err, obligation);
 
@@ -201,6 +204,142 @@ pub fn report_overflow_error<'a, 'tcx, T>(infcx: &InferCtxt<'a, 'tcx>,
     unreachable!();
 }
 
+/// Reports that a cycle was detected which led to overflow and halts
+/// compilation. This is equivalent to `report_overflow_error` except
+/// that we can give a more helpful error message (and, in particular,
+/// we do not suggest increasing the overflow limit, which is not
+/// going to help).
+pub fn report_overflow_error_cycle<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
+                                             cycle: &Vec<PredicateObligation<'tcx>>)
+                                             -> !
+{
+    assert!(cycle.len() > 1);
+
+    debug!("report_overflow_error_cycle(cycle length = {})", cycle.len());
+
+    let cycle = infcx.resolve_type_vars_if_possible(cycle);
+
+    debug!("report_overflow_error_cycle: cycle={:?}", cycle);
+
+    assert_eq!(&cycle[0].predicate, &cycle.last().unwrap().predicate);
+
+    try_report_overflow_error_type_of_infinite_size(infcx, &cycle);
+    report_overflow_error(infcx, &cycle[0], false);
+}
+
+/// If a cycle results from evaluated whether something is Sized, that
+/// is a particular special case that always results from a struct or
+/// enum definition that lacks indirection (e.g., `struct Foo { x: Foo
+/// }`). We wish to report a targeted error for this case.
+pub fn try_report_overflow_error_type_of_infinite_size<'a, 'tcx>(
+    infcx: &InferCtxt<'a, 'tcx>,
+    cycle: &[PredicateObligation<'tcx>])
+{
+    let sized_trait = match infcx.tcx.lang_items.sized_trait() {
+        Some(v) => v,
+        None => return,
+    };
+    let top_is_sized = {
+        match cycle[0].predicate {
+            ty::Predicate::Trait(ref data) => data.def_id() == sized_trait,
+            _ => false,
+        }
+    };
+    if !top_is_sized {
+        return;
+    }
+
+    // The only way to have a type of infinite size is to have,
+    // somewhere, a struct/enum type involved. Identify all such types
+    // and report the cycle to the user.
+
+    let struct_enum_tys: Vec<_> =
+        cycle.iter()
+             .flat_map(|obligation| match obligation.predicate {
+                 ty::Predicate::Trait(ref data) => {
+                     assert_eq!(data.def_id(), sized_trait);
+                     let self_ty = data.skip_binder().trait_ref.self_ty(); // (*)
+                     // (*) ok to skip binder because this is just
+                     // error reporting and regions don't really
+                     // matter
+                     match self_ty.sty {
+                         ty::TyEnum(..) | ty::TyStruct(..) => Some(self_ty),
+                         _ => None,
+                     }
+                 }
+                 _ => {
+                     infcx.tcx.sess.span_bug(obligation.cause.span,
+                                             &format!("Sized cycle involving non-trait-ref: {:?}",
+                                                      obligation.predicate));
+                 }
+             })
+             .collect();
+
+    assert!(!struct_enum_tys.is_empty());
+
+    // This is a bit tricky. We want to pick a "main type" in the
+    // listing that is local to the current crate, so we can give a
+    // good span to the user. But it might not be the first one in our
+    // cycle list. So find the first one that is local and then
+    // rotate.
+    let (main_index, main_def_id) =
+        struct_enum_tys.iter()
+                       .enumerate()
+                       .filter_map(|(index, ty)| match ty.sty {
+                           ty::TyEnum(adt_def, _) | ty::TyStruct(adt_def, _)
+                               if adt_def.did.is_local() =>
+                               Some((index, adt_def.did)),
+                           _ =>
+                               None,
+                       })
+                       .next()
+                       .unwrap(); // should always be SOME local type involved!
+
+    // Rotate so that the "main" type is at index 0.
+    let struct_enum_tys: Vec<_> =
+        struct_enum_tys.iter()
+                       .cloned()
+                       .skip(main_index)
+                       .chain(struct_enum_tys.iter().cloned().take(main_index))
+                       .collect();
+
+    let tcx = infcx.tcx;
+    let mut err = recursive_type_with_infinite_size_error(tcx, main_def_id);
+    let len = struct_enum_tys.len();
+    if len > 2 {
+        let span = tcx.map.span_if_local(main_def_id).unwrap();
+        err.fileline_note(span,
+                          &format!("type `{}` is embedded within `{}`...",
+                                   struct_enum_tys[0],
+                                   struct_enum_tys[1]));
+        for &next_ty in &struct_enum_tys[1..len-1] {
+            err.fileline_note(span,
+                              &format!("...which in turn is embedded within `{}`...", next_ty));
+        }
+        err.fileline_note(span,
+                          &format!("...which in turn is embedded within `{}`, \
+                                    completing the cycle.",
+                                   struct_enum_tys[len-1]));
+    }
+    err.emit();
+    infcx.tcx.sess.abort_if_errors();
+    unreachable!();
+}
+
+pub fn recursive_type_with_infinite_size_error<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                                     type_def_id: DefId)
+                                                     -> DiagnosticBuilder<'tcx>
+{
+    assert!(type_def_id.is_local());
+    let span = tcx.map.span_if_local(type_def_id).unwrap();
+    let mut err = struct_span_err!(tcx.sess, span, E0072, "recursive type `{}` has infinite size",
+                                   tcx.item_path_str(type_def_id));
+    err.fileline_help(span, &format!("insert indirection (e.g., a `Box`, `Rc`, or `&`) \
+                                      at some point to make `{}` representable",
+                                     tcx.item_path_str(type_def_id)));
+    err
+}
+
 pub fn report_selection_error<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>,
                                         obligation: &PredicateObligation<'tcx>,
                                         error: &SelectionError<'tcx>)
diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index 4f8f6b846a6..6ef8404cf07 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -10,19 +10,22 @@
 
 use middle::infer::InferCtxt;
 use middle::ty::{self, Ty, TypeFoldable};
-
+use rustc_data_structures::obligation_forest::{Backtrace, ObligationForest, Error};
+use std::iter;
 use syntax::ast;
 use util::common::ErrorReported;
-use util::nodemap::{FnvHashSet, NodeMap};
+use util::nodemap::{FnvHashMap, FnvHashSet, NodeMap};
 
 use super::CodeAmbiguity;
 use super::CodeProjectionError;
 use super::CodeSelectionError;
 use super::is_object_safe;
 use super::FulfillmentError;
+use super::FulfillmentErrorCode;
 use super::ObligationCause;
 use super::PredicateObligation;
 use super::project;
+use super::report_overflow_error_cycle;
 use super::select::SelectionContext;
 use super::Unimplemented;
 use super::util::predicate_for_builtin_bound;
@@ -57,12 +60,7 @@ pub struct FulfillmentContext<'tcx> {
 
     // A list of all obligations that have been registered with this
     // fulfillment context.
-    predicates: Vec<PredicateObligation<'tcx>>,
-
-    // Remembers the count of trait obligations that we have already
-    // attempted to select. This is used to avoid repeating work
-    // when `select_new_obligations` is called.
-    attempted_mark: usize,
+    predicates: ObligationForest<PendingPredicateObligation<'tcx>>,
 
     // A set of constraints that regionck must validate. Each
     // constraint has the form `T:'a`, meaning "some type `T` must
@@ -89,8 +87,6 @@ pub struct FulfillmentContext<'tcx> {
     // obligations (otherwise, it's easy to fail to walk to a
     // particular node-id).
     region_obligations: NodeMap<Vec<RegionObligation<'tcx>>>,
-
-    pub errors_will_be_reported: bool,
 }
 
 #[derive(Clone)]
@@ -100,31 +96,19 @@ pub struct RegionObligation<'tcx> {
     pub cause: ObligationCause<'tcx>,
 }
 
+#[derive(Clone, Debug)]
+pub struct PendingPredicateObligation<'tcx> {
+    pub obligation: PredicateObligation<'tcx>,
+    pub stalled_on: Vec<Ty<'tcx>>,
+}
+
 impl<'tcx> FulfillmentContext<'tcx> {
     /// Creates a new fulfillment context.
-    ///
-    /// `errors_will_be_reported` indicates whether ALL errors that
-    /// are generated by this fulfillment context will be reported to
-    /// the end user. This is used to inform caching, because it
-    /// allows us to conclude that traits that resolve successfully
-    /// will in fact always resolve successfully (in particular, it
-    /// guarantees that if some dependent obligation encounters a
-    /// problem, compilation will be aborted).  If you're not sure of
-    /// the right value here, pass `false`, as that is the more
-    /// conservative option.
-    ///
-    /// FIXME -- a better option would be to hold back on modifying
-    /// the global cache until we know that all dependent obligations
-    /// are also satisfied. In that case, we could actually remove
-    /// this boolean flag, and we'd also avoid the problem of squelching
-    /// duplicate errors that occur across fns.
-    pub fn new(errors_will_be_reported: bool) -> FulfillmentContext<'tcx> {
+    pub fn new() -> FulfillmentContext<'tcx> {
         FulfillmentContext {
             duplicate_set: FulfilledPredicates::new(),
-            predicates: Vec::new(),
-            attempted_mark: 0,
+            predicates: ObligationForest::new(),
             region_obligations: NodeMap(),
-            errors_will_be_reported: errors_will_be_reported,
         }
     }
 
@@ -198,7 +182,11 @@ impl<'tcx> FulfillmentContext<'tcx> {
         }
 
         debug!("register_predicate({:?})", obligation);
-        self.predicates.push(obligation);
+        let obligation = PendingPredicateObligation {
+            obligation: obligation,
+            stalled_on: vec![]
+        };
+        self.predicates.push_root(obligation);
     }
 
     pub fn region_obligations(&self,
@@ -216,14 +204,11 @@ impl<'tcx> FulfillmentContext<'tcx> {
                                    -> Result<(),Vec<FulfillmentError<'tcx>>>
     {
         try!(self.select_where_possible(infcx));
-
-        // Anything left is ambiguous.
-        let errors: Vec<FulfillmentError> =
-            self.predicates
-            .iter()
-            .map(|o| FulfillmentError::new((*o).clone(), CodeAmbiguity))
-            .collect();
-
+        let errors: Vec<_> =
+            self.predicates.to_errors(CodeAmbiguity)
+                           .into_iter()
+                           .map(|e| to_fulfillment_error(e))
+                           .collect();
         if errors.is_empty() {
             Ok(())
         } else {
@@ -231,119 +216,91 @@ impl<'tcx> FulfillmentContext<'tcx> {
         }
     }
 
-    /// Attempts to select obligations that were registered since the call to a selection routine.
-    /// This is used by the type checker to eagerly attempt to resolve obligations in hopes of
-    /// gaining type information. It'd be equally valid to use `select_where_possible` but it
-    /// results in `O(n^2)` performance (#18208).
-    pub fn select_new_obligations<'a>(&mut self,
-                                      infcx: &InferCtxt<'a,'tcx>)
-                                      -> Result<(),Vec<FulfillmentError<'tcx>>>
-    {
-        let mut selcx = SelectionContext::new(infcx);
-        self.select(&mut selcx, true)
-    }
-
     pub fn select_where_possible<'a>(&mut self,
                                      infcx: &InferCtxt<'a,'tcx>)
                                      -> Result<(),Vec<FulfillmentError<'tcx>>>
     {
         let mut selcx = SelectionContext::new(infcx);
-        self.select(&mut selcx, false)
+        self.select(&mut selcx)
     }
 
-    pub fn pending_obligations(&self) -> &[PredicateObligation<'tcx>] {
-        &self.predicates
+    pub fn pending_obligations(&self) -> Vec<PendingPredicateObligation<'tcx>> {
+        self.predicates.pending_obligations()
     }
 
     fn is_duplicate_or_add(&mut self,
                            tcx: &ty::ctxt<'tcx>,
                            predicate: &ty::Predicate<'tcx>)
                            -> bool {
-        // This is a kind of dirty hack to allow us to avoid "rederiving"
-        // things that we have already proven in other methods.
-        //
-        // The idea is that any predicate that doesn't involve type
-        // parameters and which only involves the 'static region (and
-        // no other regions) is universally solvable, since impls are global.
-        //
-        // This is particularly important since even if we have a
-        // cache hit in the selection context, we still wind up
-        // evaluating the 'nested obligations'.  This cache lets us
-        // skip those.
-
-        if self.errors_will_be_reported && predicate.is_global() {
-            tcx.fulfilled_predicates.borrow_mut().is_duplicate_or_add(predicate)
-        } else {
-            self.duplicate_set.is_duplicate_or_add(predicate)
+        // For "global" predicates -- that is, predicates that don't
+        // involve type parameters, inference variables, or regions
+        // other than 'static -- we can check the cache in the tcx,
+        // which allows us to leverage work from other threads. Note
+        // that we don't add anything to this cache yet (unlike the
+        // local cache).  This is because the tcx cache maintains the
+        // invariant that it only contains things that have been
+        // proven, and we have not yet proven that `predicate` holds.
+        if predicate.is_global() && tcx.fulfilled_predicates.borrow().is_duplicate(predicate) {
+            return true;
         }
+
+        // If `predicate` is not global, or not present in the tcx
+        // cache, we can still check for it in our local cache and add
+        // it if not present. Note that if we find this predicate in
+        // the local cache we can stop immediately, without reporting
+        // any errors, even though we don't know yet if it is
+        // true. This is because, while we don't yet know if the
+        // predicate holds, we know that this same fulfillment context
+        // already is in the process of finding out.
+        self.duplicate_set.is_duplicate_or_add(predicate)
     }
 
     /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it
     /// only attempts to select obligations that haven't been seen before.
     fn select<'a>(&mut self,
-                  selcx: &mut SelectionContext<'a, 'tcx>,
-                  only_new_obligations: bool)
+                  selcx: &mut SelectionContext<'a, 'tcx>)
                   -> Result<(),Vec<FulfillmentError<'tcx>>>
     {
-        debug!("select({} obligations, only_new_obligations={}) start",
-               self.predicates.len(),
-               only_new_obligations);
+        debug!("select(obligation-forest-size={})", self.predicates.len());
 
         let mut errors = Vec::new();
 
         loop {
-            let count = self.predicates.len();
-
-            debug!("select_where_possible({} obligations) iteration",
-                   count);
+            debug!("select_where_possible: starting another iteration");
 
-            let mut new_obligations = Vec::new();
-
-            // If we are only attempting obligations we haven't seen yet,
-            // then set `skip` to the number of obligations we've already
-            // seen.
-            let mut skip = if only_new_obligations {
-                self.attempted_mark
-            } else {
-                0
+            // Process pending obligations.
+            let outcome = {
+                let region_obligations = &mut self.region_obligations;
+                self.predicates.process_obligations(
+                    |obligation, backtrace| process_predicate(selcx,
+                                                              obligation,
+                                                              backtrace,
+                                                              region_obligations))
             };
 
-            // First pass: walk each obligation, retaining
-            // only those that we cannot yet process.
-            {
-                let region_obligations = &mut self.region_obligations;
-                self.predicates.retain(|predicate| {
-                    // Hack: Retain does not pass in the index, but we want
-                    // to avoid processing the first `start_count` entries.
-                    let processed =
-                        if skip == 0 {
-                            process_predicate(selcx, predicate,
-                                              &mut new_obligations, &mut errors, region_obligations)
-                        } else {
-                            skip -= 1;
-                            false
-                        };
-                    !processed
-                });
+            debug!("select_where_possible: outcome={:?}", outcome);
+
+            // these are obligations that were proven to be true.
+            for pending_obligation in outcome.completed {
+                let predicate = &pending_obligation.obligation.predicate;
+                if predicate.is_global() {
+                    selcx.tcx().fulfilled_predicates.borrow_mut()
+                                                    .is_duplicate_or_add(predicate);
+                }
             }
 
-            self.attempted_mark = self.predicates.len();
+            errors.extend(
+                outcome.errors.into_iter()
+                              .map(|e| to_fulfillment_error(e)));
 
-            if self.predicates.len() == count {
-                // Nothing changed.
+            // If nothing new was added, no need to keep looping.
+            if outcome.stalled {
                 break;
             }
-
-            // Now go through all the successful ones,
-            // registering any nested obligations for the future.
-            for new_obligation in new_obligations {
-                self.register_predicate_obligation(selcx.infcx(), new_obligation);
-            }
         }
 
-        debug!("select({} obligations, {} errors) done",
-               self.predicates.len(),
-               errors.len());
+        debug!("select({} predicates remaining, {} errors) done",
+               self.predicates.len(), errors.len());
 
         if errors.is_empty() {
             Ok(())
@@ -353,69 +310,168 @@ impl<'tcx> FulfillmentContext<'tcx> {
     }
 }
 
+/// Like `process_predicate1`, but wrap result into a pending predicate.
 fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
-                              obligation: &PredicateObligation<'tcx>,
-                              new_obligations: &mut Vec<PredicateObligation<'tcx>>,
-                              errors: &mut Vec<FulfillmentError<'tcx>>,
+                              pending_obligation: &mut PendingPredicateObligation<'tcx>,
+                              backtrace: Backtrace<PendingPredicateObligation<'tcx>>,
                               region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
-                              -> bool
+                              -> Result<Option<Vec<PendingPredicateObligation<'tcx>>>,
+                                        FulfillmentErrorCode<'tcx>>
 {
-    /*!
-     * Processes a predicate obligation and modifies the appropriate
-     * output array with the successful/error result.  Returns `false`
-     * if the predicate could not be processed due to insufficient
-     * type inference.
-     */
+    match process_predicate1(selcx, pending_obligation, backtrace, region_obligations) {
+        Ok(Some(v)) => {
+            // FIXME the right thing to do here, I think, is to permit
+            // DAGs. That is, we should detect whenever this predicate
+            // has appeared somewhere in the current tree./ If it's a
+            // parent, that's a cycle, and we should either error out
+            // or consider it ok. But if it's NOT a parent, we can
+            // ignore it, since it will be proven (or not) separately.
+            // However, this is a touch tricky, so I'm doing something
+            // a bit hackier for now so that the `huge-struct.rs` passes.
+
+            let retain_vec: Vec<_> = {
+                let mut dedup = FnvHashSet();
+                v.iter()
+                 .map(|o| {
+                     // Screen out obligations that we know globally
+                     // are true. This should really be the DAG check
+                     // mentioned above.
+                     if
+                         o.predicate.is_global() &&
+                         selcx.tcx().fulfilled_predicates.borrow().is_duplicate(&o.predicate)
+                     {
+                         return false;
+                     }
+
+                     // If we see two siblings that are exactly the
+                     // same, no need to add them twice.
+                     if !dedup.insert(&o.predicate) {
+                         return false;
+                     }
+
+                     true
+                 })
+                 .collect()
+            };
+
+            let pending_predicate_obligations =
+                v.into_iter()
+                 .zip(retain_vec)
+                 .flat_map(|(o, retain)| {
+                     if retain {
+                         Some(PendingPredicateObligation {
+                             obligation: o,
+                             stalled_on: vec![]
+                         })
+                     } else {
+                         None
+                     }
+                 })
+                .collect();
+
+            Ok(Some(pending_predicate_obligations))
+        }
+        Ok(None) => Ok(None),
+        Err(e) => Err(e)
+    }
+}
+
+/// Processes a predicate obligation and returns either:
+/// - `Ok(Some(v))` if the predicate is true, presuming that `v` are also true
+/// - `Ok(None)` if we don't have enough info to be sure
+/// - `Err` if the predicate does not hold
+fn process_predicate1<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
+                               pending_obligation: &mut PendingPredicateObligation<'tcx>,
+                               backtrace: Backtrace<PendingPredicateObligation<'tcx>>,
+                               region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
+                               -> Result<Option<Vec<PredicateObligation<'tcx>>>,
+                                         FulfillmentErrorCode<'tcx>>
+{
+    // if we were stalled on some unresolved variables, first check
+    // whether any of them have been resolved; if not, don't bother
+    // doing more work yet
+    if !pending_obligation.stalled_on.is_empty() {
+        if pending_obligation.stalled_on.iter().all(|&ty| {
+            let resolved_ty = selcx.infcx().resolve_type_vars_if_possible(&ty);
+            resolved_ty == ty // nothing changed here
+        }) {
+            debug!("process_predicate: pending obligation {:?} still stalled on {:?}",
+                   selcx.infcx().resolve_type_vars_if_possible(&pending_obligation.obligation),
+                   pending_obligation.stalled_on);
+            return Ok(None);
+        }
+        pending_obligation.stalled_on = vec![];
+    }
+
+    let obligation = &pending_obligation.obligation;
+
+    // If we exceed the recursion limit, take a moment to look for a
+    // cycle so we can give a better error report from here, where we
+    // have more context.
+    let recursion_limit = selcx.tcx().sess.recursion_limit.get();
+    if obligation.recursion_depth >= recursion_limit {
+        if let Some(cycle) = scan_for_cycle(obligation, &backtrace) {
+            report_overflow_error_cycle(selcx.infcx(), &cycle);
+        }
+    }
 
     match obligation.predicate {
         ty::Predicate::Trait(ref data) => {
+            if coinductive_match(selcx, obligation, data, &backtrace) {
+                return Ok(Some(vec![]));
+            }
+
             let trait_obligation = obligation.with(data.clone());
             match selcx.select(&trait_obligation) {
-                Ok(None) => {
-                    false
+                Ok(Some(vtable)) => {
+                    Ok(Some(vtable.nested_obligations()))
                 }
-                Ok(Some(s)) => {
-                    new_obligations.append(&mut s.nested_obligations());
-                    true
+                Ok(None) => {
+                    // This is a bit subtle: for the most part, the
+                    // only reason we can fail to make progress on
+                    // trait selection is because we don't have enough
+                    // information about the types in the trait. One
+                    // exception is that we sometimes haven't decided
+                    // what kind of closure a closure is. *But*, in
+                    // that case, it turns out, the type of the
+                    // closure will also change, because the closure
+                    // also includes references to its upvars as part
+                    // of its type, and those types are resolved at
+                    // the same time.
+                    pending_obligation.stalled_on =
+                        data.skip_binder() // ok b/c this check doesn't care about regions
+                        .input_types()
+                        .iter()
+                        .map(|t| selcx.infcx().resolve_type_vars_if_possible(t))
+                        .filter(|t| t.has_infer_types())
+                        .flat_map(|t| t.walk())
+                        .filter(|t| match t.sty { ty::TyInfer(_) => true, _ => false })
+                        .collect();
+
+                    debug!("process_predicate: pending obligation {:?} now stalled on {:?}",
+                           selcx.infcx().resolve_type_vars_if_possible(obligation),
+                           pending_obligation.stalled_on);
+
+                    Ok(None)
                 }
                 Err(selection_err) => {
-                    debug!("predicate: {:?} error: {:?}",
-                           obligation,
-                           selection_err);
-                    errors.push(
-                        FulfillmentError::new(
-                            obligation.clone(),
-                            CodeSelectionError(selection_err)));
-                    true
+                    Err(CodeSelectionError(selection_err))
                 }
             }
         }
 
         ty::Predicate::Equate(ref binder) => {
             match selcx.infcx().equality_predicate(obligation.cause.span, binder) {
-                Ok(()) => { }
-                Err(_) => {
-                    errors.push(
-                        FulfillmentError::new(
-                            obligation.clone(),
-                            CodeSelectionError(Unimplemented)));
-                }
+                Ok(()) => Ok(Some(Vec::new())),
+                Err(_) => Err(CodeSelectionError(Unimplemented)),
             }
-            true
         }
 
         ty::Predicate::RegionOutlives(ref binder) => {
             match selcx.infcx().region_outlives_predicate(obligation.cause.span, binder) {
-                Ok(()) => { }
-                Err(_) => {
-                    errors.push(
-                        FulfillmentError::new(
-                            obligation.clone(),
-                            CodeSelectionError(Unimplemented)));
-                }
+                Ok(()) => Ok(Some(Vec::new())),
+                Err(_) => Err(CodeSelectionError(Unimplemented)),
             }
-
-            true
         }
 
         ty::Predicate::TypeOutlives(ref binder) => {
@@ -431,10 +487,7 @@ fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
                         // If so, this obligation is an error (for now). Eventually we should be
                         // able to support additional cases here, like `for<'a> &'a str: 'a`.
                         None => {
-                            errors.push(
-                                FulfillmentError::new(
-                                    obligation.clone(),
-                                    CodeSelectionError(Unimplemented)))
+                            Err(CodeSelectionError(Unimplemented))
                         }
                         // Otherwise, we have something of the form
                         // `for<'a> T: 'a where 'a not in T`, which we can treat as `T: 'static`.
@@ -442,6 +495,7 @@ fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
                             register_region_obligation(t_a, ty::ReStatic,
                                                        obligation.cause.clone(),
                                                        region_obligations);
+                            Ok(Some(vec![]))
                         }
                     }
                 }
@@ -450,57 +504,93 @@ fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
                     register_region_obligation(t_a, r_b,
                                                obligation.cause.clone(),
                                                region_obligations);
+                    Ok(Some(vec![]))
                 }
             }
-            true
         }
 
         ty::Predicate::Projection(ref data) => {
             let project_obligation = obligation.with(data.clone());
-            let result = project::poly_project_and_unify_type(selcx, &project_obligation);
-            debug!("process_predicate: poly_project_and_unify_type({:?}) returned {:?}",
-                   project_obligation,
-                   result);
-            match result {
-                Ok(Some(obligations)) => {
-                    new_obligations.extend(obligations);
-                    true
-                }
-                Ok(None) => {
-                    false
-                }
-                Err(err) => {
-                    errors.push(
-                        FulfillmentError::new(
-                            obligation.clone(),
-                            CodeProjectionError(err)));
-                    true
-                }
+            match project::poly_project_and_unify_type(selcx, &project_obligation) {
+                Ok(v) => Ok(v),
+                Err(e) => Err(CodeProjectionError(e))
             }
         }
 
         ty::Predicate::ObjectSafe(trait_def_id) => {
             if !is_object_safe(selcx.tcx(), trait_def_id) {
-                errors.push(FulfillmentError::new(
-                    obligation.clone(),
-                    CodeSelectionError(Unimplemented)));
+                Err(CodeSelectionError(Unimplemented))
+            } else {
+                Ok(Some(Vec::new()))
             }
-            true
         }
 
         ty::Predicate::WellFormed(ty) => {
-            match ty::wf::obligations(selcx.infcx(), obligation.cause.body_id,
-                                      ty, obligation.cause.span) {
-                Some(obligations) => {
-                    new_obligations.extend(obligations);
-                    true
-                }
-                None => {
-                    false
+            Ok(ty::wf::obligations(selcx.infcx(), obligation.cause.body_id,
+                                   ty, obligation.cause.span))
+        }
+    }
+}
+
+/// For defaulted traits, we use a co-inductive strategy to solve, so
+/// that recursion is ok. This routine returns true if the top of the
+/// stack (`top_obligation` and `top_data`):
+/// - is a defaulted trait, and
+/// - it also appears in the backtrace at some position `X`; and,
+/// - all the predicates at positions `X..` between `X` an the top are
+///   also defaulted traits.
+fn coinductive_match<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
+                              top_obligation: &PredicateObligation<'tcx>,
+                              top_data: &ty::PolyTraitPredicate<'tcx>,
+                              backtrace: &Backtrace<PendingPredicateObligation<'tcx>>)
+                              -> bool
+{
+    if selcx.tcx().trait_has_default_impl(top_data.def_id()) {
+        debug!("coinductive_match: top_data={:?}", top_data);
+        for bt_obligation in backtrace.clone() {
+            debug!("coinductive_match: bt_obligation={:?}", bt_obligation);
+
+            // *Everything* in the backtrace must be a defaulted trait.
+            match bt_obligation.obligation.predicate {
+                ty::Predicate::Trait(ref data) => {
+                    if !selcx.tcx().trait_has_default_impl(data.def_id()) {
+                        debug!("coinductive_match: trait does not have default impl");
+                        break;
+                    }
                 }
+                _ => { break; }
+            }
+
+            // And we must find a recursive match.
+            if bt_obligation.obligation.predicate == top_obligation.predicate {
+                debug!("coinductive_match: found a match in the backtrace");
+                return true;
             }
         }
     }
+
+    false
+}
+
+fn scan_for_cycle<'a,'tcx>(top_obligation: &PredicateObligation<'tcx>,
+                           backtrace: &Backtrace<PendingPredicateObligation<'tcx>>)
+                           -> Option<Vec<PredicateObligation<'tcx>>>
+{
+    let mut map = FnvHashMap();
+    let all_obligations =
+        || iter::once(top_obligation)
+               .chain(backtrace.clone()
+                               .map(|p| &p.obligation));
+    for (index, bt_obligation) in all_obligations().enumerate() {
+        if let Some(&start) = map.get(&bt_obligation.predicate) {
+            // Found a cycle starting at position `start` and running
+            // until the current position (`index`).
+            return Some(all_obligations().skip(start).take(index - start + 1).cloned().collect());
+        } else {
+            map.insert(bt_obligation.predicate.clone(), index);
+        }
+    }
+    None
 }
 
 fn register_region_obligation<'tcx>(t_a: Ty<'tcx>,
@@ -536,3 +626,11 @@ impl<'tcx> FulfilledPredicates<'tcx> {
         !self.set.insert(key.clone())
     }
 }
+
+fn to_fulfillment_error<'tcx>(
+    error: Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>)
+    -> FulfillmentError<'tcx>
+{
+    let obligation = error.backtrace.into_iter().next().unwrap().obligation;
+    FulfillmentError::new(obligation, error.error)
+}
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 6cf841cc477..8fecffcea9f 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -28,8 +28,10 @@ use syntax::ast;
 use syntax::codemap::{Span, DUMMY_SP};
 
 pub use self::error_reporting::TraitErrorKey;
+pub use self::error_reporting::recursive_type_with_infinite_size_error;
 pub use self::error_reporting::report_fulfillment_errors;
 pub use self::error_reporting::report_overflow_error;
+pub use self::error_reporting::report_overflow_error_cycle;
 pub use self::error_reporting::report_selection_error;
 pub use self::error_reporting::report_object_safety_error;
 pub use self::coherence::orphan_check;
@@ -356,7 +358,7 @@ pub fn type_known_to_meet_builtin_bound<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
         // this function's result remains infallible, we must confirm
         // that guess. While imperfect, I believe this is sound.
 
-        let mut fulfill_cx = FulfillmentContext::new(false);
+        let mut fulfill_cx = FulfillmentContext::new();
 
         // We can use a dummy node-id here because we won't pay any mind
         // to region obligations that arise (there shouldn't really be any
@@ -434,8 +436,9 @@ pub fn normalize_param_env_or_error<'a,'tcx>(unnormalized_env: ty::ParameterEnvi
 
     let elaborated_env = unnormalized_env.with_caller_bounds(predicates);
 
-    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(elaborated_env), false);
-    let predicates = match fully_normalize(&infcx, cause,
+    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(elaborated_env));
+    let predicates = match fully_normalize(&infcx,
+                                           cause,
                                            &infcx.parameter_environment.caller_bounds) {
         Ok(predicates) => predicates,
         Err(errors) => {
@@ -444,6 +447,9 @@ pub fn normalize_param_env_or_error<'a,'tcx>(unnormalized_env: ty::ParameterEnvi
         }
     };
 
+    debug!("normalize_param_env_or_error: normalized predicates={:?}",
+           predicates);
+
     let free_regions = FreeRegionMap::new();
     infcx.resolve_regions_and_report_errors(&free_regions, body_id);
     let predicates = match infcx.fully_resolve(&predicates) {
@@ -462,6 +468,9 @@ pub fn normalize_param_env_or_error<'a,'tcx>(unnormalized_env: ty::ParameterEnvi
         }
     };
 
+    debug!("normalize_param_env_or_error: resolved predicates={:?}",
+           predicates);
+
     infcx.parameter_environment.with_caller_bounds(predicates)
 }
 
@@ -471,7 +480,7 @@ pub fn fully_normalize<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>,
                                   -> Result<T, Vec<FulfillmentError<'tcx>>>
     where T : TypeFoldable<'tcx>
 {
-    debug!("normalize_param_env(value={:?})", value);
+    debug!("fully_normalize(value={:?})", value);
 
     let mut selcx = &mut SelectionContext::new(infcx);
     // FIXME (@jroesch) ISSUE 26721
@@ -487,20 +496,28 @@ pub fn fully_normalize<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>,
     //
     // I think we should probably land this refactor and then come
     // back to this is a follow-up patch.
-    let mut fulfill_cx = FulfillmentContext::new(false);
+    let mut fulfill_cx = FulfillmentContext::new();
 
     let Normalized { value: normalized_value, obligations } =
         project::normalize(selcx, cause, value);
-    debug!("normalize_param_env: normalized_value={:?} obligations={:?}",
+    debug!("fully_normalize: normalized_value={:?} obligations={:?}",
            normalized_value,
            obligations);
     for obligation in obligations {
         fulfill_cx.register_predicate_obligation(selcx.infcx(), obligation);
     }
 
-    try!(fulfill_cx.select_all_or_error(infcx));
+    debug!("fully_normalize: select_all_or_error start");
+    match fulfill_cx.select_all_or_error(infcx) {
+        Ok(()) => { }
+        Err(e) => {
+            debug!("fully_normalize: error={:?}", e);
+            return Err(e);
+        }
+    }
+    debug!("fully_normalize: select_all_or_error complete");
     let resolved_value = infcx.resolve_type_vars_if_possible(&normalized_value);
-    debug!("normalize_param_env: resolved_value={:?}", resolved_value);
+    debug!("fully_normalize: resolved_value={:?}", resolved_value);
     Ok(resolved_value)
 }
 
diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs
index e9d7b330d07..c363425db85 100644
--- a/src/librustc/middle/traits/project.rs
+++ b/src/librustc/middle/traits/project.rs
@@ -479,7 +479,7 @@ fn project_type<'cx,'tcx>(
     let recursion_limit = selcx.tcx().sess.recursion_limit.get();
     if obligation.recursion_depth >= recursion_limit {
         debug!("project: overflow!");
-        report_overflow_error(selcx.infcx(), &obligation);
+        report_overflow_error(selcx.infcx(), &obligation, true);
     }
 
     let obligation_trait_ref =
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index f6d0da904a4..75992b6849b 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -711,7 +711,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // not update) the cache.
         let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
         if stack.obligation.recursion_depth >= recursion_limit {
-            report_overflow_error(self.infcx(), &stack.obligation);
+            report_overflow_error(self.infcx(), &stack.obligation, true);
         }
 
         // Check the cache. Note that we skolemize the trait-ref
@@ -2124,6 +2124,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                            nested: ty::Binder<Vec<Ty<'tcx>>>)
                            -> VtableBuiltinData<PredicateObligation<'tcx>>
     {
+        debug!("vtable_builtin_data(obligation={:?}, bound={:?}, nested={:?})",
+               obligation, bound, nested);
+
         let trait_def = match self.tcx().lang_items.from_builtin_kind(bound) {
             Ok(def_id) => def_id,
             Err(_) => {
diff --git a/src/librustc/middle/ty/util.rs b/src/librustc/middle/ty/util.rs
index af23efe2bf4..03145951367 100644
--- a/src/librustc/middle/ty/util.rs
+++ b/src/librustc/middle/ty/util.rs
@@ -182,7 +182,7 @@ impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> {
         let tcx = self.tcx;
 
         // FIXME: (@jroesch) float this code up
-        let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(self.clone()), false);
+        let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(self.clone()));
 
         let adt = match self_type.sty {
             ty::TyStruct(struct_def, substs) => {
@@ -655,7 +655,7 @@ impl<'tcx> ty::TyS<'tcx> {
                        -> bool
     {
         let tcx = param_env.tcx;
-        let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(param_env.clone()), false);
+        let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(param_env.clone()));
 
         let is_impld = traits::type_known_to_meet_builtin_bound(&infcx,
                                                                 self, bound, span);
diff --git a/src/librustc_borrowck/borrowck/check_loans.rs b/src/librustc_borrowck/borrowck/check_loans.rs
index 2d30b827750..5e8495ceddd 100644
--- a/src/librustc_borrowck/borrowck/check_loans.rs
+++ b/src/librustc_borrowck/borrowck/check_loans.rs
@@ -202,7 +202,7 @@ pub fn check_loans<'a, 'b, 'c, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
     debug!("check_loans(body id={})", body.id);
 
     let param_env = ty::ParameterEnvironment::for_item(bccx.tcx, fn_id);
-    let infcx = infer::new_infer_ctxt(bccx.tcx, &bccx.tcx.tables, Some(param_env), false);
+    let infcx = infer::new_infer_ctxt(bccx.tcx, &bccx.tcx.tables, Some(param_env));
 
     let mut clcx = CheckLoanCtxt {
         bccx: bccx,
diff --git a/src/librustc_borrowck/borrowck/gather_loans/mod.rs b/src/librustc_borrowck/borrowck/gather_loans/mod.rs
index 6f6ce67380b..8cf10cb9b05 100644
--- a/src/librustc_borrowck/borrowck/gather_loans/mod.rs
+++ b/src/librustc_borrowck/borrowck/gather_loans/mod.rs
@@ -55,7 +55,7 @@ pub fn gather_loans_in_fn<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
     };
 
     let param_env = ty::ParameterEnvironment::for_item(bccx.tcx, fn_id);
-    let infcx = infer::new_infer_ctxt(bccx.tcx, &bccx.tcx.tables, Some(param_env), false);
+    let infcx = infer::new_infer_ctxt(bccx.tcx, &bccx.tcx.tables, Some(param_env));
     {
         let mut euv = euv::ExprUseVisitor::new(&mut glcx, &infcx);
         euv.walk_fn(decl, body);
@@ -525,7 +525,7 @@ struct StaticInitializerCtxt<'a, 'tcx: 'a> {
 impl<'a, 'tcx, 'v> Visitor<'v> for StaticInitializerCtxt<'a, 'tcx> {
     fn visit_expr(&mut self, ex: &Expr) {
         if let hir::ExprAddrOf(mutbl, ref base) = ex.node {
-            let infcx = infer::new_infer_ctxt(self.bccx.tcx, &self.bccx.tcx.tables, None, false);
+            let infcx = infer::new_infer_ctxt(self.bccx.tcx, &self.bccx.tcx.tables, None);
             let mc = mc::MemCategorizationContext::new(&infcx);
             let base_cmt = mc.cat_expr(&**base).unwrap();
             let borrow_kind = ty::BorrowKind::from_mutbl(mutbl);
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index ef64d7dde09..1fbbdf17455 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -24,17 +24,21 @@
       html_favicon_url = "https://www.rust-lang.org/favicon.ico",
       html_root_url = "https://doc.rust-lang.org/nightly/")]
 
-#![feature(rustc_private, staged_api)]
 #![feature(hashmap_hasher)]
+#![feature(nonzero)]
+#![feature(rustc_private)]
+#![feature(staged_api)]
 
 #![cfg_attr(test, feature(test))]
 
+extern crate core;
 #[macro_use] extern crate log;
 extern crate serialize as rustc_serialize; // used by deriving
 
 pub mod bitvec;
 pub mod graph;
 pub mod ivar;
+pub mod obligation_forest;
 pub mod snapshot_vec;
 pub mod transitive_relation;
 pub mod unify;
diff --git a/src/librustc_data_structures/obligation_forest/README.md b/src/librustc_data_structures/obligation_forest/README.md
new file mode 100644
index 00000000000..1ffe07bb43b
--- /dev/null
+++ b/src/librustc_data_structures/obligation_forest/README.md
@@ -0,0 +1,80 @@
+The `ObligationForest` is a utility data structure used in trait
+matching to track the set of outstanding obligations (those not yet
+resolved to success or error). It also tracks the "backtrace" of each
+pending obligation (why we are trying to figure this out in the first
+place).
+
+### External view
+
+`ObligationForest` supports two main public operations (there are a
+few others not discussed here):
+
+1. Add a new root obligation (`push_root`).
+2. Process the pending obligations (`process_obligations`).
+
+When a new obligation `N` is added, it becomes the root of an
+obligation tree. This tree is a singleton to start, so `N` is both the
+root and the only leaf. Each time the `process_obligations` method is
+called, it will invoke its callback with every pending obligation (so
+that will include `N`, the first time). The callback shoud process the
+obligation `O` that it is given and return one of three results:
+
+- `Ok(None)` -> ambiguous result. Obligation was neither a success
+  nor a failure. It is assumed that further attempts to process the
+  obligation will yield the same result unless something in the
+  surrounding environment changes.
+- `Ok(Some(C))` - the obligation was *shallowly successful*. The
+  vector `C` is a list of subobligations. The meaning of this is that
+  `O` was successful on the assumption that all the obligations in `C`
+  are also successful. Therefore, `O` is only considered a "true"
+  success if `C` is empty. Otherwise, `O` is put into a suspended
+  state and the obligations in `C` become the new pending
+  obligations. They will be processed the next time you call
+  `process_obligations`.
+- `Err(E)` -> obligation failed with error `E`. We will collect this
+  error and return it from `process_obligations`, along with the
+  "backtrace" of obligations (that is, the list of obligations up to
+  and including the root of the failed obligation). No further
+  obligations from that same tree will be processed, since the tree is
+  now considered to be in error.
+
+When the call to `process_obligations` completes, you get back an `Outcome`,
+which includes three bits of information:
+
+- `completed`: a list of obligations where processing was fully
+  completed without error (meaning that all transitive subobligations
+  have also been completed). So, for example, if the callback from
+  `process_obligations` returns `Ok(Some(C))` for some obligation `O`,
+  then `O` will be considered completed right away if `C` is the
+  empty vector. Otherwise it will only be considered completed once
+  all the obligations in `C` have been found completed.
+- `errors`: a list of errors that occurred and associated backtraces
+  at the time of error, which can be used to give context to the user.
+- `stalled`: if true, then none of the existing obligations were
+  *shallowly successful* (that is, no callback returned `Ok(Some(_))`).
+  This implies that all obligations were either errors or returned an
+  ambiguous result, which means that any further calls to
+  `process_obligations` would simply yield back further ambiguous
+  results. This is used by the `FulfillmentContext` to decide when it
+  has reached a steady state.
+  
+#### Snapshots
+
+The `ObligationForest` supports a limited form of snapshots; see
+`start_snapshot`; `commit_snapshot`; and `rollback_snapshot`. In
+particular, you can use a snapshot to roll back new root
+obligations. However, it is an error to attempt to
+`process_obligations` during a snapshot.
+
+### Implementation details
+
+For the most part, comments specific to the implementation are in the
+code.  This file only contains a very high-level overview. Basically,
+the forest is stored in a vector. Each element of the vector is a node
+in some tree. Each node in the vector has the index of an (optional)
+parent and (for convenience) its root (which may be itself). It also
+has a current state, described by `NodeState`. After each
+processing step, we compress the vector to remove completed and error
+nodes, which aren't needed anymore.
+
+  
diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
new file mode 100644
index 00000000000..0d92a2b158f
--- /dev/null
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -0,0 +1,462 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! The `ObligationForest` is a utility data structure used in trait
+//! matching to track the set of outstanding obligations (those not
+//! yet resolved to success or error). It also tracks the "backtrace"
+//! of each pending obligation (why we are trying to figure this out
+//! in the first place). See README.md for a general overview of how
+//! to use this class.
+
+use std::fmt::Debug;
+use std::mem;
+
+mod node_index;
+
+#[cfg(test)]
+mod test;
+
+pub struct ObligationForest<O> {
+    /// The list of obligations. In between calls to
+    /// `process_obligations`, this list only contains nodes in the
+    /// `Pending` or `Success` state (with a non-zero number of
+    /// incomplete children). During processing, some of those nodes
+    /// may be changed to the error state, or we may find that they
+    /// are completed (That is, `num_incomplete_children` drops to 0).
+    /// At the end of processing, those nodes will be removed by a
+    /// call to `compress`.
+    ///
+    /// At all times we maintain the invariant that every node appears
+    /// at a higher index than its parent. This is needed by the
+    /// backtrace iterator (which uses `split_at`).
+    nodes: Vec<Node<O>>,
+    snapshots: Vec<usize>
+}
+
+pub struct Snapshot {
+    len: usize,
+}
+
+pub use self::node_index::NodeIndex;
+
+struct Node<O> {
+    state: NodeState<O>,
+    parent: Option<NodeIndex>,
+    root: NodeIndex, // points to the root, which may be the current node
+}
+
+/// The state of one node in some tree within the forest. This
+/// represents the current state of processing for the obligation (of
+/// type `O`) associated with this node.
+#[derive(Debug)]
+enum NodeState<O> {
+    /// Obligation not yet resolved to success or error.
+    Pending { obligation: O },
+
+    /// Obligation resolved to success; `num_incomplete_children`
+    /// indicates the number of children still in an "incomplete"
+    /// state. Incomplete means that either the child is still
+    /// pending, or it has children which are incomplete. (Basically,
+    /// there is pending work somewhere in the subtree of the child.)
+    ///
+    /// Once all children have completed, success nodes are removed
+    /// from the vector by the compression step.
+    Success { obligation: O, num_incomplete_children: usize },
+
+    /// This obligation was resolved to an error. Error nodes are
+    /// removed from the vector by the compression step.
+    Error,
+}
+
+#[derive(Debug)]
+pub struct Outcome<O,E> {
+    /// Obligations that were completely evaluated, including all
+    /// (transitive) subobligations.
+    pub completed: Vec<O>,
+
+    /// Backtrace of obligations that were found to be in error.
+    pub errors: Vec<Error<O,E>>,
+
+    /// If true, then we saw no successful obligations, which means
+    /// there is no point in further iteration. This is based on the
+    /// assumption that when trait matching returns `Err` or
+    /// `Ok(None)`, those results do not affect environmental
+    /// inference state. (Note that if we invoke `process_obligations`
+    /// with no pending obligations, stalled will be true.)
+    pub stalled: bool,
+}
+
+#[derive(Debug, PartialEq, Eq)]
+pub struct Error<O,E> {
+    pub error: E,
+    pub backtrace: Vec<O>,
+}
+
+impl<O: Debug> ObligationForest<O> {
+    pub fn new() -> ObligationForest<O> {
+        ObligationForest {
+            nodes: vec![],
+            snapshots: vec![]
+        }
+    }
+
+    /// Return the total number of nodes in the forest that have not
+    /// yet been fully resolved.
+    pub fn len(&self) -> usize {
+        self.nodes.len()
+    }
+
+    pub fn start_snapshot(&mut self) -> Snapshot {
+        self.snapshots.push(self.nodes.len());
+        Snapshot { len: self.snapshots.len() }
+    }
+
+    pub fn commit_snapshot(&mut self, snapshot: Snapshot) {
+        assert_eq!(snapshot.len, self.snapshots.len());
+        let nodes_len = self.snapshots.pop().unwrap();
+        assert!(self.nodes.len() >= nodes_len);
+    }
+
+    pub fn rollback_snapshot(&mut self, snapshot: Snapshot) {
+        // Check that we are obeying stack discipline.
+        assert_eq!(snapshot.len, self.snapshots.len());
+        let nodes_len = self.snapshots.pop().unwrap();
+
+        // The only action permitted while in a snapshot is to push
+        // new root obligations. Because no processing will have been
+        // done, those roots should still be in the pending state.
+        debug_assert!(self.nodes[nodes_len..].iter().all(|n| match n.state {
+            NodeState::Pending { .. } => true,
+            _ => false,
+        }));
+
+        self.nodes.truncate(nodes_len);
+    }
+
+    pub fn in_snapshot(&self) -> bool {
+        !self.snapshots.is_empty()
+    }
+
+    /// Adds a new tree to the forest.
+    ///
+    /// This CAN be done during a snapshot.
+    pub fn push_root(&mut self, obligation: O) {
+        let index = NodeIndex::new(self.nodes.len());
+        self.nodes.push(Node::new(index, None, obligation));
+    }
+
+    /// Convert all remaining obligations to the given error.
+    ///
+    /// This cannot be done during a snapshot.
+    pub fn to_errors<E:Clone>(&mut self, error: E) -> Vec<Error<O,E>> {
+        assert!(!self.in_snapshot());
+        let mut errors = vec![];
+        for index in 0..self.nodes.len() {
+            debug_assert!(!self.nodes[index].is_popped());
+            self.inherit_error(index);
+            if let NodeState::Pending { .. } = self.nodes[index].state {
+                let backtrace = self.backtrace(index);
+                errors.push(Error { error: error.clone(), backtrace: backtrace });
+            }
+        }
+        let successful_obligations = self.compress();
+        assert!(successful_obligations.is_empty());
+        errors
+    }
+
+    /// Returns the set of obligations that are in a pending state.
+    pub fn pending_obligations(&self) -> Vec<O> where O: Clone {
+        self.nodes.iter()
+                  .filter_map(|n| match n.state {
+                      NodeState::Pending { ref obligation } => Some(obligation),
+                      _ => None,
+                  })
+                  .cloned()
+                  .collect()
+    }
+
+    /// Process the obligations.
+    ///
+    /// This CANNOT be unrolled (presently, at least).
+    pub fn process_obligations<E,F>(&mut self, mut action: F) -> Outcome<O,E>
+        where E: Debug, F: FnMut(&mut O, Backtrace<O>) -> Result<Option<Vec<O>>, E>
+    {
+        debug!("process_obligations(len={})", self.nodes.len());
+        assert!(!self.in_snapshot()); // cannot unroll this action
+
+        let mut errors = vec![];
+        let mut stalled = true;
+
+        // We maintain the invariant that the list is in pre-order, so
+        // parents occur before their children. Also, whenever an
+        // error occurs, we propagate it from the child all the way to
+        // the root of the tree. Together, these two facts mean that
+        // when we visit a node, we can check if its root is in error,
+        // and we will find out if any prior node within this forest
+        // encountered an error.
+
+        for index in 0..self.nodes.len() {
+            debug_assert!(!self.nodes[index].is_popped());
+            self.inherit_error(index);
+
+            debug!("process_obligations: node {} == {:?}",
+                   index, self.nodes[index].state);
+
+            let result = {
+                let parent = self.nodes[index].parent;
+                let (prefix, suffix) = self.nodes.split_at_mut(index);
+                let backtrace = Backtrace::new(prefix, parent);
+                match suffix[0].state {
+                    NodeState::Error |
+                    NodeState::Success { .. } =>
+                        continue,
+                    NodeState::Pending { ref mut obligation } =>
+                        action(obligation, backtrace),
+                }
+            };
+
+            debug!("process_obligations: node {} got result {:?}", index, result);
+
+            match result {
+                Ok(None) => {
+                    // no change in state
+                }
+                Ok(Some(children)) => {
+                    // if we saw a Some(_) result, we are not (yet) stalled
+                    stalled = false;
+                    self.success(index, children);
+                }
+                Err(err) => {
+                    let backtrace = self.backtrace(index);
+                    errors.push(Error { error: err, backtrace: backtrace });
+                }
+            }
+        }
+
+        // Now we have to compress the result
+        let successful_obligations = self.compress();
+
+        debug!("process_obligations: complete");
+
+        Outcome {
+            completed: successful_obligations,
+            errors: errors,
+            stalled: stalled,
+        }
+    }
+
+    /// Indicates that node `index` has been processed successfully,
+    /// yielding `children` as the derivative work. If children is an
+    /// empty vector, this will update the ref count on the parent of
+    /// `index` to indicate that a child has completed
+    /// successfully. Otherwise, adds new nodes to represent the child
+    /// work.
+    fn success(&mut self, index: usize, children: Vec<O>) {
+        debug!("success(index={}, children={:?})", index, children);
+
+        let num_incomplete_children = children.len();
+
+        if num_incomplete_children == 0 {
+            // if there is no work left to be done, decrement parent's ref count
+            self.update_parent(index);
+        } else {
+            // create child work
+            let root_index = self.nodes[index].root;
+            let node_index = NodeIndex::new(index);
+            self.nodes.extend(
+                children.into_iter()
+                        .map(|o| Node::new(root_index, Some(node_index), o)));
+        }
+
+        // change state from `Pending` to `Success`, temporarily swapping in `Error`
+        let state = mem::replace(&mut self.nodes[index].state, NodeState::Error);
+        self.nodes[index].state = match state {
+            NodeState::Pending { obligation } =>
+                NodeState::Success { obligation: obligation,
+                                     num_incomplete_children: num_incomplete_children },
+            NodeState::Success { .. } |
+            NodeState::Error =>
+                unreachable!()
+        };
+    }
+
+    /// Decrements the ref count on the parent of `child`; if the
+    /// parent's ref count then reaches zero, proceeds recursively.
+    fn update_parent(&mut self, child: usize) {
+        debug!("update_parent(child={})", child);
+        if let Some(parent) = self.nodes[child].parent {
+            let parent = parent.get();
+            match self.nodes[parent].state {
+                NodeState::Success { ref mut num_incomplete_children, .. } => {
+                    *num_incomplete_children -= 1;
+                    if *num_incomplete_children > 0 {
+                        return;
+                    }
+                }
+                _ => unreachable!(),
+            }
+            self.update_parent(parent);
+        }
+    }
+
+    /// If the root of `child` is in an error state, places `child`
+    /// into an error state. This is used during processing so that we
+    /// skip the remaining obligations from a tree once some other
+    /// node in the tree is found to be in error.
+    fn inherit_error(&mut self, child: usize) {
+        let root = self.nodes[child].root.get();
+        if let NodeState::Error = self.nodes[root].state {
+            self.nodes[child].state = NodeState::Error;
+        }
+    }
+
+    /// Returns a vector of obligations for `p` and all of its
+    /// ancestors, putting them into the error state in the process.
+    /// The fact that the root is now marked as an error is used by
+    /// `inherit_error` above to propagate the error state to the
+    /// remainder of the tree.
+    fn backtrace(&mut self, mut p: usize) -> Vec<O> {
+        let mut trace = vec![];
+        loop {
+            let state = mem::replace(&mut self.nodes[p].state, NodeState::Error);
+            match state {
+                NodeState::Pending { obligation } |
+                NodeState::Success { obligation, .. } => {
+                    trace.push(obligation);
+                }
+                NodeState::Error => {
+                    // we should not encounter an error, because if
+                    // there was an error in the ancestors, it should
+                    // have been propagated down and we should never
+                    // have tried to process this obligation
+                    panic!("encountered error in node {:?} when collecting stack trace", p);
+                }
+            }
+
+            // loop to the parent
+            match self.nodes[p].parent {
+                Some(q) => { p = q.get(); }
+                None => { return trace; }
+            }
+        }
+    }
+
+    /// Compresses the vector, removing all popped nodes. This adjusts
+    /// the indices and hence invalidates any outstanding
+    /// indices. Cannot be used during a transaction.
+    fn compress(&mut self) -> Vec<O> {
+        assert!(!self.in_snapshot()); // didn't write code to unroll this action
+        let mut rewrites: Vec<_> = (0..self.nodes.len()).collect();
+
+        // Finish propagating error state. Note that in this case we
+        // only have to check immediate parents, rather than all
+        // ancestors, because all errors have already occurred that
+        // are going to occur.
+        let nodes_len = self.nodes.len();
+        for i in 0..nodes_len {
+            if !self.nodes[i].is_popped() {
+                self.inherit_error(i);
+            }
+        }
+
+        // Now go through and move all nodes that are either
+        // successful or which have an error over into to the end of
+        // the list, preserving the relative order of the survivors
+        // (which is important for the `inherit_error` logic).
+        let mut dead = 0;
+        for i in 0..nodes_len {
+            if self.nodes[i].is_popped() {
+                dead += 1;
+            } else if dead > 0 {
+                self.nodes.swap(i, i - dead);
+                rewrites[i] -= dead;
+            }
+        }
+
+        // Pop off all the nodes we killed and extract the success
+        // stories.
+        let successful =
+            (0 .. dead).map(|_| self.nodes.pop().unwrap())
+                       .flat_map(|node| match node.state {
+                           NodeState::Error => None,
+                           NodeState::Pending { .. } => unreachable!(),
+                           NodeState::Success { obligation, num_incomplete_children } => {
+                               assert_eq!(num_incomplete_children, 0);
+                               Some(obligation)
+                           }
+                       })
+                       .collect();
+
+        // Adjust the parent indices, since we compressed things.
+        for node in &mut self.nodes {
+            if let Some(ref mut index) = node.parent {
+                let new_index = rewrites[index.get()];
+                debug_assert!(new_index < (nodes_len - dead));
+                *index = NodeIndex::new(new_index);
+            }
+
+            node.root = NodeIndex::new(rewrites[node.root.get()]);
+        }
+
+        successful
+    }
+}
+
+impl<O> Node<O> {
+    fn new(root: NodeIndex, parent: Option<NodeIndex>, obligation: O) -> Node<O> {
+        Node {
+            parent: parent,
+            state: NodeState::Pending { obligation: obligation },
+            root: root
+        }
+    }
+
+    fn is_popped(&self) -> bool {
+        match self.state {
+            NodeState::Pending { .. } => false,
+            NodeState::Success { num_incomplete_children, .. } => num_incomplete_children == 0,
+            NodeState::Error => true,
+        }
+    }
+}
+
+#[derive(Clone)]
+pub struct Backtrace<'b, O: 'b> {
+    nodes: &'b [Node<O>],
+    pointer: Option<NodeIndex>,
+}
+
+impl<'b, O> Backtrace<'b, O> {
+    fn new(nodes: &'b [Node<O>], pointer: Option<NodeIndex>) -> Backtrace<'b, O> {
+        Backtrace { nodes: nodes, pointer: pointer }
+    }
+}
+
+impl<'b, O> Iterator for Backtrace<'b, O> {
+    type Item = &'b O;
+
+    fn next(&mut self) -> Option<&'b O> {
+        debug!("Backtrace: self.pointer = {:?}", self.pointer);
+        if let Some(p) = self.pointer {
+            self.pointer = self.nodes[p.get()].parent;
+            match self.nodes[p.get()].state {
+                NodeState::Pending { ref obligation } |
+                NodeState::Success { ref obligation, .. } => {
+                    Some(obligation)
+                }
+                NodeState::Error => {
+                    panic!("Backtrace encountered an error.");
+                }
+            }
+        } else {
+            None
+        }
+    }
+}
diff --git a/src/librustc_data_structures/obligation_forest/node_index.rs b/src/librustc_data_structures/obligation_forest/node_index.rs
new file mode 100644
index 00000000000..465cee0b60c
--- /dev/null
+++ b/src/librustc_data_structures/obligation_forest/node_index.rs
@@ -0,0 +1,31 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use core::nonzero::NonZero;
+use std::u32;
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub struct NodeIndex {
+    index: NonZero<u32>
+}
+
+impl NodeIndex {
+    pub fn new(value: usize) -> NodeIndex {
+        assert!(value < (u32::MAX as usize));
+        unsafe {
+            NodeIndex { index: NonZero::new((value as u32) + 1) }
+        }
+    }
+
+    pub fn get(self) -> usize {
+        (*self.index - 1) as usize
+    }
+}
+
diff --git a/src/librustc_data_structures/obligation_forest/test.rs b/src/librustc_data_structures/obligation_forest/test.rs
new file mode 100644
index 00000000000..519b282a6a8
--- /dev/null
+++ b/src/librustc_data_structures/obligation_forest/test.rs
@@ -0,0 +1,206 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use super::{ObligationForest, Outcome, Error};
+
+#[test]
+fn push_pop() {
+    let mut forest = ObligationForest::new();
+    forest.push_root("A");
+    forest.push_root("B");
+    forest.push_root("C");
+
+    // first round, B errors out, A has subtasks, and C completes, creating this:
+    //      A |-> A.1
+    //        |-> A.2
+    //        |-> A.3
+    let Outcome { completed: ok, errors: err, .. } = forest.process_obligations(|obligation, _| {
+        match *obligation {
+            "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
+            "B" => Err("B is for broken"),
+            "C" => Ok(Some(vec![])),
+            _ => unreachable!(),
+        }
+    });
+    assert_eq!(ok, vec!["C"]);
+    assert_eq!(err, vec![Error {error: "B is for broken",
+                                backtrace: vec!["B"]}]);
+
+    // second round: two delays, one success, creating an uneven set of subtasks:
+    //      A |-> A.1
+    //        |-> A.2
+    //        |-> A.3 |-> A.3.i
+    //      D |-> D.1
+    //        |-> D.2
+    forest.push_root("D");
+    let Outcome { completed: ok, errors: err, .. }: Outcome<&'static str, ()> =
+        forest.process_obligations(|obligation, _| {
+            match *obligation {
+                "A.1" => Ok(None),
+                "A.2" => Ok(None),
+                "A.3" => Ok(Some(vec!["A.3.i"])),
+                "D" => Ok(Some(vec!["D.1", "D.2"])),
+                _ => unreachable!(),
+            }
+        });
+    assert_eq!(ok, Vec::<&'static str>::new());
+    assert_eq!(err, Vec::new());
+
+
+    // third round: ok in A.1 but trigger an error in A.2. Check that it
+    // propagates to A.3.i, but not D.1 or D.2.
+    //      D |-> D.1 |-> D.1.i
+    //        |-> D.2 |-> D.2.i
+    let Outcome { completed: ok, errors: err, .. } = forest.process_obligations(|obligation, _| {
+        match *obligation {
+            "A.1" => Ok(Some(vec![])),
+            "A.2" => Err("A is for apple"),
+            "D.1" => Ok(Some(vec!["D.1.i"])),
+            "D.2" => Ok(Some(vec!["D.2.i"])),
+            _ => unreachable!(),
+        }
+    });
+    assert_eq!(ok, vec!["A.1"]);
+    assert_eq!(err, vec![Error { error: "A is for apple",
+                                 backtrace: vec!["A.2", "A"] }]);
+
+    // fourth round: error in D.1.i that should propagate to D.2.i
+    let Outcome { completed: ok, errors: err, .. } = forest.process_obligations(|obligation, _| {
+        match *obligation {
+            "D.1.i" => Err("D is for dumb"),
+            _ => panic!("unexpected obligation {:?}", obligation),
+        }
+    });
+    assert_eq!(ok, Vec::<&'static str>::new());
+    assert_eq!(err, vec![Error { error: "D is for dumb",
+                                 backtrace: vec!["D.1.i", "D.1", "D"] }]);
+}
+
+// Test that if a tree with grandchildren succeeds, everything is
+// reported as expected:
+// A
+//   A.1
+//   A.2
+//      A.2.i
+//      A.2.ii
+//   A.3
+#[test]
+fn success_in_grandchildren() {
+    let mut forest = ObligationForest::new();
+    forest.push_root("A");
+
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|obligation, _| {
+            match *obligation {
+                "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
+                _ => unreachable!(),
+            }
+        });
+    assert!(ok.is_empty());
+    assert!(err.is_empty());
+
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|obligation, _| {
+            match *obligation {
+                "A.1" => Ok(Some(vec![])),
+                "A.2" => Ok(Some(vec!["A.2.i", "A.2.ii"])),
+                "A.3" => Ok(Some(vec![])),
+                _ => unreachable!(),
+            }
+        });
+    assert_eq!(ok, vec!["A.3", "A.1"]);
+    assert!(err.is_empty());
+
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|obligation, _| {
+            match *obligation {
+                "A.2.i" => Ok(Some(vec!["A.2.i.a"])),
+                "A.2.ii" => Ok(Some(vec![])),
+                _ => unreachable!(),
+            }
+        });
+    assert_eq!(ok, vec!["A.2.ii"]);
+    assert!(err.is_empty());
+
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|obligation, _| {
+            match *obligation {
+                "A.2.i.a" => Ok(Some(vec![])),
+                _ => unreachable!(),
+            }
+        });
+    assert_eq!(ok, vec!["A.2.i.a", "A.2.i", "A.2", "A"]);
+    assert!(err.is_empty());
+
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|_, _| unreachable!());
+    assert!(ok.is_empty());
+    assert!(err.is_empty());
+}
+
+#[test]
+fn to_errors_no_throw() {
+    // check that converting multiple children with common parent (A)
+    // only yields one of them (and does not panic, in particular).
+    let mut forest = ObligationForest::new();
+    forest.push_root("A");
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|obligation, _| {
+            match *obligation {
+                "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
+                _ => unreachable!(),
+            }
+        });
+    assert_eq!(ok.len(), 0);
+    assert_eq!(err.len(), 0);
+    let errors = forest.to_errors(());
+    assert_eq!(errors.len(), 1);
+}
+
+#[test]
+fn backtrace() {
+    // check that converting multiple children with common parent (A)
+    // only yields one of them (and does not panic, in particular).
+    let mut forest: ObligationForest<&'static str> = ObligationForest::new();
+    forest.push_root("A");
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|obligation, mut backtrace| {
+            assert!(backtrace.next().is_none());
+            match *obligation {
+                "A" => Ok(Some(vec!["A.1"])),
+                _ => unreachable!(),
+            }
+        });
+    assert!(ok.is_empty());
+    assert!(err.is_empty());
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|obligation, mut backtrace| {
+            assert!(backtrace.next().unwrap() == &"A");
+            assert!(backtrace.next().is_none());
+            match *obligation {
+                "A.1" => Ok(Some(vec!["A.1.i"])),
+                _ => unreachable!(),
+            }
+        });
+    assert!(ok.is_empty());
+    assert!(err.is_empty());
+    let Outcome { completed: ok, errors: err, .. } =
+        forest.process_obligations::<(),_>(|obligation, mut backtrace| {
+            assert!(backtrace.next().unwrap() == &"A.1");
+            assert!(backtrace.next().unwrap() == &"A");
+            assert!(backtrace.next().is_none());
+            match *obligation {
+                "A.1.i" => Ok(None),
+                _ => unreachable!(),
+            }
+        });
+    assert_eq!(ok.len(), 0);
+    assert!(err.is_empty());
+}
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 8f3366eacb3..b19628baa88 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -139,7 +139,7 @@ fn test_env<F>(source_string: &str,
                                lang_items,
                                stability::Index::new(krate),
                                |tcx| {
-                                   let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
+                                   let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None);
                                    body(Env { infcx: &infcx });
                                    let free_regions = FreeRegionMap::new();
                                    infcx.resolve_regions_and_report_errors(&free_regions,
diff --git a/src/librustc_lint/builtin.rs b/src/librustc_lint/builtin.rs
index 09e6f454fb4..8985b1e56bc 100644
--- a/src/librustc_lint/builtin.rs
+++ b/src/librustc_lint/builtin.rs
@@ -869,7 +869,7 @@ impl LateLintPass for UnconditionalRecursion {
                     let node_id = tcx.map.as_local_node_id(method.def_id).unwrap();
 
                     let param_env = ty::ParameterEnvironment::for_item(tcx, node_id);
-                    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(param_env), false);
+                    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(param_env));
                     let mut selcx = traits::SelectionContext::new(&infcx);
                     match selcx.select(&obligation) {
                         // The method comes from a `T: Trait` bound.
diff --git a/src/librustc_mir/mir_map.rs b/src/librustc_mir/mir_map.rs
index ac15878dc51..3886a6b83ac 100644
--- a/src/librustc_mir/mir_map.rs
+++ b/src/librustc_mir/mir_map.rs
@@ -143,7 +143,7 @@ impl<'a, 'm, 'tcx> Visitor<'tcx> for InnerDump<'a,'m,'tcx> {
 
         let param_env = ty::ParameterEnvironment::for_item(self.tcx, id);
 
-        let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, Some(param_env), true);
+        let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, Some(param_env));
 
         match build_mir(Cx::new(&infcx), implicit_arg_tys, id, span, decl, body) {
             Ok(mut mir) => {
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index 7792169d3eb..3b7cb2bd4b4 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -141,6 +141,7 @@ fn deduce_expectations_from_obligations<'a,'tcx>(
         fulfillment_cx
         .pending_obligations()
         .iter()
+        .map(|obligation| &obligation.obligation)
         .filter_map(|obligation| {
             debug!("deduce_expectations_from_obligations: obligation.predicate={:?}",
                    obligation.predicate);
@@ -168,6 +169,7 @@ fn deduce_expectations_from_obligations<'a,'tcx>(
         fulfillment_cx
         .pending_obligations()
         .iter()
+        .map(|obligation| &obligation.obligation)
         .filter_map(|obligation| {
             let opt_trait_ref = match obligation.predicate {
                 ty::Predicate::Projection(ref data) => Some(data.to_poly_trait_ref()),
diff --git a/src/librustc_typeck/check/compare_method.rs b/src/librustc_typeck/check/compare_method.rs
index 554424a36b1..d5f24220189 100644
--- a/src/librustc_typeck/check/compare_method.rs
+++ b/src/librustc_typeck/check/compare_method.rs
@@ -42,7 +42,7 @@ pub fn compare_impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
     debug!("compare_impl_method: impl_trait_ref (liberated) = {:?}",
            impl_trait_ref);
 
-    let mut infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, true);
+    let mut infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None);
     let mut fulfillment_cx = infcx.fulfillment_cx.borrow_mut();
 
     let trait_to_impl_substs = &impl_trait_ref.substs;
@@ -416,7 +416,7 @@ pub fn compare_const_impl<'tcx>(tcx: &ty::ctxt<'tcx>,
     debug!("compare_const_impl(impl_trait_ref={:?})",
            impl_trait_ref);
 
-    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, true);
+    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None);
     let mut fulfillment_cx = infcx.fulfillment_cx.borrow_mut();
 
     // The below is for the most part highly similar to the procedure
diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs
index 0cf552b6efe..deda0b818ee 100644
--- a/src/librustc_typeck/check/dropck.rs
+++ b/src/librustc_typeck/check/dropck.rs
@@ -83,7 +83,7 @@ fn ensure_drop_params_and_item_params_correspond<'tcx>(
     // check that the impl type can be made to match the trait type.
 
     let impl_param_env = ty::ParameterEnvironment::for_item(tcx, self_type_node_id);
-    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(impl_param_env), true);
+    let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, Some(impl_param_env));
 
     let named_type = tcx.lookup_item_type(self_type_did).ty;
     let named_type = named_type.subst(tcx, &infcx.parameter_environment.free_substs);
diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs
index 44b36294cb4..d462e2b45b2 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -261,7 +261,7 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
     // FIXME(#18653) -- Try to resolve obligations, giving us more
     // typing information, which can sometimes be needed to avoid
     // pathological region inference failures.
-    fcx.select_new_obligations();
+    fcx.select_obligations_where_possible();
 
     // Insert any adjustments needed (always an autoref of some mutability).
     match self_expr {
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 0f87dc88852..a6fb4de8e2b 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -305,7 +305,7 @@ impl<'a, 'tcx> Inherited<'a, 'tcx> {
            -> Inherited<'a, 'tcx> {
 
         Inherited {
-            infcx: infer::new_infer_ctxt(tcx, tables, Some(param_env), true),
+            infcx: infer::new_infer_ctxt(tcx, tables, Some(param_env)),
             locals: RefCell::new(NodeMap()),
             tables: tables,
             deferred_call_resolutions: RefCell::new(DefIdMap()),
@@ -1235,15 +1235,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             return ty;
         }
 
-        // If not, try resolving any new fcx obligations that have cropped up.
-        self.select_new_obligations();
-        ty = self.infcx().resolve_type_vars_if_possible(&ty);
-        if !ty.has_infer_types() {
-            debug!("resolve_type_vars_if_possible: ty={:?}", ty);
-            return ty;
-        }
-
-        // If not, try resolving *all* pending obligations as much as
+        // If not, try resolving pending obligations as much as
         // possible. This can help substantially when there are
         // indirect dependencies that don't seem worth tracking
         // precisely.
@@ -2029,22 +2021,6 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             Err(errors) => { report_fulfillment_errors(self.infcx(), &errors); }
         }
     }
-
-    /// Try to select any fcx obligation that we haven't tried yet, in an effort
-    /// to improve inference. You could just call
-    /// `select_obligations_where_possible` except that it leads to repeated
-    /// work.
-    fn select_new_obligations(&self) {
-        match
-            self.inh.infcx.fulfillment_cx
-            .borrow_mut()
-            .select_new_obligations(self.infcx())
-        {
-            Ok(()) => { }
-            Err(errors) => { report_fulfillment_errors(self.infcx(), &errors); }
-        }
-    }
-
 }
 
 impl<'a, 'tcx> RegionScope for FnCtxt<'a, 'tcx> {
@@ -2496,7 +2472,7 @@ fn check_argument_types<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
         // an "opportunistic" vtable resolution of any trait bounds on
         // the call. This helps coercions.
         if check_blocks {
-            fcx.select_new_obligations();
+            fcx.select_obligations_where_possible();
         }
 
         // For variadic functions, we don't have a declared type for all of
@@ -4126,7 +4102,7 @@ fn check_const_with_ty<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 pub fn check_representable(tcx: &ty::ctxt,
                            sp: Span,
                            item_id: ast::NodeId,
-                           designation: &str) -> bool {
+                           _designation: &str) -> bool {
     let rty = tcx.node_id_to_type(item_id);
 
     // Check that it is possible to represent this type. This call identifies
@@ -4136,9 +4112,8 @@ pub fn check_representable(tcx: &ty::ctxt,
     // caught by case 1.
     match rty.is_representable(tcx, sp) {
         Representability::SelfRecursive => {
-            struct_span_err!(tcx.sess, sp, E0072, "invalid recursive {} type", designation)
-                .fileline_help(sp, "wrap the inner value in a box to make it representable")
-                .emit();
+            let item_def_id = tcx.map.local_def_id(item_id);
+            traits::recursive_type_with_infinite_size_error(tcx, item_def_id).emit();
             return false
         }
         Representability::Representable | Representability::ContainsRecursive => (),
diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs
index 7465ff526b6..7e63fd47d61 100644
--- a/src/librustc_typeck/coherence/mod.rs
+++ b/src/librustc_typeck/coherence/mod.rs
@@ -384,7 +384,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> {
             debug!("check_implementations_of_coerce_unsized: {:?} -> {:?} (free)",
                    source, target);
 
-            let infcx = new_infer_ctxt(tcx, &tcx.tables, Some(param_env), true);
+            let infcx = new_infer_ctxt(tcx, &tcx.tables, Some(param_env));
 
             let check_mutbl = |mt_a: ty::TypeAndMut<'tcx>, mt_b: ty::TypeAndMut<'tcx>,
                                mk_ptr: &Fn(Ty<'tcx>) -> Ty<'tcx>| {
@@ -528,7 +528,7 @@ fn enforce_trait_manually_implementable(tcx: &ty::ctxt, sp: Span, trait_def_id:
 
 pub fn check_coherence(crate_context: &CrateCtxt) {
     let _task = crate_context.tcx.dep_graph.in_task(DepNode::Coherence);
-    let infcx = new_infer_ctxt(crate_context.tcx, &crate_context.tcx.tables, None, true);
+    let infcx = new_infer_ctxt(crate_context.tcx, &crate_context.tcx.tables, None);
     CoherenceChecker {
         crate_context: crate_context,
         inference_context: infcx,
diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs
index 71c6fc1fd08..470e954781f 100644
--- a/src/librustc_typeck/coherence/overlap.rs
+++ b/src/librustc_typeck/coherence/overlap.rs
@@ -127,7 +127,7 @@ impl<'cx, 'tcx> OverlapChecker<'cx, 'tcx> {
                    impl1_def_id,
                    impl2_def_id);
 
-            let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, None, false);
+            let infcx = infer::new_infer_ctxt(self.tcx, &self.tcx.tables, None);
             if let Some(trait_ref) = traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) {
                 self.report_overlap_error(impl1_def_id, impl2_def_id, trait_ref);
             }
diff --git a/src/librustc_typeck/diagnostics.rs b/src/librustc_typeck/diagnostics.rs
index 5f2582a548b..55a1021f0fb 100644
--- a/src/librustc_typeck/diagnostics.rs
+++ b/src/librustc_typeck/diagnostics.rs
@@ -869,43 +869,6 @@ fn main() {
 ```
 "##,
 
-E0072: r##"
-When defining a recursive struct or enum, any use of the type being defined
-from inside the definition must occur behind a pointer (like `Box` or `&`).
-This is because structs and enums must have a well-defined size, and without
-the pointer the size of the type would need to be unbounded.
-
-Consider the following erroneous definition of a type for a list of bytes:
-
-```
-// error, invalid recursive struct type
-struct ListNode {
-    head: u8,
-    tail: Option<ListNode>,
-}
-```
-
-This type cannot have a well-defined size, because it needs to be arbitrarily
-large (since we would be able to nest `ListNode`s to any depth). Specifically,
-
-```plain
-size of `ListNode` = 1 byte for `head`
-                   + 1 byte for the discriminant of the `Option`
-                   + size of `ListNode`
-```
-
-One way to fix this is by wrapping `ListNode` in a `Box`, like so:
-
-```
-struct ListNode {
-    head: u8,
-    tail: Option<Box<ListNode>>,
-}
-```
-
-This works because `Box` is a pointer, so its size is well-known.
-"##,
-
 E0073: r##"
 You cannot define a struct (or enum) `Foo` that requires an instance of `Foo`
 in order to make a new `Foo` value. This is because there would be no way a
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index 867d12a1def..acffbeabb24 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -193,7 +193,7 @@ fn require_same_types<'a, 'tcx, M>(tcx: &ty::ctxt<'tcx>,
 {
     let result = match maybe_infcx {
         None => {
-            let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None, false);
+            let infcx = infer::new_infer_ctxt(tcx, &tcx.tables, None);
             infer::mk_eqty(&infcx, t1_is_expected, TypeOrigin::Misc(span), t1, t2)
         }
         Some(infcx) => {
diff --git a/src/test/compile-fail/bad-sized.rs b/src/test/compile-fail/bad-sized.rs
index 8c13ff70515..bfe9d740339 100644
--- a/src/test/compile-fail/bad-sized.rs
+++ b/src/test/compile-fail/bad-sized.rs
@@ -13,5 +13,6 @@ trait Trait {}
 pub fn main() {
     let x: Vec<Trait + Sized> = Vec::new();
     //~^ ERROR the trait `core::marker::Sized` is not implemented
-    //~^^ ERROR the trait `core::marker::Sized` is not implemented
+    //~| ERROR the trait `core::marker::Sized` is not implemented
+    //~| ERROR the trait `core::marker::Sized` is not implemented
 }
diff --git a/src/test/compile-fail/infinite-tag-type-recursion.rs b/src/test/compile-fail/infinite-tag-type-recursion.rs
index 7dbf75feda0..c9a7f731aea 100644
--- a/src/test/compile-fail/infinite-tag-type-recursion.rs
+++ b/src/test/compile-fail/infinite-tag-type-recursion.rs
@@ -8,9 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-
-// error-pattern: invalid recursive enum type
-
 enum mlist { cons(isize, mlist), nil, }
+//~^ ERROR recursive type `mlist` has infinite size
 
 fn main() { let a = mlist::cons(10, mlist::cons(11, mlist::nil)); }
diff --git a/src/test/compile-fail/issue-17431-1.rs b/src/test/compile-fail/issue-17431-1.rs
index bd3f2835058..260cc366fae 100644
--- a/src/test/compile-fail/issue-17431-1.rs
+++ b/src/test/compile-fail/issue-17431-1.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 struct Foo { foo: Option<Option<Foo>> }
-//~^ ERROR invalid recursive struct type
+//~^ ERROR recursive type `Foo` has infinite size
 
 impl Foo { fn bar(&self) {} }
 
diff --git a/src/test/compile-fail/issue-17431-2.rs b/src/test/compile-fail/issue-17431-2.rs
index 4e1c0d6571d..edbc8c82432 100644
--- a/src/test/compile-fail/issue-17431-2.rs
+++ b/src/test/compile-fail/issue-17431-2.rs
@@ -9,10 +9,9 @@
 // except according to those terms.
 
 struct Baz { q: Option<Foo> }
-//~^ ERROR invalid recursive struct type
 
 struct Foo { q: Option<Baz> }
-//~^ ERROR invalid recursive struct type
+//~^ ERROR recursive type `Foo` has infinite size
 
 impl Foo { fn bar(&self) {} }
 
diff --git a/src/test/compile-fail/issue-17431-3.rs b/src/test/compile-fail/issue-17431-3.rs
index 07c5f106456..9ba085591f0 100644
--- a/src/test/compile-fail/issue-17431-3.rs
+++ b/src/test/compile-fail/issue-17431-3.rs
@@ -11,7 +11,7 @@
 use std::sync::Mutex;
 
 struct Foo { foo: Mutex<Option<Foo>> }
-//~^ ERROR invalid recursive struct type
+//~^ ERROR recursive type `Foo` has infinite size
 
 impl Foo { fn bar(&self) {} }
 
diff --git a/src/test/compile-fail/issue-17431-4.rs b/src/test/compile-fail/issue-17431-4.rs
index 74952d9ca2b..665c3cf8fe6 100644
--- a/src/test/compile-fail/issue-17431-4.rs
+++ b/src/test/compile-fail/issue-17431-4.rs
@@ -11,7 +11,7 @@
 use std::marker;
 
 struct Foo<T> { foo: Option<Option<Foo<T>>>, marker: marker::PhantomData<T> }
-//~^ ERROR invalid recursive struct type
+//~^ ERROR recursive type `Foo` has infinite size
 
 impl<T> Foo<T> { fn bar(&self) {} }
 
diff --git a/src/test/compile-fail/issue-17431-5.rs b/src/test/compile-fail/issue-17431-5.rs
index 157b5ed434e..85ed4d5d634 100644
--- a/src/test/compile-fail/issue-17431-5.rs
+++ b/src/test/compile-fail/issue-17431-5.rs
@@ -11,8 +11,9 @@
 use std::marker;
 
 struct Foo { foo: Bar<Foo> }
+
 struct Bar<T> { x: Bar<Foo> , marker: marker::PhantomData<T> }
-//~^ ERROR invalid recursive struct type
+//~^ ERROR recursive type `Bar` has infinite size
 
 impl Foo { fn foo(&self) {} }
 
diff --git a/src/test/compile-fail/issue-17431-6.rs b/src/test/compile-fail/issue-17431-6.rs
index b2037378d37..4c1e82c3d6a 100644
--- a/src/test/compile-fail/issue-17431-6.rs
+++ b/src/test/compile-fail/issue-17431-6.rs
@@ -11,7 +11,7 @@
 use std::sync::Mutex;
 
 enum Foo { X(Mutex<Option<Foo>>) }
-//~^ ERROR invalid recursive enum type
+//~^ ERROR recursive type `Foo` has infinite size
 
 impl Foo { fn bar(self) {} }
 
diff --git a/src/test/compile-fail/issue-17431-7.rs b/src/test/compile-fail/issue-17431-7.rs
index 9ad81e030aa..71b85da29fc 100644
--- a/src/test/compile-fail/issue-17431-7.rs
+++ b/src/test/compile-fail/issue-17431-7.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 enum Foo { Voo(Option<Option<Foo>>) }
-//~^ ERROR invalid recursive enum type
+//~^ ERROR recursive type `Foo` has infinite size
 
 impl Foo { fn bar(&self) {} }
 
diff --git a/src/test/compile-fail/issue-20261.rs b/src/test/compile-fail/issue-20261.rs
index 42fd856ad87..09044b5b505 100644
--- a/src/test/compile-fail/issue-20261.rs
+++ b/src/test/compile-fail/issue-20261.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 fn main() {
-    for (ref i,) in [].iter() { //~ ERROR: type mismatch resolving
+    for (ref i,) in [].iter() { //~ ERROR mismatched types
         i.clone();
         //~^ ERROR: the type of this value must be known in this context
     }
diff --git a/src/test/compile-fail/issue-26548.rs b/src/test/compile-fail/issue-26548.rs
index 8b02e8e7046..28080ae09e5 100644
--- a/src/test/compile-fail/issue-26548.rs
+++ b/src/test/compile-fail/issue-26548.rs
@@ -8,11 +8,10 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: overflow representing the type `S`
-
-trait Mirror { type It; }
-impl<T> Mirror for T { type It = Self; }
+trait Mirror { type It: ?Sized; }
+impl<T: ?Sized> Mirror for T { type It = Self; }
 struct S(Option<<S as Mirror>::It>);
+//~^ ERROR recursive type `S` has infinite size
 
 fn main() {
     let _s = S(None);
diff --git a/src/test/compile-fail/issue-2718-a.rs b/src/test/compile-fail/issue-2718-a.rs
index 37daf76c0b9..6de28cbbf35 100644
--- a/src/test/compile-fail/issue-2718-a.rs
+++ b/src/test/compile-fail/issue-2718-a.rs
@@ -16,7 +16,7 @@ mod pingpong {
     use send_packet;
     pub type ping = send_packet<pong>;
     pub struct pong(send_packet<ping>);
-    //~^ ERROR invalid recursive struct type
+    //~^ ERROR recursive type `pingpong::pong` has infinite size
 }
 
 fn main() {}
diff --git a/src/test/compile-fail/issue-3008-1.rs b/src/test/compile-fail/issue-3008-1.rs
index eb684208326..d3c15763eb0 100644
--- a/src/test/compile-fail/issue-3008-1.rs
+++ b/src/test/compile-fail/issue-3008-1.rs
@@ -10,7 +10,7 @@
 
 enum foo { foo_(bar) }
 enum bar { bar_none, bar_some(bar) }
-//~^ ERROR invalid recursive enum type
+//~^ ERROR recursive type `bar` has infinite size
 
 fn main() {
 }
diff --git a/src/test/compile-fail/issue-3008-2.rs b/src/test/compile-fail/issue-3008-2.rs
index f934e0771c2..e6cc29634a1 100644
--- a/src/test/compile-fail/issue-3008-2.rs
+++ b/src/test/compile-fail/issue-3008-2.rs
@@ -12,7 +12,7 @@
 
 enum foo { foo_(bar) }
 struct bar { x: bar }
-//~^ ERROR invalid recursive struct type
+//~^ ERROR E0072
 
 fn main() {
 }
diff --git a/src/test/compile-fail/issue-3008-3.rs b/src/test/compile-fail/issue-3008-3.rs
index f8756b83f23..66bfab003e9 100644
--- a/src/test/compile-fail/issue-3008-3.rs
+++ b/src/test/compile-fail/issue-3008-3.rs
@@ -12,7 +12,7 @@ use std::marker;
 
 enum E1 { V1(E2<E1>), }
 enum E2<T> { V2(E2<E1>, marker::PhantomData<T>), }
-//~^ ERROR invalid recursive enum type
+//~^ ERROR recursive type `E2` has infinite size
 
 impl E1 { fn foo(&self) {} }
 
diff --git a/src/test/compile-fail/issue-3779.rs b/src/test/compile-fail/issue-3779.rs
index 66d8fb40cd1..d96b1a1cbe3 100644
--- a/src/test/compile-fail/issue-3779.rs
+++ b/src/test/compile-fail/issue-3779.rs
@@ -8,8 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-struct S {
-    //~^ ERROR invalid recursive struct type
+struct S { //~ ERROR E0072
     element: Option<S>
 }
 
diff --git a/src/test/compile-fail/issue-7364.rs b/src/test/compile-fail/issue-7364.rs
index 7d0a9007829..87b7b73d57d 100644
--- a/src/test/compile-fail/issue-7364.rs
+++ b/src/test/compile-fail/issue-7364.rs
@@ -17,6 +17,5 @@ use std::cell::RefCell;
 static boxed: Box<RefCell<isize>> = box RefCell::new(0);
 //~^ ERROR allocations are not allowed in statics
 //~| ERROR the trait `core::marker::Sync` is not implemented for the type
-//~| ERROR the trait `core::marker::Sync` is not implemented for the type
 
 fn main() { }
diff --git a/src/test/compile-fail/kindck-impl-type-params.rs b/src/test/compile-fail/kindck-impl-type-params.rs
index 3474a73b31f..aec40c1a73a 100644
--- a/src/test/compile-fail/kindck-impl-type-params.rs
+++ b/src/test/compile-fail/kindck-impl-type-params.rs
@@ -27,14 +27,12 @@ fn f<T>(val: T) {
     let t: S<T> = S(marker::PhantomData);
     let a = &t as &Gettable<T>;
     //~^ ERROR the trait `core::marker::Send` is not implemented
-    //~^^ ERROR the trait `core::marker::Copy` is not implemented
 }
 
 fn g<T>(val: T) {
     let t: S<T> = S(marker::PhantomData);
     let a: &Gettable<T> = &t;
     //~^ ERROR the trait `core::marker::Send` is not implemented
-    //~^^ ERROR the trait `core::marker::Copy` is not implemented
 }
 
 fn foo<'a>() {
diff --git a/src/test/compile-fail/lint-ctypes.rs b/src/test/compile-fail/lint-ctypes.rs
index 5c49098d870..731c1edbfc0 100644
--- a/src/test/compile-fail/lint-ctypes.rs
+++ b/src/test/compile-fail/lint-ctypes.rs
@@ -13,8 +13,8 @@
 
 extern crate libc;
 
-trait Mirror { type It; }
-impl<T> Mirror for T { type It = Self; }
+trait Mirror { type It: ?Sized; }
+impl<T: ?Sized> Mirror for T { type It = Self; }
 #[repr(C)]
 pub struct StructWithProjection(*mut <StructWithProjection as Mirror>::It);
 #[repr(C)]
diff --git a/src/test/compile-fail/mut-not-freeze.rs b/src/test/compile-fail/mut-not-freeze.rs
index 2269c58c97d..db19132b2c4 100644
--- a/src/test/compile-fail/mut-not-freeze.rs
+++ b/src/test/compile-fail/mut-not-freeze.rs
@@ -16,5 +16,4 @@ fn main() {
     let x = RefCell::new(0);
     f(x);
     //~^ ERROR `core::marker::Sync` is not implemented
-    //~^^ ERROR `core::marker::Sync` is not implemented
 }
diff --git a/src/test/compile-fail/not-panic-safe-2.rs b/src/test/compile-fail/not-panic-safe-2.rs
index 47a65505d8a..922d70b8013 100644
--- a/src/test/compile-fail/not-panic-safe-2.rs
+++ b/src/test/compile-fail/not-panic-safe-2.rs
@@ -18,7 +18,6 @@ use std::cell::RefCell;
 fn assert<T: RecoverSafe + ?Sized>() {}
 
 fn main() {
-    assert::<Rc<RefCell<i32>>>(); //~ ERROR: is not implemented
-    //~^ ERROR: is not implemented
+    assert::<Rc<RefCell<i32>>>(); //~ ERROR E0277
 }
 
diff --git a/src/test/compile-fail/not-panic-safe-3.rs b/src/test/compile-fail/not-panic-safe-3.rs
index a0c7865eeb0..50a69543f7d 100644
--- a/src/test/compile-fail/not-panic-safe-3.rs
+++ b/src/test/compile-fail/not-panic-safe-3.rs
@@ -19,5 +19,4 @@ fn assert<T: RecoverSafe + ?Sized>() {}
 
 fn main() {
     assert::<Arc<RefCell<i32>>>(); //~ ERROR: is not implemented
-    //~^ ERROR: is not implemented
 }
diff --git a/src/test/compile-fail/not-panic-safe-4.rs b/src/test/compile-fail/not-panic-safe-4.rs
index 9e716131525..c50e4b9d87e 100644
--- a/src/test/compile-fail/not-panic-safe-4.rs
+++ b/src/test/compile-fail/not-panic-safe-4.rs
@@ -17,6 +17,5 @@ use std::cell::RefCell;
 fn assert<T: RecoverSafe + ?Sized>() {}
 
 fn main() {
-    assert::<&RefCell<i32>>(); //~ ERROR: is not implemented
-    //~^ ERROR is not implemented
+    assert::<&RefCell<i32>>(); //~ ERROR E0277
 }
diff --git a/src/test/compile-fail/not-panic-safe-6.rs b/src/test/compile-fail/not-panic-safe-6.rs
index 90c730d3758..0fc912dc95f 100644
--- a/src/test/compile-fail/not-panic-safe-6.rs
+++ b/src/test/compile-fail/not-panic-safe-6.rs
@@ -17,7 +17,6 @@ use std::cell::RefCell;
 fn assert<T: RecoverSafe + ?Sized>() {}
 
 fn main() {
-    assert::<*mut RefCell<i32>>(); //~ ERROR: is not implemented
-    //~^ ERROR is not implemented
+    assert::<*mut RefCell<i32>>(); //~ ERROR E0277
 }
 
diff --git a/src/test/compile-fail/object-safety-generics.rs b/src/test/compile-fail/object-safety-generics.rs
index 341736f7ab5..8e3161ef884 100644
--- a/src/test/compile-fail/object-safety-generics.rs
+++ b/src/test/compile-fail/object-safety-generics.rs
@@ -28,6 +28,7 @@ fn make_bar<T:Bar>(t: &T) -> &Bar {
 }
 
 fn make_bar_explicit<T:Bar>(t: &T) -> &Bar {
+    //~^ ERROR E0038
     t as &Bar
 }
 
diff --git a/src/test/compile-fail/range-1.rs b/src/test/compile-fail/range-1.rs
index 826e4283ef8..b839902c683 100644
--- a/src/test/compile-fail/range-1.rs
+++ b/src/test/compile-fail/range-1.rs
@@ -17,12 +17,11 @@ pub fn main() {
 
     // Bool => does not implement iterator.
     for i in false..true {}
-    //~^ ERROR the trait
-    //~^^ ERROR the trait
-    //~^^^ ERROR the trait
+    //~^ ERROR E0277
 
     // Unsized type.
     let arr: &[_] = &[1, 2, 3];
     let range = *arr..;
     //~^ ERROR the trait `core::marker::Sized` is not implemented
+    //~| ERROR the trait `core::marker::Sized` is not implemented
 }
diff --git a/src/test/compile-fail/recursion.rs b/src/test/compile-fail/recursion.rs
index b1d45a82276..3221ae46296 100644
--- a/src/test/compile-fail/recursion.rs
+++ b/src/test/compile-fail/recursion.rs
@@ -19,8 +19,8 @@ impl<T:Dot> Dot for Cons<T> {
     self.head * other.head + self.tail.dot(other.tail)
   }
 }
-fn test<T:Dot> (n:isize, i:isize, first:T, second:T) ->isize {
-  match n {    0 => {first.dot(second)} //~ ERROR overflow
+fn test<T:Dot> (n:isize, i:isize, first:T, second:T) ->isize { //~ ERROR recursion limit
+  match n {    0 => {first.dot(second)}
       // FIXME(#4287) Error message should be here. It should be
       // a type error to instantiate `test` at a type other than T.
     _ => {test (n-1, i+1, Cons {head:2*i+1, tail:first}, Cons{head:i*i, tail:second})}
diff --git a/src/test/compile-fail/recursive-enum.rs b/src/test/compile-fail/recursive-enum.rs
index 33dcbdf74d2..555755cdb96 100644
--- a/src/test/compile-fail/recursive-enum.rs
+++ b/src/test/compile-fail/recursive-enum.rs
@@ -8,8 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: invalid recursive enum type
-
 enum list<T> { cons(T, list<T>), nil }
+//~^ ERROR recursive type `list` has infinite size
 
 fn main() {}
diff --git a/src/test/compile-fail/sized-cycle-note.rs b/src/test/compile-fail/sized-cycle-note.rs
new file mode 100644
index 00000000000..bb1ab2eafb3
--- /dev/null
+++ b/src/test/compile-fail/sized-cycle-note.rs
@@ -0,0 +1,31 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test the error message resulting from a cycle in solving `Foo:
+// Sized`. The specifics of the message will of course but the main
+// thing we want to preserve is that:
+//
+// 1. the message should appear attached to one of the structs
+//    defined in this file;
+// 2. it should elaborate the steps that led to the cycle.
+
+struct Baz { q: Option<Foo> }
+
+struct Foo { q: Option<Baz> }
+//~^ ERROR recursive type `Foo` has infinite size
+//~| type `Foo` is embedded within `core::option::Option<Foo>`...
+//~| ...which in turn is embedded within `core::option::Option<Foo>`...
+//~| ...which in turn is embedded within `Baz`...
+//~| ...which in turn is embedded within `core::option::Option<Baz>`...
+//~| ...which in turn is embedded within `Foo`, completing the cycle.
+
+impl Foo { fn bar(&self) {} }
+
+fn main() {}
diff --git a/src/test/compile-fail/trait-bounds-on-structs-and-enums-locals.rs b/src/test/compile-fail/trait-bounds-on-structs-and-enums-locals.rs
index d39b7e15edc..520691fbecc 100644
--- a/src/test/compile-fail/trait-bounds-on-structs-and-enums-locals.rs
+++ b/src/test/compile-fail/trait-bounds-on-structs-and-enums-locals.rs
@@ -22,6 +22,6 @@ fn main() {
         x: 3
     };
 
-    let baz: Foo<usize> = panic!();
+    let baz: Foo<usize> = loop { };
     //~^ ERROR not implemented
 }
diff --git a/src/test/compile-fail/trait-test-2.rs b/src/test/compile-fail/trait-test-2.rs
index 2d4df77f960..0cfcf6bb3f9 100644
--- a/src/test/compile-fail/trait-test-2.rs
+++ b/src/test/compile-fail/trait-test-2.rs
@@ -21,5 +21,7 @@ fn main() {
     (box 10 as Box<bar>).dup();
     //~^ ERROR E0038
     //~| ERROR E0038
+    //~| ERROR E0038
+    //~| ERROR E0038
     //~| ERROR E0277
 }
diff --git a/src/test/compile-fail/traits-inductive-overflow-supertrait-oibit.rs b/src/test/compile-fail/traits-inductive-overflow-supertrait-oibit.rs
new file mode 100644
index 00000000000..1362f8ac0ae
--- /dev/null
+++ b/src/test/compile-fail/traits-inductive-overflow-supertrait-oibit.rs
@@ -0,0 +1,28 @@
+// Copyright 2015 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.
+
+// OIBIT-based version of #29859, supertrait version. Test that using
+// a simple OIBIT `..` impl alone still doesn't allow arbitary bounds
+// to be synthesized.
+
+#![feature(optin_builtin_traits)]
+
+trait Magic: Copy {}
+impl Magic for .. {}
+
+fn copy<T: Magic>(x: T) -> (T, T) { (x, x) }
+
+#[derive(Debug)]
+struct NoClone;
+
+fn main() {
+    let (a, b) = copy(NoClone); //~ ERROR E0277
+    println!("{:?} {:?}", a, b);
+}
diff --git a/src/test/compile-fail/traits-inductive-overflow-supertrait.rs b/src/test/compile-fail/traits-inductive-overflow-supertrait.rs
new file mode 100644
index 00000000000..c717ae9639f
--- /dev/null
+++ b/src/test/compile-fail/traits-inductive-overflow-supertrait.rs
@@ -0,0 +1,25 @@
+// Copyright 2015 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.
+
+// Regression test for #29859, supertrait version. This example
+// allowed arbitrary trait bounds to be synthesized.
+
+trait Magic: Copy {}
+impl<T: Magic> Magic for T {}
+
+fn copy<T: Magic>(x: T) -> (T, T) { (x, x) }
+
+#[derive(Debug)]
+struct NoClone;
+
+fn main() {
+    let (a, b) = copy(NoClone); //~ ERROR E0275
+    println!("{:?} {:?}", a, b);
+}
diff --git a/src/test/compile-fail/traits-inductive-overflow-two-traits.rs b/src/test/compile-fail/traits-inductive-overflow-two-traits.rs
new file mode 100644
index 00000000000..c622dca2b4d
--- /dev/null
+++ b/src/test/compile-fail/traits-inductive-overflow-two-traits.rs
@@ -0,0 +1,31 @@
+// Copyright 2015 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.
+
+// Regression test for #29859, initial version. This example allowed
+// arbitrary trait bounds to be synthesized.
+
+// Trait that you want all types to implement.
+use std::marker::{Sync as Trait};
+
+pub trait Magic {
+    type X: Trait;
+}
+impl<T: Magic> Magic for T {
+    type X = Self;
+}
+
+fn check<T: Trait>() {}
+
+fn wizard<T: Magic>() { check::<<T as Magic>::X>(); }
+
+fn main() {
+    wizard::<*mut ()>(); //~ ERROR E0275
+    // check::<*mut ()>();
+}
diff --git a/src/test/compile-fail/type-recursive.rs b/src/test/compile-fail/type-recursive.rs
index 3b08d900733..4bb739800df 100644
--- a/src/test/compile-fail/type-recursive.rs
+++ b/src/test/compile-fail/type-recursive.rs
@@ -8,8 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern:invalid recursive struct type
-struct t1 {
+struct t1 { //~ ERROR E0072
     foo: isize,
     foolish: t1
 }