rustc_hir_analysis/check/
compare_impl_item.rs

1use core::ops::ControlFlow;
2use std::borrow::Cow;
3use std::iter;
4
5use hir::def_id::{DefId, DefIdMap, LocalDefId};
6use rustc_data_structures::fx::{FxIndexMap, FxIndexSet};
7use rustc_errors::codes::*;
8use rustc_errors::{Applicability, ErrorGuaranteed, MultiSpan, pluralize, struct_span_code_err};
9use rustc_hir::def::{DefKind, Res};
10use rustc_hir::intravisit::VisitorExt;
11use rustc_hir::{self as hir, AmbigArg, GenericParamKind, ImplItemKind, intravisit};
12use rustc_infer::infer::{self, BoundRegionConversionTime, InferCtxt, TyCtxtInferExt};
13use rustc_infer::traits::util;
14use rustc_middle::ty::error::{ExpectedFound, TypeError};
15use rustc_middle::ty::{
16    self, BottomUpFolder, GenericArgs, GenericParamDefKind, Ty, TyCtxt, TypeFoldable, TypeFolder,
17    TypeSuperFoldable, TypeVisitable, TypeVisitableExt, TypeVisitor, TypingMode, Upcast,
18};
19use rustc_middle::{bug, span_bug};
20use rustc_span::{DUMMY_SP, Span};
21use rustc_trait_selection::error_reporting::InferCtxtErrorExt;
22use rustc_trait_selection::infer::InferCtxtExt;
23use rustc_trait_selection::regions::InferCtxtRegionExt;
24use rustc_trait_selection::traits::{
25    self, FulfillmentError, ObligationCause, ObligationCauseCode, ObligationCtxt,
26};
27use tracing::{debug, instrument};
28
29use super::potentially_plural_count;
30use crate::errors::{LifetimesOrBoundsMismatchOnTrait, MethodShouldReturnFuture};
31
32pub(super) mod refine;
33
34/// Call the query `tcx.compare_impl_item()` directly instead.
35pub(super) fn compare_impl_item(
36    tcx: TyCtxt<'_>,
37    impl_item_def_id: LocalDefId,
38) -> Result<(), ErrorGuaranteed> {
39    let impl_item = tcx.associated_item(impl_item_def_id);
40    let trait_item = tcx.associated_item(impl_item.trait_item_def_id.unwrap());
41    let impl_trait_ref =
42        tcx.impl_trait_ref(impl_item.container_id(tcx)).unwrap().instantiate_identity();
43    debug!(?impl_trait_ref);
44
45    match impl_item.kind {
46        ty::AssocKind::Fn { .. } => compare_impl_method(tcx, impl_item, trait_item, impl_trait_ref),
47        ty::AssocKind::Type { .. } => compare_impl_ty(tcx, impl_item, trait_item, impl_trait_ref),
48        ty::AssocKind::Const { .. } => {
49            compare_impl_const(tcx, impl_item, trait_item, impl_trait_ref)
50        }
51    }
52}
53
54/// Checks that a method from an impl conforms to the signature of
55/// the same method as declared in the trait.
56///
57/// # Parameters
58///
59/// - `impl_m`: type of the method we are checking
60/// - `trait_m`: the method in the trait
61/// - `impl_trait_ref`: the TraitRef corresponding to the trait implementation
62#[instrument(level = "debug", skip(tcx))]
63fn compare_impl_method<'tcx>(
64    tcx: TyCtxt<'tcx>,
65    impl_m: ty::AssocItem,
66    trait_m: ty::AssocItem,
67    impl_trait_ref: ty::TraitRef<'tcx>,
68) -> Result<(), ErrorGuaranteed> {
69    check_method_is_structurally_compatible(tcx, impl_m, trait_m, impl_trait_ref, false)?;
70    compare_method_predicate_entailment(tcx, impl_m, trait_m, impl_trait_ref)?;
71    Ok(())
72}
73
74/// Checks a bunch of different properties of the impl/trait methods for
75/// compatibility, such as asyncness, number of argument, self receiver kind,
76/// and number of early- and late-bound generics.
77fn check_method_is_structurally_compatible<'tcx>(
78    tcx: TyCtxt<'tcx>,
79    impl_m: ty::AssocItem,
80    trait_m: ty::AssocItem,
81    impl_trait_ref: ty::TraitRef<'tcx>,
82    delay: bool,
83) -> Result<(), ErrorGuaranteed> {
84    compare_self_type(tcx, impl_m, trait_m, impl_trait_ref, delay)?;
85    compare_number_of_generics(tcx, impl_m, trait_m, delay)?;
86    compare_generic_param_kinds(tcx, impl_m, trait_m, delay)?;
87    compare_number_of_method_arguments(tcx, impl_m, trait_m, delay)?;
88    compare_synthetic_generics(tcx, impl_m, trait_m, delay)?;
89    check_region_bounds_on_impl_item(tcx, impl_m, trait_m, delay)?;
90    Ok(())
91}
92
93/// This function is best explained by example. Consider a trait with its implementation:
94///
95/// ```rust
96/// trait Trait<'t, T> {
97///     // `trait_m`
98///     fn method<'a, M>(t: &'t T, m: &'a M) -> Self;
99/// }
100///
101/// struct Foo;
102///
103/// impl<'i, 'j, U> Trait<'j, &'i U> for Foo {
104///     // `impl_m`
105///     fn method<'b, N>(t: &'j &'i U, m: &'b N) -> Foo { Foo }
106/// }
107/// ```
108///
109/// We wish to decide if those two method types are compatible.
110/// For this we have to show that, assuming the bounds of the impl hold, the
111/// bounds of `trait_m` imply the bounds of `impl_m`.
112///
113/// We start out with `trait_to_impl_args`, that maps the trait
114/// type parameters to impl type parameters. This is taken from the
115/// impl trait reference:
116///
117/// ```rust,ignore (pseudo-Rust)
118/// trait_to_impl_args = {'t => 'j, T => &'i U, Self => Foo}
119/// ```
120///
121/// We create a mapping `dummy_args` that maps from the impl type
122/// parameters to fresh types and regions. For type parameters,
123/// this is the identity transform, but we could as well use any
124/// placeholder types. For regions, we convert from bound to free
125/// regions (Note: but only early-bound regions, i.e., those
126/// declared on the impl or used in type parameter bounds).
127///
128/// ```rust,ignore (pseudo-Rust)
129/// impl_to_placeholder_args = {'i => 'i0, U => U0, N => N0 }
130/// ```
131///
132/// Now we can apply `placeholder_args` to the type of the impl method
133/// to yield a new function type in terms of our fresh, placeholder
134/// types:
135///
136/// ```rust,ignore (pseudo-Rust)
137/// <'b> fn(t: &'i0 U0, m: &'b N0) -> Foo
138/// ```
139///
140/// We now want to extract and instantiate the type of the *trait*
141/// method and compare it. To do so, we must create a compound
142/// instantiation by combining `trait_to_impl_args` and
143/// `impl_to_placeholder_args`, and also adding a mapping for the method
144/// type parameters. We extend the mapping to also include
145/// the method parameters.
146///
147/// ```rust,ignore (pseudo-Rust)
148/// trait_to_placeholder_args = { T => &'i0 U0, Self => Foo, M => N0 }
149/// ```
150///
151/// Applying this to the trait method type yields:
152///
153/// ```rust,ignore (pseudo-Rust)
154/// <'a> fn(t: &'i0 U0, m: &'a N0) -> Foo
155/// ```
156///
157/// This type is also the same but the name of the bound region (`'a`
158/// vs `'b`). However, the normal subtyping rules on fn types handle
159/// this kind of equivalency just fine.
160///
161/// We now use these generic parameters to ensure that all declared bounds
162/// are satisfied by the implementation's method.
163///
164/// We do this by creating a parameter environment which contains a
165/// generic parameter corresponding to `impl_to_placeholder_args`. We then build
166/// `trait_to_placeholder_args` and use it to convert the predicates contained
167/// in the `trait_m` generics to the placeholder form.
168///
169/// Finally we register each of these predicates as an obligation and check that
170/// they hold.
171#[instrument(level = "debug", skip(tcx, impl_trait_ref))]
172fn compare_method_predicate_entailment<'tcx>(
173    tcx: TyCtxt<'tcx>,
174    impl_m: ty::AssocItem,
175    trait_m: ty::AssocItem,
176    impl_trait_ref: ty::TraitRef<'tcx>,
177) -> Result<(), ErrorGuaranteed> {
178    // This node-id should be used for the `body_id` field on each
179    // `ObligationCause` (and the `FnCtxt`).
180    //
181    // FIXME(@lcnr): remove that after removing `cause.body_id` from
182    // obligations.
183    let impl_m_def_id = impl_m.def_id.expect_local();
184    let impl_m_span = tcx.def_span(impl_m_def_id);
185    let cause = ObligationCause::new(
186        impl_m_span,
187        impl_m_def_id,
188        ObligationCauseCode::CompareImplItem {
189            impl_item_def_id: impl_m_def_id,
190            trait_item_def_id: trait_m.def_id,
191            kind: impl_m.kind,
192        },
193    );
194
195    // Create mapping from trait method to impl method.
196    let impl_def_id = impl_m.container_id(tcx);
197    let trait_to_impl_args = GenericArgs::identity_for_item(tcx, impl_m.def_id).rebase_onto(
198        tcx,
199        impl_m.container_id(tcx),
200        impl_trait_ref.args,
201    );
202    debug!(?trait_to_impl_args);
203
204    let impl_m_predicates = tcx.predicates_of(impl_m.def_id);
205    let trait_m_predicates = tcx.predicates_of(trait_m.def_id);
206
207    // This is the only tricky bit of the new way we check implementation methods
208    // We need to build a set of predicates where only the method-level bounds
209    // are from the trait and we assume all other bounds from the implementation
210    // to be previously satisfied.
211    //
212    // We then register the obligations from the impl_m and check to see
213    // if all constraints hold.
214    let impl_predicates = tcx.predicates_of(impl_m_predicates.parent.unwrap());
215    let mut hybrid_preds = impl_predicates.instantiate_identity(tcx).predicates;
216    hybrid_preds.extend(
217        trait_m_predicates.instantiate_own(tcx, trait_to_impl_args).map(|(predicate, _)| predicate),
218    );
219
220    let is_conditionally_const = tcx.is_conditionally_const(impl_def_id);
221    if is_conditionally_const {
222        // Augment the hybrid param-env with the const conditions
223        // of the impl header and the trait method.
224        hybrid_preds.extend(
225            tcx.const_conditions(impl_def_id)
226                .instantiate_identity(tcx)
227                .into_iter()
228                .chain(
229                    tcx.const_conditions(trait_m.def_id).instantiate_own(tcx, trait_to_impl_args),
230                )
231                .map(|(trait_ref, _)| {
232                    trait_ref.to_host_effect_clause(tcx, ty::BoundConstness::Maybe)
233                }),
234        );
235    }
236
237    let normalize_cause = traits::ObligationCause::misc(impl_m_span, impl_m_def_id);
238    let param_env = ty::ParamEnv::new(tcx.mk_clauses(&hybrid_preds));
239    let param_env = traits::normalize_param_env_or_error(tcx, param_env, normalize_cause);
240    debug!(caller_bounds=?param_env.caller_bounds());
241
242    let infcx = &tcx.infer_ctxt().build(TypingMode::non_body_analysis());
243    let ocx = ObligationCtxt::new_with_diagnostics(infcx);
244
245    // Create obligations for each predicate declared by the impl
246    // definition in the context of the hybrid param-env. This makes
247    // sure that the impl's method's where clauses are not more
248    // restrictive than the trait's method (and the impl itself).
249    let impl_m_own_bounds = impl_m_predicates.instantiate_own_identity();
250    for (predicate, span) in impl_m_own_bounds {
251        let normalize_cause = traits::ObligationCause::misc(span, impl_m_def_id);
252        let predicate = ocx.normalize(&normalize_cause, param_env, predicate);
253
254        let cause = ObligationCause::new(
255            span,
256            impl_m_def_id,
257            ObligationCauseCode::CompareImplItem {
258                impl_item_def_id: impl_m_def_id,
259                trait_item_def_id: trait_m.def_id,
260                kind: impl_m.kind,
261            },
262        );
263        ocx.register_obligation(traits::Obligation::new(tcx, cause, param_env, predicate));
264    }
265
266    // If we're within a const implementation, we need to make sure that the method
267    // does not assume stronger `[const]` bounds than the trait definition.
268    //
269    // This registers the `[const]` bounds of the impl method, which we will prove
270    // using the hybrid param-env that we earlier augmented with the const conditions
271    // from the impl header and trait method declaration.
272    if is_conditionally_const {
273        for (const_condition, span) in
274            tcx.const_conditions(impl_m.def_id).instantiate_own_identity()
275        {
276            let normalize_cause = traits::ObligationCause::misc(span, impl_m_def_id);
277            let const_condition = ocx.normalize(&normalize_cause, param_env, const_condition);
278
279            let cause = ObligationCause::new(
280                span,
281                impl_m_def_id,
282                ObligationCauseCode::CompareImplItem {
283                    impl_item_def_id: impl_m_def_id,
284                    trait_item_def_id: trait_m.def_id,
285                    kind: impl_m.kind,
286                },
287            );
288            ocx.register_obligation(traits::Obligation::new(
289                tcx,
290                cause,
291                param_env,
292                const_condition.to_host_effect_clause(tcx, ty::BoundConstness::Maybe),
293            ));
294        }
295    }
296
297    // We now need to check that the signature of the impl method is
298    // compatible with that of the trait method. We do this by
299    // checking that `impl_fty <: trait_fty`.
300    //
301    // FIXME. Unfortunately, this doesn't quite work right now because
302    // associated type normalization is not integrated into subtype
303    // checks. For the comparison to be valid, we need to
304    // normalize the associated types in the impl/trait methods
305    // first. However, because function types bind regions, just
306    // calling `FnCtxt::normalize` would have no effect on
307    // any associated types appearing in the fn arguments or return
308    // type.
309
310    let mut wf_tys = FxIndexSet::default();
311
312    let unnormalized_impl_sig = infcx.instantiate_binder_with_fresh_vars(
313        impl_m_span,
314        BoundRegionConversionTime::HigherRankedType,
315        tcx.fn_sig(impl_m.def_id).instantiate_identity(),
316    );
317
318    let norm_cause = ObligationCause::misc(impl_m_span, impl_m_def_id);
319    let impl_sig = ocx.normalize(&norm_cause, param_env, unnormalized_impl_sig);
320    debug!(?impl_sig);
321
322    let trait_sig = tcx.fn_sig(trait_m.def_id).instantiate(tcx, trait_to_impl_args);
323    let trait_sig = tcx.liberate_late_bound_regions(impl_m.def_id, trait_sig);
324
325    // Next, add all inputs and output as well-formed tys. Importantly,
326    // we have to do this before normalization, since the normalized ty may
327    // not contain the input parameters. See issue #87748.
328    wf_tys.extend(trait_sig.inputs_and_output.iter());
329    let trait_sig = ocx.normalize(&norm_cause, param_env, trait_sig);
330    // We also have to add the normalized trait signature
331    // as we don't normalize during implied bounds computation.
332    wf_tys.extend(trait_sig.inputs_and_output.iter());
333    debug!(?trait_sig);
334
335    // FIXME: We'd want to keep more accurate spans than "the method signature" when
336    // processing the comparison between the trait and impl fn, but we sadly lose them
337    // and point at the whole signature when a trait bound or specific input or output
338    // type would be more appropriate. In other places we have a `Vec<Span>`
339    // corresponding to their `Vec<Predicate>`, but we don't have that here.
340    // Fixing this would improve the output of test `issue-83765.rs`.
341    let result = ocx.sup(&cause, param_env, trait_sig, impl_sig);
342
343    if let Err(terr) = result {
344        debug!(?impl_sig, ?trait_sig, ?terr, "sub_types failed");
345
346        let emitted = report_trait_method_mismatch(
347            infcx,
348            cause,
349            param_env,
350            terr,
351            (trait_m, trait_sig),
352            (impl_m, impl_sig),
353            impl_trait_ref,
354        );
355        return Err(emitted);
356    }
357
358    if !(impl_sig, trait_sig).references_error() {
359        ocx.register_obligation(traits::Obligation::new(
360            infcx.tcx,
361            cause,
362            param_env,
363            ty::ClauseKind::WellFormed(
364                Ty::new_fn_ptr(tcx, ty::Binder::dummy(unnormalized_impl_sig)).into(),
365            ),
366        ));
367    }
368
369    // Check that all obligations are satisfied by the implementation's
370    // version.
371    let errors = ocx.select_all_or_error();
372    if !errors.is_empty() {
373        let reported = infcx.err_ctxt().report_fulfillment_errors(errors);
374        return Err(reported);
375    }
376
377    // Finally, resolve all regions. This catches wily misuses of
378    // lifetime parameters.
379    let errors = infcx.resolve_regions(impl_m_def_id, param_env, wf_tys);
380    if !errors.is_empty() {
381        return Err(infcx
382            .tainted_by_errors()
383            .unwrap_or_else(|| infcx.err_ctxt().report_region_errors(impl_m_def_id, &errors)));
384    }
385
386    Ok(())
387}
388
389struct RemapLateParam<'tcx> {
390    tcx: TyCtxt<'tcx>,
391    mapping: FxIndexMap<ty::LateParamRegionKind, ty::LateParamRegionKind>,
392}
393
394impl<'tcx> TypeFolder<TyCtxt<'tcx>> for RemapLateParam<'tcx> {
395    fn cx(&self) -> TyCtxt<'tcx> {
396        self.tcx
397    }
398
399    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
400        if let ty::ReLateParam(fr) = r.kind() {
401            ty::Region::new_late_param(
402                self.tcx,
403                fr.scope,
404                self.mapping.get(&fr.kind).copied().unwrap_or(fr.kind),
405            )
406        } else {
407            r
408        }
409    }
410}
411
412/// Given a method def-id in an impl, compare the method signature of the impl
413/// against the trait that it's implementing. In doing so, infer the hidden types
414/// that this method's signature provides to satisfy each return-position `impl Trait`
415/// in the trait signature.
416///
417/// The method is also responsible for making sure that the hidden types for each
418/// RPITIT actually satisfy the bounds of the `impl Trait`, i.e. that if we infer
419/// `impl Trait = Foo`, that `Foo: Trait` holds.
420///
421/// For example, given the sample code:
422///
423/// ```
424/// use std::ops::Deref;
425///
426/// trait Foo {
427///     fn bar() -> impl Deref<Target = impl Sized>;
428///              // ^- RPITIT #1        ^- RPITIT #2
429/// }
430///
431/// impl Foo for () {
432///     fn bar() -> Box<String> { Box::new(String::new()) }
433/// }
434/// ```
435///
436/// The hidden types for the RPITITs in `bar` would be inferred to:
437///     * `impl Deref` (RPITIT #1) = `Box<String>`
438///     * `impl Sized` (RPITIT #2) = `String`
439///
440/// The relationship between these two types is straightforward in this case, but
441/// may be more tenuously connected via other `impl`s and normalization rules for
442/// cases of more complicated nested RPITITs.
443#[instrument(skip(tcx), level = "debug", ret)]
444pub(super) fn collect_return_position_impl_trait_in_trait_tys<'tcx>(
445    tcx: TyCtxt<'tcx>,
446    impl_m_def_id: LocalDefId,
447) -> Result<&'tcx DefIdMap<ty::EarlyBinder<'tcx, Ty<'tcx>>>, ErrorGuaranteed> {
448    let impl_m = tcx.opt_associated_item(impl_m_def_id.to_def_id()).unwrap();
449    let trait_m = tcx.opt_associated_item(impl_m.trait_item_def_id.unwrap()).unwrap();
450    let impl_trait_ref =
451        tcx.impl_trait_ref(impl_m.impl_container(tcx).unwrap()).unwrap().instantiate_identity();
452    // First, check a few of the same things as `compare_impl_method`,
453    // just so we don't ICE during instantiation later.
454    check_method_is_structurally_compatible(tcx, impl_m, trait_m, impl_trait_ref, true)?;
455
456    let impl_m_hir_id = tcx.local_def_id_to_hir_id(impl_m_def_id);
457    let return_span = tcx.hir_fn_decl_by_hir_id(impl_m_hir_id).unwrap().output.span();
458    let cause = ObligationCause::new(
459        return_span,
460        impl_m_def_id,
461        ObligationCauseCode::CompareImplItem {
462            impl_item_def_id: impl_m_def_id,
463            trait_item_def_id: trait_m.def_id,
464            kind: impl_m.kind,
465        },
466    );
467
468    // Create mapping from trait to impl (i.e. impl trait header + impl method identity args).
469    let trait_to_impl_args = GenericArgs::identity_for_item(tcx, impl_m.def_id).rebase_onto(
470        tcx,
471        impl_m.container_id(tcx),
472        impl_trait_ref.args,
473    );
474
475    let hybrid_preds = tcx
476        .predicates_of(impl_m.container_id(tcx))
477        .instantiate_identity(tcx)
478        .into_iter()
479        .chain(tcx.predicates_of(trait_m.def_id).instantiate_own(tcx, trait_to_impl_args))
480        .map(|(clause, _)| clause);
481    let param_env = ty::ParamEnv::new(tcx.mk_clauses_from_iter(hybrid_preds));
482    let param_env = traits::normalize_param_env_or_error(
483        tcx,
484        param_env,
485        ObligationCause::misc(tcx.def_span(impl_m_def_id), impl_m_def_id),
486    );
487
488    let infcx = &tcx.infer_ctxt().build(TypingMode::non_body_analysis());
489    let ocx = ObligationCtxt::new_with_diagnostics(infcx);
490
491    // Check that the where clauses of the impl are satisfied by the hybrid param env.
492    // You might ask -- what does this have to do with RPITIT inference? Nothing.
493    // We check these because if the where clauses of the signatures do not match
494    // up, then we don't want to give spurious other errors that point at the RPITITs.
495    // They're not necessary to check, though, because we already check them in
496    // `compare_method_predicate_entailment`.
497    let impl_m_own_bounds = tcx.predicates_of(impl_m_def_id).instantiate_own_identity();
498    for (predicate, span) in impl_m_own_bounds {
499        let normalize_cause = traits::ObligationCause::misc(span, impl_m_def_id);
500        let predicate = ocx.normalize(&normalize_cause, param_env, predicate);
501
502        let cause = ObligationCause::new(
503            span,
504            impl_m_def_id,
505            ObligationCauseCode::CompareImplItem {
506                impl_item_def_id: impl_m_def_id,
507                trait_item_def_id: trait_m.def_id,
508                kind: impl_m.kind,
509            },
510        );
511        ocx.register_obligation(traits::Obligation::new(tcx, cause, param_env, predicate));
512    }
513
514    // Normalize the impl signature with fresh variables for lifetime inference.
515    let misc_cause = ObligationCause::misc(return_span, impl_m_def_id);
516    let impl_sig = ocx.normalize(
517        &misc_cause,
518        param_env,
519        infcx.instantiate_binder_with_fresh_vars(
520            return_span,
521            BoundRegionConversionTime::HigherRankedType,
522            tcx.fn_sig(impl_m.def_id).instantiate_identity(),
523        ),
524    );
525    impl_sig.error_reported()?;
526    let impl_return_ty = impl_sig.output();
527
528    // Normalize the trait signature with liberated bound vars, passing it through
529    // the ImplTraitInTraitCollector, which gathers all of the RPITITs and replaces
530    // them with inference variables.
531    // We will use these inference variables to collect the hidden types of RPITITs.
532    let mut collector = ImplTraitInTraitCollector::new(&ocx, return_span, param_env, impl_m_def_id);
533    let unnormalized_trait_sig = tcx
534        .liberate_late_bound_regions(
535            impl_m.def_id,
536            tcx.fn_sig(trait_m.def_id).instantiate(tcx, trait_to_impl_args),
537        )
538        .fold_with(&mut collector);
539
540    let trait_sig = ocx.normalize(&misc_cause, param_env, unnormalized_trait_sig);
541    trait_sig.error_reported()?;
542    let trait_return_ty = trait_sig.output();
543
544    // RPITITs are allowed to use the implied predicates of the method that
545    // defines them. This is because we want code like:
546    // ```
547    // trait Foo {
548    //     fn test<'a, T>(_: &'a T) -> impl Sized;
549    // }
550    // impl Foo for () {
551    //     fn test<'a, T>(x: &'a T) -> &'a T { x }
552    // }
553    // ```
554    // .. to compile. However, since we use both the normalized and unnormalized
555    // inputs and outputs from the instantiated trait signature, we will end up
556    // seeing the hidden type of an RPIT in the signature itself. Naively, this
557    // means that we will use the hidden type to imply the hidden type's own
558    // well-formedness.
559    //
560    // To avoid this, we replace the infer vars used for hidden type inference
561    // with placeholders, which imply nothing about outlives bounds, and then
562    // prove below that the hidden types are well formed.
563    let universe = infcx.create_next_universe();
564    let mut idx = ty::BoundVar::ZERO;
565    let mapping: FxIndexMap<_, _> = collector
566        .types
567        .iter()
568        .map(|(_, &(ty, _))| {
569            assert!(
570                infcx.resolve_vars_if_possible(ty) == ty && ty.is_ty_var(),
571                "{ty:?} should not have been constrained via normalization",
572                ty = infcx.resolve_vars_if_possible(ty)
573            );
574            idx += 1;
575            (
576                ty,
577                Ty::new_placeholder(
578                    tcx,
579                    ty::Placeholder {
580                        universe,
581                        bound: ty::BoundTy { var: idx, kind: ty::BoundTyKind::Anon },
582                    },
583                ),
584            )
585        })
586        .collect();
587    let mut type_mapper = BottomUpFolder {
588        tcx,
589        ty_op: |ty| *mapping.get(&ty).unwrap_or(&ty),
590        lt_op: |lt| lt,
591        ct_op: |ct| ct,
592    };
593    let wf_tys = FxIndexSet::from_iter(
594        unnormalized_trait_sig
595            .inputs_and_output
596            .iter()
597            .chain(trait_sig.inputs_and_output.iter())
598            .map(|ty| ty.fold_with(&mut type_mapper)),
599    );
600
601    match ocx.eq(&cause, param_env, trait_return_ty, impl_return_ty) {
602        Ok(()) => {}
603        Err(terr) => {
604            let mut diag = struct_span_code_err!(
605                tcx.dcx(),
606                cause.span,
607                E0053,
608                "method `{}` has an incompatible return type for trait",
609                trait_m.name()
610            );
611            infcx.err_ctxt().note_type_err(
612                &mut diag,
613                &cause,
614                tcx.hir_get_if_local(impl_m.def_id)
615                    .and_then(|node| node.fn_decl())
616                    .map(|decl| (decl.output.span(), Cow::from("return type in trait"), false)),
617                Some(param_env.and(infer::ValuePairs::Terms(ExpectedFound {
618                    expected: trait_return_ty.into(),
619                    found: impl_return_ty.into(),
620                }))),
621                terr,
622                false,
623                None,
624            );
625            return Err(diag.emit());
626        }
627    }
628
629    debug!(?trait_sig, ?impl_sig, "equating function signatures");
630
631    // Unify the whole function signature. We need to do this to fully infer
632    // the lifetimes of the return type, but do this after unifying just the
633    // return types, since we want to avoid duplicating errors from
634    // `compare_method_predicate_entailment`.
635    match ocx.eq(&cause, param_env, trait_sig, impl_sig) {
636        Ok(()) => {}
637        Err(terr) => {
638            // This function gets called during `compare_method_predicate_entailment` when normalizing a
639            // signature that contains RPITIT. When the method signatures don't match, we have to
640            // emit an error now because `compare_method_predicate_entailment` will not report the error
641            // when normalization fails.
642            let emitted = report_trait_method_mismatch(
643                infcx,
644                cause,
645                param_env,
646                terr,
647                (trait_m, trait_sig),
648                (impl_m, impl_sig),
649                impl_trait_ref,
650            );
651            return Err(emitted);
652        }
653    }
654
655    if !unnormalized_trait_sig.output().references_error() && collector.types.is_empty() {
656        tcx.dcx().delayed_bug(
657            "expect >0 RPITITs in call to `collect_return_position_impl_trait_in_trait_tys`",
658        );
659    }
660
661    // FIXME: This has the same issue as #108544, but since this isn't breaking
662    // existing code, I'm not particularly inclined to do the same hack as above
663    // where we process wf obligations manually. This can be fixed in a forward-
664    // compatible way later.
665    let collected_types = collector.types;
666    for (_, &(ty, _)) in &collected_types {
667        ocx.register_obligation(traits::Obligation::new(
668            tcx,
669            misc_cause.clone(),
670            param_env,
671            ty::ClauseKind::WellFormed(ty.into()),
672        ));
673    }
674
675    // Check that all obligations are satisfied by the implementation's
676    // RPITs.
677    let errors = ocx.select_all_or_error();
678    if !errors.is_empty() {
679        if let Err(guar) = try_report_async_mismatch(tcx, infcx, &errors, trait_m, impl_m, impl_sig)
680        {
681            return Err(guar);
682        }
683
684        let guar = infcx.err_ctxt().report_fulfillment_errors(errors);
685        return Err(guar);
686    }
687
688    // Finally, resolve all regions. This catches wily misuses of
689    // lifetime parameters.
690    ocx.resolve_regions_and_report_errors(impl_m_def_id, param_env, wf_tys)?;
691
692    let mut remapped_types = DefIdMap::default();
693    for (def_id, (ty, args)) in collected_types {
694        match infcx.fully_resolve(ty) {
695            Ok(ty) => {
696                // `ty` contains free regions that we created earlier while liberating the
697                // trait fn signature. However, projection normalization expects `ty` to
698                // contains `def_id`'s early-bound regions.
699                let id_args = GenericArgs::identity_for_item(tcx, def_id);
700                debug!(?id_args, ?args);
701                let map: FxIndexMap<_, _> = std::iter::zip(args, id_args)
702                    .skip(tcx.generics_of(trait_m.def_id).count())
703                    .filter_map(|(a, b)| Some((a.as_region()?, b.as_region()?)))
704                    .collect();
705                debug!(?map);
706
707                // NOTE(compiler-errors): RPITITs, like all other RPITs, have early-bound
708                // region args that are synthesized during AST lowering. These are args
709                // that are appended to the parent args (trait and trait method). However,
710                // we're trying to infer the uninstantiated type value of the RPITIT inside
711                // the *impl*, so we can later use the impl's method args to normalize
712                // an RPITIT to a concrete type (`confirm_impl_trait_in_trait_candidate`).
713                //
714                // Due to the design of RPITITs, during AST lowering, we have no idea that
715                // an impl method corresponds to a trait method with RPITITs in it. Therefore,
716                // we don't have a list of early-bound region args for the RPITIT in the impl.
717                // Since early region parameters are index-based, we can't just rebase these
718                // (trait method) early-bound region args onto the impl, and there's no
719                // guarantee that the indices from the trait args and impl args line up.
720                // So to fix this, we subtract the number of trait args and add the number of
721                // impl args to *renumber* these early-bound regions to their corresponding
722                // indices in the impl's generic parameters list.
723                //
724                // Also, we only need to account for a difference in trait and impl args,
725                // since we previously enforce that the trait method and impl method have the
726                // same generics.
727                let num_trait_args = impl_trait_ref.args.len();
728                let num_impl_args = tcx.generics_of(impl_m.container_id(tcx)).own_params.len();
729                let ty = match ty.try_fold_with(&mut RemapHiddenTyRegions {
730                    tcx,
731                    map,
732                    num_trait_args,
733                    num_impl_args,
734                    def_id,
735                    impl_m_def_id: impl_m.def_id,
736                    ty,
737                    return_span,
738                }) {
739                    Ok(ty) => ty,
740                    Err(guar) => Ty::new_error(tcx, guar),
741                };
742                remapped_types.insert(def_id, ty::EarlyBinder::bind(ty));
743            }
744            Err(err) => {
745                // This code path is not reached in any tests, but may be
746                // reachable. If this is triggered, it should be converted to
747                // `span_delayed_bug` and the triggering case turned into a
748                // test.
749                tcx.dcx()
750                    .span_bug(return_span, format!("could not fully resolve: {ty} => {err:?}"));
751            }
752        }
753    }
754
755    // We may not collect all RPITITs that we see in the HIR for a trait signature
756    // because an RPITIT was located within a missing item. Like if we have a sig
757    // returning `-> Missing<impl Sized>`, that gets converted to `-> {type error}`,
758    // and when walking through the signature we end up never collecting the def id
759    // of the `impl Sized`. Insert that here, so we don't ICE later.
760    for assoc_item in tcx.associated_types_for_impl_traits_in_associated_fn(trait_m.def_id) {
761        if !remapped_types.contains_key(assoc_item) {
762            remapped_types.insert(
763                *assoc_item,
764                ty::EarlyBinder::bind(Ty::new_error_with_message(
765                    tcx,
766                    return_span,
767                    "missing synthetic item for RPITIT",
768                )),
769            );
770        }
771    }
772
773    Ok(&*tcx.arena.alloc(remapped_types))
774}
775
776struct ImplTraitInTraitCollector<'a, 'tcx, E> {
777    ocx: &'a ObligationCtxt<'a, 'tcx, E>,
778    types: FxIndexMap<DefId, (Ty<'tcx>, ty::GenericArgsRef<'tcx>)>,
779    span: Span,
780    param_env: ty::ParamEnv<'tcx>,
781    body_id: LocalDefId,
782}
783
784impl<'a, 'tcx, E> ImplTraitInTraitCollector<'a, 'tcx, E>
785where
786    E: 'tcx,
787{
788    fn new(
789        ocx: &'a ObligationCtxt<'a, 'tcx, E>,
790        span: Span,
791        param_env: ty::ParamEnv<'tcx>,
792        body_id: LocalDefId,
793    ) -> Self {
794        ImplTraitInTraitCollector { ocx, types: FxIndexMap::default(), span, param_env, body_id }
795    }
796}
797
798impl<'tcx, E> TypeFolder<TyCtxt<'tcx>> for ImplTraitInTraitCollector<'_, 'tcx, E>
799where
800    E: 'tcx,
801{
802    fn cx(&self) -> TyCtxt<'tcx> {
803        self.ocx.infcx.tcx
804    }
805
806    fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
807        if let ty::Alias(ty::Projection, proj) = ty.kind()
808            && self.cx().is_impl_trait_in_trait(proj.def_id)
809        {
810            if let Some((ty, _)) = self.types.get(&proj.def_id) {
811                return *ty;
812            }
813            //FIXME(RPITIT): Deny nested RPITIT in args too
814            if proj.args.has_escaping_bound_vars() {
815                bug!("FIXME(RPITIT): error here");
816            }
817            // Replace with infer var
818            let infer_ty = self.ocx.infcx.next_ty_var(self.span);
819            self.types.insert(proj.def_id, (infer_ty, proj.args));
820            // Recurse into bounds
821            for (pred, pred_span) in self
822                .cx()
823                .explicit_item_bounds(proj.def_id)
824                .iter_instantiated_copied(self.cx(), proj.args)
825            {
826                let pred = pred.fold_with(self);
827                let pred = self.ocx.normalize(
828                    &ObligationCause::misc(self.span, self.body_id),
829                    self.param_env,
830                    pred,
831                );
832
833                self.ocx.register_obligation(traits::Obligation::new(
834                    self.cx(),
835                    ObligationCause::new(
836                        self.span,
837                        self.body_id,
838                        ObligationCauseCode::WhereClause(proj.def_id, pred_span),
839                    ),
840                    self.param_env,
841                    pred,
842                ));
843            }
844            infer_ty
845        } else {
846            ty.super_fold_with(self)
847        }
848    }
849}
850
851struct RemapHiddenTyRegions<'tcx> {
852    tcx: TyCtxt<'tcx>,
853    /// Map from early/late params of the impl to identity regions of the RPITIT (GAT)
854    /// in the trait.
855    map: FxIndexMap<ty::Region<'tcx>, ty::Region<'tcx>>,
856    num_trait_args: usize,
857    num_impl_args: usize,
858    /// Def id of the RPITIT (GAT) in the *trait*.
859    def_id: DefId,
860    /// Def id of the impl method which owns the opaque hidden type we're remapping.
861    impl_m_def_id: DefId,
862    /// The hidden type we're remapping. Useful for diagnostics.
863    ty: Ty<'tcx>,
864    /// Span of the return type. Useful for diagnostics.
865    return_span: Span,
866}
867
868impl<'tcx> ty::FallibleTypeFolder<TyCtxt<'tcx>> for RemapHiddenTyRegions<'tcx> {
869    type Error = ErrorGuaranteed;
870
871    fn cx(&self) -> TyCtxt<'tcx> {
872        self.tcx
873    }
874
875    fn try_fold_region(
876        &mut self,
877        region: ty::Region<'tcx>,
878    ) -> Result<ty::Region<'tcx>, Self::Error> {
879        match region.kind() {
880            // Never remap bound regions or `'static`
881            ty::ReBound(..) | ty::ReStatic | ty::ReError(_) => return Ok(region),
882            // We always remap liberated late-bound regions from the function.
883            ty::ReLateParam(_) => {}
884            // Remap early-bound regions as long as they don't come from the `impl` itself,
885            // in which case we don't really need to renumber them.
886            ty::ReEarlyParam(ebr) => {
887                if ebr.index as usize >= self.num_impl_args {
888                    // Remap
889                } else {
890                    return Ok(region);
891                }
892            }
893            ty::ReVar(_) | ty::RePlaceholder(_) | ty::ReErased => unreachable!(
894                "should not have leaked vars or placeholders into hidden type of RPITIT"
895            ),
896        }
897
898        let e = if let Some(id_region) = self.map.get(&region) {
899            if let ty::ReEarlyParam(e) = id_region.kind() {
900                e
901            } else {
902                bug!(
903                    "expected to map region {region} to early-bound identity region, but got {id_region}"
904                );
905            }
906        } else {
907            let guar = match region.opt_param_def_id(self.tcx, self.impl_m_def_id) {
908                Some(def_id) => {
909                    let return_span = if let ty::Alias(ty::Opaque, opaque_ty) = self.ty.kind() {
910                        self.tcx.def_span(opaque_ty.def_id)
911                    } else {
912                        self.return_span
913                    };
914                    self.tcx
915                        .dcx()
916                        .struct_span_err(
917                            return_span,
918                            "return type captures more lifetimes than trait definition",
919                        )
920                        .with_span_label(self.tcx.def_span(def_id), "this lifetime was captured")
921                        .with_span_note(
922                            self.tcx.def_span(self.def_id),
923                            "hidden type must only reference lifetimes captured by this impl trait",
924                        )
925                        .with_note(format!("hidden type inferred to be `{}`", self.ty))
926                        .emit()
927                }
928                None => {
929                    // This code path is not reached in any tests, but may be
930                    // reachable. If this is triggered, it should be converted
931                    // to `delayed_bug` and the triggering case turned into a
932                    // test.
933                    self.tcx.dcx().bug("should've been able to remap region");
934                }
935            };
936            return Err(guar);
937        };
938
939        Ok(ty::Region::new_early_param(
940            self.tcx,
941            ty::EarlyParamRegion {
942                name: e.name,
943                index: (e.index as usize - self.num_trait_args + self.num_impl_args) as u32,
944            },
945        ))
946    }
947}
948
949/// Gets the string for an explicit self declaration, e.g. "self", "&self",
950/// etc.
951fn get_self_string<'tcx, P>(self_arg_ty: Ty<'tcx>, is_self_ty: P) -> String
952where
953    P: Fn(Ty<'tcx>) -> bool,
954{
955    if is_self_ty(self_arg_ty) {
956        "self".to_owned()
957    } else if let ty::Ref(_, ty, mutbl) = self_arg_ty.kind()
958        && is_self_ty(*ty)
959    {
960        match mutbl {
961            hir::Mutability::Not => "&self".to_owned(),
962            hir::Mutability::Mut => "&mut self".to_owned(),
963        }
964    } else {
965        format!("self: {self_arg_ty}")
966    }
967}
968
969fn report_trait_method_mismatch<'tcx>(
970    infcx: &InferCtxt<'tcx>,
971    mut cause: ObligationCause<'tcx>,
972    param_env: ty::ParamEnv<'tcx>,
973    terr: TypeError<'tcx>,
974    (trait_m, trait_sig): (ty::AssocItem, ty::FnSig<'tcx>),
975    (impl_m, impl_sig): (ty::AssocItem, ty::FnSig<'tcx>),
976    impl_trait_ref: ty::TraitRef<'tcx>,
977) -> ErrorGuaranteed {
978    let tcx = infcx.tcx;
979    let (impl_err_span, trait_err_span) =
980        extract_spans_for_error_reporting(infcx, terr, &cause, impl_m, trait_m);
981
982    let mut diag = struct_span_code_err!(
983        tcx.dcx(),
984        impl_err_span,
985        E0053,
986        "method `{}` has an incompatible type for trait",
987        trait_m.name()
988    );
989    match &terr {
990        TypeError::ArgumentMutability(0) | TypeError::ArgumentSorts(_, 0)
991            if trait_m.is_method() =>
992        {
993            let ty = trait_sig.inputs()[0];
994            let sugg = get_self_string(ty, |ty| ty == impl_trait_ref.self_ty());
995
996            // When the `impl` receiver is an arbitrary self type, like `self: Box<Self>`, the
997            // span points only at the type `Box<Self`>, but we want to cover the whole
998            // argument pattern and type.
999            let (sig, body) = tcx.hir_expect_impl_item(impl_m.def_id.expect_local()).expect_fn();
1000            let span = tcx
1001                .hir_body_param_idents(body)
1002                .zip(sig.decl.inputs.iter())
1003                .map(|(param_ident, ty)| {
1004                    if let Some(param_ident) = param_ident {
1005                        param_ident.span.to(ty.span)
1006                    } else {
1007                        ty.span
1008                    }
1009                })
1010                .next()
1011                .unwrap_or(impl_err_span);
1012
1013            diag.span_suggestion_verbose(
1014                span,
1015                "change the self-receiver type to match the trait",
1016                sugg,
1017                Applicability::MachineApplicable,
1018            );
1019        }
1020        TypeError::ArgumentMutability(i) | TypeError::ArgumentSorts(_, i) => {
1021            if trait_sig.inputs().len() == *i {
1022                // Suggestion to change output type. We do not suggest in `async` functions
1023                // to avoid complex logic or incorrect output.
1024                if let ImplItemKind::Fn(sig, _) =
1025                    &tcx.hir_expect_impl_item(impl_m.def_id.expect_local()).kind
1026                    && !sig.header.asyncness.is_async()
1027                {
1028                    let msg = "change the output type to match the trait";
1029                    let ap = Applicability::MachineApplicable;
1030                    match sig.decl.output {
1031                        hir::FnRetTy::DefaultReturn(sp) => {
1032                            let sugg = format!(" -> {}", trait_sig.output());
1033                            diag.span_suggestion_verbose(sp, msg, sugg, ap);
1034                        }
1035                        hir::FnRetTy::Return(hir_ty) => {
1036                            let sugg = trait_sig.output();
1037                            diag.span_suggestion_verbose(hir_ty.span, msg, sugg, ap);
1038                        }
1039                    };
1040                };
1041            } else if let Some(trait_ty) = trait_sig.inputs().get(*i) {
1042                diag.span_suggestion_verbose(
1043                    impl_err_span,
1044                    "change the parameter type to match the trait",
1045                    trait_ty,
1046                    Applicability::MachineApplicable,
1047                );
1048            }
1049        }
1050        _ => {}
1051    }
1052
1053    cause.span = impl_err_span;
1054    infcx.err_ctxt().note_type_err(
1055        &mut diag,
1056        &cause,
1057        trait_err_span.map(|sp| (sp, Cow::from("type in trait"), false)),
1058        Some(param_env.and(infer::ValuePairs::PolySigs(ExpectedFound {
1059            expected: ty::Binder::dummy(trait_sig),
1060            found: ty::Binder::dummy(impl_sig),
1061        }))),
1062        terr,
1063        false,
1064        None,
1065    );
1066
1067    diag.emit()
1068}
1069
1070fn check_region_bounds_on_impl_item<'tcx>(
1071    tcx: TyCtxt<'tcx>,
1072    impl_m: ty::AssocItem,
1073    trait_m: ty::AssocItem,
1074    delay: bool,
1075) -> Result<(), ErrorGuaranteed> {
1076    let impl_generics = tcx.generics_of(impl_m.def_id);
1077    let impl_params = impl_generics.own_counts().lifetimes;
1078
1079    let trait_generics = tcx.generics_of(trait_m.def_id);
1080    let trait_params = trait_generics.own_counts().lifetimes;
1081
1082    debug!(?trait_generics, ?impl_generics);
1083
1084    // Must have same number of early-bound lifetime parameters.
1085    // Unfortunately, if the user screws up the bounds, then this
1086    // will change classification between early and late. E.g.,
1087    // if in trait we have `<'a,'b:'a>`, and in impl we just have
1088    // `<'a,'b>`, then we have 2 early-bound lifetime parameters
1089    // in trait but 0 in the impl. But if we report "expected 2
1090    // but found 0" it's confusing, because it looks like there
1091    // are zero. Since I don't quite know how to phrase things at
1092    // the moment, give a kind of vague error message.
1093    if trait_params == impl_params {
1094        return Ok(());
1095    }
1096
1097    if !delay && let Some(guar) = check_region_late_boundedness(tcx, impl_m, trait_m) {
1098        return Err(guar);
1099    }
1100
1101    let span = tcx
1102        .hir_get_generics(impl_m.def_id.expect_local())
1103        .expect("expected impl item to have generics or else we can't compare them")
1104        .span;
1105
1106    let mut generics_span = None;
1107    let mut bounds_span = vec![];
1108    let mut where_span = None;
1109
1110    if let Some(trait_node) = tcx.hir_get_if_local(trait_m.def_id)
1111        && let Some(trait_generics) = trait_node.generics()
1112    {
1113        generics_span = Some(trait_generics.span);
1114        // FIXME: we could potentially look at the impl's bounds to not point at bounds that
1115        // *are* present in the impl.
1116        for p in trait_generics.predicates {
1117            match p.kind {
1118                hir::WherePredicateKind::BoundPredicate(hir::WhereBoundPredicate {
1119                    bounds,
1120                    ..
1121                })
1122                | hir::WherePredicateKind::RegionPredicate(hir::WhereRegionPredicate {
1123                    bounds,
1124                    ..
1125                }) => {
1126                    for b in *bounds {
1127                        if let hir::GenericBound::Outlives(lt) = b {
1128                            bounds_span.push(lt.ident.span);
1129                        }
1130                    }
1131                }
1132                _ => {}
1133            }
1134        }
1135        if let Some(impl_node) = tcx.hir_get_if_local(impl_m.def_id)
1136            && let Some(impl_generics) = impl_node.generics()
1137        {
1138            let mut impl_bounds = 0;
1139            for p in impl_generics.predicates {
1140                match p.kind {
1141                    hir::WherePredicateKind::BoundPredicate(hir::WhereBoundPredicate {
1142                        bounds,
1143                        ..
1144                    })
1145                    | hir::WherePredicateKind::RegionPredicate(hir::WhereRegionPredicate {
1146                        bounds,
1147                        ..
1148                    }) => {
1149                        for b in *bounds {
1150                            if let hir::GenericBound::Outlives(_) = b {
1151                                impl_bounds += 1;
1152                            }
1153                        }
1154                    }
1155                    _ => {}
1156                }
1157            }
1158            if impl_bounds == bounds_span.len() {
1159                bounds_span = vec![];
1160            } else if impl_generics.has_where_clause_predicates {
1161                where_span = Some(impl_generics.where_clause_span);
1162            }
1163        }
1164    }
1165
1166    let reported = tcx
1167        .dcx()
1168        .create_err(LifetimesOrBoundsMismatchOnTrait {
1169            span,
1170            item_kind: impl_m.descr(),
1171            ident: impl_m.ident(tcx),
1172            generics_span,
1173            bounds_span,
1174            where_span,
1175        })
1176        .emit_unless(delay);
1177
1178    Err(reported)
1179}
1180
1181#[allow(unused)]
1182enum LateEarlyMismatch<'tcx> {
1183    EarlyInImpl(DefId, DefId, ty::Region<'tcx>),
1184    LateInImpl(DefId, DefId, ty::Region<'tcx>),
1185}
1186
1187fn check_region_late_boundedness<'tcx>(
1188    tcx: TyCtxt<'tcx>,
1189    impl_m: ty::AssocItem,
1190    trait_m: ty::AssocItem,
1191) -> Option<ErrorGuaranteed> {
1192    if !impl_m.is_fn() {
1193        return None;
1194    }
1195
1196    let (infcx, param_env) = tcx
1197        .infer_ctxt()
1198        .build_with_typing_env(ty::TypingEnv::non_body_analysis(tcx, impl_m.def_id));
1199
1200    let impl_m_args = infcx.fresh_args_for_item(DUMMY_SP, impl_m.def_id);
1201    let impl_m_sig = tcx.fn_sig(impl_m.def_id).instantiate(tcx, impl_m_args);
1202    let impl_m_sig = tcx.liberate_late_bound_regions(impl_m.def_id, impl_m_sig);
1203
1204    let trait_m_args = infcx.fresh_args_for_item(DUMMY_SP, trait_m.def_id);
1205    let trait_m_sig = tcx.fn_sig(trait_m.def_id).instantiate(tcx, trait_m_args);
1206    let trait_m_sig = tcx.liberate_late_bound_regions(impl_m.def_id, trait_m_sig);
1207
1208    let ocx = ObligationCtxt::new(&infcx);
1209
1210    // Equate the signatures so that we can infer whether a late-bound param was present where
1211    // an early-bound param was expected, since we replace the late-bound lifetimes with
1212    // `ReLateParam`, and early-bound lifetimes with infer vars, so the early-bound args will
1213    // resolve to `ReLateParam` if there is a mismatch.
1214    let Ok(()) = ocx.eq(
1215        &ObligationCause::dummy(),
1216        param_env,
1217        ty::Binder::dummy(trait_m_sig),
1218        ty::Binder::dummy(impl_m_sig),
1219    ) else {
1220        return None;
1221    };
1222
1223    let errors = ocx.select_where_possible();
1224    if !errors.is_empty() {
1225        return None;
1226    }
1227
1228    let mut mismatched = vec![];
1229
1230    let impl_generics = tcx.generics_of(impl_m.def_id);
1231    for (id_arg, arg) in
1232        std::iter::zip(ty::GenericArgs::identity_for_item(tcx, impl_m.def_id), impl_m_args)
1233    {
1234        if let ty::GenericArgKind::Lifetime(r) = arg.kind()
1235            && let ty::ReVar(vid) = r.kind()
1236            && let r = infcx
1237                .inner
1238                .borrow_mut()
1239                .unwrap_region_constraints()
1240                .opportunistic_resolve_var(tcx, vid)
1241            && let ty::ReLateParam(ty::LateParamRegion {
1242                kind: ty::LateParamRegionKind::Named(trait_param_def_id, _),
1243                ..
1244            }) = r.kind()
1245            && let ty::ReEarlyParam(ebr) = id_arg.expect_region().kind()
1246        {
1247            mismatched.push(LateEarlyMismatch::EarlyInImpl(
1248                impl_generics.region_param(ebr, tcx).def_id,
1249                trait_param_def_id,
1250                id_arg.expect_region(),
1251            ));
1252        }
1253    }
1254
1255    let trait_generics = tcx.generics_of(trait_m.def_id);
1256    for (id_arg, arg) in
1257        std::iter::zip(ty::GenericArgs::identity_for_item(tcx, trait_m.def_id), trait_m_args)
1258    {
1259        if let ty::GenericArgKind::Lifetime(r) = arg.kind()
1260            && let ty::ReVar(vid) = r.kind()
1261            && let r = infcx
1262                .inner
1263                .borrow_mut()
1264                .unwrap_region_constraints()
1265                .opportunistic_resolve_var(tcx, vid)
1266            && let ty::ReLateParam(ty::LateParamRegion {
1267                kind: ty::LateParamRegionKind::Named(impl_param_def_id, _),
1268                ..
1269            }) = r.kind()
1270            && let ty::ReEarlyParam(ebr) = id_arg.expect_region().kind()
1271        {
1272            mismatched.push(LateEarlyMismatch::LateInImpl(
1273                impl_param_def_id,
1274                trait_generics.region_param(ebr, tcx).def_id,
1275                id_arg.expect_region(),
1276            ));
1277        }
1278    }
1279
1280    if mismatched.is_empty() {
1281        return None;
1282    }
1283
1284    let spans: Vec<_> = mismatched
1285        .iter()
1286        .map(|param| {
1287            let (LateEarlyMismatch::EarlyInImpl(impl_param_def_id, ..)
1288            | LateEarlyMismatch::LateInImpl(impl_param_def_id, ..)) = param;
1289            tcx.def_span(impl_param_def_id)
1290        })
1291        .collect();
1292
1293    let mut diag = tcx
1294        .dcx()
1295        .struct_span_err(spans, "lifetime parameters do not match the trait definition")
1296        .with_note("lifetime parameters differ in whether they are early- or late-bound")
1297        .with_code(E0195);
1298    for mismatch in mismatched {
1299        match mismatch {
1300            LateEarlyMismatch::EarlyInImpl(
1301                impl_param_def_id,
1302                trait_param_def_id,
1303                early_bound_region,
1304            ) => {
1305                let mut multispan = MultiSpan::from_spans(vec![
1306                    tcx.def_span(impl_param_def_id),
1307                    tcx.def_span(trait_param_def_id),
1308                ]);
1309                multispan
1310                    .push_span_label(tcx.def_span(tcx.parent(impl_m.def_id)), "in this impl...");
1311                multispan
1312                    .push_span_label(tcx.def_span(tcx.parent(trait_m.def_id)), "in this trait...");
1313                multispan.push_span_label(
1314                    tcx.def_span(impl_param_def_id),
1315                    format!("`{}` is early-bound", tcx.item_name(impl_param_def_id)),
1316                );
1317                multispan.push_span_label(
1318                    tcx.def_span(trait_param_def_id),
1319                    format!("`{}` is late-bound", tcx.item_name(trait_param_def_id)),
1320                );
1321                if let Some(span) =
1322                    find_region_in_predicates(tcx, impl_m.def_id, early_bound_region)
1323                {
1324                    multispan.push_span_label(
1325                        span,
1326                        format!(
1327                            "this lifetime bound makes `{}` early-bound",
1328                            tcx.item_name(impl_param_def_id)
1329                        ),
1330                    );
1331                }
1332                diag.span_note(
1333                    multispan,
1334                    format!(
1335                        "`{}` differs between the trait and impl",
1336                        tcx.item_name(impl_param_def_id)
1337                    ),
1338                );
1339            }
1340            LateEarlyMismatch::LateInImpl(
1341                impl_param_def_id,
1342                trait_param_def_id,
1343                early_bound_region,
1344            ) => {
1345                let mut multispan = MultiSpan::from_spans(vec![
1346                    tcx.def_span(impl_param_def_id),
1347                    tcx.def_span(trait_param_def_id),
1348                ]);
1349                multispan
1350                    .push_span_label(tcx.def_span(tcx.parent(impl_m.def_id)), "in this impl...");
1351                multispan
1352                    .push_span_label(tcx.def_span(tcx.parent(trait_m.def_id)), "in this trait...");
1353                multispan.push_span_label(
1354                    tcx.def_span(impl_param_def_id),
1355                    format!("`{}` is late-bound", tcx.item_name(impl_param_def_id)),
1356                );
1357                multispan.push_span_label(
1358                    tcx.def_span(trait_param_def_id),
1359                    format!("`{}` is early-bound", tcx.item_name(trait_param_def_id)),
1360                );
1361                if let Some(span) =
1362                    find_region_in_predicates(tcx, trait_m.def_id, early_bound_region)
1363                {
1364                    multispan.push_span_label(
1365                        span,
1366                        format!(
1367                            "this lifetime bound makes `{}` early-bound",
1368                            tcx.item_name(trait_param_def_id)
1369                        ),
1370                    );
1371                }
1372                diag.span_note(
1373                    multispan,
1374                    format!(
1375                        "`{}` differs between the trait and impl",
1376                        tcx.item_name(impl_param_def_id)
1377                    ),
1378                );
1379            }
1380        }
1381    }
1382
1383    Some(diag.emit())
1384}
1385
1386fn find_region_in_predicates<'tcx>(
1387    tcx: TyCtxt<'tcx>,
1388    def_id: DefId,
1389    early_bound_region: ty::Region<'tcx>,
1390) -> Option<Span> {
1391    for (pred, span) in tcx.explicit_predicates_of(def_id).instantiate_identity(tcx) {
1392        if pred.visit_with(&mut FindRegion(early_bound_region)).is_break() {
1393            return Some(span);
1394        }
1395    }
1396
1397    struct FindRegion<'tcx>(ty::Region<'tcx>);
1398    impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for FindRegion<'tcx> {
1399        type Result = ControlFlow<()>;
1400        fn visit_region(&mut self, r: ty::Region<'tcx>) -> Self::Result {
1401            if r == self.0 { ControlFlow::Break(()) } else { ControlFlow::Continue(()) }
1402        }
1403    }
1404
1405    None
1406}
1407
1408#[instrument(level = "debug", skip(infcx))]
1409fn extract_spans_for_error_reporting<'tcx>(
1410    infcx: &infer::InferCtxt<'tcx>,
1411    terr: TypeError<'_>,
1412    cause: &ObligationCause<'tcx>,
1413    impl_m: ty::AssocItem,
1414    trait_m: ty::AssocItem,
1415) -> (Span, Option<Span>) {
1416    let tcx = infcx.tcx;
1417    let mut impl_args = {
1418        let (sig, _) = tcx.hir_expect_impl_item(impl_m.def_id.expect_local()).expect_fn();
1419        sig.decl.inputs.iter().map(|t| t.span).chain(iter::once(sig.decl.output.span()))
1420    };
1421
1422    let trait_args = trait_m.def_id.as_local().map(|def_id| {
1423        let (sig, _) = tcx.hir_expect_trait_item(def_id).expect_fn();
1424        sig.decl.inputs.iter().map(|t| t.span).chain(iter::once(sig.decl.output.span()))
1425    });
1426
1427    match terr {
1428        TypeError::ArgumentMutability(i) | TypeError::ArgumentSorts(ExpectedFound { .. }, i) => {
1429            (impl_args.nth(i).unwrap(), trait_args.and_then(|mut args| args.nth(i)))
1430        }
1431        _ => (cause.span, tcx.hir_span_if_local(trait_m.def_id)),
1432    }
1433}
1434
1435fn compare_self_type<'tcx>(
1436    tcx: TyCtxt<'tcx>,
1437    impl_m: ty::AssocItem,
1438    trait_m: ty::AssocItem,
1439    impl_trait_ref: ty::TraitRef<'tcx>,
1440    delay: bool,
1441) -> Result<(), ErrorGuaranteed> {
1442    // Try to give more informative error messages about self typing
1443    // mismatches. Note that any mismatch will also be detected
1444    // below, where we construct a canonical function type that
1445    // includes the self parameter as a normal parameter. It's just
1446    // that the error messages you get out of this code are a bit more
1447    // inscrutable, particularly for cases where one method has no
1448    // self.
1449
1450    let self_string = |method: ty::AssocItem| {
1451        let untransformed_self_ty = match method.container {
1452            ty::AssocItemContainer::Impl => impl_trait_ref.self_ty(),
1453            ty::AssocItemContainer::Trait => tcx.types.self_param,
1454        };
1455        let self_arg_ty = tcx.fn_sig(method.def_id).instantiate_identity().input(0);
1456        let (infcx, param_env) = tcx
1457            .infer_ctxt()
1458            .build_with_typing_env(ty::TypingEnv::non_body_analysis(tcx, method.def_id));
1459        let self_arg_ty = tcx.liberate_late_bound_regions(method.def_id, self_arg_ty);
1460        let can_eq_self = |ty| infcx.can_eq(param_env, untransformed_self_ty, ty);
1461        get_self_string(self_arg_ty, can_eq_self)
1462    };
1463
1464    match (trait_m.is_method(), impl_m.is_method()) {
1465        (false, false) | (true, true) => {}
1466
1467        (false, true) => {
1468            let self_descr = self_string(impl_m);
1469            let impl_m_span = tcx.def_span(impl_m.def_id);
1470            let mut err = struct_span_code_err!(
1471                tcx.dcx(),
1472                impl_m_span,
1473                E0185,
1474                "method `{}` has a `{}` declaration in the impl, but not in the trait",
1475                trait_m.name(),
1476                self_descr
1477            );
1478            err.span_label(impl_m_span, format!("`{self_descr}` used in impl"));
1479            if let Some(span) = tcx.hir_span_if_local(trait_m.def_id) {
1480                err.span_label(span, format!("trait method declared without `{self_descr}`"));
1481            } else {
1482                err.note_trait_signature(trait_m.name(), trait_m.signature(tcx));
1483            }
1484            return Err(err.emit_unless(delay));
1485        }
1486
1487        (true, false) => {
1488            let self_descr = self_string(trait_m);
1489            let impl_m_span = tcx.def_span(impl_m.def_id);
1490            let mut err = struct_span_code_err!(
1491                tcx.dcx(),
1492                impl_m_span,
1493                E0186,
1494                "method `{}` has a `{}` declaration in the trait, but not in the impl",
1495                trait_m.name(),
1496                self_descr
1497            );
1498            err.span_label(impl_m_span, format!("expected `{self_descr}` in impl"));
1499            if let Some(span) = tcx.hir_span_if_local(trait_m.def_id) {
1500                err.span_label(span, format!("`{self_descr}` used in trait"));
1501            } else {
1502                err.note_trait_signature(trait_m.name(), trait_m.signature(tcx));
1503            }
1504
1505            return Err(err.emit_unless(delay));
1506        }
1507    }
1508
1509    Ok(())
1510}
1511
1512/// Checks that the number of generics on a given assoc item in a trait impl is the same
1513/// as the number of generics on the respective assoc item in the trait definition.
1514///
1515/// For example this code emits the errors in the following code:
1516/// ```rust,compile_fail
1517/// trait Trait {
1518///     fn foo();
1519///     type Assoc<T>;
1520/// }
1521///
1522/// impl Trait for () {
1523///     fn foo<T>() {}
1524///     //~^ error
1525///     type Assoc = u32;
1526///     //~^ error
1527/// }
1528/// ```
1529///
1530/// Notably this does not error on `foo<T>` implemented as `foo<const N: u8>` or
1531/// `foo<const N: u8>` implemented as `foo<const N: u32>`. This is handled in
1532/// [`compare_generic_param_kinds`]. This function also does not handle lifetime parameters
1533fn compare_number_of_generics<'tcx>(
1534    tcx: TyCtxt<'tcx>,
1535    impl_: ty::AssocItem,
1536    trait_: ty::AssocItem,
1537    delay: bool,
1538) -> Result<(), ErrorGuaranteed> {
1539    let trait_own_counts = tcx.generics_of(trait_.def_id).own_counts();
1540    let impl_own_counts = tcx.generics_of(impl_.def_id).own_counts();
1541
1542    // This avoids us erroring on `foo<T>` implemented as `foo<const N: u8>` as this is implemented
1543    // in `compare_generic_param_kinds` which will give a nicer error message than something like:
1544    // "expected 1 type parameter, found 0 type parameters"
1545    if (trait_own_counts.types + trait_own_counts.consts)
1546        == (impl_own_counts.types + impl_own_counts.consts)
1547    {
1548        return Ok(());
1549    }
1550
1551    // We never need to emit a separate error for RPITITs, since if an RPITIT
1552    // has mismatched type or const generic arguments, then the method that it's
1553    // inheriting the generics from will also have mismatched arguments, and
1554    // we'll report an error for that instead. Delay a bug for safety, though.
1555    if trait_.is_impl_trait_in_trait() {
1556        // FIXME: no tests trigger this. If you find example code that does
1557        // trigger this, please add it to the test suite.
1558        tcx.dcx()
1559            .bug("errors comparing numbers of generics of trait/impl functions were not emitted");
1560    }
1561
1562    let matchings = [
1563        ("type", trait_own_counts.types, impl_own_counts.types),
1564        ("const", trait_own_counts.consts, impl_own_counts.consts),
1565    ];
1566
1567    let item_kind = impl_.descr();
1568
1569    let mut err_occurred = None;
1570    for (kind, trait_count, impl_count) in matchings {
1571        if impl_count != trait_count {
1572            let arg_spans = |item: &ty::AssocItem, generics: &hir::Generics<'_>| {
1573                let mut spans = generics
1574                    .params
1575                    .iter()
1576                    .filter(|p| match p.kind {
1577                        hir::GenericParamKind::Lifetime {
1578                            kind: hir::LifetimeParamKind::Elided(_),
1579                        } => {
1580                            // A fn can have an arbitrary number of extra elided lifetimes for the
1581                            // same signature.
1582                            !item.is_fn()
1583                        }
1584                        _ => true,
1585                    })
1586                    .map(|p| p.span)
1587                    .collect::<Vec<Span>>();
1588                if spans.is_empty() {
1589                    spans = vec![generics.span]
1590                }
1591                spans
1592            };
1593            let (trait_spans, impl_trait_spans) = if let Some(def_id) = trait_.def_id.as_local() {
1594                let trait_item = tcx.hir_expect_trait_item(def_id);
1595                let arg_spans: Vec<Span> = arg_spans(&trait_, trait_item.generics);
1596                let impl_trait_spans: Vec<Span> = trait_item
1597                    .generics
1598                    .params
1599                    .iter()
1600                    .filter_map(|p| match p.kind {
1601                        GenericParamKind::Type { synthetic: true, .. } => Some(p.span),
1602                        _ => None,
1603                    })
1604                    .collect();
1605                (Some(arg_spans), impl_trait_spans)
1606            } else {
1607                let trait_span = tcx.hir_span_if_local(trait_.def_id);
1608                (trait_span.map(|s| vec![s]), vec![])
1609            };
1610
1611            let impl_item = tcx.hir_expect_impl_item(impl_.def_id.expect_local());
1612            let impl_item_impl_trait_spans: Vec<Span> = impl_item
1613                .generics
1614                .params
1615                .iter()
1616                .filter_map(|p| match p.kind {
1617                    GenericParamKind::Type { synthetic: true, .. } => Some(p.span),
1618                    _ => None,
1619                })
1620                .collect();
1621            let spans = arg_spans(&impl_, impl_item.generics);
1622            let span = spans.first().copied();
1623
1624            let mut err = tcx.dcx().struct_span_err(
1625                spans,
1626                format!(
1627                    "{} `{}` has {} {kind} parameter{} but its trait \
1628                     declaration has {} {kind} parameter{}",
1629                    item_kind,
1630                    trait_.name(),
1631                    impl_count,
1632                    pluralize!(impl_count),
1633                    trait_count,
1634                    pluralize!(trait_count),
1635                    kind = kind,
1636                ),
1637            );
1638            err.code(E0049);
1639
1640            let msg =
1641                format!("expected {trait_count} {kind} parameter{}", pluralize!(trait_count),);
1642            if let Some(spans) = trait_spans {
1643                let mut spans = spans.iter();
1644                if let Some(span) = spans.next() {
1645                    err.span_label(*span, msg);
1646                }
1647                for span in spans {
1648                    err.span_label(*span, "");
1649                }
1650            } else {
1651                err.span_label(tcx.def_span(trait_.def_id), msg);
1652            }
1653
1654            if let Some(span) = span {
1655                err.span_label(
1656                    span,
1657                    format!("found {} {} parameter{}", impl_count, kind, pluralize!(impl_count),),
1658                );
1659            }
1660
1661            for span in impl_trait_spans.iter().chain(impl_item_impl_trait_spans.iter()) {
1662                err.span_label(*span, "`impl Trait` introduces an implicit type parameter");
1663            }
1664
1665            let reported = err.emit_unless(delay);
1666            err_occurred = Some(reported);
1667        }
1668    }
1669
1670    if let Some(reported) = err_occurred { Err(reported) } else { Ok(()) }
1671}
1672
1673fn compare_number_of_method_arguments<'tcx>(
1674    tcx: TyCtxt<'tcx>,
1675    impl_m: ty::AssocItem,
1676    trait_m: ty::AssocItem,
1677    delay: bool,
1678) -> Result<(), ErrorGuaranteed> {
1679    let impl_m_fty = tcx.fn_sig(impl_m.def_id);
1680    let trait_m_fty = tcx.fn_sig(trait_m.def_id);
1681    let trait_number_args = trait_m_fty.skip_binder().inputs().skip_binder().len();
1682    let impl_number_args = impl_m_fty.skip_binder().inputs().skip_binder().len();
1683
1684    if trait_number_args != impl_number_args {
1685        let trait_span = trait_m
1686            .def_id
1687            .as_local()
1688            .and_then(|def_id| {
1689                let (trait_m_sig, _) = &tcx.hir_expect_trait_item(def_id).expect_fn();
1690                let pos = trait_number_args.saturating_sub(1);
1691                trait_m_sig.decl.inputs.get(pos).map(|arg| {
1692                    if pos == 0 {
1693                        arg.span
1694                    } else {
1695                        arg.span.with_lo(trait_m_sig.decl.inputs[0].span.lo())
1696                    }
1697                })
1698            })
1699            .or_else(|| tcx.hir_span_if_local(trait_m.def_id));
1700
1701        let (impl_m_sig, _) = &tcx.hir_expect_impl_item(impl_m.def_id.expect_local()).expect_fn();
1702        let pos = impl_number_args.saturating_sub(1);
1703        let impl_span = impl_m_sig
1704            .decl
1705            .inputs
1706            .get(pos)
1707            .map(|arg| {
1708                if pos == 0 {
1709                    arg.span
1710                } else {
1711                    arg.span.with_lo(impl_m_sig.decl.inputs[0].span.lo())
1712                }
1713            })
1714            .unwrap_or_else(|| tcx.def_span(impl_m.def_id));
1715
1716        let mut err = struct_span_code_err!(
1717            tcx.dcx(),
1718            impl_span,
1719            E0050,
1720            "method `{}` has {} but the declaration in trait `{}` has {}",
1721            trait_m.name(),
1722            potentially_plural_count(impl_number_args, "parameter"),
1723            tcx.def_path_str(trait_m.def_id),
1724            trait_number_args
1725        );
1726
1727        if let Some(trait_span) = trait_span {
1728            err.span_label(
1729                trait_span,
1730                format!(
1731                    "trait requires {}",
1732                    potentially_plural_count(trait_number_args, "parameter")
1733                ),
1734            );
1735        } else {
1736            err.note_trait_signature(trait_m.name(), trait_m.signature(tcx));
1737        }
1738
1739        err.span_label(
1740            impl_span,
1741            format!(
1742                "expected {}, found {}",
1743                potentially_plural_count(trait_number_args, "parameter"),
1744                impl_number_args
1745            ),
1746        );
1747
1748        return Err(err.emit_unless(delay));
1749    }
1750
1751    Ok(())
1752}
1753
1754fn compare_synthetic_generics<'tcx>(
1755    tcx: TyCtxt<'tcx>,
1756    impl_m: ty::AssocItem,
1757    trait_m: ty::AssocItem,
1758    delay: bool,
1759) -> Result<(), ErrorGuaranteed> {
1760    // FIXME(chrisvittal) Clean up this function, list of FIXME items:
1761    //     1. Better messages for the span labels
1762    //     2. Explanation as to what is going on
1763    // If we get here, we already have the same number of generics, so the zip will
1764    // be okay.
1765    let mut error_found = None;
1766    let impl_m_generics = tcx.generics_of(impl_m.def_id);
1767    let trait_m_generics = tcx.generics_of(trait_m.def_id);
1768    let impl_m_type_params =
1769        impl_m_generics.own_params.iter().filter_map(|param| match param.kind {
1770            GenericParamDefKind::Type { synthetic, .. } => Some((param.def_id, synthetic)),
1771            GenericParamDefKind::Lifetime | GenericParamDefKind::Const { .. } => None,
1772        });
1773    let trait_m_type_params =
1774        trait_m_generics.own_params.iter().filter_map(|param| match param.kind {
1775            GenericParamDefKind::Type { synthetic, .. } => Some((param.def_id, synthetic)),
1776            GenericParamDefKind::Lifetime | GenericParamDefKind::Const { .. } => None,
1777        });
1778    for ((impl_def_id, impl_synthetic), (trait_def_id, trait_synthetic)) in
1779        iter::zip(impl_m_type_params, trait_m_type_params)
1780    {
1781        if impl_synthetic != trait_synthetic {
1782            let impl_def_id = impl_def_id.expect_local();
1783            let impl_span = tcx.def_span(impl_def_id);
1784            let trait_span = tcx.def_span(trait_def_id);
1785            let mut err = struct_span_code_err!(
1786                tcx.dcx(),
1787                impl_span,
1788                E0643,
1789                "method `{}` has incompatible signature for trait",
1790                trait_m.name()
1791            );
1792            err.span_label(trait_span, "declaration in trait here");
1793            if impl_synthetic {
1794                // The case where the impl method uses `impl Trait` but the trait method uses
1795                // explicit generics
1796                err.span_label(impl_span, "expected generic parameter, found `impl Trait`");
1797                let _: Option<_> = try {
1798                    // try taking the name from the trait impl
1799                    // FIXME: this is obviously suboptimal since the name can already be used
1800                    // as another generic argument
1801                    let new_name = tcx.opt_item_name(trait_def_id)?;
1802                    let trait_m = trait_m.def_id.as_local()?;
1803                    let trait_m = tcx.hir_expect_trait_item(trait_m);
1804
1805                    let impl_m = impl_m.def_id.as_local()?;
1806                    let impl_m = tcx.hir_expect_impl_item(impl_m);
1807
1808                    // in case there are no generics, take the spot between the function name
1809                    // and the opening paren of the argument list
1810                    let new_generics_span = tcx.def_ident_span(impl_def_id)?.shrink_to_hi();
1811                    // in case there are generics, just replace them
1812                    let generics_span = impl_m.generics.span.substitute_dummy(new_generics_span);
1813                    // replace with the generics from the trait
1814                    let new_generics =
1815                        tcx.sess.source_map().span_to_snippet(trait_m.generics.span).ok()?;
1816
1817                    err.multipart_suggestion(
1818                        "try changing the `impl Trait` argument to a generic parameter",
1819                        vec![
1820                            // replace `impl Trait` with `T`
1821                            (impl_span, new_name.to_string()),
1822                            // replace impl method generics with trait method generics
1823                            // This isn't quite right, as users might have changed the names
1824                            // of the generics, but it works for the common case
1825                            (generics_span, new_generics),
1826                        ],
1827                        Applicability::MaybeIncorrect,
1828                    );
1829                };
1830            } else {
1831                // The case where the trait method uses `impl Trait`, but the impl method uses
1832                // explicit generics.
1833                err.span_label(impl_span, "expected `impl Trait`, found generic parameter");
1834                let _: Option<_> = try {
1835                    let impl_m = impl_m.def_id.as_local()?;
1836                    let impl_m = tcx.hir_expect_impl_item(impl_m);
1837                    let (sig, _) = impl_m.expect_fn();
1838                    let input_tys = sig.decl.inputs;
1839
1840                    struct Visitor(hir::def_id::LocalDefId);
1841                    impl<'v> intravisit::Visitor<'v> for Visitor {
1842                        type Result = ControlFlow<Span>;
1843                        fn visit_ty(&mut self, ty: &'v hir::Ty<'v, AmbigArg>) -> Self::Result {
1844                            if let hir::TyKind::Path(hir::QPath::Resolved(None, path)) = ty.kind
1845                                && let Res::Def(DefKind::TyParam, def_id) = path.res
1846                                && def_id == self.0.to_def_id()
1847                            {
1848                                ControlFlow::Break(ty.span)
1849                            } else {
1850                                intravisit::walk_ty(self, ty)
1851                            }
1852                        }
1853                    }
1854
1855                    let span = input_tys
1856                        .iter()
1857                        .find_map(|ty| Visitor(impl_def_id).visit_ty_unambig(ty).break_value())?;
1858
1859                    let bounds = impl_m.generics.bounds_for_param(impl_def_id).next()?.bounds;
1860                    let bounds = bounds.first()?.span().to(bounds.last()?.span());
1861                    let bounds = tcx.sess.source_map().span_to_snippet(bounds).ok()?;
1862
1863                    err.multipart_suggestion(
1864                        "try removing the generic parameter and using `impl Trait` instead",
1865                        vec![
1866                            // delete generic parameters
1867                            (impl_m.generics.span, String::new()),
1868                            // replace param usage with `impl Trait`
1869                            (span, format!("impl {bounds}")),
1870                        ],
1871                        Applicability::MaybeIncorrect,
1872                    );
1873                };
1874            }
1875            error_found = Some(err.emit_unless(delay));
1876        }
1877    }
1878    if let Some(reported) = error_found { Err(reported) } else { Ok(()) }
1879}
1880
1881/// Checks that all parameters in the generics of a given assoc item in a trait impl have
1882/// the same kind as the respective generic parameter in the trait def.
1883///
1884/// For example all 4 errors in the following code are emitted here:
1885/// ```rust,ignore (pseudo-Rust)
1886/// trait Foo {
1887///     fn foo<const N: u8>();
1888///     type Bar<const N: u8>;
1889///     fn baz<const N: u32>();
1890///     type Blah<T>;
1891/// }
1892///
1893/// impl Foo for () {
1894///     fn foo<const N: u64>() {}
1895///     //~^ error
1896///     type Bar<const N: u64> = ();
1897///     //~^ error
1898///     fn baz<T>() {}
1899///     //~^ error
1900///     type Blah<const N: i64> = u32;
1901///     //~^ error
1902/// }
1903/// ```
1904///
1905/// This function does not handle lifetime parameters
1906fn compare_generic_param_kinds<'tcx>(
1907    tcx: TyCtxt<'tcx>,
1908    impl_item: ty::AssocItem,
1909    trait_item: ty::AssocItem,
1910    delay: bool,
1911) -> Result<(), ErrorGuaranteed> {
1912    assert_eq!(impl_item.as_tag(), trait_item.as_tag());
1913
1914    let ty_const_params_of = |def_id| {
1915        tcx.generics_of(def_id).own_params.iter().filter(|param| {
1916            matches!(
1917                param.kind,
1918                GenericParamDefKind::Const { .. } | GenericParamDefKind::Type { .. }
1919            )
1920        })
1921    };
1922
1923    for (param_impl, param_trait) in
1924        iter::zip(ty_const_params_of(impl_item.def_id), ty_const_params_of(trait_item.def_id))
1925    {
1926        use GenericParamDefKind::*;
1927        if match (&param_impl.kind, &param_trait.kind) {
1928            (Const { .. }, Const { .. })
1929                if tcx.type_of(param_impl.def_id) != tcx.type_of(param_trait.def_id) =>
1930            {
1931                true
1932            }
1933            (Const { .. }, Type { .. }) | (Type { .. }, Const { .. }) => true,
1934            // this is exhaustive so that anyone adding new generic param kinds knows
1935            // to make sure this error is reported for them.
1936            (Const { .. }, Const { .. }) | (Type { .. }, Type { .. }) => false,
1937            (Lifetime { .. }, _) | (_, Lifetime { .. }) => {
1938                bug!("lifetime params are expected to be filtered by `ty_const_params_of`")
1939            }
1940        } {
1941            let param_impl_span = tcx.def_span(param_impl.def_id);
1942            let param_trait_span = tcx.def_span(param_trait.def_id);
1943
1944            let mut err = struct_span_code_err!(
1945                tcx.dcx(),
1946                param_impl_span,
1947                E0053,
1948                "{} `{}` has an incompatible generic parameter for trait `{}`",
1949                impl_item.descr(),
1950                trait_item.name(),
1951                &tcx.def_path_str(tcx.parent(trait_item.def_id))
1952            );
1953
1954            let make_param_message = |prefix: &str, param: &ty::GenericParamDef| match param.kind {
1955                Const { .. } => {
1956                    format!(
1957                        "{} const parameter of type `{}`",
1958                        prefix,
1959                        tcx.type_of(param.def_id).instantiate_identity()
1960                    )
1961                }
1962                Type { .. } => format!("{prefix} type parameter"),
1963                Lifetime { .. } => span_bug!(
1964                    tcx.def_span(param.def_id),
1965                    "lifetime params are expected to be filtered by `ty_const_params_of`"
1966                ),
1967            };
1968
1969            let trait_header_span = tcx.def_ident_span(tcx.parent(trait_item.def_id)).unwrap();
1970            err.span_label(trait_header_span, "");
1971            err.span_label(param_trait_span, make_param_message("expected", param_trait));
1972
1973            let impl_header_span = tcx.def_span(tcx.parent(impl_item.def_id));
1974            err.span_label(impl_header_span, "");
1975            err.span_label(param_impl_span, make_param_message("found", param_impl));
1976
1977            let reported = err.emit_unless(delay);
1978            return Err(reported);
1979        }
1980    }
1981
1982    Ok(())
1983}
1984
1985fn compare_impl_const<'tcx>(
1986    tcx: TyCtxt<'tcx>,
1987    impl_const_item: ty::AssocItem,
1988    trait_const_item: ty::AssocItem,
1989    impl_trait_ref: ty::TraitRef<'tcx>,
1990) -> Result<(), ErrorGuaranteed> {
1991    compare_number_of_generics(tcx, impl_const_item, trait_const_item, false)?;
1992    compare_generic_param_kinds(tcx, impl_const_item, trait_const_item, false)?;
1993    check_region_bounds_on_impl_item(tcx, impl_const_item, trait_const_item, false)?;
1994    compare_const_predicate_entailment(tcx, impl_const_item, trait_const_item, impl_trait_ref)
1995}
1996
1997/// The equivalent of [compare_method_predicate_entailment], but for associated constants
1998/// instead of associated functions.
1999// FIXME(generic_const_items): If possible extract the common parts of `compare_{type,const}_predicate_entailment`.
2000#[instrument(level = "debug", skip(tcx))]
2001fn compare_const_predicate_entailment<'tcx>(
2002    tcx: TyCtxt<'tcx>,
2003    impl_ct: ty::AssocItem,
2004    trait_ct: ty::AssocItem,
2005    impl_trait_ref: ty::TraitRef<'tcx>,
2006) -> Result<(), ErrorGuaranteed> {
2007    let impl_ct_def_id = impl_ct.def_id.expect_local();
2008    let impl_ct_span = tcx.def_span(impl_ct_def_id);
2009
2010    // The below is for the most part highly similar to the procedure
2011    // for methods above. It is simpler in many respects, especially
2012    // because we shouldn't really have to deal with lifetimes or
2013    // predicates. In fact some of this should probably be put into
2014    // shared functions because of DRY violations...
2015    let trait_to_impl_args = GenericArgs::identity_for_item(tcx, impl_ct.def_id).rebase_onto(
2016        tcx,
2017        impl_ct.container_id(tcx),
2018        impl_trait_ref.args,
2019    );
2020
2021    // Create a parameter environment that represents the implementation's
2022    // associated const.
2023    let impl_ty = tcx.type_of(impl_ct_def_id).instantiate_identity();
2024
2025    let trait_ty = tcx.type_of(trait_ct.def_id).instantiate(tcx, trait_to_impl_args);
2026    let code = ObligationCauseCode::CompareImplItem {
2027        impl_item_def_id: impl_ct_def_id,
2028        trait_item_def_id: trait_ct.def_id,
2029        kind: impl_ct.kind,
2030    };
2031    let mut cause = ObligationCause::new(impl_ct_span, impl_ct_def_id, code.clone());
2032
2033    let impl_ct_predicates = tcx.predicates_of(impl_ct.def_id);
2034    let trait_ct_predicates = tcx.predicates_of(trait_ct.def_id);
2035
2036    // The predicates declared by the impl definition, the trait and the
2037    // associated const in the trait are assumed.
2038    let impl_predicates = tcx.predicates_of(impl_ct_predicates.parent.unwrap());
2039    let mut hybrid_preds = impl_predicates.instantiate_identity(tcx).predicates;
2040    hybrid_preds.extend(
2041        trait_ct_predicates
2042            .instantiate_own(tcx, trait_to_impl_args)
2043            .map(|(predicate, _)| predicate),
2044    );
2045
2046    let param_env = ty::ParamEnv::new(tcx.mk_clauses(&hybrid_preds));
2047    let param_env = traits::normalize_param_env_or_error(
2048        tcx,
2049        param_env,
2050        ObligationCause::misc(impl_ct_span, impl_ct_def_id),
2051    );
2052
2053    let infcx = tcx.infer_ctxt().build(TypingMode::non_body_analysis());
2054    let ocx = ObligationCtxt::new_with_diagnostics(&infcx);
2055
2056    let impl_ct_own_bounds = impl_ct_predicates.instantiate_own_identity();
2057    for (predicate, span) in impl_ct_own_bounds {
2058        let cause = ObligationCause::misc(span, impl_ct_def_id);
2059        let predicate = ocx.normalize(&cause, param_env, predicate);
2060
2061        let cause = ObligationCause::new(span, impl_ct_def_id, code.clone());
2062        ocx.register_obligation(traits::Obligation::new(tcx, cause, param_env, predicate));
2063    }
2064
2065    // There is no "body" here, so just pass dummy id.
2066    let impl_ty = ocx.normalize(&cause, param_env, impl_ty);
2067    debug!(?impl_ty);
2068
2069    let trait_ty = ocx.normalize(&cause, param_env, trait_ty);
2070    debug!(?trait_ty);
2071
2072    let err = ocx.sup(&cause, param_env, trait_ty, impl_ty);
2073
2074    if let Err(terr) = err {
2075        debug!(?impl_ty, ?trait_ty);
2076
2077        // Locate the Span containing just the type of the offending impl
2078        let (ty, _) = tcx.hir_expect_impl_item(impl_ct_def_id).expect_const();
2079        cause.span = ty.span;
2080
2081        let mut diag = struct_span_code_err!(
2082            tcx.dcx(),
2083            cause.span,
2084            E0326,
2085            "implemented const `{}` has an incompatible type for trait",
2086            trait_ct.name()
2087        );
2088
2089        let trait_c_span = trait_ct.def_id.as_local().map(|trait_ct_def_id| {
2090            // Add a label to the Span containing just the type of the const
2091            let (ty, _) = tcx.hir_expect_trait_item(trait_ct_def_id).expect_const();
2092            ty.span
2093        });
2094
2095        infcx.err_ctxt().note_type_err(
2096            &mut diag,
2097            &cause,
2098            trait_c_span.map(|span| (span, Cow::from("type in trait"), false)),
2099            Some(param_env.and(infer::ValuePairs::Terms(ExpectedFound {
2100                expected: trait_ty.into(),
2101                found: impl_ty.into(),
2102            }))),
2103            terr,
2104            false,
2105            None,
2106        );
2107        return Err(diag.emit());
2108    };
2109
2110    // Check that all obligations are satisfied by the implementation's
2111    // version.
2112    let errors = ocx.select_all_or_error();
2113    if !errors.is_empty() {
2114        return Err(infcx.err_ctxt().report_fulfillment_errors(errors));
2115    }
2116
2117    ocx.resolve_regions_and_report_errors(impl_ct_def_id, param_env, [])
2118}
2119
2120#[instrument(level = "debug", skip(tcx))]
2121fn compare_impl_ty<'tcx>(
2122    tcx: TyCtxt<'tcx>,
2123    impl_ty: ty::AssocItem,
2124    trait_ty: ty::AssocItem,
2125    impl_trait_ref: ty::TraitRef<'tcx>,
2126) -> Result<(), ErrorGuaranteed> {
2127    compare_number_of_generics(tcx, impl_ty, trait_ty, false)?;
2128    compare_generic_param_kinds(tcx, impl_ty, trait_ty, false)?;
2129    check_region_bounds_on_impl_item(tcx, impl_ty, trait_ty, false)?;
2130    compare_type_predicate_entailment(tcx, impl_ty, trait_ty, impl_trait_ref)?;
2131    check_type_bounds(tcx, trait_ty, impl_ty, impl_trait_ref)
2132}
2133
2134/// The equivalent of [compare_method_predicate_entailment], but for associated types
2135/// instead of associated functions.
2136#[instrument(level = "debug", skip(tcx))]
2137fn compare_type_predicate_entailment<'tcx>(
2138    tcx: TyCtxt<'tcx>,
2139    impl_ty: ty::AssocItem,
2140    trait_ty: ty::AssocItem,
2141    impl_trait_ref: ty::TraitRef<'tcx>,
2142) -> Result<(), ErrorGuaranteed> {
2143    let impl_def_id = impl_ty.container_id(tcx);
2144    let trait_to_impl_args = GenericArgs::identity_for_item(tcx, impl_ty.def_id).rebase_onto(
2145        tcx,
2146        impl_def_id,
2147        impl_trait_ref.args,
2148    );
2149
2150    let impl_ty_predicates = tcx.predicates_of(impl_ty.def_id);
2151    let trait_ty_predicates = tcx.predicates_of(trait_ty.def_id);
2152
2153    let impl_ty_own_bounds = impl_ty_predicates.instantiate_own_identity();
2154    // If there are no bounds, then there are no const conditions, so no need to check that here.
2155    if impl_ty_own_bounds.len() == 0 {
2156        // Nothing to check.
2157        return Ok(());
2158    }
2159
2160    // This `DefId` should be used for the `body_id` field on each
2161    // `ObligationCause` (and the `FnCtxt`). This is what
2162    // `regionck_item` expects.
2163    let impl_ty_def_id = impl_ty.def_id.expect_local();
2164    debug!(?trait_to_impl_args);
2165
2166    // The predicates declared by the impl definition, the trait and the
2167    // associated type in the trait are assumed.
2168    let impl_predicates = tcx.predicates_of(impl_ty_predicates.parent.unwrap());
2169    let mut hybrid_preds = impl_predicates.instantiate_identity(tcx).predicates;
2170    hybrid_preds.extend(
2171        trait_ty_predicates
2172            .instantiate_own(tcx, trait_to_impl_args)
2173            .map(|(predicate, _)| predicate),
2174    );
2175    debug!(?hybrid_preds);
2176
2177    let impl_ty_span = tcx.def_span(impl_ty_def_id);
2178    let normalize_cause = ObligationCause::misc(impl_ty_span, impl_ty_def_id);
2179
2180    let is_conditionally_const = tcx.is_conditionally_const(impl_ty.def_id);
2181    if is_conditionally_const {
2182        // Augment the hybrid param-env with the const conditions
2183        // of the impl header and the trait assoc type.
2184        hybrid_preds.extend(
2185            tcx.const_conditions(impl_ty_predicates.parent.unwrap())
2186                .instantiate_identity(tcx)
2187                .into_iter()
2188                .chain(
2189                    tcx.const_conditions(trait_ty.def_id).instantiate_own(tcx, trait_to_impl_args),
2190                )
2191                .map(|(trait_ref, _)| {
2192                    trait_ref.to_host_effect_clause(tcx, ty::BoundConstness::Maybe)
2193                }),
2194        );
2195    }
2196
2197    let param_env = ty::ParamEnv::new(tcx.mk_clauses(&hybrid_preds));
2198    let param_env = traits::normalize_param_env_or_error(tcx, param_env, normalize_cause);
2199    debug!(caller_bounds=?param_env.caller_bounds());
2200
2201    let infcx = tcx.infer_ctxt().build(TypingMode::non_body_analysis());
2202    let ocx = ObligationCtxt::new_with_diagnostics(&infcx);
2203
2204    for (predicate, span) in impl_ty_own_bounds {
2205        let cause = ObligationCause::misc(span, impl_ty_def_id);
2206        let predicate = ocx.normalize(&cause, param_env, predicate);
2207
2208        let cause = ObligationCause::new(
2209            span,
2210            impl_ty_def_id,
2211            ObligationCauseCode::CompareImplItem {
2212                impl_item_def_id: impl_ty.def_id.expect_local(),
2213                trait_item_def_id: trait_ty.def_id,
2214                kind: impl_ty.kind,
2215            },
2216        );
2217        ocx.register_obligation(traits::Obligation::new(tcx, cause, param_env, predicate));
2218    }
2219
2220    if is_conditionally_const {
2221        // Validate the const conditions of the impl associated type.
2222        let impl_ty_own_const_conditions =
2223            tcx.const_conditions(impl_ty.def_id).instantiate_own_identity();
2224        for (const_condition, span) in impl_ty_own_const_conditions {
2225            let normalize_cause = traits::ObligationCause::misc(span, impl_ty_def_id);
2226            let const_condition = ocx.normalize(&normalize_cause, param_env, const_condition);
2227
2228            let cause = ObligationCause::new(
2229                span,
2230                impl_ty_def_id,
2231                ObligationCauseCode::CompareImplItem {
2232                    impl_item_def_id: impl_ty_def_id,
2233                    trait_item_def_id: trait_ty.def_id,
2234                    kind: impl_ty.kind,
2235                },
2236            );
2237            ocx.register_obligation(traits::Obligation::new(
2238                tcx,
2239                cause,
2240                param_env,
2241                const_condition.to_host_effect_clause(tcx, ty::BoundConstness::Maybe),
2242            ));
2243        }
2244    }
2245
2246    // Check that all obligations are satisfied by the implementation's
2247    // version.
2248    let errors = ocx.select_all_or_error();
2249    if !errors.is_empty() {
2250        let reported = infcx.err_ctxt().report_fulfillment_errors(errors);
2251        return Err(reported);
2252    }
2253
2254    // Finally, resolve all regions. This catches wily misuses of
2255    // lifetime parameters.
2256    ocx.resolve_regions_and_report_errors(impl_ty_def_id, param_env, [])
2257}
2258
2259/// Validate that `ProjectionCandidate`s created for this associated type will
2260/// be valid.
2261///
2262/// Usually given
2263///
2264/// trait X { type Y: Copy } impl X for T { type Y = S; }
2265///
2266/// We are able to normalize `<T as X>::Y` to `S`, and so when we check the
2267/// impl is well-formed we have to prove `S: Copy`.
2268///
2269/// For default associated types the normalization is not possible (the value
2270/// from the impl could be overridden). We also can't normalize generic
2271/// associated types (yet) because they contain bound parameters.
2272#[instrument(level = "debug", skip(tcx))]
2273pub(super) fn check_type_bounds<'tcx>(
2274    tcx: TyCtxt<'tcx>,
2275    trait_ty: ty::AssocItem,
2276    impl_ty: ty::AssocItem,
2277    impl_trait_ref: ty::TraitRef<'tcx>,
2278) -> Result<(), ErrorGuaranteed> {
2279    // Avoid bogus "type annotations needed `Foo: Bar`" errors on `impl Bar for Foo` in case
2280    // other `Foo` impls are incoherent.
2281    tcx.ensure_ok().coherent_trait(impl_trait_ref.def_id)?;
2282
2283    let param_env = tcx.param_env(impl_ty.def_id);
2284    debug!(?param_env);
2285
2286    let container_id = impl_ty.container_id(tcx);
2287    let impl_ty_def_id = impl_ty.def_id.expect_local();
2288    let impl_ty_args = GenericArgs::identity_for_item(tcx, impl_ty.def_id);
2289    let rebased_args = impl_ty_args.rebase_onto(tcx, container_id, impl_trait_ref.args);
2290
2291    let infcx = tcx.infer_ctxt().build(TypingMode::non_body_analysis());
2292    let ocx = ObligationCtxt::new_with_diagnostics(&infcx);
2293
2294    // A synthetic impl Trait for RPITIT desugaring or assoc type for effects desugaring has no HIR,
2295    // which we currently use to get the span for an impl's associated type. Instead, for these,
2296    // use the def_span for the synthesized  associated type.
2297    let impl_ty_span = if impl_ty.is_impl_trait_in_trait() {
2298        tcx.def_span(impl_ty_def_id)
2299    } else {
2300        match tcx.hir_node_by_def_id(impl_ty_def_id) {
2301            hir::Node::TraitItem(hir::TraitItem {
2302                kind: hir::TraitItemKind::Type(_, Some(ty)),
2303                ..
2304            }) => ty.span,
2305            hir::Node::ImplItem(hir::ImplItem { kind: hir::ImplItemKind::Type(ty), .. }) => ty.span,
2306            item => span_bug!(
2307                tcx.def_span(impl_ty_def_id),
2308                "cannot call `check_type_bounds` on item: {item:?}",
2309            ),
2310        }
2311    };
2312    let assumed_wf_types = ocx.assumed_wf_types_and_report_errors(param_env, impl_ty_def_id)?;
2313
2314    let normalize_cause = ObligationCause::new(
2315        impl_ty_span,
2316        impl_ty_def_id,
2317        ObligationCauseCode::CheckAssociatedTypeBounds {
2318            impl_item_def_id: impl_ty.def_id.expect_local(),
2319            trait_item_def_id: trait_ty.def_id,
2320        },
2321    );
2322    let mk_cause = |span: Span| {
2323        let code = ObligationCauseCode::WhereClause(trait_ty.def_id, span);
2324        ObligationCause::new(impl_ty_span, impl_ty_def_id, code)
2325    };
2326
2327    let mut obligations: Vec<_> = util::elaborate(
2328        tcx,
2329        tcx.explicit_item_bounds(trait_ty.def_id).iter_instantiated_copied(tcx, rebased_args).map(
2330            |(concrete_ty_bound, span)| {
2331                debug!(?concrete_ty_bound);
2332                traits::Obligation::new(tcx, mk_cause(span), param_env, concrete_ty_bound)
2333            },
2334        ),
2335    )
2336    .collect();
2337
2338    // Only in a const implementation do we need to check that the `[const]` item bounds hold.
2339    if tcx.is_conditionally_const(impl_ty_def_id) {
2340        obligations.extend(util::elaborate(
2341            tcx,
2342            tcx.explicit_implied_const_bounds(trait_ty.def_id)
2343                .iter_instantiated_copied(tcx, rebased_args)
2344                .map(|(c, span)| {
2345                    traits::Obligation::new(
2346                        tcx,
2347                        mk_cause(span),
2348                        param_env,
2349                        c.to_host_effect_clause(tcx, ty::BoundConstness::Maybe),
2350                    )
2351                }),
2352        ));
2353    }
2354    debug!(item_bounds=?obligations);
2355
2356    // Normalize predicates with the assumption that the GAT may always normalize
2357    // to its definition type. This should be the param-env we use to *prove* the
2358    // predicate too, but we don't do that because of performance issues.
2359    // See <https://github.com/rust-lang/rust/pull/117542#issue-1976337685>.
2360    let normalize_param_env = param_env_with_gat_bounds(tcx, impl_ty, impl_trait_ref);
2361    for obligation in &mut obligations {
2362        match ocx.deeply_normalize(&normalize_cause, normalize_param_env, obligation.predicate) {
2363            Ok(pred) => obligation.predicate = pred,
2364            Err(e) => {
2365                return Err(infcx.err_ctxt().report_fulfillment_errors(e));
2366            }
2367        }
2368    }
2369
2370    // Check that all obligations are satisfied by the implementation's
2371    // version.
2372    ocx.register_obligations(obligations);
2373    let errors = ocx.select_all_or_error();
2374    if !errors.is_empty() {
2375        let reported = infcx.err_ctxt().report_fulfillment_errors(errors);
2376        return Err(reported);
2377    }
2378
2379    // Finally, resolve all regions. This catches wily misuses of
2380    // lifetime parameters.
2381    ocx.resolve_regions_and_report_errors(impl_ty_def_id, param_env, assumed_wf_types)
2382}
2383
2384/// Install projection predicates that allow GATs to project to their own
2385/// definition types. This is not allowed in general in cases of default
2386/// associated types in trait definitions, or when specialization is involved,
2387/// but is needed when checking these definition types actually satisfy the
2388/// trait bounds of the GAT.
2389///
2390/// # How it works
2391///
2392/// ```ignore (example)
2393/// impl<A, B> Foo<u32> for (A, B) {
2394///     type Bar<C> = Wrapper<A, B, C>
2395/// }
2396/// ```
2397///
2398/// - `impl_trait_ref` would be `<(A, B) as Foo<u32>>`
2399/// - `normalize_impl_ty_args` would be `[A, B, ^0.0]` (`^0.0` here is the bound var with db 0 and index 0)
2400/// - `normalize_impl_ty` would be `Wrapper<A, B, ^0.0>`
2401/// - `rebased_args` would be `[(A, B), u32, ^0.0]`, combining the args from
2402///    the *trait* with the generic associated type parameters (as bound vars).
2403///
2404/// A note regarding the use of bound vars here:
2405/// Imagine as an example
2406/// ```
2407/// trait Family {
2408///     type Member<C: Eq>;
2409/// }
2410///
2411/// impl Family for VecFamily {
2412///     type Member<C: Eq> = i32;
2413/// }
2414/// ```
2415/// Here, we would generate
2416/// ```ignore (pseudo-rust)
2417/// forall<C> { Normalize(<VecFamily as Family>::Member<C> => i32) }
2418/// ```
2419///
2420/// when we really would like to generate
2421/// ```ignore (pseudo-rust)
2422/// forall<C> { Normalize(<VecFamily as Family>::Member<C> => i32) :- Implemented(C: Eq) }
2423/// ```
2424///
2425/// But, this is probably fine, because although the first clause can be used with types `C` that
2426/// do not implement `Eq`, for it to cause some kind of problem, there would have to be a
2427/// `VecFamily::Member<X>` for some type `X` where `!(X: Eq)`, that appears in the value of type
2428/// `Member<C: Eq> = ....` That type would fail a well-formedness check that we ought to be doing
2429/// elsewhere, which would check that any `<T as Family>::Member<X>` meets the bounds declared in
2430/// the trait (notably, that `X: Eq` and `T: Family`).
2431fn param_env_with_gat_bounds<'tcx>(
2432    tcx: TyCtxt<'tcx>,
2433    impl_ty: ty::AssocItem,
2434    impl_trait_ref: ty::TraitRef<'tcx>,
2435) -> ty::ParamEnv<'tcx> {
2436    let param_env = tcx.param_env(impl_ty.def_id);
2437    let container_id = impl_ty.container_id(tcx);
2438    let mut predicates = param_env.caller_bounds().to_vec();
2439
2440    // for RPITITs, we should install predicates that allow us to project all
2441    // of the RPITITs associated with the same body. This is because checking
2442    // the item bounds of RPITITs often involves nested RPITITs having to prove
2443    // bounds about themselves.
2444    let impl_tys_to_install = match impl_ty.kind {
2445        ty::AssocKind::Type {
2446            data:
2447                ty::AssocTypeData::Rpitit(
2448                    ty::ImplTraitInTraitData::Impl { fn_def_id }
2449                    | ty::ImplTraitInTraitData::Trait { fn_def_id, .. },
2450                ),
2451        } => tcx
2452            .associated_types_for_impl_traits_in_associated_fn(fn_def_id)
2453            .iter()
2454            .map(|def_id| tcx.associated_item(*def_id))
2455            .collect(),
2456        _ => vec![impl_ty],
2457    };
2458
2459    for impl_ty in impl_tys_to_install {
2460        let trait_ty = match impl_ty.container {
2461            ty::AssocItemContainer::Trait => impl_ty,
2462            ty::AssocItemContainer::Impl => tcx.associated_item(impl_ty.trait_item_def_id.unwrap()),
2463        };
2464
2465        let mut bound_vars: smallvec::SmallVec<[ty::BoundVariableKind; 8]> =
2466            smallvec::SmallVec::with_capacity(tcx.generics_of(impl_ty.def_id).own_params.len());
2467        // Extend the impl's identity args with late-bound GAT vars
2468        let normalize_impl_ty_args = ty::GenericArgs::identity_for_item(tcx, container_id)
2469            .extend_to(tcx, impl_ty.def_id, |param, _| match param.kind {
2470                GenericParamDefKind::Type { .. } => {
2471                    let kind = ty::BoundTyKind::Param(param.def_id, param.name);
2472                    let bound_var = ty::BoundVariableKind::Ty(kind);
2473                    bound_vars.push(bound_var);
2474                    Ty::new_bound(
2475                        tcx,
2476                        ty::INNERMOST,
2477                        ty::BoundTy { var: ty::BoundVar::from_usize(bound_vars.len() - 1), kind },
2478                    )
2479                    .into()
2480                }
2481                GenericParamDefKind::Lifetime => {
2482                    let kind = ty::BoundRegionKind::Named(param.def_id, param.name);
2483                    let bound_var = ty::BoundVariableKind::Region(kind);
2484                    bound_vars.push(bound_var);
2485                    ty::Region::new_bound(
2486                        tcx,
2487                        ty::INNERMOST,
2488                        ty::BoundRegion {
2489                            var: ty::BoundVar::from_usize(bound_vars.len() - 1),
2490                            kind,
2491                        },
2492                    )
2493                    .into()
2494                }
2495                GenericParamDefKind::Const { .. } => {
2496                    let bound_var = ty::BoundVariableKind::Const;
2497                    bound_vars.push(bound_var);
2498                    ty::Const::new_bound(
2499                        tcx,
2500                        ty::INNERMOST,
2501                        ty::BoundVar::from_usize(bound_vars.len() - 1),
2502                    )
2503                    .into()
2504                }
2505            });
2506        // When checking something like
2507        //
2508        // trait X { type Y: PartialEq<<Self as X>::Y> }
2509        // impl X for T { default type Y = S; }
2510        //
2511        // We will have to prove the bound S: PartialEq<<T as X>::Y>. In this case
2512        // we want <T as X>::Y to normalize to S. This is valid because we are
2513        // checking the default value specifically here. Add this equality to the
2514        // ParamEnv for normalization specifically.
2515        let normalize_impl_ty =
2516            tcx.type_of(impl_ty.def_id).instantiate(tcx, normalize_impl_ty_args);
2517        let rebased_args =
2518            normalize_impl_ty_args.rebase_onto(tcx, container_id, impl_trait_ref.args);
2519        let bound_vars = tcx.mk_bound_variable_kinds(&bound_vars);
2520
2521        match normalize_impl_ty.kind() {
2522            ty::Alias(ty::Projection, proj)
2523                if proj.def_id == trait_ty.def_id && proj.args == rebased_args =>
2524            {
2525                // Don't include this predicate if the projected type is
2526                // exactly the same as the projection. This can occur in
2527                // (somewhat dubious) code like this:
2528                //
2529                // impl<T> X for T where T: X { type Y = <T as X>::Y; }
2530            }
2531            _ => predicates.push(
2532                ty::Binder::bind_with_vars(
2533                    ty::ProjectionPredicate {
2534                        projection_term: ty::AliasTerm::new_from_args(
2535                            tcx,
2536                            trait_ty.def_id,
2537                            rebased_args,
2538                        ),
2539                        term: normalize_impl_ty.into(),
2540                    },
2541                    bound_vars,
2542                )
2543                .upcast(tcx),
2544            ),
2545        };
2546    }
2547
2548    ty::ParamEnv::new(tcx.mk_clauses(&predicates))
2549}
2550
2551/// Manually check here that `async fn foo()` wasn't matched against `fn foo()`,
2552/// and extract a better error if so.
2553fn try_report_async_mismatch<'tcx>(
2554    tcx: TyCtxt<'tcx>,
2555    infcx: &InferCtxt<'tcx>,
2556    errors: &[FulfillmentError<'tcx>],
2557    trait_m: ty::AssocItem,
2558    impl_m: ty::AssocItem,
2559    impl_sig: ty::FnSig<'tcx>,
2560) -> Result<(), ErrorGuaranteed> {
2561    if !tcx.asyncness(trait_m.def_id).is_async() {
2562        return Ok(());
2563    }
2564
2565    let ty::Alias(ty::Projection, ty::AliasTy { def_id: async_future_def_id, .. }) =
2566        *tcx.fn_sig(trait_m.def_id).skip_binder().skip_binder().output().kind()
2567    else {
2568        bug!("expected `async fn` to return an RPITIT");
2569    };
2570
2571    for error in errors {
2572        if let ObligationCauseCode::WhereClause(def_id, _) = *error.root_obligation.cause.code()
2573            && def_id == async_future_def_id
2574            && let Some(proj) = error.root_obligation.predicate.as_projection_clause()
2575            && let Some(proj) = proj.no_bound_vars()
2576            && infcx.can_eq(
2577                error.root_obligation.param_env,
2578                proj.term.expect_type(),
2579                impl_sig.output(),
2580            )
2581        {
2582            // FIXME: We should suggest making the fn `async`, but extracting
2583            // the right span is a bit difficult.
2584            return Err(tcx.sess.dcx().emit_err(MethodShouldReturnFuture {
2585                span: tcx.def_span(impl_m.def_id),
2586                method_name: tcx.item_ident(impl_m.def_id),
2587                trait_item_span: tcx.hir_span_if_local(trait_m.def_id),
2588            }));
2589        }
2590    }
2591
2592    Ok(())
2593}