aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_ty
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir_ty')
-rw-r--r--crates/ra_hir_ty/src/infer.rs255
-rw-r--r--crates/ra_hir_ty/src/infer/coerce.rs10
-rw-r--r--crates/ra_hir_ty/src/infer/expr.rs30
-rw-r--r--crates/ra_hir_ty/src/infer/pat.rs4
-rw-r--r--crates/ra_hir_ty/src/infer/path.rs4
-rw-r--r--crates/ra_hir_ty/src/infer/unify.rs272
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;
18use std::ops::Index; 18use std::ops::Index;
19use std::sync::Arc; 19use std::sync::Arc;
20 20
21use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
22use rustc_hash::FxHashMap; 21use rustc_hash::FxHashMap;
23 22
24use hir_def::{ 23use hir_def::{
@@ -33,12 +32,11 @@ use hir_def::{
33use hir_expand::{diagnostics::DiagnosticSink, name}; 32use hir_expand::{diagnostics::DiagnosticSink, name};
34use ra_arena::map::ArenaMap; 33use ra_arena::map::ArenaMap;
35use ra_prof::profile; 34use ra_prof::profile;
36use test_utils::tested_by;
37 35
38use super::{ 36use 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};
44use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; 42use 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)]
620pub struct TypeVarId(pub(super) u32);
621
622impl 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)]
641pub enum TypeVarValue {
642 Known(Ty),
643 Unknown,
644}
645
646impl TypeVarValue {
647 fn known(&self) -> Option<&Ty> {
648 match self {
649 TypeVarValue::Known(ty) => Some(ty),
650 TypeVarValue::Unknown => None,
651 }
652 }
653}
654
655impl 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)]
681pub enum InferTy { 470pub 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
688impl InferTy { 477impl 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
11use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; 11use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk};
12 12
13use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue}; 13use super::{InEnvironment, InferTy, InferenceContext, unify::TypeVarValue};
14 14
15impl<'a, D: HirDatabase> InferenceContext<'a, D> { 15impl<'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
3use std::borrow::Cow;
4
5use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
6
7use test_utils::tested_by;
8
3use super::{InferenceContext, Obligation}; 9use super::{InferenceContext, Obligation};
4use crate::{ 10use 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
9impl<'a, D: HirDatabase> InferenceContext<'a, D> { 15impl<'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
30pub(super) struct Canonicalized<T> { 36pub(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
170pub 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)]
180pub(crate) struct InferenceTable {
181 pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>,
182}
183
184impl 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)]
368pub struct TypeVarId(pub(super) u32);
369
370impl 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)]
389pub enum TypeVarValue {
390 Known(Ty),
391 Unknown,
392}
393
394impl TypeVarValue {
395 fn known(&self) -> Option<&Ty> {
396 match self {
397 TypeVarValue::Known(ty) => Some(ty),
398 TypeVarValue::Unknown => None,
399 }
400 }
401}
402
403impl 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}