summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/chomp/ast/error.rs22
-rw-r--r--src/chomp/ast/mod.rs115
-rw-r--r--src/chomp/ast/substitute.rs229
-rw-r--r--src/chomp/mod.rs111
-rw-r--r--src/chomp/name.rs217
-rw-r--r--src/chomp/set.rs27
-rw-r--r--src/chomp/typed/context.rs15
-rw-r--r--src/chomp/typed/error.rs93
-rw-r--r--src/chomp/typed/infer.rs213
-rw-r--r--src/chomp/typed/lower.rs16
-rw-r--r--src/chomp/typed/mod.rs140
-rw-r--r--src/chomp/visit.rs119
-rw-r--r--src/lower/mod.rs63
-rw-r--r--src/main.rs25
-rw-r--r--src/nibble/convert.rs133
-rw-r--r--src/nibble/mod.rs269
16 files changed, 998 insertions, 809 deletions
diff --git a/src/chomp/ast/error.rs b/src/chomp/ast/error.rs
index 9057ec3..ea145a7 100644
--- a/src/chomp/ast/error.rs
+++ b/src/chomp/ast/error.rs
@@ -6,31 +6,31 @@ use std::{
};
#[derive(Debug)]
-pub enum TranslateError {
+pub enum ReductionError {
CallNotAFunction {
on: Expression,
- span: Option<Span>,
+ span: Span,
},
WrongArgCount {
lambda: Lambda,
args: Vec<NamedExpression>,
- span: Option<Span>,
+ span: Span,
},
}
-impl From<TranslateError> for syn::Error {
- fn from(e: TranslateError) -> Self {
+impl From<ReductionError> for syn::Error {
+ fn from(e: ReductionError) -> Self {
let msg = e.to_string();
let span = match e {
- TranslateError::CallNotAFunction { span, .. }
- | TranslateError::WrongArgCount { span, .. } => span,
+ ReductionError::CallNotAFunction { span, .. }
+ | ReductionError::WrongArgCount { span, .. } => span,
};
- Self::new(span.unwrap_or_else(Span::call_site), msg)
+ Self::new(span, msg)
}
}
-impl Display for TranslateError {
+impl Display for ReductionError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::CallNotAFunction { .. } => {
@@ -38,7 +38,7 @@ impl Display for TranslateError {
}
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, 1) => write!(f, "this function takes {} arguments but 1 was supplied", m),
(m, n) => write!(
f,
"this function takes {} arguments but {} were supplied",
@@ -49,4 +49,4 @@ impl Display for TranslateError {
}
}
-impl Error for TranslateError {}
+impl Error for ReductionError {}
diff --git a/src/chomp/ast/mod.rs b/src/chomp/ast/mod.rs
index 232381a..7b3ea16 100644
--- a/src/chomp/ast/mod.rs
+++ b/src/chomp/ast/mod.rs
@@ -2,7 +2,7 @@ use std::fmt::{self, Display};
use proc_macro2::Span;
-use super::Name;
+use super::name::Name;
pub mod error;
pub mod substitute;
@@ -15,7 +15,7 @@ pub type Literal = String;
#[derive(Clone, Debug)]
pub struct Cat {
pub first: Box<NamedExpression>,
- pub rest: Vec<(Option<Span>, NamedExpression)>,
+ pub rest: Vec<(Span, NamedExpression)>,
}
impl Display for Cat {
@@ -45,7 +45,7 @@ impl Eq for Cat {}
#[derive(Clone, Debug)]
pub struct Alt {
pub first: Box<NamedExpression>,
- pub rest: Vec<(Option<Span>, NamedExpression)>
+ pub rest: Vec<(Span, NamedExpression)>
}
impl Display for Alt {
@@ -105,7 +105,7 @@ impl Display for Call {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "({}", self.on)?;
- for arg in self.args {
+ for arg in &self.args {
write!(f, " {}", arg)?;
}
@@ -135,7 +135,21 @@ impl Display for Lambda {
}
}
-#[derive(Clone, Debug)]
+/// A let statement.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Let {
+ pub name: Name,
+ pub bound: Box<NamedExpression>,
+ pub body: Box<NamedExpression>,
+}
+
+impl Display for Let {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "let {} = {}; {}", self.name, self.bound, self.body)
+ }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expression {
/// Matches the empty string.
Epsilon(Epsilon),
@@ -153,6 +167,8 @@ pub enum Expression {
Call(Call),
/// A function abstraction.
Lambda(Lambda),
+ /// A let statement
+ Let(Let),
}
impl Expression {
@@ -176,69 +192,11 @@ impl Display for Expression {
Self::Variable(v) => v.fmt(f),
Self::Lambda(p) => p.fmt(f),
Self::Call(c) => c.fmt(f),
+ Self::Let(l) => l.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)
@@ -287,17 +245,29 @@ impl From<Call> for Expression {
}
}
+impl From<Let> for Expression {
+ fn from(stmt: Let) -> Self {
+ Self::Let(stmt)
+ }
+}
+
#[derive(Clone, Debug)]
pub struct NamedExpression {
pub name: Option<Name>,
+ pub span: Span,
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),
+ Some(name) => {
+ if let Expression::Variable(_) = self.expr {
+ write!(f, "{}", name)
+ } else {
+ write!(f, "({} : {})", self.expr, name)
+ }
+ },
None => self.expr.fmt(f),
}
}
@@ -310,16 +280,3 @@ impl PartialEq for NamedExpression {
}
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
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(),
}
)
}
diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs
index 79b4fac..029c10f 100644
--- a/src/chomp/mod.rs
+++ b/src/chomp/mod.rs
@@ -1,114 +1,7 @@
-use std::{fmt, hash};
-
-use heck::{CamelCase, SnakeCase};
-use proc_macro2::{Ident, Span};
-use syn::ext::IdentExt;
+use proc_macro2::Span;
pub mod ast;
+pub mod name;
pub mod set;
pub mod typed;
pub mod visit;
-
-#[derive(Clone, Debug)]
-pub enum Name {
- Spanned(Ident),
- Spanless(String),
-}
-
-impl Name {
- pub fn span(&self) -> Option<Span> {
- match self {
- Self::Spanned(i) => Some(i.span()),
- Self::Spanless(_) => None,
- }
- }
-
- pub fn into_ident(self, span: Span) -> Ident {
- match self {
- Self::Spanned(i) => i,
- Self::Spanless(s) => Ident::new(&s, span),
- }
- }
-}
-
-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) {
- (Self::Spanned(me), Self::Spanned(them)) => me == them,
- (Self::Spanned(me), Self::Spanless(them)) => me.unraw() == them,
- (Self::Spanless(me), Self::Spanned(them)) => them.unraw() == me,
- (Self::Spanless(me), Self::Spanless(them)) => me == them,
- }
- }
-}
-
-impl<T: AsRef<str>> PartialEq<T> for Name {
- fn eq(&self, other: &T) -> bool {
- match self {
- Name::Spanned(me) => me.unraw() == other,
- Name::Spanless(me) => me == other.as_ref(),
- }
- }
-}
-
-impl Eq for Name {}
-
-impl hash::Hash for Name {
- fn hash<H: hash::Hasher>(&self, state: &mut H) {
- match self {
- Self::Spanned(i) => i.unraw().to_string().hash(state),
- Self::Spanless(s) => s.hash(state),
- }
- }
-}
-
-impl fmt::Display for Name {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- match self {
- Name::Spanned(i) => i.fmt(f),
- Name::Spanless(s) => s.fmt(f),
- }
- }
-}
-
-impl From<Ident> for Name {
- fn from(ident: Ident) -> Self {
- Self::Spanned(ident)
- }
-}
-
-impl From<String> for Name {
- fn from(string: String) -> Self {
- Self::Spanless(string)
- }
-}
diff --git a/src/chomp/name.rs b/src/chomp/name.rs
new file mode 100644
index 0000000..450b6e9
--- /dev/null
+++ b/src/chomp/name.rs
@@ -0,0 +1,217 @@
+use std::{
+ array::IntoIter,
+ cmp::{self, Ordering},
+ fmt, hash,
+};
+
+use heck::{CamelCase, SnakeCase};
+use proc_macro2::{Ident, Span};
+use syn::{ext::IdentExt, spanned::Spanned};
+
+#[derive(Clone, Debug)]
+pub enum Content {
+ Spanned(Ident),
+ Spanless(String),
+}
+
+impl Spanned for Content {
+ fn span(&self) -> Span {
+ match self {
+ Content::Spanned(i) => i.span(),
+ Content::Spanless(_) => Span::call_site(),
+ }
+ }
+}
+
+impl From<Content> for Ident {
+ fn from(content: Content) -> Self {
+ match content {
+ Content::Spanned(i) => i,
+ Content::Spanless(s) => Ident::new(&s, Span::call_site()),
+ }
+ }
+}
+
+impl CamelCase for Content {
+ 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()
+ }
+ Self::Spanless(name) => name.to_camel_case().into(),
+ }
+ }
+}
+
+impl SnakeCase for Content {
+ 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()
+ }
+ Self::Spanless(name) => name.to_snake_case().into(),
+ }
+ }
+}
+
+impl PartialEq for Content {
+ fn eq(&self, other: &Self) -> bool {
+ match (self, other) {
+ (Self::Spanned(me), Self::Spanned(them)) => me == them,
+ (Self::Spanned(me), Self::Spanless(them)) => me.unraw() == them,
+ (Self::Spanless(me), Self::Spanned(them)) => them.unraw() == me,
+ (Self::Spanless(me), Self::Spanless(them)) => me == them,
+ }
+ }
+}
+
+impl<T: AsRef<str>> PartialEq<T> for Content {
+ fn eq(&self, other: &T) -> bool {
+ match self {
+ Self::Spanned(me) => me.unraw() == other,
+ Self::Spanless(me) => me == other.as_ref(),
+ }
+ }
+}
+
+impl Eq for Content {}
+
+impl hash::Hash for Content {
+ fn hash<H: hash::Hasher>(&self, state: &mut H) {
+ match self {
+ Self::Spanned(i) => i.unraw().to_string().hash(state),
+ Self::Spanless(s) => s.hash(state),
+ }
+ }
+}
+
+impl fmt::Display for Content {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Self::Spanned(i) => i.fmt(f),
+ Self::Spanless(s) => s.fmt(f),
+ }
+ }
+}
+
+impl From<Ident> for Content {
+ fn from(ident: Ident) -> Self {
+ Self::Spanned(ident)
+ }
+}
+
+impl From<String> for Content {
+ fn from(string: String) -> Self {
+ Self::Spanless(string)
+ }
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
+pub enum Kind {
+ Label,
+ Let,
+ Variable,
+}
+
+impl PartialOrd for Kind {
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ Some(match (self, other) {
+ (Kind::Label, Kind::Label)
+ | (Kind::Let, Kind::Let)
+ | (Kind::Variable, Kind::Variable) => Ordering::Equal,
+ (Kind::Label, Kind::Let)
+ | (Kind::Label, Kind::Variable)
+ | (Kind::Let, Kind::Variable) => Ordering::Greater,
+ (Kind::Let, Kind::Label)
+ | (Kind::Variable, Kind::Label)
+ | (Kind::Variable, Kind::Let) => Ordering::Less,
+ })
+ }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct Name {
+ pub content: Content,
+ kind: Kind,
+}
+
+impl Name {
+ pub fn new_variable<T: Into<Content>>(content: T) -> Self {
+ Self {
+ content: content.into(),
+ kind: Kind::Variable,
+ }
+ }
+
+ pub fn new_let<T: Into<Content>>(content: T) -> Self {
+ Self {
+ content: content.into(),
+ kind: Kind::Let,
+ }
+ }
+
+ pub fn new_label<T: Into<Content>>(content: T) -> Self {
+ Self {
+ content: content.into(),
+ kind: Kind::Label,
+ }
+ }
+
+ pub fn merge(this: Option<Self>, that: Option<Self>) -> Option<Self> {
+ match (this, that) {
+ (None, that) => that,
+ (Some(this), None) => Some(this),
+ (Some(this), Some(that)) => {
+ if this.kind >= that.kind {
+ Some(this)
+ } else {
+ Some(that)
+ }
+ }
+ }
+ }
+
+ pub fn merge_all<I: IntoIterator<Item = Option<Self>>>(iter: I) -> Option<Self> {
+ iter.into_iter().fold(None, Self::merge)
+ }
+}
+
+impl Spanned for Name {
+ fn span(&self) -> Span {
+ self.content.span()
+ }
+}
+
+impl From<Name> for Ident {
+ fn from(name: Name) -> Self {
+ name.content.into()
+ }
+}
+
+impl CamelCase for Name {
+ fn to_camel_case(&self) -> Self::Owned {
+ Self {
+ content: self.content.to_camel_case(),
+ kind: self.kind,
+ }
+ }
+}
+
+impl SnakeCase for Name {
+ fn to_snake_case(&self) -> Self::Owned {
+ Self {
+ content: self.content.to_snake_case(),
+ kind: self.kind,
+ }
+ }
+}
+
+impl fmt::Display for Name {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ self.content.fmt(f)
+ }
+}
diff --git a/src/chomp/set.rs b/src/chomp/set.rs
index 0661ab6..db533da 100644
--- a/src/chomp/set.rs
+++ b/src/chomp/set.rs
@@ -21,15 +21,12 @@ impl FirstSet {
self.inner.is_empty()
}
- pub fn union(mut self, mut other: Self) -> Self {
+ pub fn union(&mut self, mut other: Self) {
self.inner.append(&mut other.inner);
- self
}
- pub fn intersect(&self, other: &Self) -> Self {
- Self {
- inner: self.inner.intersection(&other.inner).copied().collect(),
- }
+ pub fn disjoint(&self, other: &Self) -> bool {
+ self.inner.intersection(&other.inner).next().is_none()
}
}
@@ -57,26 +54,16 @@ impl FlastSet {
self.inner.is_empty()
}
- pub fn union_first(mut self, mut other: FirstSet) -> Self {
+ pub fn union_first(&mut self, mut other: FirstSet) {
self.inner.append(&mut other.inner);
- self
}
- pub fn union(mut self, mut other: Self) -> Self {
+ pub fn union(&mut self, mut other: Self) {
self.inner.append(&mut other.inner);
- self
}
- pub fn intersect_first(&self, other: &FirstSet) -> Self {
- Self {
- inner: self.inner.intersection(&other.inner).copied().collect(),
- }
- }
-
- pub fn intersect(&self, other: &Self) -> Self {
- Self {
- inner: self.inner.intersection(&other.inner).copied().collect(),
- }
+ pub fn disjoint(&self, other: &FirstSet) -> bool {
+ self.inner.intersection(&other.inner).next().is_none()
}
}
diff --git a/src/chomp/typed/context.rs b/src/chomp/typed/context.rs
index f3263ce..7ac4ae0 100644
--- a/src/chomp/typed/context.rs
+++ b/src/chomp/typed/context.rs
@@ -30,16 +30,11 @@ impl Context {
.nth_back(var.index)
.ok_or(GetVariableError::FreeVariable)
.and_then(|ty| {
- self.unguard_points
- .last()
- .and_then(|point| {
- if point + var.index >= self.vars.len() {
- Some(ty)
- } else {
- None
- }
- })
- .ok_or(GetVariableError::GuardedVariable)
+ if self.unguard_points.last().unwrap_or(&0) + var.index >= self.vars.len() {
+ Ok(ty)
+ } else {
+ Err(GetVariableError::GuardedVariable)
+ }
})
}
diff --git a/src/chomp/typed/error.rs b/src/chomp/typed/error.rs
index 5c1e21e..48bfa25 100644
--- a/src/chomp/typed/error.rs
+++ b/src/chomp/typed/error.rs
@@ -5,27 +5,19 @@ use std::{
use proc_macro2::Span;
-use crate::chomp::{ast::Variable, Name};
+use crate::chomp::{name::Name, ast::{Call, Fix, Lambda, Let, Variable}};
-use super::{context::GetVariableError, TypedExpression};
+use super::{Type, TypedExpression, context::GetVariableError};
/// 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 span: Span,
pub name: Option<Name>,
}
-impl From<VariableError> for syn::Error {
- fn from(other: VariableError) -> Self {
- let msg = other.to_string();
- let span = other.span;
- Self::new(span.unwrap_or_else(Span::call_site), msg)
- }
-}
-
impl Display for VariableError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match &self.inner {
@@ -47,24 +39,20 @@ impl Error for VariableError {}
pub enum CatError {
FirstNullable {
expr: TypedExpression,
- punct: Option<Span>,
+ punct: Span,
},
FirstFlastOverlap {
- first: Vec<TypedExpression>,
- punct: Option<Span>,
+ front_ty: Type,
+ punct: Span,
next: TypedExpression,
},
}
-impl From<CatError> for syn::Error {
- fn from(other: CatError) -> Self {
- let msg = other.to_string();
- let span = match other {
- CatError::FirstNullable { punct, .. } | CatError::FirstFlastOverlap { punct, .. } => {
- punct
- }
- };
- Self::new(span.unwrap_or_else(Span::call_site), msg)
+impl CatError {
+ pub fn span(&self) -> Span {
+ match self {
+ Self::FirstNullable { punct, .. } | Self::FirstFlastOverlap { punct, .. } => *punct,
+ }
}
}
@@ -84,24 +72,22 @@ impl Error for CatError {}
#[derive(Debug)]
pub enum AltError {
BothNullable {
- left: Vec<TypedExpression>,
- punct: Option<Span>,
+ left_ty: Type,
+ punct: Span,
right: TypedExpression,
},
FirstOverlap {
- left: Vec<TypedExpression>,
- punct: Option<Span>,
+ left_ty: Type,
+ punct: Span,
right: TypedExpression,
},
}
-impl From<AltError> for syn::Error {
- fn from(other: AltError) -> Self {
- let msg = other.to_string();
- let span = match other {
- AltError::BothNullable { punct, .. } | AltError::FirstOverlap { punct, .. } => punct,
- };
- Self::new(span.unwrap_or_else(Span::call_site), msg)
+impl AltError {
+ pub fn span(&self) -> Span {
+ match self {
+ Self::BothNullable { punct, .. } | Self::FirstOverlap { punct, .. } => *punct,
+ }
}
}
@@ -121,6 +107,24 @@ pub enum TypeError {
Cat(CatError),
Alt(AltError),
Variable(VariableError),
+ UnexpectedCall { span: Span, call: Call },
+ UnexpectedLambda { span: Span, lambda: Lambda },
+ UnexpectedLet { span: Span, stmt: Let },
+ ExpectedLambda {span: Span, fix: Fix },
+}
+
+impl TypeError {
+ pub fn span(&self) -> Span {
+ match self {
+ TypeError::Cat(c) => c.span(),
+ TypeError::Alt(a) => a.span(),
+ TypeError::Variable(v) => v.span,
+ TypeError::UnexpectedCall { span, .. }
+ | TypeError::UnexpectedLambda { span, .. }
+ | TypeError::UnexpectedLet { span, .. }
+ | TypeError::ExpectedLambda { span, .. } => *span,
+ }
+ }
}
impl From<CatError> for TypeError {
@@ -143,11 +147,9 @@ impl From<VariableError> for TypeError {
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(),
- }
+ let span = other.span();
+ let msg = format!("{}", other);
+ Self::new(span, msg)
}
}
@@ -157,6 +159,19 @@ impl Display for TypeError {
Self::Cat(e) => e.fmt(f),
Self::Alt(e) => e.fmt(f),
Self::Variable(e) => e.fmt(f),
+
+ Self::UnexpectedCall { .. } => {
+ write!(f, "unexpected call")
+ }
+ Self::UnexpectedLambda { .. } => {
+ write!(f, "unexpected lambda")
+ }
+ Self::UnexpectedLet { .. } => {
+ write!(f, "unexpected let")
+ }
+ Self::ExpectedLambda { .. } => {
+ write!(f, "expected a lambda expression")
+ }
}
}
}
diff --git a/src/chomp/typed/infer.rs b/src/chomp/typed/infer.rs
index e2c2198..bc2baea 100644
--- a/src/chomp/typed/infer.rs
+++ b/src/chomp/typed/infer.rs
@@ -1,8 +1,18 @@
+use std::{array, iter};
+
use proc_macro2::Span;
-use crate::chomp::{Name, ast::{Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, substitute::Translate}, visit::{Folder, Visitable}};
+use crate::chomp::{
+ ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Let, Literal, Variable},
+ name::Name,
+ visit::{Folder, Visitable},
+};
-use super::{Type, Typed, TypedExpression, context::Context, error::{TypeError, VariableError}};
+use super::{
+ context::Context,
+ error::{AltError, CatError, TypeError, VariableError},
+ Type, Typed, TypedExpression,
+};
#[derive(Debug)]
pub struct TypeInfer<'a> {
@@ -12,7 +22,7 @@ pub struct TypeInfer<'a> {
impl Folder for TypeInfer<'_> {
type Out = Result<TypedExpression, TypeError>;
- 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(TypedExpression {
inner: super::Epsilon::from(eps).into(),
name,
@@ -20,7 +30,7 @@ impl Folder for TypeInfer<'_> {
})
}
- 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(TypedExpression {
inner: super::Literal::from(lit).into(),
name,
@@ -28,47 +38,99 @@ impl Folder for TypeInfer<'_> {
})
}
- 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, cat: Cat) -> Self::Out {
let first = cat.first.fold(self)?;
+
+ if first.get_type().nullable() {
+ let punct = cat.rest.into_iter().next().map(|(p, _)| p).unwrap_or_else(Span::call_site);
+ return Err(CatError::FirstNullable { expr: first, punct }.into());
+ }
+
let rest = cat.rest;
- self.context
- .with_unguard(|context| -> Result<TypedExpression, TypeError> {
- let mut infer = TypeInfer { context };
- let rest = rest
- .into_iter()
- .map(|(punct, term)| -> Result<_, TypeError> {
- Ok((punct, term.fold(&mut infer)?))
- })
- .collect::<Result<Vec<_>, _>>()?;
- Ok(TypedExpression {
- inner: super::Cat::new(first, rest)?.into(),
- name,
- span,
+ let mut ty = first.get_type().clone();
+ let terms = self.context.with_unguard(|context| {
+ let mut infer = TypeInfer { context };
+ rest.into_iter()
+ .map(|(punct, right)| {
+ let right = right.fold(&mut infer)?;
+ if ty.flast_set().disjoint(right.get_type().first_set()) {
+ ty.cat(right.get_type().clone());
+ Ok(right)
+ } else {
+ Err(CatError::FirstFlastOverlap {
+ front_ty: ty.clone(),
+ punct,
+ next: right,
+ }
+ .into())
+ }
})
- })
+ .collect::<Result<Vec<_>, TypeError>>()
+ })?;
+ Ok(TypedExpression {
+ inner: super::Cat {
+ terms: iter::once(first).chain(terms).collect(),
+ ty,
+ }
+ .into(),
+ name,
+ span,
+ })
}
- 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, alt: Alt) -> Self::Out {
let first = alt.first.fold(self)?;
- let rest = alt
+ let mut ty = first.get_type().clone();
+ let terms = alt
.rest
.into_iter()
- .map(|(punct, term)| -> Result<_, TypeError> { Ok((punct, term.fold(self)?)) })
- .collect::<Result<Vec<_>, _>>()?;
+ .map(|(punct, right)| {
+ let right = right.fold(self)?;
+ if ty.nullable() && right.get_type().nullable() {
+ Err(AltError::BothNullable {
+ left_ty: ty.clone(),
+ punct,
+ right,
+ }
+ .into())
+ } else if ty.first_set().disjoint(right.get_type().first_set()) {
+ ty.alt(right.get_type().clone());
+ Ok(right)
+ } else {
+ Err(AltError::FirstOverlap {
+ left_ty: ty.clone(),
+ punct,
+ right,
+ }
+ .into())
+ }
+ })
+ .collect::<Result<Vec<_>, TypeError>>()?;
Ok(TypedExpression {
- inner: super::Alt::new(first, rest)?.into(),
+ inner: super::Alt {
+ terms: iter::once(first).chain(terms).collect(),
+ ty,
+ }
+ .into(),
name,
span,
})
}
- 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, fix: Fix) -> Self::Out {
let mut ty = Type::default();
+ let body = if let Expression::Lambda(l) = fix.inner.expr {
+ let mut body = *l.inner;
+ body.name = Name::merge_all(array::IntoIter::new([fix.inner.name, body.name, name.clone()]));
+ body
+ } else {
+ return Err(TypeError::ExpectedLambda { span, fix });
+ };
loop {
let last = ty;
let res = self.context.with_variable_type(last.clone(), |context| {
- fix.inner.clone().fold(&mut TypeInfer { context })
+ body.clone().fold(&mut TypeInfer { context })
})?;
ty = res.get_type().clone();
@@ -88,7 +150,7 @@ impl Folder for TypeInfer<'_> {
fn fold_variable(
&mut self,
name: Option<Name>,
- span: Option<Span>,
+ span: Span,
var: Variable,
) -> Self::Out {
let ty = match self.context.get_variable_type(var) {
@@ -110,18 +172,101 @@ impl Folder for TypeInfer<'_> {
})
}
- fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out {
- let translated = NamedExpression { name, expr: call.into(), span}.fold(&mut Translate::new())?;
- let inner = translated.fold(self)?;
- todo!()
+ fn fold_call(&mut self, _name: Option<Name>, span: Span, call: Call) -> Self::Out {
+ Err(TypeError::UnexpectedCall { span, call })
}
fn fold_lambda(
&mut self,
_name: Option<Name>,
- _span: Option<Span>,
- _lambda: Lambda,
+ span: Span,
+ lambda: Lambda,
) -> Self::Out {
- unimplemented!()
+ Err(TypeError::UnexpectedLambda { span, lambda })
+ }
+
+ fn fold_let(&mut self, _name: Option<Name>, span: Span, stmt: Let) -> Self::Out {
+ Err(TypeError::UnexpectedLet { span, stmt })
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::chomp::{ast::NamedExpression, typed::RawTypedExpression};
+
+ use super::*;
+
+ #[test]
+ fn cat_uses_all() {
+ let ast = Cat {
+ first: Box::new(NamedExpression {
+ name: None,
+ expr: "a".to_owned().into(),
+ span: Span::call_site(),
+ }),
+ rest: vec![(
+ Span::call_site(),
+ NamedExpression {
+ name: None,
+ expr: "b".to_owned().into(),
+ span: Span::call_site(),
+ },
+ )],
+ };
+
+ let typed = NamedExpression {
+ name: None,
+ expr: ast.into(),
+ span: Span::call_site(),
+ }
+ .fold(&mut TypeInfer {
+ context: &mut Context::default(),
+ })
+ .unwrap();
+ match typed.inner {
+ RawTypedExpression::Cat(super::super::Cat { terms, .. }) => assert_eq!(terms.len(), 2),
+ RawTypedExpression::Epsilon(_)
+ | RawTypedExpression::Literal(_)
+ | RawTypedExpression::Alt(_)
+ | RawTypedExpression::Fix(_)
+ | RawTypedExpression::Variable(_) => panic!("Cat should type check to Cat"),
+ };
+ }
+
+ #[test]
+ fn alt_uses_all() {
+ let ast = Alt {
+ first: Box::new(NamedExpression {
+ name: None,
+ expr: "a".to_owned().into(),
+ span: Span::call_site(),
+ }),
+ rest: vec![(
+ Span::call_site(),
+ NamedExpression {
+ name: None,
+ expr: "b".to_owned().into(),
+ span: Span::call_site(),
+ },
+ )],
+ };
+
+ let typed = NamedExpression {
+ name: None,
+ expr: ast.into(),
+ span: Span::call_site(),
+ }
+ .fold(&mut TypeInfer {
+ context: &mut Context::default(),
+ })
+ .unwrap();
+ match typed.inner {
+ RawTypedExpression::Alt(super::super::Alt { terms, .. }) => assert_eq!(terms.len(), 2),
+ RawTypedExpression::Epsilon(_)
+ | RawTypedExpression::Literal(_)
+ | RawTypedExpression::Cat(_)
+ | RawTypedExpression::Fix(_)
+ | RawTypedExpression::Variable(_) => panic!("Alt should type check to Alt"),
+ };
}
}
diff --git a/src/chomp/typed/lower.rs b/src/chomp/typed/lower.rs
index 37589a1..03237de 100644
--- a/src/chomp/typed/lower.rs
+++ b/src/chomp/typed/lower.rs
@@ -1,6 +1,6 @@
use proc_macro2::Span;
-use crate::chomp::Name;
+use crate::chomp::name::Name;
use super::{Alt, Cat, Epsilon, Fix, Literal, RawTypedExpression, TypedExpression, Variable};
@@ -8,19 +8,19 @@ 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_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Id;
- fn gen_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Id;
+ fn gen_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Id;
- fn gen_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Id;
+ fn gen_cat(&mut self, name: Option<Name>, span: Span, cat: Cat) -> Self::Id;
- fn gen_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Id;
+ fn gen_alt(&mut self, name: Option<Name>, span: Span, alt: Alt) -> Self::Id;
- fn gen_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Id;
+ fn gen_fix(&mut self, name: Option<Name>, span: Span, fix: Fix) -> Self::Id;
- fn gen_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable) -> Self::Id;
+ fn gen_variable(&mut self, name: Option<Name>, span: Span, var: Variable) -> Self::Id;
- fn emit_code(self, name: Option<Name>, span: Option<Span>, id: Self::Id) -> Self::Code;
+ fn emit_code(self, name: Option<Name>, span: Span, id: Self::Id) -> Self::Code;
}
pub trait GenerateCode {
diff --git a/src/chomp/typed/mod.rs b/src/chomp/typed/mod.rs
index cddb05a..f1f6967 100644
--- a/src/chomp/typed/mod.rs
+++ b/src/chomp/typed/mod.rs
@@ -5,7 +5,7 @@ use proc_macro2::Span;
use super::{
ast,
set::{FirstSet, FlastSet},
- Name,
+ name::Name,
};
pub mod context;
@@ -14,7 +14,6 @@ pub mod lower;
mod infer;
-use self::error::{AltError, CatError};
pub use self::infer::TypeInfer;
#[derive(Debug, Default, Clone, Eq, Hash, PartialEq)]
@@ -53,28 +52,25 @@ impl Type {
&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 cat(&mut self, other: Self) {
+ if self.nullable {
+ self.first_set.union(other.first_set.clone())
}
- }
- 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),
+ if other.nullable {
+ self.flast_set.union_first(other.first_set);
+ self.flast_set.union(other.flast_set);
+ } else {
+ self.flast_set = other.flast_set;
}
+
+ self.nullable &= other.nullable;
+ }
+
+ pub fn alt(&mut self, other: Self) {
+ self.nullable |= other.nullable;
+ self.first_set.union(other.first_set);
+ self.flast_set.union(other.flast_set);
}
}
@@ -122,43 +118,6 @@ pub struct Cat {
ty: Type,
}
-impl Cat {
- fn new<I: IntoIterator<Item = (Option<Span>, TypedExpression)>>(
- first: TypedExpression,
- rest: I,
- ) -> Result<Self, CatError> {
- if first.get_type().nullable() {
- return Err(CatError::FirstNullable {
- expr: first,
- punct: todo!(),
- });
- }
-
- rest.into_iter()
- .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()
- {
- let ty = ty.cat(right.get_type().clone());
- terms.push(right);
- Ok((ty, terms))
- } else {
- Err(CatError::FirstFlastOverlap {
- first: terms,
- punct,
- next: right,
- })
- }
- },
- )
- .map(|(ty, terms)| Self { ty, terms })
- }
-}
-
impl IntoIterator for Cat {
type Item = TypedExpression;
@@ -175,42 +134,6 @@ pub struct Alt {
ty: Type,
}
-impl Alt {
- pub fn new<I: IntoIterator<Item = (Option<Span>, TypedExpression)>>(
- first: TypedExpression,
- rest: I,
- ) -> Result<Self, AltError> {
- rest.into_iter()
- .try_fold(
- (first.get_type().clone(), vec![first]),
- |(ty, mut terms), (punct, right)| {
- if ty.nullable() && right.get_type().nullable() {
- Err(AltError::BothNullable {
- left: terms,
- punct,
- right,
- })
- } else if ty
- .first_set()
- .intersect(right.get_type().first_set())
- .is_empty()
- {
- let ty = ty.alt(right.get_type().clone());
- terms.push(right);
- Ok((ty, terms))
- } else {
- Err(AltError::FirstOverlap {
- left: terms,
- punct,
- right,
- })
- }
- },
- )
- .map(|(ty, terms)| Self { ty, terms })
- }
-}
-
impl IntoIterator for Alt {
type Item = TypedExpression;
@@ -245,14 +168,6 @@ impl Variable {
}
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
-pub struct Call {
- ty: Type,
-}
-
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
-pub struct Lambda {}
-
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
enum RawTypedExpression {
Epsilon(Epsilon),
Literal(Literal),
@@ -260,8 +175,6 @@ enum RawTypedExpression {
Alt(Alt),
Fix(Fix),
Variable(Variable),
- Call(Call),
- Lambda(Lambda),
}
impl From<Epsilon> for RawTypedExpression {
@@ -304,7 +217,7 @@ impl From<Variable> for RawTypedExpression {
pub struct TypedExpression {
inner: RawTypedExpression,
pub name: Option<Name>,
- pub span: Option<Span>,
+ pub span: Span,
}
impl PartialEq for TypedExpression {
@@ -360,3 +273,20 @@ impl Typed for TypedExpression {
}
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ #[test]
+ fn cat_right() {
+ let epsilon = Type { nullable: true, ..Type::default()};
+ let mut x = Type::of_str("a");
+ x.cat(Type::of_str("b"));
+ assert_eq!(x, Type::of_str("a"));
+ x.cat(Type::default());
+ assert_eq!(x, Type::of_str("a"));
+ x.cat(epsilon);
+ assert_eq!(x, Type::of_str("a"));
+ }
+}
diff --git a/src/chomp/visit.rs b/src/chomp/visit.rs
index 7e716d3..b37909d 100644
--- a/src/chomp/visit.rs
+++ b/src/chomp/visit.rs
@@ -1,113 +1,81 @@
use proc_macro2::Span;
use super::{
- ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Literal, NamedExpression, Variable},
- Name,
+ ast::{
+ Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Let, Literal, NamedExpression, Variable,
+ },
+ name::Name,
};
pub trait Visitor {
type Out;
- fn visit_epsilon(
- &mut self,
- name: Option<&Name>,
- span: Option<Span>,
- eps: &Epsilon,
- ) -> Self::Out;
+ fn visit_epsilon(&mut self, name: Option<&Name>, span: Span, eps: &Epsilon) -> Self::Out;
- fn visit_literal(
- &mut self,
- name: Option<&Name>,
- span: Option<Span>,
- lit: &Literal,
- ) -> Self::Out;
+ fn visit_literal(&mut self, name: Option<&Name>, span: Span, lit: &Literal) -> Self::Out;
- fn visit_cat(&mut self, name: Option<&Name>, span: Option<Span>, cat: &Cat) -> Self::Out;
+ fn visit_cat(&mut self, name: Option<&Name>, span: Span, cat: &Cat) -> Self::Out;
- fn visit_alt(&mut self, name: Option<&Name>, span: Option<Span>, alt: &Alt) -> Self::Out;
+ fn visit_alt(&mut self, name: Option<&Name>, span: Span, alt: &Alt) -> Self::Out;
- fn visit_fix(&mut self, name: Option<&Name>, span: Option<Span>, fix: &Fix) -> Self::Out;
+ fn visit_fix(&mut self, name: Option<&Name>, span: Span, fix: &Fix) -> Self::Out;
- fn visit_variable(
- &mut self,
- name: Option<&Name>,
- span: Option<Span>,
- var: &Variable,
- ) -> Self::Out;
+ fn visit_variable(&mut self, name: Option<&Name>, span: Span, var: &Variable) -> Self::Out;
- fn visit_call(&mut self, name: Option<&Name>, span: Option<Span>, call: &Call) -> Self::Out;
+ fn visit_call(&mut self, name: Option<&Name>, span: Span, call: &Call) -> Self::Out;
- fn visit_lambda(
- &mut self,
- name: Option<&Name>,
- span: Option<Span>,
- lambda: &Lambda,
- ) -> Self::Out;
+ fn visit_lambda(&mut self, name: Option<&Name>, span: Span, lambda: &Lambda) -> Self::Out;
+
+ fn visit_let(&mut self, name: Option<&Name>, span: Span, stmt: &Let) -> Self::Out;
}
pub trait Mapper {
type Out;
- fn map_epsilon(
- &mut self,
- name: &mut Option<Name>,
- span: Option<Span>,
- eps: &mut Epsilon,
- ) -> Self::Out;
+ fn map_epsilon(&mut self, name: &mut Option<Name>, span: 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_literal(&mut self, name: &mut Option<Name>, span: 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_cat(&mut self, name: &mut Option<Name>, span: 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_alt(&mut self, name: &mut Option<Name>, span: 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_fix(&mut self, name: &mut Option<Name>, span: Span, fix: &mut Fix) -> Self::Out;
fn map_variable(
&mut self,
name: &mut Option<Name>,
- span: Option<Span>,
+ span: Span,
var: &mut Variable,
) -> Self::Out;
- fn map_call(
- &mut self,
- name: &mut Option<Name>,
- span: Option<Span>,
- call: &mut Call,
- ) -> Self::Out;
+ fn map_call(&mut self, name: &mut Option<Name>, span: Span, call: &mut Call) -> Self::Out;
- fn map_lambda(
- &mut self,
- name: &mut Option<Name>,
- span: Option<Span>,
- lambda: &mut Lambda,
- ) -> Self::Out;
+ fn map_lambda(&mut self, name: &mut Option<Name>, span: Span, lambda: &mut Lambda)
+ -> Self::Out;
+
+ fn map_let(&mut self, name: &mut Option<Name>, span: Span, stmt: &mut Let) -> Self::Out;
}
pub trait Folder {
type Out;
- 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;
- 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;
- 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, cat: Cat) -> Self::Out;
- 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, alt: Alt) -> Self::Out;
- 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, fix: Fix) -> Self::Out;
- fn fold_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable)
- -> Self::Out;
+ fn fold_variable(&mut self, name: Option<Name>, span: Span, var: Variable) -> Self::Out;
+
+ fn fold_call(&mut self, name: Option<Name>, span: Span, call: Call) -> Self::Out;
- fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out;
+ fn fold_lambda(&mut self, name: Option<Name>, span: Span, lambda: Lambda) -> Self::Out;
- fn fold_lambda(&mut self, name: Option<Name>, span: Option<Span>, lambda: Lambda) -> Self::Out;
+ fn fold_let(&mut self, name: Option<Name>, span: Span, stmt: Let) -> Self::Out;
}
pub trait Visitable {
@@ -118,6 +86,20 @@ pub trait Visitable {
fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out;
}
+impl<T: Visitable> Visitable for Box<T> {
+ fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
+ self.as_ref().visit(visitor)
+ }
+
+ fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out {
+ self.as_mut().map(mapper)
+ }
+
+ fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out {
+ (*self).fold(folder)
+ }
+}
+
impl Visitable for NamedExpression {
fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
match &self.expr {
@@ -129,6 +111,7 @@ impl Visitable for NamedExpression {
Expression::Variable(v) => visitor.visit_variable(self.name.as_ref(), self.span, v),
Expression::Call(c) => visitor.visit_call(self.name.as_ref(), self.span, c),
Expression::Lambda(l) => visitor.visit_lambda(self.name.as_ref(), self.span, l),
+ Expression::Let(l) => visitor.visit_let(self.name.as_ref(), self.span, l),
}
}
@@ -142,6 +125,7 @@ impl Visitable for NamedExpression {
Expression::Variable(v) => mapper.map_variable(&mut self.name, self.span, v),
Expression::Call(c) => mapper.map_call(&mut self.name, self.span, c),
Expression::Lambda(l) => mapper.map_lambda(&mut self.name, self.span, l),
+ Expression::Let(l) => mapper.map_let(&mut self.name, self.span, l),
}
}
@@ -155,6 +139,7 @@ impl Visitable for NamedExpression {
Expression::Variable(v) => folder.fold_variable(self.name, self.span, v),
Expression::Call(c) => folder.fold_call(self.name, self.span, c),
Expression::Lambda(l) => folder.fold_lambda(self.name, self.span, l),
+ Expression::Let(l) => folder.fold_let(self.name, self.span, l),
}
}
}
diff --git a/src/lower/mod.rs b/src/lower/mod.rs
index dcd0f1f..e74f86a 100644
--- a/src/lower/mod.rs
+++ b/src/lower/mod.rs
@@ -8,10 +8,15 @@ use proc_macro2::{Ident, Span, TokenStream, TokenTree};
use quote::{format_ident, quote, quote_spanned};
use syn::{Index, LitStr};
-use crate::chomp::{Name, ast, set::FirstSet, typed::{
+use crate::chomp::{
+ ast,
+ name::Name,
+ set::FirstSet,
+ typed::{
lower::{Backend, GenerateCode},
Alt, Cat, Epsilon, Fix, Literal, Type, Typed, TypedExpression, Variable,
- }};
+ },
+};
#[derive(Clone, Debug)]
struct Ty {
@@ -44,7 +49,7 @@ impl RustBackend {
match name {
None => (id, format_ident!("{}{}", prefix, id + 1, span = span)),
Some(name) => {
- let name = name.to_camel_case().into_ident(span);
+ let name: Ident = name.to_camel_case().into();
let count = self.name_map.entry(name.clone()).or_insert(0);
*count += 1;
(id, format_ident!("{}{}", name, count))
@@ -60,10 +65,7 @@ impl RustBackend {
.into_iter()
.map(|e| {
(
- (
- e.get_type().clone(),
- (e.name.clone(), e.span.unwrap_or_else(Span::call_site)),
- ),
+ (e.get_type().clone(), (e.name.clone(), e.span)),
e.gen(self),
)
})
@@ -104,7 +106,7 @@ impl RustBackend {
.map(move |(index, (name, span))| match name {
None => format_ident!("{}{}", default, index + 1, span = span),
Some(name) => {
- let name = name.to_snake_case().into_ident(span);
+ let name: Ident = name.to_snake_case().into();
let count = name_map.entry(name.clone()).or_insert(0_usize);
*count += 1;
format_ident!("{}{}", name, count)
@@ -122,7 +124,7 @@ impl RustBackend {
.map(move |(index, (name, span))| match name {
None => format_ident!("{}{}", default, index + 1, span = span),
Some(name) => {
- let name = name.to_camel_case().into_ident(span);
+ let name: Ident = name.to_camel_case().into();
let count = name_map.entry(name.clone()).or_insert(0_usize);
*count += 1;
format_ident!("{}{}", name, count)
@@ -153,7 +155,7 @@ impl Backend for RustBackend {
type Code = TokenStream;
- fn gen_epsilon(&mut self, _name: Option<Name>, _span: Option<Span>, _eps: Epsilon) -> Self::Id {
+ fn gen_epsilon(&mut self, _name: Option<Name>, _span: Span, _eps: Epsilon) -> Self::Id {
if let Some(id) = self.eps_id {
return id;
}
@@ -167,9 +169,7 @@ impl Backend for RustBackend {
id
}
- fn gen_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Id {
- let span = span.unwrap_or_else(Span::call_site);
-
+ fn gen_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Id {
let lit: ast::Literal = lit.into();
if let Some(&id) = self.lit_map.get(&lit) {
return id;
@@ -218,8 +218,7 @@ impl Backend for RustBackend {
id
}
- fn gen_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Id {
- let span = span.unwrap_or_else(Span::call_site);
+ fn gen_cat(&mut self, name: Option<Name>, span: Span, cat: Cat) -> Self::Id {
let (_, name_spans, ids) = self.recurse_exprs(cat);
if let Some(&id) = self.cat_map.get(&ids) {
@@ -283,8 +282,7 @@ impl Backend for RustBackend {
id
}
- fn gen_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Id {
- let span = span.unwrap_or_else(Span::call_site);
+ fn gen_alt(&mut self, name: Option<Name>, span: Span, alt: Alt) -> Self::Id {
let (tys, name_spans, ids) = self.recurse_exprs(alt);
if let Some(&id) = self.alt_map.get(&ids) {
@@ -338,7 +336,7 @@ impl Backend for RustBackend {
fn take<P: Parser + ?Sized>(input: &mut P) -> Result<Self, TakeError> {
match input.peek() {
#(#firsts => Ok(Self::#first_alts(input.take()?)),)*
- _ => Ok(Self::#nullable(input.take()?))
+ _ => Ok(Self::#nullable(input.take()?)),
}
}
}
@@ -379,8 +377,7 @@ impl Backend for RustBackend {
id
}
- fn gen_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Id {
- let span = span.unwrap_or_else(Span::call_site);
+ fn gen_fix(&mut self, name: Option<Name>, span: Span, fix: Fix) -> Self::Id {
let inner = fix.unwrap();
if let Some(&id) = self.fix_map.get(&inner) {
@@ -401,29 +398,13 @@ impl Backend for RustBackend {
self.context.pop();
let inner_ty = self.data[inner].name.clone();
- let rest = quote_spanned! {span=>
- #[derive(Clone, Debug, Eq, Hash, PartialEq)]
- pub struct #name(pub #inner_ty);
-
- impl ::std::fmt::Display for #name {
- fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
- self.0.fmt(f)
- }
- }
-
- impl Parse for #name {
- fn take<P: Parser + ?Sized>(input: &mut P) -> Result<Self, TakeError> {
- input.take().map(Self)
- }
- }
- };
+ let rest = quote_spanned! {span=> pub type #name = #inner_ty;};
self.data[id].rest = rest;
self.data[id].deps = [inner].iter().cloned().collect();
id
}
- fn gen_variable(&mut self, _name: Option<Name>, span: Option<Span>, var: Variable) -> Self::Id {
- let span = span.unwrap_or_else(Span::call_site);
+ fn gen_variable(&mut self, _name: Option<Name>, span: Span, var: Variable) -> Self::Id {
let fix_id = self.context[self.context.len() - var.index() - 1];
if let Some(&id) = self.var_map.get(&fix_id) {
@@ -443,9 +424,7 @@ impl Backend for RustBackend {
id
}
- fn emit_code(self, name: Option<Name>, span: Option<Span>, id: Self::Id) -> Self::Code {
- let span = span.unwrap_or_else(Span::call_site);
-
+ fn emit_code(self, name: Option<Name>, span: Span, id: Self::Id) -> Self::Code {
let mut tokens = quote_spanned! {span=>
use ::chewed::*;
};
@@ -467,7 +446,7 @@ impl Backend for RustBackend {
let root_name = self.data[id].name.clone();
tokens.extend(if let Some(name) = name {
- let name = name.into_ident(span);
+ let name = name.into();
let count = self.name_map.get(&name).copied().unwrap_or_default() + 1;
let name = format_ident!("{}{}", name, count);
quote_spanned! {span=>
diff --git a/src/main.rs b/src/main.rs
index 0e7193e..0954074 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -6,7 +6,7 @@ use std::{
use chomp::{
chomp::{
- ast::substitute::InlineCalls,
+ ast::substitute::Reduce,
typed::{
context::Context,
lower::{Backend, GenerateCode},
@@ -15,8 +15,12 @@ use chomp::{
visit::Visitable,
},
lower::RustBackend,
- nibble::File,
+ nibble::{
+ convert::{self, Convert},
+ Statement,
+ },
};
+use proc_macro2::Span;
fn main() {
let mut input = String::new();
@@ -24,12 +28,13 @@ fn main() {
.read_to_string(&mut input)
.map_err(|e| Box::new(e) as Box<dyn Error>)
.and_then(|_| syn::parse_str(&input).map_err(|e| Box::new(e) as Box<dyn Error>))
- .and_then(|nibble: File| nibble.convert().map_err(|e| Box::new(e) as Box<dyn Error>))
- .and_then(|(funs, goal)| {
- funs.into_iter()
- .try_rfold(goal, |goal, function| {
- goal.fold(&mut InlineCalls { function })
- })
+ .and_then(|nibble: Statement| {
+ nibble
+ .convert(&mut convert::Context::default())
+ .map_err(|e| Box::new(e) as Box<dyn Error>)
+ })
+ .and_then(|expr| {
+ expr.fold(&mut Reduce)
.map_err(|e| Box::new(e) as Box<dyn Error>)
})
.and_then(|term| {
@@ -37,12 +42,12 @@ fn main() {
term.fold(&mut TypeInfer {
context: &mut context,
})
- .map_err(|e| Box::new(e) as Box<dyn Error>)
+ .map_err(|e| Box::new(e) as Box<dyn Error>)
})
.map(|typed| {
let mut backend = RustBackend::default();
let id = typed.gen(&mut backend);
- backend.emit_code(None, None, id)
+ backend.emit_code(None, Span::call_site(), id)
})
.and_then(|code| {
write!(io::stdout(), "{:#}", code).map_err(|e| Box::new(e) as Box<dyn Error>)
diff --git a/src/nibble/convert.rs b/src/nibble/convert.rs
index e5e8c5d..ca6c95a 100644
--- a/src/nibble/convert.rs
+++ b/src/nibble/convert.rs
@@ -1,18 +1,18 @@
use std::{fmt, mem};
use proc_macro2::Span;
-use syn::{punctuated::Pair, Token};
+use syn::{punctuated::Pair, spanned::Spanned, Token};
-use crate::chomp::{
- ast::{self, NamedExpression},
- Name,
-};
+use crate::chomp::{ast::{self, NamedExpression}, name::{Content, Name}};
-use super::{Alt, Call, Cat, Expression, Fix, Ident, Labelled, Lambda, ParenExpression, Term};
+use super::{
+ Alt, Call, Cat, Expression, Fix, GoalStatement, Ident, Labelled, Lambda, LetStatement,
+ ParenExpression, Statement, Term,
+};
#[derive(Debug, Default)]
pub struct Context {
- bindings: Vec<Name>,
+ bindings: Vec<Content>,
}
impl Context {
@@ -20,20 +20,24 @@ impl Context {
Self::default()
}
+ /// Get the De Bruijn index of `name`, if it is defined.
pub fn lookup(&self, name: &Name) -> Option<usize> {
self.bindings
.iter()
+ .rev()
.enumerate()
- .rfind(|(_, n)| *n == name)
+ .find(|(_, n)| *n == &name.content)
.map(|(idx, _)| idx)
}
+ /// Permanently add the variable `name` to the top of the stack.
pub fn push_variable(&mut self, name: Name) {
- self.bindings.push(name);
+ self.bindings.push(name.content);
}
+ /// Call `f` with the variable `name` pushed to the top of the stack.
pub fn with_variable<F: FnOnce(&mut Self) -> R, R>(&mut self, name: Name, f: F) -> R {
- self.bindings.push(name);
+ self.bindings.push(name.content);
let res = f(self);
self.bindings.pop();
res
@@ -45,7 +49,7 @@ impl Context {
f: F,
) -> R {
let len = self.bindings.len();
- self.bindings.extend(names);
+ self.bindings.extend(names.into_iter().map(|n| n.content));
let res = f(self);
self.bindings.resize_with(len, || unreachable!());
res
@@ -55,10 +59,9 @@ impl Context {
#[derive(Clone, Debug)]
pub enum ConvertError {
UndeclaredName(Box<Name>),
- EmptyCat(Option<Span>),
- EmptyAlt(Option<Span>),
- EmptyCall(Option<Span>),
- MissingArgs(Option<Span>),
+ EmptyCat(Span),
+ EmptyAlt(Span),
+ EmptyCall(Span),
}
impl From<ConvertError> for syn::Error {
@@ -68,11 +71,10 @@ impl From<ConvertError> for syn::Error {
ConvertError::UndeclaredName(name) => name.span(),
ConvertError::EmptyCat(span)
| ConvertError::EmptyAlt(span)
- | ConvertError::EmptyCall(span)
- | ConvertError::MissingArgs(span) => span,
+ | ConvertError::EmptyCall(span) => span,
};
- Self::new(span.unwrap_or_else(Span::call_site), msg)
+ Self::new(span, msg)
}
}
@@ -91,9 +93,6 @@ impl fmt::Display for ConvertError {
Self::EmptyCall(_) => {
write!(f, "call has no function")
}
- Self::MissingArgs(_) => {
- write!(f, "call has no arguments")
- }
}
}
}
@@ -106,8 +105,8 @@ pub trait Convert {
impl Convert for Ident {
fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
- let span = Some(self.span());
- let name = self.into();
+ let span = self.span();
+ let name = Name::new_variable(self);
let index = context
.lookup(&name)
@@ -148,13 +147,13 @@ impl Convert for Term {
Self::Epsilon(e) => Ok(NamedExpression {
name: None,
expr: ast::Epsilon.into(),
- span: Some(e.span),
+ span: e.span,
}),
Self::Ident(i) => i.convert(context),
Self::Literal(l) => Ok(NamedExpression {
name: None,
expr: l.value().into(),
- span: Some(l.span()),
+ span: l.span(),
}),
Self::Fix(f) => f.convert(context),
Self::Parens(p) => p.convert(context),
@@ -168,13 +167,13 @@ impl Convert for Call {
let mut iter = self.0.into_iter();
let on = iter
.next()
- .ok_or_else(|| ConvertError::EmptyCall(span))?
+ .ok_or(ConvertError::EmptyCall(span))?
.convert(context)?;
let args = iter
.map(|arg| arg.convert(context))
.collect::<Result<Vec<_>, _>>()?;
if args.is_empty() {
- Err(ConvertError::MissingArgs(span))
+ Ok(on)
} else {
Ok(NamedExpression {
name: None,
@@ -194,10 +193,10 @@ impl Convert for Cat {
fn convert_pair(
pair: Pair<Call, Token![.]>,
context: &mut Context,
- ) -> Result<(NamedExpression, Option<Span>), ConvertError> {
+ ) -> Result<(NamedExpression, Span), ConvertError> {
match pair {
- Pair::Punctuated(t, p) => t.convert(context).map(|expr| (expr, Some(p.span))),
- Pair::End(t) => t.convert(context).map(|expr| (expr, None)),
+ Pair::Punctuated(t, p) => t.convert(context).map(|expr| (expr, p.span)),
+ Pair::End(t) => t.convert(context).map(|expr| (expr, Span::call_site())),
}
}
@@ -215,7 +214,7 @@ impl Convert for Cat {
})
.peekable();
- if let Some(_) = rest.peek() {
+ if rest.peek().is_some() {
Ok(NamedExpression {
name: None,
expr: ast::Cat {
@@ -235,7 +234,8 @@ impl Convert for Labelled {
fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
let span = self.span();
let named = self.cat.convert(context)?;
- let name = self.label.map(|l| l.label.into()).or(named.name);
+ let label = self.label.map(|l| Name::new_label(l.label));
+ let name = Name::merge(label, named.name);
Ok(NamedExpression {
name,
@@ -250,10 +250,10 @@ impl Convert for Alt {
fn convert_pair(
pair: Pair<Labelled, Token![|]>,
context: &mut Context,
- ) -> Result<(NamedExpression, Option<Span>), ConvertError> {
+ ) -> Result<(NamedExpression, Span), ConvertError> {
match pair {
- Pair::Punctuated(t, p) => t.convert(context).map(|expr| (expr, Some(p.span))),
- Pair::End(t) => t.convert(context).map(|expr| (expr, None)),
+ Pair::Punctuated(t, p) => t.convert(context).map(|expr| (expr, p.span)),
+ Pair::End(t) => t.convert(context).map(|expr| (expr, Span::call_site())),
}
}
@@ -271,7 +271,7 @@ impl Convert for Alt {
})
.peekable();
- if let Some(_) = rest.peek() {
+ if rest.peek().is_some() {
Ok(NamedExpression {
name: None,
expr: ast::Alt {
@@ -290,7 +290,7 @@ impl Convert for Alt {
impl Convert for Lambda {
fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
let span = self.span();
- let mut args: Vec<_> = self.args.into_iter().map(Name::from).collect();
+ let args: Vec<_> = self.args.into_iter().map(Name::new_variable).collect();
let expr = self.expr;
let inner = context.with_variables(args.clone(), |ctx| expr.convert(ctx))?;
Ok(NamedExpression {
@@ -313,3 +313,62 @@ impl Convert for Expression {
}
}
}
+
+impl Convert for GoalStatement {
+ fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
+ let span = self.span();
+ let inner = self.expr.convert(context)?;
+ Ok(NamedExpression {
+ name: Name::merge(inner.name, Some(Name::new_variable("Ast".to_owned()))),
+ expr: inner.expr,
+ span,
+ })
+ }
+}
+
+impl Convert for LetStatement {
+ fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
+ let span = self.span();
+ let bound = if self.args.is_empty() {
+ self.expr.convert(context)?
+ } else {
+ let args: Vec<_> = self.args.into_iter().map(Name::new_variable).collect();
+ let expr = self.expr;
+ let inner = context.with_variables(args.clone(), |ctx| expr.convert(ctx))?;
+ NamedExpression {
+ name: None,
+ expr: ast::Lambda {
+ args,
+ inner: Box::new(inner),
+ }
+ .into(),
+ span,
+ }
+ };
+ let name = Name::new_let(self.name);
+ context.push_variable(name.clone());
+ let body = self.next.convert(context)?;
+ Ok(NamedExpression {
+ name: None,
+ expr: ast::Let {
+ name: name.clone(),
+ bound: Box::new(NamedExpression {
+ name: Some(name),
+ ..bound
+ }),
+ body: Box::new(body),
+ }
+ .into(),
+ span,
+ })
+ }
+}
+
+impl Convert for Statement {
+ fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
+ match self {
+ Self::Goal(g) => g.convert(context),
+ Self::Let(l) => l.convert(context),
+ }
+ }
+}
diff --git a/src/nibble/mod.rs b/src/nibble/mod.rs
index dbb05b0..f5417db 100644
--- a/src/nibble/mod.rs
+++ b/src/nibble/mod.rs
@@ -2,21 +2,17 @@ pub mod convert;
use std::fmt;
-use proc_macro2::Span;
+use proc_macro2::TokenStream;
+use quote::{ToTokens, TokenStreamExt};
use syn::{
- bracketed,
ext::IdentExt,
parenthesized,
parse::{Parse, ParseStream},
- punctuated::{Pair, Punctuated},
- token::{Bracket, Comma, Let, Match, Paren},
+ punctuated::Punctuated,
+ token::{Let, Match, Paren},
LitStr, Token,
};
-use crate::chomp::{Name, ast::{self, TopLevel}};
-
-use convert::{Context, Convert, ConvertError};
-
pub type Epsilon = Token![_];
pub type Ident = syn::Ident;
@@ -24,60 +20,15 @@ pub type Ident = syn::Ident;
pub type Literal = LitStr;
#[derive(Clone)]
-pub struct ArgList<T> {
- paren_token: Paren,
- args: Punctuated<T, Comma>,
-}
-
-impl<T> ArgList<T> {
- pub fn span(&self) -> Span {
- self.paren_token.span
- }
-
- pub fn len(&self) -> usize {
- self.args.len()
- }
-
- pub fn is_empty(&self) -> bool {
- self.args.is_empty()
- }
-}
-
-impl<T> IntoIterator for ArgList<T> {
- type Item = T;
-
- type IntoIter = <Punctuated<T, Comma> as IntoIterator>::IntoIter;
-
- fn into_iter(self) -> Self::IntoIter {
- self.args.into_iter()
- }
-}
-
-impl<T: Parse> Parse for ArgList<T> {
- fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
- let args;
- let paren_token = parenthesized!(args in input);
- let args = args.call(Punctuated::parse_terminated)?;
- Ok(Self { paren_token, args })
- }
-}
-
-impl<T: fmt::Debug> fmt::Debug for ArgList<T> {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- write!(f, "ArgList")?;
- f.debug_list().entries(self.args.iter()).finish()
- }
-}
-
-#[derive(Clone)]
pub struct Fix {
bang_token: Token![!],
pub expr: Box<Term>,
}
-impl Fix {
- pub fn span(&self) -> Option<Span> {
- self.bang_token.span.join(self.expr.span()?)
+impl ToTokens for Fix {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.bang_token.to_tokens(tokens);
+ self.expr.to_tokens(tokens);
}
}
@@ -101,6 +52,12 @@ pub struct ParenExpression {
pub expr: Expression,
}
+impl ToTokens for ParenExpression {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.paren_token.surround(tokens, |tokens| self.expr.to_tokens(tokens))
+ }
+}
+
impl Parse for ParenExpression {
fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
let expr;
@@ -127,14 +84,14 @@ pub enum Term {
Parens(ParenExpression),
}
-impl Term {
- pub fn span(&self) -> Option<Span> {
+impl ToTokens for Term {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
match self {
- Self::Epsilon(e) => Some(e.span),
- Self::Ident(i) => Some(i.span()),
- Self::Literal(l) => Some(l.span()),
- Self::Fix(f) => f.span(),
- Self::Parens(p) => Some(p.paren_token.span),
+ Self::Epsilon(e) => e.to_tokens(tokens),
+ Self::Ident(i) => i.to_tokens(tokens),
+ Self::Literal(l) => l.to_tokens(tokens),
+ Self::Fix(f) => f.to_tokens(tokens),
+ Self::Parens(p) => p.to_tokens(tokens),
}
}
}
@@ -174,18 +131,15 @@ impl fmt::Debug for Term {
#[derive(Clone, Debug)]
pub struct Call(pub Vec<Term>);
-impl Call {
- pub fn span(&self) -> Option<Span> {
- let mut iter = self.0.iter();
- let first = iter.next()?.span()?;
- iter.try_fold(first, |span, t| t.span().and_then(|s| span.join(s)))
+impl ToTokens for Call {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ tokens.append_all(&self.0)
}
}
impl Parse for Call {
fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
- let mut out = Vec::new();
- out.push(input.parse()?);
+ let mut out = vec![input.parse()?];
loop {
let lookahead = input.lookahead1();
if lookahead.peek(Token![_])
@@ -207,34 +161,22 @@ impl Parse for Call {
#[derive(Clone)]
pub struct Cat(pub Punctuated<Call, Token![.]>);
-impl Parse for Cat {
- fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
- input.call(Punctuated::parse_separated_nonempty).map(Self)
+impl ToTokens for Cat {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.0.to_tokens(tokens)
}
}
-impl Cat {
- pub fn span(&self) -> Option<Span> {
- let mut iter = self.0.pairs();
- let span = match iter.next()? {
- Pair::Punctuated(t, p) => t.span().and_then(|s| s.join(p.span)),
- Pair::End(t) => t.span(),
- }?;
-
- iter.try_fold(span, |span, pair| match pair {
- Pair::Punctuated(t, p) => t
- .span()
- .and_then(|s| span.join(s))
- .and_then(|s| s.join(p.span)),
- Pair::End(t) => t.span().and_then(|s| span.join(s)),
- })
+impl Parse for Cat {
+ fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
+ input.call(Punctuated::parse_separated_nonempty).map(Self)
}
}
impl fmt::Debug for Cat {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "Cat")?;
- f.debug_list().entries(self.0.iter()).finish()
+ f.debug_list().entries(&self.0).finish()
}
}
@@ -244,9 +186,10 @@ pub struct Label {
pub label: Ident,
}
-impl Label {
- pub fn span(&self) -> Option<Span> {
- self.colon_tok.span.join(self.label.span())
+impl ToTokens for Label {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.colon_tok.to_tokens(tokens);
+ self.label.to_tokens(tokens);
}
}
@@ -270,13 +213,12 @@ pub struct Labelled {
pub label: Option<Label>,
}
-impl Labelled {
- pub fn span(&self) -> Option<Span> {
- self.cat.span().and_then(|s| {
- self.label
- .as_ref()
- .and_then(|l| l.span().and_then(|t| s.join(t)))
- })
+impl ToTokens for Labelled {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.cat.to_tokens(tokens);
+ if let Some(label) = &self.label {
+ label.to_tokens(tokens);
+ }
}
}
@@ -295,21 +237,9 @@ impl Parse for Labelled {
#[derive(Clone)]
pub struct Alt(pub Punctuated<Labelled, Token![|]>);
-impl Alt {
- pub fn span(&self) -> Option<Span> {
- let mut iter = self.0.pairs();
- let span = match iter.next()? {
- Pair::Punctuated(t, p) => t.span().and_then(|s| s.join(p.span)),
- Pair::End(t) => t.span(),
- }?;
-
- iter.try_fold(span, |span, pair| match pair {
- Pair::Punctuated(t, p) => t
- .span()
- .and_then(|s| span.join(s))
- .and_then(|s| s.join(p.span)),
- Pair::End(t) => t.span().and_then(|s| span.join(s)),
- })
+impl ToTokens for Alt {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.0.to_tokens(tokens)
}
}
@@ -322,27 +252,40 @@ impl Parse for Alt {
impl fmt::Debug for Alt {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "Alt")?;
- f.debug_list().entries(self.0.iter()).finish()
+ f.debug_list().entries(&self.0).finish()
}
}
#[derive(Clone)]
pub struct Lambda {
slash_tok_left: Token![/],
- pub args: ArgList<Ident>,
+ pub args: Vec<Ident>,
slash_tok_right: Token![/],
pub expr: Alt,
}
-impl Lambda {
- pub fn span(&self) -> Option<Span> {
- self.slash_tok_left.span.join(self.expr.span()?)
+impl ToTokens for Lambda {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.slash_tok_left.to_tokens(tokens);
+ tokens.append_all(&self.args);
+ self.slash_tok_right.to_tokens(tokens);
+ self.expr.to_tokens(tokens);
}
}
impl Parse for Lambda {
fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
let slash_tok_left = input.parse()?;
- let args = input.parse()?;
+ let mut args = Vec::new();
+ loop {
+ args.push(input.parse()?);
+ let lookahead = input.lookahead1();
+
+ if lookahead.peek(Token![/]) {
+ break;
+ } else if !lookahead.peek(Ident::peek_any) {
+ return Err(lookahead.error());
+ }
+ }
let slash_tok_right = input.parse()?;
let expr = input.parse()?;
Ok(Self {
@@ -369,6 +312,15 @@ pub enum Expression {
Lambda(Lambda),
}
+impl ToTokens for Expression {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ match self {
+ Self::Alt(a) => a.to_tokens(tokens),
+ Self::Lambda(l) => l.to_tokens(tokens),
+ }
+ }
+}
+
impl Parse for Expression {
fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
if input.peek(Token![/]) {
@@ -386,6 +338,14 @@ pub struct GoalStatement {
semi_token: Token![;],
}
+impl ToTokens for GoalStatement {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.match_token.to_tokens(tokens);
+ self.expr.to_tokens(tokens);
+ self.semi_token.to_tokens(tokens);
+ }
+}
+
impl Parse for GoalStatement {
fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
let match_token = input.parse()?;
@@ -412,22 +372,40 @@ impl fmt::Debug for GoalStatement {
pub struct LetStatement {
let_token: Token![let],
name: Ident,
- args: Option<ArgList<Ident>>,
+ args: Vec<Ident>,
eq_token: Token![=],
expr: Expression,
semi_token: Token![;],
next: Box<Statement>,
}
+impl ToTokens for LetStatement {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ self.let_token.to_tokens(tokens);
+ self.name.to_tokens(tokens);
+ tokens.append_all(&self.args);
+ self.eq_token.to_tokens(tokens);
+ self.expr.to_tokens(tokens);
+ self.semi_token.to_tokens(tokens);
+ self.next.to_tokens(tokens);
+ }
+}
+
impl Parse for LetStatement {
fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
let let_token = input.parse()?;
let name = input.call(Ident::parse_any)?;
- let args = if input.peek(Paren) {
- Some(input.parse()?)
- } else {
- None
- };
+ let mut args = Vec::new();
+ loop {
+ let lookahead = input.lookahead1();
+ if lookahead.peek(Token![=]) {
+ break;
+ } else if lookahead.peek(Ident::peek_any) {
+ args.push(input.parse()?);
+ } else {
+ return Err(lookahead.error());
+ }
+ }
let eq_token = input.parse()?;
let expr = input.parse()?;
let semi_token = input.parse()?;
@@ -462,43 +440,18 @@ pub enum Statement {
Let(LetStatement),
}
-impl Statement {
- pub fn convert(self) -> Result<TopLevel, ConvertError> {
- let mut stmt = self;
- let mut context = Context::new();
- let mut name_val = Vec::new();
- while let Self::Let(let_stmt) = stmt {
- let mut val = match let_stmt.args {
- Some(args) => {
- todo!()
- }
- None => let_stmt.expr.convert(&mut context),
- }?;
- let name: Name = let_stmt.name.into();
- val.name = val.name.or_else(|| Some(name.clone()));
- context.push_variable(name.clone());
- name_val.push((name, val));
- stmt = *let_stmt.next;
+impl ToTokens for Statement {
+ fn to_tokens(&self, tokens: &mut TokenStream) {
+ match self {
+ Self::Goal(g) => g.to_tokens(tokens),
+ Self::Let(l) => l.to_tokens(tokens),
}
-
- let goal = match stmt {
- Statement::Goal(goal) => TopLevel::Goal(goal.expr.convert(&mut context)?),
- Statement::Let(_) => unreachable!(),
- };
-
- Ok(name_val.into_iter().rfold(goal, |inner, (name, val)| {
- TopLevel::Let(ast::Let {
- name,
- val,
- inner: Box::new(inner),
- })
- }))
}
}
impl Parse for Statement {
fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
- let mut lookahead = input.lookahead1();
+ let lookahead = input.lookahead1();
if lookahead.peek(Let) {
input.parse().map(Self::Let)
generated by cgit v1.2.3 (git 2.49.0) at 2025-04-30 13:22:54 +0000