| //! Code shared by trait and projection goals for candidate assembly. |
| |
| use super::{EvalCtxt, SolverMode}; |
| use crate::traits::coherence; |
| use rustc_hir::def_id::DefId; |
| use rustc_infer::traits::query::NoSolution; |
| use rustc_infer::traits::Reveal; |
| use rustc_middle::traits::solve::inspect::ProbeKind; |
| use rustc_middle::traits::solve::{ |
| CandidateSource, 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; |
| |
| /// A candidate is a possible way to prove a goal. |
| /// |
| /// It consists of both the `source`, which describes how that goal would be proven, |
| /// and the `result` when using the given `source`. |
| #[derive(Debug, Clone)] |
| pub(super) struct Candidate<'tcx> { |
| pub(super) source: CandidateSource, |
| pub(super) result: CanonicalResponse<'tcx>, |
| } |
| |
| /// Methods used to assemble candidates for either trait or projection goals. |
| pub(super) trait GoalKind<'tcx>: |
| TypeFoldable<TyCtxt<'tcx>> + Copy + Eq + std::fmt::Display |
| { |
| fn self_ty(self) -> Ty<'tcx>; |
| |
| fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx>; |
| |
| fn polarity(self) -> ty::ImplPolarity; |
| |
| fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self; |
| |
| 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`]). |
| fn probe_and_match_goal_against_assumption( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| assumption: ty::Clause<'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. |
| fn consider_implied_clause( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| assumption: ty::Clause<'tcx>, |
| requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>, |
| ) -> QueryResult<'tcx> { |
| Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { |
| ecx.add_goals(requirements); |
| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) |
| }) |
| } |
| |
| /// Consider a bound originating from the item bounds of an alias. For this we |
| /// require that the well-formed requirements of the self type of the goal |
| /// are "satisfied from the param-env". |
| /// See [`EvalCtxt::validate_alias_bound_self_from_param_env`]. |
| fn consider_alias_bound_candidate( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| assumption: ty::Clause<'tcx>, |
| ) -> QueryResult<'tcx> { |
| Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { |
| ecx.validate_alias_bound_self_from_param_env(goal) |
| }) |
| } |
| |
| /// 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>, |
| assumption: ty::Clause<'tcx>, |
| ) -> QueryResult<'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, |
| )); |
| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) |
| }) |
| } |
| |
| fn consider_impl_candidate( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| impl_def_id: DefId, |
| ) -> QueryResult<'tcx>; |
| |
| /// 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. |
| 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 |
| /// [`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 |
| /// [`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`. |
| 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. |
| 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. |
| 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. |
| 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. |
| fn consider_builtin_pointee_candidate( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| ) -> QueryResult<'tcx>; |
| |
| /// A coroutine (that comes from an `async` desugaring) is known to implement |
| /// `Future<Output = O>`, where `O` is given by the coroutine'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 coroutine (that comes from a `gen` desugaring) is known to implement |
| /// `Iterator<Item = O>`, where `O` is given by the generator's yield type |
| /// that was computed during type-checking. |
| fn consider_builtin_iterator_candidate( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| ) -> QueryResult<'tcx>; |
| |
| /// A coroutine (that doesn't come from an `async` or `gen` desugaring) is known to |
| /// implement `Coroutine<R, Yield = Y, Return = O>`, given the resume, yield, |
| /// and return types of the coroutine computed during type-checking. |
| fn consider_builtin_coroutine_candidate( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| ) -> QueryResult<'tcx>; |
| |
| fn consider_builtin_discriminant_kind_candidate( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| ) -> QueryResult<'tcx>; |
| |
| fn consider_builtin_destruct_candidate( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| ) -> QueryResult<'tcx>; |
| |
| fn consider_builtin_transmute_candidate( |
| ecx: &mut EvalCtxt<'_, 'tcx>, |
| goal: Goal<'tcx, Self>, |
| ) -> QueryResult<'tcx>; |
| |
| /// 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>, |
| ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)>; |
| |
| /// 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>; |
| } |
| |
| impl<'tcx> EvalCtxt<'_, 'tcx> { |
| pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>( |
| &mut self, |
| 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); |
| |
| 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_non_blanket_impl_candidates(goal, &mut candidates); |
| |
| self.assemble_builtin_impl_candidates(goal, &mut candidates); |
| |
| self.assemble_alias_bound_candidates(goal, &mut candidates); |
| |
| self.assemble_object_bound_candidates(goal, &mut candidates); |
| |
| self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates, num_steps); |
| candidates |
| } |
| |
| /// If the self type of a goal is an alias we first try to normalize the self type |
| /// and compute the candidates for the normalized self type in case that succeeds. |
| /// |
| /// These candidates are used in addition to the ones with the alias as a self type. |
| /// We do this to simplify both builtin candidates and for better performance. |
| /// |
| /// We generate the builtin candidates on the fly by looking at the self type, e.g. |
| /// add `FnPtr` candidates if the self type is a function pointer. Handling builtin |
| /// candidates while the self type is still an alias seems difficult. This is similar |
| /// to `try_structurally_resolve_type` during hir typeck (FIXME once implemented). |
| /// |
| /// Looking at all impls for some trait goal is prohibitively expensive. We therefore |
| /// only look at implementations with a matching self type. Because of this function, |
| /// we can avoid looking at all existing impls if the self type is an alias. |
| #[instrument(level = "debug", skip_all)] |
| fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'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(|_| ProbeKind::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 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) => (), |
| } |
| } |
| } |
| }; |
| |
| 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::Coroutine(_, _, _) |
| | 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 coroutines to instead directly recurse |
| // into the witness. |
| ty::CoroutineWitness(..) => (), |
| |
| // 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}"), |
| } |
| } |
| |
| 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) => (), |
| } |
| } |
| } |
| |
| fn assemble_blanket_impl_candidates<G: GoalKind<'tcx>>( |
| &mut self, |
| goal: Goal<'tcx, G>, |
| candidates: &mut Vec<Candidate<'tcx>>, |
| ) { |
| let tcx = self.tcx(); |
| 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)] |
| fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>( |
| &mut self, |
| goal: Goal<'tcx, G>, |
| candidates: &mut Vec<Candidate<'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 |
| // `consider_auto_trait_candidate` MUST be disqualified to remain sound. |
| // |
| // 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 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 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) |
| } else if lang_items.copy_trait() == Some(trait_def_id) |
| || lang_items.clone_trait() == Some(trait_def_id) |
| { |
| G::consider_builtin_copy_clone_candidate(self, goal) |
| } else if lang_items.pointer_like() == Some(trait_def_id) { |
| G::consider_builtin_pointer_like_candidate(self, goal) |
| } else if lang_items.fn_ptr_trait() == Some(trait_def_id) { |
| G::consider_builtin_fn_ptr_trait_candidate(self, goal) |
| } else if let Some(kind) = self.tcx().fn_trait_kind_from_def_id(trait_def_id) { |
| G::consider_builtin_fn_trait_candidates(self, goal, kind) |
| } else if lang_items.tuple_trait() == Some(trait_def_id) { |
| G::consider_builtin_tuple_candidate(self, goal) |
| } else if lang_items.pointee_trait() == Some(trait_def_id) { |
| G::consider_builtin_pointee_candidate(self, goal) |
| } else if lang_items.future_trait() == Some(trait_def_id) { |
| G::consider_builtin_future_candidate(self, goal) |
| } else if lang_items.iterator_trait() == Some(trait_def_id) { |
| G::consider_builtin_iterator_candidate(self, goal) |
| } else if lang_items.coroutine_trait() == Some(trait_def_id) { |
| G::consider_builtin_coroutine_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) { |
| G::consider_builtin_destruct_candidate(self, goal) |
| } else if lang_items.transmute_trait() == Some(trait_def_id) { |
| G::consider_builtin_transmute_candidate(self, goal) |
| } else { |
| Err(NoSolution) |
| }; |
| |
| match result { |
| Ok(result) => candidates.push(Candidate { |
| source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), |
| result, |
| }), |
| Err(NoSolution) => (), |
| } |
| |
| // 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, source) in G::consider_structural_builtin_unsize_candidates(self, goal) { |
| candidates.push(Candidate { source: CandidateSource::BuiltinImpl(source), result }); |
| } |
| } |
| } |
| |
| #[instrument(level = "debug", skip_all)] |
| fn assemble_param_env_candidates<G: GoalKind<'tcx>>( |
| &mut self, |
| goal: Goal<'tcx, G>, |
| candidates: &mut Vec<Candidate<'tcx>>, |
| ) { |
| for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() { |
| match G::consider_implied_clause(self, goal, assumption, []) { |
| Ok(result) => { |
| candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result }) |
| } |
| Err(NoSolution) => (), |
| } |
| } |
| } |
| |
| #[instrument(level = "debug", skip_all)] |
| fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>( |
| &mut self, |
| goal: Goal<'tcx, G>, |
| candidates: &mut Vec<Candidate<'tcx>>, |
| ) { |
| let alias_ty = match goal.predicate.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::Coroutine(..) |
| | ty::CoroutineWitness(..) |
| | ty::Never |
| | ty::Tuple(_) |
| | ty::Param(_) |
| | ty::Placeholder(..) |
| | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) |
| | ty::Alias(ty::Inherent, _) |
| | ty::Alias(ty::Weak, _) |
| | ty::Error(_) => return, |
| ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) |
| | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"), |
| // Excluding IATs and type aliases here as they don't have meaningful item bounds. |
| ty::Alias(ty::Projection | ty::Opaque, alias_ty) => alias_ty, |
| }; |
| |
| 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) => { |
| candidates.push(Candidate { source: CandidateSource::AliasBound, result }) |
| } |
| Err(NoSolution) => (), |
| } |
| } |
| } |
| |
| /// Check that we are allowed to use an alias bound originating from the self |
| /// type of this goal. This means something different depending on the self type's |
| /// alias kind. |
| /// |
| /// * Projection: Given a goal with a self type such as `<Ty as Trait>::Assoc`, |
| /// we require that the bound `Ty: Trait` can be proven using either a nested alias |
| /// bound candidate, or a param-env candidate. |
| /// |
| /// * Opaque: The param-env must be in `Reveal::UserFacing` mode. Otherwise, |
| /// the goal should be proven by using the hidden type instead. |
| #[instrument(level = "debug", skip(self), ret)] |
| pub(super) fn validate_alias_bound_self_from_param_env<G: GoalKind<'tcx>>( |
| &mut self, |
| goal: Goal<'tcx, G>, |
| ) -> QueryResult<'tcx> { |
| match *goal.predicate.self_ty().kind() { |
| ty::Alias(ty::Projection, projection_ty) => { |
| let mut param_env_candidates = vec![]; |
| let self_trait_ref = projection_ty.trait_ref(self.tcx()); |
| |
| if self_trait_ref.self_ty().is_ty_var() { |
| return self |
| .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); |
| } |
| |
| let trait_goal: Goal<'_, ty::TraitPredicate<'tcx>> = goal.with( |
| self.tcx(), |
| ty::TraitPredicate { |
| trait_ref: self_trait_ref, |
| polarity: ty::ImplPolarity::Positive, |
| }, |
| ); |
| |
| self.assemble_param_env_candidates(trait_goal, &mut param_env_candidates); |
| // FIXME: We probably need some sort of recursion depth check here. |
| // Can't come up with an example yet, though, and the worst case |
| // we can have is a compiler stack overflow... |
| self.assemble_alias_bound_candidates(trait_goal, &mut param_env_candidates); |
| |
| // FIXME: We must also consider alias-bound candidates for a peculiar |
| // class of built-in candidates that I'll call "defaulted" built-ins. |
| // |
| // For example, we always know that `T: Pointee` is implemented, but |
| // we do not always know what `<T as Pointee>::Metadata` actually is, |
| // similar to if we had a user-defined impl with a `default type ...`. |
| // For these traits, since we're not able to always normalize their |
| // associated types to a concrete type, we must consider their alias bounds |
| // instead, so we can prove bounds such as `<T as Pointee>::Metadata: Copy`. |
| self.assemble_alias_bound_candidates_for_builtin_impl_default_items( |
| trait_goal, |
| &mut param_env_candidates, |
| ); |
| |
| self.merge_candidates(param_env_candidates) |
| } |
| ty::Alias(ty::Opaque, _opaque_ty) => match goal.param_env.reveal() { |
| Reveal::UserFacing => { |
| self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) |
| } |
| Reveal::All => return Err(NoSolution), |
| }, |
| _ => bug!("only expected to be called on alias tys"), |
| } |
| } |
| |
| /// Assemble a subset of builtin impl candidates for a class of candidates called |
| /// "defaulted" built-in traits. |
| /// |
| /// For example, we always know that `T: Pointee` is implemented, but we do not |
| /// always know what `<T as Pointee>::Metadata` actually is! See the comment in |
| /// [`EvalCtxt::validate_alias_bound_self_from_param_env`] for more detail. |
| #[instrument(level = "debug", skip_all)] |
| fn assemble_alias_bound_candidates_for_builtin_impl_default_items<G: GoalKind<'tcx>>( |
| &mut self, |
| 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()); |
| |
| // You probably shouldn't add anything to this list unless you |
| // know what you're doing. |
| let result = if lang_items.pointee_trait() == Some(trait_def_id) { |
| G::consider_builtin_pointee_candidate(self, goal) |
| } else if lang_items.discriminant_kind_trait() == Some(trait_def_id) { |
| G::consider_builtin_discriminant_kind_candidate(self, goal) |
| } else { |
| Err(NoSolution) |
| }; |
| |
| match result { |
| Ok(result) => candidates.push(Candidate { |
| source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), |
| result, |
| }), |
| Err(NoSolution) => (), |
| } |
| } |
| |
| #[instrument(level = "debug", skip_all)] |
| fn assemble_object_bound_candidates<G: GoalKind<'tcx>>( |
| &mut self, |
| goal: Goal<'tcx, G>, |
| candidates: &mut Vec<Candidate<'tcx>>, |
| ) { |
| let tcx = self.tcx(); |
| if !tcx.trait_def(goal.predicate.trait_def_id(tcx)).implement_via_object { |
| return; |
| } |
| |
| let self_ty = goal.predicate.self_ty(); |
| let bounds = 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::Alias(..) |
| | ty::Closure(..) |
| | ty::Coroutine(..) |
| | ty::CoroutineWitness(..) |
| | ty::Never |
| | ty::Tuple(_) |
| | ty::Param(_) |
| | ty::Placeholder(..) |
| | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) |
| | ty::Error(_) => return, |
| ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) |
| | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"), |
| ty::Dynamic(bounds, ..) => bounds, |
| }; |
| |
| // 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; |
| } |
| |
| // 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)] |
| fn assemble_coherence_unknowable_candidates<G: GoalKind<'tcx>>( |
| &mut self, |
| goal: Goal<'tcx, G>, |
| candidates: &mut Vec<Candidate<'tcx>>, |
| ) { |
| let tcx = self.tcx(); |
| match self.solver_mode() { |
| SolverMode::Normal => return, |
| SolverMode::Coherence => {} |
| }; |
| |
| let result = self.probe_misc_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) => {} |
| } |
| } |
| |
| /// If there are multiple ways to prove a trait or projection goal, we have |
| /// to somehow try to merge the candidates into one. If that fails, we return |
| /// ambiguity. |
| #[instrument(level = "debug", skip(self), ret)] |
| pub(super) fn merge_candidates( |
| &mut self, |
| mut candidates: Vec<Candidate<'tcx>>, |
| ) -> QueryResult<'tcx> { |
| // First try merging all candidates. This is complete and fully sound. |
| let responses = candidates.iter().map(|c| c.result).collect::<Vec<_>>(); |
| if let Some(result) = self.try_merge_responses(&responses) { |
| return Ok(result); |
| } |
| |
| // We then check whether we should prioritize `ParamEnv` candidates. |
| // |
| // Doing so is incomplete and would therefore be unsound during coherence. |
| match self.solver_mode() { |
| SolverMode::Coherence => (), |
| // Prioritize `ParamEnv` candidates only if they do not guide inference. |
| // |
| // This is still incomplete as we may add incorrect region bounds. |
| SolverMode::Normal => { |
| let param_env_responses = candidates |
| .iter() |
| .filter(|c| { |
| matches!( |
| c.source, |
| CandidateSource::ParamEnv(_) | CandidateSource::AliasBound |
| ) |
| }) |
| .map(|c| c.result) |
| .collect::<Vec<_>>(); |
| if let Some(result) = self.try_merge_responses(¶m_env_responses) { |
| // We strongly prefer alias and param-env bounds here, even if they affect inference. |
| // See https://github.com/rust-lang/trait-system-refactor-initiative/issues/11. |
| return Ok(result); |
| } |
| } |
| } |
| self.flounder(&responses) |
| } |
| } |
