vendor/chalk-engine/src/normalize_deep.rs

   1 use chalk_ir::fold::shift::Shift;
   2 use chalk_ir::fold::{Fold, Folder};
   3 use chalk_ir::interner::Interner;
   4 use chalk_ir::*;
   5 use chalk_solve::infer::InferenceTable;
   6
   7 pub(crate) struct DeepNormalizer<'table, 'i, I: Interner> {
   8     table: &'table mut InferenceTable<I>,
   9     interner: &'i I,
  10 }
  11
  12 impl<I: Interner> DeepNormalizer<'_, '_, I> {
  13     /// Given a value `value` with variables in it, replaces those variables
  14     /// with their instantiated values (if any). Uninstantiated variables are
  15     /// left as-is.
  16     ///
  17     /// This is mainly intended for getting final values to dump to
  18     /// the user and its use should otherwise be avoided, particularly
  19     /// given the possibility of snapshots and rollbacks.
  20     ///
  21     /// See also `InferenceTable::canonicalize`, which -- during real
  22     /// processing -- is often used to capture the "current state" of
  23     /// variables.
  24     pub fn normalize_deep<T: Fold<I>>(
  25         table: &mut InferenceTable<I>,
  26         interner: &I,
  27         value: T,
  28     ) -> T::Result {
  29         value
  30             .fold_with(
  31                 &mut DeepNormalizer { interner, table },
  32                 DebruijnIndex::INNERMOST,
  33             )
  34             .unwrap()
  35     }
  36 }
  37
  38 impl<'i, I: Interner> Folder<'i, I> for DeepNormalizer<'_, 'i, I>
  39 where
  40     I: 'i,
  41 {
  42     fn as_dyn(&mut self) -> &mut dyn Folder<'i, I> {
  43         self
  44     }
  45
  46     fn fold_inference_ty(
  47         &mut self,
  48         var: InferenceVar,
  49         kind: TyVariableKind,
  50         _outer_binder: DebruijnIndex,
  51     ) -> Fallible<Ty<I>> {
  52         let interner = self.interner;
  53         match self.table.probe_var(var) {
  54             Some(ty) => Ok(ty
  55                 .assert_ty_ref(interner)
  56                 .clone()
  57                 .fold_with(self, DebruijnIndex::INNERMOST)?
  58                 .shifted_in(interner)), // FIXME shift
  59             None => {
  60                 // Normalize all inference vars which have been unified into a
  61                 // single variable. Ena calls this the "root" variable.
  62                 Ok(self.table.inference_var_root(var).to_ty(interner, kind))
  63             }
  64         }
  65     }
  66
  67     fn fold_inference_lifetime(
  68         &mut self,
  69         var: InferenceVar,
  70         _outer_binder: DebruijnIndex,
  71     ) -> Fallible<Lifetime<I>> {
  72         let interner = self.interner;
  73         match self.table.probe_var(var) {
  74             Some(l) => Ok(l
  75                 .assert_lifetime_ref(interner)
  76                 .clone()
  77                 .fold_with(self, DebruijnIndex::INNERMOST)?
  78                 .shifted_in(interner)),
  79             None => Ok(var.to_lifetime(interner)), // FIXME shift
  80         }
  81     }
  82
  83     fn fold_inference_const(
  84         &mut self,
  85         ty: Ty<I>,
  86         var: InferenceVar,
  87         _outer_binder: DebruijnIndex,
  88     ) -> Fallible<Const<I>> {
  89         let interner = self.interner;
  90         match self.table.probe_var(var) {
  91             Some(c) => Ok(c
  92                 .assert_const_ref(interner)
  93                 .clone()
  94                 .fold_with(self, DebruijnIndex::INNERMOST)?
  95                 .shifted_in(interner)),
  96             None => Ok(var.to_const(interner, ty)), // FIXME shift
  97         }
  98     }
  99
 100     fn forbid_free_vars(&self) -> bool {
 101         true
 102     }
 103
 104     fn interner(&self) -> &'i I {
 105         self.interner
 106     }
 107 }
 108
 109 #[cfg(test)]
 110 mod test {
 111     use super::*;
 112     use chalk_integration::interner::ChalkIr;
 113     use chalk_integration::{arg, ty};
 114
 115     const U0: UniverseIndex = UniverseIndex { counter: 0 };
 116
 117     // We just use a vec of 20 `Invariant`, since this is zipped and no substs are
 118     // longer than this
 119     #[derive(Debug)]
 120     struct TestDatabase;
 121     impl UnificationDatabase<ChalkIr> for TestDatabase {
 122         fn fn_def_variance(&self, _fn_def_id: FnDefId<ChalkIr>) -> Variances<ChalkIr> {
 123             Variances::from_iter(&ChalkIr, [Variance::Invariant; 20].iter().copied())
 124         }
 125
 126         fn adt_variance(&self, _adt_id: AdtId<ChalkIr>) -> Variances<ChalkIr> {
 127             Variances::from_iter(&ChalkIr, [Variance::Invariant; 20].iter().copied())
 128         }
 129     }
 130
 131     #[test]
 132     fn infer() {
 133         let interner = &ChalkIr;
 134         let mut table: InferenceTable<ChalkIr> = InferenceTable::new();
 135         let environment0 = Environment::new(interner);
 136         let a = table.new_variable(U0).to_ty(interner);
 137         let b = table.new_variable(U0).to_ty(interner);
 138         table
 139             .relate(
 140                 interner,
 141                 &TestDatabase,
 142                 &environment0,
 143                 Variance::Invariant,
 144                 &a,
 145                 &ty!(apply (item 0) (expr b)),
 146             )
 147             .unwrap();
 148         // a is unified to Adt<#0>(c), where 'c' is a new inference var
 149         // created by the generalizer to generalize 'b'. It then unifies 'b'
 150         // and 'c', and when we normalize them, they'll both be output as
 151         // the same "root" variable. However, there are no guarantees for
 152         // _which_ of 'b' and 'c' becomes the root. We need to normalize
 153         // "b" too, then, to ensure we get a consistent result.
 154         assert_eq!(
 155             DeepNormalizer::normalize_deep(&mut table, interner, a.clone()),
 156             ty!(apply (item 0) (expr DeepNormalizer::normalize_deep(&mut table, interner, b.clone()))),
 157         );
 158         table
 159             .relate(
 160                 interner,
 161                 &TestDatabase,
 162                 &environment0,
 163                 Variance::Invariant,
 164                 &b,
 165                 &ty!(apply (item 1)),
 166             )
 167             .unwrap();
 168         assert_eq!(
 169             DeepNormalizer::normalize_deep(&mut table, interner, a),
 170             ty!(apply (item 0) (apply (item 1)))
 171         );
 172     }
 173 }