diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/traits')
9 files changed, 785 insertions, 770 deletions
diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs index 0fd0fc001e7..fd981130af8 100644 --- a/compiler/rustc_trait_selection/src/traits/fulfill.rs +++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs @@ -1,5 +1,6 @@ use crate::infer::{InferCtxt, TyOrConstInferVar}; use crate::traits::error_reporting::TypeErrCtxtExt; +use crate::traits::normalize::normalize_with_depth_to; use rustc_data_structures::captures::Captures; use rustc_data_structures::obligation_forest::ProcessResult; use rustc_data_structures::obligation_forest::{Error, ForestObligation, Outcome}; @@ -312,7 +313,7 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { if obligation.predicate.has_projections() { let mut obligations = Vec::new(); - let predicate = crate::traits::project::normalize_with_depth_to( + let predicate = normalize_with_depth_to( &mut self.selcx, obligation.param_env, obligation.cause.clone(), diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs index bd993d308ac..9eec60ea06c 100644 --- a/compiler/rustc_trait_selection/src/traits/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/mod.rs @@ -9,6 +9,7 @@ mod engine; pub mod error_reporting; mod fulfill; pub mod misc; +pub mod normalize; mod object_safety; pub mod outlives_bounds; pub mod project; @@ -40,17 +41,15 @@ use rustc_span::Span; use std::fmt::Debug; use std::ops::ControlFlow; -pub(crate) use self::project::{needs_normalization, BoundVarReplacer, PlaceholderReplacer}; - pub use self::coherence::{add_placeholder_note, orphan_check, overlapping_impls}; pub use self::coherence::{OrphanCheckErr, OverlapResult}; pub use self::engine::{ObligationCtxt, TraitEngineExt}; pub use self::fulfill::{FulfillmentContext, PendingPredicateObligation}; +pub use self::normalize::NormalizeExt; pub use self::object_safety::astconv_object_safety_violations; pub use self::object_safety::is_vtable_safe_method; pub use self::object_safety::object_safety_violations_for_assoc_item; pub use self::object_safety::ObjectSafetyViolation; -pub use self::project::NormalizeExt; pub use self::project::{normalize_inherent_projection, normalize_projection_type}; pub use self::select::{EvaluationCache, SelectionCache, SelectionContext}; pub use self::select::{EvaluationResult, IntercrateAmbiguityCause, OverflowError}; @@ -68,6 +67,7 @@ pub use self::util::{ }; pub use self::util::{expand_trait_aliases, TraitAliasExpander}; pub use self::util::{get_vtable_index_of_object_method, impl_item_is_final, upcast_choices}; +pub use self::util::{with_replaced_escaping_bound_vars, BoundVarReplacer, PlaceholderReplacer}; pub use rustc_infer::traits::*; diff --git a/compiler/rustc_trait_selection/src/traits/normalize.rs b/compiler/rustc_trait_selection/src/traits/normalize.rs new file mode 100644 index 00000000000..0df6f36f115 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/normalize.rs @@ -0,0 +1,423 @@ +//! Deeply normalize types using the old trait solver. +use rustc_data_structures::stack::ensure_sufficient_stack; +use rustc_infer::infer::at::At; +use rustc_infer::infer::InferOk; +use rustc_infer::traits::PredicateObligation; +use rustc_infer::traits::{FulfillmentError, Normalized, Obligation, TraitEngine}; +use rustc_middle::traits::{ObligationCause, ObligationCauseCode, Reveal}; +use rustc_middle::ty::{self, Ty, TyCtxt, TypeFolder}; +use rustc_middle::ty::{TypeFoldable, TypeSuperFoldable, TypeVisitable, TypeVisitableExt}; + +use super::error_reporting::TypeErrCtxtExt; +use super::SelectionContext; +use super::{project, with_replaced_escaping_bound_vars, BoundVarReplacer, PlaceholderReplacer}; + +#[extension(pub trait NormalizeExt<'tcx>)] +impl<'tcx> At<'_, 'tcx> { + /// Normalize a value using the `AssocTypeNormalizer`. + /// + /// This normalization should be used when the type contains inference variables or the + /// projection may be fallible. + fn normalize<T: TypeFoldable<TyCtxt<'tcx>>>(&self, value: T) -> InferOk<'tcx, T> { + if self.infcx.next_trait_solver() { + InferOk { value, obligations: Vec::new() } + } else { + let mut selcx = SelectionContext::new(self.infcx); + let Normalized { value, obligations } = + normalize_with_depth(&mut selcx, self.param_env, self.cause.clone(), 0, value); + InferOk { value, obligations } + } + } + + /// Deeply normalizes `value`, replacing all aliases which can by normalized in + /// the current environment. In the new solver this errors in case normalization + /// fails or is ambiguous. This only normalizes opaque types with `Reveal::All`. + /// + /// In the old solver this simply uses `normalizes` and adds the nested obligations + /// to the `fulfill_cx`. This is necessary as we otherwise end up recomputing the + /// same goals in both a temporary and the shared context which negatively impacts + /// performance as these don't share caching. + /// + /// FIXME(-Znext-solver): This has the same behavior as `traits::fully_normalize` + /// in the new solver, but because of performance reasons, we currently reuse an + /// existing fulfillment context in the old solver. Once we also eagerly prove goals with + /// the old solver or have removed the old solver, remove `traits::fully_normalize` and + /// rename this function to `At::fully_normalize`. + fn deeply_normalize<T: TypeFoldable<TyCtxt<'tcx>>>( + self, + value: T, + fulfill_cx: &mut dyn TraitEngine<'tcx>, + ) -> Result<T, Vec<FulfillmentError<'tcx>>> { + if self.infcx.next_trait_solver() { + crate::solve::deeply_normalize(self, value) + } else { + let value = self + .normalize(value) + .into_value_registering_obligations(self.infcx, &mut *fulfill_cx); + let errors = fulfill_cx.select_where_possible(self.infcx); + let value = self.infcx.resolve_vars_if_possible(value); + if errors.is_empty() { Ok(value) } else { Err(errors) } + } + } +} + +/// As `normalize`, but with a custom depth. +pub(crate) fn normalize_with_depth<'a, 'b, 'tcx, T>( + selcx: &'a mut SelectionContext<'b, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + cause: ObligationCause<'tcx>, + depth: usize, + value: T, +) -> Normalized<'tcx, T> +where + T: TypeFoldable<TyCtxt<'tcx>>, +{ + let mut obligations = Vec::new(); + let value = normalize_with_depth_to(selcx, param_env, cause, depth, value, &mut obligations); + Normalized { value, obligations } +} + +#[instrument(level = "info", skip(selcx, param_env, cause, obligations))] +pub(crate) fn normalize_with_depth_to<'a, 'b, 'tcx, T>( + selcx: &'a mut SelectionContext<'b, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + cause: ObligationCause<'tcx>, + depth: usize, + value: T, + obligations: &mut Vec<PredicateObligation<'tcx>>, +) -> T +where + T: TypeFoldable<TyCtxt<'tcx>>, +{ + debug!(obligations.len = obligations.len()); + let mut normalizer = AssocTypeNormalizer::new(selcx, param_env, cause, depth, obligations); + let result = ensure_sufficient_stack(|| normalizer.fold(value)); + debug!(?result, obligations.len = normalizer.obligations.len()); + debug!(?normalizer.obligations,); + result +} + +pub(super) fn needs_normalization<'tcx, T: TypeVisitable<TyCtxt<'tcx>>>( + value: &T, + reveal: Reveal, +) -> bool { + match reveal { + Reveal::UserFacing => value.has_type_flags( + ty::TypeFlags::HAS_TY_PROJECTION + | ty::TypeFlags::HAS_TY_INHERENT + | ty::TypeFlags::HAS_CT_PROJECTION, + ), + Reveal::All => value.has_type_flags( + ty::TypeFlags::HAS_TY_PROJECTION + | ty::TypeFlags::HAS_TY_INHERENT + | ty::TypeFlags::HAS_TY_OPAQUE + | ty::TypeFlags::HAS_CT_PROJECTION, + ), + } +} + +struct AssocTypeNormalizer<'a, 'b, 'tcx> { + selcx: &'a mut SelectionContext<'b, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + cause: ObligationCause<'tcx>, + obligations: &'a mut Vec<PredicateObligation<'tcx>>, + depth: usize, + universes: Vec<Option<ty::UniverseIndex>>, +} + +impl<'a, 'b, 'tcx> AssocTypeNormalizer<'a, 'b, 'tcx> { + fn new( + selcx: &'a mut SelectionContext<'b, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + cause: ObligationCause<'tcx>, + depth: usize, + obligations: &'a mut Vec<PredicateObligation<'tcx>>, + ) -> AssocTypeNormalizer<'a, 'b, 'tcx> { + debug_assert!(!selcx.infcx.next_trait_solver()); + AssocTypeNormalizer { selcx, param_env, cause, obligations, depth, universes: vec![] } + } + + fn fold<T: TypeFoldable<TyCtxt<'tcx>>>(&mut self, value: T) -> T { + let value = self.selcx.infcx.resolve_vars_if_possible(value); + debug!(?value); + + assert!( + !value.has_escaping_bound_vars(), + "Normalizing {value:?} without wrapping in a `Binder`" + ); + + if !needs_normalization(&value, self.param_env.reveal()) { + value + } else { + value.fold_with(self) + } + } +} + +impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { + self.selcx.tcx() + } + + fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( + &mut self, + t: ty::Binder<'tcx, T>, + ) -> ty::Binder<'tcx, T> { + self.universes.push(None); + let t = t.super_fold_with(self); + self.universes.pop(); + t + } + + fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { + if !needs_normalization(&ty, self.param_env.reveal()) { + return ty; + } + + let (kind, data) = match *ty.kind() { + ty::Alias(kind, alias_ty) => (kind, alias_ty), + _ => return ty.super_fold_with(self), + }; + + // We try to be a little clever here as a performance optimization in + // cases where there are nested projections under binders. + // For example: + // ``` + // for<'a> fn(<T as Foo>::One<'a, Box<dyn Bar<'a, Item=<T as Foo>::Two<'a>>>>) + // ``` + // We normalize the args on the projection before the projecting, but + // if we're naive, we'll + // replace bound vars on inner, project inner, replace placeholders on inner, + // replace bound vars on outer, project outer, replace placeholders on outer + // + // However, if we're a bit more clever, we can replace the bound vars + // on the entire type before normalizing nested projections, meaning we + // replace bound vars on outer, project inner, + // project outer, replace placeholders on outer + // + // This is possible because the inner `'a` will already be a placeholder + // when we need to normalize the inner projection + // + // On the other hand, this does add a bit of complexity, since we only + // replace bound vars if the current type is a `Projection` and we need + // to make sure we don't forget to fold the args regardless. + + match kind { + ty::Opaque => { + // Only normalize `impl Trait` outside of type inference, usually in codegen. + match self.param_env.reveal() { + Reveal::UserFacing => ty.super_fold_with(self), + + Reveal::All => { + let recursion_limit = self.interner().recursion_limit(); + if !recursion_limit.value_within_limit(self.depth) { + self.selcx.infcx.err_ctxt().report_overflow_error( + &ty, + self.cause.span, + true, + |_| {}, + ); + } + + let args = data.args.fold_with(self); + let generic_ty = self.interner().type_of(data.def_id); + let concrete_ty = generic_ty.instantiate(self.interner(), args); + self.depth += 1; + let folded_ty = self.fold_ty(concrete_ty); + self.depth -= 1; + folded_ty + } + } + } + + ty::Projection if !data.has_escaping_bound_vars() => { + // This branch is *mostly* just an optimization: when we don't + // have escaping bound vars, we don't need to replace them with + // placeholders (see branch below). *Also*, we know that we can + // register an obligation to *later* project, since we know + // there won't be bound vars there. + let data = data.fold_with(self); + let normalized_ty = project::normalize_projection_type( + self.selcx, + self.param_env, + data, + self.cause.clone(), + self.depth, + self.obligations, + ); + debug!( + ?self.depth, + ?ty, + ?normalized_ty, + obligations.len = ?self.obligations.len(), + "AssocTypeNormalizer: normalized type" + ); + normalized_ty.ty().unwrap() + } + + ty::Projection => { + // If there are escaping bound vars, we temporarily replace the + // bound vars with placeholders. Note though, that in the case + // that we still can't project for whatever reason (e.g. self + // type isn't known enough), we *can't* register an obligation + // and return an inference variable (since then that obligation + // would have bound vars and that's a can of worms). Instead, + // we just give up and fall back to pretending like we never tried! + // + // Note: this isn't necessarily the final approach here; we may + // want to figure out how to register obligations with escaping vars + // or handle this some other way. + + let infcx = self.selcx.infcx; + let (data, mapped_regions, mapped_types, mapped_consts) = + BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data); + let data = data.fold_with(self); + let normalized_ty = project::opt_normalize_projection_type( + self.selcx, + self.param_env, + data, + self.cause.clone(), + self.depth, + self.obligations, + ) + .ok() + .flatten() + .map(|term| term.ty().unwrap()) + .map(|normalized_ty| { + PlaceholderReplacer::replace_placeholders( + infcx, + mapped_regions, + mapped_types, + mapped_consts, + &self.universes, + normalized_ty, + ) + }) + .unwrap_or_else(|| ty.super_fold_with(self)); + + debug!( + ?self.depth, + ?ty, + ?normalized_ty, + obligations.len = ?self.obligations.len(), + "AssocTypeNormalizer: normalized type" + ); + normalized_ty + } + ty::Weak => { + let recursion_limit = self.interner().recursion_limit(); + if !recursion_limit.value_within_limit(self.depth) { + self.selcx.infcx.err_ctxt().report_overflow_error( + &ty, + self.cause.span, + false, + |diag| { + diag.note(crate::fluent_generated::trait_selection_ty_alias_overflow); + }, + ); + } + + let infcx = self.selcx.infcx; + self.obligations.extend( + infcx.tcx.predicates_of(data.def_id).instantiate_own(infcx.tcx, data.args).map( + |(mut predicate, span)| { + if data.has_escaping_bound_vars() { + (predicate, ..) = BoundVarReplacer::replace_bound_vars( + infcx, + &mut self.universes, + predicate, + ); + } + let mut cause = self.cause.clone(); + cause.map_code(|code| { + ObligationCauseCode::TypeAlias(code, span, data.def_id) + }); + Obligation::new(infcx.tcx, cause, self.param_env, predicate) + }, + ), + ); + self.depth += 1; + let res = infcx + .tcx + .type_of(data.def_id) + .instantiate(infcx.tcx, data.args) + .fold_with(self); + self.depth -= 1; + res + } + + ty::Inherent if !data.has_escaping_bound_vars() => { + // This branch is *mostly* just an optimization: when we don't + // have escaping bound vars, we don't need to replace them with + // placeholders (see branch below). *Also*, we know that we can + // register an obligation to *later* project, since we know + // there won't be bound vars there. + + let data = data.fold_with(self); + + // FIXME(inherent_associated_types): Do we need to honor `self.eager_inference_replacement` + // here like `ty::Projection`? + project::normalize_inherent_projection( + self.selcx, + self.param_env, + data, + self.cause.clone(), + self.depth, + self.obligations, + ) + } + + ty::Inherent => { + let infcx = self.selcx.infcx; + let (data, mapped_regions, mapped_types, mapped_consts) = + BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data); + let data = data.fold_with(self); + let ty = project::normalize_inherent_projection( + self.selcx, + self.param_env, + data, + self.cause.clone(), + self.depth, + self.obligations, + ); + + PlaceholderReplacer::replace_placeholders( + infcx, + mapped_regions, + mapped_types, + mapped_consts, + &self.universes, + ty, + ) + } + } + } + + #[instrument(skip(self), level = "debug")] + fn fold_const(&mut self, constant: ty::Const<'tcx>) -> ty::Const<'tcx> { + let tcx = self.selcx.tcx(); + if tcx.features().generic_const_exprs + || !needs_normalization(&constant, self.param_env.reveal()) + { + constant + } else { + let constant = constant.super_fold_with(self); + debug!(?constant, ?self.param_env); + with_replaced_escaping_bound_vars( + self.selcx.infcx, + &mut self.universes, + constant, + |constant| constant.normalize(tcx, self.param_env), + ) + } + } + + #[inline] + fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { + if p.allow_normalization() && needs_normalization(&p, self.param_env.reveal()) { + p.super_fold_with(self) + } else { + p + } + } +} diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs index 908886a5b42..9c532ea4d8d 100644 --- a/compiler/rustc_trait_selection/src/traits/project.rs +++ b/compiler/rustc_trait_selection/src/traits/project.rs @@ -1,5 +1,7 @@ //! Code for projecting associated types out of trait references. +use std::ops::ControlFlow; + use super::check_args_compatible; use super::specialization_graph; use super::translate_args; @@ -18,8 +20,9 @@ use rustc_middle::traits::ImplSourceUserDefinedData; use crate::errors::InherentProjectionNormalizationOverflow; use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; -use crate::infer::{BoundRegionConversionTime, InferCtxt, InferOk}; -use crate::traits::error_reporting::TypeErrCtxtExt as _; +use crate::infer::{BoundRegionConversionTime, InferOk}; +use crate::traits::normalize::normalize_with_depth; +use crate::traits::normalize::normalize_with_depth_to; use crate::traits::query::evaluate_obligation::InferCtxtExt as _; use crate::traits::select::ProjectionMatchesProjection; use rustc_data_structures::sso::SsoHashSet; @@ -27,21 +30,14 @@ use rustc_data_structures::stack::ensure_sufficient_stack; use rustc_errors::ErrorGuaranteed; use rustc_hir::def::DefKind; use rustc_hir::lang_items::LangItem; -use rustc_infer::infer::at::At; use rustc_infer::infer::resolve::OpportunisticRegionResolver; use rustc_infer::infer::DefineOpaqueTypes; -use rustc_infer::traits::FulfillmentError; -use rustc_infer::traits::ObligationCauseCode; -use rustc_infer::traits::TraitEngine; use rustc_middle::traits::select::OverflowError; -use rustc_middle::ty::fold::{TypeFoldable, TypeFolder, TypeSuperFoldable}; +use rustc_middle::ty::fold::TypeFoldable; use rustc_middle::ty::visit::{MaxUniverse, TypeVisitable, TypeVisitableExt}; use rustc_middle::ty::{self, Term, ToPredicate, Ty, TyCtxt}; use rustc_span::symbol::sym; -use std::collections::BTreeMap; -use std::ops::ControlFlow; - pub use rustc_middle::traits::Reveal; pub type PolyProjectionObligation<'tcx> = Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>; @@ -52,55 +48,6 @@ pub type ProjectionTyObligation<'tcx> = Obligation<'tcx, ty::AliasTy<'tcx>>; pub(super) struct InProgress; -#[extension(pub trait NormalizeExt<'tcx>)] -impl<'tcx> At<'_, 'tcx> { - /// Normalize a value using the `AssocTypeNormalizer`. - /// - /// This normalization should be used when the type contains inference variables or the - /// projection may be fallible. - fn normalize<T: TypeFoldable<TyCtxt<'tcx>>>(&self, value: T) -> InferOk<'tcx, T> { - if self.infcx.next_trait_solver() { - InferOk { value, obligations: Vec::new() } - } else { - let mut selcx = SelectionContext::new(self.infcx); - let Normalized { value, obligations } = - normalize_with_depth(&mut selcx, self.param_env, self.cause.clone(), 0, value); - InferOk { value, obligations } - } - } - - /// Deeply normalizes `value`, replacing all aliases which can by normalized in - /// the current environment. In the new solver this errors in case normalization - /// fails or is ambiguous. This only normalizes opaque types with `Reveal::All`. - /// - /// In the old solver this simply uses `normalizes` and adds the nested obligations - /// to the `fulfill_cx`. This is necessary as we otherwise end up recomputing the - /// same goals in both a temporary and the shared context which negatively impacts - /// performance as these don't share caching. - /// - /// FIXME(-Znext-solver): This has the same behavior as `traits::fully_normalize` - /// in the new solver, but because of performance reasons, we currently reuse an - /// existing fulfillment context in the old solver. Once we also eagerly prove goals with - /// the old solver or have removed the old solver, remove `traits::fully_normalize` and - /// rename this function to `At::fully_normalize`. - fn deeply_normalize<T: TypeFoldable<TyCtxt<'tcx>>>( - self, - value: T, - fulfill_cx: &mut dyn TraitEngine<'tcx>, - ) -> Result<T, Vec<FulfillmentError<'tcx>>> { - if self.infcx.next_trait_solver() { - crate::solve::deeply_normalize(self, value) - } else { - let value = self - .normalize(value) - .into_value_registering_obligations(self.infcx, &mut *fulfill_cx); - let errors = fulfill_cx.select_where_possible(self.infcx); - let value = self.infcx.resolve_vars_if_possible(value); - if errors.is_empty() { Ok(value) } else { Err(errors) } - } - } -} - /// When attempting to resolve `<T as TraitRef>::Name` ... #[derive(Debug)] pub enum ProjectionError<'tcx> { @@ -338,700 +285,6 @@ fn project_and_unify_type<'cx, 'tcx>( } } -/// As `normalize`, but with a custom depth. -pub(crate) fn normalize_with_depth<'a, 'b, 'tcx, T>( - selcx: &'a mut SelectionContext<'b, 'tcx>, - param_env: ty::ParamEnv<'tcx>, - cause: ObligationCause<'tcx>, - depth: usize, - value: T, -) -> Normalized<'tcx, T> -where - T: TypeFoldable<TyCtxt<'tcx>>, -{ - let mut obligations = Vec::new(); - let value = normalize_with_depth_to(selcx, param_env, cause, depth, value, &mut obligations); - Normalized { value, obligations } -} - -#[instrument(level = "info", skip(selcx, param_env, cause, obligations))] -pub(crate) fn normalize_with_depth_to<'a, 'b, 'tcx, T>( - selcx: &'a mut SelectionContext<'b, 'tcx>, - param_env: ty::ParamEnv<'tcx>, - cause: ObligationCause<'tcx>, - depth: usize, - value: T, - obligations: &mut Vec<PredicateObligation<'tcx>>, -) -> T -where - T: TypeFoldable<TyCtxt<'tcx>>, -{ - debug!(obligations.len = obligations.len()); - let mut normalizer = AssocTypeNormalizer::new(selcx, param_env, cause, depth, obligations); - let result = ensure_sufficient_stack(|| normalizer.fold(value)); - debug!(?result, obligations.len = normalizer.obligations.len()); - debug!(?normalizer.obligations,); - result -} - -pub(crate) fn needs_normalization<'tcx, T: TypeVisitable<TyCtxt<'tcx>>>( - value: &T, - reveal: Reveal, -) -> bool { - match reveal { - Reveal::UserFacing => value.has_type_flags( - ty::TypeFlags::HAS_TY_PROJECTION - | ty::TypeFlags::HAS_TY_INHERENT - | ty::TypeFlags::HAS_CT_PROJECTION, - ), - Reveal::All => value.has_type_flags( - ty::TypeFlags::HAS_TY_PROJECTION - | ty::TypeFlags::HAS_TY_INHERENT - | ty::TypeFlags::HAS_TY_OPAQUE - | ty::TypeFlags::HAS_CT_PROJECTION, - ), - } -} - -struct AssocTypeNormalizer<'a, 'b, 'tcx> { - selcx: &'a mut SelectionContext<'b, 'tcx>, - param_env: ty::ParamEnv<'tcx>, - cause: ObligationCause<'tcx>, - obligations: &'a mut Vec<PredicateObligation<'tcx>>, - depth: usize, - universes: Vec<Option<ty::UniverseIndex>>, -} - -impl<'a, 'b, 'tcx> AssocTypeNormalizer<'a, 'b, 'tcx> { - fn new( - selcx: &'a mut SelectionContext<'b, 'tcx>, - param_env: ty::ParamEnv<'tcx>, - cause: ObligationCause<'tcx>, - depth: usize, - obligations: &'a mut Vec<PredicateObligation<'tcx>>, - ) -> AssocTypeNormalizer<'a, 'b, 'tcx> { - debug_assert!(!selcx.infcx.next_trait_solver()); - AssocTypeNormalizer { selcx, param_env, cause, obligations, depth, universes: vec![] } - } - - fn fold<T: TypeFoldable<TyCtxt<'tcx>>>(&mut self, value: T) -> T { - let value = self.selcx.infcx.resolve_vars_if_possible(value); - debug!(?value); - - assert!( - !value.has_escaping_bound_vars(), - "Normalizing {value:?} without wrapping in a `Binder`" - ); - - if !needs_normalization(&value, self.param_env.reveal()) { - value - } else { - value.fold_with(self) - } - } -} - -impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx> { - fn interner(&self) -> TyCtxt<'tcx> { - self.selcx.tcx() - } - - fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( - &mut self, - t: ty::Binder<'tcx, T>, - ) -> ty::Binder<'tcx, T> { - self.universes.push(None); - let t = t.super_fold_with(self); - self.universes.pop(); - t - } - - fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { - if !needs_normalization(&ty, self.param_env.reveal()) { - return ty; - } - - let (kind, data) = match *ty.kind() { - ty::Alias(kind, alias_ty) => (kind, alias_ty), - _ => return ty.super_fold_with(self), - }; - - // We try to be a little clever here as a performance optimization in - // cases where there are nested projections under binders. - // For example: - // ``` - // for<'a> fn(<T as Foo>::One<'a, Box<dyn Bar<'a, Item=<T as Foo>::Two<'a>>>>) - // ``` - // We normalize the args on the projection before the projecting, but - // if we're naive, we'll - // replace bound vars on inner, project inner, replace placeholders on inner, - // replace bound vars on outer, project outer, replace placeholders on outer - // - // However, if we're a bit more clever, we can replace the bound vars - // on the entire type before normalizing nested projections, meaning we - // replace bound vars on outer, project inner, - // project outer, replace placeholders on outer - // - // This is possible because the inner `'a` will already be a placeholder - // when we need to normalize the inner projection - // - // On the other hand, this does add a bit of complexity, since we only - // replace bound vars if the current type is a `Projection` and we need - // to make sure we don't forget to fold the args regardless. - - match kind { - ty::Opaque => { - // Only normalize `impl Trait` outside of type inference, usually in codegen. - match self.param_env.reveal() { - Reveal::UserFacing => ty.super_fold_with(self), - - Reveal::All => { - let recursion_limit = self.interner().recursion_limit(); - if !recursion_limit.value_within_limit(self.depth) { - self.selcx.infcx.err_ctxt().report_overflow_error( - &ty, - self.cause.span, - true, - |_| {}, - ); - } - - let args = data.args.fold_with(self); - let generic_ty = self.interner().type_of(data.def_id); - let concrete_ty = generic_ty.instantiate(self.interner(), args); - self.depth += 1; - let folded_ty = self.fold_ty(concrete_ty); - self.depth -= 1; - folded_ty - } - } - } - - ty::Projection if !data.has_escaping_bound_vars() => { - // This branch is *mostly* just an optimization: when we don't - // have escaping bound vars, we don't need to replace them with - // placeholders (see branch below). *Also*, we know that we can - // register an obligation to *later* project, since we know - // there won't be bound vars there. - let data = data.fold_with(self); - let normalized_ty = normalize_projection_type( - self.selcx, - self.param_env, - data, - self.cause.clone(), - self.depth, - self.obligations, - ); - debug!( - ?self.depth, - ?ty, - ?normalized_ty, - obligations.len = ?self.obligations.len(), - "AssocTypeNormalizer: normalized type" - ); - normalized_ty.ty().unwrap() - } - - ty::Projection => { - // If there are escaping bound vars, we temporarily replace the - // bound vars with placeholders. Note though, that in the case - // that we still can't project for whatever reason (e.g. self - // type isn't known enough), we *can't* register an obligation - // and return an inference variable (since then that obligation - // would have bound vars and that's a can of worms). Instead, - // we just give up and fall back to pretending like we never tried! - // - // Note: this isn't necessarily the final approach here; we may - // want to figure out how to register obligations with escaping vars - // or handle this some other way. - - let infcx = self.selcx.infcx; - let (data, mapped_regions, mapped_types, mapped_consts) = - BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data); - let data = data.fold_with(self); - let normalized_ty = opt_normalize_projection_type( - self.selcx, - self.param_env, - data, - self.cause.clone(), - self.depth, - self.obligations, - ) - .ok() - .flatten() - .map(|term| term.ty().unwrap()) - .map(|normalized_ty| { - PlaceholderReplacer::replace_placeholders( - infcx, - mapped_regions, - mapped_types, - mapped_consts, - &self.universes, - normalized_ty, - ) - }) - .unwrap_or_else(|| ty.super_fold_with(self)); - - debug!( - ?self.depth, - ?ty, - ?normalized_ty, - obligations.len = ?self.obligations.len(), - "AssocTypeNormalizer: normalized type" - ); - normalized_ty - } - ty::Weak => { - let recursion_limit = self.interner().recursion_limit(); - if !recursion_limit.value_within_limit(self.depth) { - self.selcx.infcx.err_ctxt().report_overflow_error( - &ty, - self.cause.span, - false, - |diag| { - diag.note(crate::fluent_generated::trait_selection_ty_alias_overflow); - }, - ); - } - - let infcx = self.selcx.infcx; - self.obligations.extend( - infcx.tcx.predicates_of(data.def_id).instantiate_own(infcx.tcx, data.args).map( - |(mut predicate, span)| { - if data.has_escaping_bound_vars() { - (predicate, ..) = BoundVarReplacer::replace_bound_vars( - infcx, - &mut self.universes, - predicate, - ); - } - let mut cause = self.cause.clone(); - cause.map_code(|code| { - ObligationCauseCode::TypeAlias(code, span, data.def_id) - }); - Obligation::new(infcx.tcx, cause, self.param_env, predicate) - }, - ), - ); - self.depth += 1; - let res = infcx - .tcx - .type_of(data.def_id) - .instantiate(infcx.tcx, data.args) - .fold_with(self); - self.depth -= 1; - res - } - - ty::Inherent if !data.has_escaping_bound_vars() => { - // This branch is *mostly* just an optimization: when we don't - // have escaping bound vars, we don't need to replace them with - // placeholders (see branch below). *Also*, we know that we can - // register an obligation to *later* project, since we know - // there won't be bound vars there. - - let data = data.fold_with(self); - - // FIXME(inherent_associated_types): Do we need to honor `self.eager_inference_replacement` - // here like `ty::Projection`? - normalize_inherent_projection( - self.selcx, - self.param_env, - data, - self.cause.clone(), - self.depth, - self.obligations, - ) - } - - ty::Inherent => { - let infcx = self.selcx.infcx; - let (data, mapped_regions, mapped_types, mapped_consts) = - BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data); - let data = data.fold_with(self); - let ty = normalize_inherent_projection( - self.selcx, - self.param_env, - data, - self.cause.clone(), - self.depth, - self.obligations, - ); - - PlaceholderReplacer::replace_placeholders( - infcx, - mapped_regions, - mapped_types, - mapped_consts, - &self.universes, - ty, - ) - } - } - } - - #[instrument(skip(self), level = "debug")] - fn fold_const(&mut self, constant: ty::Const<'tcx>) -> ty::Const<'tcx> { - let tcx = self.selcx.tcx(); - if tcx.features().generic_const_exprs - || !needs_normalization(&constant, self.param_env.reveal()) - { - constant - } else { - let constant = constant.super_fold_with(self); - debug!(?constant, ?self.param_env); - with_replaced_escaping_bound_vars( - self.selcx.infcx, - &mut self.universes, - constant, - |constant| constant.normalize(tcx, self.param_env), - ) - } - } - - #[inline] - fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { - if p.allow_normalization() && needs_normalization(&p, self.param_env.reveal()) { - p.super_fold_with(self) - } else { - p - } - } -} - -pub struct BoundVarReplacer<'me, 'tcx> { - infcx: &'me InferCtxt<'tcx>, - // These three maps track the bound variable that were replaced by placeholders. It might be - // nice to remove these since we already have the `kind` in the placeholder; we really just need - // the `var` (but we *could* bring that into scope if we were to track them as we pass them). - mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, - mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, - mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>, - // The current depth relative to *this* folding, *not* the entire normalization. In other words, - // the depth of binders we've passed here. - current_index: ty::DebruijnIndex, - // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy: - // we don't actually create a universe until we see a bound var we have to replace. - universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>, -} - -/// Executes `f` on `value` after replacing all escaping bound variables with placeholders -/// and then replaces these placeholders with the original bound variables in the result. -/// -/// In most places, bound variables should be replaced right when entering a binder, making -/// this function unnecessary. However, normalization currently does not do that, so we have -/// to do this lazily. -/// -/// You should not add any additional uses of this function, at least not without first -/// discussing it with t-types. -/// -/// FIXME(@lcnr): We may even consider experimenting with eagerly replacing bound vars during -/// normalization as well, at which point this function will be unnecessary and can be removed. -pub fn with_replaced_escaping_bound_vars< - 'a, - 'tcx, - T: TypeFoldable<TyCtxt<'tcx>>, - R: TypeFoldable<TyCtxt<'tcx>>, ->( - infcx: &'a InferCtxt<'tcx>, - universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>, - value: T, - f: impl FnOnce(T) -> R, -) -> R { - if value.has_escaping_bound_vars() { - let (value, mapped_regions, mapped_types, mapped_consts) = - BoundVarReplacer::replace_bound_vars(infcx, universe_indices, value); - let result = f(value); - PlaceholderReplacer::replace_placeholders( - infcx, - mapped_regions, - mapped_types, - mapped_consts, - universe_indices, - result, - ) - } else { - f(value) - } -} - -impl<'me, 'tcx> BoundVarReplacer<'me, 'tcx> { - /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that - /// use a binding level above `universe_indices.len()`, we fail. - pub fn replace_bound_vars<T: TypeFoldable<TyCtxt<'tcx>>>( - infcx: &'me InferCtxt<'tcx>, - universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>, - value: T, - ) -> ( - T, - BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, - BTreeMap<ty::PlaceholderType, ty::BoundTy>, - BTreeMap<ty::PlaceholderConst, ty::BoundVar>, - ) { - let mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion> = BTreeMap::new(); - let mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy> = BTreeMap::new(); - let mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar> = BTreeMap::new(); - - let mut replacer = BoundVarReplacer { - infcx, - mapped_regions, - mapped_types, - mapped_consts, - current_index: ty::INNERMOST, - universe_indices, - }; - - let value = value.fold_with(&mut replacer); - - (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts) - } - - fn universe_for(&mut self, debruijn: ty::DebruijnIndex) -> ty::UniverseIndex { - let infcx = self.infcx; - let index = - self.universe_indices.len() + self.current_index.as_usize() - debruijn.as_usize() - 1; - let universe = self.universe_indices[index].unwrap_or_else(|| { - for i in self.universe_indices.iter_mut().take(index + 1) { - *i = i.or_else(|| Some(infcx.create_next_universe())) - } - self.universe_indices[index].unwrap() - }); - universe - } -} - -impl<'tcx> TypeFolder<TyCtxt<'tcx>> for BoundVarReplacer<'_, 'tcx> { - fn interner(&self) -> TyCtxt<'tcx> { - self.infcx.tcx - } - - fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( - &mut self, - t: ty::Binder<'tcx, T>, - ) -> ty::Binder<'tcx, T> { - self.current_index.shift_in(1); - let t = t.super_fold_with(self); - self.current_index.shift_out(1); - t - } - - fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - match *r { - ty::ReBound(debruijn, _) - if debruijn.as_usize() - >= self.current_index.as_usize() + self.universe_indices.len() => - { - bug!( - "Bound vars {r:#?} outside of `self.universe_indices`: {:#?}", - self.universe_indices - ); - } - ty::ReBound(debruijn, br) if debruijn >= self.current_index => { - let universe = self.universe_for(debruijn); - let p = ty::PlaceholderRegion { universe, bound: br }; - self.mapped_regions.insert(p, br); - ty::Region::new_placeholder(self.infcx.tcx, p) - } - _ => r, - } - } - - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - match *t.kind() { - ty::Bound(debruijn, _) - if debruijn.as_usize() + 1 - > self.current_index.as_usize() + self.universe_indices.len() => - { - bug!( - "Bound vars {t:#?} outside of `self.universe_indices`: {:#?}", - self.universe_indices - ); - } - ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => { - let universe = self.universe_for(debruijn); - let p = ty::PlaceholderType { universe, bound: bound_ty }; - self.mapped_types.insert(p, bound_ty); - Ty::new_placeholder(self.infcx.tcx, p) - } - _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self), - _ => t, - } - } - - fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { - match ct.kind() { - ty::ConstKind::Bound(debruijn, _) - if debruijn.as_usize() + 1 - > self.current_index.as_usize() + self.universe_indices.len() => - { - bug!( - "Bound vars {ct:#?} outside of `self.universe_indices`: {:#?}", - self.universe_indices - ); - } - ty::ConstKind::Bound(debruijn, bound_const) if debruijn >= self.current_index => { - let universe = self.universe_for(debruijn); - let p = ty::PlaceholderConst { universe, bound: bound_const }; - self.mapped_consts.insert(p, bound_const); - ty::Const::new_placeholder(self.infcx.tcx, p, ct.ty()) - } - _ => ct.super_fold_with(self), - } - } - - fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { - if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p } - } -} - -/// The inverse of [`BoundVarReplacer`]: replaces placeholders with the bound vars from which they came. -pub struct PlaceholderReplacer<'me, 'tcx> { - infcx: &'me InferCtxt<'tcx>, - mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, - mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, - mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>, - universe_indices: &'me [Option<ty::UniverseIndex>], - current_index: ty::DebruijnIndex, -} - -impl<'me, 'tcx> PlaceholderReplacer<'me, 'tcx> { - pub fn replace_placeholders<T: TypeFoldable<TyCtxt<'tcx>>>( - infcx: &'me InferCtxt<'tcx>, - mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, - mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, - mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>, - universe_indices: &'me [Option<ty::UniverseIndex>], - value: T, - ) -> T { - let mut replacer = PlaceholderReplacer { - infcx, - mapped_regions, - mapped_types, - mapped_consts, - universe_indices, - current_index: ty::INNERMOST, - }; - value.fold_with(&mut replacer) - } -} - -impl<'tcx> TypeFolder<TyCtxt<'tcx>> for PlaceholderReplacer<'_, 'tcx> { - fn interner(&self) -> TyCtxt<'tcx> { - self.infcx.tcx - } - - fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( - &mut self, - t: ty::Binder<'tcx, T>, - ) -> ty::Binder<'tcx, T> { - if !t.has_placeholders() && !t.has_infer() { - return t; - } - self.current_index.shift_in(1); - let t = t.super_fold_with(self); - self.current_index.shift_out(1); - t - } - - fn fold_region(&mut self, r0: ty::Region<'tcx>) -> ty::Region<'tcx> { - let r1 = match *r0 { - ty::ReVar(vid) => self - .infcx - .inner - .borrow_mut() - .unwrap_region_constraints() - .opportunistic_resolve_var(self.infcx.tcx, vid), - _ => r0, - }; - - let r2 = match *r1 { - ty::RePlaceholder(p) => { - let replace_var = self.mapped_regions.get(&p); - match replace_var { - Some(replace_var) => { - let index = self - .universe_indices - .iter() - .position(|u| matches!(u, Some(pu) if *pu == p.universe)) - .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); - let db = ty::DebruijnIndex::from_usize( - self.universe_indices.len() - index + self.current_index.as_usize() - 1, - ); - ty::Region::new_bound(self.interner(), db, *replace_var) - } - None => r1, - } - } - _ => r1, - }; - - debug!(?r0, ?r1, ?r2, "fold_region"); - - r2 - } - - fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { - let ty = self.infcx.shallow_resolve(ty); - match *ty.kind() { - ty::Placeholder(p) => { - let replace_var = self.mapped_types.get(&p); - match replace_var { - Some(replace_var) => { - let index = self - .universe_indices - .iter() - .position(|u| matches!(u, Some(pu) if *pu == p.universe)) - .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); - let db = ty::DebruijnIndex::from_usize( - self.universe_indices.len() - index + self.current_index.as_usize() - 1, - ); - Ty::new_bound(self.infcx.tcx, db, *replace_var) - } - None => { - if ty.has_infer() { - ty.super_fold_with(self) - } else { - ty - } - } - } - } - - _ if ty.has_placeholders() || ty.has_infer() => ty.super_fold_with(self), - _ => ty, - } - } - - fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { - let ct = self.infcx.shallow_resolve(ct); - if let ty::ConstKind::Placeholder(p) = ct.kind() { - let replace_var = self.mapped_consts.get(&p); - match replace_var { - Some(replace_var) => { - let index = self - .universe_indices - .iter() - .position(|u| matches!(u, Some(pu) if *pu == p.universe)) - .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); - let db = ty::DebruijnIndex::from_usize( - self.universe_indices.len() - index + self.current_index.as_usize() - 1, - ); - ty::Const::new_bound(self.infcx.tcx, db, *replace_var, ct.ty()) - } - None => { - if ct.has_infer() { - ct.super_fold_with(self) - } else { - ct - } - } - } - } else { - ct.super_fold_with(self) - } - } -} - /// The guts of `normalize`: normalize a specific projection like `<T /// as Trait>::Item`. The result is always a type (and possibly /// additional obligations). If ambiguity arises, which implies that @@ -1076,7 +329,7 @@ pub fn normalize_projection_type<'a, 'b, 'tcx>( /// function takes an obligations vector and appends to it directly, which is /// slightly uglier but avoids the need for an extra short-lived allocation. #[instrument(level = "debug", skip(selcx, param_env, cause, obligations))] -fn opt_normalize_projection_type<'a, 'b, 'tcx>( +pub(super) fn opt_normalize_projection_type<'a, 'b, 'tcx>( selcx: &'a mut SelectionContext<'b, 'tcx>, param_env: ty::ParamEnv<'tcx>, projection_ty: ty::AliasTy<'tcx>, @@ -1180,14 +433,14 @@ fn opt_normalize_projection_type<'a, 'b, 'tcx>( let projected_term = selcx.infcx.resolve_vars_if_possible(projected_term); let mut result = if projected_term.has_projections() { - let mut normalizer = AssocTypeNormalizer::new( + let normalized_ty = normalize_with_depth_to( selcx, param_env, cause, depth + 1, + projected_term, &mut projected_obligations, ); - let normalized_ty = normalizer.fold(projected_term); Normalized { value: normalized_ty, obligations: projected_obligations } } else { diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs index 0f6c0abd280..26da065246d 100644 --- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs +++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs @@ -6,7 +6,8 @@ use crate::infer::at::At; use crate::infer::canonical::OriginalQueryValues; use crate::infer::{InferCtxt, InferOk}; use crate::traits::error_reporting::TypeErrCtxtExt; -use crate::traits::project::{needs_normalization, BoundVarReplacer, PlaceholderReplacer}; +use crate::traits::normalize::needs_normalization; +use crate::traits::{BoundVarReplacer, PlaceholderReplacer}; use crate::traits::{ObligationCause, PredicateObligation, Reveal}; use rustc_data_structures::sso::SsoHashMap; use rustc_data_structures::stack::ensure_sufficient_stack; @@ -335,7 +336,7 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> let constant = constant.try_super_fold_with(self)?; debug!(?constant, ?self.param_env); - Ok(crate::traits::project::with_replaced_escaping_bound_vars( + Ok(crate::traits::with_replaced_escaping_bound_vars( self.infcx, &mut self.universes, constant, diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs index e4a70c537d2..f76be876948 100644 --- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs +++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs @@ -18,7 +18,7 @@ use rustc_middle::ty::{ }; use rustc_span::def_id::DefId; -use crate::traits::project::{normalize_with_depth, normalize_with_depth_to}; +use crate::traits::normalize::{normalize_with_depth, normalize_with_depth_to}; use crate::traits::util::{self, closure_trait_ref_and_return_type}; use crate::traits::vtable::{ count_own_vtable_entries, prepare_vtable_segments, vtable_trait_first_method_offset, diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs index c2566f27c1f..65cb9e1c1f4 100644 --- a/compiler/rustc_trait_selection/src/traits/select/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs @@ -8,7 +8,6 @@ use self::SelectionCandidate::*; use super::coherence::{self, Conflict}; use super::const_evaluatable; use super::project; -use super::project::normalize_with_depth_to; use super::project::ProjectionTyObligation; use super::util; use super::util::closure_trait_ref_and_return_type; @@ -22,6 +21,8 @@ use super::{ use crate::infer::{InferCtxt, InferOk, TypeFreshener}; use crate::solve::InferCtxtSelectExt; use crate::traits::error_reporting::TypeErrCtxtExt; +use crate::traits::normalize::normalize_with_depth; +use crate::traits::normalize::normalize_with_depth_to; use crate::traits::project::ProjectAndUnifyResult; use crate::traits::project::ProjectionCacheKeyExt; use crate::traits::ProjectionCacheKey; @@ -1661,7 +1662,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } let Normalized { value: trait_bound, obligations: _ } = ensure_sufficient_stack(|| { - project::normalize_with_depth( + normalize_with_depth( self, obligation.param_env, obligation.cause.clone(), @@ -1717,7 +1718,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ); let infer_projection = if potentially_unnormalized_candidates { ensure_sufficient_stack(|| { - project::normalize_with_depth_to( + normalize_with_depth_to( self, obligation.param_env, obligation.cause.clone(), @@ -2382,7 +2383,7 @@ impl<'tcx> SelectionContext<'_, 'tcx> { let placeholder_ty = self.infcx.enter_forall_and_leak_universe(ty); let Normalized { value: normalized_ty, mut obligations } = ensure_sufficient_stack(|| { - project::normalize_with_depth( + normalize_with_depth( self, param_env, cause.clone(), @@ -2479,7 +2480,7 @@ impl<'tcx> SelectionContext<'_, 'tcx> { let Normalized { value: impl_trait_ref, obligations: mut nested_obligations } = ensure_sufficient_stack(|| { - project::normalize_with_depth( + normalize_with_depth( self, obligation.param_env, obligation.cause.clone(), diff --git a/compiler/rustc_trait_selection/src/traits/util.rs b/compiler/rustc_trait_selection/src/traits/util.rs index af172eb0713..23c86a2feef 100644 --- a/compiler/rustc_trait_selection/src/traits/util.rs +++ b/compiler/rustc_trait_selection/src/traits/util.rs @@ -1,11 +1,14 @@ +use std::collections::BTreeMap; + use super::NormalizeExt; use super::{ObligationCause, PredicateObligation, SelectionContext}; use rustc_data_structures::fx::FxHashSet; use rustc_errors::Diagnostic; use rustc_hir::def_id::DefId; -use rustc_infer::infer::InferOk; +use rustc_infer::infer::{InferCtxt, InferOk}; use rustc_middle::ty::GenericArgsRef; use rustc_middle::ty::{self, ImplSubject, ToPredicate, Ty, TyCtxt, TypeVisitableExt}; +use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable}; use rustc_span::Span; use smallvec::SmallVec; @@ -382,3 +385,336 @@ pub fn check_args_compatible<'tcx>( let args = &args[0..generics.count().min(args.len())]; check_args_compatible_inner(tcx, generics, args) } + +/// Executes `f` on `value` after replacing all escaping bound variables with placeholders +/// and then replaces these placeholders with the original bound variables in the result. +/// +/// In most places, bound variables should be replaced right when entering a binder, making +/// this function unnecessary. However, normalization currently does not do that, so we have +/// to do this lazily. +/// +/// You should not add any additional uses of this function, at least not without first +/// discussing it with t-types. +/// +/// FIXME(@lcnr): We may even consider experimenting with eagerly replacing bound vars during +/// normalization as well, at which point this function will be unnecessary and can be removed. +pub fn with_replaced_escaping_bound_vars< + 'a, + 'tcx, + T: TypeFoldable<TyCtxt<'tcx>>, + R: TypeFoldable<TyCtxt<'tcx>>, +>( + infcx: &'a InferCtxt<'tcx>, + universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>, + value: T, + f: impl FnOnce(T) -> R, +) -> R { + if value.has_escaping_bound_vars() { + let (value, mapped_regions, mapped_types, mapped_consts) = + BoundVarReplacer::replace_bound_vars(infcx, universe_indices, value); + let result = f(value); + PlaceholderReplacer::replace_placeholders( + infcx, + mapped_regions, + mapped_types, + mapped_consts, + universe_indices, + result, + ) + } else { + f(value) + } +} + +pub struct BoundVarReplacer<'me, 'tcx> { + infcx: &'me InferCtxt<'tcx>, + // These three maps track the bound variable that were replaced by placeholders. It might be + // nice to remove these since we already have the `kind` in the placeholder; we really just need + // the `var` (but we *could* bring that into scope if we were to track them as we pass them). + mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, + mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, + mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>, + // The current depth relative to *this* folding, *not* the entire normalization. In other words, + // the depth of binders we've passed here. + current_index: ty::DebruijnIndex, + // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy: + // we don't actually create a universe until we see a bound var we have to replace. + universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>, +} + +impl<'me, 'tcx> BoundVarReplacer<'me, 'tcx> { + /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that + /// use a binding level above `universe_indices.len()`, we fail. + pub fn replace_bound_vars<T: TypeFoldable<TyCtxt<'tcx>>>( + infcx: &'me InferCtxt<'tcx>, + universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>, + value: T, + ) -> ( + T, + BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, + BTreeMap<ty::PlaceholderType, ty::BoundTy>, + BTreeMap<ty::PlaceholderConst, ty::BoundVar>, + ) { + let mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion> = BTreeMap::new(); + let mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy> = BTreeMap::new(); + let mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar> = BTreeMap::new(); + + let mut replacer = BoundVarReplacer { + infcx, + mapped_regions, + mapped_types, + mapped_consts, + current_index: ty::INNERMOST, + universe_indices, + }; + + let value = value.fold_with(&mut replacer); + + (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts) + } + + fn universe_for(&mut self, debruijn: ty::DebruijnIndex) -> ty::UniverseIndex { + let infcx = self.infcx; + let index = + self.universe_indices.len() + self.current_index.as_usize() - debruijn.as_usize() - 1; + let universe = self.universe_indices[index].unwrap_or_else(|| { + for i in self.universe_indices.iter_mut().take(index + 1) { + *i = i.or_else(|| Some(infcx.create_next_universe())) + } + self.universe_indices[index].unwrap() + }); + universe + } +} + +impl<'tcx> TypeFolder<TyCtxt<'tcx>> for BoundVarReplacer<'_, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( + &mut self, + t: ty::Binder<'tcx, T>, + ) -> ty::Binder<'tcx, T> { + self.current_index.shift_in(1); + let t = t.super_fold_with(self); + self.current_index.shift_out(1); + t + } + + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + match *r { + ty::ReBound(debruijn, _) + if debruijn.as_usize() + >= self.current_index.as_usize() + self.universe_indices.len() => + { + bug!( + "Bound vars {r:#?} outside of `self.universe_indices`: {:#?}", + self.universe_indices + ); + } + ty::ReBound(debruijn, br) if debruijn >= self.current_index => { + let universe = self.universe_for(debruijn); + let p = ty::PlaceholderRegion { universe, bound: br }; + self.mapped_regions.insert(p, br); + ty::Region::new_placeholder(self.infcx.tcx, p) + } + _ => r, + } + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + match *t.kind() { + ty::Bound(debruijn, _) + if debruijn.as_usize() + 1 + > self.current_index.as_usize() + self.universe_indices.len() => + { + bug!( + "Bound vars {t:#?} outside of `self.universe_indices`: {:#?}", + self.universe_indices + ); + } + ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => { + let universe = self.universe_for(debruijn); + let p = ty::PlaceholderType { universe, bound: bound_ty }; + self.mapped_types.insert(p, bound_ty); + Ty::new_placeholder(self.infcx.tcx, p) + } + _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self), + _ => t, + } + } + + fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { + match ct.kind() { + ty::ConstKind::Bound(debruijn, _) + if debruijn.as_usize() + 1 + > self.current_index.as_usize() + self.universe_indices.len() => + { + bug!( + "Bound vars {ct:#?} outside of `self.universe_indices`: {:#?}", + self.universe_indices + ); + } + ty::ConstKind::Bound(debruijn, bound_const) if debruijn >= self.current_index => { + let universe = self.universe_for(debruijn); + let p = ty::PlaceholderConst { universe, bound: bound_const }; + self.mapped_consts.insert(p, bound_const); + ty::Const::new_placeholder(self.infcx.tcx, p, ct.ty()) + } + _ => ct.super_fold_with(self), + } + } + + fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { + if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p } + } +} + +/// The inverse of [`BoundVarReplacer`]: replaces placeholders with the bound vars from which they came. +pub struct PlaceholderReplacer<'me, 'tcx> { + infcx: &'me InferCtxt<'tcx>, + mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, + mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, + mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>, + universe_indices: &'me [Option<ty::UniverseIndex>], + current_index: ty::DebruijnIndex, +} + +impl<'me, 'tcx> PlaceholderReplacer<'me, 'tcx> { + pub fn replace_placeholders<T: TypeFoldable<TyCtxt<'tcx>>>( + infcx: &'me InferCtxt<'tcx>, + mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, + mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, + mapped_consts: BTreeMap<ty::PlaceholderConst, ty::BoundVar>, + universe_indices: &'me [Option<ty::UniverseIndex>], + value: T, + ) -> T { + let mut replacer = PlaceholderReplacer { + infcx, + mapped_regions, + mapped_types, + mapped_consts, + universe_indices, + current_index: ty::INNERMOST, + }; + value.fold_with(&mut replacer) + } +} + +impl<'tcx> TypeFolder<TyCtxt<'tcx>> for PlaceholderReplacer<'_, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( + &mut self, + t: ty::Binder<'tcx, T>, + ) -> ty::Binder<'tcx, T> { + if !t.has_placeholders() && !t.has_infer() { + return t; + } + self.current_index.shift_in(1); + let t = t.super_fold_with(self); + self.current_index.shift_out(1); + t + } + + fn fold_region(&mut self, r0: ty::Region<'tcx>) -> ty::Region<'tcx> { + let r1 = match *r0 { + ty::ReVar(vid) => self + .infcx + .inner + .borrow_mut() + .unwrap_region_constraints() + .opportunistic_resolve_var(self.infcx.tcx, vid), + _ => r0, + }; + + let r2 = match *r1 { + ty::RePlaceholder(p) => { + let replace_var = self.mapped_regions.get(&p); + match replace_var { + Some(replace_var) => { + let index = self + .universe_indices + .iter() + .position(|u| matches!(u, Some(pu) if *pu == p.universe)) + .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); + let db = ty::DebruijnIndex::from_usize( + self.universe_indices.len() - index + self.current_index.as_usize() - 1, + ); + ty::Region::new_bound(self.interner(), db, *replace_var) + } + None => r1, + } + } + _ => r1, + }; + + debug!(?r0, ?r1, ?r2, "fold_region"); + + r2 + } + + fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { + let ty = self.infcx.shallow_resolve(ty); + match *ty.kind() { + ty::Placeholder(p) => { + let replace_var = self.mapped_types.get(&p); + match replace_var { + Some(replace_var) => { + let index = self + .universe_indices + .iter() + .position(|u| matches!(u, Some(pu) if *pu == p.universe)) + .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); + let db = ty::DebruijnIndex::from_usize( + self.universe_indices.len() - index + self.current_index.as_usize() - 1, + ); + Ty::new_bound(self.infcx.tcx, db, *replace_var) + } + None => { + if ty.has_infer() { + ty.super_fold_with(self) + } else { + ty + } + } + } + } + + _ if ty.has_placeholders() || ty.has_infer() => ty.super_fold_with(self), + _ => ty, + } + } + + fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { + let ct = self.infcx.shallow_resolve(ct); + if let ty::ConstKind::Placeholder(p) = ct.kind() { + let replace_var = self.mapped_consts.get(&p); + match replace_var { + Some(replace_var) => { + let index = self + .universe_indices + .iter() + .position(|u| matches!(u, Some(pu) if *pu == p.universe)) + .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); + let db = ty::DebruijnIndex::from_usize( + self.universe_indices.len() - index + self.current_index.as_usize() - 1, + ); + ty::Const::new_bound(self.infcx.tcx, db, *replace_var, ct.ty()) + } + None => { + if ct.has_infer() { + ct.super_fold_with(self) + } else { + ct + } + } + } + } else { + ct.super_fold_with(self) + } + } +} diff --git a/compiler/rustc_trait_selection/src/traits/wf.rs b/compiler/rustc_trait_selection/src/traits/wf.rs index c727ef53d55..15059bc6613 100644 --- a/compiler/rustc_trait_selection/src/traits/wf.rs +++ b/compiler/rustc_trait_selection/src/traits/wf.rs @@ -313,7 +313,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> { // Don't normalize the whole obligation, the param env is either // already normalized, or we're currently normalizing the // param_env. Either way we should only normalize the predicate. - let normalized_predicate = traits::project::normalize_with_depth_to( + let normalized_predicate = traits::normalize::normalize_with_depth_to( &mut selcx, param_env, cause.clone(), |