diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src')
33 files changed, 1852 insertions, 278 deletions
diff --git a/compiler/rustc_trait_selection/src/infer.rs b/compiler/rustc_trait_selection/src/infer.rs index 6c70bbf7516..50c1787ef8c 100644 --- a/compiler/rustc_trait_selection/src/infer.rs +++ b/compiler/rustc_trait_selection/src/infer.rs @@ -4,7 +4,7 @@ use crate::traits::{self, ObligationCtxt}; use rustc_hir::def_id::DefId; use rustc_hir::lang_items::LangItem; use rustc_middle::arena::ArenaAllocatable; -use rustc_middle::infer::canonical::{Canonical, CanonicalizedQueryResponse, QueryResponse}; +use rustc_middle::infer::canonical::{Canonical, CanonicalQueryResponse, QueryResponse}; use rustc_middle::traits::query::Fallible; use rustc_middle::ty::{self, Ty, TypeFoldable, TypeVisitable}; use rustc_middle::ty::{GenericArg, ToPredicate}; @@ -102,7 +102,7 @@ pub trait InferCtxtBuilderExt<'tcx> { &mut self, canonical_key: &Canonical<'tcx, K>, operation: impl FnOnce(&ObligationCtxt<'_, 'tcx>, K) -> Fallible<R>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, R>> + ) -> Fallible<CanonicalQueryResponse<'tcx, R>> where K: TypeFoldable<'tcx>, R: Debug + TypeFoldable<'tcx>, @@ -130,7 +130,7 @@ impl<'tcx> InferCtxtBuilderExt<'tcx> for InferCtxtBuilder<'tcx> { &mut self, canonical_key: &Canonical<'tcx, K>, operation: impl FnOnce(&ObligationCtxt<'_, 'tcx>, K) -> Fallible<R>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, R>> + ) -> Fallible<CanonicalQueryResponse<'tcx, R>> where K: TypeFoldable<'tcx>, R: Debug + TypeFoldable<'tcx>, diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs index 975ff31a607..a30d1df4ede 100644 --- a/compiler/rustc_trait_selection/src/lib.rs +++ b/compiler/rustc_trait_selection/src/lib.rs @@ -19,6 +19,7 @@ #![feature(let_chains)] #![feature(if_let_guard)] #![feature(never_type)] +#![feature(result_option_inspect)] #![feature(type_alias_impl_trait)] #![recursion_limit = "512"] // For rustdoc @@ -37,4 +38,5 @@ extern crate smallvec; pub mod autoderef; pub mod errors; pub mod infer; +pub mod solve; pub mod traits; 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 00000000000..e9ddad11ff2 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/assembly.rs @@ -0,0 +1,150 @@ +//! Code shared by trait and projection goals for candidate assembly. + +use super::infcx_ext::InferCtxtExt; +use super::{ + fixme_instantiate_canonical_query_response, CanonicalGoal, CanonicalResponse, Certainty, + EvalCtxt, Goal, +}; +use rustc_hir::def_id::DefId; +use rustc_infer::infer::TyCtxtInferExt; +use rustc_infer::infer::{ + canonical::{CanonicalVarValues, OriginalQueryValues}, + InferCtxt, +}; +use rustc_infer::traits::query::NoSolution; +use rustc_middle::ty::TypeFoldable; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_span::DUMMY_SP; +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`. +/// +/// For the list of possible candidates, please look at the documentation of +/// [super::trait_goals::CandidateSource] and [super::project_goals::CandidateSource]. +#[derive(Debug, Clone)] +pub(super) struct Candidate<'tcx, G: GoalKind<'tcx>> { + pub(super) source: G::CandidateSource, + pub(super) result: CanonicalResponse<'tcx>, +} + +pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy { + type CandidateSource: Debug + Copy; + + 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( + acx: &mut AssemblyCtxt<'_, 'tcx, Self>, + goal: Goal<'tcx, Self>, + impl_def_id: DefId, + ); +} + +/// An abstraction which correctly deals with the canonical results for candidates. +/// +/// It also deduplicates the behavior between trait and projection predicates. +pub(super) struct AssemblyCtxt<'a, 'tcx, G: GoalKind<'tcx>> { + pub(super) cx: &'a mut EvalCtxt<'tcx>, + pub(super) infcx: &'a InferCtxt<'tcx>, + var_values: CanonicalVarValues<'tcx>, + candidates: Vec<Candidate<'tcx, G>>, +} + +impl<'a, 'tcx, G: GoalKind<'tcx>> AssemblyCtxt<'a, 'tcx, G> { + pub(super) fn assemble_and_evaluate_candidates( + cx: &'a mut EvalCtxt<'tcx>, + goal: CanonicalGoal<'tcx, G>, + ) -> Vec<Candidate<'tcx, G>> { + let (ref infcx, goal, var_values) = + cx.tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &goal); + let mut acx = AssemblyCtxt { cx, infcx, var_values, candidates: Vec::new() }; + + acx.assemble_candidates_after_normalizing_self_ty(goal); + + acx.assemble_impl_candidates(goal); + + acx.candidates + } + + pub(super) fn try_insert_candidate( + &mut self, + source: G::CandidateSource, + certainty: Certainty, + ) { + match self.infcx.make_canonical_response(self.var_values.clone(), certainty) { + Ok(result) => self.candidates.push(Candidate { source, result }), + Err(NoSolution) => debug!(?source, ?certainty, "failed leakcheck"), + } + } + + /// 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(&mut self, goal: Goal<'tcx, G>) { + let tcx = self.cx.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.cx.evaluate_goal(&self.infcx, normalizes_to_goal) { + Ok((_, certainty)) => certainty, + Err(NoSolution) => return, + }; + + // 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 both winnowing and to resolve associated items. + let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty)); + let mut orig_values = OriginalQueryValues::default(); + let goal = self.infcx.canonicalize_query(goal, &mut orig_values); + let normalized_candidates = + AssemblyCtxt::assemble_and_evaluate_candidates(self.cx, goal); + + // Map each candidate from being canonical wrt the current inference context to being + // canonical wrt the caller. + for Candidate { source, result } in normalized_candidates { + self.infcx.probe(|_| { + let candidate_certainty = fixme_instantiate_canonical_query_response( + &self.infcx, + &orig_values, + result, + ); + + // FIXME: This is a bit scary if the `normalizes_to_goal` overflows. + // + // If we have an ambiguous candidate it hides that normalization + // caused an overflow which may cause issues. + self.try_insert_candidate( + source, + normalization_certainty.unify_and(candidate_certainty), + ) + }) + } + }) + } + + fn assemble_impl_candidates(&mut self, goal: Goal<'tcx, G>) { + self.cx.tcx.for_each_relevant_impl( + goal.predicate.trait_def_id(self.cx.tcx), + goal.predicate.self_ty(), + |impl_def_id| G::consider_impl_candidate(self, goal, impl_def_id), + ); + } +} diff --git a/compiler/rustc_trait_selection/src/solve/cache.rs b/compiler/rustc_trait_selection/src/solve/cache.rs new file mode 100644 index 00000000000..993b7989066 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/cache.rs @@ -0,0 +1,257 @@ +//! 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::CanonicalGoal; +use super::{EvalCtxt, QueryResult}; + +use rustc_data_structures::fx::FxHashMap; +use rustc_middle::ty::TyCtxt; +use std::{cmp::Ordering, collections::hash_map::Entry}; + +#[derive(Debug, Clone)] +struct ProvisionalEntry<'tcx> { + // In case we have a coinductive cycle, this is the + // the currently least restrictive result of this goal. + response: QueryResult<'tcx>, + // The lowest element on the stack on which this result + // relies on. Starts out as just being the depth at which + // we've proven this obligation, but gets lowered to the + // depth of another goal if we rely on it in a cycle. + depth: usize, +} + +struct StackElem<'tcx> { + goal: CanonicalGoal<'tcx>, + has_been_used: bool, +} + +/// The cache used for goals which are currently in progress or which depend +/// on in progress results. +/// +/// Once we're done with a goal we can store it in the global trait solver +/// cache of the `TyCtxt`. For goals which we're currently proving, or which +/// have only been proven via a coinductive cycle using a goal still on our stack +/// we have to use this separate data structure. +/// +/// The current data structure is not perfect, so there may still be room for +/// improvement here. We have the following requirements: +/// +/// ## Is there is a provisional entry for the given goal: +/// +/// ```ignore (for syntax highlighting) +/// self.entries.get(goal) +/// ``` +/// +/// ## Get all goals on the stack involved in a cycle: +/// +/// ```ignore (for syntax highlighting) +/// let entry = self.entries.get(goal).unwrap(); +/// let involved_goals = self.stack.iter().skip(entry.depth); +/// ``` +/// +/// ## Capping the depth of all entries +/// +/// Needed whenever we encounter a cycle. The current implementation always +/// iterates over all entries instead of only the ones with a larger depth. +/// Changing this may result in notable performance improvements. +/// +/// ```ignore (for syntax highlighting) +/// let cycle_depth = self.entries.get(goal).unwrap().depth; +/// for e in &mut self.entries { +/// e.depth = e.depth.min(cycle_depth); +/// } +/// ``` +/// +/// ## Checking whether we have to rerun the current goal +/// +/// A goal has to be rerun if its provisional result was used in a cycle +/// and that result is different from its final result. We update +/// [StackElem::has_been_used] for the deepest stack element involved in a cycle. +/// +/// ## Moving all finished goals into the global cache +/// +/// If `stack_elem.has_been_used` is true, iterate over all entries, moving the ones +/// with equal depth. If not, simply move this single entry. +pub(super) struct ProvisionalCache<'tcx> { + stack: Vec<StackElem<'tcx>>, + entries: FxHashMap<CanonicalGoal<'tcx>, ProvisionalEntry<'tcx>>, +} + +impl<'tcx> ProvisionalCache<'tcx> { + pub(super) fn empty() -> ProvisionalCache<'tcx> { + ProvisionalCache { stack: Vec::new(), entries: Default::default() } + } + + pub(super) fn current_depth(&self) -> usize { + self.stack.len() + } +} + +impl<'tcx> EvalCtxt<'tcx> { + /// 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, + 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.entries.entry(goal) { + // No entry, simply push this goal on the stack after dealing with overflow. + Entry::Vacant(v) => { + if self.overflow_data.has_overflow(cache.stack.len()) { + return Err(self.deal_with_overflow()); + } + + v.insert(ProvisionalEntry { + response: fixme_response_yes_no_constraints(), + depth: cache.stack.len(), + }); + cache.stack.push(StackElem { goal, has_been_used: false }); + 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) => { + // FIXME: `ProvisionalEntry` should be `Copy`. + let entry = entry.get().clone(); + cache.stack[entry.depth].has_been_used = true; + for provisional_entry in cache.entries.values_mut() { + provisional_entry.depth = provisional_entry.depth.min(entry.depth); + } + + // 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 cache.stack[entry.depth..] + .iter() + .all(|g| g.goal.value.predicate.is_coinductive(self.tcx)) + { + Err(entry.response) + } else { + Err(fixme_response_maybe_no_constraints()) + } + } + } + } + + /// We cannot simply store the result of [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, + actual_goal: CanonicalGoal<'tcx>, + response: QueryResult<'tcx>, + ) -> bool { + let cache = &mut self.provisional_cache; + let StackElem { goal, has_been_used } = cache.stack.pop().unwrap(); + assert_eq!(goal, actual_goal); + + let provisional_entry = cache.entries.get_mut(&goal).unwrap(); + // Check whether the current stack entry is the root of a cycle. + // + // If so, we either move all participants of that cycle to the global cache + // or, in case the provisional response used in the cycle is not equal to the + // final response, have to recompute the goal after updating the provisional + // response to the final response of this iteration. + if has_been_used { + if provisional_entry.response == response { + // We simply drop all entries according to an immutable condition, so + // query instability is not a concern here. + #[allow(rustc::potential_query_instability)] + cache.entries.retain(|goal, entry| match entry.depth.cmp(&cache.stack.len()) { + Ordering::Less => true, + Ordering::Equal => { + Self::try_move_finished_goal_to_global_cache( + self.tcx, + &mut self.overflow_data, + &cache.stack, + // FIXME: these should be `Copy` :( + goal.clone(), + entry.response.clone(), + ); + false + } + Ordering::Greater => bug!("entry with greater depth than the current leaf"), + }); + + true + } else { + provisional_entry.response = response; + cache.stack.push(StackElem { goal, has_been_used: false }); + false + } + } else { + Self::try_move_finished_goal_to_global_cache( + self.tcx, + &mut self.overflow_data, + &cache.stack, + goal, + response, + ); + cache.entries.remove(&goal); + true + } + } + + fn try_move_finished_goal_to_global_cache( + tcx: TyCtxt<'tcx>, + overflow_data: &mut OverflowData, + stack: &[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); + } + } +} + +fn fixme_response_yes_no_constraints<'tcx>() -> QueryResult<'tcx> { + unimplemented!() +} + +fn fixme_response_maybe_no_constraints<'tcx>() -> QueryResult<'tcx> { + unimplemented!() +} 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 00000000000..80115d78d88 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs @@ -0,0 +1,92 @@ +use std::mem; + +use rustc_data_structures::fx::FxHashMap; +use rustc_infer::{ + infer::InferCtxt, + traits::{query::NoSolution, FulfillmentError, PredicateObligation, TraitEngine}, +}; +use rustc_middle::ty; + +use super::{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; + } + + if self.obligations.is_empty() { + Vec::new() + } else { + unimplemented!("ambiguous obligations") + } + } + + fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> { + let errors = Vec::new(); + for i in 0.. { + if !infcx.tcx.recursion_limit().value_within_limit(i) { + unimplemented!("overflow") + } + + let mut has_changed = false; + for o in mem::take(&mut self.obligations) { + let mut cx = EvalCtxt::new(infcx.tcx); + let (changed, certainty) = match cx.evaluate_goal(infcx, o.clone().into()) { + Ok(result) => result, + Err(NoSolution) => unimplemented!("error"), + }; + + has_changed |= changed; + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => self.obligations.push(o), + } + } + + 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 00000000000..436f4eea662 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/infcx_ext.rs @@ -0,0 +1,55 @@ +use rustc_infer::infer::canonical::CanonicalVarValues; +use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; +use rustc_infer::infer::InferCtxt; +use rustc_infer::traits::query::NoSolution; +use rustc_middle::ty::Ty; +use rustc_span::DUMMY_SP; + +use crate::solve::ExternalConstraints; + +use super::{Certainty, QueryResult, Response}; + +/// Methods used inside of the canonical queries of the solver. +pub(super) trait InferCtxtExt<'tcx> { + fn next_ty_infer(&self) -> Ty<'tcx>; + + fn make_canonical_response( + &self, + var_values: CanonicalVarValues<'tcx>, + certainty: Certainty, + ) -> QueryResult<'tcx>; +} + +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 make_canonical_response( + &self, + var_values: CanonicalVarValues<'tcx>, + certainty: Certainty, + ) -> QueryResult<'tcx> { + let external_constraints = take_external_constraints(self)?; + + Ok(self.canonicalize_response(Response { var_values, external_constraints, 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, + }) +} 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 00000000000..7f5e3208f4e --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -0,0 +1,309 @@ +//! 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::OriginalQueryValues; +use rustc_infer::infer::{InferCtxt, TyCtxtInferExt}; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::Obligation; +use rustc_middle::infer::canonical::{Canonical, CanonicalVarValues}; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_middle::ty::{RegionOutlivesPredicate, ToPredicate, TypeOutlivesPredicate}; +use rustc_span::DUMMY_SP; + +use self::infcx_ext::InferCtxtExt; + +mod assembly; +mod cache; +mod fulfill; +mod infcx_ext; +mod overflow; +mod project_goals; +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)] +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 cx = EvalCtxt::new(self); + cx.evaluate_canonical_goal(goal) + } +} + +struct EvalCtxt<'tcx> { + tcx: TyCtxt<'tcx>, + + provisional_cache: cache::ProvisionalCache<'tcx>, + overflow_data: overflow::OverflowData, +} + +impl<'tcx> EvalCtxt<'tcx> { + fn new(tcx: TyCtxt<'tcx>) -> EvalCtxt<'tcx> { + EvalCtxt { + tcx, + provisional_cache: cache::ProvisionalCache::empty(), + overflow_data: overflow::OverflowData::new(tcx), + } + } + + /// Recursively evaluates `goal`, returning whether any inference vars have + /// been constrained and the certainty of the result. + fn evaluate_goal( + &mut self, + infcx: &InferCtxt<'tcx>, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty), NoSolution> { + let mut orig_values = OriginalQueryValues::default(); + let canonical_goal = infcx.canonicalize_query(goal, &mut orig_values); + let canonical_response = self.evaluate_canonical_goal(canonical_goal)?; + Ok(( + true, // FIXME: check whether `var_values` are an identity substitution. + fixme_instantiate_canonical_query_response(infcx, &orig_values, canonical_response), + )) + } + + fn evaluate_canonical_goal(&mut self, goal: CanonicalGoal<'tcx>) -> QueryResult<'tcx> { + match self.try_push_stack(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 result = self.compute_goal(goal); + + // FIXME: `Response` should be `Copy` + if self.try_finalize_goal(goal, result.clone()) { + return result; + } + } + } + + fn compute_goal(&mut self, canonical_goal: CanonicalGoal<'tcx>) -> QueryResult<'tcx> { + // WARNING: We're looking at a canonical value without instantiating it here. + // + // We have to be incredibly careful to not change the order of bound variables or + // remove any. As we go from `Goal<'tcx, Predicate>` to `Goal` with the variants + // of `PredicateKind` this is the case and it is and faster than instantiating and + // recanonicalizing. + let Goal { param_env, predicate } = canonical_goal.value; + if let Some(kind) = predicate.kind().no_bound_vars() { + match kind { + ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => self.compute_trait_goal( + canonical_goal.unchecked_rebind(Goal { param_env, predicate }), + ), + ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => self + .compute_projection_goal( + canonical_goal.unchecked_rebind(Goal { param_env, predicate }), + ), + ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => self + .compute_type_outlives_goal( + canonical_goal.unchecked_rebind(Goal { param_env, predicate }), + ), + ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => self + .compute_region_outlives_goal( + canonical_goal.unchecked_rebind(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 => unimplemented!(), + } + } else { + let (infcx, goal, var_values) = + self.tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &canonical_goal); + let kind = infcx.replace_bound_vars_with_placeholders(goal.predicate.kind()); + let goal = goal.with(self.tcx, ty::Binder::dummy(kind)); + let (_, certainty) = self.evaluate_goal(&infcx, goal)?; + infcx.make_canonical_response(var_values, certainty) + } + } + + fn compute_type_outlives_goal( + &mut self, + _goal: CanonicalGoal<'tcx, TypeOutlivesPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + todo!() + } + + fn compute_region_outlives_goal( + &mut self, + _goal: CanonicalGoal<'tcx, RegionOutlivesPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + todo!() + } +} + +impl<'tcx> EvalCtxt<'tcx> { + fn evaluate_all( + &mut self, + infcx: &InferCtxt<'tcx>, + 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(infcx, 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 fixme_instantiate_canonical_query_response<'tcx>( + _: &InferCtxt<'tcx>, + _: &OriginalQueryValues<'tcx>, + _: CanonicalResponse<'tcx>, +) -> Certainty { + unimplemented!() +} diff --git a/compiler/rustc_trait_selection/src/solve/overflow.rs b/compiler/rustc_trait_selection/src/solve/overflow.rs new file mode 100644 index 00000000000..fdd6adb681b --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/overflow.rs @@ -0,0 +1,80 @@ +use rustc_infer::traits::query::NoSolution; +use rustc_middle::ty::TyCtxt; +use rustc_session::Limit; + +use super::{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> EvalCtxt<'tcx> { + pub(super) fn deal_with_overflow(&mut self) -> QueryResult<'tcx> { + self.overflow_data.deal_with_overflow(); + fixme_response_overflow_no_constraints() + } + + /// A `while`-loop which tracks overflow. + pub(super) fn repeat_while_none( + &mut self, + mut loop_body: impl FnMut(&mut Self) -> Option<Result<Certainty, NoSolution>>, + ) -> Result<Certainty, NoSolution> { + let start_depth = self.overflow_data.additional_depth; + let depth = self.provisional_cache.current_depth(); + while !self.overflow_data.has_overflow(depth) { + if let Some(result) = loop_body(self) { + self.overflow_data.additional_depth = start_depth; + return result; + } + + self.overflow_data.additional_depth += 1; + } + self.overflow_data.additional_depth = start_depth; + self.overflow_data.deal_with_overflow(); + Ok(Certainty::Maybe(MaybeCause::Overflow)) + } +} + +fn fixme_response_overflow_no_constraints<'tcx>() -> QueryResult<'tcx> { + unimplemented!() +} 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 00000000000..b50f42c4d94 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -0,0 +1,244 @@ +use crate::traits::{specialization_graph, translate_substs}; + +use super::assembly::{self, AssemblyCtxt}; +use super::{CanonicalGoal, EvalCtxt, Goal, QueryResult}; +use rustc_errors::ErrorGuaranteed; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::DefId; +use rustc_infer::infer::{InferCtxt, InferOk}; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::specialization_graph::LeafDef; +use rustc_infer::traits::{ObligationCause, Reveal}; +use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; +use rustc_middle::ty::ProjectionPredicate; +use rustc_middle::ty::TypeVisitable; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_span::DUMMY_SP; +use std::iter; + +#[allow(dead_code)] // FIXME: implement and use all variants. +#[derive(Debug, Clone, Copy)] +pub(super) enum CandidateSource { + Impl(DefId), + ParamEnv(usize), + Builtin, +} + +type Candidate<'tcx> = assembly::Candidate<'tcx, ProjectionPredicate<'tcx>>; + +impl<'tcx> EvalCtxt<'tcx> { + pub(super) fn compute_projection_goal( + &mut self, + goal: CanonicalGoal<'tcx, ProjectionPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + let candidates = AssemblyCtxt::assemble_and_evaluate_candidates(self, goal); + self.merge_project_candidates(candidates) + } + + 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::Builtin, _) => unimplemented!(), + } + } +} + +impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { + type CandidateSource = CandidateSource; + + 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( + acx: &mut AssemblyCtxt<'_, 'tcx, ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + impl_def_id: DefId, + ) { + let tcx = acx.cx.tcx; + let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx); + let impl_trait_ref = tcx.bound_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; + } + + acx.infcx.probe(|_| { + let impl_substs = acx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id); + let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); + + let Ok(InferOk { obligations, .. }) = acx + .infcx + .at(&ObligationCause::dummy(), goal.param_env) + .define_opaque_types(false) + .eq(goal_trait_ref, impl_trait_ref) + .map_err(|e| debug!("failed to equate trait refs: {e:?}")) + else { + return + }; + + let nested_goals = obligations.into_iter().map(|o| o.into()).collect(); + let Ok(trait_ref_certainty) = acx.cx.evaluate_all(acx.infcx, nested_goals) else { return }; + + let Some(assoc_def) = fetch_eligible_assoc_item_def( + acx.infcx, + goal.param_env, + goal_trait_ref, + goal.predicate.def_id(), + impl_def_id + ) else { + return + }; + + 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_trait_ref.substs, + ); + let substs = translate_substs( + acx.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()) + }; + + let Ok(InferOk { obligations, .. }) = acx + .infcx + .at(&ObligationCause::dummy(), goal.param_env) + .define_opaque_types(false) + .eq(goal.predicate.term, term.subst(tcx, substs)) + .map_err(|e| debug!("failed to equate trait refs: {e:?}")) + else { + return + }; + + let nested_goals = obligations.into_iter().map(|o| o.into()).collect(); + let Ok(rhs_certainty) = acx.cx.evaluate_all(acx.infcx, nested_goals) else { return }; + + let certainty = trait_ref_certainty.unify_and(rhs_certainty); + acx.try_insert_candidate(CandidateSource::Impl(impl_def_id), certainty); + }) + } +} + +/// 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, +) -> Option<LeafDef> { + let node_item = specialization_graph::assoc_def(infcx.tcx, impl_def_id, trait_assoc_def_id) + .map_err(|ErrorGuaranteed { .. }| ()) + .ok()?; + + 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 { Some(node_item) } else { None } +} 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 00000000000..10b45a77dab --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -0,0 +1,180 @@ +//! Dealing with trait goals, i.e. `T: Trait<'a, U>`. + +use std::iter; + +use super::assembly::{self, AssemblyCtxt}; +use super::{CanonicalGoal, EvalCtxt, Goal, QueryResult}; +use rustc_hir::def_id::DefId; +use rustc_infer::infer::InferOk; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::ObligationCause; +use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; +use rustc_middle::ty::TraitPredicate; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_span::DUMMY_SP; + +#[allow(dead_code)] // FIXME: implement and use all variants. +#[derive(Debug, Clone, Copy)] +pub(super) enum CandidateSource { + /// Some user-defined impl with the given `DefId`. + Impl(DefId), + /// The n-th caller bound in the `param_env` of our goal. + /// + /// This is pretty much always a bound from the `where`-clauses of the + /// currently checked item. + ParamEnv(usize), + /// A bound on the `self_ty` in case it is a projection or an opaque type. + /// + /// # Examples + /// + /// ```ignore (for syntax highlighting) + /// trait Trait { + /// type Assoc: OtherTrait; + /// } + /// ``` + /// + /// We know that `<Whatever as Trait>::Assoc: OtherTrait` holds by looking at + /// the bounds on `Trait::Assoc`. + AliasBound(usize), + /// A builtin implementation for some specific traits, used in cases + /// where we cannot rely an ordinary library implementations. + /// + /// The most notable examples are `Sized`, `Copy` and `Clone`. This is also + /// used for the `DiscriminantKind` and `Pointee` trait, both of which have + /// an associated type. + Builtin, + /// An automatic impl for an auto trait, e.g. `Send`. These impls recursively look + /// at the constituent types of the `self_ty` to check whether the auto trait + /// is implemented for those. + AutoImpl, +} + +type Candidate<'tcx> = assembly::Candidate<'tcx, TraitPredicate<'tcx>>; + +impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { + type CandidateSource = CandidateSource; + + 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( + acx: &mut AssemblyCtxt<'_, 'tcx, Self>, + goal: Goal<'tcx, TraitPredicate<'tcx>>, + impl_def_id: DefId, + ) { + let impl_trait_ref = acx.cx.tcx.bound_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; + } + + acx.infcx.probe(|_| { + let impl_substs = acx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id); + let impl_trait_ref = impl_trait_ref.subst(acx.cx.tcx, impl_substs); + + let Ok(InferOk { obligations, .. }) = acx + .infcx + .at(&ObligationCause::dummy(), goal.param_env) + .define_opaque_types(false) + .eq(goal.predicate.trait_ref, impl_trait_ref) + .map_err(|e| debug!("failed to equate trait refs: {e:?}")) + else { + return + }; + + let nested_goals = obligations.into_iter().map(|o| o.into()).collect(); + + let Ok(certainty) = acx.cx.evaluate_all(acx.infcx, nested_goals) else { return }; + acx.try_insert_candidate(CandidateSource::Impl(impl_def_id), certainty); + }) + } +} + +impl<'tcx> EvalCtxt<'tcx> { + pub(super) fn compute_trait_goal( + &mut self, + goal: CanonicalGoal<'tcx, TraitPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + let candidates = AssemblyCtxt::assemble_and_evaluate_candidates(self, 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::Builtin, _) + | (CandidateSource::AutoImpl, _) => 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/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs index 7c569621cfe..26757965c95 100644 --- a/compiler/rustc_trait_selection/src/traits/coherence.rs +++ b/compiler/rustc_trait_selection/src/traits/coherence.rs @@ -66,13 +66,13 @@ pub fn add_placeholder_note(err: &mut Diagnostic) { /// with a suitably-freshened `ImplHeader` with those types /// substituted. Otherwise, returns `None`. #[instrument(skip(tcx, skip_leak_check), level = "debug")] -pub fn overlapping_impls<'tcx>( - tcx: TyCtxt<'tcx>, +pub fn overlapping_impls( + tcx: TyCtxt<'_>, impl1_def_id: DefId, impl2_def_id: DefId, skip_leak_check: SkipLeakCheck, overlap_mode: OverlapMode, -) -> Option<OverlapResult<'tcx>> { +) -> Option<OverlapResult<'_>> { // Before doing expensive operations like entering an inference context, do // a quick check via fast_reject to tell if the impl headers could possibly // unify. @@ -283,7 +283,7 @@ fn implicit_negative<'cx, 'tcx>( /// Given impl1 and impl2 check if both impls are never satisfied by a common type (including /// where-clauses) If so, return true, they are disjoint and false otherwise. -fn negative_impl<'tcx>(tcx: TyCtxt<'tcx>, impl1_def_id: DefId, impl2_def_id: DefId) -> bool { +fn negative_impl(tcx: TyCtxt<'_>, impl1_def_id: DefId, impl2_def_id: DefId) -> bool { debug!("negative_impl(impl1_def_id={:?}, impl2_def_id={:?})", impl1_def_id, impl2_def_id); // Create an infcx, taking the predicates of impl1 as assumptions: diff --git a/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs b/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs index f8efe9bfa9f..71fb6058cd2 100644 --- a/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs +++ b/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs @@ -168,24 +168,27 @@ fn satisfied_from_param_env<'tcx>( param_env: ty::ParamEnv<'tcx>, infcx: &'a InferCtxt<'tcx>, + single_match: Option<Result<ty::Const<'tcx>, ()>>, } + impl<'a, 'tcx> TypeVisitor<'tcx> for Visitor<'a, 'tcx> { type BreakTy = (); fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { debug!("is_const_evaluatable: candidate={:?}", c); - if let Ok(()) = self.infcx.commit_if_ok(|_| { + if self.infcx.probe(|_| { let ocx = ObligationCtxt::new_in_snapshot(self.infcx); - if let Ok(()) = ocx.eq(&ObligationCause::dummy(), self.param_env, c.ty(), self.ct.ty()) - && let Ok(()) = ocx.eq(&ObligationCause::dummy(), self.param_env, c, self.ct) + ocx.eq(&ObligationCause::dummy(), self.param_env, c.ty(), self.ct.ty()).is_ok() + && ocx.eq(&ObligationCause::dummy(), self.param_env, c, self.ct).is_ok() && ocx.select_all_or_error().is_empty() - { - Ok(()) - } else { - Err(()) - } }) { - ControlFlow::BREAK - } else if let ty::ConstKind::Expr(e) = c.kind() { + self.single_match = match self.single_match { + None => Some(Ok(c)), + Some(Ok(o)) if o == c => Some(Ok(c)), + Some(_) => Some(Err(())), + }; + } + + if let ty::ConstKind::Expr(e) = c.kind() { e.visit_with(self) } else { // FIXME(generic_const_exprs): This doesn't recurse into `<T as Trait<U>>::ASSOC`'s substs. @@ -200,22 +203,29 @@ fn satisfied_from_param_env<'tcx>( } } + let mut single_match: Option<Result<ty::Const<'tcx>, ()>> = None; + for pred in param_env.caller_bounds() { match pred.kind().skip_binder() { ty::PredicateKind::ConstEvaluatable(ce) => { let b_ct = tcx.expand_abstract_consts(ce); - let mut v = Visitor { ct, infcx, param_env }; - let result = b_ct.visit_with(&mut v); + let mut v = Visitor { ct, infcx, param_env, single_match }; + let _ = b_ct.visit_with(&mut v); - if let ControlFlow::Break(()) = result { - debug!("is_const_evaluatable: yes"); - return true; - } + single_match = v.single_match; } _ => {} // don't care } } + if let Some(Ok(c)) = single_match { + let ocx = ObligationCtxt::new(infcx); + assert!(ocx.eq(&ObligationCause::dummy(), param_env, c.ty(), ct.ty()).is_ok()); + assert!(ocx.eq(&ObligationCause::dummy(), param_env, c, ct).is_ok()); + assert!(ocx.select_all_or_error().is_empty()); + return true; + } + debug!("is_const_evaluatable: no"); false } diff --git a/compiler/rustc_trait_selection/src/traits/engine.rs b/compiler/rustc_trait_selection/src/traits/engine.rs index c028e89e4ea..369f80139a8 100644 --- a/compiler/rustc_trait_selection/src/traits/engine.rs +++ b/compiler/rustc_trait_selection/src/traits/engine.rs @@ -3,12 +3,13 @@ use std::fmt::Debug; use super::TraitEngine; use super::{ChalkFulfillmentContext, FulfillmentContext}; +use crate::solve::FulfillmentCtxt as NextFulfillmentCtxt; use crate::traits::NormalizeExt; use rustc_data_structures::fx::FxIndexSet; use rustc_hir::def_id::{DefId, LocalDefId}; use rustc_infer::infer::at::ToTrace; use rustc_infer::infer::canonical::{ - Canonical, CanonicalVarValues, CanonicalizedQueryResponse, QueryResponse, + Canonical, CanonicalQueryResponse, CanonicalVarValues, QueryResponse, }; use rustc_infer::infer::{InferCtxt, InferOk}; use rustc_infer::traits::query::Fallible; @@ -20,6 +21,7 @@ use rustc_middle::ty::error::TypeError; use rustc_middle::ty::ToPredicate; use rustc_middle::ty::TypeFoldable; use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_session::config::TraitSolver; use rustc_span::Span; pub trait TraitEngineExt<'tcx> { @@ -29,18 +31,18 @@ pub trait TraitEngineExt<'tcx> { impl<'tcx> TraitEngineExt<'tcx> for dyn TraitEngine<'tcx> { fn new(tcx: TyCtxt<'tcx>) -> Box<Self> { - if tcx.sess.opts.unstable_opts.chalk { - Box::new(ChalkFulfillmentContext::new()) - } else { - Box::new(FulfillmentContext::new()) + match tcx.sess.opts.unstable_opts.trait_solver { + TraitSolver::Classic => Box::new(FulfillmentContext::new()), + TraitSolver::Chalk => Box::new(ChalkFulfillmentContext::new()), + TraitSolver::Next => Box::new(NextFulfillmentCtxt::new()), } } fn new_in_snapshot(tcx: TyCtxt<'tcx>) -> Box<Self> { - if tcx.sess.opts.unstable_opts.chalk { - Box::new(ChalkFulfillmentContext::new_in_snapshot()) - } else { - Box::new(FulfillmentContext::new_in_snapshot()) + match tcx.sess.opts.unstable_opts.trait_solver { + TraitSolver::Classic => Box::new(FulfillmentContext::new_in_snapshot()), + TraitSolver::Chalk => Box::new(ChalkFulfillmentContext::new_in_snapshot()), + TraitSolver::Next => Box::new(NextFulfillmentCtxt::new()), } } } @@ -213,7 +215,7 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> { &self, inference_vars: CanonicalVarValues<'tcx>, answer: T, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, T>> + ) -> Fallible<CanonicalQueryResponse<'tcx, T>> where T: Debug + TypeFoldable<'tcx>, Canonical<'tcx, QueryResponse<'tcx, T>>: ArenaAllocatable<'tcx>, diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/method_chain.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/method_chain.rs index cb373d65772..27c207528c7 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/method_chain.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/method_chain.rs @@ -14,21 +14,27 @@ impl<'a, 'tcx> TypeRelation<'tcx> for CollectAllMismatches<'a, 'tcx> { fn tag(&self) -> &'static str { "CollectAllMismatches" } + fn tcx(&self) -> TyCtxt<'tcx> { self.infcx.tcx } + fn intercrate(&self) -> bool { false } + fn param_env(&self) -> ty::ParamEnv<'tcx> { self.param_env } + fn a_is_expected(&self) -> bool { true - } // irrelevant + } + fn mark_ambiguous(&mut self) { bug!() } + fn relate_with_variance<T: Relate<'tcx>>( &mut self, _: ty::Variance, @@ -38,6 +44,7 @@ impl<'a, 'tcx> TypeRelation<'tcx> for CollectAllMismatches<'a, 'tcx> { ) -> RelateResult<'tcx, T> { self.relate(a, b) } + fn regions( &mut self, a: ty::Region<'tcx>, @@ -45,15 +52,20 @@ impl<'a, 'tcx> TypeRelation<'tcx> for CollectAllMismatches<'a, 'tcx> { ) -> RelateResult<'tcx, ty::Region<'tcx>> { Ok(a) } + fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { - if a == b || matches!(a.kind(), ty::Infer(_)) || matches!(b.kind(), ty::Infer(_)) { - return Ok(a); - } - relate::super_relate_tys(self, a, b).or_else(|e| { - self.errors.push(e); - Ok(a) + self.infcx.probe(|_| { + if a.is_ty_infer() || b.is_ty_infer() { + Ok(a) + } else { + self.infcx.super_combine_tys(self, a, b).or_else(|e| { + self.errors.push(e); + Ok(a) + }) + } }) } + fn consts( &mut self, a: ty::Const<'tcx>, @@ -64,6 +76,7 @@ impl<'a, 'tcx> TypeRelation<'tcx> for CollectAllMismatches<'a, 'tcx> { } relate::super_relate_consts(self, a, b) // could do something similar here for constants! } + fn binders<T: Relate<'tcx>>( &mut self, a: ty::Binder<'tcx, T>, diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs index 8f317beaa77..5f06c4d8282 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs @@ -33,13 +33,14 @@ use rustc_infer::infer::error_reporting::TypeErrCtxt; use rustc_infer::infer::{InferOk, TypeTrace}; use rustc_middle::traits::select::OverflowError; use rustc_middle::ty::abstract_const::NotConstEvaluatable; -use rustc_middle::ty::error::ExpectedFound; +use rustc_middle::ty::error::{ExpectedFound, TypeError}; use rustc_middle::ty::fold::{TypeFolder, TypeSuperFoldable}; use rustc_middle::ty::print::{with_forced_trimmed_paths, FmtPrinter, Print}; use rustc_middle::ty::{ self, SubtypePredicate, ToPolyTraitRef, ToPredicate, TraitRef, Ty, TyCtxt, TypeFoldable, TypeVisitable, }; +use rustc_session::config::TraitSolver; use rustc_session::Limit; use rustc_span::def_id::LOCAL_CRATE; use rustc_span::symbol::sym; @@ -770,7 +771,11 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ), } }; - + self.check_for_binding_assigned_block_without_tail_expression( + &obligation, + &mut err, + trait_predicate, + ); if self.suggest_add_reference_to_arg( &obligation, &mut err, @@ -868,6 +873,11 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ); } + if self.suggest_add_clone_to_arg(&obligation, &mut err, trait_predicate) { + err.emit(); + return; + } + if self.suggest_impl_trait(&mut err, span, &obligation, trait_predicate) { err.emit(); return; @@ -1092,15 +1102,19 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } ty::PredicateKind::Clause(ty::Clause::RegionOutlives(..)) - | ty::PredicateKind::Clause(ty::Clause::Projection(..)) | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(..)) => { - let predicate = self.resolve_vars_if_possible(obligation.predicate); - struct_span_err!( - self.tcx.sess, + span_bug!( + span, + "outlives clauses should not error outside borrowck. obligation: `{:?}`", + obligation + ) + } + + ty::PredicateKind::Clause(ty::Clause::Projection(..)) => { + span_bug!( span, - E0280, - "the requirement `{}` is not satisfied", - predicate + "projection clauses should be implied from elsewhere. obligation: `{:?}`", + obligation ) } @@ -1167,7 +1181,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } ty::PredicateKind::WellFormed(ty) => { - if !self.tcx.sess.opts.unstable_opts.chalk { + if self.tcx.sess.opts.unstable_opts.trait_solver == TraitSolver::Classic { // WF predicates cannot themselves make // errors. They can only block due to // ambiguity; otherwise, they always @@ -1179,7 +1193,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { // which bounds actually failed to hold. self.tcx.sess.struct_span_err( span, - &format!("the type `{}` is not well-formed (chalk)", ty), + &format!("the type `{}` is not well-formed", ty), ) } } @@ -1215,6 +1229,25 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } } + OutputTypeParameterMismatch( + found_trait_ref, + expected_trait_ref, + terr @ TypeError::CyclicTy(_), + ) => { + let self_ty = found_trait_ref.self_ty().skip_binder(); + let (cause, terr) = if let ty::Closure(def_id, _) = self_ty.kind() { + ( + ObligationCause::dummy_with_span(tcx.def_span(def_id)), + TypeError::CyclicTy(self_ty), + ) + } else { + (obligation.cause.clone(), terr) + }; + self.report_and_explain_type_error( + TypeTrace::poly_trait_refs(&cause, true, expected_trait_ref, found_trait_ref), + terr, + ) + } OutputTypeParameterMismatch(found_trait_ref, expected_trait_ref, _) => { let found_trait_ref = self.resolve_vars_if_possible(found_trait_ref); let expected_trait_ref = self.resolve_vars_if_possible(expected_trait_ref); @@ -1387,7 +1420,6 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { self.note_obligation_cause(&mut err, &obligation); self.point_at_returns_when_relevant(&mut err, &obligation); - err.emit(); } } @@ -2247,23 +2279,7 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { if let (Some(body_id), Some(ty::subst::GenericArgKind::Type(_))) = (body_id, subst.map(|subst| subst.unpack())) { - struct FindExprBySpan<'hir> { - span: Span, - result: Option<&'hir hir::Expr<'hir>>, - } - - impl<'v> hir::intravisit::Visitor<'v> for FindExprBySpan<'v> { - fn visit_expr(&mut self, ex: &'v hir::Expr<'v>) { - if self.span == ex.span { - self.result = Some(ex); - } else { - hir::intravisit::walk_expr(self, ex); - } - } - } - - let mut expr_finder = FindExprBySpan { span, result: None }; - + let mut expr_finder = FindExprBySpan::new(span); expr_finder.visit_expr(&self.tcx.hir().body(body_id).value); if let Some(hir::Expr { @@ -2750,6 +2766,36 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } } +/// Crude way of getting back an `Expr` from a `Span`. +pub struct FindExprBySpan<'hir> { + pub span: Span, + pub result: Option<&'hir hir::Expr<'hir>>, + pub ty_result: Option<&'hir hir::Ty<'hir>>, +} + +impl<'hir> FindExprBySpan<'hir> { + fn new(span: Span) -> Self { + Self { span, result: None, ty_result: None } + } +} + +impl<'v> Visitor<'v> for FindExprBySpan<'v> { + fn visit_expr(&mut self, ex: &'v hir::Expr<'v>) { + if self.span == ex.span { + self.result = Some(ex); + } else { + hir::intravisit::walk_expr(self, ex); + } + } + fn visit_ty(&mut self, ty: &'v hir::Ty<'v>) { + if self.span == ty.span { + self.ty_result = Some(ty); + } else { + hir::intravisit::walk_ty(self, ty); + } + } +} + /// Look for type `param` in an ADT being used only through a reference to confirm that suggesting /// `param: ?Sized` would be a valid constraint. struct FindTypeParam { @@ -2771,7 +2817,7 @@ impl<'v> Visitor<'v> for FindTypeParam { // and suggest `T: ?Sized` regardless of their obligations. This is fine because the errors // in that case should make what happened clear enough. match ty.kind { - hir::TyKind::Ptr(_) | hir::TyKind::Rptr(..) | hir::TyKind::TraitObject(..) => {} + hir::TyKind::Ptr(_) | hir::TyKind::Ref(..) | hir::TyKind::TraitObject(..) => {} hir::TyKind::Path(hir::QPath::Resolved(None, path)) if path.segments.len() == 1 && path.segments[0].ident.name == self.param => { diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs index 9bfe527647d..b0a730c8ad1 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs @@ -117,7 +117,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { Some(if movability.is_some() { "an async closure" } else { "a closure" }) }), hir::Node::Expr(hir::Expr { .. }) => { - let parent_hid = hir.get_parent_node(hir_id); + let parent_hid = hir.parent_id(hir_id); if parent_hid != hir_id { self.describe_enclosure(parent_hid) } else { None } } _ => None, diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs index 036e8f6d47b..43985495827 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs @@ -1,13 +1,16 @@ // ignore-tidy-filelength -use super::{DefIdOrName, Obligation, ObligationCause, ObligationCauseCode, PredicateObligation}; +use super::{ + DefIdOrName, FindExprBySpan, Obligation, ObligationCause, ObligationCauseCode, + PredicateObligation, +}; use crate::autoderef::Autoderef; use crate::infer::InferCtxt; use crate::traits::{NormalizeExt, ObligationCtxt}; use hir::def::CtorOf; -use hir::HirId; +use hir::{Expr, HirId}; use rustc_data_structures::fx::FxHashSet; use rustc_data_structures::stack::ensure_sufficient_stack; use rustc_errors::{ @@ -196,6 +199,20 @@ pub trait TypeErrCtxtExt<'tcx> { trait_pred: ty::PolyTraitPredicate<'tcx>, ) -> bool; + fn check_for_binding_assigned_block_without_tail_expression( + &self, + obligation: &PredicateObligation<'tcx>, + err: &mut Diagnostic, + trait_pred: ty::PolyTraitPredicate<'tcx>, + ); + + fn suggest_add_clone_to_arg( + &self, + obligation: &PredicateObligation<'tcx>, + err: &mut Diagnostic, + trait_pred: ty::PolyTraitPredicate<'tcx>, + ) -> bool; + fn suggest_add_reference_to_arg( &self, obligation: &PredicateObligation<'tcx>, @@ -248,7 +265,7 @@ pub trait TypeErrCtxtExt<'tcx> { fn point_at_returns_when_relevant( &self, - err: &mut Diagnostic, + err: &mut DiagnosticBuilder<'tcx, ErrorGuaranteed>, obligation: &PredicateObligation<'tcx>, ); @@ -335,7 +352,7 @@ pub trait TypeErrCtxtExt<'tcx> { err: &mut Diagnostic, trait_pred: ty::PolyTraitPredicate<'tcx>, ); - fn function_argument_obligation( + fn note_function_argument_obligation( &self, arg_hir_id: HirId, err: &mut Diagnostic, @@ -838,8 +855,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { let hir = self.tcx.hir(); let hir_id = hir.local_def_id_to_hir_id(def_id.as_local()?); - let parent_node = hir.get_parent_node(hir_id); - match hir.find(parent_node) { + match hir.find_parent(hir_id) { Some(hir::Node::Stmt(hir::Stmt { kind: hir::StmtKind::Local(local), .. })) => { get_name(err, &local.pat.kind) } @@ -1033,6 +1049,115 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { true } + fn check_for_binding_assigned_block_without_tail_expression( + &self, + obligation: &PredicateObligation<'tcx>, + err: &mut Diagnostic, + trait_pred: ty::PolyTraitPredicate<'tcx>, + ) { + let mut span = obligation.cause.span; + while span.from_expansion() { + // Remove all the desugaring and macro contexts. + span.remove_mark(); + } + let mut expr_finder = FindExprBySpan::new(span); + let Some(hir::Node::Expr(body)) = self.tcx.hir().find(obligation.cause.body_id) else { return; }; + expr_finder.visit_expr(&body); + let Some(expr) = expr_finder.result else { return; }; + let Some(typeck) = &self.typeck_results else { return; }; + let Some(ty) = typeck.expr_ty_adjusted_opt(expr) else { return; }; + if !ty.is_unit() { + return; + }; + let hir::ExprKind::Path(hir::QPath::Resolved(None, path)) = expr.kind else { return; }; + let hir::def::Res::Local(hir_id) = path.res else { return; }; + let Some(hir::Node::Pat(pat)) = self.tcx.hir().find(hir_id) else { + return; + }; + let Some(hir::Node::Local(hir::Local { + ty: None, + init: Some(init), + .. + })) = self.tcx.hir().find_parent(pat.hir_id) else { return; }; + let hir::ExprKind::Block(block, None) = init.kind else { return; }; + if block.expr.is_some() { + return; + } + let [.., stmt] = block.stmts else { + err.span_label(block.span, "this empty block is missing a tail expression"); + return; + }; + let hir::StmtKind::Semi(tail_expr) = stmt.kind else { return; }; + let Some(ty) = typeck.expr_ty_opt(tail_expr) else { + err.span_label(block.span, "this block is missing a tail expression"); + return; + }; + let ty = self.resolve_numeric_literals_with_default(self.resolve_vars_if_possible(ty)); + let trait_pred_and_self = trait_pred.map_bound(|trait_pred| (trait_pred, ty)); + + let new_obligation = + self.mk_trait_obligation_with_new_self_ty(obligation.param_env, trait_pred_and_self); + if self.predicate_must_hold_modulo_regions(&new_obligation) { + err.span_suggestion_short( + stmt.span.with_lo(tail_expr.span.hi()), + "remove this semicolon", + "", + Applicability::MachineApplicable, + ); + } else { + err.span_label(block.span, "this block is missing a tail expression"); + } + } + + fn suggest_add_clone_to_arg( + &self, + obligation: &PredicateObligation<'tcx>, + err: &mut Diagnostic, + trait_pred: ty::PolyTraitPredicate<'tcx>, + ) -> bool { + let self_ty = self.resolve_vars_if_possible(trait_pred.self_ty()); + let ty = self.tcx.erase_late_bound_regions(self_ty); + let owner = self.tcx.hir().get_parent_item(obligation.cause.body_id); + let Some(generics) = self.tcx.hir().get_generics(owner.def_id) else { return false }; + let ty::Ref(_, inner_ty, hir::Mutability::Not) = ty.kind() else { return false }; + let ty::Param(param) = inner_ty.kind() else { return false }; + let ObligationCauseCode::FunctionArgumentObligation { arg_hir_id, .. } = obligation.cause.code() else { return false }; + let arg_node = self.tcx.hir().get(*arg_hir_id); + let Node::Expr(Expr { kind: hir::ExprKind::Path(_), ..}) = arg_node else { return false }; + + let clone_trait = self.tcx.require_lang_item(LangItem::Clone, None); + let has_clone = |ty| { + self.type_implements_trait(clone_trait, [ty], obligation.param_env) + .must_apply_modulo_regions() + }; + + let new_obligation = self.mk_trait_obligation_with_new_self_ty( + obligation.param_env, + trait_pred.map_bound(|trait_pred| (trait_pred, *inner_ty)), + ); + + if self.predicate_may_hold(&new_obligation) && has_clone(ty) { + if !has_clone(param.to_ty(self.tcx)) { + suggest_constraining_type_param( + self.tcx, + generics, + err, + param.name.as_str(), + "Clone", + Some(clone_trait), + ); + } + err.span_suggestion_verbose( + obligation.cause.span.shrink_to_hi(), + "consider using clone here", + ".clone()".to_string(), + Applicability::MaybeIncorrect, + ); + return true; + } + false + } + fn suggest_add_reference_to_arg( &self, obligation: &PredicateObligation<'tcx>, @@ -1291,29 +1416,25 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { if let ObligationCauseCode::AwaitableExpr(hir_id) = obligation.cause.code().peel_derives() { let hir = self.tcx.hir(); - if let Some(node) = hir_id.and_then(|hir_id| hir.find(hir_id)) { - if let hir::Node::Expr(expr) = node { - // FIXME: use `obligation.predicate.kind()...trait_ref.self_ty()` to see if we have `()` - // and if not maybe suggest doing something else? If we kept the expression around we - // could also check if it is an fn call (very likely) and suggest changing *that*, if - // it is from the local crate. - err.span_suggestion( - span, - "remove the `.await`", - "", - Applicability::MachineApplicable, - ); - // FIXME: account for associated `async fn`s. - if let hir::Expr { span, kind: hir::ExprKind::Call(base, _), .. } = expr { - if let ty::PredicateKind::Clause(ty::Clause::Trait(pred)) = - obligation.predicate.kind().skip_binder() - { - err.span_label( - *span, - &format!("this call returns `{}`", pred.self_ty()), - ); - } - if let Some(typeck_results) = &self.typeck_results + if let Some(hir::Node::Expr(expr)) = hir_id.and_then(|hir_id| hir.find(hir_id)) { + // FIXME: use `obligation.predicate.kind()...trait_ref.self_ty()` to see if we have `()` + // and if not maybe suggest doing something else? If we kept the expression around we + // could also check if it is an fn call (very likely) and suggest changing *that*, if + // it is from the local crate. + err.span_suggestion( + span, + "remove the `.await`", + "", + Applicability::MachineApplicable, + ); + // FIXME: account for associated `async fn`s. + if let hir::Expr { span, kind: hir::ExprKind::Call(base, _), .. } = expr { + if let ty::PredicateKind::Clause(ty::Clause::Trait(pred)) = + obligation.predicate.kind().skip_binder() + { + err.span_label(*span, &format!("this call returns `{}`", pred.self_ty())); + } + if let Some(typeck_results) = &self.typeck_results && let ty = typeck_results.expr_ty_adjusted(base) && let ty::FnDef(def_id, _substs) = ty.kind() && let Some(hir::Node::Item(hir::Item { ident, span, vis_span, .. })) = @@ -1339,7 +1460,6 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ); } } - } } } } @@ -1399,6 +1519,13 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { .source_map() .span_take_while(span, |c| c.is_whitespace() || *c == '&'); if points_at_arg && mutability.is_not() && refs_number > 0 { + // If we have a call like foo(&mut buf), then don't suggest foo(&mut mut buf) + if snippet + .trim_start_matches(|c: char| c.is_whitespace() || c == '&') + .starts_with("mut") + { + return; + } err.span_suggestion_verbose( sp, "consider changing this borrow's mutability", @@ -1426,7 +1553,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { trait_pred: ty::PolyTraitPredicate<'tcx>, ) -> bool { let hir = self.tcx.hir(); - let parent_node = hir.get_parent_node(obligation.cause.body_id); + let parent_node = hir.parent_id(obligation.cause.body_id); let node = hir.find(parent_node); if let Some(hir::Node::Item(hir::Item { kind: hir::ItemKind::Fn(sig, _, body_id), .. })) = node && let hir::ExprKind::Block(blk, _) = &hir.body(*body_id).value.kind @@ -1463,7 +1590,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { fn return_type_span(&self, obligation: &PredicateObligation<'tcx>) -> Option<Span> { let hir = self.tcx.hir(); - let parent_node = hir.get_parent_node(obligation.cause.body_id); + let parent_node = hir.parent_id(obligation.cause.body_id); let Some(hir::Node::Item(hir::Item { kind: hir::ItemKind::Fn(sig, ..), .. })) = hir.find(parent_node) else { return None; }; @@ -1488,7 +1615,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } let hir = self.tcx.hir(); - let fn_hir_id = hir.get_parent_node(obligation.cause.body_id); + let fn_hir_id = hir.parent_id(obligation.cause.body_id); let node = hir.find(fn_hir_id); let Some(hir::Node::Item(hir::Item { kind: hir::ItemKind::Fn(sig, _, body_id), @@ -1691,7 +1818,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { fn point_at_returns_when_relevant( &self, - err: &mut Diagnostic, + err: &mut DiagnosticBuilder<'tcx, ErrorGuaranteed>, obligation: &PredicateObligation<'tcx>, ) { match obligation.cause.code().peel_derives() { @@ -1700,7 +1827,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } let hir = self.tcx.hir(); - let parent_node = hir.get_parent_node(obligation.cause.body_id); + let parent_node = hir.parent_id(obligation.cause.body_id); let node = hir.find(parent_node); if let Some(hir::Node::Item(hir::Item { kind: hir::ItemKind::Fn(_, _, body_id), .. })) = node @@ -1713,7 +1840,15 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { for expr in &visitor.returns { if let Some(returned_ty) = typeck_results.node_type_opt(expr.hir_id) { let ty = self.resolve_vars_if_possible(returned_ty); - err.span_label(expr.span, &format!("this returned value is of type `{}`", ty)); + if ty.references_error() { + // don't print out the [type error] here + err.delay_as_bug(); + } else { + err.span_label( + expr.span, + &format!("this returned value is of type `{}`", ty), + ); + } } } } @@ -2296,7 +2431,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { let expr = hir.expect_expr(expr_id); debug!("target_ty evaluated from {:?}", expr); - let parent = hir.get_parent_node(expr_id); + let parent = hir.parent_id(expr_id); if let Some(hir::Node::Expr(e)) = hir.find(parent) { let parent_span = hir.span(parent); let parent_did = parent.owner.to_def_id(); @@ -2517,8 +2652,17 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } } ObligationCauseCode::VariableType(hir_id) => { - let parent_node = self.tcx.hir().get_parent_node(hir_id); + let parent_node = self.tcx.hir().parent_id(hir_id); match self.tcx.hir().find(parent_node) { + Some(Node::Local(hir::Local { ty: Some(ty), .. })) => { + err.span_suggestion_verbose( + ty.span.shrink_to_lo(), + "consider borrowing here", + "&", + Applicability::MachineApplicable, + ); + err.note("all local variables must have a statically known size"); + } Some(Node::Local(hir::Local { init: Some(hir::Expr { kind: hir::ExprKind::Index(_, _), span, .. }), .. @@ -2688,7 +2832,9 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { // Don't print the tuple of capture types 'print: { if !is_upvar_tys_infer_tuple { - let msg = format!("required because it appears within the type `{}`", ty); + let msg = with_forced_trimmed_paths!(format!( + "required because it appears within the type `{ty}`", + )); match ty.kind() { ty::Adt(def, _) => match self.tcx.opt_item_ident(def.did()) { Some(ident) => err.span_note(ident.span, &msg), @@ -2729,7 +2875,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { let mut msg = "required because it captures the following types: ".to_owned(); for ty in bound_tys.skip_binder() { - write!(msg, "`{}`, ", ty).unwrap(); + with_forced_trimmed_paths!(write!(msg, "`{}`, ", ty).unwrap()); } err.note(msg.trim_end_matches(", ")) } @@ -2740,7 +2886,9 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { let kind = tcx.generator_kind(def_id).unwrap().descr(); err.span_note( sp, - &format!("required because it's used within this {}", kind), + with_forced_trimmed_paths!(&format!( + "required because it's used within this {kind}", + )), ) } ty::Closure(def_id, _) => err.span_note( @@ -2909,7 +3057,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ref parent_code, .. } => { - self.function_argument_obligation( + self.note_function_argument_obligation( arg_hir_id, err, parent_code, @@ -2964,7 +3112,9 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { let expr_ty = with_forced_trimmed_paths!(self.ty_to_string(expr_ty)); err.span_label( expr_span, - format!("return type was inferred to be `{expr_ty}` here"), + with_forced_trimmed_paths!(format!( + "return type was inferred to be `{expr_ty}` here", + )), ); } } @@ -2982,7 +3132,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { span: Span, ) { let body_hir_id = obligation.cause.body_id; - let item_id = self.tcx.hir().get_parent_node(body_hir_id); + let item_id = self.tcx.hir().parent_id(body_hir_id); if let Some(body_id) = self.tcx.hir().maybe_body_owned_by(self.tcx.hir().local_def_id(item_id)) @@ -3141,23 +3291,20 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ); } } - fn function_argument_obligation( + fn note_function_argument_obligation( &self, arg_hir_id: HirId, err: &mut Diagnostic, parent_code: &ObligationCauseCode<'tcx>, param_env: ty::ParamEnv<'tcx>, - predicate: ty::Predicate<'tcx>, + failed_pred: ty::Predicate<'tcx>, call_hir_id: HirId, ) { let tcx = self.tcx; let hir = tcx.hir(); - if let Some(Node::Expr(expr)) = hir.find(arg_hir_id) { - let parent_id = hir.get_parent_item(arg_hir_id); - let typeck_results: &TypeckResults<'tcx> = match &self.typeck_results { - Some(t) if t.hir_owner == parent_id => t, - _ => self.tcx.typeck(parent_id.def_id), - }; + if let Some(Node::Expr(expr)) = hir.find(arg_hir_id) + && let Some(typeck_results) = &self.typeck_results + { if let hir::Expr { kind: hir::ExprKind::Block(..), .. } = expr { let expr = expr.peel_blocks(); let ty = typeck_results.expr_ty_adjusted_opt(expr).unwrap_or(tcx.ty_error()); @@ -3182,37 +3329,29 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { let mut type_diffs = vec![]; if let ObligationCauseCode::ExprBindingObligation(def_id, _, _, idx) = parent_code.deref() - && let predicates = self.tcx.predicates_of(def_id).instantiate_identity(self.tcx) - && let Some(pred) = predicates.predicates.get(*idx) + && let Some(node_substs) = typeck_results.node_substs_opt(call_hir_id) + && let where_clauses = self.tcx.predicates_of(def_id).instantiate(self.tcx, node_substs) + && let Some(where_pred) = where_clauses.predicates.get(*idx) { - if let Ok(trait_pred) = pred.kind().try_map_bound(|pred| match pred { - ty::PredicateKind::Clause(ty::Clause::Trait(trait_pred)) => Ok(trait_pred), - _ => Err(()), - }) - && let Ok(trait_predicate) = predicate.kind().try_map_bound(|pred| match pred { - ty::PredicateKind::Clause(ty::Clause::Trait(trait_pred)) => Ok(trait_pred), - _ => Err(()), - }) + if let Some(where_pred) = where_pred.to_opt_poly_trait_pred() + && let Some(failed_pred) = failed_pred.to_opt_poly_trait_pred() { let mut c = CollectAllMismatches { infcx: self.infcx, param_env, errors: vec![], }; - if let Ok(_) = c.relate(trait_pred, trait_predicate) { + if let Ok(_) = c.relate(where_pred, failed_pred) { type_diffs = c.errors; } - } else if let ty::PredicateKind::Clause( - ty::Clause::Projection(proj) - ) = pred.kind().skip_binder() - && let ty::PredicateKind::Clause( - ty::Clause::Projection(projection) - ) = predicate.kind().skip_binder() + } else if let Some(where_pred) = where_pred.to_opt_poly_projection_pred() + && let Some(failed_pred) = failed_pred.to_opt_poly_projection_pred() + && let Some(found) = failed_pred.skip_binder().term.ty() { type_diffs = vec![ Sorts(ty::error::ExpectedFound { - expected: self.tcx.mk_ty(ty::Alias(ty::Projection, proj.projection_ty)), - found: projection.term.ty().unwrap(), + expected: self.tcx.mk_ty(ty::Alias(ty::Projection, where_pred.skip_binder().projection_ty)), + found, }), ]; } @@ -3220,16 +3359,16 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { if let hir::ExprKind::Path(hir::QPath::Resolved(None, path)) = expr.kind && let hir::Path { res: hir::def::Res::Local(hir_id), .. } = path && let Some(hir::Node::Pat(binding)) = self.tcx.hir().find(*hir_id) - && let parent_hir_id = self.tcx.hir().get_parent_node(binding.hir_id) + && let parent_hir_id = self.tcx.hir().parent_id(binding.hir_id) && let Some(hir::Node::Local(local)) = self.tcx.hir().find(parent_hir_id) && let Some(binding_expr) = local.init { // If the expression we're calling on is a binding, we want to point at the // `let` when talking about the type. Otherwise we'll point at every part // of the method chain with the type. - self.point_at_chain(binding_expr, typeck_results, type_diffs, param_env, err); + self.point_at_chain(binding_expr, &typeck_results, type_diffs, param_env, err); } else { - self.point_at_chain(expr, typeck_results, type_diffs, param_env, err); + self.point_at_chain(expr, &typeck_results, type_diffs, param_env, err); } } let call_node = hir.find(call_hir_id); @@ -3238,7 +3377,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { })) = call_node { if Some(rcvr.span) == err.span.primary_span() { - err.replace_span_with(path.ident.span); + err.replace_span_with(path.ident.span, true); } } if let Some(Node::Expr(hir::Expr { @@ -3288,8 +3427,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { if let hir::ExprKind::Path(hir::QPath::Resolved(None, path)) = expr.kind && let hir::Path { res: hir::def::Res::Local(hir_id), .. } = path && let Some(hir::Node::Pat(binding)) = self.tcx.hir().find(*hir_id) - && let parent_hir_id = self.tcx.hir().get_parent_node(binding.hir_id) - && let Some(parent) = self.tcx.hir().find(parent_hir_id) + && let Some(parent) = self.tcx.hir().find_parent(binding.hir_id) { // We've reached the root of the method call chain... if let hir::Node::Local(local) = parent @@ -3483,7 +3621,7 @@ fn hint_missing_borrow<'tcx>( let arg_spans = fn_decl.inputs.iter().map(|ty| ty.span); - fn get_deref_type_and_refs<'tcx>(mut ty: Ty<'tcx>) -> (Ty<'tcx>, usize) { + fn get_deref_type_and_refs(mut ty: Ty<'_>) -> (Ty<'_>, usize) { let mut refs = 0; while let ty::Ref(_, new_ty, _) = ty.kind() { diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs index 2566d793d78..37b40a2f75a 100644 --- a/compiler/rustc_trait_selection/src/traits/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/mod.rs @@ -102,7 +102,7 @@ pub enum TraitQueryMode { /// spans etc. passed in and hence can do reasonable /// error reporting on their own. Standard, - /// Canonicalized queries get dummy spans and hence + /// Canonical queries get dummy spans and hence /// must generally propagate errors to /// pre-canonicalization callsites. Canonical, @@ -450,9 +450,6 @@ pub fn impossible_predicates<'tcx>( } let errors = ocx.select_all_or_error(); - // Clean up after ourselves - let _ = infcx.inner.borrow_mut().opaque_type_storage.take_opaque_types(); - let result = !errors.is_empty(); debug!("impossible_predicates = {:?}", result); result @@ -484,10 +481,7 @@ fn subst_and_check_impossible_predicates<'tcx>( /// /// This only considers predicates that reference the impl's generics, and not /// those that reference the method's generics. -fn is_impossible_method<'tcx>( - tcx: TyCtxt<'tcx>, - (impl_def_id, trait_item_def_id): (DefId, DefId), -) -> bool { +fn is_impossible_method(tcx: TyCtxt<'_>, (impl_def_id, trait_item_def_id): (DefId, DefId)) -> bool { struct ReferencesOnlyParentGenerics<'tcx> { tcx: TyCtxt<'tcx>, generics: &'tcx ty::Generics, diff --git a/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs b/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs index e1092a788e3..f2c5f730b31 100644 --- a/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs +++ b/compiler/rustc_trait_selection/src/traits/outlives_bounds.rs @@ -34,7 +34,7 @@ impl<'a, 'tcx: 'a> InferCtxtExt<'a, 'tcx> for InferCtxt<'tcx> { /// argument types are well-formed. This may imply certain relationships /// between generic parameters. For example: /// ``` - /// fn foo<'a,T>(x: &'a T) {} + /// fn foo<T>(x: &T) {} /// ``` /// can only be called with a `'a` and `T` such that `&'a T` is WF. /// For `&'a T` to be WF, `T: 'a` must hold. So we can assume `T: 'a`. diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs index 84d7244c1db..f7614997585 100644 --- a/compiler/rustc_trait_selection/src/traits/project.rs +++ b/compiler/rustc_trait_selection/src/traits/project.rs @@ -25,7 +25,6 @@ use rustc_data_structures::sso::SsoHashSet; use rustc_data_structures::stack::ensure_sufficient_stack; use rustc_errors::ErrorGuaranteed; use rustc_hir::def::DefKind; -use rustc_hir::def_id::DefId; use rustc_hir::lang_items::LangItem; use rustc_infer::infer::at::At; use rustc_infer::infer::resolve::OpportunisticRegionResolver; @@ -1553,7 +1552,7 @@ fn assemble_candidates_from_impls<'cx, 'tcx>( // NOTE: This should be kept in sync with the similar code in // `rustc_ty_utils::instance::resolve_associated_item()`. let node_item = - assoc_def(selcx, impl_data.impl_def_id, obligation.predicate.def_id) + specialization_graph::assoc_def(selcx.tcx(), impl_data.impl_def_id, obligation.predicate.def_id) .map_err(|ErrorGuaranteed { .. }| ())?; if node_item.is_final() { @@ -2113,7 +2112,7 @@ fn confirm_impl_candidate<'cx, 'tcx>( let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap(); let param_env = obligation.param_env; - let Ok(assoc_ty) = assoc_def(selcx, impl_def_id, assoc_item_id) else { + let Ok(assoc_ty) = specialization_graph::assoc_def(tcx, impl_def_id, assoc_item_id) else { return Progress { term: tcx.ty_error().into(), obligations: nested }; }; @@ -2210,7 +2209,7 @@ fn confirm_impl_trait_in_trait_candidate<'tcx>( let mut obligations = data.nested; let trait_fn_def_id = tcx.impl_trait_in_trait_parent(obligation.predicate.def_id); - let Ok(leaf_def) = assoc_def(selcx, data.impl_def_id, trait_fn_def_id) else { + let Ok(leaf_def) = specialization_graph::assoc_def(tcx, data.impl_def_id, trait_fn_def_id) else { return Progress { term: tcx.ty_error().into(), obligations }; }; if !leaf_def.item.defaultness(tcx).has_value() { @@ -2285,7 +2284,7 @@ fn confirm_impl_trait_in_trait_candidate<'tcx>( obligation.param_env, cause.clone(), obligation.recursion_depth + 1, - tcx.bound_trait_impl_trait_tys(impl_fn_def_id) + tcx.bound_return_position_impl_trait_in_trait_tys(impl_fn_def_id) .map_bound(|tys| { tys.map_or_else(|_| tcx.ty_error(), |tys| tys[&obligation.predicate.def_id]) }) @@ -2347,58 +2346,6 @@ fn assoc_ty_own_obligations<'cx, 'tcx>( } } -/// Locate the definition of an associated type in the specialization hierarchy, -/// starting from the given impl. -/// -/// Based on the "projection mode", this lookup may in fact only examine the -/// topmost impl. See the comments for `Reveal` for more details. -fn assoc_def( - selcx: &SelectionContext<'_, '_>, - impl_def_id: DefId, - assoc_def_id: DefId, -) -> Result<specialization_graph::LeafDef, ErrorGuaranteed> { - let tcx = selcx.tcx(); - let trait_def_id = tcx.impl_trait_ref(impl_def_id).unwrap().def_id; - let trait_def = tcx.trait_def(trait_def_id); - - // This function may be called while we are still building the - // specialization graph that is queried below (via TraitDef::ancestors()), - // so, in order to avoid unnecessary infinite recursion, we manually look - // for the associated item at the given impl. - // If there is no such item in that impl, this function will fail with a - // cycle error if the specialization graph is currently being built. - if let Some(&impl_item_id) = tcx.impl_item_implementor_ids(impl_def_id).get(&assoc_def_id) { - let item = tcx.associated_item(impl_item_id); - let impl_node = specialization_graph::Node::Impl(impl_def_id); - return Ok(specialization_graph::LeafDef { - item: *item, - defining_node: impl_node, - finalizing_node: if item.defaultness(tcx).is_default() { - None - } else { - Some(impl_node) - }, - }); - } - - let ancestors = trait_def.ancestors(tcx, impl_def_id)?; - if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_def_id) { - Ok(assoc_item) - } else { - // This is saying that neither the trait nor - // the impl contain a definition for this - // associated type. Normally this situation - // could only arise through a compiler bug -- - // if the user wrote a bad item name, it - // should have failed in astconv. - bug!( - "No associated type `{}` for {}", - tcx.item_name(assoc_def_id), - tcx.def_path_str(impl_def_id) - ) - } -} - pub(crate) trait ProjectionCacheKeyExt<'cx, 'tcx>: Sized { fn from_poly_projection_predicate( selcx: &mut SelectionContext<'cx, 'tcx>, diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs index 86b015767f0..e6db96c9e55 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs @@ -1,4 +1,4 @@ -use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::infer::canonical::{Canonical, CanonicalQueryResponse}; use crate::traits::query::Fallible; use rustc_middle::ty::{ParamEnvAnd, TyCtxt}; @@ -16,8 +16,8 @@ impl<'tcx> super::QueryTypeOp<'tcx> for AscribeUserType<'tcx> { fn perform_query( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, ()>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, ()>> { tcx.type_op_ascribe_user_type(canonicalized) } } diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/eq.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/eq.rs index 490114aacd1..8c9b9610cb6 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/eq.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/eq.rs @@ -1,4 +1,4 @@ -use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::infer::canonical::{Canonical, CanonicalQueryResponse}; use crate::traits::query::Fallible; use rustc_middle::ty::{ParamEnvAnd, TyCtxt}; @@ -16,8 +16,8 @@ impl<'tcx> super::QueryTypeOp<'tcx> for Eq<'tcx> { fn perform_query( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, ()>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, ()>> { tcx.type_op_eq(canonicalized) } } diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs index 2a3319f0f26..18d7c9b1936 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs @@ -1,4 +1,4 @@ -use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::infer::canonical::{Canonical, CanonicalQueryResponse}; use crate::traits::query::Fallible; use rustc_infer::traits::query::OutlivesBound; use rustc_middle::ty::{self, ParamEnvAnd, Ty, TyCtxt}; @@ -27,8 +27,8 @@ impl<'tcx> super::QueryTypeOp<'tcx> for ImpliedOutlivesBounds<'tcx> { fn perform_query( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self::QueryResponse>> { // FIXME this `unchecked_map` is only necessary because the // query is defined as taking a `ParamEnvAnd<Ty>`; it should // take an `ImpliedOutlivesBounds` instead diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs index 29ae8ae6b6e..97002b461aa 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/mod.rs @@ -1,10 +1,10 @@ use crate::infer::canonical::{ - Canonicalized, CanonicalizedQueryResponse, OriginalQueryValues, QueryRegionConstraints, + Canonical, CanonicalQueryResponse, OriginalQueryValues, QueryRegionConstraints, }; use crate::infer::{InferCtxt, InferOk}; use crate::traits::query::Fallible; use crate::traits::ObligationCause; -use rustc_infer::infer::canonical::{Canonical, Certainty}; +use rustc_infer::infer::canonical::Certainty; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::PredicateObligations; use rustc_middle::ty::fold::TypeFoldable; @@ -73,8 +73,8 @@ pub trait QueryTypeOp<'tcx>: fmt::Debug + Copy + TypeFoldable<'tcx> + 'tcx { /// not captured in the return value. fn perform_query( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>>; + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self::QueryResponse>>; fn fully_perform_into( query_key: ParamEnvAnd<'tcx, Self>, diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/normalize.rs index e92ca7325d3..8f0b4de31e6 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/normalize.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/normalize.rs @@ -1,4 +1,4 @@ -use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::infer::canonical::{Canonical, CanonicalQueryResponse}; use crate::traits::query::Fallible; use rustc_middle::ty::fold::TypeFoldable; use rustc_middle::ty::{self, Lift, ParamEnvAnd, Ty, TyCtxt}; @@ -18,8 +18,8 @@ where fn perform_query( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self::QueryResponse>> { T::type_op_method(tcx, canonicalized) } } @@ -27,15 +27,15 @@ where pub trait Normalizable<'tcx>: fmt::Debug + TypeFoldable<'tcx> + Lift<'tcx> + Copy { fn type_op_method( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>>; + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self>>; } impl<'tcx> Normalizable<'tcx> for Ty<'tcx> { fn type_op_method( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self>> { tcx.type_op_normalize_ty(canonicalized) } } @@ -43,8 +43,8 @@ impl<'tcx> Normalizable<'tcx> for Ty<'tcx> { impl<'tcx> Normalizable<'tcx> for ty::Predicate<'tcx> { fn type_op_method( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self>> { tcx.type_op_normalize_predicate(canonicalized) } } @@ -52,8 +52,8 @@ impl<'tcx> Normalizable<'tcx> for ty::Predicate<'tcx> { impl<'tcx> Normalizable<'tcx> for ty::PolyFnSig<'tcx> { fn type_op_method( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self>> { tcx.type_op_normalize_poly_fn_sig(canonicalized) } } @@ -61,8 +61,8 @@ impl<'tcx> Normalizable<'tcx> for ty::PolyFnSig<'tcx> { impl<'tcx> Normalizable<'tcx> for ty::FnSig<'tcx> { fn type_op_method( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self>> { tcx.type_op_normalize_fn_sig(canonicalized) } } diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs index b63382429d0..0d42cd8250a 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs @@ -1,4 +1,4 @@ -use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::infer::canonical::{Canonical, CanonicalQueryResponse}; use crate::traits::query::dropck_outlives::{trivial_dropck_outlives, DropckOutlivesResult}; use crate::traits::query::Fallible; use rustc_middle::ty::{ParamEnvAnd, Ty, TyCtxt}; @@ -30,8 +30,8 @@ impl<'tcx> super::QueryTypeOp<'tcx> for DropckOutlives<'tcx> { fn perform_query( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, Self::QueryResponse>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, Self::QueryResponse>> { // Subtle: note that we are not invoking // `infcx.at(...).dropck_outlives(...)` here, but rather the // underlying `dropck_outlives` query. This same underlying diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/prove_predicate.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/prove_predicate.rs index 68434c2b68d..b63da28e274 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/prove_predicate.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/prove_predicate.rs @@ -1,4 +1,4 @@ -use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::infer::canonical::{Canonical, CanonicalQueryResponse}; use crate::traits::query::Fallible; use rustc_middle::ty::{self, ParamEnvAnd, TyCtxt}; @@ -32,8 +32,8 @@ impl<'tcx> super::QueryTypeOp<'tcx> for ProvePredicate<'tcx> { fn perform_query( tcx: TyCtxt<'tcx>, - mut canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, ()>> { + mut canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, ()>> { match canonicalized.value.value.predicate.kind().skip_binder() { ty::PredicateKind::Clause(ty::Clause::Trait(pred)) => { canonicalized.value.param_env.remap_constness_with(pred.constness); diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/subtype.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/subtype.rs index 57290b66914..c51292eba14 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/subtype.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/subtype.rs @@ -1,4 +1,4 @@ -use crate::infer::canonical::{Canonicalized, CanonicalizedQueryResponse}; +use crate::infer::canonical::{Canonical, CanonicalQueryResponse}; use crate::traits::query::Fallible; use rustc_middle::ty::{ParamEnvAnd, TyCtxt}; @@ -13,8 +13,8 @@ impl<'tcx> super::QueryTypeOp<'tcx> for Subtype<'tcx> { fn perform_query( tcx: TyCtxt<'tcx>, - canonicalized: Canonicalized<'tcx, ParamEnvAnd<'tcx, Self>>, - ) -> Fallible<CanonicalizedQueryResponse<'tcx, ()>> { + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalQueryResponse<'tcx, ()>> { tcx.type_op_subtype(canonicalized) } } diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs index f6fe71fbd4f..15526b34ed2 100644 --- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs +++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs @@ -12,9 +12,10 @@ use rustc_index::bit_set::GrowableBitSet; use rustc_infer::infer::InferOk; use rustc_infer::infer::LateBoundRegionConversionTime::HigherRankedType; use rustc_middle::ty::{ - self, GenericArg, GenericArgKind, GenericParamDefKind, InternalSubsts, SubstsRef, - ToPolyTraitRef, ToPredicate, Ty, TyCtxt, + self, Binder, GenericArg, GenericArgKind, GenericParamDefKind, InternalSubsts, SubstsRef, + ToPolyTraitRef, ToPredicate, TraitRef, Ty, TyCtxt, }; +use rustc_session::config::TraitSolver; use rustc_span::def_id::DefId; use crate::traits::project::{normalize_with_depth, normalize_with_depth_to}; @@ -98,8 +99,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ImplSource::Future(vtable_future) } - FnPointerCandidate { .. } => { - let data = self.confirm_fn_pointer_candidate(obligation)?; + FnPointerCandidate { is_const } => { + let data = self.confirm_fn_pointer_candidate(obligation, is_const)?; ImplSource::FnPointer(data) } @@ -597,17 +598,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { fn confirm_fn_pointer_candidate( &mut self, obligation: &TraitObligation<'tcx>, + is_const: bool, ) -> Result<ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> { debug!(?obligation, "confirm_fn_pointer_candidate"); + let tcx = self.tcx(); let self_ty = self .infcx .shallow_resolve(obligation.self_ty().no_bound_vars()) .expect("fn pointer should not capture bound vars from predicate"); - let sig = self_ty.fn_sig(self.tcx()); + let sig = self_ty.fn_sig(tcx); let trait_ref = closure_trait_ref_and_return_type( - self.tcx(), + tcx, obligation.predicate.def_id(), self_ty, sig, @@ -616,9 +619,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { .map_bound(|(trait_ref, _)| trait_ref); let mut nested = self.confirm_poly_trait_refs(obligation, trait_ref)?; + let cause = obligation.derived_cause(BuiltinDerivedObligation); + + if obligation.is_const() && !is_const { + // function is a trait method + if let ty::FnDef(def_id, substs) = self_ty.kind() && let Some(trait_id) = tcx.trait_of_item(*def_id) { + let trait_ref = TraitRef::from_method(tcx, trait_id, *substs); + let poly_trait_pred = Binder::dummy(trait_ref).with_constness(ty::BoundConstness::ConstIfConst); + let obligation = Obligation::new(tcx, cause.clone(), obligation.param_env, poly_trait_pred); + nested.push(obligation); + } + } // Confirm the `type Output: Sized;` bound that is present on `FnOnce` - let cause = obligation.derived_cause(BuiltinDerivedObligation); let output_ty = self.infcx.replace_bound_vars_with_placeholders(sig.output()); let output_ty = normalize_with_depth_to( self, @@ -755,8 +768,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { debug!(?closure_def_id, ?trait_ref, ?nested, "confirm closure candidate obligations"); // FIXME: Chalk - - if !self.tcx().sess.opts.unstable_opts.chalk { + if self.tcx().sess.opts.unstable_opts.trait_solver != TraitSolver::Chalk { nested.push(obligation.with( self.tcx(), ty::Binder::dummy(ty::PredicateKind::ClosureKind(closure_def_id, substs, kind)), diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs index 792933096b1..3f14491f803 100644 --- a/compiler/rustc_trait_selection/src/traits/select/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs @@ -755,7 +755,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // contain the "'static" lifetime (any other lifetime // would either be late-bound or local), so it is guaranteed // to outlive any other lifetime - if pred.0.is_global() && !pred.0.has_late_bound_regions() { + if pred.0.is_global() && !pred.0.has_late_bound_vars() { Ok(EvaluatedToOk) } else { Ok(EvaluatedToOkModuloRegions) @@ -1171,19 +1171,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { where I: Iterator<Item = ty::Predicate<'tcx>>, { - cycle.all(|predicate| self.coinductive_predicate(predicate)) - } - - fn coinductive_predicate(&self, predicate: ty::Predicate<'tcx>) -> bool { - let result = match predicate.kind().skip_binder() { - ty::PredicateKind::Clause(ty::Clause::Trait(ref data)) => { - self.tcx().trait_is_coinductive(data.def_id()) - } - ty::PredicateKind::WellFormed(_) => true, - _ => false, - }; - debug!(?predicate, ?result, "coinductive_predicate"); - result + cycle.all(|predicate| predicate.is_coinductive(self.tcx())) } /// Further evaluates `candidate` to decide whether all type parameters match and whether nested @@ -1386,6 +1374,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { FutureCandidate => {} // FnDef where the function is const FnPointerCandidate { is_const: true } => {} + FnPointerCandidate { is_const: false } => { + if let ty::FnDef(def_id, _) = obligation.self_ty().skip_binder().kind() && tcx.trait_of_item(*def_id).is_some() { + // Trait methods are not seen as const unless the trait is implemented as const. + // We do not filter that out in here, but nested obligations will be needed to confirm this. + } else { + continue + } + } ConstDestructCandidate(_) => {} _ => { // reject all other types of candidates @@ -1789,9 +1785,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // Check if a bound would previously have been removed when normalizing // the param_env so that it can be given the lowest priority. See // #50825 for the motivation for this. - let is_global = |cand: &ty::PolyTraitPredicate<'tcx>| { - cand.is_global() && !cand.has_late_bound_regions() - }; + let is_global = + |cand: &ty::PolyTraitPredicate<'tcx>| cand.is_global() && !cand.has_late_bound_vars(); // (*) Prefer `BuiltinCandidate { has_nested: false }`, `PointeeCandidate`, // `DiscriminantKindCandidate`, `ConstDestructCandidate` diff --git a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs index 4546c953393..02b06677740 100644 --- a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs +++ b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs @@ -1,6 +1,7 @@ use super::OverlapError; use crate::traits; +use rustc_errors::ErrorGuaranteed; use rustc_hir::def_id::DefId; use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams}; use rustc_middle::ty::{self, TyCtxt, TypeVisitable}; @@ -379,3 +380,51 @@ impl<'tcx> GraphExt<'tcx> for Graph { self.children.entry(parent).or_default().insert_blindly(tcx, child); } } + +/// Locate the definition of an associated type in the specialization hierarchy, +/// starting from the given impl. +pub(crate) fn assoc_def( + tcx: TyCtxt<'_>, + impl_def_id: DefId, + assoc_def_id: DefId, +) -> Result<LeafDef, ErrorGuaranteed> { + let trait_def_id = tcx.impl_trait_ref(impl_def_id).unwrap().def_id; + let trait_def = tcx.trait_def(trait_def_id); + + // This function may be called while we are still building the + // specialization graph that is queried below (via TraitDef::ancestors()), + // so, in order to avoid unnecessary infinite recursion, we manually look + // for the associated item at the given impl. + // If there is no such item in that impl, this function will fail with a + // cycle error if the specialization graph is currently being built. + if let Some(&impl_item_id) = tcx.impl_item_implementor_ids(impl_def_id).get(&assoc_def_id) { + let &item = tcx.associated_item(impl_item_id); + let impl_node = Node::Impl(impl_def_id); + return Ok(LeafDef { + item, + defining_node: impl_node, + finalizing_node: if item.defaultness(tcx).is_default() { + None + } else { + Some(impl_node) + }, + }); + } + + let ancestors = trait_def.ancestors(tcx, impl_def_id)?; + if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_def_id) { + Ok(assoc_item) + } else { + // This is saying that neither the trait nor + // the impl contain a definition for this + // associated type. Normally this situation + // could only arise through a compiler bug -- + // if the user wrote a bad item name, it + // should have failed in astconv. + bug!( + "No associated type `{}` for {}", + tcx.item_name(assoc_def_id), + tcx.def_path_str(impl_def_id) + ) + } +} diff --git a/compiler/rustc_trait_selection/src/traits/util.rs b/compiler/rustc_trait_selection/src/traits/util.rs index f3ca6a6c779..b5df583e3f4 100644 --- a/compiler/rustc_trait_selection/src/traits/util.rs +++ b/compiler/rustc_trait_selection/src/traits/util.rs @@ -1,6 +1,5 @@ use rustc_errors::Diagnostic; use rustc_span::Span; -use smallvec::smallvec; use smallvec::SmallVec; use rustc_data_structures::fx::FxHashSet; diff --git a/compiler/rustc_trait_selection/src/traits/vtable.rs b/compiler/rustc_trait_selection/src/traits/vtable.rs index 41ce6cdf789..5ec9c2a24cd 100644 --- a/compiler/rustc_trait_selection/src/traits/vtable.rs +++ b/compiler/rustc_trait_selection/src/traits/vtable.rs @@ -191,7 +191,7 @@ fn dump_vtable_entries<'tcx>( }); } -fn own_existential_vtable_entries<'tcx>(tcx: TyCtxt<'tcx>, trait_def_id: DefId) -> &'tcx [DefId] { +fn own_existential_vtable_entries(tcx: TyCtxt<'_>, trait_def_id: DefId) -> &[DefId] { let trait_methods = tcx .associated_items(trait_def_id) .in_definition_order() |