1use std::ops::ControlFlow;
11
12use rustc_data_structures::stack::ensure_sufficient_stack;
13use rustc_hir::lang_items::LangItem;
14use rustc_infer::infer::{BoundRegionConversionTime, DefineOpaqueTypes, InferOk};
15use rustc_infer::traits::ObligationCauseCode;
16use rustc_middle::traits::{BuiltinImplSource, SignatureMismatchData};
17use rustc_middle::ty::{
18 self, GenericArgsRef, Region, SizedTraitKind, Ty, TyCtxt, Upcast, elaborate,
19};
20use rustc_middle::{bug, span_bug};
21use rustc_span::def_id::DefId;
22use thin_vec::thin_vec;
23use tracing::{debug, instrument};
24
25use super::SelectionCandidate::{self, *};
26use super::{BuiltinImplConditions, PredicateObligations, SelectionContext};
27use crate::traits::normalize::{normalize_with_depth, normalize_with_depth_to};
28use crate::traits::util::{self, closure_trait_ref_and_return_type};
29use crate::traits::{
30 ImplSource, ImplSourceUserDefinedData, Normalized, Obligation, ObligationCause,
31 PolyTraitObligation, PredicateObligation, Selection, SelectionError, TraitObligation,
32};
33
34impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
35 #[instrument(level = "debug", skip(self))]
36 pub(super) fn confirm_candidate(
37 &mut self,
38 obligation: &PolyTraitObligation<'tcx>,
39 candidate: SelectionCandidate<'tcx>,
40 ) -> Result<Selection<'tcx>, SelectionError<'tcx>> {
41 Ok(match candidate {
42 SizedCandidate { has_nested } => {
43 let data = self.confirm_builtin_candidate(obligation, has_nested);
44 ImplSource::Builtin(BuiltinImplSource::Misc, data)
45 }
46
47 BuiltinCandidate { has_nested } => {
48 let data = self.confirm_builtin_candidate(obligation, has_nested);
49 ImplSource::Builtin(BuiltinImplSource::Misc, data)
50 }
51
52 TransmutabilityCandidate => {
53 let data = self.confirm_transmutability_candidate(obligation)?;
54 ImplSource::Builtin(BuiltinImplSource::Misc, data)
55 }
56
57 ParamCandidate(param) => {
58 let obligations =
59 self.confirm_param_candidate(obligation, param.map_bound(|t| t.trait_ref));
60 ImplSource::Param(obligations)
61 }
62
63 ImplCandidate(impl_def_id) => {
64 ImplSource::UserDefined(self.confirm_impl_candidate(obligation, impl_def_id))
65 }
66
67 AutoImplCandidate => {
68 let data = self.confirm_auto_impl_candidate(obligation)?;
69 ImplSource::Builtin(BuiltinImplSource::Misc, data)
70 }
71
72 ProjectionCandidate(idx) => {
73 let obligations = self.confirm_projection_candidate(obligation, idx)?;
74 ImplSource::Param(obligations)
75 }
76
77 ObjectCandidate(idx) => self.confirm_object_candidate(obligation, idx)?,
78
79 ClosureCandidate { .. } => {
80 let vtable_closure = self.confirm_closure_candidate(obligation)?;
81 ImplSource::Builtin(BuiltinImplSource::Misc, vtable_closure)
82 }
83
84 AsyncClosureCandidate => {
85 let vtable_closure = self.confirm_async_closure_candidate(obligation)?;
86 ImplSource::Builtin(BuiltinImplSource::Misc, vtable_closure)
87 }
88
89 AsyncFnKindHelperCandidate => {
92 ImplSource::Builtin(BuiltinImplSource::Misc, PredicateObligations::new())
93 }
94
95 CoroutineCandidate => {
96 let vtable_coroutine = self.confirm_coroutine_candidate(obligation)?;
97 ImplSource::Builtin(BuiltinImplSource::Misc, vtable_coroutine)
98 }
99
100 FutureCandidate => {
101 let vtable_future = self.confirm_future_candidate(obligation)?;
102 ImplSource::Builtin(BuiltinImplSource::Misc, vtable_future)
103 }
104
105 IteratorCandidate => {
106 let vtable_iterator = self.confirm_iterator_candidate(obligation)?;
107 ImplSource::Builtin(BuiltinImplSource::Misc, vtable_iterator)
108 }
109
110 AsyncIteratorCandidate => {
111 let vtable_iterator = self.confirm_async_iterator_candidate(obligation)?;
112 ImplSource::Builtin(BuiltinImplSource::Misc, vtable_iterator)
113 }
114
115 FnPointerCandidate => {
116 let data = self.confirm_fn_pointer_candidate(obligation)?;
117 ImplSource::Builtin(BuiltinImplSource::Misc, data)
118 }
119
120 TraitAliasCandidate => {
121 let data = self.confirm_trait_alias_candidate(obligation);
122 ImplSource::Builtin(BuiltinImplSource::Misc, data)
123 }
124
125 BuiltinObjectCandidate => {
126 ImplSource::Builtin(BuiltinImplSource::Misc, PredicateObligations::new())
130 }
131
132 BuiltinUnsizeCandidate => self.confirm_builtin_unsize_candidate(obligation)?,
133
134 TraitUpcastingUnsizeCandidate(idx) => {
135 self.confirm_trait_upcasting_unsize_candidate(obligation, idx)?
136 }
137
138 BikeshedGuaranteedNoDropCandidate => {
139 self.confirm_bikeshed_guaranteed_no_drop_candidate(obligation)
140 }
141 })
142 }
143
144 fn confirm_projection_candidate(
145 &mut self,
146 obligation: &PolyTraitObligation<'tcx>,
147 idx: usize,
148 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
149 let tcx = self.tcx();
150
151 let placeholder_trait_predicate =
152 self.infcx.enter_forall_and_leak_universe(obligation.predicate).trait_ref;
153 let placeholder_self_ty = self.infcx.shallow_resolve(placeholder_trait_predicate.self_ty());
154 let candidate_predicate = self
155 .for_each_item_bound(
156 placeholder_self_ty,
157 |_, clause, clause_idx| {
158 if clause_idx == idx {
159 ControlFlow::Break(clause)
160 } else {
161 ControlFlow::Continue(())
162 }
163 },
164 || unreachable!(),
165 )
166 .break_value()
167 .expect("expected to index into clause that exists");
168 let candidate_predicate = candidate_predicate
169 .as_trait_clause()
170 .expect("projection candidate is not a trait predicate");
171 let candidate_predicate =
172 util::lazily_elaborate_sizedness_candidate(self.infcx, obligation, candidate_predicate);
173
174 let candidate = candidate_predicate.map_bound(|t| t.trait_ref);
175
176 let candidate = self.infcx.instantiate_binder_with_fresh_vars(
177 obligation.cause.span,
178 BoundRegionConversionTime::HigherRankedType,
179 candidate,
180 );
181 let mut obligations = PredicateObligations::new();
182 let candidate = normalize_with_depth_to(
183 self,
184 obligation.param_env,
185 obligation.cause.clone(),
186 obligation.recursion_depth + 1,
187 candidate,
188 &mut obligations,
189 );
190
191 obligations.extend(
192 self.infcx
193 .at(&obligation.cause, obligation.param_env)
194 .eq(DefineOpaqueTypes::No, placeholder_trait_predicate, candidate)
195 .map(|InferOk { obligations, .. }| obligations)
196 .map_err(|_| SelectionError::Unimplemented)?,
197 );
198
199 if let ty::Alias(ty::Projection, alias_ty) = placeholder_self_ty.kind() {
201 let predicates = tcx.predicates_of(alias_ty.def_id).instantiate_own(tcx, alias_ty.args);
202 for (predicate, _) in predicates {
203 let normalized = normalize_with_depth_to(
204 self,
205 obligation.param_env,
206 obligation.cause.clone(),
207 obligation.recursion_depth + 1,
208 predicate,
209 &mut obligations,
210 );
211 obligations.push(Obligation::with_depth(
212 self.tcx(),
213 obligation.cause.clone(),
214 obligation.recursion_depth + 1,
215 obligation.param_env,
216 normalized,
217 ));
218 }
219 }
220
221 Ok(obligations)
222 }
223
224 fn confirm_param_candidate(
225 &mut self,
226 obligation: &PolyTraitObligation<'tcx>,
227 param: ty::PolyTraitRef<'tcx>,
228 ) -> PredicateObligations<'tcx> {
229 debug!(?obligation, ?param, "confirm_param_candidate");
230
231 let param = util::lazily_elaborate_sizedness_candidate(
232 self.infcx,
233 obligation,
234 param.upcast(self.infcx.tcx),
235 )
236 .map_bound(|p| p.trait_ref);
237
238 match self.match_where_clause_trait_ref(obligation, param) {
243 Ok(obligations) => obligations,
244 Err(()) => {
245 bug!(
246 "Where clause `{:?}` was applicable to `{:?}` but now is not",
247 param,
248 obligation
249 );
250 }
251 }
252 }
253
254 fn confirm_builtin_candidate(
255 &mut self,
256 obligation: &PolyTraitObligation<'tcx>,
257 has_nested: bool,
258 ) -> PredicateObligations<'tcx> {
259 debug!(?obligation, ?has_nested, "confirm_builtin_candidate");
260
261 let tcx = self.tcx();
262 let obligations = if has_nested {
263 let trait_def = obligation.predicate.def_id();
264 let conditions = match tcx.as_lang_item(trait_def) {
265 Some(LangItem::Sized) => {
266 self.sizedness_conditions(obligation, SizedTraitKind::Sized)
267 }
268 Some(LangItem::MetaSized) => {
269 self.sizedness_conditions(obligation, SizedTraitKind::MetaSized)
270 }
271 Some(LangItem::PointeeSized) => {
272 bug!("`PointeeSized` is removing during lowering");
273 }
274 Some(LangItem::Copy | LangItem::Clone) => self.copy_clone_conditions(obligation),
275 Some(LangItem::FusedIterator) => self.fused_iterator_conditions(obligation),
276 other => bug!("unexpected builtin trait {trait_def:?} ({other:?})"),
277 };
278 let BuiltinImplConditions::Where(types) = conditions else {
279 bug!("obligation {:?} had matched a builtin impl but now doesn't", obligation);
280 };
281 let types = self.infcx.enter_forall_and_leak_universe(types);
282
283 let cause = obligation.derived_cause(ObligationCauseCode::BuiltinDerived);
284 self.collect_predicates_for_types(
285 obligation.param_env,
286 cause,
287 obligation.recursion_depth + 1,
288 trait_def,
289 types,
290 )
291 } else {
292 PredicateObligations::new()
293 };
294
295 debug!(?obligations);
296
297 obligations
298 }
299
300 #[instrument(level = "debug", skip(self))]
301 fn confirm_transmutability_candidate(
302 &mut self,
303 obligation: &PolyTraitObligation<'tcx>,
304 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
305 use rustc_transmute::{Answer, Assume, Condition};
306
307 #[instrument(level = "debug", skip(tcx, obligation))]
309 fn flatten_answer_tree<'tcx>(
310 tcx: TyCtxt<'tcx>,
311 obligation: &PolyTraitObligation<'tcx>,
312 cond: Condition<Region<'tcx>, Ty<'tcx>>,
313 assume: Assume,
314 ) -> PredicateObligations<'tcx> {
315 match cond {
316 Condition::IfAll(conds) | Condition::IfAny(conds) => conds
319 .into_iter()
320 .flat_map(|cond| flatten_answer_tree(tcx, obligation, cond, assume))
321 .collect(),
322 Condition::Immutable { ty } => {
323 let trait_ref = ty::TraitRef::new(
324 tcx,
325 tcx.require_lang_item(LangItem::Freeze, obligation.cause.span),
326 [ty::GenericArg::from(ty)],
327 );
328 thin_vec![Obligation::with_depth(
329 tcx,
330 obligation.cause.clone(),
331 obligation.recursion_depth + 1,
332 obligation.param_env,
333 trait_ref,
334 )]
335 }
336 Condition::Outlives { long, short } => {
337 let outlives = ty::OutlivesPredicate(long, short);
338 thin_vec![Obligation::with_depth(
339 tcx,
340 obligation.cause.clone(),
341 obligation.recursion_depth + 1,
342 obligation.param_env,
343 outlives,
344 )]
345 }
346 Condition::Transmutable { src, dst } => {
347 let transmute_trait = obligation.predicate.def_id();
348 let assume = obligation.predicate.skip_binder().trait_ref.args.const_at(2);
349 let trait_ref = ty::TraitRef::new(
350 tcx,
351 transmute_trait,
352 [
353 ty::GenericArg::from(dst),
354 ty::GenericArg::from(src),
355 ty::GenericArg::from(assume),
356 ],
357 );
358 thin_vec![Obligation::with_depth(
359 tcx,
360 obligation.cause.clone(),
361 obligation.recursion_depth + 1,
362 obligation.param_env,
363 trait_ref,
364 )]
365 }
366 }
367 }
368
369 let predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
370
371 let mut assume = predicate.trait_ref.args.const_at(2);
372 if self.tcx().features().generic_const_exprs() {
373 assume = crate::traits::evaluate_const(self.infcx, assume, obligation.param_env)
374 }
375 let Some(assume) = rustc_transmute::Assume::from_const(self.infcx.tcx, assume) else {
376 return Err(SelectionError::Unimplemented);
377 };
378
379 let dst = predicate.trait_ref.args.type_at(0);
380 let src = predicate.trait_ref.args.type_at(1);
381
382 debug!(?src, ?dst);
383 let mut transmute_env = rustc_transmute::TransmuteTypeEnv::new(self.infcx.tcx);
384 let maybe_transmutable =
385 transmute_env.is_transmutable(rustc_transmute::Types { dst, src }, assume);
386
387 let fully_flattened = match maybe_transmutable {
388 Answer::No(_) => Err(SelectionError::Unimplemented)?,
389 Answer::If(cond) => flatten_answer_tree(self.tcx(), obligation, cond, assume),
390 Answer::Yes => PredicateObligations::new(),
391 };
392
393 debug!(?fully_flattened);
394 Ok(fully_flattened)
395 }
396
397 fn confirm_auto_impl_candidate(
403 &mut self,
404 obligation: &PolyTraitObligation<'tcx>,
405 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
406 ensure_sufficient_stack(|| {
407 assert_eq!(obligation.predicate.polarity(), ty::PredicatePolarity::Positive);
408
409 let self_ty =
410 obligation.predicate.self_ty().map_bound(|ty| self.infcx.shallow_resolve(ty));
411
412 let types = self.constituent_types_for_ty(self_ty)?;
413 let types = self.infcx.enter_forall_and_leak_universe(types);
414
415 let cause = obligation.derived_cause(ObligationCauseCode::BuiltinDerived);
416 let obligations = self.collect_predicates_for_types(
417 obligation.param_env,
418 cause,
419 obligation.recursion_depth + 1,
420 obligation.predicate.def_id(),
421 types,
422 );
423
424 Ok(obligations)
425 })
426 }
427
428 fn confirm_impl_candidate(
429 &mut self,
430 obligation: &PolyTraitObligation<'tcx>,
431 impl_def_id: DefId,
432 ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
433 debug!(?obligation, ?impl_def_id, "confirm_impl_candidate");
434
435 let args = self.rematch_impl(impl_def_id, obligation);
438 debug!(?args, "impl args");
439 ensure_sufficient_stack(|| {
440 self.vtable_impl(
441 impl_def_id,
442 args,
443 &obligation.cause,
444 obligation.recursion_depth + 1,
445 obligation.param_env,
446 obligation.predicate,
447 )
448 })
449 }
450
451 fn vtable_impl(
452 &mut self,
453 impl_def_id: DefId,
454 args: Normalized<'tcx, GenericArgsRef<'tcx>>,
455 cause: &ObligationCause<'tcx>,
456 recursion_depth: usize,
457 param_env: ty::ParamEnv<'tcx>,
458 parent_trait_pred: ty::Binder<'tcx, ty::TraitPredicate<'tcx>>,
459 ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
460 debug!(?impl_def_id, ?args, ?recursion_depth, "vtable_impl");
461
462 let mut impl_obligations = self.impl_or_trait_obligations(
463 cause,
464 recursion_depth,
465 param_env,
466 impl_def_id,
467 args.value,
468 parent_trait_pred,
469 );
470
471 debug!(?impl_obligations, "vtable_impl");
472
473 impl_obligations.extend(args.obligations);
479
480 ImplSourceUserDefinedData { impl_def_id, args: args.value, nested: impl_obligations }
481 }
482
483 fn confirm_object_candidate(
484 &mut self,
485 obligation: &PolyTraitObligation<'tcx>,
486 index: usize,
487 ) -> Result<ImplSource<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
488 let tcx = self.tcx();
489 debug!(?obligation, ?index, "confirm_object_candidate");
490
491 let trait_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
492 let self_ty = self.infcx.shallow_resolve(trait_predicate.self_ty());
493 let ty::Dynamic(data, ..) = *self_ty.kind() else {
494 span_bug!(obligation.cause.span, "object candidate with non-object");
495 };
496
497 let object_trait_ref = data.principal().unwrap_or_else(|| {
498 span_bug!(obligation.cause.span, "object candidate with no principal")
499 });
500 let object_trait_ref = self.infcx.instantiate_binder_with_fresh_vars(
501 obligation.cause.span,
502 BoundRegionConversionTime::HigherRankedType,
503 object_trait_ref,
504 );
505 let object_trait_ref = object_trait_ref.with_self_ty(self.tcx(), self_ty);
506
507 let mut nested = PredicateObligations::new();
508
509 let mut supertraits = util::supertraits(tcx, ty::Binder::dummy(object_trait_ref));
510 let unnormalized_upcast_trait_ref =
511 supertraits.nth(index).expect("supertraits iterator no longer has as many elements");
512
513 let upcast_trait_ref = self.infcx.instantiate_binder_with_fresh_vars(
514 obligation.cause.span,
515 BoundRegionConversionTime::HigherRankedType,
516 unnormalized_upcast_trait_ref,
517 );
518 let upcast_trait_ref = normalize_with_depth_to(
519 self,
520 obligation.param_env,
521 obligation.cause.clone(),
522 obligation.recursion_depth + 1,
523 upcast_trait_ref,
524 &mut nested,
525 );
526
527 nested.extend(
528 self.infcx
529 .at(&obligation.cause, obligation.param_env)
530 .eq(DefineOpaqueTypes::No, trait_predicate.trait_ref, upcast_trait_ref)
531 .map(|InferOk { obligations, .. }| obligations)
532 .map_err(|_| SelectionError::Unimplemented)?,
533 );
534
535 for (supertrait, _) in tcx
538 .explicit_super_predicates_of(trait_predicate.def_id())
539 .iter_instantiated_copied(tcx, trait_predicate.trait_ref.args)
540 {
541 let normalized_supertrait = normalize_with_depth_to(
542 self,
543 obligation.param_env,
544 obligation.cause.clone(),
545 obligation.recursion_depth + 1,
546 supertrait,
547 &mut nested,
548 );
549 nested.push(obligation.with(tcx, normalized_supertrait));
550 }
551
552 let assoc_types: Vec<_> = tcx
553 .associated_items(trait_predicate.def_id())
554 .in_definition_order()
555 .filter(|item| !tcx.generics_require_sized_self(item.def_id))
558 .filter_map(|item| if item.is_type() { Some(item.def_id) } else { None })
559 .collect();
560
561 for assoc_type in assoc_types {
562 let defs: &ty::Generics = tcx.generics_of(assoc_type);
563
564 if !defs.own_params.is_empty() {
565 tcx.dcx().span_delayed_bug(
566 obligation.cause.span,
567 "GATs in trait object shouldn't have been considered",
568 );
569 return Err(SelectionError::TraitDynIncompatible(trait_predicate.trait_ref.def_id));
570 }
571
572 for bound in self.tcx().item_bounds(assoc_type).transpose_iter() {
576 let normalized_bound = normalize_with_depth_to(
577 self,
578 obligation.param_env,
579 obligation.cause.clone(),
580 obligation.recursion_depth + 1,
581 bound.instantiate(tcx, trait_predicate.trait_ref.args),
582 &mut nested,
583 );
584 nested.push(obligation.with(tcx, normalized_bound));
585 }
586 }
587
588 debug!(?nested, "object nested obligations");
589
590 Ok(ImplSource::Builtin(BuiltinImplSource::Object(index), nested))
591 }
592
593 fn confirm_fn_pointer_candidate(
594 &mut self,
595 obligation: &PolyTraitObligation<'tcx>,
596 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
597 debug!(?obligation, "confirm_fn_pointer_candidate");
598 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
599 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
600
601 let tcx = self.tcx();
602 let sig = self_ty.fn_sig(tcx);
603 let trait_ref = closure_trait_ref_and_return_type(
604 tcx,
605 obligation.predicate.def_id(),
606 self_ty,
607 sig,
608 util::TupleArgumentsFlag::Yes,
609 )
610 .map_bound(|(trait_ref, _)| trait_ref);
611
612 let mut nested =
613 self.equate_trait_refs(obligation.with(tcx, placeholder_predicate), trait_ref)?;
614 let cause = obligation.derived_cause(ObligationCauseCode::BuiltinDerived);
615
616 let output_ty = self.infcx.enter_forall_and_leak_universe(sig.output());
618 let output_ty = normalize_with_depth_to(
619 self,
620 obligation.param_env,
621 cause.clone(),
622 obligation.recursion_depth,
623 output_ty,
624 &mut nested,
625 );
626 let tr = ty::TraitRef::new(
627 self.tcx(),
628 self.tcx().require_lang_item(LangItem::Sized, cause.span),
629 [output_ty],
630 );
631 nested.push(Obligation::new(self.infcx.tcx, cause, obligation.param_env, tr));
632
633 Ok(nested)
634 }
635
636 fn confirm_trait_alias_candidate(
637 &mut self,
638 obligation: &PolyTraitObligation<'tcx>,
639 ) -> PredicateObligations<'tcx> {
640 debug!(?obligation, "confirm_trait_alias_candidate");
641
642 let predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
643 let trait_ref = predicate.trait_ref;
644 let trait_def_id = trait_ref.def_id;
645 let args = trait_ref.args;
646
647 let trait_obligations = self.impl_or_trait_obligations(
648 &obligation.cause,
649 obligation.recursion_depth,
650 obligation.param_env,
651 trait_def_id,
652 args,
653 obligation.predicate,
654 );
655
656 debug!(?trait_def_id, ?trait_obligations, "trait alias obligations");
657
658 trait_obligations
659 }
660
661 fn confirm_coroutine_candidate(
662 &mut self,
663 obligation: &PolyTraitObligation<'tcx>,
664 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
665 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
666 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
667 let ty::Coroutine(coroutine_def_id, args) = *self_ty.kind() else {
668 bug!("closure candidate for non-closure {:?}", obligation);
669 };
670
671 debug!(?obligation, ?coroutine_def_id, ?args, "confirm_coroutine_candidate");
672
673 let coroutine_sig = args.as_coroutine().sig();
674
675 let (trait_ref, _, _) = super::util::coroutine_trait_ref_and_outputs(
676 self.tcx(),
677 obligation.predicate.def_id(),
678 self_ty,
679 coroutine_sig,
680 );
681
682 let nested = self.equate_trait_refs(
683 obligation.with(self.tcx(), placeholder_predicate),
684 ty::Binder::dummy(trait_ref),
685 )?;
686 debug!(?trait_ref, ?nested, "coroutine candidate obligations");
687
688 Ok(nested)
689 }
690
691 fn confirm_future_candidate(
692 &mut self,
693 obligation: &PolyTraitObligation<'tcx>,
694 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
695 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
696 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
697 let ty::Coroutine(coroutine_def_id, args) = *self_ty.kind() else {
698 bug!("closure candidate for non-closure {:?}", obligation);
699 };
700
701 debug!(?obligation, ?coroutine_def_id, ?args, "confirm_future_candidate");
702
703 let coroutine_sig = args.as_coroutine().sig();
704
705 let (trait_ref, _) = super::util::future_trait_ref_and_outputs(
706 self.tcx(),
707 obligation.predicate.def_id(),
708 self_ty,
709 coroutine_sig,
710 );
711
712 let nested = self.equate_trait_refs(
713 obligation.with(self.tcx(), placeholder_predicate),
714 ty::Binder::dummy(trait_ref),
715 )?;
716 debug!(?trait_ref, ?nested, "future candidate obligations");
717
718 Ok(nested)
719 }
720
721 fn confirm_iterator_candidate(
722 &mut self,
723 obligation: &PolyTraitObligation<'tcx>,
724 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
725 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
726 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
727 let ty::Coroutine(coroutine_def_id, args) = *self_ty.kind() else {
728 bug!("closure candidate for non-closure {:?}", obligation);
729 };
730
731 debug!(?obligation, ?coroutine_def_id, ?args, "confirm_iterator_candidate");
732
733 let gen_sig = args.as_coroutine().sig();
734
735 let (trait_ref, _) = super::util::iterator_trait_ref_and_outputs(
736 self.tcx(),
737 obligation.predicate.def_id(),
738 self_ty,
739 gen_sig,
740 );
741
742 let nested = self.equate_trait_refs(
743 obligation.with(self.tcx(), placeholder_predicate),
744 ty::Binder::dummy(trait_ref),
745 )?;
746 debug!(?trait_ref, ?nested, "iterator candidate obligations");
747
748 Ok(nested)
749 }
750
751 fn confirm_async_iterator_candidate(
752 &mut self,
753 obligation: &PolyTraitObligation<'tcx>,
754 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
755 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
756 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
757 let ty::Coroutine(coroutine_def_id, args) = *self_ty.kind() else {
758 bug!("closure candidate for non-closure {:?}", obligation);
759 };
760
761 debug!(?obligation, ?coroutine_def_id, ?args, "confirm_async_iterator_candidate");
762
763 let gen_sig = args.as_coroutine().sig();
764
765 let (trait_ref, _) = super::util::async_iterator_trait_ref_and_outputs(
766 self.tcx(),
767 obligation.predicate.def_id(),
768 self_ty,
769 gen_sig,
770 );
771
772 let nested = self.equate_trait_refs(
773 obligation.with(self.tcx(), placeholder_predicate),
774 ty::Binder::dummy(trait_ref),
775 )?;
776 debug!(?trait_ref, ?nested, "iterator candidate obligations");
777
778 Ok(nested)
779 }
780
781 #[instrument(skip(self), level = "debug")]
782 fn confirm_closure_candidate(
783 &mut self,
784 obligation: &PolyTraitObligation<'tcx>,
785 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
786 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
787 let self_ty: Ty<'_> = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
788
789 let trait_ref = match *self_ty.kind() {
790 ty::Closure(..) => {
791 self.closure_trait_ref_unnormalized(self_ty, obligation.predicate.def_id())
792 }
793 ty::CoroutineClosure(_, args) => {
794 args.as_coroutine_closure().coroutine_closure_sig().map_bound(|sig| {
795 ty::TraitRef::new(
796 self.tcx(),
797 obligation.predicate.def_id(),
798 [self_ty, sig.tupled_inputs_ty],
799 )
800 })
801 }
802 _ => {
803 bug!("closure candidate for non-closure {:?}", obligation);
804 }
805 };
806
807 self.equate_trait_refs(obligation.with(self.tcx(), placeholder_predicate), trait_ref)
808 }
809
810 #[instrument(skip(self), level = "debug")]
811 fn confirm_async_closure_candidate(
812 &mut self,
813 obligation: &PolyTraitObligation<'tcx>,
814 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
815 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
816 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
817
818 let tcx = self.tcx();
819
820 let mut nested = PredicateObligations::new();
821 let (trait_ref, kind_ty) = match *self_ty.kind() {
822 ty::CoroutineClosure(_, args) => {
823 let args = args.as_coroutine_closure();
824 let trait_ref = args.coroutine_closure_sig().map_bound(|sig| {
825 ty::TraitRef::new(
826 self.tcx(),
827 obligation.predicate.def_id(),
828 [self_ty, sig.tupled_inputs_ty],
829 )
830 });
831
832 (trait_ref, args.kind_ty())
836 }
837 ty::FnDef(..) | ty::FnPtr(..) => {
838 let sig = self_ty.fn_sig(tcx);
839 let trait_ref = sig.map_bound(|sig| {
840 ty::TraitRef::new(
841 self.tcx(),
842 obligation.predicate.def_id(),
843 [self_ty, Ty::new_tup(tcx, sig.inputs())],
844 )
845 });
846
847 let future_trait_def_id =
849 tcx.require_lang_item(LangItem::Future, obligation.cause.span);
850 nested.push(obligation.with(
851 tcx,
852 sig.output().map_bound(|output_ty| {
853 ty::TraitRef::new(tcx, future_trait_def_id, [output_ty])
854 }),
855 ));
856 let sized_trait_def_id =
857 tcx.require_lang_item(LangItem::Sized, obligation.cause.span);
858 nested.push(obligation.with(
859 tcx,
860 sig.output().map_bound(|output_ty| {
861 ty::TraitRef::new(tcx, sized_trait_def_id, [output_ty])
862 }),
863 ));
864
865 (trait_ref, Ty::from_closure_kind(tcx, ty::ClosureKind::Fn))
866 }
867 ty::Closure(_, args) => {
868 let args = args.as_closure();
869 let sig = args.sig();
870 let trait_ref = sig.map_bound(|sig| {
871 ty::TraitRef::new(
872 self.tcx(),
873 obligation.predicate.def_id(),
874 [self_ty, sig.inputs()[0]],
875 )
876 });
877
878 let future_trait_def_id =
880 tcx.require_lang_item(LangItem::Future, obligation.cause.span);
881 let placeholder_output_ty = self.infcx.enter_forall_and_leak_universe(sig.output());
882 nested.push(obligation.with(
883 tcx,
884 ty::TraitRef::new(tcx, future_trait_def_id, [placeholder_output_ty]),
885 ));
886 let sized_trait_def_id =
887 tcx.require_lang_item(LangItem::Sized, obligation.cause.span);
888 nested.push(obligation.with(
889 tcx,
890 sig.output().map_bound(|output_ty| {
891 ty::TraitRef::new(tcx, sized_trait_def_id, [output_ty])
892 }),
893 ));
894
895 (trait_ref, args.kind_ty())
896 }
897 _ => bug!("expected callable type for AsyncFn candidate"),
898 };
899
900 nested.extend(
901 self.equate_trait_refs(obligation.with(tcx, placeholder_predicate), trait_ref)?,
902 );
903
904 let goal_kind =
905 self.tcx().async_fn_trait_kind_from_def_id(obligation.predicate.def_id()).unwrap();
906
907 if let Some(closure_kind) = self.infcx.shallow_resolve(kind_ty).to_opt_closure_kind() {
911 if !closure_kind.extends(goal_kind) {
912 return Err(SelectionError::Unimplemented);
913 }
914 } else {
915 nested.push(Obligation::new(
916 self.tcx(),
917 obligation.derived_cause(ObligationCauseCode::BuiltinDerived),
918 obligation.param_env,
919 ty::TraitRef::new(
920 self.tcx(),
921 self.tcx()
922 .require_lang_item(LangItem::AsyncFnKindHelper, obligation.cause.span),
923 [kind_ty, Ty::from_closure_kind(self.tcx(), goal_kind)],
924 ),
925 ));
926 }
927
928 Ok(nested)
929 }
930
931 #[instrument(skip(self), level = "trace")]
957 fn equate_trait_refs(
958 &mut self,
959 obligation: TraitObligation<'tcx>,
960 found_trait_ref: ty::PolyTraitRef<'tcx>,
961 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
962 let found_trait_ref = self.infcx.instantiate_binder_with_fresh_vars(
963 obligation.cause.span,
964 BoundRegionConversionTime::HigherRankedType,
965 found_trait_ref,
966 );
967 let Normalized { obligations: nested, value: (obligation_trait_ref, found_trait_ref) } =
969 ensure_sufficient_stack(|| {
970 normalize_with_depth(
971 self,
972 obligation.param_env,
973 obligation.cause.clone(),
974 obligation.recursion_depth + 1,
975 (obligation.predicate.trait_ref, found_trait_ref),
976 )
977 });
978
979 self.infcx
981 .at(&obligation.cause, obligation.param_env)
982 .eq(DefineOpaqueTypes::Yes, obligation_trait_ref, found_trait_ref)
983 .map(|InferOk { mut obligations, .. }| {
984 obligations.extend(nested);
985 obligations
986 })
987 .map_err(|terr| {
988 SelectionError::SignatureMismatch(Box::new(SignatureMismatchData {
989 expected_trait_ref: obligation_trait_ref,
990 found_trait_ref,
991 terr,
992 }))
993 })
994 }
995
996 fn confirm_trait_upcasting_unsize_candidate(
997 &mut self,
998 obligation: &PolyTraitObligation<'tcx>,
999 idx: usize,
1000 ) -> Result<ImplSource<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
1001 let tcx = self.tcx();
1002
1003 let predicate = obligation.predicate.no_bound_vars().unwrap();
1006 let a_ty = self.infcx.shallow_resolve(predicate.self_ty());
1007 let b_ty = self.infcx.shallow_resolve(predicate.trait_ref.args.type_at(1));
1008
1009 let ty::Dynamic(a_data, a_region, ty::Dyn) = *a_ty.kind() else {
1010 bug!("expected `dyn` type in `confirm_trait_upcasting_unsize_candidate`")
1011 };
1012 let ty::Dynamic(b_data, b_region, ty::Dyn) = *b_ty.kind() else {
1013 bug!("expected `dyn` type in `confirm_trait_upcasting_unsize_candidate`")
1014 };
1015
1016 let source_principal = a_data.principal().unwrap().with_self_ty(tcx, a_ty);
1017 let unnormalized_upcast_principal =
1018 util::supertraits(tcx, source_principal).nth(idx).unwrap();
1019
1020 let nested = self
1021 .match_upcast_principal(
1022 obligation,
1023 unnormalized_upcast_principal,
1024 a_data,
1025 b_data,
1026 a_region,
1027 b_region,
1028 )?
1029 .expect("did not expect ambiguity during confirmation");
1030
1031 Ok(ImplSource::Builtin(BuiltinImplSource::TraitUpcasting(idx), nested))
1032 }
1033
1034 fn confirm_builtin_unsize_candidate(
1035 &mut self,
1036 obligation: &PolyTraitObligation<'tcx>,
1037 ) -> Result<ImplSource<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
1038 let tcx = self.tcx();
1039
1040 let source = self.infcx.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap());
1043 let target = obligation.predicate.skip_binder().trait_ref.args.type_at(1);
1044 let target = self.infcx.shallow_resolve(target);
1045 debug!(?source, ?target, "confirm_builtin_unsize_candidate");
1046
1047 Ok(match (source.kind(), target.kind()) {
1048 (&ty::Dynamic(data_a, r_a, dyn_a), &ty::Dynamic(data_b, r_b, dyn_b))
1050 if dyn_a == dyn_b =>
1051 {
1052 let existential_predicates = if data_b.principal().is_some() {
1055 tcx.mk_poly_existential_predicates_from_iter(
1056 data_a
1057 .principal()
1058 .map(|b| b.map_bound(ty::ExistentialPredicate::Trait))
1059 .into_iter()
1060 .chain(
1061 data_a
1062 .projection_bounds()
1063 .map(|b| b.map_bound(ty::ExistentialPredicate::Projection)),
1064 )
1065 .chain(
1066 data_b
1067 .auto_traits()
1068 .map(ty::ExistentialPredicate::AutoTrait)
1069 .map(ty::Binder::dummy),
1070 ),
1071 )
1072 } else {
1073 tcx.mk_poly_existential_predicates_from_iter(
1078 data_b
1079 .auto_traits()
1080 .map(ty::ExistentialPredicate::AutoTrait)
1081 .map(ty::Binder::dummy),
1082 )
1083 };
1084 let source_trait = Ty::new_dynamic(tcx, existential_predicates, r_b, dyn_a);
1085
1086 let InferOk { mut obligations, .. } = self
1089 .infcx
1090 .at(&obligation.cause, obligation.param_env)
1091 .sup(DefineOpaqueTypes::Yes, target, source_trait)
1092 .map_err(|_| SelectionError::Unimplemented)?;
1093
1094 let outlives = ty::OutlivesPredicate(r_a, r_b);
1096 obligations.push(Obligation::with_depth(
1097 tcx,
1098 obligation.cause.clone(),
1099 obligation.recursion_depth + 1,
1100 obligation.param_env,
1101 obligation.predicate.rebind(outlives),
1102 ));
1103
1104 ImplSource::Builtin(BuiltinImplSource::Misc, obligations)
1105 }
1106
1107 (_, &ty::Dynamic(data, r, ty::Dyn)) => {
1109 let mut object_dids = data.auto_traits().chain(data.principal_def_id());
1110 if let Some(did) = object_dids.find(|did| !tcx.is_dyn_compatible(*did)) {
1111 return Err(SelectionError::TraitDynIncompatible(did));
1112 }
1113
1114 let predicate_to_obligation = |predicate| {
1115 Obligation::with_depth(
1116 tcx,
1117 obligation.cause.clone(),
1118 obligation.recursion_depth + 1,
1119 obligation.param_env,
1120 predicate,
1121 )
1122 };
1123
1124 let mut nested: PredicateObligations<'_> = data
1131 .iter()
1132 .map(|predicate| predicate_to_obligation(predicate.with_self_ty(tcx, source)))
1133 .collect();
1134
1135 let tr = ty::TraitRef::new(
1137 tcx,
1138 tcx.require_lang_item(LangItem::Sized, obligation.cause.span),
1139 [source],
1140 );
1141 nested.push(predicate_to_obligation(tr.upcast(tcx)));
1142
1143 let outlives = ty::OutlivesPredicate(source, r);
1146 nested.push(predicate_to_obligation(
1147 ty::ClauseKind::TypeOutlives(outlives).upcast(tcx),
1148 ));
1149
1150 if let Some(principal) = data.principal() {
1153 for supertrait in
1154 elaborate::supertraits(tcx, principal.with_self_ty(tcx, source))
1155 {
1156 if tcx.is_trait_alias(supertrait.def_id()) {
1157 continue;
1158 }
1159
1160 for &assoc_item in tcx.associated_item_def_ids(supertrait.def_id()) {
1161 if !tcx.is_impl_trait_in_trait(assoc_item) {
1162 continue;
1163 }
1164
1165 if tcx.generics_require_sized_self(assoc_item) {
1167 continue;
1168 }
1169
1170 let pointer_like_goal = pointer_like_goal_for_rpitit(
1171 tcx,
1172 supertrait,
1173 assoc_item,
1174 &obligation.cause,
1175 );
1176
1177 nested.push(predicate_to_obligation(pointer_like_goal.upcast(tcx)));
1178 }
1179 }
1180 }
1181
1182 ImplSource::Builtin(BuiltinImplSource::Misc, nested)
1183 }
1184
1185 (&ty::Array(a, _), &ty::Slice(b)) => {
1187 let InferOk { obligations, .. } = self
1188 .infcx
1189 .at(&obligation.cause, obligation.param_env)
1190 .eq(DefineOpaqueTypes::Yes, b, a)
1191 .map_err(|_| SelectionError::Unimplemented)?;
1192
1193 ImplSource::Builtin(BuiltinImplSource::Misc, obligations)
1194 }
1195
1196 (&ty::Adt(def, args_a), &ty::Adt(_, args_b)) => {
1198 let unsizing_params = tcx.unsizing_params_for_adt(def.did());
1199 if unsizing_params.is_empty() {
1200 return Err(SelectionError::Unimplemented);
1201 }
1202
1203 let tail_field = def.non_enum_variant().tail();
1204 let tail_field_ty = tcx.type_of(tail_field.did);
1205
1206 let mut nested = PredicateObligations::new();
1207
1208 let source_tail = normalize_with_depth_to(
1212 self,
1213 obligation.param_env,
1214 obligation.cause.clone(),
1215 obligation.recursion_depth + 1,
1216 tail_field_ty.instantiate(tcx, args_a),
1217 &mut nested,
1218 );
1219 let target_tail = normalize_with_depth_to(
1220 self,
1221 obligation.param_env,
1222 obligation.cause.clone(),
1223 obligation.recursion_depth + 1,
1224 tail_field_ty.instantiate(tcx, args_b),
1225 &mut nested,
1226 );
1227
1228 let args =
1231 tcx.mk_args_from_iter(args_a.iter().enumerate().map(|(i, k)| {
1232 if unsizing_params.contains(i as u32) { args_b[i] } else { k }
1233 }));
1234 let new_struct = Ty::new_adt(tcx, def, args);
1235 let InferOk { obligations, .. } = self
1236 .infcx
1237 .at(&obligation.cause, obligation.param_env)
1238 .eq(DefineOpaqueTypes::Yes, target, new_struct)
1239 .map_err(|_| SelectionError::Unimplemented)?;
1240 nested.extend(obligations);
1241
1242 let tail_unsize_obligation = obligation.with(
1244 tcx,
1245 ty::TraitRef::new(
1246 tcx,
1247 obligation.predicate.def_id(),
1248 [source_tail, target_tail],
1249 ),
1250 );
1251 nested.push(tail_unsize_obligation);
1252
1253 ImplSource::Builtin(BuiltinImplSource::Misc, nested)
1254 }
1255
1256 _ => bug!("source: {source}, target: {target}"),
1257 })
1258 }
1259
1260 fn confirm_bikeshed_guaranteed_no_drop_candidate(
1261 &mut self,
1262 obligation: &PolyTraitObligation<'tcx>,
1263 ) -> ImplSource<'tcx, PredicateObligation<'tcx>> {
1264 let mut obligations = thin_vec![];
1265
1266 let tcx = self.tcx();
1267 let self_ty = obligation.predicate.self_ty();
1268 match *self_ty.skip_binder().kind() {
1269 ty::Ref(..) => {}
1271 ty::Adt(def, _) if def.is_manually_drop() => {}
1273 ty::Tuple(tys) => {
1276 obligations.extend(tys.iter().map(|elem_ty| {
1277 obligation.with(
1278 tcx,
1279 self_ty.rebind(ty::TraitRef::new(
1280 tcx,
1281 obligation.predicate.def_id(),
1282 [elem_ty],
1283 )),
1284 )
1285 }));
1286 }
1287 ty::Array(elem_ty, _) => {
1288 obligations.push(obligation.with(
1289 tcx,
1290 self_ty.rebind(ty::TraitRef::new(
1291 tcx,
1292 obligation.predicate.def_id(),
1293 [elem_ty],
1294 )),
1295 ));
1296 }
1297
1298 ty::FnDef(..)
1302 | ty::FnPtr(..)
1303 | ty::Error(_)
1304 | ty::Uint(_)
1305 | ty::Int(_)
1306 | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
1307 | ty::Bool
1308 | ty::Float(_)
1309 | ty::Char
1310 | ty::RawPtr(..)
1311 | ty::Never
1312 | ty::Pat(..)
1313 | ty::Dynamic(..)
1314 | ty::Str
1315 | ty::Slice(_)
1316 | ty::Foreign(..)
1317 | ty::Adt(..)
1318 | ty::Alias(..)
1319 | ty::Param(_)
1320 | ty::Placeholder(..)
1321 | ty::Closure(..)
1322 | ty::CoroutineClosure(..)
1323 | ty::Coroutine(..)
1324 | ty::UnsafeBinder(_)
1325 | ty::CoroutineWitness(..)
1326 | ty::Bound(..) => {
1327 obligations.push(obligation.with(
1328 tcx,
1329 self_ty.map_bound(|ty| {
1330 ty::TraitRef::new(
1331 tcx,
1332 tcx.require_lang_item(LangItem::Copy, obligation.cause.span),
1333 [ty],
1334 )
1335 }),
1336 ));
1337 }
1338
1339 ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
1340 panic!("unexpected type `{self_ty:?}`")
1341 }
1342 }
1343
1344 ImplSource::Builtin(BuiltinImplSource::Misc, obligations)
1345 }
1346}
1347
1348fn pointer_like_goal_for_rpitit<'tcx>(
1358 tcx: TyCtxt<'tcx>,
1359 supertrait: ty::PolyTraitRef<'tcx>,
1360 rpitit_item: DefId,
1361 cause: &ObligationCause<'tcx>,
1362) -> ty::PolyTraitRef<'tcx> {
1363 let mut bound_vars = supertrait.bound_vars().to_vec();
1364
1365 let args = supertrait.skip_binder().args.extend_to(tcx, rpitit_item, |arg, _| match arg.kind {
1366 ty::GenericParamDefKind::Lifetime => {
1367 let kind = ty::BoundRegionKind::Named(arg.def_id, tcx.item_name(arg.def_id));
1368 bound_vars.push(ty::BoundVariableKind::Region(kind));
1369 ty::Region::new_bound(
1370 tcx,
1371 ty::INNERMOST,
1372 ty::BoundRegion { var: ty::BoundVar::from_usize(bound_vars.len() - 1), kind },
1373 )
1374 .into()
1375 }
1376 ty::GenericParamDefKind::Type { .. } | ty::GenericParamDefKind::Const { .. } => {
1377 unreachable!()
1378 }
1379 });
1380
1381 ty::Binder::bind_with_vars(
1382 ty::TraitRef::new(
1383 tcx,
1384 tcx.require_lang_item(LangItem::PointerLike, cause.span),
1385 [Ty::new_projection_from_args(tcx, rpitit_item, args)],
1386 ),
1387 tcx.mk_bound_variable_kinds(&bound_vars),
1388 )
1389}