crates/hir_ty/src/infer/unify.rs

   1 //! Unification and canonicalization logic.
   2
   3 use std::{fmt, mem, 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, AliasEq, AliasTy, BoundVar, Canonical,
  15     DebruijnIndex, GenericArg, Goal, Guidance, InEnvironment, InferenceVar, Interner, ProjectionTy,
  16     Scalar, Solution, Substitution, TraitEnvironment, Ty, TyKind, VariableKind,
  17 };
  18
  19 impl<'a> InferenceContext<'a> {
  20     pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
  21         &mut self,
  22         t: T,
  23     ) -> Canonicalized<T::Result>
  24     where
  25         T::Result: HasInterner<Interner = Interner>,
  26     {
  27         // try to resolve obligations before canonicalizing, since this might
  28         // result in new knowledge about variables
  29         self.resolve_obligations_as_possible();
  30         self.table.canonicalize(t)
  31     }
  32 }
  33
  34 #[derive(Debug, Clone)]
  35 pub(super) struct Canonicalized<T>
  36 where
  37     T: HasInterner<Interner = Interner>,
  38 {
  39     pub(super) value: Canonical<T>,
  40     free_vars: Vec<GenericArg>,
  41 }
  42
  43 impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
  44     pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty {
  45         chalk_ir::Substitute::apply(&self.free_vars, ty, &Interner)
  46     }
  47
  48     pub(super) fn apply_solution(
  49         &self,
  50         ctx: &mut InferenceTable,
  51         solution: Canonical<Substitution>,
  52     ) {
  53         // the solution may contain new variables, which we need to convert to new inference vars
  54         let new_vars = Substitution::from_iter(
  55             &Interner,
  56             solution.binders.iter(&Interner).map(|k| match k.kind {
  57                 VariableKind::Ty(TyVariableKind::General) => ctx.new_type_var().cast(&Interner),
  58                 VariableKind::Ty(TyVariableKind::Integer) => ctx.new_integer_var().cast(&Interner),
  59                 VariableKind::Ty(TyVariableKind::Float) => ctx.new_float_var().cast(&Interner),
  60                 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere
  61                 VariableKind::Lifetime => static_lifetime().cast(&Interner),
  62                 _ => panic!("const variable in solution"),
  63             }),
  64         );
  65         for (i, v) in solution.value.iter(&Interner).enumerate() {
  66             let var = self.free_vars[i].clone();
  67             if let Some(ty) = v.ty(&Interner) {
  68                 // eagerly replace projections in the type; we may be getting types
  69                 // e.g. from where clauses where this hasn't happened yet
  70                 let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), &Interner));
  71                 ctx.unify(var.assert_ty_ref(&Interner), &ty);
  72             } else {
  73                 let _ = ctx.try_unify(&var, &new_vars.apply(v.clone(), &Interner));
  74             }
  75         }
  76     }
  77 }
  78
  79 pub fn could_unify(
  80     db: &dyn HirDatabase,
  81     env: Arc<TraitEnvironment>,
  82     tys: &Canonical<(Ty, Ty)>,
  83 ) -> bool {
  84     unify(db, env, tys).is_some()
  85 }
  86
  87 pub(crate) fn unify(
  88     db: &dyn HirDatabase,
  89     env: Arc<TraitEnvironment>,
  90     tys: &Canonical<(Ty, Ty)>,
  91 ) -> Option<Substitution> {
  92     let mut table = InferenceTable::new(db, env);
  93     let vars = Substitution::from_iter(
  94         &Interner,
  95         tys.binders
  96             .iter(&Interner)
  97             // we always use type vars here because we want everything to
  98             // fallback to Unknown in the end (kind of hacky, as below)
  99             .map(|_| table.new_type_var()),
 100     );
 101     let ty1_with_vars = vars.apply(tys.value.0.clone(), &Interner);
 102     let ty2_with_vars = vars.apply(tys.value.1.clone(), &Interner);
 103     if !table.unify(&ty1_with_vars, &ty2_with_vars) {
 104         return None;
 105     }
 106     // default any type vars that weren't unified back to their original bound vars
 107     // (kind of hacky)
 108     let find_var = |iv| {
 109         vars.iter(&Interner).position(|v| match v.interned() {
 110             chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
 111             chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
 112             chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
 113         } == Some(iv))
 114     };
 115     let fallback = |iv, kind, default, binder| match kind {
 116         chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv)
 117             .map_or(default, |i| BoundVar::new(binder, i).to_ty(&Interner).cast(&Interner)),
 118         chalk_ir::VariableKind::Lifetime => find_var(iv)
 119             .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(&Interner).cast(&Interner)),
 120         chalk_ir::VariableKind::Const(ty) => find_var(iv)
 121             .map_or(default, |i| BoundVar::new(binder, i).to_const(&Interner, ty).cast(&Interner)),
 122     };
 123     Some(Substitution::from_iter(
 124         &Interner,
 125         vars.iter(&Interner)
 126             .map(|v| table.resolve_with_fallback(v.assert_ty_ref(&Interner).clone(), fallback)),
 127     ))
 128 }
 129
 130 #[derive(Copy, Clone, Debug)]
 131 pub(crate) struct TypeVariableData {
 132     diverging: bool,
 133 }
 134
 135 type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>;
 136
 137 #[derive(Clone)]
 138 pub(crate) struct InferenceTable<'a> {
 139     pub(crate) db: &'a dyn HirDatabase,
 140     pub(crate) trait_env: Arc<TraitEnvironment>,
 141     var_unification_table: ChalkInferenceTable,
 142     type_variable_table: Vec<TypeVariableData>,
 143     pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>,
 144 }
 145
 146 impl<'a> InferenceTable<'a> {
 147     pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self {
 148         InferenceTable {
 149             db,
 150             trait_env,
 151             var_unification_table: ChalkInferenceTable::new(),
 152             type_variable_table: Vec::new(),
 153             pending_obligations: Vec::new(),
 154         }
 155     }
 156
 157     /// Chalk doesn't know about the `diverging` flag, so when it unifies two
 158     /// type variables of which one is diverging, the chosen root might not be
 159     /// diverging and we have no way of marking it as such at that time. This
 160     /// function goes through all type variables and make sure their root is
 161     /// marked as diverging if necessary, so that resolving them gives the right
 162     /// result.
 163     pub(super) fn propagate_diverging_flag(&mut self) {
 164         for i in 0..self.type_variable_table.len() {
 165             if !self.type_variable_table[i].diverging {
 166                 continue;
 167             }
 168             let v = InferenceVar::from(i as u32);
 169             let root = self.var_unification_table.inference_var_root(v);
 170             if let Some(data) = self.type_variable_table.get_mut(root.index() as usize) {
 171                 data.diverging = true;
 172             }
 173         }
 174     }
 175
 176     pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) {
 177         self.type_variable_table[iv.index() as usize].diverging = diverging;
 178     }
 179
 180     fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty {
 181         match kind {
 182             _ if self
 183                 .type_variable_table
 184                 .get(iv.index() as usize)
 185                 .map_or(false, |data| data.diverging) =>
 186             {
 187                 TyKind::Never
 188             }
 189             TyVariableKind::General => TyKind::Error,
 190             TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)),
 191             TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)),
 192         }
 193         .intern(&Interner)
 194     }
 195
 196     pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
 197         &mut self,
 198         t: T,
 199     ) -> Canonicalized<T::Result>
 200     where
 201         T::Result: HasInterner<Interner = Interner>,
 202     {
 203         let result = self.var_unification_table.canonicalize(&Interner, t);
 204         let free_vars = result
 205             .free_vars
 206             .into_iter()
 207             .map(|free_var| free_var.to_generic_arg(&Interner))
 208             .collect();
 209         Canonicalized { value: result.quantified, free_vars }
 210     }
 211
 212     /// Recurses through the given type, normalizing associated types mentioned
 213     /// in it by replacing them by type variables and registering obligations to
 214     /// resolve later. This should be done once for every type we get from some
 215     /// type annotation (e.g. from a let type annotation, field type or function
 216     /// call). `make_ty` handles this already, but e.g. for field types we need
 217     /// to do it as well.
 218     pub(super) fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
 219         fold_tys(
 220             ty,
 221             |ty, _| match ty.kind(&Interner) {
 222                 TyKind::Alias(AliasTy::Projection(proj_ty)) => {
 223                     self.normalize_projection_ty(proj_ty.clone())
 224                 }
 225                 _ => ty,
 226             },
 227             DebruijnIndex::INNERMOST,
 228         )
 229     }
 230
 231     pub(super) fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
 232         let var = self.new_type_var();
 233         let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() };
 234         let obligation = alias_eq.cast(&Interner);
 235         self.register_obligation(obligation);
 236         var
 237     }
 238
 239     fn extend_type_variable_table(&mut self, to_index: usize) {
 240         self.type_variable_table.extend(
 241             (0..1 + to_index - self.type_variable_table.len())
 242                 .map(|_| TypeVariableData { diverging: false }),
 243         );
 244     }
 245
 246     fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty {
 247         let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
 248         // Chalk might have created some type variables for its own purposes that we don't know about...
 249         self.extend_type_variable_table(var.index() as usize);
 250         assert_eq!(var.index() as usize, self.type_variable_table.len() - 1);
 251         self.type_variable_table[var.index() as usize].diverging = diverging;
 252         var.to_ty_with_kind(&Interner, kind)
 253     }
 254
 255     pub(crate) fn new_type_var(&mut self) -> Ty {
 256         self.new_var(TyVariableKind::General, false)
 257     }
 258
 259     pub(crate) fn new_integer_var(&mut self) -> Ty {
 260         self.new_var(TyVariableKind::Integer, false)
 261     }
 262
 263     pub(crate) fn new_float_var(&mut self) -> Ty {
 264         self.new_var(TyVariableKind::Float, false)
 265     }
 266
 267     pub(crate) fn new_maybe_never_var(&mut self) -> Ty {
 268         self.new_var(TyVariableKind::General, true)
 269     }
 270
 271     pub(crate) fn resolve_with_fallback<T>(
 272         &mut self,
 273         t: T,
 274         fallback: impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
 275     ) -> T::Result
 276     where
 277         T: HasInterner<Interner = Interner> + Fold<Interner>,
 278     {
 279         self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback)
 280     }
 281
 282     fn resolve_with_fallback_inner<T>(
 283         &mut self,
 284         var_stack: &mut Vec<InferenceVar>,
 285         t: T,
 286         fallback: &impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg,
 287     ) -> T::Result
 288     where
 289         T: HasInterner<Interner = Interner> + Fold<Interner>,
 290     {
 291         t.fold_with(
 292             &mut resolve::Resolver { table: self, var_stack, fallback },
 293             DebruijnIndex::INNERMOST,
 294         )
 295         .expect("fold failed unexpectedly")
 296     }
 297
 298     pub(crate) fn resolve_completely<T>(&mut self, t: T) -> T::Result
 299     where
 300         T: HasInterner<Interner = Interner> + Fold<Interner>,
 301     {
 302         self.resolve_with_fallback(t, |_, _, d, _| d)
 303     }
 304
 305     /// Unify two types and register new trait goals that arise from that.
 306     pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
 307         let result = if let Ok(r) = self.try_unify(ty1, ty2) {
 308             r
 309         } else {
 310             return false;
 311         };
 312         self.register_infer_ok(result);
 313         true
 314     }
 315
 316     /// Unify two types and return new trait goals arising from it, so the
 317     /// caller needs to deal with them.
 318     pub(crate) fn try_unify<T: Zip<Interner>>(&mut self, t1: &T, t2: &T) -> InferResult {
 319         match self.var_unification_table.relate(
 320             &Interner,
 321             &self.db,
 322             &self.trait_env.env,
 323             chalk_ir::Variance::Invariant,
 324             t1,
 325             t2,
 326         ) {
 327             Ok(result) => Ok(InferOk { goals: result.goals }),
 328             Err(chalk_ir::NoSolution) => Err(TypeError),
 329         }
 330     }
 331
 332     /// If `ty` is a type variable with known type, returns that type;
 333     /// otherwise, return ty.
 334     pub(crate) fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty {
 335         self.var_unification_table.normalize_ty_shallow(&Interner, ty).unwrap_or_else(|| ty.clone())
 336     }
 337
 338     pub(crate) fn register_obligation(&mut self, goal: Goal) {
 339         let in_env = InEnvironment::new(&self.trait_env.env, goal);
 340         self.register_obligation_in_env(in_env)
 341     }
 342
 343     fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) {
 344         let canonicalized = self.canonicalize(goal);
 345         if !self.try_resolve_obligation(&canonicalized) {
 346             self.pending_obligations.push(canonicalized);
 347         }
 348     }
 349
 350     pub(crate) fn register_infer_ok(&mut self, infer_ok: InferOk) {
 351         infer_ok.goals.into_iter().for_each(|goal| self.register_obligation_in_env(goal));
 352     }
 353
 354     pub(crate) fn resolve_obligations_as_possible(&mut self) {
 355         let _span = profile::span("resolve_obligations_as_possible");
 356         let mut changed = true;
 357         let mut obligations = Vec::new();
 358         while changed {
 359             changed = false;
 360             mem::swap(&mut self.pending_obligations, &mut obligations);
 361             for canonicalized in obligations.drain(..) {
 362                 if !self.check_changed(&canonicalized) {
 363                     self.pending_obligations.push(canonicalized);
 364                     continue;
 365                 }
 366                 changed = true;
 367                 let uncanonical = chalk_ir::Substitute::apply(
 368                     &canonicalized.free_vars,
 369                     canonicalized.value.value,
 370                     &Interner,
 371                 );
 372                 self.register_obligation_in_env(uncanonical);
 373             }
 374         }
 375     }
 376
 377     /// This checks whether any of the free variables in the `canonicalized`
 378     /// have changed (either been unified with another variable, or with a
 379     /// value). If this is not the case, we don't need to try to solve the goal
 380     /// again -- it'll give the same result as last time.
 381     fn check_changed(&mut self, canonicalized: &Canonicalized<InEnvironment<Goal>>) -> bool {
 382         canonicalized.free_vars.iter().any(|var| {
 383             let iv = match var.data(&Interner) {
 384                 chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
 385                 chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
 386                 chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
 387             }
 388             .expect("free var is not inference var");
 389             if self.var_unification_table.probe_var(iv).is_some() {
 390                 return true;
 391             }
 392             let root = self.var_unification_table.inference_var_root(iv);
 393             iv != root
 394         })
 395     }
 396
 397     fn try_resolve_obligation(
 398         &mut self,
 399         canonicalized: &Canonicalized<InEnvironment<Goal>>,
 400     ) -> bool {
 401         let solution = self.db.trait_solve(self.trait_env.krate, canonicalized.value.clone());
 402
 403         match solution {
 404             Some(Solution::Unique(canonical_subst)) => {
 405                 canonicalized.apply_solution(
 406                     self,
 407                     Canonical {
 408                         binders: canonical_subst.binders,
 409                         // FIXME: handle constraints
 410                         value: canonical_subst.value.subst,
 411                     },
 412                 );
 413                 true
 414             }
 415             Some(Solution::Ambig(Guidance::Definite(substs))) => {
 416                 canonicalized.apply_solution(self, substs);
 417                 false
 418             }
 419             Some(_) => {
 420                 // FIXME use this when trying to resolve everything at the end
 421                 false
 422             }
 423             None => {
 424                 // FIXME obligation cannot be fulfilled => diagnostic
 425                 true
 426             }
 427         }
 428     }
 429 }
 430
 431 impl<'a> fmt::Debug for InferenceTable<'a> {
 432     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 433         f.debug_struct("InferenceTable").field("num_vars", &self.type_variable_table.len()).finish()
 434     }
 435 }
 436
 437 mod resolve {
 438     use super::InferenceTable;
 439     use crate::{
 440         ConcreteConst, Const, ConstData, ConstValue, DebruijnIndex, GenericArg, InferenceVar,
 441         Interner, Lifetime, Ty, TyVariableKind, VariableKind,
 442     };
 443     use chalk_ir::{
 444         cast::Cast,
 445         fold::{Fold, Folder},
 446         Fallible,
 447     };
 448     use hir_def::type_ref::ConstScalar;
 449
 450     pub(super) struct Resolver<'a, 'b, F> {
 451         pub(super) table: &'a mut InferenceTable<'b>,
 452         pub(super) var_stack: &'a mut Vec<InferenceVar>,
 453         pub(super) fallback: F,
 454     }
 455     impl<'a, 'b, 'i, F> Folder<'i, Interner> for Resolver<'a, 'b, F>
 456     where
 457         F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg + 'i,
 458     {
 459         fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> {
 460             self
 461         }
 462
 463         fn interner(&self) -> &'i Interner {
 464             &Interner
 465         }
 466
 467         fn fold_inference_ty(
 468             &mut self,
 469             var: InferenceVar,
 470             kind: TyVariableKind,
 471             outer_binder: DebruijnIndex,
 472         ) -> Fallible<Ty> {
 473             let var = self.table.var_unification_table.inference_var_root(var);
 474             if self.var_stack.contains(&var) {
 475                 // recursive type
 476                 let default = self.table.fallback_value(var, kind).cast(&Interner);
 477                 return Ok((self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
 478                     .assert_ty_ref(&Interner)
 479                     .clone());
 480             }
 481             let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) {
 482                 // known_ty may contain other variables that are known by now
 483                 self.var_stack.push(var);
 484                 let result =
 485                     known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
 486                 self.var_stack.pop();
 487                 result.assert_ty_ref(&Interner).clone()
 488             } else {
 489                 let default = self.table.fallback_value(var, kind).cast(&Interner);
 490                 (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder)
 491                     .assert_ty_ref(&Interner)
 492                     .clone()
 493             };
 494             Ok(result)
 495         }
 496
 497         fn fold_inference_const(
 498             &mut self,
 499             ty: Ty,
 500             var: InferenceVar,
 501             outer_binder: DebruijnIndex,
 502         ) -> Fallible<Const> {
 503             let var = self.table.var_unification_table.inference_var_root(var);
 504             let default = ConstData {
 505                 ty: ty.clone(),
 506                 value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }),
 507             }
 508             .intern(&Interner)
 509             .cast(&Interner);
 510             if self.var_stack.contains(&var) {
 511                 // recursive
 512                 return Ok((self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
 513                     .assert_const_ref(&Interner)
 514                     .clone());
 515             }
 516             let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) {
 517                 // known_ty may contain other variables that are known by now
 518                 self.var_stack.push(var);
 519                 let result =
 520                     known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly");
 521                 self.var_stack.pop();
 522                 result.assert_const_ref(&Interner).clone()
 523             } else {
 524                 (self.fallback)(var, VariableKind::Const(ty), default, outer_binder)
 525                     .assert_const_ref(&Interner)
 526                     .clone()
 527             };
 528             Ok(result)
 529         }
 530
 531         fn fold_inference_lifetime(
 532             &mut self,
 533             _var: InferenceVar,
 534             _outer_binder: DebruijnIndex,
 535         ) -> Fallible<Lifetime> {
 536             // fall back all lifetimes to 'static -- currently we don't deal
 537             // with any lifetimes, but we can sometimes get some lifetime
 538             // variables through Chalk's unification, and this at least makes
 539             // sure we don't leak them outside of inference
 540             Ok(crate::static_lifetime())
 541         }
 542     }
 543 }