Merge #327

327: Beginnings of type inference r=flodiebold a=flodiebold

I was a bit bored, so I thought I'd try to start implementing the type system and see how far I come :wink:  This is obviously still extremely WIP, only very basic stuff working, but I thought I'd post this now to get some feedback as to whether this approach makes sense at all.

There's no user-visible effect yet, but the type inference has tests similar to the ones for the parser. My next step will probably be to implement struct types, after which this could probably be used to complete fields.

I realize this may all get thrown away when/if the compiler query system gets usable, but I feel like there are lots of IDE features that could be implemented with somewhat working type inference in the meantime :smile: 

Co-authored-by: Florian Diebold <[email protected]>

3 files changed, 96 insertions, 140 deletions

diff --git a/crates/ra_syntax/src/ast/generated.rs b/crates/ra_syntax/src/ast/generated.rs
index bf056131e..c73533861 100644
--- a/crates/ra_syntax/src/ast/generated.rs
+++ b/crates/ra_syntax/src/ast/generated.rs
@@ -523,7 +523,15 @@ impl<R: TreeRoot<RaTypes>> CastExprNode<R> {
 }
 
 
-impl<'a> CastExpr<'a> {}
+impl<'a> CastExpr<'a> {
+    pub fn expr(self) -> Option<Expr<'a>> {
+        super::child_opt(self)
+    }
+
+    pub fn type_ref(self) -> Option<TypeRef<'a>> {
+        super::child_opt(self)
+    }
+}
 
 // Char
 #[derive(Debug, Clone, Copy,)]
@@ -1553,6 +1561,10 @@ impl<'a> LetStmt<'a> {
         super::child_opt(self)
     }
 
+    pub fn type_ref(self) -> Option<TypeRef<'a>> {
+        super::child_opt(self)
+    }
+
     pub fn initializer(self) -> Option<Expr<'a>> {
         super::child_opt(self)
     }
@@ -2312,6 +2324,10 @@ impl<'a> Param<'a> {
     pub fn pat(self) -> Option<Pat<'a>> {
         super::child_opt(self)
     }
+
+    pub fn type_ref(self) -> Option<TypeRef<'a>> {
+        super::child_opt(self)
+    }
 }
 
 // ParamList
@@ -2394,7 +2410,11 @@ impl<R: TreeRoot<RaTypes>> ParenExprNode<R> {
 }
 
 
-impl<'a> ParenExpr<'a> {}
+impl<'a> ParenExpr<'a> {
+    pub fn expr(self) -> Option<Expr<'a>> {
+        super::child_opt(self)
+    }
+}
 
 // ParenType
 #[derive(Debug, Clone, Copy,)]
@@ -2681,7 +2701,11 @@ impl<R: TreeRoot<RaTypes>> PathTypeNode<R> {
 }
 
 
-impl<'a> PathType<'a> {}
+impl<'a> PathType<'a> {
+    pub fn path(self) -> Option<Path<'a>> {
+        super::child_opt(self)
+    }
+}
 
 // PlaceholderPat
 #[derive(Debug, Clone, Copy,)]
@@ -2829,7 +2853,11 @@ impl<R: TreeRoot<RaTypes>> PrefixExprNode<R> {
 }
 
 
-impl<'a> PrefixExpr<'a> {}
+impl<'a> PrefixExpr<'a> {
+    pub fn expr(self) -> Option<Expr<'a>> {
+        super::child_opt(self)
+    }
+}
 
 // RangeExpr
 #[derive(Debug, Clone, Copy,)]
@@ -2940,7 +2968,11 @@ impl<R: TreeRoot<RaTypes>> RefExprNode<R> {
 }
 
 
-impl<'a> RefExpr<'a> {}
+impl<'a> RefExpr<'a> {
+    pub fn expr(self) -> Option<Expr<'a>> {
+        super::child_opt(self)
+    }
+}
 
 // RefPat
 #[derive(Debug, Clone, Copy,)]
@@ -3051,7 +3083,11 @@ impl<R: TreeRoot<RaTypes>> RetTypeNode<R> {
 }
 
 
-impl<'a> RetType<'a> {}
+impl<'a> RetType<'a> {
+    pub fn type_ref(self) -> Option<TypeRef<'a>> {
+        super::child_opt(self)
+    }
+}
 
 // ReturnExpr
 #[derive(Debug, Clone, Copy,)]
@@ -3088,7 +3124,11 @@ impl<R: TreeRoot<RaTypes>> ReturnExprNode<R> {
 }
 
 
-impl<'a> ReturnExpr<'a> {}
+impl<'a> ReturnExpr<'a> {
+    pub fn expr(self) -> Option<Expr<'a>> {
+        super::child_opt(self)
+    }
+}
 
 // SelfParam
 #[derive(Debug, Clone, Copy,)]
@@ -3578,7 +3618,11 @@ impl<R: TreeRoot<RaTypes>> TryExprNode<R> {
 }
 
 
-impl<'a> TryExpr<'a> {}
+impl<'a> TryExpr<'a> {
+    pub fn expr(self) -> Option<Expr<'a>> {
+        super::child_opt(self)
+    }
+}
 
 // TupleExpr
 #[derive(Debug, Clone, Copy,)]
diff --git a/crates/ra_syntax/src/grammar.ron b/crates/ra_syntax/src/grammar.ron
index eed67637e..e3b9032a0 100644
--- a/crates/ra_syntax/src/grammar.ron
+++ b/crates/ra_syntax/src/grammar.ron
@@ -254,7 +254,7 @@ Grammar(
             ],
             options: [ "ParamList", ["body", "Block"], "RetType" ],
         ),
-        "RetType": (),
+        "RetType": (options: ["TypeRef"]),
         "StructDef": (
             traits: [
                 "NameOwner",
@@ -304,7 +304,7 @@ Grammar(
         "ParenType": (),
         "TupleType": (),
         "NeverType": (),
-        "PathType": (),
+        "PathType": (options: ["Path"]),
         "PointerType": (),
         "ArrayType": (),
         "SliceType": (),
@@ -346,7 +346,7 @@ Grammar(
 
         "TupleExpr": (),
         "ArrayExpr": (),
-        "ParenExpr": (),
+        "ParenExpr": (options: ["Expr"]),
         "PathExpr": (options: ["Path"]),
         "LambdaExpr": (
             options: [
@@ -377,7 +377,7 @@ Grammar(
         "BlockExpr": (
             options: [ "Block" ]
         ),
-        "ReturnExpr": (),
+        "ReturnExpr": (options: ["Expr"]),
         "MatchExpr": (
             options: [ "Expr", "MatchArmList" ],
         ),
@@ -405,10 +405,10 @@ Grammar(
         ),
         "IndexExpr": (),
         "FieldExpr": (),
-        "TryExpr": (),
-        "CastExpr": (),
-        "RefExpr": (),
-        "PrefixExpr": (),
+        "TryExpr": (options: ["Expr"]),
+        "CastExpr": (options: ["Expr", "TypeRef"]),
+        "RefExpr": (options: ["Expr"]),
+        "PrefixExpr": (options: ["Expr"]),
         "RangeExpr": (),
         "BinExpr": (),
         "String": (),
@@ -499,6 +499,7 @@ Grammar(
         ),
         "LetStmt": ( options: [
             ["pat", "Pat"],
+            ["type_ref", "TypeRef"],
             ["initializer", "Expr"],
         ]),
         "Condition": (
@@ -521,7 +522,7 @@ Grammar(
         ),
         "SelfParam": (),
         "Param": (
-            options: [ "Pat" ],
+            options: [ "Pat", "TypeRef" ],
         ),
         "UseItem": (
             options: [ "UseTree" ]
diff --git a/crates/ra_syntax/tests/test.rs b/crates/ra_syntax/tests/test.rs
index 4266864bd..2235dc401 100644
--- a/crates/ra_syntax/tests/test.rs
+++ b/crates/ra_syntax/tests/test.rs
@@ -1,14 +1,13 @@
 extern crate ra_syntax;
-#[macro_use]
 extern crate test_utils;
 extern crate walkdir;
 
 use std::{
     fmt::Write,
-    fs,
-    path::{Path, PathBuf, Component},
+    path::{PathBuf, Component},
 };
 
+use test_utils::{project_dir, dir_tests, read_text, collect_tests};
 use ra_syntax::{
     utils::{check_fuzz_invariants, dump_tree},
     SourceFileNode,
@@ -16,7 +15,7 @@ use ra_syntax::{
 
 #[test]
 fn lexer_tests() {
-    dir_tests(&["lexer"], |text, _| {
+    dir_tests(&test_data_dir(), &["lexer"], |text, _| {
         let tokens = ra_syntax::tokenize(text);
         dump_tokens(&tokens, text)
     })
@@ -24,33 +23,41 @@ fn lexer_tests() {
 
 #[test]
 fn parser_tests() {
-    dir_tests(&["parser/inline/ok", "parser/ok"], |text, path| {
-        let file = SourceFileNode::parse(text);
-        let errors = file.errors();
-        assert_eq!(
-            &*errors,
-            &[] as &[ra_syntax::SyntaxError],
-            "There should be no errors in the file {:?}",
-            path.display()
-        );
-        dump_tree(file.syntax())
-    });
-    dir_tests(&["parser/err", "parser/inline/err"], |text, path| {
-        let file = SourceFileNode::parse(text);
-        let errors = file.errors();
-        assert_ne!(
-            &*errors,
-            &[] as &[ra_syntax::SyntaxError],
-            "There should be errors in the file {:?}",
-            path.display()
-        );
-        dump_tree(file.syntax())
-    });
+    dir_tests(
+        &test_data_dir(),
+        &["parser/inline/ok", "parser/ok"],
+        |text, path| {
+            let file = SourceFileNode::parse(text);
+            let errors = file.errors();
+            assert_eq!(
+                &*errors,
+                &[] as &[ra_syntax::SyntaxError],
+                "There should be no errors in the file {:?}",
+                path.display()
+            );
+            dump_tree(file.syntax())
+        },
+    );
+    dir_tests(
+        &test_data_dir(),
+        &["parser/err", "parser/inline/err"],
+        |text, path| {
+            let file = SourceFileNode::parse(text);
+            let errors = file.errors();
+            assert_ne!(
+                &*errors,
+                &[] as &[ra_syntax::SyntaxError],
+                "There should be errors in the file {:?}",
+                path.display()
+            );
+            dump_tree(file.syntax())
+        },
+    );
 }
 
 #[test]
 fn parser_fuzz_tests() {
-    for (_, text) in collect_tests(&["parser/fuzz-failures"]) {
+    for (_, text) in collect_tests(&test_data_dir(), &["parser/fuzz-failures"]) {
         check_fuzz_invariants(&text)
     }
 }
@@ -92,102 +99,6 @@ fn self_hosting_parsing() {
         "self_hosting_parsing found too few files - is it running in the right directory?"
     )
 }
-/// Read file and normalize newlines.
-///
-/// `rustc` seems to always normalize `\r\n` newlines to `\n`:
-///
-/// ```
-/// let s = "
-/// ";
-/// assert_eq!(s.as_bytes(), &[10]);
-/// ```
-///
-/// so this should always be correct.
-fn read_text(path: &Path) -> String {
-    fs::read_to_string(path)
-        .expect(&format!("File at {:?} should be valid", path))
-        .replace("\r\n", "\n")
-}
-
-fn dir_tests<F>(paths: &[&str], f: F)
-where
-    F: Fn(&str, &Path) -> String,
-{
-    for (path, input_code) in collect_tests(paths) {
-        let parse_tree = f(&input_code, &path);
-        let path = path.with_extension("txt");
-        if !path.exists() {
-            println!("\nfile: {}", path.display());
-            println!("No .txt file with expected result, creating...\n");
-            println!("{}\n{}", input_code, parse_tree);
-            fs::write(&path, &parse_tree).unwrap();
-            panic!("No expected result")
-        }
-        let expected = read_text(&path);
-        let expected = expected.as_str();
-        let parse_tree = parse_tree.as_str();
-        assert_equal_text(expected, parse_tree, &path);
-    }
-}
-
-const REWRITE: bool = false;
-
-fn assert_equal_text(expected: &str, actual: &str, path: &Path) {
-    if expected == actual {
-        return;
-    }
-    let dir = project_dir();
-    let pretty_path = path.strip_prefix(&dir).unwrap_or_else(|_| path);
-    if expected.trim() == actual.trim() {
-        println!("whitespace difference, rewriting");
-        println!("file: {}\n", pretty_path.display());
-        fs::write(path, actual).unwrap();
-        return;
-    }
-    if REWRITE {
-        println!("rewriting {}", pretty_path.display());
-        fs::write(path, actual).unwrap();
-        return;
-    }
-    assert_eq_text!(expected, actual, "file: {}", pretty_path.display());
-}
-
-fn collect_tests(paths: &[&str]) -> Vec<(PathBuf, String)> {
-    paths
-        .iter()
-        .flat_map(|path| {
-            let path = test_data_dir().join(path);
-            test_from_dir(&path).into_iter()
-        })
-        .map(|path| {
-            let text = read_text(&path);
-            (path, text)
-        })
-        .collect()
-}
-
-fn test_from_dir(dir: &Path) -> Vec<PathBuf> {
-    let mut acc = Vec::new();
-    for file in fs::read_dir(&dir).unwrap() {
-        let file = file.unwrap();
-        let path = file.path();
-        if path.extension().unwrap_or_default() == "rs" {
-            acc.push(path);
-        }
-    }
-    acc.sort();
-    acc
-}
-
-fn project_dir() -> PathBuf {
-    let dir = env!("CARGO_MANIFEST_DIR");
-    PathBuf::from(dir)
-        .parent()
-        .unwrap()
-        .parent()
-        .unwrap()
-        .to_owned()
-}
 
 fn test_data_dir() -> PathBuf {
     project_dir().join("crates/ra_syntax/tests/data")