Auto merge of #50937 - nikomatsakis:chalkify-engine-2, r=scalexm

implement the chalk-engine traits

Preliminary implementation for the Chalk traits in rustc. Lots of `panic!()` placeholders to be filled in later.

This is currently blocked on us landing https://github.com/rust-lang-nursery/chalk/pull/131  in chalk and issuing a new release, which should occur later today.

r? @scalexm
cc @leodasvacas

15 files changed, 934 insertions, 240 deletions

diff --git a/src/Cargo.lock b/src/Cargo.lock
index 0392466956e..40ec413c90a 100644
--- a/src/Cargo.lock
+++ b/src/Cargo.lock
@@ -262,6 +262,23 @@ version = "0.1.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "chalk-engine"
+version = "0.6.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "chalk-macros 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rustc-hash 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "chalk-macros"
+version = "0.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "lazy_static 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "chrono"
 version = "0.4.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1739,6 +1756,7 @@ dependencies = [
  "backtrace 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "bitflags 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "byteorder 1.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "chalk-engine 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "flate2 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "fmt_macros 0.0.0",
  "graphviz 0.0.0",
@@ -1841,6 +1859,11 @@ version = "0.1.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "rustc-hash"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "rustc-main"
 version = "0.0.0"
 dependencies = [
@@ -1982,6 +2005,7 @@ dependencies = [
  "log 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "parking_lot 0.5.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "parking_lot_core 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rustc-hash 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-rayon 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc_cratesio_shim 0.0.0",
  "serialize 0.0.0",
@@ -2216,6 +2240,7 @@ name = "rustc_traits"
 version = "0.0.0"
 dependencies = [
  "bitflags 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "chalk-engine 0.6.0 (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",
@@ -2998,6 +3023,8 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum cargo_metadata 0.5.4 (registry+https://github.com/rust-lang/crates.io-index)" = "6ebd6272a2ca4fd39dbabbd6611eb03df45c2259b3b80b39a9ff8fbdcf42a4b3"
 "checksum cc 1.0.15 (registry+https://github.com/rust-lang/crates.io-index)" = "0ebb87d1116151416c0cf66a0e3fb6430cccd120fd6300794b4dfaa050ac40ba"
 "checksum cfg-if 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "d4c819a1287eb618df47cc647173c5c4c66ba19d888a6e50d605672aed3140de"
+"checksum chalk-engine 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a146c19172c7eea48ea55a7123ac95da786639bc665097f1e14034ee5f1d8699"
+"checksum chalk-macros 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "295635afd6853aa9f20baeb7f0204862440c0fe994c5a253d5f479dac41d047e"
 "checksum chrono 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ba5f60682a4c264e7f8d77b82e7788938a76befdf949d4a98026d19099c9d873"
 "checksum clap 2.31.2 (registry+https://github.com/rust-lang/crates.io-index)" = "f0f16b89cbb9ee36d87483dc939fe9f1e13c05898d56d7b230a0d4dff033a536"
 "checksum clippy_lints 0.0.200 (registry+https://github.com/rust-lang/crates.io-index)" = "d2432663f6bdb90255dcf9df5ca504f99b575bb471281591138f62f9d31f863b"
@@ -3142,6 +3169,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum rustc-ap-syntax 128.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "dcf9ca2901388714e9ccc7de7281ef06cec55d9f245252ba1d635bc86c730d9a"
 "checksum rustc-ap-syntax_pos 128.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e5217444369a36e98e11f4ac976f03878704893832e2e0b57d49f2f31438139f"
 "checksum rustc-demangle 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "11fb43a206a04116ffd7cfcf9bcb941f8eb6cc7ff667272246b0a1c74259a3cb"
+"checksum rustc-hash 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e06ddba37baa245040f932b15403071a46681d7e0e4158e230741943c4718b84"
 "checksum rustc-rayon 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b1aa5cd8c3a706edb19b6ec6aa7b056bdc635b6e99c5cf7014f9af9d92f15e99"
 "checksum rustc-rayon-core 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d69983f8613a9c3ba1a3bbf5e8bdf2fd5c42317b1d8dd8623ca8030173bf8a6b"
 "checksum rustc-serialize 0.3.24 (registry+https://github.com/rust-lang/crates.io-index)" = "dcf128d1287d2ea9d80910b5f1120d0b8eede3fbf1abe91c40d39ea7d51e6fda"
diff --git a/src/librustc/Cargo.toml b/src/librustc/Cargo.toml
index 8f9a8bd5c01..42eccaec9d0 100644
--- a/src/librustc/Cargo.toml
+++ b/src/librustc/Cargo.toml
@@ -26,6 +26,7 @@ syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
 backtrace = "0.3.3"
 byteorder = { version = "1.1", features = ["i128"]}
+chalk-engine = { version = "0.6.0", default-features=false }
 
 # Note that these dependencies are a lie, they're just here to get linkage to
 # work.
@@ -56,3 +57,5 @@ byteorder = { version = "1.1", features = ["i128"]}
 #        compiles, then please feel free to do so!
 flate2 = "1.0"
 tempdir = "0.3"
+
+
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 1d53a305193..c67f09c88bd 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -89,6 +89,7 @@ extern crate rustc_errors as errors;
 extern crate syntax_pos;
 extern crate jobserver;
 extern crate proc_macro;
+extern crate chalk_engine;
 
 extern crate serialize as rustc_serialize; // used by deriving
 
diff --git a/src/librustc/macros.rs b/src/librustc/macros.rs
index 7dc84b9ca29..4178fdb352d 100644
--- a/src/librustc/macros.rs
+++ b/src/librustc/macros.rs
@@ -250,10 +250,7 @@ macro_rules! BraceStructLiftImpl {
 macro_rules! EnumLiftImpl {
     (impl<$($p:tt),*> Lift<$tcx:tt> for $s:path {
         type Lifted = $lifted:ty;
-        $(
-            ($variant:path) ( $( $variant_arg:ident),* )
-        ),*
-        $(,)*
+        $($variants:tt)*
     } $(where $($wc:tt)*)*) => {
         impl<$($p),*> $crate::ty::Lift<$tcx> for $s
             $(where $($wc)*)*
@@ -261,14 +258,44 @@ macro_rules! EnumLiftImpl {
             type Lifted = $lifted;
 
             fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<$lifted> {
-                match self {
-                    $($variant ( $($variant_arg),* ) => {
-                        Some($variant ( $(tcx.lift($variant_arg)?),* ))
-                    })*
-                }
+                EnumLiftImpl!(@Variants(self, tcx) input($($variants)*) output())
             }
         }
     };
+
+    (@Variants($this:expr, $tcx:expr) input() output($($output:tt)*)) => {
+        match $this {
+            $($output)*
+        }
+    };
+
+    (@Variants($this:expr, $tcx:expr)
+     input( ($variant:path) ( $($variant_arg:ident),* ) , $($input:tt)*)
+     output( $($output:tt)*) ) => {
+        EnumLiftImpl!(
+            @Variants($this, $tcx)
+                input($($input)*)
+                output(
+                    $variant ( $($variant_arg),* ) => {
+                        Some($variant ( $($tcx.lift($variant_arg)?),* ))
+                    }
+                    $($output)*
+                )
+        )
+    };
+
+    (@Variants($this:expr, $tcx:expr)
+     input( ($variant:path), $($input:tt)*)
+     output( $($output:tt)*) ) => {
+        EnumLiftImpl!(
+            @Variants($this, $tcx)
+                input($($input)*)
+                output(
+                    $variant => { Some($variant) }
+                    $($output)*
+                )
+        )
+    };
 }
 
 #[macro_export]
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 72d8a2989b1..3bd4e11b0e8 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -17,17 +17,21 @@ pub use self::FulfillmentErrorCode::*;
 pub use self::Vtable::*;
 pub use self::ObligationCauseCode::*;
 
+use chalk_engine;
 use hir;
 use hir::def_id::DefId;
 use infer::outlives::env::OutlivesEnvironment;
 use middle::region;
 use middle::const_val::ConstEvalErr;
 use ty::subst::Substs;
-use ty::{self, AdtKind, Slice, Ty, TyCtxt, GenericParamDefKind, TypeFoldable, ToPredicate};
+use ty::{self, AdtKind, Slice, Ty, TyCtxt, GenericParamDefKind, ToPredicate};
 use ty::error::{ExpectedFound, TypeError};
+use ty::fold::{TypeFolder, TypeFoldable, TypeVisitor};
+use infer::canonical::{Canonical, Canonicalize};
 use infer::{InferCtxt};
 
 use rustc_data_structures::sync::Lrc;
+use std::fmt::Debug;
 use std::rc::Rc;
 use syntax::ast;
 use syntax_pos::{Span, DUMMY_SP};
@@ -1003,3 +1007,59 @@ pub fn provide(providers: &mut ty::maps::Providers) {
         ..*providers
     };
 }
+
+impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ty::ParamEnvAnd<'tcx, Goal<'tcx>> {
+    // we ought to intern this, but I'm too lazy just now
+    type Canonicalized = Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>;
+
+    fn intern(
+        _gcx: TyCtxt<'_, 'gcx, 'gcx>,
+        value: Canonical<'gcx, Self::Lifted>,
+    ) -> Self::Canonicalized {
+        value
+    }
+}
+
+pub trait ExClauseFold<'tcx>
+where
+    Self: chalk_engine::context::Context + Clone,
+{
+    fn fold_ex_clause_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(
+        ex_clause: &chalk_engine::ExClause<Self>,
+        folder: &mut F,
+    ) -> chalk_engine::ExClause<Self>;
+
+    fn visit_ex_clause_with<'gcx: 'tcx, V: TypeVisitor<'tcx>>(
+        ex_clause: &chalk_engine::ExClause<Self>,
+        visitor: &mut V,
+    ) -> bool;
+}
+
+pub trait ExClauseLift<'tcx>
+where
+    Self: chalk_engine::context::Context + Clone,
+{
+    type LiftedExClause: Debug + 'tcx;
+
+    fn lift_ex_clause_to_tcx<'a, 'gcx>(
+        ex_clause: &chalk_engine::ExClause<Self>,
+        tcx: TyCtxt<'a, 'gcx, 'tcx>,
+    ) -> Option<Self::LiftedExClause>;
+}
+
+impl<'gcx: 'tcx, 'tcx, C> Canonicalize<'gcx, 'tcx> for chalk_engine::ExClause<C>
+where
+    C: chalk_engine::context::Context + Clone,
+    C: ExClauseLift<'gcx> + ExClauseFold<'tcx>,
+    C::Substitution: Clone,
+    C::RegionConstraint: Clone,
+{
+    type Canonicalized = Canonical<'gcx, C::LiftedExClause>;
+
+    fn intern(
+        _gcx: TyCtxt<'_, 'gcx, 'gcx>,
+        value: Canonical<'gcx, Self::Lifted>,
+    ) -> Self::Canonicalized {
+        value
+    }
+}
diff --git a/src/librustc/traits/structural_impls.rs b/src/librustc/traits/structural_impls.rs
index 2e2f7a2ad31..d1304a0a3f8 100644
--- a/src/librustc/traits/structural_impls.rs
+++ b/src/librustc/traits/structural_impls.rs
@@ -8,11 +8,12 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use chalk_engine;
 use rustc_data_structures::accumulate_vec::AccumulateVec;
 use traits;
 use traits::project::Normalized;
-use ty::{self, Lift, TyCtxt};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
+use ty::{self, Lift, TyCtxt};
 
 use std::fmt;
 use std::rc::Rc;
@@ -21,23 +22,24 @@ use std::rc::Rc;
 
 impl<'tcx, T: fmt::Debug> fmt::Debug for Normalized<'tcx, T> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "Normalized({:?},{:?})",
-               self.value,
-               self.obligations)
+        write!(f, "Normalized({:?},{:?})", self.value, self.obligations)
     }
 }
 
 impl<'tcx, O: fmt::Debug> fmt::Debug for traits::Obligation<'tcx, O> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         if ty::tls::with(|tcx| tcx.sess.verbose()) {
-            write!(f, "Obligation(predicate={:?},cause={:?},depth={})",
-                   self.predicate,
-                   self.cause,
-                   self.recursion_depth)
+            write!(
+                f,
+                "Obligation(predicate={:?},cause={:?},depth={})",
+                self.predicate, self.cause, self.recursion_depth
+            )
         } else {
-            write!(f, "Obligation(predicate={:?},depth={})",
-                   self.predicate,
-                   self.recursion_depth)
+            write!(
+                f,
+                "Obligation(predicate={:?},depth={})",
+                self.predicate, self.recursion_depth
+            )
         }
     }
 }
@@ -45,57 +47,52 @@ impl<'tcx, O: fmt::Debug> fmt::Debug for traits::Obligation<'tcx, O> {
 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::Vtable<'tcx, N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         match *self {
-            super::VtableImpl(ref v) =>
-                write!(f, "{:?}", v),
+            super::VtableImpl(ref v) => write!(f, "{:?}", v),
 
-            super::VtableAutoImpl(ref t) =>
-                write!(f, "{:?}", t),
+            super::VtableAutoImpl(ref t) => write!(f, "{:?}", t),
 
-            super::VtableClosure(ref d) =>
-                write!(f, "{:?}", d),
+            super::VtableClosure(ref d) => write!(f, "{:?}", d),
 
-            super::VtableGenerator(ref d) =>
-                write!(f, "{:?}", d),
+            super::VtableGenerator(ref d) => write!(f, "{:?}", d),
 
-            super::VtableFnPointer(ref d) =>
-                write!(f, "VtableFnPointer({:?})", d),
+            super::VtableFnPointer(ref d) => write!(f, "VtableFnPointer({:?})", d),
 
-            super::VtableObject(ref d) =>
-                write!(f, "{:?}", d),
+            super::VtableObject(ref d) => write!(f, "{:?}", d),
 
-            super::VtableParam(ref n) =>
-                write!(f, "VtableParam({:?})", n),
+            super::VtableParam(ref n) => write!(f, "VtableParam({:?})", n),
 
-            super::VtableBuiltin(ref d) =>
-                write!(f, "{:?}", d)
+            super::VtableBuiltin(ref d) => write!(f, "{:?}", d),
         }
     }
 }
 
 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableImplData<'tcx, N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "VtableImpl(impl_def_id={:?}, substs={:?}, nested={:?})",
-               self.impl_def_id,
-               self.substs,
-               self.nested)
+        write!(
+            f,
+            "VtableImpl(impl_def_id={:?}, substs={:?}, nested={:?})",
+            self.impl_def_id, self.substs, self.nested
+        )
     }
 }
 
 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableGeneratorData<'tcx, N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "VtableGenerator(generator_def_id={:?}, substs={:?}, nested={:?})",
-               self.generator_def_id,
-               self.substs,
-               self.nested)
+        write!(
+            f,
+            "VtableGenerator(generator_def_id={:?}, substs={:?}, nested={:?})",
+            self.generator_def_id, self.substs, self.nested
+        )
     }
 }
 
 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableClosureData<'tcx, N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "VtableClosure(closure_def_id={:?}, substs={:?}, nested={:?})",
-               self.closure_def_id,
-               self.substs,
-               self.nested)
+        write!(
+            f,
+            "VtableClosure(closure_def_id={:?}, substs={:?}, nested={:?})",
+            self.closure_def_id, self.substs, self.nested
+        )
     }
 }
 
@@ -107,34 +104,37 @@ impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableBuiltinData<N> {
 
 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableAutoImplData<N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "VtableAutoImplData(trait_def_id={:?}, nested={:?})",
-               self.trait_def_id,
-               self.nested)
+        write!(
+            f,
+            "VtableAutoImplData(trait_def_id={:?}, nested={:?})",
+            self.trait_def_id, self.nested
+        )
     }
 }
 
 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableObjectData<'tcx, N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "VtableObject(upcast={:?}, vtable_base={}, nested={:?})",
-               self.upcast_trait_ref,
-               self.vtable_base,
-               self.nested)
+        write!(
+            f,
+            "VtableObject(upcast={:?}, vtable_base={}, nested={:?})",
+            self.upcast_trait_ref, self.vtable_base, self.nested
+        )
     }
 }
 
 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableFnPointerData<'tcx, N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "VtableFnPointer(fn_ty={:?}, nested={:?})",
-               self.fn_ty,
-               self.nested)
+        write!(
+            f,
+            "VtableFnPointer(fn_ty={:?}, nested={:?})",
+            self.fn_ty, self.nested
+        )
     }
 }
 
 impl<'tcx> fmt::Debug for traits::FulfillmentError<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "FulfillmentError({:?},{:?})",
-               self.obligation,
-               self.code)
+        write!(f, "FulfillmentError({:?},{:?})", self.obligation, self.code)
     }
 }
 
@@ -143,9 +143,10 @@ impl<'tcx> fmt::Debug for traits::FulfillmentErrorCode<'tcx> {
         match *self {
             super::CodeSelectionError(ref e) => write!(f, "{:?}", e),
             super::CodeProjectionError(ref e) => write!(f, "{:?}", e),
-            super::CodeSubtypeError(ref a, ref b) =>
-                write!(f, "CodeSubtypeError({:?}, {:?})", a, b),
-            super::CodeAmbiguity => write!(f, "Ambiguity")
+            super::CodeSubtypeError(ref a, ref b) => {
+                write!(f, "CodeSubtypeError({:?}, {:?})", a, b)
+            }
+            super::CodeAmbiguity => write!(f, "Ambiguity"),
         }
     }
 }
@@ -166,18 +167,13 @@ impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
             super::Unimplemented => Some(super::Unimplemented),
             super::OutputTypeParameterMismatch(a, b, ref err) => {
                 tcx.lift(&(a, b)).and_then(|(a, b)| {
-                    tcx.lift(err).map(|err| {
-                        super::OutputTypeParameterMismatch(a, b, err)
-                    })
+                    tcx.lift(err)
+                        .map(|err| super::OutputTypeParameterMismatch(a, b, err))
                 })
             }
-            super::TraitNotObjectSafe(def_id) => {
-                Some(super::TraitNotObjectSafe(def_id))
-            }
-            super::ConstEvalFailure(ref err) => {
-                tcx.lift(err).map(super::ConstEvalFailure)
-            }
-            super::Overflow => bug!() // FIXME: ape ConstEvalFailure?
+            super::TraitNotObjectSafe(def_id) => Some(super::TraitNotObjectSafe(def_id)),
+            super::ConstEvalFailure(ref err) => tcx.lift(err).map(super::ConstEvalFailure),
+            super::Overflow => bug!(), // FIXME: ape ConstEvalFailure?
         }
     }
 }
@@ -195,16 +191,11 @@ impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCauseCode<'a> {
             super::ReferenceOutlivesReferent(ty) => {
                 tcx.lift(&ty).map(super::ReferenceOutlivesReferent)
             }
-            super::ObjectTypeBound(ty, r) => {
-                tcx.lift(&ty).and_then(|ty| {
-                    tcx.lift(&r).and_then(|r| {
-                        Some(super::ObjectTypeBound(ty, r))
-                    })
-                })
-            }
-            super::ObjectCastObligation(ty) => {
-                tcx.lift(&ty).map(super::ObjectCastObligation)
-            }
+            super::ObjectTypeBound(ty, r) => tcx.lift(&ty).and_then(|ty| {
+                tcx.lift(&r)
+                    .and_then(|r| Some(super::ObjectTypeBound(ty, r)))
+            }),
+            super::ObjectCastObligation(ty) => tcx.lift(&ty).map(super::ObjectCastObligation),
             super::AssignmentLhsSized => Some(super::AssignmentLhsSized),
             super::TupleInitializerSized => Some(super::TupleInitializerSized),
             super::StructInitializerSized => Some(super::StructInitializerSized),
@@ -222,20 +213,20 @@ impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCauseCode<'a> {
             super::ImplDerivedObligation(ref cause) => {
                 tcx.lift(cause).map(super::ImplDerivedObligation)
             }
-            super::CompareImplMethodObligation { item_name,
-                                                 impl_item_def_id,
-                                                 trait_item_def_id } => {
-                Some(super::CompareImplMethodObligation {
-                    item_name,
-                    impl_item_def_id,
-                    trait_item_def_id,
-                })
-            }
+            super::CompareImplMethodObligation {
+                item_name,
+                impl_item_def_id,
+                trait_item_def_id,
+            } => Some(super::CompareImplMethodObligation {
+                item_name,
+                impl_item_def_id,
+                trait_item_def_id,
+            }),
             super::ExprAssignable => Some(super::ExprAssignable),
-            super::MatchExpressionArm { arm_span, source } => {
-                Some(super::MatchExpressionArm { arm_span,
-                                                 source: source })
-            }
+            super::MatchExpressionArm { arm_span, source } => Some(super::MatchExpressionArm {
+                arm_span,
+                source: source,
+            }),
             super::IfExpression => Some(super::IfExpression),
             super::IfExpressionWithNoElse => Some(super::IfExpressionWithNoElse),
             super::MainFunctionType => Some(super::MainFunctionType),
@@ -252,12 +243,11 @@ impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
     type Lifted = traits::DerivedObligationCause<'tcx>;
     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
         tcx.lift(&self.parent_trait_ref).and_then(|trait_ref| {
-            tcx.lift(&*self.parent_code).map(|code| {
-                traits::DerivedObligationCause {
+            tcx.lift(&*self.parent_code)
+                .map(|code| traits::DerivedObligationCause {
                     parent_trait_ref: trait_ref,
-                    parent_code: Rc::new(code)
-                }
-            })
+                    parent_code: Rc::new(code),
+                })
         })
     }
 }
@@ -265,12 +255,10 @@ impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
 impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCause<'a> {
     type Lifted = traits::ObligationCause<'tcx>;
     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
-        tcx.lift(&self.code).map(|code| {
-            traits::ObligationCause {
-                span: self.span,
-                body_id: self.body_id,
-                code,
-            }
+        tcx.lift(&self.code).map(|code| traits::ObligationCause {
+            span: self.span,
+            body_id: self.body_id,
+            code,
         })
     }
 }
@@ -283,49 +271,40 @@ impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
             traits::VtableImpl(traits::VtableImplData {
                 impl_def_id,
                 substs,
-                nested
-            }) => {
-                tcx.lift(&substs).map(|substs| {
-                    traits::VtableImpl(traits::VtableImplData {
-                        impl_def_id,
-                        substs,
-                        nested,
-                    })
+                nested,
+            }) => tcx.lift(&substs).map(|substs| {
+                traits::VtableImpl(traits::VtableImplData {
+                    impl_def_id,
+                    substs,
+                    nested,
                 })
-            }
+            }),
             traits::VtableAutoImpl(t) => Some(traits::VtableAutoImpl(t)),
             traits::VtableGenerator(traits::VtableGeneratorData {
                 generator_def_id,
                 substs,
-                nested
-            }) => {
-                tcx.lift(&substs).map(|substs| {
-                    traits::VtableGenerator(traits::VtableGeneratorData {
-                        generator_def_id: generator_def_id,
-                        substs: substs,
-                        nested: nested
-                    })
+                nested,
+            }) => tcx.lift(&substs).map(|substs| {
+                traits::VtableGenerator(traits::VtableGeneratorData {
+                    generator_def_id: generator_def_id,
+                    substs: substs,
+                    nested: nested,
                 })
-            }
+            }),
             traits::VtableClosure(traits::VtableClosureData {
                 closure_def_id,
                 substs,
-                nested
-            }) => {
-                tcx.lift(&substs).map(|substs| {
-                    traits::VtableClosure(traits::VtableClosureData {
-                        closure_def_id,
-                        substs,
-                        nested,
-                    })
+                nested,
+            }) => tcx.lift(&substs).map(|substs| {
+                traits::VtableClosure(traits::VtableClosureData {
+                    closure_def_id,
+                    substs,
+                    nested,
                 })
-            }
+            }),
             traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested }) => {
                 tcx.lift(&fn_ty).map(|fn_ty| {
-                    traits::VtableFnPointer(traits::VtableFnPointerData {
-                        fn_ty,
-                        nested,
-                    })
+                    traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested })
                 })
             }
             traits::VtableParam(n) => Some(traits::VtableParam(n)),
@@ -333,16 +312,14 @@ impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
             traits::VtableObject(traits::VtableObjectData {
                 upcast_trait_ref,
                 vtable_base,
-                nested
-            }) => {
-                tcx.lift(&upcast_trait_ref).map(|trait_ref| {
-                    traits::VtableObject(traits::VtableObjectData {
-                        upcast_trait_ref: trait_ref,
-                        vtable_base,
-                        nested,
-                    })
+                nested,
+            }) => tcx.lift(&upcast_trait_ref).map(|trait_ref| {
+                traits::VtableObject(traits::VtableObjectData {
+                    upcast_trait_ref: trait_ref,
+                    vtable_base,
+                    nested,
                 })
-            }
+            }),
         }
     }
 }
@@ -350,8 +327,7 @@ impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
 ///////////////////////////////////////////////////////////////////////////
 // TypeFoldable implementations.
 
-impl<'tcx, O: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Obligation<'tcx, O>
-{
+impl<'tcx, O: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Obligation<'tcx, O> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
         traits::Obligation {
             cause: self.cause.clone(),
@@ -536,6 +512,14 @@ EnumTypeFoldableImpl! {
     }
 }
 
+EnumLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for traits::WhereClauseAtom<'a> {
+        type Lifted = traits::WhereClauseAtom<'tcx>;
+        (traits::WhereClauseAtom::Implemented)(trait_ref),
+        (traits::WhereClauseAtom::ProjectionEq)(projection),
+    }
+}
+
 EnumTypeFoldableImpl! {
     impl<'tcx> TypeFoldable<'tcx> for traits::DomainGoal<'tcx> {
         (traits::DomainGoal::Holds)(wc),
@@ -549,7 +533,21 @@ EnumTypeFoldableImpl! {
     }
 }
 
-CloneTypeFoldableImpls! {
+EnumLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for traits::DomainGoal<'a> {
+        type Lifted = traits::DomainGoal<'tcx>;
+        (traits::DomainGoal::Holds)(wc),
+        (traits::DomainGoal::WellFormed)(wc),
+        (traits::DomainGoal::FromEnv)(wc),
+        (traits::DomainGoal::WellFormedTy)(ty),
+        (traits::DomainGoal::Normalize)(projection),
+        (traits::DomainGoal::FromEnvTy)(ty),
+        (traits::DomainGoal::RegionOutlives)(predicate),
+        (traits::DomainGoal::TypeOutlives)(predicate),
+    }
+}
+
+CloneTypeFoldableAndLiftImpls! {
     traits::QuantifierKind,
 }
 
@@ -564,9 +562,23 @@ EnumTypeFoldableImpl! {
     }
 }
 
+EnumLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for traits::Goal<'a> {
+        type Lifted = traits::Goal<'tcx>;
+        (traits::Goal::Implies)(hypotheses, goal),
+        (traits::Goal::And)(goal1, goal2),
+        (traits::Goal::Not)(goal),
+        (traits::Goal::DomainGoal)(domain_goal),
+        (traits::Goal::Quantified)(kind, goal),
+        (traits::Goal::CannotProve),
+    }
+}
+
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::Slice<traits::Goal<'tcx>> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        let v = self.iter().map(|t| t.fold_with(folder)).collect::<AccumulateVec<[_; 8]>>();
+        let v = self.iter()
+            .map(|t| t.fold_with(folder))
+            .collect::<AccumulateVec<[_; 8]>>();
         folder.tcx().intern_goals(&v)
     }
 
@@ -602,7 +614,9 @@ EnumTypeFoldableImpl! {
 
 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::Slice<traits::Clause<'tcx>> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
-        let v = self.iter().map(|t| t.fold_with(folder)).collect::<AccumulateVec<[_; 8]>>();
+        let v = self.iter()
+            .map(|t| t.fold_with(folder))
+            .collect::<AccumulateVec<[_; 8]>>();
         folder.tcx().intern_clauses(&v)
     }
 
@@ -610,3 +624,59 @@ impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::Slice<traits::Clause<'tcx>> {
         self.iter().any(|t| t.visit_with(visitor))
     }
 }
+
+impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::ExClause<C>
+where
+    C: traits::ExClauseFold<'tcx>,
+    C::Substitution: Clone,
+    C::RegionConstraint: Clone,
+{
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        <C as traits::ExClauseFold>::fold_ex_clause_with(
+            self,
+            folder,
+        )
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        <C as traits::ExClauseFold>::visit_ex_clause_with(
+            self,
+            visitor,
+        )
+    }
+}
+
+impl<'tcx, C> Lift<'tcx> for chalk_engine::ExClause<C>
+where
+    C: chalk_engine::context::Context + Clone,
+    C: traits::ExClauseLift<'tcx>,
+{
+    type Lifted = C::LiftedExClause;
+
+    fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        <C as traits::ExClauseLift>::lift_ex_clause_to_tcx(self, tcx)
+    }
+}
+
+EnumTypeFoldableImpl! {
+    impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::DelayedLiteral<C> {
+        (chalk_engine::DelayedLiteral::CannotProve)(a),
+        (chalk_engine::DelayedLiteral::Negative)(a),
+        (chalk_engine::DelayedLiteral::Positive)(a, b),
+    } where
+        C: chalk_engine::context::Context + Clone,
+        C::CanonicalConstrainedSubst: TypeFoldable<'tcx>,
+}
+
+EnumTypeFoldableImpl! {
+    impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::Literal<C> {
+        (chalk_engine::Literal::Negative)(a),
+        (chalk_engine::Literal::Positive)(a),
+    } where
+        C: chalk_engine::context::Context + Clone,
+        C::GoalInEnvironment: Clone + TypeFoldable<'tcx>,
+}
+
+CloneTypeFoldableAndLiftImpls! {
+    chalk_engine::TableIndex,
+}
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 82d796253bd..8a73219cf70 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -1512,6 +1512,57 @@ impl<'a, 'tcx> Lift<'tcx> for Region<'a> {
     }
 }
 
+impl<'a, 'tcx> Lift<'tcx> for &'a Goal<'a> {
+    type Lifted = &'tcx Goal<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Goal<'tcx>> {
+        if tcx.interners.arena.in_arena(*self as *const _) {
+            return Some(unsafe { mem::transmute(*self) });
+        }
+        // Also try in the global tcx if we're not that.
+        if !tcx.is_global() {
+            self.lift_to_tcx(tcx.global_tcx())
+        } else {
+            None
+        }
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for &'a Slice<Goal<'a>> {
+    type Lifted = &'tcx Slice<Goal<'tcx>>;
+    fn lift_to_tcx<'b, 'gcx>(
+        &self,
+        tcx: TyCtxt<'b, 'gcx, 'tcx>,
+    ) -> Option<&'tcx Slice<Goal<'tcx>>> {
+        if tcx.interners.arena.in_arena(*self as *const _) {
+            return Some(unsafe { mem::transmute(*self) });
+        }
+        // Also try in the global tcx if we're not that.
+        if !tcx.is_global() {
+            self.lift_to_tcx(tcx.global_tcx())
+        } else {
+            None
+        }
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for &'a Slice<Clause<'a>> {
+    type Lifted = &'tcx Slice<Clause<'tcx>>;
+    fn lift_to_tcx<'b, 'gcx>(
+        &self,
+        tcx: TyCtxt<'b, 'gcx, 'tcx>,
+    ) -> Option<&'tcx Slice<Clause<'tcx>>> {
+        if tcx.interners.arena.in_arena(*self as *const _) {
+            return Some(unsafe { mem::transmute(*self) });
+        }
+        // Also try in the global tcx if we're not that.
+        if !tcx.is_global() {
+            self.lift_to_tcx(tcx.global_tcx())
+        } else {
+            None
+        }
+    }
+}
+
 impl<'a, 'tcx> Lift<'tcx> for &'a Const<'a> {
     type Lifted = &'tcx Const<'tcx>;
     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<&'tcx Const<'tcx>> {
diff --git a/src/librustc_data_structures/Cargo.toml b/src/librustc_data_structures/Cargo.toml
index bb1fb84a0ce..c2b1130b75a 100644
--- a/src/librustc_data_structures/Cargo.toml
+++ b/src/librustc_data_structures/Cargo.toml
@@ -17,6 +17,7 @@ cfg-if = "0.1.2"
 stable_deref_trait = "1.0.0"
 parking_lot_core = "0.2.8"
 rustc-rayon = "0.1.0"
+rustc-hash = "1.0.0"
 
 [dependencies.parking_lot]
 version = "0.5"
diff --git a/src/librustc_data_structures/fx.rs b/src/librustc_data_structures/fx.rs
index 5bf25437763..3bf3170d1df 100644
--- a/src/librustc_data_structures/fx.rs
+++ b/src/librustc_data_structures/fx.rs
@@ -10,11 +10,11 @@
 
 use std::collections::{HashMap, HashSet};
 use std::default::Default;
-use std::hash::{Hasher, Hash, BuildHasherDefault};
-use std::ops::BitXor;
+use std::hash::Hash;
 
-pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
-pub type FxHashSet<V> = HashSet<V, BuildHasherDefault<FxHasher>>;
+pub use rustc_hash::FxHashMap;
+pub use rustc_hash::FxHashSet;
+pub use rustc_hash::FxHasher;
 
 #[allow(non_snake_case)]
 pub fn FxHashMap<K: Hash + Eq, V>() -> FxHashMap<K, V> {
@@ -26,84 +26,3 @@ pub fn FxHashSet<V: Hash + Eq>() -> FxHashSet<V> {
     HashSet::default()
 }
 
-/// A speedy hash algorithm for use within rustc. The hashmap in liballoc
-/// by default uses SipHash which isn't quite as speedy as we want. In the
-/// compiler we're not really worried about DOS attempts, so we use a fast
-/// non-cryptographic hash.
-///
-/// This is the same as the algorithm used by Firefox -- which is a homespun
-/// one not based on any widely-known algorithm -- though modified to produce
-/// 64-bit hash values instead of 32-bit hash values. It consistently
-/// out-performs an FNV-based hash within rustc itself -- the collision rate is
-/// similar or slightly worse than FNV, but the speed of the hash function
-/// itself is much higher because it works on up to 8 bytes at a time.
-pub struct FxHasher {
-    hash: usize
-}
-
-#[cfg(target_pointer_width = "32")]
-const K: usize = 0x9e3779b9;
-#[cfg(target_pointer_width = "64")]
-const K: usize = 0x517cc1b727220a95;
-
-impl Default for FxHasher {
-    #[inline]
-    fn default() -> FxHasher {
-        FxHasher { hash: 0 }
-    }
-}
-
-impl FxHasher {
-    #[inline]
-    fn add_to_hash(&mut self, i: usize) {
-        self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);
-    }
-}
-
-impl Hasher for FxHasher {
-    #[inline]
-    fn write(&mut self, bytes: &[u8]) {
-        for byte in bytes {
-            let i = *byte;
-            self.add_to_hash(i as usize);
-        }
-    }
-
-    #[inline]
-    fn write_u8(&mut self, i: u8) {
-        self.add_to_hash(i as usize);
-    }
-
-    #[inline]
-    fn write_u16(&mut self, i: u16) {
-        self.add_to_hash(i as usize);
-    }
-
-    #[inline]
-    fn write_u32(&mut self, i: u32) {
-        self.add_to_hash(i as usize);
-    }
-
-    #[cfg(target_pointer_width = "32")]
-    #[inline]
-    fn write_u64(&mut self, i: u64) {
-        self.add_to_hash(i as usize);
-        self.add_to_hash((i >> 32) as usize);
-    }
-
-    #[cfg(target_pointer_width = "64")]
-    #[inline]
-    fn write_u64(&mut self, i: u64) {
-        self.add_to_hash(i as usize);
-    }
-
-    #[inline]
-    fn write_usize(&mut self, i: usize) {
-        self.add_to_hash(i);
-    }
-
-    #[inline]
-    fn finish(&self) -> u64 {
-        self.hash as u64
-    }
-}
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index cd707152af6..e2a80acbd12 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -44,6 +44,7 @@ extern crate parking_lot;
 extern crate cfg_if;
 extern crate stable_deref_trait;
 extern crate rustc_rayon as rayon;
+extern crate rustc_hash;
 
 // See librustc_cratesio_shim/Cargo.toml for a comment explaining this.
 #[allow(unused_extern_crates)]
diff --git a/src/librustc_traits/Cargo.toml b/src/librustc_traits/Cargo.toml
index dc2a21cdab2..13498391110 100644
--- a/src/librustc_traits/Cargo.toml
+++ b/src/librustc_traits/Cargo.toml
@@ -16,3 +16,4 @@ rustc = { path = "../librustc" }
 rustc_data_structures = { path = "../librustc_data_structures" }
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
+chalk-engine = { version = "0.6.0", default-features=false }
diff --git a/src/librustc_traits/chalk_context.rs b/src/librustc_traits/chalk_context.rs
new file mode 100644
index 00000000000..bf26409c3ef
--- /dev/null
+++ b/src/librustc_traits/chalk_context.rs
@@ -0,0 +1,524 @@
+// 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 chalk_engine::fallible::Fallible as ChalkEngineFallible;
+use chalk_engine::{context, hh::HhGoal, DelayedLiteral, ExClause};
+use rustc::infer::canonical::{
+    Canonical, CanonicalVarValues, Canonicalize, QueryRegionConstraint, QueryResult,
+};
+use rustc::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime};
+use rustc::traits::{DomainGoal, ExClauseFold, ExClauseLift, Goal, ProgramClause, QuantifierKind};
+use rustc::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
+use rustc::ty::subst::Kind;
+use rustc::ty::{self, TyCtxt};
+
+use std::fmt::{self, Debug};
+use std::marker::PhantomData;
+
+use syntax_pos::DUMMY_SP;
+
+#[derive(Copy, Clone, Debug)]
+crate struct ChalkArenas<'gcx> {
+    _phantom: PhantomData<&'gcx ()>,
+}
+
+#[derive(Copy, Clone)]
+crate struct ChalkContext<'cx, 'gcx: 'cx> {
+    _arenas: ChalkArenas<'gcx>,
+    _tcx: TyCtxt<'cx, 'gcx, 'gcx>,
+}
+
+#[derive(Copy, Clone)]
+crate struct ChalkInferenceContext<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
+    infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
+}
+
+#[derive(Copy, Clone, Debug)]
+crate struct UniverseMap;
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+crate struct ConstrainedSubst<'tcx> {
+    subst: CanonicalVarValues<'tcx>,
+    constraints: Vec<QueryRegionConstraint<'tcx>>,
+}
+
+BraceStructTypeFoldableImpl! {
+    impl<'tcx> TypeFoldable<'tcx> for ConstrainedSubst<'tcx> {
+        subst, constraints
+    }
+}
+
+impl context::Context for ChalkArenas<'tcx> {
+    type CanonicalExClause = Canonical<'tcx, ExClause<Self>>;
+
+    type CanonicalGoalInEnvironment = Canonical<'tcx, ty::ParamEnvAnd<'tcx, Goal<'tcx>>>;
+
+    // u-canonicalization not yet implemented
+    type UCanonicalGoalInEnvironment = Canonical<'tcx, ty::ParamEnvAnd<'tcx, Goal<'tcx>>>;
+
+    type CanonicalConstrainedSubst = Canonical<'tcx, ConstrainedSubst<'tcx>>;
+
+    // u-canonicalization not yet implemented
+    type UniverseMap = UniverseMap;
+
+    type Solution = Canonical<'tcx, QueryResult<'tcx, ()>>;
+
+    type InferenceNormalizedSubst = CanonicalVarValues<'tcx>;
+
+    type GoalInEnvironment = ty::ParamEnvAnd<'tcx, Goal<'tcx>>;
+
+    type RegionConstraint = QueryRegionConstraint<'tcx>;
+
+    type Substitution = CanonicalVarValues<'tcx>;
+
+    type Environment = ty::ParamEnv<'tcx>;
+
+    type Goal = Goal<'tcx>;
+
+    type DomainGoal = DomainGoal<'tcx>;
+
+    type BindersGoal = ty::Binder<&'tcx Goal<'tcx>>;
+
+    type Parameter = Kind<'tcx>;
+
+    type ProgramClause = ProgramClause<'tcx>;
+
+    type ProgramClauses = Vec<ProgramClause<'tcx>>;
+
+    type UnificationResult = InferOk<'tcx, ()>;
+
+    fn into_goal(domain_goal: DomainGoal<'tcx>) -> Goal<'tcx> {
+        Goal::DomainGoal(domain_goal)
+    }
+
+    fn cannot_prove() -> Goal<'tcx> {
+        Goal::CannotProve
+    }
+
+    fn goal_in_environment(
+        env: &ty::ParamEnv<'tcx>,
+        goal: Goal<'tcx>,
+    ) -> ty::ParamEnvAnd<'tcx, Goal<'tcx>> {
+        env.and(goal)
+    }
+}
+
+impl context::AggregateOps<ChalkArenas<'gcx>> for ChalkContext<'cx, 'gcx> {
+    fn make_solution(
+        &self,
+        _root_goal: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>,
+        _simplified_answers: impl context::AnswerStream<ChalkArenas<'gcx>>,
+    ) -> Option<Canonical<'gcx, QueryResult<'gcx, ()>>> {
+        unimplemented!()
+    }
+}
+
+impl context::ContextOps<ChalkArenas<'gcx>> for ChalkContext<'cx, 'gcx> {
+    /// True if this is a coinductive goal -- e.g., proving an auto trait.
+    fn is_coinductive(&self, _goal: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>) -> bool {
+        unimplemented!()
+    }
+
+    /// Create an inference table for processing a new goal and instantiate that goal
+    /// in that context, returning "all the pieces".
+    ///
+    /// More specifically: given a u-canonical goal `arg`, creates a
+    /// new inference table `T` and populates it with the universes
+    /// found in `arg`. Then, creates a substitution `S` that maps
+    /// each bound variable in `arg` to a fresh inference variable
+    /// from T. Returns:
+    ///
+    /// - the table `T`
+    /// - the substitution `S`
+    /// - the environment and goal found by substitution `S` into `arg`
+    fn instantiate_ucanonical_goal<R>(
+        &self,
+        _arg: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>,
+        _op: impl context::WithInstantiatedUCanonicalGoal<ChalkArenas<'gcx>, Output = R>,
+    ) -> R {
+        unimplemented!()
+    }
+
+    fn instantiate_ex_clause<R>(
+        &self,
+        _num_universes: usize,
+        _canonical_ex_clause: &Canonical<'gcx, ChalkExClause<'gcx>>,
+        _op: impl context::WithInstantiatedExClause<ChalkArenas<'gcx>, Output = R>,
+    ) -> R {
+        unimplemented!()
+    }
+
+    /// True if this solution has no region constraints.
+    fn empty_constraints(ccs: &Canonical<'gcx, ConstrainedSubst<'gcx>>) -> bool {
+        ccs.value.constraints.is_empty()
+    }
+
+    fn inference_normalized_subst_from_ex_clause(
+        canon_ex_clause: &'a Canonical<'gcx, ChalkExClause<'gcx>>,
+    ) -> &'a CanonicalVarValues<'gcx> {
+        &canon_ex_clause.value.subst
+    }
+
+    fn inference_normalized_subst_from_subst(
+        canon_subst: &'a Canonical<'gcx, ConstrainedSubst<'gcx>>,
+    ) -> &'a CanonicalVarValues<'gcx> {
+        &canon_subst.value.subst
+    }
+
+    fn canonical(
+        u_canon: &'a Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>,
+    ) -> &'a Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>> {
+        u_canon
+    }
+
+    fn is_trivial_substitution(
+        _u_canon: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>,
+        _canonical_subst: &Canonical<'gcx, ConstrainedSubst<'gcx>>,
+    ) -> bool {
+        unimplemented!()
+    }
+
+    fn num_universes(_: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>) -> usize {
+        0 // FIXME
+    }
+
+    /// Convert a goal G *from* the canonical universes *into* our
+    /// local universes. This will yield a goal G' that is the same
+    /// but for the universes of universally quantified names.
+    fn map_goal_from_canonical(
+        _map: &UniverseMap,
+        value: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>,
+    ) -> Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>> {
+        *value // FIXME universe maps not implemented yet
+    }
+
+    fn map_subst_from_canonical(
+        _map: &UniverseMap,
+        value: &Canonical<'gcx, ConstrainedSubst<'gcx>>,
+    ) -> Canonical<'gcx, ConstrainedSubst<'gcx>> {
+        value.clone() // FIXME universe maps not implemented yet
+    }
+}
+
+//impl context::UCanonicalGoalInEnvironment<ChalkContext<'cx, 'gcx>>
+//    for Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>
+//{
+//    fn canonical(&self) -> &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>> {
+//        self
+//    }
+//
+//    fn is_trivial_substitution(
+//        &self,
+//        canonical_subst: &Canonical<'tcx, ConstrainedSubst<'tcx>>,
+//    ) -> bool {
+//        let subst = &canonical_subst.value.subst;
+//        assert_eq!(self.canonical.variables.len(), subst.var_values.len());
+//        subst
+//            .var_values
+//            .iter_enumerated()
+//            .all(|(cvar, kind)| match kind.unpack() {
+//                Kind::Lifetime(r) => match r {
+//                    ty::ReCanonical(cvar1) => cvar == cvar1,
+//                    _ => false,
+//                },
+//                Kind::Type(ty) => match ty.sty {
+//                    ty::TyInfer(ty::InferTy::CanonicalTy(cvar1)) => cvar == cvar1,
+//                    _ => false,
+//                },
+//            })
+//    }
+//
+//    fn num_universes(&self) -> usize {
+//        0 // FIXME
+//    }
+//}
+
+impl context::InferenceTable<ChalkArenas<'gcx>, ChalkArenas<'tcx>>
+    for ChalkInferenceContext<'cx, 'gcx, 'tcx>
+{
+    fn into_hh_goal(&mut self, goal: Goal<'tcx>) -> ChalkHhGoal<'tcx> {
+        match goal {
+            Goal::Implies(..) => panic!("FIXME rust-lang-nursery/chalk#94"),
+            Goal::And(left, right) => HhGoal::And(*left, *right),
+            Goal::Not(subgoal) => HhGoal::Not(*subgoal),
+            Goal::DomainGoal(d) => HhGoal::DomainGoal(d),
+            Goal::Quantified(QuantifierKind::Universal, binder) => HhGoal::ForAll(binder),
+            Goal::Quantified(QuantifierKind::Existential, binder) => HhGoal::Exists(binder),
+            Goal::CannotProve => HhGoal::CannotProve,
+        }
+    }
+
+    fn add_clauses(
+        &mut self,
+        _env: &ty::ParamEnv<'tcx>,
+        _clauses: Vec<ProgramClause<'tcx>>,
+    ) -> ty::ParamEnv<'tcx> {
+        panic!("FIXME no method to add clauses to ParamEnv yet")
+    }
+}
+
+impl context::ResolventOps<ChalkArenas<'gcx>, ChalkArenas<'tcx>>
+    for ChalkInferenceContext<'cx, 'gcx, 'tcx>
+{
+    fn resolvent_clause(
+        &mut self,
+        _environment: &ty::ParamEnv<'tcx>,
+        _goal: &DomainGoal<'tcx>,
+        _subst: &CanonicalVarValues<'tcx>,
+        _clause: &ProgramClause<'tcx>,
+    ) -> chalk_engine::fallible::Fallible<Canonical<'gcx, ChalkExClause<'gcx>>> {
+        panic!()
+    }
+
+    fn apply_answer_subst(
+        &mut self,
+        _ex_clause: ChalkExClause<'tcx>,
+        _selected_goal: &ty::ParamEnvAnd<'tcx, Goal<'tcx>>,
+        _answer_table_goal: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>,
+        _canonical_answer_subst: &Canonical<'gcx, ConstrainedSubst<'gcx>>,
+    ) -> chalk_engine::fallible::Fallible<ChalkExClause<'tcx>> {
+        panic!()
+    }
+}
+
+impl context::TruncateOps<ChalkArenas<'gcx>, ChalkArenas<'tcx>>
+    for ChalkInferenceContext<'cx, 'gcx, 'tcx>
+{
+    fn truncate_goal(
+        &mut self,
+        subgoal: &ty::ParamEnvAnd<'tcx, Goal<'tcx>>,
+    ) -> Option<ty::ParamEnvAnd<'tcx, Goal<'tcx>>> {
+        Some(*subgoal) // FIXME we should truncate at some point!
+    }
+
+    fn truncate_answer(
+        &mut self,
+        subst: &CanonicalVarValues<'tcx>,
+    ) -> Option<CanonicalVarValues<'tcx>> {
+        Some(subst.clone()) // FIXME we should truncate at some point!
+    }
+}
+
+impl context::UnificationOps<ChalkArenas<'gcx>, ChalkArenas<'tcx>>
+    for ChalkInferenceContext<'cx, 'gcx, 'tcx>
+{
+    fn program_clauses(
+        &self,
+        _environment: &ty::ParamEnv<'tcx>,
+        goal: &DomainGoal<'tcx>,
+    ) -> Vec<ProgramClause<'tcx>> {
+        use rustc::traits::DomainGoal::*;
+        use rustc::traits::WhereClauseAtom::*;
+
+        match goal {
+            Holds(Implemented(_trait_predicate)) => {
+                // These come from:
+                //
+                // - Trait definitions (implied bounds)
+                // - Implementations of the trait itself
+                panic!()
+            }
+
+            Holds(ProjectionEq(_projection_predicate)) => {
+                // These come from:
+                panic!()
+            }
+
+            WellFormed(Implemented(_trait_predicate)) => {
+                // These come from -- the trait decl.
+                panic!()
+            }
+
+            WellFormed(ProjectionEq(_projection_predicate)) => panic!(),
+
+            FromEnv(Implemented(_trait_predicate)) => panic!(),
+
+            FromEnv(ProjectionEq(_projection_predicate)) => panic!(),
+
+            WellFormedTy(_ty) => panic!(),
+
+            FromEnvTy(_ty) => panic!(),
+
+            RegionOutlives(_region_outlives) => panic!(),
+
+            TypeOutlives(_type_outlives) => panic!(),
+
+            Normalize(_) => panic!(),
+        }
+    }
+
+    fn instantiate_binders_universally(
+        &mut self,
+        _arg: &ty::Binder<&'tcx Goal<'tcx>>,
+    ) -> Goal<'tcx> {
+        panic!("FIXME -- universal instantiation needs sgrif's branch")
+    }
+
+    fn instantiate_binders_existentially(
+        &mut self,
+        arg: &ty::Binder<&'tcx Goal<'tcx>>,
+    ) -> Goal<'tcx> {
+        let (value, _map) = self.infcx.replace_late_bound_regions_with_fresh_var(
+            DUMMY_SP,
+            LateBoundRegionConversionTime::HigherRankedType,
+            arg,
+        );
+        *value
+    }
+
+    fn debug_ex_clause(&mut self, value: &'v ChalkExClause<'tcx>) -> Box<dyn Debug + 'v> {
+        let string = format!("{:?}", self.infcx.resolve_type_vars_if_possible(value));
+        Box::new(string)
+    }
+
+    fn canonicalize_goal(
+        &mut self,
+        value: &ty::ParamEnvAnd<'tcx, Goal<'tcx>>,
+    ) -> Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>> {
+        self.infcx.canonicalize_query(value).0
+    }
+
+    fn canonicalize_ex_clause(
+        &mut self,
+        value: &ChalkExClause<'tcx>,
+    ) -> Canonical<'gcx, ChalkExClause<'gcx>> {
+        self.infcx.canonicalize_response(value).0
+    }
+
+    fn canonicalize_constrained_subst(
+        &mut self,
+        subst: CanonicalVarValues<'tcx>,
+        constraints: Vec<QueryRegionConstraint<'tcx>>,
+    ) -> Canonical<'gcx, ConstrainedSubst<'gcx>> {
+        self.infcx
+            .canonicalize_response(&ConstrainedSubst { subst, constraints })
+            .0
+    }
+
+    fn u_canonicalize_goal(
+        &mut self,
+        value: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>,
+    ) -> (
+        Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>,
+        UniverseMap,
+    ) {
+        (value.clone(), UniverseMap)
+    }
+
+    fn invert_goal(
+        &mut self,
+        _value: &ty::ParamEnvAnd<'tcx, Goal<'tcx>>,
+    ) -> Option<ty::ParamEnvAnd<'tcx, Goal<'tcx>>> {
+        panic!("goal inversion not yet implemented")
+    }
+
+    fn unify_parameters(
+        &mut self,
+        _environment: &ty::ParamEnv<'tcx>,
+        _a: &Kind<'tcx>,
+        _b: &Kind<'tcx>,
+    ) -> ChalkEngineFallible<InferOk<'tcx, ()>> {
+        panic!()
+    }
+
+    fn sink_answer_subset(
+        &self,
+        value: &Canonical<'gcx, ConstrainedSubst<'gcx>>,
+    ) -> Canonical<'tcx, ConstrainedSubst<'tcx>> {
+        value.clone()
+    }
+
+    fn lift_delayed_literal(
+        &self,
+        _value: DelayedLiteral<ChalkArenas<'tcx>>,
+    ) -> DelayedLiteral<ChalkArenas<'gcx>> {
+        panic!("lift")
+    }
+
+    fn into_ex_clause(&mut self, _result: InferOk<'tcx, ()>, _ex_clause: &mut ChalkExClause<'tcx>) {
+        panic!("TBD")
+    }
+}
+
+type ChalkHhGoal<'tcx> = HhGoal<ChalkArenas<'tcx>>;
+
+type ChalkExClause<'tcx> = ExClause<ChalkArenas<'tcx>>;
+
+impl Debug for ChalkContext<'cx, 'gcx> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "ChalkContext")
+    }
+}
+
+impl Debug for ChalkInferenceContext<'cx, 'gcx, 'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "ChalkInferenceContext")
+    }
+}
+
+impl ExClauseLift<'gcx> for ChalkArenas<'a> {
+    type LiftedExClause = ChalkExClause<'gcx>;
+
+    fn lift_ex_clause_to_tcx(
+        _ex_clause: &ChalkExClause<'a>,
+        _tcx: TyCtxt<'_, '_, 'tcx>,
+    ) -> Option<Self::LiftedExClause> {
+        panic!()
+    }
+}
+
+impl ExClauseFold<'tcx> for ChalkArenas<'tcx> {
+    fn fold_ex_clause_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(
+        ex_clause: &ChalkExClause<'tcx>,
+        folder: &mut F,
+    ) -> ChalkExClause<'tcx> {
+        ExClause {
+            subst: ex_clause.subst.fold_with(folder),
+            delayed_literals: ex_clause.delayed_literals.fold_with(folder),
+            constraints: ex_clause.constraints.fold_with(folder),
+            subgoals: ex_clause.subgoals.fold_with(folder),
+        }
+    }
+
+    fn visit_ex_clause_with<'gcx: 'tcx, V: TypeVisitor<'tcx>>(
+        ex_clause: &ExClause<Self>,
+        visitor: &mut V,
+    ) -> bool {
+        let ExClause {
+            subst,
+            delayed_literals,
+            constraints,
+            subgoals,
+        } = ex_clause;
+        subst.visit_with(visitor)
+            && delayed_literals.visit_with(visitor)
+            && constraints.visit_with(visitor)
+            && subgoals.visit_with(visitor)
+    }
+}
+
+BraceStructLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for ConstrainedSubst<'a> {
+        type Lifted = ConstrainedSubst<'tcx>;
+
+        subst, constraints
+    }
+}
+
+impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ConstrainedSubst<'tcx> {
+    type Canonicalized = Canonical<'gcx, ConstrainedSubst<'gcx>>;
+
+    fn intern(
+        _gcx: TyCtxt<'_, 'gcx, 'gcx>,
+        value: Canonical<'gcx, ConstrainedSubst<'gcx>>,
+    ) -> Self::Canonicalized {
+        value
+    }
+}
diff --git a/src/librustc_traits/lib.rs b/src/librustc_traits/lib.rs
index f2627f65702..733d8e1708e 100644
--- a/src/librustc_traits/lib.rs
+++ b/src/librustc_traits/lib.rs
@@ -11,9 +11,13 @@
 //! New recursive solver modeled on Chalk's recursive solver. Most of
 //! the guts are broken up into modules; see the comments in those modules.
 
+#![feature(crate_in_paths)]
 #![feature(crate_visibility_modifier)]
+#![feature(extern_prelude)]
 #![feature(iterator_find_map)]
+#![feature(in_band_lifetimes)]
 
+extern crate chalk_engine;
 #[macro_use]
 extern crate log;
 #[macro_use]
@@ -22,6 +26,7 @@ extern crate rustc_data_structures;
 extern crate syntax;
 extern crate syntax_pos;
 
+mod chalk_context;
 mod dropck_outlives;
 mod evaluate_obligation;
 mod normalize_projection_ty;
diff --git a/src/librustc_traits/lowering.rs b/src/librustc_traits/lowering.rs
index 6e4c4a3ade3..32f18a62abe 100644
--- a/src/librustc_traits/lowering.rs
+++ b/src/librustc_traits/lowering.rs
@@ -22,7 +22,7 @@ use syntax::ast;
 
 use std::iter;
 
-trait Lower<T> {
+crate trait Lower<T> {
     /// Lower a rustc construction (e.g. `ty::TraitPredicate`) to a chalk-like type.
     fn lower(&self) -> T;
 }
diff --git a/src/tools/tidy/src/deps.rs b/src/tools/tidy/src/deps.rs
index 5739ec5f325..bcd6f4e67f4 100644
--- a/src/tools/tidy/src/deps.rs
+++ b/src/tools/tidy/src/deps.rs
@@ -66,6 +66,8 @@ static WHITELIST: &'static [Crate] = &[
     Crate("bitflags"),
     Crate("byteorder"),
     Crate("cc"),
+    Crate("chalk-engine"),
+    Crate("chalk-macros"),
     Crate("cfg-if"),
     Crate("cmake"),
     Crate("crossbeam-deque"),
@@ -102,6 +104,7 @@ static WHITELIST: &'static [Crate] = &[
     Crate("regex-syntax"),
     Crate("remove_dir_all"),
     Crate("rustc-demangle"),
+    Crate("rustc-hash"),
     Crate("rustc-rayon"),
     Crate("rustc-rayon-core"),
     Crate("scoped-tls"),