diff options
Diffstat (limited to 'src/chomp')
| -rw-r--r-- | src/chomp/ast/error.rs | 27 | ||||
| -rw-r--r-- | src/chomp/ast/mod.rs (renamed from src/chomp/ast.rs) | 325 | ||||
| -rw-r--r-- | src/chomp/ast/substitute.rs | 439 | ||||
| -rw-r--r-- | src/chomp/check/check.rs | 81 | ||||
| -rw-r--r-- | src/chomp/check/closed.rs | 50 | ||||
| -rw-r--r-- | src/chomp/check/deepen.rs | 47 | ||||
| -rw-r--r-- | src/chomp/check/infer.rs | 92 | ||||
| -rw-r--r-- | src/chomp/check/inline.rs | 349 | ||||
| -rw-r--r-- | src/chomp/check/mod.rs | 17 | ||||
| -rw-r--r-- | src/chomp/check/shallow.rs | 47 | ||||
| -rw-r--r-- | src/chomp/check/spanning.rs | 59 | ||||
| -rw-r--r-- | src/chomp/check/substitute.rs | 77 | ||||
| -rw-r--r-- | src/chomp/error.rs | 402 | ||||
| -rw-r--r-- | src/chomp/mod.rs | 36 | ||||
| -rw-r--r-- | src/chomp/typed.rs | 323 | ||||
| -rw-r--r-- | src/chomp/typed/context.rs (renamed from src/chomp/context.rs) | 24 | ||||
| -rw-r--r-- | src/chomp/typed/error.rs | 150 | ||||
| -rw-r--r-- | src/chomp/typed/infer.rs | 145 | ||||
| -rw-r--r-- | src/chomp/typed/lower.rs | 41 | ||||
| -rw-r--r-- | src/chomp/typed/mod.rs | 343 | ||||
| -rw-r--r-- | src/chomp/visit.rs | 219 |
21 files changed, 1390 insertions, 1903 deletions
diff --git a/src/chomp/ast/error.rs b/src/chomp/ast/error.rs new file mode 100644 index 0000000..d2c49cd --- /dev/null +++ b/src/chomp/ast/error.rs @@ -0,0 +1,27 @@ +use std::{error::Error, fmt::{self, Display}}; + +use proc_macro2::Span; + +use crate::chomp::Name; + +use super::{Call, Parameter}; + +#[derive(Debug)] +pub enum SubstituteError { + FreeParameter { param: Parameter, span: Option<Span>, name: Option<Name> }, + WrongArgCount { call: Call, expected: usize, span: Option<Span> }, +} + +impl From<SubstituteError> for syn::Error { + fn from(e: SubstituteError) -> Self { + todo!() + } +} + +impl Display for SubstituteError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + todo!() + } +} + +impl Error for SubstituteError {} diff --git a/src/chomp/ast.rs b/src/chomp/ast/mod.rs index 76d75ae..110e5c0 100644 --- a/src/chomp/ast.rs +++ b/src/chomp/ast/mod.rs @@ -1,127 +1,46 @@ -use std::{ - fmt::{self, Display}, - hash, -}; +use std::fmt::{self, Display}; use proc_macro2::Span; -use syn::{Ident, LitStr, Token}; +use syn::Token; use super::Name; -pub type Epsilon = Option<Token![_]>; +pub mod error; +pub mod substitute; -#[derive(Clone, Debug)] -pub enum Literal { - Spanned(LitStr), - Spanless(String), -} +#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)] +pub struct Epsilon; -impl Literal { - pub fn value(&self) -> String { - match self { - Self::Spanned(l) => l.value(), - Self::Spanless(s) => s.clone(), - } - } - - pub fn span(&self) -> Option<Span> { - match self { - Self::Spanned(l) => Some(l.span()), - Self::Spanless(_) => None, - } - } - - pub fn as_litstr(self, span: Span) -> LitStr { - match self { - Self::Spanned(l) => l, - Self::Spanless(s) => LitStr::new(&s, span), - } - } -} - -impl PartialEq for Literal { - fn eq(&self, other: &Self) -> bool { - match (self, other) { - (Self::Spanned(me), Self::Spanned(them)) => me == them, - (Self::Spanned(me), Self::Spanless(them)) => &me.value() == them, - (Self::Spanless(me), Self::Spanned(them)) => me == &them.value(), - (Self::Spanless(me), Self::Spanless(them)) => me == them, - } - } -} - -impl Eq for Literal {} - -impl hash::Hash for Literal { - fn hash<H: hash::Hasher>(&self, state: &mut H) { - self.value().hash(state) - } -} - -impl Display for Literal { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "{:?}", self.value()) - } -} - -impl From<LitStr> for Literal { - fn from(l: LitStr) -> Self { - Self::Spanned(l) - } -} - -impl From<String> for Literal { - fn from(s: String) -> Self { - Self::Spanless(s) - } -} +pub type Literal = String; #[derive(Clone, Debug)] pub struct Cat { - pub fst: Box<Expression>, + pub first: Box<NamedExpression>, 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 - } + pub second: Box<NamedExpression>, + pub rest: Vec<(Option<Token![.]>, NamedExpression)>, } impl Display for Cat { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "({}.{})", self.fst, self.snd) + write!(f, "({} . {}", self.first, self.second)?; + for (_, other) in &self.rest { + write!(f, " . {}", other)?; + } + write!(f, ")") } } impl PartialEq for Cat { fn eq(&self, other: &Self) -> bool { - self.first() == other.first() && self.second() == other.second() + self.first == other.first + && self.second == other.second + && self.rest.len() == other.rest.len() + && self + .rest + .iter() + .zip(other.rest.iter()) + .all(|((_, me), (_, them))| me == them) } } @@ -129,50 +48,32 @@ impl Eq for Cat {} #[derive(Clone, Debug)] pub struct Alt { - pub left: Box<Expression>, + pub first: Box<NamedExpression>, 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 - } + pub second: Box<NamedExpression>, + pub rest: Vec<(Option<Token![|]>, NamedExpression)> } impl Display for Alt { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "({}|{})", self.left, self.right) + write!(f, "({} | {}", self.first, self.second)?; + for (_, other) in &self.rest { + write!(f, " | {}", other)?; + } + write!(f, ")") } } impl PartialEq for Alt { fn eq(&self, other: &Self) -> bool { - self.left() == other.left() && self.right() == other.right() + self.first == other.first + && self.second == other.second + && self.rest.len() == other.rest.len() + && self + .rest + .iter() + .zip(other.rest.iter()) + .all(|((_, me), (_, them))| me == them) } } @@ -180,46 +81,22 @@ impl Eq for Alt {} #[derive(Clone, Debug)] pub struct Fix { - pub arg: Name, - pub inner: Box<Expression>, - pub span: Option<Span>, -} - -impl Fix { - pub fn new(arg: Name, inner: Expression, span: Option<Span>) -> Self { - Self { - arg, - inner: Box::new(inner), - span, - } - } - - pub fn arg(&self) -> &Name { - &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 - } + pub arg: Option<Name>, + pub inner: Box<NamedExpression>, } impl Display for Fix { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "[{}]({})", self.arg, self.inner) + match &self.arg { + Some(arg) => write!(f, "[{}]({})", arg, self.inner), + None => write!(f, "[]({})", self.inner), + } } } impl PartialEq for Fix { fn eq(&self, other: &Self) -> bool { - self.inner() == other.inner() + self.inner == other.inner } } @@ -227,92 +104,31 @@ impl Eq for Fix {} #[derive(Clone, Debug, Eq, Hash, PartialEq)] pub struct Variable { - pub name: Name, pub index: usize, } -impl Variable { - pub fn new(name: Name, index: usize) -> Self { - Self { name, index } - } - - pub fn name(&self) -> &Name { - &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) + write!(f, "'{}", self.index) } } #[derive(Clone, Debug, Eq, Hash, PartialEq)] pub struct Parameter { - pub name: Name, pub index: usize, } -impl Parameter { - pub const fn new(name: Name, index: usize) -> Self { - Self { name, index } - } - - pub fn name(&self) -> &Name { - &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 { - write!(f, "{}", self.name) + write!(f, "<{}>", self.index) } } /// A macro invocation. -#[derive(Clone, Debug)] +#[derive(Clone, Debug, Eq, PartialEq)] pub struct Call { pub name: Name, - pub args: Vec<Expression>, - pub span: Option<Span>, -} - -impl Call { - pub fn new(name: Name, args: Vec<Expression>, span: Option<Span>) -> Self { - Self { name, args, span } - } - - pub fn name(&self) -> &Name { - &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 - } + pub args: Vec<NamedExpression>, } impl Display for Call { @@ -335,14 +151,6 @@ impl Display for Call { } } -impl PartialEq for Call { - fn eq(&self, other: &Self) -> bool { - self.name() == other.name() && self.args() == other.args() - } -} - -impl Eq for Call {} - #[derive(Clone, Debug)] pub enum Expression { /// Matches the empty string. @@ -486,20 +294,33 @@ impl From<Call> for Expression { } #[derive(Clone, Debug)] -pub struct Function { - pub name: Name, - pub params: usize, +pub struct NamedExpression { + pub name: Option<Name>, pub expr: Expression, pub span: Option<Span>, } -impl Function { - pub const fn new(name: Name, params: usize, expr: Expression, span: Option<Span>) -> Self { - Self { - name, - params, - expr, - span, +impl Display for NamedExpression { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match &self.name { + Some(name) => write!(f, "({} : {})", self.expr, name), + None => self.expr.fmt(f), } } } + +impl PartialEq for NamedExpression { + fn eq(&self, other: &Self) -> bool { + self.expr == other.expr + } +} + +impl Eq for NamedExpression {} + +#[derive(Clone, Debug)] +pub struct Function { + pub name: Name, + pub params: Vec<Option<Name>>, + pub expr: NamedExpression, + pub span: Option<Span>, +} diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs new file mode 100644 index 0000000..1a622e1 --- /dev/null +++ b/src/chomp/ast/substitute.rs @@ -0,0 +1,439 @@ +use proc_macro2::Span; + +use crate::chomp::{ + visit::{Folder, Mapper, Visitable}, + Name, +}; + +use super::{ + error::SubstituteError, Alt, Call, Cat, Epsilon, Fix, Function, Literal, NamedExpression, + Parameter, Variable, +}; + +#[derive(Clone, Copy, Debug, Default)] +pub struct DeepenVars { + pub depth: usize, +} + +impl Mapper for DeepenVars { + type Out = (); + + fn map_epsilon( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + _eps: &mut Epsilon, + ) -> Self::Out { + } + + fn map_literal( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + _lit: &mut Literal, + ) -> Self::Out { + } + + fn map_cat( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + cat: &mut Cat, + ) -> Self::Out { + cat.first.map(self); + cat.second.map(self); + + for (_, term) in &mut cat.rest { + term.map(self); + } + } + + fn map_alt( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + alt: &mut Alt, + ) -> Self::Out { + alt.first.map(self); + alt.second.map(self); + + for (_, term) in &mut alt.rest { + term.map(self); + } + } + + fn map_fix( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + fix: &mut Fix, + ) -> Self::Out { + self.depth += 1; + fix.inner.map(self); + self.depth -= 1; + } + + fn map_variable( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + var: &mut Variable, + ) -> Self::Out { + if var.index >= self.depth { + var.index += 1; + } + } + + fn map_parameter( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + _param: &mut Parameter, + ) -> Self::Out { + } + + fn map_call( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + call: &mut Call, + ) -> Self::Out { + for arg in &mut call.args { + arg.map(self) + } + } +} + +#[derive(Clone, Copy, Debug, Default)] +pub struct ShallowVars { + pub depth: usize, +} + +impl Mapper for ShallowVars { + type Out = (); + + fn map_epsilon( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + _eps: &mut Epsilon, + ) -> Self::Out { + } + + fn map_literal( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + _lit: &mut Literal, + ) -> Self::Out { + } + + fn map_cat( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + cat: &mut Cat, + ) -> Self::Out { + cat.first.map(self); + cat.second.map(self); + + for (_, term) in &mut cat.rest { + term.map(self); + } + } + + fn map_alt( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + alt: &mut Alt, + ) -> Self::Out { + alt.first.map(self); + alt.second.map(self); + + for (_, term) in &mut alt.rest { + term.map(self); + } + } + + fn map_fix( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + fix: &mut Fix, + ) -> Self::Out { + self.depth += 1; + fix.inner.map(self); + self.depth -= 1; + } + + fn map_variable( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + var: &mut Variable, + ) -> Self::Out { + if var.index >= self.depth { + var.index -= 1; + } + } + + fn map_parameter( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + _param: &mut Parameter, + ) -> Self::Out { + } + + fn map_call( + &mut self, + _name: &mut Option<Name>, + _span: Option<Span>, + call: &mut Call, + ) -> Self::Out { + for arg in &mut call.args { + arg.map(self) + } + } +} + +#[derive(Clone, Debug)] +pub struct SubstituteParams { + pub params: Vec<NamedExpression>, +} + +impl Folder for SubstituteParams { + type Out = Result<NamedExpression, SubstituteError>; + + fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out { + Ok(NamedExpression { + name, + expr: eps.into(), + span, + }) + } + + fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out { + Ok(NamedExpression { + name, + expr: lit.into(), + span, + }) + } + + fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out { + cat.first = Box::new(cat.first.fold(self)?); + cat.second = Box::new(cat.second.fold(self)?); + cat.rest = cat + .rest + .into_iter() + .map(|(p, term)| Ok((p, term.fold(self)?))) + .collect::<Result<_, _>>()?; + Ok(NamedExpression { + name, + expr: cat.into(), + span, + }) + } + + fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out { + alt.first = Box::new(alt.first.fold(self)?); + alt.second = Box::new(alt.second.fold(self)?); + alt.rest = alt + .rest + .into_iter() + .map(|(p, term)| Ok((p, term.fold(self)?))) + .collect::<Result<_, _>>()?; + Ok(NamedExpression { + name, + expr: alt.into(), + span, + }) + } + + fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, 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(NamedExpression { + name, + expr: fix.into(), + span, + }) + } + + fn fold_variable( + &mut self, + name: Option<Name>, + span: Option<Span>, + var: Variable, + ) -> Self::Out { + Ok(NamedExpression { + name, + expr: var.into(), + span, + }) + } + + fn fold_parameter( + &mut self, + name: Option<Name>, + span: Option<Span>, + param: Parameter, + ) -> Self::Out { + let mut expr = self + .params + .get(param.index) + .cloned() + .ok_or_else(|| SubstituteError::FreeParameter { param, span, name: name.clone() })?; + expr.name = expr.name.or(name); + expr.span = expr.span.or(span); + Ok(expr) + } + + fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out { + call.args = call + .args + .into_iter() + .map(|arg| arg.fold(self)) + .collect::<Result<_, _>>()?; + Ok(NamedExpression { + name, + expr: call.into(), + span, + }) + } +} + +#[derive(Clone, Debug)] +pub struct InlineCalls { + pub function: Function, +} + +impl Folder for InlineCalls { + type Out = Result<NamedExpression, SubstituteError>; + + fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out { + Ok(NamedExpression { + name, + expr: eps.into(), + span, + }) + } + + fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out { + Ok(NamedExpression { + name, + expr: lit.into(), + span, + }) + } + + fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out { + cat.first = Box::new(cat.first.fold(self)?); + cat.second = Box::new(cat.second.fold(self)?); + cat.rest = cat + .rest + .into_iter() + .map(|(punct, term)| Ok((punct, term.fold(self)?))) + .collect::<Result<_, _>>()?; + + Ok(NamedExpression { + name, + expr: cat.into(), + span, + }) + } + + fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out { + alt.first = Box::new(alt.first.fold(self)?); + alt.second = Box::new(alt.second.fold(self)?); + alt.rest = alt + .rest + .into_iter() + .map(|(punct, term)| Ok((punct, term.fold(self)?))) + .collect::<Result<_, _>>()?; + + Ok(NamedExpression { + name, + expr: alt.into(), + span, + }) + } + + fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out { + fix.inner = Box::new(fix.inner.fold(self)?); + + Ok(NamedExpression { + name, + expr: fix.into(), + span, + }) + } + + fn fold_variable( + &mut self, + name: Option<Name>, + span: Option<Span>, + var: Variable, + ) -> Self::Out { + Ok(NamedExpression { + name, + expr: var.into(), + span, + }) + } + + fn fold_parameter( + &mut self, + name: Option<Name>, + span: Option<Span>, + param: Parameter, + ) -> Self::Out { + Ok(NamedExpression { + name, + expr: param.into(), + span, + }) + } + + fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, 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(NamedExpression { + name, + expr: call.into(), + span, + }) + } else if call.args.len() != self.function.params.len() { + Err(SubstituteError::WrongArgCount { + call, + expected: self.function.params.len(), + span, + }) + } else { + let mut expr = self + .function + .expr + .clone() + .fold(&mut SubstituteParams { params: call.args })?; + expr.name = Some(expr.name.or(name).unwrap_or(call.name)); + expr.span = expr.span.or(span); + + Ok(expr) + } + } +} diff --git a/src/chomp/check/check.rs b/src/chomp/check/check.rs deleted file mode 100644 index 8729565..0000000 --- a/src/chomp/check/check.rs +++ /dev/null @@ -1,81 +0,0 @@ -use super::{ - super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - context::Context, - error::TypeError, - typed::{self, TypedExpression}, - visit::{Folder, Visitable, Visitor}, - }, - TypeInfer, -}; - -#[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!() - } -} diff --git a/src/chomp/check/closed.rs b/src/chomp/check/closed.rs deleted file mode 100644 index 07ef7ac..0000000 --- a/src/chomp/check/closed.rs +++ /dev/null @@ -1,50 +0,0 @@ -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - visit::{Visitable, Visitor}, -}; - -/// Test if term is closed for a context with `depth` variables. -#[derive(Copy, Clone, Debug, Default)] -pub struct Closed { - depth: usize, - params: 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 { - param.index() < self.params - } - - fn visit_call(&mut self, call: &Call) -> Self::Out { - call.args().iter().all(|arg| arg.visit(self)) - } -} diff --git a/src/chomp/check/deepen.rs b/src/chomp/check/deepen.rs deleted file mode 100644 index b9f606d..0000000 --- a/src/chomp/check/deepen.rs +++ /dev/null @@ -1,47 +0,0 @@ -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - visit::{Mapper, Visitable}, -}; - -#[derive(Clone, Copy, Debug, Default)] -pub 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); - } - } -} diff --git a/src/chomp/check/infer.rs b/src/chomp/check/infer.rs deleted file mode 100644 index 941ddba..0000000 --- a/src/chomp/check/infer.rs +++ /dev/null @@ -1,92 +0,0 @@ -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - context::Context, - error::{AltError, CatError, FixError, TypeError}, - set::{FirstSet, FlastSet}, - typed::Type, - visit::{Visitable, Visitor}, -}; - -#[derive(Debug)] -pub struct TypeInfer<'a> { - pub 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!() - } -} diff --git a/src/chomp/check/inline.rs b/src/chomp/check/inline.rs deleted file mode 100644 index da501f1..0000000 --- a/src/chomp/check/inline.rs +++ /dev/null @@ -1,349 +0,0 @@ -use super::{ - super::{ - ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Function, Literal, Parameter, Variable}, - error::SubstituteError, - visit::{Folder, Visitable}, - }, - SubstituteParams, -}; - -#[derive(Clone, Debug)] -pub struct InlineCalls { - function: Function, -} - -impl InlineCalls { - pub fn new(function: Function) -> Self { - Self { function } - } -} - -impl Folder for InlineCalls { - 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 SubstituteParams::new(call.args)) - } - } -} - -#[cfg(test)] -mod tests { - use crate::chomp::Name; - - use super::*; - - fn opt() -> Function { - Function::new( - Name::Spanless("opt".to_string()), - 1, - Expression::Alt(Alt::new( - Expression::Epsilon(None), - None, - Parameter::new(Name::Spanless("x".to_string()), 0).into(), - )), - None, - ) - } - - #[test] - fn test_inline_absent() { - let expr = Epsilon::default(); - let inlined = expr.fold(&mut InlineCalls::new(opt())); - assert_eq!(inlined, Ok(Epsilon::default().into())) - } - - #[test] - fn test_inline_in_fix() { - let expr = Fix::new( - Name::Spanless("rec".to_string()), - Call::new( - Name::Spanless("opt".to_string()), - vec![Variable::new(Name::Spanless("rec".to_string()), 0).into()], - None, - ) - .into(), - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(opt())); - assert_eq!( - inlined, - Ok(Fix::new( - Name::Spanless("rec".to_string()), - Alt::new( - Epsilon::default().into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into() - ) - .into(), - None - ) - .into()) - ) - } - - #[test] - fn test_inline_deepens_vars() { - let function = Function::new( - Name::Spanless("plus".into()), - 1, - Fix::new( - Name::Spanless("rec".to_string()), - Cat::new( - Parameter::new(Name::Spanless("x".to_string()), 0).into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into(), - ) - .into(), - None, - ) - .into(), - None, - ); - let expr = Fix::new( - Name::Spanless("var".to_string()), - Call::new( - Name::Spanless("plus".into()), - vec![Variable::new(Name::Spanless("var".to_string()), 0).into()], - None, - ) - .into(), - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(function)); - assert_eq!( - inlined, - Ok(Fix::new( - Name::Spanless("var".to_string()), - Fix::new( - Name::Spanless("rec".to_string()), - Cat::new( - Variable::new(Name::Spanless("var".to_string()), 1).into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into(), - ) - .into(), - None, - ) - .into(), - None - ) - .into()) - ) - } - - #[test] - fn test_inline_resets_vars() { - let function = Function::new( - Name::Spanless("plus".into()), - 1, - Cat::new( - Fix::new( - Name::Spanless("rec".to_string()), - Epsilon::default().into(), - None, - ) - .into(), - None, - Parameter::new(Name::Spanless("x".to_string()), 0).into(), - ) - .into(), - None, - ); - let expr = Fix::new( - Name::Spanless("var".to_string()), - Call::new( - Name::Spanless("plus".into()), - vec![Variable::new(Name::Spanless("var".to_string()), 0).into()], - None, - ) - .into(), - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(function)); - assert_eq!( - inlined, - Ok(Fix::new( - Name::Spanless("var".to_string()), - Cat::new( - Fix::new( - Name::Spanless("rec".to_string()), - Epsilon::default().into(), - None, - ) - .into(), - None, - Variable::new(Name::Spanless("var".to_string()), 0).into(), - ) - .into(), - None - ) - .into()) - ) - } - - #[test] - fn test_inline_double_subst() { - let expr = Call::new( - Name::Spanless("opt".to_string()), - vec![Call::new( - Name::Spanless("opt".to_string()), - vec![Literal::Spanless("x".to_string()).into()], - None, - ) - .into()], - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(opt())); - assert_eq!( - inlined, - Ok(Alt::new( - Epsilon::default().into(), - None, - Alt::new( - Epsilon::default().into(), - None, - Literal::Spanless("x".to_string()).into() - ) - .into() - ) - .into()) - ) - } - - #[test] - fn test_inline_call_args() { - let expr = Fix::new( - Name::Spanless("rec".to_string()), - Cat::new( - Literal::Spanless("a".to_string()).into(), - None, - Call::new( - Name::Spanless("opt".to_string()), - vec![Cat::new( - Cat::new( - Literal::Spanless("a".to_string()).into(), - None, - Fix::new( - Name::Spanless("star".to_string()), - Call::new( - Name::Spanless("opt".to_string()), - vec![Cat::new( - Literal::Spanless(" ".to_string()).into(), - None, - Variable::new(Name::Spanless("star".to_string()), 0).into(), - ) - .into()], - None, - ) - .into(), - None, - ) - .into(), - ) - .into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into(), - ) - .into()], - None, - ) - .into(), - ) - .into(), - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(opt())); - assert_eq!(inlined, - Ok(Fix::new( - Name::Spanless("rec".to_string()), - Cat::new( - Literal::Spanless("a".to_string()).into(), - None, - Alt::new( - Epsilon::default().into(), - None, - Cat::new( - Cat::new( - Literal::Spanless("a".to_string()).into(), - None, - Fix::new( - Name::Spanless("star".to_string()), - Alt::new( - Epsilon::default().into(), - None, - Cat::new( - Literal::Spanless(" ".to_string()).into(), - None, - Variable::new(Name::Spanless("star".to_string()), 0).into(), - ) - .into() - ) - .into(), - None, - ) - .into(), - ) - .into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into(), - ) - .into(), - ) - .into(), - ) - .into(), - None, - ).into())) - } -} diff --git a/src/chomp/check/mod.rs b/src/chomp/check/mod.rs deleted file mode 100644 index c9aeda4..0000000 --- a/src/chomp/check/mod.rs +++ /dev/null @@ -1,17 +0,0 @@ -mod check; -mod closed; -mod deepen; -mod infer; -mod inline; -mod shallow; -mod spanning; -mod substitute; - -pub use check::TypeCheck; -pub use closed::Closed; -pub use deepen::DeepenVars; -pub use infer::TypeInfer; -pub use inline::InlineCalls; -pub use shallow::ShallowVars; -pub use spanning::Spanning; -pub use substitute::SubstituteParams; diff --git a/src/chomp/check/shallow.rs b/src/chomp/check/shallow.rs deleted file mode 100644 index e5cc1a1..0000000 --- a/src/chomp/check/shallow.rs +++ /dev/null @@ -1,47 +0,0 @@ -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - visit::{Mapper, Visitable}, -}; - -#[derive(Clone, Copy, Debug, Default)] -pub 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); - } - } -} diff --git a/src/chomp/check/spanning.rs b/src/chomp/check/spanning.rs deleted file mode 100644 index 59c3811..0000000 --- a/src/chomp/check/spanning.rs +++ /dev/null @@ -1,59 +0,0 @@ -use proc_macro2::Span; - -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - visit::{Visitable, Visitor}, -}; - -#[derive(Clone, Copy, Debug)] -pub struct Spanning; - -impl Visitor for Spanning { - type Out = Option<Span>; - - fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out { - eps.map(|e| e.span) - } - - fn visit_literal(&mut self, lit: &Literal) -> Self::Out { - 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 { - var.name().span() - } - - fn visit_parameter(&mut self, param: &Parameter) -> Self::Out { - param.name().span() - } - - fn visit_call(&mut self, call: &Call) -> Self::Out { - call.span() - } -} diff --git a/src/chomp/check/substitute.rs b/src/chomp/check/substitute.rs deleted file mode 100644 index 32595b1..0000000 --- a/src/chomp/check/substitute.rs +++ /dev/null @@ -1,77 +0,0 @@ -use super::{ - super::{ - ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Literal, Parameter, Variable}, - error::SubstituteError, - visit::{Folder, Visitable}, - }, - DeepenVars, ShallowVars, -}; - -#[derive(Clone, Debug)] -pub struct SubstituteParams { - params: Vec<Expression>, -} - -impl SubstituteParams { - pub fn new(params: Vec<Expression>) -> Self { - Self { params } - } -} - -impl Folder for SubstituteParams { - 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)) - } -} diff --git a/src/chomp/error.rs b/src/chomp/error.rs deleted file mode 100644 index e7e4660..0000000 --- a/src/chomp/error.rs +++ /dev/null @@ -1,402 +0,0 @@ -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, Eq, PartialEq)] -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().unwrap_or_else(Span::call_site).start(); - write!( - f, - "{}:{}: unbound variable '{}'", - start.line, - start.column, - var.name() - ) - } - Self::GuardedVariable(var) => { - let start = var.name().span().unwrap_or_else(Span::call_site).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, Eq, PartialEq)] -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, Eq, PartialEq)] -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, Eq, PartialEq)] -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, Eq, PartialEq)] -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, Eq, PartialEq)] -pub enum SubstituteError { - FreeParameter(Parameter), - WrongArgCount { call: Call, expected: usize }, -} - -impl From<SubstituteError> for syn::Error { - fn from(e: SubstituteError) -> Self { - match e { - SubstituteError::FreeParameter(param) => { - Self::new(param.name().span().unwrap_or_else(Span::call_site), format!("undeclared variable `{}'", param.name())) - } - SubstituteError::WrongArgCount { call, expected } => { - Self::new(call.span().unwrap_or_else(Span::call_site), format!("wrong number of arguments. Expected {}, got {}", expected, call.args().len())) - } - } - } -} - -impl Display for SubstituteError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::FreeParameter(param) => { - let start = param.name().span().unwrap_or_else(Span::call_site).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, - expected, - call.args().len() - ) - } - } - } -} - -impl Error for SubstituteError {} diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs index 1e30738..79b4fac 100644 --- a/src/chomp/mod.rs +++ b/src/chomp/mod.rs @@ -1,12 +1,10 @@ use std::{fmt, hash}; +use heck::{CamelCase, SnakeCase}; use proc_macro2::{Ident, Span}; use syn::ext::IdentExt; pub mod ast; -pub mod check; -pub mod context; -pub mod error; pub mod set; pub mod typed; pub mod visit; @@ -25,7 +23,7 @@ impl Name { } } - pub fn as_ident(self, span: Span) -> Ident { + pub fn into_ident(self, span: Span) -> Ident { match self { Self::Spanned(i) => i, Self::Spanless(s) => Ident::new(&s, span), @@ -33,6 +31,36 @@ impl Name { } } +impl CamelCase for Name { + fn to_camel_case(&self) -> Self::Owned { + match self { + Self::Spanned(ident) => { + let span = ident.span(); + let name = ident.unraw().to_string(); + Ident::new(&name.to_camel_case(), span).into() + } + Name::Spanless(name) => { + name.to_camel_case().into() + } + } + } +} + +impl SnakeCase for Name { + fn to_snake_case(&self) -> Self::Owned { + match self { + Self::Spanned(ident) => { + let span = ident.span(); + let name = ident.unraw().to_string(); + Ident::new(&name.to_snake_case(), span).into() + } + Name::Spanless(name) => { + name.to_snake_case().into() + } + } + } +} + impl PartialEq for Name { fn eq(&self, other: &Self) -> bool { match (self, other) { diff --git a/src/chomp/typed.rs b/src/chomp/typed.rs deleted file mode 100644 index db07552..0000000 --- a/src/chomp/typed.rs +++ /dev/null @@ -1,323 +0,0 @@ -use std::hash::{Hash, Hasher}; - -use proc_macro2::Span; -use syn::Token; - -use super::{ - ast, - set::{FirstSet, FlastSet}, - Name, -}; - -#[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: Option<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: ast::Literal, - ty: Type, -} - -impl Literal { - pub fn inner(&self) -> &ast::Literal { - &self.inner - } - - pub fn span(&self) -> Option<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 } - } -} - -impl From<Literal> for ast::Literal { - fn from(lit: Literal) -> Self { - lit.inner - } -} - -#[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: Name, - inner: Box<TypedExpression>, - span: Option<Span>, - ty: Type, -} - -impl Fix { - pub(crate) fn new(arg: Name, inner: TypedExpression, span: Option<Span>, ty: Type) -> Self { - Self { - arg, - inner: Box::new(inner), - span, - ty, - } - } - - pub fn unwrap(self) -> (Name, 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 { - inner: ast::Variable, - ty: Type, -} - -impl Variable { - pub(crate) fn new(inner: ast::Variable, ty: Type) -> Self { - Self { inner, ty } - } - - pub fn index(&self) -> usize { - self.inner.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/context.rs b/src/chomp/typed/context.rs index 392023f..5c8d398 100644 --- a/src/chomp/context.rs +++ b/src/chomp/typed/context.rs @@ -1,4 +1,6 @@ -use super::{ast::Variable, error::VariableError, typed::Type}; +use crate::chomp::ast::Variable; + +use super::Type; #[derive(Debug, Default)] pub struct Context { @@ -16,14 +18,12 @@ impl Context { } pub fn is_unguarded(&self, var: &Variable) -> Option<bool> { - if self.vars.len() <= var.index() { + 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(), - ) + Some(self.unguard_points[self.unguard_points.len() - 1] + var.index >= self.vars.len()) } } @@ -34,11 +34,11 @@ impl Context { res } - pub fn get_variable_type(&self, var: &Variable) -> Result<&Type, VariableError> { + pub fn get_variable_type(&self, var: &Variable) -> Result<&Type, GetVariableError> { 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]), + None => Err(GetVariableError::FreeVariable), + Some(false) => Err(GetVariableError::GuardedVariable), + Some(true) => Ok(&self.vars[self.vars.len() - var.index - 1]), } } @@ -49,3 +49,9 @@ impl Context { res } } + +#[derive(Clone, Debug, Eq, PartialEq)] +pub enum GetVariableError { + FreeVariable, + GuardedVariable, +} diff --git a/src/chomp/typed/error.rs b/src/chomp/typed/error.rs new file mode 100644 index 0000000..bb807fc --- /dev/null +++ b/src/chomp/typed/error.rs @@ -0,0 +1,150 @@ +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 PartialEq for VariableError { + fn eq(&self, other: &Self) -> bool { + todo!() + } +} + +impl Eq for VariableError {} + +impl From<VariableError> for syn::Error { + fn from(other: VariableError) -> Self { + todo!() + } +} + +impl Display for VariableError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + todo!() + } +} + +impl Error for VariableError {} + +/// A type error when concatenating two terms. +#[derive(Debug)] +pub enum CatError { + /// The first term was unexpectedly nullable. + FirstNullable(TypedExpression, Option<Span>), + /// The flast set of the first term intersects the first set of the second. + FirstFlastOverlap(Vec<TypedExpression>, Option<Span>, TypedExpression), +} + +impl PartialEq for CatError { + fn eq(&self, other: &Self) -> bool { + todo!() + } +} + +impl Eq for CatError {} + +impl From<CatError> for syn::Error { + fn from(other: CatError) -> Self { + todo!() + } +} + +impl Display for CatError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + todo!() + } +} + +impl Error for CatError {} + +/// A type error when alternating two terms. +#[derive(Debug)] +pub enum AltError { + /// Both terms are nullable. + BothNullable(Vec<TypedExpression>, Option<Span>, TypedExpression), + /// The first sets of the two terms intersect. + FirstOverlap(Vec<TypedExpression>, Option<Span>, TypedExpression), +} + +impl PartialEq for AltError { + fn eq(&self, other: &Self) -> bool { + todo!() + } +} + +impl Eq for AltError {} + +impl From<AltError> for syn::Error { + fn from(other: AltError) -> Self { + todo!() + } +} + +impl Display for AltError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + todo!() + } +} + +impl Error for AltError {} + +#[derive(Debug, Eq, PartialEq)] +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/infer.rs b/src/chomp/typed/infer.rs new file mode 100644 index 0000000..0161471 --- /dev/null +++ b/src/chomp/typed/infer.rs @@ -0,0 +1,145 @@ +use proc_macro2::Span; + +use crate::chomp::{ + ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, + visit::{Folder, Visitable}, + Name, +}; + +use super::{ + context::Context, + error::{TypeError, VariableError}, + Type, Typed, TypedExpression, +}; + +#[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 second = cat.second; + let rest = cat.rest; + let punct = cat.punct; + self.context + .with_unguard(|context| -> Result<TypedExpression, TypeError> { + let mut infer = TypeInfer { context }; + let second = second.fold(&mut infer)?; + let rest = rest + .into_iter() + .map(|(punct, term)| -> Result<_, TypeError> { + Ok((punct.map(|p| p.span), term.fold(&mut infer)?)) + }) + .collect::<Result<Vec<_>, _>>()?; + Ok(TypedExpression { + inner: super::Cat::new(first, punct.map(|p| p.span), second, 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 second = alt.second; + let rest = alt.rest; + let punct = alt.punct; + self.context + .with_unguard(|context| -> Result<TypedExpression, TypeError> { + let mut infer = TypeInfer { context }; + let second = second.fold(&mut infer)?; + let rest = rest + .into_iter() + .map(|(punct, term)| -> Result<_, TypeError> { + Ok((punct.map(|p| p.span), term.fold(&mut infer)?)) + }) + .collect::<Result<Vec<_>, _>>()?; + Ok(TypedExpression { + inner: super::Alt::new(first, punct.map(|p| p.span), second, 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_parameter( + &mut self, + _name: Option<Name>, + _span: Option<Span>, + _param: Parameter, + ) -> Self::Out { + todo!() + } + + fn fold_call(&mut self, _name: Option<Name>,_span: Option<Span>, _call: Call) -> Self::Out { + todo!() + } +} diff --git a/src/chomp/typed/lower.rs b/src/chomp/typed/lower.rs new file mode 100644 index 0000000..37589a1 --- /dev/null +++ b/src/chomp/typed/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/mod.rs b/src/chomp/typed/mod.rs new file mode 100644 index 0000000..e9aed79 --- /dev/null +++ b/src/chomp/typed/mod.rs @@ -0,0 +1,343 @@ +use std::{hash, iter}; + +use proc_macro2::Span; + +use super::{ + ast, + set::{FirstSet, FlastSet}, + Name, +}; + +pub mod context; +pub mod error; +pub mod lower; + +mod infer; + +pub use self::infer::TypeInfer; +use self::error::{AltError, CatError}; + +#[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, + punct: Option<Span>, + second: TypedExpression, + rest: I, + ) -> Result<Self, CatError> { + if first.get_type().nullable() { + return Err(CatError::FirstNullable(first, punct)); + } + + iter::once((punct, second)) + .chain(rest) + .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() + { + Err(CatError::FirstFlastOverlap(terms, punct, right)) + } else { + let ty = ty.cat(right.get_type().clone()); + terms.push(right); + Ok((ty, terms)) + } + }, + ) + .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, + punct: Option<Span>, + second: TypedExpression, + rest: I, + ) -> Result<Self, AltError> { + iter::once((punct, second)) + .chain(rest) + .try_fold( + (first.get_type().clone(), vec![first]), + |(ty, mut terms), (punct, right)| { + if ty.nullable() && right.get_type().nullable() { + Err(AltError::BothNullable(terms, punct, right)) + } else if !ty + .first_set() + .intersect(right.get_type().first_set()) + .is_empty() + { + Err(AltError::FirstOverlap(terms, punct, right)) + } else { + let ty = ty.alt(right.get_type().clone()); + terms.push(right); + Ok((ty, terms)) + } + }, + ) + .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)] +enum RawTypedExpression { + Epsilon(Epsilon), + Literal(Literal), + Cat(Cat), + Alt(Alt), + Fix(Fix), + Variable(Variable), +} + +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(), + } + } +} diff --git a/src/chomp/visit.rs b/src/chomp/visit.rs index 4113b64..bdef30e 100644 --- a/src/chomp/visit.rs +++ b/src/chomp/visit.rs @@ -1,62 +1,120 @@ -use super::ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Literal, Parameter, Variable}; +use proc_macro2::Span; + +use super::{ + ast::{ + Alt, Call, Cat, Epsilon, Expression, Fix, Literal, NamedExpression, Parameter, Variable, + }, + Name, +}; 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; + fn visit_epsilon( + &mut self, + name: Option<&Name>, + span: Option<Span>, + eps: &Epsilon, + ) -> Self::Out; + + fn visit_literal( + &mut self, + name: Option<&Name>, + span: Option<Span>, + lit: &Literal, + ) -> Self::Out; + + fn visit_cat(&mut self, name: Option<&Name>, span: Option<Span>, cat: &Cat) -> Self::Out; + + fn visit_alt(&mut self, name: Option<&Name>, span: Option<Span>, alt: &Alt) -> Self::Out; + + fn visit_fix(&mut self, name: Option<&Name>, span: Option<Span>, fix: &Fix) -> Self::Out; + + fn visit_variable( + &mut self, + name: Option<&Name>, + span: Option<Span>, + var: &Variable, + ) -> Self::Out; + + fn visit_parameter( + &mut self, + name: Option<&Name>, + span: Option<Span>, + param: &Parameter, + ) -> Self::Out; + + fn visit_call(&mut self, name: Option<&Name>, span: Option<Span>, 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; + fn map_epsilon( + &mut self, + name: &mut Option<Name>, + span: Option<Span>, + eps: &mut Epsilon, + ) -> Self::Out; + + fn map_literal( + &mut self, + name: &mut Option<Name>, + span: Option<Span>, + lit: &mut Literal, + ) -> Self::Out; + + fn map_cat(&mut self, name: &mut Option<Name>, span: Option<Span>, cat: &mut Cat) -> Self::Out; + + fn map_alt(&mut self, name: &mut Option<Name>, span: Option<Span>, alt: &mut Alt) -> Self::Out; + + fn map_fix(&mut self, name: &mut Option<Name>, span: Option<Span>, fix: &mut Fix) -> Self::Out; + + fn map_variable( + &mut self, + name: &mut Option<Name>, + span: Option<Span>, + var: &mut Variable, + ) -> Self::Out; + + fn map_parameter( + &mut self, + name: &mut Option<Name>, + span: Option<Span>, + param: &mut Parameter, + ) -> Self::Out; + + fn map_call( + &mut self, + name: &mut Option<Name>, + span: Option<Span>, + call: &mut Call, + ) -> Self::Out; } pub trait Folder { type Out; - fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out; + fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out; - fn fold_literal(&mut self, lit: Literal) -> Self::Out; + fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out; - fn fold_cat(&mut self, cat: Cat) -> Self::Out; + fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out; - fn fold_alt(&mut self, alt: Alt) -> Self::Out; + fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out; - fn fold_fix(&mut self, fix: Fix) -> Self::Out; + fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out; - fn fold_variable(&mut self, var: Variable) -> Self::Out; + fn fold_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable) + -> Self::Out; - fn fold_parameter(&mut self, param: Parameter) -> Self::Out; + fn fold_parameter( + &mut self, + name: Option<Name>, + span: Option<Span>, + param: Parameter, + ) -> Self::Out; - fn fold_call(&mut self, call: Call) -> Self::Out; + fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out; } pub trait Visitable { @@ -67,70 +125,43 @@ pub trait Visitable { 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 { +impl Visitable for NamedExpression { 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), + match &self.expr { + Expression::Epsilon(e) => visitor.visit_epsilon(self.name.as_ref(), self.span, e), + Expression::Literal(l) => visitor.visit_literal(self.name.as_ref(), self.span, l), + Expression::Cat(c) => visitor.visit_cat(self.name.as_ref(), self.span, c), + Expression::Alt(a) => visitor.visit_alt(self.name.as_ref(), self.span, a), + Expression::Fix(f) => visitor.visit_fix(self.name.as_ref(), self.span, f), + Expression::Variable(v) => visitor.visit_variable(self.name.as_ref(), self.span, v), + Expression::Parameter(p) => visitor.visit_parameter(self.name.as_ref(), self.span, p), + Expression::Call(c) => visitor.visit_call(self.name.as_ref(), self.span, 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), + match &mut self.expr { + Expression::Epsilon(e) => mapper.map_epsilon(&mut self.name, self.span, e), + Expression::Literal(l) => mapper.map_literal(&mut self.name, self.span, l), + Expression::Cat(c) => mapper.map_cat(&mut self.name, self.span, c), + Expression::Alt(a) => mapper.map_alt(&mut self.name, self.span, a), + Expression::Fix(f) => mapper.map_fix(&mut self.name, self.span, f), + Expression::Variable(v) => mapper.map_variable(&mut self.name, self.span, v), + Expression::Parameter(p) => mapper.map_parameter(&mut self.name, self.span, p), + Expression::Call(c) => mapper.map_call(&mut self.name, self.span, 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), + match self.expr { + Expression::Epsilon(e) => folder.fold_epsilon(self.name, self.span, e), + Expression::Literal(l) => folder.fold_literal(self.name, self.span, l), + Expression::Cat(c) => folder.fold_cat(self.name, self.span, c), + Expression::Alt(a) => folder.fold_alt(self.name, self.span, a), + Expression::Fix(f) => folder.fold_fix(self.name, self.span, f), + Expression::Variable(v) => folder.fold_variable(self.name, self.span, v), + Expression::Parameter(p) => folder.fold_parameter(self.name, self.span, p), + Expression::Call(c) => folder.fold_call(self.name, self.span, c), } } } |