diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve')
10 files changed, 2301 insertions, 0 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs new file mode 100644 index 000000000..31c1bc9ec --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/assembly.rs @@ -0,0 +1,387 @@ +//! Code shared by trait and projection goals for candidate assembly. + +use super::infcx_ext::InferCtxtExt; +use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, MaybeCause, QueryResult}; +use rustc_hir::def_id::DefId; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::util::elaborate_predicates; +use rustc_middle::ty::TypeFoldable; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use std::fmt::Debug; + +/// A candidate is a possible way to prove a goal. +/// +/// It consists of both the `source`, which describes how that goal would be proven, +/// and the `result` when using the given `source`. +#[derive(Debug, Clone)] +pub(super) struct Candidate<'tcx> { + pub(super) source: CandidateSource, + pub(super) result: CanonicalResponse<'tcx>, +} + +/// Possible ways the given goal can be proven. +#[derive(Debug, Clone, Copy)] +pub(super) enum CandidateSource { + /// A user written impl. + /// + /// ## Examples + /// + /// ```rust + /// fn main() { + /// let x: Vec<u32> = Vec::new(); + /// // This uses the impl from the standard library to prove `Vec<T>: Clone`. + /// let y = x.clone(); + /// } + /// ``` + Impl(DefId), + /// A builtin impl generated by the compiler. When adding a new special + /// trait, try to use actual impls whenever possible. Builtin impls should + /// only be used in cases where the impl cannot be manually be written. + /// + /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`. + /// For a list of all traits with builtin impls, check out the + /// [`EvalCtxt::assemble_builtin_impl_candidates`] method. Not + BuiltinImpl, + /// An assumption from the environment. + /// + /// More precicely we've used the `n-th` assumption in the `param_env`. + /// + /// ## Examples + /// + /// ```rust + /// fn is_clone<T: Clone>(x: T) -> (T, T) { + /// // This uses the assumption `T: Clone` from the `where`-bounds + /// // to prove `T: Clone`. + /// (x.clone(), x) + /// } + /// ``` + ParamEnv(usize), + /// If the self type is an alias type, e.g. an opaque type or a projection, + /// we know the bounds on that alias to hold even without knowing its concrete + /// underlying type. + /// + /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of + /// the self type. + /// + /// ## Examples + /// + /// ```rust + /// trait Trait { + /// type Assoc: Clone; + /// } + /// + /// fn foo<T: Trait>(x: <T as Trait>::Assoc) { + /// // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in + /// // in the trait definition. + /// let _y = x.clone(); + /// } + /// ``` + AliasBound(usize), +} + +pub(super) trait GoalKind<'tcx>: TypeFoldable<'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( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + impl_def_id: DefId, + ) -> QueryResult<'tcx>; + + fn consider_assumption( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + assumption: ty::Predicate<'tcx>, + ) -> QueryResult<'tcx>; + + fn consider_auto_trait_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; + + fn consider_trait_alias_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; + + fn consider_builtin_sized_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; + + fn consider_builtin_copy_clone_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; + + fn consider_builtin_pointer_sized_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; + + fn consider_builtin_fn_trait_candidates( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + kind: ty::ClosureKind, + ) -> QueryResult<'tcx>; + + fn consider_builtin_tuple_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; +} + +impl<'tcx> EvalCtxt<'_, 'tcx> { + pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + ) -> Vec<Candidate<'tcx>> { + debug_assert_eq!(goal, self.infcx.resolve_vars_if_possible(goal)); + + // HACK: `_: Trait` is ambiguous, because it may be satisfied via a builtin rule, + // object bound, alias bound, etc. We are unable to determine this until we can at + // least structually resolve the type one layer. + if goal.predicate.self_ty().is_ty_var() { + return vec![Candidate { + source: CandidateSource::BuiltinImpl, + result: self + .make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity)) + .unwrap(), + }]; + } + + let mut candidates = Vec::new(); + + self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates); + + self.assemble_impl_candidates(goal, &mut candidates); + + self.assemble_builtin_impl_candidates(goal, &mut candidates); + + self.assemble_param_env_candidates(goal, &mut candidates); + + self.assemble_alias_bound_candidates(goal, &mut candidates); + + self.assemble_object_bound_candidates(goal, &mut candidates); + + candidates + } + + /// If the self type of a goal is a projection, computing the relevant candidates is difficult. + /// + /// To deal with this, we first try to normalize the self type and add the candidates for the normalized + /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in + /// this case as projections as self types add ` + fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + let tcx = self.tcx(); + // FIXME: We also have to normalize opaque types, not sure where to best fit that in. + let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else { + return + }; + self.infcx.probe(|_| { + let normalized_ty = self.infcx.next_ty_infer(); + let normalizes_to_goal = goal.with( + tcx, + ty::Binder::dummy(ty::ProjectionPredicate { + projection_ty, + term: normalized_ty.into(), + }), + ); + let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) { + Ok((_, certainty)) => certainty, + Err(NoSolution) => return, + }; + let normalized_ty = self.infcx.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); + for mut normalized_candidate in normalized_candidates { + normalized_candidate.result = + normalized_candidate.result.unchecked_map(|mut response| { + // FIXME: This currently hides overflow in the normalization step of the self type + // which is probably wrong. Maybe `unify_and` should actually keep overflow as + // we treat it as non-fatal anyways. + response.certainty = response.certainty.unify_and(normalization_certainty); + response + }); + candidates.push(normalized_candidate); + } + }) + } + + fn assemble_impl_candidates<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + let tcx = self.tcx(); + tcx.for_each_relevant_impl( + goal.predicate.trait_def_id(tcx), + goal.predicate.self_ty(), + |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) { + Ok(result) => candidates + .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }), + Err(NoSolution) => (), + }, + ); + } + + fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + let lang_items = self.tcx().lang_items(); + let trait_def_id = goal.predicate.trait_def_id(self.tcx()); + let result = if self.tcx().trait_is_auto(trait_def_id) { + G::consider_auto_trait_candidate(self, goal) + } else if self.tcx().trait_is_alias(trait_def_id) { + G::consider_trait_alias_candidate(self, goal) + } else if lang_items.sized_trait() == Some(trait_def_id) { + G::consider_builtin_sized_candidate(self, goal) + } else if lang_items.copy_trait() == Some(trait_def_id) + || lang_items.clone_trait() == Some(trait_def_id) + { + G::consider_builtin_copy_clone_candidate(self, goal) + } else if lang_items.pointer_sized() == Some(trait_def_id) { + G::consider_builtin_pointer_sized_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 { + Err(NoSolution) + }; + + match result { + Ok(result) => { + candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) + } + Err(NoSolution) => (), + } + } + + fn assemble_param_env_candidates<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() { + match G::consider_assumption(self, goal, assumption) { + Ok(result) => { + candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result }) + } + Err(NoSolution) => (), + } + } + } + + fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + let alias_ty = match goal.predicate.self_ty().kind() { + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Adt(_, _) + | ty::Foreign(_) + | ty::Str + | ty::Array(_, _) + | ty::Slice(_) + | ty::RawPtr(_) + | ty::Ref(_, _, _) + | ty::FnDef(_, _) + | ty::FnPtr(_) + | ty::Dynamic(..) + | ty::Closure(..) + | ty::Generator(..) + | ty::GeneratorWitness(_) + | ty::Never + | ty::Tuple(_) + | ty::Param(_) + | ty::Placeholder(..) + | ty::Infer(_) + | ty::Error(_) => return, + ty::Bound(..) => bug!("unexpected bound type: {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() + { + match G::consider_assumption(self, goal, assumption) { + Ok(result) => { + candidates.push(Candidate { source: CandidateSource::AliasBound(i), result }) + } + Err(NoSolution) => (), + } + } + } + + fn assemble_object_bound_candidates<G: GoalKind<'tcx>>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + let self_ty = goal.predicate.self_ty(); + let bounds = match *self_ty.kind() { + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Adt(_, _) + | ty::Foreign(_) + | ty::Str + | ty::Array(_, _) + | ty::Slice(_) + | ty::RawPtr(_) + | ty::Ref(_, _, _) + | ty::FnDef(_, _) + | ty::FnPtr(_) + | ty::Alias(..) + | ty::Closure(..) + | ty::Generator(..) + | ty::GeneratorWitness(_) + | ty::Never + | ty::Tuple(_) + | ty::Param(_) + | ty::Placeholder(..) + | ty::Infer(_) + | ty::Error(_) => return, + ty::Bound(..) => bug!("unexpected bound type: {goal:?}"), + ty::Dynamic(bounds, ..) => bounds, + }; + + let tcx = self.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) { + Ok(result) => { + candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) + } + Err(NoSolution) => (), + } + } + } +} diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs new file mode 100644 index 000000000..a6240666e --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs @@ -0,0 +1,109 @@ +use std::mem; + +use rustc_data_structures::fx::FxHashMap; +use rustc_infer::{ + infer::InferCtxt, + traits::{ + query::NoSolution, FulfillmentError, FulfillmentErrorCode, PredicateObligation, + SelectionError, TraitEngine, + }, +}; +use rustc_middle::ty; + +use super::{search_graph, Certainty, EvalCtxt}; + +/// A trait engine using the new trait solver. +/// +/// This is mostly identical to how `evaluate_all` works inside of the +/// solver, except that the requirements are slightly different. +/// +/// Unlike `evaluate_all` it is possible to add new obligations later on +/// and we also have to track diagnostics information by using `Obligation` +/// instead of `Goal`. +/// +/// It is also likely that we want to use slightly different datastructures +/// here as this will have to deal with far more root goals than `evaluate_all`. +pub struct FulfillmentCtxt<'tcx> { + obligations: Vec<PredicateObligation<'tcx>>, +} + +impl<'tcx> FulfillmentCtxt<'tcx> { + pub fn new() -> FulfillmentCtxt<'tcx> { + FulfillmentCtxt { obligations: Vec::new() } + } +} + +impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { + fn register_predicate_obligation( + &mut self, + _infcx: &InferCtxt<'tcx>, + obligation: PredicateObligation<'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; + } + + self.obligations + .drain(..) + .map(|obligation| FulfillmentError { + obligation: obligation.clone(), + code: FulfillmentErrorCode::CodeAmbiguity, + root_obligation: obligation, + }) + .collect() + } + + fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> { + let mut errors = Vec::new(); + for i in 0.. { + if !infcx.tcx.recursion_limit().value_within_limit(i) { + unimplemented!("overflowed on pending obligations: {:?}", self.obligations); + } + + 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) { + Ok(result) => result, + Err(NoSolution) => { + errors.push(FulfillmentError { + obligation: obligation.clone(), + code: FulfillmentErrorCode::CodeSelectionError( + SelectionError::Unimplemented, + ), + root_obligation: obligation, + }); + continue; + } + }; + + has_changed |= changed; + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => self.obligations.push(obligation), + } + } + + if !has_changed { + break; + } + } + + errors + } + + fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> { + self.obligations.clone() + } + + fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships> { + unimplemented!("Should be moved out of `TraitEngine`") + } +} diff --git a/compiler/rustc_trait_selection/src/solve/infcx_ext.rs b/compiler/rustc_trait_selection/src/solve/infcx_ext.rs new file mode 100644 index 000000000..42f597c78 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/infcx_ext.rs @@ -0,0 +1,78 @@ +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 new file mode 100644 index 000000000..32eb84635 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -0,0 +1,400 @@ +//! The new trait solver, currently still WIP. +//! +//! As a user of the trait system, you can use `TyCtxt::evaluate_goal` to +//! interact with this solver. +//! +//! For a high-level overview of how this solver works, check out the relevant +//! section of the rustc-dev-guide. +//! +//! FIXME(@lcnr): Write that section. If you read this before then ask me +//! about it on zulip. + +// FIXME: Instead of using `infcx.canonicalize_query` we have to add a new routine which +// 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_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::ty::{self, Ty, TyCtxt}; +use rustc_middle::ty::{RegionOutlivesPredicate, ToPredicate, TypeOutlivesPredicate}; +use rustc_span::DUMMY_SP; + +use crate::traits::ObligationCause; + +mod assembly; +mod fulfill; +mod infcx_ext; +mod project_goals; +mod search_graph; +mod trait_goals; + +pub use fulfill::FulfillmentCtxt; + +/// A goal is a statement, i.e. `predicate`, we want to prove +/// given some assumptions, i.e. `param_env`. +/// +/// Most of the time the `param_env` contains the `where`-bounds of the function +/// we're currently typechecking while the `predicate` is some trait bound. +#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] +pub struct Goal<'tcx, P> { + param_env: ty::ParamEnv<'tcx>, + predicate: P, +} + +impl<'tcx, P> Goal<'tcx, P> { + pub fn new( + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + predicate: impl ToPredicate<'tcx, P>, + ) -> Goal<'tcx, P> { + Goal { param_env, predicate: predicate.to_predicate(tcx) } + } + + /// Updates the goal to one with a different `predicate` but the same `param_env`. + fn with<Q>(self, tcx: TyCtxt<'tcx>, predicate: impl ToPredicate<'tcx, Q>) -> Goal<'tcx, Q> { + Goal { param_env: self.param_env, predicate: predicate.to_predicate(tcx) } + } +} + +impl<'tcx, P> From<Obligation<'tcx, P>> for Goal<'tcx, P> { + fn from(obligation: Obligation<'tcx, P>) -> Goal<'tcx, P> { + Goal { param_env: obligation.param_env, predicate: obligation.predicate } + } +} + +#[derive(Debug, PartialEq, Eq, Clone, Hash, TypeFoldable, TypeVisitable)] +pub struct Response<'tcx> { + pub var_values: CanonicalVarValues<'tcx>, + /// Additional constraints returned by this query. + pub external_constraints: ExternalConstraints<'tcx>, + pub certainty: Certainty, +} + +#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] +pub enum Certainty { + Yes, + Maybe(MaybeCause), +} + +impl Certainty { + /// 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 { + match (self, other) { + (Certainty::Yes, Certainty::Yes) => Certainty::Yes, + (Certainty::Yes, Certainty::Maybe(_)) => other, + (Certainty::Maybe(_), Certainty::Yes) => self, + (Certainty::Maybe(MaybeCause::Overflow), Certainty::Maybe(MaybeCause::Overflow)) => { + Certainty::Maybe(MaybeCause::Overflow) + } + // If at least one of the goals is ambiguous, hide the overflow as the ambiguous goal + // may still result in failure. + (Certainty::Maybe(MaybeCause::Ambiguity), Certainty::Maybe(_)) + | (Certainty::Maybe(_), Certainty::Maybe(MaybeCause::Ambiguity)) => { + Certainty::Maybe(MaybeCause::Ambiguity) + } + } + } +} + +/// Why we failed to evaluate a goal. +#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] +pub enum MaybeCause { + /// We failed due to ambiguity. This ambiguity can either + /// be a true ambiguity, i.e. there are multiple different answers, + /// or we hit a case where we just don't bother, e.g. `?x: Trait` goals. + Ambiguity, + /// We gave up due to an overflow, most often by hitting the recursion limit. + 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. +/// +/// FIXME: We use a different type than the existing canonical queries. This is because +/// we need to add a `Certainty` for `overflow` and may want to restructure this code without +/// having to worry about changes to currently used code. Once we've made progress on this +/// 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) + } +} + +struct EvalCtxt<'a, 'tcx> { + infcx: &'a InferCtxt<'tcx>, + var_values: CanonicalVarValues<'tcx>, + + search_graph: &'a mut search_graph::SearchGraph<'tcx>, +} + +impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { + fn tcx(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + /// Creates a new evaluation context outside of the trait 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 } + } + + #[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. + // + // FIXME: Similar to `evaluate_all`, this has to check for overflow. + loop { + 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, + })) + } + + /// Recursively evaluates `goal`, returning whether any inference vars have + /// been constrained and the certainty of the result. + fn evaluate_goal( + &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 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), + )) + } + + fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { + let Goal { param_env, predicate } = goal; + let kind = predicate.kind(); + if let Some(kind) = kind.no_bound_vars() { + match kind { + ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => { + self.compute_trait_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => { + self.compute_projection_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => { + self.compute_type_outlives_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => { + self.compute_region_outlives_goal(Goal { param_env, predicate }) + } + // 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), + } + } else { + let kind = self.infcx.replace_bound_vars_with_placeholders(kind); + let goal = goal.with(self.tcx(), ty::Binder::dummy(kind)); + let (_, certainty) = self.evaluate_goal(goal)?; + self.make_canonical_response(certainty) + } + } + + fn compute_type_outlives_goal( + &mut self, + _goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + self.make_canonical_response(Certainty::Yes) + } + + fn compute_region_outlives_goal( + &mut self, + _goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + self.make_canonical_response(Certainty::Yes) + } +} + +impl<'tcx> EvalCtxt<'_, 'tcx> { + 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(()); + } + + 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 + } + Err(certainty) => Some(Ok(certainty)), + } + }) + } + + 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 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 +} + +pub(super) fn response_no_constraints<'tcx>( + tcx: TyCtxt<'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(), + certainty, + }, + }) +} diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs new file mode 100644 index 000000000..e39fa0533 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -0,0 +1,430 @@ +use crate::traits::{specialization_graph, translate_substs}; + +use super::assembly::{self, Candidate, CandidateSource}; +use super::infcx_ext::InferCtxtExt; +use super::trait_goals::structural_traits; +use super::{Certainty, EvalCtxt, Goal, MaybeCause, QueryResult}; +use rustc_errors::ErrorGuaranteed; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::DefId; +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::{self, Ty, TyCtxt}; +use rustc_middle::ty::{ProjectionPredicate, TypeSuperVisitable, TypeVisitor}; +use rustc_middle::ty::{ToPredicate, TypeVisitable}; +use rustc_span::DUMMY_SP; +use std::iter; +use std::ops::ControlFlow; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + pub(super) fn compute_projection_goal( + &mut self, + goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + ) -> QueryResult<'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 + // `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) + } 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(), + }; + 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 nested_eq_goals = + self.infcx.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() + } + + fn merge_project_candidates( + &mut self, + mut candidates: Vec<Candidate<'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; + } + } + + 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(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!(), + } + } +} + +impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { + fn self_ty(self) -> Ty<'tcx> { + self.self_ty() + } + + fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self { + self.with_self_ty(tcx, self_ty) + } + + fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId { + self.trait_def_id(tcx) + } + + fn consider_impl_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + impl_def_id: DefId, + ) -> QueryResult<'tcx> { + let tcx = ecx.tcx(); + + let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx); + let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder }; + if iter::zip(goal_trait_ref.substs, impl_trait_ref.skip_binder().substs) + .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp)) + { + return Err(NoSolution); + } + + ecx.infcx.probe(|_| { + let impl_substs = ecx.infcx.fresh_substs_for_item(DUMMY_SP, 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 where_clause_bounds = tcx + .predicates_of(impl_def_id) + .instantiate(tcx, impl_substs) + .predicates + .into_iter() + .map(|pred| goal.with(tcx, pred)); + + nested_goals.extend(where_clause_bounds); + let trait_ref_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 + // unsoundness during coherence (#105782). + let Some(assoc_def) = fetch_eligible_assoc_item_def( + ecx.infcx, + goal.param_env, + goal_trait_ref, + 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)); + }; + + if !assoc_def.item.defaultness(tcx).has_value() { + tcx.sess.delay_span_bug( + tcx.def_span(assoc_def.item.def_id), + "missing value for assoc item in impl", + ); + } + + // Getting the right substitutions here is complex, e.g. given: + // - a goal `<Vec<u32> as Trait<i32>>::Assoc<u64>` + // - the applicable impl `impl<T> Trait<i32> for Vec<T>` + // - and the impl which defines `Assoc` being `impl<T, U> Trait<U> for Vec<T>` + // + // We first rebase the goal substs onto the impl, going from `[Vec<u32>, i32, u64]` + // to `[u32, u64]`. + // + // And then map these substs to the substs of the defining impl of `Assoc`, going + // from `[u32, u64]` to `[u32, i32, u64]`. + let impl_substs_with_gat = goal.predicate.projection_ty.substs.rebase_onto( + tcx, + goal_trait_ref.def_id, + impl_substs, + ); + let substs = translate_substs( + ecx.infcx, + goal.param_env, + impl_def_id, + impl_substs_with_gat, + assoc_def.defining_node, + ); + + // 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 term: ty::EarlyBinder<ty::Term<'tcx>> = if is_const { + let identity_substs = + ty::InternalSubsts::identity_for_item(tcx, assoc_def.item.def_id); + let did = ty::WithOptConstParam::unknown(assoc_def.item.def_id); + let kind = + ty::ConstKind::Unevaluated(ty::UnevaluatedConst::new(did, identity_substs)); + ty.map_bound(|ty| tcx.mk_const(kind, ty).into()) + } else { + 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)) + }) + } + + 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>, + ) -> QueryResult<'tcx> { + bug!("auto traits do not have associated types: {:?}", goal); + } + + fn consider_trait_alias_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("trait aliases do not have associated types: {:?}", goal); + } + + fn consider_builtin_sized_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Sized` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_copy_clone_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Copy`/`Clone` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_pointer_sized_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`PointerSized` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_fn_trait_candidates( + ecx: &mut EvalCtxt<'_, '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)) + } + } + + fn consider_builtin_tuple_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Tuple` does not have an associated type: {:?}", goal); + } +} + +/// This behavior is also implemented in `rustc_ty_utils` and in the old `project` code. +/// +/// FIXME: We should merge these 3 implementations as it's likely that they otherwise +/// diverge. +#[instrument(level = "debug", skip(infcx, param_env), ret)] +fn fetch_eligible_assoc_item_def<'tcx>( + infcx: &InferCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + goal_trait_ref: ty::TraitRef<'tcx>, + trait_assoc_def_id: DefId, + impl_def_id: DefId, +) -> Result<Option<LeafDef>, NoSolution> { + let node_item = specialization_graph::assoc_def(infcx.tcx, impl_def_id, trait_assoc_def_id) + .map_err(|ErrorGuaranteed { .. }| NoSolution)?; + + let eligible = if node_item.is_final() { + // Non-specializable items are always projectable. + true + } else { + // Only reveal a specializable default if we're past type-checking + // and the obligation is monomorphic, otherwise passes such as + // transmute checking and polymorphic MIR optimizations could + // get a result which isn't correct for all monomorphizations. + if param_env.reveal() == Reveal::All { + let poly_trait_ref = infcx.resolve_vars_if_possible(goal_trait_ref); + !poly_trait_ref.still_further_specializable() + } else { + debug!(?node_item.item.def_id, "not eligible due to default"); + false + } + }; + + if eligible { Ok(Some(node_item)) } else { Ok(None) } +} diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs new file mode 100644 index 000000000..730a8e612 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs @@ -0,0 +1,123 @@ +//! This module both handles the global cache which stores "finished" goals, +//! and the provisional cache which contains partially computed goals. +//! +//! The provisional cache is necessary when dealing with coinductive cycles. +//! +//! For more information about the provisional cache and coinduction in general, +//! check out the relevant section of the rustc-dev-guide. +//! +//! FIXME(@lcnr): Write that section, feel free to ping me if you need help here +//! before then or if I still haven't done that before January 2023. +use super::overflow::OverflowData; +use super::StackDepth; +use crate::solve::{CanonicalGoal, QueryResult}; +use rustc_data_structures::fx::FxHashMap; +use rustc_index::vec::IndexVec; +use rustc_middle::ty::TyCtxt; + +rustc_index::newtype_index! { + pub struct EntryIndex {} +} + +#[derive(Debug, Clone)] +pub(super) struct ProvisionalEntry<'tcx> { + // In case we have a coinductive cycle, this is the + // the currently least restrictive result of this goal. + pub(super) response: QueryResult<'tcx>, + // In case of a cycle, the position of deepest stack entry involved + // in that cycle. This is monotonically decreasing in the stack as all + // elements between the current stack element in the deepest stack entry + // involved have to also be involved in that cycle. + // + // We can only move entries to the global cache once we're complete done + // with the cycle. If this entry has not been involved in a cycle, + // this is just its own depth. + pub(super) depth: StackDepth, + + // The goal for this entry. Should always be equal to the corresponding goal + // in the lookup table. + pub(super) goal: CanonicalGoal<'tcx>, +} + +pub(super) struct ProvisionalCache<'tcx> { + pub(super) entries: IndexVec<EntryIndex, ProvisionalEntry<'tcx>>, + // FIXME: This is only used to quickly check whether a given goal + // is in the cache. We should experiment with using something like + // `SsoHashSet` here because in most cases there are only a few entries. + pub(super) lookup_table: FxHashMap<CanonicalGoal<'tcx>, EntryIndex>, +} + +impl<'tcx> ProvisionalCache<'tcx> { + pub(super) fn empty() -> ProvisionalCache<'tcx> { + ProvisionalCache { entries: Default::default(), lookup_table: Default::default() } + } + + pub(super) fn is_empty(&self) -> bool { + self.entries.is_empty() && self.lookup_table.is_empty() + } + + /// Adds a dependency from the current leaf to `target` in the cache + /// to prevent us from moving any goals which depend on the current leaf + /// to the global cache while we're still computing `target`. + /// + /// Its important to note that `target` may already be part of a different cycle. + /// In this case we have to ensure that we also depend on all other goals + /// in the existing cycle in addition to the potentially direct cycle with `target`. + pub(super) fn add_dependency_of_leaf_on(&mut self, target: EntryIndex) { + let depth = self.entries[target].depth; + for provisional_entry in &mut self.entries.raw[target.index()..] { + // The depth of `target` is the position of the deepest goal in the stack + // on which `target` depends. That goal is the `root` of this cycle. + // + // Any entry which was added after `target` is either on the stack itself + // at which point its depth is definitely at least as high as the depth of + // `root`. If it's not on the stack itself it has to depend on a goal + // between `root` and `leaf`. If it were to depend on a goal deeper in the + // stack than `root`, then `root` would also depend on that goal, at which + // point `root` wouldn't be the root anymore. + debug_assert!(provisional_entry.depth >= depth); + provisional_entry.depth = depth; + } + + // We only update entries which were added after `target` as no other + // entry should have a higher depth. + // + // Any entry which previously had a higher depth than target has to + // be between `target` and `root`. Because of this we would have updated + // its depth when calling `add_dependency_of_leaf_on(root)` for `target`. + if cfg!(debug_assertions) { + self.entries.iter().all(|e| e.depth <= depth); + } + } + + pub(super) fn depth(&self, entry_index: EntryIndex) -> StackDepth { + self.entries[entry_index].depth + } + + pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> QueryResult<'tcx> { + self.entries[entry_index].response.clone() + } +} + +pub(super) fn try_move_finished_goal_to_global_cache<'tcx>( + tcx: TyCtxt<'tcx>, + overflow_data: &mut OverflowData, + stack: &IndexVec<super::StackDepth, super::StackElem<'tcx>>, + goal: CanonicalGoal<'tcx>, + response: QueryResult<'tcx>, +) { + // We move goals to the global cache if we either did not hit an overflow or if it's + // the root goal as that will now always hit the same overflow limit. + // + // NOTE: We cannot move any non-root goals to the global cache even if their final result + // isn't impacted by the overflow as that goal still has unstable query dependencies + // because it didn't go its full depth. + // + // FIXME(@lcnr): We could still cache subtrees which are not impacted by overflow though. + // Tracking that info correctly isn't trivial, so I haven't implemented it for now. + let should_cache_globally = !overflow_data.did_overflow() || stack.is_empty(); + if should_cache_globally { + // FIXME: move the provisional entry to the global cache. + let _ = (tcx, goal, 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 new file mode 100644 index 000000000..0030e9aa3 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -0,0 +1,178 @@ +mod cache; +mod overflow; + +use self::cache::ProvisionalEntry; +use super::{CanonicalGoal, Certainty, MaybeCause, QueryResult}; +use cache::ProvisionalCache; +use overflow::OverflowData; +use rustc_index::vec::IndexVec; +use rustc_middle::ty::TyCtxt; +use std::collections::hash_map::Entry; + +rustc_index::newtype_index! { + pub struct StackDepth {} +} + +struct StackElem<'tcx> { + goal: CanonicalGoal<'tcx>, + has_been_used: bool, +} + +pub(super) struct SearchGraph<'tcx> { + /// The stack of goals currently being computed. + /// + /// An element is *deeper* in the stack if its index is *lower*. + stack: IndexVec<StackDepth, StackElem<'tcx>>, + overflow_data: OverflowData, + provisional_cache: ProvisionalCache<'tcx>, +} + +impl<'tcx> SearchGraph<'tcx> { + pub(super) fn new(tcx: TyCtxt<'tcx>) -> SearchGraph<'tcx> { + Self { + stack: Default::default(), + overflow_data: OverflowData::new(tcx), + provisional_cache: ProvisionalCache::empty(), + } + } + + pub(super) fn is_empty(&self) -> bool { + self.stack.is_empty() + && self.provisional_cache.is_empty() + && !self.overflow_data.did_overflow() + } + + /// 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( + &mut self, + tcx: TyCtxt<'tcx>, + goal: CanonicalGoal<'tcx>, + ) -> Result<(), QueryResult<'tcx>> { + // FIXME: start by checking the global cache + + // Look at the provisional cache to check for cycles. + let cache = &mut self.provisional_cache; + match cache.lookup_table.entry(goal) { + // No entry, simply push this goal on the stack after dealing with overflow. + Entry::Vacant(v) => { + if self.overflow_data.has_overflow(self.stack.len()) { + return Err(self.deal_with_overflow(tcx, goal)); + } + + let depth = self.stack.push(StackElem { goal, has_been_used: false }); + let response = super::response_no_constraints(tcx, goal, Certainty::Yes); + let entry_index = cache.entries.push(ProvisionalEntry { response, depth, goal }); + v.insert(entry_index); + Ok(()) + } + // We have a nested goal which relies on a goal `root` deeper in the stack. + // + // We first store that we may have to rerun `evaluate_goal` for `root` in case the + // provisional response is not equal to the final response. We also update the depth + // of all goals which recursively depend on our current goal to depend on `root` + // instead. + // + // Finally we can return either the provisional response for that goal if we have a + // coinductive cycle or an ambiguous result if the cycle is inductive. + 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); + + self.stack[stack_depth].has_been_used = true; + // NOTE: The goals on the stack aren't the only goals involved in this cycle. + // We can also depend on goals which aren't part of the stack but coinductively + // depend on the stack themselves. We already checked whether all the goals + // between these goals and their root on the stack. This means that as long as + // each goal in a cycle is checked for coinductivity by itself, simply checking + // the stack is enough. + if self.stack.raw[stack_depth.index()..] + .iter() + .all(|g| g.goal.value.predicate.is_coinductive(tcx)) + { + Err(cache.provisional_result(entry_index)) + } else { + Err(super::response_no_constraints( + tcx, + goal, + Certainty::Maybe(MaybeCause::Overflow), + )) + } + } + } + } + + /// We cannot simply store the result of [super::EvalCtxt::compute_goal] as we have to deal with + /// coinductive cycles. + /// + /// When we encounter a coinductive cycle, we have to prove the final result of that cycle + /// while we are still computing that result. Because of this we continously recompute the + /// cycle until the result of the previous iteration is equal to the final result, at which + /// point we are done. + /// + /// This function returns `true` if we were able to finalize the goal and `false` if it has + /// updated the provisional cache and we have to recompute the current goal. + /// + /// FIXME: Refer to the rustc-dev-guide entry once it exists. + pub(super) 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(); + 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; + // 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 + // from the provisional cache... + // + // That's not completely correct, as a nested goal can also + // depend on a goal which is lower in the stack so it doesn't + // actually depend on the current goal. This should be fairly + // rare and is hopefully not relevant for performance. + #[allow(rustc::potential_query_instability)] + cache.lookup_table.retain(|_key, index| *index <= provisional_entry_index); + cache.entries.truncate(provisional_entry_index.index() + 1); + + // ...and finally push our goal back on the stack and reevaluate it. + self.stack.push(StackElem { 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, + ); + } + } + true + } + } +} diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs new file mode 100644 index 000000000..1dd3894c9 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs @@ -0,0 +1,84 @@ +use rustc_infer::infer::canonical::Canonical; +use rustc_infer::traits::query::NoSolution; +use rustc_middle::ty::TyCtxt; +use rustc_session::Limit; + +use super::SearchGraph; +use crate::solve::{response_no_constraints, Certainty, EvalCtxt, MaybeCause, QueryResult}; + +/// When detecting a solver overflow, we return ambiguity. Overflow can be +/// *hidden* by either a fatal error in an **AND** or a trivial success in an **OR**. +/// +/// This is in issue in case of exponential blowup, e.g. if each goal on the stack +/// has multiple nested (overflowing) candidates. To deal with this, we reduce the limit +/// used by the solver when hitting the default limit for the first time. +/// +/// FIXME: Get tests where always using the `default_limit` results in a hang and refer +/// to them here. We can also improve the overflow strategy if necessary. +pub(super) struct OverflowData { + default_limit: Limit, + current_limit: Limit, + /// When proving an **AND** we have to repeatedly iterate over the yet unproven goals. + /// + /// Because of this each iteration also increases the depth in addition to the stack + /// depth. + additional_depth: usize, +} + +impl OverflowData { + pub(super) fn new(tcx: TyCtxt<'_>) -> OverflowData { + let default_limit = tcx.recursion_limit(); + OverflowData { default_limit, current_limit: default_limit, additional_depth: 0 } + } + + #[inline] + pub(super) fn did_overflow(&self) -> bool { + self.default_limit.0 != self.current_limit.0 + } + + #[inline] + pub(super) fn has_overflow(&self, depth: usize) -> bool { + !self.current_limit.value_within_limit(depth + self.additional_depth) + } + + /// Updating the current limit when hitting overflow. + fn deal_with_overflow(&mut self) { + // When first hitting overflow we reduce the overflow limit + // for all future goals to prevent hangs if there's an exponental + // blowup. + self.current_limit.0 = self.default_limit.0 / 8; + } +} + +impl<'tcx> SearchGraph<'tcx> { + pub fn deal_with_overflow( + &mut self, + tcx: TyCtxt<'tcx>, + goal: Canonical<'tcx, impl Sized>, + ) -> QueryResult<'tcx> { + self.overflow_data.deal_with_overflow(); + response_no_constraints(tcx, goal, Certainty::Maybe(MaybeCause::Overflow)) + } +} + +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 new file mode 100644 index 000000000..9985d7181 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -0,0 +1,289 @@ +//! Dealing with trait goals, i.e. `T: Trait<'a, U>`. + +use std::iter; + +use super::assembly::{self, Candidate, CandidateSource}; +use super::infcx_ext::InferCtxtExt; +use super::{Certainty, EvalCtxt, Goal, MaybeCause, QueryResult}; +use rustc_hir::def_id::DefId; +use rustc_infer::infer::InferCtxt; +use rustc_infer::traits::query::NoSolution; +use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; +use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt}; +use rustc_middle::ty::{TraitPredicate, TypeVisitable}; +use rustc_span::DUMMY_SP; + +pub mod structural_traits; + +impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { + fn self_ty(self) -> Ty<'tcx> { + self.self_ty() + } + + fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self { + self.with_self_ty(tcx, self_ty) + } + + fn trait_def_id(self, _: TyCtxt<'tcx>) -> DefId { + self.def_id() + } + + fn consider_impl_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, TraitPredicate<'tcx>>, + impl_def_id: DefId, + ) -> QueryResult<'tcx> { + let tcx = ecx.tcx(); + + let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder }; + if iter::zip(goal.predicate.trait_ref.substs, impl_trait_ref.skip_binder().substs) + .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp)) + { + return Err(NoSolution); + } + + ecx.infcx.probe(|_| { + let impl_substs = ecx.infcx.fresh_substs_for_item(DUMMY_SP, 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)?; + let where_clause_bounds = tcx + .predicates_of(impl_def_id) + .instantiate(tcx, impl_substs) + .predicates + .into_iter() + .map(|pred| goal.with(tcx, pred)); + nested_goals.extend(where_clause_bounds); + ecx.evaluate_all_and_make_canonical_response(nested_goals) + }) + } + + fn consider_assumption( + 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() { + // FIXME: Constness and polarity + ecx.infcx.probe(|_| { + let assumption_trait_pred = + ecx.infcx.instantiate_bound_vars_with_infer(poly_trait_pred); + let nested_goals = ecx.infcx.eq( + goal.param_env, + goal.predicate.trait_ref, + assumption_trait_pred.trait_ref, + )?; + ecx.evaluate_all_and_make_canonical_response(nested_goals) + }) + } else { + Err(NoSolution) + } + } + + fn consider_auto_trait_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + ecx.probe_and_evaluate_goal_for_constituent_tys( + goal, + structural_traits::instantiate_constituent_tys_for_auto_trait, + ) + } + + fn consider_trait_alias_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let tcx = ecx.tcx(); + + ecx.infcx.probe(|_| { + let nested_obligations = tcx + .predicates_of(goal.predicate.def_id()) + .instantiate(tcx, goal.predicate.trait_ref.substs); + ecx.evaluate_all_and_make_canonical_response( + nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)).collect(), + ) + }) + } + + fn consider_builtin_sized_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + ecx.probe_and_evaluate_goal_for_constituent_tys( + goal, + structural_traits::instantiate_constituent_tys_for_sized_trait, + ) + } + + fn consider_builtin_copy_clone_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + ecx.probe_and_evaluate_goal_for_constituent_tys( + goal, + structural_traits::instantiate_constituent_tys_for_copy_clone_trait, + ) + } + + fn consider_builtin_pointer_sized_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)); + } + + let tcx = ecx.tcx(); + let self_ty = tcx.erase_regions(goal.predicate.self_ty()); + + if let Ok(layout) = tcx.layout_of(goal.param_env.and(self_ty)) + && let usize_layout = tcx.layout_of(ty::ParamEnv::empty().and(tcx.types.usize)).unwrap().layout + && layout.layout.size() == usize_layout.size() + && layout.layout.align().abi == usize_layout.align().abi + { + // FIXME: We could make this faster by making a no-constraints response + ecx.make_canonical_response(Certainty::Yes) + } else { + Err(NoSolution) + } + } + + fn consider_builtin_fn_trait_candidates( + ecx: &mut EvalCtxt<'_, '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, _)| { + 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)) + } + } + + fn consider_builtin_tuple_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + if let ty::Tuple(..) = goal.predicate.self_ty().kind() { + ecx.make_canonical_response(Certainty::Yes) + } else { + Err(NoSolution) + } + } +} + +impl<'tcx> EvalCtxt<'_, 'tcx> { + /// Convenience function for traits that are structural, i.e. that only + /// have nested subgoals that only change the self type. Unlike other + /// evaluate-like helpers, this does a probe, so it doesn't need to be + /// wrapped in one. + 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>, + ) -> QueryResult<'tcx> { + self.infcx.probe(|_| { + self.evaluate_all_and_make_canonical_response( + constituent_tys(self.infcx, goal.predicate.self_ty())? + .into_iter() + .map(|ty| { + goal.with( + self.tcx(), + ty::Binder::dummy(goal.predicate.with_self_ty(self.tcx(), ty)), + ) + }) + .collect(), + ) + }) + } + + pub(super) fn compute_trait_goal( + &mut self, + 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 + } +} 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 new file mode 100644 index 000000000..a11cd13cb --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs @@ -0,0 +1,223 @@ +use rustc_hir::{Movability, Mutability}; +use rustc_infer::{infer::InferCtxt, traits::query::NoSolution}; +use rustc_middle::ty::{self, Ty, TyCtxt}; + +// 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>, + ty: Ty<'tcx>, +) -> Result<Vec<Ty<'tcx>>, NoSolution> { + let tcx = infcx.tcx; + match *ty.kind() { + ty::Uint(_) + | ty::Int(_) + | ty::Bool + | 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(..) + | ty::Param(..) + | ty::Foreign(..) + | ty::Alias(ty::Projection, ..) + | ty::Bound(..) + | ty::Infer(ty::TyVar(_)) => Err(NoSolution), + + ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(), + + ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => { + Ok(vec![element_ty]) + } + + ty::Array(element_ty, _) | ty::Slice(element_ty) => Ok(vec![element_ty]), + + ty::Tuple(ref tys) => { + // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet + Ok(tys.iter().collect()) + } + + ty::Closure(_, ref substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]), + + ty::Generator(_, ref substs, _) => { + let generator_substs = substs.as_generator(); + Ok(vec![generator_substs.tupled_upvars_ty(), generator_substs.witness()]) + } + + ty::GeneratorWitness(types) => { + Ok(infcx.replace_bound_vars_with_placeholders(types).to_vec()) + } + + // For `PhantomData<T>`, we pass `T`. + ty::Adt(def, substs) if def.is_phantom_data() => Ok(vec![substs.type_at(0)]), + + ty::Adt(def, substs) => Ok(def.all_fields().map(|f| f.ty(tcx, substs)).collect()), + + ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) => { + // We can resolve the `impl Trait` to its concrete type, + // which enforces a DAG between the functions requiring + // the auto trait bounds in question. + Ok(vec![tcx.bound_type_of(def_id).subst(tcx, substs)]) + } + } +} + +pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>( + infcx: &InferCtxt<'tcx>, + ty: Ty<'tcx>, +) -> Result<Vec<Ty<'tcx>>, NoSolution> { + match *ty.kind() { + ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) + | ty::Uint(_) + | ty::Int(_) + | ty::Bool + | ty::Float(_) + | ty::FnDef(..) + | ty::FnPtr(_) + | ty::RawPtr(..) + | ty::Char + | ty::Ref(..) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::Array(..) + | ty::Closure(..) + | ty::Never + | ty::Dynamic(_, _, ty::DynStar) + | ty::Error(_) => Ok(vec![]), + + ty::Str + | ty::Slice(_) + | ty::Dynamic(..) + | ty::Foreign(..) + | ty::Alias(..) + | ty::Param(_) + | ty::Infer(ty::TyVar(_)) => Err(NoSolution), + + ty::Placeholder(..) + | ty::Bound(..) + | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(), + + ty::Tuple(tys) => Ok(tys.to_vec()), + + ty::Adt(def, substs) => { + let sized_crit = def.sized_constraint(infcx.tcx); + Ok(sized_crit + .0 + .iter() + .map(|ty| sized_crit.rebind(*ty).subst(infcx.tcx, substs)) + .collect()) + } + } +} + +pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( + infcx: &InferCtxt<'tcx>, + ty: Ty<'tcx>, +) -> Result<Vec<Ty<'tcx>>, NoSolution> { + match *ty.kind() { + ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) + | ty::FnDef(..) + | ty::FnPtr(_) + | ty::Error(_) => Ok(vec![]), + + // Implementations are provided in core + ty::Uint(_) + | ty::Int(_) + | ty::Bool + | ty::Float(_) + | ty::Char + | ty::RawPtr(..) + | ty::Never + | ty::Ref(_, _, Mutability::Not) + | ty::Array(..) => Err(NoSolution), + + ty::Dynamic(..) + | ty::Str + | ty::Slice(_) + | ty::Generator(_, _, Movability::Static) + | ty::Foreign(..) + | ty::Ref(_, _, Mutability::Mut) + | ty::Adt(_, _) + | ty::Alias(_, _) + | ty::Param(_) + | ty::Infer(ty::TyVar(_)) => Err(NoSolution), + + ty::Placeholder(..) + | ty::Bound(..) + | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(), + + 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 { + let generator = substs.as_generator(); + Ok(vec![generator.tupled_upvars_ty(), generator.witness()]) + } else { + Err(NoSolution) + } + } + + ty::GeneratorWitness(types) => { + Ok(infcx.replace_bound_vars_with_placeholders(types).to_vec()) + } + } +} + +pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>( + tcx: TyCtxt<'tcx>, + self_ty: Ty<'tcx>, + goal_kind: ty::ClosureKind, +) -> Result<Option<ty::Binder<'tcx, (Ty<'tcx>, Ty<'tcx>)>>, NoSolution> { + match *self_ty.kind() { + ty::FnDef(def_id, substs) => Ok(Some( + tcx.bound_fn_sig(def_id) + .subst(tcx, substs) + .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().iter()), sig.output())))) + } + ty::Closure(_, substs) => { + let closure_substs = substs.as_closure(); + match closure_substs.kind_ty().to_opt_closure_kind() { + Some(closure_kind) if closure_kind.extends(goal_kind) => {} + None => return Ok(None), + _ => return Err(NoSolution), + } + Ok(Some(closure_substs.sig().map_bound(|sig| (sig.inputs()[0], sig.output())))) + } + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Adt(_, _) + | ty::Foreign(_) + | ty::Str + | ty::Array(_, _) + | ty::Slice(_) + | ty::RawPtr(_) + | ty::Ref(_, _, _) + | ty::Dynamic(_, _, _) + | ty::Generator(_, _, _) + | ty::GeneratorWitness(_) + | ty::Never + | ty::Tuple(_) + | ty::Alias(_, _) + | ty::Param(_) + | ty::Placeholder(_) + | ty::Bound(_, _) + | ty::Infer(_) + | ty::Error(_) => Err(NoSolution), + } +} |