From 51dcf19eb6f8d2127f3dedfc1d7d5326d7a8017b Mon Sep 17 00:00:00 2001 From: Greg Brown Date: Tue, 27 Apr 2021 13:07:27 +0100 Subject: Start rewrite using query system. --- src/chomp/ast-old/error.rs | 52 +++++ src/chomp/ast-old/mod.rs | 325 +++++++++++++++++++++++++++++++ src/chomp/ast-old/substitute.rs | 412 ++++++++++++++++++++++++++++++++++++++++ src/chomp/ast.rs | 146 ++++++++++++++ src/chomp/ast/error.rs | 52 ----- src/chomp/ast/mod.rs | 325 ------------------------------- src/chomp/ast/substitute.rs | 412 ---------------------------------------- src/chomp/cst.rs | 65 +++++++ src/chomp/intern.rs | 151 +++++++++++++++ src/chomp/mod.rs | 188 +++++++++--------- src/chomp/typed-old/context.rs | 58 ++++++ src/chomp/typed-old/error.rs | 164 ++++++++++++++++ src/chomp/typed-old/infer.rs | 127 +++++++++++++ src/chomp/typed-old/lower.rs | 41 ++++ src/chomp/typed-old/mod.rs | 362 +++++++++++++++++++++++++++++++++++ src/chomp/typed.rs | 274 ++++++++++++++++++++++++++ src/chomp/typed/context.rs | 58 ------ src/chomp/typed/error.rs | 164 ---------------- src/chomp/typed/infer.rs | 127 ------------- src/chomp/typed/lower.rs | 41 ---- src/chomp/typed/mod.rs | 362 ----------------------------------- 21 files changed, 2278 insertions(+), 1628 deletions(-) create mode 100644 src/chomp/ast-old/error.rs create mode 100644 src/chomp/ast-old/mod.rs create mode 100644 src/chomp/ast-old/substitute.rs create mode 100644 src/chomp/ast.rs delete mode 100644 src/chomp/ast/error.rs delete mode 100644 src/chomp/ast/mod.rs delete mode 100644 src/chomp/ast/substitute.rs create mode 100644 src/chomp/cst.rs create mode 100644 src/chomp/intern.rs create mode 100644 src/chomp/typed-old/context.rs create mode 100644 src/chomp/typed-old/error.rs create mode 100644 src/chomp/typed-old/infer.rs create mode 100644 src/chomp/typed-old/lower.rs create mode 100644 src/chomp/typed-old/mod.rs create mode 100644 src/chomp/typed.rs delete mode 100644 src/chomp/typed/context.rs delete mode 100644 src/chomp/typed/error.rs delete mode 100644 src/chomp/typed/infer.rs delete mode 100644 src/chomp/typed/lower.rs delete mode 100644 src/chomp/typed/mod.rs (limited to 'src/chomp') diff --git a/src/chomp/ast-old/error.rs b/src/chomp/ast-old/error.rs new file mode 100644 index 0000000..9057ec3 --- /dev/null +++ b/src/chomp/ast-old/error.rs @@ -0,0 +1,52 @@ +use super::{Expression, Lambda, NamedExpression}; +use proc_macro2::Span; +use std::{ + error::Error, + fmt::{self, Display}, +}; + +#[derive(Debug)] +pub enum TranslateError { + CallNotAFunction { + on: Expression, + span: Option, + }, + WrongArgCount { + lambda: Lambda, + args: Vec, + span: Option, + }, +} + +impl From for syn::Error { + fn from(e: TranslateError) -> Self { + let msg = e.to_string(); + let span = match e { + TranslateError::CallNotAFunction { span, .. } + | TranslateError::WrongArgCount { span, .. } => span, + }; + + Self::new(span.unwrap_or_else(Span::call_site), msg) + } +} + +impl Display for TranslateError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::CallNotAFunction { .. } => { + write!(f, "call expected a function") + } + Self::WrongArgCount { lambda, args, .. } => match (lambda.args.len(), args.len()) { + (1, n) => write!(f, "this function takes 1 argument but {} were supplied", n), + (m, _) => write!(f, "this function takes {} arguments but 1 was supplied", m), + (m, n) => write!( + f, + "this function takes {} arguments but {} were supplied", + m, n + ), + }, + } + } +} + +impl Error for TranslateError {} diff --git a/src/chomp/ast-old/mod.rs b/src/chomp/ast-old/mod.rs new file mode 100644 index 0000000..232381a --- /dev/null +++ b/src/chomp/ast-old/mod.rs @@ -0,0 +1,325 @@ +use std::fmt::{self, Display}; + +use proc_macro2::Span; + +use super::Name; + +pub mod error; +pub mod substitute; + +#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Hash)] +pub struct Epsilon; + +pub type Literal = String; + +#[derive(Clone, Debug)] +pub struct Cat { + pub first: Box, + pub rest: Vec<(Option, NamedExpression)>, +} + +impl Display for Cat { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "({}", self.first)?; + for (_, other) in &self.rest { + write!(f, " . {}", other)?; + } + write!(f, ")") + } +} + +impl PartialEq for Cat { + fn eq(&self, other: &Self) -> bool { + self.first == other.first + && self.rest.len() == other.rest.len() + && self + .rest + .iter() + .zip(other.rest.iter()) + .all(|((_, me), (_, them))| me == them) + } +} + +impl Eq for Cat {} + +#[derive(Clone, Debug)] +pub struct Alt { + pub first: Box, + pub rest: Vec<(Option, NamedExpression)> +} + +impl Display for Alt { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "({}", self.first)?; + for (_, other) in &self.rest { + write!(f, " | {}", other)?; + } + write!(f, ")") + } +} + +impl PartialEq for Alt { + fn eq(&self, other: &Self) -> bool { + self.first == other.first + && self.rest.len() == other.rest.len() + && self + .rest + .iter() + .zip(other.rest.iter()) + .all(|((_, me), (_, them))| me == them) + } +} + +impl Eq for Alt {} + +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Fix { + pub inner: Box, +} + +impl Display for Fix { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "!{}", self.inner) + } +} + +#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)] +pub struct Variable { + pub index: usize, +} + +impl Display for Variable { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "'{}", self.index) + } +} + +/// A function invocation. +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Call { + pub on: Box, + pub args: Vec, +} + +impl Display for Call { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "({}", self.on)?; + + for arg in self.args { + write!(f, " {}", arg)?; + } + + write!(f, ")") + } +} + +/// A function abstraction. +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Lambda { + pub args: Vec, + pub inner: Box, +} + +impl Display for Lambda { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "/")?; + let mut iter = self.args.iter(); + if let Some(arg) = iter.next() { + write!(f, "{}", arg)?; + + for arg in iter { + write!(f, ", {}", arg)?; + } + } + write!(f, "/ {}", self.inner) + } +} + +#[derive(Clone, Debug)] +pub enum Expression { + /// Matches the empty string. + Epsilon(Epsilon), + /// Matches the literal string. + Literal(Literal), + /// Matches one term followed by another. + Cat(Cat), + /// Matches either one term or another. + Alt(Alt), + /// The least fix point of a term. + Fix(Fix), + /// A fixed point variable. + Variable(Variable), + /// A function invocation. + Call(Call), + /// A function abstraction. + Lambda(Lambda), +} + +impl Expression { + pub fn try_into_lambda(self) -> Result { + if let Self::Lambda(l) = self { + Ok(l) + } else { + Err(self) + } + } +} + +impl Display for Expression { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::Epsilon(_) => write!(f, "_"), + Self::Literal(l) => l.fmt(f), + Self::Cat(c) => c.fmt(f), + Self::Alt(a) => a.fmt(f), + Self::Fix(x) => x.fmt(f), + Self::Variable(v) => v.fmt(f), + Self::Lambda(p) => p.fmt(f), + Self::Call(c) => c.fmt(f), + } + } +} + +impl PartialEq for Expression { + fn eq(&self, other: &Self) -> bool { + match self { + Self::Epsilon(_) => matches!(other, Self::Epsilon(_)), + Self::Literal(l) => { + if let Self::Literal(them) = other { + l == them + } else { + false + } + } + Self::Cat(c) => { + if let Self::Cat(them) = other { + c == them + } else { + false + } + } + Self::Alt(a) => { + if let Self::Alt(them) = other { + a == them + } else { + false + } + } + Self::Fix(f) => { + if let Self::Fix(them) = other { + f == them + } else { + false + } + } + Self::Variable(v) => { + if let Self::Variable(them) = other { + v == them + } else { + false + } + } + Self::Lambda(p) => { + if let Self::Lambda(them) = other { + p == them + } else { + false + } + } + Self::Call(c) => { + if let Self::Call(them) = other { + c == them + } else { + false + } + } + } + } +} + +impl Eq for Expression {} + +impl From for Expression { + fn from(eps: Epsilon) -> Self { + Self::Epsilon(eps) + } +} + +impl From for Expression { + fn from(lit: Literal) -> Self { + Self::Literal(lit) + } +} + +impl From for Expression { + fn from(cat: Cat) -> Self { + Self::Cat(cat) + } +} + +impl From for Expression { + fn from(alt: Alt) -> Self { + Self::Alt(alt) + } +} + +impl From for Expression { + fn from(fix: Fix) -> Self { + Self::Fix(fix) + } +} + +impl From for Expression { + fn from(var: Variable) -> Self { + Self::Variable(var) + } +} + +impl From for Expression { + fn from(lambda: Lambda) -> Self { + Self::Lambda(lambda) + } +} + +impl From for Expression { + fn from(call: Call) -> Self { + Self::Call(call) + } +} + +#[derive(Clone, Debug)] +pub struct NamedExpression { + pub name: Option, + 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), + None => self.expr.fmt(f), + } + } +} + +impl PartialEq for NamedExpression { + fn eq(&self, other: &Self) -> bool { + self.expr == other.expr + } +} + +impl Eq for NamedExpression {} + +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Let { + pub name: Name, + pub val: NamedExpression, + pub inner: Box, +} + +#[derive(Clone, Debug, Eq, PartialEq)] +pub enum TopLevel { + Let(Let), + Goal(NamedExpression), +} diff --git a/src/chomp/ast-old/substitute.rs b/src/chomp/ast-old/substitute.rs new file mode 100644 index 0000000..80df588 --- /dev/null +++ b/src/chomp/ast-old/substitute.rs @@ -0,0 +1,412 @@ +use super::{ + error::TranslateError, Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, +}; +use crate::chomp::{ + visit::{Folder, Mapper, Visitable}, + Name, +}; +use proc_macro2::Span; + +struct Deepen { + pub depth: usize, + pub by: usize, +} + +impl Mapper for Deepen { + type Out = (); + + fn map_epsilon( + &mut self, + _name: &mut Option, + _span: Option, + _eps: &mut Epsilon, + ) -> Self::Out { + } + + fn map_literal( + &mut self, + _name: &mut Option, + _span: Option, + _lit: &mut Literal, + ) -> Self::Out { + } + + fn map_cat( + &mut self, + _name: &mut Option, + _span: Option, + cat: &mut Cat, + ) -> Self::Out { + cat.first.map(self); + for (_, other) in &mut cat.rest { + other.map(self); + } + } + + fn map_alt( + &mut self, + _name: &mut Option, + _span: Option, + alt: &mut Alt, + ) -> Self::Out { + alt.first.map(self); + for (_, other) in &mut alt.rest { + other.map(self); + } + } + + fn map_fix( + &mut self, + _name: &mut Option, + _span: Option, + fix: &mut Fix, + ) -> Self::Out { + fix.inner.map(self); + } + + fn map_variable( + &mut self, + _name: &mut Option, + _span: Option, + var: &mut Variable, + ) -> Self::Out { + if var.index >= self.depth { + var.index += self.by; + } + } + + fn map_call( + &mut self, + _name: &mut Option, + _span: Option, + call: &mut Call, + ) -> Self::Out { + call.on.map(self); + for arg in &mut call.args { + arg.map(self); + } + } + + fn map_lambda( + &mut self, + _name: &mut Option, + _span: Option, + lambda: &mut Lambda, + ) -> Self::Out { + self.depth += lambda.args.len(); + lambda.inner.map(self); + self.depth -= lambda.args.len(); + } +} + +pub struct Substitute { + pub index: usize, + pub expr: NamedExpression, +} + +impl Folder for Substitute { + type Out = NamedExpression; + + fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { + NamedExpression { + name, + expr: eps.into(), + span, + } + } + + fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out { + NamedExpression { + name, + expr: lit.into(), + span, + } + } + + fn fold_cat(&mut self, name: Option, span: Option, mut cat: Cat) -> Self::Out { + cat.first = Box::new(cat.first.fold(self)); + cat.rest = cat + .rest + .into_iter() + .map(|(span, e)| (span, e.fold(self))) + .collect(); + NamedExpression { + name, + expr: cat.into(), + span, + } + } + + fn fold_alt(&mut self, name: Option, span: Option, mut alt: Alt) -> Self::Out { + alt.first = Box::new(alt.first.fold(self)); + alt.rest = alt + .rest + .into_iter() + .map(|(span, e)| (span, e.fold(self))) + .collect(); + NamedExpression { + name, + expr: alt.into(), + span, + } + } + + fn fold_fix(&mut self, name: Option, span: Option, mut fix: Fix) -> Self::Out { + fix.inner = Box::new(fix.inner.fold(self)); + NamedExpression { + name, + expr: fix.into(), + span, + } + } + + fn fold_variable( + &mut self, + name: Option, + span: Option, + var: Variable, + ) -> Self::Out { + if var.index == self.index { + self.expr.clone() + } else { + NamedExpression { + name, + expr: Variable { + index: if var.index > self.index { + var.index - 1 + } else { + var.index + }, + } + .into(), + span, + } + } + } + + fn fold_call(&mut self, name: Option, span: Option, mut call: Call) -> Self::Out { + call.on = Box::new(call.on.fold(self)); + call.args = call.args.into_iter().map(|e| e.fold(self)).collect(); + NamedExpression { + name, + expr: call.into(), + span, + } + } + + fn fold_lambda( + &mut self, + name: Option, + span: Option, + mut lambda: Lambda, + ) -> Self::Out { + self.index += lambda.args.len(); + lambda.inner = Box::new(lambda.inner.fold(self)); + self.index -= lambda.args.len(); + NamedExpression { + name, + expr: lambda.into(), + span, + } + } +} + +pub struct Translate { + changed: bool, +} + +impl Translate { + pub fn new() -> Self { + Self { changed: false } + } +} + +impl Default for Translate { + fn default() -> Self { + Self::new() + } +} + +impl Folder for Translate { + type Out = Result; + + fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { + Ok(NamedExpression { + name, + expr: eps.into(), + span, + }) + } + + fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out { + Ok(NamedExpression { + name, + expr: lit.into(), + span, + }) + } + + fn fold_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Out { + Ok(NamedExpression { + name, + expr: cat.into(), + span, + }) + } + + fn fold_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Out { + Ok(NamedExpression { + name, + expr: alt.into(), + span, + }) + } + + fn fold_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Out { + Ok(NamedExpression { + name, + expr: fix.into(), + span, + }) + } + + fn fold_variable( + &mut self, + name: Option, + span: Option, + var: Variable, + ) -> Self::Out { + Ok(NamedExpression { + name, + expr: var.into(), + span, + }) + } + + 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)?; + } + + let lambda = on + .expr + .try_into_lambda() + .map_err(|on| TranslateError::CallNotAFunction { on, span })?; + + if lambda.args.len() != call.args.len() { + return Err(TranslateError::WrongArgCount { + lambda, + args: call.args, + span, + }); + } + + let mut out = *lambda.inner; + + for ((i, mut arg), name) in call.args.into_iter().enumerate().zip(lambda.args).rev() { + arg.name = arg.name.or(Some(name)); + arg.map(&mut Deepen { depth: 0, by: i }); + out = out.fold(&mut Substitute { + index: 0, + expr: arg, + }); + } + + self.changed = true; + while self.changed { + self.changed = false; + out = out.fold(self)?; + } + + self.changed = true; + out.name = name.or(out.name); + out.span = span.or(out.span); + Ok(out) + } + + fn fold_lambda(&mut self, name: Option, span: Option, lambda: Lambda) -> Self::Out { + Ok(NamedExpression { + name, + expr: lambda.into(), + span, + }) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + /// Returns (/x/ x) 'index + fn make_expr(index: usize) -> NamedExpression { + let var = NamedExpression { + name: None, + expr: Variable { index: 0 }.into(), + span: None, + }; + + let lambda = NamedExpression { + name: None, + expr: Lambda { + args: vec!["x".to_owned().into()], + inner: Box::new(var), + } + .into(), + span: None, + }; + + let var = NamedExpression { + name: None, + expr: Variable { index }.into(), + span: None, + }; + + NamedExpression { + name: None, + expr: Call { + on: Box::new(lambda), + args: vec![var], + } + .into(), + span: None, + } + } + + #[test] + fn deepen_lambda() { + let mut expr = make_expr(0); + expr.map(&mut Deepen { depth: 0, by: 1 }); + assert_eq!(expr, make_expr(1)) + } + + #[test] + fn substitute_renames_bigger() { + let expr = make_expr(1); + let expr = expr.fold(&mut Substitute { + index: 0, + expr: NamedExpression { + name: None, + expr: Epsilon.into(), + span: None, + }, + }); + assert_eq!(expr, make_expr(0)) + } + + #[test] + fn translate_lambda() { + let expr = make_expr(1); + let expr = expr.fold(&mut Translate::new()).unwrap(); + assert_eq!( + expr, + NamedExpression { + name: Some("x".to_owned().into()), + expr: Variable { index: 1 }.into(), + span: None + } + ) + } +} diff --git a/src/chomp/ast.rs b/src/chomp/ast.rs new file mode 100644 index 0000000..dbbcb5d --- /dev/null +++ b/src/chomp/ast.rs @@ -0,0 +1,146 @@ +use std::rc::Rc; + +use super::Context; + +#[derive(Debug)] +pub struct Lambda(pub Rc, pub Rc); + +#[derive(Debug)] +pub enum Tree { + Epsilon, + Bottom, + Identity, + Literal(String), + Variable, + Cat(Rc, Rc), + Alt(Rc, Rc), + Fix(Rc), + Call(Rc, Rc), + Lambda(Lambda), + Let(Rc, Rc, Rc), +} + +impl Tree { + pub fn try_as_lambda(&self) -> Option<&Lambda> { + if let Self::Lambda(v) = self { + Some(v) + } else { + None + } + } +} + +#[derive(Clone, Debug)] +pub enum TranslateError { + CallFunNotLambda(Rc), +} + +pub(crate) fn substitute( + ctx: &mut Context, + tree: &Rc, + from: &Rc, + into: &Rc, +) -> Option> { + if Rc::ptr_eq(tree, from) { + return Some(into.clone()); + } + + match tree.as_ref() { + Tree::Epsilon | Tree::Bottom | Tree::Identity | Tree::Literal(_) | Tree::Variable => None, + Tree::Cat(front, back) => { + let new_front = ctx.substitute(front, from, into); + let new_back = ctx.substitute(back, from, into); + let (front, back) = match (new_front, new_back) { + (None, None) => return None, + (None, Some(back)) => (front.clone(), back), + (Some(front), None) => (front, back.clone()), + (Some(front), Some(back)) => (front, back), + }; + Some(ctx.tree_interner.cat(front, back)) + } + Tree::Alt(left, right) => { + let new_left = ctx.substitute(left, from, into); + let new_right = ctx.substitute(right, from, into); + let (left, right) = match (new_left, new_right) { + (None, None) => return None, + (None, Some(right)) => (left.clone(), right), + (Some(left), None) => (left, right.clone()), + (Some(left), Some(right)) => (left, right), + }; + Some(ctx.tree_interner.alt(left, right)) + } + Tree::Fix(inner) => { + let inner = ctx.substitute(inner, from, into)?; + Some(ctx.tree_interner.fix(inner)) + } + Tree::Call(fun, arg) => { + let new_fun = ctx.substitute(fun, from, into); + let new_arg = ctx.substitute(arg, from, into); + let (fun, arg) = match (new_fun, new_arg) { + (None, None) => return None, + (None, Some(arg)) => (fun.clone(), arg), + (Some(fun), None) => (fun, arg.clone()), + (Some(fun), Some(arg)) => (fun, arg), + }; + Some(ctx.tree_interner.call(fun, arg)) + } + Tree::Lambda(Lambda(arg, inner)) => { + let inner = ctx.substitute(inner, from, into)?; + Some(Rc::new(Tree::Lambda(Lambda(arg.clone(), inner)))) + } + Tree::Let(bind, arg, inner) => { + let new_bind = ctx.substitute(bind, from, into); + let new_inner = ctx.substitute(inner, from, into); + let (bind, inner) = match (new_bind, new_inner) { + (None, None) => return None, + (None, Some(inner)) => (bind.clone(), inner), + (Some(bind), None) => (bind, inner.clone()), + (Some(bind), Some(inner)) => (bind, inner), + }; + Some(Rc::new(Tree::Let(bind, arg.clone(), inner))) + } + } +} + +pub(crate) fn translate( + ctx: &mut Context, + tree: &Rc, +) -> Result>, TranslateError> { + match tree.as_ref() { + Tree::Epsilon + | Tree::Bottom + | Tree::Identity + | Tree::Literal(_) + | Tree::Variable + | Tree::Cat(_, _) + | Tree::Alt(_, _) + | Tree::Fix(_) + | Tree::Lambda(_) => Ok(None), + Tree::Call(fun, arg) => { + let fun = ctx.translate(fun)?.unwrap_or_else(|| fun.clone()); + let lambda = fun + .try_as_lambda() + .ok_or_else(|| TranslateError::CallFunNotLambda(fun.clone()))?; + let mut out = ctx + .substitute(&lambda.1, &lambda.0, arg) + .unwrap_or_else(|| lambda.1.clone()); + loop { + match ctx.translate(&out)? { + Some(tree) => out = tree, + None => return Ok(Some(out)), + } + } + } + Tree::Let(bind, arg, inner) => { + let mut out = ctx + .substitute(inner, arg, bind) + .unwrap_or_else(|| inner.clone()); + loop { + match ctx.translate(&out)? { + Some(tree) => out = tree, + None => return Ok(Some(out)), + } + } + } + } +} diff --git a/src/chomp/ast/error.rs b/src/chomp/ast/error.rs deleted file mode 100644 index 9057ec3..0000000 --- a/src/chomp/ast/error.rs +++ /dev/null @@ -1,52 +0,0 @@ -use super::{Expression, Lambda, NamedExpression}; -use proc_macro2::Span; -use std::{ - error::Error, - fmt::{self, Display}, -}; - -#[derive(Debug)] -pub enum TranslateError { - CallNotAFunction { - on: Expression, - span: Option, - }, - WrongArgCount { - lambda: Lambda, - args: Vec, - span: Option, - }, -} - -impl From for syn::Error { - fn from(e: TranslateError) -> Self { - let msg = e.to_string(); - let span = match e { - TranslateError::CallNotAFunction { span, .. } - | TranslateError::WrongArgCount { span, .. } => span, - }; - - Self::new(span.unwrap_or_else(Span::call_site), msg) - } -} - -impl Display for TranslateError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::CallNotAFunction { .. } => { - write!(f, "call expected a function") - } - Self::WrongArgCount { lambda, args, .. } => match (lambda.args.len(), args.len()) { - (1, n) => write!(f, "this function takes 1 argument but {} were supplied", n), - (m, _) => write!(f, "this function takes {} arguments but 1 was supplied", m), - (m, n) => write!( - f, - "this function takes {} arguments but {} were supplied", - m, n - ), - }, - } - } -} - -impl Error for TranslateError {} diff --git a/src/chomp/ast/mod.rs b/src/chomp/ast/mod.rs deleted file mode 100644 index 232381a..0000000 --- a/src/chomp/ast/mod.rs +++ /dev/null @@ -1,325 +0,0 @@ -use std::fmt::{self, Display}; - -use proc_macro2::Span; - -use super::Name; - -pub mod error; -pub mod substitute; - -#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Hash)] -pub struct Epsilon; - -pub type Literal = String; - -#[derive(Clone, Debug)] -pub struct Cat { - pub first: Box, - pub rest: Vec<(Option, NamedExpression)>, -} - -impl Display for Cat { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "({}", self.first)?; - for (_, other) in &self.rest { - write!(f, " . {}", other)?; - } - write!(f, ")") - } -} - -impl PartialEq for Cat { - fn eq(&self, other: &Self) -> bool { - self.first == other.first - && self.rest.len() == other.rest.len() - && self - .rest - .iter() - .zip(other.rest.iter()) - .all(|((_, me), (_, them))| me == them) - } -} - -impl Eq for Cat {} - -#[derive(Clone, Debug)] -pub struct Alt { - pub first: Box, - pub rest: Vec<(Option, NamedExpression)> -} - -impl Display for Alt { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "({}", self.first)?; - for (_, other) in &self.rest { - write!(f, " | {}", other)?; - } - write!(f, ")") - } -} - -impl PartialEq for Alt { - fn eq(&self, other: &Self) -> bool { - self.first == other.first - && self.rest.len() == other.rest.len() - && self - .rest - .iter() - .zip(other.rest.iter()) - .all(|((_, me), (_, them))| me == them) - } -} - -impl Eq for Alt {} - -#[derive(Clone, Debug, Eq, PartialEq)] -pub struct Fix { - pub inner: Box, -} - -impl Display for Fix { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "!{}", self.inner) - } -} - -#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)] -pub struct Variable { - pub index: usize, -} - -impl Display for Variable { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "'{}", self.index) - } -} - -/// A function invocation. -#[derive(Clone, Debug, Eq, PartialEq)] -pub struct Call { - pub on: Box, - pub args: Vec, -} - -impl Display for Call { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "({}", self.on)?; - - for arg in self.args { - write!(f, " {}", arg)?; - } - - write!(f, ")") - } -} - -/// A function abstraction. -#[derive(Clone, Debug, Eq, PartialEq)] -pub struct Lambda { - pub args: Vec, - pub inner: Box, -} - -impl Display for Lambda { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "/")?; - let mut iter = self.args.iter(); - if let Some(arg) = iter.next() { - write!(f, "{}", arg)?; - - for arg in iter { - write!(f, ", {}", arg)?; - } - } - write!(f, "/ {}", self.inner) - } -} - -#[derive(Clone, Debug)] -pub enum Expression { - /// Matches the empty string. - Epsilon(Epsilon), - /// Matches the literal string. - Literal(Literal), - /// Matches one term followed by another. - Cat(Cat), - /// Matches either one term or another. - Alt(Alt), - /// The least fix point of a term. - Fix(Fix), - /// A fixed point variable. - Variable(Variable), - /// A function invocation. - Call(Call), - /// A function abstraction. - Lambda(Lambda), -} - -impl Expression { - pub fn try_into_lambda(self) -> Result { - if let Self::Lambda(l) = self { - Ok(l) - } else { - Err(self) - } - } -} - -impl Display for Expression { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::Epsilon(_) => write!(f, "_"), - Self::Literal(l) => l.fmt(f), - Self::Cat(c) => c.fmt(f), - Self::Alt(a) => a.fmt(f), - Self::Fix(x) => x.fmt(f), - Self::Variable(v) => v.fmt(f), - Self::Lambda(p) => p.fmt(f), - Self::Call(c) => c.fmt(f), - } - } -} - -impl PartialEq for Expression { - fn eq(&self, other: &Self) -> bool { - match self { - Self::Epsilon(_) => matches!(other, Self::Epsilon(_)), - Self::Literal(l) => { - if let Self::Literal(them) = other { - l == them - } else { - false - } - } - Self::Cat(c) => { - if let Self::Cat(them) = other { - c == them - } else { - false - } - } - Self::Alt(a) => { - if let Self::Alt(them) = other { - a == them - } else { - false - } - } - Self::Fix(f) => { - if let Self::Fix(them) = other { - f == them - } else { - false - } - } - Self::Variable(v) => { - if let Self::Variable(them) = other { - v == them - } else { - false - } - } - Self::Lambda(p) => { - if let Self::Lambda(them) = other { - p == them - } else { - false - } - } - Self::Call(c) => { - if let Self::Call(them) = other { - c == them - } else { - false - } - } - } - } -} - -impl Eq for Expression {} - -impl From for Expression { - fn from(eps: Epsilon) -> Self { - Self::Epsilon(eps) - } -} - -impl From for Expression { - fn from(lit: Literal) -> Self { - Self::Literal(lit) - } -} - -impl From for Expression { - fn from(cat: Cat) -> Self { - Self::Cat(cat) - } -} - -impl From for Expression { - fn from(alt: Alt) -> Self { - Self::Alt(alt) - } -} - -impl From for Expression { - fn from(fix: Fix) -> Self { - Self::Fix(fix) - } -} - -impl From for Expression { - fn from(var: Variable) -> Self { - Self::Variable(var) - } -} - -impl From for Expression { - fn from(lambda: Lambda) -> Self { - Self::Lambda(lambda) - } -} - -impl From for Expression { - fn from(call: Call) -> Self { - Self::Call(call) - } -} - -#[derive(Clone, Debug)] -pub struct NamedExpression { - pub name: Option, - 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), - None => self.expr.fmt(f), - } - } -} - -impl PartialEq for NamedExpression { - fn eq(&self, other: &Self) -> bool { - self.expr == other.expr - } -} - -impl Eq for NamedExpression {} - -#[derive(Clone, Debug, Eq, PartialEq)] -pub struct Let { - pub name: Name, - pub val: NamedExpression, - pub inner: Box, -} - -#[derive(Clone, Debug, Eq, PartialEq)] -pub enum TopLevel { - Let(Let), - Goal(NamedExpression), -} diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs deleted file mode 100644 index 80df588..0000000 --- a/src/chomp/ast/substitute.rs +++ /dev/null @@ -1,412 +0,0 @@ -use super::{ - error::TranslateError, Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, -}; -use crate::chomp::{ - visit::{Folder, Mapper, Visitable}, - Name, -}; -use proc_macro2::Span; - -struct Deepen { - pub depth: usize, - pub by: usize, -} - -impl Mapper for Deepen { - type Out = (); - - fn map_epsilon( - &mut self, - _name: &mut Option, - _span: Option, - _eps: &mut Epsilon, - ) -> Self::Out { - } - - fn map_literal( - &mut self, - _name: &mut Option, - _span: Option, - _lit: &mut Literal, - ) -> Self::Out { - } - - fn map_cat( - &mut self, - _name: &mut Option, - _span: Option, - cat: &mut Cat, - ) -> Self::Out { - cat.first.map(self); - for (_, other) in &mut cat.rest { - other.map(self); - } - } - - fn map_alt( - &mut self, - _name: &mut Option, - _span: Option, - alt: &mut Alt, - ) -> Self::Out { - alt.first.map(self); - for (_, other) in &mut alt.rest { - other.map(self); - } - } - - fn map_fix( - &mut self, - _name: &mut Option, - _span: Option, - fix: &mut Fix, - ) -> Self::Out { - fix.inner.map(self); - } - - fn map_variable( - &mut self, - _name: &mut Option, - _span: Option, - var: &mut Variable, - ) -> Self::Out { - if var.index >= self.depth { - var.index += self.by; - } - } - - fn map_call( - &mut self, - _name: &mut Option, - _span: Option, - call: &mut Call, - ) -> Self::Out { - call.on.map(self); - for arg in &mut call.args { - arg.map(self); - } - } - - fn map_lambda( - &mut self, - _name: &mut Option, - _span: Option, - lambda: &mut Lambda, - ) -> Self::Out { - self.depth += lambda.args.len(); - lambda.inner.map(self); - self.depth -= lambda.args.len(); - } -} - -pub struct Substitute { - pub index: usize, - pub expr: NamedExpression, -} - -impl Folder for Substitute { - type Out = NamedExpression; - - fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { - NamedExpression { - name, - expr: eps.into(), - span, - } - } - - fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out { - NamedExpression { - name, - expr: lit.into(), - span, - } - } - - fn fold_cat(&mut self, name: Option, span: Option, mut cat: Cat) -> Self::Out { - cat.first = Box::new(cat.first.fold(self)); - cat.rest = cat - .rest - .into_iter() - .map(|(span, e)| (span, e.fold(self))) - .collect(); - NamedExpression { - name, - expr: cat.into(), - span, - } - } - - fn fold_alt(&mut self, name: Option, span: Option, mut alt: Alt) -> Self::Out { - alt.first = Box::new(alt.first.fold(self)); - alt.rest = alt - .rest - .into_iter() - .map(|(span, e)| (span, e.fold(self))) - .collect(); - NamedExpression { - name, - expr: alt.into(), - span, - } - } - - fn fold_fix(&mut self, name: Option, span: Option, mut fix: Fix) -> Self::Out { - fix.inner = Box::new(fix.inner.fold(self)); - NamedExpression { - name, - expr: fix.into(), - span, - } - } - - fn fold_variable( - &mut self, - name: Option, - span: Option, - var: Variable, - ) -> Self::Out { - if var.index == self.index { - self.expr.clone() - } else { - NamedExpression { - name, - expr: Variable { - index: if var.index > self.index { - var.index - 1 - } else { - var.index - }, - } - .into(), - span, - } - } - } - - fn fold_call(&mut self, name: Option, span: Option, mut call: Call) -> Self::Out { - call.on = Box::new(call.on.fold(self)); - call.args = call.args.into_iter().map(|e| e.fold(self)).collect(); - NamedExpression { - name, - expr: call.into(), - span, - } - } - - fn fold_lambda( - &mut self, - name: Option, - span: Option, - mut lambda: Lambda, - ) -> Self::Out { - self.index += lambda.args.len(); - lambda.inner = Box::new(lambda.inner.fold(self)); - self.index -= lambda.args.len(); - NamedExpression { - name, - expr: lambda.into(), - span, - } - } -} - -pub struct Translate { - changed: bool, -} - -impl Translate { - pub fn new() -> Self { - Self { changed: false } - } -} - -impl Default for Translate { - fn default() -> Self { - Self::new() - } -} - -impl Folder for Translate { - type Out = Result; - - fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { - Ok(NamedExpression { - name, - expr: eps.into(), - span, - }) - } - - fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out { - Ok(NamedExpression { - name, - expr: lit.into(), - span, - }) - } - - fn fold_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Out { - Ok(NamedExpression { - name, - expr: cat.into(), - span, - }) - } - - fn fold_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Out { - Ok(NamedExpression { - name, - expr: alt.into(), - span, - }) - } - - fn fold_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Out { - Ok(NamedExpression { - name, - expr: fix.into(), - span, - }) - } - - fn fold_variable( - &mut self, - name: Option, - span: Option, - var: Variable, - ) -> Self::Out { - Ok(NamedExpression { - name, - expr: var.into(), - span, - }) - } - - 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)?; - } - - let lambda = on - .expr - .try_into_lambda() - .map_err(|on| TranslateError::CallNotAFunction { on, span })?; - - if lambda.args.len() != call.args.len() { - return Err(TranslateError::WrongArgCount { - lambda, - args: call.args, - span, - }); - } - - let mut out = *lambda.inner; - - for ((i, mut arg), name) in call.args.into_iter().enumerate().zip(lambda.args).rev() { - arg.name = arg.name.or(Some(name)); - arg.map(&mut Deepen { depth: 0, by: i }); - out = out.fold(&mut Substitute { - index: 0, - expr: arg, - }); - } - - self.changed = true; - while self.changed { - self.changed = false; - out = out.fold(self)?; - } - - self.changed = true; - out.name = name.or(out.name); - out.span = span.or(out.span); - Ok(out) - } - - fn fold_lambda(&mut self, name: Option, span: Option, lambda: Lambda) -> Self::Out { - Ok(NamedExpression { - name, - expr: lambda.into(), - span, - }) - } -} - -#[cfg(test)] -mod tests { - use super::*; - - /// Returns (/x/ x) 'index - fn make_expr(index: usize) -> NamedExpression { - let var = NamedExpression { - name: None, - expr: Variable { index: 0 }.into(), - span: None, - }; - - let lambda = NamedExpression { - name: None, - expr: Lambda { - args: vec!["x".to_owned().into()], - inner: Box::new(var), - } - .into(), - span: None, - }; - - let var = NamedExpression { - name: None, - expr: Variable { index }.into(), - span: None, - }; - - NamedExpression { - name: None, - expr: Call { - on: Box::new(lambda), - args: vec![var], - } - .into(), - span: None, - } - } - - #[test] - fn deepen_lambda() { - let mut expr = make_expr(0); - expr.map(&mut Deepen { depth: 0, by: 1 }); - assert_eq!(expr, make_expr(1)) - } - - #[test] - fn substitute_renames_bigger() { - let expr = make_expr(1); - let expr = expr.fold(&mut Substitute { - index: 0, - expr: NamedExpression { - name: None, - expr: Epsilon.into(), - span: None, - }, - }); - assert_eq!(expr, make_expr(0)) - } - - #[test] - fn translate_lambda() { - let expr = make_expr(1); - let expr = expr.fold(&mut Translate::new()).unwrap(); - assert_eq!( - expr, - NamedExpression { - name: Some("x".to_owned().into()), - expr: Variable { index: 1 }.into(), - span: None - } - ) - } -} diff --git a/src/chomp/cst.rs b/src/chomp/cst.rs new file mode 100644 index 0000000..8e3163b --- /dev/null +++ b/src/chomp/cst.rs @@ -0,0 +1,65 @@ +use std::rc::Rc; + +use super::Context; + +#[derive(Debug)] +pub struct Name; + +#[derive(Debug)] +pub enum Shape { + Epsilon, + Literal(String), + Variable(usize), + Cat(Vec>), + Alt(Vec>), + Fix(Rc), + Call(Vec>), + Lambda(Vec, Rc), + Let(Name, Rc, Rc), +} + +pub(crate) fn as_tree(ctx: &mut Context, shape: &Rc) -> Rc { + fn lambda_as_tree(ctx: &mut Context, count: usize, inner: &Rc) -> Rc { + if count == 0 { + ctx.as_tree(inner) + } else { + ctx.new_lambda(|ctx| lambda_as_tree(ctx, count - 1, inner)) + } + } + + match shape.as_ref() { + Shape::Epsilon => ctx.tree_interner.epsilon(), + Shape::Literal(l) => ctx.tree_interner.literal(l.to_owned()), + Shape::Variable(idx) => ctx.lookup_tree_variable(*idx), + Shape::Cat(v) => { + let epsilon = ctx.tree_interner.epsilon(); + v.into_iter().fold(epsilon, |front, back| { + let back = ctx.as_tree(back); + ctx.tree_interner.cat(front, back) + }) + } + Shape::Alt(v) => { + let bottom = ctx.tree_interner.bottom(); + v.into_iter().fold(bottom, |left, right| { + let right = ctx.as_tree(right); + ctx.tree_interner.alt(left, right) + }) + } + Shape::Fix(inner) => { + let inner = ctx.as_tree(inner); + ctx.tree_interner.fix(inner) + } + Shape::Call(v) => { + let identity = ctx.tree_interner.identity(); + v.into_iter().fold(identity, |fun, arg| { + let arg = ctx.as_tree(arg); + ctx.tree_interner.call(fun, arg) + }) + } + Shape::Lambda(names, inner) => lambda_as_tree(ctx, names.len(), inner), + Shape::Let(_, bind, inner) => { + let bind = ctx.as_tree(bind); + ctx.new_let(bind, |ctx| ctx.as_tree(inner)) + } + } +} diff --git a/src/chomp/intern.rs b/src/chomp/intern.rs new file mode 100644 index 0000000..b224e53 --- /dev/null +++ b/src/chomp/intern.rs @@ -0,0 +1,151 @@ +use std::{cell::RefCell, collections::HashMap, hash::Hash, rc::Rc}; + +use super::{ + ast::Tree, + typed::{GroundType, Type}, +}; + +#[derive(Debug)] +pub struct Intern(Rc); + +impl PartialEq for Intern { + fn eq(&self, other: &Self) -> bool { + Rc::ptr_eq(&self.0, &other.0) + } +} + +impl Eq for Intern {} + +impl Hash for Intern { + fn hash(&self, state: &mut H) { + Rc::as_ptr(&self.0).hash(state) + } +} + +impl From> for Intern { + fn from(inner: Rc) -> Self { + Self(inner) + } +} + +#[derive(Debug)] +pub struct TreeInterner { + epsilon: Option>, + bottom: Option>, + identity: Option>, + literal: HashMap>, + cat: HashMap<(Intern, Intern), Rc>, + alt: HashMap<(Intern, Intern), Rc>, + fix: HashMap, Rc>, + call: HashMap<(Intern, Intern), Rc>, +} + +impl TreeInterner { + pub fn epsilon(&mut self) -> Rc { + self.epsilon + .get_or_insert_with(|| Rc::new(Tree::Epsilon)) + .clone() + } + + pub fn bottom(&mut self) -> Rc { + self.bottom + .get_or_insert_with(|| Rc::new(Tree::Bottom)) + .clone() + } + + pub fn identity(&mut self) -> Rc { + self.identity + .get_or_insert_with(|| Rc::new(Tree::Identity)) + .clone() + } + + pub fn literal(&mut self, lit: String) -> Rc { + self.literal + .entry(lit) + .or_insert_with_key(|lit| Rc::new(Tree::Literal(lit.clone()))) + .clone() + } + + pub fn cat(&mut self, front: Rc, back: Rc) -> Rc { + self.cat + .entry((Intern(front), Intern(back))) + .or_insert_with_key(|(front, back)| Rc::new(Tree::Cat(front.0.clone(), back.0.clone()))) + .clone() + } + + pub fn alt(&mut self, left: Rc, right: Rc) -> Rc { + self.alt + .entry((Intern(left), Intern(right))) + .or_insert_with_key(|(left, right)| Rc::new(Tree::Alt(left.0.clone(), right.0.clone()))) + .clone() + } + + pub fn fix(&mut self, inner: Rc) -> Rc { + self.fix + .entry(Intern(inner)) + .or_insert_with_key(|inner| Rc::new(Tree::Fix(inner.0.clone()))) + .clone() + } + + pub fn call(&mut self, fun: Rc, arg: Rc) -> Rc { + self.call + .entry((Intern(fun), Intern(arg))) + .or_insert_with_key(|(fun, arg)| Rc::new(Tree::Call(fun.0.clone(), arg.0.clone()))) + .clone() + } +} + +#[derive(Debug)] +pub struct TypeInterner { + epsilon: Option>, + bottom: Option>, + character: HashMap>, + cat: HashMap<(Intern, Intern), Rc>, + alt: HashMap<(Intern, Intern), Rc>, + fix: HashMap, Rc>, +} + +impl TypeInterner { + pub fn epsilon(&mut self) -> Rc { + self.epsilon + .get_or_insert_with(|| Rc::new(GroundType::Epsilon.into())) + .clone() + } + + pub fn bottom(&mut self) -> Rc { + self.bottom + .get_or_insert_with(|| Rc::new(GroundType::Bottom.into())) + .clone() + } + + pub fn character(&mut self, c: char) -> Rc { + self.character + .entry(c) + .or_insert_with(|| Rc::new(GroundType::Character(c).into())) + .clone() + } + + pub fn cat(&mut self, front: Rc, back: Rc) -> Rc { + self.cat + .entry((Intern(front), Intern(back))) + .or_insert_with_key(|(front, back)| { + Rc::new( + GroundType::Cat(RefCell::new(front.0.clone()), RefCell::new(back.0.clone())) + .into(), + ) + }) + .clone() + } + + pub fn alt(&mut self, left: Rc, right: Rc) -> Rc { + self.alt + .entry((Intern(left), Intern(right))) + .or_insert_with_key(|(left, right)| { + Rc::new( + GroundType::Alt(RefCell::new(left.0.clone()), RefCell::new(right.0.clone())) + .into(), + ) + }) + .clone() + } +} diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs index 79b4fac..c8c82ae 100644 --- a/src/chomp/mod.rs +++ b/src/chomp/mod.rs @@ -1,114 +1,128 @@ -use std::{fmt, hash}; +use std::{collections::HashMap, rc::Rc}; -use heck::{CamelCase, SnakeCase}; -use proc_macro2::{Ident, Span}; -use syn::ext::IdentExt; +use intern::Intern; -pub mod ast; -pub mod set; -pub mod typed; -pub mod visit; +use self::ast::Lambda; -#[derive(Clone, Debug)] -pub enum Name { - Spanned(Ident), - Spanless(String), +mod ast; +mod cst; +mod intern; +mod typed; + +type SubstTriple = (Intern, Intern, Intern); + +#[derive(Debug)] +pub struct Context { + // Abstract tree interning + var_stack: Vec>, + pub tree_interner: intern::TreeInterner, + pub type_interner: intern::TypeInterner, + + // Caches + as_tree: HashMap, Rc>, + substitute: HashMap>>, + translate: HashMap, Result>, ast::TranslateError>>, + type_of: HashMap< + Intern, + Result, + >, } -impl Name { - pub fn span(&self) -> Option { - match self { - Self::Spanned(i) => Some(i.span()), - Self::Spanless(_) => None, +impl Context { + /// Converts a concrete syntax tree into an abstract one. + pub fn as_tree(&mut self, shape: &Rc) -> Rc { + if let Some(tree) = self.as_tree.get(&shape.clone().into()) { + return tree.clone(); } + let tree = cst::as_tree(self, shape); + self.as_tree.insert(shape.clone().into(), tree.clone()); + tree } - pub fn into_ident(self, span: Span) -> Ident { - match self { - Self::Spanned(i) => i, - Self::Spanless(s) => Ident::new(&s, span), + /// Creates a copy of `tree` that replaces variables pointing to `from` with `into`. + pub fn substitute( + &mut self, + tree: &Rc, + from: &Rc, + into: &Rc, + ) -> Option> { + if let Some(tree) = self.substitute.get(&( + tree.clone().into(), + from.clone().into(), + into.clone().into(), + )) { + return tree.clone(); } + let out = ast::substitute(self, tree, from, into); + self.substitute.insert( + ( + tree.clone().into(), + from.clone().into(), + into.clone().into(), + ), + out.clone(), + ); + out } -} -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() - } + /// Expands let bindings and function calls until the top level construct is a base term. + pub fn translate( + &mut self, + tree: &Rc, + ) -> Result>, ast::TranslateError> { + if let Some(tree) = self.translate.get(&tree.clone().into()) { + return tree.clone(); } + let out = ast::translate(self, tree); + self.translate.insert(tree.clone().into(), out.clone()); + out } -} -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() - } + /// Computes set of unsolvable type constraints for a term. Returns an error + /// if a solvable constraint is unsatisfiable, or the constraints cannot be inferred. + pub fn type_of( + &mut self, + tree: &Rc, + ) -> Result { + if let Some(ty) = self.type_of.get(&tree.clone().into()) { + return ty.clone(); } + let ty = typed::type_of(self, tree); + self.type_of.insert(tree.clone().into(), ty.clone()); + ty } -} -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, - } + fn lookup_tree_variable(&self, idx: usize) -> Rc { + self.var_stack[idx].clone() } -} -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(), - } - } -} + fn new_lambda Rc>(&mut self, f: F) -> Rc { + // Create variable node + let arg = Rc::new(ast::Tree::Variable); -impl Eq for Name {} + // Apply inner with the variable + self.var_stack.push(arg.clone()); + let inner = f(self); + self.var_stack.pop(); -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), - } + // Create the lambda + Rc::new(ast::Tree::Lambda(Lambda(arg, inner))) } -} -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), - } - } -} + fn new_let Rc>( + &mut self, + bind: Rc, + inner: F, + ) -> Rc { + // Create variable node + let arg = Rc::new(ast::Tree::Variable); -impl From for Name { - fn from(ident: Ident) -> Self { - Self::Spanned(ident) - } -} + // Apply inner with the variable + self.var_stack.push(arg.clone()); + let inner = inner(self); + self.var_stack.pop(); -impl From for Name { - fn from(string: String) -> Self { - Self::Spanless(string) + // Create the let + Rc::new(ast::Tree::Let(bind, arg, inner)) } } diff --git a/src/chomp/typed-old/context.rs b/src/chomp/typed-old/context.rs new file mode 100644 index 0000000..f3263ce --- /dev/null +++ b/src/chomp/typed-old/context.rs @@ -0,0 +1,58 @@ +use crate::chomp::ast::Variable; + +use super::Type; + +#[derive(Debug, Default)] +pub struct Context { + vars: Vec, + unguard_points: Vec, +} + +impl Context { + pub fn new() -> Self { + Self::default() + } + + pub fn depth(&self) -> usize { + self.vars.len() + } + + pub fn with_unguard R, R>(&mut self, f: F) -> R { + self.unguard_points.push(self.vars.len()); + let res = f(self); + self.unguard_points.pop(); + res + } + + pub fn get_variable_type(&self, var: Variable) -> Result<&Type, GetVariableError> { + self.vars + .iter() + .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) + }) + } + + pub fn with_variable_type R, R>(&mut self, ty: Type, f: F) -> R { + self.vars.push(ty); + let res = f(self); + self.vars.pop(); + res + } +} + +#[derive(Clone, Copy, Debug, Eq, PartialEq)] +pub enum GetVariableError { + FreeVariable, + GuardedVariable, +} diff --git a/src/chomp/typed-old/error.rs b/src/chomp/typed-old/error.rs new file mode 100644 index 0000000..5c1e21e --- /dev/null +++ b/src/chomp/typed-old/error.rs @@ -0,0 +1,164 @@ +use std::{ + error::Error, + fmt::{self, Display}, +}; + +use proc_macro2::Span; + +use crate::chomp::{ast::Variable, Name}; + +use super::{context::GetVariableError, TypedExpression}; + +/// A type error when using a fix point variable. +#[derive(Debug)] +pub struct VariableError { + pub inner: GetVariableError, + pub var: Variable, + pub span: Option, + 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 { + GetVariableError::FreeVariable => write!(f, "unbound variable: "), + GetVariableError::GuardedVariable => write!(f, "usage of guarded variable: "), + }?; + + if let Some(name) = &self.name { + write!(f, "`{}`", name) + } else { + write!(f, "'{}", self.var.index) + } + } +} + +impl Error for VariableError {} + +#[derive(Debug)] +pub enum CatError { + FirstNullable { + expr: TypedExpression, + punct: Option, + }, + FirstFlastOverlap { + first: Vec, + punct: Option, + 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 Display for CatError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::FirstNullable { .. } => write!(f, "first part of concatenation is nullable"), + Self::FirstFlastOverlap { .. } => { + write!(f, "first set overlaps with preceding flast set") + } + } + } +} + +impl Error for CatError {} + +#[derive(Debug)] +pub enum AltError { + BothNullable { + left: Vec, + punct: Option, + right: TypedExpression, + }, + FirstOverlap { + left: Vec, + punct: Option, + 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 Display for AltError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::BothNullable { .. } => write!(f, "both branches are nullable"), + Self::FirstOverlap { .. } => write!(f, "first sets of both branches overlap"), + } + } +} + +impl Error for AltError {} + +#[derive(Debug)] +pub enum TypeError { + Cat(CatError), + Alt(AltError), + Variable(VariableError), +} + +impl From for TypeError { + fn from(other: CatError) -> Self { + Self::Cat(other) + } +} + +impl From for TypeError { + fn from(other: AltError) -> Self { + Self::Alt(other) + } +} + +impl From for TypeError { + fn from(other: VariableError) -> Self { + Self::Variable(other) + } +} + +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(), + } + } +} + +impl Display for TypeError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::Cat(e) => e.fmt(f), + Self::Alt(e) => e.fmt(f), + Self::Variable(e) => e.fmt(f), + } + } +} + +impl Error for TypeError {} diff --git a/src/chomp/typed-old/infer.rs b/src/chomp/typed-old/infer.rs new file mode 100644 index 0000000..e2c2198 --- /dev/null +++ b/src/chomp/typed-old/infer.rs @@ -0,0 +1,127 @@ +use proc_macro2::Span; + +use crate::chomp::{Name, ast::{Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, substitute::Translate}, visit::{Folder, Visitable}}; + +use super::{Type, Typed, TypedExpression, context::Context, error::{TypeError, VariableError}}; + +#[derive(Debug)] +pub struct TypeInfer<'a> { + pub context: &'a mut Context, +} + +impl Folder for TypeInfer<'_> { + type Out = Result; + + fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { + Ok(TypedExpression { + inner: super::Epsilon::from(eps).into(), + name, + span, + }) + } + + fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out { + Ok(TypedExpression { + inner: super::Literal::from(lit).into(), + name, + span, + }) + } + + fn fold_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Out { + let first = cat.first.fold(self)?; + 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, + }) + }) + } + + fn fold_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Out { + let first = alt.first.fold(self)?; + let rest = alt + .rest + .into_iter() + .map(|(punct, term)| -> Result<_, TypeError> { Ok((punct, term.fold(self)?)) }) + .collect::, _>>()?; + Ok(TypedExpression { + inner: super::Alt::new(first, rest)?.into(), + name, + span, + }) + } + + fn fold_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Out { + let mut ty = Type::default(); + + loop { + let last = ty; + let res = self.context.with_variable_type(last.clone(), |context| { + fix.inner.clone().fold(&mut TypeInfer { context }) + })?; + ty = res.get_type().clone(); + + if last == ty { + return Ok(TypedExpression { + inner: super::Fix { + inner: Box::new(res), + } + .into(), + name, + span, + }); + } + } + } + + fn fold_variable( + &mut self, + name: Option, + span: Option, + var: Variable, + ) -> Self::Out { + let ty = match self.context.get_variable_type(var) { + Ok(ty) => ty.clone(), + Err(inner) => { + return Err(VariableError { + inner, + var, + span, + name, + } + .into()) + } + }; + Ok(TypedExpression { + inner: super::Variable { inner: var, ty }.into(), + name, + span, + }) + } + + 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_lambda( + &mut self, + _name: Option, + _span: Option, + _lambda: Lambda, + ) -> Self::Out { + unimplemented!() + } +} diff --git a/src/chomp/typed-old/lower.rs b/src/chomp/typed-old/lower.rs new file mode 100644 index 0000000..37589a1 --- /dev/null +++ b/src/chomp/typed-old/lower.rs @@ -0,0 +1,41 @@ +use proc_macro2::Span; + +use crate::chomp::Name; + +use super::{Alt, Cat, Epsilon, Fix, Literal, RawTypedExpression, TypedExpression, Variable}; + +pub trait Backend: Default { + type Id; + type Code; + + fn gen_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Id; + + fn gen_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Id; + + fn gen_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Id; + + fn gen_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Id; + + fn gen_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Id; + + fn gen_variable(&mut self, name: Option, span: Option, var: Variable) -> Self::Id; + + fn emit_code(self, name: Option, span: Option, id: Self::Id) -> Self::Code; +} + +pub trait GenerateCode { + fn gen(self, backend: &mut B) -> B::Id; +} + +impl GenerateCode for TypedExpression { + fn gen(self, backend: &mut B) -> B::Id { + match self.inner { + RawTypedExpression::Epsilon(e) => backend.gen_epsilon(self.name, self.span, e), + RawTypedExpression::Literal(l) => backend.gen_literal(self.name, self.span, l), + RawTypedExpression::Cat(c) => backend.gen_cat(self.name, self.span, c), + RawTypedExpression::Alt(a) => backend.gen_alt(self.name, self.span, a), + RawTypedExpression::Fix(f) => backend.gen_fix(self.name, self.span, f), + RawTypedExpression::Variable(v) => backend.gen_variable(self.name, self.span, v), + } + } +} diff --git a/src/chomp/typed-old/mod.rs b/src/chomp/typed-old/mod.rs new file mode 100644 index 0000000..cddb05a --- /dev/null +++ b/src/chomp/typed-old/mod.rs @@ -0,0 +1,362 @@ +use std::hash; + +use proc_macro2::Span; + +use super::{ + ast, + set::{FirstSet, FlastSet}, + Name, +}; + +pub mod context; +pub mod error; +pub mod lower; + +mod infer; + +use self::error::{AltError, CatError}; +pub use self::infer::TypeInfer; + +#[derive(Debug, Default, Clone, Eq, Hash, PartialEq)] +pub struct Type { + nullable: bool, + first_set: FirstSet, + flast_set: FlastSet, +} + +impl Type { + pub const fn new(nullable: bool, first_set: FirstSet, flast_set: FlastSet) -> Self { + Self { + nullable, + first_set, + flast_set, + } + } + + pub fn of_str(s: &str) -> Self { + Self { + nullable: s.is_empty(), + first_set: FirstSet::of_str(s), + flast_set: FlastSet::default(), + } + } + + pub fn nullable(&self) -> bool { + self.nullable + } + + pub fn first_set(&self) -> &FirstSet { + &self.first_set + } + + pub fn flast_set(&self) -> &FlastSet { + &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 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), + } + } +} + +#[derive(Clone, Debug, Eq, Hash, PartialEq)] +pub struct Epsilon { + ty: Type, +} + +impl From for Epsilon { + fn from(_: ast::Epsilon) -> Self { + Self { + ty: Type::new(true, FirstSet::default(), FlastSet::default()), + } + } +} + +#[derive(Clone, Debug, Eq, Hash, PartialEq)] +pub struct Literal { + inner: ast::Literal, + ty: Type, +} + +impl Literal { + pub fn inner(&self) -> &ast::Literal { + &self.inner + } +} + +impl From for Literal { + fn from(inner: ast::Literal) -> Self { + let ty = Type::of_str(&inner); + Self { inner, ty } + } +} + +impl From for ast::Literal { + fn from(lit: Literal) -> Self { + lit.inner + } +} + +#[derive(Clone, Debug, Eq, Hash, PartialEq)] +pub struct Cat { + terms: Vec, + 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; + + type IntoIter = as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.terms.into_iter() + } +} + +#[derive(Clone, Debug, Eq, Hash, PartialEq)] +pub struct Alt { + terms: Vec, + 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; + + type IntoIter = as IntoIterator>::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.terms.into_iter() + } +} + +#[derive(Clone, Debug, Eq, Hash, PartialEq)] +pub struct Fix { + inner: Box, +} + +impl Fix { + pub fn unwrap(self) -> TypedExpression { + *self.inner + } +} + +#[derive(Clone, Debug, Eq, Hash, PartialEq)] +pub struct Variable { + inner: ast::Variable, + ty: Type, +} + +impl Variable { + pub fn index(&self) -> usize { + self.inner.index + } +} + +#[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), + Cat(Cat), + Alt(Alt), + Fix(Fix), + Variable(Variable), + Call(Call), + Lambda(Lambda), +} + +impl From for RawTypedExpression { + fn from(eps: Epsilon) -> Self { + Self::Epsilon(eps) + } +} + +impl From for RawTypedExpression { + fn from(lit: Literal) -> Self { + Self::Literal(lit) + } +} + +impl From for RawTypedExpression { + fn from(cat: Cat) -> Self { + Self::Cat(cat) + } +} + +impl From for RawTypedExpression { + fn from(alt: Alt) -> Self { + Self::Alt(alt) + } +} + +impl From for RawTypedExpression { + fn from(fix: Fix) -> Self { + Self::Fix(fix) + } +} + +impl From for RawTypedExpression { + fn from(var: Variable) -> Self { + Self::Variable(var) + } +} + +#[derive(Clone, Debug)] +pub struct TypedExpression { + inner: RawTypedExpression, + pub name: Option, + pub span: Option, +} + +impl PartialEq for TypedExpression { + fn eq(&self, other: &Self) -> bool { + self.inner == other.inner && self.name == other.name + } +} + +impl Eq for TypedExpression {} + +impl hash::Hash for TypedExpression { + fn hash(&self, state: &mut H) { + self.inner.hash(state); + self.name.hash(state); + } +} + +pub trait Typed { + fn get_type(&self) -> &Type; +} + +macro_rules! leaf_typed { + ($ty:ty, $field:ident) => { + impl Typed for $ty { + fn get_type(&self) -> &Type { + &self.$field + } + } + }; +} + +leaf_typed!(Epsilon, ty); +leaf_typed!(Literal, ty); +leaf_typed!(Cat, ty); +leaf_typed!(Alt, ty); +leaf_typed!(Variable, ty); + +impl Typed for Fix { + fn get_type(&self) -> &Type { + self.inner.get_type() + } +} + +impl Typed for TypedExpression { + fn get_type(&self) -> &Type { + match &self.inner { + RawTypedExpression::Epsilon(e) => e.get_type(), + RawTypedExpression::Literal(l) => l.get_type(), + RawTypedExpression::Cat(c) => c.get_type(), + RawTypedExpression::Alt(a) => a.get_type(), + RawTypedExpression::Fix(f) => f.get_type(), + RawTypedExpression::Variable(v) => v.get_type(), + } + } +} diff --git a/src/chomp/typed.rs b/src/chomp/typed.rs new file mode 100644 index 0000000..50d8155 --- /dev/null +++ b/src/chomp/typed.rs @@ -0,0 +1,274 @@ +use std::{borrow::BorrowMut, cell::RefCell, rc::Rc}; + +use super::{ + ast::{Lambda, Tree}, + Context, +}; + +#[derive(Clone, Debug)] +pub enum Constraint {} + +#[derive(Clone, Debug)] +pub enum CatCheckError {} + +#[derive(Clone, Debug)] +pub enum TypeError { + NeedGroundType(Rc), + CatCheck(CatCheckError), +} + +#[derive(Debug)] +pub struct AlgebraicType {} + +#[derive(Debug)] +pub enum GroundType { + Epsilon, + Bottom, + Character(char), + Variable, + Cat(RefCell>, RefCell>), + Alt(RefCell>, RefCell>), + Fix(RefCell>, RefCell>), +} + +#[derive(Clone, Debug)] +pub struct UnificationError(pub Rc, pub Rc); + +impl GroundType { + pub fn is_variable(&self) -> bool { + matches!(self, Self::Variable) + } + + pub fn substitute(self: &mut Rc, from: &Rc, into: &Rc) { + if Rc::ptr_eq(self, from) { + *self = into.clone(); + return; + } + + match self.as_ref() { + GroundType::Epsilon => {} + GroundType::Bottom => {} + GroundType::Character(_) => {} + GroundType::Variable => {} + GroundType::Cat(front, back) => { + front.borrow_mut().substitute(from, into); + back.borrow_mut().substitute(from, into); + } + GroundType::Alt(left, right) => { + left.borrow_mut().substitute(from, into); + right.borrow_mut().substitute(from, into); + } + GroundType::Fix(_, inner) => { + inner.borrow_mut().substitute(from, into); + } + } + } + + pub fn occurs_in(self: &Rc, other: &Rc) -> bool { + if Rc::ptr_eq(self, other) { + return true; + } + + match other.as_ref() { + GroundType::Epsilon => false, + GroundType::Bottom => false, + GroundType::Character(_) => false, + GroundType::Variable => false, + GroundType::Cat(front, back) => { + self.occurs_in(&front.borrow()) || self.occurs_in(&back.borrow()) + } + GroundType::Alt(left, right) => { + self.occurs_in(&left.borrow()) || self.occurs_in(&right.borrow()) + } + GroundType::Fix(arg, out) => { + self.occurs_in(&arg.borrow()) || self.occurs_in(&out.borrow()) + } + } + } + + pub fn unify<'a>( + self: &'a mut Rc, + other: &'a mut Rc, + ) -> Result<(), UnificationError> { + if Rc::ptr_eq(self, other) { + return Ok(()); + } + + match (self.as_ref(), other.as_ref()) { + (GroundType::Epsilon, GroundType::Epsilon) => Ok(()), + (GroundType::Bottom, GroundType::Bottom) => Ok(()), + (GroundType::Character(c), GroundType::Character(d)) if c == d => Ok(()), + (GroundType::Cat(front1, back1), GroundType::Cat(front2, back2)) => { + front1.borrow_mut().unify(&mut front2.borrow_mut())?; + back1.borrow_mut().unify(&mut back2.borrow_mut()) + } + (GroundType::Alt(left1, right1), GroundType::Alt(left2, right2)) => { + left1.borrow_mut().unify(&mut left2.borrow_mut())?; + right1.borrow_mut().unify(&mut right2.borrow_mut()) + } + (GroundType::Fix(arg1, out1), GroundType::Fix(arg2, out2)) => { + let new_arg = Rc::new(GroundType::Variable); + out1.borrow_mut().substitute(&arg1.borrow(), &new_arg); + out2.borrow_mut().substitute(&arg2.borrow(), &new_arg); + arg1.replace(new_arg.clone()); + arg2.replace(new_arg.clone()); + out1.borrow_mut().unify(&mut out2.borrow_mut()) + } + (GroundType::Variable, GroundType::Variable) => { + self = other; + Ok(()) + } + (GroundType::Variable, _) if !self.occurs_in(other) => { + self = other; + Ok(()) + } + (_, GroundType::Variable) if !other.occurs_in(self) => { + other = self; + Ok(()) + } + _ => Err(UnificationError( + Rc::new(self.clone().into()), + Rc::new(other.clone().into()), + )), + } + } +} + +/// Function type where the formal parameter is guarded in the body. +/// The actual parameter is checked in an unguarded context. +#[derive(Debug)] +pub struct GuardedFunction(pub RefCell>, pub RefCell>); + +#[derive(Debug)] +pub enum Type { + Ground(RefCell>), + /// Function type where the formal parameter is unguarded in the body. + /// The actual parameter is checked in a guarded context. + UnguardedFunction(RefCell>, RefCell>), + GuardedFunction(GuardedFunction), + Variable, +} + +impl Type { + pub fn try_as_ground<'a>( + self: &'a Rc, + ) -> Result<&'a RefCell>, &'a Rc> { + if let Type::Ground(g) = self.as_ref() { + Ok(g) + } else { + Err(self) + } + } + pub fn unify<'a>( + self: &'a mut Rc, + other: &'a mut Rc, + ) -> Result<(), UnificationError> { + if Rc::ptr_eq(self, other) { + return Ok(()); + } + + match self.as_ref() { + Type::Ground(g) => { + if let Type::Ground(o) = other.as_ref() { + g.borrow_mut().unify(&mut o.borrow_mut()) + } else { + Err(UnificationError(self.clone(), other.clone())) + } + } + Type::UnguardedFunction(arg, out) => { + if let Type::UnguardedFunction(o_arg, o_out) = other.as_ref() { + arg.borrow_mut().unify(&mut o_arg.borrow_mut())?; + out.borrow_mut().unify(&mut o_out.borrow_mut()) + } else { + Err(UnificationError(self.clone(), other.clone())) + } + } + Type::GuardedFunction(GuardedFunction(arg, out)) => { + if let Type::GuardedFunction(GuardedFunction(o_arg, o_out)) = other.as_ref() { + arg.borrow_mut().unify(&mut o_arg.borrow_mut())?; + out.borrow_mut().unify(&mut o_out.borrow_mut()) + } else { + Err(UnificationError(self.clone(), other.clone())) + } + } + Type::Variable => { + self = other; + Ok(()) + } + } + } +} + +impl From for Type { + fn from(ty: GroundType) -> Self { + Rc::new(ty).into() + } +} + +impl From> for Type { + fn from(ty: Rc) -> Self { + Self::Ground(RefCell::new(ty)) + } +} + +pub fn type_of(ctx: &mut Context, tree: &Rc) -> Result, TypeError> { + match tree.as_ref() { + Tree::Epsilon => Ok(ctx.type_interner.epsilon()), + Tree::Bottom => Ok(ctx.type_interner.bottom()), + Tree::Identity => { + let arg = Rc::new(GroundType::Variable); + Ok(Rc::new(Type::UnguardedFunction( + RefCell::new(arg), + RefCell::new(Rc::new(arg.into())), + ))) + } + Tree::Literal(l) => { + if let Some(c) = l.chars().next() { + Ok(ctx.type_interner.character(c)) + } else { + Ok(ctx.type_interner.epsilon()) + } + } + Tree::Variable => todo!(), // ctx.lookup_type_variable(tree), + Tree::Cat(front, back) => { + let mut front_ty: Rc = Rc::new(GroundType::Variable.into()); + let mut back_ty: Rc = Rc::new(GroundType::Variable.into()); + ctx.type_of(front)? + .unify(&mut front_ty) + .map_err(|_| todo!())?; + ctx.type_of(back)? + .unify(&mut back_ty) + .map_err(|_| todo!())?; + let front_ty = front_ty.try_as_ground().unwrap(); + let back_ty = back_ty.try_as_ground().unwrap(); + Ok(ctx + .type_interner + .cat(front_ty.borrow().clone(), back_ty.borrow().clone())) + } + Tree::Alt(left, right) => { + let mut left_ty: Rc = Rc::new(GroundType::Variable.into()); + let mut right_ty: Rc = Rc::new(GroundType::Variable.into()); + ctx.type_of(left)? + .unify(&mut left_ty) + .map_err(|_| todo!())?; + ctx.type_of(right)? + .unify(&mut right_ty) + .map_err(|_| todo!())?; + let left_ty = left_ty.try_as_ground().unwrap(); + let right_ty = right_ty.try_as_ground().unwrap(); + Ok(ctx + .type_interner + .alt(left_ty.borrow().clone(), right_ty.borrow().clone())) + } + Tree::Fix(inner) => { + let shape = Rc::new(Type::GuardedFunction(GuardedFunction(RefCell::new(Rc::new(GroundType::Variable)), RefCell::new(Rc::new(GroundType::Variable.into()))))); + ctx.type_of(inner)? + .unify(&mut shape) + .map_err(|_| todo!())?; + todo!() + } + Tree::Call(_, _) => todo!(), + Tree::Lambda(_) => todo!(), + Tree::Let(_, _, _) => todo!(), + } +} diff --git a/src/chomp/typed/context.rs b/src/chomp/typed/context.rs deleted file mode 100644 index f3263ce..0000000 --- a/src/chomp/typed/context.rs +++ /dev/null @@ -1,58 +0,0 @@ -use crate::chomp::ast::Variable; - -use super::Type; - -#[derive(Debug, Default)] -pub struct Context { - vars: Vec, - unguard_points: Vec, -} - -impl Context { - pub fn new() -> Self { - Self::default() - } - - pub fn depth(&self) -> usize { - self.vars.len() - } - - pub fn with_unguard R, R>(&mut self, f: F) -> R { - self.unguard_points.push(self.vars.len()); - let res = f(self); - self.unguard_points.pop(); - res - } - - pub fn get_variable_type(&self, var: Variable) -> Result<&Type, GetVariableError> { - self.vars - .iter() - .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) - }) - } - - pub fn with_variable_type R, R>(&mut self, ty: Type, f: F) -> R { - self.vars.push(ty); - let res = f(self); - self.vars.pop(); - res - } -} - -#[derive(Clone, Copy, Debug, Eq, PartialEq)] -pub enum GetVariableError { - FreeVariable, - GuardedVariable, -} diff --git a/src/chomp/typed/error.rs b/src/chomp/typed/error.rs deleted file mode 100644 index 5c1e21e..0000000 --- a/src/chomp/typed/error.rs +++ /dev/null @@ -1,164 +0,0 @@ -use std::{ - error::Error, - fmt::{self, Display}, -}; - -use proc_macro2::Span; - -use crate::chomp::{ast::Variable, Name}; - -use super::{context::GetVariableError, TypedExpression}; - -/// A type error when using a fix point variable. -#[derive(Debug)] -pub struct VariableError { - pub inner: GetVariableError, - pub var: Variable, - pub span: Option, - 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 { - GetVariableError::FreeVariable => write!(f, "unbound variable: "), - GetVariableError::GuardedVariable => write!(f, "usage of guarded variable: "), - }?; - - if let Some(name) = &self.name { - write!(f, "`{}`", name) - } else { - write!(f, "'{}", self.var.index) - } - } -} - -impl Error for VariableError {} - -#[derive(Debug)] -pub enum CatError { - FirstNullable { - expr: TypedExpression, - punct: Option, - }, - FirstFlastOverlap { - first: Vec, - punct: Option, - 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 Display for CatError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::FirstNullable { .. } => write!(f, "first part of concatenation is nullable"), - Self::FirstFlastOverlap { .. } => { - write!(f, "first set overlaps with preceding flast set") - } - } - } -} - -impl Error for CatError {} - -#[derive(Debug)] -pub enum AltError { - BothNullable { - left: Vec, - punct: Option, - right: TypedExpression, - }, - FirstOverlap { - left: Vec, - punct: Option, - 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 Display for AltError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::BothNullable { .. } => write!(f, "both branches are nullable"), - Self::FirstOverlap { .. } => write!(f, "first sets of both branches overlap"), - } - } -} - -impl Error for AltError {} - -#[derive(Debug)] -pub enum TypeError { - Cat(CatError), - Alt(AltError), - Variable(VariableError), -} - -impl From for TypeError { - fn from(other: CatError) -> Self { - Self::Cat(other) - } -} - -impl From for TypeError { - fn from(other: AltError) -> Self { - Self::Alt(other) - } -} - -impl From for TypeError { - fn from(other: VariableError) -> Self { - Self::Variable(other) - } -} - -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(), - } - } -} - -impl Display for TypeError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::Cat(e) => e.fmt(f), - Self::Alt(e) => e.fmt(f), - Self::Variable(e) => e.fmt(f), - } - } -} - -impl Error for TypeError {} diff --git a/src/chomp/typed/infer.rs b/src/chomp/typed/infer.rs deleted file mode 100644 index e2c2198..0000000 --- a/src/chomp/typed/infer.rs +++ /dev/null @@ -1,127 +0,0 @@ -use proc_macro2::Span; - -use crate::chomp::{Name, ast::{Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, substitute::Translate}, visit::{Folder, Visitable}}; - -use super::{Type, Typed, TypedExpression, context::Context, error::{TypeError, VariableError}}; - -#[derive(Debug)] -pub struct TypeInfer<'a> { - pub context: &'a mut Context, -} - -impl Folder for TypeInfer<'_> { - type Out = Result; - - fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { - Ok(TypedExpression { - inner: super::Epsilon::from(eps).into(), - name, - span, - }) - } - - fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out { - Ok(TypedExpression { - inner: super::Literal::from(lit).into(), - name, - span, - }) - } - - fn fold_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Out { - let first = cat.first.fold(self)?; - 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, - }) - }) - } - - fn fold_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Out { - let first = alt.first.fold(self)?; - let rest = alt - .rest - .into_iter() - .map(|(punct, term)| -> Result<_, TypeError> { Ok((punct, term.fold(self)?)) }) - .collect::, _>>()?; - Ok(TypedExpression { - inner: super::Alt::new(first, rest)?.into(), - name, - span, - }) - } - - fn fold_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Out { - let mut ty = Type::default(); - - loop { - let last = ty; - let res = self.context.with_variable_type(last.clone(), |context| { - fix.inner.clone().fold(&mut TypeInfer { context }) - })?; - ty = res.get_type().clone(); - - if last == ty { - return Ok(TypedExpression { - inner: super::Fix { - inner: Box::new(res), - } - .into(), - name, - span, - }); - } - } - } - - fn fold_variable( - &mut self, - name: Option, - span: Option, - var: Variable, - ) -> Self::Out { - let ty = match self.context.get_variable_type(var) { - Ok(ty) => ty.clone(), - Err(inner) => { - return Err(VariableError { - inner, - var, - span, - name, - } - .into()) - } - }; - Ok(TypedExpression { - inner: super::Variable { inner: var, ty }.into(), - name, - span, - }) - } - - 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_lambda( - &mut self, - _name: Option, - _span: Option, - _lambda: Lambda, - ) -> Self::Out { - unimplemented!() - } -} diff --git a/src/chomp/typed/lower.rs b/src/chomp/typed/lower.rs deleted file mode 100644 index 37589a1..0000000 --- a/src/chomp/typed/lower.rs +++ /dev/null @@ -1,41 +0,0 @@ -use proc_macro2::Span; - -use crate::chomp::Name; - -use super::{Alt, Cat, Epsilon, Fix, Literal, RawTypedExpression, TypedExpression, Variable}; - -pub trait Backend: Default { - type Id; - type Code; - - fn gen_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Id; - - fn gen_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Id; - - fn gen_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Id; - - fn gen_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Id; - - fn gen_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Id; - - fn gen_variable(&mut self, name: Option, span: Option, var: Variable) -> Self::Id; - - fn emit_code(self, name: Option, span: Option, id: Self::Id) -> Self::Code; -} - -pub trait GenerateCode { - fn gen(self, backend: &mut B) -> B::Id; -} - -impl GenerateCode for TypedExpression { - fn gen(self, backend: &mut B) -> B::Id { - match self.inner { - RawTypedExpression::Epsilon(e) => backend.gen_epsilon(self.name, self.span, e), - RawTypedExpression::Literal(l) => backend.gen_literal(self.name, self.span, l), - RawTypedExpression::Cat(c) => backend.gen_cat(self.name, self.span, c), - RawTypedExpression::Alt(a) => backend.gen_alt(self.name, self.span, a), - RawTypedExpression::Fix(f) => backend.gen_fix(self.name, self.span, f), - RawTypedExpression::Variable(v) => backend.gen_variable(self.name, self.span, v), - } - } -} diff --git a/src/chomp/typed/mod.rs b/src/chomp/typed/mod.rs deleted file mode 100644 index cddb05a..0000000 --- a/src/chomp/typed/mod.rs +++ /dev/null @@ -1,362 +0,0 @@ -use std::hash; - -use proc_macro2::Span; - -use super::{ - ast, - set::{FirstSet, FlastSet}, - Name, -}; - -pub mod context; -pub mod error; -pub mod lower; - -mod infer; - -use self::error::{AltError, CatError}; -pub use self::infer::TypeInfer; - -#[derive(Debug, Default, Clone, Eq, Hash, PartialEq)] -pub struct Type { - nullable: bool, - first_set: FirstSet, - flast_set: FlastSet, -} - -impl Type { - pub const fn new(nullable: bool, first_set: FirstSet, flast_set: FlastSet) -> Self { - Self { - nullable, - first_set, - flast_set, - } - } - - pub fn of_str(s: &str) -> Self { - Self { - nullable: s.is_empty(), - first_set: FirstSet::of_str(s), - flast_set: FlastSet::default(), - } - } - - pub fn nullable(&self) -> bool { - self.nullable - } - - pub fn first_set(&self) -> &FirstSet { - &self.first_set - } - - pub fn flast_set(&self) -> &FlastSet { - &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 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), - } - } -} - -#[derive(Clone, Debug, Eq, Hash, PartialEq)] -pub struct Epsilon { - ty: Type, -} - -impl From for Epsilon { - fn from(_: ast::Epsilon) -> Self { - Self { - ty: Type::new(true, FirstSet::default(), FlastSet::default()), - } - } -} - -#[derive(Clone, Debug, Eq, Hash, PartialEq)] -pub struct Literal { - inner: ast::Literal, - ty: Type, -} - -impl Literal { - pub fn inner(&self) -> &ast::Literal { - &self.inner - } -} - -impl From for Literal { - fn from(inner: ast::Literal) -> Self { - let ty = Type::of_str(&inner); - Self { inner, ty } - } -} - -impl From for ast::Literal { - fn from(lit: Literal) -> Self { - lit.inner - } -} - -#[derive(Clone, Debug, Eq, Hash, PartialEq)] -pub struct Cat { - terms: Vec, - 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; - - type IntoIter = as IntoIterator>::IntoIter; - - fn into_iter(self) -> Self::IntoIter { - self.terms.into_iter() - } -} - -#[derive(Clone, Debug, Eq, Hash, PartialEq)] -pub struct Alt { - terms: Vec, - 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; - - type IntoIter = as IntoIterator>::IntoIter; - - fn into_iter(self) -> Self::IntoIter { - self.terms.into_iter() - } -} - -#[derive(Clone, Debug, Eq, Hash, PartialEq)] -pub struct Fix { - inner: Box, -} - -impl Fix { - pub fn unwrap(self) -> TypedExpression { - *self.inner - } -} - -#[derive(Clone, Debug, Eq, Hash, PartialEq)] -pub struct Variable { - inner: ast::Variable, - ty: Type, -} - -impl Variable { - pub fn index(&self) -> usize { - self.inner.index - } -} - -#[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), - Cat(Cat), - Alt(Alt), - Fix(Fix), - Variable(Variable), - Call(Call), - Lambda(Lambda), -} - -impl From for RawTypedExpression { - fn from(eps: Epsilon) -> Self { - Self::Epsilon(eps) - } -} - -impl From for RawTypedExpression { - fn from(lit: Literal) -> Self { - Self::Literal(lit) - } -} - -impl From for RawTypedExpression { - fn from(cat: Cat) -> Self { - Self::Cat(cat) - } -} - -impl From for RawTypedExpression { - fn from(alt: Alt) -> Self { - Self::Alt(alt) - } -} - -impl From for RawTypedExpression { - fn from(fix: Fix) -> Self { - Self::Fix(fix) - } -} - -impl From for RawTypedExpression { - fn from(var: Variable) -> Self { - Self::Variable(var) - } -} - -#[derive(Clone, Debug)] -pub struct TypedExpression { - inner: RawTypedExpression, - pub name: Option, - pub span: Option, -} - -impl PartialEq for TypedExpression { - fn eq(&self, other: &Self) -> bool { - self.inner == other.inner && self.name == other.name - } -} - -impl Eq for TypedExpression {} - -impl hash::Hash for TypedExpression { - fn hash(&self, state: &mut H) { - self.inner.hash(state); - self.name.hash(state); - } -} - -pub trait Typed { - fn get_type(&self) -> &Type; -} - -macro_rules! leaf_typed { - ($ty:ty, $field:ident) => { - impl Typed for $ty { - fn get_type(&self) -> &Type { - &self.$field - } - } - }; -} - -leaf_typed!(Epsilon, ty); -leaf_typed!(Literal, ty); -leaf_typed!(Cat, ty); -leaf_typed!(Alt, ty); -leaf_typed!(Variable, ty); - -impl Typed for Fix { - fn get_type(&self) -> &Type { - self.inner.get_type() - } -} - -impl Typed for TypedExpression { - fn get_type(&self) -> &Type { - match &self.inner { - RawTypedExpression::Epsilon(e) => e.get_type(), - RawTypedExpression::Literal(l) => l.get_type(), - RawTypedExpression::Cat(c) => c.get_type(), - RawTypedExpression::Alt(a) => a.get_type(), - RawTypedExpression::Fix(f) => f.get_type(), - RawTypedExpression::Variable(v) => v.get_type(), - } - } -} -- cgit v1.2.3