summaryrefslogtreecommitdiff
path: root/src/chomp/ast
diff options
context:
space:
mode:
Diffstat (limited to 'src/chomp/ast')
-rw-r--r--src/chomp/ast/error.rs52
-rw-r--r--src/chomp/ast/mod.rs325
-rw-r--r--src/chomp/ast/substitute.rs412
3 files changed, 0 insertions, 789 deletions
diff --git a/src/chomp/ast/error.rs b/src/chomp/ast/error.rs
deleted file mode 100644
index 9057ec3..0000000
--- a/src/chomp/ast/error.rs
+++ /dev/null
@@ -1,52 +0,0 @@
-use super::{Expression, Lambda, NamedExpression};
-use proc_macro2::Span;
-use std::{
- error::Error,
- fmt::{self, Display},
-};
-
-#[derive(Debug)]
-pub enum TranslateError {
- CallNotAFunction {
- on: Expression,
- span: Option<Span>,
- },
- WrongArgCount {
- lambda: Lambda,
- args: Vec<NamedExpression>,
- span: Option<Span>,
- },
-}
-
-impl From<TranslateError> for syn::Error {
- fn from(e: TranslateError) -> Self {
- let msg = e.to_string();
- let span = match e {
- TranslateError::CallNotAFunction { span, .. }
- | TranslateError::WrongArgCount { span, .. } => span,
- };
-
- Self::new(span.unwrap_or_else(Span::call_site), msg)
- }
-}
-
-impl Display for TranslateError {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- match self {
- Self::CallNotAFunction { .. } => {
- write!(f, "call expected a function")
- }
- Self::WrongArgCount { lambda, args, .. } => match (lambda.args.len(), args.len()) {
- (1, n) => write!(f, "this function takes 1 argument but {} were supplied", n),
- (m, _) => write!(f, "this function takes {} arguments but 1 was supplied", m),
- (m, n) => write!(
- f,
- "this function takes {} arguments but {} were supplied",
- m, n
- ),
- },
- }
- }
-}
-
-impl Error for TranslateError {}
diff --git a/src/chomp/ast/mod.rs b/src/chomp/ast/mod.rs
deleted file mode 100644
index 232381a..0000000
--- a/src/chomp/ast/mod.rs
+++ /dev/null
@@ -1,325 +0,0 @@
-use std::fmt::{self, Display};
-
-use proc_macro2::Span;
-
-use super::Name;
-
-pub mod error;
-pub mod substitute;
-
-#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Hash)]
-pub struct Epsilon;
-
-pub type Literal = String;
-
-#[derive(Clone, Debug)]
-pub struct Cat {
- pub first: Box<NamedExpression>,
- pub rest: Vec<(Option<Span>, NamedExpression)>,
-}
-
-impl Display for Cat {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- write!(f, "({}", self.first)?;
- 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.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 rest: Vec<(Option<Span>, NamedExpression)>
-}
-
-impl Display for Alt {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- write!(f, "({}", self.first)?;
- 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.rest.len() == other.rest.len()
- && self
- .rest
- .iter()
- .zip(other.rest.iter())
- .all(|((_, me), (_, them))| me == them)
- }
-}
-
-impl Eq for Alt {}
-
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub struct Fix {
- pub inner: Box<NamedExpression>,
-}
-
-impl Display for Fix {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- write!(f, "!{}", self.inner)
- }
-}
-
-#[derive(Clone, Copy, 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)
- }
-}
-
-/// A function invocation.
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub struct Call {
- pub on: Box<NamedExpression>,
- pub args: Vec<NamedExpression>,
-}
-
-impl Display for Call {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- write!(f, "({}", self.on)?;
-
- for arg in self.args {
- write!(f, " {}", arg)?;
- }
-
- write!(f, ")")
- }
-}
-
-/// A function abstraction.
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub struct Lambda {
- pub args: Vec<Name>,
- pub inner: Box<NamedExpression>,
-}
-
-impl Display for Lambda {
- 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, "/ {}", self.inner)
- }
-}
-
-#[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 function invocation.
- Call(Call),
- /// A function abstraction.
- Lambda(Lambda),
-}
-
-impl Expression {
- pub fn try_into_lambda(self) -> Result<Lambda, Self> {
- if let Self::Lambda(l) = self {
- Ok(l)
- } else {
- Err(self)
- }
- }
-}
-
-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::Lambda(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::Lambda(p) => {
- if let Self::Lambda(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<Lambda> for Expression {
- fn from(lambda: Lambda) -> Self {
- Self::Lambda(lambda)
- }
-}
-
-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, Eq, PartialEq)]
-pub struct Let {
- pub name: Name,
- pub val: NamedExpression,
- pub inner: Box<TopLevel>,
-}
-
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub enum TopLevel {
- Let(Let),
- Goal(NamedExpression),
-}
diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs
deleted file mode 100644
index 80df588..0000000
--- a/src/chomp/ast/substitute.rs
+++ /dev/null
@@ -1,412 +0,0 @@
-use super::{
- error::TranslateError, Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable,
-};
-use crate::chomp::{
- visit::{Folder, Mapper, Visitable},
- Name,
-};
-use proc_macro2::Span;
-
-struct Deepen {
- pub depth: usize,
- pub by: usize,
-}
-
-impl Mapper for Deepen {
- 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);
- for (_, other) in &mut cat.rest {
- other.map(self);
- }
- }
-
- fn map_alt(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- alt: &mut Alt,
- ) -> Self::Out {
- alt.first.map(self);
- for (_, other) in &mut alt.rest {
- other.map(self);
- }
- }
-
- fn map_fix(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- fix: &mut Fix,
- ) -> Self::Out {
- fix.inner.map(self);
- }
-
- fn map_variable(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- var: &mut Variable,
- ) -> Self::Out {
- if var.index >= self.depth {
- var.index += self.by;
- }
- }
-
- fn map_call(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- call: &mut Call,
- ) -> Self::Out {
- call.on.map(self);
- for arg in &mut call.args {
- arg.map(self);
- }
- }
-
- fn map_lambda(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- lambda: &mut Lambda,
- ) -> Self::Out {
- self.depth += lambda.args.len();
- lambda.inner.map(self);
- self.depth -= lambda.args.len();
- }
-}
-
-pub struct Substitute {
- pub index: usize,
- pub expr: NamedExpression,
-}
-
-impl Folder for Substitute {
- 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.rest = cat
- .rest
- .into_iter()
- .map(|(span, e)| (span, e.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.rest = alt
- .rest
- .into_iter()
- .map(|(span, e)| (span, e.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_variable(
- &mut self,
- name: Option<Name>,
- span: Option<Span>,
- var: Variable,
- ) -> Self::Out {
- if var.index == self.index {
- self.expr.clone()
- } else {
- NamedExpression {
- name,
- expr: Variable {
- index: if var.index > self.index {
- var.index - 1
- } else {
- var.index
- },
- }
- .into(),
- span,
- }
- }
- }
-
- fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
- call.on = Box::new(call.on.fold(self));
- call.args = call.args.into_iter().map(|e| e.fold(self)).collect();
- NamedExpression {
- name,
- expr: call.into(),
- span,
- }
- }
-
- fn fold_lambda(
- &mut self,
- name: Option<Name>,
- span: Option<Span>,
- mut lambda: Lambda,
- ) -> Self::Out {
- self.index += lambda.args.len();
- lambda.inner = Box::new(lambda.inner.fold(self));
- self.index -= lambda.args.len();
- NamedExpression {
- name,
- expr: lambda.into(),
- span,
- }
- }
-}
-
-pub struct Translate {
- changed: bool,
-}
-
-impl Translate {
- pub fn new() -> Self {
- Self { changed: false }
- }
-}
-
-impl Default for Translate {
- fn default() -> Self {
- Self::new()
- }
-}
-
-impl Folder for Translate {
- type Out = Result<NamedExpression, TranslateError>;
-
- 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>, cat: Cat) -> Self::Out {
- Ok(NamedExpression {
- name,
- expr: cat.into(),
- span,
- })
- }
-
- fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
- Ok(NamedExpression {
- name,
- expr: alt.into(),
- span,
- })
- }
-
- fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
- 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_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out {
- let mut on = *call.on;
- self.changed = true;
- while self.changed {
- self.changed = false;
- on = on.fold(self)?;
- }
-
- let lambda = on
- .expr
- .try_into_lambda()
- .map_err(|on| TranslateError::CallNotAFunction { on, span })?;
-
- if lambda.args.len() != call.args.len() {
- return Err(TranslateError::WrongArgCount {
- lambda,
- args: call.args,
- span,
- });
- }
-
- let mut out = *lambda.inner;
-
- for ((i, mut arg), name) in call.args.into_iter().enumerate().zip(lambda.args).rev() {
- arg.name = arg.name.or(Some(name));
- arg.map(&mut Deepen { depth: 0, by: i });
- out = out.fold(&mut Substitute {
- index: 0,
- expr: arg,
- });
- }
-
- self.changed = true;
- while self.changed {
- self.changed = false;
- out = out.fold(self)?;
- }
-
- self.changed = true;
- out.name = name.or(out.name);
- out.span = span.or(out.span);
- Ok(out)
- }
-
- fn fold_lambda(&mut self, name: Option<Name>, span: Option<Span>, lambda: Lambda) -> Self::Out {
- Ok(NamedExpression {
- name,
- expr: lambda.into(),
- span,
- })
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- /// Returns (/x/ x) 'index
- fn make_expr(index: usize) -> NamedExpression {
- let var = NamedExpression {
- name: None,
- expr: Variable { index: 0 }.into(),
- span: None,
- };
-
- let lambda = NamedExpression {
- name: None,
- expr: Lambda {
- args: vec!["x".to_owned().into()],
- inner: Box::new(var),
- }
- .into(),
- span: None,
- };
-
- let var = NamedExpression {
- name: None,
- expr: Variable { index }.into(),
- span: None,
- };
-
- NamedExpression {
- name: None,
- expr: Call {
- on: Box::new(lambda),
- args: vec![var],
- }
- .into(),
- span: None,
- }
- }
-
- #[test]
- fn deepen_lambda() {
- let mut expr = make_expr(0);
- expr.map(&mut Deepen { depth: 0, by: 1 });
- assert_eq!(expr, make_expr(1))
- }
-
- #[test]
- fn substitute_renames_bigger() {
- let expr = make_expr(1);
- let expr = expr.fold(&mut Substitute {
- index: 0,
- expr: NamedExpression {
- name: None,
- expr: Epsilon.into(),
- span: None,
- },
- });
- assert_eq!(expr, make_expr(0))
- }
-
- #[test]
- fn translate_lambda() {
- let expr = make_expr(1);
- let expr = expr.fold(&mut Translate::new()).unwrap();
- assert_eq!(
- expr,
- NamedExpression {
- name: Some("x".to_owned().into()),
- expr: Variable { index: 1 }.into(),
- span: None
- }
- )
- }
-}
generated by cgit v1.2.3 (git 2.49.0) at 2025-04-30 15:18:42 +0000