diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src')
27 files changed, 861 insertions, 866 deletions
diff --git a/compiler/rustc_trait_selection/src/infer.rs b/compiler/rustc_trait_selection/src/infer.rs index 9b47c7299bb..911cc0b88c4 100644 --- a/compiler/rustc_trait_selection/src/infer.rs +++ b/compiler/rustc_trait_selection/src/infer.rs @@ -8,26 +8,16 @@ use rustc_middle::infer::canonical::{Canonical, CanonicalQueryResponse, QueryRes use rustc_middle::traits::query::Fallible; use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable, TypeVisitableExt}; use rustc_middle::ty::{GenericArg, ToPredicate}; -use rustc_span::{Span, DUMMY_SP}; +use rustc_span::DUMMY_SP; use std::fmt::Debug; pub use rustc_infer::infer::*; pub trait InferCtxtExt<'tcx> { - fn type_is_copy_modulo_regions( - &self, - param_env: ty::ParamEnv<'tcx>, - ty: Ty<'tcx>, - span: Span, - ) -> bool; + fn type_is_copy_modulo_regions(&self, param_env: ty::ParamEnv<'tcx>, ty: Ty<'tcx>) -> bool; - fn type_is_sized_modulo_regions( - &self, - param_env: ty::ParamEnv<'tcx>, - ty: Ty<'tcx>, - span: Span, - ) -> bool; + fn type_is_sized_modulo_regions(&self, param_env: ty::ParamEnv<'tcx>, ty: Ty<'tcx>) -> bool; /// Check whether a `ty` implements given trait(trait_def_id). /// The inputs are: @@ -46,13 +36,9 @@ pub trait InferCtxtExt<'tcx> { param_env: ty::ParamEnv<'tcx>, ) -> traits::EvaluationResult; } + impl<'tcx> InferCtxtExt<'tcx> for InferCtxt<'tcx> { - fn type_is_copy_modulo_regions( - &self, - param_env: ty::ParamEnv<'tcx>, - ty: Ty<'tcx>, - span: Span, - ) -> bool { + fn type_is_copy_modulo_regions(&self, param_env: ty::ParamEnv<'tcx>, ty: Ty<'tcx>) -> bool { let ty = self.resolve_vars_if_possible(ty); if !(param_env, ty).needs_infer() { @@ -65,17 +51,12 @@ impl<'tcx> InferCtxtExt<'tcx> for InferCtxt<'tcx> { // rightly refuses to work with inference variables, but // moves_by_default has a cache, which we want to use in other // cases. - traits::type_known_to_meet_bound_modulo_regions(self, param_env, ty, copy_def_id, span) + traits::type_known_to_meet_bound_modulo_regions(self, param_env, ty, copy_def_id) } - fn type_is_sized_modulo_regions( - &self, - param_env: ty::ParamEnv<'tcx>, - ty: Ty<'tcx>, - span: Span, - ) -> bool { + fn type_is_sized_modulo_regions(&self, param_env: ty::ParamEnv<'tcx>, ty: Ty<'tcx>) -> bool { let lang_item = self.tcx.require_lang_item(LangItem::Sized, None); - traits::type_known_to_meet_bound_modulo_regions(self, param_env, ty, lang_item, span) + traits::type_known_to_meet_bound_modulo_regions(self, param_env, ty, lang_item) } #[instrument(level = "debug", skip(self, params), ret)] diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs index 891ea0cdebe..76cde1a6692 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly.rs @@ -224,7 +224,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if goal.predicate.self_ty().is_ty_var() { return vec![Candidate { source: CandidateSource::BuiltinImpl, - result: self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(), + result: self + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + .unwrap(), }]; } @@ -261,8 +263,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else { return }; - self.probe(|this| { - let normalized_ty = this.next_ty_infer(); + + self.probe(|ecx| { + let normalized_ty = ecx.next_ty_infer(); let normalizes_to_goal = goal.with( tcx, ty::Binder::dummy(ty::ProjectionPredicate { @@ -270,28 +273,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { term: normalized_ty.into(), }), ); - let normalization_certainty = match this.evaluate_goal(normalizes_to_goal) { - Ok((_, certainty)) => certainty, - Err(NoSolution) => return, - }; - let normalized_ty = this.resolve_vars_if_possible(normalized_ty); - - // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate. - // This doesn't work as long as we use `CandidateSource` in winnowing. - let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty)); - let normalized_candidates = this.assemble_and_evaluate_candidates(goal); - for mut normalized_candidate in normalized_candidates { - normalized_candidate.result = - normalized_candidate.result.unchecked_map(|mut response| { - // FIXME: This currently hides overflow in the normalization step of the self type - // which is probably wrong. Maybe `unify_and` should actually keep overflow as - // we treat it as non-fatal anyways. - response.certainty = response.certainty.unify_and(normalization_certainty); - response - }); - candidates.push(normalized_candidate); + ecx.add_goal(normalizes_to_goal); + if let Ok(_) = ecx.try_evaluate_added_goals() { + let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty); + + // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate. + // This doesn't work as long as we use `CandidateSource` in winnowing. + let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty)); + candidates.extend(ecx.assemble_and_evaluate_candidates(goal)); } - }) + }); } fn assemble_impl_candidates<G: GoalKind<'tcx>>( @@ -516,7 +507,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } else { Certainty::AMBIGUOUS }; - return self.make_canonical_response(certainty); + return self.evaluate_added_goals_and_make_canonical_response(certainty); } } @@ -538,14 +529,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } - fn discard_reservation_impl(&self, mut candidate: Candidate<'tcx>) -> Candidate<'tcx> { + fn discard_reservation_impl(&mut self, mut candidate: Candidate<'tcx>) -> Candidate<'tcx> { if let CandidateSource::Impl(def_id) = candidate.source { if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) { debug!("Selected reservation impl"); // We assemble all candidates inside of a probe so by // making a new canonical response here our result will // have no constraints. - candidate.result = self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(); + candidate.result = self + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + .unwrap(); } } diff --git a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs b/compiler/rustc_trait_selection/src/solve/canonical/mod.rs index 8c3be8da16b..9d45e78ebab 100644 --- a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/canonical/mod.rs @@ -48,7 +48,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { /// - `external_constraints`: additional constraints which aren't expressable /// using simple unification of inference variables. #[instrument(level = "debug", skip(self))] - pub(super) fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> { + pub(super) fn evaluate_added_goals_and_make_canonical_response( + &mut self, + certainty: Certainty, + ) -> QueryResult<'tcx> { + let goals_certainty = self.try_evaluate_added_goals()?; + let certainty = certainty.unify_and(goals_certainty); + let external_constraints = self.compute_external_query_constraints()?; let response = Response { var_values: self.var_values, external_constraints, certainty }; @@ -209,7 +215,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // FIXME: To deal with #105787 I also expect us to emit nested obligations here at // some point. We can figure out how to deal with this once we actually have // an ICE. - let nested_goals = self.eq(param_env, orig, response)?; + let nested_goals = self.eq_and_get_goals(param_env, orig, response)?; assert!(nested_goals.is_empty(), "{nested_goals:?}"); } diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs index ca438a103cf..95412922357 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs @@ -2,8 +2,11 @@ use rustc_hir::def_id::DefId; use rustc_infer::infer::at::ToTrace; use rustc_infer::infer::canonical::CanonicalVarValues; use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; -use rustc_infer::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime}; +use rustc_infer::infer::{ + DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, TyCtxtInferExt, +}; use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::solve::{CanonicalGoal, Certainty, MaybeCause, QueryResult}; use rustc_infer::traits::ObligationCause; use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; use rustc_middle::ty::{ @@ -13,8 +16,8 @@ use rustc_middle::ty::{ use rustc_span::DUMMY_SP; use std::ops::ControlFlow; -use super::search_graph::SearchGraph; -use super::Goal; +use super::search_graph::{self, OverflowHandler}; +use super::{search_graph::SearchGraph, Goal}; pub struct EvalCtxt<'a, 'tcx> { // FIXME: should be private. @@ -33,14 +36,305 @@ pub struct EvalCtxt<'a, 'tcx> { pub(super) search_graph: &'a mut SearchGraph<'tcx>, - /// This field is used by a debug assertion in [`EvalCtxt::evaluate_goal`], - /// see the comment in that method for more details. - pub in_projection_eq_hack: bool, + pub(super) nested_goals: NestedGoals<'tcx>, +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub(super) enum IsNormalizesToHack { + Yes, + No, +} + +#[derive(Debug, Clone)] +pub(super) struct NestedGoals<'tcx> { + pub(super) normalizes_to_hack_goal: Option<Goal<'tcx, ty::ProjectionPredicate<'tcx>>>, + pub(super) goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, +} + +impl NestedGoals<'_> { + pub(super) fn new() -> Self { + Self { normalizes_to_hack_goal: None, goals: Vec::new() } + } + + pub(super) fn is_empty(&self) -> bool { + self.normalizes_to_hack_goal.is_none() && self.goals.is_empty() + } +} + +pub trait InferCtxtEvalExt<'tcx> { + /// Evaluates a goal from **outside** of the trait solver. + /// + /// Using this while inside of the solver is wrong as it uses a new + /// search graph which would break cycle detection. + fn evaluate_root_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty), NoSolution>; +} + +impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { + #[instrument(level = "debug", skip(self))] + fn evaluate_root_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty), NoSolution> { + let mut search_graph = search_graph::SearchGraph::new(self.tcx); + + let mut ecx = EvalCtxt { + search_graph: &mut search_graph, + infcx: self, + // Only relevant when canonicalizing the response. + max_input_universe: ty::UniverseIndex::ROOT, + var_values: CanonicalVarValues::dummy(), + nested_goals: NestedGoals::new(), + }; + let result = ecx.evaluate_goal(IsNormalizesToHack::No, goal); + + assert!( + ecx.nested_goals.is_empty(), + "root `EvalCtxt` should not have any goals added to it" + ); + + assert!(search_graph.is_empty()); + result + } +} + +impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { + /// The entry point of the solver. + /// + /// This function deals with (coinductive) cycles, overflow, and caching + /// and then calls [`EvalCtxt::compute_goal`] which contains the actual + /// logic of the solver. + /// + /// Instead of calling this function directly, use either [EvalCtxt::evaluate_goal] + /// if you're inside of the solver or [InferCtxtEvalExt::evaluate_root_goal] if you're + /// outside of it. + #[instrument(level = "debug", skip(tcx, search_graph), ret)] + fn evaluate_canonical_goal( + tcx: TyCtxt<'tcx>, + search_graph: &'a mut search_graph::SearchGraph<'tcx>, + canonical_goal: CanonicalGoal<'tcx>, + ) -> QueryResult<'tcx> { + // Deal with overflow, caching, and coinduction. + // + // The actual solver logic happens in `ecx.compute_goal`. + search_graph.with_new_goal(tcx, canonical_goal, |search_graph| { + let (ref infcx, goal, var_values) = + tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &canonical_goal); + let mut ecx = EvalCtxt { + infcx, + var_values, + max_input_universe: canonical_goal.max_universe, + search_graph, + nested_goals: NestedGoals::new(), + }; + ecx.compute_goal(goal) + }) + } + + /// Recursively evaluates `goal`, returning whether any inference vars have + /// been constrained and the certainty of the result. + fn evaluate_goal( + &mut self, + is_normalizes_to_hack: IsNormalizesToHack, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty), NoSolution> { + let (orig_values, canonical_goal) = self.canonicalize_goal(goal); + let canonical_response = + EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; + + let has_changed = !canonical_response.value.var_values.is_identity(); + let certainty = self.instantiate_and_apply_query_response( + goal.param_env, + orig_values, + canonical_response, + )?; + + // Check that rerunning this query with its inference constraints applied + // doesn't result in new inference constraints and has the same result. + // + // 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 + && is_normalizes_to_hack == IsNormalizesToHack::No + && !self.search_graph.in_cycle() + { + debug!("rerunning goal to check result is stable"); + let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); + let canonical_response = + EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; + if !canonical_response.value.var_values.is_identity() { + bug!("unstable result: {goal:?} {canonical_goal:?} {canonical_response:?}"); + } + assert_eq!(certainty, canonical_response.value.certainty); + } + + Ok((has_changed, certainty)) + } + + fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { + let Goal { param_env, predicate } = goal; + let kind = predicate.kind(); + if let Some(kind) = kind.no_bound_vars() { + match kind { + ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => { + self.compute_trait_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => { + self.compute_projection_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => { + self.compute_type_outlives_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => { + self.compute_region_outlives_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => { + self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) }) + } + ty::PredicateKind::Subtype(predicate) => { + self.compute_subtype_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Coerce(predicate) => { + self.compute_coerce_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::ClosureKind(def_id, substs, kind) => self + .compute_closure_kind_goal(Goal { + param_env, + predicate: (def_id, substs, kind), + }), + ty::PredicateKind::ObjectSafe(trait_def_id) => { + self.compute_object_safe_goal(trait_def_id) + } + ty::PredicateKind::WellFormed(arg) => { + self.compute_well_formed_goal(Goal { param_env, predicate: arg }) + } + ty::PredicateKind::Ambiguous => { + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + } + // FIXME: implement these predicates :) + ty::PredicateKind::ConstEvaluatable(_) | ty::PredicateKind::ConstEquate(_, _) => { + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + ty::PredicateKind::TypeWellFormedFromEnv(..) => { + bug!("TypeWellFormedFromEnv is only used for Chalk") + } + ty::PredicateKind::AliasEq(lhs, rhs) => { + self.compute_alias_eq_goal(Goal { param_env, predicate: (lhs, rhs) }) + } + } + } 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.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + } + + // Recursively evaluates all the goals added to this `EvalCtxt` to completion, returning + // the certainty of all the goals. + #[instrument(level = "debug", skip(self))] + pub(super) fn try_evaluate_added_goals(&mut self) -> Result<Certainty, NoSolution> { + let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new()); + let mut new_goals = NestedGoals::new(); + + let response = self.repeat_while_none( + |_| Ok(Certainty::Maybe(MaybeCause::Overflow)), + |this| { + let mut has_changed = Err(Certainty::Yes); + + if let Some(goal) = goals.normalizes_to_hack_goal.take() { + let (_, certainty) = match this.evaluate_goal( + IsNormalizesToHack::Yes, + goal.with(this.tcx(), ty::Binder::dummy(goal.predicate)), + ) { + Ok(r) => r, + Err(NoSolution) => return Some(Err(NoSolution)), + }; + + if goal.predicate.projection_ty + != this.resolve_vars_if_possible(goal.predicate.projection_ty) + { + has_changed = Ok(()) + } + + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + let goal = this.resolve_vars_if_possible(goal); + + // The rhs of this `normalizes-to` must always be an unconstrained infer var as it is + // the hack used by `normalizes-to` to ensure that every `normalizes-to` behaves the same + // regardless of the rhs. + // + // However it is important not to unconditionally replace the rhs with a new infer var + // as otherwise we may replace the original unconstrained infer var with a new infer var + // and never propagate any constraints on the new var back to the original var. + let term = this + .term_is_fully_unconstrained(goal) + .then_some(goal.predicate.term) + .unwrap_or_else(|| { + this.next_term_infer_of_kind(goal.predicate.term) + }); + let projection_pred = ty::ProjectionPredicate { + term, + projection_ty: goal.predicate.projection_ty, + }; + new_goals.normalizes_to_hack_goal = + Some(goal.with(this.tcx(), projection_pred)); + + has_changed = has_changed.map_err(|c| c.unify_and(certainty)); + } + } + } + + for nested_goal in goals.goals.drain(..) { + let (changed, certainty) = + match this.evaluate_goal(IsNormalizesToHack::No, nested_goal) { + Ok(result) => result, + Err(NoSolution) => return Some(Err(NoSolution)), + }; + + if changed { + has_changed = Ok(()); + } + + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + new_goals.goals.push(nested_goal); + has_changed = has_changed.map_err(|c| c.unify_and(certainty)); + } + } + } + + core::mem::swap(&mut new_goals, &mut goals); + match has_changed { + Ok(()) => None, + Err(certainty) => Some(Ok(certainty)), + } + }, + ); + + self.nested_goals = goals; + response + } } impl<'tcx> EvalCtxt<'_, 'tcx> { pub(super) fn probe<T>(&mut self, f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> T) -> T { - self.infcx.probe(|_| f(self)) + let mut ecx = EvalCtxt { + infcx: self.infcx, + var_values: self.var_values, + max_input_universe: self.max_input_universe, + search_graph: self.search_graph, + nested_goals: self.nested_goals.clone(), + }; + self.infcx.probe(|_| f(&mut ecx)) } pub(super) fn tcx(&self) -> TyCtxt<'tcx> { @@ -61,6 +355,15 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) } + /// Returns a ty infer or a const infer depending on whether `kind` is a `Ty` or `Const`. + /// If `kind` is an integer inference variable this will still return a ty infer var. + pub(super) fn next_term_infer_of_kind(&self, kind: ty::Term<'tcx>) -> ty::Term<'tcx> { + match kind.unpack() { + ty::TermKind::Ty(_) => self.next_ty_infer().into(), + ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(), + } + } + /// Is the projection predicate is of the form `exists<T> <Ty as Trait>::Assoc = T`. /// /// This is the case if the `term` is an inference variable in the innermost universe @@ -137,6 +440,30 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self, param_env), ret)] pub(super) fn eq<T: ToTrace<'tcx>>( + &mut self, + param_env: ty::ParamEnv<'tcx>, + lhs: T, + rhs: T, + ) -> Result<(), NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .eq(DefineOpaqueTypes::No, lhs, rhs) + .map(|InferOk { value: (), obligations }| { + self.add_goals(obligations.into_iter().map(|o| o.into())); + }) + .map_err(|e| { + debug!(?e, "failed to equate"); + NoSolution + }) + } + + /// Equates two values returning the nested goals without adding them + /// to the nested goals of the `EvalCtxt`. + /// + /// If possible, try using `eq` instead which automatically handles nested + /// goals correctly. + #[instrument(level = "debug", skip(self, param_env), ret)] + pub(super) fn eq_and_get_goals<T: ToTrace<'tcx>>( &self, param_env: ty::ParamEnv<'tcx>, lhs: T, @@ -144,7 +471,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> { self.infcx .at(&ObligationCause::dummy(), param_env) - .eq(lhs, rhs) + .eq(DefineOpaqueTypes::No, lhs, rhs) .map(|InferOk { value: (), obligations }| { obligations.into_iter().map(|o| o.into()).collect() }) diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 55d361b1204..606c2eaa510 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -15,23 +15,19 @@ // FIXME: uses of `infcx.at` need to enable deferred projection equality once that's implemented. -use std::mem; - use rustc_hir::def_id::DefId; use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues}; -use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt}; +use rustc_infer::infer::{DefineOpaqueTypes, InferOk}; use rustc_infer::traits::query::NoSolution; use rustc_middle::traits::solve::{ CanonicalGoal, CanonicalResponse, Certainty, ExternalConstraints, ExternalConstraintsData, - Goal, MaybeCause, QueryResult, Response, + Goal, QueryResult, Response, }; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_middle::ty::{ CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate, }; -use rustc_span::DUMMY_SP; -use crate::solve::search_graph::OverflowHandler; use crate::traits::ObligationCause; mod assembly; @@ -42,7 +38,7 @@ mod project_goals; mod search_graph; mod trait_goals; -pub use eval_ctxt::EvalCtxt; +pub use eval_ctxt::{EvalCtxt, InferCtxtEvalExt}; pub use fulfill::FulfillmentCtxt; trait CanonicalResponseExt { @@ -57,180 +53,18 @@ impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> { } } -pub trait InferCtxtEvalExt<'tcx> { - /// Evaluates a goal from **outside** of the trait solver. - /// - /// Using this while inside of the solver is wrong as it uses a new - /// search graph which would break cycle detection. - fn evaluate_root_goal( - &self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - ) -> Result<(bool, Certainty), NoSolution>; -} - -impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { - fn evaluate_root_goal( - &self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - ) -> Result<(bool, Certainty), NoSolution> { - let mut search_graph = search_graph::SearchGraph::new(self.tcx); - - let result = EvalCtxt { - search_graph: &mut search_graph, - infcx: self, - // Only relevant when canonicalizing the response. - max_input_universe: ty::UniverseIndex::ROOT, - var_values: CanonicalVarValues::dummy(), - in_projection_eq_hack: false, - } - .evaluate_goal(goal); - - assert!(search_graph.is_empty()); - result - } -} - impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { - /// The entry point of the solver. - /// - /// This function deals with (coinductive) cycles, overflow, and caching - /// and then calls [`EvalCtxt::compute_goal`] which contains the actual - /// logic of the solver. - /// - /// Instead of calling this function directly, use either [EvalCtxt::evaluate_goal] - /// if you're inside of the solver or [InferCtxtEvalExt::evaluate_root_goal] if you're - /// outside of it. - #[instrument(level = "debug", skip(tcx, search_graph), ret)] - fn evaluate_canonical_goal( - tcx: TyCtxt<'tcx>, - search_graph: &'a mut search_graph::SearchGraph<'tcx>, - canonical_goal: CanonicalGoal<'tcx>, - ) -> QueryResult<'tcx> { - // Deal with overflow, caching, and coinduction. - // - // The actual solver logic happens in `ecx.compute_goal`. - search_graph.with_new_goal(tcx, canonical_goal, |search_graph| { - let (ref infcx, goal, var_values) = - tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &canonical_goal); - let mut ecx = EvalCtxt { - infcx, - var_values, - max_input_universe: canonical_goal.max_universe, - search_graph, - in_projection_eq_hack: false, - }; - ecx.compute_goal(goal) - }) - } - - /// Recursively evaluates `goal`, returning whether any inference vars have - /// been constrained and the certainty of the result. - fn evaluate_goal( - &mut self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - ) -> Result<(bool, Certainty), NoSolution> { - let (orig_values, canonical_goal) = self.canonicalize_goal(goal); - let canonical_response = - EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; - - let has_changed = !canonical_response.value.var_values.is_identity(); - let certainty = self.instantiate_and_apply_query_response( - goal.param_env, - orig_values, - canonical_response, - )?; - - // Check that rerunning this query with its inference constraints applied - // doesn't result in new inference constraints and has the same result. - // - // 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 - && !self.in_projection_eq_hack - && !self.search_graph.in_cycle() - && false - { - let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); - let canonical_response = - EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; - if !canonical_response.value.var_values.is_identity() { - bug!("unstable result: {goal:?} {canonical_goal:?} {canonical_response:?}"); - } - assert_eq!(certainty, canonical_response.value.certainty); - } - - Ok((has_changed, certainty)) - } - - fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { - let Goal { param_env, predicate } = goal; - let kind = predicate.kind(); - if let Some(kind) = kind.no_bound_vars() { - match kind { - ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => { - self.compute_trait_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => { - self.compute_projection_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => { - self.compute_type_outlives_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => { - self.compute_region_outlives_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => { - self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) }) - } - ty::PredicateKind::Subtype(predicate) => { - self.compute_subtype_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Coerce(predicate) => { - self.compute_coerce_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::ClosureKind(def_id, substs, kind) => self - .compute_closure_kind_goal(Goal { - param_env, - predicate: (def_id, substs, kind), - }), - ty::PredicateKind::ObjectSafe(trait_def_id) => { - self.compute_object_safe_goal(trait_def_id) - } - ty::PredicateKind::WellFormed(arg) => { - self.compute_well_formed_goal(Goal { param_env, predicate: arg }) - } - ty::PredicateKind::Ambiguous => self.make_canonical_response(Certainty::AMBIGUOUS), - // FIXME: implement these predicates :) - ty::PredicateKind::ConstEvaluatable(_) | ty::PredicateKind::ConstEquate(_, _) => { - self.make_canonical_response(Certainty::Yes) - } - ty::PredicateKind::TypeWellFormedFromEnv(..) => { - bug!("TypeWellFormedFromEnv is only used for Chalk") - } - ty::PredicateKind::AliasEq(lhs, rhs) => { - self.compute_alias_eq_goal(Goal { param_env, predicate: (lhs, rhs) }) - } - } - } else { - let kind = self.infcx.instantiate_binder_with_placeholders(kind); - let goal = goal.with(self.tcx(), ty::Binder::dummy(kind)); - let (_, certainty) = self.evaluate_goal(goal)?; - self.make_canonical_response(certainty) - } - } - + #[instrument(level = "debug", skip(self))] fn compute_type_outlives_goal( &mut self, goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { let ty::OutlivesPredicate(ty, lt) = goal.predicate; self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy()); - self.make_canonical_response(Certainty::Yes) + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } + #[instrument(level = "debug", skip(self))] fn compute_region_outlives_goal( &mut self, goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>, @@ -239,9 +73,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { &ObligationCause::dummy(), ty::Binder::dummy(goal.predicate), ); - self.make_canonical_response(Certainty::Yes) + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } + #[instrument(level = "debug", skip(self))] fn compute_coerce_goal( &mut self, goal: Goal<'tcx, CoercePredicate<'tcx>>, @@ -256,6 +91,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { }) } + #[instrument(level = "debug", skip(self))] fn compute_subtype_goal( &mut self, goal: Goal<'tcx, SubtypePredicate<'tcx>>, @@ -263,18 +99,18 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { if goal.predicate.a.is_ty_var() && goal.predicate.b.is_ty_var() { // FIXME: Do we want to register a subtype relation between these vars? // That won't actually reflect in the query response, so it seems moot. - self.make_canonical_response(Certainty::AMBIGUOUS) + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) } else { let InferOk { value: (), obligations } = self .infcx .at(&ObligationCause::dummy(), goal.param_env) - .sub(goal.predicate.a, goal.predicate.b)?; - self.evaluate_all_and_make_canonical_response( - obligations.into_iter().map(|pred| pred.into()).collect(), - ) + .sub(DefineOpaqueTypes::No, goal.predicate.a, goal.predicate.b)?; + self.add_goals(obligations.into_iter().map(|pred| pred.into())); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } + #[instrument(level = "debug", skip(self))] fn compute_closure_kind_goal( &mut self, goal: Goal<'tcx, (DefId, ty::SubstsRef<'tcx>, ty::ClosureKind)>, @@ -283,23 +119,25 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let found_kind = substs.as_closure().kind_ty().to_opt_closure_kind(); let Some(found_kind) = found_kind else { - return self.make_canonical_response(Certainty::AMBIGUOUS); + return self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); }; if found_kind.extends(expected_kind) { - self.make_canonical_response(Certainty::Yes) + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } else { Err(NoSolution) } } + #[instrument(level = "debug", skip(self))] fn compute_object_safe_goal(&mut self, trait_def_id: DefId) -> QueryResult<'tcx> { if self.tcx().check_is_object_safe(trait_def_id) { - self.make_canonical_response(Certainty::Yes) + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } else { Err(NoSolution) } } + #[instrument(level = "debug", skip(self))] fn compute_well_formed_goal( &mut self, goal: Goal<'tcx, ty::GenericArg<'tcx>>, @@ -309,10 +147,11 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { goal.param_env, goal.predicate, ) { - Some(obligations) => self.evaluate_all_and_make_canonical_response( - obligations.into_iter().map(|o| o.into()).collect(), - ), - None => self.make_canonical_response(Certainty::AMBIGUOUS), + Some(obligations) => { + self.add_goals(obligations.into_iter().map(|o| o.into())); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + None => self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS), } } @@ -326,14 +165,14 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let evaluate_normalizes_to = |ecx: &mut EvalCtxt<'_, 'tcx>, alias, other| { debug!("evaluate_normalizes_to(alias={:?}, other={:?})", alias, other); let r = ecx.probe(|ecx| { - let (_, certainty) = ecx.evaluate_goal(goal.with( + ecx.add_goal(goal.with( tcx, ty::Binder::dummy(ty::ProjectionPredicate { projection_ty: alias, term: other, }), - ))?; - ecx.make_canonical_response(certainty) + )); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }); debug!("evaluate_normalizes_to(..) -> {:?}", r); r @@ -360,10 +199,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { // Evaluate all 3 potential candidates for the alias' being equal candidates.push(evaluate_normalizes_to(self, alias_lhs, goal.predicate.1)); candidates.push(evaluate_normalizes_to(self, alias_rhs, goal.predicate.0)); - candidates.push(self.probe(|this| { + candidates.push(self.probe(|ecx| { debug!("compute_alias_eq_goal: alias defids are equal, equating substs"); - let nested_goals = this.eq(goal.param_env, alias_lhs, alias_rhs)?; - this.evaluate_all_and_make_canonical_response(nested_goals) + ecx.eq(goal.param_env, alias_lhs, alias_rhs)?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) })); debug!(?candidates); @@ -379,62 +218,31 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { goal: Goal<'tcx, (ty::Const<'tcx>, Ty<'tcx>)>, ) -> QueryResult<'tcx> { let (ct, ty) = goal.predicate; - let nested_goals = self.eq(goal.param_env, ct.ty(), ty)?; - self.evaluate_all_and_make_canonical_response(nested_goals) + self.eq(goal.param_env, ct.ty(), ty)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } impl<'tcx> EvalCtxt<'_, 'tcx> { - // Recursively evaluates a list of goals to completion, returning the certainty - // of all of the goals. - fn evaluate_all( - &mut self, - mut goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, - ) -> Result<Certainty, NoSolution> { - let mut new_goals = Vec::new(); - self.repeat_while_none( - |_| Ok(Certainty::Maybe(MaybeCause::Overflow)), - |this| { - let mut has_changed = Err(Certainty::Yes); - for goal in goals.drain(..) { - let (changed, certainty) = match this.evaluate_goal(goal) { - Ok(result) => result, - Err(NoSolution) => return Some(Err(NoSolution)), - }; - - if changed { - has_changed = Ok(()); - } - - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - new_goals.push(goal); - has_changed = has_changed.map_err(|c| c.unify_and(certainty)); - } - } - } - - match has_changed { - Ok(()) => { - mem::swap(&mut new_goals, &mut goals); - None - } - Err(certainty) => Some(Ok(certainty)), - } - }, - ) + #[instrument(level = "debug", skip(self))] + fn set_normalizes_to_hack_goal(&mut self, goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>) { + assert!( + self.nested_goals.normalizes_to_hack_goal.is_none(), + "attempted to set the projection eq hack goal when one already exists" + ); + self.nested_goals.normalizes_to_hack_goal = Some(goal); } - // Recursively evaluates a list of goals to completion, making a query response. - // - // This is just a convenient way of calling [`EvalCtxt::evaluate_all`], - // then [`EvalCtxt::make_canonical_response`]. - fn evaluate_all_and_make_canonical_response( - &mut self, - goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, - ) -> QueryResult<'tcx> { - self.evaluate_all(goals).and_then(|certainty| self.make_canonical_response(certainty)) + #[instrument(level = "debug", skip(self))] + fn add_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) { + self.nested_goals.goals.push(goal); + } + + #[instrument(level = "debug", skip(self, goals))] + fn add_goals(&mut self, goals: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>) { + let current_len = self.nested_goals.goals.len(); + self.nested_goals.goals.extend(goals); + debug!("added_goals={:?}", &self.nested_goals.goals[current_len..]); } fn try_merge_responses( @@ -466,7 +274,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }); // FIXME(-Ztrait-solver=next): We should take the intersection of the constraints on all the // responses and use that for the constraints of this ambiguous response. - let response = self.make_canonical_response(certainty); + let response = self.evaluate_added_goals_and_make_canonical_response(certainty); if let Ok(response) = &response { assert!(response.has_no_inference_or_external_constraints()); } diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs index dbb8e722c8f..93d77c39f95 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -20,6 +20,7 @@ use rustc_span::{sym, DUMMY_SP}; use std::iter; impl<'tcx> EvalCtxt<'_, 'tcx> { + #[instrument(level = "debug", skip(self), ret)] pub(super) fn compute_projection_goal( &mut self, goal: Goal<'tcx, ProjectionPredicate<'tcx>>, @@ -36,53 +37,17 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.merge_candidates_and_discard_reservation_impls(candidates) } else { let predicate = goal.predicate; - let unconstrained_rhs = match predicate.term.unpack() { - ty::TermKind::Ty(_) => self.next_ty_infer().into(), - ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(), - }; - let unconstrained_predicate = ty::Clause::Projection(ProjectionPredicate { + let unconstrained_rhs = self.next_term_infer_of_kind(predicate.term); + let unconstrained_predicate = ProjectionPredicate { projection_ty: goal.predicate.projection_ty, term: unconstrained_rhs, - }); - let (_has_changed, normalize_certainty) = self.in_projection_eq_hack(|this| { - this.evaluate_goal(goal.with(this.tcx(), unconstrained_predicate)) - })?; - - let nested_eq_goals = self.eq(goal.param_env, unconstrained_rhs, predicate.term)?; - let eval_certainty = self.evaluate_all(nested_eq_goals)?; - self.make_canonical_response(normalize_certainty.unify_and(eval_certainty)) - } - } - - /// This sets a flag used by a debug assert in [`EvalCtxt::evaluate_goal`], - /// see the comment in that method for more details. - fn in_projection_eq_hack<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T { - self.in_projection_eq_hack = true; - let result = f(self); - self.in_projection_eq_hack = false; - result - } - - /// After normalizing the projection to `normalized_alias` with the given - /// `normalization_certainty`, constrain the inference variable `term` to it - /// and return a query response. - fn eq_term_and_make_canonical_response( - &mut self, - goal: Goal<'tcx, ProjectionPredicate<'tcx>>, - normalization_certainty: Certainty, - normalized_alias: impl Into<ty::Term<'tcx>>, - ) -> QueryResult<'tcx> { - // The term of our goal should be fully unconstrained, so this should never fail. - // - // It can however be ambiguous when the `normalized_alias` contains a projection. - let nested_goals = self - .eq(goal.param_env, goal.predicate.term, normalized_alias.into()) - .expect("failed to unify with unconstrained term"); - - let unify_certainty = - self.evaluate_all(nested_goals).expect("failed to unify with unconstrained term"); + }; - self.make_canonical_response(normalization_certainty.unify_and(unify_certainty)) + self.set_normalizes_to_hack_goal(goal.with(self.tcx(), unconstrained_predicate)); + self.try_evaluate_added_goals()?; + self.eq(goal.param_env, unconstrained_rhs, predicate.term)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } } } @@ -111,19 +76,14 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ecx.probe(|ecx| { let assumption_projection_pred = ecx.instantiate_binder_with_infer(poly_projection_pred); - let mut nested_goals = ecx.eq( + ecx.eq( goal.param_env, goal.predicate.projection_ty, assumption_projection_pred.projection_ty, )?; - nested_goals.extend(requirements); - let subst_certainty = ecx.evaluate_all(nested_goals)?; - - ecx.eq_term_and_make_canonical_response( - goal, - subst_certainty, - assumption_projection_pred.term, - ) + ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)?; + ecx.add_goals(requirements); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } else { Err(NoSolution) @@ -139,21 +99,22 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { && poly_projection_pred.projection_def_id() == goal.predicate.def_id() { ecx.probe(|ecx| { + let tcx = ecx.tcx(); + let assumption_projection_pred = ecx.instantiate_binder_with_infer(poly_projection_pred); - let mut nested_goals = ecx.eq( + ecx.eq( goal.param_env, goal.predicate.projection_ty, assumption_projection_pred.projection_ty, )?; - let tcx = ecx.tcx(); let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { bug!("expected object type in `consider_object_bound_candidate`"); }; - nested_goals.extend( + ecx.add_goals( structural_traits::predicates_for_object_candidate( - ecx, + &ecx, goal.param_env, goal.predicate.projection_ty.trait_ref(tcx), bounds, @@ -161,14 +122,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { .into_iter() .map(|pred| goal.with(tcx, pred)), ); - - let subst_certainty = ecx.evaluate_all(nested_goals)?; - - ecx.eq_term_and_make_canonical_response( - goal, - subst_certainty, - assumption_projection_pred.term, - ) + ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } else { Err(NoSolution) @@ -195,16 +150,15 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { let impl_substs = ecx.fresh_substs_for_item(impl_def_id); let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); - let mut nested_goals = ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; + ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; + let where_clause_bounds = tcx .predicates_of(impl_def_id) .instantiate(tcx, impl_substs) .predicates .into_iter() .map(|pred| goal.with(tcx, pred)); - - nested_goals.extend(where_clause_bounds); - let match_impl_certainty = ecx.evaluate_all(nested_goals)?; + ecx.add_goals(where_clause_bounds); // In case the associated item is hidden due to specialization, we have to // return ambiguity this would otherwise be incomplete, resulting in @@ -216,7 +170,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal.predicate.def_id(), impl_def_id )? else { - return ecx.make_canonical_response(match_impl_certainty.unify_and(Certainty::AMBIGUOUS)); + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes); }; if !assoc_def.item.defaultness(tcx).has_value() { @@ -263,7 +217,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ty.map_bound(|ty| ty.into()) }; - ecx.eq_term_and_make_canonical_response(goal, match_impl_certainty, term.subst(tcx, substs)) + ecx.eq(goal.param_env, goal.predicate.term, term.subst(tcx, substs))?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -308,14 +263,18 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal_kind: ty::ClosureKind, ) -> QueryResult<'tcx> { let tcx = ecx.tcx(); - let Some(tupled_inputs_and_output) = - structural_traits::extract_tupled_inputs_and_output_from_callable( - tcx, - goal.predicate.self_ty(), - goal_kind, - )? else { - return ecx.make_canonical_response(Certainty::AMBIGUOUS); - }; + let tupled_inputs_and_output = + match structural_traits::extract_tupled_inputs_and_output_from_callable( + tcx, + goal.predicate.self_ty(), + goal_kind, + )? { + Some(tupled_inputs_and_output) => tupled_inputs_and_output, + None => { + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + } + }; let output_is_sized_pred = tupled_inputs_and_output .map_bound(|(_, output)| tcx.at(DUMMY_SP).mk_trait_ref(LangItem::Sized, [output])); @@ -380,13 +339,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { [ty::GenericArg::from(goal.predicate.self_ty())], )); - let (_, is_sized_certainty) = - ecx.evaluate_goal(goal.with(tcx, sized_predicate))?; - return ecx.eq_term_and_make_canonical_response( - goal, - is_sized_certainty, - tcx.types.unit, - ); + ecx.add_goal(goal.with(tcx, sized_predicate)); + ecx.eq(goal.param_env, goal.predicate.term, tcx.types.unit.into())?; + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } ty::Adt(def, substs) if def.is_struct() => { @@ -394,12 +349,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { None => tcx.types.unit, Some(field_def) => { let self_ty = field_def.ty(tcx, substs); - let new_goal = goal.with( + ecx.add_goal(goal.with( tcx, ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)), - ); - let (_, certainty) = ecx.evaluate_goal(new_goal)?; - return ecx.make_canonical_response(certainty); + )); + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } } } @@ -408,12 +363,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ty::Tuple(elements) => match elements.last() { None => tcx.types.unit, Some(&self_ty) => { - let new_goal = goal.with( + ecx.add_goal(goal.with( tcx, ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)), - ); - let (_, certainty) = ecx.evaluate_goal(new_goal)?; - return ecx.make_canonical_response(certainty); + )); + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } }, @@ -426,7 +381,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ), }; - ecx.eq_term_and_make_canonical_response(goal, Certainty::Yes, metadata_ty) + ecx.eq(goal.param_env, goal.predicate.term, metadata_ty.into())?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -522,7 +478,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { let discriminant = goal.predicate.self_ty().discriminant_ty(ecx.tcx()); - ecx.probe(|ecx| ecx.eq_term_and_make_canonical_response(goal, Certainty::Yes, discriminant)) + ecx.probe(|ecx| { + ecx.eq(goal.param_env, goal.predicate.term, discriminant.into())?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) } } diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs index f1b840aac55..83d77a69c00 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -39,9 +39,7 @@ impl<'tcx> SearchGraph<'tcx> { } pub(super) fn is_empty(&self) -> bool { - self.stack.is_empty() - && self.provisional_cache.is_empty() - && !self.overflow_data.did_overflow() + self.stack.is_empty() && self.provisional_cache.is_empty() } /// Whether we're currently in a cycle. This should only be used diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs index 7878539817c..8ab55c79fc4 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -47,16 +47,15 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let impl_substs = ecx.fresh_substs_for_item(impl_def_id); let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); - let mut nested_goals = - ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?; + ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?; let where_clause_bounds = tcx .predicates_of(impl_def_id) .instantiate(tcx, impl_substs) .predicates .into_iter() .map(|pred| goal.with(tcx, pred)); - nested_goals.extend(where_clause_bounds); - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.add_goals(where_clause_bounds); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -73,13 +72,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx.probe(|ecx| { let assumption_trait_pred = ecx.instantiate_binder_with_infer(poly_trait_pred); - let mut nested_goals = ecx.eq( + ecx.eq( goal.param_env, goal.predicate.trait_ref, assumption_trait_pred.trait_ref, )?; - nested_goals.extend(requirements); - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.add_goals(requirements); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } else { Err(NoSolution) @@ -98,7 +97,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx.probe(|ecx| { let assumption_trait_pred = ecx.instantiate_binder_with_infer(poly_trait_pred); - let mut nested_goals = ecx.eq( + ecx.eq( goal.param_env, goal.predicate.trait_ref, assumption_trait_pred.trait_ref, @@ -108,9 +107,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { bug!("expected object type in `consider_object_bound_candidate`"); }; - nested_goals.extend( + ecx.add_goals( structural_traits::predicates_for_object_candidate( - ecx, + &ecx, goal.param_env, goal.predicate.trait_ref, bounds, @@ -118,8 +117,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { .into_iter() .map(|pred| goal.with(tcx, pred)), ); - - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } else { Err(NoSolution) @@ -166,9 +164,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let nested_obligations = tcx .predicates_of(goal.predicate.def_id()) .instantiate(tcx, goal.predicate.trait_ref.substs); - ecx.evaluate_all_and_make_canonical_response( - nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)).collect(), - ) + ecx.add_goals(nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p))); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -197,7 +194,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { if goal.predicate.self_ty().has_non_region_infer() { - return ecx.make_canonical_response(Certainty::AMBIGUOUS); + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); } let tcx = ecx.tcx(); @@ -209,7 +206,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { && layout.layout.align().abi == usize_layout.align().abi { // FIXME: We could make this faster by making a no-constraints response - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } else { Err(NoSolution) } @@ -221,14 +218,18 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { goal_kind: ty::ClosureKind, ) -> QueryResult<'tcx> { let tcx = ecx.tcx(); - let Some(tupled_inputs_and_output) = - structural_traits::extract_tupled_inputs_and_output_from_callable( + let tupled_inputs_and_output = + match structural_traits::extract_tupled_inputs_and_output_from_callable( tcx, goal.predicate.self_ty(), goal_kind, - )? else { - return ecx.make_canonical_response(Certainty::AMBIGUOUS); - }; + )? { + Some(a) => a, + None => { + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + } + }; let output_is_sized_pred = tupled_inputs_and_output .map_bound(|(_, output)| tcx.at(DUMMY_SP).mk_trait_ref(LangItem::Sized, [output])); @@ -247,7 +248,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { if let ty::Tuple(..) = goal.predicate.self_ty().kind() { - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } else { Err(NoSolution) } @@ -257,7 +258,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx: &mut EvalCtxt<'_, 'tcx>, _goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } fn consider_builtin_future_candidate( @@ -277,7 +278,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Async generator unconditionally implement `Future` // Technically, we need to check that the future output type is Sized, // but that's already proven by the generator being WF. - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } fn consider_builtin_generator_candidate( @@ -317,7 +318,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let a_ty = goal.predicate.self_ty(); let b_ty = goal.predicate.trait_ref.substs.type_at(1); if b_ty.is_ty_var() { - return ecx.make_canonical_response(Certainty::AMBIGUOUS); + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); } ecx.probe(|ecx| { match (a_ty.kind(), b_ty.kind()) { @@ -326,7 +327,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Dyn upcasting is handled separately, since due to upcasting, // when there are two supertraits that differ by substs, we // may return more than one query response. - return Err(NoSolution); + Err(NoSolution) } // `T` -> `dyn Trait` unsizing (_, &ty::Dynamic(data, region, ty::Dyn)) => { @@ -341,29 +342,26 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let Some(sized_def_id) = tcx.lang_items().sized_trait() else { return Err(NoSolution); }; - let nested_goals: Vec<_> = data - .iter() - // Check that the type implements all of the predicates of the def-id. - // (i.e. the principal, all of the associated types match, and any auto traits) - .map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty))) - .chain([ - // The type must be Sized to be unsized. - goal.with( - tcx, - ty::Binder::dummy(tcx.mk_trait_ref(sized_def_id, [a_ty])), - ), - // The type must outlive the lifetime of the `dyn` we're unsizing into. - goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region))), - ]) - .collect(); - - ecx.evaluate_all_and_make_canonical_response(nested_goals) + // Check that the type implements all of the predicates of the def-id. + // (i.e. the principal, all of the associated types match, and any auto traits) + ecx.add_goals( + data.iter().map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty))), + ); + // The type must be Sized to be unsized. + ecx.add_goal( + goal.with(tcx, ty::Binder::dummy(tcx.mk_trait_ref(sized_def_id, [a_ty]))), + ); + // The type must outlive the lifetime of the `dyn` we're unsizing into. + ecx.add_goal( + goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region))), + ); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } // `[T; n]` -> `[T]` unsizing (&ty::Array(a_elem_ty, ..), &ty::Slice(b_elem_ty)) => { // We just require that the element type stays the same - let nested_goals = ecx.eq(goal.param_env, a_elem_ty, b_elem_ty)?; - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.eq(goal.param_env, a_elem_ty, b_elem_ty)?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } // Struct unsizing `Struct<T>` -> `Struct<U>` where `T: Unsize<U>` (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs)) @@ -397,15 +395,14 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Finally, we require that `TailA: Unsize<TailB>` for the tail field // types. - let mut nested_goals = ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; - nested_goals.push(goal.with( + ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; + ecx.add_goal(goal.with( tcx, ty::Binder::dummy( tcx.mk_trait_ref(goal.predicate.def_id(), [a_tail_ty, b_tail_ty]), ), )); - - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } // Tuple unsizing `(.., T)` -> `(.., U)` where `T: Unsize<U>` (&ty::Tuple(a_tys), &ty::Tuple(b_tys)) @@ -417,17 +414,16 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Substitute just the tail field of B., and require that they're equal. let unsized_a_ty = tcx.mk_tup_from_iter(a_rest_tys.iter().chain([b_last_ty]).copied()); - let mut nested_goals = ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; + ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; // Similar to ADTs, require that the rest of the fields are equal. - nested_goals.push(goal.with( + ecx.add_goal(goal.with( tcx, ty::Binder::dummy( tcx.mk_trait_ref(goal.predicate.def_id(), [*a_last_ty, *b_last_ty]), ), )); - - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } _ => Err(NoSolution), } @@ -477,12 +473,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let new_a_ty = tcx.mk_dynamic(new_a_data, b_region, ty::Dyn); // We also require that A's lifetime outlives B's lifetime. - let mut nested_obligations = ecx.eq(goal.param_env, new_a_ty, b_ty)?; - nested_obligations.push( + ecx.eq(goal.param_env, new_a_ty, b_ty)?; + ecx.add_goal( goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region))), ); - - ecx.evaluate_all_and_make_canonical_response(nested_obligations) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) }; @@ -516,7 +511,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { _goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { // `DiscriminantKind` is automatically implemented for every type. - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } @@ -530,21 +525,23 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal: Goal<'tcx, TraitPredicate<'tcx>>, constituent_tys: impl Fn(&EvalCtxt<'_, 'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>, ) -> QueryResult<'tcx> { - self.probe(|this| { - this.evaluate_all_and_make_canonical_response( - constituent_tys(this, goal.predicate.self_ty())? + self.probe(|ecx| { + ecx.add_goals( + constituent_tys(ecx, goal.predicate.self_ty())? .into_iter() .map(|ty| { goal.with( - this.tcx(), - ty::Binder::dummy(goal.predicate.with_self_ty(this.tcx(), ty)), + ecx.tcx(), + ty::Binder::dummy(goal.predicate.with_self_ty(ecx.tcx(), ty)), ) }) - .collect(), - ) + .collect::<Vec<_>>(), + ); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } + #[instrument(level = "debug", skip(self))] pub(super) fn compute_trait_goal( &mut self, goal: Goal<'tcx, TraitPredicate<'tcx>>, diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs index d7d93377cf1..9817186b874 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs @@ -189,12 +189,28 @@ pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>( goal_kind: ty::ClosureKind, ) -> Result<Option<ty::Binder<'tcx, (Ty<'tcx>, Ty<'tcx>)>>, NoSolution> { match *self_ty.kind() { - ty::FnDef(def_id, substs) => Ok(Some( - tcx.fn_sig(def_id) - .subst(tcx, substs) - .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())), - )), - ty::FnPtr(sig) => Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())))), + // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed. + ty::FnDef(def_id, substs) => { + let sig = tcx.fn_sig(def_id); + if sig.skip_binder().is_fn_trait_compatible() + && tcx.codegen_fn_attrs(def_id).target_features.is_empty() + { + Ok(Some( + sig.subst(tcx, substs) + .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())), + )) + } else { + Err(NoSolution) + } + } + // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed. + ty::FnPtr(sig) => { + if sig.is_fn_trait_compatible() { + Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())))) + } else { + Err(NoSolution) + } + } ty::Closure(_, substs) => { let closure_substs = substs.as_closure(); match closure_substs.kind_ty().to_opt_closure_kind() { @@ -333,7 +349,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceProjectionWith<'_, 'tcx> { // FIXME: Technically this folder could be fallible? let nested = self .ecx - .eq(self.param_env, alias_ty, proj.projection_ty) + .eq_and_get_goals(self.param_env, alias_ty, proj.projection_ty) .expect("expected to be able to unify goal projection with dyn's projection"); // FIXME: Technically we could register these too.. assert!(nested.is_empty(), "did not expect unification to have any nested goals"); diff --git a/compiler/rustc_trait_selection/src/traits/auto_trait.rs b/compiler/rustc_trait_selection/src/traits/auto_trait.rs index 1fb8659bb27..dbf6775afc2 100644 --- a/compiler/rustc_trait_selection/src/traits/auto_trait.rs +++ b/compiler/rustc_trait_selection/src/traits/auto_trait.rs @@ -7,6 +7,7 @@ use crate::errors::UnableToConstructConstantValue; use crate::infer::region_constraints::{Constraint, RegionConstraintData}; use crate::infer::InferCtxt; use crate::traits::project::ProjectAndUnifyResult; +use rustc_infer::infer::DefineOpaqueTypes; use rustc_middle::mir::interpret::ErrorHandled; use rustc_middle::ty::fold::{TypeFolder, TypeSuperFoldable}; use rustc_middle::ty::visit::TypeVisitableExt; @@ -179,8 +180,9 @@ impl<'tcx> AutoTraitFinder<'tcx> { // At this point, we already have all of the bounds we need. FulfillmentContext is used // to store all of the necessary region/lifetime bounds in the InferContext, as well as // an additional sanity check. - let errors = - super::fully_solve_bound(&infcx, ObligationCause::dummy(), full_env, ty, trait_did); + let ocx = ObligationCtxt::new(&infcx); + ocx.register_bound(ObligationCause::dummy(), full_env, ty, trait_did); + let errors = ocx.select_all_or_error(); if !errors.is_empty() { panic!("Unable to fulfill trait {:?} for '{:?}': {:?}", trait_did, ty, errors); } @@ -814,7 +816,7 @@ impl<'tcx> AutoTraitFinder<'tcx> { match (evaluate(c1), evaluate(c2)) { (Ok(c1), Ok(c2)) => { - match selcx.infcx.at(&obligation.cause, obligation.param_env).eq(c1, c2) + match selcx.infcx.at(&obligation.cause, obligation.param_env).eq(DefineOpaqueTypes::No,c1, c2) { Ok(_) => (), Err(_) => return false, diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs index aeaade1d66c..572d20b5368 100644 --- a/compiler/rustc_trait_selection/src/traits/coherence.rs +++ b/compiler/rustc_trait_selection/src/traits/coherence.rs @@ -17,7 +17,7 @@ use crate::traits::{ use rustc_data_structures::fx::FxIndexSet; use rustc_errors::Diagnostic; use rustc_hir::def_id::{DefId, CRATE_DEF_ID, LOCAL_CRATE}; -use rustc_infer::infer::{DefiningAnchor, InferCtxt, TyCtxtInferExt}; +use rustc_infer::infer::{DefineOpaqueTypes, DefiningAnchor, InferCtxt, TyCtxtInferExt}; use rustc_infer::traits::util; use rustc_middle::traits::specialization_graph::OverlapMode; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; @@ -181,7 +181,7 @@ fn overlap_within_probe<'cx, 'tcx>( let impl1_header = with_fresh_ty_vars(selcx, param_env, impl1_def_id); let impl2_header = with_fresh_ty_vars(selcx, param_env, impl2_def_id); - let obligations = equate_impl_headers(selcx, &impl1_header, &impl2_header)?; + let obligations = equate_impl_headers(selcx.infcx, &impl1_header, &impl2_header)?; debug!("overlap: unification check succeeded"); if overlap_mode.use_implicit_negative() { @@ -207,20 +207,25 @@ fn overlap_within_probe<'cx, 'tcx>( Some(OverlapResult { impl_header, intercrate_ambiguity_causes, involves_placeholder }) } -fn equate_impl_headers<'cx, 'tcx>( - selcx: &mut SelectionContext<'cx, 'tcx>, - impl1_header: &ty::ImplHeader<'tcx>, - impl2_header: &ty::ImplHeader<'tcx>, +#[instrument(level = "debug", skip(infcx), ret)] +fn equate_impl_headers<'tcx>( + infcx: &InferCtxt<'tcx>, + impl1: &ty::ImplHeader<'tcx>, + impl2: &ty::ImplHeader<'tcx>, ) -> Option<PredicateObligations<'tcx>> { - // Do `a` and `b` unify? If not, no overlap. - debug!("equate_impl_headers(impl1_header={:?}, impl2_header={:?}", impl1_header, impl2_header); - selcx - .infcx - .at(&ObligationCause::dummy(), ty::ParamEnv::empty()) - .define_opaque_types(true) - .eq_impl_headers(impl1_header, impl2_header) - .map(|infer_ok| infer_ok.obligations) - .ok() + let result = match (impl1.trait_ref, impl2.trait_ref) { + (Some(impl1_ref), Some(impl2_ref)) => infcx + .at(&ObligationCause::dummy(), ty::ParamEnv::empty()) + .eq(DefineOpaqueTypes::Yes, impl1_ref, impl2_ref), + (None, None) => infcx.at(&ObligationCause::dummy(), ty::ParamEnv::empty()).eq( + DefineOpaqueTypes::Yes, + impl1.self_ty, + impl2.self_ty, + ), + _ => bug!("mk_eq_impl_headers given mismatched impl kinds"), + }; + + result.map(|infer_ok| infer_ok.obligations).ok() } /// Given impl1 and impl2 check if both impls can be satisfied by a common type (including @@ -325,7 +330,7 @@ fn equate<'tcx>( ) -> bool { // do the impls unify? If not, not disjoint. let Ok(InferOk { obligations: more_obligations, .. }) = - infcx.at(&ObligationCause::dummy(), impl_env).eq(subject1, subject2) + infcx.at(&ObligationCause::dummy(), impl_env).eq(DefineOpaqueTypes::No,subject1, subject2) else { debug!("explicit_disjoint: {:?} does not unify with {:?}", subject1, subject2); return true; @@ -378,7 +383,10 @@ fn resolve_negative_obligation<'tcx>( }; let param_env = o.param_env; - if !super::fully_solve_obligation(&infcx, o).is_empty() { + let ocx = ObligationCtxt::new(&infcx); + ocx.register_obligation(o); + let errors = ocx.select_all_or_error(); + if !errors.is_empty() { return false; } @@ -388,6 +396,7 @@ fn resolve_negative_obligation<'tcx>( let wf_tys = ocx.assumed_wf_types(param_env, DUMMY_SP, body_def_id); let outlives_env = OutlivesEnvironment::with_bounds( param_env, + Some(&infcx), infcx.implied_bounds_tys(param_env, body_def_id, wf_tys), ); diff --git a/compiler/rustc_trait_selection/src/traits/engine.rs b/compiler/rustc_trait_selection/src/traits/engine.rs index 62d5e50dbc5..8acc31cd410 100644 --- a/compiler/rustc_trait_selection/src/traits/engine.rs +++ b/compiler/rustc_trait_selection/src/traits/engine.rs @@ -11,7 +11,7 @@ use rustc_infer::infer::at::ToTrace; use rustc_infer::infer::canonical::{ Canonical, CanonicalQueryResponse, CanonicalVarValues, QueryResponse, }; -use rustc_infer::infer::{InferCtxt, InferOk}; +use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, InferOk}; use rustc_infer::traits::query::Fallible; use rustc_infer::traits::{ FulfillmentError, Obligation, ObligationCause, PredicateObligation, TraitEngineExt as _, @@ -128,8 +128,7 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> { { self.infcx .at(cause, param_env) - .define_opaque_types(true) - .eq_exp(a_is_expected, a, b) + .eq_exp(DefineOpaqueTypes::Yes, a_is_expected, a, b) .map(|infer_ok| self.register_infer_ok_obligations(infer_ok)) } @@ -142,8 +141,7 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> { ) -> Result<(), TypeError<'tcx>> { self.infcx .at(cause, param_env) - .define_opaque_types(true) - .eq(expected, actual) + .eq(DefineOpaqueTypes::Yes, expected, actual) .map(|infer_ok| self.register_infer_ok_obligations(infer_ok)) } @@ -157,8 +155,7 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> { ) -> Result<(), TypeError<'tcx>> { self.infcx .at(cause, param_env) - .define_opaque_types(true) - .sub(expected, actual) + .sub(DefineOpaqueTypes::Yes, expected, actual) .map(|infer_ok| self.register_infer_ok_obligations(infer_ok)) } @@ -172,8 +169,7 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> { ) -> Result<(), TypeError<'tcx>> { self.infcx .at(cause, param_env) - .define_opaque_types(true) - .sup(expected, actual) + .sup(DefineOpaqueTypes::Yes, expected, actual) .map(|infer_ok| self.register_infer_ok_obligations(infer_ok)) } diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs index 277926688e2..a9c4e126816 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs @@ -144,18 +144,22 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { trait_ref: ty::PolyTraitRef<'tcx>, obligation: &PredicateObligation<'tcx>, ) -> OnUnimplementedNote { - if self.tcx.opt_rpitit_info(obligation.cause.body_id.to_def_id()).is_some() { - return OnUnimplementedNote::default(); - } - let (def_id, substs) = self .impl_similar_to(trait_ref, obligation) .unwrap_or_else(|| (trait_ref.def_id(), trait_ref.skip_binder().substs)); let trait_ref = trait_ref.skip_binder(); - let body_hir = self.tcx.hir().local_def_id_to_hir_id(obligation.cause.body_id); - let mut flags = - vec![(sym::ItemContext, self.describe_enclosure(body_hir).map(|s| s.to_owned()))]; + let mut flags = vec![]; + // FIXME(-Zlower-impl-trait-in-trait-to-assoc-ty): HIR is not present for RPITITs, + // but I guess we could synthesize one here. We don't see any errors that rely on + // that yet, though. + let enclosure = + if let Some(body_hir) = self.tcx.opt_local_def_id_to_hir_id(obligation.cause.body_id) { + self.describe_enclosure(body_hir).map(|s| s.to_owned()) + } else { + None + }; + flags.push((sym::ItemContext, enclosure)); match obligation.cause.code() { ObligationCauseCode::BuiltinDerivedObligation(..) diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs index 5541c085075..b501840b926 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs @@ -420,6 +420,7 @@ fn suggest_restriction<'tcx>( ) { if hir_generics.where_clause_span.from_expansion() || hir_generics.where_clause_span.desugaring_kind().is_some() + || projection.map_or(false, |projection| tcx.opt_rpitit_info(projection.def_id).is_some()) { return; } @@ -2944,9 +2945,6 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ObligationCauseCode::SizedYieldType => { err.note("the yield type of a generator must have a statically known size"); } - ObligationCauseCode::SizedBoxType => { - err.note("the type of a box expression must have a statically known size"); - } ObligationCauseCode::AssignmentLhsSized => { err.note("the left-hand-side of an assignment must have a statically known size"); } diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs index 944436ab82f..23754480fcf 100644 --- a/compiler/rustc_trait_selection/src/traits/fulfill.rs +++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs @@ -2,6 +2,7 @@ use crate::infer::{InferCtxt, TyOrConstInferVar}; use rustc_data_structures::obligation_forest::ProcessResult; use rustc_data_structures::obligation_forest::{Error, ForestObligation, Outcome}; use rustc_data_structures::obligation_forest::{ObligationForest, ObligationProcessor}; +use rustc_infer::infer::DefineOpaqueTypes; use rustc_infer::traits::ProjectionCacheKey; use rustc_infer::traits::{SelectionError, TraitEngine, TraitObligation}; use rustc_middle::mir::interpret::ErrorHandled; @@ -210,6 +211,29 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { type Error = FulfillmentErrorCode<'tcx>; type OUT = Outcome<Self::Obligation, Self::Error>; + /// Compared to `needs_process_obligation` this and its callees + /// contain some optimizations that come at the price of false negatives. + /// + /// They + /// - reduce branching by covering only the most common case + /// - take a read-only view of the unification tables which allows skipping undo_log + /// construction. + /// - bail out on value-cache misses in ena to avoid pointer chasing + /// - hoist RefCell locking out of the loop + #[inline] + fn skippable_obligations<'b>( + &'b self, + it: impl Iterator<Item = &'b Self::Obligation>, + ) -> usize { + let is_unchanged = self.selcx.infcx.is_ty_infer_var_definitely_unchanged(); + + it.take_while(|o| match o.stalled_on.as_slice() { + [o] => is_unchanged(*o), + _ => false, + }) + .count() + } + /// Identifies whether a predicate obligation needs processing. /// /// This is always inlined because it has a single callsite and it is @@ -515,7 +539,7 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { if let Ok(new_obligations) = infcx .at(&obligation.cause, obligation.param_env) .trace(c1, c2) - .eq(a.substs, b.substs) + .eq(DefineOpaqueTypes::No, a.substs, b.substs) { return ProcessResult::Changed(mk_pending( new_obligations.into_obligations(), @@ -524,8 +548,9 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { } (_, Unevaluated(_)) | (Unevaluated(_), _) => (), (_, _) => { - if let Ok(new_obligations) = - infcx.at(&obligation.cause, obligation.param_env).eq(c1, c2) + if let Ok(new_obligations) = infcx + .at(&obligation.cause, obligation.param_env) + .eq(DefineOpaqueTypes::No, c1, c2) { return ProcessResult::Changed(mk_pending( new_obligations.into_obligations(), @@ -565,12 +590,11 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { match (evaluate(c1), evaluate(c2)) { (Ok(c1), Ok(c2)) => { - match self - .selcx - .infcx - .at(&obligation.cause, obligation.param_env) - .eq(c1, c2) - { + match self.selcx.infcx.at(&obligation.cause, obligation.param_env).eq( + DefineOpaqueTypes::No, + c1, + c2, + ) { Ok(inf_ok) => { ProcessResult::Changed(mk_pending(inf_ok.into_obligations())) } @@ -610,12 +634,11 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { bug!("AliasEq is only used for new solver") } ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => { - match self - .selcx - .infcx - .at(&obligation.cause, obligation.param_env) - .eq(ct.ty(), ty) - { + match self.selcx.infcx.at(&obligation.cause, obligation.param_env).eq( + DefineOpaqueTypes::No, + ct.ty(), + ty, + ) { Ok(inf_ok) => ProcessResult::Changed(mk_pending(inf_ok.into_obligations())), Err(_) => ProcessResult::Error(FulfillmentErrorCode::CodeSelectionError( SelectionError::Unimplemented, diff --git a/compiler/rustc_trait_selection/src/traits/misc.rs b/compiler/rustc_trait_selection/src/traits/misc.rs index 0bde43c54df..336db4fee6c 100644 --- a/compiler/rustc_trait_selection/src/traits/misc.rs +++ b/compiler/rustc_trait_selection/src/traits/misc.rs @@ -111,6 +111,7 @@ pub fn type_allowed_to_implement_copy<'tcx>( // Check regions assuming the self type of the impl is WF let outlives_env = OutlivesEnvironment::with_bounds( param_env, + Some(&infcx), infcx.implied_bounds_tys( param_env, parent_cause.body_id, diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs index bfeda88a6d4..b27a3929078 100644 --- a/compiler/rustc_trait_selection/src/traits/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/mod.rs @@ -30,7 +30,7 @@ use rustc_middle::ty::fold::TypeFoldable; use rustc_middle::ty::visit::{TypeVisitable, TypeVisitableExt}; use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt, TypeSuperVisitable}; use rustc_middle::ty::{InternalSubsts, SubstsRef}; -use rustc_span::def_id::{DefId, CRATE_DEF_ID}; +use rustc_span::def_id::DefId; use rustc_span::Span; use std::fmt::Debug; @@ -63,9 +63,7 @@ pub use self::util::{ elaborate_trait_ref, elaborate_trait_refs, }; pub use self::util::{expand_trait_aliases, TraitAliasExpander}; -pub use self::util::{ - get_vtable_index_of_object_method, impl_item_is_final, predicate_for_trait_def, upcast_choices, -}; +pub use self::util::{get_vtable_index_of_object_method, impl_item_is_final, upcast_choices}; pub use self::util::{ supertrait_def_ids, supertraits, transitive_bounds, transitive_bounds_that_define_assoc_type, SupertraitDefIds, Supertraits, @@ -131,29 +129,23 @@ pub fn type_known_to_meet_bound_modulo_regions<'tcx>( param_env: ty::ParamEnv<'tcx>, ty: Ty<'tcx>, def_id: DefId, - span: Span, ) -> bool { let trait_ref = ty::Binder::dummy(infcx.tcx.mk_trait_ref(def_id, [ty])); - pred_known_to_hold_modulo_regions(infcx, param_env, trait_ref.without_const(), span) + pred_known_to_hold_modulo_regions(infcx, param_env, trait_ref.without_const()) } -#[instrument(level = "debug", skip(infcx, param_env, span, pred), ret)] +/// FIXME(@lcnr): this function doesn't seem right and shouldn't exist? +/// +/// Ping me on zulip if you want to use this method and need help with finding +/// an appropriate replacement. +#[instrument(level = "debug", skip(infcx, param_env, pred), ret)] fn pred_known_to_hold_modulo_regions<'tcx>( infcx: &InferCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>, pred: impl ToPredicate<'tcx> + TypeVisitable<TyCtxt<'tcx>>, - span: Span, ) -> bool { let has_non_region_infer = pred.has_non_region_infer(); - let obligation = Obligation { - param_env, - // We can use a dummy node-id here because we won't pay any mind - // to region obligations that arise (there shouldn't really be any - // anyhow). - cause: ObligationCause::misc(span, CRATE_DEF_ID), - recursion_depth: 0, - predicate: pred.to_predicate(infcx.tcx), - }; + let obligation = Obligation::new(infcx.tcx, ObligationCause::dummy(), param_env, pred); let result = infcx.evaluate_obligation_no_overflow(&obligation); debug!(?result); @@ -166,14 +158,13 @@ fn pred_known_to_hold_modulo_regions<'tcx>( // this function's result remains infallible, we must confirm // that guess. While imperfect, I believe this is sound. - // FIXME(@lcnr): this function doesn't seem right. - // // The handling of regions in this area of the code is terrible, // see issue #29149. We should be able to improve on this with // NLL. - let errors = fully_solve_obligation(infcx, obligation); - - match &errors[..] { + let ocx = ObligationCtxt::new(infcx); + ocx.register_obligation(obligation); + let errors = ocx.select_all_or_error(); + match errors.as_slice() { [] => true, errors => { debug!(?errors); @@ -389,43 +380,6 @@ where Ok(resolved_value) } -/// Process an obligation (and any nested obligations that come from it) to -/// completion, returning any errors -pub fn fully_solve_obligation<'tcx>( - infcx: &InferCtxt<'tcx>, - obligation: PredicateObligation<'tcx>, -) -> Vec<FulfillmentError<'tcx>> { - fully_solve_obligations(infcx, [obligation]) -} - -/// Process a set of obligations (and any nested obligations that come from them) -/// to completion -pub fn fully_solve_obligations<'tcx>( - infcx: &InferCtxt<'tcx>, - obligations: impl IntoIterator<Item = PredicateObligation<'tcx>>, -) -> Vec<FulfillmentError<'tcx>> { - let ocx = ObligationCtxt::new(infcx); - ocx.register_obligations(obligations); - ocx.select_all_or_error() -} - -/// Process a bound (and any nested obligations that come from it) to completion. -/// This is a convenience function for traits that have no generic arguments, such -/// as auto traits, and builtin traits like Copy or Sized. -pub fn fully_solve_bound<'tcx>( - infcx: &InferCtxt<'tcx>, - cause: ObligationCause<'tcx>, - param_env: ty::ParamEnv<'tcx>, - ty: Ty<'tcx>, - bound: DefId, -) -> Vec<FulfillmentError<'tcx>> { - let tcx = infcx.tcx; - let trait_ref = tcx.mk_trait_ref(bound, [ty]); - let obligation = Obligation::new(tcx, cause, param_env, ty::Binder::dummy(trait_ref)); - - fully_solve_obligation(infcx, obligation) -} - /// Normalizes the predicates and checks whether they hold in an empty environment. If this /// returns true, then either normalize encountered an error or one of the predicates did not /// hold. Used when creating vtables to check for unsatisfiable methods. diff --git a/compiler/rustc_trait_selection/src/traits/object_safety.rs b/compiler/rustc_trait_selection/src/traits/object_safety.rs index a5def4151bf..038f8964471 100644 --- a/compiler/rustc_trait_selection/src/traits/object_safety.rs +++ b/compiler/rustc_trait_selection/src/traits/object_safety.rs @@ -17,10 +17,10 @@ use rustc_errors::{DelayDm, FatalError, MultiSpan}; use rustc_hir as hir; use rustc_hir::def_id::DefId; use rustc_middle::ty::subst::{GenericArg, InternalSubsts}; -use rustc_middle::ty::ToPredicate; use rustc_middle::ty::{ self, EarlyBinder, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor, }; +use rustc_middle::ty::{ToPredicate, TypeVisitableExt}; use rustc_session::lint::builtin::WHERE_CLAUSES_OBJECT_SAFETY; use rustc_span::symbol::Symbol; use rustc_span::Span; @@ -139,6 +139,10 @@ fn object_safety_violations_for_trait( if !spans.is_empty() { violations.push(ObjectSafetyViolation::SupertraitSelf(spans)); } + let spans = super_predicates_have_non_lifetime_binders(tcx, trait_def_id); + if !spans.is_empty() { + violations.push(ObjectSafetyViolation::SupertraitNonLifetimeBinder(spans)); + } violations.extend( tcx.associated_items(trait_def_id) @@ -348,6 +352,21 @@ fn predicate_references_self<'tcx>( } } +fn super_predicates_have_non_lifetime_binders( + tcx: TyCtxt<'_>, + trait_def_id: DefId, +) -> SmallVec<[Span; 1]> { + // If non_lifetime_binders is disabled, then exit early + if !tcx.features().non_lifetime_binders { + return SmallVec::new(); + } + tcx.super_predicates_of(trait_def_id) + .predicates + .iter() + .filter_map(|(pred, span)| pred.has_non_region_late_bound().then_some(*span)) + .collect() +} + fn trait_has_sized_self(tcx: TyCtxt<'_>, trait_def_id: DefId) -> bool { generics_require_sized_self(tcx, trait_def_id) } diff --git a/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs b/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs index e2c198fabde..bac02f2d383 100644 --- a/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs +++ b/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs @@ -1,10 +1,9 @@ use crate::infer::InferCtxt; use crate::traits::query::type_op::{self, TypeOp, TypeOpOutput}; use crate::traits::query::NoSolution; -use crate::traits::ObligationCause; +use crate::traits::{ObligationCause, ObligationCtxt}; use rustc_data_structures::fx::FxIndexSet; -use rustc_infer::infer::resolve::OpportunisticRegionResolver; -use rustc_middle::ty::{self, ParamEnv, Ty, TypeFolder, TypeVisitableExt}; +use rustc_middle::ty::{self, ParamEnv, Ty}; use rustc_span::def_id::LocalDefId; pub use rustc_middle::traits::query::OutlivesBound; @@ -53,10 +52,6 @@ impl<'a, 'tcx: 'a> InferCtxtExt<'a, 'tcx> for InferCtxt<'tcx> { body_id: LocalDefId, ty: Ty<'tcx>, ) -> Vec<OutlivesBound<'tcx>> { - let ty = self.resolve_vars_if_possible(ty); - let ty = OpportunisticRegionResolver::new(self).fold_ty(ty); - assert!(!ty.needs_infer()); - let span = self.tcx.def_span(body_id); let result = param_env .and(type_op::implied_outlives_bounds::ImpliedOutlivesBounds { ty }) @@ -76,22 +71,23 @@ impl<'a, 'tcx: 'a> InferCtxtExt<'a, 'tcx> for InferCtxt<'tcx> { if let Some(constraints) = constraints { debug!(?constraints); + if !constraints.member_constraints.is_empty() { + span_bug!(span, "{:#?}", constraints.member_constraints); + } + // Instantiation may have produced new inference variables and constraints on those // variables. Process these constraints. + let ocx = ObligationCtxt::new(self); let cause = ObligationCause::misc(span, body_id); - let errors = super::fully_solve_obligations( - self, - constraints.outlives.iter().map(|constraint| { - self.query_outlives_constraint_to_obligation( - *constraint, - cause.clone(), - param_env, - ) - }), - ); - if !constraints.member_constraints.is_empty() { - span_bug!(span, "{:#?}", constraints.member_constraints); + for &constraint in &constraints.outlives { + ocx.register_obligation(self.query_outlives_constraint_to_obligation( + constraint, + cause.clone(), + param_env, + )); } + + let errors = ocx.select_all_or_error(); if !errors.is_empty() { self.tcx.sess.delay_span_bug( span, @@ -110,7 +106,10 @@ impl<'a, 'tcx: 'a> InferCtxtExt<'a, 'tcx> for InferCtxt<'tcx> { tys: FxIndexSet<Ty<'tcx>>, ) -> Bounds<'a, 'tcx> { tys.into_iter() - .map(move |ty| self.implied_outlives_bounds(param_env, body_id, ty)) + .map(move |ty| { + let ty = self.resolve_vars_if_possible(ty); + self.implied_outlives_bounds(param_env, body_id, ty) + }) .flatten() } } diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs index 01075d7c55a..b8d9cff9c48 100644 --- a/compiler/rustc_trait_selection/src/traits/project.rs +++ b/compiler/rustc_trait_selection/src/traits/project.rs @@ -28,6 +28,7 @@ use rustc_hir::def::DefKind; use rustc_hir::lang_items::LangItem; use rustc_infer::infer::at::At; use rustc_infer::infer::resolve::OpportunisticRegionResolver; +use rustc_infer::infer::DefineOpaqueTypes; use rustc_infer::traits::ImplSourceBuiltinData; use rustc_middle::traits::select::OverflowError; use rustc_middle::ty::fold::{TypeFoldable, TypeFolder, TypeSuperFoldable}; @@ -285,12 +286,12 @@ fn project_and_unify_type<'cx, 'tcx>( ); obligations.extend(new); - match infcx - .at(&obligation.cause, obligation.param_env) - // This is needed to support nested opaque types like `impl Fn() -> impl Trait` - .define_opaque_types(true) - .eq(normalized, actual) - { + // Need to define opaque types to support nested opaque types like `impl Fn() -> impl Trait` + match infcx.at(&obligation.cause, obligation.param_env).eq( + DefineOpaqueTypes::Yes, + normalized, + actual, + ) { Ok(InferOk { obligations: inferred_obligations, value: () }) => { obligations.extend(inferred_obligations); ProjectAndUnifyResult::Holds(obligations) @@ -467,6 +468,11 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx return ty; } + let (kind, data) = match *ty.kind() { + ty::Alias(kind, alias_ty) => (kind, alias_ty), + _ => return ty.super_fold_with(self), + }; + // We try to be a little clever here as a performance optimization in // cases where there are nested projections under binders. // For example: @@ -490,13 +496,11 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx // replace bound vars if the current type is a `Projection` and we need // to make sure we don't forget to fold the substs regardless. - match *ty.kind() { + match kind { // This is really important. While we *can* handle this, this has // severe performance implications for large opaque types with // late-bound regions. See `issue-88862` benchmark. - ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) - if !substs.has_escaping_bound_vars() => - { + ty::Opaque if !data.substs.has_escaping_bound_vars() => { // Only normalize `impl Trait` outside of type inference, usually in codegen. match self.param_env.reveal() { Reveal::UserFacing => ty.super_fold_with(self), @@ -512,8 +516,8 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx ); } - let substs = substs.fold_with(self); - let generic_ty = self.interner().type_of(def_id); + let substs = data.substs.fold_with(self); + let generic_ty = self.interner().type_of(data.def_id); let concrete_ty = generic_ty.subst(self.interner(), substs); self.depth += 1; let folded_ty = self.fold_ty(concrete_ty); @@ -522,8 +526,9 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx } } } + ty::Opaque => ty.super_fold_with(self), - ty::Alias(ty::Projection, data) if !data.has_escaping_bound_vars() => { + ty::Projection if !data.has_escaping_bound_vars() => { // This branch is *mostly* just an optimization: when we don't // have escaping bound vars, we don't need to replace them with // placeholders (see branch below). *Also*, we know that we can @@ -562,7 +567,7 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx normalized_ty.ty().unwrap() } - ty::Alias(ty::Projection, data) => { + ty::Projection => { // If there are escaping bound vars, we temporarily replace the // bound vars with placeholders. Note though, that in the case // that we still can't project for whatever reason (e.g. self @@ -611,8 +616,6 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx ); normalized_ty } - - _ => ty.super_fold_with(self), } } @@ -1295,7 +1298,7 @@ fn assemble_candidate_for_impl_trait_in_trait<'cx, 'tcx>( ) { let tcx = selcx.tcx(); if tcx.def_kind(obligation.predicate.def_id) == DefKind::ImplTraitPlaceholder { - let trait_fn_def_id = tcx.impl_trait_in_trait_parent(obligation.predicate.def_id); + let trait_fn_def_id = tcx.impl_trait_in_trait_parent_fn(obligation.predicate.def_id); let trait_def_id = tcx.parent(trait_fn_def_id); let trait_substs = @@ -2064,7 +2067,11 @@ fn confirm_param_env_candidate<'cx, 'tcx>( debug!(?cache_projection, ?obligation_projection); - match infcx.at(cause, param_env).eq(cache_projection, obligation_projection) { + match infcx.at(cause, param_env).eq( + DefineOpaqueTypes::No, + cache_projection, + obligation_projection, + ) { Ok(InferOk { value: _, obligations }) => { nested_obligations.extend(obligations); assoc_ty_own_obligations(selcx, obligation, &mut nested_obligations); @@ -2193,7 +2200,7 @@ fn confirm_impl_trait_in_trait_candidate<'tcx>( let tcx = selcx.tcx(); let mut obligations = data.nested; - let trait_fn_def_id = tcx.impl_trait_in_trait_parent(obligation.predicate.def_id); + let trait_fn_def_id = tcx.impl_trait_in_trait_parent_fn(obligation.predicate.def_id); let leaf_def = match specialization_graph::assoc_def(tcx, data.impl_def_id, trait_fn_def_id) { Ok(assoc_ty) => assoc_ty, Err(guar) => return Progress::error(tcx, guar), diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs index b0cec3ce7a3..a986a9b6a71 100644 --- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs +++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs @@ -197,23 +197,30 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> return Ok(*ty); } + let (kind, data) = match *ty.kind() { + ty::Alias(kind, data) => (kind, data), + _ => { + let res = ty.try_super_fold_with(self)?; + self.cache.insert(ty, res); + return Ok(res); + } + }; + // See note in `rustc_trait_selection::traits::project` about why we // wait to fold the substs. // Wrap this in a closure so we don't accidentally return from the outer function - let res = match *ty.kind() { + let res = match kind { // This is really important. While we *can* handle this, this has // severe performance implications for large opaque types with // late-bound regions. See `issue-88862` benchmark. - ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) - if !substs.has_escaping_bound_vars() => - { + ty::Opaque if !data.substs.has_escaping_bound_vars() => { // Only normalize `impl Trait` outside of type inference, usually in codegen. match self.param_env.reveal() { Reveal::UserFacing => ty.try_super_fold_with(self)?, Reveal::All => { - let substs = substs.try_fold_with(self)?; + let substs = data.substs.try_fold_with(self)?; let recursion_limit = self.interner().recursion_limit(); if !recursion_limit.value_within_limit(self.anon_depth) { // A closure or generator may have itself as in its upvars. @@ -228,7 +235,7 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> return ty.try_super_fold_with(self); } - let generic_ty = self.interner().type_of(def_id); + let generic_ty = self.interner().type_of(data.def_id); let concrete_ty = generic_ty.subst(self.interner(), substs); self.anon_depth += 1; if concrete_ty == ty { @@ -248,62 +255,22 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> } } - ty::Alias(ty::Projection, data) if !data.has_escaping_bound_vars() => { - // This branch is just an optimization: when we don't have escaping bound vars, - // we don't need to replace them with placeholders (see branch below). - - let tcx = self.infcx.tcx; - let data = data.try_fold_with(self)?; - - let mut orig_values = OriginalQueryValues::default(); - // HACK(matthewjasper) `'static` is special-cased in selection, - // so we cannot canonicalize it. - let c_data = self - .infcx - .canonicalize_query_keep_static(self.param_env.and(data), &mut orig_values); - debug!("QueryNormalizer: c_data = {:#?}", c_data); - debug!("QueryNormalizer: orig_values = {:#?}", orig_values); - let result = tcx.normalize_projection_ty(c_data)?; - // We don't expect ambiguity. - if result.is_ambiguous() { - // Rustdoc normalizes possibly not well-formed types, so only - // treat this as a bug if we're not in rustdoc. - if !tcx.sess.opts.actually_rustdoc { - tcx.sess.delay_span_bug( - DUMMY_SP, - format!("unexpected ambiguity: {:?} {:?}", c_data, result), - ); - } - return Err(NoSolution); - } - let InferOk { value: result, obligations } = - self.infcx.instantiate_query_response_and_region_obligations( - self.cause, - self.param_env, - &orig_values, - result, - )?; - debug!("QueryNormalizer: result = {:#?}", result); - debug!("QueryNormalizer: obligations = {:#?}", obligations); - self.obligations.extend(obligations); - - let res = result.normalized_ty; - // `tcx.normalize_projection_ty` may normalize to a type that still has - // unevaluated consts, so keep normalizing here if that's the case. - if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) { - res.try_super_fold_with(self)? - } else { - res - } - } + ty::Opaque => ty.try_super_fold_with(self)?, - ty::Alias(ty::Projection, data) => { + ty::Projection => { // See note in `rustc_trait_selection::traits::project` let tcx = self.infcx.tcx; let infcx = self.infcx; - let (data, mapped_regions, mapped_types, mapped_consts) = - BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data); + // Just an optimization: When we don't have escaping bound vars, + // we don't need to replace them with placeholders. + let (data, maps) = if data.has_escaping_bound_vars() { + let (data, mapped_regions, mapped_types, mapped_consts) = + BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data); + (data, Some((mapped_regions, mapped_types, mapped_consts))) + } else { + (data, None) + }; let data = data.try_fold_with(self)?; let mut orig_values = OriginalQueryValues::default(); @@ -337,14 +304,18 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> debug!("QueryNormalizer: result = {:#?}", result); debug!("QueryNormalizer: obligations = {:#?}", obligations); self.obligations.extend(obligations); - let res = PlaceholderReplacer::replace_placeholders( - infcx, - mapped_regions, - mapped_types, - mapped_consts, - &self.universes, - result.normalized_ty, - ); + let res = if let Some((mapped_regions, mapped_types, mapped_consts)) = maps { + PlaceholderReplacer::replace_placeholders( + infcx, + mapped_regions, + mapped_types, + mapped_consts, + &self.universes, + result.normalized_ty, + ) + } else { + result.normalized_ty + }; // `tcx.normalize_projection_ty` may normalize to a type that still has // unevaluated consts, so keep normalizing here if that's the case. if res != ty && res.has_type_flags(ty::TypeFlags::HAS_CT_PROJECTION) { @@ -353,8 +324,6 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> res } } - - _ => ty.try_super_fold_with(self)?, }; self.cache.insert(ty, res); diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs index 6bf3ed0d0e2..8f1b05c1190 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs @@ -1,8 +1,8 @@ use crate::infer::canonical::query_response; use crate::infer::{InferCtxt, InferOk}; -use crate::traits; use crate::traits::query::type_op::TypeOpOutput; use crate::traits::query::Fallible; +use crate::traits::ObligationCtxt; use rustc_infer::infer::region_constraints::RegionConstraintData; use rustc_span::source_map::DUMMY_SP; @@ -73,7 +73,9 @@ pub fn scrape_region_constraints<'tcx, Op: super::TypeOp<'tcx, Output = R>, R>( ); let InferOk { value, obligations } = infcx.commit_if_ok(|_| op())?; - let errors = traits::fully_solve_obligations(infcx, obligations); + let ocx = ObligationCtxt::new(infcx); + ocx.register_obligations(obligations); + let errors = ocx.select_all_or_error(); if !errors.is_empty() { infcx.tcx.sess.diagnostic().delay_span_bug( DUMMY_SP, @@ -82,9 +84,7 @@ pub fn scrape_region_constraints<'tcx, Op: super::TypeOp<'tcx, Output = R>, R>( } let region_obligations = infcx.take_registered_region_obligations(); - let region_constraint_data = infcx.take_and_reset_region_constraints(); - let region_constraints = query_response::make_query_region_constraints( infcx.tcx, region_obligations diff --git a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs index 3182af989f0..e06eff34df2 100644 --- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs +++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs @@ -11,7 +11,6 @@ use rustc_infer::traits::ObligationCause; use rustc_infer::traits::{Obligation, SelectionError, TraitObligation}; use rustc_middle::ty::fast_reject::TreatProjections; use rustc_middle::ty::{self, Ty, TypeVisitableExt}; -use rustc_target::spec::abi::Abi; use crate::traits; use crate::traits::query::evaluate_obligation::InferCtxtExt; @@ -291,6 +290,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { return; } + // Keep this funtion in sync with extract_tupled_inputs_and_output_from_callable + // until the old solver (and thus this function) is removed. + // Okay to skip binder because what we are inspecting doesn't involve bound regions. let self_ty = obligation.self_ty().skip_binder(); match *self_ty.kind() { @@ -299,31 +301,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { candidates.ambiguous = true; // Could wind up being a fn() type. } // Provide an impl, but only for suitable `fn` pointers. - ty::FnPtr(_) => { - if let ty::FnSig { - unsafety: hir::Unsafety::Normal, - abi: Abi::Rust, - c_variadic: false, - .. - } = self_ty.fn_sig(self.tcx()).skip_binder() - { + ty::FnPtr(sig) => { + if sig.is_fn_trait_compatible() { candidates.vec.push(FnPointerCandidate { is_const: false }); } } // Provide an impl for suitable functions, rejecting `#[target_feature]` functions (RFC 2396). ty::FnDef(def_id, _) => { - if let ty::FnSig { - unsafety: hir::Unsafety::Normal, - abi: Abi::Rust, - c_variadic: false, - .. - } = self_ty.fn_sig(self.tcx()).skip_binder() + if self.tcx().fn_sig(def_id).skip_binder().is_fn_trait_compatible() + && self.tcx().codegen_fn_attrs(def_id).target_features.is_empty() { - if self.tcx().codegen_fn_attrs(def_id).target_features.is_empty() { - candidates - .vec - .push(FnPointerCandidate { is_const: self.tcx().is_const_fn(def_id) }); - } + candidates + .vec + .push(FnPointerCandidate { is_const: self.tcx().is_const_fn(def_id) }); } } _ => {} diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs index ee41d840bae..eb354bc3f50 100644 --- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs +++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs @@ -8,8 +8,8 @@ //! https://rustc-dev-guide.rust-lang.org/traits/resolution.html#confirmation use rustc_data_structures::stack::ensure_sufficient_stack; use rustc_hir::lang_items::LangItem; -use rustc_infer::infer::InferOk; use rustc_infer::infer::LateBoundRegionConversionTime::HigherRankedType; +use rustc_infer::infer::{DefineOpaqueTypes, InferOk}; use rustc_middle::ty::{ self, Binder, GenericParamDefKind, InternalSubsts, SubstsRef, ToPolyTraitRef, ToPredicate, TraitRef, Ty, TyCtxt, TypeVisitableExt, @@ -18,7 +18,7 @@ use rustc_session::config::TraitSolver; use rustc_span::def_id::DefId; use crate::traits::project::{normalize_with_depth, normalize_with_depth_to}; -use crate::traits::util::{self, closure_trait_ref_and_return_type, predicate_for_trait_def}; +use crate::traits::util::{self, closure_trait_ref_and_return_type}; use crate::traits::vtable::{ count_own_vtable_entries, prepare_vtable_segments, vtable_trait_first_method_offset, VtblSegment, @@ -177,7 +177,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligations.extend(self.infcx.commit_if_ok(|_| { self.infcx .at(&obligation.cause, obligation.param_env) - .sup(placeholder_trait_predicate, candidate) + .sup(DefineOpaqueTypes::No, placeholder_trait_predicate, candidate) .map(|InferOk { obligations, .. }| obligations) .map_err(|_| Unimplemented) })?); @@ -253,15 +253,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { }; let cause = obligation.derived_cause(BuiltinDerivedObligation); - ensure_sufficient_stack(|| { - self.collect_predicates_for_types( - obligation.param_env, - cause, - obligation.recursion_depth + 1, - trait_def, - nested, - ) - }) + self.collect_predicates_for_types( + obligation.param_env, + cause, + obligation.recursion_depth + 1, + trait_def, + nested, + ) } else { vec![] }; @@ -462,7 +460,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { nested.extend(self.infcx.commit_if_ok(|_| { self.infcx .at(&obligation.cause, obligation.param_env) - .sup(obligation_trait_ref, upcast_trait_ref) + .sup(DefineOpaqueTypes::No, obligation_trait_ref, upcast_trait_ref) .map(|InferOk { obligations, .. }| obligations) .map_err(|_| Unimplemented) })?); @@ -827,11 +825,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ) }); + // needed to define opaque types for tests/ui/type-alias-impl-trait/assoc-projection-ice.rs self.infcx .at(&obligation.cause, obligation.param_env) - // needed for tests/ui/type-alias-impl-trait/assoc-projection-ice.rs - .define_opaque_types(true) - .sup(obligation_trait_ref, expected_trait_ref) + .sup(DefineOpaqueTypes::Yes, obligation_trait_ref, expected_trait_ref) .map(|InferOk { mut obligations, .. }| { obligations.extend(nested); obligations @@ -896,7 +893,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let InferOk { obligations, .. } = self .infcx .at(&obligation.cause, obligation.param_env) - .sup(target, source_trait) + .sup(DefineOpaqueTypes::No, target, source_trait) .map_err(|_| Unimplemented)?; nested.extend(obligations); @@ -995,7 +992,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let InferOk { obligations, .. } = self .infcx .at(&obligation.cause, obligation.param_env) - .sup(target, source_trait) + .sup(DefineOpaqueTypes::No, target, source_trait) .map_err(|_| Unimplemented)?; nested.extend(obligations); @@ -1066,7 +1063,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let InferOk { obligations, .. } = self .infcx .at(&obligation.cause, obligation.param_env) - .eq(b, a) + .eq(DefineOpaqueTypes::No, b, a) .map_err(|_| Unimplemented)?; nested.extend(obligations); } @@ -1114,19 +1111,16 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let InferOk { obligations, .. } = self .infcx .at(&obligation.cause, obligation.param_env) - .eq(target, new_struct) + .eq(DefineOpaqueTypes::No, target, new_struct) .map_err(|_| Unimplemented)?; nested.extend(obligations); // Construct the nested `TailField<T>: Unsize<TailField<U>>` predicate. - nested.push(predicate_for_trait_def( + let tail_unsize_obligation = obligation.with( tcx, - obligation.param_env, - obligation.cause.clone(), - obligation.predicate.def_id(), - obligation.recursion_depth + 1, - [source_tail, target_tail], - )); + tcx.mk_trait_ref(obligation.predicate.def_id(), [source_tail, target_tail]), + ); + nested.push(tail_unsize_obligation); } // `(.., T)` -> `(.., U)` @@ -1144,21 +1138,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let InferOk { obligations, .. } = self .infcx .at(&obligation.cause, obligation.param_env) - .eq(target, new_tuple) + .eq(DefineOpaqueTypes::No, target, new_tuple) .map_err(|_| Unimplemented)?; nested.extend(obligations); - // Construct the nested `T: Unsize<U>` predicate. - nested.push(ensure_sufficient_stack(|| { - predicate_for_trait_def( - tcx, - obligation.param_env, - obligation.cause.clone(), - obligation.predicate.def_id(), - obligation.recursion_depth + 1, - [a_last, b_last], - ) - })); + // Add a nested `T: Unsize<U>` predicate. + let last_unsize_obligation = obligation + .with(tcx, tcx.mk_trait_ref(obligation.predicate.def_id(), [a_last, b_last])); + nested.push(last_unsize_obligation); } _ => bug!("source: {source}, target: {target}"), diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs index 38cdaddc1e7..b8758ad9323 100644 --- a/compiler/rustc_trait_selection/src/traits/select/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs @@ -17,7 +17,7 @@ use super::project; use super::project::normalize_with_depth_to; use super::project::ProjectionTyObligation; use super::util; -use super::util::{closure_trait_ref_and_return_type, predicate_for_trait_def}; +use super::util::closure_trait_ref_and_return_type; use super::wf; use super::{ ErrorReporting, ImplDerivedObligation, ImplDerivedObligationCause, Normalized, Obligation, @@ -38,6 +38,7 @@ use rustc_data_structures::stack::ensure_sufficient_stack; use rustc_errors::Diagnostic; use rustc_hir as hir; use rustc_hir::def_id::DefId; +use rustc_infer::infer::DefineOpaqueTypes; use rustc_infer::infer::LateBoundRegionConversionTime; use rustc_infer::traits::TraitEngine; use rustc_infer::traits::TraitEngineExt; @@ -594,7 +595,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.evaluate_predicates_recursively_in_new_solver(predicates) } else { let mut result = EvaluatedToOk; - for obligation in predicates { + for mut obligation in predicates { + obligation.set_depth_from_parent(stack.depth()); let eval = self.evaluate_predicate_recursively(stack, obligation.clone())?; if let EvaluatedToErr = eval { // fast-path - EvaluatedToErr is the top of the lattice, @@ -660,12 +662,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let p = bound_predicate.rebind(p); // Does this code ever run? match self.infcx.subtype_predicate(&obligation.cause, obligation.param_env, p) { - Ok(Ok(InferOk { mut obligations, .. })) => { - self.add_depth(obligations.iter_mut(), obligation.recursion_depth); - self.evaluate_predicates_recursively( - previous_stack, - obligations.into_iter(), - ) + Ok(Ok(InferOk { obligations, .. })) => { + self.evaluate_predicates_recursively(previous_stack, obligations) } Ok(Err(_)) => Ok(EvaluatedToErr), Err(..) => Ok(EvaluatedToAmbig), @@ -676,12 +674,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let p = bound_predicate.rebind(p); // Does this code ever run? match self.infcx.coerce_predicate(&obligation.cause, obligation.param_env, p) { - Ok(Ok(InferOk { mut obligations, .. })) => { - self.add_depth(obligations.iter_mut(), obligation.recursion_depth); - self.evaluate_predicates_recursively( - previous_stack, - obligations.into_iter(), - ) + Ok(Ok(InferOk { obligations, .. })) => { + self.evaluate_predicates_recursively(previous_stack, obligations) } Ok(Err(_)) => Ok(EvaluatedToErr), Err(..) => Ok(EvaluatedToAmbig), @@ -754,9 +748,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { arg, obligation.cause.span, ) { - Some(mut obligations) => { - self.add_depth(obligations.iter_mut(), obligation.recursion_depth); - + Some(obligations) => { cache.wf_args.borrow_mut().push((arg, previous_stack.depth())); let result = self.evaluate_predicates_recursively(previous_stack, obligations); @@ -825,10 +817,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } } - self.add_depth( - subobligations.iter_mut(), - obligation.recursion_depth, - ); + // Need to explicitly set the depth of nested goals here as + // projection obligations can cycle by themselves and in + // `evaluate_predicates_recursively` we only add the depth + // for parent trait goals because only these get added to the + // `TraitObligationStackList`. + for subobligation in subobligations.iter_mut() { + subobligation.set_depth_from_parent(obligation.recursion_depth); + } let res = self.evaluate_predicates_recursively( previous_stack, subobligations, @@ -908,38 +904,28 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { if a.def.did == b.def.did && tcx.def_kind(a.def.did) == DefKind::AssocConst => { - if let Ok(new_obligations) = self + if let Ok(InferOk { obligations, value: () }) = self .infcx .at(&obligation.cause, obligation.param_env) .trace(c1, c2) - .eq(a.substs, b.substs) + .eq(DefineOpaqueTypes::No, a.substs, b.substs) { - let mut obligations = new_obligations.obligations; - self.add_depth( - obligations.iter_mut(), - obligation.recursion_depth, - ); return self.evaluate_predicates_recursively( previous_stack, - obligations.into_iter(), + obligations, ); } } (_, Unevaluated(_)) | (Unevaluated(_), _) => (), (_, _) => { - if let Ok(new_obligations) = self + if let Ok(InferOk { obligations, value: () }) = self .infcx .at(&obligation.cause, obligation.param_env) - .eq(c1, c2) + .eq(DefineOpaqueTypes::No, c1, c2) { - let mut obligations = new_obligations.obligations; - self.add_depth( - obligations.iter_mut(), - obligation.recursion_depth, - ); return self.evaluate_predicates_recursively( previous_stack, - obligations.into_iter(), + obligations, ); } } @@ -964,8 +950,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { match (evaluate(c1), evaluate(c2)) { (Ok(c1), Ok(c2)) => { - match self.infcx.at(&obligation.cause, obligation.param_env).eq(c1, c2) - { + match self.infcx.at(&obligation.cause, obligation.param_env).eq( + DefineOpaqueTypes::No, + c1, + c2, + ) { Ok(inf_ok) => self.evaluate_predicates_recursively( previous_stack, inf_ok.into_obligations(), @@ -993,7 +982,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } ty::PredicateKind::Ambiguous => Ok(EvaluatedToAmbig), ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => { - match self.infcx.at(&obligation.cause, obligation.param_env).eq(ct.ty(), ty) { + match self.infcx.at(&obligation.cause, obligation.param_env).eq( + DefineOpaqueTypes::No, + ct.ty(), + ty, + ) { Ok(inf_ok) => self.evaluate_predicates_recursively( previous_stack, inf_ok.into_obligations(), @@ -1358,24 +1351,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.infcx.evaluation_cache.insert((param_env, trait_pred), dep_node, result); } - /// For various reasons, it's possible for a subobligation - /// to have a *lower* recursion_depth than the obligation used to create it. - /// Projection sub-obligations may be returned from the projection cache, - /// which results in obligations with an 'old' `recursion_depth`. - /// Additionally, methods like `InferCtxt.subtype_predicate` produce - /// subobligations without taking in a 'parent' depth, causing the - /// generated subobligations to have a `recursion_depth` of `0`. - /// - /// To ensure that obligation_depth never decreases, we force all subobligations - /// to have at least the depth of the original obligation. - fn add_depth<T: 'cx, I: Iterator<Item = &'cx mut Obligation<'tcx, T>>>( - &self, - it: I, - min_depth: usize, - ) { - it.for_each(|o| o.recursion_depth = cmp::max(min_depth, o.recursion_depth) + 1); - } - fn check_recursion_depth<T>( &self, depth: usize, @@ -1751,7 +1726,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { }); self.infcx .at(&obligation.cause, obligation.param_env) - .sup(ty::Binder::dummy(placeholder_trait_ref), trait_bound) + .sup(DefineOpaqueTypes::No, ty::Binder::dummy(placeholder_trait_ref), trait_bound) .map(|InferOk { obligations: _, value: () }| { // This method is called within a probe, so we can't have // inference variables and placeholders escape. @@ -1813,7 +1788,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let is_match = self .infcx .at(&obligation.cause, obligation.param_env) - .sup(obligation.predicate, infer_projection) + .sup(DefineOpaqueTypes::No, obligation.predicate, infer_projection) .map_or(false, |InferOk { obligations, value: () }| { self.evaluate_predicates_recursively( TraitObligationStackList::empty(&ProvisionalEvaluationCache::default()), @@ -2432,15 +2407,14 @@ impl<'tcx> SelectionContext<'_, 'tcx> { placeholder_ty, ) }); - let placeholder_obligation = predicate_for_trait_def( + + let obligation = Obligation::new( self.tcx(), - param_env, cause.clone(), - trait_def_id, - recursion_depth, - [normalized_ty], + param_env, + self.tcx().mk_trait_ref(trait_def_id, [normalized_ty]), ); - obligations.push(placeholder_obligation); + obligations.push(obligation); obligations }) .collect() @@ -2534,7 +2508,7 @@ impl<'tcx> SelectionContext<'_, 'tcx> { let InferOk { obligations, .. } = self .infcx .at(&cause, obligation.param_env) - .eq(placeholder_obligation_trait_ref, impl_trait_ref) + .eq(DefineOpaqueTypes::No, placeholder_obligation_trait_ref, impl_trait_ref) .map_err(|e| { debug!("match_impl: failed eq_trait_refs due to `{}`", e.to_string(self.tcx())) })?; @@ -2584,7 +2558,7 @@ impl<'tcx> SelectionContext<'_, 'tcx> { ) -> Result<Vec<PredicateObligation<'tcx>>, ()> { self.infcx .at(&obligation.cause, obligation.param_env) - .sup(obligation.predicate.to_poly_trait_ref(), poly_trait_ref) + .sup(DefineOpaqueTypes::No, obligation.predicate.to_poly_trait_ref(), poly_trait_ref) .map(|InferOk { obligations, .. }| obligations) .map_err(|_| ()) } diff --git a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs index fcfb60b2603..8546bbe52dc 100644 --- a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs @@ -10,6 +10,7 @@ //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/specialization.html pub mod specialization_graph; +use rustc_infer::infer::DefineOpaqueTypes; use specialization_graph::GraphExt; use crate::errors::NegativePositiveConflict; @@ -21,7 +22,7 @@ use crate::traits::{ use rustc_data_structures::fx::FxIndexSet; use rustc_errors::{error_code, DelayDm, Diagnostic}; use rustc_hir::def_id::{DefId, LocalDefId}; -use rustc_middle::ty::{self, ImplSubject, Ty, TyCtxt}; +use rustc_middle::ty::{self, ImplSubject, Ty, TyCtxt, TypeVisitableExt}; use rustc_middle::ty::{InternalSubsts, SubstsRef}; use rustc_session::lint::builtin::COHERENCE_LEAK_CHECK; use rustc_session::lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS; @@ -193,7 +194,7 @@ fn fulfill_implication<'tcx>( // do the impls unify? If not, no specialization. let Ok(InferOk { obligations: more_obligations, .. }) = - infcx.at(&ObligationCause::dummy(), param_env).eq(source_trait, target_trait) + infcx.at(&ObligationCause::dummy(), param_env, ).eq(DefineOpaqueTypes::No,source_trait, target_trait) else { debug!( "fulfill_implication: {:?} does not unify with {:?}", @@ -349,6 +350,10 @@ fn report_conflicting_impls<'tcx>( impl_span: Span, err: &mut Diagnostic, ) { + if (overlap.trait_ref, overlap.self_ty).references_error() { + err.downgrade_to_delayed_bug(); + } + match tcx.span_of_impl(overlap.with_impl) { Ok(span) => { err.span_label(span, "first implementation here"); diff --git a/compiler/rustc_trait_selection/src/traits/util.rs b/compiler/rustc_trait_selection/src/traits/util.rs index bcf63d5a6f6..00c9a352258 100644 --- a/compiler/rustc_trait_selection/src/traits/util.rs +++ b/compiler/rustc_trait_selection/src/traits/util.rs @@ -1,15 +1,14 @@ -use rustc_errors::Diagnostic; -use rustc_span::Span; -use smallvec::SmallVec; - +use super::NormalizeExt; +use super::{ObligationCause, PredicateObligation, SelectionContext}; use rustc_data_structures::fx::FxHashSet; +use rustc_errors::Diagnostic; use rustc_hir::def_id::DefId; +use rustc_infer::infer::InferOk; +use rustc_middle::ty::SubstsRef; use rustc_middle::ty::{self, ImplSubject, ToPredicate, Ty, TyCtxt, TypeVisitableExt}; -use rustc_middle::ty::{GenericArg, SubstsRef}; +use rustc_span::Span; +use smallvec::SmallVec; -use super::NormalizeExt; -use super::{Obligation, ObligationCause, PredicateObligation, SelectionContext}; -use rustc_infer::infer::InferOk; pub use rustc_infer::traits::{self, util::*}; /////////////////////////////////////////////////////////////////////////// @@ -201,6 +200,7 @@ pub fn impl_subject_and_oblig<'a, 'tcx>( ) -> (ImplSubject<'tcx>, impl Iterator<Item = PredicateObligation<'tcx>>) { let subject = selcx.tcx().bound_impl_subject(impl_def_id); let subject = subject.subst(selcx.tcx(), impl_substs); + let InferOk { value: subject, obligations: normalization_obligations1 } = selcx.infcx.at(&ObligationCause::dummy(), param_env).normalize(subject); @@ -218,33 +218,6 @@ pub fn impl_subject_and_oblig<'a, 'tcx>( (subject, impl_obligations) } -pub fn predicate_for_trait_ref<'tcx>( - tcx: TyCtxt<'tcx>, - cause: ObligationCause<'tcx>, - param_env: ty::ParamEnv<'tcx>, - trait_ref: ty::TraitRef<'tcx>, - recursion_depth: usize, -) -> PredicateObligation<'tcx> { - Obligation { - cause, - param_env, - recursion_depth, - predicate: ty::Binder::dummy(trait_ref).without_const().to_predicate(tcx), - } -} - -pub fn predicate_for_trait_def<'tcx>( - tcx: TyCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, - cause: ObligationCause<'tcx>, - trait_def_id: DefId, - recursion_depth: usize, - params: impl IntoIterator<Item: Into<GenericArg<'tcx>>>, -) -> PredicateObligation<'tcx> { - let trait_ref = tcx.mk_trait_ref(trait_def_id, params); - predicate_for_trait_ref(tcx, cause, param_env, trait_ref, recursion_depth) -} - /// Casts a trait reference into a reference to one of its super /// traits; returns `None` if `target_trait_def_id` is not a /// supertrait. |