From 4547b622d8d29df964fa2914213088b148c498fc Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:18:32 +0200 Subject: Merging upstream version 1.67.1+dfsg1. Signed-off-by: Daniel Baumann --- .../src/traits/select/candidate_assembly.rs | 386 +++++------------ .../src/traits/select/confirmation.rs | 214 +++++---- .../rustc_trait_selection/src/traits/select/mod.rs | 482 +++++++++++++++------ 3 files changed, 567 insertions(+), 515 deletions(-) (limited to 'compiler/rustc_trait_selection/src/traits/select') diff --git a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs index 4c5bc3339..e4b70f0d2 100644 --- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs +++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs @@ -6,239 +6,21 @@ //! //! [rustc dev guide]:https://rustc-dev-guide.rust-lang.org/traits/resolution.html#candidate-assembly use hir::LangItem; -use rustc_errors::DelayDm; use rustc_hir as hir; -use rustc_hir::def_id::DefId; use rustc_infer::traits::ObligationCause; use rustc_infer::traits::{Obligation, SelectionError, TraitObligation}; -use rustc_lint_defs::builtin::DEREF_INTO_DYN_SUPERTRAIT; -use rustc_middle::ty::print::with_no_trimmed_paths; -use rustc_middle::ty::{self, ToPredicate, Ty, TypeVisitable}; +use rustc_middle::ty::{self, Ty, TypeVisitable}; use rustc_target::spec::abi::Abi; use crate::traits; -use crate::traits::coherence::Conflict; use crate::traits::query::evaluate_obligation::InferCtxtExt; -use crate::traits::{util, SelectionResult}; -use crate::traits::{Ambiguous, ErrorReporting, Overflow, Unimplemented}; +use crate::traits::util; use super::BuiltinImplConditions; -use super::IntercrateAmbiguityCause; -use super::OverflowError; -use super::SelectionCandidate::{self, *}; -use super::{EvaluatedCandidate, SelectionCandidateSet, SelectionContext, TraitObligationStack}; +use super::SelectionCandidate::*; +use super::{SelectionCandidateSet, SelectionContext, TraitObligationStack}; impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { - #[instrument(level = "debug", skip(self), ret)] - pub(super) fn candidate_from_obligation<'o>( - &mut self, - stack: &TraitObligationStack<'o, 'tcx>, - ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { - // Watch out for overflow. This intentionally bypasses (and does - // not update) the cache. - self.check_recursion_limit(&stack.obligation, &stack.obligation)?; - - // Check the cache. Note that we freshen the trait-ref - // separately rather than using `stack.fresh_trait_ref` -- - // this is because we want the unbound variables to be - // replaced with fresh types starting from index 0. - let cache_fresh_trait_pred = self.infcx.freshen(stack.obligation.predicate); - debug!(?cache_fresh_trait_pred); - debug_assert!(!stack.obligation.predicate.has_escaping_bound_vars()); - - if let Some(c) = - self.check_candidate_cache(stack.obligation.param_env, cache_fresh_trait_pred) - { - debug!("CACHE HIT"); - return c; - } - - // If no match, compute result and insert into cache. - // - // FIXME(nikomatsakis) -- this cache is not taking into - // account cycles that may have occurred in forming the - // candidate. I don't know of any specific problems that - // result but it seems awfully suspicious. - let (candidate, dep_node) = - self.in_task(|this| this.candidate_from_obligation_no_cache(stack)); - - debug!("CACHE MISS"); - self.insert_candidate_cache( - stack.obligation.param_env, - cache_fresh_trait_pred, - dep_node, - candidate.clone(), - ); - candidate - } - - fn candidate_from_obligation_no_cache<'o>( - &mut self, - stack: &TraitObligationStack<'o, 'tcx>, - ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { - if let Err(conflict) = self.is_knowable(stack) { - debug!("coherence stage: not knowable"); - if self.intercrate_ambiguity_causes.is_some() { - debug!("evaluate_stack: intercrate_ambiguity_causes is some"); - // Heuristics: show the diagnostics when there are no candidates in crate. - if let Ok(candidate_set) = self.assemble_candidates(stack) { - let mut no_candidates_apply = true; - - for c in candidate_set.vec.iter() { - if self.evaluate_candidate(stack, &c)?.may_apply() { - no_candidates_apply = false; - break; - } - } - - if !candidate_set.ambiguous && no_candidates_apply { - let trait_ref = stack.obligation.predicate.skip_binder().trait_ref; - let self_ty = trait_ref.self_ty(); - let (trait_desc, self_desc) = with_no_trimmed_paths!({ - let trait_desc = trait_ref.print_only_trait_path().to_string(); - let self_desc = if self_ty.has_concrete_skeleton() { - Some(self_ty.to_string()) - } else { - None - }; - (trait_desc, self_desc) - }); - let cause = if let Conflict::Upstream = conflict { - IntercrateAmbiguityCause::UpstreamCrateUpdate { trait_desc, self_desc } - } else { - IntercrateAmbiguityCause::DownstreamCrate { trait_desc, self_desc } - }; - debug!(?cause, "evaluate_stack: pushing cause"); - self.intercrate_ambiguity_causes.as_mut().unwrap().insert(cause); - } - } - } - return Ok(None); - } - - let candidate_set = self.assemble_candidates(stack)?; - - if candidate_set.ambiguous { - debug!("candidate set contains ambig"); - return Ok(None); - } - - let candidates = candidate_set.vec; - - debug!(?stack, ?candidates, "assembled {} candidates", candidates.len()); - - // At this point, we know that each of the entries in the - // candidate set is *individually* applicable. Now we have to - // figure out if they contain mutual incompatibilities. This - // frequently arises if we have an unconstrained input type -- - // for example, we are looking for `$0: Eq` where `$0` is some - // unconstrained type variable. In that case, we'll get a - // candidate which assumes $0 == int, one that assumes `$0 == - // usize`, etc. This spells an ambiguity. - - let mut candidates = self.filter_impls(candidates, stack.obligation); - - // If there is more than one candidate, first winnow them down - // by considering extra conditions (nested obligations and so - // forth). We don't winnow if there is exactly one - // candidate. This is a relatively minor distinction but it - // can lead to better inference and error-reporting. An - // example would be if there was an impl: - // - // impl Vec { fn push_clone(...) { ... } } - // - // and we were to see some code `foo.push_clone()` where `boo` - // is a `Vec` and `Bar` does not implement `Clone`. If - // we were to winnow, we'd wind up with zero candidates. - // Instead, we select the right impl now but report "`Bar` does - // not implement `Clone`". - if candidates.len() == 1 { - return self.filter_reservation_impls(candidates.pop().unwrap(), stack.obligation); - } - - // Winnow, but record the exact outcome of evaluation, which - // is needed for specialization. Propagate overflow if it occurs. - let mut candidates = candidates - .into_iter() - .map(|c| match self.evaluate_candidate(stack, &c) { - Ok(eval) if eval.may_apply() => { - Ok(Some(EvaluatedCandidate { candidate: c, evaluation: eval })) - } - Ok(_) => Ok(None), - Err(OverflowError::Canonical) => Err(Overflow(OverflowError::Canonical)), - Err(OverflowError::ErrorReporting) => Err(ErrorReporting), - Err(OverflowError::Error(e)) => Err(Overflow(OverflowError::Error(e))), - }) - .flat_map(Result::transpose) - .collect::, _>>()?; - - debug!(?stack, ?candidates, "winnowed to {} candidates", candidates.len()); - - let needs_infer = stack.obligation.predicate.has_non_region_infer(); - - // If there are STILL multiple candidates, we can further - // reduce the list by dropping duplicates -- including - // resolving specializations. - if candidates.len() > 1 { - let mut i = 0; - while i < candidates.len() { - let is_dup = (0..candidates.len()).filter(|&j| i != j).any(|j| { - self.candidate_should_be_dropped_in_favor_of( - &candidates[i], - &candidates[j], - needs_infer, - ) - }); - if is_dup { - debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len()); - candidates.swap_remove(i); - } else { - debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len()); - i += 1; - - // If there are *STILL* multiple candidates, give up - // and report ambiguity. - if i > 1 { - debug!("multiple matches, ambig"); - return Err(Ambiguous( - candidates - .into_iter() - .filter_map(|c| match c.candidate { - SelectionCandidate::ImplCandidate(def_id) => Some(def_id), - _ => None, - }) - .collect(), - )); - } - } - } - } - - // If there are *NO* candidates, then there are no impls -- - // that we know of, anyway. Note that in the case where there - // are unbound type variables within the obligation, it might - // be the case that you could still satisfy the obligation - // from another crate by instantiating the type variables with - // a type from another crate that does have an impl. This case - // is checked for in `evaluate_stack` (and hence users - // who might care about this case, like coherence, should use - // that function). - if candidates.is_empty() { - // If there's an error type, 'downgrade' our result from - // `Err(Unimplemented)` to `Ok(None)`. This helps us avoid - // emitting additional spurious errors, since we're guaranteed - // to have emitted at least one. - if stack.obligation.predicate.references_error() { - debug!(?stack.obligation.predicate, "found error type in predicate, treating as ambiguous"); - return Ok(None); - } - return Err(Unimplemented); - } - - // Just one candidate left. - self.filter_reservation_impls(candidates.pop().unwrap().candidate, stack.obligation) - } - #[instrument(skip(self, stack), level = "debug")] pub(super) fn assemble_candidates<'o>( &mut self, @@ -249,7 +31,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { param_env: obligation.param_env, cause: obligation.cause.clone(), recursion_depth: obligation.recursion_depth, - predicate: self.infcx().resolve_vars_if_possible(obligation.predicate), + predicate: self.infcx.resolve_vars_if_possible(obligation.predicate), }; if obligation.predicate.skip_binder().self_ty().is_ty_var() { @@ -293,10 +75,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates); } else if lang_items.discriminant_kind_trait() == Some(def_id) { // `DiscriminantKind` is automatically implemented for every type. - candidates.vec.push(DiscriminantKindCandidate); + candidates.vec.push(BuiltinCandidate { has_nested: false }); } else if lang_items.pointee_trait() == Some(def_id) { // `Pointee` is automatically implemented for every type. - candidates.vec.push(PointeeCandidate); + candidates.vec.push(BuiltinCandidate { has_nested: false }); } else if lang_items.sized_trait() == Some(def_id) { // Sized is never implementable by end-users, it is // always automatically computed. @@ -312,6 +94,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.assemble_candidates_for_transmutability(obligation, &mut candidates); } else if lang_items.tuple_trait() == Some(def_id) { self.assemble_candidate_for_tuple(obligation, &mut candidates); + } else if lang_items.pointer_sized() == Some(def_id) { + self.assemble_candidate_for_ptr_sized(obligation, &mut candidates); } else { if lang_items.clone_trait() == Some(def_id) { // Same builtin conditions as `Copy`, i.e., every type which has builtin support @@ -321,7 +105,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates); } - self.assemble_generator_candidates(obligation, &mut candidates); + if lang_items.gen_trait() == Some(def_id) { + self.assemble_generator_candidates(obligation, &mut candidates); + } else if lang_items.future_trait() == Some(def_id) { + self.assemble_future_candidates(obligation, &mut candidates); + } + self.assemble_closure_candidates(obligation, &mut candidates); self.assemble_fn_pointer_candidates(obligation, &mut candidates); self.assemble_candidates_from_impls(obligation, &mut candidates); @@ -409,16 +198,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation: &TraitObligation<'tcx>, candidates: &mut SelectionCandidateSet<'tcx>, ) { - if self.tcx().lang_items().gen_trait() != Some(obligation.predicate.def_id()) { - return; - } - // Okay to skip binder because the substs on generator types never // touch bound regions, they just capture the in-scope // type/region parameters. let self_ty = obligation.self_ty().skip_binder(); match self_ty.kind() { - ty::Generator(..) => { + // async constructs get lowered to a special kind of generator that + // should *not* `impl Generator`. + ty::Generator(did, ..) if !self.tcx().generator_is_async(*did) => { debug!(?self_ty, ?obligation, "assemble_generator_candidates",); candidates.vec.push(GeneratorCandidate); @@ -431,6 +218,23 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } } + fn assemble_future_candidates( + &mut self, + obligation: &TraitObligation<'tcx>, + candidates: &mut SelectionCandidateSet<'tcx>, + ) { + let self_ty = obligation.self_ty().skip_binder(); + if let ty::Generator(did, ..) = self_ty.kind() { + // async constructs get lowered to a special kind of generator that + // should directly `impl Future`. + if self.tcx().generator_is_async(*did) { + debug!(?self_ty, ?obligation, "assemble_future_candidates",); + + candidates.vec.push(FutureCandidate); + } + } + } + /// Checks for the artificial impl that the compiler will create for an obligation like `X : /// FnMut<..>` where `X` is a closure type. /// @@ -442,7 +246,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation: &TraitObligation<'tcx>, candidates: &mut SelectionCandidateSet<'tcx>, ) { - let Some(kind) = self.tcx().fn_trait_kind_from_lang_item(obligation.predicate.def_id()) else { + let Some(kind) = self.tcx().fn_trait_kind_from_def_id(obligation.predicate.def_id()) else { return; }; @@ -480,7 +284,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { candidates: &mut SelectionCandidateSet<'tcx>, ) { // We provide impl of all fn traits for fn pointers. - if self.tcx().fn_trait_kind_from_lang_item(obligation.predicate.def_id()).is_none() { + if !self.tcx().is_fn_trait(obligation.predicate.def_id()) { return; } @@ -680,9 +484,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { debug!(?poly_trait_ref, "assemble_candidates_from_object_ty"); - let poly_trait_predicate = self.infcx().resolve_vars_if_possible(obligation.predicate); + let poly_trait_predicate = self.infcx.resolve_vars_if_possible(obligation.predicate); let placeholder_trait_predicate = - self.infcx().replace_bound_vars_with_placeholders(poly_trait_predicate); + self.infcx.replace_bound_vars_with_placeholders(poly_trait_predicate); // Count only those upcast versions that match the trait-ref // we are looking for. Specifically, do not only check for the @@ -713,48 +517,40 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ty: Ty<'tcx>, param_env: ty::ParamEnv<'tcx>, cause: &ObligationCause<'tcx>, - ) -> Option<(Ty<'tcx>, DefId)> { + ) -> Option> { let tcx = self.tcx(); if tcx.features().trait_upcasting { return None; } // - let trait_ref = ty::TraitRef { - def_id: tcx.lang_items().deref_trait()?, - substs: tcx.mk_substs_trait(ty, &[]), - }; + let trait_ref = tcx.mk_trait_ref(tcx.lang_items().deref_trait()?, [ty]); - let obligation = traits::Obligation::new( - cause.clone(), - param_env, - ty::Binder::dummy(trait_ref).without_const().to_predicate(tcx), - ); + let obligation = + traits::Obligation::new(tcx, cause.clone(), param_env, ty::Binder::dummy(trait_ref)); if !self.infcx.predicate_may_hold(&obligation) { return None; } - let ty = traits::normalize_projection_type( - self, - param_env, - ty::ProjectionTy { - item_def_id: tcx.lang_items().deref_target()?, - substs: trait_ref.substs, - }, - cause.clone(), - 0, - // We're *intentionally* throwing these away, - // since we don't actually use them. - &mut vec![], - ) - .ty() - .unwrap(); - - if let ty::Dynamic(data, ..) = ty.kind() { - Some((ty, data.principal_def_id()?)) - } else { - None - } + self.infcx.probe(|_| { + let ty = traits::normalize_projection_type( + self, + param_env, + ty::ProjectionTy { + item_def_id: tcx.lang_items().deref_target()?, + substs: trait_ref.substs, + }, + cause.clone(), + 0, + // We're *intentionally* throwing these away, + // since we don't actually use them. + &mut vec![], + ) + .ty() + .unwrap(); + + if let ty::Dynamic(data, ..) = ty.kind() { data.principal() } else { None } + }) } /// Searches for unsizing that might apply to `obligation`. @@ -787,7 +583,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { match (source.kind(), target.kind()) { // Trait+Kx+'a -> Trait+Ky+'b (upcasts). - (&ty::Dynamic(ref data_a, ..), &ty::Dynamic(ref data_b, ..)) => { + (&ty::Dynamic(ref data_a, _, ty::Dyn), &ty::Dynamic(ref data_b, _, ty::Dyn)) => { // Upcast coercions permit several things: // // 1. Dropping auto traits, e.g., `Foo + Send` to `Foo` @@ -814,24 +610,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let principal_a = data_a.principal().unwrap(); let target_trait_did = principal_def_id_b.unwrap(); let source_trait_ref = principal_a.with_self_ty(self.tcx(), source); - if let Some((deref_output_ty, deref_output_trait_did)) = self - .need_migrate_deref_output_trait_object( - source, - obligation.param_env, - &obligation.cause, - ) - { - if deref_output_trait_did == target_trait_did { - self.tcx().struct_span_lint_hir( - DEREF_INTO_DYN_SUPERTRAIT, - obligation.cause.body_id, - obligation.cause.span, - DelayDm(|| format!( - "`{}` implements `Deref` with supertrait `{}` as output", - source, deref_output_ty - )), - |lint| lint, - ); + if let Some(deref_trait_ref) = self.need_migrate_deref_output_trait_object( + source, + obligation.param_env, + &obligation.cause, + ) { + if deref_trait_ref.def_id() == target_trait_did { return; } } @@ -848,7 +632,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } // `T` -> `Trait` - (_, &ty::Dynamic(..)) => { + (_, &ty::Dynamic(_, _, ty::Dyn)) => { candidates.vec.push(BuiltinUnsizeCandidate); } @@ -951,7 +735,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { return; } - let self_ty = self.infcx().shallow_resolve(obligation.self_ty()); + let self_ty = self.infcx.shallow_resolve(obligation.self_ty()); match self_ty.skip_binder().kind() { ty::Opaque(..) | ty::Dynamic(..) @@ -1018,7 +802,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation: &TraitObligation<'tcx>, candidates: &mut SelectionCandidateSet<'tcx>, ) { - let self_ty = self.infcx().shallow_resolve(obligation.self_ty().skip_binder()); + let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder()); match self_ty.kind() { ty::Tuple(_) => { candidates.vec.push(BuiltinCandidate { has_nested: false }); @@ -1054,4 +838,30 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | ty::Placeholder(_) => {} } } + + fn assemble_candidate_for_ptr_sized( + &mut self, + obligation: &TraitObligation<'tcx>, + candidates: &mut SelectionCandidateSet<'tcx>, + ) { + // The regions of a type don't affect the size of the type + let self_ty = self + .tcx() + .erase_regions(self.tcx().erase_late_bound_regions(obligation.predicate.self_ty())); + + // But if there are inference variables, we have to wait until it's resolved. + if self_ty.has_non_region_infer() { + candidates.ambiguous = true; + return; + } + + let usize_layout = + self.tcx().layout_of(ty::ParamEnv::empty().and(self.tcx().types.usize)).unwrap().layout; + if let Ok(layout) = self.tcx().layout_of(obligation.param_env.and(self_ty)) + && layout.layout.size() == usize_layout.size() + && layout.layout.align().abi == usize_layout.align().abi + { + candidates.vec.push(BuiltinCandidate { has_nested: false }); + } + } } diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs index ed22058c6..fda415155 100644 --- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs +++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs @@ -19,14 +19,18 @@ use rustc_span::def_id::DefId; use crate::traits::project::{normalize_with_depth, normalize_with_depth_to}; use crate::traits::util::{self, closure_trait_ref_and_return_type, predicate_for_trait_def}; +use crate::traits::vtable::{ + count_own_vtable_entries, prepare_vtable_segments, vtable_trait_first_method_offset, + VtblSegment, +}; use crate::traits::{ BuiltinDerivedObligation, ImplDerivedObligation, ImplDerivedObligationCause, ImplSource, ImplSourceAutoImplData, ImplSourceBuiltinData, ImplSourceClosureData, - ImplSourceConstDestructData, ImplSourceDiscriminantKindData, ImplSourceFnPointerData, - ImplSourceGeneratorData, ImplSourceObjectData, ImplSourcePointeeData, ImplSourceTraitAliasData, + ImplSourceConstDestructData, ImplSourceFnPointerData, ImplSourceFutureData, + ImplSourceGeneratorData, ImplSourceObjectData, ImplSourceTraitAliasData, ImplSourceTraitUpcastingData, ImplSourceUserDefinedData, Normalized, ObjectCastObligation, Obligation, ObligationCause, OutputTypeParameterMismatch, PredicateObligation, Selection, - SelectionError, TraitNotObjectSafe, TraitObligation, Unimplemented, VtblSegment, + SelectionError, TraitNotObjectSafe, TraitObligation, Unimplemented, }; use super::BuiltinImplConditions; @@ -89,17 +93,16 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ImplSource::Generator(vtable_generator) } + FutureCandidate => { + let vtable_future = self.confirm_future_candidate(obligation)?; + ImplSource::Future(vtable_future) + } + FnPointerCandidate { .. } => { let data = self.confirm_fn_pointer_candidate(obligation)?; ImplSource::FnPointer(data) } - DiscriminantKindCandidate => { - ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData) - } - - PointeeCandidate => ImplSource::Pointee(ImplSourcePointeeData), - TraitAliasCandidate => { let data = self.confirm_trait_alias_candidate(obligation); ImplSource::TraitAlias(data) @@ -148,7 +151,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let trait_predicate = self.infcx.shallow_resolve(obligation.predicate); let placeholder_trait_predicate = - self.infcx().replace_bound_vars_with_placeholders(trait_predicate).trait_ref; + self.infcx.replace_bound_vars_with_placeholders(trait_predicate).trait_ref; let placeholder_self_ty = placeholder_trait_predicate.self_ty(); let placeholder_trait_predicate = ty::Binder::dummy(placeholder_trait_predicate); let (def_id, substs) = match *placeholder_self_ty.kind() { @@ -194,6 +197,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { &mut obligations, ); obligations.push(Obligation::with_depth( + self.tcx(), obligation.cause.clone(), obligation.recursion_depth + 1, obligation.param_env, @@ -482,11 +486,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { super_trait, &mut nested, ); - nested.push(Obligation::new( - obligation.cause.clone(), - obligation.param_env, - normalized_super_trait, - )); + nested.push(obligation.with(tcx, normalized_super_trait)); } let assoc_types: Vec<_> = tcx @@ -555,13 +555,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { GenericParamDefKind::Const { .. } => { let bound_var = ty::BoundVariableKind::Const; bound_vars.push(bound_var); - tcx.mk_const(ty::ConstS { - ty: tcx.type_of(param.def_id), - kind: ty::ConstKind::Bound( + tcx.mk_const( + ty::ConstKind::Bound( ty::INNERMOST, ty::BoundVar::from_usize(bound_vars.len() - 1), ), - }) + tcx.type_of(param.def_id), + ) .into() } }); @@ -581,17 +581,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { subst_bound, &mut nested, ); - nested.push(Obligation::new( - obligation.cause.clone(), - obligation.param_env, - normalized_bound, - )); + nested.push(obligation.with(tcx, normalized_bound)); } } debug!(?nested, "object nested obligations"); - let vtable_base = super::super::vtable_trait_first_method_offset( + let vtable_base = vtable_trait_first_method_offset( tcx, (unnormalized_upcast_trait_ref, ty::Binder::dummy(object_trait_ref)), ); @@ -606,8 +602,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { { debug!(?obligation, "confirm_fn_pointer_candidate"); - // Okay to skip binder; it is reintroduced below. - let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder()); + 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 trait_ref = closure_trait_ref_and_return_type( self.tcx(), @@ -622,15 +620,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // Confirm the `type Output: Sized;` bound that is present on `FnOnce` let cause = obligation.derived_cause(BuiltinDerivedObligation); - // The binder on the Fn obligation is "less" important than the one on - // the signature, as evidenced by how we treat it during projection. - // The safe thing to do here is to liberate it, though, which should - // have no worse effect than skipping the binder here. - let liberated_fn_ty = - self.infcx.replace_bound_vars_with_placeholders(obligation.predicate.rebind(self_ty)); - let output_ty = self - .infcx - .replace_bound_vars_with_placeholders(liberated_fn_ty.fn_sig(self.tcx()).output()); + let output_ty = self.infcx.replace_bound_vars_with_placeholders(sig.output()); let output_ty = normalize_with_depth_to( self, obligation.param_env, @@ -639,15 +629,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { output_ty, &mut nested, ); - let tr = ty::Binder::dummy(ty::TraitRef::new( - self.tcx().require_lang_item(LangItem::Sized, None), - self.tcx().mk_substs_trait(output_ty, &[]), - )); - nested.push(Obligation::new( - cause, - obligation.param_env, - tr.to_poly_trait_predicate().to_predicate(self.tcx()), - )); + let tr = + ty::Binder::dummy(self.tcx().at(cause.span).mk_trait_ref(LangItem::Sized, [output_ty])); + nested.push(Obligation::new(self.infcx.tcx, cause, obligation.param_env, tr)); Ok(ImplSourceFnPointerData { fn_ty: self_ty, nested }) } @@ -659,7 +643,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { debug!(?obligation, "confirm_trait_alias_candidate"); let alias_def_id = obligation.predicate.def_id(); - let predicate = self.infcx().replace_bound_vars_with_placeholders(obligation.predicate); + let predicate = self.infcx.replace_bound_vars_with_placeholders(obligation.predicate); let trait_ref = predicate.trait_ref; let trait_def_id = trait_ref.def_id; let substs = trait_ref.substs; @@ -693,7 +677,24 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { debug!(?obligation, ?generator_def_id, ?substs, "confirm_generator_candidate"); - let trait_ref = self.generator_trait_ref_unnormalized(obligation, substs); + let gen_sig = substs.as_generator().poly_sig(); + + // NOTE: The self-type is a generator type and hence is + // in fact unparameterized (or at least does not reference any + // regions bound in the obligation). + let self_ty = obligation + .predicate + .self_ty() + .no_bound_vars() + .expect("unboxed closure type should not capture bound vars from the predicate"); + + let trait_ref = super::util::generator_trait_ref_and_outputs( + self.tcx(), + obligation.predicate.def_id(), + self_ty, + gen_sig, + ) + .map_bound(|(trait_ref, ..)| trait_ref); let nested = self.confirm_poly_trait_refs(obligation, trait_ref)?; debug!(?trait_ref, ?nested, "generator candidate obligations"); @@ -701,6 +702,36 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { Ok(ImplSourceGeneratorData { generator_def_id, substs, nested }) } + fn confirm_future_candidate( + &mut self, + obligation: &TraitObligation<'tcx>, + ) -> Result>, SelectionError<'tcx>> { + // Okay to skip binder because the substs on generator types never + // touch bound regions, they just capture the in-scope + // type/region parameters. + let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder()); + let ty::Generator(generator_def_id, substs, _) = *self_ty.kind() else { + bug!("closure candidate for non-closure {:?}", obligation); + }; + + debug!(?obligation, ?generator_def_id, ?substs, "confirm_future_candidate"); + + let gen_sig = substs.as_generator().poly_sig(); + + let trait_ref = super::util::future_trait_ref_and_outputs( + self.tcx(), + obligation.predicate.def_id(), + obligation.predicate.no_bound_vars().expect("future has no bound vars").self_ty(), + gen_sig, + ) + .map_bound(|(trait_ref, ..)| trait_ref); + + let nested = self.confirm_poly_trait_refs(obligation, trait_ref)?; + debug!(?trait_ref, ?nested, "future candidate obligations"); + + Ok(ImplSourceFutureData { generator_def_id, substs, nested }) + } + #[instrument(skip(self), level = "debug")] fn confirm_closure_candidate( &mut self, @@ -708,7 +739,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ) -> Result>, SelectionError<'tcx>> { let kind = self .tcx() - .fn_trait_kind_from_lang_item(obligation.predicate.def_id()) + .fn_trait_kind_from_def_id(obligation.predicate.def_id()) .unwrap_or_else(|| bug!("closure candidate for non-fn trait {:?}", obligation)); // Okay to skip binder because the substs on closure types never @@ -727,11 +758,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // FIXME: Chalk if !self.tcx().sess.opts.unstable_opts.chalk { - nested.push(Obligation::new( - obligation.cause.clone(), - obligation.param_env, - ty::Binder::dummy(ty::PredicateKind::ClosureKind(closure_def_id, substs, kind)) - .to_predicate(self.tcx()), + nested.push(obligation.with( + self.tcx(), + ty::Binder::dummy(ty::PredicateKind::ClosureKind(closure_def_id, substs, kind)), )); } @@ -813,9 +842,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let upcast_trait_ref; match (source.kind(), target.kind()) { // TraitA+Kx+'a -> TraitB+Ky+'b (trait upcasting coercion). - (&ty::Dynamic(ref data_a, r_a, repr_a), &ty::Dynamic(ref data_b, r_b, repr_b)) - if repr_a == repr_b => - { + ( + &ty::Dynamic(ref data_a, r_a, repr_a @ ty::Dyn), + &ty::Dynamic(ref data_b, r_b, ty::Dyn), + ) => { // See `assemble_candidates_for_unsizing` for more info. // We already checked the compatibility of auto traits within `assemble_candidates_for_unsizing`. let principal_a = data_a.principal().unwrap(); @@ -841,7 +871,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { .map(ty::Binder::dummy), ); let existential_predicates = tcx.mk_poly_existential_predicates(iter); - let source_trait = tcx.mk_dynamic(existential_predicates, r_b, repr_b); + let source_trait = tcx.mk_dynamic(existential_predicates, r_b, repr_a); // Require that the traits involved in this upcast are **equal**; // only the **lifetime bound** is changed. @@ -860,10 +890,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ); let outlives = ty::OutlivesPredicate(r_a, r_b); nested.push(Obligation::with_depth( + tcx, cause, obligation.recursion_depth + 1, obligation.param_env, - obligation.predicate.rebind(outlives).to_predicate(tcx), + obligation.predicate.rebind(outlives), )); } _ => bug!(), @@ -877,7 +908,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { vptr_offset += TyCtxt::COMMON_VTABLE_ENTRIES.len(); } VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => { - vptr_offset += util::count_own_vtable_entries(tcx, trait_ref); + vptr_offset += count_own_vtable_entries(tcx, trait_ref); if trait_ref == upcast_trait_ref { if emit_vptr { return ControlFlow::Break(Some(vptr_offset)); @@ -896,8 +927,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { }; let vtable_vptr_slot = - super::super::prepare_vtable_segments(tcx, source_trait_ref, vtable_segment_callback) - .unwrap(); + prepare_vtable_segments(tcx, source_trait_ref, vtable_segment_callback).unwrap(); Ok(ImplSourceTraitUpcastingData { upcast_trait_ref, vtable_vptr_slot, nested }) } @@ -919,7 +949,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let mut nested = vec![]; match (source.kind(), target.kind()) { // Trait+Kx+'a -> Trait+Ky+'b (auto traits and lifetime subtyping). - (&ty::Dynamic(ref data_a, r_a, ty::Dyn), &ty::Dynamic(ref data_b, r_b, ty::Dyn)) => { + (&ty::Dynamic(ref data_a, r_a, dyn_a), &ty::Dynamic(ref data_b, r_b, dyn_b)) + if dyn_a == dyn_b => + { // See `assemble_candidates_for_unsizing` for more info. // We already checked the compatibility of auto traits within `assemble_candidates_for_unsizing`. let iter = data_a @@ -938,7 +970,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { .map(ty::Binder::dummy), ); let existential_predicates = tcx.mk_poly_existential_predicates(iter); - let source_trait = tcx.mk_dynamic(existential_predicates, r_b, ty::Dyn); + let source_trait = tcx.mk_dynamic(existential_predicates, r_b, dyn_a); // Require that the traits involved in this upcast are **equal**; // only the **lifetime bound** is changed. @@ -957,10 +989,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ); let outlives = ty::OutlivesPredicate(r_a, r_b); nested.push(Obligation::with_depth( + tcx, cause, obligation.recursion_depth + 1, obligation.param_env, - obligation.predicate.rebind(outlives).to_predicate(tcx), + obligation.predicate.rebind(outlives), )); } @@ -979,6 +1012,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let predicate_to_obligation = |predicate| { Obligation::with_depth( + tcx, cause.clone(), obligation.recursion_depth + 1, obligation.param_env, @@ -999,10 +1033,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ); // We can only make objects from sized types. - let tr = ty::Binder::dummy(ty::TraitRef::new( - tcx.require_lang_item(LangItem::Sized, None), - tcx.mk_substs_trait(source, &[]), - )); + let tr = + ty::Binder::dummy(tcx.at(cause.span).mk_trait_ref(LangItem::Sized, [source])); nested.push(predicate_to_obligation(tr.without_const().to_predicate(tcx))); // If the type is `Foo + 'a`, ensure that the type @@ -1108,8 +1140,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation.cause.clone(), obligation.predicate.def_id(), obligation.recursion_depth + 1, - source_tail, - &[target_tail.into()], + [source_tail, target_tail], )); } @@ -1139,13 +1170,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation.cause.clone(), obligation.predicate.def_id(), obligation.recursion_depth + 1, - a_last, - &[b_last.into()], + [a_last, b_last], ) })); } - _ => bug!(), + _ => bug!("source: {source}, target: {target}"), }; Ok(ImplSourceBuiltinData { nested }) @@ -1255,20 +1285,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation.param_env, cause.clone(), obligation.recursion_depth + 1, - self_ty - .rebind(ty::TraitPredicate { - trait_ref: ty::TraitRef { - def_id: self.tcx().require_lang_item(LangItem::Destruct, None), - substs: self.tcx().mk_substs_trait(nested_ty, &[]), - }, - constness: ty::BoundConstness::ConstIfConst, - polarity: ty::ImplPolarity::Positive, - }) - .to_predicate(tcx), + self_ty.rebind(ty::TraitPredicate { + trait_ref: self + .tcx() + .at(cause.span) + .mk_trait_ref(LangItem::Destruct, [nested_ty]), + constness: ty::BoundConstness::ConstIfConst, + polarity: ty::ImplPolarity::Positive, + }), &mut nested, ); nested.push(Obligation::with_depth( + tcx, cause.clone(), obligation.recursion_depth + 1, obligation.param_env, @@ -1280,18 +1309,17 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // since it's either not `const Drop` (and we raise an error during selection), // or it's an ADT (and we need to check for a custom impl during selection) _ => { - let predicate = self_ty - .rebind(ty::TraitPredicate { - trait_ref: ty::TraitRef { - def_id: self.tcx().require_lang_item(LangItem::Destruct, None), - substs: self.tcx().mk_substs_trait(nested_ty, &[]), - }, - constness: ty::BoundConstness::ConstIfConst, - polarity: ty::ImplPolarity::Positive, - }) - .to_predicate(tcx); + let predicate = self_ty.rebind(ty::TraitPredicate { + trait_ref: self + .tcx() + .at(cause.span) + .mk_trait_ref(LangItem::Destruct, [nested_ty]), + constness: ty::BoundConstness::ConstIfConst, + polarity: ty::ImplPolarity::Positive, + }); nested.push(Obligation::with_depth( + tcx, cause.clone(), obligation.recursion_depth + 1, obligation.param_env, diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs index 9ebff4892..035deb616 100644 --- a/compiler/rustc_trait_selection/src/traits/select/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs @@ -2,6 +2,12 @@ //! //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection +// FIXME: The `map` field in ProvisionalEvaluationCache should be changed to +// a `FxIndexMap` to avoid query instability, but right now it causes a perf regression. This would be +// fixed or at least lightened by the addition of the `drain_filter` method to `FxIndexMap` +// Relevant: https://github.com/rust-lang/rust/pull/103723 and https://github.com/bluss/indexmap/issues/242 +#![allow(rustc::potential_query_instability)] + use self::EvaluationResult::*; use self::SelectionCandidate::*; @@ -24,9 +30,11 @@ use crate::traits::error_reporting::TypeErrCtxtExt; use crate::traits::project::ProjectAndUnifyResult; use crate::traits::project::ProjectionCacheKeyExt; use crate::traits::ProjectionCacheKey; -use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexSet}; +use crate::traits::Unimplemented; +use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::fx::{FxHashSet, FxIndexSet}; use rustc_data_structures::stack::ensure_sufficient_stack; -use rustc_errors::{Diagnostic, ErrorGuaranteed}; +use rustc_errors::Diagnostic; use rustc_hir as hir; use rustc_hir::def_id::DefId; use rustc_infer::infer::LateBoundRegionConversionTime; @@ -47,6 +55,7 @@ use std::fmt::{self, Display}; use std::iter; pub use rustc_middle::traits::select::*; +use rustc_middle::ty::print::with_no_trimmed_paths; mod candidate_assembly; mod confirmation; @@ -93,7 +102,7 @@ impl IntercrateAmbiguityCause { } pub struct SelectionContext<'cx, 'tcx> { - infcx: &'cx InferCtxt<'tcx>, + pub infcx: &'cx InferCtxt<'tcx>, /// Freshener used specifically for entries on the obligation /// stack. This ensures that all entries on the stack at one time @@ -102,25 +111,6 @@ pub struct SelectionContext<'cx, 'tcx> { /// require themselves. freshener: TypeFreshener<'cx, 'tcx>, - /// During coherence we have to assume that other crates may add - /// additional impls which we currently don't know about. - /// - /// To deal with this evaluation should be conservative - /// and consider the possibility of impls from outside this crate. - /// This comes up primarily when resolving ambiguity. Imagine - /// there is some trait reference `$0: Bar` where `$0` is an - /// inference variable. If `intercrate` is true, then we can never - /// say for sure that this reference is not implemented, even if - /// there are *no impls at all for `Bar`*, because `$0` could be - /// bound to some type that in a downstream crate that implements - /// `Bar`. - /// - /// Outside of coherence we set this to false because we are only - /// interested in types that the user could actually have written. - /// In other words, we consider `$0: Bar` to be unimplemented if - /// there is no type that the user could *actually name* that - /// would satisfy it. This avoids crippling inference, basically. - intercrate: bool, /// If `intercrate` is set, we remember predicates which were /// considered ambiguous because of impls potentially added in other crates. /// This is used in coherence to give improved diagnostics. @@ -218,16 +208,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { SelectionContext { infcx, freshener: infcx.freshener_keep_static(), - intercrate: false, intercrate_ambiguity_causes: None, query_mode: TraitQueryMode::Standard, } } - pub fn intercrate(infcx: &'cx InferCtxt<'tcx>) -> SelectionContext<'cx, 'tcx> { - SelectionContext { intercrate: true, ..SelectionContext::new(infcx) } - } - pub fn with_query_mode( infcx: &'cx InferCtxt<'tcx>, query_mode: TraitQueryMode, @@ -239,7 +224,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { /// Enables tracking of intercrate ambiguity causes. See /// the documentation of [`Self::intercrate_ambiguity_causes`] for more. pub fn enable_tracking_intercrate_ambiguity_causes(&mut self) { - assert!(self.intercrate); + assert!(self.is_intercrate()); assert!(self.intercrate_ambiguity_causes.is_none()); self.intercrate_ambiguity_causes = Some(FxIndexSet::default()); debug!("selcx: enable_tracking_intercrate_ambiguity_causes"); @@ -249,20 +234,16 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { /// was enabled and disables tracking at the same time. If /// tracking is not enabled, just returns an empty vector. pub fn take_intercrate_ambiguity_causes(&mut self) -> FxIndexSet { - assert!(self.intercrate); + assert!(self.is_intercrate()); self.intercrate_ambiguity_causes.take().unwrap_or_default() } - pub fn infcx(&self) -> &'cx InferCtxt<'tcx> { - self.infcx - } - pub fn tcx(&self) -> TyCtxt<'tcx> { self.infcx.tcx } pub fn is_intercrate(&self) -> bool { - self.intercrate + self.infcx.intercrate } /////////////////////////////////////////////////////////////////////////// @@ -294,9 +275,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { assert!(self.query_mode == TraitQueryMode::Canonical); return Err(SelectionError::Overflow(OverflowError::Canonical)); } - Err(SelectionError::Ambiguous(_)) => { - return Ok(None); - } Err(e) => { return Err(e); } @@ -328,6 +306,213 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.candidate_from_obligation(&stack) } + #[instrument(level = "debug", skip(self), ret)] + fn candidate_from_obligation<'o>( + &mut self, + stack: &TraitObligationStack<'o, 'tcx>, + ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { + // Watch out for overflow. This intentionally bypasses (and does + // not update) the cache. + self.check_recursion_limit(&stack.obligation, &stack.obligation)?; + + // Check the cache. Note that we freshen the trait-ref + // separately rather than using `stack.fresh_trait_ref` -- + // this is because we want the unbound variables to be + // replaced with fresh types starting from index 0. + let cache_fresh_trait_pred = self.infcx.freshen(stack.obligation.predicate); + debug!(?cache_fresh_trait_pred); + debug_assert!(!stack.obligation.predicate.has_escaping_bound_vars()); + + if let Some(c) = + self.check_candidate_cache(stack.obligation.param_env, cache_fresh_trait_pred) + { + debug!("CACHE HIT"); + return c; + } + + // If no match, compute result and insert into cache. + // + // FIXME(nikomatsakis) -- this cache is not taking into + // account cycles that may have occurred in forming the + // candidate. I don't know of any specific problems that + // result but it seems awfully suspicious. + let (candidate, dep_node) = + self.in_task(|this| this.candidate_from_obligation_no_cache(stack)); + + debug!("CACHE MISS"); + self.insert_candidate_cache( + stack.obligation.param_env, + cache_fresh_trait_pred, + dep_node, + candidate.clone(), + ); + candidate + } + + fn candidate_from_obligation_no_cache<'o>( + &mut self, + stack: &TraitObligationStack<'o, 'tcx>, + ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { + if let Err(conflict) = self.is_knowable(stack) { + debug!("coherence stage: not knowable"); + if self.intercrate_ambiguity_causes.is_some() { + debug!("evaluate_stack: intercrate_ambiguity_causes is some"); + // Heuristics: show the diagnostics when there are no candidates in crate. + if let Ok(candidate_set) = self.assemble_candidates(stack) { + let mut no_candidates_apply = true; + + for c in candidate_set.vec.iter() { + if self.evaluate_candidate(stack, &c)?.may_apply() { + no_candidates_apply = false; + break; + } + } + + if !candidate_set.ambiguous && no_candidates_apply { + let trait_ref = stack.obligation.predicate.skip_binder().trait_ref; + if !trait_ref.references_error() { + let self_ty = trait_ref.self_ty(); + let (trait_desc, self_desc) = with_no_trimmed_paths!({ + let trait_desc = trait_ref.print_only_trait_path().to_string(); + let self_desc = if self_ty.has_concrete_skeleton() { + Some(self_ty.to_string()) + } else { + None + }; + (trait_desc, self_desc) + }); + let cause = if let Conflict::Upstream = conflict { + IntercrateAmbiguityCause::UpstreamCrateUpdate { + trait_desc, + self_desc, + } + } else { + IntercrateAmbiguityCause::DownstreamCrate { trait_desc, self_desc } + }; + debug!(?cause, "evaluate_stack: pushing cause"); + self.intercrate_ambiguity_causes.as_mut().unwrap().insert(cause); + } + } + } + } + return Ok(None); + } + + let candidate_set = self.assemble_candidates(stack)?; + + if candidate_set.ambiguous { + debug!("candidate set contains ambig"); + return Ok(None); + } + + let candidates = candidate_set.vec; + + debug!(?stack, ?candidates, "assembled {} candidates", candidates.len()); + + // At this point, we know that each of the entries in the + // candidate set is *individually* applicable. Now we have to + // figure out if they contain mutual incompatibilities. This + // frequently arises if we have an unconstrained input type -- + // for example, we are looking for `$0: Eq` where `$0` is some + // unconstrained type variable. In that case, we'll get a + // candidate which assumes $0 == int, one that assumes `$0 == + // usize`, etc. This spells an ambiguity. + + let mut candidates = self.filter_impls(candidates, stack.obligation); + + // If there is more than one candidate, first winnow them down + // by considering extra conditions (nested obligations and so + // forth). We don't winnow if there is exactly one + // candidate. This is a relatively minor distinction but it + // can lead to better inference and error-reporting. An + // example would be if there was an impl: + // + // impl Vec { fn push_clone(...) { ... } } + // + // and we were to see some code `foo.push_clone()` where `boo` + // is a `Vec` and `Bar` does not implement `Clone`. If + // we were to winnow, we'd wind up with zero candidates. + // Instead, we select the right impl now but report "`Bar` does + // not implement `Clone`". + if candidates.len() == 1 { + return self.filter_reservation_impls(candidates.pop().unwrap(), stack.obligation); + } + + // Winnow, but record the exact outcome of evaluation, which + // is needed for specialization. Propagate overflow if it occurs. + let mut candidates = candidates + .into_iter() + .map(|c| match self.evaluate_candidate(stack, &c) { + Ok(eval) if eval.may_apply() => { + Ok(Some(EvaluatedCandidate { candidate: c, evaluation: eval })) + } + Ok(_) => Ok(None), + Err(OverflowError::Canonical) => Err(Overflow(OverflowError::Canonical)), + Err(OverflowError::ErrorReporting) => Err(ErrorReporting), + Err(OverflowError::Error(e)) => Err(Overflow(OverflowError::Error(e))), + }) + .flat_map(Result::transpose) + .collect::, _>>()?; + + debug!(?stack, ?candidates, "winnowed to {} candidates", candidates.len()); + + let needs_infer = stack.obligation.predicate.has_non_region_infer(); + + // If there are STILL multiple candidates, we can further + // reduce the list by dropping duplicates -- including + // resolving specializations. + if candidates.len() > 1 { + let mut i = 0; + while i < candidates.len() { + let is_dup = (0..candidates.len()).filter(|&j| i != j).any(|j| { + self.candidate_should_be_dropped_in_favor_of( + &candidates[i], + &candidates[j], + needs_infer, + ) + }); + if is_dup { + debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len()); + candidates.swap_remove(i); + } else { + debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len()); + i += 1; + + // If there are *STILL* multiple candidates, give up + // and report ambiguity. + if i > 1 { + debug!("multiple matches, ambig"); + return Ok(None); + } + } + } + } + + // If there are *NO* candidates, then there are no impls -- + // that we know of, anyway. Note that in the case where there + // are unbound type variables within the obligation, it might + // be the case that you could still satisfy the obligation + // from another crate by instantiating the type variables with + // a type from another crate that does have an impl. This case + // is checked for in `evaluate_stack` (and hence users + // who might care about this case, like coherence, should use + // that function). + if candidates.is_empty() { + // If there's an error type, 'downgrade' our result from + // `Err(Unimplemented)` to `Ok(None)`. This helps us avoid + // emitting additional spurious errors, since we're guaranteed + // to have emitted at least one. + if stack.obligation.predicate.references_error() { + debug!(?stack.obligation.predicate, "found error type in predicate, treating as ambiguous"); + return Ok(None); + } + return Err(Unimplemented); + } + + // Just one candidate left. + self.filter_reservation_impls(candidates.pop().unwrap().candidate, stack.obligation) + } + /////////////////////////////////////////////////////////////////////////// // EVALUATION // @@ -438,10 +623,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ensure_sufficient_stack(|| { let bound_predicate = obligation.predicate.kind(); match bound_predicate.skip_binder() { - ty::PredicateKind::Trait(t) => { + ty::PredicateKind::Clause(ty::Clause::Trait(t)) => { let t = bound_predicate.rebind(t); debug_assert!(!t.has_escaping_bound_vars()); - let obligation = obligation.with(t); + let obligation = obligation.with(self.tcx(), t); self.evaluate_trait_predicate_recursively(previous_stack, obligation) } @@ -565,7 +750,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } } - ty::PredicateKind::TypeOutlives(pred) => { + ty::PredicateKind::Clause(ty::Clause::TypeOutlives(pred)) => { // A global type with no late-bound regions can only // contain the "'static" lifetime (any other lifetime // would either be late-bound or local), so it is guaranteed @@ -577,7 +762,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } } - ty::PredicateKind::RegionOutlives(..) => { + ty::PredicateKind::Clause(ty::Clause::RegionOutlives(..)) => { // We do not consider region relationships when evaluating trait matches. Ok(EvaluatedToOkModuloRegions) } @@ -590,9 +775,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } } - ty::PredicateKind::Projection(data) => { + ty::PredicateKind::Clause(ty::Clause::Projection(data)) => { let data = bound_predicate.rebind(data); - let project_obligation = obligation.with(data); + let project_obligation = obligation.with(self.tcx(), data); match project::poly_project_and_unify_type(self, &project_obligation) { ProjectAndUnifyResult::Holds(mut subobligations) => { 'compute_res: { @@ -676,21 +861,62 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } ty::PredicateKind::ConstEquate(c1, c2) => { + let tcx = self.tcx(); assert!( - self.tcx().features().generic_const_exprs, + tcx.features().generic_const_exprs, "`ConstEquate` without a feature gate: {c1:?} {c2:?}", ); - debug!(?c1, ?c2, "evaluate_predicate_recursively: equating consts"); - // FIXME: we probably should only try to unify abstract constants - // if the constants depend on generic parameters. - // - // Let's just see where this breaks :shrug: - if let (ty::ConstKind::Unevaluated(a), ty::ConstKind::Unevaluated(b)) = - (c1.kind(), c2.kind()) { - if self.infcx.try_unify_abstract_consts(a, b, obligation.param_env) { - return Ok(EvaluatedToOk); + let c1 = tcx.expand_abstract_consts(c1); + let c2 = tcx.expand_abstract_consts(c2); + debug!( + "evalaute_predicate_recursively: equating consts:\nc1= {:?}\nc2= {:?}", + c1, c2 + ); + + use rustc_hir::def::DefKind; + use ty::ConstKind::Unevaluated; + match (c1.kind(), c2.kind()) { + (Unevaluated(a), Unevaluated(b)) + if a.def.did == b.def.did + && tcx.def_kind(a.def.did) == DefKind::AssocConst => + { + if let Ok(new_obligations) = self + .infcx + .at(&obligation.cause, obligation.param_env) + .trace(c1, c2) + .eq(a.substs, b.substs) + { + let mut obligations = new_obligations.obligations; + self.add_depth( + obligations.iter_mut(), + obligation.recursion_depth, + ); + return self.evaluate_predicates_recursively( + previous_stack, + obligations.into_iter(), + ); + } + } + (_, Unevaluated(_)) | (Unevaluated(_), _) => (), + (_, _) => { + if let Ok(new_obligations) = self + .infcx + .at(&obligation.cause, obligation.param_env) + .eq(c1, c2) + { + let mut obligations = new_obligations.obligations; + self.add_depth( + obligations.iter_mut(), + obligation.recursion_depth, + ); + return self.evaluate_predicates_recursively( + previous_stack, + obligations.into_iter(), + ); + } + } } } @@ -712,23 +938,17 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { match (evaluate(c1), evaluate(c2)) { (Ok(c1), Ok(c2)) => { - match self - .infcx() - .at(&obligation.cause, obligation.param_env) - .eq(c1, c2) + match self.infcx.at(&obligation.cause, obligation.param_env).eq(c1, c2) { - Ok(_) => Ok(EvaluatedToOk), + Ok(inf_ok) => self.evaluate_predicates_recursively( + previous_stack, + inf_ok.into_obligations(), + ), Err(_) => Ok(EvaluatedToErr), } } (Err(ErrorHandled::Reported(_)), _) | (_, Err(ErrorHandled::Reported(_))) => Ok(EvaluatedToErr), - (Err(ErrorHandled::Linted), _) | (_, Err(ErrorHandled::Linted)) => { - span_bug!( - obligation.cause.span(), - "ConstEquate: const_eval_resolve returned an unexpected error" - ) - } (Err(ErrorHandled::TooGeneric), _) | (_, Err(ErrorHandled::TooGeneric)) => { if c1.has_non_region_infer() || c2.has_non_region_infer() { Ok(EvaluatedToAmbig) @@ -742,6 +962,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ty::PredicateKind::TypeWellFormedFromEnv(..) => { bug!("TypeWellFormedFromEnv is only used for chalk") } + ty::PredicateKind::Ambiguous => Ok(EvaluatedToAmbig), } }) } @@ -752,7 +973,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { previous_stack: TraitObligationStackList<'o, 'tcx>, mut obligation: TraitObligation<'tcx>, ) -> Result { - if !self.intercrate + if !self.is_intercrate() && obligation.is_global() && obligation.param_env.caller_bounds().iter().all(|bound| bound.needs_subst()) { @@ -931,7 +1152,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { match self.candidate_from_obligation(stack) { Ok(Some(c)) => self.evaluate_candidate(stack, &c), - Err(SelectionError::Ambiguous(_)) => Ok(EvaluatedToAmbig), Ok(None) => Ok(EvaluatedToAmbig), Err(Overflow(OverflowError::Canonical)) => Err(OverflowError::Canonical), Err(ErrorReporting) => Err(OverflowError::ErrorReporting), @@ -956,7 +1176,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { fn coinductive_predicate(&self, predicate: ty::Predicate<'tcx>) -> bool { let result = match predicate.kind().skip_binder() { - ty::PredicateKind::Trait(ref data) => self.tcx().trait_is_auto(data.def_id()), + ty::PredicateKind::Clause(ty::Clause::Trait(ref data)) => { + self.tcx().trait_is_coinductive(data.def_id()) + } ty::PredicateKind::WellFormed(_) => true, _ => false, }; @@ -1016,7 +1238,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // mode, so don't do any caching. In particular, we might // re-use the same `InferCtxt` with both an intercrate // and non-intercrate `SelectionContext` - if self.intercrate { + if self.is_intercrate() { return None; } @@ -1046,7 +1268,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // mode, so don't do any caching. In particular, we might // re-use the same `InferCtxt` with both an intercrate // and non-intercrate `SelectionContext` - if self.intercrate { + if self.is_intercrate() { return; } @@ -1084,20 +1306,21 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { it.for_each(|o| o.recursion_depth = cmp::max(min_depth, o.recursion_depth) + 1); } - fn check_recursion_depth>( + fn check_recursion_depth( &self, depth: usize, error_obligation: &Obligation<'tcx, T>, - ) -> Result<(), OverflowError> { + ) -> Result<(), OverflowError> + where + T: ToPredicate<'tcx> + Clone, + { if !self.infcx.tcx.recursion_limit().value_within_limit(depth) { match self.query_mode { TraitQueryMode::Standard => { - if self.infcx.is_tainted_by_errors() { - return Err(OverflowError::Error( - ErrorGuaranteed::unchecked_claim_error_was_emitted(), - )); + if let Some(e) = self.infcx.tainted_by_errors() { + return Err(OverflowError::Error(e)); } - self.infcx.err_ctxt().report_overflow_error(error_obligation, true); + self.infcx.err_ctxt().report_overflow_obligation(error_obligation, true); } TraitQueryMode::Canonical => { return Err(OverflowError::Canonical); @@ -1112,11 +1335,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { /// The weird return type of this function allows it to be used with the `try` (`?`) /// operator within certain functions. #[inline(always)] - fn check_recursion_limit, V: Display + TypeFoldable<'tcx>>( + fn check_recursion_limit, V>( &self, obligation: &Obligation<'tcx, T>, error_obligation: &Obligation<'tcx, V>, - ) -> Result<(), OverflowError> { + ) -> Result<(), OverflowError> + where + V: ToPredicate<'tcx> + Clone, + { self.check_recursion_depth(obligation.recursion_depth, error_obligation) } @@ -1132,12 +1358,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { /// filter_impls filters constant trait obligations and candidates that have a positive impl /// for a negative goal and a negative impl for a positive goal - #[instrument(level = "debug", skip(self))] + #[instrument(level = "debug", skip(self, candidates))] fn filter_impls( &mut self, candidates: Vec>, obligation: &TraitObligation<'tcx>, ) -> Vec> { + trace!("{candidates:#?}"); let tcx = self.tcx(); let mut result = Vec::with_capacity(candidates.len()); @@ -1153,9 +1380,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ProjectionCandidate(_, ty::BoundConstness::ConstIfConst) => {} // auto trait impl AutoImplCandidate => {} - // generator, this will raise error in other places + // generator / future, this will raise error in other places // or ignore error with const_async_blocks feature GeneratorCandidate => {} + FutureCandidate => {} // FnDef where the function is const FnPointerCandidate { is_const: true } => {} ConstDestructCandidate(_) => {} @@ -1177,6 +1405,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } } + trace!("{result:#?}"); result } @@ -1215,14 +1444,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } fn is_knowable<'o>(&mut self, stack: &TraitObligationStack<'o, 'tcx>) -> Result<(), Conflict> { - debug!("is_knowable(intercrate={:?})", self.intercrate); + debug!("is_knowable(intercrate={:?})", self.is_intercrate()); - if !self.intercrate || stack.obligation.polarity() == ty::ImplPolarity::Negative { + if !self.is_intercrate() || stack.obligation.polarity() == ty::ImplPolarity::Negative { return Ok(()); } let obligation = &stack.obligation; - let predicate = self.infcx().resolve_vars_if_possible(obligation.predicate); + let predicate = self.infcx.resolve_vars_if_possible(obligation.predicate); // Okay to skip binder because of the nature of the // trait-ref-is-knowable check, which does not care about @@ -1248,7 +1477,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // the master cache. Since coherence executes pretty quickly, // it's not worth going to more trouble to increase the // hit-rate, I don't think. - if self.intercrate { + if self.is_intercrate() { return false; } @@ -1265,7 +1494,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // mode, so don't do any caching. In particular, we might // re-use the same `InferCtxt` with both an intercrate // and non-intercrate `SelectionContext` - if self.intercrate { + if self.is_intercrate() { return None; } let tcx = self.tcx(); @@ -1304,7 +1533,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // mode, so don't do any caching. In particular, we might // re-use the same `InferCtxt` with both an intercrate // and non-intercrate `SelectionContext` - if self.intercrate { + if self.is_intercrate() { return false; } match result { @@ -1359,9 +1588,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { &mut self, obligation: &TraitObligation<'tcx>, ) -> smallvec::SmallVec<[(usize, ty::BoundConstness); 2]> { - let poly_trait_predicate = self.infcx().resolve_vars_if_possible(obligation.predicate); + let poly_trait_predicate = self.infcx.resolve_vars_if_possible(obligation.predicate); let placeholder_trait_predicate = - self.infcx().replace_bound_vars_with_placeholders(poly_trait_predicate); + self.infcx.replace_bound_vars_with_placeholders(poly_trait_predicate); debug!(?placeholder_trait_predicate); let tcx = self.infcx.tcx; @@ -1389,7 +1618,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { .enumerate() .filter_map(|(idx, bound)| { let bound_predicate = bound.kind(); - if let ty::PredicateKind::Trait(pred) = bound_predicate.skip_binder() { + if let ty::PredicateKind::Clause(ty::Clause::Trait(pred)) = + bound_predicate.skip_binder() + { let bound = bound_predicate.rebind(pred.trait_ref); if self.infcx.probe(|_| { match self.match_normalize_trait_ref( @@ -1581,20 +1812,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { (TransmutabilityCandidate, _) | (_, TransmutabilityCandidate) => false, // (*) - ( - BuiltinCandidate { has_nested: false } - | DiscriminantKindCandidate - | PointeeCandidate - | ConstDestructCandidate(_), - _, - ) => true, - ( - _, - BuiltinCandidate { has_nested: false } - | DiscriminantKindCandidate - | PointeeCandidate - | ConstDestructCandidate(_), - ) => false, + (BuiltinCandidate { has_nested: false } | ConstDestructCandidate(_), _) => true, + (_, BuiltinCandidate { has_nested: false } | ConstDestructCandidate(_)) => false, (ParamCandidate(other), ParamCandidate(victim)) => { let same_except_bound_vars = other.skip_binder().trait_ref @@ -1633,6 +1852,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ImplCandidate(..) | ClosureCandidate | GeneratorCandidate + | FutureCandidate | FnPointerCandidate { .. } | BuiltinObjectCandidate | BuiltinUnsizeCandidate @@ -1651,6 +1871,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ImplCandidate(_) | ClosureCandidate | GeneratorCandidate + | FutureCandidate | FnPointerCandidate { .. } | BuiltinObjectCandidate | BuiltinUnsizeCandidate @@ -1681,6 +1902,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ImplCandidate(..) | ClosureCandidate | GeneratorCandidate + | FutureCandidate | FnPointerCandidate { .. } | BuiltinObjectCandidate | BuiltinUnsizeCandidate @@ -1693,6 +1915,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ImplCandidate(..) | ClosureCandidate | GeneratorCandidate + | FutureCandidate | FnPointerCandidate { .. } | BuiltinObjectCandidate | BuiltinUnsizeCandidate @@ -1774,6 +1997,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ImplCandidate(_) | ClosureCandidate | GeneratorCandidate + | FutureCandidate | FnPointerCandidate { .. } | BuiltinObjectCandidate | BuiltinUnsizeCandidate @@ -1783,6 +2007,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ImplCandidate(_) | ClosureCandidate | GeneratorCandidate + | FutureCandidate | FnPointerCandidate { .. } | BuiltinObjectCandidate | BuiltinUnsizeCandidate @@ -1973,6 +2198,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { /// Bar where struct Bar { x: T, y: u32 } -> [i32, u32] /// Zed where enum Zed { A(T), B(u32) } -> [i32, u32] /// ``` + #[instrument(level = "debug", skip(self), ret)] fn constituent_types_for_ty( &self, t: ty::Binder<'tcx, Ty<'tcx>>, @@ -2089,8 +2315,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { cause.clone(), trait_def_id, recursion_depth, - normalized_ty, - &[], + [normalized_ty], ); obligations.push(placeholder_obligation); obligations @@ -2117,6 +2342,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { match self.match_impl(impl_def_id, impl_trait_ref, obligation) { Ok(substs) => substs, Err(()) => { + // FIXME: A rematch may fail when a candidate cache hit occurs + // on thefreshened form of the trait predicate, but the match + // fails for some reason that is not captured in the freshened + // cache key. For example, equating an impl trait ref against + // the placeholder trait ref may fail due the Generalizer relation + // raising a CyclicalTy error due to a sub_root_var relation + // for a variable being generalized... self.infcx.tcx.sess.delay_span_bug( obligation.cause.span, &format!( @@ -2145,7 +2377,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation: &TraitObligation<'tcx>, ) -> Result>, ()> { let placeholder_obligation = - self.infcx().replace_bound_vars_with_placeholders(obligation.predicate); + self.infcx.replace_bound_vars_with_placeholders(obligation.predicate); let placeholder_obligation_trait_ref = placeholder_obligation.trait_ref; let impl_substs = self.infcx.fresh_substs_for_item(obligation.cause.span, impl_def_id); @@ -2181,7 +2413,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { .map_err(|e| debug!("match_impl: failed eq_trait_refs due to `{e}`"))?; nested_obligations.extend(obligations); - if !self.intercrate + if !self.is_intercrate() && self.tcx().impl_polarity(impl_def_id) == ty::ImplPolarity::Reservation { debug!("reservation impls only apply in intercrate mode"); @@ -2277,43 +2509,25 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { debug!(?closure_sig); - // (1) Feels icky to skip the binder here, but OTOH we know - // that the self-type is an unboxed closure type and hence is + // NOTE: The self-type is an unboxed closure type and hence is // in fact unparameterized (or at least does not reference any - // regions bound in the obligation). Still probably some - // refactoring could make this nicer. + // regions bound in the obligation). + let self_ty = obligation + .predicate + .self_ty() + .no_bound_vars() + .expect("unboxed closure type should not capture bound vars from the predicate"); + closure_trait_ref_and_return_type( self.tcx(), obligation.predicate.def_id(), - obligation.predicate.skip_binder().self_ty(), // (1) + self_ty, closure_sig, util::TupleArgumentsFlag::No, ) .map_bound(|(trait_ref, _)| trait_ref) } - fn generator_trait_ref_unnormalized( - &mut self, - obligation: &TraitObligation<'tcx>, - substs: SubstsRef<'tcx>, - ) -> ty::PolyTraitRef<'tcx> { - let gen_sig = substs.as_generator().poly_sig(); - - // (1) Feels icky to skip the binder here, but OTOH we know - // that the self-type is an generator type and hence is - // in fact unparameterized (or at least does not reference any - // regions bound in the obligation). Still probably some - // refactoring could make this nicer. - - super::util::generator_trait_ref_and_outputs( - self.tcx(), - obligation.predicate.def_id(), - obligation.predicate.skip_binder().self_ty(), // (1) - gen_sig, - ) - .map_bound(|(trait_ref, ..)| trait_ref) - } - /// Returns the obligations that are implied by instantiating an /// impl or trait. The obligations are substituted and fully /// normalized. This is used when confirming an impl or default -- cgit v1.2.3