aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src
diff options
context:
space:
mode:
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