aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src
diff options
context:
space:
mode:
authorFlorian Diebold <[email protected]>2018-12-26 16:00:42 +0000
committerFlorian Diebold <[email protected]>2018-12-29 11:04:34 +0000
commitcfa1de72ebb7060a82dbf7a67432047d9ea2288a (patch)
treea679ed837f309ee523590b5777b919604e588b4b /crates/ra_hir/src
parentf3f073804cf768c0b219d89081a26bedfde8ffed (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')
-rw-r--r--crates/ra_hir/src/ty.rs447
-rw-r--r--crates/ra_hir/src/ty/tests.rs21
-rw-r--r--crates/ra_hir/src/ty/tests/data/0002_let.txt2
-rw-r--r--crates/ra_hir/src/ty/tests/data/0003_paths.txt8
-rw-r--r--crates/ra_hir/src/ty/tests/data/0004_struct.txt4
-rw-r--r--crates/ra_hir/src/ty/tests/data/0006_backwards.txt20
6 files changed, 384 insertions, 118 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;
3mod tests; 3mod tests;
4 4
5use std::sync::Arc; 5use std::sync::Arc;
6use std::fmt; 6use std::{fmt, mem};
7 7
8use log; 8use log;
9use rustc_hash::{FxHashMap}; 9use rustc_hash::FxHashMap;
10use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError};
10 11
11use ra_db::{LocalSyntaxPtr, Cancelable}; 12use ra_db::{LocalSyntaxPtr, Cancelable};
12use ra_syntax::{ 13use ra_syntax::{
@@ -17,10 +18,89 @@ use ra_syntax::{
17use crate::{ 18use 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)]
25pub struct TypeVarId(u32);
26
27impl 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)]
44pub enum TypeVarValue {
45 Known(Ty),
46 Unknown,
47}
48
49impl 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
58impl 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)]
79pub 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)]
87struct 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
94impl 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)]
25pub enum Ty { 105pub 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}
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index a76925b58..93bf431c4 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -113,6 +113,27 @@ fn test(a: &u32, b: &mut u32, c: *const u32, d: *mut u32) {
113 ); 113 );
114} 114}
115 115
116#[test]
117fn infer_backwards() {
118 check_inference(
119 r#"
120fn takes_u32(x: u32) {}
121
122struct S { i32_field: i32 }
123
124fn test() -> &mut &f64 {
125 let a = unknown_function();
126 takes_u32(a);
127 let b = unknown_function();
128 S { i32_field: b };
129 let c = unknown_function();
130 &mut &c
131}
132"#,
133 "0006_backwards.txt",
134 );
135}
136
116fn infer(content: &str) -> String { 137fn infer(content: &str) -> String {
117 let (db, _, file_id) = MockDatabase::with_single_file(content); 138 let (db, _, file_id) = MockDatabase::with_single_file(content);
118 let source_file = db.source_file(file_id); 139 let source_file = db.source_file(file_id);
diff --git a/crates/ra_hir/src/ty/tests/data/0002_let.txt b/crates/ra_hir/src/ty/tests/data/0002_let.txt
index 2d0d1f57b..916ca25a1 100644
--- a/crates/ra_hir/src/ty/tests/data/0002_let.txt
+++ b/crates/ra_hir/src/ty/tests/data/0002_let.txt
@@ -1,5 +1,5 @@
1[21; 22) 'a': [unknown] 1[21; 22) 'a': [unknown]
2[52; 53) '1': [unknown] 2[52; 53) '1': usize
3[11; 71) '{ ...= b; }': () 3[11; 71) '{ ...= b; }': ()
4[63; 64) 'c': usize 4[63; 64) 'c': usize
5[25; 31) '1isize': [unknown] 5[25; 31) '1isize': [unknown]
diff --git a/crates/ra_hir/src/ty/tests/data/0003_paths.txt b/crates/ra_hir/src/ty/tests/data/0003_paths.txt
index dcb5456ae..2a12d264f 100644
--- a/crates/ra_hir/src/ty/tests/data/0003_paths.txt
+++ b/crates/ra_hir/src/ty/tests/data/0003_paths.txt
@@ -1,7 +1,7 @@
1[15; 20) '{ 1 }': [unknown] 1[15; 20) '{ 1 }': u32
2[17; 18) '1': [unknown] 2[17; 18) '1': u32
3[50; 51) '1': [unknown] 3[50; 51) '1': u32
4[48; 53) '{ 1 }': [unknown] 4[48; 53) '{ 1 }': u32
5[82; 88) 'b::c()': u32 5[82; 88) 'b::c()': u32
6[67; 91) '{ ...c(); }': () 6[67; 91) '{ ...c(); }': ()
7[73; 74) 'a': fn() -> u32 7[73; 74) 'a': fn() -> u32
diff --git a/crates/ra_hir/src/ty/tests/data/0004_struct.txt b/crates/ra_hir/src/ty/tests/data/0004_struct.txt
index cc8f3665b..b4af18b87 100644
--- a/crates/ra_hir/src/ty/tests/data/0004_struct.txt
+++ b/crates/ra_hir/src/ty/tests/data/0004_struct.txt
@@ -1,5 +1,5 @@
1[86; 90) 'C(1)': [unknown] 1[86; 90) 'C(1)': [unknown]
2[121; 122) 'B': [unknown] 2[121; 122) 'B': B
3[86; 87) 'C': [unknown] 3[86; 87) 'C': [unknown]
4[129; 130) '1': [unknown] 4[129; 130) '1': [unknown]
5[107; 108) 'a': A 5[107; 108) 'a': A
@@ -13,4 +13,4 @@
13[96; 97) 'B': [unknown] 13[96; 97) 'B': [unknown]
14[88; 89) '1': [unknown] 14[88; 89) '1': [unknown]
15[82; 83) 'c': [unknown] 15[82; 83) 'c': [unknown]
16[127; 131) 'C(1)': [unknown] 16[127; 131) 'C(1)': C
diff --git a/crates/ra_hir/src/ty/tests/data/0006_backwards.txt b/crates/ra_hir/src/ty/tests/data/0006_backwards.txt
new file mode 100644
index 000000000..3a12aeef4
--- /dev/null
+++ b/crates/ra_hir/src/ty/tests/data/0006_backwards.txt
@@ -0,0 +1,20 @@
1[22; 24) '{}': ()
2[14; 15) 'x': u32
3[142; 158) 'unknow...nction': [unknown]
4[126; 127) 'a': u32
5[198; 216) 'unknow...tion()': f64
6[228; 229) 'c': f64
7[198; 214) 'unknow...nction': [unknown]
8[166; 184) 'S { i3...d: b }': S
9[222; 229) '&mut &c': &mut &f64
10[194; 195) 'c': f64
11[92; 110) 'unknow...tion()': u32
12[142; 160) 'unknow...tion()': i32
13[92; 108) 'unknow...nction': [unknown]
14[116; 128) 'takes_u32(a)': [unknown]
15[78; 231) '{ ...t &c }': &mut &f64
16[227; 229) '&c': &f64
17[88; 89) 'a': u32
18[181; 182) 'b': i32
19[116; 125) 'takes_u32': fn(u32,) -> [unknown]
20[138; 139) 'b': i32