diff options
author | Florian Diebold <[email protected]> | 2018-12-26 16:00:42 +0000 |
---|---|---|
committer | Florian Diebold <[email protected]> | 2018-12-29 11:04:34 +0000 |
commit | cfa1de72ebb7060a82dbf7a67432047d9ea2288a (patch) | |
tree | a679ed837f309ee523590b5777b919604e588b4b /crates/ra_hir/src/ty.rs | |
parent | f3f073804cf768c0b219d89081a26bedfde8ffed (diff) |
Implement type variables
This will really become necessary when we implement generics, but even now, it
allows us to reason 'backwards' to infer types of expressions that we didn't
understand for some reason.
We use ena, the union-find implementation extracted from rustc, to keep track of
type variables.
Diffstat (limited to 'crates/ra_hir/src/ty.rs')
-rw-r--r-- | crates/ra_hir/src/ty.rs | 447 |
1 files changed, 336 insertions, 111 deletions
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs index 38720b7b5..0592e4a63 100644 --- a/crates/ra_hir/src/ty.rs +++ b/crates/ra_hir/src/ty.rs | |||
@@ -3,10 +3,11 @@ mod primitive; | |||
3 | mod tests; | 3 | mod tests; |
4 | 4 | ||
5 | use std::sync::Arc; | 5 | use std::sync::Arc; |
6 | use std::fmt; | 6 | use std::{fmt, mem}; |
7 | 7 | ||
8 | use log; | 8 | use log; |
9 | use rustc_hash::{FxHashMap}; | 9 | use rustc_hash::FxHashMap; |
10 | use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError}; | ||
10 | 11 | ||
11 | use ra_db::{LocalSyntaxPtr, Cancelable}; | 12 | use ra_db::{LocalSyntaxPtr, Cancelable}; |
12 | use ra_syntax::{ | 13 | use ra_syntax::{ |
@@ -17,10 +18,89 @@ use ra_syntax::{ | |||
17 | use crate::{ | 18 | use crate::{ |
18 | Def, DefId, FnScopes, Module, Function, Struct, Enum, Path, Name, AsName, | 19 | Def, DefId, FnScopes, Module, Function, Struct, Enum, Path, Name, AsName, |
19 | db::HirDatabase, | 20 | db::HirDatabase, |
20 | adt::VariantData, | ||
21 | type_ref::{TypeRef, Mutability}, | 21 | type_ref::{TypeRef, Mutability}, |
22 | }; | 22 | }; |
23 | 23 | ||
24 | #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] | ||
25 | pub struct TypeVarId(u32); | ||
26 | |||
27 | impl UnifyKey for TypeVarId { | ||
28 | type Value = TypeVarValue; | ||
29 | |||
30 | fn index(&self) -> u32 { | ||
31 | self.0 | ||
32 | } | ||
33 | |||
34 | fn from_index(i: u32) -> Self { | ||
35 | TypeVarId(i) | ||
36 | } | ||
37 | |||
38 | fn tag() -> &'static str { | ||
39 | "TypeVarId" | ||
40 | } | ||
41 | } | ||
42 | |||
43 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
44 | pub enum TypeVarValue { | ||
45 | Known(Ty), | ||
46 | Unknown, | ||
47 | } | ||
48 | |||
49 | impl TypeVarValue { | ||
50 | pub fn known(&self) -> Option<&Ty> { | ||
51 | match self { | ||
52 | TypeVarValue::Known(ty) => Some(ty), | ||
53 | TypeVarValue::Unknown => None, | ||
54 | } | ||
55 | } | ||
56 | } | ||
57 | |||
58 | impl UnifyValue for TypeVarValue { | ||
59 | type Error = NoError; | ||
60 | |||
61 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { | ||
62 | match (value1, value2) { | ||
63 | // We should never equate two type variables, both of which have | ||
64 | // known types. Instead, we recursively equate those types. | ||
65 | (TypeVarValue::Known(..), TypeVarValue::Known(..)) => { | ||
66 | panic!("equating two type variables, both of which have known types") | ||
67 | } | ||
68 | |||
69 | // If one side is known, prefer that one. | ||
70 | (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), | ||
71 | (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), | ||
72 | |||
73 | (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), | ||
74 | } | ||
75 | } | ||
76 | } | ||
77 | |||
78 | #[derive(Clone, PartialEq, Eq, Hash, Debug)] | ||
79 | pub enum InferTy { | ||
80 | TypeVar(TypeVarId), | ||
81 | // later we'll have IntVar and FloatVar as well | ||
82 | } | ||
83 | |||
84 | /// When inferring an expression, we propagate downward whatever type hint we | ||
85 | /// are able in the form of an `Expectation`. | ||
86 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
87 | struct Expectation { | ||
88 | ty: Ty, | ||
89 | // TODO: In some cases, we need to be aware whether the expectation is that | ||
90 | // the type match exactly what we passed, or whether it just needs to be | ||
91 | // coercible to the expected type. See Expectation::rvalue_hint in rustc. | ||
92 | } | ||
93 | |||
94 | impl Expectation { | ||
95 | fn has_type(ty: Ty) -> Self { | ||
96 | Expectation { ty } | ||
97 | } | ||
98 | |||
99 | fn none() -> Self { | ||
100 | Expectation { ty: Ty::Unknown } | ||
101 | } | ||
102 | } | ||
103 | |||
24 | #[derive(Clone, PartialEq, Eq, Hash, Debug)] | 104 | #[derive(Clone, PartialEq, Eq, Hash, Debug)] |
25 | pub enum Ty { | 105 | pub enum Ty { |
26 | /// The primitive boolean type. Written as `bool`. | 106 | /// The primitive boolean type. Written as `bool`. |
@@ -75,23 +155,22 @@ pub enum Ty { | |||
75 | 155 | ||
76 | // A trait, defined with `dyn trait`. | 156 | // A trait, defined with `dyn trait`. |
77 | // Dynamic(), | 157 | // Dynamic(), |
78 | /// The anonymous type of a closure. Used to represent the type of | 158 | // The anonymous type of a closure. Used to represent the type of |
79 | /// `|a| a`. | 159 | // `|a| a`. |
80 | // Closure(DefId, ClosureSubsts<'tcx>), | 160 | // Closure(DefId, ClosureSubsts<'tcx>), |
81 | 161 | ||
82 | /// The anonymous type of a generator. Used to represent the type of | 162 | // The anonymous type of a generator. Used to represent the type of |
83 | /// `|a| yield a`. | 163 | // `|a| yield a`. |
84 | // Generator(DefId, GeneratorSubsts<'tcx>, hir::GeneratorMovability), | 164 | // Generator(DefId, GeneratorSubsts<'tcx>, hir::GeneratorMovability), |
85 | 165 | ||
86 | /// A type representin the types stored inside a generator. | 166 | // A type representin the types stored inside a generator. |
87 | /// This should only appear in GeneratorInteriors. | 167 | // This should only appear in GeneratorInteriors. |
88 | // GeneratorWitness(Binder<&'tcx List<Ty<'tcx>>>), | 168 | // GeneratorWitness(Binder<&'tcx List<Ty<'tcx>>>), |
89 | |||
90 | /// The never type `!` | 169 | /// The never type `!` |
91 | Never, | 170 | Never, |
92 | 171 | ||
93 | /// A tuple type. For example, `(i32, bool)`. | 172 | /// A tuple type. For example, `(i32, bool)`. |
94 | Tuple(Vec<Ty>), | 173 | Tuple(Arc<[Ty]>), |
95 | 174 | ||
96 | // The projection of an associated type. For example, | 175 | // The projection of an associated type. For example, |
97 | // `<T as Trait<..>>::N`.pub | 176 | // `<T as Trait<..>>::N`.pub |
@@ -106,14 +185,14 @@ pub enum Ty { | |||
106 | 185 | ||
107 | // A type parameter; for example, `T` in `fn f<T>(x: T) {} | 186 | // A type parameter; for example, `T` in `fn f<T>(x: T) {} |
108 | // Param(ParamTy), | 187 | // Param(ParamTy), |
109 | 188 | /// A type variable used during type checking. Not to be confused with a | |
110 | // A placeholder type - universally quantified higher-ranked type. | 189 | /// type parameter. |
111 | // Placeholder(ty::PlaceholderType), | 190 | Infer(InferTy), |
112 | 191 | ||
113 | // A type variable used during type checking. | 192 | /// A placeholder for a type which could not be computed; this is propagated |
114 | // Infer(InferTy), | 193 | /// to avoid useless error messages. Doubles as a placeholder where type |
115 | /// A placeholder for a type which could not be computed; this is | 194 | /// variables are inserted before type checking, since we want to try to |
116 | /// propagated to avoid useless error messages. | 195 | /// infer a better type here anyway. |
117 | Unknown, | 196 | Unknown, |
118 | } | 197 | } |
119 | 198 | ||
@@ -137,8 +216,8 @@ impl Ty { | |||
137 | let inner_tys = inner | 216 | let inner_tys = inner |
138 | .iter() | 217 | .iter() |
139 | .map(|tr| Ty::from_hir(db, module, tr)) | 218 | .map(|tr| Ty::from_hir(db, module, tr)) |
140 | .collect::<Cancelable<_>>()?; | 219 | .collect::<Cancelable<Vec<_>>>()?; |
141 | Ty::Tuple(inner_tys) | 220 | Ty::Tuple(inner_tys.into()) |
142 | } | 221 | } |
143 | TypeRef::Path(path) => Ty::from_hir_path(db, module, path)?, | 222 | TypeRef::Path(path) => Ty::from_hir_path(db, module, path)?, |
144 | TypeRef::RawPtr(inner, mutability) => { | 223 | TypeRef::RawPtr(inner, mutability) => { |
@@ -154,7 +233,7 @@ impl Ty { | |||
154 | let inner_ty = Ty::from_hir(db, module, inner)?; | 233 | let inner_ty = Ty::from_hir(db, module, inner)?; |
155 | Ty::Ref(Arc::new(inner_ty), *mutability) | 234 | Ty::Ref(Arc::new(inner_ty), *mutability) |
156 | } | 235 | } |
157 | TypeRef::Placeholder => Ty::Unknown, // TODO | 236 | TypeRef::Placeholder => Ty::Unknown, |
158 | TypeRef::Fn(params) => { | 237 | TypeRef::Fn(params) => { |
159 | let mut inner_tys = params | 238 | let mut inner_tys = params |
160 | .iter() | 239 | .iter() |
@@ -217,7 +296,41 @@ impl Ty { | |||
217 | } | 296 | } |
218 | 297 | ||
219 | pub fn unit() -> Self { | 298 | pub fn unit() -> Self { |
220 | Ty::Tuple(Vec::new()) | 299 | Ty::Tuple(Arc::new([])) |
300 | } | ||
301 | |||
302 | fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { | ||
303 | f(self); | ||
304 | match self { | ||
305 | Ty::Slice(t) => Arc::make_mut(t).walk_mut(f), | ||
306 | Ty::RawPtr(t, _) => Arc::make_mut(t).walk_mut(f), | ||
307 | Ty::Ref(t, _) => Arc::make_mut(t).walk_mut(f), | ||
308 | Ty::Tuple(ts) => { | ||
309 | // Without an Arc::make_mut_slice, we can't avoid the clone here: | ||
310 | let mut v: Vec<_> = ts.iter().cloned().collect(); | ||
311 | for t in &mut v { | ||
312 | t.walk_mut(f); | ||
313 | } | ||
314 | *ts = v.into(); | ||
315 | } | ||
316 | Ty::FnPtr(sig) => { | ||
317 | let sig_mut = Arc::make_mut(sig); | ||
318 | for input in &mut sig_mut.input { | ||
319 | input.walk_mut(f); | ||
320 | } | ||
321 | sig_mut.output.walk_mut(f); | ||
322 | } | ||
323 | Ty::Adt { .. } => {} // need to walk type parameters later | ||
324 | _ => {} | ||
325 | } | ||
326 | } | ||
327 | |||
328 | fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Ty { | ||
329 | self.walk_mut(&mut |ty_mut| { | ||
330 | let ty = mem::replace(ty_mut, Ty::Unknown); | ||
331 | *ty_mut = f(ty); | ||
332 | }); | ||
333 | self | ||
221 | } | 334 | } |
222 | } | 335 | } |
223 | 336 | ||
@@ -236,7 +349,7 @@ impl fmt::Display for Ty { | |||
236 | Ty::Never => write!(f, "!"), | 349 | Ty::Never => write!(f, "!"), |
237 | Ty::Tuple(ts) => { | 350 | Ty::Tuple(ts) => { |
238 | write!(f, "(")?; | 351 | write!(f, "(")?; |
239 | for t in ts { | 352 | for t in ts.iter() { |
240 | write!(f, "{},", t)?; | 353 | write!(f, "{},", t)?; |
241 | } | 354 | } |
242 | write!(f, ")") | 355 | write!(f, ")") |
@@ -250,6 +363,7 @@ impl fmt::Display for Ty { | |||
250 | } | 363 | } |
251 | Ty::Adt { name, .. } => write!(f, "{}", name), | 364 | Ty::Adt { name, .. } => write!(f, "{}", name), |
252 | Ty::Unknown => write!(f, "[unknown]"), | 365 | Ty::Unknown => write!(f, "[unknown]"), |
366 | Ty::Infer(..) => write!(f, "_"), | ||
253 | } | 367 | } |
254 | } | 368 | } |
255 | } | 369 | } |
@@ -342,7 +456,7 @@ pub struct InferenceContext<'a, D: HirDatabase> { | |||
342 | db: &'a D, | 456 | db: &'a D, |
343 | scopes: Arc<FnScopes>, | 457 | scopes: Arc<FnScopes>, |
344 | module: Module, | 458 | module: Module, |
345 | // TODO unification tables... | 459 | var_unification_table: InPlaceUnificationTable<TypeVarId>, |
346 | type_of: FxHashMap<LocalSyntaxPtr, Ty>, | 460 | type_of: FxHashMap<LocalSyntaxPtr, Ty>, |
347 | } | 461 | } |
348 | 462 | ||
@@ -350,33 +464,116 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
350 | fn new(db: &'a D, scopes: Arc<FnScopes>, module: Module) -> Self { | 464 | fn new(db: &'a D, scopes: Arc<FnScopes>, module: Module) -> Self { |
351 | InferenceContext { | 465 | InferenceContext { |
352 | type_of: FxHashMap::default(), | 466 | type_of: FxHashMap::default(), |
467 | var_unification_table: InPlaceUnificationTable::new(), | ||
353 | db, | 468 | db, |
354 | scopes, | 469 | scopes, |
355 | module, | 470 | module, |
356 | } | 471 | } |
357 | } | 472 | } |
358 | 473 | ||
474 | fn resolve_all(mut self) -> InferenceResult { | ||
475 | let mut types = mem::replace(&mut self.type_of, FxHashMap::default()); | ||
476 | for ty in types.values_mut() { | ||
477 | let resolved = self.resolve_ty_completely(mem::replace(ty, Ty::Unknown)); | ||
478 | *ty = resolved; | ||
479 | } | ||
480 | InferenceResult { type_of: types } | ||
481 | } | ||
482 | |||
359 | fn write_ty(&mut self, node: SyntaxNodeRef, ty: Ty) { | 483 | fn write_ty(&mut self, node: SyntaxNodeRef, ty: Ty) { |
360 | self.type_of.insert(LocalSyntaxPtr::new(node), ty); | 484 | self.type_of.insert(LocalSyntaxPtr::new(node), ty); |
361 | } | 485 | } |
362 | 486 | ||
363 | fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> Option<Ty> { | 487 | fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { |
364 | if *ty1 == Ty::Unknown { | 488 | match (ty1, ty2) { |
365 | return Some(ty2.clone()); | 489 | (Ty::Unknown, ..) => true, |
366 | } | 490 | (.., Ty::Unknown) => true, |
367 | if *ty2 == Ty::Unknown { | 491 | (Ty::Bool, _) |
368 | return Some(ty1.clone()); | 492 | | (Ty::Str, _) |
493 | | (Ty::Never, _) | ||
494 | | (Ty::Char, _) | ||
495 | | (Ty::Int(..), Ty::Int(..)) | ||
496 | | (Ty::Uint(..), Ty::Uint(..)) | ||
497 | | (Ty::Float(..), Ty::Float(..)) => ty1 == ty2, | ||
498 | ( | ||
499 | Ty::Adt { | ||
500 | def_id: def_id1, .. | ||
501 | }, | ||
502 | Ty::Adt { | ||
503 | def_id: def_id2, .. | ||
504 | }, | ||
505 | ) if def_id1 == def_id2 => true, | ||
506 | (Ty::Slice(t1), Ty::Slice(t2)) => self.unify(t1, t2), | ||
507 | (Ty::RawPtr(t1, m1), Ty::RawPtr(t2, m2)) if m1 == m2 => self.unify(t1, t2), | ||
508 | (Ty::Ref(t1, m1), Ty::Ref(t2, m2)) if m1 == m2 => self.unify(t1, t2), | ||
509 | (Ty::FnPtr(sig1), Ty::FnPtr(sig2)) if sig1 == sig2 => true, | ||
510 | (Ty::Tuple(ts1), Ty::Tuple(ts2)) if ts1.len() == ts2.len() => ts1 | ||
511 | .iter() | ||
512 | .zip(ts2.iter()) | ||
513 | .all(|(t1, t2)| self.unify(t1, t2)), | ||
514 | (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2))) => { | ||
515 | self.var_unification_table.union(*tv1, *tv2); | ||
516 | true | ||
517 | } | ||
518 | (Ty::Infer(InferTy::TypeVar(tv)), other) | (other, Ty::Infer(InferTy::TypeVar(tv))) => { | ||
519 | self.var_unification_table | ||
520 | .union_value(*tv, TypeVarValue::Known(other.clone())); | ||
521 | true | ||
522 | } | ||
523 | _ => false, | ||
369 | } | 524 | } |
370 | if ty1 == ty2 { | 525 | } |
371 | return Some(ty1.clone()); | 526 | |
527 | fn new_type_var(&mut self) -> Ty { | ||
528 | Ty::Infer(InferTy::TypeVar( | ||
529 | self.var_unification_table.new_key(TypeVarValue::Unknown), | ||
530 | )) | ||
531 | } | ||
532 | |||
533 | /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it. | ||
534 | fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { | ||
535 | match ty { | ||
536 | Ty::Unknown => self.new_type_var(), | ||
537 | _ => ty, | ||
372 | } | 538 | } |
373 | // TODO implement actual unification | ||
374 | return None; | ||
375 | } | 539 | } |
376 | 540 | ||
377 | fn unify_with_coercion(&mut self, ty1: &Ty, ty2: &Ty) -> Option<Ty> { | 541 | fn insert_type_vars(&mut self, ty: Ty) -> Ty { |
378 | // TODO implement coercion | 542 | ty.fold(&mut |ty| self.insert_type_vars_shallow(ty)) |
379 | self.unify(ty1, ty2) | 543 | } |
544 | |||
545 | /// Resolves the type as far as currently possible, replacing type variables | ||
546 | /// by their known types. All types returned by the infer_* functions should | ||
547 | /// be resolved as far as possible, i.e. contain no type variables with | ||
548 | /// known type. | ||
549 | fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { | ||
550 | ty.fold(&mut |ty| match ty { | ||
551 | Ty::Infer(InferTy::TypeVar(tv)) => { | ||
552 | if let Some(known_ty) = self.var_unification_table.probe_value(tv).known() { | ||
553 | // known_ty may contain other variables that are known by now | ||
554 | self.resolve_ty_as_possible(known_ty.clone()) | ||
555 | } else { | ||
556 | Ty::Infer(InferTy::TypeVar(tv)) | ||
557 | } | ||
558 | } | ||
559 | _ => ty, | ||
560 | }) | ||
561 | } | ||
562 | |||
563 | /// Resolves the type completely; type variables without known type are | ||
564 | /// replaced by Ty::Unknown. | ||
565 | fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { | ||
566 | ty.fold(&mut |ty| match ty { | ||
567 | Ty::Infer(InferTy::TypeVar(tv)) => { | ||
568 | if let Some(known_ty) = self.var_unification_table.probe_value(tv).known() { | ||
569 | // known_ty may contain other variables that are known by now | ||
570 | self.resolve_ty_completely(known_ty.clone()) | ||
571 | } else { | ||
572 | Ty::Unknown | ||
573 | } | ||
574 | } | ||
575 | _ => ty, | ||
576 | }) | ||
380 | } | 577 | } |
381 | 578 | ||
382 | fn infer_path_expr(&mut self, expr: ast::PathExpr) -> Cancelable<Option<Ty>> { | 579 | fn infer_path_expr(&mut self, expr: ast::PathExpr) -> Cancelable<Option<Ty>> { |
@@ -387,21 +584,19 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
387 | let name = ctry!(ast_path.segment().and_then(|s| s.name_ref())); | 584 | let name = ctry!(ast_path.segment().and_then(|s| s.name_ref())); |
388 | if let Some(scope_entry) = self.scopes.resolve_local_name(name) { | 585 | if let Some(scope_entry) = self.scopes.resolve_local_name(name) { |
389 | let ty = ctry!(self.type_of.get(&scope_entry.ptr())); | 586 | let ty = ctry!(self.type_of.get(&scope_entry.ptr())); |
390 | return Ok(Some(ty.clone())); | 587 | let ty = self.resolve_ty_as_possible(ty.clone()); |
588 | return Ok(Some(ty)); | ||
391 | }; | 589 | }; |
392 | }; | 590 | }; |
393 | 591 | ||
394 | // resolve in module | 592 | // resolve in module |
395 | let resolved = ctry!(self.module.resolve_path(self.db, &path)?.take_values()); | 593 | let resolved = ctry!(self.module.resolve_path(self.db, &path)?.take_values()); |
396 | let ty = self.db.type_for_def(resolved)?; | 594 | let ty = self.db.type_for_def(resolved)?; |
397 | // TODO we will need to add type variables for type parameters etc. here | 595 | let ty = self.insert_type_vars(ty); |
398 | Ok(Some(ty)) | 596 | Ok(Some(ty)) |
399 | } | 597 | } |
400 | 598 | ||
401 | fn resolve_variant( | 599 | fn resolve_variant(&self, path: Option<ast::Path>) -> Cancelable<(Ty, Option<DefId>)> { |
402 | &self, | ||
403 | path: Option<ast::Path>, | ||
404 | ) -> Cancelable<(Ty, Option<Arc<VariantData>>)> { | ||
405 | let path = if let Some(path) = path.and_then(Path::from_ast) { | 600 | let path = if let Some(path) = path.and_then(Path::from_ast) { |
406 | path | 601 | path |
407 | } else { | 602 | } else { |
@@ -414,102 +609,116 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
414 | }; | 609 | }; |
415 | Ok(match def_id.resolve(self.db)? { | 610 | Ok(match def_id.resolve(self.db)? { |
416 | Def::Struct(s) => { | 611 | Def::Struct(s) => { |
417 | let struct_data = self.db.struct_data(def_id)?; | ||
418 | let ty = type_for_struct(self.db, s)?; | 612 | let ty = type_for_struct(self.db, s)?; |
419 | (ty, Some(struct_data.variant_data().clone())) | 613 | (ty, Some(def_id)) |
420 | } | 614 | } |
421 | _ => (Ty::Unknown, None), | 615 | _ => (Ty::Unknown, None), |
422 | }) | 616 | }) |
423 | } | 617 | } |
424 | 618 | ||
425 | fn infer_expr_opt(&mut self, expr: Option<ast::Expr>) -> Cancelable<Ty> { | 619 | fn infer_expr_opt( |
620 | &mut self, | ||
621 | expr: Option<ast::Expr>, | ||
622 | expected: &Expectation, | ||
623 | ) -> Cancelable<Ty> { | ||
426 | if let Some(e) = expr { | 624 | if let Some(e) = expr { |
427 | self.infer_expr(e) | 625 | self.infer_expr(e, expected) |
428 | } else { | 626 | } else { |
429 | Ok(Ty::Unknown) | 627 | Ok(Ty::Unknown) |
430 | } | 628 | } |
431 | } | 629 | } |
432 | 630 | ||
433 | fn infer_expr(&mut self, expr: ast::Expr) -> Cancelable<Ty> { | 631 | fn infer_expr(&mut self, expr: ast::Expr, expected: &Expectation) -> Cancelable<Ty> { |
434 | let ty = match expr { | 632 | let ty = match expr { |
435 | ast::Expr::IfExpr(e) => { | 633 | ast::Expr::IfExpr(e) => { |
436 | if let Some(condition) = e.condition() { | 634 | if let Some(condition) = e.condition() { |
437 | // TODO if no pat, this should be bool | 635 | let expected = if condition.pat().is_none() { |
438 | self.infer_expr_opt(condition.expr())?; | 636 | Expectation::has_type(Ty::Bool) |
637 | } else { | ||
638 | Expectation::none() | ||
639 | }; | ||
640 | self.infer_expr_opt(condition.expr(), &expected)?; | ||
439 | // TODO write type for pat | 641 | // TODO write type for pat |
440 | }; | 642 | }; |
441 | let if_ty = self.infer_block_opt(e.then_branch())?; | 643 | let if_ty = self.infer_block_opt(e.then_branch(), expected)?; |
442 | let else_ty = self.infer_block_opt(e.else_branch())?; | 644 | if let Some(else_branch) = e.else_branch() { |
443 | if let Some(ty) = self.unify(&if_ty, &else_ty) { | 645 | self.infer_block(else_branch, expected)?; |
444 | ty | ||
445 | } else { | 646 | } else { |
446 | // TODO report diagnostic | 647 | // no else branch -> unit |
447 | Ty::Unknown | 648 | self.unify(&expected.ty, &Ty::unit()); // actually coerce |
448 | } | 649 | } |
650 | if_ty | ||
449 | } | 651 | } |
450 | ast::Expr::BlockExpr(e) => self.infer_block_opt(e.block())?, | 652 | ast::Expr::BlockExpr(e) => self.infer_block_opt(e.block(), expected)?, |
451 | ast::Expr::LoopExpr(e) => { | 653 | ast::Expr::LoopExpr(e) => { |
452 | self.infer_block_opt(e.loop_body())?; | 654 | self.infer_block_opt(e.loop_body(), &Expectation::has_type(Ty::unit()))?; |
453 | // TODO never, or the type of the break param | 655 | // TODO never, or the type of the break param |
454 | Ty::Unknown | 656 | Ty::Unknown |
455 | } | 657 | } |
456 | ast::Expr::WhileExpr(e) => { | 658 | ast::Expr::WhileExpr(e) => { |
457 | if let Some(condition) = e.condition() { | 659 | if let Some(condition) = e.condition() { |
458 | // TODO if no pat, this should be bool | 660 | let expected = if condition.pat().is_none() { |
459 | self.infer_expr_opt(condition.expr())?; | 661 | Expectation::has_type(Ty::Bool) |
662 | } else { | ||
663 | Expectation::none() | ||
664 | }; | ||
665 | self.infer_expr_opt(condition.expr(), &expected)?; | ||
460 | // TODO write type for pat | 666 | // TODO write type for pat |
461 | }; | 667 | }; |
462 | self.infer_block_opt(e.loop_body())?; | 668 | self.infer_block_opt(e.loop_body(), &Expectation::has_type(Ty::unit()))?; |
463 | // TODO always unit? | 669 | // TODO always unit? |
464 | Ty::Unknown | 670 | Ty::unit() |
465 | } | 671 | } |
466 | ast::Expr::ForExpr(e) => { | 672 | ast::Expr::ForExpr(e) => { |
467 | let _iterable_ty = self.infer_expr_opt(e.iterable()); | 673 | let _iterable_ty = self.infer_expr_opt(e.iterable(), &Expectation::none()); |
468 | if let Some(_pat) = e.pat() { | 674 | if let Some(_pat) = e.pat() { |
469 | // TODO write type for pat | 675 | // TODO write type for pat |
470 | } | 676 | } |
471 | self.infer_block_opt(e.loop_body())?; | 677 | self.infer_block_opt(e.loop_body(), &Expectation::has_type(Ty::unit()))?; |
472 | // TODO always unit? | 678 | // TODO always unit? |
473 | Ty::Unknown | 679 | Ty::unit() |
474 | } | 680 | } |
475 | ast::Expr::LambdaExpr(e) => { | 681 | ast::Expr::LambdaExpr(e) => { |
476 | let _body_ty = self.infer_expr_opt(e.body())?; | 682 | let _body_ty = self.infer_expr_opt(e.body(), &Expectation::none())?; |
477 | Ty::Unknown | 683 | Ty::Unknown |
478 | } | 684 | } |
479 | ast::Expr::CallExpr(e) => { | 685 | ast::Expr::CallExpr(e) => { |
480 | let callee_ty = self.infer_expr_opt(e.expr())?; | 686 | let callee_ty = self.infer_expr_opt(e.expr(), &Expectation::none())?; |
481 | if let Some(arg_list) = e.arg_list() { | 687 | let (arg_tys, ret_ty) = match &callee_ty { |
482 | for arg in arg_list.args() { | 688 | Ty::FnPtr(sig) => (&sig.input[..], sig.output.clone()), |
483 | // TODO unify / expect argument type | ||
484 | self.infer_expr(arg)?; | ||
485 | } | ||
486 | } | ||
487 | match callee_ty { | ||
488 | Ty::FnPtr(sig) => sig.output.clone(), | ||
489 | _ => { | 689 | _ => { |
490 | // not callable | 690 | // not callable |
491 | // TODO report an error? | 691 | // TODO report an error? |
492 | Ty::Unknown | 692 | (&[][..], Ty::Unknown) |
693 | } | ||
694 | }; | ||
695 | if let Some(arg_list) = e.arg_list() { | ||
696 | for (i, arg) in arg_list.args().enumerate() { | ||
697 | self.infer_expr( | ||
698 | arg, | ||
699 | &Expectation::has_type(arg_tys.get(i).cloned().unwrap_or(Ty::Unknown)), | ||
700 | )?; | ||
493 | } | 701 | } |
494 | } | 702 | } |
703 | ret_ty | ||
495 | } | 704 | } |
496 | ast::Expr::MethodCallExpr(e) => { | 705 | ast::Expr::MethodCallExpr(e) => { |
497 | let _receiver_ty = self.infer_expr_opt(e.expr())?; | 706 | let _receiver_ty = self.infer_expr_opt(e.expr(), &Expectation::none())?; |
498 | if let Some(arg_list) = e.arg_list() { | 707 | if let Some(arg_list) = e.arg_list() { |
499 | for arg in arg_list.args() { | 708 | for arg in arg_list.args() { |
500 | // TODO unify / expect argument type | 709 | // TODO unify / expect argument type |
501 | self.infer_expr(arg)?; | 710 | self.infer_expr(arg, &Expectation::none())?; |
502 | } | 711 | } |
503 | } | 712 | } |
504 | Ty::Unknown | 713 | Ty::Unknown |
505 | } | 714 | } |
506 | ast::Expr::MatchExpr(e) => { | 715 | ast::Expr::MatchExpr(e) => { |
507 | let _ty = self.infer_expr_opt(e.expr())?; | 716 | let _ty = self.infer_expr_opt(e.expr(), &Expectation::none())?; |
508 | if let Some(match_arm_list) = e.match_arm_list() { | 717 | if let Some(match_arm_list) = e.match_arm_list() { |
509 | for arm in match_arm_list.arms() { | 718 | for arm in match_arm_list.arms() { |
510 | // TODO type the bindings in pat | 719 | // TODO type the bindings in pat |
511 | // TODO type the guard | 720 | // TODO type the guard |
512 | let _ty = self.infer_expr_opt(arm.expr())?; | 721 | let _ty = self.infer_expr_opt(arm.expr(), &Expectation::none())?; |
513 | } | 722 | } |
514 | // TODO unify all the match arm types | 723 | // TODO unify all the match arm types |
515 | Ty::Unknown | 724 | Ty::Unknown |
@@ -522,10 +731,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
522 | ast::Expr::PathExpr(e) => self.infer_path_expr(e)?.unwrap_or(Ty::Unknown), | 731 | ast::Expr::PathExpr(e) => self.infer_path_expr(e)?.unwrap_or(Ty::Unknown), |
523 | ast::Expr::ContinueExpr(_e) => Ty::Never, | 732 | ast::Expr::ContinueExpr(_e) => Ty::Never, |
524 | ast::Expr::BreakExpr(_e) => Ty::Never, | 733 | ast::Expr::BreakExpr(_e) => Ty::Never, |
525 | ast::Expr::ParenExpr(e) => self.infer_expr_opt(e.expr())?, | 734 | ast::Expr::ParenExpr(e) => self.infer_expr_opt(e.expr(), expected)?, |
526 | ast::Expr::Label(_e) => Ty::Unknown, | 735 | ast::Expr::Label(_e) => Ty::Unknown, |
527 | ast::Expr::ReturnExpr(e) => { | 736 | ast::Expr::ReturnExpr(e) => { |
528 | self.infer_expr_opt(e.expr())?; | 737 | self.infer_expr_opt(e.expr(), &Expectation::none())?; |
529 | Ty::Never | 738 | Ty::Never |
530 | } | 739 | } |
531 | ast::Expr::MatchArmList(_) | ast::Expr::MatchArm(_) | ast::Expr::MatchGuard(_) => { | 740 | ast::Expr::MatchArmList(_) | ast::Expr::MatchArm(_) | ast::Expr::MatchGuard(_) => { |
@@ -533,11 +742,16 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
533 | Ty::Unknown | 742 | Ty::Unknown |
534 | } | 743 | } |
535 | ast::Expr::StructLit(e) => { | 744 | ast::Expr::StructLit(e) => { |
536 | let (ty, _variant_data) = self.resolve_variant(e.path())?; | 745 | let (ty, def_id) = self.resolve_variant(e.path())?; |
537 | if let Some(nfl) = e.named_field_list() { | 746 | if let Some(nfl) = e.named_field_list() { |
538 | for field in nfl.fields() { | 747 | for field in nfl.fields() { |
539 | // TODO unify with / expect field type | 748 | let field_ty = if let (Some(def_id), Some(nr)) = (def_id, field.name_ref()) |
540 | self.infer_expr_opt(field.expr())?; | 749 | { |
750 | self.db.type_for_field(def_id, nr.as_name())? | ||
751 | } else { | ||
752 | Ty::Unknown | ||
753 | }; | ||
754 | self.infer_expr_opt(field.expr(), &Expectation::has_type(field_ty))?; | ||
541 | } | 755 | } |
542 | } | 756 | } |
543 | ty | 757 | ty |
@@ -548,9 +762,9 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
548 | } | 762 | } |
549 | ast::Expr::IndexExpr(_e) => Ty::Unknown, | 763 | ast::Expr::IndexExpr(_e) => Ty::Unknown, |
550 | ast::Expr::FieldExpr(e) => { | 764 | ast::Expr::FieldExpr(e) => { |
551 | let receiver_ty = self.infer_expr_opt(e.expr())?; | 765 | let receiver_ty = self.infer_expr_opt(e.expr(), &Expectation::none())?; |
552 | if let Some(nr) = e.name_ref() { | 766 | if let Some(nr) = e.name_ref() { |
553 | match receiver_ty { | 767 | let ty = match receiver_ty { |
554 | Ty::Tuple(fields) => { | 768 | Ty::Tuple(fields) => { |
555 | let i = nr.text().parse::<usize>().ok(); | 769 | let i = nr.text().parse::<usize>().ok(); |
556 | i.and_then(|i| fields.get(i).cloned()) | 770 | i.and_then(|i| fields.get(i).cloned()) |
@@ -558,29 +772,32 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
558 | } | 772 | } |
559 | Ty::Adt { def_id, .. } => self.db.type_for_field(def_id, nr.as_name())?, | 773 | Ty::Adt { def_id, .. } => self.db.type_for_field(def_id, nr.as_name())?, |
560 | _ => Ty::Unknown, | 774 | _ => Ty::Unknown, |
561 | } | 775 | }; |
776 | self.insert_type_vars(ty) | ||
562 | } else { | 777 | } else { |
563 | Ty::Unknown | 778 | Ty::Unknown |
564 | } | 779 | } |
565 | } | 780 | } |
566 | ast::Expr::TryExpr(e) => { | 781 | ast::Expr::TryExpr(e) => { |
567 | let _inner_ty = self.infer_expr_opt(e.expr())?; | 782 | let _inner_ty = self.infer_expr_opt(e.expr(), &Expectation::none())?; |
568 | Ty::Unknown | 783 | Ty::Unknown |
569 | } | 784 | } |
570 | ast::Expr::CastExpr(e) => { | 785 | ast::Expr::CastExpr(e) => { |
571 | let _inner_ty = self.infer_expr_opt(e.expr())?; | 786 | let _inner_ty = self.infer_expr_opt(e.expr(), &Expectation::none())?; |
572 | let cast_ty = Ty::from_ast_opt(self.db, &self.module, e.type_ref())?; | 787 | let cast_ty = Ty::from_ast_opt(self.db, &self.module, e.type_ref())?; |
788 | let cast_ty = self.insert_type_vars(cast_ty); | ||
573 | // TODO do the coercion... | 789 | // TODO do the coercion... |
574 | cast_ty | 790 | cast_ty |
575 | } | 791 | } |
576 | ast::Expr::RefExpr(e) => { | 792 | ast::Expr::RefExpr(e) => { |
577 | let inner_ty = self.infer_expr_opt(e.expr())?; | 793 | // TODO pass the expectation down |
794 | let inner_ty = self.infer_expr_opt(e.expr(), &Expectation::none())?; | ||
578 | let m = Mutability::from_mutable(e.is_mut()); | 795 | let m = Mutability::from_mutable(e.is_mut()); |
579 | // TODO reference coercions etc. | 796 | // TODO reference coercions etc. |
580 | Ty::Ref(Arc::new(inner_ty), m) | 797 | Ty::Ref(Arc::new(inner_ty), m) |
581 | } | 798 | } |
582 | ast::Expr::PrefixExpr(e) => { | 799 | ast::Expr::PrefixExpr(e) => { |
583 | let inner_ty = self.infer_expr_opt(e.expr())?; | 800 | let inner_ty = self.infer_expr_opt(e.expr(), &Expectation::none())?; |
584 | match e.op() { | 801 | match e.op() { |
585 | Some(PrefixOp::Deref) => { | 802 | Some(PrefixOp::Deref) => { |
586 | match inner_ty { | 803 | match inner_ty { |
@@ -598,28 +815,34 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
598 | ast::Expr::BinExpr(_e) => Ty::Unknown, | 815 | ast::Expr::BinExpr(_e) => Ty::Unknown, |
599 | ast::Expr::Literal(_e) => Ty::Unknown, | 816 | ast::Expr::Literal(_e) => Ty::Unknown, |
600 | }; | 817 | }; |
818 | // use a new type variable if we got Ty::Unknown here | ||
819 | let ty = self.insert_type_vars_shallow(ty); | ||
820 | self.unify(&ty, &expected.ty); | ||
601 | self.write_ty(expr.syntax(), ty.clone()); | 821 | self.write_ty(expr.syntax(), ty.clone()); |
602 | Ok(ty) | 822 | Ok(ty) |
603 | } | 823 | } |
604 | 824 | ||
605 | fn infer_block_opt(&mut self, node: Option<ast::Block>) -> Cancelable<Ty> { | 825 | fn infer_block_opt( |
826 | &mut self, | ||
827 | node: Option<ast::Block>, | ||
828 | expected: &Expectation, | ||
829 | ) -> Cancelable<Ty> { | ||
606 | if let Some(b) = node { | 830 | if let Some(b) = node { |
607 | self.infer_block(b) | 831 | self.infer_block(b, expected) |
608 | } else { | 832 | } else { |
609 | Ok(Ty::Unknown) | 833 | Ok(Ty::Unknown) |
610 | } | 834 | } |
611 | } | 835 | } |
612 | 836 | ||
613 | fn infer_block(&mut self, node: ast::Block) -> Cancelable<Ty> { | 837 | fn infer_block(&mut self, node: ast::Block, expected: &Expectation) -> Cancelable<Ty> { |
614 | for stmt in node.statements() { | 838 | for stmt in node.statements() { |
615 | match stmt { | 839 | match stmt { |
616 | ast::Stmt::LetStmt(stmt) => { | 840 | ast::Stmt::LetStmt(stmt) => { |
617 | let decl_ty = Ty::from_ast_opt(self.db, &self.module, stmt.type_ref())?; | 841 | let decl_ty = Ty::from_ast_opt(self.db, &self.module, stmt.type_ref())?; |
842 | let decl_ty = self.insert_type_vars(decl_ty); | ||
618 | let ty = if let Some(expr) = stmt.initializer() { | 843 | let ty = if let Some(expr) = stmt.initializer() { |
619 | // TODO pass expectation | 844 | let expr_ty = self.infer_expr(expr, &Expectation::has_type(decl_ty))?; |
620 | let expr_ty = self.infer_expr(expr)?; | 845 | expr_ty |
621 | self.unify_with_coercion(&expr_ty, &decl_ty) | ||
622 | .unwrap_or(decl_ty) | ||
623 | } else { | 846 | } else { |
624 | decl_ty | 847 | decl_ty |
625 | }; | 848 | }; |
@@ -629,12 +852,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { | |||
629 | }; | 852 | }; |
630 | } | 853 | } |
631 | ast::Stmt::ExprStmt(expr_stmt) => { | 854 | ast::Stmt::ExprStmt(expr_stmt) => { |
632 | self.infer_expr_opt(expr_stmt.expr())?; | 855 | self.infer_expr_opt(expr_stmt.expr(), &Expectation::none())?; |
633 | } | 856 | } |
634 | } | 857 | } |
635 | } | 858 | } |
636 | let ty = if let Some(expr) = node.expr() { | 859 | let ty = if let Some(expr) = node.expr() { |
637 | self.infer_expr(expr)? | 860 | self.infer_expr(expr, expected)? |
638 | } else { | 861 | } else { |
639 | Ty::unit() | 862 | Ty::unit() |
640 | }; | 863 | }; |
@@ -660,25 +883,27 @@ pub fn infer(db: &impl HirDatabase, function: Function) -> Cancelable<InferenceR | |||
660 | }; | 883 | }; |
661 | if let Some(type_ref) = param.type_ref() { | 884 | if let Some(type_ref) = param.type_ref() { |
662 | let ty = Ty::from_ast(db, &ctx.module, type_ref)?; | 885 | let ty = Ty::from_ast(db, &ctx.module, type_ref)?; |
886 | let ty = ctx.insert_type_vars(ty); | ||
663 | ctx.type_of.insert(LocalSyntaxPtr::new(pat.syntax()), ty); | 887 | ctx.type_of.insert(LocalSyntaxPtr::new(pat.syntax()), ty); |
664 | } else { | 888 | } else { |
665 | // TODO self param | 889 | // TODO self param |
890 | let type_var = ctx.new_type_var(); | ||
666 | ctx.type_of | 891 | ctx.type_of |
667 | .insert(LocalSyntaxPtr::new(pat.syntax()), Ty::Unknown); | 892 | .insert(LocalSyntaxPtr::new(pat.syntax()), type_var); |
668 | }; | 893 | }; |
669 | } | 894 | } |
670 | } | 895 | } |
671 | 896 | ||
672 | // TODO get Ty for node.ret_type() and pass that to infer_block as expectation | 897 | let ret_ty = if let Some(type_ref) = node.ret_type().and_then(|n| n.type_ref()) { |
673 | // (see Expectation in rustc_typeck) | 898 | let ty = Ty::from_ast(db, &ctx.module, type_ref)?; |
899 | ctx.insert_type_vars(ty) | ||
900 | } else { | ||
901 | Ty::unit() | ||
902 | }; | ||
674 | 903 | ||
675 | if let Some(block) = node.body() { | 904 | if let Some(block) = node.body() { |
676 | ctx.infer_block(block)?; | 905 | ctx.infer_block(block, &Expectation::has_type(ret_ty))?; |
677 | } | 906 | } |
678 | 907 | ||
679 | // TODO 'resolve' the types: replace inference variables by their inferred results | 908 | Ok(ctx.resolve_all()) |
680 | |||
681 | Ok(InferenceResult { | ||
682 | type_of: ctx.type_of, | ||
683 | }) | ||
684 | } | 909 | } |