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 use self::ProjectionCandidate::*;
88 use self::ProjectionCandidateSet::*;
89
90 let convert_to_ambiguous;
99
100 match self {
101 None => {
102 *self = Single(candidate);
103 return true;
104 }
105
106 Single(current) => {
107 if current == &candidate {
110 return false;
111 }
112
113 match (current, candidate) {
121 (ParamEnv(..), ParamEnv(..)) => convert_to_ambiguous = (),
122 (ParamEnv(..), _) => return false,
123 (_, ParamEnv(..)) => bug!(
124 "should never prefer non-param-env candidates over param-env candidates"
125 ),
126 (_, _) => convert_to_ambiguous = (),
127 }
128 }
129
130 Ambiguous | Error(..) => {
131 return false;
132 }
133 }
134
135 let () = convert_to_ambiguous;
138 *self = Ambiguous;
139 false
140 }
141}
142
143pub(super) enum ProjectAndUnifyResult<'tcx> {
152 Holds(PredicateObligations<'tcx>),
157 FailedNormalization,
160 Recursive,
163 MismatchedProjectionTypes(MismatchedProjectionTypes<'tcx>),
166}
167
168#[instrument(level = "debug", skip(selcx))]
176pub(super) fn poly_project_and_unify_term<'cx, 'tcx>(
177 selcx: &mut SelectionContext<'cx, 'tcx>,
178 obligation: &PolyProjectionObligation<'tcx>,
179) -> ProjectAndUnifyResult<'tcx> {
180 let infcx = selcx.infcx;
181 let r = infcx.commit_if_ok(|_snapshot| {
182 let placeholder_predicate = infcx.enter_forall_and_leak_universe(obligation.predicate);
183
184 let placeholder_obligation = obligation.with(infcx.tcx, placeholder_predicate);
185 match project_and_unify_term(selcx, &placeholder_obligation) {
186 ProjectAndUnifyResult::MismatchedProjectionTypes(e) => Err(e),
187 other => Ok(other),
188 }
189 });
190
191 match r {
192 Ok(inner) => inner,
193 Err(err) => ProjectAndUnifyResult::MismatchedProjectionTypes(err),
194 }
195}
196
197#[instrument(level = "debug", skip(selcx))]
206fn project_and_unify_term<'cx, 'tcx>(
207 selcx: &mut SelectionContext<'cx, 'tcx>,
208 obligation: &ProjectionObligation<'tcx>,
209) -> ProjectAndUnifyResult<'tcx> {
210 let mut obligations = PredicateObligations::new();
211
212 let infcx = selcx.infcx;
213 let normalized = match opt_normalize_projection_term(
214 selcx,
215 obligation.param_env,
216 obligation.predicate.projection_term,
217 obligation.cause.clone(),
218 obligation.recursion_depth,
219 &mut obligations,
220 ) {
221 Ok(Some(n)) => n,
222 Ok(None) => return ProjectAndUnifyResult::FailedNormalization,
223 Err(InProgress) => return ProjectAndUnifyResult::Recursive,
224 };
225 debug!(?normalized, ?obligations, "project_and_unify_type result");
226 let actual = obligation.predicate.term;
227 let InferOk { value: actual, obligations: new } =
231 selcx.infcx.replace_opaque_types_with_inference_vars(
232 actual,
233 obligation.cause.body_id,
234 obligation.cause.span,
235 obligation.param_env,
236 );
237 obligations.extend(new);
238
239 match infcx.at(&obligation.cause, obligation.param_env).eq(
241 DefineOpaqueTypes::Yes,
242 normalized,
243 actual,
244 ) {
245 Ok(InferOk { obligations: inferred_obligations, value: () }) => {
246 obligations.extend(inferred_obligations);
247 ProjectAndUnifyResult::Holds(obligations)
248 }
249 Err(err) => {
250 debug!("equating types encountered error {:?}", err);
251 ProjectAndUnifyResult::MismatchedProjectionTypes(MismatchedProjectionTypes { err })
252 }
253 }
254}
255
256pub fn normalize_projection_term<'a, 'b, 'tcx>(
264 selcx: &'a mut SelectionContext<'b, 'tcx>,
265 param_env: ty::ParamEnv<'tcx>,
266 alias_term: ty::AliasTerm<'tcx>,
267 cause: ObligationCause<'tcx>,
268 depth: usize,
269 obligations: &mut PredicateObligations<'tcx>,
270) -> Term<'tcx> {
271 opt_normalize_projection_term(selcx, param_env, alias_term, cause.clone(), depth, obligations)
272 .ok()
273 .flatten()
274 .unwrap_or_else(move || {
275 selcx
280 .infcx
281 .projection_term_to_infer(param_env, alias_term, cause, depth + 1, obligations)
282 .into()
283 })
284}
285
286#[instrument(level = "debug", skip(selcx, param_env, cause, obligations))]
298pub(super) fn opt_normalize_projection_term<'a, 'b, 'tcx>(
299 selcx: &'a mut SelectionContext<'b, 'tcx>,
300 param_env: ty::ParamEnv<'tcx>,
301 projection_term: ty::AliasTerm<'tcx>,
302 cause: ObligationCause<'tcx>,
303 depth: usize,
304 obligations: &mut PredicateObligations<'tcx>,
305) -> Result<Option<Term<'tcx>>, InProgress> {
306 let infcx = selcx.infcx;
307 debug_assert!(!selcx.infcx.next_trait_solver());
308 let projection_term = infcx.resolve_vars_if_possible(projection_term);
309 let cache_key = ProjectionCacheKey::new(projection_term, param_env);
310
311 let cache_entry = infcx.inner.borrow_mut().projection_cache().try_start(cache_key);
319 match cache_entry {
320 Ok(()) => debug!("no cache"),
321 Err(ProjectionCacheEntry::Ambiguous) => {
322 debug!("found cache entry: ambiguous");
326 return Ok(None);
327 }
328 Err(ProjectionCacheEntry::InProgress) => {
329 debug!("found cache entry: in-progress");
338
339 infcx.inner.borrow_mut().projection_cache().recur(cache_key);
343 return Err(InProgress);
344 }
345 Err(ProjectionCacheEntry::Recur) => {
346 debug!("recur cache");
347 return Err(InProgress);
348 }
349 Err(ProjectionCacheEntry::NormalizedTerm { ty, complete: _ }) => {
350 debug!(?ty, "found normalized ty");
362 obligations.extend(ty.obligations);
363 return Ok(Some(ty.value));
364 }
365 Err(ProjectionCacheEntry::Error) => {
366 debug!("opt_normalize_projection_type: found error");
367 let result = normalize_to_error(selcx, param_env, projection_term, cause, depth);
368 obligations.extend(result.obligations);
369 return Ok(Some(result.value));
370 }
371 }
372
373 let obligation =
374 Obligation::with_depth(selcx.tcx(), cause.clone(), depth, param_env, projection_term);
375
376 match project(selcx, &obligation) {
377 Ok(Projected::Progress(Progress {
378 term: projected_term,
379 obligations: mut projected_obligations,
380 })) => {
381 debug!("opt_normalize_projection_type: progress");
382 let projected_term = selcx.infcx.resolve_vars_if_possible(projected_term);
388
389 let mut result = if projected_term.has_aliases() {
390 let normalized_ty = normalize_with_depth_to(
391 selcx,
392 param_env,
393 cause,
394 depth + 1,
395 projected_term,
396 &mut projected_obligations,
397 );
398
399 Normalized { value: normalized_ty, obligations: projected_obligations }
400 } else {
401 Normalized { value: projected_term, obligations: projected_obligations }
402 };
403
404 let mut deduped = SsoHashSet::with_capacity(result.obligations.len());
405 result.obligations.retain(|obligation| deduped.insert(obligation.clone()));
406
407 infcx.inner.borrow_mut().projection_cache().insert_term(cache_key, result.clone());
408 obligations.extend(result.obligations);
409 Ok(Some(result.value))
410 }
411 Ok(Projected::NoProgress(projected_ty)) => {
412 debug!("opt_normalize_projection_type: no progress");
413 let result =
414 Normalized { value: projected_ty, obligations: PredicateObligations::new() };
415 infcx.inner.borrow_mut().projection_cache().insert_term(cache_key, result.clone());
416 Ok(Some(result.value))
418 }
419 Err(ProjectionError::TooManyCandidates) => {
420 debug!("opt_normalize_projection_type: too many candidates");
421 infcx.inner.borrow_mut().projection_cache().ambiguous(cache_key);
422 Ok(None)
423 }
424 Err(ProjectionError::TraitSelectionError(_)) => {
425 debug!("opt_normalize_projection_type: ERROR");
426 infcx.inner.borrow_mut().projection_cache().error(cache_key);
431 let result = normalize_to_error(selcx, param_env, projection_term, cause, depth);
432 obligations.extend(result.obligations);
433 Ok(Some(result.value))
434 }
435 }
436}
437
438fn normalize_to_error<'a, 'tcx>(
459 selcx: &SelectionContext<'a, 'tcx>,
460 param_env: ty::ParamEnv<'tcx>,
461 projection_term: ty::AliasTerm<'tcx>,
462 cause: ObligationCause<'tcx>,
463 depth: usize,
464) -> NormalizedTerm<'tcx> {
465 let trait_ref = ty::Binder::dummy(projection_term.trait_ref(selcx.tcx()));
466 let new_value = match projection_term.kind(selcx.tcx()) {
467 ty::AliasTermKind::ProjectionTy
468 | ty::AliasTermKind::InherentTy
469 | ty::AliasTermKind::OpaqueTy
470 | ty::AliasTermKind::FreeTy => selcx.infcx.next_ty_var(cause.span).into(),
471 ty::AliasTermKind::FreeConst
472 | ty::AliasTermKind::InherentConst
473 | ty::AliasTermKind::UnevaluatedConst
474 | ty::AliasTermKind::ProjectionConst => selcx.infcx.next_const_var(cause.span).into(),
475 };
476 let mut obligations = PredicateObligations::new();
477 obligations.push(Obligation {
478 cause,
479 recursion_depth: depth,
480 param_env,
481 predicate: trait_ref.upcast(selcx.tcx()),
482 });
483 Normalized { value: new_value, obligations }
484}
485
486#[instrument(level = "debug", skip(selcx, param_env, cause, obligations))]
489pub fn normalize_inherent_projection<'a, 'b, 'tcx>(
490 selcx: &'a mut SelectionContext<'b, 'tcx>,
491 param_env: ty::ParamEnv<'tcx>,
492 alias_term: ty::AliasTerm<'tcx>,
493 cause: ObligationCause<'tcx>,
494 depth: usize,
495 obligations: &mut PredicateObligations<'tcx>,
496) -> ty::Term<'tcx> {
497 let tcx = selcx.tcx();
498
499 if !tcx.recursion_limit().value_within_limit(depth) {
500 tcx.dcx().emit_fatal(InherentProjectionNormalizationOverflow {
502 span: cause.span,
503 ty: alias_term.to_string(),
504 });
505 }
506
507 let args = compute_inherent_assoc_term_args(
508 selcx,
509 param_env,
510 alias_term,
511 cause.clone(),
512 depth,
513 obligations,
514 );
515
516 let predicates = tcx.predicates_of(alias_term.def_id).instantiate(tcx, args);
518 for (predicate, span) in predicates {
519 let predicate = normalize_with_depth_to(
520 selcx,
521 param_env,
522 cause.clone(),
523 depth + 1,
524 predicate,
525 obligations,
526 );
527
528 let nested_cause = ObligationCause::new(
529 cause.span,
530 cause.body_id,
531 ObligationCauseCode::WhereClause(alias_term.def_id, span),
536 );
537
538 obligations.push(Obligation::with_depth(
539 tcx,
540 nested_cause,
541 depth + 1,
542 param_env,
543 predicate,
544 ));
545 }
546
547 let term: Term<'tcx> = if alias_term.kind(tcx).is_type() {
548 tcx.type_of(alias_term.def_id).instantiate(tcx, args).into()
549 } else {
550 get_associated_const_value(selcx, alias_term.to_term(tcx).expect_const(), param_env).into()
551 };
552
553 let mut term = selcx.infcx.resolve_vars_if_possible(term);
554 if term.has_aliases() {
555 term =
556 normalize_with_depth_to(selcx, param_env, cause.clone(), depth + 1, term, obligations);
557 }
558
559 term
560}
561
562pub fn compute_inherent_assoc_term_args<'a, 'b, 'tcx>(
564 selcx: &'a mut SelectionContext<'b, 'tcx>,
565 param_env: ty::ParamEnv<'tcx>,
566 alias_term: ty::AliasTerm<'tcx>,
567 cause: ObligationCause<'tcx>,
568 depth: usize,
569 obligations: &mut PredicateObligations<'tcx>,
570) -> ty::GenericArgsRef<'tcx> {
571 let tcx = selcx.tcx();
572
573 let impl_def_id = tcx.parent(alias_term.def_id);
574 let impl_args = selcx.infcx.fresh_args_for_item(cause.span, impl_def_id);
575
576 let mut impl_ty = tcx.type_of(impl_def_id).instantiate(tcx, impl_args);
577 if !selcx.infcx.next_trait_solver() {
578 impl_ty = normalize_with_depth_to(
579 selcx,
580 param_env,
581 cause.clone(),
582 depth + 1,
583 impl_ty,
584 obligations,
585 );
586 }
587
588 let mut self_ty = alias_term.self_ty();
591 if !selcx.infcx.next_trait_solver() {
592 self_ty = normalize_with_depth_to(
593 selcx,
594 param_env,
595 cause.clone(),
596 depth + 1,
597 self_ty,
598 obligations,
599 );
600 }
601
602 match selcx.infcx.at(&cause, param_env).eq(DefineOpaqueTypes::Yes, impl_ty, self_ty) {
603 Ok(mut ok) => obligations.append(&mut ok.obligations),
604 Err(_) => {
605 tcx.dcx().span_bug(
606 cause.span,
607 format!("{self_ty:?} was equal to {impl_ty:?} during selection but now it is not"),
608 );
609 }
610 }
611
612 alias_term.rebase_inherent_args_onto_impl(impl_args, tcx)
613}
614
615enum Projected<'tcx> {
616 Progress(Progress<'tcx>),
617 NoProgress(ty::Term<'tcx>),
618}
619
620struct Progress<'tcx> {
621 term: ty::Term<'tcx>,
622 obligations: PredicateObligations<'tcx>,
623}
624
625impl<'tcx> Progress<'tcx> {
626 fn error_for_term(
627 tcx: TyCtxt<'tcx>,
628 alias_term: ty::AliasTerm<'tcx>,
629 guar: ErrorGuaranteed,
630 ) -> Self {
631 let err_term = if alias_term.kind(tcx).is_type() {
632 Ty::new_error(tcx, guar).into()
633 } else {
634 ty::Const::new_error(tcx, guar).into()
635 };
636 Progress { term: err_term, obligations: PredicateObligations::new() }
637 }
638
639 fn with_addl_obligations(mut self, mut obligations: PredicateObligations<'tcx>) -> Self {
640 self.obligations.append(&mut obligations);
641 self
642 }
643}
644
645#[instrument(level = "info", skip(selcx))]
651fn project<'cx, 'tcx>(
652 selcx: &mut SelectionContext<'cx, 'tcx>,
653 obligation: &ProjectionTermObligation<'tcx>,
654) -> Result<Projected<'tcx>, ProjectionError<'tcx>> {
655 if !selcx.tcx().recursion_limit().value_within_limit(obligation.recursion_depth) {
656 return Err(ProjectionError::TraitSelectionError(SelectionError::Overflow(
659 OverflowError::Canonical,
660 )));
661 }
662
663 if let Err(guar) = obligation.predicate.error_reported() {
664 return Ok(Projected::Progress(Progress::error_for_term(
665 selcx.tcx(),
666 obligation.predicate,
667 guar,
668 )));
669 }
670
671 let mut candidates = ProjectionCandidateSet::None;
672
673 assemble_candidates_from_param_env(selcx, obligation, &mut candidates);
677
678 assemble_candidates_from_trait_def(selcx, obligation, &mut candidates);
679
680 assemble_candidates_from_object_ty(selcx, obligation, &mut candidates);
681
682 if let ProjectionCandidateSet::Single(ProjectionCandidate::Object(_)) = candidates {
683 } else {
688 assemble_candidates_from_impls(selcx, obligation, &mut candidates);
689 };
690
691 match candidates {
692 ProjectionCandidateSet::Single(candidate) => {
693 confirm_candidate(selcx, obligation, candidate)
694 }
695 ProjectionCandidateSet::None => {
696 let tcx = selcx.tcx();
697 let term = obligation.predicate.to_term(tcx);
698 Ok(Projected::NoProgress(term))
699 }
700 ProjectionCandidateSet::Error(e) => Err(ProjectionError::TraitSelectionError(e)),
702 ProjectionCandidateSet::Ambiguous => Err(ProjectionError::TooManyCandidates),
705 }
706}
707
708fn assemble_candidates_from_param_env<'cx, 'tcx>(
712 selcx: &mut SelectionContext<'cx, 'tcx>,
713 obligation: &ProjectionTermObligation<'tcx>,
714 candidate_set: &mut ProjectionCandidateSet<'tcx>,
715) {
716 assemble_candidates_from_predicates(
717 selcx,
718 obligation,
719 candidate_set,
720 ProjectionCandidate::ParamEnv,
721 obligation.param_env.caller_bounds().iter(),
722 false,
723 );
724}
725
726fn assemble_candidates_from_trait_def<'cx, 'tcx>(
737 selcx: &mut SelectionContext<'cx, 'tcx>,
738 obligation: &ProjectionTermObligation<'tcx>,
739 candidate_set: &mut ProjectionCandidateSet<'tcx>,
740) {
741 debug!("assemble_candidates_from_trait_def(..)");
742 let mut ambiguous = false;
743 let _ = selcx.for_each_item_bound(
744 obligation.predicate.self_ty(),
745 |selcx, clause, _| {
746 let Some(clause) = clause.as_projection_clause() else {
747 return ControlFlow::Continue(());
748 };
749 if clause.item_def_id() != obligation.predicate.def_id {
750 return ControlFlow::Continue(());
751 }
752
753 let is_match =
754 selcx.infcx.probe(|_| selcx.match_projection_projections(obligation, clause, true));
755
756 match is_match {
757 ProjectionMatchesProjection::Yes => {
758 candidate_set.push_candidate(ProjectionCandidate::TraitDef(clause));
759
760 if !obligation.predicate.has_non_region_infer() {
761 return ControlFlow::Break(());
765 }
766 }
767 ProjectionMatchesProjection::Ambiguous => {
768 candidate_set.mark_ambiguous();
769 }
770 ProjectionMatchesProjection::No => {}
771 }
772
773 ControlFlow::Continue(())
774 },
775 || ambiguous = true,
778 );
779
780 if ambiguous {
781 candidate_set.mark_ambiguous();
782 }
783}
784
785fn assemble_candidates_from_object_ty<'cx, 'tcx>(
795 selcx: &mut SelectionContext<'cx, 'tcx>,
796 obligation: &ProjectionTermObligation<'tcx>,
797 candidate_set: &mut ProjectionCandidateSet<'tcx>,
798) {
799 debug!("assemble_candidates_from_object_ty(..)");
800
801 let tcx = selcx.tcx();
802
803 if !tcx.trait_def(obligation.predicate.trait_def_id(tcx)).implement_via_object {
804 return;
805 }
806
807 let self_ty = obligation.predicate.self_ty();
808 let object_ty = selcx.infcx.shallow_resolve(self_ty);
809 let data = match object_ty.kind() {
810 ty::Dynamic(data, ..) => data,
811 ty::Infer(ty::TyVar(_)) => {
812 candidate_set.mark_ambiguous();
815 return;
816 }
817 _ => return,
818 };
819 let env_predicates = data
820 .projection_bounds()
821 .filter(|bound| bound.item_def_id() == obligation.predicate.def_id)
822 .map(|p| p.with_self_ty(tcx, object_ty).upcast(tcx));
823
824 assemble_candidates_from_predicates(
825 selcx,
826 obligation,
827 candidate_set,
828 ProjectionCandidate::Object,
829 env_predicates,
830 false,
831 );
832}
833
834#[instrument(
835 level = "debug",
836 skip(selcx, candidate_set, ctor, env_predicates, potentially_unnormalized_candidates)
837)]
838fn assemble_candidates_from_predicates<'cx, 'tcx>(
839 selcx: &mut SelectionContext<'cx, 'tcx>,
840 obligation: &ProjectionTermObligation<'tcx>,
841 candidate_set: &mut ProjectionCandidateSet<'tcx>,
842 ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionCandidate<'tcx>,
843 env_predicates: impl Iterator<Item = ty::Clause<'tcx>>,
844 potentially_unnormalized_candidates: bool,
845) {
846 let infcx = selcx.infcx;
847 let drcx = DeepRejectCtxt::relate_rigid_rigid(selcx.tcx());
848 for predicate in env_predicates {
849 let bound_predicate = predicate.kind();
850 if let ty::ClauseKind::Projection(data) = predicate.kind().skip_binder() {
851 let data = bound_predicate.rebind(data);
852 if data.item_def_id() != obligation.predicate.def_id {
853 continue;
854 }
855
856 if !drcx
857 .args_may_unify(obligation.predicate.args, data.skip_binder().projection_term.args)
858 {
859 continue;
860 }
861
862 let is_match = infcx.probe(|_| {
863 selcx.match_projection_projections(
864 obligation,
865 data,
866 potentially_unnormalized_candidates,
867 )
868 });
869
870 match is_match {
871 ProjectionMatchesProjection::Yes => {
872 candidate_set.push_candidate(ctor(data));
873
874 if potentially_unnormalized_candidates
875 && !obligation.predicate.has_non_region_infer()
876 {
877 return;
881 }
882 }
883 ProjectionMatchesProjection::Ambiguous => {
884 candidate_set.mark_ambiguous();
885 }
886 ProjectionMatchesProjection::No => {}
887 }
888 }
889 }
890}
891
892#[instrument(level = "debug", skip(selcx, obligation, candidate_set))]
893fn assemble_candidates_from_impls<'cx, 'tcx>(
894 selcx: &mut SelectionContext<'cx, 'tcx>,
895 obligation: &ProjectionTermObligation<'tcx>,
896 candidate_set: &mut ProjectionCandidateSet<'tcx>,
897) {
898 let trait_ref = obligation.predicate.trait_ref(selcx.tcx());
901 let trait_obligation = obligation.with(selcx.tcx(), trait_ref);
902 let _ = selcx.infcx.commit_if_ok(|_| {
903 let impl_source = match selcx.select(&trait_obligation) {
904 Ok(Some(impl_source)) => impl_source,
905 Ok(None) => {
906 candidate_set.mark_ambiguous();
907 return Err(());
908 }
909 Err(e) => {
910 debug!(error = ?e, "selection error");
911 candidate_set.mark_error(e);
912 return Err(());
913 }
914 };
915
916 let eligible = match &impl_source {
917 ImplSource::UserDefined(impl_data) => {
918 match specialization_graph::assoc_def(
941 selcx.tcx(),
942 impl_data.impl_def_id,
943 obligation.predicate.def_id,
944 ) {
945 Ok(node_item) => {
946 if node_item.is_final() {
947 true
949 } else {
950 match selcx.infcx.typing_mode() {
955 TypingMode::Coherence
956 | TypingMode::Analysis { .. }
957 | TypingMode::Borrowck { .. }
958 | TypingMode::PostBorrowckAnalysis { .. } => {
959 debug!(
960 assoc_ty = ?selcx.tcx().def_path_str(node_item.item.def_id),
961 ?obligation.predicate,
962 "not eligible due to default",
963 );
964 false
965 }
966 TypingMode::PostAnalysis => {
967 let poly_trait_ref =
970 selcx.infcx.resolve_vars_if_possible(trait_ref);
971 !poly_trait_ref.still_further_specializable()
972 }
973 }
974 }
975 }
976 Err(ErrorGuaranteed { .. }) => true,
980 }
981 }
982 ImplSource::Builtin(BuiltinImplSource::Misc | BuiltinImplSource::Trivial, _) => {
983 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
987
988 let tcx = selcx.tcx();
989 match selcx.tcx().as_lang_item(trait_ref.def_id) {
990 Some(
991 LangItem::Coroutine
992 | LangItem::Future
993 | LangItem::Iterator
994 | LangItem::AsyncIterator
995 | LangItem::Fn
996 | LangItem::FnMut
997 | LangItem::FnOnce
998 | LangItem::AsyncFn
999 | LangItem::AsyncFnMut
1000 | LangItem::AsyncFnOnce,
1001 ) => true,
1002 Some(LangItem::AsyncFnKindHelper) => {
1003 if obligation.predicate.args.type_at(0).is_ty_var()
1005 || obligation.predicate.args.type_at(4).is_ty_var()
1006 || obligation.predicate.args.type_at(5).is_ty_var()
1007 {
1008 candidate_set.mark_ambiguous();
1009 true
1010 } else {
1011 obligation.predicate.args.type_at(0).to_opt_closure_kind().is_some()
1012 && obligation
1013 .predicate
1014 .args
1015 .type_at(1)
1016 .to_opt_closure_kind()
1017 .is_some()
1018 }
1019 }
1020 Some(LangItem::DiscriminantKind) => match self_ty.kind() {
1021 ty::Bool
1022 | ty::Char
1023 | ty::Int(_)
1024 | ty::Uint(_)
1025 | ty::Float(_)
1026 | ty::Adt(..)
1027 | ty::Foreign(_)
1028 | ty::Str
1029 | ty::Array(..)
1030 | ty::Pat(..)
1031 | ty::Slice(_)
1032 | ty::RawPtr(..)
1033 | ty::Ref(..)
1034 | ty::FnDef(..)
1035 | ty::FnPtr(..)
1036 | ty::Dynamic(..)
1037 | ty::Closure(..)
1038 | ty::CoroutineClosure(..)
1039 | ty::Coroutine(..)
1040 | ty::CoroutineWitness(..)
1041 | ty::Never
1042 | ty::Tuple(..)
1043 | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1045
1046 ty::UnsafeBinder(_) => todo!("FIXME(unsafe_binder)"),
1047
1048 ty::Param(_)
1052 | ty::Alias(..)
1053 | ty::Bound(..)
1054 | ty::Placeholder(..)
1055 | ty::Infer(..)
1056 | ty::Error(_) => false,
1057 },
1058 Some(LangItem::PointeeTrait) => {
1059 let tail = selcx.tcx().struct_tail_raw(
1060 self_ty,
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 Some(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, None);
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, None);
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, None);
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, None);
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.trait_of_item(item_def_id).unwrap();
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 = tcx.require_lang_item(LangItem::Discriminant, None);
1515 assert_eq!(discriminant_def_id, item_def_id);
1516
1517 (self_ty.discriminant_ty(tcx).into(), PredicateObligations::new())
1518 } else if tcx.is_lang_item(trait_def_id, LangItem::PointeeTrait) {
1519 let metadata_def_id = tcx.require_lang_item(LangItem::Metadata, None);
1520 assert_eq!(metadata_def_id, item_def_id);
1521
1522 let mut obligations = PredicateObligations::new();
1523 let normalize = |ty| {
1524 normalize_with_depth_to(
1525 selcx,
1526 obligation.param_env,
1527 obligation.cause.clone(),
1528 obligation.recursion_depth + 1,
1529 ty,
1530 &mut obligations,
1531 )
1532 };
1533 let metadata_ty = self_ty.ptr_metadata_ty_or_tail(tcx, normalize).unwrap_or_else(|tail| {
1534 if tail == self_ty {
1535 let sized_predicate = ty::TraitRef::new(
1540 tcx,
1541 tcx.require_lang_item(LangItem::Sized, Some(obligation.cause.span)),
1542 [self_ty],
1543 );
1544 obligations.push(obligation.with(tcx, sized_predicate));
1545 tcx.types.unit
1546 } else {
1547 Ty::new_projection(tcx, metadata_def_id, [tail])
1550 }
1551 });
1552 (metadata_ty.into(), obligations)
1553 } else {
1554 bug!("unexpected builtin trait with associated type: {:?}", obligation.predicate);
1555 };
1556
1557 let predicate = ty::ProjectionPredicate {
1558 projection_term: ty::AliasTerm::new_from_args(tcx, item_def_id, args),
1559 term,
1560 };
1561
1562 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1563 .with_addl_obligations(obligations)
1564 .with_addl_obligations(data)
1565}
1566
1567fn confirm_fn_pointer_candidate<'cx, 'tcx>(
1568 selcx: &mut SelectionContext<'cx, 'tcx>,
1569 obligation: &ProjectionTermObligation<'tcx>,
1570 nested: PredicateObligations<'tcx>,
1571) -> Progress<'tcx> {
1572 let tcx = selcx.tcx();
1573 let fn_type = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1574 let sig = fn_type.fn_sig(tcx);
1575 let Normalized { value: sig, obligations } = normalize_with_depth(
1576 selcx,
1577 obligation.param_env,
1578 obligation.cause.clone(),
1579 obligation.recursion_depth + 1,
1580 sig,
1581 );
1582
1583 confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
1584 .with_addl_obligations(nested)
1585 .with_addl_obligations(obligations)
1586}
1587
1588fn confirm_closure_candidate<'cx, 'tcx>(
1589 selcx: &mut SelectionContext<'cx, 'tcx>,
1590 obligation: &ProjectionTermObligation<'tcx>,
1591 nested: PredicateObligations<'tcx>,
1592) -> Progress<'tcx> {
1593 let tcx = selcx.tcx();
1594 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1595 let closure_sig = match *self_ty.kind() {
1596 ty::Closure(_, args) => args.as_closure().sig(),
1597
1598 ty::CoroutineClosure(def_id, args) => {
1602 let args = args.as_coroutine_closure();
1603 let kind_ty = args.kind_ty();
1604 args.coroutine_closure_sig().map_bound(|sig| {
1605 let output_ty = if let Some(_) = kind_ty.to_opt_closure_kind()
1609 && !args.tupled_upvars_ty().is_ty_var()
1611 {
1612 sig.to_coroutine_given_kind_and_upvars(
1613 tcx,
1614 args.parent_args(),
1615 tcx.coroutine_for_closure(def_id),
1616 ty::ClosureKind::FnOnce,
1617 tcx.lifetimes.re_static,
1618 args.tupled_upvars_ty(),
1619 args.coroutine_captures_by_ref_ty(),
1620 )
1621 } else {
1622 let upvars_projection_def_id =
1623 tcx.require_lang_item(LangItem::AsyncFnKindUpvars, None);
1624 let tupled_upvars_ty = Ty::new_projection(
1625 tcx,
1626 upvars_projection_def_id,
1627 [
1628 ty::GenericArg::from(kind_ty),
1629 Ty::from_closure_kind(tcx, ty::ClosureKind::FnOnce).into(),
1630 tcx.lifetimes.re_static.into(),
1631 sig.tupled_inputs_ty.into(),
1632 args.tupled_upvars_ty().into(),
1633 args.coroutine_captures_by_ref_ty().into(),
1634 ],
1635 );
1636 sig.to_coroutine(
1637 tcx,
1638 args.parent_args(),
1639 Ty::from_closure_kind(tcx, ty::ClosureKind::FnOnce),
1640 tcx.coroutine_for_closure(def_id),
1641 tupled_upvars_ty,
1642 )
1643 };
1644 tcx.mk_fn_sig(
1645 [sig.tupled_inputs_ty],
1646 output_ty,
1647 sig.c_variadic,
1648 sig.safety,
1649 sig.abi,
1650 )
1651 })
1652 }
1653
1654 _ => {
1655 unreachable!("expected closure self type for closure candidate, found {self_ty}");
1656 }
1657 };
1658
1659 let Normalized { value: closure_sig, obligations } = normalize_with_depth(
1660 selcx,
1661 obligation.param_env,
1662 obligation.cause.clone(),
1663 obligation.recursion_depth + 1,
1664 closure_sig,
1665 );
1666
1667 debug!(?obligation, ?closure_sig, ?obligations, "confirm_closure_candidate");
1668
1669 confirm_callable_candidate(selcx, obligation, closure_sig, util::TupleArgumentsFlag::No)
1670 .with_addl_obligations(nested)
1671 .with_addl_obligations(obligations)
1672}
1673
1674fn confirm_callable_candidate<'cx, 'tcx>(
1675 selcx: &mut SelectionContext<'cx, 'tcx>,
1676 obligation: &ProjectionTermObligation<'tcx>,
1677 fn_sig: ty::PolyFnSig<'tcx>,
1678 flag: util::TupleArgumentsFlag,
1679) -> Progress<'tcx> {
1680 let tcx = selcx.tcx();
1681
1682 debug!(?obligation, ?fn_sig, "confirm_callable_candidate");
1683
1684 let fn_once_def_id = tcx.require_lang_item(LangItem::FnOnce, None);
1685 let fn_once_output_def_id = tcx.require_lang_item(LangItem::FnOnceOutput, None);
1686
1687 let predicate = super::util::closure_trait_ref_and_return_type(
1688 tcx,
1689 fn_once_def_id,
1690 obligation.predicate.self_ty(),
1691 fn_sig,
1692 flag,
1693 )
1694 .map_bound(|(trait_ref, ret_type)| ty::ProjectionPredicate {
1695 projection_term: ty::AliasTerm::new_from_args(tcx, fn_once_output_def_id, trait_ref.args),
1696 term: ret_type.into(),
1697 });
1698
1699 confirm_param_env_candidate(selcx, obligation, predicate, true)
1700}
1701
1702fn confirm_async_closure_candidate<'cx, 'tcx>(
1703 selcx: &mut SelectionContext<'cx, 'tcx>,
1704 obligation: &ProjectionTermObligation<'tcx>,
1705 nested: PredicateObligations<'tcx>,
1706) -> Progress<'tcx> {
1707 let tcx = selcx.tcx();
1708 let self_ty = selcx.infcx.shallow_resolve(obligation.predicate.self_ty());
1709
1710 let goal_kind =
1711 tcx.async_fn_trait_kind_from_def_id(obligation.predicate.trait_def_id(tcx)).unwrap();
1712 let env_region = match goal_kind {
1713 ty::ClosureKind::Fn | ty::ClosureKind::FnMut => obligation.predicate.args.region_at(2),
1714 ty::ClosureKind::FnOnce => tcx.lifetimes.re_static,
1715 };
1716 let item_name = tcx.item_name(obligation.predicate.def_id);
1717
1718 let poly_cache_entry = match *self_ty.kind() {
1719 ty::CoroutineClosure(def_id, args) => {
1720 let args = args.as_coroutine_closure();
1721 let kind_ty = args.kind_ty();
1722 let sig = args.coroutine_closure_sig().skip_binder();
1723
1724 let term = match item_name {
1725 sym::CallOnceFuture | sym::CallRefFuture => {
1726 if let Some(closure_kind) = kind_ty.to_opt_closure_kind()
1727 && !args.tupled_upvars_ty().is_ty_var()
1729 {
1730 if !closure_kind.extends(goal_kind) {
1731 bug!("we should not be confirming if the closure kind is not met");
1732 }
1733 sig.to_coroutine_given_kind_and_upvars(
1734 tcx,
1735 args.parent_args(),
1736 tcx.coroutine_for_closure(def_id),
1737 goal_kind,
1738 env_region,
1739 args.tupled_upvars_ty(),
1740 args.coroutine_captures_by_ref_ty(),
1741 )
1742 } else {
1743 let upvars_projection_def_id =
1744 tcx.require_lang_item(LangItem::AsyncFnKindUpvars, None);
1745 let tupled_upvars_ty = Ty::new_projection(
1754 tcx,
1755 upvars_projection_def_id,
1756 [
1757 ty::GenericArg::from(kind_ty),
1758 Ty::from_closure_kind(tcx, goal_kind).into(),
1759 env_region.into(),
1760 sig.tupled_inputs_ty.into(),
1761 args.tupled_upvars_ty().into(),
1762 args.coroutine_captures_by_ref_ty().into(),
1763 ],
1764 );
1765 sig.to_coroutine(
1766 tcx,
1767 args.parent_args(),
1768 Ty::from_closure_kind(tcx, goal_kind),
1769 tcx.coroutine_for_closure(def_id),
1770 tupled_upvars_ty,
1771 )
1772 }
1773 }
1774 sym::Output => sig.return_ty,
1775 name => bug!("no such associated type: {name}"),
1776 };
1777 let projection_term = match item_name {
1778 sym::CallOnceFuture | sym::Output => ty::AliasTerm::new(
1779 tcx,
1780 obligation.predicate.def_id,
1781 [self_ty, sig.tupled_inputs_ty],
1782 ),
1783 sym::CallRefFuture => ty::AliasTerm::new(
1784 tcx,
1785 obligation.predicate.def_id,
1786 [ty::GenericArg::from(self_ty), sig.tupled_inputs_ty.into(), env_region.into()],
1787 ),
1788 name => bug!("no such associated type: {name}"),
1789 };
1790
1791 args.coroutine_closure_sig()
1792 .rebind(ty::ProjectionPredicate { projection_term, term: term.into() })
1793 }
1794 ty::FnDef(..) | ty::FnPtr(..) => {
1795 let bound_sig = self_ty.fn_sig(tcx);
1796 let sig = bound_sig.skip_binder();
1797
1798 let term = match item_name {
1799 sym::CallOnceFuture | sym::CallRefFuture => sig.output(),
1800 sym::Output => {
1801 let future_output_def_id = tcx.require_lang_item(LangItem::FutureOutput, None);
1802 Ty::new_projection(tcx, future_output_def_id, [sig.output()])
1803 }
1804 name => bug!("no such associated type: {name}"),
1805 };
1806 let projection_term = match item_name {
1807 sym::CallOnceFuture | sym::Output => ty::AliasTerm::new(
1808 tcx,
1809 obligation.predicate.def_id,
1810 [self_ty, Ty::new_tup(tcx, sig.inputs())],
1811 ),
1812 sym::CallRefFuture => ty::AliasTerm::new(
1813 tcx,
1814 obligation.predicate.def_id,
1815 [
1816 ty::GenericArg::from(self_ty),
1817 Ty::new_tup(tcx, sig.inputs()).into(),
1818 env_region.into(),
1819 ],
1820 ),
1821 name => bug!("no such associated type: {name}"),
1822 };
1823
1824 bound_sig.rebind(ty::ProjectionPredicate { projection_term, term: term.into() })
1825 }
1826 ty::Closure(_, args) => {
1827 let args = args.as_closure();
1828 let bound_sig = args.sig();
1829 let sig = bound_sig.skip_binder();
1830
1831 let term = match item_name {
1832 sym::CallOnceFuture | sym::CallRefFuture => sig.output(),
1833 sym::Output => {
1834 let future_output_def_id = tcx.require_lang_item(LangItem::FutureOutput, None);
1835 Ty::new_projection(tcx, future_output_def_id, [sig.output()])
1836 }
1837 name => bug!("no such associated type: {name}"),
1838 };
1839 let projection_term = match item_name {
1840 sym::CallOnceFuture | sym::Output => {
1841 ty::AliasTerm::new(tcx, obligation.predicate.def_id, [self_ty, sig.inputs()[0]])
1842 }
1843 sym::CallRefFuture => ty::AliasTerm::new(
1844 tcx,
1845 obligation.predicate.def_id,
1846 [ty::GenericArg::from(self_ty), sig.inputs()[0].into(), env_region.into()],
1847 ),
1848 name => bug!("no such associated type: {name}"),
1849 };
1850
1851 bound_sig.rebind(ty::ProjectionPredicate { projection_term, term: term.into() })
1852 }
1853 _ => bug!("expected callable type for AsyncFn candidate"),
1854 };
1855
1856 confirm_param_env_candidate(selcx, obligation, poly_cache_entry, true)
1857 .with_addl_obligations(nested)
1858}
1859
1860fn confirm_async_fn_kind_helper_candidate<'cx, 'tcx>(
1861 selcx: &mut SelectionContext<'cx, 'tcx>,
1862 obligation: &ProjectionTermObligation<'tcx>,
1863 nested: PredicateObligations<'tcx>,
1864) -> Progress<'tcx> {
1865 let [
1866 _closure_kind_ty,
1868 goal_kind_ty,
1869 borrow_region,
1870 tupled_inputs_ty,
1871 tupled_upvars_ty,
1872 coroutine_captures_by_ref_ty,
1873 ] = **obligation.predicate.args
1874 else {
1875 bug!();
1876 };
1877
1878 let predicate = ty::ProjectionPredicate {
1879 projection_term: ty::AliasTerm::new_from_args(
1880 selcx.tcx(),
1881 obligation.predicate.def_id,
1882 obligation.predicate.args,
1883 ),
1884 term: ty::CoroutineClosureSignature::tupled_upvars_by_closure_kind(
1885 selcx.tcx(),
1886 goal_kind_ty.expect_ty().to_opt_closure_kind().unwrap(),
1887 tupled_inputs_ty.expect_ty(),
1888 tupled_upvars_ty.expect_ty(),
1889 coroutine_captures_by_ref_ty.expect_ty(),
1890 borrow_region.expect_region(),
1891 )
1892 .into(),
1893 };
1894
1895 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1896 .with_addl_obligations(nested)
1897}
1898
1899fn confirm_param_env_candidate<'cx, 'tcx>(
1901 selcx: &mut SelectionContext<'cx, 'tcx>,
1902 obligation: &ProjectionTermObligation<'tcx>,
1903 poly_cache_entry: ty::PolyProjectionPredicate<'tcx>,
1904 potentially_unnormalized_candidate: bool,
1905) -> Progress<'tcx> {
1906 let infcx = selcx.infcx;
1907 let cause = &obligation.cause;
1908 let param_env = obligation.param_env;
1909
1910 let cache_entry = infcx.instantiate_binder_with_fresh_vars(
1911 cause.span,
1912 BoundRegionConversionTime::HigherRankedType,
1913 poly_cache_entry,
1914 );
1915
1916 let cache_projection = cache_entry.projection_term;
1917 let mut nested_obligations = PredicateObligations::new();
1918 let obligation_projection = obligation.predicate;
1919 let obligation_projection = ensure_sufficient_stack(|| {
1920 normalize_with_depth_to(
1921 selcx,
1922 obligation.param_env,
1923 obligation.cause.clone(),
1924 obligation.recursion_depth + 1,
1925 obligation_projection,
1926 &mut nested_obligations,
1927 )
1928 });
1929 let cache_projection = if potentially_unnormalized_candidate {
1930 ensure_sufficient_stack(|| {
1931 normalize_with_depth_to(
1932 selcx,
1933 obligation.param_env,
1934 obligation.cause.clone(),
1935 obligation.recursion_depth + 1,
1936 cache_projection,
1937 &mut nested_obligations,
1938 )
1939 })
1940 } else {
1941 cache_projection
1942 };
1943
1944 debug!(?cache_projection, ?obligation_projection);
1945
1946 match infcx.at(cause, param_env).eq(
1947 DefineOpaqueTypes::Yes,
1948 cache_projection,
1949 obligation_projection,
1950 ) {
1951 Ok(InferOk { value: _, obligations }) => {
1952 nested_obligations.extend(obligations);
1953 assoc_term_own_obligations(selcx, obligation, &mut nested_obligations);
1954 Progress { term: cache_entry.term, obligations: nested_obligations }
1955 }
1956 Err(e) => {
1957 let msg = format!(
1958 "Failed to unify obligation `{obligation:?}` with poly_projection `{poly_cache_entry:?}`: {e:?}",
1959 );
1960 debug!("confirm_param_env_candidate: {}", msg);
1961 let err = Ty::new_error_with_message(infcx.tcx, obligation.cause.span, msg);
1962 Progress { term: err.into(), obligations: PredicateObligations::new() }
1963 }
1964 }
1965}
1966
1967fn confirm_impl_candidate<'cx, 'tcx>(
1969 selcx: &mut SelectionContext<'cx, 'tcx>,
1970 obligation: &ProjectionTermObligation<'tcx>,
1971 impl_impl_source: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>,
1972) -> Result<Projected<'tcx>, ProjectionError<'tcx>> {
1973 let tcx = selcx.tcx();
1974
1975 let ImplSourceUserDefinedData { impl_def_id, args, mut nested } = impl_impl_source;
1976
1977 let assoc_item_id = obligation.predicate.def_id;
1978 let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
1979
1980 let param_env = obligation.param_env;
1981 let assoc_term = match specialization_graph::assoc_def(tcx, impl_def_id, assoc_item_id) {
1982 Ok(assoc_term) => assoc_term,
1983 Err(guar) => {
1984 return Ok(Projected::Progress(Progress::error_for_term(
1985 tcx,
1986 obligation.predicate,
1987 guar,
1988 )));
1989 }
1990 };
1991
1992 if !assoc_term.item.defaultness(tcx).has_value() {
1998 debug!(
1999 "confirm_impl_candidate: no associated type {:?} for {:?}",
2000 assoc_term.item.name(),
2001 obligation.predicate
2002 );
2003 if tcx.impl_self_is_guaranteed_unsized(impl_def_id) {
2004 return Ok(Projected::NoProgress(obligation.predicate.to_term(tcx)));
2009 } else {
2010 return Ok(Projected::Progress(Progress {
2011 term: if obligation.predicate.kind(tcx).is_type() {
2012 Ty::new_misc_error(tcx).into()
2013 } else {
2014 ty::Const::new_misc_error(tcx).into()
2015 },
2016 obligations: nested,
2017 }));
2018 }
2019 }
2020
2021 let args = obligation.predicate.args.rebase_onto(tcx, trait_def_id, args);
2028 let args = translate_args(selcx.infcx, param_env, impl_def_id, args, assoc_term.defining_node);
2029
2030 let term = if obligation.predicate.kind(tcx).is_type() {
2031 tcx.type_of(assoc_term.item.def_id).map_bound(|ty| ty.into())
2032 } else {
2033 ty::EarlyBinder::bind(
2034 get_associated_const_value(
2035 selcx,
2036 obligation.predicate.to_term(tcx).expect_const(),
2037 param_env,
2038 )
2039 .into(),
2040 )
2041 };
2042
2043 let progress = if !tcx.check_args_compatible(assoc_term.item.def_id, args) {
2044 let msg = "impl item and trait item have different parameters";
2045 let span = obligation.cause.span;
2046 let err = if obligation.predicate.kind(tcx).is_type() {
2047 Ty::new_error_with_message(tcx, span, msg).into()
2048 } else {
2049 ty::Const::new_error_with_message(tcx, span, msg).into()
2050 };
2051 Progress { term: err, obligations: nested }
2052 } else {
2053 assoc_term_own_obligations(selcx, obligation, &mut nested);
2054 Progress { term: term.instantiate(tcx, args), obligations: nested }
2055 };
2056 Ok(Projected::Progress(progress))
2057}
2058
2059fn assoc_term_own_obligations<'cx, 'tcx>(
2063 selcx: &mut SelectionContext<'cx, 'tcx>,
2064 obligation: &ProjectionTermObligation<'tcx>,
2065 nested: &mut PredicateObligations<'tcx>,
2066) {
2067 let tcx = selcx.tcx();
2068 let predicates = tcx
2069 .predicates_of(obligation.predicate.def_id)
2070 .instantiate_own(tcx, obligation.predicate.args);
2071 for (predicate, span) in predicates {
2072 let normalized = normalize_with_depth_to(
2073 selcx,
2074 obligation.param_env,
2075 obligation.cause.clone(),
2076 obligation.recursion_depth + 1,
2077 predicate,
2078 nested,
2079 );
2080
2081 let nested_cause = if matches!(
2082 obligation.cause.code(),
2083 ObligationCauseCode::CompareImplItem { .. }
2084 | ObligationCauseCode::CheckAssociatedTypeBounds { .. }
2085 | ObligationCauseCode::AscribeUserTypeProvePredicate(..)
2086 ) {
2087 obligation.cause.clone()
2088 } else {
2089 ObligationCause::new(
2090 obligation.cause.span,
2091 obligation.cause.body_id,
2092 ObligationCauseCode::WhereClause(obligation.predicate.def_id, span),
2093 )
2094 };
2095 nested.push(Obligation::with_depth(
2096 tcx,
2097 nested_cause,
2098 obligation.recursion_depth + 1,
2099 obligation.param_env,
2100 normalized,
2101 ));
2102 }
2103}
2104
2105pub(crate) trait ProjectionCacheKeyExt<'cx, 'tcx>: Sized {
2106 fn from_poly_projection_obligation(
2107 selcx: &mut SelectionContext<'cx, 'tcx>,
2108 obligation: &PolyProjectionObligation<'tcx>,
2109 ) -> Option<Self>;
2110}
2111
2112impl<'cx, 'tcx> ProjectionCacheKeyExt<'cx, 'tcx> for ProjectionCacheKey<'tcx> {
2113 fn from_poly_projection_obligation(
2114 selcx: &mut SelectionContext<'cx, 'tcx>,
2115 obligation: &PolyProjectionObligation<'tcx>,
2116 ) -> Option<Self> {
2117 let infcx = selcx.infcx;
2118 obligation.predicate.no_bound_vars().map(|predicate| {
2121 ProjectionCacheKey::new(
2122 infcx.resolve_vars_if_possible(predicate.projection_term),
2127 obligation.param_env,
2128 )
2129 })
2130 }
2131}
2132
2133fn get_associated_const_value<'tcx>(
2134 selcx: &mut SelectionContext<'_, 'tcx>,
2135 alias_ct: ty::Const<'tcx>,
2136 param_env: ty::ParamEnv<'tcx>,
2137) -> ty::Const<'tcx> {
2138 super::evaluate_const(selcx.infcx, alias_ct, param_env)
2143}