crates/ra_hir_ty/src/infer/coerce.rs

   1 //! Coercion logic. Coercions are certain type conversions that can implicitly
   2 //! happen in certain places, e.g. weakening `&mut` to `&` or deref coercions
   3 //! like going from `&Vec<T>` to `&[T]`.
   4 //!
   5 //! See: https://doc.rust-lang.org/nomicon/coercions.html
   6
   7 use hir_def::{lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AdtId};
   8 use rustc_hash::FxHashMap;
   9 use test_utils::tested_by;
  10
  11 use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk};
  12
  13 use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext};
  14
  15 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
  16     /// Unify two types, but may coerce the first one to the second one
  17     /// using "implicit coercion rules" if needed.
  18     pub(super) fn coerce(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
  19         let from_ty = self.resolve_ty_shallow(from_ty).into_owned();
  20         let to_ty = self.resolve_ty_shallow(to_ty);
  21         self.coerce_inner(from_ty, &to_ty)
  22     }
  23
  24     /// Merge two types from different branches, with possible implicit coerce.
  25     ///
  26     /// Note that it is only possible that one type are coerced to another.
  27     /// Coercing both types to another least upper bound type is not possible in rustc,
  28     /// which will simply result in "incompatible types" error.
  29     pub(super) fn coerce_merge_branch<'t>(&mut self, ty1: &Ty, ty2: &Ty) -> Ty {
  30         if self.coerce(ty1, ty2) {
  31             ty2.clone()
  32         } else if self.coerce(ty2, ty1) {
  33             ty1.clone()
  34         } else {
  35             tested_by!(coerce_merge_fail_fallback);
  36             // For incompatible types, we use the latter one as result
  37             // to be better recovery for `if` without `else`.
  38             ty2.clone()
  39         }
  40     }
  41
  42     pub(super) fn init_coerce_unsized_map(
  43         db: &'a D,
  44         resolver: &Resolver,
  45     ) -> FxHashMap<(TypeCtor, TypeCtor), usize> {
  46         let krate = resolver.krate().unwrap();
  47         let impls = match db.lang_item(krate.into(), "coerce_unsized".into()) {
  48             Some(LangItemTarget::TraitId(trait_)) => {
  49                 db.impls_for_trait(krate.into(), trait_.into())
  50             }
  51             _ => return FxHashMap::default(),
  52         };
  53
  54         impls
  55             .iter()
  56             .filter_map(|&impl_id| {
  57                 let trait_ref = db.impl_trait(impl_id)?;
  58
  59                 // `CoerseUnsized` has one generic parameter for the target type.
  60                 let cur_from_ty = trait_ref.substs.0.get(0)?;
  61                 let cur_to_ty = trait_ref.substs.0.get(1)?;
  62
  63                 match (&cur_from_ty, cur_to_ty) {
  64                     (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => {
  65                         // FIXME: We return the first non-equal bound as the type parameter to coerce to unsized type.
  66                         // This works for smart-pointer-like coercion, which covers all impls from std.
  67                         st1.iter().zip(st2.iter()).enumerate().find_map(|(i, (ty1, ty2))| {
  68                             match (ty1, ty2) {
  69                                 (Ty::Param { idx: p1, .. }, Ty::Param { idx: p2, .. })
  70                                     if p1 != p2 =>
  71                                 {
  72                                     Some(((*ctor1, *ctor2), i))
  73                                 }
  74                                 _ => None,
  75                             }
  76                         })
  77                     }
  78                     _ => None,
  79                 }
  80             })
  81             .collect()
  82     }
  83
  84     fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool {
  85         match (&from_ty, to_ty) {
  86             // Never type will make type variable to fallback to Never Type instead of Unknown.
  87             (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => {
  88                 let var = self.table.new_maybe_never_type_var();
  89                 self.table.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
  90                 return true;
  91             }
  92             (ty_app!(TypeCtor::Never), _) => return true,
  93
  94             // Trivial cases, this should go after `never` check to
  95             // avoid infer result type to be never
  96             _ => {
  97                 if self.table.unify_inner_trivial(&from_ty, &to_ty) {
  98                     return true;
  99                 }
 100             }
 101         }
 102
 103         // Pointer weakening and function to pointer
 104         match (&mut from_ty, to_ty) {
 105             // `*mut T`, `&mut T, `&T`` -> `*const T`
 106             // `&mut T` -> `&T`
 107             // `&mut T` -> `*mut T`
 108             (ty_app!(c1@TypeCtor::RawPtr(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
 109             | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
 110             | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::Ref(Mutability::Shared)))
 111             | (ty_app!(c1@TypeCtor::Ref(Mutability::Mut)), ty_app!(c2@TypeCtor::RawPtr(_))) => {
 112                 *c1 = *c2;
 113             }
 114
 115             // Illegal mutablity conversion
 116             (
 117                 ty_app!(TypeCtor::RawPtr(Mutability::Shared)),
 118                 ty_app!(TypeCtor::RawPtr(Mutability::Mut)),
 119             )
 120             | (
 121                 ty_app!(TypeCtor::Ref(Mutability::Shared)),
 122                 ty_app!(TypeCtor::Ref(Mutability::Mut)),
 123             ) => return false,
 124
 125             // `{function_type}` -> `fn()`
 126             (ty_app!(TypeCtor::FnDef(_)), ty_app!(TypeCtor::FnPtr { .. })) => {
 127                 match from_ty.callable_sig(self.db) {
 128                     None => return false,
 129                     Some(sig) => {
 130                         let num_args = sig.params_and_return.len() as u16 - 1;
 131                         from_ty =
 132                             Ty::apply(TypeCtor::FnPtr { num_args }, Substs(sig.params_and_return));
 133                     }
 134                 }
 135             }
 136
 137             (ty_app!(TypeCtor::Closure { .. }, params), ty_app!(TypeCtor::FnPtr { .. })) => {
 138                 from_ty = params[0].clone();
 139             }
 140
 141             _ => {}
 142         }
 143
 144         if let Some(ret) = self.try_coerce_unsized(&from_ty, &to_ty) {
 145             return ret;
 146         }
 147
 148         // Auto Deref if cannot coerce
 149         match (&from_ty, to_ty) {
 150             // FIXME: DerefMut
 151             (ty_app!(TypeCtor::Ref(_), st1), ty_app!(TypeCtor::Ref(_), st2)) => {
 152                 self.unify_autoderef_behind_ref(&st1[0], &st2[0])
 153             }
 154
 155             // Otherwise, normal unify
 156             _ => self.unify(&from_ty, to_ty),
 157         }
 158     }
 159
 160     /// Coerce a type using `from_ty: CoerceUnsized<ty_ty>`
 161     ///
 162     /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html
 163     fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> {
 164         let (ctor1, st1, ctor2, st2) = match (from_ty, to_ty) {
 165             (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => (ctor1, st1, ctor2, st2),
 166             _ => return None,
 167         };
 168
 169         let coerce_generic_index = *self.coerce_unsized_map.get(&(*ctor1, *ctor2))?;
 170
 171         // Check `Unsize` first
 172         match self.check_unsize_and_coerce(
 173             st1.0.get(coerce_generic_index)?,
 174             st2.0.get(coerce_generic_index)?,
 175             0,
 176         ) {
 177             Some(true) => {}
 178             ret => return ret,
 179         }
 180
 181         let ret = st1
 182             .iter()
 183             .zip(st2.iter())
 184             .enumerate()
 185             .filter(|&(idx, _)| idx != coerce_generic_index)
 186             .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
 187
 188         Some(ret)
 189     }
 190
 191     /// Check if `from_ty: Unsize<to_ty>`, and coerce to `to_ty` if it holds.
 192     ///
 193     /// It should not be directly called. It is only used by `try_coerce_unsized`.
 194     ///
 195     /// See: https://doc.rust-lang.org/nightly/std/marker/trait.Unsize.html
 196     fn check_unsize_and_coerce(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> Option<bool> {
 197         if depth > 1000 {
 198             panic!("Infinite recursion in coercion");
 199         }
 200
 201         match (&from_ty, &to_ty) {
 202             // `[T; N]` -> `[T]`
 203             (ty_app!(TypeCtor::Array, st1), ty_app!(TypeCtor::Slice, st2)) => {
 204                 Some(self.unify(&st1[0], &st2[0]))
 205             }
 206
 207             // `T` -> `dyn Trait` when `T: Trait`
 208             (_, Ty::Dyn(_)) => {
 209                 // FIXME: Check predicates
 210                 Some(true)
 211             }
 212
 213             // `(..., T)` -> `(..., U)` when `T: Unsize<U>`
 214             (
 215                 ty_app!(TypeCtor::Tuple { cardinality: len1 }, st1),
 216                 ty_app!(TypeCtor::Tuple { cardinality: len2 }, st2),
 217             ) => {
 218                 if len1 != len2 || *len1 == 0 {
 219                     return None;
 220                 }
 221
 222                 match self.check_unsize_and_coerce(
 223                     st1.last().unwrap(),
 224                     st2.last().unwrap(),
 225                     depth + 1,
 226                 ) {
 227                     Some(true) => {}
 228                     ret => return ret,
 229                 }
 230
 231                 let ret = st1[..st1.len() - 1]
 232                     .iter()
 233                     .zip(&st2[..st2.len() - 1])
 234                     .all(|(ty1, ty2)| self.unify(ty1, ty2));
 235
 236                 Some(ret)
 237             }
 238
 239             // Foo<..., T, ...> is Unsize<Foo<..., U, ...>> if:
 240             // - T: Unsize<U>
 241             // - Foo is a struct
 242             // - Only the last field of Foo has a type involving T
 243             // - T is not part of the type of any other fields
 244             // - Bar<T>: Unsize<Bar<U>>, if the last field of Foo has type Bar<T>
 245             (
 246                 ty_app!(TypeCtor::Adt(AdtId::StructId(struct1)), st1),
 247                 ty_app!(TypeCtor::Adt(AdtId::StructId(struct2)), st2),
 248             ) if struct1 == struct2 => {
 249                 let field_tys = self.db.field_types((*struct1).into());
 250                 let struct_data = self.db.struct_data(*struct1);
 251
 252                 let mut fields = struct_data.variant_data.fields().iter();
 253                 let (last_field_id, _data) = fields.next_back()?;
 254
 255                 // Get the generic parameter involved in the last field.
 256                 let unsize_generic_index = {
 257                     let mut index = None;
 258                     let mut multiple_param = false;
 259                     field_tys[last_field_id].walk(&mut |ty| match ty {
 260                         &Ty::Param { idx, .. } => {
 261                             if index.is_none() {
 262                                 index = Some(idx);
 263                             } else if Some(idx) != index {
 264                                 multiple_param = true;
 265                             }
 266                         }
 267                         _ => {}
 268                     });
 269
 270                     if multiple_param {
 271                         return None;
 272                     }
 273                     index?
 274                 };
 275
 276                 // Check other fields do not involve it.
 277                 let mut multiple_used = false;
 278                 fields.for_each(|(field_id, _data)| {
 279                     field_tys[field_id].walk(&mut |ty| match ty {
 280                         &Ty::Param { idx, .. } if idx == unsize_generic_index => {
 281                             multiple_used = true
 282                         }
 283                         _ => {}
 284                     })
 285                 });
 286                 if multiple_used {
 287                     return None;
 288                 }
 289
 290                 let unsize_generic_index = unsize_generic_index as usize;
 291
 292                 // Check `Unsize` first
 293                 match self.check_unsize_and_coerce(
 294                     st1.get(unsize_generic_index)?,
 295                     st2.get(unsize_generic_index)?,
 296                     depth + 1,
 297                 ) {
 298                     Some(true) => {}
 299                     ret => return ret,
 300                 }
 301
 302                 // Then unify other parameters
 303                 let ret = st1
 304                     .iter()
 305                     .zip(st2.iter())
 306                     .enumerate()
 307                     .filter(|&(idx, _)| idx != unsize_generic_index)
 308                     .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
 309
 310                 Some(ret)
 311             }
 312
 313             _ => None,
 314         }
 315     }
 316
 317     /// Unify `from_ty` to `to_ty` with optional auto Deref
 318     ///
 319     /// Note that the parameters are already stripped the outer reference.
 320     fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
 321         let canonicalized = self.canonicalizer().canonicalize_ty(from_ty.clone());
 322         let to_ty = self.resolve_ty_shallow(&to_ty);
 323         // FIXME: Auto DerefMut
 324         for derefed_ty in autoderef::autoderef(
 325             self.db,
 326             self.resolver.krate(),
 327             InEnvironment {
 328                 value: canonicalized.value.clone(),
 329                 environment: self.trait_env.clone(),
 330             },
 331         ) {
 332             let derefed_ty = canonicalized.decanonicalize_ty(derefed_ty.value);
 333             match (&*self.resolve_ty_shallow(&derefed_ty), &*to_ty) {
 334                 // Stop when constructor matches.
 335                 (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => {
 336                     // It will not recurse to `coerce`.
 337                     return self.table.unify_substs(st1, st2, 0);
 338                 }
 339                 _ => {
 340                     if self.table.unify_inner_trivial(&derefed_ty, &to_ty) {
 341                         return true;
 342                     }
 343                 }
 344             }
 345         }
 346
 347         false
 348     }
 349 }