diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve')
20 files changed, 772 insertions, 1027 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs index f7031c5f4..626569fb4 100644 --- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs +++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs @@ -11,18 +11,12 @@ //! * bidirectional-normalizes-to: If `A` and `B` are both projections, and both //! may apply, then we can compute the "intersection" of both normalizes-to by //! performing them together. This is used specifically to resolve ambiguities. -use super::{EvalCtxt, SolverMode}; +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; -/// We may need to invert the alias relation direction if dealing an alias on the RHS. -#[derive(Debug)] -enum Invert { - No, - Yes, -} - impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self), ret)] pub(super) fn compute_alias_relate_goal( @@ -31,187 +25,128 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> QueryResult<'tcx> { let tcx = self.tcx(); let Goal { param_env, predicate: (lhs, rhs, direction) } = goal; - if lhs.is_infer() || rhs.is_infer() { - bug!( - "`AliasRelate` goal with an infer var on lhs or rhs which should have been instantiated" - ); - } - - match (lhs.to_alias_ty(tcx), rhs.to_alias_ty(tcx)) { - (None, None) => bug!("`AliasRelate` goal without an alias on either lhs or rhs"), - // RHS is not a projection, only way this is true is if LHS normalizes-to RHS - (Some(alias_lhs), None) => self.assemble_normalizes_to_candidate( - param_env, - alias_lhs, - rhs, - direction, - Invert::No, - ), + let Some(lhs) = self.try_normalize_term(param_env, lhs)? else { + return self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW); + }; - // LHS is not a projection, only way this is true is if RHS normalizes-to LHS - (None, Some(alias_rhs)) => self.assemble_normalizes_to_candidate( - param_env, - alias_rhs, - lhs, - direction, - Invert::Yes, - ), + let Some(rhs) = self.try_normalize_term(param_env, rhs)? else { + return self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW); + }; - (Some(alias_lhs), Some(alias_rhs)) => { - debug!("both sides are aliases"); + let variance = match direction { + ty::AliasRelationDirection::Equate => ty::Variance::Invariant, + ty::AliasRelationDirection::Subtype => ty::Variance::Covariant, + }; - let mut candidates = Vec::new(); - // LHS normalizes-to RHS - candidates.extend(self.assemble_normalizes_to_candidate( - param_env, - alias_lhs, - rhs, - direction, - Invert::No, - )); - // RHS normalizes-to RHS - candidates.extend(self.assemble_normalizes_to_candidate( - param_env, - alias_rhs, - lhs, - direction, - Invert::Yes, - )); - // Relate via args - candidates.extend( - self.assemble_subst_relate_candidate( - param_env, alias_lhs, alias_rhs, direction, - ), - ); - debug!(?candidates); + match (lhs.to_alias_ty(tcx), rhs.to_alias_ty(tcx)) { + (None, None) => { + self.relate(param_env, lhs, variance, rhs)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } - if let Some(merged) = self.try_merge_responses(&candidates) { - Ok(merged) + (Some(alias), 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) { + self.define_opaque(param_env, alias, rhs) } else { - // When relating two aliases and we have ambiguity, if both - // aliases can be normalized to something, we prefer - // "bidirectionally normalizing" both of them within the same - // candidate. - // - // See <https://github.com/rust-lang/trait-system-refactor-initiative/issues/25>. - // - // As this is incomplete, we must not do so during coherence. - match self.solver_mode() { - SolverMode::Normal => { - if let Ok(bidirectional_normalizes_to_response) = self - .assemble_bidirectional_normalizes_to_candidate( - param_env, lhs, rhs, direction, - ) - { - Ok(bidirectional_normalizes_to_response) - } else { - self.flounder(&candidates) - } - } - SolverMode::Coherence => self.flounder(&candidates), - } + Err(NoSolution) + } + } + (None, Some(alias)) => { + 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) { + self.define_opaque(param_env, alias, lhs) + } else { + Err(NoSolution) } } - } - } - #[instrument(level = "debug", skip(self), ret)] - fn assemble_normalizes_to_candidate( - &mut self, - param_env: ty::ParamEnv<'tcx>, - alias: ty::AliasTy<'tcx>, - other: ty::Term<'tcx>, - direction: ty::AliasRelationDirection, - invert: Invert, - ) -> QueryResult<'tcx> { - self.probe_misc_candidate("normalizes-to").enter(|ecx| { - ecx.normalizes_to_inner(param_env, alias, other, direction, invert)?; - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - }) + (Some(alias_lhs), Some(alias_rhs)) => { + self.relate_rigid_alias_or_opaque(param_env, alias_lhs, variance, alias_rhs) + } + } } - // Computes the normalizes-to branch, with side-effects. This must be performed - // in a probe in order to not taint the evaluation context. - fn normalizes_to_inner( + /// Normalize the `term` to equate it later. This does not define opaque types. + #[instrument(level = "debug", skip(self, param_env), ret)] + fn try_normalize_term( &mut self, param_env: ty::ParamEnv<'tcx>, - alias: ty::AliasTy<'tcx>, - other: ty::Term<'tcx>, - direction: ty::AliasRelationDirection, - invert: Invert, - ) -> Result<(), NoSolution> { - let other = match direction { - // This is purely an optimization. No need to instantiate a new - // infer var and equate the RHS to it. - ty::AliasRelationDirection::Equate => other, - - // Instantiate an infer var and subtype our RHS to it, so that we - // properly represent a subtype relation between the LHS and RHS - // of the goal. - ty::AliasRelationDirection::Subtype => { - let fresh = self.next_term_infer_of_kind(other); - let (sub, sup) = match invert { - Invert::No => (fresh, other), - Invert::Yes => (other, fresh), - }; - self.sub(param_env, sub, sup)?; - fresh + term: ty::Term<'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)) } - }; - self.add_goal(Goal::new( - self.tcx(), - param_env, - ty::ProjectionPredicate { projection_ty: alias, term: other }, - )); - - Ok(()) + ty::TermKind::Const(_) => { + if let Some(alias) = term.to_alias_ty(self.tcx()) { + let term = self.next_term_infer_of_kind(term); + self.add_goal( + GoalSource::Misc, + Goal::new(self.tcx(), param_env, ty::NormalizesTo { alias, term }), + ); + self.try_evaluate_added_goals()?; + Ok(Some(self.resolve_vars_if_possible(term))) + } else { + Ok(Some(term)) + } + } + } } - fn assemble_subst_relate_candidate( + fn define_opaque( &mut self, param_env: ty::ParamEnv<'tcx>, - alias_lhs: ty::AliasTy<'tcx>, - alias_rhs: ty::AliasTy<'tcx>, - direction: ty::AliasRelationDirection, + opaque: ty::AliasTy<'tcx>, + term: ty::Term<'tcx>, ) -> QueryResult<'tcx> { - self.probe_misc_candidate("args relate").enter(|ecx| { - match direction { - ty::AliasRelationDirection::Equate => { - ecx.eq(param_env, alias_lhs, alias_rhs)?; - } - ty::AliasRelationDirection::Subtype => { - ecx.sub(param_env, alias_lhs, alias_rhs)?; - } - } - - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - }) + 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 assemble_bidirectional_normalizes_to_candidate( + fn relate_rigid_alias_or_opaque( &mut self, param_env: ty::ParamEnv<'tcx>, - lhs: ty::Term<'tcx>, - rhs: ty::Term<'tcx>, - direction: ty::AliasRelationDirection, + lhs: ty::AliasTy<'tcx>, + variance: ty::Variance, + rhs: ty::AliasTy<'tcx>, ) -> QueryResult<'tcx> { - self.probe_misc_candidate("bidir normalizes-to").enter(|ecx| { - ecx.normalizes_to_inner( - param_env, - lhs.to_alias_ty(ecx.tcx()).unwrap(), - rhs, - direction, - Invert::No, - )?; - ecx.normalizes_to_inner( - param_env, - rhs.to_alias_ty(ecx.tcx()).unwrap(), - lhs, - direction, - Invert::Yes, - )?; + 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())), + ); + } + + 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) - }) + })); + + if let Some(result) = self.try_merge_responses(&candidates) { + Ok(result) + } else { + self.flounder(&candidates) + } } } diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index 27d2bdead..81a766f24 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -1,6 +1,7 @@ //! Code shared by trait and projection goals for candidate assembly. use super::{EvalCtxt, SolverMode}; +use crate::solve::GoalSource; use crate::traits::coherence; use rustc_hir::def_id::DefId; use rustc_infer::traits::query::NoSolution; @@ -37,8 +38,6 @@ pub(super) trait GoalKind<'tcx>: fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx>; - fn polarity(self) -> ty::ImplPolarity; - fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self; fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId; @@ -64,7 +63,9 @@ pub(super) trait GoalKind<'tcx>: requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>, ) -> QueryResult<'tcx> { Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { - ecx.add_goals(requirements); + // FIXME(-Znext-solver=coinductive): check whether this should be + // `GoalSource::ImplWhereBound` for any caller. + ecx.add_goals(GoalSource::Misc, requirements); ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -96,12 +97,16 @@ pub(super) trait GoalKind<'tcx>: let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { bug!("expected object type in `consider_object_bound_candidate`"); }; - ecx.add_goals(structural_traits::predicates_for_object_candidate( - &ecx, - goal.param_env, - goal.predicate.trait_ref(tcx), - bounds, - )); + // FIXME(-Znext-solver=coinductive): Should this be `GoalSource::ImplWhereBound`? + ecx.add_goals( + GoalSource::Misc, + structural_traits::predicates_for_object_candidate( + ecx, + goal.param_env, + goal.predicate.trait_ref(tcx), + bounds, + ), + ); ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -110,7 +115,7 @@ pub(super) trait GoalKind<'tcx>: ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, impl_def_id: DefId, - ) -> QueryResult<'tcx>; + ) -> Result<Candidate<'tcx>, NoSolution>; /// If the predicate contained an error, we want to avoid emitting unnecessary trait /// errors but still want to emit errors for other trait goals. We have some special @@ -209,6 +214,11 @@ pub(super) trait GoalKind<'tcx>: goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; + fn consider_builtin_async_iterator_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; + /// A coroutine (that doesn't come from an `async` or `gen` desugaring) is known to /// implement `Coroutine<R, Yield = Y, Return = O>`, given the resume, yield, /// and return types of the coroutine computed during type-checking. @@ -263,7 +273,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> Vec<Candidate<'tcx>> { debug_assert_eq!(goal, self.resolve_vars_if_possible(goal)); if let Some(ambig) = self.assemble_self_ty_infer_ambiguity_response(goal) { - return ambig; + return vec![ambig]; } let mut candidates = self.assemble_candidates_via_self_ty(goal, 0); @@ -288,15 +298,20 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { fn assemble_self_ty_infer_ambiguity_response<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, - ) -> Option<Vec<Candidate<'tcx>>> { - goal.predicate.self_ty().is_ty_var().then(|| { - vec![Candidate { - source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), - result: self - .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) - .unwrap(), - }] - }) + ) -> Option<Candidate<'tcx>> { + if goal.predicate.self_ty().is_ty_var() { + debug!("adding self_ty_infer_ambiguity_response"); + let source = CandidateSource::BuiltinImpl(BuiltinImplSource::Misc); + let result = self + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + .unwrap(); + let mut dummy_probe = self.inspect.new_probe(); + dummy_probe.probe_kind(ProbeKind::TraitCandidate { source, result: Ok(result) }); + self.inspect.finish_probe(dummy_probe); + Some(Candidate { source, result }) + } else { + None + } } /// Assemble candidates which apply to the self type. This only looks at candidate which @@ -310,7 +325,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> Vec<Candidate<'tcx>> { debug_assert_eq!(goal, self.resolve_vars_if_possible(goal)); if let Some(ambig) = self.assemble_self_ty_infer_ambiguity_response(goal) { - return ambig; + return vec![ambig]; } let mut candidates = Vec::new(); @@ -349,16 +364,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { num_steps: usize, ) { let tcx = self.tcx(); - let &ty::Alias(_, projection_ty) = goal.predicate.self_ty().kind() else { return }; + let &ty::Alias(_, alias) = goal.predicate.self_ty().kind() else { return }; candidates.extend(self.probe(|_| ProbeKind::NormalizedSelfTyAssembly).enter(|ecx| { - if num_steps < ecx.local_overflow_limit() { + if tcx.recursion_limit().value_within_limit(num_steps) { let normalized_ty = ecx.next_ty_infer(); - let normalizes_to_goal = goal.with( - tcx, - ty::ProjectionPredicate { projection_ty, term: normalized_ty.into() }, - ); - ecx.add_goal(normalizes_to_goal); + let normalizes_to_goal = + goal.with(tcx, ty::NormalizesTo { alias, term: normalized_ty.into() }); + ecx.add_goal(GoalSource::Misc, normalizes_to_goal); if let Err(NoSolution) = ecx.try_evaluate_added_goals() { debug!("self type normalization failed"); return vec![]; @@ -395,8 +408,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if let Some(impls_for_type) = trait_impls.non_blanket_impls().get(&simp) { for &impl_def_id in impls_for_type { match G::consider_impl_candidate(self, goal, impl_def_id) { - Ok(result) => candidates - .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }), + Ok(candidate) => candidates.push(candidate), Err(NoSolution) => (), } } @@ -488,6 +500,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } + #[instrument(level = "debug", skip_all)] fn assemble_unsize_to_dyn_candidate<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, @@ -505,6 +518,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } + #[instrument(level = "debug", skip_all)] fn assemble_blanket_impl_candidates<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, @@ -514,8 +528,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let trait_impls = tcx.trait_impls_of(goal.predicate.trait_def_id(tcx)); for &impl_def_id in trait_impls.blanket_impls() { match G::consider_impl_candidate(self, goal, impl_def_id) { - Ok(result) => candidates - .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }), + Ok(candidate) => candidates.push(candidate), Err(NoSolution) => (), } } @@ -564,6 +577,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { G::consider_builtin_future_candidate(self, goal) } else if lang_items.iterator_trait() == Some(trait_def_id) { G::consider_builtin_iterator_candidate(self, goal) + } else if lang_items.async_iterator_trait() == Some(trait_def_id) { + G::consider_builtin_async_iterator_candidate(self, goal) } else if lang_items.coroutine_trait() == Some(trait_def_id) { G::consider_builtin_coroutine_candidate(self, goal) } else if lang_items.discriminant_kind_trait() == Some(trait_def_id) { @@ -864,23 +879,18 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let result = self.probe_misc_candidate("coherence unknowable").enter(|ecx| { let trait_ref = goal.predicate.trait_ref(tcx); - #[derive(Debug)] - enum FailureKind { - Overflow, - NoSolution(NoSolution), - } + struct Overflow; let lazily_normalize_ty = |ty| match ecx.try_normalize_ty(goal.param_env, ty) { - Ok(Some(ty)) => Ok(ty), - Ok(None) => Err(FailureKind::Overflow), - Err(e) => Err(FailureKind::NoSolution(e)), + Some(ty) => Ok(ty), + None => Err(Overflow), }; match coherence::trait_ref_is_knowable(tcx, trait_ref, lazily_normalize_ty) { - Err(FailureKind::Overflow) => { + Err(Overflow) => { ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW) } - Err(FailureKind::NoSolution(NoSolution)) | Ok(Ok(())) => Err(NoSolution), + Ok(Ok(())) => Err(NoSolution), Ok(Err(_)) => { ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) } diff --git a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs index 839968b25..f442e2a08 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs @@ -50,14 +50,14 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>( ty::Array(element_ty, _) | ty::Slice(element_ty) => Ok(vec![element_ty]), - ty::Tuple(ref tys) => { + ty::Tuple(tys) => { // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet Ok(tys.iter().collect()) } - ty::Closure(_, ref args) => Ok(vec![args.as_closure().tupled_upvars_ty()]), + ty::Closure(_, args) => Ok(vec![args.as_closure().tupled_upvars_ty()]), - ty::Coroutine(_, ref args, _) => { + ty::Coroutine(_, args, _) => { let coroutine_args = args.as_coroutine(); Ok(vec![coroutine_args.tupled_upvars_ty(), coroutine_args.witness()]) } @@ -91,13 +91,13 @@ pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'tcx>( tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, ) -> ty::Binder<'tcx, Ty<'tcx>> { - debug_assert!(!ty.has_late_bound_regions()); + debug_assert!(!ty.has_bound_regions()); let mut counter = 0; let ty = tcx.fold_regions(ty, |r, current_depth| match r.kind() { ty::ReErased => { let br = ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon }; counter += 1; - ty::Region::new_late_bound(tcx, current_depth, br) + ty::Region::new_bound(tcx, current_depth, br) } // All free regions should be erased here. r => bug!("unexpected region: {r:?}"), 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()) - } -} diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs index b3f9218d7..ecdae2521 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs @@ -9,7 +9,6 @@ //! //! [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html use super::{CanonicalInput, Certainty, EvalCtxt, Goal}; -use crate::solve::canonicalize::{CanonicalizeMode, Canonicalizer}; use crate::solve::{ inspect, response_no_constraints_raw, CanonicalResponse, QueryResult, Response, }; @@ -18,6 +17,7 @@ use rustc_index::IndexVec; use rustc_infer::infer::canonical::query_response::make_query_region_constraints; use rustc_infer::infer::canonical::CanonicalVarValues; use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints}; +use rustc_infer::infer::resolve::EagerResolver; use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, InferOk}; use rustc_middle::infer::canonical::Canonical; use rustc_middle::traits::query::NoSolution; @@ -25,10 +25,8 @@ use rustc_middle::traits::solve::{ ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput, }; use rustc_middle::traits::ObligationCause; -use rustc_middle::ty::{ - self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, - TypeVisitableExt, -}; +use rustc_middle::ty::{self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable}; +use rustc_next_trait_solver::canonicalizer::{CanonicalizeMode, Canonicalizer}; use rustc_span::DUMMY_SP; use std::iter; use std::ops::Deref; @@ -58,7 +56,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalInput<'tcx, T>) { let opaque_types = self.infcx.clone_opaque_types_for_query_response(); let (goal, opaque_types) = - (goal, opaque_types).fold_with(&mut EagerResolver { infcx: self.infcx }); + (goal, opaque_types).fold_with(&mut EagerResolver::new(self.infcx)); let mut orig_values = Default::default(); let canonical_goal = Canonicalizer::canonicalize( @@ -96,26 +94,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ); let certainty = certainty.unify_with(goals_certainty); - if let Certainty::OVERFLOW = certainty { - // If we have overflow, it's probable that we're substituting a type - // into itself infinitely and any partial substitutions in the query - // response are probably not useful anyways, so just return an empty - // query response. - // - // This may prevent us from potentially useful inference, e.g. - // 2 candidates, one ambiguous and one overflow, which both - // have the same inference constraints. - // - // Changing this to retain some constraints in the future - // won't be a breaking change, so this is good enough for now. - return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Overflow)); - } let var_values = self.var_values; let external_constraints = self.compute_external_query_constraints()?; let (var_values, mut external_constraints) = - (var_values, external_constraints).fold_with(&mut EagerResolver { infcx: self.infcx }); + (var_values, external_constraints).fold_with(&mut EagerResolver::new(self.infcx)); // Remove any trivial region constraints once we've resolved regions external_constraints .region_constraints @@ -262,7 +246,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } GenericArgKind::Lifetime(r) => { - if let ty::ReLateBound(debruijn, br) = *r { + if let ty::ReBound(debruijn, br) = *r { assert_eq!(debruijn, ty::INNERMOST); opt_values[br.var] = Some(*original_value); } @@ -364,86 +348,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } -/// Resolves ty, region, and const vars to their inferred values or their root vars. -struct EagerResolver<'a, 'tcx> { - infcx: &'a InferCtxt<'tcx>, -} - -impl<'tcx> TypeFolder<TyCtxt<'tcx>> for EagerResolver<'_, 'tcx> { - fn interner(&self) -> TyCtxt<'tcx> { - self.infcx.tcx - } - - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - match *t.kind() { - ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) { - Ok(t) => t.fold_with(self), - Err(_) => Ty::new_var(self.infcx.tcx, self.infcx.root_var(vid)), - }, - ty::Infer(ty::IntVar(vid)) => self.infcx.opportunistic_resolve_int_var(vid), - ty::Infer(ty::FloatVar(vid)) => self.infcx.opportunistic_resolve_float_var(vid), - _ => { - if t.has_infer() { - t.super_fold_with(self) - } else { - t - } - } - } - } - - fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - match *r { - ty::ReVar(vid) => self - .infcx - .inner - .borrow_mut() - .unwrap_region_constraints() - .opportunistic_resolve_var(self.infcx.tcx, vid), - _ => r, - } - } - - fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { - match c.kind() { - ty::ConstKind::Infer(ty::InferConst::Var(vid)) => { - // FIXME: we need to fold the ty too, I think. - match self.infcx.probe_const_var(vid) { - Ok(c) => c.fold_with(self), - Err(_) => { - ty::Const::new_var(self.infcx.tcx, self.infcx.root_const_var(vid), c.ty()) - } - } - } - ty::ConstKind::Infer(ty::InferConst::EffectVar(vid)) => { - debug_assert_eq!(c.ty(), self.infcx.tcx.types.bool); - match self.infcx.probe_effect_var(vid) { - Some(c) => c.as_const(self.infcx.tcx), - None => ty::Const::new_infer( - self.infcx.tcx, - ty::InferConst::EffectVar(self.infcx.root_effect_var(vid)), - self.infcx.tcx.types.bool, - ), - } - } - _ => { - if c.has_infer() { - c.super_fold_with(self) - } else { - c - } - } - } - } -} - impl<'tcx> inspect::ProofTreeBuilder<'tcx> { pub fn make_canonical_state<T: TypeFoldable<TyCtxt<'tcx>>>( ecx: &EvalCtxt<'_, 'tcx>, data: T, ) -> inspect::CanonicalState<'tcx, T> { let state = inspect::State { var_values: ecx.var_values, data }; - let state = state.fold_with(&mut EagerResolver { infcx: ecx.infcx }); + let state = state.fold_with(&mut EagerResolver::new(ecx.infcx)); Canonicalizer::canonicalize( ecx.infcx, CanonicalizeMode::Response { max_input_universe: ecx.max_input_universe }, diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs new file mode 100644 index 000000000..67b680105 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/commit_if_ok.rs @@ -0,0 +1,45 @@ +use super::{EvalCtxt, NestedGoals}; +use crate::solve::inspect; +use rustc_middle::traits::query::NoSolution; + +impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { + pub(in crate::solve) fn commit_if_ok<T>( + &mut self, + f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> Result<T, NoSolution>, + ) -> Result<T, NoSolution> { + let mut nested_ecx = EvalCtxt { + infcx: self.infcx, + variables: self.variables, + var_values: self.var_values, + predefined_opaques_in_body: self.predefined_opaques_in_body, + max_input_universe: self.max_input_universe, + search_graph: self.search_graph, + nested_goals: NestedGoals::new(), + tainted: self.tainted, + inspect: self.inspect.new_probe(), + }; + + let result = nested_ecx.infcx.commit_if_ok(|_| f(&mut nested_ecx)); + if result.is_ok() { + let EvalCtxt { + infcx: _, + variables: _, + var_values: _, + predefined_opaques_in_body: _, + max_input_universe: _, + search_graph: _, + nested_goals, + tainted, + inspect, + } = nested_ecx; + self.nested_goals.extend(nested_goals); + self.tainted = tainted; + self.inspect.integrate_snapshot(inspect); + } else { + nested_ecx.inspect.probe_kind(inspect::ProbeKind::CommitIfOk); + self.inspect.finish_probe(nested_ecx.inspect); + } + + result + } +} diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs index 70235b710..76c50a111 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs @@ -4,7 +4,7 @@ use rustc_infer::infer::at::ToTrace; use rustc_infer::infer::canonical::CanonicalVarValues; use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; use rustc_infer::infer::{ - DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, TyCtxtInferExt, + BoundRegionConversionTime, DefineOpaqueTypes, InferCtxt, InferOk, TyCtxtInferExt, }; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::ObligationCause; @@ -23,17 +23,19 @@ use rustc_middle::ty::{ use rustc_session::config::DumpSolverProofTree; use rustc_span::DUMMY_SP; use std::io::Write; +use std::iter; use std::ops::ControlFlow; use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment}; use super::inspect::ProofTreeBuilder; -use super::SolverMode; use super::{search_graph, GoalEvaluationKind}; use super::{search_graph::SearchGraph, Goal}; +use super::{GoalSource, SolverMode}; pub use select::InferCtxtSelectExt; mod canonical; +mod commit_if_ok; mod probe; mod select; @@ -102,12 +104,12 @@ pub(super) struct NestedGoals<'tcx> { /// with a fresh inference variable when we evaluate this goal. That can result /// in a trait solver cycle. This would currently result in overflow but can be /// can be unsound with more powerful coinduction in the future. - pub(super) normalizes_to_hack_goal: Option<Goal<'tcx, ty::ProjectionPredicate<'tcx>>>, + pub(super) normalizes_to_hack_goal: Option<Goal<'tcx, ty::NormalizesTo<'tcx>>>, /// The rest of the goals which have not yet processed or remain ambiguous. - pub(super) goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, + pub(super) goals: Vec<(GoalSource, Goal<'tcx, ty::Predicate<'tcx>>)>, } -impl NestedGoals<'_> { +impl<'tcx> NestedGoals<'tcx> { pub(super) fn new() -> Self { Self { normalizes_to_hack_goal: None, goals: Vec::new() } } @@ -115,6 +117,11 @@ impl NestedGoals<'_> { pub(super) fn is_empty(&self) -> bool { self.normalizes_to_hack_goal.is_none() && self.goals.is_empty() } + + pub(super) fn extend(&mut self, other: NestedGoals<'tcx>) { + assert_eq!(other.normalizes_to_hack_goal, None); + self.goals.extend(other.goals) + } } #[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)] @@ -140,7 +147,7 @@ pub trait InferCtxtEvalExt<'tcx> { } impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { - #[instrument(level = "debug", skip(self), ret)] + #[instrument(level = "debug", skip(self))] fn evaluate_root_goal( &self, goal: Goal<'tcx, ty::Predicate<'tcx>>, @@ -150,7 +157,7 @@ impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { Option<inspect::GoalEvaluation<'tcx>>, ) { EvalCtxt::enter_root(self, generate_proof_tree, |ecx| { - ecx.evaluate_goal(GoalEvaluationKind::Root, goal) + ecx.evaluate_goal(GoalEvaluationKind::Root, GoalSource::Misc, goal) }) } } @@ -194,9 +201,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let result = f(&mut ecx); let tree = ecx.inspect.finalize(); - if let (Some(tree), DumpSolverProofTree::Always) = - (&tree, infcx.tcx.sess.opts.unstable_opts.dump_solver_proof_tree) - { + if let (Some(tree), DumpSolverProofTree::Always) = ( + &tree, + infcx.tcx.sess.opts.unstable_opts.next_solver.map(|c| c.dump_tree).unwrap_or_default(), + ) { let mut lock = std::io::stdout().lock(); let _ = lock.write_fmt(format_args!("{tree:?}\n")); let _ = lock.flush(); @@ -327,12 +335,12 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { fn evaluate_goal( &mut self, goal_evaluation_kind: GoalEvaluationKind, + source: GoalSource, goal: Goal<'tcx, ty::Predicate<'tcx>>, ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { let (orig_values, canonical_goal) = self.canonicalize_goal(goal); let mut goal_evaluation = self.inspect.new_goal_evaluation(goal, &orig_values, goal_evaluation_kind); - let encountered_overflow = self.search_graph.encountered_overflow(); let canonical_response = EvalCtxt::evaluate_canonical_goal( self.tcx(), self.search_graph, @@ -347,13 +355,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { Ok(response) => response, }; - let has_changed = !canonical_response.value.var_values.is_identity_modulo_regions() - || !canonical_response.value.external_constraints.opaque_types.is_empty(); - let (certainty, nested_goals) = match self.instantiate_and_apply_query_response( - goal.param_env, - orig_values, - canonical_response, - ) { + let (certainty, has_changed, nested_goals) = match self + .instantiate_response_discarding_overflow( + goal.param_env, + source, + orig_values, + canonical_response, + ) { Err(e) => { self.inspect.goal_evaluation(goal_evaluation); return Err(e); @@ -367,72 +375,54 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { bug!("an unchanged goal shouldn't have any side-effects on instantiation"); } - // Check that rerunning this query with its inference constraints applied - // doesn't result in new inference constraints and has the same result. + // FIXME: We previously had an assert here that checked that recomputing + // a goal after applying its constraints did not change its response. // - // If we have projection goals like `<T as Trait>::Assoc == u32` we recursively - // call `exists<U> <T as Trait>::Assoc == U` to enable better caching. This goal - // could constrain `U` to `u32` which would cause this check to result in a - // solver cycle. - if cfg!(debug_assertions) - && has_changed - && !matches!( - goal_evaluation_kind, - GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::Yes } - ) - && !self.search_graph.in_cycle() - { - // The nested evaluation has to happen with the original state - // of `encountered_overflow`. - let from_original_evaluation = - self.search_graph.reset_encountered_overflow(encountered_overflow); - self.check_evaluate_goal_stable_result(goal, canonical_goal, canonical_response); - // In case the evaluation was unstable, we manually make sure that this - // debug check does not influence the result of the parent goal. - self.search_graph.reset_encountered_overflow(from_original_evaluation); - } + // This assert was removed as it did not hold for goals constraining + // an inference variable to a recursive alias, e.g. in + // tests/ui/traits/next-solver/overflow/recursive-self-normalization.rs. + // + // Once we have decided on how to handle trait-system-refactor-initiative#75, + // we should re-add an assert here. Ok((has_changed, certainty, nested_goals)) } - fn check_evaluate_goal_stable_result( + fn instantiate_response_discarding_overflow( &mut self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - original_input: CanonicalInput<'tcx>, - original_result: CanonicalResponse<'tcx>, - ) { - let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); - let result = EvalCtxt::evaluate_canonical_goal( - self.tcx(), - self.search_graph, - canonical_goal, - // FIXME(-Ztrait-solver=next): we do not track what happens in `evaluate_canonical_goal` - &mut ProofTreeBuilder::new_noop(), - ); + param_env: ty::ParamEnv<'tcx>, + source: GoalSource, + original_values: Vec<ty::GenericArg<'tcx>>, + response: CanonicalResponse<'tcx>, + ) -> Result<(Certainty, bool, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { + // The old solver did not evaluate nested goals when normalizing. + // It returned the selection constraints allowing a `Projection` + // obligation to not hold in coherence while avoiding the fatal error + // from overflow. + // + // We match this behavior here by considering all constraints + // from nested goals which are not from where-bounds. We will already + // need to track which nested goals are required by impl where-bounds + // for coinductive cycles, so we simply reuse that here. + // + // While we could consider overflow constraints in more cases, this should + // not be necessary for backcompat and results in better perf. It also + // avoids a potential inconsistency which would otherwise require some + // tracking for root goals as well. See #119071 for an example. + let keep_overflow_constraints = || { + self.search_graph.current_goal_is_normalizes_to() + && source != GoalSource::ImplWhereBound + }; - macro_rules! fail { - ($msg:expr) => {{ - let msg = $msg; - warn!( - "unstable result: {msg}\n\ - original goal: {original_input:?},\n\ - original result: {original_result:?}\n\ - re-canonicalized goal: {canonical_goal:?}\n\ - second response: {result:?}" - ); - return; - }}; - } + if response.value.certainty == Certainty::OVERFLOW && !keep_overflow_constraints() { + Ok((Certainty::OVERFLOW, false, Vec::new())) + } else { + let has_changed = !response.value.var_values.is_identity_modulo_regions() + || !response.value.external_constraints.opaque_types.is_empty(); - let Ok(new_canonical_response) = result else { fail!("second response was error") }; - // We only check for modulo regions as we convert all regions in - // the input to new existentials, even if they're expected to be - // `'static` or a placeholder region. - if !new_canonical_response.value.var_values.is_identity_modulo_regions() { - fail!("additional constraints from second response") - } - if original_result.value.certainty != new_canonical_response.value.certainty { - fail!("unstable certainty") + let (certainty, nested_goals) = + self.instantiate_and_apply_query_response(param_env, original_values, response)?; + Ok((certainty, has_changed, nested_goals)) } } @@ -462,8 +452,6 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { ty::PredicateKind::Coerce(predicate) => { self.compute_coerce_goal(Goal { param_env, predicate }) } - ty::PredicateKind::ClosureKind(def_id, args, kind) => self - .compute_closure_kind_goal(Goal { param_env, predicate: (def_id, args, kind) }), ty::PredicateKind::ObjectSafe(trait_def_id) => { self.compute_object_safe_goal(trait_def_id) } @@ -474,7 +462,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { self.compute_const_evaluatable_goal(Goal { param_env, predicate: ct }) } ty::PredicateKind::ConstEquate(_, _) => { - bug!("ConstEquate should not be emitted when `-Ztrait-solver=next` is active") + bug!("ConstEquate should not be emitted when `-Znext-solver` is active") + } + ty::PredicateKind::NormalizesTo(predicate) => { + self.compute_normalizes_to_goal(Goal { param_env, predicate }) } ty::PredicateKind::AliasRelate(lhs, rhs, direction) => self .compute_alias_relate_goal(Goal { @@ -488,7 +479,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { } else { let kind = self.infcx.instantiate_binder_with_placeholders(kind); let goal = goal.with(self.tcx(), ty::Binder::dummy(kind)); - self.add_goal(goal); + self.add_goal(GoalSource::Misc, goal); self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } @@ -537,6 +528,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new()); self.inspect.evaluate_added_goals_loop_start(); + + fn with_misc_source<'tcx>( + it: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>, + ) -> impl Iterator<Item = (GoalSource, Goal<'tcx, ty::Predicate<'tcx>>)> { + iter::zip(iter::repeat(GoalSource::Misc), it) + } + // If this loop did not result in any progress, what's our final certainty. let mut unchanged_certainty = Some(Certainty::Yes); if let Some(goal) = goals.normalizes_to_hack_goal.take() { @@ -545,17 +543,15 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let unconstrained_rhs = self.next_term_infer_of_kind(goal.predicate.term); let unconstrained_goal = goal.with( tcx, - ty::ProjectionPredicate { - projection_ty: goal.predicate.projection_ty, - term: unconstrained_rhs, - }, + ty::NormalizesTo { alias: goal.predicate.alias, term: unconstrained_rhs }, ); let (_, certainty, instantiate_goals) = self.evaluate_goal( GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::Yes }, + GoalSource::Misc, unconstrained_goal, )?; - self.nested_goals.goals.extend(instantiate_goals); + self.nested_goals.goals.extend(with_misc_source(instantiate_goals)); // Finally, equate the goal's RHS with the unconstrained var. // We put the nested goals from this into goals instead of @@ -564,15 +560,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { // matters in practice, though. let eq_goals = self.eq_and_get_goals(goal.param_env, goal.predicate.term, unconstrained_rhs)?; - goals.goals.extend(eq_goals); + goals.goals.extend(with_misc_source(eq_goals)); // We only look at the `projection_ty` part here rather than // looking at the "has changed" return from evaluate_goal, // because we expect the `unconstrained_rhs` part of the predicate // to have changed -- that means we actually normalized successfully! - if goal.predicate.projection_ty - != self.resolve_vars_if_possible(goal.predicate.projection_ty) - { + if goal.predicate.alias != self.resolve_vars_if_possible(goal.predicate.alias) { unchanged_certainty = None; } @@ -587,12 +581,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { } } - for goal in goals.goals.drain(..) { + for (source, goal) in goals.goals.drain(..) { let (has_changed, certainty, instantiate_goals) = self.evaluate_goal( GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::No }, + source, goal, )?; - self.nested_goals.goals.extend(instantiate_goals); + self.nested_goals.goals.extend(with_misc_source(instantiate_goals)); if has_changed { unchanged_certainty = None; } @@ -600,7 +595,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { match certainty { Certainty::Yes => {} Certainty::Maybe(_) => { - self.nested_goals.goals.push(goal); + self.nested_goals.goals.push((source, goal)); unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); } } @@ -642,9 +637,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { /// /// This is the case if the `term` is an inference variable in the innermost universe /// and does not occur in any other part of the predicate. + #[instrument(level = "debug", skip(self), ret)] pub(super) fn term_is_fully_unconstrained( &self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, ty::NormalizesTo<'tcx>>, ) -> bool { let term_is_infer = match goal.predicate.term.unpack() { ty::TermKind::Ty(ty) => { @@ -708,7 +704,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let mut visitor = ContainsTerm { infcx: self.infcx, term: goal.predicate.term }; term_is_infer - && goal.predicate.projection_ty.visit_with(&mut visitor).is_continue() + && goal.predicate.alias.visit_with(&mut visitor).is_continue() && goal.param_env.visit_with(&mut visitor).is_continue() } @@ -723,7 +719,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { .at(&ObligationCause::dummy(), param_env) .eq(DefineOpaqueTypes::No, lhs, rhs) .map(|InferOk { value: (), obligations }| { - self.add_goals(obligations.into_iter().map(|o| o.into())); + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); }) .map_err(|e| { debug!(?e, "failed to equate"); @@ -742,7 +738,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { .at(&ObligationCause::dummy(), param_env) .sub(DefineOpaqueTypes::No, sub, sup) .map(|InferOk { value: (), obligations }| { - self.add_goals(obligations.into_iter().map(|o| o.into())); + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); }) .map_err(|e| { debug!(?e, "failed to subtype"); @@ -750,6 +746,26 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }) } + #[instrument(level = "debug", skip(self, param_env), ret)] + pub(super) fn relate<T: ToTrace<'tcx>>( + &mut self, + param_env: ty::ParamEnv<'tcx>, + lhs: T, + variance: ty::Variance, + rhs: T, + ) -> Result<(), NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .relate(DefineOpaqueTypes::No, lhs, variance, rhs) + .map(|InferOk { value: (), obligations }| { + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); + }) + .map_err(|e| { + debug!(?e, "failed to relate"); + NoSolution + }) + } + /// Equates two values returning the nested goals without adding them /// to the nested goals of the `EvalCtxt`. /// @@ -780,7 +796,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> T { self.infcx.instantiate_binder_with_fresh_vars( DUMMY_SP, - LateBoundRegionConversionTime::HigherRankedType, + BoundRegionConversionTime::HigherRankedType, value, ) } @@ -875,7 +891,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { true, &mut obligations, )?; - self.add_goals(obligations.into_iter().map(|o| o.into())); + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); Ok(()) } @@ -895,7 +911,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { hidden_ty, &mut obligations, ); - self.add_goals(obligations.into_iter().map(|o| o.into())); + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); } // Do something for each opaque/hidden pair defined with `def_id` in the diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs index 6087b9167..91fd48807 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs @@ -1,5 +1,10 @@ +use crate::solve::assembly::Candidate; + use super::EvalCtxt; -use rustc_middle::traits::solve::{inspect, CandidateSource, QueryResult}; +use rustc_middle::traits::{ + query::NoSolution, + solve::{inspect, CandidateSource, QueryResult}, +}; use std::marker::PhantomData; pub(in crate::solve) struct ProbeCtxt<'me, 'a, 'tcx, F, T> { @@ -36,6 +41,23 @@ where } } +pub(in crate::solve) struct TraitProbeCtxt<'me, 'a, 'tcx, F> { + cx: ProbeCtxt<'me, 'a, 'tcx, F, QueryResult<'tcx>>, + source: CandidateSource, +} + +impl<'tcx, F> TraitProbeCtxt<'_, '_, 'tcx, F> +where + F: FnOnce(&QueryResult<'tcx>) -> inspect::ProbeKind<'tcx>, +{ + pub(in crate::solve) fn enter( + self, + f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>, + ) -> Result<Candidate<'tcx>, NoSolution> { + self.cx.enter(|ecx| f(ecx)).map(|result| Candidate { source: self.source, result }) + } +} + impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { /// `probe_kind` is only called when proof tree building is enabled so it can be /// as expensive as necessary to output the desired information. @@ -69,20 +91,18 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { pub(in crate::solve) fn probe_trait_candidate( &mut self, source: CandidateSource, - ) -> ProbeCtxt< - '_, - 'a, - 'tcx, - impl FnOnce(&QueryResult<'tcx>) -> inspect::ProbeKind<'tcx>, - QueryResult<'tcx>, - > { - ProbeCtxt { - ecx: self, - probe_kind: move |result: &QueryResult<'tcx>| inspect::ProbeKind::TraitCandidate { - source, - result: *result, + ) -> TraitProbeCtxt<'_, 'a, 'tcx, impl FnOnce(&QueryResult<'tcx>) -> inspect::ProbeKind<'tcx>> + { + TraitProbeCtxt { + cx: ProbeCtxt { + ecx: self, + probe_kind: move |result: &QueryResult<'tcx>| inspect::ProbeKind::TraitCandidate { + source, + result: *result, + }, + _result: PhantomData, }, - _result: PhantomData, + source, } } } diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs index f1d309122..2139210b8 100644 --- a/compiler/rustc_trait_selection/src/solve/fulfill.rs +++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs @@ -108,6 +108,11 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { MismatchedProjectionTypes { err: TypeError::Mismatch }, ) } + ty::PredicateKind::NormalizesTo(..) => { + FulfillmentErrorCode::CodeProjectionError( + MismatchedProjectionTypes { err: TypeError::Mismatch }, + ) + } ty::PredicateKind::AliasRelate(_, _, _) => { FulfillmentErrorCode::CodeProjectionError( MismatchedProjectionTypes { err: TypeError::Mismatch }, @@ -135,7 +140,6 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { } ty::PredicateKind::Clause(_) | ty::PredicateKind::ObjectSafe(_) - | ty::PredicateKind::ClosureKind(_, _, _) | ty::PredicateKind::Ambiguous => { FulfillmentErrorCode::CodeSelectionError( SelectionError::Unimplemented, diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs index 69bfdd468..6db53d6dd 100644 --- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs +++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs @@ -58,7 +58,7 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> { visitor: &mut V, ) -> ControlFlow<V::BreakTy> { // HACK: An arbitrary cutoff to avoid dealing with overflow and cycles. - if self.goal.depth >= 10 { + if self.goal.depth <= 10 { let infcx = self.goal.infcx; infcx.probe(|_| { let mut instantiated_goals = vec![]; @@ -119,8 +119,7 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> { ) { for step in &probe.steps { match step { - &inspect::ProbeStep::AddGoal(goal) => nested_goals.push(goal), - inspect::ProbeStep::EvaluateGoals(_) => (), + &inspect::ProbeStep::AddGoal(_source, goal) => nested_goals.push(goal), inspect::ProbeStep::NestedProbe(ref probe) => { // Nested probes have to prove goals added in their parent // but do not leak them, so we truncate the added goals @@ -129,13 +128,17 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> { self.candidates_recur(candidates, nested_goals, probe); nested_goals.truncate(num_goals); } + inspect::ProbeStep::EvaluateGoals(_) + | inspect::ProbeStep::CommitIfOkStart + | inspect::ProbeStep::CommitIfOkSuccess => (), } } match probe.kind { inspect::ProbeKind::NormalizedSelfTyAssembly | inspect::ProbeKind::UnsizeAssembly - | inspect::ProbeKind::UpcastProjectionCompatibility => (), + | inspect::ProbeKind::UpcastProjectionCompatibility + | inspect::ProbeKind::CommitIfOk => (), // We add a candidate for the root evaluation if there // is only one way to prove a given goal, e.g. for `WellFormed`. // @@ -172,7 +175,7 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> { warn!("unexpected root evaluation: {:?}", self.evaluation); return vec![]; } - inspect::CanonicalGoalEvaluationKind::Evaluation { ref revisions } => { + inspect::CanonicalGoalEvaluationKind::Evaluation { revisions } => { if let Some(last) = revisions.last() { last } else { diff --git a/compiler/rustc_trait_selection/src/solve/inspect/build.rs b/compiler/rustc_trait_selection/src/solve/inspect/build.rs index 088455b38..d8caef5b0 100644 --- a/compiler/rustc_trait_selection/src/solve/inspect/build.rs +++ b/compiler/rustc_trait_selection/src/solve/inspect/build.rs @@ -7,7 +7,7 @@ use std::mem; use rustc_middle::traits::query::NoSolution; use rustc_middle::traits::solve::{ - CanonicalInput, Certainty, Goal, IsNormalizesToHack, QueryInput, QueryResult, + CanonicalInput, Certainty, Goal, GoalSource, IsNormalizesToHack, QueryInput, QueryResult, }; use rustc_middle::ty::{self, TyCtxt}; use rustc_session::config::DumpSolverProofTree; @@ -216,17 +216,21 @@ impl<'tcx> WipProbe<'tcx> { #[derive(Eq, PartialEq, Debug)] enum WipProbeStep<'tcx> { - AddGoal(inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>), + AddGoal(GoalSource, inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>), EvaluateGoals(WipAddedGoalsEvaluation<'tcx>), NestedProbe(WipProbe<'tcx>), + CommitIfOkStart, + CommitIfOkSuccess, } impl<'tcx> WipProbeStep<'tcx> { fn finalize(self) -> inspect::ProbeStep<'tcx> { match self { - WipProbeStep::AddGoal(goal) => inspect::ProbeStep::AddGoal(goal), + WipProbeStep::AddGoal(source, goal) => inspect::ProbeStep::AddGoal(source, goal), WipProbeStep::EvaluateGoals(eval) => inspect::ProbeStep::EvaluateGoals(eval.finalize()), WipProbeStep::NestedProbe(probe) => inspect::ProbeStep::NestedProbe(probe.finalize()), + WipProbeStep::CommitIfOkStart => inspect::ProbeStep::CommitIfOkStart, + WipProbeStep::CommitIfOkSuccess => inspect::ProbeStep::CommitIfOkSuccess, } } } @@ -261,7 +265,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> { GenerateProofTree::Never => ProofTreeBuilder::new_noop(), GenerateProofTree::IfEnabled => { let opts = &tcx.sess.opts.unstable_opts; - match opts.dump_solver_proof_tree { + match opts.next_solver.map(|c| c.dump_tree).unwrap_or_default() { DumpSolverProofTree::Always => ProofTreeBuilder::new_root(), // `OnError` is handled by reevaluating goals in error // reporting with `GenerateProofTree::Yes`. @@ -424,7 +428,11 @@ impl<'tcx> ProofTreeBuilder<'tcx> { } } - pub fn add_goal(ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, ty::Predicate<'tcx>>) { + pub fn add_goal( + ecx: &mut EvalCtxt<'_, 'tcx>, + source: GoalSource, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) { // Can't use `if let Some(this) = ecx.inspect.as_mut()` here because // we have to immutably use the `EvalCtxt` for `make_canonical_state`. if ecx.inspect.is_noop() { @@ -438,7 +446,9 @@ impl<'tcx> ProofTreeBuilder<'tcx> { evaluation: WipProbe { steps, .. }, .. }) - | DebugSolver::Probe(WipProbe { steps, .. }) => steps.push(WipProbeStep::AddGoal(goal)), + | DebugSolver::Probe(WipProbe { steps, .. }) => { + steps.push(WipProbeStep::AddGoal(source, goal)) + } s => unreachable!("tried to add {goal:?} to {s:?}"), } } @@ -459,6 +469,29 @@ impl<'tcx> ProofTreeBuilder<'tcx> { } } + /// Used by `EvalCtxt::commit_if_ok` to flatten the work done inside + /// of the probe into the parent. + pub fn integrate_snapshot(&mut self, probe: ProofTreeBuilder<'tcx>) { + if let Some(this) = self.as_mut() { + match (this, *probe.state.unwrap()) { + ( + DebugSolver::Probe(WipProbe { steps, .. }) + | DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep { + evaluation: WipProbe { steps, .. }, + .. + }), + DebugSolver::Probe(probe), + ) => { + steps.push(WipProbeStep::CommitIfOkStart); + assert_eq!(probe.kind, None); + steps.extend(probe.steps); + steps.push(WipProbeStep::CommitIfOkSuccess); + } + _ => unreachable!(), + } + } + } + pub fn new_evaluate_added_goals(&mut self) -> ProofTreeBuilder<'tcx> { self.nested(|| WipAddedGoalsEvaluation { evaluations: vec![], result: None }) } diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index dba5369fa..2f3111a24 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -1,7 +1,6 @@ //! The next-generation trait solver, currently still WIP. //! -//! As a user of rust, you can use `-Ztrait-solver=next` or `next-coherence` -//! to enable the new trait solver always, or just within coherence, respectively. +//! As a user of rust, you can use `-Znext-solver` to enable the new trait solver. //! //! As a developer of rustc, you shouldn't be using the new trait //! solver without asking the trait-system-refactor-initiative, but it can @@ -16,31 +15,33 @@ //! 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, IsNormalizesToHack, QueryResult, - Response, + CanonicalResponse, Certainty, ExternalConstraintsData, Goal, GoalSource, IsNormalizesToHack, + QueryResult, Response, }; -use rustc_middle::ty::{self, Ty, TyCtxt, UniverseIndex}; +use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, UniverseIndex}; use rustc_middle::ty::{ CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate, }; mod alias_relate; mod assembly; -mod canonicalize; mod eval_ctxt; mod fulfill; pub mod inspect; mod normalize; +mod normalizes_to; mod project_goals; mod search_graph; mod trait_goals; pub use eval_ctxt::{EvalCtxt, GenerateProofTree, InferCtxtEvalExt, InferCtxtSelectExt}; pub use fulfill::FulfillmentCtxt; -pub(crate) use normalize::{deeply_normalize, deeply_normalize_with_skipped_universes}; +pub(crate) use normalize::deeply_normalize_for_diagnostics; +pub use normalize::{deeply_normalize, deeply_normalize_with_skipped_universes}; #[derive(Debug, Clone, Copy)] enum SolverMode { @@ -63,8 +64,6 @@ enum GoalEvaluationKind { trait CanonicalResponseExt { fn has_no_inference_or_external_constraints(&self) -> bool; - - fn has_only_region_constraints(&self) -> bool; } impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> { @@ -73,11 +72,6 @@ impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> { && self.value.var_values.is_identity() && self.value.external_constraints.opaque_types.is_empty() } - - fn has_only_region_constraints(&self) -> bool { - self.value.var_values.is_identity_modulo_regions() - && self.value.external_constraints.opaque_types.is_empty() - } } impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { @@ -163,7 +157,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { ) -> QueryResult<'tcx> { match self.well_formed_goals(goal.param_env, goal.predicate) { Some(goals) => { - self.add_goals(goals); + self.add_goals(GoalSource::Misc, goals); self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } None => self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS), @@ -220,7 +214,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self))] - fn set_normalizes_to_hack_goal(&mut self, goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>) { + fn set_normalizes_to_hack_goal(&mut self, goal: Goal<'tcx, ty::NormalizesTo<'tcx>>) { assert!( self.nested_goals.normalizes_to_hack_goal.is_none(), "attempted to set the projection eq hack goal when one already exists" @@ -229,15 +223,19 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } #[instrument(level = "debug", skip(self))] - fn add_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) { - inspect::ProofTreeBuilder::add_goal(self, goal); - self.nested_goals.goals.push(goal); + fn add_goal(&mut self, source: GoalSource, goal: Goal<'tcx, ty::Predicate<'tcx>>) { + inspect::ProofTreeBuilder::add_goal(self, source, goal); + self.nested_goals.goals.push((source, goal)); } #[instrument(level = "debug", skip(self, goals))] - fn add_goals(&mut self, goals: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>) { + fn add_goals( + &mut self, + source: GoalSource, + goals: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>, + ) { for goal in goals { - self.add_goal(goal); + self.add_goal(source, goal); } } @@ -253,7 +251,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { return None; } - // FIXME(-Ztrait-solver=next): We should instead try to find a `Certainty::Yes` response with + // FIXME(-Znext-solver): We should instead try to find a `Certainty::Yes` response with // a subset of the constraints that all the other responses have. let one = responses[0]; if responses[1..].iter().all(|&resp| resp == one) { @@ -294,28 +292,61 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { /// in [`EvalCtxt::assemble_candidates_via_self_ty`] does not have to normalize /// the self type. It is required when structurally matching on any other /// arguments of a trait goal, e.g. when assembling builtin unsize candidates. + #[instrument(level = "debug", skip(self), ret)] fn try_normalize_ty( &mut self, param_env: ty::ParamEnv<'tcx>, - mut ty: Ty<'tcx>, - ) -> Result<Option<Ty<'tcx>>, NoSolution> { - for _ in 0..self.local_overflow_limit() { - let ty::Alias(_, projection_ty) = *ty.kind() else { - return Ok(Some(ty)); - }; - - let normalized_ty = self.next_ty_infer(); + ty: Ty<'tcx>, + ) -> Option<Ty<'tcx>> { + self.try_normalize_ty_recur(param_env, DefineOpaqueTypes::Yes, 0, ty) + } + + fn try_normalize_ty_recur( + &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. + if let (DefineOpaqueTypes::No, ty::AliasKind::Opaque) = (define_opaque_types, kind) { + if let Some(def_id) = alias.def_id.as_local() { + 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( - self.tcx(), + this.tcx(), param_env, - ty::ProjectionPredicate { projection_ty, term: normalized_ty.into() }, + ty::NormalizesTo { alias, term: normalized_ty.into() }, ); - self.add_goal(normalizes_to_goal); - self.try_evaluate_added_goals()?; - ty = self.resolve_vars_if_possible(normalized_ty); + 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), } - - Ok(None) } } diff --git a/compiler/rustc_trait_selection/src/solve/normalize.rs b/compiler/rustc_trait_selection/src/solve/normalize.rs index b0a348985..55b79e6fc 100644 --- a/compiler/rustc_trait_selection/src/solve/normalize.rs +++ b/compiler/rustc_trait_selection/src/solve/normalize.rs @@ -4,19 +4,20 @@ use crate::traits::{needs_normalization, BoundVarReplacer, PlaceholderReplacer}; use rustc_data_structures::stack::ensure_sufficient_stack; use rustc_infer::infer::at::At; use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; +use rustc_infer::infer::InferCtxt; use rustc_infer::traits::TraitEngineExt; use rustc_infer::traits::{FulfillmentError, Obligation, TraitEngine}; use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; -use rustc_middle::traits::Reveal; +use rustc_middle::traits::{ObligationCause, Reveal}; use rustc_middle::ty::{self, AliasTy, Ty, TyCtxt, UniverseIndex}; -use rustc_middle::ty::{FallibleTypeFolder, TypeSuperFoldable}; +use rustc_middle::ty::{FallibleTypeFolder, TypeFolder, TypeSuperFoldable}; use rustc_middle::ty::{TypeFoldable, TypeVisitableExt}; use super::FulfillmentCtxt; /// Deeply normalize all aliases in `value`. This does not handle inference and expects /// its input to be already fully resolved. -pub(crate) fn deeply_normalize<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>( +pub fn deeply_normalize<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>( at: At<'_, 'tcx>, value: T, ) -> Result<T, Vec<FulfillmentError<'tcx>>> { @@ -30,7 +31,7 @@ pub(crate) fn deeply_normalize<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>( /// Additionally takes a list of universes which represents the binders which have been /// entered before passing `value` to the function. This is currently needed for /// `normalize_erasing_regions`, which skips binders as it walks through a type. -pub(crate) fn deeply_normalize_with_skipped_universes<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>( +pub fn deeply_normalize_with_skipped_universes<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>( at: At<'_, 'tcx>, value: T, universes: Vec<Option<UniverseIndex>>, @@ -75,7 +76,7 @@ impl<'tcx> NormalizationFolder<'_, 'tcx> { tcx, self.at.cause.clone(), self.at.param_env, - ty::ProjectionPredicate { projection_ty: alias, term: new_infer_ty.into() }, + ty::NormalizesTo { alias, term: new_infer_ty.into() }, ); // Do not emit an error if normalization is known to fail but instead @@ -128,8 +129,8 @@ impl<'tcx> NormalizationFolder<'_, 'tcx> { tcx, self.at.cause.clone(), self.at.param_env, - ty::ProjectionPredicate { - projection_ty: AliasTy::new(tcx, uv.def, uv.args), + ty::NormalizesTo { + alias: AliasTy::new(tcx, uv.def, uv.args), term: new_infer_ct.into(), }, ); @@ -230,3 +231,42 @@ impl<'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for NormalizationFolder<'_, 'tcx> { } } } + +// Deeply normalize a value and return it +pub(crate) fn deeply_normalize_for_diagnostics<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>( + infcx: &InferCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + t: T, +) -> T { + t.fold_with(&mut DeeplyNormalizeForDiagnosticsFolder { + at: infcx.at(&ObligationCause::dummy(), param_env), + }) +} + +struct DeeplyNormalizeForDiagnosticsFolder<'a, 'tcx> { + at: At<'a, 'tcx>, +} + +impl<'tcx> TypeFolder<TyCtxt<'tcx>> for DeeplyNormalizeForDiagnosticsFolder<'_, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { + self.at.infcx.tcx + } + + fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { + deeply_normalize_with_skipped_universes( + self.at, + ty, + vec![None; ty.outer_exclusive_binder().as_usize()], + ) + .unwrap_or_else(|_| ty.super_fold_with(self)) + } + + fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { + deeply_normalize_with_skipped_universes( + self.at, + ct, + vec![None; ct.outer_exclusive_binder().as_usize()], + ) + .unwrap_or_else(|_| ct.super_fold_with(self)) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/inherent_projection.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/inherent.rs index 28fe59b7f..b2dff9b48 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals/inherent_projection.rs +++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/inherent.rs @@ -4,18 +4,18 @@ //! 1. instantiate substs, //! 2. equate the self type, and //! 3. instantiate and register where clauses. -use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; +use rustc_middle::traits::solve::{Certainty, Goal, GoalSource, QueryResult}; use rustc_middle::ty; -use super::EvalCtxt; +use crate::solve::EvalCtxt; impl<'tcx> EvalCtxt<'_, 'tcx> { pub(super) fn normalize_inherent_associated_type( &mut self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, ty::NormalizesTo<'tcx>>, ) -> QueryResult<'tcx> { let tcx = self.tcx(); - let inherent = goal.predicate.projection_ty; + let inherent = goal.predicate.alias; let expected = goal.predicate.term.ty().expect("inherent consts are treated separately"); let impl_def_id = tcx.parent(inherent.def_id); @@ -38,7 +38,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { .expect("expected goal term to be fully unconstrained"); // Check both where clauses on the impl and IAT + // + // FIXME(-Znext-solver=coinductive): I think this should be split + // and we tag the impl bounds with `GoalSource::ImplWhereBound`? + // Right not this includes both the impl and the assoc item where bounds, + // and I don't think the assoc item where-bounds are allowed to be coinductive. self.add_goals( + GoalSource::Misc, tcx.predicates_of(inherent.def_id) .instantiate(tcx, inherent_substs) .into_iter() diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs index 240141065..0e9656a1e 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs @@ -1,7 +1,7 @@ use crate::traits::{check_args_compatible, specialization_graph}; -use super::assembly::{self, structural_traits}; -use super::EvalCtxt; +use super::assembly::{self, structural_traits, Candidate}; +use super::{EvalCtxt, GoalSource}; use rustc_hir::def::DefKind; use rustc_hir::def_id::DefId; use rustc_hir::LangItem; @@ -13,20 +13,20 @@ use rustc_middle::traits::solve::{ }; use rustc_middle::traits::BuiltinImplSource; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; -use rustc_middle::ty::ProjectionPredicate; +use rustc_middle::ty::NormalizesTo; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_middle::ty::{ToPredicate, TypeVisitableExt}; use rustc_span::{sym, ErrorGuaranteed, DUMMY_SP}; -mod inherent_projection; +mod inherent; mod opaques; mod weak_types; impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self), ret)] - pub(super) fn compute_projection_goal( + pub(super) fn compute_normalizes_to_goal( &mut self, - goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, NormalizesTo<'tcx>>, ) -> QueryResult<'tcx> { let def_id = goal.predicate.def_id(); match self.tcx().def_kind(def_id) { @@ -71,16 +71,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self), ret)] fn normalize_anon_const( &mut self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, ty::NormalizesTo<'tcx>>, ) -> QueryResult<'tcx> { if let Some(normalized_const) = self.try_const_eval_resolve( goal.param_env, - ty::UnevaluatedConst::new( - goal.predicate.projection_ty.def_id, - goal.predicate.projection_ty.args, - ), + ty::UnevaluatedConst::new(goal.predicate.alias.def_id, goal.predicate.alias.args), self.tcx() - .type_of(goal.predicate.projection_ty.def_id) + .type_of(goal.predicate.alias.def_id) .no_bound_vars() .expect("const ty should not rely on other generics"), ) { @@ -92,17 +89,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } -impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { +impl<'tcx> assembly::GoalKind<'tcx> for NormalizesTo<'tcx> { fn self_ty(self) -> Ty<'tcx> { self.self_ty() } fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx> { - self.projection_ty.trait_ref(tcx) - } - - fn polarity(self) -> ty::ImplPolarity { - ty::ImplPolarity::Positive + self.alias.trait_ref(tcx) } fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self { @@ -127,7 +120,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ecx.instantiate_binder_with_infer(projection_pred); ecx.eq( goal.param_env, - goal.predicate.projection_ty, + goal.predicate.alias, assumption_projection_pred.projection_ty, )?; ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term) @@ -135,8 +128,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { // Add GAT where clauses from the trait's definition ecx.add_goals( + GoalSource::Misc, tcx.predicates_of(goal.predicate.def_id()) - .instantiate_own(tcx, goal.predicate.projection_ty.args) + .instantiate_own(tcx, goal.predicate.alias.args) .map(|(pred, _)| goal.with(tcx, pred)), ); @@ -152,15 +146,15 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { fn consider_impl_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, NormalizesTo<'tcx>>, impl_def_id: DefId, - ) -> QueryResult<'tcx> { + ) -> Result<Candidate<'tcx>, NoSolution> { let tcx = ecx.tcx(); - let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx); + let goal_trait_ref = goal.predicate.alias.trait_ref(tcx); let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; - if !drcx.args_refs_may_unify(goal_trait_ref.args, impl_trait_ref.skip_binder().args) { + if !drcx.args_may_unify(goal_trait_ref.args, impl_trait_ref.skip_binder().args) { return Err(NoSolution); } @@ -176,12 +170,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { .predicates .into_iter() .map(|pred| goal.with(tcx, pred)); - ecx.add_goals(where_clause_bounds); + ecx.add_goals(GoalSource::ImplWhereBound, where_clause_bounds); // Add GAT where clauses from the trait's definition ecx.add_goals( + GoalSource::Misc, tcx.predicates_of(goal.predicate.def_id()) - .instantiate_own(tcx, goal.predicate.projection_ty.args) + .instantiate_own(tcx, goal.predicate.alias.args) .map(|(pred, _)| goal.with(tcx, pred)), ); @@ -200,17 +195,21 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { }; let error_response = |ecx: &mut EvalCtxt<'_, 'tcx>, reason| { - let guar = tcx.sess.delay_span_bug(tcx.def_span(assoc_def.item.def_id), reason); + let guar = tcx.sess.span_delayed_bug(tcx.def_span(assoc_def.item.def_id), reason); let error_term = match assoc_def.item.kind { ty::AssocKind::Const => ty::Const::new_error( tcx, guar, tcx.type_of(goal.predicate.def_id()) - .instantiate(tcx, goal.predicate.projection_ty.args), + .instantiate(tcx, goal.predicate.alias.args), ) .into(), ty::AssocKind::Type => Ty::new_error(tcx, guar).into(), - ty::AssocKind::Fn => unreachable!(), + // This makes no sense... + ty::AssocKind::Fn => span_bug!( + tcx.def_span(assoc_def.item.def_id), + "cannot project to an associated function" + ), }; ecx.eq(goal.param_env, goal.predicate.term, error_term) .expect("expected goal term to be fully unconstrained"); @@ -231,11 +230,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { // // And then map these args to the args of the defining impl of `Assoc`, going // from `[u32, u64]` to `[u32, i32, u64]`. - let impl_args_with_gat = goal.predicate.projection_ty.args.rebase_onto( - tcx, - goal_trait_ref.def_id, - impl_args, - ); + let impl_args_with_gat = + goal.predicate.alias.args.rebase_onto(tcx, goal_trait_ref.def_id, impl_args); let args = ecx.translate_args( goal.param_env, impl_def_id, @@ -290,7 +286,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { - ecx.tcx().sess.delay_span_bug( + ecx.tcx().sess.span_delayed_bug( ecx.tcx().def_span(goal.predicate.def_id()), "associated types not allowed on auto traits", ); @@ -419,7 +415,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { DUMMY_SP, [ty::GenericArg::from(goal.predicate.self_ty())], ); - ecx.add_goal(goal.with(tcx, sized_predicate)); + // FIXME(-Znext-solver=coinductive): Should this be `GoalSource::ImplWhereBound`? + ecx.add_goal(GoalSource::Misc, goal.with(tcx, sized_predicate)); tcx.types.unit } @@ -427,7 +424,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { None => tcx.types.unit, Some(field_def) => { let self_ty = field_def.ty(tcx, args); - ecx.add_goal(goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty))); + // FIXME(-Znext-solver=coinductive): Should this be `GoalSource::ImplWhereBound`? + ecx.add_goal( + GoalSource::Misc, + goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty)), + ); return ecx .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } @@ -437,7 +438,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ty::Tuple(elements) => match elements.last() { None => tcx.types.unit, Some(&self_ty) => { - ecx.add_goal(goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty))); + // FIXME(-Znext-solver=coinductive): Should this be `GoalSource::ImplWhereBound`? + ecx.add_goal( + GoalSource::Misc, + goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty)), + ); return ecx .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } @@ -520,6 +525,40 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ) } + fn consider_builtin_async_iterator_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let self_ty = goal.predicate.self_ty(); + let ty::Coroutine(def_id, args, _) = *self_ty.kind() else { + return Err(NoSolution); + }; + + // Coroutines are not AsyncIterators unless they come from `gen` desugaring + let tcx = ecx.tcx(); + if !tcx.coroutine_is_async_gen(def_id) { + return Err(NoSolution); + } + + ecx.probe_misc_candidate("builtin AsyncIterator kind").enter(|ecx| { + // Take `AsyncIterator<Item = I>` and turn it into the corresponding + // coroutine yield ty `Poll<Option<I>>`. + let expected_ty = Ty::new_adt( + tcx, + tcx.adt_def(tcx.require_lang_item(LangItem::Poll, None)), + tcx.mk_args(&[Ty::new_adt( + tcx, + tcx.adt_def(tcx.require_lang_item(LangItem::Option, None)), + tcx.mk_args(&[goal.predicate.term.into()]), + ) + .into()]), + ); + let yield_ty = args.as_coroutine().yield_ty(); + ecx.eq(goal.param_env, expected_ty, yield_ty)?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + } + fn consider_builtin_coroutine_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs index ebd129f32..b5d1aa06e 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs +++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs @@ -12,10 +12,10 @@ use crate::solve::{EvalCtxt, SolverMode}; impl<'tcx> EvalCtxt<'_, 'tcx> { pub(super) fn normalize_opaque_type( &mut self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, ty::NormalizesTo<'tcx>>, ) -> QueryResult<'tcx> { let tcx = self.tcx(); - let opaque_ty = goal.predicate.projection_ty; + let opaque_ty = goal.predicate.alias; let expected = goal.predicate.term.ty().expect("no such thing as an opaque const"); match (goal.param_env.reveal(), self.solver_mode()) { @@ -44,6 +44,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // Prefer opaques registered already. let opaque_type_key = ty::OpaqueTypeKey { def_id: opaque_ty_def_id, args: opaque_ty.args }; + // FIXME: This also unifies the previous hidden type with the expected. + // + // If that fails, we insert `expected` as a new hidden type instead of + // eagerly emitting an error. let matches = self.unify_existing_opaque_tys(goal.param_env, opaque_type_key, expected); if !matches.is_empty() { @@ -53,6 +57,23 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { return self.flounder(&matches); } } + + 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); + } + }; + // Otherwise, define a new opaque type self.insert_hidden_type(opaque_type_key, goal.param_env, expected)?; self.add_item_bounds_for_hidden_type( diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/weak_types.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/weak_types.rs index 54de32cf6..6d5728797 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals/weak_types.rs +++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/weak_types.rs @@ -3,18 +3,18 @@ //! //! Since a weak alias is not ambiguous, this just computes the `type_of` of //! the alias and registers the where-clauses of the type alias. -use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; +use rustc_middle::traits::solve::{Certainty, Goal, GoalSource, QueryResult}; use rustc_middle::ty; -use super::EvalCtxt; +use crate::solve::EvalCtxt; impl<'tcx> EvalCtxt<'_, 'tcx> { pub(super) fn normalize_weak_type( &mut self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, ty::NormalizesTo<'tcx>>, ) -> QueryResult<'tcx> { let tcx = self.tcx(); - let weak_ty = goal.predicate.projection_ty; + let weak_ty = goal.predicate.alias; let expected = goal.predicate.term.ty().expect("no such thing as a const alias"); let actual = tcx.type_of(weak_ty.def_id).instantiate(tcx, weak_ty.args); @@ -22,6 +22,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // Check where clauses self.add_goals( + GoalSource::Misc, tcx.predicates_of(weak_ty.def_id) .instantiate(tcx, weak_ty.args) .predicates diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs new file mode 100644 index 000000000..30ae385a8 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -0,0 +1,38 @@ +use crate::solve::GoalSource; + +use super::EvalCtxt; +use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; +use rustc_middle::ty::{self, ProjectionPredicate}; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + #[instrument(level = "debug", skip(self), ret)] + pub(super) fn compute_projection_goal( + &mut self, + goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + let tcx = self.tcx(); + let projection_term = match goal.predicate.term.unpack() { + ty::TermKind::Ty(_) => goal.predicate.projection_ty.to_ty(tcx).into(), + ty::TermKind::Const(_) => ty::Const::new_unevaluated( + tcx, + ty::UnevaluatedConst::new( + goal.predicate.projection_ty.def_id, + goal.predicate.projection_ty.args, + ), + tcx.type_of(goal.predicate.projection_ty.def_id) + .instantiate(tcx, goal.predicate.projection_ty.args), + ) + .into(), + }; + let goal = goal.with( + tcx, + ty::PredicateKind::AliasRelate( + projection_term, + goal.predicate.term, + ty::AliasRelationDirection::Equate, + ), + ); + self.add_goal(GoalSource::Misc, goal); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/search_graph.rs b/compiler/rustc_trait_selection/src/solve/search_graph.rs index 7ffa1d7d3..2a161c2d9 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph.rs @@ -8,11 +8,13 @@ use rustc_index::IndexVec; use rustc_middle::dep_graph::dep_kinds; use rustc_middle::traits::solve::CacheData; use rustc_middle::traits::solve::{CanonicalInput, Certainty, EvaluationCache, QueryResult}; +use rustc_middle::ty; use rustc_middle::ty::TyCtxt; use rustc_session::Limit; use std::collections::hash_map::Entry; rustc_index::newtype_index! { + #[orderable] pub struct StackDepth {} } @@ -37,7 +39,7 @@ struct StackEntry<'tcx> { /// If we were to use that result when later trying to prove another cycle /// participant, we can end up with unstable query results. /// - /// See tests/ui/new-solver/coinduction/incompleteness-unstable-result.rs for + /// See tests/ui/next-solver/coinduction/incompleteness-unstable-result.rs for /// an example of where this is needed. cycle_participants: FxHashSet<CanonicalInput<'tcx>>, } @@ -110,37 +112,13 @@ impl<'tcx> SearchGraph<'tcx> { self.stack.is_empty() } - /// Whether we're currently in a cycle. This should only be used - /// for debug assertions. - pub(super) fn in_cycle(&self) -> bool { - if let Some(stack_depth) = self.stack.last_index() { - // Either the current goal on the stack is the root of a cycle - // or it depends on a goal with a lower depth. - self.stack[stack_depth].has_been_used - || self.stack[stack_depth].cycle_root_depth != stack_depth - } else { - false - } - } - - /// Fetches whether the current goal encountered overflow. - /// - /// This should only be used for the check in `evaluate_goal`. - pub(super) fn encountered_overflow(&self) -> bool { - if let Some(last) = self.stack.raw.last() { last.encountered_overflow } else { false } - } - - /// Resets `encountered_overflow` of the current goal. - /// - /// This should only be used for the check in `evaluate_goal`. - pub(super) fn reset_encountered_overflow(&mut self, encountered_overflow: bool) -> bool { - if let Some(last) = self.stack.raw.last_mut() { - let prev = last.encountered_overflow; - last.encountered_overflow = encountered_overflow; - prev - } else { - false - } + pub(super) fn current_goal_is_normalizes_to(&self) -> bool { + self.stack.raw.last().map_or(false, |e| { + matches!( + e.input.value.goal.predicate.kind().skip_binder(), + ty::PredicateKind::NormalizesTo(..) + ) + }) } /// Returns the remaining depth allowed for nested goals. @@ -269,7 +247,7 @@ impl<'tcx> SearchGraph<'tcx> { // in unstable results due to incompleteness. // // However, a test for this would be an even more complex version of - // tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.rs. + // tests/ui/traits/next-solver/coinduction/incompleteness-unstable-result.rs. // I did not bother to write such a test and we have no regression test // for this. It would be good to have such a test :) #[allow(rustc::potential_query_instability)] @@ -280,7 +258,7 @@ impl<'tcx> SearchGraph<'tcx> { // until we reach a fixpoint. It is not enough to simply retry the // `root` goal of this cycle. // - // See tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.rs + // See tests/ui/traits/next-solver/cycles/fixpoint-rerun-all-cycle-heads.rs // for an example. self.stack[stack_depth].has_been_used = true; return if let Some(result) = self.stack[stack_depth].provisional_result { diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs index a0e2ad6e2..ac3ffd2d6 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -1,12 +1,14 @@ //! Dealing with trait goals, i.e. `T: Trait<'a, U>`. -use super::assembly::{self, structural_traits}; -use super::{EvalCtxt, SolverMode}; +use super::assembly::{self, structural_traits, Candidate}; +use super::{EvalCtxt, GoalSource, SolverMode}; use rustc_hir::def_id::DefId; use rustc_hir::{LangItem, Movability}; use rustc_infer::traits::query::NoSolution; use rustc_middle::traits::solve::inspect::ProbeKind; -use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; +use rustc_middle::traits::solve::{ + CandidateSource, CanonicalResponse, Certainty, Goal, QueryResult, +}; use rustc_middle::traits::{BuiltinImplSource, Reveal}; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams, TreatProjections}; use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt}; @@ -22,10 +24,6 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { self.trait_ref } - fn polarity(self) -> ty::ImplPolarity { - self.polarity - } - fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self { self.with_self_ty(tcx, self_ty) } @@ -38,14 +36,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, TraitPredicate<'tcx>>, impl_def_id: DefId, - ) -> QueryResult<'tcx> { + ) -> Result<Candidate<'tcx>, NoSolution> { let tcx = ecx.tcx(); let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; - if !drcx - .args_refs_may_unify(goal.predicate.trait_ref.args, impl_trait_ref.skip_binder().args) - { + if !drcx.args_may_unify(goal.predicate.trait_ref.args, impl_trait_ref.skip_binder().args) { return Err(NoSolution); } @@ -65,7 +61,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { }, }; - ecx.probe_misc_candidate("impl").enter(|ecx| { + ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| { let impl_args = ecx.fresh_args_for_item(impl_def_id); let impl_trait_ref = impl_trait_ref.instantiate(tcx, impl_args); @@ -76,7 +72,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { .predicates .into_iter() .map(|pred| goal.with(tcx, pred)); - ecx.add_goals(where_clause_bounds); + ecx.add_goals(GoalSource::ImplWhereBound, where_clause_bounds); ecx.evaluate_added_goals_and_make_canonical_response(maximal_certainty) }) @@ -176,7 +172,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let nested_obligations = tcx .predicates_of(goal.predicate.def_id()) .instantiate(tcx, goal.predicate.trait_ref.args); - ecx.add_goals(nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p))); + // FIXME(-Znext-solver=coinductive): Should this be `GoalSource::ImplWhereBound`? + ecx.add_goals( + GoalSource::Misc, + nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)), + ); ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -260,7 +260,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { Err(NoSolution) } } - ty::ImplPolarity::Reservation => bug!(), + // FIXME: Goal polarity should be split from impl polarity + ty::ImplPolarity::Reservation => { + bug!("we never expect a `Reservation` polarity in a trait goal") + } } } @@ -374,6 +377,30 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } + fn consider_builtin_async_iterator_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + if goal.predicate.polarity != ty::ImplPolarity::Positive { + return Err(NoSolution); + } + + let ty::Coroutine(def_id, _, _) = *goal.predicate.self_ty().kind() else { + return Err(NoSolution); + }; + + // Coroutines are not iterators unless they come from `gen` desugaring + let tcx = ecx.tcx(); + if !tcx.coroutine_is_async_gen(def_id) { + return Err(NoSolution); + } + + // Gen coroutines unconditionally implement `Iterator` + // Technically, we need to check that the iterator output type is Sized, + // but that's already proven by the coroutines being WF. + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + fn consider_builtin_coroutine_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, @@ -425,7 +452,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { return Err(NoSolution); } - // FIXME(-Ztrait-solver=next): Implement this when we get const working in the new solver + // FIXME(-Znext-solver): Implement this when we get const working in the new solver // `Destruct` is automatically implemented for every type in // non-const environments. @@ -471,7 +498,7 @@ 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 destructured as a `dyn Trait`. let Some(b_ty) = - ecx.try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1))? + ecx.try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1)) else { return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW); }; @@ -489,17 +516,23 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Check that the type implements all of the predicates of the trait object. // (i.e. the principal, all of the associated types match, and any auto traits) - ecx.add_goals(b_data.iter().map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty)))); + ecx.add_goals( + GoalSource::ImplWhereBound, + b_data.iter().map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty))), + ); // The type must be `Sized` to be unsized. if let Some(sized_def_id) = tcx.lang_items().sized_trait() { - ecx.add_goal(goal.with(tcx, ty::TraitRef::new(tcx, sized_def_id, [a_ty]))); + ecx.add_goal( + GoalSource::ImplWhereBound, + goal.with(tcx, ty::TraitRef::new(tcx, sized_def_id, [a_ty])), + ); } else { return Err(NoSolution); } // The type must outlive the lifetime of the `dyn` we're unsizing into. - ecx.add_goal(goal.with(tcx, ty::OutlivesPredicate(a_ty, b_region))); + ecx.add_goal(GoalSource::Misc, goal.with(tcx, ty::OutlivesPredicate(a_ty, b_region))); ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -538,9 +571,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let b_ty = match ecx .try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1)) { - Ok(Some(b_ty)) => b_ty, - Ok(None) => return vec![misc_candidate(ecx, Certainty::OVERFLOW)], - Err(_) => return vec![], + Some(b_ty) => b_ty, + None => return vec![misc_candidate(ecx, Certainty::OVERFLOW)], }; let goal = goal.with(ecx.tcx(), (a_ty, b_ty)); @@ -727,11 +759,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } // Also require that a_ty's lifetime outlives b_ty's lifetime. - self.add_goal(Goal::new( - self.tcx(), - param_env, - ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region)), - )); + self.add_goal( + GoalSource::ImplWhereBound, + Goal::new( + self.tcx(), + param_env, + ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region)), + ), + ); self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } @@ -804,14 +839,17 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // Finally, we require that `TailA: Unsize<TailB>` for the tail field // types. self.eq(goal.param_env, unsized_a_ty, b_ty)?; - self.add_goal(goal.with( - tcx, - ty::TraitRef::new( + self.add_goal( + GoalSource::ImplWhereBound, + goal.with( tcx, - tcx.lang_items().unsize_trait().unwrap(), - [a_tail_ty, b_tail_ty], + ty::TraitRef::new( + tcx, + tcx.lang_items().unsize_trait().unwrap(), + [a_tail_ty, b_tail_ty], + ), ), - )); + ); self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } @@ -843,14 +881,17 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.eq(goal.param_env, unsized_a_ty, b_ty)?; // Similar to ADTs, require that we can unsize the tail. - self.add_goal(goal.with( - tcx, - ty::TraitRef::new( + self.add_goal( + GoalSource::ImplWhereBound, + goal.with( tcx, - tcx.lang_items().unsize_trait().unwrap(), - [a_last_ty, b_last_ty], + ty::TraitRef::new( + tcx, + tcx.lang_items().unsize_trait().unwrap(), + [a_last_ty, b_last_ty], + ), ), - )); + ); self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } @@ -959,6 +1000,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> QueryResult<'tcx> { self.probe_misc_candidate("constituent tys").enter(|ecx| { ecx.add_goals( + GoalSource::ImplWhereBound, constituent_tys(ecx, goal.predicate.self_ty())? .into_iter() .map(|ty| goal.with(ecx.tcx(), goal.predicate.with_self_ty(ecx.tcx(), ty))) |