summaryrefslogtreecommitdiff
path: root/src/chomp/ast/substitute.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/chomp/ast/substitute.rs')
-rw-r--r--src/chomp/ast/substitute.rs229
1 files changed, 149 insertions, 80 deletions
diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs
index 80df588..c6d3ef6 100644
--- a/src/chomp/ast/substitute.rs
+++ b/src/chomp/ast/substitute.rs
@@ -1,24 +1,32 @@
+use std::array;
+
use super::{
- error::TranslateError, Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable,
+ error::ReductionError, Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Let, Literal,
+ NamedExpression, Variable,
};
use crate::chomp::{
+ name::Name,
visit::{Folder, Mapper, Visitable},
- Name,
};
use proc_macro2::Span;
-struct Deepen {
- pub depth: usize,
- pub by: usize,
+enum Direction {
+ Deepen,
+ Shallow,
+}
+struct RenameVars {
+ depth: usize,
+ by: usize,
+ direction: Direction,
}
-impl Mapper for Deepen {
+impl Mapper for RenameVars {
type Out = ();
fn map_epsilon(
&mut self,
_name: &mut Option<Name>,
- _span: Option<Span>,
+ _span: Span,
_eps: &mut Epsilon,
) -> Self::Out {
}
@@ -26,7 +34,7 @@ impl Mapper for Deepen {
fn map_literal(
&mut self,
_name: &mut Option<Name>,
- _span: Option<Span>,
+ _span: Span,
_lit: &mut Literal,
) -> Self::Out {
}
@@ -34,7 +42,7 @@ impl Mapper for Deepen {
fn map_cat(
&mut self,
_name: &mut Option<Name>,
- _span: Option<Span>,
+ _span: Span,
cat: &mut Cat,
) -> Self::Out {
cat.first.map(self);
@@ -46,7 +54,7 @@ impl Mapper for Deepen {
fn map_alt(
&mut self,
_name: &mut Option<Name>,
- _span: Option<Span>,
+ _span: Span,
alt: &mut Alt,
) -> Self::Out {
alt.first.map(self);
@@ -58,7 +66,7 @@ impl Mapper for Deepen {
fn map_fix(
&mut self,
_name: &mut Option<Name>,
- _span: Option<Span>,
+ _span: Span,
fix: &mut Fix,
) -> Self::Out {
fix.inner.map(self);
@@ -67,18 +75,21 @@ impl Mapper for Deepen {
fn map_variable(
&mut self,
_name: &mut Option<Name>,
- _span: Option<Span>,
+ _span: Span,
var: &mut Variable,
) -> Self::Out {
if var.index >= self.depth {
- var.index += self.by;
+ match self.direction {
+ Direction::Deepen => var.index += self.by,
+ Direction::Shallow => var.index -= self.by,
+ }
}
}
fn map_call(
&mut self,
_name: &mut Option<Name>,
- _span: Option<Span>,
+ _span: Span,
call: &mut Call,
) -> Self::Out {
call.on.map(self);
@@ -90,24 +101,56 @@ impl Mapper for Deepen {
fn map_lambda(
&mut self,
_name: &mut Option<Name>,
- _span: Option<Span>,
+ _span: Span,
lambda: &mut Lambda,
) -> Self::Out {
self.depth += lambda.args.len();
lambda.inner.map(self);
self.depth -= lambda.args.len();
}
+
+ fn map_let(
+ &mut self,
+ _name: &mut Option<Name>,
+ _span: Span,
+ stmt: &mut Let,
+ ) -> Self::Out {
+ stmt.bound.map(self);
+ self.depth += 1;
+ stmt.body.map(self);
+ self.depth -= 1;
+ }
}
+#[derive(Debug)]
pub struct Substitute {
pub index: usize,
pub expr: NamedExpression,
}
+impl Substitute {
+ fn with_args<V: Visitable>(&mut self, args: usize, visitable: V) -> <Self as Folder>::Out {
+ self.index += args;
+ self.expr.map(&mut RenameVars {
+ depth: 0,
+ by: args,
+ direction: Direction::Deepen,
+ });
+ let out = visitable.fold(self);
+ self.expr.map(&mut RenameVars {
+ depth: 0,
+ by: args,
+ direction: Direction::Shallow,
+ });
+ self.index -= args;
+ out
+ }
+}
+
impl Folder for Substitute {
type Out = NamedExpression;
- fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+ fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out {
NamedExpression {
name,
expr: eps.into(),
@@ -115,7 +158,7 @@ impl Folder for Substitute {
}
}
- fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+ fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out {
NamedExpression {
name,
expr: lit.into(),
@@ -123,7 +166,7 @@ impl Folder for Substitute {
}
}
- fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out {
+ fn fold_cat(&mut self, name: Option<Name>, span: Span, mut cat: Cat) -> Self::Out {
cat.first = Box::new(cat.first.fold(self));
cat.rest = cat
.rest
@@ -137,7 +180,7 @@ impl Folder for Substitute {
}
}
- fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out {
+ fn fold_alt(&mut self, name: Option<Name>, span: Span, mut alt: Alt) -> Self::Out {
alt.first = Box::new(alt.first.fold(self));
alt.rest = alt
.rest
@@ -151,7 +194,7 @@ impl Folder for Substitute {
}
}
- fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out {
+ fn fold_fix(&mut self, name: Option<Name>, span: Span, mut fix: Fix) -> Self::Out {
fix.inner = Box::new(fix.inner.fold(self));
NamedExpression {
name,
@@ -163,11 +206,13 @@ impl Folder for Substitute {
fn fold_variable(
&mut self,
name: Option<Name>,
- span: Option<Span>,
+ span: Span,
var: Variable,
) -> Self::Out {
if var.index == self.index {
- self.expr.clone()
+ let mut out = self.expr.clone();
+ out.name = Name::merge(out.name, name);
+ out
} else {
NamedExpression {
name,
@@ -184,7 +229,7 @@ impl Folder for Substitute {
}
}
- fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
+ fn fold_call(&mut self, name: Option<Name>, span: 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 {
@@ -197,40 +242,36 @@ impl Folder for Substitute {
fn fold_lambda(
&mut self,
name: Option<Name>,
- span: Option<Span>,
+ span: Span,
mut lambda: Lambda,
) -> Self::Out {
- self.index += lambda.args.len();
- lambda.inner = Box::new(lambda.inner.fold(self));
- self.index -= lambda.args.len();
+ let depth = lambda.args.len();
+ lambda.inner = Box::new(self.with_args(depth, lambda.inner));
NamedExpression {
name,
expr: lambda.into(),
span,
}
}
-}
-pub struct Translate {
- changed: bool,
-}
-
-impl Translate {
- pub fn new() -> Self {
- Self { changed: false }
+ fn fold_let(&mut self, name: Option<Name>, span: Span, mut stmt: Let) -> Self::Out {
+ stmt.bound = Box::new(stmt.bound.fold(self));
+ stmt.body = Box::new(self.with_args(1, stmt.body));
+ NamedExpression {
+ name,
+ expr: stmt.into(),
+ span,
+ }
}
}
-impl Default for Translate {
- fn default() -> Self {
- Self::new()
- }
-}
+#[derive(Copy, Clone, Debug)]
+pub struct Reduce;
-impl Folder for Translate {
- type Out = Result<NamedExpression, TranslateError>;
+impl Folder for Reduce {
+ type Out = Result<NamedExpression, ReductionError>;
- fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+ fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out {
Ok(NamedExpression {
name,
expr: eps.into(),
@@ -238,7 +279,7 @@ impl Folder for Translate {
})
}
- fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+ fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out {
Ok(NamedExpression {
name,
expr: lit.into(),
@@ -246,7 +287,13 @@ impl Folder for Translate {
})
}
- fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+ fn fold_cat(&mut self, name: Option<Name>, span: Span, mut cat: Cat) -> Self::Out {
+ cat.first = Box::new(cat.first.fold(self)?);
+ cat.rest = cat
+ .rest
+ .into_iter()
+ .map(|(p, e)| Ok((p, e.fold(self)?)))
+ .collect::<Result<_, _>>()?;
Ok(NamedExpression {
name,
expr: cat.into(),
@@ -254,7 +301,13 @@ impl Folder for Translate {
})
}
- fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+ fn fold_alt(&mut self, name: Option<Name>, span: Span, mut alt: Alt) -> Self::Out {
+ alt.first = Box::new(alt.first.fold(self)?);
+ alt.rest = alt
+ .rest
+ .into_iter()
+ .map(|(p, e)| Ok((p, e.fold(self)?)))
+ .collect::<Result<_, _>>()?;
Ok(NamedExpression {
name,
expr: alt.into(),
@@ -262,7 +315,13 @@ impl Folder for Translate {
})
}
- fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+ fn fold_fix(&mut self, name: Option<Name>, span: Span, mut fix: Fix) -> Self::Out {
+ let mut inner = fix.inner.fold(self)?;
+ if let Expression::Lambda(mut l) = inner.expr {
+ l.inner = Box::new(l.inner.fold(self)?);
+ inner.expr = Expression::Lambda(l);
+ }
+ fix.inner = Box::new(inner);
Ok(NamedExpression {
name,
expr: fix.into(),
@@ -273,7 +332,7 @@ impl Folder for Translate {
fn fold_variable(
&mut self,
name: Option<Name>,
- span: Option<Span>,
+ span: Span,
var: Variable,
) -> Self::Out {
Ok(NamedExpression {
@@ -283,21 +342,16 @@ impl Folder for Translate {
})
}
- 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)?;
- }
+ fn fold_call(&mut self, name: Option<Name>, span: Span, call: Call) -> Self::Out {
+ let on = call.on.fold(self)?;
let lambda = on
.expr
.try_into_lambda()
- .map_err(|on| TranslateError::CallNotAFunction { on, span })?;
+ .map_err(|on| ReductionError::CallNotAFunction { on, span })?;
if lambda.args.len() != call.args.len() {
- return Err(TranslateError::WrongArgCount {
+ return Err(ReductionError::WrongArgCount {
lambda,
args: call.args,
span,
@@ -307,33 +361,44 @@ impl Folder for Translate {
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 });
+ arg.name = Name::merge(arg.name, Some(name));
+ arg.map(&mut RenameVars {
+ depth: 0,
+ by: i,
+ direction: Direction::Deepen,
+ });
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);
+ out = out.fold(self)?;
+ out.name = Name::merge_all(array::IntoIter::new([name, on.name, out.name]));
+ out.span = span;
Ok(out)
}
- fn fold_lambda(&mut self, name: Option<Name>, span: Option<Span>, lambda: Lambda) -> Self::Out {
+ fn fold_lambda(&mut self, name: Option<Name>, span: Span, lambda: Lambda) -> Self::Out {
Ok(NamedExpression {
name,
expr: lambda.into(),
span,
})
}
+
+ fn fold_let(&mut self, name: Option<Name>, span: Span, stmt: Let) -> Self::Out {
+ let mut out = stmt
+ .body
+ .fold(&mut Substitute {
+ index: 0,
+ expr: *stmt.bound,
+ })
+ .fold(self)?;
+ out.name = Name::merge(out.name, name);
+ out.span = span;
+ Ok(out)
+ }
}
#[cfg(test)]
@@ -345,23 +410,23 @@ mod tests {
let var = NamedExpression {
name: None,
expr: Variable { index: 0 }.into(),
- span: None,
+ span: Span::call_site(),
};
let lambda = NamedExpression {
name: None,
expr: Lambda {
- args: vec!["x".to_owned().into()],
+ args: vec![Name::new_variable("x".to_owned())],
inner: Box::new(var),
}
.into(),
- span: None,
+ span: Span::call_site(),
};
let var = NamedExpression {
name: None,
expr: Variable { index }.into(),
- span: None,
+ span: Span::call_site(),
};
NamedExpression {
@@ -371,14 +436,18 @@ mod tests {
args: vec![var],
}
.into(),
- span: None,
+ span: Span::call_site(),
}
}
#[test]
fn deepen_lambda() {
let mut expr = make_expr(0);
- expr.map(&mut Deepen { depth: 0, by: 1 });
+ expr.map(&mut RenameVars {
+ depth: 0,
+ by: 1,
+ direction: Direction::Deepen,
+ });
assert_eq!(expr, make_expr(1))
}
@@ -390,22 +459,22 @@ mod tests {
expr: NamedExpression {
name: None,
expr: Epsilon.into(),
- span: None,
+ span: Span::call_site(),
},
});
assert_eq!(expr, make_expr(0))
}
#[test]
- fn translate_lambda() {
+ fn reduce_lambda() {
let expr = make_expr(1);
- let expr = expr.fold(&mut Translate::new()).unwrap();
+ let expr = expr.fold(&mut Reduce).unwrap();
assert_eq!(
expr,
NamedExpression {
- name: Some("x".to_owned().into()),
+ name: Some(Name::new_variable("x".to_owned())),
expr: Variable { index: 1 }.into(),
- span: None
+ span: Span::call_site(),
}
)
}
generated by cgit v1.2.3 (git 2.49.0) at 2025-04-30 11:37:09 +0000