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.

5 files changed, 48 insertions, 7 deletions

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) {
     );
 }
 
+#[test]
+fn infer_backwards() {
+    check_inference(
+        r#"
+fn takes_u32(x: u32) {}
+
+struct S { i32_field: i32 }
+
+fn test() -> &mut &f64 {
+    let a = unknown_function();
+    takes_u32(a);
+    let b = unknown_function();
+    S { i32_field: b };
+    let c = unknown_function();
+    &mut &c
+}
+"#,
+        "0006_backwards.txt",
+    );
+}
+
 fn infer(content: &str) -> String {
     let (db, _, file_id) = MockDatabase::with_single_file(content);
     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 @@
 [21; 22) 'a': [unknown]
-[52; 53) '1': [unknown]
+[52; 53) '1': usize
 [11; 71) '{     ...= b; }': ()
 [63; 64) 'c': usize
 [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 @@
-[15; 20) '{ 1 }': [unknown]
-[17; 18) '1': [unknown]
-[50; 51) '1': [unknown]
-[48; 53) '{ 1 }': [unknown]
+[15; 20) '{ 1 }': u32
+[17; 18) '1': u32
+[50; 51) '1': u32
+[48; 53) '{ 1 }': u32
 [82; 88) 'b::c()': u32
 [67; 91) '{     ...c(); }': ()
 [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 @@
 [86; 90) 'C(1)': [unknown]
-[121; 122) 'B': [unknown]
+[121; 122) 'B': B
 [86; 87) 'C': [unknown]
 [129; 130) '1': [unknown]
 [107; 108) 'a': A
@@ -13,4 +13,4 @@
 [96; 97) 'B': [unknown]
 [88; 89) '1': [unknown]
 [82; 83) 'c': [unknown]
-[127; 131) 'C(1)': [unknown]
+[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 @@
+[22; 24) '{}': ()
+[14; 15) 'x': u32
+[142; 158) 'unknow...nction': [unknown]
+[126; 127) 'a': u32
+[198; 216) 'unknow...tion()': f64
+[228; 229) 'c': f64
+[198; 214) 'unknow...nction': [unknown]
+[166; 184) 'S { i3...d: b }': S
+[222; 229) '&mut &c': &mut &f64
+[194; 195) 'c': f64
+[92; 110) 'unknow...tion()': u32
+[142; 160) 'unknow...tion()': i32
+[92; 108) 'unknow...nction': [unknown]
+[116; 128) 'takes_u32(a)': [unknown]
+[78; 231) '{     ...t &c }': &mut &f64
+[227; 229) '&c': &f64
+[88; 89) 'a': u32
+[181; 182) 'b': i32
+[116; 125) 'takes_u32': fn(u32,) -> [unknown]
+[138; 139) 'b': i32