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_infer
::traits
::{Obligation, SelectionError, TraitObligation}
;
10 use rustc_middle
::ty
::print
::with_no_trimmed_paths
;
11 use rustc_middle
::ty
::{self, TypeFoldable}
;
12 use rustc_target
::spec
::abi
::Abi
;
14 use crate::traits
::coherence
::Conflict
;
15 use crate::traits
::{util, SelectionResult}
;
16 use crate::traits
::{Overflow, Unimplemented}
;
18 use super::BuiltinImplConditions
;
19 use super::IntercrateAmbiguityCause
;
20 use super::OverflowError
;
21 use super::SelectionCandidate
::{self, *}
;
22 use super::{EvaluatedCandidate, SelectionCandidateSet, SelectionContext, TraitObligationStack}
;
24 impl<'cx
, 'tcx
> SelectionContext
<'cx
, 'tcx
> {
25 #[instrument(level = "debug", skip(self))]
26 pub(super) fn candidate_from_obligation
<'o
>(
28 stack
: &TraitObligationStack
<'o
, 'tcx
>,
29 ) -> SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>> {
30 // Watch out for overflow. This intentionally bypasses (and does
31 // not update) the cache.
32 self.check_recursion_limit(&stack
.obligation
, &stack
.obligation
)?
;
34 // Check the cache. Note that we freshen the trait-ref
35 // separately rather than using `stack.fresh_trait_ref` --
36 // this is because we want the unbound variables to be
37 // replaced with fresh types starting from index 0.
38 let cache_fresh_trait_pred
= self.infcx
.freshen(stack
.obligation
.predicate
);
39 debug
!(?cache_fresh_trait_pred
);
40 debug_assert
!(!stack
.obligation
.predicate
.has_escaping_bound_vars());
43 self.check_candidate_cache(stack
.obligation
.param_env
, cache_fresh_trait_pred
)
45 debug
!(candidate
= ?c
, "CACHE HIT");
49 // If no match, compute result and insert into cache.
51 // FIXME(nikomatsakis) -- this cache is not taking into
52 // account cycles that may have occurred in forming the
53 // candidate. I don't know of any specific problems that
54 // result but it seems awfully suspicious.
55 let (candidate
, dep_node
) =
56 self.in_task(|this
| this
.candidate_from_obligation_no_cache(stack
));
58 debug
!(?candidate
, "CACHE MISS");
59 self.insert_candidate_cache(
60 stack
.obligation
.param_env
,
61 cache_fresh_trait_pred
,
68 fn candidate_from_obligation_no_cache
<'o
>(
70 stack
: &TraitObligationStack
<'o
, 'tcx
>,
71 ) -> SelectionResult
<'tcx
, SelectionCandidate
<'tcx
>> {
72 if let Some(conflict
) = self.is_knowable(stack
) {
73 debug
!("coherence stage: not knowable");
74 if self.intercrate_ambiguity_causes
.is_some() {
75 debug
!("evaluate_stack: intercrate_ambiguity_causes is some");
76 // Heuristics: show the diagnostics when there are no candidates in crate.
77 if let Ok(candidate_set
) = self.assemble_candidates(stack
) {
78 let mut no_candidates_apply
= true;
80 for c
in candidate_set
.vec
.iter() {
81 if self.evaluate_candidate(stack
, &c
)?
.may_apply() {
82 no_candidates_apply
= false;
87 if !candidate_set
.ambiguous
&& no_candidates_apply
{
88 let trait_ref
= stack
.obligation
.predicate
.skip_binder().trait_ref
;
89 let self_ty
= trait_ref
.self_ty();
90 let (trait_desc
, self_desc
) = with_no_trimmed_paths(|| {
91 let trait_desc
= trait_ref
.print_only_trait_path().to_string();
92 let self_desc
= if self_ty
.has_concrete_skeleton() {
93 Some(self_ty
.to_string())
97 (trait_desc
, self_desc
)
99 let cause
= if let Conflict
::Upstream
= conflict
{
100 IntercrateAmbiguityCause
::UpstreamCrateUpdate { trait_desc, self_desc }
102 IntercrateAmbiguityCause
::DownstreamCrate { trait_desc, self_desc }
104 debug
!(?cause
, "evaluate_stack: pushing cause");
105 self.intercrate_ambiguity_causes
.as_mut().unwrap().push(cause
);
112 let candidate_set
= self.assemble_candidates(stack
)?
;
114 if candidate_set
.ambiguous
{
115 debug
!("candidate set contains ambig");
119 let mut candidates
= candidate_set
.vec
;
121 debug
!(?stack
, ?candidates
, "assembled {} candidates", candidates
.len());
123 // At this point, we know that each of the entries in the
124 // candidate set is *individually* applicable. Now we have to
125 // figure out if they contain mutual incompatibilities. This
126 // frequently arises if we have an unconstrained input type --
127 // for example, we are looking for `$0: Eq` where `$0` is some
128 // unconstrained type variable. In that case, we'll get a
129 // candidate which assumes $0 == int, one that assumes `$0 ==
130 // usize`, etc. This spells an ambiguity.
132 // If there is more than one candidate, first winnow them down
133 // by considering extra conditions (nested obligations and so
134 // forth). We don't winnow if there is exactly one
135 // candidate. This is a relatively minor distinction but it
136 // can lead to better inference and error-reporting. An
137 // example would be if there was an impl:
139 // impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
141 // and we were to see some code `foo.push_clone()` where `boo`
142 // is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
143 // we were to winnow, we'd wind up with zero candidates.
144 // Instead, we select the right impl now but report "`Bar` does
145 // not implement `Clone`".
146 if candidates
.len() == 1 {
147 return self.filter_negative_and_reservation_impls(candidates
.pop().unwrap());
150 // Winnow, but record the exact outcome of evaluation, which
151 // is needed for specialization. Propagate overflow if it occurs.
152 let mut candidates
= candidates
154 .map(|c
| match self.evaluate_candidate(stack
, &c
) {
155 Ok(eval
) if eval
.may_apply() => {
156 Ok(Some(EvaluatedCandidate { candidate: c, evaluation: eval }
))
159 Err(OverflowError
) => Err(Overflow
),
161 .flat_map(Result
::transpose
)
162 .collect
::<Result
<Vec
<_
>, _
>>()?
;
164 debug
!(?stack
, ?candidates
, "winnowed to {} candidates", candidates
.len());
166 let needs_infer
= stack
.obligation
.predicate
.has_infer_types_or_consts();
168 // If there are STILL multiple candidates, we can further
169 // reduce the list by dropping duplicates -- including
170 // resolving specializations.
171 if candidates
.len() > 1 {
173 while i
< candidates
.len() {
174 let is_dup
= (0..candidates
.len()).filter(|&j
| i
!= j
).any(|j
| {
175 self.candidate_should_be_dropped_in_favor_of(
182 debug
!(candidate
= ?candidates
[i
], "Dropping candidate #{}/{}", i
, candidates
.len());
183 candidates
.swap_remove(i
);
185 debug
!(candidate
= ?candidates
[i
], "Retaining candidate #{}/{}", i
, candidates
.len());
188 // If there are *STILL* multiple candidates, give up
189 // and report ambiguity.
191 debug
!("multiple matches, ambig");
198 // If there are *NO* candidates, then there are no impls --
199 // that we know of, anyway. Note that in the case where there
200 // are unbound type variables within the obligation, it might
201 // be the case that you could still satisfy the obligation
202 // from another crate by instantiating the type variables with
203 // a type from another crate that does have an impl. This case
204 // is checked for in `evaluate_stack` (and hence users
205 // who might care about this case, like coherence, should use
207 if candidates
.is_empty() {
208 // If there's an error type, 'downgrade' our result from
209 // `Err(Unimplemented)` to `Ok(None)`. This helps us avoid
210 // emitting additional spurious errors, since we're guaranteed
211 // to have emitted at least one.
212 if stack
.obligation
.references_error() {
213 debug
!("no results for error type, treating as ambiguous");
216 return Err(Unimplemented
);
219 // Just one candidate left.
220 self.filter_negative_and_reservation_impls(candidates
.pop().unwrap().candidate
)
223 pub(super) fn assemble_candidates
<'o
>(
225 stack
: &TraitObligationStack
<'o
, 'tcx
>,
226 ) -> Result
<SelectionCandidateSet
<'tcx
>, SelectionError
<'tcx
>> {
227 let TraitObligationStack { obligation, .. }
= *stack
;
228 let obligation
= &Obligation
{
229 param_env
: obligation
.param_env
,
230 cause
: obligation
.cause
.clone(),
231 recursion_depth
: obligation
.recursion_depth
,
232 predicate
: self.infcx().resolve_vars_if_possible(obligation
.predicate
),
235 if obligation
.predicate
.skip_binder().self_ty().is_ty_var() {
236 // Self is a type variable (e.g., `_: AsRef<str>`).
238 // This is somewhat problematic, as the current scheme can't really
239 // handle it turning to be a projection. This does end up as truly
240 // ambiguous in most cases anyway.
242 // Take the fast path out - this also improves
243 // performance by preventing assemble_candidates_from_impls from
244 // matching every impl for this trait.
245 return Ok(SelectionCandidateSet { vec: vec![], ambiguous: true }
);
248 let mut candidates
= SelectionCandidateSet { vec: Vec::new(), ambiguous: false }
;
250 self.assemble_candidates_for_trait_alias(obligation
, &mut candidates
);
252 // Other bounds. Consider both in-scope bounds from fn decl
253 // and applicable impls. There is a certain set of precedence rules here.
254 let def_id
= obligation
.predicate
.def_id();
255 let lang_items
= self.tcx().lang_items();
257 if lang_items
.copy_trait() == Some(def_id
) {
258 debug
!(obligation_self_ty
= ?obligation
.predicate
.skip_binder().self_ty());
260 // User-defined copy impls are permitted, but only for
261 // structs and enums.
262 self.assemble_candidates_from_impls(obligation
, &mut candidates
);
264 // For other types, we'll use the builtin rules.
265 let copy_conditions
= self.copy_clone_conditions(obligation
);
266 self.assemble_builtin_bound_candidates(copy_conditions
, &mut candidates
);
267 } else if lang_items
.discriminant_kind_trait() == Some(def_id
) {
268 // `DiscriminantKind` is automatically implemented for every type.
269 candidates
.vec
.push(DiscriminantKindCandidate
);
270 } else if lang_items
.pointee_trait() == Some(def_id
) {
271 // `Pointee` is automatically implemented for every type.
272 candidates
.vec
.push(PointeeCandidate
);
273 } else if lang_items
.sized_trait() == Some(def_id
) {
274 // Sized is never implementable by end-users, it is
275 // always automatically computed.
276 let sized_conditions
= self.sized_conditions(obligation
);
277 self.assemble_builtin_bound_candidates(sized_conditions
, &mut candidates
);
278 } else if lang_items
.unsize_trait() == Some(def_id
) {
279 self.assemble_candidates_for_unsizing(obligation
, &mut candidates
);
281 if lang_items
.clone_trait() == Some(def_id
) {
282 // Same builtin conditions as `Copy`, i.e., every type which has builtin support
283 // for `Copy` also has builtin support for `Clone`, and tuples/arrays of `Clone`
284 // types have builtin support for `Clone`.
285 let clone_conditions
= self.copy_clone_conditions(obligation
);
286 self.assemble_builtin_bound_candidates(clone_conditions
, &mut candidates
);
289 self.assemble_generator_candidates(obligation
, &mut candidates
);
290 self.assemble_closure_candidates(obligation
, &mut candidates
);
291 self.assemble_fn_pointer_candidates(obligation
, &mut candidates
);
292 self.assemble_candidates_from_impls(obligation
, &mut candidates
);
293 self.assemble_candidates_from_object_ty(obligation
, &mut candidates
);
296 self.assemble_candidates_from_projected_tys(obligation
, &mut candidates
);
297 self.assemble_candidates_from_caller_bounds(stack
, &mut candidates
)?
;
298 // Auto implementations have lower priority, so we only
299 // consider triggering a default if there is no other impl that can apply.
300 if candidates
.vec
.is_empty() {
301 self.assemble_candidates_from_auto_impls(obligation
, &mut candidates
);
303 debug
!("candidate list size: {}", candidates
.vec
.len());
307 fn assemble_candidates_from_projected_tys(
309 obligation
: &TraitObligation
<'tcx
>,
310 candidates
: &mut SelectionCandidateSet
<'tcx
>,
312 debug
!(?obligation
, "assemble_candidates_from_projected_tys");
314 // Before we go into the whole placeholder thing, just
315 // quickly check if the self-type is a projection at all.
316 match obligation
.predicate
.skip_binder().trait_ref
.self_ty().kind() {
317 ty
::Projection(_
) | ty
::Opaque(..) => {}
318 ty
::Infer(ty
::TyVar(_
)) => {
320 obligation
.cause
.span
,
321 "Self=_ should have been handled by assemble_candidates"
329 .probe(|_
| self.match_projection_obligation_against_definition_bounds(obligation
));
331 for predicate_index
in result
{
332 candidates
.vec
.push(ProjectionCandidate(predicate_index
));
336 /// Given an obligation like `<SomeTrait for T>`, searches the obligations that the caller
337 /// supplied to find out whether it is listed among them.
339 /// Never affects the inference environment.
340 fn assemble_candidates_from_caller_bounds
<'o
>(
342 stack
: &TraitObligationStack
<'o
, 'tcx
>,
343 candidates
: &mut SelectionCandidateSet
<'tcx
>,
344 ) -> Result
<(), SelectionError
<'tcx
>> {
345 debug
!(?stack
.obligation
, "assemble_candidates_from_caller_bounds");
347 let all_bounds
= stack
352 .filter_map(|o
| o
.to_opt_poly_trait_ref());
354 // Micro-optimization: filter out predicates relating to different traits.
355 let matching_bounds
=
356 all_bounds
.filter(|p
| p
.value
.def_id() == stack
.obligation
.predicate
.def_id());
358 // Keep only those bounds which may apply, and propagate overflow if it occurs.
359 for bound
in matching_bounds
{
360 let wc
= self.evaluate_where_clause(stack
, bound
.value
)?
;
362 candidates
.vec
.push(ParamCandidate(bound
));
369 fn assemble_generator_candidates(
371 obligation
: &TraitObligation
<'tcx
>,
372 candidates
: &mut SelectionCandidateSet
<'tcx
>,
374 if self.tcx().lang_items().gen_trait() != Some(obligation
.predicate
.def_id()) {
378 // Okay to skip binder because the substs on generator types never
379 // touch bound regions, they just capture the in-scope
380 // type/region parameters.
381 let self_ty
= obligation
.self_ty().skip_binder();
382 match self_ty
.kind() {
383 ty
::Generator(..) => {
384 debug
!(?self_ty
, ?obligation
, "assemble_generator_candidates",);
386 candidates
.vec
.push(GeneratorCandidate
);
388 ty
::Infer(ty
::TyVar(_
)) => {
389 debug
!("assemble_generator_candidates: ambiguous self-type");
390 candidates
.ambiguous
= true;
396 /// Checks for the artificial impl that the compiler will create for an obligation like `X :
397 /// FnMut<..>` where `X` is a closure type.
399 /// Note: the type parameters on a closure candidate are modeled as *output* type
400 /// parameters and hence do not affect whether this trait is a match or not. They will be
401 /// unified during the confirmation step.
402 fn assemble_closure_candidates(
404 obligation
: &TraitObligation
<'tcx
>,
405 candidates
: &mut SelectionCandidateSet
<'tcx
>,
407 let kind
= match self.tcx().fn_trait_kind_from_lang_item(obligation
.predicate
.def_id()) {
414 // Okay to skip binder because the substs on closure types never
415 // touch bound regions, they just capture the in-scope
416 // type/region parameters
417 match *obligation
.self_ty().skip_binder().kind() {
418 ty
::Closure(_
, closure_substs
) => {
419 debug
!(?kind
, ?obligation
, "assemble_unboxed_candidates");
420 match self.infcx
.closure_kind(closure_substs
) {
421 Some(closure_kind
) => {
422 debug
!(?closure_kind
, "assemble_unboxed_candidates");
423 if closure_kind
.extends(kind
) {
424 candidates
.vec
.push(ClosureCandidate
);
428 debug
!("assemble_unboxed_candidates: closure_kind not yet known");
429 candidates
.vec
.push(ClosureCandidate
);
433 ty
::Infer(ty
::TyVar(_
)) => {
434 debug
!("assemble_unboxed_closure_candidates: ambiguous self-type");
435 candidates
.ambiguous
= true;
441 /// Implements one of the `Fn()` family for a fn pointer.
442 fn assemble_fn_pointer_candidates(
444 obligation
: &TraitObligation
<'tcx
>,
445 candidates
: &mut SelectionCandidateSet
<'tcx
>,
447 // We provide impl of all fn traits for fn pointers.
448 if self.tcx().fn_trait_kind_from_lang_item(obligation
.predicate
.def_id()).is_none() {
452 // Okay to skip binder because what we are inspecting doesn't involve bound regions.
453 let self_ty
= obligation
.self_ty().skip_binder();
454 match *self_ty
.kind() {
455 ty
::Infer(ty
::TyVar(_
)) => {
456 debug
!("assemble_fn_pointer_candidates: ambiguous self-type");
457 candidates
.ambiguous
= true; // Could wind up being a fn() type.
459 // Provide an impl, but only for suitable `fn` pointers.
462 unsafety
: hir
::Unsafety
::Normal
,
466 } = self_ty
.fn_sig(self.tcx()).skip_binder()
468 candidates
.vec
.push(FnPointerCandidate
);
471 // Provide an impl for suitable functions, rejecting `#[target_feature]` functions (RFC 2396).
472 ty
::FnDef(def_id
, _
) => {
474 unsafety
: hir
::Unsafety
::Normal
,
478 } = self_ty
.fn_sig(self.tcx()).skip_binder()
480 if self.tcx().codegen_fn_attrs(def_id
).target_features
.is_empty() {
481 candidates
.vec
.push(FnPointerCandidate
);
489 /// Searches for impls that might apply to `obligation`.
490 fn assemble_candidates_from_impls(
492 obligation
: &TraitObligation
<'tcx
>,
493 candidates
: &mut SelectionCandidateSet
<'tcx
>,
495 debug
!(?obligation
, "assemble_candidates_from_impls");
497 // Essentially any user-written impl will match with an error type,
498 // so creating `ImplCandidates` isn't useful. However, we might
499 // end up finding a candidate elsewhere (e.g. a `BuiltinCandidate` for `Sized)
500 // This helps us avoid overflow: see issue #72839
501 // Since compilation is already guaranteed to fail, this is just
502 // to try to show the 'nicest' possible errors to the user.
503 if obligation
.references_error() {
507 self.tcx().for_each_relevant_impl(
508 obligation
.predicate
.def_id(),
509 obligation
.predicate
.skip_binder().trait_ref
.self_ty(),
511 self.infcx
.probe(|_
| {
512 if let Ok(_substs
) = self.match_impl(impl_def_id
, obligation
) {
513 candidates
.vec
.push(ImplCandidate(impl_def_id
));
520 fn assemble_candidates_from_auto_impls(
522 obligation
: &TraitObligation
<'tcx
>,
523 candidates
: &mut SelectionCandidateSet
<'tcx
>,
525 // Okay to skip binder here because the tests we do below do not involve bound regions.
526 let self_ty
= obligation
.self_ty().skip_binder();
527 debug
!(?self_ty
, "assemble_candidates_from_auto_impls");
529 let def_id
= obligation
.predicate
.def_id();
531 if self.tcx().trait_is_auto(def_id
) {
532 match self_ty
.kind() {
534 // For object types, we don't know what the closed
535 // over types are. This means we conservatively
536 // say nothing; a candidate may be added by
537 // `assemble_candidates_from_object_ty`.
540 // Since the contents of foreign types is unknown,
541 // we don't add any `..` impl. Default traits could
542 // still be provided by a manual implementation for
543 // this trait and type.
545 ty
::Param(..) | ty
::Projection(..) => {
546 // In these cases, we don't know what the actual
547 // type is. Therefore, we cannot break it down
548 // into its constituent types. So we don't
549 // consider the `..` impl but instead just add no
550 // candidates: this means that typeck will only
551 // succeed if there is another reason to believe
552 // that this obligation holds. That could be a
553 // where-clause or, in the case of an object type,
554 // it could be that the object type lists the
555 // trait (e.g., `Foo+Send : Send`). See
556 // `ui/typeck/typeck-default-trait-impl-send-param.rs`
557 // for an example of a test case that exercises
560 ty
::Infer(ty
::TyVar(_
)) => {
561 // The auto impl might apply; we don't know.
562 candidates
.ambiguous
= true;
564 ty
::Generator(_
, _
, movability
)
565 if self.tcx().lang_items().unpin_trait() == Some(def_id
) =>
568 hir
::Movability
::Static
=> {
569 // Immovable generators are never `Unpin`, so
570 // suppress the normal auto-impl candidate for it.
572 hir
::Movability
::Movable
=> {
573 // Movable generators are always `Unpin`, so add an
574 // unconditional builtin candidate.
575 candidates
.vec
.push(BuiltinCandidate { has_nested: false }
);
580 _
=> candidates
.vec
.push(AutoImplCandidate(def_id
)),
585 /// Searches for impls that might apply to `obligation`.
586 fn assemble_candidates_from_object_ty(
588 obligation
: &TraitObligation
<'tcx
>,
589 candidates
: &mut SelectionCandidateSet
<'tcx
>,
592 self_ty
= ?obligation
.self_ty().skip_binder(),
593 "assemble_candidates_from_object_ty",
596 self.infcx
.probe(|_snapshot
| {
597 // The code below doesn't care about regions, and the
598 // self-ty here doesn't escape this probe, so just erase
600 let self_ty
= self.tcx().erase_late_bound_regions(obligation
.self_ty());
601 let poly_trait_ref
= match self_ty
.kind() {
602 ty
::Dynamic(ref data
, ..) => {
603 if data
.auto_traits().any(|did
| did
== obligation
.predicate
.def_id()) {
605 "assemble_candidates_from_object_ty: matched builtin bound, \
608 candidates
.vec
.push(BuiltinObjectCandidate
);
612 if let Some(principal
) = data
.principal() {
613 if !self.infcx
.tcx
.features().object_safe_for_dispatch
{
614 principal
.with_self_ty(self.tcx(), self_ty
)
615 } else if self.tcx().is_object_safe(principal
.def_id()) {
616 principal
.with_self_ty(self.tcx(), self_ty
)
621 // Only auto trait bounds exist.
625 ty
::Infer(ty
::TyVar(_
)) => {
626 debug
!("assemble_candidates_from_object_ty: ambiguous");
627 candidates
.ambiguous
= true; // could wind up being an object type
633 debug
!(?poly_trait_ref
, "assemble_candidates_from_object_ty");
635 let poly_trait_predicate
= self.infcx().resolve_vars_if_possible(obligation
.predicate
);
636 let placeholder_trait_predicate
=
637 self.infcx().replace_bound_vars_with_placeholders(poly_trait_predicate
);
639 // Count only those upcast versions that match the trait-ref
640 // we are looking for. Specifically, do not only check for the
641 // correct trait, but also the correct type parameters.
642 // For example, we may be trying to upcast `Foo` to `Bar<i32>`,
643 // but `Foo` is declared as `trait Foo: Bar<u32>`.
644 let candidate_supertraits
= util
::supertraits(self.tcx(), poly_trait_ref
)
646 .filter(|&(_
, upcast_trait_ref
)| {
647 self.infcx
.probe(|_
| {
648 self.match_normalize_trait_ref(
651 placeholder_trait_predicate
.trait_ref
,
656 .map(|(idx
, _
)| ObjectCandidate(idx
));
658 candidates
.vec
.extend(candidate_supertraits
);
662 /// Searches for unsizing that might apply to `obligation`.
663 fn assemble_candidates_for_unsizing(
665 obligation
: &TraitObligation
<'tcx
>,
666 candidates
: &mut SelectionCandidateSet
<'tcx
>,
668 // We currently never consider higher-ranked obligations e.g.
669 // `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
670 // because they are a priori invalid, and we could potentially add support
671 // for them later, it's just that there isn't really a strong need for it.
672 // A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
673 // impl, and those are generally applied to concrete types.
675 // That said, one might try to write a fn with a where clause like
676 // for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
677 // where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
678 // Still, you'd be more likely to write that where clause as
680 // so it seems ok if we (conservatively) fail to accept that `Unsize`
681 // obligation above. Should be possible to extend this in the future.
682 let source
= match obligation
.self_ty().no_bound_vars() {
685 // Don't add any candidates if there are bound regions.
689 let target
= obligation
.predicate
.skip_binder().trait_ref
.substs
.type_at(1);
691 debug
!(?source
, ?target
, "assemble_candidates_for_unsizing");
693 let may_apply
= match (source
.kind(), target
.kind()) {
694 // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
695 (&ty
::Dynamic(ref data_a
, ..), &ty
::Dynamic(ref data_b
, ..)) => {
696 // Upcasts permit two things:
698 // 1. Dropping auto traits, e.g., `Foo + Send` to `Foo`
699 // 2. Tightening the region bound, e.g., `Foo + 'a` to `Foo + 'b` if `'a: 'b`
701 // Note that neither of these changes requires any
702 // change at runtime. Eventually this will be
705 // We always upcast when we can because of reason
706 // #2 (region bounds).
707 data_a
.principal_def_id() == data_b
.principal_def_id()
710 // All of a's auto traits need to be in b's auto traits.
711 .all(|b
| data_a
.auto_traits().any(|a
| a
== b
))
715 (_
, &ty
::Dynamic(..)) => true,
717 // Ambiguous handling is below `T` -> `Trait`, because inference
718 // variables can still implement `Unsize<Trait>` and nested
719 // obligations will have the final say (likely deferred).
720 (&ty
::Infer(ty
::TyVar(_
)), _
) | (_
, &ty
::Infer(ty
::TyVar(_
))) => {
721 debug
!("assemble_candidates_for_unsizing: ambiguous");
722 candidates
.ambiguous
= true;
727 (&ty
::Array(..), &ty
::Slice(_
)) => true,
729 // `Struct<T>` -> `Struct<U>`
730 (&ty
::Adt(def_id_a
, _
), &ty
::Adt(def_id_b
, _
)) if def_id_a
.is_struct() => {
734 // `(.., T)` -> `(.., U)`
735 (&ty
::Tuple(tys_a
), &ty
::Tuple(tys_b
)) => tys_a
.len() == tys_b
.len(),
741 candidates
.vec
.push(BuiltinUnsizeCandidate
);
745 fn assemble_candidates_for_trait_alias(
747 obligation
: &TraitObligation
<'tcx
>,
748 candidates
: &mut SelectionCandidateSet
<'tcx
>,
750 // Okay to skip binder here because the tests we do below do not involve bound regions.
751 let self_ty
= obligation
.self_ty().skip_binder();
752 debug
!(?self_ty
, "assemble_candidates_for_trait_alias");
754 let def_id
= obligation
.predicate
.def_id();
756 if self.tcx().is_trait_alias(def_id
) {
757 candidates
.vec
.push(TraitAliasCandidate(def_id
));
761 /// Assembles the trait which are built-in to the language itself:
762 /// `Copy`, `Clone` and `Sized`.
763 fn assemble_builtin_bound_candidates(
765 conditions
: BuiltinImplConditions
<'tcx
>,
766 candidates
: &mut SelectionCandidateSet
<'tcx
>,
769 BuiltinImplConditions
::Where(nested
) => {
770 debug
!(?nested
, "builtin_bound");
773 .push(BuiltinCandidate { has_nested: !nested.skip_binder().is_empty() }
);
775 BuiltinImplConditions
::None
=> {}
776 BuiltinImplConditions
::Ambiguous
=> {
777 debug
!("assemble_builtin_bound_candidates: ambiguous builtin");
778 candidates
.ambiguous
= true;