Uplift GenericArgKind, CanonicalVarValues, QueryInput

and make NestedGoals generic

25 files changed, 377 insertions, 268 deletions

diff --git a/Cargo.lock b/Cargo.lock
index df4e4f32613..536f49989fa 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -4343,6 +4343,7 @@ dependencies = [
  "rustc_hir_pretty",
  "rustc_index",
  "rustc_macros",
+ "rustc_next_trait_solver",
  "rustc_query_system",
  "rustc_serialize",
  "rustc_session",
@@ -4451,7 +4452,13 @@ dependencies = [
 name = "rustc_next_trait_solver"
 version = "0.0.0"
 dependencies = [
+ "derivative",
+ "rustc_ast_ir",
+ "rustc_data_structures",
+ "rustc_macros",
+ "rustc_serialize",
  "rustc_type_ir",
+ "rustc_type_ir_macros",
 ]
 
 [[package]]
diff --git a/compiler/rustc_infer/src/infer/at.rs b/compiler/rustc_infer/src/infer/at.rs
index eaef715fe5d..16057b6ad9d 100644
--- a/compiler/rustc_infer/src/infer/at.rs
+++ b/compiler/rustc_infer/src/infer/at.rs
@@ -385,19 +385,31 @@ impl<'tcx> ToTrace<'tcx> for ty::GenericArg<'tcx> {
         a: Self,
         b: Self,
     ) -> TypeTrace<'tcx> {
-        use GenericArgKind::*;
         TypeTrace {
             cause: cause.clone(),
             values: match (a.unpack(), b.unpack()) {
-                (Lifetime(a), Lifetime(b)) => Regions(ExpectedFound::new(a_is_expected, a, b)),
-                (Type(a), Type(b)) => Terms(ExpectedFound::new(a_is_expected, a.into(), b.into())),
-                (Const(a), Const(b)) => {
+                (GenericArgKind::Lifetime(a), GenericArgKind::Lifetime(b)) => {
+                    Regions(ExpectedFound::new(a_is_expected, a, b))
+                }
+                (GenericArgKind::Type(a), GenericArgKind::Type(b)) => {
+                    Terms(ExpectedFound::new(a_is_expected, a.into(), b.into()))
+                }
+                (GenericArgKind::Const(a), GenericArgKind::Const(b)) => {
                     Terms(ExpectedFound::new(a_is_expected, a.into(), b.into()))
                 }
 
-                (Lifetime(_), Type(_) | Const(_))
-                | (Type(_), Lifetime(_) | Const(_))
-                | (Const(_), Lifetime(_) | Type(_)) => {
+                (
+                    GenericArgKind::Lifetime(_),
+                    GenericArgKind::Type(_) | GenericArgKind::Const(_),
+                )
+                | (
+                    GenericArgKind::Type(_),
+                    GenericArgKind::Lifetime(_) | GenericArgKind::Const(_),
+                )
+                | (
+                    GenericArgKind::Const(_),
+                    GenericArgKind::Lifetime(_) | GenericArgKind::Type(_),
+                ) => {
                     bug!("relating different kinds: {a:?} {b:?}")
                 }
             },
diff --git a/compiler/rustc_infer/src/traits/mod.rs b/compiler/rustc_infer/src/traits/mod.rs
index d5def46ad3a..0ae4340098b 100644
--- a/compiler/rustc_infer/src/traits/mod.rs
+++ b/compiler/rustc_infer/src/traits/mod.rs
@@ -78,9 +78,9 @@ impl<T: Hash> Hash for Obligation<'_, T> {
     }
 }
 
-impl<'tcx, P> From<Obligation<'tcx, P>> for ty::Goal<'tcx, P> {
+impl<'tcx, P> From<Obligation<'tcx, P>> for solve::Goal<'tcx, P> {
     fn from(value: Obligation<'tcx, P>) -> Self {
-        ty::Goal { param_env: value.param_env, predicate: value.predicate }
+        solve::Goal { param_env: value.param_env, predicate: value.predicate }
     }
 }
 
diff --git a/compiler/rustc_middle/Cargo.toml b/compiler/rustc_middle/Cargo.toml
index d1cdabc293d..ab0c598ea0c 100644
--- a/compiler/rustc_middle/Cargo.toml
+++ b/compiler/rustc_middle/Cargo.toml
@@ -28,6 +28,7 @@ rustc_hir = { path = "../rustc_hir" }
 rustc_hir_pretty = { path = "../rustc_hir_pretty" }
 rustc_index = { path = "../rustc_index" }
 rustc_macros = { path = "../rustc_macros" }
+rustc_next_trait_solver = { path = "../rustc_next_trait_solver" }
 rustc_query_system = { path = "../rustc_query_system" }
 rustc_serialize = { path = "../rustc_serialize" }
 rustc_session = { path = "../rustc_session" }
diff --git a/compiler/rustc_middle/src/infer/canonical.rs b/compiler/rustc_middle/src/infer/canonical.rs
index aee97d77222..49bf03e9c75 100644
--- a/compiler/rustc_middle/src/infer/canonical.rs
+++ b/compiler/rustc_middle/src/infer/canonical.rs
@@ -23,23 +23,20 @@
 
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::sync::Lock;
-use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
-use rustc_type_ir::Canonical as IrCanonical;
-use rustc_type_ir::CanonicalVarInfo as IrCanonicalVarInfo;
+use rustc_macros::{HashStable, TypeFoldable, TypeVisitable};
+pub use rustc_type_ir as ir;
 pub use rustc_type_ir::{CanonicalTyVarKind, CanonicalVarKind};
 use smallvec::SmallVec;
 use std::collections::hash_map::Entry;
-use std::ops::Index;
 
 use crate::infer::MemberConstraint;
 use crate::mir::ConstraintCategory;
 use crate::ty::GenericArg;
-use crate::ty::{self, BoundVar, List, Region, Ty, TyCtxt, TypeFlags, TypeVisitableExt};
-
-pub type Canonical<'tcx, V> = IrCanonical<TyCtxt<'tcx>, V>;
-
-pub type CanonicalVarInfo<'tcx> = IrCanonicalVarInfo<TyCtxt<'tcx>>;
+use crate::ty::{self, List, Region, Ty, TyCtxt, TypeFlags, TypeVisitableExt};
 
+pub type Canonical<'tcx, V> = ir::Canonical<TyCtxt<'tcx>, V>;
+pub type CanonicalVarInfo<'tcx> = ir::CanonicalVarInfo<TyCtxt<'tcx>>;
+pub type CanonicalVarValues<'tcx> = ir::CanonicalVarValues<TyCtxt<'tcx>>;
 pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo<'tcx>>;
 
 impl<'tcx> ty::TypeFoldable<TyCtxt<'tcx>> for CanonicalVarInfos<'tcx> {
@@ -51,74 +48,6 @@ impl<'tcx> ty::TypeFoldable<TyCtxt<'tcx>> for CanonicalVarInfos<'tcx> {
     }
 }
 
-/// A set of values corresponding to the canonical variables from some
-/// `Canonical`. You can give these values to
-/// `canonical_value.instantiate` to instantiate them into the canonical
-/// value at the right places.
-///
-/// When you canonicalize a value `V`, you get back one of these
-/// vectors with the original values that were replaced by canonical
-/// variables. You will need to supply it later to instantiate the
-/// canonicalized query response.
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)]
-#[derive(HashStable, TypeFoldable, TypeVisitable)]
-pub struct CanonicalVarValues<'tcx> {
-    pub var_values: ty::GenericArgsRef<'tcx>,
-}
-
-impl CanonicalVarValues<'_> {
-    pub fn is_identity(&self) -> bool {
-        self.var_values.iter().enumerate().all(|(bv, arg)| match arg.unpack() {
-            ty::GenericArgKind::Lifetime(r) => {
-                matches!(*r, ty::ReBound(ty::INNERMOST, br) if br.var.as_usize() == bv)
-            }
-            ty::GenericArgKind::Type(ty) => {
-                matches!(*ty.kind(), ty::Bound(ty::INNERMOST, bt) if bt.var.as_usize() == bv)
-            }
-            ty::GenericArgKind::Const(ct) => {
-                matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if bc.as_usize() == bv)
-            }
-        })
-    }
-
-    pub fn is_identity_modulo_regions(&self) -> bool {
-        let mut var = ty::BoundVar::ZERO;
-        for arg in self.var_values {
-            match arg.unpack() {
-                ty::GenericArgKind::Lifetime(r) => {
-                    if let ty::ReBound(ty::INNERMOST, br) = *r
-                        && var == br.var
-                    {
-                        var = var + 1;
-                    } else {
-                        // It's ok if this region var isn't unique
-                    }
-                }
-                ty::GenericArgKind::Type(ty) => {
-                    if let ty::Bound(ty::INNERMOST, bt) = *ty.kind()
-                        && var == bt.var
-                    {
-                        var = var + 1;
-                    } else {
-                        return false;
-                    }
-                }
-                ty::GenericArgKind::Const(ct) => {
-                    if let ty::ConstKind::Bound(ty::INNERMOST, bc) = ct.kind()
-                        && var == bc
-                    {
-                        var = var + 1;
-                    } else {
-                        return false;
-                    }
-                }
-            }
-        }
-
-        true
-    }
-}
-
 /// When we canonicalize a value to form a query, we wind up replacing
 /// various parts of it with canonical variables. This struct stores
 /// those replaced bits to remember for when we process the query
@@ -218,78 +147,6 @@ TrivialTypeTraversalImpls! {
     crate::infer::canonical::Certainty,
 }
 
-impl<'tcx> CanonicalVarValues<'tcx> {
-    // Given a list of canonical variables, construct a set of values which are
-    // the identity response.
-    pub fn make_identity(
-        tcx: TyCtxt<'tcx>,
-        infos: CanonicalVarInfos<'tcx>,
-    ) -> CanonicalVarValues<'tcx> {
-        CanonicalVarValues {
-            var_values: tcx.mk_args_from_iter(infos.iter().enumerate().map(
-                |(i, info)| -> ty::GenericArg<'tcx> {
-                    match info.kind {
-                        CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => {
-                            Ty::new_bound(tcx, ty::INNERMOST, ty::BoundVar::from_usize(i).into())
-                                .into()
-                        }
-                        CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => {
-                            let br = ty::BoundRegion {
-                                var: ty::BoundVar::from_usize(i),
-                                kind: ty::BrAnon,
-                            };
-                            ty::Region::new_bound(tcx, ty::INNERMOST, br).into()
-                        }
-                        CanonicalVarKind::Effect => ty::Const::new_bound(
-                            tcx,
-                            ty::INNERMOST,
-                            ty::BoundVar::from_usize(i),
-                            tcx.types.bool,
-                        )
-                        .into(),
-                        CanonicalVarKind::Const(_, ty)
-                        | CanonicalVarKind::PlaceholderConst(_, ty) => ty::Const::new_bound(
-                            tcx,
-                            ty::INNERMOST,
-                            ty::BoundVar::from_usize(i),
-                            ty,
-                        )
-                        .into(),
-                    }
-                },
-            )),
-        }
-    }
-
-    /// Creates dummy var values which should not be used in a
-    /// canonical response.
-    pub fn dummy() -> CanonicalVarValues<'tcx> {
-        CanonicalVarValues { var_values: ty::List::empty() }
-    }
-
-    #[inline]
-    pub fn len(&self) -> usize {
-        self.var_values.len()
-    }
-}
-
-impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
-    type Item = GenericArg<'tcx>;
-    type IntoIter = ::std::iter::Copied<::std::slice::Iter<'a, GenericArg<'tcx>>>;
-
-    fn into_iter(self) -> Self::IntoIter {
-        self.var_values.iter()
-    }
-}
-
-impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
-    type Output = GenericArg<'tcx>;
-
-    fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
-        &self.var_values[value.as_usize()]
-    }
-}
-
 #[derive(Default)]
 pub struct CanonicalParamEnvCache<'tcx> {
     map: Lock<
diff --git a/compiler/rustc_middle/src/traits/solve.rs b/compiler/rustc_middle/src/traits/solve.rs
index ef140860bab..efb99047d38 100644
--- a/compiler/rustc_middle/src/traits/solve.rs
+++ b/compiler/rustc_middle/src/traits/solve.rs
@@ -1,6 +1,8 @@
 use rustc_ast_ir::try_visit;
 use rustc_data_structures::intern::Interned;
 use rustc_macros::{HashStable, TypeFoldable, TypeVisitable};
+use rustc_next_trait_solver as ir;
+pub use rustc_next_trait_solver::solve::*;
 use rustc_span::def_id::DefId;
 
 use crate::infer::canonical::{CanonicalVarValues, QueryRegionConstraints};
@@ -9,8 +11,6 @@ use crate::traits::Canonical;
 use crate::ty::{
     self, FallibleTypeFolder, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable, TypeVisitor,
 };
-// FIXME(compiler-errors): remove this import in favor of `use rustc_middle::ty::Goal`.
-pub use crate::ty::Goal;
 
 use super::BuiltinImplSource;
 
@@ -19,6 +19,9 @@ pub mod inspect;
 
 pub use cache::{CacheData, EvaluationCache};
 
+pub type Goal<'tcx, P> = ir_solve::Goal<TyCtxt<'tcx>, P>;
+pub type QueryInput<'tcx, P> = ir_solve::QueryInput<TyCtxt<'tcx>, P>;
+
 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, HashStable, TypeFoldable, TypeVisitable)]
 pub struct Response<'tcx> {
     pub certainty: Certainty,
@@ -87,12 +90,6 @@ impl MaybeCause {
     }
 }
 
-#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, HashStable, TypeFoldable, TypeVisitable)]
-pub struct QueryInput<'tcx, T> {
-    pub goal: Goal<'tcx, T>,
-    pub predefined_opaques_in_body: PredefinedOpaques<'tcx>,
-}
-
 /// Additional constraints returned on success.
 #[derive(Debug, PartialEq, Eq, Clone, Hash, HashStable, Default)]
 pub struct PredefinedOpaquesData<'tcx> {
@@ -229,29 +226,6 @@ impl<'tcx> TypeVisitable<TyCtxt<'tcx>> for PredefinedOpaques<'tcx> {
     }
 }
 
-/// Why a specific goal has to be proven.
-///
-/// This is necessary as we treat nested goals different depending on
-/// their source.
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable, TypeVisitable, TypeFoldable)]
-pub enum GoalSource {
-    Misc,
-    /// We're proving a where-bound of an impl.
-    ///
-    /// FIXME(-Znext-solver=coinductive): Explain how and why this
-    /// changes whether cycles are coinductive.
-    ///
-    /// This also impacts whether we erase constraints on overflow.
-    /// Erasing constraints is generally very useful for perf and also
-    /// results in better error messages by avoiding spurious errors.
-    /// We do not erase overflow constraints in `normalizes-to` goals unless
-    /// they are from an impl where-clause. This is necessary due to
-    /// backwards compatability, cc trait-system-refactor-initiatitive#70.
-    ImplWhereBound,
-    /// Instantiating a higher-ranked goal and re-proving it.
-    InstantiateHigherRanked,
-}
-
 /// Possible ways the given goal can be proven.
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
 pub enum CandidateSource {
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index 06299cdf86f..1d3bc8b4bbe 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -90,6 +90,7 @@ use std::ops::{Bound, Deref};
 impl<'tcx> Interner for TyCtxt<'tcx> {
     type DefId = DefId;
     type DefiningOpaqueTypes = &'tcx ty::List<LocalDefId>;
+    type PredefinedOpaques = solve::PredefinedOpaques<'tcx>;
     type AdtDef = ty::AdtDef<'tcx>;
     type GenericArgs = ty::GenericArgsRef<'tcx>;
     type OwnItemArgs = &'tcx [ty::GenericArg<'tcx>];
diff --git a/compiler/rustc_middle/src/ty/generic_args.rs b/compiler/rustc_middle/src/ty/generic_args.rs
index 904c0c332a8..38b2987399a 100644
--- a/compiler/rustc_middle/src/ty/generic_args.rs
+++ b/compiler/rustc_middle/src/ty/generic_args.rs
@@ -11,6 +11,7 @@ use rustc_ast_ir::walk_visitable_list;
 use rustc_data_structures::intern::Interned;
 use rustc_errors::{DiagArgValue, IntoDiagArg};
 use rustc_hir::def_id::DefId;
+use rustc_macros::extension;
 use rustc_macros::{
     Decodable, Encodable, HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable,
 };
@@ -25,6 +26,8 @@ use std::num::NonZero;
 use std::ops::Deref;
 use std::ptr::NonNull;
 
+pub type GenericArgKind<'tcx> = rustc_type_ir::GenericArgKind<TyCtxt<'tcx>>;
+
 /// An entity in the Rust type system, which can be one of
 /// several kinds (types, lifetimes, and consts).
 /// To reduce memory usage, a `GenericArg` is an interned pointer,
@@ -49,6 +52,14 @@ impl<'tcx> rustc_type_ir::inherent::GenericArgs<TyCtxt<'tcx>> for ty::GenericArg
     }
 }
 
+impl<'tcx> rustc_type_ir::inherent::IntoKind for GenericArg<'tcx> {
+    type Kind = GenericArgKind<'tcx>;
+
+    fn kind(self) -> Self::Kind {
+        self.unpack()
+    }
+}
+
 #[cfg(parallel_compiler)]
 unsafe impl<'tcx> rustc_data_structures::sync::DynSend for GenericArg<'tcx> where
     &'tcx (Ty<'tcx>, ty::Region<'tcx>, ty::Const<'tcx>): rustc_data_structures::sync::DynSend
@@ -79,13 +90,7 @@ const TYPE_TAG: usize = 0b00;
 const REGION_TAG: usize = 0b01;
 const CONST_TAG: usize = 0b10;
 
-#[derive(Debug, TyEncodable, TyDecodable, PartialEq, Eq, HashStable)]
-pub enum GenericArgKind<'tcx> {
-    Lifetime(ty::Region<'tcx>),
-    Type(Ty<'tcx>),
-    Const(ty::Const<'tcx>),
-}
-
+#[extension(trait GenericArgPackExt<'tcx>)]
 impl<'tcx> GenericArgKind<'tcx> {
     #[inline]
     fn pack(self) -> GenericArg<'tcx> {
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index 8ba083ec306..f07f12f8bf1 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -28,7 +28,7 @@ use crate::ty::fast_reject::SimplifiedType;
 use crate::ty::util::Discr;
 pub use adt::*;
 pub use assoc::*;
-pub use generic_args::*;
+pub use generic_args::{GenericArgKind, *};
 pub use generics::*;
 pub use intrinsic::IntrinsicDef;
 use rustc_ast as ast;
@@ -97,13 +97,12 @@ pub use self::parameterized::ParameterizedOverTcx;
 pub use self::pattern::{Pattern, PatternKind};
 pub use self::predicate::{
     AliasTerm, Clause, ClauseKind, CoercePredicate, ExistentialPredicate,
-    ExistentialPredicateStableCmpExt, ExistentialProjection, ExistentialTraitRef, Goal,
-    NormalizesTo, OutlivesPredicate, PolyCoercePredicate, PolyExistentialPredicate,
-    PolyExistentialProjection, PolyExistentialTraitRef, PolyProjectionPredicate,
-    PolyRegionOutlivesPredicate, PolySubtypePredicate, PolyTraitPredicate, PolyTraitRef,
-    PolyTypeOutlivesPredicate, Predicate, PredicateKind, ProjectionPredicate,
-    RegionOutlivesPredicate, SubtypePredicate, ToPolyTraitRef, TraitPredicate, TraitRef,
-    TypeOutlivesPredicate,
+    ExistentialPredicateStableCmpExt, ExistentialProjection, ExistentialTraitRef, NormalizesTo,
+    OutlivesPredicate, PolyCoercePredicate, PolyExistentialPredicate, PolyExistentialProjection,
+    PolyExistentialTraitRef, PolyProjectionPredicate, PolyRegionOutlivesPredicate,
+    PolySubtypePredicate, PolyTraitPredicate, PolyTraitRef, PolyTypeOutlivesPredicate, Predicate,
+    PredicateKind, ProjectionPredicate, RegionOutlivesPredicate, SubtypePredicate, ToPolyTraitRef,
+    TraitPredicate, TraitRef, TypeOutlivesPredicate,
 };
 pub use self::region::{
     BoundRegion, BoundRegionKind, BoundRegionKind::*, EarlyParamRegion, LateParamRegion, Region,
diff --git a/compiler/rustc_middle/src/ty/predicate.rs b/compiler/rustc_middle/src/ty/predicate.rs
index e490e060345..644fca7c5fe 100644
--- a/compiler/rustc_middle/src/ty/predicate.rs
+++ b/compiler/rustc_middle/src/ty/predicate.rs
@@ -12,7 +12,6 @@ use crate::ty::{
     Upcast, UpcastFrom, WithCachedTypeInfo,
 };
 
-pub type Goal<'tcx, P> = ir::Goal<TyCtxt<'tcx>, P>;
 pub type TraitRef<'tcx> = ir::TraitRef<TyCtxt<'tcx>>;
 pub type AliasTerm<'tcx> = ir::AliasTerm<TyCtxt<'tcx>>;
 pub type ProjectionPredicate<'tcx> = ir::ProjectionPredicate<TyCtxt<'tcx>>;
diff --git a/compiler/rustc_middle/src/ty/region.rs b/compiler/rustc_middle/src/ty/region.rs
index 8842ecd12e9..7540f0ab83f 100644
--- a/compiler/rustc_middle/src/ty/region.rs
+++ b/compiler/rustc_middle/src/ty/region.rs
@@ -396,6 +396,12 @@ pub struct BoundRegion {
     pub kind: BoundRegionKind,
 }
 
+impl<'tcx> rustc_type_ir::inherent::BoundVarLike<TyCtxt<'tcx>> for BoundRegion {
+    fn var(self) -> BoundVar {
+        self.var
+    }
+}
+
 impl core::fmt::Debug for BoundRegion {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self.kind {
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index 9dbcd938e6e..21520fa5c25 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -1204,6 +1204,12 @@ pub struct BoundTy {
     pub kind: BoundTyKind,
 }
 
+impl<'tcx> rustc_type_ir::inherent::BoundVarLike<TyCtxt<'tcx>> for BoundTy {
+    fn var(self) -> BoundVar {
+        self.var
+    }
+}
+
 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
 #[derive(HashStable)]
 pub enum BoundTyKind {
@@ -1606,6 +1612,10 @@ impl<'tcx> Ty<'tcx> {
 }
 
 impl<'tcx> rustc_type_ir::inherent::Ty<TyCtxt<'tcx>> for Ty<'tcx> {
+    fn new_bool(tcx: TyCtxt<'tcx>) -> Self {
+        tcx.types.bool
+    }
+
     fn new_anon_bound(tcx: TyCtxt<'tcx>, debruijn: ty::DebruijnIndex, var: ty::BoundVar) -> Self {
         Ty::new_bound(tcx, debruijn, ty::BoundTy { var, kind: ty::BoundTyKind::Anon })
     }
diff --git a/compiler/rustc_next_trait_solver/Cargo.toml b/compiler/rustc_next_trait_solver/Cargo.toml
index 9d496fd8e81..8bcc21d82f8 100644
--- a/compiler/rustc_next_trait_solver/Cargo.toml
+++ b/compiler/rustc_next_trait_solver/Cargo.toml
@@ -5,9 +5,19 @@ edition = "2021"
 
 [dependencies]
 rustc_type_ir = { path = "../rustc_type_ir", default-features = false }
+derivative = "2.2.0"
+rustc_macros = { path = "../rustc_macros", optional = true }
+rustc_type_ir_macros = { path = "../rustc_type_ir_macros" }
+rustc_serialize = { path = "../rustc_serialize", optional = true }
+rustc_data_structures = { path = "../rustc_data_structures", optional = true }
+rustc_ast_ir = { path = "../rustc_ast_ir", default-features = false }
 
 [features]
 default = ["nightly"]
 nightly = [
     "rustc_type_ir/nightly",
-]
\ No newline at end of file
+    "rustc_macros",
+    "rustc_serialize",
+    "rustc_data_structures",
+    "rustc_ast_ir/nightly",
+]
diff --git a/compiler/rustc_next_trait_solver/src/lib.rs b/compiler/rustc_next_trait_solver/src/lib.rs
index e5fc8f755e0..4202dc39fb2 100644
--- a/compiler/rustc_next_trait_solver/src/lib.rs
+++ b/compiler/rustc_next_trait_solver/src/lib.rs
@@ -1 +1,2 @@
 pub mod canonicalizer;
+pub mod solve;
diff --git a/compiler/rustc_next_trait_solver/src/solve.rs b/compiler/rustc_next_trait_solver/src/solve.rs
new file mode 100644
index 00000000000..eba96facabc
--- /dev/null
+++ b/compiler/rustc_next_trait_solver/src/solve.rs
@@ -0,0 +1 @@
+pub use rustc_type_ir::solve::*;
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs
index 90cc33e0275..cf826596392 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs
@@ -6,9 +6,8 @@ use rustc_hir::{def_id::DefId, Movability, Mutability};
 use rustc_infer::traits::query::NoSolution;
 use rustc_macros::{TypeFoldable, TypeVisitable};
 use rustc_middle::bug;
-use rustc_middle::ty::{
-    self, Goal, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, Upcast,
-};
+use rustc_middle::traits::solve::Goal;
+use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, Upcast};
 use rustc_span::sym;
 
 use crate::solve::EvalCtxt;
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
index e5d26e530ee..dfb2bfc1b58 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
@@ -1,3 +1,6 @@
+use std::io::Write;
+use std::ops::ControlFlow;
+
 use rustc_data_structures::stack::ensure_sufficient_stack;
 use rustc_hir::def_id::DefId;
 use rustc_infer::infer::at::ToTrace;
@@ -11,10 +14,9 @@ use rustc_infer::traits::ObligationCause;
 use rustc_macros::{extension, HashStable};
 use rustc_middle::bug;
 use rustc_middle::infer::canonical::CanonicalVarInfos;
-use rustc_middle::traits::solve::inspect;
 use rustc_middle::traits::solve::{
-    CanonicalInput, CanonicalResponse, Certainty, PredefinedOpaques, PredefinedOpaquesData,
-    QueryResult,
+    inspect, CanonicalInput, CanonicalResponse, Certainty, NestedGoals, PredefinedOpaques,
+    PredefinedOpaquesData, QueryResult,
 };
 use rustc_middle::traits::specialization_graph;
 use rustc_middle::ty::{
@@ -23,8 +25,6 @@ use rustc_middle::ty::{
 };
 use rustc_session::config::DumpSolverProofTree;
 use rustc_span::DUMMY_SP;
-use std::io::Write;
-use std::ops::ControlFlow;
 
 use crate::traits::coherence;
 use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment};
@@ -85,7 +85,7 @@ pub struct EvalCtxt<'a, 'tcx> {
 
     pub(super) search_graph: &'a mut SearchGraph<'tcx>,
 
-    nested_goals: NestedGoals<'tcx>,
+    nested_goals: NestedGoals<TyCtxt<'tcx>>,
 
     // Has this `EvalCtxt` errored out with `NoSolution` in `try_evaluate_added_goals`?
     //
@@ -98,8 +98,12 @@ pub struct EvalCtxt<'a, 'tcx> {
     pub(super) inspect: ProofTreeBuilder<'tcx>,
 }
 
-#[derive(Default, Debug, Clone)]
-pub(super) struct NestedGoals<'tcx> {
+#[derive(derivative::Derivative)]
+#[derivative(Clone(bound = ""), Debug(bound = ""), Default(bound = ""))]
+#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)]
+#[cfg_attr(feature = "nightly", derive(TyDecodable, TyEncodable, HashStable_NoContext))]
+// FIXME: This can be made crate-private once `EvalCtxt` also lives in this crate.
+pub struct NestedGoals<I: Interner> {
     /// These normalizes-to goals are treated specially during the evaluation
     /// loop. In each iteration we take the RHS of the projection, replace it with
     /// a fresh inference variable, and only after evaluating that goal do we
@@ -110,17 +114,17 @@ pub(super) struct NestedGoals<'tcx> {
     ///
     /// Forgetting to replace the RHS with a fresh inference variable when we evaluate
     /// this goal results in an ICE..
-    pub(super) normalizes_to_goals: Vec<Goal<'tcx, ty::NormalizesTo<'tcx>>>,
+    pub normalizes_to_goals: Vec<Goal<I, NormalizesTo<I>>>,
     /// The rest of the goals which have not yet processed or remain ambiguous.
-    pub(super) goals: Vec<(GoalSource, Goal<'tcx, ty::Predicate<'tcx>>)>,
+    pub goals: Vec<(GoalSource, Goal<I, I::Predicate>)>,
 }
 
-impl<'tcx> NestedGoals<'tcx> {
-    pub(super) fn new() -> Self {
+impl<I: Interner> NestedGoals<I> {
+    pub fn new() -> Self {
         Self { normalizes_to_goals: Vec::new(), goals: Vec::new() }
     }
 
-    pub(super) fn is_empty(&self) -> bool {
+    pub fn is_empty(&self) -> bool {
         self.normalizes_to_goals.is_empty() && self.goals.is_empty()
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 540ab738a22..5a3c960d72d 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -20,11 +20,11 @@ use rustc_macros::extension;
 use rustc_middle::bug;
 use rustc_middle::infer::canonical::CanonicalVarInfos;
 use rustc_middle::traits::solve::{
-    CanonicalResponse, Certainty, ExternalConstraintsData, GoalSource, QueryResult, Response,
+    CanonicalResponse, Certainty, ExternalConstraintsData, Goal, GoalSource, QueryResult, Response,
 };
 use rustc_middle::ty::{
-    self, AliasRelationDirection, CoercePredicate, Goal, RegionOutlivesPredicate, SubtypePredicate,
-    Ty, TyCtxt, TypeOutlivesPredicate, UniverseIndex,
+    self, AliasRelationDirection, CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, Ty,
+    TyCtxt, TypeOutlivesPredicate, UniverseIndex,
 };
 
 mod alias_relate;
diff --git a/compiler/rustc_type_ir/src/canonical.rs b/compiler/rustc_type_ir/src/canonical.rs
index efefd174cd6..1c30f03c693 100644
--- a/compiler/rustc_type_ir/src/canonical.rs
+++ b/compiler/rustc_type_ir/src/canonical.rs
@@ -1,11 +1,12 @@
 #[cfg(feature = "nightly")]
 use rustc_macros::{HashStable_NoContext, TyDecodable, TyEncodable};
-use rustc_type_ir_macros::{TypeFoldable_Generic, TypeVisitable_Generic};
+use rustc_type_ir_macros::{Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic};
 use std::fmt;
 use std::hash::Hash;
+use std::ops::Index;
 
 use crate::inherent::*;
-use crate::{Interner, UniverseIndex};
+use crate::{self as ty, Interner, UniverseIndex};
 
 /// A "canonicalized" type `V` is one where all free inference
 /// variables have been rewritten to "canonical vars". These are
@@ -257,3 +258,139 @@ pub enum CanonicalTyVarKind {
     /// Floating-point type variable `?F` (that can only be unified with float types).
     Float,
 }
+
+/// A set of values corresponding to the canonical variables from some
+/// `Canonical`. You can give these values to
+/// `canonical_value.instantiate` to instantiate them into the canonical
+/// value at the right places.
+///
+/// When you canonicalize a value `V`, you get back one of these
+/// vectors with the original values that were replaced by canonical
+/// variables. You will need to supply it later to instantiate the
+/// canonicalized query response.
+#[derive(derivative::Derivative)]
+#[derivative(
+    Clone(bound = ""),
+    Copy(bound = ""),
+    PartialEq(bound = ""),
+    Eq(bound = ""),
+    Hash(bound = ""),
+    Debug(bound = "")
+)]
+#[cfg_attr(feature = "nightly", derive(TyEncodable, TyDecodable, HashStable_NoContext))]
+#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)]
+pub struct CanonicalVarValues<I: Interner> {
+    pub var_values: I::GenericArgs,
+}
+
+impl<I: Interner> CanonicalVarValues<I> {
+    pub fn is_identity(&self) -> bool {
+        self.var_values.into_iter().enumerate().all(|(bv, arg)| match arg.kind() {
+            ty::GenericArgKind::Lifetime(r) => {
+                matches!(r.kind(), ty::ReBound(ty::INNERMOST, br) if br.var().as_usize() == bv)
+            }
+            ty::GenericArgKind::Type(ty) => {
+                matches!(ty.kind(), ty::Bound(ty::INNERMOST, bt) if bt.var().as_usize() == bv)
+            }
+            ty::GenericArgKind::Const(ct) => {
+                matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if bc.var().as_usize() == bv)
+            }
+        })
+    }
+
+    pub fn is_identity_modulo_regions(&self) -> bool {
+        let mut var = ty::BoundVar::ZERO;
+        for arg in self.var_values {
+            match arg.kind() {
+                ty::GenericArgKind::Lifetime(r) => {
+                    if matches!(r.kind(), ty::ReBound(ty::INNERMOST, br) if var == br.var()) {
+                        var = var + 1;
+                    } else {
+                        // It's ok if this region var isn't an identity variable
+                    }
+                }
+                ty::GenericArgKind::Type(ty) => {
+                    if matches!(ty.kind(), ty::Bound(ty::INNERMOST, bt) if var == bt.var()) {
+                        var = var + 1;
+                    } else {
+                        return false;
+                    }
+                }
+                ty::GenericArgKind::Const(ct) => {
+                    if matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if var == bc.var())
+                    {
+                        var = var + 1;
+                    } else {
+                        return false;
+                    }
+                }
+            }
+        }
+
+        true
+    }
+
+    // Given a list of canonical variables, construct a set of values which are
+    // the identity response.
+    pub fn make_identity(tcx: I, infos: I::CanonicalVars) -> CanonicalVarValues<I> {
+        CanonicalVarValues {
+            var_values: tcx.mk_args_from_iter(infos.into_iter().enumerate().map(
+                |(i, info)| -> I::GenericArg {
+                    match info.kind {
+                        CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => {
+                            Ty::new_anon_bound(tcx, ty::INNERMOST, ty::BoundVar::from_usize(i))
+                                .into()
+                        }
+                        CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => {
+                            Region::new_anon_bound(tcx, ty::INNERMOST, ty::BoundVar::from_usize(i))
+                                .into()
+                        }
+                        CanonicalVarKind::Effect => Const::new_anon_bound(
+                            tcx,
+                            ty::INNERMOST,
+                            ty::BoundVar::from_usize(i),
+                            Ty::new_bool(tcx),
+                        )
+                        .into(),
+                        CanonicalVarKind::Const(_, ty)
+                        | CanonicalVarKind::PlaceholderConst(_, ty) => Const::new_anon_bound(
+                            tcx,
+                            ty::INNERMOST,
+                            ty::BoundVar::from_usize(i),
+                            ty,
+                        )
+                        .into(),
+                    }
+                },
+            )),
+        }
+    }
+
+    /// Creates dummy var values which should not be used in a
+    /// canonical response.
+    pub fn dummy() -> CanonicalVarValues<I> {
+        CanonicalVarValues { var_values: Default::default() }
+    }
+
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.var_values.len()
+    }
+}
+
+impl<'a, I: Interner> IntoIterator for &'a CanonicalVarValues<I> {
+    type Item = I::GenericArg;
+    type IntoIter = <I::GenericArgs as IntoIterator>::IntoIter;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.var_values.into_iter()
+    }
+}
+
+impl<I: Interner> Index<ty::BoundVar> for CanonicalVarValues<I> {
+    type Output = I::GenericArg;
+
+    fn index(&self, value: ty::BoundVar) -> &I::GenericArg {
+        &self.var_values[value.as_usize()]
+    }
+}
diff --git a/compiler/rustc_type_ir/src/generic_arg.rs b/compiler/rustc_type_ir/src/generic_arg.rs
new file mode 100644
index 00000000000..622a4080608
--- /dev/null
+++ b/compiler/rustc_type_ir/src/generic_arg.rs
@@ -0,0 +1,18 @@
+use rustc_macros::{HashStable_NoContext, TyDecodable, TyEncodable};
+
+use crate::Interner;
+
+#[derive(derivative::Derivative)]
+#[derivative(
+    Clone(bound = ""),
+    Copy(bound = ""),
+    Debug(bound = ""),
+    Eq(bound = ""),
+    PartialEq(bound = "")
+)]
+#[cfg_attr(feature = "nightly", derive(TyDecodable, TyEncodable, HashStable_NoContext))]
+pub enum GenericArgKind<I: Interner> {
+    Lifetime(I::Region),
+    Type(I::Ty),
+    Const(I::Const),
+}
diff --git a/compiler/rustc_type_ir/src/inherent.rs b/compiler/rustc_type_ir/src/inherent.rs
index 484f6c31258..fa91fad86ab 100644
--- a/compiler/rustc_type_ir/src/inherent.rs
+++ b/compiler/rustc_type_ir/src/inherent.rs
@@ -1,3 +1,8 @@
+//! Set of traits which are used to emulate the inherent impls that are present in `rustc_middle`.
+//! It is customary to glob-import `rustc_type_ir::inherent::*` to bring all of these traits into
+//! scope when programming in interner-agnostic settings, and to avoid importing any of these
+//! directly elsewhere (i.e. specify the full path for an implementation downstream).
+
 use std::fmt::Debug;
 use std::hash::Hash;
 use std::ops::Deref;
@@ -21,6 +26,8 @@ pub trait Ty<I: Interner<Ty = Self>>:
     + TypeSuperFoldable<I>
     + Flags
 {
+    fn new_bool(interner: I) -> Self;
+
     fn new_anon_bound(interner: I, debruijn: DebruijnIndex, var: BoundVar) -> Self;
 
     fn new_alias(interner: I, kind: AliasTyKind, alias_ty: AliasTy<I>) -> Self;
@@ -79,6 +86,7 @@ pub trait GenericArgs<I: Interner<GenericArgs = Self>>:
     + Eq
     + IntoIterator<Item = I::GenericArg>
     + Deref<Target: Deref<Target = [I::GenericArg]>>
+    + Default
 {
     fn type_at(self, i: usize) -> I::Ty;
 
@@ -111,3 +119,7 @@ pub trait BoundVars<I: Interner> {
 
     fn has_no_bound_vars(&self) -> bool;
 }
+
+pub trait BoundVarLike<I: Interner> {
+    fn var(self) -> BoundVar;
+}
diff --git a/compiler/rustc_type_ir/src/interner.rs b/compiler/rustc_type_ir/src/interner.rs
index 78706b0e5a5..69865602584 100644
--- a/compiler/rustc_type_ir/src/interner.rs
+++ b/compiler/rustc_type_ir/src/interner.rs
@@ -8,8 +8,8 @@ use crate::ir_print::IrPrint;
 use crate::visit::{Flags, TypeSuperVisitable, TypeVisitable};
 use crate::{
     AliasTerm, AliasTermKind, AliasTy, AliasTyKind, CanonicalVarInfo, CoercePredicate,
-    DebugWithInfcx, ExistentialProjection, ExistentialTraitRef, FnSig, NormalizesTo,
-    ProjectionPredicate, SubtypePredicate, TraitPredicate, TraitRef,
+    DebugWithInfcx, ExistentialProjection, ExistentialTraitRef, FnSig, GenericArgKind,
+    NormalizesTo, ProjectionPredicate, SubtypePredicate, TraitPredicate, TraitRef,
 };
 
 pub trait Interner:
@@ -35,7 +35,7 @@ pub trait Interner:
     /// The slice of args for a specific item. For a GAT like `type Foo<'a>`, it will be `['a]`,
     /// not including the args from the parent item (trait or impl).
     type OwnItemArgs: Copy + Debug + Hash + Eq;
-    type GenericArg: Copy + DebugWithInfcx<Self> + Hash + Eq;
+    type GenericArg: Copy + DebugWithInfcx<Self> + Hash + Eq + IntoKind<Kind = GenericArgKind<Self>>;
     type Term: Copy + Debug + Hash + Eq;
 
     type Binder<T: TypeVisitable<Self>>: BoundVars<Self> + TypeSuperVisitable<Self>;
@@ -43,13 +43,14 @@ pub trait Interner:
     type BoundVar;
 
     type CanonicalVars: Copy + Debug + Hash + Eq + IntoIterator<Item = CanonicalVarInfo<Self>>;
+    type PredefinedOpaques: Copy + Debug + Hash + Eq;
 
     // Kinds of tys
     type Ty: Ty<Self>;
     type Tys: Tys<Self>;
     type FnInputTys: Copy + Debug + Hash + Eq + Deref<Target = [Self::Ty]>;
     type ParamTy: Copy + Debug + Hash + Eq;
-    type BoundTy: Copy + Debug + Hash + Eq;
+    type BoundTy: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
     type PlaceholderTy: PlaceholderLike;
 
     // Things stored inside of tys
@@ -66,7 +67,7 @@ pub trait Interner:
     type AliasConst: Copy + DebugWithInfcx<Self> + Hash + Eq;
     type PlaceholderConst: PlaceholderLike;
     type ParamConst: Copy + Debug + Hash + Eq;
-    type BoundConst: Copy + Debug + Hash + Eq;
+    type BoundConst: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
     type ValueConst: Copy + Debug + Hash + Eq;
     type ExprConst: Copy + DebugWithInfcx<Self> + Hash + Eq;
 
@@ -74,7 +75,7 @@ pub trait Interner:
     type Region: Region<Self>;
     type EarlyParamRegion: Copy + Debug + Hash + Eq;
     type LateParamRegion: Copy + Debug + Hash + Eq;
-    type BoundRegion: Copy + Debug + Hash + Eq;
+    type BoundRegion: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
     type InferRegion: Copy + DebugWithInfcx<Self> + Hash + Eq;
     type PlaceholderRegion: PlaceholderLike;
 
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs
index 26aa07c1f44..fa9bda9a2f7 100644
--- a/compiler/rustc_type_ir/src/lib.rs
+++ b/compiler/rustc_type_ir/src/lib.rs
@@ -19,13 +19,13 @@ use std::sync::Arc as Lrc;
 
 #[macro_use]
 pub mod visit;
-
 #[cfg(feature = "nightly")]
 pub mod codec;
 pub mod fold;
 pub mod inherent;
 pub mod ir_print;
 pub mod lift;
+pub mod solve;
 pub mod ty_info;
 pub mod ty_kind;
 
@@ -35,6 +35,7 @@ mod canonical;
 mod const_kind;
 mod debug;
 mod flags;
+mod generic_arg;
 mod infcx;
 mod interner;
 mod predicate;
@@ -48,6 +49,7 @@ pub use codec::*;
 pub use const_kind::*;
 pub use debug::{DebugWithInfcx, WithInfcx};
 pub use flags::*;
+pub use generic_arg::*;
 pub use infcx::InferCtxtLike;
 pub use interner::*;
 pub use predicate::*;
@@ -368,6 +370,12 @@ rustc_index::newtype_index! {
     pub struct BoundVar {}
 }
 
+impl<I: Interner> inherent::BoundVarLike<I> for BoundVar {
+    fn var(self) -> BoundVar {
+        self
+    }
+}
+
 /// Represents the various closure traits in the language. This
 /// will determine the type of the environment (`self`, in the
 /// desugaring) argument that the closure expects.
diff --git a/compiler/rustc_type_ir/src/predicate.rs b/compiler/rustc_type_ir/src/predicate.rs
index 35e045457df..c0619d782c6 100644
--- a/compiler/rustc_type_ir/src/predicate.rs
+++ b/compiler/rustc_type_ir/src/predicate.rs
@@ -8,42 +8,9 @@ use rustc_type_ir_macros::{Lift_Generic, TypeFoldable_Generic, TypeVisitable_Gen
 use crate::inherent::*;
 use crate::visit::TypeVisitableExt as _;
 use crate::{
-    AliasTy, AliasTyKind, DebugWithInfcx, InferCtxtLike, Interner, UnevaluatedConst, Upcast,
-    WithInfcx,
+    AliasTy, AliasTyKind, DebugWithInfcx, InferCtxtLike, Interner, UnevaluatedConst, WithInfcx,
 };
 
-/// A goal is a statement, i.e. `predicate`, we want to prove
-/// given some assumptions, i.e. `param_env`.
-///
-/// Most of the time the `param_env` contains the `where`-bounds of the function
-/// we're currently typechecking while the `predicate` is some trait bound.
-#[derive(derivative::Derivative)]
-#[derivative(
-    Clone(bound = "P: Clone"),
-    Copy(bound = "P: Copy"),
-    Hash(bound = "P: Hash"),
-    PartialEq(bound = "P: PartialEq"),
-    Eq(bound = "P: Eq"),
-    Debug(bound = "P: fmt::Debug")
-)]
-#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)]
-#[cfg_attr(feature = "nightly", derive(TyDecodable, TyEncodable, HashStable_NoContext))]
-pub struct Goal<I: Interner, P> {
-    pub param_env: I::ParamEnv,
-    pub predicate: P,
-}
-
-impl<I: Interner, P> Goal<I, P> {
-    pub fn new(tcx: I, param_env: I::ParamEnv, predicate: impl Upcast<I, P>) -> Goal<I, P> {
-        Goal { param_env, predicate: predicate.upcast(tcx) }
-    }
-
-    /// Updates the goal to one with a different `predicate` but the same `param_env`.
-    pub fn with<Q>(self, tcx: I, predicate: impl Upcast<I, Q>) -> Goal<I, Q> {
-        Goal { param_env: self.param_env, predicate: predicate.upcast(tcx) }
-    }
-}
-
 /// A complete reference to a trait. These take numerous guises in syntax,
 /// but perhaps the most recognizable form is in a where-clause:
 /// ```ignore (illustrative)
diff --git a/compiler/rustc_type_ir/src/solve.rs b/compiler/rustc_type_ir/src/solve.rs
new file mode 100644
index 00000000000..2a733dd02c2
--- /dev/null
+++ b/compiler/rustc_type_ir/src/solve.rs
@@ -0,0 +1,80 @@
+use std::fmt;
+use std::hash::Hash;
+
+#[cfg(feature = "nightly")]
+use rustc_macros::{HashStable_NoContext, TyDecodable, TyEncodable};
+use rustc_type_ir_macros::{Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic};
+
+use crate::{Interner, NormalizesTo, Upcast};
+
+/// A goal is a statement, i.e. `predicate`, we want to prove
+/// given some assumptions, i.e. `param_env`.
+///
+/// Most of the time the `param_env` contains the `where`-bounds of the function
+/// we're currently typechecking while the `predicate` is some trait bound.
+#[derive(derivative::Derivative)]
+#[derivative(
+    Clone(bound = "P: Clone"),
+    Copy(bound = "P: Copy"),
+    Hash(bound = "P: Hash"),
+    PartialEq(bound = "P: PartialEq"),
+    Eq(bound = "P: Eq"),
+    Debug(bound = "P: fmt::Debug")
+)]
+#[derive(TypeVisitable_Generic, TypeFoldable_Generic, Lift_Generic)]
+#[cfg_attr(feature = "nightly", derive(TyDecodable, TyEncodable, HashStable_NoContext))]
+pub struct Goal<I: Interner, P> {
+    pub param_env: I::ParamEnv,
+    pub predicate: P,
+}
+
+impl<I: Interner, P> Goal<I, P> {
+    pub fn new(tcx: I, param_env: I::ParamEnv, predicate: impl Upcast<I, P>) -> Goal<I, P> {
+        Goal { param_env, predicate: predicate.upcast(tcx) }
+    }
+
+    /// Updates the goal to one with a different `predicate` but the same `param_env`.
+    pub fn with<Q>(self, tcx: I, predicate: impl Upcast<I, Q>) -> Goal<I, Q> {
+        Goal { param_env: self.param_env, predicate: predicate.upcast(tcx) }
+    }
+}
+
+/// Why a specific goal has to be proven.
+///
+/// This is necessary as we treat nested goals different depending on
+/// their source.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TypeVisitable_Generic, TypeFoldable_Generic)]
+#[cfg_attr(feature = "nightly", derive(HashStable_NoContext))]
+pub enum GoalSource {
+    Misc,
+    /// We're proving a where-bound of an impl.
+    ///
+    /// FIXME(-Znext-solver=coinductive): Explain how and why this
+    /// changes whether cycles are coinductive.
+    ///
+    /// This also impacts whether we erase constraints on overflow.
+    /// Erasing constraints is generally very useful for perf and also
+    /// results in better error messages by avoiding spurious errors.
+    /// We do not erase overflow constraints in `normalizes-to` goals unless
+    /// they are from an impl where-clause. This is necessary due to
+    /// backwards compatability, cc trait-system-refactor-initiatitive#70.
+    ImplWhereBound,
+    /// Instantiating a higher-ranked goal and re-proving it.
+    InstantiateHigherRanked,
+}
+
+#[derive(derivative::Derivative)]
+#[derivative(
+    Clone(bound = "Goal<I, P>: Clone"),
+    Copy(bound = "Goal<I, P>: Copy"),
+    Hash(bound = "Goal<I, P>: Hash"),
+    PartialEq(bound = "Goal<I, P>: PartialEq"),
+    Eq(bound = "Goal<I, P>: Eq"),
+    Debug(bound = "Goal<I, P>: fmt::Debug")
+)]
+#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
+#[cfg_attr(feature = "nightly", derive(TyDecodable, TyEncodable, HashStable_NoContext))]
+pub struct QueryInput<I: Interner, P> {
+    pub goal: Goal<I, P>,
+    pub predefined_opaques_in_body: I::PredefinedOpaques,
+}