diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve/assembly')
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/assembly/mod.rs | 605 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs | 417 |
2 files changed, 1022 insertions, 0 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs new file mode 100644 index 000000000..10d817f75 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -0,0 +1,605 @@ +//! Code shared by trait and projection goals for candidate assembly. + +use super::search_graph::OverflowHandler; +use super::{EvalCtxt, SolverMode}; +use crate::solve::CanonicalResponseExt; +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_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult}; +use rustc_middle::ty::fast_reject::TreatProjections; +use rustc_middle::ty::TypeFoldable; +use rustc_middle::ty::{self, Ty, TyCtxt}; +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>, +} + +/// Possible ways the given goal can be proven. +#[derive(Debug, Clone, Copy)] +pub(super) enum CandidateSource { + /// A user written impl. + /// + /// ## Examples + /// + /// ```rust + /// fn main() { + /// let x: Vec<u32> = Vec::new(); + /// // This uses the impl from the standard library to prove `Vec<T>: Clone`. + /// let y = x.clone(); + /// } + /// ``` + Impl(DefId), + /// A builtin impl generated by the compiler. When adding a new special + /// trait, try to use actual impls whenever possible. Builtin impls should + /// only be used in cases where the impl cannot be manually be written. + /// + /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`. + /// For a list of all traits with builtin impls, check out the + /// [`EvalCtxt::assemble_builtin_impl_candidates`] method. Not + BuiltinImpl, + /// An assumption from the environment. + /// + /// More precicely we've used the `n-th` assumption in the `param_env`. + /// + /// ## Examples + /// + /// ```rust + /// fn is_clone<T: Clone>(x: T) -> (T, T) { + /// // This uses the assumption `T: Clone` from the `where`-bounds + /// // to prove `T: Clone`. + /// (x.clone(), x) + /// } + /// ``` + ParamEnv(usize), + /// If the self type is an alias type, e.g. an opaque type or a projection, + /// we know the bounds on that alias to hold even without knowing its concrete + /// underlying type. + /// + /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of + /// the self type. + /// + /// ## Examples + /// + /// ```rust + /// trait Trait { + /// type Assoc: Clone; + /// } + /// + /// fn foo<T: Trait>(x: <T as Trait>::Assoc) { + /// // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in + /// // in the trait definition. + /// let _y = x.clone(); + /// } + /// ``` + AliasBound, +} + +/// Methods used to assemble candidates for either trait or projection goals. +pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq { + fn self_ty(self) -> Ty<'tcx>; + + fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx>; + + fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self; + + fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId; + + // 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::Predicate<'tcx>, + requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>, + ) -> QueryResult<'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. + fn consider_object_bound_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + assumption: ty::Predicate<'tcx>, + ) -> QueryResult<'tcx>; + + fn consider_impl_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + 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`]. + 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 [`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`]. + 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 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. + 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( + 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( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> Vec<CanonicalResponse<'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>; +} + +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)); + + // 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 structually resolve the type one layer. + if goal.predicate.self_ty().is_ty_var() { + return vec![Candidate { + source: CandidateSource::BuiltinImpl, + result: self + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + .unwrap(), + }]; + } + + let mut candidates = Vec::new(); + + self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates); + + self.assemble_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); + + candidates + } + + /// If the self type of a goal is a projection, computing the relevant candidates is difficult. + /// + /// To deal with this, we first try to normalize the self type and add the candidates for the normalized + /// self type to the list of candidates in case that succeeds. We also have to consider candidates with the + /// projection as a self type as well + #[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>>, + ) { + let tcx = self.tcx(); + // FIXME: We also have to normalize opaque types, not sure where to best fit that in. + let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else { + return + }; + + let normalized_self_candidates: Result<_, NoSolution> = self.probe(|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, 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()?; + let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty); + // NOTE: Alternatively we could call `evaluate_goal` here and only + // have a `Normalized` candidate. This doesn't work as long as we + // use `CandidateSource` in winnowing. + let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty)); + Ok(ecx.assemble_and_evaluate_candidates(goal)) + }, + ) + }); + + if let Ok(normalized_self_candidates) = normalized_self_candidates { + candidates.extend(normalized_self_candidates); + } + } + + #[instrument(level = "debug", skip_all)] + fn assemble_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) { + 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 lang_items = self.tcx().lang_items(); + let trait_def_id = goal.predicate.trait_def_id(self.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 self.tcx().trait_is_auto(trait_def_id) { + G::consider_auto_trait_candidate(self, goal) + } else if self.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.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) { + 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, 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 in G::consider_builtin_dyn_upcast_candidates(self, goal) { + candidates.push(Candidate { source: CandidateSource::BuiltinImpl, 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::Generator(..) + | ty::GeneratorWitness(_) + | ty::GeneratorWitnessMIR(..) + | 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::Alias(_, alias_ty) => alias_ty, + }; + + for assumption in self.tcx().item_bounds(alias_ty.def_id).subst(self.tcx(), alias_ty.substs) + { + match G::consider_implied_clause(self, goal, assumption, []) { + Ok(result) => { + candidates.push(Candidate { source: CandidateSource::AliasBound, 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 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::Generator(..) + | ty::GeneratorWitness(_) + | ty::GeneratorWitnessMIR(..) + | 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, + }; + + let tcx = self.tcx(); + 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 intersections in responses. + if assumption.to_opt_poly_projection_pred().is_some() + && !own_bounds.contains(&assumption) + { + continue; + } + + match G::consider_object_bound_candidate(self, goal, assumption) { + Ok(result) => { + candidates.push(Candidate { source: CandidateSource::BuiltinImpl, 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>>, + ) { + 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, 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"), + }, + } + } + } + } + + /// 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(_))) + .map(|c| c.result) + .collect::<Vec<_>>(); + if let Some(result) = self.try_merge_responses(¶m_env_responses) { + if result.has_only_region_constraints() { + return Ok(result); + } + } + } + } + self.flounder(&responses) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs new file mode 100644 index 000000000..1a566e87d --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs @@ -0,0 +1,417 @@ +use rustc_data_structures::fx::FxHashMap; +use rustc_hir::{def_id::DefId, Movability, Mutability}; +use rustc_infer::traits::query::NoSolution; +use rustc_middle::ty::{ + self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, +}; + +use crate::solve::EvalCtxt; + +// Calculates the constituent types of a type for `auto trait` purposes. +// +// For types with an "existential" binder, i.e. generator witnesses, we also +// instantiate the binder with placeholders eagerly. +pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>( + ecx: &EvalCtxt<'_, 'tcx>, + ty: Ty<'tcx>, +) -> Result<Vec<Ty<'tcx>>, NoSolution> { + let tcx = ecx.tcx(); + match *ty.kind() { + ty::Uint(_) + | ty::Int(_) + | ty::Bool + | ty::Float(_) + | ty::FnDef(..) + | ty::FnPtr(_) + | ty::Error(_) + | ty::Never + | ty::Char => Ok(vec![]), + + // Treat `str` like it's defined as `struct str([u8]);` + ty::Str => Ok(vec![tcx.mk_slice(tcx.types.u8)]), + + ty::Dynamic(..) + | ty::Param(..) + | ty::Foreign(..) + | ty::Alias(ty::Projection, ..) + | ty::Placeholder(..) + | ty::Bound(..) + | ty::Infer(_) => { + bug!("unexpected type `{ty}`") + } + + ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => { + Ok(vec![element_ty]) + } + + ty::Array(element_ty, _) | ty::Slice(element_ty) => Ok(vec![element_ty]), + + ty::Tuple(ref tys) => { + // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet + Ok(tys.iter().collect()) + } + + ty::Closure(_, ref substs) => Ok(vec![substs.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::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), + + ty::GeneratorWitnessMIR(def_id, substs) => 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), + )) + }) + .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, substs) => Ok(def.all_fields().map(|f| f.ty(tcx, substs)).collect()), + + ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) => { + // 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)]) + } + } +} + +pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'tcx>( + tcx: TyCtxt<'tcx>, + ty: Ty<'tcx>, +) -> ty::Binder<'tcx, Ty<'tcx>> { + debug_assert!(!ty.has_late_bound_regions()); + let mut counter = 0; + let ty = tcx.fold_regions(ty, |mut r, current_depth| { + if let ty::ReErased = r.kind() { + let br = + ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon(None) }; + counter += 1; + r = tcx.mk_re_late_bound(current_depth, br); + } + r + }); + let bound_vars = tcx.mk_bound_variable_kinds_from_iter( + (0..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon(None))), + ); + ty::Binder::bind_with_vars(ty, bound_vars) +} + +pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>( + ecx: &EvalCtxt<'_, 'tcx>, + ty: Ty<'tcx>, +) -> Result<Vec<Ty<'tcx>>, NoSolution> { + match *ty.kind() { + ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) + | ty::Uint(_) + | ty::Int(_) + | ty::Bool + | ty::Float(_) + | ty::FnDef(..) + | ty::FnPtr(_) + | ty::RawPtr(..) + | ty::Char + | ty::Ref(..) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::GeneratorWitnessMIR(..) + | ty::Array(..) + | ty::Closure(..) + | ty::Never + | ty::Dynamic(_, _, ty::DynStar) + | ty::Error(_) => Ok(vec![]), + + ty::Str + | ty::Slice(_) + | ty::Dynamic(..) + | ty::Foreign(..) + | ty::Alias(..) + | ty::Param(_) + | ty::Placeholder(..) => Err(NoSolution), + + ty::Bound(..) + | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { + bug!("unexpected type `{ty}`") + } + + ty::Tuple(tys) => Ok(tys.to_vec()), + + ty::Adt(def, substs) => { + let sized_crit = def.sized_constraint(ecx.tcx()); + Ok(sized_crit + .0 + .iter() + .map(|ty| sized_crit.rebind(*ty).subst(ecx.tcx(), substs)) + .collect()) + } + } +} + +pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( + ecx: &EvalCtxt<'_, '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![]), + + // Implementations are provided in core + ty::Uint(_) + | ty::Int(_) + | ty::Bool + | ty::Float(_) + | ty::Char + | ty::RawPtr(..) + | ty::Never + | ty::Ref(_, _, Mutability::Not) + | ty::Array(..) => Err(NoSolution), + + ty::Dynamic(..) + | ty::Str + | ty::Slice(_) + | ty::Generator(_, _, Movability::Static) + | ty::Foreign(..) + | ty::Ref(_, _, Mutability::Mut) + | ty::Adt(_, _) + | ty::Alias(_, _) + | ty::Param(_) + | ty::Placeholder(..) => Err(NoSolution), + + ty::Bound(..) + | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { + bug!("unexpected type `{ty}`") + } + + ty::Tuple(tys) => Ok(tys.to_vec()), + + ty::Closure(_, substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]), + + ty::Generator(_, substs, Movability::Movable) => { + if ecx.tcx().features().generator_clone { + let generator = substs.as_generator(); + Ok(vec![generator.tupled_upvars_ty(), generator.witness()]) + } else { + Err(NoSolution) + } + } + + ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), + + ty::GeneratorWitnessMIR(def_id, substs) => 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), + )) + }) + .collect()), + } +} + +// Returns a binder of the tupled inputs types and output type from a builtin callable type. +pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>( + tcx: TyCtxt<'tcx>, + self_ty: Ty<'tcx>, + goal_kind: ty::ClosureKind, +) -> 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) => { + let sig = tcx.fn_sig(def_id); + if sig.skip_binder().is_fn_trait_compatible() + && tcx.codegen_fn_attrs(def_id).target_features.is_empty() + { + Ok(Some( + sig.subst(tcx, substs) + .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())), + )) + } else { + Err(NoSolution) + } + } + // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed. + ty::FnPtr(sig) => { + if sig.is_fn_trait_compatible() { + Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())))) + } else { + Err(NoSolution) + } + } + ty::Closure(_, substs) => { + let closure_substs = substs.as_closure(); + match closure_substs.kind_ty().to_opt_closure_kind() { + // If the closure's kind doesn't extend the goal kind, + // then the closure doesn't implement the trait. + Some(closure_kind) => { + if !closure_kind.extends(goal_kind) { + return Err(NoSolution); + } + } + // Closure kind is not yet determined, so we return ambiguity unless + // the expected kind is `FnOnce` as that is always implemented. + None => { + if goal_kind != ty::ClosureKind::FnOnce { + return Ok(None); + } + } + } + Ok(Some(closure_substs.sig().map_bound(|sig| (sig.inputs()[0], sig.output())))) + } + 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::Dynamic(_, _, _) + | ty::Generator(_, _, _) + | ty::GeneratorWitness(_) + | ty::GeneratorWitnessMIR(..) + | ty::Never + | ty::Tuple(_) + | ty::Alias(_, _) + | ty::Param(_) + | ty::Placeholder(..) + | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) + | ty::Error(_) => Err(NoSolution), + + ty::Bound(..) + | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { + bug!("unexpected type `{self_ty}`") + } + } +} + +/// Assemble a list of predicates that would be present on a theoretical +/// user impl for an object type. These predicates must be checked any time +/// we assemble a built-in object candidate for an object type, since they +/// are not implied by the well-formedness of the type. +/// +/// For example, given the following traits: +/// +/// ```rust,ignore (theoretical code) +/// trait Foo: Baz { +/// type Bar: Copy; +/// } +/// +/// trait Baz {} +/// ``` +/// +/// For the dyn type `dyn Foo<Item = Ty>`, we can imagine there being a +/// pair of theoretical impls: +/// +/// ```rust,ignore (theoretical code) +/// impl Foo for dyn Foo<Item = Ty> +/// where +/// Self: Baz, +/// <Self as Foo>::Bar: Copy, +/// { +/// type Bar = Ty; +/// } +/// +/// impl Baz for dyn Foo<Item = Ty> {} +/// ``` +/// +/// However, in order to make such impls well-formed, we need to do an +/// additional step of eagerly folding the associated types in the where +/// clauses of the impl. In this example, that means replacing +/// `<Self as Foo>::Bar` with `Ty` in the first impl. +/// +// FIXME: This is only necessary as `<Self as Trait>::Assoc: ItemBound` +// bounds in impls are trivially proven using the item bound candidates. +// This is unsound in general and once that is fixed, we don't need to +// normalize eagerly here. See https://github.com/lcnr/solver-woes/issues/9 +// for more details. +pub(in crate::solve) fn predicates_for_object_candidate<'tcx>( + ecx: &EvalCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + trait_ref: ty::TraitRef<'tcx>, + object_bound: &'tcx ty::List<ty::PolyExistentialPredicate<'tcx>>, +) -> Vec<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, + ); + 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(tcx, trait_ref.substs)); + } + } + + let mut replace_projection_with = FxHashMap::default(); + for bound in object_bound { + if let ty::ExistentialPredicate::Projection(proj) = bound.skip_binder() { + let proj = proj.with_self_ty(tcx, trait_ref.self_ty()); + let old_ty = replace_projection_with.insert(proj.def_id(), bound.rebind(proj)); + assert_eq!( + old_ty, + None, + "{} has two substitutions: {} and {}", + proj.projection_ty, + proj.term, + old_ty.unwrap() + ); + } + } + + requirements.fold_with(&mut ReplaceProjectionWith { + ecx, + param_env, + mapping: replace_projection_with, + }) +} + +struct ReplaceProjectionWith<'a, 'tcx> { + ecx: &'a EvalCtxt<'a, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + mapping: FxHashMap<DefId, ty::PolyProjectionPredicate<'tcx>>, +} + +impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceProjectionWith<'_, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { + self.ecx.tcx() + } + + fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { + if let ty::Alias(ty::Projection, alias_ty) = *ty.kind() + && let Some(replacement) = self.mapping.get(&alias_ty.def_id) + { + // We may have a case where our object type's projection bound is higher-ranked, + // 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"); + proj.term.ty().unwrap() + } else { + ty.super_fold_with(self) + } + } +} |