diff options
Diffstat (limited to 'compiler/rustc_next_trait_solver/src')
9 files changed, 205 insertions, 126 deletions
diff --git a/compiler/rustc_next_trait_solver/src/canonicalizer.rs b/compiler/rustc_next_trait_solver/src/canonicalizer.rs index a418aa82100..1bc35e599c7 100644 --- a/compiler/rustc_next_trait_solver/src/canonicalizer.rs +++ b/compiler/rustc_next_trait_solver/src/canonicalizer.rs @@ -19,6 +19,20 @@ const NEEDS_CANONICAL: TypeFlags = TypeFlags::from_bits( ) .unwrap(); +#[derive(Debug, Clone, Copy)] +enum CanonicalizeInputKind { + /// When canonicalizing the `param_env`, we keep `'static` as merging + /// trait candidates relies on it when deciding whether a where-bound + /// is trivial. + ParamEnv, + /// When canonicalizing predicates, we don't keep `'static`. If we're + /// currently outside of the trait solver and canonicalize the root goal + /// during HIR typeck, we replace each occurance of a region with a + /// unique region variable. See the comment on `InferCtxt::in_hir_typeck` + /// for more details. + Predicate { is_hir_typeck_root_goal: bool }, +} + /// Whether we're canonicalizing a query input or the query response. /// /// When canonicalizing an input we're in the context of the caller @@ -26,10 +40,7 @@ const NEEDS_CANONICAL: TypeFlags = TypeFlags::from_bits( /// query. #[derive(Debug, Clone, Copy)] enum CanonicalizeMode { - /// When canonicalizing the `param_env`, we keep `'static` as merging - /// trait candidates relies on it when deciding whether a where-bound - /// is trivial. - Input { keep_static: bool }, + Input(CanonicalizeInputKind), /// FIXME: We currently return region constraints referring to /// placeholders and inference variables from a binder instantiated /// inside of the query. @@ -122,7 +133,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { let mut variables = Vec::new(); let mut env_canonicalizer = Canonicalizer { delegate, - canonicalize_mode: CanonicalizeMode::Input { keep_static: true }, + canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv), variables: &mut variables, variable_lookup_table: Default::default(), @@ -154,7 +165,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { } else { let mut env_canonicalizer = Canonicalizer { delegate, - canonicalize_mode: CanonicalizeMode::Input { keep_static: true }, + canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv), variables, variable_lookup_table: Default::default(), @@ -180,6 +191,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { pub fn canonicalize_input<P: TypeFoldable<I>>( delegate: &'a D, variables: &'a mut Vec<I::GenericArg>, + is_hir_typeck_root_goal: bool, input: QueryInput<I, P>, ) -> ty::Canonical<I, QueryInput<I, P>> { // First canonicalize the `param_env` while keeping `'static` @@ -189,7 +201,9 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { // while *mostly* reusing the canonicalizer from above. let mut rest_canonicalizer = Canonicalizer { delegate, - canonicalize_mode: CanonicalizeMode::Input { keep_static: false }, + canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { + is_hir_typeck_root_goal, + }), variables, variable_lookup_table, @@ -296,7 +310,7 @@ impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> { } } - fn cached_fold_ty(&mut self, t: I::Ty) -> I::Ty { + fn inner_fold_ty(&mut self, t: I::Ty) -> I::Ty { let kind = match t.kind() { ty::Infer(i) => match i { ty::TyVar(vid) => { @@ -413,10 +427,10 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz // We don't canonicalize `ReStatic` in the `param_env` as we use it // when checking whether a `ParamEnv` candidate is global. ty::ReStatic => match self.canonicalize_mode { - CanonicalizeMode::Input { keep_static: false } => { + CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => { CanonicalVarKind::Region(ty::UniverseIndex::ROOT) } - CanonicalizeMode::Input { keep_static: true } + CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv) | CanonicalizeMode::Response { .. } => return r, }, @@ -428,12 +442,12 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz // `ReErased`. We may be able to short-circuit registering region // obligations if we encounter a `ReErased` on one side, for example. ty::ReErased | ty::ReError(_) => match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), CanonicalizeMode::Response { .. } => return r, }, ty::ReEarlyParam(_) | ty::ReLateParam(_) => match self.canonicalize_mode { - CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), CanonicalizeMode::Response { .. } => { panic!("unexpected region in response: {r:?}") } @@ -441,7 +455,7 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz ty::RePlaceholder(placeholder) => match self.canonicalize_mode { // We canonicalize placeholder regions as existentials in query inputs. - CanonicalizeMode::Input { .. } => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + 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. @@ -459,9 +473,7 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz "region vid should have been resolved fully before canonicalization" ); match self.canonicalize_mode { - CanonicalizeMode::Input { keep_static: _ } => { - CanonicalVarKind::Region(ty::UniverseIndex::ROOT) - } + CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), CanonicalizeMode::Response { .. } => { CanonicalVarKind::Region(self.delegate.universe_of_lt(vid).unwrap()) } @@ -469,16 +481,34 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz } }; - let var = self.get_or_insert_bound_var(r, kind); + let var = if let CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { + is_hir_typeck_root_goal: true, + }) = self.canonicalize_mode + { + let var = ty::BoundVar::from(self.variables.len()); + self.variables.push(r.into()); + self.var_kinds.push(kind); + var + } else { + self.get_or_insert_bound_var(r, kind) + }; Region::new_anon_bound(self.cx(), self.binder_index, var) } fn fold_ty(&mut self, t: I::Ty) -> I::Ty { - if let Some(&ty) = self.cache.get(&(self.binder_index, t)) { + if let CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { + is_hir_typeck_root_goal: true, + }) = self.canonicalize_mode + { + // If we're canonicalizing a root goal during HIR typeck, we + // must not use the `cache` as we want to map each occurrence + // of a region to a unique existential variable. + self.inner_fold_ty(t) + } else if let Some(&ty) = self.cache.get(&(self.binder_index, t)) { ty } else { - let res = self.cached_fold_ty(t); + let res = self.inner_fold_ty(t); let old = self.cache.insert((self.binder_index, t), res); assert_eq!(old, None); res @@ -541,9 +571,9 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicaliz fn fold_clauses(&mut self, c: I::Clauses) -> I::Clauses { match self.canonicalize_mode { - CanonicalizeMode::Input { keep_static: true } + CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv) | CanonicalizeMode::Response { max_input_universe: _ } => {} - CanonicalizeMode::Input { keep_static: false } => { + CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => { panic!("erasing 'static in env") } } 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 b2d40146348..5e08c3a03d8 100644 --- a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs @@ -21,7 +21,7 @@ use crate::delegate::SolverDelegate; use crate::solve::inspect::ProbeKind; use crate::solve::{ BuiltinImplSource, CandidateSource, CanonicalResponse, Certainty, EvalCtxt, Goal, GoalSource, - MaybeCause, NoSolution, ParamEnvSource, QueryResult, + MaybeCause, NoSolution, ParamEnvSource, QueryResult, has_no_inference_or_external_constraints, }; enum AliasBoundKind { @@ -50,7 +50,7 @@ where fn trait_ref(self, cx: I) -> ty::TraitRef<I>; - fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self; + fn with_replaced_self_ty(self, cx: I, self_ty: I::Ty) -> Self; fn trait_def_id(self, cx: I) -> I::DefId; @@ -376,8 +376,8 @@ where return self.forced_ambiguity(MaybeCause::Ambiguity).into_iter().collect(); } - let goal: Goal<I, G> = - goal.with(self.cx(), goal.predicate.with_self_ty(self.cx(), normalized_self_ty)); + 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); @@ -395,9 +395,30 @@ where match assemble_from { AssembleCandidatesFrom::All => { - self.assemble_impl_candidates(goal, &mut candidates); self.assemble_builtin_impl_candidates(goal, &mut candidates); - self.assemble_object_bound_candidates(goal, &mut candidates); + // For performance we only assemble impls if there are no candidates + // which would shadow them. This is necessary to avoid hangs in rayon, + // see trait-system-refactor-initiative#109 for more details. + // + // We always assemble builtin impls as trivial builtin impls have a higher + // priority than where-clauses. + // + // We only do this if any such candidate applies without any constraints + // as we may want to weaken inference guidance in the future and don't want + // to worry about causing major performance regressions when doing so. + // See trait-system-refactor-initiative#226 for some ideas here. + if TypingMode::Coherence == self.typing_mode() + || !candidates.iter().any(|c| { + matches!( + c.source, + CandidateSource::ParamEnv(ParamEnvSource::NonGlobal) + | CandidateSource::AliasBound + ) && has_no_inference_or_external_constraints(c.result) + }) + { + self.assemble_impl_candidates(goal, &mut candidates); + self.assemble_object_bound_candidates(goal, &mut candidates); + } } AssembleCandidatesFrom::EnvAndBounds => {} } @@ -938,36 +959,23 @@ where // Even when a trait bound has been proven using a where-bound, we // still need to consider alias-bounds for normalization, see // `tests/ui/next-solver/alias-bound-shadowed-by-env.rs`. - let candidates_from_env_and_bounds: Vec<_> = self + let mut candidates: Vec<_> = self .assemble_and_evaluate_candidates(goal, AssembleCandidatesFrom::EnvAndBounds); // We still need to prefer where-bounds over alias-bounds however. // See `tests/ui/winnowing/norm-where-bound-gt-alias-bound.rs`. - let mut considered_candidates: Vec<_> = if candidates_from_env_and_bounds - .iter() - .any(|c| matches!(c.source, CandidateSource::ParamEnv(_))) - { - candidates_from_env_and_bounds - .into_iter() - .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_))) - .map(|c| c.result) - .collect() - } else { - candidates_from_env_and_bounds.into_iter().map(|c| c.result).collect() - }; - - // If the trait goal has been proven by using the environment, we want to treat - // aliases as rigid if there are no applicable projection bounds in the environment. - if considered_candidates.is_empty() { - if let Ok(response) = inject_normalize_to_rigid_candidate(self) { - considered_candidates.push(response); - } + if candidates.iter().any(|c| matches!(c.source, CandidateSource::ParamEnv(_))) { + candidates.retain(|c| matches!(c.source, CandidateSource::ParamEnv(_))); + } else if candidates.is_empty() { + // If the trait goal has been proven by using the environment, we want to treat + // aliases as rigid if there are no applicable projection bounds in the environment. + return inject_normalize_to_rigid_candidate(self); } - if let Some(response) = self.try_merge_responses(&considered_candidates) { + if let Some(response) = self.try_merge_candidates(&candidates) { Ok(response) } else { - self.flounder(&considered_candidates) + self.flounder(&candidates) } } TraitGoalProvenVia::Misc => { @@ -977,11 +985,9 @@ where // Prefer "orphaned" param-env normalization predicates, which are used // (for example, and ideally only) when proving item bounds for an impl. let candidates_from_env: Vec<_> = candidates - .iter() - .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_))) - .map(|c| c.result) + .extract_if(.., |c| matches!(c.source, CandidateSource::ParamEnv(_))) .collect(); - if let Some(response) = self.try_merge_responses(&candidates_from_env) { + if let Some(response) = self.try_merge_candidates(&candidates_from_env) { return Ok(response); } @@ -991,12 +997,10 @@ where // means we can just ignore inference constraints and don't have to special-case // constraining the normalized-to `term`. self.filter_specialized_impls(AllowInferenceConstraints::Yes, &mut candidates); - - let responses: Vec<_> = candidates.iter().map(|c| c.result).collect(); - if let Some(response) = self.try_merge_responses(&responses) { + if let Some(response) = self.try_merge_candidates(&candidates) { Ok(response) } else { - self.flounder(&responses) + self.flounder(&candidates) } } } 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 c0bebdf6fb6..faa86734d08 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 @@ -75,9 +75,16 @@ where Ok(ty::Binder::dummy(vec![args.as_coroutine_closure().tupled_upvars_ty()])) } - ty::Coroutine(_, args) => { + ty::Coroutine(def_id, args) => { let coroutine_args = args.as_coroutine(); - Ok(ty::Binder::dummy(vec![coroutine_args.tupled_upvars_ty(), coroutine_args.witness()])) + Ok(ty::Binder::dummy(vec![ + coroutine_args.tupled_upvars_ty(), + Ty::new_coroutine_witness( + ecx.cx(), + def_id, + ecx.cx().mk_args(coroutine_args.parent_args().as_slice()), + ), + ])) } ty::CoroutineWitness(def_id, args) => Ok(ecx @@ -245,7 +252,14 @@ where Movability::Movable => { if ecx.cx().features().coroutine_clone() { let coroutine = args.as_coroutine(); - Ok(ty::Binder::dummy(vec![coroutine.tupled_upvars_ty(), coroutine.witness()])) + Ok(ty::Binder::dummy(vec![ + coroutine.tupled_upvars_ty(), + Ty::new_coroutine_witness( + ecx.cx(), + def_id, + ecx.cx().mk_args(coroutine.parent_args().as_slice()), + ), + ])) } else { Err(NoSolution) } 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 61f3f9367f0..9a22bf58c03 100644 --- a/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs +++ b/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs @@ -29,8 +29,8 @@ where self.trait_ref } - fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self { - self.with_self_ty(cx, self_ty) + fn with_replaced_self_ty(self, cx: I, self_ty: I::Ty) -> Self { + self.with_replaced_self_ty(cx, self_ty) } fn trait_def_id(self, _: I) -> I::DefId { 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 5ed316aa6b1..74c5b49ea92 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 @@ -53,20 +53,19 @@ where { /// Canonicalizes the goal remembering the original values /// for each bound variable. + /// + /// This expects `goal` and `opaque_types` to be eager resolved. pub(super) fn canonicalize_goal( &self, + is_hir_typeck_root_goal: bool, goal: Goal<I, I::Predicate>, + opaque_types: Vec<(ty::OpaqueTypeKey<I>, I::Ty)>, ) -> (Vec<I::GenericArg>, CanonicalInput<I, I::Predicate>) { - // We only care about one entry per `OpaqueTypeKey` here, - // so we only canonicalize the lookup table and ignore - // duplicate entries. - let opaque_types = self.delegate.clone_opaque_types_lookup_table(); - let (goal, opaque_types) = eager_resolve_vars(self.delegate, (goal, opaque_types)); - let mut orig_values = Default::default(); let canonical = Canonicalizer::canonicalize_input( self.delegate, &mut orig_values, + is_hir_typeck_root_goal, QueryInput { goal, predefined_opaques_in_body: self 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 ce9b794d40d..8671cc7c3d3 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 @@ -20,6 +20,7 @@ use super::has_only_region_constraints; use crate::coherence; use crate::delegate::SolverDelegate; use crate::placeholder::BoundVarReplacer; +use crate::resolve::eager_resolve_vars; use crate::solve::inspect::{self, ProofTreeBuilder}; use crate::solve::search_graph::SearchGraph; use crate::solve::ty::may_use_unstable_feature; @@ -440,6 +441,7 @@ where return Ok(( NestedNormalizationGoals::empty(), GoalEvaluation { + goal, certainty: Certainty::Maybe(stalled_on.stalled_cause), has_changed: HasChanged::No, stalled_on: Some(stalled_on), @@ -447,7 +449,16 @@ where )); } - let (orig_values, canonical_goal) = self.canonicalize_goal(goal); + // We only care about one entry per `OpaqueTypeKey` here, + // so we only canonicalize the lookup table and ignore + // duplicate entries. + let opaque_types = self.delegate.clone_opaque_types_lookup_table(); + let (goal, opaque_types) = eager_resolve_vars(self.delegate, (goal, opaque_types)); + + let is_hir_typeck_root_goal = matches!(goal_evaluation_kind, GoalEvaluationKind::Root) + && self.delegate.in_hir_typeck(); + let (orig_values, canonical_goal) = + self.canonicalize_goal(is_hir_typeck_root_goal, goal, opaque_types); let mut goal_evaluation = self.inspect.new_goal_evaluation(goal, &orig_values, goal_evaluation_kind); let canonical_result = self.search_graph.evaluate_goal( @@ -525,7 +536,10 @@ where }, }; - Ok((normalization_nested_goals, GoalEvaluation { certainty, has_changed, stalled_on })) + Ok(( + normalization_nested_goals, + GoalEvaluation { goal, certainty, has_changed, stalled_on }, + )) } pub(super) fn compute_goal(&mut self, goal: Goal<I, I::Predicate>) -> QueryResult<I> { @@ -661,7 +675,7 @@ where let ( NestedNormalizationGoals(nested_goals), - GoalEvaluation { certainty, stalled_on, has_changed: _ }, + GoalEvaluation { goal, certainty, stalled_on, has_changed: _ }, ) = self.evaluate_goal_raw( GoalEvaluationKind::Nested, source, @@ -699,7 +713,15 @@ where // FIXME: Do we need to eagerly resolve here? Or should we check // if the cache key has any changed vars? let with_resolved_vars = self.resolve_vars_if_possible(goal); - if pred.alias != goal.predicate.as_normalizes_to().unwrap().skip_binder().alias { + if pred.alias + != with_resolved_vars + .predicate + .as_normalizes_to() + .unwrap() + .no_bound_vars() + .unwrap() + .alias + { unchanged_certainty = None; } @@ -711,7 +733,7 @@ where } } } else { - let GoalEvaluation { certainty, has_changed, stalled_on } = + let GoalEvaluation { goal, certainty, has_changed, stalled_on } = self.evaluate_goal(GoalEvaluationKind::Nested, source, goal, stalled_on)?; if has_changed == HasChanged::Yes { unchanged_certainty = None; diff --git a/compiler/rustc_next_trait_solver/src/solve/mod.rs b/compiler/rustc_next_trait_solver/src/solve/mod.rs index 5ea3f0d1061..2feebe270a6 100644 --- a/compiler/rustc_next_trait_solver/src/solve/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/mod.rs @@ -29,6 +29,7 @@ use tracing::instrument; pub use self::eval_ctxt::{EvalCtxt, GenerateProofTree, SolverDelegateEvalExt}; use crate::delegate::SolverDelegate; +use crate::solve::assembly::Candidate; /// How many fixpoint iterations we should attempt inside of the solver before bailing /// with overflow. @@ -244,52 +245,51 @@ where /// /// In this case we tend to flounder and return ambiguity by calling `[EvalCtxt::flounder]`. #[instrument(level = "trace", skip(self), ret)] - fn try_merge_responses( + fn try_merge_candidates( &mut self, - responses: &[CanonicalResponse<I>], + candidates: &[Candidate<I>], ) -> Option<CanonicalResponse<I>> { - if responses.is_empty() { + if candidates.is_empty() { return None; } - // FIXME(-Znext-solver): Add support to merge region constraints in - // responses to deal with trait-system-refactor-initiative#27. - let one = responses[0]; - if responses[1..].iter().all(|&resp| resp == one) { + let one: CanonicalResponse<I> = candidates[0].result; + if candidates[1..].iter().all(|candidate| candidate.result == one) { return Some(one); } - responses + candidates .iter() - .find(|response| { - response.value.certainty == Certainty::Yes - && has_no_inference_or_external_constraints(**response) + .find(|candidate| { + candidate.result.value.certainty == Certainty::Yes + && has_no_inference_or_external_constraints(candidate.result) }) - .copied() + .map(|candidate| candidate.result) } - fn bail_with_ambiguity(&mut self, responses: &[CanonicalResponse<I>]) -> CanonicalResponse<I> { - debug_assert!(responses.len() > 1); - let maybe_cause = responses.iter().fold(MaybeCause::Ambiguity, |maybe_cause, response| { - // Pull down the certainty of `Certainty::Yes` to ambiguity when combining - // these responses, b/c we're combining more than one response and this we - // don't know which one applies. - let candidate = match response.value.certainty { - Certainty::Yes => MaybeCause::Ambiguity, - Certainty::Maybe(candidate) => candidate, - }; - maybe_cause.or(candidate) - }); + fn bail_with_ambiguity(&mut self, candidates: &[Candidate<I>]) -> CanonicalResponse<I> { + debug_assert!(candidates.len() > 1); + let maybe_cause = + candidates.iter().fold(MaybeCause::Ambiguity, |maybe_cause, candidates| { + // Pull down the certainty of `Certainty::Yes` to ambiguity when combining + // these responses, b/c we're combining more than one response and this we + // don't know which one applies. + let candidate = match candidates.result.value.certainty { + Certainty::Yes => MaybeCause::Ambiguity, + Certainty::Maybe(candidate) => candidate, + }; + maybe_cause.or(candidate) + }); self.make_ambiguous_response_no_constraints(maybe_cause) } /// If we fail to merge responses we flounder and return overflow or ambiguity. #[instrument(level = "trace", skip(self), ret)] - fn flounder(&mut self, responses: &[CanonicalResponse<I>]) -> QueryResult<I> { - if responses.is_empty() { + fn flounder(&mut self, candidates: &[Candidate<I>]) -> QueryResult<I> { + if candidates.is_empty() { return Err(NoSolution); } else { - Ok(self.bail_with_ambiguity(responses)) + Ok(self.bail_with_ambiguity(candidates)) } } @@ -388,6 +388,23 @@ fn response_no_constraints_raw<I: Interner>( /// The result of evaluating a goal. pub struct GoalEvaluation<I: Interner> { + /// The goal we've evaluated. This is the input goal, but potentially with its + /// inference variables resolved. This never applies any inference constraints + /// from evaluating the goal. + /// + /// We rely on this to check whether root goals in HIR typeck had an unresolved + /// type inference variable in the input. We must not resolve this after evaluating + /// the goal as even if the inference variable has been resolved by evaluating the + /// goal itself, this goal may still end up failing due to region uniquification + /// later on. + /// + /// This is used as a minor optimization to avoid re-resolving inference variables + /// when reevaluating ambiguous goals. E.g. if we've got a goal `?x: Trait` with `?x` + /// already being constrained to `Vec<?y>`, then the first evaluation resolves it to + /// `Vec<?y>: Trait`. If this goal is still ambiguous and we later resolve `?y` to `u32`, + /// then reevaluating this goal now only needs to resolve `?y` while it would otherwise + /// have to resolve both `?x` and `?y`, + pub goal: Goal<I, I::Predicate>, pub certainty: Certainty, pub has_changed: HasChanged, /// If the [`Certainty`] was `Maybe`, then keep track of whether the goal has changed 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 1e0a90eb2ee..93434dce79f 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 @@ -99,8 +99,8 @@ where self.alias.trait_ref(cx) } - fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self { - self.with_self_ty(cx, self_ty) + fn with_replaced_self_ty(self, cx: I, self_ty: I::Ty) -> Self { + self.with_replaced_self_ty(cx, self_ty) } fn trait_def_id(self, cx: I) -> I::DefId { 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 650b85d99d2..60bae738e61 100644 --- a/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs +++ b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs @@ -33,8 +33,8 @@ where self.trait_ref } - fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self { - self.with_self_ty(cx, self_ty) + fn with_replaced_self_ty(self, cx: I, self_ty: I::Ty) -> Self { + self.with_replaced_self_ty(cx, self_ty) } fn trait_def_id(self, _: I) -> I::DefId { @@ -229,7 +229,7 @@ where } // We need to make sure to stall any coroutines we are inferring to avoid query cycles. - if let Some(cand) = ecx.try_stall_coroutine_witness(goal.predicate.self_ty()) { + if let Some(cand) = ecx.try_stall_coroutine(goal.predicate.self_ty()) { return cand; } @@ -294,7 +294,7 @@ where } // We need to make sure to stall any coroutines we are inferring to avoid query cycles. - if let Some(cand) = ecx.try_stall_coroutine_witness(goal.predicate.self_ty()) { + if let Some(cand) = ecx.try_stall_coroutine(goal.predicate.self_ty()) { return cand; } @@ -1263,7 +1263,9 @@ where let goals = ecx.enter_forall(constituent_tys(ecx, goal.predicate.self_ty())?, |ecx, tys| { tys.into_iter() - .map(|ty| goal.with(ecx.cx(), goal.predicate.with_self_ty(ecx.cx(), ty))) + .map(|ty| { + goal.with(ecx.cx(), goal.predicate.with_replaced_self_ty(ecx.cx(), ty)) + }) .collect::<Vec<_>>() }); ecx.add_goals(GoalSource::ImplWhereBound, goals); @@ -1344,11 +1346,10 @@ where mut candidates: Vec<Candidate<I>>, ) -> Result<(CanonicalResponse<I>, Option<TraitGoalProvenVia>), NoSolution> { if let TypingMode::Coherence = self.typing_mode() { - let all_candidates: Vec<_> = candidates.into_iter().map(|c| c.result).collect(); - return if let Some(response) = self.try_merge_responses(&all_candidates) { + return if let Some(response) = self.try_merge_candidates(&candidates) { Ok((response, Some(TraitGoalProvenVia::Misc))) } else { - self.flounder(&all_candidates).map(|r| (r, None)) + self.flounder(&candidates).map(|r| (r, None)) }; } @@ -1373,11 +1374,9 @@ where .any(|c| matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::NonGlobal))); if has_non_global_where_bounds { let where_bounds: Vec<_> = candidates - .iter() - .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_))) - .map(|c| c.result) + .extract_if(.., |c| matches!(c.source, CandidateSource::ParamEnv(_))) .collect(); - return if let Some(response) = self.try_merge_responses(&where_bounds) { + return if let Some(response) = self.try_merge_candidates(&where_bounds) { Ok((response, Some(TraitGoalProvenVia::ParamEnv))) } else { Ok((self.bail_with_ambiguity(&where_bounds), None)) @@ -1386,11 +1385,9 @@ where if candidates.iter().any(|c| matches!(c.source, CandidateSource::AliasBound)) { let alias_bounds: Vec<_> = candidates - .iter() - .filter(|c| matches!(c.source, CandidateSource::AliasBound)) - .map(|c| c.result) + .extract_if(.., |c| matches!(c.source, CandidateSource::AliasBound)) .collect(); - return if let Some(response) = self.try_merge_responses(&alias_bounds) { + return if let Some(response) = self.try_merge_candidates(&alias_bounds) { Ok((response, Some(TraitGoalProvenVia::AliasBound))) } else { Ok((self.bail_with_ambiguity(&alias_bounds), None)) @@ -1415,11 +1412,10 @@ where TraitGoalProvenVia::Misc }; - let all_candidates: Vec<_> = candidates.into_iter().map(|c| c.result).collect(); - if let Some(response) = self.try_merge_responses(&all_candidates) { + if let Some(response) = self.try_merge_candidates(&candidates) { Ok((response, Some(proven_via))) } else { - self.flounder(&all_candidates).map(|r| (r, None)) + self.flounder(&candidates).map(|r| (r, None)) } } @@ -1432,11 +1428,8 @@ where self.merge_trait_candidates(candidates) } - fn try_stall_coroutine_witness( - &mut self, - self_ty: I::Ty, - ) -> Option<Result<Candidate<I>, NoSolution>> { - if let ty::CoroutineWitness(def_id, _) = self_ty.kind() { + fn try_stall_coroutine(&mut self, self_ty: I::Ty) -> Option<Result<Candidate<I>, NoSolution>> { + if let ty::Coroutine(def_id, _) = self_ty.kind() { match self.typing_mode() { TypingMode::Analysis { defining_opaque_types_and_generators: stalled_generators, |