1use std::ops::ControlFlow;
4
5use rustc_data_structures::sso::SsoHashSet;
6use rustc_data_structures::stack::ensure_sufficient_stack;
7use rustc_errors::ErrorGuaranteed;
8use rustc_hir::lang_items::LangItem;
9use rustc_infer::infer::DefineOpaqueTypes;
10use rustc_infer::infer::resolve::OpportunisticRegionResolver;
11use rustc_infer::traits::{ObligationCauseCode, PredicateObligations};
12use rustc_middle::traits::select::OverflowError;
13use rustc_middle::traits::{BuiltinImplSource, ImplSource, ImplSourceUserDefinedData};
14use rustc_middle::ty::fast_reject::DeepRejectCtxt;
15use rustc_middle::ty::{
16 self, Term, Ty, TyCtxt, TypeFoldable, TypeVisitableExt, TypingMode, Upcast,
17};
18use rustc_middle::{bug, span_bug};
19use rustc_span::sym;
20use tracing::{debug, instrument};
21
22use super::{
23 MismatchedProjectionTypes, Normalized, NormalizedTerm, Obligation, ObligationCause,
24 PredicateObligation, ProjectionCacheEntry, ProjectionCacheKey, Selection, SelectionContext,
25 SelectionError, specialization_graph, translate_args, util,
26};
27use crate::errors::InherentProjectionNormalizationOverflow;
28use crate::infer::{BoundRegionConversionTime, InferOk};
29use crate::traits::normalize::{normalize_with_depth, normalize_with_depth_to};
30use crate::traits::query::evaluate_obligation::InferCtxtExt as _;
31use crate::traits::select::ProjectionMatchesProjection;
32
33pub type PolyProjectionObligation<'tcx> = Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
34
35pub type ProjectionObligation<'tcx> = Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
36
37pub type ProjectionTermObligation<'tcx> = Obligation<'tcx, ty::AliasTerm<'tcx>>;
38
39pub(super) struct InProgress;
40
41#[derive(Debug)]
43pub enum ProjectionError<'tcx> {
44 TooManyCandidates,
46
47 TraitSelectionError(SelectionError<'tcx>),
49}
50
51#[derive(PartialEq, Eq, Debug)]
52enum ProjectionCandidate<'tcx> {
53 ParamEnv(ty::PolyProjectionPredicate<'tcx>),
55
56 TraitDef(ty::PolyProjectionPredicate<'tcx>),
59
60 Object(ty::PolyProjectionPredicate<'tcx>),
62
63 Select(Selection<'tcx>),
65}
66
67enum ProjectionCandidateSet<'tcx> {
68 None,
69 Single(ProjectionCandidate<'tcx>),
70 Ambiguous,
71 Error(SelectionError<'tcx>),
72}
73
74impl<'tcx> ProjectionCandidateSet<'tcx> {
75 fn mark_ambiguous(&mut self) {
76 *self = ProjectionCandidateSet::Ambiguous;
77 }
78
79 fn mark_error(&mut self, err: SelectionError<'tcx>) {
80 *self = ProjectionCandidateSet::Error(err);
81 }
82
83 fn push_candidate(&mut self, candidate: ProjectionCandidate<'tcx>) -> bool {
87 let convert_to_ambiguous;
96
97 match self {
98 ProjectionCandidateSet::None => {
99 *self = ProjectionCandidateSet::Single(candidate);
100 return true;
101 }
102
103 ProjectionCandidateSet::Single(current) => {
104 if current == &candidate {
107 return false;
108 }
109
110 match (current, candidate) {
118 (ProjectionCandidate::ParamEnv(..), ProjectionCandidate::ParamEnv(..)) => {
119 convert_to_ambiguous = ()
120 }
121 (ProjectionCandidate::ParamEnv(..), _) => return false,
122 (_, ProjectionCandidate::ParamEnv(..)) => bug!(
123 "should never prefer non-param-env candidates over param-env candidates"
124 ),
125 (_, _) => convert_to_ambiguous = (),
126 }
127 }
128
129 ProjectionCandidateSet::Ambiguous | ProjectionCandidateSet::Error(..) => {
130 return false;
131 }
132 }
133
134 let () = convert_to_ambiguous;
137 *self = ProjectionCandidateSet::Ambiguous;
138 false
139 }
140}
141
142pub(super) enum ProjectAndUnifyResult<'tcx> {
151 Holds(PredicateObligations<'tcx>),
156 FailedNormalization,
159 Recursive,
162 MismatchedProjectionTypes(MismatchedProjectionTypes<'tcx>),
165}
166
167#[instrument(level = "debug", skip(selcx))]
175pub(super) fn poly_project_and_unify_term<'cx, 'tcx>(
176 selcx: &mut SelectionContext<'cx, 'tcx>,
177 obligation: &PolyProjectionObligation<'tcx>,
178) -> ProjectAndUnifyResult<'tcx> {
179 let infcx = selcx.infcx;
180 let r = infcx.commit_if_ok(|_snapshot| {
181 let placeholder_predicate = infcx.enter_forall_and_leak_universe(obligation.predicate);
182
183 let placeholder_obligation = obligation.with(infcx.tcx, placeholder_predicate);
184 match project_and_unify_term(selcx, &placeholder_obligation) {
185 ProjectAndUnifyResult::MismatchedProjectionTypes(e) => Err(e),
186 other => Ok(other),
187 }
188 });
189
190 match r {
191 Ok(inner) => inner,
192 Err(err) => ProjectAndUnifyResult::MismatchedProjectionTypes(err),
193 }
194}
195
196#[instrument(level = "debug", skip(selcx))]
205fn project_and_unify_term<'cx, 'tcx>(
206 selcx: &mut SelectionContext<'cx, 'tcx>,
207 obligation: &ProjectionObligation<'tcx>,
208) -> ProjectAndUnifyResult<'tcx> {
209 let mut obligations = PredicateObligations::new();
210
211 let infcx = selcx.infcx;
212 let normalized = match opt_normalize_projection_term(
213 selcx,
214 obligation.param_env,
215 obligation.predicate.projection_term,
216 obligation.cause.clone(),
217 obligation.recursion_depth,
218 &mut obligations,
219 ) {
220 Ok(Some(n)) => n,
221 Ok(None) => return ProjectAndUnifyResult::FailedNormalization,
222 Err(InProgress) => return ProjectAndUnifyResult::Recursive,
223 };
224 debug!(?normalized, ?obligations, "project_and_unify_type result");
225 let actual = obligation.predicate.term;
226 let InferOk { value: actual, obligations: new } =
230 selcx.infcx.replace_opaque_types_with_inference_vars(
231 actual,
232 obligation.cause.body_id,
233 obligation.cause.span,
234 obligation.param_env,
235 );
236 obligations.extend(new);
237
238 match infcx.at(&obligation.cause, obligation.param_env).eq(
240 DefineOpaqueTypes::Yes,
241 normalized,
242 actual,
243 ) {
244 Ok(InferOk { obligations: inferred_obligations, value: () }) => {
245 obligations.extend(inferred_obligations);
246 ProjectAndUnifyResult::Holds(obligations)
247 }
248 Err(err) => {
249 debug!("equating types encountered error {:?}", err);
250 ProjectAndUnifyResult::MismatchedProjectionTypes(MismatchedProjectionTypes { err })
251 }
252 }
253}
254
255pub fn normalize_projection_term<'a, 'b, 'tcx>(
263 selcx: &'a mut SelectionContext<'b, 'tcx>,
264 param_env: ty::ParamEnv<'tcx>,
265 alias_term: ty::AliasTerm<'tcx>,
266 cause: ObligationCause<'tcx>,
267 depth: usize,
268 obligations: &mut PredicateObligations<'tcx>,
269) -> Term<'tcx> {
270 opt_normalize_projection_term(selcx, param_env, alias_term, cause.clone(), depth, obligations)
271 .ok()
272 .flatten()
273 .unwrap_or_else(move || {
274 selcx
279 .infcx
280 .projection_term_to_infer(param_env, alias_term, cause, depth + 1, obligations)
281 .into()
282 })
283}
284
285#[instrument(level = "debug", skip(selcx, param_env, cause, obligations))]
297pub(super) fn opt_normalize_projection_term<'a, 'b, 'tcx>(
298 selcx: &'a mut SelectionContext<'b, 'tcx>,
299 param_env: ty::ParamEnv<'tcx>,
300 projection_term: ty::AliasTerm<'tcx>,
301 cause: ObligationCause<'tcx>,
302 depth: usize,
303 obligations: &mut PredicateObligations<'tcx>,
304) -> Result<Option<Term<'tcx>>, InProgress> {
305 let infcx = selcx.infcx;
306 debug_assert!(!selcx.infcx.next_trait_solver());
307 let projection_term = infcx.resolve_vars_if_possible(projection_term);
308 let cache_key = ProjectionCacheKey::new(projection_term, param_env);
309
310 let cache_entry = infcx.inner.borrow_mut().projection_cache().try_start(cache_key);
318 match cache_entry {
319 Ok(()) => debug!("no cache"),
320 Err(ProjectionCacheEntry::Ambiguous) => {
321 debug!("found cache entry: ambiguous");
325 return Ok(None);
326 }
327 Err(ProjectionCacheEntry::InProgress) => {
328 debug!("found cache entry: in-progress");
337
338 infcx.inner.borrow_mut().projection_cache().recur(cache_key);
342 return Err(InProgress);
343 }
344 Err(ProjectionCacheEntry::Recur) => {
345 debug!("recur cache");
346 return Err(InProgress);
347 }
348 Err(ProjectionCacheEntry::NormalizedTerm { ty, complete: _ }) => {
349 debug!(?ty, "found normalized ty");
361 obligations.extend(ty.obligations);
362 return Ok(Some(ty.value));
363 }
364 Err(ProjectionCacheEntry::Error) => {
365 debug!("opt_normalize_projection_type: found error");
366 let result = normalize_to_error(selcx, param_env, projection_term, cause, depth);
367 obligations.extend(result.obligations);
368 return Ok(Some(result.value));
369 }
370 }
371
372 let obligation =
373 Obligation::with_depth(selcx.tcx(), cause.clone(), depth, param_env, projection_term);
374
375 match project(selcx, &obligation) {
376 Ok(Projected::Progress(Progress {
377 term: projected_term,
378 obligations: mut projected_obligations,
379 })) => {
380 debug!("opt_normalize_projection_type: progress");
381 let projected_term = selcx.infcx.resolve_vars_if_possible(projected_term);
387
388 let mut result = if projected_term.has_aliases() {
389 let normalized_ty = normalize_with_depth_to(
390 selcx,
391 param_env,
392 cause,
393 depth + 1,
394 projected_term,
395 &mut projected_obligations,
396 );
397
398 Normalized { value: normalized_ty, obligations: projected_obligations }
399 } else {
400 Normalized { value: projected_term, obligations: projected_obligations }
401 };
402
403 let mut deduped = SsoHashSet::with_capacity(result.obligations.len());
404 result.obligations.retain(|obligation| deduped.insert(obligation.clone()));
405
406 infcx.inner.borrow_mut().projection_cache().insert_term(cache_key, result.clone());
407 obligations.extend(result.obligations);
408 Ok(Some(result.value))
409 }
410 Ok(Projected::NoProgress(projected_ty)) => {
411 debug!("opt_normalize_projection_type: no progress");
412 let result =
413 Normalized { value: projected_ty, obligations: PredicateObligations::new() };
414 infcx.inner.borrow_mut().projection_cache().insert_term(cache_key, result.clone());
415 Ok(Some(result.value))
417 }
418 Err(ProjectionError::TooManyCandidates) => {
419 debug!("opt_normalize_projection_type: too many candidates");
420 infcx.inner.borrow_mut().projection_cache().ambiguous(cache_key);
421 Ok(None)
422 }
423 Err(ProjectionError::TraitSelectionError(_)) => {
424 debug!("opt_normalize_projection_type: ERROR");
425 infcx.inner.borrow_mut().projection_cache().error(cache_key);
430 let result = normalize_to_error(selcx, param_env, projection_term, cause, depth);
431 obligations.extend(result.obligations);
432 Ok(Some(result.value))
433 }
434 }
435}
436
437fn normalize_to_error<'a, 'tcx>(
458 selcx: &SelectionContext<'a, 'tcx>,
459 param_env: ty::ParamEnv<'tcx>,
460 projection_term: ty::AliasTerm<'tcx>,
461 cause: ObligationCause<'tcx>,
462 depth: usize,
463) -> NormalizedTerm<'tcx> {
464 let trait_ref = ty::Binder::dummy(projection_term.trait_ref(selcx.tcx()));
465 let new_value = match projection_term.kind(selcx.tcx()) {
466 ty::AliasTermKind::ProjectionTy
467 | ty::AliasTermKind::InherentTy
468 | ty::AliasTermKind::OpaqueTy
469 | ty::AliasTermKind::FreeTy => selcx.infcx.next_ty_var(cause.span).into(),
470 ty::AliasTermKind::FreeConst
471 | ty::AliasTermKind::InherentConst
472 | ty::AliasTermKind::UnevaluatedConst
473 | ty::AliasTermKind::ProjectionConst => selcx.infcx.next_const_var(cause.span).into(),
474 };
475 let mut obligations = PredicateObligations::new();
476 obligations.push(Obligation {
477 cause,
478 recursion_depth: depth,
479 param_env,
480 predicate: trait_ref.upcast(selcx.tcx()),
481 });
482 Normalized { value: new_value, obligations }
483}
484
485#[instrument(level = "debug", skip(selcx, param_env, cause, obligations))]
488pub fn normalize_inherent_projection<'a, 'b, 'tcx>(
489 selcx: &'a mut SelectionContext<'b, 'tcx>,
490 param_env: ty::ParamEnv<'tcx>,
491 alias_term: ty::AliasTerm<'tcx>,
492 cause: ObligationCause<'tcx>,
493 depth: usize,
494 obligations: &mut PredicateObligations<'tcx>,
495) -> ty::Term<'tcx> {
496 let tcx = selcx.tcx();
497
498 if !tcx.recursion_limit().value_within_limit(depth) {
499 tcx.dcx().emit_fatal(InherentProjectionNormalizationOverflow {
501 span: cause.span,
502 ty: alias_term.to_string(),
503 });
504 }
505
506 let args = compute_inherent_assoc_term_args(
507 selcx,
508 param_env,
509 alias_term,
510 cause.clone(),
511 depth,
512 obligations,
513 );
514
515 let predicates = tcx.predicates_of(alias_term.def_id).instantiate(tcx, args);
517 for (predicate, span) in predicates {
518 let predicate = normalize_with_depth_to(
519 selcx,
520 param_env,
521 cause.clone(),
522 depth + 1,
523 predicate,
524 obligations,
525 );
526
527 let nested_cause = ObligationCause::new(
528 cause.span,
529 cause.body_id,
530 ObligationCauseCode::WhereClause(alias_term.def_id, span),
535 );
536
537 obligations.push(Obligation::with_depth(
538 tcx,
539 nested_cause,
540 depth + 1,
541 param_env,
542 predicate,
543 ));
544 }
545
546 let term: Term<'tcx> = if alias_term.kind(tcx).is_type() {
547 tcx.type_of(alias_term.def_id).instantiate(tcx, args).into()
548 } else {
549 get_associated_const_value(selcx, alias_term.to_term(tcx).expect_const(), param_env).into()
550 };
551
552 let mut term = selcx.infcx.resolve_vars_if_possible(term);
553 if term.has_aliases() {
554 term =
555 normalize_with_depth_to(selcx, param_env, cause.clone(), depth + 1, term, obligations);
556 }
557
558 term
559}
560
561pub fn compute_inherent_assoc_term_args<'a, 'b, 'tcx>(
563 selcx: &'a mut SelectionContext<'b, 'tcx>,
564 param_env: ty::ParamEnv<'tcx>,
565 alias_term: ty::AliasTerm<'tcx>,
566 cause: ObligationCause<'tcx>,
567 depth: usize,
568 obligations: &mut PredicateObligations<'tcx>,
569) -> ty::GenericArgsRef<'tcx> {
570 let tcx = selcx.tcx();
571
572 let impl_def_id = tcx.parent(alias_term.def_id);
573 let impl_args = selcx.infcx.fresh_args_for_item(cause.span, impl_def_id);
574
575 let mut impl_ty = tcx.type_of(impl_def_id).instantiate(tcx, impl_args);
576 if !selcx.infcx.next_trait_solver() {
577 impl_ty = normalize_with_depth_to(
578 selcx,
579 param_env,
580 cause.clone(),
581 depth + 1,
582 impl_ty,
583 obligations,
584 );
585 }
586
587 let mut self_ty = alias_term.self_ty();
590 if !selcx.infcx.next_trait_solver() {
591 self_ty = normalize_with_depth_to(
592 selcx,
593 param_env,
594 cause.clone(),
595 depth + 1,
596 self_ty,
597 obligations,
598 );
599 }
600
601 match selcx.infcx.at(&cause, param_env).eq(DefineOpaqueTypes::Yes, impl_ty, self_ty) {
602 Ok(mut ok) => obligations.append(&mut ok.obligations),
603 Err(_) => {
604 tcx.dcx().span_bug(
605 cause.span,
606 format!("{self_ty:?} was equal to {impl_ty:?} during selection but now it is not"),
607 );
608 }
609 }
610
611 alias_term.rebase_inherent_args_onto_impl(impl_args, tcx)
612}
613
614enum Projected<'tcx> {
615 Progress(Progress<'tcx>),
616 NoProgress(ty::Term<'tcx>),
617}
618
619struct Progress<'tcx> {
620 term: ty::Term<'tcx>,
621 obligations: PredicateObligations<'tcx>,
622}
623
624impl<'tcx> Progress<'tcx> {
625 fn error_for_term(
626 tcx: TyCtxt<'tcx>,
627 alias_term: ty::AliasTerm<'tcx>,
628 guar: ErrorGuaranteed,
629 ) -> Self {
630 let err_term = if alias_term.kind(tcx).is_type() {
631 Ty::new_error(tcx, guar).into()
632 } else {
633 ty::Const::new_error(tcx, guar).into()
634 };
635 Progress { term: err_term, obligations: PredicateObligations::new() }
636 }
637
638 fn with_addl_obligations(mut self, mut obligations: PredicateObligations<'tcx>) -> Self {
639 self.obligations.append(&mut obligations);
640 self
641 }
642}
643
644#[instrument(level = "info", skip(selcx))]
650fn project<'cx, 'tcx>(
651 selcx: &mut SelectionContext<'cx, 'tcx>,
652 obligation: &ProjectionTermObligation<'tcx>,
653) -> Result<Projected<'tcx>, ProjectionError<'tcx>> {
654 if !selcx.tcx().recursion_limit().value_within_limit(obligation.recursion_depth) {
655 return Err(ProjectionError::TraitSelectionError(SelectionError::Overflow(
658 OverflowError::Canonical,
659 )));
660 }
661
662 if let Err(guar) = obligation.predicate.error_reported() {
663 return Ok(Projected::Progress(Progress::error_for_term(
664 selcx.tcx(),
665 obligation.predicate,
666 guar,
667 )));
668 }
669
670 let mut candidates = ProjectionCandidateSet::None;
671
672 assemble_candidates_from_param_env(selcx, obligation, &mut candidates);
676
677 assemble_candidates_from_trait_def(selcx, obligation, &mut candidates);
678
679 assemble_candidates_from_object_ty(selcx, obligation, &mut candidates);
680
681 if let ProjectionCandidateSet::Single(ProjectionCandidate::Object(_)) = candidates {
682 } else {
687 assemble_candidates_from_impls(selcx, obligation, &mut candidates);
688 };
689
690 match candidates {
691 ProjectionCandidateSet::Single(candidate) => {
692 confirm_candidate(selcx, obligation, candidate)
693 }
694 ProjectionCandidateSet::None => {
695 let tcx = selcx.tcx();
696 let term = obligation.predicate.to_term(tcx);
697 Ok(Projected::NoProgress(term))
698 }
699 ProjectionCandidateSet::Error(e) => Err(ProjectionError::TraitSelectionError(e)),
701 ProjectionCandidateSet::Ambiguous => Err(ProjectionError::TooManyCandidates),
704 }
705}
706
707fn assemble_candidates_from_param_env<'cx, 'tcx>(
711 selcx: &mut SelectionContext<'cx, 'tcx>,
712 obligation: &ProjectionTermObligation<'tcx>,
713 candidate_set: &mut ProjectionCandidateSet<'tcx>,
714) {
715 assemble_candidates_from_predicates(
716 selcx,
717 obligation,
718 candidate_set,
719 ProjectionCandidate::ParamEnv,
720 obligation.param_env.caller_bounds().iter(),
721 false,
722 );
723}
724
725fn assemble_candidates_from_trait_def<'cx, 'tcx>(
736 selcx: &mut SelectionContext<'cx, 'tcx>,
737 obligation: &ProjectionTermObligation<'tcx>,
738 candidate_set: &mut ProjectionCandidateSet<'tcx>,
739) {
740 debug!("assemble_candidates_from_trait_def(..)");
741 let mut ambiguous = false;
742 let _ = selcx.for_each_item_bound(
743 obligation.predicate.self_ty(),
744 |selcx, clause, _| {
745 let Some(clause) = clause.as_projection_clause() else {
746 return ControlFlow::Continue(());
747 };
748 if clause.item_def_id() != obligation.predicate.def_id {
749 return ControlFlow::Continue(());
750 }
751
752 let is_match =
753 selcx.infcx.probe(|_| selcx.match_projection_projections(obligation, clause, true));
754
755 match is_match {
756 ProjectionMatchesProjection::Yes => {
757 candidate_set.push_candidate(ProjectionCandidate::TraitDef(clause));
758
759 if !obligation.predicate.has_non_region_infer() {
760 return ControlFlow::Break(());
764 }
765 }
766 ProjectionMatchesProjection::Ambiguous => {
767 candidate_set.mark_ambiguous();
768 }
769 ProjectionMatchesProjection::No => {}
770 }
771
772 ControlFlow::Continue(())
773 },
774 || ambiguous = true,
777 );
778
779 if ambiguous {
780 candidate_set.mark_ambiguous();
781 }
782}
783
784fn assemble_candidates_from_object_ty<'cx, 'tcx>(
794 selcx: &mut SelectionContext<'cx, 'tcx>,
795 obligation: &ProjectionTermObligation<'tcx>,
796 candidate_set: &mut ProjectionCandidateSet<'tcx>,
797) {
798 debug!("assemble_candidates_from_object_ty(..)");
799
800 let tcx = selcx.tcx();
801
802 if !tcx.trait_def(obligation.predicate.trait_def_id(tcx)).implement_via_object {
803 return;
804 }
805
806 let self_ty = obligation.predicate.self_ty();
807 let object_ty = selcx.infcx.shallow_resolve(self_ty);
808 let data = match object_ty.kind() {
809 ty::Dynamic(data, ..) => data,
810 ty::Infer(ty::TyVar(_)) => {
811 candidate_set.mark_ambiguous();
814 return;
815 }
816 _ => return,
817 };
818 let env_predicates = data
819 .projection_bounds()
820 .filter(|bound| bound.item_def_id() == obligation.predicate.def_id)
821 .map(|p| p.with_self_ty(tcx, object_ty).upcast(tcx));
822
823 assemble_candidates_from_predicates(
824 selcx,
825 obligation,
826 candidate_set,
827 ProjectionCandidate::Object,
828 env_predicates,
829 false,
830 );
831}
832
833#[instrument(
834 level = "debug",
835 skip(selcx, candidate_set, ctor, env_predicates, potentially_unnormalized_candidates)
836)]
837fn assemble_candidates_from_predicates<'cx, 'tcx>(
838 selcx: &mut SelectionContext<'cx, 'tcx>,
839 obligation: &ProjectionTermObligation<'tcx>,
840 candidate_set: &mut ProjectionCandidateSet<'tcx>,
841 ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionCandidate<'tcx>,
842 env_predicates: impl Iterator<Item = ty::Clause<'tcx>>,
843 potentially_unnormalized_candidates: bool,
844) {
845 let infcx = selcx.infcx;
846 let drcx = DeepRejectCtxt::relate_rigid_rigid(selcx.tcx());
847 for predicate in env_predicates {
848 let bound_predicate = predicate.kind();
849 if let ty::ClauseKind::Projection(data) = predicate.kind().skip_binder() {
850 let data = bound_predicate.rebind(data);
851 if data.item_def_id() != obligation.predicate.def_id {
852 continue;
853 }
854
855 if !drcx
856 .args_may_unify(obligation.predicate.args, data.skip_binder().projection_term.args)
857 {
858 continue;
859 }
860
861 let is_match = infcx.probe(|_| {
862 selcx.match_projection_projections(
863 obligation,
864 data,
865 potentially_unnormalized_candidates,
866 )
867 });
868
869 match is_match {
870 ProjectionMatchesProjection::Yes => {
871 candidate_set.push_candidate(ctor(data));
872
873 if potentially_unnormalized_candidates
874 && !obligation.predicate.has_non_region_infer()
875 {
876 return;
880 }
881 }
882 ProjectionMatchesProjection::Ambiguous => {
883 candidate_set.mark_ambiguous();
884 }
885 ProjectionMatchesProjection::No => {}
886 }
887 }
888 }
889}
890
891#[instrument(level = "debug", skip(selcx, obligation, candidate_set))]
892fn assemble_candidates_from_impls<'cx, 'tcx>(
893 selcx: &mut SelectionContext<'cx, 'tcx>,
894 obligation: &ProjectionTermObligation<'tcx>,
895 candidate_set: &mut ProjectionCandidateSet<'tcx>,
896) {
897 let trait_ref = obligation.predicate.trait_ref(selcx.tcx());
900 let trait_obligation = obligation.with(selcx.tcx(), trait_ref);
901 let _ = selcx.infcx.commit_if_ok(|_| {
902 let impl_source = match selcx.select(&trait_obligation) {
903 Ok(Some(impl_source)) => impl_source,
904 Ok(None) => {
905 candidate_set.mark_ambiguous();
906 return Err(());
907 }
908 Err(e) => {
909 debug!(error = ?e, "selection error");
910 candidate_set.mark_error(e);
911 return Err(());
912 }
913 };
914
915 let eligible = match &impl_source {
916 ImplSource::UserDefined(impl_data) => {
917 match specialization_graph::assoc_def(
940 selcx.tcx(),
941 impl_data.impl_def_id,
942 obligation.predicate.def_id,
943 ) {
944 Ok(node_item) => {
945 if node_item.is_final() {
946 true
948 } else {
949 match selcx.infcx.typing_mode() {
954 TypingMode::Coherence
955 | TypingMode::Analysis { .. }
956 | TypingMode::Borrowck { .. }
957 | TypingMode::PostBorrowckAnalysis { .. } => {
958 debug!(
959 assoc_ty = ?selcx.tcx().def_path_str(node_item.item.def_id),
960 ?obligation.predicate,
961 "not eligible due to default",
962 );
963 false
964 }
965 TypingMode::PostAnalysis => {
966 let poly_trait_ref =
969 selcx.infcx.resolve_vars_if_possible(trait_ref);
970 !poly_trait_ref.still_further_specializable()
971 }
972 }
973 }
974 }
975 Err(ErrorGuaranteed { .. }) => true,
979 }
980 }
981 ImplSource::Builtin(BuiltinImplSource::Misc | BuiltinImplSource::Trivial, _) => {
982 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
986
987 let tcx = selcx.tcx();
988 match selcx.tcx().as_lang_item(trait_ref.def_id) {
989 Some(
990 LangItem::Coroutine
991 | LangItem::Future
992 | LangItem::Iterator
993 | LangItem::AsyncIterator
994 | LangItem::Fn
995 | LangItem::FnMut
996 | LangItem::FnOnce
997 | LangItem::AsyncFn
998 | LangItem::AsyncFnMut
999 | LangItem::AsyncFnOnce,
1000 ) => true,
1001 Some(LangItem::AsyncFnKindHelper) => {
1002 if obligation.predicate.args.type_at(0).is_ty_var()
1004 || obligation.predicate.args.type_at(4).is_ty_var()
1005 || obligation.predicate.args.type_at(5).is_ty_var()
1006 {
1007 candidate_set.mark_ambiguous();
1008 true
1009 } else {
1010 obligation.predicate.args.type_at(0).to_opt_closure_kind().is_some()
1011 && obligation
1012 .predicate
1013 .args
1014 .type_at(1)
1015 .to_opt_closure_kind()
1016 .is_some()
1017 }
1018 }
1019 Some(LangItem::DiscriminantKind) => match self_ty.kind() {
1020 ty::Bool
1021 | ty::Char
1022 | ty::Int(_)
1023 | ty::Uint(_)
1024 | ty::Float(_)
1025 | ty::Adt(..)
1026 | ty::Foreign(_)
1027 | ty::Str
1028 | ty::Array(..)
1029 | ty::Pat(..)
1030 | ty::Slice(_)
1031 | ty::RawPtr(..)
1032 | ty::Ref(..)
1033 | ty::FnDef(..)
1034 | ty::FnPtr(..)
1035 | ty::Dynamic(..)
1036 | ty::Closure(..)
1037 | ty::CoroutineClosure(..)
1038 | ty::Coroutine(..)
1039 | ty::CoroutineWitness(..)
1040 | ty::Never
1041 | ty::Tuple(..)
1042 | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1044
1045 ty::UnsafeBinder(_) => todo!("FIXME(unsafe_binder)"),
1046
1047 ty::Param(_)
1051 | ty::Alias(..)
1052 | ty::Bound(..)
1053 | ty::Placeholder(..)
1054 | ty::Infer(..)
1055 | ty::Error(_) => false,
1056 },
1057 Some(LangItem::PointeeTrait) => {
1058 let tail = selcx.tcx().struct_tail_raw(
1059 self_ty,
1060 &obligation.cause,
1061 |ty| {
1062 normalize_with_depth(
1065 selcx,
1066 obligation.param_env,
1067 obligation.cause.clone(),
1068 obligation.recursion_depth + 1,
1069 ty,
1070 )
1071 .value
1072 },
1073 || {},
1074 );
1075
1076 match tail.kind() {
1077 ty::Bool
1078 | ty::Char
1079 | ty::Int(_)
1080 | ty::Uint(_)
1081 | ty::Float(_)
1082 | ty::Str
1083 | ty::Array(..)
1084 | ty::Pat(..)
1085 | ty::Slice(_)
1086 | ty::RawPtr(..)
1087 | ty::Ref(..)
1088 | ty::FnDef(..)
1089 | ty::FnPtr(..)
1090 | ty::Dynamic(..)
1091 | ty::Closure(..)
1092 | ty::CoroutineClosure(..)
1093 | ty::Coroutine(..)
1094 | ty::CoroutineWitness(..)
1095 | ty::Never
1096 | ty::Foreign(_)
1098 | ty::Adt(..)
1101 | ty::Tuple(..)
1103 | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..))
1105 | ty::Error(..) => true,
1107
1108 ty::Param(_) | ty::Alias(..)
1112 if self_ty != tail
1113 || selcx.infcx.predicate_must_hold_modulo_regions(
1114 &obligation.with(
1115 selcx.tcx(),
1116 ty::TraitRef::new(
1117 selcx.tcx(),
1118 selcx.tcx().require_lang_item(
1119 LangItem::Sized,
1120 obligation.cause.span,
1121 ),
1122 [self_ty],
1123 ),
1124 ),
1125 ) =>
1126 {
1127 true
1128 }
1129
1130 ty::UnsafeBinder(_) => todo!("FIXME(unsafe_binder)"),
1131
1132 ty::Param(_)
1134 | ty::Alias(..)
1135 | ty::Bound(..)
1136 | ty::Placeholder(..)
1137 | ty::Infer(..) => {
1138 if tail.has_infer_types() {
1139 candidate_set.mark_ambiguous();
1140 }
1141 false
1142 }
1143 }
1144 }
1145 _ if tcx.trait_is_auto(trait_ref.def_id) => {
1146 tcx.dcx().span_delayed_bug(
1147 tcx.def_span(obligation.predicate.def_id),
1148 "associated types not allowed on auto traits",
1149 );
1150 false
1151 }
1152 _ => {
1153 bug!("unexpected builtin trait with associated type: {trait_ref:?}")
1154 }
1155 }
1156 }
1157 ImplSource::Param(..) => {
1158 false
1184 }
1185 ImplSource::Builtin(BuiltinImplSource::Object { .. }, _) => {
1186 false
1190 }
1191 ImplSource::Builtin(BuiltinImplSource::TraitUpcasting { .. }, _) => {
1192 selcx.tcx().dcx().span_delayed_bug(
1194 obligation.cause.span,
1195 format!("Cannot project an associated type from `{impl_source:?}`"),
1196 );
1197 return Err(());
1198 }
1199 };
1200
1201 if eligible {
1202 if candidate_set.push_candidate(ProjectionCandidate::Select(impl_source)) {
1203 Ok(())
1204 } else {
1205 Err(())
1206 }
1207 } else {
1208 Err(())
1209 }
1210 });
1211}
1212
1213fn confirm_candidate<'cx, 'tcx>(
1215 selcx: &mut SelectionContext<'cx, 'tcx>,
1216 obligation: &ProjectionTermObligation<'tcx>,
1217 candidate: ProjectionCandidate<'tcx>,
1218) -> Result<Projected<'tcx>, ProjectionError<'tcx>> {
1219 debug!(?obligation, ?candidate, "confirm_candidate");
1220 let mut result = match candidate {
1221 ProjectionCandidate::ParamEnv(poly_projection)
1222 | ProjectionCandidate::Object(poly_projection) => Ok(Projected::Progress(
1223 confirm_param_env_candidate(selcx, obligation, poly_projection, false),
1224 )),
1225 ProjectionCandidate::TraitDef(poly_projection) => Ok(Projected::Progress(
1226 confirm_param_env_candidate(selcx, obligation, poly_projection, true),
1227 )),
1228 ProjectionCandidate::Select(impl_source) => {
1229 confirm_select_candidate(selcx, obligation, impl_source)
1230 }
1231 };
1232
1233 if let Ok(Projected::Progress(progress)) = &mut result
1239 && progress.term.has_infer_regions()
1240 {
1241 progress.term = progress.term.fold_with(&mut OpportunisticRegionResolver::new(selcx.infcx));
1242 }
1243
1244 result
1245}
1246
1247fn confirm_select_candidate<'cx, 'tcx>(
1249 selcx: &mut SelectionContext<'cx, 'tcx>,
1250 obligation: &ProjectionTermObligation<'tcx>,
1251 impl_source: Selection<'tcx>,
1252) -> Result<Projected<'tcx>, ProjectionError<'tcx>> {
1253 match impl_source {
1254 ImplSource::UserDefined(data) => confirm_impl_candidate(selcx, obligation, data),
1255 ImplSource::Builtin(BuiltinImplSource::Misc | BuiltinImplSource::Trivial, data) => {
1256 let tcx = selcx.tcx();
1257 let trait_def_id = obligation.predicate.trait_def_id(tcx);
1258 let progress = if tcx.is_lang_item(trait_def_id, LangItem::Coroutine) {
1259 confirm_coroutine_candidate(selcx, obligation, data)
1260 } else if tcx.is_lang_item(trait_def_id, LangItem::Future) {
1261 confirm_future_candidate(selcx, obligation, data)
1262 } else if tcx.is_lang_item(trait_def_id, LangItem::Iterator) {
1263 confirm_iterator_candidate(selcx, obligation, data)
1264 } else if tcx.is_lang_item(trait_def_id, LangItem::AsyncIterator) {
1265 confirm_async_iterator_candidate(selcx, obligation, data)
1266 } else if selcx.tcx().fn_trait_kind_from_def_id(trait_def_id).is_some() {
1267 if obligation.predicate.self_ty().is_closure()
1268 || obligation.predicate.self_ty().is_coroutine_closure()
1269 {
1270 confirm_closure_candidate(selcx, obligation, data)
1271 } else {
1272 confirm_fn_pointer_candidate(selcx, obligation, data)
1273 }
1274 } else if selcx.tcx().async_fn_trait_kind_from_def_id(trait_def_id).is_some() {
1275 confirm_async_closure_candidate(selcx, obligation, data)
1276 } else if tcx.is_lang_item(trait_def_id, LangItem::AsyncFnKindHelper) {
1277 confirm_async_fn_kind_helper_candidate(selcx, obligation, data)
1278 } else {
1279 confirm_builtin_candidate(selcx, obligation, data)
1280 };
1281 Ok(Projected::Progress(progress))
1282 }
1283 ImplSource::Builtin(BuiltinImplSource::Object { .. }, _)
1284 | ImplSource::Param(..)
1285 | ImplSource::Builtin(BuiltinImplSource::TraitUpcasting { .. }, _) => {
1286 span_bug!(
1288 obligation.cause.span,
1289 "Cannot project an associated type from `{:?}`",
1290 impl_source
1291 )
1292 }
1293 }
1294}
1295
1296fn confirm_coroutine_candidate<'cx, 'tcx>(
1297 selcx: &mut SelectionContext<'cx, 'tcx>,
1298 obligation: &ProjectionTermObligation<'tcx>,
1299 nested: PredicateObligations<'tcx>,
1300) -> Progress<'tcx> {
1301 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1302 let ty::Coroutine(_, args) = self_ty.kind() else {
1303 unreachable!(
1304 "expected coroutine self type for built-in coroutine candidate, found {self_ty}"
1305 )
1306 };
1307 let coroutine_sig = args.as_coroutine().sig();
1308 let Normalized { value: coroutine_sig, obligations } = normalize_with_depth(
1309 selcx,
1310 obligation.param_env,
1311 obligation.cause.clone(),
1312 obligation.recursion_depth + 1,
1313 coroutine_sig,
1314 );
1315
1316 debug!(?obligation, ?coroutine_sig, ?obligations, "confirm_coroutine_candidate");
1317
1318 let tcx = selcx.tcx();
1319
1320 let coroutine_def_id = tcx.require_lang_item(LangItem::Coroutine, obligation.cause.span);
1321
1322 let (trait_ref, yield_ty, return_ty) = super::util::coroutine_trait_ref_and_outputs(
1323 tcx,
1324 coroutine_def_id,
1325 obligation.predicate.self_ty(),
1326 coroutine_sig,
1327 );
1328
1329 let ty = if tcx.is_lang_item(obligation.predicate.def_id, LangItem::CoroutineReturn) {
1330 return_ty
1331 } else if tcx.is_lang_item(obligation.predicate.def_id, LangItem::CoroutineYield) {
1332 yield_ty
1333 } else {
1334 span_bug!(
1335 tcx.def_span(obligation.predicate.def_id),
1336 "unexpected associated type: `Coroutine::{}`",
1337 tcx.item_name(obligation.predicate.def_id),
1338 );
1339 };
1340
1341 let predicate = ty::ProjectionPredicate {
1342 projection_term: ty::AliasTerm::new_from_args(
1343 tcx,
1344 obligation.predicate.def_id,
1345 trait_ref.args,
1346 ),
1347 term: ty.into(),
1348 };
1349
1350 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1351 .with_addl_obligations(nested)
1352 .with_addl_obligations(obligations)
1353}
1354
1355fn confirm_future_candidate<'cx, 'tcx>(
1356 selcx: &mut SelectionContext<'cx, 'tcx>,
1357 obligation: &ProjectionTermObligation<'tcx>,
1358 nested: PredicateObligations<'tcx>,
1359) -> Progress<'tcx> {
1360 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1361 let ty::Coroutine(_, args) = self_ty.kind() else {
1362 unreachable!(
1363 "expected coroutine self type for built-in async future candidate, found {self_ty}"
1364 )
1365 };
1366 let coroutine_sig = args.as_coroutine().sig();
1367 let Normalized { value: coroutine_sig, obligations } = normalize_with_depth(
1368 selcx,
1369 obligation.param_env,
1370 obligation.cause.clone(),
1371 obligation.recursion_depth + 1,
1372 coroutine_sig,
1373 );
1374
1375 debug!(?obligation, ?coroutine_sig, ?obligations, "confirm_future_candidate");
1376
1377 let tcx = selcx.tcx();
1378 let fut_def_id = tcx.require_lang_item(LangItem::Future, obligation.cause.span);
1379
1380 let (trait_ref, return_ty) = super::util::future_trait_ref_and_outputs(
1381 tcx,
1382 fut_def_id,
1383 obligation.predicate.self_ty(),
1384 coroutine_sig,
1385 );
1386
1387 debug_assert_eq!(tcx.associated_item(obligation.predicate.def_id).name(), sym::Output);
1388
1389 let predicate = ty::ProjectionPredicate {
1390 projection_term: ty::AliasTerm::new_from_args(
1391 tcx,
1392 obligation.predicate.def_id,
1393 trait_ref.args,
1394 ),
1395 term: return_ty.into(),
1396 };
1397
1398 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1399 .with_addl_obligations(nested)
1400 .with_addl_obligations(obligations)
1401}
1402
1403fn confirm_iterator_candidate<'cx, 'tcx>(
1404 selcx: &mut SelectionContext<'cx, 'tcx>,
1405 obligation: &ProjectionTermObligation<'tcx>,
1406 nested: PredicateObligations<'tcx>,
1407) -> Progress<'tcx> {
1408 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1409 let ty::Coroutine(_, args) = self_ty.kind() else {
1410 unreachable!("expected coroutine self type for built-in gen candidate, found {self_ty}")
1411 };
1412 let gen_sig = args.as_coroutine().sig();
1413 let Normalized { value: gen_sig, obligations } = normalize_with_depth(
1414 selcx,
1415 obligation.param_env,
1416 obligation.cause.clone(),
1417 obligation.recursion_depth + 1,
1418 gen_sig,
1419 );
1420
1421 debug!(?obligation, ?gen_sig, ?obligations, "confirm_iterator_candidate");
1422
1423 let tcx = selcx.tcx();
1424 let iter_def_id = tcx.require_lang_item(LangItem::Iterator, obligation.cause.span);
1425
1426 let (trait_ref, yield_ty) = super::util::iterator_trait_ref_and_outputs(
1427 tcx,
1428 iter_def_id,
1429 obligation.predicate.self_ty(),
1430 gen_sig,
1431 );
1432
1433 debug_assert_eq!(tcx.associated_item(obligation.predicate.def_id).name(), sym::Item);
1434
1435 let predicate = ty::ProjectionPredicate {
1436 projection_term: ty::AliasTerm::new_from_args(
1437 tcx,
1438 obligation.predicate.def_id,
1439 trait_ref.args,
1440 ),
1441 term: yield_ty.into(),
1442 };
1443
1444 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1445 .with_addl_obligations(nested)
1446 .with_addl_obligations(obligations)
1447}
1448
1449fn confirm_async_iterator_candidate<'cx, 'tcx>(
1450 selcx: &mut SelectionContext<'cx, 'tcx>,
1451 obligation: &ProjectionTermObligation<'tcx>,
1452 nested: PredicateObligations<'tcx>,
1453) -> Progress<'tcx> {
1454 let ty::Coroutine(_, args) = selcx.infcx.shallow_resolve(obligation.predicate.self_ty()).kind()
1455 else {
1456 unreachable!()
1457 };
1458 let gen_sig = args.as_coroutine().sig();
1459 let Normalized { value: gen_sig, obligations } = normalize_with_depth(
1460 selcx,
1461 obligation.param_env,
1462 obligation.cause.clone(),
1463 obligation.recursion_depth + 1,
1464 gen_sig,
1465 );
1466
1467 debug!(?obligation, ?gen_sig, ?obligations, "confirm_async_iterator_candidate");
1468
1469 let tcx = selcx.tcx();
1470 let iter_def_id = tcx.require_lang_item(LangItem::AsyncIterator, obligation.cause.span);
1471
1472 let (trait_ref, yield_ty) = super::util::async_iterator_trait_ref_and_outputs(
1473 tcx,
1474 iter_def_id,
1475 obligation.predicate.self_ty(),
1476 gen_sig,
1477 );
1478
1479 debug_assert_eq!(tcx.associated_item(obligation.predicate.def_id).name(), sym::Item);
1480
1481 let ty::Adt(_poll_adt, args) = *yield_ty.kind() else {
1482 bug!();
1483 };
1484 let ty::Adt(_option_adt, args) = *args.type_at(0).kind() else {
1485 bug!();
1486 };
1487 let item_ty = args.type_at(0);
1488
1489 let predicate = ty::ProjectionPredicate {
1490 projection_term: ty::AliasTerm::new_from_args(
1491 tcx,
1492 obligation.predicate.def_id,
1493 trait_ref.args,
1494 ),
1495 term: item_ty.into(),
1496 };
1497
1498 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1499 .with_addl_obligations(nested)
1500 .with_addl_obligations(obligations)
1501}
1502
1503fn confirm_builtin_candidate<'cx, 'tcx>(
1504 selcx: &mut SelectionContext<'cx, 'tcx>,
1505 obligation: &ProjectionTermObligation<'tcx>,
1506 data: PredicateObligations<'tcx>,
1507) -> Progress<'tcx> {
1508 let tcx = selcx.tcx();
1509 let self_ty = obligation.predicate.self_ty();
1510 let item_def_id = obligation.predicate.def_id;
1511 let trait_def_id = tcx.parent(item_def_id);
1512 let args = tcx.mk_args(&[self_ty.into()]);
1513 let (term, obligations) = if tcx.is_lang_item(trait_def_id, LangItem::DiscriminantKind) {
1514 let discriminant_def_id =
1515 tcx.require_lang_item(LangItem::Discriminant, obligation.cause.span);
1516 assert_eq!(discriminant_def_id, item_def_id);
1517
1518 (self_ty.discriminant_ty(tcx).into(), PredicateObligations::new())
1519 } else if tcx.is_lang_item(trait_def_id, LangItem::PointeeTrait) {
1520 let metadata_def_id = tcx.require_lang_item(LangItem::Metadata, obligation.cause.span);
1521 assert_eq!(metadata_def_id, item_def_id);
1522
1523 let mut obligations = PredicateObligations::new();
1524 let normalize = |ty| {
1525 normalize_with_depth_to(
1526 selcx,
1527 obligation.param_env,
1528 obligation.cause.clone(),
1529 obligation.recursion_depth + 1,
1530 ty,
1531 &mut obligations,
1532 )
1533 };
1534 let metadata_ty = self_ty.ptr_metadata_ty_or_tail(tcx, normalize).unwrap_or_else(|tail| {
1535 if tail == self_ty {
1536 let sized_predicate = ty::TraitRef::new(
1541 tcx,
1542 tcx.require_lang_item(LangItem::Sized, obligation.cause.span),
1543 [self_ty],
1544 );
1545 obligations.push(obligation.with(tcx, sized_predicate));
1546 tcx.types.unit
1547 } else {
1548 Ty::new_projection(tcx, metadata_def_id, [tail])
1551 }
1552 });
1553 (metadata_ty.into(), obligations)
1554 } else {
1555 bug!("unexpected builtin trait with associated type: {:?}", obligation.predicate);
1556 };
1557
1558 let predicate = ty::ProjectionPredicate {
1559 projection_term: ty::AliasTerm::new_from_args(tcx, item_def_id, args),
1560 term,
1561 };
1562
1563 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1564 .with_addl_obligations(obligations)
1565 .with_addl_obligations(data)
1566}
1567
1568fn confirm_fn_pointer_candidate<'cx, 'tcx>(
1569 selcx: &mut SelectionContext<'cx, 'tcx>,
1570 obligation: &ProjectionTermObligation<'tcx>,
1571 nested: PredicateObligations<'tcx>,
1572) -> Progress<'tcx> {
1573 let tcx = selcx.tcx();
1574 let fn_type = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1575 let sig = fn_type.fn_sig(tcx);
1576 let Normalized { value: sig, obligations } = normalize_with_depth(
1577 selcx,
1578 obligation.param_env,
1579 obligation.cause.clone(),
1580 obligation.recursion_depth + 1,
1581 sig,
1582 );
1583
1584 confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
1585 .with_addl_obligations(nested)
1586 .with_addl_obligations(obligations)
1587}
1588
1589fn confirm_closure_candidate<'cx, 'tcx>(
1590 selcx: &mut SelectionContext<'cx, 'tcx>,
1591 obligation: &ProjectionTermObligation<'tcx>,
1592 nested: PredicateObligations<'tcx>,
1593) -> Progress<'tcx> {
1594 let tcx = selcx.tcx();
1595 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1596 let closure_sig = match *self_ty.kind() {
1597 ty::Closure(_, args) => args.as_closure().sig(),
1598
1599 ty::CoroutineClosure(def_id, args) => {
1603 let args = args.as_coroutine_closure();
1604 let kind_ty = args.kind_ty();
1605 args.coroutine_closure_sig().map_bound(|sig| {
1606 let output_ty = if let Some(_) = kind_ty.to_opt_closure_kind()
1610 && !args.tupled_upvars_ty().is_ty_var()
1612 {
1613 sig.to_coroutine_given_kind_and_upvars(
1614 tcx,
1615 args.parent_args(),
1616 tcx.coroutine_for_closure(def_id),
1617 ty::ClosureKind::FnOnce,
1618 tcx.lifetimes.re_static,
1619 args.tupled_upvars_ty(),
1620 args.coroutine_captures_by_ref_ty(),
1621 )
1622 } else {
1623 let upvars_projection_def_id =
1624 tcx.require_lang_item(LangItem::AsyncFnKindUpvars, obligation.cause.span);
1625 let tupled_upvars_ty = Ty::new_projection(
1626 tcx,
1627 upvars_projection_def_id,
1628 [
1629 ty::GenericArg::from(kind_ty),
1630 Ty::from_closure_kind(tcx, ty::ClosureKind::FnOnce).into(),
1631 tcx.lifetimes.re_static.into(),
1632 sig.tupled_inputs_ty.into(),
1633 args.tupled_upvars_ty().into(),
1634 args.coroutine_captures_by_ref_ty().into(),
1635 ],
1636 );
1637 sig.to_coroutine(
1638 tcx,
1639 args.parent_args(),
1640 Ty::from_closure_kind(tcx, ty::ClosureKind::FnOnce),
1641 tcx.coroutine_for_closure(def_id),
1642 tupled_upvars_ty,
1643 )
1644 };
1645 tcx.mk_fn_sig(
1646 [sig.tupled_inputs_ty],
1647 output_ty,
1648 sig.c_variadic,
1649 sig.safety,
1650 sig.abi,
1651 )
1652 })
1653 }
1654
1655 _ => {
1656 unreachable!("expected closure self type for closure candidate, found {self_ty}");
1657 }
1658 };
1659
1660 let Normalized { value: closure_sig, obligations } = normalize_with_depth(
1661 selcx,
1662 obligation.param_env,
1663 obligation.cause.clone(),
1664 obligation.recursion_depth + 1,
1665 closure_sig,
1666 );
1667
1668 debug!(?obligation, ?closure_sig, ?obligations, "confirm_closure_candidate");
1669
1670 confirm_callable_candidate(selcx, obligation, closure_sig, util::TupleArgumentsFlag::No)
1671 .with_addl_obligations(nested)
1672 .with_addl_obligations(obligations)
1673}
1674
1675fn confirm_callable_candidate<'cx, 'tcx>(
1676 selcx: &mut SelectionContext<'cx, 'tcx>,
1677 obligation: &ProjectionTermObligation<'tcx>,
1678 fn_sig: ty::PolyFnSig<'tcx>,
1679 flag: util::TupleArgumentsFlag,
1680) -> Progress<'tcx> {
1681 let tcx = selcx.tcx();
1682
1683 debug!(?obligation, ?fn_sig, "confirm_callable_candidate");
1684
1685 let fn_once_def_id = tcx.require_lang_item(LangItem::FnOnce, obligation.cause.span);
1686 let fn_once_output_def_id =
1687 tcx.require_lang_item(LangItem::FnOnceOutput, obligation.cause.span);
1688
1689 let predicate = super::util::closure_trait_ref_and_return_type(
1690 tcx,
1691 fn_once_def_id,
1692 obligation.predicate.self_ty(),
1693 fn_sig,
1694 flag,
1695 )
1696 .map_bound(|(trait_ref, ret_type)| ty::ProjectionPredicate {
1697 projection_term: ty::AliasTerm::new_from_args(tcx, fn_once_output_def_id, trait_ref.args),
1698 term: ret_type.into(),
1699 });
1700
1701 confirm_param_env_candidate(selcx, obligation, predicate, true)
1702}
1703
1704fn confirm_async_closure_candidate<'cx, 'tcx>(
1705 selcx: &mut SelectionContext<'cx, 'tcx>,
1706 obligation: &ProjectionTermObligation<'tcx>,
1707 nested: PredicateObligations<'tcx>,
1708) -> Progress<'tcx> {
1709 let tcx = selcx.tcx();
1710 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1711
1712 let goal_kind =
1713 tcx.async_fn_trait_kind_from_def_id(obligation.predicate.trait_def_id(tcx)).unwrap();
1714 let env_region = match goal_kind {
1715 ty::ClosureKind::Fn | ty::ClosureKind::FnMut => obligation.predicate.args.region_at(2),
1716 ty::ClosureKind::FnOnce => tcx.lifetimes.re_static,
1717 };
1718 let item_name = tcx.item_name(obligation.predicate.def_id);
1719
1720 let poly_cache_entry = match *self_ty.kind() {
1721 ty::CoroutineClosure(def_id, args) => {
1722 let args = args.as_coroutine_closure();
1723 let kind_ty = args.kind_ty();
1724 let sig = args.coroutine_closure_sig().skip_binder();
1725
1726 let term = match item_name {
1727 sym::CallOnceFuture | sym::CallRefFuture => {
1728 if let Some(closure_kind) = kind_ty.to_opt_closure_kind()
1729 && !args.tupled_upvars_ty().is_ty_var()
1731 {
1732 if !closure_kind.extends(goal_kind) {
1733 bug!("we should not be confirming if the closure kind is not met");
1734 }
1735 sig.to_coroutine_given_kind_and_upvars(
1736 tcx,
1737 args.parent_args(),
1738 tcx.coroutine_for_closure(def_id),
1739 goal_kind,
1740 env_region,
1741 args.tupled_upvars_ty(),
1742 args.coroutine_captures_by_ref_ty(),
1743 )
1744 } else {
1745 let upvars_projection_def_id = tcx
1746 .require_lang_item(LangItem::AsyncFnKindUpvars, obligation.cause.span);
1747 let tupled_upvars_ty = Ty::new_projection(
1756 tcx,
1757 upvars_projection_def_id,
1758 [
1759 ty::GenericArg::from(kind_ty),
1760 Ty::from_closure_kind(tcx, goal_kind).into(),
1761 env_region.into(),
1762 sig.tupled_inputs_ty.into(),
1763 args.tupled_upvars_ty().into(),
1764 args.coroutine_captures_by_ref_ty().into(),
1765 ],
1766 );
1767 sig.to_coroutine(
1768 tcx,
1769 args.parent_args(),
1770 Ty::from_closure_kind(tcx, goal_kind),
1771 tcx.coroutine_for_closure(def_id),
1772 tupled_upvars_ty,
1773 )
1774 }
1775 }
1776 sym::Output => sig.return_ty,
1777 name => bug!("no such associated type: {name}"),
1778 };
1779 let projection_term = match item_name {
1780 sym::CallOnceFuture | sym::Output => ty::AliasTerm::new(
1781 tcx,
1782 obligation.predicate.def_id,
1783 [self_ty, sig.tupled_inputs_ty],
1784 ),
1785 sym::CallRefFuture => ty::AliasTerm::new(
1786 tcx,
1787 obligation.predicate.def_id,
1788 [ty::GenericArg::from(self_ty), sig.tupled_inputs_ty.into(), env_region.into()],
1789 ),
1790 name => bug!("no such associated type: {name}"),
1791 };
1792
1793 args.coroutine_closure_sig()
1794 .rebind(ty::ProjectionPredicate { projection_term, term: term.into() })
1795 }
1796 ty::FnDef(..) | ty::FnPtr(..) => {
1797 let bound_sig = self_ty.fn_sig(tcx);
1798 let sig = bound_sig.skip_binder();
1799
1800 let term = match item_name {
1801 sym::CallOnceFuture | sym::CallRefFuture => sig.output(),
1802 sym::Output => {
1803 let future_output_def_id =
1804 tcx.require_lang_item(LangItem::FutureOutput, obligation.cause.span);
1805 Ty::new_projection(tcx, future_output_def_id, [sig.output()])
1806 }
1807 name => bug!("no such associated type: {name}"),
1808 };
1809 let projection_term = match item_name {
1810 sym::CallOnceFuture | sym::Output => ty::AliasTerm::new(
1811 tcx,
1812 obligation.predicate.def_id,
1813 [self_ty, Ty::new_tup(tcx, sig.inputs())],
1814 ),
1815 sym::CallRefFuture => ty::AliasTerm::new(
1816 tcx,
1817 obligation.predicate.def_id,
1818 [
1819 ty::GenericArg::from(self_ty),
1820 Ty::new_tup(tcx, sig.inputs()).into(),
1821 env_region.into(),
1822 ],
1823 ),
1824 name => bug!("no such associated type: {name}"),
1825 };
1826
1827 bound_sig.rebind(ty::ProjectionPredicate { projection_term, term: term.into() })
1828 }
1829 ty::Closure(_, args) => {
1830 let args = args.as_closure();
1831 let bound_sig = args.sig();
1832 let sig = bound_sig.skip_binder();
1833
1834 let term = match item_name {
1835 sym::CallOnceFuture | sym::CallRefFuture => sig.output(),
1836 sym::Output => {
1837 let future_output_def_id =
1838 tcx.require_lang_item(LangItem::FutureOutput, obligation.cause.span);
1839 Ty::new_projection(tcx, future_output_def_id, [sig.output()])
1840 }
1841 name => bug!("no such associated type: {name}"),
1842 };
1843 let projection_term = match item_name {
1844 sym::CallOnceFuture | sym::Output => {
1845 ty::AliasTerm::new(tcx, obligation.predicate.def_id, [self_ty, sig.inputs()[0]])
1846 }
1847 sym::CallRefFuture => ty::AliasTerm::new(
1848 tcx,
1849 obligation.predicate.def_id,
1850 [ty::GenericArg::from(self_ty), sig.inputs()[0].into(), env_region.into()],
1851 ),
1852 name => bug!("no such associated type: {name}"),
1853 };
1854
1855 bound_sig.rebind(ty::ProjectionPredicate { projection_term, term: term.into() })
1856 }
1857 _ => bug!("expected callable type for AsyncFn candidate"),
1858 };
1859
1860 confirm_param_env_candidate(selcx, obligation, poly_cache_entry, true)
1861 .with_addl_obligations(nested)
1862}
1863
1864fn confirm_async_fn_kind_helper_candidate<'cx, 'tcx>(
1865 selcx: &mut SelectionContext<'cx, 'tcx>,
1866 obligation: &ProjectionTermObligation<'tcx>,
1867 nested: PredicateObligations<'tcx>,
1868) -> Progress<'tcx> {
1869 let [
1870 _closure_kind_ty,
1872 goal_kind_ty,
1873 borrow_region,
1874 tupled_inputs_ty,
1875 tupled_upvars_ty,
1876 coroutine_captures_by_ref_ty,
1877 ] = **obligation.predicate.args
1878 else {
1879 bug!();
1880 };
1881
1882 let predicate = ty::ProjectionPredicate {
1883 projection_term: ty::AliasTerm::new_from_args(
1884 selcx.tcx(),
1885 obligation.predicate.def_id,
1886 obligation.predicate.args,
1887 ),
1888 term: ty::CoroutineClosureSignature::tupled_upvars_by_closure_kind(
1889 selcx.tcx(),
1890 goal_kind_ty.expect_ty().to_opt_closure_kind().unwrap(),
1891 tupled_inputs_ty.expect_ty(),
1892 tupled_upvars_ty.expect_ty(),
1893 coroutine_captures_by_ref_ty.expect_ty(),
1894 borrow_region.expect_region(),
1895 )
1896 .into(),
1897 };
1898
1899 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1900 .with_addl_obligations(nested)
1901}
1902
1903fn confirm_param_env_candidate<'cx, 'tcx>(
1905 selcx: &mut SelectionContext<'cx, 'tcx>,
1906 obligation: &ProjectionTermObligation<'tcx>,
1907 poly_cache_entry: ty::PolyProjectionPredicate<'tcx>,
1908 potentially_unnormalized_candidate: bool,
1909) -> Progress<'tcx> {
1910 let infcx = selcx.infcx;
1911 let cause = &obligation.cause;
1912 let param_env = obligation.param_env;
1913
1914 let cache_entry = infcx.instantiate_binder_with_fresh_vars(
1915 cause.span,
1916 BoundRegionConversionTime::HigherRankedType,
1917 poly_cache_entry,
1918 );
1919
1920 let cache_projection = cache_entry.projection_term;
1921 let mut nested_obligations = PredicateObligations::new();
1922 let obligation_projection = obligation.predicate;
1923 let obligation_projection = ensure_sufficient_stack(|| {
1924 normalize_with_depth_to(
1925 selcx,
1926 obligation.param_env,
1927 obligation.cause.clone(),
1928 obligation.recursion_depth + 1,
1929 obligation_projection,
1930 &mut nested_obligations,
1931 )
1932 });
1933 let cache_projection = if potentially_unnormalized_candidate {
1934 ensure_sufficient_stack(|| {
1935 normalize_with_depth_to(
1936 selcx,
1937 obligation.param_env,
1938 obligation.cause.clone(),
1939 obligation.recursion_depth + 1,
1940 cache_projection,
1941 &mut nested_obligations,
1942 )
1943 })
1944 } else {
1945 cache_projection
1946 };
1947
1948 debug!(?cache_projection, ?obligation_projection);
1949
1950 match infcx.at(cause, param_env).eq(
1951 DefineOpaqueTypes::Yes,
1952 cache_projection,
1953 obligation_projection,
1954 ) {
1955 Ok(InferOk { value: _, obligations }) => {
1956 nested_obligations.extend(obligations);
1957 assoc_term_own_obligations(selcx, obligation, &mut nested_obligations);
1958 Progress { term: cache_entry.term, obligations: nested_obligations }
1959 }
1960 Err(e) => {
1961 let msg = format!(
1962 "Failed to unify obligation `{obligation:?}` with poly_projection `{poly_cache_entry:?}`: {e:?}",
1963 );
1964 debug!("confirm_param_env_candidate: {}", msg);
1965 let err = Ty::new_error_with_message(infcx.tcx, obligation.cause.span, msg);
1966 Progress { term: err.into(), obligations: PredicateObligations::new() }
1967 }
1968 }
1969}
1970
1971fn confirm_impl_candidate<'cx, 'tcx>(
1973 selcx: &mut SelectionContext<'cx, 'tcx>,
1974 obligation: &ProjectionTermObligation<'tcx>,
1975 impl_impl_source: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>,
1976) -> Result<Projected<'tcx>, ProjectionError<'tcx>> {
1977 let tcx = selcx.tcx();
1978
1979 let ImplSourceUserDefinedData { impl_def_id, args, mut nested } = impl_impl_source;
1980
1981 let assoc_item_id = obligation.predicate.def_id;
1982 let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
1983
1984 let param_env = obligation.param_env;
1985 let assoc_term = match specialization_graph::assoc_def(tcx, impl_def_id, assoc_item_id) {
1986 Ok(assoc_term) => assoc_term,
1987 Err(guar) => {
1988 return Ok(Projected::Progress(Progress::error_for_term(
1989 tcx,
1990 obligation.predicate,
1991 guar,
1992 )));
1993 }
1994 };
1995
1996 if !assoc_term.item.defaultness(tcx).has_value() {
2002 debug!(
2003 "confirm_impl_candidate: no associated type {:?} for {:?}",
2004 assoc_term.item.name(),
2005 obligation.predicate
2006 );
2007 if tcx.impl_self_is_guaranteed_unsized(impl_def_id) {
2008 return Ok(Projected::NoProgress(obligation.predicate.to_term(tcx)));
2013 } else {
2014 return Ok(Projected::Progress(Progress {
2015 term: if obligation.predicate.kind(tcx).is_type() {
2016 Ty::new_misc_error(tcx).into()
2017 } else {
2018 ty::Const::new_misc_error(tcx).into()
2019 },
2020 obligations: nested,
2021 }));
2022 }
2023 }
2024
2025 let args = obligation.predicate.args.rebase_onto(tcx, trait_def_id, args);
2032 let args = translate_args(selcx.infcx, param_env, impl_def_id, args, assoc_term.defining_node);
2033
2034 let term = if obligation.predicate.kind(tcx).is_type() {
2035 tcx.type_of(assoc_term.item.def_id).map_bound(|ty| ty.into())
2036 } else {
2037 ty::EarlyBinder::bind(
2038 get_associated_const_value(
2039 selcx,
2040 obligation.predicate.to_term(tcx).expect_const(),
2041 param_env,
2042 )
2043 .into(),
2044 )
2045 };
2046
2047 let progress = if !tcx.check_args_compatible(assoc_term.item.def_id, args) {
2048 let msg = "impl item and trait item have different parameters";
2049 let span = obligation.cause.span;
2050 let err = if obligation.predicate.kind(tcx).is_type() {
2051 Ty::new_error_with_message(tcx, span, msg).into()
2052 } else {
2053 ty::Const::new_error_with_message(tcx, span, msg).into()
2054 };
2055 Progress { term: err, obligations: nested }
2056 } else {
2057 assoc_term_own_obligations(selcx, obligation, &mut nested);
2058 Progress { term: term.instantiate(tcx, args), obligations: nested }
2059 };
2060 Ok(Projected::Progress(progress))
2061}
2062
2063fn assoc_term_own_obligations<'cx, 'tcx>(
2067 selcx: &mut SelectionContext<'cx, 'tcx>,
2068 obligation: &ProjectionTermObligation<'tcx>,
2069 nested: &mut PredicateObligations<'tcx>,
2070) {
2071 let tcx = selcx.tcx();
2072 let predicates = tcx
2073 .predicates_of(obligation.predicate.def_id)
2074 .instantiate_own(tcx, obligation.predicate.args);
2075 for (predicate, span) in predicates {
2076 let normalized = normalize_with_depth_to(
2077 selcx,
2078 obligation.param_env,
2079 obligation.cause.clone(),
2080 obligation.recursion_depth + 1,
2081 predicate,
2082 nested,
2083 );
2084
2085 let nested_cause = if matches!(
2086 obligation.cause.code(),
2087 ObligationCauseCode::CompareImplItem { .. }
2088 | ObligationCauseCode::CheckAssociatedTypeBounds { .. }
2089 | ObligationCauseCode::AscribeUserTypeProvePredicate(..)
2090 ) {
2091 obligation.cause.clone()
2092 } else {
2093 ObligationCause::new(
2094 obligation.cause.span,
2095 obligation.cause.body_id,
2096 ObligationCauseCode::WhereClause(obligation.predicate.def_id, span),
2097 )
2098 };
2099 nested.push(Obligation::with_depth(
2100 tcx,
2101 nested_cause,
2102 obligation.recursion_depth + 1,
2103 obligation.param_env,
2104 normalized,
2105 ));
2106 }
2107}
2108
2109pub(crate) trait ProjectionCacheKeyExt<'cx, 'tcx>: Sized {
2110 fn from_poly_projection_obligation(
2111 selcx: &mut SelectionContext<'cx, 'tcx>,
2112 obligation: &PolyProjectionObligation<'tcx>,
2113 ) -> Option<Self>;
2114}
2115
2116impl<'cx, 'tcx> ProjectionCacheKeyExt<'cx, 'tcx> for ProjectionCacheKey<'tcx> {
2117 fn from_poly_projection_obligation(
2118 selcx: &mut SelectionContext<'cx, 'tcx>,
2119 obligation: &PolyProjectionObligation<'tcx>,
2120 ) -> Option<Self> {
2121 let infcx = selcx.infcx;
2122 obligation.predicate.no_bound_vars().map(|predicate| {
2125 ProjectionCacheKey::new(
2126 infcx.resolve_vars_if_possible(predicate.projection_term),
2131 obligation.param_env,
2132 )
2133 })
2134 }
2135}
2136
2137fn get_associated_const_value<'tcx>(
2138 selcx: &mut SelectionContext<'_, 'tcx>,
2139 alias_ct: ty::Const<'tcx>,
2140 param_env: ty::ParamEnv<'tcx>,
2141) -> ty::Const<'tcx> {
2142 super::evaluate_const(selcx.infcx, alias_ct, param_env)
2147}