Introduce lambda expressions.

5 files changed, 281 insertions, 196 deletions

diff --git a/src/chomp/typed/context.rs b/src/chomp/typed/context.rs
index f3263ce..7ac4ae0 100644
--- a/src/chomp/typed/context.rs
+++ b/src/chomp/typed/context.rs
@@ -30,16 +30,11 @@ impl Context {
             .nth_back(var.index)
             .ok_or(GetVariableError::FreeVariable)
             .and_then(|ty| {
-                self.unguard_points
-                    .last()
-                    .and_then(|point| {
-                        if point + var.index >= self.vars.len() {
-                            Some(ty)
-                        } else {
-                            None
-                        }
-                    })
-                    .ok_or(GetVariableError::GuardedVariable)
+                if self.unguard_points.last().unwrap_or(&0) + var.index >= self.vars.len() {
+                    Ok(ty)
+                } else {
+                    Err(GetVariableError::GuardedVariable)
+                }
             })
     }
 
diff --git a/src/chomp/typed/error.rs b/src/chomp/typed/error.rs
index 5c1e21e..48bfa25 100644
--- a/src/chomp/typed/error.rs
+++ b/src/chomp/typed/error.rs
@@ -5,27 +5,19 @@ use std::{
 
 use proc_macro2::Span;
 
-use crate::chomp::{ast::Variable, Name};
+use crate::chomp::{name::Name, ast::{Call, Fix, Lambda, Let, Variable}};
 
-use super::{context::GetVariableError, TypedExpression};
+use super::{Type, TypedExpression, context::GetVariableError};
 
 /// A type error when using a fix point variable.
 #[derive(Debug)]
 pub struct VariableError {
     pub inner: GetVariableError,
     pub var: Variable,
-    pub span: Option<Span>,
+    pub span: Span,
     pub name: Option<Name>,
 }
 
-impl From<VariableError> for syn::Error {
-    fn from(other: VariableError) -> Self {
-        let msg = other.to_string();
-        let span = other.span;
-        Self::new(span.unwrap_or_else(Span::call_site), msg)
-    }
-}
-
 impl Display for VariableError {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match &self.inner {
@@ -47,24 +39,20 @@ impl Error for VariableError {}
 pub enum CatError {
     FirstNullable {
         expr: TypedExpression,
-        punct: Option<Span>,
+        punct: Span,
     },
     FirstFlastOverlap {
-        first: Vec<TypedExpression>,
-        punct: Option<Span>,
+        front_ty: Type,
+        punct: Span,
         next: TypedExpression,
     },
 }
 
-impl From<CatError> for syn::Error {
-    fn from(other: CatError) -> Self {
-        let msg = other.to_string();
-        let span = match other {
-            CatError::FirstNullable { punct, .. } | CatError::FirstFlastOverlap { punct, .. } => {
-                punct
-            }
-        };
-        Self::new(span.unwrap_or_else(Span::call_site), msg)
+impl CatError {
+    pub fn span(&self) -> Span {
+        match self {
+            Self::FirstNullable { punct, .. } | Self::FirstFlastOverlap { punct, .. } => *punct,
+        }
     }
 }
 
@@ -84,24 +72,22 @@ impl Error for CatError {}
 #[derive(Debug)]
 pub enum AltError {
     BothNullable {
-        left: Vec<TypedExpression>,
-        punct: Option<Span>,
+        left_ty: Type,
+        punct: Span,
         right: TypedExpression,
     },
     FirstOverlap {
-        left: Vec<TypedExpression>,
-        punct: Option<Span>,
+        left_ty: Type,
+        punct: Span,
         right: TypedExpression,
     },
 }
 
-impl From<AltError> for syn::Error {
-    fn from(other: AltError) -> Self {
-        let msg = other.to_string();
-        let span = match other {
-            AltError::BothNullable { punct, .. } | AltError::FirstOverlap { punct, .. } => punct,
-        };
-        Self::new(span.unwrap_or_else(Span::call_site), msg)
+impl AltError {
+    pub fn span(&self) -> Span {
+        match self {
+            Self::BothNullable { punct, .. } | Self::FirstOverlap { punct, .. } => *punct,
+        }
     }
 }
 
@@ -121,6 +107,24 @@ pub enum TypeError {
     Cat(CatError),
     Alt(AltError),
     Variable(VariableError),
+    UnexpectedCall { span: Span, call: Call },
+    UnexpectedLambda { span: Span, lambda: Lambda },
+    UnexpectedLet { span: Span, stmt: Let },
+    ExpectedLambda {span: Span, fix: Fix },
+}
+
+impl TypeError {
+    pub fn span(&self) -> Span {
+        match self {
+            TypeError::Cat(c) => c.span(),
+            TypeError::Alt(a) => a.span(),
+            TypeError::Variable(v) => v.span,
+            TypeError::UnexpectedCall { span, .. }
+            | TypeError::UnexpectedLambda { span, .. }
+            | TypeError::UnexpectedLet { span, .. }
+            | TypeError::ExpectedLambda { span, .. } => *span,
+        }
+    }
 }
 
 impl From<CatError> for TypeError {
@@ -143,11 +147,9 @@ impl From<VariableError> for TypeError {
 
 impl From<TypeError> for syn::Error {
     fn from(other: TypeError) -> Self {
-        match other {
-            TypeError::Cat(e) => e.into(),
-            TypeError::Alt(e) => e.into(),
-            TypeError::Variable(e) => e.into(),
-        }
+        let span = other.span();
+        let msg = format!("{}", other);
+        Self::new(span, msg)
     }
 }
 
@@ -157,6 +159,19 @@ impl Display for TypeError {
             Self::Cat(e) => e.fmt(f),
             Self::Alt(e) => e.fmt(f),
             Self::Variable(e) => e.fmt(f),
+
+            Self::UnexpectedCall { .. } => {
+                write!(f, "unexpected call")
+            }
+            Self::UnexpectedLambda { .. } => {
+                write!(f, "unexpected lambda")
+            }
+            Self::UnexpectedLet { .. } => {
+                write!(f, "unexpected let")
+            }
+            Self::ExpectedLambda { .. } => {
+                write!(f, "expected a lambda expression")
+            }
         }
     }
 }
diff --git a/src/chomp/typed/infer.rs b/src/chomp/typed/infer.rs
index e2c2198..bc2baea 100644
--- a/src/chomp/typed/infer.rs
+++ b/src/chomp/typed/infer.rs
@@ -1,8 +1,18 @@
+use std::{array, iter};
+
 use proc_macro2::Span;
 
-use crate::chomp::{Name, ast::{Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, substitute::Translate}, visit::{Folder, Visitable}};
+use crate::chomp::{
+    ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Let, Literal, Variable},
+    name::Name,
+    visit::{Folder, Visitable},
+};
 
-use super::{Type, Typed, TypedExpression, context::Context, error::{TypeError, VariableError}};
+use super::{
+    context::Context,
+    error::{AltError, CatError, TypeError, VariableError},
+    Type, Typed, TypedExpression,
+};
 
 #[derive(Debug)]
 pub struct TypeInfer<'a> {
@@ -12,7 +22,7 @@ pub struct TypeInfer<'a> {
 impl Folder for TypeInfer<'_> {
     type Out = Result<TypedExpression, TypeError>;
 
-    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out {
         Ok(TypedExpression {
             inner: super::Epsilon::from(eps).into(),
             name,
@@ -20,7 +30,7 @@ impl Folder for TypeInfer<'_> {
         })
     }
 
-    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+    fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out {
         Ok(TypedExpression {
             inner: super::Literal::from(lit).into(),
             name,
@@ -28,47 +38,99 @@ impl Folder for TypeInfer<'_> {
         })
     }
 
-    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+    fn fold_cat(&mut self, name: Option<Name>, span: Span, cat: Cat) -> Self::Out {
         let first = cat.first.fold(self)?;
+
+        if first.get_type().nullable() {
+            let punct = cat.rest.into_iter().next().map(|(p, _)| p).unwrap_or_else(Span::call_site);
+            return Err(CatError::FirstNullable { expr: first, punct }.into());
+        }
+
         let rest = cat.rest;
-        self.context
-            .with_unguard(|context| -> Result<TypedExpression, TypeError> {
-                let mut infer = TypeInfer { context };
-                let rest = rest
-                    .into_iter()
-                    .map(|(punct, term)| -> Result<_, TypeError> {
-                        Ok((punct, term.fold(&mut infer)?))
-                    })
-                    .collect::<Result<Vec<_>, _>>()?;
-                Ok(TypedExpression {
-                    inner: super::Cat::new(first, rest)?.into(),
-                    name,
-                    span,
+        let mut ty = first.get_type().clone();
+        let terms = self.context.with_unguard(|context| {
+            let mut infer = TypeInfer { context };
+            rest.into_iter()
+                .map(|(punct, right)| {
+                    let right = right.fold(&mut infer)?;
+                    if ty.flast_set().disjoint(right.get_type().first_set()) {
+                        ty.cat(right.get_type().clone());
+                        Ok(right)
+                    } else {
+                        Err(CatError::FirstFlastOverlap {
+                            front_ty: ty.clone(),
+                            punct,
+                            next: right,
+                        }
+                        .into())
+                    }
                 })
-            })
+                .collect::<Result<Vec<_>, TypeError>>()
+        })?;
+        Ok(TypedExpression {
+            inner: super::Cat {
+                terms: iter::once(first).chain(terms).collect(),
+                ty,
+            }
+            .into(),
+            name,
+            span,
+        })
     }
 
-    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+    fn fold_alt(&mut self, name: Option<Name>, span: Span, alt: Alt) -> Self::Out {
         let first = alt.first.fold(self)?;
-        let rest = alt
+        let mut ty = first.get_type().clone();
+        let terms = alt
             .rest
             .into_iter()
-            .map(|(punct, term)| -> Result<_, TypeError> { Ok((punct, term.fold(self)?)) })
-            .collect::<Result<Vec<_>, _>>()?;
+            .map(|(punct, right)| {
+                let right = right.fold(self)?;
+                if ty.nullable() && right.get_type().nullable() {
+                    Err(AltError::BothNullable {
+                        left_ty: ty.clone(),
+                        punct,
+                        right,
+                    }
+                    .into())
+                } else if ty.first_set().disjoint(right.get_type().first_set()) {
+                    ty.alt(right.get_type().clone());
+                    Ok(right)
+                } else {
+                    Err(AltError::FirstOverlap {
+                        left_ty: ty.clone(),
+                        punct,
+                        right,
+                    }
+                    .into())
+                }
+            })
+            .collect::<Result<Vec<_>, TypeError>>()?;
         Ok(TypedExpression {
-            inner: super::Alt::new(first, rest)?.into(),
+            inner: super::Alt {
+                terms: iter::once(first).chain(terms).collect(),
+                ty,
+            }
+            .into(),
             name,
             span,
         })
     }
 
-    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+    fn fold_fix(&mut self, name: Option<Name>, span: Span, fix: Fix) -> Self::Out {
         let mut ty = Type::default();
+        let body = if let Expression::Lambda(l) = fix.inner.expr {
+            let mut body = *l.inner;
+            body.name = Name::merge_all(array::IntoIter::new([fix.inner.name, body.name, name.clone()]));
+            body
+        } else {
+            return Err(TypeError::ExpectedLambda { span, fix });
+        };
 
         loop {
             let last = ty;
             let res = self.context.with_variable_type(last.clone(), |context| {
-                fix.inner.clone().fold(&mut TypeInfer { context })
+                body.clone().fold(&mut TypeInfer { context })
             })?;
             ty = res.get_type().clone();
 
@@ -88,7 +150,7 @@ impl Folder for TypeInfer<'_> {
     fn fold_variable(
         &mut self,
         name: Option<Name>,
-        span: Option<Span>,
+        span: Span,
         var: Variable,
     ) -> Self::Out {
         let ty = match self.context.get_variable_type(var) {
@@ -110,18 +172,101 @@ impl Folder for TypeInfer<'_> {
         })
     }
 
-    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out {
-        let translated = NamedExpression { name, expr: call.into(), span}.fold(&mut Translate::new())?;
-        let inner = translated.fold(self)?;
-        todo!()
+    fn fold_call(&mut self, _name: Option<Name>, span: Span, call: Call) -> Self::Out {
+        Err(TypeError::UnexpectedCall { span, call })
     }
 
     fn fold_lambda(
         &mut self,
         _name: Option<Name>,
-        _span: Option<Span>,
-        _lambda: Lambda,
+        span: Span,
+        lambda: Lambda,
     ) -> Self::Out {
-        unimplemented!()
+        Err(TypeError::UnexpectedLambda { span, lambda })
+    }
+
+    fn fold_let(&mut self, _name: Option<Name>, span: Span, stmt: Let) -> Self::Out {
+        Err(TypeError::UnexpectedLet { span, stmt })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::chomp::{ast::NamedExpression, typed::RawTypedExpression};
+
+    use super::*;
+
+    #[test]
+    fn cat_uses_all() {
+        let ast = Cat {
+            first: Box::new(NamedExpression {
+                name: None,
+                expr: "a".to_owned().into(),
+                span: Span::call_site(),
+            }),
+            rest: vec![(
+                Span::call_site(),
+                NamedExpression {
+                    name: None,
+                    expr: "b".to_owned().into(),
+                    span: Span::call_site(),
+                },
+            )],
+        };
+
+        let typed = NamedExpression {
+            name: None,
+            expr: ast.into(),
+            span: Span::call_site(),
+        }
+        .fold(&mut TypeInfer {
+            context: &mut Context::default(),
+        })
+        .unwrap();
+        match typed.inner {
+            RawTypedExpression::Cat(super::super::Cat { terms, .. }) => assert_eq!(terms.len(), 2),
+            RawTypedExpression::Epsilon(_)
+            | RawTypedExpression::Literal(_)
+            | RawTypedExpression::Alt(_)
+            | RawTypedExpression::Fix(_)
+            | RawTypedExpression::Variable(_) => panic!("Cat should type check to Cat"),
+        };
+    }
+
+    #[test]
+    fn alt_uses_all() {
+        let ast = Alt {
+            first: Box::new(NamedExpression {
+                name: None,
+                expr: "a".to_owned().into(),
+                span: Span::call_site(),
+            }),
+            rest: vec![(
+                Span::call_site(),
+                NamedExpression {
+                    name: None,
+                    expr: "b".to_owned().into(),
+                    span: Span::call_site(),
+                },
+            )],
+        };
+
+        let typed = NamedExpression {
+            name: None,
+            expr: ast.into(),
+            span: Span::call_site(),
+        }
+        .fold(&mut TypeInfer {
+            context: &mut Context::default(),
+        })
+        .unwrap();
+        match typed.inner {
+            RawTypedExpression::Alt(super::super::Alt { terms, .. }) => assert_eq!(terms.len(), 2),
+            RawTypedExpression::Epsilon(_)
+            | RawTypedExpression::Literal(_)
+            | RawTypedExpression::Cat(_)
+            | RawTypedExpression::Fix(_)
+            | RawTypedExpression::Variable(_) => panic!("Alt should type check to Alt"),
+        };
     }
 }
diff --git a/src/chomp/typed/lower.rs b/src/chomp/typed/lower.rs
index 37589a1..03237de 100644
--- a/src/chomp/typed/lower.rs
+++ b/src/chomp/typed/lower.rs
@@ -1,6 +1,6 @@
 use proc_macro2::Span;
 
-use crate::chomp::Name;
+use crate::chomp::name::Name;
 
 use super::{Alt, Cat, Epsilon, Fix, Literal, RawTypedExpression, TypedExpression, Variable};
 
@@ -8,19 +8,19 @@ pub trait Backend: Default {
     type Id;
     type Code;
 
-    fn gen_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Id;
+    fn gen_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Id;
 
-    fn gen_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Id;
+    fn gen_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Id;
 
-    fn gen_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Id;
+    fn gen_cat(&mut self, name: Option<Name>, span: Span, cat: Cat) -> Self::Id;
 
-    fn gen_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Id;
+    fn gen_alt(&mut self, name: Option<Name>, span: Span, alt: Alt) -> Self::Id;
 
-    fn gen_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Id;
+    fn gen_fix(&mut self, name: Option<Name>, span: Span, fix: Fix) -> Self::Id;
 
-    fn gen_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable) -> Self::Id;
+    fn gen_variable(&mut self, name: Option<Name>, span: Span, var: Variable) -> Self::Id;
 
-    fn emit_code(self, name: Option<Name>, span: Option<Span>, id: Self::Id) -> Self::Code;
+    fn emit_code(self, name: Option<Name>, span: Span, id: Self::Id) -> Self::Code;
 }
 
 pub trait GenerateCode {
diff --git a/src/chomp/typed/mod.rs b/src/chomp/typed/mod.rs
index cddb05a..f1f6967 100644
--- a/src/chomp/typed/mod.rs
+++ b/src/chomp/typed/mod.rs
@@ -5,7 +5,7 @@ use proc_macro2::Span;
 use super::{
     ast,
     set::{FirstSet, FlastSet},
-    Name,
+    name::Name,
 };
 
 pub mod context;
@@ -14,7 +14,6 @@ pub mod lower;
 
 mod infer;
 
-use self::error::{AltError, CatError};
 pub use self::infer::TypeInfer;
 
 #[derive(Debug, Default, Clone, Eq, Hash, PartialEq)]
@@ -53,28 +52,25 @@ impl Type {
         &self.flast_set
     }
 
-    pub fn cat(self, other: Self) -> Self {
-        Self {
-            nullable: self.nullable && other.nullable,
-            first_set: self.first_set.union(if self.nullable {
-                other.first_set.clone()
-            } else {
-                FirstSet::default()
-            }),
-            flast_set: other.flast_set.union(if other.nullable {
-                self.flast_set.union_first(other.first_set)
-            } else {
-                FlastSet::default()
-            }),
+    pub fn cat(&mut self, other: Self) {
+        if self.nullable {
+            self.first_set.union(other.first_set.clone())
         }
-    }
 
-    pub fn alt(self, other: Self) -> Self {
-        Self {
-            nullable: self.nullable || other.nullable,
-            first_set: self.first_set.union(other.first_set),
-            flast_set: self.flast_set.union(other.flast_set),
+        if other.nullable {
+            self.flast_set.union_first(other.first_set);
+            self.flast_set.union(other.flast_set);
+        } else {
+            self.flast_set = other.flast_set;
         }
+
+        self.nullable &= other.nullable;
+    }
+
+    pub fn alt(&mut self, other: Self) {
+        self.nullable |= other.nullable;
+        self.first_set.union(other.first_set);
+        self.flast_set.union(other.flast_set);
     }
 }
 
@@ -122,43 +118,6 @@ pub struct Cat {
     ty: Type,
 }
 
-impl Cat {
-    fn new<I: IntoIterator<Item = (Option<Span>, TypedExpression)>>(
-        first: TypedExpression,
-        rest: I,
-    ) -> Result<Self, CatError> {
-        if first.get_type().nullable() {
-            return Err(CatError::FirstNullable {
-                expr: first,
-                punct: todo!(),
-            });
-        }
-
-        rest.into_iter()
-            .try_fold(
-                (first.get_type().clone(), vec![first]),
-                |(ty, mut terms), (punct, right)| {
-                    if ty
-                        .flast_set()
-                        .intersect_first(right.get_type().first_set())
-                        .is_empty()
-                    {
-                        let ty = ty.cat(right.get_type().clone());
-                        terms.push(right);
-                        Ok((ty, terms))
-                    } else {
-                        Err(CatError::FirstFlastOverlap {
-                            first: terms,
-                            punct,
-                            next: right,
-                        })
-                    }
-                },
-            )
-            .map(|(ty, terms)| Self { ty, terms })
-    }
-}
-
 impl IntoIterator for Cat {
     type Item = TypedExpression;
 
@@ -175,42 +134,6 @@ pub struct Alt {
     ty: Type,
 }
 
-impl Alt {
-    pub fn new<I: IntoIterator<Item = (Option<Span>, TypedExpression)>>(
-        first: TypedExpression,
-        rest: I,
-    ) -> Result<Self, AltError> {
-        rest.into_iter()
-            .try_fold(
-                (first.get_type().clone(), vec![first]),
-                |(ty, mut terms), (punct, right)| {
-                    if ty.nullable() && right.get_type().nullable() {
-                        Err(AltError::BothNullable {
-                            left: terms,
-                            punct,
-                            right,
-                        })
-                    } else if ty
-                        .first_set()
-                        .intersect(right.get_type().first_set())
-                        .is_empty()
-                    {
-                        let ty = ty.alt(right.get_type().clone());
-                        terms.push(right);
-                        Ok((ty, terms))
-                    } else {
-                        Err(AltError::FirstOverlap {
-                            left: terms,
-                            punct,
-                            right,
-                        })
-                    }
-                },
-            )
-            .map(|(ty, terms)| Self { ty, terms })
-    }
-}
-
 impl IntoIterator for Alt {
     type Item = TypedExpression;
 
@@ -245,14 +168,6 @@ impl Variable {
 }
 
 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
-pub struct Call {
-    ty: Type,
-}
-
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
-pub struct Lambda {}
-
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
 enum RawTypedExpression {
     Epsilon(Epsilon),
     Literal(Literal),
@@ -260,8 +175,6 @@ enum RawTypedExpression {
     Alt(Alt),
     Fix(Fix),
     Variable(Variable),
-    Call(Call),
-    Lambda(Lambda),
 }
 
 impl From<Epsilon> for RawTypedExpression {
@@ -304,7 +217,7 @@ impl From<Variable> for RawTypedExpression {
 pub struct TypedExpression {
     inner: RawTypedExpression,
     pub name: Option<Name>,
-    pub span: Option<Span>,
+    pub span: Span,
 }
 
 impl PartialEq for TypedExpression {
@@ -360,3 +273,20 @@ impl Typed for TypedExpression {
         }
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn cat_right() {
+        let epsilon = Type { nullable: true, ..Type::default()};
+        let mut x = Type::of_str("a");
+        x.cat(Type::of_str("b"));
+        assert_eq!(x, Type::of_str("a"));
+        x.cat(Type::default());
+        assert_eq!(x, Type::of_str("a"));
+        x.cat(epsilon);
+        assert_eq!(x, Type::of_str("a"));
+    }
+}