diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src')
5 files changed, 81 insertions, 179 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs index c05c9961750..81be5c09164 100644 --- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs +++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs @@ -3,33 +3,27 @@ //! of our more general approach to "lazy normalization". //! //! This is done by first normalizing both sides of the goal, ending up in -//! either a concrete type, rigid projection, opaque, or an infer variable. +//! either a concrete type, rigid alias, or an infer variable. //! These are related further according to the rules below: //! -//! (1.) If we end up with a rigid projection and a rigid projection, then we -//! relate those projections structurally. +//! (1.) If we end up with two rigid aliases, then we relate them structurally. //! -//! (2.) If we end up with a rigid projection and an alias, then the opaque will -//! have its hidden type defined to be that rigid projection. -//! -//! (3.) If we end up with an opaque and an opaque, then we assemble two -//! candidates, one defining the LHS to be the hidden type of the RHS, and vice -//! versa. -//! -//! (4.) If we end up with an infer var and an opaque or rigid projection, then +//! (2.) If we end up with an infer var and a rigid alias, then //! we assign the alias to the infer var. //! -//! (5.) If we end up with an opaque and a rigid (non-projection) type, then we -//! define the hidden type of the opaque to be the rigid type. -//! -//! (6.) Otherwise, if we end with two rigid (non-projection) or infer types, +//! (3.) Otherwise, if we end with two rigid (non-projection) or infer types, //! relate them structurally. +//! +//! Subtle: when relating an opaque to another type, we emit a +//! `NormalizesTo(opaque, ?fresh_var)` goal when trying to normalize the opaque. +//! This nested goal starts out as ambiguous and does not actually define the opaque. +//! However, if `?fresh_var` ends up geteting equated to another type, we retry the +//! `NormalizesTo` goal, at which point the opaque is actually defined. use super::{EvalCtxt, GoalSource}; -use rustc_infer::infer::DefineOpaqueTypes; use rustc_infer::traits::query::NoSolution; use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; -use rustc_middle::ty; +use rustc_middle::ty::{self, Ty}; impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self), ret)] @@ -59,37 +53,32 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } - (Some(alias), None) => { + (Some(_), None) => { if rhs.is_infer() { self.relate(param_env, lhs, variance, rhs)?; self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } else if alias.is_opaque(tcx) { - // FIXME: This doesn't account for variance. - self.define_opaque(param_env, alias, rhs) } else { Err(NoSolution) } } - (None, Some(alias)) => { + (None, Some(_)) => { if lhs.is_infer() { self.relate(param_env, lhs, variance, rhs)?; self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } else if alias.is_opaque(tcx) { - // FIXME: This doesn't account for variance. - self.define_opaque(param_env, alias, lhs) } else { Err(NoSolution) } } (Some(alias_lhs), Some(alias_rhs)) => { - self.relate_rigid_alias_or_opaque(param_env, alias_lhs, variance, alias_rhs) + self.relate(param_env, alias_lhs, variance, alias_rhs)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } } // FIXME: This needs a name that reflects that it's okay to bottom-out with an inference var. - /// Normalize the `term` to equate it later. This does not define opaque types. + /// Normalize the `term` to equate it later. #[instrument(level = "debug", skip(self, param_env), ret)] fn try_normalize_term( &mut self, @@ -98,10 +87,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> Result<Option<ty::Term<'tcx>>, NoSolution> { match term.unpack() { ty::TermKind::Ty(ty) => { - // We do no define opaque types here but instead do so in `relate_rigid_alias_or_opaque`. - Ok(self - .try_normalize_ty_recur(param_env, DefineOpaqueTypes::No, 0, ty) - .map(Into::into)) + Ok(self.try_normalize_ty_recur(param_env, 0, ty).map(Into::into)) } ty::TermKind::Const(_) => { if let Some(alias) = term.to_alias_ty(self.tcx()) { @@ -119,51 +105,34 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } - fn define_opaque( + fn try_normalize_ty_recur( &mut self, param_env: ty::ParamEnv<'tcx>, - opaque: ty::AliasTy<'tcx>, - term: ty::Term<'tcx>, - ) -> QueryResult<'tcx> { - self.add_goal( - GoalSource::Misc, - Goal::new(self.tcx(), param_env, ty::NormalizesTo { alias: opaque, term }), - ); - self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } - - fn relate_rigid_alias_or_opaque( - &mut self, - param_env: ty::ParamEnv<'tcx>, - lhs: ty::AliasTy<'tcx>, - variance: ty::Variance, - rhs: ty::AliasTy<'tcx>, - ) -> QueryResult<'tcx> { - let tcx = self.tcx(); - let mut candidates = vec![]; - if lhs.is_opaque(tcx) { - candidates.extend( - self.probe_misc_candidate("define-lhs-opaque") - .enter(|ecx| ecx.define_opaque(param_env, lhs, rhs.to_ty(tcx).into())), - ); + depth: usize, + ty: Ty<'tcx>, + ) -> Option<Ty<'tcx>> { + if !self.tcx().recursion_limit().value_within_limit(depth) { + return None; } - if rhs.is_opaque(tcx) { - candidates.extend( - self.probe_misc_candidate("define-rhs-opaque") - .enter(|ecx| ecx.define_opaque(param_env, rhs, lhs.to_ty(tcx).into())), - ); - } - - candidates.extend(self.probe_misc_candidate("args-relate").enter(|ecx| { - ecx.relate(param_env, lhs, variance, rhs)?; - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - })); + let ty::Alias(_, alias) = *ty.kind() else { + return Some(ty); + }; - if let Some(result) = self.try_merge_responses(&candidates) { - Ok(result) - } else { - self.flounder(&candidates) + match self.commit_if_ok(|this| { + let normalized_ty = this.next_ty_infer(); + let normalizes_to_goal = Goal::new( + this.tcx(), + param_env, + ty::NormalizesTo { alias, term: normalized_ty.into() }, + ); + this.add_goal(GoalSource::Misc, normalizes_to_goal); + this.try_evaluate_added_goals()?; + let ty = this.resolve_vars_if_possible(normalized_ty); + Ok(this.try_normalize_ty_recur(param_env, depth + 1, ty)) + }) { + Ok(ty) => ty, + Err(NoSolution) => Some(ty), } } } diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index 6833d2ae330..733c415ead5 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -276,11 +276,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { &mut self, goal: Goal<'tcx, G>, ) -> Vec<Candidate<'tcx>> { - let Some(normalized_self_ty) = - self.try_normalize_ty(goal.param_env, goal.predicate.self_ty()) + let Ok(normalized_self_ty) = + self.structurally_normalize_ty(goal.param_env, goal.predicate.self_ty()) else { - debug!("overflow while evaluating self type"); - return self.forced_ambiguity(MaybeCause::Overflow); + return vec![]; }; if normalized_self_ty.is_ty_var() { @@ -635,19 +634,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { return; } - match self.try_normalize_ty(goal.param_env, alias_ty.self_ty()) { - // Recurse on the self type of the projection. - Some(next_self_ty) => { - self.assemble_alias_bound_candidates_recur(next_self_ty, goal, candidates); - } - // Bail if we overflow when normalizing, adding an ambiguous candidate. - None => { - if let Ok(result) = - self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW) - { - candidates.push(Candidate { source: CandidateSource::AliasBound, result }); - } + // Recurse on the self type of the projection. + match self.structurally_normalize_ty(goal.param_env, alias_ty.self_ty()) { + Ok(next_self_ty) => { + self.assemble_alias_bound_candidates_recur(next_self_ty, goal, candidates) } + Err(NoSolution) => {} } } @@ -857,19 +849,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let tcx = self.tcx(); let result = self.probe_misc_candidate("coherence unknowable").enter(|ecx| { let trait_ref = goal.predicate.trait_ref(tcx); - #[derive(Debug)] - struct Overflow; - let lazily_normalize_ty = |ty| match ecx.try_normalize_ty(goal.param_env, ty) { - Some(ty) => Ok(ty), - None => Err(Overflow), - }; + let lazily_normalize_ty = |ty| ecx.structurally_normalize_ty(goal.param_env, ty); - match coherence::trait_ref_is_knowable(tcx, trait_ref, lazily_normalize_ty) { - Err(Overflow) => { - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW) - } - Ok(Ok(())) => Err(NoSolution), - Ok(Err(_)) => { + match coherence::trait_ref_is_knowable(tcx, trait_ref, lazily_normalize_ty)? { + Ok(()) => Err(NoSolution), + Err(_) => { ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) } } diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index a7330136fe7..94a3cef8ad1 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -15,15 +15,13 @@ //! about it on zulip. use rustc_hir::def_id::DefId; use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues}; -use rustc_infer::infer::DefineOpaqueTypes; use rustc_infer::traits::query::NoSolution; use rustc_middle::infer::canonical::CanonicalVarInfos; use rustc_middle::traits::solve::{ CanonicalResponse, Certainty, ExternalConstraintsData, Goal, GoalSource, IsNormalizesToHack, QueryResult, Response, }; -use rustc_middle::traits::Reveal; -use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, UniverseIndex}; +use rustc_middle::ty::{self, AliasRelationDirection, Ty, TyCtxt, UniverseIndex}; use rustc_middle::ty::{ CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate, }; @@ -267,71 +265,32 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { Ok(self.make_ambiguous_response_no_constraints(maybe_cause)) } - /// Normalize a type when it is structually matched on. + /// Normalize a type for when it is structurally matched on. /// - /// In nearly all cases this function must be used before matching on a type. + /// This function is necessary in nearly all cases before matching on a type. /// Not doing so is likely to be incomplete and therefore unsound during /// coherence. - #[instrument(level = "debug", skip(self), ret)] - fn try_normalize_ty( - &mut self, - param_env: ty::ParamEnv<'tcx>, - ty: Ty<'tcx>, - ) -> Option<Ty<'tcx>> { - self.try_normalize_ty_recur(param_env, DefineOpaqueTypes::Yes, 0, ty) - } - - fn try_normalize_ty_recur( + fn structurally_normalize_ty( &mut self, param_env: ty::ParamEnv<'tcx>, - define_opaque_types: DefineOpaqueTypes, - depth: usize, ty: Ty<'tcx>, - ) -> Option<Ty<'tcx>> { - if !self.tcx().recursion_limit().value_within_limit(depth) { - return None; - } - - let ty::Alias(kind, alias) = *ty.kind() else { - return Some(ty); - }; - - // We do no always define opaque types eagerly to allow non-defining uses - // in the defining scope. However, if we can unify this opaque to an existing - // opaque, then we should attempt to eagerly reveal the opaque, and we fall - // through. - if let DefineOpaqueTypes::No = define_opaque_types - && let Reveal::UserFacing = param_env.reveal() - && let ty::Opaque = kind - && let Some(def_id) = alias.def_id.as_local() - && self.can_define_opaque_ty(def_id) - { - if self - .unify_existing_opaque_tys( - param_env, - OpaqueTypeKey { def_id, args: alias.args }, - self.next_ty_infer(), - ) - .is_empty() - { - return Some(ty); - } - } - - match self.commit_if_ok(|this| { - let normalized_ty = this.next_ty_infer(); - let normalizes_to_goal = Goal::new( - this.tcx(), + ) -> Result<Ty<'tcx>, NoSolution> { + if let ty::Alias(..) = ty.kind() { + let normalized_ty = self.next_ty_infer(); + let alias_relate_goal = Goal::new( + self.tcx(), param_env, - ty::NormalizesTo { alias, term: normalized_ty.into() }, + ty::PredicateKind::AliasRelate( + ty.into(), + normalized_ty.into(), + AliasRelationDirection::Equate, + ), ); - this.add_goal(GoalSource::Misc, normalizes_to_goal); - this.try_evaluate_added_goals()?; - let ty = this.resolve_vars_if_possible(normalized_ty); - Ok(this.try_normalize_ty_recur(param_env, define_opaque_types, depth + 1, ty)) - }) { - Ok(ty) => ty, - Err(NoSolution) => Some(ty), + self.add_goal(GoalSource::Misc, alias_relate_goal); + self.try_evaluate_added_goals()?; + Ok(self.resolve_vars_if_possible(normalized_ty)) + } else { + Ok(ty) } } } diff --git a/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs index b5d1aa06e4e..356c3776c04 100644 --- a/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs +++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs @@ -58,21 +58,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } - let expected = match self.try_normalize_ty(goal.param_env, expected) { - Some(ty) => { - if ty.is_ty_var() { - return self.evaluate_added_goals_and_make_canonical_response( - Certainty::AMBIGUOUS, - ); - } else { - ty - } - } - None => { - return self - .evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW); - } - }; + let expected = self.structurally_normalize_ty(goal.param_env, expected)?; + if expected.is_ty_var() { + return self + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + } // Otherwise, define a new opaque type self.insert_hidden_type(opaque_type_key, goal.param_env, expected)?; diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs index 7a466241bfa..eacdd9fde51 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -584,11 +584,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let a_ty = goal.predicate.self_ty(); // We need to normalize the b_ty since it's matched structurally // in the other functions below. - let b_ty = match ecx - .try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1)) - { - Some(b_ty) => b_ty, - None => return vec![misc_candidate(ecx, Certainty::OVERFLOW)], + let Ok(b_ty) = ecx.structurally_normalize_ty( + goal.param_env, + goal.predicate.trait_ref.args.type_at(1), + ) else { + return vec![]; }; let goal = goal.with(ecx.tcx(), (a_ty, b_ty)); |