rustc_trait_selection/traits/
project.rs

1//! Code for projecting associated types out of trait references.
2
3use 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/// When attempting to resolve `<T as TraitRef>::Name` ...
42#[derive(Debug)]
43pub enum ProjectionError<'tcx> {
44    /// ...we found multiple sources of information and couldn't resolve the ambiguity.
45    TooManyCandidates,
46
47    /// ...an error occurred matching `T : TraitRef`
48    TraitSelectionError(SelectionError<'tcx>),
49}
50
51#[derive(PartialEq, Eq, Debug)]
52enum ProjectionCandidate<'tcx> {
53    /// From a where-clause in the env or object type
54    ParamEnv(ty::PolyProjectionPredicate<'tcx>),
55
56    /// From the definition of `Trait` when you have something like
57    /// `<<A as Trait>::B as Trait2>::C`.
58    TraitDef(ty::PolyProjectionPredicate<'tcx>),
59
60    /// Bounds specified on an object type
61    Object(ty::PolyProjectionPredicate<'tcx>),
62
63    /// From an "impl" (or a "pseudo-impl" returned by select)
64    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    // Returns true if the push was successful, or false if the candidate
84    // was discarded -- this could be because of ambiguity, or because
85    // a higher-priority candidate is already there.
86    fn push_candidate(&mut self, candidate: ProjectionCandidate<'tcx>) -> bool {
87        use self::ProjectionCandidate::*;
88        use self::ProjectionCandidateSet::*;
89
90        // This wacky variable is just used to try and
91        // make code readable and avoid confusing paths.
92        // It is assigned a "value" of `()` only on those
93        // paths in which we wish to convert `*self` to
94        // ambiguous (and return false, because the candidate
95        // was not used). On other paths, it is not assigned,
96        // and hence if those paths *could* reach the code that
97        // comes after the match, this fn would not compile.
98        let convert_to_ambiguous;
99
100        match self {
101            None => {
102                *self = Single(candidate);
103                return true;
104            }
105
106            Single(current) => {
107                // Duplicates can happen inside ParamEnv. In the case, we
108                // perform a lazy deduplication.
109                if current == &candidate {
110                    return false;
111                }
112
113                // Prefer where-clauses. As in select, if there are multiple
114                // candidates, we prefer where-clause candidates over impls. This
115                // may seem a bit surprising, since impls are the source of
116                // "truth" in some sense, but in fact some of the impls that SEEM
117                // applicable are not, because of nested obligations. Where
118                // clauses are the safer choice. See the comment on
119                // `select::SelectionCandidate` and #21974 for more details.
120                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        // We only ever get here when we moved from a single candidate
136        // to ambiguous.
137        let () = convert_to_ambiguous;
138        *self = Ambiguous;
139        false
140    }
141}
142
143/// States returned from `poly_project_and_unify_type`. Takes the place
144/// of the old return type, which was:
145/// ```ignore (not-rust)
146/// Result<
147///     Result<Option<PredicateObligations<'tcx>>, InProgress>,
148///     MismatchedProjectionTypes<'tcx>,
149/// >
150/// ```
151pub(super) enum ProjectAndUnifyResult<'tcx> {
152    /// The projection bound holds subject to the given obligations. If the
153    /// projection cannot be normalized because the required trait bound does
154    /// not hold, this is returned, with `obligations` being a predicate that
155    /// cannot be proven.
156    Holds(PredicateObligations<'tcx>),
157    /// The projection cannot be normalized due to ambiguity. Resolving some
158    /// inference variables in the projection may fix this.
159    FailedNormalization,
160    /// The project cannot be normalized because `poly_project_and_unify_type`
161    /// is called recursively while normalizing the same projection.
162    Recursive,
163    // the projection can be normalized, but is not equal to the expected type.
164    // Returns the type error that arose from the mismatch.
165    MismatchedProjectionTypes(MismatchedProjectionTypes<'tcx>),
166}
167
168/// Evaluates constraints of the form:
169/// ```ignore (not-rust)
170/// for<...> <T as Trait>::U == V
171/// ```
172/// If successful, this may result in additional obligations. Also returns
173/// the projection cache key used to track these additional obligations.
174// FIXME(mgca): While this supports constants, it is only used for types by default right now
175#[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/// Evaluates constraints of the form:
198/// ```ignore (not-rust)
199/// <T as Trait>::U == V
200/// ```
201/// If successful, this may result in additional obligations.
202///
203/// See [poly_project_and_unify_term] for an explanation of the return value.
204// FIXME(mgca): While this supports constants, it is only used for types by default right now
205#[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    // For an example where this is necessary see tests/ui/impl-trait/nested-return-type2.rs
228    // This allows users to omit re-mentioning all bounds on an associated type and just use an
229    // `impl Trait` for the assoc type to add more bounds.
230    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    // Need to define opaque types to support nested opaque types like `impl Fn() -> impl Trait`
240    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
256/// The guts of `normalize`: normalize a specific projection like `<T
257/// as Trait>::Item`. The result is always a type (and possibly
258/// additional obligations). If ambiguity arises, which implies that
259/// there are unresolved type variables in the projection, we will
260/// instantiate it with a fresh type variable `$X` and generate a new
261/// obligation `<T as Trait>::Item == $X` for later.
262// FIXME(mgca): While this supports constants, it is only used for types by default right now
263pub 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            // if we bottom out in ambiguity, create a type variable
276            // and a deferred predicate to resolve this when more type
277            // information is available.
278
279            selcx
280                .infcx
281                .projection_term_to_infer(param_env, alias_term, cause, depth + 1, obligations)
282                .into()
283        })
284}
285
286/// The guts of `normalize`: normalize a specific projection like `<T
287/// as Trait>::Item`. The result is always a type (and possibly
288/// additional obligations). Returns `None` in the case of ambiguity,
289/// which indicates that there are unbound type variables.
290///
291/// This function used to return `Option<NormalizedTy<'tcx>>`, which contains a
292/// `Ty<'tcx>` and an obligations vector. But that obligation vector was very
293/// often immediately appended to another obligations vector. So now this
294/// function takes an obligations vector and appends to it directly, which is
295/// slightly uglier but avoids the need for an extra short-lived allocation.
296// FIXME(mgca): While this supports constants, it is only used for types by default right now
297#[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    // FIXME(#20304) For now, I am caching here, which is good, but it
312    // means we don't capture the type variables that are created in
313    // the case of ambiguity. Which means we may create a large stream
314    // of such variables. OTOH, if we move the caching up a level, we
315    // would not benefit from caching when proving `T: Trait<U=Foo>`
316    // bounds. It might be the case that we want two distinct caches,
317    // or else another kind of cache entry.
318    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            // If we found ambiguity the last time, that means we will continue
323            // to do so until some type in the key changes (and we know it
324            // hasn't, because we just fully resolved it).
325            debug!("found cache entry: ambiguous");
326            return Ok(None);
327        }
328        Err(ProjectionCacheEntry::InProgress) => {
329            // Under lazy normalization, this can arise when
330            // bootstrapping. That is, imagine an environment with a
331            // where-clause like `A::B == u32`. Now, if we are asked
332            // to normalize `A::B`, we will want to check the
333            // where-clauses in scope. So we will try to unify `A::B`
334            // with `A::B`, which can trigger a recursive
335            // normalization.
336
337            debug!("found cache entry: in-progress");
338
339            // Cache that normalizing this projection resulted in a cycle. This
340            // should ensure that, unless this happens within a snapshot that's
341            // rolled back, fulfillment or evaluation will notice the cycle.
342            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            // This is the hottest path in this function.
351            //
352            // If we find the value in the cache, then return it along
353            // with the obligations that went along with it. Note
354            // that, when using a fulfillment context, these
355            // obligations could in principle be ignored: they have
356            // already been registered when the cache entry was
357            // created (and hence the new ones will quickly be
358            // discarded as duplicated). But when doing trait
359            // evaluation this is not the case, and dropping the trait
360            // evaluations can causes ICEs (e.g., #43132).
361            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            // if projection succeeded, then what we get out of this
383            // is also non-normalized (consider: it was derived from
384            // an impl, where-clause etc) and hence we must
385            // re-normalize it
386
387            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            // No need to extend `obligations`.
417            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            // if we got an error processing the `T as Trait` part,
427            // just return `ty::err` but add the obligation `T :
428            // Trait`, which when processed will cause the error to be
429            // reported later
430            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
438/// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not
439/// hold. In various error cases, we cannot generate a valid
440/// normalized projection. Therefore, we create an inference variable
441/// return an associated obligation that, when fulfilled, will lead to
442/// an error.
443///
444/// Note that we used to return `Error` here, but that was quite
445/// dubious -- the premise was that an error would *eventually* be
446/// reported, when the obligation was processed. But in general once
447/// you see an `Error` you are supposed to be able to assume that an
448/// error *has been* reported, so that you can take whatever heuristic
449/// paths you want to take. To make things worse, it was possible for
450/// cycles to arise, where you basically had a setup like `<MyType<$0>
451/// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as
452/// Trait>::Foo>` to `[type error]` would lead to an obligation of
453/// `<MyType<[type error]> as Trait>::Foo`. We are supposed to report
454/// an error for this obligation, but we legitimately should not,
455/// because it contains `[type error]`. Yuck! (See issue #29857 for
456/// one case where this arose.)
457// FIXME(mgca): While this supports constants, it is only used for types by default right now
458fn 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/// Confirm and normalize the given inherent projection.
487// FIXME(mgca): While this supports constants, it is only used for types by default right now
488#[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        // Halt compilation because it is important that overflows never be masked.
501        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    // Register the obligations arising from the impl and from the associated type itself.
517    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            // FIXME(inherent_associated_types): Since we can't pass along the self type to the
532            // cause code, inherent projections will be printed with identity instantiation in
533            // diagnostics which is not ideal.
534            // Consider creating separate cause codes for this specific situation.
535            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
562// FIXME(mgca): While this supports constants, it is only used for types by default right now
563pub 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    // Infer the generic parameters of the impl by unifying the
589    // impl type with the self type of the projection.
590    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/// Computes the result of a projection type (if we can).
646///
647/// IMPORTANT:
648/// - `obligation` must be fully normalized
649// FIXME(mgca): While this supports constants, it is only used for types by default right now
650#[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        // This should really be an immediate error, but some existing code
657        // relies on being able to recover from this.
658        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    // Make sure that the following procedures are kept in order. ParamEnv
674    // needs to be first because it has highest priority, and Select checks
675    // the return value of push_candidate which assumes it's ran at last.
676    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        // Avoid normalization cycle from selection (see
684        // `assemble_candidates_from_object_ty`).
685        // FIXME(lazy_normalization): Lazy normalization should save us from
686        // having to special case this.
687    } 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        // Error occurred while trying to processing impls.
701        ProjectionCandidateSet::Error(e) => Err(ProjectionError::TraitSelectionError(e)),
702        // Inherent ambiguity that prevents us from even enumerating the
703        // candidates.
704        ProjectionCandidateSet::Ambiguous => Err(ProjectionError::TooManyCandidates),
705    }
706}
707
708/// The first thing we have to do is scan through the parameter
709/// environment to see whether there are any projection predicates
710/// there that can answer this question.
711fn 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
726/// In the case of a nested projection like `<<A as Foo>::FooT as Bar>::BarT`, we may find
727/// that the definition of `Foo` has some clues:
728///
729/// ```ignore (illustrative)
730/// trait Foo {
731///     type FooT : Bar<BarT=i32>
732/// }
733/// ```
734///
735/// Here, for example, we could conclude that the result is `i32`.
736fn 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                        // HACK: Pick the first trait def candidate for a fully
762                        // inferred predicate. This is to allow duplicates that
763                        // differ only in normalization.
764                        return ControlFlow::Break(());
765                    }
766                }
767                ProjectionMatchesProjection::Ambiguous => {
768                    candidate_set.mark_ambiguous();
769                }
770                ProjectionMatchesProjection::No => {}
771            }
772
773            ControlFlow::Continue(())
774        },
775        // `ProjectionCandidateSet` is borrowed in the above closure,
776        // so just mark ambiguous outside of the closure.
777        || ambiguous = true,
778    );
779
780    if ambiguous {
781        candidate_set.mark_ambiguous();
782    }
783}
784
785/// In the case of a trait object like
786/// `<dyn Iterator<Item = ()> as Iterator>::Item` we can use the existential
787/// predicate in the trait object.
788///
789/// We don't go through the select candidate for these bounds to avoid cycles:
790/// In the above case, `dyn Iterator<Item = ()>: Iterator` would create a
791/// nested obligation of `<dyn Iterator<Item = ()> as Iterator>::Item: Sized`,
792/// this then has to be normalized without having to prove
793/// `dyn Iterator<Item = ()>: Iterator` again.
794fn 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            // If the self-type is an inference variable, then it MAY wind up
813            // being an object type, so induce an ambiguity.
814            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                        // HACK: Pick the first trait def candidate for a fully
878                        // inferred predicate. This is to allow duplicates that
879                        // differ only in normalization.
880                        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    // If we are resolving `<T as TraitRef<...>>::Item == Type`,
899    // start out by selecting the predicate `T as TraitRef<...>`:
900    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                // We have to be careful when projecting out of an
919                // impl because of specialization. If we are not in
920                // codegen (i.e., `TypingMode` is not `PostAnalysis`), and the
921                // impl's type is declared as default, then we disable
922                // projection (even if the trait ref is fully
923                // monomorphic). In the case where trait ref is not
924                // fully monomorphic (i.e., includes type parameters),
925                // this is because those type parameters may
926                // ultimately be bound to types from other crates that
927                // may have specialized impls we can't see. In the
928                // case where the trait ref IS fully monomorphic, this
929                // is a policy decision that we made in the RFC in
930                // order to preserve flexibility for the crate that
931                // defined the specializable impl to specialize later
932                // for existing types.
933                //
934                // In either case, we handle this by not adding a
935                // candidate for an impl if it contains a `default`
936                // type.
937                //
938                // NOTE: This should be kept in sync with the similar code in
939                // `rustc_ty_utils::instance::resolve_associated_item()`.
940                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                            // Non-specializable items are always projectable.
948                            true
949                        } else {
950                            // Only reveal a specializable default if we're past type-checking
951                            // and the obligation is monomorphic, otherwise passes such as
952                            // transmute checking and polymorphic MIR optimizations could
953                            // get a result which isn't correct for all monomorphizations.
954                            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                                    // NOTE(eddyb) inference variables can resolve to parameters, so
968                                    // assume `poly_trait_ref` isn't monomorphic, if it contains any.
969                                    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                    // Always project `ErrorGuaranteed`, since this will just help
977                    // us propagate `TyKind::Error` around which suppresses ICEs
978                    // and spurious, unrelated inference errors.
979                    Err(ErrorGuaranteed { .. }) => true,
980                }
981            }
982            ImplSource::Builtin(BuiltinImplSource::Misc | BuiltinImplSource::Trivial, _) => {
983                // While a builtin impl may be known to exist, the associated type may not yet
984                // be known. Any type with multiple potential associated types is therefore
985                // not eligible.
986                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                        // FIXME(async_closures): Validity constraints here could be cleaned up.
1004                        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                        // Integers and floats always have `u8` as their discriminant.
1044                        | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1045
1046                        ty::UnsafeBinder(_) => todo!("FIXME(unsafe_binder)"),
1047
1048                        // type parameters, opaques, and unnormalized projections don't have
1049                        // a known discriminant and may need to be normalized further or rely
1050                        // on param env for discriminant projections
1051                        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                                // We throw away any obligations we get from this, since we normalize
1063                                // and confirm these obligations once again during confirmation
1064                                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                            // Extern types have unit metadata, according to RFC 2850
1097                            | ty::Foreign(_)
1098                            // If returned by `struct_tail` this is a unit struct
1099                            // without any fields, or not a struct, and therefore is Sized.
1100                            | ty::Adt(..)
1101                            // If returned by `struct_tail` this is the empty tuple.
1102                            | ty::Tuple(..)
1103                            // Integers and floats are always Sized, and so have unit type metadata.
1104                            | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..))
1105                            // This happens if we reach the recursion limit when finding the struct tail.
1106                            | ty::Error(..) => true,
1107
1108                            // We normalize from `Wrapper<Tail>::Metadata` to `Tail::Metadata` if able.
1109                            // Otherwise, type parameters, opaques, and unnormalized projections have
1110                            // unit metadata if they're known (e.g. by the param_env) to be sized.
1111                            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                            // FIXME(compiler-errors): are Bound and Placeholder types ever known sized?
1133                            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                // This case tell us nothing about the value of an
1159                // associated type. Consider:
1160                //
1161                // ```
1162                // trait SomeTrait { type Foo; }
1163                // fn foo<T:SomeTrait>(...) { }
1164                // ```
1165                //
1166                // If the user writes `<T as SomeTrait>::Foo`, then the `T
1167                // : SomeTrait` binding does not help us decide what the
1168                // type `Foo` is (at least, not more specifically than
1169                // what we already knew).
1170                //
1171                // But wait, you say! What about an example like this:
1172                //
1173                // ```
1174                // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
1175                // ```
1176                //
1177                // Doesn't the `T : SomeTrait<Foo=usize>` predicate help
1178                // resolve `T::Foo`? And of course it does, but in fact
1179                // that single predicate is desugared into two predicates
1180                // in the compiler: a trait predicate (`T : SomeTrait`) and a
1181                // projection. And the projection where clause is handled
1182                // in `assemble_candidates_from_param_env`.
1183                false
1184            }
1185            ImplSource::Builtin(BuiltinImplSource::Object { .. }, _) => {
1186                // Handled by the `Object` projection candidate. See
1187                // `assemble_candidates_from_object_ty` for an explanation of
1188                // why we special case object types.
1189                false
1190            }
1191            ImplSource::Builtin(BuiltinImplSource::TraitUpcasting { .. }, _) => {
1192                // These traits have no associated types.
1193                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
1213// FIXME(mgca): While this supports constants, it is only used for types by default right now
1214fn 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    // When checking for cycle during evaluation, we compare predicates with
1234    // "syntactic" equality. Since normalization generally introduces a type
1235    // with new region variables, we need to resolve them to existing variables
1236    // when possible for this to work. See `auto-trait-projection-recursion.rs`
1237    // for a case where this matters.
1238    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
1247// FIXME(mgca): While this supports constants, it is only used for types by default right now
1248fn 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            // we don't create Select candidates with this kind of resolution
1287            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                // This is the "fallback impl" for type parameters, unnormalizable projections
1536                // and opaque types: If the `self_ty` is `Sized`, then the metadata is `()`.
1537                // FIXME(ptr_metadata): This impl overlaps with the other impls and shouldn't
1538                // exist. Instead, `Pointee<Metadata = ()>` should be a supertrait of `Sized`.
1539                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                // We know that `self_ty` has the same metadata as `tail`. This allows us
1548                // to prove predicates like `Wrapper<Tail>::Metadata == Tail::Metadata`.
1549                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        // Construct a "normal" `FnOnce` signature for coroutine-closure. This is
1599        // basically duplicated with the `AsyncFnOnce::CallOnce` confirmation, but
1600        // I didn't see a good way to unify those.
1601        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                // If we know the kind and upvars, use that directly.
1606                // Otherwise, defer to `AsyncFnKindHelper::Upvars` to delay
1607                // the projection, like the `AsyncFn*` traits do.
1608                let output_ty = if let Some(_) = kind_ty.to_opt_closure_kind()
1609                    // Fall back to projection if upvars aren't constrained
1610                    && !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                        // Fall back to projection if upvars aren't constrained
1728                        && !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                        // When we don't know the closure kind (and therefore also the closure's upvars,
1746                        // which are computed at the same time), we must delay the computation of the
1747                        // generator's upvars. We do this using the `AsyncFnKindHelper`, which as a trait
1748                        // goal functions similarly to the old `ClosureKind` predicate, and ensures that
1749                        // the goal kind <= the closure kind. As a projection `AsyncFnKindHelper::Upvars`
1750                        // will project to the right upvars for the generator, appending the inputs and
1751                        // coroutine upvars respecting the closure kind.
1752                        // N.B. No need to register a `AsyncFnKindHelper` goal here, it's already in `nested`.
1753                        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        // We already checked that the goal_kind >= closure_kind
1867        _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
1899// FIXME(mgca): While this supports constants, it is only used for types by default right now
1900fn 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
1967// FIXME(mgca): While this supports constants, it is only used for types by default right now
1968fn 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    // This means that the impl is missing a definition for the
1993    // associated type. This is either because the associate item
1994    // has impossible-to-satisfy predicates (since those were
1995    // allowed in <https://github.com/rust-lang/rust/pull/135480>),
1996    // or because the impl is literally missing the definition.
1997    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            // We treat this projection as rigid here, which is represented via
2005            // `Projected::NoProgress`. This will ensure that the projection is
2006            // checked for well-formedness, and it's either satisfied by a trivial
2007            // where clause in its env or it results in an error.
2008            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    // If we're trying to normalize `<Vec<u32> as X>::A<S>` using
2022    //`impl<T> X for Vec<T> { type A<Y> = Box<Y>; }`, then:
2023    //
2024    // * `obligation.predicate.args` is `[Vec<u32>, S]`
2025    // * `args` is `[u32]`
2026    // * `args` ends up as `[u32, S]`
2027    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
2059// Get obligations corresponding to the predicates from the where-clause of the
2060// associated type itself.
2061// FIXME(mgca): While this supports constants, it is only used for types by default right now
2062fn 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        // We don't do cross-snapshot caching of obligations with escaping regions,
2119        // so there's no cache key to use
2120        obligation.predicate.no_bound_vars().map(|predicate| {
2121            ProjectionCacheKey::new(
2122                // We don't attempt to match up with a specific type-variable state
2123                // from a specific call to `opt_normalize_projection_type` - if
2124                // there's no precise match, the original cache entry is "stranded"
2125                // anyway.
2126                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    // FIXME(mgca): We shouldn't be invoking ctfe here, instead const items should be aliases to type
2139    // system consts that we can retrieve with some `query const_arg_of_alias` query. Evaluating the
2140    // constant is "close enough" to getting the actual rhs of the const item for now even if it might
2141    // lead to some cycles
2142    super::evaluate_const(selcx.infcx, alias_ct, param_env)
2143}