feat(grfn/achilles): Implement tuples, and tuple patterns r/2522

Implement tuple expressions, types, and patterns, all the way through
the parser down to the typechecker. In LLVM, these are implemented as
anonymous structs, using an `extract` instruction when they're pattern
matched on to get out the individual fields.

Currently the only limitation here is patterns aren't supported in
function argument position, but you can still do something like

    fn xy = let (x, y) = xy in x + y

Change-Id: I357f17e9d4052e741eda8605b6662822f331efde
Reviewed-on: https://cl.tvl.fyi/c/depot/+/3027
Reviewed-by: grfn <grfn@gws.fyi>
Tested-by: BuildkiteCI

4 files changed, 123 insertions, 16 deletions

diff --git a/users/grfn/achilles/src/parser/expr.rs b/users/grfn/achilles/src/parser/expr.rs
index 8a28d00984c9..f596b18970aa 100644
--- a/users/grfn/achilles/src/parser/expr.rs
+++ b/users/grfn/achilles/src/parser/expr.rs
@@ -8,7 +8,8 @@ use nom::{
 };
 use pratt::{Affix, Associativity, PrattParser, Precedence};
 
-use crate::ast::{BinaryOperator, Binding, Expr, Fun, Literal, UnaryOperator};
+use super::util::comma;
+use crate::ast::{BinaryOperator, Binding, Expr, Fun, Literal, Pattern, UnaryOperator};
 use crate::parser::{arg, ident, type_};
 
 #[derive(Debug)]
@@ -192,9 +193,45 @@ named!(literal(&str) -> Literal, alt!(int | bool_ | string | unit));
 
 named!(literal_expr(&str) -> Expr, map!(literal, Expr::Literal));
 
+named!(tuple(&str) -> Expr, do_parse!(
+    complete!(tag!("("))
+        >> multispace0
+        >> fst: expr
+        >> comma
+        >> rest: separated_list0!(
+            comma,
+            expr
+        )
+        >> multispace0
+        >> tag!(")")
+        >> ({
+            let mut members = Vec::with_capacity(rest.len() + 1);
+            members.push(fst);
+            members.append(&mut rest.clone());
+            Expr::Tuple(members)
+        })
+));
+
+named!(tuple_pattern(&str) -> Pattern, do_parse!(
+    complete!(tag!("("))
+        >> multispace0
+        >> pats: separated_list0!(
+            comma,
+            pattern
+        )
+        >> multispace0
+        >> tag!(")")
+        >> (Pattern::Tuple(pats))
+));
+
+named!(pattern(&str) -> Pattern, alt!(
+    ident => { |id| Pattern::Id(id) } |
+    tuple_pattern
+));
+
 named!(binding(&str) -> Binding, do_parse!(
     multispace0
-        >> ident: ident
+        >> pat: pattern
         >> multispace0
         >> type_: opt!(preceded!(tuple!(tag!(":"), multispace0), type_))
         >> multispace0
@@ -202,7 +239,7 @@ named!(binding(&str) -> Binding, do_parse!(
         >> multispace0
         >> body: expr
         >> (Binding {
-            ident,
+            pat,
             type_,
             body
         })
@@ -267,6 +304,7 @@ named!(paren_expr(&str) -> Expr,
 
 named!(funcref(&str) -> Expr, alt!(
     ident_expr |
+    tuple |
     paren_expr
 ));
 
@@ -296,6 +334,7 @@ named!(fun_expr(&str) -> Expr, do_parse!(
 named!(fn_arg(&str) -> Expr, alt!(
     ident_expr |
     literal_expr |
+    tuple |
     paren_expr
 ));
 
@@ -314,7 +353,8 @@ named!(simple_expr_unascripted(&str) -> Expr, alt!(
     if_ |
     fun_expr |
     literal_expr |
-    ident_expr
+    ident_expr |
+    tuple
 ));
 
 named!(simple_expr(&str) -> Expr, alt!(
@@ -334,7 +374,7 @@ named!(pub expr(&str) -> Expr, alt!(
 #[cfg(test)]
 pub(crate) mod tests {
     use super::*;
-    use crate::ast::{Arg, Ident, Type};
+    use crate::ast::{Arg, Ident, Pattern, Type};
     use std::convert::TryFrom;
     use BinaryOperator::*;
     use Expr::{BinaryOp, If, Let, UnaryOp};
@@ -450,6 +490,17 @@ pub(crate) mod tests {
     }
 
     #[test]
+    fn tuple() {
+        assert_eq!(
+            test_parse!(expr, "(1, \"seven\")"),
+            Expr::Tuple(vec![
+                Expr::Literal(Literal::Int(1)),
+                Expr::Literal(Literal::String(Cow::Borrowed("seven")))
+            ])
+        )
+    }
+
+    #[test]
     fn simple_string_lit() {
         assert_eq!(
             test_parse!(expr, "\"foobar\""),
@@ -465,12 +516,12 @@ pub(crate) mod tests {
             Let {
                 bindings: vec![
                     Binding {
-                        ident: Ident::try_from("x").unwrap(),
+                        pat: Pattern::Id(Ident::try_from("x").unwrap()),
                         type_: None,
                         body: Expr::Literal(Literal::Int(1))
                     },
                     Binding {
-                        ident: Ident::try_from("y").unwrap(),
+                        pat: Pattern::Id(Ident::try_from("y").unwrap()),
                         type_: None,
                         body: Expr::BinaryOp {
                             lhs: ident_expr("x"),
@@ -553,7 +604,7 @@ pub(crate) mod tests {
             Expr::Call {
                 fun: Box::new(Expr::Let {
                     bindings: vec![Binding {
-                        ident: Ident::try_from("x").unwrap(),
+                        pat: Pattern::Id(Ident::try_from("x").unwrap()),
                         type_: None,
                         body: Expr::Literal(Literal::Int(1))
                     }],
@@ -571,7 +622,7 @@ pub(crate) mod tests {
             res,
             Expr::Let {
                 bindings: vec![Binding {
-                    ident: Ident::try_from("id").unwrap(),
+                    pat: Pattern::Id(Ident::try_from("id").unwrap()),
                     type_: None,
                     body: Expr::Fun(Box::new(Fun {
                         args: vec![Arg::try_from("x").unwrap()],
@@ -586,6 +637,28 @@ pub(crate) mod tests {
         );
     }
 
+    #[test]
+    fn tuple_binding() {
+        let res = test_parse!(expr, "let (x, y) = (1, 2) in x");
+        assert_eq!(
+            res,
+            Expr::Let {
+                bindings: vec![Binding {
+                    pat: Pattern::Tuple(vec![
+                        Pattern::Id(Ident::from_str_unchecked("x")),
+                        Pattern::Id(Ident::from_str_unchecked("y"))
+                    ]),
+                    body: Expr::Tuple(vec![
+                        Expr::Literal(Literal::Int(1)),
+                        Expr::Literal(Literal::Int(2))
+                    ]),
+                    type_: None
+                }],
+                body: Box::new(Expr::Ident(Ident::from_str_unchecked("x")))
+            }
+        )
+    }
+
     mod ascriptions {
         use super::*;
 
@@ -608,7 +681,7 @@ pub(crate) mod tests {
                 res,
                 Expr::Let {
                     bindings: vec![Binding {
-                        ident: Ident::try_from("const_1").unwrap(),
+                        pat: Pattern::Id(Ident::try_from("const_1").unwrap()),
                         type_: None,
                         body: Expr::Fun(Box::new(Fun {
                             args: vec![Arg::try_from("x").unwrap()],
@@ -633,7 +706,7 @@ pub(crate) mod tests {
                 res,
                 Expr::Let {
                     bindings: vec![Binding {
-                        ident: Ident::try_from("x").unwrap(),
+                        pat: Pattern::Id(Ident::try_from("x").unwrap()),
                         type_: Some(Type::Int),
                         body: Expr::Literal(Literal::Int(1))
                     }],
diff --git a/users/grfn/achilles/src/parser/mod.rs b/users/grfn/achilles/src/parser/mod.rs
index 3e0081bd391d..e088cbca10a5 100644
--- a/users/grfn/achilles/src/parser/mod.rs
+++ b/users/grfn/achilles/src/parser/mod.rs
@@ -6,6 +6,7 @@ use nom::{alt, char, complete, do_parse, eof, many0, named, separated_list0, tag
 pub(crate) mod macros;
 mod expr;
 mod type_;
+mod util;
 
 use crate::ast::{Arg, Decl, Fun, Ident};
 pub use expr::expr;
diff --git a/users/grfn/achilles/src/parser/type_.rs b/users/grfn/achilles/src/parser/type_.rs
index 8a1081e2521f..b80f0e0860a1 100644
--- a/users/grfn/achilles/src/parser/type_.rs
+++ b/users/grfn/achilles/src/parser/type_.rs
@@ -2,17 +2,14 @@ use nom::character::complete::{multispace0, multispace1};
 use nom::{alt, delimited, do_parse, map, named, opt, separated_list0, tag, terminated, tuple};
 
 use super::ident;
+use super::util::comma;
 use crate::ast::{FunctionType, Type};
 
 named!(pub function_type(&str) -> FunctionType, do_parse!(
     tag!("fn")
         >> multispace1
         >> args: map!(opt!(terminated!(separated_list0!(
-            tuple!(
-                multispace0,
-                tag!(","),
-                multispace0
-            ),
+            comma,
             type_
         ), multispace1)), |args| args.unwrap_or_default())
         >> tag!("->")
@@ -24,12 +21,32 @@ named!(pub function_type(&str) -> FunctionType, do_parse!(
         })
 ));
 
+named!(tuple_type(&str) -> Type, do_parse!(
+    tag!("(")
+        >> multispace0
+        >> fst: type_
+        >> comma
+        >> rest: separated_list0!(
+            comma,
+            type_
+        )
+        >> multispace0
+        >> tag!(")")
+        >> ({
+            let mut members = Vec::with_capacity(rest.len() + 1);
+            members.push(fst);
+            members.append(&mut rest.clone());
+            Type::Tuple(members)
+        })
+));
+
 named!(pub type_(&str) -> Type, alt!(
     tag!("int") => { |_| Type::Int } |
     tag!("float") => { |_| Type::Float } |
     tag!("bool") => { |_| Type::Bool } |
     tag!("cstring") => { |_| Type::CString } |
     tag!("()") => { |_| Type::Unit } |
+    tuple_type |
     function_type => { |ft| Type::Function(ft) }|
     ident => { |id| Type::Var(id) } |
     delimited!(
@@ -112,6 +129,14 @@ mod tests {
     }
 
     #[test]
+    fn tuple() {
+        assert_eq!(
+            test_parse!(type_, "(int, int)"),
+            Type::Tuple(vec![Type::Int, Type::Int])
+        )
+    }
+
+    #[test]
     fn type_vars() {
         assert_eq!(
             test_parse!(type_, "fn x, y -> x"),
diff --git a/users/grfn/achilles/src/parser/util.rs b/users/grfn/achilles/src/parser/util.rs
new file mode 100644
index 000000000000..bb53fb7fff50
--- /dev/null
+++ b/users/grfn/achilles/src/parser/util.rs
@@ -0,0 +1,8 @@
+use nom::character::complete::multispace0;
+use nom::{complete, map, named, tag, tuple};
+
+named!(pub(crate) comma(&str) -> (), map!(tuple!(
+    multispace0,
+    complete!(tag!(",")),
+    multispace0
+) ,|_| ()));