Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/hir-ty/src/next_solver/util.rs')
| -rw-r--r-- | crates/hir-ty/src/next_solver/util.rs | 1064 |
1 files changed, 1064 insertions, 0 deletions
diff --git a/crates/hir-ty/src/next_solver/util.rs b/crates/hir-ty/src/next_solver/util.rs new file mode 100644 index 0000000000..a7f9817f9c --- /dev/null +++ b/crates/hir-ty/src/next_solver/util.rs @@ -0,0 +1,1064 @@ +//! 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_self_and_deps = db.trait_impls_in_deps(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)); + for it in in_self_and_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(_, _) => 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 +} |