diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs')
-rw-r--r-- | compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs | 386 |
1 files changed, 98 insertions, 288 deletions
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<T:Clone> Vec<T> { fn push_clone(...) { ... } } - // - // and we were to see some code `foo.push_clone()` where `boo` - // is a `Vec<Bar>` 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::<Result<Vec<_>, _>>()?; - - 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<ty::PolyExistentialTraitRef<'tcx>> { let tcx = self.tcx(); if tcx.features().trait_upcasting { return None; } // <ty as Deref> - 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 }); + } + } } |