From dfc08ff2c6580bbeb3951b223e0332546ba3b0d9 Mon Sep 17 00:00:00 2001 From: Greg Brown Date: Thu, 6 May 2021 19:40:59 +0100 Subject: Introduce lambda expressions. --- src/chomp/ast/error.rs | 22 ++--- src/chomp/ast/mod.rs | 115 +++++++--------------- src/chomp/ast/substitute.rs | 229 ++++++++++++++++++++++++++++---------------- src/chomp/mod.rs | 111 +-------------------- src/chomp/name.rs | 217 +++++++++++++++++++++++++++++++++++++++++ src/chomp/set.rs | 27 ++---- src/chomp/typed/context.rs | 15 +-- src/chomp/typed/error.rs | 93 ++++++++++-------- src/chomp/typed/infer.rs | 213 +++++++++++++++++++++++++++++++++------- src/chomp/typed/lower.rs | 16 ++-- src/chomp/typed/mod.rs | 140 +++++++-------------------- src/chomp/visit.rs | 119 ++++++++++------------- 12 files changed, 755 insertions(+), 562 deletions(-) create mode 100644 src/chomp/name.rs (limited to 'src/chomp') 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, }, WrongArgCount { lambda: Lambda, args: Vec, - span: Option, + span: Span, }, } -impl From for syn::Error { - fn from(e: TranslateError) -> Self { +impl From 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, - pub rest: Vec<(Option, 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, - pub rest: Vec<(Option, 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, + pub body: Box, +} + +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 for Expression { fn from(eps: Epsilon) -> Self { Self::Epsilon(eps) @@ -287,17 +245,29 @@ impl From for Expression { } } +impl From for Expression { + fn from(stmt: Let) -> Self { + Self::Let(stmt) + } +} + #[derive(Clone, Debug)] pub struct NamedExpression { pub name: Option, + pub span: Span, pub expr: Expression, - pub span: Option, } 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, -} - -#[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, - _span: Option, + _span: Span, _eps: &mut Epsilon, ) -> Self::Out { } @@ -26,7 +34,7 @@ impl Mapper for Deepen { fn map_literal( &mut self, _name: &mut Option, - _span: Option, + _span: Span, _lit: &mut Literal, ) -> Self::Out { } @@ -34,7 +42,7 @@ impl Mapper for Deepen { fn map_cat( &mut self, _name: &mut Option, - _span: Option, + _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, - _span: Option, + _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, - _span: Option, + _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, - _span: Option, + _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, - _span: Option, + _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, - _span: Option, + _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, + _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(&mut self, args: usize, visitable: V) -> ::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, span: Option, eps: Epsilon) -> Self::Out { + fn fold_epsilon(&mut self, name: Option, 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, span: Option, lit: Literal) -> Self::Out { + fn fold_literal(&mut self, name: Option, 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, span: Option, mut cat: Cat) -> Self::Out { + fn fold_cat(&mut self, name: Option, 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, span: Option, mut alt: Alt) -> Self::Out { + fn fold_alt(&mut self, name: Option, 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, span: Option, mut fix: Fix) -> Self::Out { + fn fold_fix(&mut self, name: Option, 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, - span: Option, + 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, span: Option, mut call: Call) -> Self::Out { + fn fold_call(&mut self, name: Option, 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, - span: Option, + 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, 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; +impl Folder for Reduce { + type Out = Result; - fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { + fn fold_epsilon(&mut self, name: Option, 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, span: Option, lit: Literal) -> Self::Out { + fn fold_literal(&mut self, name: Option, 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, span: Option, cat: Cat) -> Self::Out { + fn fold_cat(&mut self, name: Option, 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::>()?; Ok(NamedExpression { name, expr: cat.into(), @@ -254,7 +301,13 @@ impl Folder for Translate { }) } - fn fold_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Out { + fn fold_alt(&mut self, name: Option, 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::>()?; Ok(NamedExpression { name, expr: alt.into(), @@ -262,7 +315,13 @@ impl Folder for Translate { }) } - fn fold_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Out { + fn fold_fix(&mut self, name: Option, 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, - span: Option, + span: Span, var: Variable, ) -> Self::Out { Ok(NamedExpression { @@ -283,21 +342,16 @@ impl Folder for Translate { }) } - fn fold_call(&mut self, name: Option, span: Option, 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, 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, span: Option, lambda: Lambda) -> Self::Out { + fn fold_lambda(&mut self, name: Option, span: Span, lambda: Lambda) -> Self::Out { Ok(NamedExpression { name, expr: lambda.into(), span, }) } + + fn fold_let(&mut self, name: Option, 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 { - 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> PartialEq 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(&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 for Name { - fn from(ident: Ident) -> Self { - Self::Spanned(ident) - } -} - -impl From 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 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> PartialEq 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(&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 for Content { + fn from(ident: Ident) -> Self { + Self::Spanned(ident) + } +} + +impl From 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 { + 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>(content: T) -> Self { + Self { + content: content.into(), + kind: Kind::Variable, + } + } + + pub fn new_let>(content: T) -> Self { + Self { + content: content.into(), + kind: Kind::Let, + } + } + + pub fn new_label>(content: T) -> Self { + Self { + content: content.into(), + kind: Kind::Label, + } + } + + pub fn merge(this: Option, that: Option) -> Option { + 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>>(iter: I) -> Option { + iter.into_iter().fold(None, Self::merge) + } +} + +impl Spanned for Name { + fn span(&self) -> Span { + self.content.span() + } +} + +impl From 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, + pub span: Span, pub name: Option, } -impl From 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, + punct: Span, }, FirstFlastOverlap { - first: Vec, - punct: Option, + front_ty: Type, + punct: Span, next: TypedExpression, }, } -impl From 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, - punct: Option, + left_ty: Type, + punct: Span, right: TypedExpression, }, FirstOverlap { - left: Vec, - punct: Option, + left_ty: Type, + punct: Span, right: TypedExpression, }, } -impl From 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 for TypeError { @@ -143,11 +147,9 @@ impl From for TypeError { impl From 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; - fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { + fn fold_epsilon(&mut self, name: Option, 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, span: Option, lit: Literal) -> Self::Out { + fn fold_literal(&mut self, name: Option, 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, span: Option, cat: Cat) -> Self::Out { + fn fold_cat(&mut self, name: Option, 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 { - let mut infer = TypeInfer { context }; - let rest = rest - .into_iter() - .map(|(punct, term)| -> Result<_, TypeError> { - Ok((punct, term.fold(&mut infer)?)) - }) - .collect::, _>>()?; - 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::, TypeError>>() + })?; + Ok(TypedExpression { + inner: super::Cat { + terms: iter::once(first).chain(terms).collect(), + ty, + } + .into(), + name, + span, + }) } - fn fold_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Out { + fn fold_alt(&mut self, name: Option, 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::, _>>()?; + .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::, 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, span: Option, fix: Fix) -> Self::Out { + fn fold_fix(&mut self, name: Option, 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, - span: Option, + 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, span: Option, 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, span: Span, call: Call) -> Self::Out { + Err(TypeError::UnexpectedCall { span, call }) } fn fold_lambda( &mut self, _name: Option, - _span: Option, - _lambda: Lambda, + span: Span, + lambda: Lambda, ) -> Self::Out { - unimplemented!() + Err(TypeError::UnexpectedLambda { span, lambda }) + } + + fn fold_let(&mut self, _name: Option, 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, span: Option, eps: Epsilon) -> Self::Id; + fn gen_epsilon(&mut self, name: Option, span: Span, eps: Epsilon) -> Self::Id; - fn gen_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Id; + fn gen_literal(&mut self, name: Option, span: Span, lit: Literal) -> Self::Id; - fn gen_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Id; + fn gen_cat(&mut self, name: Option, span: Span, cat: Cat) -> Self::Id; - fn gen_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Id; + fn gen_alt(&mut self, name: Option, span: Span, alt: Alt) -> Self::Id; - fn gen_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Id; + fn gen_fix(&mut self, name: Option, span: Span, fix: Fix) -> Self::Id; - fn gen_variable(&mut self, name: Option, span: Option, var: Variable) -> Self::Id; + fn gen_variable(&mut self, name: Option, span: Span, var: Variable) -> Self::Id; - fn emit_code(self, name: Option, span: Option, id: Self::Id) -> Self::Code; + fn emit_code(self, name: Option, 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, TypedExpression)>>( - first: TypedExpression, - rest: I, - ) -> Result { - 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, TypedExpression)>>( - first: TypedExpression, - rest: I, - ) -> Result { - 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; @@ -244,14 +167,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), @@ -260,8 +175,6 @@ enum RawTypedExpression { Alt(Alt), Fix(Fix), Variable(Variable), - Call(Call), - Lambda(Lambda), } impl From for RawTypedExpression { @@ -304,7 +217,7 @@ impl From for RawTypedExpression { pub struct TypedExpression { inner: RawTypedExpression, pub name: Option, - pub span: Option, + 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, - 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, - 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, 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, 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, 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, - 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, 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, - 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, - span: Option, - eps: &mut Epsilon, - ) -> Self::Out; + fn map_epsilon(&mut self, name: &mut Option, span: Span, eps: &mut Epsilon) -> Self::Out; - fn map_literal( - &mut self, - name: &mut Option, - span: Option, - lit: &mut Literal, - ) -> Self::Out; + fn map_literal(&mut self, name: &mut Option, span: Span, lit: &mut Literal) -> Self::Out; - fn map_cat(&mut self, name: &mut Option, span: Option, cat: &mut Cat) -> Self::Out; + fn map_cat(&mut self, name: &mut Option, span: Span, cat: &mut Cat) -> Self::Out; - fn map_alt(&mut self, name: &mut Option, span: Option, alt: &mut Alt) -> Self::Out; + fn map_alt(&mut self, name: &mut Option, span: Span, alt: &mut Alt) -> Self::Out; - fn map_fix(&mut self, name: &mut Option, span: Option, fix: &mut Fix) -> Self::Out; + fn map_fix(&mut self, name: &mut Option, span: Span, fix: &mut Fix) -> Self::Out; fn map_variable( &mut self, name: &mut Option, - span: Option, + span: Span, var: &mut Variable, ) -> Self::Out; - fn map_call( - &mut self, - name: &mut Option, - span: Option, - call: &mut Call, - ) -> Self::Out; + fn map_call(&mut self, name: &mut Option, span: Span, call: &mut Call) -> Self::Out; - fn map_lambda( - &mut self, - name: &mut Option, - span: Option, - lambda: &mut Lambda, - ) -> Self::Out; + fn map_lambda(&mut self, name: &mut Option, span: Span, lambda: &mut Lambda) + -> Self::Out; + + fn map_let(&mut self, name: &mut Option, span: Span, stmt: &mut Let) -> Self::Out; } pub trait Folder { type Out; - fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out; + fn fold_epsilon(&mut self, name: Option, span: Span, eps: Epsilon) -> Self::Out; - fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out; + fn fold_literal(&mut self, name: Option, span: Span, lit: Literal) -> Self::Out; - fn fold_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Out; + fn fold_cat(&mut self, name: Option, span: Span, cat: Cat) -> Self::Out; - fn fold_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Out; + fn fold_alt(&mut self, name: Option, span: Span, alt: Alt) -> Self::Out; - fn fold_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Out; + fn fold_fix(&mut self, name: Option, span: Span, fix: Fix) -> Self::Out; - fn fold_variable(&mut self, name: Option, span: Option, var: Variable) - -> Self::Out; + fn fold_variable(&mut self, name: Option, span: Span, var: Variable) -> Self::Out; + + fn fold_call(&mut self, name: Option, span: Span, call: Call) -> Self::Out; - fn fold_call(&mut self, name: Option, span: Option, call: Call) -> Self::Out; + fn fold_lambda(&mut self, name: Option, span: Span, lambda: Lambda) -> Self::Out; - fn fold_lambda(&mut self, name: Option, span: Option, lambda: Lambda) -> Self::Out; + fn fold_let(&mut self, name: Option, span: Span, stmt: Let) -> Self::Out; } pub trait Visitable { @@ -118,6 +86,20 @@ pub trait Visitable { fn fold(self, folder: &mut F) -> ::Out; } +impl Visitable for Box { + fn visit(&self, visitor: &mut V) -> ::Out { + self.as_ref().visit(visitor) + } + + fn map(&mut self, mapper: &mut M) -> ::Out { + self.as_mut().map(mapper) + } + + fn fold(self, folder: &mut F) -> ::Out { + (*self).fold(folder) + } +} + impl Visitable for NamedExpression { fn visit(&self, visitor: &mut V) -> ::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), } } } -- cgit v1.2.3