summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
diff options
context:
space:
mode:
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.rs386
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 });
+ }
+ }
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-10 02:19:10 +0000