diff options
author | bors[bot] <26634292+bors[bot]@users.noreply.github.com> | 2019-12-03 12:58:44 +0000 |
---|---|---|
committer | GitHub <[email protected]> | 2019-12-03 12:58:44 +0000 |
commit | c5be0cedf3a9d56c17d988ce6354599b85198fb8 (patch) | |
tree | 70e3d0e36efa9568fb7f510f44bd65ff675122a2 /crates/ra_hir_ty/src | |
parent | 3376c08052a563a5d2db487c458972378edebf44 (diff) | |
parent | 18f25acb89304b2eb0a822b7b49b5e66a439ada7 (diff) |
Merge #2463
2463: More correct method resolution r=flodiebold a=flodiebold
This should fix the order in which candidates for method resolution are considered, i.e. `(&Foo).clone()` should now be of type `Foo` instead of `&Foo`. It also checks for inherent candidates that the self type unifies properly with the self type in the impl (i.e. `impl Foo<u32>` methods will only be considered for `Foo<u32>`).
To be able to get the correct receiver type to check in the method resolution, I needed the unification logic, so I extracted it to the `unify.rs` module.
Should fix #2435.
Co-authored-by: Florian Diebold <[email protected]>
Diffstat (limited to 'crates/ra_hir_ty/src')
-rw-r--r-- | crates/ra_hir_ty/src/infer.rs | 259 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/coerce.rs | 10 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/expr.rs | 30 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/pat.rs | 4 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/path.rs | 42 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/infer/unify.rs | 276 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/method_resolution.rs | 225 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/tests.rs | 31 |
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; | |||
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,16 +32,17 @@ 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, TypeWalk, |
42 | TypeWalk, Uncertain, | 40 | Uncertain, |
43 | }; | 41 | }; |
44 | use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; | 42 | use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; |
45 | 43 | ||
44 | pub(crate) use unify::unify; | ||
45 | |||
46 | macro_rules! ty_app { | 46 | macro_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)] | ||
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 | 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)] |
681 | pub enum InferTy { | 472 | pub 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 | ||
688 | impl InferTy { | 479 | impl 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 | ||
11 | use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; | 11 | use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; |
12 | 12 | ||
13 | use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue}; | 13 | use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext}; |
14 | 14 | ||
15 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | 15 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { |
16 | /// Unify two types, but may coerce the first one to the second one | 16 | /// Unify two types, but may coerce the first one to the second one |
@@ -85,8 +85,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
85 | match (&from_ty, to_ty) { | 85 | match (&from_ty, to_ty) { |
86 | // Never type will make type variable to fallback to Never Type instead of Unknown. | 86 | // Never type will make type variable to fallback to Never Type instead of Unknown. |
87 | (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => { | 87 | (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => { |
88 | let var = self.new_maybe_never_type_var(); | 88 | let var = self.table.new_maybe_never_type_var(); |
89 | self.var_unification_table.union_value(*tv, TypeVarValue::Known(var)); | 89 | self.table.var_unification_table.union_value(*tv, TypeVarValue::Known(var)); |
90 | return true; | 90 | return true; |
91 | } | 91 | } |
92 | (ty_app!(TypeCtor::Never), _) => return true, | 92 | (ty_app!(TypeCtor::Never), _) => return true, |
@@ -94,7 +94,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
94 | // Trivial cases, this should go after `never` check to | 94 | // Trivial cases, this should go after `never` check to |
95 | // avoid infer result type to be never | 95 | // avoid infer result type to be never |
96 | _ => { | 96 | _ => { |
97 | if self.unify_inner_trivial(&from_ty, &to_ty) { | 97 | if self.table.unify_inner_trivial(&from_ty, &to_ty) { |
98 | return true; | 98 | return true; |
99 | } | 99 | } |
100 | } | 100 | } |
@@ -330,7 +330,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
330 | // Stop when constructor matches. | 330 | // Stop when constructor matches. |
331 | (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => { | 331 | (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => { |
332 | // It will not recurse to `coerce`. | 332 | // It will not recurse to `coerce`. |
333 | return self.unify_substs(st1, st2, 0); | 333 | return self.table.unify_substs(st1, st2, 0); |
334 | } | 334 | } |
335 | _ => {} | 335 | _ => {} |
336 | } | 336 | } |
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs index 4014f4732..1e78f6efd 100644 --- a/crates/ra_hir_ty/src/infer/expr.rs +++ b/crates/ra_hir_ty/src/infer/expr.rs | |||
@@ -32,7 +32,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
32 | TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() }, | 32 | TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() }, |
33 | ); | 33 | ); |
34 | } | 34 | } |
35 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 35 | let ty = self.resolve_ty_as_possible(ty); |
36 | ty | 36 | ty |
37 | } | 37 | } |
38 | 38 | ||
@@ -53,7 +53,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
53 | expected.ty.clone() | 53 | expected.ty.clone() |
54 | }; | 54 | }; |
55 | 55 | ||
56 | self.resolve_ty_as_possible(&mut vec![], ty) | 56 | self.resolve_ty_as_possible(ty) |
57 | } | 57 | } |
58 | 58 | ||
59 | fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { | 59 | fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { |
@@ -94,7 +94,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
94 | 94 | ||
95 | let pat_ty = match self.resolve_into_iter_item() { | 95 | let pat_ty = match self.resolve_into_iter_item() { |
96 | Some(into_iter_item_alias) => { | 96 | Some(into_iter_item_alias) => { |
97 | let pat_ty = self.new_type_var(); | 97 | let pat_ty = self.table.new_type_var(); |
98 | let projection = ProjectionPredicate { | 98 | let projection = ProjectionPredicate { |
99 | ty: pat_ty.clone(), | 99 | ty: pat_ty.clone(), |
100 | projection_ty: ProjectionTy { | 100 | projection_ty: ProjectionTy { |
@@ -103,7 +103,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
103 | }, | 103 | }, |
104 | }; | 104 | }; |
105 | self.obligations.push(Obligation::Projection(projection)); | 105 | self.obligations.push(Obligation::Projection(projection)); |
106 | self.resolve_ty_as_possible(&mut vec![], pat_ty) | 106 | self.resolve_ty_as_possible(pat_ty) |
107 | } | 107 | } |
108 | None => Ty::Unknown, | 108 | None => Ty::Unknown, |
109 | }; | 109 | }; |
@@ -128,7 +128,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
128 | } | 128 | } |
129 | 129 | ||
130 | // add return type | 130 | // add return type |
131 | let ret_ty = self.new_type_var(); | 131 | let ret_ty = self.table.new_type_var(); |
132 | sig_tys.push(ret_ty.clone()); | 132 | sig_tys.push(ret_ty.clone()); |
133 | let sig_ty = Ty::apply( | 133 | let sig_ty = Ty::apply( |
134 | TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 }, | 134 | TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 }, |
@@ -167,7 +167,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
167 | Expr::Match { expr, arms } => { | 167 | Expr::Match { expr, arms } => { |
168 | let input_ty = self.infer_expr(*expr, &Expectation::none()); | 168 | let input_ty = self.infer_expr(*expr, &Expectation::none()); |
169 | 169 | ||
170 | let mut result_ty = self.new_maybe_never_type_var(); | 170 | let mut result_ty = self.table.new_maybe_never_type_var(); |
171 | 171 | ||
172 | for arm in arms { | 172 | for arm in arms { |
173 | for &pat in &arm.pats { | 173 | for &pat in &arm.pats { |
@@ -283,7 +283,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
283 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); | 283 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); |
284 | let ty = match self.resolve_future_future_output() { | 284 | let ty = match self.resolve_future_future_output() { |
285 | Some(future_future_output_alias) => { | 285 | Some(future_future_output_alias) => { |
286 | let ty = self.new_type_var(); | 286 | let ty = self.table.new_type_var(); |
287 | let projection = ProjectionPredicate { | 287 | let projection = ProjectionPredicate { |
288 | ty: ty.clone(), | 288 | ty: ty.clone(), |
289 | projection_ty: ProjectionTy { | 289 | projection_ty: ProjectionTy { |
@@ -292,7 +292,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
292 | }, | 292 | }, |
293 | }; | 293 | }; |
294 | self.obligations.push(Obligation::Projection(projection)); | 294 | self.obligations.push(Obligation::Projection(projection)); |
295 | self.resolve_ty_as_possible(&mut vec![], ty) | 295 | self.resolve_ty_as_possible(ty) |
296 | } | 296 | } |
297 | None => Ty::Unknown, | 297 | None => Ty::Unknown, |
298 | }; | 298 | }; |
@@ -302,7 +302,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
302 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); | 302 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); |
303 | let ty = match self.resolve_ops_try_ok() { | 303 | let ty = match self.resolve_ops_try_ok() { |
304 | Some(ops_try_ok_alias) => { | 304 | Some(ops_try_ok_alias) => { |
305 | let ty = self.new_type_var(); | 305 | let ty = self.table.new_type_var(); |
306 | let projection = ProjectionPredicate { | 306 | let projection = ProjectionPredicate { |
307 | ty: ty.clone(), | 307 | ty: ty.clone(), |
308 | projection_ty: ProjectionTy { | 308 | projection_ty: ProjectionTy { |
@@ -311,7 +311,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
311 | }, | 311 | }, |
312 | }; | 312 | }; |
313 | self.obligations.push(Obligation::Projection(projection)); | 313 | self.obligations.push(Obligation::Projection(projection)); |
314 | self.resolve_ty_as_possible(&mut vec![], ty) | 314 | self.resolve_ty_as_possible(ty) |
315 | } | 315 | } |
316 | None => Ty::Unknown, | 316 | None => Ty::Unknown, |
317 | }; | 317 | }; |
@@ -465,10 +465,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
465 | ty_app!(TypeCtor::Tuple { .. }, st) => st | 465 | ty_app!(TypeCtor::Tuple { .. }, st) => st |
466 | .iter() | 466 | .iter() |
467 | .cloned() | 467 | .cloned() |
468 | .chain(repeat_with(|| self.new_type_var())) | 468 | .chain(repeat_with(|| self.table.new_type_var())) |
469 | .take(exprs.len()) | 469 | .take(exprs.len()) |
470 | .collect::<Vec<_>>(), | 470 | .collect::<Vec<_>>(), |
471 | _ => (0..exprs.len()).map(|_| self.new_type_var()).collect(), | 471 | _ => (0..exprs.len()).map(|_| self.table.new_type_var()).collect(), |
472 | }; | 472 | }; |
473 | 473 | ||
474 | for (expr, ty) in exprs.iter().zip(tys.iter_mut()) { | 474 | for (expr, ty) in exprs.iter().zip(tys.iter_mut()) { |
@@ -482,7 +482,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
482 | ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => { | 482 | ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => { |
483 | st.as_single().clone() | 483 | st.as_single().clone() |
484 | } | 484 | } |
485 | _ => self.new_type_var(), | 485 | _ => self.table.new_type_var(), |
486 | }; | 486 | }; |
487 | 487 | ||
488 | match array { | 488 | match array { |
@@ -524,7 +524,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
524 | }; | 524 | }; |
525 | // use a new type variable if we got Ty::Unknown here | 525 | // use a new type variable if we got Ty::Unknown here |
526 | let ty = self.insert_type_vars_shallow(ty); | 526 | let ty = self.insert_type_vars_shallow(ty); |
527 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 527 | let ty = self.resolve_ty_as_possible(ty); |
528 | self.write_expr_ty(tgt_expr, ty.clone()); | 528 | self.write_expr_ty(tgt_expr, ty.clone()); |
529 | ty | 529 | ty |
530 | } | 530 | } |
@@ -553,7 +553,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
553 | } | 553 | } |
554 | } | 554 | } |
555 | 555 | ||
556 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 556 | let ty = self.resolve_ty_as_possible(ty); |
557 | self.infer_pat(*pat, &ty, BindingMode::default()); | 557 | self.infer_pat(*pat, &ty, BindingMode::default()); |
558 | } | 558 | } |
559 | Statement::Expr(expr) => { | 559 | Statement::Expr(expr) => { |
diff --git a/crates/ra_hir_ty/src/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs index 1ebb36239..a14662884 100644 --- a/crates/ra_hir_ty/src/infer/pat.rs +++ b/crates/ra_hir_ty/src/infer/pat.rs | |||
@@ -170,7 +170,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
170 | } | 170 | } |
171 | BindingMode::Move => inner_ty.clone(), | 171 | BindingMode::Move => inner_ty.clone(), |
172 | }; | 172 | }; |
173 | let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty); | 173 | let bound_ty = self.resolve_ty_as_possible(bound_ty); |
174 | self.write_pat_ty(pat, bound_ty); | 174 | self.write_pat_ty(pat, bound_ty); |
175 | return inner_ty; | 175 | return inner_ty; |
176 | } | 176 | } |
@@ -179,7 +179,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
179 | // use a new type variable if we got Ty::Unknown here | 179 | // use a new type variable if we got Ty::Unknown here |
180 | let ty = self.insert_type_vars_shallow(ty); | 180 | let ty = self.insert_type_vars_shallow(ty); |
181 | self.unify(&ty, expected); | 181 | self.unify(&ty, expected); |
182 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | 182 | let ty = self.resolve_ty_as_possible(ty); |
183 | self.write_pat_ty(pat, ty.clone()); | 183 | self.write_pat_ty(pat, ty.clone()); |
184 | ty | 184 | ty |
185 | } | 185 | } |
diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs index bbf146418..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 | ||
3 | use std::borrow::Cow; | ||
4 | |||
5 | use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; | ||
6 | |||
7 | use test_utils::tested_by; | ||
8 | |||
3 | use super::{InferenceContext, Obligation}; | 9 | use super::{InferenceContext, Obligation}; |
4 | use crate::{ | 10 | use crate::{ |
5 | db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate, | 11 | db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate, |
6 | ProjectionTy, Substs, TraitRef, Ty, TypeWalk, | 12 | ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk, |
7 | }; | 13 | }; |
8 | 14 | ||
9 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | 15 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { |
@@ -24,7 +30,7 @@ where | |||
24 | /// A stack of type variables that is used to detect recursive types (which | 30 | /// A stack of type variables that is used to detect recursive types (which |
25 | /// are an error, but we need to protect against them to avoid stack | 31 | /// are an error, but we need to protect against them to avoid stack |
26 | /// overflows). | 32 | /// overflows). |
27 | var_stack: Vec<super::TypeVarId>, | 33 | var_stack: Vec<TypeVarId>, |
28 | } | 34 | } |
29 | 35 | ||
30 | pub(super) struct Canonicalized<T> { | 36 | pub(super) struct Canonicalized<T> { |
@@ -53,14 +59,14 @@ where | |||
53 | return tv.fallback_value(); | 59 | return tv.fallback_value(); |
54 | } | 60 | } |
55 | if let Some(known_ty) = | 61 | if let Some(known_ty) = |
56 | self.ctx.var_unification_table.inlined_probe_value(inner).known() | 62 | self.ctx.table.var_unification_table.inlined_probe_value(inner).known() |
57 | { | 63 | { |
58 | self.var_stack.push(inner); | 64 | self.var_stack.push(inner); |
59 | let result = self.do_canonicalize_ty(known_ty.clone()); | 65 | let result = self.do_canonicalize_ty(known_ty.clone()); |
60 | self.var_stack.pop(); | 66 | self.var_stack.pop(); |
61 | result | 67 | result |
62 | } else { | 68 | } else { |
63 | let root = self.ctx.var_unification_table.find(inner); | 69 | let root = self.ctx.table.var_unification_table.find(inner); |
64 | let free_var = match tv { | 70 | let free_var = match tv { |
65 | InferTy::TypeVar(_) => InferTy::TypeVar(root), | 71 | InferTy::TypeVar(_) => InferTy::TypeVar(root), |
66 | InferTy::IntVar(_) => InferTy::IntVar(root), | 72 | InferTy::IntVar(_) => InferTy::IntVar(root), |
@@ -153,10 +159,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 | |||
170 | pub 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)] | ||
186 | pub(crate) struct InferenceTable { | ||
187 | pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>, | ||
188 | } | ||
189 | |||
190 | impl 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)] | ||
372 | pub struct TypeVarId(pub(super) u32); | ||
373 | |||
374 | impl 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)] | ||
393 | pub enum TypeVarValue { | ||
394 | Known(Ty), | ||
395 | Unknown, | ||
396 | } | ||
397 | |||
398 | impl TypeVarValue { | ||
399 | fn known(&self) -> Option<&Ty> { | ||
400 | match self { | ||
401 | TypeVarValue::Known(ty) => Some(ty), | ||
402 | TypeVarValue::Unknown => None, | ||
403 | } | ||
404 | } | ||
405 | } | ||
406 | |||
407 | impl 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; | |||
7 | use arrayvec::ArrayVec; | 7 | use arrayvec::ArrayVec; |
8 | use hir_def::{ | 8 | use 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 | }; |
12 | use hir_expand::name::Name; | 12 | use hir_expand::name::Name; |
13 | use ra_db::CrateId; | 13 | use ra_db::CrateId; |
14 | use ra_prof::profile; | 14 | use ra_prof::profile; |
15 | use rustc_hash::FxHashMap; | 15 | use rustc_hash::FxHashMap; |
16 | 16 | ||
17 | use super::Substs; | ||
17 | use crate::{ | 18 | use 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) = | 228 | fn 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 | |||
276 | fn 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 | ||
310 | fn 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 | |||
227 | fn iterate_trait_method_candidates<T>( | 329 | fn 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 | ||
273 | fn iterate_inherent_methods<T>( | 375 | fn 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>( | |||
298 | fn is_valid_candidate( | 400 | fn 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 | ||
437 | pub(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 | |||
448 | fn 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 | |||
318 | pub fn implements_trait( | 465 | pub 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] |
3437 | fn method_resolution_unify_impl_self_type() { | ||
3438 | let t = type_at( | ||
3439 | r#" | ||
3440 | //- /main.rs | ||
3441 | struct S<T>; | ||
3442 | impl S<u32> { fn foo(&self) -> u8 {} } | ||
3443 | impl S<i32> { fn foo(&self) -> i8 {} } | ||
3444 | fn test() { (S::<u32>.foo(), S::<i32>.foo())<|>; } | ||
3445 | "#, | ||
3446 | ); | ||
3447 | assert_eq!(t, "(u8, i8)"); | ||
3448 | } | ||
3449 | |||
3437 | #[test] | 3450 | #[test] |
3438 | fn method_resolution_trait_before_autoref() { | 3451 | fn 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] |
3454 | fn method_resolution_by_value_before_autoref() { | 3466 | fn 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] |
3511 | fn method_resolution_impl_ref_before_trait() { | ||
3512 | let t = type_at( | ||
3513 | r#" | ||
3514 | //- /main.rs | ||
3515 | trait Trait { fn foo(self) -> u128; } | ||
3516 | struct S; | ||
3517 | impl S { fn foo(&self) -> i8 { 0 } } | ||
3518 | impl Trait for &S { fn foo(self) -> u128 { 0 } } | ||
3519 | fn test() { S.foo()<|>; } | ||
3520 | "#, | ||
3521 | ); | ||
3522 | assert_eq!(t, "i8"); | ||
3523 | } | ||
3524 | |||
3525 | #[test] | ||
3499 | fn method_resolution_trait_autoderef() { | 3526 | fn method_resolution_trait_autoderef() { |
3500 | let t = type_at( | 3527 | let t = type_at( |
3501 | r#" | 3528 | r#" |