From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/chalk-engine/src/normalize_deep.rs | 172 ++++++++++++++++++++++++++++++ 1 file changed, 172 insertions(+) create mode 100644 vendor/chalk-engine/src/normalize_deep.rs (limited to 'vendor/chalk-engine/src/normalize_deep.rs') diff --git a/vendor/chalk-engine/src/normalize_deep.rs b/vendor/chalk-engine/src/normalize_deep.rs new file mode 100644 index 000000000..0c4a01ccb --- /dev/null +++ b/vendor/chalk-engine/src/normalize_deep.rs @@ -0,0 +1,172 @@ +use chalk_ir::fold::shift::Shift; +use chalk_ir::fold::{Fold, Folder}; +use chalk_ir::interner::Interner; +use chalk_ir::*; +use chalk_solve::infer::InferenceTable; + +pub(crate) struct DeepNormalizer<'table, I: Interner> { + table: &'table mut InferenceTable, + interner: I, +} + +impl DeepNormalizer<'_, I> { + /// Given a value `value` with variables in it, replaces those variables + /// with their instantiated values (if any). Uninstantiated variables are + /// left as-is. + /// + /// This is mainly intended for getting final values to dump to + /// the user and its use should otherwise be avoided, particularly + /// given the possibility of snapshots and rollbacks. + /// + /// See also `InferenceTable::canonicalize`, which -- during real + /// processing -- is often used to capture the "current state" of + /// variables. + pub fn normalize_deep>( + table: &mut InferenceTable, + interner: I, + value: T, + ) -> T::Result { + value + .fold_with( + &mut DeepNormalizer { interner, table }, + DebruijnIndex::INNERMOST, + ) + .unwrap() + } +} + +impl Folder for DeepNormalizer<'_, I> { + type Error = NoSolution; + + fn as_dyn(&mut self) -> &mut dyn Folder { + self + } + + fn fold_inference_ty( + &mut self, + var: InferenceVar, + kind: TyVariableKind, + _outer_binder: DebruijnIndex, + ) -> Fallible> { + let interner = self.interner; + match self.table.probe_var(var) { + Some(ty) => Ok(ty + .assert_ty_ref(interner) + .clone() + .fold_with(self, DebruijnIndex::INNERMOST)? + .shifted_in(interner)), // FIXME shift + None => { + // Normalize all inference vars which have been unified into a + // single variable. Ena calls this the "root" variable. + Ok(self.table.inference_var_root(var).to_ty(interner, kind)) + } + } + } + + fn fold_inference_lifetime( + &mut self, + var: InferenceVar, + _outer_binder: DebruijnIndex, + ) -> Fallible> { + let interner = self.interner; + match self.table.probe_var(var) { + Some(l) => Ok(l + .assert_lifetime_ref(interner) + .clone() + .fold_with(self, DebruijnIndex::INNERMOST)? + .shifted_in(interner)), + None => Ok(var.to_lifetime(interner)), // FIXME shift + } + } + + fn fold_inference_const( + &mut self, + ty: Ty, + var: InferenceVar, + _outer_binder: DebruijnIndex, + ) -> Fallible> { + let interner = self.interner; + match self.table.probe_var(var) { + Some(c) => Ok(c + .assert_const_ref(interner) + .clone() + .fold_with(self, DebruijnIndex::INNERMOST)? + .shifted_in(interner)), + None => Ok(var.to_const(interner, ty)), // FIXME shift + } + } + + fn forbid_free_vars(&self) -> bool { + true + } + + fn interner(&self) -> I { + self.interner + } +} + +#[cfg(test)] +mod test { + use super::*; + use chalk_integration::interner::ChalkIr; + use chalk_integration::{arg, ty}; + + const U0: UniverseIndex = UniverseIndex { counter: 0 }; + + // We just use a vec of 20 `Invariant`, since this is zipped and no substs are + // longer than this + #[derive(Debug)] + struct TestDatabase; + impl UnificationDatabase for TestDatabase { + fn fn_def_variance(&self, _fn_def_id: FnDefId) -> Variances { + Variances::from_iter(ChalkIr, [Variance::Invariant; 20].iter().copied()) + } + + fn adt_variance(&self, _adt_id: AdtId) -> Variances { + Variances::from_iter(ChalkIr, [Variance::Invariant; 20].iter().copied()) + } + } + + #[test] + fn infer() { + let interner = ChalkIr; + let mut table: InferenceTable = InferenceTable::new(); + let environment0 = Environment::new(interner); + let a = table.new_variable(U0).to_ty(interner); + let b = table.new_variable(U0).to_ty(interner); + table + .relate( + interner, + &TestDatabase, + &environment0, + Variance::Invariant, + &a, + &ty!(apply (item 0) (expr b)), + ) + .unwrap(); + // a is unified to Adt<#0>(c), where 'c' is a new inference var + // created by the generalizer to generalize 'b'. It then unifies 'b' + // and 'c', and when we normalize them, they'll both be output as + // the same "root" variable. However, there are no guarantees for + // _which_ of 'b' and 'c' becomes the root. We need to normalize + // "b" too, then, to ensure we get a consistent result. + assert_eq!( + DeepNormalizer::normalize_deep(&mut table, interner, a.clone()), + ty!(apply (item 0) (expr DeepNormalizer::normalize_deep(&mut table, interner, b.clone()))), + ); + table + .relate( + interner, + &TestDatabase, + &environment0, + Variance::Invariant, + &b, + &ty!(apply (item 1)), + ) + .unwrap(); + assert_eq!( + DeepNormalizer::normalize_deep(&mut table, interner, a), + ty!(apply (item 0) (apply (item 1))) + ); + } +} -- cgit v1.2.3