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

2 files changed, 90 insertions, 9 deletions

diff --git a/users/grfn/achilles/src/ast/hir.rs b/users/grfn/achilles/src/ast/hir.rs
index 0d145d620bef..cdfaef567d7a 100644
--- a/users/grfn/achilles/src/ast/hir.rs
+++ b/users/grfn/achilles/src/ast/hir.rs
@@ -5,9 +5,42 @@ use itertools::Itertools;
 use super::{BinaryOperator, Ident, Literal, UnaryOperator};
 
 #[derive(Debug, PartialEq, Eq, Clone)]
+pub enum Pattern<'a, T> {
+    Id(Ident<'a>, T),
+    Tuple(Vec<Pattern<'a, T>>),
+}
+
+impl<'a, T> Pattern<'a, T> {
+    pub fn to_owned(&self) -> Pattern<'static, T>
+    where
+        T: Clone,
+    {
+        match self {
+            Pattern::Id(id, t) => Pattern::Id(id.to_owned(), t.clone()),
+            Pattern::Tuple(pats) => {
+                Pattern::Tuple(pats.into_iter().map(Pattern::to_owned).collect())
+            }
+        }
+    }
+
+    pub fn traverse_type<F, U, E>(self, f: F) -> Result<Pattern<'a, U>, E>
+    where
+        F: Fn(T) -> Result<U, E> + Clone,
+    {
+        match self {
+            Pattern::Id(id, t) => Ok(Pattern::Id(id, f(t)?)),
+            Pattern::Tuple(pats) => Ok(Pattern::Tuple(
+                pats.into_iter()
+                    .map(|pat| pat.traverse_type(f.clone()))
+                    .collect::<Result<Vec<_>, _>>()?,
+            )),
+        }
+    }
+}
+
+#[derive(Debug, PartialEq, Eq, Clone)]
 pub struct Binding<'a, T> {
-    pub ident: Ident<'a>,
-    pub type_: T,
+    pub pat: Pattern<'a, T>,
     pub body: Expr<'a, T>,
 }
 
@@ -17,8 +50,7 @@ impl<'a, T> Binding<'a, T> {
         T: Clone,
     {
         Binding {
-            ident: self.ident.to_owned(),
-            type_: self.type_.clone(),
+            pat: self.pat.to_owned(),
             body: self.body.to_owned(),
         }
     }
@@ -30,6 +62,8 @@ pub enum Expr<'a, T> {
 
     Literal(Literal<'a>, T),
 
+    Tuple(Vec<Expr<'a, T>>, T),
+
     UnaryOp {
         op: UnaryOperator,
         rhs: Box<Expr<'a, T>>,
@@ -76,6 +110,7 @@ impl<'a, T> Expr<'a, T> {
         match self {
             Expr::Ident(_, t) => t,
             Expr::Literal(_, t) => t,
+            Expr::Tuple(_, t) => t,
             Expr::UnaryOp { type_, .. } => type_,
             Expr::BinaryOp { type_, .. } => type_,
             Expr::Let { type_, .. } => type_,
@@ -115,10 +150,9 @@ impl<'a, T> Expr<'a, T> {
             } => Ok(Expr::Let {
                 bindings: bindings
                     .into_iter()
-                    .map(|Binding { ident, type_, body }| {
+                    .map(|Binding { pat, body }| {
                         Ok(Binding {
-                            ident,
-                            type_: f(type_)?,
+                            pat: pat.traverse_type(f.clone())?,
                             body: body.traverse_type(f.clone())?,
                         })
                     })
@@ -168,6 +202,13 @@ impl<'a, T> Expr<'a, T> {
                     .collect::<Result<Vec<_>, E>>()?,
                 type_: f(type_)?,
             }),
+            Expr::Tuple(members, t) => Ok(Expr::Tuple(
+                members
+                    .into_iter()
+                    .map(|t| t.traverse_type(f.clone()))
+                    .try_collect()?,
+                f(t)?,
+            )),
         }
     }
 
@@ -242,6 +283,9 @@ impl<'a, T> Expr<'a, T> {
                 args: args.iter().map(|e| e.to_owned()).collect(),
                 type_: type_.clone(),
             },
+            Expr::Tuple(members, t) => {
+                Expr::Tuple(members.into_iter().map(Expr::to_owned).collect(), t.clone())
+            }
         }
     }
 }
diff --git a/users/grfn/achilles/src/ast/mod.rs b/users/grfn/achilles/src/ast/mod.rs
index 7dc2de895709..5438d29d2cf7 100644
--- a/users/grfn/achilles/src/ast/mod.rs
+++ b/users/grfn/achilles/src/ast/mod.rs
@@ -128,8 +128,23 @@ impl<'a> Literal<'a> {
 }
 
 #[derive(Debug, PartialEq, Eq, Clone)]
+pub enum Pattern<'a> {
+    Id(Ident<'a>),
+    Tuple(Vec<Pattern<'a>>),
+}
+
+impl<'a> Pattern<'a> {
+    pub fn to_owned(&self) -> Pattern<'static> {
+        match self {
+            Pattern::Id(id) => Pattern::Id(id.to_owned()),
+            Pattern::Tuple(pats) => Pattern::Tuple(pats.iter().map(Pattern::to_owned).collect()),
+        }
+    }
+}
+
+#[derive(Debug, PartialEq, Eq, Clone)]
 pub struct Binding<'a> {
-    pub ident: Ident<'a>,
+    pub pat: Pattern<'a>,
     pub type_: Option<Type<'a>>,
     pub body: Expr<'a>,
 }
@@ -137,7 +152,7 @@ pub struct Binding<'a> {
 impl<'a> Binding<'a> {
     fn to_owned(&self) -> Binding<'static> {
         Binding {
-            ident: self.ident.to_owned(),
+            pat: self.pat.to_owned(),
             type_: self.type_.as_ref().map(|t| t.to_owned()),
             body: self.body.to_owned(),
         }
@@ -179,6 +194,8 @@ pub enum Expr<'a> {
         args: Vec<Expr<'a>>,
     },
 
+    Tuple(Vec<Expr<'a>>),
+
     Ascription {
         expr: Box<Expr<'a>>,
         type_: Type<'a>,
@@ -190,6 +207,9 @@ impl<'a> Expr<'a> {
         match self {
             Expr::Ident(ref id) => Expr::Ident(id.to_owned()),
             Expr::Literal(ref lit) => Expr::Literal(lit.to_owned()),
+            Expr::Tuple(ref members) => {
+                Expr::Tuple(members.into_iter().map(Expr::to_owned).collect())
+            }
             Expr::UnaryOp { op, rhs } => Expr::UnaryOp {
                 op: *op,
                 rhs: Box::new((**rhs).to_owned()),
@@ -312,6 +332,7 @@ pub enum Type<'a> {
     Bool,
     CString,
     Unit,
+    Tuple(Vec<Type<'a>>),
     Var(Ident<'a>),
     Function(FunctionType<'a>),
 }
@@ -326,6 +347,7 @@ impl<'a> Type<'a> {
             Type::Unit => Type::Unit,
             Type::Var(v) => Type::Var(v.to_owned()),
             Type::Function(f) => Type::Function(f.to_owned()),
+            Type::Tuple(members) => Type::Tuple(members.iter().map(Type::to_owned).collect()),
         }
     }
 
@@ -379,9 +401,23 @@ impl<'a> Type<'a> {
             Type::Float => Type::Float,
             Type::Bool => Type::Bool,
             Type::CString => Type::CString,
+            Type::Tuple(members) => Type::Tuple(
+                members
+                    .into_iter()
+                    .map(|t| t.traverse_type_vars(f.clone()))
+                    .collect(),
+            ),
             Type::Unit => Type::Unit,
         }
     }
+
+    pub fn as_tuple(&self) -> Option<&Vec<Type<'a>>> {
+        if let Self::Tuple(v) = self {
+            Some(v)
+        } else {
+            None
+        }
+    }
 }
 
 impl<'a> Display for Type<'a> {
@@ -394,6 +430,7 @@ impl<'a> Display for Type<'a> {
             Type::Unit => f.write_str("()"),
             Type::Var(v) => v.fmt(f),
             Type::Function(ft) => ft.fmt(f),
+            Type::Tuple(ms) => write!(f, "({})", ms.iter().join(", ")),
         }
     }
 }