diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve/canonicalize.rs')
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/canonicalize.rs | 428 |
1 files changed, 0 insertions, 428 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonicalize.rs deleted file mode 100644 index 377ae1b4e..000000000 --- a/compiler/rustc_trait_selection/src/solve/canonicalize.rs +++ /dev/null @@ -1,428 +0,0 @@ -use std::cmp::Ordering; - -use crate::infer::InferCtxt; -use rustc_middle::infer::canonical::Canonical; -use rustc_middle::infer::canonical::CanonicalTyVarKind; -use rustc_middle::infer::canonical::CanonicalVarInfo; -use rustc_middle::infer::canonical::CanonicalVarInfos; -use rustc_middle::infer::canonical::CanonicalVarKind; -use rustc_middle::ty::BoundRegionKind::BrAnon; -use rustc_middle::ty::BoundTyKind; -use rustc_middle::ty::TyCtxt; -use rustc_middle::ty::TypeVisitableExt; -use rustc_middle::ty::{self, Ty}; -use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable}; - -/// Whether we're canonicalizing a query input or the query response. -/// -/// When canonicalizing an input we're in the context of the caller -/// while canonicalizing the response happens in the context of the -/// query. -#[derive(Debug, Clone, Copy)] -pub enum CanonicalizeMode { - Input, - /// FIXME: We currently return region constraints referring to - /// placeholders and inference variables from a binder instantiated - /// inside of the query. - /// - /// In the long term we should eagerly deal with these constraints - /// inside of the query and only propagate constraints which are - /// actually nameable by the caller. - Response { - /// The highest universe nameable by the caller. - /// - /// All variables in a universe nameable by the caller get mapped - /// to the root universe in the response and then mapped back to - /// their correct universe when applying the query response in the - /// context of the caller. - /// - /// This doesn't work for universes created inside of the query so - /// we do remember their universe in the response. - max_input_universe: ty::UniverseIndex, - }, -} - -pub struct Canonicalizer<'a, 'tcx> { - infcx: &'a InferCtxt<'tcx>, - canonicalize_mode: CanonicalizeMode, - - variables: &'a mut Vec<ty::GenericArg<'tcx>>, - primitive_var_infos: Vec<CanonicalVarInfo<'tcx>>, - binder_index: ty::DebruijnIndex, -} - -impl<'a, 'tcx> Canonicalizer<'a, 'tcx> { - #[instrument(level = "debug", skip(infcx), ret)] - pub fn canonicalize<T: TypeFoldable<TyCtxt<'tcx>>>( - infcx: &'a InferCtxt<'tcx>, - canonicalize_mode: CanonicalizeMode, - variables: &'a mut Vec<ty::GenericArg<'tcx>>, - value: T, - ) -> Canonical<'tcx, T> { - let mut canonicalizer = Canonicalizer { - infcx, - canonicalize_mode, - - variables, - primitive_var_infos: Vec::new(), - binder_index: ty::INNERMOST, - }; - - let value = value.fold_with(&mut canonicalizer); - assert!(!value.has_infer()); - assert!(!value.has_placeholders()); - - let (max_universe, variables) = canonicalizer.finalize(); - - Canonical { max_universe, variables, value } - } - - fn finalize(self) -> (ty::UniverseIndex, CanonicalVarInfos<'tcx>) { - let mut var_infos = self.primitive_var_infos; - // 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 => {} - // 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 - // of the query. - CanonicalizeMode::Response { max_input_universe } => { - for var in var_infos.iter_mut() { - let uv = var.universe(); - let new_uv = ty::UniverseIndex::from( - uv.index().saturating_sub(max_input_universe.index()), - ); - *var = var.with_updated_universe(new_uv); - } - let max_universe = var_infos - .iter() - .map(|info| info.universe()) - .max() - .unwrap_or(ty::UniverseIndex::ROOT); - - let var_infos = self.infcx.tcx.mk_canonical_var_infos(&var_infos); - return (max_universe, var_infos); - } - } - - // Given a `var_infos` 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 only create a new universe if we would otherwise put a placeholder in - // the same compressed universe as an existential which cannot name it - // - // Let's walk through an example: - // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 0 - // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 1 - // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 1, next_orig_uv: 2 - // - var_infos: [E0, U1, E5, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 5 - // - var_infos: [E0, U1, E1, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 6 - // - var_infos: [E0, U1, E1, U1, E1, E2, U2], curr_compressed_uv: 2, next_orig_uv: - - // - // This algorithm runs in `O(n²)` where `n` is the number of different universe - // indices in the input. This should be fine as `n` is expected to be small. - let mut curr_compressed_uv = ty::UniverseIndex::ROOT; - let mut existential_in_new_uv = false; - let mut next_orig_uv = Some(ty::UniverseIndex::ROOT); - while let Some(orig_uv) = next_orig_uv.take() { - let mut update_uv = |var: &mut CanonicalVarInfo<'tcx>, orig_uv, is_existential| { - let uv = var.universe(); - match uv.cmp(&orig_uv) { - Ordering::Less => (), // Already updated - Ordering::Equal => { - if is_existential { - existential_in_new_uv = true; - } else if existential_in_new_uv { - // `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 = false; - } - - *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.map_or(true, |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_infos.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) - } - } - } - } - } - - for var in var_infos.iter_mut() { - if var.is_region() { - assert!(var.is_existential()); - *var = var.with_updated_universe(curr_compressed_uv); - } - } - - let var_infos = self.infcx.tcx.mk_canonical_var_infos(&var_infos); - (curr_compressed_uv, var_infos) - } -} - -impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { - fn interner(&self) -> TyCtxt<'tcx> { - self.infcx.tcx - } - - fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T> - where - T: TypeFoldable<TyCtxt<'tcx>>, - { - self.binder_index.shift_in(1); - let t = t.super_fold_with(self); - self.binder_index.shift_out(1); - t - } - - fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - if let ty::ReVar(vid) = *r { - let resolved_region = self - .infcx - .inner - .borrow_mut() - .unwrap_region_constraints() - .opportunistic_resolve_var(self.infcx.tcx, vid); - assert_eq!( - r, resolved_region, - "region var should have been resolved, {r} -> {resolved_region}" - ); - } - - let kind = match *r { - ty::ReLateBound(..) => return r, - - // We may encounter `ReStatic` in item signatures or the hidden type - // of an opaque. `ReErased` should only be encountered in the hidden - // type of an opaque for regions that are ignored for the purposes of - // captures. - // - // FIXME: We should investigate the perf implications of not uniquifying - // `ReErased`. We may be able to short-circuit registering region - // obligations if we encounter a `ReErased` on one side, for example. - ty::ReStatic | ty::ReErased => match self.canonicalize_mode { - CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), - CanonicalizeMode::Response { .. } => return r, - }, - - ty::ReFree(_) | ty::ReEarlyBound(_) => match self.canonicalize_mode { - CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), - CanonicalizeMode::Response { .. } => bug!("unexpected region in response: {r:?}"), - }, - - ty::RePlaceholder(placeholder) => match self.canonicalize_mode { - // We canonicalize placeholder regions as existentials in query inputs. - CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), - CanonicalizeMode::Response { max_input_universe } => { - // If we have a placeholder region inside of a query, it must be from - // a new universe. - if max_input_universe.can_name(placeholder.universe) { - bug!("new placeholder in universe {max_input_universe:?}: {r:?}"); - } - CanonicalVarKind::PlaceholderRegion(placeholder) - } - }, - - ty::ReVar(_) => match self.canonicalize_mode { - CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), - CanonicalizeMode::Response { .. } => { - CanonicalVarKind::Region(self.infcx.universe_of_region(r)) - } - }, - - ty::ReError(_) => return r, - }; - - let existing_bound_var = match self.canonicalize_mode { - CanonicalizeMode::Input => None, - CanonicalizeMode::Response { .. } => { - self.variables.iter().position(|&v| v == r.into()).map(ty::BoundVar::from) - } - }; - let var = existing_bound_var.unwrap_or_else(|| { - let var = ty::BoundVar::from(self.variables.len()); - self.variables.push(r.into()); - self.primitive_var_infos.push(CanonicalVarInfo { kind }); - var - }); - let br = ty::BoundRegion { var, kind: BrAnon }; - ty::Region::new_late_bound(self.interner(), self.binder_index, br) - } - - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - let kind = match *t.kind() { - ty::Infer(ty::TyVar(vid)) => { - assert_eq!(self.infcx.root_var(vid), vid, "ty vid should have been resolved"); - let Err(ui) = self.infcx.probe_ty_var(vid) else { - bug!("ty var should have been resolved: {t}"); - }; - CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)) - } - ty::Infer(ty::IntVar(vid)) => { - assert_eq!(self.infcx.opportunistic_resolve_int_var(vid), t); - CanonicalVarKind::Ty(CanonicalTyVarKind::Int) - } - ty::Infer(ty::FloatVar(vid)) => { - assert_eq!(self.infcx.opportunistic_resolve_float_var(vid), t); - CanonicalVarKind::Ty(CanonicalTyVarKind::Float) - } - ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { - bug!("fresh var during canonicalization: {t:?}") - } - ty::Placeholder(placeholder) => match self.canonicalize_mode { - CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder { - universe: placeholder.universe, - bound: ty::BoundTy { - var: ty::BoundVar::from_usize(self.variables.len()), - kind: ty::BoundTyKind::Anon, - }, - }), - CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder), - }, - ty::Param(_) => match self.canonicalize_mode { - CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder { - universe: ty::UniverseIndex::ROOT, - bound: ty::BoundTy { - var: ty::BoundVar::from_usize(self.variables.len()), - kind: ty::BoundTyKind::Anon, - }, - }), - CanonicalizeMode::Response { .. } => bug!("param ty in response: {t:?}"), - }, - ty::Bool - | ty::Char - | ty::Int(_) - | ty::Uint(_) - | ty::Float(_) - | ty::Adt(_, _) - | ty::Foreign(_) - | ty::Str - | ty::Array(_, _) - | ty::Slice(_) - | ty::RawPtr(_) - | ty::Ref(_, _, _) - | ty::FnDef(_, _) - | ty::FnPtr(_) - | ty::Dynamic(_, _, _) - | ty::Closure(_, _) - | ty::Coroutine(_, _, _) - | ty::CoroutineWitness(..) - | ty::Never - | ty::Tuple(_) - | ty::Alias(_, _) - | ty::Bound(_, _) - | ty::Error(_) => return t.super_fold_with(self), - }; - - let var = ty::BoundVar::from( - self.variables.iter().position(|&v| v == t.into()).unwrap_or_else(|| { - let var = self.variables.len(); - self.variables.push(t.into()); - self.primitive_var_infos.push(CanonicalVarInfo { kind }); - var - }), - ); - let bt = ty::BoundTy { var, kind: BoundTyKind::Anon }; - Ty::new_bound(self.infcx.tcx, self.binder_index, bt) - } - - fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { - let kind = match c.kind() { - ty::ConstKind::Infer(ty::InferConst::Var(vid)) => { - assert_eq!( - self.infcx.root_const_var(vid), - vid, - "const var should have been resolved" - ); - let Err(ui) = self.infcx.probe_const_var(vid) else { - bug!("const var should have been resolved"); - }; - // FIXME: we should fold this ty eventually - CanonicalVarKind::Const(ui, c.ty()) - } - ty::ConstKind::Infer(ty::InferConst::EffectVar(vid)) => { - assert_eq!( - self.infcx.root_effect_var(vid), - vid, - "effect var should have been resolved" - ); - let None = self.infcx.probe_effect_var(vid) else { - bug!("effect var should have been resolved"); - }; - CanonicalVarKind::Effect - } - ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => { - bug!("fresh var during canonicalization: {c:?}") - } - ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode { - CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst( - ty::Placeholder { - universe: placeholder.universe, - bound: ty::BoundVar::from(self.variables.len()), - }, - c.ty(), - ), - CanonicalizeMode::Response { .. } => { - CanonicalVarKind::PlaceholderConst(placeholder, c.ty()) - } - }, - ty::ConstKind::Param(_) => match self.canonicalize_mode { - CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst( - ty::Placeholder { - universe: ty::UniverseIndex::ROOT, - bound: ty::BoundVar::from(self.variables.len()), - }, - c.ty(), - ), - CanonicalizeMode::Response { .. } => bug!("param ty in response: {c:?}"), - }, - ty::ConstKind::Bound(_, _) - | ty::ConstKind::Unevaluated(_) - | ty::ConstKind::Value(_) - | ty::ConstKind::Error(_) - | ty::ConstKind::Expr(_) => return c.super_fold_with(self), - }; - - let var = ty::BoundVar::from( - self.variables.iter().position(|&v| v == c.into()).unwrap_or_else(|| { - let var = self.variables.len(); - self.variables.push(c.into()); - self.primitive_var_infos.push(CanonicalVarInfo { kind }); - var - }), - ); - ty::Const::new_bound(self.infcx.tcx, self.binder_index, var, c.ty()) - } -} |