compiler/rustc_hir_analysis/src/check/compare_method.rs

   1 use super::potentially_plural_count;
   2 use crate::errors::LifetimesOrBoundsMismatchOnTrait;
   3 use hir::def_id::{DefId, LocalDefId};
   4 use rustc_data_structures::fx::{FxHashMap, FxIndexSet};
   5 use rustc_errors::{pluralize, struct_span_err, Applicability, DiagnosticId, ErrorGuaranteed};
   6 use rustc_hir as hir;
   7 use rustc_hir::def::{DefKind, Res};
   8 use rustc_hir::intravisit;
   9 use rustc_hir::{GenericParamKind, ImplItemKind, TraitItemKind};
  10 use rustc_infer::infer::outlives::env::OutlivesEnvironment;
  11 use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
  12 use rustc_infer::infer::{self, InferCtxt, TyCtxtInferExt};
  13 use rustc_infer::traits::util;
  14 use rustc_middle::ty::error::{ExpectedFound, TypeError};
  15 use rustc_middle::ty::util::ExplicitSelf;
  16 use rustc_middle::ty::{
  17     self, AssocItem, DefIdTree, TraitRef, Ty, TypeFoldable, TypeFolder, TypeSuperFoldable,
  18     TypeVisitable,
  19 };
  20 use rustc_middle::ty::{FnSig, InternalSubsts};
  21 use rustc_middle::ty::{GenericParamDefKind, ToPredicate, TyCtxt};
  22 use rustc_span::Span;
  23 use rustc_trait_selection::traits::error_reporting::TypeErrCtxtExt;
  24 use rustc_trait_selection::traits::outlives_bounds::InferCtxtExt as _;
  25 use rustc_trait_selection::traits::{
  26     self, ObligationCause, ObligationCauseCode, ObligationCtxt, Reveal,
  27 };
  28 use std::iter;
  29
  30 /// Checks that a method from an impl conforms to the signature of
  31 /// the same method as declared in the trait.
  32 ///
  33 /// # Parameters
  34 ///
  35 /// - `impl_m`: type of the method we are checking
  36 /// - `impl_m_span`: span to use for reporting errors
  37 /// - `trait_m`: the method in the trait
  38 /// - `impl_trait_ref`: the TraitRef corresponding to the trait implementation
  39 pub(crate) fn compare_impl_method<'tcx>(
  40     tcx: TyCtxt<'tcx>,
  41     impl_m: &ty::AssocItem,
  42     trait_m: &ty::AssocItem,
  43     impl_trait_ref: ty::TraitRef<'tcx>,
  44     trait_item_span: Option<Span>,
  45 ) {
  46     debug!("compare_impl_method(impl_trait_ref={:?})", impl_trait_ref);
  47
  48     let impl_m_span = tcx.def_span(impl_m.def_id);
  49
  50     if let Err(_) = compare_self_type(tcx, impl_m, impl_m_span, trait_m, impl_trait_ref) {
  51         return;
  52     }
  53
  54     if let Err(_) = compare_number_of_generics(tcx, impl_m, impl_m_span, trait_m, trait_item_span) {
  55         return;
  56     }
  57
  58     if let Err(_) = compare_generic_param_kinds(tcx, impl_m, trait_m) {
  59         return;
  60     }
  61
  62     if let Err(_) =
  63         compare_number_of_method_arguments(tcx, impl_m, impl_m_span, trait_m, trait_item_span)
  64     {
  65         return;
  66     }
  67
  68     if let Err(_) = compare_synthetic_generics(tcx, impl_m, trait_m) {
  69         return;
  70     }
  71
  72     if let Err(_) = compare_predicate_entailment(tcx, impl_m, impl_m_span, trait_m, impl_trait_ref)
  73     {
  74         return;
  75     }
  76 }
  77
  78 /// This function is best explained by example. Consider a trait:
  79 ///
  80 ///     trait Trait<'t, T> {
  81 ///         // `trait_m`
  82 ///         fn method<'a, M>(t: &'t T, m: &'a M) -> Self;
  83 ///     }
  84 ///
  85 /// And an impl:
  86 ///
  87 ///     impl<'i, 'j, U> Trait<'j, &'i U> for Foo {
  88 ///          // `impl_m`
  89 ///          fn method<'b, N>(t: &'j &'i U, m: &'b N) -> Foo;
  90 ///     }
  91 ///
  92 /// We wish to decide if those two method types are compatible.
  93 /// For this we have to show that, assuming the bounds of the impl hold, the
  94 /// bounds of `trait_m` imply the bounds of `impl_m`.
  95 ///
  96 /// We start out with `trait_to_impl_substs`, that maps the trait
  97 /// type parameters to impl type parameters. This is taken from the
  98 /// impl trait reference:
  99 ///
 100 ///     trait_to_impl_substs = {'t => 'j, T => &'i U, Self => Foo}
 101 ///
 102 /// We create a mapping `dummy_substs` that maps from the impl type
 103 /// parameters to fresh types and regions. For type parameters,
 104 /// this is the identity transform, but we could as well use any
 105 /// placeholder types. For regions, we convert from bound to free
 106 /// regions (Note: but only early-bound regions, i.e., those
 107 /// declared on the impl or used in type parameter bounds).
 108 ///
 109 ///     impl_to_placeholder_substs = {'i => 'i0, U => U0, N => N0 }
 110 ///
 111 /// Now we can apply `placeholder_substs` to the type of the impl method
 112 /// to yield a new function type in terms of our fresh, placeholder
 113 /// types:
 114 ///
 115 ///     <'b> fn(t: &'i0 U0, m: &'b) -> Foo
 116 ///
 117 /// We now want to extract and substitute the type of the *trait*
 118 /// method and compare it. To do so, we must create a compound
 119 /// substitution by combining `trait_to_impl_substs` and
 120 /// `impl_to_placeholder_substs`, and also adding a mapping for the method
 121 /// type parameters. We extend the mapping to also include
 122 /// the method parameters.
 123 ///
 124 ///     trait_to_placeholder_substs = { T => &'i0 U0, Self => Foo, M => N0 }
 125 ///
 126 /// Applying this to the trait method type yields:
 127 ///
 128 ///     <'a> fn(t: &'i0 U0, m: &'a) -> Foo
 129 ///
 130 /// This type is also the same but the name of the bound region (`'a`
 131 /// vs `'b`).  However, the normal subtyping rules on fn types handle
 132 /// this kind of equivalency just fine.
 133 ///
 134 /// We now use these substitutions to ensure that all declared bounds are
 135 /// satisfied by the implementation's method.
 136 ///
 137 /// We do this by creating a parameter environment which contains a
 138 /// substitution corresponding to `impl_to_placeholder_substs`. We then build
 139 /// `trait_to_placeholder_substs` and use it to convert the predicates contained
 140 /// in the `trait_m` generics to the placeholder form.
 141 ///
 142 /// Finally we register each of these predicates as an obligation and check that
 143 /// they hold.
 144 #[instrument(level = "debug", skip(tcx, impl_m_span, impl_trait_ref))]
 145 fn compare_predicate_entailment<'tcx>(
 146     tcx: TyCtxt<'tcx>,
 147     impl_m: &AssocItem,
 148     impl_m_span: Span,
 149     trait_m: &AssocItem,
 150     impl_trait_ref: ty::TraitRef<'tcx>,
 151 ) -> Result<(), ErrorGuaranteed> {
 152     let trait_to_impl_substs = impl_trait_ref.substs;
 153
 154     // This node-id should be used for the `body_id` field on each
 155     // `ObligationCause` (and the `FnCtxt`).
 156     //
 157     // FIXME(@lcnr): remove that after removing `cause.body_id` from
 158     // obligations.
 159     let impl_m_hir_id = tcx.hir().local_def_id_to_hir_id(impl_m.def_id.expect_local());
 160     // We sometimes modify the span further down.
 161     let mut cause = ObligationCause::new(
 162         impl_m_span,
 163         impl_m_hir_id,
 164         ObligationCauseCode::CompareImplItemObligation {
 165             impl_item_def_id: impl_m.def_id.expect_local(),
 166             trait_item_def_id: trait_m.def_id,
 167             kind: impl_m.kind,
 168         },
 169     );
 170
 171     // Create mapping from impl to placeholder.
 172     let impl_to_placeholder_substs = InternalSubsts::identity_for_item(tcx, impl_m.def_id);
 173
 174     // Create mapping from trait to placeholder.
 175     let trait_to_placeholder_substs =
 176         impl_to_placeholder_substs.rebase_onto(tcx, impl_m.container_id(tcx), trait_to_impl_substs);
 177     debug!("compare_impl_method: trait_to_placeholder_substs={:?}", trait_to_placeholder_substs);
 178
 179     let impl_m_generics = tcx.generics_of(impl_m.def_id);
 180     let trait_m_generics = tcx.generics_of(trait_m.def_id);
 181     let impl_m_predicates = tcx.predicates_of(impl_m.def_id);
 182     let trait_m_predicates = tcx.predicates_of(trait_m.def_id);
 183
 184     // Check region bounds.
 185     check_region_bounds_on_impl_item(tcx, impl_m, trait_m, &trait_m_generics, &impl_m_generics)?;
 186
 187     // Create obligations for each predicate declared by the impl
 188     // definition in the context of the trait's parameter
 189     // environment. We can't just use `impl_env.caller_bounds`,
 190     // however, because we want to replace all late-bound regions with
 191     // region variables.
 192     let impl_predicates = tcx.predicates_of(impl_m_predicates.parent.unwrap());
 193     let mut hybrid_preds = impl_predicates.instantiate_identity(tcx);
 194
 195     debug!("compare_impl_method: impl_bounds={:?}", hybrid_preds);
 196
 197     // This is the only tricky bit of the new way we check implementation methods
 198     // We need to build a set of predicates where only the method-level bounds
 199     // are from the trait and we assume all other bounds from the implementation
 200     // to be previously satisfied.
 201     //
 202     // We then register the obligations from the impl_m and check to see
 203     // if all constraints hold.
 204     hybrid_preds
 205         .predicates
 206         .extend(trait_m_predicates.instantiate_own(tcx, trait_to_placeholder_substs).predicates);
 207
 208     // Construct trait parameter environment and then shift it into the placeholder viewpoint.
 209     // The key step here is to update the caller_bounds's predicates to be
 210     // the new hybrid bounds we computed.
 211     let normalize_cause = traits::ObligationCause::misc(impl_m_span, impl_m_hir_id);
 212     let param_env = ty::ParamEnv::new(
 213         tcx.intern_predicates(&hybrid_preds.predicates),
 214         Reveal::UserFacing,
 215         hir::Constness::NotConst,
 216     );
 217     let param_env = traits::normalize_param_env_or_error(tcx, param_env, normalize_cause);
 218
 219     let infcx = &tcx.infer_ctxt().build();
 220     let ocx = ObligationCtxt::new(infcx);
 221
 222     debug!("compare_impl_method: caller_bounds={:?}", param_env.caller_bounds());
 223
 224     let mut selcx = traits::SelectionContext::new(&infcx);
 225     let impl_m_own_bounds = impl_m_predicates.instantiate_own(tcx, impl_to_placeholder_substs);
 226     for (predicate, span) in iter::zip(impl_m_own_bounds.predicates, impl_m_own_bounds.spans) {
 227         let normalize_cause = traits::ObligationCause::misc(span, impl_m_hir_id);
 228         let traits::Normalized { value: predicate, obligations } =
 229             traits::normalize(&mut selcx, param_env, normalize_cause, predicate);
 230
 231         ocx.register_obligations(obligations);
 232         let cause = ObligationCause::new(
 233             span,
 234             impl_m_hir_id,
 235             ObligationCauseCode::CompareImplItemObligation {
 236                 impl_item_def_id: impl_m.def_id.expect_local(),
 237                 trait_item_def_id: trait_m.def_id,
 238                 kind: impl_m.kind,
 239             },
 240         );
 241         ocx.register_obligation(traits::Obligation::new(tcx, cause, param_env, predicate));
 242     }
 243
 244     // We now need to check that the signature of the impl method is
 245     // compatible with that of the trait method. We do this by
 246     // checking that `impl_fty <: trait_fty`.
 247     //
 248     // FIXME. Unfortunately, this doesn't quite work right now because
 249     // associated type normalization is not integrated into subtype
 250     // checks. For the comparison to be valid, we need to
 251     // normalize the associated types in the impl/trait methods
 252     // first. However, because function types bind regions, just
 253     // calling `normalize_associated_types_in` would have no effect on
 254     // any associated types appearing in the fn arguments or return
 255     // type.
 256
 257     // Compute placeholder form of impl and trait method tys.
 258     let tcx = infcx.tcx;
 259
 260     let mut wf_tys = FxIndexSet::default();
 261
 262     let impl_sig = infcx.replace_bound_vars_with_fresh_vars(
 263         impl_m_span,
 264         infer::HigherRankedType,
 265         tcx.fn_sig(impl_m.def_id),
 266     );
 267
 268     let norm_cause = ObligationCause::misc(impl_m_span, impl_m_hir_id);
 269     let impl_sig = ocx.normalize(norm_cause.clone(), param_env, impl_sig);
 270     let impl_fty = tcx.mk_fn_ptr(ty::Binder::dummy(impl_sig));
 271     debug!("compare_impl_method: impl_fty={:?}", impl_fty);
 272
 273     let trait_sig = tcx.bound_fn_sig(trait_m.def_id).subst(tcx, trait_to_placeholder_substs);
 274     let trait_sig = tcx.liberate_late_bound_regions(impl_m.def_id, trait_sig);
 275
 276     // Next, add all inputs and output as well-formed tys. Importantly,
 277     // we have to do this before normalization, since the normalized ty may
 278     // not contain the input parameters. See issue #87748.
 279     wf_tys.extend(trait_sig.inputs_and_output.iter());
 280     let trait_sig = ocx.normalize(norm_cause, param_env, trait_sig);
 281     // We also have to add the normalized trait signature
 282     // as we don't normalize during implied bounds computation.
 283     wf_tys.extend(trait_sig.inputs_and_output.iter());
 284     let trait_fty = tcx.mk_fn_ptr(ty::Binder::dummy(trait_sig));
 285
 286     debug!("compare_impl_method: trait_fty={:?}", trait_fty);
 287
 288     // FIXME: We'd want to keep more accurate spans than "the method signature" when
 289     // processing the comparison between the trait and impl fn, but we sadly lose them
 290     // and point at the whole signature when a trait bound or specific input or output
 291     // type would be more appropriate. In other places we have a `Vec<Span>`
 292     // corresponding to their `Vec<Predicate>`, but we don't have that here.
 293     // Fixing this would improve the output of test `issue-83765.rs`.
 294     let mut result = ocx.sup(&cause, param_env, trait_fty, impl_fty);
 295
 296     // HACK(RPITIT): #101614. When we are trying to infer the hidden types for
 297     // RPITITs, we need to equate the output tys instead of just subtyping. If
 298     // we just use `sup` above, we'll end up `&'static str <: _#1t`, which causes
 299     // us to infer `_#1t = #'_#2r str`, where `'_#2r` is unconstrained, which gets
 300     // fixed up to `ReEmpty`, and which is certainly not what we want.
 301     if trait_fty.has_infer_types() {
 302         result =
 303             result.and_then(|()| ocx.eq(&cause, param_env, trait_sig.output(), impl_sig.output()));
 304     }
 305
 306     if let Err(terr) = result {
 307         debug!(?terr, "sub_types failed: impl ty {:?}, trait ty {:?}", impl_fty, trait_fty);
 308
 309         let emitted = report_trait_method_mismatch(
 310             tcx,
 311             &mut cause,
 312             &infcx,
 313             terr,
 314             (trait_m, trait_fty),
 315             (impl_m, impl_fty),
 316             &trait_sig,
 317             &impl_trait_ref,
 318         );
 319         return Err(emitted);
 320     }
 321
 322     // Check that all obligations are satisfied by the implementation's
 323     // version.
 324     let errors = ocx.select_all_or_error();
 325     if !errors.is_empty() {
 326         let reported = infcx.err_ctxt().report_fulfillment_errors(&errors, None);
 327         return Err(reported);
 328     }
 329
 330     // Finally, resolve all regions. This catches wily misuses of
 331     // lifetime parameters.
 332     let outlives_environment = OutlivesEnvironment::with_bounds(
 333         param_env,
 334         Some(infcx),
 335         infcx.implied_bounds_tys(param_env, impl_m_hir_id, wf_tys),
 336     );
 337     infcx.check_region_obligations_and_report_errors(
 338         impl_m.def_id.expect_local(),
 339         &outlives_environment,
 340     );
 341
 342     Ok(())
 343 }
 344
 345 #[instrument(skip(tcx), level = "debug", ret)]
 346 pub fn collect_trait_impl_trait_tys<'tcx>(
 347     tcx: TyCtxt<'tcx>,
 348     def_id: DefId,
 349 ) -> Result<&'tcx FxHashMap<DefId, Ty<'tcx>>, ErrorGuaranteed> {
 350     let impl_m = tcx.opt_associated_item(def_id).unwrap();
 351     let trait_m = tcx.opt_associated_item(impl_m.trait_item_def_id.unwrap()).unwrap();
 352     let impl_trait_ref = tcx.impl_trait_ref(impl_m.impl_container(tcx).unwrap()).unwrap();
 353     let param_env = tcx.param_env(def_id);
 354
 355     let trait_to_impl_substs = impl_trait_ref.substs;
 356
 357     let impl_m_hir_id = tcx.hir().local_def_id_to_hir_id(impl_m.def_id.expect_local());
 358     let return_span = tcx.hir().fn_decl_by_hir_id(impl_m_hir_id).unwrap().output.span();
 359     let mut cause = ObligationCause::new(
 360         return_span,
 361         impl_m_hir_id,
 362         ObligationCauseCode::CompareImplItemObligation {
 363             impl_item_def_id: impl_m.def_id.expect_local(),
 364             trait_item_def_id: trait_m.def_id,
 365             kind: impl_m.kind,
 366         },
 367     );
 368
 369     // Create mapping from impl to placeholder.
 370     let impl_to_placeholder_substs = InternalSubsts::identity_for_item(tcx, impl_m.def_id);
 371
 372     // Create mapping from trait to placeholder.
 373     let trait_to_placeholder_substs =
 374         impl_to_placeholder_substs.rebase_onto(tcx, impl_m.container_id(tcx), trait_to_impl_substs);
 375
 376     let infcx = &tcx.infer_ctxt().build();
 377     let ocx = ObligationCtxt::new(infcx);
 378
 379     let norm_cause = ObligationCause::misc(return_span, impl_m_hir_id);
 380     let impl_sig = ocx.normalize(
 381         norm_cause.clone(),
 382         param_env,
 383         infcx.replace_bound_vars_with_fresh_vars(
 384             return_span,
 385             infer::HigherRankedType,
 386             tcx.fn_sig(impl_m.def_id),
 387         ),
 388     );
 389     let impl_return_ty = impl_sig.output();
 390
 391     let mut collector = ImplTraitInTraitCollector::new(&ocx, return_span, param_env, impl_m_hir_id);
 392     let unnormalized_trait_sig = tcx
 393         .liberate_late_bound_regions(
 394             impl_m.def_id,
 395             tcx.bound_fn_sig(trait_m.def_id).subst(tcx, trait_to_placeholder_substs),
 396         )
 397         .fold_with(&mut collector);
 398     let trait_sig = ocx.normalize(norm_cause.clone(), param_env, unnormalized_trait_sig);
 399     let trait_return_ty = trait_sig.output();
 400
 401     let wf_tys = FxIndexSet::from_iter(
 402         unnormalized_trait_sig.inputs_and_output.iter().chain(trait_sig.inputs_and_output.iter()),
 403     );
 404
 405     match infcx.at(&cause, param_env).eq(trait_return_ty, impl_return_ty) {
 406         Ok(infer::InferOk { value: (), obligations }) => {
 407             ocx.register_obligations(obligations);
 408         }
 409         Err(terr) => {
 410             let mut diag = struct_span_err!(
 411                 tcx.sess,
 412                 cause.span(),
 413                 E0053,
 414                 "method `{}` has an incompatible return type for trait",
 415                 trait_m.name
 416             );
 417             let hir = tcx.hir();
 418             infcx.err_ctxt().note_type_err(
 419                 &mut diag,
 420                 &cause,
 421                 hir.get_if_local(impl_m.def_id)
 422                     .and_then(|node| node.fn_decl())
 423                     .map(|decl| (decl.output.span(), "return type in trait".to_owned())),
 424                 Some(infer::ValuePairs::Terms(ExpectedFound {
 425                     expected: trait_return_ty.into(),
 426                     found: impl_return_ty.into(),
 427                 })),
 428                 terr,
 429                 false,
 430                 false,
 431             );
 432             return Err(diag.emit());
 433         }
 434     }
 435
 436     debug!(?trait_sig, ?impl_sig, "equating function signatures");
 437
 438     let trait_fty = tcx.mk_fn_ptr(ty::Binder::dummy(trait_sig));
 439     let impl_fty = tcx.mk_fn_ptr(ty::Binder::dummy(impl_sig));
 440
 441     // Unify the whole function signature. We need to do this to fully infer
 442     // the lifetimes of the return type, but do this after unifying just the
 443     // return types, since we want to avoid duplicating errors from
 444     // `compare_predicate_entailment`.
 445     match infcx.at(&cause, param_env).eq(trait_fty, impl_fty) {
 446         Ok(infer::InferOk { value: (), obligations }) => {
 447             ocx.register_obligations(obligations);
 448         }
 449         Err(terr) => {
 450             // This function gets called during `compare_predicate_entailment` when normalizing a
 451             // signature that contains RPITIT. When the method signatures don't match, we have to
 452             // emit an error now because `compare_predicate_entailment` will not report the error
 453             // when normalization fails.
 454             let emitted = report_trait_method_mismatch(
 455                 tcx,
 456                 &mut cause,
 457                 infcx,
 458                 terr,
 459                 (trait_m, trait_fty),
 460                 (impl_m, impl_fty),
 461                 &trait_sig,
 462                 &impl_trait_ref,
 463             );
 464             return Err(emitted);
 465         }
 466     }
 467
 468     // Check that all obligations are satisfied by the implementation's
 469     // RPITs.
 470     let errors = ocx.select_all_or_error();
 471     if !errors.is_empty() {
 472         let reported = infcx.err_ctxt().report_fulfillment_errors(&errors, None);
 473         return Err(reported);
 474     }
 475
 476     // Finally, resolve all regions. This catches wily misuses of
 477     // lifetime parameters.
 478     let outlives_environment = OutlivesEnvironment::with_bounds(
 479         param_env,
 480         Some(infcx),
 481         infcx.implied_bounds_tys(param_env, impl_m_hir_id, wf_tys),
 482     );
 483     infcx.check_region_obligations_and_report_errors(
 484         impl_m.def_id.expect_local(),
 485         &outlives_environment,
 486     );
 487
 488     let mut collected_tys = FxHashMap::default();
 489     for (def_id, (ty, substs)) in collector.types {
 490         match infcx.fully_resolve(ty) {
 491             Ok(ty) => {
 492                 // `ty` contains free regions that we created earlier while liberating the
 493                 // trait fn signature.  However, projection normalization expects `ty` to
 494                 // contains `def_id`'s early-bound regions.
 495                 let id_substs = InternalSubsts::identity_for_item(tcx, def_id);
 496                 debug!(?id_substs, ?substs);
 497                 let map: FxHashMap<ty::GenericArg<'tcx>, ty::GenericArg<'tcx>> =
 498                     std::iter::zip(substs, id_substs).collect();
 499                 debug!(?map);
 500
 501                 // NOTE(compiler-errors): RPITITs, like all other RPITs, have early-bound
 502                 // region substs that are synthesized during AST lowering. These are substs
 503                 // that are appended to the parent substs (trait and trait method). However,
 504                 // we're trying to infer the unsubstituted type value of the RPITIT inside
 505                 // the *impl*, so we can later use the impl's method substs to normalize
 506                 // an RPITIT to a concrete type (`confirm_impl_trait_in_trait_candidate`).
 507                 //
 508                 // Due to the design of RPITITs, during AST lowering, we have no idea that
 509                 // an impl method corresponds to a trait method with RPITITs in it. Therefore,
 510                 // we don't have a list of early-bound region substs for the RPITIT in the impl.
 511                 // Since early region parameters are index-based, we can't just rebase these
 512                 // (trait method) early-bound region substs onto the impl, and there's no
 513                 // guarantee that the indices from the trait substs and impl substs line up.
 514                 // So to fix this, we subtract the number of trait substs and add the number of
 515                 // impl substs to *renumber* these early-bound regions to their corresponding
 516                 // indices in the impl's substitutions list.
 517                 //
 518                 // Also, we only need to account for a difference in trait and impl substs,
 519                 // since we previously enforce that the trait method and impl method have the
 520                 // same generics.
 521                 let num_trait_substs = trait_to_impl_substs.len();
 522                 let num_impl_substs = tcx.generics_of(impl_m.container_id(tcx)).params.len();
 523                 let ty = tcx.fold_regions(ty, |region, _| {
 524                     match region.kind() {
 525                         // Remap all free regions, which correspond to late-bound regions in the function.
 526                         ty::ReFree(_) => {}
 527                         // Remap early-bound regions as long as they don't come from the `impl` itself.
 528                         ty::ReEarlyBound(ebr) if tcx.parent(ebr.def_id) != impl_m.container_id(tcx) => {}
 529                         _ => return region,
 530                     }
 531                     let Some(ty::ReEarlyBound(e)) = map.get(&region.into()).map(|r| r.expect_region().kind())
 532                     else {
 533                         tcx
 534                             .sess
 535                             .delay_span_bug(
 536                                 return_span,
 537                                 "expected ReFree to map to ReEarlyBound"
 538                             );
 539                         return tcx.lifetimes.re_static;
 540                     };
 541                     tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
 542                         def_id: e.def_id,
 543                         name: e.name,
 544                         index: (e.index as usize - num_trait_substs + num_impl_substs) as u32,
 545                     }))
 546                 });
 547                 debug!(%ty);
 548                 collected_tys.insert(def_id, ty);
 549             }
 550             Err(err) => {
 551                 let reported = tcx.sess.delay_span_bug(
 552                     return_span,
 553                     format!("could not fully resolve: {ty} => {err:?}"),
 554                 );
 555                 collected_tys.insert(def_id, tcx.ty_error_with_guaranteed(reported));
 556             }
 557         }
 558     }
 559
 560     Ok(&*tcx.arena.alloc(collected_tys))
 561 }
 562
 563 struct ImplTraitInTraitCollector<'a, 'tcx> {
 564     ocx: &'a ObligationCtxt<'a, 'tcx>,
 565     types: FxHashMap<DefId, (Ty<'tcx>, ty::SubstsRef<'tcx>)>,
 566     span: Span,
 567     param_env: ty::ParamEnv<'tcx>,
 568     body_id: hir::HirId,
 569 }
 570
 571 impl<'a, 'tcx> ImplTraitInTraitCollector<'a, 'tcx> {
 572     fn new(
 573         ocx: &'a ObligationCtxt<'a, 'tcx>,
 574         span: Span,
 575         param_env: ty::ParamEnv<'tcx>,
 576         body_id: hir::HirId,
 577     ) -> Self {
 578         ImplTraitInTraitCollector { ocx, types: FxHashMap::default(), span, param_env, body_id }
 579     }
 580 }
 581
 582 impl<'tcx> TypeFolder<'tcx> for ImplTraitInTraitCollector<'_, 'tcx> {
 583     fn tcx<'a>(&'a self) -> TyCtxt<'tcx> {
 584         self.ocx.infcx.tcx
 585     }
 586
 587     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 588         if let ty::Projection(proj) = ty.kind()
 589             && self.tcx().def_kind(proj.item_def_id) == DefKind::ImplTraitPlaceholder
 590         {
 591             if let Some((ty, _)) = self.types.get(&proj.item_def_id) {
 592                 return *ty;
 593             }
 594             //FIXME(RPITIT): Deny nested RPITIT in substs too
 595             if proj.substs.has_escaping_bound_vars() {
 596                 bug!("FIXME(RPITIT): error here");
 597             }
 598             // Replace with infer var
 599             let infer_ty = self.ocx.infcx.next_ty_var(TypeVariableOrigin {
 600                 span: self.span,
 601                 kind: TypeVariableOriginKind::MiscVariable,
 602             });
 603             self.types.insert(proj.item_def_id, (infer_ty, proj.substs));
 604             // Recurse into bounds
 605             for (pred, pred_span) in self.tcx().bound_explicit_item_bounds(proj.item_def_id).subst_iter_copied(self.tcx(), proj.substs) {
 606                 let pred = pred.fold_with(self);
 607                 let pred = self.ocx.normalize(
 608                     ObligationCause::misc(self.span, self.body_id),
 609                     self.param_env,
 610                     pred,
 611                 );
 612
 613                 self.ocx.register_obligation(traits::Obligation::new(
 614                     self.tcx(),
 615                     ObligationCause::new(
 616                         self.span,
 617                         self.body_id,
 618                         ObligationCauseCode::BindingObligation(proj.item_def_id, pred_span),
 619                     ),
 620                     self.param_env,
 621                     pred,
 622                 ));
 623             }
 624             infer_ty
 625         } else {
 626             ty.super_fold_with(self)
 627         }
 628     }
 629 }
 630
 631 fn report_trait_method_mismatch<'tcx>(
 632     tcx: TyCtxt<'tcx>,
 633     cause: &mut ObligationCause<'tcx>,
 634     infcx: &InferCtxt<'tcx>,
 635     terr: TypeError<'tcx>,
 636     (trait_m, trait_fty): (&AssocItem, Ty<'tcx>),
 637     (impl_m, impl_fty): (&AssocItem, Ty<'tcx>),
 638     trait_sig: &FnSig<'tcx>,
 639     impl_trait_ref: &TraitRef<'tcx>,
 640 ) -> ErrorGuaranteed {
 641     let (impl_err_span, trait_err_span) =
 642         extract_spans_for_error_reporting(&infcx, terr, &cause, impl_m, trait_m);
 643
 644     cause.span = impl_err_span;
 645
 646     let mut diag = struct_span_err!(
 647         tcx.sess,
 648         cause.span(),
 649         E0053,
 650         "method `{}` has an incompatible type for trait",
 651         trait_m.name
 652     );
 653     match &terr {
 654         TypeError::ArgumentMutability(0) | TypeError::ArgumentSorts(_, 0)
 655             if trait_m.fn_has_self_parameter =>
 656         {
 657             let ty = trait_sig.inputs()[0];
 658             let sugg = match ExplicitSelf::determine(ty, |_| ty == impl_trait_ref.self_ty()) {
 659                 ExplicitSelf::ByValue => "self".to_owned(),
 660                 ExplicitSelf::ByReference(_, hir::Mutability::Not) => "&self".to_owned(),
 661                 ExplicitSelf::ByReference(_, hir::Mutability::Mut) => "&mut self".to_owned(),
 662                 _ => format!("self: {ty}"),
 663             };
 664
 665             // When the `impl` receiver is an arbitrary self type, like `self: Box<Self>`, the
 666             // span points only at the type `Box<Self`>, but we want to cover the whole
 667             // argument pattern and type.
 668             let span = match tcx.hir().expect_impl_item(impl_m.def_id.expect_local()).kind {
 669                 ImplItemKind::Fn(ref sig, body) => tcx
 670                     .hir()
 671                     .body_param_names(body)
 672                     .zip(sig.decl.inputs.iter())
 673                     .map(|(param, ty)| param.span.to(ty.span))
 674                     .next()
 675                     .unwrap_or(impl_err_span),
 676                 _ => bug!("{:?} is not a method", impl_m),
 677             };
 678
 679             diag.span_suggestion(
 680                 span,
 681                 "change the self-receiver type to match the trait",
 682                 sugg,
 683                 Applicability::MachineApplicable,
 684             );
 685         }
 686         TypeError::ArgumentMutability(i) | TypeError::ArgumentSorts(_, i) => {
 687             if trait_sig.inputs().len() == *i {
 688                 // Suggestion to change output type. We do not suggest in `async` functions
 689                 // to avoid complex logic or incorrect output.
 690                 match tcx.hir().expect_impl_item(impl_m.def_id.expect_local()).kind {
 691                     ImplItemKind::Fn(ref sig, _)
 692                         if sig.header.asyncness == hir::IsAsync::NotAsync =>
 693                     {
 694                         let msg = "change the output type to match the trait";
 695                         let ap = Applicability::MachineApplicable;
 696                         match sig.decl.output {
 697                             hir::FnRetTy::DefaultReturn(sp) => {
 698                                 let sugg = format!("-> {} ", trait_sig.output());
 699                                 diag.span_suggestion_verbose(sp, msg, sugg, ap);
 700                             }
 701                             hir::FnRetTy::Return(hir_ty) => {
 702                                 let sugg = trait_sig.output();
 703                                 diag.span_suggestion(hir_ty.span, msg, sugg, ap);
 704                             }
 705                         };
 706                     }
 707                     _ => {}
 708                 };
 709             } else if let Some(trait_ty) = trait_sig.inputs().get(*i) {
 710                 diag.span_suggestion(
 711                     impl_err_span,
 712                     "change the parameter type to match the trait",
 713                     trait_ty,
 714                     Applicability::MachineApplicable,
 715                 );
 716             }
 717         }
 718         _ => {}
 719     }
 720
 721     infcx.err_ctxt().note_type_err(
 722         &mut diag,
 723         &cause,
 724         trait_err_span.map(|sp| (sp, "type in trait".to_owned())),
 725         Some(infer::ValuePairs::Terms(ExpectedFound {
 726             expected: trait_fty.into(),
 727             found: impl_fty.into(),
 728         })),
 729         terr,
 730         false,
 731         false,
 732     );
 733
 734     return diag.emit();
 735 }
 736
 737 fn check_region_bounds_on_impl_item<'tcx>(
 738     tcx: TyCtxt<'tcx>,
 739     impl_m: &ty::AssocItem,
 740     trait_m: &ty::AssocItem,
 741     trait_generics: &ty::Generics,
 742     impl_generics: &ty::Generics,
 743 ) -> Result<(), ErrorGuaranteed> {
 744     let trait_params = trait_generics.own_counts().lifetimes;
 745     let impl_params = impl_generics.own_counts().lifetimes;
 746
 747     debug!(
 748         "check_region_bounds_on_impl_item: \
 749             trait_generics={:?} \
 750             impl_generics={:?}",
 751         trait_generics, impl_generics
 752     );
 753
 754     // Must have same number of early-bound lifetime parameters.
 755     // Unfortunately, if the user screws up the bounds, then this
 756     // will change classification between early and late.  E.g.,
 757     // if in trait we have `<'a,'b:'a>`, and in impl we just have
 758     // `<'a,'b>`, then we have 2 early-bound lifetime parameters
 759     // in trait but 0 in the impl. But if we report "expected 2
 760     // but found 0" it's confusing, because it looks like there
 761     // are zero. Since I don't quite know how to phrase things at
 762     // the moment, give a kind of vague error message.
 763     if trait_params != impl_params {
 764         let span = tcx
 765             .hir()
 766             .get_generics(impl_m.def_id.expect_local())
 767             .expect("expected impl item to have generics or else we can't compare them")
 768             .span;
 769         let generics_span = if let Some(local_def_id) = trait_m.def_id.as_local() {
 770             Some(
 771                 tcx.hir()
 772                     .get_generics(local_def_id)
 773                     .expect("expected trait item to have generics or else we can't compare them")
 774                     .span,
 775             )
 776         } else {
 777             None
 778         };
 779
 780         let reported = tcx.sess.emit_err(LifetimesOrBoundsMismatchOnTrait {
 781             span,
 782             item_kind: assoc_item_kind_str(impl_m),
 783             ident: impl_m.ident(tcx),
 784             generics_span,
 785         });
 786         return Err(reported);
 787     }
 788
 789     Ok(())
 790 }
 791
 792 #[instrument(level = "debug", skip(infcx))]
 793 fn extract_spans_for_error_reporting<'tcx>(
 794     infcx: &infer::InferCtxt<'tcx>,
 795     terr: TypeError<'_>,
 796     cause: &ObligationCause<'tcx>,
 797     impl_m: &ty::AssocItem,
 798     trait_m: &ty::AssocItem,
 799 ) -> (Span, Option<Span>) {
 800     let tcx = infcx.tcx;
 801     let mut impl_args = match tcx.hir().expect_impl_item(impl_m.def_id.expect_local()).kind {
 802         ImplItemKind::Fn(ref sig, _) => {
 803             sig.decl.inputs.iter().map(|t| t.span).chain(iter::once(sig.decl.output.span()))
 804         }
 805         _ => bug!("{:?} is not a method", impl_m),
 806     };
 807     let trait_args =
 808         trait_m.def_id.as_local().map(|def_id| match tcx.hir().expect_trait_item(def_id).kind {
 809             TraitItemKind::Fn(ref sig, _) => {
 810                 sig.decl.inputs.iter().map(|t| t.span).chain(iter::once(sig.decl.output.span()))
 811             }
 812             _ => bug!("{:?} is not a TraitItemKind::Fn", trait_m),
 813         });
 814
 815     match terr {
 816         TypeError::ArgumentMutability(i) => {
 817             (impl_args.nth(i).unwrap(), trait_args.and_then(|mut args| args.nth(i)))
 818         }
 819         TypeError::ArgumentSorts(ExpectedFound { .. }, i) => {
 820             (impl_args.nth(i).unwrap(), trait_args.and_then(|mut args| args.nth(i)))
 821         }
 822         _ => (cause.span(), tcx.hir().span_if_local(trait_m.def_id)),
 823     }
 824 }
 825
 826 fn compare_self_type<'tcx>(
 827     tcx: TyCtxt<'tcx>,
 828     impl_m: &ty::AssocItem,
 829     impl_m_span: Span,
 830     trait_m: &ty::AssocItem,
 831     impl_trait_ref: ty::TraitRef<'tcx>,
 832 ) -> Result<(), ErrorGuaranteed> {
 833     // Try to give more informative error messages about self typing
 834     // mismatches.  Note that any mismatch will also be detected
 835     // below, where we construct a canonical function type that
 836     // includes the self parameter as a normal parameter.  It's just
 837     // that the error messages you get out of this code are a bit more
 838     // inscrutable, particularly for cases where one method has no
 839     // self.
 840
 841     let self_string = |method: &ty::AssocItem| {
 842         let untransformed_self_ty = match method.container {
 843             ty::ImplContainer => impl_trait_ref.self_ty(),
 844             ty::TraitContainer => tcx.types.self_param,
 845         };
 846         let self_arg_ty = tcx.fn_sig(method.def_id).input(0);
 847         let param_env = ty::ParamEnv::reveal_all();
 848
 849         let infcx = tcx.infer_ctxt().build();
 850         let self_arg_ty = tcx.liberate_late_bound_regions(method.def_id, self_arg_ty);
 851         let can_eq_self = |ty| infcx.can_eq(param_env, untransformed_self_ty, ty).is_ok();
 852         match ExplicitSelf::determine(self_arg_ty, can_eq_self) {
 853             ExplicitSelf::ByValue => "self".to_owned(),
 854             ExplicitSelf::ByReference(_, hir::Mutability::Not) => "&self".to_owned(),
 855             ExplicitSelf::ByReference(_, hir::Mutability::Mut) => "&mut self".to_owned(),
 856             _ => format!("self: {self_arg_ty}"),
 857         }
 858     };
 859
 860     match (trait_m.fn_has_self_parameter, impl_m.fn_has_self_parameter) {
 861         (false, false) | (true, true) => {}
 862
 863         (false, true) => {
 864             let self_descr = self_string(impl_m);
 865             let mut err = struct_span_err!(
 866                 tcx.sess,
 867                 impl_m_span,
 868                 E0185,
 869                 "method `{}` has a `{}` declaration in the impl, but not in the trait",
 870                 trait_m.name,
 871                 self_descr
 872             );
 873             err.span_label(impl_m_span, format!("`{self_descr}` used in impl"));
 874             if let Some(span) = tcx.hir().span_if_local(trait_m.def_id) {
 875                 err.span_label(span, format!("trait method declared without `{self_descr}`"));
 876             } else {
 877                 err.note_trait_signature(trait_m.name, trait_m.signature(tcx));
 878             }
 879             let reported = err.emit();
 880             return Err(reported);
 881         }
 882
 883         (true, false) => {
 884             let self_descr = self_string(trait_m);
 885             let mut err = struct_span_err!(
 886                 tcx.sess,
 887                 impl_m_span,
 888                 E0186,
 889                 "method `{}` has a `{}` declaration in the trait, but not in the impl",
 890                 trait_m.name,
 891                 self_descr
 892             );
 893             err.span_label(impl_m_span, format!("expected `{self_descr}` in impl"));
 894             if let Some(span) = tcx.hir().span_if_local(trait_m.def_id) {
 895                 err.span_label(span, format!("`{self_descr}` used in trait"));
 896             } else {
 897                 err.note_trait_signature(trait_m.name, trait_m.signature(tcx));
 898             }
 899             let reported = err.emit();
 900             return Err(reported);
 901         }
 902     }
 903
 904     Ok(())
 905 }
 906
 907 /// Checks that the number of generics on a given assoc item in a trait impl is the same
 908 /// as the number of generics on the respective assoc item in the trait definition.
 909 ///
 910 /// For example this code emits the errors in the following code:
 911 /// ```
 912 /// trait Trait {
 913 ///     fn foo();
 914 ///     type Assoc<T>;
 915 /// }
 916 ///
 917 /// impl Trait for () {
 918 ///     fn foo<T>() {}
 919 ///     //~^ error
 920 ///     type Assoc = u32;
 921 ///     //~^ error
 922 /// }
 923 /// ```
 924 ///
 925 /// Notably this does not error on `foo<T>` implemented as `foo<const N: u8>` or
 926 /// `foo<const N: u8>` implemented as `foo<const N: u32>`. This is handled in
 927 /// [`compare_generic_param_kinds`]. This function also does not handle lifetime parameters
 928 fn compare_number_of_generics<'tcx>(
 929     tcx: TyCtxt<'tcx>,
 930     impl_: &ty::AssocItem,
 931     _impl_span: Span,
 932     trait_: &ty::AssocItem,
 933     trait_span: Option<Span>,
 934 ) -> Result<(), ErrorGuaranteed> {
 935     let trait_own_counts = tcx.generics_of(trait_.def_id).own_counts();
 936     let impl_own_counts = tcx.generics_of(impl_.def_id).own_counts();
 937
 938     // This avoids us erroring on `foo<T>` implemented as `foo<const N: u8>` as this is implemented
 939     // in `compare_generic_param_kinds` which will give a nicer error message than something like:
 940     // "expected 1 type parameter, found 0 type parameters"
 941     if (trait_own_counts.types + trait_own_counts.consts)
 942         == (impl_own_counts.types + impl_own_counts.consts)
 943     {
 944         return Ok(());
 945     }
 946
 947     let matchings = [
 948         ("type", trait_own_counts.types, impl_own_counts.types),
 949         ("const", trait_own_counts.consts, impl_own_counts.consts),
 950     ];
 951
 952     let item_kind = assoc_item_kind_str(impl_);
 953
 954     let mut err_occurred = None;
 955     for (kind, trait_count, impl_count) in matchings {
 956         if impl_count != trait_count {
 957             let arg_spans = |kind: ty::AssocKind, generics: &hir::Generics<'_>| {
 958                 let mut spans = generics
 959                     .params
 960                     .iter()
 961                     .filter(|p| match p.kind {
 962                         hir::GenericParamKind::Lifetime {
 963                             kind: hir::LifetimeParamKind::Elided,
 964                         } => {
 965                             // A fn can have an arbitrary number of extra elided lifetimes for the
 966                             // same signature.
 967                             !matches!(kind, ty::AssocKind::Fn)
 968                         }
 969                         _ => true,
 970                     })
 971                     .map(|p| p.span)
 972                     .collect::<Vec<Span>>();
 973                 if spans.is_empty() {
 974                     spans = vec![generics.span]
 975                 }
 976                 spans
 977             };
 978             let (trait_spans, impl_trait_spans) = if let Some(def_id) = trait_.def_id.as_local() {
 979                 let trait_item = tcx.hir().expect_trait_item(def_id);
 980                 let arg_spans: Vec<Span> = arg_spans(trait_.kind, trait_item.generics);
 981                 let impl_trait_spans: Vec<Span> = trait_item
 982                     .generics
 983                     .params
 984                     .iter()
 985                     .filter_map(|p| match p.kind {
 986                         GenericParamKind::Type { synthetic: true, .. } => Some(p.span),
 987                         _ => None,
 988                     })
 989                     .collect();
 990                 (Some(arg_spans), impl_trait_spans)
 991             } else {
 992                 (trait_span.map(|s| vec![s]), vec![])
 993             };
 994
 995             let impl_item = tcx.hir().expect_impl_item(impl_.def_id.expect_local());
 996             let impl_item_impl_trait_spans: Vec<Span> = impl_item
 997                 .generics
 998                 .params
 999                 .iter()
1000                 .filter_map(|p| match p.kind {
1001                     GenericParamKind::Type { synthetic: true, .. } => Some(p.span),
1002                     _ => None,
1003                 })
1004                 .collect();
1005             let spans = arg_spans(impl_.kind, impl_item.generics);
1006             let span = spans.first().copied();
1007
1008             let mut err = tcx.sess.struct_span_err_with_code(
1009                 spans,
1010                 &format!(
1011                     "{} `{}` has {} {kind} parameter{} but its trait \
1012                      declaration has {} {kind} parameter{}",
1013                     item_kind,
1014                     trait_.name,
1015                     impl_count,
1016                     pluralize!(impl_count),
1017                     trait_count,
1018                     pluralize!(trait_count),
1019                     kind = kind,
1020                 ),
1021                 DiagnosticId::Error("E0049".into()),
1022             );
1023
1024             let mut suffix = None;
1025
1026             if let Some(spans) = trait_spans {
1027                 let mut spans = spans.iter();
1028                 if let Some(span) = spans.next() {
1029                     err.span_label(
1030                         *span,
1031                         format!(
1032                             "expected {} {} parameter{}",
1033                             trait_count,
1034                             kind,
1035                             pluralize!(trait_count),
1036                         ),
1037                     );
1038                 }
1039                 for span in spans {
1040                     err.span_label(*span, "");
1041                 }
1042             } else {
1043                 suffix = Some(format!(", expected {trait_count}"));
1044             }
1045
1046             if let Some(span) = span {
1047                 err.span_label(
1048                     span,
1049                     format!(
1050                         "found {} {} parameter{}{}",
1051                         impl_count,
1052                         kind,
1053                         pluralize!(impl_count),
1054                         suffix.unwrap_or_else(String::new),
1055                     ),
1056                 );
1057             }
1058
1059             for span in impl_trait_spans.iter().chain(impl_item_impl_trait_spans.iter()) {
1060                 err.span_label(*span, "`impl Trait` introduces an implicit type parameter");
1061             }
1062
1063             let reported = err.emit();
1064             err_occurred = Some(reported);
1065         }
1066     }
1067
1068     if let Some(reported) = err_occurred { Err(reported) } else { Ok(()) }
1069 }
1070
1071 fn compare_number_of_method_arguments<'tcx>(
1072     tcx: TyCtxt<'tcx>,
1073     impl_m: &ty::AssocItem,
1074     impl_m_span: Span,
1075     trait_m: &ty::AssocItem,
1076     trait_item_span: Option<Span>,
1077 ) -> Result<(), ErrorGuaranteed> {
1078     let impl_m_fty = tcx.fn_sig(impl_m.def_id);
1079     let trait_m_fty = tcx.fn_sig(trait_m.def_id);
1080     let trait_number_args = trait_m_fty.inputs().skip_binder().len();
1081     let impl_number_args = impl_m_fty.inputs().skip_binder().len();
1082     if trait_number_args != impl_number_args {
1083         let trait_span = if let Some(def_id) = trait_m.def_id.as_local() {
1084             match tcx.hir().expect_trait_item(def_id).kind {
1085                 TraitItemKind::Fn(ref trait_m_sig, _) => {
1086                     let pos = if trait_number_args > 0 { trait_number_args - 1 } else { 0 };
1087                     if let Some(arg) = trait_m_sig.decl.inputs.get(pos) {
1088                         Some(if pos == 0 {
1089                             arg.span
1090                         } else {
1091                             arg.span.with_lo(trait_m_sig.decl.inputs[0].span.lo())
1092                         })
1093                     } else {
1094                         trait_item_span
1095                     }
1096                 }
1097                 _ => bug!("{:?} is not a method", impl_m),
1098             }
1099         } else {
1100             trait_item_span
1101         };
1102         let impl_span = match tcx.hir().expect_impl_item(impl_m.def_id.expect_local()).kind {
1103             ImplItemKind::Fn(ref impl_m_sig, _) => {
1104                 let pos = if impl_number_args > 0 { impl_number_args - 1 } else { 0 };
1105                 if let Some(arg) = impl_m_sig.decl.inputs.get(pos) {
1106                     if pos == 0 {
1107                         arg.span
1108                     } else {
1109                         arg.span.with_lo(impl_m_sig.decl.inputs[0].span.lo())
1110                     }
1111                 } else {
1112                     impl_m_span
1113                 }
1114             }
1115             _ => bug!("{:?} is not a method", impl_m),
1116         };
1117         let mut err = struct_span_err!(
1118             tcx.sess,
1119             impl_span,
1120             E0050,
1121             "method `{}` has {} but the declaration in trait `{}` has {}",
1122             trait_m.name,
1123             potentially_plural_count(impl_number_args, "parameter"),
1124             tcx.def_path_str(trait_m.def_id),
1125             trait_number_args
1126         );
1127         if let Some(trait_span) = trait_span {
1128             err.span_label(
1129                 trait_span,
1130                 format!(
1131                     "trait requires {}",
1132                     potentially_plural_count(trait_number_args, "parameter")
1133                 ),
1134             );
1135         } else {
1136             err.note_trait_signature(trait_m.name, trait_m.signature(tcx));
1137         }
1138         err.span_label(
1139             impl_span,
1140             format!(
1141                 "expected {}, found {}",
1142                 potentially_plural_count(trait_number_args, "parameter"),
1143                 impl_number_args
1144             ),
1145         );
1146         let reported = err.emit();
1147         return Err(reported);
1148     }
1149
1150     Ok(())
1151 }
1152
1153 fn compare_synthetic_generics<'tcx>(
1154     tcx: TyCtxt<'tcx>,
1155     impl_m: &ty::AssocItem,
1156     trait_m: &ty::AssocItem,
1157 ) -> Result<(), ErrorGuaranteed> {
1158     // FIXME(chrisvittal) Clean up this function, list of FIXME items:
1159     //     1. Better messages for the span labels
1160     //     2. Explanation as to what is going on
1161     // If we get here, we already have the same number of generics, so the zip will
1162     // be okay.
1163     let mut error_found = None;
1164     let impl_m_generics = tcx.generics_of(impl_m.def_id);
1165     let trait_m_generics = tcx.generics_of(trait_m.def_id);
1166     let impl_m_type_params = impl_m_generics.params.iter().filter_map(|param| match param.kind {
1167         GenericParamDefKind::Type { synthetic, .. } => Some((param.def_id, synthetic)),
1168         GenericParamDefKind::Lifetime | GenericParamDefKind::Const { .. } => None,
1169     });
1170     let trait_m_type_params = trait_m_generics.params.iter().filter_map(|param| match param.kind {
1171         GenericParamDefKind::Type { synthetic, .. } => Some((param.def_id, synthetic)),
1172         GenericParamDefKind::Lifetime | GenericParamDefKind::Const { .. } => None,
1173     });
1174     for ((impl_def_id, impl_synthetic), (trait_def_id, trait_synthetic)) in
1175         iter::zip(impl_m_type_params, trait_m_type_params)
1176     {
1177         if impl_synthetic != trait_synthetic {
1178             let impl_def_id = impl_def_id.expect_local();
1179             let impl_span = tcx.def_span(impl_def_id);
1180             let trait_span = tcx.def_span(trait_def_id);
1181             let mut err = struct_span_err!(
1182                 tcx.sess,
1183                 impl_span,
1184                 E0643,
1185                 "method `{}` has incompatible signature for trait",
1186                 trait_m.name
1187             );
1188             err.span_label(trait_span, "declaration in trait here");
1189             match (impl_synthetic, trait_synthetic) {
1190                 // The case where the impl method uses `impl Trait` but the trait method uses
1191                 // explicit generics
1192                 (true, false) => {
1193                     err.span_label(impl_span, "expected generic parameter, found `impl Trait`");
1194                     (|| {
1195                         // try taking the name from the trait impl
1196                         // FIXME: this is obviously suboptimal since the name can already be used
1197                         // as another generic argument
1198                         let new_name = tcx.opt_item_name(trait_def_id)?;
1199                         let trait_m = trait_m.def_id.as_local()?;
1200                         let trait_m = tcx.hir().expect_trait_item(trait_m);
1201
1202                         let impl_m = impl_m.def_id.as_local()?;
1203                         let impl_m = tcx.hir().expect_impl_item(impl_m);
1204
1205                         // in case there are no generics, take the spot between the function name
1206                         // and the opening paren of the argument list
1207                         let new_generics_span = tcx.def_ident_span(impl_def_id)?.shrink_to_hi();
1208                         // in case there are generics, just replace them
1209                         let generics_span =
1210                             impl_m.generics.span.substitute_dummy(new_generics_span);
1211                         // replace with the generics from the trait
1212                         let new_generics =
1213                             tcx.sess.source_map().span_to_snippet(trait_m.generics.span).ok()?;
1214
1215                         err.multipart_suggestion(
1216                             "try changing the `impl Trait` argument to a generic parameter",
1217                             vec![
1218                                 // replace `impl Trait` with `T`
1219                                 (impl_span, new_name.to_string()),
1220                                 // replace impl method generics with trait method generics
1221                                 // This isn't quite right, as users might have changed the names
1222                                 // of the generics, but it works for the common case
1223                                 (generics_span, new_generics),
1224                             ],
1225                             Applicability::MaybeIncorrect,
1226                         );
1227                         Some(())
1228                     })();
1229                 }
1230                 // The case where the trait method uses `impl Trait`, but the impl method uses
1231                 // explicit generics.
1232                 (false, true) => {
1233                     err.span_label(impl_span, "expected `impl Trait`, found generic parameter");
1234                     (|| {
1235                         let impl_m = impl_m.def_id.as_local()?;
1236                         let impl_m = tcx.hir().expect_impl_item(impl_m);
1237                         let input_tys = match impl_m.kind {
1238                             hir::ImplItemKind::Fn(ref sig, _) => sig.decl.inputs,
1239                             _ => unreachable!(),
1240                         };
1241                         struct Visitor(Option<Span>, hir::def_id::LocalDefId);
1242                         impl<'v> intravisit::Visitor<'v> for Visitor {
1243                             fn visit_ty(&mut self, ty: &'v hir::Ty<'v>) {
1244                                 intravisit::walk_ty(self, ty);
1245                                 if let hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) =
1246                                     ty.kind
1247                                     && let Res::Def(DefKind::TyParam, def_id) = path.res
1248                                     && def_id == self.1.to_def_id()
1249                                 {
1250                                     self.0 = Some(ty.span);
1251                                 }
1252                             }
1253                         }
1254                         let mut visitor = Visitor(None, impl_def_id);
1255                         for ty in input_tys {
1256                             intravisit::Visitor::visit_ty(&mut visitor, ty);
1257                         }
1258                         let span = visitor.0?;
1259
1260                         let bounds = impl_m.generics.bounds_for_param(impl_def_id).next()?.bounds;
1261                         let bounds = bounds.first()?.span().to(bounds.last()?.span());
1262                         let bounds = tcx.sess.source_map().span_to_snippet(bounds).ok()?;
1263
1264                         err.multipart_suggestion(
1265                             "try removing the generic parameter and using `impl Trait` instead",
1266                             vec![
1267                                 // delete generic parameters
1268                                 (impl_m.generics.span, String::new()),
1269                                 // replace param usage with `impl Trait`
1270                                 (span, format!("impl {bounds}")),
1271                             ],
1272                             Applicability::MaybeIncorrect,
1273                         );
1274                         Some(())
1275                     })();
1276                 }
1277                 _ => unreachable!(),
1278             }
1279             let reported = err.emit();
1280             error_found = Some(reported);
1281         }
1282     }
1283     if let Some(reported) = error_found { Err(reported) } else { Ok(()) }
1284 }
1285
1286 /// Checks that all parameters in the generics of a given assoc item in a trait impl have
1287 /// the same kind as the respective generic parameter in the trait def.
1288 ///
1289 /// For example all 4 errors in the following code are emitted here:
1290 /// ```
1291 /// trait Foo {
1292 ///     fn foo<const N: u8>();
1293 ///     type bar<const N: u8>;
1294 ///     fn baz<const N: u32>();
1295 ///     type blah<T>;
1296 /// }
1297 ///
1298 /// impl Foo for () {
1299 ///     fn foo<const N: u64>() {}
1300 ///     //~^ error
1301 ///     type bar<const N: u64> {}
1302 ///     //~^ error
1303 ///     fn baz<T>() {}
1304 ///     //~^ error
1305 ///     type blah<const N: i64> = u32;
1306 ///     //~^ error
1307 /// }
1308 /// ```
1309 ///
1310 /// This function does not handle lifetime parameters
1311 fn compare_generic_param_kinds<'tcx>(
1312     tcx: TyCtxt<'tcx>,
1313     impl_item: &ty::AssocItem,
1314     trait_item: &ty::AssocItem,
1315 ) -> Result<(), ErrorGuaranteed> {
1316     assert_eq!(impl_item.kind, trait_item.kind);
1317
1318     let ty_const_params_of = |def_id| {
1319         tcx.generics_of(def_id).params.iter().filter(|param| {
1320             matches!(
1321                 param.kind,
1322                 GenericParamDefKind::Const { .. } | GenericParamDefKind::Type { .. }
1323             )
1324         })
1325     };
1326
1327     for (param_impl, param_trait) in
1328         iter::zip(ty_const_params_of(impl_item.def_id), ty_const_params_of(trait_item.def_id))
1329     {
1330         use GenericParamDefKind::*;
1331         if match (&param_impl.kind, &param_trait.kind) {
1332             (Const { .. }, Const { .. })
1333                 if tcx.type_of(param_impl.def_id) != tcx.type_of(param_trait.def_id) =>
1334             {
1335                 true
1336             }
1337             (Const { .. }, Type { .. }) | (Type { .. }, Const { .. }) => true,
1338             // this is exhaustive so that anyone adding new generic param kinds knows
1339             // to make sure this error is reported for them.
1340             (Const { .. }, Const { .. }) | (Type { .. }, Type { .. }) => false,
1341             (Lifetime { .. }, _) | (_, Lifetime { .. }) => unreachable!(),
1342         } {
1343             let param_impl_span = tcx.def_span(param_impl.def_id);
1344             let param_trait_span = tcx.def_span(param_trait.def_id);
1345
1346             let mut err = struct_span_err!(
1347                 tcx.sess,
1348                 param_impl_span,
1349                 E0053,
1350                 "{} `{}` has an incompatible generic parameter for trait `{}`",
1351                 assoc_item_kind_str(&impl_item),
1352                 trait_item.name,
1353                 &tcx.def_path_str(tcx.parent(trait_item.def_id))
1354             );
1355
1356             let make_param_message = |prefix: &str, param: &ty::GenericParamDef| match param.kind {
1357                 Const { .. } => {
1358                     format!("{} const parameter of type `{}`", prefix, tcx.type_of(param.def_id))
1359                 }
1360                 Type { .. } => format!("{} type parameter", prefix),
1361                 Lifetime { .. } => unreachable!(),
1362             };
1363
1364             let trait_header_span = tcx.def_ident_span(tcx.parent(trait_item.def_id)).unwrap();
1365             err.span_label(trait_header_span, "");
1366             err.span_label(param_trait_span, make_param_message("expected", param_trait));
1367
1368             let impl_header_span = tcx.def_span(tcx.parent(impl_item.def_id));
1369             err.span_label(impl_header_span, "");
1370             err.span_label(param_impl_span, make_param_message("found", param_impl));
1371
1372             let reported = err.emit();
1373             return Err(reported);
1374         }
1375     }
1376
1377     Ok(())
1378 }
1379
1380 /// Use `tcx.compare_assoc_const_impl_item_with_trait_item` instead
1381 pub(crate) fn raw_compare_const_impl<'tcx>(
1382     tcx: TyCtxt<'tcx>,
1383     (impl_const_item_def, trait_const_item_def): (LocalDefId, DefId),
1384 ) -> Result<(), ErrorGuaranteed> {
1385     let impl_const_item = tcx.associated_item(impl_const_item_def);
1386     let trait_const_item = tcx.associated_item(trait_const_item_def);
1387     let impl_trait_ref = tcx.impl_trait_ref(impl_const_item.container_id(tcx)).unwrap();
1388     debug!("compare_const_impl(impl_trait_ref={:?})", impl_trait_ref);
1389
1390     let impl_c_span = tcx.def_span(impl_const_item_def.to_def_id());
1391
1392     let infcx = tcx.infer_ctxt().build();
1393     let param_env = tcx.param_env(impl_const_item_def.to_def_id());
1394     let ocx = ObligationCtxt::new(&infcx);
1395
1396     // The below is for the most part highly similar to the procedure
1397     // for methods above. It is simpler in many respects, especially
1398     // because we shouldn't really have to deal with lifetimes or
1399     // predicates. In fact some of this should probably be put into
1400     // shared functions because of DRY violations...
1401     let trait_to_impl_substs = impl_trait_ref.substs;
1402
1403     // Create a parameter environment that represents the implementation's
1404     // method.
1405     let impl_c_hir_id = tcx.hir().local_def_id_to_hir_id(impl_const_item_def);
1406
1407     // Compute placeholder form of impl and trait const tys.
1408     let impl_ty = tcx.type_of(impl_const_item_def.to_def_id());
1409     let trait_ty = tcx.bound_type_of(trait_const_item_def).subst(tcx, trait_to_impl_substs);
1410     let mut cause = ObligationCause::new(
1411         impl_c_span,
1412         impl_c_hir_id,
1413         ObligationCauseCode::CompareImplItemObligation {
1414             impl_item_def_id: impl_const_item_def,
1415             trait_item_def_id: trait_const_item_def,
1416             kind: impl_const_item.kind,
1417         },
1418     );
1419
1420     // There is no "body" here, so just pass dummy id.
1421     let impl_ty = ocx.normalize(cause.clone(), param_env, impl_ty);
1422
1423     debug!("compare_const_impl: impl_ty={:?}", impl_ty);
1424
1425     let trait_ty = ocx.normalize(cause.clone(), param_env, trait_ty);
1426
1427     debug!("compare_const_impl: trait_ty={:?}", trait_ty);
1428
1429     let err = ocx.sup(&cause, param_env, trait_ty, impl_ty);
1430
1431     if let Err(terr) = err {
1432         debug!(
1433             "checking associated const for compatibility: impl ty {:?}, trait ty {:?}",
1434             impl_ty, trait_ty
1435         );
1436
1437         // Locate the Span containing just the type of the offending impl
1438         match tcx.hir().expect_impl_item(impl_const_item_def).kind {
1439             ImplItemKind::Const(ref ty, _) => cause.span = ty.span,
1440             _ => bug!("{:?} is not a impl const", impl_const_item),
1441         }
1442
1443         let mut diag = struct_span_err!(
1444             tcx.sess,
1445             cause.span,
1446             E0326,
1447             "implemented const `{}` has an incompatible type for trait",
1448             trait_const_item.name
1449         );
1450
1451         let trait_c_span = trait_const_item_def.as_local().map(|trait_c_def_id| {
1452             // Add a label to the Span containing just the type of the const
1453             match tcx.hir().expect_trait_item(trait_c_def_id).kind {
1454                 TraitItemKind::Const(ref ty, _) => ty.span,
1455                 _ => bug!("{:?} is not a trait const", trait_const_item),
1456             }
1457         });
1458
1459         infcx.err_ctxt().note_type_err(
1460             &mut diag,
1461             &cause,
1462             trait_c_span.map(|span| (span, "type in trait".to_owned())),
1463             Some(infer::ValuePairs::Terms(ExpectedFound {
1464                 expected: trait_ty.into(),
1465                 found: impl_ty.into(),
1466             })),
1467             terr,
1468             false,
1469             false,
1470         );
1471         return Err(diag.emit());
1472     };
1473
1474     // Check that all obligations are satisfied by the implementation's
1475     // version.
1476     let errors = ocx.select_all_or_error();
1477     if !errors.is_empty() {
1478         return Err(infcx.err_ctxt().report_fulfillment_errors(&errors, None));
1479     }
1480
1481     // FIXME return `ErrorReported` if region obligations error?
1482     let outlives_environment = OutlivesEnvironment::new(param_env);
1483     infcx.check_region_obligations_and_report_errors(impl_const_item_def, &outlives_environment);
1484     Ok(())
1485 }
1486
1487 pub(crate) fn compare_ty_impl<'tcx>(
1488     tcx: TyCtxt<'tcx>,
1489     impl_ty: &ty::AssocItem,
1490     impl_ty_span: Span,
1491     trait_ty: &ty::AssocItem,
1492     impl_trait_ref: ty::TraitRef<'tcx>,
1493     trait_item_span: Option<Span>,
1494 ) {
1495     debug!("compare_impl_type(impl_trait_ref={:?})", impl_trait_ref);
1496
1497     let _: Result<(), ErrorGuaranteed> = (|| {
1498         compare_number_of_generics(tcx, impl_ty, impl_ty_span, trait_ty, trait_item_span)?;
1499
1500         compare_generic_param_kinds(tcx, impl_ty, trait_ty)?;
1501
1502         let sp = tcx.def_span(impl_ty.def_id);
1503         compare_type_predicate_entailment(tcx, impl_ty, sp, trait_ty, impl_trait_ref)?;
1504
1505         check_type_bounds(tcx, trait_ty, impl_ty, impl_ty_span, impl_trait_ref)
1506     })();
1507 }
1508
1509 /// The equivalent of [compare_predicate_entailment], but for associated types
1510 /// instead of associated functions.
1511 fn compare_type_predicate_entailment<'tcx>(
1512     tcx: TyCtxt<'tcx>,
1513     impl_ty: &ty::AssocItem,
1514     impl_ty_span: Span,
1515     trait_ty: &ty::AssocItem,
1516     impl_trait_ref: ty::TraitRef<'tcx>,
1517 ) -> Result<(), ErrorGuaranteed> {
1518     let impl_substs = InternalSubsts::identity_for_item(tcx, impl_ty.def_id);
1519     let trait_to_impl_substs =
1520         impl_substs.rebase_onto(tcx, impl_ty.container_id(tcx), impl_trait_ref.substs);
1521
1522     let impl_ty_generics = tcx.generics_of(impl_ty.def_id);
1523     let trait_ty_generics = tcx.generics_of(trait_ty.def_id);
1524     let impl_ty_predicates = tcx.predicates_of(impl_ty.def_id);
1525     let trait_ty_predicates = tcx.predicates_of(trait_ty.def_id);
1526
1527     check_region_bounds_on_impl_item(
1528         tcx,
1529         impl_ty,
1530         trait_ty,
1531         &trait_ty_generics,
1532         &impl_ty_generics,
1533     )?;
1534
1535     let impl_ty_own_bounds = impl_ty_predicates.instantiate_own(tcx, impl_substs);
1536
1537     if impl_ty_own_bounds.is_empty() {
1538         // Nothing to check.
1539         return Ok(());
1540     }
1541
1542     // This `HirId` should be used for the `body_id` field on each
1543     // `ObligationCause` (and the `FnCtxt`). This is what
1544     // `regionck_item` expects.
1545     let impl_ty_hir_id = tcx.hir().local_def_id_to_hir_id(impl_ty.def_id.expect_local());
1546     debug!("compare_type_predicate_entailment: trait_to_impl_substs={:?}", trait_to_impl_substs);
1547
1548     // The predicates declared by the impl definition, the trait and the
1549     // associated type in the trait are assumed.
1550     let impl_predicates = tcx.predicates_of(impl_ty_predicates.parent.unwrap());
1551     let mut hybrid_preds = impl_predicates.instantiate_identity(tcx);
1552     hybrid_preds
1553         .predicates
1554         .extend(trait_ty_predicates.instantiate_own(tcx, trait_to_impl_substs).predicates);
1555
1556     debug!("compare_type_predicate_entailment: bounds={:?}", hybrid_preds);
1557
1558     let normalize_cause = traits::ObligationCause::misc(impl_ty_span, impl_ty_hir_id);
1559     let param_env = ty::ParamEnv::new(
1560         tcx.intern_predicates(&hybrid_preds.predicates),
1561         Reveal::UserFacing,
1562         hir::Constness::NotConst,
1563     );
1564     let param_env = traits::normalize_param_env_or_error(tcx, param_env, normalize_cause);
1565     let infcx = tcx.infer_ctxt().build();
1566     let ocx = ObligationCtxt::new(&infcx);
1567
1568     debug!("compare_type_predicate_entailment: caller_bounds={:?}", param_env.caller_bounds());
1569
1570     let mut selcx = traits::SelectionContext::new(&infcx);
1571
1572     assert_eq!(impl_ty_own_bounds.predicates.len(), impl_ty_own_bounds.spans.len());
1573     for (span, predicate) in std::iter::zip(impl_ty_own_bounds.spans, impl_ty_own_bounds.predicates)
1574     {
1575         let cause = ObligationCause::misc(span, impl_ty_hir_id);
1576         let traits::Normalized { value: predicate, obligations } =
1577             traits::normalize(&mut selcx, param_env, cause, predicate);
1578
1579         let cause = ObligationCause::new(
1580             span,
1581             impl_ty_hir_id,
1582             ObligationCauseCode::CompareImplItemObligation {
1583                 impl_item_def_id: impl_ty.def_id.expect_local(),
1584                 trait_item_def_id: trait_ty.def_id,
1585                 kind: impl_ty.kind,
1586             },
1587         );
1588         ocx.register_obligations(obligations);
1589         ocx.register_obligation(traits::Obligation::new(tcx, cause, param_env, predicate));
1590     }
1591
1592     // Check that all obligations are satisfied by the implementation's
1593     // version.
1594     let errors = ocx.select_all_or_error();
1595     if !errors.is_empty() {
1596         let reported = infcx.err_ctxt().report_fulfillment_errors(&errors, None);
1597         return Err(reported);
1598     }
1599
1600     // Finally, resolve all regions. This catches wily misuses of
1601     // lifetime parameters.
1602     let outlives_environment = OutlivesEnvironment::new(param_env);
1603     infcx.check_region_obligations_and_report_errors(
1604         impl_ty.def_id.expect_local(),
1605         &outlives_environment,
1606     );
1607
1608     Ok(())
1609 }
1610
1611 /// Validate that `ProjectionCandidate`s created for this associated type will
1612 /// be valid.
1613 ///
1614 /// Usually given
1615 ///
1616 /// trait X { type Y: Copy } impl X for T { type Y = S; }
1617 ///
1618 /// We are able to normalize `<T as X>::U` to `S`, and so when we check the
1619 /// impl is well-formed we have to prove `S: Copy`.
1620 ///
1621 /// For default associated types the normalization is not possible (the value
1622 /// from the impl could be overridden). We also can't normalize generic
1623 /// associated types (yet) because they contain bound parameters.
1624 #[instrument(level = "debug", skip(tcx))]
1625 pub fn check_type_bounds<'tcx>(
1626     tcx: TyCtxt<'tcx>,
1627     trait_ty: &ty::AssocItem,
1628     impl_ty: &ty::AssocItem,
1629     impl_ty_span: Span,
1630     impl_trait_ref: ty::TraitRef<'tcx>,
1631 ) -> Result<(), ErrorGuaranteed> {
1632     // Given
1633     //
1634     // impl<A, B> Foo<u32> for (A, B) {
1635     //     type Bar<C> =...
1636     // }
1637     //
1638     // - `impl_trait_ref` would be `<(A, B) as Foo<u32>>
1639     // - `impl_ty_substs` would be `[A, B, ^0.0]` (`^0.0` here is the bound var with db 0 and index 0)
1640     // - `rebased_substs` would be `[(A, B), u32, ^0.0]`, combining the substs from
1641     //    the *trait* with the generic associated type parameters (as bound vars).
1642     //
1643     // A note regarding the use of bound vars here:
1644     // Imagine as an example
1645     // ```
1646     // trait Family {
1647     //     type Member<C: Eq>;
1648     // }
1649     //
1650     // impl Family for VecFamily {
1651     //     type Member<C: Eq> = i32;
1652     // }
1653     // ```
1654     // Here, we would generate
1655     // ```notrust
1656     // forall<C> { Normalize(<VecFamily as Family>::Member<C> => i32) }
1657     // ```
1658     // when we really would like to generate
1659     // ```notrust
1660     // forall<C> { Normalize(<VecFamily as Family>::Member<C> => i32) :- Implemented(C: Eq) }
1661     // ```
1662     // But, this is probably fine, because although the first clause can be used with types C that
1663     // do not implement Eq, for it to cause some kind of problem, there would have to be a
1664     // VecFamily::Member<X> for some type X where !(X: Eq), that appears in the value of type
1665     // Member<C: Eq> = .... That type would fail a well-formedness check that we ought to be doing
1666     // elsewhere, which would check that any <T as Family>::Member<X> meets the bounds declared in
1667     // the trait (notably, that X: Eq and T: Family).
1668     let defs: &ty::Generics = tcx.generics_of(impl_ty.def_id);
1669     let mut substs = smallvec::SmallVec::with_capacity(defs.count());
1670     if let Some(def_id) = defs.parent {
1671         let parent_defs = tcx.generics_of(def_id);
1672         InternalSubsts::fill_item(&mut substs, tcx, parent_defs, &mut |param, _| {
1673             tcx.mk_param_from_def(param)
1674         });
1675     }
1676     let mut bound_vars: smallvec::SmallVec<[ty::BoundVariableKind; 8]> =
1677         smallvec::SmallVec::with_capacity(defs.count());
1678     InternalSubsts::fill_single(&mut substs, defs, &mut |param, _| match param.kind {
1679         GenericParamDefKind::Type { .. } => {
1680             let kind = ty::BoundTyKind::Param(param.name);
1681             let bound_var = ty::BoundVariableKind::Ty(kind);
1682             bound_vars.push(bound_var);
1683             tcx.mk_ty(ty::Bound(
1684                 ty::INNERMOST,
1685                 ty::BoundTy { var: ty::BoundVar::from_usize(bound_vars.len() - 1), kind },
1686             ))
1687             .into()
1688         }
1689         GenericParamDefKind::Lifetime => {
1690             let kind = ty::BoundRegionKind::BrNamed(param.def_id, param.name);
1691             let bound_var = ty::BoundVariableKind::Region(kind);
1692             bound_vars.push(bound_var);
1693             tcx.mk_region(ty::ReLateBound(
1694                 ty::INNERMOST,
1695                 ty::BoundRegion { var: ty::BoundVar::from_usize(bound_vars.len() - 1), kind },
1696             ))
1697             .into()
1698         }
1699         GenericParamDefKind::Const { .. } => {
1700             let bound_var = ty::BoundVariableKind::Const;
1701             bound_vars.push(bound_var);
1702             tcx.mk_const(
1703                 ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_usize(bound_vars.len() - 1)),
1704                 tcx.type_of(param.def_id),
1705             )
1706             .into()
1707         }
1708     });
1709     let bound_vars = tcx.mk_bound_variable_kinds(bound_vars.into_iter());
1710     let impl_ty_substs = tcx.intern_substs(&substs);
1711     let container_id = impl_ty.container_id(tcx);
1712
1713     let rebased_substs = impl_ty_substs.rebase_onto(tcx, container_id, impl_trait_ref.substs);
1714     let impl_ty_value = tcx.type_of(impl_ty.def_id);
1715
1716     let param_env = tcx.param_env(impl_ty.def_id);
1717
1718     // When checking something like
1719     //
1720     // trait X { type Y: PartialEq<<Self as X>::Y> }
1721     // impl X for T { default type Y = S; }
1722     //
1723     // We will have to prove the bound S: PartialEq<<T as X>::Y>. In this case
1724     // we want <T as X>::Y to normalize to S. This is valid because we are
1725     // checking the default value specifically here. Add this equality to the
1726     // ParamEnv for normalization specifically.
1727     let normalize_param_env = {
1728         let mut predicates = param_env.caller_bounds().iter().collect::<Vec<_>>();
1729         match impl_ty_value.kind() {
1730             ty::Projection(proj)
1731                 if proj.item_def_id == trait_ty.def_id && proj.substs == rebased_substs =>
1732             {
1733                 // Don't include this predicate if the projected type is
1734                 // exactly the same as the projection. This can occur in
1735                 // (somewhat dubious) code like this:
1736                 //
1737                 // impl<T> X for T where T: X { type Y = <T as X>::Y; }
1738             }
1739             _ => predicates.push(
1740                 ty::Binder::bind_with_vars(
1741                     ty::ProjectionPredicate {
1742                         projection_ty: ty::ProjectionTy {
1743                             item_def_id: trait_ty.def_id,
1744                             substs: rebased_substs,
1745                         },
1746                         term: impl_ty_value.into(),
1747                     },
1748                     bound_vars,
1749                 )
1750                 .to_predicate(tcx),
1751             ),
1752         };
1753         ty::ParamEnv::new(
1754             tcx.intern_predicates(&predicates),
1755             Reveal::UserFacing,
1756             param_env.constness(),
1757         )
1758     };
1759     debug!(?normalize_param_env);
1760
1761     let impl_ty_hir_id = tcx.hir().local_def_id_to_hir_id(impl_ty.def_id.expect_local());
1762     let impl_ty_substs = InternalSubsts::identity_for_item(tcx, impl_ty.def_id);
1763     let rebased_substs = impl_ty_substs.rebase_onto(tcx, container_id, impl_trait_ref.substs);
1764
1765     let infcx = tcx.infer_ctxt().build();
1766     let ocx = ObligationCtxt::new(&infcx);
1767
1768     let assumed_wf_types =
1769         ocx.assumed_wf_types(param_env, impl_ty_span, impl_ty.def_id.expect_local());
1770
1771     let mut selcx = traits::SelectionContext::new(&infcx);
1772     let normalize_cause = ObligationCause::new(
1773         impl_ty_span,
1774         impl_ty_hir_id,
1775         ObligationCauseCode::CheckAssociatedTypeBounds {
1776             impl_item_def_id: impl_ty.def_id.expect_local(),
1777             trait_item_def_id: trait_ty.def_id,
1778         },
1779     );
1780     let mk_cause = |span: Span| {
1781         let code = if span.is_dummy() {
1782             traits::ItemObligation(trait_ty.def_id)
1783         } else {
1784             traits::BindingObligation(trait_ty.def_id, span)
1785         };
1786         ObligationCause::new(impl_ty_span, impl_ty_hir_id, code)
1787     };
1788
1789     let obligations = tcx
1790         .bound_explicit_item_bounds(trait_ty.def_id)
1791         .subst_iter_copied(tcx, rebased_substs)
1792         .map(|(concrete_ty_bound, span)| {
1793             debug!("check_type_bounds: concrete_ty_bound = {:?}", concrete_ty_bound);
1794             traits::Obligation::new(tcx, mk_cause(span), param_env, concrete_ty_bound)
1795         })
1796         .collect();
1797     debug!("check_type_bounds: item_bounds={:?}", obligations);
1798
1799     for mut obligation in util::elaborate_obligations(tcx, obligations) {
1800         let traits::Normalized { value: normalized_predicate, obligations } = traits::normalize(
1801             &mut selcx,
1802             normalize_param_env,
1803             normalize_cause.clone(),
1804             obligation.predicate,
1805         );
1806         debug!("compare_projection_bounds: normalized predicate = {:?}", normalized_predicate);
1807         obligation.predicate = normalized_predicate;
1808
1809         ocx.register_obligations(obligations);
1810         ocx.register_obligation(obligation);
1811     }
1812     // Check that all obligations are satisfied by the implementation's
1813     // version.
1814     let errors = ocx.select_all_or_error();
1815     if !errors.is_empty() {
1816         let reported = infcx.err_ctxt().report_fulfillment_errors(&errors, None);
1817         return Err(reported);
1818     }
1819
1820     // Finally, resolve all regions. This catches wily misuses of
1821     // lifetime parameters.
1822     let implied_bounds = infcx.implied_bounds_tys(param_env, impl_ty_hir_id, assumed_wf_types);
1823     let outlives_environment =
1824         OutlivesEnvironment::with_bounds(param_env, Some(&infcx), implied_bounds);
1825
1826     infcx.check_region_obligations_and_report_errors(
1827         impl_ty.def_id.expect_local(),
1828         &outlives_environment,
1829     );
1830
1831     let constraints = infcx.inner.borrow_mut().opaque_type_storage.take_opaque_types();
1832     for (key, value) in constraints {
1833         infcx
1834             .err_ctxt()
1835             .report_mismatched_types(
1836                 &ObligationCause::misc(
1837                     value.hidden_type.span,
1838                     tcx.hir().local_def_id_to_hir_id(impl_ty.def_id.expect_local()),
1839                 ),
1840                 tcx.mk_opaque(key.def_id.to_def_id(), key.substs),
1841                 value.hidden_type.ty,
1842                 TypeError::Mismatch,
1843             )
1844             .emit();
1845     }
1846
1847     Ok(())
1848 }
1849
1850 fn assoc_item_kind_str(impl_item: &ty::AssocItem) -> &'static str {
1851     match impl_item.kind {
1852         ty::AssocKind::Const => "const",
1853         ty::AssocKind::Fn => "method",
1854         ty::AssocKind::Type => "type",
1855     }
1856 }