//! Various utilities for the next-trait-solver.

use std::iter;
use std::ops::{self, ControlFlow};

use base_db::Crate;
use hir_def::lang_item::LangItem;
use hir_def::{BlockId, HasModule, ItemContainerId, Lookup};
use intern::sym;
use la_arena::Idx;
use rustc_abi::{Float, HasDataLayout, Integer, IntegerType, Primitive, ReprOptions};
use rustc_type_ir::data_structures::IndexMap;
use rustc_type_ir::inherent::{
    AdtDef, Const as _, GenericArg as _, GenericArgs as _, ParamEnv as _, Region as _, SliceLike,
    Ty as _,
};
use rustc_type_ir::lang_items::SolverTraitLangItem;
use rustc_type_ir::solve::SizedTraitKind;
use rustc_type_ir::{
    BoundVar, Canonical, DebruijnIndex, GenericArgKind, INNERMOST, Interner, PredicatePolarity,
    TypeFlags, TypeVisitable, TypeVisitableExt,
};
use rustc_type_ir::{
    ConstKind, CoroutineArgs, FloatTy, IntTy, RegionKind, TypeFolder, TypeSuperFoldable,
    TypeSuperVisitable, TypeVisitor, UintTy, UniverseIndex, inherent::IntoKind,
};
use rustc_type_ir::{InferCtxtLike, TypeFoldable};

use crate::lower_nextsolver::{LifetimeElisionKind, TyLoweringContext};
use crate::next_solver::infer::InferCtxt;
use crate::next_solver::{
    BoundConst, CanonicalVarKind, FxIndexMap, ParamEnv, Placeholder, PlaceholderConst,
    PlaceholderRegion, TypingMode,
};
use crate::{
    db::HirDatabase,
    from_foreign_def_id,
    method_resolution::{TraitImpls, TyFingerprint},
};

use super::fold::{BoundVarReplacer, FnMutDelegate};
use super::generics::generics;
use super::{
    AliasTerm, AliasTy, Binder, BoundRegion, BoundTy, BoundTyKind, BoundVarKind, BoundVarKinds,
    CanonicalVars, Clause, ClauseKind, Clauses, Const, DbInterner, EarlyBinder, GenericArg,
    GenericArgs, Predicate, PredicateKind, ProjectionPredicate, Region, SolverContext, SolverDefId,
    Term, TraitPredicate, TraitRef, Ty, TyKind,
};

#[derive(Clone, Debug)]
pub struct Discr<'db> {
    /// Bit representation of the discriminant (e.g., `-128i8` is `0xFF_u128`).
    pub val: u128,
    pub ty: Ty<'db>,
}

impl<'db> Discr<'db> {
    /// Adds `1` to the value and wraps around if the maximum for the type is reached.
    pub fn wrap_incr(self, interner: DbInterner<'db>) -> Self {
        self.checked_add(interner, 1).0
    }
    pub fn checked_add(self, interner: DbInterner<'db>, n: u128) -> (Self, bool) {
        let (size, signed) = self.ty.int_size_and_signed(interner);
        let (val, oflo) = if signed {
            let min = size.signed_int_min();
            let max = size.signed_int_max();
            let val = size.sign_extend(self.val);
            assert!(n < (i128::MAX as u128));
            let n = n as i128;
            let oflo = val > max - n;
            let val = if oflo { min + (n - (max - val) - 1) } else { val + n };
            // zero the upper bits
            let val = val as u128;
            let val = size.truncate(val);
            (val, oflo)
        } else {
            let max = size.unsigned_int_max();
            let val = self.val;
            let oflo = val > max - n;
            let val = if oflo { n - (max - val) - 1 } else { val + n };
            (val, oflo)
        };
        (Self { val, ty: self.ty }, oflo)
    }
}

pub trait IntegerTypeExt {
    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
    fn initial_discriminant<'db>(&self, interner: DbInterner<'db>) -> Discr<'db>;
    fn disr_incr<'db>(
        &self,
        interner: DbInterner<'db>,
        val: Option<Discr<'db>>,
    ) -> Option<Discr<'db>>;
}

impl IntegerTypeExt for IntegerType {
    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
        match self {
            IntegerType::Pointer(true) => Ty::new(interner, TyKind::Int(IntTy::Isize)),
            IntegerType::Pointer(false) => Ty::new(interner, TyKind::Uint(UintTy::Usize)),
            IntegerType::Fixed(i, s) => i.to_ty(interner, *s),
        }
    }

    fn initial_discriminant<'db>(&self, interner: DbInterner<'db>) -> Discr<'db> {
        Discr { val: 0, ty: self.to_ty(interner) }
    }

    fn disr_incr<'db>(
        &self,
        interner: DbInterner<'db>,
        val: Option<Discr<'db>>,
    ) -> Option<Discr<'db>> {
        if let Some(val) = val {
            assert_eq!(self.to_ty(interner), val.ty);
            let (new, oflo) = val.checked_add(interner, 1);
            if oflo { None } else { Some(new) }
        } else {
            Some(self.initial_discriminant(interner))
        }
    }
}

pub trait IntegerExt {
    fn to_ty<'db>(&self, interner: DbInterner<'db>, signed: bool) -> Ty<'db>;
    fn from_int_ty<C: HasDataLayout>(cx: &C, ity: IntTy) -> Integer;
    fn from_uint_ty<C: HasDataLayout>(cx: &C, ity: UintTy) -> Integer;
    fn repr_discr<'db>(
        interner: DbInterner<'db>,
        ty: Ty<'db>,
        repr: &ReprOptions,
        min: i128,
        max: i128,
    ) -> (Integer, bool);
}

impl IntegerExt for Integer {
    #[inline]
    fn to_ty<'db>(&self, interner: DbInterner<'db>, signed: bool) -> Ty<'db> {
        use Integer::*;
        match (*self, signed) {
            (I8, false) => Ty::new(interner, TyKind::Uint(UintTy::U8)),
            (I16, false) => Ty::new(interner, TyKind::Uint(UintTy::U16)),
            (I32, false) => Ty::new(interner, TyKind::Uint(UintTy::U32)),
            (I64, false) => Ty::new(interner, TyKind::Uint(UintTy::U64)),
            (I128, false) => Ty::new(interner, TyKind::Uint(UintTy::U128)),
            (I8, true) => Ty::new(interner, TyKind::Int(IntTy::I8)),
            (I16, true) => Ty::new(interner, TyKind::Int(IntTy::I16)),
            (I32, true) => Ty::new(interner, TyKind::Int(IntTy::I32)),
            (I64, true) => Ty::new(interner, TyKind::Int(IntTy::I64)),
            (I128, true) => Ty::new(interner, TyKind::Int(IntTy::I128)),
        }
    }

    fn from_int_ty<C: HasDataLayout>(cx: &C, ity: IntTy) -> Integer {
        use Integer::*;
        match ity {
            IntTy::I8 => I8,
            IntTy::I16 => I16,
            IntTy::I32 => I32,
            IntTy::I64 => I64,
            IntTy::I128 => I128,
            IntTy::Isize => cx.data_layout().ptr_sized_integer(),
        }
    }
    fn from_uint_ty<C: HasDataLayout>(cx: &C, ity: UintTy) -> Integer {
        use Integer::*;
        match ity {
            UintTy::U8 => I8,
            UintTy::U16 => I16,
            UintTy::U32 => I32,
            UintTy::U64 => I64,
            UintTy::U128 => I128,
            UintTy::Usize => cx.data_layout().ptr_sized_integer(),
        }
    }

    /// Finds the appropriate Integer type and signedness for the given
    /// signed discriminant range and `#[repr]` attribute.
    /// N.B.: `u128` values above `i128::MAX` will be treated as signed, but
    /// that shouldn't affect anything, other than maybe debuginfo.
    fn repr_discr<'db>(
        interner: DbInterner<'db>,
        ty: Ty<'db>,
        repr: &ReprOptions,
        min: i128,
        max: i128,
    ) -> (Integer, bool) {
        // Theoretically, negative values could be larger in unsigned representation
        // than the unsigned representation of the signed minimum. However, if there
        // are any negative values, the only valid unsigned representation is u128
        // which can fit all i128 values, so the result remains unaffected.
        let unsigned_fit = Integer::fit_unsigned(std::cmp::max(min as u128, max as u128));
        let signed_fit = std::cmp::max(Integer::fit_signed(min), Integer::fit_signed(max));

        if let Some(ity) = repr.int {
            let discr = Integer::from_attr(&interner, ity);
            let fit = if ity.is_signed() { signed_fit } else { unsigned_fit };
            if discr < fit {
                panic!(
                    "Integer::repr_discr: `#[repr]` hint too small for \
                      discriminant range of enum `{ty:?}`"
                )
            }
            return (discr, ity.is_signed());
        }

        let at_least = if repr.c() {
            // This is usually I32, however it can be different on some platforms,
            // notably hexagon and arm-none/thumb-none
            interner.data_layout().c_enum_min_size
        } else {
            // repr(Rust) enums try to be as small as possible
            Integer::I8
        };

        // If there are no negative values, we can use the unsigned fit.
        if min >= 0 {
            (std::cmp::max(unsigned_fit, at_least), false)
        } else {
            (std::cmp::max(signed_fit, at_least), true)
        }
    }
}

pub trait FloatExt {
    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
    fn from_float_ty(fty: FloatTy) -> Self;
}

impl FloatExt for Float {
    #[inline]
    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
        use Float::*;
        match *self {
            F16 => Ty::new(interner, TyKind::Float(FloatTy::F16)),
            F32 => Ty::new(interner, TyKind::Float(FloatTy::F32)),
            F64 => Ty::new(interner, TyKind::Float(FloatTy::F64)),
            F128 => Ty::new(interner, TyKind::Float(FloatTy::F128)),
        }
    }

    fn from_float_ty(fty: FloatTy) -> Self {
        use Float::*;
        match fty {
            FloatTy::F16 => F16,
            FloatTy::F32 => F32,
            FloatTy::F64 => F64,
            FloatTy::F128 => F128,
        }
    }
}

pub trait PrimitiveExt {
    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
    fn to_int_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db>;
}

impl PrimitiveExt for Primitive {
    #[inline]
    fn to_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
        match *self {
            Primitive::Int(i, signed) => i.to_ty(interner, signed),
            Primitive::Float(f) => f.to_ty(interner),
            Primitive::Pointer(_) => Ty::new(
                interner,
                TyKind::RawPtr(
                    Ty::new(interner, TyKind::Tuple(Default::default())),
                    rustc_ast_ir::Mutability::Mut,
                ),
            ),
        }
    }

    /// Return an *integer* type matching this primitive.
    /// Useful in particular when dealing with enum discriminants.
    #[inline]
    fn to_int_ty<'db>(&self, interner: DbInterner<'db>) -> Ty<'db> {
        match *self {
            Primitive::Int(i, signed) => i.to_ty(interner, signed),
            Primitive::Pointer(_) => {
                let signed = false;
                interner.data_layout().ptr_sized_integer().to_ty(interner, signed)
            }
            Primitive::Float(_) => panic!("floats do not have an int type"),
        }
    }
}

impl<'db> HasDataLayout for DbInterner<'db> {
    fn data_layout(&self) -> &rustc_abi::TargetDataLayout {
        unimplemented!()
    }
}

pub trait CoroutineArgsExt<'db> {
    fn discr_ty(&self, interner: DbInterner<'db>) -> Ty<'db>;
}

impl<'db> CoroutineArgsExt<'db> for CoroutineArgs<DbInterner<'db>> {
    /// The type of the state discriminant used in the coroutine type.
    #[inline]
    fn discr_ty(&self, interner: DbInterner<'db>) -> Ty<'db> {
        Ty::new(interner, TyKind::Uint(UintTy::U32))
    }
}

/// Finds the max universe present
pub struct MaxUniverse {
    max_universe: UniverseIndex,
}

impl Default for MaxUniverse {
    fn default() -> Self {
        Self::new()
    }
}

impl MaxUniverse {
    pub fn new() -> Self {
        MaxUniverse { max_universe: UniverseIndex::ROOT }
    }

    pub fn max_universe(self) -> UniverseIndex {
        self.max_universe
    }
}

impl<'db> TypeVisitor<DbInterner<'db>> for MaxUniverse {
    type Result = ();

    fn visit_ty(&mut self, t: Ty<'db>) {
        if let TyKind::Placeholder(placeholder) = t.kind() {
            self.max_universe = UniverseIndex::from_u32(
                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
            );
        }

        t.super_visit_with(self)
    }

    fn visit_const(&mut self, c: Const<'db>) {
        if let ConstKind::Placeholder(placeholder) = c.kind() {
            self.max_universe = UniverseIndex::from_u32(
                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
            );
        }

        c.super_visit_with(self)
    }

    fn visit_region(&mut self, r: Region<'db>) {
        if let RegionKind::RePlaceholder(placeholder) = r.kind() {
            self.max_universe = UniverseIndex::from_u32(
                self.max_universe.as_u32().max(placeholder.universe.as_u32()),
            );
        }
    }
}

pub struct BottomUpFolder<'db, F, G, H>
where
    F: FnMut(Ty<'db>) -> Ty<'db>,
    G: FnMut(Region<'db>) -> Region<'db>,
    H: FnMut(Const<'db>) -> Const<'db>,
{
    pub interner: DbInterner<'db>,
    pub ty_op: F,
    pub lt_op: G,
    pub ct_op: H,
}

impl<'db, F, G, H> TypeFolder<DbInterner<'db>> for BottomUpFolder<'db, F, G, H>
where
    F: FnMut(Ty<'db>) -> Ty<'db>,
    G: FnMut(Region<'db>) -> Region<'db>,
    H: FnMut(Const<'db>) -> Const<'db>,
{
    fn cx(&self) -> DbInterner<'db> {
        self.interner
    }

    fn fold_ty(&mut self, ty: Ty<'db>) -> Ty<'db> {
        let t = ty.super_fold_with(self);
        (self.ty_op)(t)
    }

    fn fold_region(&mut self, r: Region<'db>) -> Region<'db> {
        // This one is a little different, because `super_fold_with` is not
        // implemented on non-recursive `Region`.
        (self.lt_op)(r)
    }

    fn fold_const(&mut self, ct: Const<'db>) -> Const<'db> {
        let ct = ct.super_fold_with(self);
        (self.ct_op)(ct)
    }
}

pub(crate) fn for_trait_impls(
    db: &dyn HirDatabase,
    krate: Crate,
    block: Option<BlockId>,
    trait_id: hir_def::TraitId,
    self_ty_fp: Option<TyFingerprint>,
    mut f: impl FnMut(&TraitImpls) -> ControlFlow<()>,
) -> ControlFlow<()> {
    // Note: Since we're using `impls_for_trait` and `impl_provided_for`,
    // only impls where the trait can be resolved should ever reach Chalk.
    // `impl_datum` relies on that and will panic if the trait can't be resolved.
    let in_deps = db.trait_impls_in_deps(krate);
    let in_self = db.trait_impls_in_crate(krate);
    let trait_module = trait_id.module(db);
    let type_module = match self_ty_fp {
        Some(TyFingerprint::Adt(adt_id)) => Some(adt_id.module(db)),
        Some(TyFingerprint::ForeignType(type_id)) => Some(from_foreign_def_id(type_id).module(db)),
        Some(TyFingerprint::Dyn(trait_id)) => Some(trait_id.module(db)),
        _ => None,
    };

    let mut def_blocks =
        [trait_module.containing_block(), type_module.and_then(|it| it.containing_block())];

    let block_impls = iter::successors(block, |&block_id| {
        cov_mark::hit!(block_local_impls);
        block_id.loc(db).module.containing_block()
    })
    .inspect(|&block_id| {
        // make sure we don't search the same block twice
        def_blocks.iter_mut().for_each(|block| {
            if *block == Some(block_id) {
                *block = None;
            }
        });
    })
    .filter_map(|block_id| db.trait_impls_in_block(block_id));
    f(&in_self)?;
    for it in in_deps.iter().map(ops::Deref::deref) {
        f(it)?;
    }
    for it in block_impls {
        f(&it)?;
    }
    for it in def_blocks.into_iter().flatten().filter_map(|it| db.trait_impls_in_block(it)) {
        f(&it)?;
    }
    ControlFlow::Continue(())
}

// FIXME(next-trait-solver): uplift
pub fn sizedness_constraint_for_ty<'db>(
    interner: DbInterner<'db>,
    sizedness: SizedTraitKind,
    ty: Ty<'db>,
) -> Option<Ty<'db>> {
    use rustc_type_ir::TyKind::*;

    match ty.kind() {
        // these are always sized
        Bool | Char | Int(..) | Uint(..) | Float(..) | RawPtr(..) | Ref(..) | FnDef(..)
        | FnPtr(..) | Array(..) | Closure(..) | CoroutineClosure(..) | Coroutine(..)
        | CoroutineWitness(..) | Never => None,

        // these are never sized
        Str | Slice(..) | Dynamic(_, _, rustc_type_ir::DynKind::Dyn) => match sizedness {
            // Never `Sized`
            SizedTraitKind::Sized => Some(ty),
            // Always `MetaSized`
            SizedTraitKind::MetaSized => None,
        },

        // Maybe `Sized` or `MetaSized`
        Param(..) | Alias(..) | Error(_) => Some(ty),

        // We cannot instantiate the binder, so just return the *original* type back,
        // but only if the inner type has a sized constraint. Thus we skip the binder,
        // but don't actually use the result from `sized_constraint_for_ty`.
        UnsafeBinder(inner_ty) => {
            sizedness_constraint_for_ty(interner, sizedness, inner_ty.skip_binder()).map(|_| ty)
        }

        // Never `MetaSized` or `Sized`
        Foreign(..) => Some(ty),

        // Recursive cases
        Pat(ty, _) => sizedness_constraint_for_ty(interner, sizedness, ty),

        Tuple(tys) => tys
            .into_iter()
            .last()
            .and_then(|ty| sizedness_constraint_for_ty(interner, sizedness, ty)),

        Adt(adt, args) => {
            let tail_ty =
                EarlyBinder::bind(adt.all_field_tys(interner).skip_binder().into_iter().last()?)
                    .instantiate(interner, args);
            sizedness_constraint_for_ty(interner, sizedness, tail_ty)
        }

        Placeholder(..) | Bound(..) | Infer(..) => {
            panic!("unexpected type `{ty:?}` in sizedness_constraint_for_ty")
        }
    }
}

pub fn apply_args_to_binder<'db, T: TypeFoldable<DbInterner<'db>>>(
    b: Binder<'db, T>,
    args: GenericArgs<'db>,
    interner: DbInterner<'db>,
) -> T {
    let types = &mut |ty: BoundTy| args.as_slice()[ty.var.index()].expect_ty();
    let regions = &mut |region: BoundRegion| args.as_slice()[region.var.index()].expect_region();
    let consts = &mut |const_: BoundConst| args.as_slice()[const_.var.index()].expect_const();
    let mut instantiate = BoundVarReplacer::new(interner, FnMutDelegate { types, regions, consts });
    b.skip_binder().fold_with(&mut instantiate)
}

pub(crate) fn mini_canonicalize<'db, T: TypeFoldable<DbInterner<'db>>>(
    mut context: SolverContext<'db>,
    val: T,
) -> Canonical<DbInterner<'db>, T> {
    let mut canon = MiniCanonicalizer {
        context: &mut context,
        db: DebruijnIndex::ZERO,
        vars: IndexMap::default(),
    };
    let canon_val = val.fold_with(&mut canon);
    let vars = canon.vars;
    Canonical {
        value: canon_val,
        max_universe: UniverseIndex::from_u32(1),
        variables: CanonicalVars::new_from_iter(
            context.cx(),
            vars.iter().enumerate().map(|(idx, (k, v))| match (*k).kind() {
                GenericArgKind::Type(ty) => match ty.kind() {
                    TyKind::Int(..) | TyKind::Uint(..) => rustc_type_ir::CanonicalVarKind::Int,
                    TyKind::Float(..) => rustc_type_ir::CanonicalVarKind::Float,
                    _ => rustc_type_ir::CanonicalVarKind::Ty {
                        ui: UniverseIndex::ZERO,
                        sub_root: BoundVar::from_usize(idx),
                    },
                },
                GenericArgKind::Lifetime(_) => {
                    rustc_type_ir::CanonicalVarKind::Region(UniverseIndex::ZERO)
                }
                GenericArgKind::Const(_) => {
                    rustc_type_ir::CanonicalVarKind::Const(UniverseIndex::ZERO)
                }
            }),
        ),
    }
}

struct MiniCanonicalizer<'a, 'db> {
    context: &'a mut SolverContext<'db>,
    db: DebruijnIndex,
    vars: IndexMap<GenericArg<'db>, usize>,
}

impl<'db> TypeFolder<DbInterner<'db>> for MiniCanonicalizer<'_, 'db> {
    fn cx(&self) -> DbInterner<'db> {
        self.context.cx()
    }

    fn fold_binder<T: TypeFoldable<DbInterner<'db>>>(
        &mut self,
        t: rustc_type_ir::Binder<DbInterner<'db>, T>,
    ) -> rustc_type_ir::Binder<DbInterner<'db>, T> {
        self.db.shift_in(1);
        let res = t.map_bound(|t| t.fold_with(self));
        self.db.shift_out(1);
        res
    }

    fn fold_ty(&mut self, t: Ty<'db>) -> Ty<'db> {
        match t.kind() {
            rustc_type_ir::TyKind::Bound(db, _) => {
                if db >= self.db {
                    panic!("Unexpected bound var");
                }
                t
            }
            rustc_type_ir::TyKind::Infer(infer) => {
                let t = match infer {
                    rustc_type_ir::InferTy::TyVar(vid) => {
                        self.context.opportunistic_resolve_ty_var(vid)
                    }
                    rustc_type_ir::InferTy::IntVar(vid) => {
                        self.context.opportunistic_resolve_int_var(vid)
                    }
                    rustc_type_ir::InferTy::FloatVar(vid) => {
                        self.context.opportunistic_resolve_float_var(vid)
                    }
                    _ => t,
                };
                let len = self.vars.len();
                let var = *self.vars.entry(t.into()).or_insert(len);
                Ty::new(
                    self.cx(),
                    TyKind::Bound(
                        self.db,
                        BoundTy { kind: super::BoundTyKind::Anon, var: BoundVar::from_usize(var) },
                    ),
                )
            }
            _ => t.super_fold_with(self),
        }
    }

    fn fold_region(
        &mut self,
        r: <DbInterner<'db> as rustc_type_ir::Interner>::Region,
    ) -> <DbInterner<'db> as rustc_type_ir::Interner>::Region {
        match r.kind() {
            RegionKind::ReBound(db, _) => {
                if db >= self.db {
                    panic!("Unexpected bound var");
                }
                r
            }
            RegionKind::ReVar(vid) => {
                let len = self.vars.len();
                let var = *self.vars.entry(r.into()).or_insert(len);
                Region::new(
                    self.cx(),
                    RegionKind::ReBound(
                        self.db,
                        BoundRegion {
                            kind: super::BoundRegionKind::Anon,
                            var: BoundVar::from_usize(var),
                        },
                    ),
                )
            }
            _ => r,
        }
    }

    fn fold_const(
        &mut self,
        c: <DbInterner<'db> as rustc_type_ir::Interner>::Const,
    ) -> <DbInterner<'db> as rustc_type_ir::Interner>::Const {
        match c.kind() {
            ConstKind::Bound(db, _) => {
                if db >= self.db {
                    panic!("Unexpected bound var");
                }
                c
            }
            ConstKind::Infer(infer) => {
                let len = self.vars.len();
                let var = *self.vars.entry(c.into()).or_insert(len);
                Const::new(
                    self.cx(),
                    ConstKind::Bound(self.db, BoundConst { var: BoundVar::from_usize(var) }),
                )
            }
            _ => c.super_fold_with(self),
        }
    }
}

pub fn explicit_item_bounds<'db>(
    interner: DbInterner<'db>,
    def_id: SolverDefId,
) -> EarlyBinder<'db, Clauses<'db>> {
    let db = interner.db();
    match def_id {
        SolverDefId::TypeAliasId(type_alias) => {
            let trait_ = match type_alias.lookup(db).container {
                ItemContainerId::TraitId(t) => t,
                _ => panic!("associated type not in trait"),
            };

            // Lower bounds -- we could/should maybe move this to a separate query in `lower`
            let type_alias_data = db.type_alias_signature(type_alias);
            let generic_params = generics(db, type_alias.into());
            let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db);
            let mut ctx = TyLoweringContext::new(
                db,
                &resolver,
                &type_alias_data.store,
                type_alias.into(),
                LifetimeElisionKind::AnonymousReportError,
            );

            let item_args = GenericArgs::identity_for_item(interner, def_id);
            let interner_ty = Ty::new_projection_from_args(interner, def_id, item_args);

            let mut bounds = Vec::new();
            for bound in &type_alias_data.bounds {
                ctx.lower_type_bound(bound, interner_ty, false).for_each(|pred| {
                    bounds.push(pred);
                });
            }

            if !ctx.unsized_types.contains(&interner_ty) {
                let sized_trait = LangItem::Sized
                    .resolve_trait(ctx.db, interner.krate.expect("Must have interner.krate"));
                let sized_bound = sized_trait.map(|trait_id| {
                    let trait_ref = TraitRef::new_from_args(
                        interner,
                        trait_id.into(),
                        GenericArgs::new_from_iter(interner, [interner_ty.into()]),
                    );
                    Clause(Predicate::new(
                        interner,
                        Binder::dummy(rustc_type_ir::PredicateKind::Clause(
                            rustc_type_ir::ClauseKind::Trait(TraitPredicate {
                                trait_ref,
                                polarity: rustc_type_ir::PredicatePolarity::Positive,
                            }),
                        )),
                    ))
                });
                bounds.extend(sized_bound);
                bounds.shrink_to_fit();
            }

            rustc_type_ir::EarlyBinder::bind(Clauses::new_from_iter(interner, bounds))
        }
        SolverDefId::InternedOpaqueTyId(id) => {
            let full_id = db.lookup_intern_impl_trait_id(id);
            match full_id {
                crate::ImplTraitId::ReturnTypeImplTrait(func, idx) => {
                    let datas = db
                        .return_type_impl_traits_ns(func)
                        .expect("impl trait id without impl traits");
                    let datas = (*datas).as_ref().skip_binder();
                    let data = &datas.impl_traits[Idx::from_raw(idx.into_raw())];
                    EarlyBinder::bind(Clauses::new_from_iter(interner, data.predicates.clone()))
                }
                crate::ImplTraitId::TypeAliasImplTrait(alias, idx) => {
                    let datas = db
                        .type_alias_impl_traits_ns(alias)
                        .expect("impl trait id without impl traits");
                    let datas = (*datas).as_ref().skip_binder();
                    let data = &datas.impl_traits[Idx::from_raw(idx.into_raw())];
                    EarlyBinder::bind(Clauses::new_from_iter(interner, data.predicates.clone()))
                }
                crate::ImplTraitId::AsyncBlockTypeImplTrait(..) => {
                    if let Some((future_trait, future_output)) = LangItem::Future
                        .resolve_trait(db, interner.krate.expect("Must have interner.krate"))
                        .and_then(|trait_| {
                            let alias = trait_.trait_items(db).associated_type_by_name(
                                &hir_expand::name::Name::new_symbol_root(sym::Output.clone()),
                            )?;
                            Some((trait_, alias))
                        })
                    {
                        let args = GenericArgs::identity_for_item(interner, def_id);
                        let out = args.as_slice()[0];
                        let mut predicates = vec![];

                        let item_ty = Ty::new_alias(
                            interner,
                            rustc_type_ir::AliasTyKind::Opaque,
                            AliasTy::new_from_args(interner, def_id, args),
                        );

                        let kind = PredicateKind::Clause(ClauseKind::Trait(TraitPredicate {
                            polarity: rustc_type_ir::PredicatePolarity::Positive,
                            trait_ref: TraitRef::new_from_args(
                                interner,
                                future_trait.into(),
                                GenericArgs::new_from_iter(interner, [item_ty.into()]),
                            ),
                        }));
                        predicates.push(Clause(Predicate::new(
                            interner,
                            Binder::bind_with_vars(
                                kind,
                                BoundVarKinds::new_from_iter(
                                    interner,
                                    [BoundVarKind::Ty(BoundTyKind::Anon)],
                                ),
                            ),
                        )));
                        let sized_trait = LangItem::Sized
                            .resolve_trait(db, interner.krate.expect("Must have interner.krate"));
                        if let Some(sized_trait_) = sized_trait {
                            let kind = PredicateKind::Clause(ClauseKind::Trait(TraitPredicate {
                                polarity: rustc_type_ir::PredicatePolarity::Positive,
                                trait_ref: TraitRef::new_from_args(
                                    interner,
                                    sized_trait_.into(),
                                    GenericArgs::new_from_iter(interner, [item_ty.into()]),
                                ),
                            }));
                            predicates.push(Clause(Predicate::new(
                                interner,
                                Binder::bind_with_vars(
                                    kind,
                                    BoundVarKinds::new_from_iter(
                                        interner,
                                        [BoundVarKind::Ty(BoundTyKind::Anon)],
                                    ),
                                ),
                            )));
                        }
                        let kind =
                            PredicateKind::Clause(ClauseKind::Projection(ProjectionPredicate {
                                projection_term: AliasTerm::new_from_args(
                                    interner,
                                    future_output.into(),
                                    GenericArgs::new_from_iter(interner, [item_ty.into()]),
                                ),
                                term: match out.kind() {
                                    GenericArgKind::Lifetime(lt) => panic!(),
                                    GenericArgKind::Type(ty) => Term::Ty(ty),
                                    GenericArgKind::Const(const_) => Term::Const(const_),
                                },
                            }));
                        predicates.push(Clause(Predicate::new(
                            interner,
                            Binder::bind_with_vars(
                                kind,
                                BoundVarKinds::new_from_iter(
                                    interner,
                                    [BoundVarKind::Ty(BoundTyKind::Anon)],
                                ),
                            ),
                        )));
                        EarlyBinder::bind(Clauses::new_from_iter(interner, predicates))
                    } else {
                        // If failed to find Symbol’s value as variable is void: Future::Output, return empty bounds as fallback.
                        EarlyBinder::bind(Clauses::new_from_iter(interner, []))
                    }
                }
            }
        }
        _ => panic!("Unexpected GeneridDefId"),
    }
}

pub struct ContainsTypeErrors;

impl<'db> TypeVisitor<DbInterner<'db>> for ContainsTypeErrors {
    type Result = ControlFlow<()>;

    fn visit_ty(&mut self, t: Ty<'db>) -> Self::Result {
        match t.kind() {
            rustc_type_ir::TyKind::Error(_) => ControlFlow::Break(()),
            _ => t.super_visit_with(self),
        }
    }
}

/// The inverse of [`BoundVarReplacer`]: replaces placeholders with the bound vars from which they came.
pub struct PlaceholderReplacer<'a, 'db> {
    infcx: &'a InferCtxt<'db>,
    mapped_regions: FxIndexMap<PlaceholderRegion, BoundRegion>,
    mapped_types: FxIndexMap<Placeholder<BoundTy>, BoundTy>,
    mapped_consts: FxIndexMap<PlaceholderConst, BoundConst>,
    universe_indices: &'a [Option<UniverseIndex>],
    current_index: DebruijnIndex,
}

impl<'a, 'db> PlaceholderReplacer<'a, 'db> {
    pub fn replace_placeholders<T: TypeFoldable<DbInterner<'db>>>(
        infcx: &'a InferCtxt<'db>,
        mapped_regions: FxIndexMap<PlaceholderRegion, BoundRegion>,
        mapped_types: FxIndexMap<Placeholder<BoundTy>, BoundTy>,
        mapped_consts: FxIndexMap<PlaceholderConst, BoundConst>,
        universe_indices: &'a [Option<UniverseIndex>],
        value: T,
    ) -> T {
        let mut replacer = PlaceholderReplacer {
            infcx,
            mapped_regions,
            mapped_types,
            mapped_consts,
            universe_indices,
            current_index: INNERMOST,
        };
        value.fold_with(&mut replacer)
    }
}

impl<'db> TypeFolder<DbInterner<'db>> for PlaceholderReplacer<'_, 'db> {
    fn cx(&self) -> DbInterner<'db> {
        self.infcx.interner
    }

    fn fold_binder<T: TypeFoldable<DbInterner<'db>>>(
        &mut self,
        t: Binder<'db, T>,
    ) -> Binder<'db, T> {
        if !t.has_placeholders() && !t.has_infer() {
            return t;
        }
        self.current_index.shift_in(1);
        let t = t.super_fold_with(self);
        self.current_index.shift_out(1);
        t
    }

    fn fold_region(&mut self, r0: Region<'db>) -> Region<'db> {
        let r1 = match r0.kind() {
            RegionKind::ReVar(vid) => self
                .infcx
                .inner
                .borrow_mut()
                .unwrap_region_constraints()
                .opportunistic_resolve_var(self.infcx.interner, vid),
            _ => r0,
        };

        let r2 = match r1.kind() {
            RegionKind::RePlaceholder(p) => {
                let replace_var = self.mapped_regions.get(&p);
                match replace_var {
                    Some(replace_var) => {
                        let index = self
                            .universe_indices
                            .iter()
                            .position(|u| matches!(u, Some(pu) if *pu == p.universe))
                            .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
                        let db = DebruijnIndex::from_usize(
                            self.universe_indices.len() - index + self.current_index.as_usize() - 1,
                        );
                        Region::new_bound(self.cx(), db, *replace_var)
                    }
                    None => r1,
                }
            }
            _ => r1,
        };

        tracing::debug!(?r0, ?r1, ?r2, "fold_region");

        r2
    }

    fn fold_ty(&mut self, ty: Ty<'db>) -> Ty<'db> {
        let ty = self.infcx.shallow_resolve(ty);
        match ty.kind() {
            TyKind::Placeholder(p) => {
                let replace_var = self.mapped_types.get(&p);
                match replace_var {
                    Some(replace_var) => {
                        let index = self
                            .universe_indices
                            .iter()
                            .position(|u| matches!(u, Some(pu) if *pu == p.universe))
                            .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
                        let db = DebruijnIndex::from_usize(
                            self.universe_indices.len() - index + self.current_index.as_usize() - 1,
                        );
                        Ty::new_bound(self.infcx.interner, db, *replace_var)
                    }
                    None => {
                        if ty.has_infer() {
                            ty.super_fold_with(self)
                        } else {
                            ty
                        }
                    }
                }
            }

            _ if ty.has_placeholders() || ty.has_infer() => ty.super_fold_with(self),
            _ => ty,
        }
    }

    fn fold_const(&mut self, ct: Const<'db>) -> Const<'db> {
        let ct = self.infcx.shallow_resolve_const(ct);
        if let ConstKind::Placeholder(p) = ct.kind() {
            let replace_var = self.mapped_consts.get(&p);
            match replace_var {
                Some(replace_var) => {
                    let index = self
                        .universe_indices
                        .iter()
                        .position(|u| matches!(u, Some(pu) if *pu == p.universe))
                        .unwrap_or_else(|| panic!("Unexpected placeholder universe."));
                    let db = DebruijnIndex::from_usize(
                        self.universe_indices.len() - index + self.current_index.as_usize() - 1,
                    );
                    Const::new_bound(self.infcx.interner, db, *replace_var)
                }
                None => {
                    if ct.has_infer() {
                        ct.super_fold_with(self)
                    } else {
                        ct
                    }
                }
            }
        } else {
            ct.super_fold_with(self)
        }
    }
}

pub(crate) fn needs_normalization<'db, T: TypeVisitable<DbInterner<'db>>>(
    infcx: &InferCtxt<'db>,
    value: &T,
) -> bool {
    let mut flags = TypeFlags::HAS_ALIAS;

    // Opaques are treated as rigid outside of `TypingMode::PostAnalysis`,
    // so we can ignore those.
    match infcx.typing_mode() {
        // FIXME(#132279): We likely want to reveal opaques during post borrowck analysis
        TypingMode::Coherence
        | TypingMode::Analysis { .. }
        | TypingMode::Borrowck { .. }
        | TypingMode::PostBorrowckAnalysis { .. } => flags.remove(TypeFlags::HAS_TY_OPAQUE),
        TypingMode::PostAnalysis => {}
    }

    value.has_type_flags(flags)
}

pub fn sizedness_fast_path<'db>(
    tcx: DbInterner<'db>,
    predicate: Predicate<'db>,
    param_env: ParamEnv<'db>,
) -> bool {
    // Proving `Sized`/`MetaSized`, very often on "obviously sized" types like
    // `&T`, accounts for about 60% percentage of the predicates we have to prove. No need to
    // canonicalize and all that for such cases.
    if let PredicateKind::Clause(ClauseKind::Trait(trait_pred)) = predicate.kind().skip_binder()
        && trait_pred.polarity == PredicatePolarity::Positive
    {
        let sizedness = match tcx.as_trait_lang_item(trait_pred.def_id()) {
            Some(SolverTraitLangItem::Sized) => SizedTraitKind::Sized,
            Some(SolverTraitLangItem::MetaSized) => SizedTraitKind::MetaSized,
            _ => return false,
        };

        // FIXME(sized_hierarchy): this temporarily reverts the `sized_hierarchy` feature
        // while a proper fix for `tests/ui/sized-hierarchy/incomplete-inference-issue-143992.rs`
        // is pending a proper fix
        if matches!(sizedness, SizedTraitKind::MetaSized) {
            return true;
        }

        if trait_pred.self_ty().has_trivial_sizedness(tcx, sizedness) {
            tracing::debug!("fast path -- trivial sizedness");
            return true;
        }

        if matches!(trait_pred.self_ty().kind(), TyKind::Param(_) | TyKind::Placeholder(_)) {
            for clause in param_env.caller_bounds().iter() {
                if let ClauseKind::Trait(clause_pred) = clause.kind().skip_binder()
                    && clause_pred.polarity == PredicatePolarity::Positive
                    && clause_pred.self_ty() == trait_pred.self_ty()
                    && (clause_pred.def_id() == trait_pred.def_id()
                        || (sizedness == SizedTraitKind::MetaSized
                            && tcx.is_trait_lang_item(
                                clause_pred.def_id(),
                                SolverTraitLangItem::Sized,
                            )))
                {
                    return true;
                }
            }
        }
    }

    false
}
