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
9 use rustc_errors
::DelayDm
;
11 use rustc_hir
::def_id
::DefId
;
12 use rustc_infer
::traits
::ObligationCause
;
13 use rustc_infer
::traits
::{Obligation, SelectionError, TraitObligation}
;
14 use rustc_lint_defs
::builtin
::DEREF_INTO_DYN_SUPERTRAIT
;
15 use rustc_middle
::ty
::print
::with_no_trimmed_paths
;
16 use rustc_middle
::ty
::{self, ToPredicate, Ty, TypeVisitable}
;
17 use rustc_target
::spec
::abi
::Abi
;
20 use crate::traits
::coherence
::Conflict
;
21 use crate::traits
::query
::evaluate_obligation
::InferCtxtExt
;
22 use crate::traits
::{util, SelectionResult}
;
23 use crate::traits
::{Ambiguous, ErrorReporting, Overflow, Unimplemented}
;
25 use super::BuiltinImplConditions
;
26 use super::IntercrateAmbiguityCause
;
27 use super::OverflowError
;
28 use super::SelectionCandidate
::{self, *}
;
29 use super::{EvaluatedCandidate, SelectionCandidateSet, SelectionContext, TraitObligationStack}
;
31 impl<'cx
, 'tcx
> SelectionContext
<'cx
, 'tcx
> {
32 #[instrument(level = "debug", skip(self), ret)]
33 pub(super) fn candidate_from_obligation
<'o
>(
35 stack
: &TraitObligationStack
<'o
, 'tcx
>,
36 ) -> SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>> {
37 // Watch out for overflow. This intentionally bypasses (and does
38 // not update) the cache.
39 self.check_recursion_limit(&stack
.obligation
, &stack
.obligation
)?
;
41 // Check the cache. Note that we freshen the trait-ref
42 // separately rather than using `stack.fresh_trait_ref` --
43 // this is because we want the unbound variables to be
44 // replaced with fresh types starting from index 0.
45 let cache_fresh_trait_pred
= self.infcx
.freshen(stack
.obligation
.predicate
);
46 debug
!(?cache_fresh_trait_pred
);
47 debug_assert
!(!stack
.obligation
.predicate
.has_escaping_bound_vars());
50 self.check_candidate_cache(stack
.obligation
.param_env
, cache_fresh_trait_pred
)
56 // If no match, compute result and insert into cache.
58 // FIXME(nikomatsakis) -- this cache is not taking into
59 // account cycles that may have occurred in forming the
60 // candidate. I don't know of any specific problems that
61 // result but it seems awfully suspicious.
62 let (candidate
, dep_node
) =
63 self.in_task(|this
| this
.candidate_from_obligation_no_cache(stack
));
66 self.insert_candidate_cache(
67 stack
.obligation
.param_env
,
68 cache_fresh_trait_pred
,
75 fn candidate_from_obligation_no_cache
<'o
>(
77 stack
: &TraitObligationStack
<'o
, 'tcx
>,
78 ) -> SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>> {
79 if let Err(conflict
) = self.is_knowable(stack
) {
80 debug
!("coherence stage: not knowable");
81 if self.intercrate_ambiguity_causes
.is_some() {
82 debug
!("evaluate_stack: intercrate_ambiguity_causes is some");
83 // Heuristics: show the diagnostics when there are no candidates in crate.
84 if let Ok(candidate_set
) = self.assemble_candidates(stack
) {
85 let mut no_candidates_apply
= true;
87 for c
in candidate_set
.vec
.iter() {
88 if self.evaluate_candidate(stack
, &c
)?
.may_apply() {
89 no_candidates_apply
= false;
94 if !candidate_set
.ambiguous
&& no_candidates_apply
{
95 let trait_ref
= stack
.obligation
.predicate
.skip_binder().trait_ref
;
96 let self_ty
= trait_ref
.self_ty();
97 let (trait_desc
, self_desc
) = with_no_trimmed_paths
!({
98 let trait_desc
= trait_ref
.print_only_trait_path().to_string();
99 let self_desc
= if self_ty
.has_concrete_skeleton() {
100 Some(self_ty
.to_string())
104 (trait_desc
, self_desc
)
106 let cause
= if let Conflict
::Upstream
= conflict
{
107 IntercrateAmbiguityCause
::UpstreamCrateUpdate { trait_desc, self_desc }
109 IntercrateAmbiguityCause
::DownstreamCrate { trait_desc, self_desc }
111 debug
!(?cause
, "evaluate_stack: pushing cause");
112 self.intercrate_ambiguity_causes
.as_mut().unwrap().insert(cause
);
119 let candidate_set
= self.assemble_candidates(stack
)?
;
121 if candidate_set
.ambiguous
{
122 debug
!("candidate set contains ambig");
126 let candidates
= candidate_set
.vec
;
128 debug
!(?stack
, ?candidates
, "assembled {} candidates", candidates
.len());
130 // At this point, we know that each of the entries in the
131 // candidate set is *individually* applicable. Now we have to
132 // figure out if they contain mutual incompatibilities. This
133 // frequently arises if we have an unconstrained input type --
134 // for example, we are looking for `$0: Eq` where `$0` is some
135 // unconstrained type variable. In that case, we'll get a
136 // candidate which assumes $0 == int, one that assumes `$0 ==
137 // usize`, etc. This spells an ambiguity.
139 let mut candidates
= self.filter_impls(candidates
, stack
.obligation
);
141 // If there is more than one candidate, first winnow them down
142 // by considering extra conditions (nested obligations and so
143 // forth). We don't winnow if there is exactly one
144 // candidate. This is a relatively minor distinction but it
145 // can lead to better inference and error-reporting. An
146 // example would be if there was an impl:
148 // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
150 // and we were to see some code `foo.push_clone()` where `boo`
151 // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
152 // we were to winnow, we'd wind up with zero candidates.
153 // Instead, we select the right impl now but report "`Bar` does
154 // not implement `Clone`".
155 if candidates
.len() == 1 {
156 return self.filter_reservation_impls(candidates
.pop().unwrap(), stack
.obligation
);
159 // Winnow, but record the exact outcome of evaluation, which
160 // is needed for specialization. Propagate overflow if it occurs.
161 let mut candidates
= candidates
163 .map(|c
| match self.evaluate_candidate(stack
, &c
) {
164 Ok(eval
) if eval
.may_apply() => {
165 Ok(Some(EvaluatedCandidate { candidate: c, evaluation: eval }
))
168 Err(OverflowError
::Canonical
) => Err(Overflow(OverflowError
::Canonical
)),
169 Err(OverflowError
::ErrorReporting
) => Err(ErrorReporting
),
170 Err(OverflowError
::Error(e
)) => Err(Overflow(OverflowError
::Error(e
))),
172 .flat_map(Result
::transpose
)
173 .collect
::<Result
<Vec
<_
>, _
>>()?
;
175 debug
!(?stack
, ?candidates
, "winnowed to {} candidates", candidates
.len());
177 let needs_infer
= stack
.obligation
.predicate
.has_non_region_infer();
179 // If there are STILL multiple candidates, we can further
180 // reduce the list by dropping duplicates -- including
181 // resolving specializations.
182 if candidates
.len() > 1 {
184 while i
< candidates
.len() {
185 let is_dup
= (0..candidates
.len()).filter(|&j
| i
!= j
).any(|j
| {
186 self.candidate_should_be_dropped_in_favor_of(
193 debug
!(candidate
= ?candidates
[i
], "Dropping candidate #{}/{}", i
, candidates
.len());
194 candidates
.swap_remove(i
);
196 debug
!(candidate
= ?candidates
[i
], "Retaining candidate #{}/{}", i
, candidates
.len());
199 // If there are *STILL* multiple candidates, give up
200 // and report ambiguity.
202 debug
!("multiple matches, ambig");
203 return Err(Ambiguous(
206 .filter_map(|c
| match c
.candidate
{
207 SelectionCandidate
::ImplCandidate(def_id
) => Some(def_id
),
217 // If there are *NO* candidates, then there are no impls --
218 // that we know of, anyway. Note that in the case where there
219 // are unbound type variables within the obligation, it might
220 // be the case that you could still satisfy the obligation
221 // from another crate by instantiating the type variables with
222 // a type from another crate that does have an impl. This case
223 // is checked for in `evaluate_stack` (and hence users
224 // who might care about this case, like coherence, should use
226 if candidates
.is_empty() {
227 // If there's an error type, 'downgrade' our result from
228 // `Err(Unimplemented)` to `Ok(None)`. This helps us avoid
229 // emitting additional spurious errors, since we're guaranteed
230 // to have emitted at least one.
231 if stack
.obligation
.predicate
.references_error() {
232 debug
!(?stack
.obligation
.predicate
, "found error type in predicate, treating as ambiguous");
235 return Err(Unimplemented
);
238 // Just one candidate left.
239 self.filter_reservation_impls(candidates
.pop().unwrap().candidate
, stack
.obligation
)
242 #[instrument(skip(self, stack), level = "debug")]
243 pub(super) fn assemble_candidates
<'o
>(
245 stack
: &TraitObligationStack
<'o
, 'tcx
>,
246 ) -> Result
<SelectionCandidateSet
<'tcx
>, SelectionError
<'tcx
>> {
247 let TraitObligationStack { obligation, .. }
= *stack
;
248 let obligation
= &Obligation
{
249 param_env
: obligation
.param_env
,
250 cause
: obligation
.cause
.clone(),
251 recursion_depth
: obligation
.recursion_depth
,
252 predicate
: self.infcx().resolve_vars_if_possible(obligation
.predicate
),
255 if obligation
.predicate
.skip_binder().self_ty().is_ty_var() {
256 debug
!(ty
= ?obligation
.predicate
.skip_binder().self_ty(), "ambiguous inference var or opaque type");
257 // Self is a type variable (e.g., `_: AsRef<str>`).
259 // This is somewhat problematic, as the current scheme can't really
260 // handle it turning to be a projection. This does end up as truly
261 // ambiguous in most cases anyway.
263 // Take the fast path out - this also improves
264 // performance by preventing assemble_candidates_from_impls from
265 // matching every impl for this trait.
266 return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true }
);
269 let mut candidates
= SelectionCandidateSet { vec: Vec::new(), ambiguous: false }
;
271 // The only way to prove a NotImplemented(T: Foo) predicate is via a negative impl.
272 // There are no compiler built-in rules for this.
273 if obligation
.polarity() == ty
::ImplPolarity
::Negative
{
274 self.assemble_candidates_for_trait_alias(obligation
, &mut candidates
);
275 self.assemble_candidates_from_impls(obligation
, &mut candidates
);
277 self.assemble_candidates_for_trait_alias(obligation
, &mut candidates
);
279 // Other bounds. Consider both in-scope bounds from fn decl
280 // and applicable impls. There is a certain set of precedence rules here.
281 let def_id
= obligation
.predicate
.def_id();
282 let lang_items
= self.tcx().lang_items();
284 if lang_items
.copy_trait() == Some(def_id
) {
285 debug
!(obligation_self_ty
= ?obligation
.predicate
.skip_binder().self_ty());
287 // User-defined copy impls are permitted, but only for
288 // structs and enums.
289 self.assemble_candidates_from_impls(obligation
, &mut candidates
);
291 // For other types, we'll use the builtin rules.
292 let copy_conditions
= self.copy_clone_conditions(obligation
);
293 self.assemble_builtin_bound_candidates(copy_conditions
, &mut candidates
);
294 } else if lang_items
.discriminant_kind_trait() == Some(def_id
) {
295 // `DiscriminantKind` is automatically implemented for every type.
296 candidates
.vec
.push(DiscriminantKindCandidate
);
297 } else if lang_items
.pointee_trait() == Some(def_id
) {
298 // `Pointee` is automatically implemented for every type.
299 candidates
.vec
.push(PointeeCandidate
);
300 } else if lang_items
.sized_trait() == Some(def_id
) {
301 // Sized is never implementable by end-users, it is
302 // always automatically computed.
303 let sized_conditions
= self.sized_conditions(obligation
);
304 self.assemble_builtin_bound_candidates(sized_conditions
, &mut candidates
);
305 } else if lang_items
.unsize_trait() == Some(def_id
) {
306 self.assemble_candidates_for_unsizing(obligation
, &mut candidates
);
307 } else if lang_items
.destruct_trait() == Some(def_id
) {
308 self.assemble_const_destruct_candidates(obligation
, &mut candidates
);
309 } else if lang_items
.transmute_trait() == Some(def_id
) {
310 // User-defined transmutability impls are permitted.
311 self.assemble_candidates_from_impls(obligation
, &mut candidates
);
312 self.assemble_candidates_for_transmutability(obligation
, &mut candidates
);
313 } else if lang_items
.tuple_trait() == Some(def_id
) {
314 self.assemble_candidate_for_tuple(obligation
, &mut candidates
);
316 if lang_items
.clone_trait() == Some(def_id
) {
317 // Same builtin conditions as `Copy`, i.e., every type which has builtin support
318 // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
319 // types have builtin support for `Clone`.
320 let clone_conditions
= self.copy_clone_conditions(obligation
);
321 self.assemble_builtin_bound_candidates(clone_conditions
, &mut candidates
);
324 self.assemble_generator_candidates(obligation
, &mut candidates
);
325 self.assemble_closure_candidates(obligation
, &mut candidates
);
326 self.assemble_fn_pointer_candidates(obligation
, &mut candidates
);
327 self.assemble_candidates_from_impls(obligation
, &mut candidates
);
328 self.assemble_candidates_from_object_ty(obligation
, &mut candidates
);
331 self.assemble_candidates_from_projected_tys(obligation
, &mut candidates
);
332 self.assemble_candidates_from_caller_bounds(stack
, &mut candidates
)?
;
333 // Auto implementations have lower priority, so we only
334 // consider triggering a default if there is no other impl that can apply.
335 if candidates
.vec
.is_empty() {
336 self.assemble_candidates_from_auto_impls(obligation
, &mut candidates
);
339 debug
!("candidate list size: {}", candidates
.vec
.len());
343 #[instrument(level = "debug", skip(self, candidates))]
344 fn assemble_candidates_from_projected_tys(
346 obligation
: &TraitObligation
<'tcx
>,
347 candidates
: &mut SelectionCandidateSet
<'tcx
>,
349 // Before we go into the whole placeholder thing, just
350 // quickly check if the self-type is a projection at all.
351 match obligation
.predicate
.skip_binder().trait_ref
.self_ty().kind() {
352 ty
::Projection(_
) | ty
::Opaque(..) => {}
353 ty
::Infer(ty
::TyVar(_
)) => {
355 obligation
.cause
.span
,
356 "Self=_ should have been handled by assemble_candidates"
364 .probe(|_
| self.match_projection_obligation_against_definition_bounds(obligation
));
368 .extend(result
.into_iter().map(|(idx
, constness
)| ProjectionCandidate(idx
, constness
)));
371 /// Given an obligation like `<SomeTrait for T>`, searches the obligations that the caller
372 /// supplied to find out whether it is listed among them.
374 /// Never affects the inference environment.
375 #[instrument(level = "debug", skip(self, stack, candidates))]
376 fn assemble_candidates_from_caller_bounds
<'o
>(
378 stack
: &TraitObligationStack
<'o
, 'tcx
>,
379 candidates
: &mut SelectionCandidateSet
<'tcx
>,
380 ) -> Result
<(), SelectionError
<'tcx
>> {
381 debug
!(?stack
.obligation
);
383 let all_bounds
= stack
388 .filter_map(|o
| o
.to_opt_poly_trait_pred());
390 // Micro-optimization: filter out predicates relating to different traits.
391 let matching_bounds
=
392 all_bounds
.filter(|p
| p
.def_id() == stack
.obligation
.predicate
.def_id());
394 // Keep only those bounds which may apply, and propagate overflow if it occurs.
395 for bound
in matching_bounds
{
396 // FIXME(oli-obk): it is suspicious that we are dropping the constness and
398 let wc
= self.where_clause_may_apply(stack
, bound
.map_bound(|t
| t
.trait_ref
))?
;
400 candidates
.vec
.push(ParamCandidate(bound
));
407 fn assemble_generator_candidates(
409 obligation
: &TraitObligation
<'tcx
>,
410 candidates
: &mut SelectionCandidateSet
<'tcx
>,
412 if self.tcx().lang_items().gen_trait() != Some(obligation
.predicate
.def_id()) {
416 // Okay to skip binder because the substs on generator types never
417 // touch bound regions, they just capture the in-scope
418 // type/region parameters.
419 let self_ty
= obligation
.self_ty().skip_binder();
420 match self_ty
.kind() {
421 ty
::Generator(..) => {
422 debug
!(?self_ty
, ?obligation
, "assemble_generator_candidates",);
424 candidates
.vec
.push(GeneratorCandidate
);
426 ty
::Infer(ty
::TyVar(_
)) => {
427 debug
!("assemble_generator_candidates: ambiguous self-type");
428 candidates
.ambiguous
= true;
434 /// Checks for the artificial impl that the compiler will create for an obligation like `X :
435 /// FnMut<..>` where `X` is a closure type.
437 /// Note: the type parameters on a closure candidate are modeled as *output* type
438 /// parameters and hence do not affect whether this trait is a match or not. They will be
439 /// unified during the confirmation step.
440 fn assemble_closure_candidates(
442 obligation
: &TraitObligation
<'tcx
>,
443 candidates
: &mut SelectionCandidateSet
<'tcx
>,
445 let Some(kind
) = self.tcx().fn_trait_kind_from_lang_item(obligation
.predicate
.def_id()) else {
449 // Okay to skip binder because the substs on closure types never
450 // touch bound regions, they just capture the in-scope
451 // type/region parameters
452 match *obligation
.self_ty().skip_binder().kind() {
453 ty
::Closure(_
, closure_substs
) => {
454 debug
!(?kind
, ?obligation
, "assemble_unboxed_candidates");
455 match self.infcx
.closure_kind(closure_substs
) {
456 Some(closure_kind
) => {
457 debug
!(?closure_kind
, "assemble_unboxed_candidates");
458 if closure_kind
.extends(kind
) {
459 candidates
.vec
.push(ClosureCandidate
);
463 debug
!("assemble_unboxed_candidates: closure_kind not yet known");
464 candidates
.vec
.push(ClosureCandidate
);
468 ty
::Infer(ty
::TyVar(_
)) => {
469 debug
!("assemble_unboxed_closure_candidates: ambiguous self-type");
470 candidates
.ambiguous
= true;
476 /// Implements one of the `Fn()` family for a fn pointer.
477 fn assemble_fn_pointer_candidates(
479 obligation
: &TraitObligation
<'tcx
>,
480 candidates
: &mut SelectionCandidateSet
<'tcx
>,
482 // We provide impl of all fn traits for fn pointers.
483 if self.tcx().fn_trait_kind_from_lang_item(obligation
.predicate
.def_id()).is_none() {
487 // Okay to skip binder because what we are inspecting doesn't involve bound regions.
488 let self_ty
= obligation
.self_ty().skip_binder();
489 match *self_ty
.kind() {
490 ty
::Infer(ty
::TyVar(_
)) => {
491 debug
!("assemble_fn_pointer_candidates: ambiguous self-type");
492 candidates
.ambiguous
= true; // Could wind up being a fn() type.
494 // Provide an impl, but only for suitable `fn` pointers.
497 unsafety
: hir
::Unsafety
::Normal
,
501 } = self_ty
.fn_sig(self.tcx()).skip_binder()
503 candidates
.vec
.push(FnPointerCandidate { is_const: false }
);
506 // Provide an impl for suitable functions, rejecting `#[target_feature]` functions (RFC 2396).
507 ty
::FnDef(def_id
, _
) => {
509 unsafety
: hir
::Unsafety
::Normal
,
513 } = self_ty
.fn_sig(self.tcx()).skip_binder()
515 if self.tcx().codegen_fn_attrs(def_id
).target_features
.is_empty() {
518 .push(FnPointerCandidate { is_const: self.tcx().is_const_fn(def_id) }
);
526 /// Searches for impls that might apply to `obligation`.
527 fn assemble_candidates_from_impls(
529 obligation
: &TraitObligation
<'tcx
>,
530 candidates
: &mut SelectionCandidateSet
<'tcx
>,
532 debug
!(?obligation
, "assemble_candidates_from_impls");
534 // Essentially any user-written impl will match with an error type,
535 // so creating `ImplCandidates` isn't useful. However, we might
536 // end up finding a candidate elsewhere (e.g. a `BuiltinCandidate` for `Sized)
537 // This helps us avoid overflow: see issue #72839
538 // Since compilation is already guaranteed to fail, this is just
539 // to try to show the 'nicest' possible errors to the user.
540 // We don't check for errors in the `ParamEnv` - in practice,
541 // it seems to cause us to be overly aggressive in deciding
542 // to give up searching for candidates, leading to spurious errors.
543 if obligation
.predicate
.references_error() {
547 self.tcx().for_each_relevant_impl(
548 obligation
.predicate
.def_id(),
549 obligation
.predicate
.skip_binder().trait_ref
.self_ty(),
551 // Before we create the substitutions and everything, first
552 // consider a "quick reject". This avoids creating more types
553 // and so forth that we need to.
554 let impl_trait_ref
= self.tcx().bound_impl_trait_ref(impl_def_id
).unwrap();
555 if self.fast_reject_trait_refs(obligation
, &impl_trait_ref
.0) {
559 self.infcx
.probe(|_
| {
560 if let Ok(_substs
) = self.match_impl(impl_def_id
, impl_trait_ref
, obligation
) {
561 candidates
.vec
.push(ImplCandidate(impl_def_id
));
568 fn assemble_candidates_from_auto_impls(
570 obligation
: &TraitObligation
<'tcx
>,
571 candidates
: &mut SelectionCandidateSet
<'tcx
>,
573 // Okay to skip binder here because the tests we do below do not involve bound regions.
574 let self_ty
= obligation
.self_ty().skip_binder();
575 debug
!(?self_ty
, "assemble_candidates_from_auto_impls");
577 let def_id
= obligation
.predicate
.def_id();
579 if self.tcx().trait_is_auto(def_id
) {
580 match self_ty
.kind() {
582 // For object types, we don't know what the closed
583 // over types are. This means we conservatively
584 // say nothing; a candidate may be added by
585 // `assemble_candidates_from_object_ty`.
588 // Since the contents of foreign types is unknown,
589 // we don't add any `..` impl. Default traits could
590 // still be provided by a manual implementation for
591 // this trait and type.
593 ty
::Param(..) | ty
::Projection(..) => {
594 // In these cases, we don't know what the actual
595 // type is. Therefore, we cannot break it down
596 // into its constituent types. So we don't
597 // consider the `..` impl but instead just add no
598 // candidates: this means that typeck will only
599 // succeed if there is another reason to believe
600 // that this obligation holds. That could be a
601 // where-clause or, in the case of an object type,
602 // it could be that the object type lists the
603 // trait (e.g., `Foo+Send : Send`). See
604 // `ui/typeck/typeck-default-trait-impl-send-param.rs`
605 // for an example of a test case that exercises
608 ty
::Infer(ty
::TyVar(_
)) => {
609 // The auto impl might apply; we don't know.
610 candidates
.ambiguous
= true;
612 ty
::Generator(_
, _
, movability
)
613 if self.tcx().lang_items().unpin_trait() == Some(def_id
) =>
616 hir
::Movability
::Static
=> {
617 // Immovable generators are never `Unpin`, so
618 // suppress the normal auto-impl candidate for it.
620 hir
::Movability
::Movable
=> {
621 // Movable generators are always `Unpin`, so add an
622 // unconditional builtin candidate.
623 candidates
.vec
.push(BuiltinCandidate { has_nested: false }
);
628 _
=> candidates
.vec
.push(AutoImplCandidate
),
633 /// Searches for impls that might apply to `obligation`.
634 fn assemble_candidates_from_object_ty(
636 obligation
: &TraitObligation
<'tcx
>,
637 candidates
: &mut SelectionCandidateSet
<'tcx
>,
640 self_ty
= ?obligation
.self_ty().skip_binder(),
641 "assemble_candidates_from_object_ty",
644 self.infcx
.probe(|_snapshot
| {
645 // The code below doesn't care about regions, and the
646 // self-ty here doesn't escape this probe, so just erase
648 let self_ty
= self.tcx().erase_late_bound_regions(obligation
.self_ty());
649 let poly_trait_ref
= match self_ty
.kind() {
650 ty
::Dynamic(ref data
, ..) => {
651 if data
.auto_traits().any(|did
| did
== obligation
.predicate
.def_id()) {
653 "assemble_candidates_from_object_ty: matched builtin bound, \
656 candidates
.vec
.push(BuiltinObjectCandidate
);
660 if let Some(principal
) = data
.principal() {
661 if !self.infcx
.tcx
.features().object_safe_for_dispatch
{
662 principal
.with_self_ty(self.tcx(), self_ty
)
663 } else if self.tcx().is_object_safe(principal
.def_id()) {
664 principal
.with_self_ty(self.tcx(), self_ty
)
669 // Only auto trait bounds exist.
673 ty
::Infer(ty
::TyVar(_
)) => {
674 debug
!("assemble_candidates_from_object_ty: ambiguous");
675 candidates
.ambiguous
= true; // could wind up being an object type
681 debug
!(?poly_trait_ref
, "assemble_candidates_from_object_ty");
683 let poly_trait_predicate
= self.infcx().resolve_vars_if_possible(obligation
.predicate
);
684 let placeholder_trait_predicate
=
685 self.infcx().replace_bound_vars_with_placeholders(poly_trait_predicate
);
687 // Count only those upcast versions that match the trait-ref
688 // we are looking for. Specifically, do not only check for the
689 // correct trait, but also the correct type parameters.
690 // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
691 // but `Foo` is declared as `trait Foo: Bar<u32>`.
692 let candidate_supertraits
= util
::supertraits(self.tcx(), poly_trait_ref
)
694 .filter(|&(_
, upcast_trait_ref
)| {
695 self.infcx
.probe(|_
| {
696 self.match_normalize_trait_ref(
699 placeholder_trait_predicate
.trait_ref
,
704 .map(|(idx
, _
)| ObjectCandidate(idx
));
706 candidates
.vec
.extend(candidate_supertraits
);
710 /// Temporary migration for #89190
711 fn need_migrate_deref_output_trait_object(
714 param_env
: ty
::ParamEnv
<'tcx
>,
715 cause
: &ObligationCause
<'tcx
>,
716 ) -> Option
<(Ty
<'tcx
>, DefId
)> {
717 let tcx
= self.tcx();
718 if tcx
.features().trait_upcasting
{
723 let trait_ref
= ty
::TraitRef
{
724 def_id
: tcx
.lang_items().deref_trait()?
,
725 substs
: tcx
.mk_substs_trait(ty
, &[]),
728 let obligation
= traits
::Obligation
::new(
731 ty
::Binder
::dummy(trait_ref
).without_const().to_predicate(tcx
),
733 if !self.infcx
.predicate_may_hold(&obligation
) {
737 let ty
= traits
::normalize_projection_type(
741 item_def_id
: tcx
.lang_items().deref_target()?
,
742 substs
: trait_ref
.substs
,
746 // We're *intentionally* throwing these away,
747 // since we don't actually use them.
753 if let ty
::Dynamic(data
, ..) = ty
.kind() {
754 Some((ty
, data
.principal_def_id()?
))
760 /// Searches for unsizing that might apply to `obligation`.
761 fn assemble_candidates_for_unsizing(
763 obligation
: &TraitObligation
<'tcx
>,
764 candidates
: &mut SelectionCandidateSet
<'tcx
>,
766 // We currently never consider higher-ranked obligations e.g.
767 // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
768 // because they are a priori invalid, and we could potentially add support
769 // for them later, it's just that there isn't really a strong need for it.
770 // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
771 // impl, and those are generally applied to concrete types.
773 // That said, one might try to write a fn with a where clause like
774 // for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
775 // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
776 // Still, you'd be more likely to write that where clause as
778 // so it seems ok if we (conservatively) fail to accept that `Unsize`
779 // obligation above. Should be possible to extend this in the future.
780 let Some(source
) = obligation
.self_ty().no_bound_vars() else {
781 // Don't add any candidates if there are bound regions.
784 let target
= obligation
.predicate
.skip_binder().trait_ref
.substs
.type_at(1);
786 debug
!(?source
, ?target
, "assemble_candidates_for_unsizing");
788 match (source
.kind(), target
.kind()) {
789 // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
790 (&ty
::Dynamic(ref data_a
, ..), &ty
::Dynamic(ref data_b
, ..)) => {
791 // Upcast coercions permit several things:
793 // 1. Dropping auto traits, e.g., `Foo + Send` to `Foo`
794 // 2. Tightening the region bound, e.g., `Foo + 'a` to `Foo + 'b` if `'a: 'b`
795 // 3. Tightening trait to its super traits, eg. `Foo` to `Bar` if `Foo: Bar`
797 // Note that neither of the first two of these changes requires any
798 // change at runtime. The third needs to change pointer metadata at runtime.
800 // We always perform upcasting coercions when we can because of reason
801 // #2 (region bounds).
802 let auto_traits_compatible
= data_b
804 // All of a's auto traits need to be in b's auto traits.
805 .all(|b
| data_a
.auto_traits().any(|a
| a
== b
));
806 if auto_traits_compatible
{
807 let principal_def_id_a
= data_a
.principal_def_id();
808 let principal_def_id_b
= data_b
.principal_def_id();
809 if principal_def_id_a
== principal_def_id_b
{
811 candidates
.vec
.push(BuiltinUnsizeCandidate
);
812 } else if principal_def_id_a
.is_some() && principal_def_id_b
.is_some() {
813 // not casual unsizing, now check whether this is trait upcasting coercion.
814 let principal_a
= data_a
.principal().unwrap();
815 let target_trait_did
= principal_def_id_b
.unwrap();
816 let source_trait_ref
= principal_a
.with_self_ty(self.tcx(), source
);
817 if let Some((deref_output_ty
, deref_output_trait_did
)) = self
818 .need_migrate_deref_output_trait_object(
820 obligation
.param_env
,
824 if deref_output_trait_did
== target_trait_did
{
825 self.tcx().struct_span_lint_hir(
826 DEREF_INTO_DYN_SUPERTRAIT
,
827 obligation
.cause
.body_id
,
828 obligation
.cause
.span
,
830 "`{}` implements `Deref` with supertrait `{}` as output",
831 source
, deref_output_ty
839 for (idx
, upcast_trait_ref
) in
840 util
::supertraits(self.tcx(), source_trait_ref
).enumerate()
842 if upcast_trait_ref
.def_id() == target_trait_did
{
843 candidates
.vec
.push(TraitUpcastingUnsizeCandidate(idx
));
851 (_
, &ty
::Dynamic(..)) => {
852 candidates
.vec
.push(BuiltinUnsizeCandidate
);
855 // Ambiguous handling is below `T` -> `Trait`, because inference
856 // variables can still implement `Unsize<Trait>` and nested
857 // obligations will have the final say (likely deferred).
858 (&ty
::Infer(ty
::TyVar(_
)), _
) | (_
, &ty
::Infer(ty
::TyVar(_
))) => {
859 debug
!("assemble_candidates_for_unsizing: ambiguous");
860 candidates
.ambiguous
= true;
864 (&ty
::Array(..), &ty
::Slice(_
)) => {
865 candidates
.vec
.push(BuiltinUnsizeCandidate
);
868 // `Struct<T>` -> `Struct<U>`
869 (&ty
::Adt(def_id_a
, _
), &ty
::Adt(def_id_b
, _
)) if def_id_a
.is_struct() => {
870 if def_id_a
== def_id_b
{
871 candidates
.vec
.push(BuiltinUnsizeCandidate
);
875 // `(.., T)` -> `(.., U)`
876 (&ty
::Tuple(tys_a
), &ty
::Tuple(tys_b
)) => {
877 if tys_a
.len() == tys_b
.len() {
878 candidates
.vec
.push(BuiltinUnsizeCandidate
);
886 #[instrument(level = "debug", skip(self, obligation, candidates))]
887 fn assemble_candidates_for_transmutability(
889 obligation
: &TraitObligation
<'tcx
>,
890 candidates
: &mut SelectionCandidateSet
<'tcx
>,
892 if obligation
.has_non_region_param() {
896 if obligation
.has_non_region_infer() {
897 candidates
.ambiguous
= true;
901 candidates
.vec
.push(TransmutabilityCandidate
);
904 #[instrument(level = "debug", skip(self, obligation, candidates))]
905 fn assemble_candidates_for_trait_alias(
907 obligation
: &TraitObligation
<'tcx
>,
908 candidates
: &mut SelectionCandidateSet
<'tcx
>,
910 // Okay to skip binder here because the tests we do below do not involve bound regions.
911 let self_ty
= obligation
.self_ty().skip_binder();
914 let def_id
= obligation
.predicate
.def_id();
916 if self.tcx().is_trait_alias(def_id
) {
917 candidates
.vec
.push(TraitAliasCandidate
);
921 /// Assembles the trait which are built-in to the language itself:
922 /// `Copy`, `Clone` and `Sized`.
923 #[instrument(level = "debug", skip(self, candidates))]
924 fn assemble_builtin_bound_candidates(
926 conditions
: BuiltinImplConditions
<'tcx
>,
927 candidates
: &mut SelectionCandidateSet
<'tcx
>,
930 BuiltinImplConditions
::Where(nested
) => {
933 .push(BuiltinCandidate { has_nested: !nested.skip_binder().is_empty() }
);
935 BuiltinImplConditions
::None
=> {}
936 BuiltinImplConditions
::Ambiguous
=> {
937 candidates
.ambiguous
= true;
942 fn assemble_const_destruct_candidates(
944 obligation
: &TraitObligation
<'tcx
>,
945 candidates
: &mut SelectionCandidateSet
<'tcx
>,
947 // If the predicate is `~const Destruct` in a non-const environment, we don't actually need
948 // to check anything. We'll short-circuit checking any obligations in confirmation, too.
949 if !obligation
.is_const() {
950 candidates
.vec
.push(ConstDestructCandidate(None
));
954 let self_ty
= self.infcx().shallow_resolve(obligation
.self_ty());
955 match self_ty
.skip_binder().kind() {
962 | ty
::Projection(_
) => {
963 // We don't know if these are `~const Destruct`, at least
964 // not structurally... so don't push a candidate.
972 | ty
::Infer(ty
::IntVar(_
))
973 | ty
::Infer(ty
::FloatVar(_
))
986 | ty
::GeneratorWitness(_
) => {
987 // These are built-in, and cannot have a custom `impl const Destruct`.
988 candidates
.vec
.push(ConstDestructCandidate(None
));
992 // Find a custom `impl Drop` impl, if it exists
993 let relevant_impl
= self.tcx().find_map_relevant_impl(
994 self.tcx().require_lang_item(LangItem
::Drop
, None
),
995 obligation
.predicate
.skip_binder().trait_ref
.self_ty(),
999 if let Some(impl_def_id
) = relevant_impl
{
1000 // Check that `impl Drop` is actually const, if there is a custom impl
1001 if self.tcx().constness(impl_def_id
) == hir
::Constness
::Const
{
1002 candidates
.vec
.push(ConstDestructCandidate(Some(impl_def_id
)));
1005 // Otherwise check the ADT like a built-in type (structurally)
1006 candidates
.vec
.push(ConstDestructCandidate(None
));
1011 candidates
.ambiguous
= true;
1016 fn assemble_candidate_for_tuple(
1018 obligation
: &TraitObligation
<'tcx
>,
1019 candidates
: &mut SelectionCandidateSet
<'tcx
>,
1021 let self_ty
= self.infcx().shallow_resolve(obligation
.self_ty().skip_binder());
1022 match self_ty
.kind() {
1024 candidates
.vec
.push(BuiltinCandidate { has_nested: false }
);
1026 ty
::Infer(ty
::TyVar(_
)) => {
1027 candidates
.ambiguous
= true;
1043 | ty
::Dynamic(_
, _
, _
)
1045 | ty
::Generator(_
, _
, _
)
1046 | ty
::GeneratorWitness(_
)
1054 | ty
::Placeholder(_
) => {}