Universally quantified type variables

Implement universally quantified type variables, both explicitly given
by the user and inferred by the type inference algorithm.

3 files changed, 74 insertions, 9 deletions

diff --git a/src/parser/expr.rs b/src/parser/expr.rs
index fd37fcb9c67c..12c55df02b80 100644
--- a/src/parser/expr.rs
+++ b/src/parser/expr.rs
@@ -9,7 +9,7 @@ use nom::{
 use pratt::{Affix, Associativity, PrattParser, Precedence};
 
 use crate::ast::{BinaryOperator, Binding, Expr, Fun, Literal, UnaryOperator};
-use crate::parser::{ident, type_};
+use crate::parser::{arg, ident, type_};
 
 #[derive(Debug)]
 enum TokenTree<'a> {
@@ -274,7 +274,7 @@ named!(no_arg_call(&str) -> Expr, do_parse!(
 named!(fun_expr(&str) -> Expr, do_parse!(
     tag!("fn")
         >> multispace1
-        >> args: separated_list0!(multispace1, ident)
+        >> args: separated_list0!(multispace1, arg)
         >> multispace0
         >> char!('=')
         >> multispace0
@@ -285,7 +285,7 @@ named!(fun_expr(&str) -> Expr, do_parse!(
         })))
 ));
 
-named!(arg(&str) -> Expr, alt!(
+named!(fn_arg(&str) -> Expr, alt!(
     ident_expr |
     literal_expr |
     paren_expr
@@ -294,7 +294,7 @@ named!(arg(&str) -> Expr, alt!(
 named!(call_with_args(&str) -> Expr, do_parse!(
     fun: funcref
         >> multispace1
-        >> args: separated_list1!(multispace1, arg)
+        >> args: separated_list1!(multispace1, fn_arg)
         >> (Expr::Call {
             fun: Box::new(fun),
             args
@@ -326,7 +326,7 @@ named!(pub expr(&str) -> Expr, alt!(
 #[cfg(test)]
 pub(crate) mod tests {
     use super::*;
-    use crate::ast::{Ident, Type};
+    use crate::ast::{Arg, Ident, Type};
     use std::convert::TryFrom;
     use BinaryOperator::*;
     use Expr::{BinaryOp, If, Let, UnaryOp};
@@ -549,7 +549,7 @@ pub(crate) mod tests {
                     ident: Ident::try_from("id").unwrap(),
                     type_: None,
                     body: Expr::Fun(Box::new(Fun {
-                        args: vec![Ident::try_from("x").unwrap()],
+                        args: vec![Arg::try_from("x").unwrap()],
                         body: *ident_expr("x")
                     }))
                 }],
@@ -586,7 +586,7 @@ pub(crate) mod tests {
                         ident: Ident::try_from("const_1").unwrap(),
                         type_: None,
                         body: Expr::Fun(Box::new(Fun {
-                            args: vec![Ident::try_from("x").unwrap()],
+                            args: vec![Arg::try_from("x").unwrap()],
                             body: Expr::Ascription {
                                 expr: Box::new(Expr::Literal(Literal::Int(1))),
                                 type_: Type::Int,
diff --git a/src/parser/mod.rs b/src/parser/mod.rs
index 9c4598732247..8599ccabfc23 100644
--- a/src/parser/mod.rs
+++ b/src/parser/mod.rs
@@ -7,7 +7,7 @@ mod macros;
 mod expr;
 mod type_;
 
-use crate::ast::{Decl, Fun, Ident};
+use crate::ast::{Arg, Decl, Fun, Ident};
 pub use expr::expr;
 pub use type_::type_;
 
@@ -58,12 +58,33 @@ where
     }
 }
 
+named!(ascripted_arg(&str) -> Arg, do_parse!(
+    complete!(char!('(')) >>
+        multispace0 >>
+        ident: ident >>
+        multispace0 >>
+        complete!(char!(':')) >>
+        multispace0 >>
+        type_: type_ >>
+        multispace0 >>
+        complete!(char!(')')) >>
+        (Arg {
+            ident,
+            type_: Some(type_)
+        })
+));
+
+named!(arg(&str) -> Arg, alt!(
+    ident => { |ident| Arg {ident, type_: None}} |
+    ascripted_arg
+));
+
 named!(fun_decl(&str) -> Decl, do_parse!(
     complete!(tag!("fn"))
         >> multispace0
         >> name: ident
         >> multispace1
-        >> args: separated_list0!(multispace1, ident)
+        >> args: separated_list0!(multispace1, arg)
         >> multispace0
         >> char!('=')
         >> multispace0
@@ -87,6 +108,8 @@ named!(pub toplevel(&str) -> Vec<Decl>, terminated!(many0!(decl), multispace0));
 mod tests {
     use std::convert::TryInto;
 
+    use crate::ast::{BinaryOperator, Expr, Literal, Type};
+
     use super::*;
     use expr::tests::ident_expr;
 
@@ -106,6 +129,29 @@ mod tests {
     }
 
     #[test]
+    fn ascripted_fn_args() {
+        test_parse!(ascripted_arg, "(x : int)");
+        let res = test_parse!(decl, "fn plus1 (x : int) = x + 1");
+        assert_eq!(
+            res,
+            Decl::Fun {
+                name: "plus1".try_into().unwrap(),
+                body: Fun {
+                    args: vec![Arg {
+                        ident: "x".try_into().unwrap(),
+                        type_: Some(Type::Int),
+                    }],
+                    body: Expr::BinaryOp {
+                        lhs: ident_expr("x"),
+                        op: BinaryOperator::Add,
+                        rhs: Box::new(Expr::Literal(Literal::Int(1))),
+                    }
+                }
+            }
+        );
+    }
+
+    #[test]
     fn multiple_decls() {
         let res = test_parse!(
             toplevel,
diff --git a/src/parser/type_.rs b/src/parser/type_.rs
index 66b4f9f72c23..c90ceda4d72e 100644
--- a/src/parser/type_.rs
+++ b/src/parser/type_.rs
@@ -1,6 +1,7 @@
 use nom::character::complete::{multispace0, multispace1};
 use nom::{alt, delimited, do_parse, map, named, opt, separated_list0, tag, terminated, tuple};
 
+use super::ident;
 use crate::ast::{FunctionType, Type};
 
 named!(function_type(&str) -> Type, do_parse!(
@@ -29,6 +30,7 @@ named!(pub type_(&str) -> Type, alt!(
     tag!("bool") => { |_| Type::Bool } |
     tag!("cstring") => { |_| Type::CString } |
     function_type |
+    ident => { |id| Type::Var(id) } |
     delimited!(
         tuple!(tag!("("), multispace0),
         type_,
@@ -38,7 +40,10 @@ named!(pub type_(&str) -> Type, alt!(
 
 #[cfg(test)]
 mod tests {
+    use std::convert::TryFrom;
+
     use super::*;
+    use crate::ast::Ident;
 
     #[test]
     fn simple_types() {
@@ -103,4 +108,18 @@ mod tests {
             })
         )
     }
+
+    #[test]
+    fn type_vars() {
+        assert_eq!(
+            test_parse!(type_, "fn x, y -> x"),
+            Type::Function(FunctionType {
+                args: vec![
+                    Type::Var(Ident::try_from("x").unwrap()),
+                    Type::Var(Ident::try_from("y").unwrap()),
+                ],
+                ret: Box::new(Type::Var(Ident::try_from("x").unwrap())),
+            })
+        )
+    }
 }