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::{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 => {
41 let data = self.confirm_builtin_candidate(obligation);
42 ImplSource::Builtin(BuiltinImplSource::Misc, data)
43 }
44
45 BuiltinCandidate => {
46 let data = self.confirm_builtin_candidate(obligation);
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 #[instrument(level = "debug", skip(self), ret)]
253 fn confirm_builtin_candidate(
254 &mut self,
255 obligation: &PolyTraitObligation<'tcx>,
256 ) -> PredicateObligations<'tcx> {
257 debug!(?obligation, "confirm_builtin_candidate");
258 let tcx = self.tcx();
259 let trait_def = obligation.predicate.def_id();
260 let self_ty = self.infcx.shallow_resolve(
261 self.infcx.enter_forall_and_leak_universe(obligation.predicate.self_ty()),
262 );
263 let types = match tcx.as_lang_item(trait_def) {
264 Some(LangItem::Sized) => self.sizedness_conditions(self_ty, SizedTraitKind::Sized),
265 Some(LangItem::MetaSized) => {
266 self.sizedness_conditions(self_ty, SizedTraitKind::MetaSized)
267 }
268 Some(LangItem::PointeeSized) => {
269 bug!("`PointeeSized` is removing during lowering");
270 }
271 Some(LangItem::Copy | LangItem::Clone) => self.copy_clone_conditions(self_ty),
272 Some(LangItem::FusedIterator) => {
273 if self.coroutine_is_gen(self_ty) {
274 ty::Binder::dummy(vec![])
275 } else {
276 unreachable!("tried to assemble `FusedIterator` for non-gen coroutine");
277 }
278 }
279 Some(
280 LangItem::Destruct
281 | LangItem::DiscriminantKind
282 | LangItem::FnPtrTrait
283 | LangItem::PointeeTrait
284 | LangItem::Tuple
285 | LangItem::Unpin,
286 ) => ty::Binder::dummy(vec![]),
287 other => bug!("unexpected builtin trait {trait_def:?} ({other:?})"),
288 };
289 let types = self.infcx.enter_forall_and_leak_universe(types);
290
291 let cause = obligation.derived_cause(ObligationCauseCode::BuiltinDerived);
292 self.collect_predicates_for_types(
293 obligation.param_env,
294 cause,
295 obligation.recursion_depth + 1,
296 trait_def,
297 types,
298 )
299 }
300
301 #[instrument(level = "debug", skip(self))]
302 fn confirm_transmutability_candidate(
303 &mut self,
304 obligation: &PolyTraitObligation<'tcx>,
305 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
306 use rustc_transmute::{Answer, Assume, Condition};
307
308 #[instrument(level = "debug", skip(tcx, obligation))]
310 fn flatten_answer_tree<'tcx>(
311 tcx: TyCtxt<'tcx>,
312 obligation: &PolyTraitObligation<'tcx>,
313 cond: Condition<Region<'tcx>, Ty<'tcx>>,
314 assume: Assume,
315 ) -> PredicateObligations<'tcx> {
316 match cond {
317 Condition::IfAll(conds) | Condition::IfAny(conds) => conds
320 .into_iter()
321 .flat_map(|cond| flatten_answer_tree(tcx, obligation, cond, assume))
322 .collect(),
323 Condition::Immutable { ty } => {
324 let trait_ref = ty::TraitRef::new(
325 tcx,
326 tcx.require_lang_item(LangItem::Freeze, obligation.cause.span),
327 [ty::GenericArg::from(ty)],
328 );
329 thin_vec![Obligation::with_depth(
330 tcx,
331 obligation.cause.clone(),
332 obligation.recursion_depth + 1,
333 obligation.param_env,
334 trait_ref,
335 )]
336 }
337 Condition::Outlives { long, short } => {
338 let outlives = ty::OutlivesPredicate(long, short);
339 thin_vec![Obligation::with_depth(
340 tcx,
341 obligation.cause.clone(),
342 obligation.recursion_depth + 1,
343 obligation.param_env,
344 outlives,
345 )]
346 }
347 Condition::Transmutable { src, dst } => {
348 let transmute_trait = obligation.predicate.def_id();
349 let assume = obligation.predicate.skip_binder().trait_ref.args.const_at(2);
350 let trait_ref = ty::TraitRef::new(
351 tcx,
352 transmute_trait,
353 [
354 ty::GenericArg::from(dst),
355 ty::GenericArg::from(src),
356 ty::GenericArg::from(assume),
357 ],
358 );
359 thin_vec![Obligation::with_depth(
360 tcx,
361 obligation.cause.clone(),
362 obligation.recursion_depth + 1,
363 obligation.param_env,
364 trait_ref,
365 )]
366 }
367 }
368 }
369
370 let predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
371
372 let mut assume = predicate.trait_ref.args.const_at(2);
373 if self.tcx().features().generic_const_exprs() {
374 assume = crate::traits::evaluate_const(self.infcx, assume, obligation.param_env)
375 }
376 let Some(assume) = rustc_transmute::Assume::from_const(self.infcx.tcx, assume) else {
377 return Err(SelectionError::Unimplemented);
378 };
379
380 let dst = predicate.trait_ref.args.type_at(0);
381 let src = predicate.trait_ref.args.type_at(1);
382
383 debug!(?src, ?dst);
384 let mut transmute_env = rustc_transmute::TransmuteTypeEnv::new(self.infcx.tcx);
385 let maybe_transmutable =
386 transmute_env.is_transmutable(rustc_transmute::Types { dst, src }, assume);
387
388 let fully_flattened = match maybe_transmutable {
389 Answer::No(_) => Err(SelectionError::Unimplemented)?,
390 Answer::If(cond) => flatten_answer_tree(self.tcx(), obligation, cond, assume),
391 Answer::Yes => PredicateObligations::new(),
392 };
393
394 debug!(?fully_flattened);
395 Ok(fully_flattened)
396 }
397
398 fn confirm_auto_impl_candidate(
404 &mut self,
405 obligation: &PolyTraitObligation<'tcx>,
406 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
407 ensure_sufficient_stack(|| {
408 assert_eq!(obligation.predicate.polarity(), ty::PredicatePolarity::Positive);
409
410 let self_ty =
411 obligation.predicate.self_ty().map_bound(|ty| self.infcx.shallow_resolve(ty));
412 let self_ty = self.infcx.enter_forall_and_leak_universe(self_ty);
413
414 let constituents = self.constituent_types_for_auto_trait(self_ty)?;
415 let constituents = self.infcx.enter_forall_and_leak_universe(constituents);
416
417 let cause = obligation.derived_cause(ObligationCauseCode::BuiltinDerived);
418 let mut obligations = self.collect_predicates_for_types(
419 obligation.param_env,
420 cause.clone(),
421 obligation.recursion_depth + 1,
422 obligation.predicate.def_id(),
423 constituents.types,
424 );
425
426 if self.tcx().sess.opts.unstable_opts.higher_ranked_assumptions {
430 for assumption in constituents.assumptions {
434 let assumption = normalize_with_depth_to(
435 self,
436 obligation.param_env,
437 cause.clone(),
438 obligation.recursion_depth + 1,
439 assumption,
440 &mut obligations,
441 );
442 self.infcx.register_region_assumption(assumption);
443 }
444 }
445
446 Ok(obligations)
447 })
448 }
449
450 fn confirm_impl_candidate(
451 &mut self,
452 obligation: &PolyTraitObligation<'tcx>,
453 impl_def_id: DefId,
454 ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
455 debug!(?obligation, ?impl_def_id, "confirm_impl_candidate");
456
457 let args = self.rematch_impl(impl_def_id, obligation);
460 debug!(?args, "impl args");
461 ensure_sufficient_stack(|| {
462 self.vtable_impl(
463 impl_def_id,
464 args,
465 &obligation.cause,
466 obligation.recursion_depth + 1,
467 obligation.param_env,
468 obligation.predicate,
469 )
470 })
471 }
472
473 fn vtable_impl(
474 &mut self,
475 impl_def_id: DefId,
476 args: Normalized<'tcx, GenericArgsRef<'tcx>>,
477 cause: &ObligationCause<'tcx>,
478 recursion_depth: usize,
479 param_env: ty::ParamEnv<'tcx>,
480 parent_trait_pred: ty::Binder<'tcx, ty::TraitPredicate<'tcx>>,
481 ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
482 debug!(?impl_def_id, ?args, ?recursion_depth, "vtable_impl");
483
484 let mut impl_obligations = self.impl_or_trait_obligations(
485 cause,
486 recursion_depth,
487 param_env,
488 impl_def_id,
489 args.value,
490 parent_trait_pred,
491 );
492
493 debug!(?impl_obligations, "vtable_impl");
494
495 impl_obligations.extend(args.obligations);
501
502 ImplSourceUserDefinedData { impl_def_id, args: args.value, nested: impl_obligations }
503 }
504
505 fn confirm_object_candidate(
506 &mut self,
507 obligation: &PolyTraitObligation<'tcx>,
508 index: usize,
509 ) -> Result<ImplSource<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
510 let tcx = self.tcx();
511 debug!(?obligation, ?index, "confirm_object_candidate");
512
513 let trait_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
514 let self_ty = self.infcx.shallow_resolve(trait_predicate.self_ty());
515 let ty::Dynamic(data, ..) = *self_ty.kind() else {
516 span_bug!(obligation.cause.span, "object candidate with non-object");
517 };
518
519 let object_trait_ref = data.principal().unwrap_or_else(|| {
520 span_bug!(obligation.cause.span, "object candidate with no principal")
521 });
522 let object_trait_ref = self.infcx.instantiate_binder_with_fresh_vars(
523 obligation.cause.span,
524 BoundRegionConversionTime::HigherRankedType,
525 object_trait_ref,
526 );
527 let object_trait_ref = object_trait_ref.with_self_ty(self.tcx(), self_ty);
528
529 let mut nested = PredicateObligations::new();
530
531 let mut supertraits = util::supertraits(tcx, ty::Binder::dummy(object_trait_ref));
532 let unnormalized_upcast_trait_ref =
533 supertraits.nth(index).expect("supertraits iterator no longer has as many elements");
534
535 let upcast_trait_ref = self.infcx.instantiate_binder_with_fresh_vars(
536 obligation.cause.span,
537 BoundRegionConversionTime::HigherRankedType,
538 unnormalized_upcast_trait_ref,
539 );
540 let upcast_trait_ref = normalize_with_depth_to(
541 self,
542 obligation.param_env,
543 obligation.cause.clone(),
544 obligation.recursion_depth + 1,
545 upcast_trait_ref,
546 &mut nested,
547 );
548
549 nested.extend(
550 self.infcx
551 .at(&obligation.cause, obligation.param_env)
552 .eq(DefineOpaqueTypes::No, trait_predicate.trait_ref, upcast_trait_ref)
553 .map(|InferOk { obligations, .. }| obligations)
554 .map_err(|_| SelectionError::Unimplemented)?,
555 );
556
557 for (supertrait, _) in tcx
560 .explicit_super_predicates_of(trait_predicate.def_id())
561 .iter_instantiated_copied(tcx, trait_predicate.trait_ref.args)
562 {
563 let normalized_supertrait = normalize_with_depth_to(
564 self,
565 obligation.param_env,
566 obligation.cause.clone(),
567 obligation.recursion_depth + 1,
568 supertrait,
569 &mut nested,
570 );
571 nested.push(obligation.with(tcx, normalized_supertrait));
572 }
573
574 let assoc_types: Vec<_> = tcx
575 .associated_items(trait_predicate.def_id())
576 .in_definition_order()
577 .filter(|item| !tcx.generics_require_sized_self(item.def_id))
580 .filter_map(|item| if item.is_type() { Some(item.def_id) } else { None })
581 .collect();
582
583 for assoc_type in assoc_types {
584 let defs: &ty::Generics = tcx.generics_of(assoc_type);
585
586 if !defs.own_params.is_empty() {
587 tcx.dcx().span_delayed_bug(
588 obligation.cause.span,
589 "GATs in trait object shouldn't have been considered",
590 );
591 return Err(SelectionError::TraitDynIncompatible(trait_predicate.trait_ref.def_id));
592 }
593
594 for bound in self.tcx().item_bounds(assoc_type).transpose_iter() {
598 let normalized_bound = normalize_with_depth_to(
599 self,
600 obligation.param_env,
601 obligation.cause.clone(),
602 obligation.recursion_depth + 1,
603 bound.instantiate(tcx, trait_predicate.trait_ref.args),
604 &mut nested,
605 );
606 nested.push(obligation.with(tcx, normalized_bound));
607 }
608 }
609
610 debug!(?nested, "object nested obligations");
611
612 Ok(ImplSource::Builtin(BuiltinImplSource::Object(index), nested))
613 }
614
615 fn confirm_fn_pointer_candidate(
616 &mut self,
617 obligation: &PolyTraitObligation<'tcx>,
618 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
619 debug!(?obligation, "confirm_fn_pointer_candidate");
620 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
621 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
622
623 let tcx = self.tcx();
624 let sig = self_ty.fn_sig(tcx);
625 let trait_ref = closure_trait_ref_and_return_type(
626 tcx,
627 obligation.predicate.def_id(),
628 self_ty,
629 sig,
630 util::TupleArgumentsFlag::Yes,
631 )
632 .map_bound(|(trait_ref, _)| trait_ref);
633
634 let mut nested =
635 self.equate_trait_refs(obligation.with(tcx, placeholder_predicate), trait_ref)?;
636 let cause = obligation.derived_cause(ObligationCauseCode::BuiltinDerived);
637
638 let output_ty = self.infcx.enter_forall_and_leak_universe(sig.output());
640 let output_ty = normalize_with_depth_to(
641 self,
642 obligation.param_env,
643 cause.clone(),
644 obligation.recursion_depth,
645 output_ty,
646 &mut nested,
647 );
648 let tr = ty::TraitRef::new(
649 self.tcx(),
650 self.tcx().require_lang_item(LangItem::Sized, cause.span),
651 [output_ty],
652 );
653 nested.push(Obligation::new(self.infcx.tcx, cause, obligation.param_env, tr));
654
655 Ok(nested)
656 }
657
658 fn confirm_trait_alias_candidate(
659 &mut self,
660 obligation: &PolyTraitObligation<'tcx>,
661 ) -> PredicateObligations<'tcx> {
662 debug!(?obligation, "confirm_trait_alias_candidate");
663
664 let predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
665 let trait_ref = predicate.trait_ref;
666 let trait_def_id = trait_ref.def_id;
667 let args = trait_ref.args;
668
669 let trait_obligations = self.impl_or_trait_obligations(
670 &obligation.cause,
671 obligation.recursion_depth,
672 obligation.param_env,
673 trait_def_id,
674 args,
675 obligation.predicate,
676 );
677
678 debug!(?trait_def_id, ?trait_obligations, "trait alias obligations");
679
680 trait_obligations
681 }
682
683 fn confirm_coroutine_candidate(
684 &mut self,
685 obligation: &PolyTraitObligation<'tcx>,
686 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
687 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
688 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
689 let ty::Coroutine(coroutine_def_id, args) = *self_ty.kind() else {
690 bug!("closure candidate for non-closure {:?}", obligation);
691 };
692
693 debug!(?obligation, ?coroutine_def_id, ?args, "confirm_coroutine_candidate");
694
695 let coroutine_sig = args.as_coroutine().sig();
696
697 let (trait_ref, _, _) = super::util::coroutine_trait_ref_and_outputs(
698 self.tcx(),
699 obligation.predicate.def_id(),
700 self_ty,
701 coroutine_sig,
702 );
703
704 let nested = self.equate_trait_refs(
705 obligation.with(self.tcx(), placeholder_predicate),
706 ty::Binder::dummy(trait_ref),
707 )?;
708 debug!(?trait_ref, ?nested, "coroutine candidate obligations");
709
710 Ok(nested)
711 }
712
713 fn confirm_future_candidate(
714 &mut self,
715 obligation: &PolyTraitObligation<'tcx>,
716 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
717 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
718 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
719 let ty::Coroutine(coroutine_def_id, args) = *self_ty.kind() else {
720 bug!("closure candidate for non-closure {:?}", obligation);
721 };
722
723 debug!(?obligation, ?coroutine_def_id, ?args, "confirm_future_candidate");
724
725 let coroutine_sig = args.as_coroutine().sig();
726
727 let (trait_ref, _) = super::util::future_trait_ref_and_outputs(
728 self.tcx(),
729 obligation.predicate.def_id(),
730 self_ty,
731 coroutine_sig,
732 );
733
734 let nested = self.equate_trait_refs(
735 obligation.with(self.tcx(), placeholder_predicate),
736 ty::Binder::dummy(trait_ref),
737 )?;
738 debug!(?trait_ref, ?nested, "future candidate obligations");
739
740 Ok(nested)
741 }
742
743 fn confirm_iterator_candidate(
744 &mut self,
745 obligation: &PolyTraitObligation<'tcx>,
746 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
747 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
748 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
749 let ty::Coroutine(coroutine_def_id, args) = *self_ty.kind() else {
750 bug!("closure candidate for non-closure {:?}", obligation);
751 };
752
753 debug!(?obligation, ?coroutine_def_id, ?args, "confirm_iterator_candidate");
754
755 let gen_sig = args.as_coroutine().sig();
756
757 let (trait_ref, _) = super::util::iterator_trait_ref_and_outputs(
758 self.tcx(),
759 obligation.predicate.def_id(),
760 self_ty,
761 gen_sig,
762 );
763
764 let nested = self.equate_trait_refs(
765 obligation.with(self.tcx(), placeholder_predicate),
766 ty::Binder::dummy(trait_ref),
767 )?;
768 debug!(?trait_ref, ?nested, "iterator candidate obligations");
769
770 Ok(nested)
771 }
772
773 fn confirm_async_iterator_candidate(
774 &mut self,
775 obligation: &PolyTraitObligation<'tcx>,
776 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
777 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
778 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
779 let ty::Coroutine(coroutine_def_id, args) = *self_ty.kind() else {
780 bug!("closure candidate for non-closure {:?}", obligation);
781 };
782
783 debug!(?obligation, ?coroutine_def_id, ?args, "confirm_async_iterator_candidate");
784
785 let gen_sig = args.as_coroutine().sig();
786
787 let (trait_ref, _) = super::util::async_iterator_trait_ref_and_outputs(
788 self.tcx(),
789 obligation.predicate.def_id(),
790 self_ty,
791 gen_sig,
792 );
793
794 let nested = self.equate_trait_refs(
795 obligation.with(self.tcx(), placeholder_predicate),
796 ty::Binder::dummy(trait_ref),
797 )?;
798 debug!(?trait_ref, ?nested, "iterator candidate obligations");
799
800 Ok(nested)
801 }
802
803 #[instrument(skip(self), level = "debug")]
804 fn confirm_closure_candidate(
805 &mut self,
806 obligation: &PolyTraitObligation<'tcx>,
807 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
808 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
809 let self_ty: Ty<'_> = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
810
811 let trait_ref = match *self_ty.kind() {
812 ty::Closure(..) => {
813 self.closure_trait_ref_unnormalized(self_ty, obligation.predicate.def_id())
814 }
815 ty::CoroutineClosure(_, args) => {
816 args.as_coroutine_closure().coroutine_closure_sig().map_bound(|sig| {
817 ty::TraitRef::new(
818 self.tcx(),
819 obligation.predicate.def_id(),
820 [self_ty, sig.tupled_inputs_ty],
821 )
822 })
823 }
824 _ => {
825 bug!("closure candidate for non-closure {:?}", obligation);
826 }
827 };
828
829 self.equate_trait_refs(obligation.with(self.tcx(), placeholder_predicate), trait_ref)
830 }
831
832 #[instrument(skip(self), level = "debug")]
833 fn confirm_async_closure_candidate(
834 &mut self,
835 obligation: &PolyTraitObligation<'tcx>,
836 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
837 let placeholder_predicate = self.infcx.enter_forall_and_leak_universe(obligation.predicate);
838 let self_ty = self.infcx.shallow_resolve(placeholder_predicate.self_ty());
839
840 let tcx = self.tcx();
841
842 let mut nested = PredicateObligations::new();
843 let (trait_ref, kind_ty) = match *self_ty.kind() {
844 ty::CoroutineClosure(_, args) => {
845 let args = args.as_coroutine_closure();
846 let trait_ref = args.coroutine_closure_sig().map_bound(|sig| {
847 ty::TraitRef::new(
848 self.tcx(),
849 obligation.predicate.def_id(),
850 [self_ty, sig.tupled_inputs_ty],
851 )
852 });
853
854 (trait_ref, args.kind_ty())
858 }
859 ty::FnDef(..) | ty::FnPtr(..) => {
860 let sig = self_ty.fn_sig(tcx);
861 let trait_ref = sig.map_bound(|sig| {
862 ty::TraitRef::new(
863 self.tcx(),
864 obligation.predicate.def_id(),
865 [self_ty, Ty::new_tup(tcx, sig.inputs())],
866 )
867 });
868
869 let future_trait_def_id =
871 tcx.require_lang_item(LangItem::Future, obligation.cause.span);
872 nested.push(obligation.with(
873 tcx,
874 sig.output().map_bound(|output_ty| {
875 ty::TraitRef::new(tcx, future_trait_def_id, [output_ty])
876 }),
877 ));
878 let sized_trait_def_id =
879 tcx.require_lang_item(LangItem::Sized, obligation.cause.span);
880 nested.push(obligation.with(
881 tcx,
882 sig.output().map_bound(|output_ty| {
883 ty::TraitRef::new(tcx, sized_trait_def_id, [output_ty])
884 }),
885 ));
886
887 (trait_ref, Ty::from_closure_kind(tcx, ty::ClosureKind::Fn))
888 }
889 ty::Closure(_, args) => {
890 let args = args.as_closure();
891 let sig = args.sig();
892 let trait_ref = sig.map_bound(|sig| {
893 ty::TraitRef::new(
894 self.tcx(),
895 obligation.predicate.def_id(),
896 [self_ty, sig.inputs()[0]],
897 )
898 });
899
900 let future_trait_def_id =
902 tcx.require_lang_item(LangItem::Future, obligation.cause.span);
903 let placeholder_output_ty = self.infcx.enter_forall_and_leak_universe(sig.output());
904 nested.push(obligation.with(
905 tcx,
906 ty::TraitRef::new(tcx, future_trait_def_id, [placeholder_output_ty]),
907 ));
908 let sized_trait_def_id =
909 tcx.require_lang_item(LangItem::Sized, obligation.cause.span);
910 nested.push(obligation.with(
911 tcx,
912 sig.output().map_bound(|output_ty| {
913 ty::TraitRef::new(tcx, sized_trait_def_id, [output_ty])
914 }),
915 ));
916
917 (trait_ref, args.kind_ty())
918 }
919 _ => bug!("expected callable type for AsyncFn candidate"),
920 };
921
922 nested.extend(
923 self.equate_trait_refs(obligation.with(tcx, placeholder_predicate), trait_ref)?,
924 );
925
926 let goal_kind =
927 self.tcx().async_fn_trait_kind_from_def_id(obligation.predicate.def_id()).unwrap();
928
929 if let Some(closure_kind) = self.infcx.shallow_resolve(kind_ty).to_opt_closure_kind() {
933 if !closure_kind.extends(goal_kind) {
934 return Err(SelectionError::Unimplemented);
935 }
936 } else {
937 nested.push(Obligation::new(
938 self.tcx(),
939 obligation.derived_cause(ObligationCauseCode::BuiltinDerived),
940 obligation.param_env,
941 ty::TraitRef::new(
942 self.tcx(),
943 self.tcx()
944 .require_lang_item(LangItem::AsyncFnKindHelper, obligation.cause.span),
945 [kind_ty, Ty::from_closure_kind(self.tcx(), goal_kind)],
946 ),
947 ));
948 }
949
950 Ok(nested)
951 }
952
953 #[instrument(skip(self), level = "trace")]
979 fn equate_trait_refs(
980 &mut self,
981 obligation: TraitObligation<'tcx>,
982 found_trait_ref: ty::PolyTraitRef<'tcx>,
983 ) -> Result<PredicateObligations<'tcx>, SelectionError<'tcx>> {
984 let found_trait_ref = self.infcx.instantiate_binder_with_fresh_vars(
985 obligation.cause.span,
986 BoundRegionConversionTime::HigherRankedType,
987 found_trait_ref,
988 );
989 let Normalized { obligations: nested, value: (obligation_trait_ref, found_trait_ref) } =
991 ensure_sufficient_stack(|| {
992 normalize_with_depth(
993 self,
994 obligation.param_env,
995 obligation.cause.clone(),
996 obligation.recursion_depth + 1,
997 (obligation.predicate.trait_ref, found_trait_ref),
998 )
999 });
1000
1001 self.infcx
1003 .at(&obligation.cause, obligation.param_env)
1004 .eq(DefineOpaqueTypes::Yes, obligation_trait_ref, found_trait_ref)
1005 .map(|InferOk { mut obligations, .. }| {
1006 obligations.extend(nested);
1007 obligations
1008 })
1009 .map_err(|terr| {
1010 SelectionError::SignatureMismatch(Box::new(SignatureMismatchData {
1011 expected_trait_ref: obligation_trait_ref,
1012 found_trait_ref,
1013 terr,
1014 }))
1015 })
1016 }
1017
1018 fn confirm_trait_upcasting_unsize_candidate(
1019 &mut self,
1020 obligation: &PolyTraitObligation<'tcx>,
1021 idx: usize,
1022 ) -> Result<ImplSource<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
1023 let tcx = self.tcx();
1024
1025 let predicate = obligation.predicate.no_bound_vars().unwrap();
1028 let a_ty = self.infcx.shallow_resolve(predicate.self_ty());
1029 let b_ty = self.infcx.shallow_resolve(predicate.trait_ref.args.type_at(1));
1030
1031 let ty::Dynamic(a_data, a_region) = *a_ty.kind() else {
1032 bug!("expected `dyn` type in `confirm_trait_upcasting_unsize_candidate`")
1033 };
1034 let ty::Dynamic(b_data, b_region) = *b_ty.kind() else {
1035 bug!("expected `dyn` type in `confirm_trait_upcasting_unsize_candidate`")
1036 };
1037
1038 let source_principal = a_data.principal().unwrap().with_self_ty(tcx, a_ty);
1039 let unnormalized_upcast_principal =
1040 util::supertraits(tcx, source_principal).nth(idx).unwrap();
1041
1042 let nested = self
1043 .match_upcast_principal(
1044 obligation,
1045 unnormalized_upcast_principal,
1046 a_data,
1047 b_data,
1048 a_region,
1049 b_region,
1050 )?
1051 .expect("did not expect ambiguity during confirmation");
1052
1053 Ok(ImplSource::Builtin(BuiltinImplSource::TraitUpcasting(idx), nested))
1054 }
1055
1056 fn confirm_builtin_unsize_candidate(
1057 &mut self,
1058 obligation: &PolyTraitObligation<'tcx>,
1059 ) -> Result<ImplSource<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
1060 let tcx = self.tcx();
1061
1062 let source = self.infcx.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap());
1065 let target = obligation.predicate.skip_binder().trait_ref.args.type_at(1);
1066 let target = self.infcx.shallow_resolve(target);
1067 debug!(?source, ?target, "confirm_builtin_unsize_candidate");
1068
1069 Ok(match (source.kind(), target.kind()) {
1070 (&ty::Dynamic(data_a, r_a), &ty::Dynamic(data_b, r_b)) => {
1072 let existential_predicates = if data_b.principal().is_some() {
1075 tcx.mk_poly_existential_predicates_from_iter(
1076 data_a
1077 .principal()
1078 .map(|b| b.map_bound(ty::ExistentialPredicate::Trait))
1079 .into_iter()
1080 .chain(
1081 data_a
1082 .projection_bounds()
1083 .map(|b| b.map_bound(ty::ExistentialPredicate::Projection)),
1084 )
1085 .chain(
1086 data_b
1087 .auto_traits()
1088 .map(ty::ExistentialPredicate::AutoTrait)
1089 .map(ty::Binder::dummy),
1090 ),
1091 )
1092 } else {
1093 tcx.mk_poly_existential_predicates_from_iter(
1098 data_b
1099 .auto_traits()
1100 .map(ty::ExistentialPredicate::AutoTrait)
1101 .map(ty::Binder::dummy),
1102 )
1103 };
1104 let source_trait = Ty::new_dynamic(tcx, existential_predicates, r_b);
1105
1106 let InferOk { mut obligations, .. } = self
1109 .infcx
1110 .at(&obligation.cause, obligation.param_env)
1111 .sup(DefineOpaqueTypes::Yes, target, source_trait)
1112 .map_err(|_| SelectionError::Unimplemented)?;
1113
1114 let outlives = ty::OutlivesPredicate(r_a, r_b);
1116 obligations.push(Obligation::with_depth(
1117 tcx,
1118 obligation.cause.clone(),
1119 obligation.recursion_depth + 1,
1120 obligation.param_env,
1121 obligation.predicate.rebind(outlives),
1122 ));
1123
1124 ImplSource::Builtin(BuiltinImplSource::Misc, obligations)
1125 }
1126
1127 (_, &ty::Dynamic(data, r)) => {
1129 let mut object_dids = data.auto_traits().chain(data.principal_def_id());
1130 if let Some(did) = object_dids.find(|did| !tcx.is_dyn_compatible(*did)) {
1131 return Err(SelectionError::TraitDynIncompatible(did));
1132 }
1133
1134 let predicate_to_obligation = |predicate| {
1135 Obligation::with_depth(
1136 tcx,
1137 obligation.cause.clone(),
1138 obligation.recursion_depth + 1,
1139 obligation.param_env,
1140 predicate,
1141 )
1142 };
1143
1144 let mut nested: PredicateObligations<'_> = data
1151 .iter()
1152 .map(|predicate| predicate_to_obligation(predicate.with_self_ty(tcx, source)))
1153 .collect();
1154
1155 let tr = ty::TraitRef::new(
1157 tcx,
1158 tcx.require_lang_item(LangItem::Sized, obligation.cause.span),
1159 [source],
1160 );
1161 nested.push(predicate_to_obligation(tr.upcast(tcx)));
1162
1163 let outlives = ty::OutlivesPredicate(source, r);
1166 nested.push(predicate_to_obligation(
1167 ty::ClauseKind::TypeOutlives(outlives).upcast(tcx),
1168 ));
1169
1170 ImplSource::Builtin(BuiltinImplSource::Misc, nested)
1171 }
1172
1173 (&ty::Array(a, _), &ty::Slice(b)) => {
1175 let InferOk { obligations, .. } = self
1176 .infcx
1177 .at(&obligation.cause, obligation.param_env)
1178 .eq(DefineOpaqueTypes::Yes, b, a)
1179 .map_err(|_| SelectionError::Unimplemented)?;
1180
1181 ImplSource::Builtin(BuiltinImplSource::Misc, obligations)
1182 }
1183
1184 (&ty::Adt(def, args_a), &ty::Adt(_, args_b)) => {
1186 let unsizing_params = tcx.unsizing_params_for_adt(def.did());
1187 if unsizing_params.is_empty() {
1188 return Err(SelectionError::Unimplemented);
1189 }
1190
1191 let tail_field = def.non_enum_variant().tail();
1192 let tail_field_ty = tcx.type_of(tail_field.did);
1193
1194 let mut nested = PredicateObligations::new();
1195
1196 let source_tail = normalize_with_depth_to(
1200 self,
1201 obligation.param_env,
1202 obligation.cause.clone(),
1203 obligation.recursion_depth + 1,
1204 tail_field_ty.instantiate(tcx, args_a),
1205 &mut nested,
1206 );
1207 let target_tail = normalize_with_depth_to(
1208 self,
1209 obligation.param_env,
1210 obligation.cause.clone(),
1211 obligation.recursion_depth + 1,
1212 tail_field_ty.instantiate(tcx, args_b),
1213 &mut nested,
1214 );
1215
1216 let args =
1219 tcx.mk_args_from_iter(args_a.iter().enumerate().map(|(i, k)| {
1220 if unsizing_params.contains(i as u32) { args_b[i] } else { k }
1221 }));
1222 let new_struct = Ty::new_adt(tcx, def, args);
1223 let InferOk { obligations, .. } = self
1224 .infcx
1225 .at(&obligation.cause, obligation.param_env)
1226 .eq(DefineOpaqueTypes::Yes, target, new_struct)
1227 .map_err(|_| SelectionError::Unimplemented)?;
1228 nested.extend(obligations);
1229
1230 let tail_unsize_obligation = obligation.with(
1232 tcx,
1233 ty::TraitRef::new(
1234 tcx,
1235 obligation.predicate.def_id(),
1236 [source_tail, target_tail],
1237 ),
1238 );
1239 nested.push(tail_unsize_obligation);
1240
1241 ImplSource::Builtin(BuiltinImplSource::Misc, nested)
1242 }
1243
1244 _ => bug!("source: {source}, target: {target}"),
1245 })
1246 }
1247
1248 fn confirm_bikeshed_guaranteed_no_drop_candidate(
1249 &mut self,
1250 obligation: &PolyTraitObligation<'tcx>,
1251 ) -> ImplSource<'tcx, PredicateObligation<'tcx>> {
1252 let mut obligations = thin_vec![];
1253
1254 let tcx = self.tcx();
1255 let self_ty = obligation.predicate.self_ty();
1256 match *self_ty.skip_binder().kind() {
1257 ty::Ref(..) => {}
1259 ty::Adt(def, _) if def.is_manually_drop() => {}
1261 ty::Tuple(tys) => {
1264 obligations.extend(tys.iter().map(|elem_ty| {
1265 obligation.with(
1266 tcx,
1267 self_ty.rebind(ty::TraitRef::new(
1268 tcx,
1269 obligation.predicate.def_id(),
1270 [elem_ty],
1271 )),
1272 )
1273 }));
1274 }
1275 ty::Array(elem_ty, _) => {
1276 obligations.push(obligation.with(
1277 tcx,
1278 self_ty.rebind(ty::TraitRef::new(
1279 tcx,
1280 obligation.predicate.def_id(),
1281 [elem_ty],
1282 )),
1283 ));
1284 }
1285
1286 ty::FnDef(..)
1290 | ty::FnPtr(..)
1291 | ty::Error(_)
1292 | ty::Uint(_)
1293 | ty::Int(_)
1294 | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
1295 | ty::Bool
1296 | ty::Float(_)
1297 | ty::Char
1298 | ty::RawPtr(..)
1299 | ty::Never
1300 | ty::Pat(..)
1301 | ty::Dynamic(..)
1302 | ty::Str
1303 | ty::Slice(_)
1304 | ty::Foreign(..)
1305 | ty::Adt(..)
1306 | ty::Alias(..)
1307 | ty::Param(_)
1308 | ty::Placeholder(..)
1309 | ty::Closure(..)
1310 | ty::CoroutineClosure(..)
1311 | ty::Coroutine(..)
1312 | ty::UnsafeBinder(_)
1313 | ty::CoroutineWitness(..)
1314 | ty::Bound(..) => {
1315 obligations.push(obligation.with(
1316 tcx,
1317 self_ty.map_bound(|ty| {
1318 ty::TraitRef::new(
1319 tcx,
1320 tcx.require_lang_item(LangItem::Copy, obligation.cause.span),
1321 [ty],
1322 )
1323 }),
1324 ));
1325 }
1326
1327 ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
1328 panic!("unexpected type `{self_ty:?}`")
1329 }
1330 }
1331
1332 ImplSource::Builtin(BuiltinImplSource::Misc, obligations)
1333 }
1334}