From a87579500a2c35597071efd0ad6983927f0c1815 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Wed, 27 Nov 2019 17:46:02 +0300 Subject: Move Ty --- crates/ra_hir_ty/src/infer/coerce.rs | 354 +++++++++++++++++++++++++++++++++++ 1 file changed, 354 insertions(+) create mode 100644 crates/ra_hir_ty/src/infer/coerce.rs (limited to 'crates/ra_hir_ty/src/infer/coerce.rs') diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs new file mode 100644 index 000000000..d66a21932 --- /dev/null +++ b/crates/ra_hir_ty/src/infer/coerce.rs @@ -0,0 +1,354 @@ +//! Coercion logic. Coercions are certain type conversions that can implicitly +//! happen in certain places, e.g. weakening `&mut` to `&` or deref coercions +//! like going from `&Vec` to `&[T]`. +//! +//! See: https://doc.rust-lang.org/nomicon/coercions.html + +use hir_def::{ + lang_item::LangItemTarget, + resolver::{HasResolver, Resolver}, + type_ref::Mutability, + AdtId, +}; +use rustc_hash::FxHashMap; +use test_utils::tested_by; + +use crate::{autoderef, db::HirDatabase, Substs, TraitRef, Ty, TypeCtor, TypeWalk}; + +use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue}; + +impl<'a, D: HirDatabase> InferenceContext<'a, D> { + /// Unify two types, but may coerce the first one to the second one + /// using "implicit coercion rules" if needed. + pub(super) fn coerce(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool { + let from_ty = self.resolve_ty_shallow(from_ty).into_owned(); + let to_ty = self.resolve_ty_shallow(to_ty); + self.coerce_inner(from_ty, &to_ty) + } + + /// Merge two types from different branches, with possible implicit coerce. + /// + /// Note that it is only possible that one type are coerced to another. + /// Coercing both types to another least upper bound type is not possible in rustc, + /// which will simply result in "incompatible types" error. + pub(super) fn coerce_merge_branch<'t>(&mut self, ty1: &Ty, ty2: &Ty) -> Ty { + if self.coerce(ty1, ty2) { + ty2.clone() + } else if self.coerce(ty2, ty1) { + ty1.clone() + } else { + tested_by!(coerce_merge_fail_fallback); + // For incompatible types, we use the latter one as result + // to be better recovery for `if` without `else`. + ty2.clone() + } + } + + pub(super) fn init_coerce_unsized_map( + db: &'a D, + resolver: &Resolver, + ) -> FxHashMap<(TypeCtor, TypeCtor), usize> { + let krate = resolver.krate().unwrap(); + let impls = match db.lang_item(krate.into(), "coerce_unsized".into()) { + Some(LangItemTarget::TraitId(trait_)) => { + db.impls_for_trait(krate.into(), trait_.into()) + } + _ => return FxHashMap::default(), + }; + + impls + .iter() + .filter_map(|&impl_id| { + let impl_data = db.impl_data(impl_id); + let resolver = impl_id.resolver(db); + let target_ty = Ty::from_hir(db, &resolver, &impl_data.target_type); + + // `CoerseUnsized` has one generic parameter for the target type. + let trait_ref = TraitRef::from_hir( + db, + &resolver, + impl_data.target_trait.as_ref()?, + Some(target_ty), + )?; + let cur_from_ty = trait_ref.substs.0.get(0)?; + let cur_to_ty = trait_ref.substs.0.get(1)?; + + match (&cur_from_ty, cur_to_ty) { + (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => { + // FIXME: We return the first non-equal bound as the type parameter to coerce to unsized type. + // This works for smart-pointer-like coercion, which covers all impls from std. + st1.iter().zip(st2.iter()).enumerate().find_map(|(i, (ty1, ty2))| { + match (ty1, ty2) { + (Ty::Param { idx: p1, .. }, Ty::Param { idx: p2, .. }) + if p1 != p2 => + { + Some(((*ctor1, *ctor2), i)) + } + _ => None, + } + }) + } + _ => None, + } + }) + .collect() + } + + fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool { + match (&from_ty, to_ty) { + // Never type will make type variable to fallback to Never Type instead of Unknown. + (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => { + let var = self.new_maybe_never_type_var(); + self.var_unification_table.union_value(*tv, TypeVarValue::Known(var)); + return true; + } + (ty_app!(TypeCtor::Never), _) => return true, + + // Trivial cases, this should go after `never` check to + // avoid infer result type to be never + _ => { + if self.unify_inner_trivial(&from_ty, &to_ty) { + return true; + } + } + } + + // Pointer weakening and function to pointer + match (&mut from_ty, to_ty) { + // `*mut T`, `&mut T, `&T`` -> `*const T` + // `&mut T` -> `&T` + // `&mut T` -> `*mut T` + (ty_app!(c1@TypeCtor::RawPtr(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared))) + | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared))) + | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::Ref(Mutability::Shared))) + | (ty_app!(c1@TypeCtor::Ref(Mutability::Mut)), ty_app!(c2@TypeCtor::RawPtr(_))) => { + *c1 = *c2; + } + + // Illegal mutablity conversion + ( + ty_app!(TypeCtor::RawPtr(Mutability::Shared)), + ty_app!(TypeCtor::RawPtr(Mutability::Mut)), + ) + | ( + ty_app!(TypeCtor::Ref(Mutability::Shared)), + ty_app!(TypeCtor::Ref(Mutability::Mut)), + ) => return false, + + // `{function_type}` -> `fn()` + (ty_app!(TypeCtor::FnDef(_)), ty_app!(TypeCtor::FnPtr { .. })) => { + match from_ty.callable_sig(self.db) { + None => return false, + Some(sig) => { + let num_args = sig.params_and_return.len() as u16 - 1; + from_ty = + Ty::apply(TypeCtor::FnPtr { num_args }, Substs(sig.params_and_return)); + } + } + } + + _ => {} + } + + if let Some(ret) = self.try_coerce_unsized(&from_ty, &to_ty) { + return ret; + } + + // Auto Deref if cannot coerce + match (&from_ty, to_ty) { + // FIXME: DerefMut + (ty_app!(TypeCtor::Ref(_), st1), ty_app!(TypeCtor::Ref(_), st2)) => { + self.unify_autoderef_behind_ref(&st1[0], &st2[0]) + } + + // Otherwise, normal unify + _ => self.unify(&from_ty, to_ty), + } + } + + /// Coerce a type using `from_ty: CoerceUnsized` + /// + /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html + fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option { + let (ctor1, st1, ctor2, st2) = match (from_ty, to_ty) { + (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => (ctor1, st1, ctor2, st2), + _ => return None, + }; + + let coerce_generic_index = *self.coerce_unsized_map.get(&(*ctor1, *ctor2))?; + + // Check `Unsize` first + match self.check_unsize_and_coerce( + st1.0.get(coerce_generic_index)?, + st2.0.get(coerce_generic_index)?, + 0, + ) { + Some(true) => {} + ret => return ret, + } + + let ret = st1 + .iter() + .zip(st2.iter()) + .enumerate() + .filter(|&(idx, _)| idx != coerce_generic_index) + .all(|(_, (ty1, ty2))| self.unify(ty1, ty2)); + + Some(ret) + } + + /// Check if `from_ty: Unsize`, and coerce to `to_ty` if it holds. + /// + /// It should not be directly called. It is only used by `try_coerce_unsized`. + /// + /// See: https://doc.rust-lang.org/nightly/std/marker/trait.Unsize.html + fn check_unsize_and_coerce(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> Option { + if depth > 1000 { + panic!("Infinite recursion in coercion"); + } + + match (&from_ty, &to_ty) { + // `[T; N]` -> `[T]` + (ty_app!(TypeCtor::Array, st1), ty_app!(TypeCtor::Slice, st2)) => { + Some(self.unify(&st1[0], &st2[0])) + } + + // `T` -> `dyn Trait` when `T: Trait` + (_, Ty::Dyn(_)) => { + // FIXME: Check predicates + Some(true) + } + + // `(..., T)` -> `(..., U)` when `T: Unsize` + ( + ty_app!(TypeCtor::Tuple { cardinality: len1 }, st1), + ty_app!(TypeCtor::Tuple { cardinality: len2 }, st2), + ) => { + if len1 != len2 || *len1 == 0 { + return None; + } + + match self.check_unsize_and_coerce( + st1.last().unwrap(), + st2.last().unwrap(), + depth + 1, + ) { + Some(true) => {} + ret => return ret, + } + + let ret = st1[..st1.len() - 1] + .iter() + .zip(&st2[..st2.len() - 1]) + .all(|(ty1, ty2)| self.unify(ty1, ty2)); + + Some(ret) + } + + // Foo<..., T, ...> is Unsize> if: + // - T: Unsize + // - Foo is a struct + // - Only the last field of Foo has a type involving T + // - T is not part of the type of any other fields + // - Bar: Unsize>, if the last field of Foo has type Bar + ( + ty_app!(TypeCtor::Adt(AdtId::StructId(struct1)), st1), + ty_app!(TypeCtor::Adt(AdtId::StructId(struct2)), st2), + ) if struct1 == struct2 => { + let field_tys = self.db.field_types((*struct1).into()); + let struct_data = self.db.struct_data(*struct1); + + let mut fields = struct_data.variant_data.fields().iter(); + let (last_field_id, _data) = fields.next_back()?; + + // Get the generic parameter involved in the last field. + let unsize_generic_index = { + let mut index = None; + let mut multiple_param = false; + field_tys[last_field_id].walk(&mut |ty| match ty { + &Ty::Param { idx, .. } => { + if index.is_none() { + index = Some(idx); + } else if Some(idx) != index { + multiple_param = true; + } + } + _ => {} + }); + + if multiple_param { + return None; + } + index? + }; + + // Check other fields do not involve it. + let mut multiple_used = false; + fields.for_each(|(field_id, _data)| { + field_tys[field_id].walk(&mut |ty| match ty { + &Ty::Param { idx, .. } if idx == unsize_generic_index => { + multiple_used = true + } + _ => {} + }) + }); + if multiple_used { + return None; + } + + let unsize_generic_index = unsize_generic_index as usize; + + // Check `Unsize` first + match self.check_unsize_and_coerce( + st1.get(unsize_generic_index)?, + st2.get(unsize_generic_index)?, + depth + 1, + ) { + Some(true) => {} + ret => return ret, + } + + // Then unify other parameters + let ret = st1 + .iter() + .zip(st2.iter()) + .enumerate() + .filter(|&(idx, _)| idx != unsize_generic_index) + .all(|(_, (ty1, ty2))| self.unify(ty1, ty2)); + + Some(ret) + } + + _ => None, + } + } + + /// Unify `from_ty` to `to_ty` with optional auto Deref + /// + /// Note that the parameters are already stripped the outer reference. + fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool { + let canonicalized = self.canonicalizer().canonicalize_ty(from_ty.clone()); + let to_ty = self.resolve_ty_shallow(&to_ty); + // FIXME: Auto DerefMut + for derefed_ty in autoderef::autoderef( + self.db, + self.resolver.krate(), + InEnvironment { + value: canonicalized.value.clone(), + environment: self.trait_env.clone(), + }, + ) { + let derefed_ty = canonicalized.decanonicalize_ty(derefed_ty.value); + match (&*self.resolve_ty_shallow(&derefed_ty), &*to_ty) { + // Stop when constructor matches. + (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => { + // It will not recurse to `coerce`. + return self.unify_substs(st1, st2, 0); + } + _ => {} + } + } + + false + } +} -- cgit v1.2.3