5 files changed, 752 insertions, 0 deletions
diff --git a/src/chomp/typed-old/context.rs b/src/chomp/typed-old/context.rs
new file mode 100644
index 0000000..f3263ce
--- /dev/null
+++ b/src/chomp/typed-old/context.rs
@@ -0,0 +1,58 @@
+use crate::chomp::ast::Variable;
+
+use super::Type;
+
+#[derive(Debug, Default)]
+pub struct Context {
+    vars: Vec<Type>,
+    unguard_points: Vec<usize>,
+}
+
+impl Context {
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    pub fn depth(&self) -> usize {
+        self.vars.len()
+    }
+
+    pub fn with_unguard<F: FnOnce(&mut Self) -> R, R>(&mut self, f: F) -> R {
+        self.unguard_points.push(self.vars.len());
+        let res = f(self);
+        self.unguard_points.pop();
+        res
+    }
+
+    pub fn get_variable_type(&self, var: Variable) -> Result<&Type, GetVariableError> {
+        self.vars
+            .iter()
+            .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)
+            })
+    }
+
+    pub fn with_variable_type<F: FnOnce(&mut Self) -> R, R>(&mut self, ty: Type, f: F) -> R {
+        self.vars.push(ty);
+        let res = f(self);
+        self.vars.pop();
+        res
+    }
+}
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum GetVariableError {
+    FreeVariable,
+    GuardedVariable,
+}
diff --git a/src/chomp/typed-old/error.rs b/src/chomp/typed-old/error.rs
new file mode 100644
index 0000000..5c1e21e
--- /dev/null
+++ b/src/chomp/typed-old/error.rs
@@ -0,0 +1,164 @@
+use std::{
+    error::Error,
+    fmt::{self, Display},
+};
+
+use proc_macro2::Span;
+
+use crate::chomp::{ast::Variable, Name};
+
+use super::{context::GetVariableError, TypedExpression};
+
+/// 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 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 {
+            GetVariableError::FreeVariable => write!(f, "unbound variable: "),
+            GetVariableError::GuardedVariable => write!(f, "usage of guarded variable: "),
+        }?;
+
+        if let Some(name) = &self.name {
+            write!(f, "`{}`", name)
+        } else {
+            write!(f, "'{}", self.var.index)
+        }
+    }
+}
+
+impl Error for VariableError {}
+
+#[derive(Debug)]
+pub enum CatError {
+    FirstNullable {
+        expr: TypedExpression,
+        punct: Option<Span>,
+    },
+    FirstFlastOverlap {
+        first: Vec<TypedExpression>,
+        punct: Option<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 Display for CatError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::FirstNullable { .. } => write!(f, "first part of concatenation is nullable"),
+            Self::FirstFlastOverlap { .. } => {
+                write!(f, "first set overlaps with preceding flast set")
+            }
+        }
+    }
+}
+
+impl Error for CatError {}
+
+#[derive(Debug)]
+pub enum AltError {
+    BothNullable {
+        left: Vec<TypedExpression>,
+        punct: Option<Span>,
+        right: TypedExpression,
+    },
+    FirstOverlap {
+        left: Vec<TypedExpression>,
+        punct: Option<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 Display for AltError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::BothNullable { .. } => write!(f, "both branches are nullable"),
+            Self::FirstOverlap { .. } => write!(f, "first sets of both branches overlap"),
+        }
+    }
+}
+
+impl Error for AltError {}
+
+#[derive(Debug)]
+pub enum TypeError {
+    Cat(CatError),
+    Alt(AltError),
+    Variable(VariableError),
+}
+
+impl From<CatError> for TypeError {
+    fn from(other: CatError) -> Self {
+        Self::Cat(other)
+    }
+}
+
+impl From<AltError> for TypeError {
+    fn from(other: AltError) -> Self {
+        Self::Alt(other)
+    }
+}
+
+impl From<VariableError> for TypeError {
+    fn from(other: VariableError) -> Self {
+        Self::Variable(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(),
+        }
+    }
+}
+
+impl Display for TypeError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Cat(e) => e.fmt(f),
+            Self::Alt(e) => e.fmt(f),
+            Self::Variable(e) => e.fmt(f),
+        }
+    }
+}
+
+impl Error for TypeError {}
diff --git a/src/chomp/typed-old/infer.rs b/src/chomp/typed-old/infer.rs
new file mode 100644
index 0000000..e2c2198
--- /dev/null
+++ b/src/chomp/typed-old/infer.rs
@@ -0,0 +1,127 @@
+use proc_macro2::Span;
+
+use crate::chomp::{Name, ast::{Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, substitute::Translate}, visit::{Folder, Visitable}};
+
+use super::{Type, Typed, TypedExpression, context::Context, error::{TypeError, VariableError}};
+
+#[derive(Debug)]
+pub struct TypeInfer<'a> {
+    pub context: &'a mut Context,
+}
+
+impl Folder for TypeInfer<'_> {
+    type Out = Result<TypedExpression, TypeError>;
+
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+        Ok(TypedExpression {
+            inner: super::Epsilon::from(eps).into(),
+            name,
+            span,
+        })
+    }
+
+    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+        Ok(TypedExpression {
+            inner: super::Literal::from(lit).into(),
+            name,
+            span,
+        })
+    }
+
+    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+        let first = cat.first.fold(self)?;
+        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,
+                })
+            })
+    }
+
+    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+        let first = alt.first.fold(self)?;
+        let rest = alt
+            .rest
+            .into_iter()
+            .map(|(punct, term)| -> Result<_, TypeError> { Ok((punct, term.fold(self)?)) })
+            .collect::<Result<Vec<_>, _>>()?;
+        Ok(TypedExpression {
+            inner: super::Alt::new(first, rest)?.into(),
+            name,
+            span,
+        })
+    }
+
+    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+        let mut ty = Type::default();
+
+        loop {
+            let last = ty;
+            let res = self.context.with_variable_type(last.clone(), |context| {
+                fix.inner.clone().fold(&mut TypeInfer { context })
+            })?;
+            ty = res.get_type().clone();
+
+            if last == ty {
+                return Ok(TypedExpression {
+                    inner: super::Fix {
+                        inner: Box::new(res),
+                    }
+                    .into(),
+                    name,
+                    span,
+                });
+            }
+        }
+    }
+
+    fn fold_variable(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        var: Variable,
+    ) -> Self::Out {
+        let ty = match self.context.get_variable_type(var) {
+            Ok(ty) => ty.clone(),
+            Err(inner) => {
+                return Err(VariableError {
+                    inner,
+                    var,
+                    span,
+                    name,
+                }
+                .into())
+            }
+        };
+        Ok(TypedExpression {
+            inner: super::Variable { inner: var, ty }.into(),
+            name,
+            span,
+        })
+    }
+
+    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_lambda(
+        &mut self,
+        _name: Option<Name>,
+        _span: Option<Span>,
+        _lambda: Lambda,
+    ) -> Self::Out {
+        unimplemented!()
+    }
+}
diff --git a/src/chomp/typed-old/lower.rs b/src/chomp/typed-old/lower.rs
new file mode 100644
index 0000000..37589a1
--- /dev/null
+++ b/src/chomp/typed-old/lower.rs
@@ -0,0 +1,41 @@
+use proc_macro2::Span;
+
+use crate::chomp::Name;
+
+use super::{Alt, Cat, Epsilon, Fix, Literal, RawTypedExpression, TypedExpression, Variable};
+
+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_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Id;
+
+    fn gen_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Id;
+
+    fn gen_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Id;
+
+    fn gen_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Id;
+
+    fn gen_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable) -> Self::Id;
+
+    fn emit_code(self, name: Option<Name>, span: Option<Span>, id: Self::Id) -> Self::Code;
+}
+
+pub trait GenerateCode {
+    fn gen<B: Backend>(self, backend: &mut B) -> B::Id;
+}
+
+impl GenerateCode for TypedExpression {
+    fn gen<B: Backend>(self, backend: &mut B) -> B::Id {
+        match self.inner {
+            RawTypedExpression::Epsilon(e) => backend.gen_epsilon(self.name, self.span, e),
+            RawTypedExpression::Literal(l) => backend.gen_literal(self.name, self.span, l),
+            RawTypedExpression::Cat(c) => backend.gen_cat(self.name, self.span, c),
+            RawTypedExpression::Alt(a) => backend.gen_alt(self.name, self.span, a),
+            RawTypedExpression::Fix(f) => backend.gen_fix(self.name, self.span, f),
+            RawTypedExpression::Variable(v) => backend.gen_variable(self.name, self.span, v),
+        }
+    }
+}
diff --git a/src/chomp/typed-old/mod.rs b/src/chomp/typed-old/mod.rs
new file mode 100644
index 0000000..cddb05a
--- /dev/null
+++ b/src/chomp/typed-old/mod.rs
@@ -0,0 +1,362 @@
+use std::hash;
+
+use proc_macro2::Span;
+
+use super::{
+    ast,
+    set::{FirstSet, FlastSet},
+    Name,
+};
+
+pub mod context;
+pub mod error;
+pub mod lower;
+
+mod infer;
+
+use self::error::{AltError, CatError};
+pub use self::infer::TypeInfer;
+
+#[derive(Debug, Default, Clone, Eq, Hash, PartialEq)]
+pub struct Type {
+    nullable: bool,
+    first_set: FirstSet,
+    flast_set: FlastSet,
+}
+
+impl Type {
+    pub const fn new(nullable: bool, first_set: FirstSet, flast_set: FlastSet) -> Self {
+        Self {
+            nullable,
+            first_set,
+            flast_set,
+        }
+    }
+
+    pub fn of_str(s: &str) -> Self {
+        Self {
+            nullable: s.is_empty(),
+            first_set: FirstSet::of_str(s),
+            flast_set: FlastSet::default(),
+        }
+    }
+
+    pub fn nullable(&self) -> bool {
+        self.nullable
+    }
+
+    pub fn first_set(&self) -> &FirstSet {
+        &self.first_set
+    }
+
+    pub fn flast_set(&self) -> &FlastSet {
+        &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 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),
+        }
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Epsilon {
+    ty: Type,
+}
+
+impl From<ast::Epsilon> for Epsilon {
+    fn from(_: ast::Epsilon) -> Self {
+        Self {
+            ty: Type::new(true, FirstSet::default(), FlastSet::default()),
+        }
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Literal {
+    inner: ast::Literal,
+    ty: Type,
+}
+
+impl Literal {
+    pub fn inner(&self) -> &ast::Literal {
+        &self.inner
+    }
+}
+
+impl From<ast::Literal> for Literal {
+    fn from(inner: ast::Literal) -> Self {
+        let ty = Type::of_str(&inner);
+        Self { inner, ty }
+    }
+}
+
+impl From<Literal> for ast::Literal {
+    fn from(lit: Literal) -> Self {
+        lit.inner
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Cat {
+    terms: Vec<TypedExpression>,
+    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;
+
+    type IntoIter = <Vec<TypedExpression> as IntoIterator>::IntoIter;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.terms.into_iter()
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Alt {
+    terms: Vec<TypedExpression>,
+    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;
+
+    type IntoIter = <Vec<TypedExpression> as IntoIterator>::IntoIter;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.terms.into_iter()
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Fix {
+    inner: Box<TypedExpression>,
+}
+
+impl Fix {
+    pub fn unwrap(self) -> TypedExpression {
+        *self.inner
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Variable {
+    inner: ast::Variable,
+    ty: Type,
+}
+
+impl Variable {
+    pub fn index(&self) -> usize {
+        self.inner.index
+    }
+}
+
+#[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),
+    Cat(Cat),
+    Alt(Alt),
+    Fix(Fix),
+    Variable(Variable),
+    Call(Call),
+    Lambda(Lambda),
+}
+
+impl From<Epsilon> for RawTypedExpression {
+    fn from(eps: Epsilon) -> Self {
+        Self::Epsilon(eps)
+    }
+}
+
+impl From<Literal> for RawTypedExpression {
+    fn from(lit: Literal) -> Self {
+        Self::Literal(lit)
+    }
+}
+
+impl From<Cat> for RawTypedExpression {
+    fn from(cat: Cat) -> Self {
+        Self::Cat(cat)
+    }
+}
+
+impl From<Alt> for RawTypedExpression {
+    fn from(alt: Alt) -> Self {
+        Self::Alt(alt)
+    }
+}
+
+impl From<Fix> for RawTypedExpression {
+    fn from(fix: Fix) -> Self {
+        Self::Fix(fix)
+    }
+}
+
+impl From<Variable> for RawTypedExpression {
+    fn from(var: Variable) -> Self {
+        Self::Variable(var)
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct TypedExpression {
+    inner: RawTypedExpression,
+    pub name: Option<Name>,
+    pub span: Option<Span>,
+}
+
+impl PartialEq for TypedExpression {
+    fn eq(&self, other: &Self) -> bool {
+        self.inner == other.inner && self.name == other.name
+    }
+}
+
+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);
+    }
+}
+
+pub trait Typed {
+    fn get_type(&self) -> &Type;
+}
+
+macro_rules! leaf_typed {
+    ($ty:ty, $field:ident) => {
+        impl Typed for $ty {
+            fn get_type(&self) -> &Type {
+                &self.$field
+            }
+        }
+    };
+}
+
+leaf_typed!(Epsilon, ty);
+leaf_typed!(Literal, ty);
+leaf_typed!(Cat, ty);
+leaf_typed!(Alt, ty);
+leaf_typed!(Variable, ty);
+
+impl Typed for Fix {
+    fn get_type(&self) -> &Type {
+        self.inner.get_type()
+    }
+}
+
+impl Typed for TypedExpression {
+    fn get_type(&self) -> &Type {
+        match &self.inner {
+            RawTypedExpression::Epsilon(e) => e.get_type(),
+            RawTypedExpression::Literal(l) => l.get_type(),
+            RawTypedExpression::Cat(c) => c.get_type(),
+            RawTypedExpression::Alt(a) => a.get_type(),
+            RawTypedExpression::Fix(f) => f.get_type(),
+            RawTypedExpression::Variable(v) => v.get_type(),
+        }
+    }
+}