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.rs259
-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.rs42
-rw-r--r--crates/ra_hir_ty/src/infer/unify.rs276
-rw-r--r--crates/ra_hir_ty/src/method_resolution.rs225
-rw-r--r--crates/ra_hir_ty/src/tests.rs31
8 files changed, 537 insertions, 340 deletions
diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs
index fe259371f..d16f1eb46 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,16 +32,17 @@ 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, TypeWalk,
42 TypeWalk, Uncertain, 40 Uncertain,
43}; 41};
44use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; 42use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic};
45 43
44pub(crate) use unify::unify;
45
46macro_rules! ty_app { 46macro_rules! ty_app {
47 ($ctor:pat, $param:pat) => { 47 ($ctor:pat, $param:pat) => {
48 crate::Ty::Apply(crate::ApplicationTy { ctor: $ctor, parameters: $param }) 48 crate::Ty::Apply(crate::ApplicationTy { ctor: $ctor, parameters: $param })
@@ -191,7 +191,7 @@ struct InferenceContext<'a, D: HirDatabase> {
191 owner: DefWithBodyId, 191 owner: DefWithBodyId,
192 body: Arc<Body>, 192 body: Arc<Body>,
193 resolver: Resolver, 193 resolver: Resolver,
194 var_unification_table: InPlaceUnificationTable<TypeVarId>, 194 table: unify::InferenceTable,
195 trait_env: Arc<TraitEnvironment>, 195 trait_env: Arc<TraitEnvironment>,
196 obligations: Vec<Obligation>, 196 obligations: Vec<Obligation>,
197 result: InferenceResult, 197 result: InferenceResult,
@@ -209,7 +209,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
209 fn new(db: &'a D, owner: DefWithBodyId, resolver: Resolver) -> Self { 209 fn new(db: &'a D, owner: DefWithBodyId, resolver: Resolver) -> Self {
210 InferenceContext { 210 InferenceContext {
211 result: InferenceResult::default(), 211 result: InferenceResult::default(),
212 var_unification_table: InPlaceUnificationTable::new(), 212 table: unify::InferenceTable::new(),
213 obligations: Vec::default(), 213 obligations: Vec::default(),
214 return_ty: Ty::Unknown, // set in collect_fn_signature 214 return_ty: Ty::Unknown, // set in collect_fn_signature
215 trait_env: TraitEnvironment::lower(db, &resolver), 215 trait_env: TraitEnvironment::lower(db, &resolver),
@@ -224,13 +224,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
224 fn resolve_all(mut self) -> InferenceResult { 224 fn resolve_all(mut self) -> InferenceResult {
225 // FIXME resolve obligations as well (use Guidance if necessary) 225 // FIXME resolve obligations as well (use Guidance if necessary)
226 let mut result = mem::replace(&mut self.result, InferenceResult::default()); 226 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() { 227 for ty in result.type_of_expr.values_mut() {
229 let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); 228 let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown));
230 *ty = resolved; 229 *ty = resolved;
231 } 230 }
232 for ty in result.type_of_pat.values_mut() { 231 for ty in result.type_of_pat.values_mut() {
233 let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); 232 let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown));
234 *ty = resolved; 233 *ty = resolved;
235 } 234 }
236 result 235 result
@@ -275,96 +274,15 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
275 self.normalize_associated_types_in(ty) 274 self.normalize_associated_types_in(ty)
276 } 275 }
277 276
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. 277 /// 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 { 278 fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
361 match ty { 279 match ty {
362 Ty::Unknown => self.new_type_var(), 280 Ty::Unknown => self.table.new_type_var(),
363 Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(Uncertain::Unknown), .. }) => { 281 Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(Uncertain::Unknown), .. }) => {
364 self.new_integer_var() 282 self.table.new_integer_var()
365 } 283 }
366 Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(Uncertain::Unknown), .. }) => { 284 Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(Uncertain::Unknown), .. }) => {
367 self.new_float_var() 285 self.table.new_float_var()
368 } 286 }
369 _ => ty, 287 _ => ty,
370 } 288 }
@@ -402,64 +320,22 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
402 } 320 }
403 } 321 }
404 322
323 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
324 self.table.unify(ty1, ty2)
325 }
326
405 /// Resolves the type as far as currently possible, replacing type variables 327 /// Resolves the type as far as currently possible, replacing type variables
406 /// by their known types. All types returned by the infer_* functions should 328 /// 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 329 /// be resolved as far as possible, i.e. contain no type variables with
408 /// known type. 330 /// known type.
409 fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { 331 fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty {
410 self.resolve_obligations_as_possible(); 332 self.resolve_obligations_as_possible();
411 333
412 ty.fold(&mut |ty| match ty { 334 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 } 335 }
435 336
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> { 337 fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
439 let mut ty = Cow::Borrowed(ty); 338 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 } 339 }
464 340
465 /// Recurses through the given type, normalizing associated types mentioned 341 /// Recurses through the given type, normalizing associated types mentioned
@@ -469,7 +345,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
469 /// call). `make_ty` handles this already, but e.g. for field types we need 345 /// call). `make_ty` handles this already, but e.g. for field types we need
470 /// to do it as well. 346 /// to do it as well.
471 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { 347 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
472 let ty = self.resolve_ty_as_possible(&mut vec![], ty); 348 let ty = self.resolve_ty_as_possible(ty);
473 ty.fold(&mut |ty| match ty { 349 ty.fold(&mut |ty| match ty {
474 Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty), 350 Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty),
475 _ => ty, 351 _ => ty,
@@ -477,40 +353,13 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
477 } 353 }
478 354
479 fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { 355 fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
480 let var = self.new_type_var(); 356 let var = self.table.new_type_var();
481 let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() }; 357 let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() };
482 let obligation = Obligation::Projection(predicate); 358 let obligation = Obligation::Projection(predicate);
483 self.obligations.push(obligation); 359 self.obligations.push(obligation);
484 var 360 var
485 } 361 }
486 362
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>) { 363 fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) {
515 let path = match path { 364 let path = match path {
516 Some(path) => path, 365 Some(path) => path,
@@ -615,78 +464,20 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
615 } 464 }
616} 465}
617 466
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 467/// 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 468/// 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 469/// two are used for inference of literal values (e.g. `100` could be one of
679/// several integer types). 470/// several integer types).
680#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] 471#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
681pub enum InferTy { 472pub enum InferTy {
682 TypeVar(TypeVarId), 473 TypeVar(unify::TypeVarId),
683 IntVar(TypeVarId), 474 IntVar(unify::TypeVarId),
684 FloatVar(TypeVarId), 475 FloatVar(unify::TypeVarId),
685 MaybeNeverTypeVar(TypeVarId), 476 MaybeNeverTypeVar(unify::TypeVarId),
686} 477}
687 478
688impl InferTy { 479impl InferTy {
689 fn to_inner(self) -> TypeVarId { 480 fn to_inner(self) -> unify::TypeVarId {
690 match self { 481 match self {
691 InferTy::TypeVar(ty) 482 InferTy::TypeVar(ty)
692 | InferTy::IntVar(ty) 483 | 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..9daa77cfa 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::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext};
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..b0024c6e1 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(),
@@ -206,12 +206,14 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
206 AssocItemId::TypeAliasId(_) => unreachable!(), 206 AssocItemId::TypeAliasId(_) => unreachable!(),
207 }; 207 };
208 let substs = match container { 208 let substs = match container {
209 ContainerId::ImplId(_) => self.find_self_types(&def, ty.clone()), 209 ContainerId::ImplId(impl_id) => {
210 method_resolution::inherent_impl_substs(self.db, impl_id, &ty)
211 }
210 ContainerId::TraitId(trait_) => { 212 ContainerId::TraitId(trait_) => {
211 // we're picking this method 213 // we're picking this method
212 let trait_substs = Substs::build_for_def(self.db, trait_) 214 let trait_substs = Substs::build_for_def(self.db, trait_)
213 .push(ty.clone()) 215 .push(ty.clone())
214 .fill(std::iter::repeat_with(|| self.new_type_var())) 216 .fill(std::iter::repeat_with(|| self.table.new_type_var()))
215 .build(); 217 .build();
216 let substs = Substs::build_for_def(self.db, item) 218 let substs = Substs::build_for_def(self.db, item)
217 .use_parent_substs(&trait_substs) 219 .use_parent_substs(&trait_substs)
@@ -231,38 +233,4 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
231 }, 233 },
232 ) 234 )
233 } 235 }
234
235 fn find_self_types(&self, def: &ValueNs, actual_def_ty: Ty) -> Option<Substs> {
236 if let ValueNs::FunctionId(func) = *def {
237 // We only do the infer if parent has generic params
238 let gen = self.db.generic_params(func.into());
239 if gen.count_parent_params() == 0 {
240 return None;
241 }
242
243 let impl_id = match func.lookup(self.db).container {
244 ContainerId::ImplId(it) => it,
245 _ => return None,
246 };
247 let self_ty = self.db.impl_self_ty(impl_id).clone();
248 let self_ty_substs = self_ty.substs()?;
249 let actual_substs = actual_def_ty.substs()?;
250
251 let mut new_substs = vec![Ty::Unknown; gen.count_parent_params()];
252
253 // The following code *link up* the function actual parma type
254 // and impl_block type param index
255 self_ty_substs.iter().zip(actual_substs.iter()).for_each(|(param, pty)| {
256 if let Ty::Param { idx, .. } = param {
257 if let Some(s) = new_substs.get_mut(*idx as usize) {
258 *s = pty.clone();
259 }
260 }
261 });
262
263 Some(Substs(new_substs.into()))
264 } else {
265 None
266 }
267 }
268} 236}
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
index f3a875678..8ed2a6090 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,268 @@ 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) -> Option<Substs> {
171 let mut table = InferenceTable::new();
172 let vars =
173 Substs::builder(ty1.num_vars).fill(std::iter::repeat_with(|| table.new_type_var())).build();
174 let ty_with_vars = ty1.value.clone().subst_bound_vars(&vars);
175 if !table.unify(&ty_with_vars, ty2) {
176 return None;
177 }
178 Some(
179 Substs::builder(ty1.num_vars)
180 .fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone())))
181 .build(),
182 )
183}
184
185#[derive(Clone, Debug)]
186pub(crate) struct InferenceTable {
187 pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>,
188}
189
190impl InferenceTable {
191 pub fn new() -> Self {
192 InferenceTable { var_unification_table: InPlaceUnificationTable::new() }
193 }
194
195 pub fn new_type_var(&mut self) -> Ty {
196 Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
197 }
198
199 pub fn new_integer_var(&mut self) -> Ty {
200 Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
201 }
202
203 pub fn new_float_var(&mut self) -> Ty {
204 Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
205 }
206
207 pub fn new_maybe_never_type_var(&mut self) -> Ty {
208 Ty::Infer(InferTy::MaybeNeverTypeVar(
209 self.var_unification_table.new_key(TypeVarValue::Unknown),
210 ))
211 }
212
213 pub fn resolve_ty_completely(&mut self, ty: Ty) -> Ty {
214 self.resolve_ty_completely_inner(&mut Vec::new(), ty)
215 }
216
217 pub fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty {
218 self.resolve_ty_as_possible_inner(&mut Vec::new(), ty)
219 }
220
221 pub fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
222 self.unify_inner(ty1, ty2, 0)
223 }
224
225 pub fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool {
226 substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth))
227 }
228
229 fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
230 if depth > 1000 {
231 // prevent stackoverflows
232 panic!("infinite recursion in unification");
233 }
234 if ty1 == ty2 {
235 return true;
236 }
237 // try to resolve type vars first
238 let ty1 = self.resolve_ty_shallow(ty1);
239 let ty2 = self.resolve_ty_shallow(ty2);
240 match (&*ty1, &*ty2) {
241 (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => {
242 self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1)
243 }
244 _ => self.unify_inner_trivial(&ty1, &ty2),
245 }
246 }
247
248 pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
249 match (ty1, ty2) {
250 (Ty::Unknown, _) | (_, Ty::Unknown) => true,
251
252 (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
253 | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
254 | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2)))
255 | (
256 Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)),
257 Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)),
258 ) => {
259 // both type vars are unknown since we tried to resolve them
260 self.var_unification_table.union(*tv1, *tv2);
261 true
262 }
263
264 // The order of MaybeNeverTypeVar matters here.
265 // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar.
266 // Unifying MaybeNeverTypeVar and other concrete type will let the former become it.
267 (Ty::Infer(InferTy::TypeVar(tv)), other)
268 | (other, Ty::Infer(InferTy::TypeVar(tv)))
269 | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other)
270 | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv)))
271 | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_)))
272 | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv)))
273 | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_)))
274 | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => {
275 // the type var is unknown since we tried to resolve it
276 self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone()));
277 true
278 }
279
280 _ => false,
281 }
282 }
283
284 /// If `ty` is a type variable with known type, returns that type;
285 /// otherwise, return ty.
286 pub fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
287 let mut ty = Cow::Borrowed(ty);
288 // The type variable could resolve to a int/float variable. Hence try
289 // resolving up to three times; each type of variable shouldn't occur
290 // more than once
291 for i in 0..3 {
292 if i > 0 {
293 tested_by!(type_var_resolves_to_int_var);
294 }
295 match &*ty {
296 Ty::Infer(tv) => {
297 let inner = tv.to_inner();
298 match self.var_unification_table.inlined_probe_value(inner).known() {
299 Some(known_ty) => {
300 // The known_ty can't be a type var itself
301 ty = Cow::Owned(known_ty.clone());
302 }
303 _ => return ty,
304 }
305 }
306 _ => return ty,
307 }
308 }
309 log::error!("Inference variable still not resolved: {:?}", ty);
310 ty
311 }
312
313 /// Resolves the type as far as currently possible, replacing type variables
314 /// by their known types. All types returned by the infer_* functions should
315 /// be resolved as far as possible, i.e. contain no type variables with
316 /// known type.
317 fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
318 ty.fold(&mut |ty| match ty {
319 Ty::Infer(tv) => {
320 let inner = tv.to_inner();
321 if tv_stack.contains(&inner) {
322 tested_by!(type_var_cycles_resolve_as_possible);
323 // recursive type
324 return tv.fallback_value();
325 }
326 if let Some(known_ty) =
327 self.var_unification_table.inlined_probe_value(inner).known()
328 {
329 // known_ty may contain other variables that are known by now
330 tv_stack.push(inner);
331 let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone());
332 tv_stack.pop();
333 result
334 } else {
335 ty
336 }
337 }
338 _ => ty,
339 })
340 }
341
342 /// Resolves the type completely; type variables without known type are
343 /// replaced by Ty::Unknown.
344 fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
345 ty.fold(&mut |ty| match ty {
346 Ty::Infer(tv) => {
347 let inner = tv.to_inner();
348 if tv_stack.contains(&inner) {
349 tested_by!(type_var_cycles_resolve_completely);
350 // recursive type
351 return tv.fallback_value();
352 }
353 if let Some(known_ty) =
354 self.var_unification_table.inlined_probe_value(inner).known()
355 {
356 // known_ty may contain other variables that are known by now
357 tv_stack.push(inner);
358 let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone());
359 tv_stack.pop();
360 result
361 } else {
362 tv.fallback_value()
363 }
364 }
365 _ => ty,
366 })
367 }
368}
369
370/// The ID of a type variable.
371#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
372pub struct TypeVarId(pub(super) u32);
373
374impl UnifyKey for TypeVarId {
375 type Value = TypeVarValue;
376
377 fn index(&self) -> u32 {
378 self.0
379 }
380
381 fn from_index(i: u32) -> Self {
382 TypeVarId(i)
383 }
384
385 fn tag() -> &'static str {
386 "TypeVarId"
387 }
388}
389
390/// The value of a type variable: either we already know the type, or we don't
391/// know it yet.
392#[derive(Clone, PartialEq, Eq, Debug)]
393pub enum TypeVarValue {
394 Known(Ty),
395 Unknown,
396}
397
398impl TypeVarValue {
399 fn known(&self) -> Option<&Ty> {
400 match self {
401 TypeVarValue::Known(ty) => Some(ty),
402 TypeVarValue::Unknown => None,
403 }
404 }
405}
406
407impl UnifyValue for TypeVarValue {
408 type Error = NoError;
409
410 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
411 match (value1, value2) {
412 // We should never equate two type variables, both of which have
413 // known types. Instead, we recursively equate those types.
414 (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
415 "equating two type variables, both of which have known types: {:?} and {:?}",
416 t1, t2
417 ),
418
419 // If one side is known, prefer that one.
420 (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
421 (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
422
423 (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
160 } 424 }
161 } 425 }
162} 426}
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index 2bded3dbd..21efb196a 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -7,19 +7,20 @@ use std::sync::Arc;
7use arrayvec::ArrayVec; 7use arrayvec::ArrayVec;
8use hir_def::{ 8use hir_def::{
9 lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AssocItemId, AstItemDef, 9 lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AssocItemId, AstItemDef,
10 FunctionId, HasModule, ImplId, TraitId, 10 FunctionId, HasModule, ImplId, Lookup, TraitId,
11}; 11};
12use hir_expand::name::Name; 12use hir_expand::name::Name;
13use ra_db::CrateId; 13use ra_db::CrateId;
14use ra_prof::profile; 14use ra_prof::profile;
15use rustc_hash::FxHashMap; 15use rustc_hash::FxHashMap;
16 16
17use super::Substs;
17use crate::{ 18use crate::{
18 autoderef, 19 autoderef,
19 db::HirDatabase, 20 db::HirDatabase,
20 primitive::{FloatBitness, Uncertain}, 21 primitive::{FloatBitness, Uncertain},
21 utils::all_super_traits, 22 utils::all_super_traits,
22 Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, 23 Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk,
23}; 24};
24 25
25/// This is used as a key for indexing impls. 26/// This is used as a key for indexing impls.
@@ -176,7 +177,6 @@ pub fn iterate_method_candidates<T>(
176 mode: LookupMode, 177 mode: LookupMode,
177 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>, 178 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
178) -> Option<T> { 179) -> Option<T> {
179 let krate = resolver.krate()?;
180 match mode { 180 match mode {
181 LookupMode::MethodCall => { 181 LookupMode::MethodCall => {
182 // For method calls, rust first does any number of autoderef, and then one 182 // For method calls, rust first does any number of autoderef, and then one
@@ -189,57 +189,159 @@ pub fn iterate_method_candidates<T>(
189 // rustc does an autoderef and then autoref again). 189 // rustc does an autoderef and then autoref again).
190 let environment = TraitEnvironment::lower(db, resolver); 190 let environment = TraitEnvironment::lower(db, resolver);
191 let ty = InEnvironment { value: ty.clone(), environment }; 191 let ty = InEnvironment { value: ty.clone(), environment };
192 for derefed_ty in autoderef::autoderef(db, resolver.krate(), ty) { 192 let krate = resolver.krate()?;
193 if let Some(result) = 193
194 iterate_inherent_methods(&derefed_ty, db, name, mode, krate, &mut callback) 194 // We have to be careful about the order we're looking at candidates
195 { 195 // in here. Consider the case where we're resolving `x.clone()`
196 return Some(result); 196 // where `x: &Vec<_>`. This resolves to the clone method with self
197 } 197 // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where
198 if let Some(result) = iterate_trait_method_candidates( 198 // the receiver type exactly matches before cases where we have to
199 &derefed_ty, 199 // do autoref. But in the autoderef steps, the `&_` self type comes
200 // up *before* the `Vec<_>` self type.
201 //
202 // On the other hand, we don't want to just pick any by-value method
203 // before any by-autoref method; it's just that we need to consider
204 // the methods by autoderef order of *receiver types*, not *self
205 // types*.
206
207 let deref_chain: Vec<_> = autoderef::autoderef(db, Some(krate), ty.clone()).collect();
208 for i in 0..deref_chain.len() {
209 if let Some(result) = iterate_method_candidates_with_autoref(
210 &deref_chain[i..],
200 db, 211 db,
201 resolver, 212 resolver,
202 name, 213 name,
203 mode,
204 &mut callback, 214 &mut callback,
205 ) { 215 ) {
206 return Some(result); 216 return Some(result);
207 } 217 }
208 } 218 }
219 None
209 } 220 }
210 LookupMode::Path => { 221 LookupMode::Path => {
211 // No autoderef for path lookups 222 // No autoderef for path lookups
212 if let Some(result) = 223 iterate_method_candidates_for_self_ty(&ty, db, resolver, name, &mut callback)
213 iterate_inherent_methods(&ty, db, name, mode, krate.into(), &mut callback) 224 }
214 { 225 }
215 return Some(result); 226}
216 } 227
217 if let Some(result) = 228fn iterate_method_candidates_with_autoref<T>(
218 iterate_trait_method_candidates(&ty, db, resolver, name, mode, &mut callback) 229 deref_chain: &[Canonical<Ty>],
219 { 230 db: &impl HirDatabase,
220 return Some(result); 231 resolver: &Resolver,
221 } 232 name: Option<&Name>,
233 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
234) -> Option<T> {
235 if let Some(result) = iterate_method_candidates_by_receiver(
236 &deref_chain[0],
237 &deref_chain[1..],
238 db,
239 resolver,
240 name,
241 &mut callback,
242 ) {
243 return Some(result);
244 }
245 let refed = Canonical {
246 num_vars: deref_chain[0].num_vars,
247 value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()),
248 };
249 if let Some(result) = iterate_method_candidates_by_receiver(
250 &refed,
251 deref_chain,
252 db,
253 resolver,
254 name,
255 &mut callback,
256 ) {
257 return Some(result);
258 }
259 let ref_muted = Canonical {
260 num_vars: deref_chain[0].num_vars,
261 value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()),
262 };
263 if let Some(result) = iterate_method_candidates_by_receiver(
264 &ref_muted,
265 deref_chain,
266 db,
267 resolver,
268 name,
269 &mut callback,
270 ) {
271 return Some(result);
272 }
273 None
274}
275
276fn iterate_method_candidates_by_receiver<T>(
277 receiver_ty: &Canonical<Ty>,
278 rest_of_deref_chain: &[Canonical<Ty>],
279 db: &impl HirDatabase,
280 resolver: &Resolver,
281 name: Option<&Name>,
282 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
283) -> Option<T> {
284 // We're looking for methods with *receiver* type receiver_ty. These could
285 // be found in any of the derefs of receiver_ty, so we have to go through
286 // that.
287 let krate = resolver.krate()?;
288 for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
289 if let Some(result) =
290 iterate_inherent_methods(self_ty, db, name, Some(receiver_ty), krate, &mut callback)
291 {
292 return Some(result);
293 }
294 }
295 for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
296 if let Some(result) = iterate_trait_method_candidates(
297 self_ty,
298 db,
299 resolver,
300 name,
301 Some(receiver_ty),
302 &mut callback,
303 ) {
304 return Some(result);
222 } 305 }
223 } 306 }
224 None 307 None
225} 308}
226 309
310fn iterate_method_candidates_for_self_ty<T>(
311 self_ty: &Canonical<Ty>,
312 db: &impl HirDatabase,
313 resolver: &Resolver,
314 name: Option<&Name>,
315 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
316) -> Option<T> {
317 let krate = resolver.krate()?;
318 if let Some(result) = iterate_inherent_methods(self_ty, db, name, None, krate, &mut callback) {
319 return Some(result);
320 }
321 if let Some(result) =
322 iterate_trait_method_candidates(self_ty, db, resolver, name, None, &mut callback)
323 {
324 return Some(result);
325 }
326 None
327}
328
227fn iterate_trait_method_candidates<T>( 329fn iterate_trait_method_candidates<T>(
228 ty: &Canonical<Ty>, 330 self_ty: &Canonical<Ty>,
229 db: &impl HirDatabase, 331 db: &impl HirDatabase,
230 resolver: &Resolver, 332 resolver: &Resolver,
231 name: Option<&Name>, 333 name: Option<&Name>,
232 mode: LookupMode, 334 receiver_ty: Option<&Canonical<Ty>>,
233 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>, 335 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
234) -> Option<T> { 336) -> Option<T> {
235 let krate = resolver.krate()?; 337 let krate = resolver.krate()?;
236 // FIXME: maybe put the trait_env behind a query (need to figure out good input parameters for that) 338 // FIXME: maybe put the trait_env behind a query (need to figure out good input parameters for that)
237 let env = TraitEnvironment::lower(db, resolver); 339 let env = TraitEnvironment::lower(db, resolver);
238 // if ty is `impl Trait` or `dyn Trait`, the trait doesn't need to be in scope 340 // if ty is `impl Trait` or `dyn Trait`, the trait doesn't need to be in scope
239 let inherent_trait = ty.value.inherent_trait().into_iter(); 341 let inherent_trait = self_ty.value.inherent_trait().into_iter();
240 // if we have `T: Trait` in the param env, the trait doesn't need to be in scope 342 // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
241 let traits_from_env = env 343 let traits_from_env = env
242 .trait_predicates_for_self_ty(&ty.value) 344 .trait_predicates_for_self_ty(&self_ty.value)
243 .map(|tr| tr.trait_) 345 .map(|tr| tr.trait_)
244 .flat_map(|t| all_super_traits(db, t)); 346 .flat_map(|t| all_super_traits(db, t));
245 let traits = 347 let traits =
@@ -252,17 +354,17 @@ fn iterate_trait_method_candidates<T>(
252 // iteration 354 // iteration
253 let mut known_implemented = false; 355 let mut known_implemented = false;
254 for (_name, item) in data.items.iter() { 356 for (_name, item) in data.items.iter() {
255 if !is_valid_candidate(db, name, mode, (*item).into()) { 357 if !is_valid_candidate(db, name, receiver_ty, (*item).into(), self_ty) {
256 continue; 358 continue;
257 } 359 }
258 if !known_implemented { 360 if !known_implemented {
259 let goal = generic_implements_goal(db, env.clone(), t, ty.clone()); 361 let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone());
260 if db.trait_solve(krate.into(), goal).is_none() { 362 if db.trait_solve(krate.into(), goal).is_none() {
261 continue 'traits; 363 continue 'traits;
262 } 364 }
263 } 365 }
264 known_implemented = true; 366 known_implemented = true;
265 if let Some(result) = callback(&ty.value, (*item).into()) { 367 if let Some(result) = callback(&self_ty.value, (*item).into()) {
266 return Some(result); 368 return Some(result);
267 } 369 }
268 } 370 }
@@ -271,22 +373,22 @@ fn iterate_trait_method_candidates<T>(
271} 373}
272 374
273fn iterate_inherent_methods<T>( 375fn iterate_inherent_methods<T>(
274 ty: &Canonical<Ty>, 376 self_ty: &Canonical<Ty>,
275 db: &impl HirDatabase, 377 db: &impl HirDatabase,
276 name: Option<&Name>, 378 name: Option<&Name>,
277 mode: LookupMode, 379 receiver_ty: Option<&Canonical<Ty>>,
278 krate: CrateId, 380 krate: CrateId,
279 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>, 381 mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
280) -> Option<T> { 382) -> Option<T> {
281 for krate in ty.value.def_crates(db, krate)? { 383 for krate in self_ty.value.def_crates(db, krate)? {
282 let impls = db.impls_in_crate(krate); 384 let impls = db.impls_in_crate(krate);
283 385
284 for impl_block in impls.lookup_impl_blocks(&ty.value) { 386 for impl_block in impls.lookup_impl_blocks(&self_ty.value) {
285 for &item in db.impl_data(impl_block).items.iter() { 387 for &item in db.impl_data(impl_block).items.iter() {
286 if !is_valid_candidate(db, name, mode, item) { 388 if !is_valid_candidate(db, name, receiver_ty, item, self_ty) {
287 continue; 389 continue;
288 } 390 }
289 if let Some(result) = callback(&ty.value, item.into()) { 391 if let Some(result) = callback(&self_ty.value, item) {
290 return Some(result); 392 return Some(result);
291 } 393 }
292 } 394 }
@@ -298,23 +400,68 @@ fn iterate_inherent_methods<T>(
298fn is_valid_candidate( 400fn is_valid_candidate(
299 db: &impl HirDatabase, 401 db: &impl HirDatabase,
300 name: Option<&Name>, 402 name: Option<&Name>,
301 mode: LookupMode, 403 receiver_ty: Option<&Canonical<Ty>>,
302 item: AssocItemId, 404 item: AssocItemId,
405 self_ty: &Canonical<Ty>,
303) -> bool { 406) -> bool {
304 match item { 407 match item {
305 AssocItemId::FunctionId(m) => { 408 AssocItemId::FunctionId(m) => {
306 let data = db.function_data(m); 409 let data = db.function_data(m);
307 name.map_or(true, |name| &data.name == name) 410 if let Some(name) = name {
308 && (data.has_self_param || mode == LookupMode::Path) 411 if &data.name != name {
412 return false;
413 }
414 }
415 if let Some(receiver_ty) = receiver_ty {
416 if !data.has_self_param {
417 return false;
418 }
419 let transformed_receiver_ty = match transform_receiver_ty(db, m, self_ty) {
420 Some(ty) => ty,
421 None => return false,
422 };
423 if transformed_receiver_ty != receiver_ty.value {
424 return false;
425 }
426 }
427 true
309 } 428 }
310 AssocItemId::ConstId(c) => { 429 AssocItemId::ConstId(c) => {
311 let data = db.const_data(c); 430 let data = db.const_data(c);
312 name.map_or(true, |name| data.name.as_ref() == Some(name)) && (mode == LookupMode::Path) 431 name.map_or(true, |name| data.name.as_ref() == Some(name)) && receiver_ty.is_none()
313 } 432 }
314 _ => false, 433 _ => false,
315 } 434 }
316} 435}
317 436
437pub(crate) fn inherent_impl_substs(
438 db: &impl HirDatabase,
439 impl_id: ImplId,
440 self_ty: &Ty,
441) -> Option<Substs> {
442 let vars = Substs::build_for_def(db, impl_id).fill_with_bound_vars(0).build();
443 let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars);
444 let self_ty_with_vars = Canonical { num_vars: vars.len(), value: &self_ty_with_vars };
445 super::infer::unify(self_ty_with_vars, self_ty)
446}
447
448fn transform_receiver_ty(
449 db: &impl HirDatabase,
450 function_id: FunctionId,
451 self_ty: &Canonical<Ty>,
452) -> Option<Ty> {
453 let substs = match function_id.lookup(db).container {
454 hir_def::ContainerId::TraitId(_) => Substs::build_for_def(db, function_id)
455 .push(self_ty.value.clone())
456 .fill_with_unknown()
457 .build(),
458 hir_def::ContainerId::ImplId(impl_id) => inherent_impl_substs(db, impl_id, &self_ty.value)?,
459 hir_def::ContainerId::ModuleId(_) => unreachable!(),
460 };
461 let sig = db.callable_item_signature(function_id.into());
462 Some(sig.params()[0].clone().subst(&substs))
463}
464
318pub fn implements_trait( 465pub fn implements_trait(
319 ty: &Canonical<Ty>, 466 ty: &Canonical<Ty>,
320 db: &impl HirDatabase, 467 db: &impl HirDatabase,
diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs
index a3cc5cf95..d5b8d10e2 100644
--- a/crates/ra_hir_ty/src/tests.rs
+++ b/crates/ra_hir_ty/src/tests.rs
@@ -3433,7 +3433,20 @@ pub fn baz() -> usize { 31usize }
3433 assert_eq!("(i32, usize)", type_at_pos(&db, pos)); 3433 assert_eq!("(i32, usize)", type_at_pos(&db, pos));
3434} 3434}
3435 3435
3436#[ignore] 3436#[test]
3437fn method_resolution_unify_impl_self_type() {
3438 let t = type_at(
3439 r#"
3440//- /main.rs
3441struct S<T>;
3442impl S<u32> { fn foo(&self) -> u8 {} }
3443impl S<i32> { fn foo(&self) -> i8 {} }
3444fn test() { (S::<u32>.foo(), S::<i32>.foo())<|>; }
3445"#,
3446 );
3447 assert_eq!(t, "(u8, i8)");
3448}
3449
3437#[test] 3450#[test]
3438fn method_resolution_trait_before_autoref() { 3451fn method_resolution_trait_before_autoref() {
3439 let t = type_at( 3452 let t = type_at(
@@ -3449,7 +3462,6 @@ fn test() { S.foo()<|>; }
3449 assert_eq!(t, "u128"); 3462 assert_eq!(t, "u128");
3450} 3463}
3451 3464
3452#[ignore]
3453#[test] 3465#[test]
3454fn method_resolution_by_value_before_autoref() { 3466fn method_resolution_by_value_before_autoref() {
3455 let t = type_at( 3467 let t = type_at(
@@ -3496,6 +3508,21 @@ fn test() { S.foo()<|>; }
3496} 3508}
3497 3509
3498#[test] 3510#[test]
3511fn method_resolution_impl_ref_before_trait() {
3512 let t = type_at(
3513 r#"
3514//- /main.rs
3515trait Trait { fn foo(self) -> u128; }
3516struct S;
3517impl S { fn foo(&self) -> i8 { 0 } }
3518impl Trait for &S { fn foo(self) -> u128 { 0 } }
3519fn test() { S.foo()<|>; }
3520"#,
3521 );
3522 assert_eq!(t, "i8");
3523}
3524
3525#[test]
3499fn method_resolution_trait_autoderef() { 3526fn method_resolution_trait_autoderef() {
3500 let t = type_at( 3527 let t = type_at(
3501 r#" 3528 r#"