diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve')
13 files changed, 2428 insertions, 708 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs index 31c1bc9ec..dec9f8016 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly.rs @@ -1,7 +1,9 @@ //! Code shared by trait and projection goals for candidate assembly. -use super::infcx_ext::InferCtxtExt; +#[cfg(doc)] +use super::trait_goals::structural_traits::*; use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, MaybeCause, QueryResult}; +use itertools::Itertools; use rustc_hir::def_id::DefId; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::util::elaborate_predicates; @@ -76,63 +78,135 @@ pub(super) enum CandidateSource { /// let _y = x.clone(); /// } /// ``` - AliasBound(usize), + AliasBound, } -pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy + Eq { +/// 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 with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self; fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId; - fn consider_impl_candidate( + // 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>, - impl_def_id: DefId, + assumption: ty::Predicate<'tcx>, + requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>, ) -> QueryResult<'tcx>; - fn consider_assumption( + // 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>; - fn consider_builtin_pointer_sized_candidate( + // 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 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>; } impl<'tcx> EvalCtxt<'_, 'tcx> { @@ -140,7 +214,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { &mut self, goal: Goal<'tcx, G>, ) -> Vec<Candidate<'tcx>> { - debug_assert_eq!(goal, self.infcx.resolve_vars_if_possible(goal)); + 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 @@ -148,9 +222,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if goal.predicate.self_ty().is_ty_var() { return vec![Candidate { source: CandidateSource::BuiltinImpl, - result: self - .make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity)) - .unwrap(), + result: self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(), }]; } @@ -186,8 +258,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else { return }; - self.infcx.probe(|_| { - let normalized_ty = self.infcx.next_ty_infer(); + self.probe(|this| { + let normalized_ty = this.next_ty_infer(); let normalizes_to_goal = goal.with( tcx, ty::Binder::dummy(ty::ProjectionPredicate { @@ -195,18 +267,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { term: normalized_ty.into(), }), ); - let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) { + let normalization_certainty = match this.evaluate_goal(normalizes_to_goal) { Ok((_, certainty)) => certainty, Err(NoSolution) => return, }; - let normalized_ty = self.infcx.resolve_vars_if_possible(normalized_ty); + let normalized_ty = this.resolve_vars_if_possible(normalized_ty); // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate. // This doesn't work as long as we use `CandidateSource` in winnowing. let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty)); - // FIXME: This is broken if we care about the `usize` of `AliasBound` because the self type - // could be normalized to yet another projection with different item bounds. - let normalized_candidates = self.assemble_and_evaluate_candidates(goal); + let normalized_candidates = this.assemble_and_evaluate_candidates(goal); for mut normalized_candidate in normalized_candidates { normalized_candidate.result = normalized_candidate.result.unchecked_map(|mut response| { @@ -255,12 +325,22 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { || lang_items.clone_trait() == Some(trait_def_id) { G::consider_builtin_copy_clone_candidate(self, goal) - } else if lang_items.pointer_sized() == Some(trait_def_id) { - G::consider_builtin_pointer_sized_candidate(self, goal) + } else if lang_items.pointer_like() == Some(trait_def_id) { + G::consider_builtin_pointer_like_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 { Err(NoSolution) }; @@ -271,6 +351,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } 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 }); + } + } } fn assemble_param_env_candidates<G: GoalKind<'tcx>>( @@ -279,7 +367,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { candidates: &mut Vec<Candidate<'tcx>>, ) { for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() { - match G::consider_assumption(self, goal, assumption) { + match G::consider_implied_clause(self, goal, assumption, []) { Ok(result) => { candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result }) } @@ -312,25 +400,23 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::Closure(..) | ty::Generator(..) | ty::GeneratorWitness(_) + | ty::GeneratorWitnessMIR(..) | ty::Never | ty::Tuple(_) | ty::Param(_) | ty::Placeholder(..) - | ty::Infer(_) + | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) | ty::Error(_) => return, - ty::Bound(..) => bug!("unexpected bound type: {goal:?}"), + 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 (i, (assumption, _)) in self - .tcx() - .bound_explicit_item_bounds(alias_ty.def_id) - .subst_iter_copied(self.tcx(), alias_ty.substs) - .enumerate() + for assumption in self.tcx().item_bounds(alias_ty.def_id).subst(self.tcx(), alias_ty.substs) { - match G::consider_assumption(self, goal, assumption) { + match G::consider_implied_clause(self, goal, assumption, []) { Ok(result) => { - candidates.push(Candidate { source: CandidateSource::AliasBound(i), result }) + candidates.push(Candidate { source: CandidateSource::AliasBound, result }) } Err(NoSolution) => (), } @@ -362,13 +448,15 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::Closure(..) | ty::Generator(..) | ty::GeneratorWitness(_) + | ty::GeneratorWitnessMIR(..) | ty::Never | ty::Tuple(_) | ty::Param(_) | ty::Placeholder(..) - | ty::Infer(_) + | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) | ty::Error(_) => return, - ty::Bound(..) => bug!("unexpected bound type: {goal:?}"), + ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) + | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"), ty::Dynamic(bounds, ..) => bounds, }; @@ -376,7 +464,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { for assumption in elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty))) { - match G::consider_assumption(self, goal, assumption.predicate) { + match G::consider_object_bound_candidate(self, goal, assumption.predicate) { Ok(result) => { candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) } @@ -384,4 +472,79 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } } + + #[instrument(level = "debug", skip(self), ret)] + pub(super) fn merge_candidates_and_discard_reservation_impls( + &mut self, + mut candidates: Vec<Candidate<'tcx>>, + ) -> QueryResult<'tcx> { + match candidates.len() { + 0 => return Err(NoSolution), + 1 => return Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result), + _ => {} + } + + if candidates.len() > 1 { + let mut i = 0; + 'outer: while i < candidates.len() { + for j in (0..candidates.len()).filter(|&j| i != j) { + if self.trait_candidate_should_be_dropped_in_favor_of( + &candidates[i], + &candidates[j], + ) { + debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len()); + candidates.swap_remove(i); + continue 'outer; + } + } + + debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len()); + i += 1; + } + + // If there are *STILL* multiple candidates that have *different* response + // results, give up and report ambiguity. + if candidates.len() > 1 && !candidates.iter().map(|cand| cand.result).all_equal() { + let certainty = if candidates.iter().all(|x| { + matches!(x.result.value.certainty, Certainty::Maybe(MaybeCause::Overflow)) + }) { + Certainty::Maybe(MaybeCause::Overflow) + } else { + Certainty::AMBIGUOUS + }; + return self.make_canonical_response(certainty); + } + } + + // FIXME: What if there are >1 candidates left with the same response, and one is a reservation impl? + Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result) + } + + fn trait_candidate_should_be_dropped_in_favor_of( + &self, + candidate: &Candidate<'tcx>, + other: &Candidate<'tcx>, + ) -> bool { + // FIXME: implement this + match (candidate.source, other.source) { + (CandidateSource::Impl(_), _) + | (CandidateSource::ParamEnv(_), _) + | (CandidateSource::AliasBound, _) + | (CandidateSource::BuiltinImpl, _) => false, + } + } + + fn discard_reservation_impl(&self, mut candidate: Candidate<'tcx>) -> Candidate<'tcx> { + if let CandidateSource::Impl(def_id) = candidate.source { + if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) { + debug!("Selected reservation impl"); + // We assemble all candidates inside of a probe so by + // making a new canonical response here our result will + // have no constraints. + candidate.result = self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(); + } + } + + candidate + } } diff --git a/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs new file mode 100644 index 000000000..c048d4a2a --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs @@ -0,0 +1,390 @@ +use std::cmp::Ordering; + +use crate::infer::InferCtxt; +use rustc_middle::infer::canonical::Canonical; +use rustc_middle::infer::canonical::CanonicalTyVarKind; +use rustc_middle::infer::canonical::CanonicalVarInfo; +use rustc_middle::infer::canonical::CanonicalVarInfos; +use rustc_middle::infer::canonical::CanonicalVarKind; +use rustc_middle::ty::BoundRegionKind::BrAnon; +use rustc_middle::ty::BoundTyKind; +use rustc_middle::ty::TyCtxt; +use rustc_middle::ty::TypeVisitableExt; +use rustc_middle::ty::{self, Ty}; +use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable}; + +/// Whether we're canonicalizing a query input or the query reponse. +/// +/// When canonicalizing an input we're in the context of the caller +/// while canonicalizing the response happens in the context of the +/// query. +#[derive(Debug, Clone, Copy)] +pub enum CanonicalizeMode { + Input, + /// FIXME: We currently return region constraints refering to + /// placeholders and inference variables from a binder instantiated + /// inside of the query. + /// + /// In the long term we should eagerly deal with these constraints + /// inside of the query and only propagate constraints which are + /// actually nameable by the caller. + Response { + /// The highest universe nameable by the caller. + /// + /// All variables in a universe nameable by the caller get mapped + /// to the root universe in the response and then mapped back to + /// their correct universe when applying the query response in the + /// context of the caller. + /// + /// This doesn't work for universes created inside of the query so + /// we do remember their universe in the response. + max_input_universe: ty::UniverseIndex, + }, +} + +pub struct Canonicalizer<'a, 'tcx> { + infcx: &'a InferCtxt<'tcx>, + canonicalize_mode: CanonicalizeMode, + + variables: &'a mut Vec<ty::GenericArg<'tcx>>, + primitive_var_infos: Vec<CanonicalVarInfo<'tcx>>, + binder_index: ty::DebruijnIndex, +} + +impl<'a, 'tcx> Canonicalizer<'a, 'tcx> { + #[instrument(level = "debug", skip(infcx), ret)] + pub fn canonicalize<T: TypeFoldable<TyCtxt<'tcx>>>( + infcx: &'a InferCtxt<'tcx>, + canonicalize_mode: CanonicalizeMode, + variables: &'a mut Vec<ty::GenericArg<'tcx>>, + value: T, + ) -> Canonical<'tcx, T> { + let mut canonicalizer = Canonicalizer { + infcx, + canonicalize_mode, + + variables, + primitive_var_infos: Vec::new(), + binder_index: ty::INNERMOST, + }; + + let value = value.fold_with(&mut canonicalizer); + assert!(!value.needs_infer()); + assert!(!value.has_placeholders()); + + let (max_universe, variables) = canonicalizer.finalize(); + + Canonical { max_universe, variables, value } + } + + fn finalize(self) -> (ty::UniverseIndex, CanonicalVarInfos<'tcx>) { + let mut var_infos = self.primitive_var_infos; + // See the rustc-dev-guide section about how we deal with universes + // during canonicalization in the new solver. + match self.canonicalize_mode { + // We try to deduplicate as many query calls as possible and hide + // all information which should not matter for the solver. + // + // For this we compress universes as much as possible. + CanonicalizeMode::Input => {} + // When canonicalizing a response we map a universes already entered + // by the caller to the root universe and only return useful universe + // information for placeholders and inference variables created inside + // of the query. + CanonicalizeMode::Response { max_input_universe } => { + for var in var_infos.iter_mut() { + let uv = var.universe(); + let new_uv = ty::UniverseIndex::from( + uv.index().saturating_sub(max_input_universe.index()), + ); + *var = var.with_updated_universe(new_uv); + } + let max_universe = var_infos + .iter() + .map(|info| info.universe()) + .max() + .unwrap_or(ty::UniverseIndex::ROOT); + + let var_infos = self.infcx.tcx.mk_canonical_var_infos(&var_infos); + return (max_universe, var_infos); + } + } + + // Given a `var_infos` with existentials `En` and universals `Un` in + // universes `n`, this algorithm compresses them in place so that: + // + // - the new universe indices are as small as possible + // - we only create a new universe if we would otherwise put a placeholder in + // the same compressed universe as an existential which cannot name it + // + // Let's walk through an example: + // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 0 + // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 0, next_orig_uv: 1 + // - var_infos: [E0, U1, E5, U2, E2, E6, U6], curr_compressed_uv: 1, next_orig_uv: 2 + // - var_infos: [E0, U1, E5, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 5 + // - var_infos: [E0, U1, E1, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 6 + // - var_infos: [E0, U1, E1, U1, E1, E2, U2], curr_compressed_uv: 2, next_orig_uv: - + // + // This algorithm runs in `O(n²)` where `n` is the number of different universe + // indices in the input. This should be fine as `n` is expected to be small. + let mut curr_compressed_uv = ty::UniverseIndex::ROOT; + let mut existential_in_new_uv = false; + let mut next_orig_uv = Some(ty::UniverseIndex::ROOT); + while let Some(orig_uv) = next_orig_uv.take() { + let mut update_uv = |var: &mut CanonicalVarInfo<'tcx>, orig_uv, is_existential| { + let uv = var.universe(); + match uv.cmp(&orig_uv) { + Ordering::Less => (), // Already updated + Ordering::Equal => { + if is_existential { + existential_in_new_uv = true; + } else if existential_in_new_uv { + // `var` is a placeholder from a universe which is not nameable + // by an existential which we already put into the compressed + // universe `curr_compressed_uv`. We therefore have to create a + // new universe for `var`. + curr_compressed_uv = curr_compressed_uv.next_universe(); + existential_in_new_uv = false; + } + + *var = var.with_updated_universe(curr_compressed_uv); + } + Ordering::Greater => { + // We can ignore this variable in this iteration. We only look at + // universes which actually occur in the input for performance. + // + // For this we set `next_orig_uv` to the next smallest, not yet compressed, + // universe of the input. + if next_orig_uv.map_or(true, |curr_next_uv| uv.cannot_name(curr_next_uv)) { + next_orig_uv = Some(uv); + } + } + } + }; + + // For each universe which occurs in the input, we first iterate over all + // placeholders and then over all inference variables. + // + // Whenever we compress the universe of a placeholder, no existential with + // an already compressed universe can name that placeholder. + for is_existential in [false, true] { + for var in var_infos.iter_mut() { + // We simply put all regions from the input into the highest + // compressed universe, so we only deal with them at the end. + if !var.is_region() { + if is_existential == var.is_existential() { + update_uv(var, orig_uv, is_existential) + } + } + } + } + } + + for var in var_infos.iter_mut() { + if var.is_region() { + assert!(var.is_existential()); + *var = var.with_updated_universe(curr_compressed_uv); + } + } + + let var_infos = self.infcx.tcx.mk_canonical_var_infos(&var_infos); + (curr_compressed_uv, var_infos) + } +} + +impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T> + where + T: TypeFoldable<TyCtxt<'tcx>>, + { + self.binder_index.shift_in(1); + let t = t.super_fold_with(self); + self.binder_index.shift_out(1); + t + } + + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + let r = self.infcx.shallow_resolve(r); + let kind = match *r { + ty::ReLateBound(..) => return r, + + ty::ReStatic => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => return r, + }, + + ty::ReErased | ty::ReFree(_) | ty::ReEarlyBound(_) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => bug!("unexpected region in response: {r:?}"), + }, + + ty::RePlaceholder(placeholder) => match self.canonicalize_mode { + // We canonicalize placeholder regions as existentials in query inputs. + CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { max_input_universe } => { + // If we have a placeholder region inside of a query, it must be from + // a new universe. + if max_input_universe.can_name(placeholder.universe) { + bug!("new placeholder in universe {max_input_universe:?}: {r:?}"); + } + CanonicalVarKind::PlaceholderRegion(placeholder) + } + }, + + ty::ReVar(_) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::Region(ty::UniverseIndex::ROOT), + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::Region(self.infcx.universe_of_region(r)) + } + }, + + ty::ReError(_) => return r, + }; + + let existing_bound_var = match self.canonicalize_mode { + CanonicalizeMode::Input => None, + CanonicalizeMode::Response { .. } => { + self.variables.iter().position(|&v| v == r.into()).map(ty::BoundVar::from) + } + }; + let var = existing_bound_var.unwrap_or_else(|| { + let var = ty::BoundVar::from(self.variables.len()); + self.variables.push(r.into()); + self.primitive_var_infos.push(CanonicalVarInfo { kind }); + var + }); + let br = ty::BoundRegion { var, kind: BrAnon(var.as_u32(), None) }; + self.interner().mk_re_late_bound(self.binder_index, br) + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + let kind = match *t.kind() { + ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) { + Ok(t) => return self.fold_ty(t), + Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)), + }, + ty::Infer(ty::IntVar(_)) => { + let nt = self.infcx.shallow_resolve(t); + if nt != t { + return self.fold_ty(nt); + } else { + CanonicalVarKind::Ty(CanonicalTyVarKind::Int) + } + } + ty::Infer(ty::FloatVar(_)) => { + let nt = self.infcx.shallow_resolve(t); + if nt != t { + return self.fold_ty(nt); + } else { + CanonicalVarKind::Ty(CanonicalTyVarKind::Int) + } + } + ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { + bug!("fresh var during canonicalization: {t:?}") + } + ty::Placeholder(placeholder) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder { + universe: placeholder.universe, + name: BoundTyKind::Anon(self.variables.len() as u32), + }), + CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder), + }, + ty::Param(_) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder { + universe: ty::UniverseIndex::ROOT, + name: ty::BoundTyKind::Anon(self.variables.len() as u32), + }), + CanonicalizeMode::Response { .. } => bug!("param ty in response: {t:?}"), + }, + 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::Alias(_, _) + | ty::Bound(_, _) + | ty::Error(_) => return t.super_fold_with(self), + }; + + let var = ty::BoundVar::from( + self.variables.iter().position(|&v| v == t.into()).unwrap_or_else(|| { + let var = self.variables.len(); + self.variables.push(t.into()); + self.primitive_var_infos.push(CanonicalVarInfo { kind }); + var + }), + ); + let bt = ty::BoundTy { var, kind: BoundTyKind::Anon(var.index() as u32) }; + self.interner().mk_bound(self.binder_index, bt) + } + + fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { + let kind = match c.kind() { + ty::ConstKind::Infer(ty::InferConst::Var(vid)) => match self.infcx.probe_const_var(vid) + { + Ok(c) => return self.fold_const(c), + Err(universe) => CanonicalVarKind::Const(universe, c.ty()), + }, + ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => { + bug!("fresh var during canonicalization: {c:?}") + } + ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst( + ty::Placeholder { + universe: placeholder.universe, + name: ty::BoundVar::from(self.variables.len()), + }, + c.ty(), + ), + CanonicalizeMode::Response { .. } => { + CanonicalVarKind::PlaceholderConst(placeholder, c.ty()) + } + }, + ty::ConstKind::Param(_) => match self.canonicalize_mode { + CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst( + ty::Placeholder { + universe: ty::UniverseIndex::ROOT, + name: ty::BoundVar::from(self.variables.len()), + }, + c.ty(), + ), + CanonicalizeMode::Response { .. } => bug!("param ty in response: {c:?}"), + }, + ty::ConstKind::Bound(_, _) + | ty::ConstKind::Unevaluated(_) + | ty::ConstKind::Value(_) + | ty::ConstKind::Error(_) + | ty::ConstKind::Expr(_) => return c.super_fold_with(self), + }; + + let var = ty::BoundVar::from( + self.variables.iter().position(|&v| v == c.into()).unwrap_or_else(|| { + let var = self.variables.len(); + self.variables.push(c.into()); + self.primitive_var_infos.push(CanonicalVarInfo { kind }); + var + }), + ); + self.interner().mk_const(ty::ConstKind::Bound(self.binder_index, var), c.ty()) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs b/compiler/rustc_trait_selection/src/solve/canonical/mod.rs new file mode 100644 index 000000000..8c3be8da1 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/canonical/mod.rs @@ -0,0 +1,240 @@ +/// Canonicalization is used to separate some goal from its context, +/// throwing away unnecessary information in the process. +/// +/// This is necessary to cache goals containing inference variables +/// and placeholders without restricting them to the current `InferCtxt`. +/// +/// Canonicalization is fairly involved, for more details see the relevant +/// section of the [rustc-dev-guide][c]. +/// +/// [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html +use self::canonicalize::{CanonicalizeMode, Canonicalizer}; +use super::{CanonicalGoal, Certainty, EvalCtxt, Goal}; +use super::{CanonicalResponse, ExternalConstraints, QueryResult, Response}; +use rustc_infer::infer::canonical::query_response::make_query_region_constraints; +use rustc_infer::infer::canonical::CanonicalVarValues; +use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints}; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::solve::ExternalConstraintsData; +use rustc_infer::traits::ObligationCause; +use rustc_middle::ty::{self, GenericArgKind}; +use rustc_span::DUMMY_SP; +use std::iter; +use std::ops::Deref; + +mod canonicalize; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + /// Canonicalizes the goal remembering the original values + /// for each bound variable. + pub(super) fn canonicalize_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> (Vec<ty::GenericArg<'tcx>>, CanonicalGoal<'tcx>) { + let mut orig_values = Default::default(); + let canonical_goal = Canonicalizer::canonicalize( + self.infcx, + CanonicalizeMode::Input, + &mut orig_values, + goal, + ); + (orig_values, canonical_goal) + } + + /// To return the constraints of a canonical query to the caller, we canonicalize: + /// + /// - `var_values`: a map from bound variables in the canonical goal to + /// the values inferred while solving the instantiated goal. + /// - `external_constraints`: additional constraints which aren't expressable + /// using simple unification of inference variables. + #[instrument(level = "debug", skip(self))] + pub(super) fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> { + let external_constraints = self.compute_external_query_constraints()?; + + let response = Response { var_values: self.var_values, external_constraints, certainty }; + let canonical = Canonicalizer::canonicalize( + self.infcx, + CanonicalizeMode::Response { max_input_universe: self.max_input_universe }, + &mut Default::default(), + response, + ); + Ok(canonical) + } + + #[instrument(level = "debug", skip(self), ret)] + fn compute_external_query_constraints(&self) -> Result<ExternalConstraints<'tcx>, NoSolution> { + // Cannot use `take_registered_region_obligations` as we may compute the response + // inside of a `probe` whenever we have multiple choices inside of the solver. + let region_obligations = self.infcx.inner.borrow().region_obligations().to_owned(); + let region_constraints = self.infcx.with_region_constraints(|region_constraints| { + make_query_region_constraints( + self.tcx(), + region_obligations + .iter() + .map(|r_o| (r_o.sup_type, r_o.sub_region, r_o.origin.to_constraint_category())), + region_constraints, + ) + }); + let opaque_types = self.infcx.clone_opaque_types_for_query_response(); + Ok(self + .tcx() + .mk_external_constraints(ExternalConstraintsData { region_constraints, opaque_types })) + } + + /// After calling a canonical query, we apply the constraints returned + /// by the query using this function. + /// + /// This happens in three steps: + /// - we instantiate the bound variables of the query response + /// - we unify the `var_values` of the response with the `original_values` + /// - we apply the `external_constraints` returned by the query + pub(super) fn instantiate_and_apply_query_response( + &mut self, + param_env: ty::ParamEnv<'tcx>, + original_values: Vec<ty::GenericArg<'tcx>>, + response: CanonicalResponse<'tcx>, + ) -> Result<Certainty, NoSolution> { + let substitution = self.compute_query_response_substitution(&original_values, &response); + + let Response { var_values, external_constraints, certainty } = + response.substitute(self.tcx(), &substitution); + + self.unify_query_var_values(param_env, &original_values, var_values)?; + + // FIXME: implement external constraints. + let ExternalConstraintsData { region_constraints, opaque_types: _ } = + external_constraints.deref(); + self.register_region_constraints(region_constraints); + + Ok(certainty) + } + + /// This returns the substitutions to instantiate the bound variables of + /// the canonical reponse. This depends on the `original_values` for the + /// bound variables. + fn compute_query_response_substitution( + &self, + original_values: &[ty::GenericArg<'tcx>], + response: &CanonicalResponse<'tcx>, + ) -> CanonicalVarValues<'tcx> { + // FIXME: Longterm canonical queries should deal with all placeholders + // created inside of the query directly instead of returning them to the + // caller. + let prev_universe = self.infcx.universe(); + let universes_created_in_query = response.max_universe.index() + 1; + for _ in 0..universes_created_in_query { + self.infcx.create_next_universe(); + } + + let var_values = response.value.var_values; + assert_eq!(original_values.len(), var_values.len()); + + // If the query did not make progress with constraining inference variables, + // we would normally create a new inference variables for bound existential variables + // only then unify this new inference variable with the inference variable from + // the input. + // + // We therefore instantiate the existential variable in the canonical response with the + // inference variable of the input right away, which is more performant. + let mut opt_values = vec![None; response.variables.len()]; + for (original_value, result_value) in iter::zip(original_values, var_values.var_values) { + match result_value.unpack() { + GenericArgKind::Type(t) => { + if let &ty::Bound(debruijn, b) = t.kind() { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[b.var.index()] = Some(*original_value); + } + } + GenericArgKind::Lifetime(r) => { + if let ty::ReLateBound(debruijn, br) = *r { + assert_eq!(debruijn, ty::INNERMOST); + opt_values[br.var.index()] = Some(*original_value); + } + } + GenericArgKind::Const(c) => { + if let ty::ConstKind::Bound(debrujin, b) = c.kind() { + assert_eq!(debrujin, ty::INNERMOST); + opt_values[b.index()] = Some(*original_value); + } + } + } + } + + let var_values = self.tcx().mk_substs_from_iter(response.variables.iter().enumerate().map( + |(index, info)| { + if info.universe() != ty::UniverseIndex::ROOT { + // A variable from inside a binder of the query. While ideally these shouldn't + // exist at all (see the FIXME at the start of this method), we have to deal with + // them for now. + self.infcx.instantiate_canonical_var(DUMMY_SP, info, |idx| { + ty::UniverseIndex::from(prev_universe.index() + idx.index()) + }) + } else if info.is_existential() { + // As an optimization we sometimes avoid creating a new inference variable here. + // + // All new inference variables we create start out in the current universe of the caller. + // This is conceptionally wrong as these inference variables would be able to name + // more placeholders then they should be able to. However the inference variables have + // to "come from somewhere", so by equating them with the original values of the caller + // later on, we pull them down into their correct universe again. + if let Some(v) = opt_values[index] { + v + } else { + self.infcx.instantiate_canonical_var(DUMMY_SP, info, |_| prev_universe) + } + } else { + // For placeholders which were already part of the input, we simply map this + // universal bound variable back the placeholder of the input. + original_values[info.expect_anon_placeholder() as usize] + } + }, + )); + + CanonicalVarValues { var_values } + } + + #[instrument(level = "debug", skip(self, param_env), ret)] + fn unify_query_var_values( + &self, + param_env: ty::ParamEnv<'tcx>, + original_values: &[ty::GenericArg<'tcx>], + var_values: CanonicalVarValues<'tcx>, + ) -> Result<(), NoSolution> { + assert_eq!(original_values.len(), var_values.len()); + for (&orig, response) in iter::zip(original_values, var_values.var_values) { + // This can fail due to the occurs check, see + // `tests/ui/typeck/lazy-norm/equating-projection-cyclically.rs` for an example + // where that can happen. + // + // FIXME: To deal with #105787 I also expect us to emit nested obligations here at + // some point. We can figure out how to deal with this once we actually have + // an ICE. + let nested_goals = self.eq(param_env, orig, response)?; + assert!(nested_goals.is_empty(), "{nested_goals:?}"); + } + + Ok(()) + } + + fn register_region_constraints(&mut self, region_constraints: &QueryRegionConstraints<'tcx>) { + for &(ty::OutlivesPredicate(lhs, rhs), _) in ®ion_constraints.outlives { + match lhs.unpack() { + GenericArgKind::Lifetime(lhs) => self.infcx.region_outlives_predicate( + &ObligationCause::dummy(), + ty::Binder::dummy(ty::OutlivesPredicate(lhs, rhs)), + ), + GenericArgKind::Type(lhs) => self.infcx.register_region_obligation_with_cause( + lhs, + rhs, + &ObligationCause::dummy(), + ), + GenericArgKind::Const(_) => bug!("const outlives: {lhs:?}: {rhs:?}"), + } + } + + for member_constraint in ®ion_constraints.member_constraints { + // FIXME: Deal with member constraints :< + let _ = member_constraint; + } + } +} diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs new file mode 100644 index 000000000..95612674e --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs @@ -0,0 +1,184 @@ +use rustc_hir::def_id::DefId; +use rustc_infer::infer::at::ToTrace; +use rustc_infer::infer::canonical::CanonicalVarValues; +use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; +use rustc_infer::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime}; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::ObligationCause; +use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; +use rustc_middle::ty::{ + self, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, + TypeVisitor, +}; +use rustc_span::DUMMY_SP; +use std::ops::ControlFlow; + +use super::search_graph::SearchGraph; +use super::Goal; + +pub struct EvalCtxt<'a, 'tcx> { + // FIXME: should be private. + pub(super) infcx: &'a InferCtxt<'tcx>, + pub(super) var_values: CanonicalVarValues<'tcx>, + /// The highest universe index nameable by the caller. + /// + /// When we enter a new binder inside of the query we create new universes + /// which the caller cannot name. We have to be careful with variables from + /// these new universes when creating the query response. + /// + /// Both because these new universes can prevent us from reaching a fixpoint + /// if we have a coinductive cycle and because that's the only way we can return + /// new placeholders to the caller. + pub(super) max_input_universe: ty::UniverseIndex, + + pub(super) search_graph: &'a mut SearchGraph<'tcx>, + + /// This field is used by a debug assertion in [`EvalCtxt::evaluate_goal`], + /// see the comment in that method for more details. + pub in_projection_eq_hack: bool, +} + +impl<'tcx> EvalCtxt<'_, 'tcx> { + pub(super) fn probe<T>(&mut self, f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> T) -> T { + self.infcx.probe(|_| f(self)) + } + + pub(super) fn tcx(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + pub(super) fn next_ty_infer(&self) -> Ty<'tcx> { + self.infcx.next_ty_var(TypeVariableOrigin { + kind: TypeVariableOriginKind::MiscVariable, + span: DUMMY_SP, + }) + } + + pub(super) fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx> { + self.infcx.next_const_var( + ty, + ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span: DUMMY_SP }, + ) + } + + /// Is the projection predicate is of the form `exists<T> <Ty as Trait>::Assoc = T`. + /// + /// This is the case if the `term` is an inference variable in the innermost universe + /// and does not occur in any other part of the predicate. + pub(super) fn term_is_fully_unconstrained( + &self, + goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + ) -> bool { + let term_is_infer = match goal.predicate.term.unpack() { + ty::TermKind::Ty(ty) => { + if let &ty::Infer(ty::TyVar(vid)) = ty.kind() { + match self.infcx.probe_ty_var(vid) { + Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), + Err(universe) => universe == self.universe(), + } + } else { + false + } + } + ty::TermKind::Const(ct) => { + if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.kind() { + match self.infcx.probe_const_var(vid) { + Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), + Err(universe) => universe == self.universe(), + } + } else { + false + } + } + }; + + // Guard against `<T as Trait<?0>>::Assoc = ?0>`. + struct ContainsTerm<'tcx> { + term: ty::Term<'tcx>, + } + impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsTerm<'tcx> { + type BreakTy = (); + fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { + if t.needs_infer() { + if ty::Term::from(t) == self.term { + ControlFlow::Break(()) + } else { + t.super_visit_with(self) + } + } else { + ControlFlow::Continue(()) + } + } + + fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { + if c.needs_infer() { + if ty::Term::from(c) == self.term { + ControlFlow::Break(()) + } else { + c.super_visit_with(self) + } + } else { + ControlFlow::Continue(()) + } + } + } + + let mut visitor = ContainsTerm { term: goal.predicate.term }; + + term_is_infer + && goal.predicate.projection_ty.visit_with(&mut visitor).is_continue() + && goal.param_env.visit_with(&mut visitor).is_continue() + } + + #[instrument(level = "debug", skip(self, param_env), ret)] + pub(super) fn eq<T: ToTrace<'tcx>>( + &self, + param_env: ty::ParamEnv<'tcx>, + lhs: T, + rhs: T, + ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .eq(lhs, rhs) + .map(|InferOk { value: (), obligations }| { + obligations.into_iter().map(|o| o.into()).collect() + }) + .map_err(|e| { + debug!(?e, "failed to equate"); + NoSolution + }) + } + + pub(super) fn instantiate_binder_with_infer<T: TypeFoldable<TyCtxt<'tcx>> + Copy>( + &self, + value: ty::Binder<'tcx, T>, + ) -> T { + self.infcx.instantiate_binder_with_fresh_vars( + DUMMY_SP, + LateBoundRegionConversionTime::HigherRankedType, + value, + ) + } + + pub(super) fn instantiate_binder_with_placeholders<T: TypeFoldable<TyCtxt<'tcx>> + Copy>( + &self, + value: ty::Binder<'tcx, T>, + ) -> T { + self.infcx.instantiate_binder_with_placeholders(value) + } + + pub(super) fn resolve_vars_if_possible<T>(&self, value: T) -> T + where + T: TypeFoldable<TyCtxt<'tcx>>, + { + self.infcx.resolve_vars_if_possible(value) + } + + pub(super) fn fresh_substs_for_item(&self, def_id: DefId) -> ty::SubstsRef<'tcx> { + self.infcx.fresh_substs_for_item(DUMMY_SP, def_id) + } + + pub(super) fn universe(&self) -> ty::UniverseIndex { + self.infcx.universe() + } +} diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs index a6240666e..a55b984fd 100644 --- a/compiler/rustc_trait_selection/src/solve/fulfill.rs +++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs @@ -1,16 +1,14 @@ use std::mem; -use rustc_data_structures::fx::FxHashMap; -use rustc_infer::{ - infer::InferCtxt, - traits::{ - query::NoSolution, FulfillmentError, FulfillmentErrorCode, PredicateObligation, - SelectionError, TraitEngine, - }, +use rustc_infer::infer::InferCtxt; +use rustc_infer::traits::{ + query::NoSolution, FulfillmentError, FulfillmentErrorCode, MismatchedProjectionTypes, + PredicateObligation, SelectionError, TraitEngine, }; use rustc_middle::ty; +use rustc_middle::ty::error::{ExpectedFound, TypeError}; -use super::{search_graph, Certainty, EvalCtxt}; +use super::{Certainty, InferCtxtEvalExt}; /// A trait engine using the new trait solver. /// @@ -42,12 +40,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { self.obligations.push(obligation); } - fn select_all_or_error(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> { - let errors = self.select_where_possible(infcx); - if !errors.is_empty() { - return errors; - } - + fn collect_remaining_errors(&mut self) -> Vec<FulfillmentError<'tcx>> { self.obligations .drain(..) .map(|obligation| FulfillmentError { @@ -68,16 +61,65 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { let mut has_changed = false; for obligation in mem::take(&mut self.obligations) { let goal = obligation.clone().into(); - let search_graph = &mut search_graph::SearchGraph::new(infcx.tcx); - let mut ecx = EvalCtxt::new_outside_solver(infcx, search_graph); - let (changed, certainty) = match ecx.evaluate_goal(goal) { + let (changed, certainty) = match infcx.evaluate_root_goal(goal) { Ok(result) => result, Err(NoSolution) => { errors.push(FulfillmentError { obligation: obligation.clone(), - code: FulfillmentErrorCode::CodeSelectionError( - SelectionError::Unimplemented, - ), + code: match goal.predicate.kind().skip_binder() { + ty::PredicateKind::Clause(ty::Clause::Projection(_)) => { + FulfillmentErrorCode::CodeProjectionError( + // FIXME: This could be a `Sorts` if the term is a type + MismatchedProjectionTypes { err: TypeError::Mismatch }, + ) + } + ty::PredicateKind::AliasEq(_, _) => { + FulfillmentErrorCode::CodeProjectionError( + MismatchedProjectionTypes { err: TypeError::Mismatch }, + ) + } + ty::PredicateKind::Subtype(pred) => { + let (a, b) = infcx.instantiate_binder_with_placeholders( + goal.predicate.kind().rebind((pred.a, pred.b)), + ); + let expected_found = ExpectedFound::new(true, a, b); + FulfillmentErrorCode::CodeSubtypeError( + expected_found, + TypeError::Sorts(expected_found), + ) + } + ty::PredicateKind::Coerce(pred) => { + let (a, b) = infcx.instantiate_binder_with_placeholders( + goal.predicate.kind().rebind((pred.a, pred.b)), + ); + let expected_found = ExpectedFound::new(false, a, b); + FulfillmentErrorCode::CodeSubtypeError( + expected_found, + TypeError::Sorts(expected_found), + ) + } + ty::PredicateKind::ConstEquate(a, b) => { + let (a, b) = infcx.instantiate_binder_with_placeholders( + goal.predicate.kind().rebind((a, b)), + ); + let expected_found = ExpectedFound::new(true, a, b); + FulfillmentErrorCode::CodeConstEquateError( + expected_found, + TypeError::ConstMismatch(expected_found), + ) + } + ty::PredicateKind::Clause(_) + | ty::PredicateKind::WellFormed(_) + | ty::PredicateKind::ObjectSafe(_) + | ty::PredicateKind::ClosureKind(_, _, _) + | ty::PredicateKind::ConstEvaluatable(_) + | ty::PredicateKind::TypeWellFormedFromEnv(_) + | ty::PredicateKind::Ambiguous => { + FulfillmentErrorCode::CodeSelectionError( + SelectionError::Unimplemented, + ) + } + }, root_obligation: obligation, }); continue; @@ -103,7 +145,10 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { self.obligations.clone() } - fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships> { - unimplemented!("Should be moved out of `TraitEngine`") + fn drain_unstalled_obligations( + &mut self, + _: &InferCtxt<'tcx>, + ) -> Vec<PredicateObligation<'tcx>> { + unimplemented!() } } diff --git a/compiler/rustc_trait_selection/src/solve/infcx_ext.rs b/compiler/rustc_trait_selection/src/solve/infcx_ext.rs deleted file mode 100644 index 42f597c78..000000000 --- a/compiler/rustc_trait_selection/src/solve/infcx_ext.rs +++ /dev/null @@ -1,78 +0,0 @@ -use rustc_infer::infer::at::ToTrace; -use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; -use rustc_infer::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime}; -use rustc_infer::traits::query::NoSolution; -use rustc_infer::traits::ObligationCause; -use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; -use rustc_middle::ty::{self, Ty, TypeFoldable}; -use rustc_span::DUMMY_SP; - -use super::Goal; - -/// Methods used inside of the canonical queries of the solver. -/// -/// Most notably these do not care about diagnostics information. -/// If you find this while looking for methods to use outside of the -/// solver, you may look at the implementation of these method for -/// help. -pub(super) trait InferCtxtExt<'tcx> { - fn next_ty_infer(&self) -> Ty<'tcx>; - fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx>; - - fn eq<T: ToTrace<'tcx>>( - &self, - param_env: ty::ParamEnv<'tcx>, - lhs: T, - rhs: T, - ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution>; - - fn instantiate_bound_vars_with_infer<T: TypeFoldable<'tcx> + Copy>( - &self, - value: ty::Binder<'tcx, T>, - ) -> T; -} - -impl<'tcx> InferCtxtExt<'tcx> for InferCtxt<'tcx> { - fn next_ty_infer(&self) -> Ty<'tcx> { - self.next_ty_var(TypeVariableOrigin { - kind: TypeVariableOriginKind::MiscVariable, - span: DUMMY_SP, - }) - } - fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx> { - self.next_const_var( - ty, - ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span: DUMMY_SP }, - ) - } - - #[instrument(level = "debug", skip(self, param_env), ret)] - fn eq<T: ToTrace<'tcx>>( - &self, - param_env: ty::ParamEnv<'tcx>, - lhs: T, - rhs: T, - ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> { - self.at(&ObligationCause::dummy(), param_env) - .define_opaque_types(false) - .eq(lhs, rhs) - .map(|InferOk { value: (), obligations }| { - obligations.into_iter().map(|o| o.into()).collect() - }) - .map_err(|e| { - debug!(?e, "failed to equate"); - NoSolution - }) - } - - fn instantiate_bound_vars_with_infer<T: TypeFoldable<'tcx> + Copy>( - &self, - value: ty::Binder<'tcx, T>, - ) -> T { - self.replace_bound_vars_with_fresh_vars( - DUMMY_SP, - LateBoundRegionConversionTime::HigherRankedType, - value, - ) - } -} diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 32eb84635..57b6a4527 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -13,31 +13,34 @@ // preserves universes and creates a unique var (in the highest universe) for each // appearance of a region. -// FIXME: `CanonicalVarValues` should be interned and `Copy`. - // FIXME: uses of `infcx.at` need to enable deferred projection equality once that's implemented. use std::mem; -use rustc_infer::infer::canonical::{Canonical, CanonicalVarKind, CanonicalVarValues}; -use rustc_infer::infer::canonical::{OriginalQueryValues, QueryRegionConstraints, QueryResponse}; +use rustc_hir::def_id::DefId; +use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues}; use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt}; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::Obligation; -use rustc_middle::infer::canonical::Certainty as OldCertainty; +use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData}; use rustc_middle::ty::{self, Ty, TyCtxt}; -use rustc_middle::ty::{RegionOutlivesPredicate, ToPredicate, TypeOutlivesPredicate}; +use rustc_middle::ty::{ + CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, ToPredicate, TypeOutlivesPredicate, +}; use rustc_span::DUMMY_SP; +use crate::solve::search_graph::OverflowHandler; use crate::traits::ObligationCause; mod assembly; +mod canonical; +mod eval_ctxt; mod fulfill; -mod infcx_ext; mod project_goals; mod search_graph; mod trait_goals; +pub use eval_ctxt::EvalCtxt; pub use fulfill::FulfillmentCtxt; /// A goal is a statement, i.e. `predicate`, we want to prove @@ -71,8 +74,7 @@ impl<'tcx, P> From<Obligation<'tcx, P>> for Goal<'tcx, P> { Goal { param_env: obligation.param_env, predicate: obligation.predicate } } } - -#[derive(Debug, PartialEq, Eq, Clone, Hash, TypeFoldable, TypeVisitable)] +#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] pub struct Response<'tcx> { pub var_values: CanonicalVarValues<'tcx>, /// Additional constraints returned by this query. @@ -80,6 +82,18 @@ pub struct Response<'tcx> { pub certainty: Certainty, } +trait CanonicalResponseExt { + fn has_no_inference_or_external_constraints(&self) -> bool; +} + +impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> { + fn has_no_inference_or_external_constraints(&self) -> bool { + self.value.external_constraints.region_constraints.is_empty() + && self.value.var_values.is_identity() + && self.value.external_constraints.opaque_types.is_empty() + } +} + #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] pub enum Certainty { Yes, @@ -87,6 +101,8 @@ pub enum Certainty { } impl Certainty { + pub const AMBIGUOUS: Certainty = Certainty::Maybe(MaybeCause::Ambiguity); + /// When proving multiple goals using **AND**, e.g. nested obligations for an impl, /// use this function to unify the certainty of these goals pub fn unify_and(self, other: Certainty) -> Certainty { @@ -118,14 +134,6 @@ pub enum MaybeCause { Overflow, } -/// Additional constraints returned on success. -#[derive(Debug, PartialEq, Eq, Clone, Hash, TypeFoldable, TypeVisitable, Default)] -pub struct ExternalConstraints<'tcx> { - // FIXME: implement this. - regions: (), - opaque_types: Vec<(Ty<'tcx>, Ty<'tcx>)>, -} - type CanonicalGoal<'tcx, T = ty::Predicate<'tcx>> = Canonical<'tcx, Goal<'tcx, T>>; type CanonicalResponse<'tcx> = Canonical<'tcx, Response<'tcx>>; /// The result of evaluating a canonical query. @@ -136,78 +144,70 @@ type CanonicalResponse<'tcx> = Canonical<'tcx, Response<'tcx>>; /// solver, merge the two responses again. pub type QueryResult<'tcx> = Result<CanonicalResponse<'tcx>, NoSolution>; -pub trait TyCtxtExt<'tcx> { - fn evaluate_goal(self, goal: CanonicalGoal<'tcx>) -> QueryResult<'tcx>; -} - -impl<'tcx> TyCtxtExt<'tcx> for TyCtxt<'tcx> { - fn evaluate_goal(self, goal: CanonicalGoal<'tcx>) -> QueryResult<'tcx> { - let mut search_graph = search_graph::SearchGraph::new(self); - EvalCtxt::evaluate_canonical_goal(self, &mut search_graph, goal) - } +pub trait InferCtxtEvalExt<'tcx> { + /// Evaluates a goal from **outside** of the trait solver. + /// + /// Using this while inside of the solver is wrong as it uses a new + /// search graph which would break cycle detection. + fn evaluate_root_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty), NoSolution>; } -struct EvalCtxt<'a, 'tcx> { - infcx: &'a InferCtxt<'tcx>, - var_values: CanonicalVarValues<'tcx>, +impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { + fn evaluate_root_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty), NoSolution> { + let mut search_graph = search_graph::SearchGraph::new(self.tcx); + + let result = EvalCtxt { + search_graph: &mut search_graph, + infcx: self, + // Only relevant when canonicalizing the response. + max_input_universe: ty::UniverseIndex::ROOT, + var_values: CanonicalVarValues::dummy(), + in_projection_eq_hack: false, + } + .evaluate_goal(goal); - search_graph: &'a mut search_graph::SearchGraph<'tcx>, + assert!(search_graph.is_empty()); + result + } } impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { - fn tcx(&self) -> TyCtxt<'tcx> { - self.infcx.tcx - } - - /// Creates a new evaluation context outside of the trait solver. + /// The entry point of the solver. /// - /// With this solver making a canonical response doesn't make much sense. - /// The `search_graph` for this solver has to be completely empty. - fn new_outside_solver( - infcx: &'a InferCtxt<'tcx>, - search_graph: &'a mut search_graph::SearchGraph<'tcx>, - ) -> EvalCtxt<'a, 'tcx> { - assert!(search_graph.is_empty()); - EvalCtxt { infcx, var_values: CanonicalVarValues::dummy(), search_graph } - } - + /// This function deals with (coinductive) cycles, overflow, and caching + /// and then calls [`EvalCtxt::compute_goal`] which contains the actual + /// logic of the solver. + /// + /// Instead of calling this function directly, use either [EvalCtxt::evaluate_goal] + /// if you're inside of the solver or [InferCtxtEvalExt::evaluate_root_goal] if you're + /// outside of it. #[instrument(level = "debug", skip(tcx, search_graph), ret)] fn evaluate_canonical_goal( tcx: TyCtxt<'tcx>, search_graph: &'a mut search_graph::SearchGraph<'tcx>, canonical_goal: CanonicalGoal<'tcx>, ) -> QueryResult<'tcx> { - match search_graph.try_push_stack(tcx, canonical_goal) { - Ok(()) => {} - // Our goal is already on the stack, eager return. - Err(response) => return response, - } - - // We may have to repeatedly recompute the goal in case of coinductive cycles, - // check out the `cache` module for more information. + // Deal with overflow, caching, and coinduction. // - // FIXME: Similar to `evaluate_all`, this has to check for overflow. - loop { + // The actual solver logic happens in `ecx.compute_goal`. + search_graph.with_new_goal(tcx, canonical_goal, |search_graph| { let (ref infcx, goal, var_values) = tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &canonical_goal); - let mut ecx = EvalCtxt { infcx, var_values, search_graph }; - let result = ecx.compute_goal(goal); - - // FIXME: `Response` should be `Copy` - if search_graph.try_finalize_goal(tcx, canonical_goal, result.clone()) { - return result; - } - } - } - - fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> { - let external_constraints = take_external_constraints(self.infcx)?; - - Ok(self.infcx.canonicalize_response(Response { - var_values: self.var_values.clone(), - external_constraints, - certainty, - })) + let mut ecx = EvalCtxt { + infcx, + var_values, + max_input_universe: canonical_goal.max_universe, + search_graph, + in_projection_eq_hack: false, + }; + ecx.compute_goal(goal) + }) } /// Recursively evaluates `goal`, returning whether any inference vars have @@ -216,14 +216,39 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { &mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>, ) -> Result<(bool, Certainty), NoSolution> { - let mut orig_values = OriginalQueryValues::default(); - let canonical_goal = self.infcx.canonicalize_query(goal, &mut orig_values); + let (orig_values, canonical_goal) = self.canonicalize_goal(goal); let canonical_response = EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; - Ok(( - !canonical_response.value.var_values.is_identity(), - instantiate_canonical_query_response(self.infcx, &orig_values, canonical_response), - )) + + let has_changed = !canonical_response.value.var_values.is_identity(); + let certainty = self.instantiate_and_apply_query_response( + goal.param_env, + orig_values, + canonical_response, + )?; + + // Check that rerunning this query with its inference constraints applied + // doesn't result in new inference constraints and has the same result. + // + // If we have projection goals like `<T as Trait>::Assoc == u32` we recursively + // call `exists<U> <T as Trait>::Assoc == U` to enable better caching. This goal + // could constrain `U` to `u32` which would cause this check to result in a + // solver cycle. + if cfg!(debug_assertions) + && has_changed + && !self.in_projection_eq_hack + && !self.search_graph.in_cycle() + { + let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); + let canonical_response = + EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; + if !canonical_response.value.var_values.is_identity() { + bug!("unstable result: {goal:?} {canonical_goal:?} {canonical_response:?}"); + } + assert_eq!(certainty, canonical_response.value.certainty); + } + + Ok((has_changed, certainty)) } fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { @@ -243,19 +268,40 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => { self.compute_region_outlives_goal(Goal { param_env, predicate }) } + ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => { + self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) }) + } + ty::PredicateKind::Subtype(predicate) => { + self.compute_subtype_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Coerce(predicate) => { + self.compute_coerce_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::ClosureKind(def_id, substs, kind) => self + .compute_closure_kind_goal(Goal { + param_env, + predicate: (def_id, substs, kind), + }), + ty::PredicateKind::ObjectSafe(trait_def_id) => { + self.compute_object_safe_goal(trait_def_id) + } + ty::PredicateKind::WellFormed(arg) => { + self.compute_well_formed_goal(Goal { param_env, predicate: arg }) + } + ty::PredicateKind::Ambiguous => self.make_canonical_response(Certainty::AMBIGUOUS), // FIXME: implement these predicates :) - ty::PredicateKind::WellFormed(_) - | ty::PredicateKind::ObjectSafe(_) - | ty::PredicateKind::ClosureKind(_, _, _) - | ty::PredicateKind::Subtype(_) - | ty::PredicateKind::Coerce(_) - | ty::PredicateKind::ConstEvaluatable(_) - | ty::PredicateKind::ConstEquate(_, _) - | ty::PredicateKind::TypeWellFormedFromEnv(_) - | ty::PredicateKind::Ambiguous => self.make_canonical_response(Certainty::Yes), + ty::PredicateKind::ConstEvaluatable(_) | ty::PredicateKind::ConstEquate(_, _) => { + self.make_canonical_response(Certainty::Yes) + } + ty::PredicateKind::TypeWellFormedFromEnv(..) => { + bug!("TypeWellFormedFromEnv is only used for Chalk") + } + ty::PredicateKind::AliasEq(lhs, rhs) => { + self.compute_alias_eq_goal(Goal { param_env, predicate: (lhs, rhs) }) + } } } else { - let kind = self.infcx.replace_bound_vars_with_placeholders(kind); + let kind = self.infcx.instantiate_binder_with_placeholders(kind); let goal = goal.with(self.tcx(), ty::Binder::dummy(kind)); let (_, certainty) = self.evaluate_goal(goal)?; self.make_canonical_response(certainty) @@ -264,102 +310,255 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { fn compute_type_outlives_goal( &mut self, - _goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>, + goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { + let ty::OutlivesPredicate(ty, lt) = goal.predicate; + self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy()); self.make_canonical_response(Certainty::Yes) } fn compute_region_outlives_goal( &mut self, - _goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>, + goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { + self.infcx.region_outlives_predicate( + &ObligationCause::dummy(), + ty::Binder::dummy(goal.predicate), + ); self.make_canonical_response(Certainty::Yes) } + + fn compute_coerce_goal( + &mut self, + goal: Goal<'tcx, CoercePredicate<'tcx>>, + ) -> QueryResult<'tcx> { + self.compute_subtype_goal(Goal { + param_env: goal.param_env, + predicate: SubtypePredicate { + a_is_expected: false, + a: goal.predicate.a, + b: goal.predicate.b, + }, + }) + } + + fn compute_subtype_goal( + &mut self, + goal: Goal<'tcx, SubtypePredicate<'tcx>>, + ) -> QueryResult<'tcx> { + if goal.predicate.a.is_ty_var() && goal.predicate.b.is_ty_var() { + // FIXME: Do we want to register a subtype relation between these vars? + // That won't actually reflect in the query response, so it seems moot. + self.make_canonical_response(Certainty::AMBIGUOUS) + } else { + let InferOk { value: (), obligations } = self + .infcx + .at(&ObligationCause::dummy(), goal.param_env) + .sub(goal.predicate.a, goal.predicate.b)?; + self.evaluate_all_and_make_canonical_response( + obligations.into_iter().map(|pred| pred.into()).collect(), + ) + } + } + + fn compute_closure_kind_goal( + &mut self, + goal: Goal<'tcx, (DefId, ty::SubstsRef<'tcx>, ty::ClosureKind)>, + ) -> QueryResult<'tcx> { + let (_, substs, expected_kind) = goal.predicate; + let found_kind = substs.as_closure().kind_ty().to_opt_closure_kind(); + + let Some(found_kind) = found_kind else { + return self.make_canonical_response(Certainty::AMBIGUOUS); + }; + if found_kind.extends(expected_kind) { + self.make_canonical_response(Certainty::Yes) + } else { + Err(NoSolution) + } + } + + fn compute_object_safe_goal(&mut self, trait_def_id: DefId) -> QueryResult<'tcx> { + if self.tcx().check_is_object_safe(trait_def_id) { + self.make_canonical_response(Certainty::Yes) + } else { + Err(NoSolution) + } + } + + fn compute_well_formed_goal( + &mut self, + goal: Goal<'tcx, ty::GenericArg<'tcx>>, + ) -> QueryResult<'tcx> { + match crate::traits::wf::unnormalized_obligations( + self.infcx, + goal.param_env, + goal.predicate, + ) { + Some(obligations) => self.evaluate_all_and_make_canonical_response( + obligations.into_iter().map(|o| o.into()).collect(), + ), + None => self.make_canonical_response(Certainty::AMBIGUOUS), + } + } + + #[instrument(level = "debug", skip(self), ret)] + fn compute_alias_eq_goal( + &mut self, + goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>)>, + ) -> QueryResult<'tcx> { + let tcx = self.tcx(); + + let evaluate_normalizes_to = |ecx: &mut EvalCtxt<'_, 'tcx>, alias, other| { + debug!("evaluate_normalizes_to(alias={:?}, other={:?})", alias, other); + let r = ecx.probe(|ecx| { + let (_, certainty) = ecx.evaluate_goal(goal.with( + tcx, + ty::Binder::dummy(ty::ProjectionPredicate { + projection_ty: alias, + term: other, + }), + ))?; + ecx.make_canonical_response(certainty) + }); + debug!("evaluate_normalizes_to(..) -> {:?}", r); + r + }; + + if goal.predicate.0.is_infer() || goal.predicate.1.is_infer() { + bug!( + "`AliasEq` goal with an infer var on lhs or rhs which should have been instantiated" + ); + } + + match ( + goal.predicate.0.to_alias_term_no_opaque(tcx), + goal.predicate.1.to_alias_term_no_opaque(tcx), + ) { + (None, None) => bug!("`AliasEq` goal without an alias on either lhs or rhs"), + (Some(alias), None) => evaluate_normalizes_to(self, alias, goal.predicate.1), + (None, Some(alias)) => evaluate_normalizes_to(self, alias, goal.predicate.0), + (Some(alias_lhs), Some(alias_rhs)) => { + debug!("compute_alias_eq_goal: both sides are aliases"); + + let mut candidates = Vec::with_capacity(3); + + // Evaluate all 3 potential candidates for the alias' being equal + candidates.push(evaluate_normalizes_to(self, alias_lhs, goal.predicate.1)); + candidates.push(evaluate_normalizes_to(self, alias_rhs, goal.predicate.0)); + candidates.push(self.probe(|this| { + debug!("compute_alias_eq_goal: alias defids are equal, equating substs"); + let nested_goals = this.eq(goal.param_env, alias_lhs, alias_rhs)?; + this.evaluate_all_and_make_canonical_response(nested_goals) + })); + + debug!(?candidates); + + self.try_merge_responses(candidates.into_iter()) + } + } + } + + #[instrument(level = "debug", skip(self), ret)] + fn compute_const_arg_has_type_goal( + &mut self, + goal: Goal<'tcx, (ty::Const<'tcx>, Ty<'tcx>)>, + ) -> QueryResult<'tcx> { + let (ct, ty) = goal.predicate; + let nested_goals = self.eq(goal.param_env, ct.ty(), ty)?; + self.evaluate_all_and_make_canonical_response(nested_goals) + } } impl<'tcx> EvalCtxt<'_, 'tcx> { + // Recursively evaluates a list of goals to completion, returning the certainty + // of all of the goals. fn evaluate_all( &mut self, mut goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, ) -> Result<Certainty, NoSolution> { let mut new_goals = Vec::new(); - self.repeat_while_none(|this| { - let mut has_changed = Err(Certainty::Yes); - for goal in goals.drain(..) { - let (changed, certainty) = match this.evaluate_goal(goal) { - Ok(result) => result, - Err(NoSolution) => return Some(Err(NoSolution)), - }; - - if changed { - has_changed = Ok(()); - } + self.repeat_while_none( + |_| Ok(Certainty::Maybe(MaybeCause::Overflow)), + |this| { + let mut has_changed = Err(Certainty::Yes); + for goal in goals.drain(..) { + let (changed, certainty) = match this.evaluate_goal(goal) { + Ok(result) => result, + Err(NoSolution) => return Some(Err(NoSolution)), + }; + + if changed { + has_changed = Ok(()); + } - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - new_goals.push(goal); - has_changed = has_changed.map_err(|c| c.unify_and(certainty)); + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + new_goals.push(goal); + has_changed = has_changed.map_err(|c| c.unify_and(certainty)); + } } } - } - match has_changed { - Ok(()) => { - mem::swap(&mut new_goals, &mut goals); - None + match has_changed { + Ok(()) => { + mem::swap(&mut new_goals, &mut goals); + None + } + Err(certainty) => Some(Ok(certainty)), } - Err(certainty) => Some(Ok(certainty)), - } - }) + }, + ) } + // Recursively evaluates a list of goals to completion, making a query response. + // + // This is just a convenient way of calling [`EvalCtxt::evaluate_all`], + // then [`EvalCtxt::make_canonical_response`]. fn evaluate_all_and_make_canonical_response( &mut self, goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, ) -> QueryResult<'tcx> { self.evaluate_all(goals).and_then(|certainty| self.make_canonical_response(certainty)) } -} -#[instrument(level = "debug", skip(infcx), ret)] -fn take_external_constraints<'tcx>( - infcx: &InferCtxt<'tcx>, -) -> Result<ExternalConstraints<'tcx>, NoSolution> { - let region_obligations = infcx.take_registered_region_obligations(); - let opaque_types = infcx.take_opaque_types_for_query_response(); - Ok(ExternalConstraints { - // FIXME: Now that's definitely wrong :) - // - // Should also do the leak check here I think - regions: drop(region_obligations), - opaque_types, - }) -} + fn try_merge_responses( + &mut self, + responses: impl Iterator<Item = QueryResult<'tcx>>, + ) -> QueryResult<'tcx> { + let candidates = responses.into_iter().flatten().collect::<Box<[_]>>(); -fn instantiate_canonical_query_response<'tcx>( - infcx: &InferCtxt<'tcx>, - original_values: &OriginalQueryValues<'tcx>, - response: CanonicalResponse<'tcx>, -) -> Certainty { - let Ok(InferOk { value, obligations }) = infcx - .instantiate_query_response_and_region_obligations( - &ObligationCause::dummy(), - ty::ParamEnv::empty(), - original_values, - &response.unchecked_map(|resp| QueryResponse { - var_values: resp.var_values, - region_constraints: QueryRegionConstraints::default(), - certainty: match resp.certainty { - Certainty::Yes => OldCertainty::Proven, - Certainty::Maybe(_) => OldCertainty::Ambiguous, - }, - opaque_types: resp.external_constraints.opaque_types, - value: resp.certainty, - }), - ) else { bug!(); }; - assert!(obligations.is_empty()); - value + if candidates.is_empty() { + return Err(NoSolution); + } + + // FIXME(-Ztreat-solver=next): We should instead try to find a `Certainty::Yes` response with + // a subset of the constraints that all the other responses have. + let one = candidates[0]; + if candidates[1..].iter().all(|resp| resp == &one) { + return Ok(one); + } + + if let Some(response) = candidates.iter().find(|response| { + response.value.certainty == Certainty::Yes + && response.has_no_inference_or_external_constraints() + }) { + return Ok(*response); + } + + let certainty = candidates.iter().fold(Certainty::AMBIGUOUS, |certainty, response| { + certainty.unify_and(response.value.certainty) + }); + // FIXME(-Ztrait-solver=next): We should take the intersection of the constraints on all the + // responses and use that for the constraints of this ambiguous response. + let response = self.make_canonical_response(certainty); + if let Ok(response) = &response { + assert!(response.has_no_inference_or_external_constraints()); + } + + response + } } pub(super) fn response_no_constraints<'tcx>( @@ -367,33 +566,14 @@ pub(super) fn response_no_constraints<'tcx>( goal: Canonical<'tcx, impl Sized>, certainty: Certainty, ) -> QueryResult<'tcx> { - let var_values = goal - .variables - .iter() - .enumerate() - .map(|(i, info)| match info.kind { - CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => { - tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i).into())).into() - } - CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => { - let br = ty::BoundRegion { - var: ty::BoundVar::from_usize(i), - kind: ty::BrAnon(i as u32, None), - }; - tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into() - } - CanonicalVarKind::Const(_, ty) | CanonicalVarKind::PlaceholderConst(_, ty) => tcx - .mk_const(ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i)), ty) - .into(), - }) - .collect(); - Ok(Canonical { max_universe: goal.max_universe, variables: goal.variables, value: Response { - var_values: CanonicalVarValues { var_values }, - external_constraints: Default::default(), + var_values: CanonicalVarValues::make_identity(tcx, goal.variables), + // FIXME: maybe we should store the "no response" version in tcx, like + // we do for tcx.types and stuff. + external_constraints: tcx.mk_external_constraints(ExternalConstraintsData::default()), certainty, }, }) diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs index e39fa0533..33c66d072 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -1,23 +1,22 @@ use crate::traits::{specialization_graph, translate_substs}; -use super::assembly::{self, Candidate, CandidateSource}; -use super::infcx_ext::InferCtxtExt; +use super::assembly; use super::trait_goals::structural_traits; -use super::{Certainty, EvalCtxt, Goal, MaybeCause, QueryResult}; +use super::{Certainty, EvalCtxt, Goal, QueryResult}; use rustc_errors::ErrorGuaranteed; use rustc_hir::def::DefKind; use rustc_hir::def_id::DefId; +use rustc_hir::LangItem; use rustc_infer::infer::InferCtxt; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::specialization_graph::LeafDef; use rustc_infer::traits::Reveal; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; +use rustc_middle::ty::ProjectionPredicate; use rustc_middle::ty::{self, Ty, TyCtxt}; -use rustc_middle::ty::{ProjectionPredicate, TypeSuperVisitable, TypeVisitor}; -use rustc_middle::ty::{ToPredicate, TypeVisitable}; -use rustc_span::DUMMY_SP; +use rustc_middle::ty::{ToPredicate, TypeVisitableExt}; +use rustc_span::{sym, DUMMY_SP}; use std::iter; -use std::ops::ControlFlow; impl<'tcx> EvalCtxt<'_, 'tcx> { pub(super) fn compute_projection_goal( @@ -27,151 +26,62 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // To only compute normalization once for each projection we only // normalize if the expected term is an unconstrained inference variable. // - // E.g. for `<T as Trait>::Assoc = u32` we recursively compute the goal - // `exists<U> <T as Trait>::Assoc = U` and then take the resulting type for + // E.g. for `<T as Trait>::Assoc == u32` we recursively compute the goal + // `exists<U> <T as Trait>::Assoc == U` and then take the resulting type for // `U` and equate it with `u32`. This means that we don't need a separate // projection cache in the solver. if self.term_is_fully_unconstrained(goal) { let candidates = self.assemble_and_evaluate_candidates(goal); - self.merge_project_candidates(candidates) + self.merge_candidates_and_discard_reservation_impls(candidates) } else { let predicate = goal.predicate; let unconstrained_rhs = match predicate.term.unpack() { - ty::TermKind::Ty(_) => self.infcx.next_ty_infer().into(), - ty::TermKind::Const(ct) => self.infcx.next_const_infer(ct.ty()).into(), + ty::TermKind::Ty(_) => self.next_ty_infer().into(), + ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(), }; let unconstrained_predicate = ty::Clause::Projection(ProjectionPredicate { projection_ty: goal.predicate.projection_ty, term: unconstrained_rhs, }); - let (_has_changed, normalize_certainty) = - self.evaluate_goal(goal.with(self.tcx(), unconstrained_predicate))?; + let (_has_changed, normalize_certainty) = self.in_projection_eq_hack(|this| { + this.evaluate_goal(goal.with(this.tcx(), unconstrained_predicate)) + })?; - let nested_eq_goals = - self.infcx.eq(goal.param_env, unconstrained_rhs, predicate.term)?; + let nested_eq_goals = self.eq(goal.param_env, unconstrained_rhs, predicate.term)?; let eval_certainty = self.evaluate_all(nested_eq_goals)?; self.make_canonical_response(normalize_certainty.unify_and(eval_certainty)) } } - /// Is the projection predicate is of the form `exists<T> <Ty as Trait>::Assoc = T`. - /// - /// This is the case if the `term` is an inference variable in the innermost universe - /// and does not occur in any other part of the predicate. - fn term_is_fully_unconstrained(&self, goal: Goal<'tcx, ProjectionPredicate<'tcx>>) -> bool { - let infcx = self.infcx; - let term_is_infer = match goal.predicate.term.unpack() { - ty::TermKind::Ty(ty) => { - if let &ty::Infer(ty::TyVar(vid)) = ty.kind() { - match infcx.probe_ty_var(vid) { - Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), - Err(universe) => universe == infcx.universe(), - } - } else { - false - } - } - ty::TermKind::Const(ct) => { - if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.kind() { - match self.infcx.probe_const_var(vid) { - Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), - Err(universe) => universe == infcx.universe(), - } - } else { - false - } - } - }; - - // Guard against `<T as Trait<?0>>::Assoc = ?0>`. - struct ContainsTerm<'tcx> { - term: ty::Term<'tcx>, - } - impl<'tcx> TypeVisitor<'tcx> for ContainsTerm<'tcx> { - type BreakTy = (); - fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { - if t.needs_infer() { - if ty::Term::from(t) == self.term { - ControlFlow::BREAK - } else { - t.super_visit_with(self) - } - } else { - ControlFlow::CONTINUE - } - } - - fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { - if c.needs_infer() { - if ty::Term::from(c) == self.term { - ControlFlow::BREAK - } else { - c.super_visit_with(self) - } - } else { - ControlFlow::CONTINUE - } - } - } - - let mut visitor = ContainsTerm { term: goal.predicate.term }; - - term_is_infer - && goal.predicate.projection_ty.visit_with(&mut visitor).is_continue() - && goal.param_env.visit_with(&mut visitor).is_continue() + /// This sets a flag used by a debug assert in [`EvalCtxt::evaluate_goal`], + /// see the comment in that method for more details. + fn in_projection_eq_hack<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T { + self.in_projection_eq_hack = true; + let result = f(self); + self.in_projection_eq_hack = false; + result } - fn merge_project_candidates( + /// After normalizing the projection to `normalized_alias` with the given + /// `normalization_certainty`, constrain the inference variable `term` to it + /// and return a query response. + fn eq_term_and_make_canonical_response( &mut self, - mut candidates: Vec<Candidate<'tcx>>, + goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + normalization_certainty: Certainty, + normalized_alias: impl Into<ty::Term<'tcx>>, ) -> QueryResult<'tcx> { - match candidates.len() { - 0 => return Err(NoSolution), - 1 => return Ok(candidates.pop().unwrap().result), - _ => {} - } - - if candidates.len() > 1 { - let mut i = 0; - 'outer: while i < candidates.len() { - for j in (0..candidates.len()).filter(|&j| i != j) { - if self.project_candidate_should_be_dropped_in_favor_of( - &candidates[i], - &candidates[j], - ) { - debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len()); - candidates.swap_remove(i); - continue 'outer; - } - } + // The term of our goal should be fully unconstrained, so this should never fail. + // + // It can however be ambiguous when the `normalized_alias` contains a projection. + let nested_goals = self + .eq(goal.param_env, goal.predicate.term, normalized_alias.into()) + .expect("failed to unify with unconstrained term"); - debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len()); - // If there are *STILL* multiple candidates, give up - // and report ambiguity. - i += 1; - if i > 1 { - debug!("multiple matches, ambig"); - // FIXME: return overflow if all candidates overflow, otherwise return ambiguity. - unimplemented!(); - } - } - } + let unify_certainty = + self.evaluate_all(nested_goals).expect("failed to unify with unconstrained term"); - Ok(candidates.pop().unwrap().result) - } - - fn project_candidate_should_be_dropped_in_favor_of( - &self, - candidate: &Candidate<'tcx>, - other: &Candidate<'tcx>, - ) -> bool { - // FIXME: implement this - match (candidate.source, other.source) { - (CandidateSource::Impl(_), _) - | (CandidateSource::ParamEnv(_), _) - | (CandidateSource::BuiltinImpl, _) - | (CandidateSource::AliasBound(_), _) => unimplemented!(), - } + self.make_canonical_response(normalization_certainty.unify_and(unify_certainty)) } } @@ -188,6 +98,82 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { self.trait_def_id(tcx) } + 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> { + if let Some(poly_projection_pred) = assumption.to_opt_poly_projection_pred() + && poly_projection_pred.projection_def_id() == goal.predicate.def_id() + { + ecx.probe(|ecx| { + let assumption_projection_pred = + ecx.instantiate_binder_with_infer(poly_projection_pred); + let mut nested_goals = ecx.eq( + goal.param_env, + goal.predicate.projection_ty, + assumption_projection_pred.projection_ty, + )?; + nested_goals.extend(requirements); + let subst_certainty = ecx.evaluate_all(nested_goals)?; + + ecx.eq_term_and_make_canonical_response( + goal, + subst_certainty, + assumption_projection_pred.term, + ) + }) + } else { + Err(NoSolution) + } + } + + fn consider_object_bound_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + assumption: ty::Predicate<'tcx>, + ) -> QueryResult<'tcx> { + if let Some(poly_projection_pred) = assumption.to_opt_poly_projection_pred() + && poly_projection_pred.projection_def_id() == goal.predicate.def_id() + { + ecx.probe(|ecx| { + let assumption_projection_pred = + ecx.instantiate_binder_with_infer(poly_projection_pred); + let mut nested_goals = ecx.eq( + goal.param_env, + goal.predicate.projection_ty, + assumption_projection_pred.projection_ty, + )?; + + let tcx = ecx.tcx(); + let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { + bug!("expected object type in `consider_object_bound_candidate`"); + }; + nested_goals.extend( + structural_traits::predicates_for_object_candidate( + ecx, + goal.param_env, + goal.predicate.projection_ty.trait_ref(tcx), + bounds, + ) + .into_iter() + .map(|pred| goal.with(tcx, pred)), + ); + + let subst_certainty = ecx.evaluate_all(nested_goals)?; + + ecx.eq_term_and_make_canonical_response( + goal, + subst_certainty, + assumption_projection_pred.term, + ) + }) + } else { + Err(NoSolution) + } + } + fn consider_impl_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, ProjectionPredicate<'tcx>>, @@ -204,11 +190,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { return Err(NoSolution); } - ecx.infcx.probe(|_| { - let impl_substs = ecx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id); + ecx.probe(|ecx| { + let impl_substs = ecx.fresh_substs_for_item(impl_def_id); let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); - let mut nested_goals = ecx.infcx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; + let mut nested_goals = ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; let where_clause_bounds = tcx .predicates_of(impl_def_id) .instantiate(tcx, impl_substs) @@ -217,7 +203,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { .map(|pred| goal.with(tcx, pred)); nested_goals.extend(where_clause_bounds); - let trait_ref_certainty = ecx.evaluate_all(nested_goals)?; + let match_impl_certainty = ecx.evaluate_all(nested_goals)?; // In case the associated item is hidden due to specialization, we have to // return ambiguity this would otherwise be incomplete, resulting in @@ -229,8 +215,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal.predicate.def_id(), impl_def_id )? else { - let certainty = Certainty::Maybe(MaybeCause::Ambiguity); - return ecx.make_canonical_response(trait_ref_certainty.unify_and(certainty)); + return ecx.make_canonical_response(match_impl_certainty.unify_and(Certainty::AMBIGUOUS)); }; if !assoc_def.item.defaultness(tcx).has_value() { @@ -265,7 +250,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { // Finally we construct the actual value of the associated type. let is_const = matches!(tcx.def_kind(assoc_def.item.def_id), DefKind::AssocConst); - let ty = tcx.bound_type_of(assoc_def.item.def_id); + let ty = tcx.type_of(assoc_def.item.def_id); let term: ty::EarlyBinder<ty::Term<'tcx>> = if is_const { let identity_substs = ty::InternalSubsts::identity_for_item(tcx, assoc_def.item.def_id); @@ -277,54 +262,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ty.map_bound(|ty| ty.into()) }; - // The term of our goal should be fully unconstrained, so this should never fail. - // - // It can however be ambiguous when the resolved type is a projection. - let nested_goals = ecx - .infcx - .eq(goal.param_env, goal.predicate.term, term.subst(tcx, substs)) - .expect("failed to unify with unconstrained term"); - let rhs_certainty = - ecx.evaluate_all(nested_goals).expect("failed to unify with unconstrained term"); - - ecx.make_canonical_response(trait_ref_certainty.unify_and(rhs_certainty)) + ecx.eq_term_and_make_canonical_response(goal, match_impl_certainty, term.subst(tcx, substs)) }) } - fn consider_assumption( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - assumption: ty::Predicate<'tcx>, - ) -> QueryResult<'tcx> { - if let Some(poly_projection_pred) = assumption.to_opt_poly_projection_pred() { - ecx.infcx.probe(|_| { - let assumption_projection_pred = - ecx.infcx.instantiate_bound_vars_with_infer(poly_projection_pred); - let nested_goals = ecx.infcx.eq( - goal.param_env, - goal.predicate.projection_ty, - assumption_projection_pred.projection_ty, - )?; - let subst_certainty = ecx.evaluate_all(nested_goals)?; - - // The term of our goal should be fully unconstrained, so this should never fail. - // - // It can however be ambiguous when the resolved type is a projection. - let nested_goals = ecx - .infcx - .eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term) - .expect("failed to unify with unconstrained term"); - let rhs_certainty = ecx - .evaluate_all(nested_goals) - .expect("failed to unify with unconstrained term"); - - ecx.make_canonical_response(subst_certainty.unify_and(rhs_certainty)) - }) - } else { - Err(NoSolution) - } - } - fn consider_auto_trait_candidate( _ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, @@ -353,11 +294,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { bug!("`Copy`/`Clone` does not have an associated type: {:?}", goal); } - fn consider_builtin_pointer_sized_candidate( + fn consider_builtin_pointer_like_candidate( _ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { - bug!("`PointerSized` does not have an associated type: {:?}", goal); + bug!("`PointerLike` does not have an associated type: {:?}", goal); } fn consider_builtin_fn_trait_candidates( @@ -365,25 +306,28 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal: Goal<'tcx, Self>, goal_kind: ty::ClosureKind, ) -> QueryResult<'tcx> { - if let Some(tupled_inputs_and_output) = - structural_traits::extract_tupled_inputs_and_output_from_callable( - ecx.tcx(), - goal.predicate.self_ty(), - goal_kind, - )? - { - let pred = tupled_inputs_and_output - .map_bound(|(inputs, output)| ty::ProjectionPredicate { - projection_ty: ecx - .tcx() - .mk_alias_ty(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs]), - term: output.into(), - }) - .to_predicate(ecx.tcx()); - Self::consider_assumption(ecx, goal, pred) - } else { - ecx.make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity)) - } + let tcx = ecx.tcx(); + let Some(tupled_inputs_and_output) = + structural_traits::extract_tupled_inputs_and_output_from_callable( + tcx, + goal.predicate.self_ty(), + goal_kind, + )? else { + return ecx.make_canonical_response(Certainty::AMBIGUOUS); + }; + let output_is_sized_pred = tupled_inputs_and_output + .map_bound(|(_, output)| tcx.at(DUMMY_SP).mk_trait_ref(LangItem::Sized, [output])); + + let pred = tupled_inputs_and_output + .map_bound(|(inputs, output)| ty::ProjectionPredicate { + projection_ty: tcx + .mk_alias_ty(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs]), + term: output.into(), + }) + .to_predicate(tcx); + // A built-in `Fn` impl only holds if the output is sized. + // (FIXME: technically we only need to check this if the type is a fn ptr...) + Self::consider_implied_clause(ecx, goal, pred, [goal.with(tcx, output_is_sized_pred)]) } fn consider_builtin_tuple_candidate( @@ -392,6 +336,193 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ) -> QueryResult<'tcx> { bug!("`Tuple` does not have an associated type: {:?}", goal); } + + fn consider_builtin_pointee_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let tcx = ecx.tcx(); + ecx.probe(|ecx| { + let metadata_ty = match goal.predicate.self_ty().kind() { + ty::Bool + | ty::Char + | ty::Int(..) + | ty::Uint(..) + | ty::Float(..) + | ty::Array(..) + | ty::RawPtr(..) + | ty::Ref(..) + | ty::FnDef(..) + | ty::FnPtr(..) + | ty::Closure(..) + | ty::Infer(ty::IntVar(..) | ty::FloatVar(..)) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::GeneratorWitnessMIR(..) + | ty::Never + | ty::Foreign(..) => tcx.types.unit, + + ty::Error(e) => tcx.ty_error(*e), + + ty::Str | ty::Slice(_) => tcx.types.usize, + + ty::Dynamic(_, _, _) => { + let dyn_metadata = tcx.require_lang_item(LangItem::DynMetadata, None); + tcx.type_of(dyn_metadata) + .subst(tcx, &[ty::GenericArg::from(goal.predicate.self_ty())]) + } + + ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => { + // FIXME(ptr_metadata): It would also be possible to return a `Ok(Ambig)` with no constraints. + let sized_predicate = ty::Binder::dummy(tcx.at(DUMMY_SP).mk_trait_ref( + LangItem::Sized, + [ty::GenericArg::from(goal.predicate.self_ty())], + )); + + let (_, is_sized_certainty) = + ecx.evaluate_goal(goal.with(tcx, sized_predicate))?; + return ecx.eq_term_and_make_canonical_response( + goal, + is_sized_certainty, + tcx.types.unit, + ); + } + + ty::Adt(def, substs) if def.is_struct() => { + match def.non_enum_variant().fields.last() { + None => tcx.types.unit, + Some(field_def) => { + let self_ty = field_def.ty(tcx, substs); + let new_goal = goal.with( + tcx, + ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)), + ); + let (_, certainty) = ecx.evaluate_goal(new_goal)?; + return ecx.make_canonical_response(certainty); + } + } + } + ty::Adt(_, _) => tcx.types.unit, + + ty::Tuple(elements) => match elements.last() { + None => tcx.types.unit, + Some(&self_ty) => { + let new_goal = goal.with( + tcx, + ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)), + ); + let (_, certainty) = ecx.evaluate_goal(new_goal)?; + return ecx.make_canonical_response(certainty); + } + }, + + ty::Infer( + ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_), + ) + | ty::Bound(..) => bug!( + "unexpected self ty `{:?}` when normalizing `<T as Pointee>::Metadata`", + goal.predicate.self_ty() + ), + }; + + ecx.eq_term_and_make_canonical_response(goal, Certainty::Yes, metadata_ty) + }) + } + + fn consider_builtin_future_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let self_ty = goal.predicate.self_ty(); + let ty::Generator(def_id, substs, _) = *self_ty.kind() else { + return Err(NoSolution); + }; + + // Generators are not futures unless they come from `async` desugaring + let tcx = ecx.tcx(); + if !tcx.generator_is_async(def_id) { + return Err(NoSolution); + } + + let term = substs.as_generator().return_ty().into(); + + Self::consider_implied_clause( + ecx, + goal, + ty::Binder::dummy(ty::ProjectionPredicate { + projection_ty: ecx.tcx().mk_alias_ty(goal.predicate.def_id(), [self_ty]), + term, + }) + .to_predicate(tcx), + // Technically, we need to check that the future type is Sized, + // but that's already proven by the generator being WF. + [], + ) + } + + fn consider_builtin_generator_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let self_ty = goal.predicate.self_ty(); + let ty::Generator(def_id, substs, _) = *self_ty.kind() else { + return Err(NoSolution); + }; + + // `async`-desugared generators do not implement the generator trait + let tcx = ecx.tcx(); + if tcx.generator_is_async(def_id) { + return Err(NoSolution); + } + + let generator = substs.as_generator(); + + let name = tcx.associated_item(goal.predicate.def_id()).name; + let term = if name == sym::Return { + generator.return_ty().into() + } else if name == sym::Yield { + generator.yield_ty().into() + } else { + bug!("unexpected associated item `<{self_ty} as Generator>::{name}`") + }; + + Self::consider_implied_clause( + ecx, + goal, + ty::Binder::dummy(ty::ProjectionPredicate { + projection_ty: ecx + .tcx() + .mk_alias_ty(goal.predicate.def_id(), [self_ty, generator.resume_ty()]), + term, + }) + .to_predicate(tcx), + // Technically, we need to check that the future type is Sized, + // but that's already proven by the generator being WF. + [], + ) + } + + fn consider_builtin_unsize_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Unsize` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_dyn_upcast_candidates( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> Vec<super::CanonicalResponse<'tcx>> { + bug!("`Unsize` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_discriminant_kind_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let discriminant = goal.predicate.self_ty().discriminant_ty(ecx.tcx()); + ecx.probe(|ecx| ecx.eq_term_and_make_canonical_response(goal, Certainty::Yes, discriminant)) + } } /// This behavior is also implemented in `rustc_ty_utils` and in the old `project` code. diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs index 730a8e612..86b13c05f 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs @@ -95,7 +95,7 @@ impl<'tcx> ProvisionalCache<'tcx> { } pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> QueryResult<'tcx> { - self.entries[entry_index].response.clone() + self.entries[entry_index].response } } diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs index 0030e9aa3..c7eb8de65 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -3,11 +3,12 @@ mod overflow; use self::cache::ProvisionalEntry; use super::{CanonicalGoal, Certainty, MaybeCause, QueryResult}; +pub(super) use crate::solve::search_graph::overflow::OverflowHandler; use cache::ProvisionalCache; use overflow::OverflowData; use rustc_index::vec::IndexVec; use rustc_middle::ty::TyCtxt; -use std::collections::hash_map::Entry; +use std::{collections::hash_map::Entry, mem}; rustc_index::newtype_index! { pub struct StackDepth {} @@ -42,10 +43,29 @@ impl<'tcx> SearchGraph<'tcx> { && !self.overflow_data.did_overflow() } + /// Whether we're currently in a cycle. This should only be used + /// for debug assertions. + pub(super) fn in_cycle(&self) -> bool { + if let Some(stack_depth) = self.stack.last() { + // Either the current goal on the stack is the root of a cycle... + if self.stack[stack_depth].has_been_used { + return true; + } + + // ...or it depends on a goal with a lower depth. + let current_goal = self.stack[stack_depth].goal; + let entry_index = self.provisional_cache.lookup_table[¤t_goal]; + self.provisional_cache.entries[entry_index].depth != stack_depth + } else { + false + } + } + /// Tries putting the new goal on the stack, returning an error if it is already cached. /// /// This correctly updates the provisional cache if there is a cycle. - pub(super) fn try_push_stack( + #[instrument(level = "debug", skip(self, tcx), ret)] + fn try_push_stack( &mut self, tcx: TyCtxt<'tcx>, goal: CanonicalGoal<'tcx>, @@ -79,8 +99,10 @@ impl<'tcx> SearchGraph<'tcx> { Entry::Occupied(entry_index) => { let entry_index = *entry_index.get(); - cache.add_dependency_of_leaf_on(entry_index); let stack_depth = cache.depth(entry_index); + debug!("encountered cycle with depth {stack_depth:?}"); + + cache.add_dependency_of_leaf_on(entry_index); self.stack[stack_depth].has_been_used = true; // NOTE: The goals on the stack aren't the only goals involved in this cycle. @@ -117,25 +139,29 @@ impl<'tcx> SearchGraph<'tcx> { /// updated the provisional cache and we have to recompute the current goal. /// /// FIXME: Refer to the rustc-dev-guide entry once it exists. - pub(super) fn try_finalize_goal( + #[instrument(level = "debug", skip(self, tcx, actual_goal), ret)] + fn try_finalize_goal( &mut self, tcx: TyCtxt<'tcx>, actual_goal: CanonicalGoal<'tcx>, response: QueryResult<'tcx>, ) -> bool { - let StackElem { goal, has_been_used } = self.stack.pop().unwrap(); + let stack_elem = self.stack.pop().unwrap(); + let StackElem { goal, has_been_used } = stack_elem; assert_eq!(goal, actual_goal); let cache = &mut self.provisional_cache; let provisional_entry_index = *cache.lookup_table.get(&goal).unwrap(); let provisional_entry = &mut cache.entries[provisional_entry_index]; - let depth = provisional_entry.depth; + // We eagerly update the response in the cache here. If we have to reevaluate + // this goal we use the new response when hitting a cycle, and we definitely + // want to access the final response whenever we look at the cache. + let prev_response = mem::replace(&mut provisional_entry.response, response); + // Was the current goal the root of a cycle and was the provisional response // different from the final one. - if has_been_used && provisional_entry.response != response { - // If so, update the provisional reponse for this goal... - provisional_entry.response = response; - // ...remove all entries whose result depends on this goal + if has_been_used && prev_response != response { + // If so, remove all entries whose result depends on this goal // from the provisional cache... // // That's not completely correct, as a nested goal can also @@ -150,29 +176,72 @@ impl<'tcx> SearchGraph<'tcx> { self.stack.push(StackElem { goal, has_been_used: false }); false } else { - // If not, we're done with this goal. - // - // Check whether that this goal doesn't depend on a goal deeper on the stack - // and if so, move it and all nested goals to the global cache. - // - // Note that if any nested goal were to depend on something deeper on the stack, - // this would have also updated the depth of the current goal. - if depth == self.stack.next_index() { - for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..) - { - let actual_index = cache.lookup_table.remove(&entry.goal); - debug_assert_eq!(Some(i), actual_index); - debug_assert!(entry.depth == depth); - cache::try_move_finished_goal_to_global_cache( - tcx, - &mut self.overflow_data, - &self.stack, - entry.goal, - entry.response, - ); - } - } + self.try_move_finished_goal_to_global_cache(tcx, stack_elem); true } } + + fn try_move_finished_goal_to_global_cache( + &mut self, + tcx: TyCtxt<'tcx>, + stack_elem: StackElem<'tcx>, + ) { + let StackElem { goal, .. } = stack_elem; + let cache = &mut self.provisional_cache; + let provisional_entry_index = *cache.lookup_table.get(&goal).unwrap(); + let provisional_entry = &mut cache.entries[provisional_entry_index]; + let depth = provisional_entry.depth; + + // If not, we're done with this goal. + // + // Check whether that this goal doesn't depend on a goal deeper on the stack + // and if so, move it and all nested goals to the global cache. + // + // Note that if any nested goal were to depend on something deeper on the stack, + // this would have also updated the depth of the current goal. + if depth == self.stack.next_index() { + for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..) { + let actual_index = cache.lookup_table.remove(&entry.goal); + debug_assert_eq!(Some(i), actual_index); + debug_assert!(entry.depth == depth); + cache::try_move_finished_goal_to_global_cache( + tcx, + &mut self.overflow_data, + &self.stack, + entry.goal, + entry.response, + ); + } + } + } + + pub(super) fn with_new_goal( + &mut self, + tcx: TyCtxt<'tcx>, + canonical_goal: CanonicalGoal<'tcx>, + mut loop_body: impl FnMut(&mut Self) -> QueryResult<'tcx>, + ) -> QueryResult<'tcx> { + match self.try_push_stack(tcx, canonical_goal) { + Ok(()) => {} + // Our goal is already on the stack, eager return. + Err(response) => return response, + } + + self.repeat_while_none( + |this| { + let result = this.deal_with_overflow(tcx, canonical_goal); + let stack_elem = this.stack.pop().unwrap(); + this.try_move_finished_goal_to_global_cache(tcx, stack_elem); + result + }, + |this| { + let result = loop_body(this); + if this.try_finalize_goal(tcx, canonical_goal, result) { + Some(result) + } else { + None + } + }, + ) + } } diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs index 1dd3894c9..56409b060 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs @@ -50,6 +50,42 @@ impl OverflowData { } } +pub(in crate::solve) trait OverflowHandler<'tcx> { + fn search_graph(&mut self) -> &mut SearchGraph<'tcx>; + + fn repeat_while_none<T>( + &mut self, + on_overflow: impl FnOnce(&mut Self) -> Result<T, NoSolution>, + mut loop_body: impl FnMut(&mut Self) -> Option<Result<T, NoSolution>>, + ) -> Result<T, NoSolution> { + let start_depth = self.search_graph().overflow_data.additional_depth; + let depth = self.search_graph().stack.len(); + while !self.search_graph().overflow_data.has_overflow(depth) { + if let Some(result) = loop_body(self) { + self.search_graph().overflow_data.additional_depth = start_depth; + return result; + } + + self.search_graph().overflow_data.additional_depth += 1; + } + self.search_graph().overflow_data.additional_depth = start_depth; + self.search_graph().overflow_data.deal_with_overflow(); + on_overflow(self) + } +} + +impl<'tcx> OverflowHandler<'tcx> for EvalCtxt<'_, 'tcx> { + fn search_graph(&mut self) -> &mut SearchGraph<'tcx> { + &mut self.search_graph + } +} + +impl<'tcx> OverflowHandler<'tcx> for SearchGraph<'tcx> { + fn search_graph(&mut self) -> &mut SearchGraph<'tcx> { + self + } +} + impl<'tcx> SearchGraph<'tcx> { pub fn deal_with_overflow( &mut self, @@ -60,25 +96,3 @@ impl<'tcx> SearchGraph<'tcx> { response_no_constraints(tcx, goal, Certainty::Maybe(MaybeCause::Overflow)) } } - -impl<'tcx> EvalCtxt<'_, 'tcx> { - /// A `while`-loop which tracks overflow. - pub fn repeat_while_none( - &mut self, - mut loop_body: impl FnMut(&mut Self) -> Option<Result<Certainty, NoSolution>>, - ) -> Result<Certainty, NoSolution> { - let start_depth = self.search_graph.overflow_data.additional_depth; - let depth = self.search_graph.stack.len(); - while !self.search_graph.overflow_data.has_overflow(depth) { - if let Some(result) = loop_body(self) { - self.search_graph.overflow_data.additional_depth = start_depth; - return result; - } - - self.search_graph.overflow_data.additional_depth += 1; - } - self.search_graph.overflow_data.additional_depth = start_depth; - self.search_graph.overflow_data.deal_with_overflow(); - Ok(Certainty::Maybe(MaybeCause::Overflow)) - } -} diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs index 9985d7181..5c499c36e 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -2,15 +2,15 @@ use std::iter; -use super::assembly::{self, Candidate, CandidateSource}; -use super::infcx_ext::InferCtxtExt; -use super::{Certainty, EvalCtxt, Goal, MaybeCause, QueryResult}; +use super::assembly; +use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, QueryResult}; use rustc_hir::def_id::DefId; -use rustc_infer::infer::InferCtxt; +use rustc_hir::LangItem; use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::util::supertraits; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt}; -use rustc_middle::ty::{TraitPredicate, TypeVisitable}; +use rustc_middle::ty::{TraitPredicate, TypeVisitableExt}; use rustc_span::DUMMY_SP; pub mod structural_traits; @@ -43,12 +43,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { return Err(NoSolution); } - ecx.infcx.probe(|_| { - let impl_substs = ecx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id); + ecx.probe(|ecx| { + let impl_substs = ecx.fresh_substs_for_item(impl_def_id); let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); let mut nested_goals = - ecx.infcx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?; + ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?; let where_clause_bounds = tcx .predicates_of(impl_def_id) .instantiate(tcx, impl_substs) @@ -60,21 +60,65 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { }) } - fn consider_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> { - if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred() { + if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred() + && poly_trait_pred.def_id() == goal.predicate.def_id() + { // FIXME: Constness and polarity - ecx.infcx.probe(|_| { + ecx.probe(|ecx| { let assumption_trait_pred = - ecx.infcx.instantiate_bound_vars_with_infer(poly_trait_pred); - let nested_goals = ecx.infcx.eq( + ecx.instantiate_binder_with_infer(poly_trait_pred); + let mut nested_goals = ecx.eq( goal.param_env, goal.predicate.trait_ref, assumption_trait_pred.trait_ref, )?; + nested_goals.extend(requirements); + ecx.evaluate_all_and_make_canonical_response(nested_goals) + }) + } else { + Err(NoSolution) + } + } + + fn consider_object_bound_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + assumption: ty::Predicate<'tcx>, + ) -> QueryResult<'tcx> { + if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred() + && poly_trait_pred.def_id() == goal.predicate.def_id() + { + // FIXME: Constness and polarity + ecx.probe(|ecx| { + let assumption_trait_pred = + ecx.instantiate_binder_with_infer(poly_trait_pred); + let mut nested_goals = ecx.eq( + goal.param_env, + goal.predicate.trait_ref, + assumption_trait_pred.trait_ref, + )?; + + let tcx = ecx.tcx(); + let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { + bug!("expected object type in `consider_object_bound_candidate`"); + }; + nested_goals.extend( + structural_traits::predicates_for_object_candidate( + ecx, + goal.param_env, + goal.predicate.trait_ref, + bounds, + ) + .into_iter() + .map(|pred| goal.with(tcx, pred)), + ); + ecx.evaluate_all_and_make_canonical_response(nested_goals) }) } else { @@ -86,6 +130,20 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { + // This differs from the current stable behavior and + // fixes #84857. Due to breakage found via crater, we + // currently instead lint patterns which can be used to + // exploit this unsoundness on stable, see #93367 for + // more details. + if let Some(def_id) = ecx.tcx().find_map_relevant_impl( + goal.predicate.def_id(), + goal.predicate.self_ty(), + Some, + ) { + debug!(?def_id, ?goal, "disqualified auto-trait implementation"); + return Err(NoSolution); + } + ecx.probe_and_evaluate_goal_for_constituent_tys( goal, structural_traits::instantiate_constituent_tys_for_auto_trait, @@ -98,7 +156,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ) -> QueryResult<'tcx> { let tcx = ecx.tcx(); - ecx.infcx.probe(|_| { + ecx.probe(|ecx| { let nested_obligations = tcx .predicates_of(goal.predicate.def_id()) .instantiate(tcx, goal.predicate.trait_ref.substs); @@ -128,12 +186,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ) } - fn consider_builtin_pointer_sized_candidate( + fn consider_builtin_pointer_like_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { if goal.predicate.self_ty().has_non_region_infer() { - return ecx.make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity)); + return ecx.make_canonical_response(Certainty::AMBIGUOUS); } let tcx = ecx.tcx(); @@ -156,23 +214,26 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { goal: Goal<'tcx, Self>, goal_kind: ty::ClosureKind, ) -> QueryResult<'tcx> { - if let Some(tupled_inputs_and_output) = + let tcx = ecx.tcx(); + let Some(tupled_inputs_and_output) = structural_traits::extract_tupled_inputs_and_output_from_callable( - ecx.tcx(), + tcx, goal.predicate.self_ty(), goal_kind, - )? - { - let pred = tupled_inputs_and_output - .map_bound(|(inputs, _)| { - ecx.tcx() - .mk_trait_ref(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs]) - }) - .to_predicate(ecx.tcx()); - Self::consider_assumption(ecx, goal, pred) - } else { - ecx.make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity)) - } + )? else { + return ecx.make_canonical_response(Certainty::AMBIGUOUS); + }; + let output_is_sized_pred = tupled_inputs_and_output + .map_bound(|(_, output)| tcx.at(DUMMY_SP).mk_trait_ref(LangItem::Sized, [output])); + + let pred = tupled_inputs_and_output + .map_bound(|(inputs, _)| { + tcx.mk_trait_ref(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs]) + }) + .to_predicate(tcx); + // A built-in `Fn` impl only holds if the output is sized. + // (FIXME: technically we only need to check this if the type is a fn ptr...) + Self::consider_implied_clause(ecx, goal, pred, [goal.with(tcx, output_is_sized_pred)]) } fn consider_builtin_tuple_candidate( @@ -185,6 +246,272 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { Err(NoSolution) } } + + fn consider_builtin_pointee_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + _goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + ecx.make_canonical_response(Certainty::Yes) + } + + fn consider_builtin_future_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let ty::Generator(def_id, _, _) = *goal.predicate.self_ty().kind() else { + return Err(NoSolution); + }; + + // Generators are not futures unless they come from `async` desugaring + let tcx = ecx.tcx(); + if !tcx.generator_is_async(def_id) { + return Err(NoSolution); + } + + // Async generator unconditionally implement `Future` + // Technically, we need to check that the future output type is Sized, + // but that's already proven by the generator being WF. + ecx.make_canonical_response(Certainty::Yes) + } + + fn consider_builtin_generator_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let self_ty = goal.predicate.self_ty(); + let ty::Generator(def_id, substs, _) = *self_ty.kind() else { + return Err(NoSolution); + }; + + // `async`-desugared generators do not implement the generator trait + let tcx = ecx.tcx(); + if tcx.generator_is_async(def_id) { + return Err(NoSolution); + } + + let generator = substs.as_generator(); + Self::consider_implied_clause( + ecx, + goal, + ty::Binder::dummy( + tcx.mk_trait_ref(goal.predicate.def_id(), [self_ty, generator.resume_ty()]), + ) + .to_predicate(tcx), + // Technically, we need to check that the generator types are Sized, + // but that's already proven by the generator being WF. + [], + ) + } + + fn consider_builtin_unsize_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let tcx = ecx.tcx(); + let a_ty = goal.predicate.self_ty(); + let b_ty = goal.predicate.trait_ref.substs.type_at(1); + if b_ty.is_ty_var() { + return ecx.make_canonical_response(Certainty::AMBIGUOUS); + } + ecx.probe(|ecx| { + match (a_ty.kind(), b_ty.kind()) { + // Trait upcasting, or `dyn Trait + Auto + 'a` -> `dyn Trait + 'b` + (&ty::Dynamic(_, _, ty::Dyn), &ty::Dynamic(_, _, ty::Dyn)) => { + // Dyn upcasting is handled separately, since due to upcasting, + // when there are two supertraits that differ by substs, we + // may return more than one query response. + return Err(NoSolution); + } + // `T` -> `dyn Trait` unsizing + (_, &ty::Dynamic(data, region, ty::Dyn)) => { + // Can only unsize to an object-safe type + if data + .principal_def_id() + .map_or(false, |def_id| !tcx.check_is_object_safe(def_id)) + { + return Err(NoSolution); + } + + let Some(sized_def_id) = tcx.lang_items().sized_trait() else { + return Err(NoSolution); + }; + let nested_goals: Vec<_> = data + .iter() + // Check that the type implements all of the predicates of the def-id. + // (i.e. the principal, all of the associated types match, and any auto traits) + .map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty))) + .chain([ + // The type must be Sized to be unsized. + goal.with( + tcx, + ty::Binder::dummy(tcx.mk_trait_ref(sized_def_id, [a_ty])), + ), + // The type must outlive the lifetime of the `dyn` we're unsizing into. + goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region))), + ]) + .collect(); + + ecx.evaluate_all_and_make_canonical_response(nested_goals) + } + // `[T; n]` -> `[T]` unsizing + (&ty::Array(a_elem_ty, ..), &ty::Slice(b_elem_ty)) => { + // We just require that the element type stays the same + let nested_goals = ecx.eq(goal.param_env, a_elem_ty, b_elem_ty)?; + ecx.evaluate_all_and_make_canonical_response(nested_goals) + } + // Struct unsizing `Struct<T>` -> `Struct<U>` where `T: Unsize<U>` + (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs)) + if a_def.is_struct() && a_def.did() == b_def.did() => + { + let unsizing_params = tcx.unsizing_params_for_adt(a_def.did()); + // We must be unsizing some type parameters. This also implies + // that the struct has a tail field. + if unsizing_params.is_empty() { + return Err(NoSolution); + } + + let tail_field = a_def + .non_enum_variant() + .fields + .last() + .expect("expected unsized ADT to have a tail field"); + let tail_field_ty = tcx.type_of(tail_field.did); + + let a_tail_ty = tail_field_ty.subst(tcx, a_substs); + let b_tail_ty = tail_field_ty.subst(tcx, b_substs); + + // Substitute just the unsizing params from B into A. The type after + // this substitution must be equal to B. This is so we don't unsize + // unrelated type parameters. + let new_a_substs = + tcx.mk_substs_from_iter(a_substs.iter().enumerate().map(|(i, a)| { + if unsizing_params.contains(i as u32) { b_substs[i] } else { a } + })); + let unsized_a_ty = tcx.mk_adt(a_def, new_a_substs); + + // Finally, we require that `TailA: Unsize<TailB>` for the tail field + // types. + let mut nested_goals = ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; + nested_goals.push(goal.with( + tcx, + ty::Binder::dummy( + tcx.mk_trait_ref(goal.predicate.def_id(), [a_tail_ty, b_tail_ty]), + ), + )); + + ecx.evaluate_all_and_make_canonical_response(nested_goals) + } + // Tuple unsizing `(.., T)` -> `(.., U)` where `T: Unsize<U>` + (&ty::Tuple(a_tys), &ty::Tuple(b_tys)) + if a_tys.len() == b_tys.len() && !a_tys.is_empty() => + { + let (a_last_ty, a_rest_tys) = a_tys.split_last().unwrap(); + let b_last_ty = b_tys.last().unwrap(); + + // Substitute just the tail field of B., and require that they're equal. + let unsized_a_ty = + tcx.mk_tup_from_iter(a_rest_tys.iter().chain([b_last_ty]).copied()); + let mut nested_goals = ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; + + // Similar to ADTs, require that the rest of the fields are equal. + nested_goals.push(goal.with( + tcx, + ty::Binder::dummy( + tcx.mk_trait_ref(goal.predicate.def_id(), [*a_last_ty, *b_last_ty]), + ), + )); + + ecx.evaluate_all_and_make_canonical_response(nested_goals) + } + _ => Err(NoSolution), + } + }) + } + + fn consider_builtin_dyn_upcast_candidates( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> Vec<CanonicalResponse<'tcx>> { + let tcx = ecx.tcx(); + + let a_ty = goal.predicate.self_ty(); + let b_ty = goal.predicate.trait_ref.substs.type_at(1); + let ty::Dynamic(a_data, a_region, ty::Dyn) = *a_ty.kind() else { + return vec![]; + }; + let ty::Dynamic(b_data, b_region, ty::Dyn) = *b_ty.kind() else { + return vec![]; + }; + + // All of a's auto traits need to be in b's auto traits. + let auto_traits_compatible = + b_data.auto_traits().all(|b| a_data.auto_traits().any(|a| a == b)); + if !auto_traits_compatible { + return vec![]; + } + + let mut unsize_dyn_to_principal = |principal: Option<ty::PolyExistentialTraitRef<'tcx>>| { + ecx.probe(|ecx| -> Result<_, NoSolution> { + // Require that all of the trait predicates from A match B, except for + // the auto traits. We do this by constructing a new A type with B's + // auto traits, and equating these types. + let new_a_data = principal + .into_iter() + .map(|trait_ref| trait_ref.map_bound(ty::ExistentialPredicate::Trait)) + .chain(a_data.iter().filter(|a| { + matches!(a.skip_binder(), ty::ExistentialPredicate::Projection(_)) + })) + .chain( + b_data + .auto_traits() + .map(ty::ExistentialPredicate::AutoTrait) + .map(ty::Binder::dummy), + ); + let new_a_data = tcx.mk_poly_existential_predicates_from_iter(new_a_data); + let new_a_ty = tcx.mk_dynamic(new_a_data, b_region, ty::Dyn); + + // We also require that A's lifetime outlives B's lifetime. + let mut nested_obligations = ecx.eq(goal.param_env, new_a_ty, b_ty)?; + nested_obligations.push( + goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region))), + ); + + ecx.evaluate_all_and_make_canonical_response(nested_obligations) + }) + }; + + let mut responses = vec![]; + // If the principal def ids match (or are both none), then we're not doing + // trait upcasting. We're just removing auto traits (or shortening the lifetime). + if a_data.principal_def_id() == b_data.principal_def_id() { + if let Ok(response) = unsize_dyn_to_principal(a_data.principal()) { + responses.push(response); + } + } else if let Some(a_principal) = a_data.principal() + && let Some(b_principal) = b_data.principal() + { + for super_trait_ref in supertraits(tcx, a_principal.with_self_ty(tcx, a_ty)) { + if super_trait_ref.def_id() != b_principal.def_id() { + continue; + } + let erased_trait_ref = super_trait_ref + .map_bound(|trait_ref| ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref)); + if let Ok(response) = unsize_dyn_to_principal(Some(erased_trait_ref)) { + responses.push(response); + } + } + } + + responses + } + + fn consider_builtin_discriminant_kind_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + _goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + // `DiscriminantKind` is automatically implemented for every type. + ecx.make_canonical_response(Certainty::Yes) + } } impl<'tcx> EvalCtxt<'_, 'tcx> { @@ -195,16 +522,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { fn probe_and_evaluate_goal_for_constituent_tys( &mut self, goal: Goal<'tcx, TraitPredicate<'tcx>>, - constituent_tys: impl Fn(&InferCtxt<'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>, + constituent_tys: impl Fn(&EvalCtxt<'_, 'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>, ) -> QueryResult<'tcx> { - self.infcx.probe(|_| { - self.evaluate_all_and_make_canonical_response( - constituent_tys(self.infcx, goal.predicate.self_ty())? + self.probe(|this| { + this.evaluate_all_and_make_canonical_response( + constituent_tys(this, goal.predicate.self_ty())? .into_iter() .map(|ty| { goal.with( - self.tcx(), - ty::Binder::dummy(goal.predicate.with_self_ty(self.tcx(), ty)), + this.tcx(), + ty::Binder::dummy(goal.predicate.with_self_ty(this.tcx(), ty)), ) }) .collect(), @@ -217,73 +544,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal: Goal<'tcx, TraitPredicate<'tcx>>, ) -> QueryResult<'tcx> { let candidates = self.assemble_and_evaluate_candidates(goal); - self.merge_trait_candidates_discard_reservation_impls(candidates) - } - - #[instrument(level = "debug", skip(self), ret)] - pub(super) fn merge_trait_candidates_discard_reservation_impls( - &mut self, - mut candidates: Vec<Candidate<'tcx>>, - ) -> QueryResult<'tcx> { - match candidates.len() { - 0 => return Err(NoSolution), - 1 => return Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result), - _ => {} - } - - if candidates.len() > 1 { - let mut i = 0; - 'outer: while i < candidates.len() { - for j in (0..candidates.len()).filter(|&j| i != j) { - if self.trait_candidate_should_be_dropped_in_favor_of( - &candidates[i], - &candidates[j], - ) { - debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len()); - candidates.swap_remove(i); - continue 'outer; - } - } - - debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len()); - // If there are *STILL* multiple candidates, give up - // and report ambiguity. - i += 1; - if i > 1 { - debug!("multiple matches, ambig"); - // FIXME: return overflow if all candidates overflow, otherwise return ambiguity. - unimplemented!(); - } - } - } - - Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result) - } - - fn trait_candidate_should_be_dropped_in_favor_of( - &self, - candidate: &Candidate<'tcx>, - other: &Candidate<'tcx>, - ) -> bool { - // FIXME: implement this - match (candidate.source, other.source) { - (CandidateSource::Impl(_), _) - | (CandidateSource::ParamEnv(_), _) - | (CandidateSource::AliasBound(_), _) - | (CandidateSource::BuiltinImpl, _) => unimplemented!(), - } - } - - fn discard_reservation_impl(&self, candidate: Candidate<'tcx>) -> Candidate<'tcx> { - if let CandidateSource::Impl(def_id) = candidate.source { - if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) { - debug!("Selected reservation impl"); - // FIXME: reduce candidate to ambiguous - // FIXME: replace `var_values` with identity, yeet external constraints. - unimplemented!() - } - } - - candidate + self.merge_candidates_and_discard_reservation_impls(candidates) } } diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs index a11cd13cb..d7d93377c 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs @@ -1,16 +1,19 @@ -use rustc_hir::{Movability, Mutability}; -use rustc_infer::{infer::InferCtxt, traits::query::NoSolution}; -use rustc_middle::ty::{self, Ty, TyCtxt}; +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}; + +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(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>( - infcx: &InferCtxt<'tcx>, + ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, ) -> Result<Vec<Ty<'tcx>>, NoSolution> { - let tcx = infcx.tcx; + let tcx = ecx.tcx(); match *ty.kind() { ty::Uint(_) | ty::Int(_) @@ -18,21 +21,24 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>( | ty::Float(_) | ty::FnDef(..) | ty::FnPtr(_) - | ty::Str | ty::Error(_) | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) | ty::Never | ty::Char => Ok(vec![]), - ty::Placeholder(..) - | ty::Dynamic(..) + // Treat this like `struct str([u8]);` + ty::Str => Ok(vec![tcx.mk_slice(tcx.types.u8)]), + + ty::Dynamic(..) | ty::Param(..) | ty::Foreign(..) | ty::Alias(ty::Projection, ..) - | ty::Bound(..) - | ty::Infer(ty::TyVar(_)) => Err(NoSolution), + | ty::Placeholder(..) => Err(NoSolution), - ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(), + ty::Bound(..) + | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { + bug!("unexpected type `{ty}`") + } ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => { Ok(vec![element_ty]) @@ -52,9 +58,9 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>( Ok(vec![generator_substs.tupled_upvars_ty(), generator_substs.witness()]) } - ty::GeneratorWitness(types) => { - Ok(infcx.replace_bound_vars_with_placeholders(types).to_vec()) - } + ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), + + ty::GeneratorWitnessMIR(..) => todo!(), // For `PhantomData<T>`, we pass `T`. ty::Adt(def, substs) if def.is_phantom_data() => Ok(vec![substs.type_at(0)]), @@ -65,13 +71,13 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>( // 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.bound_type_of(def_id).subst(tcx, substs)]) + Ok(vec![tcx.type_of(def_id).subst(tcx, substs)]) } } } pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>( - infcx: &InferCtxt<'tcx>, + ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, ) -> Result<Vec<Ty<'tcx>>, NoSolution> { match *ty.kind() { @@ -87,6 +93,7 @@ pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>( | ty::Ref(..) | ty::Generator(..) | ty::GeneratorWitness(..) + | ty::GeneratorWitnessMIR(..) | ty::Array(..) | ty::Closure(..) | ty::Never @@ -99,27 +106,28 @@ pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>( | ty::Foreign(..) | ty::Alias(..) | ty::Param(_) - | ty::Infer(ty::TyVar(_)) => Err(NoSolution), + | ty::Placeholder(..) => Err(NoSolution), - ty::Placeholder(..) - | ty::Bound(..) - | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(), + 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(infcx.tcx); + let sized_crit = def.sized_constraint(ecx.tcx()); Ok(sized_crit .0 .iter() - .map(|ty| sized_crit.rebind(*ty).subst(infcx.tcx, substs)) + .map(|ty| sized_crit.rebind(*ty).subst(ecx.tcx(), substs)) .collect()) } } } pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( - infcx: &InferCtxt<'tcx>, + ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, ) -> Result<Vec<Ty<'tcx>>, NoSolution> { match *ty.kind() { @@ -148,18 +156,19 @@ pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( | ty::Adt(_, _) | ty::Alias(_, _) | ty::Param(_) - | ty::Infer(ty::TyVar(_)) => Err(NoSolution), + | ty::Placeholder(..) => Err(NoSolution), - ty::Placeholder(..) - | ty::Bound(..) - | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(), + 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 infcx.tcx.features().generator_clone { + if ecx.tcx().features().generator_clone { let generator = substs.as_generator(); Ok(vec![generator.tupled_upvars_ty(), generator.witness()]) } else { @@ -167,12 +176,13 @@ pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( } } - ty::GeneratorWitness(types) => { - Ok(infcx.replace_bound_vars_with_placeholders(types).to_vec()) - } + ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), + + ty::GeneratorWitnessMIR(..) => todo!(), } } +// Returns a binder of the tupled inputs types and output type from a builtin callable type. pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>( tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>, @@ -180,13 +190,11 @@ pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>( ) -> Result<Option<ty::Binder<'tcx, (Ty<'tcx>, Ty<'tcx>)>>, NoSolution> { match *self_ty.kind() { ty::FnDef(def_id, substs) => Ok(Some( - tcx.bound_fn_sig(def_id) + tcx.fn_sig(def_id) .subst(tcx, substs) - .map_bound(|sig| (tcx.mk_tup(sig.inputs().iter()), sig.output())), + .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())), )), - ty::FnPtr(sig) => { - Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs().iter()), sig.output())))) - } + ty::FnPtr(sig) => Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())))), ty::Closure(_, substs) => { let closure_substs = substs.as_closure(); match closure_substs.kind_ty().to_opt_closure_kind() { @@ -211,13 +219,127 @@ pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>( | ty::Dynamic(_, _, _) | ty::Generator(_, _, _) | ty::GeneratorWitness(_) + | ty::GeneratorWitnessMIR(..) | ty::Never | ty::Tuple(_) | ty::Alias(_, _) | ty::Param(_) - | ty::Placeholder(_) - | ty::Bound(_, _) - | ty::Infer(_) + | 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. +pub(crate) 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(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) + } } } |