Introduce function types.

Function types are just functions from types to check-results. Nothing more than
delayed computation. Efficiency will initially be no better than current.
Caching results could help, but that's a future problem.

An alternative approach is introducing constraints. That would be a bigger
architectural change, with more complex processing. On the other hand, adding
future extensions would be easier.

6 files changed, 155 insertions, 74 deletions

diff --git a/Cargo.toml b/Cargo.toml
index 0d48eb1..7e2197b 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -9,6 +9,7 @@ members = ["autochomp", "chewed", "chomp-bench", "chomp-macro"]
 
 [dependencies]
 heck = "0.3.2"
+once_cell = "1.7.2"
 proc-macro2 = "1.0.24"
 quote = "1.0.8"
 syn = "1.0.58"
diff --git a/src/chomp/typed/context.rs b/src/chomp/typed/context.rs
index f3263ce..aaf01a7 100644
--- a/src/chomp/typed/context.rs
+++ b/src/chomp/typed/context.rs
@@ -1,8 +1,8 @@
 use crate::chomp::ast::Variable;
 
-use super::Type;
+use super::{GroundType, Type};
 
-#[derive(Debug, Default)]
+#[derive(Default)]
 pub struct Context {
     vars: Vec<Type>,
     unguard_points: Vec<usize>,
diff --git a/src/chomp/typed/error.rs b/src/chomp/typed/error.rs
index 5c1e21e..405568b 100644
--- a/src/chomp/typed/error.rs
+++ b/src/chomp/typed/error.rs
@@ -117,10 +117,32 @@ impl Display for AltError {
 impl Error for AltError {}
 
 #[derive(Debug)]
+pub struct NeedGroundError {
+    pub span: Option<Span>,
+}
+
+impl From<NeedGroundError> for syn::Error {
+    fn from(other: NeedGroundError) -> Self {
+        let msg = other.to_string();
+        let span = other.span;
+        Self::new(span.unwrap_or_else(Span::call_site), msg)
+    }
+}
+
+impl Display for NeedGroundError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "expected ground type but actually function type")
+    }
+}
+
+impl Error for NeedGroundError {}
+
+#[derive(Debug)]
 pub enum TypeError {
     Cat(CatError),
     Alt(AltError),
     Variable(VariableError),
+    NeedGround(NeedGroundError),
 }
 
 impl From<CatError> for TypeError {
@@ -141,12 +163,19 @@ impl From<VariableError> for TypeError {
     }
 }
 
+impl From<NeedGroundError> for TypeError {
+    fn from(other: NeedGroundError) -> Self {
+        Self::NeedGround(other)
+    }
+}
+
 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(),
+            TypeError::NeedGround(e) => e.into(),
         }
     }
 }
@@ -157,6 +186,7 @@ impl Display for TypeError {
             Self::Cat(e) => e.fmt(f),
             Self::Alt(e) => e.fmt(f),
             Self::Variable(e) => e.fmt(f),
+            Self::NeedGround(e) => e.fmt(f),
         }
     }
 }
diff --git a/src/chomp/typed/infer.rs b/src/chomp/typed/infer.rs
index 44ea654..01fe9c8 100644
--- a/src/chomp/typed/infer.rs
+++ b/src/chomp/typed/infer.rs
@@ -9,10 +9,9 @@ use crate::chomp::{
 use super::{
     context::Context,
     error::{TypeError, VariableError},
-    Type, Typed, TypedExpression,
+    GroundType, Typed, TypedExpression,
 };
 
-#[derive(Debug)]
 pub struct TypeInfer<'a> {
     pub context: &'a mut Context,
 }
@@ -20,9 +19,9 @@ 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: Option<Span>, _eps: Epsilon) -> Self::Out {
         Ok(TypedExpression {
-            inner: super::Epsilon::from(eps).into(),
+            inner: super::Epsilon.into(),
             name,
             span,
         })
@@ -76,14 +75,15 @@ impl Folder for TypeInfer<'_> {
     }
 
     fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
-        let mut ty = Type::default();
+        let mut ty = GroundType::default();
 
         loop {
             let last = ty;
-            let res = self.context.with_variable_type(last.clone(), |context| {
+            let res = self.context.with_variable_type(last.clone().into(), |context| {
                 fix.inner.clone().fold(&mut TypeInfer { context })
             })?;
-            ty = res.get_type().clone();
+
+            ty = res.get_type().as_ground(span)?.clone();
 
             if last == ty {
                 return Ok(TypedExpression {
diff --git a/src/chomp/typed/mod.rs b/src/chomp/typed/mod.rs
index 2a9e365..10514f0 100644
--- a/src/chomp/typed/mod.rs
+++ b/src/chomp/typed/mod.rs
@@ -1,5 +1,6 @@
-use std::{hash, iter};
+use std::{fmt, iter};
 
+use once_cell::sync::Lazy;
 use proc_macro2::Span;
 
 use super::{
@@ -14,17 +15,76 @@ pub mod lower;
 
 mod infer;
 
-use self::error::{AltError, CatError};
+use self::error::{AltError, CatError, NeedGroundError, TypeError};
 pub use self::infer::TypeInfer;
 
+#[derive(Clone)]
+pub enum Type {
+    Ground(GroundType),
+    Function(Box<dyn FunctionType + Send + Sync>),
+}
+
+impl Type {
+    pub fn as_ground(&self, span: Option<Span>) -> Result<&GroundType, NeedGroundError> {
+        match self {
+            Self::Ground(ty) => Ok(ty),
+            Self::Function(_) => Err(NeedGroundError { span }),
+        }
+    }
+
+    pub fn into_ground(self, span: Option<Span>) -> Result<GroundType, NeedGroundError> {
+        match self {
+            Self::Ground(ty) => Ok(ty),
+            Self::Function(_) => Err(NeedGroundError { span }),
+        }
+    }
+}
+
+impl fmt::Debug for Type {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Ground(ty) => ty.fmt(f),
+            Self::Function(_) => write!(f, "<fn>"),
+        }
+    }
+}
+
+impl From<GroundType> for Type {
+    fn from(ty: GroundType) -> Self {
+        Self::Ground(ty)
+    }
+}
+
+impl From<Box<dyn FunctionType + Send + Sync>> for Type {
+    fn from(f: Box<dyn FunctionType + Send + Sync>) -> Self {
+        Self::Function(f)
+    }
+}
+
+pub trait FunctionType : Fn(Type) -> Result<Type, TypeError> + Send + Sync{
+    fn clone_box(&self) -> Box<dyn FunctionType + Send + Sync>;
+}
+
+impl<F: 'static + Fn(Type) -> Result<Type, TypeError> + Clone + Send + Sync> FunctionType for F {
+    fn clone_box(&self) -> Box<dyn FunctionType + Send + Sync> {
+        Box::new(self.clone()) as Box<dyn FunctionType + Send + Sync>
+    }
+}
+
+impl Clone for Box<dyn FunctionType + Send + Sync> {
+    fn clone(&self) -> Self {
+        self.clone_box()
+    }
+}
+
 #[derive(Debug, Default, Clone, Eq, Hash, PartialEq)]
-pub struct Type {
+pub struct GroundType {
     nullable: bool,
     first_set: FirstSet,
     flast_set: FlastSet,
 }
 
-impl Type {
+impl GroundType {
     pub const fn new(nullable: bool, first_set: FirstSet, flast_set: FlastSet) -> Self {
         Self {
             nullable,
@@ -78,20 +138,12 @@ impl Type {
     }
 }
 
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
-pub struct Epsilon {
-    ty: Type,
-}
+static EPSILON_TY: Lazy<Type> = Lazy::new(|| GroundType::new(true, FirstSet::default(), FlastSet::default()).into());
 
-impl From<ast::Epsilon> for Epsilon {
-    fn from(_: ast::Epsilon) -> Self {
-        Self {
-            ty: Type::new(true, FirstSet::default(), FlastSet::default()),
-        }
-    }
-}
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+pub struct Epsilon;
 
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+#[derive(Clone, Debug)]
 pub struct Literal {
     inner: ast::Literal,
     ty: Type,
@@ -105,7 +157,7 @@ impl Literal {
 
 impl From<ast::Literal> for Literal {
     fn from(inner: ast::Literal) -> Self {
-        let ty = Type::of_str(&inner);
+        let ty = GroundType::of_str(&inner).into();
         Self { inner, ty }
     }
 }
@@ -116,7 +168,7 @@ impl From<Literal> for ast::Literal {
     }
 }
 
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+#[derive(Clone, Debug)]
 pub struct Cat {
     terms: Vec<TypedExpression>,
     ty: Type,
@@ -128,22 +180,24 @@ impl Cat {
         punct: Option<Span>,
         second: TypedExpression,
         rest: I,
-    ) -> Result<Self, CatError> {
-        if first.get_type().nullable() {
-            return Err(CatError::FirstNullable { expr: first, punct });
+    ) -> Result<Self, TypeError> {
+        let first_ty = first.get_type().as_ground(punct)?;
+        if first_ty.nullable() {
+            return Err(CatError::FirstNullable { expr: first, punct }.into());
         }
 
         iter::once((punct, second))
             .chain(rest)
             .try_fold(
-                (first.get_type().clone(), vec![first]),
+                (first_ty.clone(), vec![first]),
                 |(ty, mut terms), (punct, right)| {
+                    let right_ty = right.get_type().as_ground(punct)?;
                     if ty
                         .flast_set()
-                        .intersect_first(right.get_type().first_set())
+                        .intersect_first(right_ty.first_set())
                         .is_empty()
                     {
-                        let ty = ty.cat(right.get_type().clone());
+                        let ty = ty.cat(right_ty.clone());
                         terms.push(right);
                         Ok((ty, terms))
                     } else {
@@ -151,11 +205,11 @@ impl Cat {
                             first: terms,
                             punct,
                             next: right,
-                        })
+                        }.into())
                     }
                 },
             )
-            .map(|(ty, terms)| Self { ty, terms })
+            .map(|(ty, terms)| Self { ty: ty.into(), terms })
     }
 }
 
@@ -169,7 +223,7 @@ impl IntoIterator for Cat {
     }
 }
 
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+#[derive(Clone, Debug)]
 pub struct Alt {
     terms: Vec<TypedExpression>,
     ty: Type,
@@ -181,24 +235,25 @@ impl Alt {
         punct: Option<Span>,
         second: TypedExpression,
         rest: I,
-    ) -> Result<Self, AltError> {
+    ) -> Result<Self, TypeError> {
         iter::once((punct, second))
             .chain(rest)
             .try_fold(
-                (first.get_type().clone(), vec![first]),
+                (first.get_type().as_ground(punct)?.clone(), vec![first]),
                 |(ty, mut terms), (punct, right)| {
-                    if ty.nullable() && right.get_type().nullable() {
+                    let right_ty = right.get_type().as_ground(punct)?;
+                    if ty.nullable() && right_ty.nullable() {
                         Err(AltError::BothNullable {
                             left: terms,
                             punct,
                             right,
-                        })
+                        }.into())
                     } else if ty
                         .first_set()
-                        .intersect(right.get_type().first_set())
+                        .intersect(right_ty.first_set())
                         .is_empty()
                     {
-                        let ty = ty.alt(right.get_type().clone());
+                        let ty = ty.alt(right_ty.clone());
                         terms.push(right);
                         Ok((ty, terms))
                     } else {
@@ -206,11 +261,11 @@ impl Alt {
                             left: terms,
                             punct,
                             right,
-                        })
+                        }.into())
                     }
                 },
             )
-            .map(|(ty, terms)| Self { ty, terms })
+            .map(|(ty, terms)| Self { ty: ty.into(), terms })
     }
 }
 
@@ -224,7 +279,7 @@ impl IntoIterator for Alt {
     }
 }
 
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+#[derive(Clone, Debug)]
 pub struct Fix {
     inner: Box<TypedExpression>,
 }
@@ -235,7 +290,7 @@ impl Fix {
     }
 }
 
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+#[derive(Clone, Debug)]
 pub struct Variable {
     inner: ast::Variable,
     ty: Type,
@@ -247,7 +302,7 @@ impl Variable {
     }
 }
 
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+#[derive(Clone, Debug)]
 enum RawTypedExpression {
     Epsilon(Epsilon),
     Literal(Literal),
@@ -300,25 +355,16 @@ pub struct TypedExpression {
     pub span: Option<Span>,
 }
 
-impl PartialEq for TypedExpression {
-    fn eq(&self, other: &Self) -> bool {
-        self.inner == other.inner && self.name == other.name
-    }
+pub trait Typed {
+    fn get_type(&self) -> &Type;
 }
 
-impl Eq for TypedExpression {}
-
-impl hash::Hash for TypedExpression {
-    fn hash<H: hash::Hasher>(&self, state: &mut H) {
-        self.inner.hash(state);
-        self.name.hash(state);
+impl Typed for Epsilon {
+    fn get_type(&self) -> &Type {
+        &EPSILON_TY
     }
 }
 
-pub trait Typed {
-    fn get_type(&self) -> &Type;
-}
-
 macro_rules! leaf_typed {
     ($ty:ty, $field:ident) => {
         impl Typed for $ty {
@@ -329,7 +375,6 @@ macro_rules! leaf_typed {
     };
 }
 
-leaf_typed!(Epsilon, ty);
 leaf_typed!(Literal, ty);
 leaf_typed!(Cat, ty);
 leaf_typed!(Alt, ty);
diff --git a/src/lower/mod.rs b/src/lower/mod.rs
index dcd0f1f..83ac6ab 100644
--- a/src/lower/mod.rs
+++ b/src/lower/mod.rs
@@ -8,10 +8,15 @@ use proc_macro2::{Ident, Span, TokenStream, TokenTree};
 use quote::{format_ident, quote, quote_spanned};
 use syn::{Index, LitStr};
 
-use crate::chomp::{Name, ast, set::FirstSet, typed::{
+use crate::chomp::{
+    ast,
+    set::FirstSet,
+    typed::{
         lower::{Backend, GenerateCode},
-        Alt, Cat, Epsilon, Fix, Literal, Type, Typed, TypedExpression, Variable,
-    }};
+        Alt, Cat, Epsilon, Fix, GroundType, Literal, Type, Typed, TypedExpression, Variable,
+    },
+    Name,
+};
 
 #[derive(Clone, Debug)]
 struct Ty {
@@ -28,7 +33,6 @@ pub struct RustBackend {
     lit_map: HashMap<String, usize>,
     cat_map: HashMap<Vec<usize>, usize>,
     alt_map: HashMap<Vec<usize>, usize>,
-    fix_map: HashMap<TypedExpression, usize>,
     var_map: HashMap<usize, usize>, // Key is fix point ID
     name_map: HashMap<Ident, usize>,
     can_char: BTreeSet<usize>,
@@ -139,7 +143,6 @@ impl Default for RustBackend {
             lit_map: HashMap::new(),
             cat_map: HashMap::new(),
             alt_map: HashMap::new(),
-            fix_map: HashMap::new(),
             var_map: HashMap::new(),
             name_map: HashMap::new(),
             can_char: BTreeSet::new(),
@@ -286,6 +289,13 @@ impl Backend for RustBackend {
     fn gen_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Id {
         let span = span.unwrap_or_else(Span::call_site);
         let (tys, name_spans, ids) = self.recurse_exprs(alt);
+        let tys = tys
+            .into_iter()
+            .map(|ty| {
+                ty.into_ground(None)
+                    .expect("alt must have ground-typed children")
+            })
+            .collect::<Vec<_>>();
 
         if let Some(&id) = self.alt_map.get(&ids) {
             return id;
@@ -302,7 +312,7 @@ impl Backend for RustBackend {
             .map(|(idx, _)| name_parts[idx].clone());
         let (first_alts, firsts): (Vec<_>, Vec<_>) = tys
             .iter()
-            .map(Type::first_set)
+            .map(GroundType::first_set)
             .cloned()
             .enumerate()
             .filter(|(_, fs)| !fs.is_empty())
@@ -313,7 +323,7 @@ impl Backend for RustBackend {
             .unzip();
         let all_firsts = tys
             .iter()
-            .map(Type::first_set)
+            .map(GroundType::first_set)
             .cloned()
             .flat_map(FirstSet::into_iter);
 
@@ -383,12 +393,7 @@ impl Backend for RustBackend {
         let span = span.unwrap_or_else(Span::call_site);
         let inner = fix.unwrap();
 
-        if let Some(&id) = self.fix_map.get(&inner) {
-            return id;
-        }
-
         let (id, name) = self.new_type_name("Fix", name, span);
-        self.fix_map.insert(inner.clone(), id);
 
         self.data.push(Ty {
             name: TokenTree::from(name.clone()).into(),