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