diff options
Diffstat (limited to 'compiler')
| -rw-r--r-- | compiler/rustc_next_trait_solver/src/canonicalizer.rs | 152 |
1 files changed, 33 insertions, 119 deletions
diff --git a/compiler/rustc_next_trait_solver/src/canonicalizer.rs b/compiler/rustc_next_trait_solver/src/canonicalizer.rs index 47ed9e87244..a418aa82100 100644 --- a/compiler/rustc_next_trait_solver/src/canonicalizer.rs +++ b/compiler/rustc_next_trait_solver/src/canonicalizer.rs @@ -1,5 +1,3 @@ -use std::cmp::Ordering; - use rustc_type_ir::data_structures::{HashMap, ensure_sufficient_stack}; use rustc_type_ir::inherent::*; use rustc_type_ir::solve::{Goal, QueryInput}; @@ -266,11 +264,15 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { // See the rustc-dev-guide section about how we deal with universes // during canonicalization in the new solver. match self.canonicalize_mode { - // We try to deduplicate as many query calls as possible and hide - // all information which should not matter for the solver. - // - // For this we compress universes as much as possible. - CanonicalizeMode::Input { .. } => {} + // All placeholders and vars are canonicalized in the root universe. + CanonicalizeMode::Input { .. } => { + debug_assert!( + var_kinds.iter().all(|var| var.universe() == ty::UniverseIndex::ROOT), + "expected all vars to be canonicalized in root universe: {var_kinds:#?}" + ); + let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds); + (ty::UniverseIndex::ROOT, var_kinds) + } // When canonicalizing a response we map a universes already entered // by the caller to the root universe and only return useful universe // information for placeholders and inference variables created inside @@ -288,113 +290,10 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { .map(|kind| kind.universe()) .max() .unwrap_or(ty::UniverseIndex::ROOT); - let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds); - return (max_universe, var_kinds); + (max_universe, var_kinds) } } - - // Given a `var_kinds` with existentials `En` and universals `Un` in - // universes `n`, this algorithm compresses them in place so that: - // - // - the new universe indices are as small as possible - // - we create a new universe if we would otherwise - // 1. put existentials from a different universe into the same one - // 2. put a placeholder in the same universe as an existential which cannot name it - // - // Let's walk through an example: - // - var_kinds: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 0 - // - var_kinds: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 1 - // - var_kinds: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 1, next_orig_uv: 2 - // - var_kinds: [E0, U1, E5, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 5 - // - var_kinds: [E0, U1, E2, U1, E1, E6, U6], curr_compressed_uv: 2, next_orig_uv: 6 - // - var_kinds: [E0, U1, E1, U1, E1, E3, U3], curr_compressed_uv: 2, next_orig_uv: - - // - // This algorithm runs in `O(mn)` where `n` is the number of different universes and - // `m` the number of variables. This should be fine as both are expected to be small. - let mut curr_compressed_uv = ty::UniverseIndex::ROOT; - let mut existential_in_new_uv = None; - let mut next_orig_uv = Some(ty::UniverseIndex::ROOT); - while let Some(orig_uv) = next_orig_uv.take() { - let mut update_uv = |var: &mut CanonicalVarKind<I>, orig_uv, is_existential| { - let uv = var.universe(); - match uv.cmp(&orig_uv) { - Ordering::Less => (), // Already updated - Ordering::Equal => { - if is_existential { - if existential_in_new_uv.is_some_and(|uv| uv < orig_uv) { - // Condition 1. - // - // We already put an existential from a outer universe - // into the current compressed universe, so we need to - // create a new one. - curr_compressed_uv = curr_compressed_uv.next_universe(); - } - - // `curr_compressed_uv` will now contain an existential from - // `orig_uv`. Trying to canonicalizing an existential from - // a higher universe has to therefore use a new compressed - // universe. - existential_in_new_uv = Some(orig_uv); - } else if existential_in_new_uv.is_some() { - // Condition 2. - // - // `var` is a placeholder from a universe which is not nameable - // by an existential which we already put into the compressed - // universe `curr_compressed_uv`. We therefore have to create a - // new universe for `var`. - curr_compressed_uv = curr_compressed_uv.next_universe(); - existential_in_new_uv = None; - } - - *var = var.with_updated_universe(curr_compressed_uv); - } - Ordering::Greater => { - // We can ignore this variable in this iteration. We only look at - // universes which actually occur in the input for performance. - // - // For this we set `next_orig_uv` to the next smallest, not yet compressed, - // universe of the input. - if next_orig_uv.is_none_or(|curr_next_uv| uv.cannot_name(curr_next_uv)) { - next_orig_uv = Some(uv); - } - } - } - }; - - // For each universe which occurs in the input, we first iterate over all - // placeholders and then over all inference variables. - // - // Whenever we compress the universe of a placeholder, no existential with - // an already compressed universe can name that placeholder. - for is_existential in [false, true] { - for var in var_kinds.iter_mut() { - // We simply put all regions from the input into the highest - // compressed universe, so we only deal with them at the end. - if !var.is_region() { - if is_existential == var.is_existential() { - update_uv(var, orig_uv, is_existential) - } - } - } - } - } - - // We put all regions into a separate universe. - let mut first_region = true; - for var in var_kinds.iter_mut() { - if var.is_region() { - if first_region { - first_region = false; - curr_compressed_uv = curr_compressed_uv.next_universe(); - } - debug_assert!(var.is_existential()); - *var = var.with_updated_universe(curr_compressed_uv); - } - } - - let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds); - (curr_compressed_uv, var_kinds) } fn cached_fold_ty(&mut self, t: I::Ty) -> I::Ty { @@ -407,11 +306,18 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { "ty vid should have been resolved fully before canonicalization" ); - CanonicalVarKind::Ty(CanonicalTyVarKind::General( - self.delegate - .universe_of_ty(vid) - .unwrap_or_else(|| panic!("ty var should have been resolved: {t:?}")), - )) + match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => CanonicalVarKind::Ty( + CanonicalTyVarKind::General(ty::UniverseIndex::ROOT), + ), + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::Ty(CanonicalTyVarKind::General( + self.delegate.universe_of_ty(vid).unwrap_or_else(|| { + panic!("ty var should have been resolved: {t:?}") + }), + )) + } + } } ty::IntVar(vid) => { debug_assert_eq!( @@ -435,7 +341,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { }, ty::Placeholder(placeholder) => match self.canonicalize_mode { CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy( - PlaceholderLike::new_anon(placeholder.universe(), self.variables.len().into()), + PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), ), CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder), }, @@ -588,13 +494,21 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz c, "const vid should have been resolved fully before canonicalization" ); - CanonicalVarKind::Const(self.delegate.universe_of_ct(vid).unwrap()) + + match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => { + CanonicalVarKind::Const(ty::UniverseIndex::ROOT) + } + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::Const(self.delegate.universe_of_ct(vid).unwrap()) + } + } } ty::InferConst::Fresh(_) => todo!(), }, ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode { CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst( - PlaceholderLike::new_anon(placeholder.universe(), self.variables.len().into()), + PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()), ), CanonicalizeMode::Response { .. } => { CanonicalVarKind::PlaceholderConst(placeholder) |