diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve/assembly/mod.rs')
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/assembly/mod.rs | 563 |
1 files changed, 377 insertions, 186 deletions
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) => {} } } |