summaryrefslogtreecommitdiff
path: root/src/chomp/ast
diff options
context:
space:
mode:
Diffstat (limited to 'src/chomp/ast')
-rw-r--r--src/chomp/ast/error.rs27
-rw-r--r--src/chomp/ast/mod.rs326
-rw-r--r--src/chomp/ast/substitute.rs439
3 files changed, 792 insertions, 0 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/mod.rs b/src/chomp/ast/mod.rs
new file mode 100644
index 0000000..110e5c0
--- /dev/null
+++ b/src/chomp/ast/mod.rs
@@ -0,0 +1,326 @@
+use std::fmt::{self, Display};
+
+use proc_macro2::Span;
+use syn::Token;
+
+use super::Name;
+
+pub mod error;
+pub mod substitute;
+
+#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)]
+pub struct Epsilon;
+
+pub type Literal = String;
+
+#[derive(Clone, Debug)]
+pub struct Cat {
+ pub first: Box<NamedExpression>,
+ pub punct: Option<Token![.]>,
+ 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.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.rest.len() == other.rest.len()
+ && self
+ .rest
+ .iter()
+ .zip(other.rest.iter())
+ .all(|((_, me), (_, them))| me == them)
+ }
+}
+
+impl Eq for Cat {}
+
+#[derive(Clone, Debug)]
+pub struct Alt {
+ pub first: Box<NamedExpression>,
+ pub punct: Option<Token![|]>,
+ 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.first, self.second)?;
+ for (_, other) in &self.rest {
+ write!(f, " | {}", other)?;
+ }
+ write!(f, ")")
+ }
+}
+
+impl PartialEq for Alt {
+ fn eq(&self, other: &Self) -> bool {
+ 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)
+ }
+}
+
+impl Eq for Alt {}
+
+#[derive(Clone, Debug)]
+pub struct Fix {
+ pub arg: Option<Name>,
+ pub inner: Box<NamedExpression>,
+}
+
+impl Display for Fix {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ 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
+ }
+}
+
+impl Eq for Fix {}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Variable {
+ pub index: usize,
+}
+
+impl Display for Variable {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "'{}", self.index)
+ }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Parameter {
+ pub index: usize,
+}
+
+impl Display for Parameter {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "<{}>", self.index)
+ }
+}
+
+/// A macro invocation.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Call {
+ pub name: Name,
+ pub args: Vec<NamedExpression>,
+}
+
+impl Display for Call {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "{}", self.name)?;
+
+ let mut iter = self.args.iter();
+
+ if let Some(arg) = iter.next() {
+ write!(f, "({}", arg)?;
+
+ for arg in iter {
+ write!(f, ", {}", arg)?;
+ }
+
+ write!(f, ")")
+ } else {
+ Ok(())
+ }
+ }
+}
+
+#[derive(Clone, Debug)]
+pub enum Expression {
+ /// Matches the empty string.
+ Epsilon(Epsilon),
+ /// Matches the literal string.
+ Literal(Literal),
+ /// Matches one term followed by another.
+ Cat(Cat),
+ /// Matches either one term or another.
+ Alt(Alt),
+ /// The least fix point of a term.
+ Fix(Fix),
+ /// A fixed point variable.
+ Variable(Variable),
+ /// A formal parameter.
+ Parameter(Parameter),
+ /// A macro invocation.
+ Call(Call),
+}
+
+impl Display for Expression {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Self::Epsilon(_) => write!(f, "_"),
+ Self::Literal(l) => l.fmt(f),
+ Self::Cat(c) => c.fmt(f),
+ Self::Alt(a) => a.fmt(f),
+ Self::Fix(x) => x.fmt(f),
+ Self::Variable(v) => v.fmt(f),
+ Self::Parameter(p) => p.fmt(f),
+ Self::Call(c) => c.fmt(f),
+ }
+ }
+}
+
+impl 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)
+ }
+}
+
+impl From<Literal> for Expression {
+ fn from(lit: Literal) -> Self {
+ Self::Literal(lit)
+ }
+}
+
+impl From<Cat> for Expression {
+ fn from(cat: Cat) -> Self {
+ Self::Cat(cat)
+ }
+}
+
+impl From<Alt> for Expression {
+ fn from(alt: Alt) -> Self {
+ Self::Alt(alt)
+ }
+}
+
+impl From<Fix> for Expression {
+ fn from(fix: Fix) -> Self {
+ Self::Fix(fix)
+ }
+}
+
+impl From<Variable> for Expression {
+ fn from(var: Variable) -> Self {
+ Self::Variable(var)
+ }
+}
+
+impl From<Parameter> for Expression {
+ fn from(param: Parameter) -> Self {
+ Self::Parameter(param)
+ }
+}
+
+impl From<Call> for Expression {
+ fn from(call: Call) -> Self {
+ Self::Call(call)
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct NamedExpression {
+ pub name: Option<Name>,
+ pub expr: Expression,
+ pub span: Option<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)
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.49.0) at 2025-04-30 06:51:23 +0000