diff options
Diffstat (limited to 'compiler/rustc_middle/src/ty/fast_reject.rs')
| -rw-r--r-- | compiler/rustc_middle/src/ty/fast_reject.rs | 405 |
1 files changed, 405 insertions, 0 deletions
diff --git a/compiler/rustc_middle/src/ty/fast_reject.rs b/compiler/rustc_middle/src/ty/fast_reject.rs new file mode 100644 index 000000000..8d019a3ba --- /dev/null +++ b/compiler/rustc_middle/src/ty/fast_reject.rs @@ -0,0 +1,405 @@ +use crate::mir::Mutability; +use crate::ty::subst::GenericArgKind; +use crate::ty::{self, Ty, TyCtxt, TypeVisitable}; +use rustc_hir::def_id::DefId; +use std::fmt::Debug; +use std::hash::Hash; +use std::iter; + +use self::SimplifiedTypeGen::*; + +pub type SimplifiedType = SimplifiedTypeGen<DefId>; + +/// See `simplify_type` +/// +/// Note that we keep this type generic over the type of identifier it uses +/// because we sometimes need to use SimplifiedTypeGen values as stable sorting +/// keys (in which case we use a DefPathHash as id-type) but in the general case +/// the non-stable but fast to construct DefId-version is the better choice. +#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable, HashStable)] +pub enum SimplifiedTypeGen<D> +where + D: Copy + Debug + Eq, +{ + BoolSimplifiedType, + CharSimplifiedType, + IntSimplifiedType(ty::IntTy), + UintSimplifiedType(ty::UintTy), + FloatSimplifiedType(ty::FloatTy), + AdtSimplifiedType(D), + ForeignSimplifiedType(D), + StrSimplifiedType, + ArraySimplifiedType, + SliceSimplifiedType, + RefSimplifiedType(Mutability), + PtrSimplifiedType(Mutability), + NeverSimplifiedType, + TupleSimplifiedType(usize), + /// A trait object, all of whose components are markers + /// (e.g., `dyn Send + Sync`). + MarkerTraitObjectSimplifiedType, + TraitSimplifiedType(D), + ClosureSimplifiedType(D), + GeneratorSimplifiedType(D), + GeneratorWitnessSimplifiedType(usize), + OpaqueSimplifiedType(D), + FunctionSimplifiedType(usize), + PlaceholderSimplifiedType, +} + +/// Generic parameters are pretty much just bound variables, e.g. +/// the type of `fn foo<'a, T>(x: &'a T) -> u32 { ... }` can be thought of as +/// `for<'a, T> fn(&'a T) -> u32`. +/// +/// Typecheck of `foo` has to succeed for all possible generic arguments, so +/// during typeck, we have to treat its generic parameters as if they +/// were placeholders. +/// +/// But when calling `foo` we only have to provide a specific generic argument. +/// In that case the generic parameters are instantiated with inference variables. +/// As we use `simplify_type` before that instantiation happens, we just treat +/// generic parameters as if they were inference variables in that case. +#[derive(PartialEq, Eq, Debug, Clone, Copy)] +pub enum TreatParams { + /// Treat parameters as placeholders in the given environment. + /// + /// Note that this also causes us to treat projections as if they were + /// placeholders. This is only correct if the given projection cannot + /// be normalized in the current context. Even if normalization fails, + /// it may still succeed later if the projection contains any inference + /// variables. + AsPlaceholder, + AsInfer, +} + +/// Tries to simplify a type by only returning the outermost injective¹ layer, if one exists. +/// +/// **This function should only be used if you need to store or retrieve the type from some +/// hashmap. If you want to quickly decide whether two types may unify, use the [DeepRejectCtxt] +/// instead.** +/// +/// The idea is to get something simple that we can use to quickly decide if two types could unify, +/// for example during method lookup. If this function returns `Some(x)` it can only unify with +/// types for which this method returns either `Some(x)` as well or `None`. +/// +/// A special case here are parameters and projections, which are only injective +/// if they are treated as placeholders. +/// +/// For example when storing impls based on their simplified self type, we treat +/// generic parameters as if they were inference variables. We must not simplify them here, +/// as they can unify with any other type. +/// +/// With projections we have to be even more careful, as treating them as placeholders +/// is only correct if they are fully normalized. +/// +/// ¹ meaning that if the outermost layers are different, then the whole types are also different. +pub fn simplify_type<'tcx>( + tcx: TyCtxt<'tcx>, + ty: Ty<'tcx>, + treat_params: TreatParams, +) -> Option<SimplifiedType> { + match *ty.kind() { + ty::Bool => Some(BoolSimplifiedType), + ty::Char => Some(CharSimplifiedType), + ty::Int(int_type) => Some(IntSimplifiedType(int_type)), + ty::Uint(uint_type) => Some(UintSimplifiedType(uint_type)), + ty::Float(float_type) => Some(FloatSimplifiedType(float_type)), + ty::Adt(def, _) => Some(AdtSimplifiedType(def.did())), + ty::Str => Some(StrSimplifiedType), + ty::Array(..) => Some(ArraySimplifiedType), + ty::Slice(..) => Some(SliceSimplifiedType), + ty::RawPtr(ptr) => Some(PtrSimplifiedType(ptr.mutbl)), + ty::Dynamic(trait_info, ..) => match trait_info.principal_def_id() { + Some(principal_def_id) if !tcx.trait_is_auto(principal_def_id) => { + Some(TraitSimplifiedType(principal_def_id)) + } + _ => Some(MarkerTraitObjectSimplifiedType), + }, + ty::Ref(_, _, mutbl) => Some(RefSimplifiedType(mutbl)), + ty::FnDef(def_id, _) | ty::Closure(def_id, _) => Some(ClosureSimplifiedType(def_id)), + ty::Generator(def_id, _, _) => Some(GeneratorSimplifiedType(def_id)), + ty::GeneratorWitness(tys) => Some(GeneratorWitnessSimplifiedType(tys.skip_binder().len())), + ty::Never => Some(NeverSimplifiedType), + ty::Tuple(tys) => Some(TupleSimplifiedType(tys.len())), + ty::FnPtr(f) => Some(FunctionSimplifiedType(f.skip_binder().inputs().len())), + ty::Placeholder(..) => Some(PlaceholderSimplifiedType), + ty::Param(_) => match treat_params { + TreatParams::AsPlaceholder => Some(PlaceholderSimplifiedType), + TreatParams::AsInfer => None, + }, + ty::Projection(_) => match treat_params { + // When treating `ty::Param` as a placeholder, projections also + // don't unify with anything else as long as they are fully normalized. + // + // We will have to be careful with lazy normalization here. + TreatParams::AsPlaceholder if !ty.has_infer_types_or_consts() => { + debug!("treating `{}` as a placeholder", ty); + Some(PlaceholderSimplifiedType) + } + TreatParams::AsPlaceholder | TreatParams::AsInfer => None, + }, + ty::Opaque(def_id, _) => Some(OpaqueSimplifiedType(def_id)), + ty::Foreign(def_id) => Some(ForeignSimplifiedType(def_id)), + ty::Bound(..) | ty::Infer(_) | ty::Error(_) => None, + } +} + +impl<D: Copy + Debug + Eq> SimplifiedTypeGen<D> { + pub fn def(self) -> Option<D> { + match self { + AdtSimplifiedType(d) + | ForeignSimplifiedType(d) + | TraitSimplifiedType(d) + | ClosureSimplifiedType(d) + | GeneratorSimplifiedType(d) + | OpaqueSimplifiedType(d) => Some(d), + _ => None, + } + } + + pub fn map_def<U, F>(self, map: F) -> SimplifiedTypeGen<U> + where + F: Fn(D) -> U, + U: Copy + Debug + Eq, + { + match self { + BoolSimplifiedType => BoolSimplifiedType, + CharSimplifiedType => CharSimplifiedType, + IntSimplifiedType(t) => IntSimplifiedType(t), + UintSimplifiedType(t) => UintSimplifiedType(t), + FloatSimplifiedType(t) => FloatSimplifiedType(t), + AdtSimplifiedType(d) => AdtSimplifiedType(map(d)), + ForeignSimplifiedType(d) => ForeignSimplifiedType(map(d)), + StrSimplifiedType => StrSimplifiedType, + ArraySimplifiedType => ArraySimplifiedType, + SliceSimplifiedType => SliceSimplifiedType, + RefSimplifiedType(m) => RefSimplifiedType(m), + PtrSimplifiedType(m) => PtrSimplifiedType(m), + NeverSimplifiedType => NeverSimplifiedType, + MarkerTraitObjectSimplifiedType => MarkerTraitObjectSimplifiedType, + TupleSimplifiedType(n) => TupleSimplifiedType(n), + TraitSimplifiedType(d) => TraitSimplifiedType(map(d)), + ClosureSimplifiedType(d) => ClosureSimplifiedType(map(d)), + GeneratorSimplifiedType(d) => GeneratorSimplifiedType(map(d)), + GeneratorWitnessSimplifiedType(n) => GeneratorWitnessSimplifiedType(n), + OpaqueSimplifiedType(d) => OpaqueSimplifiedType(map(d)), + FunctionSimplifiedType(n) => FunctionSimplifiedType(n), + PlaceholderSimplifiedType => PlaceholderSimplifiedType, + } + } +} + +/// Given generic arguments from an obligation and an impl, +/// could these two be unified after replacing parameters in the +/// the impl with inference variables. +/// +/// For obligations, parameters won't be replaced by inference +/// variables and only unify with themselves. We treat them +/// the same way we treat placeholders. +/// +/// We also use this function during coherence. For coherence the +/// impls only have to overlap for some value, so we treat parameters +/// on both sides like inference variables. This behavior is toggled +/// using the `treat_obligation_params` field. +#[derive(Debug, Clone, Copy)] +pub struct DeepRejectCtxt { + pub treat_obligation_params: TreatParams, +} + +impl DeepRejectCtxt { + pub fn generic_args_may_unify<'tcx>( + self, + obligation_arg: ty::GenericArg<'tcx>, + impl_arg: ty::GenericArg<'tcx>, + ) -> bool { + match (obligation_arg.unpack(), impl_arg.unpack()) { + // We don't fast reject based on regions for now. + (GenericArgKind::Lifetime(_), GenericArgKind::Lifetime(_)) => true, + (GenericArgKind::Type(obl), GenericArgKind::Type(imp)) => { + self.types_may_unify(obl, imp) + } + (GenericArgKind::Const(obl), GenericArgKind::Const(imp)) => { + self.consts_may_unify(obl, imp) + } + _ => bug!("kind mismatch: {obligation_arg} {impl_arg}"), + } + } + + pub fn types_may_unify<'tcx>(self, obligation_ty: Ty<'tcx>, impl_ty: Ty<'tcx>) -> bool { + match impl_ty.kind() { + // Start by checking whether the type in the impl may unify with + // pretty much everything. Just return `true` in that case. + ty::Param(_) | ty::Projection(_) | ty::Error(_) => return true, + // These types only unify with inference variables or their own + // variant. + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Adt(..) + | ty::Str + | ty::Array(..) + | ty::Slice(..) + | ty::RawPtr(..) + | ty::Dynamic(..) + | ty::Ref(..) + | ty::Never + | ty::Tuple(..) + | ty::FnPtr(..) + | ty::Foreign(..) + | ty::Opaque(..) => {} + ty::FnDef(..) + | ty::Closure(..) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::Placeholder(..) + | ty::Bound(..) + | ty::Infer(_) => bug!("unexpected impl_ty: {impl_ty}"), + } + + let k = impl_ty.kind(); + match *obligation_ty.kind() { + // Purely rigid types, use structural equivalence. + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Str + | ty::Never + | ty::Foreign(_) => obligation_ty == impl_ty, + ty::Ref(_, obl_ty, obl_mutbl) => match k { + &ty::Ref(_, impl_ty, impl_mutbl) => { + obl_mutbl == impl_mutbl && self.types_may_unify(obl_ty, impl_ty) + } + _ => false, + }, + ty::Adt(obl_def, obl_substs) => match k { + &ty::Adt(impl_def, impl_substs) => { + obl_def == impl_def + && iter::zip(obl_substs, impl_substs) + .all(|(obl, imp)| self.generic_args_may_unify(obl, imp)) + } + _ => false, + }, + ty::Slice(obl_ty) => { + matches!(k, &ty::Slice(impl_ty) if self.types_may_unify(obl_ty, impl_ty)) + } + ty::Array(obl_ty, obl_len) => match k { + &ty::Array(impl_ty, impl_len) => { + self.types_may_unify(obl_ty, impl_ty) + && self.consts_may_unify(obl_len, impl_len) + } + _ => false, + }, + ty::Tuple(obl) => match k { + &ty::Tuple(imp) => { + obl.len() == imp.len() + && iter::zip(obl, imp).all(|(obl, imp)| self.types_may_unify(obl, imp)) + } + _ => false, + }, + ty::RawPtr(obl) => match k { + ty::RawPtr(imp) => obl.mutbl == imp.mutbl && self.types_may_unify(obl.ty, imp.ty), + _ => false, + }, + ty::Dynamic(obl_preds, ..) => { + // Ideally we would walk the existential predicates here or at least + // compare their length. But considering that the relevant `Relate` impl + // actually sorts and deduplicates these, that doesn't work. + matches!(k, ty::Dynamic(impl_preds, ..) if + obl_preds.principal_def_id() == impl_preds.principal_def_id() + ) + } + ty::FnPtr(obl_sig) => match k { + ty::FnPtr(impl_sig) => { + let ty::FnSig { inputs_and_output, c_variadic, unsafety, abi } = + obl_sig.skip_binder(); + let impl_sig = impl_sig.skip_binder(); + + abi == impl_sig.abi + && c_variadic == impl_sig.c_variadic + && unsafety == impl_sig.unsafety + && inputs_and_output.len() == impl_sig.inputs_and_output.len() + && iter::zip(inputs_and_output, impl_sig.inputs_and_output) + .all(|(obl, imp)| self.types_may_unify(obl, imp)) + } + _ => false, + }, + + // Opaque types in impls should be forbidden, but that doesn't + // stop compilation. So this match arm should never return true + // if compilation succeeds. + ty::Opaque(..) => matches!(k, ty::Opaque(..)), + + // Impls cannot contain these types as these cannot be named directly. + ty::FnDef(..) | ty::Closure(..) | ty::Generator(..) => false, + + ty::Placeholder(..) => false, + + // Depending on the value of `treat_obligation_params`, we either + // treat generic parameters like placeholders or like inference variables. + ty::Param(_) => match self.treat_obligation_params { + TreatParams::AsPlaceholder => false, + TreatParams::AsInfer => true, + }, + + ty::Infer(_) => true, + + // As we're walking the whole type, it may encounter projections + // inside of binders and what not, so we're just going to assume that + // projections can unify with other stuff. + // + // Looking forward to lazy normalization this is the safer strategy anyways. + ty::Projection(_) => true, + + ty::Error(_) => true, + + ty::GeneratorWitness(..) | ty::Bound(..) => { + bug!("unexpected obligation type: {:?}", obligation_ty) + } + } + } + + pub fn consts_may_unify(self, obligation_ct: ty::Const<'_>, impl_ct: ty::Const<'_>) -> bool { + match impl_ct.kind() { + ty::ConstKind::Param(_) | ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => { + return true; + } + ty::ConstKind::Value(_) => {} + ty::ConstKind::Infer(_) | ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => { + bug!("unexpected impl arg: {:?}", impl_ct) + } + } + + let k = impl_ct.kind(); + match obligation_ct.kind() { + ty::ConstKind::Param(_) => match self.treat_obligation_params { + TreatParams::AsPlaceholder => false, + TreatParams::AsInfer => true, + }, + + // As we don't necessarily eagerly evaluate constants, + // they might unify with any value. + ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => true, + ty::ConstKind::Value(obl) => match k { + ty::ConstKind::Value(imp) => { + // FIXME(valtrees): Once we have valtrees, we can just + // compare them directly here. + match (obl.try_to_scalar_int(), imp.try_to_scalar_int()) { + (Some(obl), Some(imp)) => obl == imp, + _ => true, + } + } + _ => true, + }, + + ty::ConstKind::Infer(_) => true, + + ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => { + bug!("unexpected obl const: {:?}", obligation_ct) + } + } + } +} |