aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_ty/src/infer.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir_ty/src/infer.rs')
-rw-r--r--crates/ra_hir_ty/src/infer.rs255
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;
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)
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-08 02:03:30 +0100