1 //! Candidate assembly.
3 //! The selection process begins by examining all in-scope impls,
4 //! caller obligations, and so forth and assembling a list of
5 //! candidates. See the [rustc dev guide] for more details.
7 //! [rustc dev guide]:https://rustc-dev-guide.rust-lang.org/traits/resolution.html#candidate-assembly
10 use rustc_infer::traits::ObligationCause;
11 use rustc_infer::traits::{Obligation, SelectionError, TraitObligation};
12 use rustc_middle::ty::print::with_no_trimmed_paths;
13 use rustc_middle::ty::{self, Ty, TypeVisitable};
14 use rustc_target::spec::abi::Abi;
17 use crate::traits::coherence::Conflict;
18 use crate::traits::query::evaluate_obligation::InferCtxtExt;
19 use crate::traits::{util, SelectionResult};
20 use crate::traits::{ErrorReporting, Overflow, Unimplemented};
22 use super::BuiltinImplConditions;
23 use super::IntercrateAmbiguityCause;
24 use super::OverflowError;
25 use super::SelectionCandidate::{self, *};
26 use super::{EvaluatedCandidate, SelectionCandidateSet, SelectionContext, TraitObligationStack};
28 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
29 #[instrument(level = "debug", skip(self), ret)]
30 pub(super) fn candidate_from_obligation<'o>(
32 stack: &TraitObligationStack<'o, 'tcx>,
33 ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
34 // Watch out for overflow. This intentionally bypasses (and does
35 // not update) the cache.
36 self.check_recursion_limit(&stack.obligation, &stack.obligation)?;
38 // Check the cache. Note that we freshen the trait-ref
39 // separately rather than using `stack.fresh_trait_ref` --
40 // this is because we want the unbound variables to be
41 // replaced with fresh types starting from index 0.
42 let cache_fresh_trait_pred = self.infcx.freshen(stack.obligation.predicate);
43 debug!(?cache_fresh_trait_pred);
44 debug_assert!(!stack.obligation.predicate.has_escaping_bound_vars());
47 self.check_candidate_cache(stack.obligation.param_env, cache_fresh_trait_pred)
53 // If no match, compute result and insert into cache.
55 // FIXME(nikomatsakis) -- this cache is not taking into
56 // account cycles that may have occurred in forming the
57 // candidate. I don't know of any specific problems that
58 // result but it seems awfully suspicious.
59 let (candidate, dep_node) =
60 self.in_task(|this| this.candidate_from_obligation_no_cache(stack));
63 self.insert_candidate_cache(
64 stack.obligation.param_env,
65 cache_fresh_trait_pred,
72 fn candidate_from_obligation_no_cache<'o>(
74 stack: &TraitObligationStack<'o, 'tcx>,
75 ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
76 if let Err(conflict) = self.is_knowable(stack) {
77 debug!("coherence stage: not knowable");
78 if self.intercrate_ambiguity_causes.is_some() {
79 debug!("evaluate_stack: intercrate_ambiguity_causes is some");
80 // Heuristics: show the diagnostics when there are no candidates in crate.
81 if let Ok(candidate_set) = self.assemble_candidates(stack) {
82 let mut no_candidates_apply = true;
84 for c in candidate_set.vec.iter() {
85 if self.evaluate_candidate(stack, &c)?.may_apply() {
86 no_candidates_apply = false;
91 if !candidate_set.ambiguous && no_candidates_apply {
92 let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
93 let self_ty = trait_ref.self_ty();
94 let (trait_desc, self_desc) = with_no_trimmed_paths!({
95 let trait_desc = trait_ref.print_only_trait_path().to_string();
96 let self_desc = if self_ty.has_concrete_skeleton() {
97 Some(self_ty.to_string())
101 (trait_desc, self_desc)
103 let cause = if let Conflict::Upstream = conflict {
104 IntercrateAmbiguityCause::UpstreamCrateUpdate { trait_desc, self_desc }
106 IntercrateAmbiguityCause::DownstreamCrate { trait_desc, self_desc }
108 debug!(?cause, "evaluate_stack: pushing cause");
109 self.intercrate_ambiguity_causes.as_mut().unwrap().insert(cause);
116 let candidate_set = self.assemble_candidates(stack)?;
118 if candidate_set.ambiguous {
119 debug!("candidate set contains ambig");
123 let candidates = candidate_set.vec;
125 debug!(?stack, ?candidates, "assembled {} candidates", candidates.len());
127 // At this point, we know that each of the entries in the
128 // candidate set is *individually* applicable. Now we have to
129 // figure out if they contain mutual incompatibilities. This
130 // frequently arises if we have an unconstrained input type --
131 // for example, we are looking for `$0: Eq` where `$0` is some
132 // unconstrained type variable. In that case, we'll get a
133 // candidate which assumes $0 == int, one that assumes `$0 ==
134 // usize`, etc. This spells an ambiguity.
136 let mut candidates = self.filter_impls(candidates, stack.obligation);
138 // If there is more than one candidate, first winnow them down
139 // by considering extra conditions (nested obligations and so
140 // forth). We don't winnow if there is exactly one
141 // candidate. This is a relatively minor distinction but it
142 // can lead to better inference and error-reporting. An
143 // example would be if there was an impl:
145 // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
147 // and we were to see some code `foo.push_clone()` where `boo`
148 // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
149 // we were to winnow, we'd wind up with zero candidates.
150 // Instead, we select the right impl now but report "`Bar` does
151 // not implement `Clone`".
152 if candidates.len() == 1 {
153 return self.filter_reservation_impls(candidates.pop().unwrap(), stack.obligation);
156 // Winnow, but record the exact outcome of evaluation, which
157 // is needed for specialization. Propagate overflow if it occurs.
158 let mut candidates = candidates
160 .map(|c| match self.evaluate_candidate(stack, &c) {
161 Ok(eval) if eval.may_apply() => {
162 Ok(Some(EvaluatedCandidate { candidate: c, evaluation: eval }))
165 Err(OverflowError::Canonical) => Err(Overflow(OverflowError::Canonical)),
166 Err(OverflowError::ErrorReporting) => Err(ErrorReporting),
167 Err(OverflowError::Error(e)) => Err(Overflow(OverflowError::Error(e))),
169 .flat_map(Result::transpose)
170 .collect::<Result<Vec<_>, _>>()?;
172 debug!(?stack, ?candidates, "winnowed to {} candidates", candidates.len());
174 let needs_infer = stack.obligation.predicate.has_non_region_infer();
176 // If there are STILL multiple candidates, we can further
177 // reduce the list by dropping duplicates -- including
178 // resolving specializations.
179 if candidates.len() > 1 {
181 while i < candidates.len() {
182 let is_dup = (0..candidates.len()).filter(|&j| i != j).any(|j| {
183 self.candidate_should_be_dropped_in_favor_of(
190 debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
191 candidates.swap_remove(i);
193 debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
196 // If there are *STILL* multiple candidates, give up
197 // and report ambiguity.
199 debug!("multiple matches, ambig");
206 // If there are *NO* candidates, then there are no impls --
207 // that we know of, anyway. Note that in the case where there
208 // are unbound type variables within the obligation, it might
209 // be the case that you could still satisfy the obligation
210 // from another crate by instantiating the type variables with
211 // a type from another crate that does have an impl. This case
212 // is checked for in `evaluate_stack` (and hence users
213 // who might care about this case, like coherence, should use
215 if candidates.is_empty() {
216 // If there's an error type, 'downgrade' our result from
217 // `Err(Unimplemented)` to `Ok(None)`. This helps us avoid
218 // emitting additional spurious errors, since we're guaranteed
219 // to have emitted at least one.
220 if stack.obligation.predicate.references_error() {
221 debug!(?stack.obligation.predicate, "found error type in predicate, treating as ambiguous");
224 return Err(Unimplemented);
227 // Just one candidate left.
228 self.filter_reservation_impls(candidates.pop().unwrap().candidate, stack.obligation)
231 #[instrument(skip(self, stack), level = "debug")]
232 pub(super) fn assemble_candidates<'o>(
234 stack: &TraitObligationStack<'o, 'tcx>,
235 ) -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> {
236 let TraitObligationStack { obligation, .. } = *stack;
237 let obligation = &Obligation {
238 param_env: obligation.param_env,
239 cause: obligation.cause.clone(),
240 recursion_depth: obligation.recursion_depth,
241 predicate: self.infcx.resolve_vars_if_possible(obligation.predicate),
244 if obligation.predicate.skip_binder().self_ty().is_ty_var() {
245 debug!(ty = ?obligation.predicate.skip_binder().self_ty(), "ambiguous inference var or opaque type");
246 // Self is a type variable (e.g., `_: AsRef<str>`).
248 // This is somewhat problematic, as the current scheme can't really
249 // handle it turning to be a projection. This does end up as truly
250 // ambiguous in most cases anyway.
252 // Take the fast path out - this also improves
253 // performance by preventing assemble_candidates_from_impls from
254 // matching every impl for this trait.
255 return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true });
258 let mut candidates = SelectionCandidateSet { vec: Vec::new(), ambiguous: false };
260 // The only way to prove a NotImplemented(T: Foo) predicate is via a negative impl.
261 // There are no compiler built-in rules for this.
262 if obligation.polarity() == ty::ImplPolarity::Negative {
263 self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
264 self.assemble_candidates_from_impls(obligation, &mut candidates);
266 self.assemble_candidates_for_trait_alias(obligation, &mut candidates);
268 // Other bounds. Consider both in-scope bounds from fn decl
269 // and applicable impls. There is a certain set of precedence rules here.
270 let def_id = obligation.predicate.def_id();
271 let lang_items = self.tcx().lang_items();
273 if lang_items.copy_trait() == Some(def_id) {
274 debug!(obligation_self_ty = ?obligation.predicate.skip_binder().self_ty());
276 // User-defined copy impls are permitted, but only for
277 // structs and enums.
278 self.assemble_candidates_from_impls(obligation, &mut candidates);
280 // For other types, we'll use the builtin rules.
281 let copy_conditions = self.copy_clone_conditions(obligation);
282 self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates);
283 } else if lang_items.discriminant_kind_trait() == Some(def_id) {
284 // `DiscriminantKind` is automatically implemented for every type.
285 candidates.vec.push(BuiltinCandidate { has_nested: false });
286 } else if lang_items.pointee_trait() == Some(def_id) {
287 // `Pointee` is automatically implemented for every type.
288 candidates.vec.push(BuiltinCandidate { has_nested: false });
289 } else if lang_items.sized_trait() == Some(def_id) {
290 // Sized is never implementable by end-users, it is
291 // always automatically computed.
292 let sized_conditions = self.sized_conditions(obligation);
293 self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates);
294 } else if lang_items.unsize_trait() == Some(def_id) {
295 self.assemble_candidates_for_unsizing(obligation, &mut candidates);
296 } else if lang_items.destruct_trait() == Some(def_id) {
297 self.assemble_const_destruct_candidates(obligation, &mut candidates);
298 } else if lang_items.transmute_trait() == Some(def_id) {
299 // User-defined transmutability impls are permitted.
300 self.assemble_candidates_from_impls(obligation, &mut candidates);
301 self.assemble_candidates_for_transmutability(obligation, &mut candidates);
302 } else if lang_items.tuple_trait() == Some(def_id) {
303 self.assemble_candidate_for_tuple(obligation, &mut candidates);
304 } else if lang_items.pointer_sized() == Some(def_id) {
305 self.assemble_candidate_for_ptr_sized(obligation, &mut candidates);
307 if lang_items.clone_trait() == Some(def_id) {
308 // Same builtin conditions as `Copy`, i.e., every type which has builtin support
309 // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
310 // types have builtin support for `Clone`.
311 let clone_conditions = self.copy_clone_conditions(obligation);
312 self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates);
315 if lang_items.gen_trait() == Some(def_id) {
316 self.assemble_generator_candidates(obligation, &mut candidates);
317 } else if lang_items.future_trait() == Some(def_id) {
318 self.assemble_future_candidates(obligation, &mut candidates);
321 self.assemble_closure_candidates(obligation, &mut candidates);
322 self.assemble_fn_pointer_candidates(obligation, &mut candidates);
323 self.assemble_candidates_from_impls(obligation, &mut candidates);
324 self.assemble_candidates_from_object_ty(obligation, &mut candidates);
327 self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
328 self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
329 // Auto implementations have lower priority, so we only
330 // consider triggering a default if there is no other impl that can apply.
331 if candidates.vec.is_empty() {
332 self.assemble_candidates_from_auto_impls(obligation, &mut candidates);
335 debug!("candidate list size: {}", candidates.vec.len());
339 #[instrument(level = "debug", skip(self, candidates))]
340 fn assemble_candidates_from_projected_tys(
342 obligation: &TraitObligation<'tcx>,
343 candidates: &mut SelectionCandidateSet<'tcx>,
345 // Before we go into the whole placeholder thing, just
346 // quickly check if the self-type is a projection at all.
347 match obligation.predicate.skip_binder().trait_ref.self_ty().kind() {
348 ty::Projection(_) | ty::Opaque(..) => {}
349 ty::Infer(ty::TyVar(_)) => {
351 obligation.cause.span,
352 "Self=_ should have been handled by assemble_candidates"
360 .probe(|_| self.match_projection_obligation_against_definition_bounds(obligation));
364 .extend(result.into_iter().map(|(idx, constness)| ProjectionCandidate(idx, constness)));
367 /// Given an obligation like `<SomeTrait for T>`, searches the obligations that the caller
368 /// supplied to find out whether it is listed among them.
370 /// Never affects the inference environment.
371 #[instrument(level = "debug", skip(self, stack, candidates))]
372 fn assemble_candidates_from_caller_bounds<'o>(
374 stack: &TraitObligationStack<'o, 'tcx>,
375 candidates: &mut SelectionCandidateSet<'tcx>,
376 ) -> Result<(), SelectionError<'tcx>> {
377 debug!(?stack.obligation);
379 let all_bounds = stack
384 .filter_map(|o| o.to_opt_poly_trait_pred());
386 // Micro-optimization: filter out predicates relating to different traits.
387 let matching_bounds =
388 all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
390 // Keep only those bounds which may apply, and propagate overflow if it occurs.
391 for bound in matching_bounds {
392 // FIXME(oli-obk): it is suspicious that we are dropping the constness and
394 let wc = self.where_clause_may_apply(stack, bound.map_bound(|t| t.trait_ref))?;
396 candidates.vec.push(ParamCandidate(bound));
403 fn assemble_generator_candidates(
405 obligation: &TraitObligation<'tcx>,
406 candidates: &mut SelectionCandidateSet<'tcx>,
408 // Okay to skip binder because the substs on generator types never
409 // touch bound regions, they just capture the in-scope
410 // type/region parameters.
411 let self_ty = obligation.self_ty().skip_binder();
412 match self_ty.kind() {
413 ty::Generator(..) => {
414 debug!(?self_ty, ?obligation, "assemble_generator_candidates",);
416 candidates.vec.push(GeneratorCandidate);
418 ty::Infer(ty::TyVar(_)) => {
419 debug!("assemble_generator_candidates: ambiguous self-type");
420 candidates.ambiguous = true;
426 fn assemble_future_candidates(
428 obligation: &TraitObligation<'tcx>,
429 candidates: &mut SelectionCandidateSet<'tcx>,
431 let self_ty = obligation.self_ty().skip_binder();
432 if let ty::Generator(did, ..) = self_ty.kind() {
433 if let Some(rustc_hir::GeneratorKind::Async(_generator_kind)) =
434 self.tcx().generator_kind(did)
436 debug!(?self_ty, ?obligation, "assemble_future_candidates",);
438 candidates.vec.push(FutureCandidate);
443 /// Checks for the artificial impl that the compiler will create for an obligation like `X :
444 /// FnMut<..>` where `X` is a closure type.
446 /// Note: the type parameters on a closure candidate are modeled as *output* type
447 /// parameters and hence do not affect whether this trait is a match or not. They will be
448 /// unified during the confirmation step.
449 fn assemble_closure_candidates(
451 obligation: &TraitObligation<'tcx>,
452 candidates: &mut SelectionCandidateSet<'tcx>,
454 let Some(kind) = self.tcx().fn_trait_kind_from_def_id(obligation.predicate.def_id()) else {
458 // Okay to skip binder because the substs on closure types never
459 // touch bound regions, they just capture the in-scope
460 // type/region parameters
461 match *obligation.self_ty().skip_binder().kind() {
462 ty::Closure(_, closure_substs) => {
463 debug!(?kind, ?obligation, "assemble_unboxed_candidates");
464 match self.infcx.closure_kind(closure_substs) {
465 Some(closure_kind) => {
466 debug!(?closure_kind, "assemble_unboxed_candidates");
467 if closure_kind.extends(kind) {
468 candidates.vec.push(ClosureCandidate);
472 debug!("assemble_unboxed_candidates: closure_kind not yet known");
473 candidates.vec.push(ClosureCandidate);
477 ty::Infer(ty::TyVar(_)) => {
478 debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
479 candidates.ambiguous = true;
485 /// Implements one of the `Fn()` family for a fn pointer.
486 fn assemble_fn_pointer_candidates(
488 obligation: &TraitObligation<'tcx>,
489 candidates: &mut SelectionCandidateSet<'tcx>,
491 // We provide impl of all fn traits for fn pointers.
492 if !self.tcx().is_fn_trait(obligation.predicate.def_id()) {
496 // Okay to skip binder because what we are inspecting doesn't involve bound regions.
497 let self_ty = obligation.self_ty().skip_binder();
498 match *self_ty.kind() {
499 ty::Infer(ty::TyVar(_)) => {
500 debug!("assemble_fn_pointer_candidates: ambiguous self-type");
501 candidates.ambiguous = true; // Could wind up being a fn() type.
503 // Provide an impl, but only for suitable `fn` pointers.
506 unsafety: hir::Unsafety::Normal,
510 } = self_ty.fn_sig(self.tcx()).skip_binder()
512 candidates.vec.push(FnPointerCandidate { is_const: false });
515 // Provide an impl for suitable functions, rejecting `#[target_feature]` functions (RFC 2396).
516 ty::FnDef(def_id, _) => {
518 unsafety: hir::Unsafety::Normal,
522 } = self_ty.fn_sig(self.tcx()).skip_binder()
524 if self.tcx().codegen_fn_attrs(def_id).target_features.is_empty() {
527 .push(FnPointerCandidate { is_const: self.tcx().is_const_fn(def_id) });
535 /// Searches for impls that might apply to `obligation`.
536 fn assemble_candidates_from_impls(
538 obligation: &TraitObligation<'tcx>,
539 candidates: &mut SelectionCandidateSet<'tcx>,
541 debug!(?obligation, "assemble_candidates_from_impls");
543 // Essentially any user-written impl will match with an error type,
544 // so creating `ImplCandidates` isn't useful. However, we might
545 // end up finding a candidate elsewhere (e.g. a `BuiltinCandidate` for `Sized)
546 // This helps us avoid overflow: see issue #72839
547 // Since compilation is already guaranteed to fail, this is just
548 // to try to show the 'nicest' possible errors to the user.
549 // We don't check for errors in the `ParamEnv` - in practice,
550 // it seems to cause us to be overly aggressive in deciding
551 // to give up searching for candidates, leading to spurious errors.
552 if obligation.predicate.references_error() {
556 self.tcx().for_each_relevant_impl(
557 obligation.predicate.def_id(),
558 obligation.predicate.skip_binder().trait_ref.self_ty(),
560 // Before we create the substitutions and everything, first
561 // consider a "quick reject". This avoids creating more types
562 // and so forth that we need to.
563 let impl_trait_ref = self.tcx().bound_impl_trait_ref(impl_def_id).unwrap();
564 if self.fast_reject_trait_refs(obligation, &impl_trait_ref.0) {
568 self.infcx.probe(|_| {
569 if let Ok(_substs) = self.match_impl(impl_def_id, impl_trait_ref, obligation) {
570 candidates.vec.push(ImplCandidate(impl_def_id));
577 fn assemble_candidates_from_auto_impls(
579 obligation: &TraitObligation<'tcx>,
580 candidates: &mut SelectionCandidateSet<'tcx>,
582 // Okay to skip binder here because the tests we do below do not involve bound regions.
583 let self_ty = obligation.self_ty().skip_binder();
584 debug!(?self_ty, "assemble_candidates_from_auto_impls");
586 let def_id = obligation.predicate.def_id();
588 if self.tcx().trait_is_auto(def_id) {
589 match self_ty.kind() {
591 // For object types, we don't know what the closed
592 // over types are. This means we conservatively
593 // say nothing; a candidate may be added by
594 // `assemble_candidates_from_object_ty`.
597 // Since the contents of foreign types is unknown,
598 // we don't add any `..` impl. Default traits could
599 // still be provided by a manual implementation for
600 // this trait and type.
602 ty::Param(..) | ty::Projection(..) => {
603 // In these cases, we don't know what the actual
604 // type is. Therefore, we cannot break it down
605 // into its constituent types. So we don't
606 // consider the `..` impl but instead just add no
607 // candidates: this means that typeck will only
608 // succeed if there is another reason to believe
609 // that this obligation holds. That could be a
610 // where-clause or, in the case of an object type,
611 // it could be that the object type lists the
612 // trait (e.g., `Foo+Send : Send`). See
613 // `ui/typeck/typeck-default-trait-impl-send-param.rs`
614 // for an example of a test case that exercises
617 ty::Infer(ty::TyVar(_)) => {
618 // The auto impl might apply; we don't know.
619 candidates.ambiguous = true;
621 ty::Generator(_, _, movability)
622 if self.tcx().lang_items().unpin_trait() == Some(def_id) =>
625 hir::Movability::Static => {
626 // Immovable generators are never `Unpin`, so
627 // suppress the normal auto-impl candidate for it.
629 hir::Movability::Movable => {
630 // Movable generators are always `Unpin`, so add an
631 // unconditional builtin candidate.
632 candidates.vec.push(BuiltinCandidate { has_nested: false });
637 _ => candidates.vec.push(AutoImplCandidate),
642 /// Searches for impls that might apply to `obligation`.
643 fn assemble_candidates_from_object_ty(
645 obligation: &TraitObligation<'tcx>,
646 candidates: &mut SelectionCandidateSet<'tcx>,
649 self_ty = ?obligation.self_ty().skip_binder(),
650 "assemble_candidates_from_object_ty",
653 self.infcx.probe(|_snapshot| {
654 // The code below doesn't care about regions, and the
655 // self-ty here doesn't escape this probe, so just erase
657 let self_ty = self.tcx().erase_late_bound_regions(obligation.self_ty());
658 let poly_trait_ref = match self_ty.kind() {
659 ty::Dynamic(ref data, ..) => {
660 if data.auto_traits().any(|did| did == obligation.predicate.def_id()) {
662 "assemble_candidates_from_object_ty: matched builtin bound, \
665 candidates.vec.push(BuiltinObjectCandidate);
669 if let Some(principal) = data.principal() {
670 if !self.infcx.tcx.features().object_safe_for_dispatch {
671 principal.with_self_ty(self.tcx(), self_ty)
672 } else if self.tcx().is_object_safe(principal.def_id()) {
673 principal.with_self_ty(self.tcx(), self_ty)
678 // Only auto trait bounds exist.
682 ty::Infer(ty::TyVar(_)) => {
683 debug!("assemble_candidates_from_object_ty: ambiguous");
684 candidates.ambiguous = true; // could wind up being an object type
690 debug!(?poly_trait_ref, "assemble_candidates_from_object_ty");
692 let poly_trait_predicate = self.infcx.resolve_vars_if_possible(obligation.predicate);
693 let placeholder_trait_predicate =
694 self.infcx.replace_bound_vars_with_placeholders(poly_trait_predicate);
696 // Count only those upcast versions that match the trait-ref
697 // we are looking for. Specifically, do not only check for the
698 // correct trait, but also the correct type parameters.
699 // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
700 // but `Foo` is declared as `trait Foo: Bar<u32>`.
701 let candidate_supertraits = util::supertraits(self.tcx(), poly_trait_ref)
703 .filter(|&(_, upcast_trait_ref)| {
704 self.infcx.probe(|_| {
705 self.match_normalize_trait_ref(
708 placeholder_trait_predicate.trait_ref,
713 .map(|(idx, _)| ObjectCandidate(idx));
715 candidates.vec.extend(candidate_supertraits);
719 /// Temporary migration for #89190
720 fn need_migrate_deref_output_trait_object(
723 param_env: ty::ParamEnv<'tcx>,
724 cause: &ObligationCause<'tcx>,
725 ) -> Option<ty::PolyExistentialTraitRef<'tcx>> {
726 let tcx = self.tcx();
727 if tcx.features().trait_upcasting {
732 let trait_ref = tcx.mk_trait_ref(tcx.lang_items().deref_trait()?, [ty]);
735 traits::Obligation::new(tcx, cause.clone(), param_env, ty::Binder::dummy(trait_ref));
736 if !self.infcx.predicate_may_hold(&obligation) {
740 self.infcx.probe(|_| {
741 let ty = traits::normalize_projection_type(
745 item_def_id: tcx.lang_items().deref_target()?,
746 substs: trait_ref.substs,
750 // We're *intentionally* throwing these away,
751 // since we don't actually use them.
757 if let ty::Dynamic(data, ..) = ty.kind() { data.principal() } else { None }
761 /// Searches for unsizing that might apply to `obligation`.
762 fn assemble_candidates_for_unsizing(
764 obligation: &TraitObligation<'tcx>,
765 candidates: &mut SelectionCandidateSet<'tcx>,
767 // We currently never consider higher-ranked obligations e.g.
768 // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
769 // because they are a priori invalid, and we could potentially add support
770 // for them later, it's just that there isn't really a strong need for it.
771 // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
772 // impl, and those are generally applied to concrete types.
774 // That said, one might try to write a fn with a where clause like
775 // for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
776 // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
777 // Still, you'd be more likely to write that where clause as
779 // so it seems ok if we (conservatively) fail to accept that `Unsize`
780 // obligation above. Should be possible to extend this in the future.
781 let Some(source) = obligation.self_ty().no_bound_vars() else {
782 // Don't add any candidates if there are bound regions.
785 let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
787 debug!(?source, ?target, "assemble_candidates_for_unsizing");
789 match (source.kind(), target.kind()) {
790 // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
791 (&ty::Dynamic(ref data_a, _, ty::Dyn), &ty::Dynamic(ref data_b, _, ty::Dyn)) => {
792 // Upcast coercions permit several things:
794 // 1. Dropping auto traits, e.g., `Foo + Send` to `Foo`
795 // 2. Tightening the region bound, e.g., `Foo + 'a` to `Foo + 'b` if `'a: 'b`
796 // 3. Tightening trait to its super traits, eg. `Foo` to `Bar` if `Foo: Bar`
798 // Note that neither of the first two of these changes requires any
799 // change at runtime. The third needs to change pointer metadata at runtime.
801 // We always perform upcasting coercions when we can because of reason
802 // #2 (region bounds).
803 let auto_traits_compatible = data_b
805 // All of a's auto traits need to be in b's auto traits.
806 .all(|b| data_a.auto_traits().any(|a| a == b));
807 if auto_traits_compatible {
808 let principal_def_id_a = data_a.principal_def_id();
809 let principal_def_id_b = data_b.principal_def_id();
810 if principal_def_id_a == principal_def_id_b {
812 candidates.vec.push(BuiltinUnsizeCandidate);
813 } else if principal_def_id_a.is_some() && principal_def_id_b.is_some() {
814 // not casual unsizing, now check whether this is trait upcasting coercion.
815 let principal_a = data_a.principal().unwrap();
816 let target_trait_did = principal_def_id_b.unwrap();
817 let source_trait_ref = principal_a.with_self_ty(self.tcx(), source);
818 if let Some(deref_trait_ref) = self.need_migrate_deref_output_trait_object(
820 obligation.param_env,
823 if deref_trait_ref.def_id() == target_trait_did {
828 for (idx, upcast_trait_ref) in
829 util::supertraits(self.tcx(), source_trait_ref).enumerate()
831 if upcast_trait_ref.def_id() == target_trait_did {
832 candidates.vec.push(TraitUpcastingUnsizeCandidate(idx));
840 (_, &ty::Dynamic(_, _, ty::Dyn)) => {
841 candidates.vec.push(BuiltinUnsizeCandidate);
844 // Ambiguous handling is below `T` -> `Trait`, because inference
845 // variables can still implement `Unsize<Trait>` and nested
846 // obligations will have the final say (likely deferred).
847 (&ty::Infer(ty::TyVar(_)), _) | (_, &ty::Infer(ty::TyVar(_))) => {
848 debug!("assemble_candidates_for_unsizing: ambiguous");
849 candidates.ambiguous = true;
853 (&ty::Array(..), &ty::Slice(_)) => {
854 candidates.vec.push(BuiltinUnsizeCandidate);
857 // `Struct<T>` -> `Struct<U>`
858 (&ty::Adt(def_id_a, _), &ty::Adt(def_id_b, _)) if def_id_a.is_struct() => {
859 if def_id_a == def_id_b {
860 candidates.vec.push(BuiltinUnsizeCandidate);
864 // `(.., T)` -> `(.., U)`
865 (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => {
866 if tys_a.len() == tys_b.len() {
867 candidates.vec.push(BuiltinUnsizeCandidate);
875 #[instrument(level = "debug", skip(self, obligation, candidates))]
876 fn assemble_candidates_for_transmutability(
878 obligation: &TraitObligation<'tcx>,
879 candidates: &mut SelectionCandidateSet<'tcx>,
881 if obligation.has_non_region_param() {
885 if obligation.has_non_region_infer() {
886 candidates.ambiguous = true;
890 candidates.vec.push(TransmutabilityCandidate);
893 #[instrument(level = "debug", skip(self, obligation, candidates))]
894 fn assemble_candidates_for_trait_alias(
896 obligation: &TraitObligation<'tcx>,
897 candidates: &mut SelectionCandidateSet<'tcx>,
899 // Okay to skip binder here because the tests we do below do not involve bound regions.
900 let self_ty = obligation.self_ty().skip_binder();
903 let def_id = obligation.predicate.def_id();
905 if self.tcx().is_trait_alias(def_id) {
906 candidates.vec.push(TraitAliasCandidate);
910 /// Assembles the trait which are built-in to the language itself:
911 /// `Copy`, `Clone` and `Sized`.
912 #[instrument(level = "debug", skip(self, candidates))]
913 fn assemble_builtin_bound_candidates(
915 conditions: BuiltinImplConditions<'tcx>,
916 candidates: &mut SelectionCandidateSet<'tcx>,
919 BuiltinImplConditions::Where(nested) => {
922 .push(BuiltinCandidate { has_nested: !nested.skip_binder().is_empty() });
924 BuiltinImplConditions::None => {}
925 BuiltinImplConditions::Ambiguous => {
926 candidates.ambiguous = true;
931 fn assemble_const_destruct_candidates(
933 obligation: &TraitObligation<'tcx>,
934 candidates: &mut SelectionCandidateSet<'tcx>,
936 // If the predicate is `~const Destruct` in a non-const environment, we don't actually need
937 // to check anything. We'll short-circuit checking any obligations in confirmation, too.
938 if !obligation.is_const() {
939 candidates.vec.push(ConstDestructCandidate(None));
943 let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
944 match self_ty.skip_binder().kind() {
951 | ty::Projection(_) => {
952 // We don't know if these are `~const Destruct`, at least
953 // not structurally... so don't push a candidate.
961 | ty::Infer(ty::IntVar(_))
962 | ty::Infer(ty::FloatVar(_))
975 | ty::GeneratorWitness(_) => {
976 // These are built-in, and cannot have a custom `impl const Destruct`.
977 candidates.vec.push(ConstDestructCandidate(None));
981 // Find a custom `impl Drop` impl, if it exists
982 let relevant_impl = self.tcx().find_map_relevant_impl(
983 self.tcx().require_lang_item(LangItem::Drop, None),
984 obligation.predicate.skip_binder().trait_ref.self_ty(),
988 if let Some(impl_def_id) = relevant_impl {
989 // Check that `impl Drop` is actually const, if there is a custom impl
990 if self.tcx().constness(impl_def_id) == hir::Constness::Const {
991 candidates.vec.push(ConstDestructCandidate(Some(impl_def_id)));
994 // Otherwise check the ADT like a built-in type (structurally)
995 candidates.vec.push(ConstDestructCandidate(None));
1000 candidates.ambiguous = true;
1005 fn assemble_candidate_for_tuple(
1007 obligation: &TraitObligation<'tcx>,
1008 candidates: &mut SelectionCandidateSet<'tcx>,
1010 let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder());
1011 match self_ty.kind() {
1013 candidates.vec.push(BuiltinCandidate { has_nested: false });
1015 ty::Infer(ty::TyVar(_)) => {
1016 candidates.ambiguous = true;
1032 | ty::Dynamic(_, _, _)
1034 | ty::Generator(_, _, _)
1035 | ty::GeneratorWitness(_)
1043 | ty::Placeholder(_) => {}
1047 fn assemble_candidate_for_ptr_sized(
1049 obligation: &TraitObligation<'tcx>,
1050 candidates: &mut SelectionCandidateSet<'tcx>,
1052 // The regions of a type don't affect the size of the type
1055 .erase_regions(self.tcx().erase_late_bound_regions(obligation.predicate.self_ty()));
1057 // But if there are inference variables, we have to wait until it's resolved.
1058 if self_ty.has_non_region_infer() {
1059 candidates.ambiguous = true;
1064 self.tcx().layout_of(ty::ParamEnv::empty().and(self.tcx().types.usize)).unwrap().layout;
1065 if let Ok(layout) = self.tcx().layout_of(obligation.param_env.and(self_ty))
1066 && layout.layout.size() == usize_layout.size()
1067 && layout.layout.align().abi == usize_layout.align().abi
1069 candidates.vec.push(BuiltinCandidate { has_nested: false });