summaryrefslogtreecommitdiff
path: root/src/chomp
diff options
context:
space:
mode:
Diffstat (limited to 'src/chomp')
-rw-r--r--src/chomp/'475
-rw-r--r--src/chomp/ast.rs345
-rw-r--r--src/chomp/check.rs481
-rw-r--r--src/chomp/context.rs51
-rw-r--r--src/chomp/error.rs389
-rw-r--r--src/chomp/mod.rs7
-rw-r--r--src/chomp/set.rs91
-rw-r--r--src/chomp/typed.rs321
-rw-r--r--src/chomp/visit.rs136
9 files changed, 2296 insertions, 0 deletions
diff --git a/src/chomp/' b/src/chomp/'
new file mode 100644
index 0000000..f2f6588
--- /dev/null
+++ b/src/chomp/'
@@ -0,0 +1,475 @@
+use proc_macro2::{Ident, Span};
+
+use super::{ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Function, Literal, Parameter, Variable}, context::Context, error::{AltError, CatError, FixError, SubstituteError, TypeError}, set::{FirstSet, FlastSet}, typed::{self, Type, TypedExpression}, visit::{Folder, Mapper, Visitable, Visitor}};
+
+/// Test if term is closed for a context with `depth` variables.
+#[derive(Debug, Default)]
+struct Closed {
+ depth: usize,
+}
+
+impl Visitor for Closed {
+ type Out = bool;
+
+ fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+ true
+ }
+
+ fn visit_literal(&mut self, _lit: &Literal) -> Self::Out {
+ true
+ }
+
+ fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+ cat.first().visit(self) && cat.second().visit(self)
+ }
+
+ fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+ alt.left().visit(self) && alt.right().visit(self)
+ }
+
+ fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+ self.depth += 1;
+ let res = fix.inner().visit(self);
+ self.depth -= 1;
+ res
+ }
+
+ fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+ var.index() < self.depth
+ }
+
+ fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+ true
+ }
+
+ fn visit_call(&mut self, call: &Call) -> Self::Out {
+ call.args().iter().all(|arg| arg.visit(self))
+ }
+}
+
+#[derive(Clone, Copy, Debug)]
+pub struct Spanning;
+
+impl Visitor for Spanning {
+ type Out = Option<Span>;
+
+ fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out {
+ Some(eps.span)
+ }
+
+ fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+ Some(lit.span())
+ }
+
+ fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+ let fst = cat.first().visit(self);
+ let snd = cat.second().visit(self);
+
+ match (fst, snd) {
+ (None, snd) => snd,
+ (Some(fst), None) => Some(fst),
+ (Some(fst), Some(snd)) => fst.join(snd),
+ }
+ }
+
+ fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+ let left = alt.left().visit(self);
+ let right = alt.right().visit(self);
+
+ match (left, right) {
+ (None, right) => right,
+ (Some(left), None) => Some(left),
+ (Some(left), Some(right)) => left.join(right),
+ }
+ }
+
+ fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+ fix.span()
+ }
+
+ fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+ Some(var.name().span())
+ }
+
+ fn visit_parameter(&mut self, param: &Parameter) -> Self::Out {
+ Some(param.name().span())
+ }
+
+ fn visit_call(&mut self, call: &Call) -> Self::Out {
+ call.span()
+ }
+}
+
+#[derive(Debug)]
+pub struct TypeInfer<'a> {
+ context: &'a mut Context,
+}
+
+impl Visitor for TypeInfer<'_> {
+ type Out = Result<Type, TypeError>;
+
+ fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+ Ok(Type::new(true, FirstSet::default(), FlastSet::default()))
+ }
+
+ fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+ Ok(Type::of_str(&lit.value()))
+ }
+
+ fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+ let first = cat.first().visit(self)?;
+ let second = self
+ .context
+ .with_unguard(|context| cat.second().visit(&mut TypeInfer { context }))?;
+
+ if first.nullable() {
+ Err(TypeError::Cat(CatError::FirstNullable(cat.clone())))
+ } else if !first
+ .flast_set()
+ .intersect_first(second.first_set())
+ .is_empty()
+ {
+ Err(TypeError::Cat(CatError::FirstFlastOverlap(cat.clone())))
+ } else {
+ Ok(first.cat(second))
+ }
+ }
+
+ fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+ let left = alt.left().visit(self)?;
+ let right = alt.right().visit(self)?;
+
+ if left.nullable() && right.nullable() {
+ Err(TypeError::Alt(AltError::BothNullable(alt.clone())))
+ } else if !left.first_set().intersect(right.first_set()).is_empty() {
+ Err(TypeError::Alt(AltError::FirstOverlap(alt.clone())))
+ } else {
+ Ok(left.alt(right))
+ }
+ }
+
+ fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+ let mut res = Type::default();
+ let mut last = None;
+
+ while last.map(|r| r != res).unwrap_or(true) {
+ last = Some(res);
+ res = self
+ .context
+ .with_variable_type(last.as_ref().cloned().unwrap(), |context| {
+ fix.inner().visit(&mut TypeInfer { context })
+ })
+ .map_err(|e| {
+ TypeError::Fix(FixError(
+ fix.clone(),
+ last.as_ref().cloned().unwrap(),
+ Box::new(e),
+ ))
+ })?;
+ }
+
+ Ok(res)
+ }
+
+ fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+ Ok(self.context.get_variable_type(&var)?.clone())
+ }
+
+ fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+ todo!()
+ }
+
+ fn visit_call(&mut self, _call: &Call) -> Self::Out {
+ todo!()
+ }
+}
+
+#[derive(Debug)]
+pub struct TypeCheck<'a> {
+ pub context: &'a mut Context,
+}
+
+impl Folder for TypeCheck<'_> {
+ type Out = Result<TypedExpression, TypeError>;
+
+ fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+ Ok(typed::Epsilon::from(eps).into())
+ }
+
+ fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+ Ok(typed::Literal::from(lit).into())
+ }
+
+ fn fold_cat(&mut self, cat: Cat) -> Self::Out {
+ let ty = TypeInfer {
+ context: self.context,
+ }
+ .visit_cat(&cat)?;
+ let fst = cat.fst.fold(self)?;
+ let snd = cat.snd;
+ let snd = self
+ .context
+ .with_unguard(|context| snd.fold(&mut TypeCheck { context }))?;
+
+ Ok(typed::Cat::new(fst, cat.punct, snd, ty).into())
+ }
+
+ fn fold_alt(&mut self, alt: Alt) -> Self::Out {
+ let ty = TypeInfer {
+ context: self.context,
+ }
+ .visit_alt(&alt)?;
+ let left = alt.left.fold(self)?;
+ let right = alt.right.fold(self)?;
+
+ Ok(typed::Alt::new(left, alt.punct, right, ty).into())
+ }
+
+ fn fold_fix(&mut self, fix: Fix) -> Self::Out {
+ let ty = TypeInfer {
+ context: self.context,
+ }
+ .visit_fix(&fix)?;
+ let inner = fix.inner;
+ let inner = self
+ .context
+ .with_variable_type(ty.clone(), |context| inner.fold(&mut TypeCheck { context }))?;
+
+ Ok(typed::Fix::new(fix.arg, inner, fix.span, ty).into())
+ }
+
+ fn fold_variable(&mut self, var: Variable) -> Self::Out {
+ let ty = TypeInfer {
+ context: self.context,
+ }
+ .visit_variable(&var)?;
+ Ok(typed::Variable::new(var, ty).into())
+ }
+
+ fn fold_parameter(&mut self, _param: Parameter) -> Self::Out {
+ todo!()
+ }
+
+ fn fold_call(&mut self, _call: Call) -> Self::Out {
+ todo!()
+ }
+}
+
+#[derive(Debug, Default)]
+struct DeepenVars {
+ depth: usize,
+}
+
+impl Mapper for DeepenVars {
+ type Out = ();
+
+ fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+ fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+ fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+ cat.first_mut().map(self);
+ cat.second_mut().map(self);
+ }
+
+ fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+ alt.left_mut().map(self);
+ alt.right_mut().map(self);
+ }
+
+ fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+ self.depth += 1;
+ fix.inner_mut().map(self);
+ self.depth -= 1;
+ }
+
+ fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+ if bind.index() >= self.depth {
+ *bind.index_mut() += 1;
+ }
+ }
+
+ fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+ fn map_call(&mut self, call: &mut Call) -> Self::Out {
+ for arg in call.args_mut() {
+ arg.map(self);
+ }
+ }
+}
+
+#[derive(Debug, Default)]
+struct ShallowVars {
+ depth: usize,
+}
+
+impl Mapper for ShallowVars {
+ type Out = ();
+
+ fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+ fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+ fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+ cat.first_mut().map(self);
+ cat.second_mut().map(self);
+ }
+
+ fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+ alt.left_mut().map(self);
+ alt.right_mut().map(self);
+ }
+
+ fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+ self.depth += 1;
+ fix.inner_mut().map(self);
+ self.depth -= 1;
+ }
+
+ fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+ if bind.index() > self.depth {
+ *bind.index_mut() -= 1;
+ }
+ }
+
+ fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+ fn map_call(&mut self, call: &mut Call) -> Self::Out {
+ for arg in call.args_mut() {
+ arg.map(self);
+ }
+ }
+}
+
+struct Substitute {
+ params: Vec<Expression>,
+}
+
+impl Folder for Substitute {
+ type Out = Result<Expression, SubstituteError>;
+
+ fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+ Ok(eps.into())
+ }
+
+ fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+ Ok(lit.into())
+ }
+
+ fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+ cat.fst = Box::new(cat.fst.fold(self)?);
+ cat.snd = Box::new(cat.snd.fold(self)?);
+ Ok(cat.into())
+ }
+
+ fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+ alt.left = Box::new(alt.left.fold(self)?);
+ alt.right = Box::new(alt.right.fold(self)?);
+ Ok(alt.into())
+ }
+
+ fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+ for param in &mut self.params {
+ param.map(&mut DeepenVars::default());
+ }
+
+ fix.inner = Box::new(fix.inner.fold(self)?);
+
+ for param in &mut self.params {
+ param.map(&mut ShallowVars::default());
+ }
+
+ Ok(fix.into())
+ }
+
+ fn fold_variable(&mut self, var: Variable) -> Self::Out {
+ Ok(Expression::Variable(var))
+ }
+
+ fn fold_call(&mut self, mut call: Call) -> Self::Out {
+ call.args = call
+ .args
+ .into_iter()
+ .map(|arg| arg.fold(self))
+ .collect::<Result<_, _>>()?;
+ Ok(call.into())
+ }
+
+ fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+ self.params
+ .get(param.index())
+ .cloned()
+ .ok_or(SubstituteError::FreeParameter(param))
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct InlineCall {
+ function: Function,
+}
+
+impl InlineCall {
+ pub fn new(function: Function) -> Self {
+ Self {
+ function
+ }
+ }
+}
+
+impl Folder for InlineCall {
+ type Out = Result<Expression, SubstituteError>;
+
+ fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+ Ok(eps.into())
+ }
+
+ fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+ Ok(lit.into())
+ }
+
+ fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+ cat.fst = Box::new(cat.fst.fold(self)?);
+ cat.snd = Box::new(cat.snd.fold(self)?);
+ Ok(cat.into())
+ }
+
+ fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+ alt.left = Box::new(alt.left.fold(self)?);
+ alt.right = Box::new(alt.right.fold(self)?);
+ Ok(alt.into())
+ }
+
+ fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+ fix.inner = Box::new(fix.inner.fold(self)?);
+ Ok(fix.into())
+ }
+
+ fn fold_variable(&mut self, var: Variable) -> Self::Out {
+ Ok(var.into())
+ }
+
+ fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+ Ok(param.into())
+ }
+
+ fn fold_call(&mut self, mut call: Call) -> Self::Out {
+ call.args = call
+ .args
+ .into_iter()
+ .map(|arg| arg.fold(self))
+ .collect::<Result<_, _>>()?;
+
+ if call.name != self.function.name {
+ Ok(call.into())
+ } else if call.args.len() != self.function.params {
+ Err(SubstituteError::WrongArgCount {
+ call,
+ expected: self.args,
+ })
+ } else {
+ self.term
+ .clone()
+ .fold(&mut Substitute { params: call.args })
+ }
+ }
+}
diff --git a/src/chomp/ast.rs b/src/chomp/ast.rs
new file mode 100644
index 0000000..e8e3309
--- /dev/null
+++ b/src/chomp/ast.rs
@@ -0,0 +1,345 @@
+use std::fmt::{self, Display};
+
+use proc_macro2::Span;
+use syn::{Ident, LitStr, Token};
+
+pub type Epsilon = Token![_];
+
+pub type Literal = LitStr;
+
+#[derive(Clone, Debug)]
+pub struct Cat {
+ pub fst: Box<Expression>,
+ pub punct: Option<Token![.]>,
+ pub snd: Box<Expression>,
+}
+
+impl Cat {
+ pub fn new(fst: Expression, punct: Option<Token![.]>, snd: Expression) -> Self {
+ Self {
+ fst: Box::new(fst),
+ punct,
+ snd: Box::new(snd),
+ }
+ }
+
+ pub fn first(&self) -> &Expression {
+ &self.fst
+ }
+
+ pub fn first_mut(&mut self) -> &mut Expression {
+ &mut self.fst
+ }
+
+ pub fn punct(&self) -> Option<Token![.]> {
+ self.punct
+ }
+
+ pub fn second(&self) -> &Expression {
+ &self.snd
+ }
+
+ pub fn second_mut(&mut self) -> &mut Expression {
+ &mut self.snd
+ }
+}
+
+impl Display for Cat {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "({}.{})", self.fst, self.snd)
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct Alt {
+ pub left: Box<Expression>,
+ pub punct: Option<Token![|]>,
+ pub right: Box<Expression>,
+}
+
+impl Alt {
+ pub fn new(left: Expression, punct: Option<Token![|]>, right: Expression) -> Self {
+ Self {
+ left: Box::new(left),
+ punct,
+ right: Box::new(right),
+ }
+ }
+
+ pub fn left(&self) -> &Expression {
+ &self.left
+ }
+
+ pub fn left_mut(&mut self) -> &mut Expression {
+ &mut self.left
+ }
+
+ pub fn punct(&self) -> Option<Token![|]> {
+ self.punct
+ }
+
+ pub fn right(&self) -> &Expression {
+ &self.right
+ }
+
+ pub fn right_mut(&mut self) -> &mut Expression {
+ &mut self.right
+ }
+}
+
+impl Display for Alt {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "({}|{})", self.left, self.right)
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct Fix {
+ pub arg: Ident,
+ pub inner: Box<Expression>,
+ pub span: Option<Span>,
+}
+
+impl Fix {
+ pub fn new(arg: Ident, inner: Expression, span: Option<Span>) -> Self {
+ Self {
+ arg,
+ inner: Box::new(inner),
+ span,
+ }
+ }
+
+ pub fn arg(&self) -> &Ident {
+ &self.arg
+ }
+
+ pub fn inner(&self) -> &Expression {
+ &self.inner
+ }
+
+ pub fn inner_mut(&mut self) -> &mut Expression {
+ &mut self.inner
+ }
+
+ pub fn span(&self) -> Option<Span> {
+ self.span
+ }
+}
+
+impl Display for Fix {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "[{}]({})", self.arg, self.inner)
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct Variable {
+ pub name: Ident,
+ pub index: usize,
+}
+
+impl Variable {
+ pub fn new(name: Ident, index: usize) -> Self {
+ Self { name, index }
+ }
+
+ pub fn name(&self) -> &Ident {
+ &self.name
+ }
+
+ pub fn index(&self) -> usize {
+ self.index
+ }
+
+ pub fn index_mut(&mut self) -> &mut usize {
+ &mut self.index
+ }
+}
+
+impl Display for Variable {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.name.fmt(f)
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct Parameter {
+ pub name: Ident,
+ pub index: usize,
+}
+
+impl Parameter {
+ pub fn new(name: Ident, index: usize) -> Self {
+ Self { name, index }
+ }
+
+ pub fn name(&self) -> &Ident {
+ &self.name
+ }
+
+ pub fn index(&self) -> usize {
+ self.index
+ }
+
+ pub fn index_mut(&mut self) -> &mut usize {
+ &mut self.index
+ }
+}
+
+impl Display for Parameter {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.name.fmt(f)
+ }
+}
+
+/// A macro invocation.
+#[derive(Clone, Debug)]
+pub struct Call {
+ pub name: Ident,
+ pub args: Vec<Expression>,
+ pub span: Option<Span>,
+}
+
+impl Call {
+ pub fn new(name: Ident, args: Vec<Expression>, span: Option<Span>) -> Self {
+ Self { name, args, span }
+ }
+
+ pub fn name(&self) -> &Ident {
+ &self.name
+ }
+
+ pub fn args(&self) -> &[Expression] {
+ &self.args
+ }
+
+ pub fn args_mut(&mut self) -> &mut [Expression] {
+ &mut self.args
+ }
+
+ pub fn span(&self) -> Option<Span> {
+ self.span
+ }
+}
+
+impl Display for Call {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "{}", self.name)?;
+
+ let mut iter = self.args.iter();
+
+ if let Some(arg) = iter.next() {
+ write!(f, "({}", arg)?;
+
+ for arg in iter {
+ write!(f, ", {}", arg)?;
+ }
+
+ write!(f, ")")
+ } else {
+ Ok(())
+ }
+ }
+}
+
+#[derive(Clone, Debug)]
+pub enum Expression {
+ /// Matches the empty string.
+ Epsilon(Epsilon),
+ /// Matches the literal string.
+ Literal(Literal),
+ /// Matches one term followed by another.
+ Cat(Cat),
+ /// Matches either one term or another.
+ Alt(Alt),
+ /// The least fix point of a term.
+ Fix(Fix),
+ /// A fixed point variable.
+ Variable(Variable),
+ /// A formal parameter.
+ Parameter(Parameter),
+ /// A macro invocation.
+ Call(Call),
+}
+
+impl Display for Expression {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Self::Epsilon(_) => write!(f, "_"),
+ Self::Literal(l) => write!(f, "{:?}", l.value()),
+ Self::Cat(c) => c.fmt(f),
+ Self::Alt(a) => a.fmt(f),
+ Self::Fix(x) => x.fmt(f),
+ Self::Variable(v) => v.fmt(f),
+ Self::Parameter(p) => p.fmt(f),
+ Self::Call(c) => c.fmt(f),
+ }
+ }
+}
+
+impl From<Epsilon> for Expression {
+ fn from(eps: Epsilon) -> Self {
+ Self::Epsilon(eps)
+ }
+}
+
+impl From<Literal> for Expression {
+ fn from(lit: Literal) -> Self {
+ Self::Literal(lit)
+ }
+}
+
+impl From<Cat> for Expression {
+ fn from(cat: Cat) -> Self {
+ Self::Cat(cat)
+ }
+}
+
+impl From<Alt> for Expression {
+ fn from(alt: Alt) -> Self {
+ Self::Alt(alt)
+ }
+}
+
+impl From<Fix> for Expression {
+ fn from(fix: Fix) -> Self {
+ Self::Fix(fix)
+ }
+}
+
+impl From<Variable> for Expression {
+ fn from(var: Variable) -> Self {
+ Self::Variable(var)
+ }
+}
+
+impl From<Parameter> for Expression {
+ fn from(param: Parameter) -> Self {
+ Self::Parameter(param)
+ }
+}
+
+impl From<Call> for Expression {
+ fn from(call: Call) -> Self {
+ Self::Call(call)
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct Function {
+ pub name: Ident,
+ pub params: usize,
+ pub expr: Expression,
+ pub span: Option<Span>,
+}
+
+impl Function {
+ pub fn new(name: Ident, params: usize, expr: Expression, span: Option<Span>) -> Self {
+ Self {
+ name,
+ params,
+ expr,
+ span,
+ }
+ }
+}
diff --git a/src/chomp/check.rs b/src/chomp/check.rs
new file mode 100644
index 0000000..cb4798c
--- /dev/null
+++ b/src/chomp/check.rs
@@ -0,0 +1,481 @@
+use proc_macro2::Span;
+
+use super::{
+ ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Function, Literal, Parameter, Variable},
+ context::Context,
+ error::{AltError, CatError, FixError, SubstituteError, TypeError},
+ set::{FirstSet, FlastSet},
+ typed::{self, Type, TypedExpression},
+ visit::{Folder, Mapper, Visitable, Visitor},
+};
+
+/// Test if term is closed for a context with `depth` variables.
+#[derive(Debug, Default)]
+struct Closed {
+ depth: usize,
+}
+
+impl Visitor for Closed {
+ type Out = bool;
+
+ fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+ true
+ }
+
+ fn visit_literal(&mut self, _lit: &Literal) -> Self::Out {
+ true
+ }
+
+ fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+ cat.first().visit(self) && cat.second().visit(self)
+ }
+
+ fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+ alt.left().visit(self) && alt.right().visit(self)
+ }
+
+ fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+ self.depth += 1;
+ let res = fix.inner().visit(self);
+ self.depth -= 1;
+ res
+ }
+
+ fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+ var.index() < self.depth
+ }
+
+ fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+ true
+ }
+
+ fn visit_call(&mut self, call: &Call) -> Self::Out {
+ call.args().iter().all(|arg| arg.visit(self))
+ }
+}
+
+#[derive(Clone, Copy, Debug)]
+pub struct Spanning;
+
+impl Visitor for Spanning {
+ type Out = Option<Span>;
+
+ fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out {
+ Some(eps.span)
+ }
+
+ fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+ Some(lit.span())
+ }
+
+ fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+ let fst = cat.first().visit(self);
+ let snd = cat.second().visit(self);
+
+ match (fst, snd) {
+ (None, snd) => snd,
+ (Some(fst), None) => Some(fst),
+ (Some(fst), Some(snd)) => fst.join(snd),
+ }
+ }
+
+ fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+ let left = alt.left().visit(self);
+ let right = alt.right().visit(self);
+
+ match (left, right) {
+ (None, right) => right,
+ (Some(left), None) => Some(left),
+ (Some(left), Some(right)) => left.join(right),
+ }
+ }
+
+ fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+ fix.span()
+ }
+
+ fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+ Some(var.name().span())
+ }
+
+ fn visit_parameter(&mut self, param: &Parameter) -> Self::Out {
+ Some(param.name().span())
+ }
+
+ fn visit_call(&mut self, call: &Call) -> Self::Out {
+ call.span()
+ }
+}
+
+#[derive(Debug)]
+pub struct TypeInfer<'a> {
+ context: &'a mut Context,
+}
+
+impl Visitor for TypeInfer<'_> {
+ type Out = Result<Type, TypeError>;
+
+ fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+ Ok(Type::new(true, FirstSet::default(), FlastSet::default()))
+ }
+
+ fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+ Ok(Type::of_str(&lit.value()))
+ }
+
+ fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+ let first = cat.first().visit(self)?;
+ let second = self
+ .context
+ .with_unguard(|context| cat.second().visit(&mut TypeInfer { context }))?;
+
+ if first.nullable() {
+ Err(TypeError::Cat(CatError::FirstNullable(cat.clone())))
+ } else if !first
+ .flast_set()
+ .intersect_first(second.first_set())
+ .is_empty()
+ {
+ Err(TypeError::Cat(CatError::FirstFlastOverlap(cat.clone())))
+ } else {
+ Ok(first.cat(second))
+ }
+ }
+
+ fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+ let left = alt.left().visit(self)?;
+ let right = alt.right().visit(self)?;
+
+ if left.nullable() && right.nullable() {
+ Err(TypeError::Alt(AltError::BothNullable(alt.clone())))
+ } else if !left.first_set().intersect(right.first_set()).is_empty() {
+ Err(TypeError::Alt(AltError::FirstOverlap(alt.clone())))
+ } else {
+ Ok(left.alt(right))
+ }
+ }
+
+ fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+ let mut res = Type::default();
+ let mut last = None;
+
+ while last.map(|r| r != res).unwrap_or(true) {
+ last = Some(res);
+ res = self
+ .context
+ .with_variable_type(last.as_ref().cloned().unwrap(), |context| {
+ fix.inner().visit(&mut TypeInfer { context })
+ })
+ .map_err(|e| {
+ TypeError::Fix(FixError(
+ fix.clone(),
+ last.as_ref().cloned().unwrap(),
+ Box::new(e),
+ ))
+ })?;
+ }
+
+ Ok(res)
+ }
+
+ fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+ Ok(self.context.get_variable_type(&var)?.clone())
+ }
+
+ fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+ todo!()
+ }
+
+ fn visit_call(&mut self, _call: &Call) -> Self::Out {
+ todo!()
+ }
+}
+
+#[derive(Debug)]
+pub struct TypeCheck<'a> {
+ pub context: &'a mut Context,
+}
+
+impl Folder for TypeCheck<'_> {
+ type Out = Result<TypedExpression, TypeError>;
+
+ fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+ Ok(typed::Epsilon::from(eps).into())
+ }
+
+ fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+ Ok(typed::Literal::from(lit).into())
+ }
+
+ fn fold_cat(&mut self, cat: Cat) -> Self::Out {
+ let ty = TypeInfer {
+ context: self.context,
+ }
+ .visit_cat(&cat)?;
+ let fst = cat.fst.fold(self)?;
+ let snd = cat.snd;
+ let snd = self
+ .context
+ .with_unguard(|context| snd.fold(&mut TypeCheck { context }))?;
+
+ Ok(typed::Cat::new(fst, cat.punct, snd, ty).into())
+ }
+
+ fn fold_alt(&mut self, alt: Alt) -> Self::Out {
+ let ty = TypeInfer {
+ context: self.context,
+ }
+ .visit_alt(&alt)?;
+ let left = alt.left.fold(self)?;
+ let right = alt.right.fold(self)?;
+
+ Ok(typed::Alt::new(left, alt.punct, right, ty).into())
+ }
+
+ fn fold_fix(&mut self, fix: Fix) -> Self::Out {
+ let ty = TypeInfer {
+ context: self.context,
+ }
+ .visit_fix(&fix)?;
+ let inner = fix.inner;
+ let inner = self
+ .context
+ .with_variable_type(ty.clone(), |context| inner.fold(&mut TypeCheck { context }))?;
+
+ Ok(typed::Fix::new(fix.arg, inner, fix.span, ty).into())
+ }
+
+ fn fold_variable(&mut self, var: Variable) -> Self::Out {
+ let ty = TypeInfer {
+ context: self.context,
+ }
+ .visit_variable(&var)?;
+ Ok(typed::Variable::new(var, ty).into())
+ }
+
+ fn fold_parameter(&mut self, _param: Parameter) -> Self::Out {
+ todo!()
+ }
+
+ fn fold_call(&mut self, _call: Call) -> Self::Out {
+ todo!()
+ }
+}
+
+#[derive(Debug, Default)]
+struct DeepenVars {
+ depth: usize,
+}
+
+impl Mapper for DeepenVars {
+ type Out = ();
+
+ fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+ fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+ fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+ cat.first_mut().map(self);
+ cat.second_mut().map(self);
+ }
+
+ fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+ alt.left_mut().map(self);
+ alt.right_mut().map(self);
+ }
+
+ fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+ self.depth += 1;
+ fix.inner_mut().map(self);
+ self.depth -= 1;
+ }
+
+ fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+ if bind.index() >= self.depth {
+ *bind.index_mut() += 1;
+ }
+ }
+
+ fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+ fn map_call(&mut self, call: &mut Call) -> Self::Out {
+ for arg in call.args_mut() {
+ arg.map(self);
+ }
+ }
+}
+
+#[derive(Debug, Default)]
+struct ShallowVars {
+ depth: usize,
+}
+
+impl Mapper for ShallowVars {
+ type Out = ();
+
+ fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+ fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+ fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+ cat.first_mut().map(self);
+ cat.second_mut().map(self);
+ }
+
+ fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+ alt.left_mut().map(self);
+ alt.right_mut().map(self);
+ }
+
+ fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+ self.depth += 1;
+ fix.inner_mut().map(self);
+ self.depth -= 1;
+ }
+
+ fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+ if bind.index() > self.depth {
+ *bind.index_mut() -= 1;
+ }
+ }
+
+ fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+ fn map_call(&mut self, call: &mut Call) -> Self::Out {
+ for arg in call.args_mut() {
+ arg.map(self);
+ }
+ }
+}
+
+struct Substitute {
+ params: Vec<Expression>,
+}
+
+impl Folder for Substitute {
+ type Out = Result<Expression, SubstituteError>;
+
+ fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+ Ok(eps.into())
+ }
+
+ fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+ Ok(lit.into())
+ }
+
+ fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+ cat.fst = Box::new(cat.fst.fold(self)?);
+ cat.snd = Box::new(cat.snd.fold(self)?);
+ Ok(cat.into())
+ }
+
+ fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+ alt.left = Box::new(alt.left.fold(self)?);
+ alt.right = Box::new(alt.right.fold(self)?);
+ Ok(alt.into())
+ }
+
+ fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+ for param in &mut self.params {
+ param.map(&mut DeepenVars::default());
+ }
+
+ fix.inner = Box::new(fix.inner.fold(self)?);
+
+ for param in &mut self.params {
+ param.map(&mut ShallowVars::default());
+ }
+
+ Ok(fix.into())
+ }
+
+ fn fold_variable(&mut self, var: Variable) -> Self::Out {
+ Ok(Expression::Variable(var))
+ }
+
+ fn fold_call(&mut self, mut call: Call) -> Self::Out {
+ call.args = call
+ .args
+ .into_iter()
+ .map(|arg| arg.fold(self))
+ .collect::<Result<_, _>>()?;
+ Ok(call.into())
+ }
+
+ fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+ self.params
+ .get(param.index())
+ .cloned()
+ .ok_or(SubstituteError::FreeParameter(param))
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct InlineCall {
+ function: Function,
+}
+
+impl InlineCall {
+ pub fn new(function: Function) -> Self {
+ Self { function }
+ }
+}
+
+impl Folder for InlineCall {
+ type Out = Result<Expression, SubstituteError>;
+
+ fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+ Ok(eps.into())
+ }
+
+ fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+ Ok(lit.into())
+ }
+
+ fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+ cat.fst = Box::new(cat.fst.fold(self)?);
+ cat.snd = Box::new(cat.snd.fold(self)?);
+ Ok(cat.into())
+ }
+
+ fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+ alt.left = Box::new(alt.left.fold(self)?);
+ alt.right = Box::new(alt.right.fold(self)?);
+ Ok(alt.into())
+ }
+
+ fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+ fix.inner = Box::new(fix.inner.fold(self)?);
+ Ok(fix.into())
+ }
+
+ fn fold_variable(&mut self, var: Variable) -> Self::Out {
+ Ok(var.into())
+ }
+
+ fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+ Ok(param.into())
+ }
+
+ fn fold_call(&mut self, mut call: Call) -> Self::Out {
+ call.args = call
+ .args
+ .into_iter()
+ .map(|arg| arg.fold(self))
+ .collect::<Result<_, _>>()?;
+
+ if call.name != self.function.name {
+ Ok(call.into())
+ } else if call.args.len() != self.function.params {
+ Err(SubstituteError::WrongArgCount {
+ call,
+ expected: self.function.params,
+ })
+ } else {
+ self.function
+ .expr
+ .clone()
+ .fold(&mut Substitute { params: call.args })
+ }
+ }
+}
diff --git a/src/chomp/context.rs b/src/chomp/context.rs
new file mode 100644
index 0000000..392023f
--- /dev/null
+++ b/src/chomp/context.rs
@@ -0,0 +1,51 @@
+use super::{ast::Variable, error::VariableError, typed::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 is_unguarded(&self, var: &Variable) -> Option<bool> {
+ if self.vars.len() <= var.index() {
+ None
+ } else if self.unguard_points.is_empty() {
+ Some(false)
+ } else {
+ Some(
+ self.unguard_points[self.unguard_points.len() - 1] + var.index() >= 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, VariableError> {
+ match self.is_unguarded(var) {
+ None => Err(VariableError::FreeVariable(var.clone())),
+ Some(false) => Err(VariableError::GuardedVariable(var.clone())),
+ Some(true) => Ok(&self.vars[self.vars.len() - var.index() - 1]),
+ }
+ }
+
+ 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
+ }
+}
diff --git a/src/chomp/error.rs b/src/chomp/error.rs
new file mode 100644
index 0000000..6733d06
--- /dev/null
+++ b/src/chomp/error.rs
@@ -0,0 +1,389 @@
+use std::{
+ error::Error,
+ fmt::{self, Display},
+};
+
+use proc_macro2::Span;
+
+use super::{
+ ast::{Alt, Call, Cat, Fix, Parameter, Variable},
+ check::Spanning,
+ typed::Type,
+ visit::Visitable,
+};
+
+/// A type error when using a fix point variable.
+#[derive(Debug)]
+pub enum VariableError {
+ /// Usage of a free variable.
+ FreeVariable(Variable),
+ /// Usage of a guarded variable.
+ GuardedVariable(Variable),
+}
+
+impl From<VariableError> for syn::Error {
+ fn from(other: VariableError) -> Self {
+ match other {
+ VariableError::FreeVariable(_) => todo!(),
+ VariableError::GuardedVariable(_) => todo!(),
+ }
+ }
+}
+
+impl Display for VariableError {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Self::FreeVariable(var) => {
+ let start = var.name().span().start();
+ write!(
+ f,
+ "{}:{}: unbound variable '{}'",
+ start.line,
+ start.column,
+ var.name()
+ )
+ }
+ Self::GuardedVariable(var) => {
+ let start = var.name().span().start();
+ write!(
+ f,
+ "{}:{}: variable '{}' is guarded",
+ start.line,
+ start.column,
+ var.name()
+ )
+ }
+ }
+ }
+}
+
+impl Error for VariableError {}
+
+/// A type error when concatenating two terms.
+#[derive(Debug)]
+pub enum CatError {
+ /// The first term was unexpectedly nullable.
+ FirstNullable(Cat),
+ /// The flast set of the first term intersects the first set of the second.
+ FirstFlastOverlap(Cat),
+}
+
+impl From<CatError> for syn::Error {
+ fn from(other: CatError) -> Self {
+ match other {
+ CatError::FirstNullable(cat) => {
+ let mut err = Self::new(
+ cat.punct().map_or_else(Span::call_site, |p| p.span),
+ "first item in sequence cannot accept the empty string",
+ );
+ err.combine(Self::new(
+ cat.first()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site),
+ "this can accept empty string",
+ ));
+ err
+ }
+ CatError::FirstFlastOverlap(cat) => {
+ let mut err = Self::new(
+ cat.punct().map_or_else(Span::call_site, |p| p.span),
+ "cannot decide whether to repeat first or start accepting second",
+ );
+ err.combine(Self::new(
+ cat.first()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site),
+ "a repetition of this",
+ ));
+ err.combine(Self::new(
+ cat.second()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site),
+ "collides with the start of this",
+ ));
+ err
+ }
+ }
+ }
+}
+
+impl Display for CatError {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Self::FirstNullable(cat) => {
+ let start = cat.punct().map_or_else(Span::call_site, |p| p.span).start();
+ let fst_start = cat
+ .first()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site)
+ .start();
+ write!(
+ f,
+ "{}:{}: term `{}' ({}:{}) accepts the empty string",
+ start.line,
+ start.column,
+ cat.first(),
+ fst_start.line,
+ fst_start.column
+ )
+ }
+ Self::FirstFlastOverlap(cat) => {
+ let start = cat.punct().map_or_else(Span::call_site, |p| p.span).start();
+ let fst_start = cat
+ .first()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site)
+ .start();
+ let snd_start = cat
+ .second()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site)
+ .start();
+ write!(
+ f,
+ "{}:{}: cannot decide whether to repeat `{}' ({}:{}) or start accepting `{}' ({}:{}).",
+ start.line,
+ start.column,
+ cat.first(),
+ fst_start.line,
+ fst_start.column,
+ cat.second(),
+ snd_start.line,
+ snd_start.column
+ )
+ }
+ }
+ }
+}
+
+impl Error for CatError {}
+
+/// A type error when alternating two terms.
+#[derive(Debug)]
+pub enum AltError {
+ /// Both terms are nullable.
+ BothNullable(Alt),
+ /// The first sets of the two terms intersect.
+ FirstOverlap(Alt),
+}
+
+impl From<AltError> for syn::Error {
+ fn from(other: AltError) -> Self {
+ match other {
+ AltError::BothNullable(alt) => {
+ let mut err = Self::new(
+ alt.punct().map_or_else(Span::call_site, |p| p.span),
+ "both branches accept the empty string",
+ );
+ err.combine(Self::new(
+ alt.left()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site),
+ "left branch accepts the empty string",
+ ));
+ err.combine(Self::new(
+ alt.right()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site),
+ "right branch accepts the empty string",
+ ));
+ err
+ }
+ AltError::FirstOverlap(alt) => {
+ let mut err = Self::new(
+ alt.punct().map_or_else(Span::call_site, |p| p.span),
+ "cannot decide whether to accept the left or right branch",
+ );
+ err.combine(Self::new(
+ alt.left()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site),
+ "left branch starts with a character",
+ ));
+ err.combine(Self::new(
+ alt.right()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site),
+ "right branch starts with the same character",
+ ));
+ err
+ }
+ }
+ }
+}
+
+impl Display for AltError {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Self::BothNullable(alt) => {
+ let start = alt.punct().map_or_else(Span::call_site, |p| p.span).start();
+ let left_start = alt
+ .left()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site)
+ .start();
+ let right_start = alt
+ .right()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site)
+ .start();
+ write!(
+ f,
+ "{}:{}: both `{}' ({}:{}) and `{}' ({}:{}) accept the empty string.",
+ start.line,
+ start.column,
+ alt.left(),
+ left_start.line,
+ left_start.column,
+ alt.right(),
+ right_start.line,
+ right_start.column,
+ )
+ }
+ Self::FirstOverlap(alt) => {
+ let start = alt.punct().map_or_else(Span::call_site, |p| p.span).start();
+ let left_start = alt
+ .left()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site)
+ .start();
+ let right_start = alt
+ .right()
+ .visit(&mut Spanning)
+ .unwrap_or_else(Span::call_site)
+ .start();
+ write!(
+ f,
+ "{}:{}: cannot decide whether to accept `{}' ({}:{}) or `{}' ({}:{}).",
+ start.line,
+ start.column,
+ alt.left(),
+ left_start.line,
+ left_start.column,
+ alt.right(),
+ right_start.line,
+ right_start.column,
+ )
+ }
+ }
+ }
+}
+
+impl Error for AltError {}
+
+#[derive(Debug)]
+pub struct FixError(pub Fix, pub Type, pub Box<TypeError>);
+
+impl From<FixError> for syn::Error {
+ fn from(e: FixError) -> Self {
+ let mut error = Self::from(*e.2);
+ error.combine(Self::new(
+ e.0.span().unwrap_or_else(Span::call_site),
+ format!("assuming `{}' has type {:?}.", e.0.arg(), e.1),
+ ));
+ error
+ }
+}
+
+impl Display for FixError {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.2.fmt(f)?;
+ let start = self.0.span().unwrap_or_else(Span::call_site).start();
+ write!(
+ f,
+ "\n({}:{}) assuming `{}' has type {:?}.",
+ start.line,
+ start.column,
+ self.0.arg(),
+ self.1
+ )
+ }
+}
+
+impl Error for FixError {}
+
+#[derive(Debug)]
+pub enum TypeError {
+ Cat(CatError),
+ Alt(AltError),
+ Variable(VariableError),
+ Fix(FixError),
+}
+
+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(),
+ TypeError::Fix(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),
+ Self::Fix(e) => e.fmt(f),
+ }
+ }
+}
+
+impl Error for TypeError {}
+
+#[derive(Debug)]
+pub enum SubstituteError {
+ FreeParameter(Parameter),
+ WrongArgCount { call: Call, expected: usize },
+}
+
+impl Display for SubstituteError {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Self::FreeParameter(param) => {
+ let start = param.name().span().start();
+ write!(
+ f,
+ "{}:{}: undeclared variable `{}'",
+ start.line,
+ start.column,
+ param.name()
+ )
+ }
+ SubstituteError::WrongArgCount { call, expected } => {
+ let start = call.span().unwrap_or_else(Span::call_site).start();
+ write!(
+ f,
+ "{}:{}: wrong number of arguments. Expected {}, got {}",
+ start.line,
+ start.column,
+ call.args().len(),
+ expected
+ )
+ }
+ }
+ }
+}
+
+impl Error for SubstituteError {}
diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs
new file mode 100644
index 0000000..bb31b6f
--- /dev/null
+++ b/src/chomp/mod.rs
@@ -0,0 +1,7 @@
+pub mod ast;
+pub mod check;
+pub mod context;
+pub mod error;
+pub mod set;
+pub mod typed;
+pub mod visit;
diff --git a/src/chomp/set.rs b/src/chomp/set.rs
new file mode 100644
index 0000000..0661ab6
--- /dev/null
+++ b/src/chomp/set.rs
@@ -0,0 +1,91 @@
+use std::collections::BTreeSet;
+
+#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)]
+pub struct FirstSet {
+ inner: BTreeSet<char>,
+}
+
+impl FirstSet {
+ pub fn new() -> Self {
+ Self::default()
+ }
+
+ pub fn of_str(s: &str) -> Self {
+ let mut inner = BTreeSet::new();
+ s.chars().next().map(|c| inner.insert(c));
+
+ Self { inner }
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.inner.is_empty()
+ }
+
+ pub fn union(mut self, mut other: Self) -> Self {
+ self.inner.append(&mut other.inner);
+ self
+ }
+
+ pub fn intersect(&self, other: &Self) -> Self {
+ Self {
+ inner: self.inner.intersection(&other.inner).copied().collect(),
+ }
+ }
+}
+
+impl IntoIterator for FirstSet {
+ type Item = char;
+
+ type IntoIter = <BTreeSet<char> as IntoIterator>::IntoIter;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.inner.into_iter()
+ }
+}
+
+#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)]
+pub struct FlastSet {
+ inner: BTreeSet<char>,
+}
+
+impl FlastSet {
+ pub fn new() -> Self {
+ Self::default()
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.inner.is_empty()
+ }
+
+ pub fn union_first(mut self, mut other: FirstSet) -> Self {
+ self.inner.append(&mut other.inner);
+ self
+ }
+
+ pub fn union(mut self, mut other: Self) -> Self {
+ self.inner.append(&mut other.inner);
+ self
+ }
+
+ pub fn intersect_first(&self, other: &FirstSet) -> Self {
+ Self {
+ inner: self.inner.intersection(&other.inner).copied().collect(),
+ }
+ }
+
+ pub fn intersect(&self, other: &Self) -> Self {
+ Self {
+ inner: self.inner.intersection(&other.inner).copied().collect(),
+ }
+ }
+}
+
+impl IntoIterator for FlastSet {
+ type Item = char;
+
+ type IntoIter = <BTreeSet<char> as IntoIterator>::IntoIter;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.inner.into_iter()
+ }
+}
diff --git a/src/chomp/typed.rs b/src/chomp/typed.rs
new file mode 100644
index 0000000..69108ae
--- /dev/null
+++ b/src/chomp/typed.rs
@@ -0,0 +1,321 @@
+use std::hash::{Hash, Hasher};
+
+use proc_macro2::Span;
+use syn::{Ident, LitStr, Token};
+
+use super::{
+ ast,
+ set::{FirstSet, FlastSet},
+};
+
+#[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(Debug, Eq, Hash, PartialEq)]
+pub struct Epsilon {
+ inner: Token![_],
+ ty: Type,
+}
+
+impl From<ast::Epsilon> for Epsilon {
+ fn from(inner: ast::Epsilon) -> Self {
+ Self {
+ inner,
+ ty: Type::new(true, FirstSet::default(), FlastSet::default()),
+ }
+ }
+}
+
+#[derive(Debug, Eq, Hash, PartialEq)]
+pub struct Literal {
+ inner: LitStr,
+ ty: Type,
+}
+
+impl Literal {
+ pub fn inner(&self) -> &LitStr {
+ &self.inner
+ }
+
+ pub fn span(&self) -> Span {
+ self.inner.span()
+ }
+}
+
+impl From<ast::Literal> for Literal {
+ fn from(inner: ast::Literal) -> Self {
+ let ty = Type::of_str(&inner.value());
+ Self { inner, ty }
+ }
+}
+
+#[derive(Debug, Eq, Hash, PartialEq)]
+pub struct Cat {
+ fst: Box<TypedExpression>,
+ punct: Option<Token![.]>,
+ snd: Box<TypedExpression>,
+ ty: Type,
+}
+
+impl Cat {
+ pub(crate) fn new(
+ fst: TypedExpression,
+ punct: Option<Token![.]>,
+ snd: TypedExpression,
+ ty: Type,
+ ) -> Self {
+ Self {
+ fst: Box::new(fst),
+ punct,
+ snd: Box::new(snd),
+ ty,
+ }
+ }
+
+ pub fn unwrap(self) -> (TypedExpression, Option<Token![.]>, TypedExpression) {
+ (*self.fst, self.punct, *self.snd)
+ }
+}
+
+#[derive(Debug, Eq, Hash, PartialEq)]
+pub struct Alt {
+ left: Box<TypedExpression>,
+ punct: Option<Token![|]>,
+ right: Box<TypedExpression>,
+ ty: Type,
+}
+
+impl Alt {
+ pub(crate) fn new(
+ left: TypedExpression,
+ punct: Option<Token![|]>,
+ right: TypedExpression,
+ ty: Type,
+ ) -> Self {
+ Self {
+ left: Box::new(left),
+ punct,
+ right: Box::new(right),
+ ty,
+ }
+ }
+
+ pub fn unwrap(self) -> (TypedExpression, Option<Token![|]>, TypedExpression) {
+ (*self.left, self.punct, *self.right)
+ }
+}
+
+#[derive(Debug)]
+pub struct Fix {
+ arg: Ident,
+ inner: Box<TypedExpression>,
+ span: Option<Span>,
+ ty: Type,
+}
+
+impl Fix {
+ pub(crate) fn new(arg: Ident, inner: TypedExpression, span: Option<Span>, ty: Type) -> Self {
+ Self {
+ arg,
+ inner: Box::new(inner),
+ span,
+ ty,
+ }
+ }
+
+ pub fn unwrap(self) -> (Ident, TypedExpression, Option<Span>) {
+ (self.arg, *self.inner, self.span)
+ }
+}
+
+impl PartialEq for Fix {
+ fn eq(&self, other: &Self) -> bool {
+ self.arg == other.arg && self.inner == other.inner && self.ty == other.ty
+ }
+}
+
+impl Eq for Fix {}
+
+impl Hash for Fix {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ self.arg.hash(state);
+ self.inner.hash(state);
+ self.ty.hash(state);
+ }
+}
+
+#[derive(Debug, Eq, Hash, PartialEq)]
+pub struct Variable {
+ ident: Ident,
+ index: usize,
+ ty: Type,
+}
+
+impl Variable {
+ pub(crate) fn new(var: ast::Variable, ty: Type) -> Self {
+ Self {
+ ident: var.name,
+ index: var.index,
+ ty,
+ }
+ }
+
+ pub fn index(&self) -> usize {
+ self.index
+ }
+}
+
+#[derive(Debug, Eq, Hash, PartialEq)]
+pub(crate) enum RawTypedExpression {
+ Epsilon(Epsilon),
+ Literal(Literal),
+ Cat(Cat),
+ Alt(Alt),
+ Fix(Fix),
+ Variable(Variable),
+}
+
+#[derive(Debug, Eq, Hash, PartialEq)]
+pub struct TypedExpression {
+ pub(crate) inner: RawTypedExpression,
+}
+
+impl From<Epsilon> for TypedExpression {
+ fn from(eps: Epsilon) -> Self {
+ Self {
+ inner: RawTypedExpression::Epsilon(eps),
+ }
+ }
+}
+
+impl From<Literal> for TypedExpression {
+ fn from(lit: Literal) -> Self {
+ Self {
+ inner: RawTypedExpression::Literal(lit),
+ }
+ }
+}
+
+impl From<Cat> for TypedExpression {
+ fn from(cat: Cat) -> Self {
+ Self {
+ inner: RawTypedExpression::Cat(cat),
+ }
+ }
+}
+
+impl From<Alt> for TypedExpression {
+ fn from(alt: Alt) -> Self {
+ Self {
+ inner: RawTypedExpression::Alt(alt),
+ }
+ }
+}
+
+impl From<Fix> for TypedExpression {
+ fn from(fix: Fix) -> Self {
+ Self {
+ inner: RawTypedExpression::Fix(fix),
+ }
+ }
+}
+
+impl From<Variable> for TypedExpression {
+ fn from(var: Variable) -> Self {
+ Self {
+ inner: RawTypedExpression::Variable(var),
+ }
+ }
+}
+
+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!(Fix, ty);
+leaf_typed!(Variable, ty);
+
+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(),
+ }
+ }
+}
diff --git a/src/chomp/visit.rs b/src/chomp/visit.rs
new file mode 100644
index 0000000..4113b64
--- /dev/null
+++ b/src/chomp/visit.rs
@@ -0,0 +1,136 @@
+use super::ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Literal, Parameter, Variable};
+
+pub trait Visitor {
+ type Out;
+ fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out;
+
+ fn visit_literal(&mut self, lit: &Literal) -> Self::Out;
+
+ fn visit_cat(&mut self, cat: &Cat) -> Self::Out;
+
+ fn visit_alt(&mut self, alt: &Alt) -> Self::Out;
+
+ fn visit_fix(&mut self, fix: &Fix) -> Self::Out;
+
+ fn visit_variable(&mut self, var: &Variable) -> Self::Out;
+
+ fn visit_parameter(&mut self, param: &Parameter) -> Self::Out;
+
+ fn visit_call(&mut self, call: &Call) -> Self::Out;
+}
+
+pub trait Mapper {
+ type Out;
+
+ fn map_epsilon(&mut self, eps: &mut Epsilon) -> Self::Out;
+
+ fn map_literal(&mut self, lit: &mut Literal) -> Self::Out;
+
+ fn map_cat(&mut self, cat: &mut Cat) -> Self::Out;
+
+ fn map_alt(&mut self, alt: &mut Alt) -> Self::Out;
+
+ fn map_fix(&mut self, fix: &mut Fix) -> Self::Out;
+
+ fn map_variable(&mut self, var: &mut Variable) -> Self::Out;
+
+ fn map_parameter(&mut self, param: &mut Parameter) -> Self::Out;
+
+ fn map_call(&mut self, call: &mut Call) -> Self::Out;
+}
+
+pub trait Folder {
+ type Out;
+
+ fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out;
+
+ fn fold_literal(&mut self, lit: Literal) -> Self::Out;
+
+ fn fold_cat(&mut self, cat: Cat) -> Self::Out;
+
+ fn fold_alt(&mut self, alt: Alt) -> Self::Out;
+
+ fn fold_fix(&mut self, fix: Fix) -> Self::Out;
+
+ fn fold_variable(&mut self, var: Variable) -> Self::Out;
+
+ fn fold_parameter(&mut self, param: Parameter) -> Self::Out;
+
+ fn fold_call(&mut self, call: Call) -> Self::Out;
+}
+
+pub trait Visitable {
+ fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out;
+
+ fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out;
+
+ fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out;
+}
+
+macro_rules! visitable_leaf {
+ ($ty:ty, $visit:ident, $map:ident, $fold:ident) => {
+ impl Visitable for $ty {
+ fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
+ visitor.$visit(self)
+ }
+
+ fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out {
+ mapper.$map(self)
+ }
+
+ fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out {
+ folder.$fold(self)
+ }
+ }
+ };
+}
+
+visitable_leaf!(Epsilon, visit_epsilon, map_epsilon, fold_epsilon);
+visitable_leaf!(Literal, visit_literal, map_literal, fold_literal);
+visitable_leaf!(Cat, visit_cat, map_cat, fold_cat);
+visitable_leaf!(Alt, visit_alt, map_alt, fold_alt);
+visitable_leaf!(Fix, visit_fix, map_fix, fold_fix);
+visitable_leaf!(Variable, visit_variable, map_variable, fold_variable);
+visitable_leaf!(Parameter, visit_parameter, map_parameter, fold_parameter);
+visitable_leaf!(Call, visit_call, map_call, fold_call);
+
+impl Visitable for Expression {
+ fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
+ match self {
+ Self::Epsilon(e) => visitor.visit_epsilon(e),
+ Self::Literal(l) => visitor.visit_literal(l),
+ Self::Cat(c) => visitor.visit_cat(c),
+ Self::Alt(a) => visitor.visit_alt(a),
+ Self::Fix(f) => visitor.visit_fix(f),
+ Self::Variable(v) => visitor.visit_variable(v),
+ Self::Parameter(p) => visitor.visit_parameter(p),
+ Self::Call(c) => visitor.visit_call(c),
+ }
+ }
+
+ fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out {
+ match self {
+ Self::Epsilon(e) => mapper.map_epsilon(e),
+ Self::Literal(l) => mapper.map_literal(l),
+ Self::Cat(c) => mapper.map_cat(c),
+ Self::Alt(a) => mapper.map_alt(a),
+ Self::Fix(f) => mapper.map_fix(f),
+ Self::Variable(v) => mapper.map_variable(v),
+ Self::Parameter(p) => mapper.map_parameter(p),
+ Self::Call(c) => mapper.map_call(c),
+ }
+ }
+
+ fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out {
+ match self {
+ Self::Epsilon(e) => folder.fold_epsilon(e),
+ Self::Literal(l) => folder.fold_literal(l),
+ Self::Cat(c) => folder.fold_cat(c),
+ Self::Alt(a) => folder.fold_alt(a),
+ Self::Fix(f) => folder.fold_fix(f),
+ Self::Variable(v) => folder.fold_variable(v),
+ Self::Parameter(p) => folder.fold_parameter(p),
+ Self::Call(c) => folder.fold_call(c),
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.49.0) at 2025-04-30 15:56:01 +0000