6 files changed, 176 insertions, 5 deletions
diff --git a/compiler/rustc_infer/src/infer/mod.rs b/compiler/rustc_infer/src/infer/mod.rs
index 515c9c34098..c2513a1af19 100644
--- a/compiler/rustc_infer/src/infer/mod.rs
+++ b/compiler/rustc_infer/src/infer/mod.rs
@@ -26,7 +26,6 @@ use rustc_macros::extension;
 pub use rustc_macros::{TypeFoldable, TypeVisitable};
 use rustc_middle::bug;
 use rustc_middle::infer::canonical::{CanonicalQueryInput, CanonicalVarValues};
-use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableValue, ConstVidKey};
 use rustc_middle::mir::ConstraintCategory;
 use rustc_middle::traits::select;
 pub use rustc_middle::ty::IntVarValue;
@@ -46,6 +45,7 @@ use tracing::{debug, instrument};
 use type_variable::TypeVariableOrigin;
 
 use crate::infer::region_constraints::UndoLog;
+use crate::infer::unify_key::{ConstVariableOrigin, ConstVariableValue, ConstVidKey};
 use crate::traits::{
     self, ObligationCause, ObligationInspector, PredicateObligations, TraitEngine,
 };
@@ -64,6 +64,7 @@ pub mod relate;
 pub mod resolve;
 pub(crate) mod snapshot;
 mod type_variable;
+mod unify_key;
 
 /// `InferOk<'tcx, ()>` is used a lot. It may seem like a useless wrapper
 /// around `PredicateObligations<'tcx>`, but it has one important property:
diff --git a/compiler/rustc_infer/src/infer/region_constraints/mod.rs b/compiler/rustc_infer/src/infer/region_constraints/mod.rs
index 6496f38269a..57555db37ab 100644
--- a/compiler/rustc_infer/src/infer/region_constraints/mod.rs
+++ b/compiler/rustc_infer/src/infer/region_constraints/mod.rs
@@ -8,7 +8,6 @@ use rustc_data_structures::undo_log::UndoLogs;
 use rustc_data_structures::unify as ut;
 use rustc_index::IndexVec;
 use rustc_macros::{TypeFoldable, TypeVisitable};
-use rustc_middle::infer::unify_key::{RegionVariableValue, RegionVidKey};
 use rustc_middle::ty::{self, ReBound, ReStatic, ReVar, Region, RegionVid, Ty, TyCtxt};
 use rustc_middle::{bug, span_bug};
 use tracing::{debug, instrument};
@@ -17,6 +16,7 @@ use self::CombineMapType::*;
 use self::UndoLog::*;
 use super::{MiscVariable, RegionVariableOrigin, Rollback, SubregionOrigin};
 use crate::infer::snapshot::undo_log::{InferCtxtUndoLogs, Snapshot};
+use crate::infer::unify_key::{RegionVariableValue, RegionVidKey};
 
 mod leak_check;
 
diff --git a/compiler/rustc_infer/src/infer/relate/generalize.rs b/compiler/rustc_infer/src/infer/relate/generalize.rs
index 21c47967ead..ce2d07f4af9 100644
--- a/compiler/rustc_infer/src/infer/relate/generalize.rs
+++ b/compiler/rustc_infer/src/infer/relate/generalize.rs
@@ -4,7 +4,6 @@ use rustc_data_structures::sso::SsoHashMap;
 use rustc_data_structures::stack::ensure_sufficient_stack;
 use rustc_hir::def_id::DefId;
 use rustc_middle::bug;
-use rustc_middle::infer::unify_key::ConstVariableValue;
 use rustc_middle::ty::error::TypeError;
 use rustc_middle::ty::visit::MaxUniverse;
 use rustc_middle::ty::{
@@ -18,6 +17,7 @@ use super::{
     PredicateEmittingRelation, Relate, RelateResult, StructurallyRelateAliases, TypeRelation,
 };
 use crate::infer::type_variable::TypeVariableValue;
+use crate::infer::unify_key::ConstVariableValue;
 use crate::infer::{InferCtxt, RegionVariableOrigin, relate};
 
 impl<'tcx> InferCtxt<'tcx> {
diff --git a/compiler/rustc_infer/src/infer/snapshot/fudge.rs b/compiler/rustc_infer/src/infer/snapshot/fudge.rs
index 394e07a81e7..3a47b13665d 100644
--- a/compiler/rustc_infer/src/infer/snapshot/fudge.rs
+++ b/compiler/rustc_infer/src/infer/snapshot/fudge.rs
@@ -1,7 +1,6 @@
 use std::ops::Range;
 
 use rustc_data_structures::{snapshot_vec as sv, unify as ut};
-use rustc_middle::infer::unify_key::{ConstVariableValue, ConstVidKey};
 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder, TypeSuperFoldable};
 use rustc_middle::ty::{self, ConstVid, FloatVid, IntVid, RegionVid, Ty, TyCtxt, TyVid};
 use rustc_type_ir::visit::TypeVisitableExt;
@@ -10,6 +9,7 @@ use ut::UnifyKey;
 
 use super::VariableLengths;
 use crate::infer::type_variable::TypeVariableOrigin;
+use crate::infer::unify_key::{ConstVariableValue, ConstVidKey};
 use crate::infer::{ConstVariableOrigin, InferCtxt, RegionVariableOrigin, UnificationTable};
 
 fn vars_since_snapshot<'tcx, T>(
diff --git a/compiler/rustc_infer/src/infer/snapshot/undo_log.rs b/compiler/rustc_infer/src/infer/snapshot/undo_log.rs
index 713389f4618..ba7d8f588e6 100644
--- a/compiler/rustc_infer/src/infer/snapshot/undo_log.rs
+++ b/compiler/rustc_infer/src/infer/snapshot/undo_log.rs
@@ -2,10 +2,10 @@ use std::marker::PhantomData;
 
 use rustc_data_structures::undo_log::{Rollback, UndoLogs};
 use rustc_data_structures::{snapshot_vec as sv, unify as ut};
-use rustc_middle::infer::unify_key::{ConstVidKey, RegionVidKey};
 use rustc_middle::ty::{self, OpaqueHiddenType, OpaqueTypeKey};
 use tracing::debug;
 
+use crate::infer::unify_key::{ConstVidKey, RegionVidKey};
 use crate::infer::{InferCtxtInner, region_constraints, type_variable};
 use crate::traits;
 
diff --git a/compiler/rustc_infer/src/infer/unify_key.rs b/compiler/rustc_infer/src/infer/unify_key.rs
new file mode 100644
index 00000000000..3ba8aea1d3a
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/unify_key.rs
@@ -0,0 +1,170 @@
+use std::cmp;
+use std::marker::PhantomData;
+
+use rustc_data_structures::unify::{NoError, UnifyKey, UnifyValue};
+use rustc_middle::{bug, ty};
+use rustc_span::Span;
+use rustc_span::def_id::DefId;
+
+#[derive(Copy, Clone, Debug)]
+pub(crate) enum RegionVariableValue<'tcx> {
+    Known { value: ty::Region<'tcx> },
+    Unknown { universe: ty::UniverseIndex },
+}
+
+#[derive(PartialEq, Copy, Clone, Debug)]
+pub(crate) struct RegionVidKey<'tcx> {
+    pub vid: ty::RegionVid,
+    pub phantom: PhantomData<RegionVariableValue<'tcx>>,
+}
+
+impl<'tcx> From<ty::RegionVid> for RegionVidKey<'tcx> {
+    fn from(vid: ty::RegionVid) -> Self {
+        RegionVidKey { vid, phantom: PhantomData }
+    }
+}
+
+impl<'tcx> UnifyKey for RegionVidKey<'tcx> {
+    type Value = RegionVariableValue<'tcx>;
+    #[inline]
+    fn index(&self) -> u32 {
+        self.vid.as_u32()
+    }
+    #[inline]
+    fn from_index(i: u32) -> Self {
+        RegionVidKey::from(ty::RegionVid::from_u32(i))
+    }
+    fn tag() -> &'static str {
+        "RegionVidKey"
+    }
+}
+
+pub(crate) struct RegionUnificationError;
+
+impl<'tcx> UnifyValue for RegionVariableValue<'tcx> {
+    type Error = RegionUnificationError;
+
+    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error> {
+        match (*value1, *value2) {
+            (RegionVariableValue::Known { .. }, RegionVariableValue::Known { .. }) => {
+                Err(RegionUnificationError)
+            }
+
+            (RegionVariableValue::Known { value }, RegionVariableValue::Unknown { universe })
+            | (RegionVariableValue::Unknown { universe }, RegionVariableValue::Known { value }) => {
+                let universe_of_value = match value.kind() {
+                    ty::ReStatic
+                    | ty::ReErased
+                    | ty::ReLateParam(..)
+                    | ty::ReEarlyParam(..)
+                    | ty::ReError(_) => ty::UniverseIndex::ROOT,
+                    ty::RePlaceholder(placeholder) => placeholder.universe,
+                    ty::ReVar(..) | ty::ReBound(..) => bug!("not a universal region"),
+                };
+
+                if universe.can_name(universe_of_value) {
+                    Ok(RegionVariableValue::Known { value })
+                } else {
+                    Err(RegionUnificationError)
+                }
+            }
+
+            (
+                RegionVariableValue::Unknown { universe: a },
+                RegionVariableValue::Unknown { universe: b },
+            ) => {
+                // If we unify two unconstrained regions then whatever
+                // value they wind up taking (which must be the same value) must
+                // be nameable by both universes. Therefore, the resulting
+                // universe is the minimum of the two universes, because that is
+                // the one which contains the fewest names in scope.
+                Ok(RegionVariableValue::Unknown { universe: a.min(b) })
+            }
+        }
+    }
+}
+
+// Generic consts.
+
+#[derive(Copy, Clone, Debug)]
+pub struct ConstVariableOrigin {
+    pub span: Span,
+    /// `DefId` of the const parameter this was instantiated for, if any.
+    ///
+    /// This should only be used for diagnostics.
+    pub param_def_id: Option<DefId>,
+}
+
+#[derive(Copy, Clone, Debug)]
+pub(crate) enum ConstVariableValue<'tcx> {
+    Known { value: ty::Const<'tcx> },
+    Unknown { origin: ConstVariableOrigin, universe: ty::UniverseIndex },
+}
+
+impl<'tcx> ConstVariableValue<'tcx> {
+    /// If this value is known, returns the const it is known to be.
+    /// Otherwise, `None`.
+    pub(crate) fn known(&self) -> Option<ty::Const<'tcx>> {
+        match *self {
+            ConstVariableValue::Unknown { .. } => None,
+            ConstVariableValue::Known { value } => Some(value),
+        }
+    }
+}
+
+#[derive(PartialEq, Copy, Clone, Debug)]
+pub(crate) struct ConstVidKey<'tcx> {
+    pub vid: ty::ConstVid,
+    pub phantom: PhantomData<ty::Const<'tcx>>,
+}
+
+impl<'tcx> From<ty::ConstVid> for ConstVidKey<'tcx> {
+    fn from(vid: ty::ConstVid) -> Self {
+        ConstVidKey { vid, phantom: PhantomData }
+    }
+}
+
+impl<'tcx> UnifyKey for ConstVidKey<'tcx> {
+    type Value = ConstVariableValue<'tcx>;
+    #[inline]
+    fn index(&self) -> u32 {
+        self.vid.as_u32()
+    }
+    #[inline]
+    fn from_index(i: u32) -> Self {
+        ConstVidKey::from(ty::ConstVid::from_u32(i))
+    }
+    fn tag() -> &'static str {
+        "ConstVidKey"
+    }
+}
+
+impl<'tcx> UnifyValue for ConstVariableValue<'tcx> {
+    type Error = NoError;
+
+    fn unify_values(&value1: &Self, &value2: &Self) -> Result<Self, Self::Error> {
+        match (value1, value2) {
+            (ConstVariableValue::Known { .. }, ConstVariableValue::Known { .. }) => {
+                bug!("equating two const variables, both of which have known values")
+            }
+
+            // If one side is known, prefer that one.
+            (ConstVariableValue::Known { .. }, ConstVariableValue::Unknown { .. }) => Ok(value1),
+            (ConstVariableValue::Unknown { .. }, ConstVariableValue::Known { .. }) => Ok(value2),
+
+            // If both sides are *unknown*, it hardly matters, does it?
+            (
+                ConstVariableValue::Unknown { origin, universe: universe1 },
+                ConstVariableValue::Unknown { origin: _, universe: universe2 },
+            ) => {
+                // If we unify two unbound variables, ?T and ?U, then whatever
+                // value they wind up taking (which must be the same value) must
+                // be nameable by both universes. Therefore, the resulting
+                // universe is the minimum of the two universes, because that is
+                // the one which contains the fewest names in scope.
+                let universe = cmp::min(universe1, universe2);
+                Ok(ConstVariableValue::Unknown { origin, universe })
+            }
+        }
+    }
+}