diff options
author | Florian Diebold <[email protected]> | 2019-12-01 19:30:28 +0000 |
---|---|---|
committer | Florian Diebold <[email protected]> | 2019-12-02 18:33:13 +0000 |
commit | 599dab59824b164b1c24e2e51adeae1ac1307964 (patch) | |
tree | 3a31914d0647dd18f6e0026681ca1aed5a0e262a /crates/ra_hir_ty/src | |
parent | cbf262a1bc72f10dc93a4993da0012d3b0abb56f (diff) |
Extract unification code to unify module
Diffstat (limited to 'crates/ra_hir_ty/src')
-rw-r--r-- | crates/ra_hir_ty/src/infer.rs | 255 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/coerce.rs | 10 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/expr.rs | 30 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/pat.rs | 4 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/path.rs | 4 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/unify.rs | 272 |
6 files changed, 312 insertions, 263 deletions
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs index fe259371f..81afbd2b4 100644 --- a/crates/ra_hir_ty/src/infer.rs +++ b/crates/ra_hir_ty/src/infer.rs | |||
@@ -18,7 +18,6 @@ use std::mem; | |||
18 | use std::ops::Index; | 18 | use std::ops::Index; |
19 | use std::sync::Arc; | 19 | use std::sync::Arc; |
20 | 20 | ||
21 | use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; | ||
22 | use rustc_hash::FxHashMap; | 21 | use rustc_hash::FxHashMap; |
23 | 22 | ||
24 | use hir_def::{ | 23 | use hir_def::{ |
@@ -33,12 +32,11 @@ use hir_def::{ | |||
33 | use hir_expand::{diagnostics::DiagnosticSink, name}; | 32 | use hir_expand::{diagnostics::DiagnosticSink, name}; |
34 | use ra_arena::map::ArenaMap; | 33 | use ra_arena::map::ArenaMap; |
35 | use ra_prof::profile; | 34 | use ra_prof::profile; |
36 | use test_utils::tested_by; | ||
37 | 35 | ||
38 | use super::{ | 36 | use super::{ |
39 | primitive::{FloatTy, IntTy}, | 37 | primitive::{FloatTy, IntTy}, |
40 | traits::{Guidance, Obligation, ProjectionPredicate, Solution}, | 38 | traits::{Guidance, Obligation, ProjectionPredicate, Solution}, |
41 | ApplicationTy, InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor, | 39 | ApplicationTy, InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty, TypeCtor, |
42 | TypeWalk, Uncertain, | 40 | TypeWalk, Uncertain, |
43 | }; | 41 | }; |
44 | use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; | 42 | use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; |
@@ -191,7 +189,7 @@ struct InferenceContext<'a, D: HirDatabase> { | |||
191 | owner: DefWithBodyId, | 189 | owner: DefWithBodyId, |
192 | body: Arc<Body>, | 190 | body: Arc<Body>, |
193 | resolver: Resolver, | 191 | resolver: Resolver, |
194 | var_unification_table: InPlaceUnificationTable<TypeVarId>, | 192 | table: unify::InferenceTable, |
195 | trait_env: Arc<TraitEnvironment>, | 193 | trait_env: Arc<TraitEnvironment>, |
196 | obligations: Vec<Obligation>, | 194 | obligations: Vec<Obligation>, |
197 | result: InferenceResult, | 195 | result: InferenceResult, |
@@ -209,7 +207,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
209 | fn new(db: &'a D, owner: DefWithBodyId, resolver: Resolver) -> Self { | 207 | fn new(db: &'a D, owner: DefWithBodyId, resolver: Resolver) -> Self { |
210 | InferenceContext { | 208 | InferenceContext { |
211 | result: InferenceResult::default(), | 209 | result: InferenceResult::default(), |
212 | var_unification_table: InPlaceUnificationTable::new(), | 210 | table: unify::InferenceTable::new(), |
213 | obligations: Vec::default(), | 211 | obligations: Vec::default(), |
214 | return_ty: Ty::Unknown, // set in collect_fn_signature | 212 | return_ty: Ty::Unknown, // set in collect_fn_signature |
215 | trait_env: TraitEnvironment::lower(db, &resolver), | 213 | trait_env: TraitEnvironment::lower(db, &resolver), |
@@ -224,13 +222,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
224 | fn resolve_all(mut self) -> InferenceResult { | 222 | fn resolve_all(mut self) -> InferenceResult { |
225 | // FIXME resolve obligations as well (use Guidance if necessary) | 223 | // FIXME resolve obligations as well (use Guidance if necessary) |
226 | let mut result = mem::replace(&mut self.result, InferenceResult::default()); | 224 | let mut result = mem::replace(&mut self.result, InferenceResult::default()); |
227 | let mut tv_stack = Vec::new(); | ||
228 | for ty in result.type_of_expr.values_mut() { | 225 | for ty in result.type_of_expr.values_mut() { |
229 | let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); | 226 | let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown)); |
230 | *ty = resolved; | 227 | *ty = resolved; |
231 | } | 228 | } |
232 | for ty in result.type_of_pat.values_mut() { | 229 | for ty in result.type_of_pat.values_mut() { |
233 | let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); | 230 | let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown)); |
234 | *ty = resolved; | 231 | *ty = resolved; |
235 | } | 232 | } |
236 | result | 233 | result |
@@ -275,96 +272,15 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
275 | self.normalize_associated_types_in(ty) | 272 | self.normalize_associated_types_in(ty) |
276 | } | 273 | } |
277 | 274 | ||
278 | fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool { | ||
279 | substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth)) | ||
280 | } | ||
281 | |||
282 | fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
283 | self.unify_inner(ty1, ty2, 0) | ||
284 | } | ||
285 | |||
286 | fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | ||
287 | if depth > 1000 { | ||
288 | // prevent stackoverflows | ||
289 | panic!("infinite recursion in unification"); | ||
290 | } | ||
291 | if ty1 == ty2 { | ||
292 | return true; | ||
293 | } | ||
294 | // try to resolve type vars first | ||
295 | let ty1 = self.resolve_ty_shallow(ty1); | ||
296 | let ty2 = self.resolve_ty_shallow(ty2); | ||
297 | match (&*ty1, &*ty2) { | ||
298 | (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => { | ||
299 | self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1) | ||
300 | } | ||
301 | _ => self.unify_inner_trivial(&ty1, &ty2), | ||
302 | } | ||
303 | } | ||
304 | |||
305 | fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
306 | match (ty1, ty2) { | ||
307 | (Ty::Unknown, _) | (_, Ty::Unknown) => true, | ||
308 | |||
309 | (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2))) | ||
310 | | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2))) | ||
311 | | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2))) | ||
312 | | ( | ||
313 | Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)), | ||
314 | Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)), | ||
315 | ) => { | ||
316 | // both type vars are unknown since we tried to resolve them | ||
317 | self.var_unification_table.union(*tv1, *tv2); | ||
318 | true | ||
319 | } | ||
320 | |||
321 | // The order of MaybeNeverTypeVar matters here. | ||
322 | // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar. | ||
323 | // Unifying MaybeNeverTypeVar and other concrete type will let the former become it. | ||
324 | (Ty::Infer(InferTy::TypeVar(tv)), other) | ||
325 | | (other, Ty::Infer(InferTy::TypeVar(tv))) | ||
326 | | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other) | ||
327 | | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv))) | ||
328 | | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_))) | ||
329 | | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv))) | ||
330 | | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_))) | ||
331 | | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => { | ||
332 | // the type var is unknown since we tried to resolve it | ||
333 | self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone())); | ||
334 | true | ||
335 | } | ||
336 | |||
337 | _ => false, | ||
338 | } | ||
339 | } | ||
340 | |||
341 | fn new_type_var(&mut self) -> Ty { | ||
342 | Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
343 | } | ||
344 | |||
345 | fn new_integer_var(&mut self) -> Ty { | ||
346 | Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
347 | } | ||
348 | |||
349 | fn new_float_var(&mut self) -> Ty { | ||
350 | Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
351 | } | ||
352 | |||
353 | fn new_maybe_never_type_var(&mut self) -> Ty { | ||
354 | Ty::Infer(InferTy::MaybeNeverTypeVar( | ||
355 | self.var_unification_table.new_key(TypeVarValue::Unknown), | ||
356 | )) | ||
357 | } | ||
358 | |||
359 | /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it. | 275 | /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it. |
360 | fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { | 276 | fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { |
361 | match ty { | 277 | match ty { |
362 | Ty::Unknown => self.new_type_var(), | 278 | Ty::Unknown => self.table.new_type_var(), |
363 | Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(Uncertain::Unknown), .. }) => { | 279 | Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(Uncertain::Unknown), .. }) => { |
364 | self.new_integer_var() | 280 | self.table.new_integer_var() |
365 | } | 281 | } |
366 | Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(Uncertain::Unknown), .. }) => { | 282 | Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(Uncertain::Unknown), .. }) => { |
367 | self.new_float_var() | 283 | self.table.new_float_var() |
368 | } | 284 | } |
369 | _ => ty, | 285 | _ => ty, |
370 | } | 286 | } |
@@ -402,64 +318,22 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
402 | } | 318 | } |
403 | } | 319 | } |
404 | 320 | ||
321 | fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
322 | self.table.unify(ty1, ty2) | ||
323 | } | ||
324 | |||
405 | /// Resolves the type as far as currently possible, replacing type variables | 325 | /// Resolves the type as far as currently possible, replacing type variables |
406 | /// by their known types. All types returned by the infer_* functions should | 326 | /// by their known types. All types returned by the infer_* functions should |
407 | /// be resolved as far as possible, i.e. contain no type variables with | 327 | /// be resolved as far as possible, i.e. contain no type variables with |
408 | /// known type. | 328 | /// known type. |
409 | fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | 329 | fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { |
410 | self.resolve_obligations_as_possible(); | 330 | self.resolve_obligations_as_possible(); |
411 | 331 | ||
412 | ty.fold(&mut |ty| match ty { | 332 | self.table.resolve_ty_as_possible(ty) |
413 | Ty::Infer(tv) => { | ||
414 | let inner = tv.to_inner(); | ||
415 | if tv_stack.contains(&inner) { | ||
416 | tested_by!(type_var_cycles_resolve_as_possible); | ||
417 | // recursive type | ||
418 | return tv.fallback_value(); | ||
419 | } | ||
420 | if let Some(known_ty) = | ||
421 | self.var_unification_table.inlined_probe_value(inner).known() | ||
422 | { | ||
423 | // known_ty may contain other variables that are known by now | ||
424 | tv_stack.push(inner); | ||
425 | let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone()); | ||
426 | tv_stack.pop(); | ||
427 | result | ||
428 | } else { | ||
429 | ty | ||
430 | } | ||
431 | } | ||
432 | _ => ty, | ||
433 | }) | ||
434 | } | 333 | } |
435 | 334 | ||
436 | /// If `ty` is a type variable with known type, returns that type; | ||
437 | /// otherwise, return ty. | ||
438 | fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { | 335 | fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { |
439 | let mut ty = Cow::Borrowed(ty); | 336 | self.table.resolve_ty_shallow(ty) |
440 | // The type variable could resolve to a int/float variable. Hence try | ||
441 | // resolving up to three times; each type of variable shouldn't occur | ||
442 | // more than once | ||
443 | for i in 0..3 { | ||
444 | if i > 0 { | ||
445 | tested_by!(type_var_resolves_to_int_var); | ||
446 | } | ||
447 | match &*ty { | ||
448 | Ty::Infer(tv) => { | ||
449 | let inner = tv.to_inner(); | ||
450 | match self.var_unification_table.inlined_probe_value(inner).known() { | ||
451 | Some(known_ty) => { | ||
452 | // The known_ty can't be a type var itself | ||
453 | ty = Cow::Owned(known_ty.clone()); | ||
454 | } | ||
455 | _ => return ty, | ||
456 | } | ||
457 | } | ||
458 | _ => return ty, | ||
459 | } | ||
460 | } | ||
461 | log::error!("Inference variable still not resolved: {:?}", ty); | ||
462 | ty | ||
463 | } | 337 | } |
464 | 338 | ||
465 | /// Recurses through the given type, normalizing associated types mentioned | 339 | /// Recurses through the given type, normalizing associated types mentioned |
@@ -469,7 +343,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
469 | /// call). `make_ty` handles this already, but e.g. for field types we need | 343 | /// call). `make_ty` handles this already, but e.g. for field types we need |
470 | /// to do it as well. | 344 | /// to do it as well. |
471 | fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { | 345 | fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { |
472 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 346 | let ty = self.resolve_ty_as_possible(ty); |
473 | ty.fold(&mut |ty| match ty { | 347 | ty.fold(&mut |ty| match ty { |
474 | Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty), | 348 | Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty), |
475 | _ => ty, | 349 | _ => ty, |
@@ -477,40 +351,13 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
477 | } | 351 | } |
478 | 352 | ||
479 | fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { | 353 | fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { |
480 | let var = self.new_type_var(); | 354 | let var = self.table.new_type_var(); |
481 | let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() }; | 355 | let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() }; |
482 | let obligation = Obligation::Projection(predicate); | 356 | let obligation = Obligation::Projection(predicate); |
483 | self.obligations.push(obligation); | 357 | self.obligations.push(obligation); |
484 | var | 358 | var |
485 | } | 359 | } |
486 | 360 | ||
487 | /// Resolves the type completely; type variables without known type are | ||
488 | /// replaced by Ty::Unknown. | ||
489 | fn resolve_ty_completely(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
490 | ty.fold(&mut |ty| match ty { | ||
491 | Ty::Infer(tv) => { | ||
492 | let inner = tv.to_inner(); | ||
493 | if tv_stack.contains(&inner) { | ||
494 | tested_by!(type_var_cycles_resolve_completely); | ||
495 | // recursive type | ||
496 | return tv.fallback_value(); | ||
497 | } | ||
498 | if let Some(known_ty) = | ||
499 | self.var_unification_table.inlined_probe_value(inner).known() | ||
500 | { | ||
501 | // known_ty may contain other variables that are known by now | ||
502 | tv_stack.push(inner); | ||
503 | let result = self.resolve_ty_completely(tv_stack, known_ty.clone()); | ||
504 | tv_stack.pop(); | ||
505 | result | ||
506 | } else { | ||
507 | tv.fallback_value() | ||
508 | } | ||
509 | } | ||
510 | _ => ty, | ||
511 | }) | ||
512 | } | ||
513 | |||
514 | fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) { | 361 | fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) { |
515 | let path = match path { | 362 | let path = match path { |
516 | Some(path) => path, | 363 | Some(path) => path, |
@@ -615,78 +462,20 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
615 | } | 462 | } |
616 | } | 463 | } |
617 | 464 | ||
618 | /// The ID of a type variable. | ||
619 | #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] | ||
620 | pub struct TypeVarId(pub(super) u32); | ||
621 | |||
622 | impl UnifyKey for TypeVarId { | ||
623 | type Value = TypeVarValue; | ||
624 | |||
625 | fn index(&self) -> u32 { | ||
626 | self.0 | ||
627 | } | ||
628 | |||
629 | fn from_index(i: u32) -> Self { | ||
630 | TypeVarId(i) | ||
631 | } | ||
632 | |||
633 | fn tag() -> &'static str { | ||
634 | "TypeVarId" | ||
635 | } | ||
636 | } | ||
637 | |||
638 | /// The value of a type variable: either we already know the type, or we don't | ||
639 | /// know it yet. | ||
640 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
641 | pub enum TypeVarValue { | ||
642 | Known(Ty), | ||
643 | Unknown, | ||
644 | } | ||
645 | |||
646 | impl TypeVarValue { | ||
647 | fn known(&self) -> Option<&Ty> { | ||
648 | match self { | ||
649 | TypeVarValue::Known(ty) => Some(ty), | ||
650 | TypeVarValue::Unknown => None, | ||
651 | } | ||
652 | } | ||
653 | } | ||
654 | |||
655 | impl UnifyValue for TypeVarValue { | ||
656 | type Error = NoError; | ||
657 | |||
658 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { | ||
659 | match (value1, value2) { | ||
660 | // We should never equate two type variables, both of which have | ||
661 | // known types. Instead, we recursively equate those types. | ||
662 | (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!( | ||
663 | "equating two type variables, both of which have known types: {:?} and {:?}", | ||
664 | t1, t2 | ||
665 | ), | ||
666 | |||
667 | // If one side is known, prefer that one. | ||
668 | (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), | ||
669 | (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), | ||
670 | |||
671 | (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), | ||
672 | } | ||
673 | } | ||
674 | } | ||
675 | |||
676 | /// The kinds of placeholders we need during type inference. There's separate | 465 | /// The kinds of placeholders we need during type inference. There's separate |
677 | /// values for general types, and for integer and float variables. The latter | 466 | /// values for general types, and for integer and float variables. The latter |
678 | /// two are used for inference of literal values (e.g. `100` could be one of | 467 | /// two are used for inference of literal values (e.g. `100` could be one of |
679 | /// several integer types). | 468 | /// several integer types). |
680 | #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] | 469 | #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] |
681 | pub enum InferTy { | 470 | pub enum InferTy { |
682 | TypeVar(TypeVarId), | 471 | TypeVar(unify::TypeVarId), |
683 | IntVar(TypeVarId), | 472 | IntVar(unify::TypeVarId), |
684 | FloatVar(TypeVarId), | 473 | FloatVar(unify::TypeVarId), |
685 | MaybeNeverTypeVar(TypeVarId), | 474 | MaybeNeverTypeVar(unify::TypeVarId), |
686 | } | 475 | } |
687 | 476 | ||
688 | impl InferTy { | 477 | impl InferTy { |
689 | fn to_inner(self) -> TypeVarId { | 478 | fn to_inner(self) -> unify::TypeVarId { |
690 | match self { | 479 | match self { |
691 | InferTy::TypeVar(ty) | 480 | InferTy::TypeVar(ty) |
692 | | InferTy::IntVar(ty) | 481 | | InferTy::IntVar(ty) |
diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs index 064993d34..9bfc701cd 100644 --- a/crates/ra_hir_ty/src/infer/coerce.rs +++ b/crates/ra_hir_ty/src/infer/coerce.rs | |||
@@ -10,7 +10,7 @@ use test_utils::tested_by; | |||
10 | 10 | ||
11 | use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; | 11 | use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; |
12 | 12 | ||
13 | use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue}; | 13 | use super::{InEnvironment, InferTy, InferenceContext, unify::TypeVarValue}; |
14 | 14 | ||
15 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | 15 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { |
16 | /// Unify two types, but may coerce the first one to the second one | 16 | /// Unify two types, but may coerce the first one to the second one |
@@ -85,8 +85,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
85 | match (&from_ty, to_ty) { | 85 | match (&from_ty, to_ty) { |
86 | // Never type will make type variable to fallback to Never Type instead of Unknown. | 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))) => { | 87 | (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => { |
88 | let var = self.new_maybe_never_type_var(); | 88 | let var = self.table.new_maybe_never_type_var(); |
89 | self.var_unification_table.union_value(*tv, TypeVarValue::Known(var)); | 89 | self.table.var_unification_table.union_value(*tv, TypeVarValue::Known(var)); |
90 | return true; | 90 | return true; |
91 | } | 91 | } |
92 | (ty_app!(TypeCtor::Never), _) => return true, | 92 | (ty_app!(TypeCtor::Never), _) => return true, |
@@ -94,7 +94,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
94 | // Trivial cases, this should go after `never` check to | 94 | // Trivial cases, this should go after `never` check to |
95 | // avoid infer result type to be never | 95 | // avoid infer result type to be never |
96 | _ => { | 96 | _ => { |
97 | if self.unify_inner_trivial(&from_ty, &to_ty) { | 97 | if self.table.unify_inner_trivial(&from_ty, &to_ty) { |
98 | return true; | 98 | return true; |
99 | } | 99 | } |
100 | } | 100 | } |
@@ -330,7 +330,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
330 | // Stop when constructor matches. | 330 | // Stop when constructor matches. |
331 | (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => { | 331 | (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => { |
332 | // It will not recurse to `coerce`. | 332 | // It will not recurse to `coerce`. |
333 | return self.unify_substs(st1, st2, 0); | 333 | return self.table.unify_substs(st1, st2, 0); |
334 | } | 334 | } |
335 | _ => {} | 335 | _ => {} |
336 | } | 336 | } |
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs index 4014f4732..1e78f6efd 100644 --- a/crates/ra_hir_ty/src/infer/expr.rs +++ b/crates/ra_hir_ty/src/infer/expr.rs | |||
@@ -32,7 +32,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
32 | TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() }, | 32 | TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() }, |
33 | ); | 33 | ); |
34 | } | 34 | } |
35 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 35 | let ty = self.resolve_ty_as_possible(ty); |
36 | ty | 36 | ty |
37 | } | 37 | } |
38 | 38 | ||
@@ -53,7 +53,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
53 | expected.ty.clone() | 53 | expected.ty.clone() |
54 | }; | 54 | }; |
55 | 55 | ||
56 | self.resolve_ty_as_possible(&mut vec![], ty) | 56 | self.resolve_ty_as_possible(ty) |
57 | } | 57 | } |
58 | 58 | ||
59 | fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { | 59 | fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { |
@@ -94,7 +94,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
94 | 94 | ||
95 | let pat_ty = match self.resolve_into_iter_item() { | 95 | let pat_ty = match self.resolve_into_iter_item() { |
96 | Some(into_iter_item_alias) => { | 96 | Some(into_iter_item_alias) => { |
97 | let pat_ty = self.new_type_var(); | 97 | let pat_ty = self.table.new_type_var(); |
98 | let projection = ProjectionPredicate { | 98 | let projection = ProjectionPredicate { |
99 | ty: pat_ty.clone(), | 99 | ty: pat_ty.clone(), |
100 | projection_ty: ProjectionTy { | 100 | projection_ty: ProjectionTy { |
@@ -103,7 +103,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
103 | }, | 103 | }, |
104 | }; | 104 | }; |
105 | self.obligations.push(Obligation::Projection(projection)); | 105 | self.obligations.push(Obligation::Projection(projection)); |
106 | self.resolve_ty_as_possible(&mut vec![], pat_ty) | 106 | self.resolve_ty_as_possible(pat_ty) |
107 | } | 107 | } |
108 | None => Ty::Unknown, | 108 | None => Ty::Unknown, |
109 | }; | 109 | }; |
@@ -128,7 +128,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
128 | } | 128 | } |
129 | 129 | ||
130 | // add return type | 130 | // add return type |
131 | let ret_ty = self.new_type_var(); | 131 | let ret_ty = self.table.new_type_var(); |
132 | sig_tys.push(ret_ty.clone()); | 132 | sig_tys.push(ret_ty.clone()); |
133 | let sig_ty = Ty::apply( | 133 | let sig_ty = Ty::apply( |
134 | TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 }, | 134 | TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 }, |
@@ -167,7 +167,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
167 | Expr::Match { expr, arms } => { | 167 | Expr::Match { expr, arms } => { |
168 | let input_ty = self.infer_expr(*expr, &Expectation::none()); | 168 | let input_ty = self.infer_expr(*expr, &Expectation::none()); |
169 | 169 | ||
170 | let mut result_ty = self.new_maybe_never_type_var(); | 170 | let mut result_ty = self.table.new_maybe_never_type_var(); |
171 | 171 | ||
172 | for arm in arms { | 172 | for arm in arms { |
173 | for &pat in &arm.pats { | 173 | for &pat in &arm.pats { |
@@ -283,7 +283,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
283 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); | 283 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); |
284 | let ty = match self.resolve_future_future_output() { | 284 | let ty = match self.resolve_future_future_output() { |
285 | Some(future_future_output_alias) => { | 285 | Some(future_future_output_alias) => { |
286 | let ty = self.new_type_var(); | 286 | let ty = self.table.new_type_var(); |
287 | let projection = ProjectionPredicate { | 287 | let projection = ProjectionPredicate { |
288 | ty: ty.clone(), | 288 | ty: ty.clone(), |
289 | projection_ty: ProjectionTy { | 289 | projection_ty: ProjectionTy { |
@@ -292,7 +292,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
292 | }, | 292 | }, |
293 | }; | 293 | }; |
294 | self.obligations.push(Obligation::Projection(projection)); | 294 | self.obligations.push(Obligation::Projection(projection)); |
295 | self.resolve_ty_as_possible(&mut vec![], ty) | 295 | self.resolve_ty_as_possible(ty) |
296 | } | 296 | } |
297 | None => Ty::Unknown, | 297 | None => Ty::Unknown, |
298 | }; | 298 | }; |
@@ -302,7 +302,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
302 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); | 302 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); |
303 | let ty = match self.resolve_ops_try_ok() { | 303 | let ty = match self.resolve_ops_try_ok() { |
304 | Some(ops_try_ok_alias) => { | 304 | Some(ops_try_ok_alias) => { |
305 | let ty = self.new_type_var(); | 305 | let ty = self.table.new_type_var(); |
306 | let projection = ProjectionPredicate { | 306 | let projection = ProjectionPredicate { |
307 | ty: ty.clone(), | 307 | ty: ty.clone(), |
308 | projection_ty: ProjectionTy { | 308 | projection_ty: ProjectionTy { |
@@ -311,7 +311,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
311 | }, | 311 | }, |
312 | }; | 312 | }; |
313 | self.obligations.push(Obligation::Projection(projection)); | 313 | self.obligations.push(Obligation::Projection(projection)); |
314 | self.resolve_ty_as_possible(&mut vec![], ty) | 314 | self.resolve_ty_as_possible(ty) |
315 | } | 315 | } |
316 | None => Ty::Unknown, | 316 | None => Ty::Unknown, |
317 | }; | 317 | }; |
@@ -465,10 +465,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
465 | ty_app!(TypeCtor::Tuple { .. }, st) => st | 465 | ty_app!(TypeCtor::Tuple { .. }, st) => st |
466 | .iter() | 466 | .iter() |
467 | .cloned() | 467 | .cloned() |
468 | .chain(repeat_with(|| self.new_type_var())) | 468 | .chain(repeat_with(|| self.table.new_type_var())) |
469 | .take(exprs.len()) | 469 | .take(exprs.len()) |
470 | .collect::<Vec<_>>(), | 470 | .collect::<Vec<_>>(), |
471 | _ => (0..exprs.len()).map(|_| self.new_type_var()).collect(), | 471 | _ => (0..exprs.len()).map(|_| self.table.new_type_var()).collect(), |
472 | }; | 472 | }; |
473 | 473 | ||
474 | for (expr, ty) in exprs.iter().zip(tys.iter_mut()) { | 474 | for (expr, ty) in exprs.iter().zip(tys.iter_mut()) { |
@@ -482,7 +482,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
482 | ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => { | 482 | ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => { |
483 | st.as_single().clone() | 483 | st.as_single().clone() |
484 | } | 484 | } |
485 | _ => self.new_type_var(), | 485 | _ => self.table.new_type_var(), |
486 | }; | 486 | }; |
487 | 487 | ||
488 | match array { | 488 | match array { |
@@ -524,7 +524,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
524 | }; | 524 | }; |
525 | // use a new type variable if we got Ty::Unknown here | 525 | // use a new type variable if we got Ty::Unknown here |
526 | let ty = self.insert_type_vars_shallow(ty); | 526 | let ty = self.insert_type_vars_shallow(ty); |
527 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 527 | let ty = self.resolve_ty_as_possible(ty); |
528 | self.write_expr_ty(tgt_expr, ty.clone()); | 528 | self.write_expr_ty(tgt_expr, ty.clone()); |
529 | ty | 529 | ty |
530 | } | 530 | } |
@@ -553,7 +553,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
553 | } | 553 | } |
554 | } | 554 | } |
555 | 555 | ||
556 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 556 | let ty = self.resolve_ty_as_possible(ty); |
557 | self.infer_pat(*pat, &ty, BindingMode::default()); | 557 | self.infer_pat(*pat, &ty, BindingMode::default()); |
558 | } | 558 | } |
559 | Statement::Expr(expr) => { | 559 | Statement::Expr(expr) => { |
diff --git a/crates/ra_hir_ty/src/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs index 1ebb36239..a14662884 100644 --- a/crates/ra_hir_ty/src/infer/pat.rs +++ b/crates/ra_hir_ty/src/infer/pat.rs | |||
@@ -170,7 +170,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
170 | } | 170 | } |
171 | BindingMode::Move => inner_ty.clone(), | 171 | BindingMode::Move => inner_ty.clone(), |
172 | }; | 172 | }; |
173 | let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty); | 173 | let bound_ty = self.resolve_ty_as_possible(bound_ty); |
174 | self.write_pat_ty(pat, bound_ty); | 174 | self.write_pat_ty(pat, bound_ty); |
175 | return inner_ty; | 175 | return inner_ty; |
176 | } | 176 | } |
@@ -179,7 +179,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
179 | // use a new type variable if we got Ty::Unknown here | 179 | // use a new type variable if we got Ty::Unknown here |
180 | let ty = self.insert_type_vars_shallow(ty); | 180 | let ty = self.insert_type_vars_shallow(ty); |
181 | self.unify(&ty, expected); | 181 | self.unify(&ty, expected); |
182 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 182 | let ty = self.resolve_ty_as_possible(ty); |
183 | self.write_pat_ty(pat, ty.clone()); | 183 | self.write_pat_ty(pat, ty.clone()); |
184 | ty | 184 | ty |
185 | } | 185 | } |
diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs index bbf146418..d0d7646a4 100644 --- a/crates/ra_hir_ty/src/infer/path.rs +++ b/crates/ra_hir_ty/src/infer/path.rs | |||
@@ -57,7 +57,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
57 | let typable: ValueTyDefId = match value { | 57 | let typable: ValueTyDefId = match value { |
58 | ValueNs::LocalBinding(pat) => { | 58 | ValueNs::LocalBinding(pat) => { |
59 | let ty = self.result.type_of_pat.get(pat)?.clone(); | 59 | let ty = self.result.type_of_pat.get(pat)?.clone(); |
60 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 60 | let ty = self.resolve_ty_as_possible(ty); |
61 | return Some(ty); | 61 | return Some(ty); |
62 | } | 62 | } |
63 | ValueNs::FunctionId(it) => it.into(), | 63 | ValueNs::FunctionId(it) => it.into(), |
@@ -211,7 +211,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
211 | // we're picking this method | 211 | // we're picking this method |
212 | let trait_substs = Substs::build_for_def(self.db, trait_) | 212 | let trait_substs = Substs::build_for_def(self.db, trait_) |
213 | .push(ty.clone()) | 213 | .push(ty.clone()) |
214 | .fill(std::iter::repeat_with(|| self.new_type_var())) | 214 | .fill(std::iter::repeat_with(|| self.table.new_type_var())) |
215 | .build(); | 215 | .build(); |
216 | let substs = Substs::build_for_def(self.db, item) | 216 | let substs = Substs::build_for_def(self.db, item) |
217 | .use_parent_substs(&trait_substs) | 217 | .use_parent_substs(&trait_substs) |
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs index f3a875678..ff50138f5 100644 --- a/crates/ra_hir_ty/src/infer/unify.rs +++ b/crates/ra_hir_ty/src/infer/unify.rs | |||
@@ -1,9 +1,15 @@ | |||
1 | //! Unification and canonicalization logic. | 1 | //! Unification and canonicalization logic. |
2 | 2 | ||
3 | use std::borrow::Cow; | ||
4 | |||
5 | use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; | ||
6 | |||
7 | use test_utils::tested_by; | ||
8 | |||
3 | use super::{InferenceContext, Obligation}; | 9 | use super::{InferenceContext, Obligation}; |
4 | use crate::{ | 10 | use crate::{ |
5 | db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate, | 11 | db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate, |
6 | ProjectionTy, Substs, TraitRef, Ty, TypeWalk, | 12 | ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk, |
7 | }; | 13 | }; |
8 | 14 | ||
9 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | 15 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { |
@@ -24,7 +30,7 @@ where | |||
24 | /// A stack of type variables that is used to detect recursive types (which | 30 | /// A stack of type variables that is used to detect recursive types (which |
25 | /// are an error, but we need to protect against them to avoid stack | 31 | /// are an error, but we need to protect against them to avoid stack |
26 | /// overflows). | 32 | /// overflows). |
27 | var_stack: Vec<super::TypeVarId>, | 33 | var_stack: Vec<TypeVarId>, |
28 | } | 34 | } |
29 | 35 | ||
30 | pub(super) struct Canonicalized<T> { | 36 | pub(super) struct Canonicalized<T> { |
@@ -53,14 +59,14 @@ where | |||
53 | return tv.fallback_value(); | 59 | return tv.fallback_value(); |
54 | } | 60 | } |
55 | if let Some(known_ty) = | 61 | if let Some(known_ty) = |
56 | self.ctx.var_unification_table.inlined_probe_value(inner).known() | 62 | self.ctx.table.var_unification_table.inlined_probe_value(inner).known() |
57 | { | 63 | { |
58 | self.var_stack.push(inner); | 64 | self.var_stack.push(inner); |
59 | let result = self.do_canonicalize_ty(known_ty.clone()); | 65 | let result = self.do_canonicalize_ty(known_ty.clone()); |
60 | self.var_stack.pop(); | 66 | self.var_stack.pop(); |
61 | result | 67 | result |
62 | } else { | 68 | } else { |
63 | let root = self.ctx.var_unification_table.find(inner); | 69 | let root = self.ctx.table.var_unification_table.find(inner); |
64 | let free_var = match tv { | 70 | let free_var = match tv { |
65 | InferTy::TypeVar(_) => InferTy::TypeVar(root), | 71 | InferTy::TypeVar(_) => InferTy::TypeVar(root), |
66 | InferTy::IntVar(_) => InferTy::IntVar(root), | 72 | InferTy::IntVar(_) => InferTy::IntVar(root), |
@@ -153,10 +159,264 @@ impl<T> Canonicalized<T> { | |||
153 | solution: Canonical<Vec<Ty>>, | 159 | solution: Canonical<Vec<Ty>>, |
154 | ) { | 160 | ) { |
155 | // the solution may contain new variables, which we need to convert to new inference vars | 161 | // the solution may contain new variables, which we need to convert to new inference vars |
156 | let new_vars = Substs((0..solution.num_vars).map(|_| ctx.new_type_var()).collect()); | 162 | let new_vars = Substs((0..solution.num_vars).map(|_| ctx.table.new_type_var()).collect()); |
157 | for (i, ty) in solution.value.into_iter().enumerate() { | 163 | for (i, ty) in solution.value.into_iter().enumerate() { |
158 | let var = self.free_vars[i]; | 164 | let var = self.free_vars[i]; |
159 | ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); | 165 | ctx.table.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); |
166 | } | ||
167 | } | ||
168 | } | ||
169 | |||
170 | pub fn unify(ty1: Canonical<&Ty>, ty2: &Ty) -> Substs { | ||
171 | let mut table = InferenceTable::new(); | ||
172 | let vars = Substs::builder(ty1.num_vars) | ||
173 | .fill(std::iter::repeat_with(|| table.new_type_var())).build(); | ||
174 | let ty_with_vars = ty1.value.clone().subst_bound_vars(&vars); | ||
175 | table.unify(&ty_with_vars, ty2); | ||
176 | Substs::builder(ty1.num_vars).fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone()))).build() | ||
177 | } | ||
178 | |||
179 | #[derive(Clone, Debug)] | ||
180 | pub(crate) struct InferenceTable { | ||
181 | pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>, | ||
182 | } | ||
183 | |||
184 | impl InferenceTable { | ||
185 | pub fn new() -> Self { | ||
186 | InferenceTable { | ||
187 | var_unification_table: InPlaceUnificationTable::new(), | ||
188 | } | ||
189 | } | ||
190 | |||
191 | pub fn new_type_var(&mut self) -> Ty { | ||
192 | Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
193 | } | ||
194 | |||
195 | pub fn new_integer_var(&mut self) -> Ty { | ||
196 | Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
197 | } | ||
198 | |||
199 | pub fn new_float_var(&mut self) -> Ty { | ||
200 | Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
201 | } | ||
202 | |||
203 | pub fn new_maybe_never_type_var(&mut self) -> Ty { | ||
204 | Ty::Infer(InferTy::MaybeNeverTypeVar( | ||
205 | self.var_unification_table.new_key(TypeVarValue::Unknown), | ||
206 | )) | ||
207 | } | ||
208 | |||
209 | pub fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { | ||
210 | self.resolve_ty_completely_inner(&mut Vec::new(), ty) | ||
211 | } | ||
212 | |||
213 | pub fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { | ||
214 | self.resolve_ty_as_possible_inner(&mut Vec::new(), ty) | ||
215 | } | ||
216 | |||
217 | pub fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
218 | self.unify_inner(ty1, ty2, 0) | ||
219 | } | ||
220 | |||
221 | pub fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool { | ||
222 | substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth)) | ||
223 | } | ||
224 | |||
225 | fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | ||
226 | if depth > 1000 { | ||
227 | // prevent stackoverflows | ||
228 | panic!("infinite recursion in unification"); | ||
229 | } | ||
230 | if ty1 == ty2 { | ||
231 | return true; | ||
232 | } | ||
233 | // try to resolve type vars first | ||
234 | let ty1 = self.resolve_ty_shallow(ty1); | ||
235 | let ty2 = self.resolve_ty_shallow(ty2); | ||
236 | match (&*ty1, &*ty2) { | ||
237 | (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => { | ||
238 | self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1) | ||
239 | } | ||
240 | _ => self.unify_inner_trivial(&ty1, &ty2), | ||
241 | } | ||
242 | } | ||
243 | |||
244 | pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
245 | match (ty1, ty2) { | ||
246 | (Ty::Unknown, _) | (_, Ty::Unknown) => true, | ||
247 | |||
248 | (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2))) | ||
249 | | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2))) | ||
250 | | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2))) | ||
251 | | ( | ||
252 | Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)), | ||
253 | Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)), | ||
254 | ) => { | ||
255 | // both type vars are unknown since we tried to resolve them | ||
256 | self.var_unification_table.union(*tv1, *tv2); | ||
257 | true | ||
258 | } | ||
259 | |||
260 | // The order of MaybeNeverTypeVar matters here. | ||
261 | // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar. | ||
262 | // Unifying MaybeNeverTypeVar and other concrete type will let the former become it. | ||
263 | (Ty::Infer(InferTy::TypeVar(tv)), other) | ||
264 | | (other, Ty::Infer(InferTy::TypeVar(tv))) | ||
265 | | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other) | ||
266 | | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv))) | ||
267 | | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_))) | ||
268 | | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv))) | ||
269 | | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_))) | ||
270 | | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => { | ||
271 | // the type var is unknown since we tried to resolve it | ||
272 | self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone())); | ||
273 | true | ||
274 | } | ||
275 | |||
276 | _ => false, | ||
277 | } | ||
278 | } | ||
279 | |||
280 | /// If `ty` is a type variable with known type, returns that type; | ||
281 | /// otherwise, return ty. | ||
282 | pub fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { | ||
283 | let mut ty = Cow::Borrowed(ty); | ||
284 | // The type variable could resolve to a int/float variable. Hence try | ||
285 | // resolving up to three times; each type of variable shouldn't occur | ||
286 | // more than once | ||
287 | for i in 0..3 { | ||
288 | if i > 0 { | ||
289 | tested_by!(type_var_resolves_to_int_var); | ||
290 | } | ||
291 | match &*ty { | ||
292 | Ty::Infer(tv) => { | ||
293 | let inner = tv.to_inner(); | ||
294 | match self.var_unification_table.inlined_probe_value(inner).known() { | ||
295 | Some(known_ty) => { | ||
296 | // The known_ty can't be a type var itself | ||
297 | ty = Cow::Owned(known_ty.clone()); | ||
298 | } | ||
299 | _ => return ty, | ||
300 | } | ||
301 | } | ||
302 | _ => return ty, | ||
303 | } | ||
304 | } | ||
305 | log::error!("Inference variable still not resolved: {:?}", ty); | ||
306 | ty | ||
307 | } | ||
308 | |||
309 | /// Resolves the type as far as currently possible, replacing type variables | ||
310 | /// by their known types. All types returned by the infer_* functions should | ||
311 | /// be resolved as far as possible, i.e. contain no type variables with | ||
312 | /// known type. | ||
313 | fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
314 | ty.fold(&mut |ty| match ty { | ||
315 | Ty::Infer(tv) => { | ||
316 | let inner = tv.to_inner(); | ||
317 | if tv_stack.contains(&inner) { | ||
318 | tested_by!(type_var_cycles_resolve_as_possible); | ||
319 | // recursive type | ||
320 | return tv.fallback_value(); | ||
321 | } | ||
322 | if let Some(known_ty) = | ||
323 | self.var_unification_table.inlined_probe_value(inner).known() | ||
324 | { | ||
325 | // known_ty may contain other variables that are known by now | ||
326 | tv_stack.push(inner); | ||
327 | let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone()); | ||
328 | tv_stack.pop(); | ||
329 | result | ||
330 | } else { | ||
331 | ty | ||
332 | } | ||
333 | } | ||
334 | _ => ty, | ||
335 | }) | ||
336 | } | ||
337 | |||
338 | /// Resolves the type completely; type variables without known type are | ||
339 | /// replaced by Ty::Unknown. | ||
340 | fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
341 | ty.fold(&mut |ty| match ty { | ||
342 | Ty::Infer(tv) => { | ||
343 | let inner = tv.to_inner(); | ||
344 | if tv_stack.contains(&inner) { | ||
345 | tested_by!(type_var_cycles_resolve_completely); | ||
346 | // recursive type | ||
347 | return tv.fallback_value(); | ||
348 | } | ||
349 | if let Some(known_ty) = | ||
350 | self.var_unification_table.inlined_probe_value(inner).known() | ||
351 | { | ||
352 | // known_ty may contain other variables that are known by now | ||
353 | tv_stack.push(inner); | ||
354 | let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone()); | ||
355 | tv_stack.pop(); | ||
356 | result | ||
357 | } else { | ||
358 | tv.fallback_value() | ||
359 | } | ||
360 | } | ||
361 | _ => ty, | ||
362 | }) | ||
363 | } | ||
364 | } | ||
365 | |||
366 | /// The ID of a type variable. | ||
367 | #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] | ||
368 | pub struct TypeVarId(pub(super) u32); | ||
369 | |||
370 | impl UnifyKey for TypeVarId { | ||
371 | type Value = TypeVarValue; | ||
372 | |||
373 | fn index(&self) -> u32 { | ||
374 | self.0 | ||
375 | } | ||
376 | |||
377 | fn from_index(i: u32) -> Self { | ||
378 | TypeVarId(i) | ||
379 | } | ||
380 | |||
381 | fn tag() -> &'static str { | ||
382 | "TypeVarId" | ||
383 | } | ||
384 | } | ||
385 | |||
386 | /// The value of a type variable: either we already know the type, or we don't | ||
387 | /// know it yet. | ||
388 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
389 | pub enum TypeVarValue { | ||
390 | Known(Ty), | ||
391 | Unknown, | ||
392 | } | ||
393 | |||
394 | impl TypeVarValue { | ||
395 | fn known(&self) -> Option<&Ty> { | ||
396 | match self { | ||
397 | TypeVarValue::Known(ty) => Some(ty), | ||
398 | TypeVarValue::Unknown => None, | ||
399 | } | ||
400 | } | ||
401 | } | ||
402 | |||
403 | impl UnifyValue for TypeVarValue { | ||
404 | type Error = NoError; | ||
405 | |||
406 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { | ||
407 | match (value1, value2) { | ||
408 | // We should never equate two type variables, both of which have | ||
409 | // known types. Instead, we recursively equate those types. | ||
410 | (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!( | ||
411 | "equating two type variables, both of which have known types: {:?} and {:?}", | ||
412 | t1, t2 | ||
413 | ), | ||
414 | |||
415 | // If one side is known, prefer that one. | ||
416 | (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), | ||
417 | (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), | ||
418 | |||
419 | (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), | ||
160 | } | 420 | } |
161 | } | 421 | } |
162 | } | 422 | } |