introduce `infcx.at(..).normalize(..)` operation [VIC]

It is backed by the new `normalize_projection_ty` query, which uses
canonicalization.

23 files changed, 637 insertions, 10 deletions

diff --git a/src/Cargo.lock b/src/Cargo.lock
index f8c04fe9272..ed32984bb58 100644
--- a/src/Cargo.lock
+++ b/src/Cargo.lock
@@ -1884,6 +1884,7 @@ dependencies = [
  "rustc_privacy 0.0.0",
  "rustc_resolve 0.0.0",
  "rustc_save_analysis 0.0.0",
+ "rustc_traits 0.0.0",
  "rustc_trans_utils 0.0.0",
  "rustc_typeck 0.0.0",
  "serialize 0.0.0",
@@ -2069,6 +2070,19 @@ dependencies = [
 ]
 
 [[package]]
+name = "rustc_traits"
+version = "0.0.0"
+dependencies = [
+ "bitflags 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "graphviz 0.0.0",
+ "log 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rustc 0.0.0",
+ "rustc_data_structures 0.0.0",
+ "syntax 0.0.0",
+ "syntax_pos 0.0.0",
+]
+
+[[package]]
 name = "rustc_trans"
 version = "0.0.0"
 dependencies = [
diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 6a2c003179a..caef3a8acc4 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -67,11 +67,12 @@ use hir::{HirId, ItemLocalId};
 
 use ich::{Fingerprint, StableHashingContext};
 use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
-use ty::{TyCtxt, Instance, InstanceDef, ParamEnv, ParamEnvAnd, PolyTraitRef, Ty};
-use ty::subst::Substs;
 use std::fmt;
 use std::hash::Hash;
 use syntax_pos::symbol::InternedString;
+use traits::query::CanonicalProjectionGoal;
+use ty::{TyCtxt, Instance, InstanceDef, ParamEnv, ParamEnvAnd, PolyTraitRef, Ty};
+use ty::subst::Substs;
 
 // erase!() just makes tokens go away. It's used to specify which macro argument
 // is repeated (i.e. which sub-expression of the macro we are in) but don't need
@@ -635,6 +636,7 @@ define_dep_nodes!( <'tcx>
     [] CompileCodegenUnit(InternedString),
     [input] OutputFilenames,
     [anon] NormalizeTy,
+    [] NormalizeProjectionTy(CanonicalProjectionGoal<'tcx>),
 
     [] SubstituteNormalizeAndTestPredicates { key: (DefId, &'tcx Substs<'tcx>) },
 
diff --git a/src/librustc/infer/at.rs b/src/librustc/infer/at.rs
index d9fbf4aa514..89dbc76c8a6 100644
--- a/src/librustc/infer/at.rs
+++ b/src/librustc/infer/at.rs
@@ -40,9 +40,9 @@ use super::*;
 use ty::relate::{Relate, TypeRelation};
 
 pub struct At<'a, 'gcx: 'tcx, 'tcx: 'a> {
-    infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
-    cause: &'a ObligationCause<'tcx>,
-    param_env: ty::ParamEnv<'tcx>,
+    pub infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
+    pub cause: &'a ObligationCause<'tcx>,
+    pub param_env: ty::ParamEnv<'tcx>,
 }
 
 pub struct Trace<'a, 'gcx: 'tcx, 'tcx: 'a> {
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 5127807bf70..2c58e17b283 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -69,6 +69,7 @@ pub mod type_variable;
 pub mod unify_key;
 
 #[must_use]
+#[derive(Debug)]
 pub struct InferOk<'tcx, T> {
     pub value: T,
     pub obligations: PredicateObligations<'tcx>,
@@ -1224,6 +1225,16 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         self.borrow_region_constraints().take_and_reset_data()
     }
 
+    /// Gives temporary access to the region constraint data.
+    #[allow(non_camel_case_types)] // bug with impl trait
+    pub fn with_region_constraints<R>(
+        &self,
+        op: impl FnOnce(&RegionConstraintData<'tcx>) -> R,
+    ) -> R {
+        let region_constraints = self.borrow_region_constraints();
+        op(region_constraints.data())
+    }
+
     /// Takes ownership of the list of variable regions. This implies
     /// that all the region constriants have already been taken, and
     /// hence that `resolve_regions_and_report_errors` can never be
diff --git a/src/librustc/infer/outlives/obligations.rs b/src/librustc/infer/outlives/obligations.rs
index 36e657f78b4..e5461685bd4 100644
--- a/src/librustc/infer/outlives/obligations.rs
+++ b/src/librustc/infer/outlives/obligations.rs
@@ -99,6 +99,16 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
             .push((body_id, obligation));
     }
 
+    /// Trait queries just want to pass back type obligations "as is"
+    pub fn take_registered_region_obligations(
+        &self,
+    ) -> Vec<(ast::NodeId, RegionObligation<'tcx>)> {
+        ::std::mem::replace(
+            &mut *self.region_obligations.borrow_mut(),
+            vec![],
+        )
+    }
+
     /// Process the region obligations that must be proven (during
     /// `regionck`) for the given `body_id`, given information about
     /// the region bounds in scope and so forth. This function must be
diff --git a/src/librustc/infer/region_constraints/mod.rs b/src/librustc/infer/region_constraints/mod.rs
index ed89d1d2f57..0c8e49fda18 100644
--- a/src/librustc/infer/region_constraints/mod.rs
+++ b/src/librustc/infer/region_constraints/mod.rs
@@ -350,6 +350,10 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         mem::replace(data, RegionConstraintData::default())
     }
 
+    pub fn data(&self) -> &RegionConstraintData<'tcx> {
+        &self.data
+    }
+
     fn in_snapshot(&self) -> bool {
         !self.undo_log.is_empty()
     }
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index 7b4211e487a..b986445ff84 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -175,6 +175,11 @@ pub struct PerfStats {
     pub decode_def_path_tables_time: Cell<Duration>,
     /// Total number of values canonicalized queries constructed.
     pub queries_canonicalized: Cell<usize>,
+    /// Number of times we canonicalized a value and found that the
+    /// result had already been canonicalized.
+    pub canonicalized_values_allocated: Cell<usize>,
+    /// Number of times this query is invoked.
+    pub normalize_projection_ty: Cell<usize>,
 }
 
 /// Enum to support dispatch of one-time diagnostics (in Session.diag_once)
@@ -862,6 +867,10 @@ impl Session {
         );
         println!("Total queries canonicalized:                   {}",
                  self.perf_stats.queries_canonicalized.get());
+        println!("Total canonical values interned:               {}",
+                 self.perf_stats.canonicalized_values_allocated.get());
+        println!("normalize_projection_ty:                       {}",
+                 self.perf_stats.normalize_projection_ty.get());
     }
 
     /// We want to know if we're allowed to do an optimization for crate foo from -z fuel=foo=n.
@@ -1149,6 +1158,8 @@ pub fn build_session_(
             symbol_hash_time: Cell::new(Duration::from_secs(0)),
             decode_def_path_tables_time: Cell::new(Duration::from_secs(0)),
             queries_canonicalized: Cell::new(0),
+            canonicalized_values_allocated: Cell::new(0),
+            normalize_projection_ty: Cell::new(0),
         },
         code_stats: RefCell::new(CodeStats::new()),
         optimization_fuel_crate,
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 4450c60b68d..3e23e382347 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -63,6 +63,8 @@ mod structural_impls;
 pub mod trans;
 mod util;
 
+pub mod query;
+
 // Whether to enable bug compatibility with issue #43355
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub enum IntercrateMode {
diff --git a/src/librustc/traits/query/mod.rs b/src/librustc/traits/query/mod.rs
new file mode 100644
index 00000000000..bba2c155583
--- /dev/null
+++ b/src/librustc/traits/query/mod.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.
+
+//! Experimental types for the trait query interface. The methods
+//! defined in this module are all based on **canonicalization**,
+//! which makes a canonical query by replacing unbound inference
+//! variables and regions, so that results can be reused more broadly.
+//! The providers for the queries defined here can be found in
+//! `librustc_traits`.
+
+use infer::canonical::Canonical;
+use ty;
+
+pub mod normalize;
+
+pub type CanonicalProjectionGoal<'tcx> =
+    Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>>>;
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub struct NoSolution;
+
+pub type Fallible<T> = Result<T, NoSolution>;
+
+impl_stable_hash_for!(struct NoSolution { });
diff --git a/src/librustc/traits/query/normalize.rs b/src/librustc/traits/query/normalize.rs
new file mode 100644
index 00000000000..030e630f23f
--- /dev/null
+++ b/src/librustc/traits/query/normalize.rs
@@ -0,0 +1,268 @@
+// 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.
+
+//! Code for the 'normalization' query. This consists of a wrapper
+//! which folds deeply, invoking the underlying
+//! `normalize_projection_ty` query when it encounters projections.
+
+use infer::{InferCtxt, InferOk};
+use infer::at::At;
+use infer::canonical::{Canonical, Canonicalize, QueryResult};
+use middle::const_val::ConstVal;
+use mir::interpret::GlobalId;
+use std::rc::Rc;
+use traits::{Obligation, ObligationCause, PredicateObligation, Reveal};
+use traits::query::CanonicalProjectionGoal;
+use traits::project::Normalized;
+use ty::{self, Ty, TyCtxt};
+use ty::fold::{TypeFoldable, TypeFolder};
+use ty::subst::{Subst, Substs};
+
+use super::NoSolution;
+
+impl<'cx, 'gcx, 'tcx> At<'cx, 'gcx, 'tcx> {
+    /// Normalize `value` in the context of the inference context,
+    /// yielding a resulting type, or an error if `value` cannot be
+    /// normalized. If you don't care about regions, you should prefer
+    /// `normalize_erasing_regions`, which is more efficient.
+    ///
+    /// If the normalization succeeds and is unambigious, returns back
+    /// the normalized value along with various outlives relations (in
+    /// the form of obligations that must be discharged).
+    ///
+    /// NB. This will *eventually* be the main means of
+    /// normalizing, but for now should be used only when we actually
+    /// know that normalization will succeed, since error reporting
+    /// and other details are still "under development".
+    pub fn normalize<T>(&self, value: &T) -> Result<Normalized<'tcx, T>, NoSolution>
+    where
+        T: TypeFoldable<'tcx>,
+    {
+        let mut normalizer = QueryNormalizer {
+            infcx: self.infcx,
+            cause: self.cause,
+            param_env: self.param_env,
+            obligations: vec![],
+            error: false,
+            anon_depth: 0,
+        };
+        if !value.has_projections() {
+            return Ok(Normalized {
+                value: value.clone(),
+                obligations: vec![],
+            });
+        }
+
+        let value1 = value.fold_with(&mut normalizer);
+        if normalizer.error {
+            Err(NoSolution)
+        } else {
+            Ok(Normalized {
+                value: value1,
+                obligations: normalizer.obligations,
+            })
+        }
+    }
+}
+
+/// Result from the `normalize_projection_ty` query.
+#[derive(Clone, Debug)]
+pub struct NormalizationResult<'tcx> {
+    /// Result of normalization.
+    pub normalized_ty: Ty<'tcx>,
+}
+
+struct QueryNormalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
+    infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
+    cause: &'cx ObligationCause<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    obligations: Vec<PredicateObligation<'tcx>>,
+    error: bool,
+    anon_depth: usize,
+}
+
+impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx> {
+    fn tcx<'c>(&'c self) -> TyCtxt<'c, 'gcx, 'tcx> {
+        self.infcx.tcx
+    }
+
+    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
+        let ty = ty.super_fold_with(self);
+        match ty.sty {
+            ty::TyAnon(def_id, substs) if !substs.has_escaping_regions() => {
+                // (*)
+                // Only normalize `impl Trait` after type-checking, usually in trans.
+                match self.param_env.reveal {
+                    Reveal::UserFacing => ty,
+
+                    Reveal::All => {
+                        let recursion_limit = self.tcx().sess.recursion_limit.get();
+                        if self.anon_depth >= recursion_limit {
+                            let obligation = Obligation::with_depth(
+                                self.cause.clone(),
+                                recursion_limit,
+                                self.param_env,
+                                ty,
+                            );
+                            self.infcx.report_overflow_error(&obligation, true);
+                        }
+
+                        let generic_ty = self.tcx().type_of(def_id);
+                        let concrete_ty = generic_ty.subst(self.tcx(), substs);
+                        self.anon_depth += 1;
+                        let folded_ty = self.fold_ty(concrete_ty);
+                        self.anon_depth -= 1;
+                        folded_ty
+                    }
+                }
+            }
+
+            ty::TyProjection(ref data) if !data.has_escaping_regions() => {
+                // (*)
+                // (*) This is kind of hacky -- we need to be able to
+                // handle normalization within binders because
+                // otherwise we wind up a need to normalize when doing
+                // trait matching (since you can have a trait
+                // obligation like `for<'a> T::B : Fn(&'a int)`), but
+                // we can't normalize with bound regions in scope. So
+                // far now we just ignore binders but only normalize
+                // if all bound regions are gone (and then we still
+                // have to renormalize whenever we instantiate a
+                // binder). It would be better to normalize in a
+                // binding-aware fashion.
+
+                let gcx = self.infcx.tcx.global_tcx();
+
+                let (c_data, orig_values) =
+                    self.infcx.canonicalize_query(&self.param_env.and(*data));
+                debug!("QueryNormalizer: c_data = {:#?}", c_data);
+                debug!("QueryNormalizer: orig_values = {:#?}", orig_values);
+                match gcx.normalize_projection_ty(c_data) {
+                    Ok(result) => {
+                        // We don't expect ambiguity.
+                        if result.is_ambiguous() {
+                            self.error = true;
+                            return ty;
+                        }
+
+                        match self.infcx.instantiate_query_result(
+                            self.cause,
+                            self.param_env,
+                            &orig_values,
+                            &result,
+                        ) {
+                            Ok(InferOk {
+                                value: result,
+                                obligations,
+                            }) => {
+                                debug!("QueryNormalizer: result = {:#?}", result);
+                                debug!("QueryNormalizer: obligations = {:#?}", obligations);
+                                self.obligations.extend(obligations);
+                                return result.normalized_ty;
+                            }
+
+                            Err(_) => {
+                                self.error = true;
+                                return ty;
+                            }
+                        }
+                    }
+
+                    Err(NoSolution) => {
+                        self.error = true;
+                        ty
+                    }
+                }
+            }
+
+            _ => ty,
+        }
+    }
+
+    fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
+        if let ConstVal::Unevaluated(def_id, substs) = constant.val {
+            let tcx = self.infcx.tcx.global_tcx();
+            if let Some(param_env) = self.tcx().lift_to_global(&self.param_env) {
+                if substs.needs_infer() {
+                    let identity_substs = Substs::identity_for_item(tcx, def_id);
+                    let instance = ty::Instance::resolve(tcx, param_env, def_id, identity_substs);
+                    if let Some(instance) = instance {
+                        let cid = GlobalId {
+                            instance,
+                            promoted: None,
+                        };
+                        match tcx.const_eval(param_env.and(cid)) {
+                            Ok(evaluated) => {
+                                let evaluated = evaluated.subst(self.tcx(), substs);
+                                return self.fold_const(evaluated);
+                            }
+                            Err(_) => {}
+                        }
+                    }
+                } else {
+                    if let Some(substs) = self.tcx().lift_to_global(&substs) {
+                        let instance = ty::Instance::resolve(tcx, param_env, def_id, substs);
+                        if let Some(instance) = instance {
+                            let cid = GlobalId {
+                                instance,
+                                promoted: None,
+                            };
+                            match tcx.const_eval(param_env.and(cid)) {
+                                Ok(evaluated) => return self.fold_const(evaluated),
+                                Err(_) => {}
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        constant
+    }
+}
+
+BraceStructTypeFoldableImpl! {
+    impl<'tcx> TypeFoldable<'tcx> for NormalizationResult<'tcx> {
+        normalized_ty
+    }
+}
+
+BraceStructLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for NormalizationResult<'a> {
+        type Lifted = NormalizationResult<'tcx>;
+        normalized_ty
+    }
+}
+
+impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>> {
+    type Canonicalized = CanonicalProjectionGoal<'gcx>;
+
+    fn intern(
+        _gcx: TyCtxt<'_, 'gcx, 'gcx>,
+        value: Canonical<'gcx, Self::Lifted>,
+    ) -> Self::Canonicalized {
+        value
+    }
+}
+
+impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for QueryResult<'tcx, NormalizationResult<'tcx>> {
+    // we ought to intern this, but I'm too lazy just now
+    type Canonicalized = Rc<Canonical<'gcx, QueryResult<'gcx, NormalizationResult<'gcx>>>>;
+
+    fn intern(
+        _gcx: TyCtxt<'_, 'gcx, 'gcx>,
+        value: Canonical<'gcx, Self::Lifted>,
+    ) -> Self::Canonicalized {
+        Rc::new(value)
+    }
+}
+
+impl_stable_hash_for!(struct NormalizationResult<'tcx> {
+    normalized_ty
+});
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 24d3b37f804..d85a95e87ea 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -106,6 +106,7 @@ pub struct GlobalArenas<'tcx> {
     tables: TypedArena<ty::TypeckTables<'tcx>>,
     /// miri allocations
     const_allocs: TypedArena<interpret::Allocation>,
+
 }
 
 impl<'tcx> GlobalArenas<'tcx> {
diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs
index 21affcbc9ed..95865d5eab0 100644
--- a/src/librustc/ty/maps/config.rs
+++ b/src/librustc/ty/maps/config.rs
@@ -11,6 +11,7 @@
 use dep_graph::SerializedDepNodeIndex;
 use hir::def_id::{CrateNum, DefId, DefIndex};
 use mir::interpret::{GlobalId};
+use traits::query::CanonicalProjectionGoal;
 use ty::{self, Ty, TyCtxt};
 use ty::subst::Substs;
 use ty::maps::queries;
@@ -51,6 +52,15 @@ impl<'tcx, M: QueryConfig<Key=DefId>> QueryDescription<'tcx> for M {
     }
 }
 
+impl<'tcx> QueryDescription<'tcx> for queries::normalize_projection_ty<'tcx> {
+    fn describe(
+        _tcx: TyCtxt,
+        goal: CanonicalProjectionGoal<'tcx>,
+    ) -> String {
+        format!("normalizing `{:?}`", goal)
+    }
+}
+
 impl<'tcx> QueryDescription<'tcx> for queries::is_copy_raw<'tcx> {
     fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String {
         format!("computing whether `{}` is `Copy`", env.value)
diff --git a/src/librustc/ty/maps/keys.rs b/src/librustc/ty/maps/keys.rs
index 8fb1ad0da82..1f040522fda 100644
--- a/src/librustc/ty/maps/keys.rs
+++ b/src/librustc/ty/maps/keys.rs
@@ -11,6 +11,7 @@
 //! Defines the set of legal keys that can be used in queries.
 
 use hir::def_id::{CrateNum, DefId, LOCAL_CRATE, DefIndex};
+use traits::query::CanonicalProjectionGoal;
 use ty::{self, Ty, TyCtxt};
 use ty::subst::Substs;
 use ty::fast_reject::SimplifiedType;
@@ -170,3 +171,13 @@ impl Key for InternedString {
         DUMMY_SP
     }
 }
+
+impl<'tcx> Key for CanonicalProjectionGoal<'tcx> {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, _tcx: TyCtxt) -> Span {
+        DUMMY_SP
+    }
+}
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index 0ded759fec7..2dc6cd7a4eb 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -14,6 +14,7 @@ use hir::def_id::{CrateNum, DefId, DefIndex};
 use hir::def::{Def, Export};
 use hir::{self, TraitCandidate, ItemLocalId, TransFnAttrs};
 use hir::svh::Svh;
+use infer::canonical::{Canonical, QueryResult};
 use lint;
 use middle::borrowck::BorrowCheckResult;
 use middle::cstore::{ExternCrate, LinkagePreference, NativeLibrary,
@@ -33,6 +34,8 @@ use mir::interpret::{GlobalId};
 use session::{CompileResult, CrateDisambiguator};
 use session::config::OutputFilenames;
 use traits::Vtable;
+use traits::query::{CanonicalProjectionGoal, NoSolution};
+use traits::query::normalize::NormalizationResult;
 use traits::specialization_graph;
 use ty::{self, CrateInherentImpls, Ty, TyCtxt};
 use ty::steal::Steal;
@@ -380,6 +383,14 @@ define_maps! { <'tcx>
     [] fn erase_regions_ty: erase_regions_ty(Ty<'tcx>) -> Ty<'tcx>,
     [] fn fully_normalize_monormophic_ty: normalize_ty_node(Ty<'tcx>) -> Ty<'tcx>,
 
+    /// Do not call this query directly: invoke `normalize` instead.
+    [] fn normalize_projection_ty: NormalizeProjectionTy(
+        CanonicalProjectionGoal<'tcx>
+    ) -> Result<
+        Lrc<Canonical<'tcx, QueryResult<'tcx, NormalizationResult<'tcx>>>>,
+        NoSolution,
+    >,
+
     [] fn substitute_normalize_and_test_predicates:
         substitute_normalize_and_test_predicates_node((DefId, &'tcx Substs<'tcx>)) -> bool,
 
@@ -537,6 +548,7 @@ fn output_filenames_node<'tcx>(_: CrateNum) -> DepConstructor<'tcx> {
 fn vtable_methods_node<'tcx>(trait_ref: ty::PolyTraitRef<'tcx>) -> DepConstructor<'tcx> {
     DepConstructor::VtableMethods{ trait_ref }
 }
+
 fn normalize_ty_node<'tcx>(_: Ty<'tcx>) -> DepConstructor<'tcx> {
     DepConstructor::NormalizeTy
 }
diff --git a/src/librustc/ty/maps/plumbing.rs b/src/librustc/ty/maps/plumbing.rs
index 68d10888902..2124b6296aa 100644
--- a/src/librustc/ty/maps/plumbing.rs
+++ b/src/librustc/ty/maps/plumbing.rs
@@ -773,6 +773,7 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
         DepKind::VtableMethods |
         DepKind::EraseRegionsTy |
         DepKind::NormalizeTy |
+        DepKind::NormalizeProjectionTy |
         DepKind::SubstituteNormalizeAndTestPredicates |
         DepKind::InstanceDefSizeEstimate |
 
diff --git a/src/librustc_driver/Cargo.toml b/src/librustc_driver/Cargo.toml
index 6a1d9e56534..3bff79ed3a6 100644
--- a/src/librustc_driver/Cargo.toml
+++ b/src/librustc_driver/Cargo.toml
@@ -28,6 +28,7 @@ rustc_plugin = { path = "../librustc_plugin" }
 rustc_privacy = { path = "../librustc_privacy" }
 rustc_resolve = { path = "../librustc_resolve" }
 rustc_save_analysis = { path = "../librustc_save_analysis" }
+rustc_traits = { path = "../librustc_traits" }
 rustc_trans_utils = { path = "../librustc_trans_utils" }
 rustc_typeck = { path = "../librustc_typeck" }
 serialize = { path = "../libserialize" }
diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index 485ee1130d3..542f818c381 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -31,6 +31,7 @@ use rustc_incremental;
 use rustc_resolve::{MakeGlobMap, Resolver, ResolverArenas};
 use rustc_metadata::creader::CrateLoader;
 use rustc_metadata::cstore::{self, CStore};
+use rustc_traits;
 use rustc_trans_utils::trans_crate::TransCrate;
 use rustc_typeck as typeck;
 use rustc_privacy;
@@ -942,6 +943,7 @@ pub fn default_provide(providers: &mut ty::maps::Providers) {
     traits::provide(providers);
     reachable::provide(providers);
     rustc_passes::provide(providers);
+    rustc_traits::provide(providers);
     middle::region::provide(providers);
     cstore::provide(providers);
     lint::provide(providers);
diff --git a/src/librustc_driver/lib.rs b/src/librustc_driver/lib.rs
index f6aa58213fc..746f2db4767 100644
--- a/src/librustc_driver/lib.rs
+++ b/src/librustc_driver/lib.rs
@@ -46,6 +46,7 @@ extern crate rustc_metadata;
 extern crate rustc_mir;
 extern crate rustc_resolve;
 extern crate rustc_save_analysis;
+extern crate rustc_traits;
 extern crate rustc_trans_utils;
 extern crate rustc_typeck;
 extern crate serialize;
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 c474cabdb3c..06e6be5cd56 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,8 @@ 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, FulfillmentContext};
+use rustc::traits::{self, Normalized, FulfillmentContext};
+use rustc::traits::query::NoSolution;
 use rustc::ty::error::TypeError;
 use rustc::ty::fold::TypeFoldable;
 use rustc::ty::{self, ToPolyTraitRef, Ty, TyCtxt, TypeVariants};
@@ -1553,10 +1554,17 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
     {
         debug!("normalize(value={:?}, location={:?})", value, location);
         self.fully_perform_op(location.at_self(), |this| {
-            let mut selcx = traits::SelectionContext::new(this.infcx);
-            let cause = this.misc(this.last_span);
-            let traits::Normalized { value, obligations } =
-                traits::normalize(&mut selcx, this.param_env, cause, value);
+            let Normalized { value, obligations } = this.infcx
+                .at(&this.misc(this.last_span), this.param_env)
+                .normalize(value)
+                .unwrap_or_else(|NoSolution| {
+                    span_bug!(
+                        this.last_span,
+                        "normalization of `{:?}` failed at {:?}",
+                        value,
+                        location,
+                    );
+                });
             Ok(InferOk { value, obligations })
         }).unwrap()
     }
diff --git a/src/librustc_traits/Cargo.toml b/src/librustc_traits/Cargo.toml
new file mode 100644
index 00000000000..dc2a21cdab2
--- /dev/null
+++ b/src/librustc_traits/Cargo.toml
@@ -0,0 +1,18 @@
+[package]
+authors = ["The Rust Project Developers"]
+name = "rustc_traits"
+version = "0.0.0"
+
+[lib]
+name = "rustc_traits"
+path = "lib.rs"
+crate-type = ["dylib"]
+
+[dependencies]
+bitflags = "1.0"
+graphviz = { path = "../libgraphviz" }
+log = { version = "0.4" }
+rustc = { path = "../librustc" }
+rustc_data_structures = { path = "../librustc_data_structures" }
+syntax = { path = "../libsyntax" }
+syntax_pos = { path = "../libsyntax_pos" }
diff --git a/src/librustc_traits/lib.rs b/src/librustc_traits/lib.rs
new file mode 100644
index 00000000000..0d92404d24b
--- /dev/null
+++ b/src/librustc_traits/lib.rs
@@ -0,0 +1,37 @@
+// 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.
+
+//! New recursive solver modeled on Chalk's recursive solver. Most of
+//! the guts are broken up into modules; see the comments in those modules.
+
+#![deny(warnings)]
+
+#![feature(crate_visibility_modifier)]
+#![feature(match_default_bindings)]
+#![feature(underscore_lifetimes)]
+
+#[macro_use]
+extern crate log;
+extern crate rustc;
+extern crate rustc_data_structures;
+extern crate syntax;
+extern crate syntax_pos;
+
+mod normalize_projection_ty;
+mod util;
+
+use rustc::ty::maps::Providers;
+
+pub fn provide(p: &mut Providers) {
+    *p = Providers {
+        normalize_projection_ty: normalize_projection_ty::normalize_projection_ty,
+        ..*p
+    };
+}
diff --git a/src/librustc_traits/normalize_projection_ty.rs b/src/librustc_traits/normalize_projection_ty.rs
new file mode 100644
index 00000000000..55785d9586c
--- /dev/null
+++ b/src/librustc_traits/normalize_projection_ty.rs
@@ -0,0 +1,55 @@
+// 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 rustc::infer::canonical::{Canonical, QueryResult};
+use rustc::traits::{self, FulfillmentContext, Normalized, ObligationCause,
+                    SelectionContext};
+use rustc::traits::query::{CanonicalProjectionGoal, NoSolution, normalize::NormalizationResult};
+use rustc::ty::{ParamEnvAnd, TyCtxt};
+use rustc::util::common::CellUsizeExt;
+use std::rc::Rc;
+use syntax::ast::DUMMY_NODE_ID;
+use syntax_pos::DUMMY_SP;
+use util;
+
+crate fn normalize_projection_ty<'tcx>(
+    tcx: TyCtxt<'_, 'tcx, 'tcx>,
+    goal: CanonicalProjectionGoal<'tcx>,
+) -> Result<Rc<Canonical<'tcx, QueryResult<'tcx, NormalizationResult<'tcx>>>>, NoSolution> {
+    debug!("normalize_provider(goal={:#?})", goal);
+
+    tcx.sess.perf_stats.normalize_projection_ty.increment();
+    tcx.infer_ctxt().enter(|ref infcx| {
+        let (
+            ParamEnvAnd {
+                param_env,
+                value: goal,
+            },
+            canonical_inference_vars,
+        ) = infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &goal);
+        let fulfill_cx = &mut FulfillmentContext::new();
+        let selcx = &mut SelectionContext::new(infcx);
+        let cause = ObligationCause::misc(DUMMY_SP, DUMMY_NODE_ID);
+        let Normalized {
+            value: answer,
+            obligations,
+        } = traits::normalize_projection_type(selcx, param_env, goal, cause, 0);
+        fulfill_cx.register_predicate_obligations(infcx, obligations);
+
+        // Now that we have fulfilled as much as we can, create a solution
+        // from what we've learned.
+        util::make_query_response(
+            infcx,
+            canonical_inference_vars,
+            NormalizationResult { normalized_ty: answer },
+            fulfill_cx,
+        )
+    })
+}
diff --git a/src/librustc_traits/util.rs b/src/librustc_traits/util.rs
new file mode 100644
index 00000000000..976eb442a0d
--- /dev/null
+++ b/src/librustc_traits/util.rs
@@ -0,0 +1,117 @@
+// 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 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::query::NoSolution;
+use rustc::ty;
+use std::fmt::Debug;
+
+/// The canonicalization form of `QueryResult<'tcx, T>`.
+type CanonicalizedQueryResult<'gcx, 'tcx, T> =
+    <QueryResult<'tcx, T> as Canonicalize<'gcx, 'tcx>>::Canonicalized;
+
+crate fn make_query_response<'gcx, 'tcx, T>(
+    infcx: &InferCtxt<'_, 'gcx, 'tcx>,
+    inference_vars: CanonicalVarValues<'tcx>,
+    answer: T,
+    fulfill_cx: &mut FulfillmentContext<'tcx>,
+) -> Result<CanonicalizedQueryResult<'gcx, 'tcx, T>, NoSolution>
+where
+    T: Debug,
+    QueryResult<'tcx, T>: Canonicalize<'gcx, 'tcx>,
+{
+    let tcx = infcx.tcx;
+
+    debug!(
+        "make_query_response(\
+         inference_vars={:?}, \
+         answer={:?})",
+        inference_vars, answer,
+    );
+
+    // Select everything, returning errors.
+    let true_errors = match fulfill_cx.select_where_possible(infcx) {
+        Ok(()) => vec![],
+        Err(errors) => errors,
+    };
+    debug!("true_errors = {:#?}", true_errors);
+
+    if !true_errors.is_empty() {
+        // FIXME -- we don't indicate *why* we failed to solve
+        debug!("make_query_response: true_errors={:#?}", true_errors);
+        return Err(NoSolution);
+    }
+
+    // Anything left unselected *now* must be an ambiguity.
+    let ambig_errors = match fulfill_cx.select_all_or_error(infcx) {
+        Ok(()) => vec![],
+        Err(errors) => errors,
+    };
+    debug!("ambig_errors = {:#?}", ambig_errors);
+
+    let region_obligations = infcx.take_registered_region_obligations();
+
+    let (region_outlives, ty_outlives) = infcx.with_region_constraints(|region_constraints| {
+        let RegionConstraintData {
+            constraints,
+            verifys,
+            givens,
+        } = region_constraints;
+
+        assert!(verifys.is_empty());
+        assert!(givens.is_empty());
+
+        let region_outlives: Vec<_> = constraints
+            .into_iter()
+            .map(|(k, _)| match *k {
+                Constraint::VarSubVar(v1, v2) => {
+                    (tcx.mk_region(ty::ReVar(v1)), tcx.mk_region(ty::ReVar(v2)))
+                }
+                Constraint::VarSubReg(v1, r2) => (tcx.mk_region(ty::ReVar(v1)), r2),
+                Constraint::RegSubVar(r1, v2) => (r1, tcx.mk_region(ty::ReVar(v2))),
+                Constraint::RegSubReg(r1, r2) => (r1, r2),
+            })
+            .collect();
+
+        let ty_outlives: Vec<_> = region_obligations
+            .into_iter()
+            .map(|(_, r_o)| (r_o.sup_type, r_o.sub_region))
+            .collect();
+
+        (region_outlives, ty_outlives)
+    });
+
+    let certainty = if ambig_errors.is_empty() {
+        Certainty::Proven
+    } else {
+        Certainty::Ambiguous
+    };
+
+    let (canonical_result, _) = infcx.canonicalize_response(&QueryResult {
+        var_values: inference_vars,
+        region_constraints: QueryRegionConstraints {
+            region_outlives,
+            ty_outlives,
+        },
+        certainty,
+        value: answer,
+    });
+
+    debug!(
+        "make_query_response: canonical_result = {:#?}",
+        canonical_result
+    );
+
+    Ok(canonical_result)
+}