rustc_hir_analysis/hir_ty_lowering/

dyn_trait.rs

use rustc_ast::TraitObjectSyntax;
use rustc_data_structures::fx::{FxHashSet, FxIndexMap, FxIndexSet};
use rustc_errors::codes::*;
use rustc_errors::{
    Applicability, Diag, EmissionGuarantee, StashKey, Suggestions, struct_span_code_err,
};
use rustc_hir::def::{DefKind, Res};
use rustc_hir::def_id::DefId;
use rustc_hir::{self as hir, LangItem};
use rustc_lint_defs::builtin::{BARE_TRAIT_OBJECTS, UNUSED_ASSOCIATED_TYPE_BOUNDS};
use rustc_middle::ty::elaborate::ClauseWithSupertraitSpan;
use rustc_middle::ty::{
    self, BottomUpFolder, ExistentialPredicateStableCmpExt as _, Ty, TyCtxt, TypeFoldable,
    TypeVisitableExt, Upcast,
};
use rustc_span::edit_distance::find_best_match_for_name;
use rustc_span::{ErrorGuaranteed, Span};
use rustc_trait_selection::error_reporting::traits::report_dyn_incompatibility;
use rustc_trait_selection::error_reporting::traits::suggestions::NextTypeParamName;
use rustc_trait_selection::traits;
use smallvec::{SmallVec, smallvec};
use tracing::{debug, instrument};

use super::HirTyLowerer;
use crate::errors::DynTraitAssocItemBindingMentionsSelf;
use crate::hir_ty_lowering::{
    GenericArgCountMismatch, ImpliedBoundsContext, OverlappingAsssocItemConstraints,
    PredicateFilter, RegionInferReason,
};

impl<'tcx> dyn HirTyLowerer<'tcx> + '_ {
    /// Lower a trait object type from the HIR to our internal notion of a type.
    #[instrument(level = "debug", skip_all, ret)]
    pub(super) fn lower_trait_object_ty(
        &self,
        span: Span,
        hir_id: hir::HirId,
        hir_bounds: &[hir::PolyTraitRef<'tcx>],
        lifetime: &hir::Lifetime,
        syntax: TraitObjectSyntax,
    ) -> Ty<'tcx> {
        let tcx = self.tcx();
        let dummy_self = tcx.types.trait_object_dummy_self;

        match syntax {
            TraitObjectSyntax::Dyn => {}
            TraitObjectSyntax::None => {
                match self.prohibit_or_lint_bare_trait_object_ty(span, hir_id, hir_bounds) {
                    // Don't continue with type analysis if the `dyn` keyword is missing.
                    // It generates confusing errors, especially if the user meant to use
                    // another keyword like `impl`.
                    Some(guar) => return Ty::new_error(tcx, guar),
                    None => {}
                }
            }
        }

        let mut user_written_bounds = Vec::new();
        let mut potential_assoc_items = Vec::new();
        for poly_trait_ref in hir_bounds.iter() {
            // FIXME(mgca): We actually leak `trait_object_dummy_self` if the type of any assoc
            //              const mentions `Self` (in "Self projections" which we intentionally
            //              allow). That's because we query feed the instantiated type to `type_of`.
            //              That's really bad, dummy self should never escape lowering! It leads us
            //              to accept less code we'd like to support and can lead to ICEs later.
            let result = self.lower_poly_trait_ref(
                poly_trait_ref,
                dummy_self,
                &mut user_written_bounds,
                PredicateFilter::SelfOnly,
                OverlappingAsssocItemConstraints::Forbidden,
            );
            if let Err(GenericArgCountMismatch { invalid_args, .. }) = result.correct {
                potential_assoc_items.extend(invalid_args);
            }
        }

        self.add_default_traits(
            &mut user_written_bounds,
            dummy_self,
            &hir_bounds
                .iter()
                .map(|&trait_ref| hir::GenericBound::Trait(trait_ref))
                .collect::<Vec<_>>(),
            ImpliedBoundsContext::AssociatedTypeOrImplTrait,
            span,
        );

        let (mut elaborated_trait_bounds, elaborated_projection_bounds) =
            traits::expand_trait_aliases(tcx, user_written_bounds.iter().copied());

        // FIXME(sized-hierarchy): https://github.com/rust-lang/rust/pull/142712#issuecomment-3013231794
        debug!(?user_written_bounds, ?elaborated_trait_bounds);
        let meta_sized_did = tcx.require_lang_item(LangItem::MetaSized, span);
        // Don't strip out `MetaSized` when the user wrote it explicitly, only when it was
        // elaborated
        if user_written_bounds
            .iter()
            .all(|(clause, _)| clause.as_trait_clause().map(|p| p.def_id()) != Some(meta_sized_did))
        {
            elaborated_trait_bounds.retain(|(pred, _)| pred.def_id() != meta_sized_did);
        }
        debug!(?user_written_bounds, ?elaborated_trait_bounds);

        let (regular_traits, mut auto_traits): (Vec<_>, Vec<_>) = elaborated_trait_bounds
            .into_iter()
            .partition(|(trait_ref, _)| !tcx.trait_is_auto(trait_ref.def_id()));

        // We don't support empty trait objects.
        if regular_traits.is_empty() && auto_traits.is_empty() {
            let guar =
                self.report_trait_object_with_no_traits(span, user_written_bounds.iter().copied());
            return Ty::new_error(tcx, guar);
        }
        // We don't support >1 principal
        if regular_traits.len() > 1 {
            let guar = self.report_trait_object_addition_traits(&regular_traits);
            return Ty::new_error(tcx, guar);
        }
        // Don't create a dyn trait if we have errors in the principal.
        if let Err(guar) = regular_traits.error_reported() {
            return Ty::new_error(tcx, guar);
        }

        // Check that there are no gross dyn-compatibility violations;
        // most importantly, that the supertraits don't contain `Self`,
        // to avoid ICEs.
        for (clause, span) in user_written_bounds {
            if let Some(trait_pred) = clause.as_trait_clause() {
                let violations = self.dyn_compatibility_violations(trait_pred.def_id());
                if !violations.is_empty() {
                    let reported = report_dyn_incompatibility(
                        tcx,
                        span,
                        Some(hir_id),
                        trait_pred.def_id(),
                        &violations,
                    )
                    .emit();
                    return Ty::new_error(tcx, reported);
                }
            }
        }

        // Map the projection bounds onto a key that makes it easy to remove redundant
        // bounds that are constrained by supertraits of the principal trait.
        //
        // Also make sure we detect conflicting bounds from expanding trait aliases.
        //
        // FIXME(#150936): Since the elaborated projection bounds also include the user-written ones
        //                 and we're separately rejecting duplicate+conflicting bindings for trait
        //                 object types when lowering assoc item bindings, there are basic cases
        //                 where we're emitting two distinct but very similar diagnostics.
        let mut projection_bounds = FxIndexMap::default();
        for (proj, proj_span) in elaborated_projection_bounds {
            let item_def_id = proj.item_def_id();

            let proj = proj.map_bound(|mut proj| {
                let references_self = proj.term.walk().any(|arg| arg == dummy_self.into());
                if references_self {
                    let guar = self.dcx().emit_err(DynTraitAssocItemBindingMentionsSelf {
                        span,
                        kind: tcx.def_descr(item_def_id),
                        binding: proj_span,
                    });
                    proj.term = replace_dummy_self_with_error(tcx, proj.term, guar);
                }
                proj
            });

            let key = (
                item_def_id,
                tcx.anonymize_bound_vars(
                    proj.map_bound(|proj| proj.projection_term.trait_ref(tcx)),
                ),
            );
            if let Some((old_proj, old_proj_span)) =
                projection_bounds.insert(key, (proj, proj_span))
                && tcx.anonymize_bound_vars(proj) != tcx.anonymize_bound_vars(old_proj)
            {
                let kind = tcx.def_descr(item_def_id);
                let name = tcx.item_name(item_def_id);
                self.dcx()
                    .struct_span_err(span, format!("conflicting {kind} bindings for `{name}`"))
                    .with_span_label(
                        old_proj_span,
                        format!("`{name}` is specified to be `{}` here", old_proj.term()),
                    )
                    .with_span_label(
                        proj_span,
                        format!("`{name}` is specified to be `{}` here", proj.term()),
                    )
                    .emit();
            }
        }

        let principal_trait = regular_traits.into_iter().next();

        // A stable ordering of associated types & consts from the principal trait and all its
        // supertraits. We use this to ensure that different substitutions of a trait don't
        // result in `dyn Trait` types with different projections lists, which can be unsound:
        // <https://github.com/rust-lang/rust/pull/136458>.
        // We achieve a stable ordering by walking over the unsubstituted principal trait ref.
        let mut ordered_associated_items = vec![];

        if let Some((principal_trait, ref spans)) = principal_trait {
            let principal_trait = principal_trait.map_bound(|trait_pred| {
                assert_eq!(trait_pred.polarity, ty::PredicatePolarity::Positive);
                trait_pred.trait_ref
            });

            for ClauseWithSupertraitSpan { clause, supertrait_span } in traits::elaborate(
                tcx,
                [ClauseWithSupertraitSpan::new(
                    ty::TraitRef::identity(tcx, principal_trait.def_id()).upcast(tcx),
                    *spans.last().unwrap(),
                )],
            )
            .filter_only_self()
            {
                let clause = clause.instantiate_supertrait(tcx, principal_trait);
                debug!("observing object predicate `{clause:?}`");

                let bound_predicate = clause.kind();
                match bound_predicate.skip_binder() {
                    ty::ClauseKind::Trait(pred) => {
                        // FIXME(negative_bounds): Handle this correctly...
                        let trait_ref =
                            tcx.anonymize_bound_vars(bound_predicate.rebind(pred.trait_ref));
                        ordered_associated_items.extend(
                            tcx.associated_items(pred.trait_ref.def_id)
                                .in_definition_order()
                                // Only associated types & type consts can possibly be
                                // constrained in a trait object type via a binding.
                                .filter(|item| item.is_type() || item.is_type_const(tcx))
                                // Traits with RPITITs are simply not dyn compatible (for now).
                                .filter(|item| !item.is_impl_trait_in_trait())
                                .map(|item| (item.def_id, trait_ref)),
                        );
                    }
                    ty::ClauseKind::Projection(pred) => {
                        let pred = bound_predicate.rebind(pred);
                        // A `Self` within the original bound will be instantiated with a
                        // `trait_object_dummy_self`, so check for that.
                        let references_self =
                            pred.skip_binder().term.walk().any(|arg| arg == dummy_self.into());

                        // If the projection output contains `Self`, force the user to
                        // elaborate it explicitly to avoid a lot of complexity.
                        //
                        // The "classically useful" case is the following:
                        // ```
                        //     trait MyTrait: FnMut() -> <Self as MyTrait>::MyOutput {
                        //         type MyOutput;
                        //     }
                        // ```
                        //
                        // Here, the user could theoretically write `dyn MyTrait<MyOutput = X>`,
                        // but actually supporting that would "expand" to an infinitely-long type
                        // `fix $ τ → dyn MyTrait<MyOutput = X, Output = <τ as MyTrait>::MyOutput`.
                        //
                        // Instead, we force the user to write
                        // `dyn MyTrait<MyOutput = X, Output = X>`, which is uglier but works. See
                        // the discussion in #56288 for alternatives.
                        if !references_self {
                            let key = (
                                pred.item_def_id(),
                                tcx.anonymize_bound_vars(
                                    pred.map_bound(|proj| proj.projection_term.trait_ref(tcx)),
                                ),
                            );
                            if !projection_bounds.contains_key(&key) {
                                projection_bounds.insert(key, (pred, supertrait_span));
                            }
                        }

                        self.check_elaborated_projection_mentions_input_lifetimes(
                            pred,
                            *spans.first().unwrap(),
                            supertrait_span,
                        );
                    }
                    _ => (),
                }
            }
        }

        // Flag assoc item bindings that didn't really need to be specified.
        for &(projection_bound, span) in projection_bounds.values() {
            let def_id = projection_bound.item_def_id();
            if tcx.generics_require_sized_self(def_id) {
                // FIXME(mgca): Ideally we would generalize the name of this lint to sth. like
                // `unused_associated_item_bindings` since this can now also trigger on *const*
                // projections / assoc *const* bindings.
                tcx.emit_node_span_lint(
                    UNUSED_ASSOCIATED_TYPE_BOUNDS,
                    hir_id,
                    span,
                    crate::errors::UnusedAssociatedTypeBounds { span },
                );
            }
        }

        // The user has to constrain all associated types & consts via bindings unless the
        // corresponding associated item has a `where Self: Sized` clause. This can be done
        // in the `dyn Trait` directly, in the supertrait bounds or behind trait aliases.
        //
        // Collect all associated items that weren't specified and compute the list of
        // projection bounds which we'll later turn into existential ones.
        //
        // We intentionally keep around projections whose associated item has a `Self: Sized`
        // bound in order to be able to wfcheck the RHS, allow the RHS to constrain generic
        // parameters and to imply bounds.
        // See also <https://github.com/rust-lang/rust/pull/140684>.
        let mut missing_assoc_items = FxIndexSet::default();
        let projection_bounds: Vec<_> = ordered_associated_items
            .into_iter()
            .filter_map(|key @ (def_id, _)| {
                if let Some(&assoc) = projection_bounds.get(&key) {
                    return Some(assoc);
                }
                if !tcx.generics_require_sized_self(def_id) {
                    missing_assoc_items.insert(key);
                }
                None
            })
            .collect();

        // If there are any associated items whose value wasn't provided, bail out with an error.
        if let Err(guar) = self.check_for_required_assoc_items(
            principal_trait.as_ref().map_or(smallvec![], |(_, spans)| spans.clone()),
            missing_assoc_items,
            potential_assoc_items,
            hir_bounds,
        ) {
            return Ty::new_error(tcx, guar);
        }

        // De-duplicate auto traits so that, e.g., `dyn Trait + Send + Send` is the same as
        // `dyn Trait + Send`.
        // We remove duplicates by inserting into a `FxHashSet` to avoid re-ordering
        // the bounds
        let mut duplicates = FxHashSet::default();
        auto_traits.retain(|(trait_pred, _)| duplicates.insert(trait_pred.def_id()));

        debug!(?principal_trait);
        debug!(?auto_traits);

        // Erase the `dummy_self` (`trait_object_dummy_self`) used above.
        let principal_trait_ref = principal_trait.map(|(trait_pred, spans)| {
            trait_pred.map_bound(|trait_pred| {
                let trait_ref = trait_pred.trait_ref;
                assert_eq!(trait_pred.polarity, ty::PredicatePolarity::Positive);
                assert_eq!(trait_ref.self_ty(), dummy_self);

                let span = *spans.first().unwrap();

                // Verify that `dummy_self` did not leak inside generic parameter defaults. This
                // could not be done at path creation, since we need to see through trait aliases.
                let mut missing_generic_params = Vec::new();
                let generics = tcx.generics_of(trait_ref.def_id);
                let args: Vec<_> = trait_ref
                    .args
                    .iter()
                    .enumerate()
                    // Skip `Self`
                    .skip(1)
                    .map(|(index, arg)| {
                        if arg.walk().any(|arg| arg == dummy_self.into()) {
                            let param = &generics.own_params[index];
                            missing_generic_params.push((param.name, param.kind.clone()));
                            param.to_error(tcx)
                        } else {
                            arg
                        }
                    })
                    .collect();

                let empty_generic_args = hir_bounds.iter().any(|hir_bound| {
                    hir_bound.trait_ref.path.res == Res::Def(DefKind::Trait, trait_ref.def_id)
                        && hir_bound.span.contains(span)
                });
                self.report_missing_generic_params(
                    missing_generic_params,
                    trait_ref.def_id,
                    span,
                    empty_generic_args,
                );

                ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef::new(
                    tcx,
                    trait_ref.def_id,
                    args,
                ))
            })
        });

        let existential_projections = projection_bounds.into_iter().map(|(bound, _)| {
            bound.map_bound(|mut b| {
                assert_eq!(b.projection_term.self_ty(), dummy_self);

                // Like for trait refs, verify that `dummy_self` did not leak inside default type
                // parameters.
                let references_self = b.projection_term.args.iter().skip(1).any(|arg| {
                    if arg.walk().any(|arg| arg == dummy_self.into()) {
                        return true;
                    }
                    false
                });
                if references_self {
                    let guar = tcx
                        .dcx()
                        .span_delayed_bug(span, "trait object projection bounds reference `Self`");
                    b.projection_term = replace_dummy_self_with_error(tcx, b.projection_term, guar);
                }

                ty::ExistentialPredicate::Projection(ty::ExistentialProjection::erase_self_ty(
                    tcx, b,
                ))
            })
        });

        let mut auto_trait_predicates: Vec<_> = auto_traits
            .into_iter()
            .map(|(trait_pred, _)| {
                assert_eq!(trait_pred.polarity(), ty::PredicatePolarity::Positive);
                assert_eq!(trait_pred.self_ty().skip_binder(), dummy_self);

                ty::Binder::dummy(ty::ExistentialPredicate::AutoTrait(trait_pred.def_id()))
            })
            .collect();
        auto_trait_predicates.dedup();

        // N.b. principal, projections, auto traits
        // FIXME: This is actually wrong with multiple principals in regards to symbol mangling
        let mut v = principal_trait_ref
            .into_iter()
            .chain(existential_projections)
            .chain(auto_trait_predicates)
            .collect::<SmallVec<[_; 8]>>();
        v.sort_by(|a, b| a.skip_binder().stable_cmp(tcx, &b.skip_binder()));
        let existential_predicates = tcx.mk_poly_existential_predicates(&v);

        // Use explicitly-specified region bound, unless the bound is missing.
        let region_bound = if !lifetime.is_elided() {
            self.lower_lifetime(lifetime, RegionInferReason::ExplicitObjectLifetime)
        } else {
            self.compute_object_lifetime_bound(span, existential_predicates).unwrap_or_else(|| {
                // Curiously, we prefer object lifetime default for `+ '_`...
                if tcx.named_bound_var(lifetime.hir_id).is_some() {
                    self.lower_lifetime(lifetime, RegionInferReason::ExplicitObjectLifetime)
                } else {
                    let reason =
                        if let hir::LifetimeKind::ImplicitObjectLifetimeDefault = lifetime.kind {
                            RegionInferReason::ObjectLifetimeDefault(span.shrink_to_hi())
                        } else {
                            RegionInferReason::ExplicitObjectLifetime
                        };
                    self.re_infer(span, reason)
                }
            })
        };
        debug!(?region_bound);

        Ty::new_dynamic(tcx, existential_predicates, region_bound)
    }

    /// Check that elaborating the principal of a trait ref doesn't lead to projections
    /// that are unconstrained. This can happen because an otherwise unconstrained
    /// *type variable* can be substituted with a type that has late-bound regions. See
    /// `elaborated-predicates-unconstrained-late-bound.rs` for a test.
    fn check_elaborated_projection_mentions_input_lifetimes(
        &self,
        pred: ty::PolyProjectionPredicate<'tcx>,
        span: Span,
        supertrait_span: Span,
    ) {
        let tcx = self.tcx();

        // Find any late-bound regions declared in `ty` that are not
        // declared in the trait-ref or assoc_item. These are not well-formed.
        //
        // Example:
        //
        //     for<'a> <T as Iterator>::Item = &'a str // <-- 'a is bad
        //     for<'a> <T as FnMut<(&'a u32,)>>::Output = &'a str // <-- 'a is ok
        let late_bound_in_projection_term =
            tcx.collect_constrained_late_bound_regions(pred.map_bound(|pred| pred.projection_term));
        let late_bound_in_term =
            tcx.collect_referenced_late_bound_regions(pred.map_bound(|pred| pred.term));
        debug!(?late_bound_in_projection_term);
        debug!(?late_bound_in_term);

        // FIXME: point at the type params that don't have appropriate lifetimes:
        // struct S1<F: for<'a> Fn(&i32, &i32) -> &'a i32>(F);
        //                         ----  ----     ^^^^^^^
        // NOTE(mgca): This error should be impossible to trigger with assoc const bindings.
        self.validate_late_bound_regions(
            late_bound_in_projection_term,
            late_bound_in_term,
            |br_name| {
                let item_name = tcx.item_name(pred.item_def_id());
                struct_span_code_err!(
                    self.dcx(),
                    span,
                    E0582,
                    "binding for associated type `{}` references {}, \
                             which does not appear in the trait input types",
                    item_name,
                    br_name
                )
                .with_span_label(supertrait_span, "due to this supertrait")
            },
        );
    }

    /// Prohibit or lint against *bare* trait object types depending on the edition.
    ///
    /// *Bare* trait object types are ones that aren't preceded by the keyword `dyn`.
    /// In edition 2021 and onward we emit a hard error for them.
    fn prohibit_or_lint_bare_trait_object_ty(
        &self,
        span: Span,
        hir_id: hir::HirId,
        hir_bounds: &[hir::PolyTraitRef<'tcx>],
    ) -> Option<ErrorGuaranteed> {
        let tcx = self.tcx();
        let [poly_trait_ref, ..] = hir_bounds else { return None };

        let in_path = match tcx.parent_hir_node(hir_id) {
            hir::Node::Ty(hir::Ty {
                kind: hir::TyKind::Path(hir::QPath::TypeRelative(qself, _)),
                ..
            })
            | hir::Node::Expr(hir::Expr {
                kind: hir::ExprKind::Path(hir::QPath::TypeRelative(qself, _)),
                ..
            })
            | hir::Node::PatExpr(hir::PatExpr {
                kind: hir::PatExprKind::Path(hir::QPath::TypeRelative(qself, _)),
                ..
            }) if qself.hir_id == hir_id => true,
            _ => false,
        };
        let needs_bracket = in_path
            && !tcx
                .sess
                .source_map()
                .span_to_prev_source(span)
                .ok()
                .is_some_and(|s| s.trim_end().ends_with('<'));

        let is_global = poly_trait_ref.trait_ref.path.is_global();

        let mut sugg = vec![(
            span.shrink_to_lo(),
            format!(
                "{}dyn {}",
                if needs_bracket { "<" } else { "" },
                if is_global { "(" } else { "" },
            ),
        )];

        if is_global || needs_bracket {
            sugg.push((
                span.shrink_to_hi(),
                format!(
                    "{}{}",
                    if is_global { ")" } else { "" },
                    if needs_bracket { ">" } else { "" },
                ),
            ));
        }

        if span.edition().at_least_rust_2021() {
            let mut diag = rustc_errors::struct_span_code_err!(
                self.dcx(),
                span,
                E0782,
                "{}",
                "expected a type, found a trait"
            );
            if span.can_be_used_for_suggestions()
                && poly_trait_ref.trait_ref.trait_def_id().is_some()
                && !self.maybe_suggest_impl_trait(span, hir_id, hir_bounds, &mut diag)
                && !self.maybe_suggest_dyn_trait(hir_id, span, sugg, &mut diag)
            {
                self.maybe_suggest_add_generic_impl_trait(span, hir_id, &mut diag);
            }
            // Check if the impl trait that we are considering is an impl of a local trait.
            self.maybe_suggest_blanket_trait_impl(span, hir_id, &mut diag);
            self.maybe_suggest_assoc_ty_bound(hir_id, &mut diag);
            self.maybe_suggest_typoed_method(
                hir_id,
                poly_trait_ref.trait_ref.trait_def_id(),
                &mut diag,
            );
            // In case there is an associated type with the same name
            // Add the suggestion to this error
            if let Some(mut sugg) =
                self.dcx().steal_non_err(span, StashKey::AssociatedTypeSuggestion)
                && let Suggestions::Enabled(ref mut s1) = diag.suggestions
                && let Suggestions::Enabled(ref mut s2) = sugg.suggestions
            {
                s1.append(s2);
                sugg.cancel();
            }
            Some(diag.emit())
        } else {
            tcx.node_span_lint(BARE_TRAIT_OBJECTS, hir_id, span, |lint| {
                lint.primary_message("trait objects without an explicit `dyn` are deprecated");
                if span.can_be_used_for_suggestions() {
                    lint.multipart_suggestion(
                        "if this is a dyn-compatible trait, use `dyn`",
                        sugg,
                        Applicability::MachineApplicable,
                    );
                }
                self.maybe_suggest_blanket_trait_impl(span, hir_id, lint);
            });
            None
        }
    }

    /// For a struct or enum with an invalid bare trait object field, suggest turning
    /// it into a generic type bound.
    fn maybe_suggest_add_generic_impl_trait(
        &self,
        span: Span,
        hir_id: hir::HirId,
        diag: &mut Diag<'_>,
    ) -> bool {
        let tcx = self.tcx();

        let parent_hir_id = tcx.parent_hir_id(hir_id);
        let parent_item = tcx.hir_get_parent_item(hir_id).def_id;

        let generics = match tcx.hir_node_by_def_id(parent_item) {
            hir::Node::Item(hir::Item {
                kind: hir::ItemKind::Struct(_, generics, variant),
                ..
            }) => {
                if !variant.fields().iter().any(|field| field.hir_id == parent_hir_id) {
                    return false;
                }
                generics
            }
            hir::Node::Item(hir::Item { kind: hir::ItemKind::Enum(_, generics, def), .. }) => {
                if !def
                    .variants
                    .iter()
                    .flat_map(|variant| variant.data.fields().iter())
                    .any(|field| field.hir_id == parent_hir_id)
                {
                    return false;
                }
                generics
            }
            _ => return false,
        };

        let Ok(rendered_ty) = tcx.sess.source_map().span_to_snippet(span) else {
            return false;
        };

        let param = "TUV"
            .chars()
            .map(|c| c.to_string())
            .chain((0..).map(|i| format!("P{i}")))
            .find(|s| !generics.params.iter().any(|param| param.name.ident().as_str() == s))
            .expect("we definitely can find at least one param name to generate");
        let mut sugg = vec![(span, param.to_string())];
        if let Some(insertion_span) = generics.span_for_param_suggestion() {
            sugg.push((insertion_span, format!(", {param}: {}", rendered_ty)));
        } else {
            sugg.push((generics.where_clause_span, format!("<{param}: {}>", rendered_ty)));
        }
        diag.multipart_suggestion(
            "you might be missing a type parameter",
            sugg,
            Applicability::MachineApplicable,
        );
        true
    }

    /// Make sure that we are in the condition to suggest the blanket implementation.
    fn maybe_suggest_blanket_trait_impl<G: EmissionGuarantee>(
        &self,
        span: Span,
        hir_id: hir::HirId,
        diag: &mut Diag<'_, G>,
    ) {
        let tcx = self.tcx();
        let parent_id = tcx.hir_get_parent_item(hir_id).def_id;
        if let hir::Node::Item(hir::Item {
            kind: hir::ItemKind::Impl(hir::Impl { self_ty: impl_self_ty, of_trait, generics, .. }),
            ..
        }) = tcx.hir_node_by_def_id(parent_id)
            && hir_id == impl_self_ty.hir_id
        {
            let Some(of_trait) = of_trait else {
                diag.span_suggestion_verbose(
                    impl_self_ty.span.shrink_to_hi(),
                    "you might have intended to implement this trait for a given type",
                    format!(" for /* Type */"),
                    Applicability::HasPlaceholders,
                );
                return;
            };
            if !of_trait.trait_ref.trait_def_id().is_some_and(|def_id| def_id.is_local()) {
                return;
            }
            let of_trait_span = of_trait.trait_ref.path.span;
            // make sure that we are not calling unwrap to abort during the compilation
            let Ok(of_trait_name) = tcx.sess.source_map().span_to_snippet(of_trait_span) else {
                return;
            };

            let Ok(impl_trait_name) = self.tcx().sess.source_map().span_to_snippet(span) else {
                return;
            };
            let sugg = self.add_generic_param_suggestion(generics, span, &impl_trait_name);
            diag.multipart_suggestion(
                format!(
                    "alternatively use a blanket implementation to implement `{of_trait_name}` for \
                     all types that also implement `{impl_trait_name}`"
                ),
                sugg,
                Applicability::MaybeIncorrect,
            );
        }
    }

    /// Try our best to approximate when adding `dyn` would be helpful for a bare
    /// trait object.
    ///
    /// Right now, this is if the type is either directly nested in another ty,
    /// or if it's in the tail field within a struct. This approximates what the
    /// user would've gotten on edition 2015, except for the case where we have
    /// an *obvious* knock-on `Sized` error.
    fn maybe_suggest_dyn_trait(
        &self,
        hir_id: hir::HirId,
        span: Span,
        sugg: Vec<(Span, String)>,
        diag: &mut Diag<'_>,
    ) -> bool {
        let tcx = self.tcx();
        if span.in_derive_expansion() {
            return false;
        }

        // Look at the direct HIR parent, since we care about the relationship between
        // the type and the thing that directly encloses it.
        match tcx.parent_hir_node(hir_id) {
            // These are all generally ok. Namely, when a trait object is nested
            // into another expression or ty, it's either very certain that they
            // missed the ty (e.g. `&Trait`) or it's not really possible to tell
            // what their intention is, so let's not give confusing suggestions and
            // just mention `dyn`. The user can make up their mind what to do here.
            hir::Node::Ty(_)
            | hir::Node::Expr(_)
            | hir::Node::PatExpr(_)
            | hir::Node::PathSegment(_)
            | hir::Node::AssocItemConstraint(_)
            | hir::Node::TraitRef(_)
            | hir::Node::Item(_)
            | hir::Node::WherePredicate(_) => {}

            hir::Node::Field(field) => {
                // Enums can't have unsized fields, fields can only have an unsized tail field.
                if let hir::Node::Item(hir::Item {
                    kind: hir::ItemKind::Struct(_, _, variant), ..
                }) = tcx.parent_hir_node(field.hir_id)
                    && variant
                        .fields()
                        .last()
                        .is_some_and(|tail_field| tail_field.hir_id == field.hir_id)
                {
                    // Ok
                } else {
                    return false;
                }
            }
            _ => return false,
        }

        // FIXME: Only emit this suggestion if the trait is dyn-compatible.
        diag.multipart_suggestion(
            "you can add the `dyn` keyword if you want a trait object",
            sugg,
            Applicability::MachineApplicable,
        );
        true
    }

    fn add_generic_param_suggestion(
        &self,
        generics: &hir::Generics<'_>,
        self_ty_span: Span,
        impl_trait_name: &str,
    ) -> Vec<(Span, String)> {
        // check if the trait has generics, to make a correct suggestion
        let param_name = generics.params.next_type_param_name(None);

        let add_generic_sugg = if let Some(span) = generics.span_for_param_suggestion() {
            (span, format!(", {param_name}: {impl_trait_name}"))
        } else {
            (generics.span, format!("<{param_name}: {impl_trait_name}>"))
        };
        vec![(self_ty_span, param_name), add_generic_sugg]
    }

    /// Make sure that we are in the condition to suggest `impl Trait`.
    fn maybe_suggest_impl_trait(
        &self,
        span: Span,
        hir_id: hir::HirId,
        hir_bounds: &[hir::PolyTraitRef<'tcx>],
        diag: &mut Diag<'_>,
    ) -> bool {
        let tcx = self.tcx();
        let parent_id = tcx.hir_get_parent_item(hir_id).def_id;
        // FIXME: If `type_alias_impl_trait` is enabled, also look for `Trait0<Ty = Trait1>`
        //        and suggest `Trait0<Ty = impl Trait1>`.
        // Functions are found in three different contexts.
        // 1. Independent functions
        // 2. Functions inside trait blocks
        // 3. Functions inside impl blocks
        let (sig, generics) = match tcx.hir_node_by_def_id(parent_id) {
            hir::Node::Item(hir::Item {
                kind: hir::ItemKind::Fn { sig, generics, .. }, ..
            }) => (sig, generics),
            hir::Node::TraitItem(hir::TraitItem {
                kind: hir::TraitItemKind::Fn(sig, _),
                generics,
                ..
            }) => (sig, generics),
            hir::Node::ImplItem(hir::ImplItem {
                kind: hir::ImplItemKind::Fn(sig, _),
                generics,
                ..
            }) => (sig, generics),
            _ => return false,
        };
        let Ok(trait_name) = tcx.sess.source_map().span_to_snippet(span) else {
            return false;
        };
        let impl_sugg = vec![(span.shrink_to_lo(), "impl ".to_string())];
        // Check if trait object is safe for suggesting dynamic dispatch.
        let is_dyn_compatible = hir_bounds.iter().all(|bound| match bound.trait_ref.path.res {
            Res::Def(DefKind::Trait, id) => tcx.is_dyn_compatible(id),
            _ => false,
        });

        let borrowed = matches!(
            tcx.parent_hir_node(hir_id),
            hir::Node::Ty(hir::Ty { kind: hir::TyKind::Ref(..), .. })
        );

        // Suggestions for function return type.
        if let hir::FnRetTy::Return(ty) = sig.decl.output
            && ty.peel_refs().hir_id == hir_id
        {
            let pre = if !is_dyn_compatible {
                format!("`{trait_name}` is dyn-incompatible, ")
            } else {
                String::new()
            };
            let msg = format!(
                "{pre}use `impl {trait_name}` to return an opaque type, as long as you return a \
                 single underlying type",
            );

            diag.multipart_suggestion(msg, impl_sugg, Applicability::MachineApplicable);

            // Suggest `Box<dyn Trait>` for return type
            if is_dyn_compatible {
                // If the return type is `&Trait`, we don't want
                // the ampersand to be displayed in the `Box<dyn Trait>`
                // suggestion.
                let suggestion = if borrowed {
                    vec![(ty.span, format!("Box<dyn {trait_name}>"))]
                } else {
                    vec![
                        (ty.span.shrink_to_lo(), "Box<dyn ".to_string()),
                        (ty.span.shrink_to_hi(), ">".to_string()),
                    ]
                };

                diag.multipart_suggestion(
                    "alternatively, you can return an owned trait object",
                    suggestion,
                    Applicability::MachineApplicable,
                );
            }
            return true;
        }

        // Suggestions for function parameters.
        for ty in sig.decl.inputs {
            if ty.peel_refs().hir_id != hir_id {
                continue;
            }
            let sugg = self.add_generic_param_suggestion(generics, span, &trait_name);
            diag.multipart_suggestion(
                format!("use a new generic type parameter, constrained by `{trait_name}`"),
                sugg,
                Applicability::MachineApplicable,
            );
            diag.multipart_suggestion(
                "you can also use an opaque type, but users won't be able to specify the type \
                 parameter when calling the `fn`, having to rely exclusively on type inference",
                impl_sugg,
                Applicability::MachineApplicable,
            );
            if !is_dyn_compatible {
                diag.note(format!(
                    "`{trait_name}` is dyn-incompatible, otherwise a trait object could be used"
                ));
            } else {
                // No ampersand in suggestion if it's borrowed already
                let (dyn_str, paren_dyn_str) =
                    if borrowed { ("dyn ", "(dyn ") } else { ("&dyn ", "&(dyn ") };

                let sugg = if let [_, _, ..] = hir_bounds {
                    // There is more than one trait bound, we need surrounding parentheses.
                    vec![
                        (span.shrink_to_lo(), paren_dyn_str.to_string()),
                        (span.shrink_to_hi(), ")".to_string()),
                    ]
                } else {
                    vec![(span.shrink_to_lo(), dyn_str.to_string())]
                };
                diag.multipart_suggestion(
                    format!(
                        "alternatively, use a trait object to accept any type that implements \
                         `{trait_name}`, accessing its methods at runtime using dynamic dispatch",
                    ),
                    sugg,
                    Applicability::MachineApplicable,
                );
            }
            return true;
        }
        false
    }

    fn maybe_suggest_assoc_ty_bound(&self, hir_id: hir::HirId, diag: &mut Diag<'_>) {
        let mut parents = self.tcx().hir_parent_iter(hir_id);

        if let Some((c_hir_id, hir::Node::AssocItemConstraint(constraint))) = parents.next()
            && let Some(obj_ty) = constraint.ty()
            && let Some((_, hir::Node::TraitRef(trait_ref))) = parents.next()
        {
            if let Some((_, hir::Node::Ty(ty))) = parents.next()
                && let hir::TyKind::TraitObject(..) = ty.kind
            {
                // Assoc ty bounds aren't permitted inside trait object types.
                return;
            }

            if trait_ref
                .path
                .segments
                .iter()
                .find_map(|seg| {
                    seg.args.filter(|args| args.constraints.iter().any(|c| c.hir_id == c_hir_id))
                })
                .is_none_or(|args| args.parenthesized != hir::GenericArgsParentheses::No)
            {
                // Only consider angle-bracketed args (where we have a `=` to replace with `:`).
                return;
            }

            let lo = if constraint.gen_args.span_ext.is_dummy() {
                constraint.ident.span
            } else {
                constraint.gen_args.span_ext
            };
            let hi = obj_ty.span;

            if !lo.eq_ctxt(hi) {
                return;
            }

            diag.span_suggestion_verbose(
                lo.between(hi),
                "you might have meant to write a bound here",
                ": ",
                Applicability::MaybeIncorrect,
            );
        }
    }

    fn maybe_suggest_typoed_method(
        &self,
        hir_id: hir::HirId,
        trait_def_id: Option<DefId>,
        diag: &mut Diag<'_>,
    ) {
        let tcx = self.tcx();
        let Some(trait_def_id) = trait_def_id else {
            return;
        };
        let hir::Node::Expr(hir::Expr {
            kind: hir::ExprKind::Path(hir::QPath::TypeRelative(path_ty, segment)),
            ..
        }) = tcx.parent_hir_node(hir_id)
        else {
            return;
        };
        if path_ty.hir_id != hir_id {
            return;
        }
        let names: Vec<_> = tcx
            .associated_items(trait_def_id)
            .in_definition_order()
            .filter(|assoc| assoc.namespace() == hir::def::Namespace::ValueNS)
            .map(|cand| cand.name())
            .collect();
        if let Some(typo) = find_best_match_for_name(&names, segment.ident.name, None) {
            diag.span_suggestion_verbose(
                segment.ident.span,
                format!(
                    "you may have misspelled this associated item, causing `{}` \
                    to be interpreted as a type rather than a trait",
                    tcx.item_name(trait_def_id),
                ),
                typo,
                Applicability::MaybeIncorrect,
            );
        }
    }
}

fn replace_dummy_self_with_error<'tcx, T: TypeFoldable<TyCtxt<'tcx>>>(
    tcx: TyCtxt<'tcx>,
    t: T,
    guar: ErrorGuaranteed,
) -> T {
    t.fold_with(&mut BottomUpFolder {
        tcx,
        ty_op: |ty| {
            if ty == tcx.types.trait_object_dummy_self { Ty::new_error(tcx, guar) } else { ty }
        },
        lt_op: |lt| lt,
        ct_op: |ct| ct,
    })
}