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/infer.rs | |
parent | cbf262a1bc72f10dc93a4993da0012d3b0abb56f (diff) |
Extract unification code to unify module
Diffstat (limited to 'crates/ra_hir_ty/src/infer.rs')
-rw-r--r-- | crates/ra_hir_ty/src/infer.rs | 255 |
1 files changed, 22 insertions, 233 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) |