hir.rs

// ignore-tidy-filelength
use std::fmt;

use rustc_abi::ExternAbi;
use rustc_ast::attr::AttributeExt;
use rustc_ast::token::CommentKind;
use rustc_ast::util::parser::ExprPrecedence;
use rustc_ast::{
    self as ast, FloatTy, InlineAsmOptions, InlineAsmTemplatePiece, IntTy, Label, LitIntType,
    LitKind, TraitObjectSyntax, UintTy, UnsafeBinderCastKind,
};
pub use rustc_ast::{
    AssignOp, AssignOpKind, AttrId, AttrStyle, BinOp, BinOpKind, BindingMode, BorrowKind,
    BoundConstness, BoundPolarity, ByRef, CaptureBy, DelimArgs, ImplPolarity, IsAuto,
    MetaItemInner, MetaItemLit, Movability, Mutability, UnOp,
};
use rustc_attr_data_structures::AttributeKind;
use rustc_data_structures::fingerprint::Fingerprint;
use rustc_data_structures::sorted_map::SortedMap;
use rustc_data_structures::tagged_ptr::TaggedRef;
use rustc_index::IndexVec;
use rustc_macros::{Decodable, Encodable, HashStable_Generic};
use rustc_span::def_id::LocalDefId;
use rustc_span::hygiene::MacroKind;
use rustc_span::source_map::Spanned;
use rustc_span::{BytePos, DUMMY_SP, ErrorGuaranteed, Ident, Span, Symbol, kw, sym};
use rustc_target::asm::InlineAsmRegOrRegClass;
use smallvec::SmallVec;
use thin_vec::ThinVec;
use tracing::debug;

use crate::LangItem;
use crate::def::{CtorKind, DefKind, Res};
use crate::def_id::{DefId, LocalDefIdMap};
pub(crate) use crate::hir_id::{HirId, ItemLocalId, ItemLocalMap, OwnerId};
use crate::intravisit::{FnKind, VisitorExt};

#[derive(Debug, Copy, Clone, PartialEq, Eq, HashStable_Generic)]
pub enum LifetimeSource {
    /// E.g. `&Type`, `&'_ Type`, `&'a Type`, `&mut Type`, `&'_ mut Type`, `&'a mut Type`
    Reference,

    /// E.g. `ContainsLifetime`, `ContainsLifetime<'_>`, `ContainsLifetime<'a>`
    Path {
        /// - true for `ContainsLifetime<'_>`, `ContainsLifetime<'a>`,
        ///   `ContainsLifetime<'_, T>`, `ContainsLifetime<'a, T>`
        /// - false for `ContainsLifetime`
        with_angle_brackets: bool,
    },

    /// E.g. `impl Trait + '_`, `impl Trait + 'a`
    OutlivesBound,

    /// E.g. `impl Trait + use<'_>`, `impl Trait + use<'a>`
    PreciseCapturing,

    /// Other usages which have not yet been categorized. Feel free to
    /// add new sources that you find useful.
    ///
    /// Some non-exhaustive examples:
    /// - `where T: 'a`
    /// - `fn(_: dyn Trait + 'a)`
    Other,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, HashStable_Generic)]
pub enum LifetimeSyntax {
    /// E.g. `&Type`, `ContainsLifetime`
    Hidden,

    /// E.g. `&'_ Type`, `ContainsLifetime<'_>`, `impl Trait + '_`, `impl Trait + use<'_>`
    Anonymous,

    /// E.g. `&'a Type`, `ContainsLifetime<'a>`, `impl Trait + 'a`, `impl Trait + use<'a>`
    Named,
}

impl From<Ident> for LifetimeSyntax {
    fn from(ident: Ident) -> Self {
        let name = ident.name;

        if name == kw::Empty {
            unreachable!("A lifetime name should never be empty");
        } else if name == kw::UnderscoreLifetime {
            LifetimeSyntax::Anonymous
        } else {
            debug_assert!(name.as_str().starts_with('\''));
            LifetimeSyntax::Named
        }
    }
}

/// A lifetime. The valid field combinations are non-obvious and not all
/// combinations are possible. The following example shows some of
/// them. See also the comments on `LifetimeKind` and `LifetimeSource`.
///
/// ```
/// #[repr(C)]
/// struct S<'a>(&'a u32);       // res=Param, name='a, source=Reference, syntax=Named
/// unsafe extern "C" {
///     fn f1(s: S);             // res=Param, name='_, source=Path, syntax=Hidden
///     fn f2(s: S<'_>);         // res=Param, name='_, source=Path, syntax=Anonymous
///     fn f3<'a>(s: S<'a>);     // res=Param, name='a, source=Path, syntax=Named
/// }
///
/// struct St<'a> { x: &'a u32 } // res=Param, name='a, source=Reference, syntax=Named
/// fn f() {
///     _ = St { x: &0 };        // res=Infer, name='_, source=Path, syntax=Hidden
///     _ = St::<'_> { x: &0 };  // res=Infer, name='_, source=Path, syntax=Anonymous
/// }
///
/// struct Name<'a>(&'a str);    // res=Param,  name='a, source=Reference, syntax=Named
/// const A: Name = Name("a");   // res=Static, name='_, source=Path, syntax=Hidden
/// const B: &str = "";          // res=Static, name='_, source=Reference, syntax=Hidden
/// static C: &'_ str = "";      // res=Static, name='_, source=Reference, syntax=Anonymous
/// static D: &'static str = ""; // res=Static, name='static, source=Reference, syntax=Named
///
/// trait Tr {}
/// fn tr(_: Box<dyn Tr>) {}     // res=ImplicitObjectLifetimeDefault, name='_, source=Other, syntax=Hidden
///
/// fn capture_outlives<'a>() ->
///     impl FnOnce() + 'a       // res=Param, ident='a, source=OutlivesBound, syntax=Named
/// {
///     || {}
/// }
///
/// fn capture_precise<'a>() ->
///     impl FnOnce() + use<'a>  // res=Param, ident='a, source=PreciseCapturing, syntax=Named
/// {
///     || {}
/// }
///
/// // (commented out because these cases trigger errors)
/// // struct S1<'a>(&'a str);   // res=Param, name='a, source=Reference, syntax=Named
/// // struct S2(S1);            // res=Error, name='_, source=Path, syntax=Hidden
/// // struct S3(S1<'_>);        // res=Error, name='_, source=Path, syntax=Anonymous
/// // struct S4(S1<'a>);        // res=Error, name='a, source=Path, syntax=Named
/// ```
///
/// Some combinations that cannot occur are `LifetimeSyntax::Hidden` with
/// `LifetimeSource::OutlivesBound` or `LifetimeSource::PreciseCapturing`
/// — there's no way to "elide" these lifetimes.
#[derive(Debug, Copy, Clone, HashStable_Generic)]
pub struct Lifetime {
    #[stable_hasher(ignore)]
    pub hir_id: HirId,

    /// Either a named lifetime definition (e.g. `'a`, `'static`) or an
    /// anonymous lifetime (`'_`, either explicitly written, or inserted for
    /// things like `&type`).
    pub ident: Ident,

    /// Semantics of this lifetime.
    pub kind: LifetimeKind,

    /// The context in which the lifetime occurred. See `Lifetime::suggestion`
    /// for example use.
    pub source: LifetimeSource,

    /// The syntax that the user used to declare this lifetime. See
    /// `Lifetime::suggestion` for example use.
    pub syntax: LifetimeSyntax,
}

#[derive(Debug, Copy, Clone, HashStable_Generic)]
pub enum ParamName {
    /// Some user-given name like `T` or `'x`.
    Plain(Ident),

    /// Indicates an illegal name was given and an error has been
    /// reported (so we should squelch other derived errors).
    ///
    /// Occurs when, e.g., `'_` is used in the wrong place, or a
    /// lifetime name is duplicated.
    Error(Ident),

    /// Synthetic name generated when user elided a lifetime in an impl header.
    ///
    /// E.g., the lifetimes in cases like these:
    /// ```ignore (fragment)
    /// impl Foo for &u32
    /// impl Foo<'_> for u32
    /// ```
    /// in that case, we rewrite to
    /// ```ignore (fragment)
    /// impl<'f> Foo for &'f u32
    /// impl<'f> Foo<'f> for u32
    /// ```
    /// where `'f` is something like `Fresh(0)`. The indices are
    /// unique per impl, but not necessarily continuous.
    Fresh,
}

impl ParamName {
    pub fn ident(&self) -> Ident {
        match *self {
            ParamName::Plain(ident) | ParamName::Error(ident) => ident,
            ParamName::Fresh => Ident::with_dummy_span(kw::UnderscoreLifetime),
        }
    }
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, HashStable_Generic)]
pub enum LifetimeKind {
    /// User-given names or fresh (synthetic) names.
    Param(LocalDefId),

    /// Implicit lifetime in a context like `dyn Foo`. This is
    /// distinguished from implicit lifetimes elsewhere because the
    /// lifetime that they default to must appear elsewhere within the
    /// enclosing type. This means that, in an `impl Trait` context, we
    /// don't have to create a parameter for them. That is, `impl
    /// Trait<Item = &u32>` expands to an opaque type like `type
    /// Foo<'a> = impl Trait<Item = &'a u32>`, but `impl Trait<item =
    /// dyn Bar>` expands to `type Foo = impl Trait<Item = dyn Bar +
    /// 'static>`. The latter uses `ImplicitObjectLifetimeDefault` so
    /// that surrounding code knows not to create a lifetime
    /// parameter.
    ImplicitObjectLifetimeDefault,

    /// Indicates an error during lowering (usually `'_` in wrong place)
    /// that was already reported.
    Error,

    /// User wrote an anonymous lifetime, either `'_` or nothing (which gets
    /// converted to `'_`). The semantics of this lifetime should be inferred
    /// by typechecking code.
    Infer,

    /// User wrote `'static` or nothing (which gets converted to `'_`).
    Static,
}

impl LifetimeKind {
    fn is_elided(&self) -> bool {
        match self {
            LifetimeKind::ImplicitObjectLifetimeDefault | LifetimeKind::Infer => true,

            // It might seem surprising that `Fresh` counts as not *elided*
            // -- but this is because, as far as the code in the compiler is
            // concerned -- `Fresh` variants act equivalently to "some fresh name".
            // They correspond to early-bound regions on an impl, in other words.
            LifetimeKind::Error | LifetimeKind::Param(..) | LifetimeKind::Static => false,
        }
    }
}

impl fmt::Display for Lifetime {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.ident.name.fmt(f)
    }
}

impl Lifetime {
    pub fn new(
        hir_id: HirId,
        ident: Ident,
        kind: LifetimeKind,
        source: LifetimeSource,
        syntax: LifetimeSyntax,
    ) -> Lifetime {
        let lifetime = Lifetime { hir_id, ident, kind, source, syntax };

        // Sanity check: elided lifetimes form a strict subset of anonymous lifetimes.
        #[cfg(debug_assertions)]
        match (lifetime.is_elided(), lifetime.is_anonymous()) {
            (false, false) => {} // e.g. `'a`
            (false, true) => {}  // e.g. explicit `'_`
            (true, true) => {}   // e.g. `&x`
            (true, false) => panic!("bad Lifetime"),
        }

        lifetime
    }

    pub fn is_elided(&self) -> bool {
        self.kind.is_elided()
    }

    pub fn is_anonymous(&self) -> bool {
        self.ident.name == kw::UnderscoreLifetime
    }

    pub fn is_syntactically_hidden(&self) -> bool {
        matches!(self.syntax, LifetimeSyntax::Hidden)
    }

    pub fn is_syntactically_anonymous(&self) -> bool {
        matches!(self.syntax, LifetimeSyntax::Anonymous)
    }

    pub fn is_static(&self) -> bool {
        self.kind == LifetimeKind::Static
    }

    pub fn suggestion(&self, new_lifetime: &str) -> (Span, String) {
        use LifetimeSource::*;
        use LifetimeSyntax::*;

        debug_assert!(new_lifetime.starts_with('\''));

        match (self.syntax, self.source) {
            // The user wrote `'a` or `'_`.
            (Named | Anonymous, _) => (self.ident.span, format!("{new_lifetime}")),

            // The user wrote `Path<T>`, and omitted the `'_,`.
            (Hidden, Path { with_angle_brackets: true }) => {
                (self.ident.span, format!("{new_lifetime}, "))
            }

            // The user wrote `Path` and omitted the `<'_>`.
            (Hidden, Path { with_angle_brackets: false }) => {
                (self.ident.span.shrink_to_hi(), format!("<{new_lifetime}>"))
            }

            // The user wrote `&type` or `&mut type`.
            (Hidden, Reference) => (self.ident.span, format!("{new_lifetime} ")),

            (Hidden, source) => {
                unreachable!("can't suggest for a hidden lifetime of {source:?}")
            }
        }
    }
}

/// A `Path` is essentially Rust's notion of a name; for instance,
/// `std::cmp::PartialEq`. It's represented as a sequence of identifiers,
/// along with a bunch of supporting information.
#[derive(Debug, Clone, Copy, HashStable_Generic)]
pub struct Path<'hir, R = Res> {
    pub span: Span,
    /// The resolution for the path.
    pub res: R,
    /// The segments in the path: the things separated by `::`.
    pub segments: &'hir [PathSegment<'hir>],
}

/// Up to three resolutions for type, value and macro namespaces.
pub type UsePath<'hir> = Path<'hir, SmallVec<[Res; 3]>>;

impl Path<'_> {
    pub fn is_global(&self) -> bool {
        self.segments.first().is_some_and(|segment| segment.ident.name == kw::PathRoot)
    }
}

/// A segment of a path: an identifier, an optional lifetime, and a set of
/// types.
#[derive(Debug, Clone, Copy, HashStable_Generic)]
pub struct PathSegment<'hir> {
    /// The identifier portion of this path segment.
    pub ident: Ident,
    #[stable_hasher(ignore)]
    pub hir_id: HirId,
    pub res: Res,

    /// Type/lifetime parameters attached to this path. They come in
    /// two flavors: `Path<A,B,C>` and `Path(A,B) -> C`. Note that
    /// this is more than just simple syntactic sugar; the use of
    /// parens affects the region binding rules, so we preserve the
    /// distinction.
    pub args: Option<&'hir GenericArgs<'hir>>,

    /// Whether to infer remaining type parameters, if any.
    /// This only applies to expression and pattern paths, and
    /// out of those only the segments with no type parameters
    /// to begin with, e.g., `Vec::new` is `<Vec<..>>::new::<..>`.
    pub infer_args: bool,
}

impl<'hir> PathSegment<'hir> {
    /// Converts an identifier to the corresponding segment.
    pub fn new(ident: Ident, hir_id: HirId, res: Res) -> PathSegment<'hir> {
        PathSegment { ident, hir_id, res, infer_args: true, args: None }
    }

    pub fn invalid() -> Self {
        Self::new(Ident::dummy(), HirId::INVALID, Res::Err)
    }

    pub fn args(&self) -> &GenericArgs<'hir> {
        if let Some(ref args) = self.args {
            args
        } else {
            const DUMMY: &GenericArgs<'_> = &GenericArgs::none();
            DUMMY
        }
    }
}

/// A constant that enters the type system, used for arguments to const generics (e.g. array lengths).
///
/// These are distinct from [`AnonConst`] as anon consts in the type system are not allowed
/// to use any generic parameters, therefore we must represent `N` differently. Additionally
/// future designs for supporting generic parameters in const arguments will likely not use
/// an anon const based design.
///
/// So, `ConstArg` (specifically, [`ConstArgKind`]) distinguishes between const args
/// that are [just paths](ConstArgKind::Path) (currently just bare const params)
/// versus const args that are literals or have arbitrary computations (e.g., `{ 1 + 3 }`).
///
/// The `Unambig` generic parameter represents whether the position this const is from is
/// unambiguously a const or ambiguous as to whether it is a type or a const. When in an
/// ambiguous context the parameter is instantiated with an uninhabited type making the
/// [`ConstArgKind::Infer`] variant unusable and [`GenericArg::Infer`] is used instead.
#[derive(Clone, Copy, Debug, HashStable_Generic)]
#[repr(C)]
pub struct ConstArg<'hir, Unambig = ()> {
    #[stable_hasher(ignore)]
    pub hir_id: HirId,
    pub kind: ConstArgKind<'hir, Unambig>,
}

impl<'hir> ConstArg<'hir, AmbigArg> {
    /// Converts a `ConstArg` in an ambiguous position to one in an unambiguous position.
    ///
    /// Functions accepting an unambiguous consts may expect the [`ConstArgKind::Infer`] variant
    /// to be used. Care should be taken to separately handle infer consts when calling this
    /// function as it cannot be handled by downstream code making use of the returned const.
    ///
    /// In practice this may mean overriding the [`Visitor::visit_infer`][visit_infer] method on hir visitors, or
    /// specifically matching on [`GenericArg::Infer`] when handling generic arguments.
    ///
    /// [visit_infer]: [rustc_hir::intravisit::Visitor::visit_infer]
    pub fn as_unambig_ct(&self) -> &ConstArg<'hir> {
        // SAFETY: `ConstArg` is `repr(C)` and `ConstArgKind` is marked `repr(u8)` so that the
        // layout is the same across different ZST type arguments.
        let ptr = self as *const ConstArg<'hir, AmbigArg> as *const ConstArg<'hir, ()>;
        unsafe { &*ptr }
    }
}

impl<'hir> ConstArg<'hir> {
    /// Converts a `ConstArg` in an unambigous position to one in an ambiguous position. This is
    /// fallible as the [`ConstArgKind::Infer`] variant is not present in ambiguous positions.
    ///
    /// Functions accepting ambiguous consts will not handle the [`ConstArgKind::Infer`] variant, if
    /// infer consts are relevant to you then care should be taken to handle them separately.
    pub fn try_as_ambig_ct(&self) -> Option<&ConstArg<'hir, AmbigArg>> {
        if let ConstArgKind::Infer(_, ()) = self.kind {
            return None;
        }

        // SAFETY: `ConstArg` is `repr(C)` and `ConstArgKind` is marked `repr(u8)` so that the layout is
        // the same across different ZST type arguments. We also asserted that the `self` is
        // not a `ConstArgKind::Infer` so there is no risk of transmuting a `()` to `AmbigArg`.
        let ptr = self as *const ConstArg<'hir> as *const ConstArg<'hir, AmbigArg>;
        Some(unsafe { &*ptr })
    }
}

impl<'hir, Unambig> ConstArg<'hir, Unambig> {
    pub fn anon_const_hir_id(&self) -> Option<HirId> {
        match self.kind {
            ConstArgKind::Anon(ac) => Some(ac.hir_id),
            _ => None,
        }
    }

    pub fn span(&self) -> Span {
        match self.kind {
            ConstArgKind::Path(path) => path.span(),
            ConstArgKind::Anon(anon) => anon.span,
            ConstArgKind::Infer(span, _) => span,
        }
    }
}

/// See [`ConstArg`].
#[derive(Clone, Copy, Debug, HashStable_Generic)]
#[repr(u8, C)]
pub enum ConstArgKind<'hir, Unambig = ()> {
    /// **Note:** Currently this is only used for bare const params
    /// (`N` where `fn foo<const N: usize>(...)`),
    /// not paths to any const (`N` where `const N: usize = ...`).
    ///
    /// However, in the future, we'll be using it for all of those.
    Path(QPath<'hir>),
    Anon(&'hir AnonConst),
    /// This variant is not always used to represent inference consts, sometimes
    /// [`GenericArg::Infer`] is used instead.
    Infer(Span, Unambig),
}

#[derive(Clone, Copy, Debug, HashStable_Generic)]
pub struct InferArg {
    #[stable_hasher(ignore)]
    pub hir_id: HirId,
    pub span: Span,
}

impl InferArg {
    pub fn to_ty(&self) -> Ty<'static> {
        Ty { kind: TyKind::Infer(()), span: self.span, hir_id: self.hir_id }
    }
}

#[derive(Debug, Clone, Copy, HashStable_Generic)]
pub enum GenericArg<'hir> {
    Lifetime(&'hir Lifetime),
    Type(&'hir Ty<'hir, AmbigArg>),
    Const(&'hir ConstArg<'hir, AmbigArg>),
    /// Inference variables in [`GenericArg`] are always represnted by
    /// `GenericArg::Infer` instead of the `Infer` variants on [`TyKind`] and
    /// [`ConstArgKind`] as it is not clear until hir ty lowering whether a
    /// `_` argument is a type or const argument.
    ///
    /// However, some builtin types' generic arguments are represented by [`TyKind`]
    /// without a [`GenericArg`], instead directly storing a [`Ty`] or [`ConstArg`]. In
    /// such cases they *are* represented by the `Infer` variants on [`TyKind`] and
    /// [`ConstArgKind`] as it is not ambiguous whether the argument is a type or const.
    Infer(InferArg),
}

impl GenericArg<'_> {
    pub fn span(&self) -> Span {
        match self {
            GenericArg::Lifetime(l) => l.ident.span,
            GenericArg::Type(t) => t.span,
            GenericArg::Const(c) => c.span(),
            GenericArg::Infer(i) => i.span,
        }
    }

    pub fn hir_id(&self) -> HirId {
        match self {
            GenericArg::Lifetime(l) => l.hir_id,
            GenericArg::Type(t) => t.hir_id,
            GenericArg::Const(c) => c.hir_id,
            GenericArg::Infer(i) => i.hir_id,
        }
    }

    pub fn descr(&self) -> &'static str {
        match self {
            GenericArg::Lifetime(_) => "lifetime",
            GenericArg::Type(_) => "type",
            GenericArg::Const(_) => "constant",
            GenericArg::Infer(_) => "placeholder",
        }
    }

    pub fn to_ord(&self) -> ast::ParamKindOrd {
        match self {
            GenericArg::Lifetime(_) => ast::ParamKindOrd::Lifetime,
            GenericArg::Type(_) | GenericArg::Const(_) | GenericArg::Infer(_) => {
                ast::ParamKindOrd::TypeOrConst
            }
        }
    }

    pub fn is_ty_or_const(&self) -> bool {
        match self {
            GenericArg::Lifetime(_) => false,
            GenericArg::Type(_) | GenericArg::Const(_) | GenericArg::Infer(_) => true,
        }
    }
}

/// The generic arguments and associated item constraints of a path segment.
#[derive(Debug, Clone, Copy, HashStable_Generic)]
pub struct GenericArgs<'hir> {
    /// The generic arguments for this path segment.
    pub args: &'hir [GenericArg<'hir>],
    /// The associated item constraints for this path segment.
    pub constraints: &'hir [AssocItemConstraint<'hir>],
    /// Whether the arguments were written in parenthesized form (e.g., `Fn(T) -> U`).
    ///
    /// This is required mostly for pretty-printing and diagnostics,
    /// but also for changing lifetime elision rules to be "function-like".
    pub parenthesized: GenericArgsParentheses,
    /// The span encompassing the arguments, constraints and the surrounding brackets (`<>` or `()`).
    ///
    /// For example:
    ///
    /// ```ignore (illustrative)
    ///       Foo<A, B, AssocTy = D>           Fn(T, U, V) -> W
    ///          ^^^^^^^^^^^^^^^^^^^             ^^^^^^^^^
    /// ```
    ///
    /// Note that this may be:
    /// - empty, if there are no generic brackets (but there may be hidden lifetimes)
    /// - dummy, if this was generated during desugaring
    pub span_ext: Span,
}

impl<'hir> GenericArgs<'hir> {
    pub const fn none() -> Self {
        Self {
            args: &[],
            constraints: &[],
            parenthesized: GenericArgsParentheses::No,
            span_ext: DUMMY_SP,
        }
    }

    /// Obtain the list of input types and the output type if the generic arguments are parenthesized.
    ///
    /// Returns the `Ty0, Ty1, ...` and the `RetTy` in `Trait(Ty0, Ty1, ...) -> RetTy`.
    /// Panics if the parenthesized arguments have an incorrect form (this shouldn't happen).
    pub fn paren_sugar_inputs_output(&self) -> Option<(&[Ty<'hir>], &Ty<'hir>)> {
        if self.parenthesized != GenericArgsParentheses::ParenSugar {
            return None;
        }

        let inputs = self
            .args
            .iter()
            .find_map(|arg| {
                let GenericArg::Type(ty) = arg else { return None };
                let TyKind::Tup(tys) = &ty.kind else { return None };
                Some(tys)
            })
            .unwrap();

        Some((inputs, self.paren_sugar_output_inner()))
    }

    /// Obtain the output type if the generic arguments are parenthesized.
    ///
    /// Returns the `RetTy` in `Trait(Ty0, Ty1, ...) -> RetTy`.
    /// Panics if the parenthesized arguments have an incorrect form (this shouldn't happen).
    pub fn paren_sugar_output(&self) -> Option<&Ty<'hir>> {
        (self.parenthesized == GenericArgsParentheses::ParenSugar)
            .then(|| self.paren_sugar_output_inner())
    }

    fn paren_sugar_output_inner(&self) -> &Ty<'hir> {
        let [constraint] = self.constraints.try_into().unwrap();
        debug_assert_eq!(constraint.ident.name, sym::Output);
        constraint.ty().unwrap()
    }

    pub fn has_err(&self) -> Option<ErrorGuaranteed> {
        self.args
            .iter()
            .find_map(|arg| {
                let GenericArg::Type(ty) = arg else { return None };
                let TyKind::Err(guar) = ty.kind else { return None };
                Some(guar)
            })
            .or_else(|| {
                self.constraints.iter().find_map(|constraint| {
                    let TyKind::Err(guar) = constraint.ty()?.kind else { return None };
                    Some(guar)
                })
            })
    }

    #[inline]
    pub fn num_lifetime_params(&self) -> usize {
        self.args.iter().filter(|arg| matches!(arg, GenericArg::Lifetime(_))).count()
    }

    #[inline]
    pub fn has_lifetime_params(&self) -> bool {
        self.args.iter().any(|arg| matches!(arg, GenericArg::Lifetime(_)))
    }

    #[inline]
    /// This function returns the number of type and const generic params.
    /// It should only be used for diagnostics.
    pub fn num_generic_params(&self) -> usize {
        self.args.iter().filter(|arg| !matches!(arg, GenericArg::Lifetime(_))).count()
    }

    /// The span encompassing the arguments and constraints[^1] inside the surrounding brackets.
    ///
    /// Returns `None` if the span is empty (i.e., no brackets) or dummy.
    ///
    /// [^1]: Unless of the form `-> Ty` (see [`GenericArgsParentheses`]).
    pub fn span(&self) -> Option<Span> {
        let span_ext = self.span_ext()?;
        Some(span_ext.with_lo(span_ext.lo() + BytePos(1)).with_hi(span_ext.hi() - BytePos(1)))
    }

    /// Returns span encompassing arguments and their surrounding `<>` or `()`
    pub fn span_ext(&self) -> Option<Span> {
        Some(self.span_ext).filter(|span| !span.is_empty())
    }

    pub fn is_empty(&self) -> bool {
        self.args.is_empty()
    }
}

#[derive(Copy, Clone, PartialEq, Eq, Debug, HashStable_Generic)]
pub enum GenericArgsParentheses {
    No,
    /// Bounds for `feature(return_type_notation)`, like `T: Trait<method(..): Send>`,
    /// where the args are explicitly elided with `..`
    ReturnTypeNotation,
    /// parenthesized function-family traits, like `T: Fn(u32) -> i32`
    ParenSugar,
}

/// The modifiers on a trait bound.
#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable_Generic)]
pub struct TraitBoundModifiers {
    pub constness: BoundConstness,
    pub polarity: BoundPolarity,
}

impl TraitBoundModifiers {
    pub const NONE: Self =
        TraitBoundModifiers { constness: BoundConstness::Never, polarity: BoundPolarity::Positive };
}

#[derive(Clone, Copy, Debug, HashStable_Generic)]
pub enum GenericBound<'hir> {
    Trait(PolyTraitRef<'hir>),
    Outlives(&'hir Lifetime),
    Use(&'hir [PreciseCapturingArg<'hir>], Span),
}

impl GenericBound<'_> {
    pub fn trait_ref(&self) -> Option<&TraitRef<'_>> {
        match self {
            GenericBound::Trait(data) => Some(&data.trait_ref),
            _ => None,
        }
    }

    pub fn span(&self) -> Span {
        match self {
            GenericBound::Trait(t, ..) => t.span,
            GenericBound::Outlives(l) => l.ident.span,
            GenericBound::Use(_, span) => *span,
        }
    }
}

pub type GenericBounds<'hir> = &'hir [GenericBound<'hir>];

#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, HashStable_Generic, Debug)]
pub enum MissingLifetimeKind {
    /// An explicit `'_`.
    Underscore,
    /// An elided lifetime `&' ty`.
    Ampersand,
    /// An elided lifetime in brackets with written brackets.
    Comma,
    /// An elided lifetime with elided brackets.
    Brackets,
}

#[derive(Copy, Clone, Debug, HashStable_Generic)]
pub enum LifetimeParamKind {
    // Indicates that the lifetime definition was explicitly declared (e.g., in
    // `fn foo<'a>(x: &'a u8) -> &'a u8 { x }`).
    Explicit,

    // Indication that the lifetime was elided (e.g., in both cases in
    // `fn foo(x: &u8) -> &'_ u8 { x }`).
    Elided(MissingLifetimeKind),

    // Indication that the lifetime name was somehow in error.
    Error,
}

#[derive(Debug, Clone, Copy, HashStable_Generic)]
pub enum GenericParamKind<'hir> {
    /// A lifetime definition (e.g., `'a: 'b + 'c + 'd`).
    Lifetime {
        kind: LifetimeParamKind,
    },
    Type {
        default: Option<&'hir Ty<'hir>>,
        synthetic: bool,
    },
    Const {
        ty: &'hir Ty<'hir>,
        /// Optional default value for the const generic param
        default: Option<&'hir ConstArg<'hir>>,
        synthetic: bool,
    },
}

#[derive(Debug, Clone, Copy, HashStable_Generic)]
pub struct GenericParam<'hir> {
    #[stable_hasher(ignore)]
    pub hir_id: HirId,
    pub def_id: LocalDefId,
    pub name: ParamName,
    pub span: Span,
    pub pure_wrt_drop: bool,
    pub kind: GenericParamKind<'hir>,
    pub colon_span: Option<Span>,
    pub source: GenericParamSource,
}

impl<'hir> GenericParam<'hir> {
    /// Synthetic type-parameters are inserted after normal ones.
    /// In order for normal parameters to be able to refer to synthetic ones,
    /// scans them first.
    pub fn is_impl_trait(&self) -> bool {
        matches!(self.kind, GenericParamKind::Type { synthetic: true, .. })
    }

    /// This can happen for `async fn`, e.g. `async fn f<'_>(&'_ self)`.
    ///
    /// See `lifetime_to_generic_param` in `rustc_ast_lowering` for more information.
    pub fn is_elided_lifetime(&self) -> bool {
        matches!(self.kind, GenericParamKind::Lifetime { kind: LifetimeParamKind::Elided(_) })
    }
}

/// Records where the generic parameter originated from.
///
/// This can either be from an item's generics, in which case it's typically
/// early-bound (but can be a late-bound lifetime in functions, for example),
/// or from a `for<...>` binder, in which case it's late-bound (and notably,
/// does not show up in the parent item's generics).
#[derive(Debug, Clone, Copy, HashStable_Generic)]
pub enum GenericParamSource {
    // Early or late-bound parameters defined on an item
    Generics,
    // Late-bound parameters defined via a `for<...>`
    Binder,
}

#[derive(Default)]
pub struct GenericParamCount {
    pub lifetimes: usize,
    pub types: usize,
    pub consts: usize,
    pub infer: usize,
}

/// Represents lifetimes and type parameters attached to a declaration
/// of a function, enum, trait, etc.
#[derive(Debug, Clone, Copy, HashStable_Generic)]
pub struct Generics<'hir> {
    pub params: &'hir [GenericParam<'hir>],
    pub predicates: &'hir [WherePredicate<'hir>],
    pub has_where_clause_predicates: bool,
    pub where_clause_span: Span,
    pub span: Span,
}

impl<'hir> Generics<'hir> {
    pub const fn empty() -> &'hir Generics<'hir> {
        const NOPE: Generics<'_> = Generics {
            params: &[],
            predicates: &[],
            has_where_clause_predicates: false,
            where_clause_span: DUMMY_SP,
            span: DUMMY_SP,
        };
        &NOPE
    }

    pub fn get_named(&self, name: Symbol) -> Option<&GenericParam<'hir>> {
        self.params.iter().find(|&param| name == param.name.ident().name)
    }

    /// If there are generic parameters, return where to introduce a new one.
    pub fn span_for_lifetime_suggestion(&self) -> Option<Span> {
        if let Some(first) = self.params.first()
            && self.span.contains(first.span)
        {
            // `fn foo<A>(t: impl Trait)`
            //         ^ suggest `'a, ` here
            Some(first.span.shrink_to_lo())
        } else {
            None
        }
    }

    /// If there are generic parameters, return where to introduce a new one.
    pub fn span_for_param_suggestion(&self) -> Option<Span> {
        self.params.iter().any(|p| self.span.contains(p.span)).then(|| {
            // `fn foo<A>(t: impl Trait)`
            //          ^ suggest `, T: Trait` here
            self.span.with_lo(self.span.hi() - BytePos(1)).shrink_to_lo()
        })
    }

    /// `Span` where further predicates would be suggested, accounting for trailing commas, like
    ///  in `fn foo<T>(t: T) where T: Foo,` so we don't suggest two trailing commas.
    pub fn tail_span_for_predicate_suggestion(&self) -> Span {
        let end = self.where_clause_span.shrink_to_hi();
        if self.has_where_clause_predicates {
            self.predicates
                .iter()
                .rfind(|&p| p.kind.in_where_clause())
                .map_or(end, |p| p.span)
                .shrink_to_hi()
                .to(end)
        } else {
            end
        }
    }

    pub fn add_where_or_trailing_comma(&self) -> &'static str {
        if self.has_where_clause_predicates {
            ","
        } else if self.where_clause_span.is_empty() {
            " where"
        } else {
            // No where clause predicates, but we have `where` token
            ""
        }
    }

    pub fn bounds_for_param(
        &self,
        param_def_id: LocalDefId,
    ) -> impl Iterator<Item = &WhereBoundPredicate<'hir>> {
        self.predicates.iter().filter_map(move |pred| match pred.kind {
            WherePredicateKind::BoundPredicate(bp)
                if bp.is_param_bound(param_def_id.to_def_id()) =>
            {
                Some(bp)
            }
            _ => None,
        })
    }

    pub fn outlives_for_param(
        &self,
        param_def_id: LocalDefId,
    ) -> impl Iterator<Item = &WhereRegionPredicate<'_>> {
        self.predicates.iter().filter_map(move |pred| match pred.kind {
            WherePredicateKind::RegionPredicate(rp) if rp.is_param_bound(param_def_id) => Some(rp),
            _ => None,
        })
    }

    /// Returns a suggestable empty span right after the "final" bound of the generic parameter.
    ///
    /// If that bound needs to be wrapped in parentheses to avoid ambiguity with
    /// subsequent bounds, it also returns an empty span for an open parenthesis
    /// as the second component.
    ///
    /// E.g., adding `+ 'static` after `Fn() -> dyn Future<Output = ()>` or
    /// `Fn() -> &'static dyn Debug` requires parentheses:
    /// `Fn() -> (dyn Future<Output = ()>) + 'static` and
    /// `Fn() -> &'static (dyn Debug) + 'static`, respectively.
    pub fn bounds_span_for_suggestions(
        &self,
        param_def_id: LocalDefId,
    ) -> Option<(Span, Option<Span>)> {
        self.bounds_for_param(param_def_id).flat_map(|bp| bp.bounds.iter().rev()).find_map(
            |bound| {
                let span_for_parentheses = if let Some(trait_ref) = bound.trait_ref()
                    && let [.., segment] = trait_ref.path.segments
                    && let Some(ret_ty) = segment.args().paren_sugar_output()
                    && let ret_ty = ret_ty.peel_refs()
                    && let TyKind::TraitObject(_, tagged_ptr) = ret_ty.kind
                    && let TraitObjectSyntax::Dyn | TraitObjectSyntax::DynStar = tagged_ptr.tag()
                    && ret_ty.span.can_be_used_for_suggestions()
                {
                    Some(ret_ty.span)
                } else {
                    None
                };

                span_for_parentheses.map_or_else(
                    || {
                        // We include bounds that come from a `#[derive(_)]` but point at the user's code,
                        // as we use this method to get a span appropriate for suggestions.
                        let bs = bound.span();
                        bs.can_be_used_for_suggestions().then(|| (bs.shrink_to_hi(), None))
                    },
                    |span| Some((span.shrink_to_hi(), Some(span.shrink_to_lo()))),
                )
            },
        )
    }

    pub fn span_for_predicate_removal(&self, pos: usize) -> Span {
        let predicate = &self.predicates[pos];
        let span = predicate.span;

        if !predicate.kind.in_where_clause() {
            // <T: ?Sized, U>
            //   ^^^^^^^^
            return span;
        }

        // We need to find out which comma to remove.
        if pos < self.predicates.len() - 1 {
            let next_pred = &self.predicates[pos + 1];
            if next_pred.kind.in_where_clause() {
                // where T: ?Sized, Foo: Bar,
                //       ^^^^^^^^^^^
                return span.until(next_pred.span);
            }
        }

        if pos > 0 {
            let prev_pred = &self.predicates[pos - 1];
            if prev_pred.kind.in_where_clause() {
                // where Foo: Bar, T: ?Sized,
                //               ^^^^^^^^^^^
                return prev_pred.span.shrink_to_hi().to(span);
            }
        }