crates/hir_ty/src/infer/unify.rs

   1 //! Unification and canonicalization logic.
   2
   3 use std::{borrow::Cow, fmt, sync::Arc};
   4
   5 use chalk_ir::{
   6     cast::Cast, fold::Fold, interner::HasInterner, zip::Zip, FloatTy, IntTy, TyVariableKind,
   7     UniverseIndex,
   8 };
   9 use chalk_solve::infer::ParameterEnaVariableExt;
  10 use ena::unify::UnifyKey;
  11
  12 use super::{InferOk, InferResult, InferenceContext, TypeError};
  13 use crate::{
  14     db::HirDatabase, fold_tys, static_lifetime, BoundVar, Canonical, DebruijnIndex, GenericArg,
  15     InferenceVar, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyKind, VariableKind,
  16 };
  17
  18 impl<'a> InferenceContext<'a> {
  19     pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
  20         &mut self,
  21         t: T,
  22     ) -> Canonicalized<T::Result>
  23     where
  24         T::Result: HasInterner<Interner = Interner>,
  25     {
  26         let result = self.table.var_unification_table.canonicalize(&Interner, t);
  27         let free_vars = result
  28             .free_vars
  29             .into_iter()
  30             .map(|free_var| free_var.to_generic_arg(&Interner))
  31             .collect();
  32         Canonicalized { value: result.quantified, free_vars }
  33     }
  34 }
  35
  36 #[derive(Debug)]
  37 pub(super) struct Canonicalized<T>
  38 where
  39     T: HasInterner<Interner = Interner>,
  40 {
  41     pub(super) value: Canonical<T>,
  42     free_vars: Vec<GenericArg>,
  43 }
  44
  45 impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
  46     pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty {
  47         chalk_ir::Substitute::apply(&self.free_vars, ty, &Interner)
  48     }
  49
  50     pub(super) fn apply_solution(
  51         &self,
  52         ctx: &mut InferenceContext<'_>,
  53         solution: Canonical<Substitution>,
  54     ) {
  55         // the solution may contain new variables, which we need to convert to new inference vars
  56         let new_vars = Substitution::from_iter(
  57             &Interner,
  58             solution.binders.iter(&Interner).map(|k| match k.kind {
  59                 VariableKind::Ty(TyVariableKind::General) => {
  60                     ctx.table.new_type_var().cast(&Interner)
  61                 }
  62                 VariableKind::Ty(TyVariableKind::Integer) => {
  63                     ctx.table.new_integer_var().cast(&Interner)
  64                 }
  65                 VariableKind::Ty(TyVariableKind::Float) => {
  66                     ctx.table.new_float_var().cast(&Interner)
  67                 }
  68                 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere
  69                 VariableKind::Lifetime => static_lifetime().cast(&Interner),
  70                 _ => panic!("const variable in solution"),
  71             }),
  72         );
  73         for (i, v) in solution.value.iter(&Interner).enumerate() {
  74             let var = self.free_vars[i].clone();
  75             if let Some(ty) = v.ty(&Interner) {
  76                 // eagerly replace projections in the type; we may be getting types
  77                 // e.g. from where clauses where this hasn't happened yet
  78                 let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), &Interner));
  79                 ctx.table.unify(var.assert_ty_ref(&Interner), &ty);
  80             } else {
  81                 let _ = ctx.table.unify_inner(&var, &new_vars.apply(v.clone(), &Interner));
  82             }
  83         }
  84     }
  85 }
  86
  87 pub fn could_unify(
  88     db: &dyn HirDatabase,
  89     env: Arc<TraitEnvironment>,
  90     tys: &Canonical<(Ty, Ty)>,
  91 ) -> bool {
  92     unify(db, env, tys).is_some()
  93 }
  94
  95 pub(crate) fn unify(
  96     db: &dyn HirDatabase,
  97     env: Arc<TraitEnvironment>,
  98     tys: &Canonical<(Ty, Ty)>,
  99 ) -> Option<Substitution> {
 100     let mut table = InferenceTable::new(db, env);
 101     let vars = Substitution::from_iter(
 102         &Interner,
 103         tys.binders
 104             .iter(&Interner)
 105             // we always use type vars here because we want everything to
 106             // fallback to Unknown in the end (kind of hacky, as below)
 107             .map(|_| table.new_type_var()),
 108     );
 109     let ty1_with_vars = vars.apply(tys.value.0.clone(), &Interner);
 110     let ty2_with_vars = vars.apply(tys.value.1.clone(), &Interner);
 111     if !table.unify(&ty1_with_vars, &ty2_with_vars) {
 112         return None;
 113     }
 114     // default any type vars that weren't unified back to their original bound vars
 115     // (kind of hacky)
 116     let find_var = |iv| {
 117         vars.iter(&Interner).position(|v| match v.interned() {
 118             chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
 119             chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
 120             chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
 121         } == Some(iv))
 122     };
 123     let fallback = |iv, kind, default, binder| match kind {
 124         chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv)
 125             .map_or(default, |i| BoundVar::new(binder, i).to_ty(&Interner).cast(&Interner)),
 126         chalk_ir::VariableKind::Lifetime => find_var(iv)
 127             .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(&Interner).cast(&Interner)),
 128         chalk_ir::VariableKind::Const(ty) => find_var(iv)
 129             .map_or(default, |i| BoundVar::new(binder, i).to_const(&Interner, ty).cast(&Interner)),
 130     };
 131     Some(Substitution::from_iter(
 132         &Interner,
 133         vars.iter(&Interner)
 134             .map(|v| table.resolve_with_fallback(v.assert_ty_ref(&Interner).clone(), fallback)),
 135     ))
 136 }
 137
 138 #[derive(Clone, Debug)]
 139 pub(super) struct TypeVariableTable {
 140     inner: Vec<TypeVariableData>,
 141 }
 142
 143 impl TypeVariableTable {
 144     pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) {
 145         self.inner[iv.index() as usize].diverging = diverging;
 146     }
 147
 148     fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty {
 149         match kind {
 150             _ if self.inner.get(iv.index() as usize).map_or(false, |data| data.diverging) => {
 151                 TyKind::Never
 152             }
 153             TyVariableKind::General => TyKind::Error,
 154             TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)),
 155             TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)),
 156         }
 157         .intern(&Interner)
 158     }
 159 }
 160
 161 #[derive(Copy, Clone, Debug)]
 162 pub(crate) struct TypeVariableData {
 163     diverging: bool,
 164 }
 165
 166 type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>;
 167
 168 #[derive(Clone)]
 169 pub(crate) struct InferenceTable<'a> {
 170     db: &'a dyn HirDatabase,
 171     trait_env: Arc<TraitEnvironment>,
 172     pub(super) var_unification_table: ChalkInferenceTable,
 173     pub(super) type_variable_table: TypeVariableTable,
 174 }
 175
 176 impl<'a> InferenceTable<'a> {
 177     pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self {
 178         InferenceTable {
 179             db,
 180             trait_env,
 181             var_unification_table: ChalkInferenceTable::new(),
 182             type_variable_table: TypeVariableTable { inner: Vec::new() },
 183         }
 184     }
 185
 186     /// Chalk doesn't know about the `diverging` flag, so when it unifies two
 187     /// type variables of which one is diverging, the chosen root might not be
 188     /// diverging and we have no way of marking it as such at that time. This
 189     /// function goes through all type variables and make sure their root is
 190     /// marked as diverging if necessary, so that resolving them gives the right
 191     /// result.
 192     pub(super) fn propagate_diverging_flag(&mut self) {
 193         for i in 0..self.type_variable_table.inner.len() {
 194             if !self.type_variable_table.inner[i].diverging {
 195                 continue;
 196             }
 197             let v = InferenceVar::from(i as u32);
 198             let root = self.var_unification_table.inference_var_root(v);
 199             if let Some(data) = self.type_variable_table.inner.get_mut(root.index() as usize) {
 200                 data.diverging = true;
 201             }
 202         }
 203     }
 204
 205     fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty {
 206         let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
 207         // Chalk might have created some type variables for its own purposes that we don't know about...
 208         // TODO refactor this?
 209         self.type_variable_table.inner.extend(
 210             (0..1 + var.index() as usize - self.type_variable_table.inner.len())
 211                 .map(|_| TypeVariableData { diverging: false }),
 212         );
 213         assert_eq!(var.index() as usize, self.type_variable_table.inner.len() - 1);
 214         self.type_variable_table.inner[var.index() as usize].diverging = diverging;
 215         var.to_ty_with_kind(&Interner, kind)
 216     }
 217
 218     pub(crate) fn new_type_var(&mut self) -> Ty {
 219         self.new_var(TyVariableKind::General, false)
 220     }
 221
 222     pub(crate) fn new_integer_var(&mut self) -> Ty {
 223         self.new_var(TyVariableKind::Integer, false)
 224     }
 225
 226     pub(crate) fn new_float_var(&mut self) -> Ty {
 227         self.new_var(TyVariableKind::Float, false)
 228     }
 229
 230     pub(crate) fn new_maybe_never_var(&mut self) -> Ty {
 231         self.new_var(TyVariableKind::General, true)
 232     }
 233
 234     pub(crate) fn resolve_with_fallback<T>(
 235         &mut self,
 236         t: T,
 237         fallback: impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
 238     ) -> T::Result
 239     where
 240         T: HasInterner<Interner = Interner> + Fold<Interner>,
 241     {
 242         self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback)
 243     }
 244
 245     fn resolve_with_fallback_inner<T>(
 246         &mut self,
 247         var_stack: &mut Vec<InferenceVar>,
 248         t: T,
 249         fallback: &impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
 250     ) -> T::Result
 251     where
 252         T: HasInterner<Interner = Interner> + Fold<Interner>,
 253     {
 254         t.fold_with(
 255             &mut resolve::Resolver {
 256                 type_variable_table: &self.type_variable_table,
 257                 var_unification_table: &mut self.var_unification_table,
 258                 var_stack,
 259                 fallback,
 260             },
 261             DebruijnIndex::INNERMOST,
 262         )
 263         .expect("fold failed unexpectedly")
 264     }
 265
 266     pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty {
 267         self.resolve_with_fallback(ty, |_, _, d, _| d)
 268     }
 269
 270     // FIXME get rid of this, instead resolve shallowly where necessary
 271     pub(crate) fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty {
 272         self.resolve_ty_as_possible_inner(&mut Vec::new(), ty)
 273     }
 274
 275     /// Unify two types and register new trait goals that arise from that.
 276     // TODO give these two functions better names
 277     pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
 278         let _result = if let Ok(r) = self.unify_inner(ty1, ty2) {
 279             r
 280         } else {
 281             return false;
 282         };
 283         // TODO deal with new goals
 284         true
 285     }
 286
 287     /// Unify two types and return new trait goals arising from it, so the
 288     /// caller needs to deal with them.
 289     pub(crate) fn unify_inner<T: Zip<Interner>>(&mut self, t1: &T, t2: &T) -> InferResult {
 290         match self.var_unification_table.relate(
 291             &Interner,
 292             &self.db,
 293             &self.trait_env.env,
 294             chalk_ir::Variance::Invariant,
 295             t1,
 296             t2,
 297         ) {
 298             Ok(_result) => {
 299                 // TODO deal with new goals
 300                 Ok(InferOk {})
 301             }
 302             Err(chalk_ir::NoSolution) => Err(TypeError),
 303         }
 304     }
 305
 306     /// If `ty` is a type variable with known type, returns that type;
 307     /// otherwise, return ty.
 308     // FIXME this could probably just return Ty
 309     pub(crate) fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
 310         self.var_unification_table
 311             .normalize_ty_shallow(&Interner, ty)
 312             .map_or(Cow::Borrowed(ty), Cow::Owned)
 313     }
 314
 315     /// Resolves the type as far as currently possible, replacing type variables
 316     /// by their known types.
 317     fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<InferenceVar>, ty: Ty) -> Ty {
 318         fold_tys(
 319             ty,
 320             |ty, _| match ty.kind(&Interner) {
 321                 &TyKind::InferenceVar(tv, kind) => {
 322                     if tv_stack.contains(&tv) {
 323                         // recursive type
 324                         return self.type_variable_table.fallback_value(tv, kind);
 325                     }
 326                     if let Some(known_ty) = self.var_unification_table.probe_var(tv) {
 327                         // known_ty may contain other variables that are known by now
 328                         tv_stack.push(tv);
 329                         let result = self.resolve_ty_as_possible_inner(
 330                             tv_stack,
 331                             known_ty.assert_ty_ref(&Interner).clone(),
 332                         );
 333                         tv_stack.pop();
 334                         result
 335                     } else {
 336                         ty
 337                     }
 338                 }
 339                 _ => ty,
 340             },
 341             DebruijnIndex::INNERMOST,
 342         )
 343     }
 344 }
 345
 346 impl<'a> fmt::Debug for InferenceTable<'a> {
 347     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 348         f.debug_struct("InferenceTable")
 349             .field("num_vars", &self.type_variable_table.inner.len())
 350             .finish()
 351     }
 352 }
 353
 354 mod resolve {
 355     use super::{ChalkInferenceTable, TypeVariableTable};
 356     use crate::{
 357         ConcreteConst, Const, ConstData, ConstValue, DebruijnIndex, GenericArg, InferenceVar,
 358         Interner, Ty, TyVariableKind, VariableKind,
 359     };
 360     use chalk_ir::{
 361         cast::Cast,
 362         fold::{Fold, Folder},
 363         Fallible,
 364     };
 365     use hir_def::type_ref::ConstScalar;
 366
 367     pub(super) struct Resolver<'a, F> {
 368         pub type_variable_table: &'a TypeVariableTable,
 369         pub var_unification_table: &'a mut ChalkInferenceTable,
 370         pub var_stack: &'a mut Vec<InferenceVar>,
 371         pub fallback: F,
 372     }
 373     impl<'a, 'i, F> Folder<'i, Interner> for Resolver<'a, F>
 374     where
 375         F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg + 'i,
 376     {
 377         fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> {
 378             self
 379         }
 380
 381         fn interner(&self) -> &'i Interner {
 382             &Interner
 383         }
 384
 385         fn fold_inference_ty(
 386             &mut self,
 387             var: InferenceVar,
 388             kind: TyVariableKind,
 389             outer_binder: DebruijnIndex,
 390         ) -> Fallible<Ty> {
 391             let var = self.var_unification_table.inference_var_root(var);
 392             if self.var_stack.contains(&var) {
 393                 // recursive type
 394                 let default = self.type_variable_table.fallback_value(var, kind).cast(&Interner);
 395                 return Ok((self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
 396                     .assert_ty_ref(&Interner)
 397                     .clone());
 398             }
 399             let result = if let Some(known_ty) = self.var_unification_table.probe_var(var) {
 400                 // known_ty may contain other variables that are known by now
 401                 self.var_stack.push(var);
 402                 let result =
 403                     known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
 404                 self.var_stack.pop();
 405                 result.assert_ty_ref(&Interner).clone()
 406             } else {
 407                 let default = self.type_variable_table.fallback_value(var, kind).cast(&Interner);
 408                 (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
 409                     .assert_ty_ref(&Interner)
 410                     .clone()
 411             };
 412             Ok(result)
 413         }
 414
 415         fn fold_inference_const(
 416             &mut self,
 417             ty: Ty,
 418             var: InferenceVar,
 419             outer_binder: DebruijnIndex,
 420         ) -> Fallible<Const> {
 421             let var = self.var_unification_table.inference_var_root(var);
 422             let default = ConstData {
 423                 ty: ty.clone(),
 424                 value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }),
 425             }
 426             .intern(&Interner)
 427             .cast(&Interner);
 428             if self.var_stack.contains(&var) {
 429                 // recursive
 430                 return Ok((self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
 431                     .assert_const_ref(&Interner)
 432                     .clone());
 433             }
 434             let result = if let Some(known_ty) = self.var_unification_table.probe_var(var) {
 435                 // known_ty may contain other variables that are known by now
 436                 self.var_stack.push(var);
 437                 let result =
 438                     known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
 439                 self.var_stack.pop();
 440                 result.assert_const_ref(&Interner).clone()
 441             } else {
 442                 (self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
 443                     .assert_const_ref(&Interner)
 444                     .clone()
 445             };
 446             Ok(result)
 447         }
 448     }
 449 }