Implement TypeRelation::consts

Co-Authored-By: Gabriel Smith <yodaldevoid@users.noreply.github.com>

9 files changed, 315 insertions, 18 deletions

diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs
index 9bd7f4c02d7..0fc13bdaee6 100644
--- a/src/librustc/infer/canonical/canonicalizer.rs
+++ b/src/librustc/infer/canonical/canonicalizer.rs
@@ -10,10 +10,11 @@ use crate::infer::canonical::{
     OriginalQueryValues,
 };
 use crate::infer::InferCtxt;
+use crate::mir::interpret::ConstValue;
 use std::sync::atomic::Ordering;
 use crate::ty::fold::{TypeFoldable, TypeFolder};
 use crate::ty::subst::Kind;
-use crate::ty::{self, BoundVar, Lift, List, Ty, TyCtxt, TypeFlags};
+use crate::ty::{self, BoundVar, InferConst, Lift, List, Ty, TyCtxt, TypeFlags};
 
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::indexed_vec::Idx;
@@ -432,6 +433,54 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx>
             }
         }
     }
+
+    fn fold_const(&mut self, c: &'tcx ty::LazyConst<'tcx>) -> &'tcx ty::LazyConst<'tcx> {
+        if let ty::LazyConst::Evaluated(ct) = c {
+            match ct.val {
+                ConstValue::Infer(InferConst::Var(vid)) => {
+                    debug!("canonical: const var found with vid {:?}", vid);
+                    match self.infcx.unwrap().probe_const_var(vid) {
+                        Ok(c) => {
+                            debug!("(resolved to {:?})", c);
+                            return self.fold_const(c);
+                        }
+
+                        // `ConstVar(vid)` is unresolved, track its universe index in the
+                        // canonicalized result
+                        Err(mut ui) => {
+                            if !self.infcx.unwrap().tcx.sess.opts.debugging_opts.chalk {
+                                // FIXME: perf problem described in #55921.
+                                ui = ty::UniverseIndex::ROOT;
+                            }
+                            return self.canonicalize_const_var(
+                                CanonicalVarInfo {
+                                    kind: CanonicalVarKind::Const(ui)
+                                },
+                                c
+                            );
+                        }
+                    }
+                }
+                ConstValue::Infer(InferConst::Fresh(_)) => {
+                    bug!("encountered a fresh const during canonicalization")
+                }
+                ConstValue::Infer(InferConst::Canonical(debruijn, _)) => {
+                    if debruijn >= self.binder_index {
+                        bug!("escaping bound type during canonicalization")
+                    } else {
+                        return c;
+                    }
+                }
+                _ => {}
+            }
+        }
+
+        if c.type_flags().intersects(self.needs_canonical_flags) {
+            c.super_fold_with(self)
+        } else {
+            c
+        }
+    }
 }
 
 impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
@@ -625,7 +674,7 @@ impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
     /// `ty_var`.
     fn canonicalize_ty_var(&mut self, info: CanonicalVarInfo, ty_var: Ty<'tcx>) -> Ty<'tcx> {
         let infcx = self.infcx.expect("encountered ty-var without infcx");
-        let bound_to = infcx.shallow_resolve(ty_var);
+        let bound_to = infcx.shallow_resolve_type(ty_var);
         if bound_to != ty_var {
             self.fold_ty(bound_to)
         } else {
diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index f212f6298be..203fd25c842 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -464,7 +464,7 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
 
         debug!("generalize: t={:?}", t);
 
-        // Check to see whether the type we are genealizing references
+        // Check to see whether the type we are generalizing references
         // any other type variable related to `vid` via
         // subtyping. This is basically our "occurs check", preventing
         // us from creating infinitely sized types.
@@ -576,6 +576,32 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
         // very descriptive origin for this region variable.
         Ok(self.infcx.next_region_var_in_universe(MiscVariable(self.span), self.for_universe))
     }
+
+    fn consts(
+        &mut self,
+        c: &'tcx ty::LazyConst<'tcx>,
+        c2: &'tcx ty::LazyConst<'tcx>
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        assert_eq!(c, c2); // we are abusing TypeRelation here; both LHS and RHS ought to be ==
+
+        match c {
+            LazyConst::Evaluated(ty::Const {
+                val: ConstValue::Infer(InferConst::Var(vid)),
+                ..
+            }) => {
+                let mut variable_table = self.infcx.const_unification_table.borrow_mut();
+                match variable_table.probe(*vid).known() {
+                    Some(u) => {
+                        self.relate(&u, &u)
+                    }
+                    None => Ok(c),
+                }
+            }
+            _ => {
+                relate::super_relate_consts(self, c, c)
+            }
+        }
+    }
 }
 
 pub trait RelateResultCompare<'tcx, T> {
diff --git a/src/librustc/infer/equate.rs b/src/librustc/infer/equate.rs
index 31b01eecf5c..e94996a0b99 100644
--- a/src/librustc/infer/equate.rs
+++ b/src/librustc/infer/equate.rs
@@ -1,12 +1,13 @@
-use super::combine::{CombineFields, RelationDir};
-use super::{Subtype};
+use super::combine::{CombineFields, RelationDir, const_unification_error};
+use super::Subtype;
 
 use crate::hir::def_id::DefId;
 
-use crate::ty::{self, Ty, TyCtxt};
+use crate::ty::{self, Ty, TyCtxt, InferConst};
 use crate::ty::TyVar;
 use crate::ty::subst::SubstsRef;
 use crate::ty::relate::{self, Relate, RelateResult, TypeRelation};
+use crate::mir::interpret::ConstValue;
 
 /// Ensures `a` is made equal to `b`. Returns `a` on success.
 pub struct Equate<'combine, 'infcx: 'combine, 'gcx: 'infcx+'tcx, 'tcx: 'infcx> {
@@ -100,6 +101,47 @@ impl<'combine, 'infcx, 'gcx, 'tcx> TypeRelation<'infcx, 'gcx, 'tcx>
         Ok(a)
     }
 
+    fn consts(
+        &mut self,
+        a: &'tcx ty::LazyConst<'tcx>,
+        b: &'tcx ty::LazyConst<'tcx>,
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        debug!("{}.consts({:?}, {:?})", self.tag(), a, b);
+        if a == b { return Ok(a); }
+
+        let infcx = self.fields.infcx;
+        let a = infcx.const_unification_table.borrow_mut().replace_if_possible(a);
+        let b = infcx.const_unification_table.borrow_mut().replace_if_possible(b);
+        let a_is_expected = self.a_is_expected();
+        if let (&ty::LazyConst::Evaluated(a_eval), &ty::LazyConst::Evaluated(b_eval)) = (a, b) {
+            match (a_eval.val, b_eval.val) {
+                (ConstValue::Infer(InferConst::Var(a_vid)),
+                 ConstValue::Infer(InferConst::Var(b_vid))) => {
+                    infcx.const_unification_table
+                        .borrow_mut()
+                        .unify_var_var(a_vid, b_vid)
+                        .map_err(|e| const_unification_error(a_is_expected, e))?;
+                    return Ok(a);
+                }
+
+                (ConstValue::Infer(InferConst::Var(a_id)), _) => {
+                    self.fields.infcx.unify_const_variable(a_is_expected, a_id, b)?;
+                    return Ok(a);
+                }
+
+                (_, ConstValue::Infer(InferConst::Var(b_id))) => {
+                    self.fields.infcx.unify_const_variable(!a_is_expected, b_id, a)?;
+                    return Ok(a);
+                }
+
+                _ => {}
+            }
+        }
+
+        self.fields.infcx.super_combine_consts(self, a, b)?;
+        Ok(a)
+    }
+
     fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
                   -> RelateResult<'tcx, ty::Binder<T>>
         where T: Relate<'tcx>
diff --git a/src/librustc/infer/glb.rs b/src/librustc/infer/glb.rs
index 910c6571853..dde43d20722 100644
--- a/src/librustc/infer/glb.rs
+++ b/src/librustc/infer/glb.rs
@@ -60,6 +60,19 @@ impl<'combine, 'infcx, 'gcx, 'tcx> TypeRelation<'infcx, 'gcx, 'tcx>
         Ok(self.fields.infcx.borrow_region_constraints().glb_regions(self.tcx(), origin, a, b))
     }
 
+    fn consts(
+        &mut self,
+        a: &'tcx ty::LazyConst<'tcx>,
+        b: &'tcx ty::LazyConst<'tcx>,
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        debug!("{}.consts({:?}, {:?})", self.tag(), a, b);
+        if a == b {
+            return Ok(a);
+        }
+
+        self.fields.infcx.super_combine_consts(self, a, b)
+    }
+
     fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
                   -> RelateResult<'tcx, ty::Binder<T>>
         where T: Relate<'tcx>
diff --git a/src/librustc/infer/lub.rs b/src/librustc/infer/lub.rs
index f9eb60d82d1..2a06886d94b 100644
--- a/src/librustc/infer/lub.rs
+++ b/src/librustc/infer/lub.rs
@@ -60,6 +60,19 @@ impl<'combine, 'infcx, 'gcx, 'tcx> TypeRelation<'infcx, 'gcx, 'tcx>
         Ok(self.fields.infcx.borrow_region_constraints().lub_regions(self.tcx(), origin, a, b))
     }
 
+    fn consts(
+        &mut self,
+        a: &'tcx ty::LazyConst<'tcx>,
+        b: &'tcx ty::LazyConst<'tcx>,
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        debug!("{}.consts({:?}, {:?})", self.tag(), a, b);
+        if a == b {
+            return Ok(a);
+        }
+
+        self.fields.infcx.super_combine_consts(self, a, b)
+    }
+
     fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
                   -> RelateResult<'tcx, ty::Binder<T>>
         where T: Relate<'tcx>
diff --git a/src/librustc/infer/nll_relate/mod.rs b/src/librustc/infer/nll_relate/mod.rs
index 753fd04aac3..91a1e0a13bc 100644
--- a/src/librustc/infer/nll_relate/mod.rs
+++ b/src/librustc/infer/nll_relate/mod.rs
@@ -27,7 +27,7 @@ use crate::ty::error::TypeError;
 use crate::ty::fold::{TypeFoldable, TypeVisitor};
 use crate::ty::relate::{self, Relate, RelateResult, TypeRelation};
 use crate::ty::subst::Kind;
-use crate::ty::{self, Ty, TyCtxt};
+use crate::ty::{self, Ty, TyCtxt, InferConst};
 use rustc_data_structures::fx::FxHashMap;
 use std::fmt::Debug;
 
@@ -537,10 +537,10 @@ where
     }
 
     fn tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
-        let a = self.infcx.shallow_resolve(a);
+        let a = self.infcx.shallow_resolve_type(a);
 
         if !D::forbid_inference_vars() {
-            b = self.infcx.shallow_resolve(b);
+            b = self.infcx.shallow_resolve_type(b);
         }
 
         match (&a.sty, &b.sty) {
@@ -608,6 +608,24 @@ where
         Ok(a)
     }
 
+    fn consts(
+        &mut self,
+        a: &'tcx ty::LazyConst<'tcx>,
+        b: &'tcx ty::LazyConst<'tcx>,
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        if let ty::LazyConst::Evaluated(ty::Const {
+            val: ConstValue::Infer(InferConst::Canonical(_, _)),
+            ..
+        }) = a {
+            // FIXME(const_generics): I'm unsure how this branch should actually be handled,
+            // so this is probably not correct.
+            self.infcx.super_combine_consts(self, a, b)
+        } else {
+            debug!("consts(a={:?}, b={:?}, variance={:?})", a, b, self.ambient_variance);
+            relate::super_relate_consts(self, a, b)
+        }
+    }
+
     fn binders<T>(
         &mut self,
         a: &ty::Binder<T>,
@@ -853,7 +871,7 @@ where
     fn tys(&mut self, a: Ty<'tcx>, _: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
         use crate::infer::type_variable::TypeVariableValue;
 
-        debug!("TypeGeneralizer::tys(a={:?})", a,);
+        debug!("TypeGeneralizer::tys(a={:?})", a);
 
         match a.sty {
             ty::Infer(ty::TyVar(_)) | ty::Infer(ty::IntVar(_)) | ty::Infer(ty::FloatVar(_))
@@ -934,7 +952,7 @@ where
         a: ty::Region<'tcx>,
         _: ty::Region<'tcx>,
     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
-        debug!("TypeGeneralizer::regions(a={:?})", a,);
+        debug!("TypeGeneralizer::regions(a={:?})", a);
 
         if let ty::ReLateBound(debruijn, _) = a {
             if *debruijn < self.first_free_index {
@@ -963,6 +981,26 @@ where
         Ok(replacement_region_vid)
     }
 
+    fn consts(
+        &mut self,
+        a: &'tcx ty::LazyConst<'tcx>,
+        _: &'tcx ty::LazyConst<'tcx>,
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        debug!("TypeGeneralizer::consts(a={:?})", a);
+
+        if let ty::LazyConst::Evaluated(ty::Const {
+            val: ConstValue::Infer(InferConst::Canonical(_, _)),
+            ..
+        }) = a {
+            bug!(
+                "unexpected inference variable encountered in NLL generalization: {:?}",
+                a
+            );
+        } else {
+            relate::super_relate_consts(self, a, a)
+        }
+    }
+
     fn binders<T>(
         &mut self,
         a: &ty::Binder<T>,
@@ -971,7 +1009,7 @@ where
     where
         T: Relate<'tcx>,
     {
-        debug!("TypeGeneralizer::binders(a={:?})", a,);
+        debug!("TypeGeneralizer::binders(a={:?})", a);
 
         self.first_free_index.shift_in(1);
         let result = self.relate(a.skip_binder(), a.skip_binder())?;
diff --git a/src/librustc/infer/sub.rs b/src/librustc/infer/sub.rs
index 0cff42742c3..b285d597291 100644
--- a/src/librustc/infer/sub.rs
+++ b/src/librustc/infer/sub.rs
@@ -1,11 +1,12 @@
 use super::SubregionOrigin;
-use super::combine::{CombineFields, RelationDir};
+use super::combine::{CombineFields, RelationDir, const_unification_error};
 
 use crate::traits::Obligation;
-use crate::ty::{self, Ty, TyCtxt};
+use crate::ty::{self, Ty, TyCtxt, InferConst};
 use crate::ty::TyVar;
 use crate::ty::fold::TypeFoldable;
 use crate::ty::relate::{Cause, Relate, RelateResult, TypeRelation};
+use crate::mir::interpret::ConstValue;
 use std::mem;
 
 /// Ensures `a` is made a subtype of `b`. Returns `a` on success.
@@ -133,6 +134,50 @@ impl<'combine, 'infcx, 'gcx, 'tcx> TypeRelation<'infcx, 'gcx, 'tcx>
         Ok(a)
     }
 
+    fn consts(
+        &mut self,
+        a: &'tcx ty::LazyConst<'tcx>,
+        b: &'tcx ty::LazyConst<'tcx>,
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        debug!("{}.consts({:?}, {:?})", self.tag(), a, b);
+        if a == b { return Ok(a); }
+
+        let infcx = self.fields.infcx;
+        let a = infcx.const_unification_table.borrow_mut().replace_if_possible(a);
+        let b = infcx.const_unification_table.borrow_mut().replace_if_possible(b);
+
+        // Consts can only be equal or unequal to each other: there's no subtyping
+        // relation, so we're just going to perform equating here instead.
+        let a_is_expected = self.a_is_expected();
+        if let (&ty::LazyConst::Evaluated(a_eval), &ty::LazyConst::Evaluated(b_eval)) = (a, b) {
+            match (a_eval.val, b_eval.val) {
+                (ConstValue::Infer(InferConst::Var(a_vid)),
+                 ConstValue::Infer(InferConst::Var(b_vid))) => {
+                    infcx.const_unification_table
+                        .borrow_mut()
+                        .unify_var_var(a_vid, b_vid)
+                        .map_err(|e| const_unification_error(a_is_expected, e))?;
+                    return Ok(a);
+                }
+
+                (ConstValue::Infer(InferConst::Var(a_id)), _) => {
+                    self.fields.infcx.unify_const_variable(a_is_expected, a_id, b)?;
+                    return Ok(a);
+                }
+
+                (_, ConstValue::Infer(InferConst::Var(b_id))) => {
+                    self.fields.infcx.unify_const_variable(!a_is_expected, b_id, a)?;
+                    return Ok(a);
+                }
+
+                _ => {}
+            }
+        }
+
+        self.fields.infcx.super_combine_consts(self, a, b)?;
+        Ok(a)
+    }
+
     fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
                   -> RelateResult<'tcx, ty::Binder<T>>
         where T: Relate<'tcx>
diff --git a/src/librustc/ty/_match.rs b/src/librustc/ty/_match.rs
index 07fa441bb80..fdc69561014 100644
--- a/src/librustc/ty/_match.rs
+++ b/src/librustc/ty/_match.rs
@@ -1,6 +1,7 @@
-use crate::ty::{self, Ty, TyCtxt};
-use crate::ty::error::TypeError;
+use crate::ty::{self, Ty, TyCtxt, InferConst};
+use crate::ty::error::{TypeError, ConstError};
 use crate::ty::relate::{self, Relate, TypeRelation, RelateResult};
+use crate::mir::interpret::ConstValue;
 
 /// A type "A" *matches* "B" if the fresh types in B could be
 /// substituted with values so as to make it equal to A. Matching is
@@ -78,6 +79,35 @@ impl<'a, 'gcx, 'tcx> TypeRelation<'a, 'gcx, 'tcx> for Match<'a, 'gcx, 'tcx> {
         }
     }
 
+    fn consts(
+        &mut self,
+        a: &'tcx ty::LazyConst<'tcx>,
+        b: &'tcx ty::LazyConst<'tcx>,
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        debug!("{}.consts({:?}, {:?})", self.tag(), a, b);
+        if a == b {
+            return Ok(a);
+        }
+
+        if let (&ty::LazyConst::Evaluated(a_eval), &ty::LazyConst::Evaluated(b_eval)) = (a, b) {
+            match (a_eval.val, b_eval.val) {
+                (_, ConstValue::Infer(InferConst::Fresh(_))) => {
+                    return Ok(a);
+                }
+
+                (ConstValue::Infer(_), _) | (_, ConstValue::Infer(_)) => {
+                    return Err(TypeError::ConstError(
+                        ConstError::Mismatch(relate::expected_found(self, &a, &b))
+                    ));
+                }
+
+                _ => {}
+            }
+        }
+
+        relate::super_relate_consts(self, a, b)
+    }
+
     fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
                   -> RelateResult<'tcx, ty::Binder<T>>
         where T: Relate<'tcx>
diff --git a/src/librustc_traits/chalk_context/resolvent_ops.rs b/src/librustc_traits/chalk_context/resolvent_ops.rs
index 4f5a4996db5..7fc05308754 100644
--- a/src/librustc_traits/chalk_context/resolvent_ops.rs
+++ b/src/librustc_traits/chalk_context/resolvent_ops.rs
@@ -16,9 +16,10 @@ use rustc::traits::{
     Environment,
     InEnvironment,
 };
-use rustc::ty::{self, Ty, TyCtxt};
+use rustc::ty::{self, Ty, TyCtxt, InferConst};
 use rustc::ty::subst::Kind;
 use rustc::ty::relate::{Relate, RelateResult, TypeRelation};
+use rustc::mir::interpret::ConstValue;
 use syntax_pos::DUMMY_SP;
 
 use super::{ChalkInferenceContext, ChalkArenas, ChalkExClause, ConstrainedSubst};
@@ -203,7 +204,7 @@ impl TypeRelation<'cx, 'gcx, 'tcx> for AnswerSubstitutor<'cx, 'gcx, 'tcx> {
     }
 
     fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
-        let b = self.infcx.shallow_resolve(b);
+        let b = self.infcx.shallow_resolve_type(b);
         debug!("AnswerSubstitutor::tys(a = {:?}, b = {:?})", a, b);
 
         if let &ty::Bound(debruijn, bound_ty) = &a.sty {
@@ -275,4 +276,44 @@ impl TypeRelation<'cx, 'gcx, 'tcx> for AnswerSubstitutor<'cx, 'gcx, 'tcx> {
 
         Ok(a)
     }
+
+    fn consts(
+        &mut self,
+        a: &'tcx ty::LazyConst<'tcx>,
+        b: &'tcx ty::LazyConst<'tcx>,
+    ) -> RelateResult<'tcx, &'tcx ty::LazyConst<'tcx>> {
+        if let ty::LazyConst::Evaluated(ty::Const {
+            val: ConstValue::Infer(InferConst::Canonical(debruijn, bound_ct)),
+            ..
+        }) = a {
+            if *debruijn == self.binder_index {
+                self.unify_free_answer_var(*bound_ct, b.into())?;
+                return Ok(b);
+            }
+        }
+
+        match (a, b) {
+            (
+                ty::LazyConst::Evaluated(ty::Const {
+                    val: ConstValue::Infer(InferConst::Canonical(a_debruijn, a_bound)),
+                    ..
+                }),
+                ty::LazyConst::Evaluated(ty::Const {
+                    val: ConstValue::Infer(InferConst::Canonical(b_debruijn, b_bound)),
+                    ..
+                }),
+            ) => {
+                assert_eq!(a_debruijn, b_debruijn);
+                assert_eq!(a_bound, b_bound);
+                Ok(a)
+            }
+
+            // Everything else should just be a perfect match as well,
+            // and we forbid inference variables.
+            _ => match ty::relate::super_relate_consts(self, a, b) {
+                Ok(ct) => Ok(ct),
+                Err(err) => bug!("const mismatch in `AnswerSubstitutor`: {}", err),
+            }
+        }
+    }
 }