diff options
Diffstat (limited to 'src/chomp/check')
-rw-r--r-- | src/chomp/check/check.rs | 81 | ||||
-rw-r--r-- | src/chomp/check/closed.rs | 50 | ||||
-rw-r--r-- | src/chomp/check/deepen.rs | 47 | ||||
-rw-r--r-- | src/chomp/check/infer.rs | 92 | ||||
-rw-r--r-- | src/chomp/check/inline.rs | 349 | ||||
-rw-r--r-- | src/chomp/check/mod.rs | 17 | ||||
-rw-r--r-- | src/chomp/check/shallow.rs | 47 | ||||
-rw-r--r-- | src/chomp/check/spanning.rs | 59 | ||||
-rw-r--r-- | src/chomp/check/substitute.rs | 77 |
9 files changed, 0 insertions, 819 deletions
diff --git a/src/chomp/check/check.rs b/src/chomp/check/check.rs deleted file mode 100644 index 8729565..0000000 --- a/src/chomp/check/check.rs +++ /dev/null @@ -1,81 +0,0 @@ -use super::{ - super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - context::Context, - error::TypeError, - typed::{self, TypedExpression}, - visit::{Folder, Visitable, Visitor}, - }, - TypeInfer, -}; - -#[derive(Debug)] -pub struct TypeCheck<'a> { - pub context: &'a mut Context, -} - -impl Folder for TypeCheck<'_> { - type Out = Result<TypedExpression, TypeError>; - - fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out { - Ok(typed::Epsilon::from(eps).into()) - } - - fn fold_literal(&mut self, lit: Literal) -> Self::Out { - Ok(typed::Literal::from(lit).into()) - } - - fn fold_cat(&mut self, cat: Cat) -> Self::Out { - let ty = TypeInfer { - context: self.context, - } - .visit_cat(&cat)?; - let fst = cat.fst.fold(self)?; - let snd = cat.snd; - let snd = self - .context - .with_unguard(|context| snd.fold(&mut TypeCheck { context }))?; - - Ok(typed::Cat::new(fst, cat.punct, snd, ty).into()) - } - - fn fold_alt(&mut self, alt: Alt) -> Self::Out { - let ty = TypeInfer { - context: self.context, - } - .visit_alt(&alt)?; - let left = alt.left.fold(self)?; - let right = alt.right.fold(self)?; - - Ok(typed::Alt::new(left, alt.punct, right, ty).into()) - } - - fn fold_fix(&mut self, fix: Fix) -> Self::Out { - let ty = TypeInfer { - context: self.context, - } - .visit_fix(&fix)?; - let inner = fix.inner; - let inner = self - .context - .with_variable_type(ty.clone(), |context| inner.fold(&mut TypeCheck { context }))?; - - Ok(typed::Fix::new(fix.arg, inner, fix.span, ty).into()) - } - - fn fold_variable(&mut self, var: Variable) -> Self::Out { - let ty = TypeInfer { - context: self.context, - } - .visit_variable(&var)?; - Ok(typed::Variable::new(var, ty).into()) - } - - fn fold_parameter(&mut self, _param: Parameter) -> Self::Out { - todo!() - } - - fn fold_call(&mut self, _call: Call) -> Self::Out { - todo!() - } -} diff --git a/src/chomp/check/closed.rs b/src/chomp/check/closed.rs deleted file mode 100644 index 07ef7ac..0000000 --- a/src/chomp/check/closed.rs +++ /dev/null @@ -1,50 +0,0 @@ -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - visit::{Visitable, Visitor}, -}; - -/// Test if term is closed for a context with `depth` variables. -#[derive(Copy, Clone, Debug, Default)] -pub struct Closed { - depth: usize, - params: usize, -} - -impl Visitor for Closed { - type Out = bool; - - fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out { - true - } - - fn visit_literal(&mut self, _lit: &Literal) -> Self::Out { - true - } - - fn visit_cat(&mut self, cat: &Cat) -> Self::Out { - cat.first().visit(self) && cat.second().visit(self) - } - - fn visit_alt(&mut self, alt: &Alt) -> Self::Out { - alt.left().visit(self) && alt.right().visit(self) - } - - fn visit_fix(&mut self, fix: &Fix) -> Self::Out { - self.depth += 1; - let res = fix.inner().visit(self); - self.depth -= 1; - res - } - - fn visit_variable(&mut self, var: &Variable) -> Self::Out { - var.index() < self.depth - } - - fn visit_parameter(&mut self, param: &Parameter) -> Self::Out { - param.index() < self.params - } - - fn visit_call(&mut self, call: &Call) -> Self::Out { - call.args().iter().all(|arg| arg.visit(self)) - } -} diff --git a/src/chomp/check/deepen.rs b/src/chomp/check/deepen.rs deleted file mode 100644 index b9f606d..0000000 --- a/src/chomp/check/deepen.rs +++ /dev/null @@ -1,47 +0,0 @@ -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - visit::{Mapper, Visitable}, -}; - -#[derive(Clone, Copy, Debug, Default)] -pub struct DeepenVars { - depth: usize, -} - -impl Mapper for DeepenVars { - type Out = (); - - fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {} - - fn map_literal(&mut self, _: &mut Literal) -> Self::Out {} - - fn map_cat(&mut self, cat: &mut Cat) -> Self::Out { - cat.first_mut().map(self); - cat.second_mut().map(self); - } - - fn map_alt(&mut self, alt: &mut Alt) -> Self::Out { - alt.left_mut().map(self); - alt.right_mut().map(self); - } - - fn map_fix(&mut self, fix: &mut Fix) -> Self::Out { - self.depth += 1; - fix.inner_mut().map(self); - self.depth -= 1; - } - - fn map_variable(&mut self, bind: &mut Variable) -> Self::Out { - if bind.index() >= self.depth { - *bind.index_mut() += 1; - } - } - - fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {} - - fn map_call(&mut self, call: &mut Call) -> Self::Out { - for arg in call.args_mut() { - arg.map(self); - } - } -} diff --git a/src/chomp/check/infer.rs b/src/chomp/check/infer.rs deleted file mode 100644 index 941ddba..0000000 --- a/src/chomp/check/infer.rs +++ /dev/null @@ -1,92 +0,0 @@ -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - context::Context, - error::{AltError, CatError, FixError, TypeError}, - set::{FirstSet, FlastSet}, - typed::Type, - visit::{Visitable, Visitor}, -}; - -#[derive(Debug)] -pub struct TypeInfer<'a> { - pub context: &'a mut Context, -} - -impl Visitor for TypeInfer<'_> { - type Out = Result<Type, TypeError>; - - fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out { - Ok(Type::new(true, FirstSet::default(), FlastSet::default())) - } - - fn visit_literal(&mut self, lit: &Literal) -> Self::Out { - Ok(Type::of_str(&lit.value())) - } - - fn visit_cat(&mut self, cat: &Cat) -> Self::Out { - let first = cat.first().visit(self)?; - let second = self - .context - .with_unguard(|context| cat.second().visit(&mut TypeInfer { context }))?; - - if first.nullable() { - Err(TypeError::Cat(CatError::FirstNullable(cat.clone()))) - } else if !first - .flast_set() - .intersect_first(second.first_set()) - .is_empty() - { - Err(TypeError::Cat(CatError::FirstFlastOverlap(cat.clone()))) - } else { - Ok(first.cat(second)) - } - } - - fn visit_alt(&mut self, alt: &Alt) -> Self::Out { - let left = alt.left().visit(self)?; - let right = alt.right().visit(self)?; - - if left.nullable() && right.nullable() { - Err(TypeError::Alt(AltError::BothNullable(alt.clone()))) - } else if !left.first_set().intersect(right.first_set()).is_empty() { - Err(TypeError::Alt(AltError::FirstOverlap(alt.clone()))) - } else { - Ok(left.alt(right)) - } - } - - fn visit_fix(&mut self, fix: &Fix) -> Self::Out { - let mut res = Type::default(); - let mut last = None; - - while last.map(|r| r != res).unwrap_or(true) { - last = Some(res); - res = self - .context - .with_variable_type(last.as_ref().cloned().unwrap(), |context| { - fix.inner().visit(&mut TypeInfer { context }) - }) - .map_err(|e| { - TypeError::Fix(FixError( - fix.clone(), - last.as_ref().cloned().unwrap(), - Box::new(e), - )) - })?; - } - - Ok(res) - } - - fn visit_variable(&mut self, var: &Variable) -> Self::Out { - Ok(self.context.get_variable_type(&var)?.clone()) - } - - fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out { - todo!() - } - - fn visit_call(&mut self, _call: &Call) -> Self::Out { - todo!() - } -} diff --git a/src/chomp/check/inline.rs b/src/chomp/check/inline.rs deleted file mode 100644 index da501f1..0000000 --- a/src/chomp/check/inline.rs +++ /dev/null @@ -1,349 +0,0 @@ -use super::{ - super::{ - ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Function, Literal, Parameter, Variable}, - error::SubstituteError, - visit::{Folder, Visitable}, - }, - SubstituteParams, -}; - -#[derive(Clone, Debug)] -pub struct InlineCalls { - function: Function, -} - -impl InlineCalls { - pub fn new(function: Function) -> Self { - Self { function } - } -} - -impl Folder for InlineCalls { - type Out = Result<Expression, SubstituteError>; - - fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out { - Ok(eps.into()) - } - - fn fold_literal(&mut self, lit: Literal) -> Self::Out { - Ok(lit.into()) - } - - fn fold_cat(&mut self, mut cat: Cat) -> Self::Out { - cat.fst = Box::new(cat.fst.fold(self)?); - cat.snd = Box::new(cat.snd.fold(self)?); - Ok(cat.into()) - } - - fn fold_alt(&mut self, mut alt: Alt) -> Self::Out { - alt.left = Box::new(alt.left.fold(self)?); - alt.right = Box::new(alt.right.fold(self)?); - Ok(alt.into()) - } - - fn fold_fix(&mut self, mut fix: Fix) -> Self::Out { - fix.inner = Box::new(fix.inner.fold(self)?); - Ok(fix.into()) - } - - fn fold_variable(&mut self, var: Variable) -> Self::Out { - Ok(var.into()) - } - - fn fold_parameter(&mut self, param: Parameter) -> Self::Out { - Ok(param.into()) - } - - fn fold_call(&mut self, mut call: Call) -> Self::Out { - call.args = call - .args - .into_iter() - .map(|arg| arg.fold(self)) - .collect::<Result<_, _>>()?; - - if call.name != self.function.name { - Ok(call.into()) - } else if call.args.len() != self.function.params { - Err(SubstituteError::WrongArgCount { - call, - expected: self.function.params, - }) - } else { - self.function - .expr - .clone() - .fold(&mut SubstituteParams::new(call.args)) - } - } -} - -#[cfg(test)] -mod tests { - use crate::chomp::Name; - - use super::*; - - fn opt() -> Function { - Function::new( - Name::Spanless("opt".to_string()), - 1, - Expression::Alt(Alt::new( - Expression::Epsilon(None), - None, - Parameter::new(Name::Spanless("x".to_string()), 0).into(), - )), - None, - ) - } - - #[test] - fn test_inline_absent() { - let expr = Epsilon::default(); - let inlined = expr.fold(&mut InlineCalls::new(opt())); - assert_eq!(inlined, Ok(Epsilon::default().into())) - } - - #[test] - fn test_inline_in_fix() { - let expr = Fix::new( - Name::Spanless("rec".to_string()), - Call::new( - Name::Spanless("opt".to_string()), - vec![Variable::new(Name::Spanless("rec".to_string()), 0).into()], - None, - ) - .into(), - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(opt())); - assert_eq!( - inlined, - Ok(Fix::new( - Name::Spanless("rec".to_string()), - Alt::new( - Epsilon::default().into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into() - ) - .into(), - None - ) - .into()) - ) - } - - #[test] - fn test_inline_deepens_vars() { - let function = Function::new( - Name::Spanless("plus".into()), - 1, - Fix::new( - Name::Spanless("rec".to_string()), - Cat::new( - Parameter::new(Name::Spanless("x".to_string()), 0).into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into(), - ) - .into(), - None, - ) - .into(), - None, - ); - let expr = Fix::new( - Name::Spanless("var".to_string()), - Call::new( - Name::Spanless("plus".into()), - vec![Variable::new(Name::Spanless("var".to_string()), 0).into()], - None, - ) - .into(), - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(function)); - assert_eq!( - inlined, - Ok(Fix::new( - Name::Spanless("var".to_string()), - Fix::new( - Name::Spanless("rec".to_string()), - Cat::new( - Variable::new(Name::Spanless("var".to_string()), 1).into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into(), - ) - .into(), - None, - ) - .into(), - None - ) - .into()) - ) - } - - #[test] - fn test_inline_resets_vars() { - let function = Function::new( - Name::Spanless("plus".into()), - 1, - Cat::new( - Fix::new( - Name::Spanless("rec".to_string()), - Epsilon::default().into(), - None, - ) - .into(), - None, - Parameter::new(Name::Spanless("x".to_string()), 0).into(), - ) - .into(), - None, - ); - let expr = Fix::new( - Name::Spanless("var".to_string()), - Call::new( - Name::Spanless("plus".into()), - vec![Variable::new(Name::Spanless("var".to_string()), 0).into()], - None, - ) - .into(), - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(function)); - assert_eq!( - inlined, - Ok(Fix::new( - Name::Spanless("var".to_string()), - Cat::new( - Fix::new( - Name::Spanless("rec".to_string()), - Epsilon::default().into(), - None, - ) - .into(), - None, - Variable::new(Name::Spanless("var".to_string()), 0).into(), - ) - .into(), - None - ) - .into()) - ) - } - - #[test] - fn test_inline_double_subst() { - let expr = Call::new( - Name::Spanless("opt".to_string()), - vec![Call::new( - Name::Spanless("opt".to_string()), - vec![Literal::Spanless("x".to_string()).into()], - None, - ) - .into()], - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(opt())); - assert_eq!( - inlined, - Ok(Alt::new( - Epsilon::default().into(), - None, - Alt::new( - Epsilon::default().into(), - None, - Literal::Spanless("x".to_string()).into() - ) - .into() - ) - .into()) - ) - } - - #[test] - fn test_inline_call_args() { - let expr = Fix::new( - Name::Spanless("rec".to_string()), - Cat::new( - Literal::Spanless("a".to_string()).into(), - None, - Call::new( - Name::Spanless("opt".to_string()), - vec![Cat::new( - Cat::new( - Literal::Spanless("a".to_string()).into(), - None, - Fix::new( - Name::Spanless("star".to_string()), - Call::new( - Name::Spanless("opt".to_string()), - vec![Cat::new( - Literal::Spanless(" ".to_string()).into(), - None, - Variable::new(Name::Spanless("star".to_string()), 0).into(), - ) - .into()], - None, - ) - .into(), - None, - ) - .into(), - ) - .into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into(), - ) - .into()], - None, - ) - .into(), - ) - .into(), - None, - ); - let inlined = expr.fold(&mut InlineCalls::new(opt())); - assert_eq!(inlined, - Ok(Fix::new( - Name::Spanless("rec".to_string()), - Cat::new( - Literal::Spanless("a".to_string()).into(), - None, - Alt::new( - Epsilon::default().into(), - None, - Cat::new( - Cat::new( - Literal::Spanless("a".to_string()).into(), - None, - Fix::new( - Name::Spanless("star".to_string()), - Alt::new( - Epsilon::default().into(), - None, - Cat::new( - Literal::Spanless(" ".to_string()).into(), - None, - Variable::new(Name::Spanless("star".to_string()), 0).into(), - ) - .into() - ) - .into(), - None, - ) - .into(), - ) - .into(), - None, - Variable::new(Name::Spanless("rec".to_string()), 0).into(), - ) - .into(), - ) - .into(), - ) - .into(), - None, - ).into())) - } -} diff --git a/src/chomp/check/mod.rs b/src/chomp/check/mod.rs deleted file mode 100644 index c9aeda4..0000000 --- a/src/chomp/check/mod.rs +++ /dev/null @@ -1,17 +0,0 @@ -mod check; -mod closed; -mod deepen; -mod infer; -mod inline; -mod shallow; -mod spanning; -mod substitute; - -pub use check::TypeCheck; -pub use closed::Closed; -pub use deepen::DeepenVars; -pub use infer::TypeInfer; -pub use inline::InlineCalls; -pub use shallow::ShallowVars; -pub use spanning::Spanning; -pub use substitute::SubstituteParams; diff --git a/src/chomp/check/shallow.rs b/src/chomp/check/shallow.rs deleted file mode 100644 index e5cc1a1..0000000 --- a/src/chomp/check/shallow.rs +++ /dev/null @@ -1,47 +0,0 @@ -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - visit::{Mapper, Visitable}, -}; - -#[derive(Clone, Copy, Debug, Default)] -pub struct ShallowVars { - depth: usize, -} - -impl Mapper for ShallowVars { - type Out = (); - - fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {} - - fn map_literal(&mut self, _: &mut Literal) -> Self::Out {} - - fn map_cat(&mut self, cat: &mut Cat) -> Self::Out { - cat.first_mut().map(self); - cat.second_mut().map(self); - } - - fn map_alt(&mut self, alt: &mut Alt) -> Self::Out { - alt.left_mut().map(self); - alt.right_mut().map(self); - } - - fn map_fix(&mut self, fix: &mut Fix) -> Self::Out { - self.depth += 1; - fix.inner_mut().map(self); - self.depth -= 1; - } - - fn map_variable(&mut self, bind: &mut Variable) -> Self::Out { - if bind.index() > self.depth { - *bind.index_mut() -= 1; - } - } - - fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {} - - fn map_call(&mut self, call: &mut Call) -> Self::Out { - for arg in call.args_mut() { - arg.map(self); - } - } -} diff --git a/src/chomp/check/spanning.rs b/src/chomp/check/spanning.rs deleted file mode 100644 index 59c3811..0000000 --- a/src/chomp/check/spanning.rs +++ /dev/null @@ -1,59 +0,0 @@ -use proc_macro2::Span; - -use super::super::{ - ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable}, - visit::{Visitable, Visitor}, -}; - -#[derive(Clone, Copy, Debug)] -pub struct Spanning; - -impl Visitor for Spanning { - type Out = Option<Span>; - - fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out { - eps.map(|e| e.span) - } - - fn visit_literal(&mut self, lit: &Literal) -> Self::Out { - lit.span() - } - - fn visit_cat(&mut self, cat: &Cat) -> Self::Out { - let fst = cat.first().visit(self); - let snd = cat.second().visit(self); - - match (fst, snd) { - (None, snd) => snd, - (Some(fst), None) => Some(fst), - (Some(fst), Some(snd)) => fst.join(snd), - } - } - - fn visit_alt(&mut self, alt: &Alt) -> Self::Out { - let left = alt.left().visit(self); - let right = alt.right().visit(self); - - match (left, right) { - (None, right) => right, - (Some(left), None) => Some(left), - (Some(left), Some(right)) => left.join(right), - } - } - - fn visit_fix(&mut self, fix: &Fix) -> Self::Out { - fix.span() - } - - fn visit_variable(&mut self, var: &Variable) -> Self::Out { - var.name().span() - } - - fn visit_parameter(&mut self, param: &Parameter) -> Self::Out { - param.name().span() - } - - fn visit_call(&mut self, call: &Call) -> Self::Out { - call.span() - } -} diff --git a/src/chomp/check/substitute.rs b/src/chomp/check/substitute.rs deleted file mode 100644 index 32595b1..0000000 --- a/src/chomp/check/substitute.rs +++ /dev/null @@ -1,77 +0,0 @@ -use super::{ - super::{ - ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Literal, Parameter, Variable}, - error::SubstituteError, - visit::{Folder, Visitable}, - }, - DeepenVars, ShallowVars, -}; - -#[derive(Clone, Debug)] -pub struct SubstituteParams { - params: Vec<Expression>, -} - -impl SubstituteParams { - pub fn new(params: Vec<Expression>) -> Self { - Self { params } - } -} - -impl Folder for SubstituteParams { - type Out = Result<Expression, SubstituteError>; - - fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out { - Ok(eps.into()) - } - - fn fold_literal(&mut self, lit: Literal) -> Self::Out { - Ok(lit.into()) - } - - fn fold_cat(&mut self, mut cat: Cat) -> Self::Out { - cat.fst = Box::new(cat.fst.fold(self)?); - cat.snd = Box::new(cat.snd.fold(self)?); - Ok(cat.into()) - } - - fn fold_alt(&mut self, mut alt: Alt) -> Self::Out { - alt.left = Box::new(alt.left.fold(self)?); - alt.right = Box::new(alt.right.fold(self)?); - Ok(alt.into()) - } - - fn fold_fix(&mut self, mut fix: Fix) -> Self::Out { - for param in &mut self.params { - param.map(&mut DeepenVars::default()); - } - - fix.inner = Box::new(fix.inner.fold(self)?); - - for param in &mut self.params { - param.map(&mut ShallowVars::default()); - } - - Ok(fix.into()) - } - - fn fold_variable(&mut self, var: Variable) -> Self::Out { - Ok(Expression::Variable(var)) - } - - fn fold_call(&mut self, mut call: Call) -> Self::Out { - call.args = call - .args - .into_iter() - .map(|arg| arg.fold(self)) - .collect::<Result<_, _>>()?; - Ok(call.into()) - } - - fn fold_parameter(&mut self, param: Parameter) -> Self::Out { - self.params - .get(param.index()) - .cloned() - .ok_or(SubstituteError::FreeParameter(param)) - } -} |