From aa7585d8bf84f27adeaf57e35f430e2e82a5d208 Mon Sep 17 00:00:00 2001 From: Greg Brown Date: Fri, 20 Nov 2020 16:04:50 +0000 Subject: Precompute properties of well-typed terms --- src/ast/mod.rs | 135 +++++++++++++++++++++++++++++++++++++++++++++++-------- src/ast/typed.rs | 17 +++++-- 2 files changed, 130 insertions(+), 22 deletions(-) diff --git a/src/ast/mod.rs b/src/ast/mod.rs index 0e3feea..10054fc 100644 --- a/src/ast/mod.rs +++ b/src/ast/mod.rs @@ -40,6 +40,10 @@ impl Epsilon { impl Type for Epsilon { type Err = Infallible; + fn closed(&self, _depth: usize) -> Result<(), VariableError> { + Ok(()) + } + fn is_nullable(&self, _context: &mut C) -> Option { Some(true) } @@ -53,7 +57,12 @@ impl Type for Epsilon { } fn well_typed(self, _context: &mut C) -> Result { - Ok(Typed::Epsilon) + Ok(Typed { + kind: TypeKind::Epsilon, + nullable: true, + first_set: FirstSet::new(), + flast_set: FlastSet::new(), + }) } } @@ -62,6 +71,10 @@ pub type Literal = LitStr; impl Type for Literal { type Err = Infallible; + fn closed(&self, _depth: usize) -> Result<(), VariableError> { + Ok(()) + } + fn is_nullable(&self, _context: &mut C) -> Option { Some(self.value().is_empty()) } @@ -75,7 +88,15 @@ impl Type for Literal { } fn well_typed(self, _context: &mut C) -> Result { - Ok(Typed::Literal(self.value())) + let value = self.value(); + let nullable = value.is_empty(); + let first_set = FirstSet::of_str(&value); + Ok(Typed { + kind: TypeKind::Literal(value), + nullable, + first_set, + flast_set: FlastSet::new(), + }) } } @@ -99,6 +120,10 @@ impl Cat { impl Type for Cat { type Err = CatError; + fn closed(&self, depth: usize) -> Result<(), VariableError> { + self.fst.closed(depth).and_then(|()| self.snd.closed(depth)) + } + fn is_nullable(&self, context: &mut C) -> Option { Some(self.fst.is_nullable(context)? && self.snd.is_nullable(context)?) } @@ -141,7 +166,23 @@ impl Type for Cat { } else if !fst.flast_set().intersect_first(&snd.first_set()).is_empty() { Err(CatError::FirstFlastOverlap(fst, snd)) } else { - Ok(Typed::Cat(Box::new(fst), Box::new(snd))) + // fst.is_nullable always false + let nullable = false; + let first_set = fst.first_set().clone(); + let flast_set = if snd.is_nullable() { + snd.flast_set() + .clone() + .union_first(snd.first_set().clone()) + .union(fst.flast_set().clone()) + } else { + snd.flast_set().clone() + }; + Ok(Typed { + kind: TypeKind::Cat(Box::new(fst), Box::new(snd)), + nullable, + first_set, + flast_set, + }) } } } @@ -180,6 +221,12 @@ impl Alt { impl Type for Alt { type Err = AltError; + fn closed(&self, depth: usize) -> Result<(), VariableError> { + self.left + .closed(depth) + .and_then(|()| self.right.closed(depth)) + } + fn is_nullable(&self, context: &mut C) -> Option { Some(self.left.is_nullable(context)? || self.right.is_nullable(context)?) } @@ -215,7 +262,15 @@ impl Type for Alt { } else if !left.first_set().intersect(&right.first_set()).is_empty() { Err(AltError::FirstOverlap(left, right)) } else { - Ok(Typed::Alt(Box::new(left), Box::new(right))) + let nullable = false; + let first_set = left.first_set().clone().union(right.first_set().clone()); + let flast_set = left.flast_set().clone().union(right.flast_set().clone()); + Ok(Typed { + kind: TypeKind::Alt(Box::new(left), Box::new(right)), + nullable, + first_set, + flast_set, + }) } } } @@ -254,6 +309,10 @@ impl Fix { impl Type for Fix { type Err = TermError; + fn closed(&self, depth: usize) -> Result<(), VariableError> { + self.inner.closed(depth + 1) + } + fn is_nullable(&self, context: &mut C) -> Option { fix(Some(false), |last| { last.as_ref() @@ -284,16 +343,22 @@ impl Type for Fix { } fn well_typed(self, context: &mut C) -> Result { - // FIXME: free variables cause panic + self.inner.closed(context.get_depth() + 1)?; + let nullable = self.is_nullable(context).unwrap(); let first_set = self.first_set(context).unwrap(); let flast_set = self.flast_set(context).unwrap(); context - .push_flast_set(nullable, first_set, flast_set, |ctx| { + .push_flast_set(nullable, first_set.clone(), flast_set.clone(), |ctx| { self.inner.well_typed(ctx) }) - .map(|inner| Typed::Fix(Box::new(inner))) + .map(|inner| Typed { + kind: TypeKind::Fix(Box::new(inner)), + nullable, + first_set, + flast_set, + }) } } @@ -312,6 +377,14 @@ impl Variable { impl Type for Variable { type Err = VariableError; + fn closed(&self, depth: usize) -> Result<(), VariableError> { + if self.index < depth { + Ok(()) + } else { + Err(VariableError::FreeVariable(self.clone())) + } + } + fn is_nullable(&self, context: &mut C) -> Option { context.get_nullable(self.index) } @@ -325,10 +398,12 @@ impl Type for Variable { } fn well_typed(self, context: &mut C) -> Result { - match context.get_flast_set(self.index) { - Some(_) => Ok(Typed::Variable(self.index)), - None => Err(VariableError::FreeVariable(self)), - } + self.closed(context.get_depth()).map(|()| Typed { + kind: TypeKind::Variable(self.index), + nullable: self.is_nullable(context).unwrap(), + first_set: self.first_set(context).unwrap(), + flast_set: self.flast_set(context).unwrap(), + }) } } @@ -359,6 +434,10 @@ impl Call { impl Type for Call { type Err = Infallible; + fn closed(&self, _depth: usize) -> Result<(), VariableError> { + todo!() + } + fn is_nullable(&self, _context: &mut C) -> Option { todo!() } @@ -390,6 +469,18 @@ pub enum Term { impl Type for Term { type Err = TermError; + fn closed(&self, depth: usize) -> Result<(), VariableError> { + match self { + Self::Epsilon(e) => e.closed(depth), + Self::Literal(e) => e.closed(depth), + Self::Cat(e) => e.closed(depth), + Self::Alt(e) => e.closed(depth), + Self::Fix(e) => e.closed(depth), + Self::Variable(e) => e.closed(depth), + Self::Call(e) => e.closed(depth), + } + } + fn is_nullable(&self, context: &mut C) -> Option { match self { Self::Epsilon(e) => e.is_nullable(context), @@ -453,19 +544,19 @@ impl From for TermError { } impl From for TermError { - fn from(other: CatError) -> Self{ + fn from(other: CatError) -> Self { Self::Cat(other) } } impl From for TermError { - fn from(other: AltError) -> Self{ + fn from(other: AltError) -> Self { Self::Alt(other) } } impl From for TermError { - fn from(other: VariableError) -> Self{ + fn from(other: VariableError) -> Self { Self::Variable(other) } } @@ -477,15 +568,21 @@ impl Display for TermError { } #[derive(Clone, Debug, Eq, PartialEq)] -pub enum Typed { +enum TypeKind { Epsilon, - Bottom, Literal(String), Cat(Box, Box), Alt(Box, Box), Fix(Box), Variable(usize), - Call(Ident, Vec), +} + +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Typed { + kind: TypeKind, + nullable: bool, + first_set: FirstSet, + flast_set: FlastSet, } impl Typed { @@ -493,11 +590,11 @@ impl Typed { todo!() } - pub fn first_set(&self) -> FirstSet { + pub fn first_set(&self) -> &FirstSet { todo!() } - pub fn flast_set(&self) -> FlastSet { + pub fn flast_set(&self) -> &FlastSet { todo!() } } diff --git a/src/ast/typed.rs b/src/ast/typed.rs index 48ca740..e277cbb 100644 --- a/src/ast/typed.rs +++ b/src/ast/typed.rs @@ -1,4 +1,5 @@ use super::Typed; +use super::VariableError; use std::collections::BTreeSet; use std::fmt::Display; @@ -79,6 +80,8 @@ impl FlastSet { pub trait NullContext { type PushNull: NullContext; + fn get_depth(&self) -> usize; + fn get_nullable(&self, index: usize) -> Option; fn push_nullable R, R>(&mut self, nullable: bool, f: F) -> R; @@ -115,15 +118,23 @@ pub trait Type { type Err: Display; /// # Errors - /// Returns [`None`] if the nullity cannot be determined. + /// Returns [`Err`] if there is a variable with an index greater than or equal + /// to `depth`. + fn closed(&self, depth: usize) -> Result<(), VariableError>; + + /// # Errors + /// Returns [`None`] only if `self.closed(context.get_depth())` returns an + /// [`Err`]. fn is_nullable(&self, context: &mut C) -> Option; /// # Errors - /// Returns [`None`] if the first set cannot be determined. + /// Returns [`None`] only if `self.closed(context.get_depth())` returns an + /// [`Err`]. fn first_set(&self, context: &mut C) -> Option; /// # Errors - /// Returns [`None`] if the flast set cannot be determined. + /// Returns [`None`] only if `self.closed(context.get_depth())` returns an + /// [`Err`]. fn flast_set(&self, context: &mut C) -> Option; /// # Errors -- cgit v1.2.3