diff options
Diffstat (limited to 'src/chomp/ast')
| -rw-r--r-- | src/chomp/ast/mod.rs | 145 | ||||
| -rw-r--r-- | src/chomp/ast/substitute.rs | 342 |
2 files changed, 310 insertions, 177 deletions
diff --git a/src/chomp/ast/mod.rs b/src/chomp/ast/mod.rs index e4ed2fc..4a202e0 100644 --- a/src/chomp/ast/mod.rs +++ b/src/chomp/ast/mod.rs @@ -102,55 +102,74 @@ impl PartialEq for Fix { impl Eq for Fix {} #[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)] -pub struct Variable { +pub struct Parameter { pub index: usize, } -impl Display for Variable { +impl Display for Parameter { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "'{}", self.index) + write!(f, "<{}>", self.index) } } -#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)] -pub struct Parameter { - pub index: usize, +#[derive(Clone, Debug, Eq, Hash, PartialEq)] +pub struct Global { + pub name: Name, } -impl Display for Parameter { +impl Display for Global { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "<{}>", self.index) + write!(f, "'{}", self.name) } } /// A macro invocation. #[derive(Clone, Debug, Eq, PartialEq)] pub struct Call { - pub name: Name, + pub fun: Box<NamedExpression>, pub args: Vec<NamedExpression>, } impl Display for Call { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "{}", self.name)?; + write!(f, "({})(", self.fun)?; let mut iter = self.args.iter(); if let Some(arg) = iter.next() { - write!(f, "({}", arg)?; + write!(f, "{}", arg)?; for arg in iter { write!(f, ", {}", arg)?; } + } + + write!(f, ")") + } +} - write!(f, ")") - } else { - Ok(()) +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Function { + pub args: Vec<Name>, + pub expr: Box<NamedExpression>, +} + +impl Display for Function { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "[")?; + let mut iter = self.args.iter(); + if let Some(arg) = iter.next() { + write!(f, "{}", arg)?; + for arg in iter { + write!(f, ", {}", arg)?; + } } + + write!(f, "]") } } -#[derive(Clone, Debug)] +#[derive(Clone, Debug, PartialEq, Eq)] pub enum Expression { /// Matches the empty string. Epsilon(Epsilon), @@ -162,12 +181,14 @@ pub enum Expression { 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. + /// A global variable. + Global(Global), + /// A function invocation. Call(Call), + /// A function definition. + Function(Function) } impl Display for Expression { @@ -178,72 +199,14 @@ impl Display for Expression { 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::Global(g) => g.fmt(f), Self::Parameter(p) => p.fmt(f), Self::Call(c) => c.fmt(f), + Self::Function(n) => n.fmt(f), } } } -impl PartialEq for Expression { - fn eq(&self, other: &Self) -> bool { - match self { - Self::Epsilon(_) => matches!(other, Self::Epsilon(_)), - Self::Literal(l) => { - if let Self::Literal(them) = other { - l == them - } else { - false - } - } - Self::Cat(c) => { - if let Self::Cat(them) = other { - c == them - } else { - false - } - } - Self::Alt(a) => { - if let Self::Alt(them) = other { - a == them - } else { - false - } - } - Self::Fix(f) => { - if let Self::Fix(them) = other { - f == them - } else { - false - } - } - Self::Variable(v) => { - if let Self::Variable(them) = other { - v == them - } else { - false - } - } - Self::Parameter(p) => { - if let Self::Parameter(them) = other { - p == them - } else { - false - } - } - Self::Call(c) => { - if let Self::Call(them) = other { - c == them - } else { - false - } - } - } - } -} - -impl Eq for Expression {} - impl From<Epsilon> for Expression { fn from(eps: Epsilon) -> Self { Self::Epsilon(eps) @@ -274,24 +237,30 @@ impl From<Fix> for Expression { } } -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<Global> for Expression { + fn from(global: Global) -> Self { + Self::Global(global) + } +} + impl From<Call> for Expression { fn from(call: Call) -> Self { Self::Call(call) } } +impl From<Function> for Expression { + fn from(fun: Function) -> Self { + Self::Function(fun) + } +} + #[derive(Clone, Debug)] pub struct NamedExpression { pub name: Option<Name>, @@ -315,11 +284,3 @@ impl PartialEq for NamedExpression { } 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 index 2008a15..5f5d576 100644 --- a/src/chomp/ast/substitute.rs +++ b/src/chomp/ast/substitute.rs @@ -6,8 +6,8 @@ use crate::chomp::{ }; use super::{ - error::SubstituteError, Alt, Call, Cat, Epsilon, Fix, Function, Literal, NamedExpression, - Parameter, Variable, + error::SubstituteError, Alt, Call, Cat, Epsilon, Expression, Fix, Function, Global, Literal, + NamedExpression, Parameter, }; #[derive(Clone, Copy, Debug, Default)] @@ -73,22 +73,20 @@ impl Mapper for DeepenVars { self.depth -= 1; } - fn map_variable( + fn map_parameter( &mut self, _name: &mut Option<Name>, _span: Option<Span>, - var: &mut Variable, + _param: &mut Parameter, ) -> Self::Out { - if var.index >= self.depth { - var.index += 1; - } + todo!() } - fn map_parameter( + fn map_global( &mut self, - _name: &mut Option<Name>, - _span: Option<Span>, - _param: &mut Parameter, + name: &mut Option<Name>, + span: Option<Span>, + global: &mut Global, ) -> Self::Out { } @@ -102,6 +100,15 @@ impl Mapper for DeepenVars { arg.map(self) } } + + fn map_function( + &mut self, + name: &mut Option<Name>, + span: Option<Span>, + fun: &mut Function, + ) -> Self::Out { + todo!() + } } #[derive(Clone, Copy, Debug, Default)] @@ -167,22 +174,20 @@ impl Mapper for ShallowVars { self.depth -= 1; } - fn map_variable( + fn map_parameter( &mut self, _name: &mut Option<Name>, _span: Option<Span>, - var: &mut Variable, + _param: &mut Parameter, ) -> Self::Out { - if var.index >= self.depth { - var.index -= 1; - } + todo!() } - fn map_parameter( + fn map_global( &mut self, - _name: &mut Option<Name>, - _span: Option<Span>, - _param: &mut Parameter, + name: &mut Option<Name>, + span: Option<Span>, + global: &mut Global, ) -> Self::Out { } @@ -196,6 +201,15 @@ impl Mapper for ShallowVars { arg.map(self) } } + + fn map_function( + &mut self, + name: &mut Option<Name>, + span: Option<Span>, + fun: &mut Function, + ) -> Self::Out { + todo!() + } } #[derive(Clone, Debug)] @@ -270,35 +284,32 @@ impl Folder for SubstituteParams { }) } - 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() })?; + 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_global(&mut self, name: Option<Name>, span: Option<Span>, global: Global) -> Self::Out { + Ok(NamedExpression { + name, + expr: global.into(), + span, + }) + } + fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out { call.args = call .args @@ -311,14 +322,161 @@ impl Folder for SubstituteParams { span, }) } + + fn fold_function( + &mut self, + name: Option<Name>, + span: Option<Span>, + fun: Function, + ) -> Self::Out { + todo!() + } } #[derive(Clone, Debug)] -pub struct InlineCalls { - pub function: Function, +pub struct InlineGlobal { + pub expr: Expression, + pub name: Name, + pub span: Option<Span>, } -impl Folder for InlineCalls { +impl Folder for InlineGlobal { + type Out = NamedExpression; + + fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out { + NamedExpression { + name, + expr: eps.into(), + span, + } + } + + fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out { + 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)| (punct, term.fold(self))) + .collect(); + + 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)| (punct, term.fold(self))) + .collect(); + + 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)); + + NamedExpression { + name, + expr: fix.into(), + span, + } + } + + fn fold_parameter( + &mut self, + name: Option<Name>, + span: Option<Span>, + param: Parameter, + ) -> Self::Out { + NamedExpression { + name, + expr: param.into(), + span, + } + } + + fn fold_global(&mut self, name: Option<Name>, span: Option<Span>, global: Global) -> Self::Out { + if global.name == self.name { + NamedExpression { + name: Some(name.unwrap_or(self.name.clone())), + expr: self.expr.clone(), + span: span.or(self.span), + } + } else { + NamedExpression { + name, + expr: global.into(), + span, + } + } + } + + fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out { + call.fun = Box::new(call.fun.fold(self)); + call.args = call.args.into_iter().map(|arg| arg.fold(self)).collect(); + + NamedExpression { + name, + expr: call.into(), + span, + } + } + + fn fold_function( + &mut self, + name: Option<Name>, + span: Option<Span>, + fun: Function, + ) -> Self::Out { + fun.expr = Box::new(fun.expr.fold(self)); + NamedExpression { + name, + expr: fun.into(), + span, + } + } +} + +pub struct ExpandCalls { + pub changed: bool, +} + +impl ExpandCalls { + fn fold_until_done( + &mut self, + mut term: NamedExpression, + ) -> Result<NamedExpression, SubstituteError> { + let last = self.changed; + self.changed = true; + while self.changed { + self.changed = false; + term = term.fold(self)? + } + self.changed = last; + Ok(term) + } +} + +impl Folder for ExpandCalls { type Out = Result<NamedExpression, SubstituteError>; fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out { @@ -337,13 +495,13 @@ impl Folder for InlineCalls { }) } - 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)?); + fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out { + cat.first = Box::new(self.fold_until_done(*cat.first)?); + cat.second = Box::new(self.fold_until_done(*cat.second)?); cat.rest = cat .rest .into_iter() - .map(|(punct, term)| Ok((punct, term.fold(self)?))) + .map(|(punct, term)| Ok((punct, self.fold_until_done(term)?))) .collect::<Result<_, _>>()?; Ok(NamedExpression { @@ -353,13 +511,13 @@ impl Folder for InlineCalls { }) } - 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)?); + fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out { + alt.first = Box::new(self.fold_until_done(*alt.first)?); + alt.second = Box::new(self.fold_until_done(*alt.second)?); alt.rest = alt .rest .into_iter() - .map(|(punct, term)| Ok((punct, term.fold(self)?))) + .map(|(punct, term)| Ok((punct, self.fold_until_done(term)?))) .collect::<Result<_, _>>()?; Ok(NamedExpression { @@ -369,9 +527,8 @@ impl Folder for InlineCalls { }) } - fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out { - fix.inner = Box::new(fix.inner.fold(self)?); - + fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out { + fix.inner = Box::new(self.fold_until_done(*fix.inner)?); Ok(NamedExpression { name, expr: fix.into(), @@ -379,61 +536,76 @@ impl Folder for InlineCalls { }) } - fn fold_variable( + fn fold_parameter( &mut self, name: Option<Name>, span: Option<Span>, - var: Variable, + param: Parameter, ) -> Self::Out { Ok(NamedExpression { name, - expr: var.into(), + expr: param.into(), span, }) } - fn fold_parameter( - &mut self, - name: Option<Name>, - span: Option<Span>, - param: Parameter, - ) -> Self::Out { + fn fold_global(&mut self, name: Option<Name>, span: Option<Span>, global: Global) -> Self::Out { Ok(NamedExpression { name, - expr: param.into(), + expr: global.into(), span, }) } - fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out { - call.args = call + fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out { + let fun = self.fold_until_done(*call.fun)?; + let args = call .args .into_iter() - .map(|arg| arg.fold(self)) - .collect::<Result<_, _>>()?; - - if call.name != self.function.name { + .map(|arg| self.fold_until_done(arg)) + .collect::<Result<Vec<_>, _>>()?; + + if let Expression::Function(f) = fun.expr { + if f.args.len() == args.len() { + let mut out = f.expr.fold(&mut SubstituteParams { params: args })?; + self.changed = true; + out.name = name.or(out.name); + out.span = span.or(out.span); + Ok(out) + } else { + Err(SubstituteError::WrongArgCount { + call: Call { + fun: Box::new(fun), + args, + }, + expected: f.args.len(), + span, + }) + } + } else { Ok(NamedExpression { name, - expr: call.into(), - span, - }) - } else if call.args.len() == self.function.params.len() { - let mut expr = self - .function - .expr - .clone() - .fold(&mut SubstituteParams { params: call.args })?; - expr.name = Some(name.or(expr.name).unwrap_or(call.name)); - expr.span = span.or(expr.span); - - Ok(expr) - } else { - Err(SubstituteError::WrongArgCount { - call, - expected: self.function.params.len(), + expr: Call { + fun: Box::new(fun), + args, + } + .into(), span, }) } } + + fn fold_function( + &mut self, + name: Option<Name>, + span: Option<Span>, + fun: Function, + ) -> Self::Out { + fun.expr = Box::new(self.fold_until_done(*fun.expr)?); + Ok(NamedExpression { + name, + expr: fun.into(), + span, + }) + } } |