diff options
Diffstat (limited to 'compiler/rustc_next_trait_solver/src')
11 files changed, 327 insertions, 113 deletions
diff --git a/compiler/rustc_next_trait_solver/src/canonicalizer.rs b/compiler/rustc_next_trait_solver/src/canonicalizer.rs index da05c49756f..a8f2b4e8db6 100644 --- a/compiler/rustc_next_trait_solver/src/canonicalizer.rs +++ b/compiler/rustc_next_trait_solver/src/canonicalizer.rs @@ -2,9 +2,8 @@ use rustc_type_ir::data_structures::{HashMap, ensure_sufficient_stack}; use rustc_type_ir::inherent::*; use rustc_type_ir::solve::{Goal, QueryInput}; use rustc_type_ir::{ - self as ty, Canonical, CanonicalParamEnvCacheEntry, CanonicalTyVarKind, CanonicalVarKind, - Flags, InferCtxtLike, Interner, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable, - TypeVisitableExt, + self as ty, Canonical, CanonicalParamEnvCacheEntry, CanonicalVarKind, Flags, InferCtxtLike, + Interner, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, }; use crate::delegate::SolverDelegate; @@ -68,6 +67,13 @@ pub struct Canonicalizer<'a, D: SolverDelegate<Interner = I>, I: Interner> { variables: &'a mut Vec<I::GenericArg>, var_kinds: Vec<CanonicalVarKind<I>>, variable_lookup_table: HashMap<I::GenericArg, usize>, + /// Maps each `sub_unification_table_root_var` to the index of the first + /// variable which used it. + /// + /// This means in case two type variables have the same sub relations root, + /// we set the `sub_root` of the second variable to the position of the first. + /// Otherwise the `sub_root` of each type variable is just its own position. + sub_root_lookup_table: HashMap<ty::TyVid, usize>, binder_index: ty::DebruijnIndex, /// We only use the debruijn index during lookup. We don't need to @@ -89,6 +95,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { variables, variable_lookup_table: Default::default(), + sub_root_lookup_table: Default::default(), var_kinds: Vec::new(), binder_index: ty::INNERMOST, @@ -133,6 +140,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { variables: &mut variables, variable_lookup_table: Default::default(), + sub_root_lookup_table: Default::default(), var_kinds: Vec::new(), binder_index: ty::INNERMOST, @@ -140,6 +148,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { }; let param_env = param_env.fold_with(&mut env_canonicalizer); debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST); + debug_assert!(env_canonicalizer.sub_root_lookup_table.is_empty()); CanonicalParamEnvCacheEntry { param_env, variable_lookup_table: env_canonicalizer.variable_lookup_table, @@ -165,6 +174,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { variables, variable_lookup_table: Default::default(), + sub_root_lookup_table: Default::default(), var_kinds: Vec::new(), binder_index: ty::INNERMOST, @@ -172,6 +182,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { }; let param_env = param_env.fold_with(&mut env_canonicalizer); debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST); + debug_assert!(env_canonicalizer.sub_root_lookup_table.is_empty()); (param_env, env_canonicalizer.variable_lookup_table, env_canonicalizer.var_kinds) } } @@ -200,6 +211,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { variables, variable_lookup_table, + sub_root_lookup_table: Default::default(), var_kinds, binder_index: ty::INNERMOST, @@ -266,6 +278,13 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { ty::BoundVar::from(idx) } + fn get_or_insert_sub_root(&mut self, vid: ty::TyVid) -> ty::BoundVar { + let root_vid = self.delegate.sub_unification_table_root_var(vid); + let idx = + *self.sub_root_lookup_table.entry(root_vid).or_insert_with(|| self.variables.len()); + ty::BoundVar::from(idx) + } + fn finalize(self) -> (ty::UniverseIndex, I::CanonicalVarKinds) { let mut var_kinds = self.var_kinds; // See the rustc-dev-guide section about how we deal with universes @@ -313,18 +332,15 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { "ty vid should have been resolved fully before canonicalization" ); - match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => CanonicalVarKind::Ty( - CanonicalTyVarKind::General(ty::UniverseIndex::ROOT), - ), - CanonicalizeMode::Response { .. } => { - CanonicalVarKind::Ty(CanonicalTyVarKind::General( - self.delegate.universe_of_ty(vid).unwrap_or_else(|| { - panic!("ty var should have been resolved: {t:?}") - }), - )) - } - } + let sub_root = self.get_or_insert_sub_root(vid); + let ui = match self.canonicalize_mode { + CanonicalizeMode::Input { .. } => ty::UniverseIndex::ROOT, + CanonicalizeMode::Response { .. } => self + .delegate + .universe_of_ty(vid) + .unwrap_or_else(|| panic!("ty var should have been resolved: {t:?}")), + }; + CanonicalVarKind::Ty { ui, sub_root } } ty::IntVar(vid) => { debug_assert_eq!( @@ -332,7 +348,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { t, "ty vid should have been resolved fully before canonicalization" ); - CanonicalVarKind::Ty(CanonicalTyVarKind::Int) + CanonicalVarKind::Int } ty::FloatVar(vid) => { debug_assert_eq!( @@ -340,7 +356,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { t, "ty vid should have been resolved fully before canonicalization" ); - CanonicalVarKind::Ty(CanonicalTyVarKind::Float) + CanonicalVarKind::Float } ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => { panic!("fresh vars not expected in canonicalization") diff --git a/compiler/rustc_next_trait_solver/src/coherence.rs b/compiler/rustc_next_trait_solver/src/coherence.rs index 79219b34e29..b949deb1192 100644 --- a/compiler/rustc_next_trait_solver/src/coherence.rs +++ b/compiler/rustc_next_trait_solver/src/coherence.rs @@ -435,7 +435,21 @@ where } } ty::Error(_) => ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)), - ty::Closure(did, ..) | ty::CoroutineClosure(did, ..) | ty::Coroutine(did, ..) => { + ty::Closure(did, ..) => { + if self.def_id_is_local(did) { + ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) + } else { + self.found_non_local_ty(ty) + } + } + ty::CoroutineClosure(did, ..) => { + if self.def_id_is_local(did) { + ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) + } else { + self.found_non_local_ty(ty) + } + } + ty::Coroutine(did, ..) => { if self.def_id_is_local(did) { ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) } else { diff --git a/compiler/rustc_next_trait_solver/src/delegate.rs b/compiler/rustc_next_trait_solver/src/delegate.rs index 7b932010d49..41c2e5f60ec 100644 --- a/compiler/rustc_next_trait_solver/src/delegate.rs +++ b/compiler/rustc_next_trait_solver/src/delegate.rs @@ -57,12 +57,14 @@ pub trait SolverDelegate: Deref<Target = Self::Infcx> + Sized { where V: TypeFoldable<Self::Interner>; - fn instantiate_canonical_var_with_infer( + fn instantiate_canonical_var( &self, kind: ty::CanonicalVarKind<Self::Interner>, span: <Self::Interner as Interner>::Span, + var_values: &[<Self::Interner as Interner>::GenericArg], universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, ) -> <Self::Interner as Interner>::GenericArg; + fn add_item_bounds_for_hidden_type( &self, def_id: <Self::Interner as Interner>::DefId, @@ -76,7 +78,7 @@ pub trait SolverDelegate: Deref<Target = Self::Infcx> + Sized { &self, goal_trait_ref: ty::TraitRef<Self::Interner>, trait_assoc_def_id: <Self::Interner as Interner>::DefId, - impl_def_id: <Self::Interner as Interner>::DefId, + impl_def_id: <Self::Interner as Interner>::ImplId, ) -> Result< Option<<Self::Interner as Interner>::DefId>, <Self::Interner as Interner>::ErrorGuaranteed, diff --git a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs index be7e4dd4cda..fb777496e31 100644 --- a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs @@ -11,8 +11,9 @@ use rustc_type_ir::lang_items::SolverTraitLangItem; use rustc_type_ir::search_graph::CandidateHeadUsages; use rustc_type_ir::solve::SizedTraitKind; use rustc_type_ir::{ - self as ty, Interner, TypeFlags, TypeFoldable, TypeSuperVisitable, TypeVisitable, - TypeVisitableExt as _, TypeVisitor, TypingMode, Upcast as _, elaborate, + self as ty, Interner, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable, + TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor, TypingMode, Upcast, + elaborate, }; use tracing::{debug, instrument}; @@ -186,7 +187,8 @@ where fn consider_impl_candidate( ecx: &mut EvalCtxt<'_, D>, goal: Goal<I, Self>, - impl_def_id: I::DefId, + impl_def_id: I::ImplId, + then: impl FnOnce(&mut EvalCtxt<'_, D>, Certainty) -> QueryResult<I>, ) -> Result<Candidate<I>, NoSolution>; /// If the predicate contained an error, we want to avoid emitting unnecessary trait @@ -365,6 +367,15 @@ pub(super) enum AssembleCandidatesFrom { EnvAndBounds, } +impl AssembleCandidatesFrom { + fn should_assemble_impl_candidates(&self) -> bool { + match self { + AssembleCandidatesFrom::All => true, + AssembleCandidatesFrom::EnvAndBounds => false, + } + } +} + /// This is currently used to track the [CandidateHeadUsages] of all failed `ParamEnv` /// candidates. This is then used to ignore their head usages in case there's another /// always applicable `ParamEnv` candidate. Look at how `param_env_head_usages` is @@ -397,14 +408,15 @@ where return (candidates, failed_candidate_info); }; + let goal: Goal<I, G> = goal + .with(self.cx(), goal.predicate.with_replaced_self_ty(self.cx(), normalized_self_ty)); + if normalized_self_ty.is_ty_var() { debug!("self type has been normalized to infer"); - candidates.extend(self.forced_ambiguity(MaybeCause::Ambiguity)); + self.try_assemble_bounds_via_registered_opaques(goal, assemble_from, &mut candidates); return (candidates, failed_candidate_info); } - let goal: Goal<I, G> = goal - .with(self.cx(), goal.predicate.with_replaced_self_ty(self.cx(), normalized_self_ty)); // Vars that show up in the rest of the goal substs may have been constrained by // normalizing the self type as well, since type variables are not uniquified. let goal = self.resolve_vars_if_possible(goal); @@ -484,8 +496,9 @@ where if cx.impl_is_default(impl_def_id) { return; } - - match G::consider_impl_candidate(self, goal, impl_def_id) { + match G::consider_impl_candidate(self, goal, impl_def_id, |ecx, certainty| { + ecx.evaluate_added_goals_and_make_canonical_response(certainty) + }) { Ok(candidate) => candidates.push(candidate), Err(NoSolution) => (), } @@ -943,6 +956,116 @@ where } } + /// If the self type is the hidden type of an opaque, try to assemble + /// candidates for it by consider its item bounds and by using blanket + /// impls. This is used to incompletely guide type inference when handling + /// non-defining uses in the defining scope. + /// + /// We otherwise just fail fail with ambiguity. Even if we're using an + /// opaque type item bound or a blank impls, we still force its certainty + /// to be `Maybe` so that we properly prove this goal later. + /// + /// See <https://github.com/rust-lang/trait-system-refactor-initiative/issues/182> + /// for why this is necessary. + fn try_assemble_bounds_via_registered_opaques<G: GoalKind<D>>( + &mut self, + goal: Goal<I, G>, + assemble_from: AssembleCandidatesFrom, + candidates: &mut Vec<Candidate<I>>, + ) { + let self_ty = goal.predicate.self_ty(); + // If the self type is sub unified with any opaque type, we + // also look at blanket impls for it. + let mut assemble_blanket_impls = false; + for alias_ty in self.opaques_with_sub_unified_hidden_type(self_ty) { + assemble_blanket_impls = true; + debug!("self ty is sub unified with {alias_ty:?}"); + + struct ReplaceOpaque<I: Interner> { + cx: I, + alias_ty: ty::AliasTy<I>, + self_ty: I::Ty, + } + impl<I: Interner> TypeFolder<I> for ReplaceOpaque<I> { + fn cx(&self) -> I { + self.cx + } + fn fold_ty(&mut self, ty: I::Ty) -> I::Ty { + if let ty::Alias(ty::Opaque, alias_ty) = ty.kind() { + if alias_ty == self.alias_ty { + return self.self_ty; + } + } + ty.super_fold_with(self) + } + } + + // We look at all item-bounds of the opaque, replacing the + // opaque with the current self type before considering + // them as a candidate. Imagine e've got `?x: Trait<?y>` + // and `?x` has been sub-unified with the hidden type of + // `impl Trait<u32>`, We take the item bound `opaque: Trait<u32>` + // and replace all occurrences of `opaque` with `?x`. This results + // in a `?x: Trait<u32>` alias-bound candidate. + for item_bound in self + .cx() + .item_self_bounds(alias_ty.def_id) + .iter_instantiated(self.cx(), alias_ty.args) + { + let assumption = + item_bound.fold_with(&mut ReplaceOpaque { cx: self.cx(), alias_ty, self_ty }); + candidates.extend(G::probe_and_match_goal_against_assumption( + self, + CandidateSource::AliasBound, + goal, + assumption, + |ecx| { + // We want to reprove this goal once we've inferred the + // hidden type, so we force the certainty to `Maybe`. + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + }, + )); + } + } + + // We also need to consider blanket impls for not-yet-defined opaque types. + // + // See tests/ui/impl-trait/non-defining-uses/use-blanket-impl.rs for an example. + if assemble_blanket_impls && assemble_from.should_assemble_impl_candidates() { + let cx = self.cx(); + cx.for_each_blanket_impl(goal.predicate.trait_def_id(cx), |impl_def_id| { + // For every `default impl`, there's always a non-default `impl` + // that will *also* apply. There's no reason to register a candidate + // for this impl, since it is *not* proof that the trait goal holds. + if cx.impl_is_default(impl_def_id) { + return; + } + + match G::consider_impl_candidate(self, goal, impl_def_id, |ecx, certainty| { + if ecx.shallow_resolve(self_ty).is_ty_var() { + // We force the certainty of impl candidates to be `Maybe`. + let certainty = certainty.and(Certainty::AMBIGUOUS); + ecx.evaluate_added_goals_and_make_canonical_response(certainty) + } else { + // We don't want to use impls if they constrain the opaque. + // + // FIXME(trait-system-refactor-initiative#229): This isn't + // perfect yet as it still allows us to incorrectly constrain + // other inference variables. + Err(NoSolution) + } + }) { + Ok(candidate) => candidates.push(candidate), + Err(NoSolution) => (), + } + }); + } + + if candidates.is_empty() { + candidates.extend(self.forced_ambiguity(MaybeCause::Ambiguity)); + } + } + /// Assemble and merge candidates for goals which are related to an underlying trait /// goal. Right now, this is normalizes-to and host effect goals. /// diff --git a/compiler/rustc_next_trait_solver/src/solve/assembly/structural_traits.rs b/compiler/rustc_next_trait_solver/src/solve/assembly/structural_traits.rs index 7c5940828da..f6eab286ba7 100644 --- a/compiler/rustc_next_trait_solver/src/solve/assembly/structural_traits.rs +++ b/compiler/rustc_next_trait_solver/src/solve/assembly/structural_traits.rs @@ -605,7 +605,7 @@ fn coroutine_closure_to_certain_coroutine<I: Interner>( cx: I, goal_kind: ty::ClosureKind, goal_region: I::Region, - def_id: I::DefId, + def_id: I::CoroutineClosureId, args: ty::CoroutineClosureArgs<I>, sig: ty::CoroutineClosureSignature<I>, ) -> I::Ty { @@ -629,7 +629,7 @@ fn coroutine_closure_to_ambiguous_coroutine<I: Interner>( cx: I, goal_kind: ty::ClosureKind, goal_region: I::Region, - def_id: I::DefId, + def_id: I::CoroutineClosureId, args: ty::CoroutineClosureArgs<I>, sig: ty::CoroutineClosureSignature<I>, ) -> I::Ty { @@ -664,7 +664,7 @@ fn coroutine_closure_to_ambiguous_coroutine<I: Interner>( pub(in crate::solve) fn extract_fn_def_from_const_callable<I: Interner>( cx: I, self_ty: I::Ty, -) -> Result<(ty::Binder<I, (I::FnInputTys, I::Ty)>, I::DefId, I::GenericArgs), NoSolution> { +) -> Result<(ty::Binder<I, (I::FnInputTys, I::Ty)>, I::FunctionId, I::GenericArgs), NoSolution> { match self_ty.kind() { ty::FnDef(def_id, args) => { let sig = cx.fn_sig(def_id); diff --git a/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs b/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs index 229345065b1..cb72c1cd92b 100644 --- a/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs +++ b/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs @@ -123,7 +123,8 @@ where fn consider_impl_candidate( ecx: &mut EvalCtxt<'_, D>, goal: Goal<I, Self>, - impl_def_id: I::DefId, + impl_def_id: I::ImplId, + then: impl FnOnce(&mut EvalCtxt<'_, D>, Certainty) -> QueryResult<I>, ) -> Result<Candidate<I>, NoSolution> { let cx = ecx.cx(); @@ -152,20 +153,20 @@ where } ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| { - let impl_args = ecx.fresh_args_for_item(impl_def_id); + let impl_args = ecx.fresh_args_for_item(impl_def_id.into()); ecx.record_impl_args(impl_args); let impl_trait_ref = impl_trait_ref.instantiate(cx, impl_args); ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?; let where_clause_bounds = cx - .predicates_of(impl_def_id) + .predicates_of(impl_def_id.into()) .iter_instantiated(cx, impl_args) .map(|pred| goal.with(cx, pred)); ecx.add_goals(GoalSource::ImplWhereBound, where_clause_bounds); // For this impl to be `const`, we need to check its `[const]` bounds too. let const_conditions = cx - .const_conditions(impl_def_id) + .const_conditions(impl_def_id.into()) .iter_instantiated(cx, impl_args) .map(|bound_trait_ref| { goal.with( @@ -175,7 +176,7 @@ where }); ecx.add_goals(GoalSource::ImplWhereBound, const_conditions); - ecx.evaluate_added_goals_and_make_canonical_response(certainty) + then(ecx, certainty) }) } @@ -240,7 +241,7 @@ where ty::TraitRef::new(cx, cx.require_trait_lang_item(SolverTraitLangItem::Sized), [output]) }); let requirements = cx - .const_conditions(def_id) + .const_conditions(def_id.into()) .iter_instantiated(cx, args) .map(|trait_ref| { ( diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs index 6f9f4067384..169832ca5fb 100644 --- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs +++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs @@ -16,7 +16,8 @@ use rustc_type_ir::data_structures::HashSet; use rustc_type_ir::inherent::*; use rustc_type_ir::relate::solver_relating::RelateExt; use rustc_type_ir::{ - self as ty, Canonical, CanonicalVarValues, InferCtxtLike, Interner, TypeFoldable, + self as ty, Canonical, CanonicalVarKind, CanonicalVarValues, InferCtxtLike, Interner, + TypeFoldable, }; use tracing::{debug, instrument, trace}; @@ -336,7 +337,16 @@ where { match result_value.kind() { ty::GenericArgKind::Type(t) => { - if let ty::Bound(debruijn, b) = t.kind() { + // We disable the instantiation guess for inference variables + // and only use it for placeholders. We need to handle the + // `sub_root` of type inference variables which would make this + // more involved. They are also a lot rarer than region variables. + if let ty::Bound(debruijn, b) = t.kind() + && !matches!( + response.variables.get(b.var().as_usize()).unwrap(), + CanonicalVarKind::Ty { .. } + ) + { assert_eq!(debruijn, ty::INNERMOST); opt_values[b.var()] = Some(*original_value); } @@ -355,39 +365,33 @@ where } } } - - let var_values = delegate.cx().mk_args_from_iter( - response.variables.iter().enumerate().map(|(index, var_kind)| { - if var_kind.universe() != ty::UniverseIndex::ROOT { - // A variable from inside a binder of the query. While ideally these shouldn't - // exist at all (see the FIXME at the start of this method), we have to deal with - // them for now. - delegate.instantiate_canonical_var_with_infer(var_kind, span, |idx| { - prev_universe + idx.index() - }) - } else if var_kind.is_existential() { - // As an optimization we sometimes avoid creating a new inference variable here. - // - // All new inference variables we create start out in the current universe of the caller. - // This is conceptually wrong as these inference variables would be able to name - // more placeholders then they should be able to. However the inference variables have - // to "come from somewhere", so by equating them with the original values of the caller - // later on, we pull them down into their correct universe again. - if let Some(v) = opt_values[ty::BoundVar::from_usize(index)] { - v - } else { - delegate - .instantiate_canonical_var_with_infer(var_kind, span, |_| prev_universe) - } + CanonicalVarValues::instantiate(delegate.cx(), response.variables, |var_values, kind| { + if kind.universe() != ty::UniverseIndex::ROOT { + // A variable from inside a binder of the query. While ideally these shouldn't + // exist at all (see the FIXME at the start of this method), we have to deal with + // them for now. + delegate.instantiate_canonical_var(kind, span, &var_values, |idx| { + prev_universe + idx.index() + }) + } else if kind.is_existential() { + // As an optimization we sometimes avoid creating a new inference variable here. + // + // All new inference variables we create start out in the current universe of the caller. + // This is conceptually wrong as these inference variables would be able to name + // more placeholders then they should be able to. However the inference variables have + // to "come from somewhere", so by equating them with the original values of the caller + // later on, we pull them down into their correct universe again. + if let Some(v) = opt_values[ty::BoundVar::from_usize(var_values.len())] { + v } else { - // For placeholders which were already part of the input, we simply map this - // universal bound variable back the placeholder of the input. - original_values[var_kind.expect_placeholder_index()] + delegate.instantiate_canonical_var(kind, span, &var_values, |_| prev_universe) } - }), - ); - - CanonicalVarValues { var_values } + } else { + // For placeholders which were already part of the input, we simply map this + // universal bound variable back the placeholder of the input. + original_values[kind.expect_placeholder_index()] + } + }) } /// Unify the `original_values` with the `var_values` returned by the canonical query.. diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs index 443aebbdb4d..3e3a5246f3d 100644 --- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs @@ -407,20 +407,21 @@ where // If we have run this goal before, and it was stalled, check that any of the goal's // args have changed. Otherwise, we don't need to re-run the goal because it'll remain // stalled, since it'll canonicalize the same way and evaluation is pure. - if let Some(stalled_on) = stalled_on - && !stalled_on.stalled_vars.iter().any(|value| self.delegate.is_changed_arg(*value)) - && !self - .delegate - .opaque_types_storage_num_entries() - .needs_reevaluation(stalled_on.num_opaques) + if let Some(GoalStalledOn { num_opaques, ref stalled_vars, ref sub_roots, stalled_cause }) = + stalled_on + && !stalled_vars.iter().any(|value| self.delegate.is_changed_arg(*value)) + && !sub_roots + .iter() + .any(|&vid| self.delegate.sub_unification_table_root_var(vid) != vid) + && !self.delegate.opaque_types_storage_num_entries().needs_reevaluation(num_opaques) { return Ok(( NestedNormalizationGoals::empty(), GoalEvaluation { goal, - certainty: Certainty::Maybe(stalled_on.stalled_cause), + certainty: Certainty::Maybe(stalled_cause), has_changed: HasChanged::No, - stalled_on: Some(stalled_on), + stalled_on, }, )); } @@ -476,16 +477,6 @@ where HasChanged::No => { let mut stalled_vars = orig_values; - // Remove the canonicalized universal vars, since we only care about stalled existentials. - stalled_vars.retain(|arg| match arg.kind() { - ty::GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Infer(_)), - ty::GenericArgKind::Const(ct) => { - matches!(ct.kind(), ty::ConstKind::Infer(_)) - } - // Lifetimes can never stall goals. - ty::GenericArgKind::Lifetime(_) => false, - }); - // Remove the unconstrained RHS arg, which is expected to have changed. if let Some(normalizes_to) = goal.predicate.as_normalizes_to() { let normalizes_to = normalizes_to.skip_binder(); @@ -497,6 +488,27 @@ where stalled_vars.swap_remove(idx); } + // Remove the canonicalized universal vars, since we only care about stalled existentials. + let mut sub_roots = Vec::new(); + stalled_vars.retain(|arg| match arg.kind() { + // Lifetimes can never stall goals. + ty::GenericArgKind::Lifetime(_) => false, + ty::GenericArgKind::Type(ty) => match ty.kind() { + ty::Infer(ty::TyVar(vid)) => { + sub_roots.push(self.delegate.sub_unification_table_root_var(vid)); + true + } + ty::Infer(_) => true, + ty::Param(_) | ty::Placeholder(_) => false, + _ => unreachable!("unexpected orig_value: {ty:?}"), + }, + ty::GenericArgKind::Const(ct) => match ct.kind() { + ty::ConstKind::Infer(_) => true, + ty::ConstKind::Param(_) | ty::ConstKind::Placeholder(_) => false, + _ => unreachable!("unexpected orig_value: {ct:?}"), + }, + }); + Some(GoalStalledOn { num_opaques: canonical_goal .canonical @@ -505,6 +517,7 @@ where .opaque_types .len(), stalled_vars, + sub_roots, stalled_cause, }) } @@ -900,6 +913,10 @@ where && goal.param_env.visit_with(&mut visitor).is_continue() } + pub(super) fn sub_unify_ty_vids_raw(&self, a: ty::TyVid, b: ty::TyVid) { + self.delegate.sub_unify_ty_vids_raw(a, b) + } + #[instrument(level = "trace", skip(self, param_env), ret)] pub(super) fn eq<T: Relate<I>>( &mut self, @@ -1043,6 +1060,10 @@ where self.delegate.resolve_vars_if_possible(value) } + pub(super) fn shallow_resolve(&self, ty: I::Ty) -> I::Ty { + self.delegate.shallow_resolve(ty) + } + pub(super) fn eager_resolve_region(&self, r: I::Region) -> I::Region { if let ty::ReVar(vid) = r.kind() { self.delegate.opportunistic_resolve_lt_var(vid) @@ -1092,7 +1113,7 @@ where &self, goal_trait_ref: ty::TraitRef<I>, trait_assoc_def_id: I::DefId, - impl_def_id: I::DefId, + impl_def_id: I::ImplId, ) -> Result<Option<I::DefId>, I::ErrorGuaranteed> { self.delegate.fetch_eligible_assoc_item(goal_trait_ref, trait_assoc_def_id, impl_def_id) } @@ -1159,6 +1180,33 @@ where ) -> bool { may_use_unstable_feature(&**self.delegate, param_env, symbol) } + + pub(crate) fn opaques_with_sub_unified_hidden_type( + &self, + self_ty: I::Ty, + ) -> impl Iterator<Item = ty::AliasTy<I>> + use<'a, D, I> { + let delegate = self.delegate; + delegate + .clone_opaque_types_lookup_table() + .into_iter() + .chain(delegate.clone_duplicate_opaque_types()) + .filter_map(move |(key, hidden_ty)| { + if let ty::Infer(ty::TyVar(self_vid)) = self_ty.kind() { + if let ty::Infer(ty::TyVar(hidden_vid)) = hidden_ty.kind() { + if delegate.sub_unification_table_root_var(self_vid) + == delegate.sub_unification_table_root_var(hidden_vid) + { + return Some(ty::AliasTy::new_from_args( + delegate.cx(), + key.def_id.into(), + key.args, + )); + } + } + } + None + }) + } } /// Eagerly replace aliases with inference variables, emitting `AliasRelate` diff --git a/compiler/rustc_next_trait_solver/src/solve/mod.rs b/compiler/rustc_next_trait_solver/src/solve/mod.rs index 85f9d852d95..cd27c9c26c1 100644 --- a/compiler/rustc_next_trait_solver/src/solve/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/mod.rs @@ -24,7 +24,7 @@ mod trait_goals; use derive_where::derive_where; use rustc_type_ir::inherent::*; pub use rustc_type_ir::solve::*; -use rustc_type_ir::{self as ty, Interner, TypingMode}; +use rustc_type_ir::{self as ty, Interner, TyVid, TypingMode}; use tracing::instrument; pub use self::eval_ctxt::{ @@ -119,11 +119,15 @@ where #[instrument(level = "trace", skip(self))] fn compute_subtype_goal(&mut self, goal: Goal<I, ty::SubtypePredicate<I>>) -> QueryResult<I> { - if goal.predicate.a.is_ty_var() && goal.predicate.b.is_ty_var() { - self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) - } else { - self.sub(goal.param_env, goal.predicate.a, goal.predicate.b)?; - self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + match (goal.predicate.a.kind(), goal.predicate.b.kind()) { + (ty::Infer(ty::TyVar(a_vid)), ty::Infer(ty::TyVar(b_vid))) => { + self.sub_unify_ty_vids_raw(a_vid, b_vid); + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + } + _ => { + self.sub(goal.param_env, goal.predicate.a, goal.predicate.b)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } } } @@ -422,6 +426,7 @@ pub struct GoalEvaluation<I: Interner> { pub struct GoalStalledOn<I: Interner> { pub num_opaques: usize, pub stalled_vars: Vec<I::GenericArg>, + pub sub_roots: Vec<TyVid>, /// The cause that will be returned on subsequent evaluations if this goal remains stalled. pub stalled_cause: MaybeCause, } diff --git a/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs index cfdf2007391..54b92ebac1d 100644 --- a/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs @@ -5,7 +5,7 @@ mod opaque_types; use rustc_type_ir::fast_reject::DeepRejectCtxt; use rustc_type_ir::inherent::*; -use rustc_type_ir::lang_items::{SolverLangItem, SolverTraitLangItem}; +use rustc_type_ir::lang_items::{SolverAdtLangItem, SolverLangItem, SolverTraitLangItem}; use rustc_type_ir::solve::SizedTraitKind; use rustc_type_ir::{self as ty, Interner, NormalizesTo, PredicateKind, Upcast as _}; use tracing::instrument; @@ -193,7 +193,8 @@ where fn consider_impl_candidate( ecx: &mut EvalCtxt<'_, D>, goal: Goal<I, NormalizesTo<I>>, - impl_def_id: I::DefId, + impl_def_id: I::ImplId, + then: impl FnOnce(&mut EvalCtxt<'_, D>, Certainty) -> QueryResult<I>, ) -> Result<Candidate<I>, NoSolution> { let cx = ecx.cx(); @@ -217,13 +218,13 @@ where }; ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| { - let impl_args = ecx.fresh_args_for_item(impl_def_id); + let impl_args = ecx.fresh_args_for_item(impl_def_id.into()); let impl_trait_ref = impl_trait_ref.instantiate(cx, impl_args); ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; let where_clause_bounds = cx - .predicates_of(impl_def_id) + .predicates_of(impl_def_id.into()) .iter_instantiated(cx, impl_args) .map(|pred| goal.with(cx, pred)); ecx.add_goals(GoalSource::ImplWhereBound, where_clause_bounds); @@ -314,8 +315,7 @@ where // nested goal for consistency. ty::TypingMode::Coherence => { ecx.add_goal(GoalSource::Misc, goal.with(cx, PredicateKind::Ambiguous)); - return ecx - .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); + return then(ecx, Certainty::Yes); } ty::TypingMode::Analysis { .. } | ty::TypingMode::Borrowck { .. } @@ -325,8 +325,7 @@ where goal, goal.predicate.alias, ); - return ecx - .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); + return then(ecx, Certainty::Yes); } } } else { @@ -824,10 +823,10 @@ where // coroutine yield ty `Poll<Option<I>>`. let wrapped_expected_ty = Ty::new_adt( cx, - cx.adt_def(cx.require_lang_item(SolverLangItem::Poll)), + cx.adt_def(cx.require_adt_lang_item(SolverAdtLangItem::Poll)), cx.mk_args(&[Ty::new_adt( cx, - cx.adt_def(cx.require_lang_item(SolverLangItem::Option)), + cx.adt_def(cx.require_adt_lang_item(SolverAdtLangItem::Option)), cx.mk_args(&[expected_ty.into()]), ) .into()]), @@ -979,7 +978,7 @@ where fn translate_args( &mut self, goal: Goal<I, ty::NormalizesTo<I>>, - impl_def_id: I::DefId, + impl_def_id: I::ImplId, impl_args: I::GenericArgs, impl_trait_ref: rustc_type_ir::TraitRef<I>, target_container_def_id: I::DefId, @@ -988,14 +987,15 @@ where Ok(if target_container_def_id == impl_trait_ref.def_id.into() { // Default value from the trait definition. No need to rebase. goal.predicate.alias.args - } else if target_container_def_id == impl_def_id { + } else if target_container_def_id == impl_def_id.into() { // Same impl, no need to fully translate, just a rebase from // the trait is sufficient. goal.predicate.alias.args.rebase_onto(cx, impl_trait_ref.def_id.into(), impl_args) } else { let target_args = self.fresh_args_for_item(target_container_def_id); - let target_trait_ref = - cx.impl_trait_ref(target_container_def_id).instantiate(cx, target_args); + let target_trait_ref = cx + .impl_trait_ref(target_container_def_id.try_into().unwrap()) + .instantiate(cx, target_args); // Relate source impl to target impl by equating trait refs. self.eq(goal.param_env, impl_trait_ref, target_trait_ref)?; // Also add predicates since they may be needed to constrain the diff --git a/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs index cdcfebf2909..a69e867289c 100644 --- a/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs +++ b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs @@ -54,7 +54,8 @@ where fn consider_impl_candidate( ecx: &mut EvalCtxt<'_, D>, goal: Goal<I, TraitPredicate<I>>, - impl_def_id: I::DefId, + impl_def_id: I::ImplId, + then: impl FnOnce(&mut EvalCtxt<'_, D>, Certainty) -> QueryResult<I>, ) -> Result<Candidate<I>, NoSolution> { let cx = ecx.cx(); @@ -91,13 +92,13 @@ where }; ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| { - let impl_args = ecx.fresh_args_for_item(impl_def_id); + let impl_args = ecx.fresh_args_for_item(impl_def_id.into()); ecx.record_impl_args(impl_args); let impl_trait_ref = impl_trait_ref.instantiate(cx, impl_args); ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?; let where_clause_bounds = cx - .predicates_of(impl_def_id) + .predicates_of(impl_def_id.into()) .iter_instantiated(cx, impl_args) .map(|pred| goal.with(cx, pred)); ecx.add_goals(GoalSource::ImplWhereBound, where_clause_bounds); @@ -112,7 +113,7 @@ where .map(|pred| goal.with(cx, pred)), ); - ecx.evaluate_added_goals_and_make_canonical_response(maximal_certainty) + then(ecx, maximal_certainty) }) } |