rustc_type_ir/

predicate.rs

use std::hash::Hash;
use std::{fmt, iter};

use derive_where::derive_where;
#[cfg(feature = "nightly")]
use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable, HashStable_NoContext};
use rustc_type_ir_macros::{
    GenericTypeVisitable, Lift_Generic, TypeFoldable_Generic, TypeVisitable_Generic,
};

use crate::inherent::*;
use crate::lift::Lift;
use crate::upcast::{Upcast, UpcastFrom};
use crate::visit::TypeVisitableExt as _;
use crate::{self as ty, AliasTyKind, Interner};

/// `A: 'region`
#[derive_where(Clone, Hash, PartialEq, Debug; I: Interner, A)]
#[derive_where(Copy; I: Interner, A: Copy)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct OutlivesPredicate<I: Interner, A>(pub A, pub I::Region);

impl<I: Interner, A: Eq> Eq for OutlivesPredicate<I, A> {}

// FIXME: We manually derive `Lift` because the `derive(Lift_Generic)` doesn't
// understand how to turn `A` to `A::Lifted` in the output `type Lifted`.
impl<I: Interner, U: Interner, A> Lift<U> for OutlivesPredicate<I, A>
where
    A: Lift<U>,
    I::Region: Lift<U, Lifted = U::Region>,
{
    type Lifted = OutlivesPredicate<U, A::Lifted>;

    fn lift_to_interner(self, cx: U) -> Option<Self::Lifted> {
        Some(OutlivesPredicate(self.0.lift_to_interner(cx)?, self.1.lift_to_interner(cx)?))
    }
}

/// `'a == 'b`.
/// For the rationale behind having this instead of a pair of bidirectional
/// `'a: 'b` and `'b: 'a`, see
/// [this discusstion on Zulip](https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/A.20question.20on.20.23251/near/584167074).
#[derive_where(Clone, Copy, Hash, PartialEq, Eq, Debug; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct RegionEqPredicate<I: Interner>(pub I::Region, pub I::Region);

impl<I: Interner> RegionEqPredicate<I> {
    /// Decompose `'a == 'b` into `['a: 'b, 'b: 'a]`
    pub fn into_bidirectional_outlives(self) -> [OutlivesPredicate<I, I::GenericArg>; 2] {
        [OutlivesPredicate(self.0.into(), self.1), OutlivesPredicate(self.1.into(), self.0)]
    }
}

#[derive_where(Clone, Copy, Hash, PartialEq, Eq, Debug; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub enum RegionConstraint<I: Interner> {
    Outlives(OutlivesPredicate<I, I::GenericArg>),
    Eq(RegionEqPredicate<I>),
}

impl<I: Interner> From<OutlivesPredicate<I, I::GenericArg>> for RegionConstraint<I> {
    fn from(value: OutlivesPredicate<I, I::GenericArg>) -> Self {
        RegionConstraint::Outlives(value)
    }
}

impl<I: Interner> From<RegionEqPredicate<I>> for RegionConstraint<I> {
    fn from(value: RegionEqPredicate<I>) -> Self {
        RegionConstraint::Eq(value)
    }
}

impl<I: Interner> RegionConstraint<I> {
    /// Whether the given constraint is either `'a: 'a` or `'a == 'a`.
    pub fn is_trivial(self) -> bool {
        match self {
            RegionConstraint::Outlives(outlives) => {
                outlives.0.as_region().is_some_and(|re| re == outlives.1)
            }
            RegionConstraint::Eq(eq) => eq.0 == eq.1,
        }
    }

    /// If `self` is an eq constraint, iterate through its decomposed bidirectional outlives
    /// bounds and if not, just iterate once for the outlives bound itself.
    pub fn iter_outlives(self) -> impl Iterator<Item = OutlivesPredicate<I, I::GenericArg>> {
        match self {
            RegionConstraint::Outlives(outlives) => iter::once(outlives).chain(None),
            RegionConstraint::Eq(eq) => {
                let [outlives1, outlives2] = eq.into_bidirectional_outlives();
                iter::once(outlives1).chain(Some(outlives2))
            }
        }
    }
}

/// A complete reference to a trait.
///
/// These take numerous guises in syntax,
/// but perhaps the most recognizable form is in a where-clause:
/// ```ignore (illustrative)
/// T: Foo<U>
/// ```
/// This would be represented by a trait-reference where the `DefId` is the
/// `DefId` for the trait `Foo` and the args define `T` as parameter 0,
/// and `U` as parameter 1.
///
/// Trait references also appear in object types like `Foo<U>`, but in
/// that case the `Self` parameter is absent from the generic parameters.
#[derive_where(Clone, Copy, Hash, PartialEq; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct TraitRef<I: Interner> {
    pub def_id: I::TraitId,
    pub args: I::GenericArgs,
    /// This field exists to prevent the creation of `TraitRef` without
    /// calling [`TraitRef::new_from_args`].
    _use_trait_ref_new_instead: (),
}

impl<I: Interner> Eq for TraitRef<I> {}

impl<I: Interner> TraitRef<I> {
    pub fn new_from_args(interner: I, trait_def_id: I::TraitId, args: I::GenericArgs) -> Self {
        interner.debug_assert_args_compatible(trait_def_id.into(), args);
        Self { def_id: trait_def_id, args, _use_trait_ref_new_instead: () }
    }

    pub fn new(
        interner: I,
        trait_def_id: I::TraitId,
        args: impl IntoIterator<Item: Into<I::GenericArg>>,
    ) -> Self {
        let args = interner.mk_args_from_iter(args.into_iter().map(Into::into));
        Self::new_from_args(interner, trait_def_id, args)
    }

    pub fn from_assoc(interner: I, trait_id: I::TraitId, args: I::GenericArgs) -> TraitRef<I> {
        let generics = interner.generics_of(trait_id.into());
        TraitRef::new(interner, trait_id, args.iter().take(generics.count()))
    }

    /// Returns a `TraitRef` of the form `P0: Foo<P1..Pn>` where `Pi`
    /// are the parameters defined on trait.
    pub fn identity(interner: I, def_id: I::TraitId) -> TraitRef<I> {
        TraitRef::new_from_args(
            interner,
            def_id,
            I::GenericArgs::identity_for_item(interner, def_id.into()),
        )
    }

    pub fn with_replaced_self_ty(self, interner: I, self_ty: I::Ty) -> Self {
        TraitRef::new(
            interner,
            self.def_id,
            [self_ty.into()].into_iter().chain(self.args.iter().skip(1)),
        )
    }

    #[inline]
    pub fn self_ty(&self) -> I::Ty {
        self.args.type_at(0)
    }
}

impl<I: Interner> ty::Binder<I, TraitRef<I>> {
    pub fn self_ty(&self) -> ty::Binder<I, I::Ty> {
        self.map_bound_ref(|tr| tr.self_ty())
    }

    pub fn def_id(&self) -> I::TraitId {
        self.skip_binder().def_id
    }

    pub fn to_host_effect_clause(self, cx: I, constness: BoundConstness) -> I::Clause {
        self.map_bound(|trait_ref| {
            ty::ClauseKind::HostEffect(HostEffectPredicate { trait_ref, constness })
        })
        .upcast(cx)
    }
}

#[derive_where(Clone, Copy, Hash, PartialEq; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct TraitPredicate<I: Interner> {
    pub trait_ref: TraitRef<I>,

    /// If polarity is Positive: we are proving that the trait is implemented.
    ///
    /// If polarity is Negative: we are proving that a negative impl of this trait
    /// exists. (Note that coherence also checks whether negative impls of supertraits
    /// exist via a series of predicates.)
    pub polarity: PredicatePolarity,
}

impl<I: Interner> Eq for TraitPredicate<I> {}

impl<I: Interner> TraitPredicate<I> {
    pub fn with_replaced_self_ty(self, interner: I, self_ty: I::Ty) -> Self {
        Self {
            trait_ref: self.trait_ref.with_replaced_self_ty(interner, self_ty),
            polarity: self.polarity,
        }
    }

    pub fn def_id(self) -> I::TraitId {
        self.trait_ref.def_id
    }

    pub fn self_ty(self) -> I::Ty {
        self.trait_ref.self_ty()
    }
}

impl<I: Interner> ty::Binder<I, TraitPredicate<I>> {
    pub fn def_id(self) -> I::TraitId {
        // Ok to skip binder since trait `DefId` does not care about regions.
        self.skip_binder().def_id()
    }

    pub fn self_ty(self) -> ty::Binder<I, I::Ty> {
        self.map_bound(|trait_ref| trait_ref.self_ty())
    }

    #[inline]
    pub fn polarity(self) -> PredicatePolarity {
        self.skip_binder().polarity
    }
}

impl<I: Interner> UpcastFrom<I, TraitRef<I>> for TraitPredicate<I> {
    fn upcast_from(from: TraitRef<I>, _tcx: I) -> Self {
        TraitPredicate { trait_ref: from, polarity: PredicatePolarity::Positive }
    }
}

impl<I: Interner> UpcastFrom<I, ty::Binder<I, TraitRef<I>>> for ty::Binder<I, TraitPredicate<I>> {
    fn upcast_from(from: ty::Binder<I, TraitRef<I>>, _tcx: I) -> Self {
        from.map_bound(|trait_ref| TraitPredicate {
            trait_ref,
            polarity: PredicatePolarity::Positive,
        })
    }
}

impl<I: Interner> fmt::Debug for TraitPredicate<I> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "TraitPredicate({:?}, polarity:{:?})", self.trait_ref, self.polarity)
    }
}

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
#[cfg_attr(feature = "nightly", derive(Decodable_NoContext, Encodable_NoContext, HashStable))]
pub enum ImplPolarity {
    /// `impl Trait for Type`
    Positive,
    /// `impl !Trait for Type`
    Negative,
    /// `#[rustc_reservation_impl] impl Trait for Type`
    ///
    /// This is a "stability hack", not a real Rust feature.
    /// See #64631 for details.
    Reservation,
}

impl fmt::Display for ImplPolarity {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Positive => f.write_str("positive"),
            Self::Negative => f.write_str("negative"),
            Self::Reservation => f.write_str("reservation"),
        }
    }
}

impl ImplPolarity {
    /// The polarity marker in front of the impl trait ref if applicable.
    pub fn as_str(self) -> &'static str {
        match self {
            Self::Positive => "",
            Self::Negative => "!",
            Self::Reservation => "",
        }
    }
}

/// Polarity for a trait predicate.
///
/// May either be negative or positive.
/// Distinguished from [`ImplPolarity`] since we never compute goals with
/// "reservation" level.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
#[cfg_attr(feature = "nightly", derive(Decodable_NoContext, Encodable_NoContext, HashStable))]
pub enum PredicatePolarity {
    /// `Type: Trait`
    Positive,
    /// `Type: !Trait`
    Negative,
}

impl PredicatePolarity {
    /// Flips polarity by turning `Positive` into `Negative` and `Negative` into `Positive`.
    pub fn flip(&self) -> PredicatePolarity {
        match self {
            PredicatePolarity::Positive => PredicatePolarity::Negative,
            PredicatePolarity::Negative => PredicatePolarity::Positive,
        }
    }
}

impl fmt::Display for PredicatePolarity {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Positive => f.write_str("positive"),
            Self::Negative => f.write_str("negative"),
        }
    }
}

#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub enum ExistentialPredicate<I: Interner> {
    /// E.g., `Iterator`.
    Trait(ExistentialTraitRef<I>),
    /// E.g., `Iterator::Item = T`.
    Projection(ExistentialProjection<I>),
    /// E.g., `Send`.
    AutoTrait(I::TraitId),
}

impl<I: Interner> Eq for ExistentialPredicate<I> {}

impl<I: Interner> ty::Binder<I, ExistentialPredicate<I>> {
    pub fn def_id(&self) -> I::DefId {
        match self.skip_binder() {
            ExistentialPredicate::Trait(tr) => tr.def_id.into(),
            ExistentialPredicate::Projection(p) => p.def_id.into(),
            ExistentialPredicate::AutoTrait(did) => did.into(),
        }
    }
    /// Given an existential predicate like `?Self: PartialEq<u32>` (e.g., derived from `dyn PartialEq<u32>`),
    /// and a concrete type `self_ty`, returns a full predicate where the existentially quantified variable `?Self`
    /// has been replaced with `self_ty` (e.g., `self_ty: PartialEq<u32>`, in our example).
    pub fn with_self_ty(&self, cx: I, self_ty: I::Ty) -> I::Clause {
        match self.skip_binder() {
            ExistentialPredicate::Trait(tr) => self.rebind(tr).with_self_ty(cx, self_ty).upcast(cx),
            ExistentialPredicate::Projection(p) => {
                self.rebind(p.with_self_ty(cx, self_ty)).upcast(cx)
            }
            ExistentialPredicate::AutoTrait(did) => {
                let generics = cx.generics_of(did.into());
                let trait_ref = if generics.count() == 1 {
                    ty::TraitRef::new(cx, did, [self_ty])
                } else {
                    // If this is an ill-formed auto trait, then synthesize
                    // new error args for the missing generics.
                    let err_args =
                        GenericArgs::extend_with_error(cx, did.into(), &[self_ty.into()]);
                    ty::TraitRef::new_from_args(cx, did, err_args)
                };
                self.rebind(trait_ref).upcast(cx)
            }
        }
    }
}

/// An existential reference to a trait, where `Self` is erased.
///
/// For example, the trait object `Trait<'a, 'b, X, Y>` is:
/// ```ignore (illustrative)
/// exists T. T: Trait<'a, 'b, X, Y>
/// ```
/// The generic parameters don't include the erased `Self`, only trait
/// type and lifetime parameters (`[X, Y]` and `['a, 'b]` above).
#[derive_where(Clone, Copy, Hash, PartialEq; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct ExistentialTraitRef<I: Interner> {
    pub def_id: I::TraitId,
    pub args: I::GenericArgs,
    /// This field exists to prevent the creation of `ExistentialTraitRef` without
    /// calling [`ExistentialTraitRef::new_from_args`].
    _use_existential_trait_ref_new_instead: (),
}

impl<I: Interner> Eq for ExistentialTraitRef<I> {}

impl<I: Interner> ExistentialTraitRef<I> {
    pub fn new_from_args(interner: I, trait_def_id: I::TraitId, args: I::GenericArgs) -> Self {
        interner.debug_assert_existential_args_compatible(trait_def_id.into(), args);
        Self { def_id: trait_def_id, args, _use_existential_trait_ref_new_instead: () }
    }

    pub fn new(
        interner: I,
        trait_def_id: I::TraitId,
        args: impl IntoIterator<Item: Into<I::GenericArg>>,
    ) -> Self {
        let args = interner.mk_args_from_iter(args.into_iter().map(Into::into));
        Self::new_from_args(interner, trait_def_id, args)
    }

    pub fn erase_self_ty(interner: I, trait_ref: TraitRef<I>) -> ExistentialTraitRef<I> {
        // Assert there is a Self.
        trait_ref.args.type_at(0);

        ExistentialTraitRef {
            def_id: trait_ref.def_id,
            args: interner.mk_args(&trait_ref.args.as_slice()[1..]),
            _use_existential_trait_ref_new_instead: (),
        }
    }

    /// Object types don't have a self type specified. Therefore, when
    /// we convert the principal trait-ref into a normal trait-ref,
    /// you must give *some* self type. A common choice is `mk_err()`
    /// or some placeholder type.
    pub fn with_self_ty(self, interner: I, self_ty: I::Ty) -> TraitRef<I> {
        // otherwise the escaping vars would be captured by the binder
        // debug_assert!(!self_ty.has_escaping_bound_vars());

        TraitRef::new(interner, self.def_id, [self_ty.into()].into_iter().chain(self.args.iter()))
    }
}

impl<I: Interner> ty::Binder<I, ExistentialTraitRef<I>> {
    pub fn def_id(&self) -> I::TraitId {
        self.skip_binder().def_id
    }

    /// Object types don't have a self type specified. Therefore, when
    /// we convert the principal trait-ref into a normal trait-ref,
    /// you must give *some* self type. A common choice is `mk_err()`
    /// or some placeholder type.
    pub fn with_self_ty(&self, cx: I, self_ty: I::Ty) -> ty::Binder<I, TraitRef<I>> {
        self.map_bound(|trait_ref| trait_ref.with_self_ty(cx, self_ty))
    }
}

/// A `ProjectionPredicate` for an `ExistentialTraitRef`.
#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct ExistentialProjection<I: Interner> {
    pub def_id: I::DefId,
    pub args: I::GenericArgs,
    pub term: I::Term,

    /// This field exists to prevent the creation of `ExistentialProjection`
    /// without using [`ExistentialProjection::new_from_args`].
    #[derive_where(skip(Debug))]
    use_existential_projection_new_instead: (),
}

impl<I: Interner> Eq for ExistentialProjection<I> {}

impl<I: Interner> ExistentialProjection<I> {
    pub fn new_from_args(
        interner: I,
        def_id: I::DefId,
        args: I::GenericArgs,
        term: I::Term,
    ) -> ExistentialProjection<I> {
        interner.debug_assert_existential_args_compatible(def_id, args);
        Self { def_id, args, term, use_existential_projection_new_instead: () }
    }

    pub fn new(
        interner: I,
        def_id: I::DefId,
        args: impl IntoIterator<Item: Into<I::GenericArg>>,
        term: I::Term,
    ) -> ExistentialProjection<I> {
        let args = interner.mk_args_from_iter(args.into_iter().map(Into::into));
        Self::new_from_args(interner, def_id, args, term)
    }

    /// Extracts the underlying existential trait reference from this projection.
    ///
    /// For example, if this is a projection of `exists T. <T as Iterator>::Item == X`,
    /// then this function would return an `exists T. T: Iterator` existential trait
    /// reference.
    pub fn trait_ref(&self, interner: I) -> ExistentialTraitRef<I> {
        let def_id = interner.parent(self.def_id);
        let args_count = interner.generics_of(def_id).count() - 1;
        let args = interner.mk_args(&self.args.as_slice()[..args_count]);
        ExistentialTraitRef::new_from_args(interner, def_id.try_into().unwrap(), args)
    }

    pub fn with_self_ty(&self, interner: I, self_ty: I::Ty) -> ProjectionPredicate<I> {
        // otherwise the escaping regions would be captured by the binders
        debug_assert!(!self_ty.has_escaping_bound_vars());

        ProjectionPredicate {
            projection_term: AliasTerm::new(
                interner,
                interner.alias_term_kind_from_def_id(self.def_id),
                [self_ty.into()].iter().chain(self.args.iter()),
            ),
            term: self.term,
        }
    }

    pub fn erase_self_ty(interner: I, projection_predicate: ProjectionPredicate<I>) -> Self {
        // Assert there is a Self.
        projection_predicate.projection_term.args.type_at(0);

        Self {
            def_id: projection_predicate.projection_term.def_id(),
            args: interner.mk_args(&projection_predicate.projection_term.args.as_slice()[1..]),
            term: projection_predicate.term,
            use_existential_projection_new_instead: (),
        }
    }
}

impl<I: Interner> ty::Binder<I, ExistentialProjection<I>> {
    pub fn with_self_ty(&self, cx: I, self_ty: I::Ty) -> ty::Binder<I, ProjectionPredicate<I>> {
        self.map_bound(|p| p.with_self_ty(cx, self_ty))
    }

    pub fn item_def_id(&self) -> I::DefId {
        self.skip_binder().def_id
    }
}

#[derive_where(Clone, Copy, PartialEq, Eq, Hash, Debug; I: Interner)]
#[derive(Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
)]
pub enum AliasTermKind<I: Interner> {
    /// A projection `<Type as Trait>::AssocType`.
    ///
    /// Can get normalized away if monomorphic enough.
    ///
    /// The `def_id` is the `DefId` of the `TraitItem` for the associated type.
    ///
    /// Note that the `def_id` is not the `DefId` of the `TraitRef` containing this
    /// associated type, which is in `interner.associated_item(def_id).container`,
    /// aka. `interner.parent(def_id)`.
    ProjectionTy { def_id: I::DefId },

    /// An associated type in an inherent `impl`
    ///
    /// The `def_id` is the `DefId` of the `ImplItem` for the associated type.
    InherentTy { def_id: I::DefId },

    /// An opaque type (usually from `impl Trait` in type aliases or function return types)
    ///
    /// `def_id` is the `DefId` of the `OpaqueType` item.
    ///
    /// Can only be normalized away in `PostAnalysis` mode or its defining scope.
    ///
    /// During codegen, `interner.type_of(def_id)` can be used to get the type of the
    /// underlying type if the type is an opaque.
    OpaqueTy { def_id: I::DefId },

    /// A type alias that actually checks its trait bounds.
    ///
    /// Currently only used if the type alias references opaque types.
    /// Can always be normalized away.
    FreeTy { def_id: I::DefId },

    /// An unevaluated anonymous constants.
    UnevaluatedConst { def_id: I::DefId },
    /// An unevaluated const coming from an associated const.
    ProjectionConst { def_id: I::DefId },
    /// A top level const item not part of a trait or impl.
    FreeConst { def_id: I::DefId },
    /// An associated const in an inherent `impl`
    InherentConst { def_id: I::DefId },
}

impl<I: Interner> AliasTermKind<I> {
    pub fn descr(self) -> &'static str {
        match self {
            AliasTermKind::ProjectionTy { .. } => "associated type",
            AliasTermKind::ProjectionConst { .. } => "associated const",
            AliasTermKind::InherentTy { .. } => "inherent associated type",
            AliasTermKind::InherentConst { .. } => "inherent associated const",
            AliasTermKind::OpaqueTy { .. } => "opaque type",
            AliasTermKind::FreeTy { .. } => "type alias",
            AliasTermKind::FreeConst { .. } => "unevaluated constant",
            AliasTermKind::UnevaluatedConst { .. } => "unevaluated constant",
        }
    }

    pub fn is_type(self) -> bool {
        match self {
            AliasTermKind::ProjectionTy { .. }
            | AliasTermKind::InherentTy { .. }
            | AliasTermKind::OpaqueTy { .. }
            | AliasTermKind::FreeTy { .. } => true,

            AliasTermKind::UnevaluatedConst { .. }
            | AliasTermKind::ProjectionConst { .. }
            | AliasTermKind::InherentConst { .. }
            | AliasTermKind::FreeConst { .. } => false,
        }
    }

    // FIXME: replace with explicit matches
    pub fn def_id(self) -> I::DefId {
        let (AliasTermKind::ProjectionTy { def_id }
        | AliasTermKind::InherentTy { def_id }
        | AliasTermKind::OpaqueTy { def_id }
        | AliasTermKind::FreeTy { def_id }
        | AliasTermKind::UnevaluatedConst { def_id }
        | AliasTermKind::ProjectionConst { def_id }
        | AliasTermKind::FreeConst { def_id }
        | AliasTermKind::InherentConst { def_id }) = self;
        def_id
    }
}

impl<I: Interner> From<ty::AliasTyKind<I>> for AliasTermKind<I> {
    fn from(value: ty::AliasTyKind<I>) -> Self {
        match value {
            ty::Projection { def_id } => AliasTermKind::ProjectionTy { def_id },
            ty::Opaque { def_id } => AliasTermKind::OpaqueTy { def_id },
            ty::Free { def_id } => AliasTermKind::FreeTy { def_id },
            ty::Inherent { def_id } => AliasTermKind::InherentTy { def_id },
        }
    }
}

/// Represents the unprojected term of a projection goal.
///
/// * For a projection, this would be `<Ty as Trait<...>>::N<...>`.
/// * For an inherent projection, this would be `Ty::N<...>`.
/// * For an opaque type, there is no explicit syntax.
#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct AliasTerm<I: Interner> {
    /// The parameters of the associated or opaque item.
    ///
    /// For a projection, these are the generic parameters for the trait and the
    /// GAT parameters, if there are any.
    ///
    /// For an inherent projection, they consist of the self type and the GAT parameters,
    /// if there are any.
    ///
    /// For RPIT the generic parameters are for the generics of the function,
    /// while for TAIT it is used for the generic parameters of the alias.
    pub args: I::GenericArgs,

    #[type_foldable(identity)]
    #[type_visitable(ignore)]
    pub kind: AliasTermKind<I>,

    /// This field exists to prevent the creation of `AliasTerm` without using [`AliasTerm::new_from_args`].
    #[derive_where(skip(Debug))]
    _use_alias_term_new_instead: (),
}

impl<I: Interner> Eq for AliasTerm<I> {}

impl<I: Interner> AliasTerm<I> {
    pub fn new_from_args(
        interner: I,
        kind: AliasTermKind<I>,
        args: I::GenericArgs,
    ) -> AliasTerm<I> {
        interner.debug_assert_args_compatible(kind.def_id(), args);
        AliasTerm { kind, args, _use_alias_term_new_instead: () }
    }

    pub fn new(
        interner: I,
        kind: AliasTermKind<I>,
        args: impl IntoIterator<Item: Into<I::GenericArg>>,
    ) -> AliasTerm<I> {
        let args = interner.mk_args_from_iter(args.into_iter().map(Into::into));
        Self::new_from_args(interner, kind, args)
    }

    pub fn new_from_def_id(interner: I, def_id: I::DefId, args: I::GenericArgs) -> AliasTerm<I> {
        let kind = interner.alias_term_kind_from_def_id(def_id);
        Self::new_from_args(interner, kind, args)
    }

    pub fn from_unevaluated_const(interner: I, ct: ty::UnevaluatedConst<I>) -> Self {
        let kind = interner.alias_term_kind_from_def_id(ct.def.into());
        AliasTerm::new_from_args(interner, kind, ct.args)
    }

    pub fn expect_ty(self, interner: I) -> ty::AliasTy<I> {
        let kind = match self.kind(interner) {
            AliasTermKind::ProjectionTy { def_id } => AliasTyKind::Projection { def_id },
            AliasTermKind::InherentTy { def_id } => AliasTyKind::Inherent { def_id },
            AliasTermKind::OpaqueTy { def_id } => AliasTyKind::Opaque { def_id },
            AliasTermKind::FreeTy { def_id } => AliasTyKind::Free { def_id },
            AliasTermKind::InherentConst { .. }
            | AliasTermKind::FreeConst { .. }
            | AliasTermKind::UnevaluatedConst { .. }
            | AliasTermKind::ProjectionConst { .. } => {
                panic!("Cannot turn `UnevaluatedConst` into `AliasTy`")
            }
        };
        ty::AliasTy { kind, args: self.args, _use_alias_ty_new_instead: () }
    }

    // FIXME: remove this function (access the field instead)
    pub fn kind(self, _interner: I) -> AliasTermKind<I> {
        self.kind
    }

    // FIXME: replace with explicit matches
    pub fn def_id(self) -> I::DefId {
        self.kind.def_id()
    }

    pub fn to_term(self, interner: I) -> I::Term {
        let alias_ty_kind = match self.kind(interner) {
            AliasTermKind::FreeConst { def_id }
            | AliasTermKind::InherentConst { def_id }
            | AliasTermKind::UnevaluatedConst { def_id }
            | AliasTermKind::ProjectionConst { def_id } => {
                return I::Const::new_unevaluated(
                    interner,
                    ty::UnevaluatedConst::new(def_id.try_into().unwrap(), self.args),
                )
                .into();
            }

            AliasTermKind::ProjectionTy { def_id } => ty::Projection { def_id },
            AliasTermKind::InherentTy { def_id } => ty::Inherent { def_id },
            AliasTermKind::OpaqueTy { def_id } => ty::Opaque { def_id },
            AliasTermKind::FreeTy { def_id } => ty::Free { def_id },
        };

        Ty::new_alias(interner, ty::AliasTy::new_from_args(interner, alias_ty_kind, self.args))
            .into()
    }

    pub fn with_args(self, interner: I, args: I::GenericArgs) -> Self {
        Self::new_from_args(interner, self.kind, args)
    }
}

/// The following methods work only with (trait) associated term projections.
impl<I: Interner> AliasTerm<I> {
    pub fn self_ty(self) -> I::Ty {
        self.args.type_at(0)
    }

    pub fn with_replaced_self_ty(self, interner: I, self_ty: I::Ty) -> Self {
        AliasTerm::new(
            interner,
            self.kind,
            [self_ty.into()].into_iter().chain(self.args.iter().skip(1)),
        )
    }

    pub fn trait_def_id(self, interner: I) -> I::TraitId {
        assert!(
            matches!(
                self.kind(interner),
                AliasTermKind::ProjectionTy { .. } | AliasTermKind::ProjectionConst { .. }
            ),
            "expected a projection"
        );
        interner.parent(self.def_id()).try_into().unwrap()
    }

    /// Extracts the underlying trait reference and own args from this projection.
    /// For example, if this is a projection of `<T as StreamingIterator>::Item<'a>`,
    /// then this function would return a `T: StreamingIterator` trait reference and
    /// `['a]` as the own args.
    pub fn trait_ref_and_own_args(self, interner: I) -> (TraitRef<I>, I::GenericArgsSlice) {
        interner.trait_ref_and_own_args_for_alias(self.def_id(), self.args)
    }

    /// Extracts the underlying trait reference from this projection.
    /// For example, if this is a projection of `<T as Iterator>::Item`,
    /// then this function would return a `T: Iterator` trait reference.
    ///
    /// WARNING: This will drop the args for generic associated types
    /// consider calling [Self::trait_ref_and_own_args] to get those
    /// as well.
    pub fn trait_ref(self, interner: I) -> TraitRef<I> {
        self.trait_ref_and_own_args(interner).0
    }

    /// Extract the own args from this projection.
    /// For example, if this is a projection of `<T as StreamingIterator>::Item<'a>`,
    /// then this function would return the slice `['a]` as the own args.
    pub fn own_args(self, interner: I) -> I::GenericArgsSlice {
        self.trait_ref_and_own_args(interner).1
    }
}

/// The following methods work only with inherent associated term projections.
impl<I: Interner> AliasTerm<I> {
    /// Transform the generic parameters to have the given `impl` args as the base and the GAT args on top of that.
    ///
    /// Does the following transformation:
    ///
    /// ```text
    /// [Self, P_0...P_m] -> [I_0...I_n, P_0...P_m]
    ///
    ///     I_i impl args
    ///     P_j GAT args
    /// ```
    pub fn rebase_inherent_args_onto_impl(
        self,
        impl_args: I::GenericArgs,
        interner: I,
    ) -> I::GenericArgs {
        debug_assert!(matches!(
            self.kind(interner),
            AliasTermKind::InherentTy { .. } | AliasTermKind::InherentConst { .. }
        ));
        interner.mk_args_from_iter(impl_args.iter().chain(self.args.iter().skip(1)))
    }
}

impl<I: Interner> From<ty::AliasTy<I>> for AliasTerm<I> {
    fn from(ty: ty::AliasTy<I>) -> Self {
        AliasTerm {
            args: ty.args,
            kind: AliasTermKind::from(ty.kind),
            _use_alias_term_new_instead: (),
        }
    }
}

/// This kind of predicate has no *direct* correspondent in the
/// syntax, but it roughly corresponds to the syntactic forms:
///
/// 1. `T: TraitRef<..., Item = Type>`
/// 2. `<T as TraitRef<...>>::Item == Type` (NYI)
///
/// In particular, form #1 is "desugared" to the combination of a
/// normal trait predicate (`T: TraitRef<...>`) and one of these
/// predicates. Form #2 is a broader form in that it also permits
/// equality between arbitrary types. Processing an instance of
/// Form #2 eventually yields one of these `ProjectionPredicate`
/// instances to normalize the LHS.
#[derive_where(Clone, Copy, Hash, PartialEq; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct ProjectionPredicate<I: Interner> {
    pub projection_term: AliasTerm<I>,
    pub term: I::Term,
}

impl<I: Interner> Eq for ProjectionPredicate<I> {}

impl<I: Interner> ProjectionPredicate<I> {
    pub fn self_ty(self) -> I::Ty {
        self.projection_term.self_ty()
    }

    pub fn with_replaced_self_ty(self, interner: I, self_ty: I::Ty) -> ProjectionPredicate<I> {
        Self {
            projection_term: self.projection_term.with_replaced_self_ty(interner, self_ty),
            ..self
        }
    }

    pub fn trait_def_id(self, interner: I) -> I::TraitId {
        self.projection_term.trait_def_id(interner)
    }

    pub fn def_id(self) -> I::DefId {
        self.projection_term.def_id()
    }
}

impl<I: Interner> ty::Binder<I, ProjectionPredicate<I>> {
    /// Returns the `DefId` of the trait of the associated item being projected.
    #[inline]
    pub fn trait_def_id(&self, cx: I) -> I::TraitId {
        self.skip_binder().projection_term.trait_def_id(cx)
    }

    pub fn term(&self) -> ty::Binder<I, I::Term> {
        self.map_bound(|predicate| predicate.term)
    }

    /// The `DefId` of the `TraitItem` for the associated type.
    ///
    /// Note that this is not the `DefId` of the `TraitRef` containing this
    /// associated type, which is in `tcx.associated_item(projection_def_id()).container`.
    pub fn item_def_id(&self) -> I::DefId {
        // Ok to skip binder since trait `DefId` does not care about regions.
        self.skip_binder().projection_term.def_id()
    }
}

impl<I: Interner> fmt::Debug for ProjectionPredicate<I> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "ProjectionPredicate({:?}, {:?})", self.projection_term, self.term)
    }
}

/// Used by the new solver to normalize an alias. This always expects the `term` to
/// be an unconstrained inference variable which is used as the output.
#[derive_where(Clone, Copy, Hash, PartialEq; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct NormalizesTo<I: Interner> {
    pub alias: AliasTerm<I>,
    pub term: I::Term,
}

impl<I: Interner> Eq for NormalizesTo<I> {}

impl<I: Interner> NormalizesTo<I> {
    pub fn self_ty(self) -> I::Ty {
        self.alias.self_ty()
    }

    pub fn with_replaced_self_ty(self, interner: I, self_ty: I::Ty) -> NormalizesTo<I> {
        Self { alias: self.alias.with_replaced_self_ty(interner, self_ty), ..self }
    }

    pub fn trait_def_id(self, interner: I) -> I::TraitId {
        self.alias.trait_def_id(interner)
    }

    pub fn def_id(self) -> I::DefId {
        self.alias.def_id()
    }
}

impl<I: Interner> fmt::Debug for NormalizesTo<I> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "NormalizesTo({:?}, {:?})", self.alias, self.term)
    }
}

#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
)]
pub struct HostEffectPredicate<I: Interner> {
    pub trait_ref: ty::TraitRef<I>,
    pub constness: BoundConstness,
}

impl<I: Interner> Eq for HostEffectPredicate<I> {}

impl<I: Interner> HostEffectPredicate<I> {
    pub fn self_ty(self) -> I::Ty {
        self.trait_ref.self_ty()
    }

    pub fn with_replaced_self_ty(self, interner: I, self_ty: I::Ty) -> Self {
        Self { trait_ref: self.trait_ref.with_replaced_self_ty(interner, self_ty), ..self }
    }

    pub fn def_id(self) -> I::TraitId {
        self.trait_ref.def_id
    }
}

impl<I: Interner> ty::Binder<I, HostEffectPredicate<I>> {
    pub fn def_id(self) -> I::TraitId {
        // Ok to skip binder since trait `DefId` does not care about regions.
        self.skip_binder().def_id()
    }

    pub fn self_ty(self) -> ty::Binder<I, I::Ty> {
        self.map_bound(|trait_ref| trait_ref.self_ty())
    }

    #[inline]
    pub fn constness(self) -> BoundConstness {
        self.skip_binder().constness
    }
}

/// Encodes that `a` must be a subtype of `b`. The `a_is_expected` flag indicates
/// whether the `a` type is the type that we should label as "expected" when
/// presenting user diagnostics.
#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct SubtypePredicate<I: Interner> {
    pub a_is_expected: bool,
    pub a: I::Ty,
    pub b: I::Ty,
}

impl<I: Interner> Eq for SubtypePredicate<I> {}

/// Encodes that we have to coerce *from* the `a` type to the `b` type.
#[derive_where(Clone, Copy, Hash, PartialEq, Debug; I: Interner)]
#[derive(TypeVisitable_Generic, GenericTypeVisitable, TypeFoldable_Generic, Lift_Generic)]
#[cfg_attr(
    feature = "nightly",
    derive(Decodable_NoContext, Encodable_NoContext, HashStable_NoContext)
)]
pub struct CoercePredicate<I: Interner> {
    pub a: I::Ty,
    pub b: I::Ty,
}

impl<I: Interner> Eq for CoercePredicate<I> {}

#[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "nightly", derive(Encodable_NoContext, Decodable_NoContext, HashStable))]
pub enum BoundConstness {
    /// `Type: const Trait`
    ///
    /// A bound is required to be unconditionally const, even in a runtime function.
    Const,
    /// `Type: [const] Trait`
    ///
    /// Requires resolving to const only when we are in a const context.
    Maybe,
}

impl BoundConstness {
    pub fn satisfies(self, goal: BoundConstness) -> bool {
        match (self, goal) {
            (BoundConstness::Const, BoundConstness::Const | BoundConstness::Maybe) => true,
            (BoundConstness::Maybe, BoundConstness::Maybe) => true,
            (BoundConstness::Maybe, BoundConstness::Const) => false,
        }
    }

    pub fn as_str(self) -> &'static str {
        match self {
            Self::Const => "const",
            Self::Maybe => "[const]",
        }
    }
}

impl fmt::Display for BoundConstness {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Const => f.write_str("const"),
            Self::Maybe => f.write_str("[const]"),
        }
    }
}