From dc10a278cca74d737e4af0fe034a1caa8abb291d Mon Sep 17 00:00:00 2001 From: Greg Brown Date: Wed, 6 Jan 2021 14:56:11 +0000 Subject: Restructure code base to separate compilation phases. --- src/ast/convert.rs | 153 ----- src/ast/mod.rs | 1647 ---------------------------------------------------- src/ast/typed.rs | 284 --------- 3 files changed, 2084 deletions(-) delete mode 100644 src/ast/convert.rs delete mode 100644 src/ast/mod.rs delete mode 100644 src/ast/typed.rs (limited to 'src/ast') diff --git a/src/ast/convert.rs b/src/ast/convert.rs deleted file mode 100644 index 8051c90..0000000 --- a/src/ast/convert.rs +++ /dev/null @@ -1,153 +0,0 @@ -use std::borrow::Borrow; -use std::collections::HashMap; -use std::hash::Hash; - -use super::Term; - -#[derive(Debug, Default)] -/// The variable context for converting a concrete syntax tree to an abstract -/// one. -/// -/// There are two name scopes in a context. Bindings are used by fixed points. -/// Variables are formal parameters of macros. -pub struct Context { - bindings: Vec, - variables: HashMap, -} - -impl Context { - /// Creates a new variable context. No names are bound. - pub fn new() -> Self { - Self::default() - } - - /// Returns [`Some`] index of a binding `name`. - /// - /// # Errors - /// Returns [`None`] if `name.is_empty()` or if `name` is unbound. - /// - /// # Examples - /// ``` - /// use chomp::ast::convert::Context; - /// - /// let mut context = Context::new(); - /// assert_eq!(context.get_binding("x"), None); - /// - /// context.with_binding("x".to_owned(), |c| { - /// assert_eq!(c.get_binding("x"), Some(0)); - /// - /// c.with_binding("y".to_owned(), |c| { - /// assert_eq!(c.get_binding("x"), Some(1)); - /// }) - /// }); - /// - /// assert_eq!(context.get_binding("x"), None); - /// ``` - pub fn get_binding>(&self, name: &T) -> Option { - let mut iter = self.bindings.iter(); - let mut pos = 0; - - if name == "" { - return None; - } - - while let Some(var) = iter.next_back() { - if T::eq(&name, &var) { - return Some(pos); - } else { - pos += 1; - } - } - - None - } - - /// Adds a binding `name` for the duration of the function `f`. - /// - /// # Panics - /// If `name.is_empty()`. - /// - /// # Examples - /// ``` - /// use chomp::ast::convert::Context; - /// - /// let mut context = Context::new(); - /// assert_eq!(context.get_binding("x"), None); - /// - /// context.with_binding("x".to_owned(), |c| { - /// assert_eq!(c.get_binding("x"), Some(0)); - /// }); - /// - /// assert_eq!(context.get_binding("x"), None); - /// ``` - pub fn with_binding T, T>(&mut self, name: String, f: F) -> T { - if name.is_empty() { - panic!() - } - - self.bindings.push(name); - let res = f(self); - self.bindings.pop(); - res - } - - /// Returns [`Some`] index of a variable `name`. - /// - /// # Errors - /// If `name == "".to_owned().borrow()` or `name` is unbound. - /// - /// # Examples - /// ``` - /// use chomp::ast::convert::Context; - /// - /// let mut ctx = Context::new(); - /// assert_eq!(ctx.get_variable("x"), None); - /// - /// ctx.set_variables(vec!["x".to_owned(), "y".to_owned()]); - /// assert_eq!(ctx.get_variable("x"), Some(0)); - /// assert_eq!(ctx.get_variable("y"), Some(1)); - /// - /// ctx.set_variables(vec![]); - /// assert_eq!(ctx.get_variable("x"), None); - /// ``` - pub fn get_variable(&self, name: &T) -> Option - where - String: Borrow, - { - if name == "".to_owned().borrow() { - return None; - } - - self.variables.get(name).copied() - } - - /// Reassigns all variable indices based off of their position in `args`. - /// - /// # Examples - /// ``` - /// use chomp::ast::convert::Context; - /// - /// let mut ctx = Context::new(); - /// assert_eq!(ctx.get_variable("x"), None); - /// - /// ctx.set_variables(vec!["x".to_owned(), "y".to_owned()]); - /// assert_eq!(ctx.get_variable("x"), Some(0)); - /// assert_eq!(ctx.get_variable("y"), Some(1)); - /// - /// ctx.set_variables(vec![]); - /// assert_eq!(ctx.get_variable("x"), None); - /// ``` - pub fn set_variables>(&mut self, args: I) { - self.variables = args - .into_iter() - .enumerate() - .map(|(index, name)| (name, index)) - .collect(); - } -} - -/// Used to convert a concrete term into an abstract term. -pub trait Convert { - /// Performs the conversion. - fn convert(&self, context: &mut Context) -> Term; -} diff --git a/src/ast/mod.rs b/src/ast/mod.rs deleted file mode 100644 index b4baa9d..0000000 --- a/src/ast/mod.rs +++ /dev/null @@ -1,1647 +0,0 @@ -use self::typed::{FirstContext, FlastContext, NullContext}; -use proc_macro2::{Span, TokenStream, TokenTree}; -use quote::{format_ident, quote}; -use std::collections::{BTreeSet, HashMap}; -use std::error::Error; -use std::fmt::{self, Display}; -use syn::{Ident, LitStr, Token}; - -pub mod convert; -pub mod typed; - -/// A literal epsilon. -pub type Epsilon = Token![_]; - -/// A literal string. -pub type Literal = LitStr; - -/// The concatenation of two terms. -#[derive(Clone, Debug)] -pub struct Cat { - fst: Box, - punct: Token![.], - snd: Box, -} - -impl Cat { - /// Creates a new `Cat` from the two sub-terms and the joining punctuation. - pub fn new(fst: Term, punct: Token![.], snd: Term) -> Self { - Self { - fst: Box::new(fst), - punct, - snd: Box::new(snd), - } - } -} - -/// A type error when concatenating two terms. -#[derive(Debug)] -pub enum CatError { - /// The first term was unexpectedly nullable. - FirstNullable { - /// The punctuation of the concatenation. - punct: Span, - /// The span of the first term. - fst_span: Span, - /// The first term. - fst: Typed, - }, - /// The flast set of the first term intersects the first set of the second. - FirstFlastOverlap { - /// The punctuation of the concatenation. - punct: Span, - /// The span of the first term. - fst_span: Span, - /// The first term. - fst: Typed, - /// The span of the second term. - snd_span: Span, - /// The second term. - snd: Typed, - }, -} - -impl From for syn::Error { - fn from(other: CatError) -> Self { - match other { - CatError::FirstNullable { - punct, fst_span, .. - } => { - let mut err = Self::new( - punct, - "first item in sequence cannot accept the empty string", - ); - err.combine(Self::new(fst_span, "this can accept empty string")); - err - } - CatError::FirstFlastOverlap { - punct, - fst_span, - snd_span, - .. - } => { - let mut err = Self::new( - punct, - "cannot decide whether to repeat first or start accepting second", - ); - err.combine(Self::new(fst_span, "a repetition of this")); - err.combine(Self::new(snd_span, "collides with the start of this")); - err - } - } - } -} - -impl Display for CatError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::FirstNullable { - punct, - fst_span, - fst, - .. - } => { - let start = punct.start(); - let fst_start = fst_span.start(); - write!( - f, - "{}:{}: term '{}' ({}:{}) accepts the empty string", - start.line, start.column, fst, fst_start.line, fst_start.column - ) - } - Self::FirstFlastOverlap { - punct, - fst, - fst_span, - snd, - snd_span, - .. - } => { - let start = punct.start(); - let fst_start = fst_span.start(); - let snd_start = snd_span.start(); - write!( - f, - "{}:{}: cannot decide whether to repeat '{}' ({}:{}) or start accepting '{}' ({}:{}).", - start.line, start.column, fst, fst_start.line, fst_start.column, snd, snd_start.line, snd_start.column - ) - } - } - } -} - -impl Error for CatError {} - -/// An alternation of two terms. -#[derive(Clone, Debug)] -pub struct Alt { - left: Box, - punct: Token![|], - right: Box, -} - -impl Alt { - /// Creates a new `Alt` from the two terms and the joining punctuation. - pub fn new(left: Term, punct: Token![|], right: Term) -> Self { - Self { - left: Box::new(left), - punct, - right: Box::new(right), - } - } -} - -/// A type error when alternating two terms. -#[derive(Debug)] -pub enum AltError { - /// Both terms are nullable. - BothNullable { - /// The punctuation of the alternation. - punct: Span, - /// The span of the left term. - left_span: Span, - /// The left term. - left: Typed, - /// The span of the right term. - right_span: Span, - /// The right term. - right: Typed, - }, - /// The first sets of the two terms intersect. - FirstOverlap { - /// The punctuation of the alternation. - punct: Span, - /// The span of the left term. - left_span: Span, - /// The left term. - left: Typed, - /// The span of the right term. - right_span: Span, - /// The right term. - right: Typed, - }, -} - -impl From for syn::Error { - fn from(other: AltError) -> Self { - match other { - AltError::BothNullable { - punct, - left_span, - right_span, - .. - } => { - let mut err = Self::new(punct, "both branches accept the empty string"); - err.combine(Self::new(left_span, "left branch accepts the empty string")); - err.combine(Self::new( - right_span, - "right branch accepts the empty string", - )); - err - } - AltError::FirstOverlap { - punct, - left_span, - right_span, - .. - } => { - let mut err = Self::new( - punct, - "cannot decide whether to accept the left or right branch", - ); - err.combine(Self::new(left_span, "left branch starts with a character")); - err.combine(Self::new( - right_span, - "right branch starts with the same character", - )); - err - } - } - } -} - -impl Display for AltError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::BothNullable { - punct, - left_span, - left, - right_span, - right, - .. - } => { - let start = punct.start(); - let left_start = left_span.start(); - let right_start = right_span.start(); - write!( - f, - "{}:{}: both '{}' ({}:{}) and '{}' ({}:{}) accept the empty string.", - start.line, - start.column, - left, - left_start.line, - left_start.column, - right, - right_start.line, - right_start.column, - ) - } - Self::FirstOverlap { - punct, - left_span, - left, - right_span, - right, - .. - } => { - let start = punct.start(); - let left_start = left_span.start(); - let right_start = right_span.start(); - write!( - f, - "{}:{}: cannot decide whether to accept '{}' ({}:{}) or '{}' ({}:{}).", - start.line, - start.column, - left, - left_start.line, - left_start.column, - right, - right_start.line, - right_start.column, - ) - } - } - } -} - -impl Error for AltError {} - -/// The least fixed point of a term. -#[derive(Clone, Debug)] -pub struct Fix { - span: Span, - arg: Ident, - inner: Box, -} - -impl Fix { - /// Creates a new `Fix` from the argument name, inner term and overall span. - pub fn new(arg: Ident, inner: Term, span: Span) -> Self { - Self { - arg, - inner: Box::new(inner), - span, - } - } - - /// Iteratively computes the least fixed point of a function from an initial - /// state. - pub fn fixpoint Result, T: Default + PartialEq, E>( - &self, - mut step: F, - ) -> Result { - let mut res = T::default(); - let mut last = None; - while last.map(|r| r != res).unwrap_or(true) { - last = Some(res); - res = step(self, last.as_ref().unwrap())?; - } - - Ok(res) - } -} - -/// A variable usage -#[derive(Clone, Debug)] -pub struct Variable { - name: Ident, - index: usize, -} - -impl Variable { - /// Creates a new `Variable` from the name and index. - pub fn new(name: Ident, index: usize) -> Self { - Self { name, index } - } -} - -/// A type error when using a fix point variable. -#[derive(Debug)] -pub enum BindingError { - /// Usage of a free binding variable. - FreeBinding(Variable), - /// Usage of a guarded binding variable. - GuardedBinding(Variable), -} - -impl From for syn::Error { - fn from(other: BindingError) -> Self { - match other { - BindingError::FreeBinding(_) => todo!(), - BindingError::GuardedBinding(_) => todo!(), - } - } -} - -impl Display for BindingError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::FreeBinding(var) => { - let start = var.name.span().start(); - write!( - f, - "{}:{}: unbound binding '{}'", - start.line, start.column, var.name - ) - } - Self::GuardedBinding(var) => { - let start = var.name.span().start(); - write!( - f, - "{}:{}: binding '{}' is guarded", - start.line, start.column, var.name - ) - } - } - } -} - -impl Error for BindingError {} - -/// A macro invocation. -#[derive(Clone, Debug)] -pub struct Call { - span: Span, - name: Ident, - args: Vec, -} - -impl Call { - /// Create a new `Call` from the macro name, actual parameters and overall span. - pub fn new(name: Ident, args: Vec, span: Span) -> Self { - Self { name, args, span } - } -} - -/// An abstract Nibble term. -#[derive(Clone, Debug)] -pub enum Term { - /// 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. - Binding(Variable), - /// A formal parameter. - Variable(Variable), - /// A macro invocation. - Call(Call), -} - -impl Term { - /// Dispatches a [`Visitor`] to the underlying term. - pub fn visit(&self, visitor: &mut V) -> ::Out { - match self { - Self::Epsilon(eps) => visitor.visit_epsilon(eps), - Self::Literal(lit) => visitor.visit_literal(lit), - Self::Cat(cat) => visitor.visit_cat(cat), - Self::Alt(alt) => visitor.visit_alt(alt), - Self::Fix(fix) => visitor.visit_fix(fix), - Self::Binding(bind) => visitor.visit_binding(bind), - Self::Variable(var) => visitor.visit_variable(var), - Self::Call(call) => visitor.visit_call(call), - } - } - - /// Dispatches a [`VisitorMut`] to the underlying term. - pub fn visit_mut(&mut self, visitor: &mut V) -> ::Out { - match self { - Self::Epsilon(eps) => visitor.visit_mut_epsilon(eps), - Self::Literal(lit) => visitor.visit_mut_literal(lit), - Self::Cat(cat) => visitor.visit_mut_cat(cat), - Self::Alt(alt) => visitor.visit_mut_alt(alt), - Self::Fix(fix) => visitor.visit_mut_fix(fix), - Self::Binding(bind) => visitor.visit_mut_binding(bind), - Self::Variable(var) => visitor.visit_mut_variable(var), - Self::Call(call) => visitor.visit_mut_call(call), - } - } - - /// Dispatches a [`Folder`] to the underlying term. - pub fn fold(self, folder: &mut F) -> ::Out { - match self { - Self::Epsilon(eps) => folder.fold_epsilon(eps), - Self::Literal(lit) => folder.fold_literal(lit), - Self::Cat(cat) => folder.fold_cat(cat), - Self::Alt(alt) => folder.fold_alt(alt), - Self::Fix(fix) => folder.fold_fix(fix), - Self::Binding(bind) => folder.fold_binding(bind), - Self::Variable(var) => folder.fold_variable(var), - Self::Call(call) => folder.fold_call(call), - } - } -} - -#[derive(Debug)] -/// An error when checking whether a term is well typed. -pub enum TermError { - /// An error with a [`Cat`]. - Cat(CatError), - /// An error with an [`Alt`]. - Alt(AltError), - /// An error with a binding [`Variable`]. - Binding(BindingError), -} - -impl From for TermError { - fn from(other: CatError) -> Self { - Self::Cat(other) - } -} - -impl From for TermError { - fn from(other: AltError) -> Self { - Self::Alt(other) - } -} - -impl From for TermError { - fn from(other: BindingError) -> Self { - Self::Binding(other) - } -} - -impl From for syn::Error { - fn from(other: TermError) -> Self { - match other { - TermError::Cat(e) => e.into(), - TermError::Alt(e) => e.into(), - TermError::Binding(e) => e.into(), - } - } -} - -impl Display for TermError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::Cat(e) => e.fmt(f), - Self::Alt(e) => e.fmt(f), - Self::Binding(e) => e.fmt(f), - } - } -} - -impl Error for TermError {} - -/// Immutably visit parts of a [`Term`]. -pub trait Visitor { - /// The result of visiting terms. - type Out; - fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out; - - fn visit_literal(&mut self, lit: &Literal) -> Self::Out; - - fn visit_cat(&mut self, cat: &Cat) -> Self::Out; - - fn visit_alt(&mut self, alt: &Alt) -> Self::Out; - - fn visit_fix(&mut self, fix: &Fix) -> Self::Out; - - fn visit_binding(&mut self, bind: &Variable) -> Self::Out; - - fn visit_variable(&mut self, var: &Variable) -> Self::Out; - - fn visit_call(&mut self, call: &Call) -> Self::Out; -} - -pub trait VisitorMut { - type Out; - fn visit_mut_epsilon(&mut self, eps: &mut Epsilon) -> Self::Out; - fn visit_mut_literal(&mut self, lit: &mut Literal) -> Self::Out; - fn visit_mut_cat(&mut self, cat: &mut Cat) -> Self::Out; - fn visit_mut_alt(&mut self, alt: &mut Alt) -> Self::Out; - fn visit_mut_fix(&mut self, fix: &mut Fix) -> Self::Out; - fn visit_mut_binding(&mut self, bind: &mut Variable) -> Self::Out; - fn visit_mut_variable(&mut self, var: &mut Variable) -> Self::Out; - fn visit_mut_call(&mut self, call: &mut Call) -> Self::Out; -} - -pub trait Folder { - type Out; - fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out; - fn fold_literal(&mut self, lit: Literal) -> Self::Out; - fn fold_cat(&mut self, cat: Cat) -> Self::Out; - fn fold_alt(&mut self, alt: Alt) -> Self::Out; - fn fold_fix(&mut self, fix: Fix) -> Self::Out; - fn fold_binding(&mut self, bind: Variable) -> Self::Out; - fn fold_variable(&mut self, var: Variable) -> Self::Out; - fn fold_call(&mut self, call: Call) -> Self::Out; -} - -struct Closed(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.fst.visit(self) && cat.snd.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.0 += 1; - let res = fix.inner.visit(self); - self.0 -= 1; - res - } - - fn visit_binding(&mut self, bind: &Variable) -> Self::Out { - self.0 > bind.index - } - - fn visit_variable(&mut self, _var: &Variable) -> Self::Out { - true - } - - fn visit_call(&mut self, call: &Call) -> Self::Out { - call.args.iter().all(|arg| arg.visit(self)) - } -} - -struct Nullable<'a>(NullContext<'a>); - -impl Visitor for Nullable<'_> { - type Out = Result; - - fn visit_epsilon(&mut self, _: &Epsilon) -> Self::Out { - Ok(true) - } - - fn visit_literal(&mut self, lit: &Literal) -> Self::Out { - Ok(lit.value().is_empty()) - } - - fn visit_cat(&mut self, cat: &Cat) -> Self::Out { - if !cat.fst.visit(self)? { - return Ok(false); - } - - self.0.unguard(); - let res = cat.snd.visit(self)?; - self.0.guard(); - Ok(res) - } - - fn visit_alt(&mut self, alt: &Alt) -> Self::Out { - if alt.left.visit(self)? { - Ok(true) - } else { - alt.right.visit(self) - } - } - - fn visit_fix(&mut self, fix: &Fix) -> Self::Out { - fix.fixpoint(|fix, last| { - self.0.push_nullable(*last); - let res = fix.inner.visit(self)?; - self.0.pop_nullable(); - Ok(res) - }) - } - - fn visit_binding(&mut self, bind: &Variable) -> Self::Out { - match self.0.is_guarded(bind.index) { - None => Err(BindingError::FreeBinding(bind.clone())), - Some(true) => Err(BindingError::GuardedBinding(bind.clone())), - Some(false) => Ok(self.0.is_nullable(bind.index).unwrap()), - } - } - - fn visit_variable(&mut self, _var: &Variable) -> Self::Out { - todo!() - } - - fn visit_call(&mut self, _call: &Call) -> Self::Out { - todo!() - } -} - -struct FirstSet<'a>(FirstContext<'a>); - -impl Visitor for FirstSet<'_> { - type Out = Result; - - fn visit_epsilon(&mut self, _: &Epsilon) -> Self::Out { - Ok(typed::FirstSet::new()) - } - - fn visit_literal(&mut self, lit: &Literal) -> Self::Out { - Ok(typed::FirstSet::of_str(&lit.value())) - } - - fn visit_cat(&mut self, cat: &Cat) -> Self::Out { - let mut set = cat.fst.visit(self)?; - - if cat.fst.visit(&mut Nullable(self.0.as_null()))? { - self.0.unguard(); - set.union(cat.snd.visit(self)?); - self.0.guard(); - } - - Ok(set) - } - - fn visit_alt(&mut self, alt: &Alt) -> Self::Out { - let mut set = alt.left.visit(self)?; - set.union(alt.right.visit(self)?); - Ok(set) - } - - fn visit_fix(&mut self, fix: &Fix) -> Self::Out { - let nullable = Nullable(self.0.as_null()).visit_fix(fix)?; - fix.fixpoint(|fix, last: &typed::FirstSet| { - self.0.push_first_set(nullable, last.clone()); - let res = fix.inner.visit(self)?; - self.0.pop_first_set(); - Ok(res) - }) - } - - fn visit_binding(&mut self, bind: &Variable) -> Self::Out { - match self.0.is_guarded(bind.index) { - None => Err(BindingError::FreeBinding(bind.clone())), - Some(true) => Err(BindingError::GuardedBinding(bind.clone())), - Some(false) => Ok(self.0.first_set(bind.index).unwrap().clone()), - } - } - - fn visit_variable(&mut self, _var: &Variable) -> Self::Out { - todo!() - } - - fn visit_call(&mut self, _call: &Call) -> Self::Out { - todo!() - } -} - -struct FlastSet<'a>(&'a mut FlastContext); - -impl Visitor for FlastSet<'_> { - type Out = Result; - - fn visit_epsilon(&mut self, _: &Epsilon) -> Self::Out { - Ok(typed::FlastSet::new()) - } - - fn visit_literal(&mut self, _: &Literal) -> Self::Out { - Ok(typed::FlastSet::new()) - } - - fn visit_cat(&mut self, cat: &Cat) -> Self::Out { - self.0.unguard(); - let mut set = cat.snd.visit(self)?; - let nullable = cat.snd.visit(&mut Nullable(self.0.as_null()))?; - self.0.guard(); - - if nullable { - self.0.unguard(); - set.union_first(cat.snd.visit(&mut FirstSet(self.0.as_first()))?); - self.0.guard(); - set.union(cat.fst.visit(self)?); - } - - Ok(set) - } - - fn visit_alt(&mut self, alt: &Alt) -> Self::Out { - let mut set = alt.left.visit(self)?; - set.union(alt.right.visit(self)?); - Ok(set) - } - - fn visit_fix(&mut self, fix: &Fix) -> Self::Out { - let nullable = Nullable(self.0.as_null()).visit_fix(fix)?; - let first_set = FirstSet(self.0.as_first()).visit_fix(fix)?; - fix.fixpoint(|fix, last: &typed::FlastSet| { - self.0 - .push_flast_set(nullable, first_set.clone(), last.clone()); - let res = fix.inner.visit(self)?; - self.0.pop_flast_set(); - Ok(res) - }) - } - - fn visit_binding(&mut self, bind: &Variable) -> Self::Out { - match self.0.is_guarded(bind.index) { - None => Err(BindingError::FreeBinding(bind.clone())), - Some(true) => Err(BindingError::GuardedBinding(bind.clone())), - Some(false) => Ok(self.0.flast_set(bind.index).unwrap().clone()), - } - } - - fn visit_variable(&mut self, _var: &Variable) -> Self::Out { - todo!() - } - - fn visit_call(&mut self, _call: &Call) -> Self::Out { - todo!() - } -} - -struct Spanning; - -impl Visitor for Spanning { - type Out = Span; - - fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out { - eps.span - } - - fn visit_literal(&mut self, lit: &Literal) -> Self::Out { - lit.span() - } - - fn visit_cat(&mut self, cat: &Cat) -> Self::Out { - let fst = cat.fst.visit(self); - let snd = cat.snd.visit(self); - fst.join(snd).unwrap_or_else(Span::call_site) - } - - fn visit_alt(&mut self, alt: &Alt) -> Self::Out { - let left = alt.left.visit(self); - let right = alt.right.visit(self); - left.join(right).unwrap_or_else(Span::call_site) - } - - fn visit_fix(&mut self, fix: &Fix) -> Self::Out { - fix.span - } - - fn visit_binding(&mut self, var: &Variable) -> Self::Out { - var.name.span() - } - - fn visit_variable(&mut self, var: &Variable) -> Self::Out { - var.name.span() - } - - fn visit_call(&mut self, call: &Call) -> Self::Out { - call.span - } -} - -#[derive(Debug, Default)] -pub struct TypeCheck(FlastContext); - -impl TypeCheck { - pub fn new() -> Self { - Self::default() - } -} - -impl Folder for TypeCheck { - type Out = Result<(Typed, Span), TermError>; - - fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out { - let nullable = Nullable(self.0.as_null()).visit_epsilon(&eps)?; - let first_set = FirstSet(self.0.as_first()).visit_epsilon(&eps)?; - let flast_set = FlastSet(&mut self.0).visit_epsilon(&eps)?; - let span = Spanning.visit_epsilon(&eps); - let kind = TypeKind::Epsilon; - Ok(( - Typed { - kind, - nullable, - first_set, - flast_set, - }, - span, - )) - } - - fn fold_literal(&mut self, lit: Literal) -> Self::Out { - let nullable = Nullable(self.0.as_null()).visit_literal(&lit)?; - let first_set = FirstSet(self.0.as_first()).visit_literal(&lit)?; - let flast_set = FlastSet(&mut self.0).visit_literal(&lit)?; - let span = Spanning.visit_literal(&lit); - let kind = TypeKind::Literal(lit.value()); - Ok(( - Typed { - kind, - nullable, - first_set, - flast_set, - }, - span, - )) - } - - fn fold_cat(&mut self, cat: Cat) -> Self::Out { - let nullable = Nullable(self.0.as_null()).visit_cat(&cat)?; - let first_set = FirstSet(self.0.as_first()).visit_cat(&cat)?; - let flast_set = FlastSet(&mut self.0).visit_cat(&cat)?; - let span = Spanning.visit_cat(&cat); - - let (fst, fst_span) = cat.fst.fold(self)?; - - self.0.unguard(); - let (snd, snd_span) = cat.snd.fold(self)?; - self.0.guard(); - - if fst.is_nullable() { - Err(TermError::Cat(CatError::FirstNullable { - punct: cat.punct.span, - fst_span, - fst, - })) - } else if !fst.flast_set().intersect_first(&snd.first_set()).is_empty() { - Err(TermError::Cat(CatError::FirstFlastOverlap { - punct: cat.punct.span, - fst_span, - fst, - snd_span, - snd, - })) - } else { - let kind = TypeKind::Cat(Box::new(fst), Box::new(snd)); - Ok(( - Typed { - kind, - nullable, - first_set, - flast_set, - }, - span, - )) - } - } - - fn fold_alt(&mut self, alt: Alt) -> Self::Out { - let nullable = Nullable(self.0.as_null()).visit_alt(&alt)?; - let first_set = FirstSet(self.0.as_first()).visit_alt(&alt)?; - let flast_set = FlastSet(&mut self.0).visit_alt(&alt)?; - let span = Spanning.visit_alt(&alt); - - let (left, left_span) = alt.left.fold(self)?; - let (right, right_span) = alt.right.fold(self)?; - - if left.is_nullable() && right.is_nullable() { - Err(TermError::Alt(AltError::BothNullable { - punct: alt.punct.span, - left_span, - left, - right_span, - right, - })) - } else if !left.first_set().intersect(&right.first_set()).is_empty() { - Err(TermError::Alt(AltError::FirstOverlap { - punct: alt.punct.span, - left_span, - left, - right_span, - right, - })) - } else { - let kind = TypeKind::Alt(Box::new(left), Box::new(right)); - Ok(( - Typed { - kind, - nullable, - first_set, - flast_set, - }, - span, - )) - } - } - - fn fold_fix(&mut self, fix: Fix) -> Self::Out { - let nullable = Nullable(self.0.as_null()).visit_fix(&fix)?; - let first_set = FirstSet(self.0.as_first()).visit_fix(&fix)?; - let flast_set = FlastSet(&mut self.0).visit_fix(&fix)?; - let span = Spanning.visit_fix(&fix); - - self.0 - .push_flast_set(nullable, first_set.clone(), flast_set.clone()); - let (inner, _) = fix.inner.fold(self)?; - self.0.pop_flast_set(); - - let kind = TypeKind::Fix(Box::new(inner)); - - Ok(( - Typed { - kind, - nullable, - first_set, - flast_set, - }, - span, - )) - } - - fn fold_binding(&mut self, bind: Variable) -> Self::Out { - let nullable = Nullable(self.0.as_null()).visit_binding(&bind)?; - let first_set = FirstSet(self.0.as_first()).visit_binding(&bind)?; - let flast_set = FlastSet(&mut self.0).visit_binding(&bind)?; - let span = Spanning.visit_binding(&bind); - let kind = TypeKind::Binding(bind.index); - - Ok(( - Typed { - kind, - nullable, - first_set, - flast_set, - }, - span, - )) - } - - fn fold_variable(&mut self, _var: Variable) -> Self::Out { - todo!() - } - - fn fold_call(&mut self, _call: Call) -> Self::Out { - todo!() - } -} - -struct DeepenVars(usize); - -impl VisitorMut for DeepenVars { - type Out = (); - - fn visit_mut_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {} - - fn visit_mut_literal(&mut self, _: &mut Literal) -> Self::Out {} - - fn visit_mut_cat(&mut self, cat: &mut Cat) -> Self::Out { - cat.fst.visit_mut(self); - cat.snd.visit_mut(self); - } - - fn visit_mut_alt(&mut self, alt: &mut Alt) -> Self::Out { - alt.left.visit_mut(self); - alt.right.visit_mut(self); - } - - fn visit_mut_fix(&mut self, fix: &mut Fix) -> Self::Out { - self.0 += 1; - fix.inner.visit_mut(self); - self.0 -= 1; - } - - fn visit_mut_binding(&mut self, bind: &mut Variable) -> Self::Out { - if bind.index >= self.0 { - bind.index += 1; - } - } - - fn visit_mut_variable(&mut self, _: &mut Variable) -> Self::Out {} - - fn visit_mut_call(&mut self, call: &mut Call) -> Self::Out { - for arg in &mut call.args { - arg.visit_mut(self); - } - } -} - -struct ShallowVars(usize); - -impl VisitorMut for ShallowVars { - type Out = (); - - fn visit_mut_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {} - - fn visit_mut_literal(&mut self, _: &mut Literal) -> Self::Out {} - - fn visit_mut_cat(&mut self, cat: &mut Cat) -> Self::Out { - cat.fst.visit_mut(self); - cat.snd.visit_mut(self); - } - - fn visit_mut_alt(&mut self, alt: &mut Alt) -> Self::Out { - alt.left.visit_mut(self); - alt.right.visit_mut(self); - } - - fn visit_mut_fix(&mut self, fix: &mut Fix) -> Self::Out { - self.0 += 1; - fix.inner.visit_mut(self); - self.0 -= 1; - } - - fn visit_mut_binding(&mut self, bind: &mut Variable) -> Self::Out { - if bind.index > self.0 { - bind.index -= 1; - } - } - - fn visit_mut_variable(&mut self, _: &mut Variable) -> Self::Out { - todo!() - } - - fn visit_mut_call(&mut self, call: &mut Call) -> Self::Out { - for arg in &mut call.args { - arg.visit_mut(self); - } - } -} - -struct Substitute(Vec); - -impl Folder for Substitute { - type Out = Result; - - fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out { - Ok(Term::Epsilon(eps)) - } - - fn fold_literal(&mut self, lit: Literal) -> Self::Out { - Ok(Term::Literal(lit)) - } - - fn fold_cat(&mut self, cat: Cat) -> Self::Out { - let fst = cat.fst.fold(self)?; - let snd = cat.snd.fold(self)?; - Ok(Term::Cat(Cat { - fst: Box::new(fst), - punct: cat.punct, - snd: Box::new(snd), - })) - } - - fn fold_alt(&mut self, alt: Alt) -> Self::Out { - let left = alt.left.fold(self)?; - let right = alt.right.fold(self)?; - Ok(Term::Alt(Alt { - left: Box::new(left), - punct: alt.punct, - right: Box::new(right), - })) - } - - fn fold_fix(&mut self, fix: Fix) -> Self::Out { - for var in &mut self.0 { - var.visit_mut(&mut DeepenVars(0)); - } - let inner = fix.inner.fold(self)?; - for var in &mut self.0 { - var.visit_mut(&mut ShallowVars(0)); - } - Ok(Term::Fix(Fix { - span: fix.span, - arg: fix.arg, - inner: Box::new(inner), - })) - } - - fn fold_binding(&mut self, var: Variable) -> Self::Out { - Ok(Term::Binding(var)) - } - - fn fold_call(&mut self, call: Call) -> Self::Out { - let args = call - .args - .into_iter() - .map(|arg| arg.fold(self)) - .collect::>()?; - Ok(Term::Call(Call { - span: call.span, - name: call.name, - args, - })) - } - - fn fold_variable(&mut self, var: Variable) -> Self::Out { - self.0 - .get(var.index) - .cloned() - .ok_or(SubstituteError::FreeVariable(var)) - } -} - -#[derive(Clone, Debug)] -pub struct InlineCall { - name: String, - term: Term, - args: usize, -} - -impl InlineCall { - pub fn new(name: Ident, term: Term, args: usize) -> Self { - Self { - name: name.to_string(), - term, - args, - } - } -} - -impl Folder for InlineCall { - type Out = Result; - - fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out { - Ok(Term::Epsilon(eps)) - } - - fn fold_literal(&mut self, lit: Literal) -> Self::Out { - Ok(Term::Literal(lit)) - } - - fn fold_cat(&mut self, cat: Cat) -> Self::Out { - let fst = cat.fst.fold(self)?; - let snd = cat.snd.fold(self)?; - Ok(Term::Cat(Cat { - fst: Box::new(fst), - punct: cat.punct, - snd: Box::new(snd), - })) - } - - fn fold_alt(&mut self, alt: Alt) -> Self::Out { - let left = alt.left.fold(self)?; - let right = alt.right.fold(self)?; - Ok(Term::Alt(Alt { - left: Box::new(left), - punct: alt.punct, - right: Box::new(right), - })) - } - - fn fold_fix(&mut self, fix: Fix) -> Self::Out { - let inner = fix.inner.fold(self)?; - Ok(Term::Fix(Fix { - span: fix.span, - arg: fix.arg, - inner: Box::new(inner), - })) - } - - fn fold_binding(&mut self, bind: Variable) -> Self::Out { - Ok(Term::Binding(bind)) - } - - fn fold_variable(&mut self, var: Variable) -> Self::Out { - Ok(Term::Variable(var)) - } - - fn fold_call(&mut self, call: Call) -> Self::Out { - if call.name != self.name { - let args = call - .args - .into_iter() - .map(|arg| arg.fold(self)) - .collect::>()?; - Ok(Term::Call(Call { - span: call.span, - name: call.name, - args, - })) - } else if call.args.len() != self.args { - Err(SubstituteError::WrongArgCount { - call, - expected: self.args, - }) - } else { - let args = call - .args - .into_iter() - .map(|arg| arg.fold(self)) - .collect::>()?; - self.term.clone().fold(&mut Substitute(args)) - } - } -} - -#[derive(Debug)] -pub enum SubstituteError { - FreeVariable(Variable), - WrongArgCount { call: Call, expected: usize }, -} - -impl Display for SubstituteError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::FreeVariable(var) => { - let start = var.name.span().start(); - write!( - f, - "{}:{}: undeclared variable '{}'", - start.line, start.column, var.name - ) - } - SubstituteError::WrongArgCount { call, expected } => { - let start = call.span.start(); - write!( - f, - "{}:{}: wrong number of arguments. Expected {}, got {}", - start.line, - start.column, - call.args.len(), - expected - ) - } - } - } -} - -impl Error for SubstituteError {} - -#[derive(Clone, Debug, Eq, PartialEq, Hash)] -enum TypeKind { - Epsilon, - Literal(String), - Cat(Box, Box), - Alt(Box, Box), - Fix(Box), - Binding(usize), -} - -#[derive(Debug)] -pub struct Code { - id: usize, -} - -impl TypeKind { - /// Produces ident for the type and token stream for implementation - fn emit_code(self, context: &mut CodeContext) -> Code { - match self { - Self::Epsilon => context.epsilon(), - Self::Literal(s) => context.literal(s), - Self::Cat(fst, snd) => { - let Typed { kind: fst_kind, .. } = *fst; - let Typed { kind: snd_kind, .. } = *snd; - let fst_code = fst_kind.emit_code(context); - let snd_code = snd_kind.emit_code(context); - context.cat(fst_code, snd_code) - } - Self::Alt(left, right) => { - let Typed { - kind: left_kind, - nullable: left_null, - first_set: left_first, - .. - } = *left; - let Typed { - kind: right_kind, - nullable: right_null, - first_set: right_first, - .. - } = *right; - let left_code = left_kind.emit_code(context); - let right_code = right_kind.emit_code(context); - context.alt( - left_code, - left_null, - left_first, - right_code, - right_null, - right_first, - ) - } - Self::Fix(inner) => { - let Typed { - kind: inner_kind, .. - } = *inner; - context.fix(inner_kind) - } - Self::Binding(index) => context.variable(index), - } - } -} - -impl Display for TypeKind { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match self { - Self::Epsilon => write!(f, "_"), - Self::Literal(s) => write!(f, "{:?}", s), - Self::Cat(fst, snd) => write!(f, "{}.{}", fst, snd), - Self::Alt(left, right) => write!(f, "({} | {})", left, right), - Self::Fix(inner) => write!(f, "[]({})", inner), - Self::Binding(index) => write!(f, "{}", index), - } - } -} - -#[derive(Clone, Debug, Eq, PartialEq, Hash)] -pub struct Typed { - kind: TypeKind, - nullable: bool, - first_set: typed::FirstSet, - flast_set: typed::FlastSet, -} - -impl Typed { - pub fn is_nullable(&self) -> bool { - self.nullable - } - - pub fn first_set(&self) -> &typed::FirstSet { - &self.first_set - } - - pub fn flast_set(&self) -> &typed::FlastSet { - &self.flast_set - } - - pub fn emit_code(self, name: Ident) -> TokenStream { - let mut context = CodeContext::new(); - let code = self.kind.emit_code(&mut context); - context.all_code(name, code) - } -} - -impl Display for Typed { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - self.kind.fmt(f) - } -} - -#[derive(Debug)] -pub struct CodeContext { - data: Vec<(TokenStream, TokenStream, BTreeSet)>, - lit_map: HashMap, - cat_map: HashMap<(usize, usize), usize>, - alt_map: HashMap<(usize, usize), usize>, - fix_map: HashMap, - var_map: HashMap, // Key is fix point ID - context: Vec, -} - -impl CodeContext { - fn new() -> Self { - let eps = (quote! {()}, TokenStream::new(), BTreeSet::new()); - - Self { - data: vec![eps], - lit_map: HashMap::new(), - cat_map: HashMap::new(), - alt_map: HashMap::new(), - fix_map: HashMap::new(), - var_map: HashMap::new(), - context: Vec::new(), - } - } - - fn epsilon(&mut self) -> Code { - Code { id: 0 } - } - - fn literal(&mut self, lit: String) -> Code { - if let Some(&id) = self.lit_map.get(&lit) { - Code { id } - } else { - let id = self.data.len(); - let name = format_ident!("Lit{}", id); - let doc_name = format!( - r#"The literal string `"{}"`."#, - lit.escape_debug().collect::() - ); - let tokens = quote! { - #[doc=#doc_name] - pub struct #name; - - impl Parse for #name { - fn parse(input: &mut P) -> Result { - input.take_str(#lit).map(|()| #name) - } - } - }; - - self.data - .push((TokenTree::from(name).into(), tokens, BTreeSet::new())); - self.lit_map.insert(lit, id); - - Code { id } - } - } - - fn cat(&mut self, fst: Code, snd: Code) -> Code { - if let Some(&id) = self.cat_map.get(&(fst.id, snd.id)) { - Code { id } - } else { - let id = self.data.len(); - let fst_ty = self.data[fst.id].0.clone(); - let snd_ty = self.data[snd.id].0.clone(); - self.data.push(( - quote! {(#fst_ty, #snd_ty)}, - TokenStream::new(), - [fst.id, snd.id].iter().cloned().collect(), - )); - self.cat_map.insert((fst.id, snd.id), id); - Code { id } - } - } - - fn alt( - &mut self, - left_code: Code, - left_null: bool, - left_first: typed::FirstSet, - right_code: Code, - right_null: bool, - right_first: typed::FirstSet, - ) -> Code { - if let Some(&id) = self.alt_map.get(&(left_code.id, right_code.id)) { - Code { id } - } else { - let id = self.data.len(); - let left_ty = self.data[left_code.id].0.clone(); - let right_ty = self.data[right_code.id].0.clone(); - let name = format_ident!("Alt{}", id); - let mut tokens = quote! { - pub enum #name { - Left(#left_ty), - Right(#right_ty), - } - }; - - let other = if left_null { - let iter = right_first.into_iter(); - - quote! { - impl Parse for #name { - fn parse(input: &mut P) -> Result { - match input.peek() { - #(Some(#iter))|* => input.parse().map(Self::Right), - _ => input.parse().map(Self::Left), - } - } - } - } - } else if right_null { - let iter = left_first.into_iter(); - - quote! { - impl Parse for #name { - fn parse(input: &mut P) -> Result { - match input.peek() { - #(Some(#iter))|* => input.parse().map(Self::Left), - _ => input.parse().map(Self::Right), - } - } - } - } - } else { - let mut first = left_first.clone(); - first.union(right_first.clone()); - let iter_first = first.into_iter(); - let iter_left = left_first.into_iter(); - let iter_right = right_first.into_iter(); - - quote! { - impl Parse for #name { - fn parse(input: &mut P) -> Result { - match input.peek().ok_or(Error::EndOfStream)? { - #(#iter_left)|* => input.parse().map(Self::Left), - #(#iter_right)|* => input.parse().map(Self::Right), - c => input.error(Error::BadBranch(c, &[#(#iter_first),*])) - } - } - } - } - }; - - tokens.extend(other); - self.data.push(( - TokenTree::from(name).into(), - tokens, - [left_code.id, right_code.id].iter().cloned().collect(), - )); - self.alt_map.insert((left_code.id, right_code.id), id); - Code { id } - } - } - - fn fix(&mut self, inner: TypeKind) -> Code { - if let Some(&id) = self.fix_map.get(&inner) { - Code { id } - } else { - let id = self.data.len(); - let name = format_ident!("Fix{}", id); - self.data.push(( - TokenTree::from(name.clone()).into(), - TokenStream::new(), - BTreeSet::new(), - )); - self.context.push(id); - let inner = inner.emit_code(self).id; - let inner_ty = self.data[inner].0.clone(); - let tokens = quote! { - pub struct #name(#inner_ty); - - impl Parse for #name { - fn parse(input: &mut P) -> Result { - input.parse().map(Self) - } - } - }; - self.data[id].1 = tokens; - self.data[id].2 = [inner].iter().cloned().collect(); - Code { id } - } - } - - fn variable(&mut self, index: usize) -> Code { - let fix_id = self.context[self.context.len() - index - 1]; - if let Some(&id) = self.var_map.get(&fix_id) { - Code { id } - } else { - let id = self.data.len(); - let fix_ty = self.data[fix_id].0.clone(); - let name = quote! {Box<#fix_ty>}; - self.data.push((name, TokenStream::new(), BTreeSet::new())); - self.var_map.insert(fix_id, id); - Code { id } - } - } - - pub fn all_code(&mut self, name: Ident, code: Code) -> TokenStream { - let root = self.data[code.id].clone(); - let mut tokens = root.1; - let mut completed = [code.id].iter().cloned().collect::>(); - let mut todo = root.2; - - while !todo.is_empty() { - let mut next = BTreeSet::new(); - completed.extend(todo.clone()); - - for ty in todo { - let ty = self.data[ty].clone(); - tokens.extend(ty.1); - next.extend(ty.2.into_iter().filter(|id| !completed.contains(id))); - } - - todo = next; - } - - let root_ty = root.0; - tokens.extend(quote! { - pub type #name = #root_ty; - - pub enum Error { - BadBranch(char, &'static [char]), - EndOfStream, - } - - pub type Result = std::result::Result; - - pub trait Parser: Iterator { - fn peek(&mut self) -> Option; - - fn parse(&mut self) -> Result where Self: Sized { - T::parse(self) - } - - fn take_str(&mut self, s: &str) -> Result<()>; - - fn error(&mut self, e: Error) -> Result; - } - - pub trait Parse: Sized { - fn parse(input: &mut P) -> Result; - } - - impl Parse for () { - fn parse(_input: &mut P) -> Result { - Ok(()) - } - } - - impl Parse for (A, B) { - fn parse(input: &mut P) -> Result { - let a = input.parse()?; - let b = input.parse()?; - Ok((a, b)) - } - } - - impl Parse for Box { - fn parse(input: &mut P) -> Result { - input.parse().map(Box::new) - } - } - }); - - tokens - } -} diff --git a/src/ast/typed.rs b/src/ast/typed.rs deleted file mode 100644 index 7c3f89e..0000000 --- a/src/ast/typed.rs +++ /dev/null @@ -1,284 +0,0 @@ -use std::collections::BTreeSet; - -#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)] -pub struct FirstSet { - inner: BTreeSet, -} - -impl FirstSet { - pub fn new() -> Self { - Self::default() - } - - pub fn of_str(s: &str) -> Self { - let mut inner = BTreeSet::new(); - s.chars().next().map(|c| inner.insert(c)); - - Self { inner } - } - - pub fn is_empty(&self) -> bool { - self.inner.is_empty() - } - - pub fn union(&mut self, mut other: Self) { - self.inner.append(&mut other.inner); - } - - pub fn intersect(&self, other: &Self) -> Self { - Self { - inner: self.inner.intersection(&other.inner).copied().collect(), - } - } -} - -impl IntoIterator for FirstSet { - type Item = char; - - type IntoIter = as IntoIterator>::IntoIter; - - fn into_iter(self) -> Self::IntoIter { - self.inner.into_iter() - } -} - -#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)] -pub struct FlastSet { - inner: BTreeSet, -} - -impl FlastSet { - pub fn new() -> Self { - Self::default() - } - - pub fn is_empty(&self) -> bool { - self.inner.is_empty() - } - - pub fn union_first(&mut self, mut other: FirstSet) { - self.inner.append(&mut other.inner); - } - - pub fn union(&mut self, mut other: Self) { - self.inner.append(&mut other.inner); - } - - pub fn intersect_first(&self, other: &FirstSet) -> Self { - Self { - inner: self.inner.intersection(&other.inner).copied().collect(), - } - } - - pub fn intersect(&self, other: &Self) -> Self { - Self { - inner: self.inner.intersection(&other.inner).copied().collect(), - } - } -} - -#[derive(Debug)] -pub struct NullContext<'a> { - inner: &'a mut FlastContext, -} - -impl NullContext<'_> { - pub fn depth(&self) -> usize { - self.inner.depth() - } - - pub fn is_guarded(&self, index: usize) -> Option { - self.inner.is_guarded(index) - } - - pub fn with_unguard R, R>(&mut self, f: F) -> R { - self.unguard(); - let res = f(self); - self.guard(); - res - } - - pub(crate) fn unguard(&mut self) { - self.inner.unguard() - } - - pub(crate) fn guard(&mut self) { - self.inner.guard() - } - - pub fn is_nullable(&self, index: usize) -> Option { - self.inner.is_nullable(index) - } - - pub fn with_nullable R, R>(&mut self, nullable: bool, f: F) -> R { - self.push_nullable(nullable); - let res = f(self); - self.guard(); - res - } - - pub(crate) fn push_nullable(&mut self, nullable: bool) { - self.inner.push_nullable(nullable) - } - - pub(crate) fn pop_nullable(&mut self) { - self.inner.pop_nullable() - } -} - -#[derive(Debug)] -pub struct FirstContext<'a> { - inner: &'a mut FlastContext, -} - -impl FirstContext<'_> { - pub fn depth(&self) -> usize { - self.inner.depth() - } - - pub fn is_guarded(&self, index: usize) -> Option { - self.inner.is_guarded(index) - } - - pub fn with_unguard R, R>(&mut self, f: F) -> R { - self.unguard(); - let res = f(self); - self.guard(); - res - } - - pub(crate) fn unguard(&mut self) { - self.inner.unguard() - } - - pub(crate) fn guard(&mut self) { - self.inner.guard() - } - - pub fn first_set(&self, index: usize) -> Option<&FirstSet> { - self.inner.first_set(index) - } - - pub fn with_first_set R, R>( - &mut self, - nullable: bool, - first_set: FirstSet, - f: F, - ) -> R { - self.push_first_set(nullable, first_set); - let res = f(self); - self.pop_first_set(); - res - } - - pub(crate) fn push_first_set(&mut self, nullable: bool, first_set: FirstSet) { - self.inner.push_first_set(nullable, first_set) - } - - pub(crate) fn pop_first_set(&mut self) { - self.inner.pop_first_set() - } - - pub fn as_null(&mut self) -> NullContext<'_> { - NullContext { inner: self.inner } - } -} - -#[derive(Debug, Default)] -pub struct FlastContext { - binds: Vec<(bool, FirstSet, FlastSet)>, - unguard_points: Vec, -} - -impl FlastContext { - pub fn new() -> Self { - Self::default() - } - - pub fn depth(&self) -> usize { - self.binds.len() - } - - pub fn is_guarded(&self, index: usize) -> Option { - if self.binds.len() <= index { - None - } else if self.unguard_points.is_empty() { - Some(true) - } else { - Some(self.unguard_points[self.unguard_points.len() - 1] + index < self.binds.len()) - } - } - - pub fn with_unguard R, R>(&mut self, f: F) -> R { - self.unguard(); - let res = f(self); - self.guard(); - res - } - - pub(crate) fn unguard(&mut self) { - self.unguard_points.push(self.binds.len()); - } - - pub(crate) fn guard(&mut self) { - self.unguard_points.pop(); - } - - fn is_nullable(&self, index: usize) -> Option { - self.binds.get(self.binds.len() - index - 1).map(|(null, _, _)| *null) - } - - fn push_nullable(&mut self, nullable: bool) { - self.binds - .push((nullable, FirstSet::default(), FlastSet::default())) - } - - fn pop_nullable(&mut self) { - self.binds.pop(); - } - - fn first_set(&self, index: usize) -> Option<&FirstSet> { - self.binds.get(self.binds.len() - index - 1).map(|(_, first, _)| first) - } - - fn push_first_set(&mut self, nullable: bool, first_set: FirstSet) { - self.binds.push((nullable, first_set, FlastSet::default())) - } - - fn pop_first_set(&mut self) { - self.binds.pop(); - } - - pub fn flast_set(&self, index: usize) -> Option<&FlastSet> { - self.binds.get(self.binds.len() - index - 1).map(|(_, _, flast)| flast) - } - - pub fn with_flast_set R, R>( - &mut self, - nullable: bool, - first_set: FirstSet, - flast_set: FlastSet, - f: F, - ) -> R { - self.push_flast_set(nullable, first_set, flast_set); - let res = f(self); - self.pop_flast_set(); - res - } - - pub(crate) fn push_flast_set(&mut self, nullable: bool, first_set: FirstSet, flast_set: FlastSet) { - self.binds.push((nullable, first_set, flast_set)); - } - - pub(crate) fn pop_flast_set(&mut self) { - self.binds.pop(); - } - - pub fn as_first(&mut self) -> FirstContext<'_> { - FirstContext { inner: self } - } - - pub fn as_null(&mut self) -> NullContext<'_> { - NullContext { inner: self } - } -} -- cgit v1.2.3