Auto merge of #49202 - csmoe:trait_engine, r=nikomatsakis

Introduce trait engine

address #48895 step 1: introduce trait engine

13 files changed, 196 insertions, 118 deletions

diff --git a/src/librustc/infer/outlives/bounds.rs b/src/librustc/infer/outlives/bounds.rs
index 8bb3f4158ff..4bc64acc763 100644
--- a/src/librustc/infer/outlives/bounds.rs
+++ b/src/librustc/infer/outlives/bounds.rs
@@ -11,7 +11,7 @@
 use infer::InferCtxt;
 use syntax::ast;
 use syntax::codemap::Span;
-use traits::FulfillmentContext;
+use traits::{FulfillmentContext, TraitEngine};
 use ty::{self, Ty, TypeFoldable};
 use ty::outlives::Component;
 use ty::wf;
diff --git a/src/librustc/traits/engine.rs b/src/librustc/traits/engine.rs
new file mode 100644
index 00000000000..8eee6f35ab9
--- /dev/null
+++ b/src/librustc/traits/engine.rs
@@ -0,0 +1,71 @@
+// Copyright 2018 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 infer::InferCtxt;
+use ty::{self, Ty, TyCtxt};
+use hir::def_id::DefId;
+
+use super::{FulfillmentContext, FulfillmentError};
+use super::{ObligationCause, PendingPredicateObligation, PredicateObligation};
+
+pub trait TraitEngine<'tcx>: 'tcx {
+    fn normalize_projection_type<'a, 'gcx>(
+        &mut self,
+        infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        projection_ty: ty::ProjectionTy<'tcx>,
+        cause: ObligationCause<'tcx>,
+    ) -> Ty<'tcx>;
+
+    fn register_bound<'a, 'gcx>(
+        &mut self,
+        infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        ty: Ty<'tcx>,
+        def_id: DefId,
+        cause: ObligationCause<'tcx>,
+    );
+
+    fn register_predicate_obligation<'a, 'gcx>(
+        &mut self,
+        infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+        obligation: PredicateObligation<'tcx>,
+    );
+
+    fn select_all_or_error<'a, 'gcx>(
+        &mut self,
+        infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+    ) -> Result<(), Vec<FulfillmentError<'tcx>>>;
+
+    fn select_where_possible<'a, 'gcx>(
+        &mut self,
+        infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+    ) -> Result<(), Vec<FulfillmentError<'tcx>>>;
+
+    fn pending_obligations(&self) -> Vec<PendingPredicateObligation<'tcx>>;
+}
+
+impl<'a, 'gcx, 'tcx> dyn TraitEngine<'tcx> {
+    pub fn new(_tcx: TyCtxt<'_, '_, 'tcx>) -> Box<Self> {
+        Box::new(FulfillmentContext::new())
+    }
+
+    pub fn register_predicate_obligations<I>(
+        &mut self,
+        infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+        obligations: I,
+    ) where
+        I: IntoIterator<Item = PredicateObligation<'tcx>>,
+    {
+        for obligation in obligations {
+            self.register_predicate_obligation(infcx, obligation);
+        }
+    }
+}
diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 150a2ead9e9..1c091d68a2e 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -21,6 +21,7 @@ use middle::const_val::{ConstEvalErr, ErrKind};
 use super::CodeAmbiguity;
 use super::CodeProjectionError;
 use super::CodeSelectionError;
+use super::engine::TraitEngine;
 use super::{FulfillmentError, FulfillmentErrorCode};
 use super::{ObligationCause, PredicateObligation, Obligation};
 use super::project;
@@ -85,6 +86,59 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
         }
     }
 
+    pub fn register_predicate_obligations<I>(&mut self,
+                                             infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+                                             obligations: I)
+        where I: IntoIterator<Item = PredicateObligation<'tcx>>
+    {
+        for obligation in obligations {
+            self.register_predicate_obligation(infcx, obligation);
+        }
+    }
+
+    /// 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(&mut self, selcx: &mut SelectionContext<'a, 'gcx, 'tcx>)
+              -> Result<(),Vec<FulfillmentError<'tcx>>> {
+        debug!("select(obligation-forest-size={})", self.predicates.len());
+
+        let mut errors = Vec::new();
+
+        loop {
+            debug!("select: starting another iteration");
+
+            // Process pending obligations.
+            let outcome = self.predicates.process_obligations(&mut FulfillProcessor {
+                selcx,
+                register_region_obligations: self.register_region_obligations
+            });
+            debug!("select: outcome={:?}", outcome);
+
+            // FIXME: if we kept the original cache key, we could mark projection
+            // obligations as complete for the projection cache here.
+
+            errors.extend(
+                outcome.errors.into_iter()
+                              .map(|e| to_fulfillment_error(e)));
+
+            // If nothing new was added, no need to keep looping.
+            if outcome.stalled {
+                break;
+            }
+        }
+
+        debug!("select({} predicates remaining, {} errors) done",
+               self.predicates.len(), errors.len());
+
+        if errors.is_empty() {
+            Ok(())
+        } else {
+            Err(errors)
+        }
+    }
+}
+
+impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> {
     /// "Normalize" a projection type `<SomeType as SomeTrait>::X` by
     /// creating a fresh type variable `$0` as well as a projection
     /// predicate `<SomeType as SomeTrait>::X == $0`. When the
@@ -92,12 +146,12 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
     /// `SomeTrait` or a where clause that lets us unify `$0` with
     /// something concrete. If this fails, we'll unify `$0` with
     /// `projection_ty` again.
-    pub fn normalize_projection_type(&mut self,
-                                     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                     param_env: ty::ParamEnv<'tcx>,
-                                     projection_ty: ty::ProjectionTy<'tcx>,
-                                     cause: ObligationCause<'tcx>)
-                                     -> Ty<'tcx>
+    fn normalize_projection_type<'a, 'gcx>(&mut self,
+                                 infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+                                 param_env: ty::ParamEnv<'tcx>,
+                                 projection_ty: ty::ProjectionTy<'tcx>,
+                                 cause: ObligationCause<'tcx>)
+                                 -> Ty<'tcx>
     {
         debug!("normalize_projection_type(projection_ty={:?})",
                projection_ty);
@@ -125,12 +179,12 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
     /// Requires that `ty` must implement the trait with `def_id` in
     /// the given environment. This trait must not have any type
     /// parameters (except for `Self`).
-    pub fn register_bound(&mut self,
-                          infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                          param_env: ty::ParamEnv<'tcx>,
-                          ty: Ty<'tcx>,
-                          def_id: DefId,
-                          cause: ObligationCause<'tcx>)
+    fn register_bound<'a, 'gcx>(&mut self,
+                      infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+                      param_env: ty::ParamEnv<'tcx>,
+                      ty: Ty<'tcx>,
+                      def_id: DefId,
+                      cause: ObligationCause<'tcx>)
     {
         let trait_ref = ty::TraitRef {
             def_id,
@@ -144,9 +198,9 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
         });
     }
 
-    pub fn register_predicate_obligation(&mut self,
-                                         infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                         obligation: PredicateObligation<'tcx>)
+    fn register_predicate_obligation<'a, 'gcx>(&mut self,
+                                     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
+                                     obligation: PredicateObligation<'tcx>)
     {
         // this helps to reduce duplicate errors, as well as making
         // debug output much nicer to read and so on.
@@ -162,19 +216,9 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
         });
     }
 
-    pub fn register_predicate_obligations<I>(&mut self,
-                                             infcx: &InferCtxt<'a, 'gcx, 'tcx>,
-                                             obligations: I)
-        where I: IntoIterator<Item = PredicateObligation<'tcx>>
-    {
-        for obligation in obligations {
-            self.register_predicate_obligation(infcx, obligation);
-        }
-    }
-
-    pub fn select_all_or_error(&mut self,
-                               infcx: &InferCtxt<'a, 'gcx, 'tcx>)
-                               -> Result<(),Vec<FulfillmentError<'tcx>>>
+    fn select_all_or_error<'a, 'gcx>(&mut self,
+                                     infcx: &InferCtxt<'a, 'gcx, 'tcx>)
+                                     -> Result<(),Vec<FulfillmentError<'tcx>>>
     {
         self.select_where_possible(infcx)?;
 
@@ -190,58 +234,17 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
         }
     }
 
-    pub fn select_where_possible(&mut self,
-                                 infcx: &InferCtxt<'a, 'gcx, 'tcx>)
-                                 -> Result<(),Vec<FulfillmentError<'tcx>>>
+    fn select_where_possible<'a, 'gcx>(&mut self,
+                             infcx: &InferCtxt<'a, 'gcx, 'tcx>)
+                             -> Result<(),Vec<FulfillmentError<'tcx>>>
     {
         let mut selcx = SelectionContext::new(infcx);
         self.select(&mut selcx)
     }
 
-    pub fn pending_obligations(&self) -> Vec<PendingPredicateObligation<'tcx>> {
+    fn pending_obligations(&self) -> Vec<PendingPredicateObligation<'tcx>> {
         self.predicates.pending_obligations()
     }
-
-    /// 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(&mut self, selcx: &mut SelectionContext<'a, 'gcx, 'tcx>)
-              -> Result<(),Vec<FulfillmentError<'tcx>>> {
-        debug!("select(obligation-forest-size={})", self.predicates.len());
-
-        let mut errors = Vec::new();
-
-        loop {
-            debug!("select: starting another iteration");
-
-            // Process pending obligations.
-            let outcome = self.predicates.process_obligations(&mut FulfillProcessor {
-                selcx,
-                register_region_obligations: self.register_region_obligations
-            });
-            debug!("select: outcome={:?}", outcome);
-
-            // FIXME: if we kept the original cache key, we could mark projection
-            // obligations as complete for the projection cache here.
-
-            errors.extend(
-                outcome.errors.into_iter()
-                              .map(|e| to_fulfillment_error(e)));
-
-            // If nothing new was added, no need to keep looping.
-            if outcome.stalled {
-                break;
-            }
-        }
-
-        debug!("select({} predicates remaining, {} errors) done",
-               self.predicates.len(), errors.len());
-
-        if errors.is_empty() {
-            Ok(())
-        } else {
-            Err(errors)
-        }
-    }
 }
 
 struct FulfillProcessor<'a, 'b: 'a, 'gcx: 'tcx, 'tcx: 'b> {
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index a0ba88f7d55..1d5d3e41c9c 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -34,7 +34,7 @@ use syntax::ast;
 use syntax_pos::{Span, DUMMY_SP};
 
 pub use self::coherence::{orphan_check, overlapping_impls, OrphanCheckErr, OverlapResult};
-pub use self::fulfill::FulfillmentContext;
+pub use self::fulfill::{FulfillmentContext, PendingPredicateObligation};
 pub use self::project::MismatchedProjectionTypes;
 pub use self::project::{normalize, normalize_projection_type, poly_project_and_unify_type};
 pub use self::project::{ProjectionCache, ProjectionCacheSnapshot, Reveal, Normalized};
@@ -45,6 +45,7 @@ pub use self::select::{EvaluationCache, SelectionContext, SelectionCache};
 pub use self::select::IntercrateAmbiguityCause;
 pub use self::specialize::{OverlapError, specialization_graph, translate_substs};
 pub use self::specialize::{SpecializesCache, find_associated_item};
+pub use self::engine::TraitEngine;
 pub use self::util::elaborate_predicates;
 pub use self::util::supertraits;
 pub use self::util::Supertraits;
@@ -54,6 +55,7 @@ pub use self::util::transitive_bounds;
 
 mod coherence;
 pub mod error_reporting;
+mod engine;
 mod fulfill;
 mod project;
 mod object_safety;
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index 5ea089abb8e..a9d1c8bcc3d 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -26,7 +26,7 @@ use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use hir::def_id::DefId;
 use infer::{InferCtxt, InferOk};
 use ty::subst::{Subst, Substs};
-use traits::{self, ObligationCause};
+use traits::{self, ObligationCause, TraitEngine};
 use traits::select::IntercrateAmbiguityCause;
 use ty::{self, TyCtxt, TypeFoldable};
 use syntax_pos::DUMMY_SP;
diff --git a/src/librustc/traits/trans/mod.rs b/src/librustc/traits/trans/mod.rs
index cc8b74e0ee2..31e851126d7 100644
--- a/src/librustc/traits/trans/mod.rs
+++ b/src/librustc/traits/trans/mod.rs
@@ -18,7 +18,8 @@ use std::marker::PhantomData;
 use syntax_pos::DUMMY_SP;
 use infer::InferCtxt;
 use syntax_pos::Span;
-use traits::{FulfillmentContext, Obligation, ObligationCause, SelectionContext, Vtable};
+use traits::{FulfillmentContext, Obligation, ObligationCause, SelectionContext,
+             TraitEngine, Vtable};
 use ty::{self, Ty, TyCtxt};
 use ty::subst::{Subst, Substs};
 use ty::fold::TypeFoldable;
diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
index 80a439b1830..544cb5eefc8 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
@@ -20,7 +20,7 @@ use dataflow::move_paths::MoveData;
 use rustc::hir::def_id::DefId;
 use rustc::infer::{InferCtxt, InferOk, InferResult, LateBoundRegionConversionTime, UnitResult};
 use rustc::infer::region_constraints::{GenericKind, RegionConstraintData};
-use rustc::traits::{self, Normalized, FulfillmentContext};
+use rustc::traits::{self, Normalized, TraitEngine};
 use rustc::traits::query::NoSolution;
 use rustc::ty::error::TypeError;
 use rustc::ty::fold::TypeFoldable;
@@ -662,7 +662,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
     where
         OP: FnOnce(&mut Self) -> InferResult<'tcx, R>,
     {
-        let mut fulfill_cx = FulfillmentContext::new();
+        let mut fulfill_cx = TraitEngine::new(self.infcx.tcx);
         let InferOk { value, obligations } = self.infcx.commit_if_ok(|_| op(self))?;
         fulfill_cx.register_predicate_obligations(self.infcx, obligations);
         if let Err(e) = fulfill_cx.select_all_or_error(self.infcx) {
diff --git a/src/librustc_mir/transform/qualify_consts.rs b/src/librustc_mir/transform/qualify_consts.rs
index 8e2f98d2769..aeefd5ab1d5 100644
--- a/src/librustc_mir/transform/qualify_consts.rs
+++ b/src/librustc_mir/transform/qualify_consts.rs
@@ -21,7 +21,7 @@ use rustc_data_structures::fx::FxHashSet;
 use rustc::hir;
 use rustc::hir::def_id::DefId;
 use rustc::middle::const_val::ConstVal;
-use rustc::traits;
+use rustc::traits::{self, TraitEngine};
 use rustc::ty::{self, TyCtxt, Ty, TypeFoldable};
 use rustc::ty::cast::CastTy;
 use rustc::ty::maps::Providers;
diff --git a/src/librustc_traits/util.rs b/src/librustc_traits/util.rs
index 976eb442a0d..bff070ab73d 100644
--- a/src/librustc_traits/util.rs
+++ b/src/librustc_traits/util.rs
@@ -12,7 +12,7 @@ use rustc::infer::InferCtxt;
 use rustc::infer::canonical::{CanonicalVarValues, Canonicalize, Certainty, QueryRegionConstraints,
                               QueryResult};
 use rustc::infer::region_constraints::{Constraint, RegionConstraintData};
-use rustc::traits::FulfillmentContext;
+use rustc::traits::{FulfillmentContext, TraitEngine};
 use rustc::traits::query::NoSolution;
 use rustc::ty;
 use std::fmt::Debug;
diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs
index 596381d7ea6..d508b6df924 100644
--- a/src/librustc_typeck/check/dropck.rs
+++ b/src/librustc_typeck/check/dropck.rs
@@ -16,7 +16,7 @@ use rustc::infer::outlives::env::OutlivesEnvironment;
 use rustc::middle::region;
 use rustc::ty::subst::{Subst, Substs, UnpackedKind};
 use rustc::ty::{self, Ty, TyCtxt};
-use rustc::traits::{self, ObligationCause};
+use rustc::traits::{ObligationCause, TraitEngine};
 use util::common::ErrorReported;
 
 use syntax::ast;
@@ -84,7 +84,7 @@ fn ensure_drop_params_and_item_params_correspond<'a, 'tcx>(
     tcx.infer_ctxt().enter(|ref infcx| {
         let impl_param_env = tcx.param_env(self_type_did);
         let tcx = infcx.tcx;
-        let mut fulfillment_cx = traits::FulfillmentContext::new();
+        let mut fulfillment_cx = TraitEngine::new(tcx);
 
         let named_type = tcx.type_of(self_type_did);
 
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index f820b0ba16b..0f0f59c28f8 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -95,7 +95,7 @@ use rustc::infer::type_variable::{TypeVariableOrigin};
 use rustc::middle::region;
 use rustc::mir::interpret::{GlobalId};
 use rustc::ty::subst::{Kind, Subst, Substs};
-use rustc::traits::{self, FulfillmentContext, ObligationCause, ObligationCauseCode};
+use rustc::traits::{self, ObligationCause, ObligationCauseCode, TraitEngine};
 use rustc::ty::{self, Ty, TyCtxt, Visibility, ToPredicate};
 use rustc::ty::adjustment::{Adjust, Adjustment, AutoBorrow, AutoBorrowMutability};
 use rustc::ty::fold::TypeFoldable;
@@ -195,7 +195,7 @@ pub struct Inherited<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 
     locals: RefCell<NodeMap<Ty<'tcx>>>,
 
-    fulfillment_cx: RefCell<traits::FulfillmentContext<'tcx>>,
+    fulfillment_cx: RefCell<Box<dyn TraitEngine<'tcx>>>,
 
     // When we process a call like `c()` where `c` is a closure type,
     // we may not have decided yet whether `c` is a `Fn`, `FnMut`, or
@@ -634,7 +634,7 @@ impl<'a, 'gcx, 'tcx> Inherited<'a, 'gcx, 'tcx> {
                 maybe_tables: infcx.in_progress_tables,
             },
             infcx,
-            fulfillment_cx: RefCell::new(traits::FulfillmentContext::new()),
+            fulfillment_cx: RefCell::new(TraitEngine::new(tcx)),
             locals: RefCell::new(NodeMap()),
             deferred_call_resolutions: RefCell::new(DefIdMap()),
             deferred_cast_checks: RefCell::new(Vec::new()),
@@ -2910,7 +2910,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                 // is polymorphic) and the expected return type.
                 // No argument expectations are produced if unification fails.
                 let origin = self.misc(call_span);
-                let ures = self.at(&origin, self.param_env).sup(ret_ty, formal_ret);
+                let ures = self.at(&origin, self.param_env).sup(ret_ty, &formal_ret);
 
                 // FIXME(#27336) can't use ? here, Try::from_error doesn't default
                 // to identity so the resulting type is not constrained.
@@ -2921,7 +2921,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                         // out unconstrained or ambiguous, as we're
                         // just trying to get hints here.
                         self.save_and_restore_in_snapshot_flag(|_| {
-                            let mut fulfill = FulfillmentContext::new();
+                            let mut fulfill = TraitEngine::new(self.tcx);
                             for obligation in ok.obligations {
                                 fulfill.register_predicate_obligation(self, obligation);
                             }
diff --git a/src/librustc_typeck/coherence/builtin.rs b/src/librustc_typeck/coherence/builtin.rs
index 9493c36fe95..aa4322783c6 100644
--- a/src/librustc_typeck/coherence/builtin.rs
+++ b/src/librustc_typeck/coherence/builtin.rs
@@ -15,7 +15,7 @@ use rustc::infer::outlives::env::OutlivesEnvironment;
 use rustc::middle::region;
 use rustc::middle::lang_items::UnsizeTraitLangItem;
 
-use rustc::traits::{self, ObligationCause};
+use rustc::traits::{self, TraitEngine, ObligationCause};
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::TypeFoldable;
 use rustc::ty::adjustment::CoerceUnsizedInfo;
@@ -172,34 +172,34 @@ fn visit_implementation_of_coerce_unsized<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     }
 }
 
-pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+pub fn coerce_unsized_info<'a, 'gcx>(gcx: TyCtxt<'a, 'gcx, 'gcx>,
                                      impl_did: DefId)
                                      -> CoerceUnsizedInfo {
     debug!("compute_coerce_unsized_info(impl_did={:?})", impl_did);
-    let coerce_unsized_trait = tcx.lang_items().coerce_unsized_trait().unwrap();
+    let coerce_unsized_trait = gcx.lang_items().coerce_unsized_trait().unwrap();
 
-    let unsize_trait = match tcx.lang_items().require(UnsizeTraitLangItem) {
+    let unsize_trait = match gcx.lang_items().require(UnsizeTraitLangItem) {
         Ok(id) => id,
         Err(err) => {
-            tcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err));
+            gcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err));
         }
     };
 
     // this provider should only get invoked for local def-ids
-    let impl_node_id = tcx.hir.as_local_node_id(impl_did).unwrap_or_else(|| {
+    let impl_node_id = gcx.hir.as_local_node_id(impl_did).unwrap_or_else(|| {
         bug!("coerce_unsized_info: invoked for non-local def-id {:?}", impl_did)
     });
 
-    let source = tcx.type_of(impl_did);
-    let trait_ref = tcx.impl_trait_ref(impl_did).unwrap();
+    let source = gcx.type_of(impl_did);
+    let trait_ref = gcx.impl_trait_ref(impl_did).unwrap();
     assert_eq!(trait_ref.def_id, coerce_unsized_trait);
     let target = trait_ref.substs.type_at(1);
     debug!("visit_implementation_of_coerce_unsized: {:?} -> {:?} (bound)",
            source,
            target);
 
-    let span = tcx.hir.span(impl_node_id);
-    let param_env = tcx.param_env(impl_did);
+    let span = gcx.hir.span(impl_node_id);
+    let param_env = gcx.param_env(impl_did);
     assert!(!source.has_escaping_regions());
 
     let err_info = CoerceUnsizedInfo { custom_kind: None };
@@ -208,11 +208,11 @@ pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
            source,
            target);
 
-    tcx.infer_ctxt().enter(|infcx| {
+    gcx.infer_ctxt().enter(|infcx| {
         let cause = ObligationCause::misc(span, impl_node_id);
-        let check_mutbl = |mt_a: ty::TypeAndMut<'tcx>,
-                           mt_b: ty::TypeAndMut<'tcx>,
-                           mk_ptr: &Fn(Ty<'tcx>) -> Ty<'tcx>| {
+        let check_mutbl = |mt_a: ty::TypeAndMut<'gcx>,
+                           mt_b: ty::TypeAndMut<'gcx>,
+                           mk_ptr: &Fn(Ty<'gcx>) -> Ty<'gcx>| {
             if (mt_a.mutbl, mt_b.mutbl) == (hir::MutImmutable, hir::MutMutable) {
                 infcx.report_mismatched_types(&cause,
                                              mk_ptr(mt_b.ty),
@@ -225,20 +225,20 @@ pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         let (source, target, trait_def_id, kind) = match (&source.sty, &target.sty) {
             (&ty::TyRef(r_a, mt_a), &ty::TyRef(r_b, mt_b)) => {
                 infcx.sub_regions(infer::RelateObjectBound(span), r_b, r_a);
-                check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ref(r_b, ty))
+                check_mutbl(mt_a, mt_b, &|ty| gcx.mk_imm_ref(r_b, ty))
             }
 
             (&ty::TyRef(_, mt_a), &ty::TyRawPtr(mt_b)) |
             (&ty::TyRawPtr(mt_a), &ty::TyRawPtr(mt_b)) => {
-                check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ptr(ty))
+                check_mutbl(mt_a, mt_b, &|ty| gcx.mk_imm_ptr(ty))
             }
 
             (&ty::TyAdt(def_a, substs_a), &ty::TyAdt(def_b, substs_b)) if def_a.is_struct() &&
                                                                           def_b.is_struct() => {
                 if def_a != def_b {
-                    let source_path = tcx.item_path_str(def_a.did);
-                    let target_path = tcx.item_path_str(def_b.did);
-                    span_err!(tcx.sess,
+                    let source_path = gcx.item_path_str(def_a.did);
+                    let target_path = gcx.item_path_str(def_b.did);
+                    span_err!(gcx.sess,
                               span,
                               E0377,
                               "the trait `CoerceUnsized` may only be implemented \
@@ -292,9 +292,9 @@ pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                 let diff_fields = fields.iter()
                     .enumerate()
                     .filter_map(|(i, f)| {
-                        let (a, b) = (f.ty(tcx, substs_a), f.ty(tcx, substs_b));
+                        let (a, b) = (f.ty(gcx, substs_a), f.ty(gcx, substs_b));
 
-                        if tcx.type_of(f.did).is_phantom_data() {
+                        if gcx.type_of(f.did).is_phantom_data() {
                             // Ignore PhantomData fields
                             return None;
                         }
@@ -321,7 +321,7 @@ pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                     .collect::<Vec<_>>();
 
                 if diff_fields.is_empty() {
-                    span_err!(tcx.sess,
+                    span_err!(gcx.sess,
                               span,
                               E0374,
                               "the trait `CoerceUnsized` may only be implemented \
@@ -329,14 +329,14 @@ pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                being coerced, none found");
                     return err_info;
                 } else if diff_fields.len() > 1 {
-                    let item = tcx.hir.expect_item(impl_node_id);
+                    let item = gcx.hir.expect_item(impl_node_id);
                     let span = if let ItemImpl(.., Some(ref t), _, _) = item.node {
                         t.path.span
                     } else {
-                        tcx.hir.span(impl_node_id)
+                        gcx.hir.span(impl_node_id)
                     };
 
-                    let mut err = struct_span_err!(tcx.sess,
+                    let mut err = struct_span_err!(gcx.sess,
                                                    span,
                                                    E0375,
                                                    "implementing the trait \
@@ -363,7 +363,7 @@ pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             }
 
             _ => {
-                span_err!(tcx.sess,
+                span_err!(gcx.sess,
                           span,
                           E0376,
                           "the trait `CoerceUnsized` may only be implemented \
@@ -372,11 +372,11 @@ pub fn coerce_unsized_info<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             }
         };
 
-        let mut fulfill_cx = traits::FulfillmentContext::new();
+        let mut fulfill_cx = TraitEngine::new(infcx.tcx);
 
         // Register an obligation for `A: Trait<B>`.
         let cause = traits::ObligationCause::misc(span, impl_node_id);
-        let predicate = tcx.predicate_for_trait_def(param_env,
+        let predicate = gcx.predicate_for_trait_def(param_env,
                                                     cause,
                                                     trait_def_id,
                                                     0,
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index 8b3d5af3edd..86c5e49d167 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -88,6 +88,7 @@ This API is completely unstable and subject to change.
 #![feature(slice_patterns)]
 #![cfg_attr(stage0, feature(i128_type))]
 #![cfg_attr(stage0, feature(never_type))]
+#![feature(dyn_trait)]
 
 #[macro_use] extern crate log;
 #[macro_use] extern crate syntax;
@@ -111,7 +112,7 @@ use rustc::infer::InferOk;
 use rustc::ty::subst::Substs;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::maps::Providers;
-use rustc::traits::{FulfillmentContext, ObligationCause, ObligationCauseCode};
+use rustc::traits::{ObligationCause, ObligationCauseCode, TraitEngine};
 use session::{CompileIncomplete, config};
 use util::common::time;
 
@@ -160,7 +161,7 @@ fn require_same_types<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                 -> bool {
     tcx.infer_ctxt().enter(|ref infcx| {
         let param_env = ty::ParamEnv::empty();
-        let mut fulfill_cx = FulfillmentContext::new();
+        let mut fulfill_cx = TraitEngine::new(infcx.tcx);
         match infcx.at(&cause, param_env).eq(expected, actual) {
             Ok(InferOk { obligations, .. }) => {
                 fulfill_cx.register_predicate_obligations(infcx, obligations);