diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve')
20 files changed, 2091 insertions, 1382 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs index 422a6ee34..6b839d64b 100644 --- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs +++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs @@ -1,3 +1,16 @@ +//! Implements the `AliasRelate` goal, which is used when unifying aliases. +//! Doing this via a separate goal is called "deferred alias relation" and part +//! of our more general approach to "lazy normalization". +//! +//! This goal, e.g. `A alias-relate B`, may be satisfied by one of three branches: +//! * normalizes-to: If `A` is a projection, we can prove the equivalent +//! projection predicate with B as the right-hand side of the projection. +//! This goal is computed in both directions, if both are aliases. +//! * subst-relate: Equate `A` and `B` by their substs, if they're both +//! aliases with the same def-id. +//! * bidirectional-normalizes-to: If `A` and `B` are both projections, and both +//! may apply, then we can compute the "intersection" of both normalizes-to by +//! performing them together. This is used specifically to resolve ambiguities. use super::{EvalCtxt, SolverMode}; use rustc_infer::traits::query::NoSolution; use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; @@ -65,25 +78,28 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { direction, Invert::Yes, )); - // Relate via substs - let subst_relate_response = self - .assemble_subst_relate_candidate(param_env, alias_lhs, alias_rhs, direction); - candidates.extend(subst_relate_response); + // Relate via args + candidates.extend( + self.assemble_subst_relate_candidate( + param_env, alias_lhs, alias_rhs, direction, + ), + ); debug!(?candidates); if let Some(merged) = self.try_merge_responses(&candidates) { Ok(merged) } else { - // When relating two aliases and we have ambiguity, we prefer - // relating the generic arguments of the aliases over normalizing - // them. This is necessary for inference during typeck. + // When relating two aliases and we have ambiguity, if both + // aliases can be normalized to something, we prefer + // "bidirectionally normalizing" both of them within the same + // candidate. + // + // See <https://github.com/rust-lang/trait-system-refactor-initiative/issues/25>. // // As this is incomplete, we must not do so during coherence. match self.solver_mode() { SolverMode::Normal => { - if let Ok(subst_relate_response) = subst_relate_response { - Ok(subst_relate_response) - } else if let Ok(bidirectional_normalizes_to_response) = self + if let Ok(bidirectional_normalizes_to_response) = self .assemble_bidirectional_normalizes_to_candidate( param_env, lhs, rhs, direction, ) @@ -115,6 +131,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }) } + // Computes the normalizes-to branch, with side-effects. This must be performed + // in a probe in order to not taint the evaluation context. fn normalizes_to_inner( &mut self, param_env: ty::ParamEnv<'tcx>, @@ -124,9 +142,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { invert: Invert, ) -> Result<(), NoSolution> { let other = match direction { - // This is purely an optimization. + // This is purely an optimization. No need to instantiate a new + // infer var and equate the RHS to it. ty::AliasRelationDirection::Equate => other, + // Instantiate an infer var and subtype our RHS to it, so that we + // properly represent a subtype relation between the LHS and RHS + // of the goal. ty::AliasRelationDirection::Subtype => { let fresh = self.next_term_infer_of_kind(other); let (sub, sup) = match invert { @@ -140,7 +162,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.add_goal(Goal::new( self.tcx(), param_env, - ty::Binder::dummy(ty::ProjectionPredicate { projection_ty: alias, term: other }), + ty::ProjectionPredicate { projection_ty: alias, term: other }, )); Ok(()) @@ -153,7 +175,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { alias_rhs: ty::AliasTy<'tcx>, direction: ty::AliasRelationDirection, ) -> QueryResult<'tcx> { - self.probe_candidate("substs relate").enter(|ecx| { + self.probe_candidate("args relate").enter(|ecx| { match direction { ty::AliasRelationDirection::Equate => { ecx.eq(param_env, alias_lhs, alias_rhs)?; diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index 28138054a..36194f973 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -1,18 +1,18 @@ //! Code shared by trait and projection goals for candidate assembly. -use super::search_graph::OverflowHandler; use super::{EvalCtxt, SolverMode}; use crate::traits::coherence; -use rustc_data_structures::fx::FxIndexSet; use rustc_hir::def_id::DefId; use rustc_infer::traits::query::NoSolution; -use rustc_infer::traits::util::elaborate; use rustc_infer::traits::Reveal; use rustc_middle::traits::solve::inspect::CandidateKind; -use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult}; -use rustc_middle::ty::fast_reject::TreatProjections; -use rustc_middle::ty::TypeFoldable; +use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; +use rustc_middle::traits::BuiltinImplSource; +use rustc_middle::ty::fast_reject::{SimplifiedType, TreatParams}; use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_middle::ty::{fast_reject, TypeFoldable}; +use rustc_middle::ty::{ToPredicate, TypeVisitableExt}; +use rustc_span::ErrorGuaranteed; use std::fmt::Debug; pub(super) mod structural_traits; @@ -87,16 +87,6 @@ pub(super) enum CandidateSource { AliasBound, } -/// Records additional information about what kind of built-in impl this is. -/// This should only be used by selection. -#[derive(Debug, Clone, Copy)] -pub(super) enum BuiltinImplSource { - TraitUpcasting, - Object, - Misc, - Ambiguity, -} - /// Methods used to assemble candidates for either trait or projection goals. pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq + std::fmt::Display @@ -109,10 +99,10 @@ pub(super) trait GoalKind<'tcx>: fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId; - // Try equating an assumption predicate against a goal's predicate. If it - // holds, then execute the `then` callback, which should do any additional - // work, then produce a response (typically by executing - // [`EvalCtxt::evaluate_added_goals_and_make_canonical_response`]). + /// Try equating an assumption predicate against a goal's predicate. If it + /// holds, then execute the `then` callback, which should do any additional + /// work, then produce a response (typically by executing + /// [`EvalCtxt::evaluate_added_goals_and_make_canonical_response`]). fn probe_and_match_goal_against_assumption( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, @@ -120,9 +110,9 @@ pub(super) trait GoalKind<'tcx>: then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>, ) -> QueryResult<'tcx>; - // Consider a clause, which consists of a "assumption" and some "requirements", - // to satisfy a goal. If the requirements hold, then attempt to satisfy our - // goal by equating it with the assumption. + /// Consider a clause, which consists of a "assumption" and some "requirements", + /// to satisfy a goal. If the requirements hold, then attempt to satisfy our + /// goal by equating it with the assumption. fn consider_implied_clause( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, @@ -149,9 +139,9 @@ pub(super) trait GoalKind<'tcx>: }) } - // Consider a clause specifically for a `dyn Trait` self type. This requires - // additionally checking all of the supertraits and object bounds to hold, - // since they're not implied by the well-formedness of the object type. + /// Consider a clause specifically for a `dyn Trait` self type. This requires + /// additionally checking all of the supertraits and object bounds to hold, + /// since they're not implied by the well-formedness of the object type. fn consider_object_bound_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, @@ -160,18 +150,14 @@ pub(super) trait GoalKind<'tcx>: Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { let tcx = ecx.tcx(); let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { - bug!("expected object type in `consider_object_bound_candidate`"); - }; - ecx.add_goals( - structural_traits::predicates_for_object_candidate( - &ecx, - goal.param_env, - goal.predicate.trait_ref(tcx), - bounds, - ) - .into_iter() - .map(|pred| goal.with(tcx, pred)), - ); + bug!("expected object type in `consider_object_bound_candidate`"); + }; + ecx.add_goals(structural_traits::predicates_for_object_candidate( + &ecx, + goal.param_env, + goal.predicate.trait_ref(tcx), + bounds, + )); ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -182,112 +168,137 @@ pub(super) trait GoalKind<'tcx>: impl_def_id: DefId, ) -> QueryResult<'tcx>; - // A type implements an `auto trait` if its components do as well. These components - // are given by built-in rules from [`instantiate_constituent_tys_for_auto_trait`]. + /// If the predicate contained an error, we want to avoid emitting unnecessary trait + /// errors but still want to emit errors for other trait goals. We have some special + /// handling for this case. + /// + /// Trait goals always hold while projection goals never do. This is a bit arbitrary + /// but prevents incorrect normalization while hiding any trait errors. + fn consider_error_guaranteed_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + guar: ErrorGuaranteed, + ) -> QueryResult<'tcx>; + + /// A type implements an `auto trait` if its components do as well. + /// + /// These components are given by built-in rules from + /// [`structural_traits::instantiate_constituent_tys_for_auto_trait`]. fn consider_auto_trait_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // A trait alias holds if the RHS traits and `where` clauses hold. + /// A trait alias holds if the RHS traits and `where` clauses hold. fn consider_trait_alias_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // A type is `Copy` or `Clone` if its components are `Sized`. These components - // are given by built-in rules from [`instantiate_constituent_tys_for_sized_trait`]. + /// A type is `Copy` or `Clone` if its components are `Sized`. + /// + /// These components are given by built-in rules from + /// [`structural_traits::instantiate_constituent_tys_for_sized_trait`]. fn consider_builtin_sized_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // A type is `Copy` or `Clone` if its components are `Copy` or `Clone`. These - // components are given by built-in rules from [`instantiate_constituent_tys_for_copy_clone_trait`]. + /// A type is `Copy` or `Clone` if its components are `Copy` or `Clone`. + /// + /// These components are given by built-in rules from + /// [`structural_traits::instantiate_constituent_tys_for_copy_clone_trait`]. fn consider_builtin_copy_clone_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // A type is `PointerLike` if we can compute its layout, and that layout - // matches the layout of `usize`. + /// A type is `PointerLike` if we can compute its layout, and that layout + /// matches the layout of `usize`. fn consider_builtin_pointer_like_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // A type is a `FnPtr` if it is of `FnPtr` type. + /// A type is a `FnPtr` if it is of `FnPtr` type. fn consider_builtin_fn_ptr_trait_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>` - // family of traits where `A` is given by the signature of the type. + /// A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>` + /// family of traits where `A` is given by the signature of the type. fn consider_builtin_fn_trait_candidates( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, kind: ty::ClosureKind, ) -> QueryResult<'tcx>; - // `Tuple` is implemented if the `Self` type is a tuple. + /// `Tuple` is implemented if the `Self` type is a tuple. fn consider_builtin_tuple_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // `Pointee` is always implemented. - // - // See the projection implementation for the `Metadata` types for all of - // the built-in types. For structs, the metadata type is given by the struct - // tail. + /// `Pointee` is always implemented. + /// + /// See the projection implementation for the `Metadata` types for all of + /// the built-in types. For structs, the metadata type is given by the struct + /// tail. fn consider_builtin_pointee_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // A generator (that comes from an `async` desugaring) is known to implement - // `Future<Output = O>`, where `O` is given by the generator's return type - // that was computed during type-checking. + /// A generator (that comes from an `async` desugaring) is known to implement + /// `Future<Output = O>`, where `O` is given by the generator's return type + /// that was computed during type-checking. fn consider_builtin_future_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // A generator (that doesn't come from an `async` desugaring) is known to - // implement `Generator<R, Yield = Y, Return = O>`, given the resume, yield, - // and return types of the generator computed during type-checking. + /// A generator (that doesn't come from an `async` desugaring) is known to + /// implement `Generator<R, Yield = Y, Return = O>`, given the resume, yield, + /// and return types of the generator computed during type-checking. fn consider_builtin_generator_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // The most common forms of unsizing are array to slice, and concrete (Sized) - // type into a `dyn Trait`. ADTs and Tuples can also have their final field - // unsized if it's generic. - fn consider_builtin_unsize_candidate( + fn consider_builtin_discriminant_kind_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - // `dyn Trait1` can be unsized to `dyn Trait2` if they are the same trait, or - // if `Trait2` is a (transitive) supertrait of `Trait2`. - fn consider_builtin_dyn_upcast_candidates( + fn consider_builtin_destruct_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - ) -> Vec<CanonicalResponse<'tcx>>; + ) -> QueryResult<'tcx>; - fn consider_builtin_discriminant_kind_candidate( + fn consider_builtin_transmute_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; - fn consider_builtin_destruct_candidate( + /// Consider (possibly several) candidates to upcast or unsize a type to another + /// type, excluding the coercion of a sized type into a `dyn Trait`. + /// + /// We return the `BuiltinImplSource` for each candidate as it is needed + /// for unsize coercion in hir typeck and because it is difficult to + /// otherwise recompute this for codegen. This is a bit of a mess but the + /// easiest way to maintain the existing behavior for now. + fn consider_structural_builtin_unsize_candidates( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx>; + ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)>; - fn consider_builtin_transmute_candidate( + /// Consider the `Unsize` candidate corresponding to coercing a sized type + /// into a `dyn Trait`. + /// + /// This is computed separately from the rest of the `Unsize` candidates + /// since it is only done once per self type, and not once per + /// *normalization step* (in `assemble_candidates_via_self_ty`). + fn consider_unsize_to_dyn_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; @@ -299,35 +310,68 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal: Goal<'tcx, G>, ) -> Vec<Candidate<'tcx>> { debug_assert_eq!(goal, self.resolve_vars_if_possible(goal)); + if let Some(ambig) = self.assemble_self_ty_infer_ambiguity_response(goal) { + return ambig; + } + + let mut candidates = self.assemble_candidates_via_self_ty(goal, 0); + + self.assemble_unsize_to_dyn_candidate(goal, &mut candidates); + + self.assemble_blanket_impl_candidates(goal, &mut candidates); + + self.assemble_param_env_candidates(goal, &mut candidates); + + self.assemble_coherence_unknowable_candidates(goal, &mut candidates); - // HACK: `_: Trait` is ambiguous, because it may be satisfied via a builtin rule, - // object bound, alias bound, etc. We are unable to determine this until we can at - // least structurally resolve the type one layer. - if goal.predicate.self_ty().is_ty_var() { - return vec![Candidate { - source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity), + candidates + } + + /// `?0: Trait` is ambiguous, because it may be satisfied via a builtin rule, + /// object bound, alias bound, etc. We are unable to determine this until we can at + /// least structurally resolve the type one layer. + /// + /// It would also require us to consider all impls of the trait, which is both pretty + /// bad for perf and would also constrain the self type if there is just a single impl. + fn assemble_self_ty_infer_ambiguity_response<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + ) -> Option<Vec<Candidate<'tcx>>> { + goal.predicate.self_ty().is_ty_var().then(|| { + vec![Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), result: self .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) .unwrap(), - }]; + }] + }) + } + + /// Assemble candidates which apply to the self type. This only looks at candidate which + /// apply to the specific self type and ignores all others. + /// + /// Returns `None` if the self type is still ambiguous. + fn assemble_candidates_via_self_ty<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + num_steps: usize, + ) -> Vec<Candidate<'tcx>> { + debug_assert_eq!(goal, self.resolve_vars_if_possible(goal)); + if let Some(ambig) = self.assemble_self_ty_infer_ambiguity_response(goal) { + return ambig; } let mut candidates = Vec::new(); - self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates); - - self.assemble_impl_candidates(goal, &mut candidates); + self.assemble_non_blanket_impl_candidates(goal, &mut candidates); self.assemble_builtin_impl_candidates(goal, &mut candidates); - self.assemble_param_env_candidates(goal, &mut candidates); - self.assemble_alias_bound_candidates(goal, &mut candidates); self.assemble_object_bound_candidates(goal, &mut candidates); - self.assemble_coherence_unknowable_candidates(goal, &mut candidates); - + self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates, num_steps); candidates } @@ -350,70 +394,179 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { &mut self, goal: Goal<'tcx, G>, candidates: &mut Vec<Candidate<'tcx>>, + num_steps: usize, + ) { + let tcx = self.tcx(); + let &ty::Alias(_, projection_ty) = goal.predicate.self_ty().kind() else { return }; + + candidates.extend(self.probe(|_| CandidateKind::NormalizedSelfTyAssembly).enter(|ecx| { + if num_steps < ecx.local_overflow_limit() { + let normalized_ty = ecx.next_ty_infer(); + let normalizes_to_goal = goal.with( + tcx, + ty::ProjectionPredicate { projection_ty, term: normalized_ty.into() }, + ); + ecx.add_goal(normalizes_to_goal); + if let Err(NoSolution) = ecx.try_evaluate_added_goals() { + debug!("self type normalization failed"); + return vec![]; + } + let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty); + debug!(?normalized_ty, "self type normalized"); + // 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)); + ecx.assemble_candidates_via_self_ty(goal, num_steps + 1) + } else { + match ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW) { + Ok(result) => vec![Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), + result, + }], + Err(NoSolution) => vec![], + } + } + })); + } + + #[instrument(level = "debug", skip_all)] + fn assemble_non_blanket_impl_candidates<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, ) { let tcx = self.tcx(); - let &ty::Alias(_, projection_ty) = goal.predicate.self_ty().kind() else { - return + let self_ty = goal.predicate.self_ty(); + let trait_impls = tcx.trait_impls_of(goal.predicate.trait_def_id(tcx)); + let mut consider_impls_for_simplified_type = |simp| { + if let Some(impls_for_type) = trait_impls.non_blanket_impls().get(&simp) { + for &impl_def_id in impls_for_type { + match G::consider_impl_candidate(self, goal, impl_def_id) { + Ok(result) => candidates + .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }), + Err(NoSolution) => (), + } + } + } }; - let normalized_self_candidates: Result<_, NoSolution> = - self.probe(|_| CandidateKind::NormalizedSelfTyAssembly).enter(|ecx| { - ecx.with_incremented_depth( - |ecx| { - let result = ecx.evaluate_added_goals_and_make_canonical_response( - Certainty::Maybe(MaybeCause::Overflow), - )?; - Ok(vec![Candidate { - source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity), - result, - }]) - }, - |ecx| { - let normalized_ty = ecx.next_ty_infer(); - let normalizes_to_goal = goal.with( - tcx, - ty::Binder::dummy(ty::ProjectionPredicate { - projection_ty, - term: normalized_ty.into(), - }), - ); - ecx.add_goal(normalizes_to_goal); - let _ = ecx.try_evaluate_added_goals().inspect_err(|_| { - debug!("self type normalization failed"); - })?; - let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty); - debug!(?normalized_ty, "self type normalized"); - // 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)); - Ok(ecx.assemble_and_evaluate_candidates(goal)) - }, - ) - }); + match self_ty.kind() { + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Adt(_, _) + | ty::Foreign(_) + | ty::Str + | ty::Array(_, _) + | ty::Slice(_) + | ty::RawPtr(_) + | ty::Ref(_, _, _) + | ty::FnDef(_, _) + | ty::FnPtr(_) + | ty::Dynamic(_, _, _) + | ty::Closure(_, _) + | ty::Generator(_, _, _) + | ty::Never + | ty::Tuple(_) => { + let simp = + fast_reject::simplify_type(tcx, self_ty, TreatParams::ForLookup).unwrap(); + consider_impls_for_simplified_type(simp); + } + + // HACK: For integer and float variables we have to manually look at all impls + // which have some integer or float as a self type. + ty::Infer(ty::IntVar(_)) => { + use ty::IntTy::*; + use ty::UintTy::*; + // This causes a compiler error if any new integer kinds are added. + let (I8 | I16 | I32 | I64 | I128 | Isize): ty::IntTy; + let (U8 | U16 | U32 | U64 | U128 | Usize): ty::UintTy; + let possible_integers = [ + // signed integers + SimplifiedType::Int(I8), + SimplifiedType::Int(I16), + SimplifiedType::Int(I32), + SimplifiedType::Int(I64), + SimplifiedType::Int(I128), + SimplifiedType::Int(Isize), + // unsigned integers + SimplifiedType::Uint(U8), + SimplifiedType::Uint(U16), + SimplifiedType::Uint(U32), + SimplifiedType::Uint(U64), + SimplifiedType::Uint(U128), + SimplifiedType::Uint(Usize), + ]; + for simp in possible_integers { + consider_impls_for_simplified_type(simp); + } + } + + ty::Infer(ty::FloatVar(_)) => { + // This causes a compiler error if any new float kinds are added. + let (ty::FloatTy::F32 | ty::FloatTy::F64); + let possible_floats = [ + SimplifiedType::Float(ty::FloatTy::F32), + SimplifiedType::Float(ty::FloatTy::F64), + ]; + + for simp in possible_floats { + consider_impls_for_simplified_type(simp); + } + } + + // The only traits applying to aliases and placeholders are blanket impls. + // + // Impls which apply to an alias after normalization are handled by + // `assemble_candidates_after_normalizing_self_ty`. + ty::Alias(_, _) | ty::Placeholder(..) | ty::Error(_) => (), + + // FIXME: These should ideally not exist as a self type. It would be nice for + // the builtin auto trait impls of generators to instead directly recurse + // into the witness. + ty::GeneratorWitness(_) | ty::GeneratorWitnessMIR(_, _) => (), + + // These variants should not exist as a self type. + ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) + | ty::Param(_) + | ty::Bound(_, _) => bug!("unexpected self type: {self_ty}"), + } + } - if let Ok(normalized_self_candidates) = normalized_self_candidates { - candidates.extend(normalized_self_candidates); + fn assemble_unsize_to_dyn_candidate<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + let tcx = self.tcx(); + if tcx.lang_items().unsize_trait() == Some(goal.predicate.trait_def_id(tcx)) { + match G::consider_unsize_to_dyn_candidate(self, goal) { + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), + result, + }), + Err(NoSolution) => (), + } } } - #[instrument(level = "debug", skip_all)] - fn assemble_impl_candidates<G: GoalKind<'tcx>>( + fn assemble_blanket_impl_candidates<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, candidates: &mut Vec<Candidate<'tcx>>, ) { let tcx = self.tcx(); - tcx.for_each_relevant_impl_treating_projections( - goal.predicate.trait_def_id(tcx), - goal.predicate.self_ty(), - TreatProjections::NextSolverLookup, - |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) { + let trait_impls = tcx.trait_impls_of(goal.predicate.trait_def_id(tcx)); + for &impl_def_id in trait_impls.blanket_impls() { + match G::consider_impl_candidate(self, goal, impl_def_id) { Ok(result) => candidates .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }), Err(NoSolution) => (), - }, - ); + } + } } #[instrument(level = "debug", skip_all)] @@ -422,8 +575,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal: Goal<'tcx, G>, candidates: &mut Vec<Candidate<'tcx>>, ) { - let lang_items = self.tcx().lang_items(); - let trait_def_id = goal.predicate.trait_def_id(self.tcx()); + let tcx = self.tcx(); + let lang_items = tcx.lang_items(); + let trait_def_id = goal.predicate.trait_def_id(tcx); // N.B. When assembling built-in candidates for lang items that are also // `auto` traits, then the auto trait candidate that is assembled in @@ -432,9 +586,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // Instead of adding the logic here, it's a better idea to add it in // `EvalCtxt::disqualify_auto_trait_candidate_due_to_possible_impl` in // `solve::trait_goals` instead. - let result = if self.tcx().trait_is_auto(trait_def_id) { + let result = if let Err(guar) = goal.predicate.error_reported() { + G::consider_error_guaranteed_candidate(self, guar) + } else if tcx.trait_is_auto(trait_def_id) { G::consider_auto_trait_candidate(self, goal) - } else if self.tcx().trait_is_alias(trait_def_id) { + } else if tcx.trait_is_alias(trait_def_id) { G::consider_trait_alias_candidate(self, goal) } else if lang_items.sized_trait() == Some(trait_def_id) { G::consider_builtin_sized_candidate(self, goal) @@ -456,8 +612,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { G::consider_builtin_future_candidate(self, goal) } else if lang_items.gen_trait() == Some(trait_def_id) { G::consider_builtin_generator_candidate(self, goal) - } else if lang_items.unsize_trait() == Some(trait_def_id) { - G::consider_builtin_unsize_candidate(self, goal) } else if lang_items.discriminant_kind_trait() == Some(trait_def_id) { G::consider_builtin_discriminant_kind_candidate(self, goal) } else if lang_items.destruct_trait() == Some(trait_def_id) { @@ -479,11 +633,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // There may be multiple unsize candidates for a trait with several supertraits: // `trait Foo: Bar<A> + Bar<B>` and `dyn Foo: Unsize<dyn Bar<_>>` if lang_items.unsize_trait() == Some(trait_def_id) { - for result in G::consider_builtin_dyn_upcast_candidates(self, goal) { - candidates.push(Candidate { - source: CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting), - result, - }); + for (result, source) in G::consider_structural_builtin_unsize_candidates(self, goal) { + candidates.push(Candidate { source: CandidateSource::BuiltinImpl(source), result }); } } } @@ -544,7 +695,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ty::Alias(ty::Projection | ty::Opaque, alias_ty) => alias_ty, }; - for assumption in self.tcx().item_bounds(alias_ty.def_id).subst(self.tcx(), alias_ty.substs) + for assumption in + self.tcx().item_bounds(alias_ty.def_id).instantiate(self.tcx(), alias_ty.args) { match G::consider_alias_bound_candidate(self, goal, assumption) { Ok(result) => { @@ -584,7 +736,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.tcx(), ty::TraitPredicate { trait_ref: self_trait_ref, - constness: ty::BoundConstness::NotConst, polarity: ty::ImplPolarity::Positive, }, ); @@ -698,30 +849,53 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ty::Dynamic(bounds, ..) => bounds, }; - let own_bounds: FxIndexSet<_> = - bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)).collect(); - for assumption in elaborate(tcx, own_bounds.iter().copied()) - // we only care about bounds that match the `Self` type - .filter_only_self() - { - // FIXME: Predicates are fully elaborated in the object type's existential bounds - // list. We want to only consider these pre-elaborated projections, and not other - // projection predicates that we reach by elaborating the principal trait ref, - // since that'll cause ambiguity. - // - // We can remove this when we have implemented lifetime intersections in responses. - if assumption.as_projection_clause().is_some() && !own_bounds.contains(&assumption) { - continue; - } + // Do not consider built-in object impls for non-object-safe types. + if bounds.principal_def_id().is_some_and(|def_id| !tcx.check_is_object_safe(def_id)) { + return; + } - match G::consider_object_bound_candidate(self, goal, assumption) { - Ok(result) => candidates.push(Candidate { - source: CandidateSource::BuiltinImpl(BuiltinImplSource::Object), - result, - }), - Err(NoSolution) => (), + // Consider all of the auto-trait and projection bounds, which don't + // need to be recorded as a `BuiltinImplSource::Object` since they don't + // really have a vtable base... + for bound in bounds { + match bound.skip_binder() { + ty::ExistentialPredicate::Trait(_) => { + // Skip principal + } + ty::ExistentialPredicate::Projection(_) + | ty::ExistentialPredicate::AutoTrait(_) => { + match G::consider_object_bound_candidate( + self, + goal, + bound.with_self_ty(tcx, self_ty), + ) { + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), + result, + }), + Err(NoSolution) => (), + } + } } } + + // FIXME: We only need to do *any* of this if we're considering a trait goal, + // since we don't need to look at any supertrait or anything if we are doing + // a projection goal. + if let Some(principal) = bounds.principal() { + let principal_trait_ref = principal.with_self_ty(tcx, self_ty); + self.walk_vtable(principal_trait_ref, |ecx, assumption, vtable_base, _| { + match G::consider_object_bound_candidate(ecx, goal, assumption.to_predicate(tcx)) { + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Object { + vtable_base, + }), + result, + }), + Err(NoSolution) => (), + } + }); + } } #[instrument(level = "debug", skip_all)] @@ -730,26 +904,43 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal: Goal<'tcx, G>, candidates: &mut Vec<Candidate<'tcx>>, ) { + let tcx = self.tcx(); match self.solver_mode() { SolverMode::Normal => return, - SolverMode::Coherence => { - let trait_ref = goal.predicate.trait_ref(self.tcx()); - match coherence::trait_ref_is_knowable(self.tcx(), trait_ref) { - Ok(()) => {} - Err(_) => match self - .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) - { - Ok(result) => candidates.push(Candidate { - source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity), - result, - }), - // FIXME: This will be reachable at some point if we're in - // `assemble_candidates_after_normalizing_self_ty` and we get a - // universe error. We'll deal with it at this point. - Err(NoSolution) => bug!("coherence candidate resulted in NoSolution"), - }, + SolverMode::Coherence => {} + }; + + let result = self.probe_candidate("coherence unknowable").enter(|ecx| { + let trait_ref = goal.predicate.trait_ref(tcx); + + #[derive(Debug)] + enum FailureKind { + Overflow, + NoSolution(NoSolution), + } + let lazily_normalize_ty = |ty| match ecx.try_normalize_ty(goal.param_env, ty) { + Ok(Some(ty)) => Ok(ty), + Ok(None) => Err(FailureKind::Overflow), + Err(e) => Err(FailureKind::NoSolution(e)), + }; + + match coherence::trait_ref_is_knowable(tcx, trait_ref, lazily_normalize_ty) { + Err(FailureKind::Overflow) => { + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW) + } + Err(FailureKind::NoSolution(NoSolution)) | Ok(Ok(())) => Err(NoSolution), + Ok(Err(_)) => { + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) } } + }); + + match result { + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), + result, + }), + Err(NoSolution) => {} } } diff --git a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs index 3bb8cad15..c47767101 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs @@ -1,6 +1,9 @@ +//! Code which is used by built-in goals that match "structurally", such a auto +//! traits, `Copy`/`Clone`. use rustc_data_structures::fx::FxHashMap; use rustc_hir::{def_id::DefId, Movability, Mutability}; use rustc_infer::traits::query::NoSolution; +use rustc_middle::traits::solve::Goal; use rustc_middle::ty::{ self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, }; @@ -51,36 +54,36 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>( Ok(tys.iter().collect()) } - ty::Closure(_, ref substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]), + ty::Closure(_, ref args) => Ok(vec![args.as_closure().tupled_upvars_ty()]), - ty::Generator(_, ref substs, _) => { - let generator_substs = substs.as_generator(); - Ok(vec![generator_substs.tupled_upvars_ty(), generator_substs.witness()]) + ty::Generator(_, ref args, _) => { + let generator_args = args.as_generator(); + Ok(vec![generator_args.tupled_upvars_ty(), generator_args.witness()]) } ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), - ty::GeneratorWitnessMIR(def_id, substs) => Ok(ecx + ty::GeneratorWitnessMIR(def_id, args) => Ok(ecx .tcx() .generator_hidden_types(def_id) .map(|bty| { ecx.instantiate_binder_with_placeholders(replace_erased_lifetimes_with_bound_vars( tcx, - bty.subst(tcx, substs), + bty.instantiate(tcx, args), )) }) .collect()), // For `PhantomData<T>`, we pass `T`. - ty::Adt(def, substs) if def.is_phantom_data() => Ok(vec![substs.type_at(0)]), + ty::Adt(def, args) if def.is_phantom_data() => Ok(vec![args.type_at(0)]), - ty::Adt(def, substs) => Ok(def.all_fields().map(|f| f.ty(tcx, substs)).collect()), + ty::Adt(def, args) => Ok(def.all_fields().map(|f| f.ty(tcx, args)).collect()), - ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) => { + ty::Alias(ty::Opaque, ty::AliasTy { def_id, args, .. }) => { // We can resolve the `impl Trait` to its concrete type, // which enforces a DAG between the functions requiring // the auto trait bounds in question. - Ok(vec![tcx.type_of(def_id).subst(tcx, substs)]) + Ok(vec![tcx.type_of(def_id).instantiate(tcx, args)]) } } } @@ -146,9 +149,9 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>( ty::Tuple(tys) => Ok(tys.to_vec()), - ty::Adt(def, substs) => { + ty::Adt(def, args) => { let sized_crit = def.sized_constraint(ecx.tcx()); - Ok(sized_crit.subst_iter_copied(ecx.tcx(), substs).collect()) + Ok(sized_crit.iter_instantiated(ecx.tcx(), args).collect()) } } } @@ -158,14 +161,12 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( ty: Ty<'tcx>, ) -> Result<Vec<Ty<'tcx>>, NoSolution> { match *ty.kind() { - ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) - | ty::FnDef(..) - | ty::FnPtr(_) - | ty::Error(_) => Ok(vec![]), + ty::FnDef(..) | ty::FnPtr(_) | ty::Error(_) => Ok(vec![]), // Implementations are provided in core ty::Uint(_) | ty::Int(_) + | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) | ty::Bool | ty::Float(_) | ty::Char @@ -192,11 +193,11 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( ty::Tuple(tys) => Ok(tys.to_vec()), - ty::Closure(_, substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]), + ty::Closure(_, args) => Ok(vec![args.as_closure().tupled_upvars_ty()]), - ty::Generator(_, substs, Movability::Movable) => { + ty::Generator(_, args, Movability::Movable) => { if ecx.tcx().features().generator_clone { - let generator = substs.as_generator(); + let generator = args.as_generator(); Ok(vec![generator.tupled_upvars_ty(), generator.witness()]) } else { Err(NoSolution) @@ -205,13 +206,13 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), - ty::GeneratorWitnessMIR(def_id, substs) => Ok(ecx + ty::GeneratorWitnessMIR(def_id, args) => Ok(ecx .tcx() .generator_hidden_types(def_id) .map(|bty| { ecx.instantiate_binder_with_placeholders(replace_erased_lifetimes_with_bound_vars( ecx.tcx(), - bty.subst(ecx.tcx(), substs), + bty.instantiate(ecx.tcx(), args), )) }) .collect()), @@ -226,13 +227,13 @@ pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>( ) -> Result<Option<ty::Binder<'tcx, (Ty<'tcx>, Ty<'tcx>)>>, NoSolution> { match *self_ty.kind() { // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed. - ty::FnDef(def_id, substs) => { + ty::FnDef(def_id, args) => { 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) + sig.instantiate(tcx, args) .map_bound(|sig| (Ty::new_tup(tcx, sig.inputs()), sig.output())), )) } else { @@ -247,9 +248,9 @@ pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>( Err(NoSolution) } } - ty::Closure(_, substs) => { - let closure_substs = substs.as_closure(); - match closure_substs.kind_ty().to_opt_closure_kind() { + ty::Closure(_, args) => { + let closure_args = args.as_closure(); + match closure_args.kind_ty().to_opt_closure_kind() { // If the closure's kind doesn't extend the goal kind, // then the closure doesn't implement the trait. Some(closure_kind) => { @@ -265,7 +266,7 @@ pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>( } } } - Ok(Some(closure_substs.sig().map_bound(|sig| (sig.inputs()[0], sig.output())))) + Ok(Some(closure_args.sig().map_bound(|sig| (sig.inputs()[0], sig.output())))) } ty::Bool | ty::Char @@ -343,17 +344,18 @@ pub(in crate::solve) fn predicates_for_object_candidate<'tcx>( param_env: ty::ParamEnv<'tcx>, trait_ref: ty::TraitRef<'tcx>, object_bound: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>, -) -> Vec<ty::Clause<'tcx>> { +) -> Vec<Goal<'tcx, ty::Predicate<'tcx>>> { let tcx = ecx.tcx(); let mut requirements = vec![]; requirements.extend( - tcx.super_predicates_of(trait_ref.def_id).instantiate(tcx, trait_ref.substs).predicates, + tcx.super_predicates_of(trait_ref.def_id).instantiate(tcx, trait_ref.args).predicates, ); for item in tcx.associated_items(trait_ref.def_id).in_definition_order() { // FIXME(associated_const_equality): Also add associated consts to // the requirements here. if item.kind == ty::AssocKind::Type { - requirements.extend(tcx.item_bounds(item.def_id).subst_iter(tcx, trait_ref.substs)); + requirements + .extend(tcx.item_bounds(item.def_id).iter_instantiated(tcx, trait_ref.args)); } } @@ -373,17 +375,22 @@ pub(in crate::solve) fn predicates_for_object_candidate<'tcx>( } } - requirements.fold_with(&mut ReplaceProjectionWith { - ecx, - param_env, - mapping: replace_projection_with, - }) + let mut folder = + ReplaceProjectionWith { ecx, param_env, mapping: replace_projection_with, nested: vec![] }; + let folded_requirements = requirements.fold_with(&mut folder); + + folder + .nested + .into_iter() + .chain(folded_requirements.into_iter().map(|clause| Goal::new(tcx, param_env, clause))) + .collect() } struct ReplaceProjectionWith<'a, 'tcx> { ecx: &'a EvalCtxt<'a, 'tcx>, param_env: ty::ParamEnv<'tcx>, mapping: FxHashMap<DefId, ty::PolyProjectionPredicate<'tcx>>, + nested: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, } impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceProjectionWith<'_, 'tcx> { @@ -399,13 +406,12 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceProjectionWith<'_, 'tcx> { // but the where clauses we instantiated are not. We can solve this by instantiating // the binder at the usage site. let proj = self.ecx.instantiate_binder_with_infer(*replacement); - // FIXME: Technically this folder could be fallible? - let nested = self - .ecx - .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"); + // FIXME: Technically this equate could be fallible... + self.nested.extend( + self.ecx + .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"), + ); proj.term.ty().unwrap() } else { ty.super_fold_with(self) diff --git a/compiler/rustc_trait_selection/src/solve/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonicalize.rs index 255620489..a9d182abf 100644 --- a/compiler/rustc_trait_selection/src/solve/canonicalize.rs +++ b/compiler/rustc_trait_selection/src/solve/canonicalize.rs @@ -125,9 +125,8 @@ impl<'a, 'tcx> Canonicalizer<'a, 'tcx> { // - var_infos: [E0, U1, E1, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 6 // - var_infos: [E0, U1, E1, U1, E1, E2, U2], curr_compressed_uv: 2, next_orig_uv: - // - // This algorithm runs in `O(nm)` where `n` is the number of different universe - // indices in the input and `m` is the number of canonical variables. - // This should be fine as both `n` and `m` are expected to be small. + // This algorithm runs in `O(n²)` where `n` is the number of different universe + // indices in the input. This should be fine as `n` is expected to be small. let mut curr_compressed_uv = ty::UniverseIndex::ROOT; let mut existential_in_new_uv = false; let mut next_orig_uv = Some(ty::UniverseIndex::ROOT); @@ -208,23 +207,18 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { t } - fn fold_region(&mut self, mut r: ty::Region<'tcx>) -> ty::Region<'tcx> { - match self.canonicalize_mode { - CanonicalizeMode::Input => { - // Don't resolve infer vars in input, since it affects - // caching and may cause trait selection bugs which rely - // on regions to be equal. - } - CanonicalizeMode::Response { .. } => { - if let ty::ReVar(vid) = *r { - r = self - .infcx - .inner - .borrow_mut() - .unwrap_region_constraints() - .opportunistic_resolve_var(self.infcx.tcx, vid); - } - } + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + if let ty::ReVar(vid) = *r { + let resolved_region = self + .infcx + .inner + .borrow_mut() + .unwrap_region_constraints() + .opportunistic_resolve_var(self.infcx.tcx, vid); + assert_eq!( + r, resolved_region, + "region var should have been resolved, {r} -> {resolved_region}" + ); } let kind = match *r { @@ -263,50 +257,38 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { ty::ReError(_) => return r, }; - let var = ty::BoundVar::from( - self.variables.iter().position(|&v| v == r.into()).unwrap_or_else(|| { - let var = self.variables.len(); - self.variables.push(r.into()); - self.primitive_var_infos.push(CanonicalVarInfo { kind }); - var - }), - ); + let existing_bound_var = match self.canonicalize_mode { + CanonicalizeMode::Input => None, + CanonicalizeMode::Response { .. } => { + self.variables.iter().position(|&v| v == r.into()).map(ty::BoundVar::from) + } + }; + let var = existing_bound_var.unwrap_or_else(|| { + let var = ty::BoundVar::from(self.variables.len()); + self.variables.push(r.into()); + self.primitive_var_infos.push(CanonicalVarInfo { kind }); + var + }); let br = ty::BoundRegion { var, kind: BrAnon(None) }; ty::Region::new_late_bound(self.interner(), self.binder_index, br) } - fn fold_ty(&mut self, mut t: Ty<'tcx>) -> Ty<'tcx> { + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { let kind = match *t.kind() { - ty::Infer(ty::TyVar(mut vid)) => { - // We need to canonicalize the *root* of our ty var. - // This is so that our canonical response correctly reflects - // any equated inference vars correctly! - let root_vid = self.infcx.root_var(vid); - if root_vid != vid { - t = Ty::new_var(self.infcx.tcx, root_vid); - vid = root_vid; - } - - match self.infcx.probe_ty_var(vid) { - Ok(t) => return self.fold_ty(t), - Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)), - } + ty::Infer(ty::TyVar(vid)) => { + assert_eq!(self.infcx.root_var(vid), vid, "ty vid should have been resolved"); + let Err(ui) = self.infcx.probe_ty_var(vid) else { + bug!("ty var should have been resolved: {t}"); + }; + CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)) } ty::Infer(ty::IntVar(vid)) => { - let nt = self.infcx.opportunistic_resolve_int_var(vid); - if nt != t { - return self.fold_ty(nt); - } else { - CanonicalVarKind::Ty(CanonicalTyVarKind::Int) - } + assert_eq!(self.infcx.opportunistic_resolve_int_var(vid), t); + CanonicalVarKind::Ty(CanonicalTyVarKind::Int) } ty::Infer(ty::FloatVar(vid)) => { - let nt = self.infcx.opportunistic_resolve_float_var(vid); - if nt != t { - return self.fold_ty(nt); - } else { - CanonicalVarKind::Ty(CanonicalTyVarKind::Float) - } + assert_eq!(self.infcx.opportunistic_resolve_float_var(vid), t); + CanonicalVarKind::Ty(CanonicalTyVarKind::Float) } ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { bug!("fresh var during canonicalization: {t:?}") @@ -369,22 +351,19 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { Ty::new_bound(self.infcx.tcx, self.binder_index, bt) } - fn fold_const(&mut self, mut c: ty::Const<'tcx>) -> ty::Const<'tcx> { + fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { let kind = match c.kind() { - ty::ConstKind::Infer(ty::InferConst::Var(mut vid)) => { - // We need to canonicalize the *root* of our const var. - // This is so that our canonical response correctly reflects - // any equated inference vars correctly! - let root_vid = self.infcx.root_const_var(vid); - if root_vid != vid { - c = ty::Const::new_var(self.infcx.tcx, root_vid, c.ty()); - vid = root_vid; - } - - match self.infcx.probe_const_var(vid) { - Ok(c) => return self.fold_const(c), - Err(universe) => CanonicalVarKind::Const(universe, c.ty()), - } + ty::ConstKind::Infer(ty::InferConst::Var(vid)) => { + assert_eq!( + self.infcx.root_const_var(vid), + vid, + "const var should have been resolved" + ); + let Err(ui) = self.infcx.probe_const_var(vid) else { + bug!("const var should have been resolved"); + }; + // FIXME: we should fold this ty eventually + CanonicalVarKind::Const(ui, c.ty()) } ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => { bug!("fresh var during canonicalization: {c:?}") diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs index 74dfbdddb..5c2cbe399 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs @@ -1,20 +1,21 @@ +use rustc_data_structures::stack::ensure_sufficient_stack; use rustc_hir::def_id::{DefId, LocalDefId}; use rustc_infer::infer::at::ToTrace; use rustc_infer::infer::canonical::CanonicalVarValues; use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; use rustc_infer::infer::{ - DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, RegionVariableOrigin, - TyCtxtInferExt, + DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, TyCtxtInferExt, }; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::ObligationCause; +use rustc_middle::infer::canonical::CanonicalVarInfos; use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; use rustc_middle::traits::solve::inspect; use rustc_middle::traits::solve::{ - CanonicalInput, CanonicalResponse, Certainty, IsNormalizesToHack, MaybeCause, - PredefinedOpaques, PredefinedOpaquesData, QueryResult, + CanonicalInput, CanonicalResponse, Certainty, IsNormalizesToHack, PredefinedOpaques, + PredefinedOpaquesData, QueryResult, }; -use rustc_middle::traits::DefiningAnchor; +use rustc_middle::traits::{specialization_graph, DefiningAnchor}; use rustc_middle::ty::{ self, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor, @@ -24,10 +25,10 @@ use rustc_span::DUMMY_SP; use std::io::Write; use std::ops::ControlFlow; -use crate::traits::specialization_graph; +use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment}; use super::inspect::ProofTreeBuilder; -use super::search_graph::{self, OverflowHandler}; +use super::search_graph; use super::SolverMode; use super::{search_graph::SearchGraph, Goal}; pub use select::InferCtxtSelectExt; @@ -54,6 +55,9 @@ pub struct EvalCtxt<'a, 'tcx> { /// the job already. infcx: &'a InferCtxt<'tcx>, + /// The variable info for the `var_values`, only used to make an ambiguous response + /// with no constraints. + variables: CanonicalVarInfos<'tcx>, pub(super) var_values: CanonicalVarValues<'tcx>, predefined_opaques_in_body: PredefinedOpaques<'tcx>, @@ -116,7 +120,8 @@ impl NestedGoals<'_> { #[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)] pub enum GenerateProofTree { Yes(UseGlobalCache), - No, + IfEnabled, + Never, } #[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)] @@ -169,6 +174,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { self.search_graph.solver_mode() } + pub(super) fn local_overflow_limit(&self) -> usize { + self.search_graph.local_overflow_limit() + } + /// Creates a root evaluation context and search graph. This should only be /// used from outside of any evaluation, and other methods should be preferred /// over using this manually (such as [`InferCtxtEvalExt::evaluate_root_goal`]). @@ -182,18 +191,19 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let mut ecx = EvalCtxt { search_graph: &mut search_graph, - infcx: infcx, + infcx, + nested_goals: NestedGoals::new(), + inspect: ProofTreeBuilder::new_maybe_root(infcx.tcx, generate_proof_tree), + // Only relevant when canonicalizing the response, // which we don't do within this evaluation context. predefined_opaques_in_body: infcx .tcx .mk_predefined_opaques_in_body(PredefinedOpaquesData::default()), - // Only relevant when canonicalizing the response. max_input_universe: ty::UniverseIndex::ROOT, + variables: ty::List::empty(), var_values: CanonicalVarValues::dummy(), - nested_goals: NestedGoals::new(), tainted: Ok(()), - inspect: ProofTreeBuilder::new_maybe_root(infcx.tcx, generate_proof_tree), }; let result = f(&mut ecx); @@ -202,7 +212,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { (&tree, infcx.tcx.sess.opts.unstable_opts.dump_solver_proof_tree) { let mut lock = std::io::stdout().lock(); - let _ = lock.write_fmt(format_args!("{tree:?}")); + let _ = lock.write_fmt(format_args!("{tree:?}\n")); let _ = lock.flush(); } @@ -243,6 +253,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let mut ecx = EvalCtxt { infcx, + variables: canonical_input.variables, var_values, predefined_opaques_in_body: input.predefined_opaques_in_body, max_input_universe: canonical_input.max_universe, @@ -270,6 +281,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { // assertions against dropping an `InferCtxt` without taking opaques. // FIXME: Once we remove support for the old impl we can remove this. if input.anchor != DefiningAnchor::Error { + // This seems ok, but fragile. let _ = infcx.take_opaque_types(); } @@ -297,24 +309,26 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { // Deal with overflow, caching, and coinduction. // // The actual solver logic happens in `ecx.compute_goal`. - search_graph.with_new_goal( - tcx, - canonical_input, - goal_evaluation, - |search_graph, goal_evaluation| { - EvalCtxt::enter_canonical( - tcx, - search_graph, - canonical_input, - goal_evaluation, - |ecx, goal| { - let result = ecx.compute_goal(goal); - ecx.inspect.query_result(result); - result - }, - ) - }, - ) + ensure_sufficient_stack(|| { + search_graph.with_new_goal( + tcx, + canonical_input, + goal_evaluation, + |search_graph, goal_evaluation| { + EvalCtxt::enter_canonical( + tcx, + search_graph, + canonical_input, + goal_evaluation, + |ecx, goal| { + let result = ecx.compute_goal(goal); + ecx.inspect.query_result(result); + result + }, + ) + }, + ) + }) } /// Recursively evaluates `goal`, returning whether any inference vars have @@ -326,6 +340,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { let (orig_values, canonical_goal) = self.canonicalize_goal(goal); let mut goal_evaluation = self.inspect.new_goal_evaluation(goal, is_normalizes_to_hack); + let encountered_overflow = self.search_graph.encountered_overflow(); let canonical_response = EvalCtxt::evaluate_canonical_goal( self.tcx(), self.search_graph, @@ -341,7 +356,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { Ok(response) => response, }; - let has_changed = !canonical_response.value.var_values.is_identity() + let has_changed = !canonical_response.value.var_values.is_identity_modulo_regions() || !canonical_response.value.external_constraints.opaque_types.is_empty(); let (certainty, nested_goals) = match self.instantiate_and_apply_query_response( goal.param_env, @@ -373,37 +388,60 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { && 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 new_canonical_response = EvalCtxt::evaluate_canonical_goal( - self.tcx(), - self.search_graph, - canonical_goal, - // FIXME(-Ztrait-solver=next): we do not track what happens in `evaluate_canonical_goal` - &mut ProofTreeBuilder::new_noop(), - )?; - // We only check for modulo regions as we convert all regions in - // the input to new existentials, even if they're expected to be - // `'static` or a placeholder region. - if !new_canonical_response.value.var_values.is_identity_modulo_regions() { - bug!( - "unstable result: re-canonicalized goal={canonical_goal:#?} \ - first_response={canonical_response:#?} \ - second_response={new_canonical_response:#?}" - ); - } - if certainty != new_canonical_response.value.certainty { - bug!( - "unstable certainty: {certainty:#?} re-canonicalized goal={canonical_goal:#?} \ - first_response={canonical_response:#?} \ - second_response={new_canonical_response:#?}" - ); - } + // The nested evaluation has to happen with the original state + // of `encountered_overflow`. + let from_original_evaluation = + self.search_graph.reset_encountered_overflow(encountered_overflow); + self.check_evaluate_goal_stable_result(goal, canonical_goal, canonical_response); + // In case the evaluation was unstable, we manually make sure that this + // debug check does not influence the result of the parent goal. + self.search_graph.reset_encountered_overflow(from_original_evaluation); } Ok((has_changed, certainty, nested_goals)) } + fn check_evaluate_goal_stable_result( + &mut self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + original_input: CanonicalInput<'tcx>, + original_result: CanonicalResponse<'tcx>, + ) { + let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); + let result = EvalCtxt::evaluate_canonical_goal( + self.tcx(), + self.search_graph, + canonical_goal, + // FIXME(-Ztrait-solver=next): we do not track what happens in `evaluate_canonical_goal` + &mut ProofTreeBuilder::new_noop(), + ); + + macro_rules! fail { + ($msg:expr) => {{ + let msg = $msg; + warn!( + "unstable result: {msg}\n\ + original goal: {original_input:?},\n\ + original result: {original_result:?}\n\ + re-canonicalized goal: {canonical_goal:?}\n\ + second response: {result:?}" + ); + return; + }}; + } + + let Ok(new_canonical_response) = result else { fail!("second response was error") }; + // We only check for modulo regions as we convert all regions in + // the input to new existentials, even if they're expected to be + // `'static` or a placeholder region. + if !new_canonical_response.value.var_values.is_identity_modulo_regions() { + fail!("additional constraints from second response") + } + if original_result.value.certainty != new_canonical_response.value.certainty { + fail!("unstable certainty") + } + } + fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { let Goal { param_env, predicate } = goal; let kind = predicate.kind(); @@ -430,11 +468,8 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { 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::ClosureKind(def_id, args, kind) => self + .compute_closure_kind_goal(Goal { param_env, predicate: (def_id, args, kind) }), ty::PredicateKind::ObjectSafe(trait_def_id) => { self.compute_object_safe_goal(trait_def_id) } @@ -471,101 +506,22 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let inspect = self.inspect.new_evaluate_added_goals(); let inspect = core::mem::replace(&mut self.inspect, inspect); - 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| { - this.inspect.evaluate_added_goals_loop_start(); - - let mut has_changed = Err(Certainty::Yes); - - if let Some(goal) = goals.normalizes_to_hack_goal.take() { - // Replace the goal with an unconstrained infer var, so the - // RHS does not affect projection candidate assembly. - let unconstrained_rhs = this.next_term_infer_of_kind(goal.predicate.term); - let unconstrained_goal = goal.with( - this.tcx(), - ty::Binder::dummy(ty::ProjectionPredicate { - projection_ty: goal.predicate.projection_ty, - term: unconstrained_rhs, - }), - ); - - let (_, certainty, instantiate_goals) = - match this.evaluate_goal(IsNormalizesToHack::Yes, unconstrained_goal) { - Ok(r) => r, - Err(NoSolution) => return Some(Err(NoSolution)), - }; - new_goals.goals.extend(instantiate_goals); - - // Finally, equate the goal's RHS with the unconstrained var. - // We put the nested goals from this into goals instead of - // next_goals to avoid needing to process the loop one extra - // time if this goal returns something -- I don't think this - // matters in practice, though. - match this.eq_and_get_goals( - goal.param_env, - goal.predicate.term, - unconstrained_rhs, - ) { - Ok(eq_goals) => { - goals.goals.extend(eq_goals); - } - Err(NoSolution) => return Some(Err(NoSolution)), - }; - - // We only look at the `projection_ty` part here rather than - // looking at the "has changed" return from evaluate_goal, - // because we expect the `unconstrained_rhs` part of the predicate - // to have changed -- that means we actually normalized successfully! - if goal.predicate.projection_ty - != this.resolve_vars_if_possible(goal.predicate.projection_ty) - { - has_changed = Ok(()) - } - - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - // We need to resolve vars here so that we correctly - // deal with `has_changed` in the next iteration. - new_goals.normalizes_to_hack_goal = - Some(this.resolve_vars_if_possible(goal)); - has_changed = has_changed.map_err(|c| c.unify_with(certainty)); - } - } + let mut response = Ok(Certainty::OVERFLOW); + for _ in 0..self.local_overflow_limit() { + // FIXME: This match is a bit ugly, it might be nice to change the inspect + // stuff to use a closure instead. which should hopefully simplify this a bit. + match self.evaluate_added_goals_step() { + Ok(Some(cert)) => { + response = Ok(cert); + break; } - - for goal in goals.goals.drain(..) { - let (changed, certainty, instantiate_goals) = - match this.evaluate_goal(IsNormalizesToHack::No, goal) { - Ok(result) => result, - Err(NoSolution) => return Some(Err(NoSolution)), - }; - new_goals.goals.extend(instantiate_goals); - - if changed { - has_changed = Ok(()); - } - - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - new_goals.goals.push(goal); - has_changed = has_changed.map_err(|c| c.unify_with(certainty)); - } - } - } - - core::mem::swap(&mut new_goals, &mut goals); - match has_changed { - Ok(()) => None, - Err(certainty) => Some(Ok(certainty)), + Ok(None) => {} + Err(NoSolution) => { + response = Err(NoSolution); + break; } - }, - ); + } + } self.inspect.eval_added_goals_result(response); @@ -576,9 +532,84 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let goal_evaluations = std::mem::replace(&mut self.inspect, inspect); self.inspect.added_goals_evaluation(goal_evaluations); - self.nested_goals = goals; response } + + /// Iterate over all added goals: returning `Ok(Some(_))` in case we can stop rerunning. + /// + /// Goals for the next step get directly added the the nested goals of the `EvalCtxt`. + fn evaluate_added_goals_step(&mut self) -> Result<Option<Certainty>, NoSolution> { + let tcx = self.tcx(); + let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new()); + + self.inspect.evaluate_added_goals_loop_start(); + // If this loop did not result in any progress, what's our final certainty. + let mut unchanged_certainty = Some(Certainty::Yes); + if let Some(goal) = goals.normalizes_to_hack_goal.take() { + // Replace the goal with an unconstrained infer var, so the + // RHS does not affect projection candidate assembly. + let unconstrained_rhs = self.next_term_infer_of_kind(goal.predicate.term); + let unconstrained_goal = goal.with( + tcx, + ty::ProjectionPredicate { + projection_ty: goal.predicate.projection_ty, + term: unconstrained_rhs, + }, + ); + + let (_, certainty, instantiate_goals) = + self.evaluate_goal(IsNormalizesToHack::Yes, unconstrained_goal)?; + self.add_goals(instantiate_goals); + + // Finally, equate the goal's RHS with the unconstrained var. + // We put the nested goals from this into goals instead of + // next_goals to avoid needing to process the loop one extra + // time if this goal returns something -- I don't think this + // matters in practice, though. + let eq_goals = + self.eq_and_get_goals(goal.param_env, goal.predicate.term, unconstrained_rhs)?; + goals.goals.extend(eq_goals); + + // We only look at the `projection_ty` part here rather than + // looking at the "has changed" return from evaluate_goal, + // because we expect the `unconstrained_rhs` part of the predicate + // to have changed -- that means we actually normalized successfully! + if goal.predicate.projection_ty + != self.resolve_vars_if_possible(goal.predicate.projection_ty) + { + unchanged_certainty = None; + } + + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + // We need to resolve vars here so that we correctly + // deal with `has_changed` in the next iteration. + self.set_normalizes_to_hack_goal(self.resolve_vars_if_possible(goal)); + unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); + } + } + } + + for goal in goals.goals.drain(..) { + let (has_changed, certainty, instantiate_goals) = + self.evaluate_goal(IsNormalizesToHack::No, goal)?; + self.add_goals(instantiate_goals); + if has_changed { + unchanged_certainty = None; + } + + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + self.add_goal(goal); + unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); + } + } + } + + Ok(unchanged_certainty) + } } impl<'tcx> EvalCtxt<'_, 'tcx> { @@ -593,10 +624,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }) } - pub(super) fn next_region_infer(&self) -> ty::Region<'tcx> { - self.infcx.next_region_var(RegionVariableOrigin::MiscVariable(DUMMY_SP)) - } - pub(super) fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx> { self.infcx.next_const_var( ty, @@ -774,24 +801,18 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.infcx.resolve_vars_if_possible(value) } - pub(super) fn fresh_substs_for_item(&self, def_id: DefId) -> ty::SubstsRef<'tcx> { - self.infcx.fresh_substs_for_item(DUMMY_SP, def_id) + pub(super) fn fresh_args_for_item(&self, def_id: DefId) -> ty::GenericArgsRef<'tcx> { + self.infcx.fresh_args_for_item(DUMMY_SP, def_id) } - pub(super) fn translate_substs( + pub(super) fn translate_args( &self, param_env: ty::ParamEnv<'tcx>, source_impl: DefId, - source_substs: ty::SubstsRef<'tcx>, + source_args: ty::GenericArgsRef<'tcx>, target_node: specialization_graph::Node, - ) -> ty::SubstsRef<'tcx> { - crate::traits::translate_substs( - self.infcx, - param_env, - source_impl, - source_substs, - target_node, - ) + ) -> ty::GenericArgsRef<'tcx> { + crate::traits::translate_args(self.infcx, param_env, source_impl, source_args, target_node) } pub(super) fn register_ty_outlives(&self, ty: Ty<'tcx>, lt: ty::Region<'tcx>) { @@ -863,14 +884,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { pub(super) fn add_item_bounds_for_hidden_type( &mut self, opaque_def_id: DefId, - opaque_substs: ty::SubstsRef<'tcx>, + opaque_args: ty::GenericArgsRef<'tcx>, param_env: ty::ParamEnv<'tcx>, hidden_ty: Ty<'tcx>, ) { let mut obligations = Vec::new(); self.infcx.add_item_bounds_for_hidden_type( opaque_def_id, - opaque_substs, + opaque_args, ObligationCause::dummy(), param_env, hidden_ty, @@ -896,13 +917,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { continue; } values.extend(self.probe_candidate("opaque type storage").enter(|ecx| { - for (a, b) in std::iter::zip(candidate_key.substs, key.substs) { + for (a, b) in std::iter::zip(candidate_key.args, key.args) { ecx.eq(param_env, a, b)?; } ecx.eq(param_env, candidate_ty, ty)?; ecx.add_item_bounds_for_hidden_type( candidate_key.def_id.to_def_id(), - candidate_key.substs, + candidate_key.args, param_env, candidate_ty, ); @@ -928,4 +949,39 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { Err(ErrorHandled::TooGeneric) => None, } } + + /// Walk through the vtable of a principal trait ref, executing a `supertrait_visitor` + /// for every trait ref encountered (including the principal). Passes both the vtable + /// base and the (optional) vptr slot. + pub(super) fn walk_vtable( + &mut self, + principal: ty::PolyTraitRef<'tcx>, + mut supertrait_visitor: impl FnMut(&mut Self, ty::PolyTraitRef<'tcx>, usize, Option<usize>), + ) { + let tcx = self.tcx(); + let mut offset = 0; + prepare_vtable_segments::<()>(tcx, principal, |segment| { + match segment { + VtblSegment::MetadataDSA => { + offset += TyCtxt::COMMON_VTABLE_ENTRIES.len(); + } + VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => { + let own_vtable_entries = count_own_vtable_entries(tcx, trait_ref); + + supertrait_visitor( + self, + trait_ref, + offset, + emit_vptr.then(|| offset + own_vtable_entries), + ); + + offset += own_vtable_entries; + if emit_vptr { + offset += 1; + } + } + } + ControlFlow::Continue(()) + }); + } } diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs index 637d45888..523841951 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs @@ -1,26 +1,30 @@ -/// Canonicalization is used to separate some goal from its context, -/// throwing away unnecessary information in the process. -/// -/// This is necessary to cache goals containing inference variables -/// and placeholders without restricting them to the current `InferCtxt`. -/// -/// Canonicalization is fairly involved, for more details see the relevant -/// section of the [rustc-dev-guide][c]. -/// -/// [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html +//! Canonicalization is used to separate some goal from its context, +//! throwing away unnecessary information in the process. +//! +//! This is necessary to cache goals containing inference variables +//! and placeholders without restricting them to the current `InferCtxt`. +//! +//! Canonicalization is fairly involved, for more details see the relevant +//! section of the [rustc-dev-guide][c]. +//! +//! [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html use super::{CanonicalInput, Certainty, EvalCtxt, Goal}; use crate::solve::canonicalize::{CanonicalizeMode, Canonicalizer}; -use crate::solve::{CanonicalResponse, QueryResult, Response}; +use crate::solve::{response_no_constraints_raw, CanonicalResponse, QueryResult, Response}; use rustc_data_structures::fx::FxHashSet; use rustc_index::IndexVec; use rustc_infer::infer::canonical::query_response::make_query_region_constraints; use rustc_infer::infer::canonical::CanonicalVarValues; use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints}; +use rustc_infer::infer::InferCtxt; use rustc_middle::traits::query::NoSolution; use rustc_middle::traits::solve::{ - ExternalConstraints, ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput, + ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput, +}; +use rustc_middle::ty::{ + self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, + TypeVisitableExt, }; -use rustc_middle::ty::{self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable}; use rustc_span::DUMMY_SP; use std::iter; use std::ops::Deref; @@ -32,6 +36,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { &self, goal: Goal<'tcx, T>, ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalInput<'tcx, T>) { + let opaque_types = self.infcx.clone_opaque_types_for_query_response(); + let (goal, opaque_types) = + (goal, opaque_types).fold_with(&mut EagerResolver { infcx: self.infcx }); + let mut orig_values = Default::default(); let canonical_goal = Canonicalizer::canonicalize( self.infcx, @@ -40,11 +48,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { QueryInput { goal, anchor: self.infcx.defining_use_anchor, - predefined_opaques_in_body: self.tcx().mk_predefined_opaques_in_body( - PredefinedOpaquesData { - opaque_types: self.infcx.clone_opaque_types_for_query_response(), - }, - ), + predefined_opaques_in_body: self + .tcx() + .mk_predefined_opaques_in_body(PredefinedOpaquesData { opaque_types }), }, ); (orig_values, canonical_goal) @@ -70,34 +76,43 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ); let certainty = certainty.unify_with(goals_certainty); + if let Certainty::OVERFLOW = certainty { + // If we have overflow, it's probable that we're substituting a type + // into itself infinitely and any partial substitutions in the query + // response are probably not useful anyways, so just return an empty + // query response. + // + // This may prevent us from potentially useful inference, e.g. + // 2 candidates, one ambiguous and one overflow, which both + // have the same inference constraints. + // + // Changing this to retain some constraints in the future + // won't be a breaking change, so this is good enough for now. + return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Overflow)); + } - let response = match certainty { - Certainty::Yes | Certainty::Maybe(MaybeCause::Ambiguity) => { - let external_constraints = self.compute_external_query_constraints()?; - Response { var_values: self.var_values, external_constraints, certainty } - } - Certainty::Maybe(MaybeCause::Overflow) => { - // If we have overflow, it's probable that we're substituting a type - // into itself infinitely and any partial substitutions in the query - // response are probably not useful anyways, so just return an empty - // query response. - // - // This may prevent us from potentially useful inference, e.g. - // 2 candidates, one ambiguous and one overflow, which both - // have the same inference constraints. - // - // Changing this to retain some constraints in the future - // won't be a breaking change, so this is good enough for now. - return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Overflow)); - } - }; + let var_values = self.var_values; + let external_constraints = self.compute_external_query_constraints()?; + + let (var_values, mut external_constraints) = + (var_values, external_constraints).fold_with(&mut EagerResolver { infcx: self.infcx }); + // Remove any trivial region constraints once we've resolved regions + external_constraints + .region_constraints + .outlives + .retain(|(outlives, _)| outlives.0.as_region().map_or(true, |re| re != outlives.1)); let canonical = Canonicalizer::canonicalize( self.infcx, CanonicalizeMode::Response { max_input_universe: self.max_input_universe }, &mut Default::default(), - response, + Response { + var_values, + certainty, + external_constraints: self.tcx().mk_external_constraints(external_constraints), + }, ); + Ok(canonical) } @@ -109,34 +124,25 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { &self, maybe_cause: MaybeCause, ) -> CanonicalResponse<'tcx> { - let unconstrained_response = Response { - var_values: CanonicalVarValues { - var_values: self.tcx().mk_substs_from_iter(self.var_values.var_values.iter().map( - |arg| -> ty::GenericArg<'tcx> { - match arg.unpack() { - GenericArgKind::Lifetime(_) => self.next_region_infer().into(), - GenericArgKind::Type(_) => self.next_ty_infer().into(), - GenericArgKind::Const(ct) => self.next_const_infer(ct.ty()).into(), - } - }, - )), - }, - external_constraints: self - .tcx() - .mk_external_constraints(ExternalConstraintsData::default()), - certainty: Certainty::Maybe(maybe_cause), - }; - - Canonicalizer::canonicalize( - self.infcx, - CanonicalizeMode::Response { max_input_universe: self.max_input_universe }, - &mut Default::default(), - unconstrained_response, + response_no_constraints_raw( + self.tcx(), + self.max_input_universe, + self.variables, + Certainty::Maybe(maybe_cause), ) } + /// Computes the region constraints and *new* opaque types registered when + /// proving a goal. + /// + /// If an opaque was already constrained before proving this goal, then the + /// external constraints do not need to record that opaque, since if it is + /// further constrained by inference, that will be passed back in the var + /// values. #[instrument(level = "debug", skip(self), ret)] - fn compute_external_query_constraints(&self) -> Result<ExternalConstraints<'tcx>, NoSolution> { + fn compute_external_query_constraints( + &self, + ) -> Result<ExternalConstraintsData<'tcx>, NoSolution> { // We only check for leaks from universes which were entered inside // of the query. self.infcx.leak_check(self.max_input_universe, None).map_err(|e| { @@ -166,9 +172,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.predefined_opaques_in_body.opaque_types.iter().all(|(pa, _)| pa != a) }); - Ok(self - .tcx() - .mk_external_constraints(ExternalConstraintsData { region_constraints, opaque_types })) + Ok(ExternalConstraintsData { region_constraints, opaque_types }) } /// After calling a canonical query, we apply the constraints returned @@ -211,7 +215,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // created inside of the query directly instead of returning them to the // caller. let prev_universe = self.infcx.universe(); - let universes_created_in_query = response.max_universe.index() + 1; + let universes_created_in_query = response.max_universe.index(); for _ in 0..universes_created_in_query { self.infcx.create_next_universe(); } @@ -250,7 +254,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } - let var_values = self.tcx().mk_substs_from_iter(response.variables.iter().enumerate().map( + let var_values = self.tcx().mk_args_from_iter(response.variables.iter().enumerate().map( |(index, info)| { if info.universe() != ty::UniverseIndex::ROOT { // A variable from inside a binder of the query. While ideally these shouldn't @@ -326,3 +330,65 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { Ok(()) } } + +/// Resolves ty, region, and const vars to their inferred values or their root vars. +struct EagerResolver<'a, 'tcx> { + infcx: &'a InferCtxt<'tcx>, +} + +impl<'tcx> TypeFolder<TyCtxt<'tcx>> for EagerResolver<'_, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + match *t.kind() { + ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) { + Ok(t) => t.fold_with(self), + Err(_) => Ty::new_var(self.infcx.tcx, self.infcx.root_var(vid)), + }, + ty::Infer(ty::IntVar(vid)) => self.infcx.opportunistic_resolve_int_var(vid), + ty::Infer(ty::FloatVar(vid)) => self.infcx.opportunistic_resolve_float_var(vid), + _ => { + if t.has_infer() { + t.super_fold_with(self) + } else { + t + } + } + } + } + + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + match *r { + ty::ReVar(vid) => self + .infcx + .inner + .borrow_mut() + .unwrap_region_constraints() + .opportunistic_resolve_var(self.infcx.tcx, vid), + _ => r, + } + } + + fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { + match c.kind() { + ty::ConstKind::Infer(ty::InferConst::Var(vid)) => { + // FIXME: we need to fold the ty too, I think. + match self.infcx.probe_const_var(vid) { + Ok(c) => c.fold_with(self), + Err(_) => { + ty::Const::new_var(self.infcx.tcx, self.infcx.root_const_var(vid), c.ty()) + } + } + } + _ => { + if c.has_infer() { + c.super_fold_with(self) + } else { + c + } + } + } + } +} diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs index 4477ea7d5..317c43baf 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs @@ -17,6 +17,7 @@ where let mut nested_ecx = EvalCtxt { infcx: outer_ecx.infcx, + variables: outer_ecx.variables, var_values: outer_ecx.var_values, predefined_opaques_in_body: outer_ecx.predefined_opaques_in_body, max_input_universe: outer_ecx.max_input_universe, diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs index bf6cbef8c..42d7a587c 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs @@ -1,24 +1,21 @@ -use std::ops::ControlFlow; - +use rustc_hir as hir; use rustc_hir::def_id::DefId; -use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, InferOk}; -use rustc_infer::traits::util::supertraits; +use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt}; use rustc_infer::traits::{ - Obligation, PolyTraitObligation, PredicateObligation, Selection, SelectionResult, + Obligation, PolyTraitObligation, PredicateObligation, Selection, SelectionResult, TraitEngine, }; use rustc_middle::traits::solve::{CanonicalInput, Certainty, Goal}; use rustc_middle::traits::{ - ImplSource, ImplSourceObjectData, ImplSourceTraitUpcastingData, ImplSourceUserDefinedData, - ObligationCause, SelectionError, + BuiltinImplSource, ImplSource, ImplSourceUserDefinedData, ObligationCause, SelectionError, }; -use rustc_middle::ty::{self, TyCtxt}; +use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_span::DUMMY_SP; -use crate::solve::assembly::{BuiltinImplSource, Candidate, CandidateSource}; +use crate::solve::assembly::{Candidate, CandidateSource}; use crate::solve::eval_ctxt::{EvalCtxt, GenerateProofTree}; use crate::solve::inspect::ProofTreeBuilder; -use crate::solve::search_graph::OverflowHandler; -use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment}; +use crate::traits::StructurallyNormalizeExt; +use crate::traits::TraitEngineExt; pub trait InferCtxtSelectExt<'tcx> { fn select_in_new_trait_solver( @@ -40,7 +37,7 @@ impl<'tcx> InferCtxtSelectExt<'tcx> for InferCtxt<'tcx> { self.instantiate_binder_with_placeholders(obligation.predicate), ); - let (result, _) = EvalCtxt::enter_root(self, GenerateProofTree::No, |ecx| { + let (result, _) = EvalCtxt::enter_root(self, GenerateProofTree::Never, |ecx| { let goal = Goal::new(ecx.tcx(), trait_goal.param_env, trait_goal.predicate); let (orig_values, canonical_goal) = ecx.canonicalize_goal(goal); let mut candidates = ecx.compute_canonical_trait_candidates(canonical_goal); @@ -102,32 +99,34 @@ impl<'tcx> InferCtxtSelectExt<'tcx> for InferCtxt<'tcx> { rematch_impl(self, goal, def_id, nested_obligations) } - // Rematching the dyn upcast or object goal will instantiate the same nested - // goals that would have caused the ambiguity, so we can still make progress here - // regardless. - // FIXME: This doesn't actually check the object bounds hold here. - ( - _, - CandidateSource::BuiltinImpl( - BuiltinImplSource::Object | BuiltinImplSource::TraitUpcasting, - ), - ) => rematch_object(self, goal, nested_obligations), + // If an unsize goal is ambiguous, then we can manually rematch it to make + // selection progress for coercion during HIR typeck. If it is *not* ambiguous, + // but is `BuiltinImplSource::Misc`, it may have nested `Unsize` goals, + // and we need to rematch those to detect tuple unsizing and trait upcasting. + // FIXME: This will be wrong if we have param-env or where-clause bounds + // with the unsize goal -- we may need to mark those with different impl + // sources. + (Certainty::Maybe(_), CandidateSource::BuiltinImpl(src)) + | (Certainty::Yes, CandidateSource::BuiltinImpl(src @ BuiltinImplSource::Misc)) + if self.tcx.lang_items().unsize_trait() == Some(goal.predicate.def_id()) => + { + rematch_unsize(self, goal, nested_obligations, src, certainty) + } // Technically some builtin impls have nested obligations, but if // `Certainty::Yes`, then they should've all been verified and don't // need re-checking. - (Certainty::Yes, CandidateSource::BuiltinImpl(BuiltinImplSource::Misc)) => { - Ok(Some(ImplSource::Builtin(nested_obligations))) + (Certainty::Yes, CandidateSource::BuiltinImpl(src)) => { + Ok(Some(ImplSource::Builtin(src, nested_obligations))) } // It's fine not to do anything to rematch these, since there are no // nested obligations. (Certainty::Yes, CandidateSource::ParamEnv(_) | CandidateSource::AliasBound) => { - Ok(Some(ImplSource::Param(nested_obligations, ty::BoundConstness::NotConst))) + Ok(Some(ImplSource::Param(nested_obligations))) } - (_, CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity)) - | (Certainty::Maybe(_), _) => Ok(None), + (Certainty::Maybe(_), _) => Ok(None), } } } @@ -143,7 +142,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // the cycle anyways one step later. EvalCtxt::enter_canonical( self.tcx(), - self.search_graph(), + self.search_graph, canonical_input, // FIXME: This is wrong, idk if we even want to track stuff here. &mut ProofTreeBuilder::new_noop(), @@ -174,11 +173,12 @@ fn candidate_should_be_dropped_in_favor_of<'tcx>( } (_, CandidateSource::ParamEnv(_)) => true, + // FIXME: we could prefer earlier vtable bases perhaps... ( - CandidateSource::BuiltinImpl(BuiltinImplSource::Object), - CandidateSource::BuiltinImpl(BuiltinImplSource::Object), + CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }), + CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }), ) => false, - (_, CandidateSource::BuiltinImpl(BuiltinImplSource::Object)) => true, + (_, CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. })) => true, (CandidateSource::Impl(victim_def_id), CandidateSource::Impl(other_def_id)) => { tcx.specializes((other_def_id, victim_def_id)) @@ -195,8 +195,9 @@ fn rematch_impl<'tcx>( impl_def_id: DefId, mut nested: Vec<PredicateObligation<'tcx>>, ) -> SelectionResult<'tcx, Selection<'tcx>> { - let substs = infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id); - let impl_trait_ref = infcx.tcx.impl_trait_ref(impl_def_id).unwrap().subst(infcx.tcx, substs); + let args = infcx.fresh_args_for_item(DUMMY_SP, impl_def_id); + let impl_trait_ref = + infcx.tcx.impl_trait_ref(impl_def_id).unwrap().instantiate(infcx.tcx, args); nested.extend( infcx @@ -207,101 +208,191 @@ fn rematch_impl<'tcx>( ); nested.extend( - infcx.tcx.predicates_of(impl_def_id).instantiate(infcx.tcx, substs).into_iter().map( + infcx.tcx.predicates_of(impl_def_id).instantiate(infcx.tcx, args).into_iter().map( |(pred, _)| Obligation::new(infcx.tcx, ObligationCause::dummy(), goal.param_env, pred), ), ); - Ok(Some(ImplSource::UserDefined(ImplSourceUserDefinedData { impl_def_id, substs, nested }))) + Ok(Some(ImplSource::UserDefined(ImplSourceUserDefinedData { impl_def_id, args, nested }))) } -fn rematch_object<'tcx>( +/// The `Unsize` trait is particularly important to coercion, so we try rematch it. +/// NOTE: This must stay in sync with `consider_builtin_unsize_candidate` in trait +/// goal assembly in the solver, both for soundness and in order to avoid ICEs. +fn rematch_unsize<'tcx>( infcx: &InferCtxt<'tcx>, goal: Goal<'tcx, ty::TraitPredicate<'tcx>>, mut nested: Vec<PredicateObligation<'tcx>>, + source: BuiltinImplSource, + certainty: Certainty, ) -> SelectionResult<'tcx, Selection<'tcx>> { - let self_ty = goal.predicate.self_ty(); - let ty::Dynamic(data, _, source_kind) = *self_ty.kind() - else { - bug!() - }; - let source_trait_ref = data.principal().unwrap().with_self_ty(infcx.tcx, self_ty); - - let (is_upcasting, target_trait_ref_unnormalized) = if Some(goal.predicate.def_id()) - == infcx.tcx.lang_items().unsize_trait() - { - assert_eq!(source_kind, ty::Dyn, "cannot upcast dyn*"); - if let ty::Dynamic(data, _, ty::Dyn) = goal.predicate.trait_ref.substs.type_at(1).kind() { - (true, data.principal().unwrap().with_self_ty(infcx.tcx, self_ty)) - } else { - bug!() - } - } else { - (false, ty::Binder::dummy(goal.predicate.trait_ref)) - }; - - let mut target_trait_ref = None; - for candidate_trait_ref in supertraits(infcx.tcx, source_trait_ref) { - let result = infcx.commit_if_ok(|_| { - infcx.at(&ObligationCause::dummy(), goal.param_env).eq( - DefineOpaqueTypes::No, - target_trait_ref_unnormalized, - candidate_trait_ref, - ) - - // FIXME: We probably should at least shallowly verify these... - }); + let tcx = infcx.tcx; + let a_ty = structurally_normalize(goal.predicate.self_ty(), infcx, goal.param_env, &mut nested); + let b_ty = structurally_normalize( + goal.predicate.trait_ref.args.type_at(1), + infcx, + goal.param_env, + &mut nested, + ); - match result { - Ok(InferOk { value: (), obligations }) => { - target_trait_ref = Some(candidate_trait_ref); - nested.extend(obligations); - break; + match (a_ty.kind(), b_ty.kind()) { + // Don't try to coerce `?0` to `dyn Trait` + (ty::Infer(ty::TyVar(_)), _) | (_, ty::Infer(ty::TyVar(_))) => Ok(None), + // Stall any ambiguous upcasting goals, since we can't rematch those + (ty::Dynamic(_, _, ty::Dyn), ty::Dynamic(_, _, ty::Dyn)) => match certainty { + Certainty::Yes => Ok(Some(ImplSource::Builtin(source, nested))), + _ => Ok(None), + }, + // `T` -> `dyn Trait` upcasting + (_, &ty::Dynamic(data, region, ty::Dyn)) => { + // 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) + nested.extend(data.iter().map(|pred| { + Obligation::new( + infcx.tcx, + ObligationCause::dummy(), + goal.param_env, + pred.with_self_ty(tcx, a_ty), + ) + })); + // The type must be Sized to be unsized. + let sized_def_id = tcx.require_lang_item(hir::LangItem::Sized, None); + nested.push(Obligation::new( + infcx.tcx, + ObligationCause::dummy(), + goal.param_env, + ty::TraitRef::new(tcx, sized_def_id, [a_ty]), + )); + // The type must outlive the lifetime of the `dyn` we're unsizing into. + nested.push(Obligation::new( + infcx.tcx, + ObligationCause::dummy(), + goal.param_env, + ty::OutlivesPredicate(a_ty, region), + )); + + Ok(Some(ImplSource::Builtin(source, nested))) + } + // `[T; n]` -> `[T]` unsizing + (&ty::Array(a_elem_ty, ..), &ty::Slice(b_elem_ty)) => { + nested.extend( + infcx + .at(&ObligationCause::dummy(), goal.param_env) + .eq(DefineOpaqueTypes::No, a_elem_ty, b_elem_ty) + .expect("expected rematch to succeed") + .into_obligations(), + ); + + Ok(Some(ImplSource::Builtin(source, nested))) + } + // Struct unsizing `Struct<T>` -> `Struct<U>` where `T: Unsize<U>` + (&ty::Adt(a_def, a_args), &ty::Adt(b_def, b_args)) + if a_def.is_struct() && a_def.did() == b_def.did() => + { + let unsizing_params = tcx.unsizing_params_for_adt(a_def.did()); + // We must be unsizing some type parameters. This also implies + // that the struct has a tail field. + if unsizing_params.is_empty() { + bug!("expected rematch to succeed") } - Err(_) => continue, + + let tail_field = a_def + .non_enum_variant() + .fields + .raw + .last() + .expect("expected unsized ADT to have a tail field"); + let tail_field_ty = tcx.type_of(tail_field.did); + + let a_tail_ty = tail_field_ty.instantiate(tcx, a_args); + let b_tail_ty = tail_field_ty.instantiate(tcx, b_args); + + // Substitute just the unsizing params from B into A. The type after + // this substitution must be equal to B. This is so we don't unsize + // unrelated type parameters. + let new_a_args = tcx.mk_args_from_iter( + a_args + .iter() + .enumerate() + .map(|(i, a)| if unsizing_params.contains(i as u32) { b_args[i] } else { a }), + ); + let unsized_a_ty = Ty::new_adt(tcx, a_def, new_a_args); + + nested.extend( + infcx + .at(&ObligationCause::dummy(), goal.param_env) + .eq(DefineOpaqueTypes::No, unsized_a_ty, b_ty) + .expect("expected rematch to succeed") + .into_obligations(), + ); + + // Finally, we require that `TailA: Unsize<TailB>` for the tail field + // types. + nested.push(Obligation::new( + tcx, + ObligationCause::dummy(), + goal.param_env, + ty::TraitRef::new(tcx, goal.predicate.def_id(), [a_tail_ty, b_tail_ty]), + )); + + Ok(Some(ImplSource::Builtin(source, nested))) + } + // Tuple unsizing `(.., T)` -> `(.., U)` where `T: Unsize<U>` + (&ty::Tuple(a_tys), &ty::Tuple(b_tys)) + if a_tys.len() == b_tys.len() && !a_tys.is_empty() => + { + let (a_last_ty, a_rest_tys) = a_tys.split_last().unwrap(); + let b_last_ty = b_tys.last().unwrap(); + + // Substitute just the tail field of B., and require that they're equal. + let unsized_a_ty = + Ty::new_tup_from_iter(tcx, a_rest_tys.iter().chain([b_last_ty]).copied()); + nested.extend( + infcx + .at(&ObligationCause::dummy(), goal.param_env) + .eq(DefineOpaqueTypes::No, unsized_a_ty, b_ty) + .expect("expected rematch to succeed") + .into_obligations(), + ); + + // Similar to ADTs, require that we can unsize the tail. + nested.push(Obligation::new( + tcx, + ObligationCause::dummy(), + goal.param_env, + ty::TraitRef::new(tcx, goal.predicate.def_id(), [*a_last_ty, *b_last_ty]), + )); + + // We need to be able to detect tuple unsizing to require its feature gate. + assert_eq!( + source, + BuiltinImplSource::TupleUnsizing, + "compiler-errors wants to know if this can ever be triggered..." + ); + Ok(Some(ImplSource::Builtin(source, nested))) + } + _ => { + assert_ne!(certainty, Certainty::Yes); + Ok(None) } } +} - let target_trait_ref = target_trait_ref.unwrap(); - - let mut offset = 0; - let Some((vtable_base, vtable_vptr_slot)) = - prepare_vtable_segments(infcx.tcx, source_trait_ref, |segment| { - match segment { - VtblSegment::MetadataDSA => { - offset += TyCtxt::COMMON_VTABLE_ENTRIES.len(); - } - VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => { - let own_vtable_entries = count_own_vtable_entries(infcx.tcx, trait_ref); - - if trait_ref == target_trait_ref { - if emit_vptr { - return ControlFlow::Break(( - offset, - Some(offset + count_own_vtable_entries(infcx.tcx, trait_ref)), - )); - } else { - return ControlFlow::Break((offset, None)); - } - } - - offset += own_vtable_entries; - if emit_vptr { - offset += 1; - } - } - } - ControlFlow::Continue(()) - }) - else { - bug!(); - }; - - // If we're upcasting, get the offset of the vtable pointer, otherwise get - // the base of the vtable. - Ok(Some(if is_upcasting { - ImplSource::TraitUpcasting(ImplSourceTraitUpcastingData { vtable_vptr_slot, nested }) +fn structurally_normalize<'tcx>( + ty: Ty<'tcx>, + infcx: &InferCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + nested: &mut Vec<PredicateObligation<'tcx>>, +) -> Ty<'tcx> { + if matches!(ty.kind(), ty::Alias(..)) { + let mut engine = <dyn TraitEngine<'tcx>>::new(infcx); + let normalized_ty = infcx + .at(&ObligationCause::dummy(), param_env) + .structurally_normalize(ty, &mut *engine) + .expect("normalization shouldn't fail if we got to here"); + nested.extend(engine.pending_obligations()); + normalized_ty } else { - ImplSource::Object(ImplSourceObjectData { vtable_base, nested }) - })) + ty + } } diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs index 88ee14c4d..f1d309122 100644 --- a/compiler/rustc_trait_selection/src/solve/fulfill.rs +++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs @@ -57,7 +57,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { .map(|obligation| { let code = infcx.probe(|_| { match infcx - .evaluate_root_goal(obligation.clone().into(), GenerateProofTree::No) + .evaluate_root_goal(obligation.clone().into(), GenerateProofTree::IfEnabled) .0 { Ok((_, Certainty::Maybe(MaybeCause::Ambiguity), _)) => { @@ -96,7 +96,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { for obligation in mem::take(&mut self.obligations) { let goal = obligation.clone().into(); let (changed, certainty, nested_goals) = - match infcx.evaluate_root_goal(goal, GenerateProofTree::No).0 { + match infcx.evaluate_root_goal(goal, GenerateProofTree::IfEnabled).0 { Ok(result) => result, Err(NoSolution) => { errors.push(FulfillmentError { diff --git a/compiler/rustc_trait_selection/src/solve/inherent_projection.rs b/compiler/rustc_trait_selection/src/solve/inherent_projection.rs new file mode 100644 index 000000000..28fe59b7f --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/inherent_projection.rs @@ -0,0 +1,50 @@ +//! Computes a normalizes-to (projection) goal for inherent associated types, +//! `#![feature(inherent_associated_type)]`. Since astconv already determines +//! which impl the IAT is being projected from, we just: +//! 1. instantiate substs, +//! 2. equate the self type, and +//! 3. instantiate and register where clauses. +use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; +use rustc_middle::ty; + +use super::EvalCtxt; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + pub(super) fn normalize_inherent_associated_type( + &mut self, + goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + let tcx = self.tcx(); + let inherent = goal.predicate.projection_ty; + let expected = goal.predicate.term.ty().expect("inherent consts are treated separately"); + + let impl_def_id = tcx.parent(inherent.def_id); + let impl_substs = self.fresh_args_for_item(impl_def_id); + + // Equate impl header and add impl where clauses + self.eq( + goal.param_env, + inherent.self_ty(), + tcx.type_of(impl_def_id).instantiate(tcx, impl_substs), + )?; + + // Equate IAT with the RHS of the project goal + let inherent_substs = inherent.rebase_inherent_args_onto_impl(impl_substs, tcx); + self.eq( + goal.param_env, + expected, + tcx.type_of(inherent.def_id).instantiate(tcx, inherent_substs), + ) + .expect("expected goal term to be fully unconstrained"); + + // Check both where clauses on the impl and IAT + self.add_goals( + tcx.predicates_of(inherent.def_id) + .instantiate(tcx, inherent_substs) + .into_iter() + .map(|(pred, _)| goal.with(tcx, pred)), + ); + + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/inspect.rs b/compiler/rustc_trait_selection/src/solve/inspect.rs index 2d6717fda..cda683963 100644 --- a/compiler/rustc_trait_selection/src/solve/inspect.rs +++ b/compiler/rustc_trait_selection/src/solve/inspect.rs @@ -200,30 +200,23 @@ impl<'tcx> ProofTreeBuilder<'tcx> { tcx: TyCtxt<'tcx>, generate_proof_tree: GenerateProofTree, ) -> ProofTreeBuilder<'tcx> { - let generate_proof_tree = match ( - tcx.sess.opts.unstable_opts.dump_solver_proof_tree, - tcx.sess.opts.unstable_opts.dump_solver_proof_tree_use_cache, - generate_proof_tree, - ) { - (_, Some(use_cache), GenerateProofTree::Yes(_)) => { - GenerateProofTree::Yes(UseGlobalCache::from_bool(use_cache)) - } - - (DumpSolverProofTree::Always, use_cache, GenerateProofTree::No) => { - let use_cache = use_cache.unwrap_or(true); - GenerateProofTree::Yes(UseGlobalCache::from_bool(use_cache)) - } - - (_, None, GenerateProofTree::Yes(_)) => generate_proof_tree, - (DumpSolverProofTree::Never, _, _) => generate_proof_tree, - (DumpSolverProofTree::OnError, _, _) => generate_proof_tree, - }; - match generate_proof_tree { - GenerateProofTree::No => ProofTreeBuilder::new_noop(), - GenerateProofTree::Yes(global_cache_disabled) => { - ProofTreeBuilder::new_root(global_cache_disabled) + GenerateProofTree::Never => ProofTreeBuilder::new_noop(), + GenerateProofTree::IfEnabled => { + let opts = &tcx.sess.opts.unstable_opts; + match opts.dump_solver_proof_tree { + DumpSolverProofTree::Always => { + let use_cache = opts.dump_solver_proof_tree_use_cache.unwrap_or(true); + ProofTreeBuilder::new_root(UseGlobalCache::from_bool(use_cache)) + } + // `OnError` is handled by reevaluating goals in error + // reporting with `GenerateProofTree::Yes`. + DumpSolverProofTree::OnError | DumpSolverProofTree::Never => { + ProofTreeBuilder::new_noop() + } + } } + GenerateProofTree::Yes(use_cache) => ProofTreeBuilder::new_root(use_cache), } } diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 77809d8d2..75a99f799 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -1,21 +1,27 @@ -//! The new trait solver, currently still WIP. +//! The next-generation trait solver, currently still WIP. //! -//! As a user of the trait system, you can use `TyCtxt::evaluate_goal` to -//! interact with this solver. +//! As a user of rust, you can use `-Ztrait-solver=next` or `next-coherence` +//! to enable the new trait solver always, or just within coherence, respectively. +//! +//! As a developer of rustc, you shouldn't be using the new trait +//! solver without asking the trait-system-refactor-initiative, but it can +//! be enabled with `InferCtxtBuilder::with_next_trait_solver`. This will +//! ensure that trait solving using that inference context will be routed +//! to the new trait solver. //! //! For a high-level overview of how this solver works, check out the relevant //! section of the rustc-dev-guide. //! //! FIXME(@lcnr): Write that section. If you read this before then ask me //! about it on zulip. - use rustc_hir::def_id::DefId; use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues}; use rustc_infer::traits::query::NoSolution; +use rustc_middle::infer::canonical::CanonicalVarInfos; use rustc_middle::traits::solve::{ CanonicalResponse, Certainty, ExternalConstraintsData, Goal, QueryResult, Response, }; -use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_middle::ty::{self, Ty, TyCtxt, UniverseIndex}; use rustc_middle::ty::{ CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate, }; @@ -25,6 +31,7 @@ mod assembly; mod canonicalize; mod eval_ctxt; mod fulfill; +mod inherent_projection; pub mod inspect; mod normalize; mod opaques; @@ -37,7 +44,7 @@ pub use eval_ctxt::{ EvalCtxt, GenerateProofTree, InferCtxtEvalExt, InferCtxtSelectExt, UseGlobalCache, }; pub use fulfill::FulfillmentCtxt; -pub(crate) use normalize::deeply_normalize; +pub(crate) use normalize::{deeply_normalize, deeply_normalize_with_skipped_universes}; #[derive(Debug, Clone, Copy)] enum SolverMode { @@ -123,10 +130,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { #[instrument(level = "debug", skip(self))] fn compute_closure_kind_goal( &mut self, - goal: Goal<'tcx, (DefId, ty::SubstsRef<'tcx>, ty::ClosureKind)>, + goal: Goal<'tcx, (DefId, ty::GenericArgsRef<'tcx>, ty::ClosureKind)>, ) -> QueryResult<'tcx> { - let (_, substs, expected_kind) = goal.predicate; - let found_kind = substs.as_closure().kind_ty().to_opt_closure_kind(); + let (_, args, expected_kind) = goal.predicate; + let found_kind = args.as_closure().kind_ty().to_opt_closure_kind(); let Some(found_kind) = found_kind else { return self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); @@ -266,33 +273,64 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { return Err(NoSolution); } - let Certainty::Maybe(maybe_cause) = responses.iter().fold( - Certainty::AMBIGUOUS, - |certainty, response| { + let Certainty::Maybe(maybe_cause) = + responses.iter().fold(Certainty::AMBIGUOUS, |certainty, response| { certainty.unify_with(response.value.certainty) - }, - ) else { + }) + else { bug!("expected flounder response to be ambiguous") }; Ok(self.make_ambiguous_response_no_constraints(maybe_cause)) } + + /// Normalize a type when it is structually matched on. + /// + /// For self types this is generally already handled through + /// `assemble_candidates_after_normalizing_self_ty`, so anything happening + /// in [`EvalCtxt::assemble_candidates_via_self_ty`] does not have to normalize + /// the self type. It is required when structurally matching on any other + /// arguments of a trait goal, e.g. when assembling builtin unsize candidates. + fn try_normalize_ty( + &mut self, + param_env: ty::ParamEnv<'tcx>, + mut ty: Ty<'tcx>, + ) -> Result<Option<Ty<'tcx>>, NoSolution> { + for _ in 0..self.local_overflow_limit() { + let ty::Alias(_, projection_ty) = *ty.kind() else { + return Ok(Some(ty)); + }; + + let normalized_ty = self.next_ty_infer(); + let normalizes_to_goal = Goal::new( + self.tcx(), + param_env, + ty::ProjectionPredicate { projection_ty, term: normalized_ty.into() }, + ); + self.add_goal(normalizes_to_goal); + self.try_evaluate_added_goals()?; + ty = self.resolve_vars_if_possible(normalized_ty); + } + + Ok(None) + } } -pub(super) fn response_no_constraints<'tcx>( +fn response_no_constraints_raw<'tcx>( tcx: TyCtxt<'tcx>, - goal: Canonical<'tcx, impl Sized>, + max_universe: UniverseIndex, + variables: CanonicalVarInfos<'tcx>, certainty: Certainty, -) -> QueryResult<'tcx> { - Ok(Canonical { - max_universe: goal.max_universe, - variables: goal.variables, +) -> CanonicalResponse<'tcx> { + Canonical { + max_universe, + variables, value: Response { - var_values: CanonicalVarValues::make_identity(tcx, goal.variables), + var_values: CanonicalVarValues::make_identity(tcx, variables), // FIXME: maybe we should store the "no response" version in tcx, like // we do for tcx.types and stuff. external_constraints: tcx.mk_external_constraints(ExternalConstraintsData::default()), certainty, }, - }) + } } diff --git a/compiler/rustc_trait_selection/src/solve/normalize.rs b/compiler/rustc_trait_selection/src/solve/normalize.rs index c388850d8..872f0c879 100644 --- a/compiler/rustc_trait_selection/src/solve/normalize.rs +++ b/compiler/rustc_trait_selection/src/solve/normalize.rs @@ -20,8 +20,23 @@ pub(crate) fn deeply_normalize<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>( at: At<'_, 'tcx>, value: T, ) -> Result<T, Vec<FulfillmentError<'tcx>>> { + assert!(!value.has_escaping_bound_vars()); + deeply_normalize_with_skipped_universes(at, value, vec![]) +} + +/// Deeply normalize all aliases in `value`. This does not handle inference and expects +/// its input to be already fully resolved. +/// +/// Additionally takes a list of universes which represents the binders which have been +/// entered before passing `value` to the function. This is currently needed for +/// `normalize_erasing_regions`, which skips binders as it walks through a type. +pub(crate) fn deeply_normalize_with_skipped_universes<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>( + at: At<'_, 'tcx>, + value: T, + universes: Vec<Option<UniverseIndex>>, +) -> Result<T, Vec<FulfillmentError<'tcx>>> { let fulfill_cx = FulfillmentCtxt::new(at.infcx); - let mut folder = NormalizationFolder { at, fulfill_cx, depth: 0, universes: Vec::new() }; + let mut folder = NormalizationFolder { at, fulfill_cx, depth: 0, universes }; value.try_fold_with(&mut folder) } @@ -60,10 +75,7 @@ impl<'tcx> NormalizationFolder<'_, 'tcx> { tcx, self.at.cause.clone(), self.at.param_env, - ty::Binder::dummy(ty::ProjectionPredicate { - projection_ty: alias, - term: new_infer_ty.into(), - }), + ty::ProjectionPredicate { projection_ty: alias, term: new_infer_ty.into() }, ); // Do not emit an error if normalization is known to fail but instead @@ -116,10 +128,10 @@ impl<'tcx> NormalizationFolder<'_, 'tcx> { tcx, self.at.cause.clone(), self.at.param_env, - ty::Binder::dummy(ty::ProjectionPredicate { - projection_ty: tcx.mk_alias_ty(uv.def, uv.substs), + ty::ProjectionPredicate { + projection_ty: tcx.mk_alias_ty(uv.def, uv.args), term: new_infer_ct.into(), - }), + }, ); let result = if infcx.predicate_may_hold(&obligation) { @@ -180,7 +192,7 @@ impl<'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for NormalizationFolder<'_, 'tcx> { mapped_regions, mapped_types, mapped_consts, - &mut self.universes, + &self.universes, result, )) } else { @@ -210,7 +222,7 @@ impl<'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for NormalizationFolder<'_, 'tcx> { mapped_regions, mapped_types, mapped_consts, - &mut self.universes, + &self.universes, result, )) } else { diff --git a/compiler/rustc_trait_selection/src/solve/opaques.rs b/compiler/rustc_trait_selection/src/solve/opaques.rs index 16194f5ad..f08adc020 100644 --- a/compiler/rustc_trait_selection/src/solve/opaques.rs +++ b/compiler/rustc_trait_selection/src/solve/opaques.rs @@ -1,3 +1,6 @@ +//! Computes a normalizes-to (projection) goal for opaque types. This goal +//! behaves differently depending on the param-env's reveal mode and whether +//! the opaque is in a defining scope. use rustc_middle::traits::query::NoSolution; use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; use rustc_middle::traits::Reveal; @@ -26,8 +29,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if !self.can_define_opaque_ty(opaque_ty_def_id) { return Err(NoSolution); } - // FIXME: This may have issues when the substs contain aliases... - match self.tcx().uses_unique_placeholders_ignoring_regions(opaque_ty.substs) { + // FIXME: This may have issues when the args contain aliases... + match self.tcx().uses_unique_placeholders_ignoring_regions(opaque_ty.args) { Err(NotUniqueParam::NotParam(param)) if param.is_non_region_infer() => { return self.evaluate_added_goals_and_make_canonical_response( Certainty::AMBIGUOUS, @@ -40,7 +43,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } // Prefer opaques registered already. let opaque_type_key = - ty::OpaqueTypeKey { def_id: opaque_ty_def_id, substs: opaque_ty.substs }; + ty::OpaqueTypeKey { def_id: opaque_ty_def_id, args: opaque_ty.args }; let matches = self.unify_existing_opaque_tys(goal.param_env, opaque_type_key, expected); if !matches.is_empty() { @@ -54,7 +57,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.insert_hidden_type(opaque_type_key, goal.param_env, expected)?; self.add_item_bounds_for_hidden_type( opaque_ty.def_id, - opaque_ty.substs, + opaque_ty.args, goal.param_env, expected, ); @@ -65,7 +68,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // e.g. assigning `impl Copy := NotCopy` self.add_item_bounds_for_hidden_type( opaque_ty.def_id, - opaque_ty.substs, + opaque_ty.args, goal.param_env, expected, ); @@ -73,7 +76,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } (Reveal::All, _) => { // FIXME: Add an assertion that opaque type storage is empty. - let actual = tcx.type_of(opaque_ty.def_id).subst(tcx, opaque_ty.substs); + let actual = tcx.type_of(opaque_ty.def_id).instantiate(tcx, opaque_ty.args); self.eq(goal.param_env, expected, actual)?; self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs index e53b784a7..e47e22877 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -1,8 +1,7 @@ -use crate::traits::specialization_graph; +use crate::traits::{check_args_compatible, specialization_graph}; use super::assembly::{self, structural_traits}; use super::EvalCtxt; -use rustc_errors::ErrorGuaranteed; use rustc_hir::def::DefKind; use rustc_hir::def_id::DefId; use rustc_hir::LangItem; @@ -11,11 +10,12 @@ use rustc_infer::traits::specialization_graph::LeafDef; use rustc_infer::traits::Reveal; use rustc_middle::traits::solve::inspect::CandidateKind; use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; +use rustc_middle::traits::BuiltinImplSource; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; use rustc_middle::ty::ProjectionPredicate; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_middle::ty::{ToPredicate, TypeVisitableExt}; -use rustc_span::{sym, DUMMY_SP}; +use rustc_span::{sym, ErrorGuaranteed, DUMMY_SP}; impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self), ret)] @@ -48,7 +48,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.merge_candidates(candidates) } ty::AssocItemContainer::ImplContainer => { - bug!("IATs not supported here yet") + self.normalize_inherent_associated_type(goal) } } } else { @@ -58,7 +58,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } DefKind::AnonConst => self.normalize_anon_const(goal), DefKind::OpaqueTy => self.normalize_opaque_type(goal), - DefKind::TyAlias => self.normalize_weak_type(goal), + DefKind::TyAlias { .. } => self.normalize_weak_type(goal), kind => bug!("unknown DefKind {} in projection goal: {goal:#?}", kind.descr(def_id)), } } @@ -72,7 +72,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal.param_env, ty::UnevaluatedConst::new( goal.predicate.projection_ty.def_id, - goal.predicate.projection_ty.substs, + goal.predicate.projection_ty.args, ), self.tcx() .type_of(goal.predicate.projection_ty.def_id) @@ -112,6 +112,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ) -> QueryResult<'tcx> { if let Some(projection_pred) = assumption.as_projection_clause() { if projection_pred.projection_def_id() == goal.predicate.def_id() { + let tcx = ecx.tcx(); ecx.probe_candidate("assumption").enter(|ecx| { let assumption_projection_pred = ecx.instantiate_binder_with_infer(projection_pred); @@ -122,6 +123,14 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { )?; ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term) .expect("expected goal term to be fully unconstrained"); + + // Add GAT where clauses from the trait's definition + ecx.add_goals( + tcx.predicates_of(goal.predicate.def_id()) + .instantiate_own(tcx, goal.predicate.projection_ty.args) + .map(|(pred, _)| goal.with(tcx, pred)), + ); + then(ecx) }) } else { @@ -142,93 +151,116 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx); let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; - if !drcx.substs_refs_may_unify(goal_trait_ref.substs, impl_trait_ref.skip_binder().substs) { + if !drcx.args_refs_may_unify(goal_trait_ref.args, impl_trait_ref.skip_binder().args) { return Err(NoSolution); } - ecx.probe( - |r| CandidateKind::Candidate { name: "impl".into(), result: *r }).enter( - |ecx| { - let impl_substs = ecx.fresh_substs_for_item(impl_def_id); - let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); - - 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)); - 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 - // unsoundness during coherence (#105782). - let Some(assoc_def) = fetch_eligible_assoc_item_def( - ecx, - goal.param_env, - goal_trait_ref, - goal.predicate.def_id(), - impl_def_id - )? else { - return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + ecx.probe(|r| CandidateKind::Candidate { name: "impl".into(), result: *r }).enter(|ecx| { + let impl_args = ecx.fresh_args_for_item(impl_def_id); + let impl_trait_ref = impl_trait_ref.instantiate(tcx, impl_args); + + ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; + + let where_clause_bounds = tcx + .predicates_of(impl_def_id) + .instantiate(tcx, impl_args) + .predicates + .into_iter() + .map(|pred| goal.with(tcx, pred)); + ecx.add_goals(where_clause_bounds); + + // Add GAT where clauses from the trait's definition + ecx.add_goals( + tcx.predicates_of(goal.predicate.def_id()) + .instantiate_own(tcx, goal.predicate.projection_ty.args) + .map(|(pred, _)| goal.with(tcx, pred)), + ); + + // In case the associated item is hidden due to specialization, we have to + // return ambiguity this would otherwise be incomplete, resulting in + // unsoundness during coherence (#105782). + let Some(assoc_def) = fetch_eligible_assoc_item_def( + ecx, + goal.param_env, + goal_trait_ref, + goal.predicate.def_id(), + impl_def_id, + )? + else { + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + }; + + let error_response = |ecx: &mut EvalCtxt<'_, 'tcx>, reason| { + let guar = tcx.sess.delay_span_bug(tcx.def_span(assoc_def.item.def_id), reason); + let error_term = match assoc_def.item.kind { + ty::AssocKind::Const => ty::Const::new_error( + tcx, + guar, + tcx.type_of(goal.predicate.def_id()) + .instantiate(tcx, goal.predicate.projection_ty.args), + ) + .into(), + ty::AssocKind::Type => Ty::new_error(tcx, guar).into(), + ty::AssocKind::Fn => unreachable!(), }; + ecx.eq(goal.param_env, goal.predicate.term, error_term) + .expect("expected goal term to be fully unconstrained"); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }; - if !assoc_def.item.defaultness(tcx).has_value() { - let guar = tcx.sess.delay_span_bug( - tcx.def_span(assoc_def.item.def_id), - "missing value for assoc item in impl", - ); - let error_term = match assoc_def.item.kind { - ty::AssocKind::Const => ty::Const::new_error(tcx, - guar, - tcx.type_of(goal.predicate.def_id()) - .subst(tcx, goal.predicate.projection_ty.substs), - ) - .into(), - ty::AssocKind::Type => Ty::new_error(tcx,guar).into(), - ty::AssocKind::Fn => unreachable!(), - }; - ecx.eq(goal.param_env, goal.predicate.term, error_term) - .expect("expected goal term to be fully unconstrained"); - return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes); - } + if !assoc_def.item.defaultness(tcx).has_value() { + return error_response(ecx, "missing value for assoc item in impl"); + } - // Getting the right substitutions here is complex, e.g. given: - // - a goal `<Vec<u32> as Trait<i32>>::Assoc<u64>` - // - the applicable impl `impl<T> Trait<i32> for Vec<T>` - // - and the impl which defines `Assoc` being `impl<T, U> Trait<U> for Vec<T>` - // - // We first rebase the goal substs onto the impl, going from `[Vec<u32>, i32, u64]` - // to `[u32, u64]`. - // - // And then map these substs to the substs of the defining impl of `Assoc`, going - // from `[u32, u64]` to `[u32, i32, u64]`. - let impl_substs_with_gat = goal.predicate.projection_ty.substs.rebase_onto( - tcx, - goal_trait_ref.def_id, - impl_substs, - ); - let substs = ecx.translate_substs( - goal.param_env, - impl_def_id, - impl_substs_with_gat, - assoc_def.defining_node, + // Getting the right args here is complex, e.g. given: + // - a goal `<Vec<u32> as Trait<i32>>::Assoc<u64>` + // - the applicable impl `impl<T> Trait<i32> for Vec<T>` + // - and the impl which defines `Assoc` being `impl<T, U> Trait<U> for Vec<T>` + // + // We first rebase the goal args onto the impl, going from `[Vec<u32>, i32, u64]` + // to `[u32, u64]`. + // + // And then map these args to the args of the defining impl of `Assoc`, going + // from `[u32, u64]` to `[u32, i32, u64]`. + let impl_args_with_gat = goal.predicate.projection_ty.args.rebase_onto( + tcx, + goal_trait_ref.def_id, + impl_args, + ); + let args = ecx.translate_args( + goal.param_env, + impl_def_id, + impl_args_with_gat, + assoc_def.defining_node, + ); + + if !check_args_compatible(tcx, assoc_def.item, args) { + return error_response( + ecx, + "associated item has mismatched generic item arguments", ); + } - // Finally we construct the actual value of the associated type. - let term = match assoc_def.item.kind { - ty::AssocKind::Type => tcx.type_of(assoc_def.item.def_id).map_bound(|ty| ty.into()), - ty::AssocKind::Const => bug!("associated const projection is not supported yet"), - ty::AssocKind::Fn => unreachable!("we should never project to a fn"), - }; + // Finally we construct the actual value of the associated type. + let term = match assoc_def.item.kind { + ty::AssocKind::Type => tcx.type_of(assoc_def.item.def_id).map_bound(|ty| ty.into()), + ty::AssocKind::Const => bug!("associated const projection is not supported yet"), + ty::AssocKind::Fn => unreachable!("we should never project to a fn"), + }; - ecx.eq(goal.param_env, goal.predicate.term, term.subst(tcx, substs)) - .expect("expected goal term to be fully unconstrained"); - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - }, - ) + ecx.eq(goal.param_env, goal.predicate.term, term.instantiate(tcx, args)) + .expect("expected goal term to be fully unconstrained"); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + } + + /// Fail to normalize if the predicate contains an error, alternatively, we could normalize to `ty::Error` + /// and succeed. Can experiment with this to figure out what results in better error messages. + fn consider_error_guaranteed_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + _guar: ErrorGuaranteed, + ) -> QueryResult<'tcx> { + Err(NoSolution) } fn consider_auto_trait_candidate( @@ -350,7 +382,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ty::Dynamic(_, _, _) => { let dyn_metadata = tcx.require_lang_item(LangItem::DynMetadata, None); tcx.type_of(dyn_metadata) - .subst(tcx, &[ty::GenericArg::from(goal.predicate.self_ty())]) + .instantiate(tcx, &[ty::GenericArg::from(goal.predicate.self_ty())]) } ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => { @@ -365,29 +397,21 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { tcx.types.unit } - ty::Adt(def, substs) if def.is_struct() => { - match def.non_enum_variant().tail_opt() { - None => tcx.types.unit, - Some(field_def) => { - let self_ty = field_def.ty(tcx, substs); - ecx.add_goal(goal.with( - tcx, - ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)), - )); - return ecx - .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); - } + ty::Adt(def, args) if def.is_struct() => match def.non_enum_variant().tail_opt() { + None => tcx.types.unit, + Some(field_def) => { + let self_ty = field_def.ty(tcx, args); + ecx.add_goal(goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty))); + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } - } + }, ty::Adt(_, _) => tcx.types.unit, ty::Tuple(elements) => match elements.last() { None => tcx.types.unit, Some(&self_ty) => { - ecx.add_goal(goal.with( - tcx, - ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)), - )); + ecx.add_goal(goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty))); return ecx .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } @@ -413,7 +437,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { let self_ty = goal.predicate.self_ty(); - let ty::Generator(def_id, substs, _) = *self_ty.kind() else { + let ty::Generator(def_id, args, _) = *self_ty.kind() else { return Err(NoSolution); }; @@ -423,15 +447,15 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { return Err(NoSolution); } - let term = substs.as_generator().return_ty().into(); + let term = args.as_generator().return_ty().into(); Self::consider_implied_clause( ecx, goal, - ty::Binder::dummy(ty::ProjectionPredicate { + ty::ProjectionPredicate { projection_ty: ecx.tcx().mk_alias_ty(goal.predicate.def_id(), [self_ty]), term, - }) + } .to_predicate(tcx), // Technically, we need to check that the future type is Sized, // but that's already proven by the generator being WF. @@ -444,7 +468,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { let self_ty = goal.predicate.self_ty(); - let ty::Generator(def_id, substs, _) = *self_ty.kind() else { + let ty::Generator(def_id, args, _) = *self_ty.kind() else { return Err(NoSolution); }; @@ -454,7 +478,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { return Err(NoSolution); } - let generator = substs.as_generator(); + let generator = args.as_generator(); let name = tcx.associated_item(goal.predicate.def_id()).name; let term = if name == sym::Return { @@ -468,12 +492,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { Self::consider_implied_clause( ecx, goal, - ty::Binder::dummy(ty::ProjectionPredicate { + ty::ProjectionPredicate { projection_ty: ecx .tcx() .mk_alias_ty(goal.predicate.def_id(), [self_ty, generator.resume_ty()]), term, - }) + } .to_predicate(tcx), // Technically, we need to check that the future type is Sized, // but that's already proven by the generator being WF. @@ -481,17 +505,17 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ) } - fn consider_builtin_unsize_candidate( + fn consider_unsize_to_dyn_candidate( _ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { - bug!("`Unsize` does not have an associated type: {:?}", goal); + bug!("`Unsize` does not have an associated type: {:?}", goal) } - fn consider_builtin_dyn_upcast_candidates( + fn consider_structural_builtin_unsize_candidates( _ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - ) -> Vec<CanonicalResponse<'tcx>> { + ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)> { bug!("`Unsize` does not have an associated type: {:?}", goal); } diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs index 56f126e91..be48447e2 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs @@ -19,21 +19,25 @@ rustc_index::newtype_index! { #[derive(Debug, Clone)] pub(super) struct ProvisionalEntry<'tcx> { - // In case we have a coinductive cycle, this is the - // the currently least restrictive result of this goal. - pub(super) response: QueryResult<'tcx>, - // In case of a cycle, the position of deepest stack entry involved - // in that cycle. This is monotonically decreasing in the stack as all - // elements between the current stack element in the deepest stack entry - // involved have to also be involved in that cycle. - // - // We can only move entries to the global cache once we're complete done - // with the cycle. If this entry has not been involved in a cycle, - // this is just its own depth. + /// In case we have a coinductive cycle, this is the + /// the current provisional result of this goal. + /// + /// This starts out as `None` for all goals and gets to some + /// when the goal gets popped from the stack or we rerun evaluation + /// for this goal to reach a fixpoint. + pub(super) response: Option<QueryResult<'tcx>>, + /// In case of a cycle, the position of deepest stack entry involved + /// in that cycle. This is monotonically decreasing in the stack as all + /// elements between the current stack element in the deepest stack entry + /// involved have to also be involved in that cycle. + /// + /// We can only move entries to the global cache once we're complete done + /// with the cycle. If this entry has not been involved in a cycle, + /// this is just its own depth. pub(super) depth: StackDepth, - // The goal for this entry. Should always be equal to the corresponding goal - // in the lookup table. + /// The goal for this entry. Should always be equal to the corresponding goal + /// in the lookup table. pub(super) input: CanonicalInput<'tcx>, } @@ -92,7 +96,7 @@ impl<'tcx> ProvisionalCache<'tcx> { self.entries[entry_index].depth } - pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> QueryResult<'tcx> { + pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> Option<QueryResult<'tcx>> { self.entries[entry_index].response } } 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 f00456e26..49ebfa4e6 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -1,37 +1,51 @@ mod cache; -mod overflow; - -pub(super) use overflow::OverflowHandler; -use rustc_middle::traits::solve::inspect::CacheHit; use self::cache::ProvisionalEntry; +use super::inspect::ProofTreeBuilder; +use super::SolverMode; use cache::ProvisionalCache; -use overflow::OverflowData; +use rustc_data_structures::fx::FxHashSet; +use rustc_index::Idx; use rustc_index::IndexVec; use rustc_middle::dep_graph::DepKind; -use rustc_middle::traits::solve::{CanonicalInput, Certainty, MaybeCause, QueryResult}; +use rustc_middle::traits::solve::inspect::CacheHit; +use rustc_middle::traits::solve::CacheData; +use rustc_middle::traits::solve::{CanonicalInput, Certainty, EvaluationCache, QueryResult}; use rustc_middle::ty::TyCtxt; -use std::{collections::hash_map::Entry, mem}; - -use super::inspect::ProofTreeBuilder; -use super::SolverMode; +use rustc_session::Limit; +use std::collections::hash_map::Entry; rustc_index::newtype_index! { pub struct StackDepth {} } -struct StackElem<'tcx> { +#[derive(Debug)] +struct StackEntry<'tcx> { input: CanonicalInput<'tcx>, + available_depth: Limit, + // The maximum depth reached by this stack entry, only up-to date + // for the top of the stack and lazily updated for the rest. + reached_depth: StackDepth, + encountered_overflow: bool, has_been_used: bool, + + /// We put only the root goal of a coinductive cycle into the global cache. + /// + /// If we were to use that result when later trying to prove another cycle + /// participant, we can end up with unstable query results. + /// + /// See tests/ui/new-solver/coinduction/incompleteness-unstable-result.rs for + /// an example of where this is needed. + cycle_participants: FxHashSet<CanonicalInput<'tcx>>, } pub(super) struct SearchGraph<'tcx> { mode: SolverMode, + local_overflow_limit: usize, /// The stack of goals currently being computed. /// /// An element is *deeper* in the stack if its index is *lower*. - stack: IndexVec<StackDepth, StackElem<'tcx>>, - overflow_data: OverflowData, + stack: IndexVec<StackDepth, StackEntry<'tcx>>, provisional_cache: ProvisionalCache<'tcx>, } @@ -39,8 +53,8 @@ impl<'tcx> SearchGraph<'tcx> { pub(super) fn new(tcx: TyCtxt<'tcx>, mode: SolverMode) -> SearchGraph<'tcx> { Self { mode, + local_overflow_limit: tcx.recursion_limit().0.ilog2() as usize, stack: Default::default(), - overflow_data: OverflowData::new(tcx), provisional_cache: ProvisionalCache::empty(), } } @@ -49,19 +63,42 @@ impl<'tcx> SearchGraph<'tcx> { self.mode } - /// We do not use the global cache during coherence. + pub(super) fn local_overflow_limit(&self) -> usize { + self.local_overflow_limit + } + + /// Update the stack and reached depths on cache hits. + #[instrument(level = "debug", skip(self))] + fn on_cache_hit(&mut self, additional_depth: usize, encountered_overflow: bool) { + let reached_depth = self.stack.next_index().plus(additional_depth); + if let Some(last) = self.stack.raw.last_mut() { + last.reached_depth = last.reached_depth.max(reached_depth); + last.encountered_overflow |= encountered_overflow; + } + } + + /// Pops the highest goal from the stack, lazily updating the + /// the next goal in the stack. /// + /// Directly popping from the stack instead of using this method + /// would cause us to not track overflow and recursion depth correctly. + fn pop_stack(&mut self) -> StackEntry<'tcx> { + let elem = self.stack.pop().unwrap(); + if let Some(last) = self.stack.raw.last_mut() { + last.reached_depth = last.reached_depth.max(elem.reached_depth); + last.encountered_overflow |= elem.encountered_overflow; + } + elem + } + /// The trait solver behavior is different for coherence - /// so we would have to add the solver mode to the cache key. - /// This is probably not worth it as trait solving during - /// coherence tends to already be incredibly fast. - /// - /// We could add another global cache for coherence instead, - /// but that's effort so let's only do it if necessary. - pub(super) fn should_use_global_cache(&self) -> bool { + /// so we use a separate cache. Alternatively we could use + /// a single cache and share it between coherence and ordinary + /// trait solving. + pub(super) fn global_cache(&self, tcx: TyCtxt<'tcx>) -> &'tcx EvaluationCache<'tcx> { match self.mode { - SolverMode::Normal => true, - SolverMode::Coherence => false, + SolverMode::Normal => &tcx.new_solver_evaluation_cache, + SolverMode::Coherence => &tcx.new_solver_coherence_evaluation_cache, } } @@ -87,36 +124,111 @@ impl<'tcx> SearchGraph<'tcx> { } } - /// Tries putting the new goal on the stack, returning an error if it is already cached. + /// Fetches whether the current goal encountered overflow. + /// + /// This should only be used for the check in `evaluate_goal`. + pub(super) fn encountered_overflow(&self) -> bool { + if let Some(last) = self.stack.raw.last() { last.encountered_overflow } else { false } + } + + /// Resets `encountered_overflow` of the current goal. + /// + /// This should only be used for the check in `evaluate_goal`. + pub(super) fn reset_encountered_overflow(&mut self, encountered_overflow: bool) -> bool { + if let Some(last) = self.stack.raw.last_mut() { + let prev = last.encountered_overflow; + last.encountered_overflow = encountered_overflow; + prev + } else { + false + } + } + + /// Returns the remaining depth allowed for nested goals. + /// + /// This is generally simply one less than the current depth. + /// However, if we encountered overflow, we significantly reduce + /// the remaining depth of all nested goals to prevent hangs + /// in case there is exponential blowup. + fn allowed_depth_for_nested( + tcx: TyCtxt<'tcx>, + stack: &IndexVec<StackDepth, StackEntry<'tcx>>, + ) -> Option<Limit> { + if let Some(last) = stack.raw.last() { + if last.available_depth.0 == 0 { + return None; + } + + Some(if last.encountered_overflow { + Limit(last.available_depth.0 / 4) + } else { + Limit(last.available_depth.0 - 1) + }) + } else { + Some(tcx.recursion_limit()) + } + } + + /// Probably the most involved method of the whole solver. /// - /// This correctly updates the provisional cache if there is a cycle. - #[instrument(level = "debug", skip(self, tcx, inspect), ret)] - fn try_push_stack( + /// Given some goal which is proven via the `prove_goal` closure, this + /// handles caching, overflow, and coinductive cycles. + pub(super) fn with_new_goal( &mut self, tcx: TyCtxt<'tcx>, input: CanonicalInput<'tcx>, inspect: &mut ProofTreeBuilder<'tcx>, - ) -> Result<(), QueryResult<'tcx>> { - // Look at the provisional cache to check for cycles. + mut prove_goal: impl FnMut(&mut Self, &mut ProofTreeBuilder<'tcx>) -> QueryResult<'tcx>, + ) -> QueryResult<'tcx> { + // Check for overflow. + let Some(available_depth) = Self::allowed_depth_for_nested(tcx, &self.stack) else { + if let Some(last) = self.stack.raw.last_mut() { + last.encountered_overflow = true; + } + return Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); + }; + + // Try to fetch the goal from the global cache. + if inspect.use_global_cache() { + if let Some(CacheData { result, reached_depth, encountered_overflow }) = + self.global_cache(tcx).get( + tcx, + input, + |cycle_participants| { + self.stack.iter().any(|entry| cycle_participants.contains(&entry.input)) + }, + available_depth, + ) + { + self.on_cache_hit(reached_depth, encountered_overflow); + return result; + } + } + + // Look at the provisional cache to detect cycles. let cache = &mut self.provisional_cache; match cache.lookup_table.entry(input) { - // No entry, simply push this goal on the stack after dealing with overflow. + // No entry, we push this goal on the stack and try to prove it. Entry::Vacant(v) => { - if self.overflow_data.has_overflow(self.stack.len()) { - return Err(self.deal_with_overflow(tcx, input)); - } - - let depth = self.stack.push(StackElem { input, has_been_used: false }); - let response = super::response_no_constraints(tcx, input, Certainty::Yes); - let entry_index = cache.entries.push(ProvisionalEntry { response, depth, input }); + let depth = self.stack.next_index(); + let entry = StackEntry { + input, + available_depth, + reached_depth: depth, + encountered_overflow: false, + has_been_used: false, + cycle_participants: Default::default(), + }; + assert_eq!(self.stack.push(entry), depth); + let entry_index = + cache.entries.push(ProvisionalEntry { response: None, depth, input }); v.insert(entry_index); - Ok(()) } // We have a nested goal which relies on a goal `root` deeper in the stack. // - // We first store that we may have to rerun `evaluate_goal` for `root` in case the - // provisional response is not equal to the final response. We also update the depth - // of all goals which recursively depend on our current goal to depend on `root` + // We first store that we may have to reprove `root` in case the provisional + // response is not equal to the final response. We also update the depth of all + // goals which recursively depend on our current goal to depend on `root` // instead. // // Finally we can return either the provisional response for that goal if we have a @@ -125,169 +237,144 @@ impl<'tcx> SearchGraph<'tcx> { inspect.cache_hit(CacheHit::Provisional); let entry_index = *entry_index.get(); - let stack_depth = cache.depth(entry_index); debug!("encountered cycle with depth {stack_depth:?}"); cache.add_dependency_of_leaf_on(entry_index); + let mut iter = self.stack.iter_mut(); + let root = iter.nth(stack_depth.as_usize()).unwrap(); + for e in iter { + root.cycle_participants.insert(e.input); + } + // If we're in a cycle, we have to retry proving the current goal + // until we reach a fixpoint. self.stack[stack_depth].has_been_used = true; - // NOTE: The goals on the stack aren't the only goals involved in this cycle. - // We can also depend on goals which aren't part of the stack but coinductively - // depend on the stack themselves. We already checked whether all the goals - // between these goals and their root on the stack. This means that as long as - // each goal in a cycle is checked for coinductivity by itself, simply checking - // the stack is enough. - if self.stack.raw[stack_depth.index()..] - .iter() - .all(|g| g.input.value.goal.predicate.is_coinductive(tcx)) - { - Err(cache.provisional_result(entry_index)) + return if let Some(result) = cache.provisional_result(entry_index) { + result } else { - Err(super::response_no_constraints( - tcx, - input, - Certainty::Maybe(MaybeCause::Overflow), - )) - } - } - } - } - - /// We cannot simply store the result of [super::EvalCtxt::compute_goal] as we have to deal with - /// coinductive cycles. - /// - /// When we encounter a coinductive cycle, we have to prove the final result of that cycle - /// while we are still computing that result. Because of this we continuously recompute the - /// cycle until the result of the previous iteration is equal to the final result, at which - /// point we are done. - /// - /// This function returns `true` if we were able to finalize the goal and `false` if it has - /// updated the provisional cache and we have to recompute the current goal. - /// - /// FIXME: Refer to the rustc-dev-guide entry once it exists. - #[instrument(level = "debug", skip(self, actual_input), ret)] - fn try_finalize_goal( - &mut self, - actual_input: CanonicalInput<'tcx>, - response: QueryResult<'tcx>, - ) -> bool { - let stack_elem = self.stack.pop().unwrap(); - let StackElem { input, has_been_used } = stack_elem; - assert_eq!(input, actual_input); - - let cache = &mut self.provisional_cache; - let provisional_entry_index = *cache.lookup_table.get(&input).unwrap(); - let provisional_entry = &mut cache.entries[provisional_entry_index]; - // We eagerly update the response in the cache here. If we have to reevaluate - // this goal we use the new response when hitting a cycle, and we definitely - // want to access the final response whenever we look at the cache. - let prev_response = mem::replace(&mut provisional_entry.response, response); - - // Was the current goal the root of a cycle and was the provisional response - // different from the final one. - if has_been_used && prev_response != response { - // If so, remove all entries whose result depends on this goal - // from the provisional cache... - // - // That's not completely correct, as a nested goal can also - // depend on a goal which is lower in the stack so it doesn't - // actually depend on the current goal. This should be fairly - // rare and is hopefully not relevant for performance. - #[allow(rustc::potential_query_instability)] - cache.lookup_table.retain(|_key, index| *index <= provisional_entry_index); - cache.entries.truncate(provisional_entry_index.index() + 1); - - // ...and finally push our goal back on the stack and reevaluate it. - self.stack.push(StackElem { input, has_been_used: false }); - false - } else { - true - } - } + // If we don't have a provisional result yet, the goal has to + // still be on the stack. + let mut goal_on_stack = false; + let mut is_coinductive = true; + for entry in self.stack.raw[stack_depth.index()..] + .iter() + .skip_while(|entry| entry.input != input) + { + goal_on_stack = true; + is_coinductive &= entry.input.value.goal.predicate.is_coinductive(tcx); + } + debug_assert!(goal_on_stack); - pub(super) fn with_new_goal( - &mut self, - tcx: TyCtxt<'tcx>, - canonical_input: CanonicalInput<'tcx>, - inspect: &mut ProofTreeBuilder<'tcx>, - mut loop_body: impl FnMut(&mut Self, &mut ProofTreeBuilder<'tcx>) -> QueryResult<'tcx>, - ) -> QueryResult<'tcx> { - if self.should_use_global_cache() && inspect.use_global_cache() { - if let Some(result) = tcx.new_solver_evaluation_cache.get(&canonical_input, tcx) { - debug!(?canonical_input, ?result, "cache hit"); - inspect.cache_hit(CacheHit::Global); - return result; + if is_coinductive { + Self::response_no_constraints(tcx, input, Certainty::Yes) + } else { + Self::response_no_constraints(tcx, input, Certainty::OVERFLOW) + } + }; } } - match self.try_push_stack(tcx, canonical_input, inspect) { - Ok(()) => {} - // Our goal is already on the stack, eager return. - Err(response) => return response, - } - // This is for global caching, so we properly track query dependencies. - // Everything that affects the `Result` should be performed within this + // Everything that affects the `result` should be performed within this // `with_anon_task` closure. - let (result, dep_node) = tcx.dep_graph.with_anon_task(tcx, DepKind::TraitSelect, || { - self.repeat_while_none( - |this| { - let result = this.deal_with_overflow(tcx, canonical_input); - let _ = this.stack.pop().unwrap(); - result - }, - |this| { - let result = loop_body(this, inspect); - this.try_finalize_goal(canonical_input, result).then(|| result) - }, - ) - }); + let ((final_entry, result), dep_node) = + tcx.dep_graph.with_anon_task(tcx, DepKind::TraitSelect, || { + // When we encounter a coinductive cycle, we have to fetch the + // result of that cycle while we are still computing it. Because + // of this we continuously recompute the cycle until the result + // of the previous iteration is equal to the final result, at which + // point we are done. + for _ in 0..self.local_overflow_limit() { + let response = prove_goal(self, inspect); + // Check whether the current goal is the root of a cycle and whether + // we have to rerun because its provisional result differed from the + // final result. + // + // Also update the response for this goal stored in the provisional + // cache. + let stack_entry = self.pop_stack(); + debug_assert_eq!(stack_entry.input, input); + let cache = &mut self.provisional_cache; + let provisional_entry_index = + *cache.lookup_table.get(&stack_entry.input).unwrap(); + let provisional_entry = &mut cache.entries[provisional_entry_index]; + if stack_entry.has_been_used + && provisional_entry.response.map_or(true, |r| r != response) + { + // If so, update the provisional result for this goal and remove + // all entries whose result depends on this goal from the provisional + // cache... + // + // That's not completely correct, as a nested goal can also only + // depend on a goal which is lower in the stack so it doesn't + // actually depend on the current goal. This should be fairly + // rare and is hopefully not relevant for performance. + provisional_entry.response = Some(response); + #[allow(rustc::potential_query_instability)] + cache.lookup_table.retain(|_key, index| *index <= provisional_entry_index); + cache.entries.truncate(provisional_entry_index.index() + 1); + + // ...and finally push our goal back on the stack and reevaluate it. + self.stack.push(StackEntry { has_been_used: false, ..stack_entry }); + } else { + return (stack_entry, response); + } + } + + debug!("canonical cycle overflow"); + let current_entry = self.pop_stack(); + let result = Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); + (current_entry, result) + }); + + // We're now done with this goal. In case this goal is involved in a larger cycle + // do not remove it from the provisional cache and update its provisional result. + // We only add the root of cycles to the global cache. + // + // It is not possible for any nested goal to depend on something deeper on the + // stack, as this would have also updated the depth of the current goal. let cache = &mut self.provisional_cache; - let provisional_entry_index = *cache.lookup_table.get(&canonical_input).unwrap(); + let provisional_entry_index = *cache.lookup_table.get(&input).unwrap(); let provisional_entry = &mut cache.entries[provisional_entry_index]; let depth = provisional_entry.depth; - - // If not, we're done with this goal. - // - // Check whether that this goal doesn't depend on a goal deeper on the stack - // and if so, move it to the global cache. - // - // Note that if any nested goal were to depend on something deeper on the stack, - // this would have also updated the depth of the current goal. if depth == self.stack.next_index() { - // If the current goal is the head of a cycle, we drop all other - // cycle participants without moving them to the global cache. - let other_cycle_participants = provisional_entry_index.index() + 1; - for (i, entry) in cache.entries.drain_enumerated(other_cycle_participants..) { + for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..) { let actual_index = cache.lookup_table.remove(&entry.input); debug_assert_eq!(Some(i), actual_index); debug_assert!(entry.depth == depth); } - let current_goal = cache.entries.pop().unwrap(); - let actual_index = cache.lookup_table.remove(¤t_goal.input); - debug_assert_eq!(Some(provisional_entry_index), actual_index); - debug_assert!(current_goal.depth == depth); - - // We move the root goal to the global cache if we either did not hit an overflow or if it's - // the root goal as that will now always hit the same overflow limit. - // - // NOTE: We cannot move any non-root goals to the global cache. When replaying the root goal's - // dependencies, our non-root goal may no longer appear as child of the root goal. + // When encountering a cycle, both inductive and coinductive, we only + // move the root into the global cache. We also store all other cycle + // participants involved. // - // See https://github.com/rust-lang/rust/pull/108071 for some additional context. - let can_cache = !self.overflow_data.did_overflow() || self.stack.is_empty(); - if self.should_use_global_cache() && can_cache { - tcx.new_solver_evaluation_cache.insert( - current_goal.input, - dep_node, - current_goal.response, - ); - } + // We disable the global cache entry of the root goal if a cycle + // participant is on the stack. This is necessary to prevent unstable + // results. See the comment of `StackEntry::cycle_participants` for + // more details. + let reached_depth = final_entry.reached_depth.as_usize() - self.stack.len(); + self.global_cache(tcx).insert( + input, + reached_depth, + final_entry.encountered_overflow, + final_entry.cycle_participants, + dep_node, + result, + ) + } else { + provisional_entry.response = Some(result); } result } + + fn response_no_constraints( + tcx: TyCtxt<'tcx>, + goal: CanonicalInput<'tcx>, + certainty: Certainty, + ) -> QueryResult<'tcx> { + Ok(super::response_no_constraints_raw(tcx, goal.max_universe, goal.variables, certainty)) + } } diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs deleted file mode 100644 index e0a2e0c5c..000000000 --- a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs +++ /dev/null @@ -1,120 +0,0 @@ -use rustc_infer::infer::canonical::Canonical; -use rustc_infer::traits::query::NoSolution; -use rustc_middle::traits::solve::{Certainty, MaybeCause, QueryResult}; -use rustc_middle::ty::TyCtxt; -use rustc_session::Limit; - -use super::SearchGraph; -use crate::solve::{response_no_constraints, EvalCtxt}; - -/// When detecting a solver overflow, we return ambiguity. Overflow can be -/// *hidden* by either a fatal error in an **AND** or a trivial success in an **OR**. -/// -/// This is in issue in case of exponential blowup, e.g. if each goal on the stack -/// has multiple nested (overflowing) candidates. To deal with this, we reduce the limit -/// used by the solver when hitting the default limit for the first time. -/// -/// FIXME: Get tests where always using the `default_limit` results in a hang and refer -/// to them here. We can also improve the overflow strategy if necessary. -pub(super) struct OverflowData { - default_limit: Limit, - current_limit: Limit, - /// When proving an **AND** we have to repeatedly iterate over the yet unproven goals. - /// - /// Because of this each iteration also increases the depth in addition to the stack - /// depth. - additional_depth: usize, -} - -impl OverflowData { - pub(super) fn new(tcx: TyCtxt<'_>) -> OverflowData { - let default_limit = tcx.recursion_limit(); - OverflowData { default_limit, current_limit: default_limit, additional_depth: 0 } - } - - #[inline] - pub(super) fn did_overflow(&self) -> bool { - self.default_limit.0 != self.current_limit.0 - } - - #[inline] - pub(super) fn has_overflow(&self, depth: usize) -> bool { - !self.current_limit.value_within_limit(depth + self.additional_depth) - } - - /// Updating the current limit when hitting overflow. - fn deal_with_overflow(&mut self) { - // When first hitting overflow we reduce the overflow limit - // for all future goals to prevent hangs if there's an exponential - // blowup. - self.current_limit.0 = self.default_limit.0 / 8; - } -} - -pub(in crate::solve) trait OverflowHandler<'tcx> { - fn search_graph(&mut self) -> &mut SearchGraph<'tcx>; - - fn repeat_while_none<T>( - &mut self, - on_overflow: impl FnOnce(&mut Self) -> Result<T, NoSolution>, - mut loop_body: impl FnMut(&mut Self) -> Option<Result<T, NoSolution>>, - ) -> Result<T, NoSolution> { - let start_depth = self.search_graph().overflow_data.additional_depth; - let depth = self.search_graph().stack.len(); - while !self.search_graph().overflow_data.has_overflow(depth) { - if let Some(result) = loop_body(self) { - self.search_graph().overflow_data.additional_depth = start_depth; - return result; - } - - self.search_graph().overflow_data.additional_depth += 1; - } - self.search_graph().overflow_data.additional_depth = start_depth; - self.search_graph().overflow_data.deal_with_overflow(); - on_overflow(self) - } - - // Increment the `additional_depth` by one and evaluate `body`, or `on_overflow` - // if the depth is overflown. - fn with_incremented_depth<T>( - &mut self, - on_overflow: impl FnOnce(&mut Self) -> T, - body: impl FnOnce(&mut Self) -> T, - ) -> T { - let depth = self.search_graph().stack.len(); - self.search_graph().overflow_data.additional_depth += 1; - - let result = if self.search_graph().overflow_data.has_overflow(depth) { - self.search_graph().overflow_data.deal_with_overflow(); - on_overflow(self) - } else { - body(self) - }; - - self.search_graph().overflow_data.additional_depth -= 1; - result - } -} - -impl<'tcx> OverflowHandler<'tcx> for EvalCtxt<'_, 'tcx> { - fn search_graph(&mut self) -> &mut SearchGraph<'tcx> { - &mut self.search_graph - } -} - -impl<'tcx> OverflowHandler<'tcx> for SearchGraph<'tcx> { - fn search_graph(&mut self) -> &mut SearchGraph<'tcx> { - self - } -} - -impl<'tcx> SearchGraph<'tcx> { - pub fn deal_with_overflow( - &mut self, - tcx: TyCtxt<'tcx>, - goal: Canonical<'tcx, impl Sized>, - ) -> QueryResult<'tcx> { - self.overflow_data.deal_with_overflow(); - response_no_constraints(tcx, goal, Certainty::Maybe(MaybeCause::Overflow)) - } -} diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs index ef5f25b1f..8685f3100 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -5,13 +5,13 @@ use super::{EvalCtxt, SolverMode}; use rustc_hir::def_id::DefId; use rustc_hir::{LangItem, Movability}; use rustc_infer::traits::query::NoSolution; -use rustc_infer::traits::util::supertraits; +use rustc_middle::traits::solve::inspect::CandidateKind; use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; -use rustc_middle::traits::Reveal; +use rustc_middle::traits::{BuiltinImplSource, Reveal}; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams, TreatProjections}; use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt}; use rustc_middle::ty::{TraitPredicate, TypeVisitableExt}; -use rustc_span::DUMMY_SP; +use rustc_span::{ErrorGuaranteed, DUMMY_SP}; impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { fn self_ty(self) -> Ty<'tcx> { @@ -39,10 +39,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; - if !drcx.substs_refs_may_unify( - goal.predicate.trait_ref.substs, - impl_trait_ref.skip_binder().substs, - ) { + if !drcx + .args_refs_may_unify(goal.predicate.trait_ref.args, impl_trait_ref.skip_binder().args) + { return Err(NoSolution); } @@ -63,13 +62,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { }; ecx.probe_candidate("impl").enter(|ecx| { - let impl_substs = ecx.fresh_substs_for_item(impl_def_id); - let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); + let impl_args = ecx.fresh_args_for_item(impl_def_id); + let impl_trait_ref = impl_trait_ref.instantiate(tcx, impl_args); 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) + .instantiate(tcx, impl_args) .predicates .into_iter() .map(|pred| goal.with(tcx, pred)); @@ -79,6 +78,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { }) } + fn consider_error_guaranteed_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + _guar: ErrorGuaranteed, + ) -> QueryResult<'tcx> { + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + fn probe_and_match_goal_against_assumption( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, @@ -164,7 +170,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx.probe_candidate("trait alias").enter(|ecx| { let nested_obligations = tcx .predicates_of(goal.predicate.def_id()) - .instantiate(tcx, goal.predicate.trait_ref.substs); + .instantiate(tcx, goal.predicate.trait_ref.args); ecx.add_goals(nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p))); ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) @@ -337,7 +343,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { } let self_ty = goal.predicate.self_ty(); - let ty::Generator(def_id, substs, _) = *self_ty.kind() else { + let ty::Generator(def_id, args, _) = *self_ty.kind() else { return Err(NoSolution); }; @@ -347,7 +353,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { return Err(NoSolution); } - let generator = substs.as_generator(); + let generator = args.as_generator(); Self::consider_implied_clause( ecx, goal, @@ -359,7 +365,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ) } - fn consider_builtin_unsize_candidate( + fn consider_builtin_discriminant_kind_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { @@ -367,131 +373,205 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { return Err(NoSolution); } - let tcx = ecx.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.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + // `DiscriminantKind` is automatically implemented for every type. + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + + fn consider_builtin_destruct_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + if goal.predicate.polarity != ty::ImplPolarity::Positive { + return Err(NoSolution); } - ecx.probe_candidate("builtin unsize").enter(|ecx| { - match (a_ty.kind(), b_ty.kind()) { - // Trait upcasting, or `dyn Trait + Auto + 'a` -> `dyn Trait + 'b` - (&ty::Dynamic(_, _, ty::Dyn), &ty::Dynamic(_, _, ty::Dyn)) => { - // 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. - Err(NoSolution) - } - // `T` -> `dyn Trait` unsizing - (_, &ty::Dynamic(data, region, ty::Dyn)) => { - // Can only unsize to an object-safe type - if data - .principal_def_id() - .is_some_and(|def_id| !tcx.check_is_object_safe(def_id)) - { - return Err(NoSolution); - } - let Some(sized_def_id) = tcx.lang_items().sized_trait() else { - return Err(NoSolution); - }; - // 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::TraitRef::new(tcx, 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 - 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)) - if a_def.is_struct() && a_def.did() == b_def.did() => - { - let unsizing_params = tcx.unsizing_params_for_adt(a_def.did()); - // We must be unsizing some type parameters. This also implies - // that the struct has a tail field. - if unsizing_params.is_empty() { - return Err(NoSolution); - } + // FIXME(-Ztrait-solver=next): Implement this when we get const working in the new solver - let tail_field = a_def.non_enum_variant().tail(); - let tail_field_ty = tcx.type_of(tail_field.did); - - let a_tail_ty = tail_field_ty.subst(tcx, a_substs); - let b_tail_ty = tail_field_ty.subst(tcx, b_substs); - - // Substitute just the unsizing params from B into A. The type after - // this substitution must be equal to B. This is so we don't unsize - // unrelated type parameters. - let new_a_substs = - tcx.mk_substs_from_iter(a_substs.iter().enumerate().map(|(i, a)| { - if unsizing_params.contains(i as u32) { b_substs[i] } else { a } - })); - let unsized_a_ty = Ty::new_adt(tcx, a_def, new_a_substs); - - // Finally, we require that `TailA: Unsize<TailB>` for the tail field - // types. - ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; - ecx.add_goal(goal.with( - tcx, - ty::TraitRef::new(tcx, goal.predicate.def_id(), [a_tail_ty, b_tail_ty]), - )); - 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)) - if a_tys.len() == b_tys.len() && !a_tys.is_empty() => - { - let (a_last_ty, a_rest_tys) = a_tys.split_last().unwrap(); - let b_last_ty = b_tys.last().unwrap(); - - // Substitute just the tail field of B., and require that they're equal. - let unsized_a_ty = - Ty::new_tup_from_iter(tcx, a_rest_tys.iter().chain([b_last_ty]).copied()); - ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; - - // Similar to ADTs, require that the rest of the fields are equal. - ecx.add_goal(goal.with( - tcx, - ty::TraitRef::new(tcx, goal.predicate.def_id(), [*a_last_ty, *b_last_ty]), - )); - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } - _ => Err(NoSolution), + // `Destruct` is automatically implemented for every type in + // non-const environments. + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + + fn consider_builtin_transmute_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + if goal.predicate.polarity != ty::ImplPolarity::Positive { + return Err(NoSolution); + } + + // `rustc_transmute` does not have support for type or const params + if goal.has_non_region_placeholders() { + return Err(NoSolution); + } + + // Erase regions because we compute layouts in `rustc_transmute`, + // which will ICE for region vars. + let args = ecx.tcx().erase_regions(goal.predicate.trait_ref.args); + + let Some(assume) = + rustc_transmute::Assume::from_const(ecx.tcx(), goal.param_env, args.const_at(3)) + else { + return Err(NoSolution); + }; + + let certainty = ecx.is_transmutable( + rustc_transmute::Types { dst: args.type_at(0), src: args.type_at(1) }, + args.type_at(2), + assume, + )?; + ecx.evaluate_added_goals_and_make_canonical_response(certainty) + } + + fn consider_unsize_to_dyn_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + ecx.probe(|_| CandidateKind::UnsizeAssembly).enter(|ecx| { + let a_ty = goal.predicate.self_ty(); + // We need to normalize the b_ty since it's destructured as a `dyn Trait`. + let Some(b_ty) = + ecx.try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1))? + else { + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW); + }; + + let ty::Dynamic(b_data, b_region, ty::Dyn) = *b_ty.kind() else { + return Err(NoSolution); + }; + + let tcx = ecx.tcx(); + + // Can only unsize to an object-safe trait. + if b_data.principal_def_id().is_some_and(|def_id| !tcx.check_is_object_safe(def_id)) { + return Err(NoSolution); + } + + // Check that the type implements all of the predicates of the trait object. + // (i.e. the principal, all of the associated types match, and any auto traits) + ecx.add_goals(b_data.iter().map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty)))); + + // The type must be `Sized` to be unsized. + if let Some(sized_def_id) = tcx.lang_items().sized_trait() { + ecx.add_goal(goal.with(tcx, ty::TraitRef::new(tcx, sized_def_id, [a_ty]))); + } else { + return Err(NoSolution); } + + // The type must outlive the lifetime of the `dyn` we're unsizing into. + ecx.add_goal(goal.with(tcx, ty::OutlivesPredicate(a_ty, b_region))); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } - fn consider_builtin_dyn_upcast_candidates( + /// ```ignore (builtin impl example) + /// trait Trait { + /// fn foo(&self); + /// } + /// // results in the following builtin impl + /// impl<'a, T: Trait + 'a> Unsize<dyn Trait + 'a> for T {} + /// ``` + fn consider_structural_builtin_unsize_candidates( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - ) -> Vec<CanonicalResponse<'tcx>> { + ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)> { if goal.predicate.polarity != ty::ImplPolarity::Positive { return vec![]; } - let tcx = ecx.tcx(); - - let a_ty = goal.predicate.self_ty(); - let b_ty = goal.predicate.trait_ref.substs.type_at(1); - let ty::Dynamic(a_data, a_region, ty::Dyn) = *a_ty.kind() else { - return vec![]; + let misc_candidate = |ecx: &mut EvalCtxt<'_, 'tcx>, certainty| { + ( + ecx.evaluate_added_goals_and_make_canonical_response(certainty).unwrap(), + BuiltinImplSource::Misc, + ) }; - let ty::Dynamic(b_data, b_region, ty::Dyn) = *b_ty.kind() else { - return vec![]; + + let result_to_single = |result, source| match result { + Ok(resp) => vec![(resp, source)], + Err(NoSolution) => vec![], }; + ecx.probe(|_| CandidateKind::UnsizeAssembly).enter(|ecx| { + let a_ty = goal.predicate.self_ty(); + // We need to normalize the b_ty since it's matched structurally + // in the other functions below. + let b_ty = match ecx + .try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1)) + { + Ok(Some(b_ty)) => b_ty, + Ok(None) => return vec![misc_candidate(ecx, Certainty::OVERFLOW)], + Err(_) => return vec![], + }; + + let goal = goal.with(ecx.tcx(), (a_ty, b_ty)); + match (a_ty.kind(), b_ty.kind()) { + (ty::Infer(ty::TyVar(..)), ..) => bug!("unexpected infer {a_ty:?} {b_ty:?}"), + (_, ty::Infer(ty::TyVar(..))) => vec![misc_candidate(ecx, Certainty::AMBIGUOUS)], + + // Trait upcasting, or `dyn Trait + Auto + 'a` -> `dyn Trait + 'b`. + ( + &ty::Dynamic(a_data, a_region, ty::Dyn), + &ty::Dynamic(b_data, b_region, ty::Dyn), + ) => ecx.consider_builtin_dyn_upcast_candidates( + goal, a_data, a_region, b_data, b_region, + ), + + // `T` -> `dyn Trait` unsizing is handled separately in `consider_unsize_to_dyn_candidate` + (_, &ty::Dynamic(..)) => vec![], + + // `[T; N]` -> `[T]` unsizing + (&ty::Array(a_elem_ty, ..), &ty::Slice(b_elem_ty)) => result_to_single( + ecx.consider_builtin_array_unsize(goal, a_elem_ty, b_elem_ty), + BuiltinImplSource::Misc, + ), + + // `Struct<T>` -> `Struct<U>` where `T: Unsize<U>` + (&ty::Adt(a_def, a_args), &ty::Adt(b_def, b_args)) + if a_def.is_struct() && a_def == b_def => + { + result_to_single( + ecx.consider_builtin_struct_unsize(goal, a_def, a_args, b_args), + BuiltinImplSource::Misc, + ) + } + + // `(A, B, T)` -> `(A, B, U)` where `T: Unsize<U>` + (&ty::Tuple(a_tys), &ty::Tuple(b_tys)) + if a_tys.len() == b_tys.len() && !a_tys.is_empty() => + { + result_to_single( + ecx.consider_builtin_tuple_unsize(goal, a_tys, b_tys), + BuiltinImplSource::TupleUnsizing, + ) + } + + _ => vec![], + } + }) + } +} + +impl<'tcx> EvalCtxt<'_, 'tcx> { + /// Trait upcasting allows for coercions between trait objects: + /// ```ignore (builtin impl example) + /// trait Super {} + /// trait Trait: Super {} + /// // results in builtin impls upcasting to a super trait + /// impl<'a, 'b: 'a> Unsize<dyn Super + 'a> for dyn Trait + 'b {} + /// // and impls removing auto trait bounds. + /// impl<'a, 'b: 'a> Unsize<dyn Trait + 'a> for dyn Trait + Send + 'b {} + /// ``` + fn consider_builtin_dyn_upcast_candidates( + &mut self, + goal: Goal<'tcx, (Ty<'tcx>, Ty<'tcx>)>, + a_data: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>, + a_region: ty::Region<'tcx>, + b_data: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>, + b_region: ty::Region<'tcx>, + ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)> { + let tcx = self.tcx(); + let Goal { predicate: (a_ty, _b_ty), .. } = goal; + // All of a's auto traits need to be in b's auto traits. let auto_traits_compatible = b_data.auto_traits().all(|b| a_data.auto_traits().any(|a| a == b)); @@ -499,125 +579,241 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { return vec![]; } - let mut unsize_dyn_to_principal = |principal: Option<ty::PolyExistentialTraitRef<'tcx>>| { - ecx.probe_candidate("upcast dyn to principle").enter(|ecx| -> Result<_, NoSolution> { - // Require that all of the trait predicates from A match B, except for - // the auto traits. We do this by constructing a new A type with B's - // auto traits, and equating these types. - let new_a_data = principal - .into_iter() - .map(|trait_ref| trait_ref.map_bound(ty::ExistentialPredicate::Trait)) - .chain(a_data.iter().filter(|a| { - matches!(a.skip_binder(), ty::ExistentialPredicate::Projection(_)) - })) - .chain( - b_data - .auto_traits() - .map(ty::ExistentialPredicate::AutoTrait) - .map(ty::Binder::dummy), - ); - let new_a_data = tcx.mk_poly_existential_predicates_from_iter(new_a_data); - let new_a_ty = Ty::new_dynamic(tcx, new_a_data, b_region, ty::Dyn); - - // We also require that A's lifetime outlives B's lifetime. - 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_added_goals_and_make_canonical_response(Certainty::Yes) - }) - }; - let mut responses = vec![]; // If the principal def ids match (or are both none), then we're not doing // trait upcasting. We're just removing auto traits (or shortening the lifetime). if a_data.principal_def_id() == b_data.principal_def_id() { - if let Ok(response) = unsize_dyn_to_principal(a_data.principal()) { - responses.push(response); - } - } else if let Some(a_principal) = a_data.principal() - && let Some(b_principal) = b_data.principal() - { - for super_trait_ref in supertraits(tcx, a_principal.with_self_ty(tcx, a_ty)) { - if super_trait_ref.def_id() != b_principal.def_id() { - continue; - } - let erased_trait_ref = super_trait_ref - .map_bound(|trait_ref| ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref)); - if let Ok(response) = unsize_dyn_to_principal(Some(erased_trait_ref)) { - responses.push(response); - } + if let Ok(resp) = self.consider_builtin_upcast_to_principal( + goal, + a_data, + a_region, + b_data, + b_region, + a_data.principal(), + ) { + responses.push((resp, BuiltinImplSource::Misc)); } + } else if let Some(a_principal) = a_data.principal() { + self.walk_vtable( + a_principal.with_self_ty(tcx, a_ty), + |ecx, new_a_principal, _, vtable_vptr_slot| { + if let Ok(resp) = ecx.probe_candidate("dyn upcast").enter(|ecx| { + ecx.consider_builtin_upcast_to_principal( + goal, + a_data, + a_region, + b_data, + b_region, + Some(new_a_principal.map_bound(|trait_ref| { + ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref) + })), + ) + }) { + responses + .push((resp, BuiltinImplSource::TraitUpcasting { vtable_vptr_slot })); + } + }, + ); } responses } - fn consider_builtin_discriminant_kind_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, + fn consider_builtin_upcast_to_principal( + &mut self, + goal: Goal<'tcx, (Ty<'tcx>, Ty<'tcx>)>, + a_data: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>, + a_region: ty::Region<'tcx>, + b_data: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>, + b_region: ty::Region<'tcx>, + upcast_principal: Option<ty::PolyExistentialTraitRef<'tcx>>, ) -> QueryResult<'tcx> { - if goal.predicate.polarity != ty::ImplPolarity::Positive { - return Err(NoSolution); + let param_env = goal.param_env; + + // More than one projection in a_ty's bounds may match the projection + // in b_ty's bound. Use this to first determine *which* apply without + // having any inference side-effects. We process obligations because + // unification may initially succeed due to deferred projection equality. + let projection_may_match = + |ecx: &mut Self, + source_projection: ty::PolyExistentialProjection<'tcx>, + target_projection: ty::PolyExistentialProjection<'tcx>| { + source_projection.item_def_id() == target_projection.item_def_id() + && ecx + .probe(|_| CandidateKind::UpcastProbe) + .enter(|ecx| -> Result<(), NoSolution> { + ecx.eq(param_env, source_projection, target_projection)?; + let _ = ecx.try_evaluate_added_goals()?; + Ok(()) + }) + .is_ok() + }; + + for bound in b_data { + match bound.skip_binder() { + // Check that a's supertrait (upcast_principal) is compatible + // with the target (b_ty). + ty::ExistentialPredicate::Trait(target_principal) => { + self.eq(param_env, upcast_principal.unwrap(), bound.rebind(target_principal))?; + } + // Check that b_ty's projection is satisfied by exactly one of + // a_ty's projections. First, we look through the list to see if + // any match. If not, error. Then, if *more* than one matches, we + // return ambiguity. Otherwise, if exactly one matches, equate + // it with b_ty's projection. + ty::ExistentialPredicate::Projection(target_projection) => { + let target_projection = bound.rebind(target_projection); + let mut matching_projections = + a_data.projection_bounds().filter(|source_projection| { + projection_may_match(self, *source_projection, target_projection) + }); + let Some(source_projection) = matching_projections.next() else { + return Err(NoSolution); + }; + if matching_projections.next().is_some() { + return self.evaluate_added_goals_and_make_canonical_response( + Certainty::AMBIGUOUS, + ); + } + self.eq(param_env, source_projection, target_projection)?; + } + // Check that b_ty's auto traits are present in a_ty's bounds. + ty::ExistentialPredicate::AutoTrait(def_id) => { + if !a_data.auto_traits().any(|source_def_id| source_def_id == def_id) { + return Err(NoSolution); + } + } + } } - // `DiscriminantKind` is automatically implemented for every type. - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + // Also require that a_ty's lifetime outlives b_ty's lifetime. + self.add_goal(Goal::new( + self.tcx(), + param_env, + ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region)), + )); + + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } - fn consider_builtin_destruct_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, + /// We have the following builtin impls for arrays: + /// ```ignore (builtin impl example) + /// impl<T: ?Sized, const N: usize> Unsize<[T]> for [T; N] {} + /// ``` + /// While the impl itself could theoretically not be builtin, + /// the actual unsizing behavior is builtin. Its also easier to + /// make all impls of `Unsize` builtin as we're able to use + /// `#[rustc_deny_explicit_impl]` in this case. + fn consider_builtin_array_unsize( + &mut self, + goal: Goal<'tcx, (Ty<'tcx>, Ty<'tcx>)>, + a_elem_ty: Ty<'tcx>, + b_elem_ty: Ty<'tcx>, ) -> QueryResult<'tcx> { - if goal.predicate.polarity != ty::ImplPolarity::Positive { - return Err(NoSolution); - } - - if !goal.param_env.is_const() { - // `Destruct` is automatically implemented for every type in - // non-const environments. - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } else { - // FIXME(-Ztrait-solver=next): Implement this when we get const working in the new solver - Err(NoSolution) - } + self.eq(goal.param_env, a_elem_ty, b_elem_ty)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } - fn consider_builtin_transmute_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, + /// We generate a builtin `Unsize` impls for structs with generic parameters only + /// mentioned by the last field. + /// ```ignore (builtin impl example) + /// struct Foo<T, U: ?Sized> { + /// sized_field: Vec<T>, + /// unsizable: Box<U>, + /// } + /// // results in the following builtin impl + /// impl<T: ?Sized, U: ?Sized, V: ?Sized> Unsize<Foo<T, V>> for Foo<T, U> + /// where + /// Box<U>: Unsize<Box<V>>, + /// {} + /// ``` + fn consider_builtin_struct_unsize( + &mut self, + goal: Goal<'tcx, (Ty<'tcx>, Ty<'tcx>)>, + def: ty::AdtDef<'tcx>, + a_args: ty::GenericArgsRef<'tcx>, + b_args: ty::GenericArgsRef<'tcx>, ) -> QueryResult<'tcx> { - if goal.predicate.polarity != ty::ImplPolarity::Positive { - return Err(NoSolution); - } + let tcx = self.tcx(); + let Goal { predicate: (_a_ty, b_ty), .. } = goal; - // `rustc_transmute` does not have support for type or const params - if goal.has_non_region_placeholders() { + let unsizing_params = tcx.unsizing_params_for_adt(def.did()); + // We must be unsizing some type parameters. This also implies + // that the struct has a tail field. + if unsizing_params.is_empty() { return Err(NoSolution); } - // Erase regions because we compute layouts in `rustc_transmute`, - // which will ICE for region vars. - let substs = ecx.tcx().erase_regions(goal.predicate.trait_ref.substs); + let tail_field = def.non_enum_variant().tail(); + let tail_field_ty = tcx.type_of(tail_field.did); + + let a_tail_ty = tail_field_ty.instantiate(tcx, a_args); + let b_tail_ty = tail_field_ty.instantiate(tcx, b_args); + + // Substitute just the unsizing params from B into A. The type after + // this substitution must be equal to B. This is so we don't unsize + // unrelated type parameters. + let new_a_args = tcx.mk_args_from_iter( + a_args + .iter() + .enumerate() + .map(|(i, a)| if unsizing_params.contains(i as u32) { b_args[i] } else { a }), + ); + let unsized_a_ty = Ty::new_adt(tcx, def, new_a_args); + + // Finally, we require that `TailA: Unsize<TailB>` for the tail field + // types. + self.eq(goal.param_env, unsized_a_ty, b_ty)?; + self.add_goal(goal.with( + tcx, + ty::TraitRef::new( + tcx, + tcx.lang_items().unsize_trait().unwrap(), + [a_tail_ty, b_tail_ty], + ), + )); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } - let Some(assume) = rustc_transmute::Assume::from_const( - ecx.tcx(), - goal.param_env, - substs.const_at(3), - ) else { - return Err(NoSolution); - }; + /// We generate the following builtin impl for tuples of all sizes. + /// + /// This impl is still unstable and we emit a feature error when it + /// when it is used by a coercion. + /// ```ignore (builtin impl example) + /// impl<T: ?Sized, U: ?Sized, V: ?Sized> Unsize<(T, V)> for (T, U) + /// where + /// U: Unsize<V>, + /// {} + /// ``` + fn consider_builtin_tuple_unsize( + &mut self, + goal: Goal<'tcx, (Ty<'tcx>, Ty<'tcx>)>, + a_tys: &'tcx ty::List<Ty<'tcx>>, + b_tys: &'tcx ty::List<Ty<'tcx>>, + ) -> QueryResult<'tcx> { + let tcx = self.tcx(); + let Goal { predicate: (_a_ty, b_ty), .. } = goal; - let certainty = ecx.is_transmutable( - rustc_transmute::Types { dst: substs.type_at(0), src: substs.type_at(1) }, - substs.type_at(2), - assume, - )?; - ecx.evaluate_added_goals_and_make_canonical_response(certainty) + let (&a_last_ty, a_rest_tys) = a_tys.split_last().unwrap(); + let &b_last_ty = b_tys.last().unwrap(); + + // Substitute just the tail field of B., and require that they're equal. + let unsized_a_ty = + Ty::new_tup_from_iter(tcx, a_rest_tys.iter().copied().chain([b_last_ty])); + self.eq(goal.param_env, unsized_a_ty, b_ty)?; + + // Similar to ADTs, require that we can unsize the tail. + self.add_goal(goal.with( + tcx, + ty::TraitRef::new( + tcx, + tcx.lang_items().unsize_trait().unwrap(), + [a_last_ty, b_last_ty], + ), + )); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } -} -impl<'tcx> EvalCtxt<'_, 'tcx> { // Return `Some` if there is an impl (built-in or user provided) that may // hold for the self type of the goal, which for coherence and soundness // purposes must disqualify the built-in auto impl assembled by considering @@ -689,7 +885,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::Tuple(_) | ty::Adt(_, _) // FIXME: Handling opaques here is kinda sus. Especially because we - // simplify them to PlaceholderSimplifiedType. + // simplify them to SimplifiedType::Placeholder. | ty::Alias(ty::Opaque, _) => { let mut disqualifying_impl = None; self.tcx().for_each_relevant_impl_treating_projections( @@ -726,12 +922,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ecx.add_goals( constituent_tys(ecx, goal.predicate.self_ty())? .into_iter() - .map(|ty| { - goal.with( - ecx.tcx(), - ty::Binder::dummy(goal.predicate.with_self_ty(ecx.tcx(), ty)), - ) - }) + .map(|ty| goal.with(ecx.tcx(), goal.predicate.with_self_ty(ecx.tcx(), ty))) .collect::<Vec<_>>(), ); ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) diff --git a/compiler/rustc_trait_selection/src/solve/weak_types.rs b/compiler/rustc_trait_selection/src/solve/weak_types.rs index b095b54c5..54de32cf6 100644 --- a/compiler/rustc_trait_selection/src/solve/weak_types.rs +++ b/compiler/rustc_trait_selection/src/solve/weak_types.rs @@ -1,3 +1,8 @@ +//! Computes a normalizes-to (projection) goal for inherent associated types, +//! `#![feature(lazy_type_alias)]` and `#![feature(type_alias_impl_trait)]`. +//! +//! Since a weak alias is not ambiguous, this just computes the `type_of` of +//! the alias and registers the where-clauses of the type alias. use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; use rustc_middle::ty; @@ -12,8 +17,18 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let weak_ty = goal.predicate.projection_ty; let expected = goal.predicate.term.ty().expect("no such thing as a const alias"); - let actual = tcx.type_of(weak_ty.def_id).subst(tcx, weak_ty.substs); + let actual = tcx.type_of(weak_ty.def_id).instantiate(tcx, weak_ty.args); self.eq(goal.param_env, expected, actual)?; + + // Check where clauses + self.add_goals( + tcx.predicates_of(weak_ty.def_id) + .instantiate(tcx, weak_ty.args) + .predicates + .into_iter() + .map(|pred| goal.with(tcx, pred)), + ); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } |