rustc_next_trait_solver/solve/normalizes_to/
mod.rs

1mod anon_const;
2mod free_alias;
3mod inherent;
4mod opaque_types;
5
6use rustc_type_ir::fast_reject::DeepRejectCtxt;
7use rustc_type_ir::inherent::*;
8use rustc_type_ir::lang_items::TraitSolverLangItem;
9use rustc_type_ir::solve::SizedTraitKind;
10use rustc_type_ir::{self as ty, Interner, NormalizesTo, PredicateKind, Upcast as _};
11use tracing::instrument;
12
13use crate::delegate::SolverDelegate;
14use crate::solve::assembly::structural_traits::{self, AsyncCallableRelevantTypes};
15use crate::solve::assembly::{self, Candidate};
16use crate::solve::inspect::ProbeKind;
17use crate::solve::{
18    BuiltinImplSource, CandidateSource, Certainty, EvalCtxt, Goal, GoalSource, MaybeCause,
19    NoSolution, QueryResult,
20};
21
22impl<D, I> EvalCtxt<'_, D>
23where
24    D: SolverDelegate<Interner = I>,
25    I: Interner,
26{
27    #[instrument(level = "trace", skip(self), ret)]
28    pub(super) fn compute_normalizes_to_goal(
29        &mut self,
30        goal: Goal<I, NormalizesTo<I>>,
31    ) -> QueryResult<I> {
32        debug_assert!(self.term_is_fully_unconstrained(goal));
33        let cx = self.cx();
34        match goal.predicate.alias.kind(cx) {
35            ty::AliasTermKind::ProjectionTy | ty::AliasTermKind::ProjectionConst => {
36                let trait_ref = goal.predicate.alias.trait_ref(cx);
37                let (_, proven_via) =
38                    self.probe(|_| ProbeKind::ShadowedEnvProbing).enter(|ecx| {
39                        let trait_goal: Goal<I, ty::TraitPredicate<I>> = goal.with(cx, trait_ref);
40                        ecx.compute_trait_goal(trait_goal)
41                    })?;
42                self.assemble_and_merge_candidates(proven_via, goal, |ecx| {
43                    ecx.probe(|&result| ProbeKind::RigidAlias { result }).enter(|this| {
44                        this.structurally_instantiate_normalizes_to_term(
45                            goal,
46                            goal.predicate.alias,
47                        );
48                        this.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
49                    })
50                })
51            }
52            ty::AliasTermKind::InherentTy | ty::AliasTermKind::InherentConst => {
53                self.normalize_inherent_associated_term(goal)
54            }
55            ty::AliasTermKind::OpaqueTy => self.normalize_opaque_type(goal),
56            ty::AliasTermKind::FreeTy | ty::AliasTermKind::FreeConst => {
57                self.normalize_free_alias(goal)
58            }
59            ty::AliasTermKind::UnevaluatedConst => self.normalize_anon_const(goal),
60        }
61    }
62
63    /// When normalizing an associated item, constrain the expected term to `term`.
64    ///
65    /// We know `term` to always be a fully unconstrained inference variable, so
66    /// `eq` should never fail here. However, in case `term` contains aliases, we
67    /// emit nested `AliasRelate` goals to structurally normalize the alias.
68    pub fn instantiate_normalizes_to_term(
69        &mut self,
70        goal: Goal<I, NormalizesTo<I>>,
71        term: I::Term,
72    ) {
73        self.eq(goal.param_env, goal.predicate.term, term)
74            .expect("expected goal term to be fully unconstrained");
75    }
76
77    /// Unlike `instantiate_normalizes_to_term` this instantiates the expected term
78    /// with a rigid alias. Using this is pretty much always wrong.
79    pub fn structurally_instantiate_normalizes_to_term(
80        &mut self,
81        goal: Goal<I, NormalizesTo<I>>,
82        term: ty::AliasTerm<I>,
83    ) {
84        self.relate_rigid_alias_non_alias(goal.param_env, term, ty::Invariant, goal.predicate.term)
85            .expect("expected goal term to be fully unconstrained");
86    }
87}
88
89impl<D, I> assembly::GoalKind<D> for NormalizesTo<I>
90where
91    D: SolverDelegate<Interner = I>,
92    I: Interner,
93{
94    fn self_ty(self) -> I::Ty {
95        self.self_ty()
96    }
97
98    fn trait_ref(self, cx: I) -> ty::TraitRef<I> {
99        self.alias.trait_ref(cx)
100    }
101
102    fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self {
103        self.with_self_ty(cx, self_ty)
104    }
105
106    fn trait_def_id(self, cx: I) -> I::DefId {
107        self.trait_def_id(cx)
108    }
109
110    fn fast_reject_assumption(
111        ecx: &mut EvalCtxt<'_, D>,
112        goal: Goal<I, Self>,
113        assumption: I::Clause,
114    ) -> Result<(), NoSolution> {
115        if let Some(projection_pred) = assumption.as_projection_clause() {
116            if projection_pred.item_def_id() == goal.predicate.def_id() {
117                if DeepRejectCtxt::relate_rigid_rigid(ecx.cx()).args_may_unify(
118                    goal.predicate.alias.args,
119                    projection_pred.skip_binder().projection_term.args,
120                ) {
121                    return Ok(());
122                }
123            }
124        }
125
126        Err(NoSolution)
127    }
128
129    fn match_assumption(
130        ecx: &mut EvalCtxt<'_, D>,
131        goal: Goal<I, Self>,
132        assumption: I::Clause,
133        then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
134    ) -> QueryResult<I> {
135        let cx = ecx.cx();
136        // FIXME(generic_associated_types): Addresses aggressive inference in #92917.
137        //
138        // If this type is a GAT with currently unconstrained arguments, we do not
139        // want to normalize it via a candidate which only applies for a specific
140        // instantiation. We could otherwise keep the GAT as rigid and succeed this way.
141        // See tests/ui/generic-associated-types/no-incomplete-gat-arg-inference.rs.
142        //
143        // This only avoids normalization if the GAT arguments are fully unconstrained.
144        // This is quite arbitrary but fixing it causes some ambiguity, see #125196.
145        match goal.predicate.alias.kind(cx) {
146            ty::AliasTermKind::ProjectionTy | ty::AliasTermKind::ProjectionConst => {
147                for arg in goal.predicate.alias.own_args(cx).iter() {
148                    let Some(term) = arg.as_term() else {
149                        continue;
150                    };
151                    let term = ecx.structurally_normalize_term(goal.param_env, term)?;
152                    if term.is_infer() {
153                        return ecx.evaluate_added_goals_and_make_canonical_response(
154                            Certainty::AMBIGUOUS,
155                        );
156                    }
157                }
158            }
159            ty::AliasTermKind::OpaqueTy
160            | ty::AliasTermKind::InherentTy
161            | ty::AliasTermKind::InherentConst
162            | ty::AliasTermKind::FreeTy
163            | ty::AliasTermKind::FreeConst
164            | ty::AliasTermKind::UnevaluatedConst => {}
165        }
166
167        let projection_pred = assumption.as_projection_clause().unwrap();
168
169        let assumption_projection_pred = ecx.instantiate_binder_with_infer(projection_pred);
170        ecx.eq(goal.param_env, goal.predicate.alias, assumption_projection_pred.projection_term)?;
171
172        ecx.instantiate_normalizes_to_term(goal, assumption_projection_pred.term);
173
174        // Add GAT where clauses from the trait's definition
175        // FIXME: We don't need these, since these are the type's own WF obligations.
176        ecx.add_goals(
177            GoalSource::AliasWellFormed,
178            cx.own_predicates_of(goal.predicate.def_id())
179                .iter_instantiated(cx, goal.predicate.alias.args)
180                .map(|pred| goal.with(cx, pred)),
181        );
182
183        then(ecx)
184    }
185
186    fn consider_additional_alias_assumptions(
187        _ecx: &mut EvalCtxt<'_, D>,
188        _goal: Goal<I, Self>,
189        _alias_ty: ty::AliasTy<I>,
190    ) -> Vec<Candidate<I>> {
191        vec![]
192    }
193
194    fn consider_impl_candidate(
195        ecx: &mut EvalCtxt<'_, D>,
196        goal: Goal<I, NormalizesTo<I>>,
197        impl_def_id: I::DefId,
198    ) -> Result<Candidate<I>, NoSolution> {
199        let cx = ecx.cx();
200
201        let goal_trait_ref = goal.predicate.alias.trait_ref(cx);
202        let impl_trait_ref = cx.impl_trait_ref(impl_def_id);
203        if !DeepRejectCtxt::relate_rigid_infer(ecx.cx()).args_may_unify(
204            goal.predicate.alias.trait_ref(cx).args,
205            impl_trait_ref.skip_binder().args,
206        ) {
207            return Err(NoSolution);
208        }
209
210        // We have to ignore negative impls when projecting.
211        let impl_polarity = cx.impl_polarity(impl_def_id);
212        match impl_polarity {
213            ty::ImplPolarity::Negative => return Err(NoSolution),
214            ty::ImplPolarity::Reservation => {
215                unimplemented!("reservation impl for trait with assoc item: {:?}", goal)
216            }
217            ty::ImplPolarity::Positive => {}
218        };
219
220        ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| {
221            let impl_args = ecx.fresh_args_for_item(impl_def_id);
222            let impl_trait_ref = impl_trait_ref.instantiate(cx, impl_args);
223
224            ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?;
225
226            let where_clause_bounds = cx
227                .predicates_of(impl_def_id)
228                .iter_instantiated(cx, impl_args)
229                .map(|pred| goal.with(cx, pred));
230            ecx.add_goals(GoalSource::ImplWhereBound, where_clause_bounds);
231
232            // Bail if the nested goals don't hold here. This is to avoid unnecessarily
233            // computing the `type_of` query for associated types that never apply, as
234            // this may result in query cycles in the case of RPITITs.
235            // See <https://github.com/rust-lang/trait-system-refactor-initiative/issues/185>.
236            ecx.try_evaluate_added_goals()?;
237
238            // Add GAT where clauses from the trait's definition.
239            // FIXME: We don't need these, since these are the type's own WF obligations.
240            ecx.add_goals(
241                GoalSource::AliasWellFormed,
242                cx.own_predicates_of(goal.predicate.def_id())
243                    .iter_instantiated(cx, goal.predicate.alias.args)
244                    .map(|pred| goal.with(cx, pred)),
245            );
246
247            let error_response = |ecx: &mut EvalCtxt<'_, D>, guar| {
248                let error_term = match goal.predicate.alias.kind(cx) {
249                    ty::AliasTermKind::ProjectionTy => Ty::new_error(cx, guar).into(),
250                    ty::AliasTermKind::ProjectionConst => Const::new_error(cx, guar).into(),
251                    kind => panic!("expected projection, found {kind:?}"),
252                };
253                ecx.instantiate_normalizes_to_term(goal, error_term);
254                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
255            };
256
257            let target_item_def_id = match ecx.fetch_eligible_assoc_item(
258                goal_trait_ref,
259                goal.predicate.def_id(),
260                impl_def_id,
261            ) {
262                Ok(Some(target_item_def_id)) => target_item_def_id,
263                Ok(None) => {
264                    match ecx.typing_mode() {
265                        // In case the associated item is hidden due to specialization,
266                        // normalizing this associated item is always ambiguous. Treating
267                        // the associated item as rigid would be incomplete and allow for
268                        // overlapping impls, see #105782.
269                        //
270                        // As this ambiguity is unavoidable we emit a nested ambiguous
271                        // goal instead of using `Certainty::AMBIGUOUS`. This allows us to
272                        // return the nested goals to the parent `AliasRelate` goal. This
273                        // would be relevant if any of the nested goals refer to the `term`.
274                        // This is not the case here and we only prefer adding an ambiguous
275                        // nested goal for consistency.
276                        ty::TypingMode::Coherence => {
277                            ecx.add_goal(GoalSource::Misc, goal.with(cx, PredicateKind::Ambiguous));
278                            return ecx
279                                .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
280                        }
281                        // Outside of coherence, we treat the associated item as rigid instead.
282                        ty::TypingMode::Analysis { .. }
283                        | ty::TypingMode::Borrowck { .. }
284                        | ty::TypingMode::PostBorrowckAnalysis { .. }
285                        | ty::TypingMode::PostAnalysis => {
286                            ecx.structurally_instantiate_normalizes_to_term(
287                                goal,
288                                goal.predicate.alias,
289                            );
290                            return ecx
291                                .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
292                        }
293                    };
294                }
295                Err(guar) => return error_response(ecx, guar),
296            };
297
298            if !cx.has_item_definition(target_item_def_id) {
299                // If the impl is missing an item, it's either because the user forgot to
300                // provide it, or the user is not *obligated* to provide it (because it
301                // has a trivially false `Sized` predicate). If it's the latter, we cannot
302                // delay a bug because we can have trivially false where clauses, so we
303                // treat it as rigid.
304                if cx.impl_self_is_guaranteed_unsized(impl_def_id) {
305                    match ecx.typing_mode() {
306                        // Trying to normalize such associated items is always ambiguous
307                        // during coherence to avoid cyclic reasoning. See the example in
308                        // tests/ui/traits/trivial-unsized-projection-in-coherence.rs.
309                        //
310                        // As this ambiguity is unavoidable we emit a nested ambiguous
311                        // goal instead of using `Certainty::AMBIGUOUS`. This allows us to
312                        // return the nested goals to the parent `AliasRelate` goal. This
313                        // would be relevant if any of the nested goals refer to the `term`.
314                        // This is not the case here and we only prefer adding an ambiguous
315                        // nested goal for consistency.
316                        ty::TypingMode::Coherence => {
317                            ecx.add_goal(GoalSource::Misc, goal.with(cx, PredicateKind::Ambiguous));
318                            return ecx
319                                .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
320                        }
321                        ty::TypingMode::Analysis { .. }
322                        | ty::TypingMode::Borrowck { .. }
323                        | ty::TypingMode::PostBorrowckAnalysis { .. }
324                        | ty::TypingMode::PostAnalysis => {
325                            ecx.structurally_instantiate_normalizes_to_term(
326                                goal,
327                                goal.predicate.alias,
328                            );
329                            return ecx
330                                .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
331                        }
332                    }
333                } else {
334                    return error_response(ecx, cx.delay_bug("missing item"));
335                }
336            }
337
338            let target_container_def_id = cx.parent(target_item_def_id);
339
340            // Getting the right args here is complex, e.g. given:
341            // - a goal `<Vec<u32> as Trait<i32>>::Assoc<u64>`
342            // - the applicable impl `impl<T> Trait<i32> for Vec<T>`
343            // - and the impl which defines `Assoc` being `impl<T, U> Trait<U> for Vec<T>`
344            //
345            // We first rebase the goal args onto the impl, going from `[Vec<u32>, i32, u64]`
346            // to `[u32, u64]`.
347            //
348            // And then map these args to the args of the defining impl of `Assoc`, going
349            // from `[u32, u64]` to `[u32, i32, u64]`.
350            let target_args = ecx.translate_args(
351                goal,
352                impl_def_id,
353                impl_args,
354                impl_trait_ref,
355                target_container_def_id,
356            )?;
357
358            if !cx.check_args_compatible(target_item_def_id, target_args) {
359                return error_response(
360                    ecx,
361                    cx.delay_bug("associated item has mismatched arguments"),
362                );
363            }
364
365            // Finally we construct the actual value of the associated type.
366            let term = match goal.predicate.alias.kind(cx) {
367                ty::AliasTermKind::ProjectionTy => {
368                    cx.type_of(target_item_def_id).map_bound(|ty| ty.into())
369                }
370                ty::AliasTermKind::ProjectionConst => {
371                    // FIXME(mgca): once const items are actual aliases defined as equal to type system consts
372                    // this should instead return that.
373                    if cx.features().associated_const_equality() {
374                        panic!("associated const projection is not supported yet")
375                    } else {
376                        ty::EarlyBinder::bind(
377                            Const::new_error_with_message(
378                                cx,
379                                "associated const projection is not supported yet",
380                            )
381                            .into(),
382                        )
383                    }
384                }
385                kind => panic!("expected projection, found {kind:?}"),
386            };
387
388            ecx.instantiate_normalizes_to_term(goal, term.instantiate(cx, target_args));
389            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
390        })
391    }
392
393    /// Fail to normalize if the predicate contains an error, alternatively, we could normalize to `ty::Error`
394    /// and succeed. Can experiment with this to figure out what results in better error messages.
395    fn consider_error_guaranteed_candidate(
396        _ecx: &mut EvalCtxt<'_, D>,
397        _guar: I::ErrorGuaranteed,
398    ) -> Result<Candidate<I>, NoSolution> {
399        Err(NoSolution)
400    }
401
402    fn consider_auto_trait_candidate(
403        ecx: &mut EvalCtxt<'_, D>,
404        _goal: Goal<I, Self>,
405    ) -> Result<Candidate<I>, NoSolution> {
406        ecx.cx().delay_bug("associated types not allowed on auto traits");
407        Err(NoSolution)
408    }
409
410    fn consider_trait_alias_candidate(
411        _ecx: &mut EvalCtxt<'_, D>,
412        goal: Goal<I, Self>,
413    ) -> Result<Candidate<I>, NoSolution> {
414        panic!("trait aliases do not have associated types: {:?}", goal);
415    }
416
417    fn consider_builtin_sizedness_candidates(
418        _ecx: &mut EvalCtxt<'_, D>,
419        goal: Goal<I, Self>,
420        _sizedness: SizedTraitKind,
421    ) -> Result<Candidate<I>, NoSolution> {
422        panic!("`Sized`/`MetaSized` does not have an associated type: {:?}", goal);
423    }
424
425    fn consider_builtin_copy_clone_candidate(
426        _ecx: &mut EvalCtxt<'_, D>,
427        goal: Goal<I, Self>,
428    ) -> Result<Candidate<I>, NoSolution> {
429        panic!("`Copy`/`Clone` does not have an associated type: {:?}", goal);
430    }
431
432    fn consider_builtin_fn_ptr_trait_candidate(
433        _ecx: &mut EvalCtxt<'_, D>,
434        goal: Goal<I, Self>,
435    ) -> Result<Candidate<I>, NoSolution> {
436        panic!("`FnPtr` does not have an associated type: {:?}", goal);
437    }
438
439    fn consider_builtin_fn_trait_candidates(
440        ecx: &mut EvalCtxt<'_, D>,
441        goal: Goal<I, Self>,
442        goal_kind: ty::ClosureKind,
443    ) -> Result<Candidate<I>, NoSolution> {
444        let cx = ecx.cx();
445        let tupled_inputs_and_output =
446            match structural_traits::extract_tupled_inputs_and_output_from_callable(
447                cx,
448                goal.predicate.self_ty(),
449                goal_kind,
450            )? {
451                Some(tupled_inputs_and_output) => tupled_inputs_and_output,
452                None => {
453                    return ecx.forced_ambiguity(MaybeCause::Ambiguity);
454                }
455            };
456
457        // A built-in `Fn` impl only holds if the output is sized.
458        // (FIXME: technically we only need to check this if the type is a fn ptr...)
459        let output_is_sized_pred = tupled_inputs_and_output.map_bound(|(_, output)| {
460            ty::TraitRef::new(cx, cx.require_lang_item(TraitSolverLangItem::Sized), [output])
461        });
462
463        let pred = tupled_inputs_and_output
464            .map_bound(|(inputs, output)| ty::ProjectionPredicate {
465                projection_term: ty::AliasTerm::new(
466                    cx,
467                    goal.predicate.def_id(),
468                    [goal.predicate.self_ty(), inputs],
469                ),
470                term: output.into(),
471            })
472            .upcast(cx);
473
474        Self::probe_and_consider_implied_clause(
475            ecx,
476            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
477            goal,
478            pred,
479            [(GoalSource::ImplWhereBound, goal.with(cx, output_is_sized_pred))],
480        )
481    }
482
483    fn consider_builtin_async_fn_trait_candidates(
484        ecx: &mut EvalCtxt<'_, D>,
485        goal: Goal<I, Self>,
486        goal_kind: ty::ClosureKind,
487    ) -> Result<Candidate<I>, NoSolution> {
488        let cx = ecx.cx();
489
490        let env_region = match goal_kind {
491            ty::ClosureKind::Fn | ty::ClosureKind::FnMut => goal.predicate.alias.args.region_at(2),
492            // Doesn't matter what this region is
493            ty::ClosureKind::FnOnce => Region::new_static(cx),
494        };
495        let (tupled_inputs_and_output_and_coroutine, nested_preds) =
496            structural_traits::extract_tupled_inputs_and_output_from_async_callable(
497                cx,
498                goal.predicate.self_ty(),
499                goal_kind,
500                env_region,
501            )?;
502
503        // A built-in `AsyncFn` impl only holds if the output is sized.
504        // (FIXME: technically we only need to check this if the type is a fn ptr...)
505        let output_is_sized_pred = tupled_inputs_and_output_and_coroutine.map_bound(
506            |AsyncCallableRelevantTypes { output_coroutine_ty: output_ty, .. }| {
507                ty::TraitRef::new(cx, cx.require_lang_item(TraitSolverLangItem::Sized), [output_ty])
508            },
509        );
510
511        let pred = tupled_inputs_and_output_and_coroutine
512            .map_bound(
513                |AsyncCallableRelevantTypes {
514                     tupled_inputs_ty,
515                     output_coroutine_ty,
516                     coroutine_return_ty,
517                 }| {
518                    let (projection_term, term) = if cx
519                        .is_lang_item(goal.predicate.def_id(), TraitSolverLangItem::CallOnceFuture)
520                    {
521                        (
522                            ty::AliasTerm::new(
523                                cx,
524                                goal.predicate.def_id(),
525                                [goal.predicate.self_ty(), tupled_inputs_ty],
526                            ),
527                            output_coroutine_ty.into(),
528                        )
529                    } else if cx
530                        .is_lang_item(goal.predicate.def_id(), TraitSolverLangItem::CallRefFuture)
531                    {
532                        (
533                            ty::AliasTerm::new(
534                                cx,
535                                goal.predicate.def_id(),
536                                [
537                                    I::GenericArg::from(goal.predicate.self_ty()),
538                                    tupled_inputs_ty.into(),
539                                    env_region.into(),
540                                ],
541                            ),
542                            output_coroutine_ty.into(),
543                        )
544                    } else if cx.is_lang_item(
545                        goal.predicate.def_id(),
546                        TraitSolverLangItem::AsyncFnOnceOutput,
547                    ) {
548                        (
549                            ty::AliasTerm::new(
550                                cx,
551                                goal.predicate.def_id(),
552                                [
553                                    I::GenericArg::from(goal.predicate.self_ty()),
554                                    tupled_inputs_ty.into(),
555                                ],
556                            ),
557                            coroutine_return_ty.into(),
558                        )
559                    } else {
560                        panic!(
561                            "no such associated type in `AsyncFn*`: {:?}",
562                            goal.predicate.def_id()
563                        )
564                    };
565                    ty::ProjectionPredicate { projection_term, term }
566                },
567            )
568            .upcast(cx);
569
570        Self::probe_and_consider_implied_clause(
571            ecx,
572            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
573            goal,
574            pred,
575            [goal.with(cx, output_is_sized_pred)]
576                .into_iter()
577                .chain(nested_preds.into_iter().map(|pred| goal.with(cx, pred)))
578                .map(|goal| (GoalSource::ImplWhereBound, goal)),
579        )
580    }
581
582    fn consider_builtin_async_fn_kind_helper_candidate(
583        ecx: &mut EvalCtxt<'_, D>,
584        goal: Goal<I, Self>,
585    ) -> Result<Candidate<I>, NoSolution> {
586        let [
587            closure_fn_kind_ty,
588            goal_kind_ty,
589            borrow_region,
590            tupled_inputs_ty,
591            tupled_upvars_ty,
592            coroutine_captures_by_ref_ty,
593        ] = *goal.predicate.alias.args.as_slice()
594        else {
595            panic!();
596        };
597
598        // Bail if the upvars haven't been constrained.
599        if tupled_upvars_ty.expect_ty().is_ty_var() {
600            return ecx.forced_ambiguity(MaybeCause::Ambiguity);
601        }
602
603        let Some(closure_kind) = closure_fn_kind_ty.expect_ty().to_opt_closure_kind() else {
604            // We don't need to worry about the self type being an infer var.
605            return Err(NoSolution);
606        };
607        let Some(goal_kind) = goal_kind_ty.expect_ty().to_opt_closure_kind() else {
608            return Err(NoSolution);
609        };
610        if !closure_kind.extends(goal_kind) {
611            return Err(NoSolution);
612        }
613
614        let upvars_ty = ty::CoroutineClosureSignature::tupled_upvars_by_closure_kind(
615            ecx.cx(),
616            goal_kind,
617            tupled_inputs_ty.expect_ty(),
618            tupled_upvars_ty.expect_ty(),
619            coroutine_captures_by_ref_ty.expect_ty(),
620            borrow_region.expect_region(),
621        );
622
623        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
624            ecx.instantiate_normalizes_to_term(goal, upvars_ty.into());
625            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
626        })
627    }
628
629    fn consider_builtin_tuple_candidate(
630        _ecx: &mut EvalCtxt<'_, D>,
631        goal: Goal<I, Self>,
632    ) -> Result<Candidate<I>, NoSolution> {
633        panic!("`Tuple` does not have an associated type: {:?}", goal);
634    }
635
636    fn consider_builtin_pointee_candidate(
637        ecx: &mut EvalCtxt<'_, D>,
638        goal: Goal<I, Self>,
639    ) -> Result<Candidate<I>, NoSolution> {
640        let cx = ecx.cx();
641        let metadata_def_id = cx.require_lang_item(TraitSolverLangItem::Metadata);
642        assert_eq!(metadata_def_id, goal.predicate.def_id());
643        let metadata_ty = match goal.predicate.self_ty().kind() {
644            ty::Bool
645            | ty::Char
646            | ty::Int(..)
647            | ty::Uint(..)
648            | ty::Float(..)
649            | ty::Array(..)
650            | ty::Pat(..)
651            | ty::RawPtr(..)
652            | ty::Ref(..)
653            | ty::FnDef(..)
654            | ty::FnPtr(..)
655            | ty::Closure(..)
656            | ty::CoroutineClosure(..)
657            | ty::Infer(ty::IntVar(..) | ty::FloatVar(..))
658            | ty::Coroutine(..)
659            | ty::CoroutineWitness(..)
660            | ty::Never
661            | ty::Foreign(..)
662            | ty::Dynamic(_, _, ty::DynStar) => Ty::new_unit(cx),
663
664            ty::Error(e) => Ty::new_error(cx, e),
665
666            ty::Str | ty::Slice(_) => Ty::new_usize(cx),
667
668            ty::Dynamic(_, _, ty::Dyn) => {
669                let dyn_metadata = cx.require_lang_item(TraitSolverLangItem::DynMetadata);
670                cx.type_of(dyn_metadata)
671                    .instantiate(cx, &[I::GenericArg::from(goal.predicate.self_ty())])
672            }
673
674            ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => {
675                // This is the "fallback impl" for type parameters, unnormalizable projections
676                // and opaque types: If the `self_ty` is `Sized`, then the metadata is `()`.
677                // FIXME(ptr_metadata): This impl overlaps with the other impls and shouldn't
678                // exist. Instead, `Pointee<Metadata = ()>` should be a supertrait of `Sized`.
679                let alias_bound_result =
680                    ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
681                        let sized_predicate = ty::TraitRef::new(
682                            cx,
683                            cx.require_lang_item(TraitSolverLangItem::Sized),
684                            [I::GenericArg::from(goal.predicate.self_ty())],
685                        );
686                        ecx.add_goal(GoalSource::Misc, goal.with(cx, sized_predicate));
687                        ecx.instantiate_normalizes_to_term(goal, Ty::new_unit(cx).into());
688                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
689                    });
690                // In case the dummy alias-bound candidate does not apply, we instead treat this projection
691                // as rigid.
692                return alias_bound_result.or_else(|NoSolution| {
693                    ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|this| {
694                        this.structurally_instantiate_normalizes_to_term(
695                            goal,
696                            goal.predicate.alias,
697                        );
698                        this.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
699                    })
700                });
701            }
702
703            ty::Adt(def, args) if def.is_struct() => match def.struct_tail_ty(cx) {
704                None => Ty::new_unit(cx),
705                Some(tail_ty) => {
706                    Ty::new_projection(cx, metadata_def_id, [tail_ty.instantiate(cx, args)])
707                }
708            },
709            ty::Adt(_, _) => Ty::new_unit(cx),
710
711            ty::Tuple(elements) => match elements.last() {
712                None => Ty::new_unit(cx),
713                Some(tail_ty) => Ty::new_projection(cx, metadata_def_id, [tail_ty]),
714            },
715
716            ty::UnsafeBinder(_) => {
717                // FIXME(unsafe_binder): Figure out how to handle pointee for unsafe binders.
718                todo!()
719            }
720
721            ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
722            | ty::Bound(..) => panic!(
723                "unexpected self ty `{:?}` when normalizing `<T as Pointee>::Metadata`",
724                goal.predicate.self_ty()
725            ),
726        };
727
728        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
729            ecx.instantiate_normalizes_to_term(goal, metadata_ty.into());
730            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
731        })
732    }
733
734    fn consider_builtin_future_candidate(
735        ecx: &mut EvalCtxt<'_, D>,
736        goal: Goal<I, Self>,
737    ) -> Result<Candidate<I>, NoSolution> {
738        let self_ty = goal.predicate.self_ty();
739        let ty::Coroutine(def_id, args) = self_ty.kind() else {
740            return Err(NoSolution);
741        };
742
743        // Coroutines are not futures unless they come from `async` desugaring
744        let cx = ecx.cx();
745        if !cx.coroutine_is_async(def_id) {
746            return Err(NoSolution);
747        }
748
749        let term = args.as_coroutine().return_ty().into();
750
751        Self::probe_and_consider_implied_clause(
752            ecx,
753            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
754            goal,
755            ty::ProjectionPredicate {
756                projection_term: ty::AliasTerm::new(ecx.cx(), goal.predicate.def_id(), [self_ty]),
757                term,
758            }
759            .upcast(cx),
760            // Technically, we need to check that the future type is Sized,
761            // but that's already proven by the coroutine being WF.
762            [],
763        )
764    }
765
766    fn consider_builtin_iterator_candidate(
767        ecx: &mut EvalCtxt<'_, D>,
768        goal: Goal<I, Self>,
769    ) -> Result<Candidate<I>, NoSolution> {
770        let self_ty = goal.predicate.self_ty();
771        let ty::Coroutine(def_id, args) = self_ty.kind() else {
772            return Err(NoSolution);
773        };
774
775        // Coroutines are not Iterators unless they come from `gen` desugaring
776        let cx = ecx.cx();
777        if !cx.coroutine_is_gen(def_id) {
778            return Err(NoSolution);
779        }
780
781        let term = args.as_coroutine().yield_ty().into();
782
783        Self::probe_and_consider_implied_clause(
784            ecx,
785            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
786            goal,
787            ty::ProjectionPredicate {
788                projection_term: ty::AliasTerm::new(ecx.cx(), goal.predicate.def_id(), [self_ty]),
789                term,
790            }
791            .upcast(cx),
792            // Technically, we need to check that the iterator type is Sized,
793            // but that's already proven by the generator being WF.
794            [],
795        )
796    }
797
798    fn consider_builtin_fused_iterator_candidate(
799        _ecx: &mut EvalCtxt<'_, D>,
800        goal: Goal<I, Self>,
801    ) -> Result<Candidate<I>, NoSolution> {
802        panic!("`FusedIterator` does not have an associated type: {:?}", goal);
803    }
804
805    fn consider_builtin_async_iterator_candidate(
806        ecx: &mut EvalCtxt<'_, D>,
807        goal: Goal<I, Self>,
808    ) -> Result<Candidate<I>, NoSolution> {
809        let self_ty = goal.predicate.self_ty();
810        let ty::Coroutine(def_id, args) = self_ty.kind() else {
811            return Err(NoSolution);
812        };
813
814        // Coroutines are not AsyncIterators unless they come from `gen` desugaring
815        let cx = ecx.cx();
816        if !cx.coroutine_is_async_gen(def_id) {
817            return Err(NoSolution);
818        }
819
820        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
821            let expected_ty = ecx.next_ty_infer();
822            // Take `AsyncIterator<Item = I>` and turn it into the corresponding
823            // coroutine yield ty `Poll<Option<I>>`.
824            let wrapped_expected_ty = Ty::new_adt(
825                cx,
826                cx.adt_def(cx.require_lang_item(TraitSolverLangItem::Poll)),
827                cx.mk_args(&[Ty::new_adt(
828                    cx,
829                    cx.adt_def(cx.require_lang_item(TraitSolverLangItem::Option)),
830                    cx.mk_args(&[expected_ty.into()]),
831                )
832                .into()]),
833            );
834            let yield_ty = args.as_coroutine().yield_ty();
835            ecx.eq(goal.param_env, wrapped_expected_ty, yield_ty)?;
836            ecx.instantiate_normalizes_to_term(goal, expected_ty.into());
837            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
838        })
839    }
840
841    fn consider_builtin_coroutine_candidate(
842        ecx: &mut EvalCtxt<'_, D>,
843        goal: Goal<I, Self>,
844    ) -> Result<Candidate<I>, NoSolution> {
845        let self_ty = goal.predicate.self_ty();
846        let ty::Coroutine(def_id, args) = self_ty.kind() else {
847            return Err(NoSolution);
848        };
849
850        // `async`-desugared coroutines do not implement the coroutine trait
851        let cx = ecx.cx();
852        if !cx.is_general_coroutine(def_id) {
853            return Err(NoSolution);
854        }
855
856        let coroutine = args.as_coroutine();
857
858        let term = if cx.is_lang_item(goal.predicate.def_id(), TraitSolverLangItem::CoroutineReturn)
859        {
860            coroutine.return_ty().into()
861        } else if cx.is_lang_item(goal.predicate.def_id(), TraitSolverLangItem::CoroutineYield) {
862            coroutine.yield_ty().into()
863        } else {
864            panic!("unexpected associated item `{:?}` for `{self_ty:?}`", goal.predicate.def_id())
865        };
866
867        Self::probe_and_consider_implied_clause(
868            ecx,
869            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
870            goal,
871            ty::ProjectionPredicate {
872                projection_term: ty::AliasTerm::new(
873                    ecx.cx(),
874                    goal.predicate.def_id(),
875                    [self_ty, coroutine.resume_ty()],
876                ),
877                term,
878            }
879            .upcast(cx),
880            // Technically, we need to check that the coroutine type is Sized,
881            // but that's already proven by the coroutine being WF.
882            [],
883        )
884    }
885
886    fn consider_structural_builtin_unsize_candidates(
887        _ecx: &mut EvalCtxt<'_, D>,
888        goal: Goal<I, Self>,
889    ) -> Vec<Candidate<I>> {
890        panic!("`Unsize` does not have an associated type: {:?}", goal);
891    }
892
893    fn consider_builtin_discriminant_kind_candidate(
894        ecx: &mut EvalCtxt<'_, D>,
895        goal: Goal<I, Self>,
896    ) -> Result<Candidate<I>, NoSolution> {
897        let self_ty = goal.predicate.self_ty();
898        let discriminant_ty = match self_ty.kind() {
899            ty::Bool
900            | ty::Char
901            | ty::Int(..)
902            | ty::Uint(..)
903            | ty::Float(..)
904            | ty::Array(..)
905            | ty::Pat(..)
906            | ty::RawPtr(..)
907            | ty::Ref(..)
908            | ty::FnDef(..)
909            | ty::FnPtr(..)
910            | ty::Closure(..)
911            | ty::CoroutineClosure(..)
912            | ty::Infer(ty::IntVar(..) | ty::FloatVar(..))
913            | ty::Coroutine(..)
914            | ty::CoroutineWitness(..)
915            | ty::Never
916            | ty::Foreign(..)
917            | ty::Adt(_, _)
918            | ty::Str
919            | ty::Slice(_)
920            | ty::Dynamic(_, _, _)
921            | ty::Tuple(_)
922            | ty::Error(_) => self_ty.discriminant_ty(ecx.cx()),
923
924            ty::UnsafeBinder(_) => {
925                // FIXME(unsafe_binders): instantiate this with placeholders?? i guess??
926                todo!("discr subgoal...")
927            }
928
929            // Given an alias, parameter, or placeholder we add an impl candidate normalizing to a rigid
930            // alias. In case there's a where-bound further constraining this alias it is preferred over
931            // this impl candidate anyways. It's still a bit scuffed.
932            ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => {
933                return ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
934                    ecx.structurally_instantiate_normalizes_to_term(goal, goal.predicate.alias);
935                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
936                });
937            }
938
939            ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
940            | ty::Bound(..) => panic!(
941                "unexpected self ty `{:?}` when normalizing `<T as DiscriminantKind>::Discriminant`",
942                goal.predicate.self_ty()
943            ),
944        };
945
946        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
947            ecx.instantiate_normalizes_to_term(goal, discriminant_ty.into());
948            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
949        })
950    }
951
952    fn consider_builtin_destruct_candidate(
953        _ecx: &mut EvalCtxt<'_, D>,
954        goal: Goal<I, Self>,
955    ) -> Result<Candidate<I>, NoSolution> {
956        panic!("`Destruct` does not have an associated type: {:?}", goal);
957    }
958
959    fn consider_builtin_transmute_candidate(
960        _ecx: &mut EvalCtxt<'_, D>,
961        goal: Goal<I, Self>,
962    ) -> Result<Candidate<I>, NoSolution> {
963        panic!("`TransmuteFrom` does not have an associated type: {:?}", goal)
964    }
965
966    fn consider_builtin_bikeshed_guaranteed_no_drop_candidate(
967        _ecx: &mut EvalCtxt<'_, D>,
968        goal: Goal<I, Self>,
969    ) -> Result<Candidate<I>, NoSolution> {
970        unreachable!("`BikeshedGuaranteedNoDrop` does not have an associated type: {:?}", goal)
971    }
972}
973
974impl<D, I> EvalCtxt<'_, D>
975where
976    D: SolverDelegate<Interner = I>,
977    I: Interner,
978{
979    fn translate_args(
980        &mut self,
981        goal: Goal<I, ty::NormalizesTo<I>>,
982        impl_def_id: I::DefId,
983        impl_args: I::GenericArgs,
984        impl_trait_ref: rustc_type_ir::TraitRef<I>,
985        target_container_def_id: I::DefId,
986    ) -> Result<I::GenericArgs, NoSolution> {
987        let cx = self.cx();
988        Ok(if target_container_def_id == impl_trait_ref.def_id {
989            // Default value from the trait definition. No need to rebase.
990            goal.predicate.alias.args
991        } else if target_container_def_id == impl_def_id {
992            // Same impl, no need to fully translate, just a rebase from
993            // the trait is sufficient.
994            goal.predicate.alias.args.rebase_onto(cx, impl_trait_ref.def_id, impl_args)
995        } else {
996            let target_args = self.fresh_args_for_item(target_container_def_id);
997            let target_trait_ref =
998                cx.impl_trait_ref(target_container_def_id).instantiate(cx, target_args);
999            // Relate source impl to target impl by equating trait refs.
1000            self.eq(goal.param_env, impl_trait_ref, target_trait_ref)?;
1001            // Also add predicates since they may be needed to constrain the
1002            // target impl's params.
1003            self.add_goals(
1004                GoalSource::Misc,
1005                cx.predicates_of(target_container_def_id)
1006                    .iter_instantiated(cx, target_args)
1007                    .map(|pred| goal.with(cx, pred)),
1008            );
1009            goal.predicate.alias.args.rebase_onto(cx, impl_trait_ref.def_id, target_args)
1010        })
1011    }
1012}